李季碧,鄧科,任智,黃堰江,陳前斌,劉東遠(yuǎn)

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,400065,重慶)

?

機(jī)會(huì)網(wǎng)絡(luò)中高效低時(shí)延多擺渡節(jié)點(diǎn)路由算法

李季碧,鄧科,任智,黃堰江,陳前斌,劉東遠(yuǎn)

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,400065,重慶)

針對機(jī)會(huì)網(wǎng)絡(luò)中帶網(wǎng)關(guān)節(jié)點(diǎn)的多擺渡節(jié)點(diǎn)路由算法(MMFGW)存在部分區(qū)外消息冗余等待、數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)偏多和相鄰區(qū)擺渡節(jié)點(diǎn)之間無協(xié)作的情況,提出了一種新的多擺渡高效低時(shí)延路由算法(ERMF)。當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)有數(shù)據(jù)發(fā)送時(shí),ERMF算法通過查詢跨層旁聽機(jī)制建立區(qū)外屬性表,確認(rèn)表中有匹配,則數(shù)據(jù)不再經(jīng)過本地?cái)[渡節(jié)點(diǎn)轉(zhuǎn)發(fā),而是向網(wǎng)關(guān)節(jié)點(diǎn)直傳。另外,跨區(qū)域擺渡節(jié)點(diǎn)之間相遇時(shí),通過彼此交換自己區(qū)域內(nèi)的節(jié)點(diǎn)信息獲取屬于本區(qū)域內(nèi)的有效數(shù)據(jù),這2種直接通信的協(xié)作機(jī)制均可優(yōu)化節(jié)點(diǎn)間單一的數(shù)據(jù)交互方式,促進(jìn)區(qū)域間數(shù)據(jù)的快速傳輸,在不影響原有數(shù)據(jù)傳輸功能的前提下降低數(shù)據(jù)分組時(shí)延和轉(zhuǎn)發(fā)開銷。仿真結(jié)果表明,與MMFGW算法和節(jié)點(diǎn)中繼算法相比,ERMF算法的數(shù)據(jù)分組轉(zhuǎn)發(fā)開銷和平均端到端時(shí)延分別降低了8.1%和7.3%以上。

機(jī)會(huì)網(wǎng)絡(luò);路由算法;消息擺渡;轉(zhuǎn)發(fā)開銷;端到端時(shí)延

機(jī)會(huì)網(wǎng)絡(luò)是一種在無線鏈路斷開和網(wǎng)絡(luò)分裂情況下即使不存在端到端路徑也能夠傳輸信息的新型網(wǎng)絡(luò)[1],而這種新型網(wǎng)絡(luò)的特性給路由設(shè)計(jì)帶來了一些挑戰(zhàn)。由于路由算法的好壞直接影響著網(wǎng)絡(luò)的性能[2],因此人們在機(jī)會(huì)網(wǎng)絡(luò)場景中設(shè)計(jì)了多種最優(yōu)的路由算法[3],其中帶可控移動(dòng)節(jié)點(diǎn)的多區(qū)域擺渡路由設(shè)計(jì)是人們更為關(guān)注的一個(gè)研究熱點(diǎn)。多擺渡(Ferry)路由算法不同于單擺渡路由算法[4],它不僅要關(guān)注每個(gè)擺渡節(jié)點(diǎn)如何選擇最優(yōu)路徑,而且要考慮多個(gè)擺渡節(jié)點(diǎn)間如何高效地交互協(xié)作[5-6]。因此,如何最大限度減少時(shí)延和轉(zhuǎn)發(fā)開銷就成了學(xué)者研究的重點(diǎn)。

目前,根據(jù)擺渡節(jié)點(diǎn)間的協(xié)調(diào)部署方式不同,多擺渡節(jié)點(diǎn)路由算法主要分為單路徑算法(SIRA)和多路徑算法(MURA)2大方向[7]。其中典型的MURA算法又分為2類:一類是擺渡中繼算法(FRA),其思想是擺渡節(jié)點(diǎn)按照預(yù)先設(shè)定路線需同時(shí)同地到達(dá)才可交互數(shù)據(jù),它屬于一種直接通信方式,但該方式要求擺渡節(jié)點(diǎn)具有直接同步交互能力,實(shí)時(shí)性很高,因此在現(xiàn)實(shí)中很難實(shí)現(xiàn);另一類是節(jié)點(diǎn)中繼算法(NRA),它是一種間接通信方式,其思想是通過擺渡節(jié)點(diǎn)和放置在鄰區(qū)位置的中繼節(jié)點(diǎn)之間的協(xié)調(diào)配合來完成數(shù)據(jù)的傳輸,比如文獻(xiàn)[8]提到的一種附帶具有大緩存空間的特殊轉(zhuǎn)發(fā)節(jié)點(diǎn)——Throwbox節(jié)點(diǎn)的星型拓?fù)銶RT-Star路由方案,以及文獻(xiàn)[9]談到的一種將區(qū)域信使和獨(dú)立信使2類節(jié)點(diǎn)充當(dāng)不同類型的擺渡節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)的路由策略,這類算法在處理節(jié)點(diǎn)間分配方式和數(shù)據(jù)交互方式上不僅不夠優(yōu)化而且缺乏相互協(xié)作,造成區(qū)域間數(shù)據(jù)更新滯后。最具代表性的是文獻(xiàn)[10]提出的帶網(wǎng)關(guān)節(jié)點(diǎn)的多消息擺渡節(jié)點(diǎn)路由算法(MMFGW),該算法利用網(wǎng)關(guān)節(jié)點(diǎn)來為各類擺渡節(jié)點(diǎn)間提供交互和中繼區(qū)外消息服務(wù),但我們在研究中發(fā)現(xiàn)網(wǎng)關(guān)節(jié)點(diǎn)和擺渡節(jié)點(diǎn)交互階段以及相鄰區(qū)擺渡節(jié)點(diǎn)間相遇階段存在以下2個(gè)問題:①網(wǎng)關(guān)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)發(fā)送的區(qū)外信息等待時(shí)延過長和中間轉(zhuǎn)發(fā)次數(shù)偏多;②相鄰區(qū)擺渡節(jié)點(diǎn)間相遇時(shí),節(jié)點(diǎn)間無協(xié)作,缺乏數(shù)據(jù)的直接交互,減緩了區(qū)域間數(shù)據(jù)的快速傳輸。針對以上問題,本文提出了一種新的多擺渡高效低時(shí)延路由算法(ERMF),通過采用不同類型節(jié)點(diǎn)之間區(qū)外消息的直接交互策略,可以促進(jìn)區(qū)域間數(shù)據(jù)的快速傳輸,達(dá)到減少控制開銷和平均時(shí)延的目的。

1 機(jī)會(huì)網(wǎng)絡(luò)模型

由于村莊之間的地理位置具有隨機(jī)性,因而會(huì)存在空白區(qū)域和村莊相鄰的情況。如圖1所示的網(wǎng)絡(luò)劃分為3個(gè)區(qū)域,每個(gè)區(qū)域代表一個(gè)村莊,區(qū)域內(nèi)包含一個(gè)本地?cái)[渡節(jié)點(diǎn)(local ferry,LF)和靜態(tài)網(wǎng)關(guān)節(jié)點(diǎn)(Gateway)以及若干個(gè)普通節(jié)點(diǎn)。LF的運(yùn)動(dòng)軌跡需要覆蓋區(qū)域內(nèi)的所有路點(diǎn),并通過最短路徑算法計(jì)算旅行商問題(Travelling Salesman Problem,TSP)獲得全局?jǐn)[渡節(jié)點(diǎn)GF(Global Ferry)沿著固定的路徑移動(dòng),它的移動(dòng)路徑覆蓋所有的網(wǎng)關(guān)節(jié)點(diǎn)。因此,LF負(fù)責(zé)與本區(qū)域內(nèi)普通節(jié)點(diǎn)和Gateway節(jié)點(diǎn)交互數(shù)據(jù),而GF主要負(fù)責(zé)與Gateway節(jié)點(diǎn)區(qū)域間的數(shù)據(jù)傳輸。

圖1 機(jī)會(huì)網(wǎng)絡(luò)模型

2 ERMF算法

ERMF算法包含2種新機(jī)制:普通節(jié)點(diǎn)向網(wǎng)關(guān)節(jié)點(diǎn)直傳數(shù)據(jù)和跨區(qū)域擺渡節(jié)點(diǎn)間的數(shù)據(jù)傳輸。

定義1 區(qū)內(nèi)消息:指源節(jié)點(diǎn)地址和目的節(jié)點(diǎn)地址屬于同一區(qū)域的消息。

定義2 區(qū)外消息:指源和目的節(jié)點(diǎn)地址屬于不同區(qū)域的消息。

2.1 ERMF算法新機(jī)制

2.1.1 普通節(jié)點(diǎn)向網(wǎng)關(guān)節(jié)點(diǎn)直傳數(shù)據(jù) 圖2為普通節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)直接通信示意圖。圖中G節(jié)點(diǎn)、F節(jié)點(diǎn)和D節(jié)點(diǎn)分別代表網(wǎng)關(guān)節(jié)點(diǎn)、本地?cái)[渡節(jié)點(diǎn)LF和全局?jǐn)[渡節(jié)點(diǎn)GF,而S節(jié)點(diǎn)、Q節(jié)點(diǎn)和H節(jié)點(diǎn)都代表普通節(jié)點(diǎn)。該機(jī)制主要運(yùn)用在以下2種情況:①Gateway節(jié)點(diǎn)和LF節(jié)點(diǎn)通信時(shí)所覆蓋的公共鄰居節(jié)點(diǎn);②Gateway節(jié)點(diǎn)通信范圍內(nèi)覆蓋的所有普通節(jié)點(diǎn)。

圖2 普通節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)直接通信示意圖

普通節(jié)點(diǎn)向網(wǎng)關(guān)節(jié)點(diǎn)直傳數(shù)據(jù)的設(shè)計(jì)思想是:當(dāng)Gateway節(jié)點(diǎn)的鄰居節(jié)點(diǎn)監(jiān)聽到擺渡節(jié)點(diǎn)和Gateway節(jié)點(diǎn)之間在通信時(shí),通過跨層信息共享的方式[11],通告網(wǎng)絡(luò)層并創(chuàng)建節(jié)點(diǎn)區(qū)外屬性表,待這些區(qū)域的普通節(jié)點(diǎn)有區(qū)外消息要發(fā)送時(shí),不用經(jīng)過本地?cái)[渡節(jié)點(diǎn),而是直接轉(zhuǎn)發(fā)給Gateway節(jié)點(diǎn)。

普通節(jié)點(diǎn)向網(wǎng)關(guān)節(jié)點(diǎn)直傳數(shù)據(jù)機(jī)制的具體操作分為以下3個(gè)步驟。

步驟1 擺渡節(jié)點(diǎn)按照預(yù)定軌道周期性廣播HELLO消息,當(dāng)Gateway節(jié)點(diǎn)收到該消息后回復(fù)ECHO消息,雙方進(jìn)入數(shù)據(jù)傳輸階段。

步驟2 若Gateway節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的MAC層監(jiān)聽到LF節(jié)點(diǎn)向Gateway節(jié)點(diǎn)發(fā)送的數(shù)據(jù)幀(或者Gateway節(jié)點(diǎn)向GF節(jié)點(diǎn)發(fā)送的數(shù)據(jù)幀)時(shí),則將該數(shù)據(jù)幀解封裝后產(chǎn)生的數(shù)據(jù)分組提到網(wǎng)絡(luò)層,并立即通過跨層信息共享的方式通告網(wǎng)絡(luò)層,在該層做出判斷處理后,創(chuàng)建節(jié)點(diǎn)區(qū)外屬性表,然后將提取到的分組IP頭部的目的地址寫入到該表內(nèi),并刪除此消息的數(shù)據(jù)部分。

步驟3 收到如同步驟2的數(shù)據(jù)幀僅需把該幀包含的數(shù)據(jù)分組所攜帶的目的地址填入到此表內(nèi),經(jīng)過一段時(shí)間后,該區(qū)域節(jié)點(diǎn)的區(qū)外屬性表的記錄都趨于完整,此時(shí)若再有消息發(fā)送,首先去查詢該表,查看該消息的目的節(jié)點(diǎn)的區(qū)域?qū)傩允欠裨诒碇杏杏涗洝Ｈ粲?則直接轉(zhuǎn)發(fā)給Gateway節(jié)點(diǎn),否則等待轉(zhuǎn)發(fā)給LF節(jié)點(diǎn)。

2.1.2 跨區(qū)域擺渡節(jié)點(diǎn)間的數(shù)據(jù)傳輸 圖3為相鄰區(qū)擺渡節(jié)點(diǎn)間通信示意圖。圖中F節(jié)點(diǎn)代表全局?jǐn)[渡節(jié)點(diǎn)GF,而S節(jié)點(diǎn)、D節(jié)點(diǎn)、Q節(jié)點(diǎn)分別代表不同區(qū)域擺渡節(jié)點(diǎn)LF,新機(jī)制主要思想是若相鄰區(qū)擺渡節(jié)點(diǎn)相遇時(shí),會(huì)彼此交換自己區(qū)域內(nèi)節(jié)點(diǎn)的有效數(shù)據(jù)。如果是本地?cái)[渡節(jié)點(diǎn)之間通信,只交換屬于對方區(qū)域內(nèi)的區(qū)外消息;如果是本地?cái)[渡節(jié)點(diǎn)和全局?jǐn)[渡節(jié)點(diǎn)之間通信,則本地?cái)[渡節(jié)點(diǎn)會(huì)把全部區(qū)外消息交給全局?jǐn)[渡節(jié)點(diǎn)。

圖3 相鄰區(qū)擺渡節(jié)點(diǎn)間通信示意圖

跨區(qū)域擺渡節(jié)點(diǎn)間數(shù)據(jù)傳輸機(jī)制的具體操作步驟如下。

步驟1 一個(gè)給定區(qū)域的擺渡節(jié)點(diǎn)沿著默認(rèn)的路徑運(yùn)動(dòng),并使用短距離通信方式周期性廣播HELLO消息。

步驟2 若該擺渡節(jié)點(diǎn)在移動(dòng)過程中偵測到有相鄰區(qū)擺渡節(jié)點(diǎn)發(fā)送的HELLO消息時(shí),會(huì)回復(fù)ECHO消息。

步驟3 雙方確認(rèn)互為鄰居節(jié)點(diǎn)后,則進(jìn)入交互數(shù)據(jù)階段,此時(shí)若LF節(jié)點(diǎn)的MAC層收到標(biāo)識的源MAC地址、目的MAC地址分別為GF節(jié)點(diǎn)、LF節(jié)點(diǎn)的控制幀,則雙方會(huì)把自己緩存區(qū)內(nèi)的區(qū)外消息全部交給對方;若LF節(jié)點(diǎn)的MAC層收到標(biāo)識的源MAC地址和目的MAC地址都為LF節(jié)點(diǎn)的控制幀,則LF節(jié)點(diǎn)彼此只交換屬于對方區(qū)域內(nèi)的區(qū)外消息。

步驟4 待彼此交互完數(shù)據(jù)后,擺渡節(jié)點(diǎn)繼續(xù)按照自己的路線運(yùn)動(dòng),等待和相應(yīng)的網(wǎng)關(guān)節(jié)點(diǎn)通信。

2.2 ERMF路由算法操作

由ERMF網(wǎng)絡(luò)模型可知,網(wǎng)絡(luò)中擁有4種類型節(jié)點(diǎn):普通節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)Gateway、本地?cái)[渡節(jié)點(diǎn)LF、全局?jǐn)[渡節(jié)點(diǎn)GF。

(1)普通節(jié)點(diǎn)操作。如果Gateway節(jié)點(diǎn)通信范圍內(nèi)的普通節(jié)點(diǎn)有區(qū)外消息要發(fā)送時(shí),則將消息直接轉(zhuǎn)發(fā)給Gateway節(jié)點(diǎn),然后刪除該消息以避免造成消息冗余;否則,等待轉(zhuǎn)發(fā)給LF節(jié)點(diǎn)。

(2)LF操作。LF和其他節(jié)點(diǎn)交互階段,即作為動(dòng)態(tài)轉(zhuǎn)發(fā)節(jié)點(diǎn)有以下3個(gè)步驟:①LF維護(hù)一個(gè)包含本簇內(nèi)所有普通節(jié)點(diǎn)的位置信息以及消息丟棄率的鏈表,這個(gè)鏈表可以通過GPS獲得,并且在計(jì)算LF的移動(dòng)軌跡前要更新這些信息;②如果LF緩存內(nèi)的消息的目的節(jié)點(diǎn)屬于本區(qū)域內(nèi)部,則LF遇到相應(yīng)的目的節(jié)點(diǎn)就轉(zhuǎn)發(fā)此消息,并從緩存中刪除消息副本;③如果LF緩存內(nèi)的消息需要轉(zhuǎn)發(fā)到區(qū)域外的節(jié)點(diǎn),則LF遇到相鄰區(qū)擺渡節(jié)點(diǎn),此時(shí)就將相應(yīng)的區(qū)外消息轉(zhuǎn)發(fā)給它,否則轉(zhuǎn)發(fā)給本區(qū)域的Gateway節(jié)點(diǎn)。

(3)GF操作。GF和其他轉(zhuǎn)發(fā)節(jié)點(diǎn)的交互過程有以下3個(gè)步驟:①GF沿著覆蓋所有Gateway的最短路徑巡回移動(dòng);②如果GF遇到與自己緩存中消息相符的目的節(jié)點(diǎn),那么將此消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn),并在緩存中刪除消息副本;③如果GF遇到LF則將消息轉(zhuǎn)發(fā)給它,否則送往目的節(jié)點(diǎn)所在區(qū)域的Gateway。

(4)Gateway操作。Gateway作為靜態(tài)轉(zhuǎn)發(fā)節(jié)點(diǎn)與其他節(jié)點(diǎn)交互操作的具體步驟如下:①如果消息的目的節(jié)點(diǎn)在Gateway范圍內(nèi),直接將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn),并在緩存中刪除消息;②如果LF進(jìn)入Gateway的通信范圍,則Gateway將從LF節(jié)點(diǎn)接收發(fā)往本區(qū)域外節(jié)點(diǎn)的信息,并等待GF的到來,將消息轉(zhuǎn)發(fā)給GF,在緩存中刪除對應(yīng)的消息副本;③如果GF進(jìn)入Gateway的通信范圍,Gateway從GF接收來自其他區(qū)域轉(zhuǎn)發(fā)給本地區(qū)域的消息,當(dāng)LF到來時(shí),將消息轉(zhuǎn)發(fā)給LF,進(jìn)一步轉(zhuǎn)發(fā)給位于本區(qū)域中的目的節(jié)點(diǎn)。

2.3 ERMF算法分析

為確定ERMF算法的正確性和有效性,本文進(jìn)行了詳細(xì)的理論分析如下。

引理1 ERMF算法的轉(zhuǎn)發(fā)開銷低于MMFGW算法。

證明 假設(shè)網(wǎng)絡(luò)中有M個(gè)LF區(qū)域,每個(gè)LF區(qū)域分A和B2個(gè)分區(qū),A代表普通節(jié)點(diǎn)無監(jiān)聽區(qū),B代表普通節(jié)點(diǎn)監(jiān)聽區(qū)。每個(gè)分區(qū)內(nèi)普通節(jié)點(diǎn)又分為2類消息:區(qū)內(nèi)消息和區(qū)外消息。令A(yù)in、Aout分別代表A分區(qū)普通節(jié)點(diǎn)發(fā)送的區(qū)內(nèi)消息和區(qū)外消息個(gè)數(shù),Bin、Bout代表B分區(qū)普通節(jié)點(diǎn)發(fā)送的區(qū)內(nèi)消息和區(qū)外消息個(gè)數(shù)。

假定成功率為1,轉(zhuǎn)發(fā)開銷單位為個(gè),且每個(gè)包大小都相同,則第i(1≤i≤M)個(gè)LF區(qū)域內(nèi)消息從源節(jié)點(diǎn)成功到達(dá)目的節(jié)點(diǎn)所產(chǎn)生的轉(zhuǎn)發(fā)開銷為

Ci=CAin+CAout+CBin+CBout

(1)

式中：CAin、CAout分別代表A分區(qū)普通節(jié)點(diǎn)發(fā)送的區(qū)內(nèi)消息和區(qū)外消息產(chǎn)生的轉(zhuǎn)發(fā)開銷;CBin、CBout分別表示B分區(qū)普通節(jié)點(diǎn)發(fā)送的區(qū)內(nèi)消息和區(qū)外消息產(chǎn)生的轉(zhuǎn)發(fā)開銷。

相比于MMFGW算法，在ERMF算法中B分區(qū)普通節(jié)點(diǎn)發(fā)送的區(qū)外消息不再經(jīng)過LF節(jié)點(diǎn)的轉(zhuǎn)發(fā)，而是向Gateway節(jié)點(diǎn)直傳,因此在該分區(qū)內(nèi)每一個(gè)區(qū)外消息到達(dá)目的節(jié)點(diǎn)時(shí)都會(huì)減少一次轉(zhuǎn)發(fā)。

所以，ERMF算法B分區(qū)內(nèi)的區(qū)外消息所產(chǎn)生的轉(zhuǎn)發(fā)開銷均小于MMFGW算法，即

(2)

又因?yàn)镋RMF算法A分區(qū)的區(qū)內(nèi)消息和區(qū)外消息以及B分區(qū)的區(qū)內(nèi)消息均未受新機(jī)制影響，因此在ERMF算法中CAin、CAout、CBin均等于MMFGW算法的轉(zhuǎn)發(fā)開銷。

根據(jù)式(1)得，ERMF算法區(qū)域i內(nèi)的轉(zhuǎn)發(fā)開銷小于MMFGW算法，即

(3)

因此可得出，在整個(gè)網(wǎng)絡(luò)區(qū)域內(nèi)，ERMF算法轉(zhuǎn)發(fā)開銷小于MMFGW算法，即

(4)

CERMF

(5)

證畢。

引理2 ERMF算法的平均傳輸時(shí)延低于MMFGW算法。

證明 由消息擺渡機(jī)制的時(shí)延公式得

(6)

式中:Tii表示區(qū)域i內(nèi)不同節(jié)點(diǎn)間產(chǎn)生的業(yè)務(wù)量;Tij代表區(qū)域i內(nèi)的節(jié)點(diǎn)到區(qū)域j內(nèi)的節(jié)點(diǎn)之間的業(yè)務(wù)量;di表示消息在區(qū)域i內(nèi)節(jié)點(diǎn)間傳送所產(chǎn)生的時(shí)延;dij表示消息從區(qū)域i內(nèi)節(jié)點(diǎn)傳送到區(qū)域j內(nèi)節(jié)點(diǎn)所產(chǎn)生的時(shí)延。

由于任意區(qū)域i可分為A和B2個(gè)分區(qū)(A代表普通節(jié)點(diǎn)無監(jiān)聽區(qū)，B代表普通節(jié)點(diǎn)監(jiān)聽區(qū)),則消息從區(qū)域i傳送到區(qū)域j產(chǎn)生的時(shí)延為

dij=(diAj+diBj)/2

(7)

式中：diAj、diBj分別代表消息從區(qū)域i內(nèi)A分區(qū)節(jié)點(diǎn)、B分區(qū)節(jié)點(diǎn)到區(qū)域j內(nèi)節(jié)點(diǎn)所產(chǎn)生的時(shí)延。

由于B區(qū)節(jié)點(diǎn)的消息在傳輸過程中省略了LF節(jié)點(diǎn)的轉(zhuǎn)發(fā)，縮短了到Gateway節(jié)點(diǎn)的時(shí)延，因此

(8)

因?yàn)镋RMF算法A分區(qū)的時(shí)延未受新機(jī)制影響，因此根據(jù)式(7)可得，ERMF算法區(qū)域i到區(qū)域j的時(shí)延小于MMFGW算法，即

(9)

在同等條件下，區(qū)域i內(nèi)節(jié)點(diǎn)到區(qū)域j內(nèi)節(jié)點(diǎn)的業(yè)務(wù)量Tij相同，則不同區(qū)域間總業(yè)務(wù)量的平均傳輸時(shí)延的關(guān)系為

(10)

類似地，因?yàn)?種算法中同一區(qū)域內(nèi)總業(yè)務(wù)量產(chǎn)生的平均時(shí)延相等，即

(11)

所以

dERMF

(12)

證畢。

2.4 計(jì)算復(fù)雜度

假設(shè)N個(gè)靜止的普通節(jié)點(diǎn)均勻分布在面積為S的正方形網(wǎng)絡(luò)中。整個(gè)網(wǎng)絡(luò)被均分為M個(gè)小區(qū)域,且每個(gè)小區(qū)域均勻分布著N/M個(gè)普通節(jié)點(diǎn),1個(gè)LF和Gateway節(jié)點(diǎn)部署在中心位置,整個(gè)網(wǎng)絡(luò)僅分配1個(gè)GF,GF和LF沿著自己預(yù)定的軌跡都以恒定的相同速率V運(yùn)動(dòng),節(jié)點(diǎn)產(chǎn)生消息的速度為m,網(wǎng)絡(luò)運(yùn)行時(shí)間為T。以下從時(shí)間、存儲(chǔ)和通信3個(gè)方面來分析ERMF算法的復(fù)雜度。

(13)

GF節(jié)點(diǎn)的最短巡回路徑長度為

(14)

一個(gè)數(shù)據(jù)分組在最極端的情況下需要經(jīng)過LF、GF、Gateway節(jié)點(diǎn)轉(zhuǎn)發(fā)才能到達(dá)目的節(jié)點(diǎn),因此節(jié)點(diǎn)在最極端情況下需運(yùn)動(dòng)的距離D為

D≈2(LGF+LLF)=

(15)

消耗的時(shí)間為

t=D/V

(16)

從而得其時(shí)間復(fù)雜度Ft為

(17)

2.4.2 存儲(chǔ)復(fù)雜度 由于消息與m、T、N等正相關(guān),在極端情況下,節(jié)點(diǎn)在運(yùn)行t時(shí)間后,消息始終未尋到目的節(jié)點(diǎn),則存儲(chǔ)復(fù)雜度為

Fs=O(mTN)

(18)

2.4.3 通信復(fù)雜度 由于一個(gè)數(shù)據(jù)消息在最極端的情況下需要經(jīng)過N-1次轉(zhuǎn)發(fā)才能到達(dá)目的節(jié)點(diǎn),因此通信復(fù)雜度為

Ft=O(N)

(19)

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

本文通過改變網(wǎng)絡(luò)的普通節(jié)點(diǎn)個(gè)數(shù)N、LF個(gè)數(shù)M,采用了平均傳輸時(shí)延、轉(zhuǎn)發(fā)開銷和消息傳輸成功率3個(gè)性能評價(jià)指標(biāo)。對3種多Ferry路由算法NRA、MMFGW和ERMF的性能進(jìn)行了比較分析。

3.1 仿真設(shè)置

仿真實(shí)驗(yàn)平臺為ONE(opportunistic networking environment simulator)[12]。普通節(jié)點(diǎn)處于靜止?fàn)顟B(tài),在不同的網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)均勻分布。用3個(gè)不同的節(jié)點(diǎn)網(wǎng)絡(luò)層進(jìn)程模型分別實(shí)現(xiàn)NRA、MMFGW和ERMF算法。主要仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)配置

3.2 仿真結(jié)果分析

在每個(gè)仿真場景下分別運(yùn)行NRA、MMFGW和ERMF算法,并統(tǒng)計(jì)這3種算法在不同場景下的轉(zhuǎn)發(fā)開銷、平均時(shí)延和消息成功率。針對普通節(jié)點(diǎn)數(shù)和LF個(gè)數(shù)2種情況,每組實(shí)驗(yàn)分別進(jìn)行7次和5次,實(shí)驗(yàn)結(jié)果求平均值,所得實(shí)驗(yàn)結(jié)果如圖4～圖6所示。

(a)普通節(jié)點(diǎn)數(shù)對轉(zhuǎn)發(fā)開銷的影響

(b)LF個(gè)數(shù)對轉(zhuǎn)發(fā)開銷的影響圖4 3種算法的轉(zhuǎn)發(fā)開銷比較

圖4a、4b分別顯示了普通節(jié)點(diǎn)個(gè)數(shù)N和LF個(gè)數(shù)M對網(wǎng)絡(luò)的轉(zhuǎn)發(fā)開銷的影響。由圖4可以看出,ERMF算法在轉(zhuǎn)發(fā)開銷上至少下降了8.1%,其原因主要在于:①當(dāng)Gateway節(jié)點(diǎn)的鄰居節(jié)點(diǎn)有消息要發(fā)往區(qū)外節(jié)點(diǎn)時(shí),這些消息不用經(jīng)過本地?cái)[渡節(jié)點(diǎn)的轉(zhuǎn)發(fā),而是直接轉(zhuǎn)發(fā)給Gateway節(jié)點(diǎn),而MMFGW算法則規(guī)定要先發(fā)給本地?cái)[渡節(jié)點(diǎn),這樣,ERMF算法就減少了一次轉(zhuǎn)發(fā)操作;②當(dāng)相鄰區(qū)域的擺渡節(jié)點(diǎn)相遇時(shí),它們可以直接傳送數(shù)據(jù),不必經(jīng)過Gateway節(jié)點(diǎn)中轉(zhuǎn)。這樣,隨著轉(zhuǎn)發(fā)次數(shù)的減少,轉(zhuǎn)發(fā)開銷也相應(yīng)降低。

(a)普通節(jié)點(diǎn)數(shù)對時(shí)延的影響

(b)LF個(gè)數(shù)對時(shí)延的影響圖5 3種算法的時(shí)延比較

圖5a、5b分別顯示了普通節(jié)點(diǎn)個(gè)數(shù)N和LF個(gè)數(shù)M對網(wǎng)絡(luò)的平均傳輸時(shí)延的影響。由圖5可以看出,ERMF算法在平均時(shí)延上至少減少了7.3%。ERMF算法降低時(shí)延的主要原因是:①M(fèi)一定,N增加,使更多的節(jié)點(diǎn)落到Gateway節(jié)點(diǎn)覆蓋的區(qū)域,Gateway節(jié)點(diǎn)的鄰居節(jié)點(diǎn)有區(qū)外消息發(fā)送時(shí),直接轉(zhuǎn)給Gateway節(jié)點(diǎn),大大省略了等待LF的時(shí)間;②N一定,M增加時(shí),提高了擺渡節(jié)點(diǎn)之間相遇的概率,使得兩擺渡節(jié)點(diǎn)相遇交互區(qū)外消息時(shí)能更快到達(dá)本區(qū)域,明顯縮短了該消息到達(dá)目的區(qū)域的時(shí)間。

圖6a、6b分別顯示了不同網(wǎng)絡(luò)場景下普通節(jié)點(diǎn)個(gè)數(shù)和LF個(gè)數(shù)對成功率的影響?？梢钥闯?ERMF算法與MMFGW算法相比較,成功率基本上持平。其主要原因是:滿足條件的節(jié)點(diǎn)轉(zhuǎn)發(fā)區(qū)外消息時(shí),本文算法雖大大縮短了緩存時(shí)間,使更多消息在其生存周期內(nèi)完成了交換,提高了成功率,但由于擺渡節(jié)點(diǎn)間交互時(shí)相對移動(dòng),可能會(huì)丟失一部分?jǐn)?shù)據(jù),因此綜合分析驗(yàn)證,2種算法在成功率上相差不大。

(a)普通節(jié)點(diǎn)數(shù)對消息傳輸成功率的影響

(b)LF個(gè)數(shù)對消息傳輸成功率的影響圖6 3種算法的消息傳輸成功率比較

4 結(jié) 論

本文針對網(wǎng)關(guān)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)存在區(qū)外消息冗余等待、轉(zhuǎn)發(fā)次數(shù)偏多和跨區(qū)域擺渡節(jié)點(diǎn)無協(xié)作的問題,提出了一種新的多擺渡高效低時(shí)延路由算法——ERMF,新算法分別設(shè)計(jì)了普通節(jié)點(diǎn)向網(wǎng)關(guān)節(jié)點(diǎn)直傳數(shù)據(jù)和跨區(qū)域擺渡節(jié)點(diǎn)間的數(shù)據(jù)傳輸2種機(jī)制,實(shí)現(xiàn)了普通節(jié)點(diǎn)可根據(jù)消息的目的地動(dòng)態(tài)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)和擺渡節(jié)點(diǎn)間的直接通信,從而減少了數(shù)據(jù)的中間轉(zhuǎn)發(fā),節(jié)省了時(shí)間。仿真結(jié)果表明,與MMFGW和NRA算法相比,本文提出的ERMF算法至少降低了8.1%的轉(zhuǎn)發(fā)開銷和7.3%的平均時(shí)延。

[1]熊永平, 孫利民, 牛建偉, 等.機(jī)會(huì)網(wǎng)絡(luò) [J].軟件學(xué)報(bào), 2009, 20(1):124-137.XIONG Yongping, SUN Limin, NIU Jianwei, et al.Opportunistic networks [J].Journal of Software, 2009, 20(1):124-137.

[2]劉喬壽, 黃寬, 吳大鵬, 等.協(xié)作意愿感知的機(jī)會(huì)網(wǎng)絡(luò)路由算法 [J].重慶郵電大學(xué)學(xué)報(bào), 2012, 24(6):760-764.LIU Qiaoshou, HUANG Kuan, WU Dapeng, et al.Cooperative willingness perception based routing algorithm in opportunistic network [J].Journal of Chongqing University of Posts and Telecommunications, 2012, 24(6):760-764.

[3]WANG Yong, PENG Wei, DOU Qiang, et al.Energy-constrained ferry route design for sparse wireless sensor networks [J].Journal of Central South University, 2013, 20(11):3142-3149.

[4]ZHAO W, AMMAR M, ZEGURA E.A message ferrying approach for data delivery in sparse mobile ad hoc networks [C]∥Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc networking and Computing.New York, USA:ACM, 2004:187-198.

[5]HE T, SAMI A, LEE K W.Dispatch-and-search:dynamic multi-ferry control in partitioned mobile networks [C]∥Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York, USA:ACM, 2011:17-26.

[6]SUGANTHE R C, BALASUBRAMANIE P.Improving QoS in disconnected mobile ad hoc network [J].Journal of Mobile Communication, 2008, 2(4):105-111.

[7]ZHAO W, AMMAR M, ZEGURA E.Controlling the mobility of multiple data transport ferries in a delay-tolerant network [C]∥Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ, USA:IEEE, 2005:1407-1418.

[8]ZHANG Y, WANG L.Route design for multiple ferries and improvement in delay tolerant network [J].Computer Engineering and Design, 2009, 30(24):5605-5608.

[9]LAI Y L, JIANG J R.A genetic algorithm for data mule path planning in wireless sensor networks [J].Applied Mathematics & Information Sciences, 2013, 7(1):413-419.

[10]SUGANTHE R C, BALASUBRAMANIE P.Improving QoS in delay tolerant mobile ad hoc network using multiple message ferries [J].Network Protocols and Algorithms, 2011, 3(4):32-53.

[11]任智, 索建偉, 陳紅, 等.基于相遇節(jié)點(diǎn)跨層感知的機(jī)會(huì)網(wǎng)絡(luò)高效低時(shí)延路由算法 [J].通信學(xué)報(bào), 2013, 34(10):1-8.REN Zhi, SUO Jianwei, CHEN Hong, et al.Efficient low-delay routing algorithm for opportunistic networks based on cross-layer sensing of encountered nodes [J].Journal on Communications, 2013, 34(10):1-8.

[本刊相關(guān)文獻(xiàn)鏈接]

李季碧,李賓,任智,等.自適應(yīng)動(dòng)態(tài)功率控制的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能高效路由算法.2014,48(12):49-56.[doi:10.7652/xjtuxb 201412008]

崔華力,錢德沛,張興軍,等.用于無線多跳網(wǎng)絡(luò)視頻流傳輸?shù)膬?yōu)先級機(jī)會(huì)網(wǎng)絡(luò)編碼.2013,47(12):13-18.[doi:10.7652/xjtuxb201312003]

李劉強(qiáng),桂小林,安健,等.采用模糊層次聚類的社會(huì)網(wǎng)絡(luò)重疊社區(qū)檢測算法.2015,49(2):6-13.[doi:10.7652/xjtuxb 201502002]

楊建偉,桂小林,安健,等.一種信任關(guān)系網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)檢測算法.2014,48(12):80-86.[doi:10.7652/xjtuxb2014 12013]

陳皓勇,文俊中,王增煜,等.能量網(wǎng)絡(luò)的傳遞規(guī)律與網(wǎng)絡(luò)方程.2014,48(10):66-76.[doi:10.7652/xjtuxb201410011]

李建東,鄭杰,劉勤,等.異構(gòu)協(xié)作網(wǎng)絡(luò)中采用令牌漏桶的多接入業(yè)務(wù)分配算法.2014,48(8):7-11.[doi:10.7652/xjtuxb 201408002]

劉勝,荊奇.時(shí)滯TCP網(wǎng)絡(luò)滑模預(yù)測主動(dòng)隊(duì)列管理算法.2014,48(8):42-46.[doi:10.7652/xjtuxb201408008]

鄭鵬飛,尤佳莉,王勁林,等.一種多租戶云的內(nèi)部網(wǎng)絡(luò)共享策略.2014,48(8):54-59.[doi:10.7652/xjtuxb201408010]

董哲,伊鵬.采用鏈路聚類的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法.2014,48(8):73-79.[doi:10.7652/xjtuxb201408013]

魏全瑞,劉俊,韓九強(qiáng).改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計(jì)與節(jié)點(diǎn)定位算法.2014,48(6):1-6.[doi:10.7652/xjtuxb 201406001]

(編輯 劉楊)

An Efficient and Low-Delay Routing Algorithm for Multiple Ferries in Opportunistic Networks

LI Jibi,DENG Ke,REN Zhi,HUANG Yanjiang,CHEN Qianbin,LIU Dongyuan

(Key Laboratory of Mobile Communications Technology of Chongqing, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

An efficient and low-delay routing algorithm based on multiple ferries (ERMF) is proposed to address the problems that appear when the multiple message ferries gateway-based algorithm (MMFGW) is applied to opportunistic networks, such as some outside information redundancy is waiting for transfer, the number of data forwarding is a little large, and there is no collaboration among neighboring regions.When the neighbor nodes of a gateway node have data to send, the ERMF algorithm makes a decision through querying an attribute table of outside regions, which is established based on a cross-layer overhearing mechanism.If there exists a match in the table, the data is directly transferred to the gateway instead of forwarding through a local ferry node.When the ferries between the two regions are encountered, each ferry obtains valid data in its own region through exchanging information of nodes in their own regions.These two coordination mechanisms of direct communication optimize the single data interaction mode, realize fast data transmission between two regions, and reduce the delay and cost of data forwarding without affecting the function of original data transmission.Simulation results and comparisons with the MMFGW and the node relaying algorithm show that the proposed ERMF reduces the forward overhead and the average end-to-end delay of packets by about 8.1% and 7.3%, respectively.

opportunistic network; routing algorithm; message ferry; forward overhead; end-to-end delay

2014-07-15。 作者簡介:李季碧(1975—),女,講師。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(60972068);教育部長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助項(xiàng)目(IRT1299);重慶市自然科學(xué)基金資助項(xiàng)目(cstc2012jjA40051);重慶市科委重點(diǎn)實(shí)驗(yàn)室專項(xiàng)經(jīng)費(fèi)資助項(xiàng)目(D2011-24);重慶市教委科研基金資助項(xiàng)目(KJ120510)。

時(shí)間:2015-03-03

http:∥www.cnki.net/kcms/detail/61.1069.T.20150303.1003.001.html

10.7652/xjtuxb201504015

TP393.04

A

0253-987X(2015)04-0091-07