SeRLoc: Robust localization for wireless sensor networks

ABSTRACT

Many distributed monitoring applications of Wireless Sensor Networks (WSNs) require the location information of a sensor node. In this article, we address the problem of enabling nodes of Wireless Sensor Networks to determine their location in an untrusted environment, known as the secure localization problem. We propose a novel range-independent localization algorithm called SeRLoc that is well suited to a resource constrained environment such as a WSN. SeRLoc is a distributed algorithm based on a two-tier network architecture that allows sensors to passively determine their location without interacting with other sensors. We show that SeRLoc is robust against known attacks on a WSNs such as the wormhole attack, the Sybil attack, and compromise of network entities and analytically compute the probability of success for each attack. We also compare the performance of SeRLoc with state-of-the-art range-independent localization schemes and show that SeRLoc has better performance.

REFERENCES

• 1: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 2: Nirupama Bulusu , Deborah L. Estrin, Self-configuring localization systems, 2002
• 3: Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. IEEE Person. Comm. Mag. 7, 5 (Oct.), 28--34.
• 4: Camp, T., Boleng, J., and Davies, V. 2002. A survey of mobility models for ad hoc network research. Wirel. Comm. Mobile Comput. (WCMC): Special Issue on Mobile Ad Hoc Networking:Research, Trends and Applications, 483--502.
• 5: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 6: Čapkun, S. and Hubaux, J. 2005. Secure positioning of wireless devices with application to sensor networks. To appear in Proceedings of Infocom'05.
• 7: Coppersmith, D. and Jakobsson, M. 2002. Almost optimal hash sequence traversal. In Proceedings of the Financial Cryptography 6th International Conference (FC'02) Lecture Notes in Computer Science. Vol. 2357. 102--119.
• 8: Cressie, N. 1993. Statistics for Spatial Data. John Wiley & Sons, New York, NY.
• 9: Doherty, L., Ghaoui, L., and Pister, K. 2001. Convex position estimation in wireless sensor networks. In Proceedings of the IEEE INFOCOM'01. Vol. 3. 1655--1663.
• 10: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 11: Gruteser, M., Schelle, G., Jain, A., Han, R., and Grunwald, D. 2003. Privacy-aware location sensor networks. In Proceedings of the 9th Workshop on Hot Topics in Operating Systems (HotOS'03).
• 12: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 13: Hofmann-Wellenhof, B., Lichtenegger, H., and Collins, J. 1997. Global Positioning System: Theory and Practice. Springer-Verlag.
• 14: Hu, Y., Perrig, A., and Johnson, D. 2003. Packet leashes: A defense against wormhole attacks in wireless ad hoc networks. In Proceedings of INFOCOM'03. 1976--1986.
• 15: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 16: Karlof, C. and Wagner, D. 2003. Secure routing in wireless sensor networks: Attacks and countermeasures. Ad-Hoc Networks 1, 293--315.
• 17: Kleinrock, L. and Slivester, J. 1978. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of the National Telecom Conference. 4.3.1--4.3.5.
• 18: Leslie Lamport, Password authentication with insecure communication, Communications of the ACM, v.24 n.11, p.770-772, Nov. 1981 [doi>10.1145/358790.358797]
• 19: Lazos, L. and Poovendran, R. 2003. Energy-aware secure multicast communication in ad-hoc networks using geographic location information. In Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP'03). Vol. 6. 201--204.
• 20: Loukas Lazos , Radha Poovendran, SeRLoc: secure range-independent localization for wireless sensor networks, Proceedings of the 2004 ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023646.1023650]
• 21: MICA. Mica wireless measurement system. Available at http://www.xbow.com/Products/Product_pdf_files /Wireless_pdf/MICA.pdf.
• 22: Nagpal, R., Shrobe, H., and Bachrach, J. 2003. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proceedings of Information Processing in Sensor Networks (IPSN'03) Lecture Notes in Computer Science. Vol. 2634. 333--348.
• 23: James Newsome , Elaine Shi , Dawn Song , Adrian Perrig, The sybil attack in sensor networks: analysis & defenses, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984660]
• 24: Niculescu, D. and Nath, B. 2001. Ad-hoc positioning systems (aps). In Proceedings of IEEE GLOBECOM'01. Vol. 5. 2926--2931.
• 25: Niculescu, D. and Nath, B. 2003. Ad hoc positioning system (aps) using aoa. In Proceedings of INFOCOM'03. Vol. 3. 1734--1743.
• 26: Papadimitratos, P. and Haas, Z. J. 2002. Secure routing for mobile ad hoc networks. In Proceedings of the Center for Networking and Distributed Systems (CNDS'02).
• 27: Pickholtz, R., Schilling, D., and Milstein, L. 1982. Theory of spread spectrum communications---A tutorial. IEEE Trans. Comm. 30, 5 (May), 855--884.
• 28: Nissanka B. Priyantha , Hari Balakrishnan , Erik Demaine , Seth Teller, Poster abstract: anchor-free distributed localization in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958550]
• 29: Ram Ramanathan, On the performance of ad hoc networks with beamforming antennas, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501430]
• 30: Rivest, R. 1995. The rc5 encryption algorithm. In Proceedings of the 1st Workshop on Fast Software Encryption. 86--96.
• 31: Naveen Sastry , Umesh Shankar , David Wagner, Secure verification of location claims, Proceedings of the 2003 ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941313]
• 32: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 33: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 34: Douglas Stinson, Cryptography: Theory and Practice,Second Edition, CRC/C&H, 2002
• 35: Wicker, S. and Bartz, M. 1994. Type-ii hybrid-arq protocols using punctured mds codes. IEEE Trans. Comm. 42, 2/3/4, 1431--1440.
• 36: Yazdi, N., Ayazi, F., and Najafi, K. 1998. Micromachined inertial sensors. In Proceedings of the IEEE. Vol. 85, 8 (Aug.), 1640--1659.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Design, Performance, Security

Keywords:
Range-independent, secure localization, sensor networks