Genetic-algorithm-based construction of Load-Balanced CDSs in Wireless Sensor Networks
Authors:
- 1 November 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21557578,p. 667-672
Abstract
A Connected Dominating Set (CDS) is used as a virtual backbone for efficient routing and broadcasting in Wireless Sensor Networks (WSNs). Most existing works focus on constructing a Minimum CDS (MCDS), a k-connect m-dominating CDS, a minimum routing cost CDS or a bounded-diameter CDS. However, no work considers the load-balance factor of CDSs in WSNs. In this paper, we propose a novel problem - the Load-Balanced CDS (LBCDS) problem, in which constructing an LBCDS and load-balancedly allocating dominatees to dominators are investigated simultaneously. A Genetic Algorithm (GA) based strategy called LBCDS-GA is proposed to construct an LBCDS in a WSN. As a matter of fact, constructing a CDS as a virtual backbone in a WSN is an efficient way to extend network lifetime through reducing the number of the nodes involved in communication, while building an LBCDS and load-balancedly allocating dominatees to dominators can further prolong network lifetime through balancing the workloads of all the dominators. Through extensive simulations, we demonstrate that our proposed methods extend network lifetime by 65% on average compared with the best and latest MCDS construction algorithm.Keywords
This publication has 17 references indexed in Scilit:
- A Genetic Algorithm for Constructing a Reliable MCDS in Probabilistic Wireless Networks2011
- Hybrid Genetic Algorithm Using a Forward Encoding Scheme for Lifetime Maximization of Wireless Sensor NetworksIEEE Transactions on Evolutionary Computation, 2010
- A New Constant Factor Approximation for Computing 3-Connected m-Dominating Sets in Homogeneous Wireless Networks2010
- Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks2010
- A genetic algorithm based approach for energy efficient routing in two-tiered sensor networksAd Hoc Networks, 2009
- A p-norm Flow Optimization Problem in Dense Wireless Sensor Networks2008
- An extended localized algorithm for connected dominating set formation in ad hoc wireless networksIEEE Transactions on Parallel and Distributed Systems, 2004
- Routing in ad-hoc networks using minimum connected dominating sets2002
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- The broadcast storm problem in a mobile ad hoc network1999