Contention aware mobility prediction routing for intermittently connected mobile networks

This paper introduces a novel multi-copy routing protocol, called predict and forward (PF), for delay tolerant networks, which aims to explore the possibility of using mobile nodes as message carriers for end-to-end delivery of the messages. With PF, the message forwarding decision is made by manipulating the probability distribution of future inter-contact and contact durations based on the network status, including wireless link condition and nodal buffer availability. In particular, PF is based on the observations that the node mobility behavior is semi-deterministic and could be predicted once there is sufficient mobility history information. We implemented the proposed protocol and compared it with a number of existing encounter-based routing approaches in terms of delivery delay, delivery ratio, and the number of transmissions required for message delivery. The simulation results show that PF outperforms all the counterpart multi-copy encounter-based routing protocols considered in the study.     

Routing for disruption tolerant networks: taxonomy and design

Communication networks, whether they are wired or wireless, have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links (e.g. due to wireless propagation phenomena and node mobility) will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected, i.e., most of the time, end-to-end paths connecting every node pair do not exist. To cope with frequent, long-lived disconnections, opportunistic routing techniques have been proposed in which, at every hop, a node decides whether it should forward or store-and-carry a message. Despite a growing number of such proposals, there still exists little consensus on the most suitable routing algorithm(s) in this context. One of the reasons is the large diversity of emerging wireless applications and networks exhibiting such “episodic” connectivity. These networks often have very different characteristics and requirements, making it very difficult, if not impossible, to design a routing solution that fits all. In this paper, we first break up existing routing strategies into a small number of common and tunable routing modules (e.g. message replication, coding, etc.), and then show how and when a given routing module should be used, depending on the set of network characteristics exhibited by the wireless application. We further attempt to create a taxonomy for intermittently connected networks. We try to identify generic network characteristics that are relevant to the routing process (e.g., network density, node heterogeneity, mobility patterns) and dissect different “challenged” wireless networks or applications based on these characteristics. Our goal is to identify a set of useful design guidelines that will enable one to choose an appropriate routing protocol for the application or network in hand. Finally, to demonstrate the utility of our approach, we take up some case studies of challenged wireless networks, and validate some of our routing design principles using simulations.     

Generic prediction assisted single-copy routing in underwater delay tolerant sensor networks

One challenge in delay tolerant networks (DTNs) is efficient routing, as the lack of contemporaneous end-to-end paths makes conventional routing schemes inapplicable. Although many DTN routing protocols have been proposed, they often have two limitations: many protocols are not mobility cognizant, so they only suit specific mobility models and become inefficient when the environment changes; some protocols employ multi-copy replication to accommodate mobility diversity for increased delivery probability or reduced delay, but they usually do not perform well in resource constrained networks. Due to the unique characteristics of underwater sensor networks (UWSNs), efficient DTN routing becomes even more challenging. In this paper, we propose a generic prediction assisted single-copy routing (PASR) scheme that can be instantiated for different mobility models. PASR first collects a short-duration trace with network connectivity information and employs an effective off-line greedy algorithm to characterize the underlying network mobility patterns, depict the features of best routing paths and provide guidance on how to use historical information. Then it instantiates prediction assisted single-copy online routing protocols based on the guidance. As a result, the instantiated protocols are energy efficient and cognizant of the underlying mobility patterns. We demonstrate the advantages of PASR in underwater sensor networks with various mobility models.     

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.     

基于网络编码的机会网络高效路由算法

针对采用Epidemic机制的机会网络路由算法在数据分组传送阶段存在通信冗余的问题,提出了一种基于网络编码的高效路由算法--NCBER(network-coding-based epidemic routing）。NCBER在传送数据分组的过程中使用主动异或网络编码和多播,并取消了 Request（请求）控制分组,从而减少数据分组的转发次数和控制分组数量,降低网络开销,缩短分组传输时延。理论分析和仿真结果表明,NCBER 算法在网络开销和数据分组端到端时延性能方面优于经典的Epidemic路由算法及其改进算法MRRMR（message redundancy removal of multi-copy routing）,并且使数据传送成功率保持在100%。     

Connectivity-aware minimum-delay geographic routing with vehicle tracking in VANETs

In this paper, we propose the connectivity-aware minimum-delay geographic routing (CMGR) protocol for vehicular ad hoc networks (VANETs), which adapts well to continuously changing network status in such networks. When the network is sparse, CMGR takes the connectivity of routes into consideration in its route selection logic to maximize the chance of packet reception. On the other hand, in situations with dense network nodes, CMGR determines the routes with adequate connectivity and selects among them the route with the minimum delay. The performance limitations of CMGR in special vehicular networking situations are studied and addressed. These situations, which include the case where the target vehicle has moved away from its expected location and the case where traffic in a road junction is so sparse that no next-hop vehicle can be found on the intended out-going road, are also problematic in most routing protocols for VANETs. Finally, the proposed protocol is compared with two plausible geographic connectivity-aware routing protocols for VANETs, A-STAR and VADD. The obtained results show that CMGR outperforms A-STAR and VADD in terms of both packet delivery ratio and ratio of dropped data packets. For example, under the specific conditions considered in the simulations, when the maximum allowable one-way transmission delay is 1 min and one gateway is deployed in the network, the packet delivery ratio of CMGR is approximately 25% better than VADD and A-STAR for high vehicle densities and goes up to 900% better for low vehicle densities.     

Exploiting Contact Spatial Dependency for Opportunistic Message Forwarding

The movement of real users often follows patterns that can be characterized by certain statistical metrics of the contacts. Such metrics are useful for routing decisions, especially in sparse mobile ad hoc networks where node connectivity is opportunistic and messages are delivered using store-carry-forward routing. Past analysis on real-world data traces indicates that human behaviors affect the node contact pattern and spatial dependency exists among mobile nodes. A new metric called the expected dependent delay that characterizes the expected delay of a contact dependent on the previous hop is proposed. It characterizes the spatial dependency between neighboring contact pairs and reflects the regularity in node movement. In sparse opportunistic mobile ad hoc networks, a good approximation of the expected delay of a multihop path can be derived as the sum of the expected delay of the first hop and the expected dependent delays of later hops. We apply the proposed path-delay estimation to end-to-end routing. Simulation results show that compared with routing schemes that consider only the delivery probability or the expected delay, the proposed scheme can reduce the message delay significantly, when the network is sufficiently sparse and the spatial dependency is quantitatively constant over time. Moreover, the proposed method is tractable and can be easily implemented in combination with other routing techniques such as multipath routing and per-contact routing.     

Routing protocols for vehicular Ad Hoc networks in rural areas

Research on vehicular ad hoc networks has focused mainly on efficient routing protocol design under conditions where there are relatively large numbers of closely spaced vehicles. These routing protocols are designed principally for urban areas with high node density and fully connected networks and are not suitable for packet delivery in a sparse, partially connected VANET. In this article, we examine the challenges of VANETs in sparse network conditions, review alternatives including epidemic routing, and propose a border node-based routing protocol for partially connected VANETs. The BBR protocol can tolerate network partition due to low node density and high node mobility. The performance of epidemic routing and BBR are evaluated with a geographic and traffic information- based mobility model that captures typical highway conditions. The simulation results show that under rural network conditions, a limited flooding protocol such as BBR performs well and offers the advantage of not relying on a location service required by other protocols proposed for VANETs.     

Analysis of broadcasting delays in vehicular ad hoc networks

High mobility of nodes in vehicular ad hoc networks (VANETs) may lead to frequent breakdowns of established routes in conventional routing algorithms commonly used in mobile ad hoc networks. To satisfy the high reliability and low delivery‐latency requirements for safety applications in VANETs, broadcasting becomes an essential operation for route establishment and repair. However, high node mobility causes constantly changing traffic and topology, which creates great challenges for broadcasting. Therefore, there is much interest in better understanding the properties of broadcasting in VANETs. In this paper we perform stochastic analysis of broadcasting delays in VANETs under three typical scenarios: freeway, sparse traffic and dense traffic, and utilize them to analyze the broadcasting delays in these scenarios. In the freeway scenario, the analytical equation of the expected delay in one connected group is given based on statistical analysis of real traffic data collected on freeways. In the sparse traffic scenario, the broadcasting delay in an n‐vehicle network is calculated by a finite Markov chain. In the dense traffic scenario, the collision problem is analyzed by different radio propagation models. The correctness of these theoretical analyses is confirmed by simulations. These results are useful to provide theoretical insights into the broadcasting delays in VANETs. Copyright © 2010 John Wiley & Sons, Ltd.     

面向可扩展的VANETs混合路由的研究与仿真

车载网VANETs(Vehicular ad hoc networks)属于高速移动的无线网络,可供车辆安全、交通监测以及其他的商业服务的应用。然而,为此,提出混合式的位VANETs中车辆的快速移动导致通信链路频繁地断裂,增加路由开销,降低了可扩展性。议地理位置路由的特点。HLAR(Hybrid location-based ad hoc routing)。HLAR结合了反应式路由、HLAR克服了反应式路由的扩展性问题,并改善了地理位置路由对位置误差的敏感性。同时,通过理论分析,量可扩展性,并推导了路由开销的表达式。通过分析、仿真表明,提出的路由协议具有很好的扩展性,并降低了路由开销。在仿真中引入位置误差因子,结果表明。同时,与同类的其他协议相比,输时延方面HLAR到对位置误差具有很强的鲁棒性HLAR在数据传输率、端到端传提升。     

Message redundancy removal of multi-copy routing in delay tolerant MANET

This article puts forward a new scheme to control message redundancy efficiently in delay tolerant mobile Ad-hoc networks(MANET).The class of networks generally lacks end-to-end connectivity.In order to improve the efficiency that messages are delivered successfully,multiple message copies routing protocols are usually used,but the network load is increased due to a large number of message redundancies.In the study,by using counter method,every node adds an encounter counter based on epidemic routing scheme...     

Routing in Delay-Tolerant Networks Comprising Heterogeneous Node Populations

Communication networks are traditionally assumed to be connected. However, emerging wireless applications such as vehicular networks, pocket-switched networks, etc., coupled with volatile links, node mobility, and power outages, will require the network to operate despite frequent disconnections. To this end, opportunistic routing techniques have been proposed, where a node may store-and-carry a message for some time, until a new forwarding opportunity arises. Although a number of such algorithms exist, most focus on relatively homogeneous settings of nodes. However, in many envisioned applications, participating nodes might include handhelds, vehicles, sensors, etc. These various "classes” have diverse characteristics and mobility patterns, and will contribute quite differently to the routing process. In this paper, we address the problem of routing in intermittently connected wireless networks comprising multiple classes of nodes. We show that proposed solutions, which perform well in homogeneous scenarios, are not as competent in this setting. To this end, we propose a class of routing schemes that can identify the nodes of "highest utility” for routing, improving the delay and delivery ratio by four to five times. Additionally, we propose an analytical framework based on fluid models that can be used to analyze the performance of various opportunistic routing strategies, in heterogeneous settings.     

Reinforcement Learning Based Mobility Adaptive Routing for Vehicular Ad-Hoc Networks

Vehicular ad-hoc networks (VANETs) is drawing more and more attentions in intelligent transportation system to reduce road accidents and assist safe driving. However, due to the high mobility and uneven distribution of vehicles in VANETs, multi-hops communication between the vehicles is still particularly challenging. Considering the distinctive characteristics of VANETs, in this paper, an adaptive routing protocol based on reinforcement learning (ARPRL) is proposed. Through distributed Q-Learning algorithm, ARPRL constantly learns and obtains the fresh network link status proactively with the periodic HELLO packets in the form of Q table update. Therefore, ARPRL’s dynamic adaptability to network changes is improved. Novel Q value update functions which take into account the vehicle mobility related information are designed to reinforce the Q values of wireless links by exchange of HELLO packets between neighbor vehicles. In order to avoid the routing loops caused in Q learning process, the HELLO packet structure is redesigned. In addition, reactive routing probe strategy is applied in the process of learning to speed up the convergence of Q learning. Finally, the feedback from the MAC layer is used to further improve the adaptation of Q learning to the VANETs environment. Through simulation experiment result, we show that ARPRL performs better than existing protocols in the form of average packet delivery ratio, end-to-end delay and number hops of route path while network overhead remains within acceptable ranges.     

Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case

Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from the source to the destination. There are many real networks that follow this model, for example, wildlife tracking sensor networks, military networks, vehicular ad hoc networks (VANETs), etc. In this context, conventional routing schemes would fail, because they try to establish complete end-to-end paths, before any data is sent. To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention which can significantly degrade their performance. With this in mind, we look into a number of ldquosingle-copyrdquo routing schemes that use only one copy per message, and hence significantly reduce the resource requirements of flooding-based algorithms. We perform a detailed exploration of the single-copy routing space in order to identify efficient single-copy solutions that (i) can be employed when low resource usage is critical, and (ii) can help improve the design of general routing schemes that use multiple copies. We also propose a theoretical framework that we use to analyze the performance of all single-copy schemes presented, and to derive upper and lower bounds on the delay of any scheme.     

A mobicast routing protocol with carry‐and‐forward in vehicular ad hoc networks

In vehicular networks, safety and comfort applications are two quite different kinds of applications to avoid the emergency traffic accident and enjoy the non‐emergency entertainment. The comfort application drives the challenges of new non‐emergency entertainments for vehicular ad hoc networks (VANETs). The comfort application usually keeps the delay‐tolerant capability; that is, messages initiated from a specific vehicle at time t can be delivered through VANETs to some vehicles within a given constrained delay time λ. In this paper, we investigate a new mobicast protocol to support comfort applications for a highway scenario in VANETs. All vehicles are located in a geographic zone (denoted as zone of relevance (ZOR)) at time t; the mobicast routing must disseminate the data message initiated from a specific vehicle to all vehicles that have ever appeared in ZOR at time t. This data dissemination must be performed before time t + λ through the carry‐and‐forward technique. In addition, the temporary network fragmentation problem is considered in our protocol design. Also, the low degree of channel utilization is kept to reserve the resource for safety applications. To illustrate the performance achievement, simulation results are examined in terms of message overhead, dissemination success rate, and accumulative packet delivery delay. Copyright © 2012 John Wiley & Sons, Ltd.     

A graph structure approach to improving message dissemination in vehicular networks

Efficient message dissemination in vehicular ad-hoc networks (VANETs) is crucial for supporting communication among vehicles and also between users and the Internet, with minimal delay and overhead but maximum reachability. To improve the message dissemination in these networks, we show the need to study the graph-theoretic properties of VANETs, since they neither follow the small-world nor the scale-free network characteristics often found in large self-organized networks. We consider three fundamental properties: connectivity, node degree, and clustering coefficient. For each property, we develop and validate analytical models for both the urban and highway scenarios, building an extensive graph structure perspective on VANETs. With this, we see how connectivity changes with network density, that VANETs exhibit truncated Gaussian node degree distributions, and that network clustering coefficients do not depend on the network’s size or density. We then show how these results can be used to generate individual behavior favorable to the whole network using local information. The usefulness of this new approach is demonstrated by proposing new mechanisms to enhance the urban vehicular broadcasting protocol UV-CAST. Our results show that these new mechanisms lead to excellent performance while reducing the overhead in the UV-CAST protocol.     

Avoidance of multicast incapable branching nodes for multicast routing in WDM networks

In this article we study the multicast routing problem in all-optical WDM networks under the spare light splitting constraint. To implement a multicast session, several light-trees may have to be used due to the limited fanouts of network nodes. Although many multicast routing algorithms have been proposed in order to reduce the total number of wavelength channels used (total cost) for a multicast session, the maximum number of wavelengths required in one fiber link (link stress) and the end-to-end delay are two parameters which are not always taken into consideration. It is known that the shortest path tree (SPT) results in the optimal end-to-end delay, but it can not be employed directly for multicast routing in sparse light splitting WDM networks. Hence, we propose a novel wavelength routing algorithm which tries to avoid the multicast incapable branching nodes (MIBs, branching nodes without splitting capability) in the shortest-path-based multicast tree to diminish the link stress. Good parts of the shortest-path-tree are retained by the algorithm to reduce the end-to-end delay. The algorithm consists of tree steps: (1) a DijkstraPro algorithm with priority assignment and node adoption is introduced to produce a SPT with up to 38% fewer MIB nodes in the NSF topology and 46% fewer MIB nodes in the USA Longhaul topology, (2) critical articulation and deepest branch heuristics are used to process the MIB nodes, (3) a distance-based light-tree reconnection algorithm is proposed to create the multicast light-trees. Extensive simulations demonstrate the algorithm’s efficiency in terms of link stress and end-to-end delay.     

Information routing and reliability issues in distributed sensornetworks

Communication issues and problems in information routing in distributed sensor networks (DSNs) are considered. Two important communication constraints, viz., the delay constraint and the reliability constraint, are identified, and their impact on information routing is discussed. It is shown that the maximum end-to-end delay in a network depends on the diameter of the network, and efficient distributed algorithms are presented to determine the diameter of asynchronous networks. A distributed algorithm that determines the diameter of an asynchronous tree network when an arbitrary node in the network initiates the algorithm is introduced. An efficient algorithm for determining the diameter when multiple nodes initiate the algorithm is presented. An algorithm to determine the diameter of arbitrary networks is presented, and its message complexity is shown. Effects of link/node failures on network delay are studied, and important network structure design criterion are discussed. The distributed, dynamic routing algorithms are reviewed, and their adaptation to DSN environments is discussed     

Secure Multi-copy Routing in Compromised Delay Tolerant Networks

Routing in delay tolerant networks (DTNs) is challenging due to their unique characteristics of intermittent node connectivity. Different protocols (single-, multi-copy, erasure-coding-based etc.) utilizing store-carry-and-forward paradigm have been proposed to achieve routing of messages in such environments by opportunistic message exchanges between nodes that are in the communication range of each other. The sparsity and distributed nature of these networks together with the lack of stable connectivity between source destination pairs make these networks vulnerable to malicious nodes which might attempt to learn the content of the messages being routed between the nodes. In this paper, we study DTNs in which malicious nodes are present, to which we refer to as compromised DTNs. We discuss and analyze the effects of presence of malicious nodes on routing of messages in compromised DTNs. We propose a two period routing approach which aims at achieving the desired delivery ratio by a given delivery deadline in presence of malicious nodes. Our simulation results with both random networks and real DTN traces show that, with proper parameter setting, the proposed method can achieve delivery ratios which surpass those reached by other algorithms by a given delivery deadline.     

Multi-hop routing with cooperative transmission: a cross-layer approach

Cooperative diversity techniques have received a lot of attention recently due to their ability to provide spatial diversity in fading wireless environment without the requirement of implementing multiple antenna on the same device. It increases link reliability, provides higher capacity, reduces transmit power, and extends transmission range for the same level of performance and modulation rate. In this paper, we study the achievable gain of cooperative communications from a wireless cross-layer point of view in multi hop networks. We propose two routing algorithms applicable for wireless ad hoc networks. First, we propose an edge node based on a greedy cooperative routing (ENBGCR) algorithm, where we modify the geographic routing algorithm to incorporate the cooperative transmission and extend the coverage range of the nodes. The main objective of ENBGCR algorithm is to minimize the number of hops that messages transverse to reach their destination. Then the energy-efficient cooperative routing algorithm is proposed to minimize the end-to-end total transmission power subject to end-to-end target data rate. Simulation results for both algorithms show that the proposed strategies have great improvement in terms of delay and power saving respectively for the same quality of service requirement as compared to traditional algorithms.