基于鏈路效能社會(huì)DTN網(wǎng)絡(luò)的路由算法

王志海 高雪瑤

摘 要：數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸需要網(wǎng)絡(luò)協(xié)議的保障，同時(shí)網(wǎng)絡(luò)協(xié)議的設(shè)計(jì)也需要結(jié)合通信的環(huán)境特征。TCP/IP協(xié)議設(shè)計(jì)的相關(guān)假設(shè)在有線網(wǎng)絡(luò)或者節(jié)點(diǎn)間連接狀況良好的無(wú)線網(wǎng)絡(luò)中可以實(shí)現(xiàn)。在某些環(huán)境惡劣的受限通信場(chǎng)景中，TCP/IP協(xié)議體系難以完成數(shù)據(jù)傳輸?shù)娜蝿?wù)。為了滿足多種需求、隨時(shí)接入及不限地域的通信需要，引入容遲網(wǎng)絡(luò)（DTN，Delay Tolerant Network）的概念。社會(huì)DTN網(wǎng)絡(luò)通過(guò)無(wú)線連接，節(jié)點(diǎn)間的連接效能并不相同，對(duì)鏈路的性能進(jìn)行評(píng)價(jià)，并作出定量分析，能夠指導(dǎo)數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸。設(shè)計(jì)了基于鏈路效能的社會(huì)DTN網(wǎng)絡(luò)路由算法——LABR。通過(guò)ONE平臺(tái)仿真驗(yàn)證，對(duì)性能進(jìn)行分析，并與現(xiàn)有路由算法進(jìn)行對(duì)比。

關(guān)鍵詞：DTN;社會(huì)網(wǎng)絡(luò);鏈路效用;ONE

DOI：10.15938/j.jhust.2020.01.013

中圖分類號(hào)： TP305

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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 引 言

科學(xué)技術(shù)，特別是集成電路，無(wú)線通信等領(lǐng)域的發(fā)展與進(jìn)步，使得傳統(tǒng)笨重低效的計(jì)算機(jī)設(shè)備向便攜高效發(fā)展，設(shè)備間連接也呈現(xiàn)由有線向無(wú)線發(fā)展趨勢(shì)[1]。利用無(wú)線電磁波等作為信息載體，將電腦、手機(jī)等無(wú)線便攜設(shè)備通過(guò)無(wú)線網(wǎng)關(guān)等和地面Internet網(wǎng)絡(luò)連接，構(gòu)成覆蓋更廣的無(wú)線移動(dòng)網(wǎng)絡(luò)，完成數(shù)據(jù)全天候廣覆蓋的傳輸任務(wù)。圖1為無(wú)線移動(dòng)網(wǎng)絡(luò)與有線網(wǎng)互聯(lián)示意圖。

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

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

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

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

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

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

在文[27]提出利用社會(huì)網(wǎng)絡(luò)固有特性設(shè)計(jì)路由算法。文中提出兩種社會(huì)和結(jié)構(gòu)衡量指標(biāo)：中心性和社區(qū)。社區(qū)檢測(cè)采取k-clique算法，即兩節(jié)點(diǎn)共有k-1個(gè)相同節(jié)點(diǎn)屬于同一社區(qū)。中心性通過(guò)該節(jié)點(diǎn)作為中繼節(jié)點(diǎn)的次數(shù)。在社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)間的連通性能不僅具有無(wú)線網(wǎng)絡(luò)中相關(guān)特性，還表明了節(jié)點(diǎn)間的社會(huì)關(guān)系。兩節(jié)點(diǎn)間鏈路持續(xù)時(shí)間越長(zhǎng)，節(jié)點(diǎn)關(guān)系越緊密。然而通過(guò)現(xiàn)實(shí)觀察我們可以發(fā)現(xiàn)，簡(jiǎn)單的統(tǒng)計(jì)鏈路持續(xù)時(shí)間并不能精確的反應(yīng)節(jié)點(diǎn)間的關(guān)系，需要對(duì)通過(guò)連接時(shí)間對(duì)鏈路的效能進(jìn)行量化，持續(xù)時(shí)間越長(zhǎng)的鏈路效能越高。以鏈路持續(xù)時(shí)間長(zhǎng)度t為自變量的量化函數(shù)f（t）需要具有以下性能：

1）鏈路持續(xù)時(shí)間為0效用為0，即f（0）=0;

2）數(shù)據(jù)的傳輸依賴于鏈路，即在（0，+∞）區(qū)間內(nèi)f（t）>0;

3）持續(xù)時(shí)間越長(zhǎng)的鏈路具有更高的效能，即在（0，+∞）區(qū)間內(nèi)f′（t）>0;

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

3 社會(huì)網(wǎng)絡(luò)路由仿真分析

仿真驗(yàn)證的實(shí)現(xiàn)需要仿真平臺(tái)的支持，在本文中選取ONE（opportunistic network environment）[28]。該仿真平臺(tái)由芬蘭赫爾辛基工業(yè)大學(xué)設(shè)計(jì)，可以用于DTN網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模型、路由傳輸?shù)确较虻姆抡妗＼浖蒍AVA編寫，開源性好，擴(kuò)展性強(qiáng)。

3-1 消息生存時(shí)間的影響

仿真中，設(shè)置節(jié)點(diǎn)存儲(chǔ)空間為50Mb，傳輸速率為600Kbps，消息大小為600Kb，生存時(shí)間為2至6天。消息投遞概率、投遞延遲和網(wǎng)絡(luò)開銷如圖9所示。

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

3-2 消息生存時(shí)間的影響

仿真中，設(shè)置節(jié)點(diǎn)存儲(chǔ)空間為50Mb，消息大小為600Kb，生存時(shí)間為4天傳輸速率為0-2至1-8Mbps，。消息投遞概率、投遞延遲和網(wǎng)絡(luò)開銷如圖10所示。

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

4 結(jié) 論

本文主要對(duì)設(shè)計(jì)的LABR路由算法進(jìn)行了仿真驗(yàn)證。仿真基于ONE平臺(tái)，通過(guò)對(duì)相應(yīng)程序的修改，搭建了合理的仿真場(chǎng)景。通過(guò)和傳染病路由的對(duì)比，LABR路由在投遞概率和投遞延遲指標(biāo)上和傳染病路由有相似的性能，但降低了網(wǎng)絡(luò)中的開銷。同時(shí)社會(huì)網(wǎng)絡(luò)中消息的生存時(shí)間對(duì)傳染病路由和LABR路由的消息投遞概率、投遞延遲和網(wǎng)絡(luò)開銷有較大影響，需要針對(duì)具體數(shù)據(jù)傳輸要求合理設(shè)置，而節(jié)點(diǎn)的傳輸速率影響較小。

參 考 文 獻(xiàn)：

[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] 張艷霞，尹佳鑫，蒙高鵬，等.一種基于廣域測(cè)量信息的在線同調(diào)分群方法[J].電機(jī)與控制學(xué)報(bào)，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] 朱霄珣，徐博超，焦宏超，等.遺傳算法對(duì)SVR風(fēng)速預(yù)測(cè)模型的多參數(shù)優(yōu)化[J].電機(jī)與控制學(xué)報(bào)，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] 任立偉，班曉軍，吳奮，等.二自由度飛行姿態(tài)模擬器的模糊強(qiáng)化學(xué)習(xí)控制[J].電機(jī)與控制學(xué)報(bào)，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] 葉建設(shè)， 宋世杰， 沈榮駿. 深空通信 DTN 應(yīng)用研究[J]. 宇航學(xué)報(bào)， 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]林闖， 董揚(yáng)威， 單志廣. 基于 DTN 的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述[J]. 計(jì)算機(jī)研究與發(fā)展， 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]張振京， 金志剛， 舒炎泰. 基于節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的社會(huì)性DTN高效路由[J]. 計(jì)算機(jī)學(xué)報(bào)， 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]郭航， 王興偉， 黃敏， 等. 容延容斷網(wǎng)絡(luò)研究及進(jìn)展[J]. 計(jì)算機(jī)科學(xué)， 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]李蘭英，劉昌東.一種無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的改進(jìn)算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，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路由協(xié)議研究[J].哈爾濱理工大學(xué)學(xué)報(bào)，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]李巖，袁安娜，柳培新.一種改進(jìn)的ZigBee網(wǎng)絡(luò)能量均衡簇樹路由算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，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]張振京， 金志剛， 舒炎泰. 基于節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的社會(huì)性 DTN 高效路由[J]. 計(jì)算機(jī)學(xué)報(bào)， 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]陳淵. 延遲容忍網(wǎng)絡(luò)中基于社會(huì)屬性的路由算法研究與設(shè)計(jì)[D]. 上海：華東師范大學(xué)， 2013.

（編輯：溫澤宇）