Abstract
With the proliferation of location dependent applications in sensor networks, location awareness becomes an essential capability of sensor nodes. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work, via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we provide insight into the impact of localization accuracy on various location dependent applications and suggestions on improving their performance in the presence of such inaccuracy.
- Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the IEEE INFOCOM '00.Google Scholar
- Beutel, J. 1999. Geolocation in a picoRadio environment, M.S. Thesis, ETH Zurich, Electronics Laboratory.Google Scholar
- Blum, B., Nagaraddi, P., Wood, A., Abdelzaher, T. F., Son, S., and Stankovic, J. A. 2003. In Proceedings of Mobisys 2003, San Francisco, CA.Google Scholar
- Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5, 28--34.Google ScholarCross Ref
- Bulusu, N., Heidemann, J., and Estrin, D. 2001. Adaptive beacon placement. In IEEE ICDCS '01, Phoenix, AZ. Google ScholarDigital Library
- Bulusu, N., Heidemann, J., Estrin, D., and Tran, T. 2003. Self-configuring localization systems: Design and experimental evaluation. In TECS Special Issue on Networked Embedded Computing. Google ScholarDigital Library
- Caffery, J. Jr. 2000. A new approach to the geometry of TOA location. In IEEE Vehicular Technology Conference (VTC), Boston, MA.Google ScholarCross Ref
- Capkun, S., Hamdi, M., and Hubaux, J. P. 2001. GPS-free positioning in mobile ad-hoc networks. In Proceedings of HICCSS '01, Maui, Hawaii. Google ScholarDigital Library
- Crossbow. MICA Sensor Board Information, http://www.xbow.comGoogle Scholar
- Doherty, L., Ghaoui, L. E., and Pister, K. S. J. 2001. Convex position estimation in wireless sensor networks. In Proceedings of the IEEE INFOCOM '01, Anchorage, AK.Google Scholar
- Estrin, D., Govindan, R., Heidemann, J., and Kumar, S. 1999. Next century challenges: Scalable coordination in sensor networks. In Proceedings of MobiCom '99, Seattle, Washington. Google ScholarDigital Library
- Ganesan, D., Krishnamachari, B., Woo, A., Culler, D., Estrin, D., and Wicker, S. 2002. Complex behavior at scale: An experimental study of low-power wireless sensor vetworks. Technical Report UCLA/CSD-TR 02-0013.Google Scholar
- Girod, L. and Estrin, D. 2001. Robust range estimation using acoustic and multimodal sensing. In Proceedings of IROS '01, Maui, Hawaii.Google Scholar
- Harter, A., Hopper, A., Steggles, P., Ward, A., and Webster, P. 1999. The anatomy of a context-aware application. In Proceedings of MobiCom '99, Seattle, Washington. Google ScholarDigital Library
- He, T., Huang, C., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. F. 2003a. Range-free localization schemes in large scale sensor networks. In Proceedings of MobiCom 2003. Google ScholarDigital Library
- He, T., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. F. 2003b. A lazy-binding communication protocol for highly dynamic wireless sensor networks. Still in submission.Google Scholar
- Hightower, J. and Boriello, G. 2001. Location systems for ubiquitous computing. IEEE Computer, 34, 8, 57--66. Google ScholarDigital Library
- Hightower, J., Boriello, G., and Want, R. 2000. SpotON: An indoor 3D location sensing technology based on RF signal strength. University of Washington CSE Report #2000-02-02.Google Scholar
- Hong, X., Xu, K., and Gerla, M. 2002. Scalable routing protocols for mobile ad hoc networks. IEEE Network Magazine, 16, 4. Google ScholarDigital Library
- Karp, B. and Kung, H. T. 2000. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of MobiCom '00, New York. Google ScholarDigital Library
- Kleinrock, L. and Silvester, J. 1978. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of National Telecomm Conference, 4.3.1--4.3.5.Google Scholar
- Ko, Y. B. and Vaidya, N. H. 1998. Location-aided routing (LAR) in mobile ad hoc networks. In Proceedings of MobiCom '98, Dallas, TX. Google ScholarDigital Library
- Li, J., Jannotti, J., De Couto, D. S. J., Karger, D., and Morris, R. 2000. A scalable location service for geographic ad-hoc routing. In Proceedings of MobiCom '00, New York. Google ScholarDigital Library
- Nagpal, R. 1999. Organizing a global coordinate system from local information on an amorphous computer. A.I. Memo, MIT A.I. Laboratory.Google Scholar
- Nagpal, R., Shrobe, H., and Bachrach, J. 2003. Organizing a global coordinate system from local information on an ad hoc sensor network. In IPSN '03, Palo Alto. Google ScholarDigital Library
- Navas, J. C. and Imielinski, T. 1997. Geographic addressing and routing. In Proceedings of MobiCom '97, Budapest, Hungary. Google ScholarDigital Library
- Niculescu, D. and Nath. B. 2001. Ad-hoc positioning systems. In Proceedings of IEEE GLOBECOM '01.Google ScholarCross Ref
- Niculescu, D. and Nath, B. 2003a. DV based positioning in ad hoc networks. Journal of Telecommunication Systems 22, 1, 267--280.Google ScholarDigital Library
- Niculescu, D. and Nath, B. 2003b. Ad hoc positioning system (APS) using AoA. In Proceedings of the IEEE INFOCOM '03, San Francisco, CA.Google Scholar
- Priyantha, N. B., Chakraborty, A., and Balakrishnan, H. 2000. The cricket location-support system. In Proceedings of MobiCom '00, New York. Google ScholarDigital Library
- Savarese, C., Rabay, J., and Langendoen, K. 2002. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In USENIX Technical Annual Conference, Monterey, CA. Google ScholarDigital Library
- Savvides, A., Han, C. C., and Srivastava, M. B. 2001. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of MobiCom'01, 2001, Rome, Italy (July). Google ScholarDigital Library
- Savvides, A., Park, H., and Srivastava, M. B. 2002. The bits and flops of the N-hop multilateration primitive for node localization problems. In WSNA'02, Atlanta, GA. Google ScholarDigital Library
- Want, R., Hopper, A., Falcao, V., and Gibbons, J. 1992. The active badge location system. ACM Transactions on Information Systems. Google ScholarDigital Library
- Wellenhoff, B. H., Lichtenegger, H., and Collins, J. 1997. Global Positions System: Theory and Practice, 4th Ed. Springer Verlag, NY.Google Scholar
- Whitehouse, K. and Culler, D. 2002. Calibration as parameter estimation in sensor networks. In First ACM International Workshop on Wireless Sensor Networks and Application, Atlanta GA. Google ScholarDigital Library
- Xu, Y., Heidemann, J., and Estrin, D. 2001. Geography-informed energy conservation for ad hoc routing. In Proceedings of MobiCom '01, Rome, Italy. Google ScholarDigital Library
- Yan, T., He, T., and Stankovic, J. A. 2003. Differentiated surveillance service for sensor networks. In SenSys 2003, Los Angeles, CA. Google ScholarDigital Library
- Zhou, G., He, T., Krishnamurthy, S., and Stankovic, J. A. 2004. Impact of radio irregularity on wireless sensor networks. In Proceedings of MobiSys'04, Boston, MA. Google ScholarDigital Library
Index Terms
- Range-free localization and its impact on large scale sensor networks
Recommendations
Range-free localization schemes for large scale sensor networks
MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networkingWireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-...
Optimality analysis of sensor-target localization geometries
The problem of target localization involves estimating the position of a target from multiple noisy sensor measurements. It is well known that the relative sensor-target geometry can significantly affect the performance of any particular localization ...
Poster abstract: Range-based localization in sensor networks: localizability and accuracy
IPSN '13: Proceedings of the 12th international conference on Information processing in sensor networksLocalizability and accuracy are two fundamental problems in many range-based localization schemes for sensor networks. This poster addresses the two problems theoretically by introducing two new concepts: the effective degree and the lower bound of ...
Comments