CaltechAUTHORS
  A Caltech Library Service

Localization and routing in sensor networks by local angle information

Bruck, Jehoshua and Gao, Jie and Jiang, Anxiao (Andrew) (2005) Localization and routing in sensor networks by local angle information. In: MobiHoc '05 Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing. ACM , New York, NY, pp. 181-192. ISBN 1-59593-004-3. https://resolver.caltech.edu/CaltechAUTHORS:20160811-163730860

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160811-163730860

Abstract

Location information is very useful in the design of sensor network infrastructures. In this paper, we study the anchor-free 2D localization problem by using local angle measurements in a sensor network. 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 1 away. Despite the negative results, however, one 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 not only does it give very good local embedding, i.e., neighboring nodes are close and non-neighboring nodes are far away, but it also gives a quite accurate 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. The embedding algorithm can be adapted to other models of wireless sensor networks and is robust to measurement noise.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1062689.1062713DOIPaper
http://dl.acm.org/citation.cfm?doid=1062689.1062713PublisherPaper
http://resolver.caltech.edu/CaltechPARADISE:2005.ETR068Related ItemTechnical Report
ORCID:
AuthorORCID
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2005 ACM. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0209042.
Funders:
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
NSFCCR-TC-0209042
Subject Keywords:Algorithms, Design, Theory, Sensor networks, Wireless networks, Localization, Geographical routing, Embedding, Planar spanner subgraph
Classification Code:E.1 [Data]: Data Structures— graphs and networks; F.2.2 [Theory of Computation]: analysis of algorithms and problem complexity—non-numerical algorithms and problems
DOI:10.1145/1062689.1062713
Record Number:CaltechAUTHORS:20160811-163730860
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160811-163730860
Official Citation:Jehoshua Bruck, Jie Gao, and Anxiao (Andrew) Jiang. 2005. Localization and routing in sensor networks by local angle information. In Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc '05). ACM, New York, NY, USA, 181-192. DOI=http://dx.doi.org/10.1145/1062689.1062713
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69577
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:12 Aug 2016 17:20
Last Modified:11 Nov 2021 04:16

Repository Staff Only: item control page