  We study the problem of power-efficient routing for multihop wireless ad hoc
sensor networks. The guiding insight of our work is that unlike an ad hoc
wireless network, a wireless ad hoc sensor network does not require full
connectivity among the nodes. As long as the sensing region is well covered by
connected nodes, the network can perform its task. We consider two kinds of
geometric random graphs as base interconnection structures: unit disk graphs
$\UDG(2,\lambda)$ and $k$-nearest-neighbor graphs $\NN(2,k)$ built on points
generated by a Poisson point process of density $\lambda$ in $\RR^2$. We
provide subgraph constructions for these two models $\US(2,\lambda)$ and
$\NS(2,k)$ and show that there are values $\lambda_s$ and $k_s$ above which
these constructions have the following good properties: (i) they are sparse;
(ii) they are power-efficient in the sense that the graph distance is no more
than a constant times the Euclidean distance between any pair of points; (iii)
they cover the space well; (iv) the subgraphs can be set up easily using local
information at each node. We also describe a simple local algorithm for routing
packets on these subgraphs. Our constructions also give new upper bounds for
the critical values of the parameters $\lambda$ and $k$ for the models
$\UDG(2,\lambda)$ and $\NN(2,k)$.
