Graph-theoretic topology control algorithms for wireless sensor networks

Wireless sensor networks (WSN) consist of devices that are able to collect data from environment by using their onboard sensors, process this data and communicate with each other through radio signals. Since these devices are battery-powered, they should use energy efficiently. Topology control algorithms are algorithms which aim to build a backbone by reducing the number of links in networks. In this context, creating a Breath-First Search Tree (BFST) routing backbone can reduce message traffic. Vertex cover (VC) is one of the major problems of graph theory. In VC problem, incident edges of vertex are covered by creating a vertex set. On WSN with the help of VC, secure points are found and the edges are monitored. In this thesis, two algorithms are presented for constructing integrated BFST and VC on WSN. The aim is to ensure the energy efficiency by constructing these two structures together instead of constructing separately. The proposed algorithms are theoretically analyzed and compared with the existing algorithms through simulations. Keywords: Wireless Sensor Networks, Breath First Search Tree, Vertex Cover, Topology Control, Distributed Algorithm