AMPLE: A novel incentive approach to adaptive-width channel allocation in multi-hop, non-cooperative wireless networks

Due to the limitation of radio spectrum resource and fast deployment of wireless devices, careful channel allocation is of great importance for mitigating the performance degradation caused by interference among different users in wireless networks. Most of existing work focused on fixed-width channel allocation. However, latest researches have demonstrated that it is possible to combine contiguous channels for better utilizing the available channels. In this paper, we study the problem of adaptive-width channel allocation in multi-hop, non-cooperative wireless networks from a game-theoretic point of view. We first present a strategic game model for this problem and demonstrate the existence of Nash Equilibrium (NE) in an anarchical scenario. Since a NE is not an ideal solution, we then propose AMPLE, a novel incentive approach to guarantee the system performance at high level. Since the problem of channel allocation in multiple collision domains is NP-complete, we first present an approximate algorithm that gives an allocation with good system performance. We then design a charging scheme that guarantees the system to converge to a Dominant Strategy Equilibrium (DSE), in which it is to the best interest of each node to follow the computed channel allocation, regardless how the others behave. Numerical results verify that AMPLE does prevent nodes' misbehavior, and achieves much higher average system throughputs than anarchical NEs.