Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks

Xin-Yuan Zhang, Jun Zhang, Yue-Jiao Gong, Zhi-Hui Zhan, Wei-Neng Chen, Yun Li

Research output: Contribution to journalArticle

33 Citations (Scopus)

Abstract

Operating mode scheduling is crucial for the lifetime of wireless sensor networks (WSNs). However, the growing scale of networks has made such a scheduling problem more challenging, as existing set cover and evolutionary algorithms become unable to provide satisfactory efficiency due to the curse of dimensionality. In this paper, a Kuhn-Munkres (KM) parallel genetic algorithm is developed to solve the set cover problem and is applied to the lifetime maximization of large-scale WSNs. The proposed algorithm schedules the sensors into a number of disjoint complete cover sets and activates them in batch for energy conservation. It uses a divide-and-conquer strategy of dimensionality reduction, and the polynomial KM algorithm a are hence adopted to splice the feasible solutions obtained in each subarea to enhance the search efficiency substantially. To further improve global efficiency, a redundant-trend sensor schedule strategy was developed. Additionally, we meliorate the evaluation function through penalizing incomplete cover sets, which speeds up convergence. Eight types of experiments are conducted on a distributed platform to test and inform the effectiveness of the proposed algorithm. The results show that it offers promising performance in terms of the convergence rate, solution quality, and success rate.

LanguageEnglish
Article number7362161
Pages695-710
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume20
Issue number5
Early online date22 Dec 2015
DOIs
Publication statusPublished - 31 Oct 2016

Fingerprint

Parallel Genetic Algorithm
Set Cover
Parallel algorithms
Wireless Sensor Networks
Wireless sensor networks
Genetic algorithms
Scheduling
Lifetime
Schedule
Function evaluation
Sensors
Evolutionary algorithms
Sensor
Curse of Dimensionality
Divide and conquer
Energy conservation
Energy Conservation
Dimensionality Reduction
Evaluation Function
Polynomials

Keywords

  • Kuhn-Munkres (KM) algorithm
  • large-scale wireless sensor networks (WSNs)
  • parallel genetic algorithm (PGA)
  • set cover problem

Cite this

Zhang, Xin-Yuan ; Zhang, Jun ; Gong, Yue-Jiao ; Zhan, Zhi-Hui ; Chen, Wei-Neng ; Li, Yun. / Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks. In: IEEE Transactions on Evolutionary Computation. 2016 ; Vol. 20, No. 5. pp. 695-710.
@article{ca208454c4a54612a6c2236b2153af06,
title = "Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks",
abstract = "Operating mode scheduling is crucial for the lifetime of wireless sensor networks (WSNs). However, the growing scale of networks has made such a scheduling problem more challenging, as existing set cover and evolutionary algorithms become unable to provide satisfactory efficiency due to the curse of dimensionality. In this paper, a Kuhn-Munkres (KM) parallel genetic algorithm is developed to solve the set cover problem and is applied to the lifetime maximization of large-scale WSNs. The proposed algorithm schedules the sensors into a number of disjoint complete cover sets and activates them in batch for energy conservation. It uses a divide-and-conquer strategy of dimensionality reduction, and the polynomial KM algorithm a are hence adopted to splice the feasible solutions obtained in each subarea to enhance the search efficiency substantially. To further improve global efficiency, a redundant-trend sensor schedule strategy was developed. Additionally, we meliorate the evaluation function through penalizing incomplete cover sets, which speeds up convergence. Eight types of experiments are conducted on a distributed platform to test and inform the effectiveness of the proposed algorithm. The results show that it offers promising performance in terms of the convergence rate, solution quality, and success rate.",
keywords = "Kuhn-Munkres (KM) algorithm, large-scale wireless sensor networks (WSNs), parallel genetic algorithm (PGA), set cover problem",
author = "Xin-Yuan Zhang and Jun Zhang and Yue-Jiao Gong and Zhi-Hui Zhan and Wei-Neng Chen and Yun Li",
note = "{\circledC} 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2016",
month = "10",
day = "31",
doi = "10.1109/TEVC.2015.2511142",
language = "English",
volume = "20",
pages = "695--710",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
number = "5",

}

Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks. / Zhang, Xin-Yuan; Zhang, Jun; Gong, Yue-Jiao; Zhan, Zhi-Hui; Chen, Wei-Neng; Li, Yun.

In: IEEE Transactions on Evolutionary Computation, Vol. 20, No. 5, 7362161, 31.10.2016, p. 695-710.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks

AU - Zhang, Xin-Yuan

AU - Zhang, Jun

AU - Gong, Yue-Jiao

AU - Zhan, Zhi-Hui

AU - Chen, Wei-Neng

AU - Li, Yun

N1 - © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2016/10/31

Y1 - 2016/10/31

N2 - Operating mode scheduling is crucial for the lifetime of wireless sensor networks (WSNs). However, the growing scale of networks has made such a scheduling problem more challenging, as existing set cover and evolutionary algorithms become unable to provide satisfactory efficiency due to the curse of dimensionality. In this paper, a Kuhn-Munkres (KM) parallel genetic algorithm is developed to solve the set cover problem and is applied to the lifetime maximization of large-scale WSNs. The proposed algorithm schedules the sensors into a number of disjoint complete cover sets and activates them in batch for energy conservation. It uses a divide-and-conquer strategy of dimensionality reduction, and the polynomial KM algorithm a are hence adopted to splice the feasible solutions obtained in each subarea to enhance the search efficiency substantially. To further improve global efficiency, a redundant-trend sensor schedule strategy was developed. Additionally, we meliorate the evaluation function through penalizing incomplete cover sets, which speeds up convergence. Eight types of experiments are conducted on a distributed platform to test and inform the effectiveness of the proposed algorithm. The results show that it offers promising performance in terms of the convergence rate, solution quality, and success rate.

AB - Operating mode scheduling is crucial for the lifetime of wireless sensor networks (WSNs). However, the growing scale of networks has made such a scheduling problem more challenging, as existing set cover and evolutionary algorithms become unable to provide satisfactory efficiency due to the curse of dimensionality. In this paper, a Kuhn-Munkres (KM) parallel genetic algorithm is developed to solve the set cover problem and is applied to the lifetime maximization of large-scale WSNs. The proposed algorithm schedules the sensors into a number of disjoint complete cover sets and activates them in batch for energy conservation. It uses a divide-and-conquer strategy of dimensionality reduction, and the polynomial KM algorithm a are hence adopted to splice the feasible solutions obtained in each subarea to enhance the search efficiency substantially. To further improve global efficiency, a redundant-trend sensor schedule strategy was developed. Additionally, we meliorate the evaluation function through penalizing incomplete cover sets, which speeds up convergence. Eight types of experiments are conducted on a distributed platform to test and inform the effectiveness of the proposed algorithm. The results show that it offers promising performance in terms of the convergence rate, solution quality, and success rate.

KW - Kuhn-Munkres (KM) algorithm

KW - large-scale wireless sensor networks (WSNs)

KW - parallel genetic algorithm (PGA)

KW - set cover problem

UR - http://www.scopus.com/inward/record.url?scp=84995518904&partnerID=8YFLogxK

UR - https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=4235

UR - http://eprints.gla.ac.uk/118977/

U2 - 10.1109/TEVC.2015.2511142

DO - 10.1109/TEVC.2015.2511142

M3 - Article

VL - 20

SP - 695

EP - 710

JO - IEEE Transactions on Evolutionary Computation

T2 - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 5

M1 - 7362161

ER -