Large Wireless Ad Hoc Network Clustering with End-to-End QoS Constraints Using Multiobjective Particle Swarm Optimization

Abstract

To scale for large ad hoc networks containing 
hundreds or even thousands of subnets, the networks must be 
hierarchically organized by partitioning them into clusters or 
domains. Many researchers have proposed partitioning of large 
networks into clusters, but this requires specifying cluster size 
bound. Graph Partitioning (GP) algorithms search for min-cut 
that balances the number of nodes in each partition. The 
limitations of GP algorithms are that they cannot be optimized 
for end-to-end performance requirements or take into account 
the characteristics of network topology. We propose a 
clustering algorithm based on the concept of Multiobjective 
Particle Swarm Optimization (MOPSO). Our algorithm 
minimizes the sum of the total hop count in each cluster and 
minimizes the edge-cut weight between clusters. Further, our 
algorithm provides quality of service (QoS) by taking into 
account end-to-end performance requirements. We find that 
minimizing the sum of the cluster hop count results in a 
balanced and bounded cluster size. For a given number of 
clusters, our clustering algorithm creates clusters with sizes 
closer to average size and avoids isolated nodes. In our study, the 
terms domain, cluster, and partition are used interchangeably.