Truthful multipath routing for ad hoc networks with selfish nodes

Multiple path routing protocols are shown to be performance-effective alternatives over single-path routing for ad hoc networks. They provide better resistance to link breakage and load balancing. However, these protocols typically assume a cooperative network setting. In practice nodes in an ad hoc network may behave selfishly   and may not be willing to forward packets for other nodes freely. One way to stimulate nodes’ cooperation is to reimburse forwarding nodes according to their cost such that these nodes get enough incentive. However, selfish nodes may cheat over their cost to maximize their payoff. This necessitates the need for a truthful protocol which maximizes a node’s payoff only when it reveals its true cost. In this paper, we present GTMRGTMR, a generic mechanism to transform any   table-driven multipath routing protocol into a truthful one, and prove that it guarantees truthfulness. Further, we present TMRP — a truthful multipath routing protocol based on AOMDV protocol as an instance of GTMRGTMR. A prominent feature of TMRP is that it incurs only 2n2n control packets for a route discovery and does not require new types of control messages over AOMDV. To the best of our knowledge, this is the lowest overhead incurred for any truthful routing protocols. TMRP can also achieve load balancing without compromising truthfulness. We conduct an extensive simulation study to evaluate the performance of TMRP. Simulation results show that TMRP provides high packet delivery ratio and has low overhead and low end-to-end delay without compromising the overpayment to the nodes.