暫態社區感知的ICWN數據轉發機制

杜劍, 夏元軼, 趙俊峰, 王崢, 王鶴

（1. 北京智芯微電子科技有限公司，北京 100192；2. 國網江蘇省電力公司信息通信分公司，江蘇 南京 210024）

暫態社區感知的ICWN數據轉發機制

杜劍1, 夏元軼2, 趙俊峰2, 王崢1, 王鶴1

（1. 北京智芯微電子科技有限公司，北京 100192；2. 國網江蘇省電力公司信息通信分公司，江蘇 南京 210024）

為了有效解決間斷連接無線網絡中的數據轉發問題，提出了一種暫態社區感知的數據轉發機制，運用半馬爾可夫鏈模型描述節點在多個地理位置間的轉移過程，預測節點在未來相遇的時間概率分布，確定節點相遇位置和時間，為下一跳中繼節點的選擇提供了理論依據。實驗數值表明，與傳統算法相比，所提機制能有效提高節點相遇預測的準確性，在數據成功投遞率和傳輸時延等性能上都有較大的提升。

間斷連接無線網絡；數據轉發；暫態社區；相遇預測；半馬爾可夫模型

1 引言

間斷連接無線網絡（intermittentl connected wireless network，ICWN）是指不需要源節點和目的節點在轉發數據前建立完整的端到端路徑，利用節點移動帶來的相遇機會，以更加靈活的“存儲—攜帶—轉發”的協作方式逐跳進行傳輸[1]。該網絡具有自組織、節點稀疏、間歇連接、資源受限、拓撲動態變化等特性[2]。在這種復雜多變的組網環境下，設計能夠滿足間斷連接無線網絡通信需求的數據轉發機制成為研究間斷連接無線網絡的關鍵問題[3]。

在間斷連接無線網絡中，源節點和目標節點之間并不依靠始終連通的完整鏈路進行數據的傳輸[4]，且源節點與中繼節點之間的連接也隨著時間的變化而不斷變化，任意成對節點間的通信鏈路都隨時會遭遇斷裂[5]，這種間斷性的端到端連接和不斷變化的網絡拓撲使得傳統移動自組織網絡的數據轉發機制難以直接應用到間斷連接無線網絡中[6]。

目前，國內外研究人員已經提出了一些應用于間斷連接無線網絡的數據轉發機制。Becker等人[7]提出了傳染路由（epidemic routing）機制，其核心思想是源節點將數據復制、轉發給任何與其相遇的節點，一定程度上提高了數據的傳輸效率，但洪泛型的數據轉發機制需要占用大量的緩存空間，消耗大量能量，而節點自身資源很有限，導致該機制分組丟失率較高。社會學的主要研究內容是人類在時間、空間內的交互作用，基于社會理論，Hui等人[8]提出了一種名為多標簽的數據轉發機制，將網絡劃分為若干社區，節點在轉發數據時選擇通信范圍內與自己同社區的節點作為下一跳節點，但當源節點與目的節點所屬社區距離較遠時，數據成功投遞率不高。為此，參考文獻[9]中提出Bubble-Rap算法，在選擇中繼節點時考慮節點及節點所在社區的活躍度，根據不同需求選擇下一跳節點。針對間斷連接無線網絡的分裂性特點及節點移動行為的趨同性，參考文獻[10]提出SimBet機制，在選擇中繼節點時綜合考慮節點向心度和相似度，節點向心度描述兩節點之間的依賴程度，相似度表征節點移動行為的趨同性，根據節點向心度和相似度評估數據轉發效用值，以此選擇下一跳節點。上述機制中，節點轉發數據時僅選擇未來與目的節點相遇概率高或效用值大的節點作為下一跳節點，其主要關注的是未來兩個節點能否相遇，而沒有考慮節點相遇的時間和地理位置。而實際情況中，節點不會無休止地緩存數據，且數據自身存在時效性，因此設計數據轉發機制時既要保證數據的有效傳遞，也要考慮數據的時效性。

針對上述問題，本文提出了一種暫態社區感知的數據轉發機制（transient community awared data forwarding mechanism，TCDFM），運用半馬爾可夫模型，準確預測節點未來相遇的時間和地理位置，更加合理地選擇下一跳中繼節點，在保障數據成功投遞率的同時，降低數據傳輸時延，保證數據的時效性。

2 網絡環境

間斷連接無線網絡中節點的社會屬性使節點的移動具有一定規律性[11]，但移動軌跡并不固定，網絡中節點以一定次序在幾個地理位置之間進行訪問，節點在到達目標位置后，以一定的概率選擇在該位置滯留一定時間或者直接離開。本文假設在校園場景下，地理位置分別為教室、食堂、圖書館等建筑，節點為持有短距離無線通信設備的學生和老師。節點各自遵循自己的日程表進行移動。其中，社會屬性作為節點的內在屬性，則會在很大程度上影響節點的移動模式，呈現出某時段在有限移動范圍內高度活躍，在另一時段移動相對遲緩，將這種特性定義為節點的暫態特性。通過進一步研究發現，節點的暫態特性主要表現在時間和地理位置兩個方面，節點往往趨向于在特定時間區間的某一地理位置聚集。那么在ICWN中，若干節點在某個時間區間內常駐在某個明確的地理范圍內，且在此范圍內的節點保持緊密的聯系，從而可以將這些節點進行聚合形成穩定連通的 ICWN子網，將其稱為暫態社區（temporal community，TC）。

為了構建暫態社區，節點為數據設定一個TTL值，TTL值到期，節點自動將數據刪除。具體數據轉發過程如下：當一個節點需要轉發數據時，首先篩選鄰居節點中未來能與目標節點相遇的節點作為候選中繼節點；然后，節點執行本文預測算法，預測各候選中繼節點與目標節點的相遇時間，并與數據的TTL值比對，淘汰在TTL到期前無法與目標節點相遇的候選中繼節點；最后，計算候選中繼節點中與目標節點的相遇概率，選取相遇概率最大的節點作為下一跳節點，如果候選中繼節點與目標節點相遇的概率值均小于當前節點，則數據繼續緩存在本地節點。圖 1為校園場景下本文數據轉發機制示意，節點 A需要轉發數據給節點 E，當前時刻節點A與室友節點B和節點C同處于宿舍內。基于節點歷史移動信息，節點 A預測到在TTL到期之前，相比于節點C，節點B更有可能與節點E相遇，所以節點A將數據轉發給節點B。節點B不久后與節點E相遇，進而將數據轉發給節點E。

圖1 校園場景下本文數據轉發機制示意

3 節點行為預測

3.1 節點歷史行為信息交互

為了準確預測節點的移動行為，網絡中的每個節點都需要盡可能地了解其他節點的歷史移動信息。本文將節點的移動信息設計為一個5元組其中，P是節點在不同地理位置之間的轉移概率矩陣，SP是節點在各個位置的滯留時間概率分布，T是節點地理位置變化的起始時間，ID和LocID分別是節點 ID和節點所在位置的ID。當兩個節點相遇時，節點間會交換歷史移動信息。節點接收到其他節點的歷史移動信息后，通過5元組內的T值判斷數據的新舊，然后將較新的數據在本地緩存。

若節點S想要轉發數據給節點D，則首先查詢本地數據中節點 D 的歷史移動信息則節點 D在時間t時所處的位置由式（1）得到：

其中，Wt代表節點D在時間t的地理位置，L是地理位置集合。

3.2 行為參數評估

預測兩個節點的相遇時間和地理位置需要獲知兩個參數：地理位置轉移概率矩陣和滯留時間概率分布，兩個參數均由節點歷史移動信息獲知。

圖2 地理位置轉移示意

節點n當前位于地理位置i，隨后轉移到地理位置j，節點在位置i的滯留時間概率分布函數可以定義為：

當網絡達到穩定狀態時，移動歷史信息為滯留時間分布的計算提供依據。按照式(4)的方式計算＜k)：

3.3 節點狀態轉移概率評估

為了提高間斷連接無線網絡中暫態社區時空特征對節點移動行為預測的有效性，本文使用時間齊次的半馬爾可夫鏈模型模擬節點n的移動過程，該過程可以表示為()。節點所處的不同狀態用地理位置 ID表示，記作 L=1,2,3,…,l。一個節點在兩個地理位置之間的移動對應節點在馬爾可夫鏈中兩個狀態之間的轉移。假設不同狀態間的轉移概率具有馬爾可夫鏈的無記憶性，即節點n從狀態轉移到狀態的概率是獨立于狀態的，這個轉移行為僅與節點當前狀態相關。基于上述特點，隨機過程(符合標準的時間離散馬爾可夫鏈的特性。隨機變量表示節點n由狀態向轉移的時間，隨機變量（）描述了節點n在地理位置i的滯留時間。本文節點在某個地理位置的滯留時間并不包含節點在兩個狀態之間轉移所需要耗費的時間。

4 轉發決策

間斷連接無線網絡雖然是延遲可容忍網絡，但是數據具有時效性，超過時效的數據即使轉發到目標節點也沒有意義，而且在網絡中持續轉發、緩存時，數據也是對網絡資源的浪費。本文認為數據的最大可接受時延就是數據的生存時間TTL。令節點n表示源節點的鄰居節點，N是當前節點的所有鄰居節點的集合，d表示目標節點，選取與目標節點相遇概率最大的節點作為下一跳節點：

利用上述方法，選擇具有最高效用值的節點作為中繼節點轉發數據，即在未來的TTTL單位時間內與目標節點相遇概率最高的節點。如果所選的中繼節點未來與目標節點相遇的概率小于當前節點，則數據繼續緩存在當前節點，直至更優的中繼節點出現，或者待TTL值到期后將數據刪除。

5 仿真結果分析

本文采用間斷連接無線網絡環境 ONE[12]仿真平臺進行數據轉發策略性能驗證，并與典型的數據轉發機制Prophet及Bubble-Rap進行對比，以驗證所提出機制TCDFM的性能。仿真參數見表1。

表1 仿真參數設置

5.1 節點數量對數據轉發策略的影響

間斷連接無線網絡是典型的節點分布稀疏網絡，網絡中節點的數量直接影響節點相遇機會，最終影響數據轉發機制整體性能。因此，首先分析節點數量對不同數據轉發機制的影響，結果如圖1所示。

圖3 節點數量對數據成功投遞率的影響

圖4 節點數量對平均傳輸時延的影響

由圖3、圖4可以看出，隨著網絡中節點數量的增加，TCDFM和Bubble-Rap機制在數據成功投遞率上呈現平穩上升趨勢，相比前兩者，Prophet則呈現反向趨勢。TCDFM與兩種算法的數據傳輸時延均隨著節點數量的增加呈現下降趨勢。本文算法在數據成功投遞率和平均傳輸時延所呈現出的性能均是最優的，數據成功投遞率分別比Bubble-Rap算法和Prophet算法平均高出13.2%和17.9%，平均傳輸時延分別比 Bubble-Rap和Prophet平均低26.8%和37.3%。主要原因為隨著網絡中節點數量的增多，節點間相遇機會增加，為中繼節點的選擇提供了更多的選擇，明確了中繼節點進行數據投遞的目標，進而提高了數據成功投遞率。在Prophet算法中，隨著數據副本在網絡中大量分發，網絡資源被大量占用，導致基于相遇概率的多副本分發的 Prophet算法會進行大量的數據復制、轉發，抑制了副本的有效傳遞，降低了網絡性能，最終造成了數據傳輸時延較大。TCDFM 算法考慮了中繼節點能否在數據時效性內將數據轉發給目標節點，在中繼機會增多的同時，能夠挑選更優的中繼節點進行數據轉發，如果數據在有效時間內不能成功投遞，則立即刪除，避免資源浪費對其他數據的投遞產生影響，從而降低了數據的傳輸時延。

5.2 數據TTL值對數據轉發策略的影響

TTL表示網絡中數據的生存時長，不同的TTL值在一定程度上影響了網絡中待轉發數據的數量。因此，TTL值對數據轉發策略的性能和網絡的存續時間影響很大。圖5、圖6分別表示在不同TTL值下，不同算法的數據的成功投遞率和平均傳輸時延。

圖5 TTL值對數據成功投遞率的影響

由圖5、圖6中可以看出，隨著TTL值增加，3種路由算法的數據成功投遞率均先上升后下降，同時，隨著TTL值的增加，數據傳輸的平均時延

圖6 TTL值對平均傳輸時延的影響

隨之增加。本文 TCDFM 算法在數據成功投遞率上分別比Prophet算法和Bubble-Rap算法平均高出 12.3%、17.2%，而數據的平均傳輸時延則比Prophet算法和 Bubble-Rap算法分別低 19.6%、14.1%。主要原因為數據的 TTL值較小時，節點間還未產生相遇機會，數據就有可能被刪除，數據的成功投遞率會比較低。而當TTL值較大時，網絡中的數據會始終保存在節點的緩存空間中，即使數據成功投遞到目標節點，網絡中仍然包含大量數據副本，極大地浪費網絡資源，影響網絡的性能。因此，在TTL值增大的過程中，數據的成功投遞率會隨之增高，在達到峰值后，繼續增大TTL值就會造成網絡擁塞，數據的正常傳輸受阻，數據成功投遞率開始下滑，同時，平均傳輸時延增大。

6 結束語

為了實現間斷連接無線網絡中數據的高效可靠傳輸，本文提出了一種暫態社區感知的數據轉發機制，利用時間齊次的半馬爾可夫鏈模型進行節點相遇預測，確定兩個節點未來在指定時間指定位置的相遇概率。節點需要轉發數據時，從鄰居節點中篩選在TTL值到期之前與目標節點相遇的節點作為候選中繼節點，選擇各候選中繼節點中與目標節點相遇概率最大的節點作為下一跳中繼節點。仿真結果表明，與傳統路由機制相比，所提出的機制能夠在保證較高數據投遞率的同時，降低數據的傳輸時延，有效地提高網絡可靠性。

[1] WU D P, ZHANG H P, WANG H G, et al. Quality of protection(QoP)-driven data forwarding for intermittently connected wireless networks[J]. IEEE Wireless Communication, 2015,22(4): 66-73.

[2] WU D P, HE J, WANG H G, et al. A hierarchical packet forwarding mechanism for energy harvesting wireless sensor networks[J]. IEEE Communication Magazine, 2015, 53(8): 92-98.

[3] WU D P, WANG Y Y, WANG H G, et al. Dynamic coding control in social intermittent connectivity wireless networks[J].IEEE Transactions on Vehicular Technology, 2016, 65(9):7634-7646.

[4] WANG R Y, YANG H P, WANG H G, et al. Social overlapping community aware neighbor discovery for D2D communications[J]. IEEE Wireless Communications, 2016, 23(4): 28-34.

[5] FENG M, MAO S, JIANG T. Joint duplex mode selection,channel allocation, and power control for full-duplex cognitive femtocell networks[J]. Digital Communications and Networks,2015, 1(1): 30-44.

[6] WU D P, ZHANG P N, WANG H G, et al. Node service ability aware packet forwarding mechanism in intermittently connected wireless networks[J]. IEEE Transaction on Wireless Communications, 2016, 15(12): 8169-8181.

[7] BISTA B B. Improving energy consumption of epidemic routing in delay tolerant networks[C]//International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, July 6-8, 2016, Fukuoka, Japan. New Jersey: IEEE Press, 2016: 278-283

[8] SONG L, LI Y, FAN S, et al. Social-based multi-label routing in delay tolerant networks[C]//IEEE Fourth International Conference on Big Data and Cloud Computing, Dec 3-5, 2014, Sydney, Australia. New Jersey: IEEE Press, 2014: 402-407.

[9] GUPTA A, AGRAWAL A, NAGRATH P. Variant of BUBBLE rap forwarding algorithm for delay tolerant networks[C]//International Conference on Computational Techniques in Information and Communication Technologies, March 11-13, 2016, New Delhi, India. New Jersey: IEEE Press, 2016:63-68.

[10] SHRESTHA N, SASSATELLI L. Inter-session network coding-based policies for delay tolerant mobile social networks[J].IEEE Transactions on Wireless Communications, 2016, 15(11):7329-7342.

[11] 潘劍飛, 徐麗麗, 董一鴻. 動態社區演化研究進展[J]. 電信科學, 2017, 33(1): 24-33.PAN J F, XU L L, DONG Y H. Research progress of dynamic community evolution[J]. Telecommunications Science, 2017,33(1): 24-33.

[12] ODA T, ELMAZI D, SPAHO E, et al. A simulation system based on ONE and SUMO simulators: performance evaluation of direct delivery, epidemic and energy aware epidemic DTN protocols[C]//International Conference on Network-Based Information Systems, Sept 2-4, 2015, Taipei, China. New Jersey:IEEE Press, 2015: 418-423.

Transient community awared data forwarding mechanism for intermittent connected wireless network

DU Jian1, XIA Yuanyi2, ZHAO Junfeng2, WANG Zheng1, WANG He1
1. Beijing Smartchip Microelectronics Technology Co., Ltd., Beijing 100192, China 2. Information & Telecommunication Branch of State Grid Jiangsu Electric Porer Company, Nanjing 210024, China

In order to solve the problem of data forwarding in intermittent connected wireless network effectively, a transient community awared data forwarding mechanism for intermittent connected wireless network(ICWN) was proposed. Utilizing the semi-Markov chain model, the transfer process of nodes’s between multiple geographic locations was described and the time probability distribution of nodes’ encountering in the future was predicted, then the encountering time and locations could be obtained, which provided theoretical basis for the selection of next relay node. Experiment results show that the proposed mechanism can effectively improve the forecasting accuracy of nodes’ encounter and has a great improvement in the data delivery ratio and transmission delay.

intermittent connected wireless network, data forwarding, transient community, encounter forcasting,semi-Markov model

Science and Technology Project of State Grid (No.526800150007)

TP393

A

10.11959/j.issn.1000?0801.2017262

2017?07?20；

2017?08?31

國家電網公司科技基金資助項目（No.526800150007）

杜劍（1987?），男，北京智芯微電子科技有限公司中級工程師，主要研究方向為集成電路與傳感芯片在電力中的應用。

夏元軼（1988?），男，國網江蘇省電力公司信息通信分公司專職，主要研究方向為電力信息化。

趙俊峰（1974?），男，國網江蘇省電力公司信息通信分公司主任，主要研究方向為電力信息化。

王崢（1983?），男，博士，北京智芯微電子科技有限公司部門經理，主要研究方向為微電子與固體電子學。

王鶴（1982?），男，北京智芯微電子科技有限公司中級工程師，主要研究方向為無線網絡通信及無線傳感網通信技術應用。