Distributed Load Balancing Algorithm in Wireless Networks

Abstract

As communication networks scale up in size, complexity and demand, effective distribution of the traffic load throughout the network is a matter of great importance. Load balancing will enhance the network throughput and enables us to utilize both communication and energy resources more evenly through an efficient redistribution of traffic load across the network. This thesis provides an algorithm for balancing the traffic load in a general network setting. Unlike most of state-of-the-art algorithms in load balancing context, the proposed method is fully distributed, eliminating the need to collect information at a central node and thereby improving network reliability. The effective distribution of load is realized through solving a convex optimization problem where the p-norm of network load is minimized subject to network physical constraints. The optimization solution relies on the Alternating Direction Method of Multipliers (ADMM), which is a powerful tool for solving distributed convex optimization problems. A three-step ADMM-based iterative scheme is derived from suitably reformulated form of p-norm problem. The distributed implementation of the proposed algorithm is further elaborated by introducing a projection step and an initialization setup. The projection step involves an inner-loop iterative scheme to solve linear subproblems. In a distributed setting, each iteration step requires communication among all neighboring nodes. Due to high energy consumption of node-to-node communication, it is most appealing to devise a fast and computationally efficient iterative scheme which can converge to optimal solution within a desired accuracy by using as few iteration steps as possible. A fast convergence iterative scheme is presented which shows superior convergence performance compared to conventional methods. Inspired by fast propagation of waves in physical media, this iterative scheme is derived from partial differential equations for propagation of electrical voltages and currents in a transmission line. To perform these iterations, all nodes should have access to an acceleration parameter which relies on the network topology. The initialization stage is developed in order to overcome the last challenging obstacle toward achieving a fully distributed algorithm.