Optimal Control of Wireless Networks With Finite Buffers

This paper considers network control for wireless networks with finite buffers. We investigate the performance of joint flow control, routing, and scheduling algorithms that achieve high network utility and deterministically bounded backlogs inside the network. Our algorithms guarantee that buffers inside the network never overflow. We study the tradeoff between buffer size and network utility and show that under the one-hop interference model, if internal buffers have size <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">(N-1)/(2 ε)</tex></formula> , then <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">ε</tex></formula> -optimal network utility can be achieved, where <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">ε</tex></formula> is a control parameter and <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">N</tex> </formula> is the number of network nodes. The underlying scheduling/routing component of the considered control algorithms requires ingress queue length information (IQI) at all network nodes. However, we show that these algorithms can achieve the same utility performance with delayed ingress queue length information at the cost of a larger average backlog bound. We also show how to extend the results to other interference models and to wireless networks with time-varying link quality. Numerical results reveal that the considered algorithms achieve nearly optimal network utility with a significant reduction in queue backlog compared to existing algorithms in the literature.