无标度的WSNs路由算法研究

刘莉莉，徐 野

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

无标度的WSNs路由算法研究

刘莉莉，徐 野

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

针对无标度的拓扑特性，提出一种基于无标度的无线传感器网络路由算法。该路由算法从平均度分布和节点吸附性的角度出发，采用多路径的设计原则，建立一种无标度网络模型，利用该模型建立无线传感器网络拓扑，同时节点具有信息融合能力，提高数据的冗余可靠性，降低网络吞吐量，使网络能量均衡，延长网络生命周期。仿真结果表明，该路由算法与针对无线传感器网络的一些路由算法Flooding、LEACH和NBEERP相比，在节点度分布、可靠性和总体性能评价方面效果显著。

无标度；无线传感器网络；路由算法；网络生命周期

无标度网络模型起源于1999年，当年10月，美国的圣母大学物理系教授Barabasi和他的博士生Albert共同写作了一篇题目为《随机网络中标度的涌现》[1]的论文，这篇论文在“Science”杂志上发表，它揭示了复杂网络的无标度特性，即马太定律，绝大多数节点的度很低，而只有少数节点的度很高的一种定律。经过长期的研究发现，无标度网络普遍存在于实际网络中。Barabasi教授在此理论的基础上，建立了无标度模型，现在被简称为BA模型。无标度网络的拓扑服从幂律分布，其中，增长特性和择优连接特性是无标度网络标志性特征。不同的幂指数会影响网络均匀性，而均匀性又对网络的鲁棒性产生一定的影响。目前的无标度网络，主要是对其拓扑结构特性和模型的研究，把无标度理论应用到无线传感器网络中的应用还相对较少。文献[2]考虑节点本身吸附性，在网络择优连接上进行改进，分析网络的度分布特性；文献[3]以路径上的节点强度乘积定义有效代价，利用信息包队列长度与发送能力之间的关系，自适应调整邻居节点权值，以提高网络的吞吐量；文献[4]利用无标度网络的幂律和强聚集特性，很好地平衡了路由表大小和伸长系数的关系，提高网络的扩展性。通过设置一个阈值来约束地标节点最小的覆盖面，研究其对紧凑路由算法的影响；文献[5]对网络流量模型和节点的betweeness进行分析和改进，提高模型的网络容量；文献[6]从无标度网络的物理特性出发，综合网络节点队列长度，建立动态局部路由；文献[7]深入研究网络拓扑和节点的处理速度对路由算法设计的影响，分别从静态和动态的角度出发，提出参数优化方法。文献[8]基于无标度的结构提出了WSNs的容错拓扑控制算法，核心思想是提高无线传感器网络的容错性。这些文献中的路由算法从不同的角度优化网络特性，但是没有针对网络拓扑特性提出的路由算法。无线传感器网络(wireless sensor network，WSN)是由部署在监测区域内大量的、廉价的、微型的传感器组成，通过无线通信方式形成的一个多跳的自组织的网络系统。无线传感器网络通常包括传感器节点、汇聚节点和管理节点，通过随机部署在监测区域内或附近形成的自组织方式的网络。在无线传感器网络中，传感器节点将监测收集的数据经过多条路径传递到汇聚节点，之后通过互联网或卫星送达管理节点。本文针对无标度的拓扑特性，提出一种基于无标度特性的无线传感器网络路由SFRA算法，该算法在数据传输、网络能耗、存活节点数和网络生命周期方面进行相应的仿真研究。

1 基于无标度的网络模型

无标度网络拓扑有两个必不可少的形成机制：增长特性和择优连接特性。正是因为这两个特性才能对无标度网络具有幂律分布进行解释。所以，具有幂律分布的网络称为无标度网络。根据无标度的性质，在无线传感器网络中建立一定的择优连接机制，使得传感器节点的能量分布均衡，从而延长网络的生命周期；也可以改变网络的增长机制，通过控制网络的拓扑结构，调节网络的均匀性，从而在面对随机攻击和特定攻击时，提高网络的鲁棒性。因为多数节点的度很少，少数节点的度很高，所以对那些度很高的节点的能耗研究就显得尤为重要。

无标度网络不是规则网络，也不是小世界网络，而是一种根据一定的策略所形成的介于规则和随机网络之间的复杂网络。

1.1 无标度网络属性

无标度网络的一些基本定义如下：

定义1 设无向图G=(V，E)，N=|V|表示网络节点数目，M=|E|表示网络的边数。则节点i的度定义为：节点i与邻居节点相连接的数量，记做ki。

定义2 网络中随机一节点的节点度称为度分布，无标度网络节点度服从幂律分布，度分布函数用p(k)表示，即网络中任意节点正好有k条边的概率。那么度为k的节点数目与k之间的关系为

p(k)∝k-r

(1)符合这个关系式的网络就是具有幂律特性的拓扑。

定义3 无标度网络的标志性特征是增长和择优，这也是无标度网络的形成机制。

定义4 网络G中节点服从幂律分布，但是其缺少一个描述问题的特征尺度，所以被称为无尺度网络，也称为无标度网络。

定义5 网络节点的幂律分布遵从马太定律，即绝大多数节点的度很低，而只有少数节点的度很高，将这些度很高的少数节点定义为热节点，多数度很低的节点成为普通节点。

定义6 设节点自身具有吸附性，那么新加入网络的节点与网络中原来的节点相连接的概率取决于网络中节点的度和节点自身的吸附性，称之为偏好依附。

定义7 聚集系数：描述的是网络中一节点与邻居节点之间的关系，即该节点在网络中的聚集程度，数学表达式为

(2)

定义8 定义网络中一个热节点与邻居节点组成的一个小规模网络为整个网络中的一个簇，这个热节点是这个簇的簇头CH[10]。与这些簇头都相连的节点称为汇聚节点。

定义9 鲁棒性：无标度网络在面对随机攻击时，具有很高的鲁棒性；在面对蓄意攻击时具有脆弱性。

1.2 网络拓扑模型

基于无标度的无线传感器网络由普通节点、热节点、汇聚节点通过边连接而成，它们之间通过边这个链接进行相互通信。热节点与普通节点形成一个个簇群，与普通节点相连的热节点又与上一层的热节点相连接，形成上一级的簇群。汇聚节点与最上层的热节点也形成一个簇群，这样，整个网络根据簇的等级分成好多层。

普通节点的作用是存储和收发信息，热节点的作用是接受来自普通节点的信息资源，将数据进行融合后转发给上一层热节点或汇聚节点，所以热节点需要更多稳定的能源，而且，位置相对固定。

在初始状态，网络中包含m0个孤立的节点[11]。

(1)增长特性：每一个时间段，有一个新的节点将会加入到网络中，并与网络中m个其他节点建立连接。

(2)择优特性：设节点自身吸附性为A，那么新增加的节点与网络中某节点i连接上的概率Πi，被假设为正比于节点i的度值与本身吸附性之和：

(3)

经过t个时间段后，得到N=t+m0个节点、mt条边的网络。

如图1所示，普通节点与最底层的热节点相连，最底层热节点与上一层热节点相连，最终到达汇聚节点。普通节点根据热节点的度和吸附性决定加入哪个簇，并通知该热节点。当热节点接收到所有加入信息后，会产生一个TDMA信号，并通知所有普通节点，普通节点将自己簇的簇头信息存储起来，这样，簇头和普通节点之间的通信就建立起来了。

图1 基于无标度特性的无线传感器网络拓扑结构

2 数值分析

对无线传感器网络节点度分布进行求解，这里采用连续域理论[11]的分析方法。假设一个新节点I在t时刻加入网络，此时网络中有t+m0个节点，网络中节点i的度ki是连续变量，那么，ki的连续变化率可得

(4)

t时刻，网络总的节点度为

(5)

将式(5)代入式(4)中，化简得

(6)

求解微分方程，并代入初始条件ki(ti)=m，计算化简得

(7)

(8)

(9)

该网络模型的节点度分布可由式(9)化简得

从表11中可以看出，西部矿业股份有限公司2013～2017年的资产负债率分别为57%、53%、56%、59%、60%，这五年间企业的资产负债率波动较小，近四年其资产负债率一直处于增长状态，表明企业在2014～2017年四年间长期偿债能力在逐年下降，但下降幅度不大，长期偿债能力较强。

(10)

由上面推导可见，该无线传感器网络节点度分布服从2(m+A)2(k+A)-3的幂律分布，可以证明该无线传感器网络具有无标度特性。

以上主要是证明无线传感器网络模型的度分布服从幂律分布与节点度负幂次方相关。无标度特性的提出，为研究无线传感器网络路由算法提供了新的思路和理论依据。

3 路由算法设计

3.1 SFRA路由

基于无标度的无线传感器网络路由(SFRA)算法的流程如图2所示。

图2 SFRA算法流程

算法的具体实现描述如下：

(1)假设现在节点C要向节点B转发数据，首先，先判断目标地址是否与之前的有相同的，如果有相同的，转向(2)，否则转向(3)；

(2)如果发送的数据内容也是相同的，那么系统将自动取消此次转发，如果发送内容不同，在目标地址相同的情况下，在路由表中搜索到路径，按照之前的发送路径转发数据；

(4)因为X=Y，所以数据是在簇内通信。确定目标地址，获取目标节点ID号，根据最短路径转发数据；

(5)判断是否存在最短路径，若存在，则按照最短路径转发数据，否则转向(6)；

(6)节点X把数据传送到节点B所在簇的簇首Y，本算法是把该无线传感器网络看成无向图，簇首X执行CDZ算法[12],计算出此次转发数据的最短路径，然后将计算出最短路径的路由表存储到簇首的缓存中，并且另外通知此最短路径中的节点[13]。

CDZ算法：将中心节点的一条实际存在的路径近似跨区域节点之间的最短路径。用Ci表示中心节点的集合(i表示节点个数),LCAsp：s和p的最近公共祖先。

①任意两个属于不同簇的节点s和p之间的距离：近似为这两个节点到各自簇中心节点的距离与这两个簇中心节点的距离之和：d(s,p)=d(s,Cs)+d(p,Cp)+d(Cs,Cp);

②属于同一簇的节点s和p之间的距离：d(s,p)=d(s,LCAsp)+d(p,LCAsp)

(7)要发送的数据包按照路由表的最短路径将数据从节点X发送到节点Y，然后簇首Y根据簇内最短路径将数据包转发给节点B，完成此次转发。转向(1)。

3.2 路由鲁棒性分析

鲁棒性是指网络中节点因为能量耗尽或受到攻击无用时，网络中的其他节点仍然能够保持正常通信，网络的结构和性能仍然能够维持基本稳定的性质。而路由鲁棒性[14]则是代表该路由算法在遇到一些自身或外在不可控因素时的适应能力。它是在节点能量、通信能力和网络拓扑等因素作用下的宏观效应。所以，路由鲁棒性是评价路由算法优劣的重要依据。

SFRA路由依赖于无标度的拓扑结构，这是因为该无线传感器网络模型具有无标度特性。前面已经介绍，无标度网络节点度分布服从幂律特性，所以该WSN面对随机攻击具有很强的鲁棒性[15]，但热节点面对蓄意攻击时又具有相对的脆弱性，所以热节点的失效必定会影响无线传感器网络的通信质量。

(1)普通节点的鲁棒性

当普通节点因能量耗尽或受到攻击失效时，该节点在失效前会发送消息通知该节点所在簇的热节点，那么热节点接收到消息后会根据簇中的情况更新路由表。可以看出，这种情况下对网络中数据的通信的可靠性影响很小。

(2)热节点的鲁棒性

热节点因为具有相当大的度，通信消耗的能量也大得多，所以一般电源和位置相对较固定，这也是设置网络拓扑的基本前提，一般热节点不会失效。但当热节点能量低于设定的阈值或受到蓄意攻击时，该热节点所在的整个簇的通信将会受到影响。一般在一定的时间间隔内，该簇的路由不通，那么认为该簇首失效，簇首失效之前会发送报文通知上一级的簇首节点，当网络中近半数簇首节点失效时，会通知sink节点，sink节点就会广播通知所有热节点，然后热节点再广播通知普通节点，执行SFRA路由算法，重新建立传输路由。

4 实验仿真分析

4.1 仿真环境

监测区域大小为200m×200m的正方形范围，共有无线传感器网络节点2000个，基站坐标为(0,0)，传感器节点的位置固定且已知，节点感知范围在30m。仿真实验的环境：CPU为Intel Core i3；内存2G；操作系统为Windows 7；仿真软件为Matlab。软件操作界面如图3所示。

图3 Matlab软件操作界面

4.2 算法性能指标

为了评价SFRA路由算法的性能，对无线传感器网络的拓扑结构和度分布特性、SFRA的数据传输、网络能耗和网络生命周期方面进行仿真验证。网络数据传输，即传感器节点在监测区域内进行数据包传送，网络节点通过最短路径算法进行传输数据，降低了节点的能耗和丢包率，所以，传输路径越短，跳数越少，时间就越短。该参数反映网络的传输能力，传输数据包越多，说明传输能力越强。网络能耗，即整个网络中节点的能量消耗情况。热节点的能源供给较为固定，而普通节点的能源相对较小，所以，数量众多的普通节点的能量消耗越小，网络生存时间越长，节能效果越好。网络生命周期就是网络的生存时间，即网络仍然存在最大连通子图，网络能够正常通信的时间越长，网络生存时间就越长。在仿真环境下，将本文提出的SFRA算法和LEACH算法在前面提到的几种性能方面进行比较。

4.3 仿真结果与分析

图4为无线传感器网络的拓扑结构图，该图的相关参数如下：初始网络节点个数为n0=5，每次引入新节点时新生成的边数m=5，网络规模N=130。实验后该网络图的聚类系数为0.15，平均路径长度为2.35。

图4 无线传感器网络拓扑结构图

图5为无线传感器网络的度分布情况。分别在网络规模为N=1500和N=2000的情况进行实验，由图5可以看出，传感器节点在双对数坐标下误差允许范围内服从幂律分布，与上一节进行的理论推导结果相一致，验证了其正确性。

图6为LEACH算法和SFRA算法的数据传输对比。由图6可以看出，SFRA算法的数据传输量比LEACH算法略低，这种情况促使网络节省能量。由于算法进行数据通信，必须通过簇首转发数据，而簇首的存储空间有限，所以单位时间内转发的数据也是有限的。SFRA算法有簇内和簇间通信，且运用最短路径算法，将最短路径存储到路由表中，使节点拥有记忆功能，在此通过此路径传输数据时会更快，所以传输数据量的速度也比LEACH算法快得多。

图5 无线传感器网络度分布图

图6 LEACH和SFRA的数据传输对比图

图7反映了全网在初始能耗为零的情况下，两种算法能量消耗情况。由图7可以看出网络节点能耗的趋势，在300时间段内，LEACH算法的节点能量几乎耗尽，而SFRA算法的节点能耗相对比较缓慢从而延长了网络的生存时间。起初两种算法的节点能耗差距不大，但随着时间的增加，SFRA的能耗小于LEACH。可以看出，SFRA相比于LEACH具有明显能耗优势。由于LEACH算法定期或节点受到攻击后重新竞选簇首，没有考虑簇首节点剩余能量的情况，所以当簇首选举更换较频繁时，随着时间的推移，会出现簇首能量耗尽快，更换簇首的周期变短的情况。而SFRA根据节点的度和自身的吸附性选择簇首，能够保证网络簇首节点死亡速度慢，增加了网络的可靠性，从而延长了整个网络的生命周期。

图7 LEACH和SFRA的网络能耗对比图

图8 LEACH和SFRA的存活节点数随时间的变化对比图

图8反映了在两种算法下网络中节点存活数量随时间的变化关系。从图8可以看出，SFRA存活节点数量在任何一个单位时间内大于LEACH，且LEACH的网络生命周期只有400个时间点，而SFRA的网络生命周期长达1000个时间点。因为LEACH在选举簇首时并没有考虑形成的簇首分布情况，当选举的簇首相对较集中时，该区域节点能量会消耗得很快，节点存活率就会降低，所以会出现节点急剧下降的情况。SFRA采用多跳的形式进行通信，网络吞吐量不大，所以节点存活时间较长，具有明显优势。

4.4 仿真评价

主要将SFRA算法与Flooding算法、LEACH算法和NEBBRP算法进行比较分析。

4.4.1 总体性能评价

Flooding算法是平面式路由，采用广播的方式进行选择路径，所以计算复杂度较低。LEACH算法、SFRA算法和NEBBRP算法是层次型路由，计算复杂度较高。但SFRA算法仅增加了吸附性这个因素，所以实现起来跟LEACH算法相似。表1为四种路由算法的总体性能评价。

表1 四种路由算法的总体性能评价

4.4.2 路由可靠性评价

对四种路由算法进行仿真，测试对数据感知的可靠性。对四种模型中sink节点所接收到的数据报文进行统计，从而判断可靠性能。SFRA算法采用信息融合技术，所以报文流量最低，所以可靠性最高。表2为四种路由算法的可靠性评价。

表2 四种路由算法的可靠性评价 %

4.4.3 网络节点度分布的评价

无标度网络节点度分布为幂律分布，幂指数为大于2的任意有理数，且是可调节的。无标度网络的通信效率最高。Flooding算法所形成网络的节点度分布是均匀分布，是规则网络，平均连接度是6。LEACH算法没有规定的度分布，且网络拓扑结构也是相对随机，平均连接度为4。表3为四种路由算法的网络节点度分布。

表3 四种路由算法的网络节点度分布

从以上几组仿真分析来看，SFRA算法在总体评价、路由可靠性和节点度分布三个方面均有优势。满足能量有限、动态拓扑性无线传感器网络路由的需求，并能够使传感节点更加长期有效地工作。

5 结束语

研究了一种基于无标度拓扑特性的无线传感器网络路由算法。将无标度理论应用到无线传感器网络的路由算法研究中，并针对无标度特殊的拓扑结构，采用CDZ算法计算数据传输最短路径。大量仿真实验表明，该算法在降低传感器网络能耗，延长网络生命周期等方面比传统无线传感器网络路由算法有较大优势，可应用于无线传感器网络中，并对无线传感器网络路由算法研究提供了理论依据，为以后的研究奠定了基础。

[1]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[2]申超杰.改进的BA复杂网络模型度分布的演化[D].天津：河北工业大学,2007.

[3]郭文忠,刘漳辉,王小溪,等.含权无标度网络中带自适应系数的混合路由算法[J].小型微型计算机系统,2014(3):448-452.

[4]田勇,唐祯安,喻言.能量均衡的室内无线传感器网络自适应分簇路由算法[J].电子与信息学报,2013,35(12):2992-2998.

[5]李智楠,朱磊,陈剑斌.一种改进的无标度网络模型[J].军事通信技术,2010(2):35-39.

[6]文宏,樊晓平,张会福,等.无标度网络上的动态局部路由策略设计[J].Computer Engineering and Applications,2014,50(20):10-14.

[7]文宏,樊晓平,张会福,等.无标度网络局部路由算法优化与设计[J].湖南大学学报:自然科学版,2014,41(10):122-128.

[8]韩涛.基于无标度理论的 WSNs 拓扑控制算法研究[D].秦皇岛：燕山大学,2014.

[9]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社有限公司,2006.

[10]Xu J,Wang X F.Cascading failures in scale-free coupled map lattices[J].Physica A:Statistical Mechanics and its Applications,2005,349(3):685-692.

[11]苏威积,赵海,张文波,等.基于嵌入式技术的传感器网络无尺度路由算法[J].计算机工程,2006,32(14):87-88.

[12]唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2279-2290.

[13]Tang F,You I,Guo S,et al.A chain-cluster based routing algorithm for wireless sensor networks[J].Journal of intelligent manufacturing,2012,23(4):1305-1313.

[14]Ye F,Zhong G,Lu S,et al.A robust data delivery protocol for large scale sensor networks[C]//Information Processing in Sensor Networks.Springer Berlin Heidelberg,2003:658-673.

[15]Kollios G,Byers J W,Considine J,et al.Robust Aggregation in Sensor Networks[J].IEEE Data Eng.Bull.,2005,28(1):26-32.

(责任编辑：马金发)

Research on the Scale-free WSNs Routing Algorithm

LIU Lili,XU Ye

(Shenyang Ligong University,Shenyang 110159,China)

Based on the topological characteristics of scale-free,a kind of wireless sensor network routing algorithm is put forward.From the perspective of the average degree distribution and the adsorption of nodes in this routing algorithm,multipath designing principle is adopted,which builds a scale-free network model.And wireless sensor network topology is established based on the model,nodes with information fusion ability at the same time,which improves data reliability redundancy and reduces network throughput.So network energy becomes balanced,which prolongs network life cycle.Simulation results show that the routing algorithm has more significant effect on the node degree distribution,reliability and overall performance evaluation in comparison with some other routing algorithms such as Flooding,LEACH and NBEERP.

scale-free;wireless sensor network;routing algorithm;network life cycle

2016-03-24

国家自然科学基金面上资助项目(61373159)；辽宁省高等学校优秀人才支持计划资助项目(LJQ2015095)；沈阳市科技应用基

础研究计划资助项目(F13-316-1-22)；沈阳理工大学重点学科、重点实验室开放基金资助项目(4771004kfs18)

刘莉莉(1992—)，女，硕士研究生；通讯作者：徐野(1976—)，男，教授，博士，研究方向：复杂互联系统与大规模网络。

1003-1251(2016)06-0059-07

TP393

A