Research On Coalition Structure Generation In OCF Games

As one of the important research directions of distributed artificial intelligence,agent theory and technology have been applied in various applications that computer supported in recent years.The core research content of agent theory is multi-agent system(MAS),which provides a cooperation mode called coalition for internal independent agents.In this mode,agents can spontaneously form coalitions and allocate some resources to jointly complete the same task,thereby improving the task completion efficiency and personal benefits.As a key research content of MAS,coalition structure generation(CSG)problem mainly studies how to form an efficient and stable coalition between agents,so as to maximize the benefits of agents in system.Against this background,this dissertation studies the CSG problem in overlapping coalition formation(OCF)games,which also known as the OCSG problem.The CSG problem of traditional game assumes that each agent can only participate in one coalition,which means that no matter how many resources are left,the agent can only put all resources into one task.This assumption will not only waste resources,but also affect the benefit of agent and system,which cannot meet the actual needs.The OCF games remove this limitation.Each agent chooses to join multiple different coalitions according to the number of resources it can allocate,which can not only effectively solve the problem of resource and benefit allocation in the application,but also improve the resource utilization of the system and the efficiency of task completion.The main research contents of this dissertation are as follows:(1)Propose an OCSG algorithm based on monotonic 6)OCF games(OCF games with constraint on the maximum number of coalitions 6)).For the difficult problem of OCSG calculation,this dissertation uses 6)OCF games to reduce the search space of the problem.Then a similarity measure is introduced to weigh the similarity between any two coalition structures,and the monotonicity of 6)OCF games is defined.Finally,for 6)OCF games with this property,the coalition constrained greedy(CCG)algorithm is designed to solve the given OCSG problem.It is proved by theoretical analysis and experimental results that the CCG algorithm is solvable with fixed parameters and has better applicability.(2)Propose a resource allocation algorithm for device-to-device(D2D)system based on coalition interference value constraint.For the resource allocation and interference coordination problem in the D2 D communication,a special OCF game model is used to transform the problem into solving the OCSG problem,thereby design the coalition interference value constraint(CIVC)algorithm.With the goal of maximizing the throughput of the D2 D system,the algorithm improves the system performance as much as possible while ensuring the quality of service for each user.At the same time,the algorithm introduces the concept of coalition interference value to measure the interference level between the D2 D links and the cellular users,and a new D2 D switching scheme is designed to autonomously coordinate the interference level between user equipments in the system.Compared with other algorithms,the CIVC algorithm has higher performance and efficiency.