朱子青 曹玖新 周 濤 胥 帥 馬 卓 劉 波

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)) 南京 211189) (zzqxztc@seu.edu.cn)

基于多維特征分析的移動(dòng)社會(huì)網(wǎng)絡(luò)消息傳輸

朱子青 曹玖新 周 濤 胥 帥 馬 卓 劉 波

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)) 南京 211189) (zzqxztc@seu.edu.cn)

基于延遲容忍特征，移動(dòng)社會(huì)網(wǎng)絡(luò)采用“存儲(chǔ)—運(yùn)載—轉(zhuǎn)發(fā)”模式在節(jié)點(diǎn)之間進(jìn)行消息傳輸.如何選定合適的中繼節(jié)點(diǎn)進(jìn)行消息的高效傳輸是當(dāng)前研究中備受關(guān)注的熱點(diǎn)問(wèn)題.從不同的角度對(duì)網(wǎng)絡(luò)中的多維社會(huì)特征展開(kāi)分析.首先，根據(jù)節(jié)點(diǎn)間的交互關(guān)系，確定節(jié)點(diǎn)間社會(huì)關(guān)系模型；其次，依據(jù)網(wǎng)絡(luò)拓?fù)浣o出了鄰居集合和本地社區(qū)的定義，提出了一種移動(dòng)社會(huì)網(wǎng)絡(luò)的本地社區(qū)劃分方法，進(jìn)而建立了節(jié)點(diǎn)間的社區(qū)關(guān)系；然后，基于節(jié)點(diǎn)間的行為特征給出了節(jié)點(diǎn)活躍度定義，通過(guò)PageRank算法獲得節(jié)點(diǎn)的多維屬性特征PR值，并利用PR值給出節(jié)點(diǎn)間傳輸值，從而獲得節(jié)點(diǎn)的不同傳輸效用值.在此基礎(chǔ)之上，綜合考慮節(jié)點(diǎn)社區(qū)關(guān)系和節(jié)點(diǎn)的不同傳輸效用值，設(shè)計(jì)并實(shí)現(xiàn)了移動(dòng)社會(huì)網(wǎng)絡(luò)的消息傳輸算法.實(shí)驗(yàn)表明，算法在傳輸成功率、傳輸冗余率、平均延時(shí)等多個(gè)方面具有優(yōu)勢(shì).

移動(dòng)社會(huì)網(wǎng)絡(luò)；延遲容忍網(wǎng)絡(luò)；社區(qū)劃分；PageRank算法；動(dòng)態(tài)網(wǎng)絡(luò)

隨著手機(jī)等移動(dòng)設(shè)備的大量普及，利用移動(dòng)設(shè)備建立的連接進(jìn)行設(shè)備之間的直接信息傳輸引起了廣泛的關(guān)注.移動(dòng)社會(huì)網(wǎng)絡(luò)(mobile social network, MSN)是由人隨身攜帶的移動(dòng)設(shè)備構(gòu)成，具有社會(huì)網(wǎng)絡(luò)的社會(huì)性和移動(dòng)通信網(wǎng)絡(luò)的移動(dòng)性.如何解決MSN網(wǎng)絡(luò)中的消息傳輸和共享一直是人們研究的熱點(diǎn)問(wèn)題.在網(wǎng)絡(luò)中，設(shè)備會(huì)隨著人移動(dòng)，由于人的移動(dòng)性，即人們之間的相遇時(shí)間間隔與相遇頻率等因素會(huì)影響設(shè)備間消息的傳輸成功率或者傳輸延時(shí).當(dāng)前大量的研究表明，隨著人移動(dòng)的設(shè)備在移動(dòng)過(guò)程中存在著明顯的移動(dòng)規(guī)律.文獻(xiàn)[1]通過(guò)對(duì)大量的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，得出網(wǎng)絡(luò)中的移動(dòng)設(shè)備之間相遇間隔時(shí)間服從冪律分布的結(jié)論.文獻(xiàn)[2]則指出人們所攜帶的網(wǎng)絡(luò)節(jié)點(diǎn)之間的相遇間隔時(shí)間在某時(shí)間閾值范圍內(nèi)服從冪律分布，而超過(guò)該閾值則服從指數(shù)分布.文獻(xiàn)[3-4]也對(duì)隨著人移動(dòng)的設(shè)備間相遇規(guī)律開(kāi)展了研究，表明網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)行為確實(shí)存在基于社會(huì)行為的移動(dòng)規(guī)律.

如何利用移動(dòng)社會(huì)網(wǎng)絡(luò)中的社會(huì)規(guī)律，分析節(jié)點(diǎn)之間的社會(huì)關(guān)系特征，從而設(shè)計(jì)消息傳輸算法是一個(gè)重要的研究問(wèn)題.

本文綜合考慮移動(dòng)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)所存在的多維社會(huì)特征.基于網(wǎng)絡(luò)的局部拓?fù)浜徒换リP(guān)系設(shè)計(jì)了本地社區(qū)算法；根據(jù)節(jié)點(diǎn)的移動(dòng)行為規(guī)律提出了節(jié)點(diǎn)的社會(huì)活躍度概念；利用PageRank算法使節(jié)點(diǎn)之間根據(jù)傳輸狀況特征的不同進(jìn)行相互評(píng)價(jià)，從而獲得節(jié)點(diǎn)的多屬性特征PR特征值，并給出節(jié)點(diǎn)間傳輸值的定義；最終，設(shè)計(jì)實(shí)現(xiàn)了移動(dòng)社會(huì)網(wǎng)絡(luò)消息傳輸算法.

1 相關(guān)工作

近年來(lái)，業(yè)界對(duì)延遲容忍網(wǎng)絡(luò)(delay tolerant network, DTN)[5]消息傳輸已經(jīng)開(kāi)展了大量研究工作.有基于傳統(tǒng)路由轉(zhuǎn)發(fā)策略擴(kuò)展改進(jìn)的MED，EDAQ，LP，PLSR路由[6]；基于多副本傳染型傳輸策略改進(jìn)的Spray系列路由[7-8]、利用路由節(jié)點(diǎn)概率效用值進(jìn)行傳輸?shù)腜rophet路由[9]；結(jié)合新型智能優(yōu)化算法[10-11]的路由.傳統(tǒng)DTN路由算法的設(shè)計(jì)都沒(méi)有涉及網(wǎng)絡(luò)中存在的社會(huì)規(guī)律.因而在移動(dòng)社會(huì)網(wǎng)絡(luò)環(huán)境下，開(kāi)展了很多結(jié)合社會(huì)網(wǎng)絡(luò)規(guī)律設(shè)計(jì)的基于社會(huì)屬性(social based)的路由算法的研究.

Daly等人[12]利用復(fù)雜網(wǎng)絡(luò)中度(degree)、接近中心度(closeness centrality)、介數(shù)中心度(betweenness centrality)、節(jié)點(diǎn)間相似性(similarity)等特性對(duì)網(wǎng)絡(luò)中的社會(huì)特征進(jìn)行分析，提出了SimBet算法，實(shí)現(xiàn)路由消息傳輸.Pan等人[13-14]分析了網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu)，提出了BubbleRap算法，消息依據(jù)節(jié)點(diǎn)間的社區(qū)關(guān)系進(jìn)行傳播，提高了網(wǎng)絡(luò)中消息的傳輸性能.Wu等人[15]依據(jù)網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)所存在的“Home”屬性，提出了類似Spray路由機(jī)制的Homing Spread算法，可以有效提高消息傳輸性能.Li等人[16]分析了節(jié)點(diǎn)之間的相遇頻率、每次平均通信時(shí)間、歷史通信總時(shí)間和平均最短分離時(shí)間對(duì)節(jié)點(diǎn)之間交互緊密程度的影響，進(jìn)而從中選擇合適的指標(biāo)建立節(jié)點(diǎn)間社會(huì)關(guān)系.而Gao等人[17]則著重研究了節(jié)點(diǎn)之間的瞬時(shí)連接對(duì)消息傳輸?shù)淖饔?

以上研究所具有的共同特點(diǎn)在于網(wǎng)絡(luò)中消息傳輸算法所利用的網(wǎng)絡(luò)社會(huì)關(guān)系特征都是通過(guò)節(jié)點(diǎn)之間的移動(dòng)交互“探索”得到的，被稱為探索型社會(huì)網(wǎng)絡(luò)(detected social networks)[18].也有一部分研究不通過(guò)節(jié)點(diǎn)之間的“探索”獲得社會(huì)關(guān)系.而是直接利用網(wǎng)絡(luò)中節(jié)點(diǎn)之間已經(jīng)存在的社會(huì)連接關(guān)系分析節(jié)點(diǎn)間社會(huì)特征，此類型的移動(dòng)社會(huì)網(wǎng)絡(luò)被稱為自我宣稱型社會(huì)網(wǎng)絡(luò)(self-reported social networks)[18].在移動(dòng)社會(huì)網(wǎng)絡(luò)中，有文獻(xiàn)利用社會(huì)關(guān)系問(wèn)卷調(diào)查、社交網(wǎng)絡(luò)朋友關(guān)注等已知的社會(huì)關(guān)系來(lái)分析網(wǎng)絡(luò)中的社會(huì)特征，進(jìn)而設(shè)計(jì)消息傳輸算法.如文獻(xiàn)[19-20]利用了用戶線上Facebook的社交關(guān)系建立了社會(huì)關(guān)系拓?fù)?，而文獻(xiàn)[21]則是利用INFOCOM2006的與會(huì)人員填寫的問(wèn)卷調(diào)查建立已知的社會(huì)關(guān)系網(wǎng)絡(luò).

然而現(xiàn)有的相關(guān)研究工作仍然存在一些不足：

1) 當(dāng)前一些研究[21]是建立在整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間社會(huì)關(guān)系已經(jīng)確定的基礎(chǔ)之上，對(duì)全局網(wǎng)絡(luò)的社會(huì)屬性特征進(jìn)行分析，進(jìn)而設(shè)計(jì)中繼節(jié)點(diǎn)選擇算法.而移動(dòng)網(wǎng)絡(luò)的特性決定了網(wǎng)絡(luò)中各節(jié)點(diǎn)只能動(dòng)態(tài)地獲得局部的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或部分節(jié)點(diǎn)之間的關(guān)系，因此應(yīng)該更注重節(jié)點(diǎn)的局部動(dòng)態(tài)連接關(guān)系分析.

2) 很多學(xué)者[14]對(duì)網(wǎng)絡(luò)中存在的社區(qū)關(guān)系展開(kāi)了研究.然而社區(qū)之間的劃分是建立在網(wǎng)絡(luò)中節(jié)點(diǎn)全局關(guān)系已完全建立的基礎(chǔ)之上.這不適用于移動(dòng)社會(huì)網(wǎng)絡(luò)的局部動(dòng)態(tài)連接情況.在移動(dòng)社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)動(dòng)態(tài)地獲取周圍節(jié)點(diǎn)的連接信息，通過(guò)局部的網(wǎng)絡(luò)信息，和周圍節(jié)點(diǎn)建立社區(qū)關(guān)系.一部分學(xué)者[16,21]在移動(dòng)社會(huì)網(wǎng)絡(luò)的環(huán)境下，對(duì)局部社區(qū)探測(cè)進(jìn)行了探討.但是通過(guò)局部信息建立的本地社區(qū)(local community)只關(guān)注社區(qū)關(guān)系形成的過(guò)程，沒(méi)有關(guān)注時(shí)間流逝之后節(jié)點(diǎn)社區(qū)的老化問(wèn)題.

3) 社會(huì)網(wǎng)絡(luò)中存在的冪律性特征，例如網(wǎng)絡(luò)中度數(shù)小的節(jié)點(diǎn)要比度數(shù)大的節(jié)點(diǎn)數(shù)量高很多，所以在傳輸時(shí)，只考慮節(jié)點(diǎn)自身的度指標(biāo)會(huì)產(chǎn)生傳輸數(shù)據(jù)向某些節(jié)點(diǎn)過(guò)度集中的問(wèn)題.這造成了消息傳輸?shù)牟还叫?，個(gè)別節(jié)點(diǎn)上的消息負(fù)載相對(duì)過(guò)高.社會(huì)網(wǎng)絡(luò)領(lǐng)域的研究中就發(fā)現(xiàn)小度數(shù)節(jié)點(diǎn)或者弱連接對(duì)信息在網(wǎng)絡(luò)中的傳播有重要作用[22].Ioannidis等人[23]便研究過(guò)如何利用網(wǎng)絡(luò)中弱社會(huì)關(guān)系對(duì)消息進(jìn)行路由傳輸.節(jié)點(diǎn)自身不活躍而鄰居很活躍，節(jié)點(diǎn)也可以將持有的消息擴(kuò)散出去.因此，應(yīng)該應(yīng)用一種更科學(xué)的指標(biāo)來(lái)使消息向“非中心性”節(jié)點(diǎn)傳輸.考慮節(jié)點(diǎn)在傳輸時(shí)，節(jié)點(diǎn)自身的傳輸狀況對(duì)周圍節(jié)點(diǎn)的影響.

2 節(jié)點(diǎn)社會(huì)關(guān)系模型

由于節(jié)點(diǎn)間相遇的間斷性，移動(dòng)社會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)鋾?huì)不斷改變.本文將節(jié)點(diǎn)間不斷變化的節(jié)點(diǎn)移動(dòng)相遇關(guān)系轉(zhuǎn)變?yōu)橄鄬?duì)穩(wěn)定的社會(huì)關(guān)系.然后對(duì)網(wǎng)絡(luò)中存在的社會(huì)特征展開(kāi)分析.

在移動(dòng)社會(huì)網(wǎng)絡(luò)中，社會(huì)關(guān)系緊密的節(jié)點(diǎn)，節(jié)點(diǎn)之間也會(huì)進(jìn)行頻繁的通信，因而可以用節(jié)點(diǎn)間的通信累計(jì)時(shí)間表示節(jié)點(diǎn)間的社會(huì)關(guān)系.本文將移動(dòng)社會(huì)網(wǎng)絡(luò)建模為具有多屬性的節(jié)點(diǎn)無(wú)向網(wǎng)絡(luò)圖，其形式化描述如下：

給定Gt(V,E),其中V是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為網(wǎng)絡(luò)中2個(gè)節(jié)點(diǎn)之間社會(huì)關(guān)系連接邊的集合，t表示網(wǎng)絡(luò)在一段時(shí)期的狀態(tài).網(wǎng)絡(luò)中節(jié)點(diǎn)u，v之間的邊關(guān)系權(quán)重表示為wt(u,v)，表示為節(jié)點(diǎn)u，v之間在一段時(shí)期t的累計(jì)通信時(shí)間.每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇頻率、相遇時(shí)間間隔等特征，作為節(jié)點(diǎn)集合V中節(jié)點(diǎn)所具有的自身屬性.

3 本地社區(qū)發(fā)現(xiàn)

攜帶消息的節(jié)點(diǎn)在網(wǎng)絡(luò)中根據(jù)和其相遇節(jié)點(diǎn)的社區(qū)關(guān)系，選擇不同的消息路由策略.因此本文參考文獻(xiàn)[24]的思想提出改進(jìn)的本地社區(qū)探測(cè)算法LAC(local aging community).

3.1 鄰居集合和本地社區(qū)

為便于描述，本文定義相關(guān)的概念.

定義1. 節(jié)點(diǎn)直接鄰居關(guān)系.是指兩相遇節(jié)點(diǎn)之間的累積相遇時(shí)間超過(guò)設(shè)定的閾值，則這2個(gè)節(jié)點(diǎn)之間形成直接鄰居關(guān)系，體現(xiàn)了節(jié)點(diǎn)之間通信連接的緊密性.

對(duì)于一個(gè)給定的節(jié)點(diǎn)u，其直接鄰居的節(jié)點(diǎn)集合可形式化表示為：

Nu={v|wt(u，v)>Tth,v∈Mu}，

其中，wt(u,v)表示u與v之間的邊權(quán)重；Tth表示鄰居關(guān)系時(shí)間閾值；Mu表示和節(jié)點(diǎn)u相遇過(guò)的節(jié)點(diǎn)集合.

定義2. 節(jié)點(diǎn)間接鄰居關(guān)系.是指兩相遇節(jié)點(diǎn)沒(méi)有形成直接鄰居關(guān)系，但是2節(jié)點(diǎn)之間的直接鄰居重合程度超過(guò)設(shè)定閾值，則這2個(gè)節(jié)點(diǎn)之間形成間接鄰居關(guān)系，體現(xiàn)了節(jié)點(diǎn)之間再通信的可能性.

對(duì)于一個(gè)給定的節(jié)點(diǎn)u，其間接鄰居的節(jié)點(diǎn)集合可形式化表示為：

其中，Tth為設(shè)定的時(shí)間閾值；Nu和Nv分別表示u與v的直接鄰居節(jié)點(diǎn)集合；Mu表示和節(jié)點(diǎn)u相遇過(guò)的節(jié)點(diǎn)集合；λ為重合度設(shè)定閾值.

定義3. 節(jié)點(diǎn)本地社區(qū).是指和節(jié)點(diǎn)同處一個(gè)社區(qū)的節(jié)點(diǎn)組成的集合.其包括所有直接鄰居節(jié)點(diǎn)和間接鄰居節(jié)點(diǎn)的集合，以及節(jié)點(diǎn)本地社區(qū)在形成過(guò)程中，兩相遇節(jié)點(diǎn)互相合并本地社區(qū)時(shí)，不存在直接鄰居和間接鄰居關(guān)系的節(jié)點(diǎn).

對(duì)于一個(gè)給定的節(jié)點(diǎn)u，其本地社區(qū)的成員集合可形式化表示為：

定義4. 節(jié)點(diǎn)間接社區(qū)關(guān)系.是指兩相遇節(jié)點(diǎn)之間的本地社區(qū)滿足條件合并后，新本地社區(qū)中不屬于2個(gè)節(jié)點(diǎn)原本地社區(qū)的節(jié)點(diǎn).2個(gè)節(jié)點(diǎn)分別和不屬于原本地社區(qū)的節(jié)點(diǎn)形成節(jié)點(diǎn)間接社區(qū)關(guān)系.節(jié)點(diǎn)間接社區(qū)關(guān)系，體現(xiàn)了節(jié)點(diǎn)之間形成社區(qū)或者相遇通信的可能性.

對(duì)于一個(gè)給定的節(jié)點(diǎn)u，其節(jié)點(diǎn)間接社區(qū)成員集合可形式化表示為：

3.2 本地社區(qū)發(fā)現(xiàn)算法

本文給出適用于移動(dòng)社會(huì)網(wǎng)絡(luò)的本地社區(qū)劃分算法LAC，其基本思想是：

1) 本地社區(qū)形成過(guò)程.節(jié)點(diǎn)的直接鄰居關(guān)系和間接關(guān)系節(jié)點(diǎn)首先成為其本地社區(qū)成員；然后節(jié)點(diǎn)間在每次相遇過(guò)程中，通過(guò)本地社區(qū)的重合條件進(jìn)行合并，產(chǎn)生新的本地社區(qū)成員.

2) 本地社區(qū)維護(hù)過(guò)程.節(jié)點(diǎn)首先檢測(cè)其直接鄰居關(guān)系節(jié)點(diǎn)是否老化，如果節(jié)點(diǎn)的直接鄰居關(guān)系節(jié)點(diǎn)出現(xiàn)老化，則檢測(cè)節(jié)點(diǎn)的間接鄰居關(guān)系節(jié)點(diǎn)；最后檢測(cè)和節(jié)點(diǎn)存在間接社區(qū)關(guān)系節(jié)點(diǎn)是否老化.因而算法流程包括本地形成和社區(qū)維護(hù)2個(gè)過(guò)程.

過(guò)程1. LAC本地社區(qū)形成.

過(guò)程1和過(guò)程2分別表示LAC算法中本地社區(qū)形成和隨時(shí)間流逝的維護(hù)過(guò)程.其中，過(guò)程1的行⑤～⑦表示節(jié)點(diǎn)間的直接鄰居關(guān)系形成.行⑧～表示節(jié)點(diǎn)間的間接鄰居關(guān)系形成.行～表示節(jié)點(diǎn)的本地社區(qū)合并，并產(chǎn)生存在間接社區(qū)關(guān)系的節(jié)點(diǎn).而過(guò)程2中，行④～⑧表示隨時(shí)間流逝，節(jié)點(diǎn)之間的邊權(quán)重改變，引起節(jié)點(diǎn)間的直接鄰居關(guān)系老化；行⑨～表示隨時(shí)間流逝節(jié)點(diǎn)間的間接鄰居關(guān)系老化；行～表示節(jié)點(diǎn)的本地社區(qū)中間接社區(qū)關(guān)系節(jié)點(diǎn)被刪除；行～進(jìn)行DO WHILE循環(huán)檢測(cè)，是因?yàn)殚g接社區(qū)關(guān)系節(jié)點(diǎn)在每次社區(qū)合并過(guò)程中，會(huì)使新的間接社區(qū)關(guān)系節(jié)點(diǎn)加入，因而每次本地社區(qū)成員改變了，要循環(huán)檢測(cè)其余存在間接社區(qū)關(guān)系的節(jié)點(diǎn)是否應(yīng)該被刪除.

對(duì)于LAC的算法時(shí)間復(fù)雜度，過(guò)程1的時(shí)間消耗主要集中在行④、行⑧和行，即節(jié)點(diǎn)u判斷相遇節(jié)點(diǎn)v是否存在于其本地社區(qū)以及判斷鄰居或者社區(qū)的重合度.節(jié)點(diǎn)u本地社區(qū)成員數(shù)目為|Cu|，顯然都要比節(jié)點(diǎn)的鄰居數(shù)目要大，因而算法時(shí)間復(fù)雜度為O(|Cu|).而過(guò)程2的時(shí)間消耗主要集中在行①、行④、行⑨和行的節(jié)點(diǎn)集合遍歷，和行⑩和行，檢測(cè)原先條件滿足時(shí)所記錄的重合集合Nu∩Nv，Cu∩Cv的狀態(tài).而存在間接社區(qū)關(guān)系的節(jié)點(diǎn)，在每輪維護(hù)中，某種情況下可以通過(guò)DO WHILE循環(huán)檢測(cè)依次全部刪除，假設(shè)節(jié)點(diǎn)u的間接社區(qū)成員數(shù)目為，則其為遞減數(shù)列因而最壞情況下，算法時(shí)間復(fù)雜度為，一般情況下相遇過(guò)的節(jié)點(diǎn)數(shù)量|Mu|要比都要大，因而時(shí)間復(fù)雜度為O(|Mu|).

4 節(jié)點(diǎn)傳輸效用值

進(jìn)行消息傳輸時(shí)，節(jié)點(diǎn)在判斷和相遇節(jié)點(diǎn)的社區(qū)關(guān)系基礎(chǔ)上，通過(guò)考慮相遇節(jié)點(diǎn)的傳輸效用值，在社區(qū)間和社區(qū)內(nèi)選擇合適的中繼節(jié)點(diǎn).

4.1 節(jié)點(diǎn)社會(huì)活躍度

在網(wǎng)絡(luò)中相遇節(jié)點(diǎn)數(shù)量多的節(jié)點(diǎn)，其本身具有更高的消息傳播可能性.同時(shí)，節(jié)點(diǎn)和周圍節(jié)點(diǎn)相遇比較頻繁，也能增加節(jié)點(diǎn)傳播消息的能力.本文利用節(jié)點(diǎn)的相遇節(jié)點(diǎn)數(shù)目和與其他節(jié)點(diǎn)相遇時(shí)間間隔來(lái)描述節(jié)點(diǎn)的活躍程度，即社會(huì)活躍度(social activity, SA)，其定義為：

SA(u)=|Mu|a-δTu，

(1)

其中,|Mu|表示節(jié)點(diǎn)u在網(wǎng)絡(luò)中相遇過(guò)的節(jié)點(diǎn)數(shù)量,而Tu為一段時(shí)間內(nèi)節(jié)點(diǎn)u和所有相遇過(guò)節(jié)點(diǎn)的最近相遇間隔時(shí)間的平均值,δ為平滑因子.

如文獻(xiàn)[1-2]所指出的，基于節(jié)點(diǎn)之間相遇時(shí)間間隔的冪指特性分布，只有很少一部分節(jié)點(diǎn)的相遇時(shí)間間隔會(huì)很大.所以本文將節(jié)點(diǎn)社會(huì)活躍度定義為關(guān)于時(shí)間的冪函數(shù)形式，當(dāng)和其他節(jié)點(diǎn)相遇時(shí)間間隔變大，其社會(huì)活躍度也會(huì)快速下降.

4.2 節(jié)點(diǎn)多維屬性特征PR值

當(dāng)消息在節(jié)點(diǎn)之間進(jìn)行傳輸時(shí)，為了避免消息向個(gè)別中心節(jié)點(diǎn)過(guò)度聚集現(xiàn)象，本文使用新的指標(biāo)來(lái)改進(jìn)消息的傳輸性能.網(wǎng)頁(yè)排名的PageRank算法[25]使網(wǎng)站的重要度得分由自身和其他網(wǎng)站共同決定.

4.2.1 多維屬性特征分析

本文采用PageRank算法的思想建立節(jié)點(diǎn)的傳輸評(píng)分特征值.綜合網(wǎng)絡(luò)中節(jié)點(diǎn)的3種屬性特征展開(kāi)分析.

1) 節(jié)點(diǎn)的社會(huì)活躍度屬性

對(duì)于節(jié)點(diǎn)的社會(huì)活躍度屬性，本文規(guī)定低活躍度的節(jié)點(diǎn)向周邊高活躍度的直接鄰居節(jié)點(diǎn)給予評(píng)分，反之，不評(píng)分.因而可以抽象為如圖1所示的有向圖.

Fig. 1 Node social activity relations圖1 節(jié)點(diǎn)社會(huì)活躍度關(guān)系

節(jié)點(diǎn)間的評(píng)分函數(shù)為：

A(v,u)×PR(v)，

(2)

其中，PR(v)為節(jié)點(diǎn)v的PageRank值，A(v,u)為節(jié)點(diǎn)v對(duì)直接鄰居節(jié)點(diǎn)u活躍度權(quán)重比例分配計(jì)算函數(shù)：

(3)

Fig. 2 Node interaction frequency relations圖2 節(jié)點(diǎn)交互頻率關(guān)系

節(jié)點(diǎn)依據(jù)周圍直接鄰居節(jié)點(diǎn)的社會(huì)活躍度和其自身的社會(huì)活躍度關(guān)系給予不同的評(píng)價(jià)權(quán)重.得分比較高的節(jié)點(diǎn)，表示其周圍直接鄰居都認(rèn)為此節(jié)點(diǎn)有更高的社會(huì)活躍度.

2) 節(jié)點(diǎn)之間的相遇頻率屬性

對(duì)于節(jié)點(diǎn)和其他節(jié)點(diǎn)的相遇頻率屬性，可以抽象為如圖2所示的有向圖.

每個(gè)節(jié)點(diǎn)通過(guò)與周邊節(jié)點(diǎn)的交互頻率向直接鄰居給予評(píng)分，周圍鄰居出現(xiàn)頻率越高，則對(duì)其評(píng)分權(quán)重越大.本文給出節(jié)點(diǎn)按照相遇頻率得到的周圍鄰居評(píng)分函數(shù)：

Pv(u)×PR(v)，

(4)

其中，Pv(u)為節(jié)點(diǎn)v相遇其鄰居節(jié)點(diǎn)u的頻率.

依照節(jié)點(diǎn)周圍直接鄰居出現(xiàn)的頻率，節(jié)點(diǎn)對(duì)周圍直接鄰居節(jié)點(diǎn)出現(xiàn)的不同頻率，給予不同的評(píng)分權(quán)重.評(píng)分比較高的節(jié)點(diǎn)，表示其周圍鄰居節(jié)點(diǎn)都認(rèn)為該節(jié)點(diǎn)經(jīng)常出現(xiàn)，或者節(jié)點(diǎn)本身和某一評(píng)分較高的節(jié)點(diǎn)經(jīng)常相遇.

3) 節(jié)點(diǎn)的直接鄰居數(shù)屬性

對(duì)于節(jié)點(diǎn)在網(wǎng)絡(luò)中的鄰居數(shù)屬性，即指節(jié)點(diǎn)的周圍的直接鄰居數(shù)量，如圖3所示.本文給出節(jié)點(diǎn)評(píng)分函數(shù)：

(5)

其中，Nv表示節(jié)點(diǎn)v的直接鄰居.

Fig. 3 Node direct neighbor relations圖3 節(jié)點(diǎn)的直接鄰居關(guān)系

依照節(jié)點(diǎn)周圍直接鄰居的數(shù)量，節(jié)點(diǎn)對(duì)每個(gè)鄰居均等地給予評(píng)分.評(píng)分高的節(jié)點(diǎn)，表示獲得了很多節(jié)點(diǎn)的評(píng)分，或者此節(jié)點(diǎn)和高評(píng)分的節(jié)點(diǎn)存在直接鄰居關(guān)系.

最后，本文綜合考慮不同方面的特征分析，給出基于PageRank算法的節(jié)點(diǎn)u得分特征值函數(shù)：

(6)

其中，α+β+γ=1，d為PageRank中的衰減因子.

4.2.2 節(jié)點(diǎn)PR值計(jì)算流程

對(duì)于PR值的計(jì)算迭代簡(jiǎn)單實(shí)例如圖4所示.計(jì)算過(guò)程中，節(jié)點(diǎn)A需要接收節(jié)點(diǎn)B和C傳來(lái)的PR值分量才進(jìn)行迭代計(jì)算.同理，節(jié)點(diǎn)B，C也要分別接收和傳輸鄰居的PR值分量才能完成自己的PR值計(jì)算.

Fig. 4 Simple network topology圖4 簡(jiǎn)單網(wǎng)絡(luò)拓?fù)涫疽鈭D

因此，本文給出移動(dòng)社會(huì)網(wǎng)絡(luò)下的PR值計(jì)算規(guī)則：

1) 每一個(gè)節(jié)點(diǎn)在傳輸完成自己的所有出度邊PR值分量和接收其他鄰居節(jié)點(diǎn)PR值分量后，更新自己的PR值.

2) 如果相遇節(jié)點(diǎn)之間的PR值和上次相遇時(shí)相同，則不進(jìn)行節(jié)點(diǎn)之間的PR分量值傳輸.

在移動(dòng)網(wǎng)絡(luò)的環(huán)境下，節(jié)點(diǎn)和直接鄰居關(guān)系節(jié)點(diǎn)在已經(jīng)建立連接情況下，可以完成PR值每一輪計(jì)算，而每個(gè)節(jié)點(diǎn)PR值和網(wǎng)絡(luò)拓?fù)溆嘘P(guān).因而當(dāng)網(wǎng)絡(luò)拓?fù)湓椒€(wěn)定，節(jié)點(diǎn)之間相遇越頻繁，連接越持續(xù)，則會(huì)向節(jié)點(diǎn)PR值的收斂穩(wěn)定值趨近得越快.

4.3 節(jié)點(diǎn)間的傳輸值

為了使消息在網(wǎng)絡(luò)中的消息路由傳輸過(guò)程中具有目的性和方向性，減少傳輸開(kāi)銷，本文分析PageRank算法分量的傳輸過(guò)程.如圖4所示，本文假定節(jié)點(diǎn)A，B，C的PR值當(dāng)前都為1，因子d=0.85.出度邊的權(quán)重都為1.

假定節(jié)點(diǎn)B和節(jié)點(diǎn)A，C經(jīng)常相遇，而節(jié)點(diǎn)C又經(jīng)常和節(jié)點(diǎn)A經(jīng)常相遇，本文分析節(jié)點(diǎn)B的PR值傳輸過(guò)程.

那么當(dāng)節(jié)點(diǎn)B和節(jié)點(diǎn)A相遇時(shí)，節(jié)點(diǎn)A依據(jù)出邊權(quán)重向節(jié)點(diǎn)B傳輸PR值分量0.425.

當(dāng)節(jié)點(diǎn)B和節(jié)點(diǎn)C相遇時(shí)，節(jié)點(diǎn)C獲得B傳來(lái)的PR值分量0.425.然后，節(jié)點(diǎn)C再和節(jié)點(diǎn)A相遇，節(jié)點(diǎn)C會(huì)依據(jù)自身出邊權(quán)重向節(jié)點(diǎn)A傳輸節(jié)點(diǎn)B的PR值分量0.361.

節(jié)點(diǎn)A將保留每次獲得的更大的傳輸值，作為節(jié)點(diǎn)對(duì)其的傳輸值.

因而在原始PageRank公式上定義節(jié)點(diǎn)u獲得節(jié)點(diǎn)v的傳輸值函數(shù)為：

(7)

其中，path(v,u)表示節(jié)點(diǎn)v對(duì)節(jié)點(diǎn)u的所有可能的傳輸路徑，m表示傳輸路徑上的一點(diǎn)，O(m)表示節(jié)點(diǎn)m的出度邊的集合，|L|表示其中一條路徑的長(zhǎng)度.

式(7)中O(m)出度邊集合在本文中由有向評(píng)分權(quán)重函數(shù)代替,所以本文的基于PageRank算法的節(jié)點(diǎn)v對(duì)節(jié)點(diǎn)u的傳輸值函數(shù)為：

(8)

在移動(dòng)網(wǎng)絡(luò)環(huán)境下，節(jié)點(diǎn)v每次將自己當(dāng)前的PR值按照評(píng)分權(quán)重傳輸給周圍的直接鄰居，直接鄰居記錄這些節(jié)點(diǎn)v的PR值分量，然后再將這些分量繼續(xù)傳輸給自己的直接鄰居.因而任意一個(gè)節(jié)點(diǎn)會(huì)比較所有從鄰居節(jié)點(diǎn)獲得的節(jié)點(diǎn)v傳輸值，選取最大的值作為節(jié)點(diǎn)v對(duì)其的傳輸值.

5 移動(dòng)社會(huì)網(wǎng)絡(luò)的消息傳輸算法

本文消息傳輸算法的基本思想是通過(guò)節(jié)點(diǎn)之間的社區(qū)關(guān)系選擇不同的傳輸策略，利用網(wǎng)絡(luò)的社會(huì)特征，在節(jié)點(diǎn)社區(qū)內(nèi)和社區(qū)間選擇合適的中繼節(jié)點(diǎn).從而防止社區(qū)內(nèi)部消息在社區(qū)間的傳輸以及減少跨社區(qū)的消息在非目的節(jié)點(diǎn)社區(qū)內(nèi)部的傳輸，使消息傳輸更有方向性、減少冗余的消息傳輸.

5.1 傳輸策略的選擇

本文算法根據(jù)消息傳輸?shù)哪康牡毓?jié)點(diǎn)和相遇節(jié)點(diǎn)之間的社區(qū)關(guān)系，選擇不同的路由策略.當(dāng)節(jié)點(diǎn)u攜帶目的地為節(jié)點(diǎn)d的消息，和節(jié)點(diǎn)v相遇時(shí)，節(jié)點(diǎn)u會(huì)根據(jù)和相遇節(jié)點(diǎn)v的不同社區(qū)關(guān)系，同時(shí)考慮節(jié)點(diǎn)u，v之間的社會(huì)活躍度、消息目標(biāo)節(jié)點(diǎn)的傳輸值等特征選擇不同的路由傳輸策略.具體策略如下：

1) 如果消息攜帶節(jié)點(diǎn)u及相遇節(jié)點(diǎn)v都不和消息目的地節(jié)點(diǎn)d處于同一社區(qū)，那么將消息傳輸?shù)缴鐣?huì)活躍度高的節(jié)點(diǎn)或者PR值和消息目標(biāo)節(jié)點(diǎn)d的傳輸值都很高的節(jié)點(diǎn)，從而增大發(fā)現(xiàn)和目的地節(jié)點(diǎn)d處于同一社區(qū)的節(jié)點(diǎn)機(jī)會(huì).

這里PR值仍然需要和傳輸值組合在一起作為節(jié)點(diǎn)選擇的依據(jù)，這是因?yàn)楣?jié)點(diǎn)的PR值可以由直接鄰居節(jié)點(diǎn)的傳輸值組成，如對(duì)于節(jié)點(diǎn)u：

(9)

那么：

(10)

因而，節(jié)點(diǎn)傳輸值無(wú)法完全體現(xiàn)出節(jié)點(diǎn)自身的PR值特征.

2) 當(dāng)消息攜帶節(jié)點(diǎn)u及相遇節(jié)點(diǎn)v都和目的地節(jié)點(diǎn)d處于同一社區(qū)，表明消息已經(jīng)很接近目的地節(jié)點(diǎn)，則將消息向PR值和傳輸值都很高的節(jié)點(diǎn)傳輸.

3) 當(dāng)消息攜帶節(jié)點(diǎn)u不和目的地節(jié)點(diǎn)d節(jié)點(diǎn)在同一社區(qū)，而相遇節(jié)點(diǎn)v和目的地節(jié)點(diǎn)d處于同一社區(qū)，那么就將消息傳輸給節(jié)點(diǎn)相遇節(jié)點(diǎn)v.

4) 當(dāng)消息攜帶節(jié)點(diǎn)u不和目的地節(jié)點(diǎn)d節(jié)點(diǎn)處于同一社區(qū)，而相遇節(jié)點(diǎn)v和目的地節(jié)點(diǎn)d也不處于同一社區(qū)，那么就不進(jìn)行消息傳輸.

5.2 算法流程

消息傳輸算法綜合考慮節(jié)點(diǎn)社區(qū)關(guān)系和節(jié)點(diǎn)的傳輸效用值，從而實(shí)現(xiàn)消息傳輸.其具體算法實(shí)現(xiàn)如下：

算法1. 消息傳輸算法.

算法1中，行③～⑦表示節(jié)點(diǎn)攜帶消息和相遇節(jié)點(diǎn)以及目標(biāo)節(jié)點(diǎn)在同一社區(qū)內(nèi)的傳輸情況;行～表示節(jié)點(diǎn)攜帶消息和相遇節(jié)點(diǎn)都不處于同一個(gè)社區(qū)的傳輸情況;而其他行，則表示消息優(yōu)先將消息傳輸給和目標(biāo)節(jié)點(diǎn)同屬一個(gè)社區(qū)的相遇節(jié)點(diǎn)，否則不進(jìn)行傳輸.

對(duì)于算法1的時(shí)間復(fù)雜度，其時(shí)間消耗主要集中在行③、行⑧和行，即節(jié)點(diǎn)u和相遇節(jié)點(diǎn)v消息目的節(jié)點(diǎn)d是否處于同一社區(qū).假設(shè)節(jié)點(diǎn)u和節(jié)點(diǎn)v的本地社區(qū)成員數(shù)目分別為|Cu|和|Cv|，因而算法時(shí)間復(fù)雜度為O(|Cu|+|Cv|).

顯然算法的有效工作依賴于節(jié)點(diǎn)相關(guān)特征屬性的計(jì)算和本地社區(qū)的發(fā)現(xiàn).因此在網(wǎng)絡(luò)當(dāng)中，每當(dāng)2個(gè)節(jié)點(diǎn)相遇時(shí)，都要優(yōu)先互相交換自身特征屬性信息和獲得的其他節(jié)點(diǎn)特征屬性信息.

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

為了評(píng)估算法的性能，本文實(shí)驗(yàn)采用仿真工具ONE[26]，此仿真工具是專門為評(píng)估DTN網(wǎng)絡(luò)路由和算法協(xié)議設(shè)計(jì)的.本文將所提出的消息傳輸算法與Epidemic算法、Prophet算法、BubbleRap算法、Simbet算法在相同實(shí)驗(yàn)環(huán)境下的傳輸性能進(jìn)行了比較.其中,Epidemic算法對(duì)任何相遇的節(jié)點(diǎn)都進(jìn)行消息傳輸,在不考慮緩存大小的理想情況下，能夠獲得最好的傳輸效果，本文把Epidemic算法作為一個(gè)性能比較的上界;Prophet算法是依照節(jié)點(diǎn)相遇概率進(jìn)行消息傳輸?shù)姆椒?而BubblRap算法和Simbet算法都是典型的帶有社會(huì)屬性的消息傳輸方法.

6.1 實(shí)驗(yàn)數(shù)據(jù)

本文使用INFOCOM2005和INFOCOM2006數(shù)據(jù)集驗(yàn)證算法在真實(shí)場(chǎng)景中的性能.

1) INFOCOM2005.該數(shù)據(jù)集采集自分發(fā)給2005年參與INFOCOM學(xué)生研討會(huì)的大概50名學(xué)生的移動(dòng)設(shè)備.這些參與者屬于不同的國(guó)家、區(qū)域或者研究課題組.

2) INFOCOM2006.該數(shù)據(jù)集采集自分發(fā)給2006年參與INFOCOM會(huì)議的與會(huì)人員攜帶的移動(dòng)設(shè)備.人數(shù)相比INFOCOM2005更多，超過(guò)80人.2組數(shù)據(jù)集的一些基本特征如表1所示.數(shù)據(jù)集的用戶活動(dòng)范圍小、記錄周期短，但是相比其他的數(shù)據(jù)集，INFOCOM2005和INFOCOM2006都具有節(jié)點(diǎn)連接發(fā)生頻率高的特點(diǎn).

Table 1 Data Basic Information表1 數(shù)據(jù)基本信息

6.2 參數(shù)設(shè)置

本文對(duì)算法1中的每個(gè)閾值參數(shù)進(jìn)行選擇.根據(jù)人類生活規(guī)律，人們會(huì)在一段時(shí)間內(nèi)進(jìn)行周期性的活動(dòng)，這一段時(shí)間可以是以每周(7 d)作為基礎(chǔ)單元，按照每月(約4周)、每年(約48周)進(jìn)行一段時(shí)期的固定規(guī)律活動(dòng)，而在這一段時(shí)間之后人的行為可能會(huì)改變.而INFOCOM2005和INFOCOM2006數(shù)據(jù)集的數(shù)據(jù)記錄只有3 d左右，所以本文把每天人們的日?；顒?dòng)分為上午、下午、夜晚、午夜4個(gè)時(shí)段[13](各6 h).以每個(gè)時(shí)段作為基礎(chǔ)單元，以每個(gè)基礎(chǔ)單元的倍數(shù)作為一段時(shí)期活動(dòng)的周期時(shí)間單元.

對(duì)于INFOCOM2005和INFOCOM2006數(shù)據(jù)集，本文認(rèn)為如果2個(gè)節(jié)點(diǎn)同時(shí)出席聽(tīng)取同一場(chǎng)學(xué)術(shù)報(bào)告，這2個(gè)節(jié)點(diǎn)更有可能具有“社會(huì)鄰居”關(guān)系[13].考慮在進(jìn)行學(xué)術(shù)報(bào)告時(shí)大家基本是不動(dòng)的，所以本文把上午或下午時(shí)段內(nèi)，學(xué)術(shù)報(bào)告會(huì)時(shí)長(zhǎng)10 800 s(3 h)作為INFOCOM2005和INFOCOM2006數(shù)據(jù)集的鄰居關(guān)系建立閾值.

本文觀察INFOCOM2005和INFOCOM2006數(shù)據(jù)集的節(jié)點(diǎn)對(duì)通信間隔的累積分布log-log圖像，如圖5所示.可以發(fā)現(xiàn)，在43 200 s(2×6 h)之前呈現(xiàn)明顯的冪率分布特征.通過(guò)如圖6的log-line圖像可知，43 200 s(2×6 h)之后，節(jié)點(diǎn)對(duì)的通信間隔大小分布由冪率分布特征轉(zhuǎn)變?yōu)橹笖?shù)分布特征.也就是說(shuō)，固定的活動(dòng)規(guī)律有所改變.所以對(duì)于算法1在實(shí)驗(yàn)中的參數(shù)，鄰居關(guān)系移除的時(shí)間閾值和平滑因子都以12 h作為選取點(diǎn).

Fig. 5 Node contact interval time of log-log complementary cumulative distribution圖5 節(jié)點(diǎn)通信時(shí)間間隔互補(bǔ)累計(jì)分布log-log圖

Fig. 6 Node interval time of log-line complementary cumulative distribution圖6 節(jié)點(diǎn)時(shí)間間隔互補(bǔ)累計(jì)分布log-line圖

本文認(rèn)為節(jié)點(diǎn)屬性的多個(gè)方面是同等重要的，因而PR特征值中的參數(shù)α,β,γ分別取為13.對(duì)本地社區(qū)發(fā)現(xiàn)算法中的相關(guān)參數(shù)λ、σ則參考文獻(xiàn)[24]中的實(shí)驗(yàn)選取0.8.因而本文采用如表2所示的實(shí)驗(yàn)參數(shù).

Table 2 Selection of Threshold Parameter表2 閾值參數(shù)的選取

6.3 仿真場(chǎng)景

本文在實(shí)驗(yàn)中采用50 MB大小的緩存，每45～150 s隨機(jī)產(chǎn)生一個(gè)5 KB左右大小的信息數(shù)據(jù)包，由網(wǎng)絡(luò)中某一節(jié)點(diǎn)隨機(jī)向另外一個(gè)節(jié)點(diǎn)發(fā)送.

6.4 算法評(píng)估

本文用以下指標(biāo)來(lái)評(píng)估相關(guān)算法的性能.

1) 傳輸成功率(delivery ratio).算法的首要目標(biāo)就是獲得更高的傳輸成功率.消息成功率就是在消息整個(gè)傳輸?shù)倪^(guò)程中目標(biāo)節(jié)點(diǎn)成功接收到消息數(shù)與在源節(jié)點(diǎn)所傳輸?shù)乃邢?shù)比值，反映了傳輸成功率.

2) 傳輸冗余率(overhead ratio).冗余率定義為每當(dāng)成功接收一個(gè)消息數(shù)據(jù)包所需要的額外傳輸次數(shù).此參數(shù)反映了消息的冗余傳輸次數(shù).節(jié)點(diǎn)在移動(dòng)社會(huì)網(wǎng)絡(luò)中進(jìn)行間歇性通信，節(jié)點(diǎn)之間的相遇機(jī)會(huì)有限，能以越少冗余傳輸次數(shù)完成消息傳輸，說(shuō)明算法性能越好.同時(shí)，對(duì)于復(fù)制型的算法，節(jié)點(diǎn)會(huì)在每次傳輸時(shí)創(chuàng)建消息副本，冗余傳輸次數(shù)過(guò)多，會(huì)產(chǎn)生更多的消息副本，影響網(wǎng)絡(luò)傳輸性能.

傳輸冗余率=

3) 平均延時(shí)(average delay).消息延時(shí)是指節(jié)點(diǎn)發(fā)送的消息從源節(jié)點(diǎn)成功到達(dá)目標(biāo)節(jié)點(diǎn)所需的時(shí)間.平均消息延時(shí)體現(xiàn)了網(wǎng)絡(luò)的實(shí)時(shí)性，同時(shí)也間接反映了整個(gè)網(wǎng)絡(luò)的消息流通是否正常.雖然在延遲容忍網(wǎng)絡(luò)環(huán)境下，無(wú)法像傳統(tǒng)網(wǎng)絡(luò)那樣要求消息的傳輸延時(shí)，但是消息的傳輸延時(shí)比較低時(shí)，節(jié)點(diǎn)可以盡早釋放緩存中的數(shù)據(jù)，提升網(wǎng)絡(luò)的傳輸性能.

Fig. 7 Message delivery ratio圖7 消息傳輸成功率

6.5 結(jié)果分析

在仿真過(guò)程當(dāng)中，本文通過(guò)改變每次實(shí)驗(yàn)的不同生存時(shí)間(time to live, TTL)來(lái)比較各個(gè)路由算法的消息傳輸成功率、網(wǎng)絡(luò)傳輸冗余率、傳輸平均延時(shí).

本文首先對(duì)比每一個(gè)算法的消息傳輸成功率.如圖7所示，隨著TTL增加，消息傳輸?shù)某晒β书_(kāi)始提高.這是因?yàn)橄⒌腡TL增大使數(shù)據(jù)信息在緩存中駐留的時(shí)間更長(zhǎng)了.因此攜帶消息的節(jié)點(diǎn)更有可能和目的地節(jié)點(diǎn)相遇.

Fig. 8 Message overhead ratio圖8 消息傳輸冗余率

很明顯，相比帶有社會(huì)屬性的SimBet算法和同樣使用社區(qū)發(fā)現(xiàn)策略的BubbleRap算法，本文提出的SocialEvalution算法的傳輸成功率要更好.相比SimBet在INFOCOM2005和INFOCOM2006數(shù)據(jù)集中，最高的成功率提升了約6.8%和29.3%，相比BubbleRap算法提升了約3%和4%.從實(shí)驗(yàn)可知，SimBet算法非常不適應(yīng)現(xiàn)實(shí)稀疏特征的數(shù)據(jù)集，其傳輸成功率很低.而本文算法和Prophet算法的傳輸成功率比較接近，甚至在INFOCOM2005的數(shù)據(jù)集中，本文的SocialEvalution算法和Prophet算法都非常逼近Epidemic算法的發(fā)送成功率.

對(duì)于實(shí)驗(yàn)中每個(gè)算法的傳輸冗余率，從圖8中可以觀察到，因?yàn)镋pidemic算法的無(wú)差異洪泛性傳輸，節(jié)點(diǎn)之間的冗余中繼傳輸次數(shù)很多.在消息的傳輸過(guò)程中，網(wǎng)絡(luò)中的大多數(shù)節(jié)點(diǎn)都對(duì)消息進(jìn)行了傳輸.因而2個(gè)數(shù)據(jù)集中，Epidemic算法的消息冗余中繼傳輸次數(shù)非常高，而SimBet算法的傳輸冗余率在2個(gè)數(shù)據(jù)集的仿真實(shí)驗(yàn)中都比較小，但是實(shí)驗(yàn)結(jié)果表明其相比其他算法的傳輸成功率要低.Bubble算法的傳輸冗余率要比本文的算法和Prophet算法的傳輸冗余率要小，但是其傳輸成功率相比本文算法要低.

對(duì)于算法的傳輸冗余率，顯然攜帶消息的節(jié)點(diǎn)直接等待消息傳輸?shù)哪康墓?jié)點(diǎn)出現(xiàn)的傳輸冗余率是最低的，但是這種模式的傳輸效果顯然是最差的.如果消息通過(guò)一些中繼節(jié)點(diǎn)更快地被傳輸?shù)侥康墓?jié)點(diǎn)，那么消息在傳輸過(guò)程中的中繼節(jié)點(diǎn)很多會(huì)造成其傳輸次數(shù)增多，這將導(dǎo)致算法的冗余率升高，但是卻可以保證消息傳輸?shù)难訒r(shí)和傳輸成功率.因而還需要比較各個(gè)算法的平均延時(shí).

Fig. 9 Message average delay圖9 網(wǎng)絡(luò)傳輸平均延時(shí)

本文的SocialEvalution算法避免消息向個(gè)別節(jié)點(diǎn)過(guò)于集中傳輸，節(jié)點(diǎn)會(huì)選擇其他的候選節(jié)點(diǎn)作為消息中繼節(jié)點(diǎn)，因而這會(huì)造成消息的冗余傳輸次數(shù)增加.所以SocialEvalutio算法的冗余率比SimBet和Bubble都要高，但是本文的SocialEvalution算法顯然要比Prophet算法冗余率要低，而且算法的傳輸成功率和Prophet相比沒(méi)有下降.

如圖9所示，實(shí)驗(yàn)表明SimBet算法和BubbleRap算法的平均傳輸延時(shí)很高，而Epidemic算法的消息傳輸?shù)暮榉翰呗允瓜⒌钠骄訒r(shí)最低.INFOCOM2005數(shù)據(jù)集中，本文SocialEvalution算法的發(fā)送延時(shí)和Prophet算法很接近.而在2個(gè)數(shù)據(jù)集中，當(dāng)消息的TTL大于12 h時(shí)，SocialEvalution算法的消息平均延時(shí)相比Prophet算法的平均延時(shí)出現(xiàn)升高.

這種結(jié)果的出現(xiàn)是由于SocialEvalution中如6.2節(jié)實(shí)驗(yàn)設(shè)置部分所述，將鄰居關(guān)系移除閾值設(shè)定為12 h，而12 h之后社區(qū)算法刪除了一些老化的社區(qū)成員節(jié)點(diǎn).在實(shí)驗(yàn)中，這些被刪除的節(jié)點(diǎn)可能依然會(huì)偶爾和消息攜帶節(jié)點(diǎn)產(chǎn)生相遇，進(jìn)而有機(jī)會(huì)獲得消息，并將消息傳輸給目的節(jié)點(diǎn)，這種情況降低了Prophet算法的傳輸平均延時(shí).

7 總結(jié)與展望

本文基于建立的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)了本地社區(qū)算法；根據(jù)節(jié)點(diǎn)的移動(dòng)行為規(guī)律提出了節(jié)點(diǎn)的社會(huì)活躍度概念；利用PageRank算法計(jì)算節(jié)點(diǎn)的多屬性特征PR特征值，并給出節(jié)點(diǎn)間傳輸值的定義；在此基礎(chǔ)之上，設(shè)計(jì)和實(shí)現(xiàn)了移動(dòng)社會(huì)網(wǎng)絡(luò)消息傳輸算法；最后在真實(shí)數(shù)據(jù)集合上驗(yàn)證本文消息傳輸算法的性能.實(shí)驗(yàn)表明本文的路由算法相比其他算法具有更好的傳輸效果.

在實(shí)際環(huán)境中，網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)移動(dòng)方式復(fù)雜多變.移動(dòng)社會(huì)網(wǎng)絡(luò)的消息傳輸研究難點(diǎn)，便在于如何挖掘和利用節(jié)點(diǎn)之間潛在的行為模式信息，進(jìn)而實(shí)現(xiàn)消息的路由傳輸.因?yàn)榫W(wǎng)絡(luò)本身所具有的社會(huì)性特征，利用網(wǎng)絡(luò)中存在的社會(huì)特性可以預(yù)測(cè)節(jié)點(diǎn)的移動(dòng)行為，改善網(wǎng)絡(luò)傳輸性能.

未來(lái)計(jì)劃更加深入地分析消息在節(jié)點(diǎn)間的傳輸特性，研究節(jié)點(diǎn)之間存在的社會(huì)關(guān)系，從而探索更好的社區(qū)發(fā)現(xiàn)算法和深入挖掘節(jié)點(diǎn)的社會(huì)特征.

[1]Chaintreau A, Pan Hui, Crowcroft J, et al. Impact of human mobility on opportunistic forwarding algorithms [J]. IEEE Trans on Mobile Computing, 2007, 6(6): 606-620

[2]Karagiannis T, Boudec L J Y, Vojnovic＇ M, et al. Power law and exponential decay of inter contact times between mobile devices[C] //Proc of the 13th Annual ACM Int Conf on Mobile Computing and Networking (MobiCom’07). New York: ACM, 2007: 183-194

[3]Passarella A, Conti M, Boldrini C, et al. Modelling inter-contact times in social pervasive networks[C] //Proc of the 14th ACM Int Conf on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWi M’11). New York: ACM, 2011: 333-340

[4]Tian Ye, Li Jiang. Heterogeneity of device contact process in pocket switched networks[C] //Proc of the 5th Int Conf on Wireless Algorithms, Systems and Applications(WASA’10). New York: ACM, 2010: 157-166

[5]Fall K. A delay-tolerant network architecture for challenged Internets[C] //Proc of the 2003 Applications, Technologies, Architectures and Protocols for Computer Communications (SIGCOMM’03). New York: ACM, 2003: 27-34

[6]Jain S, Fall K, Patra R. Routing in a delay tolerant network[C] //Proc of the 2004 Applications, Technologies, Architectures and Protocols for Computer Communications(SIGCOMM’04). New York: ACM, 2004: 145-158

[7]Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: The single-copy case [J]. IEEE/ACM Trans on Network, 2008, 16(1): 63-76

[8]Spyropoulos T, INRIA, Psounis K, et al. Efficient routing in intermittently connected mobile networks: The multiple-copy case[J]. IEEE/ACM Trans on Network, 2008, 16(1): 77-90

[9]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

[10]Yang Zhenguo, Huang Liusheng, Xiao Mingjun, et al. ACR: An ant-colony-based routing in delay tolerant networks[J]. Journal of Computer Research and Development, 2012, 49(12): 2501-2514 (in Chinese)(楊振國(guó), 黃劉生, 肖明軍, 等.一種基于蟻群算法的容遲網(wǎng)絡(luò)路由策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49 (12): 2501-2514)

[11]Wang En, Yang Yongjian, Li Li. Game of life based congestion control strategy in delay tolerant networks[J]. Journal of Computer Research and Development, 2014, 51(11): 2393-2407 (in Chinese)(王恩, 楊永健, 李蒞. DTN中基于生命游戲的擁塞控制策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51 (11): 2393-2407)

[12]Daly E M, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs[C] //Proc of the 8th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’07). New York: ACM, 2007: 32-40

[13]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay tolerant networks[C] //Proc of the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’08). New York: ACM, 2008: 241-250

[14]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2011, 10(11): 1576-1589

[15]Wu Jie, Xiao Mingjun, Huang Liusheng. Homing spread: Community home-based multi-copy routing in mobile social networks[C] //Proc of the 2003 Int Conf on Computer Communications (INFOCOM’03).Piscataway, NJ: IEEE, 2013: 2319-2327

[16]Li Feng, Wu Jie. LocalCom: A community-based epidemic forwarding scheme in disruption-tolerant networks[C] //Proc of the 2009 Society Conf on Mesh and Ad Hoc Communications and Networks (SECON’09).Piscataway, NJ: IEEE, 2009: 1-9

[17]Gao Wei, Cao Guohong, Porta L T, et al. On exploiting transient social contact patterns for data forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2013, 12 (1): 151-165

[18]Wei Kaimin, Liang Xiao, Xu Ke. A survey of social-aware routing protocols in delay tolerant networks: Applications, taxonomy and design-related issues[J]. Communications Surveys & Tutorials, 2014, 16(1): 556-578

[19]Socievole A, Yoneki E, Rango F D, et al. Opportunistic message routing using multi-layer social networks[C] //Proc of the 2nd ACM Workshop on High Performance Mobile Opportunistic Systems(HP-MOSys’13). New York: ACM, 2013: 39-46

[20]Pietil?inen AK, Oliver E, LeBrun J, et al. Mobiclique: Middleware for mobile social networking[C] //Proc of the 2nd ACM Workshop on Online Social Networks(WOSN’09). New York: ACM, 2009: 49-54

[21]Mtibaa A, May M, Diot C, et al. PeopleRank: Social opportunistic forwarding[C] //Proc of the 2010 Int Conf on Computer Communications (INFOCOM’10).Piscataway, NJ: IEEE, 2010: 1-5

[22]Granovetter M S. The strength of weak ties [J]. American Journal of Sociology, 1973, 78(6): 1360-1380

[23]Ioannidis S, Chaintreau A. On the strength of weak ties in mobile social networks[C] //Proc of the 2nd ACM EuroSys Workshop on Social Network Systems (SNS’09). New York: ACM, 2009: 19-25

[24]Pan Hui, Yoneki E, Chan Shuyan, et al. Distributed community detection in delay tolerant networks[C] //Proc of the 2nd ACM/IEEE Int Workshop on Mobility in The Evolving Internet Architecture(MobiArch’07). New York: ACM, 2007: No.7

[25]Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1): 107-117

[26]Helsinki University of Technology. ONE: Opportunistic network environment[CP]. 2009 [2015-12-03]. http://www.netlab.tkk.fi/tutkimus/dtn/theone

Zhu Ziqing, born in 1990. PhD candidate of Southeast University. His current research interests include social computing and computer network.

Cao Jiuxin, born in 1967. Professor and PhD supervisor of Southeast University. His current research interests include social computing, computer network and complex network.

Zhou Tao, born in 1989. PhD candidate of Southeast University. His current research interests include social computing and complex network.

Xu Shuai, born in 1991. PhD candidate of Southeast University. His current research interests include social computing.

Ma Zhuo, born in 1993. Master candidate of Southeast University. Her current research interests include social computing.

Liu Bo, born in 1975. Professor and master supervisor of Southeast University. Her current research interests include social computing and distributed network management.

Multi-Feature Based Message Transmitting in Mobile Social Network

Zhu Ziqing, Cao Jiuxin, Zhou Tao, Xu Shuai, Ma Zhuo, and Liu Bo

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189) (KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)

Based on the features of delay tolerant network (DTN), mobile social network (MSN) uses “storage-carry-forwards” approach for message transmission between nodes. How to select a suitable relay node for efficient message transmission is an urgent issue in the current research fields. This paper focuses on the problem by analyzing the social characteristics of network in different perspectives. Firstly, based on the interaction between nodes, the model of social relations between nodes is constructed. Secondly, this paper gives the definition of neighbor set and local community based on the network topology and establishes the community relationship between the nodes. Furthermore, this paper defines the social activity based on the behavior of nodes and takes advantage of the PageRank algorithm to obtainPRvalues on the basis of multiple features of nodes. Then, transmission values of nodes is defined by usingPRvalues and different utility values of nodes can be obtained. On this basis, considering community relations of nodes and different transmission utility values of nodes, this paper designs and implements a message transmission algorithm in mobile social network. Finally, experiments show that the algorithm has advantages in delivery ratio, overhead ratio and average delay.

mobile social network (MSN); delay tolerant network (DTN); community detection; PageRank algorithm; dynamic network

2015-12-03；

2016-03-22

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2010CB328104)；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2013AA013503)；國(guó)家自然科學(xué)基金項(xiàng)目(61272531，61202449，61272054，61370207，61370208，61300024，61320106007，61472081)；江蘇省網(wǎng)絡(luò)與信息安全重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目(BM2003201)；江蘇省科技計(jì)劃基金資助項(xiàng)目(SBY2014021039-10) This work was supported by the National Basic Research Program of China (973 Program) (2010CB328104), the National High Technology Research and Development Program of China (863 Program) (2013AA013503), the National Natural Science Foundation of China (61272531, 61202449, 61272054, 61370207, 61370208, 61300024, 61320106007, 61472081), the Jiangsu Provincial Key Laboratory of Network and Information Security Foundation (BM2003201), and the Science and Technology Planning Project of Jiangsu Province (SBY2014021039-10).

曹玖新(jx.cao@seu.edu.cn)

TP393