基于ODMRP的分布式核心穩(wěn)定路由算法①

傅 偉,周新力,劉 軍

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

2(66135部隊(duì),北京 100144)

1 前言

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

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

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

2 ODMRP協(xié)議改進(jìn)機(jī)制

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

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

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

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

2.1.1 空洞問(wèn)題分析

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

2.1.2 改進(jìn)方案

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

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

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

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

2.2 分布式核心節(jié)點(diǎn)選擇機(jī)制

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

2.2.1 核心節(jié)點(diǎn)選擇標(biāo)準(zhǔn)

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

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

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

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

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

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

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

(2)不存在交叉路徑時(shí),選擇貪婪轉(zhuǎn)發(fā)過(guò)程中第一個(gè)分段點(diǎn)作為核心節(jié)點(diǎn);

(3)既不存在交叉路徑也不存在路由空洞時(shí),選擇核心節(jié)點(diǎn)標(biāo)準(zhǔn)N(i)最高的節(jié)點(diǎn)作為核心節(jié)點(diǎn).

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

2.3 鏈路搶修機(jī)制

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

2.3.1 搶修發(fā)起時(shí)機(jī)

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

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

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

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

2.3.2 搶修發(fā)起過(guò)程

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

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

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

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

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

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

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

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

表1 Join-Request/Join-Table分組數(shù)據(jù)結(jié)構(gòu)

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

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

3.2 路由過(guò)程

3.2.1 正向路由建立

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

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

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

(3)節(jié)點(diǎn)接收到Join-Request分組首先判斷之前是否接受過(guò)來(lái)自于同一個(gè)源節(jié)點(diǎn)的Join-Request分組.如果是,則將該節(jié)點(diǎn)寫(xiě)入Core Node字段.進(jìn)行第(4)步;

(4)判斷選擇標(biāo)準(zhǔn)中是否滿(mǎn)足0 ≤θ＜π.如果是,進(jìn)行第(5)步;否則,將Prior Sending State設(shè)置為0,進(jìn)行第(6)步;

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

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

3.2.2 反向路由建立

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

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

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

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

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

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

(6)判斷該節(jié)點(diǎn)是否為分段點(diǎn),如果是則發(fā)起一個(gè)向下一個(gè)分段點(diǎn)的尋路過(guò)程,直到到達(dá)下一個(gè)分段點(diǎn),進(jìn)行第(4)步.

由于節(jié)點(diǎn)的移動(dòng)性導(dǎo)致路由過(guò)程中部分節(jié)點(diǎn)失效,在一段時(shí)間內(nèi)沒(méi)有接收到Sop包的轉(zhuǎn)發(fā)節(jié)點(diǎn)判斷路失效主動(dòng)退出組播組.

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

4 仿真分析

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

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

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

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

圖5 平均端到端時(shí)延

圖6 分組交付率

圖7顯示的是ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在不同節(jié)點(diǎn)密度下網(wǎng)絡(luò)負(fù)載的變化趨勢(shì).可以看出ODMRP協(xié)議、VCMP協(xié)議以及DKSR協(xié)議在網(wǎng)絡(luò)負(fù)載上相差不大.雖然在節(jié)點(diǎn)密度不大的情況下,VCMP協(xié)議以及DKSR協(xié)議對(duì)于路徑優(yōu)化信息的引入導(dǎo)致網(wǎng)絡(luò)負(fù)載稍有增加,但是但隨著網(wǎng)絡(luò)節(jié)點(diǎn)密度的增大,對(duì)路徑的優(yōu)化效果明顯,多余的節(jié)點(diǎn)傳輸減少,網(wǎng)絡(luò)負(fù)載降低,而ODMRP協(xié)議通過(guò)洪泛的方式建立路由大大增加了網(wǎng)絡(luò)的負(fù)載.DKSR協(xié)議通過(guò)穩(wěn)定算法以及核心節(jié)點(diǎn)選擇機(jī)制建立穩(wěn)定鏈路,并且通過(guò)搶修機(jī)制保證鏈路有效性,減少了由于鏈路斷裂導(dǎo)致重新建立鏈路,從而降低了網(wǎng)絡(luò)負(fù)載,因此隨著節(jié)點(diǎn)密度的增大曲線趨于穩(wěn)定.而VCMP協(xié)議會(huì)因?yàn)橥負(fù)涞淖兓糠宙溌肥?從而網(wǎng)絡(luò)負(fù)載上升.

圖7 網(wǎng)絡(luò)開(kāi)銷(xiāo)

5 結(jié)語(yǔ)

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