Research And Application Of Distributed Constraint Optimization Algorithm

With the development of hardware and network technique,as well as the application of distributed computation,distributed constraint optimization problem(DCOP),as an essential framework of the multi-agent system,has attracted considerable attention.Nowadays,the research of DCOP is broadly classified into three modules,including modeling module,algorithm module,and application module.In the modeling module,the traditional DCOP framework is heavily depended on the assumption of symmetric constraints between agents.Besides,the framework limits the application of DCOP under the dynamic environment.In the algorithm module,DCOP algorithms are divided into complete and incomplete algorithms.Complete ones focus on searching the global optimal solution with large amounts of consumption of computing and communication resources,whereas incomplete ones are able to cut down on resource consumption with the sacrifice of the quality of obtained solution.Generally speaking,the solution solved by an incomplete algorithm is named sub-optimal solution.Due to the advantages of incomplete algorithms,they are applied for solving DCOP composed of large amounts of agents,constraints,etc.In the application module,the real world problems are generally transformed into multi-agent systems,then modeled by the DCOP framework and solved by an appropriate DCOP algorithm.Based on aforementioned three modules,this dissertation develops the research of DCOP from the point of the view of model applicability,the efficiency of DCOP algorithms and the application of DCOP.Further,we verify our proposed algorithms and applications using the experiments and simulation.More precisely,the main contribution of this dissertation is as follows:1)Firstly,this dissertation surveys the state-of-the-art approaches of DCOP algorithms.From the review,this dissertation provides the modeling methods of DCOP,and analyzes the DCOP applicability.After that,the author summarizes the general procedure of solving the DCOP according to the existing approaches.Based on such procedure,DCOP algorithms are classified into multiple categories from the perspectives of the quality guarantee of the solutions and strategies used for solving DCOP.At last,the problems embedded in current DCOP research are proposed and regarded as the research directions during the Ph.D.study.2)As for the asymmetric DCOP(ADCOP),which is a modified version of the traditional DCOP model,existing DCOP algorithms are hardly used for obtaining the solution.To solve this problem,this dissertation firstly proposes a reduplicate obfuscation mechanism with which the payoff information from different agents connected by the same constraint can be effectively protected.Thus,the privacy of an agent can not be known or inferred by the others.With the aid of such mechanism,the author proposed two ADCOP algorithms,namely AsyDPOP(Asymmetric Distributed Pseudo-tree Optimization Procedure)and AsyDALO(Asymmetric Distributed Asynchronous Local Optimization).The latter one not only provides a theoretical guarantee of obtained solution but at what levels,can protect the privacy of agents.3)Through analyzing the efficiency of MULBS(Multiple local bound search)algorithms,the dissertation proposes a modified version,named MULBS+.The difference between MULBS and MULBS+ relies on two aspects.On the one hand,a minimal conflict selection mechanism is used in MULBS+ instead of the search strategy in MULBS.On the other hand,MULBS+ exploits a global parallel search strategy based on dynamic graph-partitioning which can quickly converge to a stable solution Experiments show that the proposed algorithm is better than the original one no matter in the perspective of running time or the quality of the solution.Particularly,the performance has a large improvement when the constraint graph density of a DCOP is large.4)In the matter of the research of incomplete algorithm,this dissertation proposes a local stability supported parallel search algorithm,LSPA.Firstly,the author introduces the definition of local stability supported which is used to estimate the cost if there is the variation of the assignment of a variable.Then,LSAP is able to quickly converge to a stable solution using a reliable initial solution according to the strategy proposed in the dissertation.In order to execute the parallel search,LSPA constantly computes local stability of compatible agents.Experiments show that LSPA outperforms some of the state-of-the-art incomplete DCOP algorithms.5)To solve the user association problem in the heterogeneous networks.This dissertation investigates how to model the problem as a DCOP from the view of the point of the multiagent system.Hereinafter,we propose a DCOP solver which not only sets up the model in a distributed way but also enables us to efficiently obtain the solution by means of a complete DCOP algorithm.Both theoretical analysis and simulation show that different qualitative solutions can be obtained in terms of an introduced parameter ? in the model.It is also apparent that there is 6%improvement in the throughput by the DCOP solver comparing with other counterparts.Particularly,it demonstrates up to 18%increase in the ability to make BSs serve more users when the number of users is above 200 while the available resources are limited.