Standard embedded sensor network models emphasize energy efficiency and distributed decision-making by considering untethered and unattended sensors. To this we add two constraints - the possibility of sensor failure and the fact that each sensor must tradeoff its own resource consumption with overall network objectives. In this paper, we develop an analytical model of data-centric information routing in sensor networks under all the above constraints. Unlike existing techniques, we use game theory to model intelligent sensors thereby making our approach sensor-centric. Sensors behave as rational players in an N-player routing game, where they tradeoff individual communication and other costs with network wide benefits. The outcome of the sensor behavior is a sequence of communication link establishments, resulting in routing paths from reporting to querying sensors. We show that the optimal routing architecture is the Nash equilibrium of the N-player routing game and that computing the optimal paths (which maximizes payoffs of the individual sensors) is NP-hard with and without data-aggregation. We develop a game-theoretic metric called path weakness to measure the qualitative performance of different routing mechanisms. This sensor-centric concept which is based on the contribution of individual sensors to the overall routing objective is used to define the quality of routing (QoR) paths. Simulation results are used to compare the QoR of different routing paths derived using various energy-constrained routing algorithms.

Given the increasing importance of optimal sensor deployment for battlefield strategists, the converse problem of reacting to a particular deployment by an enemy is equally significant and not yet addressed in a quantifiable manner in the literature. We address this issue by modeling a two stage game in which the opponent deploys sensors to cover a sensor field and we attempt to maximally reduce his coverage at minimal cost. In this context, we introduce the concept of minimal sensor integrity which measures Me vulnerability of any sensor deployment. We find the best response by quantifying the merits of each response. While the problem of optimally deploying sensors subject to coverage constraints is NP-complete, in this paper we show that the best response (i.e. the maximum vulnerability) can be computed in polynomial time for sensors with arbitrary coverage capabilities deployed over points in any dimensional space. In the special case when sensor coverages form an interval graph (as in a linear grid), we describe a better O(Min(M/sup 2/, NM)) dynamic programming algorithm.