TY - GEN
T1 - Distributed Greedy approximation to Maximum Weighted Independent Set for scheduling with fading channels
AU - Joo, Changhee
AU - Lin, Xiaojun
AU - Ryu, Jiho
AU - Shroff, Ness B.
PY - 2013
Y1 - 2013
N2 - Developing scheduling mechanisms that can simultaneously achieve throughput optimality and good delay performance often require solving the Maximum Independent Weighted Set (MWIS) problem. However, under most realistic network settings, the MWIS problem can be shown to be NPhard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of the opportunistic gain, and may no longer guarantee good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size, and achieves provable performance guarantees (which is arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). Through simulations we verify that both the throughput and the delay under our proposed distributed scheduling scheme are close to that of the optimal solution to MWIS. Further, we implement a preliminary version of our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The preliminary experiment results show that our implementation successfully accounts for wireless fading, and attains the opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.
AB - Developing scheduling mechanisms that can simultaneously achieve throughput optimality and good delay performance often require solving the Maximum Independent Weighted Set (MWIS) problem. However, under most realistic network settings, the MWIS problem can be shown to be NPhard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of the opportunistic gain, and may no longer guarantee good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size, and achieves provable performance guarantees (which is arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). Through simulations we verify that both the throughput and the delay under our proposed distributed scheduling scheme are close to that of the optimal solution to MWIS. Further, we implement a preliminary version of our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The preliminary experiment results show that our implementation successfully accounts for wireless fading, and attains the opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.
KW - Distributed algorithm
KW - Maximum weighted independent set
KW - Wireless scheduling
UR - http://www.scopus.com/inward/record.url?scp=84883035120&partnerID=8YFLogxK
U2 - 10.1145/2491288.2491297
DO - 10.1145/2491288.2491297
M3 - Conference contribution
AN - SCOPUS:84883035120
SN - 9781450321938
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 89
EP - 97
BT - MobiHoc 2013 - Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing
T2 - 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2013
Y2 - 29 July 2013 through 1 August 2013
ER -