[發(fā)明專利]一種基于新貪心策略的按需服務(wù)數(shù)據(jù)包調(diào)度貪心算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201611019367.3
• 申請(qǐng)日: 2016-11-17
• 公開（公告）號(hào): CN106713173A
• 公開（公告）日: 2017-05-24
• 發(fā)明（設(shè)計(jì)）人: 高振國(guó);孫鵬;姚念民;盧志茂;陳炳才;譚國(guó)真
• 申請(qǐng)（專利權(quán)）人: 大連理工大學(xué)
• 主分類號(hào): H04L12/863
• 分類號(hào): H04L12/863;H04L29/08;H04L12/24
• 代理公司: 大連理工大學(xué)專利中心21200
• 代理人: 梅洪玉

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)無線通信技術(shù)領(lǐng)域，涉及在基站集成無線網(wǎng)絡(luò)環(huán)境下,一種基于新貪心策略的按需服務(wù)數(shù)據(jù)包調(diào)度貪心算法。

背景技術(shù)

本文應(yīng)用一種基于信息站的三層網(wǎng)絡(luò)架構(gòu)，即內(nèi)容服務(wù)器，信息站(路邊通信單元)和車載設(shè)備(用戶)，系統(tǒng)中的網(wǎng)絡(luò)數(shù)據(jù)服務(wù)方式為按需服務(wù)方式。這種網(wǎng)絡(luò)架構(gòu)和服務(wù)方式現(xiàn)在已經(jīng)廣泛應(yīng)用于服務(wù)高速列車乘客的網(wǎng)絡(luò)需求和V2X車聯(lián)網(wǎng)系統(tǒng)通信中。在該系統(tǒng)中，基站通過穩(wěn)定的網(wǎng)絡(luò)連接與內(nèi)容服務(wù)器相連，當(dāng)車載設(shè)備(用戶)按照需求請(qǐng)求數(shù)據(jù)服務(wù)時(shí)，數(shù)據(jù)報(bào)文將通過基站與車載設(shè)備或終端(手機(jī)，電腦等)之間的無線信道調(diào)度和分配給用戶。

為了滿足車輛在告訴行駛過程中基站與車輛通信的需求，克服開普勒效應(yīng)等對(duì)網(wǎng)絡(luò)通信的影響，有學(xué)者提出一種專門用于基站與車載設(shè)備通信的MAC幀結(jié)構(gòu)。這種結(jié)構(gòu)下，每個(gè)時(shí)間區(qū)間被分為時(shí)間間隔相等的用于信息傳播的時(shí)隙，時(shí)間間隔小于信道相干時(shí)間(channel coherence time)，劃分的每個(gè)時(shí)隙的信道增益是固定的，但是由于信號(hào)衰減等原因，時(shí)隙的容量會(huì)因不同的情況而有所差異。考慮時(shí)隙中信道增益等信道信息，應(yīng)用自適應(yīng)調(diào)制和編碼技術(shù)，每個(gè)時(shí)隙可以發(fā)送的數(shù)據(jù)包數(shù)量上限可以得出。

考慮網(wǎng)絡(luò)通信的質(zhì)量，為了滿足用戶良好的網(wǎng)絡(luò)體驗(yàn)，高質(zhì)量、低延遲、低丟包率等要求是基站調(diào)度數(shù)據(jù)包時(shí)要追求的目標(biāo)。Mohit Agarwal和Anuj Puri在2002年的論文中提出了一種服務(wù)請(qǐng)求模型。在按需請(qǐng)求數(shù)據(jù)服務(wù)下，用戶愿意為不同的服務(wù)付出的代價(jià)也是不同，另外由于用戶之間的差異，不同用戶愿意為請(qǐng)求服務(wù)支付的價(jià)格也不盡相同，怎樣合理高效利用信道，在上述幀結(jié)構(gòu)下合理調(diào)度服務(wù)數(shù)據(jù)，使得調(diào)度的服務(wù)數(shù)據(jù)獲得最大價(jià)值，使得服務(wù)運(yùn)營(yíng)商或提供者獲得最大收益也是一種很重要的目標(biāo)。基于該目標(biāo)，該調(diào)度問題將被轉(zhuǎn)化為一個(gè)搶占式單機(jī)調(diào)度問題，本發(fā)明的目標(biāo)就是如此。

現(xiàn)在已經(jīng)有學(xué)者將上述問題轉(zhuǎn)化為目標(biāo)函數(shù)為一個(gè)整數(shù)最優(yōu)規(guī)劃的問題，能夠證明求解該整數(shù)最優(yōu)規(guī)劃問題是一個(gè)NP困難的問題，不能在線性時(shí)間內(nèi)找到最優(yōu)解。

很多學(xué)者提出了很多解決上述問題的算法,例如EDF算法，F(xiàn)IFO算法，還有基于其他效用函數(shù)(例如指數(shù)容量等)的貪心算法，但是目前算法得到的效果普遍不高，還有可以優(yōu)化的余地。

發(fā)明內(nèi)容

為解決現(xiàn)有技術(shù)中存在的問題，本發(fā)明提出一種基于新貪心策略的按需服務(wù)數(shù)據(jù)包調(diào)度貪心算法，將按需服務(wù)的數(shù)據(jù)包調(diào)度問題轉(zhuǎn)化為整數(shù)最優(yōu)規(guī)劃問題，進(jìn)而轉(zhuǎn)化為0-1最優(yōu)規(guī)劃問題，利用貪心算法依照提出的效用函數(shù)值作為貪心策略對(duì)該問題進(jìn)行優(yōu)化求解。

本發(fā)明所采用的技術(shù)方案是按照以下步驟進(jìn)行：

步驟一，將按需服務(wù)的數(shù)據(jù)包調(diào)度問題轉(zhuǎn)化為整數(shù)最優(yōu)規(guī)劃問題；

1)建立時(shí)隙模型；

和表示網(wǎng)絡(luò)用戶進(jìn)入和離開信息站h,h＝1,2,…,H的傳輸范圍的時(shí)刻，時(shí)間在每個(gè)間隔期間內(nèi)被等分為時(shí)長(zhǎng)T_F的時(shí)隙，第H信息站覆蓋的區(qū)域分為個(gè)時(shí)隙，用于數(shù)據(jù)傳輸?shù)臅r(shí)隙總數(shù)確定在信息站每時(shí)隙內(nèi)的最大數(shù)據(jù)包傳輸數(shù)量C_n,n＝1,2,…,N。

2)建立服務(wù)請(qǐng)求模型；

設(shè)用戶服務(wù)請(qǐng)求集合為S，S中的每個(gè)服務(wù)請(qǐng)求s(s∈S)表示為一個(gè)四元組：

(G_s,Q_s,D_s,W_s(n))(1)

其中，Q_s為每個(gè)服務(wù)需要被調(diào)度的數(shù)據(jù)包數(shù)量，G_s為每個(gè)服務(wù)的到達(dá)時(shí)間，D_s為該服務(wù)的最晚調(diào)度時(shí)間，W_s(n)為收益，其中n為該數(shù)據(jù)包的發(fā)送時(shí)隙；如果該服務(wù)的請(qǐng)求在它的生命周期[G_s,D_s]內(nèi)被調(diào)度，那么該請(qǐng)求的每一個(gè)數(shù)據(jù)包將會(huì)獲得一定收益，否則將不會(huì)獲得收益。

3)將問題轉(zhuǎn)化為求解最優(yōu)整數(shù)規(guī)劃問題；

令x_ns表示請(qǐng)求s在時(shí)隙n內(nèi)發(fā)送數(shù)據(jù)包的數(shù)量，則調(diào)度方案表示為向量該調(diào)度方案將調(diào)度產(chǎn)生的總收益表示為如下目標(biāo)函數(shù)：

其中，

其中，(2a)表示，數(shù)據(jù)包只能在服務(wù)的生命周期內(nèi)才能被調(diào)度和分配，超出生命周期的數(shù)據(jù)包無效，且被調(diào)度數(shù)據(jù)包的數(shù)量只能為整數(shù)；(2b)表示在每個(gè)時(shí)隙內(nèi)調(diào)度的數(shù)據(jù)包數(shù)量不能超過該時(shí)隙能發(fā)送的數(shù)據(jù)包數(shù)量的上限；(2c)則表示每個(gè)服務(wù)被調(diào)度數(shù)據(jù)包的數(shù)量不能超過該服務(wù)需調(diào)度數(shù)據(jù)包數(shù)量的上限。