Open Access Open Access  Restricted Access Subscription or Fee Access

Localization in Wireless Sensor Network through Constraint Satisfaction

Vikash Kumar, Anoop Kumar Yadav, Itu Snigdh

Abstract


To obtain a satisfactory performance in the wireless sensor network, optimal placement of sensors and routing is the most important aspect. In order to get optimal coverage in a given field for surveillance, we propose hexagonal cellular grid approach. The proposed approach is aimed at optimizing coverage and efficient placement of sensors under the constraints of number of sensors required, observe events of interest and communication between sensors. By computational geometry, specifically Voronoi Diagram and Delaunay Triangulation, we establish the main highlight of the paper – optimal placement of sensors and routing. Experimental results for an example sensor field demonstrate the application of our approach.

Keywords


Delaunay Triangulation, Localization, Sensor Deployment, Voronoi Diagram.

Full Text:

PDF

References


C. Y. Chong, and S. P Kumar, “Sensor networks: evolution, opportunities, and challenges,” Proceedings of the IEEE, Vol. 91, No. 8, pp. 1247–1256, 2003.

H. Zhang and A. Arora, “GS3: Scalable self-configuration and self-healing in wireless networks,” in Annual ACM Symposium on Principles of Distributed Computing, Monterey, California, pp. 58 - 67, 2002.

E. Biagioni and G. Sasaki, “Wireless sensor placement for reliable and efficient data collection,” Proc. Hawaii Int. Conf. Syst. Sci., Jan., 2003.

H. Qi, S. S. Iyengar, and K. Chakrabarty, “Distributed Sensor Fusion – A Review of Recent Research,” Journal of the Franklin Institute, Vol. 338, pp. 655–668, 2001.

S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Worst and best-case coverage in sensor networks,” IEEE Transactions on Mobile Computing, Vol. 4, pp. 84- 92, 2005.

H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” in NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.

X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in SenSys ’03: Proceedings of the 1st international conference on Embedded networked sensor systems. ACM Press, February 2003, pp. 28–39.

D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in ACM Int’l Workshop on Wireless Sensor Networks and Applications (WSNA), 2002.

F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang, “Peas: A robust energy conserving protocol for long-lived sensor networks,” in ICDCS’03: Proceedings of the 23rd International Conference on Distributed Computing Systems. IEEE Computer Society, May 2003, p. 28.

S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Coverage problems in wireless ad-hoc sensor networks,” in INFOCOM, April 2001, pp. 1380-1387.

S. Capkun, Maher Hamdi, and J. P. Hubaux, “GPS-free positioning in mobile ad-hoc networks,” Cluster Computing, vol. 5, no. 2, April 2002.

M. Marengoni, B.A. Draper, A. Hanson, R.A. Sitaraman, “System to place observers on a polyhedral terrain in polynomial time,” Image and Vision Computing, vol.18, pp. 773-80, Dec. 1996.

L. Doherty, K. S. J. Pister, and L. El Ghaoui, “Convex position estimation in wireless sensor networks,” in Proc. IEEE Infocom 2001, Anchorage AK, Apr. 2001, vol. 3, pp. 1655–1663.

W.W. Gregg, W.E. Esaias, G.C. Feldman, R. Frouin, S.B. Hooker, C.R. McClain, R.H. Woodward, “Coverage opportunities for global ocean color in a multimission era”, IEEE Transactions on Geoscience and Remote Sensing, vol.36, pp. 1620-7, Sept. 1998.

X.-Y. Li, P.-J. Wan, O. Frieder “Coverage in wireless ad-hoc sensor networks”, IEEE Transactions on Computers, vol. 52, no. 6, pp. 753-763, June 2003.

H. Shu, Q. Liang, and J. Gao “Distributed sensor networks deployment using fuzzy logic systems,” International Journal of Wireless Information Networks, Vol. 14, No. 3, September 2007.

A. Savvides, C.C. Han, and M.B. Srivastava, "Dynamic fine-grained localization in ad hoc networks of sensors," Proc. Seventh Ann. Int'l Conf. Mobile Computing and Networking (Mobi-COM 2001), July 2001.

S. Fortune, "Voronoi diagrams and Delaunay triangulations," Computing in Euclidean Geometry, F.K. Hwang and D.-Z. Du, eds., pp. 193-233, Singapore: World Scientific, 1992.

J. O'Rourke, Combinatorial Geometry in C. Cambridge, 1998.

F.P. Preparata and M.I. Shamos, “Computational geometry: An introduction”. Springer-Verlag, 1985.

Md. B. Haider, K. Sugihara, "Almost Delaunay Triangulation Routing in Wireless Sensor Networks," 10th international conference on Computer and information technology, 2008. iccit 2007. pp. 1-7, Dec. 2007.

F. Aurenhammer, “Voronoi Diagrams – A survey of a fundamental geometric data structure,” ACM Computing Surveys 23, pp. 345-405, 1991.

K. Mulmuley, “Computational geometry: An introduction through randomized algorithms,” Prentice-Hall, 1994.

Chun-Hsien Wu, Kuo-Chuan Lee and Yeh-Ching Chung, “A delaunay triangulation based method for wireless sensor network deployment,” Proceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 1, pp-253-260, 2006.

P. Bose, P. Morin, I. Stojmenovic and J. Urrutia. “Routing with guaranteed delivery in ad hoc wireless networks”. Wireless Networking, 7(6):609--616, 2001.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.