March 20, 2007
Geographic routing is becoming the protocol of choice for many sensor network applications. The current state of the art is unsatisfactory: some algorithms are very efficient, however they require a preliminary planarization of the communication graph. Planarization induces overhead and is not realistic in many scenarios. On the otherhand, georouting algorithms which do not rely on planarization have fairly low success rates and either fail to route messages around all but the simplest obstacles or have a high topology control overhead (e.g. contour detection algorithms). To overcome these limitations, we propose GRIC, the first lightweight and efficient on demand (i.e. all-to-all) geographic routing algorithm which does not require planarization and has almost 100% delivery rates (when no obstacles are added). Furthermore, the excellent behavior of our algorithm is maintained even in the presence of large convex obstacles. The case of hard concave obstacles is also studied; such obstacles are hard instances for which performance diminishes.
Similar papers 1
July 8, 2013
We introduce and evaluate a very simple landmark-based network partition technique called Hierarchical Bipartition Routing (HBR) to support routing with delivery guarantee in wireless ad hoc sensor networks. It is a simple routing protocol that can easily be combined with any other greedy routing algorithm to obtain delivery guarantee. The efficiency of HBR increases if the network is sparse and contains obstacles. The space necessary to store the additional routing informati...
March 12, 2014
Geographic routing consists in using the position information of nodes to assist in the routing process, and has been a widely studied subject in sensor networks. One of the outstanding challenges facing geographic routing has been its applicability. Authors either make some broad assumptions on an idealized version of wireless networks which are often unverifiable, or they use costly methods to planarize the communication graph. The overarching questions that drive us are ...
April 29, 2005
Geocasting is the delivery of packets to nodes within a certain geographic area. For many applications in wireless ad hoc and sensor networks, geocasting is an important and frequent communication service. The challenging problem in geocasting is distributing the packets to all the nodes within the geocast region with high probability but with low overhead. According to our study we notice a clear tradeoff between the proportion of nodes in the geocast region that receive the...
March 25, 2008
Geometric routing algorithms like GFG (GPSR) are lightweight, scalable algorithms that can be used to route in resource-constrained ad hoc wireless networks. However, such algorithms run on planar graphs only. To efficiently construct a planar graph, they require a unit-disk graph. To make the topology unit-disk, the maximum link length in the network has to be selected conservatively. In practical setting this leads to the designs where the node density is rather high. Moreo...
November 20, 2004
Geographic routing with greedy relaying strategies have been widely studied as a routing scheme in sensor networks. These schemes assume that the nodes have perfect information about the location of the destination. When the distance between the source and destination is normalized to unity, the asymptotic routing delays in these schemes are $\Theta(\frac{1}{M(n)}),$ where M(n) is the maximum distance traveled in a single hop (transmission range of a radio). In this paper, we...
December 8, 2014
Geographic routing protocols greatly reduce the requirements of topology storage and provide flexibility in the accommodation of the dynamic behavior of ad hoc networks. This paper presents performance evaluations and comparisons of two geographic routing protocols and the popular AODV protocol. The trade-offs among the average path reliabilities, average conditional delays, average conditional number of hops, and area spectral efficiencies and the effects of various paramete...
September 3, 2015
Geographic routing protocols greatly reduce the requirements of topology storage and provide flexibility in the accommodation of the dynamic behavior of mobile ad hoc networks. This paper presents performance evaluations and comparisons of two geographic routing protocols and the popular AODV protocol. The tradeoffs among the average path reliabilities, average conditional delays, average conditional numbers of hops, and area spectral efficiencies and the effects of various p...
February 24, 2009
We present a novel geographical routing scheme for spontaneous wireless mesh networks. Greedy geographical routing has many advantages, but suffers from packet losses occurring at the border of voids. In this paper, we propose a flexible greedy routing scheme that can be adapted to any variant of geographical routing and works for any connectivity graph, not necessarily Unit Disk Graphs. The idea is to reactively detect voids, backtrack packets, and propagate information on b...
November 28, 2011
In the years, routing protocols in wireless sensor networks (WSN) have been substantially investigated by researches. Most state-of-the-art surveys have focused on reviewing of wireless sensor network .In this paper we review the existing secure geographic routing protocols for wireless sensor network (WSN) and also provide a qualitative comparison of them.
January 19, 2012
Thanks to the potential they hold and the variety of their application domains, Multimedia Wireless Sensor Networks (MWSN) are forecast to become highly integrated into our daily activities. Due to the carried content nature, mainly composed of images and/or video streams with high throughput and delay constraints, Quality of Service in the context of MWSN is a crucial issue. In this paper, we propose a QoS and energy aware geographic routing protocol for MWSN: QGRP. The prop...