A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters
Nodes in an ad hoc network are usually organized into clusters, with each cluster being coordinated by a node acting as the cluster head (CH). Cluster members are one hop away from their CH. The collection of CHs give rise to a graph structure known as a dominating set. This paper proposes a hybrid...
| Main Authors: | , |
|---|---|
| Format: | Book Section |
| Language: | English |
| Published: |
IEEE Xplore
2005
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/2334/ http://shdl.mmu.edu.my/2334/1/A%20hybrid%20ant%20colony%20optimization%20approach%20%28hACO%29%20for%20constructing%20load-balanced%20clusters.pdf |
| _version_ | 1848790028563513344 |
|---|---|
| author | Ho, C. K. Ewe, H. T. |
| author_facet | Ho, C. K. Ewe, H. T. |
| author_sort | Ho, C. K. |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | Nodes in an ad hoc network are usually organized into clusters, with each cluster being coordinated by a node acting as the cluster head (CH). Cluster members are one hop away from their CH. The collection of CHs give rise to a graph structure known as a dominating set. This paper proposes a hybrid ACO (hACO) approach that, when given a graph representing a network, selects a set of CHs in such a way that enables the remaining nodes to be distributed as evenly as possible to these CHs while ensuring that the maximum load a CH can take is maintained. Artificial ants are used to select the CHs. After a CH is selected, a heuristic is used to determine cluster member assignment. Solution quality is measured using a metric called the load balancing factor (LBF). We benchmark the performance of the hACO against a recently proposed genetic algorithm (GA) that addresses the same problem. Empirical results point to the fact that hACO consistently produced good solutions across the 41 problem instances. Even though GA gave the best solutions for several instances, its performance deteriorated for graphs with relatively higher density. We explain this behavior by examining the clusters produced by both methods. |
| first_indexed | 2025-11-14T18:06:06Z |
| format | Book Section |
| id | mmu-2334 |
| institution | Multimedia University |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:06:06Z |
| publishDate | 2005 |
| publisher | IEEE Xplore |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-23342013-12-06T00:16:39Z http://shdl.mmu.edu.my/2334/ A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters Ho, C. K. Ewe, H. T. QA75.5-76.95 Electronic computers. Computer science Nodes in an ad hoc network are usually organized into clusters, with each cluster being coordinated by a node acting as the cluster head (CH). Cluster members are one hop away from their CH. The collection of CHs give rise to a graph structure known as a dominating set. This paper proposes a hybrid ACO (hACO) approach that, when given a graph representing a network, selects a set of CHs in such a way that enables the remaining nodes to be distributed as evenly as possible to these CHs while ensuring that the maximum load a CH can take is maintained. Artificial ants are used to select the CHs. After a CH is selected, a heuristic is used to determine cluster member assignment. Solution quality is measured using a metric called the load balancing factor (LBF). We benchmark the performance of the hACO against a recently proposed genetic algorithm (GA) that addresses the same problem. Empirical results point to the fact that hACO consistently produced good solutions across the 41 problem instances. Even though GA gave the best solutions for several instances, its performance deteriorated for graphs with relatively higher density. We explain this behavior by examining the clusters produced by both methods. IEEE Xplore 2005-09 Book Section NonPeerReviewed text en http://shdl.mmu.edu.my/2334/1/A%20hybrid%20ant%20colony%20optimization%20approach%20%28hACO%29%20for%20constructing%20load-balanced%20clusters.pdf Ho, C. K. and Ewe, H. T. (2005) A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters. In: The 2005 IEEE Congress on Evolutionary Computation, 2005. IEEE Xplore, pp. 2010-2017. ISBN 0-7803-9363-5 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1554942 10.1109/CEC.2005.1554942 10.1109/CEC.2005.1554942 10.1109/CEC.2005.1554942 |
| spellingShingle | QA75.5-76.95 Electronic computers. Computer science Ho, C. K. Ewe, H. T. A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title | A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title_full | A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title_fullStr | A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title_full_unstemmed | A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title_short | A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters |
| title_sort | hybrid ant colony optimization approach (haco) for constructing load-balanced clusters |
| topic | QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/2334/ http://shdl.mmu.edu.my/2334/ http://shdl.mmu.edu.my/2334/ http://shdl.mmu.edu.my/2334/1/A%20hybrid%20ant%20colony%20optimization%20approach%20%28hACO%29%20for%20constructing%20load-balanced%20clusters.pdf |