×

Deterministic secure positioning in wireless sensor networks. (English) Zbl 1221.68043

Summary: The position verification problem is an important building block for a large subset of wireless sensor network (WSN) applications. Indeed, the performance of the WSN degrades significantly when misbehaving nodes report false location information in order to fake their actual position. In this paper we propose the first deterministic distributed protocol for an accurate identification of faking sensors in a WSN. Our scheme does not rely on a subset of trusted nodes that cooperate and are not allowed to misbehave. Thus, any subset of nodes is allowed to try faking its position. As in previous approaches, our protocol is based on distance evaluation techniques developed for WSN.
On the positive side, we show that when the received signal strength (RSS) technique is used, our protocol handles at most \(\lfloor \frac {n}{2} \rfloor-2\) faking sensors. When the time of flight (ToF) technique is used, our protocol manages at most \(\lfloor \frac {n}{2} \rfloor-3\) misbehaving sensors. On the negative side, we prove that no deterministic protocol can identify faking sensors if their number is \(\lceil \frac {n}{2} \rceil-1\). Thus, our scheme is almost optimal with respect to the number of faking sensors.
We discuss application of our technique in the trusted sensor model. More specifically, our results can be used to minimize the number of trusted sensors that are needed to defeat faking ones.

MSC:

68M14 Distributed systems
68M12 Network protocols
68M07 Mathematical problems of computer architecture
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bahl, P.; Padmanabhan, V. N., Radar: an in-building rf-based user location and tracking system, (INFOCOM, vol. 2 (2000), IEEE), 775-784
[2] Brands, S.; Chaum, D., Distance-bounding protocols, (EUROCRYPT’93: Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (1994), Springer-Verlag: Springer-Verlag Secaucus, USA), 344-359 · Zbl 0951.94511
[3] Capkun, S.; Cagalj, M.; Srivastava, M. B., Secure localization with hidden and mobile base stations, (INFOCOM (2006), IEEE)
[4] Capkun, S.; Hubaux, J., Secure positioning in wireless networks, IEEE Journal on Selected Areas in Communications: Special Issue on Security in Wireless Ad Hoc Networks, 24, 2, 221-232 (2006)
[5] Douceur, J. R., The sybil attack, (IPTPS’01: Int. Workshop on Peer-to-Peer Systems. IPTPS’01: Int. Workshop on Peer-to-Peer Systems, LNCS, vol. 2429 (2002), Springer-Verlag: Springer-Verlag London, UK), 251-260 · Zbl 1014.68882
[6] Fette, Bruce, Cognitive Radio Technology (2009), Academic Press
[7] R.J. Fontana, E. Richley, J. Barney, Commercialization of an ultra wideband precision asset location system, in: Ultra Wideband Systems and Technologies, 2003 IEEE Conference on, 2003, pp. 369-373.; R.J. Fontana, E. Richley, J. Barney, Commercialization of an ultra wideband precision asset location system, in: Ultra Wideband Systems and Technologies, 2003 IEEE Conference on, 2003, pp. 369-373.
[8] T. He, S. Krishnamurthy, J.A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, B. Krogh, An energy-efficient surveillance system using wireless sensor networks, in: MobiSys’04: Proc. of the 2nd Int. Conf. on Mobile Systems, Applications, and Services, New York, USA, 2004, pp. 270-283.; T. He, S. Krishnamurthy, J.A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, B. Krogh, An energy-efficient surveillance system using wireless sensor networks, in: MobiSys’04: Proc. of the 2nd Int. Conf. on Mobile Systems, Applications, and Services, New York, USA, 2004, pp. 270-283.
[9] J. Hightower, R. Want, G. Borriello, SpotON: an indoor 3d location sensing technology based on RF signal strength, UW CSE 00-02-02, University of Washington, Department of Computer Science and Engineering, Seattle, WA, February 2000.; J. Hightower, R. Want, G. Borriello, SpotON: an indoor 3d location sensing technology based on RF signal strength, UW CSE 00-02-02, University of Washington, Department of Computer Science and Engineering, Seattle, WA, February 2000.
[10] Hollander, M.; Wolfe, D. A., Nonparametric Statistical Methods (1999), Wiley: Wiley New York · Zbl 0997.62511
[11] Hu, Y.; Perrig, A.; Johnson, D. B., Packet leashes: a defense against wormhole attacks in wireless networks, (INFOCOM (2003), IEEE)
[12] Hwang, J.; He, T.; Kim, Y., Detecting phantom nodes in wireless sensor networks, (INFOCOM (2007), IEEE), 2391-2395
[13] Karp, B.; Kung, H. T., Gpsr: greedy perimeter stateless routing for wireless networks, (MobiCom’00: Proc. of the 6th Annual Int. Conf. on Mobile Computing and Networking (2000), ACM Press: ACM Press New York, USA), 243-254
[14] Lamport, Leslie; Shostak, Robert; Pease, Marshall, The byzantine generals problem, ACM Trans. on Programming Lamguages and Systems, 4, 3, 382-401 (1982) · Zbl 0483.68021
[15] Lazos, L.; Poovendran, R., Serloc: Robust localization for wireless sensor networks, ACM Trans. Sen. Netw., 1, 1, 73-100 (2005)
[16] Lazos, L.; Poovendran, R.; Capkun, S., Rope: robust position estimation in wireless sensor networks, (IPSN (2005), IEEE), 324-331
[17] C.H. Liu, D.J. Fang, Propagation. in antenna handbook: Theory, applications, and design, Van Nostrand Reinhold, 1988, pp. 1-56 (Chapter 29).; C.H. Liu, D.J. Fang, Propagation. in antenna handbook: Theory, applications, and design, Van Nostrand Reinhold, 1988, pp. 1-56 (Chapter 29).
[18] Nesterenko, Mikhail; Tixeuil, Sébastien, Discovering network topology in the presence of byzantine faults, IEEE Trans. Parallel Distrib. Syst., 20, 12, 1777-1789 (2009) · Zbl 1222.68047
[19] Priyantha, N. B.; Chakraborty, A.; Balakrishnan, H., The cricket location-support system, (6th ACM MOBICOM (2000), ACM: ACM Boston, MA)
[20] Shapiro, S. S.; Wilks, M. B., An analysis of variance test for normality (complete samples), Bometrika, 52, 3-4, 591-611 (1965) · Zbl 0134.36501
[21] Szewczyk, R.; Mainwaring, A.; Polastre, J.; Anderson, J.; Culler, D., An analysis of a large scale habitat monitoring application, (SenSys’04: Proc. Int. Conf. Embedded Networked Sensor Systems (2004), ACM Press: ACM Press NY, USA), 214-226
[22] Vora, Adnam; Nesterenko, Mikhail; Tixeuil, Sébastien; Delaët, Sylvie, Universe detectors for sybil defense in ad hoc wireles networks, (International Conference on Stabilization, Safety, and Security. International Conference on Stabilization, Safety, and Security, SSS 2008. International Conference on Stabilization, Safety, and Security. International Conference on Stabilization, Safety, and Security, SSS 2008, Lecture Notes in Computer Science (2008), Springer-Verlag)
[23] Want, R.; Hopper, A.; Falc, ao V.; Gibbons, J., The active badge location system, ACM Trans. Inf. Syst., 10, 1, 91-102 (1992)
[24] A. Ward, A. Jones, A. Hopper, A new location technique for the active office, Personal Communications, IEEE [see also IEEE Wireless Communications], 4(5) (1997) 42-47.; A. Ward, A. Jones, A. Hopper, A new location technique for the active office, Personal Communications, IEEE [see also IEEE Wireless Communications], 4(5) (1997) 42-47.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.