Optimal Skewed Allocation on Multiple Channels for Broadcast in Smart Cities

We consider the problem of allocating N uniform data to K transmission channels so as the average Expected Delay (AED) is minimized. This problem arises in designing efficient data-diffusion broadcast algorithms in a smart environment. We show that the basic dynamic rogramming algorithm for solving the uniform pallocation problem can be speedup up to O(NK) time by applying an optimal algorithm to find the row-minima of totally monotone matrices. Such a new algorithm is always faster than the best previously known algorithm for the uniform allocation problem that runs in O(NKlogN). Moreover, it is computationally optimal for the uniform allocation of up to N data and K channels. We then reduce the largest allocation problem, i.e., the subproblem with exactly N data and K channels, to the problem of finding a minimum weight K-link path in a particular directed acyclic graph. We also present two heuristics and we show by extended simulations their effectiveness in practical scenarios. Both the K-link path algorithm and the heuristics are much faster than O(NK). We then compare the behaviours of our algorithms on the online version of the allocation problem in which new single items are inserted for broadcast.