We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close --- thus, the available pairs are modeled with a link graph $\mathcal{L}=(V,E)$. Also, signal attenuation need not follow a nice geometric formulas --- hence, interference is modeled by a conflict (hyper)graph $\mathcal{C}=(E,F)$ on the links. The objective is to maximize the efficiency of the communication, or equivalently minimizing the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a $O(ρ\log n)$-approximation, where $n$ is the number of nodes and $ρ$ is the inductive independence, and show that near-linear dependence on $ρ$ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and "niceness" in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

We study a fundamental measure for wireless interference in the signal-to-interference noise ratio model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power---when the power used by a transmitter only depends on the distance to the receiver---as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves capacity that is---due to existing lower bounds---asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems involving both oblivious power and arbitrary power control, including connectivity, secondary spectrum auctions, and dynamic packet scheduling. We also show that the price of oblivious power---the relative increase in capacity possible when using unconstrained power control---is only doubly logarithmic in the maximum link length.

We present a framework for the maximum flow problem in wireless networks using the SINR interference model in combination with MIMO nodes. The performance ratio of our algorithm matches the best O(log n) approximation factor known for the pure flow problem, but avoids the impractical dependence on the ellipsoid method and features both simpler and more intuitive analysis. The objective of a maximum flow in wireless networks is to get as much information from a sender to a receiver using intermediate nodes in a multi-hop environment. The algorithm is based on an LP formulation of the flow problem, and handles gracefully all additional linear constraints. The set of constraints that can be included contains, among other, power limits, fairness between source-sink pairs, capacity limits and bounds, and the use of Multi-Input Multi-Output nodes for the source and the sink nodes, which are often the bottlenecks in a wireless flow.

We present randomized distributed algorithms for connectivity and aggregation in multi-hop wireless networks under the SINR model. The connectivity problem asks for a set of links that strongly connect a given set of wireless nodes, along with an efficient schedule. Aggregation asks for a spanning in-arborescence (converge-cast tree), along with a schedule that additionally obeys the partial order defined by the tree. Here we treat the multi-hop case, where nodes have limited power that restricts the links they can potentially form. We show that connectivity is possible for any set of n nodes in O(\log n) slots, which matches the best centralized bound known, and that aggregation is possible in O(D + log n) time (D being the maximum hop-distance), which is optimal.

We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power — when the power used by a transmitter only depends on the distance to the receiver — as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves — due to existing lower bounds — capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment.

No abstract available.

We consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. Combinatorially, this means a) finding a set of links that form a strongly connected spanning graph on a set of n points in the plane, and b) scheduling it efficiently in the SINR model of interference. The nodes must converge on a solution in a distributed manner, having no means of communication beyond the sole wireless channel.

Given n wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in O(log n) slots, improving on the previous best bound of O(log2 n) due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of Ω(1/ log n) on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of Ω(n) slots for connectivity. This rules out a recent claim of a O(log n) bound using oblivious power. On the other hand, using our result we show that O(min(log Δ, log n · (log n + log log Δ))) slots suffice, where Δ is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with O(log n) latency is possible, improving upon the previous best known latency of O(log3 n). We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and k-edge connected structures.

We consider the capacity problem (or, the single slot scheduling problem) in wireless networks. Our goal is to maximize the number of successful connections in arbitrary wirelessnetworks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz (INFOCOM 2009) and Dinitz (INFOCOM 2010). We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a O(log Δ) approximation, where Δ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.

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 θ(log n)-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal O(log n + log log Δ)-approximation to the power control problem using mean power, where Δ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.