基于鏈路代價(jià)綜合評(píng)估和轉(zhuǎn)發(fā)限制的延遲容忍社會(huì)性網(wǎng)絡(luò)路由

白云飛，劉元安，袁東明，胡鶴飛

（北京郵電大學(xué) 無線電技術(shù)與電磁兼容實(shí)驗(yàn)室，北京 100876）

0 引 言

由于延遲容忍網(wǎng)絡(luò)［1］無法保證穩(wěn)定的端到端鏈路連通，節(jié)點(diǎn)間的鏈路呈現(xiàn)間歇性中斷的特性，因此傳統(tǒng)無線網(wǎng)絡(luò)中的路由算法無法適應(yīng)延遲容忍網(wǎng)絡(luò)。在延遲容忍網(wǎng)絡(luò)中，路由機(jī)制一般采用“存儲(chǔ)－攜帶－轉(zhuǎn)發(fā)”的方式，中間節(jié)點(diǎn)在接收到信息并將其緩存后，可能暫時(shí)不存在轉(zhuǎn)發(fā)數(shù)據(jù)所需的鏈路，中間節(jié)點(diǎn)必須攜帶該信息直到它與路由決定的下一跳節(jié)點(diǎn)或目的節(jié)點(diǎn)之間建立連通的機(jī)會(huì)鏈路為止。因此，鏈路轉(zhuǎn)發(fā)代價(jià)評(píng)估的準(zhǔn)確性至關(guān)重要，一旦錯(cuò)過鏈路連通的機(jī)會(huì)或選擇的下一跳節(jié)點(diǎn)性能不佳，必將導(dǎo)致信息投遞率的下降，以及信息傳輸時(shí)延的增加。延遲容忍網(wǎng)絡(luò)中根據(jù)不同鏈路代價(jià)進(jìn)行轉(zhuǎn)發(fā)決策的路由算法研究已經(jīng)成為熱點(diǎn)。

文獻(xiàn)［2］提出了一種基于節(jié)點(diǎn)間轉(zhuǎn)發(fā)概率估計(jì)的路由協(xié)議 Prophet（Probabilistic routing protocol using history of encounters and transitivity），將節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)概率定義為每條鏈路的代價(jià)值。每個(gè)節(jié)點(diǎn)通過對(duì)相遇節(jié)點(diǎn)的歷史信息的統(tǒng)計(jì)，來計(jì)算到達(dá)其他節(jié)點(diǎn)的概率，并以此為判據(jù)進(jìn)行路由轉(zhuǎn)發(fā)決策。文獻(xiàn)［3］結(jié)合現(xiàn)實(shí)網(wǎng)絡(luò)場(chǎng)景，利用節(jié)點(diǎn)上存在大量重復(fù)鏈路的特點(diǎn)，并根據(jù)重復(fù)鏈路出現(xiàn)的次序進(jìn)行鏈路代價(jià)的計(jì)算，該算法是單副本協(xié)議，在網(wǎng)絡(luò)節(jié)點(diǎn)緩存資源受限時(shí)，能獲取較好的性能。文獻(xiàn)［4］提出了 MEED（Minimum estimated expected delay）路由協(xié)議，通過考察兩節(jié)點(diǎn)間的鏈路通斷規(guī)律，定義了節(jié)點(diǎn)間的平均等待時(shí)延，作為路由轉(zhuǎn)發(fā)的依據(jù)，在鏈路平均等待時(shí)延的計(jì)算中，節(jié)點(diǎn)只依賴本地信息，無需全網(wǎng)的先驗(yàn)知識(shí)，同時(shí)在中間節(jié)點(diǎn)處引入了路由重算的方法，來保證中間節(jié)點(diǎn)對(duì)機(jī)會(huì)鏈路的利用率。文獻(xiàn)［5］提出了條件相遇時(shí)間的概念，將兩節(jié)點(diǎn)之間的相遇概率計(jì)算擴(kuò)展至兩節(jié)點(diǎn)與第三個(gè)節(jié)點(diǎn)的相遇關(guān)系之中，并提出了有條件的最短路徑算法CSPR（Conditional shortest path routing），實(shí)驗(yàn)表明該算法能夠很好地適應(yīng)延遲容忍網(wǎng)絡(luò)間歇性中斷的特點(diǎn)。文獻(xiàn)［6］提出了一種基于上下文屬性信息的路由協(xié)議CAR（Context－aware routing），算法根據(jù)節(jié)點(diǎn)的剩余能量、網(wǎng)絡(luò)拓?fù)涞淖兓潭?、到達(dá)目的區(qū)域的概率和節(jié)點(diǎn)的移動(dòng)速度等信息來進(jìn)行鏈路代價(jià)的評(píng)估。

上述算法將延遲容忍網(wǎng)絡(luò)看作一個(gè)單獨(dú)的網(wǎng)絡(luò)區(qū)域，區(qū)域內(nèi)所有節(jié)點(diǎn)遵循大致相同的運(yùn)動(dòng)模型。但是在實(shí)際的DTN（如由行人、交通工具組成的城市網(wǎng)絡(luò)和多個(gè)社區(qū)之間的居民生活網(wǎng)絡(luò)）中，網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律往往具有較強(qiáng)的社會(huì)屬性（多區(qū)域特性），整個(gè)DTN是由若干位置不同的網(wǎng)絡(luò)子區(qū)域構(gòu)成，稱為延遲容忍社會(huì)性網(wǎng)絡(luò)［7］。文獻(xiàn)［7－9］研究表明實(shí)際的DTN網(wǎng)絡(luò)具有明顯的社會(huì)特性，并且定義了節(jié)點(diǎn)中心性的概念，根據(jù)節(jié)點(diǎn)中心性的不同，來進(jìn)行路由轉(zhuǎn)發(fā)決策。文獻(xiàn)［10］在文獻(xiàn)［7］對(duì)節(jié)點(diǎn)中心性定義的基礎(chǔ)上，引入了節(jié)點(diǎn)關(guān)聯(lián)度等參數(shù)，通過計(jì)算節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的效用值來完成路由的轉(zhuǎn)發(fā)，提出了延遲容忍分簇網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的自適應(yīng)機(jī)會(huì)路由算法URD。但URD容易導(dǎo)致數(shù)據(jù)分組大量的集中于網(wǎng)絡(luò)簇塊的割點(diǎn)之上，過多地消耗割點(diǎn)的能量資源，引起網(wǎng)絡(luò)擁塞、負(fù)載失衡等節(jié)點(diǎn)失效問題。

本文結(jié)合DTN網(wǎng)絡(luò)社會(huì)性的特點(diǎn)，提出了基于鏈路代價(jià)綜合評(píng)估和轉(zhuǎn)發(fā)限制的路由算法SECMR（Synthetical estimation of contact metrics routing based on forwarding constraint）。算法構(gòu)建了鏈路代價(jià)綜合評(píng)估模型，并將路由過程分為域內(nèi)轉(zhuǎn)發(fā)、活躍節(jié)點(diǎn)社會(huì)性游弋、信息投遞三個(gè)步驟。在域內(nèi)轉(zhuǎn)發(fā)階段，根據(jù)計(jì)算得到的節(jié)點(diǎn)社會(huì)性參數(shù)值來代替節(jié)點(diǎn)中心性參數(shù)進(jìn)行轉(zhuǎn)發(fā)決策，同時(shí)設(shè)置域內(nèi)轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST，來避免大量去往其他區(qū)域數(shù)據(jù)在活躍節(jié)點(diǎn)處的擁塞。

1 網(wǎng)絡(luò)模型

根據(jù)實(shí)際延遲容忍網(wǎng)絡(luò)具有社會(huì)屬性的特點(diǎn)，本文采用的DTN網(wǎng)絡(luò)模型如圖1所示。DTN由若干個(gè)社會(huì)子區(qū)域構(gòu)成，分別用社會(huì)區(qū)域1、社會(huì)區(qū)域2、社會(huì)區(qū)域3來表示，只在本區(qū)域內(nèi)運(yùn)動(dòng)的節(jié)點(diǎn)稱作域內(nèi)節(jié)點(diǎn)，在本區(qū)域內(nèi)運(yùn)動(dòng)頻繁且能夠在各個(gè)子區(qū)域之間運(yùn)動(dòng)的節(jié)點(diǎn)稱為活躍節(jié)點(diǎn)，活躍節(jié)點(diǎn)的社會(huì)性較強(qiáng)。域內(nèi)節(jié)點(diǎn)遵循IPMM（In－place mobility model）運(yùn)動(dòng)模型［11］，整個(gè)網(wǎng)絡(luò)被劃分為不同的子區(qū)域，不同的組節(jié)點(diǎn)分別在不同的子區(qū)域內(nèi)活動(dòng)；活躍節(jié)點(diǎn)遵循RWP（Random way point）運(yùn)動(dòng)模型［12］，能夠在整個(gè)網(wǎng)絡(luò)中運(yùn)動(dòng)。通過仿真實(shí)驗(yàn)分析表明，IPMM＋RWP運(yùn)動(dòng)模型能夠更加準(zhǔn)確地描述延遲容忍社會(huì)性網(wǎng)絡(luò)中節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律。

圖1 延遲容忍社會(huì)性網(wǎng)絡(luò)模型Fig.1 Social DTN network model

本網(wǎng)絡(luò)模型主要特征包括:

（1）節(jié)點(diǎn)之間的機(jī)會(huì)鏈路為雙向時(shí)變鏈路，鏈路的間歇中斷特性是隨機(jī)的，下一次連接到來的時(shí)刻和持續(xù)的時(shí)間是無法預(yù)知的。但由于網(wǎng)絡(luò)具有社會(huì)性的特點(diǎn)，網(wǎng)絡(luò)中節(jié)點(diǎn)經(jīng)過長時(shí)間運(yùn)動(dòng)后，具備一定的運(yùn)動(dòng)規(guī)律，通過對(duì)鏈路歷史信息的長時(shí)間觀測(cè)與記錄，能夠比較準(zhǔn)確地預(yù)測(cè)鏈路未來的通斷特性。

（2）機(jī)會(huì)鏈路連通期間的帶寬穩(wěn)定，數(shù)據(jù)轉(zhuǎn)發(fā)的傳輸時(shí)延可以忽略。

（3）網(wǎng)絡(luò)中各節(jié)點(diǎn)的緩存資源相同，能夠滿足單拷貝信息的存儲(chǔ)需求。同時(shí)，節(jié)點(diǎn)具備鄰居信息收集、鏈路綜合代價(jià)值的計(jì)算以及數(shù)據(jù)轉(zhuǎn)發(fā)等過程所需的處理能力。

2 鏈路代價(jià)綜合評(píng)估參數(shù)定義

定義1 節(jié)點(diǎn)社會(huì)性狀態(tài)參數(shù)。對(duì)于節(jié)點(diǎn)a，時(shí)間周期為T。定義參數(shù)SOC（a）表示節(jié)點(diǎn)a在連續(xù)的時(shí)間長度T內(nèi)，節(jié)點(diǎn)因?yàn)殡S機(jī)移動(dòng)而引起的鄰居節(jié)點(diǎn)集的變化程度。

令na［t1，t2］表示在時(shí)間段 ［t1，t2］內(nèi)節(jié)點(diǎn)a收集到的鄰居節(jié)點(diǎn)集的信息，在統(tǒng)計(jì)SOC（a）時(shí)，節(jié)點(diǎn)a將時(shí)間周期T劃分為兩個(gè)等長時(shí)間段進(jìn)行對(duì)比，SOC（a）計(jì)算公式如下:

由上式可以看出:每經(jīng)歷一個(gè)時(shí)間周期T，節(jié)點(diǎn)通過收集與自身建立機(jī)會(huì)鏈路的鄰居節(jié)點(diǎn)的信息，實(shí)現(xiàn)對(duì)SOC（a）的更新。SOC（a）的值越大，表明節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)變化程度越大，反映出節(jié)點(diǎn)a的運(yùn)動(dòng)比較頻繁，能夠與更多的節(jié)點(diǎn)建立機(jī)會(huì)鏈路，成為社會(huì)節(jié)點(diǎn)的可能性越大。利用該節(jié)點(diǎn)進(jìn)行信息的轉(zhuǎn)發(fā)，更有利于信息在區(qū)域內(nèi)的擴(kuò)散以及域間的傳輸。

定義2 鏈路通斷狀態(tài)參數(shù)。對(duì)于任意兩節(jié)點(diǎn)a與b，a與b之間存在的間歇性中斷鏈路為e （a，b）。設(shè)鏈路e （a，b）在時(shí)間周期T內(nèi)的離散連通時(shí)間段為ci＝ ｛c1，c2，…｝，離散中斷時(shí)間段為di＝ ｛d1，d2，…｝，則CDS （a，b）定義為鏈路e （a，b）的通斷狀態(tài)參數(shù)。該參數(shù)根據(jù)在周期T內(nèi)的各個(gè)通斷周期的持續(xù)時(shí)間計(jì)算得到，如圖2所示。

圖2 鏈路通斷周期的持續(xù)時(shí)間示意圖Fig.2 Duration time of contact up and down

由圖2可以看出，縱軸使用持續(xù)時(shí)間來表示鏈路通斷的狀態(tài)，當(dāng)鏈路斷裂時(shí)，持續(xù)時(shí)間始終為0，當(dāng)鏈路連通時(shí)，持續(xù)時(shí)間由0上升，直到鏈路連通狀態(tài)結(jié)束返回0。鏈路通斷狀態(tài)參數(shù)CDS （a，b）是通過對(duì)時(shí)間周期T內(nèi)鏈路e （a，b）的離散通斷周期進(jìn)行統(tǒng)計(jì)平均而得到，計(jì)算方法如下:

鏈路通斷狀態(tài)參數(shù)CDS （a，b）表征了在一段時(shí)間周期內(nèi)鏈路e （a，b）的連通狀態(tài)持續(xù)程度，CDS （a，b）的值越大，表明節(jié)點(diǎn)a與b之間的鏈路連通特性越好，更有利于大量數(shù)據(jù)的轉(zhuǎn)發(fā)。

定義3 鏈路頻率狀態(tài)參數(shù)。對(duì)于兩節(jié)點(diǎn)a與b，a與b之間存在的間歇性中斷鏈路為e （a，b），令t （a，b）表 示 在時(shí)間周期T內(nèi) 鏈 路e （a，b）的連通次數(shù)，t （a）表示時(shí)間周期T內(nèi)節(jié)點(diǎn)a與所有鄰居節(jié)點(diǎn)之間形成機(jī)會(huì)鏈路的次數(shù)。定義參數(shù)FEQ （a，b）為鏈路e （a，b）的頻率狀態(tài)參數(shù)，表示鏈路e （a，b）相對(duì)于節(jié)點(diǎn)a全部機(jī)會(huì)鏈路的連通頻率，F(xiàn)EQ （a，b）越大，則轉(zhuǎn)發(fā)的機(jī)率越高。

相對(duì)于鏈路通斷狀態(tài)參數(shù)CDS （a，b），鏈路頻率狀態(tài)參數(shù)FEQ （a，b）對(duì)鏈路的轉(zhuǎn)發(fā)代價(jià)值起到了更為精確的評(píng)估作用。擁有高FEQ （a，b）值的鏈路應(yīng)具有更高的轉(zhuǎn)發(fā)優(yōu)先級(jí)，因?yàn)殒溌返亩啻芜B接能夠更好地保證節(jié)點(diǎn)數(shù)據(jù)的連續(xù)轉(zhuǎn)發(fā)。

定義4 節(jié)點(diǎn)相近度參數(shù)。對(duì)于兩節(jié)點(diǎn)a與b，時(shí)間周期為T。定義參數(shù)SIM（a，b）表示在時(shí)間長度T內(nèi)，節(jié)點(diǎn)a與節(jié)點(diǎn)b的公共鄰居節(jié)點(diǎn)數(shù)占兩節(jié)點(diǎn)總鄰居節(jié)點(diǎn)數(shù)的比例，即與兩節(jié)點(diǎn)分別形成機(jī)會(huì)鏈路的鄰居節(jié)點(diǎn)集的相似程度。

假定t為當(dāng)前的計(jì)算時(shí)間，na（t－T，t）表示節(jié)點(diǎn)a在上一個(gè)時(shí)間周期T內(nèi)出現(xiàn)的鄰居節(jié)點(diǎn)集，nb（t－T，t）表示節(jié)點(diǎn)b在上一個(gè)時(shí)間周期T內(nèi)出現(xiàn)的鄰居節(jié)點(diǎn)集，則節(jié)點(diǎn)相近度參數(shù)的計(jì)算公式如下:

由上式可以看出，參數(shù)SIM（a，b）的值越大，表明兩節(jié)點(diǎn)能夠通過公共鄰居節(jié)點(diǎn)集進(jìn)行成功轉(zhuǎn)發(fā)的概率越大，在數(shù)據(jù)傳輸?shù)倪^程中，應(yīng)選擇與目的節(jié)點(diǎn)相近度較大的中間節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，增強(qiáng)延遲容忍網(wǎng)絡(luò)的協(xié)作性，提升節(jié)點(diǎn)間數(shù)據(jù)分組轉(zhuǎn)發(fā)的效率和成功率。

3 SECMR算法

在無線Ad hoc、無線Mesh等網(wǎng)絡(luò)中，由于節(jié)點(diǎn)之間鏈路不存在間歇性斷裂的特性，因此能夠使用基于單源最短路徑算法思想的Dijkstra或Bellman－Ford等算法，網(wǎng)絡(luò)特性能夠容忍算法本身的復(fù)雜度。但延遲容忍網(wǎng)絡(luò)不同于傳統(tǒng)的無線網(wǎng)絡(luò)，網(wǎng)絡(luò)結(jié)構(gòu)與鏈路特性決定了無法使用傳統(tǒng)的最短路徑算法進(jìn)行路由決策。因此，本節(jié)將在充分考慮DTN網(wǎng)絡(luò)無法時(shí)刻保持連通的情況下，結(jié)合DTN網(wǎng)絡(luò)社會(huì)性的特點(diǎn)，將路由過程劃分為域內(nèi)轉(zhuǎn)發(fā)、活躍節(jié)點(diǎn)社會(huì)性游弋、信息投遞三個(gè)步驟，在路由轉(zhuǎn)發(fā)過程中，采用SECMR算法中提出的鏈路代價(jià)綜合評(píng)估模型，對(duì)機(jī)會(huì)鏈路代價(jià)進(jìn)行評(píng)估，作為中間節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)決策的依據(jù)。

3.1 節(jié)點(diǎn)間信息交換

在SECMR算法中，每個(gè)節(jié)點(diǎn)擁有獨(dú)立的節(jié)點(diǎn)ID，并維護(hù)一張鄰居信息表，鄰居信息表通過定期廣播Hello消息的方式來獲取（見圖3），鄰居信息表中包含以下內(nèi)容:①時(shí)間周期T內(nèi)出現(xiàn)的鄰居節(jié)點(diǎn)集；②每個(gè)鄰居節(jié)點(diǎn)出現(xiàn)的次數(shù)；③與出現(xiàn)的每個(gè)鄰居節(jié)點(diǎn)所建立的機(jī)會(huì)鏈路的通斷周期記錄；④每個(gè)鄰居節(jié)點(diǎn)所記錄的一個(gè)時(shí)間周期內(nèi)自身的鄰居節(jié)點(diǎn)集；⑤鄰居節(jié)點(diǎn)與目的節(jié)點(diǎn)的綜合代價(jià)值。

節(jié)點(diǎn)在接收到鄰居節(jié)點(diǎn)的Hello消息時(shí)，應(yīng)返回相應(yīng)的信息，回復(fù)信息的內(nèi)容見圖4。其中Node＿ID表示本節(jié)點(diǎn)ID，Nbor＿ID表示本節(jié)點(diǎn)在上一個(gè)時(shí)間周期內(nèi)收集到的鄰居節(jié)點(diǎn)的ID，SECM表示節(jié)點(diǎn)計(jì)算得到的與其他相遇過節(jié)點(diǎn)之間的鏈路綜合代價(jià)評(píng)估值。

圖3 域內(nèi)鄰居節(jié)點(diǎn)信息收集算法Fig.3 Algorithm for collecting information of neighbors

圖4 Hello信息回復(fù)分組格式Fig.4 Acknowledgement of hello message

3.2 鏈路綜合代價(jià)值計(jì)算

如圖5所示，由兩個(gè)區(qū)域組成的延遲容忍社會(huì)性網(wǎng)絡(luò)中，節(jié)點(diǎn)m、n、p屬于活躍節(jié)點(diǎn)，不僅與區(qū)域內(nèi)的節(jié)點(diǎn)聯(lián)系較為頻繁，且在區(qū)域之間隨機(jī)移動(dòng)。若節(jié)點(diǎn)m中存在一條目的地為b的數(shù)據(jù)分組，則m移動(dòng)至區(qū)域B之后將會(huì)與B中的各個(gè)節(jié)點(diǎn)相遇，若m與b相遇，直接完成數(shù)據(jù)的投遞；若與節(jié)點(diǎn)p或節(jié)點(diǎn)a相遇，則需根據(jù)鏈路綜合代價(jià)值進(jìn)行轉(zhuǎn)發(fā)決策。

圖5 包含兩個(gè)子區(qū)域的社會(huì)性DTN示意圖Fig.5 Social DTN including two sub－regions

兩節(jié)點(diǎn)之間的鏈路綜合代價(jià)值SECM表征了兩節(jié)點(diǎn)之間構(gòu)成機(jī)會(huì)鏈路的概率大小以及信息在該鏈路上轉(zhuǎn)發(fā)的能力，主要根據(jù)鏈路通斷狀態(tài)、鏈路頻率狀態(tài)和節(jié)點(diǎn)相近度三個(gè)參數(shù)得到（計(jì)算方法見圖6），三個(gè)參數(shù)對(duì)于SECM（a，b）的權(quán)重程度是不同的，其權(quán)重比例為α≤β≤γ，在算法實(shí)現(xiàn)與仿真實(shí)驗(yàn)中分別取α＝0.2，β＝0.3，γ＝0.5。

圖6 節(jié)點(diǎn)之間的鏈路綜合代價(jià)值計(jì)算Fig.6 Algorithm for computing SEM（a，b）

3.3 路由轉(zhuǎn)發(fā)

路由轉(zhuǎn)發(fā)包含兩種情況:

（1）源節(jié)點(diǎn)與目的節(jié)點(diǎn)處于同一個(gè)社會(huì)網(wǎng)絡(luò)區(qū)域之內(nèi)，轉(zhuǎn)發(fā)過程可以通過活躍節(jié)點(diǎn)或以SECM為依據(jù)的轉(zhuǎn)發(fā)決策進(jìn)行。

（2）源節(jié)點(diǎn)與目的節(jié)點(diǎn)位于不同的社會(huì)網(wǎng)絡(luò)區(qū)域，數(shù)據(jù)分組的轉(zhuǎn)發(fā)必須首先轉(zhuǎn)發(fā)至源節(jié)點(diǎn)區(qū)域內(nèi)的活躍節(jié)點(diǎn)，活躍節(jié)點(diǎn)進(jìn)行社會(huì)性游弋到達(dá)目的節(jié)點(diǎn)所在的網(wǎng)絡(luò)區(qū)域，然后通過SECM進(jìn)行數(shù)據(jù)投遞。

對(duì)于第一種情況，根據(jù)算法2，區(qū)域內(nèi)各節(jié)點(diǎn)通過計(jì)算得到與鄰居節(jié)點(diǎn)的SECM值，節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)，只需比較SECM值的大小來決定是否進(jìn)行轉(zhuǎn)發(fā)。

對(duì)于第二種情況，如果按照URD等算法提出的按節(jié)點(diǎn)中心度進(jìn)行轉(zhuǎn)發(fā)決策［10］，跨區(qū)域的數(shù)據(jù)分組最終都會(huì)聚集到本區(qū)域內(nèi)節(jié)點(diǎn)中心度最大的節(jié)點(diǎn)上，導(dǎo)致節(jié)點(diǎn)的開銷增大，影響數(shù)據(jù)的投遞率和傳輸時(shí)延。SECMR算法針對(duì)這種情況，對(duì)于跨區(qū)域數(shù)據(jù)在域內(nèi)進(jìn)行轉(zhuǎn)發(fā)的階段，設(shè)置了域內(nèi)路由轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST，當(dāng)某一活躍節(jié)點(diǎn)的節(jié)點(diǎn)社會(huì)屬性參數(shù)值超過SOC＿CST時(shí)，便中止數(shù)據(jù)的域內(nèi)轉(zhuǎn)發(fā)，直到活躍節(jié)點(diǎn)進(jìn)入目的節(jié)點(diǎn)所在的網(wǎng)絡(luò)區(qū)域之中。域內(nèi)路由轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST的設(shè)置充分考慮了社會(huì)網(wǎng)絡(luò)的特點(diǎn):每個(gè)社會(huì)網(wǎng)絡(luò)區(qū)域內(nèi)的活躍節(jié)點(diǎn)一般不止一個(gè)，將域間數(shù)據(jù)的轉(zhuǎn)發(fā)開銷由一個(gè)活躍度最大的節(jié)點(diǎn)分配至數(shù)個(gè)較為活躍的節(jié)點(diǎn)，在大幅降低活躍節(jié)點(diǎn)資源開銷的同時(shí)，也有效提升了數(shù)據(jù)的投遞成功率，降低了傳輸時(shí)延，SECMR算法的路由轉(zhuǎn)發(fā)決策過程見圖7。

圖7 SECMR路由轉(zhuǎn)發(fā)決策Fig.7 Forwarding policy of SECMR

4 仿真驗(yàn)證

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

本文采用仿真軟件ONE（Opportunistic network environment）［13］進(jìn)行算法的仿真與測(cè)試。ONE能夠支持多種運(yùn)動(dòng)模型來模擬網(wǎng)絡(luò)中節(jié)點(diǎn)的運(yùn)動(dòng)軌跡，而且提供了人機(jī)交互界面來進(jìn)行網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)運(yùn)動(dòng)狀態(tài)的實(shí)時(shí)觀測(cè)。本文利用該仿真軟件，首先進(jìn)行了SECMR算法對(duì)于延遲容忍社會(huì)性網(wǎng)絡(luò)的適應(yīng)度測(cè)試，將SECMR算法與URD算法在不同的運(yùn)動(dòng)模型條件下的性能進(jìn)行了對(duì)比，另外還對(duì)SECMR路由算法與Epidemic、Prophet和 MEED三種經(jīng)典DTN路由協(xié)議的數(shù)據(jù)投遞率和平均時(shí)延等性能指標(biāo)進(jìn)行了仿真實(shí)驗(yàn)。

仿真主機(jī)采用Intel Core23.0GHz，操作系統(tǒng)為Linux 2.6.26，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量設(shè)置為300個(gè)，網(wǎng)絡(luò)共劃分為15個(gè)子區(qū)域，每個(gè)區(qū)域20個(gè)節(jié)點(diǎn)，其中15個(gè)節(jié)點(diǎn)的移動(dòng)模型設(shè)置為IPMM，5個(gè)節(jié)點(diǎn)的移動(dòng)模型設(shè)置為RWP。域內(nèi)路由轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST＝0.3，其他具體仿真參數(shù)如下:網(wǎng)絡(luò)規(guī)模為5km×5km；節(jié)點(diǎn)移動(dòng)速度為0～10m／s；通信半徑為150m；節(jié)點(diǎn)緩存為6MB；鏈路帶寬為10MB；時(shí)間周期T為1min；信息分組長度為512Byte；信息注入速率為15min；分組發(fā)送頻率為5packets／s；移動(dòng)模型為IPMM＋RWP；仿真持續(xù)期為12h。

4.2 仿真結(jié)果與分析

圖8給出了SECMR路由協(xié)議對(duì)于不同的節(jié)點(diǎn)運(yùn)動(dòng)模型的適應(yīng)程度。從圖8可以看出，當(dāng)DTN網(wǎng)絡(luò)中的節(jié)點(diǎn)采用IPMM＋RWP運(yùn)動(dòng)模型時(shí)，SECMR算法能夠達(dá)到滿意的數(shù)據(jù)投遞成功率，而對(duì)于RW和RWP兩種運(yùn)動(dòng)模型，SECMR協(xié)議的性能一般。這是因?yàn)樵谘舆t容忍社會(huì)性網(wǎng)絡(luò)中，節(jié)點(diǎn)的運(yùn)動(dòng)軌跡基本符合IPMM＋RWP運(yùn)動(dòng)模型，而SECMR協(xié)議的鏈路代價(jià)綜合評(píng)估算法正好滿足網(wǎng)絡(luò)社會(huì)性特點(diǎn)的要求。RW為完全隨機(jī)性的運(yùn)動(dòng)模型，節(jié)點(diǎn)的歷史行為對(duì)節(jié)點(diǎn)的未來運(yùn)動(dòng)軌跡無任何影響，因此在仿真中的性能表現(xiàn)較差；RWP運(yùn)動(dòng)模型是RW模型的優(yōu)化，其運(yùn)動(dòng)軌跡更符合現(xiàn)實(shí)網(wǎng)絡(luò)的特點(diǎn)，因此在仿真中的性能居中。仿真結(jié)果證明了SECMR算法對(duì)延遲容忍社會(huì)性網(wǎng)絡(luò)具有較高的適應(yīng)度，其數(shù)據(jù)投遞成功率能維持在一個(gè)較高的水平。

圖8 不同節(jié)點(diǎn)移動(dòng)模型下的SECMR路由協(xié)議性能Fig.8 Routing performance with different mobile model

圖9 不同仿真時(shí)間條件下的算法投遞率性能對(duì)比Fig.9 Delivery ratio comparison with different simulation time

圖9為不同仿真時(shí)間下4種算法的數(shù)據(jù)分組投遞成功率的變化情況。由圖9可以看出，隨著仿真時(shí)間由100增加到700min，四種路由協(xié)議的數(shù)據(jù)投遞率都呈現(xiàn)下降的趨勢(shì)，這是因?yàn)楦鶕?jù)網(wǎng)絡(luò)參數(shù)的設(shè)定，分組數(shù)據(jù)不停地向網(wǎng)絡(luò)中注入，導(dǎo)致網(wǎng)絡(luò)中數(shù)據(jù)分組的大量擴(kuò)散，因此節(jié)點(diǎn)的緩存資源將會(huì)逐步消耗殆盡，從而引起路由性能的下降。從仿真的整體結(jié)果來看，Epidemic協(xié)議擁有最高的數(shù)據(jù)投遞率，Prophet和MEED兩種單副本路由協(xié)議的投遞率基本持平，維持在0.48～0.6，而SECMR協(xié)議的數(shù)據(jù)投遞率比這兩種協(xié)議高15%～20%。該仿真結(jié)果的產(chǎn)生基于以下原因:Epidemic路由協(xié)議利用洪泛的方法將數(shù)據(jù)信息轉(zhuǎn)發(fā)至所有遇到的節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)數(shù)據(jù)副本，該算法通過犧牲大量的網(wǎng)絡(luò)資源來獲取極大的數(shù)據(jù)投遞概率，實(shí)現(xiàn)數(shù)據(jù)分組的高效轉(zhuǎn)發(fā)與傳輸，由于該仿真場(chǎng)景中節(jié)點(diǎn)的緩存容量較為充足，因此能夠保持較高的數(shù)據(jù)投遞率；Prophet和MEED兩種路由協(xié)議都是根據(jù)節(jié)點(diǎn)之間的歷史交互情況來對(duì)節(jié)點(diǎn)未來的性能進(jìn)行預(yù)測(cè)，并將預(yù)測(cè)結(jié)果作為路由轉(zhuǎn)發(fā)決策的依據(jù)，以提升投遞率，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)之間的交互比較頻繁時(shí)，算法性能優(yōu)越性較易體現(xiàn)，然而該仿真網(wǎng)絡(luò)的節(jié)點(diǎn)運(yùn)動(dòng)模型為IPMM＋RWP，兩種算法計(jì)算得出的鏈路代價(jià)值往往無法體現(xiàn)網(wǎng)絡(luò)的真實(shí)特性，因此其數(shù)據(jù)投遞率偏低；SECMR算法充分考慮網(wǎng)絡(luò)的社會(huì)屬性，對(duì)節(jié)點(diǎn)之間的鏈路代價(jià)進(jìn)行了綜合性評(píng)估，仿真結(jié)果充分說明了SECMR協(xié)議對(duì)于延遲容忍社會(huì)性網(wǎng)絡(luò)的適應(yīng)程度。

圖10為4種路由協(xié)議在100～700min內(nèi)的平均傳輸時(shí)延的對(duì)比情況。由圖10中可以看出，Prophet和MEED兩種單副本路由協(xié)議的時(shí)延開銷較大，這是由于:①兩種協(xié)議必須收集節(jié)點(diǎn)間的歷史交互情況，進(jìn)行鏈路代價(jià)的計(jì)算，以完成路由轉(zhuǎn)發(fā)；②由于DTN的社會(huì)性，導(dǎo)致兩種算法計(jì)算得出的判據(jù)值并不能很好地反映網(wǎng)絡(luò)的真實(shí)情況，從而導(dǎo)致對(duì)下一跳節(jié)點(diǎn)選擇的精確性不足，引發(fā)了傳輸時(shí)延的增加。Epidemic協(xié)議在節(jié)點(diǎn)相遇時(shí)采用摘要向量來進(jìn)行信息的互換，一方面保證了重復(fù)分組的發(fā)送，同時(shí)使得數(shù)據(jù)副本數(shù)量大大增加，有效地降低了傳輸時(shí)延，但是這種性能必須以充足的網(wǎng)絡(luò)資源為前提。SECMR協(xié)議根據(jù)節(jié)點(diǎn)的歷史交互信息進(jìn)行鏈路綜合代價(jià)的計(jì)算，但采用節(jié)點(diǎn)社會(huì)性參數(shù)替代傳統(tǒng)的網(wǎng)格中心度參數(shù)，滿足了DTN社會(huì)性的要求，提升了路由轉(zhuǎn)發(fā)決策的準(zhǔn)確度，因此能夠獲取較低的平均傳輸時(shí)延。根據(jù)仿真結(jié)果，SECMR算法相對(duì)于Prophet和MEED兩種協(xié)議，平均延遲分別降低了9%和12%。

圖10 不同仿真時(shí)間條件下的算法平均傳輸延遲對(duì)比Fig.10 Average delay comparison with different simulation time

圖11 不同緩存資源條件下的算法投遞率對(duì)比Fig.11 Delivery ratio performance with different buffers

圖11為4種算法的數(shù)據(jù)分組投遞成功率在不同的節(jié)點(diǎn)緩存容量條件下的變化情況。仿真結(jié)果表明，隨著節(jié)點(diǎn)緩存容量的不斷增加，Epidemic協(xié)議的數(shù)據(jù)投遞率提升明顯，當(dāng)緩存容量超過30 MB時(shí)，Epidemic算法的投遞率已經(jīng)達(dá)到100%。SECMR算法運(yùn)行過程中，節(jié)點(diǎn)需要對(duì)鏈路綜合代價(jià)值以及節(jié)點(diǎn)社會(huì)性參數(shù)值進(jìn)行計(jì)算，因此對(duì)于節(jié)點(diǎn)資源有一定的需求，隨著緩存資源的增加，SCEMR算法在性能上的優(yōu)勢(shì)也進(jìn)一步體現(xiàn)，當(dāng)緩存容量大于15MB時(shí)，SECMR算法的數(shù)據(jù)投遞率比Prophet和MEED算法平均高出近16%。此外，Prophet和MEED算法并未隨節(jié)點(diǎn)緩存容量的增加而有較大的性能提升，這是由于這兩種協(xié)議并未考慮延遲容忍網(wǎng)絡(luò)的社會(huì)屬性，算法獲取的鏈路代價(jià)值無法準(zhǔn)確反映網(wǎng)絡(luò)的真實(shí)情況，盡管擁有足夠的緩存資源，但數(shù)據(jù)投遞率依然無法得到有效的提升。

圖12為4種路由協(xié)議的平均傳輸時(shí)延在不同的節(jié)點(diǎn)緩存容量條件下的變化情況。從圖12看出，4種協(xié)議的平均時(shí)延隨著緩存容量的增加都表現(xiàn)出遞減的趨勢(shì)，這是因?yàn)?對(duì)于多副本傳染的Epidemic協(xié)議，緩存容量的提升保證了網(wǎng)絡(luò)中的副本數(shù)量，因此數(shù)據(jù)投遞的效率會(huì)大幅提升，相應(yīng)地縮短了數(shù)據(jù)傳輸?shù)臅r(shí)延；對(duì)于基于歷史信息的Prophet、MEED、SECMR三種單副本協(xié)議而言，緩存資源的豐富不僅能夠保存更多的鄰居節(jié)點(diǎn)信息，減少鏈路代價(jià)值的計(jì)算時(shí)間，同時(shí)保證了數(shù)據(jù)不會(huì)因?yàn)楣?jié)點(diǎn)緩存溢出而頻繁地被丟棄，減少了數(shù)據(jù)的重傳次數(shù)，從而降低了數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延。

圖12 不同緩存資源條件下的算法平均傳輸延遲對(duì)比Fig.12 Average delay performance with different buffers

圖13 不同域內(nèi)路由轉(zhuǎn)發(fā)限制參數(shù)下的算法投遞率對(duì)比Fig.13 Delivery ratio with different SOC＿CST

圖13給出了具有不同路由轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST的SECMR路由協(xié)議與URD路由協(xié)議在數(shù)據(jù)投遞率指標(biāo)上的對(duì)比情況。由仿真結(jié)果可以看出，SECMR－0.3的數(shù)據(jù)投遞率比URD協(xié)議高21%～40%，SECMR－0.5的數(shù)據(jù)投遞率比URD協(xié)議高8%～28%，而SECMR－0.7的數(shù)據(jù)投遞率性能反而低于URD算法。造成這種現(xiàn)象的原因是SOC＿CST取值的不同，SOC＿CST的取值過大時(shí)，SECMR算法的域內(nèi)路由轉(zhuǎn)發(fā)決策將會(huì)造成跨區(qū)域數(shù)據(jù)分組在域內(nèi)少量活躍度很高的節(jié)點(diǎn)處形成數(shù)據(jù)擁塞，因此很多數(shù)據(jù)分組會(huì)因?yàn)楣?jié)點(diǎn)緩存容量不足而被丟棄，制約了協(xié)議的數(shù)據(jù)投遞成功率；當(dāng)SOC＿CST＝0.3時(shí)，路由算法能夠?qū)⒂蜷g數(shù)據(jù)的轉(zhuǎn)發(fā)開銷由少數(shù)幾個(gè)活躍度較大的節(jié)點(diǎn)分?jǐn)傊炼鄠€(gè)較為活躍的節(jié)點(diǎn)，在降低活躍節(jié)點(diǎn)資源開銷的同時(shí)，有效提升了數(shù)據(jù)的投遞成功率。經(jīng)過多次仿真實(shí)驗(yàn)的驗(yàn)證，當(dāng)SOC＿CST的取值范圍在0.3～0.4時(shí)，SECMR算法的數(shù)據(jù)投遞率將維持在60%以上。

圖14給出了具有不同路由轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST的SECMR路由協(xié)議與URD路由協(xié)議在平均傳輸時(shí)延指標(biāo)上的對(duì)比情況。由仿真結(jié)果可以看出，SECMR－0.3的平均傳輸時(shí)延比URD協(xié)議低19%～23%，SECMR－0.5的平均傳輸時(shí)延比URD協(xié)議低9%～14%，而SECMR－0.7的平均傳輸時(shí)延高于URD算法。造成這種現(xiàn)象的原因是SOC＿CST取值的不同，當(dāng)SOC＿CST的取值過大時(shí)，SECMR算法的域內(nèi)路由轉(zhuǎn)發(fā)決策將會(huì)造成跨區(qū)域數(shù)據(jù)分組在域內(nèi)少量活躍度很高的節(jié)點(diǎn)處的數(shù)據(jù)擁塞，因此很多數(shù)據(jù)分組會(huì)因?yàn)楣?jié)點(diǎn)緩存容量不足而被丟棄，引發(fā)了大量域間數(shù)據(jù)的重傳，導(dǎo)致了平均傳輸時(shí)延的增加；當(dāng)SOC＿CST＝0.3時(shí)，路由算法能夠?qū)⒂蜷g數(shù)據(jù)的轉(zhuǎn)發(fā)開銷由少數(shù)幾個(gè)活躍度較大的節(jié)點(diǎn)分?jǐn)傊炼鄠€(gè)較為活躍的節(jié)點(diǎn)，在降低活躍節(jié)點(diǎn)資源開銷的同時(shí)，也有效減少了數(shù)據(jù)丟失和數(shù)據(jù)重傳的次數(shù)。

圖14 不同域內(nèi)路由轉(zhuǎn)發(fā)限制參數(shù)下的平均傳輸時(shí)延對(duì)比Fig.14 Average delay with different SOC＿CST

5 結(jié)束語

為了適應(yīng)延遲容忍網(wǎng)絡(luò)的社會(huì)性，提升路由轉(zhuǎn)發(fā)的準(zhǔn)確性，本文引入節(jié)點(diǎn)社會(huì)性參數(shù)、鏈路通斷狀態(tài)參數(shù)、鏈路頻率狀態(tài)參數(shù)與節(jié)點(diǎn)相近度參數(shù)構(gòu)建了延遲容忍社會(huì)性網(wǎng)絡(luò)鏈路代價(jià)綜合評(píng)估模型，并在此模型的基礎(chǔ)上提出了SECMR路由協(xié)議。在域內(nèi)轉(zhuǎn)發(fā)階段，根據(jù)計(jì)算得到的節(jié)點(diǎn)社會(huì)性參數(shù)值來代替節(jié)點(diǎn)中心性參數(shù)進(jìn)行轉(zhuǎn)發(fā)決策，同時(shí)設(shè)置域內(nèi)轉(zhuǎn)發(fā)限制參數(shù)SOC＿CST，來避免跨區(qū)域數(shù)據(jù)在活躍節(jié)點(diǎn)處的大量聚集。仿真實(shí)驗(yàn)結(jié)果表明，SECMR路由協(xié)議對(duì)于延遲容忍社會(huì)性網(wǎng)絡(luò)具有良好的適應(yīng)能力；與Prophet及MEED路由協(xié)議相比，SECMR路由協(xié)議能夠有效提升數(shù)據(jù)分組投遞率，降低傳輸時(shí)延。

［1］Fall K.A delay－tolerant network architecture for challenged internets［C］∥Proc Conf Appl Technol Architectures Protocols for Computer Commun，Karlsruhe，Germany，2003:27－34.

［2］Lindgren A，Doria A，Schelen O.Probabilistic routing in intermittently connected networks［J］.SIGMOBILE Mob Comput Commun Rev，2003，7（3）:19－20.

［3］Jathar R，Gupta A.Probabilistic routing using con－tact sequencing in delay tolerant networks［C］∥The 2nd International Conference on Communication Systems and Networks，2010.

［4］Jones E，Li L.Practical routing in delay tolerant networks［J］.IEEE Transactions on Mobile Computing，2007，6（8）:943－959.

［5］Bulut E，Geyik S，Szymanski B.Conditional shortest path routing in delay tolerant networks［C］∥IEEE International Symposium on“A World of Wireless，Mobile and Multimedia Networks”，2010.

［6］Musolesi M，Mascolo C.CAR:context－aware adaptive routing for delay－tolerant mobile networks［J］.IEEE Transactions on Mobile Computing，2009，8（2）:246－260.

［7］Daly Ekizabeth，Haahr Mads.Social network analysis for routing in disconnected dealy－tolerant MANETs［J］.IEEE Transactions on Mobile Computing，2009，8（5）:606－621.

［8］Jeffrey T，Stanley M.An experimental study of the small world problem［J］.Sociometry，1969，32（4）:425－443.

［9］Freeman Linton C.Centrality in social networks conceptual clarification［J］.Social Networks，1978，79（1）:215－239.

［10］王博，黃傳河，楊文忠.時(shí)延容忍網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的自適應(yīng)機(jī)會(huì)路由算法［J］.通信學(xué)報(bào)，2010，31（10）:36－47.Wang Bo，Huang Chuan－h(huán)e，Yang Wen－zhong.A－daptive opportunistic routing protocol based on forwarding－utility for delay tolerant networks［J］.Journal on Communications，2010，31（10）:36－47.

［11］Hong Xiao－yan，Gerla Mario，Pei Guang－yu，et al.A group mobility model for ad hoc wireless networks［C］∥Bonkerche A，ed.Proc.of the Int＇l Workshop on Modeling and Simulation of Wireless and Mobile Systems Seattle:ACM Press，1999:53－60.

［12］Bettstetter C，Hartenstein H.Stochastic properties of the random waypoint mobility model［C］∥ACM and Kluwer Wireless Networks:Special Issue on Modeling and Analysis of Mobile Networks，2004，10（5）:555－567.

［13］Ari K，Jorg O，Teemu K.The ONE simulator for DTN protocol evaluation［C］∥Proc of the ACM SIMU Tools，Rome，Italy，2009.