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

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

1 引言

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

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

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

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

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

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

2.1 基于節(jié)點親密度的拓撲模型

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

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

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

圖1 相遇情況

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

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

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

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

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

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

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

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

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

圖4 網(wǎng)絡(luò)帶權(quán)拓撲

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 參數(shù)說明

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

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

時延均值=消息到達目的節(jié)點的平均時間

4.2 實驗結(jié)果分析

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

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

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

圖7 不同緩存下的平均時延

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

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

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

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

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

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

圖10 不同報文生成速率下的投遞成功率

圖11 不同報文生成速率下的平均時延

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

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

5 結(jié)束語

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

[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] 熊永平， 孫利民， 牛建偉等. 機會網(wǎng)絡(luò)[J]. 軟件學(xué)報， 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]. 計算機研究與發(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] 韓毅， 方濱興， 賈焰等. 基于密度估計的社會網(wǎng)絡(luò)特征簇挖掘方法[J]. 通信學(xué)報， 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] 林友芳， 王天宇， 唐銳等. 一種有效的社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[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] 李陟， 李千目， 張宏. 基于最近社交圈的社交時延容忍網(wǎng)絡(luò)路由策略[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é)報， 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ò)中基于社會網(wǎng)絡(luò)的可靠路由[J].通信學(xué)報， 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] 王恩， 楊永健， 李蒞. 基于動態(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.