论文部分内容阅读
摘 要：DTN是一种新型网络体系结构，其网络频繁断裂的特点常常导致消息传输失败，针对这个问题，提出一种基于连接持续时间预测的DTN路由算法CPBRA。利用相遇节点的移动速度、方向，传输范围等信息预测节点的连接的持续时间，并依据消息的大小选择适当的消息传输路径，以减少消息重传的错误操作，提高资源利用率，有效地控制网络开销。
关键词：容迟网络；路由算法；连接持续时间；同伴节点；预测
中图分类号：TP393.04
随着微电子技术的发展，越来越多的新型无线网络开始出现，如陆地移动网络、军事无线自组织网络等。这些网络存在共同的特点：间歇性连接、缺少端到端路径、资源受限等。传统的无线网络传输模式要求通信源和目标节点之间存在至少一条完整的路径，因而无法在这些网络环境中运行。为了解决这些新型网络中的通信问题，Fall等科学家提出了容迟网络[1]（Delay Tolerant Network，DTN）的架构。DTN充分利用节点移动形成的通信机会，采用“存储-携带-转发”模式进行消息转发。
由于DTN网络拓扑的动态性，从而导致了链路间歇性断裂而且中断时间较长。如果消息在转发过程中中断链接，则直接导致消息传输失败，必须等待链接成功后续传，这样使得DTN有限的资源被大量消耗。如果能在消息转发前，先根据连接的容量大小、预测节点连接的持续时间等因素来选择合适的消息进行转发，将能有效地提高消息传输的可靠性，减少消息重传操作。基于以上思想，本文提出一种基于连接持续时间预测的路由算法（A Routing Algorithm Based on Contact-duration Prediction，CPBRA），该算法采用Binary Spray and Wait（BSW）[2]算法进行消息扩散传输，使消息快速传达目标同伴节点，然后在目标同伴节点间进行消息分发以控制网络开销。
1 相关研究
目前DTN路由策略可以划分为扩散性路由、概率性路由和确定性路由[2]。
扩散性路由通常使用复制技术，通过传染转发方式（epidemic forwarding，EF）[3将同一消息的多份拷贝注入网络的一种简单的扩散性算法，每个携带消息的节点将消息转发给所有的邻居节点。因此该算法较易产生较大网络负载。BSW[2]算法在源节点指定消息允许的最大拷贝数为L，并使用基于二叉树的方法来产生L份拷贝。相比EF算法，BSW控制了网络开销，有较好的可扩展性。
概率性路由的工作原理是通过节点相遇历史信息对消息转发的有用性进行评估，给每个节点赋予转发效用值。PROPHET是一种比较有代表性的概率性路由，该算法使用节点相遇频率来估算传输概率。当节点相遇时交换消息列表及传输概率向量，消息不断地从传输概率小的节点转发到传输概率大的节点，直到遇到目标节点。
确定性路由假设节点移动路径等一些信息是可以確定或预知的，该类路由往往有较高的传输效率，但需要一些辅助设备（如GPS等）。基于位置路由算法（Location-Based Routing），使用GPS导航设备获取节点的坐标。节点可以根据自身的坐标、目标节点坐标和潜在下一跳的坐标信息选择最佳的传输路径，有较高的传输效率，但是节点坐标信息在网络中的扩散一定程度上增加了网络负载。
2 CPBRA算法
2.1 网络模型。网络是由N个移动节点组成，一旦节点进入彼此通信范围内，便建立了连接，可以进行直接通信。当节点不在直接通信范围内，可以通过其它中间节点进行通信。节点的能量和缓存空间有限，节点间连接时间有限。目标节点有足够的空间存储接收的消息，只有传输中的消息受有限存储空间的限制。每个节点可携带多个需要送达各目标节点的消息，同一消息的所有拷贝具有相同ID。
2.2 同伴节点。每个节点记录与其他节点相遇的历史信息，包括接触频率和相遇时的连通时长。根据这些信息，该节点每隔时间窗口T，利用公式（1）、（2）估算与其它节点的“相邻值”。相邻值表示节点的邻近程度，相邻值越大，表明节点接触的可能性越大。每个节点选择相邻值最大的F个节点作为自己的同伴节点。
3 性能评估
3.1 仿真环境模拟设置。CPBRA中参数γ，α分别取0.98和0.2；tunit，T分别为4秒和180秒；参数F，L1，L2分别取6、6和8。BSW[2]中L取6。PROPHET[4]中Pinit为0.75，参数γ，β分别取0.98和0.25。
3.2 模拟结果与性能分析。本文从消息成功传输率和通信开销方面分析路由算法的性能。图1所示为网络流量确定为3000的情况下，消息成功传输率随着消息大小变化的曲线图。从图中可以看到CPBRA算法具有较高的消息成功传输率。当网络中的消息大小较小时，BSW算法的消息成功传输率与CPBRA算法接近，但是，当消息大小变大时，BSW算法的消息成功传输率低于CPBRA算法。
4 结束语
本文提出的CPBRA算法是基于连接预测和控制复制思想，该算法对节点相遇所能维持的时间长度进行预测，估算连接容量，根据消息大小选择合适的消息转发路径。从实验结果可以看出，CPBRA在消息成功传输率和通信开销方面都优于其他算法。
参考文献：
[1]FALL K.A delay-tolerant network architecture for challenged Internets[C].Proceedings of ACM SIGCOMM.New York：ACM Press，2003：27-34.
[2]曹元大，殷磊，马明辉.容迟网络中低资源消耗Advanced Epidemic路由算法[J].计算机应用，2009（01）：281-283.
作者简介：黄勇萍（1985-），硕士研究生，讲师，研究方向：计算机网络。
作者单位：广西民族师范学院 数学与计算机科学系，广西崇左 532200
基金项目：广西民族师范学院2011年度资助项目（项目编号：XYYB2011023）。
关键词：容迟网络；路由算法；连接持续时间；同伴节点；预测
中图分类号：TP393.04
随着微电子技术的发展，越来越多的新型无线网络开始出现，如陆地移动网络、军事无线自组织网络等。这些网络存在共同的特点：间歇性连接、缺少端到端路径、资源受限等。传统的无线网络传输模式要求通信源和目标节点之间存在至少一条完整的路径，因而无法在这些网络环境中运行。为了解决这些新型网络中的通信问题，Fall等科学家提出了容迟网络[1]（Delay Tolerant Network，DTN）的架构。DTN充分利用节点移动形成的通信机会，采用“存储-携带-转发”模式进行消息转发。
由于DTN网络拓扑的动态性，从而导致了链路间歇性断裂而且中断时间较长。如果消息在转发过程中中断链接，则直接导致消息传输失败，必须等待链接成功后续传，这样使得DTN有限的资源被大量消耗。如果能在消息转发前，先根据连接的容量大小、预测节点连接的持续时间等因素来选择合适的消息进行转发，将能有效地提高消息传输的可靠性，减少消息重传操作。基于以上思想，本文提出一种基于连接持续时间预测的路由算法（A Routing Algorithm Based on Contact-duration Prediction，CPBRA），该算法采用Binary Spray and Wait（BSW）[2]算法进行消息扩散传输，使消息快速传达目标同伴节点，然后在目标同伴节点间进行消息分发以控制网络开销。
1 相关研究
目前DTN路由策略可以划分为扩散性路由、概率性路由和确定性路由[2]。
扩散性路由通常使用复制技术，通过传染转发方式（epidemic forwarding，EF）[3将同一消息的多份拷贝注入网络的一种简单的扩散性算法，每个携带消息的节点将消息转发给所有的邻居节点。因此该算法较易产生较大网络负载。BSW[2]算法在源节点指定消息允许的最大拷贝数为L，并使用基于二叉树的方法来产生L份拷贝。相比EF算法，BSW控制了网络开销，有较好的可扩展性。
概率性路由的工作原理是通过节点相遇历史信息对消息转发的有用性进行评估，给每个节点赋予转发效用值。PROPHET是一种比较有代表性的概率性路由，该算法使用节点相遇频率来估算传输概率。当节点相遇时交换消息列表及传输概率向量，消息不断地从传输概率小的节点转发到传输概率大的节点，直到遇到目标节点。
确定性路由假设节点移动路径等一些信息是可以確定或预知的，该类路由往往有较高的传输效率，但需要一些辅助设备（如GPS等）。基于位置路由算法（Location-Based Routing），使用GPS导航设备获取节点的坐标。节点可以根据自身的坐标、目标节点坐标和潜在下一跳的坐标信息选择最佳的传输路径，有较高的传输效率，但是节点坐标信息在网络中的扩散一定程度上增加了网络负载。
2 CPBRA算法
2.1 网络模型。网络是由N个移动节点组成，一旦节点进入彼此通信范围内，便建立了连接，可以进行直接通信。当节点不在直接通信范围内，可以通过其它中间节点进行通信。节点的能量和缓存空间有限，节点间连接时间有限。目标节点有足够的空间存储接收的消息，只有传输中的消息受有限存储空间的限制。每个节点可携带多个需要送达各目标节点的消息，同一消息的所有拷贝具有相同ID。
2.2 同伴节点。每个节点记录与其他节点相遇的历史信息，包括接触频率和相遇时的连通时长。根据这些信息，该节点每隔时间窗口T，利用公式（1）、（2）估算与其它节点的“相邻值”。相邻值表示节点的邻近程度，相邻值越大，表明节点接触的可能性越大。每个节点选择相邻值最大的F个节点作为自己的同伴节点。
3 性能评估
3.1 仿真环境模拟设置。CPBRA中参数γ，α分别取0.98和0.2；tunit，T分别为4秒和180秒；参数F，L1，L2分别取6、6和8。BSW[2]中L取6。PROPHET[4]中Pinit为0.75，参数γ，β分别取0.98和0.25。
3.2 模拟结果与性能分析。本文从消息成功传输率和通信开销方面分析路由算法的性能。图1所示为网络流量确定为3000的情况下，消息成功传输率随着消息大小变化的曲线图。从图中可以看到CPBRA算法具有较高的消息成功传输率。当网络中的消息大小较小时，BSW算法的消息成功传输率与CPBRA算法接近，但是，当消息大小变大时，BSW算法的消息成功传输率低于CPBRA算法。
4 结束语
本文提出的CPBRA算法是基于连接预测和控制复制思想，该算法对节点相遇所能维持的时间长度进行预测，估算连接容量，根据消息大小选择合适的消息转发路径。从实验结果可以看出，CPBRA在消息成功传输率和通信开销方面都优于其他算法。
参考文献：
[1]FALL K.A delay-tolerant network architecture for challenged Internets[C].Proceedings of ACM SIGCOMM.New York：ACM Press，2003：27-34.
[2]曹元大，殷磊，马明辉.容迟网络中低资源消耗Advanced Epidemic路由算法[J].计算机应用，2009（01）：281-283.
作者简介：黄勇萍（1985-），硕士研究生，讲师，研究方向：计算机网络。
作者单位：广西民族师范学院 数学与计算机科学系，广西崇左 532200
基金项目：广西民族师范学院2011年度资助项目（项目编号：XYYB2011023）。