Constructing MICDS Algorithm for Data Transmission using Maximal Independent Set in Network Graph
|
10.5120/18948-0040 |
G N Purohit, Seema Verma, Usha Sharma and Gargi Chauhan. Article: Constructing MICDS Algorithm for Data Transmission using Maximal Independent Set in Network Graph. International Journal of Computer Applications 108(10):19-24, December 2014. Full text available. BibTeX
@article{key:article,
author = {G. N. Purohit and Seema Verma and Usha Sharma and Gargi Chauhan},
title = {Article: Constructing MICDS Algorithm for Data Transmission using Maximal Independent Set in Network Graph},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {108},
number = {10},
pages = {19-24},
month = {December},
note = {Full text available}
}
Abstract
Wireless Sensor Networks (WSNs) is a distributed wireless network which consists of a large number of small (sensor) nodes with sensing, computation and wireless communication capabilities. These sensor nodes work together to monitor various applications and they communicate with each other in multiple hops or directly, with the objective of handing over the processed data to the sink node or access point (AP). WSNs have many issues like self-configuration, fault-tolerance, adaptation, flexibility, energy efficiency, security, scalability, interference, architectural issues, mobility and delay tolerance but the most critical and important issue is to reduce energy wastage and interference and increasing network lifetime [1,2, 3]. In order to manage these issues, WSNs require some virtual backbone. A Connected Dominating Set (CDS) can be used to create a virtual backbone in WSNs [5,6,7,8, 9,10]. The CDS is a dominating set which induces a connected subgraph. A maximal independent set is an independent set that is not a subset of any other independent set [7,8]. In this paper, proposed a MICDS (Maximal Independent Connected Dominating Set) algorithm for the WSNs, which are based on the construction of the maximal independent set (MIS) of the representing network graph. There are two different steps in the implementation of MICDS algorithm. In the first phase, the maximal independent set of the network is constructed. In second phase, the dominating set and connectors for the dominating set are constructed using MIS. Using the dominating set and connectors, all the data is transmitted to the sink node or access point (AP). The simulation results indicate that the MICDS algorithm reduce the interference and energy wastage in the network graph, further it also increases the lifetime of the network.
References
- Gargi Chauhan, Usha Sharma, Seema Verma and G. N. Purohit, "TDMA Scheduling Algorithm Using Independent Sets in Network Graph", Internatonal Journal of Computer and Technology,vol. 10,No. 10.
- Yiwei Wu and Yingshu Li, ``Connected Dominating Sets", to appear in Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols, Bentham Science, 2009.
- Pathan, A. S. K. ; Hyung-Woo Lee; Choong Seon Hong, "Security in wireless sensor networks: issues and challenges" Advanced Communication Technology (ICACT), Page(s):6, year 2006.
- Li Y. S, Thai M. T, Wang . F, Yi C. W, Wan P. J and Du D. Z, "On Greedy Construction Of Connected Dominating Sets in Wireless Networks", Journal of Wireless Communications and Mobile Computing, vol. 5, no. 8, pp. 927-932, 2005.
- Yaqian LI, Rongrong YIN, Haoran LIU, Xiaochen HAO," A Reliable Connected Dominating Set Algorithm in Wireless Sensor Networks", Journal of Computational Information Systems 8: 6 (2012) 2583-2592.
- Kamrul Islam, Selim G. Akl, and Henk Meijer, "Distributed Generation of a Family of Connected Dominating Sets in Wireless Sensor Networks", Distributed Computing in Sensor Systems - DCOSS , pp. 343-355, 2009.
- My T. Thai, Feng Wang, Dan Liu, Shiwei Zhu, Ding-Zhu Du, "Connected Dominating Sets in Wireless Networks with Different Transmission Ranges," IEEE Transactions on Mobile Computing, vol. 6, no. 7, pp. 721-730, July 2007, doi:10. 1109/TMC. 2007. 1034.
- Weili Wu, Hongwei Du, Xiaohua Jia, Yingshu Li, Scott C. -H. Huang," Minimum connected dominating sets and maximal independent sets in unit disk graphs", Theoretical Computer Science 352 (2006) 1 – 7.
- Kamrul Islam, Selim G Akl, and Henk Meijer, A Constant Factor Localized Algorithm for Computing Connected Dominating Sets inWireless Sensor Networks, Proc of 14th IEEE International Conference on Parallel and Distributed Systems, ICPADS. 2008.
- Sajid Hussain, Mubashsharul I. Shafique, Laurance T. Yang: Construction a CDS based network backbone for energy efficiency in industrial WSN,IEEE 2010.
- Yiwei Wu and Yingshu Li, "Construction Algorithms for k-Connected m-Dominating Sets in Wireless Sensor Networks," 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008), Hong Kong, China, May 26-30, 2008.
- Najla Al-Nabhan, Bowu Zhang, Mznah Al-Rodhaan, Abdullah Al-Dhelaan: Two Connected Dominating Set Algorithms for Wireless Sensor Networks. WASA 2012: 705-713.
- Xiaoyan Kui, Yu Sheng, Huakun Du, and Junbin Liang, "Constructing a CDS-Based Network Backbone for Data Collection in Wireless Sensor Networks", International Journal of Distributed Sensor Networks Volume 2013.
- Li, Y. , Zhu, S. , Thai, M. T. , Du, D. -Z. : Localized Construction of Connected Dominating Set in Wireless Networks. In: NSF International Workshop on Thoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks (2004).
- K. P. Sampoornam, Dr. K. Rameshwaran," Energy Efficient Routing Scheme for Sensor Networks Using Connected Dominating Set ", IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 5, No 2, September 2011 ISSN (Online): 1694-0814.