Approximation algorithms for a link scheduling problem in wireless relay networks with QoS guarantee
Journal
IEEE Transactions on Mobile Computing
Journal Volume
9
Journal Issue
12
Pages
1732-1748
Date Issued
2010
Author(s)
Abstract
The emerging wireless relay networks (WRNs) are expected to provide significant improvement on throughput and extension of coverage area for next-generation wireless systems. We study an optimization problem for multihop link scheduling with bandwidth and delay guarantees over WRNs. Our optimization problem is investigated under a more general interference model with a generic objective. The objective can be based on various kinds of performance indexes (e.g., throughput, fairness, and capacity), which can be determined by service providers. Through our theoretical analysis, the intractability and inapproximability of the optimization problem are shown. Due to the intractable computational complexity, we present efficient algorithms to provide a reasonable small approximation factor against any optimal solution even for a worst-case input. Furthermore, some experimental results indicate that our algorithms yield near-optimal performance in the average case. ? 2006 IEEE.
Subjects
Approximation algorithms
link scheduling
quality of service
wireless relay networks
Type
journal article