MDCE路由算法的分析与改进
2021-01-15杨万鑫汪学明夏红红
杨万鑫 汪学明 夏红红
1(贵州大学计算机科学与技术学院 贵州 贵阳 550025) 2(凯里学院大数据工程学院 贵州 凯里 556011)
0 引 言
延迟容忍网络(Delay Tolerant Networks,DTN)使用“存储-携带-转发”的方式进行消息传递，于 2003年由Kevin Fall首次明确提出，其特点是高时延、移动性、资源受限、节点密度稀疏、网络拓扑结构频繁割裂，可能不存在一条源节点到目的节点的链路，而传统的TCP/IP路由协议无法满足DTN消息的传递要求。因此提高消息的投递率、降低消息的传输时延、减少网络负载率及资源消耗，成为当前DTN研究领域的主要研究课题[3-5]。目前DTN路由方案中一类为随机性路由方案，主要以Epidemic/Random spray方式[9]为代表；另一类是基于确定性的路由方案，例如基于树的方式[6]、修正的最短路径方法[7]、时空路由[8]等。
在实际环境如移动车载自组网络中，车必然沿着道路行走，只有在十字路口(或掉头)才会改变其移动方向。在动物迁徙过程中，受迁徙路线及群体的影响，会沿着道路或水源行走，只有在道路或水流分叉的时候才改变迁徙方向。因此节点移动方向的变化频率相对要低很多，具有更好的稳定性及可靠性，也避免了使用GPS时刻采集地理位置信息带来的资源消耗问题。另一方面，在多数DTN应用场景中，网络节点往往是沿着某一方向移动一段距离或者一段时间之后才会改变移动方向[9-11]，因此，利用中继节点一段距离之内仍然会按照原来既定方向移动的特点，可以定向引导和控制消息副本的传输方向。徐吉兴等[1]提出了MDCE路由算法，由于MDCE路由算法在网络负载率、丢包数仍然很高，会演化为泛洪形式的传播，这与L-C Epidemic、Epidemic情况类似，将会导致与以上两者同样高的负载率和缓存空间占用率，并且在实际的DTN环境中，由于条件及资源的限制及DTN特点，很难拥有六个或更多的节点。
因此，本文将对MDCE路由算法做进一步改进，使得在投递率不变或变化很小的情况下降低丢包数及网络负载率。
1 MDCE路由协议分析
1.1 MDCE下一跳节点的选择
在基于地理位置的DTN路由算法中，任意时刻节点只能获取一跳以内邻居节点的信息，且频繁获取位置信息会增加额外的资源消耗，同时还无法获取目的节点的信息。为了避免错过消息传递成功的机会，路由选取应更为慎重。MDCE是基于移动方向的中继节点选择算法，避免了节点过分依赖GPS的信息，利用节点移动的方向来提高消息传递的准确性。由于目的节点可能存在于源节点周围的任何方向。MDCE算法以当前节点Ni的移动方向作为参考方向，选择了左、左前、右、右前、左后和右后六个方向的相邻节点来复制消息副本，如图1所示。
图1 移动方向选择
1.2 MDCE路由算法描述
DTN中节点的缓存有限，有的节点只愿意转发与自己有社会关系的节点数据包[12]。因此MDCE路由算法使用消息经过的跳数C(M)、已存活时间L(M)、能够存活时间TTL作为优先级参考的参考标准。使用H(M)、T(M)分别表示跳数和已存活时间对优先级的作用大小；使用UP(M)表示最终的优先级。设消息经过跳数的门限值HOPthreshold=⎣log2NC」,NC为网络中的节点数量。H(M)、T(M)、UP(M)计算公式如下：
(1)
(2)
UP(M)=1-H(M)×β-T(M)×(1-β)
(3)
结合移动方向的选择和缓存管理策略，MDCE路由协议算法描述详见文献[1]。
1.3 存在问题
由于目的节点方向的不确定性，MDCE路由算法为了提高投递率，导致网络副本过多，存在如下问题：
1) 在实际的DTN环境中，由于环境条件及资源的限制，邻居节点很难达到六个及以上。
2) 当消息生存周期过长(超过30分钟)时，因为消息副本过多，高负载率降低了网络性能使得消息大量丢弃，丧失了最佳的消息传递机会，导致投递率快速下降。
3) 由于中继节点过多，将会转化为Epidemic路由算法，导致负载率高、缓存占用率高、消息副本过多。
4) 选择的下一跳中继节点的移动方向与当前节点去过方向相反，会使得消息副本又向传递来的方向传递，而来向区域已经存在较密集的消息副本，增加了网络负载率、缓存占用率。
2 MDCE算法改进
2.1 改进MDCE算法下一跳节点的选择
针对MDCE路由算法的4个缺点，应该适当减少网络中的消息副本，避免或减少缓存与其他资源争夺，保证消息副本有足够的存活时间，减少消息副本被丢弃的机率，从多个节点中选择两个方向作为节点的下一跳中继节点进行消息复制，同时不删除当前节点消息，即消息沿三个方向进行传输，如图2所示。
图2 下一跳节点选择
这样既减少了节点的计算量，又避免了MDCE路由协议转换为纯粹的Epidemic路由协议，解决了上述前3个缺点。在资源的利用上，也可以减少能量的消耗。由图2可知，若A为消息生成节点则按照三个方向进行传输，若为消息携带者(中继节点)，则按两个方向进行传输，且自身消息副本不删除，如果少于或等于两个节点，则进行消息复制，同时源节点也保留消息副本。在节点的运动的过程中，可以通过原来位置S和现在的节点A，计算出下一跳中继节点传输的移动方向，把消息往AB、AC方向传输，通过计算可得出左前和右前的夹角范围分别是60°～180°和180°～300°。通过该角度范围，使更加偏向于AB、AC方向上的节点复制消息，即面向区域A1、A2方向传递，效果如图3所示，避免了前述的问题4。
图3 中继节点选择示意图
2.2 MDCE改进路由算法描述
结合移动方向的选择和缓存管理策略，MDCE改进后路由算法描述如下：
输出：下一跳中继节点列表。
for (源节点或中继节点的相邻节点1 toN)计算MD和MDi的夹角
If (R1 if (relay List中已经存在一个该方向上的中继节点) 选择一个具有更小值的节点 return NodeList If(node[i]==soursenode) else if(nextnode[i]!=null&&i>3) 从NodeList节点列表中选择节点向三个方向进行传递，删除消息副本 else If(nextnode[i]!=null&&i<3) 从NodeList相邻节点列表中选择节点进行消息复制，且不删除消息副本 If(node[i]==destination node) 广播送达消息 If(当前为中继节点) else if(nextnode[i]!=null&&i>3) 从NodeList列表中选择复制消息给相邻节点 else If(nextnode[i]!=null&&i<3) 从相邻节点列表中选择节点进行消息复制，且不删除消息副本 NextNode列表NodeList选择方法 这样，中继节点在密度稀疏或稠密的情况下都能更好地控制消息冗余。对于改进后的算法，可以通过数学模型得到其覆盖示意图，如图4所示，其中S为源节点。 图4 消息模拟传递示意图 对于缓存管理策略，本文采用与MDCE算法相同的管理方式。 本节使用ONE基于随机路点模型对MDCE和改进后的MDCE进行仿真实验。四个衡量指标分别为投递率、负载率、平均跳数和丢包数，测试两个算法在缓存空间、消息生存周期(TTL)、消息生成时间间隔的路由性能表现。容延网络仿真平台仿真参数如表1所示。 表1 随机路点模型仿真参数 图5是两种算法的路由性能随节点缓存空间大小的变化情况。可以看出，改进后的MDCE算法在负载率、丢包数上都取得了一定优势，在投递率上相差不大，在可以接受的范围，虽然平均跳数次于原来的MDCE算法，但在资源受限的条件下改进后的MDCE算法是比较有效的。 图5 算法性能与缓存空间关系图 可以得出，在随机路点模型中，当资源严重受限，网络能力严重不足，缓存资源不是捉襟见肘时，改进后的MDCE算法可以代替MDCE算法。此时，改进后的MDCE路由算法在保持较高投递率的同时，降低了负载率及消息丢包数，性能更加出色。 图6是两种路由算法性能随消息生存时间的变化情况。在不同的生存时间里，对比原MDCE算法，改进后的MDCE在负载率、丢包数上有所降低，拥有一定优势。当消息生存时间大于40 min时，改进后的MDCE明显优于传统MDCE算法。 图6 算法性能与生存周期关系图 可以得出，在随机路点模型中，当消息的生存时间较长时，改进后的MDCE算法的消息传递率比原MDCE算法高，且改进后的MDCE算法负载率更低，丢包数更少。在DTN特殊环境中，改进后的MDCE算法路由性能更优，性能更稳定，虽然在跳数上略高，但在投递率、丢包数、网络负载率上更有优势。 图7是两种路由算法性能随着消息生成时间间隔的变化情况。改进后的MDCE在网络负载率、丢包数上仍然具有优势，平均路数相差不大，进一步验证了改进后的MDCE在性能上的优势及有效性。 图7 算法性能与消息生成间隔相关图 可以得出，在随机路点模型的容迟网络环境中，改进后的MDCE算法适用于比原MDCE算法条件更为受限的情况，具有更好的性能。 因为DTN网络的特殊性，无法捕获DTN网络的全局拓扑结构(即使捕获到也可能是无效的拓扑结构)，所以DTN网络的评价标准主要有消息传递的可靠性、丢包数、网络负载率。在资源受限的DTN网络中，行之有效的资源管理策略可以提高资源的利用率，减少丢包数，提高传递效率，并降低网络负载率，减少资源消耗，提高整体路由性能。本文使用ONE对改进后的MDCE路由算法进行了仿真实验，结果表明，在基于随机路点模型的网络环境中，改进后的MDCE算法除了在平均跳数上略差于MDCE算法，但其在取得较高消息投递率的同时，网络负载率及丢包数都优于原来的MDCE算法。下一步研究将利用统计相关知识，针对DTN节点的活动频率不同等特点，提出更加高效的DTN路由算法，并在具体的容迟网络中进行实际的部署应用。
3 实 验
3.1 节点缓存空间
3.2 消息生存周期
3.3 生成消息的时间间隔
4 结 语
