Evolutionary Games for Correlation-Aware Clustering in Massive Machine-to-Machine Networks

In this paper, the problem of self-organizing, correlation-aware clustering is studied for a dense network of machine-type devices (MTDs) deployed over a cellular network. In dense machine-to-machine networks, MTDs are typically located within close proximity and gather correlated data, and, thus, clustering MTDs based on data correlation leads to a decrease in the number of redundant bits transmitted to the base station. The clustering problem is formulated as an evolutionary game, which models the interactions among a massive number of MTDs, in order to decrease MTD transmission power. A novel utility function that captures the tradeoff between minimizing the average MTD transmission power per cluster and maximizing cluster size (or minimizing signaling overhead) is proposed. To solve this game, a distributed algorithm is proposed to allow a massive number of MTDs to autonomously form clusters. It is shown that the proposed distributed algorithm converges to an evolutionary stable strategy (ESS) that is robust to a small portion of MTDs deviating, e.g., due to some stochastic changes in the M2M environment from the stable cluster formation at convergence. The maximum fraction of MTDs that can deviate from the ESS, while still maintaining a stable cluster formation, is derived. Simulation results show the efficiency of the proposed algorithm in clustering MTDs with highly correlated data: on average, the proposed approach yields reductions of up to 44.1% and 15.25% in terms of the transmit power per cluster, compared to forming clusters with the maximum possible size and uniformly selecting a cluster size, respectively.