Research On Distributed Algorithm Based On Markov Approximation For Combinatorial Network Optimization

The rapid development of IoT and 5G-network brings many network problems,such as resource scarcity and load imbalance and so on.Therefore,network optimization has become a research focus in communication field.The goal of network optimization is to effectively manage and control the network system by designing a reasonable algorithm,so as to optimize the system performance.Many important network optimization problems are fundamentally combinatorial optimization problems,which belong to NP-hard problems.It is quite difficult to solve with the expansion of the network scale.Furthermore,the dynamic changes of the network environment also brings great challenges to network optimization.In the paper,we study two problems in network optimization by designing distributed dynamic algorithms: TV white spectrum allocation problem and AP association problem.The main research contents are as follows:Spectrum resource allocation has a great impact on the overall performance of the network system and has attracted a wide spread attention.Unlike the traditional WiFi spectrum,TV white spectrum varies with time and space,namely temporal variation and spatial variation.How to allocate TV white spectrum to secondary users by taking the spatial and temporal variation into consideration is a research challenges.In this paper,we first formulate the TV spectrum allocation problem as a 0-1 integer programming problem,and then we approximate the optimal objective via Log-Sum-Exp function.Thereafter,a distributed allocation algorithm for TV white spectrum is designed to solve this problem using Markov approximation technology.Moreover,we extend the proposed algorithm to a dynamic environment in order to address the problem of TV white spectrum changing due to the random arrivals and departures of primary users.Simulation results show that our proposed distributed algorithm can converge very fast to the optimal solution.In the network,some APs are overloaded with too many associated users,while other APs remain underutilized.In this case,how to choose an appropriate AP plays a very important role in network design.We first approximate the optimal objective viaLog-Sum-Exp function.Thereafter,we construct a special class of Markov Chain with steady-state distribution specify to the problem to yield a distributed solution.Furthermore,we extend the distributed algorithm to a dynamic algorithm to adapt the dynamic change of users on the network.The approximate gap between the approximate solution and the optimal solution is obtained by theoretical analysis.Finally,simulation experiments verify the effectiveness and convergence of the proposed algorithm.