基于社會(huì)屬性的PSN消息路由算法

曹玖新，陳高君，楊婧，朱子青，劉波

（東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189）

1 引言

隨著手機(jī)等手持設(shè)備的大量普及，利用手持設(shè)備實(shí)現(xiàn)信息傳輸并提供網(wǎng)絡(luò)服務(wù)功能的口袋交換網(wǎng)絡(luò)（PSN， pocket switched network）受到了廣泛的關(guān)注，它是一種由人隨身攜帶的手持設(shè)備組成的特殊的延遲容忍網(wǎng)絡(luò)（DTN， delay tolerance network）網(wǎng)絡(luò)，由2005年劍橋大學(xué)和Intel研究院提出[1]。它利用人類的移動(dòng)性和局域連通性，采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的傳輸模式，利用節(jié)點(diǎn)移動(dòng)而進(jìn)入彼此的通信范圍所產(chǎn)生的數(shù)據(jù)交換機(jī)會(huì)進(jìn)行通信，在移動(dòng)用戶的設(shè)備之間傳遞數(shù)據(jù)。

設(shè)備隨著設(shè)備攜帶者移動(dòng)，而設(shè)備攜帶者的移動(dòng)往往具有目的性和規(guī)律性，因而PSN網(wǎng)絡(luò)具有社會(huì)網(wǎng)絡(luò)特征。研究PSN網(wǎng)絡(luò)中節(jié)點(diǎn)之間構(gòu)成的社會(huì)網(wǎng)絡(luò)有助于發(fā)現(xiàn)節(jié)點(diǎn)行為規(guī)律，預(yù)測(cè)這些無線通信設(shè)備構(gòu)成的通信網(wǎng)絡(luò)的變化趨勢(shì)，有利于更好地發(fā)現(xiàn)信息攜帶節(jié)點(diǎn)、實(shí)現(xiàn)PSN網(wǎng)絡(luò)中的信息路由。

路由問題作為 PSN網(wǎng)絡(luò)中一個(gè)獨(dú)立開放的研究領(lǐng)域，其當(dāng)前研究的熱點(diǎn)是如何更好地選擇中繼節(jié)點(diǎn)以獲得更高的傳遞成功率和更低的網(wǎng)絡(luò)負(fù)載。目前已有越來越多的研究[2～6]開始關(guān)注通過挖掘PSN網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)信息來優(yōu)化路由算法。

通過社交網(wǎng)絡(luò)分析可知，大部分人的活動(dòng)范圍都是局限于一定的區(qū)域或社區(qū)。社區(qū)（community）是一些節(jié)點(diǎn)所組成的子集，而它的內(nèi)部節(jié)點(diǎn)之間的聯(lián)系比社區(qū)之間的聯(lián)系要緊密。為了充分利用 PSN網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)運(yùn)動(dòng)規(guī)律，本文將社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性與移動(dòng)社會(huì)網(wǎng)絡(luò)的特征相結(jié)合，考慮節(jié)點(diǎn)社區(qū)關(guān)系和節(jié)點(diǎn)活躍度對(duì)路由算法的影響，提出了基于社區(qū)關(guān)系的BridgingCom路由算法。算法首先通過每個(gè)節(jié)點(diǎn)識(shí)別出自己所在社區(qū)，獲得局部社區(qū)信息，作為節(jié)點(diǎn)關(guān)系的判斷依據(jù)；然后使用橋接中心度（bridging centrality）作為選擇中繼節(jié)點(diǎn)的依據(jù)，使消息傳遞更有方向性和目的性，盡快從本地傳遞到目標(biāo)節(jié)點(diǎn)。

2 相關(guān)工作

2.1 PSN中的“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”模型

PSN網(wǎng)絡(luò)作為一種特殊的DTN具有網(wǎng)絡(luò)位置稀疏、高延遲、低數(shù)據(jù)傳輸率、節(jié)點(diǎn)間間歇性連接、消息排隊(duì)時(shí)間較長和節(jié)點(diǎn)資源有限等特征。因此，傳統(tǒng)移動(dòng)自組織網(wǎng)絡(luò)中的路由技術(shù)不再適用。為了能夠充分利用節(jié)點(diǎn)移動(dòng)帶來的連接機(jī)會(huì)，PSN在數(shù)據(jù)傳輸時(shí)采用的是“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的模式來克服鏈接的頻繁斷開。

圖1所示為PSN路由過程，即一個(gè)消息的交付過程。源節(jié)點(diǎn)S欲發(fā)送信息至目標(biāo)節(jié)點(diǎn)D，然而在t1時(shí)刻節(jié)點(diǎn)S與D并未發(fā)生接觸且節(jié)點(diǎn)S沒有路徑可以到達(dá)D；于是節(jié)點(diǎn)S將信息數(shù)據(jù)轉(zhuǎn)發(fā)至鄰居節(jié)點(diǎn)1，節(jié)點(diǎn)1在t2將數(shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點(diǎn)3，最后在t3時(shí)刻節(jié)點(diǎn)3與目標(biāo)節(jié)點(diǎn)D相遇并將信息數(shù)據(jù)發(fā)送給D。從上面的示例可以看出，“存儲(chǔ)—攜帶—存儲(chǔ)”模型是“存儲(chǔ)—轉(zhuǎn)發(fā)”模型的拓展，它充分利用了節(jié)點(diǎn)的移動(dòng)能力和存儲(chǔ)能力，為PSN中的信息發(fā)布提供了一個(gè)非常有效的方法。通過該轉(zhuǎn)發(fā)策略，使源節(jié)點(diǎn)不需與目標(biāo)節(jié)點(diǎn)發(fā)生接觸，轉(zhuǎn)而通過中間節(jié)點(diǎn)的運(yùn)載和轉(zhuǎn)發(fā)，成功的將數(shù)據(jù)發(fā)送給目標(biāo)節(jié)點(diǎn)。

圖1 “存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”實(shí)例

2.2 現(xiàn)有PSN網(wǎng)絡(luò)中的路由算法

由于“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”模式的存在，中繼節(jié)點(diǎn)的選擇以及副本數(shù)的確定顯得尤為重要。與傳統(tǒng)Internet以最小跳數(shù)、最短路徑為路由目標(biāo)不同，PSN中不同的應(yīng)用場(chǎng)景可能具有不同特征與不同的目標(biāo)，主要有最小化傳輸延遲、最大化消息傳遞成功率以及最小化緩沖、網(wǎng)絡(luò)帶寬和能量消耗等目標(biāo)。目前已有的PSN的路由算法從不同的角度有不同的分類方法[7]。按照消息復(fù)制策略，已有的PSN路由算法可以分為3大類：?jiǎn)胃北韭酚伞魅韭酚梢约盎谥R(shí)的路由。

在單副本路由中，任何時(shí)間網(wǎng)絡(luò)中只有一個(gè)節(jié)點(diǎn)攜帶同一消息。單副本路由的開銷很小，但通常交付延遲較高，可靠性相對(duì)較低。

傳染路由(epidemic routing)[8]中每個(gè)節(jié)點(diǎn)都不進(jìn)行路由決策，而將消息泛洪給自己所有的鄰居節(jié)點(diǎn)。如果所有的節(jié)點(diǎn)都能夠充分移動(dòng)，傳染路由能夠幾乎將所有的數(shù)據(jù)都正確分發(fā)，由于傳染路由窮舉了所有可能的傳輸路徑，消耗資源嚴(yán)重，在現(xiàn)實(shí)中，能量、帶寬、緩沖等資源缺乏而造成資源競(jìng)爭(zhēng)，傳染路由性能會(huì)嚴(yán)重降級(jí)。

不依賴于網(wǎng)絡(luò)知識(shí)的路由方式中消息傳輸顯得較盲目，為了充分利用資源，基于知識(shí)啟發(fā)的路由決策可使消息傳遞的方向明確。根據(jù)依據(jù)的網(wǎng)絡(luò)知識(shí)不同可以細(xì)分為基于上下文的路由、基于歷史信息的路由和基于社交信息的路由。如基于傳輸預(yù)測(cè)的路由算法[9]利用歷史連接數(shù)據(jù)計(jì)算傳遞概率，預(yù)測(cè)節(jié)點(diǎn)相遇概率，為每個(gè)節(jié)點(diǎn)計(jì)算到達(dá)目標(biāo)節(jié)點(diǎn)的傳輸預(yù)測(cè)值，將消息副本向傳輸預(yù)測(cè)值大的節(jié)點(diǎn)傳遞。與傳統(tǒng)的不考慮歷史數(shù)據(jù)的路由算法相比它們具有更好的性能。

近年來，基于社交信息的 DTN路由研究受到了廣泛的關(guān)注，PSN作為典型的具有社交屬性的DTN網(wǎng)絡(luò)表現(xiàn)出小世界[10]、有差異的節(jié)點(diǎn)中心度[11，12]、有周期規(guī)律性的活動(dòng)、節(jié)點(diǎn)分布廣等特征。利用PSN網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)在社會(huì)關(guān)系，可有效地解決移動(dòng)社會(huì)網(wǎng)絡(luò)中信息傳輸效率和準(zhǔn)確性較低的問題。SimBet路由算法[2]同時(shí)考慮以當(dāng)前節(jié)點(diǎn)為中心的Ego網(wǎng)絡(luò)的中心度（Ego-centric centrality）和社會(huì)相似性決定消息轉(zhuǎn)發(fā)。消息向中心度高的節(jié)點(diǎn)轉(zhuǎn)發(fā)，提高成功選擇有效中繼節(jié)點(diǎn)的可能性。文獻(xiàn)[13]基于地理位置進(jìn)行網(wǎng)絡(luò)劃分，獲得節(jié)點(diǎn)社區(qū)關(guān)系，但這種劃分方法根據(jù)位置進(jìn)行劃分而不是根據(jù)節(jié)點(diǎn)本身劃分。Bubble Rap算法[3]選擇介數(shù)中心度（betweenness centrality）高的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)所在社區(qū)節(jié)點(diǎn)作為中繼。消息到達(dá)目標(biāo)社區(qū)前，相遇節(jié)點(diǎn)之間比較全局中心度，到達(dá)目標(biāo)社區(qū)后，相遇節(jié)點(diǎn)比較局部中心度。因此，消息在傳輸過程中會(huì)涌向中心度高的節(jié)點(diǎn)，這些節(jié)點(diǎn)的資源被迅速消耗掉。Hu等人在Bubble Rap算法的基礎(chǔ)上加入SRL（social relation level），提出了 BiBUBBLE 算法[14]，在中繼節(jié)點(diǎn)選擇時(shí)除了考慮節(jié)點(diǎn)的介數(shù)中心度外，也考慮節(jié)點(diǎn)的SRL值，增加中繼節(jié)點(diǎn)數(shù)目，提高傳輸效率。CAF算法[15]在原有路由算法的基礎(chǔ)上加入多宿主節(jié)點(diǎn)（multi-homed node）概念，在社區(qū)之間通過多宿主節(jié)點(diǎn)傳遞消息，提高消息傳遞準(zhǔn)確性。文獻(xiàn)[16]發(fā)現(xiàn)具有相似偏好的設(shè)備攜帶者更有可能相遇，因此文章提出使用k維向量表示其偏好并將消息轉(zhuǎn)發(fā)給具有相似偏好的節(jié)點(diǎn)。文獻(xiàn)[17]同時(shí)考慮中心度及用戶偏好，基于用戶偏好信息計(jì)算中心度。2012年 Matthew Orlinski等人提出了基于Epidemic算法的 QualityEpidemic算法[18]，使用已有的社區(qū)識(shí)別算法將節(jié)點(diǎn)劃分為不同社區(qū)，節(jié)點(diǎn)只把消息傳遞給與目標(biāo)節(jié)點(diǎn)相同社區(qū)的節(jié)點(diǎn)。該算法適用性比較強(qiáng)，但是否能夠?qū)⑾鬟f到目標(biāo)節(jié)點(diǎn)依賴于節(jié)點(diǎn)的移動(dòng)性。文獻(xiàn)[19]基于分簇結(jié)構(gòu)將移動(dòng)規(guī)律相似的節(jié)點(diǎn)聚合為最近社交圈的節(jié)點(diǎn)簇，并提出基于分簇結(jié)構(gòu)的路由協(xié)議，路由分為簇外噴射、簇間轉(zhuǎn)發(fā)和簇內(nèi)傳染3個(gè)階段。

由于PSN網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模式、應(yīng)用場(chǎng)景、路由優(yōu)化目標(biāo)都有所不同，因此每個(gè)PSN中路由算法的側(cè)重點(diǎn)都不同。在沒有基礎(chǔ)設(shè)施的情況下，充分利用便攜設(shè)備節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)處理以及網(wǎng)絡(luò)通信功能，研究人的移動(dòng)和相遇規(guī)律，PSN可以更高效地完成數(shù)據(jù)在不同節(jié)點(diǎn)間傳輸，實(shí)現(xiàn)數(shù)據(jù)的交換和信息共享。在信息服務(wù)、災(zāi)難救援、軍事領(lǐng)域等很多方面都具有良好的應(yīng)用前景。

3 相關(guān)概念

本章首先給出PSN形式化網(wǎng)絡(luò)模型，然后基于此模型介紹局部社區(qū)識(shí)別算法中使用到的基本概念，最后給出節(jié)點(diǎn)中心度的定義和計(jì)算方法。

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

為了便于網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)系分析，方便地表達(dá)社會(huì)網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)，更準(zhǔn)確地進(jìn)行社區(qū)關(guān)系分析，這里將PSN網(wǎng)絡(luò)建模為具有時(shí)間屬性的無向圖，其形式化描述如下。

給定Gt(V，E)，其中，V是網(wǎng)絡(luò)中的頂點(diǎn)集合，|V|=n；E為網(wǎng)絡(luò)中2個(gè)正在通信的節(jié)點(diǎn)之間連接邊的集合，|E|=m。節(jié)點(diǎn)u、v之間的邊權(quán)重用T(u，v)表示，本文使用節(jié)點(diǎn)間累計(jì)通信時(shí)間作為T(u，v)的度量。

3.2 熟知集合和局部社區(qū)

為了便于下文描述局部社區(qū)識(shí)別算法，首先定義社區(qū)識(shí)別算法中的基本概念。

定義1熟知集合（familiar set）。對(duì)于一個(gè)給定的頂點(diǎn)vi，它的完整的熟知集合形式化表示為Fi

其中，T(vj，vi)表示vj與vi之間的累計(jì)連接時(shí)間，Tth是時(shí)間閾值，Ni表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合。節(jié)點(diǎn)的熟知集合保存的是當(dāng)前節(jié)點(diǎn)的鄰居集合中節(jié)點(diǎn)的累積連接時(shí)間超過閾值Tth的所有節(jié)點(diǎn)。

定義2局部社區(qū)（local community）。對(duì)于一個(gè)給定的頂點(diǎn)vi，它的局部社區(qū)表示為Ci，它包括熟知集合Fi中的所有節(jié)點(diǎn)和通過局部社區(qū)識(shí)別算法獲取的節(jié)點(diǎn)。

一般社區(qū)識(shí)別算法需要通過分析整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)，將網(wǎng)絡(luò)劃分為若干個(gè)相互分離的社區(qū)[20]，本文中使用的社區(qū)識(shí)別算法是通過節(jié)點(diǎn)局部知識(shí)獲得節(jié)點(diǎn)所在的社區(qū)信息，因此稱為局部社區(qū)。由于網(wǎng)絡(luò)動(dòng)態(tài)變化和有限的網(wǎng)絡(luò)信息知識(shí)，可能本屬于同一社區(qū)的節(jié)點(diǎn)會(huì)分配到不同的局部社區(qū)。

定義3Ego網(wǎng)絡(luò)(Ego network)[21]。對(duì)于給定的節(jié)點(diǎn)v，它的 Ego網(wǎng)絡(luò)是指節(jié)點(diǎn)v本身、v的直接鄰居以及它們之間的連接關(guān)系組成的子網(wǎng)。

3.3 節(jié)點(diǎn)中心度定義

為了使消息能夠盡快進(jìn)入目標(biāo)節(jié)點(diǎn)所在社區(qū)，識(shí)別出可以在2個(gè)社區(qū)之間起到溝通橋梁作用的節(jié)點(diǎn)成為關(guān)鍵。因此，本文使用橋接中心度作為節(jié)點(diǎn)中心度[11]的排名依據(jù)。

橋接中心度(bridging centrality)[22]能夠很好地識(shí)別出位于不同社區(qū)之間的起到橋梁溝通作用的節(jié)點(diǎn)。橋接中心度BC定義如式(1)所示。

其中，Csoc(v)表示節(jié)點(diǎn)v的介數(shù)中心度[23]，如式(2)所示。

β(v) 為橋接系數(shù)（bridging coefficient），如式(3)所示。

其中，gjk表示j與k之間的最短路徑數(shù)，gjk(pi)表示j與k之間的最短路徑中通過i的數(shù)目，d(i)表示節(jié)點(diǎn)i的度（degree）值。

Csoc(v)可以衡量網(wǎng)絡(luò)中通過該節(jié)點(diǎn)的最短路徑的數(shù)目，表示節(jié)點(diǎn)在網(wǎng)絡(luò)中的社會(huì)重要性；β(v)表示節(jié)點(diǎn)在信息流中的重要性，反映了節(jié)點(diǎn)位于緊密連接的區(qū)域之間的程度，衡量節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)中的重要性。

在PSN中，網(wǎng)絡(luò)動(dòng)態(tài)變化，節(jié)點(diǎn)之間沒有穩(wěn)定的連接，網(wǎng)絡(luò)拓?fù)銰t(V，E)隨時(shí)發(fā)生著改變，2個(gè)相遇節(jié)點(diǎn)很難獲得整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。因此，本文利用當(dāng)前節(jié)點(diǎn)的局部社區(qū)信息，在當(dāng)前節(jié)點(diǎn)的Ego網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)的橋接中心度，式(4)為本文使用的橋接中心度計(jì)算公式。

考慮到PSN中很可能在某一時(shí)刻不是一個(gè)完全連通圖，網(wǎng)絡(luò)連接圖中有度為0的局部獨(dú)立節(jié)點(diǎn)存在，也就意味著不會(huì)有其他節(jié)點(diǎn)的消息通過此節(jié)點(diǎn)。為了保證在計(jì)算β(v)時(shí)不發(fā)生除以 0溢出問題，式(4)設(shè)定如果節(jié)點(diǎn)V的度d(v)為0，將(v)賦值為0。

4 基于社會(huì)屬性的BridingCom路由算法

由社交網(wǎng)絡(luò)分析可知，大部分人的活動(dòng)范圍都是局限于一定的區(qū)域或社區(qū)。如果目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)并不在同一個(gè)活躍社區(qū)，消息在超時(shí)之前被傳遞到目標(biāo)節(jié)點(diǎn)可能需要經(jīng)過其他中間社區(qū)，成功傳遞的概率將會(huì)受限。如果消息的傳播范圍被限制在“局部”，不僅造成消息無法成功投遞，還占用了中繼節(jié)點(diǎn)寶貴的緩存空間，影響其他有可能成功送達(dá)目的地的消息接收。有效利用節(jié)點(diǎn)的節(jié)點(diǎn)歷史運(yùn)動(dòng)軌跡和社會(huì)活動(dòng)關(guān)系可以使消息傳遞更有方向性和目的性，提高路由效率，降低傳輸延遲。

但是，PSN網(wǎng)絡(luò)結(jié)構(gòu)實(shí)時(shí)發(fā)生改變，并且節(jié)點(diǎn)沒有辦法通過統(tǒng)一平臺(tái)（如 Internet等）獲得統(tǒng)一服務(wù)器提供的網(wǎng)絡(luò)全局?jǐn)?shù)據(jù)，網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)無法獲得整個(gè)網(wǎng)絡(luò)的實(shí)時(shí)結(jié)構(gòu)。目前已有的根據(jù)整個(gè)網(wǎng)絡(luò)拓?fù)鋵?duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)進(jìn)行的研究[20]都不適合PSN這種動(dòng)態(tài)變化的網(wǎng)絡(luò)，因此本文通過局部社區(qū)識(shí)別算法獲得節(jié)點(diǎn)的社區(qū)信息。

在局部社區(qū)識(shí)別的基礎(chǔ)上，本文基于節(jié)點(diǎn)歷史運(yùn)動(dòng)軌跡和社會(huì)學(xué)研究理論，提出了一種基于社會(huì)信息的BridgingCom路由算法。該算法的基本思想是通過節(jié)點(diǎn)之間的社區(qū)關(guān)系為不同節(jié)點(diǎn)選擇不同的路由方向，防止社區(qū)內(nèi)部消息在社區(qū)間的傳遞以及減少社區(qū)間的消息在社區(qū)內(nèi)部的傳遞，從而使消息傳遞更有方向性、降低網(wǎng)絡(luò)負(fù)載。當(dāng)消息未達(dá)到目標(biāo)節(jié)點(diǎn)所在社區(qū)，選擇全局中心度高的節(jié)點(diǎn)，增加接觸到目標(biāo)節(jié)點(diǎn)的機(jī)會(huì)；當(dāng)消息已經(jīng)傳遞到目標(biāo)節(jié)點(diǎn)所在社區(qū)時(shí)，選擇本地中心度高的節(jié)點(diǎn)，防止消息擴(kuò)散。

4.1 局部社區(qū)識(shí)別算法

為了根據(jù)社區(qū)信息選擇合適的中繼節(jié)點(diǎn)，節(jié)點(diǎn)能夠正確、高效地識(shí)別出自己所在的社區(qū)信息是需要解決的首要問題。為了獲得節(jié)點(diǎn)的社區(qū)信息，本文從節(jié)點(diǎn)局部出發(fā)，采用局部社區(qū)識(shí)別算法，根據(jù)節(jié)點(diǎn)歷史通信記錄，尋找節(jié)點(diǎn)所在的社區(qū)信息并實(shí)時(shí)更新。

2007年P(guān)an Hui等人提出的Simple局部社區(qū)識(shí)別算法[24]通過進(jìn)入彼此通信范圍的節(jié)點(diǎn)交換獲得彼此的局部信息，更新局部知識(shí)，計(jì)算節(jié)點(diǎn)所在社區(qū)。在Simple局部社區(qū)識(shí)別算法中，節(jié)點(diǎn)不斷累加與鄰居節(jié)點(diǎn)的連接時(shí)間，隨著時(shí)間推移，每個(gè)節(jié)點(diǎn)存儲(chǔ)的歷史信息會(huì)逐步增加。

長時(shí)間未聯(lián)系的節(jié)點(diǎn)信息不僅浪費(fèi)存儲(chǔ)空間，而且還可能會(huì)對(duì)未來行為預(yù)測(cè)產(chǎn)生錯(cuò)誤的指導(dǎo)作用。因此，在Simple局部社區(qū)識(shí)別算法的基礎(chǔ)上加入連接老化機(jī)制，算法基本思想如算法1所示。

算法1帶有老化機(jī)制的局部社區(qū)識(shí)別算法

輸入：本節(jié)點(diǎn)s的局部社區(qū)Cloc(s)=φ；

熟知集合F(s)；

連接節(jié)點(diǎn)的u的局部社區(qū)Cloc(u)；

熟知集合F(u)。

輸出：節(jié)點(diǎn)s所在的局部社區(qū)Cloc(s)；

更新后的熟知集合F(s)。

①從源節(jié)點(diǎn)s的開始，初始化

②當(dāng)s與節(jié)點(diǎn)u相遇時(shí)，交換彼此的本地信息；

③節(jié)點(diǎn)s根據(jù)連接老化閾值T更新局部社區(qū)，刪除超過時(shí)間T未再遇到的節(jié)點(diǎn)；

④若節(jié)點(diǎn)u不在s的熟知集合F(s)中，s更新與u之間的連接時(shí)間記錄，若連接時(shí)間超過設(shè)定閾值，將u并入F(s)和Cloc(s)；

⑤節(jié)點(diǎn)u不在Cloc(s)時(shí)，若，將u并入到Cloc(s)，其中λ為并入閾值；

⑥若u已經(jīng)通過前幾步被加入到Cloc(s)，則考慮是否合并2個(gè)局部社區(qū)：如果2個(gè)局部社區(qū)的重疊區(qū)域中的節(jié)點(diǎn)數(shù)則合并2個(gè)局部社區(qū)，其中γ為合并閾值。

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)需要保存的信息包括需傳遞的消息列表，以及本節(jié)點(diǎn)的熟知集合F和目前的局部社區(qū)標(biāo)識(shí)C及社區(qū)內(nèi)成員，以便當(dāng)節(jié)點(diǎn)相遇時(shí)交換彼此攜帶的信息，更新節(jié)點(diǎn)的局部社區(qū)知識(shí)。

算法1中的連接老化機(jī)制主要通過時(shí)間閾值T控制熟知集合和局部社區(qū)中節(jié)點(diǎn)增刪發(fā)揮作用。當(dāng)節(jié)點(diǎn)s遇到其他節(jié)點(diǎn)后，首先更新節(jié)點(diǎn)的局部社區(qū)信息，然后根據(jù)相遇節(jié)點(diǎn)是否在s的熟知集合和局部社區(qū)集合內(nèi)做不同的操作：如果節(jié)點(diǎn)已經(jīng)在s的局部社區(qū)內(nèi)，則根據(jù)2個(gè)節(jié)點(diǎn)的熟知集合和局部社區(qū)集合的重合度更新節(jié)點(diǎn)s的局部社區(qū)集合。這樣不僅可以節(jié)約緩存空間，而且還可以減弱過時(shí)的歷史信息對(duì)算法的影響，使算法更加準(zhǔn)確地反映網(wǎng)絡(luò)節(jié)點(diǎn)實(shí)時(shí)的傳輸能力。

4.2 BridgingCom路由算法

在PSN網(wǎng)絡(luò)中，消息是在相遇節(jié)點(diǎn)之間不斷復(fù)制傳遞的，節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械闹匾杂绊懥讼鞑サ男剩?，處于網(wǎng)絡(luò)核心地帶的節(jié)點(diǎn)更容易將消息傳遞出去，而在網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)則不具備這種能力。因此，在4.1節(jié)中局部社區(qū)識(shí)別算法獲得的局部社區(qū)信息的基礎(chǔ)上，BridingCom算法根據(jù)要傳遞消息的目標(biāo)節(jié)點(diǎn)與相遇節(jié)點(diǎn)的社區(qū)關(guān)系，選擇不同的路由策略。

1)跨社區(qū)傳遞：如果消息攜帶節(jié)點(diǎn)s及相遇節(jié)點(diǎn)都不知道目標(biāo)節(jié)點(diǎn)d的方位（都不在目標(biāo)節(jié)點(diǎn)所在的社區(qū)），將消息發(fā)送到橋接中心度高的節(jié)點(diǎn)，增加接觸到目標(biāo)節(jié)點(diǎn)所在社區(qū)的機(jī)會(huì)。

2)社區(qū)內(nèi)傳遞：當(dāng)目標(biāo)節(jié)點(diǎn)與相遇節(jié)點(diǎn)處于相同社區(qū)，表明消息已經(jīng)接近目標(biāo)節(jié)點(diǎn)，因此將消息推送到社區(qū)內(nèi)重要性高的節(jié)點(diǎn)，這里使用節(jié)點(diǎn)u的Ego網(wǎng)絡(luò)中的邊數(shù)作為局部中心度，使用LocalRank(u)表示。

圖2描述了BridingCom算法的基本思想，展示了具有3個(gè)社區(qū)的網(wǎng)絡(luò)中2個(gè)消息的傳遞路徑。設(shè)網(wǎng)絡(luò)中的3個(gè)社區(qū)分別為社區(qū)A、社區(qū)B與社區(qū)C。當(dāng)社區(qū)A中節(jié)點(diǎn)S有消息要傳遞到社區(qū)A中的節(jié)點(diǎn)D1時(shí)，社區(qū)內(nèi)節(jié)點(diǎn)S與節(jié)點(diǎn)D1雖然無法直接通信，此時(shí)選取中心度高的節(jié)點(diǎn)，可以高效地將消息傳遞給D1。當(dāng)社區(qū)A中節(jié)點(diǎn)S有消息要傳遞到社區(qū)C中的節(jié)點(diǎn)D2時(shí)，假設(shè)最佳路徑需要通過社區(qū)B中節(jié)點(diǎn)才能到達(dá)社區(qū)C中的節(jié)點(diǎn)D2。此時(shí)根據(jù)BridgingCom算法選取位于2個(gè)社區(qū)之間的“橋節(jié)點(diǎn)”，盡快將消息推送出S所在的社區(qū)A，傳遞到邊界節(jié)點(diǎn)N1，然后通過連接社區(qū)A與社區(qū)B的節(jié)點(diǎn)B1傳遞到社區(qū)B，進(jìn)而獲得到達(dá)社區(qū)C中節(jié)點(diǎn)D2的路徑。

圖2 “消息傳遞”實(shí)例

BridgingCom路由算法如算法2所示。其中，節(jié)點(diǎn)的社區(qū)信息通過局部社區(qū)識(shí)別算法獲得。

算法2BridgingCom路由算法

輸入：本地節(jié)點(diǎn)s；相遇節(jié)點(diǎn)u；要傳遞的消息m；m的目標(biāo)節(jié)點(diǎn)t

輸出：消息是否復(fù)制傳遞成功；

① 當(dāng)節(jié)點(diǎn)s遇到節(jié)點(diǎn)u，更新節(jié)點(diǎn)s的局部社區(qū)集合C(s)；

② 當(dāng)目標(biāo)節(jié)點(diǎn)t在節(jié)點(diǎn)s所在社區(qū)t∈C(s)，如果u∈C(s)，則轉(zhuǎn)到③，否則算法結(jié)束；

③ 計(jì)算節(jié)點(diǎn)s的局部中心度LocalRank（s）與節(jié)點(diǎn)u的局部中心度LocalRank（u），如果LocalRank（s） ≤LocalRank（u），則將消息復(fù)制傳遞給u，否則算法結(jié)束；

④ 當(dāng)目標(biāo)節(jié)點(diǎn)t不在節(jié)點(diǎn)s所在社區(qū)即t?C(s)，如果相遇節(jié)點(diǎn)u與目標(biāo)節(jié)點(diǎn)t在同一社區(qū)t∈C(u)時(shí)，則將消息復(fù)制傳遞給u，否則轉(zhuǎn)到⑤；

⑤ 如果沒有傳遞消息，則計(jì)算節(jié)點(diǎn)s的橋接中心度(s)和節(jié)點(diǎn)u的橋接中心度(u)，如果(u)≥(s)，則同樣將消息復(fù)制傳遞給u。

BridgingCom路由算法的有效運(yùn)作依賴于局部社區(qū)識(shí)別算法和節(jié)點(diǎn)重要性度量策略。因此當(dāng)2個(gè)節(jié)點(diǎn)相遇時(shí)，首先交換彼此存儲(chǔ)的局部網(wǎng)絡(luò)信息，包括節(jié)點(diǎn)熟知集合、局部社區(qū)集合，節(jié)點(diǎn)更新自己的局部社區(qū)知識(shí)和節(jié)點(diǎn)中心度。

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

為了評(píng)價(jià) BridgingCom算法的性能，在 The ONE[25]仿真平臺(tái)上比較了本文提出的BridgingCom算法與Direct算法、Epidemic算法、Bubble算法[3]、BiBUBBLE算法[14]以及 QualityEpidemic算法[18]在不同的TTL（time to live）情況下的傳遞性能。

Direct算法使源節(jié)點(diǎn)只與目標(biāo)發(fā)生消息傳遞，因此消息傳遞延遲非常大，不進(jìn)行消息復(fù)制，網(wǎng)絡(luò)負(fù)載最低。Epidemic算法與Direct算法相反，將消息復(fù)制傳遞給所有相遇節(jié)點(diǎn)，能夠獲得較短傳輸延遲，但毫無選擇地盲目復(fù)制使傳輸能耗巨大，嚴(yán)重影響網(wǎng)絡(luò)壽命。Bubble算法、BiBUBBLE算法以及QualityEpidemic算法為近幾年提出的基于節(jié)點(diǎn)社會(huì)關(guān)系進(jìn)行路由決策的代表算法。

5.1 實(shí)驗(yàn)?zāi)繕?biāo)

PSN中消息傳輸失敗的原因可能有：由于 PSN間歇連通，消息傳輸過程中鏈路中斷；消息在應(yīng)用能夠容忍的時(shí)間內(nèi)不能到達(dá)目標(biāo)節(jié)點(diǎn)，被節(jié)點(diǎn)丟棄；節(jié)點(diǎn)為了有效利用有限的緩存或節(jié)約能量而選擇性的丟棄部分消息。PSN路由的目標(biāo)是以較少的資源消耗獲得較高的消息交付比率（可靠性）和較低的交付延遲。主要從以下幾個(gè)方面來評(píng)估相關(guān)算法的性能。

1) 消息傳遞成功率（delivery ratio）：路由算法的終極目標(biāo)就是獲得更高的傳遞成功率。消息交付比率就是在整個(gè)通信過程中目標(biāo)節(jié)點(diǎn)成功接收到數(shù)據(jù)分組數(shù)量與在源節(jié)點(diǎn)所傳遞的所有數(shù)據(jù)分組比值，反映了傳遞成功率。

2) 平均延時(shí)（average delay）：消息延時(shí)是節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時(shí)數(shù)據(jù)塊從源節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)所需的時(shí)間。平均消息延時(shí)體現(xiàn)了網(wǎng)絡(luò)的實(shí)時(shí)性，同時(shí)也間接反應(yīng)了整個(gè)網(wǎng)絡(luò)消息流通是否正常。另外，盡管PSN中應(yīng)用能夠容忍一定的延遲，但傳輸延遲越短，將使得應(yīng)用的時(shí)效性越強(qiáng)，網(wǎng)絡(luò)資源將越早得到釋放，網(wǎng)絡(luò)資源的利用率也將得以提高。

3) 網(wǎng)絡(luò)傳輸冗余比（overhead ratio）：網(wǎng)絡(luò)傳輸冗余比是指在PSN中副本消息與成功傳遞的消息之差除于成功遞交的消息數(shù)目。此參數(shù)反應(yīng)了網(wǎng)絡(luò)的冗余消息量，如果比值高，則說明網(wǎng)絡(luò)性能差，網(wǎng)絡(luò)中充斥著很多沒法交付的消息；若比值低，說明網(wǎng)絡(luò)有較好的傳輸能力，能將較多的消息成功交付。

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

為了驗(yàn)證算法在真實(shí)場(chǎng)景中的性能，本文使用以下2個(gè)數(shù)據(jù)集，并對(duì)數(shù)據(jù)進(jìn)行了處理，刪除連接時(shí)間為0的無效連接信息，防止瞬時(shí)連接影響實(shí)驗(yàn)效果，數(shù)據(jù)集基本信息如表1所示。

數(shù)據(jù)1MIT Reality Mining Project[26]數(shù)據(jù)集（簡(jiǎn)稱Reality數(shù)據(jù)）

Reality Mining項(xiàng)目包括75個(gè)來自MIT Media實(shí)驗(yàn)室學(xué)生，25個(gè)來自MIT Media實(shí)驗(yàn)室附近的MIT Sloan Business School的學(xué)生。該數(shù)據(jù)集中有效節(jié)點(diǎn)數(shù)為97。由于Reality數(shù)據(jù)集時(shí)間跨度比較長，因此這里只選用實(shí)驗(yàn)數(shù)據(jù)中4段比較穩(wěn)定而且沒有額外的假期干擾的連接數(shù)據(jù)，每段數(shù)據(jù)包含一周的連接信息。

數(shù)據(jù)2Haggle Project[27]數(shù)據(jù)集（簡(jiǎn)稱Infocm2006數(shù)據(jù)）

該數(shù)據(jù)集是98個(gè)Infocom2006的與會(huì)人員攜帶iMotes設(shè)備產(chǎn)生的記錄數(shù)據(jù)。由于此組數(shù)據(jù)集合時(shí)間跨度比較短，因此選用整個(gè)數(shù)據(jù)集合進(jìn)行實(shí)驗(yàn)。

表1 Reality和Infocom2006數(shù)據(jù)集基本信息

這2組數(shù)據(jù)的一些基本特征如表1所示。Reality數(shù)據(jù)集和 Infocom2006數(shù)據(jù)集中的連接間隔（granularity）分別為 300 s和 120 s，連接事件（number of internal contacts）分別為54 667次和191 336次，平均每天每2個(gè)節(jié)點(diǎn)之間發(fā)生的連接事件數(shù)目分別為0.024次和6.7次?？梢钥闯?，Reality數(shù)據(jù)集的持續(xù)周期長，用戶活動(dòng)范圍比較廣，連接事件間隔比較長，連接發(fā)生頻率比較低；Infocom2006數(shù)據(jù)集的持續(xù)周期短，用戶活動(dòng)范圍小，記錄周期短，連接發(fā)生頻率高。

圖3為Reality數(shù)據(jù)集和Infocom 2006數(shù)據(jù)集在實(shí)驗(yàn)周期中每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)發(fā)生連接的總次數(shù)、每個(gè)節(jié)點(diǎn)曾遇到過的節(jié)點(diǎn)總數(shù)。從圖3可以看出來節(jié)點(diǎn)活動(dòng)具有社會(huì)規(guī)律：節(jié)點(diǎn)活動(dòng)范圍具有局限性，發(fā)生的大部分連接都是與某一固定節(jié)點(diǎn)集合中節(jié)點(diǎn)之間發(fā)生的；節(jié)點(diǎn)活躍程度不同，某些節(jié)點(diǎn)表現(xiàn)出明顯高于其他節(jié)點(diǎn)的活躍度。選擇合適的中繼節(jié)點(diǎn)，將消息盡快推送出局部社區(qū)，將有助于增加接觸到目標(biāo)節(jié)點(diǎn)的機(jī)會(huì)。

圖3 節(jié)點(diǎn)連接次數(shù)與連接節(jié)點(diǎn)數(shù)統(tǒng)計(jì)

5.3 實(shí)驗(yàn)方法

本實(shí)驗(yàn)采用網(wǎng)絡(luò)仿真工具The ONE[25]，此平臺(tái)是專為評(píng)估 DTN網(wǎng)絡(luò)路由和應(yīng)用協(xié)議設(shè)計(jì)的。本文通過The ONE提供的導(dǎo)入式移動(dòng)模式（external movement）將處理過的2組數(shù)據(jù)導(dǎo)入到仿真平臺(tái)。

為了能更好評(píng)估算法性能，模擬時(shí)節(jié)點(diǎn)緩存大小設(shè)為10 MB，消息大小為5～10 kB。采取以下2種消息生成機(jī)制。

1) 每隔60～120 s隨機(jī)產(chǎn)生一條新消息，消息的源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)隨機(jī)生成。消息產(chǎn)生位置和目標(biāo)節(jié)點(diǎn)均勻分布在整個(gè)網(wǎng)絡(luò)，防止由于消息的局部性對(duì)實(shí)驗(yàn)結(jié)果造成影響。

2) 每隔60～120 s隨機(jī)產(chǎn)生一條新消息，消息的源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間一跳可達(dá)。消息目標(biāo)節(jié)點(diǎn)選擇受到源節(jié)點(diǎn)的限制，目標(biāo)節(jié)點(diǎn)距離源節(jié)點(diǎn)不遠(yuǎn)，減少了“不存在路徑”的消息傳遞對(duì)實(shí)驗(yàn)結(jié)果的影響。

BridgingCom算法能夠準(zhǔn)確運(yùn)行的前提是局部社區(qū)識(shí)別算法能準(zhǔn)確獲知節(jié)點(diǎn)的社區(qū)信息。經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)[30]，連接時(shí)間閾值Fi確定時(shí)，算法2的并入閾值vj和合并閾值Fi～在0.5到0.9之間變化對(duì)獲得的局部社區(qū)劃分結(jié)果影響不大，且在一般情況下推薦閾值設(shè)置為0.6，因此本文采用如表2所示的參數(shù)。

表2 分布式社區(qū)識(shí)別算法基本參數(shù)

5.4 結(jié)果分析

為了模擬真實(shí)場(chǎng)景，使通信網(wǎng)絡(luò)中一直有新的消息加入，本文首先采用消息生成機(jī)制 1)，每隔60～120 s隨機(jī)選擇一個(gè)源節(jié)點(diǎn)產(chǎn)生一條新消息，然后隨機(jī)選擇消息的目標(biāo)節(jié)點(diǎn)。在Reality數(shù)據(jù)集合和Infocom 2006數(shù)據(jù)集合上的不同TTL（time to live）下獲得仿真結(jié)果，并對(duì)各個(gè)路由算法的消息傳遞成功率、網(wǎng)絡(luò)傳輸冗余比和消息傳遞成功的平均延遲時(shí)間進(jìn)行了詳細(xì)的分析和比較。

從圖4可以看出，隨著TTL增大，消息將有更大的機(jī)會(huì)到達(dá)目標(biāo)節(jié)點(diǎn)，因此每種路由的傳遞成功率都隨著TTL的變化而逐漸提高。與其他算法相比，本文提出的BridgingCom算法在TTL比較小時(shí)優(yōu)勢(shì)并不明顯，各個(gè)算法差異不大；但當(dāng)TTL增大，特別是超過12 h后，由于BridgingCom算法有策略的限制消息復(fù)制，其傳遞性能優(yōu)勢(shì)開始體現(xiàn)，表現(xiàn)出優(yōu)于其他算法的傳遞成功率（除Epidemic算法外）。另外，當(dāng)TTL繼續(xù)增大時(shí)，直到TTL等于模擬周期（也就是網(wǎng)絡(luò)中的消息會(huì)一直存在，不會(huì)因?yàn)門TL超時(shí)而被刪除）時(shí)，各個(gè)路由算法的傳遞成功率增長開始變得緩慢，特別是Epidemic算法表現(xiàn)最為明顯。

圖4 消息交付比率

圖 4 (b)中結(jié)果與圖 4 (a)整體趨勢(shì)一致，BridgingCom算法獲得了優(yōu)于其他算法的傳遞成功率。不同的是，在 Infocom2006數(shù)據(jù)集中QualityEpidemic算法獲得了異常高的傳遞成功率，這是因?yàn)镮nfocom2006數(shù)據(jù)集中節(jié)點(diǎn)密度大（節(jié)點(diǎn)活動(dòng)范圍小，連接事件發(fā)生頻繁），基于洪泛的QualityEpidemic算法無法有效選擇中繼節(jié)點(diǎn)，產(chǎn)生大量消息副本，可以從圖5(b)看出，雖然消息傳遞成功率提高，但是網(wǎng)絡(luò)副本數(shù)卻也同時(shí)大大增加，并沒有有效的控制副本數(shù)量。

圖5為各算法的傳輸冗余比結(jié)果?；诤榉旱腅pidemic算法和 QualityEpidemic算法在網(wǎng)絡(luò)中副本數(shù)目最多，遠(yuǎn)遠(yuǎn)大于其他算法。BridgingCom算法在不同TTL下，產(chǎn)生的冗余消息數(shù)目穩(wěn)定，冗余比增長緩慢。原因是BridgingCom算法根據(jù)目標(biāo)節(jié)點(diǎn)的位置，選擇不同的中繼節(jié)點(diǎn)，與Epidemic算法相比，能夠顯著減少網(wǎng)絡(luò)開銷。

圖5 網(wǎng)絡(luò)傳輸冗余比

從圖6可以看到，隨著TTL增大，各個(gè)算法的平均延遲時(shí)間呈現(xiàn)增長趨勢(shì)。當(dāng)TTL較小時(shí)，各個(gè)算法的消息平均延遲時(shí)間差別不大，但是當(dāng)在圖6(a)中TTL增大到24 h、圖6(b)中TTL增大到3 h，各個(gè)算法產(chǎn)生的消息平均延遲時(shí)間差異變大。BridgingCom路由算法在提高消息傳遞成功率的同時(shí)能有效控制消息的平均傳遞延遲時(shí)間，特別是在網(wǎng)絡(luò)負(fù)載比較高時(shí)，BridgingCom路由算法有相對(duì)比較低的延遲時(shí)間，如圖 6(a)中TTL大于48 h之后，圖6(b)中TTL大于6 h之后。這是由于BridgingCom路由算法對(duì)有不同目的地的消息選擇不同路由策略，能有效控制消息的復(fù)制和傳遞方向。

圖6 消息平均延遲時(shí)間

可以從圖6(a)觀察到，Direct算法在TTL為6 h、12 h和24 h時(shí)的平均延時(shí)并沒有明顯大于其他算法。一般認(rèn)為，Direct算法沒有消息復(fù)制，并且只當(dāng)源節(jié)點(diǎn)遇到目標(biāo)節(jié)點(diǎn)時(shí)才傳遞消息，應(yīng)該是獲得傳遞機(jī)會(huì)最少的一種路由算法，而消息傳遞出去機(jī)會(huì)少，傳遞成功的延時(shí)應(yīng)該會(huì)變大。

為了找到出現(xiàn)這個(gè)“異常結(jié)果”的原因，本文采用消息生成機(jī)制 2）控制消息的目標(biāo)節(jié)點(diǎn)范圍，進(jìn)行了一組新的實(shí)驗(yàn)，在產(chǎn)生新消息時(shí)不再隨機(jī)設(shè)定目標(biāo)節(jié)點(diǎn)，而是根據(jù)源節(jié)點(diǎn)不同選擇不同的目標(biāo)節(jié)點(diǎn)，實(shí)驗(yàn)結(jié)果如圖7所示。

從圖7可以發(fā)現(xiàn)，隨著TTL增大，各個(gè)算法的傳遞成功的消息的平均延時(shí)都逐步增大。當(dāng)TTL比較小時(shí)，新產(chǎn)生的消息獲得的傳遞機(jī)會(huì)較小，這時(shí)各個(gè)算法之間的差異體現(xiàn)不大，因此各個(gè)算法的傳遞成功的消息的平均延時(shí)差不多。隨著TTL增大，雖然消息在網(wǎng)絡(luò)中保存時(shí)間增長，但Direct路由算法可供選擇的中繼節(jié)點(diǎn)有限，獲得的傳遞機(jī)會(huì)最少，呈現(xiàn)出較高的消息延時(shí)。因此，出現(xiàn)圖6(a)中的特殊情況的原因是其他算法傳遞成功的消息不僅包含直接傳遞成功的消息還包含大量的、花費(fèi)較長時(shí)間間接傳遞成功的消息，大量需要長時(shí)間傳遞的消息將消息的傳輸延遲平均值提高。

圖7 消息平均延遲時(shí)間

另外，通過圖4可以看出，當(dāng)完全隨機(jī)選擇新產(chǎn)生消息的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)時(shí)（消息生成機(jī)制1）），隨著TTL變化，各個(gè)算法在Reality數(shù)據(jù)集合和Infocom2006數(shù)據(jù)集合上的結(jié)果雖然整體變化趨勢(shì)類似，但也可以看出網(wǎng)絡(luò)連接密度對(duì)網(wǎng)絡(luò)傳輸效率的影響：網(wǎng)絡(luò)密度大，節(jié)點(diǎn)單位時(shí)間接觸到的鄰居多，消息有更多的轉(zhuǎn)發(fā)機(jī)會(huì)，也可能會(huì)產(chǎn)生更多的消息副本，增加網(wǎng)絡(luò)運(yùn)行時(shí)的系統(tǒng)開銷和網(wǎng)絡(luò)資源消耗。

6 結(jié)束語

本文的貢獻(xiàn)是在 PSN中基于節(jié)點(diǎn)移動(dòng)性和連接時(shí)間分析節(jié)點(diǎn)社會(huì)關(guān)系，引入橋接中心度（bridging centrality）作為中繼節(jié)點(diǎn)的選擇依據(jù)，提出了基于社會(huì)屬性的BridgingCom路由算法，并且在真實(shí)數(shù)據(jù)集合上驗(yàn)證本算法的性能。實(shí)驗(yàn)證明BridgingCom路由算法能以較低的網(wǎng)絡(luò)負(fù)載獲得較高的傳遞成功率。

PSN路由算法的研究難點(diǎn)在于如何在連接非持續(xù)、傳輸高延遲及資源受限的情況下，選定合適的數(shù)據(jù)傳輸路徑以完成高效的端到端傳輸，并實(shí)現(xiàn)數(shù)據(jù)傳輸成功率、傳輸能耗以及傳輸延遲之間的有效平衡。PSN作為一種具有社會(huì)規(guī)律性的 DTN，通過挖掘節(jié)點(diǎn)之間的社會(huì)關(guān)系可以更加可靠地預(yù)測(cè)節(jié)點(diǎn)移動(dòng)規(guī)律，提高消息傳遞的效率。在完善現(xiàn)有的方法的同時(shí)，將密切關(guān)注當(dāng)前國內(nèi)外對(duì) PSN路由提出的新理論新方法，深入研究 PSN中節(jié)點(diǎn)社會(huì)特征的理論支撐，考慮如何動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)實(shí)時(shí)變化調(diào)節(jié)社區(qū)識(shí)別的算法的閾值，以及有效的中繼節(jié)點(diǎn)度量等。

[1] HUI P， CHAINTREAU A，et al. Pocket switched networks and human mobility in conference environments[A]. Proc of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking[C]. ACM， 2005.244-251.

[2] DALY E， HAAHR M. Social network analysis for routing in disconnected delay-tolerant manets[A]. Proc of ACM MobiHoc[C]. ACM，2007. 32-40.

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

[4] ZHU Y， XU B， SHI X，et al. A survey of social-based routing in delay tolerant networks： positive and negative social effects[J]. IEEE Communications Surveys & Tutorials， 2012， 15(1)： 387-401.

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

[6] DIOT C，et al. Haggle project[EB/OL]. http：//www.haggleproject.org，2004.

[7] 蘇金樹，胡喬林，趙寶康，彭偉.容延容斷網(wǎng)絡(luò)路由技術(shù)[J]. 軟件學(xué)報(bào)，2010，21(1)：119-132.SU J S， HU Q L， ZHAO B K， PENG W. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software， 2010，21(1)：119-132.

[8] VAHDAT A， BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Technical Report， 2000.

[9] ANDERS L， AVRI D， OLOV S. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2003， 7(3)： 19-20.

[10] MILGRAM S. The small world problem[J]. Psychology Today， 1967，2： 60-67.

[11] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social networks， 1979，1(3)： 215-239.

[12] DALY E M， HAAHR M. Social network analysis for information flow in disconnected delay-tolerant MANETs[J]. IEEE Transactions on Mobile Computing， 2009， 8(5)： 606-621.

[13] SARAFIJANOVIC-DJUKIC M P N， GROSSGLAUSER M. Island hopping： efficient mobility-assisted forwarding in partitioned networks[A].Proc of Sensor and Ad Hoc Communications and Networks[C]. IEEE，2006. 226-235.

[14] HU T， HONG F， ZHANG X Q. BiBUBBLE： social-based forwarding in pocket switched networks[A].Proc of UIC/ATC[C]. IEEE， 2010.195-199.

[15] MTIBAA A， HARRAS K A. Social forwarding in large scale networks：insights based on real trace analysis[A].Proc of Computer Communications and Networks[C]. IEEE， 2011. 1-8.

[16] MEI A， MORABITO G， SANTI P，et al. Social-aware stateless forwarding in pocket switched networks[A].Proc of IEEE INFOCOM[C].IEEE， 2011. 251-255.

[17] GAO W， CAO G. User-centric data dissemination in disruption tolerant networks[A].Proc of IEEE INFOCOM[C]. IEEE， 2011.3119-3127.

[18] ORLINSKI M， FILER N. Quality distributed community formation for data delivery in pocket switched networks[A].Proc of SIMPLEX[C]. ACM， 2012. 31-36.

[19] LI Z， LI Q M， ZHANG H，et al.Closely social circuit based routing in social delay tolerant networks[J].Journal of Computer Research and Development，2012，49(6)：1185-1195.

[20] 程學(xué)旗， 沈華偉. 復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011(8)：57-70.CHENG X Q， SHEN H W. Community structure of complex networks[J].Complex Systems and Complexity Science，2011(8)：57-70.

[21] MARSDEN P V. Egocentric and sociocentric measures of network centrality[J]. Social Networks， 2002(24)： 407-422.

[22] HWANG W， CHO Y， ZHANG A.et al. Bridging centrality： identifying bridging nodes in scale-free networks[A].Proc of ACM SIGKDD[C].ACM， 2006.20-23.

[23] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social networks， 1979， 1(3)： 215-239.

[24] PAN H， EIKO Y， SHU Y C， JON C. Distributed community detection in delay tolerant networks[A].Proc of 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture[C].2007.27-30.

[25] ONE： Opportunistic Network Environment[EB/OL]. http：//www.netlab.tkk.fi/tutkimus/dtn/theone/. 2009.

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

[27] DIOT C，et al. Haggle project[EB/OL]. http：//www.haggleproject.org，2004.