Chinese Journal of Computers   Full Text
Title	A Cooperation Protocol for Ad Hoc Networks with Selfish Nodes Based on Mechanism Design
Authors	GUO Jian-Li WU Zhi-Bo DONG Jian YANG Xiao-Zong LIU Hong-Wei
Address	(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
Year	2009
Issue	No.3(483—492)
Abstract &   Background	Abstract In mobile ad hoc networks, how to stimulate selfish nodes to participate in the network cooperation is currently a hot research field. This paper proposes the LMOCP protocol, which applied VCG mechanism to calculate payments for relay nodes. The introduction of a neighbor discovery process and the improvement on routing discovery process can together decrease the overhead of control message from O(n3) to O(n2). By encrypting the RREQ, relay nodes can not discard RREQ any more. The validity of the protocol is analyzed, and the LMOCP protocol is proven to be Ex Post Nash implementable under the assumption that node rational is the common knowledge, and the optimal strategy of each node is to honestly report their prices. Ns-2 was used for simulation and the result shows that LMOCP had lower message overhead and shorter network delay compared with several important protocol. Keywords mobile ad hoc networks; selfish node; node cooperation; VCG mechanism; neighbor discovery Background In ad hoc network, nodes cooperate by forwarding packets for each other to allow them to communicate beyond direct wireless transmission range. All the mature routing protocols, such as DSR and AODV, assume that nodes are cooperative, and they are willing to forward packets for other nodes. In recent years, with the progress of technology, it is becoming possible to deploy mobile ad hoc networks for civilian applications as well. In these networks, each node belongs to different individuals or organizations, and the cooperation among the nodes would not be guaranteed. In order to save resources (such as energy), some nodes may show selfish behavior, discarding all passing by packets. How to stimulate selfish nodes to cooperate became a hot spot in ad hoc network research community recently. Current studies proposed a lot of schemes to encourage selfish nodes to take part in network cooperation, such as Ad hoc-VCG or LOTTO. But there still exist some drawbacks in these protocols: source node can increase its payment by cheating; relay nodes may drop RREQs, which is important for destination node; there are lots of RREQs need to be exchanged in route discovery phase. This paper proposes a new cooperation protocol named LMOCP, which solves those shortcomings. The authors also prove that LMOCP is Ex Post Nash implemental. This research is partially supported by the High Technology Research and Development Program (863) of China under grant No.2006AA01A103 and the National Natural Science Foundation of China under grant No.60503015.