航空自組網(wǎng)中面向容錯(cuò)的中繼節(jié)點(diǎn)速度控制*

李 杰，宮二玲，孫志強(qiáng)，劉 偉，謝紅衛(wèi)

航空自組網(wǎng)中面向容錯(cuò)的中繼節(jié)點(diǎn)速度控制*

李 杰，宮二玲，孫志強(qiáng)，劉 偉，謝紅衛(wèi)

(國(guó)防科技大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院， 湖南 長(zhǎng)沙 410073)

由于飛機(jī)節(jié)點(diǎn)的通信距離有限，航空自組網(wǎng)的網(wǎng)絡(luò)拓?fù)涓邉?dòng)態(tài)的變化會(huì)導(dǎo)致頻繁的網(wǎng)絡(luò)分割并嚴(yán)重影響網(wǎng)絡(luò)上層應(yīng)用的正常運(yùn)行。為了保證飛機(jī)節(jié)點(diǎn)之間端到端的連通性不受影響，航空自組網(wǎng)必須具備容錯(cuò)性，即任意一個(gè)節(jié)點(diǎn)或鏈路失效后網(wǎng)絡(luò)仍然連通。通常情況下飛機(jī)節(jié)點(diǎn)的運(yùn)動(dòng)不可控，因此可在網(wǎng)絡(luò)中加入一定數(shù)量的中繼節(jié)點(diǎn)，通過(guò)控制中繼節(jié)點(diǎn)的運(yùn)動(dòng)速度來(lái)實(shí)現(xiàn)并維持航空自組網(wǎng)的容錯(cuò)性。提出了一種在線中繼節(jié)點(diǎn)速度控制方法，該方法根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)計(jì)算出中繼節(jié)點(diǎn)的最佳運(yùn)動(dòng)方式，在保證網(wǎng)絡(luò)容錯(cuò)的前提下使得中繼節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)所運(yùn)動(dòng)的總路程最短。仿真結(jié)果表明該中繼節(jié)點(diǎn)速度控制方法在航空自組網(wǎng)的容錯(cuò)控制方面具有潛在的應(yīng)用前景。

自組織網(wǎng)絡(luò)；容錯(cuò)設(shè)計(jì)；網(wǎng)絡(luò)連通性；速度控制

(CollegeofMechatronicEngineeringandAutomation,NationalUniversityofDefenseTechnology,Changsha410073,China)

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

在AANET中，飛機(jī)節(jié)點(diǎn)的高速運(yùn)動(dòng)使得網(wǎng)絡(luò)拓?fù)涓邉?dòng)態(tài)地變化。由于飛機(jī)的通信距離有限，在節(jié)點(diǎn)較為稀疏的區(qū)域，AANET則無(wú)法保證飛機(jī)之間持續(xù)的端到端可靠連接。延遲容忍網(wǎng)絡(luò)(Delay-TolerantNetwork，DTN)[3]技術(shù)可以解決網(wǎng)絡(luò)頻繁分割狀態(tài)下的數(shù)據(jù)通信問(wèn)題。DTN利用網(wǎng)絡(luò)節(jié)點(diǎn)的存儲(chǔ)空間對(duì)數(shù)據(jù)進(jìn)行暫時(shí)緩存，并基于“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的路由模式實(shí)現(xiàn)節(jié)點(diǎn)間的通信。然而DTN的這種路由模式會(huì)帶來(lái)較大的端到端延遲。AANET中的多數(shù)應(yīng)用對(duì)實(shí)時(shí)性要求很高，所以DTN技術(shù)并不能解決AANET的實(shí)時(shí)通信問(wèn)題。此外，當(dāng)AANET應(yīng)用于戰(zhàn)場(chǎng)環(huán)境等一些惡劣的網(wǎng)絡(luò)環(huán)境時(shí)，網(wǎng)絡(luò)還要求具有一定的容錯(cuò)性，即部分節(jié)點(diǎn)或通信鏈路失效不會(huì)對(duì)網(wǎng)絡(luò)的連通性產(chǎn)生影響。

實(shí)現(xiàn)容錯(cuò)網(wǎng)絡(luò)的拓?fù)淇刂品椒煞譃槿?。第一類是通過(guò)控制天線的發(fā)射功率來(lái)改變節(jié)點(diǎn)的最大通信距離，進(jìn)而改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。其控制目標(biāo)是使得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)達(dá)到容錯(cuò)性要求的同時(shí)，網(wǎng)絡(luò)消耗的能量最少。該類方法在無(wú)線傳感器網(wǎng)絡(luò)(WirelessSensorNetwork，WSN)中應(yīng)用較多[4-5]。而在AANET中，節(jié)點(diǎn)的分布區(qū)域較廣，即使使用最大的發(fā)射功率，網(wǎng)絡(luò)拓?fù)湟矡o(wú)法達(dá)到容錯(cuò)性要求。如果網(wǎng)絡(luò)中節(jié)點(diǎn)的運(yùn)動(dòng)方式可控，則可用第二類方法對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行控制，即：通過(guò)控制網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)，使得網(wǎng)絡(luò)拓?fù)鋵?shí)現(xiàn)容錯(cuò)性要求[6]。第三類方法是向網(wǎng)絡(luò)中加入額外的中繼節(jié)點(diǎn)來(lái)重構(gòu)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)滿足容錯(cuò)性要求[7-10]。因此，可以在AANET中網(wǎng)絡(luò)連通性差的區(qū)域加入額外的中繼節(jié)點(diǎn)(長(zhǎng)航時(shí)的無(wú)人機(jī)或其他可控空中平臺(tái))來(lái)增強(qiáng)網(wǎng)絡(luò)的連通性[11]。由于網(wǎng)絡(luò)拓?fù)涞牟粩嘧兓?，必須通過(guò)控制這些中繼節(jié)點(diǎn)的運(yùn)動(dòng)速度來(lái)保持網(wǎng)絡(luò)的容錯(cuò)性要求。考慮到每個(gè)中繼節(jié)點(diǎn)的能量有限，為了延長(zhǎng)其工作時(shí)間，在保證網(wǎng)絡(luò)容錯(cuò)性要求的前提下還須使得中繼節(jié)點(diǎn)總的運(yùn)動(dòng)路程最短。然而，現(xiàn)有的通過(guò)中繼節(jié)點(diǎn)進(jìn)行拓?fù)淇刂频姆椒ù蠖际轻槍?duì)靜態(tài)網(wǎng)絡(luò)來(lái)合理配置中繼節(jié)點(diǎn)的位置[7-8]，或是在網(wǎng)絡(luò)拓?fù)渚徛兓木W(wǎng)絡(luò)中控制中繼節(jié)點(diǎn)的運(yùn)動(dòng)[9-10]。這些方法都無(wú)法應(yīng)用于網(wǎng)絡(luò)拓?fù)鋭×易兓腁ANET中。

1 問(wèn)題描述

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

(1)

(2)

(3)

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

圖1 在線拓?fù)淇刂艶ig.1 Online topology control

2 在線拓?fù)淇刂?/h2>

要實(shí)現(xiàn)在線拓?fù)淇刂?，就需要根?jù)網(wǎng)絡(luò)的實(shí)時(shí)狀態(tài)得出RN速度矩陣的最優(yōu)解。用采樣間隔時(shí)間Δt將時(shí)間t離散化為時(shí)間序列n=0，1，…，K，其中，K = ?T/Δt」。從而式(1)～(3)可離散化為

(4)

(5)

(6)

算法1 RN運(yùn)動(dòng)的在線控制

3 MCFM問(wèn)題的求解算法

3.1 算法提出

若si表示某個(gè)SP，為了體現(xiàn)RN移動(dòng)si的位置所要運(yùn)動(dòng)的平均距離，定義其成本c(si)為所有RN到si的平均距離，即：

(7)

構(gòu)造完全圖GC(VA，EC)，其中邊集EC表示任意兩個(gè)VA中的點(diǎn)所形成邊的集合。對(duì)于EC中的邊(ai，aj)定義其權(quán)值c(ai，aj)為：

(8)

圖2 完備加權(quán)二部圖Fig.2 Weighted complete bipartite graph

(9)

算法2 MCFM問(wèn)題的快速算法

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

3.2 算法的復(fù)雜度分析

4 仿真驗(yàn)證

圖4 仿真模型Fig.4 Simulation model

假設(shè)w個(gè)AN以速度v在邊長(zhǎng)為400km的矩形區(qū)域運(yùn)動(dòng)。用隨機(jī)路點(diǎn)(RandomWayPoint，RWP)[17]運(yùn)動(dòng)模型作為AN的運(yùn)動(dòng)模型，并將停止時(shí)間設(shè)為0，來(lái)逼真地模擬實(shí)際飛機(jī)的運(yùn)動(dòng)模式。為了提高網(wǎng)絡(luò)的連通性，在網(wǎng)絡(luò)中加入m個(gè)最大速度vmax=800m/s的RN，并設(shè)置速度更新間隔Δt=8s。網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最大通信距離r=100km?？偟姆抡鏁r(shí)間設(shè)置為30min。如圖4所示，基于網(wǎng)絡(luò)仿真平臺(tái)OMNeT++[18]建立仿真模型。在圖4所示的網(wǎng)絡(luò)模型中，“relay”模塊代表RN，“host”模塊代表AN。圖5描繪了當(dāng)v=300m/s，w=12，m=5時(shí)3個(gè)不同仿真時(shí)刻的網(wǎng)絡(luò)的拓?fù)鋱D。

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

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

(c) 仿真時(shí)刻為600s(c) At simulation time of 600s圖5 網(wǎng)絡(luò)拓?fù)銯ig.5 Network topology

為了方便研究算法性能，定義以下幾個(gè)性能指標(biāo)。

1)RN總的運(yùn)動(dòng)路程(TotalTravelDistance，TTD)：TTD值反映了RN在網(wǎng)絡(luò)運(yùn)行期間所消耗的總能量。為了延長(zhǎng)RN的工作時(shí)間，要求TTD要盡量的小。

2)2連通率(BiconnectivityRate，BR)：BR定義為網(wǎng)絡(luò)為頂點(diǎn)2連通的時(shí)間與網(wǎng)絡(luò)總的運(yùn)行時(shí)間比值。BR值越大則說(shuō)明網(wǎng)絡(luò)的容錯(cuò)性越好。

3)相對(duì)2連通率(RelativeBiconnectivityRate，RBR)：RBR值反映了RN的運(yùn)動(dòng)對(duì)網(wǎng)絡(luò)2連通率的影響。若向具有w個(gè)AN的網(wǎng)絡(luò)中加入m個(gè)RN，當(dāng)前網(wǎng)絡(luò)的2連通率和原網(wǎng)絡(luò)相比所提升的部分除了通過(guò)RN的運(yùn)動(dòng)所提升的部分外還包括由于網(wǎng)絡(luò)節(jié)點(diǎn)密度增加所提升的值。RBR值可以由網(wǎng)絡(luò)當(dāng)前的BR值減去當(dāng)網(wǎng)絡(luò)中只有w+m個(gè)AN時(shí)的值得到。若令BRo表示當(dāng)網(wǎng)絡(luò)中只有w+m個(gè)AN時(shí)的2連通率，則有

RBR=BR-BRo

(10)

4.1 性能分析

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

(a) 網(wǎng)絡(luò)2連通率(a) Biconnectivity rate of the network

(b) 網(wǎng)絡(luò)相對(duì)2連通率(b) Relative biconnectivity rate of the network

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

4.2 性能比較

令w=12，m=6，比較本文的算法和文獻(xiàn)[9]中提出的算法的性能。只考慮TTD和BR兩個(gè)性能指標(biāo)。令TTD和TTD*分別表示本文算法和文獻(xiàn)[9]中提出的算法的RN移動(dòng)總距離；BR和BR*分別表示本文算法和文獻(xiàn)[9]中提出的算法的網(wǎng)絡(luò)2連通率。比較比值TTD/TTD*和BR/BR*在不同網(wǎng)絡(luò)動(dòng)態(tài)中的值。從圖7可以看出，隨著AN運(yùn)動(dòng)速度的提高，本文的算法可以取得較好的性能。這是由于文獻(xiàn)[9]中提出的算法是針對(duì)當(dāng)前時(shí)刻的網(wǎng)絡(luò)狀態(tài)來(lái)確定中繼節(jié)點(diǎn)的最新位置。然而，在高動(dòng)態(tài)的網(wǎng)絡(luò)中，RN移動(dòng)到目標(biāo)位置時(shí)，網(wǎng)絡(luò)的狀態(tài)早已改變，所以該算法在高動(dòng)態(tài)的航空網(wǎng)絡(luò)環(huán)境中并不能獲得較好的性能。

圖7 性能比較Fig.7 Performance comparison

5 結(jié)論

1)針對(duì)AANET的特點(diǎn)提出一種基于中繼節(jié)點(diǎn)的網(wǎng)絡(luò)容錯(cuò)控制方法。該控制方法采用在線控制RN運(yùn)動(dòng)速度的方式，利用較小的運(yùn)動(dòng)總路程實(shí)現(xiàn)網(wǎng)絡(luò)的容錯(cuò)性。

2)將RN的運(yùn)動(dòng)速度控制問(wèn)題抽象為求解最小成本可行移動(dòng)矩陣的問(wèn)題，并給出了適用于在線控制的快速計(jì)算方法。

3)仿真結(jié)果表明該拓?fù)淇刂品椒ㄔ贏ANET的容錯(cuò)控制方面具有潛在的應(yīng)用前景。

References)

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

[2] 鄭博, 張衡陽(yáng), 黃國(guó)策, 等. 航空自組網(wǎng)的現(xiàn)狀與發(fā)展[J]. 電信科學(xué), 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；謝紅衛(wèi)(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail：sunzq@nudt.edu.cn

10.11887/j.cn.201504026

http://journal.nudt.edu.cn

TP

A