Title: Routing game in hybrid wireless mesh networks with selfish mesh clients

Authors: Yu Wang, Teresa A. Dahlberg, Weizhao Wang

Addresses: Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA. ' Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA. ' Google Inc., Mountain View, CA, USA

Abstract: Wireless mesh networks (WMNs) consist of mesh routers and mesh clients where fixed mesh routers form the multi-hop backbone of the network. It is often assumed that each individual mesh client will faithfully follow the prescribed protocols. However, these mobile devices, owned by individual users, will likely do what is the most beneficial to their owners, i.e. act |selfishly|. In this article, we study how to design routing protocols in WMNs with selfish mesh clients. We first show that the totalpayment of the classical Vickrey-Clarke-Groves (VCG)-based routing protocol could be very expensive and inefficient for hybrid mesh networks. Then, we modify the VCG-based method to make it more efficient in terms of total payment, but we also prove that mesh clients could lie about their costs in this modified method. Instead of the VCG-based method, we then propose a novel routing protocol that could achieve Nash equilibrium with low total payments.

Keywords: game theory; Nash equilibrium; routing protocols; VCG mechanism; Vickrey-Clarke-Groves mechanism; wireless mesh networks; WMNs; wireless networks; selfish mesh clients.

DOI: 10.1504/IJAACS.2008.021490

International Journal of Autonomous and Adaptive Communications Systems, 2008 Vol.1 No.4, pp.425 - 446

Published online: 28 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article