武淑艷 韓毅剛 傅秋宇 馮 飛

(南開大學(xué)電子信息與光學(xué)工程學(xué)院 天津 300350)

?

基于接觸信息的自適應(yīng)機(jī)會網(wǎng)絡(luò)路由算法

武淑艷 韓毅剛 傅秋宇 馮 飛

(南開大學(xué)電子信息與光學(xué)工程學(xué)院 天津 300350)

考慮到實(shí)際網(wǎng)絡(luò)環(huán)境的不斷變化以及機(jī)會網(wǎng)絡(luò)節(jié)點(diǎn)總是在密集與稀疏場景間隨機(jī)切換的特點(diǎn)，提出一種能夠借助節(jié)點(diǎn)接觸信息進(jìn)行網(wǎng)絡(luò)環(huán)境判斷的自適應(yīng)路由算法——CIAONR(Contact Information-based Adaptive Opportunity Network Routing)。CIAONR在節(jié)點(diǎn)分布式采集接觸信息的過程中，利用節(jié)點(diǎn)接觸延遲與生存期的關(guān)系判斷節(jié)點(diǎn)所處網(wǎng)絡(luò)環(huán)境。然后依據(jù)CIAONR約束條件指導(dǎo)轉(zhuǎn)發(fā)路徑的選擇，最終按照對應(yīng)交互流程完成消息交付。理論分析和仿真結(jié)果表明，CIAONR算法在不同網(wǎng)絡(luò)環(huán)境下均保持較高投遞率，網(wǎng)絡(luò)開銷和延遲也控制在一定范圍內(nèi)，具有普適效果。

機(jī)會網(wǎng)絡(luò) 路由算法 接觸信息 自適應(yīng)

0 引 言

機(jī)會網(wǎng)絡(luò)是一種基于節(jié)點(diǎn)接觸形成通信機(jī)會進(jìn)而通過逐跳轉(zhuǎn)發(fā)實(shí)現(xiàn)數(shù)據(jù)交互的移動自組織網(wǎng)絡(luò)MANET(Mobile Ad-Hoc Network)，是實(shí)現(xiàn)間歇式連通環(huán)境下節(jié)點(diǎn)通信的基本方法。早期機(jī)會網(wǎng)絡(luò)主要應(yīng)用于野生動物追蹤、災(zāi)難環(huán)境臨時組網(wǎng)、偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)覆蓋等場景，應(yīng)用局限性較大。近幾年隨著各種便攜式設(shè)備迅速發(fā)展和普及，移動設(shè)備感知、計(jì)算、通信、存儲等能力越來越強(qiáng)，物聯(lián)網(wǎng)、車聯(lián)網(wǎng)快速興起，智慧城市等新概念每日更新，機(jī)會網(wǎng)絡(luò)因其對網(wǎng)絡(luò)全連通無要求的特點(diǎn)，更符合實(shí)際環(huán)境的需求，再次受到高度關(guān)注。

機(jī)會網(wǎng)絡(luò)中，節(jié)點(diǎn)環(huán)境常在密集與稀疏間進(jìn)行反復(fù)切換[1-2]，如大量野生動物群聚生活，車聯(lián)網(wǎng)用戶在社區(qū)間穿梭等場景，而現(xiàn)有機(jī)會網(wǎng)絡(luò)路由算法的研究和評估主要側(cè)重于在一個特定場景下投遞率、傳輸延遲和轉(zhuǎn)發(fā)代價之間的權(quán)衡，對網(wǎng)絡(luò)環(huán)境快速變化這一特點(diǎn)的考慮和研究相對較少。節(jié)點(diǎn)接觸信息主要包括節(jié)點(diǎn)接觸時長、接觸延遲、相遇頻率等，能夠較全面地將當(dāng)前網(wǎng)絡(luò)環(huán)境進(jìn)一步量化，為機(jī)會網(wǎng)絡(luò)路由算法提供自適應(yīng)調(diào)整依據(jù)。因此，本文著眼于機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)的接觸信息，提出了一種自適應(yīng)路由算法——CIAONR，對密集、稀疏網(wǎng)絡(luò)拓?fù)淠軌蜃孕信卸?，進(jìn)而達(dá)到提高不同網(wǎng)絡(luò)環(huán)境下投遞率，控制網(wǎng)絡(luò)開銷和延遲的目的，有效提高了路由的普適效果。

1 相關(guān)工作

機(jī)會網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)闹饕ぷ鞣绞綖椤按鎯?攜帶-轉(zhuǎn)發(fā)”，如何選擇轉(zhuǎn)發(fā)時機(jī)和轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)是機(jī)會網(wǎng)絡(luò)路由算法主要解決的問題[3]?，F(xiàn)有機(jī)會轉(zhuǎn)發(fā)策略基本分為兩類，即零信息型和信息輔助型[4]，見圖1所示。

圖1 機(jī)會網(wǎng)絡(luò)轉(zhuǎn)發(fā)策略分類

零信息型是最早提出的機(jī)會網(wǎng)絡(luò)路由算法，包括Epidemic、Spray and Wait等算法。Epidemic算法是一種模仿傳染病擴(kuò)散的洪泛算法，相遇即轉(zhuǎn)發(fā)存儲，在網(wǎng)絡(luò)資源充足的情況下能夠獲得最優(yōu)的延時性能，但由于網(wǎng)絡(luò)中存在大量的分組副本，網(wǎng)絡(luò)開銷也相對增大。Spray and Wait算法針對Epidemic進(jìn)行了改進(jìn)，通過向網(wǎng)絡(luò)中洪泛固定數(shù)目的分組副本來實(shí)現(xiàn)保持較低的傳輸延遲和網(wǎng)絡(luò)開銷的目的，其傳輸量遠(yuǎn)小于Epidemic，網(wǎng)絡(luò)延遲接近最優(yōu)，具有較好的擴(kuò)展性。在此基礎(chǔ)上，研究學(xué)者進(jìn)一步提出了將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于機(jī)會網(wǎng)絡(luò)的路由算法，對Epidemic算法進(jìn)行了一系列改進(jìn)[5]。Katti等提出基于機(jī)會的網(wǎng)絡(luò)編碼方法COPE，有效提高無線網(wǎng)絡(luò)的傳輸容量和吞吐量。Chachulski等對COPE進(jìn)行了改進(jìn)，提出MORE協(xié)議將編碼信息路由到多跳鄰居節(jié)點(diǎn)，網(wǎng)絡(luò)吞吐量進(jìn)一步提升。

由于充分利用了實(shí)際網(wǎng)絡(luò)中反映出來的信息，近年來信息輔助型策略更受關(guān)注。PROPHET算法依據(jù)歷史信息提出了基于節(jié)點(diǎn)接觸概率的傳輸預(yù)測路由算法，在社區(qū)模型場景中性能較好。GBP算法在此基礎(chǔ)上考慮了節(jié)點(diǎn)分組情況，認(rèn)為同組節(jié)點(diǎn)不應(yīng)保存相同副本，通過本地信息引導(dǎo)分組副本到達(dá)目的節(jié)點(diǎn)，在網(wǎng)絡(luò)開銷上表現(xiàn)出色，但網(wǎng)絡(luò)延遲較大[6]。Burgess等學(xué)者提出的MaxProp算法根據(jù)鏈路的歷史數(shù)據(jù)進(jìn)行數(shù)據(jù)分組的優(yōu)先級劃分，然后按照優(yōu)先級調(diào)度數(shù)據(jù)分組，獲得了較高的成功送達(dá)率，但網(wǎng)絡(luò)開銷、傳輸延遲都隨之增大。Tan等學(xué)者對下一條鄰居節(jié)點(diǎn)進(jìn)行歷史傳輸時間標(biāo)記，建立了局部最小傳輸延遲算法MTDA[7]，減小了節(jié)點(diǎn)之間的傳輸延遲。在利用鄰居節(jié)點(diǎn)信息指導(dǎo)路由轉(zhuǎn)發(fā)方面，任智等學(xué)者提出了基于旁聽的機(jī)會網(wǎng)絡(luò)路由算法ORON[8]，通過旁聽鄰居節(jié)點(diǎn)信息設(shè)計(jì)博弈策略從而激勵節(jié)點(diǎn)交易。

此外，Chen、Bulut等學(xué)者從人文社會的角度提出了根據(jù)社會關(guān)系進(jìn)行節(jié)點(diǎn)劃分的機(jī)會網(wǎng)絡(luò)路由算法[9-11]，在社區(qū)等特定場景下獲得較好的網(wǎng)絡(luò)性能，但適用場景局限性較大。

2 基于接觸信息的自適應(yīng)路由算法

為打破路由算法適用場景局限的問題，重點(diǎn)考慮機(jī)會網(wǎng)絡(luò)環(huán)境變化的特點(diǎn)，提出基于接觸信息的自適應(yīng)路由算法CIAONR。本節(jié)主要從網(wǎng)絡(luò)模型、數(shù)據(jù)模型等方面詳述了節(jié)點(diǎn)對接觸信息的整合和應(yīng)用，并進(jìn)行了深入的理論分析。

2.1 機(jī)會網(wǎng)絡(luò)模型

定義1 網(wǎng)絡(luò)模型。機(jī)會網(wǎng)絡(luò)用帶權(quán)有向圖G=(V,E,F)表示，其中節(jié)點(diǎn)集合V={v1,v2, …,vn}，網(wǎng)絡(luò)規(guī)模為n，n>1；網(wǎng)絡(luò)鏈路集合E=?∪{e1,e2,…,em}，ek=vivj表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的鏈路，節(jié)點(diǎn)鏈路規(guī)模為m，1≤m≤n(n-1)；F(ek)表示em的權(quán)值集。

定義2 鏈路權(quán)重模型。F(ek)為鏈路ek=vivj的權(quán)值集合，F(xiàn)(ek)={Tk,Lk,Pk}，Tk表示節(jié)點(diǎn)vi與節(jié)點(diǎn)v=之間的鏈路持續(xù)時間均值，Tk>0；Lk表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的鏈路相鄰兩次建立的時間延遲均值，Lk>0；Pk表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的鏈路建立概率，即節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的接觸概率，0≤Pk≤1。

性質(zhì)1 節(jié)點(diǎn)鏈路為有向模型，鏈路建立對兩節(jié)點(diǎn)作用一致，即vivj與vjvi表示的是同一條鏈路。但從兩節(jié)點(diǎn)方向看鏈路對應(yīng)權(quán)重不完全相同，鏈路有方向之分。

定義3 節(jié)點(diǎn)模型。在節(jié)點(diǎn)規(guī)模為n的機(jī)會網(wǎng)絡(luò)中，每個節(jié)點(diǎn)維護(hù)3個n×n數(shù)據(jù)矩陣，即接觸概率矩陣PALL、接觸時間矩陣TALL、延遲矩陣LALL。矩陣行列交叉點(diǎn)即為對應(yīng)節(jié)點(diǎn)對接觸信息，如PALL矩陣的第i行第j列值Pij即為從本節(jié)點(diǎn)角度看節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的接觸頻率，如圖2所示，PALL第一行為節(jié)點(diǎn)v1與其他(n-1)個節(jié)點(diǎn)的接觸概率，以此類推。各矩陣均記錄了上一次更新時間LastUpdateTime，節(jié)點(diǎn)相遇則以此為依據(jù)重新計(jì)算概率值或進(jìn)行相應(yīng)數(shù)據(jù)更新。

圖2 節(jié)點(diǎn)接觸概率矩陣PALL

由于鏈路建立對兩節(jié)點(diǎn)作用效果是對等的，則接觸時間、接觸延遲對兩節(jié)點(diǎn)而言均一致。節(jié)點(diǎn)接觸概率根據(jù)各節(jié)點(diǎn)接觸其他節(jié)點(diǎn)的頻率會發(fā)生相應(yīng)變化，因而存在差異。節(jié)點(diǎn)更新接觸概率時會進(jìn)行歸一化處理，接觸概率矩陣PALL行向量逐項(xiàng)求和為1。

定義4 節(jié)點(diǎn)相遇概率。從移動模型角度看，節(jié)點(diǎn)兩兩相遇的概率為[12]：

(1)

其中，ω為移動模型常量，對應(yīng)特定移動模型為固定值。R為節(jié)點(diǎn)通信范圍，在本文中也設(shè)置為常量。A為節(jié)點(diǎn)移動區(qū)域面積，在此以輻射區(qū)域計(jì)算。本式可簡化為：

(2)

定義5 平均傳輸字節(jié)數(shù)。節(jié)點(diǎn)進(jìn)行多次分組復(fù)制后，對每次傳輸?shù)淖止?jié)數(shù)求均值記為該節(jié)點(diǎn)的平均傳輸字節(jié)數(shù)，用符號BAVG表示，每次進(jìn)行傳輸后自動更新。

2.2 數(shù)據(jù)交互模型

機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)的信息傳遞完全依賴節(jié)點(diǎn)相遇機(jī)會來完成，網(wǎng)絡(luò)中傳遞的數(shù)據(jù)分組類型主要有3種，即摘要向量SV、數(shù)據(jù)分組副本、分組到達(dá)確認(rèn)信息ACK。在本算法中，摘要向量SV主要包含本節(jié)點(diǎn)維護(hù)的3個n×n數(shù)據(jù)矩陣信息，分組到達(dá)確認(rèn)信息ACK則用于通知所有節(jié)點(diǎn)已成功交付的數(shù)據(jù)分組。具體交互流程如圖3所示。

1) 節(jié)點(diǎn)vi與節(jié)點(diǎn)vj相遇首先交換本節(jié)點(diǎn)攜帶的以對方為目的節(jié)點(diǎn)的數(shù)據(jù)分組，并將已成功交付信息加入到ACK中。

2) 交換vi與vj各自維護(hù)的SV向量表，進(jìn)行PALL、TALL、LALL的交換更新，根據(jù)最新數(shù)據(jù)重新計(jì)算緩存區(qū)內(nèi)數(shù)據(jù)分組副本的開銷，更新數(shù)據(jù)分組隊(duì)列。

3) 交換ACK信息，對應(yīng)刪除緩存區(qū)內(nèi)已成功交付數(shù)據(jù)分組的副本。

4) 依據(jù)數(shù)據(jù)分組隊(duì)列進(jìn)行數(shù)據(jù)分組副本傳遞，更新各副本的剩余副本數(shù)量值，完成交互，更新TALL中對應(yīng)本節(jié)點(diǎn)相關(guān)數(shù)據(jù)。

圖3 節(jié)點(diǎn)相遇交互流程

2.3 關(guān)于節(jié)點(diǎn)接觸信息的CIAONR約束條件

在機(jī)會網(wǎng)絡(luò)的信息交互過程中，節(jié)點(diǎn)接觸信息是對節(jié)點(diǎn)運(yùn)動、通信最直接而有效的量化表示。大量數(shù)據(jù)分析顯示，移動網(wǎng)絡(luò)中大部分節(jié)點(diǎn)相遇間隔時間較短，呈現(xiàn)近似的冪律分布[13-16]，即節(jié)點(diǎn)的移動和相遇有社區(qū)聚集現(xiàn)象。同社區(qū)節(jié)點(diǎn)在較短時間內(nèi)可以產(chǎn)生大量的相遇，而不同社區(qū)的節(jié)點(diǎn)相遇則需要較長的時間。

文獻(xiàn)[16]數(shù)據(jù)顯示，在一個較長的單位時間T里，有超過95%的相遇發(fā)生在遠(yuǎn)不足10%的時間中，相遇發(fā)生的時間間隔短，稱為節(jié)點(diǎn)處于BUSY狀態(tài)；而在剩下的T的90%時間中，僅發(fā)生了不足5%的相遇，相遇時間間隔長，節(jié)點(diǎn)處于SPARE狀態(tài)。當(dāng)節(jié)點(diǎn)處于BUSY狀態(tài)(在本社區(qū)內(nèi)運(yùn)動)，應(yīng)積極的與接觸節(jié)點(diǎn)進(jìn)行高效快速的信息交互；處于SPARE狀態(tài)下(在社區(qū)間運(yùn)動)，節(jié)點(diǎn)則應(yīng)以低開銷為前提給相遇節(jié)點(diǎn)盡可能多的散布副本。因此根據(jù)節(jié)點(diǎn)接觸頻率、接觸時長、接觸時延有效判斷節(jié)點(diǎn)社區(qū)分組和所處狀態(tài)，進(jìn)而作出能夠自動調(diào)整的路由算法是非常有必要的。

假設(shè)一個小型網(wǎng)絡(luò)由6個節(jié)點(diǎn)組成，每組包含2個節(jié)點(diǎn)，具體分布如圖4所示。為簡化模型，節(jié)點(diǎn)隨機(jī)移動，節(jié)點(diǎn)接觸概率p接觸采用改進(jìn)后的增量平均化方法進(jìn)行估算和更新，見式(3)：

(3)

其中，p遇由式(1)給出。α為接觸概率衰減因子，α∈(0,1)。k是兩節(jié)點(diǎn)相遇延遲的時間單位數(shù)。計(jì)算公式如下：

(4)

圖4 小型網(wǎng)絡(luò)節(jié)點(diǎn)分布圖

假設(shè)有消息M要從節(jié)點(diǎn)1發(fā)送到節(jié)點(diǎn)4，消息M的生存期為TTTL，可進(jìn)行一次副本復(fù)制。節(jié)點(diǎn)1首先向節(jié)點(diǎn)x傳送1個副本，節(jié)點(diǎn)x可在節(jié)點(diǎn)2、節(jié)點(diǎn)3、節(jié)點(diǎn)5和節(jié)點(diǎn)6中進(jìn)行選擇。節(jié)點(diǎn)1或節(jié)點(diǎn)x若在TTTL到期前遇到節(jié)點(diǎn)4則可完成交付。

傳送副本過程中，認(rèn)為同一社區(qū)內(nèi)節(jié)點(diǎn)相遇概率高于不同社區(qū)間節(jié)點(diǎn)相遇概率，簡化后如式(5)，a為不同社區(qū)間距離表示。

(5)

(6)

當(dāng)x=3時，則A組、C組各有1個副本存在，消息M送達(dá)概率為p1,3→4。

(7)

計(jì)算二者之差，

(8)

由于α∈(0,1)，(k2-k1)≥1且為正整數(shù)，所以αk2-k1<1，(r+a)2>r2，易得p1,3→4-p1,2→4<0，即p1,3→4

顯然，當(dāng)x=5、x=6時，

由此可知，當(dāng)消息生存期足夠長，僅量化考慮延遲對數(shù)據(jù)分組交付的影響時，將副本傳送給本組內(nèi)節(jié)點(diǎn)能夠獲得較大投遞率，對應(yīng)場景為密集環(huán)境。而在文獻(xiàn)[6]中理論分析認(rèn)為，當(dāng)不考慮延遲對交付的影響，僅考慮消息生存期限制時，傳遞到不同社區(qū)節(jié)點(diǎn)的交付概率比傳遞給同社區(qū)節(jié)點(diǎn)交付概率大，在此情況下傳遞給頻繁相遇的節(jié)點(diǎn)會對消息的傳輸起到增大開銷的作用，對應(yīng)稀疏場景。綜上所述，對于信息的投遞時機(jī)與投遞對象應(yīng)根據(jù)節(jié)點(diǎn)所處環(huán)境進(jìn)行相應(yīng)調(diào)整，從而達(dá)到投遞率最大化，網(wǎng)絡(luò)開銷最小化的目的。

(10)

1) 當(dāng)TCompare≥T閾時，認(rèn)為節(jié)點(diǎn)處于密集環(huán)境，將消息優(yōu)先傳送給接觸概率大的節(jié)點(diǎn)；

2) 當(dāng)TCompare

2.4 數(shù)據(jù)分組隊(duì)列與節(jié)點(diǎn)接觸度隊(duì)列維護(hù)規(guī)則

對于數(shù)據(jù)分組隊(duì)列，當(dāng)分組跳數(shù)小于等于閾值T分組時，按照跳數(shù)進(jìn)行排序，假定跳數(shù)小的數(shù)據(jù)分組送達(dá)率高，優(yōu)先發(fā)送跳數(shù)小的數(shù)據(jù)分組；當(dāng)分組跳數(shù)大于閾值T分組時，按照路徑開銷排序，單跳路徑開銷計(jì)算公式如下：

(11)

使用Dijkstra算法求出最小開銷路徑，根據(jù)消息的最小開銷進(jìn)行排序。

節(jié)點(diǎn)接觸度隊(duì)列按照各節(jié)點(diǎn)與本節(jié)點(diǎn)接觸度進(jìn)行排序。節(jié)點(diǎn)相遇時，首先按照消息隊(duì)列順序讀取數(shù)據(jù)分組，查詢下一跳節(jié)點(diǎn)與本節(jié)點(diǎn)接觸度p下一跳。當(dāng)TCompare≥T閾時，僅將滿足p下一跳≥T節(jié)點(diǎn)的消息發(fā)送給對應(yīng)下一跳節(jié)點(diǎn)，否則跳過該消息，讀取下一消息；當(dāng)TCompare

3 仿真結(jié)果及分析

采用機(jī)會網(wǎng)絡(luò)專用仿真平臺ONE分別在不同網(wǎng)絡(luò)規(guī)模和不同節(jié)點(diǎn)容量下進(jìn)行建模和仿真，以數(shù)據(jù)分組成功投遞率、網(wǎng)絡(luò)開銷、數(shù)據(jù)分組平均端到端時延三個指標(biāo)對Epidemic、Spray And Wait、GBP[5]和CIAONR算法性能進(jìn)行比較。

3.1 仿真參數(shù)設(shè)置

仿真實(shí)驗(yàn)使用赫爾辛基(Helsinki)部分地區(qū)為背景，主要參數(shù)設(shè)置如表1所示。

表1 主要仿真參數(shù)

在仿真時間1 000 s后隨機(jī)選取節(jié)點(diǎn)，在間隔時間區(qū)間[25,35]內(nèi)隨機(jī)產(chǎn)生新消息，從1 000 s開始，到43 200 s結(jié)束，共計(jì)發(fā)送[1 206,1 688]個數(shù)據(jù)分組。選取隨機(jī)種子集合{128,130,132,134}，每組實(shí)驗(yàn)做4次仿真，取統(tǒng)計(jì)結(jié)果的平均值進(jìn)行分析。

3.2 固定節(jié)點(diǎn)緩存改變節(jié)點(diǎn)規(guī)模

在固定節(jié)點(diǎn)緩存容量為20 MB的情況下，對不同節(jié)點(diǎn)規(guī)模進(jìn)行了仿真。圖5是隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加各路由算法的成功投遞率變化趨勢。CIAONR算法在各種節(jié)點(diǎn)規(guī)模下均為最佳，在節(jié)點(diǎn)規(guī)模為400時，成功投遞率超過95%，接近100%。而在4 500 m×3 400 m的范圍內(nèi)僅有50個節(jié)點(diǎn)時，由于CIAONR算法引入了自適應(yīng)調(diào)整機(jī)制，在節(jié)點(diǎn)密度較低的情況下能夠做出自行判斷，成功投遞率接近60%，投遞效果較為穩(wěn)定。

圖5 固定緩存改變節(jié)點(diǎn)規(guī)模-投遞率

圖6(a)為固定節(jié)點(diǎn)緩存容量的情況下，4種路由算法的網(wǎng)絡(luò)交付開銷率，開銷率用源節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)分組總數(shù)和所有節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組總數(shù)之比來進(jìn)行評價。由于Epidemic算法“隨遇隨傳隨存”的工作模式，造成開銷率隨節(jié)點(diǎn)規(guī)模的增加而大幅度增加。為方便查看具體折線，特將Spray And Wait、GBP、CIAONR算法折線單獨(dú)在圖6(b)中做比較。

(a) 4種路由算法開銷率對比圖

(b) 3種路由算法開銷率對比圖圖6 固定緩存改變節(jié)點(diǎn)規(guī)模-開銷率

如圖6(b)所示，CIAONR算法在50～400個的節(jié)點(diǎn)規(guī)模中均保持低于9的開銷率，在節(jié)點(diǎn)密度較小的環(huán)境下略高于GBP算法，其原因?yàn)樵谳^稀疏網(wǎng)絡(luò)環(huán)境下進(jìn)行CIAONR算法進(jìn)行了自適應(yīng)的調(diào)整，傳送較多數(shù)據(jù)分組給組外節(jié)點(diǎn)，造成開銷率的上升，當(dāng)節(jié)點(diǎn)規(guī)模達(dá)到300個后，則與GBP算法基本持平，到400個的節(jié)點(diǎn)規(guī)模時較之GBP還有所下降。

圖7為4種路由算法的平均時延趨勢圖，CIAONR算法平均交付時延在各規(guī)模網(wǎng)絡(luò)下均接近Spray And Wait算法的平均時延，低于Epidemic和GBP算法平均時延。在節(jié)點(diǎn)規(guī)模達(dá)到200個以后，其平均時延稍低于Spray And Wait算法，接近最優(yōu)。

圖7 固定緩存改變節(jié)點(diǎn)規(guī)模-平均延遲

由圖5-圖7可知，在固定節(jié)點(diǎn)緩存容量為20 MB的情況下，CIAONR算法的投遞率始終高于另外3種算法，其網(wǎng)絡(luò)開銷在節(jié)點(diǎn)規(guī)模較小的時候雖略高于GBP算法，但在節(jié)點(diǎn)規(guī)模增大的過程中，也不斷接近甚至低于GBP算法。CIAONR算法的平均交付時延在較稀疏網(wǎng)絡(luò)環(huán)境中與Spray And Wait算法接近，始終低于另外2種算法。隨節(jié)點(diǎn)規(guī)模增大其平均時延逐步降低，超過200個的節(jié)點(diǎn)規(guī)模后平均時延低于Spray And Wait算法，接近最優(yōu)。

3.3 固定節(jié)點(diǎn)規(guī)模改變節(jié)點(diǎn)緩存

圖8 固定節(jié)點(diǎn)規(guī)模改變緩存-投遞率

固定節(jié)點(diǎn)規(guī)模為200個，在不同節(jié)點(diǎn)緩存容量的情況下進(jìn)行了算法仿真對比。圖8-圖10是隨著網(wǎng)絡(luò)中節(jié)點(diǎn)緩存容量的增加各路由算法的成功投遞率、網(wǎng)絡(luò)開銷、平均投遞延遲的變化趨勢。通過對比可得，CIAONR算法對節(jié)點(diǎn)緩存容量要求不高，除了容量為10、15 MB時稍有變化，達(dá)到20 MB后折線基本保持水平。仿真顯示，Epidemic算法隨節(jié)點(diǎn)緩存變化各參數(shù)變化較大，Spray And Wait算法在節(jié)點(diǎn)緩存為10 MB時也稍有不穩(wěn)定，CIAONR與GBP算法對節(jié)點(diǎn)緩存容量要求最低。

(a) 4種路由算法開銷率對比圖

(b) 3種路由算法開銷率對比圖圖9 固定節(jié)點(diǎn)規(guī)模改變緩存-開銷率

圖10 固定節(jié)點(diǎn)規(guī)模改變緩存-平均延遲

經(jīng)仿真驗(yàn)證，CIAONR算法較之另外3種算法擁有高且普適的成功投遞率，雖然在節(jié)點(diǎn)密度較小時，網(wǎng)絡(luò)開銷和網(wǎng)絡(luò)延遲略高于GBP和Spray And Wait算法，但其差值小，且隨著節(jié)點(diǎn)規(guī)模增加，迅速得到改善，更適用于實(shí)際的網(wǎng)絡(luò)應(yīng)用。

4 結(jié) 語

通過對實(shí)際網(wǎng)絡(luò)環(huán)境的觀察發(fā)現(xiàn)，移動節(jié)點(diǎn)總是在不同密度網(wǎng)絡(luò)中隨機(jī)切換，因此提出一種基于節(jié)點(diǎn)接觸信息的自適應(yīng)路由算法——CIAONR算法。CIAONR算法充分利用各節(jié)點(diǎn)采集到的接觸信息，依據(jù)CIAONR約束條件自行判斷網(wǎng)絡(luò)環(huán)境并以此指導(dǎo)路由轉(zhuǎn)發(fā)，最終完成交付。仿真實(shí)驗(yàn)驗(yàn)證了CIAONR算法在投遞率方面的顯著提升，網(wǎng)絡(luò)開銷率也控制在較低范圍內(nèi)，未來將在降低網(wǎng)絡(luò)延遲方面做進(jìn)一步研究。

[1] 吳磊, 王曉敏, 劉明,等. 延遲容忍傳感器網(wǎng)絡(luò)中基于群組運(yùn)動的事件傳輸[J]. 軟件學(xué)報(bào), 2012, 23(3): 629-647.

[2] Zhang H Y, Fan W H, Wang L, et al. Real-Time and reliable greedy geographical routing for mobile wireless sensor networks[J]. Journal of Computer Research and Development, 2009, 46(5): 713-722 (in Chinese with English abstract).

[3] 張三峰, 黃迪, 陳州. 一種面向機(jī)會網(wǎng)絡(luò)路由的最優(yōu)停止決策方法[J]. 軟件學(xué)報(bào), 2014, 25(6): 1291-1300.

[4] 馬華東, 袁培燕, 趙東. 移動機(jī)會網(wǎng)絡(luò)路由問題研究進(jìn)展[J]. 軟件學(xué)報(bào), 2015, 26(3): 600- 616.

[5] 任智, 劉智虎, 姚玉坤. 基于網(wǎng)絡(luò)編碼的機(jī)會網(wǎng)絡(luò)高效路由算法[J]. 通信學(xué)報(bào), 2013, 34(9): 16-23.

[6] 楊帆, 來嘉哲. 基于分組的DTN路由協(xié)議[J]. 電子測量技術(shù), 2015, 38(10): 144-148.

[7] 譚紫逸, 陳志剛, 吳嘉,等. 機(jī)會網(wǎng)絡(luò)多跳節(jié)點(diǎn)最小傳輸延遲算法設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(8):2458-2461.

[8] 姚玉坤, 張強(qiáng), 楊及開. 基于社會組的高投遞率機(jī)會網(wǎng)絡(luò)路由協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(2):577-581.

[9] Chen K, Shen H. SMART: Lightweight distributed Social Map based Routing in Delay Tolerant Networks[C]// IEEE International Conference on Network Protocols. IEEE Computer Society, 2012:1-10.

[10] Bulut E, Szymanski B. Exploiting friendship relations for efficient routing in mobile social networks[J]. IEEE Trans. On Parallel and Distributed Systems, 2012, 23(12): 2254-2265.

[11] 任智, 譚永銀, 索建偉,等. 一種基于旁聽的機(jī)會網(wǎng)絡(luò)路由算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(11):3396-3400.

[12] Zhang X, Neglia G, Kurose J, et al. Performance modeling of epidemic routing[J]. Computer Networks, 2007, 51(10): 2867-2891.

[13] Chaintreau A, Hui P, Crowcroft J, et al. Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms[C]// INFOCOM 2006. IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain. DBLP, 2006:1-13.

[14] Karagiannis T, Boudec J Y L, Vojnovic M. Power Law and Exponential Decay of Intercontact Times between Mobile Devices[J]. IEEE Transactions on Mobile Computing, 2010, 9(10):1377-1390.

[15] 程剛, 張?jiān)朴? 張勇. 基于人類真實(shí)場景的分時段的機(jī)會網(wǎng)絡(luò)移動模型[J]. 通信學(xué)報(bào), 2013, 34(S1): 182-189.

[16] 蔡青松, 牛建偉, 劉燕. 機(jī)會網(wǎng)絡(luò)中的消息傳輸路徑特性研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(5): 793-801.

[17] Tie X,Venkataramani A,Balasubramanian A.R3:robust replication routing in wireless networks with diverse connectivity characteristics[C]//International Conference on Mobile Computing and Networking, MOBICOM 2011, Las Vegas, Nevada, Usa, September. 2011:181-192.

ADAPTIVE OPPORTUNITY NETWORK ROUTING ALGORITHM BASED ON THE CONTACT INFORMATION

Wu Shuyan Han Yigang Fu Qiuyu Feng Fei

(CollegeofElectronicInformationandOpticalEngineering,NankaiUniversity,Tianjin300350,China)

Considering the constantly changes in the actual network environment and the characteristics of opportunity networks nodes which always switch stochastically between dense and sparse scene, an adaptive routing algorithm called CIAONR which can judge the network environment with the node contact information is proposed. CIAONR uses nodes’ contact delay and lifetime to determine the network environment in which the nodes are located during the process of collecting the contact information. Then, according to the CIAONR constraints, the choice of the forwarding path is guided, and finally the message delivery is completed according to the corresponding interaction flow. Theoretical analysis and simulation results show that the CIAONR maintains a high delivery rate in different network environments, and the network overhead and delay are also controlled within a certain range, which has a universal effect.

Opportunity network Routing algorithm Contact information Adaptive

2016-07-01。武淑艷，碩士生，主研領(lǐng)域：計(jì)算機(jī)通信網(wǎng)絡(luò)，內(nèi)容中心網(wǎng)絡(luò)，機(jī)會網(wǎng)絡(luò)。韓毅剛，副教授。傅秋宇，碩士生。馮飛，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2017.07.019