Distributed energy efficient backbone construction utilizing particle swarm ‎optimization algorithm in wireless sensor networks with bidirectional links

Connected dominating set (CDS) problem is the most widely used method for backbone formation ‎in wireless sensor networks. To date, numerous algorithms have been proposed for backbone ‎construction on minimum CDS (MCDS) problem in unit disk graphs (UDG); however, only a few ‎algorithms have been proposed on MCDS problem in disk graphs with bidirectional links (DGB) ‎and on degree-constrained minimum-weight CDS (DC-MWCDS) problem in UDG. To the best of ‎our knowledge, no work has been done on DC-MWCDS problem in DGB. In this paper, we present ‎OEDC-MWCDS problem (optimal energy and degree constrained minimum-weight connected ‎dominating set) for constructing energy efficient backbone in wireless sensor networks. Then, we ‎model a wireless sensor network as a disk graph with bidirectional links and propose a backbone ‎construction algorithm called EBC-PSO (Energy efficient Backbone Construction utilizing Particle ‎Swarm Optimization algorithm) to obtain a CDS with the minimum weight subject to the optimal ‎energy and degree constraint. The main objective of the proposed algorithm is to find the optimal ‎values of energy and degree of constraint to maximize network lifetime. In the proposed algorithm, ‎optimal coefficients of minimum remaining energy and maximum degree of nodes are determined ‎utilizing PSO algorithm. Then, in the selection of DS nodes, these coefficients are used. Simulation ‎results verify the performance of the proposed algorithm in terms of network lifetime and ‎backbone size.‎