A survey on position-based routing in mobile ad hoc networks

We present an overview of ad hoc routing protocols that make forwarding decisions based on the geographical position of a packet's destination. Other than the destination's position, each node need know only its own position and the position of its one-hop neighbors in order to forward packets. Since it is not necessary to maintain explicit routes, position-based routing does scale well even if the network is highly dynamic. This is a major advantage in a mobile ad hoc network where the topology may change frequently. The main prerequisite for position-based routing is that a sender can obtain the current position of the destination. Therefore, previously proposed location services are discussed in addition to position-based packet forwarding strategies. We provide a qualitative comparison of the approaches in both areas and investigate opportunities for future research     

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.     

Environment-Driven Opportunity Forwarding Cross-Layer Optimization for Ubiquitous Wireless Networks

In this paper, an environment-driven cross-layer optimization scheme is proposed to maximize packet forwarding efficiency. The proposed algorithm is aimed to improve the performance of location-based routing protocol in respect of greedy forwarding and avoid void regions for ubiquitous wireless networks. In greedy forwarding mode, we use a new routing metric IAPS which can estimate the forwarding distance, link quality and the difficulty of channel access during the process of the next hop node selection. When the packet forwarding comes into a local minimum, the proposed scheme uses an opportunistic forwarding method based on competitive advantage to bypass the void regions. NS2 simulation results indicate that the proposed algorithm can improve network resource utilization and the average throughput, and reduce congestion loss rate of wireless multi-hop network comparison with existing GPSR algorithm.     

Intelligent beaconless geographical forwarding for urban vehicular environments

A Vehicular Ad hoc Network is a type of wireless ad hoc network that facilitates ubiquitous connectivity between vehicles in the absence of fixed infrastructure. Source based geographical routing has been proven to perform well in unstable vehicular networks. However, these routing protocols leverage beacon messages to update the positional information of all direct neighbour nodes. As a result, high channel congestion or problems with outdated neighbour lists may occur. To this end, we propose a street-aware, Intelligent Beaconless (IB) geographical forwarding protocol based on modified 802.11 Request To Send (RTS)/ Clear To Send frames, for urban vehicular networks. That is, at the intersection, each candidate junction node leverage digital road maps as well as distance to destination, power signal strength of the RTS frame and direction routing metrics to determine if it should elect itself as a next relay node. For packet forwarding between Intersections, on the other hand, the candidate node considers the relative direction to the packet carrier node and power signal strength of the RTS frame as routing metrics to elect itself based on intelligently combined metrics. After designing the IB protocol, we implemented it and compared it with standard protocols. The simulation results show that the proposed protocol can improve average delay and successful packet delivery ratio in realistic wireless channel conditions and urban vehicular scenarios.     

Energy Efficient Location Error Resilient Connectivity in Wireless Sensor Networks

Geographic routing for realistic conditions is often permeated with localization errors resulting in poor performance and high energy consumption. We propose a simple yet novel geographic routing method to accomplish routing in the presence of location and channel errors. In this algorithm, it is proposed that next hop node is selected based on the combined probability of distance, estimated location error and estimated channel access probability associated with neighbor nodes. The metrics observed for performance were the successful packet delivery rate and the energy consumed. Our algorithms performance is better compared to greedy forwarding techniques of algorithms such as Greedy routing scheme (GRS) and geographic random forwarding (GeRaF). Simulations show the throughput for our algorithm is better compared to others along with reducing the energy wasted on lost packets.

     

Three-dimensional greedy routing in large-scale random wireless sensor networks

In this paper, we investigate how to design greedy routing to achieve sustainable and scalable in a large-scale three-dimensional (3D) sensor network. Several 3D position-based routing protocols were proposed to seek either delivery guarantee or energy-efficiency in 3D wireless networks. However, recent results [1], [2] showed that there is no deterministic localized routing algorithm that guarantees either delivery of packets or energy-efficiency of its routes in 3D networks. In this paper, we focus on design of 3D greedy routing protocols which can guarantee delivery of packets and/or energy-efficiency of their paths with high probability in a randomly deployed 3D sensor network. In particular, we first study the asymptotic critical transmission radius for 3D greedy routing to ensure the packet delivery in large-scale random 3D sensor networks, then propose a refined 3D greedy routing protocol to achieve energy-efficiency of its paths with high probability. We also conduct extensive simulations to confirm our theoretical results.     

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.     

Hop count optimal position-based packet routing algorithms for ad hoc wireless networks with a realistic physical Layer

Existing routing and broadcasting protocols for ad hoc networks assume an ideal physical layer model. We apply the log-normal shadow fading model to represent a realistic physical layer and use the probability p(x) for receiving a packet successfully as a function of distance x between two nodes. We define the transmission radius R as the distance at which p(R)=0.5. We propose a medium access control layer protocol, where receiver node acknowledges packet to sender node u times, where u*p(x)/spl ap/1. We derived an approximation for p(x) to reduce computation time. It can be used as the weight in the optimal shortest hop count routing scheme. We then study the optimal packet forwarding distance to minimize the hop count, and show that it is approximately 0.73R (for power attenuation degree 2). A hop count optimal, greedy, localized routing algorithm [referred as ideal hop count routing (IHCR)] for ad hoc wireless networks is then presented. We present another algorithm called expected progress routing with acknowledgment (referred as aEPR) for ad hoc wireless networks. Two variants of aEPR algorithm, namely, aEPR-1 and aEPR-u are also presented. Next, we propose projection progress scheme, and its two variants, 1-Projection and u-Projection. Iterative versions of aEPR and projection progress attempt to improve their performance. We then propose tR-greedy routing scheme, where packet is forwarded to neighbor closest to destination, among neighbors that are within distance tR. All described schemes are implemented, and their performances are evaluated and compared.     

On energy efficiency of geographic opportunistic routing in lossy multihop wireless networks

Geographic opportunistic routing (GOR) is an emerging technique that can improve energy efficiency in lossy multihop wireless networks. GOR makes local routing decision by using nodes?? location information, and exploits the broadcast nature and spatial diversity of the wireless medium to improve the packet forwarding reliability. In this paper, our goal is to fully understand the principles and tradeoffs in GOR, thus provide insightful analysis and guidance to the design of more efficient routing protocols in multihop wireless networks. We propose a local metric, one-hop energy efficiency (OEE), to balance the packet advancement, reliability and energy consumption in GOR. We identify and prove important properties about GOR on selecting and prioritizing the forwarding candidates in order to maximize the expected packet advancement. Leveraging the proved properties, we then propose two localized candidate selection algorithms with O(N ³) running time to determine the forwarding candidate set that maximizes OEE, where N is the number of available next-hop neighbors. Through extensive simulations, we show that GOR applying OEE achieves better energy efficiency than the existing geographic routing and blind opportunistic routing schemes under different node densities and packet sizes.     

AO2P: ad hoc on-demand position-based private routing protocol

Privacy is needed in ad hoc networks. An ad hoc on-demand position-based private routing algorithm, called AO2P, is proposed for communication anonymity. Only the position of the destination is exposed in the network for route discovery. To discover routes with the limited routing information, a receiver contention scheme is designed for determining the next hop. Pseudo identifiers are used for data packet delivery after a route is established. Real identities (IDs) for the source nodes, the destination nodes, and the forwarding nodes in the end-to-end connections are kept private. Anonymity for a destination relies on the difficulty of matching a geographic position to a real node ID. This can be enforced by the use of secure position service systems. Node mobility enhances destination anonymity by making the match of a node ID with a position momentary. To further improve destination privacy, R-AO2P is proposed. In this protocol, the position of a reference point, instead of the position of the destination, is used for route discovery. Analytical models are developed for evaluating the delay in route discovery and the probability of route discovery failure. A simulator based on ns-2 is developed for evaluating network throughput. Analysis and simulation results show that, while AO2P preserves communication privacy in ad hoc networks, its routing performance is comparable with other position-based routing algorithms.     

无线传感器网络路由协议的设计与实现

针对传统路由协议端到端时延长、丢包率过高的现实问题,提出了一种基于贪婪转发的能量感知多路径路由协议(Greedy Forward Energy-aware Multipath Routing Protocol,GFEMRP)。GFEMRP从传感器起始结点出发,如果遇到网络黑洞则选择周边转发方式,否则将选择吞吐量大、且更接近于目的结点的结点作为下一跳结点。利用了OMNET++5.0和INET框架对包括无线自组网按需平面距离向量路由协议(Ad hoc on-demand distance vector routing protocol,AODV),动态按需无线自组织网络(Dynamic MANET On-demand,DYMO),贪婪周边无状态路由无线网络(Greedy Perimeter Stateless Routing for Wireless Networks,GPSR)和GFEMRP协议在内的四种路由协议进行了仿真和比较,实验结果表明GFEMRP协议具有良好的端到端时延、丢包率等性能。     

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.     

Virtual‐coordinate‐based delivery‐guaranteed routing protocol in three‐dimensional wireless sensor networks

Because of the wide range of applications, many geographic routing protocols have been proposed in three‐dimensional (3D) wireless sensor networks. However, all the methods require assistance from a global positioning system (GPS), which is not always available. In this paper, we propose a method of constructing an axis‐based virtual coordinate assignment in 3D wireless sensor networks (ABVCap_3D) that requires no GPS assistance. We also propose a routing protocol based on ABVCap_3D, which guarantees packet delivery in 3D networks. Using simulations, we evaluate the performance of ABVCap_3D routing and other well‐known routing protocols, such as greedy‐random‐greedy routing, greedy‐hull‐greedy routing, and the routing based on axis‐based virtual coordinate assignment in 2D wireless sensor networks (ABVCap routing). Simulations show that ABVCap_3D routing requires significantly relative lower cost for guaranteeing packet delivery in comparison with ABVCap routing. Simulations also demonstrate that ABVCap_3D routing ensures a moderate ratio for routing path length to the shortest (ideal) path length. Copyright © 2012 John Wiley & Sons, Ltd.     

一种能量平衡的无线体域网络AODV多播路由发现协议

在动态网络拓扑中,AODV协议通过数据源节点S泛洪广播RREQ消息请求到任意目标节点D的路由,而在无线体域网络中,只有一个sink目标节点,除最短跳数路由上的节点外,其他参与RREQ接收和转发的节点浪费了能量。提出了一种能量平衡的无线体域网络AODV多播路由发现协议,通过在节点广播的hello消息中增加到sink的最小跳数hops、到sink的下一跳节点next和节点本身是否具备转发能力isforward 3 个参数,只选择能到达sink节点的邻居节点参与转发RREQ消息,变广播为多播,有效地降低了路由发现的能量开销,并通过能量平衡延长了WBAN的使用寿命。性能分析与模拟实验表明,该协议在RREQ数量、数据传输率和能量消耗等方面优于相似协议EAAODV。     

Localized energy efficient routing in mobile ad hoc networks

We consider the problem of localized energy aware routing in mobile ad hoc networks. In localized routing algorithms, each node forwards a message based on the position of itself, its neighbors and the destination. The objective of energy aware routing algorithms is to minimize the total power for routing a message from source to destination or to maximize the total number of routing tasks that a node can perform before its battery power depletes. In this paper we propose new localized energy aware routing algorithms called OLEAR. The algorithms have very high packet delivery rate with low packet forwarding and battery power consumption. In addition, they ensure good energy distribution among the nodes. Finally, packets reach the destination using smaller number of hops. All these properties make our algorithm suitable for routing in any energy constrained environment. We compare the performance of our algorithms with other existing energy and non‐energy aware localized algorithms. Simulation experiments show that our algorithms present comparable energy consumption and distribution to other energy aware algorithms and better packet delivery rate. Copyright © 2006 John Wiley & Sons, Ltd.     

Planar graph routing on geographical clusters

Geographic routing protocols base their forwarding decisions on the location of the current device, its neighbors, and the packets destination. Early proposed heuristic greedy routing algorithms might fail even if there is a path from source to destination. In recent years several recovery strategies have been proposed in order to overcome such greedy routing failures. Planar graph traversal was the first of those strategies that does not require packet duplication and memorizing past routing tasks. This article introduces a novel recovery strategy based on the idea of planar graph traversal but performing routing tasks along geographical clusters instead of individual nodes. The planar graph construction method discovered so far needs one-hop neighbor information only, but may produce disconnection even if there is a path from source to destination. However, simulation results show that the proposed algorithm is a good choice from a practical point of view, since disconnection does only concern sparse networks, while in dense network the proposed algorithm competes with existing solutions and even outperforms planar graph routing methods based on one-hop neighbor information. This paper finally gives an outline of further research directions which show that geographical clusters may be the key to solve some problems that come along with planar graph routing in wireless networks.     

On Throughput Efficiency of Geographic Opportunistic Routing in Multihop Wireless Networks

Geographic opportunistic routing (GOR) has shown throughput efficiency in coping with unreliable transmissions in multihop wireless networks. The basic idea behind opportunistic routing is to take advantage of the broadcast nature and spacial diversity of the wireless medium by involving multiple neighbors of the sender into the local forwarding, thus improve transmission reliability. The existing GOR schemes typically involve as many as available next-hop neighbors into the local forwarding, and give the nodes closer to the destination higher relay priorities. In this paper, we show that it is not always the optimal way to achieve the best throughput. We introduce a framework to analyze the one-hop throughput of GOR, provide a deeper insight into the trade-off between the benefit (packet advancement and transmission reliability) and cost (medium time delay) associated with the node collaboration, and propose a local metric named expected one-hop throughput (EOT) to balance the benefit and cost. We also identify an upper bound of EOT and its concavity, which indicates that even if the candidate coordination delay were negligible, the throughput gain would become marginal when the number of forwarding candidates increases. Based on the EOT, we also propose a local candidate selection and prioritization algorithm. Simulation results validate our analysis and show that the EOT metric leads to both better one-hop and path throughput than the corresponding pure GOR and geographic routing.     

Low-cost routing in selfish and rational wireless ad hoc networks

Numerous routing protocols have been proposed for wireless networks. A common assumption made by the majority of these protocols is that each wireless node will follow the prescribed protocol without any deviation. This may not be true in practice since wireless nodes could be owned by users who perform in their own interests. We then have to design routing protocols that still work properly even for networks composed of selfish nodes. In this paper, we propose a unicast routing protocol to address this issue under the assumption that all networking nodes are rational. Here, a node is rational if it always chooses a strategy that maximizes its benefit. We assume that each node has a privately known cost of relaying a unit of data for other nodes. In our protocol, each wireless node has to declare a cost for forwarding a unit of data. When a node wants to send data to the access point, it first computes the least cost path to the access point and then computes a payment to each node on this path. We present a pricing mechanism such that the profit of each relay node is maximized when it declares its true cost. We also give a time optimal method to compute the payment in a centralized manner. We then discuss in detail how to implement the routing protocol in the distributed manner. We conduct extensive simulations to study the ratio of the total payment over the total cost incurred by all relay nodes. We find that this ratio is small in practice. Our protocol works when the wireless nodes will not collude and we show that no truthful mechanism can avoid the collusion of any pair of two nodes. We also give a truthful mechanism when a node only colludes with its neighbors.     

Congestion Aware Geographic Routing Protocol for Wireless Ad Hoc and Sensor Networks

Geographic routing protocols forward packets according to the geographical locations of nodes. Thus, the criteria used to select a forwarding node impacts on the performance of the protocols such as energy efficiency and end-to-end transmission delay. In this paper, we propose a congestion aware forwarder selection (CAFS) method for a geographic routing protocol. To design CAFS, we devise a cost function by combining not only the forward progress made to a packet but also the amount of energy required for packet forwarding, forwarding direction, and congestion levels of potential forwarders. Among the potential forwarders, CAFS selects the next forwarder having the minimum cost. In our simulation studies, we compare the performance of CAFS with those of the maximum progress (MP) method and the cost over progress (CoP) method in various network conditions. The results show that compared with MP, the length of a routing path in terms of the number of hops becomes longer when CAFS is used. However, the shorter hop distance helps to avoid unnecessary retransmissions caused by packet loss in a wireless channel. In addition, since CAFS considers congestion levels of candidate forwarders, it reduces the queuing delay in each forwarder. Therefore, CAFS is superior to the MP and the CoP in terms of the energy consumption, end-to-end packet transfer delay, and the successful packet delivery rate.     

A Localized Computing Approach for Connectivity Improvement Analysis in Wireless Personal Networks

A fundamental problem that confronts wireless networks are localization, mobility maintenance and number of neighbors required to maintain the connectivity. To overcome this problem and achieve a better quality of service, a self stability model is introduced, named as localized tree model which includes min and max routing methods. This work is based on node degree, neighbor’s information and coverage area. Based on the mobility requirements of the network, dynamic structures are formed with minimum control load and complexity. Main objective of the research is to obtain the network parameters from the connectivity analysis. The performance of the proposed approach is witnessed by analyzing the parameters like scalability, packet delivery ratio and connectivity efficiency.