A survey of void handling techniques for geographic routing in wireless networks
IEEE Communications Surveys & TutorialsPublished 1 January 2007
Dazhi Chen, Pramod K. Varshney
Citations223
SJR quartileQ1
SJR score14.18
SNIP13.92
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An overview of the void problem is presented and the currently available void-handling techniques (as of July 2006) for geographic routing are surveyed, each designed with a different approach.
Abstract
Communications voids, where geographic greedy forwarding fails to move a packet further towards its destination, are an important issue for geographic routing in wireless networks. This article presents an overview of the void problem and surveys the currently available void-handling techniques (as of July 2006) for geographic routing. In the survey, we classify these void-handling techniques into six categories, each designed with a different approach, that is, planar-graph-based, geometric, flooding-based, costbased, heuristic, and hybrid. For each category, we present its basic principle and illustrate some classic techniques as well as the latest advances. We also provide a qualitative comparison of these techniques and discuss some possible directions of future research.
Keywords
Computer Science
IEEE Transactions on Information TheoryThe capacity of wireless networks
8,315 Citations2000Piyush Gupta, P. R. Kumar
GPSR
7,032 Citations2000Brad Karp, H. T. Kung
Greedy Perimeter Stateless Routing is presented, a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions and its scalability on densely deployed wireless networks is demonstrated.
IEEE Personal CommunicationsGPS-less low-cost outdoor localization for very small devices
3,572 Citations2000Nirupama Bulusu, John Heidemann +1 more
This work reviews localization techniques and evaluates the effectiveness of a very simple connectivity metric method for localization in outdoor environments that makes use of the inherent RF communications capabilities of these devices.
The broadcast storm problem in a mobile ad hoc network
3,146 Citations1999Sze-Yao Ni, Yu‐Chee Tseng +2 more
This paper proposes several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcast to alleviate the broadcast storm problem, which is identified by showing how serious it is through analyses and simulations.
Dynamic fine-grained localization in Ad-Hoc networks of sensors
2,692 Citations2001Andreas Savvides, Chih‐Chieh Han +1 more
A novel approach to the localization of sensors in an ad-hoc network that enables sensor nodes to discover their locations using a set distributed iterative algorithms is described.
International Journal of Wireless Information NetworksThe Global Positioning System: Signals, measurements, and performance
2,621 Citations1994Per Enge
This advanced tutorial will describe the GPS signals, the various measurements made by the GPS receivers, and estimate the achievable accuracies, and focus on topics which are more unique to radio navigation or GPS.
IEEE NetworkA survey on position-based routing in mobile ad hoc networks
1,558 Citations2001Martin Mauve, Joerg Widmer +1 more
An overview of ad hoc routing protocols that make forwarding decisions based on the geographical position of a packet's destination and previously proposed location services are discussed in addition to position-based packet forwarding strategies.
IRE Transactions on Communications SystemsOptimal Transmission Ranges for Randomly Distributed Packet Radio Terminals
1,255 Citations1984Hideaki Takagi, Leonard Kleinrock
It is shown that the FM capture phenomenon with slotted ALOHA greatly improves the expected progress over the system without capture due to the more limited area of possibly interfering terminals around the receiver.
Wireless NetworksRouting with Guaranteed Delivery in Ad Hoc Wireless Networks
1,203 Citations2001Prosenjit Bose, Pat Morin +2 more
SPEED: a stateless protocol for real-time communication in sensor networks
1,181 Citations2004Tian He, John A. Stankovic +2 more
SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce, and specifically tailored to be a stateless, localized algorithm with minimal control overhead.
Wireless Sensor Networks: An Information Processing Approach
970 Citations2004Feng Zhao, Leonidas Guibas
This paper presents a meta-modelling framework that automates and automates the very labor-intensive and therefore time-heavy and expensive process of manually cataloging and cataloging sensor networks.
IEEE Transactions on Mobile ComputingGeographic random forwarding (geraf) for ad hoc and sensor networks: multihop performance
875 Citations2003Michele Zorzi, Ramesh R. Rao
This paper focuses on the multihop performance of a novel forwarding technique based on geographical location of the nodes involved and random selection of the relaying node via contention among receivers, and an idealized scheme (in which the best relay node is always chosen) is discussed.
Compass routing on geometric networks.
848 Citations1999Evangelos Kranakis, Harvinder Singh +1 more
A close look at maps of numerous cities around the world, show that the previous way to explore a new, and unknown city will in general yield walks that will be close to the optimal ones to travel from one location to another.
Geographic routing without location information
758 Citations2003Ananth Rao, Sylvia Ratnasamy +3 more
This paper defines a scalable coordinate-based routing algorithm that does not rely on location information, and thus can be used in a wide variety of ad hoc and sensornet environments.
IEEE Transactions on CommunicationsTransmission Range Control in Multihop Packet Radio Networks
673 Citations1986Ting‐Chao Hou, Victor O. K. Li
This paper presents a model for analyzing the performance of transmission strategies in a multihop packet radio network where each station has adjustable transmission radius and shows that the network can achieve better performance by suitably controlling the transmission range.
Geometric ad-hoc routing
662 Citations2003Fabian Kühn, Rogert Wattenhofer +2 more
A new geometric routing algorithm is proposed which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal and the formerly necessary assumption that the distance between network nodes may not fall below a constant value is dropped.
Worst-Case optimal and average-case efficient geometric ad-hoc routing
543 Citations2003Fabian Kühn, Rogert Wattenhofer +1 more
GOAFR is the first ad-hoc algorithm to be both asymptotically optimal and average-case efficient and study a dozen of routing algorithms and shows that GOAFR outperforms other prominent algorithms, such as GPSR or AFR.
Locating and bypassing routing holes in sensor networks
469 Citations2005Qing Fang, Jie Gao +1 more
A distributed algorithm is described, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes, and it is shown that these hole-surrounding routes can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.
A scalable solution to minimum cost forwarding in large sensor networks
413 Citations2002Fan Ye, Andre Chen +2 more
This work presents a novel backoff-based cost field setup algorithm that finds the optimal costs of all nodes to the sink with one single message overhead at each node in a large sensor network.
IEEE Transactions on Parallel and Distributed SystemsLoop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks
401 Citations2001Ivan Stojmenović, Lin Xu
2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best1-hop neighbor among joint neighbors of A and C are proposed.
Boundary recognition in sensor networks by topological methods
375 Citations2006Yue Wang, Jie Gao +1 more
This paper proposes a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles, and obtains as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing.
Computer CommunicationsBLR: beacon-less routing algorithm for mobile ad hoc networks
321 Citations2004Marc Heissenbüttel, Torsten Braun +2 more
Analytical results and simulation experiments indicate that BLR provides efficient and robust routing in highly dynamic mobile ad hoc networks.
Geographic routing without location information
289 Citations2003Ananth Rao, Christos H. Papadimitriou +2 more
Distributed construction of a planar spanner and routing for ad hoc wireless networks
274 Citations2003Xiangyang Li, Gruiă Cälinescu +1 more
This work presents a novel localized networking protocol that constructs a planar 2.5-spanner of UDG, called the localized Delaunay triangulation, as network topology, and shows that the delivery rates of existing localized routing protocols are increased when localizedDelaunay Triangulation is used instead of several previously proposed topologies.
Geometric spanner for routing in mobile networks
261 Citations2001Jie Gao, Leonidas Guibas +3 more
It is shown by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol, and theoretical bounds on the quality of paths discovered using GPSR are investigated.
Lecture notes in computer scienceNeighborhood-Based Topology Recognition in Sensor Networks
188 Citations2004Sándor P. Fekete, Alexander Kröller +3 more
This work considers a crucial aspect of self-organization of a sensor network consisting of a large set of simple sensor nodes with no location hardware and only very limited communication range, and describes algorithmic approaches for determining the structure of boundary nodes of the region, and the topology of the Region.
Symposium on Discrete AlgorithmsDeterministic boundary recognition and topology extraction for large sensor networks
165 Citations2006Alexander Kröller, Sándor P. Fekete +2 more
Geometric spanner for routing in mobile networks
159 Citations2001Jie Gao, Leonidas Guibas +3 more
Cluster ComputingSelf Organized Terminode Routing
144 Citations2002Ljubica Blažević, Silvia Giordano +1 more
The simulation results for a large, highly mobile ad hoc environment demonstrate benefits of the combination of TLR and TRR over an existing protocol that uses geographical information for packet forwarding.
Information assurance in sensor networks
110 Citations2003Budhaditya Deb, Sudeept Bhatnagar +1 more
This paper proposes a new scheme for information delivery at a desired reliability using hop-by-hop broadcast, and shows how the wireless broadcast can be utilized to increase the packet delivery rate at each hop and attain a wanted reliability at minimal cost.
IEEE NetworkScalable geographic routing algorithms for wireless ad hoc networks
96 Citations2004Hannes Frey
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.
MACRO: an integrated MAC/routing protocol for geographic forwarding in wireless sensor networks
76 Citations2005D. Ferrara, Laura Galluccio +3 more
An integrated MAC/routing protocol, called MACRO, which exploits the capability of sensor devices to tune their transmission power is introduced and performance results show that the proposed protocol outperforms other solutions in terms of energy efficiency and boosts data aggregation.
International Journal of Ad Hoc and Ubiquitous ComputingAvoid 'void' in geographic routing for data aggregation in sensor networks
62 Citations2006Shigang Chen, Guangbin Fan +1 more
A new geographic routing algorithm that forwards packets from sensors to base stations along efficient routes and replaces the right-hand rule by distance upgrading is proposed, which is fully distributed and responds to topology changes instantly with localised operations.
Computer CommunicationsOn-demand Geographic Forwarding for data delivery in wireless sensor networks
59 Citations2007Dazhi Chen, Pramod K. Varshney
This study demonstrates that OGF is viable for efficient data delivery in the targeted sensor networks and exhibits a superior performance in terms of energy consumption, scalability, and void handling.
PSGR: priority-based stateless geo-routing in wireless sensor networks
54 Citations2005Yingqi Xu, Wang-Chien Lee +2 more
Simulation results show that PSGR exhibits superior performance in terms of energy consumption, routing latency and delivery rate, and soundly outperforms all of the compared protocols.
A state-free data delivery protocol for multihop wireless sensor networks
51 Citations2005Dazhi Chen, Jing Deng +1 more
Simulation results are presented to show that SIF performs better than some previously proposed protocols for data delivery in terms of communication overhead, packet delivery ratio, and average packet delay.
Self organized terminode routing simulation
49 Citations2001Ljubica Blažević, Silvia Giordano +1 more
The simulation results for a large, highly mobile ad-hoc environment demonstrate benefits of the combination of TLR and TRR over an existing protocol that uses geographical information for packet forwarding.
Topology Control in Wireless AD HOC Networks
42 Citations2004Xiang‐Yang Li
This chapter reviews in detail the geometry structures that are suitable for topology control in wireless ad hoc networks, especially the structures with bounded stretch factors, bounded node degree, or planar structures.
On the forwarding area of contention-based geographic forwarding for ad hoc and sensor networks
27 Citations2005Dazhi Chen, Jing Deng +1 more
This work model CGF without void (i.e., absence of a next-hop node in the forwarding area) handling as a 3-step forwarding strategy and introduces two state-free void handling schemes for CGF and study their performance in depth.
Depth first search and location based localized routing and QoS routing in wireless networks
26 Citations2002Ivan Stojmenović, Mark Russell +1 more
This is the first localized algorithm that guarantees delivery for (connected) wireless networks modeled by arbitrary graphs, including inaccurate location information, and is also the first paper to apply GPS in QoS routing decisions, and to consider the connection time as a QoS criterion.
Characterizing the Impact of Routing Holes on Geographic Routing
18 Citations2005Marwan Fayed, Hussein T. Mouftah
The distribution of hops required to map a hole is skewed toward smaller values (/spl les/ 10 hops), and the likelihood of encountering a routing hole as a function of distance is found to be greatly affected by the distance in all but uniformly generated networks.
Information Assurance in Sensor Networks
1 Citations2009Hong Man, Yafeng Yin
The Particle Filter Gaussian Process Dynamical Model is extended to track multiple targets in complex visual environment and a high-dimensional training target trajectory data set of the observation space is projected to a low-dimensional latent space through Probabilistic Principal Component Analysis.