Clustering in Wireless Ad-Hoc Networks Using Graph Theoretical Algorithms

Elektrotechnik Diplomarbeiten (November 2007 - Juli 2008) net

Betreuer

Daniel Bielefeld, Gernot Fabeck,

Abstract

With the advent of Mobile Ad hoc Networks(MANETs) challenging new design characteristics arise. MANETs are distributed systems consisting of mobile wireless nodes that are self organized and perform operations to enable the communication in the network. An effcient way to exchange information between nodes in the network is to form virtual groups among nodes called clusters. A cluster normally consists of a clusterhead and ordinary nodes. The clusterhead is a node which manages local network information while the ordinary nodes are neighboring nodes of the clusterhead. The communication between clusters enables flexible infrastructure while they maintain the topology of the network as long as possible. The information exchange between any two nodes is achieved by relaying to the respective clusterhead. In this thesis, the following contributions are made : First, we address connectivity and topology control. The connectivity of the network depends on the values of certain parameters like transmission range and a node density. For given n mobile nodes with a very small value of the transmission range below this threshold, the random topology results in a disconnected network which consists of almost only independent isolated nodes. When the nodes transmission range is increased the connectivity of the network also increases dramatically until the network is surly connected. We implement the connect algorithm to optimize the network topology. The distributed algorithm adjusts the different transmission powers at different nodes resulting in an optimized connected network. Next, we address the random waypoint model, modeling the movement behavior of mobile devices in MANETs. We study the most commonly used stochastic mobility models and present a modification of them in our work. Finally, We analyze the performance of the distributed MWIS algorithm for clustering, with the weights adapted to the dynamic network. All of these topics are treated using simulations.