带有能量补给的异构无线传感器网络拓扑控制算法

马晨明 ，王万良 ，洪 榛 ，姚信威

（1.浙江工业大学信息工程学院 杭州 310023；2.浙江工业大学计算机科学与技术学院 杭州 310023；3.浙江理工大学机械与自动控制学院 杭州 310018）

1 引言

无线传感器网络作为物联网底层的重要组成部分，已经受到了国内外的广泛关注[1]。受到成本和体积的限制，传感器节点的能量一直是值得高度关注的问题。拓扑控制[2]是无线传感器网络中节约能量、增加运行时间的关键技术，可以均衡网络的能耗，最终达到延长网络生命时间的目的。拓扑控制主要由拓扑构建和拓扑维护[3]组成，拓扑构建用于优化网络的拓扑结构，减少节点之间的通信干扰；拓扑维护是恢复、轮换、再生成拓扑的过程，节点在拓扑构建后将启动拓扑维护以保障网络的有效运行。

LBCDS[4]是一种集中式的拓扑构建算法，由某个节点对全局网络拓扑信息进行搜集，然后再开始运行具体算法。算法首先计算网络的平均节点度，然后采用贪心的思想依次选择节点度最接近于平均节点度的节点作为活跃节点直到网络完全连通。但是，该算法需要较长的计算时间，同时也没有考虑节点的剩余能量的影响。

MIP-MCDS[5]和 NMIP-MCDS[6]采用令牌流对拓扑构建问题进行数学建模，以最小化网络分发的令牌作为目标函数，求解完毕后，各个持有令牌的节点组成最小连通支配集。但是，该类算法需要获得全网的拓扑结构信息，因此存在计算复杂度高、求解速度慢等问题。

EBCDS[7]是一种分布式拓扑构建算法，可以应用在节点比较密集的环境中。首先选择能量水平和节点度均较大的节点构造最大独立集，然后启动一个超时搜集三跳内的路径消息，超时结束后由ID较小的节点选择较优的路径连通。但是，EBCDS将三跳邻域中所有节点均进行了连通，导致产生的连通支配集规模较大，同时算法的消息复杂度也较高。

以上文献关注如何构建高效的网络拓扑，而参考文献[8]指出选择合适的拓扑维护策略将大大增加网络的生命时间。参考文献[9]提出的拓扑维护方法以最小能量为目标简化网络拓扑，当节点发现它的邻居节点出现故障后，它会重新运行拓扑构建算法以连通网络。参考文献[10]采用的是基于时间的拓扑维护策略，即定期触发拓扑维护以平衡节点的能耗。参考文献[11]对每个簇进行单独维护，当簇头的剩余能量低于簇内平均剩余能量时，需要选举新的簇头。算法要求保证新簇头和原簇头之间的距离小于k×d0/n，同时还需要簇头满足剩余能量大于簇内成员的平均能量。假设网络不存在这样的节点，原簇头会一直运行，直到能量耗尽。

以上算法针对拓扑构建或拓扑维护单独进行研究，而没有将两个过程很好地进行结合，同时以上算法均假设网络节点性能完全相同，没有考虑到可能存在不同计算、通信半径或能量水平的节点，这在实际研究中是缺乏应用价值的。参考文献[12]将拓扑构建和拓扑维护进行结合，同时考虑了节点通信半径异构的问题，算法在初始时采用了两轮消息交换的方式获得邻居节点信息，但是在通信开销上仍然可以进一步优化。随着节点能量采集技术的完善，节点已经可以将周围环境中的太阳光照、热力温差、机械振动、气流和压力变化等能源持续不断地转化为可用的电能[13]，这对延长网络的生命时间起到了重要的作用。

为了考虑节点能量采集技术对拓扑控制算法产生的影响，同时进一步降低当前算法的通信开销并优化网络的生命时间，本文在节点的通信半径和能量水平存在异构的无线传感器网络模型中，提出了一种同时包含拓扑构建和拓扑维护过程的异构无线传感器网络拓扑控制算法(HELM)。算法首先运行拓扑构建过程，以较小的通信开销生成连通支配集，然后利用邻域节点信息并结合时间、能量和故障的触发条件，提出了一种由sink节点执行决策的拓扑维护算法，进一步优化了A3M[12]算法在拓扑构建和拓扑维护过程中的能耗，并最大限度地延长网络的运行时间。

2 系统模型

2.1 网络模型

用图G(V,E)表示该网络模型，其中，V是节点集合，E是由V中节点组成的通信链路集合，假设：

·N个节点随机部署在M×M的区域中；

·sink节点位于中心（M/2，M/2），且计算、存储和能量均不受限制；

·为了能够更好地控制成本，网络由小部分高级节点和大部分普通节点组成，高级节点具有能量采集能力，而普通节点只含有有限的电池能量。节点通过ID进行唯一标识，不需要配备GPS获得位置信息；

·节点可以通过接收信息的信号强度RSSI获得邻居节点之间的距离d；

·假设所有节点的通信半径R∈[Rmin,Rmax]，则节点vi和vj之间存在通信链路 （当且仅当vi和vj相互处于对方的通信半径内）；

·初始网络拓扑为全连通图。

2.2 能量补给模型

目前，传感器节点的能量采集类型以太阳能和振动能为主，其中，太阳能的功率密度为10～15 mW/cm3，振动能功率密度约为0.275 mW/cm3。考虑到太阳能受到夜晚无光照的限制，本文研究内容以振动能为主，采用与参考文献[14]相同的振动能源能量补给模型，假设振动中心获得的振动能量最大，所有节点获得的能量与振动中心的距离成反比，这样不同位置由于机械振动强度不同，则所获得的能量补给大小也不同。

3 拓扑构建

在通信半径相同的网络中，当节点u收到邻居节点v的消息后，可以确定u、v处于同一通信半径内。当节点的通信半径存在异构时，参考文献[12]采用两轮消息交换的方式以获得邻居节点信息，但是这会增加通信开销。通过比较节点之间的距离与通信半径，只需要一次信息交换就能确定节点之间是否可以通信。假设节点u收到了v发送的hello消息，通过信号强度RSSI可以获得u、v之间的距离 d（u,v），然后和通信半径 Ru进行比较，如果 Ru≥d（u,v）就可以确定节点之间可以通信，这样就确定了网络中的邻居节点集合。

下面对算法的相关术语进行描述。

·节点的颜色：白色，初始状态；红色，中间状态；黑色，活跃节点；灰色，普通节点。

·N1:节点的邻居节点集合。

·Hop:节点距离sink节点的跳数。

·E、Emax:分别表示节点的当前剩余能量和最大初始能量。

·R、Rmax:分别表示节点的通信半径和网络中最大节点的通信半径。

·权值w1:支配节点不仅需要较高的剩余能量，还要考虑节点的能量采集能力，另外优先选择通信半径大、节点之间距离远的节点，这样可以减少支配集的规模，∑Eharvest(u)表示节点从上次成为活跃节点后到当前时间所采集的能量之和。

·competition(ID,E,Hop,First)消息:First表示最早收到的发送节点ID。

算法的主要思想是权值最大的节点会最先广播competition消息而成为活跃节点。初始时，sink广播competition消息而变成红色，然后等待时间T1确定自己能否成为活跃节点。节点v收到消息后，先确认是否邻居节点，如果发现自己的Hop属性还没有初始化或小于当前Hop+1，则进行更新，然后将邻居节点信息存储到N1。如果当前节点是白色，启动与w1成反比的定时器T2。时间T2内，节点收到满足连通性的消息时，则对N1进行更新。当T2结束，当前节点v设置First并广播一个competition消息。如果在时间T1内，上层的红色邻居节点u收到了该消息，发现First==IDu，则当前节点成为黑色节点，否则查看First对应的ID是否在N1中，如果存在，则将它的颜色标记为黑色。时间T1结束后，如果当前节点仍然没有收到First==IDu的消息，则当前节点变成灰色节点。

图1给出了HELM算法的一个运行实例。初始时，节点 S广播 competition消息，节点 A、B、C、D、E、F 处于 S的通信半径内，将能收到S的消息，B不是S的邻居节点，这是因为节点B的通信半径RB

4 拓扑维护

本节提出了一种面向时间、能量、故障触发机制的混合型拓扑维护算法。算法结合静态和动态拓扑维护的优点，根据当前网络状况选择局部或全局拓扑修复策略，以达到最小化网络能耗的目的。局部拓扑修复是在能量不足或失效的节点邻域内生成替代节点，可快速恢复网络，所需要的时延和能耗也较少；全局拓扑修复需要对全网进行重构，这样会消耗过多的能量而影响网络的生命。拓扑维护过程描述如下。

图1 拓扑构建算法的运行实例

在拓扑构建结束后，节点首先会对邻居节点计算权值w2，然后按照w2的大小进行排序，得到有关节点的ID、颜色和w2的列表FList。w2计算如式(2)，这里考虑节点之间的距离越近，那么邻居节点的权值w2就越高，因为两个节点如果位于同一位置，那么该节点自然也就可以覆盖当前节点所需要覆盖的节点，而此时由于已经搜集了邻域的节点能量，可以使用相对剩余能量来替代能量。

然后，各个节点会通过虚拟骨干向sink节点发送一个有关本地拓扑的local message，消息中包括节点的ID和FList。由于sink节点不受性能的约束，可以建立一个全局拓扑，利用该信息可以对失效或者能量不足的节点执行快速修复，下面对3种触发机制进行描述。

基于时间触发的机制是在sink节点中进行，sink节点记录每次发生全局拓扑修复的时间，然后每隔一定的时间执行该过程以平衡节点之间的能耗。

基于故障触发的机制是在当前的节点失效后的γ时间后触发，如果sink节点在一定的间隔中没有收到节点发送的数据，就会认为该节点失效了，然后开始执行拓扑维护策略。

基于能量触发机制是在节点的剩余能量小于阈值时，向sink节点发送reconstruction消息 (send,gateway,sink)请求网络重建，其中，send表示发送节点ID，gateway表示下一跳节点ID，sink表示基站ID。reconstruction消息沿着gateway向sink节点发送，如果当前节点ID不等于sink，节点继续选择合适的gateway进行转发。信息到达基站后，sink节点开始评估网络的状态以执行合适的拓扑维护策略，下面对具体的策略进行描述。

sink节点对当前网络进行评估，如果发现时间T内收到了多个节点的重建请求，则证明网络已经并非最优，需要立即重启全局拓扑修复，并对当前时间进行更新；如果请求数较少，sink节点会在全局拓扑中找到维护节点u，然后从u的FList中依次选择灰色且性能最优的节点加入列表ReplaceID，直到完全覆盖被替换节点u的FList中的所有灰色节点，如果局部拓扑修复不能得到连通的拓扑，那么sink节点会重启全局拓扑修复以保证网络的连通。

随 后 ，sink节点将decision message(flag,time,ReplaceID)沿着虚拟骨干对全网进行发送，其中，flag表示拓扑修复策略，time表示需要等待的时延，如果是局部修复策略，ReplaceID表示需要成为活跃节点的ID集合，否则该集合为空。活跃节点将收到的消息向普通节点进行转发，节点收到消息后检查是否需要成为活跃节点。

5 理论分析

定理1如果初始网络是连通的，那么通过拓扑构建后形成的支配集也是连通的。

证明算法形成的支配集由黑色节点组成。由于节点共存在4种颜色，初始时所有节点都是白色，节点一旦广播competition消息就会变成红色，然后根据是否收到满足First等于自己ID的消息来决定成为黑色或灰色节点，也就是说算法结束后只可能存在白色、黑色、灰色节点。假如还存在白色节点，那就说明该节点没有收到过其他节点广播的competition消息，这与定理假设初始网络是连通的相矛盾，得证。

定理2拓扑构建算法中每个节点至多只需要发送一次消息，而时间复杂度为O(n)。

证明当前节点收到上层节点发送的消息后，会在超时结束后广播一次消息，并根据收到消息的First属性决定变为黑色或灰色。此外，节点的操作不需要排序，均能在常数时间内完成，因此算法的时间复杂度为O(n)。

定理3拓扑维护算法至多只需要发送2n的消息，算法的时间复杂度为O(nlgn)。

证明节点需要对邻居节点计算权值w2并排序，这个过程需要O(ΔlgΔ)的时间，Δ为最大邻居节点数。消息沿着虚拟骨干向基站转发，最坏的情况下，消息被转发n次到达sink节点。基于时间机制的拓扑维护策略每隔时间T进行重构，不需要其他额外操作；基于能量和故障机制的拓扑维护策略，采用局部拓扑修复时，至多需要O(Δ)的时间来判断是否可以生成替代节点集ReplaceID，而采用全局拓扑维护时需要O(1)的时间决定。sink节点根据当前网络状况将执行的策略和时延封装在decision消息并沿着拓扑反向转发至多n次，因此拓扑维护发送的消息最多不会超过2n，而算法的时间复杂度在最坏情况下为O(n lg n)。

6 仿真实验及分析

6.1 实验环境及参数设置

仿真实验选择性能较好且同时包含拓扑构建和拓扑维护过程的异构无线传感器网络拓扑控制算法A3M作为比较对象，实验采用基于网络事件驱动的软件Atarraya[15]进行评估，仿真开始时，振动能源的能量采集速率λ=0，随着时间的增加，λ将以0.001 mJ/unit的速率递增，算法采用的能耗模型与参考文献[12]相同，其他参数见表1。

表1 仿真实验参数设置

6.2 实验结果

首先通过一组节点状态转换图阐述仿真实验的运行过程。实验初始时，将150个通信半径和能量各不相同的传感器节点部署到网络中，如图2(a)所示，此时所有节点均为白色。当算法运行结束后，可以得到如图2(b)所示的网络拓扑，其中，黑色表示活跃节点，灰色表示处于休眠的节点。实验结果取自随机生成的20个拓扑实例分别运行10次后的平均值，从通信开销和网络生命时间对算法进行评估。

实验1主要对拓扑构建算法的通信开销进行评估，当网络节点数为100时，观察发送和接收的消息数随着最大通信半径变化而发生的改变。如图3所示，HELM不管是需要发送还是需要接收的消息数都要比A3M更少，特别是当节点的最大通信半径较大(40 m)时，HELM需要接收的消息数为3 212.3条，而A3M需要接收大约7 942.5条消息，相当于HELM节省了59.6%的通信开销，这说明HELM的扩展性较好。

实验2将节点的最大通信半径固定为30 m，通过改变节点的数量来观察算法的通信开销。如图4所示，随着节点数量的增加，需要发送和接收的消息数都在不断增加。HELM需要发送的消息数量等于节点的数量，而A3M需要发送的消息数量为300～650条。相比之下，两个算法需要接收的消息数量更多，当网络节点数为200个时，HELM、A3M分别需要接收9 310.5条、22 475.8条消息，从图4中曲线的变化趋势预测，当节点数量更密集时，这一情况会更加明显。

实验3对拓扑维护的性能进行评估，将最大通信半径为20 m的100个节点进行部署，节点每隔10个单元时间向sink节点发送数据,拓扑维护中的时间、能量、故障阈值见表1中的T1、T2、T3，这里暂不考虑数据融合和能量采集的影响，观察通信覆盖率随时间的变化情况。图5显示了4种拓扑维护策略的运行情况，HELM和A3M两种拓扑维护策略与静态和动态拓扑维护相比都将延长网络的运行时间，特别是HELM，直到时间点20 988.2时开始出现第一个节点的死亡而导致通信覆盖率下降，这一现象在A3M中发生在时间点17 558.1，此时HELM提高了19.5%的网络运行时间，这是因为HELM的拓扑维护策略只有在不得已的情况下才对网络进行重构，否则对当前拓扑执行局部修复以减少网络能耗。

实验4在实验3的基础上对HELM中基于时间机制的维护策略进行评估，观察时间轮换的策略对通信覆盖率产生的影响。从图6中发现，考虑时间因素能够得到更好的通信覆盖率。当第一个节点死亡时，不考虑时间轮换的策略相比考虑时间轮换的策略提前了2 158.2个单位时间，随着时间的不断增加，两个算法的通信覆盖率差距在不断变大，这是因为基于时间轮换的策略使得节点之间的能量消耗更加平衡，而不考虑时间轮换的策略可能由于某些关键节点的死亡而使得网络性能快速下降。

实验5在实验3的基础上对HELM中基于故障机制的拓扑维护策略进行评估，将节点的故障率分别设为1%和3%，观察通信覆盖率的变化情况。如图7所示，随着节点故障率的增加，在相同生命时间下两种拓扑维护策略的通信覆盖率都有所下降，其中，HELM拓扑维护策略的第一个死亡节点的时间提前了1 836.5个时间单元。此外，由图可知，A3M拓扑维护策略下降得更快，这是因为当节点失效时，A3M不但每次都需要进行拓扑重构，而且在重构过程中A3M需要发送和接收的消息数量比HELM更多，这就造成A3M的能耗更大，严重影响了网络的生命时间。

实验6对能量补给模型的性能进行评估，观察是否考虑能量采集对网络的生命时间产生的影响。如图8所示，随着时间的增加剩余存活节点数量逐渐下降，但是考虑能量补给的网络的存活节点数量始终要大于不考虑能量补给的网络节点数量，这是因为部分节点可以通过采集而有效补给能量。带有能量补给的网络出现第一个死亡节点的时间为23 568.5，相比无能量补给模型，该模型相当于延长了7.2%的网络生命时间。

7 结束语

随着传感器节点可以通过能量采集进行供能，当前拓扑控制算法需要考虑节点能量补给的特性以延长网络的生命时间，本文在通信半径和能量存在异构的网络中提出了一种结合拓扑构建和拓扑维护过程的拓扑控制算法。算法首先以较少的通信开销构建连通支配集，而当拓扑不再高效时，及时运行拓扑维护算法，由sink节点决定采用局部或全局拓扑修复策略以节约网络能量。仿真结果显示，拓扑构建算法相比A3M可以节省超过59%的通信开销，而拓扑维护策略更是将网络的运行时间提高了将近20%。此外，与无能量补给的网络模型相比，带有能量补给的网络模型最终使网络的生命时间延长了7.2%。HELM可以应用在环境比较恶劣的地区，当节点失效时可以通过较小的能耗代价保障网络拓扑的质量。

1 钱志鸿,王义君.面向物联网的无线传感器网络综述.电子与信息学报,2013,35(1)：215～227 Qian Z H,Wang Y J.Internet of things-oriented wireless sensor networks review. Journal of Electronics & Information Technology,2013,35(1):215～227

2 Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks. IEEE Communications Surveys and Tutorials,2013,15(1):121～144

3 Labrador M A,Wightman P M.Topology Control in Wireless Sensor Network.Berlin:Springer,2009

4 He J,Ji S L,Fan P Z,et al.Constructing a load-balanced virtual backbone in wireless sensor networks.Proceedings of International Conference on Computing Networking and Communications,Maui,Hawaii,USA,2012:147～163

5 Wightman P M,Fabregas A,Labrador M A.An optimal solution to the MCDS problem for topology construction in wireless sensor networks.Proceedings of IEEE Latin-American Conference on Communications,Bogota,Columbia,2010:1～6

6 洪榛,俞立,张贵军等.基于最小连通支配集的无线传感网拓扑构建研究.电子与信息学报,2012,34(8)：2000～2006 Hong Z,Yu L,Zhang G J,et al.Topology construction based on minimum connected dominating set for wireless sensor networks.Journal of Electronics&Information Technology,2012,34(8):2000～2006

7 奎晓燕,杜华坤,梁俊斌.无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法.电子学报,2013,41(8)：1521～1528 Kui X Y,Du H K,Liang J B.An energy-balanced connected dominating sets for data gathering in wireless sensor networks.Acta Electronica Sinica,2013,41(8):1521～1528

8 Wightman P M,Labrador M A.Topology maintenance:extending the lifetime of wireless sensor networks.IEEE Latin America Transactions,2010,8(4):1～6

9 沈中,常义林,崔灿等.一种可自维护无线网络拓扑最小能量特性的分布式拓扑控制算法.计算机学报,2007,30(4)：569～578 Shen Z,Chang Y L,Cui C,et al.A distributed topology control algorithm for self-maintenance of the minimum-energy property of a wireless networks topology.Chinese Journal of Computers,2007,30(4):569～578

10 Liao Y,Qi H,Li W.Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks.IEEE Sensors Journal,2013,13(5):1498～1506

11 康一梅,李志军,胡江等.一种低能耗层次型无线传感器网络拓扑控制算法.自动化学报,2010,36(4)：543～549 Kang Y M,Li Z J,Hu J,et al.A Low-power hierarchical wireless sensor network topology control algorithm.Acta Automatica Sinica,2010,36(4):543～549

12 马晨明,王万良,洪榛.异构无线传感器网络中基于CDS树的拓扑控制方法.传感技术学报,2014,27(6)：814～820 Ma C M,Wang W L,Hong Z.A topology control method based on CDS tree in heterogeneous wireless sensor network.Chinese Journal of Sensors and Actuators,2014,27(6):814～820

13 Sudevalayam S,Kulkarni P.Energy harvesting sensor nodes:survey and implications.Communications Surveys&Tutorials,2011,13(3):443～461

14 姚玉坤,王冠,任智等.能耗均衡的自供能无线传感器网络分簇路由算法.传感技术学报,2013,10(26)：1420～1425 Yao Y K,Wang G,Ren Z,et al.Energy balanced clustering algorithm for self-energized wireless sensor networks.Chinese Journal of Sensors and Actuators,2013,10(26):1420～1425

15 Wightman P M,Labrador M A.Atarraya:a simulation tool to teach and research topology control algorithms for wireless sensor networks.Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009