馮濤，劉廣鐘

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

0 引言

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

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

1 相關(guān)工作

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

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

蔓延路由協(xié)議的思想是把所要發(fā)送的報(bào)文給它所有的鄰居節(jié)點(diǎn).這種路由方式意味著:只要節(jié)點(diǎn)的緩存足夠大，隨著節(jié)點(diǎn)之間的不斷“接觸”，數(shù)據(jù)就會(huì)從源端開始像病毒那樣傳播到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，從而大大增加網(wǎng)路負(fù)擔(dān)，造成網(wǎng)絡(luò)擁塞.所以，現(xiàn)實(shí)情況下，由于緩存空間、能量、帶寬等資源的限制，傳染路由性能會(huì)嚴(yán)重降級(jí)，很難適應(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ā)消息不同，概率路由中的每個(gè)節(jié)點(diǎn)將會(huì)估計(jì)到達(dá)目的節(jié)點(diǎn)的概率.如果所遇節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率比自己的大，則將報(bào)文轉(zhuǎn)發(fā)給它，否則將自己傳輸或等待其他節(jié)點(diǎn).與蔓延路由相比，網(wǎng)絡(luò)開銷降低，但與此同時(shí)，延遲會(huì)增加，報(bào)文遞交率會(huì)降低.

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

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

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

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

2.1 親密度定義

提出親密度的定義如下:

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

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

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

2.2 獲知親密度的方式

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

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

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

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

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

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

社會(huì)網(wǎng)絡(luò)模型:例如，對(duì)于一個(gè)城市的社會(huì)網(wǎng)絡(luò)，可以分為無(wú)數(shù)個(gè)人，那么抽象為社會(huì)網(wǎng)絡(luò)模型，可以將這種網(wǎng)絡(luò)的每個(gè)人看成是網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)之間的通信利用所攜帶的通信設(shè)備進(jìn)行.可以看出，某些時(shí)刻社會(huì)網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)之間通信可能具有間歇，所有這種網(wǎng)絡(luò)表現(xiàn)出DTN 的特點(diǎn).本課題就是對(duì)這樣的社會(huì)網(wǎng)絡(luò)進(jìn)行抽象，將攜帶移動(dòng)通信設(shè)備的人看作網(wǎng)絡(luò)中的節(jié)點(diǎn).利用親密度的不同輔助節(jié)點(diǎn)間數(shù)據(jù)的傳輸，提出在DTN 社會(huì)網(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)號(hào);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 對(duì)下一節(jié)點(diǎn)y 的消息遞交方法如下:(1)當(dāng)y 節(jié)點(diǎn)即為目的節(jié)點(diǎn)d 時(shí)，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 時(shí)，分別比較x和y 與d 的親密度，若C(x，d)＜C(y，d)，x 節(jié)點(diǎn)將消息m 發(fā)送給y 節(jié)點(diǎn)，說(shuō)明與x 相比，y 與目的節(jié)點(diǎn)的親密度更高，y 與d 在上1個(gè)周期內(nèi)相處的時(shí)間更長(zhǎng)，能把消息傳遞給d 的可能性也更大.(3)當(dāng)y 節(jié)點(diǎn)不是目的節(jié)點(diǎn)d 且C(x，d)≥C(y，d)時(shí)，不用傳遞消息，因?yàn)楣?jié)點(diǎn)y 與節(jié)點(diǎn)d 的親密度不高，傳遞的意義不大.(4)當(dāng)C(x，d)=0，C(x，y)=0 時(shí)，x 與目的節(jié)點(diǎn)d 不相識(shí)且x 與y 也不相識(shí)，這種情況下y 與目的節(jié)點(diǎn)d 相識(shí)的可能性要大于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í)移動(dòng)軌跡的MIT Reality 數(shù)據(jù)集［8］作為實(shí)驗(yàn)基礎(chǔ)，用VC++作為實(shí)驗(yàn)工具驗(yàn)證上述方法的有效性.在MIT Reality 項(xiàng)目中，收集的數(shù)據(jù)包括節(jié)點(diǎn)訪問(wèn)地點(diǎn)記錄、節(jié)點(diǎn)間的接觸記錄(接觸開始和結(jié)束時(shí)間)和通話記錄等.

選擇2004 年10 月和11 月的數(shù)據(jù)進(jìn)行實(shí)驗(yàn).其中，10 月的數(shù)據(jù)指對(duì)相關(guān)信息的獲取，11 月根據(jù)已獲得的信息，基于節(jié)點(diǎn)間的親密度進(jìn)行數(shù)據(jù)遞交.首先要抽離數(shù)據(jù)集，創(chuàng)建每個(gè)人的活動(dòng)記錄(即保存每個(gè)節(jié)點(diǎn)與哪些節(jié)點(diǎn)有過(guò)接觸)，然后統(tǒng)計(jì)各節(jié)點(diǎn)與其他節(jié)點(diǎn)的相處時(shí)長(zhǎng)，最終獲得每個(gè)節(jié)點(diǎn)的親密度.初始節(jié)點(diǎn)數(shù)目為100，初始消息生存時(shí)間(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)幾個(gè)方面進(jìn)行比較，可以采用網(wǎng)絡(luò)中傳輸報(bào)文的平均副本數(shù)量評(píng)估路由算法的資源消耗.

4.2.2 TTL 的影響

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

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

結(jié)果分析:

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

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

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

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

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

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

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

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

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

本文通過(guò)實(shí)驗(yàn)驗(yàn)證HIDBR 的有效性.與現(xiàn)有的相關(guān)工作比較，HIDBR 在獲得與蔓延路由協(xié)議接近的消息傳輸成功率的同時(shí)，傳輸開銷大大降低，同時(shí)與基于社會(huì)網(wǎng)絡(luò)的Bubble 路由算法等社會(huì)網(wǎng)絡(luò)中的路由策略相比，可更好地實(shí)現(xiàn)數(shù)據(jù)傳輸成功率和傳輸開銷、傳輸延遲之間的平衡.總體而言，DTN 的路由算法雖已取得一定的研究成果，但仍然處于初步階段，特別是在理論研究及面向?qū)嶋H應(yīng)用方面還有很大的研究空間，路由問(wèn)題依舊是DTN 的關(guān)鍵難點(diǎn)問(wè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］張欣璐，劉廣鐘.無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)資源搜索算法［J］.上海海事大學(xué)學(xué)報(bào)，2008，29(2):78-81.

［4］熊樺，劉廣鐘.基于Sama 協(xié)議的移動(dòng)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.