无线传感器网络拓扑控制算法范文

1概述

无线传感器网络(WirelessSensorNetwork，WSN)近年来的快速发展离不开传感器技术、网络无线通信技术、嵌入式技术、分布式信息技术以及微电子制造技术等相关关键技术的日益成熟。它是一种无中心节点的全分布系统，是有针对性对某个监控区域内进行随机投放的若干个传感器节点自组织通过无线电信通信构成网络系统。传感器节点可根据其内置的不同功能的传感器，感知所在的周遭环境中人们的感兴趣的数据，如温度、红外线、湿度、压力、土壤成分、移动物体的属性等。正因为无线传感器网络的无处不在的感知技术优势，它有着非常广泛的应用前景。在军事领域、环境应用、医疗事业、工业应用以及商用等多个领域都占有意义非凡的一席之地。显然，无线传感器网络是当前多学科高度交叉、前沿的热点研究之一。无线传感器网络中传感器节点一般由数据采集模块、数据处理和控制模块、无线通信模块和供电模块组成。而正因为它自身的物理特性因素，其电量供给有限成为无线传感器网络生命期主要的瓶颈问题之一。早期的经典拓扑控制算法思想主要是借助控制节点传输功率或稀疏化网络拓扑图，达到降低节点信道之间干扰的目的。近阶段有一些研究者，指出机械性减少边的数量、长度及邻节点度不一定就能保证节点之间的干扰现象也降低，并就干扰模型的定义和度量方法进行了研究。其中，定义的干扰模型有基于发送节点的干扰模型、基于接收节点的干扰模型。基于不同的干扰模型，文献［8］指出二维及二维以上的网络模型的拓扑控制干扰优化问题已被证明属于NP问题。在上述拓扑控制算法的研究中，很少有以降低全局网络节点中的最大干扰值作为首要目标，干扰的存在不仅会影响通信质量，而且造成数据不断重传损耗电量缩短网络生命周期［9］，大部分算法针对的都是节点分布比较均匀的网络情况，而对于节点间非均匀分布的网络情况，如指数链模型无线传感器网络下的干扰优化效果甚微。本文将采用基于接收节点干扰模型，以干扰阈值作为重要考虑因素，以最小化最大干扰值、网络连通性为算法首要目标，对一维指数链模型的无线传感器网络节点的邻居节点、节点传输半径和网络节点数、节点所受的干扰进行研究，设计一种启发式算法，并将其算法思想沿用至二维网络模型中，保证其网络连通性的同时达到优化最大干扰值的目的。

2相关工作

功率控制是研究无线传感器网络拓扑控制重要方向之一，功率控制指的是合理地设置或动态调整节点的传输半径功率，在保证整个网络的连通的同时，弱化节点间的相互干扰，并达到高效节能、延长网络生命期的目的。文献［7］指出包含最近邻居的节点算法(下文简称为最近邻算法)在指数链模型上的干扰优化效果不甚理想。在一维指数链上若有n个节点以2的指数倍的距离相隔进行排布，由于最近邻算法的算法特性，会将构成网络中的最短路径的链路保留下来，以减少链路开销。而一维指数链的特性会使得新加入每一条的连接增大原先最右边的节点的发射半径，这也加剧了网络中节点的最大干扰值扩大。如图1所示，由文献［7］指出最近邻算法产生的拓扑结构节点中受到的最大的干扰达到n－2∈n。显然，一个节点在有n个节点的网络中，在最坏的情况下，受到除已的其他节点干扰，即干扰值为n－1，可见，最近邻算法在一维指数链上干扰优化的改进效果不如人意。

3干扰模型要素

根据无线传感器网络的特性，本文延续文献［7-8］模型化方法利用单位圆盘图(UnitDiskGraph，UDG)理论］进行无线传感器网络抽象建模。便于讨论后文提出的干扰优化拓扑控制算法，本文采用无向图中的顶点来模拟在监测区域投放的传感器节点，图中任意2点存在的边作为任意2个传感器节点直接通信即一跳距离的依据。

3．1单位圆盘图在UDG图G=(V，E)中，V为图G中顶点的集合，E为图G的任意顶点存在边的集合。V中的每个顶点都有以该顶点为中心的等半径的圆一一对应，假设所有节点具有相同的通信半径上限rmax，当且仅当u顶点和v顶点之间的欧氏距离小于等于rmax时，则e(u，v)∈E。根据上述UDG图的定义，假定UDG图G=(u，v)为无线传感器网络的抽象模型，并设定无线传感器网络中的传感器节点的传输功率是可调节的，其有效值区间是［0，MaxPower］，其中，MaxPower代表了节点传输功率的上限值。

3．2模型字符为更简洁明了描述本文要点，将使用以下模型字符进行定义:(1)Nu表示结果拓扑图T中u节点的邻居节点集合，即在结果拓扑图T中与u只有一跳距离的顶点的集合。(2)ru表示结果拓扑图T中u节点的通信半径，ru=maxv∈Nu{|u，v|}，其中，|u，v|指的是u节点与v节点之间的欧氏距离。(3)D(u，ru)表示以u为圆盘中心ru为通信半径所覆盖的节点的集合，为方便算法展开分析，这里不考虑节点自身覆盖的情况。(4)本文采用基于接收者的干扰模型，RI(u)表示u节点对于根据拓扑控制得到最终的拓扑图T=(V，E’)，节点受到干扰是这样定义。(5)衡量结果拓扑图的干扰值是由众节点所受的干扰度最大的那个节点的干扰值所决定。根据3．1节中指出通信功率的上限MaxPower，则同样的，传感器节点都受限于同一个最大通信半径值MaxRadiu，而节点的通信半径取值随着拓扑控制调节控制在［0，MaxRadiu］区间，也就是说，无线传感器网络中的传感器节点初始条件都是统一的，当中的最早消耗完电量的节点则是受到干扰最多的那个节点，这也决定了当前无线传感器网络的生命期的长度。

4本文算法设计思想

根据上述采用的基于接收者的网络拓扑干扰模型，本文提出了一种基于干扰阈值调节的拓扑控制(ThresholdAdaptiveTopologyControl，TATC)算法。TATC算法思想主要如下:(1)建立模型:每个节点需要与其他节点进行消息交互，收集搭建链路的距离即通信半径的数据。考虑在理想状态下，如果网络中任意u，v节点能通过一跳距离能收到消息响应成功，则根据式(1)，它们之间的通信链路距离是不超过设定的单位通信半径上限单位1，则图G中u，v点中存在直接链路，即e(u，v)∈E。(2)初始化结构拓扑图T，T=(V，ETATC)，ETATC=NULL。由于当前T中边为空集，当前RI(T)=0;设定一个干扰阈值RI-threshold初始值为1。(3)随机遍历E集合中的链路，对链路进行预处理选择，尝试每一条链路逐步加入ETATC集合中，并计算出当前图T中各个节点RI值，从而得到RI(T)值。(4)对当前假设的图T中ETATC集合中利用深度搜索算法进行是否存在边回路检测，如若存在回路，则ETATC集合中将不会包含该链路，与此同时，E集合中也将剔除该链路，之后返回步骤(3)，将继续遍历下一条链路。否则，执行步骤(5)。(5)如果加入链路能使RI(T)不超过当前的RI-threshold，则该链路将加入ETATC集合中，与此同时，E集合中也将剔除该链路。(6)遍历完毕，延续深度搜索算法检测图T连通性，如果不连通，则将当前最大干扰阈值进行向上调整，执行步骤(3)，否则执行步骤(7)。(7)算法执行完毕，得到结果拓扑控制图T=(V，ETATC)，此时的最大干扰阈值RI-threshold则为当前结果拓扑控制图T中的RI(T)值。

5拓扑结构性质分析

TATC是一个贪心算法。在进行拓扑控制时，在结果拓扑图T中的链路还未达到所需时，此时，算法中设定的RI-threshold阈值参数相当于当前的目标函数。把所有符合当前的全局最大干扰阈值条件下的链路都会包含在ETATC集合中，前提是该链路的加入不造成T中有环，如果造成环，直接在初始G中丢弃该链路，如果符合当前添加情况，也需在G中剔除该链路。继续检测拓扑图T是否为连通图为该算法的出口的关键，如果不为连通图，需增大RI-threshold阈值参数，继续上述的步骤(3)。显而易见，G图中有m条链路，n个节点，每次遍历的是当前G中链路集合。RI-threshold阈值参数在算法中逐步增加，直到图T构成了一个连通图。因此，步骤(3)中需要至多遍历RI-threshold×m次。其中，RI-threshold的取值范围的上限是n－1，步骤(4)、步骤(5)中会剔除一些冗余的链路，步骤(3)再次遍历时其链路集合工作负荷逐渐减轻。同理，步骤(6)对图T的连通性需检测RI-threshold次。其中，算法从e(u，v)=E(u，v)∈V，ETATC={•}开始，重复执行以下的操作:在所有e(u，v)=E找到符合一条符合当前RI-threshold阈值参数的边加入集合ETATC，同时在原集合E中删除该边，直至ETATC中有n－1条边，即图T为极小连通图。算法的时间复杂度为O(n2)。如图3所示，16个节点的一维指数链，使用TATC算法所得的结构拓扑图中产生的最大干扰RI(T)=5，而根据本文第2节中指出的最近邻算法则在该链路上产生的RI(T)=14。

6性能仿真与分析

为评估TATC算法的有效性，根据文献［8］所介绍的指数链特征采用UDG模型分别构建一维指数链以及二维指数链的初始拓扑结构。如图4、图5所示，横坐标表示当前一维指数链网络中的节点数，纵坐标分别表示当前网络中节点的最大的干扰值、网络节点的平均干扰值。图中比较了最近邻算法以及本文算法在一维指数链产生的拓扑图中节点中的最大干扰值以及平均干扰值。与最近邻算法相比，TATC算法显著减小了网络中节点的最大干扰值、平均干扰值，而且随着节点数的增加，拓扑控制后的拓扑图的最大干扰、平均干扰增长幅度较慢。图6、图7仿真的是在区域1000m×1000m的区域中，据二维指数链特性［7］排布50个～400个节点，上述的2种算法在该网络环境产生的拓扑结构图中的节点的最大干扰值以及平均干扰值。可以明显看到，采用TATC算法的网络中的最大干扰值、平均干扰值的数值优于最近邻算法。

7结束语

本文设计一种基于最大干扰值阈值调节的拓扑控制算法。该算法以网络连通性、拓扑结构干扰弱化性为目标函数，对干扰阈值不断自适应调节，直到构造成所需的网络拓扑结构。实验结果表明，在指数链模型上，该算法能控制节点的最大干扰值在构建拓扑结构中趋于缓慢增长，比最近邻算法取得了更好的干扰优化效果。但该算法还需进一步改善并推广至其他网络模型。今后将从网络容错性能和适用性方面上继续改进该算法，以提升网络的抗毁性，降低算法的局限性。

作者：谢晓虹 曾碧卿 单位：华南师范大学计算机学院 华南师范大学软件学院