This chapter proposes a scenario-based and diameter-bounded algorithm for cluster formation and management in mobile ad hoc networks (MANETs). A (k, r) -Dominating Set is used for the selection of clusterheads and gateway nodes depending on the topology of the network. Here k is the minimum number of clusterheads per node in the network and r is the maximum number of hops between the node and the clusterhead. The non-clusterhead node selects the most qualified dominating node as its clusterhead from among the k dominating nodes. The quality of the clusterhead is a function of various metrics, which include connectivity, stability and residual battery power. The long-term service as a clusterhead depletes its energy, causing it to drop out of the network. Similarly, the clusterhead with relatively high mobility than its neighbors leads to frequent clusterhead election process. This perturbs the stability of the network and can adversely affect the network performance. Load balancing among the clusterheads and correct positioning of the clusterhead in a cluster are vital to increase the lifespan of a network. The proposed centralized algorithm periodically calculates the quality of all dominating nodes in the network and if it goes below the threshold level it resigns the job as the clusterhead and sends this message to all other members in the cluster. Since these nodes have k dominating nodes within the r -hop distance, it can choose the current best-qualified node as its clusterhead. Simulation experiments are conducted to evaluate the performance of the algorithm in terms of the number of elements in the (k, r)-DS, the load balancing factor, the number of re-affiliations per unit time and the number of dominating set updates per unit time. The results establish the potential of this algorithm for use in MANETs.
TopIntroduction
A MANET is a self configuring wireless, multi-hop, and dynamic network consists of mobile nodes that operate without the need for any established infrastructure. This type of network is highly demanding due to the lack of infrastructure and easiness and cost effectiveness in installation. Each node in the network will be able to communicate directly with any other node that resides within its transmission range, whereas intermediate nodes are required for communicating with the nodes that reside beyond the transmission range. All nodes in the ad hoc network take part in the communication process. They are free to move randomly, and arbitrarily organized themselves to create unpredictable network topologies. A MANET can operate in stand-alone fashion or can be connected to a fixed infrastructure with the help of gateway devices to facilitate Internet connectivity even in remote places.
The MANET is useful in situations where the development of infrastructure is expensive or inconvenient to use or set up, or if it is absent. It has many emerging applications, which include commercial, industrial and war front applications, search and rescue operations, sensor networks and vehicular communications. Nodes in the MANETs are generally battery operated with limited processing power and memory capacity. Wireless networks generally have limited bandwidth and nodes with high mobility. Such networks often experience high partitioning rate due to the increase in the link breakage rates. If the two hosts that want to communicate are outside their wireless transmission ranges, they could communicate only if the other hosts between them in the ad hoc wireless network are willing to forward packets for them. Instead of using specialized routers for path discovery and traffic routing, each node in the ad hoc network acts as a router and take part in the communication process. Each node operates in distributed peer-to-peer mode, acts as an independent router and generates independent data. Designing efficient routing protocols for MANETs is a very challenging task and it is an active area of research. The major issues in cluster based MANETs are mobility management, topology assignment, clustering overhead, frequent clusterhead re-election, overhead of clusterhead, depletion of battery power, security and Quality of Service (QoS).
Destination Sequenced Distance-Vector (DSDV) (Perkins, 1994), Dynamic Source Routing (DSR) (Johnson, 1996) and Ad hoc On demand Distance Vector (AODV) (Perkins, 1999) are some of the popular protocols proposed for multi-hop routing. These flat routing schemes encounter scalability problems with increased network size. The signaling overhead of the routing algorithms based on reactive and proactive routing schemes increases with the size and mobility of the network. The expensive message flooding schemes for route discovery and maintenance can be reduced in hierarchical routing. Hierarchical architectures help in increasing the lifetime of the network and also increase the network scalability. With clustering, the mobile nodes are divided into a number of virtual groups called clusters. Nodes in a cluster can be of type clusterhead, gateway or ordinary node. The clusterhead is the coordinator for the operations within the cluster. Cluster based virtual network architecture requires many information exchanges to perform routing as well as to form and maintain clusters. A stable clustering algorithm should not change the cluster configuration frequently. The advantages of clustering include (i) efficient handling of mobility management (ii) provision for optimization in routing mechanism (iii) shared use of application within the group (iv) spatial reuse of resources (v) better bandwidth utilization (vi) aggregation of topology information (vii) virtual circuit support (viii) making a dynamic topology appear less dynamic (Mc Donald, 1999) and (ix) minimizing the amount of storage for communication (Basagni, 2006).