| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Localization from Connectivity in Sensor Networks
November 2004 (vol. 15 no. 11)
pp. 961-974
Abstract—We propose an approach that uses connectivity information—who is within communications range of whom—to derive the locations of nodes in a network. The approach can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. It is based on multidimensional scaling (MDS), an efficient data analysis technique that takes O(n^3) time for a network of n nodes. Unlike previous approaches, MDS takes full advantage of connectivity or distance information between nodes that have yet to be localized. Two methods are presented: a simple method that builds a global map using MDS and a more complicated one that builds small local maps and then patches them together to form a global map. Furthermore, least-squares optimization can be incorporated into the methods to further improve the solutions at the expense of additional computation. Through simulation studies on uniform as well as irregular networks, we show that the methods achieve more accurate solutions than previous methods, especially when there are few anchor nodes. They can even yield good relative maps when no anchor nodes are available.
[1] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, “Localization from Mere Connectivity,” Proc. ACM MobiHoc, pp. 201-212, June 2003.
[2] Y. Shang and W. Ruml, “Improved MDS-Based Localization,” Proc. IEEE Infocom, 2004.
[3] D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker, “An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks,” Technical Report ucla/csd-tr-02-0013, Computer Science Dept., Univ. of California, Los Angeles, 2002.
[4] E. Royer and C. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Comm., Apr. 1999.
[5] Y. Yu, R. Govindan, and D. Estrin, “Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks,” Technical Report ucla/csd-tr-01-0023, Computer Science Dept., Univ. of California, Los Angeles, May 2001.
[6] M. Chu, H. Haussecker, and F. Zhao, “Scalable Information-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks,” Int'l J. High Performance Computing Applications, June 2002.
[7] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,” Proc. Sixth Int'l Conf. Mobile Computing and Networks (ACM Mobicom), 2000.
[8] D.B. Johnson and D.B. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” Mobile Computing, T. Imielinski and H. Korth, eds., pp. 153-181, Kluwer Academic, 1996.
[9] B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. Sixth Int'l Conf. Mobile Computing and Networks (ACM Mobicom), 2000.
[10] I. Borg and P. Groenen, Modern Multidimensional Scaling, Theory and Applications New York: Springer-Verlag, 1997.
[11] J. Tenenbaum, V. de Silva, and J. Langford, “A Global Geometric Framework for Nonlinear Dimensionality Reduction,” Science, vol. 290, no. 5500, pp. 2319-2323, 2000.
[12] W. Glunt, T.L. Hayden, and M. Raydan, “Molecular Conformation from Distance Matrices,” J. Computational Chemistry, vol. 14, no. 1, pp. 114-120, 1993.
[13] W.S. Torgerson, “Multidimensional Scaling of Similarity,” Psychometrika, vol. 30, pp. 379-393, 1965.
[14] R.N. Shepard, “Analysis of Proximities: Multidimensional Scaling with an Unknown Distance Function I & II,” Psychometrika, vol. 27, pp. 125-140, 219-246, 1962.
[15] A. Savvides, H. Park, and M. Srivastava, “The Bits and Flops of the n-Hop Multilateration Primitive for Node Localization Problems,” Proc. First ACM Int'l Workshop Wireless Sensor Networks and Applications (WSNA '02), pp. 112-121, Sept. 2002.
[16] C. Savarese, J. Rabaey, and K. Langendoen, “Robust Positioning Algorithm for Distributed Ad-Hoc Wireless Sensor Networks,” Proc. USENIX Technical Ann. Conf., June 2002.
[17] J. Hightower and G. Boriello, “Location Systems for Ubiquitous Computing,” Computer, vol. 34, no. 8, pp. 57-66, Aug. 2001.
[18] A. Savvides, C.C. Han, and M. Srivastava, “Dynamic Fine-Grained Localization in Ad Hoc Networks of Sensors,” Proc. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MOBICON), July 2001.
[19] A. Nasipuri and K. Li, “A Directionality Based Location Discovery Scheme for Wireless Sensor Networks,” Proc. First ACM Int'l Workshop Wireless Sensor Networks and Applications (WSNA '02), pp. 105-111, Sept. 2002.
[20] A. Howard, M.J. Mataric, and G.S. Sukhatme, “Relaxation on a Mesh: A Formalism for Generalized Localization,” Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS '01), pp. 1055-1060, 2001.
[21] S.I. Roumeliotis and G.A. Bekey, “Synergetic Localization for Groups of Mobile Robots,” Proc. 39th IEEE Conf. Decision and Control, Dec. 2000.
[22] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-Less Low-Cost Outdoor Localization for Very Small Devices,” IEEE Personal Comm., vol. 7, no. 5, pp. 28-34, Oct. 2000.
[23] L. Doherty, L. El Ghaoui, and K. Pister, “Convex Position Estimation in Wireless Sensor Networks,” Proc. Infocom 2001, Apr. 2001.
[24] D. Niculescu and B. Nath, “Ad-Hoc Positioning System,” Proc. IEEE GlobeCom, Nov. 2001.
[25] A. Cerpa and D. Estrin, “Ascent: Adaptive Self-Configuring Sensor Networks Topologies,” Proc. IEEE InfoComm, June 2002.
[26] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” ACM Wireless Networks J., vol. 8, no. 5, Sept. 2002.
[27] Y. Xu, J. Heidemann, and D. Estrin, “Geography-Informed Energy Conservation for Ad Hoc Routing,” Proc. ACM MobiComm, July 2001.
Index Terms:
Wireless sensor networks, optimization, position estimation.
Citation:
Yi Shang, Wheeler Ruml, Ying Zhang, Markus Fromherz, "Localization from Connectivity in Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 11, pp. 961-974, Nov. 2004, doi:10.1109/TPDS.2004.67
