Operations Research Approach Towards Layered Multi-Source Video Delivery
We address the problem of rate scaling of multiple layered video streams in applications such as a multi-camera video surveillance system. This differs from the single video streaming scenario in that relevant information from all sources has to be aggregated and a collective decision made. We propose a scenario to achieve better granularity in quality adaptation by considering inter-source and inter-layer streaming jointly, using Operation Research techniques to arrive at an optimal or nearoptimal solution. We formulate our Multi-Source MultiLayer Selection (SLS) problem in the form of a MultipleChoice Knapsack Problem (MCKP). We analyze optimal and approximate algorithms to determine their suitability for solving the problem. We present a simple modification based on an existing greedy aglorithm by exploiting some properties of layered video. The modified SLS algorithm is extended to incorporate weights (Weighted SLS - WSLS - algorithm). Via experimental results using MPEG-4 FGS, we show that WSLS improves the performance for specialized applications. We also discuss the various network configurations of a multi-source video distribution system.
A Genetic Algorithm for Layered Multi-Source Video Distribution
We propose a genetic algorithm -- MckpGen -- for rate scaling and adaptive streaming of layered video streams from multiple sources in a bandwidth-constrained environment. A genetic algorithm (GA) consists of several components: a representation scheme; a generator for creating an initial population; a crossover operator for producing offspring solutions from parents; a mutation operator to promote genetic diversity and a repair operator to ensure feasibility of solutions produced. We formulated the problem as a Multiple-Choice Knapsack Problem (MCKP), a variant of Knapsack Problem (KP) and a decision problem in combinatorial optimization. MCKP has many successful applications in fault tolerance, capital budgeting, resource allocation for conserving energy on mobile devices, etc. Genetic algorithms have been used to solve NP-complete problems effectively, such as the KP, however, to the best of our knowledge, there is no GA for MCKP. We utilize a binary chromosome representation scheme for MCKP and design and implement the components, utilizing problem-specific knowledge for solving MCKP. In addition, for the repair operator, we propose two schemes (RepairSimple and RepairBRP ). Results show that RepairBRP yields significantly better performance. We further show that the average fitness of the entire population converges towards the best fitness (optimal) value and compare the performance at various bit-rates.