Distributed Sink Tree Construction in Wireless Sensor Networks with Promiscuous Learning

Sink trees such as Breadth-First Search (BFS) or Shortest-Path Tree (SPT) are essential in Wireless Sensor Networks (WSNs) for various purposes such as data gathering, aggregation, clustering, and synchronization. These trees minimize the path-lengths reachable from root node to any other node in the network. With the energy-bound sensor nodes, it is vital to construct such trees in an effective manner, by minimizing the number of message exchanges. By exploiting the broadcast nature of the underlying wireless medium, we present distributed energy-efficient algorithms for constructing BFS and SPT sink trees in WSNs. To mitigate collisions, we propose a simple distributed collision avoidance mechanism that enables efficient functioning of our tree construction algorithms. Extensive simulation study is performed for different networks by varying the size, degree, and depth. Our promiscuous learning based algorithm outperformed by incurring up to 66% less (message) exchanges than the state-of-the-art tree construction algorithm.