一種基于飛行器移動(dòng)特征的網(wǎng)絡(luò)拓?fù)淇刂茩C(jī)制

鐘冬，王一寧，朱怡安，尤濤，段俊花

（西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710072）

一種基于飛行器移動(dòng)特征的網(wǎng)絡(luò)拓?fù)淇刂茩C(jī)制

鐘冬，王一寧，朱怡安，尤濤，段俊花

（西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710072）

在高速移動(dòng)節(jié)點(diǎn)組成的空中交通網(wǎng)絡(luò)中，節(jié)點(diǎn)的高速移動(dòng)會(huì)增大路由路徑中斷的概率，進(jìn)而增大重路由的頻率，使網(wǎng)絡(luò)的通信性能下降。選擇可用度較高的鏈路生成路由路徑，能夠有效降低重路由頻率，提高路由路徑的可用時(shí)間。文中提出了一個(gè)將航空自組織網(wǎng)絡(luò)的節(jié)點(diǎn)移動(dòng)特征和鏈路可用度相結(jié)合的拓?fù)淇刂茩C(jī)制，并將該機(jī)制與OLSR協(xié)議結(jié)合，生成新的路徑鏈接可用度路由協(xié)議（LAR協(xié)議）。通過(guò)仿真實(shí)驗(yàn)對(duì)比不同場(chǎng)景下LAR協(xié)議與其他路由協(xié)議的性能，包括端到端延遲、路徑可用性及路徑長(zhǎng)度，結(jié)果表明，LAR協(xié)議可明顯增加路徑的可用時(shí)間，同時(shí)端到端延時(shí)和路徑可用率2項(xiàng)指標(biāo)的性能也較為理想。

拓?fù)淇刂?；路由協(xié)議；Ad Hoc網(wǎng)絡(luò)；移動(dòng)計(jì)算；無(wú)線(xiàn)網(wǎng)絡(luò)

航空自組織網(wǎng)絡(luò)（aeronautical Ad Hoc network，AANET）是移動(dòng)自組織網(wǎng)絡(luò)（MANET）中的一種，它可以作為未來(lái)民航通信系統(tǒng)中天基網(wǎng)和地基網(wǎng)的重要補(bǔ)充用于未來(lái)民航的通信。AANET與傳統(tǒng)的移動(dòng)自組織網(wǎng)絡(luò)相比，其節(jié)點(diǎn)的移動(dòng)速度普遍較高，且移動(dòng)軌跡受限，能量約束要求不高。節(jié)點(diǎn)的高速移動(dòng)，會(huì)使網(wǎng)絡(luò)的拓?fù)淇焖僮兓?，?jié)點(diǎn)之間鏈接頻繁中斷，從而導(dǎo)致路由路徑的頻繁中斷，進(jìn)而對(duì)應(yīng)用建立的持續(xù)會(huì)話(huà)產(chǎn)生較大影響［1］。上述問(wèn)題對(duì)移動(dòng)自組織網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)帶來(lái)了新的挑戰(zhàn)，要求協(xié)議能夠?qū)崟r(shí)感知網(wǎng)絡(luò)拓?fù)涞念l繁變化，并根據(jù)拓?fù)涞念l繁變化采取有效的處理機(jī)制［2］。為此，本文提出了一種新的基于拓?fù)浣Y(jié)構(gòu)的路由機(jī)制。其目標(biāo)是在不依賴(lài)定位系統(tǒng)的情況下，根據(jù)飛機(jī)的移動(dòng)特征對(duì)網(wǎng)絡(luò)的拓?fù)溥M(jìn)行控制，從而為AANET應(yīng)用的部署提供理想的網(wǎng)絡(luò)環(huán)境。

1　AANET網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)模型

設(shè)2個(gè)飛行器節(jié)點(diǎn)m1和m2之間的間距為d；每個(gè)節(jié)點(diǎn)的通信范圍為r；2個(gè)節(jié)點(diǎn)分別以v1和v2的速度移動(dòng)。當(dāng)2個(gè)節(jié)點(diǎn)m1和m2之間的間距d≤r時(shí)，在2節(jié)點(diǎn)之間創(chuàng)建1個(gè)鏈接。此時(shí)，隨著節(jié)點(diǎn)的高速移動(dòng)會(huì)出現(xiàn)2種情況：在v1=v2的情況下，節(jié)點(diǎn)之間的鏈接狀態(tài)將會(huì)一直保持有效；在v1≠v2的情況下，節(jié)點(diǎn)之間的鏈接將會(huì)在一段時(shí)間后中斷。根據(jù)同一航線(xiàn)上飛行器的飛行特征，v1和v2在極坐標(biāo)系中可分別表示為（v1，θ1）和（v2，θ2），其中v1，v2∈［Vmin，Vmax］，θ1，θ2∈｛0，Π｝，節(jié)點(diǎn)m1和m2的相對(duì)速度可表示為

其相對(duì)速率可表示為

相對(duì)速率函數(shù)依賴(lài)于相互獨(dú)立的隨機(jī)變量v1、v2、θ1和θ2。這里用隨機(jī)變量Vr表示相對(duì)速度，相對(duì)速度的數(shù)學(xué)期望可定義為

因?yàn)楣剑?）中的隨機(jī)變量相互獨(dú)立。所以聯(lián)合分布函數(shù)f（Vr）等于其邊緣分布函數(shù)的乘積，即

從而可得出相對(duì)速度的數(shù)學(xué)期望可表示為

設(shè)節(jié)點(diǎn)m1和m2在時(shí)刻t建立了一個(gè)鏈接llink12，并且節(jié)點(diǎn)m1相對(duì)于節(jié)點(diǎn)m2以vr的速度移動(dòng)，如果相對(duì)速率｜vr｜＞0，則鏈接llink12將在一段時(shí)間后斷開(kāi)。如果節(jié)點(diǎn)在時(shí)間區(qū)間（t，t+Δt）內(nèi)移動(dòng)速度不變，且相對(duì)距離不超過(guò)2r，則鏈接llink12將一直處于可用狀態(tài)。

對(duì)在t時(shí)刻建立的鏈接，在t+Δt時(shí)刻仍保持鏈路可用的概率可由下式表示

設(shè)節(jié)點(diǎn)m1在t+Δt時(shí)刻的無(wú)線(xiàn)電覆蓋區(qū)域與在t時(shí)刻的無(wú)線(xiàn)電覆蓋區(qū)域的重疊部分用Ot+Δt（d）表示，則節(jié)點(diǎn)m1以速度v1在時(shí)間區(qū)間（t，t+Δt）內(nèi)移動(dòng)距離d（d≥0）時(shí)，其重疊區(qū)域Ot+Δt（d）的計(jì)算函數(shù)可表示為

下面以基于拓?fù)浣Y(jié)構(gòu)的路由機(jī)制中的Hello報(bào)文為實(shí)例，介紹節(jié)點(diǎn)移動(dòng)過(guò)程中鏈接可用概率的計(jì)算方法。設(shè)Hello報(bào)文每隔T秒鐘廣播1次，以發(fā)現(xiàn)或維持相應(yīng)的可用鏈接，則節(jié)點(diǎn)m1與節(jié)點(diǎn)m2移動(dòng)一個(gè)周期T時(shí)間后的距離可由E（Vr）T計(jì)算得到。因此，在經(jīng)過(guò)n個(gè)周期后，鏈接保持可用的概率可由公式（7）表示（其中N表示自然數(shù)集合）。

如果2個(gè)節(jié)點(diǎn)的相對(duì)移動(dòng)方向只有正向和反向2種，則同向移動(dòng)時(shí)，相對(duì)速度的數(shù)學(xué)期望的計(jì)算公式可由公式（4）簡(jiǎn)化為

當(dāng)節(jié)點(diǎn)m1和m2反方向移動(dòng)時(shí)，相對(duì)速度的數(shù)學(xué)期望的計(jì)算公式同樣可由公式（4）簡(jiǎn)化為

定理1（同向鏈接定理） 在相同航線(xiàn)航行的節(jié)點(diǎn)兩兩建立的鏈接中，同向航行節(jié)點(diǎn)比反向航行節(jié)點(diǎn)建立的鏈接保持長(zhǎng)時(shí)間可用的概率高。

證明 已知周期T為定值，2個(gè)移動(dòng)節(jié)點(diǎn)的相對(duì)距離d=E（Vr）nT與E（Vr）成正比。由公式（8）和（9）知E（Vr）opposite direction＞E（Vr）same direction。而函數(shù)Ot+Δt（d）在區(qū)間0≤d≤2r內(nèi)是一個(gè)減函數(shù)。由已知條件和公式（7）可推出

因此，當(dāng)節(jié)點(diǎn)同向移動(dòng)時(shí)，節(jié)點(diǎn)m1和m2之間的鏈接保持長(zhǎng)時(shí)間可用的概率（pconnected）高。

AANET的路由協(xié)議在創(chuàng)建多跳路由路徑時(shí)，如果能利用定理1的結(jié)論，可有效降低鏈路中斷的概率，從而降低路由路徑中斷的概率。

定理2（反向鏈接定理） 在相同航線(xiàn)航行的節(jié)點(diǎn)中，對(duì)兩兩反向航行的節(jié)點(diǎn)之間所創(chuàng)建的所有鏈接，新創(chuàng)建的鏈接保持長(zhǎng)時(shí)間可用的概率高。

證明 設(shè)時(shí)間周期為T(mén)，且兩兩反向航行的飛行器在不同時(shí)刻創(chuàng)建的2個(gè)鏈接分別為llink1和llink2，再設(shè)在時(shí)刻t時(shí)，鏈接llink1持續(xù)了n個(gè)周期（其中n ∈N），鏈接llink2持續(xù)了（n-β）個(gè)周期（其中0＜β ＜n，β∈N）。則根據(jù)公式（7），在時(shí)刻t鏈接llink1和llink2保持可用的概率分別由下式表示

以及

由于函數(shù)Ot+Δt（d）的值在區(qū)間0≤d≤2r內(nèi)遞減，由此可推出pconnected（n）＜pconnected（n-β）。因此，建立時(shí)間較長(zhǎng)的鏈路llink1保持可用的概率較小。

2　基于移動(dòng)模型的拓?fù)淇刂?/h2>

本節(jié)詳述AANET網(wǎng)絡(luò)拓?fù)淇刂茩C(jī)制中，如何根據(jù)節(jié)點(diǎn)移動(dòng)特征檢測(cè)識(shí)別同一航線(xiàn)的2個(gè)飛行器之間建立的可用鏈接。在基于拓?fù)浣Y(jié)構(gòu)的路由機(jī)制中，節(jié)點(diǎn)之間鏈接的發(fā)現(xiàn)與維護(hù)，主要通過(guò)定期交換Hello報(bào)文來(lái)實(shí)現(xiàn)。鏈路可依據(jù)時(shí)間的度量指標(biāo)，通過(guò)收到Hello報(bào)文的數(shù)量來(lái)表示。引入節(jié)點(diǎn)邏輯鄰居集合的概念，該集合是指可直接給其發(fā)送Hello報(bào)文的1跳節(jié)點(diǎn)的集合。

表1是節(jié)點(diǎn)mi的一個(gè)邏輯鄰居集合列表（這里i=1），其中Mi表示mi的邏輯鄰居集合，ti（mx）表示節(jié)點(diǎn)mi從它的鄰居節(jié)點(diǎn)mx首次接收到一個(gè)Hello報(bào)文的時(shí)間，并在它們之間建立1條單向鏈路的時(shí)刻。φi（mx）表示節(jié)點(diǎn)mi和mx之間的穩(wěn)定度，用來(lái)度量mi和mx之間建立鏈接的持續(xù)時(shí)間。公式（10）是φi（mx）的具體計(jì)算方法，其中t表示當(dāng)前時(shí)間，T表示接收Hello報(bào)文的周期，［］表示取整數(shù)位。

表1　節(jié)點(diǎn)mi的邏輯鄰居列表（t=132.6 s，T=1 s，i=1）

Ni（mx）表示超時(shí)參數(shù)，意指當(dāng)2節(jié)點(diǎn)之間超過(guò)Ni（mx）時(shí)間沒(méi)有Hello報(bào)文交互時(shí)，認(rèn)為2節(jié)點(diǎn)之間的鏈接已經(jīng)斷開(kāi)。Ni（mx）指標(biāo)的作用，是避免Hello報(bào)文因偶爾的干擾導(dǎo)致發(fā)送或接收失敗時(shí)，誤認(rèn)為鏈接已經(jīng)斷開(kāi)而設(shè)置的。本文設(shè)置Ni（mx）= 4T，這意味著鏈路檢測(cè)機(jī)制可容忍連續(xù)3個(gè)周期沒(méi)有收到Hello報(bào)文。因?yàn)槌霈F(xiàn)3次以上連續(xù)丟失Hello報(bào)文的概率非常小，可以忽略不計(jì)［4-5］。當(dāng)一個(gè)鏈接出現(xiàn)經(jīng)歷4個(gè)周期還未收到Hello報(bào)文時(shí)，則認(rèn)定該鏈接中斷，路由過(guò)程中將不再選擇此鏈接，同時(shí)穩(wěn)定度參數(shù)將會(huì)歸零重新累加。但是，當(dāng)穩(wěn)定度參數(shù)重新達(dá)到一個(gè)定值時(shí)，該鏈接將會(huì)被重新認(rèn)定為可用鏈接。

2.1同向航行的長(zhǎng)可用鏈接的識(shí)別方法

用穩(wěn)定度參數(shù)來(lái)檢測(cè)識(shí)別同航向飛行器之間建立的長(zhǎng)可用鏈接。如公式（11）所示，當(dāng)一個(gè)鏈接的穩(wěn)定度參數(shù)φi（mx）大于一個(gè)給定值nstab時(shí)，則認(rèn)為該鏈接具有較高的穩(wěn)定度，是一個(gè)長(zhǎng)可用鏈接，用llinkix-l表示。

下面具體說(shuō)明nstab值的確定方法。由公式（6）和（7）可知，當(dāng)E（Vr）≠0且d＞2r時(shí)，pconnected（n）= 0成立；由于此時(shí)d=E（Vr）nT，因此可知當(dāng)n＞ 2r/E（Vr）T時(shí)，pconnected（n）=0。然而文獻(xiàn)［7］的研究發(fā)現(xiàn)，高速移動(dòng)自組織網(wǎng)絡(luò)中，保持鏈接可用狀態(tài)下，節(jié)點(diǎn)相對(duì)速度的概率是按正態(tài)分布的，其中99.7%的速度分布在E（Vr）±3σ（σ＜E（Vr）/3）范圍內(nèi)，其中σ表示分布的標(biāo)準(zhǔn)差。這里我們?nèi)∠鄬?duì)速度分布的下限為E（Vr）-3σ，以獲得較大的nstab值。其計(jì)算公式為

由上式知，同一航線(xiàn)上，沿相同航向飛行的2個(gè)飛行器之間建立一個(gè)鏈接后，只在收到nstab個(gè)以上的HELLO報(bào)文時(shí)，才能說(shuō)明該鏈接是一個(gè)長(zhǎng)可用鏈接。

2.2雙向航行的短可用鏈接的識(shí)別方法

AANET網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)特性使節(jié)點(diǎn)之間的鏈接不能總是長(zhǎng)可用鏈接，經(jīng)常會(huì)出現(xiàn)路由路徑中的鏈接，無(wú)法保持長(zhǎng)可用鏈接的情況。此時(shí)，路由過(guò)程就需要使用短可用鏈接來(lái)填補(bǔ)路由路徑，以保障數(shù)據(jù)的可靠傳輸。這里，短可用鏈接是指φi（mx）＜nstab且可用時(shí)間較長(zhǎng)的鏈接。短可用鏈接的識(shí)別算法需用到定理2的理論，可從1組不穩(wěn)定鏈接（φi（mx）＜nstab）中，挑選出可用時(shí)間較長(zhǎng)的鏈接。即按照下式選擇邏輯鄰居集合中，穩(wěn)定度參數(shù)值最小的鏈接為短可用鏈接

對(duì)于不穩(wěn)定鏈接來(lái)講，本方法不區(qū)別鏈接是由同向航行節(jié)點(diǎn)建立的還是由反向航行節(jié)點(diǎn)建立的，只選擇φi（mx）值最低的鏈接為短可用鏈接。

2.3基于鏈接穩(wěn)定度的拓?fù)淇刂茩C(jī)制

當(dāng)邏輯鄰居節(jié)點(diǎn)都與一個(gè)節(jié)點(diǎn)具有長(zhǎng)可用鏈接時(shí)，此節(jié)點(diǎn)可認(rèn)為是一個(gè)穩(wěn)定節(jié)點(diǎn)，并可作為廣播網(wǎng)絡(luò)拓?fù)浒l(fā)生變化的信息。為避免大量拓?fù)渥兓畔⒌膹V播造成泛洪現(xiàn)象，本文提出了一種廣播代理選舉算法。該算法可選擇一個(gè)節(jié)點(diǎn)統(tǒng)一發(fā)送拓?fù)渥兓男畔?。此外，該算法生成的由長(zhǎng)可用鏈接組成的拓?fù)浣Y(jié)構(gòu)，可有效用于全網(wǎng)范圍內(nèi)的信息發(fā)布與傳遞。

設(shè)A（mi）為節(jié)點(diǎn)mi所選擇的廣播代理，且每個(gè)節(jié)點(diǎn)mi只能選擇一個(gè)廣播代理，mi也可通過(guò)Hello報(bào)文獲知其邏輯鄰居集合中的節(jié)點(diǎn)所選擇的廣播代理。mi選擇廣播代理的方法如算法1所示。

算法1 節(jié)點(diǎn)mi選舉其廣播代理的算法

輸入：Mi，｛φi（mx）， Ai（mx），ti（mx）｝?mx∈Mi

輸出：A（mi）

1）φmax←return-φmax-from-table（）；

2）address←MAX-INT；

3）Amid←-1；

4）thershold←-1；

5）IF if-stable-node（mi）THEN/?規(guī)則1-判斷節(jié)點(diǎn)是否是穩(wěn)定節(jié)點(diǎn)?/

6）FOR each neighbor mx∈MiDO

7）insert-list（Ai（mx），list-BA）；/?將鄰居節(jié)點(diǎn)的廣播代理插入列表中?/

8）END

9）IF（miis BA）THEN

10）insert-list（mi，list-BA）；

11）END

12）FOR each Ax∈list-BA DO/?選出已有廣播代理中穩(wěn)定度最高的廣播代理?/

13）FOR each neighbor mx∈MiDO

14）IF（mx=Ax）AND if-stable-node（mx）THEN/?規(guī)則2-選擇鄰居中的已是廣播代理的節(jié)點(diǎn)為mi的廣播代理?/

15）Amid←mx；

16）END

17）END

18）IF（Amid≠-1）THEN；/?代理節(jié)點(diǎn)已選出?/

19）BREAK；

20）END

21）IF（mi=Ax）THEN/?規(guī)則3-選舉自己為廣播代理?/

22）Amid←mi；

23）BREAK；

24）END

25）END

26）IF（Amid=-1）THEN/?規(guī)則4-選舉鄰居節(jié)點(diǎn)為一個(gè)新的廣播代理?/

27）FOR each neighbor mx∈MiDO

28）IF（φmax-φi（mx）-thershold≤0）

AND（address-mx＜address）THEN

29）address←address-mx；

30）Amid←mx；

31）END

32）END

33）END

34）END

35）A（mi）=Amid；

上述算法中，規(guī)則1～4的原理說(shuō)明如下：

規(guī)則1 當(dāng)mi與其邏輯鄰居節(jié)點(diǎn)之間沒(méi)有長(zhǎng)可用鏈接時(shí)，它不選擇任何節(jié)點(diǎn)做自己的廣播代理；

規(guī)則2 當(dāng)mi未被其邏輯鄰居節(jié)點(diǎn)選為廣播代理，并且至少存在一個(gè)鄰居節(jié)點(diǎn)mx已經(jīng)是一個(gè)廣播代理時(shí)，mi選擇節(jié)點(diǎn)mx為自己的廣播代理；

規(guī)則3 當(dāng)mi是其邏輯鄰居節(jié)點(diǎn)選擇出來(lái)的廣播代理之一，同時(shí)其地址又小于其他邏輯鄰居節(jié)點(diǎn)選擇出來(lái)的廣播代理的地址時(shí)，mi將選擇自己作為廣播代理；

規(guī)則4 當(dāng)mi的邏輯鄰居中（mx∈Mi），沒(méi)有一個(gè)節(jié)點(diǎn)已選定廣播代理時(shí)，mi選擇邏輯鄰居集合中穩(wěn)定度參數(shù)值最大的邏輯鄰居中地址最小的節(jié)點(diǎn)作為廣播代理；

上述算法中，規(guī)則4用于網(wǎng)絡(luò)中選擇第一個(gè)廣播代理，規(guī)則2用于合并多個(gè)廣播組。規(guī)則3用于自己充當(dāng)廣播代理時(shí)合并多個(gè)廣播組。

傳統(tǒng)的聚類(lèi)算法在選舉簇頭的過(guò)程中通常需要使用2跳以外的節(jié)點(diǎn)信息，而本算法中廣播代理的選舉只使用1跳以外的鄰居節(jié)點(diǎn)信息。因此，廣播組是會(huì)發(fā)生重疊的。圖1是一個(gè)本算法的具體實(shí)例，圖1a）所示的網(wǎng)絡(luò)中，節(jié)點(diǎn)m1是由節(jié)點(diǎn)m2、m3和m4選舉出來(lái)的廣播代理。應(yīng)用規(guī)則3，節(jié)點(diǎn)m1選舉自己為廣播代理。在節(jié)點(diǎn)m5和m6與網(wǎng)絡(luò)有了物理鏈接后，如果m5選舉m2為廣播代理，m6選舉m3為廣播代理（如圖1b）所示），則在此情況下，廣播代理m1、m2和m3都是穩(wěn)定節(jié)點(diǎn)，因此，m1、m2和m3生成的拓?fù)涫且粋€(gè)穩(wěn)定拓?fù)?。此時(shí)，節(jié)點(diǎn)集合｛m1，m2，m3｝可將數(shù)據(jù)包發(fā)送到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，且所生成的穩(wěn)定拓?fù)湟部捎糜谛畔⒌娜W(wǎng)廣播。

但是，穩(wěn)定拓?fù)洳⒎窃谒星闆r下，都能用于信息的全網(wǎng)廣播。例如，對(duì)于圖1c）中的網(wǎng)絡(luò)，如果通過(guò)穩(wěn)定拓?fù)涞墓?jié)點(diǎn)集合｛m1，m2，m3｝進(jìn)行信息的全網(wǎng)廣播時(shí)，并不能保證所有網(wǎng)絡(luò)節(jié)點(diǎn)都一定能收到消息。事實(shí)上，由m1和m8驅(qū)動(dòng)的廣播路徑，由于普通節(jié)點(diǎn)m5和m9之間不是長(zhǎng)可用鏈接，因此m1通過(guò)穩(wěn)定拓?fù)洌鹠1，m2，m3｝在全網(wǎng)的廣播消息發(fā)送到m5時(shí)，是無(wú)法繼續(xù)發(fā)送到m9和m8的。同樣，m8在全網(wǎng)的廣播消息只有m9能收到，其他節(jié)點(diǎn)是收不到的。此類(lèi)狀況通常發(fā)生在飛行節(jié)點(diǎn)密度較低的時(shí)候。由于本算法僅關(guān)注穩(wěn)定拓?fù)淇捎脮r(shí)間的問(wèn)題。因此，全網(wǎng)廣播的實(shí)時(shí)可達(dá)性可暫不考慮。

圖1　算法1的實(shí)例

3　仿真實(shí)驗(yàn)

為驗(yàn)證本文提出的拓?fù)淇刂茩C(jī)制的效果，我們利用上述拓?fù)淇刂茩C(jī)制對(duì)OLSR協(xié)議進(jìn)行了改進(jìn)，設(shè)計(jì)了一個(gè)融入AANET網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)特征的路由協(xié)議——鏈接可用度路由協(xié)議（link availability routing protocol，LAR）。并分別與OLSR、DSR、AODV、GPSR協(xié)議的性能進(jìn)行了比較。對(duì)比的性能參數(shù)主要包括：路徑可用率、路徑長(zhǎng)度、路徑可用時(shí)間及端到端延遲4個(gè)參數(shù)。實(shí)驗(yàn)中定義了4個(gè)不同節(jié)點(diǎn)密度的場(chǎng)景，節(jié)點(diǎn)的平均鄰居數(shù)分別設(shè)定為4、6、8和10，以保證以10公里為半徑的圓周內(nèi)飛行器數(shù)量個(gè)數(shù)分別保持在5、7、9和11。

仿真實(shí)驗(yàn)結(jié)果中端到端延遲的情況如表2所示。從表2的總體比對(duì)結(jié)果來(lái)看，本文提出的LAR協(xié)議比DSR和GPSR協(xié)議的端到端延遲要明顯低很多，介于OLSR和AODV協(xié)議之間。就端到端延遲而言LAR比OLSR協(xié)議的性能略差一點(diǎn)，這主要是因?yàn)長(zhǎng)AR協(xié)議中MPRs集合的節(jié)點(diǎn)數(shù)比OLSR協(xié)議優(yōu)化過(guò)的MPRs集合中的節(jié)點(diǎn)數(shù)要多，這會(huì)致使LAR協(xié)議在網(wǎng)絡(luò)拓?fù)涓聲r(shí)產(chǎn)生更多的廣播控制報(bào)文。

表2　端到端時(shí)延的比對(duì)/ms

表3描述了不同模擬場(chǎng)景下不同協(xié)議的平均路徑長(zhǎng)度。OLSR協(xié)議在所有場(chǎng)景下都具有最小的平均路徑長(zhǎng)度。LAR協(xié)議的平均路徑長(zhǎng)度只稍大于OLSR協(xié)議，低于其他3個(gè)協(xié)議。而DSR協(xié)議則在幾乎所有場(chǎng)景下都具有最長(zhǎng)的平均路徑長(zhǎng)度。將表2和表3結(jié)合起來(lái)比較，我們可以發(fā)現(xiàn)平均路徑長(zhǎng)度的增加會(huì)導(dǎo)致端到端延遲的增加。然而，不是所有仿真場(chǎng)景下都有上述特性。這是因?yàn)槊糠N路由協(xié)議都有其自身特點(diǎn)，不能一概而論的認(rèn)為端到端延遲和平均路徑長(zhǎng)度之間一定成正比。當(dāng)給定協(xié)議具有較小的平均路徑長(zhǎng)度時(shí)，如果路徑飽和程度較高，則會(huì)表現(xiàn)出較高的端到端延遲。

表3　平均路徑長(zhǎng)度的比對(duì)（跳數(shù)）

表4使用到給定目的節(jié)點(diǎn)的路徑解析比率來(lái)描述路徑的平均可用率。其中DSR和GPRS協(xié)議表現(xiàn)出較高的路徑可用率，這主要是因?yàn)樯鲜鰞蓞f(xié)議都具有按需路由的特性。本文提出的LAR協(xié)議的路徑可用率與AODV協(xié)議非常接近，遠(yuǎn)高于OLSR協(xié)議。對(duì)于最終用戶(hù)來(lái)說(shuō)，路徑的可用率是一項(xiàng)很重要的指標(biāo)，但對(duì)于網(wǎng)絡(luò)的穩(wěn)定性來(lái)講路徑的可用時(shí)間也是非常重要的［3］。雖然仿真實(shí)驗(yàn)中DSR和GPSR協(xié)議的路徑可用率最高，但它們表現(xiàn)出的端到端時(shí)延也是最長(zhǎng)的。另外，DSR和GPSR協(xié)議還有一個(gè)問(wèn)題，盡管它們可為一個(gè)給定目的節(jié)點(diǎn)解析出大量的路徑，但從路徑可用時(shí)間的角度來(lái)考慮，這些路徑的質(zhì)量并不高。

表4　路徑可用率的比對(duì)/%

本文選擇一個(gè)中低密度（場(chǎng)景2）和一個(gè)中高密度的空中交通場(chǎng)景（場(chǎng)景3）的仿真實(shí)驗(yàn)結(jié)果來(lái)分析路徑的可用時(shí)間。而場(chǎng)景1和場(chǎng)景2的實(shí)驗(yàn)結(jié)果較為相似，場(chǎng)景3和場(chǎng)景4的實(shí)驗(yàn)結(jié)果較為相似，因此場(chǎng)景1和4的實(shí)驗(yàn)結(jié)果不再分析。分析過(guò)程中采用路徑可用時(shí)間的累積分布函數(shù)（CDF，cumulative distribution function）來(lái)進(jìn)一步分析不同協(xié)議的實(shí)驗(yàn)結(jié)果，如圖2所示。其中圖2a）是場(chǎng)景2中的路徑可用時(shí)間的比對(duì)結(jié)果，圖2b）是場(chǎng)景3中的路徑可用時(shí)間的比對(duì)結(jié)果。結(jié)合表4的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)GPSR和DSR協(xié)議雖然具有較高的路徑可用率，但圖2中路徑可用時(shí)間的累計(jì)分布函數(shù)值顯示它們生成的路徑中約有45%的路徑可用時(shí)間不大于1 s。而LAR協(xié)議只有9%的路徑的可用時(shí)間不大于1秒，明顯低于GPSR和DSR協(xié)議。也就是說(shuō)LAR協(xié)議創(chuàng)建的路徑具有較長(zhǎng)可用時(shí)間的概率較高。如圖2a）顯示LAR協(xié)議所創(chuàng)建的路徑中，可用時(shí)間不超過(guò)6 s的數(shù)量約為28%，而其他協(xié)議的數(shù)量都介于55%和78%之間。

所有仿真實(shí)驗(yàn)結(jié)果表明，本文提出的理論方法應(yīng)用到LAR協(xié)議后，可明顯增加路徑的可用時(shí)間。而在實(shí)驗(yàn)過(guò)程中，我們發(fā)現(xiàn)只選擇同向飛行的節(jié)點(diǎn)建立路由路徑時(shí)，OLSR協(xié)議建立的路由路徑可用率可達(dá)到72.18%，當(dāng)選擇雙向飛行的節(jié)點(diǎn)建立路由路徑時(shí)，路徑可用度僅為45.27%。而從表4的實(shí)驗(yàn)結(jié)果看，LAR協(xié)議在雙向飛行的節(jié)點(diǎn)中建立路由路徑的可用率可達(dá)到66.93%，接近OLSR協(xié)議在同向飛行節(jié)點(diǎn)中建立路由路徑的可用率。此外，LAR協(xié)議在端到端延遲方面也表現(xiàn)出較好的性能，只有OLSR協(xié)議優(yōu)于它。但其路徑可用率的實(shí)驗(yàn)數(shù)據(jù)卻優(yōu)于OLSR協(xié)議，可以與AODV協(xié)議相媲美。因此，LAR協(xié)議對(duì)路由路徑可用時(shí)間的改善表明，其更適合用于對(duì)網(wǎng)絡(luò)穩(wěn)定性要求較高的AANET網(wǎng)絡(luò)。

圖2　路徑可用時(shí)間的性能比對(duì)

4　結(jié) 論

本文提出了一種新的適用于AANET網(wǎng)絡(luò)的拓?fù)淇刂茩C(jī)制。該機(jī)制通過(guò)提高網(wǎng)絡(luò)拓?fù)渲墟溄拥目捎脮r(shí)間來(lái)降低路由路徑的中斷概率，能有效提高路由協(xié)議的性能。實(shí)驗(yàn)結(jié)果表明，本文提出的理論方法可有效改善基于拓?fù)浣Y(jié)構(gòu)和基于位置路由協(xié)議的性能，主要體現(xiàn)在路徑可用時(shí)間的提高。對(duì)于端到端延遲及路徑可用率等其它性能指標(biāo)，也可達(dá)到較為理想的水平。未來(lái)可進(jìn)一步研究移動(dòng)模型實(shí)時(shí)參數(shù)的概率模型，為進(jìn)一步探索在不同移動(dòng)條件下，實(shí)現(xiàn)自適應(yīng)路由行為的研究提供所需的理論基礎(chǔ)。

［1］ Hoffmann F，Medina D，Wolisz A.Joint Routing and Scheduling in Mobile Aeronautical Ad Hoc Networks［J］.IEEE Trans on Vehicular Technology，2013，62（6）：2700-2712

［2］ Li Y，Shirani R，St-Hilaire M，et al.Improving Routing in Networks of Unmanned Aerial Vehicles：Reactive-Greedy-Reactive ［J］.Wireless Communications&Mobile Computing，2012，12（18）：1608-1619

［3］ Nahm K，Helmy A，Kuo C C.Cross-layer Interaction of TCP and ad Hoc Routing Protocols in Multihop IEEE 802.11 Networks ［J］.IEEE Trans on Mobile Computing，2008，7（4）：458-469

［4］ Oliveira R，Bernardo L，Pinto P.The Influence of Broadcast Traffic on IEEE 802.11 DCF Networks［J］.Elsevier Computer Communications，2009，32（2）：439-452

［5］ Oliveira R，Luis M，Bernardo L，Dinis R.Towards Reliable Broadcast in ad Hoc Networks［J］.IEEE Communications Letters，2012，16（3）：314-317

A Network Topology Control Mechanism Based on Air Vehicle Movement Characteristics

Zhong Dong，Wang Yining，Zhu Yian，You Tao，Duan Junhua
（Department of Computer Science and Engineering，Northwestern Polytechnical University，Xi′an 710072，China）

In an air traffic network consisting of fast-moving nodes，their fast movement increase the possibility of a routing path break，thereby increasing the re-routing frequency and reducing the communication performance of the air traffic network.Selecting a link with high availability to generate a routing path can not only reduce the re-routing frequency effectively but also increase the lifetime of the routing path.This paper proposes a network topology control mechanism that combines node movement characteristics of aeronautical ad hoc networks with its link availability.In addition，the control mechanism is combined with the OLSR protocol to generate a new link availability routing（LAR）protocol.Through simulation，the LAR performance is compared with other routing protocols in different scenarios，including the comparison of end to end delay，path availability and path length.The simulation results show that the LAR protocol can significantly increase the lifetime of routing path compared with the topologybased routing protocol and location-based routing protocol and that the performance of end to end delay and path availability is desirable.

topology；routing protocols；ad hoc network；availability；mobile computing；wireless network；time delay；topology control

TP393

A

1000-2758（2015）06-1007-07

2015-04-24

國(guó)家自然科學(xué)基金（61303225）、陜西省自然科學(xué)基金（2013JQ8046）與西北工業(yè)大學(xué)基礎(chǔ)研究基金（GBKY1004）資助。

鐘冬（1979—），西北工業(yè)大學(xué)講師，主要從事移動(dòng)計(jì)算及物聯(lián)網(wǎng)研究。