Windows Scheduling, Multiple-Message Broadcast, and other Wireless Networks Problems

23^rd June 2014, 16:00 Ashton Lecture Theater
Prof Miguel Mosteiro
Department of Computer Science
Kean University
USA

Abstract

The Windows Scheduling (WS) problem (also known as Inventory Replenishment in Supply Chain) is a restricted version of Unit-Fractions Bin Packing. In Wireless Networks, the problem is to schedule the use of shared channels, restricted for each client to a maximum delay between consecutive transmissions. In previous models clients do not leave the system, or decisions are permanent (online). I will present recent work on WS where we assume that clients may be reallocated at some cost. I will briefly describe three online reallocation WS algorithms that achieve constant amortized reallocations with close to optimal channel usage in practice. To the best of our knowledge, this was the first study of WS with reallocation cost.
In the dynamic version of the Multiple-Message Broadcast (MMB) problem packets are continuously injected in some network nodes for dissemination. In recent work, we measured performance of a MMB algorithm as the ratio of the throughput of such protocol against the optimal, for any sufficiently long period of time since startup. I will describe a dynamic MMB protocol that works under an affectance model that parameterizes the interference that other nodes introduce in the communication between a given pair of nodes. As an algorithmic tool, we developed an efficient algorithm to schedule a broadcast along a BFS tree under the affectance model. For the analysis, we defined two novel network characteristics (based on the network topology, the affectance function and the chosen BFS tree) that combined influence the performance of broadcasting with affectance (modulo polylogarithmic function). I will briefly describe the results and simulations of this protocol. To the best of our knowledge, this is the first dynamic MMB protocol that provides throughput guarantees for continuous injection of messages and works under the affectance model.
Future work and open problems in these and perhaps other lines will be briefly discussed.