A multi-hop mobile ad hoc network (MANET) consists of mobile hosts connected by wireless links. In this network, user’s cooperation is usually assumed, i.e., each node agrees to forward packets for other nodes if needed. Such cooperative behavior does exist in military and emergency missions, however, it is not a realistic assumption in a public MANET formed by a random group of strangers. Mobile users with a small computing device usually face limited resources, such as battery, CPU and memory. In order to save these resources, they are likely to behave selfishly, for example, by refusing to forward other users’ packets, and hence paralyze the whole network.
Although the users are selfish, we can assume that they are rational. Therefore, a promising way to foster cooperation is via certain incentive mechanisms. Facing the correct incentive, a rational user will choose to cooperate voluntarily. In human society, monetary rewards are usually given for providing service. The same principle should also apply in MANET, considering the fact that mobile devices are ultimately owned and controlled by human users. To some extent, forwarding packets in a public MANET can be seen as a user’s service to others.
To this end, we adopt the “pay for service” model of cooperation, and propose an auction-based incentive scheme (called iPass) to enable cooperative packet forwarding behavior in MANET. Each flow pays the market price of packet forwarding service to the intermediate routers. The resource allocation mechanism in our scheme is based on the generalized Vickrey auction with reserve pricing. We prove that in our scheme, user’s truthful bidding of utility remains a dominant strategy, users and routers have incentive to participate in the scheme, and packet forwarding always leads to higher social welfare for the whole network. We design a signaling protocol to implement the scheme, and show that it can serve as an explicit rate-based flow control mechanism for the network. Therefore, iPass is a joint solution of incentive engineering and flow control in a non-cooperative MANET. Simulation results show that iPass is able to determine the auction outcome quickly, and at the same time achieve the goals of flow control.
Publications
- Kai Chen, Klara Nahrstedt, iPass: an Incentive Compatible Auction Scheme to Enable Packet Forwarding Service in MANET, in Proc. of 24th IEEE International Conference on Distributed Computing Systems (ICDCS 2004), Tokyo, Japan, March, 2004