An Energy-Efficient Clique-Based Geocast Algorithm for Dense Sensor Networks

Alain Bertrand Bomgni, Jean Frédéric Myoupo

.

DOI: 10.4236/cn.2010.22019                

Abstract

This paper proposes an energy-efficient geocast algorithm for wireless sensor networks with guaranteed de-livery of packets from the sink to all nodes located in several geocast regions. Our approach is different from those existing in the literature. We first propose a hybrid clustering scheme: in the first phase we partition the network in cliques using an existing energy-efficient clustering protocol. Next the set of clusterheads of cliques are in their turn partitioned using an energy-efficient hierarchical clustering. Our approach to con-sume less energy falls into the category of energy-efficient clustering algorithm in which the clusterhead is located in the central area of the cluster. Since each cluster is a clique, each sensor is at one hop to the cluster head. This contributes to use less energy for transmission to and from the clusterhead, comparatively to multi hop clustering. Moreover we use the strategy of asleep-awake to minimize energy consumption during extra clique broadcasts.

Keywords

Geocast, Wireless Sensor Networks, Clustering, Clique, Energy Consumption

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	T. Imielinski and J. Navas, “GPS-based Addressing and Routing,” RFC 2009 Computer Science, Rutgers Univer-sity Press, Rutgers, March 1996.
[2]	Y.-B. Ko and N. H. Vaidya, “Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks,” MONET, Vol. 7, No. 6, 2002, pp. 471-480.
[3]	D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS),” Proceedings of IEEE Global Telecommunications Conference, San Antonio, 25-29 November 2001, pp. 2926-2931.
[4]	E. Kranakis, H. Singh and J. Urrutia, “Compass Routing on Geometric Networks,” Proceedings of 11th Canadian Conference on Computational Geometry, Vancouver, 15- 18 August 1999, pp. 51-54.
[5]	K. Seada and A. Helmy, “Efficient Geocasting with Per-fect Delivery in Wireless Networks,” IEEE Wireless Communications and Networking Conference, Atlanta, 21-25 March 2004, pp. 2551-2556.
[6]	I. Stojmenovic, “Geocasting with Guaranteed Delivery in Sensor Networks,” IEEE Wireless Communications, Vol. 11, No. 6, December 2004, pp. 29-37.
[7]	J. Lian, K. Naik, Y. Liu and L. Chen, “Virtual Surround-ing Face Geocasting with Guaranteed Message Delivery for Sensor Networks,” Proceedings of the 14th IEEE In-ternational Conference on Network Protocols, Santa Barbara, 12-15 November 2006, pp. 198-207.
[8]	Y.-M. Song, S.-H. Lee and Y.-B. Ko, “FERMA: An Effi-cient Geocasting Protocol for Wireless Sensor Networks with Multiple Target Regions,” Lecture Notes on Com-puter Science, Vol. 3823, 2005, pp. 1138-1147.
[9]	Chih-Yung Chang, Chao-Tsun Chang and Shin-Chih Tu, “Obstacle-Free Geocasting Protocols for Single/Multi- Destination Short Message Services in Ad Hoc Networks,” Wireless Networks, Vol. 9, No. 2, 2003, pp. 143-155.
[10]	L. Choi, J. K. Jung, B.-H. Cho and H. Choi, “M-Geocast: Robust and Energy-Efficient Geometric Routing for Mo-bile Sensor Networks,” Lecture Notes in Computer Science, Vol. 5287, 2008, pp. 304-316.
[11]	Y.-C. Shim, “Energy Efficient Geocast Protocol for Sen-sor Networks,” Proceedings of the 6th WSEAS Interna-tional Conference on Electronics, Hardware, Wireless and Optical Communications, Corfu, 16-19 February 2007, pp. 28-34.
[12]	W. Zhang, X. Jia and C. Huang, “Distributed Ener-gy-Efficient Geographic Multicast for Wireless Sensor Networks,” International Journal of Wireless and Mobile Computing, Vol. 1, 2006, pp. 141-147.
[13]	Advanced Micro Devices, “White Paper: Magic Packet Technology,” November 1995. http://www.amd.com/us-en /assets/content_type/white_papers_and_tech_docs/20213. pdf
[14]	D. Baker and A. Ephremides, “The Architectural Or-ganization of a Mobile Radio Network via Distributed Algorithm,” IEEE Transactions on Communications, Vol. 29, No. 11, November 1981, pp. 1694-1701.
[15]	S. Banerjee and S. Khuller. “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks”, Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchor-age, Vol. 2, 22-26 April 2001, pp. 1028-1037.
[16]	A. B. Bomgni, J. F. Myoupo and A. O. Cheikhna, “Ran-domized Multi-Stage Clustering-Based Geocast Algo-rithms in Anonymous Wireless Sensor Networks,” 5th IEEE/ACM International Wireless Communications and Mobile Computing Conference, Leipzig, 21-24 June 2009, pp. 286-291.
[17]	M. Gerla and J. T. C. Tsai, “Multicluster, Mobile, Multi-media Radio Network”, Wireless Networks, Vol. 1, No. 3, 1995, pp. 255-265.
[18]	S. Basagni, “Distributed Clustering for Ad Hoc Net-works,” Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks, Fremantle, 23-25 June 1999, pp. 310-315.
[19]	K. Sun, P. Peng and P. Ning, “Secure Distributed Cluster Formation in Wireless Sensor Networks,” 22nd Annual Computer Security Applications Conference, Las Vegas, 11-15 December 2006, pp. 131-140.
[20]	P. Tosic and G. Agha. “Maximal Clique Based Distributed Coalition Formation for Task Allocation in Large-Scale Multi-agent Systems”. Lecture Notes in Computer Science, Vol. 3446, 2005, pp. 104-120.
[21]	W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the 33th IEEE Hawii International Conference on Systems, Hawii, 4-7 January 2000, pp. 3005-3014.
[22]	J. S. Liu and C. H. R. Lin, “Energy-Efficient Clustering Protocol in Wireless Sensor Networks,” Ad Hoc Networks, Vol. 3, No. 3, May 2005, pp. 371-388.
[23]	D. Wei, S. Kaplan and H. A. Chan, “Energy Efficient Clustering Algorithms for Wireless, Sensor Networks,” Proceedings of IEEE Conference on Communications, Beijing, 19-23 May 2008, pp. 236-240.
[24]	Y. Zhou, M. Hart, S. Vadgama and A. Rouz. “A Hierar-chical Clustering Method in wireless Ad Hoc Sensor Networks,” Proceedings of International Conference on Communications, Glasgow, 24-28 June 2007, pp. 3505- 3509.
[25]	J. Lewis, “Wake on LAN over Wireless,” 2008. http:// www.johnlewis.ie/2008/07/10/wake-on-lan-over-wireless
[26]	W. Wang and A. Jantsch, “An Algorithm for Electing Cluster Heads Based on Maximum Residual Energy,” Proceedings of International Wireless Communications and Mobile Computing Conference, Vancouver, 3-6 June 2006, pp. 1465-1470.
[27]	O. Younis and S. Fahmy, “HEED: A Hybrid, Energy- Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks,” IEEE Transactions on Mobile Com-puting, Vol. 3, No. 4, 2004, pp. 366-379.
[28]	J. A. Sanchez, P. M. Ruiz and I. Stojmenovic, “Ener-gy-Efficient Geographic Multicast Routing for Sensor and Actuator Networks,” Computer Communications, Vol. 30, No. 13, September 2007, pp. 2519-2531.
[29]	J. A. Sanchez, P. M. Ruiz and I. Stojmenovic, “GMR: Geographic Multicast Routing for Wireless Sensor Net-works,” Proceedings of the 3rd Sensor and Ad Hoc Communications and Networks, Reston, 25-28 September 2006, pp. 20-29.