In wireless networks, some of the most important supporting functionalities are decentralized resource sharing and association of clients to access points. These functionalities aim to optimally allocate the available wireless transmission resources, for example, time or spectrum channels, the transmit power, access points, and relaying opportunities, all of which are subject to availability constraints. Decentralized resource sharing and association are designed by a common background theory: optimization problems that are non-convex with mixed integer-real variables, and need to be solved by distributed algorithms over the network nodes. The thesis investigates these optimization problems and establishes novel solution methods based on auction and Lagrangian duality theories. The thesis is divided into two parts: in the first part, the theoretical background of the thesis is given, and novel results on distributed auction theory are established to solve a class of optimization problems with integer variables. These theoretical background and novel results are then used in the second part of the thesis, where published or submitted papers are reported. Specifically, novel solution methods for distributed optimization problems with mixed integer-real variables are in- vestigated for resource sharing and association problems in cognitive radio networks, and in millimeter wave networks.
In the first paper (J1), a non-convex optimization problem with mixed integer and real variables is considered for resource allocation in a cognitive radio network. In this network, unlicensed secondary users can maximize their achievable transmit rates by cooperating with licensed primary users. An optimization problem to maximize the secondary users achievable rates is proposed by controlling the transmit radio power, the secondary users relaying selection, and power splitting of the relays, while guaranteeing primary users performance. A novel distributed solution method is developed to find the solution to such a challenging mixed integer and non-convex problem. The method provides a distributed algorithm for finding the optimal power allocations for secondary users, and a greedy distributed algorithm for finding the associations between primary and secondary users. Optimality and convergence of the solution method are investigated. The numerical results illustrate the performance of the proposed solution methods, and show that they give a near-to-optimal solution.
In the second paper, the solution methods investigated in the first paper are used for mixed integer-real optimization problems in millimeter wave networks. These networks are emerging to enable extremely high data rates wireless communications. The main limiting factors of millimeter wave networks are communication blockage (due to high penetration loss of the transmit signals) and deafness (misalignment between the antenna’s beams of the transmitter and receiver). To minimize these limiting factors, it is imperative to design efficient association between clients and access points. Therefore, a general optimization framework to maximize network throughput considering both blockage and deafness is proposed. The optimization framework considers static networks (i.e., no client mobility) and investigates a novel distributed auction based solution, where the clients and access points act asynchronously to achieve optimal association along with the optimal beamwidth of the antennas. A convergence proof and optimality of the auction algorithm are analyzed.
The optimization framework investigated in the second paper was intended for static networks. In networks with dynamic topologies and channel variations, the dynamic appearance of obstacles or of small misalignments between antenna beams of the transmitters and receivers may trigger the reexecution of the association mechanism, which is time consuming and may be inefficient. This challenge is addressed in the third paper by dynamic distributed association techniques that are robust to wireless channel variations and client mobility. The association problem is formulated as a mixed-integer optimization problem aiming to maximize the network throughput with proportional fairness guarantees. This optimization problem is solved by a distributed dual decomposition algorithm, and by a novel dynamic distributed auction algorithm. A distinguishing novel feature of the proposed algorithms is that the resulting optimal association does not have to be re-computed every time the network changes (e.g., due to client mobility). Instead, it is proved that the algorithm continuously adapts to the network variation and is thus capable to continuously track the optimal solutions. It is shown that the proposed algorithm provably converges to a solution that maximizes the aggregate network utility within a desired bound.
The previous line of research is then extended to the case where, in addition to designing the association clients-access points, also relays nodes are considered. The association of clients to relaying nodes can provide more uniform quality of service by offering robust millimeter waves connection, load balancing, coverage extension, indoor-outdoor coverage, efficient mobility management, and smooth handover operations. The challenges of clientrelay-access point association are addressed in a sequence of two contributions having different optimization goals: the first one considers the throughput maximization, and the second one the load balancing. In the first contribution (presented in the fourth paper of the thesis), a distributed optimization that solves the joint client association and relaying problem is investigated for the throughput maximization. The optimization problem is posed as a novel multi-dimension assignment optimization, for which an original solution method is established by a series of transformations together with a distributed auction solution algorithm. In the second contribution (presented in the fifth paper of the thesis), the joint association and relaying problem is posed as a novel stochastic optimization problem considering the load balancing, and the resource sharing at access points. The problem is solved by a distributed auction algorithm where the clients and relays act asyn- chronously to quickly achieve optimal association. The convergence time and performance bounds of the algorithm are derived in closed-forms. Numerical results quantify the performance enhancements introduced by the relays, and the substantial improvements of the network throughput and fairness among the clients by the proposed association methods compared to existing approaches.
The common thread in the line of research reported in the papers of the thesis is given by the solution methods of mixed integer optimization problems that must be solved in a distributed manner. The core result of the thesis is a novel distributed approach, based on the auction theory, for the computation of the solution of a class of optimization problems. It is shown that such an approach can work in static and dynamic network topologies and exhibits convergence and optimality guarantees by leveraging the specific assumptions of the problems’ constraints. Future study could extend the proposed distributed auction method for more general optimization problems for association, such as generalized assignment problems.
Stockholm: KTH Royal Institute of Technology, 2016. , xxi, 41 p.