摘 要： 针对传感器网络存在的节点能耗过快问题，提出了一种新的分簇路由协议EEGC。该协议底层拓扑采用分簇及簇内部分覆盖算法，有效地降低了网络能耗。上层拓扑采用近簇头单跳通信、远簇头多跳通信的方式，缓解了内环簇头能耗过快的问题。同时，以簇头剩余能量决定簇及簇间路由的重构，进一步提高了控制消息的效率。仿真验证表明，EEGC协议的网络寿命明显优于LEACH。
关键词： 无线传感器网络；能量控制；分簇算法；覆盖算法；能量洞
节能问题一直是无线传感器网络WSN(Wireless Sensor Network)的研究热点，其中基于分簇的路由协议引起了较多的关注[1-2]。分簇协议一般采用多跳通信，但是研究发现，多跳通信会导致离Sink越近的传感器节点的能量消耗越快[3]，这种现象导致在Sink周围形成“能量洞”。参考文献[4]首次提出能量洞问题在节点随机均匀分布的环境中是不可避免的。同时，从延长网络生命周期和网络覆盖率的角度考虑，参考文献[5]重点讨论了部分覆盖算法，指出恰当的部分覆盖可以减少冗余节点，更节省网络能量。
针对上述问题，本文提出了一种新的分簇算法EEGC，该算法主要针对节点同构、节点随机均匀分布的网络环境。EEGC采用基于最小跳数的簇头竞争方法、内环簇头直接通信以及外环簇头多跳通信的方式，缓解了网络Sink节点周围能量洞的问题。同时调用部分覆盖算法，避免了大量冗余节点的能耗，实现了一个高效的节能通信网络。
1 系统模型和问题分析
1.1 系统模型
本文假设n个传感器节点随机均匀地分布在监测区域Aarea内，节点具有相同的初始能量和能耗模型。基站部署在区域外，由位于监测区域内的Sink节点将收集的信息传送到基站。所有节点不具有定位功能，节点的无线发射功率可控，可以根据距离来调整发射功率的大小。无线传感器网络的能耗主要来自于通信，所有节点发送、接收和融合数据消息的能量消耗模型见参考文献[1]。
1.2 簇内部分覆盖算法
定义1 服务质量q(the Desired QoS)定义为所有工作节点构成的有效监测区域面积占整个监测区域Aarea(L×L)面积的比例，即：
如果某个节点在时刻t之前收到其他节点的簇头广播Head消息，则节点不再广播Head消息，直接发送Join_head消息加入该簇。若节点同时收到两个簇头广播Head消息，则加入能量较大的那个簇。如果在T时刻后，节点还未收到簇头声明Head，则自己广播簇头声明Head，宣布成为簇头。
2.3 数据传输
根据簇内覆盖算法，簇头计算出簇内工作节点数kact=K/kexp，簇头选择能量较大的kact-1个成员节点，创建一个TDMA时隙调度，并把该TDMA调度广播给这kact-1个节点。这kact-1个节点在所分配的时隙将监测数据发送到簇头，簇内其他节点进入休眠模式。
若簇内工作节点i能量耗尽，则簇头关闭该工作节点，并调用能量较大的休眠节点j工作，安排节点j在节点i的时隙发送信息。若簇头节点的能量小于ECHmin，则重新竞选簇头，每个非死亡节点在半径Rc内广播自身能量和梯度值，然后重复2.2和2.3的步骤。簇头节点能量阈值ECHmin为接收、融合簇内工作节点的数据消息，以及发送数据消息损耗的能量，ECHmin=(k-1)lEelec+klEDA+(lEelec+lεfsd2up)。对于每个簇，重复进行多次簇内和簇间数据传输，直到簇头的剩余能量不足以维持一次数据传输过程时，才重新竞选簇头，这样可以有效地提高每次分簇的效率。
簇间数据传输阶段，每个簇头在3Rc半径内广播Child消息。内环所有簇头i(Gi≤3)直接发送数据消息给Sink节点。外环簇头i(Gi>3)存储接收到的Child消息，同时选择Ej/Gj比值较大的低梯度簇头j作为父节点，进行数据多跳传输。如果一条路径失败，则选择3Rc范围内的其他簇头节点作为父节点，进行簇间信息传递。只有当网络内所有节点重新进行簇的构建过程，网络才会重新广播Child消息构建簇间路由，否则，所有簇头节点依照储存的路由表传递数据。这种内环簇头直接通信、外环簇头多跳通信的方式，能够减少内环簇头的负载，缓解内环节点能耗过快的问题。
3 实验验证与仿真
为了说明算法效果，使用MATLAB对算法进行了仿真测试，仿真区域100 m×100 m，仿真场景参数如表2所示。
3.2 协议性能
图3、图4分别比较了EEGC协议在n=100、q=0.99/0.90以及n=400、q=0.99/0.90场景下，网络寿命与每轮工作节点数目的关系。由图可见，在q=0.99条件下，网络要求更多工作节点来换取较小的QoS优势。
图5比较了EEGC协议和LEACH在n=100条件下的实际网络服务质量。图6比较了EEGC协议与LEACH在n=400条件下的实际网络服务质量。
图5和图6均可表明EEGC协议在保证高服务质量的同时，网络寿命更长。同时，比较EEGC协议在q=0.99、n=400与q=0.99、n=100两种情况的曲线图可知，EEGC协议在高密度环境下的网络能耗更加均衡，网络服务质量更高，也验证了EEGC协议主要是针对高密度的随机分布网络环境。
EEGC协议采用了部分覆盖算法调度活动节点，有效减少了冗余节点。同时，簇和簇间路由的重构都由簇头剩余能量值决定，在高能量、高密度的网络中，这样可以降低反复重新构建簇及路由的能量损耗；但是在低能量、节点稀疏的网络，这种网络重构机制在节能方面并无优势。同时，本协议的空分路由策略——内环直接通信、外环多跳通信，还有待改进。下一步需要研究更合理的拓扑机制，进一步节省系统能耗，延长网络寿命。
参考文献
[1] HEINZELMAN W， CHANDRAKSAN A， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications， 2002，1(4)：660-670.
[2] 沈波，张世永，孙亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17(7)：1588-1600.
[3] 宋超，刘明，龚海刚，等.基于蚁群优化解决传感器网络中的能量洞问题[J].软件学报，2009，20(10)：2729-2743.
[4] OLARIU S， STOJMENOVIC I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C].Proceedings of the IEEE INFOCOM’06. Barcelona， Spain： IEEE Press， 2006-04-06-25.
[5] Zou Yi， CHAKRABARTY K. A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J]. IEEE Transactions on Wireless Communications， 2005， 54(8)：978-991.
[6] 毛莺池，刘明，陈力军，等.DELIC：一种高效节能的与节点位置无关的传感器网络覆盖协议[J].计算机研究与发展，2006，43(2)：187-195.