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

0 引 言

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

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

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

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

1.1 网络模型设计

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

图1 加入超级节点后的传感器网络

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

1.2 小世界效应分析

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

当H（Ni，S）≥ H' （Ni，S）时，节点选择经超级节点发送数据。 反之，当 H（Nj，S）<H'（Nj，S），即普通节点 Nj 离汇聚节点较 近时，节点 Nj 经其他普通节点无线多跳到达汇聚节点。

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

所以，在同构 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 网络的交叉点上，针对无 线传感器网络随机分布节点的情况，增设超级节点的节能问题 还须进一步讨论。