ADAPTIVE SCHEDULING OF STREAMING VIDEO OVER WIRELESS NETWORKS

• US 20090193484A1
• Filed: 01/05/2009
• Published: 07/30/2009
• Est. Priority Date: 01/03/2008
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Rangarajan, Sampath, Zhang, Honghai
• Granted Patent: US 8,141,120 B2
• Time in Patent Office: Days
• US Class Current: 725/112
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/2405 Monitoring of the internal components or processes of the server, e.g. server load allocation of resources in multiprogramming arrangements G06F9/50; performance measurement of computer activity G06F11/34
• CPC Class Codes: H04N 21/6473 Monitoring network processes errors for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: H04N 21/64738 Monitoring network characteristics, e.g. bandwidth, congestion level data switched network analysis H04L41/14; monitoring functioning in data switched networks H04L43/0817; flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/64769 for rate control flow control in packet networks H04L47/10

Abstract

An adaptive scheduling process is disclosed which dynamically decides which frames need to be transmitted and which ones need to be dropped at any transmission opportunity based on current channel conditions and on characteristics of each video frame.

Claims

1. A method to transmit streaming video over a wireless network channel with periodic transmission opportunities, comprising:

receiving a plurality of video frames for transmission, each frame having an importance θ and

a deadline by which the frame is to be received;

transmitting video frames at each transmission opportunity with a scheduler, wherein the scheduler maximizes the total importance for all frames to be received within each frame deadline by applying dynamic programming on a predetermined window of frames and updating the scheduler with a channel feedback.

2. The method of claim 1, comprising determining u(i, T) as a maximum utility (importance) that can be attained with a deadline T and with frames up to i.

3. The method of claim 2, comprising determining u(i,T)=u(i,T_i) if T is greater than the deadline T_i of frame i and otherwise determining u(i,T) first recursively and then using dynamic programming.

4. The method of claim 1, comprising applying random channel error probability in selecting the frames.

5. The method of claim 4, comprising determining an expected utility u(i,T) as attainable by deadline T and with up to i frames.

6. The method of claim 5, comprising recursively determining the expected utility u(i,T) as

u(i,T)=max(u(i1,T),max(u(i1,Tk)P_li,kθ

_i, over l_ikT, and P_li,k1δ

))

where

$P_{l,k}=\underset{j=l}{\overset{k}{\sum <br><br>}}<br><br><br><br>\left(\begin{array}{c}k\\ j\end{array}\right)<br><br>{\left(1<br><br>p_e\right)}^j<br><br>p_{e^{-}}^{k-j}$

is the probability of having at least l successful transmissions out of k attempts, l_i is the length of frame i, and p_e is the packet error probability at one transmission.

7. A method to transmit streaming video having a plurality of frames over a wireless channel, each frame having an importance measure relating to video quality, comprising:

maximizing a total importance measure for all frames to be received within each frame deadline through dynamic programming with a predetermined window of frames;

dynamically scheduling one or more frames to be transmitted or dropped at each transmission opportunity based on current channel conditions and on characteristics of each video frame; and

updating the dynamic schedule with a channel feedback.

8. The method of claim 7, comprising deciding frame(s) to be dropped based on deadline, size, and importance of each frame.

9. The method of claim 7, comprising determining u(i, T) as a maximum utility (importance) that can be attained with a deadline T with frames up to i.

10. A video transmission system, comprising:

a wireless transceiver to transmit a plurality of video frames, each frame having an importance θ and

having a deadline T by which all packets of the frame must be received, the wireless transceiver communicating over a network channel with periodic transmission opportunities; and

a scheduler to select one or more frames to transmit at each transmission opportunity, wherein the scheduler maximizes an expected total importance for all frames to be received before each frame deadline by applying dynamic programming on a predetermined window of frames, wherein the scheduler is updated with channel feedback.

11. The system of claim 10, wherein the network channel is an erasure channel, each packet is erased with a probability, and wherein the scheduler maximizes an expected importance.

12. The system of claim 10, wherein the scheduler considers the importance, the size, and the deadline of each frame.

13. The system of claim 10, wherein the problem is formulated as a knapsack problem with deadline constraints and randomness of packet error, and is solved though dynamic programming.

14. The system of claim 10, wherein the scheduler prioritizes packet transmission and selectively drops packets at a wireless last hop.

15. The system of claim 10, wherein packets that are the least important in terms of overall PSNR are dropped first.

16. The system of claim 10, wherein the scheduler operates without communication between a video server and a base station.

17. The system of claim 10, wherein the scheduler operates with a base station scheduler to exploit channel and user diversity over a multi-carrier and multi-user wireless network, comprising determining u(i, T) as a maximum expected utility (importance) that can be attained with a deadline T with frames up to i, and determining which frames are dropped and which are transmitted.

18. The system of claim 10, comprising recursively determining u(i,T) and then computing it using a dynamic programming approach without recursion.

19. The method of claim 10, comprising determining u(i,T)=u(i,T_i) if T is greater than the deadline T_i of frame i and otherwise determining u(i,T) recursively and then using a dynamic programming approach.