Distributed Task Assignment Based on Gossip with Guaranteed Performance on Heterogeneous Networks**The research leading to these results has received funding from Region Sardinia, LR 7/2007 (call 2010) under project SIAR (CRP24709) and from Italian grant SIR “Scienti_c Independence of young Researchers”, project CoNetDomeSys, code RBSI14OF6H, funded by the Italian Ministry of Research and Education (MIUR).

摘要

In this paper we propose a novel distributed algorithm for task assignment on heterogeneous networks. We consider a set of tasks with heterogeneous cost to be assigned to a set of nodes with heterogeneous execution speed and interconnected by a network with unknown topology represented by an undirected graph. Our objective is to minimize the execution time of the set of tasks by the networked system. We propose a local interaction rule which allows the nodes of a network to cooperatively assign tasks among themselves with a guaranteed performance with respect to the optimal assignment exploiting a gossip based randomized interaction scheme. We characterize the convergence properties of the proposed approach and provide simulation results.