彈性拓撲控制技術(shù)研究

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

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

彈性拓撲控制技術(shù)研究

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

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

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

無線自組織網(wǎng)絡；彈性；拓撲控制

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 引言

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

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

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

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

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

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

2 二信道連通且k點連通拓撲控制技術(shù)

2.1 系統(tǒng)模型

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

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

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

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

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

2.2 算法描述

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

2.2.1 信息交互階段

2.2.2 拓撲控制階段

2.2.3 功率控制階段

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

2.2.4 信道分配階段

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

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

圖2 拓撲控制階段示意

3 仿真及結(jié)果分析

3.1 仿真場景

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

3.2 仿真結(jié)果分析

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

圖3 最大功率網(wǎng)絡拓撲結(jié)構(gòu)

圖4 算法生成的網(wǎng)絡拓撲結(jié)構(gòu)

圖5 一個信道失效后的網(wǎng)絡拓撲結(jié)構(gòu)

圖6 一個信道和一個節(jié)點失效后的網(wǎng)絡拓撲結(jié)構(gòu)

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

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

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

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

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

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

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

4 結(jié)束語

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

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

[2] 甄巖,李祥珍.移動自組織網(wǎng)絡發(fā)展與應用展望[J].數(shù)字通信,2010,5(9)：31-33.

[3] 楊明華,張法江,鄭建群,等.網(wǎng)絡彈性技術(shù)研究[J].信息安全與技術(shù),2014,5(9):36-40.

[4] 李軒.認知無線網(wǎng)絡的拓撲控制方法研究[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—)，碩士研究生。主要研究方向：分布式無線網(wǎng)絡的拓撲控制技術(shù)。

10.3969/j.issn.1003-3106.2017.11.02

陳雯,孫紅光,李建東,等.彈性拓撲控制技術(shù)研究[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—)，博士，講師，碩士生導師。主要研究方向：異構(gòu)網(wǎng)絡的資源管控方法、D2D通信技術(shù)和超密集網(wǎng)絡的性能分析等。