基于小世界特征的无线传感器网络拓扑优化

罗小娟　黄如

摘 要：针对无线传感器网络存在的能量消耗问题，在基于复杂网络小世界特征基础上，通过在无线传感器网络中增加超级节点，并在超级节点之间建立超级链路，提出一种具有小世界特征效应的无线网络模型。从复杂网络的视角计算分析了在传感器网络中部署超级节点对网络节点能量效率的影响。仿真研究结果显示，在传感器网络中适当增设少量超级节点，可大幅减少网络的平均路径长度，明显改善网络传输性能，同时极大地提高了网络节点的节能比率。

关键词：无线传感器网络；复杂网络；拓扑优化；小世界特征

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2018）03-00-03

0 引 言

经典的复杂网络理论已经证明： “小世界效应”在社会关系网络中广泛存在[1，2]。小世界现象的本质特征是具有小的平均路径长度和大的集聚系数[3，4]。小世界特征普遍存在于如计算机互联网、科学家合作网、社会关系网等现实网络中，同时小世界理论还广泛存在于电力网络、神经网络等系统中[5，6]。真实的网络可以分为关系网络与空间网络两大类。在关系网络（Relation Network）的拓扑结构中，节点之间的连接与节点距离和位置无关，节点之间的距离以跳数来计算；空间网络（Spatial Network）节点之间的连接与节点之间的距离和位置紧密相关。传统的复杂网络研究通常都将社会关系或者技术网络抽象为关系网络，属于关系图的范畴；无线Ad-Hoc网络与无线传感器网络由于其传输半径的限制，是空间网络，属于空间图的范畴。空间网络的拓扑结构与连通性及传输半径紧密相关。

小世界特征是指网络较小的平均路径长度和大的聚类系数，无线传感网络中节点之间采用无线多跳方式传输数据，引入小世界特征可以降低网络系统的通信开销，并增强网络的容错性，从而延长整个系统的生存时间[7-11]。张[12]等选择性地删除一些边，基于汇聚节点建立捷径，交替进行，直到两个小世界特征达到最优。周[13]等基于小世界与能效提出了一种容迟网络路由算法。Nardis[14]等设计了一种自适应选举簇头，簇头之间动态建立捷径，生成具有小世界特征的网络拓扑结构，实验结果显示了该网络的优良性能。

根据传感网应用环境的不同，部署方式可以分为确定性部署和随机部署两类。在监测范围小且人类方便到达的应用环境如车间、医院、商场中，可以预先确定传感器节点的位置并手工部署在确定位置上。但当网络规模较大或在环境恶劣危险的场合应用时，如湖泊、沼泽、沙漠、战场、疫区等，通常采用随机播撒方式。本文在无线传感网中引入复杂网络中的小世界特征，结合确定性部署和随机部署方式，在随机部署的基础上，确定部署少量具有更高能量、更强数据处理能力的超级节点，在超级节点和汇聚节点之间建立超级链路形成直接通信的可靠捷径，从而构建基于无线传感器网络小世界效应的网络模型。

1 小世界效应的传感器网络模型

1.1 网络模型设计

在无线传感网络应用中，通常传感器节点一旦部署，位置便相对固定，且需长期运行监测如森林火灾检测的应用场景，本文采用的网络模型为N个传感器节点均匀部署在一个X×Y的长方形区域Z内，每个节点均匀分布在交叉点上，为了避免网络拓撲结构经常改变，假定所有传感器节点一旦部署位置固定，且这些节点是同构的，具有相同的能量和相同的通信半径，并知道自己的位置信息，位置采用平面坐标（x，y）标记，其中0≤x≤X-1，0≤y≤Y-1。网络拓扑形成平面Mesh结构，如图1所示。

传感器节点只与临近节点即与自己垂直和水平方向的节点传送和接收数据，汇聚节点可以部署于区域范围内的任何位置，传感器节点以一定的速率发送数据传到汇聚节点，汇聚节点可以与其他有线网络或者无线网络连接，最后传送到用户终端。传感器节点也可采用贪婪路由策略，即数据经最短距离传送到汇聚节点。

1.2 小世界效应分析

假设已知普通节点Ni的平面坐标位置为（xi，yi），普通节点Nj位于（xj，yj），汇聚节点Sink的平面坐标位置为（xs，ys）。先计算普通节点Ni和Nj不经过超级节点把数据发送给汇聚节点的最短跳数距离为：

如图1所示，如果普通节点Ni远离汇聚节点，Ni先以无线多跳的方式将数据发送给最近的超级节点，超级节点通过超级链路直接传送给汇聚节点。此时，Ni节点把数据发送给最近超级节点的最短跳数为：

当H（Ni， S）≥H' （Ni， S）时，节点选择经超级节点发送数据。反之，当H（Nj，S）

小世界网络具有较小的特征路径长度。在一般复杂网络中，特征路径长度指网络中任意两点之间最短路径的平均值。在无线传感网络中，所有传感器节点感知的数据均向汇聚节点汇集，传送数据具有明确的方向性，数据流向是一种“多对一”的集中汇聚模式，在本节仿真分析中给汇聚节点设定了特定的地理位置，所以平均路径长度需要根据传感器网络的特殊性进行修正。这里的平均路径长度APL指为传感网络中所有节点发送数据到达汇聚节点所经过的通信跳数平均值，表示为：

其中：n为网络中传感器节点的个数；Hi-sink表示节点i到超级节点或汇聚节点的通信跳数距离，即为传感器网络中普通节点i到汇聚节点通信的所有路径中最短传输路径的跳数，表示为：

假设在同构网络中加入μ个超级节点后，普通节点通过超级节点传送数据的概率为ρi，μ，在一个大规模的无线传感器网络应用中，ρi，μ随着μ值的增加而增大，则网络节点到汇聚节点的路径长度平均约为：

在初始的同构网络中，没有增设超级节点时，网络节点到汇聚节点的平均路径长度为：

所以，在同构Mesh网络与通过增设μ个超级节点而构造生成的超级链路网络之间，网络节点到超级节点或汇聚节点的平均路径长度的比率定义为平均路径长度的变化率，记为：

在传感器网络中，节点的能量消耗主要用于数据处理与传输，所以网络能耗与数据传输的平均路径长度密切相关，定义能量节省比率为：

能量节省比率越大，表示传感器网络的能量效率越高。

对于增设了超级节点后的无线传感器网络，超级节点周围的普通节点通过超级节点发送数据，网络拓扑发生相应变化，网络出现聚类特性，可认为具有较高的聚类系数。

1.3 仿真结果

仿真实验采用规模为20×20的Mesh网络，普通节点部署在Mesh网络中的交叉点上，汇聚节点分别部署在（0，0）和网络的中心（10，10）位置，假设超级节点同样均匀部署在监测环境中，如图2所示。

平均路径长度（APL）与超级节点的关系如图3所示，展示了网络中超级节点数和平均路径长度APL（μ）之间的关系。图中显示了添加网络中的部分超级节点，超级节点的网络节点的平均路径长度迅速下降，尤其在汇聚节点处（0，0）比（10，10）提高更为显著，当汇聚节点处在（0，0）的位置时，超级节点增加1～6个，平均路径长度由10降至4。然而，当超级节点继续增加时，平均路径长度下降非常缓慢。结果表明，在同构网络中加入少量超级节点，平均路径长度迅速下降，网络具有小世界特征。

平均路径长度变化率APLR（μ）与超级节点数的关系如图4所示。在两个模拟环境中都添加了6个超级节点，网络的平均路径长度减少约至45%。由曲线可知，若继续增加超级节点的数量，路径长度将不再显著减少。因此，合理增加超级节点对网络拓扑结构没有太大影响，但可以大大减少数据传输的网络路径长度，进一步体现了小世界复杂网络的特点。

网络节能比率与增设超级节点的关系如图5所示。当增加第1～6条超级链路时，网络节能比率约50%，但增加更多超级链路后节能效果不明显。且当汇聚节点位于（0，0）时，比位于（10，10） 时节能效果有明显提高。

2 结 语

本文首先分析了小世界效应在无线传感器网络中的应用和研究。在无线传感网络中，引入超级节点和超级链路，提出了小世界特征的网络模型，仿真分析了超级节点数对网络平均路径长度、路径长度变化率和网络节能率的影响，增加少量超级节点可以减少网络数据传输延迟，提高网络的能量效率。本文考虑的是节点均匀分布在Mesh网络的交叉点上，针对无线传感器网络随机分布节点的情况，增设超级节点的节能问题还须进一步讨论。

参考文献

[1] MILGRAM S. The small world problem. Psychology Today[Z]. 1967： 60-67.

[2] KLEINBERG J. Navigation in a small world[J].Nature， 2000： 845-845.

[3] WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world networks[J].Nature，1998： 440-442.

[4] NEWMAN M E J，WATTS D J. Renormalization group analysis of the small-world network mode[J].Physics Letters A，1999， 263（3-4）： 341-346.

[5] Ye X，Xu L，Lin L. Small-word model based topology optimization in wireless Sensor networks[C].Proceeding of the IEEE international conference on information science and engineering，2008.

[6] HUI K Y K， LUI J C S， YAU D K Y. Small-world overlay P2P networks：construction， management and handling of dynamic flash crowds[J].Computer networks，2006， 50（15）： 2727-2746 .

[7] ZHENG P， TANG W， ZHANG J. A simple method for designing efficient small-world neural networks[J].Neural networks，2010， 23（2）： 155-159.

[8] HELMY A. Small worlds in wireless networks[J].IEEE communications letters， 2003， 7（10）：490 -492.

[9] SHARMA G，MAZUMDAR R. A case for hybrid sensor networks[J].IEEE/ACM transactions on network，2008，16（5）： 1121-1132.

[10] GUIDONI D L， MINI R A，LOUREIRO A A. On the design of resilient heterogeneous wireless sensor networks based on small world concepts[J]. Computer networks，2010， 54（8）： 1266-1281.

[11] KOMURO N，MOTEGI S，SANADA K，et al. Small-World-Network model based routing method for wireless sensor networks[J].IEICE transactions of commununications，2016（11） ： 2315-2322.

[12]張静莲，刘三阳，张朝辉.具有小世界现象的无线传感器网络构造方法[J].信号处理，2017，33（3）：417-421.

[13]周朝荣，徐小琼，杨柳，等.基于小世界与能效的容迟网络路由算法[J].电子科技大学学报，2016，45（1）：129-134.

[14]熊书明，胡永娣.基于小世界概念的异构传感器网络拓扑控制[J].计算机工程与设计，2016，37（11）：2869-2875.