機(jī)會(huì)網(wǎng)絡(luò)中基于有權(quán)社團(tuán)結(jié)構(gòu)圖的路由協(xié)議研究

馬學(xué)彬,白 婧,鄭田玉

(內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院,內(nèi)蒙古呼和浩特010021)

?

機(jī)會(huì)網(wǎng)絡(luò)中基于有權(quán)社團(tuán)結(jié)構(gòu)圖的路由協(xié)議研究

馬學(xué)彬,白 婧,鄭田玉

(內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院,內(nèi)蒙古呼和浩特010021)

基于社團(tuán)檢測(cè)的機(jī)會(huì)網(wǎng)絡(luò)路由算法大多采用無(wú)權(quán)重網(wǎng)絡(luò)拓?fù)鋭澐稚鐖F(tuán),僅將節(jié)點(diǎn)間的關(guān)系抽象為一條簡(jiǎn)單的無(wú)權(quán)重的邊,忽略了節(jié)點(diǎn)關(guān)系的強(qiáng)弱程度.本文通過(guò)引入權(quán)重策略改進(jìn)了QCA社團(tuán)更新算法,提出了一種基于有權(quán)社團(tuán)結(jié)構(gòu)的路由算法,該算法解決了社團(tuán)關(guān)系定量化單一的問(wèn)題,更能真實(shí)反映出社團(tuán)成員之間的關(guān)系.算法中,節(jié)點(diǎn)間的交互信息轉(zhuǎn)化為權(quán)重,根據(jù)不同的網(wǎng)絡(luò)環(huán)境選擇不同的權(quán)重轉(zhuǎn)化方案——?dú)w一化權(quán)重(normalized weight)和非歸一化權(quán)重(non-normalized weight).路由算法在檢測(cè)到周圍網(wǎng)絡(luò)環(huán)境變化時(shí)自動(dòng)切換權(quán)重計(jì)算方案以適應(yīng)網(wǎng)絡(luò)環(huán)境的變化.通過(guò)在仿真環(huán)境和真實(shí)數(shù)據(jù)集上測(cè)試和分析,該算法能夠?qū)⒕W(wǎng)絡(luò)中的節(jié)點(diǎn)劃分出合理的社團(tuán)結(jié)構(gòu),并在保證較高的傳輸成功率的情況下降低網(wǎng)絡(luò)開(kāi)銷.

機(jī)會(huì)網(wǎng)絡(luò);社團(tuán)劃分;路由算法;有權(quán)拓?fù)?/p>

1 引言

在機(jī)會(huì)網(wǎng)絡(luò)[1]中,人們隨身攜帶的智能移動(dòng)設(shè)備構(gòu)成了網(wǎng)絡(luò)中的節(jié)點(diǎn),并且隨著人的移動(dòng)而移動(dòng).由于人作為社會(huì)群體中的一員體現(xiàn)出社會(huì)性特征,所以這些移動(dòng)設(shè)備也具有一定的社會(huì)性特征.社團(tuán)劃分就是基于網(wǎng)絡(luò)中節(jié)點(diǎn)間的相互關(guān)系將它們劃分到各個(gè)社團(tuán),并且同一社團(tuán)內(nèi)成員間的交互概率會(huì)明顯高于社團(tuán)間成員的交互概率[2～4].利用節(jié)點(diǎn)間的這個(gè)特點(diǎn)可以為選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)提供極為重要的參考依據(jù),因此劃分網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)用于數(shù)據(jù)轉(zhuǎn)發(fā),對(duì)提高機(jī)會(huì)網(wǎng)絡(luò)中的路由性能具有重大意義.

本文提出了一種基于社團(tuán)劃分方法的路由算法.在機(jī)會(huì)網(wǎng)絡(luò)中,大部分基于社團(tuán)劃分的路由算法只是將網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的連接簡(jiǎn)單映射為網(wǎng)絡(luò)拓?fù)渲幸粭l無(wú)權(quán)重的邊,忽視了節(jié)點(diǎn)間的連接所反映的節(jié)點(diǎn)間關(guān)系強(qiáng)弱的信息.根據(jù)節(jié)點(diǎn)間的連接信息可以分析出它們間的關(guān)系強(qiáng)度以及節(jié)點(diǎn)移動(dòng)模式的共同特征[5],利用這些信息可以劃分出高質(zhì)量的社團(tuán)結(jié)構(gòu)并因此提高路由性能[6].

2 相關(guān)工作

機(jī)會(huì)網(wǎng)絡(luò)中,有關(guān)社團(tuán)劃分的路由算法多是從復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法演變而來(lái)的,比較經(jīng)典的算法包括K派系過(guò)濾算法[7～9]、GN算法[10]等等.在文獻(xiàn)[7]中,作者使用K-clique算法通過(guò)添加一些社會(huì)信息來(lái)檢測(cè)社會(huì)網(wǎng)絡(luò),并形成一個(gè)具有自報(bào)告功能的社會(huì)網(wǎng)絡(luò).研究發(fā)現(xiàn)通過(guò)使用自報(bào)告的社會(huì)網(wǎng)絡(luò)信息雖然不能明顯的提升消息傳輸成功率,但是能有效地降低開(kāi)銷.在文獻(xiàn)[8]中,作者改進(jìn)了文獻(xiàn)[7]中的想法,在兩個(gè)不同的場(chǎng)景下使用K-clique算法,分別是室內(nèi)場(chǎng)景和室外場(chǎng)景.作者發(fā)現(xiàn)能夠影響機(jī)會(huì)網(wǎng)絡(luò)解決方案和算法的關(guān)鍵是社會(huì)信息和移動(dòng)行為信息,網(wǎng)絡(luò)性能能夠通過(guò)增加社會(huì)網(wǎng)絡(luò)參與者的社會(huì)聯(lián)系來(lái)增加.同時(shí),通過(guò)組合這兩種信息,可以提高傳輸成功率,并且?guī)缀鯖](méi)有影響交付延遲.在文獻(xiàn)[9]中,Fu提出了一個(gè)基于聯(lián)合發(fā)現(xiàn)結(jié)構(gòu)的改進(jìn)的k-clique發(fā)現(xiàn)算法,它縮短了社團(tuán)發(fā)現(xiàn)的時(shí)間,其劃分社團(tuán)的時(shí)間復(fù)雜度接近線性.Newman于2004年提出的模塊度(Modularity)[10,11]更是成為衡量社團(tuán)結(jié)構(gòu)劃分質(zhì)量的一個(gè)重要的指標(biāo).由于Newman提出的快速算法時(shí)間復(fù)雜度較高,改進(jìn)的算法引入了模擬退火算法、禁忌搜索算法、退火算法等來(lái)加快計(jì)算速度.

目前,對(duì)于社團(tuán)劃分算法方面的研究,如何快速高效、高精度地劃分社團(tuán)仍是研究熱點(diǎn)之一.此外,研究者從多個(gè)角度去分析社團(tuán)結(jié)構(gòu),進(jìn)而提高劃分精度.模塊度、節(jié)點(diǎn)的社會(huì)屬性,節(jié)點(diǎn)的私人屬性等方面已經(jīng)成為研究社團(tuán)結(jié)構(gòu)需要考慮的因素.Nam等人[12]提出了一種在動(dòng)態(tài)社交網(wǎng)絡(luò)中自適應(yīng)更新社團(tuán)結(jié)構(gòu)的算法Quick Community Adaptation(QCA).通過(guò)推導(dǎo)簡(jiǎn)化了模塊度計(jì)算的復(fù)雜度,形成了一個(gè)新的社團(tuán)更新算法.QCA根據(jù)網(wǎng)絡(luò)變化實(shí)時(shí)更新節(jié)點(diǎn)的所屬社團(tuán),最終得到高質(zhì)量的社團(tuán)劃分結(jié)果.該算法在運(yùn)行時(shí)間上有顯著的提高,適合劃分大型的、快速變化的網(wǎng)絡(luò)上的社團(tuán)結(jié)構(gòu),如在線社交網(wǎng)絡(luò)、人際關(guān)系網(wǎng)等.Costa等人[13]提出了一種在機(jī)會(huì)網(wǎng)絡(luò)中使用發(fā)布/訂閱機(jī)制的路由算法——SocialCast 路由算法.在該路由算法中,作者建立了社會(huì)網(wǎng)絡(luò)模型和移動(dòng)模型,將社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)性和移動(dòng)性以量化的方式轉(zhuǎn)化為協(xié)同定位和連接度的改變.該路由算法只將消息發(fā)布給訂閱它的節(jié)點(diǎn),而具有相同興趣的節(jié)點(diǎn)會(huì)聚集在一起,這能夠有效地控制網(wǎng)絡(luò)中的副本數(shù)量,并通過(guò)社交矩陣預(yù)測(cè)并選擇最佳的消息載體.該路由算法一共分為興趣分發(fā)、中繼選擇、消息發(fā)布三個(gè)階段.該算法適合具有小世界特性的網(wǎng)絡(luò)和很難獲取全局信息的網(wǎng)絡(luò).Pan Hui等[14]提出一種基于社會(huì)屬性的路由算法Bubble Rap.該路由算法根據(jù)目的地社團(tuán)和節(jié)點(diǎn)中心度的排名來(lái)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn).在該算法中,每個(gè)節(jié)點(diǎn)至少屬于一個(gè)社區(qū),每個(gè)節(jié)點(diǎn)有兩個(gè)中心性,一個(gè)是本地中心性,一個(gè)是全局中心性.整個(gè)路由過(guò)程分為兩個(gè)階段,全局轉(zhuǎn)發(fā)和局部轉(zhuǎn)發(fā).在全局轉(zhuǎn)發(fā)階段,該算法盡最大努力使消息到達(dá)目的社團(tuán);在局部轉(zhuǎn)發(fā)階段,該算法將把消息轉(zhuǎn)發(fā)到目的節(jié)點(diǎn).通過(guò)這兩個(gè)階段的相互配合使消息快速高效地到達(dá)目的節(jié)點(diǎn).但是該算法在所有節(jié)點(diǎn)的全局中心性都很低時(shí)可能失效.Bulut 等[15]提出了基于朋友關(guān)系的路由,在相遇次數(shù)、相遇持續(xù)時(shí)間、相遇規(guī)律這三個(gè)維度定義朋友的特性,并且基于朋友關(guān)系的質(zhì)量來(lái)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn),通過(guò)將消息交付給高質(zhì)量的朋友來(lái)增加消息的傳輸成功率.Mei等提出了一種社會(huì)性敏感的無(wú)狀態(tài)路由方法SANE (Social-Aware and Stateless Routing)[16].在這種路由算法中一個(gè)人的興趣由k維的興趣向量表示,兩個(gè)用戶u和v之間的興趣相似性用向量間的Cosine相似性來(lái)表示.在路由過(guò)程中,消息被轉(zhuǎn)發(fā)給與目的地興趣最相似的節(jié)點(diǎn).該算法維護(hù)和更新社會(huì)度量相對(duì)簡(jiǎn)單,占用空間小,時(shí)間復(fù)雜度和空間復(fù)雜度都很低.在文獻(xiàn)[17]中,Xuebin M提出了一個(gè)基于節(jié)點(diǎn)間耦合程度的路由算法CR,每個(gè)節(jié)點(diǎn)根據(jù)它與周圍相遇節(jié)點(diǎn)的相似性確定它們屬于哪個(gè)社團(tuán),并根據(jù)消息的目的節(jié)點(diǎn)選擇與其最屬性接近的社團(tuán)進(jìn)行轉(zhuǎn)發(fā),最終將消息發(fā)送到目的社團(tuán)并進(jìn)一步轉(zhuǎn)發(fā)到目的節(jié)點(diǎn).該算法通過(guò)記錄的接觸歷史信息計(jì)算關(guān)系強(qiáng)度及其節(jié)點(diǎn)間的耦合程度,使得該算法的計(jì)算復(fù)雜度和時(shí)間復(fù)雜度都較低.實(shí)驗(yàn)結(jié)果表明,該算法減少了轉(zhuǎn)發(fā)的次數(shù),提高了傳輸成功率.在文獻(xiàn)[18]中,Theus Hossmann研究了四個(gè)數(shù)據(jù)集和三個(gè)先進(jìn)的合成數(shù)據(jù)的社團(tuán)結(jié)構(gòu)、圖譜、社團(tuán)內(nèi)部以及社團(tuán)間的權(quán)重分布.在此基礎(chǔ)上作者提出來(lái)一個(gè)框架用于分析基于SNA的DTN路由方案的性能.在文獻(xiàn)[19]中提出了一個(gè)新的路由算法NBR,該算法使用一個(gè)加入節(jié)點(diǎn)回歸因素的模型.在社區(qū)內(nèi)采用混合路由算法,并加入了正反饋思想計(jì)算節(jié)點(diǎn)活躍度來(lái)尋找目的節(jié)點(diǎn);在社區(qū)間采用查詢路由表和判斷節(jié)點(diǎn)回歸相結(jié)合的方法進(jìn)行消息轉(zhuǎn)發(fā).該算法與其他算法相比,不僅提高了傳輸成功率,也降低了開(kāi)銷.

上面所述路由算法雖然從不同角度解決了社團(tuán)劃分和機(jī)會(huì)網(wǎng)絡(luò)中基于社團(tuán)結(jié)構(gòu)的路由算法問(wèn)題,但是他們大多只考慮了影響社團(tuán)結(jié)構(gòu)的一個(gè)或幾個(gè)因素,并沒(méi)有綜合考慮各種因素.本文通過(guò)給出一個(gè)通用的社團(tuán)劃分框架,可以把各種因素轉(zhuǎn)換為邊之間的權(quán)重,通過(guò)劃分社團(tuán)結(jié)構(gòu)來(lái)提高機(jī)會(huì)網(wǎng)絡(luò)的路由性能.該路由算法還考慮到不同拓?fù)浣Y(jié)構(gòu)的特點(diǎn),自主選擇不同的權(quán)重計(jì)算方法,使得劃分的社團(tuán)更準(zhǔn)確、更高效.

3 基于權(quán)重的社團(tuán)更新算法

本文基于Nam P Nguyen[12]等人的工作,對(duì)其提出的QCA算法進(jìn)行改進(jìn),將其應(yīng)用于機(jī)會(huì)網(wǎng)絡(luò)并引入權(quán)重概念以提升算法性能.對(duì)于單個(gè)節(jié)點(diǎn)來(lái)說(shuō),在無(wú)權(quán)重網(wǎng)絡(luò)拓?fù)渲?它涉及的網(wǎng)絡(luò)拓?fù)涞淖儎?dòng)有兩種,分別是邊的添加和刪除.而對(duì)于有權(quán)網(wǎng)絡(luò)拓?fù)?邊的添加和刪除相對(duì)應(yīng)的轉(zhuǎn)變?yōu)檫厵?quán)重的增加和減少,因此QCA社團(tuán)更新算法[12]中的計(jì)算公式不再適合本文中的情況,需要重新推導(dǎo).接下來(lái)會(huì)用到的一些概念和符號(hào)如下.

假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)渲兴械倪厵?quán)重都是大于0的,且整個(gè)網(wǎng)絡(luò)中均勻分布多個(gè)社團(tuán)(四個(gè)以上),即wij≥0,M>0,dC>0,M大于任意dC,兩個(gè)節(jié)點(diǎn)間的邊的權(quán)重由w1變?yōu)閣2,變化量為|Δw|.經(jīng)過(guò)推導(dǎo),可以得到以下幾條結(jié)論:

(1)社團(tuán)內(nèi)的邊權(quán)重的增加能使該社團(tuán)對(duì)全局模塊度的貢獻(xiàn)增加.

證明

若權(quán)重變化后模塊度增加,則需滿足條件Q′-Q>0

因Δw>0,可知若要Q′-Q>0,需要(2M2-2MdC-dCΔw)(2M-dC)>0,

因?yàn)?M為整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的和,所以一個(gè)社團(tuán)內(nèi)的節(jié)點(diǎn)的度的和不可能大于2M,因此dC>2M不成立,不存在上面這一種情況.

由上面的推導(dǎo)①可以看出,只要網(wǎng)絡(luò)中均勻分布兩個(gè)以上的社團(tuán),且權(quán)重的增加不是特別大的話,社團(tuán)內(nèi)部的邊權(quán)重的增加必然能夠使該社團(tuán)的模塊度增大.由此可知,一般情況下,社團(tuán)內(nèi)的邊權(quán)重的增加能使該社團(tuán)模塊度的增加.

通過(guò)上面的推導(dǎo)可知,一般情況下社團(tuán)內(nèi)的邊權(quán)重的減少能夠使該社團(tuán)對(duì)全局模塊度的貢獻(xiàn)減少.

(2)兩個(gè)社團(tuán)間的邊權(quán)重減少時(shí)能夠提高兩個(gè)社團(tuán)對(duì)全局模塊度的貢獻(xiàn).

證明 由結(jié)論(1)可反向推導(dǎo)得出.

證明 假設(shè)社團(tuán)C內(nèi)部邊權(quán)重的減少會(huì)導(dǎo)致該社團(tuán)分裂為C1和C2,那么權(quán)重變化前模塊度應(yīng)該符合下面公式

Q1+Q2

權(quán)重減少后模塊度應(yīng)該符合下面公式

(4)當(dāng)社團(tuán)內(nèi)的一條邊權(quán)重減少,并且這條邊的兩端節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)只有一條邊與其相連,則這條邊的變化不會(huì)分裂兩個(gè)社團(tuán).

證明

若社團(tuán)內(nèi)的一條邊(u,v)的權(quán)重減少|(zhì)Δw|,且這條邊兩端的兩個(gè)節(jié)點(diǎn)u和v中至少有一個(gè)的度為1,若這條邊的權(quán)重變化會(huì)導(dǎo)致本地社團(tuán)C的分裂,則應(yīng)該滿足以下兩個(gè)條件權(quán)重變化前的模塊度

Q1+Q2

權(quán)重變化后的模塊度

即

因?yàn)?/p>

由上面推導(dǎo)可知,當(dāng)社團(tuán)內(nèi)一條權(quán)重減少的邊的兩端的節(jié)點(diǎn)只要其中一個(gè)的度為1,則這條邊的變化不會(huì)分裂兩個(gè)社團(tuán).

證明

(6)當(dāng)社團(tuán)間的一條邊權(quán)重增加時(shí),若這條邊所連接的一端的節(jié)點(diǎn)符合公式

則該節(jié)點(diǎn)應(yīng)該加入到另一端的社團(tuán).若兩端的節(jié)點(diǎn)都符合該公式,則選擇值較大的一段加入.

證明

當(dāng)兩個(gè)社團(tuán)間一條邊的權(quán)重增長(zhǎng)時(shí),節(jié)點(diǎn)若留在原來(lái)的社團(tuán)C中時(shí),模塊度為

QC+QD

若節(jié)點(diǎn)u離開(kāi)社團(tuán)C,加入社團(tuán)D,模塊度變?yōu)?/p>

QC-u+QD+u

若要證明節(jié)點(diǎn)u加入社團(tuán)D后模塊度會(huì)增加,只需證明

QC-u+QD+u>QC+QD

即

本文所提出的基于權(quán)重的社團(tuán)更新算法如算法1所示.其中,increaseWeight(u,v,Δw)算法如算法2所示,算法中使用的decreaseWeight(u,v,Δw)、newNode(u)、removeNode(u)三種方法的內(nèi)部實(shí)現(xiàn)方式與QCA算法中類似,主要區(qū)別在于使用的推導(dǎo)公式不同,因此這里不做贅述.

算法1 WQCA

Output:Community which nodeubelongs to.

Begin

ForΔGdo

Ifξi=changeWeight (v) then

IfΔw>0 then

increaseWeight(u,v,Δw)

Else IfΔw<0 then

decreaseWeight(u,v,Δw)

End If

Else Ifξi=newNode(v)then

newNode(v)

Else Ifξi=removeNode(v) then

removeNode(v)

End If

End For

End

算法2 increaseWeight(u,v,Δw)

Begin

IfC(u)≠C(v) then

Δq=max{Δqu,C(u),C(v),Δqv,C(u),C(v)}

w=arg max{Δqu,C(u),C(v),Δqv,C(u),C(v)}

IfΔq>0 then

wjoin into another community

End If

End If

End

4 基于權(quán)重的社團(tuán)劃分路由協(xié)議

基于權(quán)重的社團(tuán)劃分路由協(xié)議分為信息采集、權(quán)重轉(zhuǎn)化和路由轉(zhuǎn)發(fā)三部分.其中信息采集和權(quán)重轉(zhuǎn)化為社團(tuán)劃分的前期工作,它們將機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)接觸信息轉(zhuǎn)化為邊權(quán)重,并形成有權(quán)網(wǎng)絡(luò)拓?fù)鋱D.社團(tuán)劃分算法就是在這兩部分工作的基礎(chǔ)上運(yùn)行的.消息的路由轉(zhuǎn)發(fā)則是根據(jù)社團(tuán)劃分算法得到的結(jié)果和權(quán)重等信息判斷轉(zhuǎn)發(fā)節(jié)點(diǎn).社團(tuán)劃分算法流程圖如圖1所示.

4.1 信息采集

節(jié)點(diǎn)采集信息的質(zhì)量十分重要,會(huì)直接影響到之后的社團(tuán)劃分和路由性能.為了保留節(jié)點(diǎn)間的強(qiáng)連接以及剔除一些無(wú)意義的弱連接(例如兩個(gè)節(jié)點(diǎn)間只存在一次連接時(shí)間極短的連接等情況),需要采用合適大小的時(shí)間窗口和合適的策略對(duì)連接進(jìn)行篩選.如果選擇不恰當(dāng),會(huì)造成網(wǎng)絡(luò)拓?fù)湓絹?lái)越稠密,經(jīng)過(guò)一段時(shí)間后網(wǎng)絡(luò)拓?fù)洳辉倌苊鞔_的反映出節(jié)點(diǎn)間的關(guān)系,甚至網(wǎng)絡(luò)拓?fù)溆锌赡茏優(yōu)檫B通圖.本路由協(xié)議提出兩種方式,在規(guī)定的時(shí)間窗口內(nèi)以最新的最近連接(Most Recent Connection,MRC)和最新的最頻繁連接(Most Frequent Connection,MFC)兩種方式篩選部分連接[20].最新的最近連接(MRC)是根據(jù)表中記錄的節(jié)點(diǎn)最近連接時(shí)間選擇距離當(dāng)前時(shí)間最遠(yuǎn)的一部分記錄刪除.最新最頻繁連接(MFC)則是選擇當(dāng)前時(shí)間片內(nèi)連接次數(shù)最少的一部分記錄刪除.

在本路由協(xié)議中,網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都要維護(hù)一個(gè)記錄自身與其他節(jié)點(diǎn)的連接信息的網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷?每個(gè)節(jié)點(diǎn)以其全局唯一的ID的形式存放在網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷碇?網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷碇械拿恳豁?xiàng)都記錄著另一節(jié)點(diǎn)與本節(jié)點(diǎn)間的連接次數(shù)、連接時(shí)長(zhǎng)、兩節(jié)點(diǎn)間的權(quán)重等信息,在社團(tuán)劃分時(shí)根據(jù)表中記錄的連接信息計(jì)算兩個(gè)節(jié)點(diǎn)之間的邊的權(quán)重并記錄在表中相應(yīng)的字段.本文所用到的社團(tuán)更新算法是根據(jù)網(wǎng)絡(luò)拓?fù)涞淖儎?dòng)更新社團(tuán),但是考慮到若是每一次網(wǎng)絡(luò)拓?fù)渥儎?dòng)都更新社團(tuán)結(jié)構(gòu)會(huì)造成大量的計(jì)算以及節(jié)點(diǎn)間的社團(tuán)記錄無(wú)法同步等問(wèn)題,因此本文采用時(shí)間片的形式更新社團(tuán)結(jié)構(gòu),每當(dāng)時(shí)間片結(jié)束時(shí)調(diào)用社團(tuán)更新算法更新網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).在網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷泶嬖谝粋€(gè)名為標(biāo)志位的字段,該字段用來(lái)記錄網(wǎng)絡(luò)拓?fù)湓跁r(shí)間片內(nèi)的變動(dòng)情況,具體來(lái)說(shuō)標(biāo)志位包含四個(gè)值new、delete、change、old.下面為標(biāo)志位變動(dòng)的幾種情況:

算法3 信息采集算法

Begin

Beforeatimeslicerunning

For The Connection Information List do

IfconItem.flag=“delete” then

removeconItemfrom the list

Else IfconItem.flag=“new”or“change” then

conItem.flag=“old”

End If

End For

Timesilceruning

Forcondo

Ifcondoesn′t exist in the connection information list then

addconinto the list andconItem.flag=“new”

Else

conItem.flag=“change”

End If

End For

Timeslicerunsout

choose removeconItemin the connection information byMRCorMFC

removeItem.flag=“delete”

End

在網(wǎng)絡(luò)拓?fù)溆涗洷碇械墓?jié)點(diǎn)表示當(dāng)前節(jié)點(diǎn)與表中記錄的其它節(jié)點(diǎn)間存在邊,這條邊的權(quán)重根據(jù)所采集的連接信息計(jì)算.另外,每個(gè)節(jié)點(diǎn)保存著一個(gè)黑名單列表(BlackList),用來(lái)記錄拒絕接收轉(zhuǎn)發(fā)消息的節(jié)點(diǎn).信息采集階段的具體算法如算法3所示.

4.2 權(quán)重轉(zhuǎn)化

在不同的網(wǎng)絡(luò)環(huán)境下,權(quán)重計(jì)算公式應(yīng)該相應(yīng)的改變以維持社團(tuán)更新算法的最優(yōu)性能.對(duì)于節(jié)點(diǎn)密度比較高接觸時(shí)間長(zhǎng)而且頻繁的網(wǎng)絡(luò)環(huán)境,節(jié)點(diǎn)間的邊的權(quán)重值會(huì)比較高.而非歸一化權(quán)重在這種環(huán)境下能夠保持較高的分辨率,劃分出合理的社團(tuán)結(jié)構(gòu),不會(huì)將這些高權(quán)重的節(jié)點(diǎn)都劃分到一個(gè)社團(tuán).而在一般的情況下,歸一化權(quán)重能夠能更敏感的察覺(jué)網(wǎng)絡(luò)拓?fù)涞淖兓?得到合理的社團(tuán)劃分結(jié)果.

根據(jù)上面的公式計(jì)算節(jié)點(diǎn)間的邊權(quán)重,將前面采集到的有關(guān)連接信息的數(shù)據(jù)充分提取利用,以進(jìn)一步體現(xiàn)節(jié)點(diǎn)間關(guān)系的緊密程度,并在此基礎(chǔ)上劃分出更加合理的社團(tuán)結(jié)構(gòu).

4.3 路由轉(zhuǎn)發(fā)

在消息轉(zhuǎn)發(fā)階段,節(jié)點(diǎn)在與其他節(jié)點(diǎn)相遇時(shí),首先檢查消息目的地是否存在于相遇的網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷碇?因?yàn)榫W(wǎng)絡(luò)拓?fù)湫畔⒂涗洷淼暮Y選策略,留在表中的大部分是與當(dāng)前節(jié)點(diǎn)經(jīng)常相遇或頻繁相遇的節(jié)點(diǎn),所以先檢查表中記錄的節(jié)點(diǎn)有助于更快找到合適的轉(zhuǎn)發(fā)節(jié)點(diǎn).若消息目的地存在于相遇節(jié)點(diǎn)的表中,則選擇權(quán)重大的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息.

當(dāng)目的地節(jié)點(diǎn)不存在于任何一個(gè)相遇節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷碇袝r(shí),路由轉(zhuǎn)發(fā)根據(jù)社團(tuán)內(nèi)/外轉(zhuǎn)發(fā)以及路由調(diào)度策略轉(zhuǎn)發(fā)消息.為了便于選擇轉(zhuǎn)發(fā)節(jié)點(diǎn),節(jié)點(diǎn)先統(tǒng)計(jì)自身與各個(gè)社團(tuán)間的總權(quán)重并建立一張社團(tuán)權(quán)重查詢表,如圖2所示.節(jié)點(diǎn)與各個(gè)社團(tuán)間的總權(quán)重為網(wǎng)絡(luò)拓?fù)湫畔⒂涗洷碇袑儆谕簧鐖F(tuán)的節(jié)點(diǎn)成員與當(dāng)前節(jié)點(diǎn)間的邊權(quán)重的總和.根據(jù)消息目的地的所屬社團(tuán)判斷該消息目前是處于社團(tuán)內(nèi)部轉(zhuǎn)發(fā)還是社團(tuán)外部轉(zhuǎn)發(fā),采用相應(yīng)的轉(zhuǎn)發(fā)策略.下面分別詳細(xì)介紹這兩部分以及相應(yīng)的路由調(diào)度策略.社團(tuán)查詢的時(shí)間復(fù)雜度是O(m+n),其中m是拓?fù)湫畔?shù)目,n是社團(tuán)表大小.

算法4 WQCA 路由算法

Begin

Forcondo

Formsgdo

Ifmsg.destinationexists in The Connection Information List then

addmsgtoForwardList

Else Ifmsgexists in destination community then

Ifcon.CommWeight>CurCommWeightthen

addmsgtoForwardList

End If

Else

Ifcon.Community=msg.DesCommthen

addmsgtoForwardList

Else Ifcon.CommNum>curCommNumthen

addmsgtoForwardList

End If

End If

End For

sort(ForwardList)

forwardMessage(ForwardList)

End For

End

若消息已經(jīng)處于目的地社團(tuán),則采取社團(tuán)內(nèi)轉(zhuǎn)發(fā)的方式轉(zhuǎn)發(fā)消息.消息處于社團(tuán)內(nèi)轉(zhuǎn)發(fā)時(shí),消息不再轉(zhuǎn)發(fā)向非目的地社團(tuán)成員的節(jié)點(diǎn),只在目的地社團(tuán)內(nèi)部傳播.比較相遇節(jié)點(diǎn)與目的地社團(tuán)的權(quán)重,選擇權(quán)重較大的節(jié)點(diǎn)轉(zhuǎn)發(fā).處于社團(tuán)中心的節(jié)點(diǎn)同其他社團(tuán)成員的接觸比較頻繁,相應(yīng)的它與其所屬社團(tuán)的權(quán)重也會(huì)更大一些.消息逐漸向與目的地社團(tuán)權(quán)重大的節(jié)點(diǎn)轉(zhuǎn)移,意味著它將逐漸接近社團(tuán)中心,進(jìn)而遇見(jiàn)更多的目的地社團(tuán)成員,有更大的概率遇到目的地節(jié)點(diǎn).

若消息未傳遞到目的地社團(tuán),則采取社團(tuán)外轉(zhuǎn)發(fā)的方式.根據(jù)社團(tuán)權(quán)重查詢表,找到節(jié)點(diǎn)與目的地社團(tuán)的總權(quán)重,選擇與目的地社團(tuán)權(quán)重最大的節(jié)點(diǎn)轉(zhuǎn)發(fā).若沒(méi)有與目的地社團(tuán)連接的相遇節(jié)點(diǎn),則選擇連接鄰接社團(tuán)數(shù)量最多的節(jié)點(diǎn)轉(zhuǎn)發(fā).只有離開(kāi)當(dāng)前這個(gè)非目的地社團(tuán)才能夠有更多的機(jī)會(huì)遇見(jiàn)目的地社團(tuán),因此期望還未傳遞到目的地社團(tuán)的消息能夠向社團(tuán)邊緣傳遞.邊緣節(jié)點(diǎn)能夠有更多的機(jī)會(huì)接觸其他社團(tuán)的成員將消息擴(kuò)散出去.

路由轉(zhuǎn)發(fā)階段的具體算法實(shí)現(xiàn)如算法4所示.路由轉(zhuǎn)發(fā)的時(shí)間復(fù)雜度是O(m*n),m是連接節(jié)點(diǎn)數(shù)目,n是消息數(shù)目.

5 仿真實(shí)驗(yàn)

5.1 社團(tuán)結(jié)構(gòu)

在ONE[20]平臺(tái)上使用Pittsburgh Working Day Model[21]分別運(yùn)行基于模塊度的社團(tuán)劃分算法、QCA以及WQCA算法三種算法.通過(guò)三者的社團(tuán)劃分結(jié)果比較算法的性能.仿真時(shí)長(zhǎng)為2周,每天進(jìn)行一次社團(tuán)劃分,并統(tǒng)計(jì)當(dāng)前網(wǎng)絡(luò)中的社團(tuán)總數(shù)和全局模塊度.

圖3、圖4分別為基于最新最頻繁連接和最新的最近連接信息采集兩種方式在每次進(jìn)行社團(tuán)劃分時(shí)劃分出的社團(tuán)數(shù)量.從中可以看出,基于模塊度的社團(tuán)劃分算法趨向于將整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到少數(shù)幾個(gè)社團(tuán)內(nèi),整個(gè)網(wǎng)絡(luò)中的社團(tuán)數(shù)量是隨著仿真時(shí)間的增長(zhǎng)變得越來(lái)越少.在仿真中,整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)模式?jīng)]有太過(guò)劇烈的改變.隨著仿真時(shí)間的增長(zhǎng),可以看出WQCA算法劃分出的社團(tuán)結(jié)構(gòu)比QCA算法更快的趨于穩(wěn)定,而且WQCA算法劃分出的社團(tuán)結(jié)構(gòu)相較另兩種算法相比波動(dòng)相對(duì)較小.

并且,從圖3和圖4中可以看出MFC方式劃分出的社團(tuán)結(jié)構(gòu)要比MRC方式劃分出的社團(tuán)結(jié)構(gòu)更穩(wěn)定一些.雖然對(duì)于QCA和WQCA這兩種根據(jù)網(wǎng)絡(luò)拓?fù)渥兓律鐖F(tuán)的算法來(lái)說(shuō),連接產(chǎn)生的時(shí)間離社團(tuán)更新的時(shí)間越近,它對(duì)節(jié)點(diǎn)所屬社團(tuán)產(chǎn)生的影響就越大,并且整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)軌跡變動(dòng)的越劇烈越隨機(jī),這種影響越明顯,但是在本仿真環(huán)境中,節(jié)點(diǎn)的移動(dòng)軌跡具有一定的規(guī)律性,節(jié)點(diǎn)間的接觸也比較頻繁,因此使用MFC的信息采集方式不僅不會(huì)剔除掉很多重要的接觸信息,反而會(huì)過(guò)濾掉大部分干擾社團(tuán)劃分的無(wú)意義接觸信息,所以在本仿真環(huán)境中使用MFC信息采集方式更加合理.

5.2 路由性能

為了得到WQCA算法在真實(shí)環(huán)境下的性能表現(xiàn),在Inforcom06數(shù)據(jù)集上對(duì)Direct Transmission (DT)[22]、Epidemic[23]、SW[24]和WQCA這四種路由算法進(jìn)行了比較.機(jī)會(huì)網(wǎng)絡(luò)路由算法中,最基本的是DT、Epidemic,SW這三種路由算法.Epidemic是理想中成功率最高的路由算法,這也是冗余度最高的路由算法.DT路由算法冗余最低,成功率也是最低的.SW也是一個(gè)經(jīng)典的算法,它是DT、Epidemic算法的折中,冗余和成功率也在這兩者之間.如果拿這些算法比,不具有代表意義.由于Inforcom06數(shù)據(jù)集中的節(jié)點(diǎn)數(shù)量相對(duì)較少,節(jié)點(diǎn)間接觸比較稀疏,而且真實(shí)環(huán)境中人的移動(dòng)軌跡變化更具有隨機(jī)性,所以這里WQCA算法采用MRC方式收集接觸信息,以避免將對(duì)社團(tuán)劃分影響比較大的接觸信息篩選掉.

圖5、6和7分別為DT、Epidemic、SW和WQCA這四種路由算法隨TTL時(shí)間變化的消息傳輸成功率、平均時(shí)延和網(wǎng)絡(luò)開(kāi)銷率變化曲線.可以看出,隨著TTL的增加這四種路由算法的傳輸成功率和平均時(shí)延都保持著持續(xù)增長(zhǎng).這是因?yàn)樵疽恍┰赥TL內(nèi)傳遞不到目的地的消息副本,由于TTL延長(zhǎng)而找到了目的地節(jié)點(diǎn)傳輸成功.WQCA路由的傳輸成功率和平均時(shí)延僅次于Epidemic路由.WQCA的傳輸成功率只比Epidemic路由低了7%至8%,平均時(shí)延比Epidemic高了100s左右,而網(wǎng)絡(luò)開(kāi)銷則比Epidemic低了將近35%.再看WQCA與DT的比較,雖然在網(wǎng)絡(luò)開(kāi)銷方面WQCA比DT高很多,這是因?yàn)樵贒T當(dāng)中始終只保持一個(gè)副本,而在傳輸成功率方面WQCA比DT高12%至25%,在平均延時(shí)方面,WQCA比DT低180s至390s.可以看出WQCA在網(wǎng)絡(luò)開(kāi)銷增加不多的情況下在傳輸成功率和的優(yōu)勢(shì)很明顯.最后比較WQCA和SW算法.由于SW算法是Epidemic和DT算法的折中,所以SW在傳輸成功率方面要優(yōu)于DT算法,而在網(wǎng)絡(luò)開(kāi)銷方面要優(yōu)于Epidemic算法.在傳輸成功率方面WQCA比SW算法高7%至10%,在平均延時(shí)方面,WQCA比SW少30s至450s,在網(wǎng)絡(luò)開(kāi)銷方面WQCA要比SW高,這是因?yàn)?SW的網(wǎng)絡(luò)副本數(shù)量是固定的,而WQCA是可變,但是從整個(gè)機(jī)會(huì)網(wǎng)絡(luò)的環(huán)境來(lái)看,增加的網(wǎng)絡(luò)副本數(shù)是可接受的.

為了比較WQCA算法與其他采用社團(tuán)劃分的路由算法,本文選取了經(jīng)典的Bubble-rap[25]算法的改進(jìn)算法dLife[26]與本算法進(jìn)行比較.移動(dòng)模型選取了工作日模型(WDM)[27],實(shí)驗(yàn)場(chǎng)景地圖是赫爾辛基地圖,這是因?yàn)閳?chǎng)景中的節(jié)點(diǎn)數(shù)量相對(duì)較少,節(jié)點(diǎn)間接觸比較稀疏,而節(jié)點(diǎn)之間的社團(tuán)結(jié)構(gòu)明顯,適合采用基于社團(tuán)結(jié)構(gòu)的路由算法.圖8、9、10為WQCA和dLife這兩種路由算法隨TTL時(shí)間變化的消息傳輸成功率、平均時(shí)延和網(wǎng)絡(luò)開(kāi)銷率變化曲線.可以看出,WQCA的傳輸成功率明顯高于dLife,平均時(shí)延也比dLife低.這是因?yàn)閮煞矫娴脑?首先,dLife采用的是K-clique社團(tuán)劃分方法,K-clique社團(tuán)劃分方法的對(duì)于社團(tuán)劃分不如WQCA社團(tuán)劃分方法穩(wěn)定;其次dLife在轉(zhuǎn)發(fā)時(shí),如果目的節(jié)點(diǎn)不在源節(jié)點(diǎn)社團(tuán)內(nèi),就選擇權(quán)重高的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn),而WQCA算法選取的是社團(tuán)的邊緣節(jié)點(diǎn),這使得下一跳節(jié)點(diǎn)選取更為合理.在網(wǎng)絡(luò)開(kāi)銷方面,WQCA在TTL為600分鐘以內(nèi)時(shí)與dLife算法差別不大,在600分鐘以上時(shí)明顯高于dLife算法,這是因?yàn)樵诒舅惴ㄖ腥绻诤荛L(zhǎng)時(shí)間無(wú)法尋找到目的社團(tuán)將通過(guò)增加副本數(shù)來(lái)提高傳輸成功率.如果網(wǎng)絡(luò)環(huán)境對(duì)網(wǎng)絡(luò)開(kāi)銷要求較高,可以根據(jù)情況把TTL設(shè)置為600分鐘以內(nèi).

6 結(jié)論

本文提出了一種基于有權(quán)社團(tuán)結(jié)構(gòu)的路由算法,該路由算法可以選擇兩種不同的方式(MRC或MFC)采集信息,根據(jù)采集的節(jié)點(diǎn)間接觸信息進(jìn)行權(quán)重轉(zhuǎn)化,在此基礎(chǔ)上劃分社團(tuán)并判斷轉(zhuǎn)發(fā)節(jié)點(diǎn).同時(shí),本文根據(jù)網(wǎng)絡(luò)環(huán)境的變化提出了兩種適應(yīng)不同環(huán)境的權(quán)重轉(zhuǎn)化方案,讓路由算法在檢測(cè)到周圍網(wǎng)絡(luò)環(huán)境變化時(shí)能夠自主切換權(quán)重計(jì)算方式.通過(guò)與其他路由算法的比較,本文提出的路由算法能夠在保證較高的傳輸成功率的情況下保持較低的平均時(shí)延,并有效降低網(wǎng)絡(luò)開(kāi)銷.該路由算法性能穩(wěn)定,能夠自主適應(yīng)較大的網(wǎng)絡(luò)拓?fù)渥兓?目前該路由算法還有很大的提升空間,未來(lái)工作將針對(duì)進(jìn)一步提升路由性能以及重疊社團(tuán)等方面作進(jìn)一步研究.

[1]Y P Xiong,L M Sun,J W Niu,Y Liu.Opportunistic networks[J].Journal of Software,2009,20(1):124-137.

[2]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[3]Traag V A,Bruggeman J.Community detection in networks with positive and negative links[J].Physical Review E,2009,80(3):036115.

[4]E M Daly,M Haahr.Social network analysis for information flow in disconnected delay-tolerant MANETs[J].IEEE Transactions on Mobile Computing,2009,8(5):606-621.

[5]Onnela J P,Saram?ki J,Hyv?nen J,et al.Structure and tie strengths in mobile communication networks[J].Proceedings of the National Academy of Sciences,2007,104(18):7332-7336.

[6]Xiang R,Neville J,Rogati M.Modeling relationship strength in online social networks[A].Proceedings of the 19th International Conference on World Wide Web[C].New York:ACM,2010.981-990.

[7]Bigwood Greg,et al.Exploiting self-reported social networks for routing in ubiquitous computing environments[A].IEEE International Conference on Wireless and Mobile Computing[C].Avignon:IEEE,2008.484-489.

[8]Ciobanu R I,et al.Social aspects for opportunistic communication[A].11th International Symposium on Parallel and Distributed Computing (ISPDC)[C].Bavaria:IEEE,2012.251-258.

[9]F Cai,et al.K-clique community detection based on union-find[A].International Conference on Computer,Information and Telecommunication Systems (CITS)[C].Jeju:IEEE,2014.1-5.

[10]Newman M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.

[11]Newman M E J.Analysis of weighted networks[J].Physical Review E,2004,70(5):056131.

[12]Nguyen N P,et al.Adaptive algorithms for detecting community structure in dynamic social networks[A].Proceedings of IEEE INFOCOM[C].Shanghai:IEEE,2011.2282-2290.

[13]Daly E M,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs[A].Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing[C].New York:ACM,2007.32-40.

[14]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.

[15]E Bulut,B K Szymanski.Exploiting friendship elations for efficient routing in mobile social networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(12):2254-2265.

[16]A Mei,et al.Social-aware stateless forwarding in pocket switched networks[A].Proceedings IEEE INFOCOM[C].Shanghai:IEEE,2011.251-255.

[17]Xuebin Ma,et al.A community-based routing algorithm for opportunistic networks[A].2013 Fifth International Conference on Ubiquitous and Future Networks (ICUFN)[C].Da Nang:IEEE,2013.701-706.

[18]Hossmann T,Spyropoulos T,Legendre F.Social network analysis of human mobility and implications for DTN performance analysis and mobility modeling[R].Switzerland:Computer Engineering and Networks Laboratory ETH Zurich,2010.323.

[19]Ma H,Du Q.Research on opportunistic network routing based on community structure[J].Electronic Science and Technology,2013,2013(5):037.

[20]A Ker?nen,J Ott,T K?rkk?inen.The ONE simulator for DTN protocol evaluation[A].The 2nd International Conference on Simulation Tools and Techniques[C].Brussels:ICST,2009.55.

[21]Ekman Frans,Ari Ker?nen,Jouni Karvo,J?rg Ott.Working day movement model[A].Proceedings of the 1st ACM SIGMOBILE Workshop on Mobility Models[C].New York:ACM,2008.33-40.

[22]Spyropoulos,et al.Single-copy routing in intermittently connected mobile networks[A].Proceedings of Sensor and Ad Hoc Communications and Networks SECON[C].Los Angeles:IEEE,2004.235-244.

[23]Vahdat A,Becker D.Epidemic routing for partially connected ad hoc networks[R].Technical Report CS-200006,Duke University,2000.

[24]Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[A].Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking[C].New York:ACM,2005.252-259.

[25]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.

[26]Moreira W,Mendes P,Sargento S.Opportunistic routing based on daily routines[A].2012 IEEE International Symposium on World of Wireless,Mobile and Multimedia Networks (WoWMoM)[C].San Francisco:IEEE,2012.1-6.

[27]Ekman F,Ker?nen A,Karvo J,et al.Working day movement model[A].Proceedings of the 1st ACM SIGMOBILE Workshop on Mobility Models[C].New York:ACM,2008.33-40.

馬學(xué)彬 男,1981年生,內(nèi)蒙古大學(xué)副教授,從事計(jì)算網(wǎng)絡(luò)技術(shù)方面的有關(guān)研究.

E-mail:csmaxuebin@imu.edu.cn

白 婧 女,1989年12月出生,內(nèi)蒙古大學(xué)碩士研究生.研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò).

鄭田玉 男,1993年12月出生,內(nèi)蒙古大學(xué)碩士研究生.研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò).

A Routing Algorithm Based on Weighted Community Detection for Opportunistic Networks

MA Xue-bin,BAI Jing,ZHENG Tian-yu

(SchoolofComputer,InnerMongoliaUniversity,Hohhot,InnerMongolia010021,China)

Most of the opportunistic networks routing algorithms based on community detection use an un-weighted network which ignores the degree of intensity of relations between nodes.This paper proposes a routing algorithm based on community detection of weighted network.We improve quick community adaptation (QCA) and make it adapt to the opportunistic networks by using weighted networks.The algorithm calculates link weights by the connection information between nodes in the network.According to the different network environments,we present two weight calculation strategies:normalized weight strategy and non-normalized weight strategy.The algorithm detects the environment around the current node,and then chooses the right strategy.To illustrate the performance of our algorithm,we test the algorithm by using a simulation environment and a real dataset.The results demonstrate that our algorithm gets a reasonable community structure and reduces the overhead ratio and keeps a higher delivery probability.

opportunistic networks;community detection;routing algorithm;weighted topology

2015-02-04;

2015-11-20;責(zé)任編輯：李勇鋒

國(guó)家自然科學(xué)基金(No.61162006);內(nèi)蒙古自然科學(xué)基金(No.2014MS0605)

TN92

A

0372-2112 (2016)10-2449-10

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.024