傅 偉,周新力,劉 軍

1(海軍航空大學 電子信息工程系,煙臺 264001)

2(66135部隊,北京 100144)

1 前言

當前無人機的作戰(zhàn)形式由單機作戰(zhàn)向多機聯(lián)合作戰(zhàn)形式轉變,無人機群所展現(xiàn)出來的全方位大范圍的作戰(zhàn)能力是單個無人機所無法比擬的,但是這種高速高動態(tài)的作戰(zhàn)環(huán)境需要更加靈活的通信方式和嚴密的標準.移動自組網(wǎng)絡(Mobile Ad hoc NETwork,MANET)以其無中心、自組織、動態(tài)拓撲和多路徑的特點,成為集群作戰(zhàn)的首選方式.組播網(wǎng)絡作為MANET網(wǎng)絡形式中的一種就具有廣闊的應用空間,特別是在無人機戰(zhàn)術網(wǎng)絡平臺,通過一對多的數(shù)據(jù)分發(fā)使得信息的傳輸更加及時高效.和單播路由協(xié)議相比,組播網(wǎng)絡可以實現(xiàn)多種信息的同傳,大大節(jié)省了網(wǎng)絡帶寬.但是移動網(wǎng)絡中由于拓撲結構不斷變化,對于組播組的結構和維護消息也會大幅增加,這就要求對組播網(wǎng)絡進行改進以適應移動網(wǎng)絡環(huán)境.

近些年不少學者研究并提出了較多組播路由協(xié)議.文獻[1]提出了一種結合貪婪算法與區(qū)域組播的結合的組播協(xié)議,雖然通過源節(jié)點能夠較快的聚合出最優(yōu)路徑但也增加了源節(jié)點的負擔,也沒有解決貪婪算法會遇到的空洞問題.文獻[2]提出了一種基于區(qū)域劃分的地理組播協(xié)議,但是區(qū)域角的確定只適用于靜止的網(wǎng)絡,節(jié)點的移動會產(chǎn)生較大影響.文獻[3]提出了一種基于能量高效的組播協(xié)議,采用最短路徑的思想尋找耗能最低路徑,算法對特定節(jié)點的過分消耗會加速網(wǎng)絡的崩潰.文獻[4]通過改變路徑來實現(xiàn)能量的動態(tài)均衡,但是沒有考慮路徑信息的傳輸對網(wǎng)絡能量的消耗.文獻[5]提出了一種分層式的節(jié)點自適應修復方法,通過設置冗余節(jié)點對失效節(jié)點進行修復,但是大量冗余信息的儲存造成網(wǎng)絡資源的消耗.文獻[6]提出了一種混合式的應用層組播恢復方法,解決了中心節(jié)點失效造成的網(wǎng)絡癱瘓,但是網(wǎng)絡的組織具有較高的復雜性.

雖然我國在無人機領域取得了一定的成就,一部分民用無人機研發(fā)機構也實現(xiàn)了對多無人機的操控,但是這種基于表演性質的操控對于真正應用于戰(zhàn)場環(huán)境還有較大差距.同時,軍用無人機對于提升無人機協(xié)同作戰(zhàn)能力具有迫切需求,目前為止只實現(xiàn)了對兩架無人機的同時操控.因此,開展對于無人機自組織網(wǎng)絡協(xié)議的研究,為實現(xiàn)真正的無人機集群作戰(zhàn)的通信,具有較大的軍事價值和研究意義.

2 ODMRP協(xié)議改進機制

ODMRP(On-Demand Multicast Routing Protocol)協(xié)議是一種網(wǎng)格型的組播路由協(xié)議,轉發(fā)路徑的形成是按需發(fā)起的.由于采用洪泛機制發(fā)起路由,多節(jié)點的重復廣播很容易引起沖突導致報文丟失,同時隨著網(wǎng)絡的擴大,即使有范圍洪泛對開銷的控制,也會造成無法避免的巨大開銷.同時,協(xié)議雖然通過網(wǎng)格結構建立了冗余鏈路,但由于屬于按需型,鏈路穩(wěn)定性難以保證.

針對ODMRP協(xié)議存在的不足,文章引入了貪婪算法優(yōu)化機制,解決因為洪泛問題導致的開銷過大,同時提出了分布式核心節(jié)點選擇機制和鏈路搶修機制分別用以減少節(jié)點的信息存儲和提高鏈路的魯棒性.在第3節(jié)中將三個優(yōu)化機制整合,提出分布式核心穩(wěn)定路由算法.仿真實驗證明,該算法在平均端到端時延、分組交付率及網(wǎng)絡開銷等方面明顯優(yōu)于ODMRP協(xié)議與以VCMP協(xié)議為代表的改進算法,適用于多無人機聯(lián)合通信環(huán)境.

2.1 貪婪算法優(yōu)化機制

ODMRP協(xié)議通過洪泛Join-Request分組的方式尋找到達目的節(jié)點的路由,雖然這種方式可以建立起到達目的節(jié)點的冗余路徑,但是路徑的穩(wěn)定性無法得到保證,且選出的“最短”路徑并非最佳.當網(wǎng)絡中數(shù)據(jù)交換量較大的情況下會導致網(wǎng)絡開銷過大.因此引入貪婪算法作為路由發(fā)現(xiàn)機制,并進行改進解決貪婪算法過程中出現(xiàn)的路由空洞問題.

2.1.1 空洞問題分析

貪婪算法尋找到達目的節(jié)點的路徑,這種方法在一般情況下往往會以最快的速度選擇一條最短路徑,但是當發(fā)送節(jié)點在其通信范圍內找不到比本節(jié)點“距離”目的節(jié)點更“近”的節(jié)點時,就會產(chǎn)生路由空洞[7].解決路由空洞問題最常用的方法是根據(jù)節(jié)點的分布,將網(wǎng)絡連接圖平面化[8,9],將數(shù)據(jù)向著更接近于目的節(jié)點的節(jié)點轉發(fā),直到能夠恢復到貪婪算法[10].但是這種單純的依據(jù)靜止的拓撲信息進行路由發(fā)現(xiàn)的周邊轉發(fā)算法不適用于動態(tài)拓撲,需要一種更加靈活的方式完成路由.

2.1.2 改進方案

為了解決上述問題,文章提出基于已有路徑采取反向優(yōu)化機制,改進了數(shù)據(jù)傳輸過程中的數(shù)據(jù)結構,很好的解決了這種路徑繞行問題,既不產(chǎn)生多余的數(shù)據(jù)包,也不會增加時延.

通過對路由空洞形態(tài)的分析可以發(fā)現(xiàn),在周邊節(jié)點中必然會存在某些特殊的幾何位置,在這些位置上的節(jié)點之間可以通過貪婪算法建立路由,而不需要周邊轉發(fā),且路由跳數(shù)較少.因此,當目的節(jié)點在接收到數(shù)據(jù)包后,讀取數(shù)據(jù)包內所包含的信息,為保證后續(xù)數(shù)據(jù)能夠以更短的時延、更小的能量損耗傳輸,對處于周邊轉發(fā)狀態(tài)的路徑進行優(yōu)化.例如圖1所示空洞,S節(jié)點首先向D節(jié)點發(fā)起一次數(shù)據(jù)傳輸,根據(jù)貪婪轉發(fā)算法當數(shù)據(jù)到達A節(jié)點后遇到路由空洞,隨后轉發(fā)方式變?yōu)橹苓呣D發(fā)算法到達B點,轉發(fā)方式恢復為貪婪轉發(fā)發(fā)送到C節(jié)點,再次遇到路由空洞周邊轉發(fā)到E節(jié)點,由E貪婪轉發(fā)到D節(jié)點.轉發(fā)過程中,數(shù)據(jù)包將正向路徑中由周邊轉發(fā)轉為貪婪轉發(fā)的節(jié)點標記為分段點(如B和E).

反向優(yōu)化時,目的節(jié)點D首先讀取數(shù)據(jù)包中的分段點,通過貪婪轉發(fā)的方式反向發(fā)送到E節(jié)點,再從分段點中尋找下一個最近分段節(jié)點B,并發(fā)起一次貪婪轉發(fā),若轉發(fā)過程中由于節(jié)點的移動性產(chǎn)生新的空洞,同樣將更新后的路徑和狀態(tài)記錄到數(shù)據(jù)包中.由B到S進行相同操作,不再贅述.

優(yōu)化后的路徑在數(shù)據(jù)傳輸過程中同樣保留路徑優(yōu)化功能,當由于節(jié)點的移動導致中間節(jié)點失效時能夠及時發(fā)現(xiàn)、及時優(yōu)化.

2.2 分布式核心節(jié)點選擇機制

上節(jié)中雖然引入貪婪算法來解決網(wǎng)絡開銷問題,但無法保證所選鏈路的穩(wěn)定性,而且在移動網(wǎng)絡中節(jié)點加入或退出時需要告知所有節(jié)點網(wǎng)絡拓撲的變化,大大增加了節(jié)點的儲存空間[11].文章提出通過建立分布式核心節(jié)點,在核心節(jié)點中存儲組播組的地址以及組成員的信息,在拓撲發(fā)生變化時只更新核心節(jié)點中的信息,而不用通知所有組成員,這樣既降低了儲存空間,也降低了網(wǎng)絡開銷.

2.2.1 核心節(jié)點選擇標準

在貪婪算法對節(jié)點的選擇上,為了能夠滿足更多的傳輸需求,需要對貪婪算法進行改進.通常,無人機在執(zhí)行飛行任務時會根據(jù)航程、能量攜帶情況規(guī)定一定的巡航時間,當能量耗盡就退出所屬機群返航,因此為了增加無人機巡航范圍和巡航時間,需要盡可能的合理分配功率消耗.在通信領域,能量的消耗主要來自于數(shù)據(jù)的發(fā)送,盡可能的避免低能量節(jié)點發(fā)送數(shù)據(jù)包是提高偵查能力的主要方法.

如圖2所示,將節(jié)點的傳輸范圍劃分為三個部分,以源節(jié)點與目的節(jié)點的連線為軸方向左右各取α角,在此區(qū)域內接收節(jié)點與目的節(jié)點之間的歐氏距離小于發(fā)送節(jié)點與目的節(jié)點的歐氏距離,選得的接收節(jié)點為I區(qū)域最優(yōu)點.由2α向兩邊繼續(xù)擴張到180度,上下兩部分共同組成II區(qū)域,該區(qū)域中依然有部分節(jié)點滿足I區(qū)域條件,節(jié)點選擇需要考慮在內.節(jié)點傳輸范圍內的剩余部分組成III區(qū)域,在I區(qū)域和II區(qū)域都無法選擇符合要求的節(jié)點時,需在該區(qū)域選擇周邊轉發(fā)節(jié)點,此時空間傳輸?shù)膬?yōu)勢已不再作為主要標準,能量均衡顯得尤為重要[12].由此得到核心節(jié)點的選擇標準:

圖2 節(jié)點選擇范圍

其中,N(i)是核心節(jié)點的選擇判據(jù),選擇可選區(qū)域內判據(jù)最大的點作為下一跳節(jié)點,β是修正系數(shù),根據(jù)節(jié)點所在位置取值,d(S,N)是發(fā)送節(jié)點與接收節(jié)點的距離,Eres是 節(jié)點的剩余能量,Ecap是節(jié)點的總能量.

2.2.2 核心節(jié)點選擇方案

根據(jù)改進貪婪算法方案,源節(jié)點首先發(fā)起一次向多個組播目的節(jié)點的尋路過程,并將源節(jié)點作為第一個核心節(jié)點.路由節(jié)點的選擇根據(jù)核心節(jié)點選擇標準,并在數(shù)據(jù)包中記錄路由發(fā)現(xiàn)與優(yōu)化過程中N(i)最高的節(jié)點,核心節(jié)點的選擇分為以下三個優(yōu)先級:

(1)同一個節(jié)點收到來自于同一個源節(jié)點不同目的節(jié)點的Join-Request分組,則將該節(jié)點作為核心節(jié)點;

(2)不存在交叉路徑時,選擇貪婪轉發(fā)過程中第一個分段點作為核心節(jié)點;

(3)既不存在交叉路徑也不存在路由空洞時,選擇核心節(jié)點標準N(i)最高的節(jié)點作為核心節(jié)點.

每一條路徑上除源節(jié)點外只存在一個核心節(jié)點,核心節(jié)點選擇完成后通知源節(jié)點并獲得組播網(wǎng)絡中所有節(jié)點的路由信息.

2.3 鏈路搶修機制

由于節(jié)點的移動特性,部分中間節(jié)點不再適用于路由傳輸,需要重新改變路由信息,這樣不但會導致鏈路的斷裂與部分數(shù)據(jù)的丟失,同樣會增加網(wǎng)絡負載.為此,將一種基于鏈路生存時間的搶修機制引入算法,在鏈路斷裂之前發(fā)起局部鏈路的修復過程,保證數(shù)據(jù)不丟失.

2.3.1 搶修發(fā)起時機

根據(jù)無線信號功率計算的地面反射模型可得:

Pr是無線信號的接收功率,Pt是無線信號的發(fā)射功率,Gt和Gr是發(fā)送天線和接收天線的增益,ht和hr為發(fā)送節(jié)點和接收節(jié)點的有效高度,d為兩節(jié)點之間的水平距離.為了簡化模型將公式中的常量抽象為統(tǒng)一參數(shù)k,得到簡化模型:

假設每個節(jié)點發(fā)送的數(shù)據(jù)包功率相同,隨著距離的增加節(jié)點接收到的數(shù)據(jù)包功率降低,節(jié)點能夠接收到的數(shù)據(jù)包的最小功率為Pmin,節(jié)點通信范圍為R,移動速度為v,單跳傳輸時間為ts.為了保證鏈路完整性以及不新鏈路會造成過多的開銷,局部鏈路的修復在8跳時間內完成.由此可以得到數(shù)據(jù)包警告功率:

當節(jié)點數(shù)據(jù)包的接受功率處于降低狀態(tài)且已觸發(fā)路由警告后,節(jié)點會根據(jù)其移動方向計算鏈路的生存時間.若生存時間小于修復時間時,發(fā)起局部搶修.生存時間的計算公式如下:

2.3.2 搶修發(fā)起過程

搶修發(fā)起過程如圖3所示,節(jié)點B連續(xù)收到來自節(jié)點A的數(shù)據(jù)包,接收到數(shù)據(jù)包的功率一直處于下降狀態(tài)且最后一次的接收功率大小低于警告功率時(過程1),首先返回一個通知包通知上一跳節(jié)點鏈路處于危險狀態(tài)(過程2),同時轉發(fā)接收到的數(shù)據(jù)包,并等待兩跳的時間(過程3).在兩跳時間內未收到來自下一跳節(jié)點的警告信息,則判斷該節(jié)點與上一跳節(jié)點之間鏈路危險,那么向上一跳節(jié)點的前跳節(jié)點D發(fā)起一次貪婪轉發(fā)(過程4).若在兩跳時間內收到來自下一跳節(jié)點的警告信息(過程5),則判斷為該節(jié)點與鏈路遠離,那么向上一跳節(jié)點返回通知包(過程6),通知前跳節(jié)點發(fā)起一次向下一跳節(jié)點的貪婪轉發(fā)(過程7).

圖3 搶修發(fā)起過程

為避免路由陷入連續(xù)的更新導致負載變大,收到鏈路危險通知的節(jié)點在收到來自同一源節(jié)點的尋路分組后不返回應答分組,不參與轉發(fā).

3 分布式核心穩(wěn)定路由算法

3.1 數(shù)據(jù)包格式

為了實現(xiàn)改進后的協(xié)議功能需要對數(shù)據(jù)包的格式進行重新定義.

當源節(jié)點需要發(fā)送數(shù)據(jù)時,需要發(fā)送Join-Request分組去發(fā)現(xiàn)到達組播成員的路徑來組建一個新的組播組.為了實現(xiàn)改進貪婪機制的功能,Join-Table分組采用與Join-Request分組相同的數(shù)據(jù)格式.表1為改進后的數(shù)據(jù)結構.圖4為其數(shù)據(jù)封裝結構.

算法將組播組中組播成員以及地址信息儲存在核心節(jié)點中,普通轉發(fā)節(jié)點只需要維護一張相鄰兩跳的路徑信息表,減少了由于拓撲的變化產(chǎn)生的路由信息大量更新,也減少了普通轉發(fā)節(jié)點的儲存空間.表2為轉發(fā)節(jié)點路徑信息表.

表1 Join-Request/Join-Table分組數(shù)據(jù)結構

圖4 Join-Request/Join-Table分組數(shù)據(jù)結構封裝

表2 轉發(fā)節(jié)點路徑信息表

3.2 路由過程

3.2.1 正向路由建立

根據(jù)改進機制對ODMRP協(xié)議的路由建立過程進行優(yōu)化,具體步驟如下:

(1)源節(jié)點有數(shù)據(jù)需要發(fā)送,首先將源節(jié)點設置為核心節(jié)點,但不計入Join-Request分組中.設置Core Node字段為空,NIMAX=0;

(2)向參與組播的目的節(jié)點發(fā)送Join-Request分組,并按照核心節(jié)點選擇機制選擇下一跳;

(3)節(jié)點接收到Join-Request分組首先判斷之前是否接受過來自于同一個源節(jié)點的Join-Request分組.如果是,則將該節(jié)點寫入Core Node字段.進行第(4)步;

(4)判斷選擇標準中是否滿足0 ≤θ＜π.如果是,進行第(5)步;否則,將Prior Sending State設置為0,進行第(6)步;

(5)判斷Prior Sending State的值是否為0,如果是,則將該節(jié)點的ID和地址插入到Segment Point字段中,進行第(6)步;若Prior Sending State的值為1,直接進行第(6)步;

(6)判斷下一跳節(jié)點是否為目的節(jié)點,若是.則直接發(fā)送分組結束正向路由搭建過程;若不是,比較該節(jié)點到下一跳節(jié)點選擇標準N(i)的值與NIMAX的值,將較大的值計入NIMAX字段,并發(fā)送分組,進行第(3)步.

3.2.2 反向路由建立

根據(jù)正向路由得到的信息構建Join-Table分組進行反向路徑的確認,具體步驟如下:

(1)目的節(jié)點首先讀取正向路徑信息中是否存在核心節(jié)點,如若有,則將其設定為該路徑的核心節(jié)點并寫入Join-Table分組中的Core Node字段,按照記錄的路由發(fā)送分組,進行第(4)步,若沒有則進行第(2)步;

(2)查找Join-Request分組中Segment Point字段是否記錄分段點信息,如果有,則將其設定為該路徑的核心節(jié)點并寫入Join-Table分組中的Core Node字段,按照記錄的路由發(fā)送分組,進行第(4)步,否則,進行第(3)步;

(3)將NIMAX字段中記錄的節(jié)點設定為該路徑的核心節(jié)點并寫入Join-Table分組中的Core Node字段,按照記錄的路由發(fā)送分組,進行第(4)步;

(4)接收到Join-Table分組的節(jié)點首先判斷自己是否為源節(jié)點,如果是,則結束反向路由建立,如果不是,進行第(5)步;

(5)判斷該節(jié)點是否為核心節(jié)點,如果是則標記為核心節(jié)點,建立核心節(jié)點路由表,記錄組播組的地址及成員節(jié)點信息,進行第(6)步,否則直接進行第(6)步;

(6)判斷該節(jié)點是否為分段點,如果是則發(fā)起一個向下一個分段點的尋路過程,直到到達下一個分段點,進行第(4)步.

由于節(jié)點的移動性導致路由過程中部分節(jié)點失效,在一段時間內沒有接收到Sop包的轉發(fā)節(jié)點判斷路失效主動退出組播組.

路由搶修發(fā)起的時機與過程在2.3節(jié)中已有敘述,在此不再贅述.

4 仿真分析

本文使用opnet[13]進行仿真,在場景配置中,為使得最終的仿真結果更加直觀,將本文協(xié)議分布式核心穩(wěn)定路由協(xié)議命名為DKSR(Distribute Kernel Stable Routing).為了驗證算法的優(yōu)化性能,選擇與組播路由中性能較好的ODMRP[14]路由協(xié)議以及同樣針對ODMRP進行改進的變核心組播協(xié)議 VCMP(Variable Core Multicast route Protocol[15])算法從平均端到端時延、分組交付率和網(wǎng)絡開銷三個方面進行比較,并對不同節(jié)點密度下的協(xié)議性能進行仿真.VCMP算法通過在源節(jié)點與目的節(jié)點之間設置單個核心節(jié)點的方式建立路由,源節(jié)點與核心節(jié)點之間通過單播協(xié)議傳輸,由核心節(jié)點將數(shù)據(jù)洪泛給目的節(jié)點.主要仿真參數(shù)見表3.

表3 主要仿真參數(shù)設置

圖5顯示的是ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在不同節(jié)點密度下平均端到端時延的變化趨勢.可以看出,比較于ODMRP協(xié)議,VCMP協(xié)議以及DKSR協(xié)議具有更加明顯的優(yōu)勢.這是因為VCMP協(xié)議以及DKSR協(xié)議都通過貪婪算法對ODMRP協(xié)議的路由發(fā)現(xiàn)過程進行了改進,能夠更快的尋找到組播成員節(jié)點.比較于VCMP協(xié)議,在節(jié)點密度較小的情況下,DKSR協(xié)議的端到端時延稍有增加,這是因為該協(xié)議在路由發(fā)現(xiàn)過程中會通過反向優(yōu)化來減少路由繞行,隨著節(jié)點數(shù)目的增加,鏈路的穩(wěn)定性優(yōu)勢突出,優(yōu)化效果更加明顯.VCMP協(xié)議采用單一的路由發(fā)現(xiàn)方式,隨著節(jié)點數(shù)目增加,鏈路不穩(wěn)定因素增多導致核心節(jié)點頻繁更新.因此,DKSR協(xié)議具有更好的網(wǎng)絡擴展性.

圖6顯示的是ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在不同節(jié)點密度下分組交付率的變化趨勢.可以看出,比較于ODMRP協(xié)議和VCMP協(xié)議,DKSR協(xié)議的分組交付率優(yōu)勢更加明顯.這是因為DKSR協(xié)議能夠選擇一條更加穩(wěn)定的路由,并且能夠隨著網(wǎng)絡拓撲的變化及時的修復路徑,保證節(jié)點能夠準確的交付.而VCMP協(xié)議對核心節(jié)點的選取和變化條件單一,路徑的修復不及時,因此導致部分數(shù)據(jù)丟失,交付率下降.

圖5 平均端到端時延

圖6 分組交付率

圖7顯示的是ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在不同節(jié)點密度下網(wǎng)絡負載的變化趨勢.可以看出ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在網(wǎng)絡負載上相差不大.雖然在節(jié)點密度不大的情況下,VCMP協(xié)議以及DKSR協(xié)議對于路徑優(yōu)化信息的引入導致網(wǎng)絡負載稍有增加,但是但隨著網(wǎng)絡節(jié)點密度的增大,對路徑的優(yōu)化效果明顯,多余的節(jié)點傳輸減少,網(wǎng)絡負載降低,而ODMRP協(xié)議通過洪泛的方式建立路由大大增加了網(wǎng)絡的負載.DKSR協(xié)議通過穩(wěn)定算法以及核心節(jié)點選擇機制建立穩(wěn)定鏈路,并且通過搶修機制保證鏈路有效性,減少了由于鏈路斷裂導致重新建立鏈路,從而降低了網(wǎng)絡負載,因此隨著節(jié)點密度的增大曲線趨于穩(wěn)定.而VCMP協(xié)議會因為拓撲的變化部分鏈路失效,從而網(wǎng)絡負載上升.

圖7 網(wǎng)絡開銷

5 結語

本文針對組播路由的建立問題提出改進算法,改進貪婪選擇機制以減少路由發(fā)現(xiàn)過程中的數(shù)據(jù)洪泛以及路由空洞,考慮到成員節(jié)點負載能力有限提出了核心節(jié)點選擇算法,以減少儲存空間,同時提出通過鏈路搶修機制提前修復危險鏈路保證路徑的有效性和交付率.仿真實驗證明,DKSR協(xié)議能夠很好的提升組播網(wǎng)絡的性能,雖然造成了網(wǎng)絡負載的稍有增加,但在可接受范圍內對網(wǎng)絡性能做出明顯優(yōu)化,能夠達到多無人機聯(lián)合通信需求.