Separability and Topology Control of Quasi Unit Disk Graphs Conference Paper uri icon


  • A deep understanding of the structural properties of wireless networks is critical for evaluating the performance of network protocols and improving their designs. Many protocols for wireless networks -routing, topology control, information storage/retrieval and numerous other applications -have been based on the idealized unit-disk graph (UDG) network model. The significant deviation of the UDG model from many real wireless networks is substantially limiting the applicability of such protocols. A more general network model, the quasi unitdisk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the designs of key network protocols and algorithms. In this paper, we present results on two important properties of quasi-UDGs: separability and the existence of power efficient spanners. Network separability is a fundamental property leading to efficient network algorithms and fast parallel computation. We prove that every quasi-UDG has a corresponding grid graph with small balanced separators that captures its connectivity properties. We also study the problem of constructing an energy-efficient backbone for a quasi-UDG. We present a distributed localized algorithm that, given a quasi-UDG, constructs a nearly planar backbone with a constant stretch factor and a bounded degree. We demonstrate the excellent performance of these auxiliary graphs through simulations and show their applications in efficient routing. 2007 IEEE.

name of conference

  • IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications

published proceedings

  • INFOCOM 2007, VOLS 1-5

author list (cited authors)

  • Chen, J., Jiang, A. A., Kanj, I. A., Xia, G. e., & Zhang, F.

citation count

  • 21

complete list of authors

  • Chen, Jianer||Jiang, Anxiao Andrew||Kanj, Iyad A||Xia, Ge||Zhang, Fenghui

publication date

  • May 2007