鄭博，張衡陽，王寶良，趙瑋

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077）

航空自組網(wǎng)負(fù)載均衡地理路由策略

鄭博，張衡陽，王寶良，趙瑋

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077）

針對貪婪周邊無狀態(tài)路由（GPSR，greedy perimeter stateless routing）協(xié)議在航空自組網(wǎng)中存在難以適應(yīng)高動態(tài)網(wǎng)絡(luò)環(huán)境、易導(dǎo)致網(wǎng)絡(luò)擁塞等問題，提出一種基于TTE（time to enter the communication range of the destination）的多路徑流量分配負(fù)載均衡地理路由（LBGR，load balancing geographic routing）協(xié)議。該協(xié)議將TTE作為路由決策依據(jù)，具體包括分組轉(zhuǎn)發(fā)策略、多路徑流量分配策略和局部最優(yōu)化處理策略等3種機制。進一步采用排隊論對多路徑流量分配策略進行了建模分析，得出了平均隊長、平均等待隊長、平均等待時間等性能指標(biāo)的數(shù)學(xué)表達(dá)式。最后利用OMNeT++仿真平臺對LBGR協(xié)議的性能進行了仿真驗證，結(jié)果表明相比GPSR等協(xié)議，LBGR協(xié)議在分組傳輸成功率和端到端時延方面有較大幅度的提升，能夠有效適應(yīng)高動態(tài)航空環(huán)境。

航空自組網(wǎng)；貪婪地理路由協(xié)議；負(fù)載均衡；多路徑；多隊列；局部最優(yōu)化

1 引言

航空自組網(wǎng)是移動ad hoc網(wǎng)絡(luò)（MANET，mobile ad hoc network）在航空通信領(lǐng)域的應(yīng)用，其基本思想是，一定范圍內(nèi)的航空飛行器之間可以互相轉(zhuǎn)發(fā)控制指令信息，交換各自的飛行狀態(tài)、感知信息等數(shù)據(jù)，并自動地連接建立起一個MANET[1～4]。航空自組網(wǎng)采用動態(tài)組網(wǎng)、動態(tài)路由和無線中繼等技術(shù)，將航空飛行器互連互通，具備自組織、自修復(fù)的能力和快速、高效組網(wǎng)的優(yōu)勢，可滿足特定條件下軍、民航通信的需求，是對現(xiàn)有航空通信網(wǎng)的補充和發(fā)展，具有重要的理論研究意義和實際應(yīng)用價值。目前，該領(lǐng)域代表性的研究與應(yīng)用項目主要有AANET[5]、ATENAA[6]、NEWSKY[7]、SANDRA[8]和iNET[9]等。

路由協(xié)議是航空自組網(wǎng)的一項關(guān)鍵技術(shù)，主要解決數(shù)據(jù)分組實時、可靠傳輸?shù)膯栴}?；诼酚杀淼南闰炇胶头磻?yīng)式路由協(xié)議大多是通過路由探測分組的全網(wǎng)性或部分泛洪廣播來獲得鏈路狀態(tài)，從而建立和存儲端到端的路由表。然而在航空高動態(tài)環(huán)境下，端到端的路由會因節(jié)點的高速移動、戰(zhàn)損失效而中斷，需要不斷地進行路由表的重建和維護，控制開銷大。貪婪地理路由協(xié)議在整個數(shù)據(jù)傳輸過程中不需要泛洪探測分組，不需要建立、維護和存儲端到端的基于鏈路狀態(tài)的路由表，只要求網(wǎng)絡(luò)中每個節(jié)點準(zhǔn)確地感知和存儲周圍鄰居節(jié)點的位置信息即可[10]。數(shù)據(jù)分組的轉(zhuǎn)發(fā)按照貪婪轉(zhuǎn)發(fā)策略分布式進行，控制開銷小，網(wǎng)絡(luò)可擴展性強。因此，貪婪地理路由協(xié)議在航空自組網(wǎng)中頗受關(guān)注，成為研究熱點之一。

然而，傳統(tǒng)貪婪地理路由協(xié)議——貪婪周邊無狀態(tài)路由[11]應(yīng)用于高動態(tài)、大尺度、稀疏型航空自組網(wǎng)存在以下3個方面的問題：1) 隨著我國低空空域的開放，航空節(jié)點呈現(xiàn)出典型的三維空間分布，而GPSR協(xié)議的應(yīng)用環(huán)境為地面二維場景；2) GPSR協(xié)議完全以向目的節(jié)點的前進距離為依據(jù)來選擇下一跳節(jié)點，沒有考慮航空節(jié)點的高動態(tài)性；3) GPSR協(xié)議在選擇下一跳節(jié)點時沒有考慮節(jié)點的負(fù)載狀況，數(shù)據(jù)分組在一定時間內(nèi)沿著同一路徑傳輸，當(dāng)業(yè)務(wù)量較大時，將產(chǎn)生較大的排隊時延，甚至造成分組丟棄，嚴(yán)重影響數(shù)據(jù)傳輸?shù)膶崟r性和可靠性。

針對以上問題，本文提出一種適用于三維高動態(tài)航空自組網(wǎng)的負(fù)載均衡地理路由協(xié)議，具體包含基于TTE的分組轉(zhuǎn)發(fā)策略、多路徑流量分配策略以及局部最優(yōu)化處理策略3種機制。該協(xié)議的主要特點在于：1) 將TTE作為路由選擇的標(biāo)準(zhǔn)，以適應(yīng)網(wǎng)絡(luò)拓?fù)涞母邉討B(tài)變化；2) 根據(jù)各鄰居節(jié)點的TTE值將流量在不同鄰居節(jié)點間按反比分配，實現(xiàn)負(fù)載均衡，克服網(wǎng)絡(luò)擁塞；3) 針對網(wǎng)絡(luò)中節(jié)點密度低的情況，采取“存儲—攜帶”機制來解決局部最優(yōu)化問題。

2 相關(guān)工作

近年來，貪婪地理路由協(xié)議在各類三維空間網(wǎng)絡(luò)中的應(yīng)用引起了研究人員的廣泛關(guān)注。文獻[12～16]對貪婪地理路由協(xié)議在三維無線傳感器網(wǎng)絡(luò)（3-D WSN，3-dimensional wireless sensor network）中的應(yīng)用進行研究：文獻[12]提出了一種多跳Delaunay三角剖分（MDT，multihop delaunay triangulation）路由，利用虛擬Delaunay三角剖分來解決3-D WSN中的空洞問題；文獻[13]提出了一種基于貪婪嵌入思想的氣泡路由（bubble routing）算法，將3-D WSN分解為一系列的空心球體細(xì)胞（HSC，hollow spherical cell）；文獻[14]首次對高虧格三維曲面WSN中的可擴展路由算法進行了研究，利用圖嵌入方法將網(wǎng)絡(luò)分解為虧格0成分；文獻[15]和文獻[16]進一步針對多種高虧格三維曲面WSN提出了可擴展、分布式路由算法。

應(yīng)用于航空自組網(wǎng)中貪婪地理路由協(xié)議的研究工作可歸納為以下3個方面。

1) 針對航空環(huán)境改進貪婪轉(zhuǎn)發(fā)策略中下一跳節(jié)點的選擇標(biāo)準(zhǔn)，為了適應(yīng)高動態(tài)網(wǎng)絡(luò)拓?fù)渥兓蛟鰪婃溌贩€(wěn)定性，將節(jié)點的運動特征作為下一跳節(jié)點的選擇依據(jù)。AeroRP（aeronautical routing protocol）將交叉時間（TTI，time to intercept）作為路由選擇依據(jù)，有效解決了基于位置的貪婪轉(zhuǎn)發(fā)策略在航空環(huán)境中存在的問題[9]。但該協(xié)議局限于二維場景，且目的節(jié)點僅限于靜止的地面站點。FGPA（fountain-code based greedy position-assisted）路由選擇離開通信范圍時距離目的節(jié)點最近的節(jié)點，作為下一跳節(jié)點，以此增強鏈路穩(wěn)定性[17]。MPGR（mobility prediction based geographic routing）在對節(jié)點進行移動預(yù)測的基礎(chǔ)上，將各鄰居節(jié)點與目的節(jié)點之間的距離，以及與轉(zhuǎn)發(fā)節(jié)點之間的連通時長，作為下一跳節(jié)點的綜合判斷依據(jù)[18]。GRAA（geographic routing protocol for aircraft ad hoc network）根據(jù)節(jié)點的三維地理位置和速度信息，將一段時間后距離目的節(jié)點最近作為下一跳節(jié)點的選擇依據(jù)[19]。RGR（reactive-greedy-reactive）協(xié)議結(jié)合了AODV和貪婪轉(zhuǎn)發(fā)策略，在通常情況下采用AODV協(xié)議構(gòu)建路由，由于網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，當(dāng)轉(zhuǎn)發(fā)節(jié)點尋找下一跳節(jié)點發(fā)現(xiàn)鏈路已斷開時，采用貪婪轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)分組[20]。文獻[21]通過在路由建立過程中增加穩(wěn)定性標(biāo)準(zhǔn)，提出了改進的RGR（modified-RGR）協(xié)議。

2) 為了克服網(wǎng)絡(luò)擁塞，采用負(fù)載均衡策略。GLSR（geographic load share routing）將分組的前進距離與排隊時延的比值定義為前進速率，并以前進速率作為下一跳節(jié)點的選擇標(biāo)準(zhǔn)，以此來實現(xiàn)負(fù)載均衡[22]。但該協(xié)議主要針對節(jié)點速率較低的航空場景，難以適應(yīng)節(jié)點速率達(dá)到3馬赫的高動態(tài)網(wǎng)絡(luò)。DGLAR（dynamic geographic load aware routing）協(xié)議在路由選擇時同時考慮節(jié)點的相對移動速度和數(shù)據(jù)擁塞情況，定義了一種新的路由度量機制，而且其動態(tài)路由因子可根據(jù)網(wǎng)絡(luò)應(yīng)用環(huán)境進行調(diào)節(jié)[23]。但動態(tài)路由因子的具體取值只能通過經(jīng)驗判斷，難以依靠具體理論獲得。

3) 結(jié)合航空環(huán)境改進空洞處理算法，如optimized-RGR協(xié)議，其空洞處理策略是當(dāng)貪婪轉(zhuǎn)發(fā)策略找不到合適的下一跳節(jié)點時，將分組轉(zhuǎn)發(fā)給向目的節(jié)點運動速度最快的節(jié)點[24]；MPGR采用了兩跳邊界轉(zhuǎn)發(fā)的空洞處理模式[18]。

隨著貪婪地理路由協(xié)議在各類網(wǎng)絡(luò)中的廣泛應(yīng)用，為克服網(wǎng)絡(luò)擁塞、減少節(jié)點能耗、提高網(wǎng)絡(luò)壽命，研究人員對多路徑負(fù)載均衡貪婪地理路由協(xié)議進行了深入的研究，代表性的工作主要有：DGR（directional geographical routing）協(xié)議將單一的業(yè)務(wù)流按照不同的傳輸方向分為多條子流，并采用輪詢調(diào)度的方式進行分組傳輸[25]；GBR（greedy-based backup routing）協(xié)議在選擇主用路徑的基礎(chǔ)上，通過計算鏈路壽命選擇本地備份 路 徑[26]；ELGR（energy-efficiency and load-balanced geographic routing）協(xié)議根據(jù)節(jié)點剩余能量與隊列長度的比較進行路由決策[27]；TPGF（two-phase geographical greedy forwarding）路由通過路徑發(fā)現(xiàn)和路徑優(yōu)化這2個階段來選取路由[28]；GEAM（geographic energy-aware non-interfering multipath）路由和RD-GMR（radio-disjoint geographic multipath routing）協(xié)議都考慮了多條路徑之間的干擾問題[29,30]。但以上協(xié)議都是針對靜態(tài)或低動態(tài)網(wǎng)絡(luò)提出的。在航空自組網(wǎng)中，由于網(wǎng)絡(luò)拓?fù)渥兓容^劇烈，貪婪地理路由協(xié)議中的鄰居節(jié)點表需要頻繁更新，這些協(xié)議難以滿足應(yīng)用需求。

3 負(fù)載均衡地理路由協(xié)議

3.1 問題描述

在GPSR等傳統(tǒng)貪婪地理路由協(xié)議中，通常采用的貪婪轉(zhuǎn)發(fā)策略MND（most nearest to destination）選擇離目的節(jié)點最近且比自身距離目的節(jié)點更近的鄰居節(jié)點作為下一跳節(jié)點。在圖1(a)所示場景中，節(jié)點i需要把分組最終發(fā)送給目的節(jié)點d，如果選擇鄰居節(jié)點n1為下一跳節(jié)點，則分組的前進距離可表示為

其中，δid表示節(jié)點i和目的節(jié)點d之間的大圓弧距離。將節(jié)點i的所有鄰居節(jié)點的集合記為?i。如果節(jié)點i和節(jié)點nk之間存在通信鏈路，則將該鏈路記為(i,nk)。對于節(jié)點nk∈?i，將其鏈路(i,nk)上的分組隊列記為Qink。根據(jù)MND策略，如果分組的前進距離滿足

則節(jié)點i選擇節(jié)點n1為下一跳節(jié)點，并將分組放入隊列Qin1中等待傳輸。MND策略的問題在于：一是僅把向目的節(jié)點的前進距離作為下一跳節(jié)點的選擇標(biāo)準(zhǔn)，沒有考慮航空高動態(tài)場景下節(jié)點運動特征等因素；二是數(shù)據(jù)分組只沿最優(yōu)路徑傳輸，沒有考慮網(wǎng)絡(luò)擁塞情況，這樣就會導(dǎo)致網(wǎng)絡(luò)負(fù)載不均衡，嚴(yán)重時會造成分組丟失，影響數(shù)據(jù)傳輸?shù)膶崟r性和可靠性。

為此，本文提出的LBGR協(xié)議一方面以航空飛行器的運動特征為依據(jù)選取下一跳節(jié)點，另一方面將流量在所有滿足條件的鄰居節(jié)點中動態(tài)合理分配，實現(xiàn)負(fù)載均衡。例如，在圖1(b)所示的場景中，節(jié)點i根據(jù)所有鄰居節(jié)點與目的節(jié)點的相對運動特征選取下一跳節(jié)點，并把流量在滿足條件的鄰居節(jié)點n1、n2和n3中按比例分配，進行多路徑傳輸。

為了便于開展研究，本文給出以下假設(shè)條件。

1) 所有節(jié)點的位置在三維網(wǎng)絡(luò)場景中隨機均勻分布，并隨機運動。

2) 所有節(jié)點的通信范圍都是以R為半徑的球體，即當(dāng)2個節(jié)點間的距離小于R時，二者間可建立雙向通信鏈路，當(dāng)其距離大于R時，鏈路斷開。

3) 所有分組具有相同的長度和傳輸速率，按Poisson流到達(dá)節(jié)點，節(jié)點對分組的服務(wù)時間服從負(fù)指數(shù)分布。

圖1 傳統(tǒng)貪婪地理路由和LBGR協(xié)議場景

3.2 協(xié)議設(shè)計思想

LBGR協(xié)議的核心思想是將TTE作為路由選擇的主要依據(jù)，即在所有鄰居節(jié)點中優(yōu)先選擇TTE值最小且比自身TTE值更小的節(jié)點作為下一跳節(jié)點來轉(zhuǎn)發(fā)分組。該協(xié)議具體包含3種機制：基于TTE的分組轉(zhuǎn)發(fā)策略、多路徑流量分配策略，以及局部最優(yōu)化處理算法，其工作流程如圖2所示。網(wǎng)絡(luò)中各節(jié)點采用周期性HELLO策略來構(gòu)建和維護鄰居節(jié)點表，存儲各鄰居節(jié)點的速度和位置信息；采用位置服務(wù)算法獲取目的節(jié)點的速度和位置信息；利用航空飛行器的GPS設(shè)備獲取自身的速度和位置信息。LBGR協(xié)議根據(jù)目的節(jié)點、各鄰居節(jié)點，以及自身的速度和位置信息，計算各鄰居節(jié)點及自身的TTE值，從而判斷是否有小于自身TTE值的鄰居節(jié)點。如果有，根據(jù)多路徑流量分配機制，將分組轉(zhuǎn)發(fā)給下一跳節(jié)點。如果所有鄰居節(jié)點的TTE值都大于節(jié)點自身的TTE值，這種情況稱為局部最優(yōu)化（local optimum）現(xiàn)象，類似于傳統(tǒng)貪婪地理路由協(xié)議中的空洞現(xiàn)象。在這種情況下，采用容延容斷網(wǎng)絡(luò)（DTN，delay/disruption tolerant network）的“存儲—攜帶”路由機制，將待發(fā)送分組存入緩存區(qū)，在動態(tài)場景中等待下一個HELLO周期再判斷是否遇到TTE值更小的鄰居節(jié)點。

圖2 LBGR協(xié)議工作流程

3.3 基于TTE的分組轉(zhuǎn)發(fā)策略

1) 鄰居節(jié)點與目的節(jié)點之間的相對速度

如圖3所示，在三維坐標(biāo)系中，節(jié)點i的下一跳節(jié)點nk在當(dāng)前時刻的位置坐標(biāo)為(xnk,ynk,znk)，目的節(jié)點d的位置坐標(biāo)為(xd,yd,zd)。節(jié)點nk的運動速度、節(jié)點d的運動速度可分別表示為

其中，vnk和vd分別表示節(jié)點nk和d的速率，θnk和θd分別表示在xoy平面上的投影與x軸正方向的夾角，?nk和?d分別表示與z軸正方向的夾角。

圖3 鄰居節(jié)點nk與目的節(jié)點d之間的相對運動

節(jié)點nk與節(jié)點d的相對速度為

其相對速率可表示為

2) 進入目的節(jié)點通信范圍的時間TTE

節(jié)點nk與節(jié)點d之間的相對位置向量可表示為

則節(jié)點nk與節(jié)點d之間的距離可表示為

如圖3所示，節(jié)點nk若要進入節(jié)點d的通信范圍，其相對速度之間的最大夾角θmax可表示為

定義TTE為

若TTE=0，表明節(jié)點nk背離節(jié)點d運動，將無法進入節(jié)點d的通信范圍，因此，節(jié)點nk不會被選為下一跳節(jié)點。若TTE＜0，表明當(dāng)前時刻節(jié)點nk正處于節(jié)點d的通信范圍，因此相對于TTE＞0的節(jié)點，節(jié)點nk將被優(yōu)先選為下一跳節(jié)點。

4 多路徑流量分配機制建模分析

LBGR協(xié)議采用的流量分配方案是所有TTE值小于轉(zhuǎn)發(fā)節(jié)點的鄰居節(jié)點都參與流量分配，將一個HELLO周期內(nèi)的總流量根據(jù)各鄰居節(jié)點的TTE值按反比分配，即TTE值較小的鄰居節(jié)點分配的業(yè)務(wù)量較大，而TTE值較大的鄰居節(jié)點分配的業(yè)務(wù)量較小。假設(shè)到達(dá)節(jié)點i的分組是參數(shù)為λ的Poisson流，令{n1,n2,…,ns}表示參與節(jié)點i流量分配的下一跳節(jié)點的集合，則分配給的所有下一跳節(jié)點的分組仍然是Poisson流，其中第k個節(jié)點的分組到達(dá)率為

設(shè)每個節(jié)點發(fā)送緩存區(qū)大小為K，當(dāng)緩存區(qū)有空位置時，新到達(dá)的分組就進入系統(tǒng)排隊等待服務(wù)，當(dāng)緩存區(qū)被全部占用時，丟棄新到達(dá)的分組。網(wǎng)絡(luò)中所有分組按照“先到先服務(wù)”（first-come,first-served）的原則接受服務(wù)，每個分組所需的服務(wù)時間獨立，服從參數(shù)μ的負(fù)指數(shù)分布，且到達(dá)與服務(wù)是彼此獨立的。實質(zhì)上該多隊列模型可以分為s個獨立的M/M/1/K混合制排隊系統(tǒng)[31]，如圖4所示。定義為第k個排隊系統(tǒng)的交通強度。

圖4 流量分配多隊列模型

令隨機變量N(k)(t)表示在任意時刻t第k個排隊系統(tǒng)中的分組數(shù)，則隨機過程{N(k)(t),t≥0}為E={0,1,2,…,K}上的生滅過程。

引理1[31]對于第k個排隊系統(tǒng)，令，有

因此，第k個隊列中有j個分組的概率為

由于M/M/1/K是損失制，第k個排隊系統(tǒng)損失的概率為

單位時間內(nèi)平均損失的分組數(shù)為

單位時間內(nèi)平均進入排隊系統(tǒng)的分組數(shù)為

平均等待隊長為

經(jīng)推導(dǎo)，可得

于是正在被服務(wù)的平均分組數(shù)為

因此，平均隊長為

于是統(tǒng)計平衡下分組的等待時間分布函數(shù)為

平均等待時間為

對于第k個排隊系統(tǒng)，假設(shè)K=50、μ=1，當(dāng)分組到達(dá)率由0增大到5時，平均隊長、平均等待隊長、隊列中有j個分組的概率和平均等待時間的數(shù)值計算結(jié)果如圖5所示。由圖5可知，隨著分組到達(dá)率的增大，平均隊長、平均等待隊長和平均等待時間都增大，隊列中有j個分組的概率向多分組趨勢轉(zhuǎn)移，這表明采用多路徑流量分配機制能夠有效減少分組排隊等待時間、緩解網(wǎng)絡(luò)擁塞。

圖5 第k個排隊系統(tǒng)性能指標(biāo)的數(shù)值計算結(jié)果

5 仿真實驗

下面利用OMNeT++仿真平臺對LBGR協(xié)議的性能進行仿真評估。對以下5種協(xié)議的性能進行對比分析：GPSR協(xié)議[11]、DGR協(xié)議[25]、GLSR協(xié)議[22]、基于TTE的貪婪地理路由（TTE-based GGR，TTE-based greedy geographic routing）協(xié)議（即只采用基于TTE的貪婪轉(zhuǎn)發(fā)策略，而未采用多路徑流量分配機制），以及LBGR協(xié)議。在節(jié)點數(shù)量為10～100、節(jié)點運動速率為300～1 200 m/s的情況下，分別仿真評估3種協(xié)議的性能。具體仿真參數(shù)設(shè)置如表1所示。仿真結(jié)束后，對協(xié)議的平均分組傳輸成功率和平均端到端時延2項性能指標(biāo)進行對比分析，其中，每個數(shù)值為10次仿真結(jié)果的平均值。

表1 仿真參數(shù)設(shè)置

節(jié)點數(shù)量變化對協(xié)議性能的影響如圖6所示。由圖6(a)和圖6(b)可知，當(dāng)節(jié)點數(shù)量增多時，5種協(xié)議的性能都是先提高后下降，這是因為當(dāng)節(jié)點密度較低時，會出現(xiàn)網(wǎng)絡(luò)分割和局部最優(yōu)化現(xiàn)象，造成分組丟失，并產(chǎn)生較大的傳輸時延；而當(dāng)節(jié)點密度大于30時，由于相應(yīng)的控制開銷增大，占用了一定的信道資源，也會使分組傳輸成功率降低、端到端時延增大。相比較而言，GPSR和TTE-based GGR協(xié)議的性能受節(jié)點數(shù)量變化影響較大，而LBGR、DGR和GLSR協(xié)議的性能較為穩(wěn)定。

節(jié)點運動速率變化對協(xié)議性能的影響如圖7所示。由圖7(a)和圖7(b)可知，隨著節(jié)點運動速率的增大，3種協(xié)議的傳輸成功率都降低、端到端時延都增大，這是因為節(jié)點運動速率的增大造成網(wǎng)絡(luò)拓?fù)涞膭×易兓?，同樣的HELLO周期導(dǎo)致鄰居節(jié)點表更新維護不及時，引起通信暫盲現(xiàn)象。其中，GPSR協(xié)議性能受速率變化的影響最為嚴(yán)重，其次是DGR協(xié)議，而LBGR、TTE-based GGR、GLSR協(xié)議性能所受影響不大，因為這3種協(xié)議正是為航空場景設(shè)計的，也說明基于TTE的分組轉(zhuǎn)發(fā)策略能夠較好適應(yīng)高動態(tài)網(wǎng)絡(luò)環(huán)境。

由圖6和圖7可知，在本文設(shè)定的仿真環(huán)境下，總體而言，LBGR協(xié)議性能最優(yōu)，其次是為民用航空跨洋飛行場景提出的、以分組前進速率為路由選擇依據(jù)的、兼?zhèn)湄?fù)載均衡能力的GLSR協(xié)議，再次是只以TTE為依據(jù)貪婪轉(zhuǎn)發(fā)分組、不具備負(fù)載均衡能力的TTE-based GGR協(xié)議，第四是采用輪詢調(diào)度負(fù)載分配機制的DGR協(xié)議，最后是原始的GPSR協(xié)議。

圖6 當(dāng)節(jié)點運動速率為600 m/s時，節(jié)點數(shù)量變化對協(xié)議性能的影響

6 結(jié)束語

本文為三維高動態(tài)航空自組網(wǎng)設(shè)計了一種多路徑流量分配的負(fù)載均衡地理路由協(xié)議。針對貪婪地理路由協(xié)議應(yīng)用于航空自組網(wǎng)中出現(xiàn)的難以適應(yīng)高動態(tài)網(wǎng)絡(luò)環(huán)境、易造成網(wǎng)絡(luò)擁塞等問題，該協(xié)議一方面將“進入目的節(jié)點通信范圍的時間”作為主要路由決策依據(jù)，取代了貪婪地理路由協(xié)議“距離目的節(jié)點最近”的路由選擇標(biāo)準(zhǔn)，提高了高動態(tài)網(wǎng)絡(luò)環(huán)境下路由選擇的有效性和可靠性；另一方面將流量在多個節(jié)點間合理分配，實現(xiàn)了負(fù)載均衡，有效克服了網(wǎng)絡(luò)擁塞現(xiàn)象。仿真實驗結(jié)果表明，提出的協(xié)議能夠有效提高分組傳輸成功率，降低分組端到端時延，提高數(shù)據(jù)傳輸?shù)膶崟r性和可靠性。該協(xié)議對本領(lǐng)域的研究與應(yīng)用具有一定的參考價值。

圖7 當(dāng)節(jié)點數(shù)量為50時，節(jié)點運動速率變化對協(xié)議性能的影響

[1]CHENG B N,BLOCK F J,HAMILTON B R,et al.Design considerations for next-generation airborne tactical networks[J].IEEE Communications Magazine,2014,52(5):138-145.

[2]BEKMEZCI I,SAHINGOZ O K,TEMEL S.Flying ad hoc networks (FANETs):a survey[J].Ad Hoc Networks,2013,11(3):1254-1270.

[3]梁一鑫,程光,郭曉軍,等.機載網(wǎng)絡(luò)體系結(jié)構(gòu)及其協(xié)議棧研究進展[J].軟件學(xué)報,2016,27(1):96-111.LIANG Y X,CHENG G,GUO X J,et al.Research progress on architecture and protocol stack of the airborne network[J].Journal of Software,2016,27(1):96-111.

[4]鄭博,張衡陽,黃國策,等.航空自組網(wǎng)的現(xiàn)狀與發(fā)展[J].電信科學(xué),2011,27(5):38-47.ZHENG B,ZHANG H Y,HUANG G C,et al.Status and development of aeronautical ad hoc networks[J].Telecommunication Sciences,2011,27(5):38-47.

[5]SAKHAEE E,JAMALIPOUR A.The global in-flight Internet[J].IEEE Journal on Selected Areas in Communications,2006,24(9):1748-1757.

[6]KARRAS K,KYRITSIS T,AMIRFEIZ M,et al.Aeronautical mobile ad hoc networks[C]//14th European Wireless Conference.Prague,Czech Republic,2008:3972-3977.

[7]SCHNELL M,SCALISE S.NEWSKY:a concept for networking the sky for civil aeronautical communications[J].Space Communications,2007,21(3-4):157-166.

[8]PLASS S,HERMENIER R,LUCKE O,et al.Flight trial demonstration of seamless aeronautical networking[J].IEEE Communications Magazine,2014,52(5):119-128.

[9]ROHRER J P,JABBAR A,CETINKAYA E K,et al.Highly-dynamic cross-layered aeronautical network architecture[J].IEEE Transactions on Aerospace and Electronic Systems,2011,47(4):2742-2765.

[10]CADGER F,CURRAN K,SANTOS J,et al.A survey of geographical routing in wireless ad hoc networks[J].IEEE Communications Surveys &Tutorials,2013,15(2):621-653.

[11]KARP B,KUNG H T.GPSR:greedy perimeter stateless routing for wireless networks[C]//ACM 6th Annual International Conference on Mobile Computing and Networking (MobiCOM).New York,2000:243-254.

[12]LAM S S,CHEN Q.Geographic routing in d-dimensional spaces with guaranteed delivery and low stretch[J].IEEE/ACM Transactions on Networking,2013,21(2):663-677.

[13]XIA S,JIN M,WU H,et al.Bubble routing:a scalable algorithm with guaranteed delivery in 3D sensor networks[C]//IEEE SECON.2012:245-253.

[14]YU X,YIN X,HAN W,et al.Scalable routing in 3D high genus sensor networks using graph embedding[C]//IEEE INFOCOM.2012:2681-2685.

[15]YU T,et al.SINUS:a scalable and distributed routing algorithm with guaranteed delivery for WSNs on high genus 3D surfaces[C]//IEEE INFOCOM.2013:2175-2183.

[16]WANG C,JIANG H B,YU T L,et al.SLICE:enabling greedy routing in high genus 3-D WSNs with general topologies[J].IEEE/ACM Transactions on Networking,2016,24(4):2472-2484.

[17]ZHU Y,HUANG Q Y,LI J D,et al.Design and evaluation of airborne communication networks[C]//Seventh IEEE International Conference on Ubiquitous and Future Networks (ICUFN).2015:277-282.

[18]LIN L,SUN Q B,WANG S G,et al.A geographic mobility prediction routing protocol for ad hoc UAV network[C]//IEEE Globecom Workshops,2012.

[19]HYEON S,KIM K,YANG S.A new geographic routing protocol foraircraft ad hoc networks[C]//IEEE/AIAA 29th Digital Avionics Systems Conference (DASC).Salt Lake City,UT,USA,2010.

[20]SHIRANI R,HILAIRE M S,KUNZ T,et al.Combined reactive-geographic routing for unmanned aeronautical ad-hoc networks[C]//8th IEEE International Wireless Communications and Mobile Computing Conference (IWCMC).Limassol,Cyprus,2012:820-826.

[21]LI Y,SHIRANI R,ST-HILAIRE M,et al.Improving routing in networks of UAVs:reactive-greedy-reactive[J].Wireless Communications &Mobile Computing,2012,12(18):1608-1619.

[22]MEDINA D,HOFFMANN F,ROSSETTO F,et al.A geographic routing strategy for north atlantic in-flight Internet access via airborne mesh networking[J].IEEE/ACM Transactions on Networking,2012,20(4):1231-1244.

[23]劉智,徐楨,航空高動態(tài)網(wǎng)絡(luò)負(fù)載感知路由算法[J].北京航空航天大學(xué)學(xué)報,2014,40(12):1697-1701.LIU Z,XU Z.Geographic load aware routing algorithm for highly dynamic airborne networks[J].Journal of Beijing University of Aeronautics and Astronautics,2014,40(12):1697-1701.

[24]BIOMO J D M M,KUNZ T,ST-HILAIRE M.Routing in unmanned aerial ad hoc networks:a recovery strategy for greedy geographic forwarding failure[C]//IEEE Wireless Communications and Networking Conference (WCNC).Istanbul,Turkey,2014:2236-2241.

[25]CHEN M,LEUNG V C M,MAO S,et al.Directional geographical routing for real-time video communications in wireless sensor networks[J].Computer Communications,2007,30(17):3368-3383.

[26]YANG W J,YANG X Y,YANG S S,et al.A greedy-based stable multi-path routing protocol in mobile ad hoc networks[J].Ad Hoc Networks,2011,9(4):662-674.

[27]WANG G D,WANG G,ZHANG J.ELGR:an energy-efficiency and load-balanced geographic routing algorithm for lossy mobile ad hoc networks[J].Chinese Journal of Aeronautics,2010,23(3):334-340.

[28]SHU L,ZHANG Y,YANG L T,et al.TPGF:geographic routing in wireless multimedia sensor networks[J].Telecommunications Systems,,2010,40(1-2):79-95.

[29]LI B Y,CHUANG P J.Geographic energy-aware non-interfering multipath routing for multimedia transmission in wireless sensor networks[J].Information Sciences,,2013,249(16):24-37.

[30]DONG P,QIAN H Y,ZHOU K,et al.A maximally radio-disjoint geographic multipath routing protocol for MANET[J].Ann Telecommun,2015,70(5-6):207-220.

[31]ZUKERMAN M.Introduction to queueing theory and stochastic teletraffic models[J].Eprint Arxiv,2010.

鄭博（1982-），男，陜西咸陽人，博士，空軍工程大學(xué)講師，主要研究方向為移動ad hoc網(wǎng)絡(luò)、機載通信網(wǎng)絡(luò)等。

張衡陽（1978-），男，湖南祁東人，博士，空軍工程大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為移動ad hoc網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)、航空數(shù)據(jù)鏈、機載通信網(wǎng)絡(luò)等。

王寶良（1962-），男，河南開封人，空軍工程大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為航空數(shù)據(jù)鏈。

趙瑋（1993-），男，陜西西安人，空軍工程大學(xué)碩士生，主要研究方向為移動ad hoc網(wǎng)絡(luò)。

Load balancing geographic routing strategy for aeronautical ad hoc networks

ZHENG Bo,ZHANG Heng-yang,WANG Bao-liang,ZHAO Wei
（Information and Navigation Institute,Air Force Engineering University,Xi’an 710077,China）

In aeronautical ad hoc networks,the traditional greedy perimeter stateless routing (GPSR) protocol poses several issues.For example,it is difficult to adapt to the highly-dynamic network environment,and it is prone to cause congestions.In order to address the problems,a TTE (time to enter the communication range of the destination)-based load balancing geographic routing (LBGR) protocol was presented.Taking TTE as the main routing decision metrics,this protocol included the TTE-based packet forwarding scheme,multi-path traffic allocation scheme,and local optimum handling scheme.Furthermore,the multi-path traffic allocation scheme employing the queueing theory was modeled,and the mathematical expressions of some metrics were derived,such as the mean queue size,mean number of packets waiting in the queue,and mean waiting time.Finally,the analysis of the OMNeT++ simulations shows LBGR protocol has advantages over GPSR and some other protocols in terms of the packet delivery ratio and end-to-end delay,and is more suitable for the highly-dynamic aeronautical environment.

aeronautical ad hoc network,greedy geographical routing protocol,load balancing,multi-path,multi-queue,local optimum

s:The National Natural Science Foundation of China (No.61202490),The Aeronautical Science Foundation of China (No.20150896010)

TP393

A

10.11959/j.issn.1000-436x.2016273

2016-06-04；

2016-11-15

資助項目（No.61202490）；航空科學(xué)基金資助項目（No.20150896010）