Time-optimal convergecast in sensor networks with multiple channels

Abstract

Sensor networks consist of a set of wireless sensor nodes which sense the environment and route the sensed information to a sink node. Data gathering is one of the important applications in sensor networks. In this thesis, using multiple channels, we consider TDMA schedule algorithm focusing on many-to-one communication which is called convergecast. In convergecast, a packet generated in each sensor node is delivered to a sink node without any data aggregation in the intermediate node. In large network environment with many hops, we found that usage of multiple channels significantly improves delay efficiency comparing to usage of a single channel. We formulate this problem and propose heuristic algorithms for proper channel assignment and convergecast in different topologies. In general topology, with 2 channels, we present the convergecast algorithm requiring timeslot at most 2N−1+d where N is the number of sensor nodes and d is the delay to avoid interference among sensor nodes. We also found that, for general topology, usage of 4 channels contributes to even more delay efficiency which can achieve d=0. Furthermore, unlike using 3 or fewer channels, using 4 channels is also memory efficient without creating an extra internal memory table in a sensor node to avoid interference among nodes. Additionally, such delay efficiency can result in energy efficiency which is also another important issue in sensor networks.