基于能量加权的无线传感器网络拓扑抗毁算法

刘玉伟， 陈雯柏，马 航，兰少峰，吴 昊

(北京信息科技大学 自动化学院， 北京 100020)

无线传感器网络(Wireless Sensor Networks，WSNs)以网络节点轻便、廉价、低功耗且易自组织和信息采集等特点被广泛应用于军事、安防等各种复杂场景[1-3]，是当前物联网的重要部分和研究热点。如今，5G技术兴起并迅速发展，以低延迟、高速率传输等优点，促进了传感器节点越来越多的应用到窄带物联网(NB-IoT)的部署方案中，将位置、图像、天气等大量数据信息收集注入到网络中，使信息得到更广泛有效的利用；同时，移动5G网络将使无线通信设备如无线传感器节点在军用通信系统中实现更高效的应用[4]。而无线传感器节点具有能量有限且易受外界复杂因素影响的特点，如何利用拓扑控制提高网络的抗毁性，进而保证网络执行各种复杂任务的能力，对无线传感网络应用具有重要意义[5]。

拓扑控制是节点以一定的规则进行邻居节点的选择并形成优化网络结构的过程，是网络实现协议的基础，形成的拓扑结构是网络生存的根基。为了延长拓扑中传感器节点的使用寿命，Fujii S等[6]提出了簇头选择和旋转等理论。 Zebbane B等[7]提出了一种基于组的能量守恒协议(Group-based Energy Conservation Protocol,GECP)，通过传感器节点之间的睡眠调度来延长网络生命周期，以确保网络连接；AçM等[8]提出了基于Esau-Williams(E-W)算法的设计，解决无线传感器网络中的CMST问题，降低了算法的能耗；Dorogovtsev等[9]提出了一种具有类循环拓扑的集中式连通感知算法，实现了更好的拓扑和物理连接要求；Hu S等[10]提出了一种无标度拓扑演化机制(Scale Free Topological Evolution Mechanism,SFTEM)，提高了网络的生存能力并保持能量平衡；Jemal A F等[11]提出了一种基于簇的无线传感器网络能量高效路由器布局方案，该方案采用K均值算法选择初始簇头，然后选择电池能量充足的簇头以及选择备用簇头，达到降低能耗的目标；Sun等[12]提出了以最小生成树为基础在连通拓扑构造中考虑剩余能量信息的能量感知加权动态拓扑控制(Weighted Dynamic Topology Control,WDTC)算法。WDTC基于链路权重函数工作，平衡了节点的能量消耗。

以上这些算法都在拓扑控制中对网络拓扑从节能角度和如何延长网络寿命角度考虑模拟搭建网络[7]，大量工作仅集中在考虑平衡节点的能量消耗及节点的生存时间问题，而没有从整个网络考虑其抗毁性[13-16]。本文从无线传感网络的抗毁角度出发，为增强网络拓扑的抗毁性，提出了能量加权的拓扑抗毁控制算法(Energy-aware Wighted Topology Invulnerability Control,EWTIC)，对网络进行构建并进行仿真验证。

1 系统模型及相关定义

1.1 系统模型

系统模型：假设一个面积为l×lm2的矩形区域，n个传感器节点随机撒播在此区域中[12]。假设每个节点通过GPS或是其他基于距离的定位技术获取自己的位置信息，每个节点具有唯一的ID，且节点是静态节点。传感器节点的传输范围有限，其通信半径R是无线电传播所能到达的最大欧几里得距离，无线电范围是平等且有限的，通信链路是对称的。假设节点功率可调，任意两节点u,v若可进行通信，则两节点距离d(u,v)≤R，记duv=1,否则duv=0。

定义1E={(u,v)∶d(u,v)≤dmax,u,v∈V}为边集，V为节点集，dmax为每个节点的最大传输范围，即为通信半径R。图G=(V,E)中的边(u,v)为无序，则称图G为无向图。无向图用来表示网络中传感器节点的拓扑结构，已连接的节点间可进行双向通信和信息传递。

定义2对于无向图G=(V,E)中的任意两个节点u,v，若两个节点之间的距离d(u,v)小于等于通信半径R，即d(u,v)≤R，同时满足duv=1，则称节点v为节点u的1跳邻居节点，记作v∈N(u)。

定义3在无向图G中，若顶点u,v间存在两条路径，除u,v两顶点之外，两条路径不经过相同的顶点，则称这两条路径为顶点不相交路径。

定义4若无向图中任意两节点间至少存在一条相通的路径，则称图是单连通的。

定义5网络由n个节点构成，k

定义6NVu={v∈V(G)∶d(u,v)≤dmax}定义为节点的可见邻域，Gu=(NVu,Eu)表示为G的生成子图。

1.2 能量模型

无线传感器网络(WSNs)中通常将第一个节点的死亡时间定义为网络的生存时间，网络的生存时间是网络性能评估的重要指标之一。网络的生存寿命与节点能量消耗紧密相关，本节建立网络拓扑的能量模型，确定能量消耗与通信距离等参数的关系。

网络的能量消耗主要来自于节点间的数据发送与接收，因此，主要依照节点数据的收发来构建能量模型。节点发送数据时，能量损耗分为发射电路损耗和功率放大损耗两部分。设有传输距离阈值d0，当两节点间的传输距离小于阈值d0,功率放大损耗为自由空间损耗；当大于等于阈值d0时，则为衰减空间损耗。

节点发送数据长度为lbit数据包的能耗为：

ETX(l,d)=lEelec+lEfsd2+Edad≤d0

(1)

ETX(l,d)=lEelec+lEmpd4+Edad>d0

(2)

节点接收数据长度为lbit数据包时，能量损耗仅为电路消耗，能耗为：

ERX(l)=lEelec

(3)

式(1)～(3)中，d为节点间距离；l为数据包长度；Eelec为收发每单位bit长度的数据所消耗的能量；Eda为多路径衰减能量。

网络中任意节点的能量消耗为发送和接收数据的能耗之和，所以任意节点u每lbit数据平均消耗的能量为：

ETX(l,d)=2lEelec+lEfsd2+Edad≤d0

(4)

ETX(l,d)=2lEelec+lEmpd4+Edad>d0

(5)

由式(4)、式(5)可知，网络拓扑中的节点的能量消耗主要取决于节点间的通信距离，节点的通信距离越大，能量消耗的越快，通信的节点间距离当小于阈值时，能量与距离的二次方成正比消耗，大于阈值时，则与距离的四次方成正比消耗，进而导致节点的剩余能量越低。

2 基于能量加权的拓扑抗毁算法

本文提出的基于能量加权的拓扑抗毁算法不同于LMST(Local Minimum Spanning Tree,LMST)算法和WDTC算法，主要思路在于能量加权的权重值下节点的选择和构建K连通的拓扑，从而实现抗毁效果。

2.1 LMST算法

能量感知加权动态拓扑控制(WDTC)算法是基于局部最小生成树LMST算法对网络进行拓扑构建的，LMST算法由以下4个步骤组成：(1)信息收集；(2)拓扑结构，每个节点构建其几何图的最小生成树(Minimum Spanning Tree,MST)；(3)传输功率的确定，每个节点调整其传输功率，使其能够到达最远的邻居；(4)只具有双向边的拓扑结构构建。LMST具有3个显著特点：(1)构造的拓扑保持了网络的连通性；(2)构建网络的拓扑中节点的逻辑度不超过6；(3)拓扑只有双向链路。

然而，在LMST构建的MST类拓扑中，每个节点的负载和传输功率分布都具有很大的不平衡性。因此，节点的能耗严重失衡，导致网络生存寿命缩短。因为LMST具有能耗不平衡、网络寿命有限等缺点，只要节点位置保持不变，LMST算法构建的拓扑不会改变，所以为延长网络寿命，使每个节点的剩余能量趋于均衡，提出WDTC算法。

2.2 WDTC算法

WDTC算法在LMST算法只利用几何信息的基础上，将节点的剩余能量信息添加进拓扑构建中，通过边权函数将几何图转化为加权图，每个节点利用新的加权图构建MST拓扑网络,边缘权重反映边缘上的通信成本。在每一阶段，随着网络中各节点剩余能量的消耗，边缘的权重是不同的，因此产生的MST也是不同的[12]。

WDTC算法步骤如下：

步骤1：每个节点以其最大传输功率周期性地广播Hello消息,消息包含节点的ID、位置和剩余能量。

步骤3：每个节点在加权W(u,v)的角度下，用Kruskal算法计算Gu的MST加权图。MST加权图既反映了边缘长度，又反映了节点的能量消耗信息。因此，节点u的邻域集随距离和能耗的变化而周期性变化，最终能耗趋于均衡。

构建的简易拓扑示意图如图1，根据WDTC算法步骤，依据权值得到加权图，根据Kruskal算法，以节点1为起点，通过权值选择，以1、3、4、6、5、2、1的顺序进行拓扑连接从而得到拓扑结果。

图1 WDTC算法拓扑示意图

WDTC算法重新配置拓扑时， WDTC和LMST的拓扑结构重构频率相同的情况下，WDTC不会产生任何额外的能量消耗和计算开销，因为剩余的能量信息可以通过交换消息中的位置信息来承载;当节点处于平稳状态时，WDTC下的拓扑重构频率要比LMST高得多;在WDTC和LMST中，每个节点都用相同的顶点和边构建其图的局部MST，因此WDTC和LMST具有相同的时间复杂度O(eloge)，其中e是边的数目。在WDTC中将拓扑重新构建M次，因此WDTC的计算开销也将是LMST的M倍。

2.3 基于能量加权的拓扑抗毁算法

网络中每个节点连通的邻居节点数量少，某些节点间的不相交路径只有一条，图1中关键链路一旦受损，数据的传输则会受到影响，网络便呈现出脆弱性，面对随机失效或是范围性失效，网络的受损程度会增大，抵御风险的能力偏低，从而影响网络的正常运行。同时，面对由静态节点组成的网络，节点的位置信息不变，网络中变化的是各节点的剩余能量，根据能量信息构建网络拓扑的WDTC算法达到了能耗均衡的效果，但为进一步提高网络的稳定性和抗毁性，提高其抵御风险的能力，本研究将给出相应改进方案，提出基于能量加权的拓扑抗毁算法(EWTIC算法)。

2.3.1EWITC算法

根据文献[12]，将能量信息添加在拓扑结构中，通过边权函数将几何图转化为加权图。根据文献[12]定义，权函数为W(u,v)=W(duv,Eu,Ev)>0，duv≤dmax,其中duv是u与v之间的欧氏距离，Eu,Ev分别是u和v的剩余能量。函数W是变量duv的增函数，是变量Eu和Ev的减函数，提出的算法依据边缘权重的不同应用K连通网络的思想进行连接，单个节点执行至多K次的邻居节点间权重值查找，对符合预设条件(包括能量阈值、距离阈值、权重值等)的节点进行拓扑连接，直至网络中所有节点重复相同的操作步骤，则完成网络的拓扑构建。

算法中，每个节点周期性地广播一个具有最大传输能量的Hello消息，以收集其可见邻居的位置和能量信息。根据节点的剩余能量信息重新配置拓扑，EWITC算法具有类似于WDTC的特性，与WDTC拓扑结构重构频率相同时，因为剩余的能量信息可以通过交换消息中的位置信息来承载，不会产生任何额外的能量消耗和计算开销；重构频率高于WDTC时，EWITC的能量消耗和计算开销相较于WDTC增加。

如图2所示，以6个节点的简易网络为例，对算法思想进行简要说明。利用边权函数已计算好加权值，在上图中以线段长短表示权值的大小。以节点1开始进行拓扑构建，节点1的邻居节点有节点2，3，4，5，经查找，节点1与节点3之间的加权值最小，对节点1和3进行连接，之后，同样以1为起点，查找与未连接节点间的最小加权值，节点1与2进行连接，重复上述查找，节点1与4进行连接，示例中以3为连通度，完成节点1的链路连接，以节点2为首，重复上述查找，依次连接到节点4与节点5。 其余节点同样依据此思想进行连接。

图2 EWITC算法拓扑示意图

2.3.2算法步骤

EWTIC算法步骤如下：

步骤1：网络初始化，节点随机布置在一定区域内，并根据实际情况对各节点能量设初值，节点ID、坐标信息等初始化。

步骤2：每个节点以其最大功率周期性广播Hello消息，消息中含有节点的ID、坐标以及剩余能量信息，完成信息交互。

步骤4：每个节点在加权W(u,v)的角度下，以K连通网络思想为基础，满足距离阈值、能量阈值的条件下，每个节点重复K次查找最小权重值，对符合条件的邻居节点进行拓扑连接并对节点邻居矩阵标记，直至网络中全部节点完成查找与连接，则完成拓扑构建。能量随着网络的运行而不断消耗，节点的邻接矩阵也会随能耗变化而定期变化，最终能耗均衡且抗毁性提高。

相较于LMST、WDTC算法，EWITC算法在同频率拓扑构建时不会产生额外的能量消耗和计算开销，因其剩余能量的信息可在交换位置信息时承载。EWITC算法的重构频率比LMST算法高，且EWITC算法的计算开销与WDTC算法相类似，同重构次数M成正比。

3 仿真与分析

本文采用Matlab R2015b对EWITC算法进行性能仿真验证，并与WDTC算法进行性能比较。通过仿真比较分析WDTC算法与EWITC算法的平均连通度、鲁棒性、介数中心性等性能指标的差异。

3.1 仿真结果

在WDTC的基础上，为了提高网络拓扑的抗毁性，提高网络抵御风险的能力，提出EWTIC算法以达到更好的拓扑质量。首先，对EWITC算法如何工作进行演示，搭建一个网络场景，将50个节点随机布置在100 m×100 m的方形区域内，节点的传输半径设置为40 m，实验中采用多路径传播的方式进行数据传输，为公平起见，一半的节点随机分配为源节点，另一半则作为目的节点。每个源节点以2包/s的速率向目的地发送数据包，节点的初始能量容量为E±0.05 J内随机分配，以贴近实际节点的能量容量分布，r为数据包传输的次数，最大运行次数rmax设为40，设置每次数据包大小l为4 000 bit。

图3中给出了EWITC算法的拓扑演化情况，类比最大功率传输，明显每个节点的连接路径减少，网络拓扑复杂度降低，每个节点需要通讯的节点减少。实验采用循环次数表示时间，随着运行次数的变化，可观察到拓扑随着能量分布变化而演化。

图3 EWTIC拓扑演化示意图

3.2 性能评价

在这一部分中，为了对EWITC算法从抗毁性角度[12,14]进行评价，实验中3个性能指标的计算将参照文献[5]中的3个性能指标的计算公式，即鲁棒性评价指标、平均连通度以及介数中心性评价指标进行抗毁性评估，通过计算验证算法的有效性。这里，实验将EWITC算法与WDTC和LEECH算法进行比较。n个节点分布在500 m ×500 m区域。每个节点的传输范围为100 m。实验中选择节点的连通度为4作为连通上界，连通度过大会造成网络能耗过大。表1中显示了其他模拟参数值。实验中节点n的数目以50到150为区间。每个数据点平均30次模拟运行。

表1中，α:指数，E:初始能量,Efs:自由空间损耗,Emp:衰减空间损耗,Eda:多路径衰减能量，Eelec单位数据传输损耗。

表1 仿真参数

节点的度通常是指与某个节点直接相连的边个数，反映对网络连通性影响的大小。网络的平均度(平均连通度)是网络中所有节点度的平均值。

从图4(a) 可以看出，EWITC算法的平均连通度明显优于WDTC和LEECH，随着节点数量的增加，曲线都有明显的增加，所提算法在连通度上始终比WDTC高，由此表明网络中节点的连通路径比WDTC多，因此信息的传输更有保证，网络的稳定性增加，这与实际拓扑情况相符。

网络的鲁棒性是指网络中任意节点被移除之后，网络中剩余节点间仍能保持连通的平均影响力。定义为任意节点被移除后，网络中的剩余连通节点对数与网络中的总节点对数的比值的均值。

由图4(b) 可知，EWTIC算法的鲁棒性随着节点的增加明显增加，增速明显高于其他算法。由此说明EWITC算法相较于其他算法，某节点的移除对网络的影响力更小，对网络造成的影响更低。WDTC算法由于采用最小生成树思想，某些节点失效可直接导致网络的断裂，鲁棒性低，对网络影响较大，故而EWITC算法在鲁棒性评价上更优。

节点的介数反映节点在整个系统中的影响力，定义为网络中所有的最短路径之中，经过节点的最短路径数占所有最短路径的比值。

介数中心性的比较中，为了更清晰显示仿真结果，实验中选择了50个节点下介数中心性图对WDTC算法和EWITC算法的进行比较。

EWITC与WDTC算法的介数中心性对比如图4(c) 所示。 WDTC算法构建的网络中，每个节点的介数中心性相对较小，大部分节点的介数偏小，某些节点如3、15等节点失效，则其他节点之间不连通，所以节点的介数相对较小且低于0.05。EWITC算法构建的网络，由于连通度相比于WDTC提高，且多路径通信下，更多节点分担通信路径的任务，因此节点介数增加，这明显也与实际情况相符合的。

仿真结果表明，从平均连通度、鲁棒性以及介数中心性角度来看，EWITC算法构建的拓扑的抗毁性更好。

图4 各评价指标曲线

4 结论

1) 针对加权拓扑算法构建拓扑结构的易受损性，提出了一种有效的能量加权的抗毁拓扑EWTIC算法。

2) 将能量加权与k连通思想结合构建出了稳定的拓扑结构，随着能量的消耗，网络的拓扑结构定期调整，网络仍然保持拓扑结构的均衡性，多路径传输得到保证。

3) 算法在鲁棒性、介数中心性、网络平均连通度评价指标评估下，EWITC抗毁算法表现出高连通度、强鲁棒性和更优的介数中心性，有效地增强了网络拓扑的抗毁能力，对网络拓扑结构稳定具有参考意义。