[發(fā)明專利]部分可觀測(cè)馬爾可夫決策過程中可伸縮視頻流的優(yōu)化調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 200910196540.0
• 申請(qǐng)日: 2009-09-25
• 公開（公告）號(hào): CN101674482A
• 公開（公告）日: 2010-03-17
• 發(fā)明（設(shè)計(jì)）人: 鄒君妮;范鳳軍;彭兵;汪敏
• 申請(qǐng)（專利權(quán)）人: 上海大學(xué)
• 主分類號(hào): H04N7/30
• 分類號(hào): H04N7/30
• 代理公司: 上海上大專利事務(wù)所（普通合伙）
• 代理人: 陸聰明

1.一種部分可觀測(cè)馬爾可夫決策過程中可伸縮視頻流的優(yōu)化調(diào)度方法，其特征在于，針對(duì)無線廣播下的環(huán)境進(jìn)行假設(shè)簡(jiǎn)化，在用戶狀態(tài)不確定或部分可觀測(cè)的條件下，對(duì)可伸縮視頻流進(jìn)行調(diào)度，采用部分可觀測(cè)馬爾可夫決策過程建立數(shù)據(jù)包調(diào)度優(yōu)化模型，該模型包括狀態(tài)集合、行動(dòng)集合、狀態(tài)轉(zhuǎn)移概率、報(bào)酬函數(shù)、觀察集合、觀察概率，給出具體的調(diào)度過程，其具體步驟如下：

(1)、假設(shè)一個(gè)無線廣播傳輸環(huán)境模型，其具體為：

(1-1)、AP需要將視頻流發(fā)送給M個(gè)接收者r¹，r²，…，r^M；

(1-2)、AP需要在N個(gè)時(shí)隙內(nèi)將L個(gè)包的集合L＝{l₁，l₂，…，l_L}發(fā)送給接收者；

(1-3)、每一幀數(shù)據(jù)(L個(gè)包)的最大發(fā)送時(shí)間均為N個(gè)時(shí)隙，N個(gè)時(shí)隙結(jié)束之后，AP轉(zhuǎn)向下一幀數(shù)據(jù)包的發(fā)送；

(1-4)、AP轉(zhuǎn)發(fā)1個(gè)數(shù)據(jù)包的時(shí)間是一個(gè)時(shí)隙；

(1-5)、假設(shè)無線信道的丟包率服從參數(shù)為p_i的伯努利分布；

(2)、分別對(duì)可伸縮視頻流的每一幀數(shù)據(jù)分為L(zhǎng)層，每層打包為一個(gè)數(shù)據(jù)包，每一幀的數(shù)據(jù)包集合記為L(zhǎng)＝{l₁，l₂，…，l_L}，設(shè)立數(shù)據(jù)包調(diào)度優(yōu)化模型，具體步驟為：

(2-1)、狀態(tài)集合：在任一給定的時(shí)間節(jié)點(diǎn)，假設(shè)接收者r^m收到了若干數(shù)據(jù)包，它是L的一個(gè)子集，該子集可以用L位矢量表示，即?其中b∈{0，1}，b_i＝1表示r^m擁有數(shù)據(jù)包l_i，否則b_i＝0，共有M個(gè)接收者，系統(tǒng)的狀態(tài)s用一個(gè)矩陣來表示：?系統(tǒng)一共有2^M×L個(gè)狀態(tài)，

表示M個(gè)用戶擁有的數(shù)據(jù)包的狀態(tài)集合，?表示對(duì)應(yīng)狀態(tài)的概率分布?

(2-2)、行動(dòng)集合：A＝{a₁，a₂，…，a_L}表示M個(gè)用戶擁有的數(shù)據(jù)包的行動(dòng)集合，在每一個(gè)時(shí)隙內(nèi)AP選擇一個(gè)需要發(fā)送的數(shù)據(jù)包，a_l表示“發(fā)送第l個(gè)數(shù)據(jù)包”；

(2-3)、狀態(tài)轉(zhuǎn)移概率：在給定參數(shù)為p_i的伯努利丟包模型下，可以直接計(jì)算出狀態(tài)轉(zhuǎn)移?概率P(s_t+1＝s′|s_t＝s，a_t＝a)，例如，發(fā)送兩個(gè)包到兩個(gè)接收者，M＝2，L＝2，假設(shè)?在t時(shí)刻，系統(tǒng)處在s狀態(tài)，即r¹擁有數(shù)據(jù)包l₁，r²擁有數(shù)據(jù)包l₂，此時(shí)，AP選擇行動(dòng)a₁＝“發(fā)送l₁”，那么轉(zhuǎn)移到狀態(tài)s′的概率是P(s_t+1＝s′|s_t＝s，a_t＝a)＝0；如果選擇行動(dòng)a₂＝“發(fā)送l₂”，那么轉(zhuǎn)移到的概率是P(s_t+1＝s′|s_t＝s，a_t＝a)＝1-p₁；

(2-4)、報(bào)酬函數(shù)：報(bào)酬函數(shù)的選擇必須使每一時(shí)間節(jié)點(diǎn)下的瞬時(shí)報(bào)酬r(s，a)的總和能準(zhǔn)確地反應(yīng)既定目標(biāo)——視頻流質(zhì)量的最優(yōu)化，可以把接收者接收到每一個(gè)特定數(shù)據(jù)包所減少的失真作為瞬時(shí)報(bào)酬，視頻質(zhì)量最優(yōu)等價(jià)于所有M個(gè)用戶的視頻失真總和最小；

采取行動(dòng)a后的狀態(tài)轉(zhuǎn)移概率已知，瞬時(shí)報(bào)酬r(s，a)可以通過下式計(jì)算

；

(2-5)、觀察集合：O表示AP能觀察到的觀察集合，O＝{ACK，NAK}，o(t)＝{o₁(t)，o₂(t)，…，o_M(t)}表示在t時(shí)刻M個(gè)用戶的聯(lián)合觀察，oⁱ(t)∈{ACK，NAK}，其中

ACK：確認(rèn)收到數(shù)據(jù)包的反饋；

NAK：沒有收到數(shù)據(jù)包的反饋；

(2-6)、觀察概率：觀察結(jié)果的不確定性，觀察結(jié)果o在狀態(tài)s下采取行動(dòng)a后，用一個(gè)條件概率函數(shù)Z(s，a，o)＝pr(o?|s，a)來給出；

(3)、對(duì)可伸縮視頻流優(yōu)化調(diào)度：假設(shè)初始信念狀態(tài)為：?設(shè)定第2^M×L個(gè)狀態(tài)為所有接收者成功接收到所有數(shù)據(jù)包的目標(biāo)狀態(tài)，針對(duì)某一幀數(shù)據(jù)包的具體調(diào)度步驟如下：

(3-1)、部分可觀測(cè)馬爾可夫決策過程的參數(shù)輸入：初始信念狀態(tài)?

(3-2)、選擇需要發(fā)送的數(shù)據(jù)包：在每一個(gè)時(shí)隙內(nèi)AP通過下式選擇需要發(fā)送的數(shù)據(jù)包，

其中∏₁(b₀，t₀)表示一步部分可觀測(cè)馬爾可夫決策過程需要發(fā)送的最優(yōu)數(shù)據(jù)包；?表示t₀時(shí)刻在初始信念為b₀的情況下，發(fā)送第k個(gè)數(shù)據(jù)包后第m個(gè)用戶獲得的一步失真減少；Ω(t)表示在t時(shí)刻需要發(fā)送的數(shù)據(jù)包的集合，初始時(shí)刻的Ω(t₀)＝{1，2，…，L}；

(3-3)、信念狀態(tài)更新一次：每發(fā)送一個(gè)數(shù)據(jù)包，進(jìn)行一次聯(lián)合觀察o，o(t)＝{o₁(t)，o₂(t)，…，o_M(t)}，其中o_i(t)∈{ACK，NAK}，系統(tǒng)發(fā)生狀態(tài)轉(zhuǎn)移，從狀態(tài)s_i轉(zhuǎn)移到狀態(tài)s_j，根據(jù)接收到的反饋的不同，s_j的取值一共有2^M種情況，即?的一次更新過程如下：

收益值為：

H₁(b₀，t₀)表示一步部分可觀測(cè)馬爾可夫決策過程的收益值，每發(fā)送一次，概率更新一次，狀態(tài)的確定度越來越大；

(3-4)、判斷發(fā)送時(shí)隙n是否大于最大發(fā)送時(shí)隙數(shù)N，若大于，則轉(zhuǎn)移到下一幀的數(shù)據(jù)包?進(jìn)行發(fā)送；否則接著發(fā)送此幀的數(shù)據(jù)包。經(jīng)過n步后，部分可觀測(cè)馬爾可夫決策過程的最大失真減少及其最優(yōu)策略分別如下：

經(jīng)過N個(gè)時(shí)隙后轉(zhuǎn)移到下一幀數(shù)據(jù)包的調(diào)度，直至H幀的視頻流的數(shù)據(jù)包調(diào)度完成。?