Minimal time convergecast scheduling 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 (3n(sub)k -1, N) timeslots for convergecast, where n(sub)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 around 1.5N timeslots are required. 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 simple modifications to apply our algorithm when (i) the convergecast is initiated by the base station, (ii) nodes employ packet aggregation, (iii) nodes generate multiple packets and (iv) the wireless channel propagation characteristics are not ideal. We present simulation results to show that our convergecast scheduling algorithm performs better than existing convergecast algorithms.
Gandham, S.; Zhang, Y. ; Huang, Q. Minimal time convergecast scheduling in wireless sensor networks. 26th International IEEE Conference on Distributed Computing Systems (ICDCS 2006); 2006 July 4-7; Lisbon, Portugal.