Localization and Routing in Sensor Networks by Local Angle Information Academic Article uri icon

abstract

  • Location information is useful both for network organization and for sensor data integrity. In this article, we study the anchor-free 2D localization problem by using local angle measurements. We prove that given a unit disk graph and the angles between adjacent edges, it is NP-hard to find a valid embedding in the plane such that neighboring nodes are within distance 1 from each other and non-neighboring nodes are at least distance 2/2 away. Despite the negative results, however, we can find a planar spanner of a unit disk graph by using only local angles. The planar spanner can be used to generate a set of virtual coordinates that enable efficient and local routing schemes such as geographical routing or approximate shortest path routing. We also proposed a practical anchor-free embedding scheme by solving a linear program. We show by simulation that it gives both a good local embedding, with neighboring nodes embedded close and non-neighboring nodes far away, and a satisfactory global view such that geographical routing and approximate shortest path routing on the embedded graph are almost identical to those on the original (true) embedding.

published proceedings

  • ACM TRANSACTIONS ON SENSOR NETWORKS

author list (cited authors)

  • Bruck, J., Gao, J., & Jiang, A. A.

citation count

  • 42

complete list of authors

  • Bruck, Jehoshua||Gao, Jie||Jiang, Anxiao Andrew

publication date

  • January 2009