Connectivity of Random Wireless Networks with Distributed Resource Allocation
Erdem Koyuncu, Hamid Jafarkhani · 2015 IEEE Global Communications Conference (GLOBECOM) · 2015
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 R2∈ Θ(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 R2∈ O(log n/n) and M ∈ O(logn).