Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size.
Kesselheim obtained a @math -approximation algorithm for the capacity problem with power control for doubling metrics @cite_22 . Around the same time, the first constant factor algorithm for all sub-linear, length monotone power assignments was achieved on general metrics @cite_6 . Other recent studies in the SINR model include work on topological maps @cite_14 , distributed algorithms for scheduling @cite_24 , distributed power control @cite_9 and auction based spectrum allocation @cite_3 .
@cite_14 @cite_22 @cite_9 @cite_6 @cite_3 @cite_24
2952813714 1584433497 2136756148 2950068681
In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a . In the SINR model, the resulting partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a @math -dimensional map. Specifically, although the @math -dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the @math -dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location. In modern wireless networks devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Ω(n) approximations. Our algorithm still achieves an O(log n) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, existing approaches work well together with the algorithm allowing it to be used in singlehop and multi-hop scheduling scenarios. Here, we also get polylog n approximations. We study convergence of distributed protocols for power control in a non-cooperative wireless transmission scenario. There are n wireless communication requests or links that experience interference and noise. To be successful a link must satisfy an SINR constraint. Each link is a rational selfish agent that strives to be successful with the least power that is required. A classic approach to this problem is the fixed-point iteration due to Foschini and Miljanic , for which we prove the first bounds on worst-case convergence times - after roughly O(n n) rounds all SINR constraints are nearly satisfied. When agents try to satisfy each constraint exactly, however, links might not be successful at all. For this case, we design a novel framework for power control using regret learning algorithms and iterative discretization. While the exact convergence times must rely on a variety of parameters, we show that roughly a polynomial number of rounds suffices to make every link successful during at least a constant fraction of all previous rounds. The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight @math -approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal @math -approximation to the power control problem using mean power, where @math is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.