A Polynomial-Time Approximation Algorithm for Weighted Sum-Rate Maximization in UWB Networks

Scheduling in an ad hoc wireless network suffers from the non-convexity of the cost function, caused by the interference between communication links. In previous optimization theoretic analysis, the weighted sum-rate maximization (WSRM) which inherits the non-convexity has been identified as a core problem of the hard scheduling problem. In this paper, we propose a polynomial-time approximation algorithm with guaranteed accuracy for WSRM under an Ultra- wide band (UWB) assumption. The algorithm is obtained by an appropriate adaptation of the ´shifting´ strategy (a well- known approximation technique for some geometric problems) for the wireless broadcast environment. The worst case accuracy and complexity of the algorithm are analyzed by utilizing the quadratic link rate function derived in previous research, under the assumption of a large bandwidth, as is typical in UWB networks. The average case performance of the algorithm is investigated by simulations on random ad hoc networks.