Zoomable video streaming refers to a new class of interactive video applications, where users can zoom into a video stream to view a selected region of interest in higher resolutions and pan around to move the region of interest. The zoom and pan effects are typically achieved by breaking the source video into a grid of independently decodable tiles. Streaming the tiles to a set of heterogeneous users using broadcast is challenging, as users have different link rates and different regions of interest at different resolution levels. In this paper, we consider the following problem: given the subset of tiles that each user requested, the link rate of each user, and the available time slots, at which resolution should each tile be sent, to maximize the overall video quality received by all users. We design an efficient algorithm to solve the problem above, and evaluate the solution on a testbed using 10 mobile devices. Our method is able to achieve up to 12dB improvements over other heuristic methods.
To further improve streaming performance, the last category of research jointly adapts video data rate and multicast link rate. This category is the most related to our work. @cite_13 investigate the utility optimization problem of scalable video multicast and prove that this problem is NP-Hard. A greedy algorithm is then proposed to schedule the transmissions of layers and determine the corresponding modulation and coding scheme (MCS) assigned for each transmission. @cite_24 suggest a pseudo-polynomial algorithm with dynamic programming to solve the optimization problem. Most recently, MuVi @cite_23 has been designed to investigate the optimal multicast scheduling problem for videos encoded with I, P, and B frames. As the computational complexity of the suggested algorithm @cite_24 grows quadratically with the number of available time slots, it fails to efficiently solve the optimization problem with multiple multicast sessions. To reduce the computational complexity especially for the case of multiple sessions, a fully polynomial time approximation algorithm is presented @cite_0 . The approximation factor, however, linearly decreases with the number of multicast sessions.
@cite_24 @cite_0 @cite_13 @cite_23
2119959531 2147990225 2168573851
Scalable video coding (SVC), together with adaptive modulation and coding (AMC), can improve wireless multicast streaming video by jointly performing radio resource allocation and modulation and coding scheme (MCS) selection. However, the existing schemes in the literature allocate radio resources for different video layers separately, which leads to a waste of radio resources. In this work, we introduce the notion of joint layer resource allocation which allows to jointly allocate resources to multiple video layers that are assigned the same MCS. We formulate this problem and prove it to be NP-hard. Then we develop a pseudo-polynomial algorithm that finds the optimal total system utility. Our algorithm assumes a very generic utility function and flexible video layer rates. To reduce the complexity of the algorithm, we also propose Fully Polynomial Time Approximation Schemes (FPTAS) for the same problem. Simulation results show that our optimal algorithm offers significant improvement on system utility over a previous optimal algorithm and a greedy algorithm both of which do not support joint layer resource allocation. The proposed approximation algorithm provides controllable tradeoff between performance and computational complexity and, with appropriately chosen parameters, it outperforms the greedy algorithm with 40 less running time. Future 4G cellular networks are featured with high data rate and improved coverage, which will enable realtime video multicast and broadcast services. Scalable video coding is very appropriate for wireless multicast service because it allows to choose different modulation and coding schemes (MCSs) for different video layers and can provide good video quality to users in good channel conditions while still maintaining reasonable video quality for other users. In order to apply scalable video coding to wireless multicast streaming, it is important to choose appropriate MCS for each video layer and to determine the right resource allocation among multiple video sessions. In this paper we propose a two-step dynamic programming algorithm that finds the optimal total system utility of all users where the system utility can be a generic non-negative, non-decreasing function of received rate. Our algorithm supports variable layer size and thus allows flexibility during the video encoding process. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources. With the constraints of network topologies and link capacities, achieving the optimal end-to-end throughput in data networks has been known as a fundamental but computationally hard problem. In this paper, we seek efficient solutions to the problem of achieving optimal throughput in data networks, with single or multiple unicast, multicast and broadcast sessions. Although previous approaches lead to solving NP-complete problems, we show the surprising result that, facilitated by the recent advances of network coding, computing the strategies to achieve the optimal end-to-end throughput can be performed in polynomial time. This result holds for one or more communication sessions, as well as in the overlay network model. Supported by empirical studies, we present the surprising observation that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality. In this paper, we investigate the problem of Multicast Routing in Sparse Splitting Networks (MR-SSN). Given a network topology with the multicast capable nodes distributed uniformly throughout the network, and a multicast session, the MR-SSN problem is to find a route from the source node of the multicast session to all destinations of the multicast session such that the total number of fibers used in establishing the session is minimized. In this paper, we develop a rerouting algorithm for a given Steiner tree, which makes it feasible to route a multicast session using a tree-based solution in sparse light splitting optical networks. In addition, we present a heuristic based on Tabu Search (TS) that requires only one transmitter for the source node and one wavelength for each multicast session. To evaluate the performance of heuristics, we formulate the MR-SSP problem as an integer linear program (ILP), and optimally solve small instances using the commercially available linear solver, CPLEX. We test our heuristic on a wide range of network topologies. Our experimental results show that: (1) The difference between our solution and ILP optimal solution, in terms of the number of fibers used for establishing a multicast session, is within 10 in almost all the instances and within 5 in about half of the instances. (2) The average delay, taken over all destination nodes, falls within three times the optimal value. (3) A sparse light splitting all-optical network with 30 of multicast capable cross-connects has an acceptable low cost and relatively good performance. (4) The improvement achieved by TS heuristic increases considerably when the session size is large, the number of Splitter-and-Delivery cross-connects is small, and the network connectivity is dense.