Abstract
The primary function of wireless sensor networks is to sense the environment and gather data. In typical scenarios, a single sink node is used to collect data from all the sensor nodes of the network. The load of the sink will be heavy and wireless communication around the sink tends to be congested. A general strategy to solving the problem is to schedule the communications of the sensor nodes so that their radio transmissions will not interfere with each other. Assuming each sensor has a piece of sensed data to send back to the sink, the above problem becomes that of scheduling the transmission and relaying of these data in the sensor network so that the throughput is maximized. That is, all the data are sent to the sink in the shortest time subject to the radio interfere among the sensor nodes. However, to do this, we must first organize the sensor nodes into a certain transmission structure, often a tree, to relay the data back to the sink. This structure must take into account of the radio interference among the sensors and the balance of the nodes in the subtrees. In this thesis, we consider gathering-structure construction and transmission scheduling together, aiming at a more compact and efficient schedule than using simple greedy heuristics. We study how different gathering topologies affect the system throughput and propose an efficient routing algorithm for data gathering that complements the shortest-path routing algorithm. The knowledge of the gathering structure is then used to guide the graph coloring heuristic to schedule the data transmissions. The proposed schemes are evaluated and verified through simulations.