Routing protocols for Mobile Ad Hoc Networks (MANETs) have been extensively studied for more than fifteen years. Position-based routing protocols route packets towards the destination using greedy forwarding (i.e., an intermediate node forwards packets to a neighbor that is closer to the destination than itself). Different position-based protocols use different strategies to pick the neighbor to forward the packet. If a node has no neighbor that is closer to the destination than itself, greedy forwarding fails. In this case, we say there is void (no neighboring nodes) in the direction of the destination. Different position-based routing protocols use different methods for dealing with voids. In this paper, we use a simple backtracking technique to deal with voids and design a position-based routing protocol called "Greedy Routing Protocol with Backtracking (GRB)". We compare the performance of our protocol with the well known Greedy Perimeter Stateless Routing (GPSR) routing and the Ad-Hoc On-demand Distance Vector (AODV) routing protocol as well as the Dynamic Source Routing (DSR) protocol. Our protocol needs much less routing-control packets than those needed by DSR, AODV, and GPSR. Simulation results also show that our protocol has a higher packet-delivery ratio, lower end-to-end delay, and less hop count on average than AODV.
@cite_22 proposed localized load-aware geographic routing using the concept of cost-to-progress ratio in greedy routing (CPR-Routing). The main idea behind this protocol is to combine the greedy forwarding technique and localized cost-to-progress ratio (CPR) @cite_6 . The load awareness used in this protocol tends to minimize load and maximize progress geographically towards the destination; however, this is difficult to achieve, so it tries to balance the two factors in making routing decisions. A drawback of this approach is the complexity involved in the calculation for selecting appropriate neighbor to forward a packet which could result in higher end-to-end delay.
@cite_22 @cite_6
2052957359 1974718755 2110159784 2100013559
We propose to apply the concept of Cost-to-Progress Ratio (CPR) in greedy routing for load reduction and balancing. The load of a node is the percentage of time it is occupied by forwarding traffic or inability to forward due to interference. The resultant routing protocol, named CPR-routing, is a localized parameterless approach, optimizing the ratio of nodal load and geographic progress. Through extensive simulation, we evaluate it in comparison with an existing parameter-based localized solution, α-routing. Our simulation results indicate that CPR-routing outperforms α-routing in per node load, success rate, and average hop count. Greedy geographic routing is attractive for large multi-hop wireless networks because of its simple and distributed operation. However, it may easily result in dead ends or hotspots when routing in a network with obstacles (regions without sufficient connectivity to forward messages). In this paper, we propose a distributed routing algorithm that combines greedy geographic routing with two non-Euclidian distance metrics, chosen so as to provide load balanced routing around obstacles and hotspots. The first metric, Local Shortest Path, is used to achieve high probability of progress, while the second metric, Weighted Distance Gain, is used to select a desirable node among those that provide progress. The proposed Load Balanced Local Shortest Path (LBLSP) routing algorithm provides loop freedom, guarantees delivery when a path exists, is able to efficiently route around obstacles, and provides good load balancing. In this article we propose several new progress based, localized, power, and cost aware algorithms for routing in ad hoc wireless networks. These algorithms attempt to minimize the total power and or cost needed to route a message from source to destination. In localized algorithms, each node makes routing decisions solely on the basis of location of itself, its neighbors and destination. The new algorithms are based on the notion of proportional progress. A node currently holding the packet will forward it to a neighbor, closer to destination than itself, which minimizes the ratio of power and or cost to reach that neighbor, and the progress made, measured as the reduction in distance to destination, or projection along the line to destination. First, we propose Power Progress, Iterative Power Progress, Projection Power Progress, and Iterative Projection Power Progress algorithms, where the proportional progress is defined in terms of power measure. The power metrics are then replaced by cost or power-co... We propose a novel localized routing protocol for wireless sensor networks (WSN) that is energy-efficient and guarantees delivery. We prove that it is constant factor of the optimum for dense networks. To forward a packet, a node s in graph G computes the cost of the energy weighted shortest path (SP) between s and each of its neighbors which are closer to the destination than itself. It then selects node x which minimizes the ratio of the cost of the SP to the progress towards the destination. It then sends the message to the first node on the SP from s to x: say node x'. Node x' restarts the same greedy routing process until the destination is reached or the routing fails. To recover from failure, our algorithm invokes face routing that guarantees delivery. This work is the first to optimize energy consumption of face routing. First, we build a connected dominating set from graph G, second we compute its Gabriel graph to obtain the planar graph G'. Face routing is applied on G' only to decide which edges to follow in the recovery process. On each edge, greedy routing is used. This two-phase (greedy-Face) end-to-end routing process (EtE) reiterates until the final destination is reached. Simulation results show that EtE outperforms several existing geographical routing on energy consumption metric.