1Timely Throughput of Heterogeneous Wireless Networks: Fundamental Limits and Algorithms

The proliferation of different wireless access technologies, together with the growing number of multi-radio wireless devices suggest that the opportunistic utilization of multiple connections at the users can be an effective solution to the phenomenal growth of traffic demand in wireless networks. In this paper we consider the downlink of a wireless network with N Access Points (AP’s) and M clients, where each client is connected to several out-of-band AP’s, and requests delay-sensitive traffic (e.g., real-time video). We adopt the framework of Hou, Borkar, and Kumar, and study the maximum total timely throughput of the network, denoted by CT3, which is the maximum average number of packets delivered successfully before their deadline. Solving this problem is challenging since even the number of different ways of assigning packets to the AP’s is NM. We overcome the challenge by proposing a deterministic relaxation of the problem, which converts the problem to a network with deterministic delays in each link. We show that the additive gap between the capacity of the relaxed problem, denoted by Cdet, and CT3 is bounded by 2 N(Cdet