Minimal agents matchmaking: multi-agents collective layer in grids using area dominating sets and routing indices

Abstract

This document examines the combination of various techniques, concerning multi-agent systems, sensor networks and peer to peer (P2P) networks in order to improve matching times between a consumer and a producer in distributed systems. This thesis concentrates on the consumer/producer matchmaking problem in which each producer provides more than one and less than five resources and each consumer requests only one amount of one resource. Thus the consumer has one task to execute. The producers and consumers are integrated in the grid environment and are assigned to represent nodes in the network that are either asking for resources or are able to provide some of them. The matching of the nodes that provide resources and the ones that consume a resource is formed by simulating the grid network to a multi-agent system that performs matchmaking.Apart from using Routing Indices to find routes for a message, we also borrow a technique originated by sensor networks that actually minimizes, having to consider a number of constraints, the number of nodes that must hold such indices in the network. This technique is called Area Dominating Set and it is widely used in sensor networks. Its main advantage is that it determines a dominating set formed by a small fraction of the whole amount of nodes in the network. These gateway nodes are also called dominant nodes and their usage is to reduce communication complexity by representing their non-dominant neighbors to the other dominant nodes in the network. Therefore, all messages are propagated by the gateways and the non-gateways are basically terminal points in the network. Due to the nature of this technique, we have simplified the algorithm, so that the geographical information needed in order to form the set of each node’s neighbors have been eliminated from the algorithm for the formation of the Area Dominating Set and have been substituted by the assumption that only one-hop neighbors exist.The thesis presents the algorithms implemented in great detail and provides results from matchmaking experiments. These results reveal the advantages of the methods exploited towards solving the matchmaking problem in various settings of consumer and producer nodes.