基于節(jié)點(diǎn)間親密度的DTN 路由策略

馮濤，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引言

延遲容忍網(wǎng)絡(luò)(Delay-Tolerant Network，DTN)是從空間網(wǎng)絡(luò)互聯(lián)抽象出來的一種網(wǎng)絡(luò)體系結(jié)構(gòu)，源于FALL［1］在2003 年發(fā)表的一篇論文，但至今定義仍然模糊.一般認(rèn)為，DTN是一種新型的“存儲—攜帶—轉(zhuǎn)發(fā)”網(wǎng)絡(luò)體系結(jié)構(gòu)和協(xié)議族，用來實(shí)現(xiàn)惡劣或受干擾環(huán)境下的無線數(shù)據(jù)傳輸.

可以將DTN 看作是一種特殊的ad hoc 網(wǎng)絡(luò)，主要針對端到端連接和節(jié)點(diǎn)資源都有限的網(wǎng)絡(luò)解決方案，用于滿足隨意的異步消息的可靠傳遞.［1-2］由于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目比較少，節(jié)點(diǎn)之間聯(lián)系不是很頻繁，會經(jīng)常出現(xiàn)網(wǎng)絡(luò)斷開的現(xiàn)象，導(dǎo)致報(bào)文在傳輸過程中不能確保端到端的路徑.DTN 的研究和發(fā)展為軍事戰(zhàn)爭、航天通信、災(zāi)難恢復(fù)等領(lǐng)域的消息交互提供有力的科學(xué)理論和技術(shù)支持.

1 相關(guān)工作

DTN 現(xiàn)有的研究雖有一定成果，但仍處于初步階段.也可能是適用性的限制，大家都熱衷于研究一些比較熱門的網(wǎng)絡(luò)模型和通信機(jī)制，如對等網(wǎng)絡(luò)資源搜索算法［3］和移動Agent 組通信機(jī)制［4］.但是，DTN 的研究無論是在理論還是面向?qū)嶋H應(yīng)用方面都有很大的研究空間.

在DTN 的研究過程中，網(wǎng)絡(luò)的路由協(xié)議被人關(guān)注最多.幾種比較典型的DTN 路由算法:VAHDAT等［5］提出的蔓延路由協(xié)議(epidemic routeing)、基于概率的路由協(xié)議(probabilistic routeing)［6］和PAN等［7］提出的基于社會網(wǎng)絡(luò)的Bubble 路由算法.

蔓延路由協(xié)議的思想是把所要發(fā)送的報(bào)文給它所有的鄰居節(jié)點(diǎn).這種路由方式意味著:只要節(jié)點(diǎn)的緩存足夠大，隨著節(jié)點(diǎn)之間的不斷“接觸”，數(shù)據(jù)就會從源端開始像病毒那樣傳播到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，從而大大增加網(wǎng)路負(fù)擔(dān)，造成網(wǎng)絡(luò)擁塞.所以，現(xiàn)實(shí)情況下，由于緩存空間、能量、帶寬等資源的限制，傳染路由性能會嚴(yán)重降級，很難適應(yīng)現(xiàn)實(shí)環(huán)境.

PROPHET(Probabilistic Routeing Protocol using History of Encounters and Transitivity)［6］是一種基于概率估計(jì)的路由，與傳染路由盲目地向所有鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息不同，概率路由中的每個節(jié)點(diǎn)將會估計(jì)到達(dá)目的節(jié)點(diǎn)的概率.如果所遇節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率比自己的大，則將報(bào)文轉(zhuǎn)發(fā)給它，否則將自己傳輸或等待其他節(jié)點(diǎn).與蔓延路由相比，網(wǎng)絡(luò)開銷降低，但與此同時，延遲會增加，報(bào)文遞交率會降低.

基于社會網(wǎng)絡(luò)的Bubble 路由算法主要利用社會網(wǎng)絡(luò)的社區(qū)性和集中性現(xiàn)象.它的消息傳遞分為兩步，并且有全局等級和本地活躍度等級兩個等級信息.首先源節(jié)點(diǎn)根據(jù)全局等級信息將信息發(fā)送到具有更高集中度的節(jié)點(diǎn)，直到該節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)又屬于同一個社區(qū)，然后在同一社區(qū)內(nèi)部再根據(jù)本地活躍度等級信息將信息轉(zhuǎn)發(fā)到目標(biāo)節(jié)點(diǎn).

本文在上述基礎(chǔ)上提出一個基于節(jié)點(diǎn)親密度的路由策略.利用人與人相處時間較為穩(wěn)定的特征確定人與人之間的親密度，再根據(jù)親密度的大小輔助路由，最后利用實(shí)驗(yàn)與現(xiàn)有的路由進(jìn)行分析比較，證明其有效性.

2 節(jié)點(diǎn)親密度

在Reality 數(shù)據(jù)集中記錄節(jié)點(diǎn)與節(jié)點(diǎn)的相遇信息.如兩個節(jié)點(diǎn)相遇時，互相發(fā)送信號獲知對方節(jié)點(diǎn)信息，一定周期內(nèi)未收到對方信息即認(rèn)為對方離開，結(jié)束相遇.獲取相遇信息主要是為確定節(jié)點(diǎn)間的相遇時長，進(jìn)而確定節(jié)點(diǎn)間親密度.

2.1 親密度定義

提出親密度的定義如下:

節(jié)點(diǎn)與某個節(jié)點(diǎn)頻繁相遇，使得周期T 內(nèi)兩個節(jié)點(diǎn)累計(jì)相處總時長達(dá)到一定限度，稱該節(jié)點(diǎn)的親密度高.

節(jié)點(diǎn)每次與另一節(jié)點(diǎn)nk相處的時長tk可通過式(1)獲得，即用節(jié)點(diǎn)離開nk的時間lk減去節(jié)點(diǎn)與nk相遇的時間mk.

若在周期T 內(nèi)節(jié)點(diǎn)對nk重復(fù)訪問，累計(jì)時長

2.2 獲知親密度的方式

在獲知節(jié)點(diǎn)親密度時，可根據(jù)周期統(tǒng)計(jì)信息進(jìn)行，并基于上一周期獲知的統(tǒng)計(jì)數(shù)據(jù)指導(dǎo)下一周期的消息傳遞并輔助未來的路由.為此提出以下獲知親密度的方式:

設(shè)節(jié)點(diǎn)x 在最近1個周期T 內(nèi)接觸的其他m個節(jié)點(diǎn)的集合為Sx={n1，n2，…，nm}，集合中任意1個元素ni為節(jié)點(diǎn)x 最近1個周期接觸時間大于零的節(jié)點(diǎn)，與Sx對應(yīng)，節(jié)點(diǎn)x 與其他節(jié)點(diǎn)接觸時長所組成的集合為ΔtSx={Δt1，Δt2，…，Δtm}，其中Δti為節(jié)點(diǎn)x 最近1個周期與節(jié)點(diǎn)ni接觸的時長.那么節(jié)點(diǎn)x 與ni的親密度C(x，ni)=Δ(ti/Δ(t1+Δt2+…+Δtm)).

根據(jù)人類的活動規(guī)律，文中設(shè)定1個周期為1周，統(tǒng)計(jì)節(jié)點(diǎn)在最近1個月(4 周)通信的節(jié)點(diǎn)信息，并求取親密度.

3 基于節(jié)點(diǎn)親密度的路由策略

3.1 社會網(wǎng)絡(luò)模型

在現(xiàn)實(shí)生活中，人與人之間的親密度具有較強(qiáng)的穩(wěn)定性，即雖然會在生活中認(rèn)識很多不同的人，但是與大部分人的親密度都不高，如路人;而與少部分的人親密度較高且相對穩(wěn)定，如家人.

社會網(wǎng)絡(luò)模型:例如，對于一個城市的社會網(wǎng)絡(luò)，可以分為無數(shù)個人，那么抽象為社會網(wǎng)絡(luò)模型，可以將這種網(wǎng)絡(luò)的每個人看成是網(wǎng)絡(luò)中的每個節(jié)點(diǎn)，網(wǎng)絡(luò)之間的通信利用所攜帶的通信設(shè)備進(jìn)行.可以看出，某些時刻社會網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)之間通信可能具有間歇，所有這種網(wǎng)絡(luò)表現(xiàn)出DTN 的特點(diǎn).本課題就是對這樣的社會網(wǎng)絡(luò)進(jìn)行抽象，將攜帶移動通信設(shè)備的人看作網(wǎng)絡(luò)中的節(jié)點(diǎn).利用親密度的不同輔助節(jié)點(diǎn)間數(shù)據(jù)的傳輸，提出在DTN 社會網(wǎng)絡(luò)環(huán)境中基于節(jié)點(diǎn)親密度的路由策略(Human Intimate Degree Based Routeing，HIDBR).

3.2 HIDBR 路由策略中的消息傳遞

首先介紹下面所用到的數(shù)據(jù)結(jié)構(gòu).

其中:id為當(dāng)前節(jié)點(diǎn)號;connectNode為該節(jié)點(diǎn)的接觸節(jié)點(diǎn)集合Sx;c表示與本節(jié)點(diǎn)的親密度C(x，ni).

設(shè)節(jié)點(diǎn)x 攜帶消息m，m 的目的節(jié)點(diǎn)為d，x 對下一節(jié)點(diǎn)y 的消息遞交方法如下:(1)當(dāng)y 節(jié)點(diǎn)即為目的節(jié)點(diǎn)d 時，x 節(jié)點(diǎn)將消息m 發(fā)送給y 節(jié)點(diǎn)并刪除x 上的m，目的節(jié)點(diǎn)收到消息，消息傳遞結(jié)束.(2)當(dāng)y 節(jié)點(diǎn)不是目的節(jié)點(diǎn)d 時，分別比較x和y 與d 的親密度，若C(x，d)＜C(y，d)，x 節(jié)點(diǎn)將消息m 發(fā)送給y 節(jié)點(diǎn)，說明與x 相比，y 與目的節(jié)點(diǎn)的親密度更高，y 與d 在上1個周期內(nèi)相處的時間更長，能把消息傳遞給d 的可能性也更大.(3)當(dāng)y 節(jié)點(diǎn)不是目的節(jié)點(diǎn)d 且C(x，d)≥C(y，d)時，不用傳遞消息，因?yàn)楣?jié)點(diǎn)y 與節(jié)點(diǎn)d 的親密度不高，傳遞的意義不大.(4)當(dāng)C(x，d)=0，C(x，y)=0 時，x 與目的節(jié)點(diǎn)d 不相識且x 與y 也不相識，這種情況下y 與目的節(jié)點(diǎn)d 相識的可能性要大于x，但為了控制副本數(shù)量，暫不將這種情況列入消息傳遞.(5)每次消息傳遞前都要檢查下一節(jié)點(diǎn)是否已收到相同的消息，若下一節(jié)點(diǎn)已經(jīng)有相同的消息則不再重復(fù)發(fā)送，以便控制副本數(shù)量.

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)所用數(shù)據(jù)集和實(shí)驗(yàn)工具

選擇基于人類真實(shí)移動軌跡的MIT Reality 數(shù)據(jù)集［8］作為實(shí)驗(yàn)基礎(chǔ)，用VC++作為實(shí)驗(yàn)工具驗(yàn)證上述方法的有效性.在MIT Reality 項(xiàng)目中，收集的數(shù)據(jù)包括節(jié)點(diǎn)訪問地點(diǎn)記錄、節(jié)點(diǎn)間的接觸記錄(接觸開始和結(jié)束時間)和通話記錄等.

選擇2004 年10 月和11 月的數(shù)據(jù)進(jìn)行實(shí)驗(yàn).其中，10 月的數(shù)據(jù)指對相關(guān)信息的獲取，11 月根據(jù)已獲得的信息，基于節(jié)點(diǎn)間的親密度進(jìn)行數(shù)據(jù)遞交.首先要抽離數(shù)據(jù)集，創(chuàng)建每個人的活動記錄(即保存每個節(jié)點(diǎn)與哪些節(jié)點(diǎn)有過接觸)，然后統(tǒng)計(jì)各節(jié)點(diǎn)與其他節(jié)點(diǎn)的相處時長，最終獲得每個節(jié)點(diǎn)的親密度.初始節(jié)點(diǎn)數(shù)目為100，初始消息生存時間(TTL)為7 d.

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

4.2.1 與其他協(xié)議的比較

本實(shí)驗(yàn)將HIDBR 與DTN中現(xiàn)有的幾種路由協(xié)議從傳輸率(delivery ratio)、傳輸延遲(latency)、傳輸開銷(transmission consumption)幾個方面進(jìn)行比較，可以采用網(wǎng)絡(luò)中傳輸報(bào)文的平均副本數(shù)量評估路由算法的資源消耗.

4.2.2 TTL 的影響

通過變化消息在網(wǎng)絡(luò)中的生存時間觀察其對網(wǎng)絡(luò)性能產(chǎn)生的影響.

消息都具有生命周期，超過生命周期都將被刪除.本實(shí)驗(yàn)的使用數(shù)據(jù)為1個月，實(shí)驗(yàn)設(shè)置TTL 波動為1～7 d，實(shí)驗(yàn)結(jié)果見圖1～3.

結(jié)果分析:

(1)從圖中可見，隨著TTL 的增加，各個協(xié)議的消息傳輸成功率都呈上升趨勢.這是因?yàn)殡S著消息TTL 的增加，將有更多的消息到達(dá)目的地.但與此同時，網(wǎng)絡(luò)中的副本數(shù)在增加，資源開銷也在增加.由于一些原先在TTL 到期前不能到達(dá)目的地的消息在TTL 增大后能到達(dá)目的地，參與計(jì)算平均延遲的消息數(shù)量增加，所以平均傳輸延遲也呈上升趨勢.

(2)在這些協(xié)議中，由于蔓延路由協(xié)議窮舉所有可能的傳輸路徑，因此具有最高的消息傳輸成功率，且延遲最小，但其也具有最大開銷.HIDBR和基于社會網(wǎng)絡(luò)的Bubble 路由算法有針對性地發(fā)送信息，雖然消息傳輸成功率比蔓延路由協(xié)議稍低，但其傳輸開銷也大大降低.

(3)基于社會網(wǎng)絡(luò)的Bubble 路由算法中雖然把節(jié)點(diǎn)劃分了社區(qū)，但社區(qū)內(nèi)僅根據(jù)節(jié)點(diǎn)的活躍等級高低進(jìn)行消息復(fù)制，節(jié)點(diǎn)間的親疏遠(yuǎn)近關(guān)系卻沒有反映出來，有可能導(dǎo)致節(jié)點(diǎn)須經(jīng)過較長的時間才能把消息遞交給目的點(diǎn)，使得延遲相對較高，這也證實(shí)HIDBR 策略的有效性.

4.2.3 節(jié)點(diǎn)數(shù)量的影響

實(shí)驗(yàn)中的TTL 固定為7 d，通過變化實(shí)驗(yàn)節(jié)點(diǎn)數(shù)量觀察其對網(wǎng)絡(luò)性能的影響.設(shè)定初始節(jié)點(diǎn)數(shù)為10:

(1)從圖4中看出，隨著參與節(jié)點(diǎn)數(shù)量的增加，各協(xié)議的消息傳輸成功率呈上升趨勢.這是因?yàn)殡S著參與節(jié)點(diǎn)的增加，節(jié)點(diǎn)之間接觸的機(jī)會增多，數(shù)據(jù)傳輸機(jī)會增加，使得數(shù)據(jù)傳輸成功率及消息副本數(shù)量總體呈上升趨勢(圖5)，延遲總體呈下降趨勢(圖6).

(2)在所有協(xié)議中，蔓延路由協(xié)議的傳輸成功率最高.這是因?yàn)槠涑浞掷霉?jié)點(diǎn)間的連接機(jī)會，傳輸成功率比HIDBR和基于社會網(wǎng)絡(luò)的Bubble 路由算法都高，但是其開銷也最大.隨著參與節(jié)點(diǎn)的增加，后兩種算法的傳輸成功率較為接近.

(3)由圖6可知，基于社會網(wǎng)絡(luò)的Bubble 路由算法的延遲偏高.這是因?yàn)樵谙鬟f過程中所選擇的下一跳與目的節(jié)點(diǎn)的社會距離還不夠近，導(dǎo)致延遲偏高.隨著參與節(jié)點(diǎn)的增加，蔓延路由協(xié)議和HIDBR 的延遲總體呈下降趨勢，特別是參與節(jié)點(diǎn)的數(shù)量較以后下降越明顯.

5 結(jié)束語

本文通過實(shí)驗(yàn)驗(yàn)證HIDBR 的有效性.與現(xiàn)有的相關(guān)工作比較，HIDBR 在獲得與蔓延路由協(xié)議接近的消息傳輸成功率的同時，傳輸開銷大大降低，同時與基于社會網(wǎng)絡(luò)的Bubble 路由算法等社會網(wǎng)絡(luò)中的路由策略相比，可更好地實(shí)現(xiàn)數(shù)據(jù)傳輸成功率和傳輸開銷、傳輸延遲之間的平衡.總體而言，DTN 的路由算法雖已取得一定的研究成果，但仍然處于初步階段，特別是在理論研究及面向?qū)嶋H應(yīng)用方面還有很大的研究空間，路由問題依舊是DTN 的關(guān)鍵難點(diǎn)問題之一.

［1］FALL K.A delay-tolerant network architecture for challenged Internets［C］// Proc ACM SIGCOMM’03.Karlsruhe:ACM Pr，2003:27-34.

［2］JAIN S，F(xiàn)ALL K，PATRA R.Routeing in a delay-tolerant network［C］// Proc Conf on applications，Technologies，Architectures ＆ Protocols for Comput Commun (SIGCOMM’04).New York:ACM Pr，2004:145-158.

［3］張欣璐，劉廣鐘.無結(jié)構(gòu)對等網(wǎng)絡(luò)資源搜索算法［J］.上海海事大學(xué)學(xué)報(bào)，2008，29(2):78-81.

［4］熊樺，劉廣鐘.基于Sama 協(xié)議的移動Agent 組通信機(jī)制［J］.上海海事大學(xué)學(xué)報(bào)，2008，29(3):55-59.

［5］VAHDAT A，BECKER D.Epidemic routeing for partially connected Ad Hoc networks［D］.Durham，UK:Duke Univ，2000.

［6］LINDGREN A，DORIA A，SCHELEN O.Probabilistic routeing in intermittently connected networks［J］.Lect Notes in Comput Sci，2004:239-254.

［7］PAN H，CROWCROFT J，YONEKI E.Bubble Rap:social-based forwarding in delay-tolerant networks［C］// Proc 9th ACM Int Symp on Mobi-HOC.New York:ACM Pr，2008:241-250.

［8］EAGLE N，PENTLAND A，LAZER D.Inferring social network structure using mobile phone data［C］// Proc National Acad of Sci (PNAS).Massachusetts:Massachusetts Inst of Technol，2009:15274-15278.