The PL-Gossip algorithm

Many recently proposed sensornet applications require large number of sensor nodes operating over long periods of time. In contrast to the first-generation sensornet deployments, these applications involve sophisticated internode communication rather than simple tree-based data collection. The examples include network maintenance, data-centric storage, object tracking, and various query engines. If these proposals for next-generation applications are ever to become reality, we will need solutions for self-organization of very large networks. We argue that these applications need methods for organizing nodes into recursive geometric structures, for example, proximity-based hierarchies. Such structures should provide naming that facilitates amongst others, routing, multicasting, and data aggregation and fusion. This paper presents a novel algorithm for dynamically organizing nodes in a sensornet into an area hierarchy. The algorithm employs gossiping, guaranteeing predictable maintenance traffic, which is a crucial property when it comes to energy conservation. Simulations show that the algorithm scales to large networks, works well in the presence of message loss and networ