Content area
Full Text
Mobile Networks and Applications 11, 161175, 2006C 2006 Springer Science + Business Media, LLC. Manufactured in The Netherlands.DOI: 10.1007/s11036-006-4469-5Localized Construction of Bounded Degree and Planar Spanner for
Wireless Ad Hoc NetworksYU WANGDepartment of Computer Science, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USAXIANG-YANG LIDepartment of Computer Science, Illinois Institute of Technology, 10 West 31st Street, Chicago, IL 60616, USAPublished online: 31 March 2006Abstract. We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks
modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method
applies the Yao structure on the local Delaunay graph [1] in an ordering that are computed locally. This new structure has the following
attractive properties: (1) it is a planar graph; (2) its node degree is bounded from above by a positive constant 19 +2; (3) it is a t-spanner
(given any two nodes u and v, there is a path connecting them in the structure such that its length is no more than t max{1}Cdel times of the shortest path in the unit disk graph); (4) it can be constructed locally and is easy to maintain when the nodes move around;2 , sin2+(5) moreover, we show that the total communication cost is O(n log n) bits, where n is the number of wireless nodes, and the computation
cost of each node is at most O(d log d), where d is its 2-hop neighbors in the original unit disk graph. Here Cdel is the spanning ratio of the
Delaunay triangulation, which is at most 439 . And the adjustable parameter satisfies 0 < /3.Keywords: Wireless ad hoc networks, topology control, bounded degree, planar, spanner, localized algorithm1. IntroductionWe consider a wireless ad hoc network (or sensor network)
consisting of a set V of n wireless nodes distributed in a
two-dimensional plane. Each node has some computation
power and an omni-directional antenna. This is attractive
because a single transmission of a node can be received by
all nodes within its vicinity. By a proper scaling, we assume
that all nodes have the maximum transmission range equal
to one unit. These wireless nodes define a...