A game theoretical approach to clustering of ad-hoc and sensor networks

Game theory has been used for decades in fields of science such as economics and biology, but recently it was used to model routing and packet forwarding in wireless ad-hoc and sensor networks. However, the clustering problem, related to self-organization of nodes into large groups, has not been studied under this framework. In this work our objective is to provide a game theoretical modeling of clustering for ad-hoc and sensor networks. The analysis is based on a non-cooperative game approach where each sensor behaves selfishly in order to conserve its energy and thus maximize its lifespan. We prove the Nash Equilibria of the game for pure and mixed strategies, the expected payoffs and the price of anarchy corresponding to these equilibria. Then, we use this analysis to formulate a clustering mechanism (which we called Clustered Routing for Selfish Sensors-CROSS), that can be applied to sensor networks in practice. Comparing this mechanism to a popular clustering technique, we show via simulations that CROSS achieves a performance similar to that of a very popular clustering algorithm.