Distributed C-Means Clustering Via Broadcast-Only Token Passing

摘要

This paper provides an implementation of the $C$-means algorithm in an asynchronous and distributed fashion; specifically, we consider a network of agents, each provided with a piece of information (e.g., data acquired via sensors) and we partition the agents in not mutually exclusive sets such that agents in the same set have similar information; moreover, each set of agents calculates a representative value for the group. Previous distributed algorithms that aimed at accomplishing this task have nontrivial demands, in that they require point-to-point communication capabilities among the agents, which may need to exchange large amounts of data in order to execute their computations. Within the proposed approach, instead, the agents need no prior knowledge about their neighbors and can simply communicate using broadcasts. The proposed solution consists in organizing data transmission following a token-passing approach, thus limiting the communication effort with respect to synchronous distributed implementations; furthermore, the token-passing phase is implemented via the broadcast-only communication, thus avoiding the requirements of the point-to-point communication. As shown via simulations, the latter feature is obtained at the cost of a modest increase in data transmission with respect to a traditional point-to-point token-passing scheme.