Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks
(2020) In Algorithms 13(2).- Abstract
- An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating set (MCDS), where the searching space for finding a route is restricted to nodes in this MCDS. Thus, finding MCDS in a WSN provides a flexible low-cost solution for the problem of event monitoring, particularly in places with limited or dangerous access to humans as is the case for most WSN deployments. In this paper, we proposed an adaptive scatter search (ASS-MCDS) algorithm that finds the near-optimal solution to this problem. The proposed method invokes a composite fitness function that... (More)
- An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating set (MCDS), where the searching space for finding a route is restricted to nodes in this MCDS. Thus, finding MCDS in a WSN provides a flexible low-cost solution for the problem of event monitoring, particularly in places with limited or dangerous access to humans as is the case for most WSN deployments. In this paper, we proposed an adaptive scatter search (ASS-MCDS) algorithm that finds the near-optimal solution to this problem. The proposed method invokes a composite fitness function that aims to maximize the solution coverness and connectivity and minimize its cardinality. Moreover, the ASS-MCDS methods modified the scatter search framework through new local search and solution update procedures that maintain the search objectives. We tested the performance of our proposed algorithm using different benchmark-test-graph sets available in the literature. Experiments results show that our proposed algorithm gave good results in terms of solution quality. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1e2b0ddd-ebbb-4e65-92d0-05c56e2deb51
- author
- Abdulaziz, Shada LU ; Hedar, Abdel-Rahman ; Sewisy, Adel and El-Sayed, Gamal
- organization
- publishing date
- 2020-02-04
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- dominating sets, minimum connected dominating sets, scatter search, local search, wireless network design
- in
- Algorithms
- volume
- 13
- issue
- 2
- pages
- 15 pages
- publisher
- MDPI AG
- external identifiers
-
- scopus:85080119522
- ISSN
- 1999-4893
- DOI
- 10.3390/a13020035
- language
- English
- LU publication?
- yes
- id
- 1e2b0ddd-ebbb-4e65-92d0-05c56e2deb51
- date added to LUP
- 2020-02-14 11:58:24
- date last changed
- 2023-09-23 22:31:01
@article{1e2b0ddd-ebbb-4e65-92d0-05c56e2deb51, abstract = {{An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating set (MCDS), where the searching space for finding a route is restricted to nodes in this MCDS. Thus, finding MCDS in a WSN provides a flexible low-cost solution for the problem of event monitoring, particularly in places with limited or dangerous access to humans as is the case for most WSN deployments. In this paper, we proposed an adaptive scatter search (ASS-MCDS) algorithm that finds the near-optimal solution to this problem. The proposed method invokes a composite fitness function that aims to maximize the solution coverness and connectivity and minimize its cardinality. Moreover, the ASS-MCDS methods modified the scatter search framework through new local search and solution update procedures that maintain the search objectives. We tested the performance of our proposed algorithm using different benchmark-test-graph sets available in the literature. Experiments results show that our proposed algorithm gave good results in terms of solution quality.}}, author = {{Abdulaziz, Shada and Hedar, Abdel-Rahman and Sewisy, Adel and El-Sayed, Gamal}}, issn = {{1999-4893}}, keywords = {{dominating sets; minimum connected dominating sets; scatter search; local search; wireless network design}}, language = {{eng}}, month = {{02}}, number = {{2}}, publisher = {{MDPI AG}}, series = {{Algorithms}}, title = {{Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks}}, url = {{https://lup.lub.lu.se/search/files/76188810/algorithms_13_00035.pdf}}, doi = {{10.3390/a13020035}}, volume = {{13}}, year = {{2020}}, }