Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks
This paper presents three ant colony optimization (ACO) approaches for a difficult graph theoretic problem formulated from the task of computing load-balanced clusters in ad hoc networks. These three approaches contain novel strategies for adapting the search process to the new problem structure whe...
| Main Authors: | , |
|---|---|
| Format: | Book Section |
| Language: | English |
| Published: |
IEEE
2007
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/3181/ http://shdl.mmu.edu.my/3181/1/Ant%20Colony%20Optimization%20Approaches%20for%20the%20Dynamic%20Load-Balanced%20Clustering%20Problem%20in%20Ad%20Hoc%20Networks.pdf |
| _version_ | 1848790256488284160 |
|---|---|
| author | Ho, Chin K. Ewe, Hong T. |
| author_facet | Ho, Chin K. Ewe, Hong T. |
| author_sort | Ho, Chin K. |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | This paper presents three ant colony optimization (ACO) approaches for a difficult graph theoretic problem formulated from the task of computing load-balanced clusters in ad hoc networks. These three approaches contain novel strategies for adapting the search process to the new problem structure whenever an environment change occurs. An environment change occurs when nodes in the network move. Dynamic changes in problem structure pose a great challenge for ACO algorithms because the pheromone information is rendered inaccurate and inconsistent. Hence, all three strategies to enable ACO to work in a dynamic setting have a common objective, that is, to adapt the pheromone information to closely reflect the new problem structure. The first approach is the population-based ACO algorithm (P-ACO) that incorporates a novel solution repair procedure. The second approach, which we call PAdapt, works by adapting three major algorithm parameters following an innovative strategy. The third approach, which we term GreedyAnts, uses a greedy solution construction strategy to bias the pheromone information towards the new problem structure. Empirical results show that GreedyAnts is very competitive with P-ACO, while PAdapt is less impressive. The GreedyAnts approach is advantageous over P-ACO because it does not require a solution repair heuristic that incurs additional processing. |
| first_indexed | 2025-11-14T18:09:43Z |
| format | Book Section |
| id | mmu-3181 |
| institution | Multimedia University |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:09:43Z |
| publishDate | 2007 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-31812013-11-15T04:13:13Z http://shdl.mmu.edu.my/3181/ Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks Ho, Chin K. Ewe, Hong T. T Technology (General) QA75.5-76.95 Electronic computers. Computer science This paper presents three ant colony optimization (ACO) approaches for a difficult graph theoretic problem formulated from the task of computing load-balanced clusters in ad hoc networks. These three approaches contain novel strategies for adapting the search process to the new problem structure whenever an environment change occurs. An environment change occurs when nodes in the network move. Dynamic changes in problem structure pose a great challenge for ACO algorithms because the pheromone information is rendered inaccurate and inconsistent. Hence, all three strategies to enable ACO to work in a dynamic setting have a common objective, that is, to adapt the pheromone information to closely reflect the new problem structure. The first approach is the population-based ACO algorithm (P-ACO) that incorporates a novel solution repair procedure. The second approach, which we call PAdapt, works by adapting three major algorithm parameters following an innovative strategy. The third approach, which we term GreedyAnts, uses a greedy solution construction strategy to bias the pheromone information towards the new problem structure. Empirical results show that GreedyAnts is very competitive with P-ACO, while PAdapt is less impressive. The GreedyAnts approach is advantageous over P-ACO because it does not require a solution repair heuristic that incurs additional processing. IEEE 2007-04 Book Section NonPeerReviewed text en http://shdl.mmu.edu.my/3181/1/Ant%20Colony%20Optimization%20Approaches%20for%20the%20Dynamic%20Load-Balanced%20Clustering%20Problem%20in%20Ad%20Hoc%20Networks.pdf Ho, Chin K. and Ewe, Hong T. (2007) Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks. In: IEEE Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, pp. 76-83. ISBN 1-4244-0708-7 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4223158 doi:10.1109/SIS.2007.368029 doi:10.1109/SIS.2007.368029 |
| spellingShingle | T Technology (General) QA75.5-76.95 Electronic computers. Computer science Ho, Chin K. Ewe, Hong T. Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title | Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title_full | Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title_fullStr | Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title_full_unstemmed | Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title_short | Ant Colony Optimization Approaches for the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks |
| title_sort | ant colony optimization approaches for the dynamic load-balanced clustering problem in ad hoc networks |
| topic | T Technology (General) QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/3181/ http://shdl.mmu.edu.my/3181/ http://shdl.mmu.edu.my/3181/ http://shdl.mmu.edu.my/3181/1/Ant%20Colony%20Optimization%20Approaches%20for%20the%20Dynamic%20Load-Balanced%20Clustering%20Problem%20in%20Ad%20Hoc%20Networks.pdf |