Distributed time-optimal scheduling for convergecast in wireless sensor networks

We consider applications of sensor networks wherein data packets generated by every node have to reach the base station. This results in a many-to-one communication paradigm referred to as convergecast. We are interested in determining a TDMA schedule that minimizes the total time required to complete the convergecast. Initially, we consider a simple version of the problem wherein every node generates exactly one packet. We provide a distributed scheduling algorithm for tree networks that requires at most max(3n(k) - 1,N) timeslots for convergecast, where n(k) represents the maximum number of nodes in any subtree and N represents the number of nodes in the network. We propose a distributed convergecast scheduling algorithm for general networks that requires at most 3N timeslots. Through extensive simulations, we demonstrate that actual number of timeslots needed is around 1.5N. In addition to time efficiency, we prove that our convergecast scheduling algorithm requires the nodes to buffer no more than two packets at any instance. We propose a sleep schedule that conserves more than 50% of the energy. We propose simple modifications to apply our algorithm when (i) the convergecast is initiated by the base station, (ii) nodes generate multiple packets and (iii) the wireless channel propagation characteristics are not ideal. Simulation results for a real application scenario show that our convergecast scheduling algorithm performs significantly better than existing convergecast algorithms. (c) 2007 Elsevier B.V. All rights reserved.