航空自组网中面向容错的中继节点速度控制*

2015-11-07宫二玲孙志强谢红卫

国防科技大学学报 2015年4期

李杰，宫二玲，孙志强，刘伟，谢红卫

李杰，宫二玲，孙志强，刘伟，谢红卫

(国防科技大学机电工程与自动化学院，湖南长沙 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

为了方便研究算法性能，定义以下几个性能指标。

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

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