Distributed time-optimal scheduling for convergecast in wireless sensor networks


Event Computer Networks


Zhang, Ying
Technical Publications
February 22nd 2008
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(3nk-1,N) timeslots for convergecast, where nk 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.


Gandham, S.; Zhang, Y.; Huang, Q. Distributed time-optimal scheduling for convergecast in wireless sensor networks. Computer Networks. 2008 February 22; 52 (3): 610-629.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.


PARC scientists and staffers are active members and contributors to the science and technology communities.