Topology management schemes conserve energy in wireless ad hoc networks by identifying redundant nodes that may turn off their radios or other components while maintaining connectivity. We present Naps, a randomized topology management scheme that does not rely on geographic location information, provides exibility in the target density of waking nodes, and sends only a periodic heartbeat message between waking neighbors; thus it is implementable even on modest hardware. We formally analyze the connectivity of the waking graphs produced by Naps, showing that these graphs have nearly complete connectivity even at relatively low densities. We examine simulation results for a wide range of initial deployment densities and for heterogeneous and mobile deployments.

We propose a family of constant-degree routing networks of logarithmic diameter, with the additional property that the addition or removal of a node to the network requires no global coordination, only a constant number of linkage changes in expectation, and a logarithmic number with high probability. Our randomized construction improves upon existing solutions, such as balanced search trees, by ensuring that the congestion of the network is always within a logarithmic factor of the optimum with high probability. Our construction derives from recent advances in the study of peer-to-peer lookup networks, where rapid changes require efficient and distributed maintenance, and where the lookup efficiency is impacted both by the lengths of paths to requested data and the presence or elimination of bottlenecks in the network.