DISTRIBUTED STOCHASTIC CLUSTERING FOR AUTOMATED FORMATION OF CONNECTED NETWORKS OF AGENTS

摘要

A “Stochastic Clustering-Based Network Generator” enables rapid formation of an interconnected hierarchical network structure from an arbitrary number of agents via an iterative turn-based coalescence process. Given N agents wishing to coalesce into one hierarchical network, a turn-based process allows each agent (or the head of each hierarchical cluster of agents), to randomly decide whether to issue or listen for merge requests in each round. Issuing a request amounts to contacting a randomly chosen agent with a merge request. Given multiple received requests, a cluster head will randomly accept one request for a merge received by any agent in that cluster. The requesting cluster then merges as a hierarchical child of the accepting cluster. In a related embodiment, given multiple merge requests, the request from the smallest cluster is accepted. In further embodiments, ties of the smallest cluster size are broken based on various options.