Abstract
Heterogeneous sensor network has received a lot of attention in recent years due to its wide range of applications from battlefield to museum guide. Since wireless sensors are often powered by batteries, energy resource of the nodes is a major constraint of the wireless sensor networks. To prolong the system lifetime, it is important to maximizing the system throughput while still maintaining the node life time. \par In this study we consider a heterogeneous sensor network containing at least two types of sensors: one type of sensors is powered by batteries with limited energy, and the other is more powerful sensors which have much higher energy capacity. The powerful sensors may be used for gateways or controllers in the network. To facilitate the communication of the powerful sensors, it is necessary to build an overlay on top of the sensor network to link the powerful sensors. Given that the powerful sensors are still limited in the communication range and their communications with each other require the less powerful sensors in between for message relaying, the problem of determining the overlay topology becomes critical. This overlay must have low diameter so that it can efficiently support upper layer applications, such as resource discovery. In addition, it must consider the energy consumption of the underlying less-powerful, relaying sensors and spread the routing load evenly among the relaying sensors to prolong the system lifetime. In this thesis, we propose a distributed overlay formation protocol to achieve the above goals. Through simulation, we compare our protocol with two overlay formation protocols, {\it fully connected graph} and {\it minimum spanning tree}. The results show that our proposed protocol can achieve better performance both in message latency and energy consumption.