| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Localization through Map Stitching in Wireless Sensor Networks
January 2008 (vol. 19 no. 1)
pp. 93-105
Node localization is an essential problem in ad hoc wireless sensor networks. The map stitching is a type of localization algorithm that has received a great deal of attention recently. In this algorithm, the network is divided into small overlapping subregions, each of which creates a local map. Then, the local maps are stitched together to form a single global map. In this paper, we first propose a new technique for map-to-map stitching which exploits every available distances between two maps. Next, we propose a few anchor-free localization algorithms based on our stitching technique. We experimentally studied the performance of our algorithms under various settings. The results show that our method achieves a significant performance improvement upon the existing method.
[1] 93 J. Bachrach and C. Taylor, “Localization in Sensor Networks,” Handbook of Sensor Networks: Algorithms and Architectures, Wiley-Interscience, 2005.[2] T. Cox and M. Cox, Multidimensional Scaling, second ed. Chapman & Hall, 2001.[3] I. Cidon and O. Mokryn, “Propagation and Leader Election in a Multihop Broadcast Environment,” Proc. 12th Int'l Symp. Distributed Computing (DISC '98), 1998.[4] G.E. Forsythe and G.H. Golub, “On the Stationary Values of a Second Degree Polynomial on the Unit Sphere,” SIAM J. Applied Math., vol. 13, pp. 1050-1068, 1965.[5] W. Harger, “Minimizing a Quadratic over a Sphere,” SIAM J.Optimization, vol. 12, pp. 188-208, 2001.[6] B.K.P. Horn, H. Hilden, and S. Negahdaripour, “Closed-Form Solution of Absolute Orientation Using Orthonormal Matrices,” J.Optical Soc. of Am. A, vol. 5, no. 7, 1988.[7] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,” Proc. MobiCom '00, pp. 56-67, 2000.[8] J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris, “A Scalable Location Service for Geographic Ad Hoc Routing,” Proc. MobiCom '00, Aug. 2000.[9] X. Ji and H. Zha, “Sensor Positioning in Wireless Ad Hoc Networks Using Multidimensional Scaling,” Proc. IEEE INFOCOM, 2004.[10] L. Meertens and S. Fitzpatrick, “The Distributed Construction of a Global Coordinate System in a Network of Static Computational Nodes from Inter-Node Distances,” Technical Report KES.U.04.04, Kestrel Inst., 2004.[11] S. Madden, M. Franklin, J. Hellerstein, and W. Hong, “TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks,” Proc. Fifth Usenix Symp. Operating Systems Design and Implementation (OSDI '02), Dec. 2002.[12] D. Moore, J. Leonard, D. Rus, and S. Teller, “Robust Distributed Network Localization with Noisy Range Measurements,” Proc. Second ACM Int'l Conf. Embedded Networked Sensor Systems (SenSys '04), Nov. 2004.[13] D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks,” Telecomm. Systems, vol. 22, nos. 1-4, pp. 267-280, 2003.[14] O.H. Kwon and H.J. Song, “A New Map Stitching Method for Anchor-Free Localization in Wireless Sensor Networks,” Proc. Sixth IEEE Int'l Conf. Computer and Information Technology (CIT '06), pp. 236-241, 2006.[15] N.B. Priynatha, H. Balakrishnan, E. Demaine, and S. Teller, “Anchor-Free Distributed Localization in Sensor Networks,” Technical Report No. 892, MIT Laboratory for Computer Science, Apr. 2003.[16] A. Savvides, C.-C. Han, and M.B. Srivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” Proc. MobiCom '01, July 2001.[17] Y. Shang and W. Ruml, “Improved MDS-Based Localization,” Proc. INFOCOM '04, 2004.[18] C. Savarese, J.M. Rabaey, and J. Beutel, “Locationing in Distributed Ad-Hoc Wireless Sensor Networks,” Proc. IEEE Int'l Conf. Acoustics, Speech, and Signal Processing (ICASSP '01), May 2001.[19] Y. Ye, “A New Complexity Result on Minimization of a Quadratic Function with a Sphere Constraint,” Recent Advances in Global Optimization, pp. 19-31, Princeton Univ. Press, 1992.
Index Terms:
wireless sensor network, location identification, localization algorithm, distributed algorithms
Citation:
Oh-Heum Kwon, Ha-Joo Song, "Localization through Map Stitching in Wireless Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 1, pp. 93-105, Jan. 2008, doi:10.1109/TPDS.2007.70706
