Abstract
This paper presents an on-demand clustering and routing scheme for Mobile Ad Hoc Networks (MANETs) that extends the Ad hoc On-demand Distance Vector (AODV) protocol. By integrating cluster formation with routing control messages and employing a mobility-aware election process, the proposed Cluster-AODV achieves lower communication overhead and enhanced scalability compared to standard AODV and proactive clustering methods.
Introduction
Mobile Ad Hoc Networks (MANETs) are decentralized, self-configuring networks of mobile devices. Due to unpredictable node movement and limited resources such as battery and bandwidth, efficient routing remains a significant challenge. Standard reactive protocols like AODV perform well in small networks but suffer from "broadcast storms"—where route requests flood the entire network—as node density increases. Conversely, traditional proactive clustering often generates excessive background maintenance traffic in highly mobile environments. Cluster-AODV aims to bridge this gap by creating an on-demand, distributed clustering system designed to scale AODV for larger, dynamic networks.
Methodology: The Cluster-AODV Framework
The authors introduce Cluster-AODV, which modifies the standard AODV framework through several key innovations:
- Node Roles: Nodes are assigned specific roles: Cluster Head (CH), Secondary Cluster Head (SCH) for redundancy, Gateway (GW) to connect clusters, Ordinary Node, or Undecided.
- Mobility-Aware Election: Rather than relying on node IDs, the algorithm uses a "mobility index." Nodes with lower relative movement are prioritized as Cluster Heads, leading to increased cluster stability.
- Hierarchical Routing:
- Intra-cluster: Destinations within the same cluster are reached using a Local Route Request (LRREQ).
- Inter-cluster: For destinations outside the cluster, RREQs are only forwarded by Gateways and CHs. This pruning of the search tree drastically reduces network-wide flooding.
- On-Demand Maintenance: Clusters are formed or updated only when data transmission is required, leveraging AODV’s existing "Hello" messages to minimize overhead.
Experimental Setup
The scheme was evaluated through rigorous simulation using the NS2 (Network Simulator 2) tool. The environment consisted of 100 to 200 nodes randomly placed in a 1000m x 1000m area. The "Random Waypoint" mobility model was used, with node speeds ranging from 0 to 20 m/sec and a 40-second pause time. Traffic was modeled as Constant Bit Rate (CBR) with 30 source-destination pairs.
Key Results and Insights
Simulation results indicate that Cluster-AODV consistently outperforms pure AODV and traditional clustering algorithms (such as Lowest ID or Highest Connectivity):
- Enhanced Stability: Cluster-AODV achieved an average cluster member residence time of 110–130 seconds, significantly higher than competing methods. This is attributed to the mobility index, which selects "quiet" nodes as leaders.
- Reduced Routing Overhead: In a 200-node network, the normalized routing overhead for Cluster-AODV was substantially lower than pure AODV, particularly as node speed increased.
- Improved Packet Delivery Ratio (PDR): Cluster-AODV maintained higher reliability as network size grew. For a 200-node network, the PDR remained near 0.91, while pure AODV dropped toward 0.85.
- Redundancy: The election of a Secondary CH (SCH) effectively mitigates the "single point of failure" risk by providing a backup head that stores routing tables.
Limitations and Future Work
While Cluster-AODV shows promise, it currently focuses on two-hop clusters. Future work will explore multihop clustering to support even larger or sparser environments. Additionally, while communication overhead is reduced, the increased memory and processing requirements on Cluster Heads require further analysis. The authors plan to develop a cluster-based middleware for data dissemination and replica management, utilizing this stable clustering backbone for higher-level applications.
Summary updated