Connectivity Management in Ad Hoc Networks

Abstract

This thesis discusses connectivity management issues in ad hoc networks. If the link quality and node location information is available in an ad hoc network, the connectivity can be maintained or improved through adding additional network nodes at proper positions. WIDENS is an ad hoc network in which the MAC/PHY layer provides a platform that collects and transmits this kind of information. Based on this platform, a Deployment Tool of the WIDENS network can show the network topology and node information on some special network nodes. The tool can also make deployment recommendations as to where to put additional network nodes, in order to increase the connectivity of the network. To guide the development of this Deployment Tool is the main objective of this thesis.

This thesis contains a survey of literature related to this subject, and also concerns how they can be implemented in WIDENS. A basic component based Minimum Spanning Tree connectivity algorithm, with data structures used to represent the WIDENS network and to implement the Deployment Tool, is explained thoroughly. An optimization algorithm for Minimum Spanning Tree is given, to improve its performance especially in discrete metrics. A bi-connecting-while-testing algorithm, with time requirement comparison to existing algorithms in different situations, is proposed to increase the degree of connectivity of the network. Two mathematical models for connectivity management in movement are introduced briefly, which allow for discussed static connectivity algorithms to apply in a moving ad hoc network, with a simple mathematical transform.