01whole.pdf (1.34 MB)
Download file

The minimum clearing time problem in wireless networks

Download (1.34 MB)
thesis
posted on 29.03.2022, 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.

History

Table of Contents

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

Notes

Empirical thesis. Bibliography: pages 53-54

Awarding Institution

Macquarie University

Degree Type

Thesis MRes

Degree

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

Department, Centre or School

Department of Engineering

Year of Award

2016

Principal Supervisor

Stephen Hanly

Rights

Copyright Swaroop Gopalam 2016. Copyright disclaimer: http://mq.edu.au/library/copyright

Language

English

Extent

1 online resource (viii, 54 pages) diagrams

Former Identifiers

mq:69698 http://hdl.handle.net/1959.14/1256861