On the Problem of Wireless Scheduling With Linear Power Levels
Abstract
In this work we consider the problem of communication scheduling in wireless networks with respect to the SINR (Signal to Interference plus Noise Ratio) constraint in metric spaces. For the powers of sender nodes we consider the linear power assignment, which is one of commonly considered power schemes. We give a constant factor deterministic approximation algorithm for scheduling in wireless networks, which are given in some special class of metric spaces, which contains the Euclidean spaces. To the best of our knowledge, this is the first constant factor approximation algorithm for this problem. Simultaneously we obtain the approximate value of the optimal schedule length with error at most a constant factor.
References
A. Fanghänel, T. Keβelheim, H. Räcke, B. Vöking, “Oblivious interference scheduling", Proc. 28th Symposium on Principles of Distributed Computing (PODC), 2009.
A. Fanghänel, T. Keβelheim and B. Vöking, “Improved Algorithms on Latency Minimization in Wireless Networks", Proc. 36th International Colloqium on Automata, Languages and Programming (ICALP), 2009.
O. Goussevskaia, M.M. Halldórsson, R. Wattenhofer and Emo Welzl. “Capacity of Arbitrary Wireless Networks", 28th Annual IEEE Conference on Computer Communications (INFOCOM), 2009.
M.M. Halldórsson, “Wireless Scheduling with Power Control" Proc. 17th annual European Symposium on Algorithms (ESA), 2009.
M.M. Halldórsson and R. Wattenhofer, “Wireless Communication is in APX",Proc. 36th International Colloqium on Automata, Languages and Programming (ICALP), 2009.
G.H. Hardy, J.E. Littlewood, G. Pólya, Inequalities, Cambridge University Press, 1934.
S.O. Krumke, M.V. Marathe and S.S. Ravi, “Models and approximation algorithms for channel assignment in radio networks", Wireless Networks 7, 2001.
T. Moscibroda, R. Wattenhofer, “The complexity of connectivity in wireless networks", 25th Annual IEEE Conference on Computer Communications (INFOCOM), 2006.
T. Moscibroda, R. Wattenhofer and Y. Weber. “Protocol Design Beyond Graph-Based Models", Hot Topics in Networks (HotNets), 2006.
T. Moscibroda, R. Wattenhofer and A. Zollinger, “Topology control meets SINR: The scheduling complexity of arbitrary topologies", ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2007.
V.S.A. Kumar, M.V. Marathe, S. Parthasarathy and A. Srinivasan, “Algorithmic Aspects of Capacity in Wireless Networks", ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2005.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
