We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Genetic Algorithm with Immigrants Schemes for Constructing a ó-Reliable MCDS in Probabilistic Wireless Networks.
- Authors
JING (SELENA) HE; SHOULING JI; YI PAN; ZHIPENG CAI
- Abstract
Minimum Connected Dominating Sets (MCDSs) are used as virtual backbones for efficient routing and broadcasting in wireless networks extensively. However, the MCDS problem is NP-Complete even in Unit Disk Graphs. Therefore, many heuristic-based approximation algorithms have been proposed recently. In these approaches, networks are deterministic where two nodes are assumed either connected or disconnected. In most real applications, however, there are many intermittently connected wireless links called lossy links, which only provide probabilistic connectivity. For wireless networks with lossy links, we propose a Probabilistic Network Model (PNM). Under this model, we measure the quality of Connected Dominating Sets (CDSs) using CDS reliability defined as the minimum upper limit of the node-to-node delivery ratio between any pair of dominators in a CDS. We attempt to construct a MCDS while its reliability is above a preset application-specified threshold σ, called σ-Reliable MCDS (σ-RMCDS). We claim that constructing a σ-RMCDS is NP-Hard under the PNM model. We propose a novel Genetic Algorithm (GA) with immigrants schemes called RMCDS-GA to solve the σ-RMCDS problem. To evaluate the performance of RMCDS-GA, we conduct comprehensive simulations. The simulation results show that compared with the traditional MCDS algorithms. RMCDS-GA can construct a more reliable CDS without increasing the size of a CDS.
- Subjects
GENETIC algorithms; WIRELESS communications; APPROXIMATION theory; ENERGY consumption; RELIABILITY in engineering; SIMULATION methods &; models
- Publication
Adhoc & Sensor Wireless Networks, 2014, Vol 20, Issue 3/4, p153
- ISSN
1551-9899
- Publication type
Article