Loading...
Please wait, while we are loading the content...
Similar Documents
Distributed localization using noisy distance and angle information (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Basu, Amitabh Gao, Jie Mitchell, Joseph S. B. Sabhnani, Girishkumar |
| Description | Localization is an important and extensively studied problem in ad-hoc wireless sensor networks. Given the connectivity graph of the sensor nodes, along with additional local information (e.g. distances, angles, orientations etc.), the goal is to reconstruct the global geometry of the network. In this paper, we study the problem of localization with noisy distance and angle information. With no noise at all, the localization problem with both angle (with orientation) and distance information is trivial. However, in the presence of even a small amount of noise, we prove that the localization problem is NP-hard. Localization with accurate distance information and relative angle information is also hard. These hardness results motivate our study of approximation schemes. We relax the non-convex constraints to approximating convex constraints and propose linear programs (LP) for two formulations of the resulting localization problem, which we call the weak deployment and strong deployment problems. These two formulations give upper and lower bounds on the location uncertainty respectively: No sensor is located outside its weak deployment region, and each sensor can be anywhere in its strong deployment region without violating the approximate distance and an-gle constraints. Though LP-based algorithms are usually solved by centralized methods, we propose distributed, iterative methods, which are provably convergent to the centralized algorithm solutions. We give simulation results for the distributed algorithms, evaluating the convergence rate, dependence on measurement noises, and robustness to link dynamics. |
| File Format | |
| Language | English |
| Publisher | ACM Press |
| Publisher Date | 2006-01-01 |
| Publisher Institution | PROCEEDINGS OF THE SEVENTH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING |
| Access Restriction | Open |
| Subject Keyword | Location Uncertainty Small Amount Centralized Method Convex Constraint Angle Information Localization Problem Connec-tivity Graph Ad-hoc Wireless Sensor Network Weak Deployment Distance Information Sensor Node Lp-based Algorithm Global Geometry Hardness Result Cen-tralized Algorithm Solution Measurement Noise Propose Linear Pro-grams Relative Angle Information Distributed Algorithm Convergence Rate Strong Deployment Problem Strong Deployment Region Ap-proximation Scheme Noisy Distance Non-convex Constraint Additional Local Information It-erative Method An-gle Constraint Accu-rate Distance Information Weak Deployment Region Simulation Result Approximate Distance |
| Content Type | Text |
| Resource Type | Article |
