[發(fā)明專利]一種基于馬爾科夫決策過程的移動(dòng)數(shù)據(jù)分流方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711373579.6
• 申請(qǐng)日: 2017-12-19
• 公開（公告）號(hào): CN108093425A
• 公開（公告）日: 2018-05-29
• 發(fā)明（設(shè)計(jì)）人: 張成;張險(xiǎn)峰;陳慶武
• 申請(qǐng)（專利權(quán)）人: 中山米來機(jī)器人科技有限公司
• 主分類號(hào): H04W24/06
• 分類號(hào): H04W24/06;H04W28/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于馬爾科夫決策過程的移動(dòng)數(shù)據(jù)分流方法，包括以下步驟(1)移動(dòng)數(shù)據(jù)分流的馬爾科夫模型；(2)一種動(dòng)態(tài)優(yōu)化決策算法；(3)一種低時(shí)間復(fù)雜度的啟發(fā)式分流算法，其特征在于：

步驟(1)移動(dòng)數(shù)據(jù)分流的馬爾科夫模型：

移動(dòng)用戶使用手機(jī)應(yīng)用進(jìn)行數(shù)據(jù)下載時(shí)，由于時(shí)間限制，當(dāng)發(fā)生網(wǎng)絡(luò)阻塞問題，為提升用戶體驗(yàn)，用戶將進(jìn)行數(shù)據(jù)分流用以解決上述問題，會(huì)自主性選擇網(wǎng)絡(luò)，考慮到手機(jī)能量消耗以及網(wǎng)絡(luò)成本；對(duì)此，進(jìn)行基于移動(dòng)數(shù)據(jù)分流的馬爾可夫決策的建模；

(1.1)模型環(huán)境：

為便于建模，步驟(1.1)對(duì)模型的使用環(huán)境進(jìn)行相關(guān)介紹：

1)MUs從遠(yuǎn)程服務(wù)器下載M個(gè)文件，并且每個(gè)文件形成數(shù)據(jù)流(Flow)，則對(duì)應(yīng)的數(shù)據(jù)流集定義為同時(shí)每個(gè)Flow都有相應(yīng)的時(shí)間限制其中T＝(T1,T2,...,TM)表示為對(duì)于MU的M個(gè)文件的時(shí)間限制向量集，為便于建模，認(rèn)為T1≤T2≤...TM并定義時(shí)間系統(tǒng)

2)為便于分析，限制MU只能在L可能性的位置移動(dòng)，對(duì)應(yīng)的位置集當(dāng)蜂窩網(wǎng)絡(luò)在上述位置集中出現(xiàn)的概率相等，而無線局域網(wǎng)出現(xiàn)的概率依賴于其位置

(1.2)馬爾科夫決策模型的建立：

當(dāng)用戶下載文件，發(fā)生網(wǎng)絡(luò)阻塞時(shí)，用戶將根據(jù)網(wǎng)絡(luò)使用成本、能量消耗以及剩余時(shí)間進(jìn)行網(wǎng)絡(luò)選擇，從而完成數(shù)據(jù)傳輸；

(1.2.1)系統(tǒng)狀態(tài)st

st＝{lt，bt}

其中表示通過GPS獲取的MUs在t時(shí)的位置指數(shù)，表示位置集；為M個(gè)文件在t時(shí)的文件下載剩余量的向量集，并且而Bj表示第j個(gè)數(shù)據(jù)流的總的文件下載剩余量，因此則表示對(duì)應(yīng)的剩余數(shù)據(jù)的向量集；

(1.2.2)用戶動(dòng)作：

用戶動(dòng)作at表示t時(shí)決定在處于無線局域網(wǎng)覆蓋時(shí)，是否使用，或者使用蜂窩網(wǎng)絡(luò)，或者繼續(xù)等待空閑以及如何對(duì)M數(shù)據(jù)流進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)率的分配，其定義如下：

at＝(at，c，at，ω)

1)其中，表示分配蜂窩網(wǎng)絡(luò)的數(shù)據(jù)率的向量集，表示對(duì)于第j個(gè)數(shù)據(jù)使用蜂窩網(wǎng)絡(luò)的分配數(shù)據(jù)率；則表示分配的無線局域網(wǎng)的數(shù)據(jù)率，而表示對(duì)于第j個(gè)數(shù)據(jù)使用無線局域網(wǎng)的分配的數(shù)據(jù)率；符號(hào)c和ω分別表示蜂窩網(wǎng)絡(luò)和無線局域網(wǎng)；如果用戶不在無線局域網(wǎng)覆蓋的范圍內(nèi)時(shí)，可能為0；

2)所有數(shù)據(jù)流使用蜂窩網(wǎng)絡(luò)和無線局域網(wǎng)的總的數(shù)據(jù)率分別定義

且at，c和at，ω需要滿足以下條件：

a t , c = γ c l a t , ω = γ ω l ]]>

其中，和分別表示在位置l時(shí)蜂窩網(wǎng)絡(luò)和無線局域網(wǎng)的最大數(shù)據(jù)率；

3)在t時(shí)有以下因素影響用戶的決策

a)網(wǎng)絡(luò)成本即用戶使用網(wǎng)絡(luò)服務(wù)的成本：網(wǎng)絡(luò)服務(wù)以基于使用量的價(jià)格計(jì)算模式，并且定義移動(dòng)網(wǎng)絡(luò)操作的價(jià)格為pc，且認(rèn)為無線局域網(wǎng)免費(fèi)使用，則網(wǎng)絡(luò)成本ct(st，at)的定義如下：

b)能量消耗：通過使用無線局域網(wǎng)或蜂窩網(wǎng)絡(luò)傳輸數(shù)據(jù)產(chǎn)生的能量消耗，其定義為：

其中，表示在位置l處使用蜂窩網(wǎng)絡(luò)的能量消耗率，表示在位置l處使用無線局域網(wǎng)的能量消耗率，且兩者都隨輸出為變小，即傳輸同等的數(shù)據(jù)量，低傳輸速度消耗更多的能量；θt表示MU在t時(shí)關(guān)注能量消耗的權(quán)重，θt值越小，表明MU對(duì)于能量消耗的關(guān)注度越小；

c)懲罰因子：如果數(shù)據(jù)傳輸沒能在時(shí)間限制內(nèi)完成，對(duì)于MU的懲罰因子其定義如下：

c ^ T j + 1 ( s T j + 1 ) = c ^ T j + 1 ( l T j + 1 , b T j + 1 ) = g ( b T j + 1 ) ]]>

上式中函數(shù)g(·)具有非負(fù)非減的特性，Tj+1表示在時(shí)間限制Tj之后計(jì)算懲罰因子；

(1.2.3)狀態(tài)轉(zhuǎn)移概率：

Pr(st+1|st，at)

上式表明如果在狀態(tài)st時(shí)進(jìn)行選擇動(dòng)作at后，狀態(tài)st+1的概率，為便于分析，假定數(shù)據(jù)傳輸?shù)氖Ｓ嗔亢臀恢酶淖兿嗷オ?dú)立，故

Pr ( s t + 1 | s t , a t ) = Pr ( ( l t + 1 , b t + 1 ) | ( l t , b t ) , a t ) = p l t + 1 , l t Pr ( b t + 1 | ( l t , b t ) , a t ) ]]>

其中

Pr ( b t + 1 | ( l t , b t ) , a t ) = 1 i f b t + 1 = [ b t - a t , c - a t , ω ] + 0 o t h e r w i s e ]]>

上式中[x]+＝max{x，0}且認(rèn)為用戶從位置lt到位置lt+1的概率已知；

(1.2.4)策略π

上式中函數(shù)φt(lt，bt)將狀態(tài)st＝(lt，bt)映射到在t時(shí)的動(dòng)作決策，策略π的集合定義為Π；如果策略π被選中，則狀態(tài)表示為

(1.3)用戶目標(biāo)函數(shù)

其目的是最小化從時(shí)間t＝1到t＝TM的總成本，包括網(wǎng)絡(luò)成本和能量消耗，且在t＝TM+1時(shí)的懲罰因子具有最優(yōu)的策略π*，如下式所示：

上式中rt(st，at)表示網(wǎng)絡(luò)成本和能量消耗的總和，其計(jì)算公式如下：

rt(st，at)＝ct(st，at)+ζt(st，at)

步驟(2)一種動(dòng)態(tài)優(yōu)化決策算法：

通過步驟(1)建立用戶選擇網(wǎng)絡(luò)和數(shù)據(jù)分配的MDP模型，其目的是為了通過做出相應(yīng)的動(dòng)作從而降低用戶成本，為此，步驟(2)采用一種動(dòng)態(tài)方法解決MDP問題。

2.如權(quán)利要求1所述的一種基于馬爾科夫決策過程的移動(dòng)數(shù)據(jù)分流方法，其特征在于：所述步驟(2)進(jìn)一步包括：

(2.1)MDP問題的最優(yōu)化函數(shù)：

定義vt(st)為用戶在狀態(tài)st處從t到TM+1的總成本的最小期望值，如下式所示：

基于上式，采用一種動(dòng)態(tài)方法解決MDP問題；

(2.2)一種動(dòng)態(tài)解決MDP問題的方法，其過程如下：

(2.2.1)最優(yōu)策略計(jì)算階段：

(2.2.2)通過等式7,建立用戶在位置l,下載剩余量b時(shí)，時(shí)間TM+1的總成本最小期望值l屬于位置集合

(2.2.3)定義時(shí)間TM等于t；

(2.2.4)當(dāng)t大于等于1時(shí)

(2.2.5)對(duì)于在時(shí)間t位置屬于集合的lt；

(2.2.6)定義時(shí)間t下載剩余量集合的向量集bt等于0；

(2.2.7)對(duì)于時(shí)間t屬于下載剩余量集合的向量集bt；

(2.2.8)用公式14計(jì)算時(shí)間t時(shí)狀態(tài)st，分配的蜂窩網(wǎng)絡(luò)的數(shù)據(jù)率at時(shí)，總成本的期望值Qt(st，at)；

(2.2.9)定義時(shí)間t時(shí)最小總成本期望值的變量值為

(2.2.10)定義時(shí)間t時(shí)最小總成本期望值vt(l，b)等于變量值與Qt的期望；

(2.2.11)定義M個(gè)文件在時(shí)間t時(shí)下載剩余量的向量集bt等于bt加上σ；

(2.2.12)結(jié)束循環(huán)；

(2.2.13)結(jié)束循環(huán)；

(2.2.14)定義時(shí)間t等于t-1；

(2.2.15)結(jié)束循環(huán)；

(2.2.16)最佳策略π*是為了接下來的分流數(shù)據(jù)傳輸策略生成的；

(2.2.17)；

(2.2.18)分流數(shù)據(jù)傳輸策略；

(2.2.19)定義時(shí)間t＝1，下載剩余量b等于文件下載剩余量集合

(2.2.20)當(dāng)時(shí)間t小于等于時(shí)間TM并且bt大于0；

(2.2.21)lt由GPS確定；

(2.2.22)根據(jù)最佳策略π*，定義用戶動(dòng)作

(2.2.23)定義bt＝[bt-at，c-at，ω]+；

(2.2.24)結(jié)束循環(huán)；

(2.2.25)定義t＝t+1；

(2.2.26)結(jié)束循環(huán)；

步驟(3)一種低時(shí)間復(fù)雜度的啟發(fā)式分流算法：

步驟(2)成功實(shí)現(xiàn)了降低用戶成本的功能；但是，其算法的時(shí)間復(fù)雜度很高；因此，步驟(2)僅作為最佳分流策略的離線算法；

針對(duì)上述問題，提出一種新的算法，實(shí)現(xiàn)兩個(gè)目標(biāo)：1.低時(shí)間復(fù)雜度；2.實(shí)時(shí)性計(jì)算；具體步驟：

(3.1.1)在時(shí)間間隙t；

(3.1.2)輸入：截止時(shí)間矢量集合T，截止時(shí)間閾值通過GPS獲取的Mus在t時(shí)的位置指數(shù)lt，M個(gè)文件在時(shí)間t時(shí)下載剩余量的向量集bt；

(3.1.3)對(duì)于屬于集合T的矢量Tj；

(3.1.4)如果t<Tj；

(3.1.5)將Tj-t添加到截止時(shí)間保留表R；

(3.1.6)定義權(quán)重等于

(3.1.7)否則；

(3.1.8)定義權(quán)重等于0；

(3.1.9)將權(quán)重添加到分配率權(quán)重列表Wt；

(3.1.10)結(jié)束循環(huán)；

(3.1.11)結(jié)束循環(huán)；

(3.1.12)標(biāo)準(zhǔn)化Wt到

(3.1.13)標(biāo)準(zhǔn)化bt到

(3.1.14)如果在位置l無線LAN網(wǎng)接入點(diǎn)可用而且速率比γth高，γth是由MUs的能量偏好定義的參數(shù)；

(3.1.15)根據(jù)分配無線LAN網(wǎng)數(shù)據(jù)接入率到每一個(gè)流；

(3.1.16)無線LAN網(wǎng)數(shù)據(jù)接入率at，w確定；

(3.1.17)如果R的最小值小于

(3.1.18)根據(jù)分配蜂窩網(wǎng)數(shù)據(jù)率到每一個(gè)流；

(3.1.19)蜂窩網(wǎng)數(shù)據(jù)接入率at，c確定；

(3.1.20)結(jié)束循環(huán)；

(3.1.21)根據(jù)at，c和at，w輸出分配的蜂窩網(wǎng)絡(luò)的數(shù)據(jù)率at；

從上述算法的結(jié)果可以看出，時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)低于算法1；并且，算法2可以作為在線算法實(shí)現(xiàn)實(shí)時(shí)計(jì)算。