Multi-path routing and forwarding in non-cooperative wireless networks

Multi-path routing and forwarding in non-cooperative networks is extremely challenging due to the co-existence of both rational and Byzantine nodes. They both might deviate from the protocol; however, their intentions and behaviors are totally different. Rational nodes aim to maximize their utilities, while Byzantine nodes purposefully deviate from the protocol to disrupt the normal operation of a network. Most work in the literature treat both kinds of misbehavior without distinction and thus lead to ineffective solutions. This paper presents a hybrid design that seamlessly integrates mechanisms for different misbehavior in a unified framework. The GSP auction provides incentives for rational nodes to cooperate and results in truth-telling Nash equilibria. With the possible inclusion of Byzantine nodes in the least cost paths selected by GSP, the FORBID mechanism builds a decentralized reputation system such that malicious behavior is effectively detected. This in turn triggers the GSP auction to update the least cost paths so as to exclude the malicious nodes from being selected for communication. It is proved that the unified protocol is cooperation-optimal. Experiments have been conducted to further investigate the performance of the proposed protocol and the impact of various parameters.