Source-linked AI summary
Survey of clustering algorithms for MANET
Ratish Agarwal, Dr. Mahesh Motwani
TL;DR
Mobile ad hoc networks need clustering because mobility changes topology and can increase topology-maintenance overhead, while flat routing can produce excessive information. The paper surveys clustering schemes, including approaches using cluster roles, thresholds, on-demand election, connectivity, mobility, energy, and stability criteria. It identifies cluster stability, control overhead, energy consumption, traffic distribution, and clusterhead fairness as important issues for cluster-based MANETs.
Problem
Changing topology and excessive routing information make efficient organization of mobile ad hoc networks an important research issue.
Method
The paper surveys and classifies different MANET clustering schemes and their clusterhead-election, maintenance, load-balancing, and stability approaches.
Results
The survey covers schemes focused on reducing clustering overhead, balancing cluster load, controlling clusterhead election, and improving stability through criteria such as mobility, energy, and entropy.
Takeaways & Limitations
The survey highlights cluster stability, construction and maintenance overhead, energy consumption, traffic-load distribution, and fairness in clusterhead service as key issues for MANET clustering.
Abstract
from arXiv · showhide
Many clustering schemes have been proposed for ad hoc networks. A systematic classification of these clustering schemes enables one to better understand and make improvements. In mobile ad hoc networks, the movement of the network nodes may quickly change the topology resulting in the increase of the overhead message in topology maintenance. Protocols try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control protocol. The clusterhead election is invoked on-demand, and is aimed to reduce the computation and communication costs. A large variety of approaches for ad hoc clustering have been developed by researchers which focus on different performance metrics. This paper presents a survey of different clustering schemes.
I. INTRODUCTION
MANETs use multihop wireless communication without stationary infrastructure, so routing must adapt to changing topology and heterogeneous node resources. Cluster-based routing organizes nodes hierarchically to reduce routing information and overhead.
- MANET nodes communicate through multihop wireless links without base stations, with each node also forwarding packets for others.
- High mobility changes network topology, while flat routing in large networks can generate excessive information that saturates the network.
- Clustering groups nodes into overlapping clusters and records routes between clusters rather than individual nodes.
- Clusterheads coordinate clusters, ordinary nodes access their clusterhead directly, and gateways connect nodes that can hear two or more clusterheads.
- Replacing nodes with clusters allows existing routing protocols to be applied while limiting routing-control propagation to clusterheads and gateways.
II. CLUSTERING ALGORITHMS IN MANET
The paper surveys clustering algorithms developed for mobile ad hoc networks. Its goal is to present the different schemes for organizing and evaluating MANET clusters.
- The paper presents a survey of different clustering algorithms.
2.1 Identifier-based clustering
Identifier-based clustering uses node identifiers and neighbor information to elect clusterheads and assign cluster roles. These schemes can control cluster density, but fixed identifiers may repeatedly burden particular nodes.
- Identifier-based clustering assigns each node an ID and uses neighbor information to choose clusterheads.
- Nodes periodically broadcast the identifiers of nodes they can hear, including themselves.
- A node is a clusterhead when it hears only nodes with higher IDs; other nodes select the lowest-ID node they hear unless that node defers.
- A node hearing two or more clusterheads becomes a gateway; otherwise, it is an ordinary node.
- The Lowest-ID scheme can drain certain nodes because fixed, arbitrary IDs make smaller-ID nodes more likely to serve as clusterheads for longer periods.
- The Max-Min d-cluster algorithm forms clusters extending up to d hops from a clusterhead and limits messages to a multiple of d rather than n.
2.2 Connectivity-based clustering
Connectivity-based schemes select or constrain clusterheads using neighborhood connectivity and cluster size. Their trade-offs include throughput, reaffiliation, overhead, and load balancing under changing topology.
- 2.2.1 Highest connectivity clustering algorithm (HCC): The Highest-degree approach selects the node with the maximum number of neighbors as clusterhead, making cluster members at most two hops apart.
- 2.2.1 Highest connectivity clustering algorithm (HCC): Although the Highest-degree system has a low clusterhead-change rate, its throughput is low and node reaffiliation is high under movement.
- 2.2.2 K-CONID: K-CONID combines connectivity with lower ID as a secondary criterion to reduce ties and the number of clusters, forming clusters within k hops.
- 2.2.2 K-CONID: K-CONID generalizes connectivity from one-hop degree to a k-hop neighborhood, with k = 1 making connectivity equivalent to node degree.
- 2.2.2 K-CONID: Each node broadcasts its clustering decision after higher-priority k-hop neighbors decide; priority is based first on connectivity and then on lowest ID.
- 2.2.3 Adaptive cluster load balance method: Load-balancing clustering uses a threshold to prevent a clusterhead from serving too many mobile hosts.
- 2.2.3 Adaptive cluster load balance method: Adaptive multihop clustering sets upper and lower bounds on cluster members and exchanges cluster information through members, gateways, and clusterheads.
2.3 Mobility-aware clustering
Mobility-aware clustering adapts cluster structure or leadership to node movement, using relative stability, local speed variance, or probabilistic path availability.
- Mobility-metric clustering: Mobility metrics can make d-hop cluster diameter adaptable to node mobility.The approach uses received signal strength to estimate neighbor distance and adjusts clustering accordingly.
- Mobility-metric clustering: Estimated-distance variation and relative mobility are combined to calculate local stability.Physical distance is avoided because transmission power can make physically close nodes appear distant.
- Local-mobility clustering: Low relative speed variance identifies mobile nodes that are less mobile than their neighbors and suitable for clusterhead selection.Aggregate local speed is estimated from variance relative to each neighbor.
- Probabilistic clustering: The (a, t) criteria require paths between every pair of cluster nodes to remain available for time t with probability a.This supports an adaptive architecture that bounds path-availability probability while managing routing overhead.
2.4 Low cost of maintenance clustering
Low-maintenance clustering reduces repeated restructuring by limiting when cluster changes occur, but some schemes still incur global recomputation or gradual cluster fragmentation.
- Least cluster change algorithm: LCC handles clusterhead proximity by requiring one of two nearby clusterheads to relinquish its role.This is one of the stated reclustering cases.
- Least cluster change algorithm: LCC improves cluster stability by removing special local feature requirements for clusterheads.However, a node losing access to every clusterhead can trigger complete cluster-structure recomputation.
- Adaptive clustering: The adaptive scheme forms clusters with one construction broadcast per mobile node.During maintenance, nodes leave or join clusters when same-cluster distance exceeds two hops.
- Adaptive clustering: Without cluster elimination or merging, the adaptive scheme progressively creates more clusters until nearly every node forms a single-node cluster.The stated consequence is disappearance of the cluster structure over time.
- 3-hop between adjacent clusterheads: 3hBAC introduces clusterguest status for nodes outside clusterhead range but within clustermember range.Its maintenance keeps adjacent clusterheads at least two hops apart and avoids ripple effects during reclustering.
- Passive clustering: Passive Clustering avoids dedicated clustering control packets by piggybacking cluster-state decisions on packets sent by mobile nodes.This targets repeated cluster-dependent announcements as a source of control overhead.
2.5 Power-aware clustering
Power-aware clustering addresses energy consumption through service-duration limits, dominating-set reduction, and constrained master–slave assignments, but minimizing dominators does not equal balancing energy use.
- Load-balanced clustering: LBC limits how long a node continuously serves as clusterhead using a configurable duration budget.When the budget expires, the clusterhead resets its virtual ID and relinquishes the role.
- Load-balanced clustering: LBC selects a replacement whose previous total clusterhead service time is shortest in its neighborhood.The scheme uses virtual IDs and states that this should support good energy levels.
- Power-aware connected dominant set: Energy-efficient dominating-set clustering reduces the dominating set by excluding unnecessary clusterheads.Dominating nodes consume additional energy for routing updates and packet relay.
- Power-aware connected dominant set: Minimizing the dominating set does not balance energy consumption between dominating and ordinary nodes.Dominating nodes may therefore deplete their energy faster.
- Master–slave clustering: The master–slave scheme assigns each slave to one master and limits the number of slaves each master can serve.Cluster area is determined by the farthest master–slave distance.
2.6 Combined-weight based clustering
Combined-weight clustering elects clusterheads from multiple mobility, connectivity, distance, power, and position-related metrics, with different schemes targeting overhead, stability, spacing, or energy.
- Weighted clustering algorithm: WCA invokes clusterhead election on mobility or coverage failure rather than periodically, while using a threshold to limit clusterhead load.The selected node is evaluated using mobility, degree, transmission power, and battery power.
- Weighted clustering algorithm: WCA selects the node with minimum weighted cost across degree difference, neighbor distance, mobility, and cumulative clusterhead time.The weighting factors sum to 1; degree difference uses the predefined threshold δ.
- Weighted clustering algorithm: WCA assumes member distances stay within transmission range and prohibits immediate neighboring clusterheads.These conditions define constraints on the resulting cluster structure.
- Entropy-based clustering: High node mobility increases WCA reaffiliation frequency and communication overhead; entropy-based clustering evaluates route stability to address this drawback.Entropy is presented as a measure of uncertainty or disorder associated with network stability and mobility.
- Vote-based clustering: The vote-based scheme combines neighbor count and remaining battery time using weighted location-related factors.Each mobile host exchanges Hello messages and derives its vote from Equation (2).
- Weight-based adaptive clustering: WBACA uses GPS-based position information and prevents one-hop neighboring clusterheads, connecting overlapping clusters through gateways.Its motivation includes avoiding the need for all nodes to know every other node’s weight beforehand.
- Combined-elective metric clustering: CEMCA elects clusterheads using combined mobility, degree, battery-energy, and transmission-range metrics in a distributed process.All nodes have the same opportunity to become clusterheads.
III. CONCLUSION
The survey highlights that hierarchical organization of MANETs must be assessed across stability, overhead, energy, load distribution, and clusterhead fairness.
- The survey identifies cluster structure stability as a central issue in organizing mobile ad hoc networks hierarchically.
- Control overhead must be considered during both cluster construction and maintenance.
- Clustering schemes should account for energy consumption associated with different cluster-related node roles.
- Traffic load distribution within clusters is another issue affecting hierarchical MANET organization.
- Fairness in serving as clusterheads must be considered for mobile nodes.