Recent advances in wireless communication have made possible the large-scale deployment of wireless networks, which consist of small, low-cost nodes with simple processing and networking capabilities. In order to reach the desired destination such as the data sink, transmissions depending on multiple hops are necessary. As a result, the optimization of routing is a critical problem that involves many aspects such as link quality, energy efficiency, and security. Moreover, the nodes may not be willing to fully cooperate. For example, from the node's perspective, forwarding the arriving packets consumes its limited battery power, so it may not be in the node's interest to forward all arriving packets. But doing so will adversely affect network connectivity. Hence, it is crucial to design a distributed-control mechanism that encourages cooperation among participating multi-hop nodes.

This chapter studies game-theoretic approaches to routing in multi-hop networks. We first introduce important models and examples of routing games. We provide two detailed examples, a repeated-routing game and a hierarchical-routing game for enforcing cooperation. Finally, we list other approaches from the literature.

Routing-game basics

A network is given by a directed graph G = (V, E), with vertex set V and edge set E (either directed or undirected). A set {(s1, d1), …, (sK, dK)} consists of source–destination vertex pairs, which we also call commodities. Each player is identified with one commodity. Different players can originate from different source vertices and pass information to different destination vertices.