11574c37d3cf12fb0821d86d570c0e6e pmc_8914629.pdf a3909f95c0adb19f196eaa254baabe5123dcfd6b pmc_8914629.pdf e68c204fa4d2caaf76cd73fc0b47c0cea025c18c2dc475e8384b3b98fd6a11dd pmc_8914629.pdf Title: A Population-Based Iterated Greedy Algorithm for Maximizing Sensor Network Lifetime Subject: Finding dominating sets in graphs is very important in the context of numerous real-world applications, especially in the area of wireless sensor networks. This is because network lifetime in wireless sensor networks can be prolonged by assigning sensors to disjoint dominating node sets. The nodes of these sets are then used by a sleep–wake cycling mechanism in a sequential way; that is, at any moment in time, only the nodes from exactly one of these sets are switched on while the others are switched off. This paper presents a population-based iterated greedy algorithm for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Our approach is compared to the ILP solver, CPLEX, which is an existing local search technique, and to our earlier greedy algorithm. This is performed through its application to 640 random graphs from the literature and to 300 newly generated random geometric graphs. The results show that our algorithm significantly outperforms the competitors. Keywords: population-based iterated greedy; disjoint dominating sets; lifetime maximization; wireless sensor networks Author: Pedro Pinacho-Davidson, Christian Blum and Salim Bouamama Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Mon Feb 28 03:41:14 2022 CET ModDate: Mon Feb 28 04:24:18 2022 CET Custom Metadata: no Metadata Stream: no Tagged: no UserProperties: no Suspects: no Form: none JavaScript: no Pages: 20 Encrypted: no Page size: 595.276 x 841.89 pts (A4) Page rot: 0 File size: 518382 bytes Optimized: no PDF version: 1.7 name type encoding emb sub uni object ID ------------------------------------ ----------------- ---------------- --- --- --- --------- BAFDJH+URWPalladioL-Bold Type 1 Custom yes yes no 10 0 MQUIRU+URWPalladioL-Roma Type 1 Custom yes yes no 15 0 WLMXCC+URWPalladioL-Ital Type 1 Custom yes yes no 19 0 MCBCCI+SourceSansRoman-Regular Type 1C Custom yes yes no 27 0 MCBCCM+SourceSansRoman.613wght Type 1C Custom yes yes no 31 0 MCBCCO+SourceSansRoman-Bold Type 1C Custom yes yes no 35 0 RVSEMT+TimesNewRomanPS-BoldItalicMT Type 1C WinAnsi yes yes no 47 0 CWEGQA+PazoMath Type 1 Builtin yes yes no 69 0 SYFPBV+CMMI10 Type 1 Builtin yes yes no 73 0 SOSTRQ+CMR10 Type 1 Builtin yes yes no 77 0 PXGDSW+CMSY10 Type 1 Builtin yes yes no 81 0 TLIXIB+CMEX10 Type 1 Builtin yes yes no 85 0 ASEERR+PazoMath-Italic Type 1 Builtin yes yes no 92 0 QDTWCG+MSBM10 Type 1 Builtin yes yes no 99 0 BYPIPD+Helvetica Type 1C WinAnsi yes yes no 109 0 BYPIPD+Helvetica Type 1C WinAnsi yes yes no 115 0 BYPIPD+Helvetica Type 1C WinAnsi yes yes no 121 0 QJSRQA+SFSS1000 Type 1 Custom yes yes no 127 0 BFLQCD+MSAM10 Type 1 Builtin yes yes no 141 0 UNGHPN+SFSS0900 Type 1 Custom yes yes no 151 0 OMHGYV+PazoMath-BoldItalic Type 1 Builtin yes yes no 162 0 STLTWE+URWPalladioL-BoldItal Type 1 Custom yes yes no 166 0 HVLRJR+CMBX10 Type 1 Builtin yes yes no 170 0 UKXYFA+Helvetica Type 1C WinAnsi yes yes no 180 0 UKXYFA+Helvetica Type 1C WinAnsi yes yes no 186 0 UKXYFA+Helvetica Type 1C WinAnsi yes yes no 195 0 UKXYFA+Helvetica Type 1C WinAnsi yes yes no 201 0 IFNCUA+SFTT0900 Type 1 Custom yes yes no 210 0 HBLKEJ+NimbusSans-Regular Type 1C WinAnsi yes yes yes 220 0 SICTZL+NimbusSans-Regular Type 1C WinAnsi yes yes yes 228 0 Jhove (Rel. 1.28.0, 2023-05-18) Date: 2024-05-07 04:29:05 CEST RepresentationInformation: pmc_8914629.pdf ReportingModule: PDF-hul, Rel. 1.12.4 (2023-03-16) LastModified: 2022-03-28 07:26:18 CEST Size: 518382 Format: PDF Version: 1.7 Status: Well-Formed and valid SignatureMatches: PDF-hul MIMEtype: application/pdf PDFMetadata: Objects: 392 FreeObjects: 5 IncrementalUpdates: 0 DocumentCatalog: PageLayout: SinglePage PageMode: UseNone Outlines: Item: Title: Introduction Destination: section.1 Children: Item: Title: Necessary Graph Theoretic Concepts Destination: subsection.1.1 Item: Title: Graph Problems Used to Model WSN Lifetime Maximization Destination: subsection.1.2 Item: Title: Existing Work for the MWDDS Problem and Our Contribution Destination: subsection.1.3 Item: Title: Paper Organization Destination: subsection.1.4 Item: Title: The MWDDS Problem Destination: section.2 Children: Item: Title: Graphical Example Destination: subsection.2.1 Item: Title: ILP Model for the MWDDS Problem Destination: subsection.2.2 Item: Title: Proposed Algorithm Destination: section.3 Item: Title: Experimental Evaluation Destination: section.4 Children: Item: Title: Problem Instances Destination: subsection.4.1 Item: Title: Algorithm Tuning Destination: subsection.4.2 Item: Title: Results and Discussion Destination: subsection.4.3 Item: Title: Conclusions Destination: section.5 Item: Title: References Destination: section.5 Info: Title: A Population-Based Iterated Greedy Algorithm for Maximizing Sensor Network Lifetime Author: Pedro Pinacho-Davidson, Christian Blum and Salim Bouamama Subject: Finding dominating sets in graphs is very important in the context of numerous real-world applications, especially in the area of wireless sensor networks. This is because network lifetime in wireless sensor networks can be prolonged by assigning sensors to disjoint dominating node sets. The nodes of these sets are then used by a sleep wake cycling mechanism in a sequential way; that is, at any moment in time, only the nodes from exactly one of these sets are switched on while the others are switched off. This paper presents a population-based iterated greedy algorithm for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Our approach is compared to the ILP solver, CPLEX, which is an existing local search technique, and to our earlier greedy algorithm. This is performed through its application to 640 random graphs from the literature and to 300 newly generated random geometric graphs. The results show that our algorithm significantly outperforms the competitors. Keywords: population-based iterated greedy; disjoint dominating sets; lifetime maximization; wireless sensor networks Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Mon Feb 28 03:41:14 CET 2022 ModDate: Mon Feb 28 04:24:18 CET 2022 ID: 0xe72a01196aeda2e68b217b55d8eb4097, 0xe72a01196aeda2e68b217b55d8eb4097 Filters: FilterPipeline: FlateDecode Fonts: Type1: Font: BaseFont: OMHGYV+PazoMath-BoldItalic FontSubset: true FirstChar: 115 LastChar: 115 FontDescriptor: FontName: OMHGYV+PazoMath-BoldItalic Flags: Symbolic FontBBox: -64, -272, 868, 740 FontFile: true Font: BaseFont: QDTWCG+MSBM10 FontSubset: true FirstChar: 82 LastChar: 82 FontDescriptor: FontName: QDTWCG+MSBM10 Flags: Symbolic FontBBox: -55, -420, 2343, 920 FontFile: true Font: BaseFont: CWEGQA+PazoMath FontSubset: true FirstChar: 68 LastChar: 229 FontDescriptor: FontName: CWEGQA+PazoMath Flags: Symbolic FontBBox: -40, -283, 878, 946 FontFile: true Font: BaseFont: STLTWE+URWPalladioL-BoldItal FontSubset: true FirstChar: 84 LastChar: 114 FontDescriptor: FontName: STLTWE+URWPalladioL-BoldItal Flags: Symbolic FontBBox: -170, -300, 1073, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: SYFPBV+CMMI10 FontSubset: true FirstChar: 60 LastChar: 62 FontDescriptor: FontName: SYFPBV+CMMI10 Flags: Symbolic FontBBox: -32, -250, 1048, 750 FontFile: true Font: BaseFont: BAFDJH+URWPalladioL-Bold FontSubset: true FirstChar: 3 LastChar: 122 FontDescriptor: FontName: BAFDJH+URWPalladioL-Bold Flags: Symbolic FontBBox: -152, -301, 1000, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: HVLRJR+CMBX10 FontSubset: true FirstChar: 43 LastChar: 61 FontDescriptor: FontName: HVLRJR+CMBX10 Flags: Symbolic FontBBox: -56, -250, 1164, 750 FontFile: true Font: BaseFont: SOSTRQ+CMR10 FontSubset: true FirstChar: 40 LastChar: 93 FontDescriptor: FontName: SOSTRQ+CMR10 Flags: Symbolic FontBBox: -40, -250, 1009, 750 FontFile: true Font: BaseFont: BFLQCD+MSAM10 FontSubset: true FirstChar: 73 LastChar: 73 FontDescriptor: FontName: BFLQCD+MSAM10 Flags: Symbolic FontBBox: 8, -463, 1331, 1003 FontFile: true Font: BaseFont: MQUIRU+URWPalladioL-Roma FontSubset: true FirstChar: 2 LastChar: 252 FontDescriptor: FontName: MQUIRU+URWPalladioL-Roma Flags: Symbolic FontBBox: -166, -283, 1021, 943 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: PXGDSW+CMSY10 FontSubset: true FirstChar: 0 LastChar: 110 FontDescriptor: FontName: PXGDSW+CMSY10 Flags: Symbolic FontBBox: -29, -960, 1116, 775 FontFile: true Font: BaseFont: IFNCUA+SFTT0900 FontSubset: true FirstChar: 35 LastChar: 119 FontDescriptor: FontName: IFNCUA+SFTT0900 Flags: Symbolic FontBBox: -210, -359, 1376, 844 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: WLMXCC+URWPalladioL-Ital FontSubset: true FirstChar: 8 LastChar: 180 FontDescriptor: FontName: WLMXCC+URWPalladioL-Ital Flags: Symbolic FontBBox: -170, -305, 1010, 941 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: TLIXIB+CMEX10 FontSubset: true FirstChar: 83 LastChar: 83 FontDescriptor: FontName: TLIXIB+CMEX10 Flags: Symbolic FontBBox: -24, -2960, 1454, 772 FontFile: true Font: BaseFont: UNGHPN+SFSS0900 FontSubset: true FirstChar: 97 LastChar: 114 FontDescriptor: FontName: UNGHPN+SFSS0900 Flags: Symbolic FontBBox: -209, -321, 1528, 907 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: ASEERR+PazoMath-Italic FontSubset: true FirstChar: 100 LastChar: 115 FontDescriptor: FontName: ASEERR+PazoMath-Italic Flags: Symbolic FontBBox: -70, -277, 902, 733 FontFile: true Font: BaseFont: QJSRQA+SFSS1000 FontSubset: true FirstChar: 49 LastChar: 121 FontDescriptor: FontName: QJSRQA+SFSS1000 Flags: Symbolic FontBBox: -201, -321, 1483, 901 FontFile: true EncodingDictionary: Differences: true Pages: Page: Sequence: 1 Annotations: Annotation: Subtype: Link Rect: 54, 323, 152, 332 Annotation: Subtype: Link Rect: 34, 313, 67, 320 Annotation: Subtype: Link Rect: 34, 164, 96, 186 Annotation: Subtype: Link Rect: 126, 90, 154, 99 Annotation: Subtype: Link Rect: 34, 78, 147, 87 Annotation: Subtype: Link Rect: 34, 756, 153, 792 Annotation: Subtype: Link Rect: 515, 756, 560, 792 Annotation: Subtype: Link Rect: 121, 663, 132, 676 Annotation: Subtype: Link Rect: 218, 663, 229, 676 Annotation: Subtype: Link Rect: 369, 663, 380, 676 Annotation: Subtype: Link Rect: 218, 272, 225, 281 ActionDest: 234 Annotation: Subtype: Link Rect: 226, 272, 233, 281 ActionDest: 234 Annotation: Subtype: Link Rect: 237, 184, 244, 193 ActionDest: 234 Annotation: Subtype: Link Rect: 113, 17, 241, 28 Annotation: Subtype: Link Rect: 410, 17, 560, 28 Annotation: Subtype: Link Rect: 34, 396, 86, 415 Page: Sequence: 2 Annotations: Annotation: Subtype: Link Rect: 221, 736, 228, 744 ActionDest: 234 Annotation: Subtype: Link Rect: 366, 735, 373, 744 ActionDest: 234 Annotation: Subtype: Link Rect: 505, 735, 512, 744 ActionDest: 234 Annotation: Subtype: Link Rect: 250, 723, 257, 732 ActionDest: 234 Annotation: Subtype: Link Rect: 250, 710, 257, 719 ActionDest: 237 Annotation: Subtype: Link Rect: 266, 428, 273, 437 ActionDest: 237 Annotation: Subtype: Link Rect: 276, 428, 288, 437 ActionDest: 237 Annotation: Subtype: Link Rect: 301, 340, 313, 349 ActionDest: 237 Page: Sequence: 3 Annotations: Annotation: Subtype: Link Rect: 179, 597, 191, 606 ActionDest: 237 Annotation: Subtype: Link Rect: 394, 497, 406, 506 ActionDest: 237 Annotation: Subtype: Link Rect: 529, 497, 540, 506 ActionDest: 237 Annotation: Subtype: Link Rect: 543, 497, 555, 506 ActionDest: 237 Annotation: Subtype: Link Rect: 284, 484, 296, 493 ActionDest: 237 Annotation: Subtype: Link Rect: 444, 484, 456, 493 ActionDest: 237 Annotation: Subtype: Link Rect: 278, 421, 290, 430 ActionDest: 237 Annotation: Subtype: Link Rect: 293, 421, 305, 430 ActionDest: 237 Annotation: Subtype: Link Rect: 510, 421, 522, 430 ActionDest: 237 Annotation: Subtype: Link Rect: 192, 409, 204, 418 ActionDest: 237 Annotation: Subtype: Link Rect: 549, 384, 556, 393 ActionDest: 237 Annotation: Subtype: Link Rect: 493, 346, 505, 355 ActionDest: 237 Annotation: Subtype: Link Rect: 406, 308, 417, 317 ActionDest: 237 Annotation: Subtype: Link Rect: 406, 233, 418, 242 ActionDest: 237 Annotation: Subtype: Link Rect: 179, 183, 191, 192 ActionDest: 237 Annotation: Subtype: Link Rect: 287, 120, 299, 129 ActionDest: 237 Page: Sequence: 4 Annotations: Annotation: Subtype: Link Rect: 506, 736, 518, 744 ActionDest: 237 Annotation: Subtype: Link Rect: 532, 723, 544, 732 ActionDest: 237 Annotation: Subtype: Link Rect: 179, 647, 191, 657 ActionDest: 237 Annotation: Subtype: Link Rect: 351, 622, 363, 631 ActionDest: 237 Annotation: Subtype: Link Rect: 474, 597, 486, 606 ActionDest: 237 Annotation: Subtype: Link Rect: 486, 597, 498, 606 ActionDest: 237 Annotation: Subtype: Link Rect: 352, 585, 364, 594 ActionDest: 237 Annotation: Subtype: Link Rect: 462, 456, 469, 468 ActionDest: 96 Annotation: Subtype: Link Rect: 490, 444, 497, 456 ActionDest: 124 Annotation: Subtype: Link Rect: 322, 419, 329, 431 ActionDest: 145 Annotation: Subtype: Link Rect: 433, 406, 440, 418 ActionDest: 214 Annotation: Subtype: Link Rect: 217, 183, 224, 195 ActionDest: 103 Annotation: Subtype: Link Rect: 548, 183, 555, 195 ActionDest: 103 Annotation: Subtype: Link Rect: 196, 133, 203, 146 ActionDest: 103 Annotation: Subtype: Link Rect: 470, 58, 477, 70 ActionDest: 103 Page: Sequence: 5 Annotations: Annotation: Subtype: Link Rect: 232, 442, 244, 452 ActionDest: 237 Annotation: Subtype: Link Rect: 551, 70, 558, 81 ActionDest: 103 Page: Sequence: 6 Annotations: Annotation: Subtype: Link Rect: 371, 733, 378, 745 ActionDest: 103 Annotation: Subtype: Link Rect: 367, 708, 374, 720 ActionDest: 103 Annotation: Subtype: Link Rect: 343, 695, 350, 707 ActionDest: 103 Annotation: Subtype: Link Rect: 374, 658, 381, 669 ActionDest: 103 Annotation: Subtype: Link Rect: 481, 645, 488, 657 ActionDest: 103 Annotation: Subtype: Link Rect: 269, 632, 276, 644 ActionDest: 103 Annotation: Subtype: Link Rect: 301, 632, 308, 644 ActionDest: 103 Annotation: Subtype: Link Rect: 447, 547, 459, 556 ActionDest: 237 Annotation: Subtype: Link Rect: 488, 469, 496, 481 ActionDest: 124 Annotation: Subtype: Link Rect: 398, 184, 405, 198 ActionDest: 138 Page: Sequence: 7 Annotations: Annotation: Subtype: Link Rect: 500, 720, 507, 733 ActionDest: 124 Annotation: Subtype: Link Rect: 519, 683, 526, 695 ActionDest: 124 Annotation: Subtype: Link Rect: 452, 657, 459, 670 ActionDest: 124 Annotation: Subtype: Link Rect: 179, 384, 191, 393 ActionDest: 237 Page: Sequence: 8 Annotations: Annotation: Subtype: Link Rect: 550, 352, 557, 364 ActionDest: 138 Page: Sequence: 9 Page: Sequence: 10 Annotations: Annotation: Subtype: Link Rect: 274, 670, 288, 682 ActionDest: 148 Annotation: Subtype: Link Rect: 345, 384, 357, 393 ActionDest: 237 Annotation: Subtype: Link Rect: 218, 371, 230, 380 ActionDest: 237 Annotation: Subtype: Link Rect: 435, 321, 447, 330 ActionDest: 237 Annotation: Subtype: Link Rect: 249, 220, 261, 229 ActionDest: 237 Page: Sequence: 11 Annotations: Annotation: Subtype: Link Rect: 327, 683, 560, 695 Annotation: Subtype: Link Rect: 165, 670, 233, 682 Annotation: Subtype: Link Rect: 192, 515, 204, 524 ActionDest: 237 Annotation: Subtype: Link Rect: 527, 361, 534, 373 ActionDest: 148 Annotation: Subtype: Link Rect: 391, 177, 398, 189 ActionDest: 159 Page: Sequence: 12 Annotations: Annotation: Subtype: Link Rect: 320, 620, 327, 632 ActionDest: 159 Annotation: Subtype: Link Rect: 298, 607, 310, 616 ActionDest: 237 Annotation: Subtype: Link Rect: 423, 389, 429, 400 ActionDest: 204 Annotation: Subtype: Link Rect: 203, 375, 210, 387 ActionDest: 159 Annotation: Subtype: Link Rect: 488, 102, 495, 115 ActionDest: 174 Annotation: Subtype: Link Rect: 275, 89, 282, 101 ActionDest: 189 Page: Sequence: 13 Annotations: Annotation: Subtype: Link Rect: 530, 733, 537, 745 ActionDest: 207 Annotation: Subtype: Link Rect: 281, 708, 288, 720 ActionDest: 174 Annotation: Subtype: Link Rect: 308, 708, 315, 720 ActionDest: 189 Page: Sequence: 14 Page: Sequence: 15 Page: Sequence: 16 Annotations: Annotation: Subtype: Link Rect: 198, 632, 205, 644 ActionDest: 189 Annotation: Subtype: Link Rect: 209, 207, 216, 219 ActionDest: 214 Annotation: Subtype: Link Rect: 231, 157, 238, 169 ActionDest: 214 Annotation: Subtype: Link Rect: 345, 119, 352, 131 ActionDest: 214 Annotation: Subtype: Link Rect: 543, 119, 550, 131 ActionDest: 214 Page: Sequence: 17 Annotations: Annotation: Subtype: Link Rect: 457, 733, 464, 748 ActionDest: 174 Annotation: Subtype: Link Rect: 482, 733, 488, 748 ActionDest: 189 Annotation: Subtype: Link Rect: 410, 710, 416, 723 ActionDest: 174 Annotation: Subtype: Link Rect: 204, 694, 210, 707 ActionDest: 174 Annotation: Subtype: Link Rect: 375, 542, 381, 555 ActionDest: 174 Annotation: Subtype: Link Rect: 204, 526, 210, 539 ActionDest: 174 Annotation: Subtype: Link Rect: 396, 373, 402, 386 ActionDest: 189 Annotation: Subtype: Link Rect: 204, 357, 210, 370 ActionDest: 189 Annotation: Subtype: Link Rect: 375, 216, 381, 229 ActionDest: 189 Annotation: Subtype: Link Rect: 204, 200, 210, 213 ActionDest: 189 Page: Sequence: 18 Page: Sequence: 19 Annotations: Annotation: Subtype: Link Rect: 255, 585, 267, 594 ActionDest: 237 Annotation: Subtype: Link Rect: 536, 416, 560, 427 Annotation: Subtype: Link Rect: 165, 404, 413, 415 Annotation: Subtype: Link Rect: 281, 213, 319, 223 Annotation: Subtype: Link Rect: 130, 190, 168, 200 Annotation: Subtype: Link Rect: 379, 166, 417, 177 Annotation: Subtype: Link Rect: 278, 143, 315, 154 Annotation: Subtype: Link Rect: 380, 120, 417, 131 Annotation: Subtype: Link Rect: 224, 97, 262, 108 Page: Sequence: 20 Annotations: Annotation: Subtype: Link Rect: 259, 629, 297, 640 Annotation: Subtype: Link Rect: 187, 561, 225, 571 Annotation: Subtype: Link Rect: 196, 537, 234, 548 Annotation: Subtype: Link Rect: 149, 515, 186, 525 Annotation: Subtype: Link Rect: 193, 515, 229, 525 Annotation: Subtype: Link Rect: 131, 492, 168, 502 Annotation: Subtype: Link Rect: 369, 468, 407, 479 Annotation: Subtype: Link Rect: 205, 445, 242, 456 Annotation: Subtype: Link Rect: 208, 423, 245, 433 Annotation: Subtype: Link Rect: 198, 399, 235, 410 Annotation: Subtype: Link Rect: 265, 353, 303, 364 Annotation: Subtype: Link Rect: 59, 331, 96, 341 Annotation: Subtype: Link Rect: 122, 262, 160, 272 Annotation: Subtype: Link Rect: 302, 238, 339, 249 Annotation: Subtype: Link Rect: 253, 215, 291, 226 Annotation: Subtype: Link Rect: 185, 158, 222, 169 Annotation: Subtype: Link Rect: 95, 136, 133, 146 Checksum: 21da72f2 Type: CRC32 Checksum: 11574c37d3cf12fb0821d86d570c0e6e Type: MD5 Checksum: a3909f95c0adb19f196eaa254baabe5123dcfd6b Type: SHA-1 Checksum: e68c204fa4d2caaf76cd73fc0b47c0cea025c18c2dc475e8384b3b98fd6a11dd Type: SHA-256