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.
The seminal work of Gupta and Kumar @cite_7 initiated the study of the capacity of wireless networks. The authors bounded the throughput capacity in the best-case (i.e., optimal configurations) for the protocol and the physical models for @math .
@cite_7
2137775453
When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput spl lambda (n) obtainable by each node for a randomly chosen destination is spl Theta (W spl radic (nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is spl Theta (W spl radic An) bit-meters per second. Thus even under optimal circumstances, the throughput is only spl Theta (W spl radic n) bits per second for each node for a destination nonvanishingly far away. Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions. Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity. Splitting the channel into several subchannels does not change any of the results. Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance.