David K. Goldenberg
ABSTRACT
Determining node positions is essential for many next-generation network functionalities. Previous localization algorithms lack correctness guarantees or require network density higher than required for unique localizability. In this paper, we describe a class of algorithms for fine-grained localization called Sweeps. Sweeps correctly finitely localizes all nodes in bilateration networks. Sweeps also handles angle measurements and noisy measurements. We demonstrate the practicality of our algorithm through extensive simulations on a large number of networks, upon which it consistently localizes one-thousand-node networks of average degree less than five in less than two minutes on a consumer PC.
- J. Albowicz, A. Chen, and L. Zhang. Recursive position estimation in sensor networks. In Proceedings of the 9th International Conference on Network Protocols (ICNP), pages 35--41, Riverside, CA, Nov. 2001. Google Scholar
Digital Library
- B. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A. Morse, W. Whiteley, and Y. R. Yang. Global properties of easily localizable sensor networks. Preprint Australian National University, 2005.Google Scholar
- J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur. A theory of network localization. IEEE Transactions on Mobile Computing, 2006. Google ScholarDigital Library
- J. Aspnes, D. Goldenberg, and Y. R. Yang. On the computational complexity of sensor network localization. In Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, Turku, Finland, July 2004.Google ScholarCross Ref
- P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In Proceedings of IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000.Google ScholarCross Ref
- B. Berger, J. Kleinberg, and T. Leighton. Reconstructing a three-dimensional model with arbitrary errors. Journal of the ACM (JACM), 46(2):212--235, 1999. Google ScholarDigital Library
- P. Biswas, T.-C. Liang, K.-C. Toh, T.-C. Wang, and Y. Ye. Semidefinite programming approaches to sensor network localization with noisy distance measurements. IEEE Transactions on Automation Science and Engineering, 2006.Google ScholarCross Ref
- P. Biswas and Y. Ye. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of the Third International Workshop on Information Processing in Sensor Networks (IPSN'04), Berkeley, CA, Apr. 2004. Google ScholarDigital Library
- N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications Magazine, 7(5):28--34, Oct. 2000.Google ScholarCross Ref
- S. Capkun, M. Hamdi, and J.-P. Hubaux. GPS-free positioning in mobile ad-hoc networks. In Proceedings of HICSS, 2001. Google ScholarDigital Library
- K. Chintalapudi, R. Govindan, G. Sukhatme, and A. Dhariwal. Ad-hoc localization using ranging and sectoring. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.Google ScholarCross Ref
- J. Cortes and F. Bullo. Coordination and geometric optimization via distributed dynamical systems. SIAM Journal on Control and Optimization, 44:1543--1574, 2005. Google ScholarDigital Library
- L. Doherty, K. S. J. Pister, and L. E. Ghaoui. Convex position estimation in wireless sensor networks. In Proceedings of IEEE INFOCOM, Anchorage, AK, Apr. 2001.Google ScholarCross Ref
- T. Eren, D. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson, and P. N. Belhumeur. Rigidity, computation, and randomization in network localization. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.Google ScholarCross Ref
- J. Fang, M. Cao, A. S. Morse, and B. D. O. Anderson. Localization of sensor networks using Sweeps. In Proceedings of the IEEE Conference on Decision and Control, San Diego, CA, Dec. 2006.Google ScholarCross Ref
- J. Fang, M. Cao, A. S. Morse, and B. D. O. Anderson. Sequential localization of networks. In Proceedings of Seventeenth International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, July 2006.Google Scholar
- D. Goldenberg, A. Krishnamurthy, W. Maness, Y. R. Yang, A. Young, A. S. Morse, A. Savvides, and B. D. O. Anderson. Network localization in partially localizable networks. In Proceedings of IEEE INFOCOM, Miami, FL, Apr. 2005.Google ScholarCross Ref
- A. Haeberlen, E. Flannery, A. Ladd, A. Rudys, D. Wallach, and L. Kavraki. Practical robust localization over large-scale 802.11 wireless networks. In Proceedings of the Tenth International Conference on Mobile Computing and Networking (Mobicom), Philadelphia, PA, Sept. 2004. Google ScholarDigital Library
- T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher. Range-free localization schemes in large scale sensor networks. In Proceedings of the Ninth International Conference on Mobile Computing and Networking (Mobicom), pages 81--95, San Diego, CA, Sept. 2003. Google ScholarDigital Library
- L. Hu and D. Evans. Localization for mobile sensor networks. In Proceedings of the Tenth International Conference on Mobile Computing and Networking (Mobicom), Philadelphia, PA, Sept. 2004. Google ScholarDigital Library
- X. Ji and H. Zha. Sensor positioning in wireless ad-hoc sensor networks with multidimensional scaling. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.Google Scholar
- G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331--340, 2002.Google ScholarCross Ref
- K. Langendoen and N. Reijers. Distributed localization in wireless sensor networks: a quantitative comparison. Computer Networks, 43:499--518, 2003. Google ScholarDigital Library
- H. Lim and J. Hou. Localization for anisotropic sensor networks. In Proceedings of IEEE INFOCOM,Miami,FL, Apr. 2005.Google Scholar
- H. Lim, L. Kung, J. Hou, and H. Luo. Zero-configuration, robust indoor localization: theory and experimentation. In Proceedings of IEEE INFOCOM, Barcelona, Spain, Apr. 2006.Google ScholarCross Ref
- J. Lin, A. S. Morse, and B. D. O. Anderson. The multi-agent rendezvous problem - The asynchronous case. In Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, 2004.Google ScholarCross Ref
- J. McLurkin and J. Smith. Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots. In Proceedings of Distributed Autonomous Robotic Systems Conference, 2004.Google Scholar
- D. Moore, J. Leonard, D. Rus, and S. Teller. Robust distributed network localization with noisy range measurements. In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys), Baltimore, MD, Nov. 2004. Google ScholarDigital Library
- D. Niculescu and B. Nath. Ad-hoc positioning system. In Proceedings of IEEE Globecom, San Antonio, TX, Nov. 2001.Google ScholarCross Ref
- D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AOA. In Proceedings of IEEE INFOCOM,San Francisco, CA, Apr. 2003.Google ScholarCross Ref
- D. Niculescu and B. Nath. VOR basestations for indoor 802.11 positioning. In Proceedings of the Tenth International Conference on Mobile Computing and Networking (Mobicom), Philadelphia, PA, Sept. 2004. Google ScholarDigital Library
- N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. In Proceedings of IEEE INFOCOM, Miami, FL, Apr. 2005.Google ScholarCross Ref
- N. B. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket location-support system. In Proceedings of the Sixth International Conference on Mobile Computing and Networking (Mobicom), pages 32--43, Boston, MA, Aug. 2000. Google ScholarDigital Library
- C. Savarese, J. Rabaey, and K. Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In Proceedings of USENIX Technical Annual Conference, Monterey, CA, June 2002. Google ScholarDigital Library
- A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the Seventh International Conference on Mobile Computing and Networking (Mobicom), pages 166--179, Rome, Italy, July 2001. Google ScholarDigital Library
- Y. Shang and W. Ruml. Improved MDS-based localization. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.Google ScholarCross Ref
- Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz. Localization from mere connectivity. In Proceedings of the Fourth ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Annapolis, MD, June 2003. Google ScholarDigital Library
- R. Stoleru, T. He, J. Stankovic, and D. Luebke. High-accuracy, low-cost localization system for wireless sensor network. In Proceedings of the Third ACM Conference on Embedded Networked Sensor Systems (SenSys), Nov. 2005. Google ScholarDigital Library
- C. Wang and L. Xiao. Locating sensors in concave environments. In Proceedings of IEEE INFOCOM, Barcelona, Spain, Apr. 2006.Google Scholar
Index Terms
- Localization in sparse networks using sweeps
Recommendations
Localization Using Anonymous Measurements
DCOSS '15: Proceedings of the 2015 International Conference on Distributed Computing in Sensor SystemsRange-based IEEE 802.15.4 localization systems currently require relatively high anchor density for indoor deployments. It can therefore be beneficial to use external sources of transmission as additional anchors. We present methods for using WiFi ...
Indoor localization using multi-range beaconing: poster
MobiHoc '16: Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and ComputingThe increasing importance of location-aware computing and context-dependent services have led to a growing interest in low-cost indoor positioning with sub-meter accuracy. Bluetooth positioning has received increasing attention from both academia and ...
Practical localization system for consumer devices using zigbee networks
As the era of ubiquitous computing dawns, there is a growing need for a reliable, efficient positioning and tracking system. A localization system involves ongoing tracking of the location of assets and personnel. This paper presents a practical ...
Comments