基于鏈路效能社會DTN網絡的路由算法

王志海 高雪瑤

摘 要：數據在網絡中的傳輸需要網絡協議的保障，同時網絡協議的設計也需要結合通信的環境特征。TCP/IP協議設計的相關假設在有線網絡或者節點間連接狀況良好的無線網絡中可以實現。在某些環境惡劣的受限通信場景中，TCP/IP協議體系難以完成數據傳輸的任務。為了滿足多種需求、隨時接入及不限地域的通信需要，引入容遲網絡（DTN，Delay Tolerant Network）的概念。社會DTN網絡通過無線連接，節點間的連接效能并不相同，對鏈路的性能進行評價，并作出定量分析，能夠指導數據在網絡中的傳輸。設計了基于鏈路效能的社會DTN網絡路由算法——LABR。通過ONE平臺仿真驗證，對性能進行分析，并與現有路由算法進行對比。

關鍵詞：DTN;社會網絡;鏈路效用;ONE

DOI：10.15938/j.jhust.2020.01.013

中圖分類號： TP305

文獻標志碼： A

文章編號： 1007-2683（2020）01-0086-07

Abstract：Data transmission in the network rely on network protocols， while the design of network protocols also require accommodation with the communication environmental characteristicsThe design of TCP/IP protocol is based on wired network or wireless network nodes which are well connectedHowever， in some harsh challenged communication scenario， TCP / IP protocol system is difficult to complete the task of data transmissionIn order to meet a variety of communication needs anytime and anywhere， DTN（Delay Tolerant Network） emergedDTN social network is connected in wireless way， and the activity of connection between nodes is differentThrough evaluation of the activity of the link， quantitative analysis can guide the data transmission in the networkBased on this， a new routing algorithm named Link Activity Based Routing（LABR） is proposedThe performance of LABR is analyzed and compared with other routing algorithms in Opportunistic Network Environment（ONE）-Keywords：DTN; social network; link activity; ONE

0 引 言

科學技術，特別是集成電路，無線通信等領域的發展與進步，使得傳統笨重低效的計算機設備向便攜高效發展，設備間連接也呈現由有線向無線發展趨勢[1]。利用無線電磁波等作為信息載體，將電腦、手機等無線便攜設備通過無線網關等和地面Internet網絡連接，構成覆蓋更廣的無線移動網絡，完成數據全天候廣覆蓋的傳輸任務。圖1為無線移動網絡與有線網互聯示意圖。

為了滿足多種需求、隨時接入及不限地域的通信需求，容遲網絡（DTN，delay tolerant network）的概念應運而生[2]。DTN由Fall等于2003年提出，并得到了廣泛的關注。由于網絡環境的限制，DTN網絡采取了異步數據轉發的方式。同時將消息以“存儲-等待-轉發”的方式在DTN網絡中的傳輸，保證數據在復雜多變網絡中的可靠性及有效性[3]。消息在網絡中的保管權轉移和確認有相應的流程保證，防止數據在網絡傳輸過程中出現丟失的情況。DTN在應用層和傳輸層之間引入束層（bundle layer），以實現不同區域局部網絡的互聯互通[4]。

DTN的主要研究機構是DTN研究組。該組織致力于完善DTN結構設計和相關協議的規范，并且發布了一系列的協議草案。其中端到端的束層協議（BP，bundle protocol）[5]，規范了消息（bundle）傳輸過程中相關抽象服務;點到點的Licklider傳輸協議（LTP，licklider transmission protocol）[6]，利用重傳機制在長時延高誤碼率鏈路中保障消息的可靠性。此外還有約20個DTN相關的協議草案，包括安全[7]、路由[8]和BP擴展等方向。

目前DTN網絡已開展相關實驗并應用于眾多場景。在深空通信中，DTN為星際互聯網（IPN，interPlanetary internet）的實現提供了可能的解決方案[9]。IPN為美國國家航空航天局（NASA，mational aeronautics and space administration）提出，計劃連接宇宙空間中的中繼衛星、星球表面的探測網，建立星際間的“Internet網絡”。IPN主要包括行星表面網絡、行星際網絡及地面網絡等[10]。在2008年的“深度撞擊計劃”完成DTN協議下的數據傳輸，初步實現了宇宙空間的數據傳輸功能[11]。圖2為IPN網絡組成示意圖。

在文[26]提出基于小世界的SimBet路由算法。中心性計算不需要對整個網絡拓撲，只要求本地相關信息，選取中介中心性衡量。節點間相似性通過兩節點鄰居節點中相同節點數目衡量。SimBet路由算法利用節點間預估計的中介性和相似性選擇中繼節點，能夠達到和傳染病路由相似的性能，但減小了網絡開銷。為了簡化計算，社會網絡圖用矩陣的形式描述。連接矩陣A中的每個元素Aij表示節點i和節點j之間的連接關系。中介中心性為矩陣A2[1-A]ij中元素和的倒數。由于節點間的連接是雙向的，連接矩陣為對稱陣，故僅需要考慮對角線上方的非零元素。相似性為連接矩陣中非零相等的行向量的個數。在路由計算時，相對于m節點，選取n節點作為目的為d節點的消息中繼的評價效用函數為：

SimBetUtiln（d）=αSimUtiln（d）+βBetUtiln（1）

其中：SimUtiln（d）=Simn（d）Simn（d）+Simm（d），BetUtiln=BetnBetn+Betm。

在文[27]提出利用社會網絡固有特性設計路由算法。文中提出兩種社會和結構衡量指標：中心性和社區。社區檢測采取k-clique算法，即兩節點共有k-1個相同節點屬于同一社區。中心性通過該節點作為中繼節點的次數。在社會網絡中，節點間的連通性能不僅具有無線網絡中相關特性，還表明了節點間的社會關系。兩節點間鏈路持續時間越長，節點關系越緊密。然而通過現實觀察我們可以發現，簡單的統計鏈路持續時間并不能精確的反應節點間的關系，需要對通過連接時間對鏈路的效能進行量化，持續時間越長的鏈路效能越高。以鏈路持續時間長度t為自變量的量化函數f（t）需要具有以下性能：

1）鏈路持續時間為0效用為0，即f（0）=0;

2）數據的傳輸依賴于鏈路，即在（0，+∞）區間內f（t）>0;

3）持續時間越長的鏈路具有更高的效能，即在（0，+∞）區間內f′（t）>0;

基于此，本文中選取常見的指數型函數f（t）=b·eat-1，a，b>0作為鏈路效能的量化函數。圖7為鏈路效用量化函數示意圖。

3 社會網絡路由仿真分析

仿真驗證的實現需要仿真平臺的支持，在本文中選取ONE（opportunistic network environment）[28]。該仿真平臺由芬蘭赫爾辛基工業大學設計，可以用于DTN網絡中節點移動模型、路由傳輸等方向的仿真。軟件由JAVA編寫，開源性好，擴展性強。

3-1 消息生存時間的影響

仿真中，設置節點存儲空間為50Mb，傳輸速率為600Kbps，消息大小為600Kb，生存時間為2至6天。消息投遞概率、投遞延遲和網絡開銷如圖9所示。

在圖9（a）中可以看出，隨著消息的生存時間增加，數據的投遞延遲增大。這主要是減小消息的生存時間，使得長時間在網絡中保存的數據被刪除，整體消息的時延減小。同時傳染病路由延遲小于LABR路由，兩者整體趨勢大致相同。在圖9（b）中，由于傳染病路由是將消息無差別的傳輸至每一個相遇的節點中，相對于LABR路由網絡開銷過大，網絡負載較重，增加了節點數據處理量，造成大量資源的浪費。在圖9（c）中，生存時間的增加使得消息有足夠的時間完成在網絡中的傳輸。然而當生存時間大于4天之后，消息的投遞概率趨于穩定。以上分析可以得出，LABR路由在投遞概率和投遞延遲指標上和傳染病路由有相似的性能，但降低了網絡中的開銷。同時社會網絡中消息的生存時間對傳染病路由和LABR路由的消息投遞概率、投遞延遲和網絡開銷有較大影響，需要針對具體數據傳輸要求合理設置。

3-2 消息生存時間的影響

仿真中，設置節點存儲空間為50Mb，消息大小為600Kb，生存時間為4天傳輸速率為0-2至1-8Mbps，。消息投遞概率、投遞延遲和網絡開銷如圖10所示。

在圖10（a）中可以看出，隨著節點傳輸速率的增加，兩種路由算法下數據的投遞延遲基本保持不變，傳染病路由延遲小于LABR路由。在圖10（b）中，傳染病路由的網絡開銷大于LABR路由。在圖10（c）中，傳染病路由消息投遞概率略大于LABR路由，兩者的投遞概率在節點傳輸速率為0-2至1-8Mbps的情況下基本保持不變。這表明，社會網絡中節點的傳輸速率對傳染病路由和LABR路由的消息投遞概率、投遞延遲和網絡開銷影響較小。

4 結 論

本文主要對設計的LABR路由算法進行了仿真驗證。仿真基于ONE平臺，通過對相應程序的修改，搭建了合理的仿真場景。通過和傳染病路由的對比，LABR路由在投遞概率和投遞延遲指標上和傳染病路由有相似的性能，但降低了網絡中的開銷。同時社會網絡中消息的生存時間對傳染病路由和LABR路由的消息投遞概率、投遞延遲和網絡開銷有較大影響，需要針對具體數據傳輸要求合理設置，而節點的傳輸速率影響較小。

參 考 文 獻：

[1] RAPPAPORT T S. Wireless Communications： Principles and Practice[M]. New Jersey： Prentice Hall PTR， 1996.

[2] BURLEIGH S， HOOKE A， TORGERSON L， et al. Delay-tolerant Networking： An Approach to Interplanetary Internet[J]. Communications Magazine， IEEE， 2003， 41（6）： 128.

[3] 張艷霞，尹佳鑫，蒙高鵬，等.一種基于廣域測量信息的在線同調分群方法[J].電機與控制學報，2019，23（5）：10.

ZHANG Yanxia， YIN Jiaxin， MENG gaopeng， et al. Method of Online Recognition of Coherent Generators Based on Wide Area Information[J]. Electric Machines and Control， 2019， 23（5）： 10.

[4] BURLEIGH S. Interplanetary Overlay Network： An Implementation of the DTN Bundle Protocol[C]//Consumer Communications and Networking Conference， 2007. CCNC 2007. 4th IEEE. 2007： 222.

[5] 朱霄珣，徐博超，焦宏超，等.遺傳算法對SVR風速預測模型的多參數優化[J].電機與控制學報，2017，21（2）：70.

ZHU Xiaoxun，XU Bochao，JIAOHongchao，et al. Windspeed Prediction Mettiod Based on SVR and Multi-parameter Optimization of GA [J]. Electric Machines and Control， 2017， 21（2）： 70.

[6] RAMADAS M， BURLEIGH S， FARRELL S. Licklider Transmission Protocol-motivation[J]. IETF Request for Comments RFC， 2008， 5326.

[7] FARRELL S， CAHILL V. Security Considerations in Space and Delay Tolerant Networks[C]//Space Mission Challenges for Information Technology， 2006. SMC-IT 2006. Second IEEE International Conference on. IEEE， 2006： 8 pp.38.

[8] 任立偉，班曉軍，吳奮，等.二自由度飛行姿態模擬器的模糊強化學習控制[J].電機與控制學報，2019，23（11）：127.

REN Liwei， BAN Xiaojun， WU Fen， et al. Fuzzy Learning Controller Design of a 2-D of Flight Attitude Simulator[J]. Electric Machines and Control， 2019， 23（11）： 127.

[9] 葉建設， 宋世杰， 沈榮駿. 深空通信 DTN 應用研究[J]. 宇航學報， 2010（4）： 941.YE Jianshe， SONG Shijie， SHEN Rongjun. Research of Deep Space Communication DTN Application[J]. Electric Machines and Control， 2010（4）： 941.

[10]AKYILDIZ I F， AKANB， CHEN C， et al. InterPlaNetary Internet： State-of-the-art and Research Challenges[J]. Computer Networks， 2003， 43（2）： 75.

[11]林闖， 董揚威， 單志廣. 基于 DTN 的空間網絡互聯服務研究綜述[J]. 計算機研究與發展， 2014， 51（5）： 931.LIN Chuang， DONG Yangwei， SHAN Zhiguang. Research on Space Internetworking Service Based on DTN[J]. Journal of Computer Research and Development， 2014， 51（5）： 931.

[12]張振京， 金志剛， 舒炎泰. 基于節點運動預測的社會性DTN高效路由[J]. 計算機學報， 2013， 36（3）： 626.ZHANG Zhenjing， JIN Zhigang， SHU Yantai. Efficient Routing in Social DTN Based on Nodes′ Movement Prediction[J]. Chinese Journal of Computer，2013， 36（3）： 626.

[13]郭航， 王興偉， 黃敏， 等. 容延容斷網絡研究及進展[J]. 計算機科學， 2010， 37（11）： 12.GUO Hang， WANG Xingwei， HUANG Min， et al. Research on Delay/disruption Tolerant Networks[J]. Computer Science，2010， 37（11）： 12.

[14]李蘭英，劉昌東.一種無線傳感器網絡路由協議LEACH的改進算法[J].哈爾濱理工大學學報，2015，20（2）：75.LI Lanying; LIU Changdong. An Improved Algorithm of LEACH Routing Protocol in Wireless Sensor Networks[J].Journal of Harbin University of Science and Technology，2015，20（2）：75.

[15]宋立新，戴赫.基于蟻群算法的WSN路由協議研究[J].哈爾濱理工大學學報，2014，19（6）：88.SONG Lixin， DAI He. Research on WSN Routing Protocol Based on Ant Colony Algorithm[J].Journal of Harbin University of Science and Technology，2014，19（6）：88.

[16]JAIN S， FALL K， PATRA R. Routing in a Delay Tolerant Network[M]. ACM， 2004.

[17]MERUGU S， AMMAR M H， ZEGURA E W. Routing in Space and Time in Networks with Predictable Mobility[J]. 2004.

[18]VAHDAT A， BECKER D. Epidemic Routing for Partially Connected ad Hoc Networks[R]. Technical Report CS-200006， Duke University， 2000.

[19]GROSSGLAUSER M， TSE D. Mobility Increases the Capacity of Ad-hoc Wireless Networks[C]//INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE， 2001， 3： 1360.

[20]TCHAKOUNTIO F， RAMANATHAN R. Tracking Highly Mobile Endpoints[C]//Proceedings of the 4th ACM international workshop on Wireless mobile multimedia. ACM， 2001： 83.

[21]LINDGREN A， DORIA A， SCHELN O. Probabilistic Routing in Intermittently Connected Networks[J]. ACM SIGMOBILE mobile computing and communications review， 2003， 7（3）： 19.

[22]李巖，袁安娜，柳培新.一種改進的ZigBee網絡能量均衡簇樹路由算法[J].哈爾濱理工大學學報，2013，18（5）：56.LI Yan， YUAN Anna， LIU Peixin. Improved Energy-balanced Cluster Tree Routing Algorithm for ZigBee Network[J]. Journal of Harbin University of Science and Technology，2013，18（5）：56.

[23]CHEN Z D， KUNG H T， VLAH D. Ad Hoc Relay Wireless Networks Over Moving Vehicles on Highways[C]//Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing. ACM， 2001： 247.

[24]張振京， 金志剛， 舒炎泰. 基于節點運動預測的社會性 DTN 高效路由[J]. 計算機學報， 2013， 36（3）： 626.ZHANG Zhenjing， JIN Zhigang， SHU Yantai. Efficient Social DTN Routing Based on Node Motion Prediction[J]. Chinese Journal of Computers，2013， 36（3）： 626.

[25]HUI P， CROWCROFT J. How Small Labels Create Big Improvements[C]//Pervasive Computing and Communications Workshops， 2007. PerCom Workshops′ 07. Fifth Annual IEEE International Conference on. IEEE， 2007： 65.

[26]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. ACM， 2007： 32.

[27]HUI P， CROWCROFT J， YONEKI E. Bubble Rap： Social-based Forwarding in Delay-tolerant Networks[J]. Mobile Computing， IEEE Transactions on， 2011， 10（11）： 1576.

[28]陳淵. 延遲容忍網絡中基于社會屬性的路由算法研究與設計[D]. 上海：華東師范大學， 2013.

（編輯：溫澤宇）