In this paper we study the connectivity problem for wireless networks under the Signal to Interference plus Noise Ratio (SINR) model. Given a set of radio transmitters distributed in some area, we seek to build a directed strongly connected communication graph, and compute an edge coloring of this graph such that the transmitter-receiver pairs in each color class can communicate simultaneously. Depending on the interference model, more or less colors, corresponding to the number of frequencies or time slots, are necessary. We consider the SINR model that compares the received power of a signal at a receiver to the sum of the strength of other signals plus ambient noise . The strength of a signal is assumed to fade polynomially with the distance from the sender, depending on the so-called path-loss exponent ?. We show that, when all transmitters use the same power, the number of colors needed is constant in one-dimensional grids if ?> 1 as well as in two-dimensional grids if ?> 2. For smaller path-loss exponents and two-dimensional grids we prove upper and lower bounds in the order of @math and ?(logn loglogn) for ?= 2 and ?(n 2 ?? 1) for ?< 2 respectively. If nodes are distributed uniformly at random on the interval [0,1], a regular coloring of @math colors guarantees connectivity, while ?(loglogn) colors are required for any coloring.
We define and study the scheduling complexity in wireless networks, which expresses the theoretically achievable efficiency of MAC layer protocols. Given a set of communication requests in arbitrary networks, the scheduling complexity describes the amount of time required to successfully schedule all requests. The most basic and important network structure in wireless networks being connectivity, we study the scheduling complexity of connectivity, i.e., the minimal amount of time required until a connected structure can be scheduled. In this paper, we prove that the scheduling complexity of connectivity grows only polylogarithmically in the number of nodes. Specifically, we present a novel scheduling algorithm that successfully schedules a strongly connected set of links in time O(logn) even in arbitrary worst-case networks. On the other hand, we prove that standard MAC layer or scheduling protocols can perform much worse. Particularly, any protocol that either employs uniform or linear (a node’s transmit power is proportional to the minimum power required to reach its intended receiver) power assignment has a Ω(n) scheduling complexity in the worst case, even for simple communication requests. In contrast, our polylogarithmic scheduling algorithm allows many concurrent transmission by using an explicitly formulated non-linear power assignment scheme. Our results show that even in large-scale worst-case networks, there is no theoretical scalability problem when it comes to scheduling transmission requests, thus giving an interesting complement to the more pessimistic bounds for the capacity in wireless networks. All results are based on the physical model of communication, which takes into account that the signal-tonoise plus interference ratio (SINR) at a receiver must be above a certain threshold if the transmission is to be received correctly. In this paper we shed new light on the fundamental gap between graph-based models used by protocol designers and fading channel models used by communication theorists in wireless networks. We experimentally demonstrate that graph-based models capture real-world phenomena inadequately. Consequentially, we advocate studying models beyond graphs even for protocol-design. In the main part of the paper we present an archetypal multi-hop situation. We show that the theoretical limits of any protocol which obeys the laws of graph-based models can be broken by a protocol explicitly defined for the physical model. Finally, we discuss possible applications, from data gathering to media access control.  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. The throughput capacity of arbitrary wireless networks under the physical Signal to Interference Plus Noise Ratio (SINR) model has received much attention in recent years. In this paper, we investigate the question of how much the worst-case performance of uniform and non-uniform power assignments differ under constraints such as a bound on the area where nodes are distributed or restrictions on the maximum power available. We determine the maximum factor by which a non-uniform power assignment can outperform the uniform case in the SINR model. More precisely, we prove that in one-dimensional settings the capacity of a non-uniform assignment exceeds a uniform assignment by at most a factor of (O( L_ ) ) when the length of the network is (L_ ). In two-dimensional settings, the uniform assignment is at most a factor of (O( P_ ) ) worse than the non-uniform assignment if the maximum power is (P_ ). We provide algorithms that reach this capacity in both cases. These bounds are tight in the sense that previous work gave examples of networks where the lack of power control causes a performance loss in the order of these factors. To complement our theoretical results and to evaluate our algorithms with concrete input networks, we carry out simulations on random wireless networks. The results demonstrate that the link sets generated by the algorithms contain around 20–35 of all links. As a consequence, engineers and researchers may prefer the uniform model due to its simplicity if this degree of performance deterioration is acceptable. In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a color such that the pairs in each color class (representing pairs communicating in the same time slot) can communicate simultaneously at the specified power levels. 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 modelling interference in the engineering community. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests. We study oblivious power assignments in which the power value of a pair only depends on the distance between the points of this pair. We prove that oblivious power assignments cannot yield approximation ratios better than Ω(n) for the directed version of the problem, which is the worst possible performance guarantee as there is a straightforward algorithm that achieves an O(n)-approximation. For the bidirectional version, however, we can show the existence of a universally good oblivious power assignment: For any set of n bidirectional communication requests, the so-called "square root assignment" admits a coloring with at most polylog(n) times the minimal number of colors. The proof for the existence of this coloring is non-constructive. We complement it by an approximation algorithm for the coloring problem under the square root assignment. This way, we obtain the first polynomial time algorithm with approximation ratio polylog(n) for interference scheduling in the physical model.