Efficient Allocation of Hierarchically-Decomposable Tasks in a Sensor Web Contract Net

In large, distributed systems, such as a sensor web, allocating resources to tasks that span multiple providers presents significant challenges. Individual subtasks associated with a task could potentially be assigned to a number of agents (e.g., when there is overlap in sensor or data processing capability among constituent sensor networks). This problem is further compounded by the dynamic nature of a sensor web, in which both desired tasks and resource availability change with time and environmental conditions. This paper presents a novel variation of the contract net protocol (CNP) for subtask allocation, which employs brokers to limit communication overhead in a two-phase CNP and aggregate domain information from groups of agents. Experimental results using this subtask allocation approach verify its efficiency and scalability. These results also suggest specific refinements and appropriate parameters for a variety of system configurations and operating conditions in sensor webs and other large multi-agent systems.