Creating and maintaining topologies in wireless networks

Sammanfattning: Wireless ad-hoc networks differs in many aspects compared to traditional infrastructured networks. Among other things, individual nodes cannot be expected to know the topology of the entire network. Also, since nodes typically are powered by batteries and eventually will run out of energy, it is imperative for algorithms to minimize the energy cost while distributing it as fairly as possible over all nodes in the network. This thesis covers different types of distributed algorithms for wireless networks, where all of them in some way creates or maintains a topology in order to facilitate communication in the network. The thesis comprises three scientific papers. The first paper concerns clustering, dividing the set of nodes in a network into subsets based on the network's connectivity graph. We propose a new clustering algorithm which uses the novel idea to maintain an existing clustering structure rather than creating a new structure from scratch, in order to minimize the changes in the structure as well as the communication overhead. The second paper covers interference reduction through topology control. We discuss previous work in how to measure interference, and present new metrics that aims to measure the average interference of the network rather than just the worst path. We also propose a new topology control algorithm and compare its performance to previous topology control algorithms, using our as well as previous interference models. In the third paper, we present a power-aware routing algorithm for Bluetooth networks. Unless similar previous work, our algorithm does not require the nodes to have any knowledge of the network except for their neighbors. By collecting path information in the routing messages, individual nodes can still make routing decisions in order to avoid nodes that are close to being depleted of energy. We also present a simplified version of the algorithm for general wireless ad-hoc networks.