Affiliations: Faculty of Information Technology, University of
Science, Ho Chi Minh City, Vietnam
Note: [] Corresponding author: Dung T. Tran, Faculty of Information
Technology, University of Science, Ho Chi Minh City, Vietnam. E-mail: [email protected]
Abstract: Choosing routes such that the network lifetime is maximized in a
wireless network with limited energy resources is a major routing problem in
wireless multi-hop ad hoc networks. In this paper, we study the problem where
participants are rationally selfish and non-cooperative. By selfish we
designate the users who are ready to tamper with their source-routing (senders could choose intermediate nodes in the routing paths)
or next hop selection strategies in order to increase the total number of packets
transmitted, but do not try to harm or drop packets of the other nodes. The
problem therefore amounts to a non-cooperative game. In the works [2,6,19,23], the authors show that
the game admits Nash equilibria [1]. Along this line, we first show
that if the cost function is linear, this game has pure-strategy equilibrium
flow even though participants have different demands. However, finding a Nash
equilibrium for a normal game is computationally hard [9]. In this
work, inspired by mixed-strategy equilibrium, we propose a simple local routing
algorithm called MIxed Path Routing protocol (MiPR). Using analysis and
simulations, we show that MiPR drives the system to an equilibrium state where
selfish participants do not have incentive to deviate. Moreover, MiPR
significantly improves the network lifetime as compared to original routing protocols.
Keywords: Local routing, Network lifetime, Nash equilibrium
