基于链路效能社会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网络组成示意图。 　　本文介绍了网络社会性的基本概念，基于社会的路由策略。通过对无线连接的分析，提出基于连接性能的社会DTN路由算法。分析了社会DTN网络中的路由算法，结合链路效能和社区检测算法提出了LABR。主要对LABR算法性能进行仿真验证，并对仿真参数的影响进行分析。
　　1 延迟容忍网络
　　DTN协议体系结构具有和TCP/IP协议体系类似的分层结构，如图3所示。图中网络中各个子层均有相对应的协议实现本层的功能，并为顶层及底层协议提供数据接口[13]。
　　DTN协议不仅考虑了链路中断对网络性能的影响，而且提供了处理异构网络的框架。Internet网络模型通过要求每个节点使用一个网络层标示符（IP地址）、相同的数据包格式、在连通的拓扑结构中计算路由实现网络异构连接。DTN中通过使用命名、分层、打包和硬盘存储，并在传输层之上增加束层以完成异构部分的互联。图4为束层网络异构示意图。由于DTN網络中包含多种不同的网络协议（TCP/IP，raw Ethernet等），DTN中定义汇聚层（CLAs，Convergence Layer Adapters）将束层协议数据单元（bundle）传输至底层协议[14]。
　　传统路由是在网络持续连接、较低的传播时延和极低的丢包率的条件下设计的。然后在数据资源受限的DTN网络中上述条件并不满足，需要针对恶劣的通信环境设计新的数据传输路径选择机制和算法。目前研究人员已经提出的路由设计方案分成两类：基于确定或可预测拓扑路由和基于统计或时变拓扑的路由[15]。两类类均包含众多路由算法，并有不同的网络假设。
　　1-1 确定或可预测拓扑路由
　　确定或可预测拓扑路由方案是基于节点未来的移动轨迹和连接状况已知或者能够预测，在路由计算的时刻网络拓扑结构可获取。典型的确定或可预测拓扑路由有：
　　1）基于数据库路由：在文[16]提出构建网络拓扑和流量特性的数据库，以此完成数据路由传输。根据所能获取的网络特征程度，将数据库分成四种类型：连接统计数据库、连接数据库、队列数据库和流量数据库。连接统计数据库包含节点间连接的统计信息，例如平均连接间隔时间;连接数据库包含网络中任意两节点之间的连接信息，等同于获取了DTN网络中的时变连接图;队列数据库包含任意时刻任意节点的存储队列信息，可用以拥塞节点的路由计算;流量数据库包含目前和未来一段时间内网络流量特征。基于不同数据库，作者将DTN中路由方案进行分类，如全特征可知的线性编程方式和部分特征可知的改进迪杰斯特拉算法等。图5为获取网络特征程度和路由方案性能关系示意图。
　　2）时空图路由：在文[17]假设网络特性在时间间隔T内可知或可预测，而不是在整个时间段内。网络拓扑的动态性通过时空图来描述，在时空路由表中的当前和未来临近节点中选取下一跳节点。和传统路由表不同的是，时空路由表包含消息目的节点和消息达到时间。选取动态计算最短路径减小数据在传输过程的延迟。图6为节点间联通关系和对应的时空图。
　　1-2 统计或时变拓扑的路由
　　统计或时变拓扑的路由方案是基于网络的行为是随机的，数据传输路径的选取和时间空间有关。最简单的方式是将消息发送给所有连接的节点，此外其他路由方案和连接历史信息和移动特性等。
　　1）传染病类型路由：传染病路由假设对网络中节点的移动特性和拓扑结构完全未知，在文[18]提出了将消息泛洪传输至所有临近节点中，使得所有消息在网络中所有节点上均匀分布。该算法要求网络中节点具有足够大的存储空间，通过节点的移动将消息从源节点传输至目的节点。由此每个消息只能进过两跳传输，从而减小网络中开销。在文[20]提出将消息传输至和目的节点接触过的中继节点中。这利用了在移动网络中，消息的目的节点任然可能处于选取的中继节点的邻域内。
　　2）基于估计型路由：基于估计型路由估计计算当前连接中能够使消息到达目的节点的概率，并选取最高值作为下一跳节点。根据估计得出的概率，节点决定继续存储该消息并等待未来更高概率的链路，或者将消息转发至概率最高的节点。在文[21]提出PROPHET概率路由。该路由算法首先估计预测投递概率矩阵，当节点相遇时进行交互，并将消息传输至具有和目的节点相遇概率更高的节点中。在文[22]提出了结合异步和同步消息传输模式的CAR路由算法。在同步模式中，当前节点和消息目的节点间存在可用连接，在异步模式中则不存在，消息需要存储。当同步模式不可实施时，CAR算法利用卡尔曼滤波方式处理离散事件序列，预测能够将消息传输至目的节点概率最高的中继节点。该算法在节点有限存储空间网络中仍能保持较高性能。
　　3）基于移动模型路由：基于移动模型路由假设网络中的节点按照已知的移动模型运动，由此估计不同节点和消息的目的节点相遇概率。在文[23]对高速公路上的节点运动进行建模。当车流量稀少时，网络各个部分处于分离状态。传输中继节点的选取借助于车辆移动轨迹可预测性。消息采取存储转发的模式，逐跳向目的节点方向传输。根据消息允许在中继节点存储时间长度，传输方式分为两种：保守方式和积极方式。
　　2 社会网络路由算法
　　在地面网络中无线设备例如智能手机、笔记本电脑等的携带者大多数为个体人。节点的运动和节点间的连接具有明显的社会属性，节点间信息的传输会呈现出社会学特征：小世界聚集现象[24]。本节主要介绍网络社会性的基本概念，基于社会的路由策略。通过对无线连接的分析，提出基于连接性能的社会DTN路由算法。
　　2-1 社会DTN网络路由
　　社会网络中的节点间断连接、网络拓扑结构时变等特性，是典型的DTN网络。针对网络具有的社会属性，研究人员提出了相应的路由算法。
　　在文[25]提出LABEL路由算法，利用社区检测能够增加数据在口袋交换网络（PSN，pocket switched network）中投递概率，减小传输成本。通过Intel iMote设备收集节点间的连接信息和移动统计特性，每个节点均具有标签，能够告知其他节点该节点所处节点集群信息。消息在转发的过程中，节点会选择与消息目的节点相同标签的节点作为中继。 　　在文[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， AKAN B， 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.
　　（编辑：温泽宇）
转载注明来源:https://www.xzbu.com/8/view-15210255.htm