The goal is to connect N randomly placed points (nodes) in a unit square or cube using wireless transmitters. More formally, the goal is to associate each node x with a non-negative real number D_x in such a way that the set of nodes together with all oriented couples [x,y] such that the Euclidean distance of x and y is at most D_x forms a strongly connected graph. Assuming that D_x is related to the power of the transmitter of x (usually the power is proportional to the square of D_x), we are looking for power-efficient solution.
An asymptotically optimal solution of Clementi et al. requires global knowledge of a network that is often not available before a network connecting the nodes is established and it also needs information about positions (GPS coordinates) of the nodes. Two known solutions based on local distributed algorithms (the nit disk model, i.e. the same D_x for all nodes, and regular degree model, i.e. each node transmitting to the same number of the nearest neighbours) are proved to be power inefficient.
Roughly speaking, the present solution is based on a local distributed algorithm connecting most nodes using transmission to a small constant number of nearest neighbours (a giant component of the corresponding random geometric graph) and higher power (number of neighbours) for remaining nodes. In this way we are able to connect all points using constant (independent of N) average power per transmitter. A rigorous analysis of the problem (the size of the giant component) uses known results from percolation theory.