夏茂晉， 王青山， 王 琦， 曹 成， 汪麗芳

(合肥工業(yè)大學 數(shù)學學院，安徽 合肥 230009)

計算與測試

基于團結構親密度的移動社交網絡數(shù)據轉發(fā)算法*

夏茂晉， 王青山， 王 琦， 曹 成， 汪麗芳

(合肥工業(yè)大學 數(shù)學學院，安徽 合肥 230009)

由于移動社交網絡中不存在穩(wěn)定的端到端連接，因此移動社交網絡中的數(shù)據轉發(fā)是一個重要問題。從節(jié)點的友好性角度出發(fā)，利用節(jié)點間的友好性，構造了節(jié)點間的團結構并利用團與節(jié)點、社區(qū)之間的親密度，提出了一種基于團結構親密度的數(shù)據轉發(fā)算法(DFAIG)?；舅枷胧?，數(shù)據包攜帶節(jié)點只有在本社區(qū)AP或者相遇節(jié)點與以目的節(jié)點為中心的團結構的親密度達到一定要求時，才轉發(fā)數(shù)據包給相遇節(jié)點。仿真結果顯示:與著名的Epidemic, Label和SGBR相比，提出的算法在降低網絡開銷上具有明顯優(yōu)勢，且有效地提高數(shù)據包傳遞率。

移動社交網絡； 團結構親密度； 數(shù)據轉發(fā)； 拷貝數(shù)

0 引 言

容遲網絡(delay tolerant networks,DTNs)[1,2]作為一類新型的無線網絡，廣泛應用于社交網絡、車載網絡、戰(zhàn)場通信、野生動物保護等具有挑戰(zhàn)性的領域。隨著近年來無線網絡和5G技術的研究，使得移動社交網絡(mobile social networks)越來越成為容遲網絡的一個非常重要的應用。在移動社交網絡中，人們通過WiFi、4G、藍牙等間歇式的連接來相互傳遞數(shù)據，從而實現(xiàn)網絡設備之間的數(shù)據通信。但是由于移動社交網絡中不存在穩(wěn)定的端到端連接，傳統(tǒng)的路由協(xié)議不適用于該類網絡。因此，數(shù)據轉發(fā)是該類網絡中一個關鍵問題。移動社交網絡中一般使用“存儲—攜帶—轉發(fā)”的數(shù)據轉發(fā)方式。

Epidemic[3]作為經典的泛洪式路由方法，網絡中攜帶數(shù)據包的節(jié)點會將數(shù)據包拷貝給所有相遇且不攜帶數(shù)據包的節(jié)點。通過這種洪泛式的方法將數(shù)據包盡可能地傳遞給網絡中的所有節(jié)點，以達到將數(shù)據包快速傳遞到目的節(jié)點的目的。另一種典型的路由方法Prophet[4]是基于節(jié)點之間的相遇歷史信息和傳遞性來預測每個節(jié)點的傳遞概率，即將數(shù)據包傳遞給目的節(jié)點的概率。數(shù)據包的攜帶者將數(shù)據包轉發(fā)給相遇節(jié)點中傳遞概率更高的節(jié)點。然而容遲網絡近期的研究熱點是，通過節(jié)點的社會屬性來設計路由方法[5～10]。比如節(jié)點的社區(qū)性、中心性、友好性、相似性等等。在Label[5]算法中，首先將網絡中的節(jié)點按照不同的社區(qū)貼上標簽，同一個社區(qū)的節(jié)點標簽相同。這樣源節(jié)點就可以將數(shù)據包有目的性的傳遞到目的節(jié)點所在社區(qū)中的節(jié)點，即和目的節(jié)點相同標簽的節(jié)點。Bulut E[7]提出了新的標量SPM(CSPM)來衡量節(jié)點間的友好性，并利用節(jié)點間的友好性定義節(jié)點間是否為直接或間接的朋友，然后利用節(jié)點間友好性的不同來轉發(fā)數(shù)據包。Dsearching[9]是基于節(jié)點的社區(qū)活動性將移動社交網絡分成若干個子區(qū)域，每個子區(qū)域設立靜態(tài)地標，用來存儲節(jié)點訪問過的子區(qū)域和移動信息，利用這些信息可以有效地發(fā)送數(shù)據包從而傳遞到目的節(jié)點，很大地降低了傳遞延遲。

本文從節(jié)點的社會屬性出發(fā)，同時考慮節(jié)點間友好性、節(jié)點與節(jié)點構成的團之間的友好性以及團與地理社區(qū)之間的友好性，提出了基于團結構親密度的數(shù)據轉發(fā)算法(data forwarding algorithm based on the intimacy of groups，DFAIG)。

1 網絡模型

由小世界模型可以知道，人們會因為興趣愛好彼此之間接觸頻繁(社會中每個人都有自己的朋友圈)。假設移動社交網絡中有N個地理社區(qū)，每個地里社區(qū)設置一個接入點(access point，AP)配置無線訪問設備，n個攜帶無線訪問設備的人隨意活動在這些地理社區(qū)。人們會因為相同的興趣愛好彼此之間組成一個團體，比如籃球隊、舞蹈團和科研小組等，這些團體成員都有自己的朋友節(jié)點，比如籃球隊成員有自己的朋友，他們之間接觸頻繁。同樣，一個人可能會因為不同的興趣愛好，同時參加籃球隊和舞蹈團。而且由于興趣不同，每個團經常訪問的地理社區(qū)也是不一樣的，比如籃球隊經常出沒于籃球場。根據節(jié)點i和其他節(jié)點j在某個時刻T內接觸的歷史信息，定義函數(shù)gi,j(t)，gi,j(t)(gi,j(t)=0)表示在時刻t節(jié)點i與節(jié)點j的累計接觸次數(shù)，則節(jié)點i與節(jié)點j的平均接觸率φ為

(1)

則節(jié)點i與節(jié)點j的平均接觸率在節(jié)點i總的接觸率中所占的比例，稱為親密度λi,j，即

(2)

定義1當且僅當λi,j≥λ(i≠j)時，節(jié)點j在以節(jié)點i為中心的團Gi中，其中λ是閾值。

閾值λ根據不同的應用場景來設置一個合適的值，本文在實驗中取λ值為0.02。同時，本文定義一個自由變量

(3)

一個節(jié)點可以同時屬于幾個團結構，比如節(jié)點j除了屬于以節(jié)點i為中心的團外可能還屬于其他的團結構。如果源節(jié)點知道以目的節(jié)點為中心的團中有哪些節(jié)點以及該團經常出現(xiàn)的地理社區(qū)，就可以選擇與目的節(jié)點d為中心的團Gd中節(jié)點接觸頻繁的節(jié)點或者AP點作為中繼節(jié)點。因此，本文定義親密度ρi,Gd來衡量節(jié)點i與以目的節(jié)點d為中心團之間的接觸頻率

(4)

式中α和β(0≤α≤β≤1)為節(jié)點i與團Gd中成員之間接觸重要性的參數(shù)。如果兩個節(jié)點與團Gd總的累計接觸次數(shù)一樣，與目的節(jié)點d接觸次數(shù)越多的節(jié)點親密度越高。同樣地，利用式(3)可以計算地理社區(qū)AP點與團Gd之間的親密度。

根據節(jié)點、地理社區(qū)AP點與團Gd之間的親密度不同，數(shù)據包攜帶節(jié)點可以選擇合適的中繼節(jié)點來轉發(fā)數(shù)據包。如表1所示，假設數(shù)據包攜帶節(jié)點j與Gd親密度為0.211 1，根據表中所列節(jié)點1～4與Gd親密度可知，節(jié)點j僅僅在遇到節(jié)點2時才會將數(shù)據包傳遞節(jié)點2，而在遇到節(jié)點1、節(jié)點3和節(jié)點4時都不產生拷貝。同理可知，節(jié)點j在遇到編號為1的社區(qū)AP點時也會轉發(fā)數(shù)據包，而在遇到其他三個AP時都不產生拷貝。

表1 節(jié)點、地理社區(qū)AP與團Gd的親密度

節(jié)點或者AP編號1234節(jié)點與Gd的親密度0．1110．3330．1110．167AP與Gd的親密度S0．3250．1250．2110．167

2 基于團體活躍度的數(shù)據轉發(fā)算法

DFAIG之前，首先介紹如何計算節(jié)點的團結構以及團在各個地理社區(qū)的活躍度。節(jié)點i與其他節(jié)點接觸以及訪問某個地理社區(qū)時，都會記錄節(jié)點i與這些節(jié)點之間總的累積接觸次數(shù)。每個節(jié)點根據式(1)、式(2)和定義1可以得到以自己為中心的團結構，再通過兩個節(jié)點碰面時交換彼此的團結構信息。因此，網絡中節(jié)點可以知道以目的節(jié)點為中心的團結構Gd中包含的節(jié)點。根據式(4)可以進一步計算其他節(jié)點、地理社區(qū)AP與團Gd之間的親密度。當然，團結構Gd以及節(jié)點與團Gd的親密度隨著節(jié)點的移動被及時更新。

其次，利用團結構Gd以及節(jié)點與團Gd親密度等信息，數(shù)據包攜帶節(jié)點可以選擇更合適的節(jié)點作為中繼節(jié)點，從而快速地將數(shù)據包傳遞到團Gd中。數(shù)據包在到達團Gd中后選擇以洪泛的方式傳遞到目的節(jié)點。具體描述如下：

假設攜帶數(shù)據包p的節(jié)點i在遇到不攜帶此數(shù)據包的節(jié)點j時：

1)如果節(jié)點i屬于團Gd

①節(jié)點j也是屬于團Gd時，節(jié)點i拷貝數(shù)據包給節(jié)點j；

②否則不產生拷貝；

2)如果節(jié)點i不屬于團Gd(包括節(jié)點i，j是地理社區(qū)AP點時情形)

③節(jié)點j是以目的節(jié)點為中心的團Gd中的節(jié)點或者目的節(jié)點，則轉發(fā)數(shù)據包給節(jié)點j；

④如果節(jié)點j不屬于團Gd且ρj,Gd≥ρi,Gd，則轉發(fā)數(shù)據包給節(jié)點j；

3)結束。

在上述步驟④中，條件表達式ρj,Gd≥ρi,Gd表示當節(jié)點j和團Gd的親密度大于節(jié)點i和團Gd的親密度時，節(jié)點i就可以轉發(fā)數(shù)據包給節(jié)點j。從上面算法可以看出存在①,②和③三種情況，節(jié)點i將拷貝或者轉發(fā)數(shù)據包給節(jié)點j。

3 性能評價

本文使用Infocom 06的真實跟蹤數(shù)據在C++編寫的仿真軟件上進行模擬實驗。該數(shù)據是由2006年在西班牙巴塞羅那召開的Infocom 會議上78個學生通過攜帶Imote設備采集得到的。會場布置20個固定的Imote設備作為AP點，分布在不同區(qū)域。本文將提出的算法DFAIG與著名的Epidemic[3]，Label[5]和SGBR[10]算法進行比較。在Epidemic算法中，攜帶數(shù)據包的節(jié)點會將數(shù)據包在網絡中進行洪泛式的傳播給其他沒有存儲數(shù)據包的節(jié)點。Label算法中攜帶數(shù)據包的節(jié)點為了在節(jié)約網絡資源消耗下，將數(shù)據包傳遞給目的節(jié)點所在社區(qū)，只會將數(shù)據包傳遞給和目的節(jié)點標簽一樣的節(jié)點。SGBR則是提出了一種基于社會團體的路由算法，該算法在提高傳遞率同時，又節(jié)約了網絡資源消耗。本文用以下三個參數(shù)來衡量不同轉發(fā)策略的性能：1)傳遞率：網絡中被成功傳遞到目的節(jié)點的數(shù)據包占所有發(fā)送數(shù)據包的比率。2)平均延遲：數(shù)據包從源節(jié)點到達目的節(jié)點所經歷的時間。3)拷貝數(shù)：采用一個數(shù)據包被成功傳遞時在網絡中產生的拷貝數(shù)目。源節(jié)點和目的節(jié)點從移動節(jié)點中隨機選取，為了突出與目的節(jié)點接觸的重要性，在實驗中，令α=0.8，β=1。

3.1 源節(jié)點數(shù)據包數(shù)目對算法性能的影響

首先通過將DFAIG算法中源節(jié)點初始數(shù)據包數(shù)量的值從500變化到5 000來比較四種算法性能，實驗結果如圖2所示。由圖2(a)所示，四種算法的拷貝數(shù)變化不是很明顯，本文提出的DFAIG算法最低，比Epidemic，Label，SGBR分別最多低77 %,63 %，34 %。如圖2(b)所示，隨著數(shù)據包數(shù)量L的增加，DFAIG算法僅僅比Epidemic低，比其他兩種算法都高，其中Epidemic算法由于使用洪泛策略而達到傳遞率的上界。如圖2(c)所示，DFAIG算法在傳遞率、拷貝數(shù)都優(yōu)于Label和SGBR算法，僅平均延遲比其他方法略高。

圖2 數(shù)據包數(shù)目對算法性能的影響

3.2 數(shù)據包生存時間對算法性能的影響

在社交網絡中，由于端到端連接的不穩(wěn)定性，如果過低，路由算法很可能無法完成數(shù)據轉發(fā)。因此，將數(shù)據包生存時間(time-to-live,TTL)從8 h增加到16 h，來評價DFAIG，Epidemic，Label，SGBR四種算法性能，其中λ=0.02。實驗結果如圖3所示。由圖3(a)可知，DFAIG拷貝數(shù)明顯比其他三種算法都低，其中，比Epidemic,Label和SGBR分別最多低79 %,64 %和35 %。由圖3(b)可知，對不同的TTL值，DFAIG傳遞率比Epidemic要低(由于Epidemic采用洪泛的方式，因此它的傳遞率是最高的)，比Label和SGBR都稍高。在圖3(c)中可以看出，DFAIG平均延遲比SGBR要低10 %左右，比Label要高8 %，比Epidemic高14 %。

3.3 閾值λ對DFAIG算法性能的影響

為了研究閾值λ對算法DFAIG的影響，將λ從0.01增加到0.035，其中TTL=12 h，實驗結果如圖4所示。由圖4(a)可知，拷貝數(shù)隨著λ的增大快速減少，實驗結果進一步驗證了結論：網絡中的拷貝數(shù)是與閾值λ負相關；而由圖4(b)可知，可以發(fā)現(xiàn)DFAIG的傳遞率隨著λ的增大逐漸減??；由圖4(c)可以發(fā)現(xiàn)，DFAIG的平均延遲時間隨著λ的增大而逐漸增加。

4 結 論

仿真實驗結果表明:本文提出的DFAIG算法與Epide-mic,Label和SGBR等算法相比，大幅度降低網絡中拷貝數(shù)目從而節(jié)約網絡資源，同時傳遞率僅僅比采用洪泛策略的Epidemic算法低。未來將進一步研究團結構親密度在動態(tài)社區(qū)數(shù)據轉發(fā)算法中的應用。

[1] Balasubramanian A,Levine B N,Venkataramani A.DTN routing as a resource allocation problem[C]∥Proceedings of SIGCOMM 2007，Kyoto,2007:373-384.

圖3 TTL對算法性能的影響

圖4 λ值對DFAIG算法性能的影響

[2] 劉艷萍，王青山，王 琦.移動社交網絡中基于影響力的數(shù)據轉發(fā)算法 [J].合肥工業(yè)大學學報：自然科學版，2014，53(3):295-300.

[3] Vahdat A,Becker D.Epidemic routing for partially connected Ad Hoc networks[R].San Diego:University of California,2000.

[4] Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[C]∥ACM International Symposium on Mobilde Ad Hoc Networking and Computing,MobiHoc 2003,Annapolis,MD America:ACM,2003：19-20.

[5] Pan Hui,Crowcroft J.How small labels create big improvement-s[C]∥The Fifth Annual IEEE International Conference，White Plains:IEEE,2007:65-70.

[6] Pan Hui,Crowcroft J,Yoeki E.Bubble rap:Social-based forwarding in delay tolerant networks[J].IEEE Transactions on Mobile Computing,2010,10(11):1576-1589.

[7] Bulut E,Szymanski B K.Friendship-based routing in delay tole-rant mobile social networks[C]∥IEEE Global Telecommunications Conference,Miami,America:IEEE,2010,1-5.

[8] Dang F,Yang X,Long K P.Spray and forward:Efficient routing based on the Markov location prediction model for DTNs[J].Science China Information Sciences,2012,5(2):433-440.

[9] Chen K,Shen H D.Searching:Distributed searching of mobile nodes in DTNs with floating mobility information[C]∥2014 IEEE Conference on Computer Communications,Toronto，Canada,IEEE,2014:2283-2291.

[10] Abdelkader T,Naik K.SGBR:A routing protocol for delay tole-rant networks using social grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2472-2481.

Data forwarding algorithm based on intimacy of group in mobile social networks*

XIA Mao-jin, WANG Qing-shan, WANG Qi, CAO Cheng, WANG Li-fang

(School of Mathematics,Hefei University of Technology,Hefei 230009,China)

As intermittent and uncertain network connectivity in mobile social networks,data forwarding becomes an important problem.Based on the friendship of nodes,first constructs groups of nodes and then utilizing the intimacy of groups with nodes and communications,propose a data forwarding algorithm based on intimacy of group (DFAIG).The idea of DFAIG is that data packet carrier only forward data to encounter node its communication AP or the encounter node whose intimacy of group which takes destination node as center meets a certain requirement.Simulation results show that the algorithm has obvious superiority on reducing network overhead and also can significantly increase delivery ratio compared with Epidemic algorithm,Label and SGBR algorithm.

mobile social networks; intimacy of groups; data forwarding; copy numbers

10.13873/J.1000—9787(2017)02—0127—04

TP 301.6

A

1000—9787(2017)02—0127—04

夏茂晉(1992-)，男，碩士研究生，主要研究方向為移動社交網絡路由算法設計。

王青山(1975-)，男，博士，副教授，研究生導師，從事移動社交網絡路由設計研究工作。