Truthful routing for wireless hybrid networks

Wireless hybrid networks combine the characteristics of both cellular and mobile ad hoc networks. In wireless hybrid networks, it is often assumed that each individual mobile node faithfully follows the prescribed protocols without any deviation. However, these mobile devices, when owned by individual users, will likely do what is the most beneficial to their owners, i.e., act "selfishly". Therefore, an algorithm or protocol intended for selfish wireless devices must be designed. In this paper, we specifically study how to design routing protocols in wireless hybrid networks with selfish nodes. We first present a VCG-based routing protocol for hybrid networks, and show it is truthful but could be expensive. Then we modify the VCG-based routing protocol to make it more efficient for hybrid networks in term of total payment. However, we prove that nodes could lie up their costs in the modified method. Moreover, we propose a novel routing protocol based on first-price path auctions [N. Immorlica et al, 2005], which can achieve a Nash equilibrium with low total payment