Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks

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 ; (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 · C_del 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; (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 C_del is the spanning ratio of the Delaunay triangulation, which is at most . And the adjustable parameter α satisfies 0 < α ≤ π/3. Yu Wang is an assistant professor in the Department of Computer Science, University of North Carolina at Charlotte. He received his Ph.D. degree in computer science from Illinois Institute of Technology in 2004, his B.S. degree and M.S. degree in computer science from Tsinghua University, China, in 1998 and 2000. His current research interests include computer networks, wireless networks, mobile computing, algorithm design, and artificial intelligence. His recent work focuses on designing power efficient algorithms for wireless ad hoc networks and sensor networks. He published more than 40 papers in peer-reviewed journals and conferences. He served as program committee member for sevaral conferences (such as IEEE INFOCOM, IEEE MASS, IEEE ICCCN, etc.). He also served as reviewers for a number of international journals and conferences. His paper titled "Sparse Power Efficient Topology for Wireless Networks" won a Best Paper Award from the 35th IEEE Hawaii International Conference on System Sciences in 2002. He is a member of the ACM, IEEE, and IEEE Communication Society. For more information, please see http://www.cs.uncc.edu/~ywang32. Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He received M.S. (2000) and Ph.D. (2001) degree at Department of Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Department of Computer Science and Bachelor degree at Department of Business Management from Tsinghua University, P.R. China in 1995. He is a member of the Chinese national team prepared for the International Mathematics Olympics (IMO) from 1988 to 1990. His research interests span the wireless ad hoc networks, game theory, computational geometry, and cryptography and network security. Recently, he focuses on performing research on the cooperation, energy efficiency, and distributed algorithms for wireless ad hoc and sensor networks. He has published about 60 conference papers in top-quality conferences such as ACM MobiCom, ACM MobiHoc, ACM SODA, ACM STOC, IEEE INFOCOM, etc. He has more than 30 journal papers published or accepted for publish. He is a Member of the ACM, IEEE, and IEEE Communication Society. Xiang Yang Liserved various positions (such as conference chair, local arrangement chair, financial chair, session chair, TPC member) at a number of international conferences such as IEEE INFOCOM, ACM MobiHoc, ACM STOC. Li recently also co-organized a special issue of ACM MONET on non-cooperative computing in wireless networks. For more information, please see http://www.cs.iit.edu/~xli.