摘 要： 提出一种基于PEGASIS的路由改进算法，引入记忆和比较的方法寻找最优可连接的节点，避免产生长链，从而导致部分节点因传输距离过大和耗能过多而过快死亡。给出了一种均衡各节点能耗的新簇头选择方案，对该模型的系统总能耗进行量化分析。通过仿真证明，该方案相对普通PEGASIS路由算法消耗能量更低，延长了网络寿命。
关键词： PEGASIS；能耗；记忆策略；能距比；无线传感器网络
低功耗无线通信技术、微型传感器技术和计算机嵌入式技术的迅猛发展，使各种大量无线传感器自主构建成无线传感器网络成为现实。在无线传感器网络中，由于其节点能量非常有限，无法进行补充，一旦节点能量耗尽，会给通信和信息的采集带来严重的障碍。因此，如何构建无线传感器网络来提高能量的有效性、延长网络寿命、避免网络分裂、均衡节点能耗、降低传输时延成为学者们讨论的主要话题。本文以链式PEGASIS协议为基础，改进协议避免产生长链消耗过多能量，提出新的簇头选择方法，并进行量化研究。
1 协议分析及改进
1.1 协议知识
PEGASIS协议是一种典型基于链状结构的路由协议，是LEACH协议的改进。PEGASIS算法的核心思想是利用贪婪算法生成一条单链，然后随机选择链中一个节点作为簇头节点，为了延长网络生命周期，每个节点只与最近的节点进行通信，然后将数据汇总给簇头节点，由簇头节点将数据发给基站。
PEGASIS协议的成链过程按轮进行，首先从距离基站最远的节点开始建链，将此节点作为端节点，然后查找它的最近节点，并将此最近节点加入链中，再由新加入的节点搜索除了原端点以外的最近节点，如此寻找下去，直到将所有节点形成一个单链，并且随机选出簇头节点。图1为链形成的流程。其中END表示当前节点，CHAIN表示形成的链。
链中的数据发送模式为：簇头节点首先给两端节点发送一个TOKEN，然后两端节点将收集到的数据发送给链中上一个节点，上一个节点接收到数据以后，融合自身的数据后再发送到上一个节点，直到两边都将数据发送给簇头节点。簇头节点最后融合两边收到的数据，再与基站进行通信。
相比LEACH算法，PEGASIS路由算法减少了节点之间的通信平均距离，也不需要动态形成簇而产生的额外开销，只有一个簇头节点将数据传送到基站，节省了能量的消耗。但是此方案也存在严重的缺点，图2(a)为随机生成的20个节点，图2(b)为经过PEGASIS路由算法后形成的链，从中可见，节点11与12、16与17、18与19之间的链路距离相对于别的节点间距离明显偏大，因此会造成11、16、18这三个节点发送数据的耗能过大，导致这几个节点过早死亡，阻断通信。为了实现节能，必须改进这些长链链路，更新路由算法，在建链过程中防止长链产生。
1.2 改进协议
针对以上提出的问题，已经有学者提出了一种设立一个距离门限，每两个节点之间的距离与门限值比较，根据节点间距离与门限的比较来确定把新节点加入链，还是继续寻找其他节点[1]；参考文献[2-3]提出一种分层树成链的方法节能，但也没有充分考虑长链问题；参考文献[4]采用分区来避免长链，但没有考虑部分簇头轮换。
本文提出一种记忆式的M-PEGASIS路由算法，其成链流程图如图3所示。该算法还是遵循PEGASIS协议算法，但是增加一个记忆比较模块，即由距离基站最远的节点N开始寻找入链，此时初始化记忆节点Mem为空（认为任何节点和空节点的距离无穷大），找出距离N最近的节点N+1，随后计算N+1与N以及记忆节点Mem的距离D和Dm，然后对两个距离进行比较，如果D<Dm，则说明N+1与N的距离比N+1与记忆节点近，N+1与N连接，最后将N节点赋值给Mem节点，N+1节点赋值给N节点；反之则N+1节点与记忆节点连接，N+1赋值给N，Mem节点不变, 继续进入循环寻找下一个入链节点。
用此新方法分析图2中节点11到节点12的长链，此时记忆节点Mem为节点10，当前节点N为节点11，节点11寻找离它最近的未入链节点，找到节点12，并且算出到节点12的距离，然后再计算出节点12与记忆节点10之间的距离，发现到记忆节点10之间的距离明显小于到当前节点11的距离，因此，节点12与记忆节点10连接，此时节点12为当前节点N，记忆节点依旧是10。图4为无线传感器网络中，运用PEGASIS协议与运用M-PEGASIS协议的对比图。很明显，运用M-PEGASIS方法有效避免了长链的产生，为无线传感器网络的数据传输节省了能量。
取比值大的节点作为该轮通信的簇头节点，考虑到簇头节点与基站通信的耗能比普通节点多，故需要进行簇头的轮换，簇头轮换选择机制也按照Q值的大小，簇头节点每隔20轮通信检测一次该Q值。当该Q值降低到通信前Q值的50%时，该链启动簇头重选机制，重新根据Q值的大小排序选出新的簇头节点。如此算法不但避免了某些节点耗能过多而过早死亡，造成网络分裂，影响通信，还大大地增加了无线传感器网络寿命，均衡了各节点能量消耗。
2 量能分析
在此量能分析中，假定基站位于众节点的正上方，且各个节点的初始能量相同，遵循能量消耗与距离成正相关的关系，为了节省簇头节点的能耗，延长簇头节点的生命，将簇头节点设定为距离基站最近的节点。在此模型中，假设链中共有c个节点，每一个节点传输的数据长度都是L bit，则除簇头节点以外，本地通信中每个节点都进行了一次数据传输，不考虑节点内部数据融合等其他时延，得到能耗公式推导如下：
链内本地能耗由下面两部分组成：
3 仿真分析
为了证实M-PEGASIS算法相比普通PEGASIS算法有更高的节能效果，对其进行相应的仿真。在长宽各为50 m的正方形区域内，随机生成了100个节点，将基站的位置定在坐标点(25，200)处，数据包长度为1 000 bit，采用参考文献[6]中的能量映射模型，并且假设开始每个节点都具有相同的能量，用通信的轮数来表示节点的寿命。PEGASIS算法与M-PEGASIS算法的节点存活对比仿真结果如图5、图6、图7所示。
根据仿真结果可知，PEGASIS算法中，1%、20%、50%、100%节点死亡时间在700轮、1 100轮、1 200轮和1 380轮附近，此结果与参考文献[7]中得出的结论相符。改进算法M-PEGASIS中，1%、20%、50%和100%节点死亡时间推迟到了1 600轮、1 680轮、1 800轮和1 890轮，这是由于当簇头Q值降低到通信前一半时引入簇头轮换机制，所以出现第一个死亡节点的时间大大推迟了，但是当死亡节点开始出现以后，此时各节点的能量普遍已经很低，故节点死亡速度很快。即使这样，在没有增加算法复杂度的情况下，也使时间上有了40%～50%左右的提升。
本文分析了经典的链式PEGASIS算法，虽然此算法相对于LEACH算法能耗方面有了很大的降低，但是还存在着很大的不足：(1)在节点比较多的情况下很容易产生长链，从而增加节点间传输的距离，增加了部分节点的能耗，导致这些节点过早的死亡，影响网络效率；(2)链的簇头选择方式为随机选择，具有很大的不确定性，并且导致节点间能耗不均匀。分析了以上两个缺点，本文提出了一种记忆式的改进路由算法，避免了成链过程中长链的产生，进而节约并均衡能耗。又对簇头选择的方式从节约能耗的角度加入了一定的选择方法，进一步平衡了节点能耗，延长了网络寿命。
然而，基于此路由算法的无线传感器网络虽然能有效节约能量消耗，但也存在一定问题，当在一个无线传感器节点数目很大的传感器集群中，运用此方法收集传递数据，往往会造成比较大的时延，形成一条带分支的链也是一项很大的工作，并且随着部分节点的死亡，Q值的降低，导致链的频繁重构，也是对网络的一种巨大的消耗，更影响了网络的健壮性，因此接下来还可以在成链方面有新的改进，例如对每条链的节点数目限定一个上限值，从而在数目巨大的传感器网络中形成多条子链，然后再将每个子链的簇头按照同样的路由算法形成一个父链，进一步适应大型无线传感器网络集群。
参考文献
[1] 余永昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法[J].电子学报，2008，36(7)：1309-1315.
[2] 王波，蒋卫，孙燚.改进PEGASIS的分层链树路由协议[J].计算机系统应用，2009(12)：98-102.
[3] 吴联芳，张昱，金心宇.基于模拟退火算法的无线传感网PEGASIS算法[J].江南大学学报，2008，7(4)：438-442.
[4] 陈慧娜，唐明浩.基于PEGASIS的改进型WSN路由协议[J].计算机工程，2010，36(19)：134-136.
[5] Cui Shuguag，GOLDSMITH A J，BAHAI A.Energy constrained modulation optimization for coded systems[C].Proc.of IEEE GLOBECOM’03.2003.
[6] HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application specific protocol for wireless mirco-sensor networks[J].IEEE Tram Wireless Communications，2002，1(4)：660-670
[7] LINDSEY S，CAULIGI S.Raghavendra PEGASIS：powerefficient gathering in sensor information systems[C].Conference Proceedings，2002.