Efficient algorithms to compute sleep schedules resulting in minimum delay routes in sensor networks

In wireless sensor networks, it is important to minimize energy consumption of the sensor nodes. Energy consumption of sensor nodes can be reduced explicitly by making sensors sleep when they are idle. In this paper, we consider a single wake-up periodic schedule in that the sensor wakes up in one slot out of k slots. This results in every sensor node having a duty cycle of 1/k on an average. However, since the sensors are not awake all the time, transmissions get delayed since one of the two neighbours is in sleep mode. This requires that a sleep schedule be computed such that the network transmission delay is minimum. In the past, algorithms have been proposed that compute minimum delay sleep schedules of the sensors. However, the algorithms that obtain sleep schedules and routes with small delays are highly computationally intensive. In cases of sensor networks in which the topology changes, it is required that the sleep schedules are computed on-the-fly. This requires the algorithms to be efficient. In this paper, we propose two algorithms that compute sleep schedules and routes with small delays and are much more efficient. We evaluate the proposed algorithms on the basis of delay diameter, average all pair delay and average number of hops in a path. We also compare their performance on the basis of execution time.