多信道數(shù)據(jù)廣播系統(tǒng)的實時多數(shù)據(jù)項請求調度.pdf

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

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

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

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

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

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

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