摘 要： 提出一种基于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，则除簇头节点以外，本地通信中每个节点都进行了一次数据传输，不考虑节点内部数据融合等其他时延，得到能耗公式推导如下：
链内本地能耗由下面两部分组成：