Dynamic multi-dimensional PSO with indirect encoding for proportional fair constrained resource allocation

ABSTRACT

Dynamic particle swarm optimization (PSO) problems are generally characterized by the exhaustively examined issues of the changing location of optima, the changing fitness of optima, and measurement noise/errors. However, the challenging issue of continuously changing problem dimensionality has not been similarly examined. Given that in anytime dynamic resource allocation it is necessary to maintain a high quality solution, we argue that, rather than restarting the PSO algorithm, a more appropriate approach is to design an algorithm that robustly handles changing problem dimensionality. Specifically, we propose an indirect particle encoding scheme specifically designed for a dynamic multi-dimensional PSO algorithm for proportional fair constrained resource allocation. This PSO algorithm is implemented for the proportional fair allocation of power and users to channels within a simulation of an Orthogonal Frequency-Division Multiple Access (OFDMA) wireless network with mobile users switching cells as they traverse the simulation environment. The proposed PSO algorithm is evaluated using simulations, which demonstrate the ability of the proposed indirect encoding scheme to maximize the overall proportional fair optimization goal, without unfairly penalizing the individual components of the solution related to newly introduced problem dimensions.

References

1. "3GPP." Internet: www.3gpp.org, {Jan. 29, 2013}.
2. I. Ahmed and S. Majumder. Adaptive Resource Allocation Based on Modified Genetic Algorithm and Particle Swarm Optimization for Multiuser OFDM Systems. In Proc. ICECE, 211--216, 2008.
3. T. Blackwell. Particle Swarm Optimization in Dynamic Environments. Springer, 2007.
4. S. Borst, M. Markakis, and I. Saniee. Distributed Power Allocation and User Assignment in OFDMA Cellular Networks. In Proc. Allerton, 1055--1063, 2011.
5. F. Brah, L. Vandendorpe, and J. Louveaux. OFDMA Constrained Resource Allocation with imperfect Channel Knowledge. In Proc. COM/VT, 1--5, 2007.
6. A. Carlisle and G. Dozler. Tracking Changing Extrema with Adaptive Particle Swarm Optimizer. In Proc. WAC, vol.13, 265--270, 2002.
7. Chen et. al. Resource Constrained Multirobot Task Allocation with A Leader-Follower Coalition Method . In Proc. IROS, 5093--5098, 2010.
8. X. Hu and R. Eberhart. Adaptive Particle Swarm Optimization: Detection and Response to Dynamic Systems. In Proc. CEC, vol.2, 1666--1670, 2002.
9. T. Ince, S. Kiranyaz, and M. Gabbouj. A Generic and Robust System for Automated Patient-Specific Classification of Electrocardiogram Signals. IEEE Trans. Bio-Med. Eng., 56(5):1415--1426, May 2009.
10. J. Kennedy and R. Eberhart, "Particle Swarm Optimization," in Proc. ICNN, 1995, pp. 1942--1948.
11. Z. Liang, Y. Chew, and C. Ko. Decentralized Bit, Subcarrier and Power Allocation with Interference Avoidance in Multicell OFDMA Systems using Game Theoretic Approach. In Proc. MILCOM, 1--7, 2008.
12. Y. Liu, K. Han, and D. Zhang. Consumer Sharing Policy Constrained Resource Allocation Method for Grid System . In Proc. ISCIT, 721--725, 2009.
13. A. Nickabadi, M. Ebadzadeh, and R. Safabakhsh. DNPSO: A Dynamic Niching Particle Swarm Optimizer for Multi-Modal Optimization. In Proc. CEC, 26--32, 2008.
14. D. Parrott and X. Li. A Particle Swarm Model for Tracking Multiple Peaks in a Dynamic Environment using Speciation. In Proc. CEC, vol.1, 98--103, 2004.
15. K. Parsopoulos and M. Vrahatis. Recent approaches to global optimization problems through Particle Swarm Optimization. Natural Computing, 1:235--306, 2002.
16. S. Sadeque, I. Ahmed, and R. Vaughan. Impact of Individual and Joint Optimizations in Multi-user OFDM Resource Allocation by Modified PSO. In Proc. CCECE, 1233--1237, 2011.
17. Sharma et. al. On the use of particle swarm optimization for adaptive resource allocation in orthogonal frequency division multiple access systems with proportional rate constraints. Info. Sci., 182(1):115--124, 2012.
18. T. Starr, J.M. Cioffi, P.J. Silverman. Understanding Digital Subscriber Line Technology. Prentice Hall PTR, 1999.
19. D. Tse, P. Viswanath. Fundamentals of Wireless Communications. Cambridge University Press, 2004.
20. H. Wang, D. Wang, and S. Yang. Triggered Memory-Based Swarm Optimization in Dynamic Environments. In Proc. the EvoCOP, 637--646, 2007.
21. Y. Wang, F. Chen, and G. Wei. Adaptive Subcarrier and Bit Allocation for Multiuser OFDM System Based on Genetic Algorithm. In Proc. ICC, vol.1, 242--246, 2005.
22. S. Yang. Population-Based Incremental Learning with Memory Scheme for Changing Environments. In Proc. the GECCO, 711--718, 2005.
23. S. Yang and X. Yao. Population-Based Incremental Learning With Associative Memory for Dynamic Environments. IEEE Trans. Evol. Comput., 542--561, October 2008.
24. Y. Yi, Z. Yu, and W. Ye. Modified Particle Swarm Optimization and Genetic Algorithm Based Adaptive Resources Allocation Algorithm for Multiuser Orthogonal Frequency Division Multiplexing System. Information Technology, 10(5):955--964, 2011.
25. Young et. al. Energy-Constrained Dynamic Resource Allocation in a Heterogeneous Computing Environment. In Proc. ICPPW, 298--307, 2011.
26. S. Zilberstein and S. Russell. Approximate Reasoning Using Anytime Algorithms. In S. Natarajan, editor, Imprecise and Approximate Computation, 43--62. Springer US, 1995.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Networks

  • Network protocols

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization