Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks

Abdulaziz, Shada LU ; Hedar, Abdel-Rahman ; Sewisy, Adel and El-Sayed, Gamal (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:
author
; ; and
organization
publishing date
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}},
}