Randomized Initialization of a Wireless Multihop Network

The initialization problem consists to give a unique identifier ranging from 1 to n for a set of n indistinguishable nodes. We consider here a wireless network where n nodes (processors) are randomly thrown in a square X, uniformly and independently. We assume that the network is synchronous and two nodes are able to communicate if they are within distance at most of r of each other. We design a distributed protocol to achieve the initialization task for a wireless multihop network of n nodes uniformly scattered in a square X. We show how the transmitting range of the deployed stations can affect the typical characteristics such as the degrees and the diameter of the network. By allowing the nodes to transmit at a specific range, we show how to design a randomized protocol running in expected time O(n^{3/2} log^2 n) for the initialization problem.