Applications of Graph Theory Algorithms in Mobile Ad hoc Networks

Introduction

A Mobile Ad hoc Network (MANET) is a dynamically changing infrastructureless and resource-constrained network of wireless nodes that may move arbitrarily, independent of each other. The transmission range of the wireless nodes is often limited, necessitating multi-hop routing to be a common phenomenon for communication between any two nodes in a MANET. Various routing protocols for unicast, multicast, multi-path and broadcast communication have been proposed for MANETs. The communication structures that are often determined include: a path (for unicast – single-path and multi-path routing), a tree (for multicast routing) and a Connected Dominating Set – CDS (for broadcast routing). Within a particular class, it is almost impossible to find a single routing protocol that yields an optimal communication structure with respect to different route selection metrics and operating conditions.

Various simulators such as ns-2 (Fall & Varadhan, 2001) and GloMoSim (Zeng, Bagrodia, & Gerla, 1998) are available to implement and study the behavior of the routing protocols. But, students and investigators who are new to this area often get perplexed in the complexity of these simulators and lose the focus in designing and analyzing the characteristics of the network and the protocol. Most of the time would be spent in learning the existing code modules of the simulator and the logical flow between the different code modules. The purpose of this chapter would be to illustrate the applications of Graph Theory algorithms to study, analyze and simulate the behavior of routing protocols for MANETs. Applications of Graph Theory algorithms for unicast (single-path and multi-path), multicast and broadcast communication in MANETs will be discussed.

An ad hoc network is often approximated as a unit disk graph (Kuhn, Moscibroda, & Wattenhofer, 2004). In this graph, the vertices represent the wireless nodes and an edge exists between two vertices u and v if the normalized Euclidean distance (i.e., the physical Euclidean distance divided by the transmission range) between u and v is at most 1. Two nodes can communicate only if each node lies within (or on the edge of) the unit disk of the other node. The unit disk graph model neatly captures the behavior of many practical ad hoc networks and would be used in the rest of this chapter for discussing the algorithms to simulate the MANET routing protocols.

Most of the contemporary routing protocols proposed in the MANET literature adopt a Least Overhead Routing Approach (LORA) according to which a communication structure (route, tree or CDS) discovered through a global flooding procedure would be used as long as the communication structure exist, irrespective of the structure becoming sub-optimal since the time of its discovery in the MANET. This chapter will also adopt a similar strategy and focus only on discovering a communication structure on a particular network graph taken as a snapshot during the functioning of the MANET. Such a graph snapshot would be hereafter referred to as a ‘Static Graph’ and a sequence of such static graphs over the duration of the MANET simulation session would be called a ‘Mobile Graph’. A communication structure determined on a particular static graph would be then validated for its existence in the subsequent static graphs and once the structure breaks, the appropriate graph algorithm can be invoked on the static graph corresponding to that particular time instant and the above procedure would be continued for the rest of the static graphs in the mobile graph. The big-O notation is used to express the theoretical worst-case run-time complexity of the algorithms discussed in this paper. Given a problem size x, where x is usually the number of items, one can say f(x) = O(g(x)), when there exists positive constants c and k such that 0 ≤ f(x) ≤ cg(x), for all x ≥ k (Cormen et al. 2001).

The following are the learning objectives of this chapter with regards to the applications of Graph Theory algorithms in Mobile Ad hoc Networks: