Network Formation Games for Distributed Uplink Tree Construction in IEEE 802.16J Networks

This paper investigates the problem of the formation of an uplink tree structure among the IEEE 802.16j network's Relay Stations (RSs) and their serving Base Station (MR-BS). The authors model the problem as a network formation game in which the RSs want to form a directed tree graph to improve their utility, in terms of the Packet Success Rate (PSR), by using multi-hop cooperative transmission while accounting for a link maintenance cost. In this game, the relay stations engage in bilateral negotiations which result in a contractual agreement to form a directed link between each pair. For network dynamics, they propose an algorithm based on the local best responses of the RSs that converges to a local Nash network.