Weitere Kapitel dieses Buchs durch Wischen aufrufen
In the interference scheduling problem, one is given a set of n communication requests each of which corresponds to a sender and a receiver in a multipoint radio network. Each request must be assigned a power level and a color such that signals in each color class can be transmitted simultaneously. The feasibility of simultaneous communication within a color class is defined in terms of the signal to interference plus noise ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the “physical model” and is the established way of modeling interference in the engineering community. The objective is to minimize the schedule length corresponding to the number of colors needed to schedule all requests. We study oblivious power assignments in which the power value of a request only depends on the path loss between the sender and the receiver, e.g., in a linear fashion. At first, we present a measure of interference giving lower bounds for the schedule length with respect to linear and other power assignments. Based on this measure, we devise distributed scheduling algorithms for the linear power assignment achieving the minimal schedule length up to small factors. In addition, we study a power assignment in which the signal strength is set to the square root of the path loss. We show that this power assignment leads to improved approximation guarantees in two kinds of problem instances defined by directed and bidirectional communication request. Finally, we study the limitations of oblivious power assignments by proving lower bounds for this class of algorithms.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
M. Andrews and M. Dinitz. Maximizing capacity in arbitrary wireless networks in the SINR model: Comple xity and game theory. In Proceedings of the 28th Conference of the IEEE Communications Society (INFOCOM), Rio de Janeiro, Brazil, 2009.
C. Avin, Z. Lotker, and Y. A. Pignolet. On the power of uniform power: Capacity of wireless networks with bounded resources. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), Copenhagen, Denmark, 2009.
D. Chafekar, V. S. Anil Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Cross-layer latency minimization in wireless networks with SINR con. In Proceedings of the 8th ACM International Symposium Mobile Ad-Hoc Networking and Computing (MOBIHOC), pages 110–119, Montreal, Quebec, Canada, 2007.
D. Chafekar, V. S. Anil Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Approximation algorithms for computing capacity of wireless networks with SINR constraints. In Proceedings of the 27th Conference of the IEEE Communications Society (INFOCOM), pages 1166–1174, Phoenix, AZ, USA, 2008.
A. Fanghänel, T. Kesselheim, H. Räcke, and B. Vöcking. Oblivious interference scheduling. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC), Calgary, Alberta, Canada, 2009.
O. Goussevskaia, M. M. Halldórsson, R. Wattenhofer, and E. Welzl. Capacity of arbitrary wireless networks. In Proceedings of the 28th Conference of the IEEE Communications Society (INFOCOM), Rio de Janeiro, Brazil, 2009.
O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer. Complexity in geometric SINR. In Proceedings of the 8th ACM International Symposium Mobile Ad-Hoc Networking and Computing (MOBIHOC), pages 100–109, Montreal, Quebec, Canada, 2007.
P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In W. M. McEneaney, G. Yin, and Q. Zhang, editors, Stochastic Analysis, Control, Optimization, and Applications: A Volume in Honor of W. H. Fleming, Systems & Control: Foundations & Applications, pages 547–566. Birkhäuser, 1998.
M. M. Halldórsson. Wireless scheduling with power control. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), Copenhagen, Denmark, 2009.
M. M. Halldórsson and R. Wattenhofer. Computing Wireless Capacity. In press.
V. S. Anil Kumar, M. V. Marathe, S. Thite, H. Balakrishnan, C. L. Barrett. The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications, 22(6):1069–1079, 2004. CrossRef
R. Hekmat and P. Van Mieghem. Interference in wireless multi-hop ad-hoc networks and its effect on network capacity. Wireless Networks, 10(4):389–399, 2004. CrossRef
T. Moscibroda and R. Wattenhofer. The complexity of connectivity in wireless networks. In Proceedings of the 25th Conference of the IEEE Communications Society (INFOCOM), pages 1–13, Barcelona, Catalunya, Spain, 2006.
T. Moscibroda, R. Wattenhofer, and A. Zollinger. Topology control meets SINR: The scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM International Symposium Mobile Ad-Hoc Networking and Computing (MOBIHOC), pages 310–321, Florence, Italy, 2006.
S. Ramanathan and E. L. Lloyd. Scheduling algorithms for multi-hop radio networks. ACM SIGCOMM Computer Communication Review, 22(4):211–222, 1992. CrossRef
S. Singh and C. S. Raghavendra. PAMAS—Power aware multi-access protocol with signalling for ad hoc networks. ACM SIGCOMM Computer Communication Review, 28(3):5–26, 1998. CrossRef
- Scheduling and Power Assignments in the Physical Model
- Springer Berlin Heidelberg
- Chapter 2
Neuer Inhalt/© Filograph | Getty Images | iStock