Adaptive Spraying for Routing in Delay Tolerant Networks

Message delivery in Delay Tolerant Networks (DTNs) is challenging due to the fact that the network is intermittently connected. Mobility can be exploited to improve DTN performance. In this paper, we propose a DTN routing scheme Adaptive Spraying. Adaptive Spraying exploits mobility pattern and encounter history to predict the number of nodes with no copy a node will encounter within the expected delay. The number of nodes encountered can be viewed as the number of copies disseminated. Each node with copies dynamically chooses the number of copies by itself, instead of a fixed number determined at the source node. We present an analysis of the scheme and validate the analytical results with simulations. Simulation results show that Adaptive Spraying performs well over a variety of environmental conditions such as transmission range and traffic load.     

Selective Message Forwarding in Delay Tolerant Networks

It is challenging to deliver messages in a network where no instant end-to-end path exists, so called delay-tolerant network (DTN). Node encounters are used for message forwarding. In this paper, we propose a DTN routing protocol SMART. SMART utilizes the travel companions of the destinations (i.e. nodes that frequently meet the destination) to increase the delivery opportunities while limiting message overhead to a bounded number. Our approach differs from related work in that it does not propagate node encounter history nor the delivery probabilities derived from the encounter history. In SMART, a message source injects a fixed number of message copies into the network to forward the message to a companion of the destination, which only forwards the message to a fixed number of the destination’s companions. Our analysis and simulation results show that SMART has a higher delivery ratio and a smaller delivery latency than the schemes that only use controlled opportunistically-forwarding mechanism and has a significantly smaller routing overhead than a pure flooding scheme.     

容迟／容断网络路由技术研究

容迟／容断网络（DTN）由于其长延迟、高误码率及频繁断路等网络特性不满足互联网较短传输延迟、低误码率及存在端到端路径的基本假设,传统Internet体系结构和协议无法直接用于DTN。DTN路由机制可以按照连接的确定性分为确定性路由和随机性路由。确定性路由主要有基于树的路由、时空路由和修正的最短路径路由等方法;随机性路由主要有流行性路由、基于历史消息的路由、基于模型的路由、可控移动路由和基于编码的路由。DTN在游牧计算、军事战场通信、紧急营救及灾后重建方面具有广泛应用前景。     

Network Coding for Overhead Reduction in Delay Tolerant Networks

Employing Network Coding (NC) in routing protocols for Delay Tolerant Networks (DTNs) is a challenging issue during the last years due to its potential beneficial effect on improving relevant critical metrics. This paper proposes an effective NC scheme intended for sparse DTNs comprising nodes of limited storage capacity. The scheme employs a memory management algorithm that makes optimal use of the limited storage capacity and focuses on unicast sessions where source and intermediate nodes combine only packets belonging to the same generation and destined for the same destination node. Upon having received a sufficient number of linearly independent packets resulting in a matrix of full rank, the destination nodes can apply network decoding to retrieve the information intended for them. The proposed scheme is fully distributed since the network nodes make decisions based on information collected solely from their own buffers. Combined either with Epidemic or probabilistic routing protocols, the scheme manages to drastically reduce the overhead created per source packet.     

面向能量感知的DTN地理位置路由算法在灾害地域的应用

延迟容错网络中的路由特点是不存在一条端到端的通路.这种特征可用于基础设施被摧毁的灾害地区.使用现有的移动平台如手机,建立一个能源感知的通信网络是一个有吸引力的问题.本文基于预测的路由和传输控制机制,提出了一种地理位置的协议.通过使用雅安地区的实际地图作为实验地图,对比现有的经典协议,可以发现该算法增加了消息投递成功率,降低了传输延时,并大大降低了路由开销.此外,算法的消息传输跳数比其他算法更接近于传染病路由算法.     

Two-Level Community-Based Routing in Delay Tolerant Networks

Delay tolerant networks can not maintain end-to-end connectivity. Thus the routing is one of the critical issues. As we known, the two-level community model including the small community and the big community is proposed for the first time. In the same small community, any two member nodes are friends with each other. And in the same big community which is constructed of some small communities, any two communities have some pairs of friend nodes between them. Based on this model, a two-level community-based routing (TLCR) algorithm is presented in delay tolerant networks. In TLCR, according to the location of packet holder including inside the small community of destination node, inside of the big community and outside of the small community of destination node, and outside of the big community of destination node, the different packet forwarding strategies are investigated. The number of relay nodes selected by a packet holder is decreasing with the holder’s location from inside of the small community of destination node to outside of the big community of destination node. The probability of the source node successfully delivers the packet to the destination node and the copies number corresponding with the above three locations are analyzed, respectively. The simulation results show that TLCR not only improves the delivery ratio but also greatly reduces the resource cost.

     

Stigmergic Communication for Self-Organized Multi Ferry Delay Tolerant Networks

This paper presents an Adaptive On-the-fly Decision maker for Multi Ferry (A-ODMF) delay tolerant networks. A-ODMF chooses the next node to visit for controlled mobility data ferries. In our assumptions, there is no direct communication among ferries. Therefore, we apply a stigmergic communication among ferries for their coordination. Nodes are employed to act as relays for an indirect signaling of control information among ferries to decrease redundant visits to nodes. Moreover, the self-organized decision maker in A-ODMF adapts its decision functions based on the local observations of a ferry from the delay of delivered messages in the network to increase the efficiency of ferry decisions. A-ODMF also considers the priority of messages in the ferry buffer and delivers high priority messages earlier. The simulation results show that A-ODMF outperforms existing on-the-fly approaches in terms of message latency. In scenarios with high number of ferries, the impact of indirect signaling and the adaptive decision maker in A-ODMF is more significant on the performance improvement. A-ODMF decreases unnecessary visits to nodes and therefore improves the travel time of messages in a ferry buffer. Finally, we study and discuss the impact of increasing the number of ferries and increasing the ferry speed on the performance and cost of a message ferry network. We show that a required performance can be achieved with less cost by increasing the speed of ferries than increasing the number of ferries.     

Context-Aware Routing in Delay and Disruption Tolerant Networks

In this paper, we analyze the problem of context adaptation in delay and disruption tolerant networks (DTNs). Initially, we performed experiments with well-known routing protocols to evaluate how much distinct configurations impact their performance. The results show that the performance is highly configuration dependent and improper configuration can lead to a performance up to 506.6 % worse than the best configuration tested. This motivates us to propose CARTOON (context-aware routing protocol for opportunistic networks), a novel routing protocol for DTNs based on the concept of context-adaptation. We evaluate CARTOON through simulations and the results show that our propose outperformed other well-known protocols, exhibiting results that are, on average, at 95 % of the computed optimum delivery rate.     

On the Performance of Epidemic Based Routing Protocols for Delivering Multicast Bundles in Delay Tolerant Networks

Epidemic and ts variants are one main category of routing protocols in delay tolerant networks. They are known to be simple, have low latency and high delivery ratio. However, to date, virtually no work has investigated their suitability in delivering multicast bundles. To this end, we have conducted extensive and comprehensive simulation studies to answer this question. Specifically, we compare their delivery ratio, and buffer occupancy level in various multicast scenarios where nodes move according to both random way point model and a trace file containing records of student movements on a campus. Moreover, we tested the influence of key factors such as anti-entropy session, multicast group size, the number of groups and subscribers forwarding policies. We found that, achieving a high delivery ratio is dependent on nodes using anti-entropy session, relay/subscriber ratio and subscribers working as relays. Additionally, we also observed that relay nodes that use epidemic variants experience high buffer occupancy level. In particular, protocols such as epidemic with encounter count (EC) result in 100 % buffer utilization. To solve this problem, we propose EC quota, in which bundles can only be transmitted to \(k\) relay nodes. Our experiments prove that EC quota is capable of reducing the buffer occupancy level of relay nodes by 15–100 % whilst maintaining high delivery ratios.     

On Modeling The Impact of Selfish Behaviors on Limited Epidemic Routing in Delay Tolerant Networks

Transmission opportunity in delay tolerant network (DTN) is uncertain. To improve the routing performance, DTN tries to use every contact between nodes, and one classic policy is epidemic routing algorithm (ER). Due to much energy consumption, L-hop limited ER algorithm is proposed. However, such method does not consider the energy constraint for a specific node. To overcome this problem, we propose the L-count limited ER algorithm, in which each node forwards at most $L$ times. Numerical results show that this new algorithm can get better performance. Both of above algorithms need nodes to work in a cooperative way. However, due to selfish nature of nodes (individual selfishness and social selfishness), they may not be willing to help others. This paper proposes an accurate theoretical framework to evaluate the impact of these behaviors based on nonlinear differential equations (ODE). Simulations based on both synthetic and real motion traces show the accuracy of our theoretical model. Numerical results show that selfish nature can decrease the flooding performance in both algorithms. Under the same selfish behaviors, the performance is decreasing with the number of communities. The deviation of the performance between two algorithms is decreasing with the value of $L$ .     

Memory Forwarding Algorithm in Multiple Communities Delay Tolerant Networks

The routing is one of the key problems in delay tolerant networks (DTNs) because the source and destination often could not find a contemporaneous end-to-end path. In this paper, with the objective of reducing the number of copies, we propose two corresponding routings including a memory forwarding algorithm (MFA) and an extended memory forwarding algorithm (EMFA) for the specific type of node placement in DTNs where the nodes are randomly located and moved at different communities. The main idea of our algorithms are that the node copies a packet to an encountering node or not based on the relationship of their and the destination’s community locations calculated from the memory table, and they are designed for small and moderate number of communities respectively. We then state and analyze the expected number of copies of our algorithms. Simulation results reveal that MFA and EMFA can apparently decrease the number of copies and achieve comparable delivery delays compared with the classic multi-copy routings.     

Social group detection based routing in Delay Tolerant Networks

When implementing Mobile Ad Hoc Networks, a key characteristic of the network is the mobility pattern of the nodes. Based on the application, nodes can follow semi-predictable patterns, such as the routes followed by Vehicular Ad Hoc Networks, or the more strict schedules followed by aerial reconnaissance. Optimal routing schemes tend to take advantage of information regarding these patterns. In social environments, such as wildlife tracking or sending messages between humans, the devices and/or users will follow regular contact habits, tending to encounter social groups in which they participate. By identifying these groups, the patterns are used to optimize routing through a social environment. Dynamic Social Grouping (DSG), used to route messages strictly from a node to a basestation, is ideal for gathering sensor data and updating a shared data cache. In contrast, Dynamic Social Grouping-Node to Node (DSG-N²) is used to route messages between nodes, generally conventional communications. Both of these algorithms can be implemented ad null, meaning the devices initially have no information about their environment, and they work to reduce bandwith and delivery time while maintaining a high delivery ratio. In addition to presenting these two routing schemas, this article compares and contrasts two methods for estimating nodes’ delivery probabilities. The Contact Based Probability is based on encounters with other nodes, and the Performance Based Probability is based on the behavior of previous messages. The probability estimates were then validated with the Oracle analysis, which is based on knowledge of future events. This analysis indicated that DSG-N² probability estimates are comparable to the ideal.     

Determination of Relay Node Based on Fuzzy Logic in Delay Tolerant Network

Wireless Personal Communications - Delay tolerant networks are among mobile ad hoc networks. There is not a complete and connected route between the source and destination in these networks due to...     

基于分布传感的容迟自组织网络动态融合机制

为保证自组织容迟网络能够可靠并有效传输数据,以更好地实现在传输效率与网络开销之间的均衡,提出了一种基于分布传感的容迟自组织网络动态融合机制.该机制在分析自组织容迟网节点分布特性的基础上,通过分布式节点密度感知,实现快速获知整个网络中热点区域的节点分布,并利用热点区域节点之间的限跳函数实现动态路由,以最大程度减少在热点区域的冗余数据,有效地降低网络整体传输时延与开销.仿真结果表明,该算法在传输效率和时延方面展示具有明显优势,且有效降低网络冗余信息开销.     

Optimal Routing Control in Delay Tolerant Networks with Time-Varying Fees

Due to the uncertainty of the connections in delay tolerant networks, the source may need help from other nodes and make these nodes serve as relays to forward the messages to the destination. To further improve the performance, the source may also make these nodes serve as agents, which can help the source to make other nodes serve as relays. However, nodes may not be willing to help the source without any reward because of the selfish nature. This means that the source has to pay certain reward to the nodes that provide help. Furthermore, such fees may be varying with time. For example, if the nodes guess that the source is eager to transmit the message to the destination, they may ask for more reward. In addition, the reward that the source obtains from the destination may be varying with time, too. For example, the sooner the destination gets the message, the more reward may be. In such complex case, it may not be good for the source to request help all the time. This paper proposes a unifying theoretical framework based on Ordinary Differential Equations to evaluate the total reward that the source can obtain. Then, based on the framework, we study the optimal control problem by Pontryagin’s Maximum Principle and prove that the optimal policy confirms to the threshold form in some cases. Simulations based on both synthetic and real motion traces show the accuracy of the framework. Furthermore, we demonstrate that the performance of the optimal policy is the best through extensive numerical results.     

Integrated Social and QoS Trust-Based Routing in Delay Tolerant Networks

We propose and analyze a class of integrated social and quality of service (QoS) trust-based routing protocols in mobile ad-hoc delay tolerant networks. The underlying idea is to incorporate trust evaluation in the routing protocol, considering not only QoS trust properties but also social trust properties to evaluate other nodes encountered. We prove that our protocol is resilient against bad-mouthing, good-mouthing and whitewashing attacks performed by malicious nodes. By utilizing a stochastic Petri net model describing a delay tolerant network consisting of heterogeneous mobile nodes with vastly different social and networking behaviors, we analyze the performance characteristics of trust-based routing protocols in terms of message delivery ratio, message delay, and message overhead against connectivity-based, epidemic and PROPHET routing protocols. The results indicate that our trust-based routing protocols outperform PROPHET and can approach the ideal performance obtainable by epidemic routing in delivery ratio and message delay, without incurring high message overhead. Further, integrated social and QoS trust-based protocols can effectively trade off message delay for a significant gain in message delivery ratio and message overhead over traditional connectivity-based routing protocols.     

On Exploiting Dynamic Trusted Routing Scheme in Delay Tolerant Networks

Wireless Personal Communications - Delay tolerant network routing is characterized by sparsely or densely populated nodes. In such network routing with limited resource like buffer space is a...     

容迟网络中基于社会感知的协作机制研究

针对节点的社会自私性(social selfishness)对容迟网络(delay tolerant network,DTN)中路由效率、网络性能和安全等造成的负面影响,采用社会感知(socially aware)、博弈论等方法设计合理的协作机制是当前容迟网络研究的一个重要方向.文中首先描述了节点的社会自私性对容迟网络性能的影响.依据分析工具的差异,将已有容迟网络中基于社会感知的协作机制分为基于博弈论、基于信誉、基于虚拟银行3类.文中对各类协作机制的基本原理、方法和不足之处进行了分析和比较,最后对容迟网络中基于社会感知的协作机制的未来研究方向进行了展望.     

Theoretical Limits for Time Delay Based Location Estimation in Cooperative Relay Networks

Node localization in wireless networks is crucial for supporting advanced location-based services and improving the performance of network algorithms such as routing schemes. In this paper, we study the fundamental limits for time delay based location estimation in cooperative relay networks. The theoretical limits are investigated by obtaining Cramer–Rao Lower Bound (CRLB) expressions for the unknown source location under different relaying strategies when the location of the destination is known and unknown. More specifically, the effects of amplify-and-forward and decode-and-forward relaying strategies on the location estimation accuracy are studied. Furthermore, the CRLB expressions are derived for the cases where the location of only source as well as both source and destination nodes are unknown considering the relays as reference nodes. In addition, the effects of the node topology on the location estimation accuracy of the source node are investigated. The results reveal that the relaying strategy at relay nodes, the number of relays, and the node topology can have significant impacts on the location accuracy of the source node. Additionally, knowing the location of the destination node is crucial for achieving accurate source localization in cooperative relay networks.     

Efficient Authentication and Key Agreement Protocol with Anonymity for Delay Tolerant Networks

Most of the existing authentication and key agreement protocols for delay tolerant networks are not designed for protecting privacy. In this paper, an authentication and key agreement protocol with anonymity based on combined public key is proposed. The proposed protocol eliminates the need of public key digital certificate on-line retrieval, so that any on-line trusted third party is no longer required, only needs an off-line public information repository and key generation center; and realizes mutual authentication and key agreement with anonymity between two entities. We show that the proposed protocol is secure for all probabilistic polynomial-time attackers, and achieves good security properties, including authentication, anonymity, and confidentiality and so on.