WSN中一种高效节能的分簇路由协议＊

程焱芳，吴玉成

(重庆大学 通信工程学院，重庆 400044)

节能问题一直是无线传感器网络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)面积的比例，即：

其中，Si表示工作节点ni的感知范围，K表示工作节点的数量。 区域 Aarea中任意一点 Pi(x，y)∈Aarea，Pi(x，y)没有被K个工作节点覆盖的概率为：

因此，在区域 Aarea中，任意一点 Pi(x，y)至少被其中一个工作节点覆盖的概率θ为：

根据服务质量q的定义，可知在区域Aarea中K个工作节点达到的服务质量为：

其中，Rs为感知半径。由式(4)可知，随机部署网络在区域大小和感知半径已知的情况下，满足服务质量q要求最少需要选取K个工作节点：

1.3 最佳簇半径

在EEGC协议中，梯度建立阶段网络耗能固定，簇的构造和簇间路由选择两部分的耗能与簇的“死亡”相关。综上考虑，本协议中实现网络节能的关键是使所有节点在数据传输阶段每次传送消息耗能最低。

因此，成员节点每传输L比特感知数据耗能为：

簇头节点的能耗主要包括两部分：接收、融合成员节点和孩子的数据消息，以及向父节点传送数据。因此，簇头节点每传输L比特数据消息的耗能为：

其中，Nchild=1是指每个簇头节点的孩子节点数，kact=K/kexp表示每个簇的工作节点数。

为保证网络全连通，采用簇间广播半径dup=3Rc。因此整个网络每传送L比特数据信息消耗的能量为：

对簇半径Rc求导，得：

将式(5)代入式(10)，并令求导结果等于 0，可得最优簇半径为：

2 EEGC协议

系统初始化，所有传感器节点都有唯一ID号，依次为 1、2、3……n，梯度初始值为无穷大。Sink节点 ID号为0，梯度为0。表1列出了所有广播消息以及其相应的描述信息。

表1 状态和消息描述

2.1 梯度的建立

梯度生成阶段，所有节点接收半径Rc内的梯度广播消息，确定自身的梯度值，并记录相邻节点的梯度值、能量状态和ID号。

(1)首先，Sink节点以半径 Rc广播Hello消息。其他节点 i(1≤i≤n)收到广播信息后，按照步骤(2)进行操作。

(2)高梯度节点接收半径Rc内其他节点的Hello消息，根据广播节点的梯度值大小修改自身的梯度。例如，节点i收到节点j发送的Hello消息，保存节点 j的消息信息。如果节点i的梯度大于节点j的梯度，则节点i修改自身梯度Gi=Gj+1，并以半径 Rc广播 Hello消息；否则，不修改自身梯度值。所有节点重复进行步骤(2)，直到时间tg结束。

(3)tg时刻之后，节点将存在获得梯度和未获得梯度两种状态。对于未获得梯度的任意节点i(1≤i≤n)，需要增大自己的发射半径发送Hello消息，以使距离最近的低梯度节点j接收到该信息。然后节点i根据节点j的响应消息修改自身梯度Gi=Gj+1，并根据接收信号的强度，调整发射功率，缩小冲突范围。最后，节点i向邻域内其他节点广播自己的新梯度信息，网络内所有节点的梯度建立完成。

2.2 簇的形成

在簇头选择阶段，每个节点根据存储的邻域节点能量值和梯度值，利用式(12)计算t值，并在时刻 t以半径Rc广播Head消息竞争簇头。

如果某个节点在时刻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.1 生命周期

图1比较了LEACH和EEGC协议在不同的节点分布密度下的网络寿命期望值。由图1可见，针对不同的节点分布密度，EEGC协议的网络寿命均优于LEACH。在LEACH协议中，随着节点分布密度的加大，网络内冗余节点越来越多，网络寿命随着节点分布密度的加大而逐渐降低。而由于EEGC协议采用了部分覆盖算法，有效调动活动节点，在服务质量q=0.90和q=0.99两种情况下，网络寿命随着节点分布密度的加大而延长。由图1可以明显看出，EEGC在延长网络寿命方面比LEACH协议优秀。

图2比较了EEGC协议在不同的服务质量QoS下的网络寿命，选取的仿真节点数目n=100。由图2可见，网络寿命随QoS的提高而降低，这是由于系统内单位时间内要求保持工作状态的节点减少了，单位时间内的耗能地减少了。

表2 仿真参数

图1 网络寿命随节点数目变化曲线

图2 网络寿命随服务质量变化曲线

3.2 协议性能

图3、图4分别比较了 EEGC协议在 n=100、q=0.99/0.90以及 n=400、q=0.99/0.90场景下，网络寿命与每轮工作节点数目的关系。由图可见，在q=0.99条件下，网络要求更多工作节点来换取较小的QoS优势。

图3 网络寿命VS.工作节点数目(n=100)

图4 网络寿命VS.工作节点数目(n=400)

图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协议主要是针对高密度的随机分布网络环境。

图5 网络寿命VS.实际服务质量(n=100)

EEGC协议采用了部分覆盖算法调度活动节点，有效减少了冗余节点。同时，簇和簇间路由的重构都由簇头剩余能量值决定，在高能量、高密度的网络中，这样可以降低反复重新构建簇及路由的能量损耗；但是在低能量、节点稀疏的网络，这种网络重构机制在节能方面并无优势。同时，本协议的空分路由策略——内环直接通信、外环多跳通信，还有待改进。下一步需要研究更合理的拓扑机制，进一步节省系统能耗，延长网络寿命。

图6 网络寿命VS.实际服务质量(n=400)

[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.