一种干扰优化无线传感器网络拓扑控制算法

谢晓虹，曾碧卿

（1.华南师范大学计算机学院，广州510631；2.华南师范大学软件学院，广东佛山528225）

一种干扰优化无线传感器网络拓扑控制算法

谢晓虹1，曾碧卿2

（1.华南师范大学计算机学院，广州510631；2.华南师范大学软件学院，广东佛山528225）

针对如何准确度量无线传感器网络中的干扰，并构建最小化最大干扰值拓扑结构的问题，根据传感器节点的特点以及无线通信机制，提出一种阈值调节的拓扑控制算法。网络中每个节点收集邻居节点相关信息，同时以干扰阈值为目标函数，选取符合当前干扰阈值以及不会使当前拓扑图产生回路的链路进行拓扑构建，直至拓扑连通，实现整个网络中节点最大干扰最小化。仿真结果表明，在无线传感器网络指数链模型下，与最近邻算法相比，该算法生成的拓扑控制结构干扰优化效果更优，并能保证网络的连通性及更有效地延长网络的生存周期。

无线传感器网络；阈值控制；指数链模型；干扰优化；拓扑控制

1 概述

无线传感器网络（Wireless Sensor Network，WSN）近年来的快速发展离不开传感器技术、网络无线通信技术、嵌入式技术、分布式信息技术以及微电子制造技术等相关关键技术的日益成熟。它是一种无中心节点的全分布系统，是有针对性对某个监控区域内进行随机投放的若干个传感器节点自组织通过无线电信通信构成网络系统。传感器节点可根据其内置的不同功能的传感器，感知所在的周遭环境中人们的感兴趣的数据，如温度、红外线、湿度、压力、土壤成分、移动物体的属性等［1］。正因为无线传感器网络的无处不在的感知技术优势，它有着非常广泛的应用前景。在军事领域、环境应用、医疗事业、工业应用以及商用等多个领域都占有意义非凡的一席之地。显然，无线传感器网络是当前多学科高度交叉、前沿的热点研究之一。无线传感器网络中传感器节点一般由数据采集模块、数据处理和控制模块、无线通信模块和供电模块组成［2］。而正因为它自身的物理特性因素，其电量供给［3］有限成为无线传感器网络生命期主要的瓶颈问题之一。

早期的经典拓扑控制算法思想主要是借助控制节点传输功率或稀疏化网络拓扑图［4］，达到降低节点信道之间干扰的目的。近阶段有一些研究者，指出机械性减少边的数量、长度及邻节点度不一定就能保证节点之间的干扰现象也降低［5-7］，并就干扰模型的定义和度量方法进行了研究。其中，定义的干扰模型有基于发送节点的干扰模型、基于接收节点的干扰模型。基于不同的干扰模型，文献［8］指出二维及二维以上的网络模型的拓扑控制干扰优化问题已被证明属于NP问题。

在上述拓扑控制算法的研究中，很少有以降低全局网络节点中的最大干扰值作为首要目标，干扰的存在不仅会影响通信质量，而且造成数据不断重传损耗电量缩短网络生命周期［9］，大部分算法针对的都是节点分布比较均匀的网络情况，而对于节点间非均匀分布的网络情况，如指数链模型无线传感器网络下的干扰优化效果甚微。本文将采用基于接收节点干扰模型，以干扰阈值作为重要考虑因素，以最小化最大干扰值、网络连通性为算法首要目标，对一维指数链模型的无线传感器网络节点的邻居节点、节点传输半径和网络节点数、节点所受的干扰进行研究，设计一种启发式算法，并将其算法思想沿用至二维网络模型中，保证其网络连通性的同时达到优化最大干扰值的目的。

2 相关工作

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

如图1所示，由文献［7］指出最近邻算法产生的拓扑结构节点中受到的最大的干扰达到n-2∈n。显然，一个节点在有n个节点的网络中，在最坏的情况下，受到除已的其他节点干扰，即干扰值为n-1，可见，最近邻算法在一维指数链上干扰优化的改进效果不如人意。

图1 最近邻算法构建拓扑控制的过程

3 干扰模型要素

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

3.1 单位圆盘图

在UDG图G=（V，E）中，V为图G中顶点的集合，E为图G的任意顶点存在边的集合。V中的每个顶点都有以该顶点为中心的等半径的圆一一对应，假设所有节点具有相同的通信半径上限rmax，当且仅当u顶点和v顶点之间的欧氏距离小于等于rmax时，则e（u，v）∈E。UDG图顶点的通信半径r，一般指定为单位1，关系数学表达式如下：

根据上述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'），节点受到干扰是这样定义的：

如图2所示，每个节点所选用的传输半径受其最远的邻居节点影响，则u节点选用k1作为它的通信半径，v节点选用k2作为通信半径。根据式（2），可计算u，v节点所受到的干扰值分别为RI（u）=2，RI（v）=3。

图2 基于接收者的干扰模型

（5）衡量结果拓扑图的干扰值是由众节点所受的干扰度最大的那个节点的干扰值所决定。根据3.1节中指出通信功率的上限MaxPower，则同样的，传感器节点都受限于同一个最大通信半径值MaxRadiu，而节点的通信半径取值随着拓扑控制调节控制在［0，MaxRadiu］区间，也就是说，无线传感器网络中的传感器节点初始条件都是统一的，当中的最早消耗完电量的节点则是受到干扰最多的那个节点，这也决定了当前无线传感器网络的生命期的长度。因此，本文取图T节点中RI（v）值最大者作为该算法产生的拓扑图干扰：

（6）图2中受到的平均干扰可定义为：

4 本文算法设计思想

根据上述采用的基于接收者的网络拓扑干扰模型，本文提出了一种基于干扰阈值调节的拓扑控制（Threshold Adaptive Topology Control，TATC）算法。TATC算法思想主要如下：

（1）建立模型：每个节点需要与其他节点进行消息交互，收集搭建链路的距离即通信半径的数据。考虑在理想状态下，如果网络中任意u，v节点能通过一跳距离能收到消息响应成功，则根据式（1），它们之间的通信链路距离是不超过设定的单位通信半径上限单位1，则图G中u，v点中存在直接链路，即e（u，v）∈E。消息信息收集处理完毕，可搭建成初始拓扑图G：

（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-。

证明：如图3所示，一维指数链上有n个节点按照2i倍数增长分布。可观察到RI-threshold阈值参数变化，就会有新的节点与最左边的节点相连，RI-threshold为1时，从左至右，v0连接v1，为2时，v2连接v3并连接v0，为3时，v4连接v0，并连接v5，v6，以此类推，当此时的RI-threshold为RI（n）（RI（n）＞2）时，其至少能连（（RI（n）-1）+（RI（n）-2）+…+1+2）个节点：threshold阈值参数的边加入集合ETATC，同时在原集合E中删除该边，直至ETATC中有n-1条边，即图T为极小连通图。算法的时间复杂度为O（n2）。

定理 在一维指数链图G，应用TATC算法构造拓扑图的

图3 一维指数链上本文算法产生的结果拓扑结构

如图3所示，16个节点的一维指数链，使用TATC算法所得的结构拓扑图中产生的最大干扰RI（T）=5，而根据本文第2节中指出的最近邻算法则在该链路上产生的RI（T）=14。

6 性能仿真与分析

为评估TATC算法的有效性，根据文献［8］所介绍的指数链特征采用UDG模型分别构建一维指数链以及二维指数链的初始拓扑结构。

如图4、图5所示，横坐标表示当前一维指数链网络中的节点数，纵坐标分别表示当前网络中节点的最大的干扰值、网络节点的平均干扰值。图中比较了最近邻算法以及本文算法在一维指数链产生的拓扑图中节点中的最大干扰值以及平均干扰值。与最近邻算法相比，TATC算法显著减小了网络中节点的最大干扰值、平均干扰值，而且随着节点数的增加，拓扑控制后的拓扑图的最大干扰、平均干扰增长幅度较慢。

图4 一维指数链网络中的最大干扰值比较

图5 一维指数链网络中的平均干扰值比较

图6 、图7仿真的是在区域1 000 m×1 000 m的区域中，据二维指数链特性［7］排布50个～400个节点，上述的2种算法在该网络环境产生的拓扑结构图中的节点的最大干扰值以及平均干扰值。可以明显看到，采用TATC算法的网络中的最大干扰值、平均干扰值的数值优于最近邻算法。

图6 二维指数链网络中的最大干扰值比较

图7 二维指数链网络中的平均干扰值比较

7 结束语

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

［1］ 吴成洪.无线传感器网络拓扑控制研究［D］.西安：西安电子科技大学，2010.

［2］ 江 勇，赵 倩.一种应用强化学习的自适应无线传感器网络路由算法［J］.小型微型计算机系统，2013，34（8）：1723-1727.

［3］ Deshpande A，Montiel C，McLauchlan L.W ireless Sensor Networks——A Comparative Study for Energy Minimization Using Topology Control［C］//Proceedings of the 6th Annual IEEE Green Technologies Conference. Washington D.C.，USA：IEEE Press，2014：44-48.

［4］ 任月清，徐立新.无线传感器网络拓扑连通性与稀疏性研究［J］.传感技术学报，2011，24（7）：1038-1042.

［5］ Burkhart M，Von R P，Wattenhofer R，et al.Does Topology Control Reduce Interference［C］//Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA：ACM Press，2004：9-19.

［6］ Santi P.Topology Control in Wireless Ad Hoc and Sensor Networks［J］.ACM Computing Surveys，2005，37（2）：164-194.

［7］ Rickenbach P V，Schmid S，Wattenhofer R，et al.A Robust Interference Model for Wireless Ad-hoc Networks［C］// Proceedings of the 5th International Workshop on Algorithms for Wireless，Mobile，Ad Hoc and Sensor Networks. Washington D.C.，USA：IEEE Press，2005：239-247.

［8］ Tan Haisheng，Lou Tiancheng，Wang Yuexuan，et al. Exact Algorithm s to Minimize Interference in Wireless Sensor Networks［J］.Theoretical Computing Science，2011，412（50）：6913-6925.

［9］ 李晓鸿，王文艳，王 东.一种最大化Ad Hoc网络生存期的拓扑控制算法［J］.计算机研究与发展，2013，50（3）：461-471.

［10］ 孙 超，尹荣荣，郝晓辰，等.异构无线传感器网络支配集拓扑控制算法［J］.软件学报，2011，22（9）：2137-2148.

［11］ Moscibroda T，Wattenhofer R.Minimizing Interference in Ad Hoc and Sensor Networks［C］//Proceedings of Joint Workshop on Foundations of Mobile Computing. New York，USA：ACM Press，2005：24-33.

［12］ 路 纲，周明天，牛新征，等.无线网络邻近图综述［J］.软件学报，2008，19（4）：888-911.

［13］ Rickenbach V P，Wattenhofer R，Zollinger A.Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks［J］.IEEE/ACM Transactions on Networking，2009，17（1）：172-185.

编辑 刘 冰

An Interference-optimization Topology Control Algorithm in Wireless Sensor Network

XIE Xiaohong1，ZENG Biqing2
（1.School of Computing，South China Normal University，Guangzhou 510631，China；2.School of Software，South China Normal University，Foshan 528225，China）

Researching the solution to the problem that how to measure the interference accurately and construct the topological structure with minimizing interference in the Wireless Sensor Network（WSN），it proposes topology control algorithm of threshold adjustment.It can minimize the interference heuristically in exponential node chain network model. In the network，each node collects useful information of its neighbor nodes，and at the same time，with the interference threshold as the objective function，it selects the link between the nodes，which are in line with current interference threshold and don't make the current topology generate loop path.It constructs topology until the topology becomes connected graph，which can minimize the maximum interference among the nodes in the network.Simulation results show that，the new algorithm compared with the nearest algorithm on the exponential node chain network model of WSN，the interference generated topology control structure optimization effect is better，and can guarantee the connectivity of the network and more effectively prolong the lifecycle of the network.

Wireless Sensor Network（WSN）；threshold control；index chain model；interference-optimization；topology control

谢晓虹，曾碧卿.一种干扰优化无线传感器网络拓扑控制算法［J］.计算机工程，2015，41（11）：131-134，141.

英文引用格式：Xie Xiaohong，Zeng Biqing.An Interference-optimization Topology Control Algorithm in Wireless Sensor Network［J］.Computer Engineering，2015，41（11）：131-134，141.

1000-3428（2015）11-0131-04

A

TP391

10.3969/j.issn.1000-3428.2015.11.023

国家自然科学基金资助项目（71272144）；广州市科技计划基金资助项目（2013KP084）。

谢晓虹（1990-），女，硕士研究生，主研方向：无线传感器网络；曾碧卿，教授、博士。

2014-10-29

2014-12-23 E-m ail：zengbiqing0528@163.com