基于无线信号不规则性的无线传感网层次型拓扑控制算法

唐 宏 王惠珠

1 引言

无线传感器网络（Wireless Sensor Networks,WSNs）由大量能量受限的传感器设备组成，延长网络生存时间是目前首先需要考虑的问题[1,2]。拓扑控制是一种重要的节能技术，在保证覆盖和连通质量的条件下，通过减少冗余链路降低网络能耗[3]。层次型拓扑控制算法大都以LEACH算法为基础发展而来，其拓扑结构主要有3类：（1）簇内单跳、簇间单跳[4,5]；（2）簇内多跳、簇间多跳[6]；（3）单多跳相结合[7,8]。其中实现分簇的方法主要有静态分簇[6,9]和动态分簇。选取簇头的方式主要有4类：（1）采用随机数阈值，使产生的随机数小于该阈值的节点成为簇头[4,5]。（2）考虑节点剩余能量，使剩余能量较高的节点优先成为簇头[8]。（3）考虑节点竞争半径，使基站附近形成较小的簇，缓解基站附近的“热区”问题[7,8]。（4）综合考虑节点剩余能量以及到基站的距离，使剩余能量较高且距离基站较近的节点优先成为簇头[10]。

上述方法未考虑节点成为簇头后簇结构的性能，且未考虑无线信号不规则性对拓扑构建过程的影响。延长网络生存时间的同时未兼顾网络能量均衡性，且存在簇头间链路较稀疏的情况。本文欲在考虑无线信号不规则性的条件下，对节点成为簇头后的簇结构稳定性建模，并使簇头间形成平面型数据转发层，构建两层的WSNs拓扑结构。该方法首先根据无线信号不规则性 DOI（Degree Of Irregularity）模型[11]定义区域分割参数实现静态分簇。其次，根据节点成簇稳定性选取候选簇头，并根据候选簇头在簇内的位置确定最终簇头。簇头间则形成平面型拓扑结构以避免由于中继簇头突然失效造成的网络分割。最后给出WSIBTC算法与其他几类算法的实验比较结果。

2 系统假设和能耗模型

2.1 系统假设

（1）传感器节点随机分布于监测区域内，基站位于监测区域之外；

（2）传感器节点和基站部署完成后处于静止状态，前者同构，能量受限，后者能量无限；

（3）传感器节点通过现有的定位技术或者接收信号强度与节点间距离的关系获得自身在监测区域内的具体位置信息。

定义 1 WSNs可以抽象为2维平面图G （V, E）。其中G为节点以最大发射功率相互通信时形成的原始拓扑结构，V为节点集合，E为节点间边的集合。

定义 2 集合 VPH包含的元素为任意节点的物理邻居节点。对于任意的节点i,j∈V，若满足i∈且 j ∈，则表示节点i和j相互覆盖；如果i∈且j∉VPiH，则表示节点i覆盖j，但是节点j不能覆盖i。

定义 3 集合VL包含的元素为任意节点的逻辑邻居节点。该集合是通过某种计算规则，将节点VPH集合中符合条件的物理邻居节点筛选出来组成的节点集合。

定义5Ri为节点i的平均有效传输距离，Rj为节点j的平均有效传输距离， dij为节点i, j之间的距离，如果dij＜Ri且Rj，则i∈且j∈。

2.2 能耗模型

WSIBTC算法采用与LEACH算法相同的能耗模型。任意两个可以相互通信且距离为d的节点间发送l比特数据的能耗为

其中 Ee表示发射端和接收端的电路损耗能量；d0为参考距离，满足d0=。LEACH能耗模型定义如果 d ＜d0，功率放大损耗采用自由空间传播模型；如果 d ≥d0，则采用多径传播模型。εfs和εmp分别表示两种模型中对应的功率放大器的放大参数。令DAE 为节点融合数据包时消耗的能量，则接收端接收l比特数据以及节点将接收到的0n个数据包融合为一个数据包时的能耗分别可用式（2），式（3）表示为

3 算法原理

3.1 子区域个数的确定

文献[11]建立的无线信号不规则性数学模型为DOI模型，即由于传感器设备本身的异构性或者信号传播时发生的衍射、反射等现象造成无线信号在不同传播方向上具有不同的路径损耗。DOI模型中节点各方向上的有效传输距离为

其中 Pt为节点发射功率；rss为接收端接收信号强度；Pl（d0）为自由空间传播模型下的路径损耗；α为路径损耗指数，介于2～4之间。 ki为具体传播方向上的路径损耗调整因子，满足其中DOI为传播方向每改变1°时最大路径损耗变化百分数，介于0～0.02之间；Rand为服从韦伯分布的随机数； i = 0 代表初始传播方向。由于节点可以通过测量获取接收信号强度，为了便于分析，将式（4）化简为

令 Rmax表示节点最大有效传输距离， Rmin为最小有效传输距离，则节点平均有效传输距离为R = （Rmax+Rmin）/2。假设节点随机分布于边长为L的正方形区域中，子区域个数为m，则每个子区域的面积约为 L2/m。由正方形面积与对角线间的关系可得，子区域对角线长度l0= L，则簇内及相邻子区域节点相互可达的条件为2l0≤R，因此m与R的关系需满足 m ≥ 8L2/f2（kav）。其中 kav为R对应的平均路径损耗调整因子。综上所述，区域分割参数 t0需满足

⋅表示向上取整。基站根据t0将监测区域分别进行横向、纵向上的划分，则 m =。

3.2 簇头的确定

串联与并联模块的组合可以描述任何复杂系统。在层次型网络拓扑中，根据节点感知到的数据间的依赖关系，其 RBD （Reliability Block Diagram）模型可以表示为[12]

图1 有n个簇成员的簇头RBD模型

节点i竞争簇头时的成簇稳定性可以表示为

其 中S（ r） 为 节 点 的 生 存 函 数 ， 定 义 为Si（ r）=Ere（r）（r）。其中（r）为节点i第r轮的剩余能量，Ere（r）为第r轮网络平均剩余能量。

候选簇头的产生是形成簇结构的基础。子区域中的节点均产生一个0～1之间的随机数，若节点i产生的随机数小于等于阈值T（ i），则广播其为候选簇头的消息。现有文献对LEACH算法中T（ i）的改进主要通过引入节点剩余能量以及全网平均剩余能量。当网络进入瓶颈期，存活节点较低的能量等级使T（ i）大大减小，造成簇头选取过程的不稳定[9]。考虑上述因素，一种新的阈值计算公式可以表示为

其中p为节点成为簇头的概率，r是目前循环进行的轮数，0G为最近1/p轮中尚未成为簇头的节点集合。产生的随机数小于等于（）T i的簇成员将成为候选簇头，广播COMPETE_HEAD_MSG。

簇头在簇中的位置直接影响着簇成员的能耗。假设每个簇中距离基站最近和最远的节点分别为i,j,ijd为节点i,j之间的距离。以ijd为直径画圆，候选簇头y,h,g的位置如图2所示。根据三角公式，位于该圆域内且距离节点i,j最近的候选簇头将优先成为最终簇头。

竞选成功的候选簇头广播 FINAL_HEAD_MSG，接收到该消息的候选簇头则广播 QUIT_MSG宣布竞争失败，成为簇成员。簇成员发送JOIN_MSG消息请求入簇，建立簇内星型拓扑结构。

3.3 簇头间权值函数的确定

图2 候选簇头位置示意图

网络中的节点可以被看作粒子，节点间的通信代价可以等效为粒子间的作用力[13]。WSIBTC算法将这种虚拟的作用力定义为节点间的“粘度”，其中簇头的剩余能量等效为粒子的电荷量，簇头间的路径损耗作为簇头通信时的代价，则簇头间的“粘度”满足

dBS为簇头到基站的距离，γ1,γ2为加权系数，满足γ1+γ2=1。

构建簇头间的拓扑结构时，簇成员暂时关闭通信模块进入睡眠状态。簇头广播HelloMSG获取邻居信息表。簇头i接收到邻居簇头j的信息表后，首先判断是否存在公共物理邻居簇头s。若存在，则需比较W（ i, j） 与W（ i, s） + W （ s, j ） 的大小，判断与物理邻居进行通信时的本地最小权值。令VLiS为簇头i的单跳逻辑邻居簇头集合， VLiM为多跳逻辑邻居簇头集合，若存在公共物理邻居簇头s满足W（ i, j）＞W（ i, s） + W （ s, j） ，则VLiM= VLiM∪ { j}且中继簇头为s，否则 VLiS

= VLiS∪{ j }。所有簇头均执行上述过程，建立平面型数据转发层。

3.4 网络能耗分析

假设监测区域为边长为L的正方形区域，节点数为 N0,n为子区域中节点个数，初始能量为 E0,m为子区域个数，每轮网络能耗包括簇头能耗 ECH和簇成员能耗 ECM。令网络每轮能耗为 Erd，则 Erd=ECH+ECM。WSIBTC算法根据簇头到基站的距离选取负责与基站直接通信的簇头，其选择依据为le=（dBS/ d0），其中 ⋅ 为向上取整函数。若le＞1，即该簇头与基站间的距离大于 d0，需通过中继簇头转发数据；若le = 1 ，即该簇头到基站的距离小于等于 d0。le = 1 的簇头广播自身的等级消息，其他簇头则将相应簇头标记为最终目的节点，使网络中传递的数据包最终由该簇头传递至基站。因此，簇头能耗需分情况讨论。

情况1 le＞1时簇头接收簇成员及邻居簇头数据包时的能耗分别为,。令c为邻居簇头的个数，满足1≤c＜m。簇头向邻居簇头发送数据包时的能耗为，其中 dCH为簇头间的平均距离，满足dCH= R / 2 = f （ kav）/2，其总能耗满足 E=++。

情况 2 le = 1 时簇头接收簇成员及邻居簇头数据包时的能耗同情况（1）。簇头向基站发送数据包时的能耗为，其总能耗为。现有文献对簇头到基站的平均距离估计值为 dBS=0.765⋅（L/2）[8]。下面对簇成员能耗进行分析。

由于每个簇所占据的平均网络面积大小为L2/m，该区域中节点的分布函数可表示为ρ=m / f（ x, y）[15]。假设簇头位于簇中心，则簇成员与簇头间的期望平方距离满足

由式（13）可以看出网络能耗与平均有效传输距离对应的平均路径损耗调整因子有关。

4 算法分析

4.1 算法实现

步骤 1 部署节点后，基站发送 InitialMSG，收到 InitialMSG的节点上报自身的位置、id等信息，基站获取节点信息，统计节点总数，执行WSIBTC算法。

步骤 2 基站根据0t将监测区域分别进行横向、纵向上的划分，形成多个子区域，每个子区域即是一个簇。基站广播AdverinfoMSG告知节点所属的簇。

步骤 3 簇内节点以最大发射功率获取邻居节点信息表。根据节点的成簇稳定性选取候选簇头，最终簇头的产生由候选簇头在簇中的位置决定。最终簇头产生后，簇内形成星形拓扑结构。

步骤 4 簇成员暂时关闭通信模块，进入睡眠状态。簇头间交换邻居信息表，计算自身与邻居簇头的权值，选择邻居簇头。所有簇头均执行上述过程，簇头间形成一种平面型拓扑结构。

步骤 5 拓扑结构形成后，基站唤醒簇成员，开始数据包的传递。当完成一定的数据收集后，重新跳到步骤 3。循环执行上述步骤，直到某个节点能量耗尽而失效。

4.2 消息复杂度

性质 在所选网络中，WSIBTC算法的消息复杂度为O（ N0）。

证明 如前所述，网络中的簇头个数为m，则簇成员的总数为 N0- m 。基站广播AdverinfoMSG告知节点所属的簇，并广播一条网络平均能量消息AVE_MSG给每一个节点，其次 N0T个候选簇头共广播 N0T条COMPETE_HEAD_MSG消息。每个候选簇头广播一条FINAL_HEAD_MSG消息宣布其竞争成功，或者广播一条QUIT_MSG消息宣布其退出竞争。每个簇头广播一条 HEAD_MSG消息， N0- m 个簇成员广播一条JOIN_MSG消息。构建簇头间拓扑结构时，每个簇头需广播HelloMSG消息获取邻居信息。因此，WSIBTC算法的消息开销 满 足 2 + N0T+ N0T+ m + （ N0- m ） + m =2N0T+N0+m+2，其消息复杂度为O（ N0）。 证毕

上述性质说明WSIBTC算法的消息开销较小，具有较好的能量效率。HEED算法[16]需在簇半径内进行多次消息迭代，最多进行Ntr×N次消息交换，其中 Ntr为消息迭代次数，通信开销较大。WSIBTC算法避免了消息迭代，其通信开销小于 HEED。EEUC的消息复杂度也为O（ N0），但其在选择候选簇头时没有考虑节点的剩余能量，且竞争系数较小时，簇头间的距离过大，增大了簇头能耗。

4.3 网络连通性

假设所有节点均以最大发射功率通信时构建的全局拓扑为G （V, E），执行WSIBTC算法后得到的拓扑结构为 G*（ V, E*） 。

性质 如果G （V, E） 是连通的，那么G*（V, E*）也是连通的。

证明 由于G（ V, E）连通，则G （V, E）中必然存在一条路径 p t= （ w0= i , w1, w2, ⋅⋅⋅,wn-1,wn= j ） ，其中 wg和 wg+1（g = 0 ,1,2,⋅⋅⋅,n - 1 ） 互为邻居节点。要证明 G*（ V, E*） 中节点i,j也是连通的，只需证明任意互为邻居的节点对 wg和 wg+1之间存在通信路径。WSIBTC算法中，G*（ V, E*）中各个节点均建立起自身的邻居信息表，即如果节点 wg和 wg+1互为邻居节点，则一定存在彼此的邻居信息表中，所以仅证明wg到 wg+1存在通信路径即可。WSIBTC算法中需分两种情况进行讨论：（1）节点 wg到 wg+1存在单跳通信路径；（2）节点 wg到 wg+1存在多跳通信路径，即节点和 wg+1为簇头，且二者之间存在一个公共物理邻居簇头 ws，满足 wg经 ws转发到 wg+1比直接传输信息到 wg+1的权值更小。继续分情况讨论 wg和 ws之间以及 ws和 wg+1存在通信路径即可。重复上述步骤，最终得到 wg和 wg+1连通的结论。由节点i,j的任意性可知，G*（ V, E*）中的每对节点之间都至少存在一条通信路径，因此 G*（ V, E*） 连通。 证毕

4.4 生存函数的性质

性质 1 Si（0）=1。

因此， Si（ r）是单调递减的。 证毕

5 仿真实现和分析

5.1 仿真参数设置

定义 6 从第1轮选择簇头开始到第1个节点死亡（能量消耗尽）的轮数，称为网络生存时间。

表 1 WSIBTC算法的各个参数仿真值

5.2 算法仿真结果分析

5.2.1 网络拓扑结构 图3为未经拓扑控制时的网络拓扑图。从图3中可以看出，节点以最大发射功率与可达邻居节点相互通信，造成网络中存在大量的冗余链路，节点能耗较大，网络生存时间较短。图4为执行WSIBTC算法后得到的拓扑图。从图4中可以看出，监测区域被划分为9个子区域，即9个簇。黑色实心圆点为每个簇中选出的簇头，黑色实线为簇头间的拓扑关系，簇头间形成了一种平面型的拓扑结构。通过图 3，图 4的对比可以看出由WSIBTC算法得到的拓扑结构精简了节点间大量的冗余链路。簇头间形成平面拓扑结构，当某个中继簇头因外界原因突然失效时，簇头间仍存在其他通信路径。

图3 未经拓扑控制的网络拓扑结构

图5 无线信号不规则性对 网络生存时间的影响

5.2.2 无线信号不规则性对网络性能的影响 图5为无线信号不规则性对网络生存时间的影响，可以看出DOI较大时会缩短网络的生存时间，降低节点平均有效传输距离。监测区域需被划分为更多的子区域以保证簇内及簇间节点的通信，即每一轮担任簇头的节点数增多，需进行处理及转发的数据包的数量增大，使节点能耗速率增大，如图6所示。存活节点的数量可以反映网络中节点的能量均衡情况。存活节点的数量越多，说明网络能量利用率越高，节点寿命越长。图6为DOI对网络剩余能量的影响。可以看出当DOI较大时，其能耗曲线相对较陡。基于上述原因，DOI较大时不仅会使网络出现第1个死亡节点的时间提前，同时增大了网络能耗速率。

5.2.3 网络能耗对比 图 7比较各算法的网络生存时间。如图7可知WSIBTC算法相比于其他几种算法，有效地延长了网络的生存时间。LEACH,MODELEACH, MODELEACHST与MODELEACHHT算法中簇头与基站之间采用单跳通信方式，距离基站较远的簇头能耗较大，网络生存时间较短。在MODELEACH算法的基础上通过分别引入一个软门限与硬门限值降低簇头重选频率，使网络生存时间得以延长，但是其依然保留了LEACH算法原有的拓扑结构。EEUC算法在选取候选簇头时没有考虑节点的剩余能量，且在竞争系数较小时会导致簇头间距离过大，使簇头能耗过大。WSIBTC算法可以避免网络进入瓶颈期后存在部分节点剩余能量较高的现象，簇头在选择邻居簇头时在一定程度上平衡了簇头间的能耗，因此有效延长了网络的生存时间。图8比较各算法的网络能耗。从图8中可知其他几种算法的网络能耗速率均高于 WSIBTC算法，其原因与上述比较网络生存时间的原因相同。

图9比较各算法的网络能量均衡性。从图9中可知EEUC算法表现出了良好的能量均衡性，其在出现第 1 个死亡节点后，网络即进入衰亡期，大量节点随之死亡，说明基于节点竞争半径的非均匀分簇算法能够有效地平衡节点间的能耗。MODELEACH,MODELEACHHT, MODELEAC HST算法存在节点能耗不均衡的现象。WSIBTC算法的网络能量均衡性介于上述算法之间，且在考虑无线信号不规则性时，其网络能量均衡性会受到影响。图10比较各算法产生的有效数据包的数量。有效数据包的数量是指在未进行数据融合时簇头需向基站传递的数据包的数量。从图10中可以才看出WSIBTC算法产生的有效数据包的数量高于其他几种算法，并且接近于EEUC算法产生的有效数据包的数量。综合来看，WSIBTC算法相比于其他几种算法效果更优。

图6 无线信号不规则性对网络能耗的影响

图7 网络生存时间比较图

图8 网络能耗比较图

图9 网络能量均衡性比较图

图10 网络有效数据包的数量比较图

6 结束语

本文从子区域个数的确定、候选簇头的选取、最终簇头的确定以及簇头间拓扑结构的建立4个方面研究基于无线信号不规则性的无线传感网层次型拓扑控制算法。在WSIBTC算法中根据节点平均有效传输距离将监测区域划分为多个子区域，并根据RBD图对节点的成簇稳定性进行建模，作为选取候选簇头的标准，最终簇头的确定则由候选簇头在簇内的位置决定。在建立簇头间的拓扑结构时，根据粒子间的作用力定义了节点间的“粘度”函数，并在此基础上定义了簇头间的权值函数作为选择邻居簇头的标准。分析了节点以及网络能耗，并给出了网络每一轮能耗的理论模型。在此基础上，对算法的消息复杂度、网络连通性以及节点生存函数的性质进行了分析证明。最后仿真比较无线信号不规则性对网络生存时间、网络能耗的影响以及 LEACH,EEUC, MODELEACH, MODELEACHST, MODE LEACHHT和WSIBTC算法的网络生存时间、网络能耗、网络能量均衡性和网络中产生的有效数据包的数量。

[1] 陈友荣, 周骏华, 尉理哲, 等. 基于网格的移动无线传感网生存时间优化算法[J]. 电子与信息学报, 2014, 36（10）:2370-2378.Chen You-rong, Zhou Jun-hua, Wei Li-zhe, et al.. Grid-based lifetime optimization algorithm for mobile wireless sensor networks[J]. Journal of Electronics & Information Technology,2014, 36 （10）: 2370-2378.

[2] Salarian H, Chin K W, and Naghdy F. An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J]. IEEE Transactions on Vehicular Technology,2014, 63（5）: 2407-2419.

[3] Thakkar A and Kotecha K. Cluster head election for energy and delay constraint applications of wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14（8）: 2658-2664.

[4] Heinzelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. IEEE Proceedings of the 33rd Annual Hawaii International Conference, Hawaii, 2000:8020-8029.

[5] Mahmood D, Javaid N, Mahmood S, et al.. A variant of LEACH for WSNs[C]. IEEE 2013 Eighth Internatioanal Conference on Broadband and Wireless Computing,Communication and Applications （BWCCA）, Compiegne,2013: 158-163.

[6] Sheikhpour R and Jabbehdari S. An energyefficient chainbased routing protocol for wireless sensor networks[J]. KSII Transactions on Internet and Information Systems, 2013,7（6）: 1357-1378.

[7] 李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007, 30（1）: 27-36.Li Cheng-fa, Chen Gui-hai, Ye Mao, et al.. An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Juornal of Computers, 2007, 30（1）: 27-36.

[8] 尚凤军, Mehran A, Tadeusz W. 无线传感器网络的分布式能量条有效非均匀成簇算法[J]. 通信学报, 2009, 30（10）: 34-43.Shang Feng-jun, Mehran A, and Tadeusz W. Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J]. Journal on Communications, 2009, 30（10）:34-43.

[9] Kumar D. Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks[J]. IET Wireless Sensor Systems, 2014, 4（1）: 9-16.

[10] Jafri M R, Javaid N, Javaid A, et al.. Maximizing the lifetime of multi-chain pegasis using sink mobility[J]. World Applied Sciences Journal, 2013, 21（9）: 1283-1289.

[11] Zhou G, He T, Krishnamurthy S, et al.. Models and solutions for radio irregularity in wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2006, 2（2）: 221-262.

[12] 周祖德, 胡鹏, 李方敏. 无线传感器网络分簇通信协议的可靠性方案[J]. 通信学报, 2008, 29（5）: 114-121.Zhou Zu-de, Hu Peng, and Li Fang-min. Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J]. Journal on Communications, 2008, 29（5）:114-121.

[13] Ammari H M. An energy-aware cover-sense-inform framework for k-covered wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23（4）:651-658.

[14] 郝晓辰, 窦晶晶, 刘彬. 基于路径损耗的无线传感器网络分布式拓扑控制算法[J]. 软件学报, 2009, 20（12）: 3213-3222.Hao Xiao-chen, Dou Jing-jing, and Liu Bin. Path-loss based distributed topology control algorithm for wireless sensor networks[J]. Journal of Software, 2009, 20（12）: 3213-3222.

[15] 刘浩然, 韩涛, 李雅倩, 等. 具有路径损耗优化特性的 WSN无标度容错拓扑控制算法[J]. 通信学报, 2014, 35（6）: 64-72.Liu Hao-ran, Han Tao, Li Ya-qian, et al.. Scale-free fault-tolerant topology control algorithm in wireless sensor network with optimization of path energy consumption[J].Journal on Communications, 2014, 35（6）: 64-72.

[16] Younis O and Fahmy S. HEED: a hybrid, energy-efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing, 2004, 3（4）:366-379.

[17] 汤强, 汪秉文, 戴志诚, 等. 半集中式能耗均衡多跳分簇协议[J]. 小型微型计算机系统, 2010, 31（4）: 583-586.Tang Qiang, Wang Bing-wen, Dai Zhi-cheng, et al.. Semicentralized clustering protocol with energy balance and multi-hop transmission[J]. Journal of Chinese Computer Systems, 2010, 31（4）: 583-586.?