Game theory has been applied to many abstract networks in the course, from trading networks to social networks. One example that merits further investigation is a wireless ad hoc network.

Wireless ad hoc networks can easily be understood with the concepts presented in this class. Computers are nodes in the network and wireless radio links are the edges of the network. The network is called “ad hoc” because the wireless radio links are dynamically created based on the physical proximity of one node to another (e.g. the two nodes can reach each other over the wireless radio).

Unique problems arise in ad hoc networks. For example, since the topology of the network is dynamic, the shortest path from one node to another node may constantly be changing. In fact, changes in the network topology might sever one part of the network from the other. Also, since the network passes messages from one node to another via multi-hop routing, certain nodes may be more heavily burdened than other nodes.

For example, consider the situation where a node sits in a “powerful” position in the network (e.g. the red node). This is similar to the situation discussed in class, where one person is the unique link between two different social networks, so that information flows exclusively through that person. While in a social network this may be an enviable position, being a node that has high “betweenness” value can cause problems in a wireless ad hoc network.

First, having such a critical node is bad from a fault tolerance viewpoint. If that one node is destroyed, two network separates into two separate subgraphs that cannot communicate with each other.

Second, this critical node will have to ferry vast quantities of information from one side of the network to the other. If the nodes were part of a wireless sensor network, each node may have a limited power supply (e.g. a small coin battery). For each message that it relays, the node loses a little bit of power, and with the increasing number of messages, the node will rapidly run out of power.

Recall the four node network discussed in network exchange theory (a-b-c-d). The terminal nodes on the four node network (a and d) were at the mercy of the more powerful nodes in the center (b and c). An idea was briefly mentioned in lecture where node d may choose to forgo an exchange with node c and instead work on forming a link with either b or a.

In a real world wireless ad hoc network, this is a possibility. The two nodes at the top of the graph can improve the overall connectivity of the network by boosting their signals to form a link (marked in dashed red). While this requires more energy than the shorter hop to an adjacent node, this helps avoid having only one path between the two networks.

Game theory can be employed in wireless networks to help induce a socially optimal equilibrium (directly analogous to the joint strategy in a two player game that is social welfare maximizing). Each node has a choice to relay a message or not. By help relay the message, the node reduces its energy supply, but by not participating, it hurts the overall throughput of the network. Researchers can modify the utility function (a way to compute the payoff) of each node to help balance between these two choices to ensure the health of a wireless ad hoc network. Some ideas that have been suggested include providing incentives for participating, such as virtual currency (e.g. I’ll pass on your message, but you owe me one.). Other ideas include disincentives for not participating, such as quid pro quo (e.g. If you don’t pass on my message, I won’t pass on yours either.).

The optimal solution is still an open research question. For a broad overview of this topic, “Using Game Theory to Analyze Wireless Ad Hoc Networks” by Srivastava et. al. provides a basic overview of game theory and its applications to wireless ad hoc networks. The presentation “Forwarding incentives for wireless networks” by Vivek Raghunathan provides examples and references to further literature on the specific topic of packet forwarding in wireless ad hoc networks.