Abstract

A Wireless sensor network(WSN) is composed of a large number of sensor nodes, which are densely deployed either inside the phenomenon or very close to it. Unlike traditional networks, a WSN has its own design and resource constraints. As sensor nodes operate on limited battery power, energy usage is a very important concern in a WSN; and there has been significant research focus that revolves around harvesting and minimizing energy. In the proposed work , assuming the WSN to be large scale and non uniform an algorithm is proposed which includes- selection of cluster head from dominating set node,creation of clusters with one and only one cluster head and Relay node deployment in clusters and between cluster heads. In this algorithm, approach of clustering and relay node placement are combined for efficient utilization of energy, thus maximizing network lifetime.

References

• I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks Journal 38 (2002) 393- 422.
• Jian Tang*, Bin Hao, Arunabha Sen, Relay node placement in large scale wireless sensor networks, Computer Communications 29 (2006) 490 501
• Y. T. Hou, Y. Shi, H. D. Sherali and S. F. Midkiff; Prolonging sensor network lifetime with energy provisioning and relay node placement; Secon05; pp. 295 304.
• J. Bredin, E. Demaine, M. Hajiaghayi and D. Rus; Deploying sensor networks with guaranteed capacity and fault tolerance; Mobihoc05; pp. 309- 319.
• X. Cheng, D. Z. Du, L. Wang and B. Xu; Relay sensor placement in wireless sensor networks; ACM/Springer WINET07;
• A. Efrat, Sandor P. Fekete, P. Gaddehosur, J. Mitchell, V. Polishchuk and J. Suomela; Improved Approximation Algorithms for Relay Placement; ESA08; pp. 356 367.
• B. Hao, J. Tang and G. Xue; Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation; HPSR04; pp. 246-250.
• H. Liu, P. J. Wan and X. H. Jia; Fault-tolerant relay node placement in wireless sensor networks; LNCS; Vol. 3595(2005), pp. 230 239.
• E. Lloyd and G. Xue; Relay node placement in wireless sensor networks; IEEE Transactions on Computers; Vol. 56(2007), pp. 134138.
• S. Misra, S. Hong, G. Xue and J. Tang; Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements; Infocom08.
• ] J. Pan, Y. T. Hou, L. Cai, Y. Shi, S. X. Shen; Topology control for wireless sensor networks; Mobicom03, pp. 286299.
• A. Srinivas, G. Zussman, and E. Modiano; Mobile backbone networks Construction and maintenance, Mobihoc06, pp. 166177.
• K. Xu, H. Hassanein, G. Takahara and Q. Wang; Relay node deployment strategies in heterogeneous wireless sensor networks: multiple-hop communication case; Secon05, pp. 575- 585.
• W. Zhang, G. Xue, and S. Misra; Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms; Infocom07; pp. 16491657.
• A. Kashyap, S. Khuller and M. Shayman; Relay placement for higher order connectivity in wireless sensor networks; Infocom06.
• D. Estrin, R. Govindan, J. Heidemann, S. Kumar, Next century challenges: scalable coordination in sensor networks, ACM MobiCom99, Washingtion, USA, 1999, pp. 263270.
• G. Hoblos, M. Staroswiecki, A. Aitouche, Optimal design of fault tolerant sensor networks, IEEE International Conference on Control Applications, Anchorage, AK, September 2000, pp. 467472.
• D. Nadig, S. S. Iyengar, A new architecture for distributed sensor integration, Proceedings of IEEE Southeastcon93, Charlotte, NC, April 1993.
• C. Shen, C. Srisathapornphat, C. Jaikaeo, Sensor information networking architecture and applications, IEEE Personal Communications, August 2001, pp. 5259.
• E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, A. Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of ACM MobiCom01, Rome, Italy, July 2001, pp. 272286 .
• S. Cho, A. Chandrakasan, Energy-efficient protocols for low duty cycle wireless microsensor, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI Vol. 2 (2000), p. 10.
• N. Bulusu, D. Estrin, L. Girod, J. Heidemann, Scalable coordination for wireless sensor networks: self-configuring localization systems, International Symposium on Communication Theory and Applications (ISCTA 2001), Ambleside, UK, July 2001.
• C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm forsensor networks, Proceedings of the ACM Mobi- Com00, Boston, MA, 2000, pp. 5667.
• J. M. Kahn, R. H. Katz, K. S. J. Pister, Next century challenges: mobile networking for smart dust, Proceedings of the ACM MobiCom99, Washington, USA, 1999, pp. 271278.
• G. J. Pottie, W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM 43 (5) (2000) 551 558.
• A. Porret, T. Melly, C. C. Enz, E. A. Vittoz, A low-power low-voltage transceiver architecture suitable for wireless distributed sensors network, IEEE International Symposium on Circuits and Systems00, Geneva, Vol. 1, 2000, pp. 5659.
• Weiyi Zhang, Guoliang Xue and Satyajayant Misra, Fault- Tolerant Relay Node Placement inWireless Sensor Networks: Problems and Algorithms, 2007 IEEE
• Y. Thomas Hou, Senior Member, IEEE, Yi Shi, Student Member, IEEE,Hanif D. Sherali, and Scott F. Midkiff, Senior Member, IEEE, On Energy Provisioning and Relay Node Placement for Wireless Sensor Networks, IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 4, NO. 5, SEPTEMBER 2005
• K. Lu G. Liu R. Mao Y. Feng, Relay node placement based on balancing power consumption in wireless sensor networks, The Institution of Engineering and Technology 2011
• Hai Liu, Peng-Jun Wan, and Xiaohua Jia, Fault-Tolerant Relay Node Placement in Wireless Sensor Networks, Springer- Verlag Berlin Heidelberg 2005
• Santhosh Pandey ,Shaoqiang Dong ,Prathima Agrawal ,Krishna M. Sivalingam, On Performance of Node Placement Approaches for Hierarchical Heterogeneous Sensor Networks, Springer Science + Business Media, LLC 2008
• Dejun Yang, Satyajayant Misra, Xi Fang, Guoliang Xue, and Junshan Zhang, Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Efficient Approximations, 2010 IEEE
• R. Agrawal, and R. Srikant, Fast Algorithms for Mining Association Rules, Proceedings of the 20th VLDB, pp. 487499, 1994.
• S. K. Chong, S. Krishnaswamy, S. W. Loke, and Mohamed Gaber, Using Association Rules for Energy Conservation in Wireless Sensor Networks, Proceedings of the 23rd ACM Symposium on Applied Computing, Brazil, 2008.
• A. Deshpande, C. Guestrin, and S. R. Madden, Using Probabilistic Models for Data Management in Acquisitional Environments, Proceedings of the 2005 CIDR Conference, 2005.
• W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Networks, IEEE Transactions onWireless Communications, Vol. 1, pp. 600-670, 2002.
• W. Hu, V. N. Tran, N. Bulusu, C. T. Chou, S. Jha, and A. Taylor. The Design and Evaluation of a Hybrid Sensor Network for Canetoad Monitoring, Proceedings of Information Processing in Sensor Networks (IPSN 2005/SPOTS 2005), Los Angeles, 2005.
• P. Levis, N. Lee, M. Welsh, and D. Culler, TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications, SenSys 2003, 2003.
• K. K. Loo, I. Tong, B. Kao, and D. Cheung, Online Algorithms for Mining Inter-Stream Associations From Large Sensor Networks, PAKDD, pp. 143-149, 2005.
• R. Marin-Perianu, M. Marin-Perianu, and P. Havinga, Movementbased Group Awareness withWireless Sensor Networks, Proceedings of Pervasive 2007, 2007.
• V. S. Anitha, M. P. Sebastian, A Connected Dominating Setbased Weighted Clustering Algorithm for Wireless Sensor Networks, IEEE 2010
• L. Jia, R. Rajaraman, and T. Suel, An efficient distributed algorithm for constructing small dominating sets, Distrib. Comput. , vol. 15, no. 4, pp. 193205, 2002.
• Julia Albath, Mayur Thakur, Sanjay Madria, Energy Constrained Dominating Set for Clustering in Wireless Sensor Networks, 24th IEEE International Conference on Advanced Information Networking and Applications, 2-5, 2010
• Bolian Yin, Hongchi Shi, Yi Shang , An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks, J. Parallel Distributed Computing 71(2011) 27-39
• Do-hyun Nam, hong-ki min, An Efficient Ad-Hoc Routing Using aHybrid Clustering Method in a Wireless Sensor Network, Wirelessand Mobile Computing, Networking and Communications, pp. 60-60, Oct 2007.
• A. A. Abbasi and M. Younis, A survey on clustering algorithms for wireless sensor networks, Computer Communications, 30, 28262841, 2007.
• Wendi B Heinzelman, Anantha P. Chandrashekhan, Hari Balakrishan, An application specific protocol architecture for wireless Senesor Network, IEEE 2002
• Ma Chaw Mon Thein, Thandar Thein , An energy efficient Cluster Head Selection forWireless Sensor network, 2010 Int. Conf. on Intelligent systems, Modelling and simulation.
• 0. Younis, et. al. , HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for AdHoc Sensor Networks, IEEE Transactions on Mobile Computing, 3(4):660-669, 2004.
• S. Lindsey, et. al. ,PEG ASIS: Power-Efficient Gathering in Sensor Information Systems, IEEE Aerospace Conference Proceedings, Vol. 3, 9-16 gust, pp. 102-114, 2002.
• Shujuan Jin, Keqiu Li, LBCS: A Load Balanced Clustering Scheme in Wireless Sensor Networks, 2009 Third International Conference on Multimedia and Ubiquitous Engineering, IEEE
• Suan Khai Chong, Mohamed Medhat Gaber, A rule Learning approach to energy efficient clustering in wireless sensor network , 2008 IEEE