On maximizing the throughput of convergecast in wireless sensor networks

A primary task of wireless sensor networks is collecting environmental information. In most cases, a sink node is responsible for collecting data from all sensor nodes. The radio congestion around the sink becomes the main bottleneck to maximizing the throughput of the convergecast. A general strategy to alleviating the problem is to schedule the communications among sensors to avoid interference. In this paper, we consider both routing structures and communication schedules for optimizing the scheduling length. We show that the shortest-length conflict-free scheduling is equivalent to finding a minimal vertex coloring. To solve the schedule problem, a virtual-node expansion is proposed to handle the relay operations in convergecast, and then coloring algorithms are used to obtain the communication schedule. However, scheduling only solves part of the problem. Routing structures will also affect the scheduling quality. The disjoint-strips routing is thus proposed to leverage possible parallel transmissions in convergecast. The proposed algorithms are evaluated through simulations.