多信道數(shù)據(jù)廣播系統(tǒng)的實(shí)時(shí)多數(shù)據(jù)項(xiàng)請(qǐng)求調(diào)度.pdf

1、數(shù)據(jù)廣播是一種被廣泛接受的用于動(dòng)態(tài)和可擴(kuò)展的無(wú)線信息分發(fā)的方法。隨著數(shù)據(jù)廣播系統(tǒng)中移動(dòng)用戶和實(shí)時(shí)應(yīng)用數(shù)量的快速增長(zhǎng)，來(lái)自客戶端的實(shí)時(shí)數(shù)據(jù)需求變得更加棘手。而且，大規(guī)模數(shù)據(jù)需求導(dǎo)致服務(wù)器端需要大規(guī)模數(shù)據(jù)庫(kù)。因而，基于推的廣播調(diào)度程序不能獲取最優(yōu)的性能。因?yàn)檫@種廣播是基于歷史的數(shù)據(jù)訪問(wèn)統(tǒng)計(jì)數(shù)據(jù)或者預(yù)定義的請(qǐng)求配置文件的靜態(tài)的數(shù)據(jù)廣播。因此，按需廣播比基于推的廣播更適合此種情況。然而，按需廣播需要在線的數(shù)據(jù)調(diào)度。這是很難獲得最優(yōu)或接近最優(yōu)的性

2、能的。其次，在一些緊急的應(yīng)用中，比如道路交通導(dǎo)航系統(tǒng)，客戶端可能同時(shí)請(qǐng)求不止一個(gè)相互依賴的數(shù)據(jù)項(xiàng)。因此，對(duì)于實(shí)時(shí)按需數(shù)據(jù)廣播系統(tǒng)，這樣的多數(shù)據(jù)項(xiàng)請(qǐng)求在有截止期限制的條件下將使得數(shù)據(jù)調(diào)度算法的設(shè)計(jì)更為復(fù)雜。第三，雖然已有的多信道結(jié)構(gòu)增加了滿足大數(shù)據(jù)需求的可用帶寬，但是因?yàn)橐粋€(gè)客戶端在一個(gè)時(shí)間僅能從一個(gè)信道獲取一個(gè)數(shù)據(jù)項(xiàng)，所以多信道結(jié)構(gòu)也增加了客戶端在多信道之間的帶寬共享的難度?；谝陨戏治觯绾卧O(shè)計(jì)一個(gè)好的數(shù)據(jù)調(diào)度算法是實(shí)時(shí)按需數(shù)據(jù)廣播系

3、統(tǒng)的核心部分。
　　 隨著實(shí)時(shí)應(yīng)用的增加，在調(diào)度多數(shù)據(jù)項(xiàng)請(qǐng)求時(shí)最小化請(qǐng)求截止期錯(cuò)過(guò)率已經(jīng)成為一項(xiàng)重要的任務(wù)。在本文中，我們證明在單信道和多信道數(shù)據(jù)廣播環(huán)境下調(diào)度實(shí)時(shí)多數(shù)據(jù)項(xiàng)請(qǐng)求的NP難度。而且，我們分別針對(duì)單信道和多信道結(jié)構(gòu)提出兩種基于profit的調(diào)度算法，PVC和SSA。兩種算法都利用了我們提出的兩個(gè)概念。一個(gè)是需求數(shù)據(jù)項(xiàng)的“profit”（利潤(rùn)），另一個(gè)是待滿足請(qǐng)求的“opportunity cost”（機(jī)會(huì)成本）。據(jù)我們

4、所知，這是第一次在按需廣播調(diào)度中引入來(lái)自經(jīng)濟(jì)學(xué)中的機(jī)會(huì)成本。根據(jù)由PVC做出的調(diào)度決策，SSA將調(diào)度到的請(qǐng)求中的數(shù)據(jù)項(xiàng)分配到可用信道上。總體上，單信道調(diào)度中PVC在請(qǐng)求截止期錯(cuò)過(guò)率方面優(yōu)于其它算法。多信道調(diào)度中SSA在請(qǐng)求截止期錯(cuò)過(guò)率方面隨著信道數(shù)的增加比其它算法具有更大的優(yōu)勢(shì)。此外，在總帶寬相同條件下，仿真實(shí)驗(yàn)結(jié)果表明，在單信道環(huán)境下調(diào)度比在多信道環(huán)境下調(diào)度具有更好的實(shí)時(shí)性能，即請(qǐng)求截止期錯(cuò)過(guò)率。這啟發(fā)我們通過(guò)理論建模比較這兩種調(diào)度。

5、理論結(jié)果表明，在總帶寬相同條件下，單信道調(diào)度比多信道調(diào)度有更好的平均周轉(zhuǎn)時(shí)間。
　　 據(jù)我們所知，雖然在有線網(wǎng)絡(luò)和無(wú)線網(wǎng)絡(luò)中已經(jīng)有多種面向連接的接入控制的工作，但是在實(shí)時(shí)數(shù)據(jù)廣播系統(tǒng)中尚未有接入控制的探索。在無(wú)線的移動(dòng)網(wǎng)絡(luò)環(huán)境中，由于數(shù)據(jù)廣播一次響應(yīng)能夠滿足包含相同數(shù)據(jù)項(xiàng)的眾多請(qǐng)求，這一潛在優(yōu)勢(shì)使得它成為越來(lái)越受歡迎的信息分發(fā)方法。此外，數(shù)據(jù)廣播能夠容納任意多的具有相同興趣的客戶端。在實(shí)時(shí)應(yīng)用中，所有請(qǐng)求有截止期限制，即錯(cuò)過(guò)截止

6、期即意味請(qǐng)求的失敗。然而，在沒(méi)有接入控制條件下，客戶端必須等待接收它們所需要的數(shù)據(jù)項(xiàng)直到請(qǐng)求截止期失效。如果請(qǐng)求最終失敗，客戶端電池的能量和時(shí)間都將被浪費(fèi)。此外，在請(qǐng)求提交時(shí)，客戶端不知道它們提交的請(qǐng)求能否得到滿足，這將降低客戶體驗(yàn)和服務(wù)吸引力。為了減少失敗請(qǐng)求的不必要的等待時(shí)間并提供客戶端一定的QoS(服務(wù)質(zhì)量)保證，我們?cè)趯?shí)時(shí)數(shù)據(jù)廣播系統(tǒng)中引入廣播接入控制。請(qǐng)求提交后，請(qǐng)求的數(shù)據(jù)項(xiàng)將被分配到信道中，如果分配不可行，請(qǐng)求將提前被拒絕。

7、
　　 然而，通過(guò)構(gòu)建廣播接入控制的子問(wèn)題，即團(tuán)問(wèn)題，我們證明以最大化帶寬共享為目標(biāo)的實(shí)時(shí)多數(shù)據(jù)項(xiàng)請(qǐng)求的廣播接入控制問(wèn)題是NP（非確定性多項(xiàng)式，non-deterministic polynomial）難的問(wèn)題。之后，我們提出一個(gè)簡(jiǎn)化的接入控制算法，稱為數(shù)據(jù)項(xiàng)層接入控制(Item Level Admission Control，ILAC)。在接入控制之后，為了達(dá)到帶寬共享的最大化，信道分配問(wèn)題被模型化為二部圖的最大帶權(quán)匹配問(wèn)題并