Improving routing protocol performance in delay tolerant networks using extended information

Delay tolerant networks (DTNs) are wireless mobile networks that do not guarantee the existence of a path between a source and a destination at any time. When two nodes move within each other’s transmission range during a period of time, they can contact each other. The contact of nodes can be periodical, predictable and nonpredictable. In this paper, we assume the contact of nodes is nonpredictable so that it can reflect the most flexible way of nodes movement. Due to the uncertainty and time-varying nature of DTNs, routing poses special challenges. Some existing schemes use utility functions to steer the routing in the right direction. We find that these schemes do not capture enough information of the network. Thus, we develop an extended information model that can capture more mobility information and use regression functions for data processing. Experimental results from both our own simulator and real wireless trace data show that our routing algorithms based on the extended information model can increase the delivery ratio and reduce the delivery latency of routing compared with existing ones.     

DTN体系结构及关键技术研究综述

中断/延迟容忍网络(Disruption/ Delay Tolerant Network,DTN)是从Ad-hoc网络中抽象出来的一种全新的网络模型。与传统的无线移动自组织网络不同,该网络模型的应用场景具有高延迟、易中断等特点。高延迟、易中断的网络环境被称为受限网络。DTN作为一个针对受限网络的新兴研究领域,使用特殊的“存储-携带-转发”模式进行数据传递,以对抗受限网络中的高延迟和易中断带来的影响。它的发展将对未来军事战争、航天通信、抢险救灾等诸多场景提供更为可靠的通信保证。文中分析了DTN体系架构及其特性,研究了DTN路由协议并指出其适用的场景,最后总结了DTN研究中遇到的难点问题,并指出未来研究需要关注的方向。     

Dynamic Prediction based Multi Queue (DPMQ) drop policy for probabilistic routing protocols of delay tolerant network

Two most important issues should be considered to achieve data delivery in DTN networking: routing protocols for the network and intelligent buffer management policy for everyone node in the network. The routing scheme decides which messages should be forwarded when nodes meet, and the buffer management policy determines which message is purged when the buffer overflows in a node. This study proposes a buffer management policy named as Dynamic Prediction based Multi Queue (DPMQ) for probabilistic routing protocols. It works by classification of local buffer into three queues of messages, which are DCTL, HPTL and LPTL. The simulation results have proven that the DPMQ performs well as compared to DLA, DOA, MOFO, LIFO, LEPR and LIFO in terms of reducing the message relay, message drop, hop counts average and overhead while rising in the delivery probability.     

一种有效的时延约束组播路由算法

在多媒体通信网络中，组播问题提出了新的要求，除了最小化组播通信的代价，同时要求保证每一个目的的节点在固定的延时之内接收信息，在这篇论文中，我们提出了一个边路选择函数用于解决时延约束组播问题，我们的实验结果揭示了该函数能提供满足时约束且代价较小的组播路由问题近似解。     

Delay-sensitive routing in multi-rate MANETs

A mobile ad hoc network (MANET) is a collection of mobile hosts, which can communicate by the aid of intermediate mobile hosts without utilizing a fixed infrastructure and centralized administration. Many MANET standards, such as 802.11a, 802.11b, and 802.11g, can be operated at various rates for Quality-of-Service (QoS) constrained multimedia communication to more efficiently use the limited resources of MANETs. Since the radio channel is shared among neighbors in MANETs, calculating one-hop delays and determining delay-sensitive routes using the IEEE 802.11 MAC are still two challenging problems. In this paper, we first exploit the busy/idle ratio of the shared channel to estimate one-hop delay based on varied data rates. Then by the aid of the estimated delay, a multi-rate routing protocol is proposed for selecting data rates and determining a route for admitting a flow with a requested delay. In MANETs, when a host is transmitting data packets, its neighbors are blocked (i.e., forbidden to send packets) since it shares the radio channel with its neighbors. We adopt the strategy by selecting the combination of data rates and a route in order to minimize the total blocking time to all hosts of the network for maximizing the network’s capacity, which is the number of flows admitted by the network. Simulation results show that the proposed method obtains a more precise one-hop delay than a very recent work, and the proposed protocol admits more flows than an existing protocol.     

DTN中基于节点价值的效用路由算法

为了解决延迟容忍网络(DTN)中传统路由算法中消息被分配的网络资源不均衡及节点负载不均衡问题,结合消息效用值提出了一种基于节点价值的效用路由算法。算法根据动态改变的消息效用值选择最高优先级的消息(具有最小TTL和到目的节点最短距离的消息)进行转发,以使得为每个消息分配的网络资源相对均衡;同时,根据节点的价值(与节点速度和剩余缓存有关)选择下一跳节点,以平衡每个节点的负载;另外,算法还采用了一定的消息管理机制及时清除缓存空间。通过仿真实验及性能分析表明,该算法在传输成功率、传输延迟和网络开销上都有明显的改善。因此,通过充分利用网络资源提高了算法的整体性能。     

一种基于好友簇的社交网络中的时延容忍路由协议

社交网络是一种以便携式移动通信设备为节点的无线网络,通常由于其规模较大、结构复杂并且拓扑变化频繁,而成为时延容忍网络的一个典型应用场景。通过分析社交网络的特性,构建了基于好友群组的网络拓扑模型,并基于该模型,提出了一种基于簇结构的时延容忍路由协议。通过实验证明了该路由协议可以在保证较高路由性能的前提下有效控制由于数据副本传染造成的对网络资源的消耗。     

DTN中基于二分散发和等待路由的自适应拥塞控制策略

针对二分散发和等待路由中报文被转发的特点,提出节点首先通过应答交换机制丢弃已被递交到信宿节点的报文,来减少网络中冗余报文的传输;当节点缓存完全占用又需存储新报文时,执行拥塞检测和拥塞避免操作,遍历缓存,找到缓存中拷贝数最小的报文将其丢弃（若此报文正在被传输则丢弃拷贝数次小的报文）直至有足够的缓存空间存储新接收到的报文。通过大量仿真实验及相关数据的分析与比较,说明该拥塞策略能显著提高递交率,减小开销,并对拥塞状况有更好的自适应能力。     

On supporting high-throughput routing metrics in on-demand routing protocols for multi-hop wireless networks

Researchers have proposed routing metrics other than hop count, such as ETX (expected transmission count) and ETT (expected transmission time), to find routes with high throughput. These metrics are inherently suitable to be used in source routing protocols such as DSR, because link state information needs to be collected for the calculation of the shortest path. In this paper, we propose an efficient and generalized approach called accumulated path metric (APM) for supporting high-throughput metrics (HTMs) in on-demand routing protocols. One advantage of APM is that it is able to find the shortest path, in terms of a particular metric, without collecting topology information and without running a shortest-path algorithm. This will significantly simplify the existing design of supporting HTMs in DSR. We present a proof of the correctness of APM. Moreover, we address the problem of duplicate RREQ (route request) transmissions with existing HTM schemes and present a broadcast ordering (BO) technique to suppress unnecessary RREQ transmissions. We study the performance of APM and BO in both AODV and DSR, and the results verify the effectiveness of the proposed approaches.     

基于平均传递概率的容迟网络路由算法的设计

为了提高容迟网络的传递率、降低传输延迟、对节点缓存进行更有效的管理, 结合已有的PROPHET和Spray and Wait算法, 提出了一种基于平均传递概率的容迟网络路由算法RAB-ADP。在该算法中设置了一个与时间有关的平均传递预测概率参数进行消息转发的决策, 解决了PROPHET算法容易产生路由抖动的缺点。算法综合利用了复制和知识两个属性, 采用{MOPR; FIFO}队列策略组, 通过消息传送完毕的ACK确认信息进行缓存管理和网络中冗余消息副本的删除。仿真实验表明, 该算法在节点缓存大小不同以及网络中节点数目不同的两种情况下, 传递率和路由开销比率的性能均优于其他经典路由算法。     

An efficient anonymous authentication mechanism for delay tolerant networks

Security and privacy are crucial to the wide deployments of delay tolerant networks. Without security and privacy guarantees, people are reluctant to accept such a new network paradigm. To address the security and privacy issues in delay tolerant networks, in this paper, based on ID-based ring signatures and Merkle hash tree techniques, we present a new efficient anonymous authentication mechanism. The newly proposed mechanism not only achieves good security properties, including authentication, anonymity and confidentiality, but also has strong robustness and high efficiency.     

DTN中一种基于接触时间的休眠机制

针对容迟/容断网络(DTN)中能量供应受限的问题,提出一种基于接触时间的休眠机制SSCT(Sleep Scheme based on Contact Time)。节点依据历史接触时间自适应调整等待时间和休眠时间,从而降低休眠期间错失通信机会的概率。仿真实验表明,添加SSCT的Epidemi。算法能够在保证消息交付率的基础上降低网络开销和能耗。相比First Contact算法,SSCT对多副本路由算法的性能提升更加明显。     

一种考虑节点拥塞情况的DTN概率路由算法*

容迟网络是一种新型网络,其概率路由算法根据历史相遇频率对相遇概率进行计算与更新,通过相遇概率判断是否转发报文。当节点缓存受限时,在网络中采用概率路由算法使得节点很容易发生拥塞,对报文的传送产生影响。为了减小拥塞对概率路由算法的影响,提出了一种考虑节点拥塞情况的概率路由算法,将节点相遇的概率和节点拥塞的情况综合起来,得到一个报文的递交概率,降低了由于拥塞对网络性能的影响,提高了报文的递交率,减小了报文在缓存中排队等候的时间。仿真结果表明,与传统的概率路由算法相比,在改进后的概率路由算法中报文递交率显著提高,平均延迟也在降低。     

A reinforcement learning-based routing for delay tolerant networks

Delay Tolerant Reinforcement-Based (DTRB) is a delay tolerant routing solution for IEEE 802.11 wireless networks which enables device to device data exchange without the support of any pre-existing network infrastructure. The solution utilizes Multi-Agent Reinforcement Learning techniques to learn about routes in the network and forward/replicate the messages that produce the best reward. The rewarding process is executed by a learning algorithm based on the distances between the nodes, which are calculated as a function of time from the last meetings. DTRB is a flooding-based delay tolerant routing solution. The simulation results show that DTRB can deliver more messages than a traditional delay tolerant routing solution does in densely populated areas, with similar end-to-end delay and lower network overhead.     

A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

基于DTN历史队列预测的单播路由算法

容迟容断网络（delay tolerant networks, DTN）具有连接频繁间断、高延迟、高误码率、高丢包率等特点。良好稳健的路由算法是提高消息转发成功率、降低延迟和能耗、提高DTN通信能力的重要因素。为此设计了一种基于历史队列预测的单播路由算法（earliest deliver based on historical orderliness prediction, EDHO）。仿真结果表明该算法可有效地提高DTN消息传递的可靠性。     

Sparse communication networks and efficient routing in the plane

Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously. This approach is explored by considering the design of communication networks supporting efficient routing in the special case of points located in the Euclidean plane. The desirable network parameters considered include low degree and small number of communication links. The desirable routing parameters considered include small routing tables, small number of hops and low routing stretch. Two rather different schemes are presented, one based on direct navigation in the plane and the other based on efficient hierarchical tree covers. On a collection of n sites with diameter D, these methods yield networks with a total of communication links and some bounds on the degree, coupled with routing schemes with constant routing stretch, memory bits per vertex and routes with at most or hops. Received: October 2000 / Accepted: May 2001     

DTN中考虑连接时间的概率路由算法

鉴于连接时间对报文能否成功传输有重要影响,提出考虑连接时间的概率路由算法。该算法基于连接时间和历史相遇频率两个因素来估计递交概率,从而大大提高了报文成功递交的概率,减少了报文传输中断的发生。仿真结果表明,与传统的概率路由相比该路由算法具有较高的报文递交概率和较低的网络开销率。     

A routing defense mechanism using evolutionary game theory for Delay Tolerant Networks

Delay Tolerant Networks (DTNs) often suffer from intermittent disruption due to factors such as mobility and energy. Though lots of routing algorithms in DTNs have been proposed in the last few years, the routing security problems have not attracted enough attention. DTNs are still facing the threats from different kinds of routing attacks. In this paper, a general purpose defense mechanism is proposed against various routing attacks on DTNs. The defense mechanism is based on the routing path information acquired from the forwarded messages and the acknowledgment (ACK), and it is suitable for different routing schemes. Evolutionary game theory is applied with the defense mechanism to analyze and facilitate the strategy changes of the nodes in the networks. Simulation results show that the proposed evolutionary game theory based defense scheme can achieve high average delivery ratio, low network overhead and low average transmission delay in various routing attack scenarios. By introducing the game theory, the networks can avoid being attacked and provide normal transmission service. The networks can reach evolutionary strategy stable (ESS) under special conditions after evolution. The initial parameters will affect the convergence speed and the final ESS, but the initial ratio of the nodes choosing different strategies can only affect the game process.