機(jī)會(huì)網(wǎng)絡(luò)中基于擺渡節(jié)點(diǎn)與簇節(jié)點(diǎn)相互協(xié)作的路由機(jī)制

劉春蕊,張書奎,2,賈俊鋮,林政寬

(1.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇蘇州 215006;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室 江蘇南京 210003)

?

機(jī)會(huì)網(wǎng)絡(luò)中基于擺渡節(jié)點(diǎn)與簇節(jié)點(diǎn)相互協(xié)作的路由機(jī)制

劉春蕊1,張書奎1,2,賈俊鋮1,林政寬1

(1.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇蘇州 215006;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室 江蘇南京 210003)

機(jī)會(huì)網(wǎng)絡(luò)是一種不需要在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑,利用節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì)實(shí)現(xiàn)網(wǎng)絡(luò)通信的延遲容忍自組織網(wǎng)絡(luò),它以“存儲(chǔ)—攜帶—處理—轉(zhuǎn)發(fā)”的模式進(jìn)行.為實(shí)現(xiàn)互不相交簇間的信息傳輸,本文設(shè)計(jì)了一種帶閾值的簇移動(dòng)模型CMMT,并提出了一種基于擺渡(Ferry)節(jié)點(diǎn)與簇節(jié)點(diǎn)協(xié)作的路由算法(CBSW).該算法減少了冗余的通信和存儲(chǔ)開銷,以及在Spray 階段簇節(jié)點(diǎn)沒有遇到目的節(jié)點(diǎn)或擺渡節(jié)點(diǎn),進(jìn)入Wait階段攜帶消息的節(jié)點(diǎn)采用直接分發(fā)方式只向目的節(jié)點(diǎn)傳輸?shù)葐栴}.仿真實(shí)驗(yàn)表明,CBSW算法能夠增加傳輸成功率,減少網(wǎng)絡(luò)開銷和傳輸延遲.

機(jī)會(huì)網(wǎng)絡(luò);移動(dòng)模型;協(xié)作;路由算法

1 引言

機(jī)會(huì)網(wǎng)絡(luò)源于延遲容忍網(wǎng)絡(luò)(DTN)和移動(dòng)自組網(wǎng)絡(luò)(MANET),可視為兩者的子類[1],它是一種在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間不存在連通路徑的情況下,利用節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì)實(shí)現(xiàn)網(wǎng)絡(luò)通信的延遲容忍自組織網(wǎng)絡(luò)[2].由于環(huán)境干擾、應(yīng)用特點(diǎn)等影響,在許多情況下無法建立全連通網(wǎng)絡(luò),而機(jī)會(huì)網(wǎng)絡(luò)可滿足這些應(yīng)用需求,廣泛應(yīng)用于野生動(dòng)物監(jiān)測(cè)、手持設(shè)備組網(wǎng)、智能交通等領(lǐng)域.典型應(yīng)用:ZebraNet[3]是一個(gè)追蹤肯尼亞草原斑馬活動(dòng)的機(jī)會(huì)網(wǎng)絡(luò)系統(tǒng),SWIM[4]是一個(gè)監(jiān)視鯨魚活動(dòng)的水下機(jī)會(huì)網(wǎng)絡(luò)系統(tǒng),基于車輛傳感器的網(wǎng)絡(luò)系統(tǒng)CarTel[5],能夠用于監(jiān)測(cè)環(huán)境、診斷車輛狀態(tài)和交通路線導(dǎo)航等,DakNet[6]為偏遠(yuǎn)鄉(xiāng)村提供成本較低的數(shù)字通信服務(wù).此外,文獻(xiàn)[7,8]設(shè)計(jì)了一種社交機(jī)會(huì)網(wǎng)絡(luò)系統(tǒng).

目前,國內(nèi)外研究人員提出的機(jī)會(huì)網(wǎng)絡(luò)路由機(jī)制,主要有:Direct Delivery、CAR等[9]基于轉(zhuǎn)發(fā)策略的路由算法和Epidemic[10]、Spray and Wait[11]、PRoPHET[12]等基于復(fù)制策略的路由算法.多副本機(jī)制雖然時(shí)延較低、可靠性較高,但其占用了大量的網(wǎng)絡(luò)帶寬和緩存空間,不適合于資源受限的機(jī)會(huì)網(wǎng)絡(luò).在節(jié)點(diǎn)能量和帶寬受限的情況下,單副本路由機(jī)制在網(wǎng)絡(luò)資源開銷方面有較強(qiáng)的優(yōu)勢(shì)[13].

在許多應(yīng)用中,有些節(jié)點(diǎn)的地位高于其它節(jié)點(diǎn),這些節(jié)點(diǎn)具有較強(qiáng)的存儲(chǔ)能力和無線通訊能力,稱之為擺渡(Ferry)節(jié)點(diǎn).自從基于消息擺渡的路由算法被提出以后,人們對(duì)其加以改進(jìn)和拓展的研究一直在進(jìn)行,在Ferry節(jié)點(diǎn)主動(dòng)運(yùn)動(dòng)路徑的設(shè)計(jì)和優(yōu)化等方面已經(jīng)取得了一些進(jìn)展,但在消息傳輸方面存在冗余的通信和存儲(chǔ)開銷,這些問題對(duì)機(jī)會(huì)網(wǎng)絡(luò)的性能產(chǎn)生重要影響.在節(jié)點(diǎn)移動(dòng)過程中,由于密度分布不均等形成互不相交的“簇”,為實(shí)現(xiàn)不同簇間的信息快速傳輸,本文設(shè)計(jì)了一種帶閾值的簇移動(dòng)模型CMMT,并在此基礎(chǔ)上提出了一種協(xié)作路由算法CBSW.本文的主要貢獻(xiàn)如下:

①設(shè)計(jì)了移動(dòng)模型CMMT,該模型增加了Ferry節(jié)點(diǎn)與簇節(jié)點(diǎn)的相遇機(jī)會(huì).

②通過簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)的協(xié)作,設(shè)計(jì)了路由算法CBSW.該算法減少了冗余的通信和存儲(chǔ)開銷、解決了在Wait階段采用Direct Delivery方式只向目的節(jié)點(diǎn)傳輸?shù)葐栴},提高了傳輸成功率,減少了路由開銷.

2 相關(guān)工作

2.1 機(jī)會(huì)轉(zhuǎn)發(fā)

路由和轉(zhuǎn)發(fā)是組網(wǎng)技術(shù)的兩個(gè)首要問題.現(xiàn)有的Ad-Hoc網(wǎng)絡(luò)路由協(xié)議都是假設(shè)源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間至少存在一條連通路徑,不適合于機(jī)會(huì)網(wǎng)絡(luò).機(jī)會(huì)網(wǎng)絡(luò)以“存儲(chǔ)—攜帶—處理—轉(zhuǎn)發(fā)”的模式工作,當(dāng)路由表中不存在下一跳節(jié)點(diǎn)時(shí),消息在當(dāng)前節(jié)點(diǎn)存儲(chǔ),并隨著該節(jié)點(diǎn)的移動(dòng)尋找合適的轉(zhuǎn)發(fā)時(shí)機(jī),因而每個(gè)消息選擇合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)和時(shí)機(jī)就成為設(shè)計(jì)高效機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議的關(guān)鍵.文獻(xiàn)[14]根據(jù)轉(zhuǎn)發(fā)策略的不同,將現(xiàn)有的轉(zhuǎn)發(fā)機(jī)制分為:基于冗余的轉(zhuǎn)發(fā)機(jī)制、冗余效用混合的轉(zhuǎn)發(fā)機(jī)制、主動(dòng)運(yùn)動(dòng)的轉(zhuǎn)發(fā)機(jī)制和基于效用的轉(zhuǎn)發(fā)機(jī)制,如圖1所示.

2.2 移動(dòng)過程

在機(jī)會(huì)網(wǎng)絡(luò)中,移動(dòng)模型研究的是以刻劃節(jié)點(diǎn)的相遇特征為核心.因?yàn)樵跈C(jī)會(huì)網(wǎng)絡(luò)中,數(shù)據(jù)傳輸依賴于節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì),而節(jié)點(diǎn)的相遇概率和相遇時(shí)間分布是由節(jié)點(diǎn)的移動(dòng)模型決定的.因此,與傳統(tǒng)的MANET相比,移動(dòng)模型的研究更加重要.

對(duì)于移動(dòng)模型的研究主要有兩種途徑,一種是對(duì)模型進(jìn)行理論或仿真分析,如Random Way Point[15](RWP)、Random Walk[16](RW)和Random Direction[17](RD)是3個(gè)經(jīng)典的移動(dòng)模型.另一種是基于運(yùn)動(dòng)軌跡集進(jìn)行統(tǒng)計(jì)分析,收集運(yùn)動(dòng)軌跡集也就成為移動(dòng)模型的研究基礎(chǔ)之一,如MIT的Reality Mining[18]記錄了MIT校園中100個(gè)智能手機(jī)移動(dòng)軌跡和相遇數(shù)據(jù),UCSD的Wireless Topology Discovery[19]收集了300個(gè)PDA與Wi-Fi接入點(diǎn)的相遇數(shù)據(jù),Cambridge的Haggle[20]記錄了若干iMote設(shè)備在校園內(nèi)的相遇情況,UMass的DieselNet[21]收集了公交車上無線節(jié)點(diǎn)組成的機(jī)會(huì)網(wǎng)絡(luò)實(shí)際運(yùn)行中的相遇規(guī)律.

本文設(shè)計(jì)的移動(dòng)模型根據(jù)節(jié)點(diǎn)類型不同而不同.簇節(jié)點(diǎn)采用CMMT移動(dòng)模型,它們?cè)诖胤秶鷥?nèi)按一定規(guī)則移動(dòng),Ferry節(jié)點(diǎn)采用基于地圖的移動(dòng)模型,它們沿著預(yù)先設(shè)定的路徑移動(dòng),為簇節(jié)點(diǎn)提供消息轉(zhuǎn)發(fā)服務(wù).

2.3 路由算法

在機(jī)會(huì)網(wǎng)絡(luò)的路由算法中,Epidemic[10]是經(jīng)典的路由算法之一.在Epidemic算法中,每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)緩存區(qū),存儲(chǔ)源于本節(jié)點(diǎn)和以本節(jié)點(diǎn)作為中繼節(jié)點(diǎn)的數(shù)據(jù)分組,每個(gè)數(shù)據(jù)分組有一個(gè)全局唯一標(biāo)識(shí)符.同時(shí)每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)概要向量,用來記錄節(jié)點(diǎn)所攜帶的數(shù)據(jù)分組.當(dāng)兩節(jié)點(diǎn)相遇時(shí),首先交換彼此的概要向量,獲知對(duì)方存儲(chǔ)數(shù)據(jù)分組情況后,僅傳輸對(duì)方?jīng)]有的數(shù)據(jù)分組.Epidemic算法本質(zhì)上是一種洪泛算法,每個(gè)節(jié)點(diǎn)都將數(shù)據(jù)分組轉(zhuǎn)發(fā)給所有遇到的節(jié)點(diǎn).其主要優(yōu)點(diǎn)是能最大化數(shù)據(jù)分組傳輸?shù)某晒β?找到一條最短路徑,減少傳輸延遲,其主要缺點(diǎn)是網(wǎng)絡(luò)中存在大量的數(shù)據(jù)分組副本,會(huì)消耗大量的網(wǎng)絡(luò)資源.

Spray and Wait[11](SW)也可視為基于泛洪策略的路由算法,當(dāng)兩節(jié)點(diǎn)相遇時(shí),向?qū)Ψ絺鬏敍]有的數(shù)據(jù)分組,但通過一定策略限定數(shù)據(jù)分組副本數(shù)量以免泛洪.Binary Spray and Wait (BSW)算法是SW算法的一種改進(jìn).

Ferry路由算法根據(jù)Ferry節(jié)點(diǎn)的數(shù)量可以分為兩類:單Ferry路由算法和多Ferry路由算法.根據(jù)Ferry節(jié)點(diǎn)是否按照同一路徑進(jìn)行路由,多Ferry路由算法分為:Ferry單路徑算法和Ferry多路徑算法.典型的Ferry路由算法有:MFS[22]、NIMF/FIMF[23]、SIRA/MURA/NRA/FRA[24]算法.MFS算法是一種單Ferry節(jié)點(diǎn)的路由算法,首次在DTN中引入Ferry節(jié)點(diǎn),為不存在連通的DTN節(jié)點(diǎn)提供消息轉(zhuǎn)發(fā)服務(wù),該算法主要研究靜態(tài)DTN在節(jié)點(diǎn)稀疏分布網(wǎng)絡(luò)場(chǎng)景下的數(shù)據(jù)通信問題.

為了減少冗余的通信和存儲(chǔ)開銷,本文設(shè)計(jì)了一種CBSW路由算法,該算法結(jié)合了Ferry路由與BSW路由算法的優(yōu)點(diǎn),并解決了在Spray階段簇節(jié)點(diǎn)沒有遇到Ferry節(jié)點(diǎn)造成傳輸成功率較低等問題.

3 移動(dòng)模型

3.1 網(wǎng)絡(luò)環(huán)境

被動(dòng)式Ferry路由規(guī)劃在已有的DTN部署應(yīng)用和實(shí)驗(yàn)中得到了更多的應(yīng)用,這是因?yàn)樵趯?shí)際的DTN部署應(yīng)用中,由于受地理環(huán)境、交通條件以及Ferry節(jié)點(diǎn)承載工具的限制,Ferry節(jié)點(diǎn)只能被動(dòng)地按照預(yù)先設(shè)定的運(yùn)動(dòng)路徑運(yùn)動(dòng),獨(dú)立或輔助完成DTN網(wǎng)絡(luò)的數(shù)據(jù)傳輸.例如,圖2鄉(xiāng)村通信網(wǎng)絡(luò)就是一個(gè)典型的被動(dòng)式Ferry路徑規(guī)劃的應(yīng)用實(shí)例.

網(wǎng)絡(luò)由多個(gè)互不相交的簇和預(yù)先設(shè)定的路徑組成.移動(dòng)節(jié)點(diǎn)分為Ferry節(jié)點(diǎn)和簇節(jié)點(diǎn),Ferry節(jié)點(diǎn)采用基于地圖的移動(dòng)模型,且按照預(yù)先設(shè)定的路徑移動(dòng).簇節(jié)點(diǎn)采用CMMT移動(dòng)模型,且只能在其所在的簇范圍內(nèi)按一定規(guī)則移動(dòng).設(shè)簇的個(gè)數(shù)為N,簇的范圍是半徑為R的圓形區(qū)域,每個(gè)簇內(nèi)有n個(gè)簇節(jié)點(diǎn)且簇中心位置已知,Ferry節(jié)點(diǎn)的個(gè)數(shù)為F,不同簇內(nèi)的簇節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換時(shí),需通過Ferry節(jié)點(diǎn)協(xié)作轉(zhuǎn)發(fā),并作如下設(shè)定:

(1)同一簇內(nèi)的簇節(jié)點(diǎn)在本簇范圍內(nèi)移動(dòng),移動(dòng)速度較慢,它們之間的相遇概率較高,通過一跳或多跳可完成數(shù)據(jù)交換.

(2)不同簇內(nèi)的簇節(jié)點(diǎn)移動(dòng)范圍互不相交,相遇概率為零.因此,不同簇內(nèi)的簇節(jié)點(diǎn)通過移動(dòng)速度較快的Ferry節(jié)點(diǎn)協(xié)作完成消息傳遞.

3.2 移動(dòng)模型

設(shè)節(jié)點(diǎn)A在半徑為R的圓形區(qū)域S內(nèi)運(yùn)動(dòng),Pt和Pt+1分別表示A的當(dāng)前位置和下一時(shí)刻移動(dòng)到的位置,并按以下規(guī)則從Pt移動(dòng)到Pt+1:

(1)Pt+1從S中按均勻分布隨機(jī)選擇,且其選擇與歷史及當(dāng)前位置無關(guān).

(2)A以速度Vt從Pt勻速運(yùn)動(dòng)到Pt+1,且Vt的選擇與歷史以及當(dāng)前速度大小無關(guān).以常用的均勻速度分布為例,Vt從[Vmin,Vmax) 按均勻分布隨機(jī)選擇,即f(v)=1/(Vmax-Vmin)(Vmin≤v

對(duì)于一個(gè)正方形區(qū)域S內(nèi)的RWP移動(dòng)模型[25],其節(jié)點(diǎn)位置(x,y)的分布與Vmin和Vmax無關(guān),節(jié)點(diǎn)位置分布的概率密度函數(shù),記f(x,y).其特點(diǎn)如下:

(1)節(jié)點(diǎn)運(yùn)動(dòng)方向偏向中心,方向角θ的概率密度函數(shù)為:

+cos2θ+cosθ|cosθ|+1))

(1)

f(θ)的概率分布圖如圖3所示:

(2)

對(duì)于一個(gè)圓形區(qū)域S內(nèi)的Cluster Movement (CM)移動(dòng)模型[25],節(jié)點(diǎn)位置分布的概率密度函數(shù),記f(r,θ).穩(wěn)態(tài)的概率密度函數(shù)f(r,θ)在圓形區(qū)域S內(nèi)非均勻分布,如下式所示:

(3)

為了增加簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)的相遇機(jī)會(huì),通過對(duì)RWP和CM移動(dòng)模型分析,設(shè)計(jì)了一種帶閾值的移動(dòng)模型CMMT,該移動(dòng)模型增加了Ferry節(jié)點(diǎn)與簇節(jié)點(diǎn)的相遇機(jī)會(huì).當(dāng)節(jié)點(diǎn)A從當(dāng)前坐標(biāo)(Xt,Yt)移動(dòng)到簇內(nèi)另一隨機(jī)坐標(biāo)(Xt+1,Yt+1)時(shí),需判斷(Xt+1,Yt+1)到所在簇中心的距離是否大于閾值(Threshold),如果是,則先經(jīng)過簇中心,再移動(dòng)到(Xt+1,Yt+1),否則直接移動(dòng)到(Xt+1,Yt+1).假設(shè)N個(gè)節(jié)點(diǎn)在半徑為R的圓形區(qū)域S內(nèi)運(yùn)動(dòng),N分別為3,5,7,9,10,15,20,R=100m,閾值分別為0,10,20,30,40,50,60,70,80,90,100.圖6為閾值對(duì)傳輸成功率均值的影響.以閾值=0為例,求不同節(jié)點(diǎn)個(gè)數(shù)的傳輸成功率,取其均值.當(dāng)閾值>R/2時(shí),閾值=60傳輸成功率均值最大.圖4、5、7分別為閾值=0,50,100時(shí)節(jié)點(diǎn)運(yùn)動(dòng)軌跡.CMMT包含:在簇內(nèi)按均勻分布隨機(jī)選擇坐標(biāo)(Xt+1,Yt+1)和根據(jù)條件判斷是否將簇中心加入到路徑.分別如算法1、2所示.

4 路由算法

在移動(dòng)模型CMMT基礎(chǔ)上,提出了一種基于簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)協(xié)作的Binary Spray & Wait路由算法CBSW.基本思想:在網(wǎng)絡(luò)中引入Ferry節(jié)點(diǎn),其沿著預(yù)先確定的路徑移動(dòng),通過控制簇節(jié)點(diǎn)的運(yùn)動(dòng)路徑使其與Ferry節(jié)點(diǎn)相遇,從而實(shí)現(xiàn)不同簇內(nèi)的消息傳輸.該算法分為兩個(gè)階段,Spray階段和Wait階段.

在Spray階段,源節(jié)點(diǎn)將需要傳輸?shù)南?fù)制L份.若有A節(jié)點(diǎn),其中包含n個(gè)數(shù)據(jù)分組,在n個(gè)數(shù)據(jù)分組中,包括起源于A節(jié)點(diǎn)和以A節(jié)點(diǎn)作為中繼節(jié)點(diǎn)的數(shù)據(jù)分組.A節(jié)點(diǎn)為簇節(jié)點(diǎn)或Ferry節(jié)點(diǎn).

②如果A節(jié)點(diǎn)是Ferry節(jié)點(diǎn),A進(jìn)行消息轉(zhuǎn)發(fā)時(shí),只向D節(jié)點(diǎn)所在簇內(nèi)的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā).

如果在該階段遇到目的節(jié)點(diǎn),則消息傳輸結(jié)束,否則隨后源節(jié)點(diǎn)和中繼節(jié)點(diǎn)重復(fù)進(jìn)行上述過程,直到節(jié)點(diǎn)中只有一個(gè)數(shù)據(jù)分組為止,然后此節(jié)點(diǎn)轉(zhuǎn)入Wait階段.

在Wait階段,如果消息M的源節(jié)點(diǎn)S與目的節(jié)點(diǎn)D屬于同一簇,采用Direct Delivery方式轉(zhuǎn)發(fā)給目的節(jié)點(diǎn),否則,如果在Spray階段沒有遇到Ferry節(jié)點(diǎn),采用向Ferry節(jié)點(diǎn)轉(zhuǎn)發(fā)并向重新注入L份消息副本重復(fù)Spray階段操作.流程圖如圖8所示,算法如算法3所示.

5 性能分析

在網(wǎng)絡(luò)模型中,設(shè)簇的個(gè)數(shù)為N,每個(gè)簇內(nèi)有n個(gè)簇節(jié)點(diǎn)和F個(gè)Ferry節(jié)點(diǎn),則節(jié)點(diǎn)總數(shù)為N*n+F,數(shù)據(jù)分組總數(shù)為m,消息生存時(shí)間為livebime消息副本個(gè)數(shù)為L(zhǎng).

當(dāng)n≤L時(shí),BSW算法退化成Epidemic算法,假設(shè)在某時(shí)間段△t內(nèi),數(shù)據(jù)分組mk傳輸成功的概率為Pd,目的節(jié)點(diǎn)遇到簇節(jié)點(diǎn)i的概率為Pi,節(jié)點(diǎn)攜有mk的概率為Pik；目的節(jié)點(diǎn)遇到Ferry節(jié)點(diǎn)f的概率為Pf,節(jié)點(diǎn)攜有mk的概率為Pfk,則

(4)

(5)

當(dāng)n≥L時(shí),T1為Spray階段,L為副本的數(shù)量,則

(6)

當(dāng)不同簇內(nèi)的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí),在BSW算法中,如果在Spray階段簇節(jié)點(diǎn)沒有遇到Ferry節(jié)點(diǎn),在Wait階段,采用Direct Delivery方式傳輸給目的節(jié)點(diǎn),會(huì)導(dǎo)致這些消息永遠(yuǎn)不能到達(dá)目的節(jié)點(diǎn),影響傳輸成功率.CBSW路由算法解決了這些問題,數(shù)據(jù)傳輸成功率不會(huì)隨著節(jié)點(diǎn)的增加而減少.

6 性能評(píng)價(jià)

6.1 實(shí)驗(yàn)平臺(tái)及評(píng)價(jià)指標(biāo)

ONE(Opportunistic Networking Environment)[26]仿真系統(tǒng)是SINDTN和CATDTN工程項(xiàng)目開發(fā)的,它是一個(gè)基于離散事件引擎,通過使用不同的路由協(xié)議來模擬機(jī)會(huì)網(wǎng)絡(luò)中消息的收發(fā),并生成多種報(bào)告.

為定量對(duì)比分析機(jī)會(huì)網(wǎng)絡(luò)各路由算法的性能,用傳輸成功率、傳輸延遲和路由開銷[27]作為評(píng)價(jià)路由算法的度量依據(jù).

①傳輸成功率

傳輸成功率(Delivery Ratio)是在一定時(shí)間內(nèi)成功到達(dá)目的節(jié)點(diǎn)數(shù)據(jù)分組總數(shù)和源節(jié)點(diǎn)發(fā)出的需傳輸數(shù)據(jù)分組總數(shù)之比,該度量值刻劃了路由算法正確轉(zhuǎn)發(fā)數(shù)據(jù)分組到目的節(jié)點(diǎn)的能力.

(7)

②傳輸延遲

傳輸延遲(Delivery Delay)是數(shù)據(jù)分組從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)所需要的時(shí)間,通常采用平均傳輸延遲來評(píng)價(jià).盡管機(jī)會(huì)網(wǎng)絡(luò)允許較大的延遲,但傳輸延遲小意味路由算法傳輸能力強(qiáng)、傳輸效率高,同時(shí)也意味著數(shù)據(jù)分組在傳輸過程中占用較少的網(wǎng)絡(luò)資源.平均消息傳輸延遲可用公式(8)計(jì)算,其中N表示成功傳輸?shù)南⒖倲?shù),TRi表示消息i成功到達(dá)目的節(jié)點(diǎn)的時(shí)間,TSi表示消息i的發(fā)送時(shí)間.

(8)

③路由開銷

路由開銷(Overhead)是指在一定時(shí)間內(nèi)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組的總數(shù),即源節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)分組總數(shù)和所有節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組總數(shù)之比.路由開銷高,意味著節(jié)點(diǎn)大量地轉(zhuǎn)發(fā)數(shù)據(jù)分組,這會(huì)使網(wǎng)絡(luò)中充斥著大量的數(shù)據(jù)分組副本,增加網(wǎng)絡(luò)中數(shù)據(jù)分組發(fā)生碰撞的概率,也會(huì)大量地消耗節(jié)點(diǎn)能量.

路由開銷=

(9)

6.2 仿真場(chǎng)景設(shè)計(jì)

仿真界面如圖9所示,Ferry節(jié)點(diǎn)的運(yùn)動(dòng)軌跡如圖10所示,仿真參數(shù)如表1所示.

表1 仿真場(chǎng)景設(shè)置

6.3 實(shí)驗(yàn)結(jié)果及分析

6.3.1 簇內(nèi)不同節(jié)點(diǎn)密度下路由算法的表現(xiàn)

在表1中,以不同的簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)進(jìn)行仿真.簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)采用的路由及仿真結(jié)果對(duì)應(yīng)如表2所示,仿真實(shí)驗(yàn)結(jié)果如圖11所示：

表2 簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)采用路由與仿真結(jié)果對(duì)應(yīng)表

簇節(jié)點(diǎn)采用路由Ferry節(jié)點(diǎn)采用路由仿真結(jié)果表示EpidemicEpidemicEpidemicBSWEpidemicBSW&EBSWBSWBSW

由圖11(a)可知,Epidemic、BSW&E傳輸成功率基本與簇內(nèi)節(jié)點(diǎn)密度無關(guān),BSW的傳輸成功率隨著簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的增加而下降,當(dāng)簇內(nèi)節(jié)點(diǎn)較少時(shí),其傳輸成功率高于其它兩種路由算法,當(dāng)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較多時(shí),其傳輸成功率與BSW&E算法相差較小,但不及Epidemic算法.由圖11(b)可知,當(dāng)簇內(nèi)節(jié)點(diǎn)密度達(dá)到一定程度,Epidemic的路由開銷隨其增加近似呈指數(shù)增長(zhǎng),其它兩種算法的路由開銷基本與簇內(nèi)節(jié)點(diǎn)密度無關(guān),且兩者的路由開銷較小.由圖11(c)可知,Epidemic傳輸延遲較大,BSW&E次之,BSW傳輸延遲最小.隨著簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)增加,BSW&E與BSW差距變小.

在上實(shí)驗(yàn)的基礎(chǔ)上,采用BSW路由算法,簇節(jié)點(diǎn)采用CMMT移動(dòng)模型,以不同的節(jié)點(diǎn)數(shù)再次進(jìn)行仿真,實(shí)驗(yàn)結(jié)果用CMMT-BSW表示,簇節(jié)點(diǎn)采用CM移動(dòng)模型的實(shí)驗(yàn)結(jié)果用BSW表示.仿真實(shí)驗(yàn)結(jié)果如圖12所示：

由圖12(a)可知,當(dāng)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較小時(shí),CMMT-BSW傳輸成功率比BSW有所增加,但隨著節(jié)點(diǎn)的增加,增加的幅度變小.原因分析：在增加簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)相遇機(jī)會(huì)的同時(shí),促使消息在Spray階段快速擴(kuò)散,導(dǎo)致Spray階段的時(shí)間變短.倘若在Spray階段簇節(jié)點(diǎn)沒有遇到Ferry節(jié)點(diǎn),進(jìn)入Wait階段后,用Direct Delivery方式傳輸給目的節(jié)點(diǎn),由于移動(dòng)模型的約束,攜帶消息的節(jié)點(diǎn)不可能遇到目的節(jié)點(diǎn)并傳輸給目的節(jié)點(diǎn),這樣會(huì)導(dǎo)致消息傳輸失敗.由圖12(b)可知,當(dāng)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較小時(shí),CMMT-BSW開銷比BSW小,但隨著節(jié)點(diǎn)的增加,兩者相差較小.由圖12(c)可知,在傳輸延遲上,CMMT-BSW比BSW減少,在簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)少時(shí),兩者相差較大,且隨著簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的增加而變小.

下面的實(shí)驗(yàn),簇節(jié)點(diǎn)采用CMMT移動(dòng)模型,并用CBSW和BSW路由算法進(jìn)行仿真.仿真實(shí)驗(yàn)結(jié)果如圖13所示：

由圖13(a)可知,CBSW路由算法與BSW路由算法相比,在傳輸成功率上有明顯的增加,且CBSW路由算法基本與簇內(nèi)節(jié)點(diǎn)密度無關(guān).由圖13(b)可知,CBSW比BSW在傳輸開銷上有所減少,且CBSW路由算法在簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較多時(shí),不會(huì)隨著簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的增加而增加.由圖13(c)可知,在節(jié)點(diǎn)數(shù)量少時(shí),CBSW傳輸延遲比BSW傳輸延遲有所減少,當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)量較多時(shí),CBSW傳輸延遲比BSW傳輸延遲大.

6.3.2 不同簇內(nèi)節(jié)點(diǎn)速度下路由算法的表現(xiàn)

在表1中,采用CMMT移動(dòng)模型,并用CBSW和BSW路由算法進(jìn)行仿真,在本實(shí)驗(yàn)中簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)為6,以不同的速度進(jìn)行仿真,得到如圖14所示：

由圖14(a)可知,傳輸成功率高低：CBSW>BSW在簇內(nèi)節(jié)點(diǎn)速度為0～1m/s時(shí),BSW路由算法的傳輸成功率較高,而CBSW傳輸成功率較低,當(dāng)簇內(nèi)節(jié)點(diǎn)速度大于0～1m/s,CBSW路由算法與BSW路由算法的傳輸成功率基本與簇內(nèi)節(jié)點(diǎn)速度大小無關(guān).由圖14(b)可知,BSW在速度為0～1m/s時(shí),傳輸開銷較小,當(dāng)簇內(nèi)節(jié)點(diǎn)速度大于0～1m/s時(shí),BSW路和CBSW路由算法的開銷基本與簇內(nèi)節(jié)點(diǎn)速度大小無關(guān).由圖14(c)可知,在簇內(nèi)節(jié)點(diǎn)速度為0～1m/s時(shí),CBSW與BSW傳輸延遲都較大,當(dāng)簇內(nèi)節(jié)點(diǎn)速度大于0～1m/s時(shí),它們的傳輸延遲基本與簇內(nèi)節(jié)點(diǎn)速度大小無關(guān).

6.3.3 不同簇內(nèi)節(jié)點(diǎn)緩存下路由算法的表現(xiàn)

在表1中,同樣地,采用CMMT移動(dòng)模型,并用Epidemic,CBSW和BSW路由算法進(jìn)行仿真,在本實(shí)驗(yàn)中簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)為50,以不同的緩存進(jìn)行仿真,得到如圖15所示：

由圖15(a)可知,CBSW與BSW路由算法的傳輸成功率基本與簇內(nèi)節(jié)點(diǎn)緩存大小無關(guān).Epidemic路由算法的傳輸成功率隨著簇內(nèi)節(jié)點(diǎn)緩存的增加而增加.由此可見,CBSW路由算法的成功率較高,占用緩存較小.由圖15(b)可知,CBSW與BSW路由算法的路由開銷基本與簇內(nèi)節(jié)點(diǎn)緩存大小無關(guān).Epidemic路由算法的傳輸成功率隨著簇內(nèi)節(jié)點(diǎn)緩存的增加而減少.與Epidemic相比,CBSW與BSW路由算法的路由開銷較小.由圖15(c)可知,CBSW路由算法與BSW路由算法的傳輸延遲基本與簇內(nèi)節(jié)點(diǎn)緩存大小無關(guān).Epidemic路由算法的傳輸成功率隨著簇內(nèi)節(jié)點(diǎn)緩存的增加而增加.

6.3.4 不同F(xiàn)erry節(jié)點(diǎn)密度下路由算法的表現(xiàn)

本實(shí)驗(yàn)采用多個(gè)Ferry節(jié)點(diǎn)按照相同路徑進(jìn)行運(yùn)動(dòng),Ferry節(jié)點(diǎn)個(gè)數(shù)分別取1,2,4,用CBSW算法進(jìn)行仿真.仿真結(jié)果如圖16所示：

由圖16(a)可知,當(dāng)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較多時(shí),隨著Ferry節(jié)點(diǎn)個(gè)數(shù)的增加,傳輸成功率有所增加; 圖16(b)可知,隨著Ferry節(jié)點(diǎn)個(gè)數(shù)的增加,傳輸開銷有所增加；圖16(c)可知,傳輸延遲隨著Ferry節(jié)點(diǎn)個(gè)數(shù)的增加也是有所減少.

7 結(jié)論

在本文中,一方面通過設(shè)置閾值經(jīng)過簇中心的方式,增加簇節(jié)點(diǎn)與Ferry節(jié)點(diǎn)的相遇概率,設(shè)計(jì)了CMMT移動(dòng)模型.另一方面,由于相遇概率的增加,使緩存中的消息增加和消息擴(kuò)散速度增加,為減少節(jié)點(diǎn)緩存中的消息的數(shù)量,刪除了用不到的消息,并解決了在Spray階段簇節(jié)點(diǎn)沒有遇到Ferry節(jié)點(diǎn),引起傳輸成功率下降的問題,設(shè)計(jì)了CBSW路由算法.仿真實(shí)驗(yàn)表明,CBSW算法能夠增加傳輸成功率,且其傳輸成功率基本與簇內(nèi)節(jié)點(diǎn)密度無關(guān),該算法減少路由開銷,并且在簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)較小時(shí),減少傳輸延遲.

本文中采用的移動(dòng)模型具有嚴(yán)格的條件約束,這與現(xiàn)實(shí)情況還存在一定的差距,需進(jìn)一步完善.多Ferry節(jié)點(diǎn)路由算法,本文采用的是同一路徑的方法,對(duì)于不同路徑還需進(jìn)一步深入研究.

[1]CHAINTREAU A,HUI P,CROWCROFT J,et al.Pocket switched networks:real-world mobility and its consequences for opportunistic forwarding [R].University of Cambridge,Computer Lab,Tech Rep UCAM-CL-TR-617,2005.

[2]PELUSI L,PASSARELLA A,CONTIM.Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J].Communications Magazine,IEEE,2006,44(11):134-141.

[3]JUANG P,OKI H,WANG Y,et al.Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with ZebraNet[A].Proceeding of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems[C].New York:ACM,2002.96-107.

[4]SMALL T,HAAS Z J.The shared wireless infestation model:a new ad hoc networking paradigm [A].Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing[C].New York:ACM,2003.233-244.

[5]HULL B,BYCHKOVSKY V,ZHANG Y,et al.CarTel:a distributed mobile sensor computing system[A].The 4th ACM Conference on Embedded Networked Sensor System[C].Colorado:ACM,2006.125-138.

[6]PENTLAND A,FLETCHER R,HASSON A.DakNet:rethinking connectivity in developing nations[J].Computer,2004,37(1):78-83.

[7]MOREIRA W,FERREIRA R,CIRQUEIRA D,et al.SocialDTN:a DTN implementation for digital and social inclusion[A].ACM MobiCom Workshop on Lowest Cost Denominator Networking for Universal Access[C].Miami:ACM,2013.25-28.

[8]MOREIRA W,MENDES P,FERREIRA R,et al.Opportunistic routing based on users daily life routine[A].World of Wireless,Mobile and Multimedia Networks (WoWMoM),2012 IEEE International Symposium[C].Baltimore:IEEE,2012.1-6.

[9]NAUMOV V,GROSS T R.Connectivity-aware routing (CAR) in vehicular ad-hoc networks[A].INFOCOM 2007.26th IEEE International Conference on Computer Communications[C].Anchorage:IEEE,2007.1919-1927.

[10]VAHDAT A,BECKER D.Epidemic routing for partially connected ad hoc networks,CS2200006[R].Durham,NC:Duke University,2000.

[11]SPYROPOULOS T,PSOUNIS K,PAGHAVENDRA C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[A].Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking[C].New York:ACM,2005.252-259.

[12]LINDGREN A,DORIA A,SCHENLEN O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[13]SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Efficient routing in intermittently connected mobile networks:the multiple-copy case[J].Networking,IEEE/ACM Transactions on,2008,16(1):77-90.

[14]熊永平等,孫利民,年建偉,劉燕.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2009,20(1):124-137.

XIONG Yong-Ping,SUN Li-Min,NIU Jian-Wei,LIU Yan.Opportunistic Networks[J].Journal of Software,2009,20(1):124-137.(in Chinese)

[15]BETTSTETTER C,RESTA G,SANETI P.The node distribution of the random waypoint mobility model for wireless ad hoc networks[J].Mobile Computing,IEEE transactions on,2003,2(3):257-269

[16]HONG X,GERLA M,PEI G,et al.A group mobility model for ad hoc wireless networks[A].Proceedings of the 2nd ACM International Workshop on Modeling,Analysis and Simulation of Wireless and Mobile Systems[C].New York:ACM,1999.53-60

[17]ROYER E M,MELLIAR-SMITH P M,MOSER L E.An analysis of the optimum node density for ad hoc mobile networks[A].Proceedings of the IEEE International Conference on Communications[C].USA:IEEE,2001.857-861.

[18]EAGLE N,PENTLAND A.Reality mining:sensing complex social systems[J].Personal and Ubiquitous Computing,2006,10(4):255-268.

[19]The University California S D.Wireless Topology Discovery Project[Z].UCSD,2004.

[20]DIO I.An Innovative Paradigm for Autonomic Opportunistic Communication[Z].2010.

[21]ZHANG X,KUROSE J,LEVINE B N,et al.Study of a bus-based disruption-tolerant network:mobility modeling and impact on routing[A].The 3th Annual International Conference on Mobile Computing and Networking[C].Montreal:MobiCom,2007.195-206.

[22]ZHAO W,AMMAR M,and ZEGURA E.Message ferrying proactive routing in highly-partitioned wireless and ad hoc networks[A].The 9th IEEE International Workshop on Future Trends in Distributed Computing Systems (FTDCS)[C].Puerto:IEEE,2003.308-314.

[23]ZHAO W,et al.A message ferrying approach for data delivery in sparse mobile Ad Hoc networks[A].Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc'04)[C].New York:ACM,2004.187-98.

[24]Zhao W,AMMAR M,ZEGURA E.Controlling the mobility of multiple data transport ferries in a delay-tolerant network[A].Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05)[C].Miami:IEEE,2005.1407-1418.

[25]BETTSTETTER C,WAGNER C.The spatial node distribution of the random waypoint mobility model[A].Proceedings of German Workshop on Mobile Ad Hoc networks(WMAN)[C].Germany:IEEE,2002.41-58

[26]KERANEN A.Opportunistic network environment simulator[R].Special Assignment report,Helsinki University of Technology,Department of Communications and Networking,2008.

[27]JONES E,WARD P.Routing strategies for delay-tolerant networks[A].Proceedings of the ACM SIGCOMM workshop on Delay-tolerant networking[C].New York:ACM,2006.1577-1580.

劉春蕊 女,1987年出生于河南周口,現(xiàn)為蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生,主要研究方向?yàn)椋喝褐歉兄?、網(wǎng)絡(luò)編碼以及隱私保護(hù)等.

E-mail:20134227012@suda.edu.cn

張書奎 男,1966年生于內(nèi)蒙古,博士,教授、博士生導(dǎo)師,主要研究方向?yàn)槲锫?lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)、信息安全、移動(dòng)計(jì)算、智能信息處理等.

E-mail:zhangsk@suda.edu.cn

Routing Mechanism Based on the Cooperation of the Ferry Nodes and Cluster Nodes in Opportunistic Networks

LIU Chun-rui1,ZHANG Shu-kui1,2,JIA Jun-cheng1,LIN Cheng-kuan1

(1.SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou,Jiangsu215006,China;2.JiangsuHighTechnologyResearchKeyLaboratoryforWirelessSensorNetworks,Nanjing,Jiangsu210003,China)

Opportunistic Networks are delay tolerant self-organized networks with sparse nodes,where the message propagation depends on the cooperation of nodes to fulfill a “store-carry-process-and-forward” fashion by leveraging the mobility of nodes,because there does not exist a complete path from the source to the destination in the most time.To achieve the communication of nodes in mutually disjoint clusters,we propose a Cluster Movement Model with Threshold (CMMT) and routing algorithm (CBSW),which is Cooperative Binary Spray and Wait routing algorithm based on the Ferry nodes and cluster nodes cooperation.This routing algorithm reduces of the redundancy of communication and store the cost,as well as if the destination or Ferry nodes are not found in the spraying phase,nodes carrying a message copy will forward the message only to its destination in the Waiting phase nodes etc.Simulation results demonstrate the effectiveness of the proposed CBSW protocol in terms of high delivery ratio,low overhead and small average delay.

opportunistic networks;movement model;cooperation;routing algorithm

2015-04-23;

2015-10-13：責(zé)任編輯：馬蘭英

國家自然科學(xué)基金(No.61201212,No.61572340);江蘇省自然科學(xué)基金資助項(xiàng)目(No.BK2011376);江蘇省“六大人才高峰”項(xiàng)目(No.2014-WLW-010);蘇州市融合通信重點(diǎn)實(shí)驗(yàn)室(No.SKLCC2013XX)；江蘇省產(chǎn)學(xué)前瞻性項(xiàng)目(No.BY2012114)；軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心部分資助;江蘇省科技項(xiàng)目(No.BY2014059-02)

TP393.04

A

0372-2112 (2016)11-2607-11

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.007