A Unified Framework for Scheduling Problems with and without Power Control in Multi-hop Wireless Networks [Report]

NESL Technical Report #: 2004-11-2


Abstract: Scheduling problems in multi-hop wireless networks have been traditionally modeled as graph coloring problems, for which a transmission is assumed to be successfully received if the intended receiver is sufficiently apart from the sources of other simultaneous transmissions. In this paper, we underscore the disadvantages of such graph-based scheduling algorithms, which abstract away the physical layer details. Furthermore, we analyze and investigate several classes of scheduling problems in multi-hop wireless networks, which consist of fixed power link scheduling, power controlled link scheduling, fixed power node scheduling, and power controlled node scheduling. The goal is to find a minimum length time frame to schedule all the nodes or links in a TDMA setting. We present a unified set-covering based framework for these problems to model the interactions between simultaneous transmissions involved in the network, based on the received signal-to-interference and noise ratio (SINR). We then introduce a generic polynomial heuristic for performing the scheduling. Through our numerical results we show that our algorithm leads to a significant increase in the throughput level in comparison with conventional graph-based scheduling algorithms. We show that our generic algorithm can lead to an order of magnitude increase in the throughput of fully connected topologies with sufficient number of nodes over conventional graph-based scheduling algorithms. We also show that our scheme outperforms related schemes proposed in prior work.

Page (Count): 35

Date: 2004-11-14

Public Document?: Yes

NESL Document?: Yes

Document category: Report