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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

路由和轉(zhuǎn)發(fā)是組網(wǎng)技術(shù)的兩個首要問題.現(xiàn)有的Ad-Hoc網(wǎng)絡(luò)路由協(xié)議都是假設(shè)源節(jié)點與目的節(jié)點之間至少存在一條連通路徑,不適合于機(jī)會網(wǎng)絡(luò).機(jī)會網(wǎng)絡(luò)以“存儲—攜帶—處理—轉(zhuǎn)發(fā)”的模式工作,當(dāng)路由表中不存在下一跳節(jié)點時,消息在當(dāng)前節(jié)點存儲,并隨著該節(jié)點的移動尋找合適的轉(zhuǎn)發(fā)時機(jī),因而每個消息選擇合適的轉(zhuǎn)發(fā)節(jié)點和時機(jī)就成為設(shè)計高效機(jī)會網(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ī)制、主動運(yùn)動的轉(zhuǎn)發(fā)機(jī)制和基于效用的轉(zhuǎn)發(fā)機(jī)制,如圖1所示.

2.2 移動過程

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

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

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

2.3 路由算法

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

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

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

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

3 移動模型

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

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

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

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

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

3.2 移動模型

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

4 路由算法

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

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

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

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

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

5 性能分析

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

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

(4)

(5)

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

(6)

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

6 性能評價

6.1 實驗平臺及評價指標(biāo)

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

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

①傳輸成功率

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

(7)

②傳輸延遲

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

(8)

③路由開銷

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

路由開銷=

(9)

6.2 仿真場景設(shè)計

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

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

6.3 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)論

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

本文中采用的移動模型具有嚴(yán)格的條件約束,這與現(xiàn)實情況還存在一定的差距,需進(jìn)一步完善.多Ferry節(jié)點路由算法,本文采用的是同一路徑的方法,對于不同路徑還需進(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ī)會網(wǎng)絡(luò)[J].軟件學(xué)報,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ī)科學(xué)與技術(shù)學(xué)院碩士研究生,主要研究方向為：群智感知、網(wǎng)絡(luò)編碼以及隱私保護(hù)等.

E-mail:20134227012@suda.edu.cn

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

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

TP393.04

A

0372-2112 (2016)11-2607-11

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

10.3969/j.issn.0372-2112.2016.11.007