Cooperative node localization using nonlinear data projection

ABSTRACT

Cooperative node localization schemes that employ nonlinear data reduction often deliver higher network node position accuracy compared to many other approaches. Other advantages of such algorithms are that they require only a minimum number of anchor nodes (if we require absolute locations) and that they can be applied under both range-based and range-free conditions. This article presents a novel cooperative node localization scheme, applying an efficient neural network nonlinear projection method called Curvilinear Component Analysis (CCA). A thorough comparative performance study of the proposed scheme in different mission-critical operational network scenarios is conducted. Compared with another leading cooperative node localization algorithm, MDS-MAP, which employs Multi-Dimensional Scaling (MDS), the proposed CCA-MAP approach significantly improves position estimate accuracy in many of the scenarios. We also propose a new local edge model for range-free distance matrix approximation that considerably enhances the performance for both MDS-MAP and CCA-MAP in certain irregular network configurations which are very challenging for node positioning.

REFERENCES

• 1: Pratik Biswas , Yinyu Ye, Semidefinite programming for ad hoc wireless sensor network localization, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984630]
• 2: Borg, I. and Groenen, P. 1997. Modern Multidimensional Scaling: Theory and Applications, Springer-Verlag New York, ISBN 0387948457.
• 3: Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004 [doi>10.1145/972627.972630]
• 4: Chintalapudi, K.K., Dhariwal, A., Govindan, R., and Sukhatme, G. 2004. Ad hoc localization using ranging and sectoring. In Proceedings of IEEE INFOCOM.
• 5: Demartines, P. and Herault, J. 1997. Curvilinear component analysis: A self-organizing neural network for nonlinear mapping of data sets. IEEE Trans. Neural Netw. 8, 1.
• 6: Doherty, L., Pister, K., and El Ghaoui, L. 2001. Convex position estimation in wireless sensor networks. In Proceedings of IEEE InfoCom.
• 7: Drineas, P., Javed, A., Magdon-Ismail, M., Pandurangan, G., Virrankoski, R., and Savvides, A. 2006. Distance matrix reconstruction from incomplete distance information for sensor network localization. In Proceedings of the third Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON'06).
• 8: Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Morse, A.S., Anderson, B.D.O., and Belhumeur, P.N. 2004. Rigidity, computation, and randomization in network localization. In Proceedings of IEEE INFOCOM.
• 9: Gezici, S., Tian, Z., Giannakis, G., Kobayashi, H., Molisch, A., Poor, H., and Sahinoglu, Z. 2005. Localization via ultra-wideband radios. IEEE Sig. Process. Mag. 22, 4, 70--84.
• 10: 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]
• 11: Ji, X. and Zha, H. 2004. Sensor positioning in wireless ad hoc sensor networks using multidimensional scaling. In Proceedings of IEEE INFOCOM.
• 12: Kleinrock, L. and Silvester, J. 1978. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of the IEEE National Telecommunications Conference.
• 13: T. Kohonen , M. R. Schroeder , T. S. Huang, Self-Organizing Maps, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 14: 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]
• 15: Juan Liu , Ying Zhang , Feng Zhao, Robust distributed node localization with error management, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132933]
• 16: Niculescu, D. and Nath, B. 2003a. Ad hoc positioning system (APS) using AoA. In Proceedings of INFOCOM.
• 17: Niculescu, D. and Nath, B. 2003b. DV based positioning in ad hoc networks. Kluwer J. Telecomm. Syst. 22, 1-4, 267--280.
• 18: Pubudu N. Pathirana , Nirupama Bulusu , Andrey V. Savkin , Sanjay Jha, Node Localization Using Mobile Robots in Delay-Tolerant Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.285-296, May 2005 [doi>10.1109/TMC.2005.43]
• 19: Patwari, N., Ash, J.N., Kyperountas, S., Herro, A.O., Moses, R.L., and Correal, N.S. 2005. Locating the nodes. IEEE Sig. Process. Mag. 22, 4, 54--69.
• 20: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 21: 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]
• 22: J. W. Sammon, A Nonlinear Mapping for Data Structure Analysis, IEEE Transactions on Computers, v.18 n.5, p.401-409, May 1969 [doi>10.1109/T-C.1969.222678]
• 23: 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]
• 24: 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]
• 25: Shang, Y. and Ruml, W. 2004. Improved MDS based localization. In Proceedings of IEEE INFOCOM.
• 26: Yi Shang , Wheeler Ruml , Ying Zhang , Markus Fromherz, Localization from Connectivity in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.961-974, November 2004 [doi>10.1109/TPDS.2004.67]
• 27: Ssu, K-F., Ou, C-H., and Jiau, H. 2005. Localization with mobile anchor points in wireless sensor networks. IEEE Trans. Vehic. Tech. 54, 3, 1187--1197.
• 28: Vijayanth Vivekanandan , Vincent W. S. Wong, Ordinal MDS-based localisation for wireless sensor networks, International Journal of Sensor Networks, v.1 n.3/4, p.169-178, September 2006 [doi>10.1504/IJSNET.2006.012032]
• 29: Wu, S. and Chow, T.W.S. 2005. PRSOM: A new visualization method by hybridizing multidimensional scaling and self-organizing map. IEEE Trans. Neural Netw. 16, 6, 1362--1380.
• 30: Zhang, Y., Huang, Q., and Liu, J. 2006. Sequential location algorithm for active sensor network deployment. In Proceedings of IEEE International Symposium on Pervasive Computing and Ad Hoc Communications (PCAC'06).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

General Terms:
Algorithms, Design, Performance

Keywords:
Localization, curvilinear component analysis, multi-dimensional scaling, nonlinear mapping, simulations