Applications of Graph Theory Algorithms in Mobile Ad hoc Networks

Applications of Graph Theory Algorithms in Mobile Ad hoc Networks

Natarajan Meghanathan (Jackson State University, USA)
DOI: 10.4018/978-1-4666-0080-5.ch004
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Various simulators (e.g., ns-2 and GloMoSim) are available to implement and study the behavior of the routing protocols for Mobile Ad hoc Networks (MANETs). However, 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 is spent in learning the existing code modules of the simulator and the logical flow between the different code modules. The purpose of this chapter is to illustrate the applications of Graph Theory algorithms to study, analyze, and simulate the behavior of routing protocols for MANETs. Specifically, the chapter focuses on the applications of Graph Theory algorithms to determine paths, trees, and connected dominating sets for simulating and analyzing respectively unicast (single-path and multi-path), multicast, and broadcast communication in mobile ad hoc networks (MANETs). The chapter discusses the (i) Dijkstra’s shortest path algorithm and its modifications for finding stable paths and bottleneck paths; (ii) Prim’s minimum spanning tree algorithm and its modification for finding all pairs smallest and largest bottleneck paths; (iii) Minimum Steiner tree algorithm to connect a source node to all the receivers of a multicast group; (iv) A node-degree based algorithm to construct an approximate minimum Connected Dominating Set (CDS) for sending information from one node to all other nodes in the network; and (v) Algorithms to find a sequence of link-disjoint, node-disjoint, and zone-disjoint multi-path routes in MANETs.
Chapter Preview
Top

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 xk (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:

Complete Chapter List

Search this Book:
Reset