On tree-based convergecasting in wireless sensor networks

A wireless sensor network (WSN) consists of sensors implanted in an environment for collecting and transmitting data regarding changes in the environment based on the requests from a controlling device (called base station) using wireless communication. WSNs are being used in medical, military, and environment monitoring applications. Broadcast (dissemination of information from a central node) and convergecast (gathering of information towards a central node) are important communication paradigms across all application domains. Most sensor applications involve both convergecasting and broadcasting. The time taken to complete either of them has to be kept minimal. This can be accomplished by constructing an efficient tree for both broadcasting as well as convergecasting and allocating wireless communication channels to ensure collision-free communication. There exist several works on broadcasting in multihop radio networks (a.k.a. ad hoc networks), which can also be used for broadcasting in WSNs. These algorithms construct a broadcast tree and compute a schedule for transmitting and receiving for each node to achieve collision-free broadcasting. In this paper, we show that we need a new algorithm for applications, which involve both convergecasting and broadcasting since the broadcast tree may not be efficient for convergecasting. So we propose a heuristic algorithm (convergecasting tree construction and channel allocation algorithm (CTCCAA)), which constructs a tree with schedules assigned to nodes for collision free convergecasting. The algorithm is capable of code allocation (direct sequence spread spectrum (DSSS)/ frequency hopping spread spectrum (FHSS)), in case multiple codes are available, to minimize the total duration required for convergecasting. We also show that the same tree can be used for broadcasting and is as efficient as a tree exclusively constructed for broadcasting.