TY - JOUR

T1 - The critical grid size and transmission radius for local-minimum-free grid routing in wireless ad hoc and sensor networks

AU - Ik, Tsi-Ui

AU - Wan, Peng Jun

AU - Su, Chao Min

AU - Huang, Chen Wei

PY - 2010/12/1

Y1 - 2010/12/1

N2 - 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. Next, for any given > 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.

AB - 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. Next, for any given > 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.

KW - disk graphs

KW - geographic greedy routing

KW - grid routing

KW - local minima

KW - random deployment

KW - wireless ad hoc networks

KW - wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=78649888530&partnerID=8YFLogxK

U2 - 10.1093/comjnl/bxq030

DO - 10.1093/comjnl/bxq030

M3 - Article

AN - SCOPUS:78649888530

VL - 53

SP - 1621

EP - 1631

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 10

ER -