一种能量感知的无线传感网拓扑控制算法*

陈 志 ，骆 平，岳文静，扈罗全，黄洵松，曹 壹，毛 博

(1．南京邮电大学计算机学院，南京210003;2．南京大学计算机软件新技术国家重点实验室，南京210093;3．江苏省无线传感网高技术研究重点实验室，南京210003;4．宽带无线通信与传感网技术教育部重点实验室，南京210003;5．苏州出入境检验检疫局，江苏苏州215104)

无线传感网是由部署在监测区域内大量的廉价微型传感器节点通过无线通信方式形成的一种多跳自组织网络[1]，具有广泛的应用。考虑到无线传感网节点能量有限等特点，设计能量高效的网络协议需要设计优化的拓扑控制机制，以提高网络运行效率，减少系统吞吐量。

无线传感网拓扑控制研究涉及邻近图方法、概率分析方法、优化理论方法、分簇算法等，其中分簇拓扑控制算法具有拓扑管理方便、能量利用高效、数据融合简单等优点。在分簇算法中，网络被划分为多个簇，每个簇通常由一个簇头和多个簇内成员组成，簇内信息经过簇头融合之后再转发至基站[2]。

不平衡能量分布的无线传感网模型是异构传感网基本模型[3]，无论是实验室环境还是实际应用环境条件下，考虑到技术缺陷或环境等因素，传感网节点能量在使用之前、使用过程中和使用后都不可能达到完全的平衡，因而不平衡能量分布传感网模型更贴近实际情况。

文献[4]提出了无线传感网拓扑控制典型的低功耗自适应算法LEACH，与平面拓扑算法相比，该协议可以延长网络生命期约30%，但是LEACH算法没有考虑能量不平衡问题。在LEACH的基础上出现了很多基于节点剩余能量的拓扑控制算法，文献[5]提出了一种基于剩余能量的自适应分簇算法，该算法选择剩余能量最大的节点作为簇头，文献[6]提出了基于节点能量阈值的簇头竞争算法，当簇头节点的剩余能量值降低到特定阈值下时，算法就启动新一轮簇的建立过程。

在无线传感网实际应用中，异构节点的正确使用可以比较好地平衡网络负载，延长无线传感网生命期。文献[7]提出了一种异构无线传感网分簇算法，该算法使用功能较强的特定节点作为簇头，并将一个簇分为内外两层，实现了快速分簇和多跳路由。文献[8]提出了一种能量有效的双簇头产生算法以减轻簇头负担并均衡网络能耗，该算法在每个簇中选出两个簇头分别承担簇内数据处理和簇外数据通信任务，较好地平衡了网络负载，但是网络大量节点的协调增加了信息交互的负担。文献[9]使用异构无线传感网对特定环境进行监测，提出了在考虑能量效率、覆盖范围和生命期等因素的情况下网络异构节点的最优比例，但没有处理好能量平衡的问题。

在目前所有提出的异构传感网分簇拓扑控制算法中，文献[10]提出的EADEEG算法是特别新颖和高效的，得到广泛的关注，EADEEG算法是一种基于能量感知的无线传感网数据收集协议，EADEEG算法基于邻居节点平均剩余能量与本节点剩余能量的比值，提出了一种独特的分簇方法，形成了比较优化的网络拓扑，延长了网络寿命，并且可以有效地应用于不平衡能量分布的网络场景。

1 问题描述

文献[11]提出了一种以邻居节点平均剩余能量与节点剩余能量的比值为参数、以节点的“度”作为另一个参数的分布式分簇算法BPEC。BPEC分簇算法在一定程度上解决了EADEEG算法存在的“孤点”问题，但BPEC算法还存在以下问题:

问题1 文献[11]所述BPEC算法引入了“度”的计算，“度”只对剩余能量大于平均剩余能量的“孤点”产生有限的影响，网络每一轮运行中的“孤点”仍然有可能成为簇头。如图1所示:节点2为“孤点”，若节点2成为簇头后会使簇与簇之间产生过多重叠区域，造成分簇不平衡，网络局部簇头数目偏多，从而降低网络效率，耗费能量。

图1 “孤点”问题

问题2 BPEC算法没有及时休眠能量过低的传感器节点，从而加快了能量过低节点的失效，不利于网络平衡。

问题3 BPEC算法在每一轮簇头选举之前，各个节点都要为获取实时的“度”和邻居节点平均剩余能量信息而在邻居节点之间进行大量的信息交互和数据计算，大量信息的发送和接收造成了能量损失。传感器节点在很短时间内所处环境、邻居节点关系不会有较大变化，节点的时间保持同步，簇头和普通节点信号发射半径固定，大部分节点只能在短时间内不变，这些因素决定了没有必要在每一轮开始时都进行能量信息交互，网络运行过程中可以充分利用经验数据，并在运行若干轮以后对经验数据进行修正，从而减少不必要的能量损耗。

基于上述方面的考虑，本文在对BPEC算法改进的基础上，提出一种新的面向不平衡能量分布的拓扑控制算法EADCA。

2 节点能耗模型

本文假定无线传感网节点均匀分布在目标区域内，无线传感网节点具有以下特征:①传感器节点具有全局唯一的标识符ID;②传感器节点被部署在目标区域后不具有移动能力;③传感器节点在部署时具有不同的能量分布，且能量不能被补充;④传感器节点不能获取地理位置信息，但能够根据接收信号强度计算发送节点到本节点的相对距离;⑤除上述特点外，传感器节点的其他参数配置相同。

无线传感网节点能耗主要涉及传感器模块、处理器模块、通信模块等。由于传感器模块和处理器模块的能耗比较低，本文只考虑通信模块的能耗，采用与文献[4]相同的一阶无线通信能耗模型。在该模型中，发送n bit信息且传送距离为d时的能耗公式及接收n bit信息的能耗公式如下:

3 能量感知分布式拓扑控制算法EADCA

面向不平衡能量分布的拓扑控制算法EADCA在BPEC算法的基础上对分簇过程进行改进，避免“孤点”问题，及时对能量过低的节点进行休眠。EADCA包括四个过程:信息交互、簇头竞争、节点归属和孤点休眠。在每一轮分簇开始时，各个节点获取自己的剩余能量，并与自己的邻居节点进行能量信息交互。各个节点根据交互的能量信息进行簇头竞争，产生适当数目的簇头节点。新当选的簇头向邻居节点广播消息，各个普通节点根据接收到的簇头广播消息，加入距离自己最近的簇头所在的簇。网络在运行过程中保持时间同步。图2为EADCA算法流程图。

图2 EADCA流程图

在EADCA中，网络节点维护以下数据信息:节点唯一标志符ID、节点剩余能量Er、邻居节点平均剩余能量Ea、上一轮邻居节点平均剩余能量oldEa、簇内节点tdma时隙、是否为簇头、该节点的簇头节点标识符、邻居节点列表、簇内成员列表、当前的轮数等。这些数据信息以特定的数据结构形式保存在节点内存中。节点之间的通信报文包括能量报文powerMsg、簇头声明报文 advMsg、入簇请求报文reqMsg、tdma时分报文等。

EADCA具体步骤如下:

步骤1 信息交互

(1)若网络是运行第1轮，则执行以下动作:

网络中各个节点以自己的发射半径R向邻居节点广播能量报文powerMsg。同时，各个节点接收邻居节点发送过来的powerMsg能量报文。各个节点根据接收到的powerMsg报文，计算出邻居节点平均剩余能量值Ea，并保存在各自的数据结构中。

(2)若网络运行第2轮，则执行以下动作:

网络中各个节点将上一轮计算所得的邻居节点平均剩余能量值Ea存入另一个数据结构:上一轮邻居节点平均剩余能量oldEa。各个节点以自己的发射半径R向邻居节点广播能量报文powerMsg。同时，各个节点接收邻居节点发送过来的能量报文powerMsg。各个节点根据接收到powerMsg报文，计算出邻居节点平均剩余能量值存入Ea，并保存在各自的数据结构中。

(3)若网络运行第3轮，则执行以下动作:

网络中各个节点将邻居节点平均剩余能量值Ea保存到临时存储器temp。各节点基于经验数据，即上一轮邻居节点平均剩余能量值oldEa和当前邻居节点平均剩余能量值Ea，使用式(3)来及时更新当前邻居节点平均剩余能量值Ea。各节点完成更新邻居节点平均剩余能量值Ea后，将临时存储器temp保存的值赋给上一轮邻居节点平均剩余能量值oldEa。

(4)若网络运行第4轮，则执行以下动作:

网络中各个节点使用已经存在于内存中的邻居节点平均剩余能量值Ea和上一轮邻居节点平均剩余能量值oldEa，基于经验数据，直接使用式(3)来及时更新邻居节点平均剩余能量值Ea。

整个网络在后面的运行过程中，在信息交互阶段重复上述步骤，以每4轮为一个单位，前两轮获取经验数据，后两轮在信息交互阶段不再发送和接收报文进行交互，而是直接使用经验数据。所有节点的信息交互过程持续时间为T1，第1轮的节点剩余能量值为节点的初始能量值。

步骤2 簇头竞争

各个节点在经历了持续T1时间的信息交互过程后，按照式(4)[10]～式(6)进行簇头竞争或休眠。簇头竞争持续时间为T2。

(1)当节点剩余能量大于邻居节点平均剩余能量值时，按照式(4)计算该节点可能成为簇头节点而发送簇头声明报文advMsg的时刻t1。所有剩余能量大于邻居节点平均剩余能量的节点在各自的t1时刻到达时，如果还没有收到任何邻居节点发出的簇头声明报文advMsg，则该节点向邻居节点广播簇头声明报文advMsg，声明自己当选为簇头;否则该节点立刻放弃簇头竞争而成为非簇头节点。

(2)当节点剩余能量小于邻居节点平均剩余能量值时，按照下列式(5)和式(6)分别计算时刻t2和时刻t3。当t2小于t3时，该节点在其时刻t2到达时，如果还没有收到任何邻居节点发出的簇头声明报文advMsg，则该节点向邻居节点广播簇头声明报文advMsg，声明自己当选为簇头;否则该节点立刻放弃簇头竞争而成为非簇头节点。当t2大于t3时，该节点进入一轮休眠。

在式(4)～式(6)中，ρ为0．9到1之间的随机数，T2为簇头竞争的持续时间，Er为节点剩余能量，Ea为邻居节点平均剩余能量;式(4)引用自文献[10];式(5)源于对文献[11]的改进，与文献[11]中有关公式形式相同，参数意义不同。由上述公式可以得到结论:t1＜(T2/2)[11]，(T2/2)＜t2＜T2，(T2/2)＜t3＜T2，该结论说明簇头竞争阶段持续了T2时间，在0到(T2/2)时间段里，在节点剩余能量Er大于邻居节点平均剩余能量Ea的节点中选出部分簇头节点;在(T2/2)到T2时间段里，选择剩余能量较大的节点作为簇头节点，并且使剩余能量不足邻居节点平均剩余能量一半的节点进入一轮休眠中。

步骤3 节点归属

当簇头竞争结束后，网络进入节点归属阶段，该阶段持续时间为T3。当普通节点接收到簇头节点发送过来的簇头声明报文advMsg，该节点根据接收的信号强度计算该节点到簇头节点的距离d。每一个普通节点可能接收到一个或多个簇头节点发送来的簇头声明报文advMsg，该节点选择距离自己最近的簇头节点作为自己的簇头，并向该簇头节点发送入簇请求报文reqMsg。网络中各个簇头节点在接收普通节点发送来的入簇请求报文reqMsg后，将该普通节点的ID加入自己的簇内成员列表，并将不属于该簇的其他节点ID删除，这样就完成了分簇过程。各个普通节点在成为特定簇的成员节点后，调整自己的信号发射半径为普通节点信号传输半径，以多跳方式与簇头进行通信。

步骤4 孤点休眠

在簇头竞争和节点归属的过程中，凡是成为簇头，却没有收到任何入簇请求报文reqMsg的网络节点立即放弃簇头身份，进入一轮休眠。凡是没有成为簇头，且没有收到任何簇头声明报文advMsg的网络节点，立即进入一轮休眠。

4 仿真分析

由文献[10]可知，整个无线传感网中实际簇头数量的期望值计算公式为:

其中，Kexp为簇头数量的期望值，‖A‖为网络覆盖区域的面积，r为簇半径。

下面以EADCA算法和BPEC算法为对象进行仿真和分析，仿真平台为 Castalia[12]。参照文献[11]，本文仿真采用高密度和低密度两种场景，具体仿真参数配置如表1。图3和图4给出的仿真结果是10次独立仿真结果的平均值。

表1 仿真参数

图3给出使用100个节点进行低密度节点布局的仿真实验结果。由该图可知，当簇半径较小时，EADCA算法产生的簇头节点数目小于BPEC算法产生的簇头节点数目，这是由于当簇半径较小时，簇头广播簇头声明报文advMsg的范围有限，导致网络中存在一定数目的“孤点”。EADCA算法休眠了这些“孤点”，而BPEC算法则使这部分“孤点”成为簇头;EADCA算法休眠部分低能量节点，减少了可能参与簇头竞争的节点数目。当簇半径较大时，EADCA算法产生的簇头节点数目小于并且接近BPEC算法产生的簇头节点数目，这是由于随着簇半径的增大，“孤点”对簇头竞争的作用减弱，同时EADCA算法休眠了部分能量较低的节点，使得EADCA算法中可能参与簇头竞争的节点数目在概率上低于BPEC算法。可见，EADCA算法可能产生的簇头数目比BPEC算法更贴近理论值。

图3 100个节点产生簇头数目的理论值与实际值比较

由图4可知，在使用500个节点的高密度场景下，仿真数据仍然接近理论值，说明在节点密度达到一定程度后，可能产生的簇头数目不会随着冗余节点的增加而增加。当簇半径较大时，EADCA算法产生的簇头数目非常接近甚至超出BPEC算法产生的簇头数目，这是由于在簇半径较大时，“孤点”的影响变小，EADCA算法虽然休眠了部分节点，但网络中仍然存在冗余节点，这些因素使得EADCA算法和BPEC算法产生的簇头数目非常相近;此外，EADCA算法及时休眠不必要工作的节点，使得网络能量更趋于平衡，随着BPEC网络节点一一失效，EADCA网络能够在较长时间继续保持较多的节点进行簇头竞争，从而实现EADCA算法产生簇头数目接近超出BPEC算法产生簇头数目的可能。

综上所述，EADCA算法延续了BPEC算法的分布式并行算法的特性，选择剩余能量比较突出的节点作为簇头，而不是简单地选择剩余能量最大的节点作为簇头，适合于大规模无线传感网应用。

图4 500个节点产生簇头数目的理论值与实际值比较

EADCA算法基于足够短时间内网络节点及其周边环境大致不变的情形，在簇头竞争过程中充分利用经验数据，使得EADCA算法在簇头竞争过程中的信息交互负荷为BPEC算法的一半，这在分簇无线传感网高速按轮运行过程中节省了能耗。EADCA算法对“孤点”进行了休眠处理，避免了BPEC算法中“孤点”成为簇头而造成网络局部簇结构重叠的情况，提高了网络的工作效率。

EADEEG算法使用式(4)来处理所有节点的簇头竞争;BPEC算法采用涉及“度”的公式来对节点剩余能量值Er大于邻居节点平均剩余能量值Ea的网络节点进行簇头竞争;而本文EADCA算法引用EADEEG算法中的式(4)，并在此基础上引入了“孤点”休眠处理来对节点剩余能量值Er大于邻居节点平均剩余能量值Ea的网络节点进行簇头选择，既省去了 BPEC算法对“度”的计算，也弥补了EADEEG算法的不足。可见，EADCA算法延续了EADEEG算法和BPEC算法簇头竞争的高效性，而在“孤点”处理上性能更优。

BPEC算法基于节点剩余能量和节点初始能量，使用一个类似于式(5)来处理节点剩余能量值Er小于邻居节点平均剩余能量值Ea的网络节点;而EADCA算法基于节点剩余能量和邻居节点平均剩余能量，使用了式(5)和式(6)来处理节点剩余能量值Er小于邻居节点平均剩余能量值Ea的网络节点。当式(5)的计算结果t2大于式(6)的计算结果t3时，说明节点剩余能量Er不足邻居节点平均剩余能量Ea的一半，则该节点进入一轮休眠;当t2小于t3时，说明节点剩余能量Er大于邻居节点平均剩余能量Ea的一半且小于Ea，则EADCA算法选择能量比较突出者作为簇头。可见，EADCA算法比BPEC算法对簇头的选择性更加精确，同时又对剩余能量过低的节点进行休眠，利于网络平衡。

5 结论

本文提出了一种基于节点剩余能量的分布式分簇拓扑控制算法EADCA，该算法注重使无线传感网能量趋向平衡，充分利用经验数据，减少不必要的网络交互，在一定程度上提高了能量利用率和网络生命期。该算法对“孤点”进行及时休眠，避免孤立节点成为簇头，有效控制了网络的簇头数量和分布密度。同时，EADCA算法充分考虑邻居节点平均剩余能量、实时节点剩余能量，比EADEEG算法和BPEC算法对节点休眠和簇头竞争的控制更精确，同时也更节省能量。本文通过仿真实验验证了EADCA算法产生的簇头数目优于BPEC算法产生的簇头数目，并更贴近网络所期望的理论值。

本文在网络运行中使用经验数据并及时对经验数据进行修正，但目前经验数据的使用并没有固定的模型，在无线传感网实际应用中，不同的情况下应采用不同的经验数据使用模型，否则可能会对网络产生负面的效果。

[1]史倢，陈志，章韵，等．一种基于元胞自动机的无线传感器网络拓扑控制方法[J]．传感技术学报，2011，24(12):1734－1738．

[2]A-l Karaki J N，Kamal A E．Routing Techniques in Wireless Sensor Network:A Survey[J]．IEEE Wireless Communications，2004，11(6):6－28．

[3]Mhatre V，Rosenberg C．Homogeneous vs Heterogeneous Clustered Sensor Networks:A Comparative Study[C]//Proceedings of IEEE International Conference on Communications，2004:3646－3651．

[4]Heinzellnan W B，Chandrakasan A P，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Transactions on Wireless Communications，2002，1(4):660－670．

[5]Garg A，Hanrnandlu M．An Energy-Aware Adaptive Clustering Protocol for Sensor Networks[C]//Proceedings of Fourth International Conference on Intelligent Sensing and Information Processing，2006:23－30．

[6]Rajiullah M，Shimamoto S．An Energy-Aware Periodical Data Gathering Protocol Using Deterministic Clustering in Wireless Sensor Networks(WSN)[C]//Proceedings of IEEE Wireless Communications and Networking Conference，2007:3016－3020．

[7]张雪凡．异构分簇的无线传感器网络拓扑控制[J]．应用科学学报，2011，29(1):39－43．

[8]徐小良，裘君娜．异构传感器网络中一种能量有效的簇头选择算法[J]．传感技术学报，2009，22(3):395－400．

[9]Machado R，Zhang W，Wang G．Network Planning for Heterogeneous Wireless Sensor Networks in Environmental Survivability[C]//Proceedings of 21st IEEE International Conference on Tools with Artificial Intelligence，2009:814－821．

[10]刘明，曹建农，陈贵海，等．EADEEG:能量感知的无线传感器网络数据收集协议[J]．软件学报，2007，18(5):1092－1109．

[11]周新莲，吴敏，徐建波．BPEC:无线传感器网络中一种能量感知的分布式分簇算法[J]．计算机研究与发展，2009，46(5):723－730．

[12]Boulis A．Castalia:Revealing Pitfalls in Designing Distributed Algorithms in WSN[C]//Proceedings of Proceedings of the 5th International Conference on Embedded Networked Sensor Systems，2007:407－408．