延遲容忍網(wǎng)絡(luò)中基于地點(diǎn)偏好的社會感知多播路由協(xié)議設(shè)計(jì)

陳家旭,唐亞哲,胡成臣,王換招

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,710049,西安)

延遲容忍網(wǎng)絡(luò)中基于地點(diǎn)偏好的社會感知多播路由協(xié)議設(shè)計(jì)

陳家旭,唐亞哲,胡成臣,王換招

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,710049,西安)

根據(jù)延遲容忍網(wǎng)絡(luò)中人類運(yùn)動體現(xiàn)出的地點(diǎn)偏好特征,提出了一個(gè)社會感知路由協(xié)議,并采用了點(diǎn)到社區(qū)的多播方式。相應(yīng)地設(shè)計(jì)了節(jié)點(diǎn)分布式地獲取社區(qū)及其地理位置的方法,其中的分布式社區(qū)檢測算法獨(dú)立于路由協(xié)議,并具有靈活、準(zhǔn)確的特征。協(xié)議以文中發(fā)掘出的新的社會感知量——地點(diǎn)偏好為中心,將消息不斷地向目的社區(qū)所在的地理位置推進(jìn),在消息抵達(dá)社區(qū)成員節(jié)點(diǎn)之后利用社區(qū)結(jié)構(gòu)所蘊(yùn)含的強(qiáng)社會關(guān)系在社區(qū)內(nèi)部繼續(xù)傳送消息,并激活消息復(fù)制機(jī)制。本協(xié)議基于社會網(wǎng)絡(luò)分析,從地理位置的角度準(zhǔn)確預(yù)測節(jié)點(diǎn)運(yùn)動從而進(jìn)行路由。實(shí)驗(yàn)結(jié)果表明:本協(xié)議與兩個(gè)未采用地點(diǎn)偏好的社會感知路由協(xié)議相比,在不增加協(xié)議開銷的情況下提升了至少10%的發(fā)包成功率;在社區(qū)及其地理位置已知的場景下具有更好的性能,在保持最高的發(fā)包成功率的同時(shí)縮減了50%以上的開銷。

延遲容忍網(wǎng)絡(luò);地點(diǎn)偏好;社會感知;社區(qū)

在延遲容忍網(wǎng)絡(luò)中,由于缺乏端到端鏈路,路由協(xié)議通常采用存儲-攜帶-轉(zhuǎn)發(fā)的傳輸模式,即借助節(jié)點(diǎn)運(yùn)動造成的相遇來完成消息的傳輸。當(dāng)前延遲容忍網(wǎng)絡(luò)的場景大多是由人類攜帶的移動通信設(shè)備所組成,理解人類運(yùn)動并加以利用可以有效提升路由協(xié)議的性能。人們喜歡訪問對其具有吸引力的少數(shù)幾個(gè)地點(diǎn)[1],并在這些地點(diǎn)停留較長時(shí)間。人們對于這些地點(diǎn)的頻繁訪問和較長時(shí)間的停留在本文中被稱為地點(diǎn)偏好。地點(diǎn)偏好是造成人類運(yùn)動的接觸間隔時(shí)間呈冪律-指數(shù)分布的根本原因[2],因此在路由協(xié)議設(shè)計(jì)中把握人類運(yùn)動中地點(diǎn)偏好的特點(diǎn),可以更準(zhǔn)確地預(yù)測到節(jié)點(diǎn)之間的相遇,從而提升協(xié)議性能。

當(dāng)前對延遲容忍網(wǎng)絡(luò)路由協(xié)議的研究[3-8]雖然也注意到了理解人類運(yùn)動的重要性,但地點(diǎn)偏好的特征從未得到發(fā)掘與應(yīng)用。本文針對此問題,圍繞地點(diǎn)偏好并基于社區(qū)結(jié)構(gòu)來設(shè)計(jì)路由協(xié)議。社區(qū)是社會網(wǎng)絡(luò)中的重要概念,在由人類組成的延遲容忍網(wǎng)絡(luò)中,具有相同興趣的人們以極大的可能性共存于相近的地理位置,從而彼此之間產(chǎn)生較多的相遇而形成社區(qū)[8]。上述地理位置相當(dāng)于對社區(qū)成員有較大的吸引力,地點(diǎn)偏好特征依然存在。容易看出,處于同一社區(qū)的人更容易彼此碰面,反之,擁有一定程度的社會關(guān)系的人群才會形成社區(qū)。因此,社區(qū)內(nèi)消息的傳輸將比全網(wǎng)范圍內(nèi)消息傳輸更加便利。此外,社區(qū)的概念非常有利于在路由協(xié)議的設(shè)計(jì)中采用多播傳輸?shù)哪Ｊ?與單播傳輸模式相比,多播傳輸可明顯提高消息傳輸效率。本協(xié)議即采用了點(diǎn)到社區(qū)的多播方式。協(xié)議的原理是將消息不斷地向目的社區(qū)所對應(yīng)的地理位置推進(jìn),由于社區(qū)的所有成員都是消息的目的節(jié)點(diǎn),因此理論上可以提升協(xié)議的發(fā)包成功率,然而為得到此地理位置信息,會產(chǎn)生額外的開銷,表現(xiàn)在需要先得到網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),并由各社區(qū)成員所偏好訪問的地點(diǎn)坐標(biāo)近似估算出社區(qū)對應(yīng)的地理位置。本文將k-clique社區(qū)檢測算法[9]分布化,設(shè)計(jì)了相匹配的控制信息交換策略,根據(jù)這些信息分布式地估算出社區(qū)對應(yīng)的地理位置,從而能夠達(dá)到與未采用地點(diǎn)偏好的社會感知協(xié)議相比,在減少或不增加協(xié)議開銷的基礎(chǔ)上提高協(xié)議的發(fā)包成功率。在社區(qū)及其地理位置已知的場景下,本協(xié)議將不用進(jìn)行額外的控制信息交換而直接使用社區(qū)偏好地點(diǎn)的地理位置信息,可以在提升發(fā)包成功率的同時(shí)顯著降低協(xié)議開銷。

1 分布式社區(qū)檢測

文獻(xiàn)[9]中提出了采用k-clique社區(qū)檢測算法從社會網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū),然而運(yùn)行k-clique需要全網(wǎng)的接觸時(shí)長矩陣。本節(jié)介紹采用控制包輔助的方式來幫助各節(jié)點(diǎn)在本地搜集全局相關(guān)信息,從而實(shí)現(xiàn)分布式的k-clique社區(qū)檢測算法。

節(jié)點(diǎn)n在本地保存它與全部節(jié)點(diǎn)的接觸時(shí)長Dn,它所知道的全網(wǎng)所有節(jié)點(diǎn)的接觸時(shí)長矩陣Mn以及用來存儲社區(qū)檢測結(jié)果的Rn。當(dāng)節(jié)點(diǎn)n遇到其他節(jié)點(diǎn)(例如節(jié)點(diǎn)i)時(shí),彼此交換控制信息。節(jié)點(diǎn)n產(chǎn)生的控制信息包含節(jié)點(diǎn)id和Mn。在節(jié)點(diǎn)n產(chǎn)生控制信息之前,用最新的Dn信息去更新本地的Mn,以保證所交換的接觸時(shí)長矩陣中含有當(dāng)前節(jié)點(diǎn)的最新接觸時(shí)長信息。在節(jié)點(diǎn)n收到對方的控制信息后,用本地的Mn與收到的Mi中每一個(gè)元素的較大值來更新本地的Mn。節(jié)點(diǎn)n通過與其他節(jié)點(diǎn)不斷地進(jìn)行控制信息交換來保證本地的Mn含有它所能得到的盡可能準(zhǔn)確的全網(wǎng)接觸時(shí)長信息,以便隨時(shí)在本地執(zhí)行k-clique社區(qū)檢測算法,具體的偽代碼如下。

for alld∈Mn

ifd>=Tththen∥Tth為接觸時(shí)長的權(quán)重閾值

d=1

else

d=0

end if

end for

在Mn中找到所有大小為k的完全子圖(k-clique)

for allk-clique ∈Mn

Rn←k-clique

if ?k′-clique s.t.(k′-clique中的節(jié)點(diǎn)數(shù)量) ∩ (Rn里任意一個(gè)大小為k的完全子圖中的節(jié)點(diǎn)數(shù)量)=k-1 then

Rn←(在k′-clique中但不在此大小為k的完全子圖中的節(jié)點(diǎn))

end if

end for

刪除Rn中重復(fù)的社區(qū)

雖然k-clique社區(qū)檢測算法復(fù)雜度較大,但在應(yīng)用于較少節(jié)點(diǎn)組成的實(shí)驗(yàn)場景中時(shí)(100人以下,例如文獻(xiàn)[3]中用來運(yùn)行k-clique的若干實(shí)際場景)并非大規(guī)模網(wǎng)絡(luò),因此暫不考慮算法復(fù)雜度帶來的影響。

執(zhí)行k-clique所需信息已存于節(jié)點(diǎn)本地,且隨網(wǎng)絡(luò)運(yùn)行不斷更新,因此本文算法具有靈活性,即可以在任何時(shí)間運(yùn)行并多次運(yùn)行。本文算法檢測結(jié)果的準(zhǔn)確性將通過把本文算法對人類真實(shí)運(yùn)動數(shù)據(jù)[10]的檢測結(jié)果與原k-clique算法及Hui等在文獻(xiàn)[11]中提出的另一種分布式k-clique社區(qū)檢測算法的檢測結(jié)果進(jìn)行對比驗(yàn)證。使用Jaccard指數(shù)來描述兩個(gè)社區(qū)結(jié)構(gòu)(Γj和Γi)的相似性,即

(1)

式中:Γi是社區(qū)i的成員集合,|Γi|為集合Γi的勢,值為Γi中成員的數(shù)量。這里Γi為原k-clique社區(qū)檢測算法檢測出的社區(qū),Γj則是被評估的分布式k-clique社區(qū)檢測算法所檢測出的社區(qū)。對于通過原k-clique算法所檢測到的規(guī)模最大的社區(qū)內(nèi)的所有成員,均用本文提出的分布式k-clique算法與文獻(xiàn)[11]中的分布式k-clique算法分別對自己所在社區(qū)進(jìn)行檢測,并將結(jié)果與原k-clique社區(qū)檢測算法進(jìn)行比較并計(jì)算出Jaccard指數(shù),如圖1所示。檢測中采用的運(yùn)動數(shù)據(jù)[10]是2006年INFOCOM會議采集到的,包括了78個(gè)攜帶移動通信設(shè)備的與會者在3天的相遇情況。3個(gè)k-clique算法參數(shù)取值相同,即k=4,接觸時(shí)長的權(quán)重閾值為10ks。

圖1 兩種分布式k-clique社區(qū)檢測算法的對比

圖1中,橫坐標(biāo)代表此圖所示社區(qū)的成員節(jié)點(diǎn)id,為原k-clique算法的檢測結(jié)果。縱坐標(biāo)分別是本文提出的分布式k-clique算法及文獻(xiàn)[11]提出的分布式k-clique算法與原k-clique算法之間的Jaccard指數(shù)。由圖1可見,本文所設(shè)計(jì)的分布式k-clique社區(qū)檢測算法,在節(jié)點(diǎn)檢測自己所在社區(qū)的情況下,基本上可以得到與原k-clique社區(qū)檢測算法完全一致的結(jié)果。這是因?yàn)樯鐓^(qū)內(nèi)節(jié)點(diǎn)相遇頻繁,能夠及時(shí)并準(zhǔn)確地更新社區(qū)內(nèi)成員的接觸信息。文獻(xiàn)[11]中的分布式算法顯示出與原k-clique算法較明顯的偏差。

2 路由協(xié)議設(shè)計(jì)

有了分布式k-clique社區(qū)檢測算法,還需要設(shè)計(jì)相匹配的控制信息交換策略,才能使各節(jié)點(diǎn)根據(jù)交換所得信息分布式地估算出社區(qū)對應(yīng)的地理位置,從而基于地點(diǎn)偏好實(shí)現(xiàn)路由協(xié)議。分布式k-clique算法和控制信息交換策略雖然在功能上有所區(qū)分,但實(shí)際上可以由同樣的控制包攜帶,而分布式社區(qū)地理位置生成算法也是緊跟在分布式k-clique之后,在各節(jié)點(diǎn)本地執(zhí)行,因此這兩個(gè)功能可以在同一模塊中實(shí)現(xiàn)。節(jié)點(diǎn)n只需在本地同時(shí)保存最常訪問的若干地點(diǎn)的坐標(biāo)及其概率的數(shù)據(jù)結(jié)構(gòu)Cn以及它所知道的所有節(jié)點(diǎn)的Cx(x為任意節(jié)點(diǎn))信息的矩陣Fn,在與其他節(jié)點(diǎn)相遇而進(jìn)行控制信息交換時(shí),將Cn附在它產(chǎn)生的控制信息中。在收到節(jié)點(diǎn)i發(fā)來的控制信息之后,將Fn中每一個(gè)節(jié)點(diǎn)的最常訪問地點(diǎn)的坐標(biāo)及概率進(jìn)行更新,將Fi與Fn中對應(yīng)節(jié)點(diǎn)的地點(diǎn)偏好信息按照權(quán)重重新排序,保留權(quán)重最大的若干個(gè)。

在節(jié)點(diǎn)n進(jìn)行完分布式k-clique算法之后,根據(jù)所檢測到的各社區(qū)的所有成員的Cy(y為社區(qū)成員節(jié)點(diǎn)id)信息(從Fn中讀取),取Cy中各熱點(diǎn)的加權(quán)平均值近似地作為該社區(qū)在地理上的位置,其中權(quán)重值為對應(yīng)的節(jié)點(diǎn)訪問該熱點(diǎn)的概率。至此,節(jié)點(diǎn)n能夠大致估算出網(wǎng)絡(luò)中存在的社區(qū)及每個(gè)社區(qū)對應(yīng)的地理位置所在。估算此地理位置的偽代碼如下。

for allRn中的社區(qū)

for all 此社區(qū)的成員節(jié)點(diǎn)

L←Fn中這些節(jié)點(diǎn)對應(yīng)信息的加權(quán)平均值

end for

end for

在上述準(zhǔn)備工作的基礎(chǔ)上,可以設(shè)計(jì)并實(shí)現(xiàn)基于地點(diǎn)偏好的路由協(xié)議,協(xié)議在兩節(jié)點(diǎn)相遇時(shí)生效。為使用消息的目的社區(qū)對應(yīng)的地理位置(以L表示)信息來實(shí)現(xiàn)地點(diǎn)偏好的設(shè)計(jì),相遇的兩節(jié)點(diǎn)應(yīng)先交換Landmark Vector控制信息。節(jié)點(diǎn)n產(chǎn)生的Landmark Vector包括了節(jié)點(diǎn)id;節(jié)點(diǎn)n下一次停止運(yùn)動所在的地點(diǎn)dest(n);節(jié)點(diǎn)n在從當(dāng)前位置到dest(n)的運(yùn)動中所能到達(dá)的與L的最近距離distance(n,L);節(jié)點(diǎn)n所處的社區(qū)標(biāo)簽com(n);以及對于n緩存中的每一個(gè)消息m的id及其目的社區(qū)標(biāo)簽label(m)。當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí),它們首先銷毀各自緩存中所有超出生存時(shí)間的消息,然后交換Landmark Vector。對于兩個(gè)節(jié)點(diǎn)緩存中的每一個(gè)消息,如果對方節(jié)點(diǎn)是此消息的目的節(jié)點(diǎn)并且尚未收到過此消息,那么應(yīng)將此消息復(fù)制給對方(留副本),收到該消息的節(jié)點(diǎn)將此消息id記錄到已收到消息的id集合中并投遞到(不留副本)之上的應(yīng)用層,然后根據(jù)協(xié)議選擇當(dāng)前消息下一跳的中繼節(jié)點(diǎn)。

協(xié)議采用了點(diǎn)到社區(qū)的多播方式,即目的社區(qū)的所有成員都是消息的目的節(jié)點(diǎn)。消息在生成的時(shí)候會標(biāo)記上其目的社區(qū)的標(biāo)簽label(m),以此來協(xié)助節(jié)點(diǎn)辨別是否應(yīng)接收該消息。同時(shí),節(jié)點(diǎn)n在本地對自己所在社區(qū)的標(biāo)簽以com(n)表示。通過這種方式,節(jié)點(diǎn)可以判斷自己是否應(yīng)該接收某消息。協(xié)議主體思想的偽代碼如下:

if com(i)=label(m) and com(j)=label(m) then

copy(m)

end if

if com(i)=label(m) and com(j)≠label(m) then

new_carrier(m)←i

end if

if com(i)≠label(m) and com(j)=label(m) then

new_carrier(m)←j

end if

if com(i)≠label(m) and com(j)≠label(m) then

if distance(i,L)

new_carrier(m)←i

end if

if distance(i,L)>distance(j,L) then

new_carrier(m)←j

end if

end if

其中copy(m)代表將消息m從當(dāng)前的攜帶者復(fù)制到另一個(gè)節(jié)點(diǎn)中,而new_carrier(m)代表此次相遇后消息m新的攜帶者,即另一方不應(yīng)再攜帶m。

該策略決定了消息在傳輸過程中每一跳的中繼節(jié)點(diǎn)。可見在本協(xié)議中,“消息目的社區(qū)的成員節(jié)點(diǎn)”比“地點(diǎn)偏好”有更高的優(yōu)先級。因?yàn)椤跋⒛康纳鐓^(qū)的成員節(jié)點(diǎn)”意味著該節(jié)點(diǎn)與非社區(qū)成員節(jié)點(diǎn)相比,有更大的可能性遇到目的社區(qū)的其他成員節(jié)點(diǎn)。僅當(dāng)相遇的兩節(jié)點(diǎn)都不屬于消息目的社區(qū)的成員節(jié)點(diǎn)時(shí),協(xié)議才依照“地點(diǎn)偏好”選擇消息的下一跳中繼節(jié)點(diǎn),即由兩節(jié)點(diǎn)中在當(dāng)前運(yùn)動階段可以到達(dá)更接近L的節(jié)點(diǎn)來攜帶消息。這樣的設(shè)計(jì)原理可保證將消息不斷地向其目的社區(qū)所在的地理位置推進(jìn),直到其中一個(gè)目的節(jié)點(diǎn)收到此消息。之后由此節(jié)點(diǎn)攜帶消息,并在遇到同樣屬于目的社區(qū)的節(jié)點(diǎn)時(shí)激活消息的復(fù)制機(jī)制(上述偽代碼的第2行),以加快消息的傳播。

3 模擬及性能評估

本節(jié)對上一節(jié)所提出的路由協(xié)議進(jìn)行了編程實(shí)現(xiàn),并與兩個(gè)未使用地點(diǎn)偏好的社會感知路由協(xié)議SocialCast[8]和SGBR[7]進(jìn)行了性能對比。其中SocialCast采用的是發(fā)布/訂閱架構(gòu)的多播模式,假設(shè)了社區(qū)與興趣之間的一一映射關(guān)系,因此SocialCast可以直接采用本文所定義的點(diǎn)到社區(qū)的多播模式。SGBR雖然采用了單播的方式,但由于各個(gè)消息獨(dú)立選擇路由,將SGBR擴(kuò)展為本文中的點(diǎn)到社區(qū)的多播模式不會影響SGBR的性能。

采用開銷和發(fā)包成功率兩個(gè)量來衡量路由協(xié)議的性能。開銷指成功發(fā)送一個(gè)數(shù)據(jù)包所需要的代價(jià),表征了路由協(xié)議的效率,計(jì)算式為c=(Rc+Dd)/Rd,其中Rc為收到的控制包數(shù),Dd為生成的數(shù)據(jù)包副本數(shù),Rd為收到的數(shù)據(jù)包數(shù)。發(fā)包成功率是指發(fā)送出的數(shù)據(jù)包被成功接收的概率,衡量了路由協(xié)議的有效性,計(jì)算式為p=Rd/Gd,其中Gd為生成的數(shù)據(jù)包數(shù)。

模擬中使用SWIM[1]來刻畫節(jié)點(diǎn)運(yùn)動,因?yàn)镾WIM是一個(gè)優(yōu)秀的人類運(yùn)動模型,表現(xiàn)在其能夠重現(xiàn)與實(shí)際人類運(yùn)動相匹配的統(tǒng)計(jì)量,例如接觸間隔時(shí)間、接觸時(shí)長和接觸數(shù)量;能夠還原指定網(wǎng)絡(luò)場景下的社區(qū)結(jié)構(gòu);能夠用來準(zhǔn)確預(yù)測路由協(xié)議在真實(shí)場景下的性能[1]。網(wǎng)絡(luò)區(qū)域?yàn)? km×5 km,其中有100個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的傳輸半徑為250m,保證了稀疏的節(jié)點(diǎn)密度從而形成延遲容忍網(wǎng)絡(luò)的環(huán)境。SWIM的相關(guān)系數(shù)取值為0.25,停止時(shí)間服從[10s,1 440s]范圍內(nèi)斜率為1.45的冪律分布,運(yùn)動時(shí)間為10s。模擬時(shí)間設(shè)置為3d(259 200s)。

為防止SWIM生成不明確的社會關(guān)系,節(jié)點(diǎn)的家并非在網(wǎng)絡(luò)區(qū)域上隨機(jī)平均選取。在100個(gè)節(jié)點(diǎn)中隨機(jī)選擇20個(gè)節(jié)點(diǎn),令它們的家相距較近,從而這些節(jié)點(diǎn)中的大部分將屬于同一社區(qū),且此社區(qū)的規(guī)模為20左右。為給SWIM模型以充分的時(shí)間來形成穩(wěn)定的社區(qū)結(jié)構(gòu),在第200ks時(shí),系統(tǒng)進(jìn)行k-clique社區(qū)檢測算法,之后賦給規(guī)模最大的社區(qū)一個(gè)標(biāo)簽。在第200ks時(shí),各節(jié)點(diǎn)執(zhí)行分布式k-clique社區(qū)檢測算法。Δt之后,網(wǎng)絡(luò)中開始產(chǎn)生數(shù)據(jù)包。其中Δt設(shè)為較小的值即可,并不影響結(jié)果。發(fā)包持續(xù)時(shí)間為1 ks,發(fā)包間隔為60s,與文獻(xiàn)[8]中相同,隨機(jī)選擇半數(shù)的節(jié)點(diǎn)為發(fā)包者,包中附有標(biāo)記著目的社區(qū)的標(biāo)簽,該社區(qū)的所有成員都將是接收者。由于發(fā)包節(jié)點(diǎn)是從所有節(jié)點(diǎn)之中隨機(jī)選取,目的節(jié)點(diǎn)也主要是由初始被設(shè)置為離家較近的隨機(jī)選擇的20個(gè)節(jié)點(diǎn)中的大部分組成,因此這樣設(shè)定可以保證包的源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的一種隨機(jī)的社會關(guān)系,而不會影響到協(xié)議的性能。k-clique算法的k取值為4,接觸時(shí)長的權(quán)重閾值為60ks。假設(shè)所有節(jié)點(diǎn)緩存足夠大。實(shí)驗(yàn)在用C++編寫的離散事件模擬器中運(yùn)行。

路由協(xié)議中包與其副本的總數(shù)r在本文提出的協(xié)議中設(shè)置為4,在SocialCast中設(shè)置為5,而在SGBR中設(shè)置為32。本協(xié)議并不依賴于復(fù)制機(jī)制,故取3個(gè)協(xié)議中的最小值,由于采用了平均分配副本數(shù)量的機(jī)制(即相遇雙方節(jié)點(diǎn)在復(fù)制包的時(shí)候各持有半數(shù)的包副本,因此r需設(shè)置為2的冪次方),故r取值為4。SocialCast對復(fù)制機(jī)制的依賴性次之,同時(shí)為避免SocialCast與本協(xié)議對比時(shí)由于r值過小的原因而對協(xié)議性能造成的影響,故r取略大于4的值。SGBR較依賴復(fù)制機(jī)制并采用了平均分配副本數(shù)量的機(jī)制,從而r設(shè)為較大值32(即25)。SocialCast中的其他參數(shù)如ωcdc、ωcol、λ和ε(參數(shù)定義見文獻(xiàn)[8])都取了與文獻(xiàn)[8]中相同的值。同樣地,SGBR中的其他參數(shù)如α、γ、Cth和Dth(參數(shù)定義見文獻(xiàn)[7])也都取了與文獻(xiàn)[7]中相同的值。對于每個(gè)實(shí)驗(yàn)數(shù)據(jù),取20次運(yùn)行結(jié)果的平均值,其中每次運(yùn)行都采用了不同的隨機(jī)數(shù)種子。協(xié)議性能對比結(jié)果如圖2、圖3所示。

圖2 3個(gè)路由協(xié)議的開銷

圖3 3個(gè)路由協(xié)議的發(fā)包成功率

雖然延遲容忍網(wǎng)絡(luò)中消息傳遞對運(yùn)動的依賴性導(dǎo)致Rd直接受節(jié)點(diǎn)運(yùn)動的影響,但是在運(yùn)動模型及參數(shù)都確定的情況下,可以認(rèn)為Rd是運(yùn)動模型的無關(guān)變量。然而,協(xié)議對Rd卻可產(chǎn)生較大影響。假設(shè)在不考慮生存時(shí)間的情況下數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)的平均延遲為d,協(xié)議的參數(shù)中將數(shù)據(jù)包的生存時(shí)間設(shè)置為H,那么Rd與H和d的關(guān)系如下:當(dāng)H≤d時(shí),大部分?jǐn)?shù)據(jù)包在還沒有到達(dá)端到端延遲期望值的情況下就已經(jīng)因?yàn)榈竭_(dá)生存時(shí)間而被銷毀,這將導(dǎo)致很低的Rd值。從H>d開始,Rd值將顯著增加,但當(dāng)H增加到一定程度之后,社區(qū)中相對可達(dá)的節(jié)點(diǎn)都已經(jīng)收到了數(shù)據(jù)包,Rd值隨H的增幅又將變緩慢,因而開銷c=(Rc+Dd)/Rd≈Rc/Rd在一定范圍內(nèi)呈現(xiàn)出如圖2所示的與Rd大致成反比的關(guān)系。同理,發(fā)包成功率p=Rd/Gd中,Gd在模擬參數(shù)指定的情況下為常量,因此p與Rd成正比。結(jié)合Rd與H的關(guān)系,即有圖3所描述的發(fā)包成功率隨生存時(shí)間的變化情況。

前述場景中社區(qū)對應(yīng)的地理位置為未知信息,并通過節(jié)點(diǎn)交換控制信息分布式地獲得。實(shí)際上,在其他場景,例如人們熟悉的環(huán)境中,社區(qū)及其對應(yīng)的地理位置為已知信息,不再需要分布式社區(qū)檢測與控制信息交換,本協(xié)議的開銷可以大大降低,從而相對于其他協(xié)議體現(xiàn)出更明顯的優(yōu)勢。作者同樣進(jìn)行了這種場景下的模擬,即將運(yùn)動模型從SWIM換成HCMM[12]再次觀測3個(gè)協(xié)議的性能。HCMM刻畫了社區(qū)及對應(yīng)地理位置已知的網(wǎng)絡(luò)環(huán)境,設(shè)置模擬時(shí)間為28 800s,發(fā)包時(shí)間為3～4 ks,運(yùn)動速度服從1～6 m/s的平均分布,停止時(shí)間為10s,網(wǎng)絡(luò)中社區(qū)數(shù)量為4,本協(xié)議中包不再采用復(fù)制機(jī)制,其他參數(shù)均與上述場景相同。限于篇幅,此處并未給出具體圖示,然而模擬結(jié)果表明在不需要主動獲得社區(qū)及所對應(yīng)的地理位置的場景下,與SocialCast及SGBR相比,本協(xié)議可以在保持最高發(fā)包成功率的基礎(chǔ)上縮減協(xié)議開銷達(dá)50%以上。

4 結(jié) 論

針對延遲容忍網(wǎng)絡(luò)中人類運(yùn)動的地點(diǎn)偏好特征,提出了一個(gè)社會感知多播路由協(xié)議。協(xié)議將消息逐漸向目的社區(qū)所在的地理位置傳送,當(dāng)?shù)竭_(dá)其中一個(gè)目的節(jié)點(diǎn)后,利用社區(qū)之間的強(qiáng)社會關(guān)系,由此節(jié)點(diǎn)一直攜帶并激活復(fù)制機(jī)制,以便于其他目的節(jié)點(diǎn)收到消息。實(shí)驗(yàn)結(jié)果表明,與兩個(gè)未采用地點(diǎn)偏好的社會感知路由協(xié)議相比,本協(xié)議在不增加開銷的情況下提升了發(fā)包成功率,而在無需主動獲得社區(qū)地理位置信息的場景中,可在保持最高發(fā)包成功率的同時(shí)大幅降低開銷。

[1] KOSTA S,MEI A,STEFA J.Large-scale synthetic social mobile networks with SWIM [J].IEEE Transactions on Mobile Computing,2014,13(1): 116-129.

[2] MAITI R R,MALLYA A,GANGULY N.Characterizing Mobility Models for Human Movement [J/OL].(2013-02-19) [2013-10-15].http:∥web.engr.illinois.edu/～amallya2/trial/aCleanerWebsite/files/MobilityModel_CHANTS.pdf.

[3] HUI Pan,CROWCROFT J,YONEKI E.Bubble rap: social-based forwarding in delay-tolerant networks [J].IEEE Transactions on Mobile Computing,2011,10(11): 1576-1589.

[4] GAO Wei,CAO Guohong.User-centric data dissemination in disruption tolerant networks [C]∥Proceedings of the 30th Conference on Computer Communications.Piscataway,NJ,USA: IEEE,2011: 3119-3127.

[5] LI Feng,WU Jie.Mops: providing content-based service in disruption-tolerant networks [C]∥Proceedings of the 29th IEEE International Conference on Distributed Computing Systems.Piscataway,NJ,USA: IEEE,2009: 526-533.

[6] BULUT E,SZYMANSKI B K.Friendship based routing in delay tolerant mobile social networks [C]∥Proceedings of the Global Telecommunications Conference.Piscataway,NJ,USA: IEEE,2010: 1-5.

[7] ABDELKADER T,NAIK K,NAYAK A,et al.SGBR: a routing protocol for delay tolerant networks using social grouping [J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12): 2472-2481.

[8] COSTA P,MASCOLO C,MUSOLESI M,et al.Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks [J].IEEE Journal on Selected Areas in Communications,2008,26(5): 748-760.

[9] PALLA G,DERNYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society [J].Nature,2005,435(7043): 814-818.

[10]HUI Pan,SCOTT J,CHAINTREAU A.CRAWDAD metadata: cambridge/haggle/imote/infocom2006 [EB/OL].(2009-05-29) [2013-07-30].http:∥crawdad.cs.dartmouth.dartmouth.edu/cambridge/haggle/imote/infocom2006.

[11]HUI Pan,YONEKI E,CHAN S Y,et al.Distributed community detection in delay tolerant networks [C]∥Proceedings of the 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture.New York,USA: ACM,2007: 7.

[12]BOLDRINI C,PASSARELLA A.HCMM: modeling spatial and temporal properties of human mobility driven by users’ social relationships [J].Computer Communications,2010,33(9): 1056-1074.

(編輯 武紅江)

DesignofaSocial-AwareMulticastRoutingProtocolBasedonLocationPreferenceinDelayTolerantNetworks

CHEN Jiaxu,TANG Yazhe,HU Chengchen,WANG Huanzhao

(Department of Computer Science and Technology,Xi’an Jiaotong University,Xi’an 710049,China)

A social-aware routing protocol utilizing a ‘one-to-community’ multicast scheme is proposed.The protocol is based on the characteristics of location preference in human mobility in delay tolerant networks.A distributed method is designed to obtain the community structure and its geographical position,where the distributed community detection algorithm is independent of the routing protocol and has features of flexibility and accuracy.The protocol concentrates on the exploited social-aware metric,namely location preference,and forwards messages towards the geographical position of the destination community.Once the message arrives one of the destination nodes,strong social relations inside the destination community can be utilized to accelerate the message’s arrival at other destination nodes by means of duplicating replicas.The protocol accurately predicts node mobility in geography based on social network analysis.Simulation results given by comparing the proposed protocol with two existing social-aware routing protocols without using location preference show that the packet delivery ratio raises at least 10% without increasing the cost.It is also observed that the proposed protocol has better performance in the scenario where communities and their geographical positions are known.The cost reduces more than 50% while the packet delivery ratio is the highest.

delay tolerant networks; location preference; social-aware; community

2014-01-12。

陳家旭(1983—),男,博士生;胡成臣(通信作者),男,副教授。

國家自然科學(xué)基金資助項(xiàng)目(61170245)。

時(shí)間:2014-05-30

10.7652/xjtuxb201406003

TP393

:A

:0253-987X(2014)06-0013-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.003.html