能量高效的无线传感器网络稳定分簇路由协议

田 勇， 唐 祯 安

（1.大连理工大学 电子科学与技术学院，辽宁 大连 116024；2.大连东软信息学院 嵌入式系统工程系，辽宁 大连 116024）

0 引 言

分簇路由协议是目前无线传感器网络（wireless sensor network，WSN）研究的热点之一，这类协议首先根据某种规则把WSN节点集划分为多个子集，每个子集成为一个簇，具有一个簇头[1].分簇路由协议中如何选取簇头是最关键问题之一，根据簇头选取方式的不同，可以把分簇路由协议分为分布式和集中式两种[2].分布式路由协议包括两类：一类是节点根据某个阈值决定是 否 当 选 为 簇 头，如 LEACH （low－energy adaptive clustering hierarchy）协议[3]就是这类分布式协议，它是由节点根据随机数自主决定是否当选为簇头，每轮产生的簇头没有确定的数量和位置；另一类是通过节点之间的信息交互产生簇头，如 HEED（hybrid energy－efficient distributed clustering）协议[4]和 HEED－M 协议[5].HEED协议将节点最大剩余能量和平均最小可达能量作为选择簇头的参数，以便簇内通信代价达到最小，但是此协议为了达到簇内通信代价最小的目的可能多次进行消息迭代，使得通信开销显著增加.HEED－M协议与HEED协议的唯一区别就是HEED协议使用单跳通信的方式，而HEED－M协议使用多跳通信的方式.集中式路由协议是指由基站基于整个网络信息进行簇拓扑结构的划分，被建模为带有特定限制的图形划分问题，现已证明是NP问题[6].文献[7]提出了一种集中式路由协议LEACH－C（LEACH－centralized）.这类协议的主要缺点是每个节点必须向基站传送地理位置和剩余能量信息，增加了额外的能量开销.

近年来，随着 WSN路由协议研究的不断深入，又出现了大量的分簇协议.文献[8]提出了一种按照网络生命周期最大化原则计算最优传感器节点部署圆环数的方法，并且设计了EBDG（energy－balanced data gathering）协 议.Kaur等[9]考虑传感器节点的覆盖范围是一个任意形状的区域，设计了一种带有多种尺寸的固定形状区域的网络.文献[10]研究了线性数据采集传感器网络的均衡能量消耗问题.文献[11]提出了一种新的非均匀分簇路由协议EEUC，该协议利用非均匀的成簇半径，使得靠近基站的簇成员节点数目相对减少.文献[12]提出了EBCA协议，将簇内剩余能量最多的节点作为下一轮簇头节点.

本文针对WSN能量受限和能量消耗不均衡问题，提出一种能量高效的稳定分簇（EESC）路由协议.该协议由当前簇头选择剩余能量最大的成员节点为下一轮簇头，下一轮簇头上任后，非簇头节点根据能量距离函数决定加入哪个簇，簇间采用单跳或多跳的通信方式发送数据，以降低能量的消耗.

1 网络模型

本文研究的WSN由N个随机分布在正方形区域内的传感器节点组成，这些节点周期性地收集周围环境的数据，并按照本文给出的路由协议传输至基站.同时假设网络性质如下：

（1）基站位于分布区域外侧，并且它和传感器节点在部署后位置不再发生变化.

（2）传感器节点都是具有唯一标识的同构节点，并且能够进行数据融合.

（3）传感器节点可以根据接收节点的距离，调整发射功率.

（4）传感器节点能够根据接收到的信号强度来计算它到发送节点的近似距离[11].

本文采用的能量消耗模型由发射电路消耗的能量和功率放大电路消耗的能量两部分组成.功率放大电路的能耗根据发射节点和接收节点之间的距离d有所不同，当d小于阈值d0时，采用自由空间模型；大于等于阈值d0时，采用多径衰落模型.因此，距离为d的两个节点，发射长度为l的数据所消耗的能量为

式中：Eelec表示发射电路的能耗；εfsd2和εmpd4分别为功率放大电路在两种模型中的能耗.接收这些数据所消耗的能量为

另外，用Eda表示融合单位比特数据所消耗的能量.

2 EESC路由协议

EESC路由协议的基本操作过程是：在网络部署完成后，基站用给定的功率向网络广播一个信号，每个传感器节点接收到该信号后，根据信号强度计算出到基站的近似距离.在WSN开始工作之前需要先产生第一轮的簇头，由于第一轮传感器节点的能量都是一样的，直接采用LEACH产生簇头的方法来产生簇头.每个节点选择一个介于0和1的随机数，如果这个数小于阈值p，该节点成为簇头.在第一轮的簇头产生后，协议进入循环阶段：

（1）簇头向全网广播其成为簇头的消息，非簇头节点在收到簇头广播的消息后，根据能量距离函数确定其属于的簇，并通知相应的簇头；

（2）簇头根据簇成员节点发来的信息，选择其中剩余能量最大的节点为下一轮簇头的接班人；

（3）簇成员节点按照TDMA（时分复用）时隙发送数据给簇头，簇头对接收的信息进行数据融合之后，将自己此时的信息广播给所有簇头，然后根据簇头最小能量耗费判定依据来选择通信代价最小的方式将数据融合结果发送给基站；

（4）基站通知下一轮簇头的接班人成为簇头的消息，网络进入下一轮循环.

2.1 簇的形成

每个簇头在新一轮循环开始时，向全网广播簇头消息HEAD＿MSG，消息的内容为节点的标识（ID）和当前剩余能量（RE）.非簇头节点接收到此消息后，将根据能量距离函数决定加入哪个簇头.首先非簇头节点sj计算它到发送HEAD＿MSG消息的簇头（CHi）的距离d（sj，CHi），然后计算能量距离函数f（i，j）为[13]

其中i为簇头的ID，j为非簇头节点的ID，REi为簇头的剩余能量.节点sj加入簇头CHi的条件就是使能量距离函数f（i，j）最小.

根据能量距离函数的公式可知，非簇头节点向簇头发送信息消耗的能量取决于两者的距离d（sj，CHi），此距离越小能量距离函数f（i，j）越小，非簇头节点向簇头发送消息所消耗的能量就越小；簇头的剩余能量越多，能量距离函数f（i，j）越小，就越有利于平衡全网的能量消耗.

当非簇头节点sj决定加入簇头CHi之后，向簇头CHi发送JOIN＿MSG消息，消息的内容为节点的ID，以及本轮循环结束后该节点的剩余能量REj，计算如下：

其中REj－cur为节点sj当前的剩余能量，Ej－sm为向簇头CHi发送JOIN＿MSG消息所消耗的能量，Ej－td为向簇头CHi传输数据所消耗的能量.簇头CHi记录成员节点的ID及其REj信息，然后簇头给每个簇成员节点分配TDMA时隙.

2.2 下一轮簇头的产生

在簇的形成阶段，簇头CHi记录了其所有成员节点的剩余能量REj信息.为了平衡全网的能量，簇头必须由能量较高的节点来担任，所以簇头可以从成员节点中选择剩余能量REj最大的节点担任下一轮簇头的接班人.

2.3 簇间单跳和多跳混合路由协议

在所有节点得到其TDMA时隙后，它们按照所分配的TDMA时隙把收集的数据传送给簇头.簇头先对簇成员节点发来的数据以及下一轮的簇头信息进行融合处理，然后将数据以单跳或多跳的通信方式传输至基站.

首先采用文献[11]的思想，引入一个阈值TD＿MAX.若簇头到基站的距离小于TD＿MAX，则它直接将数据传送给基站；否则使用多跳路由的方式与基站进行通信.在选择单跳或者多跳传输之前，每个簇头向全网广播NODE＿MSG消息，内容包括其节点标识、它当前的剩余能量和它到基站的距离.下面介绍使用多跳路由方式时，簇头选择中继节点的策略.

本文选择比簇头CHi更接近基站的区域中的簇头作为路由候选节点，并且建立相应的集合，簇头CHi的路由候选节点集合定义如下：

其中CHk表示路由候选节点，d（CHk，BS）表示路由候选节点CHk和基站BS之间的距离，d（CHi，BS）表示簇头CHi和基站BS之间的距离.簇头CHi将从此集合中选择一个节点CHk作为数据转发中继节点，选择的策略分析如下：假设CHk将数据直接传输至基站，则为了传输长度为l的数据至基站，CHi和CHk消耗的总能量为

簇头CHi直接与基站通信消耗的能量为

如果簇头CHi的路由候选节点集合RCCHi中仅存在一个候选节点CHk，使得E2hop小于E1hop，则簇头CHi将选择CHk作为其中继节点；如果存在多个候选节点使得E2hop小于E1hop，则簇头CHi将选择剩余能量最大的候选节点作为其中继节点；否则簇头CHi将直接与基站进行通信.

3 EESC路由协议分析

EESC路由协议利用集中式路由协议的思想解决了分布式路由协议簇头数目不确定和簇头剩余能量难以判断的问题；同时又利用分布式路由协议的思想克服了集中式路由协议必须在基站和节点之间传输信息而耗费额外能量的缺点.下面给出了整个协议的伪码：

在此协议中，簇头向全网广播HEAD＿MSG消息和NODE＿MSG消息时，广播半径设为此簇头到网络覆盖范围的4个顶点的最大值；而发送JOIN＿MSG消息时，发送半径为实际到目标节点的距离.该协议是消息驱动的，因此需要分析消息复杂度.

性质1 在所选网络中，EESC路由协议的消息复杂度为O（N）.

证明 每一轮开始时，有N×p个簇头共广播N×p条HEAD＿MSG消息；而N×（1－p）个非簇头节点共广播N×（1－p）条JOIN＿MSG消息；簇头向全网广播剩余能量等信息的NODE＿MSG消息共N×p条.因此总的消息开销为

即消息复杂度为O（N）.

性质1说明EESC路由协议的消息复杂度较小，能量效率较高.文献[11]提出的EEUC协议和文献[14]提出的DEEUC协议的消息复杂度也为O（N），并且都低于HEED协议的消息开销.与文献[11，14]协议相比，EESC协议的消息开销更低，因此能量效率更高.

4 实验结果及分析

为了验证协议的有效性，利用MATLAB对协议进行了仿真测试，实验所用参数如表1所示.

表1 实验参数Tab.1 Simulation parameters

4.1 参数p的选择

协议中决定簇头数目的参数p的选择是非常重要的，本文用实验方法来确定p的取值.令p从0.01到0.1，观察网络中第一个死亡节点和最后一个死亡节点的轮次（R）随之变化的情况.每个p值实验10次取平均值，实验结果如图1所示.由图可见p＝0.04时，网络的第一个死亡节点的轮次最大，当p＝0.02时，网路的最后一个死亡节点的轮次最大；而当p＝0.04时，从第一个死亡节点到最后一个死亡节点的轮次差值最小，这个轮次差值可以反映网络节点能量消耗的均衡情况，差值越小说明网络的能量消耗越均衡.因此本文取p＝0.04，使得网络的存活时间更长，能量消耗均衡程度更好.

图1 第一个死亡节点和最后一个死亡节点死亡轮次随参数p的变化Fig.1 The round changes of the first dead node and the final dead node in networks with the parameter p

4.2 簇头的能量消耗

为了验证本文提出的EESC路由协议能量的高效性和均衡性，将EESC与LEACH、HEED和HEED－M三种分簇路由协议进行比较.由于分簇路由协议中簇头承担了接收成员数据、融合数据和将数据发送给基站等多项任务，是WSN中能量消耗的主要部分.图2显示了随机选取10轮，4种协议的簇头在一轮里消耗能量之和（Et）的比较结果.从图中可以看出，EESC路由协议的簇头消耗的能量之和最低而且波动最小，这是因为EESC协议簇头的消息开销较小，并且簇头采用单跳或多跳的通信方式发送数据至基站，显著降低了能量的消耗；波动最小是由于EESC路由协议的簇头数量在没有节点死亡之前固定不变，簇头消耗的能量之和没有明显的波动.LEACH协议的簇头消耗能量最高，波动最大，是因为它采用单跳通信方式，而且构造的簇头数量较多，导致簇头消耗的能量增大；另外LEACH构造簇头的数量不够稳定，导致簇头消耗的能量之和也有较大差别.HEED和HEED－M协议簇头消耗的能量和波动性处于EESC和LEACH协议之间，而HEED－M协议簇头消耗的能量又低于HEED协议，原因在于HEED－M采用了多跳通信的方式，降低了能量消耗.

图2 4种协议的簇头消耗能量之和Fig.2 The sum of energy dissipated by cluster heads in four protocols

4.3 网络的生命周期

网络生命周期的长短是衡量WSN路由协议优劣的首要设计目标.图3显示了EESC、LEACH、HEED和HEED－M四种协议存活节点数目（Nlife）随轮次变化的情况.存活节点数目可以反映网络能量的使用效率，存活节点越多说明网络的能量使用效率越高.从图中可以看出，由于LEACH协议通过等概率地随机循环选择簇头，将整个网络的能量负载平均分配到每个传感器节点，使得第一个死亡节点出现在大约260轮，而最后一个死亡节点出现在大约600轮.但是，LEACH协议没有考虑节点的剩余能量，并且每轮产生的簇头没有确定的数量，使得网络的生命周期和能量消耗的均衡性并不理想.HEED协议在选择簇头时考虑了节点的剩余能量，并以主从关系引入了多个约束条件作用于簇头的选择过程，同时也考虑了分簇后簇内的通信开销问题，因此第一个死亡节点出现在大约330轮，而最后一个死亡节点出现在大约700轮.与LEACH协议相比，延长了网络生命周期.然而，无论是LEACH协议还是HEED协议，节点都是采用单跳的方式与基站进行通信.HEED－M协议在HEED协议的基础上，将节点与基站的通信方式由单跳改为了多跳，取得了较好的效果.与以上3种协议相比，本文提出的EESC路由协议不仅选择簇内能量最大的节点作为下一轮的簇头，而且在建簇时利用能量距离函数来优化簇内的通信开销，在传输数据时采用单跳和多跳相结合的方式与基站进行通信，因此在大约760轮时才出现第一个死亡节点，而此时其他3种协议的节点已经全部死亡，并且最后一个与第一个死亡节点的差值也远小于其他3种协议，这说明EESC路由协议不仅高效地利用了网络的能量，延长了网络的生命周期，而且网络的能量消耗更加均衡.

图3 4种协议的网络生命周期比较Fig.3 The network lifetime comparison of four protocols

5 结 语

本文提出了一种能量高效的WSN稳定分簇路由协议，该协议利用建簇过程传输节点剩余能量信息，簇头根据簇成员节点的剩余能量来选取下一轮的簇头.这样，不仅使每次产生的簇头能量最大，数目稳定，而且不需要在节点和基站之间传输剩余能量等信息，因此具有分布式和集中式分簇路由协议的共同优点.实验证明了EESC路由协议能量利用的高效性和能量消耗的均衡性.

[1] 李建中，高 宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）：1－15.LI Jian－zhong， GAO Hong. Survey on sensor network research[J].Journal of Computer Research and Development，2008，45（1）：1－15.（in Chinese）

[2] 沈 波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17（7）：1588－1600 SHEN Bo，ZHANG Shi－yong，ZHONG Yi－ping.Cluster－based routing protocols for wireless sensor networks[J].Journal of Software，2006，17（7）：1588－1600.（in Chinese）

[3] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless microsensor networks [C]// Proceedings of the Hawaii International Conference on System Sciences.Los Alamitos：IEEE，2000：1－10.

[4] Younis O，Fahmy S.HEED：a hybrid，energyefficient，distributed clustering approach for ad hoc sensor networks [J].IEEE Transactions on Mobile Computing，2004，3（4）：366－379.

[5] Younis O，Fahmy S.An experimental study of routing and data aggregation in sensor networks[C]//2nd IEEE International Conference on Mobile Ad－hoc and Sensor Systems，MASS 2005.Piscataway：Institute of Electrical and Electronics Engineers Computer Society，2005：50－57.

[6] Rhazi A E，Pierre S.A tabu search algorithm for cluster building in wireless sensor networks [J].IEEE Transactions on Mobile Computing，2009，8（4）：433－444.

[7] Heinzelman W，Chandrakasan A，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communication， 2002，1（4）：660－670.

[8] ZHANG Hai－bo，SHEN Hong.Balancing energy consumption to maximize network lifetime in datagathering sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2009，20（10）：1526－1539.

[9] Kaur T，Baek J.A strategic deployment and clusterheader selection for wireless sensor networks [J].IEEE Transactions on Consumer Electronics，2009，55（4）：1890－1897.

[10] ZHANG Hai－bo，SHEN Hong， TAN Ya－suo.Optimal energy balanced data gathering in wireless sensor networks [C] // Proceedings －21st International Parallel and Distributed Processing Symposium，IPDPS 2007.Piscataway：Institute of Electrical and Electronics Engineers Computer Society，2007.

[11] 李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报，2007，30（1）：27－36 LI Cheng－fa，CHEN Gui－hai，YE Mao，etal.An uneven cluster－based routing protocol for wireless sensor networks[J].Chinese Journal of Computers，2007，30（1）：27－36.（in Chinese）

[12] 杜玉红，张晓敏，蔡成闻.无线传感器网络能量均衡自适应分簇算法[J].传感技术学报，2007，20（7）：1616－1619.DU Yu－hong，ZHANG Xiao－min，CAI Cheng－wen.Energy－balanced adaptive clustering algorithm in wireless sensor networks [J].Chinese Journal of Sensors and Actuators，2007，20（7）：1616－1619.（in Chinese）

[13] 洪 利，杨淑玲.一种全局能量均衡的路由协议[J].计算机工程与应用，2010，46（2）：86－89.HONG Li， YANG Shu－ling. Overall energybalanced routing protocol[J].Computer Engineering and Applications，2010，46（2）：86－89.（in Chinese）

[14] 尚凤军，Abolhasan M，Wysocki T.无线传感器网络的分布式能量有效非均匀成簇算法[J].通信学报，2009，30（10）：34－43.SHANG Feng－jun，Abolhasan M， Wysocki T.Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J].Journal on Communications，2009，30（10）：34－43. （in Chinese）