機會社會網絡中一種基于社區的高效路由算法

任 智，黃希凱，譚永銀

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

機會社會網絡中一種基于社區的高效路由算法

任 智，黃希凱，譚永銀

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

針對機會社會網絡中RADR（機會社會網絡消息傳送算法）存在消息傳輸時延偏大和消息傳輸成功率偏低的問題，提出一種ECRA（基于社區的高效的機會社會網絡路由算法）。ECRA只選取與消息目的節點在同一個社區的鄰居節點來計算重要度，并且利用連通拓撲偵聽相遇節點，檢測相遇節點的鄰居節點中是否存在更高重要度的節點，若存在，則利用相遇節點將消息傳遞給具有更高重要度的鄰居節點。理論分析和仿真結果表明，ECRA與RADR及相關對比算法比較，在消息傳輸成功率、平均端到端時延等方面的性能均得到了提升。

機會社會網絡；路由算法；社區；重要度；偵聽機制

0 引 言

機會網絡是一種特殊的移動自組織網絡，它能夠在網絡鏈路處于間歇性連接的狀態下，提供端到端的通信服務［1］。隨著移動終端設備的高速發展，利用移動設備進行消息傳輸也越來越普遍，將社會關系引用到機會網絡當中，能更好地優化機會網絡的消息傳輸機制［2］。

目前，研究人員已提出一些有效的機會社會網絡路由算法：SGBR（基于社會群組的路由算法）［3］利用節點間相遇的頻繁程度計算出連通度值，通過設定連通度閾值劃分社區，向與目的節點連通度值大的節點轉發消息，該算法的缺點是無序發送消息時可能導致生存期剩余時間小的消息到期被刪除，降低了傳輸成功率。CHMTS（社區分層消息傳輸）算法［4］利用EO（外部優化）算法劃分社區，并使用改進的Prophet算法進行消息傳輸，該算法的缺點是消息轉發時沒有考慮整個傳輸鏈路的高效性。文獻［5］提出了一種RADR（機會社會網絡消息傳輸算法），該算法使用k-Clique算法［6］進行社區檢測，在消息傳輸階段根據節點重要度進行路由選擇，但是該算法存在節點重要度計算不準確以及路由選擇單一的問題。針對RADR出現的問題，本文提出一種ECRA（基于社區的高效的機會社會網絡路由算法）。

1 社區劃分與問題描述

1.1社區劃分

ECRA采用k-Clique算法進行社區劃分，k-Clique算法中熟悉集Fi為節點vi的相遇節點中持續相遇時間超過閾值的節點集合，vj是vi熟悉集內的節點，不完全熟悉集為FCj，即vi得到的vj的熟悉集。Co為局部社區。當節點vo與節點vi相遇，算法執行步驟如下：

步驟1：節點初始化，Co=｛vo｝，Fo=?，FCj=?。

步驟2：當節點vo與節點vi相遇時，交換彼此局部社區Ci、熟悉集Fi和不完全熟悉集FCj的信息。步驟3：若vi不在vo的熟悉集Fo中，則vo更新與節點vi的持續時間，然后執行步驟4；如果持續時間超過閾值，則將vi加入vo的熟悉集Fo和局部社區Cv中。

步驟4：若熟悉集Fi至少包括Co中的k-1個節點，則也將節點vi加入到Co中。

步驟5：若vi已是Co中節點，且vi熟悉集中的節點vj滿足|FCj∩Co|≥k-1，則將vj加入到Co中。

1.2問題描述

RADR存在以下問題：

（1）原算法考慮節點的重要度是為了將消息盡快轉發到目的節點所在社區，而在計算節點重要度時，將節點的所有鄰居節點的社會強度加權計算進去，沒有考慮鄰居節點中存在非消息目的節點所在社區的節點，會對節點重要度的計算造成干擾，影響傳輸效率。

（2）原算法認為節點重要度高的節點遇見目的節點的概率更高，并且將消息轉發到目的節點社區的概率更高，沒有考慮到利用連通拓撲結構偵聽機制來轉發消息，降低了傳輸成功率和消息轉發效率，并增加了傳輸時延。

2 ECRA

本文提出的ECRA旨在解決RADR存在的兩個問題，新算法中為節點重要度計算和消息轉發設計了兩種新機制，從而達到降低消息傳輸時延、提高傳輸成功率和轉發效率的目的。

2.1社會權重和重要度計算

RADR使用社會權重和重要度來衡量節點的社會性。

（1）社會權重的計算

在第i個時間片段ΔTi內，節點x與節點y有n次接觸，第k次接觸為CD（x，y）k，則在這個時間片段內的接觸時間TCT（x，y）i的計算公式為

在第j天的第i個時間片段ΔTi，節點x與y的平均累積接觸持續時間為AD（x，y）ji，計算公式為

節點x與節點y的社會權重由下式計算得到：

式中，t為一天劃分的時間片段數。

（2）節點重要度的計算

節點的重要度與節點的社會權重有關，其計算公式為

式中，N（x）為節點x的所有鄰居節點集合，d為隨機因子。

2.2ECRA包含的新機制

2.2.1節點重要度的計算更新

由2.1節可知，RADR計算節點的重要度時，N（x）是節點x的所有鄰居節點集合，如圖1所示，圖中Ui表示節點所在社區。式（4）將節點A的所有鄰居節點的社會權重加權代入公式計算，這樣計算出來的結果不能準確地反應出是節點到目標社區的重要度大，因為節點到其他社區的加權可能會導致總的節點重要度大。因此，為了準確衡量節點到目的節點社區的重要度，ECRA在運用式（4）計算時，N（x）只包含與目的節點同一個社區的節點，這樣更能體現到達目的節點社區的概率，消息能更快地傳遞到目的節點所在社區。

圖1　節點重要度計算示意圖

2.2.2利用連通拓撲圖偵聽相遇節點

ECRA利用連通拓撲的有利條件提出了節點偵聽的思路，利用中間節點將消息轉發給重要度更高的節點，可以提高傳輸可靠性和傳輸效率，降低端到端時延。圖2所示為通信重疊區域內消息傳輸示意圖。由圖可知，消息攜帶節點S向其周圍的節點廣播Hello消息，確定通信范圍內周圍的鄰居節點。鄰居關系確定后，節點S利用MAC（媒體訪問控制）層偵聽它的鄰居節點B發出的裝載數據和控制信息的消息，判斷消息類型并提取頭部的MAC地址。獲得幀中MAC地址后，MAC層通過跨層信息共享的方式將其送往網絡層；網絡層收到該MAC地址后做一次反向ARP（地址解析協議）處理，獲知鄰居節點與哪些節點進行通信。如果節點S的網絡層發現節點A是B的鄰居，即使B的重要度相對更低，也將消息m發送給B，以便使消息通過B傳遞到A，利用節點A讓消息盡快到達與目的節點相遇概率更高的節點，從而提高傳輸成功率。

圖2　通信重疊區域內消息傳輸示意圖

2.3算法操作步驟

根據相遇節點與消息目的節點是否同屬于一個社區，ECRA分為兩種傳輸方式：

（1）相遇節點與消息目的節點同屬于一個社區

步驟1：節點i、j在網絡中移動，攜帶消息m的節點i與節點j相遇，節點i判斷節點j是否是消息m的目的節點；

步驟2：如果鄰居節點j是消息的目的節點，則i直接將消息m發送給目的節點j，完成消息傳遞，否則進行下一步；

步驟3：節點i和j相互交換雙方的存儲矢量表，若節點j中存在消息m，則雙方不做操作，繼續移動，否則轉向下一步；

步驟4：節點i與節點j交換雙方的社會信息表，如果節點j到消息m的目的節點D的社會權重大于節點i到節點D的社會權重，則節點i將消息m拷貝一份，傳遞給節點j，否則轉向下一步；

步驟5：如果節點j到目的節點D的社會權重小于節點i到節點D的社會權重，則由當前節點i繼續攜帶消息在網絡中移動。

（2）相遇節點與消息目的節點不屬于同一個社區

步驟1：節點i、j在網絡中移動，攜帶消息m的節點i與節點j相遇，節點i判斷節點j是否是消息m的目的節點；

步驟2：如果鄰居節點j是消息的目的節點，則i直接將消息m發送給目的節點j，完成消息傳遞，否則轉向下一步；

步驟3：節點i和j相互交換雙方的存儲矢量表，若節點j中存在消息m，則雙方不做操作，繼續移動，否則轉向下一步；

步驟4：節點i與節點j交換雙方的社會信息表，如果節點j到消息m的目的節點D的重要度大于節點i到節點D的重要度，則節點i將消息m拷貝一份，傳遞給節點j；否則轉向下一步；

步驟5：利用連通拓撲圖跨層偵聽輔助傳輸機制，節點i偵聽相遇節點j的鄰居節點信息，判斷節點j的鄰居中有沒有重要度大于節點i的鄰居節點，若有，則將消息m拷貝一份，轉發給節點j，否則轉向下一步；

步驟6：當前節點i繼續攜帶消息在網絡中移動。

3 ECRA仿真實驗及分析

本文使用ONE［7］作為仿真平臺，仿真場景參數設定如表1所示。

表1　仿真場景參數設定

本節通過改變節點緩存的大小，分析比較ECRA、RADR和CHMTS算法在消息傳輸成功率、平均端到端時延、轉發效率和消息平均存儲時間4個方面的性能。

（1）消息傳輸成功率

圖3　節點緩存對消息傳輸成功率的影響

圖3所示為節點緩存對消息傳輸成功率的影響。由圖可知，當節點緩存不斷變大時，消息成功傳輸的概率均有所提高。ECRA消息成功傳輸的概率要優于另外兩種算法，這是因為ECRA利用有效連通拓撲偵聽鄰居節點，將消息轉發給更有利于數據包到達目的節點的節點，使轉發更具有效性，同時在計算節點重要度時，只計算與目的節點同一個社區的鄰居節點，使節點重要度的計算更準確，更有利于消息的傳遞，從而有效地提高了算法的消息傳輸成功率。

（2）平均端到端時延

圖4所示為節點緩存對平均端到端時延的影響。由圖可知，隨著節點緩存不斷增加，3種算法的平均端到端時延也在變大，而ECRA的平均端到端時延要優于其他兩種算法。這是因為ECRA通過偵聽判斷通信范圍重疊區域內節點發送的矢量信息，獲知被偵聽節點中是否存在節點重要度更高的鄰居節點，若有，則將消息發送給被偵聽的節點，由該節點將消息轉發給其節點重要度更高的鄰居節點，使消息更快地到達與目的節點相遇概率更高的節點，從而降低了消息傳輸所消耗的時間，相比其他兩種算法表現出了更低的時延特性。

圖4　節點緩存對平均端到端時延的影響

（3）消息轉發效率

圖5所示為節點緩存對消息轉發效率的影響。由圖可知，ECRA的消息轉發效率優于其他兩種算法，這是因為ECRA改進了節點重要度的計算，避免了將消息轉發給其他不必要的節點，降低了消息副本數，使消息轉發更加有效，改善了網絡的擁塞情況，進而提高了轉發效率。而其他兩種算法在限制消息副本數和減少不必要消息轉發上均存在不足，所以在消息轉發效率這個性能指標上要低于ECRA。

圖5　節點緩存對消息轉發效率的影響

（4）消息平均存儲時間

圖6所示為節點緩存對消息平均存儲時間的影響。由圖可知，ECRA的消息平均存儲時間在3種算法中是最小的，這是因為ECRA對RADR做了改進，在消息傳遞時充分利用到目的節點重要度較高的節點轉發消息，在相對短的時間內把消息投遞給了目的節點，縮短了消息的存儲時間。

圖6　節點緩存對消息平均存儲時間的影響

4 結束語

本文針對RADR存在的問題，提出了一種ECRA，該算法提出連通拓撲圖節點偵聽機制，并改進節點重要度計算公式。仿真結果表明，ECRA較RADR及其他對比算法表現出了更好的消息傳輸成功率、轉發效率和更低的傳輸時延、平均存儲時間。

［1]熊永平，孫利民，牛建偉，等.機會網絡［J］.軟件學報，2009，20（1）：124-137.

［2]Wu J，Wang Y.Opportunistic Mobile Social Networks ［M］.Boca Raton：CRC Press，2014：256-266.

［3]Abdelkader T，Naik K，Nayak A，et al.SGBR：A Routing Protocol for Delay Tolerant Networks Using Social Grouping［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（12）：2472-2481.

［4]Wang L，Geng X.A community-driven hierarchical message transmission scheme in opportunistic networks［J］.Smart Computing Review，2011，1（1）：85-94.

［5]Moreira W，Mendes P，Sargento S.Opportunistic Routing Based on Daily Routines［C］//Proc of the IEEE International Symposium on Wireless，Mobile and Multimedia Networks 2012.San Francisco，US：IEEE，2012：1-6.

［6]Hui P，Yoneki E，Chan S Y，et al.Distributed Community Detection in Delay Tolerant Networks［C］// Proc of ACM/IEEE international workshop on Mobility in the evolving internet architecture 2007.New York，US：ACM Press，2007：716-722.

［7]Keranen A，Ott J，Karkkainen T.The ONE simulator for DTN protocol evaluation［C］//Proc of the International Conference on Simulation Tools and Techniques 2009.Brussels，Belgium：IEEE，2009：55-59.

An Efficient Community-based Routing Algorithm in Opportunistic Social Networks

REN Zhi，HUANG Xi-kai，TAN Yong-yin
（Chongqing Key Laboratory of Mobile Communication Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

To solve the problems of high transmission delay and low forwarding efficiency in the Routing Algorithm based on Daily Routines（RADR）in opportunistic social networks，an Efficient Community-based Routing Algorithm is proposed （ECRA）.The algorithm only selects the neighbor nodes which are in the same community with message destination node to calculate the node’s important degree.The algorithm uses topological connections to intercept the encounter node.If there exists node which has higher node’s importance than the encounter nodes neighbor，the message is transmitted to the encounter node neighbor nodes by the encounter node.Theoretical analysis and simulation results show that ECRA outperforms existing RADR and the correlation algorithms in terms of delivery ratio，average end-end delivery delay，relay ratio and average storage time.

opportunistic social networks；routing algorithms；communities；important degree；interceptionmechanism

TP393

A

1005-8788（2016）02-0063-04

10.13756/j.gtxyj.2016.02.020

2015-12-07

國家自然科學基金資助項目（61379159）；重慶市自然科學基金資助項目（cstc2012jjaA40051）

任智（1971-），男，四川內江人。教授，博士，主要研究方向為寬帶無線移動通信網絡及網絡仿真技術。

黃希凱，碩士研究生。E-mail：413575446@qq.com