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

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

（空軍工程大學(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)高動(dò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種機(jī)制。進(jìn)一步采用排隊(duì)論對多路徑流量分配策略進(jìn)行了建模分析，得出了平均隊(duì)長、平均等待隊(duì)長、平均等待時(shí)間等性能指標(biāo)的數(shù)學(xué)表達(dá)式。最后利用OMNeT++仿真平臺(tái)對LBGR協(xié)議的性能進(jìn)行了仿真驗(yàn)證，結(jié)果表明相比GPSR等協(xié)議，LBGR協(xié)議在分組傳輸成功率和端到端時(shí)延方面有較大幅度的提升，能夠有效適應(yīng)高動(dòng)態(tài)航空環(huán)境。

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 鄰居節(jié)點(diǎn)nk與目的節(jié)點(diǎn)d之間的相對運(yùn)動(dòng)

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

其相對速率可表示為

2) 進(jìn)入目的節(jié)點(diǎn)通信范圍的時(shí)間TTE

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

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

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

定義TTE為

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

4 多路徑流量分配機(jī)制建模分析

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

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

圖4 流量分配多隊(duì)列模型

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

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

因此，第k個(gè)隊(duì)列中有j個(gè)分組的概率為

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

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

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

平均等待隊(duì)長為

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

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

因此，平均隊(duì)長為

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

平均等待時(shí)間為

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

圖7 當(dāng)節(jié)點(diǎn)數(shù)量為50時(shí)，節(jié)點(diǎn)運(yùn)動(dòng)速率變化對協(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]梁一鑫,程光,郭曉軍,等.機(jī)載網(wǎng)絡(luò)體系結(jié)構(gòu)及其協(xié)議棧研究進(jìn)展[J].軟件學(xué)報(bào),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]劉智,徐楨,航空高動(dòng)態(tài)網(wǎng)絡(luò)負(fù)載感知路由算法[J].北京航空航天大學(xué)學(xué)報(bào),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é)講師，主要研究方向?yàn)橐苿?dòng)ad hoc網(wǎng)絡(luò)、機(jī)載通信網(wǎng)絡(luò)等。

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

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

趙瑋（1993-），男，陜西西安人，空軍工程大學(xué)碩士生，主要研究方向?yàn)橐苿?dòng)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

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