弹性拓扑控制技术研究

陈 雯，孙红光，李建东，盛 敏

(西安电子科技大学ISN国家重点实验室，陕西 西安710071)

弹性拓扑控制技术研究

陈 雯，孙红光，李建东，盛 敏

(西安电子科技大学ISN国家重点实验室，陕西 西安710071)

为了提高无线自组织网络的鲁棒性，针对现有的拓扑控制技术不能解决网络中一个信道被干扰且多个节点同时失效而造成的网络分割问题，提出了一种弹性可重构的二信道连通且k点连通的分布式拓扑控制方法，该方法可根据网络环境的变化动态改变网络的拓扑结构，实现在网络任意一个信道被干扰的情况下仍能维持k点连通。仿真结果表明，相比于现有的拓扑控制算法，所提方法不仅能够增强网络的鲁棒性，还能降低节点能耗，延长网络生存期。

无线自组织网络；弹性；拓扑控制

AbstractThe existing topology control techniques can’t eliminate network partition caused by an interfered channel and multiple simultaneously inactive nodes in network.In order to resolve these problems and enhance the robustness of wireless ad hoc networks,this paper proposes a resilient and reconfigurable distributed topology control algorithm.The proposed algorithm can dynamically change the network topology structure based on the variation of network environment,and achieve the 2-channel and k-vertex connectivity when a channel in network is interfered.Our simulations results show that compared with the current topology control algorithm,the proposed algorithm can not only improve the robustness of network topology,but also reduce the node energy consumption and prolong the network lifetime.

Keywordswireless ad hoc networks;resilience;topology control

0 引言

无线自组织网络[1]是由多个节点组成、采用无线通信方式、动态组网的多跳对等网络。与具有基础设施的蜂窝通信网络不同，无线自组织网络无需固定的基础设施，能够更加快速、便捷、高效地部署，被广泛应用于诸多领域，如：抗灾抢险、军事行动、环境监控和医疗事业等[2]。然而，由于缺乏中心控制节点，自组织网络极易遭受干扰和破坏，导致网络性能下降，甚至造成网络分割而无法正常运行。为了使得网络在干扰不可预测或节点被破坏的情况下仍能正常运行且保证数据传输的高可靠性，网络拓扑结构需要具备弹性可伸缩的特征。弹性网络是指网络能够对外界环境的变化及时感知，通过对自身的拓扑结构、路由策略和传输策略等的自适应重构，削弱外界干扰带来的负面影响，维持一定的网络性能[3]。作为上层通信协议的底层支撑，拓扑结构是网络节点间互联互通的基础。良好的拓扑结构能够延长网络的生存期，增强网络的鲁棒性，保证网络节点间始终存在基本通信路径[4]。因此，本文重点研究弹性网络的拓扑控制技术，通过动态构建弹性网络拓扑，并根据环境变化自适应调整拓扑结构，使得网络在多变的环境下始终能维持较好的拓扑形态，实现网络性能的基本保障。

1 现有弹性拓扑控制技术及其存在的问题

文献[5-6]以最小化网络的能耗为目标，研究了低能耗拓扑的构建方法。文献[7-8]以延长网络的生存期为目标，利用功率控制技术来减小用户之间的干扰。文献[9-11]以提高网络的整体吞吐量为目标，分别从减小网络的干扰源数目、最大化并传节点数和构建网络中任意节点之间的最小干扰路径来对网络拓扑进行控制。为了解决网络中某些节点因天气原因或电池耗尽而失效导致的网络拓扑的割裂问题，需要构建高容错性的网络拓扑，以提升网络的鲁棒性。文献[12-16]以构建具有k点连通特性的网络拓扑为目标，采用功率控制等手段来提高网络拓扑的容错性，典型的如FLSS算法[14]。文献[17-19]以构建具有k边连通特性的网络拓扑为目标，保证网络中任意k-1条边被移除时，剩余的网络仍可保持连通，典型算法如LTRT算法[19]。然而，当网络中某一信道被干扰时，k点或k边连通算法将无法保证网络的连通特性，这是因为工作在被干扰信道上的多个节点可能同时失效，且失效的节点数目是不确定。为了改进这些问题，文献[20-22]在多信道认知无线网络中研究了授权信道被干扰时次级用户网络的连通性问题，提出了保证二信道连通特性的中心式和分布式算法，可在任意一个信道被干扰时，仍保持次级用户网络的基本连通性，典型的如DBCC算法[20]。

由于无线网络的无线信道广播特性以及资源受限特性，网络中某些信道和节点极易同时失效，造成网络分割，使网络无法正常运行。这种情况下，上述单纯基于k点、k边以及二信道的连通拓扑控制方法不再适用，如图1所示。

图1 一个信道被干扰和一个节点同时失效对二信道连通网络的影响

图1(a)是一个二信道连通网络，同时也是一个两点和两边连通网络，当网络中的一个信道被干扰后的网络变为基本连通，如图1(b)所示，在这种情况下如果网络中的某个节点失效则可能导致网络分割，如图1(c)所示。针对上述情况，提出了一种二信道连通且k点连通的拓扑控制方法，该方法能够保证在网络中的任意一个信道被干扰，同时多个节点失效的请况下，该网络仍能达到基本连通。

2 二信道连通且k点连通拓扑控制技术

2.1 系统模型

本文考虑一种具有n个用户的自组织网络，每个用户的功率Pu在其最大功率约束范围之内可以自适应调节，即0

③ 二信道连通：当网络中存在一个干扰源对网络中正在使用的某个信道进行干扰时，工作在该信道上的所有用户均停止数据的收发，这种情况下，网络中使用其他信道的节点间仍至少存在一条路径，则称该网络为二信道连通。

④ 冲突图：用户在相同的信道上传输数据可能会产生相互干扰，则在网络G中，用CG=(V(CG),E(CG))来表示用户的相互干扰冲突图，其中V(CG)=V(G)，E(CG)表示用户潜在干扰的无向边集合。

⑤ 冲突：如果2个用户u和v在图CG中存在一条无向边，则两用户相互冲突。

⑥ 冲突度：与用户u相互冲突用户的个数，称为该用户的冲突度。

2.2 算法描述

利用二信道连通且k点连通分布式算法构网络拓扑主要分为4个阶段：信息交互阶段、拓扑控制阶段、功率控制阶段和信道分配阶段。下面给出4段阶段具体工作原理。

2.2.1 信息交互阶段

2.2.2 拓扑控制阶段

2.2.3 功率控制阶段

每个节点通过局部泛洪方式，将本地边信息和冲突节点信息广播至Su中的所有节点，同时根据收集的其他节点本地信息更新自身本地拓扑和冲突节点集；根据更信后的Su，每个节点将功率调整至能够覆盖Su中最远一跳节点。

2.2.4 信道分配阶段

通过局部泛洪方式，每个节点可以得到其相应冲突节点的冲突度，冲突度大的节点拥有分配信道的较高优先权，待大于自身冲突度的冲突节点进行信道分配后，本节点即可进行信道分配，并将分配结果发送给其冲突节点，分配时要求相互冲突的节点分配不同信道。

根据以上算法步骤，给出了构建二信道连通且2点连通拓扑结构的拓扑控制阶段示意图，如图2所示。

图2 拓扑控制阶段示意

3 仿真及结果分析

3.1 仿真场景

在仿真场景中，网络节点随机均匀分布在一个1 000 m×1 000 m的二维平面区域中，将接收信噪比SNR的门限值β设为-80 dBm，路径损耗因子α取值为4；网络中所有节点采用相同的最大发射功率，其中最大发射功率Pmax=256 mW，对应的最大传输半径Rmax=400 m；假设干扰源会影响到网络的所有用户。

3.2 仿真结果分析

图3～图7给出了50节点场景下本方法生成的网络拓扑。由图3～图7可以看出，本方法生成的拓扑在网络任意信道被干扰后，网络仍然是k-1点连通。

图3 最大功率网络拓扑结构

图4 算法生成的网络拓扑结构

图5 一个信道失效后的网络拓扑结构

图6 一个信道和一个节点失效后的网络拓扑结构

图7 一个信道和两个节点失效后的网络拓扑结构

本文方法与现有最大功率拓扑MaxPower对节点平均传输半径的不同k值进行仿真如图8所示。可以看出，随着网络中用户数的增多，最大功率拓扑MaxPower的平均传输半径保持不变，均为400 m，而本文方法的平均传输半径随着网络中用户节点数的增加不断减小，而随着k的增加，平均传输半径不断增加；同时，当k=2时，本方法的传输半径小于CBCC算法，可见本方法能很好地减小节点的能耗，增大网络的生存期。

图8 网络节点传输半径随网络节点数的变化

本文方法与现有最大功率构造方法MaxPower相比，实现二信道连通且k点连通的平均所需信道数的仿真如图9所示。

图9 网络平均所需信道数随网络节点数的变化

从图9中可以看出，随着网络中用户节点数的增多，最大功率拓扑构造方法MaxPower的平均所需信道数呈线性增长，所提算法平均所需信道数较少，且随着网络中用户节点数或k值的增大，网络平均所需信道数缓慢增长，同时当k=2时所提算法的平均所需信道数小于CBCC算法。

从上述分析可以得出本文方法不仅大大节约了信道资源，而且保证了网络的k点连通，从而使得网络具有很好的鲁棒性。

4 结束语

针对现有拓扑控制存在的问题，本文考虑了无线自组织网络中无线信道受干扰和节点硬件受损坏两方面对网络产生的影响，提出了一种二信道连通且k点连通的拓扑控制算法，解决了网络中某个信道不可用且某些节点由于内在或外在因素也不可用时造成网络分割的问题。仿真结果证明，该算法可以保证当网络中的任意一个信道被干扰时，网络仍然k-1点连通。与传统的最大功率拓扑相比，随着用户数或k值的增大，算法的最大所需信道数缓慢上升，说明算法的可扩展性强。本文算法仅针对网络某一信道受干扰且多个节点同时失效对网络连通性的影响。在下一步的工作中，将考虑当网络中多个信道同时受干扰且多个节点同时失效时对网络产生的影响，提出增强网络鲁棒性的方法。

[1] 于宏毅.无线移动自组织网[M].北京:人民邮电出版社,2005.

[2] 甄岩,李祥珍.移动自组织网络发展与应用展望[J].数字通信,2010,5(9)：31-33.

[3] 杨明华,张法江,郑建群,等.网络弹性技术研究[J].信息安全与技术,2014,5(9):36-40.

[4] 李轩.认知无线网络的拓扑控制方法研究[D].西安：西安电子科技大学博士论文,2014.

[5] RAMANATHAN R,ROSALES-HAINR.Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment[C]∥INFOCOM 2000.Nineteenth Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.IEEE Xplore,2000:404-413.

[6] KIROUSIS L M,KRANAKIS E,KRIZANC D,et al.Power Consumption in Packet Radio Networks[J].Theoretical Computer Science,2000,243(1-2)：289-305.

[7] BURKHART M,VON RICKENBACH P,WATTENHOFER R,et al.Does Topology Control Reduce Interference?[C]∥ACM International Symposium on Mobile Ad Hoc NETWORKING and Computing.ACM,2004:9-19.

[8] MOAVENI-NEJAD K,LI X-Y.Low-Interference Topology Control for Wireless Ad-Hoc Networks[J].Ad Hoc & Sensor Wireless Networks,2005,1(1-2)：41-64.

[9] RAJARAMAN R.Topology Control and Routing in Ad Hoc Networks：A Survey[J].ACM SIGACT News,2002,33(2):60-73.

[10] GOMEZ J,CAMPBELL A T.Variable-Range Transmission Power Control in Wireless Ad Hoc Networks[J].IEEE Transactions on Mobile Computing,2007,6(1)：87-99.

[11] SANTI P.Topology Control in Wireless Ad Hoc and Sensor Networks[J].ACM Computing Surveys,2005,37(2):164-194.

[12] DAS A K,MESBAHI M.K-node Connected Power Efficient Topologies in Wireless Networks：Asemidefinite Programming Approach[C]∥Global Telecommunications Conference.GLOBECOM.IEEE.IEEE Xplore,2005:1-6.

[13] JIA X,KIM D,MAKKI S,et al.Power Assignment for k-Connectivity in Wireless Ad Hoc Networks[C]∥INFOCOM 2005.Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE,2005:2206-2211.

[14] LI N,HOU J.Localized Fault-Tolerant Topology Control in Wireless Ad Hoc Networks[J].IEEE Transactions on Parallel & Distributed Systems,2006,17(4):307-320.

[15] HAJIAGHAYI M,IMMORLICA N,MIRROKNI V S.Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks[J].IEEE/ACM Transactions on Networking,2007,15(6):1345-1358.

[16] WANG F,THAI M T,LI Y,et al.Fault-Tolerant Topology Control for All-to-One and One-to-All Communication in Wireles Networks[J].IEEE Transactions on Mobile Computing,Mar.2008,7(3):322-331.

[17] WANG X,SHENG M,LIU M,et al.RESP：A k-Connected Residual Energy-Aware Topology Control Algorithm for Ad Hoc Networks[C]∥IEEE WCNC,2013:1009-1014.

[18] LI L,HALPERN J Y,BAHL P,et al.A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks[J].IEEE/ACM Trans.Networking,2005,13(1):147-159.

[19] MIYAO K,NAKAYAMA H,ANSARI N,et al.LTRT：An Efficient and Reliable Topology Control Algorithm for Ad-Hoc Networks[J].IEEE Transactions on Wireless Communications,2009,8(12):6050-6058.

[20] WANG X,SHENG M,ZHAI D,et al.Achieving Bi-Channel-Connectivity with Topology Control in Cognitive Radio Networks[J].IEEE Journal on Selected Areas in Communications,2014,32：2163-2176.

[21] LIU H,ZHOU Y,CHU X,et al.Generalized-Biconnectivity for Fault Tolerant Cognitive Radio Networks[C]∥International Conference on Computer Communications and Networks.IEEE,2012:1-8.

[22] ZHAI D,WANG X,SHENG M,et al.Bi-Channel-Connected Topology Control in Cognitive Radio Networks[C]∥Vehicular Technology Conference.IEEE,2014:1-5.

StudyonResilientTopologyControlTechniques

CHEN Wen,SUN Hong-guang,LI Jian-dong,SHENG Min

(StateKeyLabofISN,XidianUniversity,Xi’anShaanxi710071,China)

TN915.01

A

1003-3106(2017)11-0006-06

陈雯女，(1991—)，硕士研究生。主要研究方向：分布式无线网络的拓扑控制技术。

10.3969/j.issn.1003-3106.2017.11.02

陈雯,孙红光,李建东,等.弹性拓扑控制技术研究[J].无线电工程,2017,47(11):6-11.[CHEN Wen,SUN Hongguang,LI Jiandong,et al.Study on Resilient Topology Control Techniques[J].Radio Engineering,2017,47(11):6-11.]

2017-07-06

国家自然科学基金资助项目(61231008)；西安电子科技大学基本科研业务费基金资助项目(XJS16036, JB160103)。

孙红光男，(1985—)，博士，讲师，硕士生导师。主要研究方向：异构网络的资源管控方法、D2D通信技术和超密集网络的性能分析等。