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

Zhang, Xin-Yuan and Zhang, Jun and Gong, Yue-Jiao and Zhan, Zhi-Hui and Chen, Wei-Neng and Li, Yun (2016) Kuhn-Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks. IEEE Transactions on Evolutionary Computation, 20 (5). pp. 695-710. 7362161. ISSN 1089-778X

[thumbnail of Zhang-etal-IEEE-TEC-2015-Kuhn-Munkres-parallel-genetic-algorithm-for-the-set-cover-problem]
Preview
 Text (Zhang-etal-IEEE-TEC-2015-Kuhn-Munkres-parallel-genetic-algorithm-for-the-set-cover-problem)
Zhang_etal_IEEE_TEC_2015_Kuhn_Munkres_parallel_genetic_algorithm_for_the_set_cover_problem.pdf
Accepted Author Manuscript
Download (1MB)| Preview

    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.

    ORCID iDs

    Zhang, Xin-Yuan, Zhang, Jun ORCID logoORCID: https://orcid.org/0000-0002-3731-4594, Gong, Yue-Jiao, Zhan, Zhi-Hui, Chen, Wei-Neng and Li, Yun ORCID logoORCID: https://orcid.org/0000-0002-6575-1839;
    • Item type:Article
      ID code:65130
      Dates:
      Date
      Event
      31 October 2016
      Published
      22 December 2015
      Published Online
      19 December 2015
      Accepted
      Notes:© 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.
      Keywords:Kuhn-Munkres (KM) algorithm, large-scale wireless sensor networks (WSNs), parallel genetic algorithm (PGA), set cover problem, Electronic computers. Computer science, Engineering (General). Civil engineering (General), Software, Theoretical Computer Science, Computational Theory and Mathematics
      Subjects:Science > Mathematics > Electronic computers. Computer science
      Technology > Engineering (General). Civil engineering (General)
      Department:Faculty of Engineering
      Depositing user: Pure Administrator
      Date deposited:13 Aug 2018 09:06
      Last modified:11 Apr 2021 00:47
      Related URLs:
      URI:https://strathprints.strath.ac.uk/id/eprint/65130
    CORE (COnnecting REpositories)