采用傳遞概率與社會(huì)網(wǎng)絡(luò)分析的延遲容忍網(wǎng)絡(luò)路由

楊沫,由磊,李冰,趙建軍

(天津大學(xué)電子信息工程學(xué)院,300072,天津)

?

采用傳遞概率與社會(huì)網(wǎng)絡(luò)分析的延遲容忍網(wǎng)絡(luò)路由

楊沫,由磊,李冰,趙建軍

(天津大學(xué)電子信息工程學(xué)院,300072,天津)

結(jié)合了傳遞概率與社會(huì)網(wǎng)絡(luò)分析的路由設(shè)計(jì),可以充分利用網(wǎng)絡(luò)中節(jié)點(diǎn)的運(yùn)動(dòng)特性增強(qiáng)端到端的消息傳輸質(zhì)量。通過(guò)對(duì)節(jié)點(diǎn)進(jìn)行相遇歷史信息分析和社會(huì)關(guān)系分析,提出了基于傳遞概率與社會(huì)網(wǎng)絡(luò)分析的延遲容忍網(wǎng)絡(luò)路由(RPRSA)。相遇歷史信息分析是通過(guò)節(jié)點(diǎn)在相遇時(shí)進(jìn)行獨(dú)立概率計(jì)算和彼此概率信息交換,使得節(jié)點(diǎn)可以預(yù)測(cè)它在短期內(nèi)的移動(dòng)特性;社會(huì)關(guān)系分析是通過(guò)節(jié)點(diǎn)在長(zhǎng)期內(nèi)的移動(dòng)所形成的關(guān)系親疏程度,使得節(jié)點(diǎn)可以預(yù)測(cè)它的長(zhǎng)期運(yùn)動(dòng)規(guī)律。仿真結(jié)果表明,該路由算法能夠很好地利用節(jié)點(diǎn)的運(yùn)動(dòng)特性,保證弱社會(huì)關(guān)系節(jié)點(diǎn)和孤立節(jié)點(diǎn)有更好的消息傳輸質(zhì)量,更好地提高節(jié)點(diǎn)端到端的消息傳輸質(zhì)量。

延遲容忍網(wǎng)絡(luò);社會(huì)網(wǎng)絡(luò)分析;傳遞概率;路由設(shè)計(jì)

延遲容忍網(wǎng)絡(luò)[1-2](delay tolerant network,DTN)是一類缺乏穩(wěn)定、持續(xù)端到端連接的網(wǎng)絡(luò)組織結(jié)構(gòu),這類網(wǎng)絡(luò)的路由被稱之為DTN路由,如果在DTN路由中采取了社會(huì)網(wǎng)絡(luò)的分析方法,即為社會(huì)性DTN路由,其中典型的路由有標(biāo)簽路由(Lable)、升序路由(Rank)、冒泡路由(Bubble Rap,下文簡(jiǎn)化為Bubble)[3-4]等。Label直接利用社區(qū)傳遞的方式提高傳輸質(zhì)量;Rank通過(guò)高流行度節(jié)點(diǎn)擴(kuò)散消息的方式提高傳輸質(zhì)量;Bubble通過(guò)利用高流行度節(jié)點(diǎn)向社區(qū)擴(kuò)散消息的方式提高傳輸質(zhì)量?？墒乾F(xiàn)有的路由無(wú)法保證孤立節(jié)點(diǎn)和弱社會(huì)關(guān)系節(jié)點(diǎn)的通信傳輸質(zhì)量,這正是現(xiàn)有社會(huì)性DTN路由面臨的主要挑戰(zhàn)之一。為此,本文設(shè)計(jì)了基于傳遞概率的社會(huì)性路由,既可以很好地預(yù)測(cè)節(jié)點(diǎn)短期移動(dòng)特性,也可以很好地預(yù)測(cè)節(jié)點(diǎn)的長(zhǎng)期運(yùn)動(dòng)規(guī)律,這樣能夠很好地解決現(xiàn)有社會(huì)性DTN路由所存在的這一問(wèn)題,通過(guò)仿真驗(yàn)證了該路由與已有的路由相比有更好的通信傳輸質(zhì)量。

1 RPRSA中的基本模型與方法

1.1 網(wǎng)絡(luò)模型和假設(shè)

1.2 社會(huì)網(wǎng)絡(luò)分析模型

本文采用文獻(xiàn)[8-9]中的k-clique算法進(jìn)行社會(huì)網(wǎng)絡(luò)分析。k-clique算法具有如下特點(diǎn):在數(shù)學(xué)形式上將這些完整的社區(qū)稱之為k-clique,通過(guò)k-clique社會(huì)分析算法得到的社區(qū)要求社區(qū)內(nèi)的節(jié)點(diǎn)必須與社區(qū)內(nèi)其他節(jié)點(diǎn)都有聯(lián)系,k為社區(qū)內(nèi)的節(jié)點(diǎn)數(shù),在k-clique算法中,允許不同的社區(qū)中有重復(fù)的節(jié)點(diǎn),而且允許有不屬于任何社區(qū)的孤立節(jié)點(diǎn)[10-11]。社會(huì)網(wǎng)絡(luò)分析的方式如下,通過(guò)設(shè)定閾值θ,可以將歸一化矩陣G進(jìn)行二值化得到矩陣M,再設(shè)定社區(qū)內(nèi)的節(jié)點(diǎn)數(shù)常值k′,通過(guò)已知的M與k′,就可以用k-clique算法得到網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),記作集合L,元素用l表示。特別指出的是,本文雖然采用了k-clique算法,但是可以容易地?cái)U(kuò)展到其他的社會(huì)網(wǎng)絡(luò)分析算法(例如Laplace圖特征值譜二分法、GN算法等),網(wǎng)絡(luò)中節(jié)點(diǎn)間的社會(huì)關(guān)系并不是固定的,而是隨著時(shí)間動(dòng)態(tài)變化。由于集中式的社會(huì)網(wǎng)絡(luò)分析方法無(wú)法動(dòng)態(tài)反映節(jié)點(diǎn)之間的社會(huì)關(guān)系,本文采取了分布式的社會(huì)網(wǎng)絡(luò)分析方法,可以更好地反映節(jié)點(diǎn)間的社會(huì)關(guān)系。

1.3 傳遞概率模型

在社會(huì)性DTN中,有一類情況可能會(huì)發(fā)生,網(wǎng)絡(luò)中存在部分節(jié)點(diǎn)具有弱社會(huì)關(guān)系甚至是孤立的。為了保證這些節(jié)點(diǎn)在社會(huì)性DTN中的通信傳輸質(zhì)量,本文采取了基于傳遞概率的路由策略[12]。通過(guò)傳遞概率的更新,節(jié)點(diǎn)可以更好地預(yù)測(cè)自己在未來(lái)一段時(shí)間內(nèi)的運(yùn)動(dòng)特性。如果一對(duì)節(jié)點(diǎn)進(jìn)行了直接端到端通信,那么在之后的一段時(shí)間內(nèi)很可能再次進(jìn)行直接端到端通信,這就可以提高弱社會(huì)關(guān)系甚至孤立節(jié)點(diǎn)的通信傳輸質(zhì)量。本文的傳遞概率更新包括節(jié)點(diǎn)間傳遞概率更新和節(jié)點(diǎn)社區(qū)間傳遞概率更新。

節(jié)點(diǎn)間傳遞概率更新是在同一個(gè)社區(qū)的節(jié)點(diǎn)之間進(jìn)行的。其中,直接節(jié)點(diǎn)間傳遞概率更新是節(jié)點(diǎn)對(duì)直接相遇后,直接更新彼此的傳遞概率;間接節(jié)點(diǎn)間傳遞概率更新是節(jié)點(diǎn)通過(guò)直接相遇節(jié)點(diǎn)更新與其他節(jié)點(diǎn)的傳遞概率。節(jié)點(diǎn)社區(qū)間傳遞概率是在不同社區(qū)的節(jié)點(diǎn)之間進(jìn)行的。其中:直接社區(qū)傳遞概率更新是節(jié)點(diǎn)與不同社區(qū)的節(jié)點(diǎn)直接相遇后,直接更新節(jié)點(diǎn)與對(duì)方社區(qū)的傳遞概率;間接社區(qū)傳遞概率更新是節(jié)點(diǎn)通過(guò)直接相遇節(jié)點(diǎn)所在的社區(qū)更新與其他社區(qū)的傳遞概率。每一個(gè)節(jié)點(diǎn)都記錄一個(gè)傳遞概率表單,表單采用矩陣P表示,元素用p表示,其中節(jié)點(diǎn)間的初始傳遞概率為pn,節(jié)點(diǎn)社區(qū)間的初始傳遞概率為pd。傳遞概率更新的計(jì)算則要根據(jù)節(jié)點(diǎn)間的相遇歷史信息計(jì)算得到。

1.4 路由模型

為了保證DTN網(wǎng)絡(luò)的消息傳輸成功率,降低網(wǎng)絡(luò)中通信失敗的源節(jié)點(diǎn)數(shù),本文采取了源節(jié)點(diǎn)多拷貝路由機(jī)制:消息的源節(jié)點(diǎn)s最多可以在DTN網(wǎng)絡(luò)中產(chǎn)生c份相同消息的拷貝;消息m到達(dá)目的節(jié)點(diǎn)d所在社區(qū)l后的多復(fù)制路由機(jī)制,即如果m傳遞到下一跳節(jié)點(diǎn)后,上一跳節(jié)點(diǎn)將不刪除m,這可以加快網(wǎng)絡(luò)中消息到達(dá)目的節(jié)點(diǎn)的速度。

同時(shí),為了防止采取的路由機(jī)制對(duì)網(wǎng)絡(luò)造成負(fù)擔(dān),本文首先限制了源節(jié)點(diǎn)拷貝數(shù),其次消息在未到達(dá)l時(shí)采取零復(fù)制路由機(jī)制,即m傳遞到下一跳節(jié)點(diǎn)后,上一跳節(jié)點(diǎn)將刪除m,并且消息在到達(dá)l后,l以外的所有節(jié)點(diǎn)都要?jiǎng)h除消息m,最后限制m的生存時(shí)間,如果在規(guī)定時(shí)間內(nèi)沒(méi)有到達(dá)目的節(jié)點(diǎn),那么刪除m。

2 傳遞概率更新算法

傳遞概率更新分為傳遞概率衰減部分更新和傳遞概率上升部分更新兩個(gè)步驟。傳遞概率衰減部分更新是節(jié)點(diǎn)間相遇時(shí),在進(jìn)行端到端通信之前,相遇節(jié)點(diǎn)依照相鄰兩次相遇的時(shí)間間隔進(jìn)行衰減部分的更新;傳遞概率上升部分更新是相遇節(jié)點(diǎn)間互相參照對(duì)方的傳遞概率表單,更新自身表單中對(duì)應(yīng)傳遞概率相對(duì)較小的部分。

直接節(jié)點(diǎn)間傳遞概率更新如下式

(1)

間接節(jié)點(diǎn)間傳遞概率更新,如果p(y,z)=p(x,z),則傳遞概率上升部分無(wú)需更新,只需要更新傳遞概率衰減部分;在p(y,z)p(x,z)時(shí),上升部分的更新方式是一致的,即節(jié)點(diǎn)更新自身傳遞概率表單中較小的部分,所以本文假設(shè)p(y,z)

(2)

直接社區(qū)傳遞概率更新如下式

(3)

間接社區(qū)傳遞概率更新,如果p(y,l)=p(x,l),則傳遞概率上升部分不需要更新,只需要更新傳遞概率衰減部分;在p(y,l)p(x,l)時(shí),傳遞概率上升部分的更新方式是一致的,即節(jié)點(diǎn)更新自身傳遞概率表單中較小的部分,所以本文假設(shè)p(y,l)

(4)

3 路由算法

在基于傳遞概率與社會(huì)網(wǎng)絡(luò)分析的延遲容忍網(wǎng)絡(luò)路由算法(delay-tolerant network routing based on probability of relay and social analysis, RPRSA)中,如果有需要傳遞消息的節(jié)點(diǎn)相遇,則根據(jù)節(jié)點(diǎn)間彼此的傳遞概率表單以及社會(huì)關(guān)系屬性判斷消息是否進(jìn)行傳遞。RPRSA路由算法流程如下。

設(shè)置實(shí)驗(yàn)仿真時(shí)間T;設(shè)置仿真實(shí)驗(yàn)的節(jié)點(diǎn)組;設(shè)置節(jié)點(diǎn)的消息產(chǎn)生周期r;設(shè)置消息最大副本數(shù)c;設(shè)置消息生存時(shí)間F;初始化節(jié)點(diǎn)的傳遞概率表單P。

在節(jié)點(diǎn)x、y相遇時(shí),節(jié)點(diǎn)x的路由過(guò)程如下。

步驟1 判斷節(jié)點(diǎn)x中消息的生存時(shí)間是否超過(guò)F,對(duì)于超過(guò)F的消息,在節(jié)點(diǎn)x中刪除;

步驟2 判斷節(jié)點(diǎn)x是否有需要傳遞的消息,如果有進(jìn)行步驟3,否則節(jié)點(diǎn)x結(jié)束消息傳遞;

步驟3 判斷節(jié)點(diǎn)y是否接收過(guò)節(jié)點(diǎn)x即將傳遞的消息,如果接收過(guò),則拒絕再次接收這個(gè)消息,否則節(jié)點(diǎn)x、y進(jìn)行步驟4;

步驟4 如果節(jié)點(diǎn)x有節(jié)點(diǎn)y沒(méi)有接收過(guò)的消息m,且該消息的目的節(jié)點(diǎn)是d,則目的節(jié)點(diǎn)d所在的目的社區(qū)是l。

步驟5 如果節(jié)點(diǎn)y是消息m的目的節(jié)點(diǎn),則執(zhí)行步驟6,否則節(jié)點(diǎn)x直接將消息m傳遞給y,并且刪除網(wǎng)絡(luò)中所有的消息m;

步驟6 如果節(jié)點(diǎn)x、y不都在目的社區(qū)l外部,則執(zhí)行步驟7,否則比較節(jié)點(diǎn)x、y與目的社區(qū)l的傳遞概率,當(dāng)p(x,l)

步驟7 如果節(jié)點(diǎn)x、y不都在目的社區(qū)l內(nèi)部,則執(zhí)行步驟8,否則比較節(jié)點(diǎn)x、y與目的節(jié)點(diǎn)d的傳遞概率,當(dāng)p(x,d)

步驟8 節(jié)點(diǎn)x在目的社區(qū)l外部,節(jié)點(diǎn)y在目的社區(qū)l內(nèi)部,則節(jié)點(diǎn)x將消息m發(fā)送到節(jié)點(diǎn)y,并且節(jié)點(diǎn)x刪除消息m。

步驟9 循環(huán)執(zhí)行步驟1～8,直到仿真時(shí)間結(jié)束。

RPRSA路由充分利用了節(jié)點(diǎn)的短期移動(dòng)特性和長(zhǎng)期運(yùn)動(dòng)規(guī)律,使得弱社會(huì)關(guān)系節(jié)點(diǎn)和孤立節(jié)點(diǎn)可以更好地傳輸消息,保證更多的節(jié)點(diǎn)之間能夠建立端到端的有效連接。

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

4.1 仿真場(chǎng)景與參數(shù)

本文采用了數(shù)據(jù)集Reality Mining[13-14],該數(shù)據(jù)集開(kāi)始于2004年,采集了96個(gè)節(jié)點(diǎn),其中75個(gè)節(jié)點(diǎn)來(lái)自麻省理工大學(xué)媒體實(shí)驗(yàn)室,另外21個(gè)節(jié)點(diǎn)來(lái)自臨近的斯隆商學(xué)院。

本文采集時(shí)間為16 981 816 s,采集了205 187組數(shù)據(jù),每一組數(shù)據(jù)包括以下4方面內(nèi)容:組序號(hào),即代表數(shù)據(jù)集中的第幾組數(shù)據(jù);連接狀態(tài),即連接或者斷開(kāi);時(shí)間,即得到此連接狀態(tài)的時(shí)間;節(jié)點(diǎn)序號(hào),即處于此連接狀態(tài)下的一對(duì)節(jié)點(diǎn)各自的序號(hào)。

仿真實(shí)驗(yàn)選取了數(shù)據(jù)集中的3個(gè)數(shù)據(jù)段,表1列出了所選取的數(shù)據(jù)量以及仿真的起止時(shí)間。

表1 仿真實(shí)驗(yàn)中選取的3個(gè)數(shù)據(jù)段

實(shí)驗(yàn)仿真時(shí)間為T(mén),即仿真時(shí)間的起始值和終止值的差值。仿真時(shí)選取了3個(gè)不同的節(jié)點(diǎn)組,每組節(jié)點(diǎn)的數(shù)據(jù)集中有96個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn),每個(gè)源節(jié)點(diǎn)隨機(jī)選取一個(gè)節(jié)點(diǎn)作為自己的目的節(jié)點(diǎn),目的節(jié)點(diǎn)的產(chǎn)生是隨機(jī)的,沒(méi)有關(guān)聯(lián);消息產(chǎn)生周期r為50 000 s;衰減因子γ=0.98;傳遞因子β=0.25;節(jié)點(diǎn)間的初始傳遞概率pn=0.75,節(jié)點(diǎn)社區(qū)間的初始傳遞概率pd=0.75。

初步的仿真表明,這些參數(shù)值的選取是合理的。盡管參數(shù)的取值并不是唯一的,但是取值符合概率模型的實(shí)際情況。當(dāng)參數(shù)值發(fā)生變化后,會(huì)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)間傳遞概率產(chǎn)生影響,但對(duì)最后的仿真結(jié)果幾乎無(wú)影響,因?yàn)橄?dòng)態(tài)地在網(wǎng)絡(luò)中尋找合適的節(jié)點(diǎn)進(jìn)行路由轉(zhuǎn)發(fā)。

本文中將RPRSA路由分別與Rank、Label、Bubble[7]路由進(jìn)行了對(duì)比,分析了消息生存時(shí)間F和源節(jié)點(diǎn)消息拷貝數(shù)c對(duì)RPRSA路由的影響,并從兩個(gè)方面衡量算法的性能:源節(jié)點(diǎn)平均傳輸成功率,即目的節(jié)點(diǎn)收到的消息數(shù)占源節(jié)點(diǎn)發(fā)送消息總數(shù)的百分比;通信失敗的源節(jié)點(diǎn)數(shù),即在仿真時(shí)間內(nèi)未能與目的節(jié)點(diǎn)成功通信至少一次的源節(jié)點(diǎn)數(shù)。

4.2 仿真結(jié)果

首先分析RPRSA路由,在給定的3個(gè)節(jié)點(diǎn)組中,每組節(jié)點(diǎn)分別在已選取的3個(gè)數(shù)據(jù)段上進(jìn)行仿真,消息生存時(shí)間F=T/3,源節(jié)點(diǎn)消息拷貝數(shù)c=1。對(duì)Rank、Label、Bubble路由進(jìn)行同樣的仿真,這樣每種算法都會(huì)得到9組仿真數(shù)據(jù)。

4.2.1 源節(jié)點(diǎn)平均傳輸成功率 由于篇幅限制,對(duì)每種算法得到的9組數(shù)據(jù)中的平均傳輸成功率再次取平均值,然后再與其他算法進(jìn)行比較。

圖1 RPRSA和Label路由平均傳輸成功率差值

圖2 RPRSA和Rank路由平均傳輸成功率差值

圖3 RPRSA和Bubble路由平均傳輸成功率差值

圖1～3是RPRSA路由分別與Label、Rank、Bubble路由的源節(jié)點(diǎn)平均傳輸成功率R進(jìn)行差值(RRPRSA,Label;RRPRSA,Rank;RRPRSA,Bubble)運(yùn)算得到的結(jié)果。在圖1中差值大于0的數(shù)目要明顯多于小于0的數(shù)目;在圖2中差值大于0的數(shù)目要略微多于小于0的數(shù)目;在圖3中差值大于0的數(shù)目要略微少于小于0的數(shù)目。因此,可以得到RPRSA路由的源節(jié)點(diǎn)傳輸成功率優(yōu)于Label和Rank路由,而相比Bubble路由會(huì)有些劣勢(shì)。

4.2.2 通信失敗的源節(jié)點(diǎn)數(shù) 表2列出了網(wǎng)絡(luò)中通信失敗的源節(jié)點(diǎn)數(shù)對(duì)比情況。由于篇幅限制,本文沒(méi)有列出第3組節(jié)點(diǎn)在3個(gè)數(shù)據(jù)段上的通信失敗的源節(jié)點(diǎn)數(shù)。

可以看到,與Label、Rank、Bubble路由相比,在相同條件下RPRSA路由中通信失敗的源節(jié)點(diǎn)數(shù)都要少很多。因此,RPRSA路由可以更好地保證弱社會(huì)關(guān)系節(jié)點(diǎn)和孤立節(jié)點(diǎn)的通信傳輸質(zhì)量,更好地實(shí)現(xiàn)端到端之間的通信,尤其對(duì)于那些端端之間有更高可靠性要求的網(wǎng)絡(luò),RPRSA路由是更好的選擇。

表2 網(wǎng)絡(luò)中通信失敗的源節(jié)點(diǎn)數(shù)對(duì)比情況

4.2.3 生存時(shí)間F對(duì)RPRSA路由的影響 選取第1組節(jié)點(diǎn)和第3個(gè)數(shù)據(jù)段,在其他條件相同時(shí),分別取值為T(mén)/3、T/2和T。圖4中是TTL取值T/2和T/3時(shí)所得到的平均傳輸成功率的差值;圖5中是TTL取值T和T/2時(shí)所得到的平均傳輸成功率的差值。

圖4 TTL取值T/3與T/2時(shí)性能對(duì)比

圖5 TTL取值T/2與T時(shí)性能對(duì)比

表3比較了第3個(gè)數(shù)據(jù)段,對(duì)于不同的F取值時(shí),網(wǎng)絡(luò)中通信失敗的源節(jié)點(diǎn)數(shù)。

適當(dāng)?shù)脑黾覨,可以提高網(wǎng)絡(luò)的平均傳輸成功率,但幾乎不會(huì)降低通信失敗的源節(jié)點(diǎn)數(shù);而且F增加也會(huì)對(duì)網(wǎng)絡(luò)造成負(fù)擔(dān)。

4.2.4 源節(jié)點(diǎn)拷貝數(shù)c對(duì)RPRSA路由的影響

表3 在第3個(gè)數(shù)據(jù)段F對(duì)通信失敗的源節(jié)點(diǎn)數(shù)的影響

選取第1組節(jié)點(diǎn)和第3個(gè)數(shù)據(jù)段,在其他條件相同時(shí),c分別取值1和5。圖6是c=5和c=1時(shí)所得到的平均傳輸成功率的差值。

圖6 源節(jié)點(diǎn)拷貝數(shù)取值5與1時(shí)性能對(duì)比

表4統(tǒng)計(jì)了c取值1和5時(shí),網(wǎng)絡(luò)中通信失敗的源節(jié)點(diǎn)數(shù)。

表4 源節(jié)點(diǎn)拷貝數(shù)對(duì)通信失敗的源節(jié)點(diǎn)數(shù)影響

適當(dāng)?shù)靥岣遚值,雖然可以提高平均傳輸成功率,但幾乎不會(huì)降低通信失敗的源節(jié)點(diǎn)數(shù),而且c的取值增加也會(huì)對(duì)網(wǎng)絡(luò)造成負(fù)擔(dān)。

5 結(jié) 語(yǔ)

與Label、Rank、Bubble路由相比,本文所提的RPRSA路由在保證平均傳輸成功率的同時(shí)減小了通信失敗的源節(jié)點(diǎn)數(shù),尤其是對(duì)于需要在某些節(jié)點(diǎn)間完成重要消息傳遞的應(yīng)用,RPRSA路由更具有可靠性。

本文沒(méi)有考慮消息的傳輸時(shí)延,與Bubble路由相比,平均傳輸成功率仍然有進(jìn)一步提高的空間。今后將進(jìn)一步研究改善RPRSA路由的性能。

[1] FALL K. A delay-tolerant network architecture for challenged internets [C]∥Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York, USA: ACM, 2003: 27-34.

[2] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs [C]∥Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York, USA: ACM, 2007: 32-40.

[3] BETTSTETTER C. Mobility modeling in wireless networks: categorization, smooth movement, and border effects [J]. ACM Sigmobile Mobile Computing and Communications Review, 2001, 5(3): 55-66.

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

[5] JONES E P C, LI L, SCHMIDTKE J K, et al. Practical routing in delay-tolerant networks [J]. IEEE Transactions on Mobile Computing, 2007, 6(8): 943-959.

[6] EVERETT M, BORGATTI S P. Ego network betweenness [J]. Social Networks, 2005, 27(1): 31-38.

[7] FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35-41.

[8] 白如江, 冷伏海.k-clique 社區(qū)知識(shí)創(chuàng)新演化方法研究 [J]. 圖書(shū)情報(bào)工作, 2013, 57(17): 86-94. BAI Rujiang, LENG Fuhai. Knowledge innovational evolution analysis based onk-clique community network [J]. Library and Information Service, 2013, 57(17): 86-94.

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

[10]EVERETT M G, BORGATTI S P. Analyzing clique overlap [J]. Connections, 1998, 21(1): 49-61.

[11]HUI P, CROWCROFT J. How small labels create big improvements [C]∥Proceedings of the 2007 IEEE International Conference on Pervasive Computing and Communications Workshop. Piscataway, NJ, USA: IEEE, 2007: 65-70.

[12]LINDGREN A, DORIA A, SCHELEN O. Probabilistic routing in intermittently connected networks [J]. ACM Sigmobile Mobile Computing and Communications Review, 2003, 7(3): 19-20.

[13]POTTENGER W M, YANG T. Detecting emerging concepts in textual data mining [C]∥Proceedings of the 2002 Society for Industrial and Applied Mathematics. New York, USA: ACM, 2002: 89-105.

[14]EAGLE N, PENTLAND A. Reality mining: sensing complex social systems [J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268.

[本刊相關(guān)文獻(xiàn)鏈接]

趙皓,高智勇,高建民,等.一種采用相空間重構(gòu)的多源數(shù)據(jù)融合方法.2016,50(8):84-89.[doi:10.7652/xjtuxb201608 014]

趙博選,高建民,陳琨.求解多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題的兩階段混合Pareto蟻群算法.2016,50(7):145-151.[doi:10.7652/xjtuxb201607022]

劉岳鐳,馮祖仁,任曉棟.具有惡化效應(yīng)的雙代理單機(jī)最優(yōu)調(diào)度算法.2016,50(6):9-14.[doi:10.7652/xjtuxb201606002]

劉強(qiáng),董小社,朱正東,等.一種短作業(yè)環(huán)境下的延遲調(diào)度算法.2015,49(2):1-5.[doi:10.7652/xjtuxb201502001]

崔穎安,李雪,夏輝,等.面向社交媒體嵌入關(guān)系數(shù)據(jù)感知方法的研究.2015,49(2):31-36.[doi:10.7652/xjtuxb201502 006]

陳家旭,唐亞哲,胡成臣,等.延遲容忍網(wǎng)絡(luò)中基于地點(diǎn)偏好的社會(huì)感知多播路由協(xié)議設(shè)計(jì).2014,48(6):13-18.[doi:10.7652/xjtuxb201406003]

趙曉明,周顥,何軍,等.視頻點(diǎn)播系統(tǒng)中視頻分片協(xié)同存儲(chǔ)方案研究.2014,48(4):26-30.[doi:10.7652/xjtuxb201404 005]

(編輯 武紅江)

A Delay-Tolerant Network Routing Based on Probability of Relay and Social Network Analysis

YANG Mo,YOU Lei,LI Bing,ZHAO Jianjun

(School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China)

Routing designs that combine with relay probability and social network analysis can fully utilize movement characteristic of nodes and enhance quality of message transmission from end to end. A delay-tolerant network routing based on probability of relay and social network analysis (RPRSA) is proposed based on the analyses of historical information of nodes encounters and social relationship. The analysis of historical information is to forecast short-run movement characteristic by independent probability computation and probability information exchange with each other when nodes encounter, and the analysis of social relation is to forecast long-run movement law by the degree of intimacy among nodes formed in long-run movements. Simulation results show that the proposed routing makes full use of movement features among nodes, guarantees the quality of messages transmission among the nodes with weak social relation and the isolate nodes, and enhances the quality of messages transmission from end to end.

delay-tolerant network; social network analysis; relay probability; routing design

2016-08-01。 作者簡(jiǎn)介:楊沫(1990—),男,碩士生;由磊(通信作者),男,講師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61202380);天津市自然科學(xué)基金資助項(xiàng)目(12JCQNJC00300)。

時(shí)間:2016-10-19

10.7652/xjtuxb201612021

TP393

A

0253-987X(2016)12-0136-06

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