Istituto di Informatica e Telematica     
Eidenbenz S., Resta G., Santi P. COMMIT: A Sender-Centric, Truthful, and Energy-Efficient Routing Protocol for Ad Hoc Networks with Selfish Nodes. In: IEEE Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (Denver, USA, 2005). Proceedings, IEEE Computer Society, 2005.
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: 􀀀􀀀 a node is always better off participating in the protocol execution (individual rationality), 􀀀􀀀􀀀 a node is always better off behaving according to the protocol specification (truthfulness), 􀀀􀀀􀀀􀀀 messages are routed along the most energyefficient path, and 􀀀􀀀 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 crosslayer 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.
DOI: 10.1109/IPDPS.2005.142
Subject COMMIT protocol
Routing protocols
Ad Hoc networks

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional