Connectivity of Random Wireless Networks with Distributed Resource Allocation

We study the connectivity of wireless networks consisting of n nodes that are located independently and uniformly at random on the unit square. Our focus is on an orthogonal multiple access scenario where there are M orthogonal resources (e.g. time slots and/or frequency bands) that are to be assigned to each connection in the network. Correspondingly, we consider a disk-interference model where two nodes can be connected over resource m if (i) they are within communication range R, and (ii) no other node within distance R to either one of the two nodes uses the resource m. In such a scenario, it is known that if one is allowed to optimally choose (depending on the node locations) the node connections and the associated resources, the conditions R² ∈ Θ(logn/n) and M ∈ Θ(log n) are necessary and sufficient to ensure asymptotically almost sure connectivity as n → ∞. We propose a distributed resource allocation scheme where each node, unaware of its (and other nodes´) geographical location(s), decides on its connections and the associated resources by communicating with its neighboring nodes only. Our scheme provides a connected network under the best-possible conditions R² ∈ O(log n/n) and M ∈ O(log_n).