Power requirements for connectivity in clustered wireless networks

We consider wireless networks in which a subset of the nodes provide coverage to clusters of clients and route data packets from source to destination. We generalize previous work of Gilbert (1961), deriving conditions on the communication range of the nodes and on the placement of the covering stations to provide, with probability one, some long distance multi-hop communication. One key result is that the network can almost surely (a.s.) provide some long distance multi-hop communication, regardless of the algorithm used to place the covering stations, if the density of the clients is high enough and their communication range is less than half the communication range of the base stations. As the ratio between the two communication ranges becomes greater than half, a malicious covering algorithm that never provides long distance, multi-hop communication in the network, exists even if we constrain the base station to be placed at the vertices of a fixed grid-which is the typical scenario in the case of commercial networks.