WSN  Vol.3 No.6 , June 2011
MDS and Trilateration Based Localization in Wireless Sensor Network
ABSTRACT
Localization of sensor nodes is crucial in Wireless Sensor Network because of applications like surveillance, tracking, navigation etc. Various optimization techniques for localization have been proposed in literature by different researchers. In this paper, we propose a two phase hybrid approach for localization using Multidi- mensional Scaling and trilateration, namely, MDS with refinement using trilateration. Trilateration refines the estimated locations obtained by the MDS algorithm and hence acts as a post optimizer which improves the accuracy of the estimated positions of sensor nodes. Through extensive simulations, we have shown that the proposed algorithm is more robust to noise than previous approaches and provides higher accuracy for estimating the positions of sensor nodes.

Cite this paper
nullS. Patil and M. Zaveri, "MDS and Trilateration Based Localization in Wireless Sensor Network," Wireless Sensor Network, Vol. 3 No. 6, 2011, pp. 198-208. doi: 10.4236/wsn.2011.36023.
References
[1]   M. Li and L. Yunghao, “Underground Structure Moni-toring with Wireless Sensor Networks,” Proceedings of International Symposium on Information Processing in Sensor Networks, 25-27 April 2007, pp.69-78. doi:10.1109/IPSN.2007.4379666

[2]   N. Alsharabi, L. R. Fa, F. Zing and M. Ghurab, “Wireless Sensor Networks of Battlefields Hotspot Challenges and Solutions,” Proceedings of Sixth International Confer-ence on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, 2008, pp.192- 196. doi:10.1109/WIOPT.2008.4586064

[3]   M. Hefeeda and M. Bagheri, “Wireless Sensor Networks for Early Detection of Forest Fires,” Proceedings of In-ternational Conference on Mobile Ad Hoc and Sensor Systems, 8-11 October 2007, pp. 1-6. doi:10.1109/MOBHOC.2007.4428702

[4]   N. Bulusu, J. Heidemann and D. Estrin, “GPS-Less Low Cost Outdoor Localization for Very Small Devices,” IEEE Transactions on Personal Communication, Vol. 7, No. 5, 2002, pp. 28-34.

[5]   M. Chu, H. Haussecker and F. Zhao, “Scalable Informa-tion-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks,” International Journal of High Performance Computing Applications, Vol. 16, No. 3, 2002, pp.1-22. doi:10.1177/10943420020160030901

[6]   B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of Sixth International Conference on Mobile Computing and Networks (ACM Mobicom), 2000, pp.1-10.

[7]   Y. Yu, R. Govindan and D. Estrin, “Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks,” University of California, Los Angeles Computer Science Department Technical Report UCLA/CSD-TR-01-0023, May 2001. http://citeseerx.ist.psu.edu

[8]   Z. Guo and M. C. Zhou, “Optimal Tracking Interval for Predictive Tracking in Wireless Sensor Network,” IEEE Communication Letters, Vol. 9, No. 9, 2005, pp. 805-807. doi:10.1109/LCOMM.2005.1506709

[9]   Y. Shang, W. Ruml, Y. Zhang and M. Fromherz, “Local-ization from Mere Connectivity,” The 4th ACM Interna-tional Symposium on Mobile and Ad-Hoc Networking & Computing Symposium on Mobile and Ad-Hoc Network-ing & Computing, 2003, pp. 201-212.

[10]   I. Borg and P. Groenen, “Modern Multidimensional Scaling, Theory and Applications,” Springer-Verlag, New York, 1997.

[11]   W. S. Torgeson, “Multidimensional Scaling of Similar-ity,” Psychometrika, Vol. 30, No. 4, 1965, pp. 379-393. doi:10.1007/BF02289530

[12]   R. N. Shepard, “The Analysis of Proximities: Multidi-mensional Scaling with an Unknown Distance Function,” Psychometrika, Vol. 27, No. 2, 1962, pp. 125-140. doi:10.1007/BF02289630

[13]   Y. Shang, W Ruml, Y. Zhang and M. Fromherz, “Local-ization from Connectivity in Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 11, 2004, pp. 961-974. doi:10.1109/TPDS.2004.67

[14]   T. Hornoch, “Notes on the Adjustment of Trilateration,” Survey Review, Vol. 18, No. 135, 1965, pp. 14-18.

[15]   G. Q. Mao, B. Fidan and B. D. O. Anderson, “Wireless sensor Network Localization Techniques,” The Interna-tional Journal of Computer and Telecommunications Networking Computer Networks, Vol. 51, No. 10, 2007, pp. 2529-2553.

[16]   I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Networks,” Computer Networks, 2002, pp. 393-422. doi:10.1016/S1389-1286(01)00302-4

[17]   X. Li, H. Shi and Y. Shang, “A Sorted RSSI Quantization Based Algorithm for Sensor Network Localization,” Proceedings of 11th International Conference on Parallel and Distributed Systems, 2005, pp. 557-563.

[18]   P. Xing, H. Yu and Y. Zhang, “An Assisting Localization Method for Wireless Sensor Networks,” Proceedings of Second International Conference on Mobile Technology, Applications and Systems, 15-17 November 2005, pp. 1-6.

[19]   T. He, C. Huang, B. Blum, J. Stankovic and T. Abdelza-her, “Range-Free Localization Schemes for Large Scale Sensor Networks,” Proceedings of the Ninth Annual In-ternational Conference on Mobile Computing and Net-working (ACM Mobicom), San Diego, September 2003, pp. 81-95.

[20]   D. Niculescu and B. Nath, “Adhoc Positioning System,” Proceedings of the Global Telecommunications Confer-ence, San Antonio, 2001, pp. 2926-2931.

[21]   C. Savarese, J. Rabay and K. Langendoen, “Robust Posi-tioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks,” USENIX Technical Annual conference, June 2002, pp. 1-10.

[22]   A. Savvides, C. Han and M. B. Srivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sen-sors,” Proceedings of the 7th Annual International Con-ference on Mobile Computing and Networking (ACM Mobicom), 2001, pp. 166-179.

[23]   F. Tian, W. Guo, C. Wang and Q. Gao, “Robust Local-ization Based on Adjustment of Trilateration Network for Wireless Sensor Networks,” Proceedings of 4th Interna-tional Conference on Wireless Communications, Network-ing and Mobile Computing, WiCOM’8, 2008, pp. 1-4.

[24]   A. Savvides, H. Park and M. B. Srivastava, “The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems,” Proceedings of the 1st ACM In-ternational Workshop on Wireless Sensor Networks and Applications, WSNA’2, 2002, pp. 112-121.

[25]   L. Doherty, K. pister and L. El. Ghaoui, “Convex Posi-tion Estimation in Wireless Sensor Networks,” Proceed-ings of IEEE INFOCOM 2001, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001, Vol. 3, pp. 1655-1663.

[26]   P. Biswas and Y. Ye, “Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization,” Third In-ternational Symposium on Information Processing in Sensor Network, April 2004, pp. 46-54. doi:10.1145/984622.984630

[27]   T. C. Liang, T. C. Wang and Y. Ye, “A Gradient Search Method to Round the Semidefinite Programming Relaxa-tion Solution for Ad Hoc Wireless Sensor Network Lo-calization,” Stanford University, Formal Report 5, 2004. http: //www.stanford. edu/-yyye/ formal-report5. pdf

[28]   B. Borchers, “ CSDP-A C Library for Semidefinite Pro-gramming,” Optimization Methods and Software, Vol. 11, No. 1, 1999, pp. 613-623. doi:10.1080/10556789908805765

 
 
Top