无线传感器网络拓扑管理模式的分析

Analysis of Topology Management Mode in Wireless Sensor Networks

摘要: 无线传感器网络在物联网中起着关键性的作用，分析已有的网络拓扑管理模式，有助于设置更适合的、满足应用场合需求的管理策略。无线传感器网络依据其拓扑形式分为层次型和扁平型结构；从节点变化角度来分类，分为静态网络与有动态因素的网络(简称为动态网络)。分析了静态网络的层次型结构的选择方式，其簇头的选择方法分为基于概率、非概率以及选择针对性能指标的处理方法；分析了动态网络从供能与否，节点移动与网络移动中网络拓扑管理模式；最后分析了无线传感器网络问题的转化形式，并对转化后的问题的处理做了简要的分析。我们认为，运筹学与博弈论方法是路由设计的有效理论工具。

Abstract: Wireless sensor networks play a key role in the Internet of things. Analyzing the existing topology managements is helpful in both setting more suitable management strategies and meeting the needs of applications. In terms of the topology, wireless sensor networks can be divided into hier-archical structure and flat structure. There are two kinds of wireless sensor networks. One is static network, and the other is dynamic network. We analyze the methods of hierarchical structure built on static network. Three ways are adopted to select cluster heads. The first is based on probability, the second is based on nonprobability and the third is according to performances of networks. By analyzing the dynamic characteristics, we describe the mode of network topology management. Finally, we analyze the transformation forms of wireless sensor networks and make a brief analysis of the transformed problems. We believe that operational research and game theory are effective theoretical tools for routing design.

1. 引言

大量微型传感器通过无线技术构建成无线传感器网络，它们具有自适应能力。在泛在网络中，传感器网络占据重要的位置。物联网、传感器网络和泛在网络有着紧密的关系，泛在网络包含物联网，物联网包含传感器网(图1) [1]。

Figure 1. The relation among sensor networks, Internet of things and ubiquitous networks

图1. 传感器网络、物联网与泛在网络的关系

传感器网络通常用于物与物之间的数据传送与转发。传感器自身有计算功能、存储功能、体积小、携带能量少且一般情况下给传感器补充能量是较棘手之事，节能在传感器网络拓扑管理时考虑较多。传感器网络的各项性能指标亦纳入考虑范畴，如尽可能延长网络的寿命，保障数据安全地在传感器网络中传送，使得传感器网络的覆盖区域与数据的传送范围相一致，不出现空洞现象。在传感器网络中，发送数据的传感器称为源点，接收数据的传感器为汇点。传感器网络中，若所有的传感器不管是源点还是汇点(又称为基站)，均为物理位置不变，称这类传感器网络为静态网络；若网络中的传感器节点中非汇点均处于物理位置不变状态，而汇点的物理位置处理动态变化状态，称这一类传感器网络为具有移动汇点的传感器网络。传感器的角色可分为源点、中继节点和汇点。在传感器网络中，同一个传感器在不同的情况下，可以既是源点，又是中继节点角色。静态网络中，若传感器网络在布局环境相同，呈现均匀分布状态，则传感器的传送半径R满足一定条件 [2] [3] 时，传感器网络设定的传送范围与传感器的覆盖范围一致。

传感器网络接收的数据具有随机性，数据的存储转发亦有随机性，是基于任务性的网络，导致了网络的拓扑具有动态性，增加了传感器网络拓扑管理的复杂性。有学者在研究网络拓扑管理时，设计博弈策略达到目标最优 [4] [5]。依据网络中接收数据的规律性和数据之间的关联性，从数据流的角度考虑网络拓扑管理问题 [6]。复杂的网络结构中，通过提供某种树形结构的管理，能够降低问题的复杂性，得到较好的解决方案。构造层次结构的拓扑管理模式时，有学者通过引入随机概率的选举簇头 [7] [8] [9] [10]，利用无线信号的强弱性让其余非簇头的节点加入某个簇，整个网络由不同的簇区域构成。在解决连通图与连通网络问题时，依据支配集的理论思路布局主干网或构建虚拟主干网，谋求网络拓扑管理的解决策略 [11]。对于具有动态因子的传感器网络，静态网络的面临的各种因素依旧存在，尚需要应对数据传送中需要的即时性与延时性之间的冲突，研究工作者亦在此方面做了相关的研究 [12]。

本文的整体结构如图2所示。我们在第2节分析了依据概率与非概率方式建立静态网络的层次性结构，从性能指标方面着眼的静态网络的拓扑管理方法；第3节分析了有动态因子的网络处理拓扑管理问题的模式；随后对拓扑管理的转化问题简单分析了一下，最后从整体给出了我们看法，并且给出本文的总结。

Figure 2. Classification on topology problems in Wireless Sensor Networks

图2. 无线传感器网络拓扑问题的分类

2. 静态传感器网络拓扑管理与路由策略的研究

在静态传感器网络的拓扑管理，就其拓扑形式，分为层次型结构或扁平型结构，参见图3。静态网络的层次型拓扑结构构建过程中，簇头选举主要有2种方式：基于概率方式与基于非概率方式。

Figure 3. Hierarchy and flat structure (including chain structure)

图3. 层次与扁平结构(含链式结构)

2.1. 基于概率的层次型拓扑结构建立

以随机概率为准则进行簇头选举的代表性协议有LEACH [7]、HEED [8]。LEACH [7] 路由协议是第一个基于层次的分簇路由协议，依据该协议网络中簇头节点所占比例由期望概率预先设定好，簇头结点在动态中产生，每个节点成为簇头的机会是均等的；HEED协议 [8] 考虑了通信的代价与节点的剩余能量的层次化分簇协议，数据信息从源点一跳到达簇头后再转发到汇聚点，数据传送转发可能经过多跳，途经的中继点均为簇头节点。在此两种协议的基础上，有了很多改进的路由协议，有些路由协议与优化规则相结合，对以概率方式选出的簇头候选者进行再次确认。

研究工作者对LEACH的设计了许多改进策略 [13] [14]，如C-LEACH (Centralized LEACH) [13] 算法分配让汇聚节点充当中心节点，网络中节点的剩余能量和地理位置等信息由中心节点收集，簇头节点亦由中心节点确定，数据发送到簇头并经过聚合之后一跳送达汇聚节点。亦有LEACH改进策略分离数据收集与转发两个功能，每个簇选举2簇头，第一簇头与第二簇头分别完成数据收集聚合和数据转发的任务 [15]。Xing [16] 考虑了节点布局不均匀或在网络使用中导致的节点分布不均衡，调整了概率选举簇头的阈值；另外考虑到LEACH中簇头到汇聚节点只是一跳到达，没有注意簇头与汇聚节点几何距离的远近对数据输送耗能的影响，将它们的几何距离适当地引入中继节点，设计了改进的拓扑管理策略。Nigam G. K.等 [17] 得到了用粒子群PSO (Particle Swarm Optimization)优化的路由策略PSO-LEACH。Tarunpreet Bhatia等 [18] 利用遗传算法提出了无线传感器网络中的路由算法GADA-LEACH (LEACH based on Genetic Algorithm and Distance Aware)。文章先用LEACH协议选择初始簇头，然后依据所有节点的能量与簇头能量的比值、同簇中节点的平均距离、簇头到BS的平均距离，定义了适应度函数，利用了遗传算法进行初选簇头的优化。文献 [19] 利用了遗传算法，设计了一种基于遗传算法的能量有效的建簇和路由方法GECR (Genetic algorithm-based Energy-efficient Clustering and Routing approach)。K. Thangaramya等 [20] 利用了模糊神经网络设计了能量敏感的分簇协议。任昌鸿等 [21] 将改进粒子群算法与分布式空间分析技术相结合，设计了均衡密度聚类方法。

针对HEED协议在传感器网络环境可能出现的情况，亦出现了不同的改进协议。匡哲君 [9] 针对HEED协议可能引发的问题，提出了在静态网络中基于角色成员关系的分簇算法REEM (A role, energy -efficient, membership clustering)，其设计的准则是消除或减少“能量洞”的出现。文献 [22] 考虑了HEED协议可能导致的数据传播中节点的能耗不均和节点失效速度不均衡，利用了相对失效度及节点的离散度调整了结点参与簇头选举的阈值，在拓扑管理策略的设计中微调了节点的最大传送半径。

2.2. 非概率形式选择簇头，建立层次型拓扑结构

GAF (Geographical Adaptive Fidelity)算法 [23] 整体上没有利用概率形式构建拓扑结构，根据节点的地理分布划分簇区域，每个簇中的节点同属于一个地理区域；簇头由簇中节点随机选择方式产生，相邻区域的两个簇之间的节点通过簇头可以相互通信。Ngoc-Tu Nguyen等人 [24] 从数据融合发挥最大效用角度设计路由，以负载消耗极小化的目标，利用均衡调整原则建立了虚拟汇聚树，进行数据的接收与转发，让能量均衡消耗，从而减少能量洞出现。文献 [25] Mohit Sajwan、Devashish Gosain、Ajay K. Sharma以能耗最小化为目标，设计了多路径路由和单跳路由择优的算法。Basem Abid等 [26] 提出了分布式连通支配集数据聚合(DCDSDA, Distributed Connected Dominating Set for Data Aggregation)来构建网络拓扑结构，根据每个传感器的剩余能量，形成一个连通的支配集，组成一个树形拓扑结构的虚拟主干网。Prasenjit Chanakt [27] 等直接利用能耗的公式估计能耗，通过估计的值来设计各自的算法。通过详细的簇头能耗、成员能耗等计算公式，依据计算结果选择簇头、源点到汇点的路径等，减缓“空洞”现象出现。

2.3. 依据性能指标要求设计路由策略以及相关方面的研究

文献 [28] 利用动态能量管理模型对性能进行分析。文献 [29] 以增进服务质量为目标，从负载平衡的角度进行路由策略的设计。夏静山等 [30] 针对路径总距离和消耗总能量的双重目标提出了节点充电路径的优化方法，通过改进的遗传算法求解构建的多目标优化问题。高翔霄等 [31] 利用时隙窗口间隔均衡控制和数据传输延迟配置设计了基于的无线传感器网络数据传输延时分配算法。Sonam Maurya等 [32] 通过构建虚拟环，利用受限搜索空间，在异构传感器环境下为数据传输建立了一种时延感知的能量有效可靠路由技术。

在静态网络中，拓扑结构可以是层次型，亦可能是扁平型。层次拓扑结构的路由协议，主要涉及两个阶段，即簇构建阶段与稳定阶段的数据传输。拓扑管理的目标需要满足若干性能指标的综合因子，其中延长网络的生存时间是一个重要的衡量指标。

3. 有动态属性的传感器网络拓扑管理与路由策略的研究

在无线传感器网络节点的移动管理策略中，可以分为基于节点的移动和基于网络的移动。基于节点的方案要求移动节点在网络层处理移动切换事务；而基于网络的移动切换方案中不需要移动节点亲自处理子网内的移动事务。两者之间相异之处：

1) 基于节点的移动管理方案，主要依靠移动节点本身收发相关控制消息，通知网络中的其它节点自己的移动带来的拓扑变化，进而做出通信拓扑的调整；

2) 基于网络的移动管理方案，主要依靠网络中的其它节点，对移动节点的移动带来的拓扑变化进行更新、登记等操作，实现通信的延续。

网络层次来看，移动管理算法主要可以分为MAC层的移动管理和网络层的移动管理。从技术角度划分，MAC层的移动管理有同步移动管理和非同步移动管理。MAC层的移动管理要求网络中一定范围内的节点需要具有同步时钟，严格根据各节点的时钟进行周期性的点唤醒等操作。网络层的移动管理通过相应的消息控制报文来实现移动管理，而且网络层的移动管理策略根据是否基于TCP/IP协议分为两类。在物联网背景下，TCP/IP协议由于其更好的通用性，逐渐在无线传感器网络中得到研究人员的重视。

Figure 4. Topology management methods with dynamic factors or problem transformation

图4. 有动态因素或问题转化的拓扑管理处理方法

网络中可移动的节点有传感器节点或者网络汇聚节点，无论是哪种节点的移动，都会带来网络通信拓扑的改变。图4刻画了有动态因素的传感器网络拓扑管理模式、网络拓扑管理问题的转化的方法及处理(参见下节内容)。

3.1. 基于节点的移动

传感器节点的移动一种是节点自身为实现某种功能性目的移动，比如需要附着在移动物体上的传感器节点，如在医疗领域的应用：病人佩戴一套可实时测量脉搏、心跳、血压等无线传感器设备，在给定的范围内(如病房楼内)移动的同时，医护人员可以随时检测到病人的这些实时信息；另一种是由于外界环境带来的节点的位移，比如风雨、水中的传感器节点等。同时，还有研究认为网络中节点的失效也可以视为一种无线传传感器网络节点的移动，这种观点实际上把“移动”的概念扩展到了“链路拓扑”的改变层面。由此可见，移动是无线传感器网络研究中的重要内容。

尚小薄 [10] 研究了类簇树拓扑模型的传感器网络，依据图论中的分层思想，提出了2个适用于具有移动节点的无线传感器网络拓扑管理策略与算法。他提出的算法之一用于实现节点在传感器子网内移动时的拓扑管理，保证了拓扑结构变动时数据传输的连续性与完整性。他提出的另一算法实现了两个子网之间的节点切换时的移动拓扑管理，使得数据传输拓扑的连续性与完整性，降低拓扑管理与控制在节点切换时产生的开销。Sonam Maurya等 [32] 研究了大型密集网络中的高汇聚点(sink)的移动性可能导致节点的流量负载、冲突、丢包、延迟和快速能量消耗等开销问题。为异质传感器网络环境下，用于异构传感器环境下的数据传输的时延感知的能量有效可靠路由(DA-EERR)技术。匡哲君 [9] [33] 提出一种适应于动态汇聚节点的环境下的通信方案，其方案根据延迟容忍级别完成延迟通信。延迟容忍下的移动汇聚节点方案，也对静态汇聚节点情况做了相应的考虑，如适用于对解决传感器网络在运行过程中出现的“能量洞”问题。R. Ashween等 [34] 探讨了移动汇聚点(sink)的传感器网络，针对汇聚节点到中心的位置更新研究了相应的对策；采用灰太狼优化(OGWO)算法优化，设计了一个基于移动接收器最佳更新的能量嵌入式路由协议。唐继强 [35] 分析了有移动汇聚节点引发线路规划问题，建立了非线性规划模型、最大–最小优化问题、整数规划问题，它们分别对应了移动汇聚节点最短线路规划、感知节点能耗与线路长度均衡的线路规划问题、最小数据延迟线路规划问题。文 [35] 分别利用枚举剪枝算法和变量分离算法来求解对应的非线性规划问题，用锚点位置调整算法和通信半径调整算法各自求解最大-最小优化问题，利用替换算法求解最小数据延迟线路规划问题。

3.2. 基于网络的移动

彭颖等 [36] 分析了移动网络中基于最优停止理论的数据传输能耗优化策略，考虑了单信道中数据生成速率与传输延时已知的情况下，信道质量随着时间变化。信道质量的变化依据信道增益函数周期性服从某种规律(如Rayleigh分布、Rician分布)，在给定数据传输率情况下，以数据传输能耗最小为目标考虑了数据的发送与停止的时间，选择最佳的发送与停止时间。Jinho Kim等 [37] 研究了一种支持传感器网络组移动性的方案，为具有基于位置(ID-based)的路由通信提出了一种无线传感器网络移动性管理体系结构，考虑了基于ID与位置(ID/LOC)的分离，通过分布式管理，使得大量无线传感器网络的节能、轻量移动性控制得以满足，同时提出了先发现后转发的路由优化思想。

4. 基于问题调整与转化方式的研究策略

一些研究以感知范围不重叠的节点集合建立独立集，将无线传感器网络的覆盖问题转化为图的最大独立集问题。图的最大独立集问题是一个NP难问题，可以依据贪婪法求得满足某种要求的近似解。

魏博垚等 [38] 研究了无线传感器网络部分覆盖和数据收集问题。无线传感器网络部分覆盖和数据收集问题，或较关注覆盖，或较注意数据收集问题。针对部分覆盖问题，寻找激活节点数少且满足覆盖要求且的解决方案，达到降低能耗；较注重数据收集问题时，确保网络连通性同时，建立从感知节点到汇聚 (sink)节点的数据收集路径，然后依据贪婪法，激活较少的节点满足部分覆盖需求，让其余的节点处于休眠状态。对于第二种情况，有些研究者通过自动机学习的方法实现节点的休眠节点的自适应调度。魏博垚等 [38] 依据贪婪法的算法处理部分覆盖和数据收集问题时，采用了避免监测冗余，对节点能耗不均衡的问题做了相应考虑。M. A. Merzoug等 [39] 就大规模的无线传感器网络，设计了扩展与聚合交替形式的算法，称为扩展(展开)聚合SA (Spreading Aggregation)方法，既能收集数据，亦能满足分布式冲突避免。Sain Saginbekov等 [40] 研究了多汇聚(sink)节点问题，提出了一种分布式能量平衡算法平衡各个汇聚(sink)节点的能量消耗，其方法是通过引入虚拟汇点，建立以其为根节点的层次型拓扑结构。

5. 基于运筹学与博弈论方法是路由设计的有效理论工具

无线传感器网络，若仅仅从拓扑角度考虑，可以看成节点和边均有权值的受限的无向图；若考虑到网络有多种基本性能指标，为了延长整个网络的生存时间，在多个性能指标中进行折中，博弈论的理论适合其管理策略的设计；考虑到传感器节点发送数据的随机性，节点能量随着时间的减少特点，可以从随机图角度进行对传感器网络拓扑作理论分析与探讨，有学者用随机图研究了随机分布式算法。

尚小薄 [10] 用图的相关理论，研究了无线传感器网络中的拓扑管理问题。唐继强 [35] 非线性规划、最大–最小优化问题、整数规划问题研究了有移动汇聚节点的传感器网络管理问题。一些学者将用图的最大独立集问题研究无线传感器网络的覆盖问题。蔡钊等 [4] 用博弈论的思想提出了一种WSN拓扑控制算法。Wu [11] 提出了寻找连通支配集来实现网络能耗均匀分布的ECDS (Efficient distributed algorithm for calculating Connected Dominating Set in ad hoc)算法从而延长网络寿命。

6. 总结

本文研讨了无线传感器网络的拓扑管理问题，从问题的处理角度进行了归类，将其分为网络拓扑管理问题本身的处理和其转化问题的处理。从问题有无涉及外在素或问题自身的特征，分别对静态网络、有动态因子的网络(含定期为部分传感器节点供能)和基于多性能指标三个方面进行概述。对于转化问题的处理，我们分析了三个侧面，即数据收集与部分覆盖、支配集问题和基于Pareto最优为目标的博弈策略。通过对现有的近处管理模式的分析，我们认为运筹学图与博弈论方法是路由设计的有效理论工具。