loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12
COMMIT: A Sender-Centric Truthful and Energy-Efficient Routing Protocol for Ad Hoc Networks with Selfish Nodes
Denver, Colorado
April 04-April 08
ISBN: 0-7695-2312-9
Stephan Eidenbenz, Los Alamos National Labs, USA
Giovanni Resta, IIT-CNR, Pisa, Italy
Paolo Santi, IIT-CNR, Pisa, Italy
We consider the problem of establishing a route and sending packets between a source/destination pair in ad hoc networks composed of rational selfish nodes, whose purpose is to maximize their own utility. In order to motivate nodes to follow the protocol specification, we use side payments that are made to the forwarding nodes. Our goal is to design a fully distributed algorithm such that: (i) a node is always better off participating in the protocol execution (individual rationality), (ii) a node is always better off behaving according to the protocol specification (truthfulness), (iii) messages are routed along the most energy-efficient path, and (iv) the message complexity is reasonably low. We introduce the COMMIT protocol for individually rational, truthful, and energy-efficient routing in ad hoc networks. To the best of our knowledge, this is the first ad hoc routing protocol with these features. COMMIT is based on the VCG payment scheme, in conjunction with a novel game-theoretic technique to achieve truthfulness for the sender node. By means of simulation, we show that the inevitable economic inefficiency is small. As an aside, our work demonstrates the advantage of using a cross-layer approach to solving problems: leveraging the existence of an underlying topology control protocol, we are able to simplify the design and analysis of our routing protocol, and to reduce its message complexity. On the other hand, our investigation of the routing problem in presence of selfish nodes disclosed a new metric under which topology control protocols can be evaluated: the cost of cooperation.
Citation:
Stephan Eidenbenz, Giovanni Resta, Paolo Santi, "COMMIT: A Sender-Centric Truthful and Energy-Efficient Routing Protocol for Ad Hoc Networks with Selfish Nodes," ipdps, vol. 13, pp.239b, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, 2005
Usage of this product signifies your acceptance of the Terms of Use.