Minimizing Recovery State in Geographic Ad Hoc Routing

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, node elevation ad-hoc routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.     

Up-Down Links Dualpath Greedy Routing Protocol for Wireless Sensor Networks

Greedy geographic routing is attractive in wireless sensor networks because of its efficiency and scalability. This paper presents an up-down links dualpath greedy routing (UDLDGR) protocol for wireless sensor networks. The routing protocol not only reserves the features of greedy forwarding algorithm, which is simple, efficient, but also uses different relay nodes to serve as routing nodes for up and down routing paths, makes the energy consumption more balanced. The greatest advantage of UDLDGR is it trades off only small cost for the source node to obtain two different transmission paths information. The multipath strengthens the network reliability, such as load balancing and robustness to failures. Our simulation results show that UDLDGR can improve system lifetime by 20–100% compared to single path approaches.     

Routing in wireless/mobile ad‐hoc networks via dynamic group construction

An ad-hoc network is temporarily formed by a group of mobile hosts communicating over wireless channels without any fixed network interaction and centralized administration. When a mobile host communicates with other mobile hosts in an ad-hoc network, the routes are established via the intermediate mobile hosts as forwarding nodes. Under such a network environment an adaptive approach for routing management will be proposed in this paper. In this approach, at first the network infrastructure is constructed by several communication groups, which are called routing groups. A routing group communicates with other routing groups via the boundary mobile hosts as forwarding nodes. In a routing group the mobile hosts are divided, by means of the dominating values, into two groups – one positive cluster and several non-positive clusters. The nodes in the positive cluster maintain the topology information of the routing group. Under such a construction environment, intra-group routing performs unicasting and gets multiple paths, while inter-group routing performs on group level by propagating the route requests to the boundary clusters, which are called bridge clusters. This routing scheme massively reduces the message complexity that is especially important for system performance under such a resource constraint environment. As far as the dynamic topology characteristics of ad-hoc networks are concerned, this approach also provides a more efficient infrastructure update. Finally, simulation results show that the routing via dynamic group construction outperforms the previous works in message complexity and infrastructure update efficiency. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bayesian inference approach for establishing efficient routes in wireless ad-hoc networks

Mobile ad hoc networks (MANETs) are dynamic wireless networks that have no fixed infrastructures and do not require predefined configurations. In this infrastructure-less paradigm, nodes in addition of being hosts, they also act as relays and forward data packets for other nodes in the network. Due to limited resources in MANETs such as bandwidth and power, the performance of the routing protocol plays a significant role. A routing protocol in MATET should not introduce excessive control messages to the network in order to save network bandwidth and nodes power. In this paper, we propose a probabilistic approach based on Bayesian inference to enable efficient routing in MANETs. Nodes in the proposed approach utilize the broadcast nature of the wireless channel to observe the network topology by overhearing wireless transmissions at neighboring nodes in a distributed manner, and learn from these observations when taking packet forwarding decision on the IP network layer. Our simulation results show that our routing approach reduces the number of control message (routing overhead) by a ratio up to 20 % when the network size is 60 nodes, while maintaining similar average route establishment delay as compared to the ad-hoc on demand routing protocol.     

Secure routing in MANETs using local times

We present a new approach to secure routing in mobile ad-hoc networks based solely on the relative transmission times of overhead packets. Unlike most previous works aimed at securing route computation, we eliminate a key vulnerability (explicitly stated routing metrics) altogether. We introduce the Secure Time-Ordered routing Protocol (STOP), which uses time-based orderings to ensure the establishment of multiple loop-free paths between a source and a destination. STOP is the first routing protocol to use performance-based path selection without source routing, path vectors, or complete topology information, making it far more efficient that similar approaches. We prove that adversaries cannot take any action to manipulate the time-based ordering so as to unfairly gain control of the forwarding topology and, by design, nodes which drop data packets will be avoided. Furthermore, at convergence, traffic load is evenly distributed over the well-performing paths, so adversaries cannot gain complete control over the data flow through temporary good behavior. Simulation results show that the countermeasures in STOP are effective against a variety of attacks from independent and colluding adversaries, and that this improved security does not come at the expense of routing performance.     

Scalable geographic routing algorithms for wireless ad hoc networks

The design of efficient routing protocols for dynamical changing network topologies is a crucial part of building power-efficient and scalable ad hoc wireless networks. If position information is available due to GPS or some kind of relative positioning technique, a promising approach is given by geographic routing algorithms, where each forwarding decision is based on the positions of current, destination, and possible candidate nodes in vicinity only. About 15 years ago heuristic greedy algorithms were proposed, which in order to provide freedom from loops might fail even if there is a path from source to destination. In recent years planar graph traversal has been investigated as one possible strategy to recover from such greedy routing failures. This article provides a tutorial for this class of geographic routing algorithms, and discusses recent improvements to both greedy forwarding and routing in planar graphs.     

Distributed fault-tolerant topology control in wireless multi-hop networks

In wireless multi-hop and ad-hoc networks, minimizing power consumption and at the same time maintaining desired properties of the network topology is of prime importance. In this work, we present a distributed algorithm for assigning minimum possible power to all the nodes in a static wireless network such that the resultant network topology is k-connected. In this algorithm, a node collects the location and maximum power information from all nodes in its vicinity, and then adjusts the power of these nodes in such a way that it can reach all of them through k optimal vertex-disjoint paths. The algorithm ensures k-connectivity in the final topology provided the topology induced when all nodes transmit with their maximum power is k-connected. We extend our topology control algorithm from static networks to networks having mobile nodes. We present proof of correctness for our algorithm for both static and mobile scenarios, and through extensive simulation we present its behavior.     

On Increasing Service Accessibility and Efficiency in Wireless Ad-Hoc Networks with Group Mobility

Wireless ad-hoc networks consist of mobile nodes interconnected by multi-hopwireless paths. Unlike conventional wireless networks, ad-hoc networks haveno fixed network infrastructure or administrative support. Because of thedynamic nature of the network topology and limited bandwidth of wirelesschannels, Quality-of-Service (QoS) provisioning is an inherently complex anddifficult issue. In this paper, we propose a fully distributed and adaptivealgorithm to provide statistical QoS guarantees with respect toaccessibility of services in an ad-hoc network. In this algorithm,we focus on the optimization of a new QoS parameter of interest, serviceefficiency, while keeping protocol overheads to the minimum. To achievethis goal, we theoretically derive the lower and upper bounds of serviceefficiency based on a novel model for group mobility, followed by extensivesimulation results to verify the effectiveness of our algorithm.     

Proficient link state routing in mobile ad hoc network-based deep Q-learning network optimized with chaotic bat swarm optimization algorithm

Mobile ad-hoc network (MANET) is a category of ad-hoc network that can be reconfigurable its network. MANETS are self-organized networks, that can use the wireless links to connect various networks via mobile nodes: but it consumes more energy and it also has routing problems. This is the major drawback of being connected with the MANET technology. Therefore, this study proposes a new protocol as deep Q-learning network optimized with chaotic bat swarm optimization algorithm (CBS)-based optimized link state routing (OLSR) (CBS-OLSR) for MANET. This protocol reduces MANET energy usage and adopts OLSR multi-point relay (MPR) technology. MANET's OLSR and the CBS algorithm utilize a similar method to locate the best optimum path from source to destination node. By embedding the new improved deep Q-learning and OLSR algorithms, both are used for optimizing the MPR sets selection, it can efficiently diminish the energy consumption in the network topology, but automatically increase the lifespan of the network. It also enhances the package delivery ratio and decreases end-to-end delay. The experimental outcomes prove that the proposed protocol is reliable and proficient that is appropriate for numerous MANET applications.     

Cross‐layer optimized routing in wireless sensor networks with duty cycle and energy harvesting

In this paper, we propose a cross‐layer optimized geographic node‐disjoint multipath routing algorithm, that is, two‐phase geographic greedy forwarding plus. To optimize the system as a whole, our algorithm is designed on the basis of multiple layers' interactions, taking into account the following. First is the physical layer, where sensor nodes are developed to scavenge the energy from environment, that is, node rechargeable operation (a kind of idle charging process to nodes). Each node can adjust its transmission power depending on its current energy level (the main object for nodes with energy harvesting is to avoid the routing hole when implementing the routing algorithm). Second is the sleep scheduling layer, where an energy‐balanced sleep scheduling scheme, that is, duty cycle (a kind of node sleep schedule that aims at putting the idle listening nodes in the network into sleep state such that the nodes will be awake only when they are needed), and energy‐consumption‐based connected k‐neighborhood is applied to allow sensor nodes to have enough time to recharge energy, which takes nodes' current energy level as the parameter to dynamically schedule nodes to be active or asleep. Third is the routing layer, in which a forwarding node chooses the next‐hop node based on 2‐hop neighbor information rather than 1‐hop. Performance of two‐phase geographic greedy forwarding plus algorithm is evaluated under three different forwarding policies, to meet different application requirements. Our extensive simulations show that by cross‐layer optimization, more shorter paths are found, resulting in shorter average path length, yet without causing much energy consumption. On top of these, a considerable increase of the network sleep rate is achieved. Copyright © 2014 John Wiley & Sons, Ltd.     

Path selection algorithms for fault tolerance in wireless mesh networks

Recently Wireless Mesh Networks (WMNs) have emerged as a key technology for providing high-bandwidth networking among peer nodes over a specific coverage area. Features such as low cost, ease of deployment, self-configuration and self-healing make them one of the most promising global telecommunication systems. Despite their advantages, however, several research challenges remain in all protocol layers. In this paper, we address the main challenging issues related to the routing aspects in a WMN. Routing in such networks is performed through multi-hop paths where intermediate nodes cooperatively make forwarding decisions based on their knowledge regarding the network topology. However, in an unideal dynamic environment due to frequent or rare node failures/misbehavior, traditional ad-hoc routing protocols suffer from high routing overhead or energy consumption. Motivated by this, we propose several path selection algorithms which adapt to such topology dynamics. The main objective of these routing schemes is to provide fault tolerance without sacrificing the energy and computational complexity efficiency. Numerical investigations, based on extensive simulations, validate the effectiveness of our proposals even when faulty nodes subsist in the environment.     

NARD: Neighbor-assisted route discovery in MANETs

Reactive routing protocols for mobile ad-hoc networks usually discover routes by disseminating control packets across the entire network; this technique is known as brute-force flooding. This paper presents NARD, which stands for neighbor-assisted route discovery protocol for mobile ad-hoc networks. In NARD, a source node floods a limited portion of the network searching not only for the destination node, but also for routing information related to other nodes (called destination-neighbors) that were near the destination node recently. Destination-neighbors can be used as anchor points where a second limited flooding takes place in search for the destination node. Because only two limited portions of the network are flooded by control packets near the source and destination nodes, NARD can significantly reduce signaling overhead due to route-discovery compared with other proposals. Simulations with NS-2 were carried out to verify the validity of our approach.     

Optimal Query-Driven Data Forwarding for Delay-Sensitive Wireless Sensor Networks

Most of existing works on the topic of real-time routing for wireless sensor networks suffer from void forwarding paths (cannot reach the destination, but have to backtrack) and time overhead of handling isolated nodes. Designing a desired real-time data forwarding protocol as well as achieving a good tradeoff between real time and energy efficiency (as well as energy balance) for delay-sensitive wireless sensor networks remains a crucial and challenging issue. In this paper, we propose an optimal query-driven data forwarding framework that each sensor gets its optimal data forwarding paths (directed acyclic graphs) based on the query messages flooded by the base station without extra overhead. Furthermore, First Forwarding Nodes and Second Forwarding Nodes schemes are developed for data forwarding. In addition, two greedy distributed data forwarding algorithms are provided base on hybrid link cost model trying to achieve energy balance and congestion avoidance in data forwarding. Our framework is fully distributed and practical to implement, as well as robust and scalable to topological changes. The extensive simulations show that our framework has significantly outperformed the existing routing protocols in terms of real time and energy efficiency.     

Boundary Mapping and Boundary-State Routing (BSR) in Ad Hoc Networks

This paper presents a geographic routing protocol, boundary state routing (BSR), which consists of two components. The first is an improved forwarding strategy, greedy-bounded compass, which can forward packets around concave boundaries, where the packet moves away from the destination without looping. The second component is a boundary mapping protocol (BMP), which is used to maintain link state information for boundaries containing concave vertices. The proposed forwarding strategy greedy-bounded compass is shown to produce a higher rate of path completion than Greedy forwarding and significantly improves the performance of greedy perimeter state routing (GPSR) in sparse networks when used in place of greedy forwarding. The proposed geographic routing protocol BSR is shown to produce significant improvements in performance in comparison to GPSR in sparse networks due to informed decisions regarding the direction of boundary traversal at local minima.     

An implementation framework for trajectory-based routing in ad hoc networks

Routing in ad hoc networks is a complicated task because of many reasons. The nodes are low-memory, low-powered, and they cannot maintain routing tables large enough for well-known routing protocols. Because of that, greedy forwarding at intermediate nodes is desirable in ad hoc networks. Also, for traffic engineering, multi-path capabilities are important. So, it is desirable to define routes at the source like in source based routing (SBR) while performing greedy forwarding at intermediate nodes.We investigate trajectory-based routing (TBR) which was proposed as a middle-ground between SBR and greedy forwarding techniques. In TBR, source encodes trajectory to be traversed and embeds it into each packet. Upon the arrival of each packet, intermediate nodes decode the trajectory and employ greedy forwarding techniques such that the packet follows its trajectory as much as possible.In this paper, we address various issues regarding implementation of TBR. We also provide techniques to efficiently forward packets along a trajectory defined as a parametric curve. We use the well-known Bezier parametric curve for encoding trajectories into packets at source. Based on this trajectory encoding, we develop and evaluate various greedy forwarding algorithms     

On-demand loop-free routing with link vectors

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request (RREQ) to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast RREQ to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform dynamic source routing, ad hoc on-demand distance vector, optimized link-state routing protocol, and topology broadcast based on reverse-path forwarding, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.     

车载Ad hoc网络基于转发能力预测的路由策略

在车载Ad hoc网络中,节点的高速移动导致全网拓扑的频繁变化,以街道为单位的路由策略更加高效。传统的研究中使用街道的静态信息或者瞬时的动态信息选择路由路径。前者忽略了车辆节点的动态分布,后者中,精确的全局动态信息获取困难且开销巨大。文章提出街道转发能力来评估街道的路由特性,并预测其持续时间。基于街道转发能力的预测,本文设计了结合静态长度和动态信息的路由策略。仿真结果表明,本策略可以显著提高路由性能。     

An evaluation of routing in vehicular networks using analytic hierarchy process

This paper presents a comprehensive study of the performance of routing protocols in distributed vehicular networks. We propose a novel and efficient routing protocol, namely cross‐layer, weighted, position‐based routing, which considers link quality, mobility and utilisation of nodes in a cross layer manner to make effective position‐based forwarding decisions. An analytic hierarchy process approach is utilised to combine multiple decision criteria into a single weighting function and to perform a comparative evaluation of the effects of aforementioned criteria on forwarding decisions. Comprehensive simulations are performed in realistic representative urban scenarios with synthetic and real traffic. Insights on the effect of different communication and mobility parameters are obtained. The results demonstrate that the proposed protocol outperforms existing routing protocols for vehicular ad hoc networks, including European Telecommunications Standards Institute (ETSI's) proposed greedy routing protocol, greedy traffic aware routing protocol and advanced greedy forwarding in terms of combined packet delivery ratio, end‐to‐end delay and overhead. Copyright © 2015 John Wiley & Sons, Ltd.     

GeoSVR: A map-based stateless VANET routing

Compared with traditional routing techniques, geographic routing has been proven to be more suitable for highly mobile environments like Vehicular Ad-Hoc Networks (VANETs) because of enhanced scalability and feasibility. These routings use greedy modes or forwarding paths to forward packets. However, the dynamic nature of vehicular network such as frequently changed topology, vehicles density and radio obstacles, could create local maximum, sparse connectivity and network partitions. We propose GeoSVR, a geographic stateless routing combined with node location and digital map. The proposed GeoSVR scheme enhances forwarding path to solve local maximum and sparse connectivity problem, and the proposed restricted forwarding algorithm overcomes unreliable wireless channel issues. In our study, simulations and real world experiments were conducted to evaluate the efficacy and efficiency of the proposed solution. Our results show GeoSVR can provide higher packet delivery ratio with comparable latency to other geographic routing schemes.