View article

Assumptions about node density in the sensor networks literature are frequently too strong. Neither adversarially chosen nor uniform random deployment seem realistic in many intended applications of sensor nodes. We define smooth distributions of sensor nodes to be those where the minimum density is guaranteed to achieve connectivity in random deployments, but higher densities may appear in certain areas. We study basic problems for smooth distribution of nodes. Most notably, we present a Weak Sensor Model-compliant distributed protocol for hop-optimal network initialization (NI), a fundamental problem in sensor networks. In order to prove lower bounds, we observe that all nodes must communicate with some other node in order to join the network, and we call the problem of achieving such a communication the group therapy (GT) problem. We show a tight lower bound for the GT problem in …