A Column Generation Method for Constructing and Scheduling Multiple Forwarding Trees in Wireless Sensor Networks

doi:10.1109/TWC.2016.2585490

2016-09-01

PRE

Dariush Ebrahimi *

Samir Sebbah

Chadi Assi

DOI：10.1109/TWC.2016.2585490

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Wireless sensor network

column generation

SINR

routing

link scheduling

energy

latency