Evolutionary coalitional game for correlation-aware clustering in machine-to-machine communications

Abstract

In this paper, the problem of correlation-aware clustering is studied for a dense network of machine-type devices (MTDs) deployed over a cellular network. In such dense networks, MTDs sense an environment and transmit their data to the base station (BS) via a cellular uplink. However, since MTDs are typically closely located to each other they will gather correlated data, and, thus, large amounts of redundant bits can be transmitted to the BS. To address this problem, an evolutionary coalitional (EC) game is proposed to cluster MTDs into coalitions in a fully distributed and autonomous manner, based on the correlation of their data. The proposed EC game allows a reduction in the number of redundant bits being sent to the BS, while also reducing the energy used for transmission by each MTD. To solve the EC game, a distributed coalition formation algorithm is proposed and shown to reach an evolutionary stable coalition structure, which is robust to a small portion of MTDs changing their strategy at the stable outcome. For this game, the maximum portion of MTDs that can deviate from the stable coalitional structure is derived. Simulation results show that the proposed approach can effectively cluster MTDs with highly correlated data which, in turn, enables those MTDs to eliminate a large number of redundant bits. Moreover, the results show that, for a given maximum correlation factor and network density, the transmission energy per MTD can be decreased by 19%, compared to a baseline merge-and-split algorithm. In addition, when a maximum correlation factor is considered, the number of redundant bits that can be eliminated per coalition is increased by 50%, compared to the merge-and-split algorithm. Show more