Distributed Resource Allocation In Multi-agent Systems

The resource allocation problem in multi-agent systems is to maximize the benefit of the whole network by reallocating network resource.Traditional centralized algorithms are hard to perform well in large-scaled networks due to their low scalability and reliability,high requirement of synchronization.Moreover,in centralized networks,the center takes all burdens of computation.If the center breaks down,the whole system cannot work any more.This research studies the distributed resource allocation algorithms in multi-agent systems,solving the problem of decentralizing the global deviation in distributed resource allocation problems by local estimation.Based on this method,some algorithms which converge to the optimal solution linearly and are applicable to general smooth convex functions are proposed.We analyze their convergence,focusing on convergence rate and accuracy.Moreover,we study distributed resource allocation with unreliable communication networks,including the convergence of the algorithm under stochastic networks and uncoordinated stepsizes,and differential privacy of cost functions under communication eavesdropping.This improves the performance of algorithms under unreliable communication networks,maintaining the efficiency,stability and security of networked systems.The main works and contributions of this dissertation are as follows:1.For the problems of eliminating and decentralizing the global imbalance of resource in distributed resource allocation problems,we propose the distributed deviation tracking method to decentralize the global imbalance by local estimate.Combining this method with the weighted gradient method,we propose a distributed unconstrained resource allocation algorithm.This algorithm is applicable to general smooth convex functions.We prove that this algorithm converges to the optimal solutions linearly and verify the theoretical results with numerical simulations of the economic dispatch problem.2.For the problem that the gradients of all agents are not equal when achieving optimal solution of distributed constrained resource allocation.We introduce a new variable,i.e.,the expected gradient,to transform the condition of the optimal solution into the consensus of expected gradients.Then,we propose a distributed constrained resource allocation algorithm based on weighted expected gradients method and distributed deviation tracking method.We prove the algorithm converges to the optimal solution linearly with a constant stepsize.Compared with an existing algorithm,the proposed algorithm converges at a higher rate.3.For the random failure of communication links,we establish a distributed stochastic network and propose an approach of reassigning the weight matrix to maintain the matrix doubly stochastic.Based on stochastically weighted gradient method,we propose a distributed resource allocation algorithm that is applicable to stochastic networks.The algorithm is proved to converge to the optimal solution linearly in mean square sense.Moreover,due to the difficulty of coordinate all agents’ stepsizes in stochastic networks,we study the convergence of the algorithm with uncoordinated stepsizes.The algorithm is proved to converge to the optimal solution even with uncoordinated stepsizes.We verify the convergence in stochastic networks with numerical simulations of the economic dispatch problem.4.For the problem of the potential communication intercept,we design a differentially private distributed resource allocation algorithm.First,we prove the limit of state perturbation,i.e.,distributed algorithm cannot converge and preserve differential privacy simultaneously with only state perturbation.Based on this conclusion,we propose the state and direction perturbation methods.Combining this with the deviation tracking method,we propose a differentially private distributed resource allocation algorithm,proving this algorithm converges linearly in mean square sense and preserves differential privacy of all agents’ functions.Then,we obtain the trade-off between convergence accuracy and differential privacy based on the relation between accuracy and noise.We simulate the behaviors of attackers in smart grid,calculate the level of differential privacy and study the relation between the convergence accuracy and differential privacy,validating the feasibility of the proposed algorithm.