Minimization of the Diffusion Delay of a Tree-Based Wireless Sensor Network

In wireless sensor networks, saving energy is crucial in order to increase the network lifetime. Energy is often saved by synchronizing the nodes activity, and having long periods of inactivity, or by having nodes exchange a global activity schedule. The synchronization and the exchange of a global schedule are two examples where information is broadcast from a specific node to the whole network. In this paper, we focus on the delay required to broadcast information in the whole network using a tree topology. We first show that the diffusion delay can be significantly reduced by utilizing the parallelization of node processing. We provide an algorithm in order to find optimal solutions when transmissions are sequential. Then, we propose a linear algorithm that is able to find good solutions. We compare the exact solution to the heuristic solution on a workstation and conclude that our heuristic is very competitive and can be used to reduce the diffusion delay of a broadcast frame in a tree.