Graph Matchings and Wireless Communication

A classical problem in mobile telephony is to decide user-basestation association, i.e., given large number of mobile users, which basestation should each mobile user connect to. The question is interesting because all mobile users connected to one basestation have to time-share its resources, and the nearest basestation is not always the best choice because of wireless propagation medium.

A more modern paradigm envisaged in 5G network is that active mobiles are going to seek help (via relaying) from nearby idling mobile devices for improving their data rates. Once again, which neighbor should be selected for relaying and what incentives to offer him to prevent him from 'gaming' the system are objects of current interest.  

We will discuss both these problems via classical matching algorithms from graph theory.