一种具有稳定链路的幂律可调WSNs无标度容错拓扑算法

李曦达，刘 彬，尹荣荣，刘浩然

（1.燕山大学信息科学与工程学院，河北秦皇岛066004；2.燕山大学河北省特种光纤与光纤传感重点实验室，河北秦皇岛066004）

一种具有稳定链路的幂律可调WSNs无标度容错拓扑算法

李曦达1，*，刘 彬1，2，尹荣荣2，刘浩然2

（1.燕山大学信息科学与工程学院，河北秦皇岛066004；2.燕山大学河北省特种光纤与光纤传感重点实验室，河北秦皇岛066004）

针对固定幂律WSNs无标度容错拓扑不具普适应的问题，采用节点批量到达的Poisson网络规模以及节点吸引度规则，提出幂律可调的WSNs无标度容错拓扑算法APSL。该算法利用接收信号强度值建立通信链路，避免了网络中的不稳定链路，并通过调节拓扑参数，构建出了幂律指数在（1，+∞）的无标度容错拓扑。实验结果表明，APSL算法能够提升网络链路的稳定性，同时还能够满足网络多样化容错需求。

无线传感器网络；容错拓扑算法；稳定链路；幂律指数

0　引言

无线传感器网络（WSNs，Wireless Sensor Networks）无标度容错拓扑算法所构建的网络拓扑，无需添加冗余链路，无低能效制约，且可满足对恶劣环境的容错要求，具有冗余拓扑无法比拟的容错优势［1-2］。

Barabasi等人率先提出了著名的无标度拓扑生成模型BA［3］。基于BA模型，Zhu等人从WSNs节点传输范围有限角度提出了无标度拓扑算法，生成了具有局部范围增长和择优连接的无标度容错拓扑［4］。Zheng等人从WSNs规模随时间非线性增长角度提出了无标度拓扑算法，构建了非线性增长的无标度容错拓扑［5］。Yin等人从WSNs动态择优连接角度提出了无标度拓扑算法，构建了动态择优连接的无标度容错拓扑［6］。Luo和Zhang等人从WSNs节点竞争和退化、链路断开和重连角度提出无标度拓扑算法，分别构建了具有自修复能力的无标度容错拓扑［7-8］。以上研究能够有效提高网络对随机节点失效的容错性能，但在无标度容错拓扑构建中还没有考虑到链路的不稳定性，且无法满足网络对随机和选择节点失效的不同容忍要求，这对于面向实际应用的WSNs是不够的。

本文提出了一种具有稳定链路的幂律可调WSNs无标度容错拓扑算法APSL（Adjustable Power-law and Steady Links），利用基于批量到达的节点增长和基于链路质量的择优连接，构建出链路稳定且幂律指数在（1，+∞）的无标度容错拓扑，满足网络不同的容错需求。最后给出实验结果和分析。

1　稳定链路度量标准

目前链路质量度量标准主要有［9］：收包率PRR（Packet Reception Rate）、链路质量指示LQI（Link Quality Indicator）和接收信号强度指示RSSI（Received Signal Strength Indicator）。

PRR是最为直接的链路质量度量标准，它反映的是一段时间内节点成功收到数据包个数占总发送数据包的比例。PRR需要统计一段时间内的数据，而一般无线射频芯片在每个包到达时都能够提供LQI值和RSSI值［10］。相比较而言，LQI和RSSI在获取方式上优于PRR。针对CC2420无线射频芯片，Sprinivasan和Levis比较了PRR随LQI和RSSI的变化情况，发现RSSI对PRR的影响更为稳定，且具有良好的对称性［11］。基于此本文以RSSI为链路质量的度量标准，下面就对收包率PRR和接收信号强度指示值RSSI之间的变化关系进行理论分析。

由于网络中成功接收一个数据包的概率PRR与数据帧的大小f（以字节为单位）和比特误码率pe有关，可表示如下：

可见，PRR随着RSSI的增大呈指数上升趋势，且RSSI与PRR之间一一对应，即RSSI越大，相应的PRR越大，为此以较大的RSSI作为拓扑生成依据，生成的网络拓扑其信息通信可靠性就越高。

2　APSL算法

2.1APSL算法过程

WSNs拓扑是从一个小规模网络逐层向外增长，在单位时间间隔内可能同时有多个新节点加入网络，为此本文按照Possion分布批量添加新节点生成网络，给出幂律可调的WSNs无标度容错拓扑算法APSL，算法流程如图1所示。APSL算法包含两个过程：

1）非线性增长：在初始时刻（t=0）时，假定初始网络中有m0个孤立节点。t时刻，按照到达率为λ的Possion过程到达r［N（t）］θ个新节点，其中，参数θ＞0，r＞0，N（t）为t时刻节点到达的批次数。

2）择优连接：每一个到达的新节点与其邻域内m（m≤m0）个已存在的节点相连。到达新节点与领域内已存节点i相连的概率与节点的节点度和吸引度有关，故按照两部分求和形式设满足条件如下：

其中，0＜ε＜1，i=1，2…，m0+t-1，ki为节点i的节点度，βi为节点i的吸引度，它描述的是节点优先被选取建立连接的能力，由链路质量状况RSSI的取值来衡量。

图1　APSL算法流程Fig.1 Process of APSL algorithm

APSL算法中，择优连接概率Π（i）表明，WSNs中新加入的节点，其择优连接不仅仅依赖于与节点的节点度ki，还与节点间的链路质量状况RSSI（吸引度βi）有关。每个到达节点的新链路通过Π（i）添加到网络，通过调节拓扑参数ε，可调节节点度和吸引度对择优概率Π（i）的影响程度。因此，通过调整APSL算法参数ε，可有效控制WSNs无标度容错拓扑的形成过程。

考虑到算法复杂度决定其所需资源，为此对APSL算法信息复杂度进行分析。依据APSL算法实现过程，一个新节点若要加入网络，需要广播一次加入消息以寻找其邻节点，相应收到消息的邻节点需要回复一个消息，从而该新节点才能够依据择优连接概率确定建立连接的邻节点，进而广播一次连接消息完成与邻节点的连接；而节点加入网络后，若接收到来自待加入邻节点的加入消息时，需要广播一次回复消息，由于网络中节点的最大节点度为kmax，即其邻节点最多有kmax个，故APSL算法组网过程中，一个节点的信息复杂度为O（2+kmax），鉴于网络中有N-m0个节点待加入，所以APSL算法组网的信息复杂度为O（（2+kmax）·（N-m0））。

2.2APSL算法动态特性分析

基于APSL算法过程，下面分析APSL算法生成拓扑的度分布情况。根据Possion到达过程，在［0，t）内到达网络节点批次N（t）的均值为

设ti表示第i批节点进入网络的时刻，即第i批节点的到达时刻。令kij（t）表示t时刻第i批节点中的第j个节点的节点度。根据连续场理论，随机变量kij（t）是连续变化的。那么，kij（t）连续变化的速率为

再根据初始条件kij（ti）=m，依据分离变量法由式（7）可得

因此P（kij（t）≥k）可表示为

由Possion理论，随机变量ti服从Γ分布

其中，t≫ti。根据式（11），APSL算法生成拓扑度分布如下：

3　实验结果和分析

为了验证APSL算法的有效性，本节首先对APSL算法生成拓扑的度分布及相应容错能力进行仿真对比，验证APSL算法通过参数调整能够满足不同的容错需求。再实验研究通信链路的稳定性，验证APSL算法以RSSI作为通信链路质量度量标准的正确性。

实验一：在MATLAB平台上进行APSL生成拓扑度分布及容错性仿真实验。首先假设最大传输距离均为200 m的320个节点随机分布在800 m× 800 m的监测区域内，各节点分别执行APSL算法。图2给出了在APSL算法参数ε分别为0.1、0.5和0.9时生成的网络拓扑图。

图2　APSL拓扑图Fig.2 APSL topology

由图2可见，随着拓扑参数ε的增大，APSL拓扑中出现了极少量节点度特别大的节点，而大多数节点的节点度依然较小，此时随机发生的节点失效，更多的是节点度小的节点失效，它们不会对整个网络拓扑产生重大影响，体现出对随机节点失效的强容错性，而对于选择性的节点失效，是按照节点度由大到小的节点依次失效，它们对网络拓扑的破坏性极大，呈现出对选择性节点失效的脆弱性，反则反之。可见，拓扑参数ε的改变能够达到网络不同的容错需求。

下面进一步选择随机节点失效下的网络最大连通分支规模，和按照节点度由大到小选择性节点失效下的网络最大连通分支规模指标，对APSL算法参数ε分别取0.1、0.5和0.9时生成的网络拓扑进行容错性能的评价，以得到参数ε与生成拓扑容错性之间的变化情况，如图3、图4所示。

图3　APSL拓扑的容错性能对比情况Fig.3 Comparison of APSL topology fault-tolerance

图4　APSL拓扑的容侵性能对比情况Fig.4 Comparison of APSL topology intrusion-tolerance

由图3可知，APSL算法参数ε越大，其生成的网络拓扑在随机节点失效下的网络最大连通分支规模随失效节点数的递增其递减的趋势越慢，从而表明参数ε越大，其生成的网络拓扑对随机节点失效的容错性越好。相应地结合图4可知，APSL算法参数ε越大，其生成的网络拓扑在按节点度由大到小选择性节点失效下的网络最大连通分支规模随失效节点数的递增其递减的趋势越快，从而表明参数ε越大，其生成的网络拓扑对选择性节点失效的容错性越差。由此可见，随着APSL算法参数ε的增大，其生成网络拓扑在容忍随机节点失效的容错性方面会越好，而在容忍选择性节点失效的容错性方面却会越差。

图5　PRR和RSSI的变化关系图Fig.5 Relationship between PRR and RSSI

实验二：采用Crossbow公司的IRIS平台进行通信链路稳定性实验。首先在空旷的场地中放置两个IRIS节点［12］，一个节点直接与基站相连，记为A节点，作为数据接收端，另一个节点，记为B节点，作为数据发送端。初始A、B节点间的距离为0 m，移动B节点，当A、B节点间的距离每增加0.6 m，分别统计多次RSSI值，经一段时间得到PRR与RSSI的变化关系，如图5所示。由图5可知，收包率PRR随着链路质量指示值RSSI的递增呈现出递增的趋势。那么以RSSI作为通信链路质量度量标准，RSSI值越大，该通信链路的PRR就越大，通信链路就越稳定。下面对采用RSSI作为链路连接标准的APSL算法，其生成网络拓扑的链路稳定性进行验证。对APSL算法参数ε分别取0.1、0.5和0.9时生成的网络拓扑，其链路质量度量指标RSSI值，如图6所示。由图6可知，APSL算法参数ε越大，其生成网络拓扑的链路质量RSSI，其最小值（Min）、平均值（Mean）和最大值（Max）分别呈现递减趋势，并且链路质量RSSI的Min值均大于-96 dBm。进一步结合图5可知，此时网络拓扑链路的相应PRR值均高于0.9，从而表明，APSL算法生成拓扑具有好的链路稳定性。可见，APSL算法以RSSI为链路择优连接概率是合理的。

进一步采用典型WSNs无标度容错拓扑算法EAEM［4］进行仿真对比，以评价APSL拓扑的链路稳定性。图7显示了EAEM算法和APST算法（ε分别取0.1、0.5、0.9）生成网络拓扑，其链路质量度量指标RSSI均值随网络规模的变化情况。

图6　APSL拓扑的链路稳定性对比情况Fig.6 Comparison of APSL topology stability

图7　APST与EAEM拓扑链路稳定性对比Fig.7 Comparison of topology stability for APSL and EAEM

从图7可以看到，随着网络规模的增大，EAEM和APST算法（ε分别取0.1、0.5、0.9）所构建的网络拓扑其链路稳定性均呈上升趋势，且无论网络规模如何，APST算法生成的网络拓扑较EAEM算法生成拓扑的平均链路质量RSSI值都更大，即APST算法生成拓扑具有更好的链路稳定性，这主要是因为APST算法在构建无标度容错拓扑时引入RSSI值作为拓扑择优连接的标准，有效增强了链路稳定性。

4　结论

本文提出了一种以接收信号强度判断链路质量的WSNs无标度容错拓扑算法APSL。对APSL算法生成的不同幂律指数拓扑的容错能力进行的仿真研究，结果表明了随着幂律指数ω的增加，拓扑抵御随机节点失效的能力减弱，抵御选择性节点失效的能力增强的结论。通过以IRIS节点进行的通信实验研究，验证了APSL以RSSI值构建拓扑能够提升链路稳定性的结论。

［1］Zhou M X，Liu J.A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks［J］.Physica A：Statistical Mechanics and its Applications，2014，410：131-143.

［2］Baria A，Jaekel A，Jiang J，et al.Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement［J］.Computer Communications，2012，35（3）：320-333.

［3］Barabasi A，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（15）：509-512.

［4］Zhu H L，Luo H，Peng H P，et al.Complex networks-based energyefficient evoluation model for wireless sensor networks［J］.Chaos，Solitons and Fractals，2009，41（4）：1828-1835.

［5］Zheng G Z，Liu S Y，Qi X G.Scale-free topology evolution for wireless sensornetworks withreconstructionmechanism［J］. Computers&Electrical Engineering，2012，38（3）：643-651.

［6］Yin B B，Zhu L Z，Cai K Y.The BA model with finite-precision preferential attachment［J］.Physica A：Statistical Mechanics and its Applications.2009，388（14）：2806-2814.

［7］Luo X J，Yu H Q，Wang X.Energy-aware topology evolution model with link and node deletion in wireless sensor networks［J］.Mathematical Problems in Engineering.2012（4）：1-14.

［8］Zhang K，Han D H，Feng H P.A model of linear expanding in the local-world based on the laws of internal evolution of the wireless sensor networks［C］//Proceeding of International Conference on Computer Application and System Modeling，Taiyuan，2010：22-24.

［9］郝晓辰，窦晶晶，刘彬.基于路径损耗的无线传感器网络分布式拓扑控制算法［J］.软件学报，2009，20（12）：3213-3222.

［10］Naqvi H，Berber S，Salcic Z，et al.Energy efficiency of collaborative communication with imperfect frequency synchronization in wireless sensor networks［J］.Lecture Notes in Computer Science，2010，6059：214-227.

［11］Srinivasan K，Levis P.RSSI is under appreciated［C］//Proceedings of the Third Workshop on Embedded Networked Sensors，Boulder，2006：1-5.

［12］刘浩然，尹荣荣，郝晓辰，等.无线传感器网络中一种具有稳定链路的鲁棒可调拓扑算法［J］.电子与信息学报，2009，31（11）：2751-2756.

A scale-free fault-tolerant topology algorithm with adjustable power-law and steady links in wireless sensor networks

LI Xi-da1，LIU Bin1，2，YIN Rong-rong2，LIU Hao-ran2
（1.School of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China；2.The Key Laboratory for Special Fiber and Fiber Sensor of Hebei Province，Yanshan University，Qinhuangdao，Hebei 066004，China）

In order to solve the problem that the scale-free fault-tolerant topology with fixed power-law exponent is not universal，based on the node batch arrival rule in according with Poisson model and node attraction rule，a scale-free fault-tolerant topology algorithm with adjustable power-law and steady links（named APSL）is proposed.Firstly，the criterion of connecting links is built according to receive signal strength indication，which avoids effectively the instable links.Secondly，a scale-free fault-tolerant topology with the power-law exponent in the range（1，+∞）is built through adjusting the topology parameters.The experimental results show that APSL algorithm can fit the variety requirements of fault-tolerance and raise the stability of links.

wireless sensor networks；fault-tolerant topology algorithm；steady links；power-law exponent

TN929.53

A DOI：10.3969/j.issn.1007-791X.2015.06.014

1007-791X（2015）06-0555-06

2015-10-09 基金项目：河北省自然科学基金资助项目（F2015203091）；秦皇岛市科学技术研究与发展计划项目（201502A216）

*李曦达（1977-），女，辽宁辽阳人，博士研究生，副教授，主要研究方向为无线传感器网络，Email：lixida@ysu.edu.cn。