Paper Info
Title
The Critical Grid Size and Transmission Radius for Local-Minimum-Free Grid Routing in Wireless Ad Hoc and Sensor Networks
Abstract
In grid routing, the plane is tessellated into equal-sized square cells. Two cells are called neighbor cells if they share a common edge, and two nodes are called routing neighbors if they are in neighbor cells and within each other's transmission range. If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells. As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets. To guarantee deliverability, in this paper, we investigate two vital parameters of grid routing, called the grid size and the transmission radius. Assume that nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r the transmission radius. First, we show that if for some constant β and r = √5l, then β = 1 is the threshold for deliverability. In other words, there almost surely do not exist local minima if β 1 and there almost surely exist local minima if β β 1, we give sufficient and necessary conditions to determine the critical transmission radius (CTR) for deliverability. Then, we show that as β ≅ 1.092, the CTR is the minimum over all β 1. Simulation results are given to validate this theoretical work.
Year
DOI
Venue
2010
10.1093/comjnl/bxq030
Comput. J.
Keywords
Field
DocType
neighbor node,wireless ad hoc,equal-sized square cell,local minimum,transmission range,critical transmission radius,sensor networks,local-minimum-free grid routing,neighbor cell,grid size,unit-area square,critical grid size,transmission radius,grid routing,sensor network,wireless sensor networks,local minima
Link-state routing protocol,Dynamic Source Routing,Computer science,Static routing,Destination-Sequenced Distance Vector routing,Wireless Routing Protocol,Wireless ad hoc network,Geographic routing,Grid,Distributed computing
Journal
Volume
Issue
ISSN
53
10
0010-4620
Citations 
PageRank 
References 
0
0.34
27
Authors
4
Name
Order
Citations
PageRank
Chih-Wei Yi156249.87
Peng-Jun Wan23669247.28
Chao-Min Su3132.60
Chen-Wei Huang41259.03