An auction-based strategy for distributed task allocation in wireless sensor networks

Abstract

Game theory provides a mathematical tool for the analysis of distributed decision making interactions between agents with conflicting interests. We apply game theory for distributed task allocation in wireless sensor networks (WSNs) where the decision makers in the game are the sensor nodes willing to perform the task to maximize their profits. They have to cope with limited resources (i.e., available energy levels) that imposes a conflict of interest. In resource-constrained wireless sensor networks, one of the fundamental challenges is to achieve a fair energy balance among nodes to maximize the overall network lifetime. Auction-based schemes, owing to their perceived fairness and allocation efficiency, are among the well-known game theoretic mechanisms for energy balanced distributed task allocation. In this paper, the real-time distributed task allocation problem is formulated as an incomplete information, incentive compatible and economically-robust reverse auction game. The main objective of this scheme is to maximize the overall network lifetime considering the application's deadline as the constraint. In the proposed game theoretic model, the distributed best response for bid updates globally converges to the unique Nash Equilibrium in a completely asynchronous manner. Another problem addressed in this paper is the winner determination problem. Given a distributed pool of bids from bidders (i.e., sensor nodes), a centralized winner determination protocol (WDP) would require costly message exchanges with high energy consumption and overhead. Hence, we propose the Energy and Delay Efficient Distributed Winner Determination Protocol (ED-WDP) for the reverse auction-based scheme. Our simulation results show a fairer energy balance achieved through this bid formulation in comparison to other well-known static schemes. Moreover, by utilizing the ED-WDP among the numerous distributed resources, the message exchange overhead, energy consumption and delay for winner determination are significantly reduced compared to a centralized WDP. © 2012 Elsevier B.V. All rights reserved.