A Review of Distributed Scheduling Algorithms for Tree based Wireless Sensor Networks

Abstract

In this paper, distributed scheduling algorithms for data collection in tree-based Wireless Sensor Networks (WSNs) are reviewed. The algorithms are categorized based on type of convergecast addressed by them i.e. (i) Aggregated convergecast (ii) Raw convergecast (iii) General approaches. In aggregated convergecast scheduling algorithm, one slot per node is selected as all incoming packets are fully aggregated with packet of the given node. So, every node sends out only one packet. In raw convergecast, as packets are not aggregated, every node needs multiple time-slots. It is desired that algorithms for aggregated convergecast should be bottom-up in nature (i.e. run from leaf nodes towards the sink) to ensure aggregation freshness. In raw convergecast, the algorithms should be hybrid in nature. It means that the execution should take place in bottom-up and also in top-down manner. This ensures that every node transmits its own packet in the smallest possible time-slot and forward packets of children in the same TDMA cycle. The General approaches are not designed for any fix convergecast method, but they have other objectives like minimizing control overhead, minimizing schedule length or minimize energy consumption and many others. This work also presents a review of algorithms related to fault tolerance. The algorithms related to fault tolerance are aimed at quickly selecting new parent/slot when some existing parent dies. When the given node dies, the parent of the given node does not receive packets from the given node. So, the parent needs lesser time-slots as it has to forward lesser number of packets. Similarly, when the given node selects new parent due to death of current parent, the new parent needs extra slots to forward packets coming from the given node. Thus fault tolerance algorithms also take care of schedule adjustment due to change in workload of nodes. It is found that still there is scope of further research as follows: (i) Hybrid joint scheduling & tree formation algorithm for raw convergecast can be designed. (ii) The slot assignment should be elastic in nature. The given node should be assigned additional slots when required and slots should be revoked when not needed. (iii) The scheduling algorithm should have some provision of priority-based data transmission. When a node has urgent or high-priority data, it should be allowed to transmit it without waiting for its transmission turn.