Macquarie University
01whole.pdf (1.34 MB)
Download file

The minimum clearing time problem in wireless networks

Download (1.34 MB)
posted on 2022-03-29, 03:31 authored by Swaroop Gopalam
The thesis focuses on the minimum time clearing objective for link scheduling in wireless networks. We formulate the problem as a deterministic LP. We relate the problem to other works on capacity and scheduling. In general, the problem is NP-complete. We consider special networks where the additional structure makes the problem tractable. We argue that explicitly solving the linear program is implausible. And proceed to show that the problemis amenable to a greedy allocation scheme that only requires local information. Beyond the special case, we consider simple ring networks where in general, the greedy solution is sub-optimal. We solve the minimum clearing time problem for ring networks under 1-hop interference model. We establish the sufficiency conditions for optimality of a greedy solution. We also provide the solution when these conditions do not hold. For this case, the solution depends on global information, unlike the greedy solution. However, the solution only has a linear complexity in terms of computation. The minimum clearing time problem can help us understand how the network is constrained under different load distributions. Ultimately, in the future we aim to use these insights to design a simple scheduling policy, with nearly optimal performance in a general wireless network.


Table of Contents

1. Introduction -- 2. Tree networks -- 3. Ring networks -- 4. Future work -- References.


Empirical thesis. Bibliography: pages 53-54

Awarding Institution

Macquarie University

Degree Type

Thesis MRes


MRes, Macquarie University, Faculty of Science and Engineering, Department of Engineering

Department, Centre or School

Department of Engineering

Year of Award


Principal Supervisor

Stephen Hanly


Copyright Swaroop Gopalam 2016. Copyright disclaimer:




1 online resource (viii, 54 pages) diagrams

Former Identifiers