王恩，楊永健，趙衛(wèi)丹，劉林璐

（1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130012；2.吉林大學(xué) 軟件學(xué)院，吉林 長(zhǎng)春 130012）

1 引言

Fall[1]在國(guó)際會(huì)議 SIGCOMM 上最早提出了容遲網(wǎng)絡(luò)（DTN）[2，3]這一概念。其長(zhǎng)延時(shí)，節(jié)點(diǎn)資源有限，間歇性連接，不對(duì)稱傳輸速率，信噪比低等特點(diǎn)使針對(duì)這種網(wǎng)絡(luò)環(huán)境提出一種良好的路由算法[4，5]成為當(dāng)前的研究熱點(diǎn)。

早期的關(guān)于容遲網(wǎng)絡(luò)路由算法提出了一種單副本路由協(xié)議[6]，同一時(shí)間在網(wǎng)絡(luò)中只保留特定消息的一個(gè)副本，該路由方式開(kāi)銷低，資源利用率高，但通常交付延遲較大，而且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化導(dǎo)致傳輸不可靠。因此提出了基于多拷貝的路由協(xié)議，Epidemic[7]是一種以病毒感染的方式在網(wǎng)絡(luò)中擴(kuò)散消息的多副本路由策略，這種方式消耗了大量的網(wǎng)絡(luò)資源而導(dǎo)致實(shí)際應(yīng)用中該路由協(xié)議性能隨時(shí)間增加而明顯降低。為了控制消息泛洪帶來(lái)的資源消耗，提出了基于固定配額的多拷貝路由協(xié)議[8]，其中比較經(jīng)典的是spray and wait[9]路由協(xié)議。這些經(jīng)典的路由協(xié)議可以直接應(yīng)用到社會(huì)網(wǎng)絡(luò)中，但是隨著節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)中冗余副本數(shù)顯著提高，導(dǎo)致網(wǎng)絡(luò)負(fù)載過(guò)大，節(jié)點(diǎn)緩存擁塞[10]等現(xiàn)象時(shí)常發(fā)生。

近年來(lái)，隨著無(wú)線通信技術(shù)日趨成熟，通信設(shè)備的體積不斷縮小，以人攜帶通信設(shè)備的方式形成了諸如體域網(wǎng)、校園網(wǎng)絡(luò)[11]等網(wǎng)絡(luò)環(huán)境，由于節(jié)點(diǎn)的移動(dòng)受人類活動(dòng)的影響，節(jié)點(diǎn)間的通信不再單純地依靠隨機(jī)的相遇來(lái)完成，而是與彼此的社會(huì)關(guān)系（如親人、同事、朋友）產(chǎn)生了密不可分的聯(lián)系，這使容遲網(wǎng)絡(luò)體現(xiàn)出了經(jīng)典的“小世界現(xiàn)象”，即節(jié)點(diǎn)間可以依據(jù)其社會(huì)屬性通過(guò)一跳或幾跳與其他節(jié)點(diǎn)產(chǎn)生聯(lián)系，社會(huì)關(guān)系親密的節(jié)點(diǎn)間會(huì)表現(xiàn)出良好的數(shù)據(jù)通信能力。這樣在容遲網(wǎng)絡(luò)中挖掘出節(jié)點(diǎn)間的社會(huì)關(guān)系，以應(yīng)用到路由的選擇策略中就成了近期比較熱門的研究課題，研究人員就如何劃分社交網(wǎng)絡(luò)已經(jīng)提出了很多社交圈（社交簇）的挖掘方法：文獻(xiàn)[12]通過(guò)聚類方法抽取網(wǎng)絡(luò)的層次結(jié)構(gòu)，定義了一套社會(huì)網(wǎng)絡(luò)的標(biāo)注密度估計(jì)函數(shù)，通過(guò)該函數(shù)進(jìn)行網(wǎng)絡(luò)層次上的聚合操作，進(jìn)而提出了基于密度估計(jì)的社會(huì)網(wǎng)絡(luò)特征簇挖掘方法；文獻(xiàn)[13]通過(guò)研究Web鏈接結(jié)構(gòu)，使用最大流—最小割定理思想對(duì)社區(qū)進(jìn)行劃分，將網(wǎng)絡(luò)模型化為信息流通的信道和關(guān)節(jié)，進(jìn)而劃分出社區(qū)邊界；文獻(xiàn)[14]中，林友芳等人提出了邊穩(wěn)定系數(shù)模型和完全信息圖模型，在此基礎(chǔ)上設(shè)計(jì)和實(shí)現(xiàn)了一種有效的社區(qū)發(fā)現(xiàn)算法。

在容遲網(wǎng)絡(luò)的路由策略中引入社交圈的挖掘方法，已經(jīng)提出了很多性能較好的路由方法。文獻(xiàn)[15]通過(guò)將移動(dòng)規(guī)律相近的節(jié)點(diǎn)聚合成最近社交圈策略，提出了一種基于分簇的簇外噴射、簇間轉(zhuǎn)發(fā)和簇內(nèi)傳染3階段社交時(shí)延網(wǎng)絡(luò)路由協(xié)議；在文獻(xiàn)[16]中，周瑞濤等人通過(guò)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)歷史運(yùn)動(dòng)軌跡點(diǎn)聚類建立其熱點(diǎn)活動(dòng)區(qū)域，把熱點(diǎn)區(qū)域重疊度較高的節(jié)點(diǎn)歸為同一社區(qū)。在源節(jié)點(diǎn)和目的節(jié)點(diǎn)社區(qū)中以洪泛的方式加快消息擴(kuò)散和傳遞速度。針對(duì)不同社區(qū)準(zhǔn)確的選擇中繼節(jié)點(diǎn)。文獻(xiàn)[17]中于海征等人利用社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)間的權(quán)值計(jì)算方法，計(jì)算出團(tuán)隊(duì)間的關(guān)系強(qiáng)度矩陣。消息源節(jié)點(diǎn)的團(tuán)隊(duì)依據(jù)關(guān)系強(qiáng)度矩陣選擇適合節(jié)點(diǎn)作為中繼向目的節(jié)點(diǎn)傳遞消息，考慮到了自私節(jié)點(diǎn)對(duì)傳遞的影響，提出了基于社會(huì)網(wǎng)絡(luò)的可靠路由方法。

本文提出了以節(jié)點(diǎn)間相遇頻率和節(jié)點(diǎn)間的通信時(shí)長(zhǎng)為依據(jù)來(lái)確定節(jié)點(diǎn)之間親密度的方法，克服了以往研究中只以相遇次數(shù)等[18]信息來(lái)確定節(jié)點(diǎn)關(guān)系的不準(zhǔn)確性，同時(shí)本文利用節(jié)點(diǎn)親密度的拓?fù)淙珗D動(dòng)態(tài)生成親密關(guān)系樹(shù)，能夠動(dòng)態(tài)適應(yīng)節(jié)點(diǎn)之間關(guān)系的變化情況，通過(guò)對(duì)樹(shù)結(jié)構(gòu)的有效裁剪找到關(guān)系緊密的節(jié)點(diǎn)分組，應(yīng)用該分組來(lái)進(jìn)行容遲網(wǎng)絡(luò)中的路由，有效地克服了以往路由算法選擇下一跳的盲目性，進(jìn)一步提高了基于節(jié)點(diǎn)間親密度的分組路由方法PBI的性能。

2 網(wǎng)絡(luò)模型定義

2.1 基于節(jié)點(diǎn)親密度的拓?fù)淠Ｐ?/h3>

通常意義上的容遲網(wǎng)絡(luò)模型很難用以往的如G=(V，E)的形式來(lái)表示，其中V是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為邊集。主要原因是其中節(jié)點(diǎn)的高移動(dòng)性導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化，點(diǎn)和點(diǎn)之間的邊連接不夠穩(wěn)定，權(quán)值很難準(zhǔn)確表示。但在社會(huì)網(wǎng)絡(luò)下由于節(jié)點(diǎn)間存在某種社會(huì)關(guān)系，他們之間確實(shí)存在某種特定且相對(duì)穩(wěn)定的聯(lián)系[19]，如同事之間會(huì)在同一時(shí)間來(lái)到單位，在同一時(shí)間吃午飯，在同一時(shí)間下班。公交車司機(jī)會(huì)沿著固定的路線，有周期地在地圖上移動(dòng)。校園中老師每周的課時(shí)不變，每節(jié)課上課的時(shí)間都會(huì)與特定的學(xué)生相遇等。由于這些人所帶有的特定社會(huì)屬性，導(dǎo)致他們之間的相遇并非偶然，存在著極強(qiáng)的規(guī)律性，挖掘出這樣的社會(huì)關(guān)系對(duì)在社會(huì)時(shí)延網(wǎng)絡(luò)下的路由算法有很大幫助，基于以上考慮定義網(wǎng)絡(luò)拓?fù)淠Ｐ腿缦隆?/p>

定義1G=(V，E)為網(wǎng)絡(luò)拓?fù)鋱D，其中V為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為定義在G上的邊集。節(jié)點(diǎn)u，v∈V，eu，v∈E表示節(jié)點(diǎn)u和v之間的邊，W(eu，v)表示eu，v的大小，在此特殊定義為節(jié)點(diǎn)間的親密度。

通常對(duì)容遲網(wǎng)絡(luò)中節(jié)點(diǎn)之間關(guān)系的研究只是將其簡(jiǎn)單地定義為相遇次數(shù)，或者直接將其簡(jiǎn)化為如果有聯(lián)系就將邊的權(quán)值設(shè)置為 1，否則為 0，這些對(duì)邊權(quán)值的簡(jiǎn)化必然會(huì)導(dǎo)致模型表達(dá)的準(zhǔn)確性下降，如圖1所示。

圖1 相遇情況

圖1中表示了網(wǎng)絡(luò)中2個(gè)節(jié)點(diǎn)在T時(shí)間內(nèi)的4種相遇情況，如果單純地用相遇次數(shù)來(lái)定義節(jié)點(diǎn)之間的聯(lián)系強(qiáng)度，則4種情況對(duì)應(yīng)的邊的權(quán)值分別為2、4、1、1。即做如下判斷：情況2下節(jié)點(diǎn)之間聯(lián)系最緊密，情況3和情況4節(jié)點(diǎn)聯(lián)系強(qiáng)度相同，顯然這樣的判斷不夠準(zhǔn)確，沒(méi)有考慮每次節(jié)點(diǎn)之間的通信時(shí)長(zhǎng)，在某種情況下相遇的節(jié)點(diǎn)未必通信，而通信時(shí)間的長(zhǎng)短往往更能夠反應(yīng)兩節(jié)點(diǎn)社會(huì)關(guān)系的緊密強(qiáng)弱，故提出節(jié)點(diǎn)之間親密度模型。

定義 2節(jié)點(diǎn)u，v∈V，eu，v∈E表示節(jié)點(diǎn)u和v之間的邊，W(eu，v)表示表示節(jié)點(diǎn)u和v的節(jié)點(diǎn)間親密度，n表示在統(tǒng)計(jì)的T時(shí)間內(nèi)u和v的相遇總次數(shù)，Tk表示第K次相遇的通話時(shí)長(zhǎng)，Bk表示第K次斷開(kāi)的時(shí)間長(zhǎng)度。W(eu，v)的計(jì)算通過(guò)圖2所示，Ok表示第K次通話開(kāi)始時(shí)所對(duì)應(yīng)的節(jié)點(diǎn)間通信能力，Yk表示第K次通話結(jié)束時(shí)節(jié)點(diǎn)間的通信能力。其中增長(zhǎng)和下降的斜率定義為增長(zhǎng)系數(shù)α和阻尼系數(shù)β，為了簡(jiǎn)化模型，將α和β值設(shè)置為1。

圖2 節(jié)點(diǎn)間通信能力

本文認(rèn)為節(jié)點(diǎn)間持續(xù)的通信說(shuō)明節(jié)點(diǎn)間有著較強(qiáng)的通信能力，長(zhǎng)時(shí)間的通信斷開(kāi)會(huì)導(dǎo)致通信能力下降，當(dāng)下降為0時(shí)就停止下降，等待下一次通信的開(kāi)始，而圖2中陰影部分的面積即表示節(jié)點(diǎn)間的親密度可由式(3)得到，Tk和Bk均由統(tǒng)計(jì)量得到，O1=0，Y1=T1。

應(yīng)用以上節(jié)點(diǎn)間親密度模型，對(duì)圖1數(shù)據(jù)進(jìn)行分析得到4種相遇情況所對(duì)應(yīng)的通信能力如圖3所示，根據(jù)圖3計(jì)算得到節(jié)點(diǎn)間親密度在這4種情況下分別為，從數(shù)據(jù)可以看出這樣的節(jié)點(diǎn)間親密度定義更能準(zhǔn)確地反應(yīng)出節(jié)點(diǎn)之間的社會(huì)關(guān)系，情況3下由于其長(zhǎng)時(shí)間通信而導(dǎo)致其親密性最高，而情況4的通信時(shí)間較短，且斷開(kāi)時(shí)間較長(zhǎng)，導(dǎo)致其親密性最低。

圖3 不同相遇情況下的通信能力

2.2 親密關(guān)系樹(shù)模型

為了簡(jiǎn)化網(wǎng)絡(luò)模型，以 5個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)為例，根據(jù)定義 1，網(wǎng)絡(luò)中可以生成一張完全帶權(quán)拓?fù)鋱D（如圖4所示），其中節(jié)點(diǎn)之間的邊的權(quán)值表示親密度，由定義2得到。依據(jù)這樣的拓?fù)鋱D，通過(guò)算法1[20]可以生成一棵親密關(guān)系樹(shù)（如圖5所示），該算法與文獻(xiàn)[20]的分組算法執(zhí)行流程相同,但是分組的依據(jù)有截然的區(qū)別,即本文提出的帶權(quán)拓?fù)鋱D中的權(quán)重能很好地顯示節(jié)點(diǎn)間通信的能力,進(jìn)而幫助容遲網(wǎng)絡(luò)環(huán)境下報(bào)文的路由,在這里特殊強(qiáng)調(diào)的是其中特殊標(biāo)注的節(jié)點(diǎn)為算法中每次隨機(jī)選取獲得的節(jié)點(diǎn)。

海明威在其創(chuàng)作中一直遵循年輕時(shí)形成的“電報(bào)體風(fēng)格”，在其作品《午后之死》中也正式提出了他在創(chuàng)作上的“冰山原則”。海明威以冰山為喻，表達(dá)了作者只應(yīng)描寫(xiě)冰山露出水面的一小部分，而隱藏于水下的則應(yīng)該通過(guò)文字的延伸由讀者去想象補(bǔ)充這一主張。本文通過(guò)解讀《老人與?！?，分析小說(shuō)的文體風(fēng)格及人物塑造來(lái)探究“冰山原則”的獨(dú)特之處。

圖4 網(wǎng)絡(luò)帶權(quán)拓?fù)?/p>

圖5 樹(shù)結(jié)構(gòu)

這樣通過(guò)算法1自底向上生成了一棵親密關(guān)系二叉樹(shù)，網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)為n，則這棵親密關(guān)系樹(shù)的非葉子節(jié)點(diǎn)個(gè)數(shù)為n-1，這樣就應(yīng)用節(jié)點(diǎn)間親密度模型找到了網(wǎng)絡(luò)中n-1個(gè)關(guān)系緊密的分組集合，特別注意的是第6)和8)步中每次選取剩余集合中內(nèi)部平均親密度最高的集合成為Gk，這主要是考慮讓社會(huì)關(guān)系緊密的圈子盡可能多地吸納進(jìn)節(jié)點(diǎn)，以保證算法得到的集合內(nèi)部社會(huì)關(guān)系強(qiáng)度遠(yuǎn)高于集合外部，從某種意義上也防止由于過(guò)分隨機(jī)選取集合而導(dǎo)致分組的差異行和不合理性，為了防止內(nèi)部親密度過(guò)高的分組較多，這些分組不愿意和外部集合成組，而導(dǎo)致算法在 2)、3)、4)、6)中循環(huán)，無(wú)法建立起一顆完整二叉樹(shù)，所以在3)中加入了親密度W(Gi，Gj)均小于W(Vk)的判斷，然后跳到9)中完成親密關(guān)系樹(shù)的建立。

2.3 基于節(jié)點(diǎn)親密關(guān)系樹(shù)的分組裁剪模型[20]

根據(jù)算法 1，親密關(guān)系樹(shù)中的所有非葉子節(jié)點(diǎn)均存放在M集合中，因?yàn)橥ㄟ^(guò)算法1得到了大量具有親密關(guān)系的節(jié)點(diǎn)分組，所以這些集合中不免存在一些相互之間親密關(guān)系較弱的分組，同時(shí)也存在著一些彼此之間具有包含關(guān)系的分組，因此需要對(duì)得到的集合進(jìn)行裁剪，以挑選出那些彼此之間沒(méi)有包含關(guān)系，并且集合內(nèi)部具有較強(qiáng)親密度的分組。

將集合M中的所有元素（集合）內(nèi)部的關(guān)系親密度值進(jìn)行由大到小排序，將后一半親密度比較小的分組從集合M中刪除出去，這里選擇刪除后一半主要是通過(guò)多次實(shí)驗(yàn)發(fā)現(xiàn)親密度較高的前一半分組即可覆蓋網(wǎng)絡(luò)中多數(shù)節(jié)點(diǎn)，所以刪除后一半既能保證留下的分組都具有較高的關(guān)系親密度，同時(shí)又能保證網(wǎng)絡(luò)覆蓋度。接下來(lái)遍歷剩余的集合M，如果M中的某一個(gè)分組M1被M中其他某一分組所包含，則將M1從M中刪除，則剩余的集合M中分組之間不存在包含關(guān)系，利用基于節(jié)點(diǎn)間親密度的分組方法得到了網(wǎng)絡(luò)中親密度較高的所有分組。

3 基于節(jié)點(diǎn)間親密度的分組路由方法PBI

文中借鑒基于配額的經(jīng)典路由方法 spray and wait，該路由方法將消息傳輸過(guò)程分為spray 和wait階段，在消息產(chǎn)生的時(shí)候就確定了消息的固定配額數(shù)，在spray階段每當(dāng)攜帶報(bào)文的節(jié)點(diǎn)遇到其他沒(méi)有該消息的節(jié)點(diǎn)時(shí)，就將自己報(bào)文總數(shù)的一半分給這個(gè)節(jié)點(diǎn)，自己保留一半，當(dāng)節(jié)點(diǎn)剩余的報(bào)文數(shù)量為1時(shí)spray階段結(jié)束，該節(jié)點(diǎn)進(jìn)入wait階段，即等待該報(bào)文的目標(biāo)節(jié)點(diǎn)出現(xiàn)，否則一直攜帶該報(bào)文。為了克服spray 階段的盲目性，和wait階段的保守性，結(jié)合基于節(jié)點(diǎn)親密關(guān)系樹(shù)的分組裁剪模型得到的分組，提出了基于節(jié)點(diǎn)間親密度的分組路由方法(PBI)。

算法2基于親密度的路由算法

基于節(jié)點(diǎn)間親密度的分組路由方法源節(jié)點(diǎn)A，相遇節(jié)點(diǎn)B，目的節(jié)點(diǎn)C

基于節(jié)點(diǎn)間親密度的分組路由方法與spray and wait算法一樣分為2個(gè)階段，在散發(fā)階段首先判斷相遇節(jié)點(diǎn)B和目的節(jié)點(diǎn)C是否在一個(gè)分組中，如果在則將源節(jié)點(diǎn)A本身的拷貝數(shù)的一半分給B，這樣做加強(qiáng)了不同分組之間的報(bào)文散發(fā)，防止由于傳統(tǒng)spray and wait中，具有相同運(yùn)動(dòng)規(guī)律的節(jié)點(diǎn)間形成的封閉性，導(dǎo)致一些報(bào)文在一些固定的節(jié)點(diǎn)間傳播而無(wú)法發(fā)送到目的節(jié)點(diǎn)。另外將報(bào)文散發(fā)給與目的節(jié)點(diǎn)在一個(gè)分組內(nèi)的節(jié)點(diǎn)，也有效增強(qiáng)了報(bào)文的投遞概率。在等待階段，不是被動(dòng)地等待目的節(jié)點(diǎn)的出現(xiàn)，當(dāng)遇到和目的節(jié)點(diǎn)在一個(gè)分組內(nèi)的節(jié)點(diǎn)時(shí)，首先判斷自己和目的節(jié)點(diǎn)是否在一個(gè)分組，如果不在，則將自己的唯一一份報(bào)文交付給相遇節(jié)點(diǎn)，如果自己和目的節(jié)點(diǎn)在一個(gè)分組內(nèi)，則將自己的唯一一份報(bào)文復(fù)制一份給相遇節(jié)點(diǎn)，自己也留一份，這樣做主要是為了增強(qiáng)主動(dòng)路由過(guò)程，通過(guò)將報(bào)文迅速地投遞到目的節(jié)點(diǎn)的分組，盡力交付報(bào)文。實(shí)驗(yàn)證明基于節(jié)點(diǎn)間親密度的分組路由方法 PBI增強(qiáng)了投遞成功率，減小了平均網(wǎng)絡(luò)時(shí)延，更說(shuō)明親密度的計(jì)算模型以及依據(jù)親密度的分組方法的準(zhǔn)確性。

綜上所述，基于節(jié)點(diǎn)間親密度的分組路由方法PBI在spray and wait路由方法的基礎(chǔ)上進(jìn)行改進(jìn)，首先定義節(jié)點(diǎn)間親密度的概念，依據(jù)節(jié)點(diǎn)間親密度生成整個(gè)網(wǎng)絡(luò)的帶權(quán)拓?fù)鋱D，在其上引入之前的分組方法得到彼此之間親密度較高的節(jié)點(diǎn)分組，進(jìn)而在將spray and wait路由方法與節(jié)點(diǎn)分組結(jié)合得到效率更高的基于節(jié)點(diǎn)間親密度的分組路由方法。在 ONE模擬器中對(duì)PBI、spray and wait以及Epidemic 3種路由方法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明在不同的報(bào)文副本數(shù)，本地緩存以及報(bào)文生成速率的條件下PBI在投遞成功率和平均時(shí)延方面取得了更好的路由性能。

4 實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

表1 參數(shù)說(shuō)明

本文實(shí)驗(yàn)部分分為2個(gè)階段：熱啟動(dòng)階段和路由階段。故將仿真時(shí)間設(shè)置為10 000 s，前5 000 s節(jié)點(diǎn)在地圖上遵循既定的移動(dòng)模型，運(yùn)用基于節(jié)點(diǎn)親密度的拓?fù)淠Ｐ蜕捎H密關(guān)系樹(shù)，通過(guò)分組裁剪方法裁剪出有利于路由算法的親密關(guān)系分組。從第5 000 s開(kāi)始產(chǎn)生報(bào)文，將文中提出的基于節(jié)點(diǎn)間親密度的分組路由方法PBI應(yīng)用到仿真環(huán)境中，通過(guò)分別改變節(jié)點(diǎn)本地緩存的大小、報(bào)文初始副本數(shù)以及報(bào)文的生成速率這3個(gè)參數(shù)來(lái)觀測(cè)路由算法的性能，與Epidemic、spray and wait 2種經(jīng)典路由協(xié)議對(duì)比，從以下2個(gè)方面評(píng)估PBI協(xié)議。

投遞概率=成功投遞到目的節(jié)點(diǎn)的報(bào)文數(shù)量/網(wǎng)絡(luò)中產(chǎn)生的報(bào)文總數(shù)

時(shí)延均值=消息到達(dá)目的節(jié)點(diǎn)的平均時(shí)間

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

本文的仿真部分主要進(jìn)行3組實(shí)驗(yàn)，分別在不同的本地緩存、報(bào)文副本數(shù)以及報(bào)文生成速率的網(wǎng)絡(luò)環(huán)境下測(cè)試 PBI、Epidemic以及 spray and wait的路由性能。之所以選擇更改這3個(gè)網(wǎng)絡(luò)條件主要是基于以下考慮：本地緩存的大小能夠影響路由算法的性能，準(zhǔn)確的路由方法即使在較小的緩存空間下依然能夠取得很好的投遞效果。報(bào)文副本數(shù)能夠影響spray and wait和PBI的感染范圍。報(bào)文生成速率可以影響網(wǎng)絡(luò)擁塞程度，進(jìn)而影響路由結(jié)果。

第1組實(shí)驗(yàn)，將報(bào)文的初始副本數(shù)設(shè)為4，報(bào)文的生成速率為[15，25]即每隔(15～25) s的時(shí)間生成一個(gè)報(bào)文，改變節(jié)點(diǎn)本地緩存大小，在10 MB、20 MB、30 MB、50 MB、100 MB情況下，與spray and wait和Epidemic 2種路由協(xié)議相比，投遞成功率變化情況如圖6所示，平均時(shí)延變化情況如圖7所示。

圖6 不同緩存下的投遞成功率

圖7 不同緩存下的平均時(shí)延

圖6中數(shù)據(jù)顯示，在緩存較小的情況下（10 MB，20 MB），PBI表現(xiàn)出良好的投遞性能，這主要是因?yàn)槲闹刑岢龅姆纸M方法大幅度減小了由于spray and wait盲目投遞所造成的緩存和帶寬的浪費(fèi)。尤其是緩存不足的時(shí)候這種提升會(huì)更加明顯，這主要是因?yàn)榫彺婵臻g有限時(shí)，節(jié)點(diǎn)能夠攜帶的報(bào)文數(shù)量有限，因此容易發(fā)生報(bào)文的丟棄現(xiàn)象，只有提升路由方法的準(zhǔn)確性才能得到投遞成功率的提升。當(dāng)緩存增大到50 MB以后，Epidemic的投遞成功率顯著提升，這主要是緩存大小趨于理想化，即使通過(guò)泛洪方式路由，網(wǎng)絡(luò)也不會(huì)發(fā)生擁塞，導(dǎo)致Epidemic有很高的投遞成功率，同時(shí)也容易看出PBI隨著緩存增大依然保持著很好的投遞效果，在100 MB緩存的情況下依然可以擁有和Epidemic持平的投遞成功率。圖7中數(shù)據(jù)顯示PBI的平均時(shí)延小于另外2種路由方法，差值平均在100 s左右，尤其是在緩存較小時(shí)效果明顯，更說(shuō)明PBI很好地改善了路由性能。

第2組實(shí)驗(yàn)，將節(jié)點(diǎn)的緩存大小設(shè)置為100 MB，報(bào)文的生成速率同樣為[15， 25]，改變報(bào)文的初始副本數(shù)，在2、4、6、8這4種情況下，與spray and wait和Epidemic 2種路由協(xié)議相比，投遞成功率變化情況如圖8所示，平均時(shí)延變化情況如圖9所示。

圖8 不同報(bào)文副本數(shù)下的投遞成功率

從圖8中數(shù)據(jù)可以得出如下結(jié)論：在緩存較大情況下，PBI有著與Epidemic不分伯仲的投遞成功率，并且這個(gè)概率值平均比 spray and wait高出20%，當(dāng)節(jié)點(diǎn)的初始copies數(shù)越小的時(shí)候，PBI的路由性能越明顯，經(jīng)分析這主要是因?yàn)樵趙ait階段PBI中引入了主動(dòng)路由過(guò)程，拋棄了被動(dòng)等待目的節(jié)點(diǎn)出現(xiàn)的保守行為，取得了路由性能上的提高。另外準(zhǔn)確的分組方法，能夠使持有報(bào)文的節(jié)點(diǎn)更清楚哪些節(jié)點(diǎn)能夠很好地幫助路由過(guò)程，避免無(wú)意義的報(bào)文傳輸，因此能夠通過(guò)組內(nèi)和組間的合作完成報(bào)文的投遞。圖9中數(shù)據(jù)表明PBI在不同的報(bào)文初始副本數(shù)的情況下，其網(wǎng)絡(luò)平均時(shí)延均小于另外 2種路由方法，并且其時(shí)延均值穩(wěn)定在一個(gè)較低的范圍內(nèi)，不會(huì)大幅度波動(dòng)。

圖9 不同報(bào)文副本數(shù)下的平均時(shí)延

第3組實(shí)驗(yàn)，同樣將節(jié)點(diǎn)的緩存大小設(shè)置為100 MB，報(bào)文的初始副本數(shù)同樣設(shè)為4，改變報(bào)文的生成速率，在[5，15]、[15，25]、[25，35]、[35，45]這4種情況下，與spray and wait 和Epidemic 2種路由協(xié)議相比，投遞成功率變化情況如圖10所示，平均時(shí)延變化情況如圖11所示。

圖10 不同報(bào)文生成速率下的投遞成功率

圖11 不同報(bào)文生成速率下的平均時(shí)延

圖 10中數(shù)據(jù)表明，在報(bào)文生成速率較高的情況下([5～15])，PBI的投遞成功率比另外2種都要高，主要是因?yàn)檫^(guò)多的報(bào)文導(dǎo)致了 Epidemic的擁塞發(fā)生，過(guò)多的報(bào)文因?yàn)榫彺嬉绯龆鴣G棄，因此報(bào)文生成速率越高，溢出發(fā)生的可能性就越大，進(jìn)而使其投遞率隨時(shí)間增長(zhǎng)而下降，當(dāng)報(bào)文的生成速率較低時(shí)，緩存擁塞得到了緩解，因此此時(shí)PBI和Epidemic的投遞成功率相近。圖 11中數(shù)據(jù)同樣可以看出在報(bào)文生成速率較高情況下，Epidemic的平均時(shí)延最高，同樣是因?yàn)閳?bào)文的大量丟棄延長(zhǎng)了報(bào)文到達(dá)的平均時(shí)間，進(jìn)而證明確實(shí)發(fā)生了嚴(yán)重的擁塞，隨著報(bào)文生成速率的下降，Epidemic的平均時(shí)延平穩(wěn)降低，但是PBI的平均時(shí)延一直低于另外2種路由方法。

綜上所述，PBI路由方法提高了路由的投遞成功率，減小了網(wǎng)絡(luò)的平均時(shí)延。在不同的報(bào)文副本數(shù)、本地緩存以及報(bào)文生成速率的條件下與Epidemic和spray and wait相比均得到了較好的路由性能。經(jīng)過(guò)分析主要是因?yàn)镋pidemic局限于緩存的約束，當(dāng)緩存較小時(shí)會(huì)發(fā)生擁塞現(xiàn)象，而spray and wait路由方法的spray階段存在盲目性，wait階段的被動(dòng)等待使其損失了大量的投遞機(jī)會(huì)，而PBI很好地解決了以上問(wèn)題，首先PBI在spray and wait上進(jìn)行改進(jìn)，就已經(jīng)限制了報(bào)文的蔓延上限，而PBI通過(guò)節(jié)點(diǎn)親密度的計(jì)算結(jié)果進(jìn)行分組，使彼此通信機(jī)會(huì)良好的節(jié)點(diǎn)進(jìn)入同一分組，依據(jù)該分組結(jié)果進(jìn)行組內(nèi)和組間的報(bào)文散發(fā)，因此取得了最好的投遞效果。

5 結(jié)束語(yǔ)

容遲網(wǎng)絡(luò)環(huán)境下由于節(jié)點(diǎn)的移動(dòng)性較強(qiáng)，節(jié)點(diǎn)間連接頻繁中斷，導(dǎo)致該網(wǎng)絡(luò)環(huán)境下節(jié)點(diǎn)以“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的方式進(jìn)行報(bào)文投遞，傳統(tǒng)的TCP/IP協(xié)議不再適用于該網(wǎng)絡(luò)環(huán)境，因而在該網(wǎng)絡(luò)環(huán)境下的報(bào)文路由問(wèn)題一直是當(dāng)今研究領(lǐng)域的前沿問(wèn)題。本文在容遲網(wǎng)絡(luò)環(huán)境中通過(guò)定義節(jié)點(diǎn)之間的親密度模型形成了一張整個(gè)網(wǎng)絡(luò)的帶權(quán)拓?fù)鋱D，依據(jù)親密關(guān)系樹(shù)生成模型挖掘出一些內(nèi)部有親密關(guān)系的分組，通過(guò)裁剪方法得到了互相之間沒(méi)有包含關(guān)系的節(jié)點(diǎn)分組，利用該分組信息進(jìn)行容遲網(wǎng)絡(luò)中的路由算法決策，提出了基于節(jié)點(diǎn)間親密度的分組路由方法 PBI，實(shí)驗(yàn)表明 PBI與 spray and wait 和Epidemic 2種路由方法相比大幅度提高投遞成功率，并且減小網(wǎng)絡(luò)平均時(shí)延。在接下來(lái)的工作中，計(jì)劃取消熱啟動(dòng)階段，將節(jié)點(diǎn)的分組挖掘過(guò)程滲透進(jìn)路由方法中，動(dòng)態(tài)地完成親密關(guān)系分組的挖掘，即通過(guò)網(wǎng)絡(luò)信息的搜集動(dòng)態(tài)地進(jìn)行路由決策，進(jìn)而通過(guò)實(shí)驗(yàn)驗(yàn)證想法的可行性。

[1] FALL K. A delay-tolerant network architecture for challenged Internets[A]. Proc of the ACM SIGCOMM[C]. 2003.27-34.

[2] BURLEIGH S， HOOKE A， TORGERSON L，et al. Delay tolerant networking： an approach to interplanetary internet[J]. IEEE Communications Magazine， 2003.41(6)：128-136.

[3] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y，et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8)： 102-114.

[4] JONES E， WARD P. Routing strategies for delay-tolerant networks[A]. Proc of International Conference on Wireless Communications and Mobile Computing[C].2006.

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

[6] JAIN S， FALL K， PATRA R. Routing in delay tolerant network[A].Proc of SIGCOMM[C]. New York： ACM Press， 2004.145-157.

[7] VAHDAT A， BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Duke University， 2000.

[8] TANG L， ZHENG Q， LIU J，et al. SMART： A selective controlled-flooding routing for delay tolerant networks[A]. Fourth International Conference on IEEE Broadband Communications， Networks and Systems[C]. 2007.356-365.

[9] SOYROPOULOS T， PSOUNIS K， RAGHAVENDRA C S. Spray and wait： an efficient routing scheme for intermittently connected mobile networks[A]. Proc of the ACM SIGCOMM Workshop on Delay-Tolerant Networking[C]. 2005.252-259.

[10] 王恩， 楊永健， 李蒞. DTN 中基于生命游戲的擁塞控制策略[J]. 計(jì)算機(jī)研究與發(fā)展， 2014， 51(11)： 2393-2407.WANG E， YANG Y J， LI L. Game of life based congestion control strategy in delay tolerant networks[J]. Journal of Computer Research and Development， 2014， 51(11)： 2393-2407

[11] SU J， CHIN A， POPIVANOVA A，et al. User mobility for opportunistic ad-hoc networking[A]. Proc of the 6th IEEE Workshop on Mobile Computing System and Applications[C]. 2004.41-50.

[12] 韓毅， 方濱興， 賈焰等. 基于密度估計(jì)的社會(huì)網(wǎng)絡(luò)特征簇挖掘方法[J]. 通信學(xué)報(bào)， 2012， 33(5)： 38-48.HAN Y， FANG B X， JIA Y，et al. Mining characteristic clusters： a density estimation approach[J]. Journal on Communications， 2012，33(5)：38-48.

[13] ZENG Z P，WANG J Y，ZHOU L Z，et al. Coherent closed quasi-clique discovery from large dense graph databases[A]. Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， KDD '06[C]. 2006. 797-802.

[14] 林友芳， 王天宇， 唐銳等. 一種有效的社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[J]. 計(jì)算機(jī)研究與發(fā)展， 2012， 49(2)： 337-345.LIN Y F， WANG T Y， TANG R，et al. An effective model and algorithm for community detection in social networks[J]. Journal of Computer Research and Development， 2012， 49(2)： 337-345.

[15] 李陟， 李千目， 張宏. 基于最近社交圈的社交時(shí)延容忍網(wǎng)絡(luò)路由策略[J]. 計(jì)算機(jī)研究與發(fā)展，2012， 49(6)： 1185-1195.LI Z， LI Q M， ZHANG H. Closely social circuit based routing in social delay tolerant networks[J]. Journal of Computer Research and Development， 2012， 49(6)： 1185-1195.

[16] 周瑞濤， 曹元大， 胡晶晶. 基于社區(qū)的容遲網(wǎng)絡(luò)路由方法[J]. 北京理工大學(xué)學(xué)報(bào)， 2012， 32(009)： 966-970.ZHOU T R， CAO Y D， HU J J. Community based routing in delay and tolerance networks[J]. Transaction of Beijing Institute of Technology，2012， 32(009)： 966-970.

[17] 于海征， 馬建峰， 邊紅. 容遲網(wǎng)絡(luò)中基于社會(huì)網(wǎng)絡(luò)的可靠路由[J].通信學(xué)報(bào)， 2010， 31(12)： 21-26.YU H Z， MA J F， BIAN H. Social network-based trustworthy routing in delay tolerant networks[J]. Journal on Communication， 2010，31(12)： 21-26.

[18] VELLAMBI B N， SUBRAMANIAN R， FEKRI F，et al. Reliable and efficient message delivery in delay tolerant networks using rateless codes[A]. Proc of the 1st International Mobisys Workshop on Mobile Opportunistic Networking[C]. ACM， 2007.91-98.

[19] EAGLE N， PENTLAND A S， LAZER D. Inferring friendship network structure by using mobile phone data[J]. Proceedings of the National Academy of Sciences， 2009， 106(36)： 15274-15278.

[20] 王恩， 楊永健， 李蒞. 基于動(dòng)態(tài)半馬爾可夫路徑搜索模型的 DTN分 簇 路 由 方 法 [EB/OL]. http：//cjc.ict.ac.cn/online/bfpub/we-20141216123501.pdf.WANG E， YANG Y J， LI L. A Clustering Routing Method Based on Semi-Markov Process and Path-finding Strategy in DTN[EB/OL].http：//cjc.ict.ac.cn/online/bfpub/we- 20141216123501.pdf.