采用傳遞概率與社會網絡分析的延遲容忍網絡路由

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

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

?

采用傳遞概率與社會網絡分析的延遲容忍網絡路由

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

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

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

延遲容忍網絡;社會網絡分析;傳遞概率;路由設計

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

1 RPRSA中的基本模型與方法

1.1 網絡模型和假設

1.2 社會網絡分析模型

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

1.3 傳遞概率模型

在社會性DTN中,有一類情況可能會發生,網絡中存在部分節點具有弱社會關系甚至是孤立的。為了保證這些節點在社會性DTN中的通信傳輸質量,本文采取了基于傳遞概率的路由策略[12]。通過傳遞概率的更新,節點可以更好地預測自己在未來一段時間內的運動特性。如果一對節點進行了直接端到端通信,那么在之后的一段時間內很可能再次進行直接端到端通信,這就可以提高弱社會關系甚至孤立節點的通信傳輸質量。本文的傳遞概率更新包括節點間傳遞概率更新和節點社區間傳遞概率更新。

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

1.4 路由模型

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

同時,為了防止采取的路由機制對網絡造成負擔,本文首先限制了源節點拷貝數,其次消息在未到達l時采取零復制路由機制,即m傳遞到下一跳節點后,上一跳節點將刪除m,并且消息在到達l后,l以外的所有節點都要刪除消息m,最后限制m的生存時間,如果在規定時間內沒有到達目的節點,那么刪除m。

2 傳遞概率更新算法

傳遞概率更新分為傳遞概率衰減部分更新和傳遞概率上升部分更新兩個步驟。傳遞概率衰減部分更新是節點間相遇時,在進行端到端通信之前,相遇節點依照相鄰兩次相遇的時間間隔進行衰減部分的更新;傳遞概率上升部分更新是相遇節點間互相參照對方的傳遞概率表單,更新自身表單中對應傳遞概率相對較小的部分。

直接節點間傳遞概率更新如下式

(1)

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

(2)

直接社區傳遞概率更新如下式

(3)

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

(4)

3 路由算法

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

設置實驗仿真時間T;設置仿真實驗的節點組;設置節點的消息產生周期r;設置消息最大副本數c;設置消息生存時間F;初始化節點的傳遞概率表單P。

在節點x、y相遇時,節點x的路由過程如下。

步驟1 判斷節點x中消息的生存時間是否超過F,對于超過F的消息,在節點x中刪除;

步驟2 判斷節點x是否有需要傳遞的消息,如果有進行步驟3,否則節點x結束消息傳遞;

步驟3 判斷節點y是否接收過節點x即將傳遞的消息,如果接收過,則拒絕再次接收這個消息,否則節點x、y進行步驟4;

步驟4 如果節點x有節點y沒有接收過的消息m,且該消息的目的節點是d,則目的節點d所在的目的社區是l。

步驟5 如果節點y是消息m的目的節點,則執行步驟6,否則節點x直接將消息m傳遞給y,并且刪除網絡中所有的消息m;

步驟6 如果節點x、y不都在目的社區l外部,則執行步驟7,否則比較節點x、y與目的社區l的傳遞概率,當p(x,l)

步驟7 如果節點x、y不都在目的社區l內部,則執行步驟8,否則比較節點x、y與目的節點d的傳遞概率,當p(x,d)

步驟8 節點x在目的社區l外部,節點y在目的社區l內部,則節點x將消息m發送到節點y,并且節點x刪除消息m。

步驟9 循環執行步驟1～8,直到仿真時間結束。

RPRSA路由充分利用了節點的短期移動特性和長期運動規律,使得弱社會關系節點和孤立節點可以更好地傳輸消息,保證更多的節點之間能夠建立端到端的有效連接。

4 仿真結果與分析

4.1 仿真場景與參數

本文采用了數據集Reality Mining[13-14],該數據集開始于2004年,采集了96個節點,其中75個節點來自麻省理工大學媒體實驗室,另外21個節點來自臨近的斯隆商學院。

本文采集時間為16 981 816 s,采集了205 187組數據,每一組數據包括以下4方面內容:組序號,即代表數據集中的第幾組數據;連接狀態,即連接或者斷開;時間,即得到此連接狀態的時間;節點序號,即處于此連接狀態下的一對節點各自的序號。

仿真實驗選取了數據集中的3個數據段,表1列出了所選取的數據量以及仿真的起止時間。

表1 仿真實驗中選取的3個數據段

實驗仿真時間為T,即仿真時間的起始值和終止值的差值。仿真時選取了3個不同的節點組,每組節點的數據集中有96個節點作為源節點,每個源節點隨機選取一個節點作為自己的目的節點,目的節點的產生是隨機的,沒有關聯;消息產生周期r為50 000 s;衰減因子γ=0.98;傳遞因子β=0.25;節點間的初始傳遞概率pn=0.75,節點社區間的初始傳遞概率pd=0.75。

初步的仿真表明,這些參數值的選取是合理的。盡管參數的取值并不是唯一的,但是取值符合概率模型的實際情況。當參數值發生變化后,會對網絡中的節點間傳遞概率產生影響,但對最后的仿真結果幾乎無影響,因為消息動態地在網絡中尋找合適的節點進行路由轉發。

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

4.2 仿真結果

首先分析RPRSA路由,在給定的3個節點組中,每組節點分別在已選取的3個數據段上進行仿真,消息生存時間F=T/3,源節點消息拷貝數c=1。對Rank、Label、Bubble路由進行同樣的仿真,這樣每種算法都會得到9組仿真數據。

4.2.1 源節點平均傳輸成功率 由于篇幅限制,對每種算法得到的9組數據中的平均傳輸成功率再次取平均值,然后再與其他算法進行比較。

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

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

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

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

4.2.2 通信失敗的源節點數 表2列出了網絡中通信失敗的源節點數對比情況。由于篇幅限制,本文沒有列出第3組節點在3個數據段上的通信失敗的源節點數。

可以看到,與Label、Rank、Bubble路由相比,在相同條件下RPRSA路由中通信失敗的源節點數都要少很多。因此,RPRSA路由可以更好地保證弱社會關系節點和孤立節點的通信傳輸質量,更好地實現端到端之間的通信,尤其對于那些端端之間有更高可靠性要求的網絡,RPRSA路由是更好的選擇。

表2 網絡中通信失敗的源節點數對比情況

4.2.3 生存時間F對RPRSA路由的影響 選取第1組節點和第3個數據段,在其他條件相同時,分別取值為T/3、T/2和T。圖4中是TTL取值T/2和T/3時所得到的平均傳輸成功率的差值;圖5中是TTL取值T和T/2時所得到的平均傳輸成功率的差值。

圖4 TTL取值T/3與T/2時性能對比

圖5 TTL取值T/2與T時性能對比

表3比較了第3個數據段,對于不同的F取值時,網絡中通信失敗的源節點數。

適當的增加F,可以提高網絡的平均傳輸成功率,但幾乎不會降低通信失敗的源節點數;而且F增加也會對網絡造成負擔。

4.2.4 源節點拷貝數c對RPRSA路由的影響

表3 在第3個數據段F對通信失敗的源節點數的影響

選取第1組節點和第3個數據段,在其他條件相同時,c分別取值1和5。圖6是c=5和c=1時所得到的平均傳輸成功率的差值。

圖6 源節點拷貝數取值5與1時性能對比

表4統計了c取值1和5時,網絡中通信失敗的源節點數。

表4 源節點拷貝數對通信失敗的源節點數影響

適當地提高c值,雖然可以提高平均傳輸成功率,但幾乎不會降低通信失敗的源節點數,而且c的取值增加也會對網絡造成負擔。

5 結 語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[本刊相關文獻鏈接]

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

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

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

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

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

陳家旭,唐亞哲,胡成臣,等.延遲容忍網絡中基于地點偏好的社會感知多播路由協議設計.2014,48(6):13-18.[doi:10.7652/xjtuxb201406003]

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

(編輯 武紅江)

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

YANG Mo,YOU Lei,LI Bing,ZHAO Jianjun

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

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

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

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

時間:2016-10-19

10.7652/xjtuxb201612021

TP393

A

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

網絡出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20161019.1112.004.html