View article

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 (1) a node is always better off participating in the protocol execution (individual rationality), (2) a node is always better off behaving according to the protocol specification (truthfulness), (3) messages are routed along the most energy-efficient (least cost) path, and (4) 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 …