_Algorithms_**2009**, \(2\), 1303 - 1326; doi:10.3390/a2041303  
_Article_  
**Incentive Compatible and Globally Efficient Position Based Routing for Selfish Reverse Multicast in Wireless Sensor Networks**  
**[PERSON] \({}^{1}\), [PERSON] \({}^{2,\star}\), [PERSON] \({}^{3}\), [PERSON] \({}^{4}\) and [PERSON] \({}^{2}\)**  
\({}^{1}\) Discrete Simulation Sciences, Los Alamos National Laboratories, Los Alamos, NM 87545, USA;  
E-Mail: [EMAIL_ADDRESS] (S.E.) \({}^{2}\) Electrical Engineering and Computer Science, University of Kansas, Lawrence, KS 66045,USA;  
E-Mail: [EMAIL_ADDRESS] (S.V.) \({}^{3}\) Computer Science,University of California, Los Angeles, Los Angeles, CA 90095, USA;  
E-Mail: [EMAIL_ADDRESS] (A.M.)  
\({}^{4}\) Mathematical Sciences, Claremont Graduate University, Claremont, CA 91711, USA;  
E-Mail: [PERSON]SS] (A.P.) \({}^{\star}\) Author to whom correspondence should be addressed; E-Mail:[EMAIL_ADDRESS];  
Tel. : +1 310-895-0170; Fax: +1 785-864-3226. _Received: 31 August 2009; in revised form: 16 September 2009 / Accepted: 29 September 2009 / Published: 14 October 2009_  
**Abstract:** We consider the problem of all-to-one selfish routing in the absence of a payment scheme in wireless sensor networks, where a natural model for cost is the power required to forward, referring to the resulting game as a Locally Minimum Cost Forwarding (LMCF). Our objective is to characterize equilibria and their global costs in terms of stretch and diameter, in particular finding incentive compatible algorithms that are also close to globally optimal. We find that although social costs for equilibria of LMCF exhibit arbitrarily bad worst-case bounds and computational infeasibility of reaching optimal equilibria, there exist greedy and local incentive compatible heuristics achieving near-optimal global costs. **Keywords:** sensor networks; incentive compatible topology control; game theory; price of stability; price of anarchy; heuristics for NP-hard problems; location based routing; local algorithms; random Euclidean power graphsIntroduction  
Incentive-compatible topology control protocols play a central role in selfish wireless networking. These protocols determine which links are to be used for forwarding data packets from sources to destinations. Non-selfish topology control involves selecting a subset of possible communication edges such that the resulting induced subgraph satisfies a number of desirable properties, such as being a single component, having small maximum degree, and preserving shortest paths within a small factor (see [1; 2] for an overview of topology control results). Incentive-compatible topology control has only recently received attention from the wireless network research community, with the two traditional game-theoretic approaches being to characterize Nash equilibria [3; 4; 5] and to design VCG-based mechanisms for ad-hoc networks [3; 4; 6; 7; 8; 9]. A wireless sensor node is capable of monitoring the environment or sensing an occurrence of a particular event. A collection of such nodes is called a wireless sensor network [10]. Sensor nodes are often deployed in an ad-hoc manner and they send the sensed information to a base-station or a cluster head which acts as a data collection point. As often sensor nodes are deployed on a far off location and are battery-powered, they are highly energy-constrained. Thus energy efficiency is an important parameter in evaluating the performance of any protocol designed for sensor networks. Reverse multicast traffic is more common in a wireless sensor network as multiple nodes send the sensed information to a single data collection point and due to the energy constraint, a sensor node will often choose to send the data in a multihop fashion so as to avoid transmission over a long distance [11]. Thus a sensor network can be modelled as a collection of selfish nodes with reverse multicast traffic. We study selfish topology control where all participating nodes need to have a path to a single destination.