Distributed localization for anisotropic sensor networks

ABSTRACT

In this article, we address the issue of localization in anisotropic sensor networks. Anisotropic networks differ from isotropic networks in that they possess properties that vary according to the direction of measurement. Anisotropic characteristics result from various factors such as the geographic shape of the region (nonconvex region), different node densities, irregular radio patterns, and anisotropic terrain conditions. In order to characterize anisotropic features, we devise a linear mapping method that projects one embedding space built upon proximity measures into geographic distance space by using the truncated singular value decomposition (SVD) pseudo-inverse technique. This transformation retains as much topological information as possible and reduces the effect of measurement noise on the estimates of geographic distances. We show via simulation that the proposed localization method outperforms DV-hop, DV-distance, and MDS-MAP, and makes robust and accurate estimates of sensor locations in both isotropic and anisotropic sensor networks.

REFERENCES

• 1: Pratik Biswas , Tzu-Chen Lian , Ta-Chung Wang , Yinyu Ye, Semidefinite programming based algorithms for sensor network localization, ACM Transactions on Sensor Networks (TOSN), v.2 n.2, p.188-220, May 2006 [doi>10.1145/1149283.1149286]
• 2: Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low-cost outdoor localization for very small devices. IEEE Pers. Commun. 7, 5 (Oct.), 28--34.
• 3: Doherty, L., Pister, K., and Ghaoui, L. 2001. Convex position estimation in wireless sensor networks. In Proceedings of IEEE Conference on Computer Communications (Infocom).
• 4: Gencer, N. G. and Williamson, S. J. 1998. Differential characterization of neural sources with the bimodal truncated SVD pseudo-inverse for EEG and MEG measurements. IEEE Trans. Biomed. Eng. 45, 7.
• 5: Simon Haykin, Adaptive filter theory (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 6: 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]
• 7: Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003 [doi>10.1109/TPAMI.2003.1195989]
• 8: Ji, X. and Zha, H. 2004. Sensor positioning in wireless ad hoc sensor networks using multidimensional scaling. In Proceedings of IEEE Conference on Computer Communications (INFOCOM).
• 9: Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
• 10: Ning Li , Jennifer C. Hou, FLSS: a fault-tolerant topology control algorithm for wireless 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.1023747]
• 11: Li, N. and Hou, J. C. 2004b. Topology control in heterogeneous wireless networks: problems and solutions. In Proceedings of IEEE Conference on Computer Communications (INFOCOM).
• 12: Li, N., Hou, J. C., and Sha, L. 2003. Design and analysis of a MST-based distributed topology control algorithm for wireless ad hoc networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM).
• 13: Hyuk Lim , Jennifer C. Hou , Chong-Ho Choi, Constructing internet coordinate system based on delay measurement, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948222]
• 14: 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).
• 15: Niculescu, D. and Nath, B. 2001. Ad hoc positioning system (APS). In Proceedings of IEEE Global Communications Conference (GLOBECOM).
• 16: Vikas C. Raykar , Igor Kozintsev , Rainer Lienhart, Position calibration of audio sensors and actuators in a distributed computing platform, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957133]
• 17: Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. 2002. Incremental SVD-based algorithms for highly scalable recommender systems. In Proceedings of International Conference on Computer and Information Technology.
• 18: Chris Savarese , Jan M. Rabaey , Koen Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.317-327, June 10-15, 2002
• 19: 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]
• 20: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 21: Shang, Y. and Ruml, W. 2004. Improved MDS-based localization. In Proceedings of IEEE Conference on Computer Communications (INFOCOM).
• 22: 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]
• 23: Shim, Y. S. and Cho, Z. H. 1981. SVD pseudo-inversion image reconstruction. IEEE Trans. Acoust. Speech. Sign. Proc. ASSP-29.
• 24: Liying Tang , Mark Crovella, Virtual landmarks for the internet, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948223]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance

Keywords:
Localization, sensor networks, singular value decomposition