航空自組網中面向容錯的中繼節點速度控制*

李 杰，宮二玲，孫志強，劉 偉，謝紅衛

航空自組網中面向容錯的中繼節點速度控制*

李 杰，宮二玲，孫志強，劉 偉，謝紅衛

(國防科技大學 機電工程與自動化學院， 湖南 長沙 410073)

由于飛機節點的通信距離有限，航空自組網的網絡拓撲高動態的變化會導致頻繁的網絡分割并嚴重影響網絡上層應用的正常運行。為了保證飛機節點之間端到端的連通性不受影響，航空自組網必須具備容錯性，即任意一個節點或鏈路失效后網絡仍然連通。通常情況下飛機節點的運動不可控，因此可在網絡中加入一定數量的中繼節點，通過控制中繼節點的運動速度來實現并維持航空自組網的容錯性。提出了一種在線中繼節點速度控制方法，該方法根據網絡當前狀態計算出中繼節點的最佳運動方式，在保證網絡容錯的前提下使得中繼節點在網絡運行時間內所運動的總路程最短。仿真結果表明該中繼節點速度控制方法在航空自組網的容錯控制方面具有潛在的應用前景。

自組織網絡；容錯設計；網絡連通性；速度控制

(CollegeofMechatronicEngineeringandAutomation,NationalUniversityofDefenseTechnology,Changsha410073,China)

航空自組網(AeronauticalAdhocNETwork，AANET)[1]是在配備無線通信設備的飛機之間形成一種特殊的無中心移動自組織網絡(MobileAdhocNETwork，MANET)，為飛機間提供直接的通信服務。AANET的基本思想是在飛機的通信范圍內，飛機之間可以相互交換控制信息和命令數據，而在通信范圍之外的飛機可以通過多跳方式傳遞數據，形成一個空中的MANET。在AANET中，每個飛機不僅僅是收發器，而且還可以起到路由器的作用來轉發數據。與簡單地利用飛行器作為中繼節點進行通信的方式不同，AANET采用動態組網、動態路由和無線中繼等技術，將航空飛行器互連互通，具備自組織、自修復的能力和快速、高效組網的優勢，可滿足特定條件下的軍、民航通信的需求[2]。

在AANET中，飛機節點的高速運動使得網絡拓撲高動態地變化。由于飛機的通信距離有限，在節點較為稀疏的區域，AANET則無法保證飛機之間持續的端到端可靠連接。延遲容忍網絡(Delay-TolerantNetwork，DTN)[3]技術可以解決網絡頻繁分割狀態下的數據通信問題。DTN利用網絡節點的存儲空間對數據進行暫時緩存，并基于“存儲-攜帶-轉發”的路由模式實現節點間的通信。然而DTN的這種路由模式會帶來較大的端到端延遲。AANET中的多數應用對實時性要求很高，所以DTN技術并不能解決AANET的實時通信問題。此外，當AANET應用于戰場環境等一些惡劣的網絡環境時，網絡還要求具有一定的容錯性，即部分節點或通信鏈路失效不會對網絡的連通性產生影響。

實現容錯網絡的拓撲控制方法可分為三類。第一類是通過控制天線的發射功率來改變節點的最大通信距離，進而改變網絡的拓撲結構。其控制目標是使得網絡的拓撲結構達到容錯性要求的同時，網絡消耗的能量最少。該類方法在無線傳感器網絡(WirelessSensorNetwork，WSN)中應用較多[4-5]。而在AANET中，節點的分布區域較廣，即使使用最大的發射功率，網絡拓撲也無法達到容錯性要求。如果網絡中節點的運動方式可控，則可用第二類方法對網絡拓撲進行控制，即：通過控制網絡節點的運動，使得網絡拓撲實現容錯性要求[6]。第三類方法是向網絡中加入額外的中繼節點來重構網絡的拓撲結構，使得網絡拓撲結構滿足容錯性要求[7-10]。因此，可以在AANET中網絡連通性差的區域加入額外的中繼節點(長航時的無人機或其他可控空中平臺)來增強網絡的連通性[11]。由于網絡拓撲的不斷變化，必須通過控制這些中繼節點的運動速度來保持網絡的容錯性要求。考慮到每個中繼節點的能量有限，為了延長其工作時間，在保證網絡容錯性要求的前提下還須使得中繼節點總的運動路程最短。然而，現有的通過中繼節點進行拓撲控制的方法大都是針對靜態網絡來合理配置中繼節點的位置[7-8]，或是在網絡拓撲緩慢變化的網絡中控制中繼節點的運動[9-10]。這些方法都無法應用于網絡拓撲劇烈變化的AANET中。

1 問題描述

假設在二維平面上有w個飛機節點(AirborneNode，AN)和m個中繼節點(RelayNode，RN)。AN和RN都配備了最大通信距離為r的全向天線。令AN的集合記為VA= {a1，a2，…，aw}，其中ai(1≤i≤w)表示第i個飛機節點。令RN的集合記為VR= {r1，r2，…，rm}，其中rj(1≤j≤m)表示第j個中繼節點。在本文中，某網絡節點在二維平面中的位置坐標用表示該節點字符的黑體形式來表示。如，節點ai的位置坐標用矢量ai= (xai, yai)表示，節點rj的位置坐標用矢量rj= (xrj, yrj)表示。位置矩陣A=[a1，a2，…，aw]表示AN集合VA的位置坐標，位置矩陣R=[r1，r2，…，rm]則表示RN集合VR的位置坐標。節點rj在t時刻的瞬時速度用矢量vj(t)表示。所有RN在t時刻的速度用速度矩陣V(t)=[v1(t)，v2(t)，…，vm(t)]表示。給定AN的集合VA，RN的集合VR，以及通信距離r，其拓撲可以用無向圖G=(V，E)來表示，其中V=VA∪VR為頂點集，表示網絡中的空中平臺；E為邊集，表示網絡中任意兩個距離小于r的節點之間形成的通信鏈路的集合。網絡拓撲的容錯性可用圖論中的頂點連通度來度量。如果圖G中任意兩個頂點之間都至少有k條內部頂點不相交的路徑，則稱圖G為頂點k連通。當k=1時，圖G為簡單連通；當k≥2時，稱圖G具有容錯能力，此時網絡的抗毀性較好。由于AANET只要保證AN之間的通信具有容錯性即可。因此，在下文提到圖G為頂點k連通時則表示任意兩個AN之間至少有k條內部頂點不相交的路徑。若網絡總的運行時間為T，網絡的容錯控制問題可以轉化為求RN的速度矩陣V(t)，0 < t ≤ T，使得在保證網絡容錯的前提下，所有RN在時間T內總的移動距離最短。因此，可以抽象為式(1)～(3)的優化問題。

(1)

(2)

(3)

式中：vmax表示RN的最大速度，λt(u, v)表示在t時刻點u和v之間內部頂點不相交路徑的數量。

圖1 在線拓撲控制Fig.1 Online topology control

2 在線拓撲控制

要實現在線拓撲控制，就需要根據網絡的實時狀態得出RN速度矩陣的最優解。用采樣間隔時間Δt將時間t離散化為時間序列n=0，1，…，K，其中，K = ?T/Δt」。從而式(1)～(3)可離散化為

(4)

(5)

(6)

算法1 RN運動的在線控制

3 MCFM問題的求解算法

3.1 算法提出

若si表示某個SP，為了體現RN移動si的位置所要運動的平均距離，定義其成本c(si)為所有RN到si的平均距離，即：

(7)

構造完全圖GC(VA，EC)，其中邊集EC表示任意兩個VA中的點所形成邊的集合。對于EC中的邊(ai，aj)定義其權值c(ai，aj)為：

(8)

圖2 完備加權二部圖Fig.2 Weighted complete bipartite graph

(9)

算法2 MCFM問題的快速算法

圖3 算法2具有較差性能的場景Fig.3 An example of poor performance by Alg.2

3.2 算法的復雜度分析

4 仿真驗證

圖4 仿真模型Fig.4 Simulation model

假設w個AN以速度v在邊長為400km的矩形區域運動。用隨機路點(RandomWayPoint，RWP)[17]運動模型作為AN的運動模型，并將停止時間設為0，來逼真地模擬實際飛機的運動模式。為了提高網絡的連通性，在網絡中加入m個最大速度vmax=800m/s的RN，并設置速度更新間隔Δt=8s。網絡中所有節點的最大通信距離r=100km。總的仿真時間設置為30min。如圖4所示，基于網絡仿真平臺OMNeT++[18]建立仿真模型。在圖4所示的網絡模型中，“relay”模塊代表RN，“host”模塊代表AN。圖5描繪了當v=300m/s，w=12，m=5時3個不同仿真時刻的網絡的拓撲圖。

(a) 仿真時刻為200s(a) At simulation time of 200s

(b) 仿真時刻為260s(b) At simulation time of 260s

(c) 仿真時刻為600s(c) At simulation time of 600s圖5 網絡拓撲Fig.5 Network topology

為了方便研究算法性能，定義以下幾個性能指標。

1)RN總的運動路程(TotalTravelDistance，TTD)：TTD值反映了RN在網絡運行期間所消耗的總能量。為了延長RN的工作時間，要求TTD要盡量的小。

2)2連通率(BiconnectivityRate，BR)：BR定義為網絡為頂點2連通的時間與網絡總的運行時間比值。BR值越大則說明網絡的容錯性越好。

3)相對2連通率(RelativeBiconnectivityRate，RBR)：RBR值反映了RN的運動對網絡2連通率的影響。若向具有w個AN的網絡中加入m個RN，當前網絡的2連通率和原網絡相比所提升的部分除了通過RN的運動所提升的部分外還包括由于網絡節點密度增加所提升的值。RBR值可以由網絡當前的BR值減去當網絡中只有w+m個AN時的值得到。若令BRo表示當網絡中只有w+m個AN時的2連通率，則有

RBR=BR-BRo

(10)

4.1 性能分析

為了便于對算法性能進行分析，網絡中AN數量要選擇合適的值以便能產生顯著的控制效果。由于網絡BR值與網絡中節點密度有關，為了方便研究RN運動對網絡性能的影響，網絡的初始BR值不能太大。因此，AN的數量太大會導致較大的初始BR值，則算法不會產生顯著的控制效果。而AN的數量過少則無法證明算法在實際AANET中的有效性。實驗證明，當網絡中AN數為12左右時，網絡具有較小的BR值(0.05左右)。因此，在下面的仿真實驗中設置w=12。由于當前飛機的巡航速度一般在1馬赫以下，所以在對算法性能分析時只考慮AN以亞音速巡航的場景。研究不同數量的RN在低動態環境(v=100m/s)和高動態環境(v=300m/s)下對網絡性能的影響。RN的數量與各個性能指標的關系如圖6所示。如圖6(a)所示，網絡的2連通率隨著RN的增加而顯著增大，而低動態的網絡環境更容易獲得較高的BR值。這也證明該RN運動控制算法在AANET的容錯控制方面的有效性。從圖6(b)可以看出，網絡的相對2連通率并不是隨著RN數量的增加而單調增加，而是在RN的數量大于5后出現減少的趨勢。所以，當RN數量增加到一定值之后，網絡BR值的提高更多的是依賴網絡節點密度的增加。根據式(10)可知，當網絡的節點總數達到一定數量之后，BRo值的增加占主要部分，使得RBR值出現減少的趨勢。而RBR值依賴于RN的運動，所以當RN的數量大于5后，TTD的值隨著RN數目增加的趨勢也變得不顯著，如圖6(c)所示。

(a) 網絡2連通率(a) Biconnectivity rate of the network

(b) 網絡相對2連通率(b) Relative biconnectivity rate of the network

(c) RN總的運動路程(c) Total travel distance of RNs圖6 性能分析Fig.6 Performance analysis

4.2 性能比較

令w=12，m=6，比較本文的算法和文獻[9]中提出的算法的性能。只考慮TTD和BR兩個性能指標。令TTD和TTD*分別表示本文算法和文獻[9]中提出的算法的RN移動總距離；BR和BR*分別表示本文算法和文獻[9]中提出的算法的網絡2連通率。比較比值TTD/TTD*和BR/BR*在不同網絡動態中的值。從圖7可以看出，隨著AN運動速度的提高，本文的算法可以取得較好的性能。這是由于文獻[9]中提出的算法是針對當前時刻的網絡狀態來確定中繼節點的最新位置。然而，在高動態的網絡中，RN移動到目標位置時，網絡的狀態早已改變，所以該算法在高動態的航空網絡環境中并不能獲得較好的性能。

圖7 性能比較Fig.7 Performance comparison

5 結論

1)針對AANET的特點提出一種基于中繼節點的網絡容錯控制方法。該控制方法采用在線控制RN運動速度的方式，利用較小的運動總路程實現網絡的容錯性。

2)將RN的運動速度控制問題抽象為求解最小成本可行移動矩陣的問題，并給出了適用于在線控制的快速計算方法。

3)仿真結果表明該拓撲控制方法在AANET的容錯控制方面具有潛在的應用前景。

References)

[1]SakhaeeE,JamalipourA.Theglobalin-flightinternet[J].IEEEJournalonSelectedAreasinCommunications, 2006, 24(9): 1748-1757.

[2] 鄭博, 張衡陽, 黃國策, 等. 航空自組網的現狀與發展[J]. 電信科學, 2011, 27(5): 38-47.

ZHENGBo,ZHANGHengyang,HUANGGuoce,etal.Statusanddevelopmentofaeronauticaladhocnetworks[J].TelecommunicationsScience, 2011, 27(5): 38-47. (inChinese)

[3]FallK.Adelay-tolerantnetworkarchitectureforchallengedinternets[C]//ProceedingsofACMInternationalConferenceontheApplications,Technologies,Architectures,andProtocolsforComputerCommunication,Karlsruhe,Germany:ACM, 2003: 27-34.

[4]AzizAA,SekerciogluYA,FitzpatrickP,etal.Asurveyon

distributedtopologycontroltechniquesforextendingthelifetimeofbatterypoweredwirelesssensornetworks[J].IEEECommunicationsSurveys&Tutorials, 2013, 15(1): 121-144. [5]NishiyamaH,NgoT,AnsariN,etal.Onminimizingtheimpactofmobilityontopologycontrolinmobileadhocnetworks[J].IEEETransactionsonWirelessCommunications, 2012, 11(3): 1158-1166.

[6]DasS,LiuH,NayakA,etal.Alocalizedalgorithmforbi-connectivityofconnectedmobilerobots[J].TelecommunicationSystems, 2009, 40(3-4): 129-140.

[7]NigamA,AgarwalYK.Optimalrelaynodeplacementindelayconstrainedwirelesssensornetworkdesign[J].EuropeanJournalofOperationalResearch, 2014, 233(1): 220-233.

[8]KashyapA,KhullerS,ShaymanM.Relayplacementforfaulttoleranceinwirelessnetworksinhigherdimensions[J].ComputationalGeometry, 2011, 44(4): 206-215.

[9]KashyapA,ShaymanM.Relayplacementandmovementcontrolforrealizationoffault-tolerantadhocnetworks[C]//Proceedingsof41stAnnualConferenceonInformationSciencesandSystems,Baltimore,MD:IEEE, 2007: 783-788.

[10]SenturkIF,AkkayaK,YilmazS.Relayplacementforrestoringconnectivityinpartitionedwirelesssensornetworksunderlimitedinformation[J].AdHocNetworks, 2014, 13: 487-503.

[11]RohrerJP,JabbarA,CetinkayaEK,etal.Highly-dynamiccross-layeredaeronauticalnetworkarchitecture[J].IEEETransactionsonAerospaceandElectronicSystem, 2011, 47(4): 2742-2765.

[12]LinGH,XueGL.SteinertreeproblemwithminimumnumberofSteinerpointsandboundededge-length[J].InformationProcessingLetters, 1999, 69(2): 53-57.

[13]DegenerB,FeketeSP,KempkesB,etal.Asurveyonrelayplacementwithruntimeandapproximationguarantees[J].ComputerScienceReview, 2011, 5(1): 57-68.

[14]KhullerS,RaghavachariB.Improvedapproximationalgorithmsforuniformconnectivityproblems[J].JournalofAlgorithms, 1996, 21(2): 434-450.

[15]WestDB.Introductiontographtheory[M]. 2nded.UK:PearsonEducation, 2000: 125-130.

[16]KhulleS,VishkinU.Biconnectivityapproximationsandgraphcarvings[J].JournaloftheACM, 1994, 41(2): 214-235.

[17]CampT,BolengJ,DaviesV.Asurveyofmobilitymodelsforadhocnetworksresearch[J].WirelessCommunicationsandMobileComputing, 2002, 2(5): 483-502.

[18]OMNeT++ [EB/OL].OMNeT++Community, [2014-08-17].http://www.omnetpp.org.

Relay speed control for realization of fault-tolerant aeronautical ad hoc networks

LI Jie, GONG Erling, SUN Zhiqiang, LIU Wei, XIE Hongwei

Duetothelimitedtransmissionrangeofairbornenodes,aeronauticaladhocnetworksuffersfromfrequentnetworkpartitioninginthehighly-dynamicenvironment,whichmayaffecttheoperationofnetworkapplications.Inordertoguaranteeend-to-endconnectivity,aeronauticaladhocnetworkshouldhavetheabilityoffault-toleranceagainstlinkornodefailures.Therefore,oneormorerelaynodesarerequiredforconstructingsuchafault-tolerantnetwork.Asairbornenodesmove,relaynodesneedtomoveaswellinordertore-establishthetopologyasquicklyaspossible.Anonlinealgorithmisproposedforrelaynodes’speedcontroltorealizethenetworkfault-tolerantduringrunningtime.Basedonthenetwork’sactualstate,theonlinealgorithmcalculatesrelaynodes’velocitiessuchthatthenetworkcankeepfault-toleranceandrelaynodes,cantravelashorttotaldistanceduringtherunningtime.Simulationsdemonstratethattheproposedalgorithmisofgreatpotentialtobeappliedtoaeronauticaladhocnetworks.

adhocnetworks;fault-tolerantdesign;networkconnectivity;speedcontrol

2014-10-15

李杰(1985—)，男，江蘇徐州人，博士研究生，E-mail：ljkjhk@126.com；謝紅衛(通信作者)，男，教授，博士，博士生導師，E-mail：sunzq@nudt.edu.cn

10.11887/j.cn.201504026

http://journal.nudt.edu.cn

TP

A