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