一种高可靠低能耗的无线传感器网络拓扑方法

辛强伟 唐云凯 许晓婷

摘要：过多的跳数对于无线传感器网络的效率和可靠性都不利。本文提出环形最小连通支配集方法，从拓扑的角度来探讨该方法对无线传感器网络可靠性和能耗的影响。最小连通支配集可有效地减小网络的跳数，环形拓扑可提高可靠性，因而环形最小连通支配集方法可实现网络的高可靠性和低能耗。

关键词：无线传感器网络；最小连通支配集；拓扑

中图分类号：TP393 文献标识码：A 文章编号：1007-9416（2018）08-0055-02

1 引言

实际应用存在大规模无线传感器网络，例如森林监测、城市智能交通管理系统和大型社区监测等，这些实际应用需要部署大量的传感器节点。无线传感器网络中节点通过自组织形成一定的拓扑，通过形成的连接通信。由于节点通信距离的限制，无线传感器网络采用多跳的方式传输数据。无线传输的不稳定导致转发可能会出现丢包，转发次数越多丢包越严重。一次转发时间很短，但多次转发累积消耗的时间对于实时控制系统不容忽视。此外，有的路由机制采取发送数据包后，若对方在设定的时间内不应答，则重传数据包，而重传会降低网络的效率和增大网络的时延。

大规模无线传感器网络的平均跳数往往较大。过多的跳数可导致能耗增加、丢包率上升、延迟增大以及可靠性变差。减少冗余转发节点对于大规模无线传感器网络具有重要意义。大规模无线传感器网络的要求之一是低能耗。此外，高可靠性也是大规模无线传感器网络的要求。本文研究如何实现大规模无线传感器网络的高可靠性和低能耗。

2 已有工作

目前对于无线传感器网络最小连通支配集的研究主要集中在减少能量的消耗，达到延长网络的生存时间。最小连通支配集方法可避免泛洪，减少冗余转发节点[1]。增加处于睡眠状态的节点即非支配点的数目，可以达到降低网络能耗的目的。

最小连通支配集法容错的研究比较少，当最小连通支配集中有节点故障或失效时可以修复。基于能量代价的最小权和支配集拓扑控制算法考虑了节点能量[2]。根据各节点之间的能量和距离等因素，用加权的方式来构建和分析最小连通支配集。为了延长网络生存时间，用马尔科夫模型优化最小连通支配集算法[3]。

3 环形最小连通支配集分析

相同条件下，随着跳数的增加，丢包率会呈现上升的趋势。因此较少无线传感器网络的跳数对于实现高效互连很重要。本文通过建立环形最小连通支配集来减小无线传感器网络中的跳数并且提高网络的可靠性。

3.1 平均跳数最小化

無线传感器网络的平均跳数为任意两个节点之间的跳数的平均值。最小连通支配集目的是让尽量多的节点处于休眠状态，最大限度地减少中间转发节点。在拓扑控制中应用最小连通支配集可以减少冗余转发节点，为实现高效无线传感器网络提供了保证。

无线传感器网络的节点部署密度加大时，会造成连通率的增大。平均跳数和连通率有着一定的联系。随机部署在一区域内的无线传感器网络节点的度分布近似于Poisson分布，属于均匀网络。无线传感器网络节点的度受节点通信距离的限制，因而如果随机部署节点可能会形成多数节点的度相近。连通率与无线传感器网络的平均度成正比，当网络的平均度达到一定程度后，即当节点部署达到一定程度后，再继续增加节点数目，连通率会保持不变。

无线传感器网络的传输效率取决于节点数目和平均跳数。当节点密度偏低时，会有一些节点不能连通，这时最小连通支配集表现为较少的构成节点。随着节点密度的增大，无线传感器网络的连通性逐步增强。随着节点数目的增大，最小连通支配集变大。当节点密度达到一定水平时，最小连通支配集的大小趋于稳定。

最大跳数的意义在于可被视为最坏情况，平均跳数的意义在于可被视为一般情况。设计和分析无线传感器网络时如果对系统有很高容错要求，应准备最坏情况的发生，即准备最大跳数的出现。随着节点数目的增加，最大跳数变大。当节点密度达到一定水平时，最大跳数趋于稳定。

随机部署节点随着节点密度的增大，平均跳数逐渐出现小幅下降的趋势。当节点还相对稀疏时，会有一些节点相互之间不能连通。在全面连通之后继续增加节点，会产生冗余节点，使得网络具备一定的容错性。因此一定的冗余是必要的。

当节点密度较低时，随着节点数目的增大，平均跳数较快增大。当节点密度达到一定水平后，平均跳数逐渐小幅减小。随着节点数目的增加会出现两个阶段：第一个阶段是当连通率尚未达到1时，随着节点数目的增加，平均跳数处于上升的趋势；第二个阶段是当连通率达到1后，随着节点数目的增加，平均跳数处于下降的趋势。随机部署时全面连通所需的节点数目可以用来衡量算法的优劣。在达到全面连通后继续增加节点会减小跳数，从而提高网络效率和加强网络容错。

3.2 可调节的环形结构

最小连通支配集是一个图论里的概念，支配集中包含的是骨干节点，骨干节点之间可以通信，而且骨干节点的数目最小。环形最小连通支配集的特点是闭环结构，可运用自愈环对网络进行自动保护，从而可以显著提高无线传感器网络的可靠性。

环型网络拓扑结构是一种连接成封闭回路的结构。环形最小连通支配集从网络结构上看，各骨干节点间是直接串联、首尾相接、有输入和输出、输出能返回到输入并产生影响。这样任何一个骨干节点出现故障都会造成最小连通支配集的中断，因而会在第一时间发现。另一方面，该方法也是一种具有反馈的机制，可以根据返回的参数进行网络的调节。

传感器节点由于采用电池供电容易因电量耗尽而失效，此外故障和人为破坏也会造成传感器节点失效。最小连通支配集是骨干节点并非普通节点，其失效会对网络造成重要影响，需要采用环形结构第一时间发现并进行解决，从而提高网络的可靠性。

4 结语

高可靠性和低能耗是无线传感器网络的重要要求，由于多跳会带来时延影响网络效率以及增大能耗，因而减少无线传感器网络的跳数具有现实意义。本文探讨了最小连通支配集对跳数的影响以及网络跳数和连通率之间的关系。使用环形最小连通支配集法可以有效地减小最大跳数和平均跳数并且较好地提高网络可靠性，从而达到建立高可靠低能耗的无线传感器网络。

参考文献

[1]唐勇，周明天.基于极大独立集的最小连通支配集的分布式算法[J].电子学报，2007，32（4）：868-874.

[2]孙超，尹荣荣，郝晓辰，刘彬.WSNs中基于能量代价的最小权和支配集拓扑控制算法[J].电子与信息学报，2010，32（4）：857-863.

[3]汪文勇，向渝，董传坤，杨挺，唐勇.用马尔科夫模型优化分布式最小连通支配集算法[J].电子学报，2010，38（10）：2441-2446.