The Study On Using Distributed Constraint Optimization Problem To Model Target Tracking In Sensor Networks

Distributed Constraint Optimization Problem(DCOP)is an important model for multi-agent coordination and optimization,which has many important features including privacy,locality of information,etc.Recently,considerable research efforts have been made to develop algorithms for solving DCOPs,whereas few investigations have been committed into applications of DCOP.Sensor networks is an important research topic in application of DCOPs.Since it can be modeled by DCOP easily,target tracking problems in sensor networks have received widespread attention.However,there are still some defects in modeling target tracking,such as inaccurate definition to model or lack of physical interpretation.Thus,the paper proposes a DCOP model for target tracking problem which has clear physical interpretation.Moreover,the paper also proposes several algorithms for solving such model.The main contributions are listed as following.(1)This paper reviews related works of target tracking problem in sensor networks,and presents comparison and analysis on two different modelling methods: centralized method and DCOP.Then,the paper presents definitions to DCOPs and constraint graph,and details of DSA and MGM which are two incomplete algorithms for solving DCOPs.Besides,the paper also discusses several DCOP methods for modeling target tracking problem in sensor networks and their advantages and disadvantages.(2)This paper abstracts target tracking problem in sensor networks as multi-graph coloring problem,and proposes two different DCOP methods to model it,i.e.,ACSV and ACMV.In ACSV,each agent controls one variable.Thus,each possible value of a variable is a set of colors rather than a single value.ACMV allows an agent to control several variables,which requires variables not only to consider the external constraints but also to satisfy the internal constraints.Finally,this paper also discusses advantages and disadvantages of two models.(3)This paper proposes two DCOP algorithms based on DSA and MGM for solving multi-graph coloring problem: MGCDSA and MGCMGM.They perform pruning and dimensionality reduction when algorithm is initializing.Pruning can ignore variables which do not have external constraint,while dimensionality reduction can reduce the dimensionality of constraint matrices between two variables.The experimental results show that the two algorithms can solve multi-graph coloringproblems efficiently.(4)We improve the existing DCOPSolver which is a framework for developing DCOP algorithms by adding generating module and parsing module for multi-graph coloring problem,and refining communication logic and result displaying module.