一种高效节能的小世界无线传感器网络*

柳 艳，肖 旻，王纪军，陈咏秋，徐明生

（1.江苏电力信息技术有限公司，南京 210000；2.南京工程学院数理部，南京 211167；3.南京工程学院计算机工程学院，南京 211167）

0 引言

复杂网络（CN，Complex Networks）是对复杂系统（CS，Complex System）的一种抽象描述。当前，复杂网络的研究已经被逐步应用到自然科学、社会科学和工程科学等不同领域［1］。大规模无线传感器网络（Large-Scale Wireless Sensor Networks）正是复杂网络研究的应用之一。随着物联网（IoT，Internet of Things）的广泛应用，作为其终端支撑技术的无线传感器网络的规模也越来越大，这种大规模网络表现出了简单网络所不具备的统计特性［2］。因此，利用复杂网络理论来研究大规模无线传感器网络有着其充分的合理性。复杂网络的基本网络模型包括：规则网络（Regular Network）、随机网络（Random Network）、小世界网络（Small World Network）、无标度网络（Scale-free Network）和局域世界演化网络（Local-world Evolving Network）等［3］。其中，小世界网络是介于规则网络和随机网络之间的一种网络模型。鉴于大部分现实网络既不是规则的，也不是完全随机的，研究基于小世界网络模型的无线传感器网络更有现实意义。

无线传感器网络是指在感兴趣的区域内布置一定数量的通信节点，这些节点依靠相应的算法自组织网络结构，并通过无线信道和邻居节点进行通信，以多跳方式将感应数据传递到指定的Sink 节点位置。由于无线传感器网络通常被布置在环境恶劣的区域，进行人工补充节点能量将会付出相当大的代价，所以，采取相应的措施减少网络能量消耗是无线传感器网络的重要研究课题［4］。小世界网络具有较小的平均路径长度和较大的聚类系数，此特性为减少网络能耗提供了理论保证［5］。基于小世界模型来构造无线传感器网络拓扑的方法有静态模式和动态模式两类［6］。本文将静态和动态模式相结合，提出一种构造小世界无线传感器网络的混合模式，即在拓扑优化后的网络中选择特定节点，使之在网络中随机移动，从而构造出具有小世界特性的无线传感器网络。此方法从拓扑层面上对网络结构进行优化控制，以达到节约能量的目的。最后将上述小世界网络拓扑构造方法与经典的基于连通支配集的拓扑构造方法A3［7］和A3 Cov［8］进行了仿真比较，结果表明，本方案增加了网络能效性，延长了网络的生命周期，提高了网络运行的有效性。

1 无线传感器网络的小世界构造方法

小世界网络的核心思想是：尽管有些网络规模大、结构复杂，但其中任意两个节点之间却存在一个相对较小的路径长度。两种典型的小世界网络模型分别为WS 小世界模型［9］和NW 小世界模型［10］。利用小世界模型来构造无线传感器网络的方法有静态模式和动态模式两类。其中，静态的构造方法有基于加边的静态构造、基于超级节点的静态构造和基于拓扑优化的静态构造；动态的构造方法目前主要是研究基于数据骡子的动态构造。

1.1 基于加边的静态构造

此构造方法基于NW 小世界模型的思想，即在无线传感器网络中在节点之间增加连接边。文献［11］根据节点度进行排序，在考虑网络均匀覆盖的前提下，将在一定距离范围内的具有较高度的节点进行有线连接并形成链。文献［12］讨论了在瑞利衰落环境下的小世界无线自组织网络构建方法，使用增加无线连接边方式，让距离Sink 节点较远的普通节点与之直接相连，可显著降低平均最短路径。文献［13］针对无线自组织网络的特殊性，引入空间图的概念进行网络初始化，然后进行加边形成小世界网络。

1.2 基于超级节点的静态构造

此构造方法在网络中添加一类能量更充足、通信半径更长、数据处理能力更强的超级节点，普通节点优先选择超级节点作为数据转发的中继，使得数据传输到Sink 节点的跳数大大减少。文献［14］通过升级一部分节点使之成为超级节点，随着能量的消耗，再将之降为普通节点。此机制可以比小世界网络减少40%的端到端延时和减少25%的能耗。文献［15］利用局部重要性节点设计了传输捷径，将处于捷径两端的节点设置为超级节点。此机制下的网络呈现出明显的小世界特征，并具有较好的鲁棒性。

1.3 基于拓扑优化的静态构造

此构造方法是以一定规则去简化网络结构，以满足小世界模型的某些特征量的要求。文献［16］通过删除网络中多余的连接，以增加平均聚类系数，使得网络簇结构更加显著、拓扑结构更加简单，提高了数据传输效率。文献［17］证明了当网络具有小世界特性，且确定网络直径所需要的算法循环次数远小于网络节点数n 时，算法的时间复杂度为O（n2）。实验表明，当对连接度和连接方式进行适当控制时，可形成小世界网络特征，即可使网络取得最优的连接增益。

1.4 基于数据骡子的动态构造

在一些特殊场合，如战场应用中，无线传感器网络呈现出稀疏性，甚至会出现多个网络片互不连通的情况，此时利用上述静态方法构造小世界网络无法实现。文献［18］提出了基于数据骡子（Data Mules）来构造小世界无线传感器网络的方法。此方法在静态网络中添加一些移动节点，当移动节点在网络中游走时，收集相应普通节点转发的数据，当其与Sink 节点建立连接时，即可将数据卸载至Sink 节点。由数据骡子所建立起来的传输路径是一种动态路径，并无固定结构，但从数据传输跳数而言，仍然减少了网络平均路径。文献［19］分析了数据骡子在无线传感器网络中的应用，在不同的场景中仿真分析了加入数据骡子后网络最短路径、最长路径和聚类系数的变化情况。

2 基于混合模式的小世界无线传感器网络

目前在构造具有小世界特性的无线传感器网络时，通常从规则网络开始着手。但无线传感器网络一般被应用在人力物力难以到达的特殊场合，采用的部署方式是在目标区域随机撒下若干个节点，形成的初始网络是随机网络。基于此种特点，本文首先对随机网络进行拓扑优化改造，然后在拓扑优化后的网络中选择特定节点，使之在网络中随机移动，从而构造出具有小世界特性的无线传感器网络。这种把静态和动态相结合的小世界构造方法，称为混合模式。基于混合模式构造的小世界无线传感器网络可分为拓扑优化阶段、小世界模型构造阶段和能量动态均衡阶段。

2.1 拓扑优化阶段

在拓扑优化方面，本文将利用基于连通支配集（CDS，Connected Dominating Set） 的拓扑构造方法A3［7］和A3 Cov［8］。A3 算法的目标是在网络中找到一个次优的连通支配集，其算法执行分为3 个阶段：邻居发现阶段、子节点选择阶段和二次机会阶段。涉及到的消息收发有：Hello 消息、Parent Recognition 消息、Children Recognition 消息和Sleeping 消息。

邻居发现阶段：节点在目标区域布置完毕后，从Sink 节点开始启动树的构建过程。网络中A 节点通过发送Hello 消息发现邻居节点，收到此消息的B 节点如果没有被其他节点覆盖，则B 的属性将被设置为覆盖子节点，A 为父节点，B 回复Parent Recognition 消息给A，否则B 将忽略Hello 消息。另外，可利用式（1）来计算收到Hello 消息的信号强度和节点的能量强度，此公式可用于候选父节点的确定。

其中，x（子节点）是y（父节点）的候选节点，WE是节点的剩余能量权值，Ex是节点x 的剩余能量，Emax是最大的初始能量，WD是与父节点距离的权值，RSSIy是接收父节点信号的强度，RSSI*是保证连接的最小RSSI，由接收机的灵敏度确定。

子节点选择阶段：父节点设置了一个超时时限来接收其邻居子节点的应答。一旦时限到，父节点根据式（1）按降序排列每个子节点从而形成列表，并将此列表信息包含在Children Recognition 消息中发送给子节点。子节点接收到此消息后，会设置一个与其在列表中位置成正比的时限。在此时限中，子节点等待来自兄弟节点发送的Sleeping 消息，若收到，则自动进入睡眠状态。可以看出，那些能量高、距离父节点较远的节点更容易成为候选父节点（树的一部分）。

二次机会阶段：特殊情况下，节点发送Sleeping消息会使网络进入死等状态。为了防止此现象，节点在接收到Sleeping 消息后会设置一个定时器，在此时间段内进行操作。

A3 算法根据节点传输半径进行消息传递，进而生成连通树，没有考虑节点感知半径。A3 Cov 算法在A3 算法的基础上增加了感知选择阶段，是一个既考虑连通又考虑覆盖的生成树算法。在感知选择阶段，若被选择的子节点不在感知半径以内，仍然不能处于活跃状态。

在如图1 所示的随机网络布局下，采用A3 和A3 Cov 算法进行生成树构建的虚拟骨干网（VBN，Virtual Backbone Network）如图2 和图3 所示。

图1 随机网络布局

图2 基于A3 算法的虚拟骨干网

图3 基于A3 Cov 算法的虚拟骨干网

2.2 小世界模型构造阶段

本文基于恶劣环境（如军事应用场所、灾难应用场所等）下的无线传感器网络部署，无法向网络中添加基础设施以实现添加有线边。另外，除Sink节点外，假设网络中的普通节点是同质的、能量有限的和可移动的。Sink 节点是静止的、能量无限的和处于部署区域中心。为了避免增加无线边使得网络拓扑重新复杂化，且节点通信负载更大的情况，本文将基于数据骡子来动态构造具有小世界特征的无线传感器网络。具体可分为参数计算、数据骡子选择、移动策略和数据转发等4 个方面。

由于拓扑优化后形成虚拟骨干网，每个普通节点到Sink 节点的路径长度一定，即可计算任意节点到Sink 节点的路径长度dis及网络平均路径长度L，如式（4）所示。

其中，dij表示网络中两个节点之间连接的最短路径边数，对网络中任意两个节点之间的最短路径取平均值便可得到平均路径长度，本文考虑全连通网络情况。

数据骡子选择：本文基于以下两点进行数据骡子的选择。

2）若节点i 到Sink 节点的路径长度dis大于网络平均路径长度L，则证明i 距离Sink 节点较远。为了构造小世界网络平均路径长度较短的特性，使节点i 成为数据骡子。第1）点与第2）点不重复使用。

移动策略：由于被选定的数据骡子并不存储整个网络的拓扑结构图，为了节省传感器存储容量和减少计算复杂度，本文采取数据骡子在网络规划范围内随机选择方向进行移动的方式。初始阶段，数据骡子随机选择方向并匀速移动，当到达网络边界时，以对称角度向反方向移动，当网络重新进行拓扑优化时，停止移动。

数据转发：数据骡子在随机移动的过程中正常进行数据收发。在全连通情况下进行数据传输时，如果源节点找不到数据骡子进行转发，则依据图2和图3 所示的虚拟骨干网进行传输。否则，源节点将数据加载到与目的节点方向一致的数据骡子上，称为“上骡”。当数据骡子到达目的节点或改变方向时，从其存储器提取信息发送到其他节点，称为“卸骡”。

2.3 能量动态均衡阶段

利用混合模式构造形成小世界网络之后，即可进入网络运行状态。在网络运行中，各个节点的能量均衡利用是无线传感器网络需要实现的重要目标。尽管小世界模型本身有利于节点的能量均衡，但静态的拓扑结构仍然使得一部分承担较重流量的节点提早耗尽能量。本文采用拓扑结构动态重构的方法来进一步实现节点能量的均衡使用，即当某条件成立时，立即重新调用拓扑构造算法进行拓扑优化。将能量阈值和时间阈值作为拓扑重构的触发条件。当某个活动节点的剩余能量低于其初始能量的20%或网络运行时间超过1 000 s 时，重新调用拓扑构造算法。最终形成了应用A3 算法的基于混合模式的小世界无线传感器网络（MSW-WSNs-A3，Mixed-mode Small World Wireless Sensor Networks Using A3）和应用A3 Cov 算法的基于混合模式的小世界无线传感器网络（MSW-WSNs-A3 Cov，Mixed-mode Small World Wireless Sensor Networks Using A3 Cov）。

综上所述，MSW-WSNs-A3 和MSW-WSNs-A3 Cov 的构造步骤如下：

1）在目标区域随机部署可移动同质无线传感器作为普通节点，在区域中心位置部署能量无限的静止Sink 节点，普通节点与Sink 节点的传输半径相同。转向步骤2）；

2）调用A3 或A3 Cov 算法进行拓扑优化。转向步骤3）；

5）网络运行，在生命周期内，当任意节点的剩余能量低于其初始能量的20%或网络运行时间超过1 000 s 时，转向步骤2）；若Sink 节点成为孤立节点，网络运行完毕，生命周期结束。

3 仿真分析

本文把生命周期定义为从网络运行开始至Sink 节点成为孤立节点为止。将基于A3 和A3 Cov的无线传感器网络分别记作WSNs-A3 和WSNs-A3 Cov，在一定网络环境下对WSNs-A3、WSNs-A3 Cov、MSW-WSNs-A3 和MSW-WSNs-A3 Cov 进行仿真分析，比较各自的生命周期情况。

图4 和图5 以时间为横坐标，以与Sink 节点存在路径的活动节点数目为纵坐标，描述的是WSNs-A3 同MSW-WSNs-A3 以 及WSNs-A3 Cov同MSW-WSNs-A3 Cov 对比的生命周期情况。可以看出，为了保证覆盖率，WSNs-A3 Cov 一开始便激活了约4 倍于WSNs-A3 的节点数。随着时间的推移，WSNs-A3 和WSNs-A3 Cov 都存在活动节点数量阶跃式下降的情况，MSW-WSNs-A3 和MSW-WSNs-A3 Cov 大大缓和了这种跃式下降的程度，证明本文设计的高效节能的小世界无线传感器网络具有很好的能量均衡效果，生命周期得到了明显的改善。

表1 仿真参数设置

图4 WSNs-A3 与MSW-WSNs-A3 生命周期比较

图5 WSNs-A3 Cov 与MSW-WSNs-A3 Cov 生命周期比较

下页图6 和图7 以时间为横坐标，以节点通信覆盖为纵坐标，描述的是WSNs-A3 同MSW-WSNs-A3以及WSNs-A3 Cov 同MSW-WSNs-A3 Cov 对比的通信覆盖率情况。通过生命周期可以看出网络的能量使用情况，而通过观察通信覆盖随时间的变化情况，可以看出网络运行的有效性，因为当通信覆盖率降低到一定程度后，尽管生命周期还没有完成，节点采集的数据已不能反映部署区域的整体情况。通过仿真可以看出，WSNs-A3 Cov 的通信覆盖降到50%所花费的时间比WSNs-A3 要快约3 000 s，这是由于WSNs-A3 Cov 在网络运行之初激活的节点数较多造成的。MSW-WSNs-A3 的通信覆盖降到50 %所花费的时间比WSNs-A3 慢约2 倍，MSW-WSNs-A3 Cov 的通信覆盖降到50 %所花费的时间比WSNs-A3 Cov 慢约4 倍，证明本文设计的高效节能的小世界无线传感器网络具有很好的运行有效性。

图6 WSNs-A3 与MSW-WSNs-A3 通信覆盖比较

图7 WSNs-A3 Cov 与MSW-WSNs-A3 Cov 通信覆盖比较

4 结论

本文提出了一种利用静态和动态相结合的混合模式来构造小世界无线传感器网络的方法，该方法可分为拓扑优化、小世界模型构造和能量动态均衡3 个阶段，最终形成了应用A3 和A3 Cov 算法的基于混合模式的小世界无线传感器网络MSW-WSNs-A3 和MSW-WSNs-A3 Cov。经过仿真分析，表明MSW-WSNs-A3 和MSW-WSNs-A3 Cov可以较大程度缓解WSNs-A3 和WSNs-A3 Cov 有效活动节点数跃式下降的程度，并能使网络具有很好的运行有效性，达到了节点能量均衡利用的目的，延长了网络生命周期。下一步的工作重点将研究新的适合小世界特征的拓扑优化方案，使拓扑优化阶段不再依附于其他算法之上。