Magnús M. Halldórsson
Abstract
We consider the scheduling of arbitrary wireless links in the physical model of interference to minimize the time for satisfying all requests. We study here the combined problem of scheduling and power control, where we seek both an assignment of power settings and a partition of the links so that each set satisfies the signal-to-interference-plus-noise (SINR) constraints.
We give an algorithm that attains an approximation ratio of O(log n ċ log log Δ), where n is the number of links and Δ is the ratio between the longest and the shortest link length. Under the natural assumption that lengths are represented in binary, this gives the first approximation ratio that is polylogarithmic in the size of the input. The algorithm has the desirable property of using an oblivious power assignment, where the power assigned to a sender depends only on the length of the link. We give evidence that this dependence on Δ is unavoidable, showing that any reasonably behaving oblivious power assignment results in a Ω(log log Δ)-approximation.
These results hold also for the (weighted) capacity problem of finding a maximum (weighted) subset of links that can be scheduled in a single time slot. In addition, we obtain improved approximation for a bidirectional variant of the scheduling problem, give partial answers to questions about the utility of graphs for modeling physical interference, and generalize the setting from the standard 2-dimensional Euclidean plane to doubling metrics. Finally, we explore the utility of graph models in capturing wireless interference.
- Akcoglu, K., Aspnes, J., DasGupta, B., and Kao, M.-Y. 2002. Opportunity-cost algorithms for combinatorial auctions. In Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, E. J. Kontoghiorghes, B. Rustem, and S. Siokos, Eds., Kluwer Academic Publishers, 455--479.Google Scholar
- Andrews, M. and Dinitz, M. 2009. Maximizing capacity in arbitrary wireless networks in the sinr model: Complexity and game theory. In Proceedings of the 28th Annual IEEE Conference on Computer Communications (INFOCOM).Google Scholar
- Assouad, P. 1983. Plongements lipschitziens dans Rn. Soc. Math. France 111, 4, 429--448.Google ScholarCross Ref
- Auletta, V., Moscardelli, L., Penna, P., and Persiano, G. 2008. Interference games in wireless networks. In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE). Lecture Notes in Computer Science Series, vol. 5385, 278--285. Google ScholarDigital Library
- Avin, C., Emek, Y., Kantor, E., Lotker, Z., Peleg, D., and Roditty, L. 2008. SNR diagrams: Towards algorithmically usable SINR models of wireless networks. In Proceedings of the 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC). Google ScholarDigital Library
- Avin, C., Lotker, Z., and Pignolet, Y. A. 2009. On the power of uniform power: Capacity of wireless networks with bounded resources. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA).Google Scholar
- Brar, G. S., Blough, D. M., and Santi, P. 2008. The SCREAM approach for efficient distributed scheduling with physical interference in wireless mesh networks. In Proceedings of the 28th IEEE International Conference on Distributed Computing Systems (ICDCS 2008). 214--224. Google ScholarDigital Library
- Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., and Srinivasan, A. 2007. Cross-layer latency minimization for wireless networks using SINR constraints. In Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). Google ScholarDigital Library
- Clarkson, K. 2005. Nearest-neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, MIT Press.Google Scholar
- Couture, M., Barbeau, M., Bose, P., Carmi, P., and Kranakis, E. 2007. Location oblivious distributed unit disk graph coloring. In Proceedings of the 14th International Conference on Structural Information and Communication Complexity (SIROCCO). Springer-Verlag, 222--233. Google ScholarDigital Library
- ElBatt, T. A. and Ephremides, A. 2004. Joint scheduling and power control for wireless ad hoc networks. IEEE Trans. Wirel. Commun. 3, 1, 74--85. Google ScholarDigital Library
- Erlebach, T. and Grant, T. 2010. Scheduling multicast requests in the sinr model. In Proceedings of the 6th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS).Google Scholar
- Fanghänel, A., Geulen, S., Hoefer, M., and Vöcking, B. 2010. Online capacity maximization in wireless networks. In Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 92--99. Google ScholarDigital Library
- Fanghänel, A., Kesselheim, T., Räcke, H., and Vöcking, B. 2009a. Oblivious interference scheduling. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC). Google ScholarDigital Library
- Fanghänel, A., Kesselheim, T., and Vöcking, B. 2009b. Improved algorithms for latency minimization in wireless networks. In Proceedings of the 37th International Conference on Algorithms, Languages and Programming (ICALP). Google ScholarDigital Library
- Fejes Tóth, G. 1972. Lagerungen in der Ebene, auf der Kugel und in Raum 2nd Ed. Springer-Verlag, Berlin.Google Scholar
- Gao, Y., Hou, J. C., and Nguyen, H. 2008. Topology control for maintaining network connectivity and maximizing network capacity under the physical model. In Proceedings of the 27th Annual IEEE Conference on Computer Communications (INFOCOM).Google Scholar
- Goussevskaia, O., Halldórsson, M. M., Wattenhofer, R., and Welzl, E. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th Annual IEEE Conference on Computer Communications (INFOCOM).Google Scholar
- Goussevskaia, O., Moscibroda, T., and Wattenhofer, R. 2008. Local broadcasting in the physical interference model. In Proceedings of the 5th ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing. Google ScholarDigital Library
- Goussevskaia, O., Oswald, Y. A., and Wattenhofer, R. 2007. Complexity in geometric SINR. In Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 100--109. Google ScholarDigital Library
- Grönkvist, J. and Hansson, A. 2001. Comparison between graph-based and interference-based STDMA scheduling. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 255--258. Google ScholarDigital Library
- Gupta, P. and Kumar, P. R. 2000. The capacity of wireless networks. IEEE Trans. Inf. Theory 46, 2, 388--404. Google ScholarDigital Library
- Halldórsson, M. M. 2009. Wireless scheduling with power control. In Proceedings of the 17th European Symposium on Algorithms (ESA).Google ScholarCross Ref
- Halldórsson, M. M. and Mitra, P. 2011. Wireless capacity with oblivious power in general metrics. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Halldórsson, M. M. and Wattenhofer, R. 2009. Wireless communication is in APX. In Proceedings of the 37th International Conference on Algorithms, Languages and Programming (ICALP). Google ScholarDigital Library
- Heinonen, J. 1999. Lectures on Analysis in Metric Spaces. Springer.Google Scholar
- Katz, B., Völker, M., and Wagner, D. 2008. Link scheduling in local interference models. In Proceedings of the 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS). 57--71. Google ScholarDigital Library
- Kesselheim, T. 2011. A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Lipton, R. J., and Tomkins, A. 1994. Online interval scheduling. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 302--311. Google ScholarDigital Library
- Maheshwari, R., Jain, S., and Das, S. R. 2008. A measurement study of interference modeling and scheduling in low-power wireless networks. In Proceedings of the 6th International Conference on Embedded Networked Sensor Systems (SenSys). 141--154. Google ScholarDigital Library
- Moscibroda, T. 2007. The worst-case capacity of wireless sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN). 1--10. Google ScholarDigital Library
- Moscibroda, T., Oswald, Y. A., and Wattenhofer, R. 2007. How optimal are wireless scheduling protocols? In Proceedings of the 26th Annual IEEE Conference on Computer Communications (INFOCOM). 1433--1441.Google Scholar
- Moscibroda, T. and Wattenhofer, R. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th Annual IEEE Conference on Computer Communications (INFOCOM).Google Scholar
- Moscibroda, T. and Wattenhofer, R. 2008. Coloring unstructured radio networks. Distrib. Comput. 21, 271--284.Google ScholarDigital Library
- Moscibroda, T., Wattenhofer, R., and Weber, Y. 2006a. Protocol design beyond graph-based models. In Proceedings of the 5th Workshop on Hot Topics in Networks (HotNets).Google Scholar
- Moscibroda, T., Wattenhofer, R., and Zollinger, A. 2006b. Topology Control meets SINR: The scheduling complexity of arbitrary topologies. In Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). Google ScholarDigital Library
- Scheideler, C., Richa, A. W., and Santi, P. 2008. An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 91--100. Google ScholarDigital Library
- Tonoyan, T. 2011. Algorithms for scheduling with power control in wireless networks. In Proceedings of the TAPAS, A. Marchetti-Spaccamela and M. Segal, Eds., Lecture Notes in Computer Science Series, vol. 6595, Springer, 252--263. Google ScholarDigital Library
- Weisstein, E. W. Circle packing. From MathWorld--A Wolfram Web Resource. http://mathworld. wolfram.com/CirclePacking.html.Google Scholar
- Ye, Y. and Borodin, A. 2009. Elimination graphs. In Proceedings of the 37th International Conference on Algorithms, Languages and Programming (ICALP). 774--785. Google ScholarDigital Library
Index Terms
- Wireless scheduling with power control
Recommendations
On the complexity of scheduling in wireless networks
MobiCom '06: Proceedings of the 12th annual international conference on Mobile computing and networkingWe consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links ...
Stability and delay of finite-user slotted ALOHA with multipacket reception
The effect of multipacket reception (MPR) on stability and delay of slotted ALOHA based random-access systems is considered. A general asymmetric MPR model is introduced and the medium-access control (MAC) capacity region is specified. An explicit ...
Practical scheduling schemes with throughput guarantees for multi-hop wireless networks
In wireless communication systems, the interference between links results in a challenging scheduling problem. A K-hop interference model is defined as one for which no two links within K-hops can successfully transmit at the same time (note that IEEE ...
Comments