Algorithmic study of wireless ad hoc network problems

This dissertation focuses on two important problems in wireless ad hoc networks, namely broadcast scheduling and cluster formation. In a wireless ad hoc network, radio stations share a common channel over which communications take place. As the communication spectrum is limited, it is necessary to have efficient channel assignment algorithms so that transmission conflicts can be avoided. Moreover, when dealing with large networks it is desirable to have certain hierarchical architecture so that many problems can be solved efficiently. To this end we will consider the clustering architecture, which provides an infrastructure that supports efficient routing and localizes transmission conflicts in wireless ad hoc networks.; With regard to broadcast scheduling we investigate the problem of maximizing a set of radio stations that can broadcast simultaneously without causing any transmission conflicts. This is known as the problem of computing a maximum broadcasting set in a wireless ad hoc network. It turns out that this problem is NP-complete. Therefore we provide for it an efficient heuristic as well as its distributed implementation. We perform experiments to show that our heuristic performs better than other methods.; As wireless ad hoc networks are dynamic in nature, their mobility characteristic should be taken into consideration. This leads us to investigating the problem of adapting maximum broadcasting sets to simple topology changes, which is shown to be NP-complete. We develop a new heuristic to adapt maximal broadcasting sets to local changes in wireless ad hoc networks. We also provide a distributed implementation and do experiments to show that the performance of our heuristic is comparable with the rerun approach which simply computes a new maximal broadcasting set when the network topology changes.; With regard to the cluster formation problem, we study the problem of forming a clustering architecture so that the number of clusters is as small as possible. We show that the problem of computing a minimum d-hop, dominating set is NP-complete even when the networks under consideration are unit disc graphs (which are perhaps the simplest model of wireless ad hoc networks). We then investigate the problem of adapting d-hop dominating sets to topology changes. As the problem of adapting minimum d-hop dominating sets is shown to be NP-complete, we design a heuristic that adapts minimal d-hop, dominating sets to topology changes. We provide a distributed implementation of our heuristic and do experiments to show that its performance is comparable with the rerun approach.; Finally, we explore the problem of forming connected d-hop clusters in wireless ad hoc networks. In this clustering architecture the cluster heads are connected. As the problem of computing a minimum connected d-hop dominating set is shown to be NP-complete, we develop a heuristic and provide a distributed implementation. Experiments show that our heuristic performs substantially better than others.