A Column Generation Method for Constructing and Scheduling Multiple Forwarding Trees in Wireless Sensor Networks
Autor: | Dariush Ebrahimi, Chadi Assi, Samir Sebbah |
---|---|
Rok vydání: | 2016 |
Předmět: |
020203 distributed computing
Schedule Computer science business.industry Applied Mathematics Distributed computing 020206 networking & telecommunications 02 engineering and technology Dynamic priority scheduling Fair-share scheduling Computer Science Applications Scheduling (computing) Key distribution in wireless sensor networks 0202 electrical engineering electronic engineering information engineering Wireless Column generation Electrical and Electronic Engineering business Wireless sensor network Efficient energy use Computer network |
Zdroj: | IEEE Transactions on Wireless Communications. 15:6513-6523 |
ISSN: | 1536-1276 |
DOI: | 10.1109/twc.2016.2585490 |
Popis: | This paper considers the problem of jointly constructing and scheduling forwarding trees in a wireless sensor network, each to collect measurements from a group of sensor nodes at a single sink node. The goal is to construct such trees that gather measurements in the most energy efficient manner and with minimal gathering latency. We assume transmissions (carrying measurements) on wireless links interfere with one another, and thus, appropriate link scheduling is required to manage interference. We refer to this problem as forwarding tree construction and scheduling (FTCS). Each tree may be constructed independently, and then, its links are scheduled. However, when all trees are combined together, the shortest and energy efficient schedule may not be guaranteed. Furthermore, a large number of possible forwarding trees for each group of sensors may be considered. Both problems of enumerating forwarding trees and scheduling links for those trees are hard combinatorial problems. This is compounded by the fact that the two problems must be solved jointly, to guarantee the selection of the best forwarding trees that, when their links are scheduled, guarantee a shortest energy efficient schedule. After highlighting the complexity of the FTCS problem, we present a novel primal-dual decomposition method using column generation. We also highlight several challenges we faced when solving the decomposed problem and present efficient techniques for mitigating those challenges. One major advantage of this paper is that it can serve as a benchmark for evaluating the performance of any low complexity method for solving the FTCS problem for larger network instances, where no known exact solutions can be found. |
Databáze: | OpenAIRE |
Externí odkaz: |