A distributed truthful routing protocol for Mobile Ad hoc Networks

In Mobile Ad hoc Networks (MANETs), nodes depend on each other for routing and forwarding their packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and not cooperate in network activities. Such selfish behaviour poses a real threat to the proper functioning of MANETs. To cope with this situation, a motivation stimulation mechanism is required to provide sufficient incentives for nodes to forward other nodes´ packets. One appropriate approach is to have network nodes pay in order to motivate them to cooperate with the protocol. To achieve truthfulness, the payment should be based on the cost of transmission of packets. Since the mentioned costs are private to the nodes, a suitable mechanism is needed to collect the real values. In this paper, we propose a distributed truthful routing protocol utilizing the game theoretic notion of the mechanism design to solve the problem. To the best of our knowledge, our proposed protocol is the first protocol attaining the message complexity of O(n+d), in which n is the number of nodes in the network, and d is an upper bound on the length of the path. The proof of the protocol´s properties is provided and its performance is evaluated through simulation. Experimental results confirm that the proposed protocol has a considerably low overhead and outperforms the previously proposed protocol TMRP which has the best performance between truthful routing protocols in ad hoc networks, in terms of overhead and end-to-end delay with a slight decrease in delivery ratio. Instead, our protocol finds optimal paths that can save energy consumption and decrease the payments to the intermediate nodes.