【文章內容簡介】 播服務器可以根據這些數(shù)據特征來更加合理地進行數(shù)據調度，從而能夠有效地降低實時事務的失敗率。在按需廣播模式中，每個調度數(shù)據只廣播一次，它并不考慮數(shù)據的請求頻率等信息，從而不能滿足將來事務的數(shù)據請求，即不能有效的將數(shù)據請求滿足在請求發(fā)出之前。在系統(tǒng)負荷較大的情況下，事務的失敗率仍然較高。 混合廣播模式混合廣播模式中上行信道的用途與按需廣播的相同，用于傳送移動客戶的事務及數(shù)據請求。不同點是下行信道被分為周期廣播和按需廣播兩部分。[23]所示。上行信道下行信道周期廣播按需廣播 混合廣播模式的帶寬分配該模式的最大特點是通過上行信道收集移動客戶的動態(tài)數(shù)據請求信息，并以此為依據，不斷地調整周期廣播的序列內容，從而盡可能地多滿足最多用戶的數(shù)據訪問需求，以此來減少用戶與服務器之間的通信。而對于不能在周期廣播中滿足的數(shù)據請求，將在按需廣播時段廣播。周期廣播的采用既可以減少上行信道的負荷，又能最大限度地利用下行廣播的帶寬，使廣播優(yōu)勢發(fā)揮得最好。但混合數(shù)據廣播的實現(xiàn)比周期數(shù)據廣播和按需數(shù)據廣播更加復雜。具體有以下兩個難點：（1） 如何分配周期廣播和按需數(shù)據廣播的帶寬，從而使信道達到最大的利用率，以及達到最高的事務成功率。因為數(shù)據的請求模式等數(shù)據特征會隨著時間的變化而動態(tài)變化，所以優(yōu)良的混合廣播調度策略應該可以基于這些變化，動態(tài)地調整帶寬的分配比例。（2） 如何獲取有效的數(shù)據請求模式。由于移動客戶的部分數(shù)據請求在周期廣播中已得到滿足，所以這些請求可能不會到達服務器，從而服務器也無法獲取有效的數(shù)據請求模式，導致數(shù)據的請求模式不再有效，進而影響后繼周期廣播的數(shù)據調度。一般使用采樣技術來獲取這些“熱點數(shù)據”的請求模式。 實時數(shù)據的特征實時數(shù)據庫中數(shù)據具有豐富的類型特征，[41]所示，這些不同特征的數(shù)據在移動環(huán)境中要求有不同的管理機制。數(shù)據特征實時性存取頻率關鍵性持久性非實時實時短有效期長有效期高頻低頻關鍵非關鍵臨時永久 實時數(shù)據庫系統(tǒng)中的數(shù)據特征實時數(shù)據與非實時數(shù)據：傳統(tǒng)數(shù)據庫系統(tǒng)中的數(shù)據屬于非實時數(shù)據，這種類型數(shù)據時間的流失不影響數(shù)據的合法性。實時數(shù)據具有一個外部有效期 evi（External Valid Internal）[37]，數(shù)據僅在此期間內有效。當 evi 很長時稱為長有效期數(shù)據，當 evi 很短時稱為短有效期數(shù)據。數(shù)據的時限由數(shù)據的本身有效期和事務的時限決定。設 Dvi 為數(shù)據的有效期，Tvi 為事務的時限，則用戶要求的數(shù)據的有效期 Devi = Dvi∩Tvi[37]。高頻數(shù)據和低頻數(shù)據：高頻數(shù)據即通常所說的熱點數(shù)據，這類數(shù)據由于經常被移動客戶請求，應將他們緩存在移動主機中，或通過廣播發(fā)送。而低頻數(shù)據則可在需要時臨時傳送。關鍵數(shù)據與非關鍵數(shù)據：關鍵數(shù)據對應著高優(yōu)先級，應優(yōu)先被調度。持久性數(shù)據與非持久數(shù)據：持久數(shù)據是要進行長久保存和歸檔的數(shù)據，這類數(shù)據經常被許多移動客戶請求，因此當在移動客戶上產生或更新后，必須提交給服務器保存。以上各種數(shù)據特性可以交叉組合，從而使移動實時數(shù)據庫中數(shù)據具有復雜性，實時數(shù)據廣播模型一定要有利于反映數(shù)據實時性、優(yōu)先級以及存取模式等特性。 實時數(shù)據廣播模型，一個無線廣播單元由一個移動支持基站（MSS）和由該MSS覆蓋的所有移動客戶（MC）構成。移動客戶與MSS通過無線信道通信，MSS即為廣播服務器。每個無線廣播單元具有廣播的獨立性。本文的研究只基于一個無線廣播單元，本文忽略數(shù)據及事務的分布等因素對廣播調度的影響。文獻[37]提出一種實時數(shù)據廣播模型，移動客戶利用上行信道向廣播服務器提出數(shù)據請求。廣播服務器響應用戶請求，將移動客戶所需數(shù)據組織在廣播通道中，利用下行信道廣播數(shù)據。該模型的設計基于按需廣播模式，它不僅識別移動客戶提出的請求，同時將數(shù)據以廣播的方式發(fā)布，發(fā)揮了廣播通信的優(yōu)勢，使通信帶寬具有可伸縮性。結合文獻[37]給出的模型，該模型采用混合數(shù)據廣播模式。廣播服務器在下行信道的周期廣播帶寬中，廣播“熱點數(shù)據”，在按需廣播帶寬中響應移動客戶的實時數(shù)據請求。……周期廣播 | 按需廣播接收調度請求隊列就緒隊列廣播數(shù)據請求數(shù)據庫數(shù)據請求模式集 實時數(shù)據廣播模型信道該實時數(shù)據廣播模型分為接收、調度和廣播三個模塊。接受模塊負責接收移動客戶的數(shù)據請求，將這些請求按照截止期或其它數(shù)據特征排隊于請求隊列中；調度模塊負責根據當前請求隊列數(shù)據以及數(shù)據請求模式來調度數(shù)據，并將被調度數(shù)據存儲在就緒隊列中，調度分為周期廣播調度和按需廣播調度；同時調度模塊根據請求隊列數(shù)據來更新數(shù)據請求模式（通過采樣技術完成）；廣播模塊負責周期性地廣播就緒隊列中的數(shù)據。一個有效的數(shù)據廣播模型不僅要滿足用戶對數(shù)據的時間限制要求，還要利用數(shù)據廣播技術分發(fā)數(shù)據，有效地利用通信帶寬，滿足最多用戶的數(shù)據需求。：（1） 采用混合數(shù)據廣播模式：用戶通過上行信道上傳請求，從而能夠使服務器獲取事務及數(shù)據的時間限制，進而能夠更好地滿足這些時間限制；服務器通過下行信道周期性的廣播數(shù)據，從而發(fā)揮了廣播通信的優(yōu)勢，使通信帶寬具有較大地伸縮性。（2） 采用數(shù)據請求模式集：調度模塊根據這些請求模式能夠更加合理的調度數(shù)據，廣播“熱點數(shù)據”，以滿足更多用戶的數(shù)據需求。（3） 上行信道，數(shù)據請求模式集，下行信道三者形成一個良性互動的生態(tài)圈：服務器根據上行信道的數(shù)據請求來更新數(shù)據請求模式集，以使這些模式趨向于實際模式；下行信道的周期廣播根據這些請求模式生成，從而使數(shù)據調度具有較強的合理性；有效的周期廣播能夠極大地滿足移動客戶的數(shù)據需求，從而降低了上行信道的負荷。 研究中的假設為了便于研究，對廣播模型及廣播環(huán)境作了一些限制，下面是一些基本的假設：（1） 移動客戶對廣播數(shù)據訪問的獨立性：服務器向移動客戶廣播時所基于的通信網絡具有固定的廣播能力，即被廣播的數(shù)據對所有的移動客戶機都是可同時訪問的，各個移動客戶之間互不干擾。并且移動客戶的前后數(shù)據請求具有相互獨立性。（2） 廣播數(shù)據格式的一致性：廣播數(shù)據的最小單位是數(shù)據項，且所有被廣播的數(shù)據項都是等長度的。在實際應用中，這些數(shù)據項可以是關系數(shù)據庫中的記錄、面向對象數(shù)據庫中的對象，或者是數(shù)據庫中的一個存儲頁面。（3） 廣播數(shù)據項的自我識別性：即移動客戶通過收任意一個數(shù)據項可以知道它是不是自己所要訪問的數(shù)據項。這可以通過在每個廣播數(shù)據項之前插入適當?shù)念^標識來實現(xiàn)。（4） 廣播數(shù)據項以主鍵標識其唯一性：即每個廣播數(shù)據項擁有一個主鍵，它能夠唯一地標識一個數(shù)據項，并且移動客戶機總是根據主鍵來訪問數(shù)據廣播中的數(shù)據項。（5） 廣播數(shù)據項地址的確定：定義一個數(shù)據項在數(shù)據廣播中的地址為該數(shù)據項在廣播信道中到達的偏移時間。假定數(shù)據廣播信道具有固定的網絡帶寬，且廣播一個數(shù)據項的時間為單位時間 l，則當移動客戶從一個廣播周期起始處開始接聽時，后續(xù)每個廣播數(shù)據項的地址依次為 1，2，3，……。（6） 數(shù)據庫的一致性假設：數(shù)據庫的一致性以一個廣播周期為單位，即：如果在一個廣播周期內發(fā)生了數(shù)據庫的更新，則更新結果將在下一個廣播周期內反映出來。 小結本章首先介紹了近年來在數(shù)據廣播技術研究中流行的數(shù)據廣播模式，然后給出實時環(huán)境中數(shù)據的新特征，最后提出一種基于混合廣播模式的實時廣播模型，該模型能夠綜合考慮了數(shù)據的實時性及請求頻度等特征，最后本章給出數(shù)據廣播研究中的一些系統(tǒng)假設。實時數(shù)據廣播模型的提出，為本文進一步的調度策略研究提供有效的基礎設施。4 一種改進的自適應混合廣播調度策略在實時環(huán)境下，數(shù)據和事務往往具有時間限制，超過請求的時限，事務將會夭折，數(shù)據將會貶值，有時甚至會帶來災難性的后果；同時，在實際應用中，數(shù)據一般具有一定的請求模式，廣播調度應該充分利用這些模式，廣播“熱點數(shù)據”，以滿足更多用戶的數(shù)據需求。由本文前述可知，混合廣播調度結合按需廣播與周期廣播的優(yōu)點，能夠較好地滿足這些應用需求，但它的實現(xiàn)面臨如下兩個難點：（1）如何高效合理地分配周期廣播和按需數(shù)據廣播的帶寬比例；（2）如何獲取有效的數(shù)據請求模式。文獻[10]提出一種自適應混合廣播調度策略TCAHB(Time Critical Adaptive Hybrid Broadcast)，該策略能夠根據數(shù)據的請求模式及數(shù)據的截止期等信息動態(tài)調整帶寬分配，并且該策略使用采樣技術來獲取“熱點數(shù)據”的請求模式。由TCAHB的性能分析可知，該策略在一定程度上解決了上述混合廣播實現(xiàn)中的兩個難點問題。本章在TCAHB調度策略的基礎上，提出一種改進的TCAHB策略（Improved TCAHB）。該改進策略將TCAHB推廣到基于事務的廣播調度中，并且它采用“分布式周期廣播”思想，以解決過長的周期廣播與事務及數(shù)據實時要求之間的矛盾。理論分析及實驗表明，該改進能夠進一步降低事務的失敗率，同時減輕上行信道的通信負荷。，包括周期廣播與按需廣播的數(shù)據調度，采樣技術的實施；，提出改進方向，給出Improved TCAHB調度策略的實現(xiàn)。 TCAHB調度策略 參數(shù)描述（1） 周期廣播帶寬比例BW，帶寬比例閾值BW_Threshold在每一廣播周期中，周期廣播占整個廣播周期的比例為BW，該比例的上限為BW_Threshold。上限閾值的采用，使得按需廣播的帶寬得到了有效的保證，從而在一定程度上保證了實時但非“熱點”數(shù)據的及時調度。（2） 數(shù)據項i的帶寬需求BW_Requiredi在數(shù)據項i被實時調度的前提下，廣播數(shù)據項i所用帶寬的下限。其中，Di為數(shù)據項i的相對截止期，Si為數(shù)據項i的長度，其單位長度為“廣播帶寬s”。（3） 數(shù)據項i的請求數(shù)Requests_Receivedi在上一廣播周期中，對數(shù)據項i的請求總次數(shù)。該值描述數(shù)據的“熱點”性質。（4） 數(shù)據項i的優(yōu)先級Priorityi在數(shù)據項i被選擇進入周期調度之前，需要進行排隊，在滿足其它選擇條件下，處于隊列前端的數(shù)據項優(yōu)先進入周期廣播調度集合中。該值是周期廣播中數(shù)據項是否被調度的第一層過濾標準。它綜合考慮了數(shù)據的請求頻率、截止期、數(shù)據大小等特性。（5） 時刻t數(shù)據項i的被調度次數(shù)Allocated(i, t)在本次調度中，截至相對時刻t，數(shù)據項i已占有的時間槽。為保證有限的周期廣播帶寬不被浪費，需滿足下述約束：當不滿足該式時，時間槽t將不會分配給數(shù)據項i。其中T = TtotalBW，Ttotal為廣播周期的長度。（6） 時刻t數(shù)據項i的偽截止期Pseudodeadline(i, t)在本次調度中，時間槽t分配給在時刻t處具有最小偽截止期的數(shù)據項。該偽截止期綜合考慮了防止帶寬浪費的原則以及數(shù)據的緊迫性要求。 周期廣播的數(shù)據調度參數(shù)（1）至（4）在上一廣播周期結束，本次調度之前計算，參數(shù)(5)（6）在每分配一個時間槽時計算一次。同時，周期廣播調度部分需要下述兩個全局存儲結構：（1）待調度數(shù)據集PendingScheduleDataSet：它用來存儲上一廣播周期的調度數(shù)據集，以及當前請求隊列中的數(shù)據項。（2）調度數(shù)據集ScheduledDataSet：它用來存儲在本次周期廣播中即將被調度的數(shù)據項。TCAHB策略保證，已納入調度數(shù)據集的數(shù)據項i，在Di時間長度上，它至少會被調度一次。周期廣播部分的調度策略分以下兩步：（1） 計算調度數(shù)據集ScheduledDataSet和周期廣播帶寬比例BW：圖 其中CutoffThresholdi為數(shù)據項i上次周期廣播的長度與相對截止期Di的比值。該閾值說明：只有數(shù)據項i的請求數(shù)超過數(shù)據項i在上一個廣播周期中的最小調度次數(shù)時，該數(shù)據項i才有被再次調度的意義。（2） 分配時間槽（周期廣播數(shù)據調度）令所有數(shù)據項的Allocated = 0；For t = 1 to T 計算ScheduledDataSet中所有數(shù)據項的偽截止期Pseudodeadline； 選取Pseudodeadline最小且滿足Allocated(i)247。BW_Requiredi = t的數(shù)據項i； 將數(shù)據項i的游標指向的數(shù)據段放入時間槽t中；游標后移或置首位；Allocated(i)++；End for由于數(shù)據項變長，所以將數(shù)據項切分為一系列等長數(shù)據段。每一數(shù)據項由一個游標指示即將被調度的數(shù)據段，初始游標在首數(shù)據段。令T = TtotalBW。分配時間槽算法如下： 按需廣播的數(shù)據調度對于待調度數(shù)據集PendingScheduleDataSet中的剩余數(shù)據，TCAHB策略采用EDFBatch（Earliest Deadline First with Batch）[23]進行調度。由于周期帶寬比例上限閾值BW_Threshold的采用，部分請求的實時性需求在此按需廣播周期中得到滿足。 數(shù)據請求模式的采樣技術TCAHB調度策略的采樣思想為：在周期廣播的末端，阻塞那些有可能被剔除出調度數(shù)據集ScheduledDataSet的“熱點數(shù)據”的調度，部分用戶由于無法在這一時段獲取這些“熱點數(shù)據”，從而通過上行信道提出請求，請求到達廣播服務器，調度模塊獲取這些請求，通過這些請求以及采樣時間等參數(shù)來估算數(shù)據項的請求模式。在每一廣播周期，調度數(shù)據集ScheduledDataSet中數(shù)據項的請求頻率都將有一衰減。從而保證某些“熱點數(shù)據”存在被剔除出調度數(shù)據集的可能性，又保證了這些請求模式的光滑延續(xù)性。如何確定采樣時間長度，是一關系到采樣精確度的重要因素。TCAHB策略對數(shù)據項i的采樣時間估計由下列公式確定：其中BL（=Ttotal）為廣播周期長度，Expected_Sample_Sizei為服務器對被采樣數(shù)據項i的期望請求數(shù)。經過Sampling_Timei之后，估計數(shù)據項的請求數(shù)如下：其中Actural_Sample_Sizei為服務器在采樣時間內獲取的被采樣數(shù)據項i的實際請求數(shù)。 TCAHB調度策略的性能分析及改進措施，周期廣播的帶寬比例在BW_Threshold的約束下，可以自適應動態(tài)調整。調整依據為當前待調度數(shù)據集中數(shù)據項