Robot assisted localization of sensor networks guided by rigidity

ABSTRACT

In this paper, we propose a robot assisted localization guided by rigidity checking. For a network to be localizable, it must be rigid, which means given the existing edge constraints, there is only one location for each node in it. Many networks, however, are not rigid. To localize these nonrigid network, a robot can be used to add additional distance measure between nodes so that the network becomes rigid and localizable. To facilitate the localization and reduce the travel cost of the robot, the rigid subregions of the network are first identified. The identification of rigid subregions provides a guide for the movement of robots. A brief introduction to rigidity theory is presented in this paper. Experiments that evaluate the performance of the proposed approach are presented. The experimental results prove that the proposed approach is sound and gives excellent results compared to previous approaches for localization.

REFERENCES

• 1: I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. IEEE Commun. Mag., 40:102--114, 2002.
• 2: N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low cost outdoor localization for very small devices. Technical Report 00-729, Computer science department, University of Southern California, Los Angles, CA, 2000.
• 3: T. Eren, D. Goldenberg, W. Whitley, Y. Yang, A. Morse, B. Anderson, and P. Belheumer. Rigidity, computation, and randomization of network localization, 2004.
• 4: D. Goldenberg, A. Krishnamurthy, W. Maness, R. Yang, A. Young, and A. Savvides. Network localization in partially localizable networks. In Proceedings of INFOCOM 2005.
• 5: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 6: Donald J. Jacobs , Bruce Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, Journal of Computational Physics, v.137 n.2, p.346-365, Nov. 1, 1997 [doi>10.1006/jcph.1997.5809]
• 7: G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, pages 331--340, 4 1970.
• 8: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 9: Xuanlong Nguyen , Michael I. Jordan , Bruno Sinopoli, A kernel-based learning approach to ad hoc sensor network localization, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.134-152, August 2005 [doi>10.1145/1077391.1077397]
• 10: N. B. Priyantha, H. Balakrishnan, E. D. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. In IEEE Conference on Computer Communications (InfoCom05), 2005.
• 11: C. Savarese, J. Rabaey, and J. Beutel. Locationing in distributed ad hoc wireless sensor networks. In Proc. 2001 Int'l Conf. Acoustics, Speech, and Signal Processing (ICASSP 2001), volume 4, pages 2037--2040, May 2001.
• 12: S. N. Simic and S. Sastry. Distributed environmental monitoring using random sensor networks. In Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks, pages 582--592, 2003.
• 13: C. Wu, W. Sheng, and Y. Zhang. Mobile self-localization using multi-dimensional scaling in robotic sensor networks. The International Journal of Intelligent Control and Systems, 11(3), September 2006.
• 14: Feng Zhao , Leonidas Guibas, Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Commercial robots and applications

General Terms:
Design, Performance

Keywords:
localization, robotics, sensor networks