Efficient Void Handling Technique For Geographic Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract-Geographic routing uses location information to forward data packets, in a hop-by-hop routing fashion. Greedy forwarding is used to select next hop forwarder with the largest positive progress towards the destination. Communication voids are the most intolerable events that occurred at the time of transmission, where geographic greedy forwarding fails to move a packet further towards its destination, are an important issue for geographic routing in Mobile adhoc networks. This article presents a survey on currently available various void-handling techniques for geographic routing based on void problem to find an efficient void-handling technique for Geographic routing.

Keywords- MANET, GPSR, POR, Boundhole, PAGER-M, PSGR, BLR, TENT


MOBILE ad hoc networks (MANETs) have gained a great deal of attention because of its significant advantages brought about by multihop, infrastructure-less transmission. However, due to the error prone wireless channel and the dynamic network topology, reliable data delivery in MANETs, especially in challenging environments with high mobility remains an issue. Traditional topology-based MANET routing protocols (e.g., DSDV, AODV, DSR [1]) are quite susceptible to node mobility. One of the main reasons is due to the predetermination of an end-to-end route before data transmission. Owing to the constant and even faster changing network topology, it is very difficult to maintain a deterministic route. The discovery and recovery procedures are also time and energy consuming. Once the path breaks, the data packets will get lost or be delayed for a long time until the reconstruction of the route, causing transmission interruptions.

Geographic routing, which is often called position based, location-based, or directional routing, was originally proposed for packet radio networks in the early 80's [2, 3]. In recent years, with the rapid application of Global Positioning System (GPS) [4] and the progress on self configuring localization mechanisms [5, 6], it has regained significant attention, as it provides a promising solution for information delivery in next-generation wireless networks like Mobile Ad Hoc Networks (MANETs), Vehicular Ad Hoc Networks (VANETs), Wireless Sensor Networks (WSNs), and Wireless Mesh Networks (WMNs). Geographic routing exploits the geographic information instead of topological connectivity information to move data packets to gradually approach and eventually reach the intended destination. In most geographic routing protocols, only one-hop geographic information of neighbouring nodes is exploited. Thus, geographic routing does not require the establishment or maintenance of complete routes from sources to destinations [7]. The localized operation and the stateless feature of geographic routing make it simple and scalable. Geographic routing also enables a geocasting service, which supports the delivery of packets to all nodes in a specified geographic region [8].

Geographic routing mainly relies on an extremely simple geographic greedy-forwarding strategy at every hop to move a data packet to a locally optimal next-hop node with a positive progress towards the destination node. It is straightforward to show that it is very likely for a loop to form on the route, provided that a negative progress is allowed. However, greedy forwarding may not always be possible. For example, what if all the neighbouring nodes of a sender are farther away from the destination node than the sender itself? That is, a sender fails to locate a next-hop node in its neighbourhood which has a positive geographic progress towards the destination node. This undesirable phenomenon, called a communications void, is often also referred to as local maximum phenomenon [7]

Communications void [9] is a challenging problem for geographic routing and, in order to enable the use of geographic routing in next-generation wireless networks, this problem must be tackled. Although a dense deployment of wireless nodes can reduce the likelihood of the occurrence of a void in the network, it is still possible for some packets to encounter voids that are induced by obstacles, unreliable nodes, the boundaries of a wireless network, and the like. These packets have to be discarded when only a single greedy-forwarding strategy is used, even though a topologically valid path to the destination node may still exist. Thus, it is imperative to design a void-handling technique for geographic routing in an effective and efficient manner.

Our contribution in this article is to survey the various void-handling techniques for geographic routing in Mobile adhoc networks. First we have stated out the problems in Geographic routing and Void handling. We have given a brief description about the various Void Handling Techniques then we have made a survey based on these void handling techniques depending upon various Geographic Routing Protocols.


Geographic routing [7] usually consists of two main elements: a location service and a geographic forwarding strategy. The location service is responsible for determining the position of the packet destination, before a packet can be sent from a source node. The position of the packet destination is then carried in the header of the packet so that intermediate hops can learn where the packet is destined for. Geographic forwarding operates in two modes: geographic greedy-forwarding mode and void- handling mode. In the greedy-forwarding mode, selection of a next-hop node for packet forwarding is made according to the positions of the current node, its neighbouring nodes, and the destination node. A node can determine its own position either by pre configuration if the node is stationary, or via a GPS receiver, or through localization algorithms. In Void handling mode the source node attempts to route the packet around the void because it is very likely that a topologically valid path from the source to the destination node exists.

The existence of communications voids is a serious problem and how to handle voids in an effective and efficient manner is an important technical challenge for any viable geographic routing protocol. Due to the unpredictable patterns of node deployment and the uncertain dynamics of time varying wireless network environments, it is impossible to predict when and where a void will occur. Without an appropriate void-handling technique in place, some data packets may get lost in the network, wasting precious network resources as well as disabling communications between some pairs of nodes in a wireless network. The simplest void-handling technique is flooding, initiated at a void node and executed afterward at all the nodes receiving the stuck packet for the first time. The technique will certainly enable the packet to reach the destination if at least a path exists. However, this technique is effective but inefficient in terms of resource utilization, because every other node in the network has to forward the packet once and the destination node may receive too many unnecessary copies of the same data packet from different paths. In addition, the first copy of the stuck packet arriving at the destination may not follow the optimal path from the void node to the destination [9]. Note that a void handling technique is invoked only when a data packet encounters a void and greedy forwarding fails at the void node. Once the stuck data packet overcomes the void or reaches a node that is closer to the destination than the void node, greedy forwarding is then reactivated for the packet.


In this section we survey the various void-handling techniques. For an in-depth understanding of these techniques, we separate these techniques from their relevant geographic routing protocols. That is, we present basic principles and inherent characteristics of these techniques, independent of other components of geographic routing as well as of any wireless network environment with specific network characteristics. We classify the void-handling techniques into the following seven categories of approaches employed: planar graph- based, geometric, flooding-based, cost-based, heuristic, virtual destination based and hybrid.

Planar-graph-based Void-Handling Technique

In graph theory, a planar graph is a graph that can be embedded in the plane so that no edges intersect. On an embedding of the planar graph, a simple planar graph traversal approach can be used to find a path towards the destination, based on the ancient idea of the right-hand rule, which states that it is possible to traverse every wall in a maze by keeping one's right hand against the wall while walking forward. In a wireless network, a set of nodes can be considered a unit disk graph in which the nodes are vertices and an edge exists between two vertices if their distance is less than r, where r is the radio range for a wireless node. Here, we assume that all nodes in the network have the uniform radio range of a disk of radius r. Theoretically, it has been shown that a planar-graph based technique guarantees packet delivery [10] because planar graph traversal ensures that a path is discovered if there does exist a topologically valid path.

The performance of a planar-graph-based void-handling technique depends not only on the performance of the planar graph traversal algorithm, but also on the performance of the distributed planarization algorithm. In the following, we review some planar graph-based void handling techniques.

Perimeter Routing: Perimeter routing, as the complete void handling technique in the GPSR protocol [11], consists of a planar traversal algorithm, a distributed planarization algorithm, as well as some other protocol optimizations. In GPSR, a planar sub graph of the original graph is computed during a pre processing phase using the RNG planarization technique or the GG planarization technique. Perimeter routing is disabled if a node is encountered that is closer to the destination than the void node. Note that there is no guarantee that perimeter routing will find good-quality paths in the planar sub graph.

Request Routing: Request Route is the void-handling technique used in the BLR protocol [12]. In BLR, a complete planar subgraph is not constructed for the original network graph but a partial planar subgraph is constructed for nodes around a void node on demand (i.e., only when there is data traffic going through the void node). Note that the Request Route technique increases the overall network delay, due to its instant request for the information of neighbouring nodes.

Bypass: Bypass is the void-handling technique employed in the PSGR protocol [13]. Similar to the previous planar graph traversal algorithms, the traversal in bypass employs the well known right hand rule to circumvent a void. Bypass separates the whole plane into two sides, by the line connecting the void node and the destination node. However, the bypass mechanism implies an assumption that the underlying graph formed in a wireless network must be planar to begin with. Otherwise, traversal based on the right handle rule cannot function appropriately. The assumption is often invalid in practice, which makes the use of the bypass void-handling scheme somewhat questionable.

Geometric Void Handling Technique

The main principle behind techniques in this category is to identify holes in a network by making use of the geometric properties of deployed nodes. Depending on application requirements, these paths can be found on demand (i.e., only when a packet gets stuck at a void node), or they can be discovered in a pre-processing phase and stored locally along the boundaries of holes. In order to identify a hole around a void node, a node should first use a rule to detect if it can possibly be a void node. This task is implemented by the TENT rule [14]. In the following, we review some Geometric void handling techniques.

Boundhole: when a packet gets stuck at a void node, it must be at the boundary of at least one of the holes. Note that the idea of holes and hole-surrounding paths in this category is mainly used in the context of wireless sensor networks where routing around voids is only one of the possible applications using holes. When a destination node is outside a bounded hole, BOUNDHOLE [14] guarantees that a stuck packet will always get to the destination. BOUNDHOLE works in a way that it creates a bounded hole around the source node to destination to transmit the data. Note that BOUNDHOLE tends to impose higher load on nodes near the hole boundaries.

Flooding based Void Handling Technique

Void-handling techniques in this category exploit the simplest communications means in a network (i.e., flooding), to get a stuck data packet to get around a void. As we know, original flooding, in which every node in the network is supposed to receive a copy of stuck packets, is a simple and effective technique to handle voids. We call it as original flooding (full flooding). However, full flooding is inefficient in terms of resource utilization and they still cost too much while handling voids, because only the destination node wishes to receive stuck packets from void nodes. Thus, some advanced flooding-based void-handling techniques are desired to efficiently handle voids. The main goal is to make every effort to control the range of flooding as well as the frequency of occurrence of flooding at void nodes to a desired extent, so that the flooding cost is minimized while effectively handling voids. Such a flooding mechanism is called restricted flooding or partial flooding [15]. In the following, we review some Flooding based void handling techniques.

One-Hop Flooding: One-hop flooding [16] is a kind of restricted flooding and it is used at a void node to broadcast the stuck packet only to its one-hop neighbouring nodes instead of flooding to every node in the network as full flooding does. After flooding the packet to all its neighbouring nodes, a void node remembers the stuck packet ID via an entry in its cache corresponding to a specific destination and refuses to accept the same packet from any of its neighbouring nodes. After accepting the stuck packet, every neighbouring node of the void node acts independently and exploits greedy forwarding to forward its own copy of the stuck packet. Note that, the similar idea can be further extended into an n-hop flooding technique where n is larger than or equal to two.

Partial Hop-by-Hop Routing: In Geographic Routing Algorithm [18], a packet will be delivered to a destination node by greedy forwarding if no void is encountered. When a packet gets stuck at a void node for a specific destination, it starts route discovery. The route discovery phase finds a path from the void node to the destination on demand and updates routing tables at all the nodes on the path from the void node toward the destination. After the route discovery is successfully completed, the stuck packet can be routed from the void node to the destination by partial hop-by-hop routing. Note that in [17, 18], another class of route discovery technique other than flooding- based techniques, that is, the depth first-search-based technique, is also proposed for route discovery to find good quality paths in an effective and efficient manner.

Partial Source Routing: PSR [19] is an on-demand and stateless void-handling scheme and it enables a void node to forward any stuck data packet to either a targeted destination node directly or to a node which has a nearer distance to the destination than itself. PSR consists of two phases: partial path discovery and source packet forwarding. In the partial path discovery phase, a void node uses a method similar to expanded ring search to identify a partial path starting from the void node. In the source packet forwarding phase, the void node knows at least a partial path to the destination or to another better-positioned node if a path exists. The void node includes the source path in the data packet's header and forwards the packet to the specified next-hop node. Similar to partial hop-by-hop routing, the cost of discovering a partial path by flooding in PSR can be amortized over the relatively long duration of communications.

Cost based Void Handling Technique

Void-handling techniques in this category exploit a cost based idea to handle voids. In cost-based void handling, a packet flows from a node with a higher cost to a node with a lower cost [20]. The definition of cost varies between different contexts. When designing a cost-based void-handling technique, each node in the network is first assigned a cost, which may be equal to its Euclidean distance to the destination. A packet is still forwarded greedily until it gets stuck at a void node, then cost-based forwarding is enabled. The void node increases its cost to a value larger than its Euclid distance to the destination, so that the packet can finally be directed by the high-cost-to-low-cost rule along efficient paths to get around the void. In the following, we review some Cost based void handling techniques.

Cost based Forwarding: Cost-based forwarding in Partial-partition Avoiding Geographic Routing-MobilePAGER-M [21] is employed to handle voids. It consists of two phases: the shadow-spread phase and the cost-spread phase. The former is used to identify shadow nodes (i.e., void and potential void nodes) and bright nodes (i.e., nonvoid nodes). Such status information, along with the position information, is exchanged among neighbouring nodes by one hop periodic beacons. After this phase, the original network graph is divided into shadow areas with shadow nodes and bright areas with bright nodes Note that cost-based forwarding may not route packets along voids [21]. It tries to route packets originating at other nodes away from void nodes before they get stuck.

Distance Upgrading Algorithm: DUA, the basic cost based idea similar to cost-based forwarding in PAGER-M, is presented more formally in [22], which also investigated two possible problems caused by such cost-based void-handling idea. The first one is that DUA may produce inefficient routing paths. The second problem is that when a void disappears, the routing graph may need to be modified in order to make use of shorter paths. Routing paths processed by distance upgrading and downgrading algorithms beforehand may remain correct but not optimal in terms of shortest paths. Thus, the distance recovery algorithm proposed in [22] is required to dynamically adjust costs at some nodes, in response to network dynamics, to take advantage of optimal paths available in the network.

Heuristic Void Handling

Void-handling techniques in this category exploit some heuristics to handle voids. These techniques are based on some intuitive ideas that are non amenable to a strict theoretical analysis on their effectiveness and efficiency. The basic principle is either to utilize some extra resources or to directly exploit some inherent properties of network topology and some geographic properties of void areas. In the following, we review some Heuristic void handling techniques.

Void Avoidance: Void avoidance [24] actively sends a packet to its upstream node to signal the existence of a void. In this method the void node sends data to intermediate node, if it is not possible to transmit them the intermediate node sends a back pressure to the void node. On receiving it the void node forwards it to the next node. If node A does not exist, further back pressure will occur until a new path is located. It was argued in [24] that it is guaranteed to find a greedy path if one exists, although void avoidance is not guaranteed to find a topologically valid path.

Intermediate node Forwarding: Intermediate node forwarding (INF) [23] is a probabilistic solution for routing around voids via intermediate geographic locations. When a packet is stuck at a void node, the void node discards the packet and sends a notification to the source node of the packet. The source node of the packet then chooses a single intermediate position randomly for a circle around the midpoint of the line between the source node and the destination node. Packets have to traverse that intermediate position. If the packet is discarded again, the radius of the circle is increased and another random position is chosen. This is repeated until the packets are delivered to the destination or until a predefined value has been reached and the source node assumes that the destination is unreachable.

Anchored Geodesic Packet Forwarding: Differently from other void-handling techniques, AGPF in terminode routing [25] is a preventive technique, which tries to prevent a packet from encountering voids before sending the packet, that is, the technique lowers the probability of the occurrence of a void on the path the packet traverses, while other techniques attempt to detect voids and then handle them. In AGPF, a packet at the sender includes a list of positions of anchors in the packet header, which is used as loose source routing information. The packet must pass by the areas of these anchors on its way to its destination. The packet is forwarded greedily between anchors. If the anchors are correctly set, then the packet will reach the destination with a high probability. Note that the sender needs to acquire the position information of anchors and maintain it periodically. AGPF also suggested to use perimeter routing occasionally when there is a void in terminode distribution between two anchors [25].

Hybrid Void Handling

Void-handling techniques in this category combine at least two void-handling techniques together to handle voids more effectively and more efficiently. These techniques may belong to the same category or to different categories. Whether or not a hybrid void-handling technique can guarantee packet delivery depends on specific void-handling techniques combined. There are two possible situations where a hybrid void-handling technique is needed. One is that a single void-handling technique cannot handle voids effectively for all possible network topologies. The other is where one technique, when combined with another technique, can enhance the efficiency of handling voids or reduce the required network resources. In the following, we review some Hybrid void handling techniques.

Partial Source Routing plus Passive Participation: In some resource-constrained wireless networks such as sensor networks, passive participation can be incorporated into Partial Source Routing [19] to handle voids more efficiently. For example, if energy reserve at a void node is lower than a threshold value and the node learns from the past, according to the content of data or high-level description, that its own data is more critical than data from other nodes, the void node can initiate passive participation to discourage itself from forwarding any data traffic destined for the destination which causes the void. This means that the void node will not forward any data packets for other nodes in favour of sending its own packets. This hybrid void-handling technique can improve resource utilization while ensuring that the critical data traffic can be delivered.

Boundhole plus Restricted Flooding: BOUNDHOLE [14] cannot handle a void if the destination is inside the hole, because it is possible that all the nodes in the hole are not closer to the destination than the void node is. In this situation, the stuck packet will have to come back to the void node along the boundary of the hole without being able to locate a node closer to the destination. Restricted flooding, as mentioned above, is initiated to allow each node on the boundary of the hole to broadcast the stuck packet to its entire one-hop neighbouring nodes. BOUNDHOLE itself cannot guarantee the packet delivery. However, using BOUNDHOLE plus restricted flooding, a packet will always reach the destination.

Virtual Destination based Void Handling Technique:

Virtual Destination based Void Handling Technique is a new concept proposed in [26]. In this method it first selects the Trigger node in which it is responsible for transmitting data in Void situations. To handle communication voids, almost all existing Mechanisms try to find a route around. During the void handling process, the advantage of greedy forwarding cannot be achieved as the path that is used to go around the hole is usually not optimal (e.g., with more hops compared to the possible optimal path). More importantly, the robustness of multicast-style routing cannot be exploited. In order to enable opportunistic forwarding in void handling, which means even in dealing with voids, we can still transmit the packet in an opportunistic routing like fashion; virtual destination is introduced, as the temporary target that the packets are forwarded to. Flooding, a packet will always reach the destination. In the following, we review some Virtual Destination based void handling techniques.

Position based Opportunistic Routing: POR [27] is based on geographic routing, the only information exchanged is a node's location obtained via GPS-like equipment. When a source node wants to transmit a packet to the destination, it should get the location (x, y) of the destination through a location service. Here we assume that a location registration and look up service which maps node addresses to locations has already been available just as in. Position-based property makes POR robust and scalable. The location information is actually used to limit the flooding range, other than accurate control message (such as the Reply in AODV) to determine the unique next hop. Moreover, the reduction in control packets and the almost stateless nature of POR underscore its excellent scalability. It only relies on the knowledge of the forwarding node's immediate neighbours and the state required is almost negligible.

Robust Geographic Routing: The design of RGR [28] is based on geographic routing and opportunistic forwarding. The node is assumed to be aware of its own location and the positions of its direct neighbours. Location information can be exchanged using one-hop beacon or piggyback in the data packet's header. We also assume that a location registration and look-up service which maps node addresses to locations is available just as in. When a source node wants to transmit a packet, it gets the location of the destination first and then attaches it to the packet header together with its own location.


Throughout this survey we have explained about the various Void Handling Techniques and it's various features. In this Comparative survey we explained about all the problems faced by these Void Handling techniques to evaluate the best Void Handling Mechanism for Geographic Routing in Mobile adhoc networks.

Planar-graph-based techniques such as perimeter routing make unrealistic assumptions about radio ranges and neighbouring information, the behaviour of these techniques should be investigated if these assumptions are violated, for example, if there are obstructions to radio signals in a network. Some fundamental problems in planar-graph-based techniques include if there exists any better distributed planarization algorithm than those introduced previously, in terms of the quality of paths when compared to the topologically optimal paths in the original graph, and if a void-handling technique is able to find these good quality paths, provided that the paths remain in the planar subgraph. Also, as using planarization may disconnect a connected network with particular patterns of obstacles between nodes, such impact on the performance of geographic routing protocols should be carefully evaluated.

In BOUNDHOLE, holes are discovered in advance for the future use of routing to avoid holes. However, in order to record the discovered path, it requires much greater resources such as memory storage compared to planar graph traversal, especially when holes have a very large boundary. It would be very interesting to know more inherent characteristics of holes under wireless networks of different sizes or node densities, each with an ad hoc deployment of nodes. Such characteristics include distribution of holes in the network, sizes of holes, and so forth. After an in-depth understanding of the characteristics of holes, a more efficient void-handling technique than BOUNDHOLE can be designed by exploiting such knowledge a priori.

A key aspect of a viable flooding-based void-handling technique is to minimize the flooding cost. Thus, more efficient strategies for restricting the flooding range and rate while still being able to circumvent voids are needed. Furthermore, it is possible to develop some efficient methods other than flooding in the route discovery phase of PHR and PSR.

The performance of cost-based void-handling techniques depends on the number of destinations, the number of void nodes, and network dynamics. The currently available cost based void-handling techniques can handle a moderate number of void nodes with a limited number of destination nodes under a relatively static wireless network. Otherwise, network performance will get worse due to too much overhead incurred by cost adjustment and maintenance around void regions. Cost-based void-handling techniques fit into the context of most wireless sensor networks very well, where the number of data sinks is usually limited and routing usually occurs much faster than topology changes. It would be desirable to develop some advanced optimization strategies to reduce the overhead of cost adjustment and maintenance.

Some formal theoretical analyses are required to explain when and where some heuristic techniques are applicable. For instance, although we learn, from simulations, that passive participation does not function well in a relatively low-density wireless network, we do not have a strict analysis to understand the phenomenon as well as the relation between node density and the effectiveness of passive participation. Similar analyses are also desired for active exploration, void avoidance, INF, and AGPF. These results may be derived in the probabilistic sense.

The Virtual Destination based Void Handling scheme serves well at the time of Communication void but in the case of switching back to Normal Greedy Forwarding mode is an issue in RGR but it is handled well in POR by the use of a strategy that analyses the location of the Destination. If the Destination is nearby then it switches back to normal greedy forwarding mode from Void Handling mode. The realistic manner of data transfer at the time of Communication void made Virtual Destination based void handling scheme as one of the efficient techniques.

It is desirable to design more hybrid void-handling techniques if such combinations can enhance the effectiveness of handling voids or can reduce the required resources in void handling. Also, strategies in order to prevent a very long detour of a stuck packet are desired for the existing void-handling techniques to be efficient in practical average-case network topologies. Further, most existing void-handling techniques are designed with some unrealistic assumptions such as equal node transmission ranges, unidirectional links, precise location information, and the like. It would be interesting to see how these techniques perform, either theoretically or by network level simulations, under some more realistic assumptions. Finally, as far as we know, all current techniques have considered voids in a two-dimensional coordinate system. Whether these void-handling techniques are still feasible in a three dimensional coordinate system needs more in-depth research work. Handling three-dimensional communications voids in a realistic environment would be very interesting and challenging.


In this Survey we have examined various Void Handling Techniques for Mobile adhoc Networks. We have discussed about the strategies of these Void handling Techniques along with the Geographic Routing. We have surveyed about all the existing Void Handling Techniques to find an efficient technique that supports efficient data delivery at the time of Communication void. The Comparative study about the Void Handling schemes states that each void handling technique has its own properties and techniques to void handling problem. Comparing all the void handling techniques Virtual Destination based void handling technique proves to be the efficient technique to deliver data at the time of Communication Void, due to its technique which it allows the node to change from void handling mode to normal greedy forwarding mode when the data is near to its destination and provides a reliable data delivery in Mobile adhoc networks.