陳 雯，孫紅光，李建東，盛 敏

(西安電子科技大學ISN國家重點實驗室，陜西 西安710071)

彈性拓撲控制技術研究

陳 雯，孫紅光，李建東，盛 敏

(西安電子科技大學ISN國家重點實驗室，陜西 西安710071)

為了提高無線自組織網絡的魯棒性，針對現(xiàn)有的拓撲控制技術不能解決網絡中一個信道被干擾且多個節(jié)點同時失效而造成的網絡分割問題，提出了一種彈性可重構的二信道連通且k點連通的分布式拓撲控制方法，該方法可根據網絡環(huán)境的變化動態(tài)改變網絡的拓撲結構，實現(xiàn)在網絡任意一個信道被干擾的情況下仍能維持k點連通。仿真結果表明，相比于現(xiàn)有的拓撲控制算法，所提方法不僅能夠增強網絡的魯棒性，還能降低節(jié)點能耗，延長網絡生存期。

無線自組織網絡；彈性；拓撲控制

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]是由多個節(jié)點組成、采用無線通信方式、動態(tài)組網的多跳對等網絡。與具有基礎設施的蜂窩通信網絡不同，無線自組織網絡無需固定的基礎設施，能夠更加快速、便捷、高效地部署，被廣泛應用于諸多領域，如：抗災搶險、軍事行動、環(huán)境監(jiān)控和醫(yī)療事業(yè)等[2]。然而，由于缺乏中心控制節(jié)點，自組織網絡極易遭受干擾和破壞，導致網絡性能下降，甚至造成網絡分割而無法正常運行。為了使得網絡在干擾不可預測或節(jié)點被破壞的情況下仍能正常運行且保證數(shù)據傳輸?shù)母呖煽啃?，網絡拓撲結構需要具備彈性可伸縮的特征。彈性網絡是指網絡能夠對外界環(huán)境的變化及時感知，通過對自身的拓撲結構、路由策略和傳輸策略等的自適應重構，削弱外界干擾帶來的負面影響，維持一定的網絡性能[3]。作為上層通信協(xié)議的底層支撐，拓撲結構是網絡節(jié)點間互聯(lián)互通的基礎。良好的拓撲結構能夠延長網絡的生存期，增強網絡的魯棒性，保證網絡節(jié)點間始終存在基本通信路徑[4]。因此，本文重點研究彈性網絡的拓撲控制技術，通過動態(tài)構建彈性網絡拓撲，并根據環(huán)境變化自適應調整拓撲結構，使得網絡在多變的環(huán)境下始終能維持較好的拓撲形態(tài)，實現(xiàn)網絡性能的基本保障。

1 現(xiàn)有彈性拓撲控制技術及其存在的問題

文獻[5-6]以最小化網絡的能耗為目標，研究了低能耗拓撲的構建方法。文獻[7-8]以延長網絡的生存期為目標，利用功率控制技術來減小用戶之間的干擾。文獻[9-11]以提高網絡的整體吞吐量為目標，分別從減小網絡的干擾源數(shù)目、最大化并傳節(jié)點數(shù)和構建網絡中任意節(jié)點之間的最小干擾路徑來對網絡拓撲進行控制。為了解決網絡中某些節(jié)點因天氣原因或電池耗盡而失效導致的網絡拓撲的割裂問題，需要構建高容錯性的網絡拓撲，以提升網絡的魯棒性。文獻[12-16]以構建具有k點連通特性的網絡拓撲為目標，采用功率控制等手段來提高網絡拓撲的容錯性，典型的如FLSS算法[14]。文獻[17-19]以構建具有k邊連通特性的網絡拓撲為目標，保證網絡中任意k-1條邊被移除時，剩余的網絡仍可保持連通，典型算法如LTRT算法[19]。然而，當網絡中某一信道被干擾時，k點或k邊連通算法將無法保證網絡的連通特性，這是因為工作在被干擾信道上的多個節(jié)點可能同時失效，且失效的節(jié)點數(shù)目是不確定。為了改進這些問題，文獻[20-22]在多信道認知無線網絡中研究了授權信道被干擾時次級用戶網絡的連通性問題，提出了保證二信道連通特性的中心式和分布式算法，可在任意一個信道被干擾時，仍保持次級用戶網絡的基本連通性，典型的如DBCC算法[20]。

由于無線網絡的無線信道廣播特性以及資源受限特性，網絡中某些信道和節(jié)點極易同時失效，造成網絡分割，使網絡無法正常運行。這種情況下，上述單純基于k點、k邊以及二信道的連通拓撲控制方法不再適用，如圖1所示。

圖1 一個信道被干擾和一個節(jié)點同時失效對二信道連通網絡的影響

圖1(a)是一個二信道連通網絡，同時也是一個兩點和兩邊連通網絡，當網絡中的一個信道被干擾后的網絡變?yōu)榛具B通，如圖1(b)所示，在這種情況下如果網絡中的某個節(jié)點失效則可能導致網絡分割，如圖1(c)所示。針對上述情況，提出了一種二信道連通且k點連通的拓撲控制方法，該方法能夠保證在網絡中的任意一個信道被干擾，同時多個節(jié)點失效的請況下，該網絡仍能達到基本連通。

2 二信道連通且k點連通拓撲控制技術

2.1 系統(tǒng)模型

本文考慮一種具有n個用戶的自組織網絡，每個用戶的功率Pu在其最大功率約束范圍之內可以自適應調節(jié)，即0

③ 二信道連通：當網絡中存在一個干擾源對網絡中正在使用的某個信道進行干擾時，工作在該信道上的所有用戶均停止數(shù)據的收發(fā)，這種情況下，網絡中使用其他信道的節(jié)點間仍至少存在一條路徑，則稱該網絡為二信道連通。

④ 沖突圖：用戶在相同的信道上傳輸數(shù)據可能會產生相互干擾，則在網絡G中，用CG=(V(CG),E(CG))來表示用戶的相互干擾沖突圖，其中V(CG)=V(G)，E(CG)表示用戶潛在干擾的無向邊集合。

⑤ 沖突：如果2個用戶u和v在圖CG中存在一條無向邊，則兩用戶相互沖突。

⑥ 沖突度：與用戶u相互沖突用戶的個數(shù)，稱為該用戶的沖突度。

2.2 算法描述

利用二信道連通且k點連通分布式算法構網絡拓撲主要分為4個階段：信息交互階段、拓撲控制階段、功率控制階段和信道分配階段。下面給出4段階段具體工作原理。

2.2.1 信息交互階段

2.2.2 拓撲控制階段

2.2.3 功率控制階段

每個節(jié)點通過局部泛洪方式，將本地邊信息和沖突節(jié)點信息廣播至Su中的所有節(jié)點，同時根據收集的其他節(jié)點本地信息更新自身本地拓撲和沖突節(jié)點集；根據更信后的Su，每個節(jié)點將功率調整至能夠覆蓋Su中最遠一跳節(jié)點。

2.2.4 信道分配階段

通過局部泛洪方式，每個節(jié)點可以得到其相應沖突節(jié)點的沖突度，沖突度大的節(jié)點擁有分配信道的較高優(yōu)先權，待大于自身沖突度的沖突節(jié)點進行信道分配后，本節(jié)點即可進行信道分配，并將分配結果發(fā)送給其沖突節(jié)點，分配時要求相互沖突的節(jié)點分配不同信道。

根據以上算法步驟，給出了構建二信道連通且2點連通拓撲結構的拓撲控制階段示意圖，如圖2所示。

圖2 拓撲控制階段示意

3 仿真及結果分析

3.1 仿真場景

在仿真場景中，網絡節(jié)點隨機均勻分布在一個1 000 m×1 000 m的二維平面區(qū)域中，將接收信噪比SNR的門限值β設為-80 dBm，路徑損耗因子α取值為4；網絡中所有節(jié)點采用相同的最大發(fā)射功率，其中最大發(fā)射功率Pmax=256 mW，對應的最大傳輸半徑Rmax=400 m；假設干擾源會影響到網絡的所有用戶。

3.2 仿真結果分析

圖3～圖7給出了50節(jié)點場景下本方法生成的網絡拓撲。由圖3～圖7可以看出，本方法生成的拓撲在網絡任意信道被干擾后，網絡仍然是k-1點連通。

圖3 最大功率網絡拓撲結構

圖4 算法生成的網絡拓撲結構

圖5 一個信道失效后的網絡拓撲結構

圖6 一個信道和一個節(jié)點失效后的網絡拓撲結構

圖7 一個信道和兩個節(jié)點失效后的網絡拓撲結構

本文方法與現(xiàn)有最大功率拓撲MaxPower對節(jié)點平均傳輸半徑的不同k值進行仿真如圖8所示。可以看出，隨著網絡中用戶數(shù)的增多，最大功率拓撲MaxPower的平均傳輸半徑保持不變，均為400 m，而本文方法的平均傳輸半徑隨著網絡中用戶節(jié)點數(shù)的增加不斷減小，而隨著k的增加，平均傳輸半徑不斷增加；同時，當k=2時，本方法的傳輸半徑小于CBCC算法，可見本方法能很好地減小節(jié)點的能耗，增大網絡的生存期。

圖8 網絡節(jié)點傳輸半徑隨網絡節(jié)點數(shù)的變化

本文方法與現(xiàn)有最大功率構造方法MaxPower相比，實現(xiàn)二信道連通且k點連通的平均所需信道數(shù)的仿真如圖9所示。

圖9 網絡平均所需信道數(shù)隨網絡節(jié)點數(shù)的變化

從圖9中可以看出，隨著網絡中用戶節(jié)點數(shù)的增多，最大功率拓撲構造方法MaxPower的平均所需信道數(shù)呈線性增長，所提算法平均所需信道數(shù)較少，且隨著網絡中用戶節(jié)點數(shù)或k值的增大，網絡平均所需信道數(shù)緩慢增長，同時當k=2時所提算法的平均所需信道數(shù)小于CBCC算法。

從上述分析可以得出本文方法不僅大大節(jié)約了信道資源，而且保證了網絡的k點連通，從而使得網絡具有很好的魯棒性。

4 結束語

針對現(xiàn)有拓撲控制存在的問題，本文考慮了無線自組織網絡中無線信道受干擾和節(jié)點硬件受損壞兩方面對網絡產生的影響，提出了一種二信道連通且k點連通的拓撲控制算法，解決了網絡中某個信道不可用且某些節(jié)點由于內在或外在因素也不可用時造成網絡分割的問題。仿真結果證明，該算法可以保證當網絡中的任意一個信道被干擾時，網絡仍然k-1點連通。與傳統(tǒng)的最大功率拓撲相比，隨著用戶數(shù)或k值的增大，算法的最大所需信道數(shù)緩慢上升，說明算法的可擴展性強。本文算法僅針對網絡某一信道受干擾且多個節(jié)點同時失效對網絡連通性的影響。在下一步的工作中，將考慮當網絡中多個信道同時受干擾且多個節(jié)點同時失效時對網絡產生的影響，提出增強網絡魯棒性的方法。

[1] 于宏毅.無線移動自組織網[M].北京:人民郵電出版社,2005.

[2] 甄巖,李祥珍.移動自組織網絡發(fā)展與應用展望[J].數(shù)字通信,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)；西安電子科技大學基本科研業(yè)務費基金資助項目(XJS16036, JB160103)。

孫紅光男，(1985—)，博士，講師，碩士生導師。主要研究方向：異構網絡的資源管控方法、D2D通信技術和超密集網絡的性能分析等。