一種基于需求的實(shí)時(shí)數(shù)據(jù)廣播模型

摘要:數(shù)據(jù)廣播是提高移動(dòng)計(jì)算系統(tǒng)可伸縮性的一項(xiàng)重要技術(shù)，該文提出了一種實(shí)時(shí)數(shù)據(jù)廣播模型。該模型采用數(shù)據(jù)需求驅(qū)動(dòng)機(jī)制，不僅充分考慮用戶對(duì)數(shù)據(jù)的時(shí)效要求，還利用數(shù)據(jù)廣播技術(shù)分發(fā)數(shù)據(jù)，有效地利用通信帶寬，滿足最多用戶的數(shù)據(jù)需求。

關(guān)鍵詞:移動(dòng)計(jì)算;數(shù)據(jù)廣播;實(shí)時(shí)數(shù)據(jù)

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)14-3647-02

Based on the Demand for Real-time Data Broadcasting Model

YAN Ying， ZHAO Hai-liang

(1.Hunan Communication Polytechnic， Changsha 410000， China)

Abstract: Data broadcasting is to improve the mobile computing system scalability an important technology， this paper， a real-time data broadcast model. The model used data on demand-driven mechanism， give full consideration to the user not only the timeliness of data requirements， but also use data broadcasting technologies， dissemination of data， effective use of communications bandwidth， to meet the data needs of most users.

Key words: mobile computing; data broadcast; real-time data

1 引言

移動(dòng)計(jì)算技術(shù)的快速發(fā)展使得用戶隨時(shí)隨地訪問(wèn)數(shù)據(jù)成為可能。然而，與固定網(wǎng)絡(luò)相比，支持移動(dòng)計(jì)算的無(wú)線通信具有帶寬小、通信質(zhì)量差的特點(diǎn)。為了支持大量移動(dòng)用戶并發(fā)訪問(wèn)服務(wù)器上的數(shù)據(jù)，人們提出服務(wù)器向空中廣播數(shù)據(jù)，用戶從空中獲取數(shù)據(jù)的新的數(shù)據(jù)發(fā)送模式，即數(shù)據(jù)廣播(Data Broadcast)。

數(shù)據(jù)廣播是提高移動(dòng)計(jì)算系統(tǒng)可伸縮性的一項(xiàng)重要技術(shù)，在公共信息發(fā)布、軍事應(yīng)用等領(lǐng)域有著很好的應(yīng)用前景。數(shù)據(jù)廣播使下行帶寬具有可伸縮性，可同時(shí)滿足大量用戶的數(shù)據(jù)需求而不出現(xiàn)網(wǎng)絡(luò)的擁塞。

2 數(shù)據(jù)廣播模式

在數(shù)據(jù)庫(kù)系統(tǒng)中，一些計(jì)算機(jī)是存儲(chǔ)各種數(shù)據(jù)的“倉(cāng)庫(kù)”，是數(shù)據(jù)的“提供者”，而一些計(jì)算機(jī)是數(shù)據(jù)的“消費(fèi)者”。當(dāng)“消費(fèi)者”請(qǐng)求一個(gè)數(shù)據(jù)項(xiàng)時(shí)，“提供者”必須將該數(shù)據(jù)項(xiàng)傳送給“消費(fèi)者”。在移動(dòng)計(jì)算環(huán)境中，這種數(shù)據(jù)傳送的方式可以分為三種，即純PULL方式(Pure-Pull-Based)、純PUSH方式(Pure-Push-Based)和混合(Hybrid)方式[1-2]。對(duì)應(yīng)上述三種數(shù)據(jù)分發(fā)技術(shù)，數(shù)據(jù)廣播模式一般可分為三類:周期數(shù)據(jù)廣播(Periodic Broadcast)、聯(lián)機(jī)請(qǐng)求廣播(On-Demand Broadcast)和混合數(shù)據(jù)廣播(Hybrid Broadcast)。

2.1 周期數(shù)據(jù)廣播

周期數(shù)據(jù)廣播是指系統(tǒng)利用廣播信道周期地廣播數(shù)據(jù)，用戶不能向服務(wù)器提出數(shù)據(jù)請(qǐng)求，只能被動(dòng)地接收數(shù)據(jù)，因此也被稱為靜態(tài)數(shù)據(jù)廣播。周期廣播對(duì)數(shù)據(jù)的選定是在服務(wù)器端，一旦選定，就按既定的內(nèi)容廣播。這種純PUSH技術(shù)將整個(gè)帶寬用于廣播，雖然最大限度地利用了帶寬，但這種廣播模式是盲目的，忽略了用戶的數(shù)據(jù)需求，并且不能識(shí)別用戶和事務(wù)的特征以及對(duì)數(shù)據(jù)的時(shí)限要求。

2.2 聯(lián)機(jī)請(qǐng)求廣播

聯(lián)機(jī)請(qǐng)求廣播結(jié)合PULL和PUSH技術(shù)，給定上行和下行信道，其中上行信道帶寬較低，用于傳送用戶的數(shù)據(jù)請(qǐng)求事務(wù)，下行信道用于廣播被用戶頻率申請(qǐng)的“熱點(diǎn)數(shù)據(jù)”。在聯(lián)機(jī)請(qǐng)求廣播模式中，移動(dòng)用戶在提出數(shù)據(jù)請(qǐng)求前先查詢數(shù)據(jù)廣播索引。通過(guò)索引，用戶可以獲知信道的頻率、數(shù)據(jù)項(xiàng)標(biāo)識(shí)符、解密碼、所請(qǐng)求的數(shù)據(jù)項(xiàng)在廣播中到來(lái)的時(shí)間等信息。若用戶想要訪問(wèn)的數(shù)據(jù)沒(méi)有包含在廣播信道中，或者通過(guò)廣播獲取該數(shù)據(jù)會(huì)超過(guò)時(shí)間限制，則用戶可通過(guò)上行信道發(fā)送數(shù)據(jù)請(qǐng)求給服務(wù)器。這種廣播模式，服務(wù)器不知道移動(dòng)客戶機(jī)(Mobile Client，以下簡(jiǎn)稱MC)對(duì)廣播數(shù)據(jù)項(xiàng)的訪問(wèn)概率分布，而是根據(jù)用戶的動(dòng)態(tài)需求廣播數(shù)據(jù)，有效地提高了下行信道的帶寬利用率，還可通過(guò)索引技術(shù)減少上行信道的飽和程度。

2.3 混合數(shù)據(jù)廣播

混合數(shù)據(jù)廣播中上行信道的用途與聯(lián)機(jī)請(qǐng)求廣播的相同，用于傳送用戶數(shù)據(jù)訪問(wèn)請(qǐng)求。不同點(diǎn)是下行信道被分為周期廣播和聯(lián)機(jī)請(qǐng)求廣播兩部分，信道帶寬分配如圖1所示。

混合數(shù)據(jù)廣播最大的特點(diǎn)是通過(guò)上行信道收集用戶的動(dòng)態(tài)數(shù)據(jù)請(qǐng)求信息，并以此為依據(jù)，不斷地調(diào)整周期廣播的內(nèi)容，盡可能地滿足最多用戶的數(shù)據(jù)訪問(wèn)需求，來(lái)減少用戶與服務(wù)器之間的通信。而對(duì)于不能在周期廣播中滿足的用戶數(shù)據(jù)請(qǐng)求，將通過(guò)聯(lián)機(jī)請(qǐng)求廣播?；旌蠑?shù)據(jù)廣播比較靈活，既可以減少上行信道的飽和程度，又能最大限度地利用下行廣播的帶寬，使廣播優(yōu)勢(shì)發(fā)揮得最好。但混合數(shù)據(jù)廣播的實(shí)現(xiàn)比周期數(shù)據(jù)廣播和聯(lián)機(jī)請(qǐng)求廣播更加復(fù)雜。如何根據(jù)系統(tǒng)的工作量動(dòng)態(tài)地分配周期廣播和聯(lián)機(jī)請(qǐng)求廣播帶寬，以達(dá)到系統(tǒng)最優(yōu)性能，是混合數(shù)據(jù)廣播最關(guān)鍵的問(wèn)題。

3 實(shí)時(shí)數(shù)據(jù)特性

在實(shí)時(shí)應(yīng)用環(huán)境中，數(shù)據(jù)類型非常復(fù)雜，有實(shí)時(shí)數(shù)據(jù)與非實(shí)時(shí)數(shù)據(jù)。實(shí)時(shí)數(shù)據(jù)與一外部有效期evi(External Valid Internal)相連，當(dāng)evi很長(zhǎng)時(shí)稱為長(zhǎng)時(shí)限數(shù)據(jù)，當(dāng)evi很短時(shí)稱為短時(shí)限數(shù)據(jù)。數(shù)據(jù)的時(shí)限由數(shù)據(jù)的本身有效期和事務(wù)的時(shí)限決定[3]。設(shè)Dvi為數(shù)據(jù)的有效期，Tvi為事務(wù)的時(shí)限，則用戶要求的數(shù)據(jù)的有效期Devi=Dvi∩Tvi。

同時(shí)數(shù)據(jù)時(shí)限的危急度也與事務(wù)的特性有關(guān)，硬實(shí)時(shí)事務(wù)要求數(shù)據(jù)必須在限定的時(shí)限完成，否則就會(huì)造成災(zāi)難。軟實(shí)時(shí)事務(wù)都有一個(gè)完成的最終時(shí)間期限。這個(gè)時(shí)間期限可由用戶明確定義，也可由系統(tǒng)根據(jù)QoS隱含定義。如果獲取的數(shù)據(jù)超過(guò)了時(shí)間期限，則數(shù)據(jù)的使用價(jià)值會(huì)大打折扣，所以加在數(shù)據(jù)時(shí)限上的要求相對(duì)比較寬松。

另外，根據(jù)存取頻率還分為高頻數(shù)據(jù)和低頻數(shù)據(jù)。按數(shù)據(jù)的關(guān)鍵性，可分為關(guān)鍵數(shù)據(jù)和一般數(shù)據(jù)。鑒于數(shù)據(jù)的復(fù)雜性，廣播模型一定要有利于反映數(shù)據(jù)的特性。

基于以上因素，本文提出了基于需求的實(shí)時(shí)數(shù)據(jù)廣播模型。

4 基于需求的實(shí)時(shí)數(shù)據(jù)廣播模型

移動(dòng)計(jì)算環(huán)境由若干MC和一個(gè)廣播服務(wù)器組成，MC與廣播服務(wù)器通過(guò)無(wú)線信道通信。MC利用上行信道向廣播服務(wù)器提出數(shù)據(jù)請(qǐng)求事務(wù)。廣播服務(wù)器響應(yīng)用戶請(qǐng)求，將MC所需數(shù)據(jù)組織在廣播通道中，利用下行信道廣播數(shù)據(jù)。數(shù)據(jù)廣播模型如圖2。

該數(shù)據(jù)廣播模型分為接收事務(wù)、選擇廣播內(nèi)容和調(diào)度三部分。服務(wù)器先接收用戶數(shù)據(jù)請(qǐng)求事務(wù)，儲(chǔ)存在用戶請(qǐng)求隊(duì)列中。然后根據(jù)當(dāng)前用戶請(qǐng)求隊(duì)列狀態(tài)選取數(shù)據(jù)參與廣播，將之存儲(chǔ)在就緒隊(duì)列中。最后進(jìn)行調(diào)度，周期地廣播數(shù)據(jù)。

鑒于移動(dòng)用戶對(duì)數(shù)據(jù)需求的動(dòng)態(tài)改變特性，該數(shù)據(jù)廣播模型采用需求驅(qū)動(dòng)機(jī)制，根據(jù)用戶請(qǐng)求隊(duì)列的最新狀態(tài)選擇和調(diào)度廣播內(nèi)容。為了滿足用戶對(duì)數(shù)據(jù)的時(shí)效要求，設(shè)定了數(shù)據(jù)的最大響應(yīng)時(shí)間限制(Respond Time Limit，RTL)。MC在發(fā)出一個(gè)訪問(wèn)請(qǐng)求之后，開始監(jiān)聽數(shù)據(jù)廣播的內(nèi)容，如果監(jiān)聽的時(shí)間超過(guò)了RTL還沒(méi)有得到響應(yīng)，就認(rèn)為該訪問(wèn)請(qǐng)求失敗了，不繼續(xù)監(jiān)聽。同樣，數(shù)據(jù)廣播服務(wù)器在收到MC發(fā)出的訪問(wèn)請(qǐng)求之后，如果在最大響應(yīng)時(shí)間限制RTL之內(nèi)不能把相應(yīng)的數(shù)據(jù)項(xiàng)編入數(shù)據(jù)廣播中，將把該數(shù)據(jù)請(qǐng)求從請(qǐng)求隊(duì)列中刪除，作失敗處理。廣播模型的目標(biāo)不僅要滿足用戶對(duì)數(shù)據(jù)的時(shí)間限制要求，還要利用數(shù)據(jù)廣播技術(shù)分發(fā)數(shù)據(jù)，有效地利用通信帶寬，滿足最多用戶的數(shù)據(jù)需求。該廣播模型的優(yōu)點(diǎn)是:

1) 綜合了PULL和PUSH技術(shù)，允許用戶上傳請(qǐng)求，下傳反饋信息，與服務(wù)器直接進(jìn)行溝通;

2) 能識(shí)別MC提出的用戶請(qǐng)求;

3) 將數(shù)據(jù)以廣播的方式分發(fā)，發(fā)揮了廣播通信的優(yōu)勢(shì)，使通信帶寬具有可伸縮性;

4) 明確考慮了用戶對(duì)數(shù)據(jù)的時(shí)效要求。

用戶通過(guò)廣播獲取數(shù)據(jù)過(guò)程如下:

1) MC發(fā)出用戶請(qǐng)求;

2) 服務(wù)器接收用戶請(qǐng)求，并放置在用戶請(qǐng)求隊(duì)列中;

3) 廣播內(nèi)容選擇程序在用戶請(qǐng)求隊(duì)列里選擇廣播內(nèi)容，并形成就緒隊(duì)列;

4)調(diào)度程序?qū)途w隊(duì)列進(jìn)行調(diào)度，周期地廣播數(shù)據(jù)。

為了便于研究，對(duì)廣播模型及廣播環(huán)境作了一些限制，下面是一些基本的假設(shè):

1) 服務(wù)器向MC廣播時(shí)所基于的通信網(wǎng)絡(luò)具有固有的廣播能力，即被廣播的數(shù)據(jù)對(duì)所有MC都是可同時(shí)訪問(wèn)的，且各個(gè)MC之間互不干擾。

2) 數(shù)據(jù)廣播的最小單位是數(shù)據(jù)項(xiàng)，且所有數(shù)據(jù)項(xiàng)長(zhǎng)度相等，每個(gè)數(shù)據(jù)項(xiàng)在廣播周期中只被廣播一次。

3) 數(shù)據(jù)廣播采用固定周期的廣播方式。

4) 服務(wù)器通過(guò)單信道廣播數(shù)據(jù)項(xiàng)。

5) MC提出的數(shù)據(jù)請(qǐng)求事務(wù)中至少包含兩個(gè)數(shù)據(jù)項(xiàng)，任何兩個(gè)請(qǐng)求事務(wù)都是互相獨(dú)立的。MC對(duì)事務(wù)中數(shù)據(jù)項(xiàng)獲取的先后順序不作要求。

6) MC在訪問(wèn)數(shù)據(jù)廣播時(shí)，每次訪問(wèn)一個(gè)數(shù)據(jù)項(xiàng)，并且相鄰兩次訪問(wèn)的數(shù)據(jù)項(xiàng)之間是相互獨(dú)立的。

7) 所有的數(shù)據(jù)項(xiàng)都是可自我標(biāo)識(shí)的，即MC通過(guò)接收任意一個(gè)數(shù)據(jù)項(xiàng)，可以知道它是不是自己所要訪問(wèn)的數(shù)據(jù)項(xiàng)。這可以通過(guò)在每個(gè)廣播數(shù)據(jù)項(xiàng)之前插入適當(dāng)?shù)念^數(shù)據(jù)來(lái)實(shí)現(xiàn)。

8) 每個(gè)廣播數(shù)據(jù)項(xiàng)擁有一個(gè)主鍵(Primary Key)，它能夠唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)項(xiàng)，并且MC總是根據(jù)主鍵來(lái)訪問(wèn)數(shù)據(jù)廣播中的數(shù)據(jù)項(xiàng)。

9) 廣播信道中的數(shù)據(jù)項(xiàng)是只讀的，不考慮數(shù)據(jù)項(xiàng)更新的情況。

10) 廣播信道等基礎(chǔ)設(shè)施是可靠的，不考慮傳輸錯(cuò)誤的存在。

11) 服務(wù)器不知道MC 對(duì)廣播數(shù)據(jù)項(xiàng)的訪問(wèn)概率分布，因?yàn)镸C的數(shù)據(jù)訪問(wèn)興趣隨時(shí)間動(dòng)態(tài)改變。

12) 對(duì)于超過(guò)定時(shí)限制而請(qǐng)求失敗的事務(wù)，服務(wù)器不進(jìn)行廣播重發(fā)。MC可繼續(xù)提出請(qǐng)求事務(wù)申請(qǐng)?jiān)摂?shù)據(jù)。

4 結(jié)束語(yǔ)

該文提出了一種實(shí)時(shí)數(shù)據(jù)廣播模型。該模型采用數(shù)據(jù)需求驅(qū)動(dòng)機(jī)制，不僅充分考慮用戶對(duì)數(shù)據(jù)的時(shí)效要求，還利用數(shù)據(jù)廣播技術(shù)分發(fā)數(shù)據(jù)，有效地利用通信帶寬，滿足最多用戶的數(shù)據(jù)需求。

參考文獻(xiàn):

[1] Chung Y.D.， Kim M.H. QEM: a scheduling method for wireless broadcast data. In: Proc of the 6th Int Conf on Database Systems for Advanced Applications. 1999:135-142.

[2] Lee G.L.， Lo S.C. Broadcast data allocation for efficient access of multiple data items in mobile environments. Mobile Networks and Applications， 2003， 8(4):365-375.

[3] 何新貴，唐常杰，李霖，等.特種數(shù)據(jù)庫(kù)技術(shù)[M].北京:科學(xué)出版社， 2000:204-234.