Variable neighborhood search variants for Min-power symmetric connectivity problem |
| |
| Affiliation: | 1. Singapore-MIT Alliance for Research and Technology (SMART), 1 Create Way, Singapore;2. Canada Excellence Research Chair in “Data Science for Real-time Decision-making”, Department of Mathematics and Industrial Engineering - École Polytechnique de Montréal, Pavillon André Aisenstadt, 2920 Chemin de la Tour, Montréal, Canada;1. Canada Excellence Research Chair in Data Science for Real-time Decision-making, École Polytechnique de Montréal, Canada;2. Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Canada;3. HEC Montréal and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Canada |
| |
| Abstract: | We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges. In this paper, the most general strongly NP-hard formulation, when edge weights have arbitrary non-negative values, is considered. We propose new heuristics, mostly based on variable neighborhood search, for getting an approximate solution of the problem. Extensive comparative analysis between the proposed methods was performed. Numerical experiments demonstrated the high efficiency of the proposed heuristics. |
| |
| Keywords: | Wireless sensor network Energy efficiency NP-hard problem Variable neighborhood search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
