基于小世界模型的无线传感器网络层次型路由算法

韦世红，唐起超

(重庆邮电大学 移动通信技术重点实验室，重庆 400065)(*通信作者电子邮箱2075721094@qq.com)

基于小世界模型的无线传感器网络层次型路由算法

韦世红，唐起超*

(重庆邮电大学 移动通信技术重点实验室，重庆 400065)(*通信作者电子邮箱2075721094@qq.com)

层次型路由算法是无线传感器网络研究的热点领域。针对传感器节点能量受限问题，提出一种基于小世界模型的无线传感器网络层次型路由算法(HASWNM)。通过添加高性能节点以及在簇头间添加捷径的方法，使得无线传感器网络(WSN)体现出小世界网络特性。由于能量消耗主要集中在数据发送阶段，因此该算法在簇间中继选择时考虑了簇头自身的能量问题。此外，根据簇头节点距离基站的位置远近，确定不同的自适应搜索区域。实验结果证明，当高性能节点个数为100时，网络中可以呈现出小世界特性。与CSWN、TSWN、DASM相比，该算法第一个节点的死亡轮数分别延迟了6%，6%，29%，每一轮网络中的平均能量消耗分别减少了5%，12%，17%。因此，该算法构造的无线传感器网络具有小世界特性，并且能量消耗较低。

无线传感器网络；聚类系数；平均路径长度；能量损耗

1 小世界网络模型

小世界网络的本质特征是具有小的平均路径长度和大的聚类系数[1]，将复杂网络的小世界现象引入无线传感器网络(Wireless Sensor Network, WSN)的研究，对分析WSN的拓扑结构、发现WSN中隐藏的规律以及预测WSN的行为具有十分重要的理论意义。

1)平均路径长度：平均路径长度定义为所有节点间通信距离的平均值。计算公式如式(1)所示：

(1)

其中：N表示的是传感器节点的数量，dij表示的是节点i和节点j之间的通信距离实际存在的边条数。

对小世界WSN平均路径长度的计算，目前还没有非常精确的解析表达式，如果小世界WSN通过“随机化重连”构成，则平均路径长度如式(2)所示：

(2)

其中：N表示的是传感器节点个数，K表示的是节点度数，p为重连概率，f(x)表示的是普适标度函数。

普适标度函数f(x)基于平均场方法给出：

(3)

当节点的平均度固定时，平均路径长度的增加速度与N的对数成正比。表明基于小世界的无线传感器网络其平均路径长度较小，且对于随机故障具有较强的鲁棒性。

2).聚类系数C：聚类系数描述了节点i与其直接相连的邻居节点的连接关系，如式(4)所示：

Ci=3NΔ(i)/N3(i)

(4)

其中：NΔ(i)表示的是该网络中包含节点i的三角形总数，N3(i)表示包含节点i的三元组总数。

对部分聚类系数较小的边进行一些必要的选择性删改，可提高网络整体的平均聚类系数，从而达到简化拓扑结构、优化路径选择的效果。

广大学者提出了很多无线传感器网络小世界特性的构造方法。文献[2]提出了基于NW(Newman-Watts)小世界WSN的构造方法，但是网络的抗毁性较差，性能低，造价昂贵。文献[3]提出了基于汇聚节点(sink node)构造小世界WSN，抗毁性较差，适用于小规模的网络。文献[4]提出了基于拓扑优化的小世界WSN构造，该算法形成了一种静态拓扑，抗毁性适中，网络规模适中。

针对现有算法的不足以及经验，本文提出了一种基于小世界特性的无线传感网层次型路由算法(Hierarchical routing Algorithm for wireless sensor networks based on Small World Network Model, HASWNM)，通过添加高性能节点以及在簇头间添加捷径的方法，使得无线传感器网络体现出小世界特性。该算法在簇间中继选择时候考虑了簇头自身的能量问题，达到了很好的节能效果。

2 本文算法

2.1 系统模型

1)N个传感器节点随机部署在M×M的正方形监控区域内，传感器节点分为普通节点和高性能节点。节点通过ID(Identification)进行标识，并且存储、计算能量受限。

2)传感器节点一旦被部署，则一直处于静止状态。

3)sink节点存储、计算能量不受限，并且sink节点是固定的。

4)假设节点i的通信半径为Rc(i)，节点j的通信半径为Rc(j)，节点i和节点j之间的距离为dij，那么节点i和节j能够直接通信的充要条件[5]是Rc(i)≤dij∧Rc(j)≤dij。

2.2 基本概念

定义1 两个高性能节点之间的链接成为捷径[6]。

定义2 高性能节点间的链接概率用p表示。

定义3 假设普通节点的通信半径为RL，高性能节点的通信半径为RH，在实验的过程中保证RH≫RL。

2.3 算法描述

算法是以轮数为单位，每一轮主要分为簇的划分以及簇头的选择，簇头的选择根据数据传输的可靠性；选择出来的簇头节点同时进行链路构建，包括候选捷径端点的确定以及捷径端点的确定；最后完成数据的通信过程。具体的流程如图1所示。

图1 算法流程

1)对监控区域进行随机撒点，主要分为两类传感器节点，具有高能量的传感器节点(High-energy sensor node, H-sensor)和具有低能量的传感器节点(Low-energy sensor node, L-sensor)。其中，高性能节点的个数应该大于等于簇头节点的数目，其余的是低能量的普通节点，这样做的好处就是尽可能地保证每个簇内都具有高性能节点。拥有高能量的传感器节点具有较大的通信半径RH，拥有低能量的传感器节点具有较小的通信半径RL。

2)簇的建立阶段分为邻居发现阶段、控制数据广播以及网络配置。在邻居发现阶段，所有的传感器节点广播一个带有自己ID号的hello包，收到hello包的传感器节点会更新自己的邻居表和接收信号强度(Receive Signal Strength Indicator, RSSI)。控制数据广播，该算法使用泛洪的方法传输控制数据到基站，每个传感器节点的控制信息包括自身的ID号、剩余能量和它的邻居表数据。中继节点接收到数据包会继续广播直到数据包传输到基站为止。网络配置阶段，当基站收到网络中所有的传感器节点的控制包时，基站开始配置网络。配置广播，当基站完成网络配置，以泛洪的方式向所有的传感器节点广播网络配置，对子区域进行划分。每个传感器节点根据接收的消息确定要加入的簇。每个子区域的传感器节点构建单链路，并根据成簇的可靠性进行簇头节点的选举。

仿真的过程中，位于监控区域左下角位置的汇聚节点，根据距离汇聚节点的距离将监控区域划分为不同的环形等级，然后将每一层的面积平均化，得到每个簇的大小区域。规定距离基站越近的环形等级越低，分别为0,1…,i，如图2所示。环形等级level计算公式为：

level=i,i*d0≤r≤(i+1)*d0

(5)

其中：r表示的是环形的半径大小，d0表示的是自由空间传播模型和多径衰减模型的临界距离，i表示的是环形等级的数值大小。

图2 环形等级示意图

图3 簇内数据融合的示意图

如图3所示，在一个簇内有N个传感器节点，按照经典的PEGASIS(Power-Efficient Gathering in Sensor Information System)算法形成单链路，如果簇头节点C4左边链路有m个传感器节点，那么C4右边链路就有N-1-m个传感器节点。任何复杂的系统都可以通过并联与串联模块的组合来描述[7]。如图4可靠性模型(Reliability Block Diagram, RBD)所示，整个簇的数据传输可靠性Rcluster表示为：

(6)

其中：RCH表示的是簇头节点的数据可靠性，RCMi表示的是普通传感器节点的数据可靠性。

节点i的数据可靠性定义为：

RCMi=Ere(i)/Einit(i)

(7)

其中：Ere(i)表示的是节点i的剩余能量，Einit(i)表示的是节点i的初始能量。

图4 RBD模型示意图

3)确定簇头节点i的自适应搜索区域。

(8)

其中：dmax表示的是头节点集合中距离基站的最远距离，dis表示的是当前的簇头节点距离基站的距离，dmin表示的是簇头节点集合中距离基站的最近距离，θinit表示的是距离基站最远的簇头的搜索角度。

图5 节点i的自适应搜索区域

本算法通过搜索角度控制簇头的搜索区域。距离基站最远的簇头节点的搜索区域为θinit，其余簇头节点的搜索角度随着dis的变化而变化，距离基站越近，簇头节点的搜索区域越大，则可以作为下一跳的节点的选择性就越多，从而避免个别节点点介数过高的情况，一定程度上缓解了“热点”问题的产生，延长了网络寿命。

根据文献[11]，无线传感器网络可以方便地表述为图G=〈V,E〉，其中，V代表图中顶点的集合，E代表图中边的集合，用Gd(a,b)表示节点a和节点b的最短距离，a∈V∧b∈V，σab代表节点a和节点b之间的最短路径数目，a∈V∧b∈V，σab(z)代表节点a到节点b经过节点z的路径数目，z∈V。节点z的点介数BC(z)定义为：

(9)

4)候选捷径端点的确定。

如果该簇头在当前θ的搜索区域范围内没有发现候选捷径端点的存在，那么该簇头节点会继续扩大搜索范围，直至找到候选捷径端点。如果当θ达到360°时，该簇头仍然没有找到候选捷径端点，则选择距离该节点最近的簇头节点作为下一跳节点。如果该节点找不到离自己最近的簇头节点，那么会选择邻近区域的普通节点作为中继节点进行数据传输。

5)捷径端点的确定。

捷径端点的确定如图6流程所示，由于在部署传感器节点的时候采取的是随机撒点的方式，所以会导致选择出来的簇头节点不一定是H-sensor节点。如果该簇头节点i是L-sensor，则节点i选取离节点j距离最近的节点作为节点j的下一跳节点。如果是该簇头节点i是H-sensor节点，比较该节点的本轮剩余能量Ei和网络中簇头节点的平均剩余能量Eave，Eave的表达式如式(10)所示:

(10)

其中：m簇头节点的数目，Eres(i)表示的是节点i当前的剩余能量。

如果节点Eres(i)>Eave，则节点i选择距离基站最近的候选捷径端点作为下一跳节点。如果Eres(i)

图6 捷径端点确定的流程

图7是 HASWNM算法生成的拓扑结构图。传感器节点主要分为4类：当选为簇头的高性能节点；作为簇成员的高性能节点；当选为簇头的低性能节点；作为簇成员的低性能节点。簇间的通信采用了大量的捷径链路。每个簇头在中继节点的选择方法上呈现出差异性。

图7 算法拓扑结构示意图

6)数据传输阶段。

当基站接收到所有簇头传送过来的数据包时，即完成了一轮的通信。进入下一轮的数据采集。

2.4 算法复杂度分析

假设监控区域内有N个传感器节点，其中有m个簇头，那么普通节点的个数为N-m，每个簇内的节点个数平均为N/m。簇的建立阶段分为邻居发现阶段、控制数据广播以及网络配置。在邻居发现阶段，所有的传感器节点广播一个带有自己ID号的hello包，共有N个数据包。在控制数据广播阶段，每个传感器节点的控制信息包括自身的ID号、剩余能量和它的邻居表数据通过泛洪的方式传送给基站，共有N个数据包。基站收到所有的数据包信息之后，在网络配置阶段，会以泛洪的方式发送一个数据包，使得网络节点了解网络整体的情况。

3 仿真结果与分析

3.1 实验场景设置

根据参考文献[3]，在实验仿真时，簇数K取值按照K=πR2/r2。其中，R表示的是高性能节点的通信半径，r表示的是低性能节点的通信半径。

实验验证借助Matlab平台，仿真实验的具体参数设置如表1所示。

表1 实验参数设置

仿真的大致流程为：

1)随机部署1 000个传感器节点，初始化网络，每个网络节点坐标为(xi,yi)，ID号为idi，并进行簇的划分。每个簇内按照数据传输的可靠性选取出簇头节点，并对簇头节点打上标记flag。

3)当基站收到了所有簇头的数据包后，一轮传输结束，进入到下一轮数据收集的准备阶段。

3.2 仿真结果分析

实验1 能量消耗和高性能节点数目关系实验。

从图8中可以看出，HASWNM只是对簇头节点寻找相应的捷径端点，当网络中的高性能节点的数目不是很多的时候，由于高性能节点分布不均匀，可能会导致能量消耗比较快一点。但是随着高性能传感器节点个数的增加，基本能够保持每个簇内都有高性能节点，这样导致能量消耗比较低，所以能耗基本呈现出一个下降的趋势。DASM(Directed Angulation towards the Sink node Model)中，高性能节点在固定的搜索区域内搜索捷径端点，TSWN(Tree-based Small World Network)将自适应搜索区域内的所有高性能节点加入到捷径的创建中，当有多个高性能节点时，随机选择加入捷径，因此，故在初始时，两种模型的高性能节点利用率相对CSWN(topology Control based on Small World Network)、HASWNM高，其能耗会更加均衡，网络能量消耗相对较低。

图8 能量消耗和高性能节点数目的关系

实验2 网络生命周期和高性能节点数目关系实验。

从图9可以看出，网络生命周期与能量消耗呈现出一定的关系，在高性能节点个数不是很多的时候，相比别的算法，HASWNM算法能耗要更高一些，导致其网络生命周期比较短，随着高性能节点个数的增加，HASWNM在网络生命周期方面表现出一定的优越性。

实验3 小世界特性和高性能节点数目关系实验。

本文定义C(0)表示的是仅由普通节点构成的网络聚类系数大小，C(H)表示的是由H个高性能节点以及一些普通的传感器节点构成的网络聚类系数大小，L(0)表示的是仅由普通节点构成的网络平均路径长度大小，L(H)表示的是由H个高性能节点以及一些普通的传感器节点构成的网络平均路径长度大小。

从图10中可以看出，随着高性能节点个数的增加，L(H)/L(0)呈下降的趋势，当高性能的节点个数达到100时，平均路径长度减少了72%左右。当高性能节点个数达到100以后，L(H)/L(0)基本维持不变，C(H)/C(0)也基本处于不变的状态。采用本实验的参数设置时，最佳的高性能节点个数为100个时，使得网络的平均路径长度最小。

图9 网络生命周期和高性能节点数目的关系

图10 聚类系数、平均路径长度与高性能节点数目的关系

实验4 网络剩余能量和仿真轮数的关系。

当实验仿真时，高性能的节点个数设置为100，那么低性能节点的个数就为900个。根据每轮能量消耗，可以估算出不同算法的最大工作轮数不超过700，因此，算法最大仿真周期设置为700轮。

图11表示的节点总的剩余能量和仿真轮数的关系。通过前面图8分析可知，高性能节点的个数为100时，HASWNM算法每轮的平均能耗是最低的。通过图11可以直观地看出，节点总的剩余能量是最多的，其次是CSWN、TSWN，最差的是DASM算法。实验8和实验11的结果具有很强的关联性。

实验5 不同算法网络平均周期比较实验。

图12表示的是不同算法的网络平均生命周期。从图中可以看出，HASWNM算法在第一个节点死亡、10%节点死亡以及50%节点死亡时，都具有最大的仿真轮数。第一个节点死亡时，HASWNM算法相比较CSWN延迟了6%，相比较TSWN延迟了6%，相比较DASM延迟了29%。10%节点死亡时，HASWNM算法相比较CSWN延迟了18%，相比较TSWN延迟了30%，相比较DASM延迟了63%。50%节点死亡时，HASWNM算法相比较CSWN延迟了19%，相比较TSWN延迟了23%，相比较DASM延迟了32%。全部节点死亡时，HASWNM算法相比较CSWN延迟了4%，相比较TSWN延迟了10%，相比较DASM延迟了19%。WSN生命周期的长短主要取决于网络的能耗情况，通过图8知道，由于节点搜索区域以及捷径端点的选择规则的不同，导致当高性能节点数为100的时候，每一轮的能量消耗从小到大依次为：HASWNM、CSWN、TSWN、DASM。

图11 节点总的剩余能量和仿真轮数的关系

图12 不同算法的网络平均生命周期

4 结语

本文提出了一种基于小世界网络模型的无线传感器网络层次型路由算法，小世界模型的构造是通过添加高性能节点以及在选择出来的簇头节点间添加捷径的方法实现的。由于无线传感器的能耗主要集中在数据的发送阶段，所以只有能量高于所有簇头平均能量的簇头节点，才会选择候选捷径端点中距离基站最近的簇头作为下一跳节点，否则，会随机选择一个候选捷径端点作为下一跳节点。这样做的好处是节省了一定的能量，避免了个别节点能量消耗过快。簇头根据距离基站的位置，控制搜索区域的角度，避免了基站周围个别节点点介数过高的问题，有效地延长了网络的生命周期。通过仿真验证，基于小世界网络模型的无线传感器网络层次型算法使得网络具有大的聚类系数和小的平均路径长度，同时网络能耗相比较也比较低。本文提出的算法主要考虑节点的能耗，后续可以考虑从覆盖率、QoS以及有利于算法的扩展性等因素入手，展开进一步研究。

References)

[1] GITTERMAN M. Small-world phenomena in physics: the Ising model [J]. Journal of Physics A: Mathematical and General, 2000, 33(47): 8373-8381.

[2] HELMY A. Small worlds in wireless networks [J]. IEEE Communications Letters, 2003, 7(10): 490-492.

[3] 熊书明,胡永娣. 基于小世界概念的异构传感器网络拓扑控制[J].计算机工程与设计,2016,37(11):2869-2875.(XIONG S M, HU Y D. Topology control method for heterogeneous wireless sensor network based on small world concepts [J]. Computer Engineering and Design, 2016, 37(11): 2869-2875.)

[4] 叶秀彩,许力,林力伟.基于小世界现象的无线传感器网络拓扑优化[J].福建师范大学学报(自然科学版),2008,24(5):37-40.(YE X C, XU L, LIN L W. Topology optimization based on small-world phenomenon in wireless sensor networks [J]. Journal of Fujian Normal University (Natural Science Edition), 2008, 24(5): 37-40.)

[5] 马晨明.面向节能和容错的异构无线传感器网络分布式拓扑控制算法研究[D].杭州:浙江工业大学,2015.(MA C M. Research on distribution topology control algorithm for energy saving and fault tolerant in heterogeneous wireless sensor networks [D]. Hangzhou: Zhejiang University of Technology, 2015.)

[6] 任秀丽,董姜颖,薜建生.基于小世界的无线传感器网络的路由算法[J].计算机应用,2010,30(9):2497-2500.(REN X L, DONG J Y, XUE J S. Small world routing algorithm of wireless sensor network [J]. Journal of Computer Applications, 2010, 30(9): 2497-2500.)

[7] 周祖德,胡鹏,李方敏,等.无线传感器网络分簇通信协议的可靠性方案[J].通信学报,2008,29(5):114-121.(ZHOU Z D, HU P, LI F M, et al. Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J]. Journal on Communication, 2008, 29(5): 114-121.)

[8] GUIDONI D L, MINI R A F, LOUREIRO A A F. On the design of resilient heterogeneous wireless sensor networks based on small world concepts [J]. Computer Networks, 2010, 54(8): 1266-1281.

[9] 张婧.无线传感器网络能耗平衡策略研究[D].长春:吉林大学,2015.(ZHANG J. Research on energy-balanced strategy in wireless sensor networks [D]. Changchun: Jilin University, 2015.)

[10] 谢启辉,黄杰.基于动态搜索区域的无线传感器网络小世界特性构建方案[J].东南大学学报(自然科学版),2012,42(4):593-598.(XIE Q H, HUANG J. A scheme of constructing small world network in WSNs based on dynamically searching zone [J]. Journal of Southeast University (Natural Science Edition), 2012, 42(4): 593-598.)

[11] ASIF W, QURESHI H K, RAJARAJAN M. Variable Rate Adaptive Modulation (VRAM) for introducing small-world model into WSNs [C]// Proceedings of the 2013 47th Annual Conference on Information Sciences and Systems. Piscataway, NJ: IEEE, 2013: 1-6.

Hierarchicalroutingalgorithmforwirelesssensornetworksbasedonsmallworldmodel

WEI Shihong, TANG Qichao*

(KeyLabofMobileCommunicationsTechnology,ChongqingUniversityofPostsandCommunications,Chongqing400065,China)

Hierarchical routing algorithm is now a hotspot in the field of wireless sensor network. Aiming at the problem that the energy of sensor nodes are limited, a hierarchical routing algorithm for wireless sensor networks based on small world model (HASWNM) was proposed. The Wireless Sensor Network (WSN) could reflect characteristics of the small world by adding nodes with high performance as well as shortcuts among cluster heads. As the energy consumption was mainly concentrated in the data transmission phase, the energy of the cluster head was taken into account while choosing the relay node between clusters. Besides, the different adaptive search area was determined according to the distance between the cluster head and the base station. The experimental results showed that the network can show the characteristics of small world when the number of high-performance nodes reached 100, and compared to the algorithms of CSWN (topology Control based on Small World Network), TSWN (Tree-based Small World Network), DASM (Directed Angulation towards the Sink node Model), the number of death rounds of the first node was delayed by 6%，6%，29% separately, and the average energy consumption of the network per round was reduced by 5%，12%，17% respectively. Thus the wireless sensor network constructed by the proposed algorithm has the characteristics of small world and low energy consumption.

Wireless Sensor Network (WSN); clustering coefficient; average path length; energy consumption

2017- 03- 20;

2017- 04- 11。

长江学者和创新团队发展计划项目(IRT1299)；重庆市科委项目(CSTC2012jjA40044, CSTC2013yykfA40010)。

韦世红(1970—)，女，重庆人，副教授，博士，主要研究方向：无线传感器网络拓扑控制与路由算法、MIMO信道估计； 唐起超(1989—)，男，山东威海人，硕士研究生，主要研究方向：无线传感器网络路由算法、复杂网络模型。

1001- 9081(2017)09- 2457- 06

10.11772/j.issn.1001- 9081.2017.09.2457

TN929.5

A

现实生活中许许多多的网络都具有复杂网络的性质，如社会关系中的科学协作网、朋友关系网；生态系统中的蛋白质网、神经元网络；技术网络中的Internet以及信息网络中的WWW等。作为复杂网络重要特性之一的小世界特性，是复杂网络最普遍和最重要的拓扑结构属性之一，小世界现象普遍存在于大量真实网络中，如计算机互联网、科学家合作网、产品生产关系网和电力网络等。

This work is partially supported by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), the Project of Chongqing Science and Technology Commission (CSTC2012jjA40044, CSTC2013yykfA40010).

WEIShihong, born in 1970, Ph. D., associate professor. Her research interests include topology control and routing algorithm of wireless sensor networks, channel estimation of MIMO system.

TANGQichao, born in 1989, M. S. candidate. His research interests include routing algorithm of wireless sensor networks, complex network model.