多數(shù)據(jù)項(xiàng)請(qǐng)求的多信道并行廣播調(diào)度算法

呂承飛， 季林峰， 倪 寧

(1.浙江大學(xué)計(jì)算機(jī)學(xué)院，浙江杭州310027；2.浙江商業(yè)職業(yè)技術(shù)學(xué)院信息技術(shù)系，浙江杭州310012)

0 引 言

在移動(dòng)計(jì)算環(huán)境中，數(shù)據(jù)廣播是種高效的數(shù)據(jù)訪問(wèn)方式，能夠以較小代價(jià)向大量移動(dòng)用戶廣播數(shù)據(jù)，而且廣播開(kāi)銷不隨移動(dòng)用戶數(shù)量的增加而增加。因此，數(shù)據(jù)廣播技術(shù)一直是研究的熱點(diǎn)。之前的研究一般都假設(shè)用戶每次發(fā)送請(qǐng)求只請(qǐng)求單個(gè)數(shù)據(jù)項(xiàng)，而在實(shí)際中，用戶一般都是同時(shí)請(qǐng)求多個(gè)數(shù)據(jù)項(xiàng)，因此研究多數(shù)據(jù)項(xiàng)請(qǐng)求的廣播調(diào)度算法更具有現(xiàn)實(shí)意義。另外，采用多信道并行廣播技術(shù)，即多個(gè)信道同時(shí)進(jìn)行數(shù)據(jù)廣播，能夠進(jìn)一步減少用戶請(qǐng)求的訪問(wèn)時(shí)間。但是由于多個(gè)數(shù)據(jù)項(xiàng)同時(shí)廣播，有可能導(dǎo)致數(shù)據(jù)訪問(wèn)沖突，如何解決數(shù)據(jù)訪問(wèn)沖突問(wèn)題是多信道并行廣播技術(shù)研究的重點(diǎn)。

目前，研究人員已經(jīng)提出了許多廣播調(diào)度算法，在單信道單數(shù)據(jù)項(xiàng)請(qǐng)求的廣播模式下有經(jīng)典的多盤(pán)調(diào)度算法[1]。文獻(xiàn)[2-5]研究了在單信道多數(shù)據(jù)項(xiàng)請(qǐng)求廣播模式下的數(shù)據(jù)廣播調(diào)度算法，文獻(xiàn)[2]以訪問(wèn)概率為基礎(chǔ)，提出了QEM數(shù)據(jù)廣播調(diào)度算法，文獻(xiàn)[3-5]分別對(duì)QEM調(diào)度算法進(jìn)行了改進(jìn)，進(jìn)一步提高了數(shù)據(jù)廣播性能。針對(duì)多信道多數(shù)據(jù)項(xiàng)請(qǐng)求的廣播模式，研究人員也提出了一些廣播調(diào)度算法[6-8]。文獻(xiàn)[6]通過(guò)完全消除數(shù)據(jù)訪問(wèn)沖突來(lái)降低用戶訪問(wèn)時(shí)間，但是這樣導(dǎo)致一些廣播時(shí)槽未被使用，降低了帶寬的使用率。文獻(xiàn)[7-8]提出的廣播調(diào)度算法對(duì)所有數(shù)據(jù)項(xiàng)都是非重復(fù)廣播的，在實(shí)際環(huán)境中廣播周期往往比較長(zhǎng)，因此當(dāng)錯(cuò)過(guò)本次廣播的數(shù)據(jù)項(xiàng)時(shí)需要等待較長(zhǎng)時(shí)間才能在下次廣播中獲得請(qǐng)求的數(shù)據(jù)項(xiàng)。針對(duì)上述問(wèn)題，提出了一種新的廣播調(diào)度算法，該算法在避免數(shù)據(jù)訪問(wèn)沖突的基礎(chǔ)上，對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)采用重復(fù)廣播技術(shù)，進(jìn)一步降低了平均訪問(wèn)時(shí)間，提高了廣播性能。

1 多信道并行數(shù)據(jù)廣播

多信道并行廣播是指多個(gè)信道同時(shí)對(duì)數(shù)據(jù)項(xiàng)進(jìn)行廣播，與單信道數(shù)據(jù)廣播相比，多信道數(shù)據(jù)廣播極大地降低了廣播周期，從而減少了用戶請(qǐng)求的訪問(wèn)時(shí)間，提高了數(shù)據(jù)廣播性能。然而，由于多個(gè)數(shù)據(jù)項(xiàng)分別在多個(gè)信道同時(shí)廣播，所以多個(gè)數(shù)據(jù)項(xiàng)之間也可能存在數(shù)據(jù)訪問(wèn)沖突。數(shù)據(jù)訪問(wèn)沖突，即對(duì)于多數(shù)據(jù)項(xiàng)的用戶請(qǐng)求，同個(gè)用戶請(qǐng)求內(nèi)的至少兩個(gè)數(shù)據(jù)項(xiàng)同時(shí)在多個(gè)信道中被廣播，那么這多個(gè)數(shù)據(jù)項(xiàng)之間就存在數(shù)據(jù)訪問(wèn)沖突。

一個(gè)典型的數(shù)據(jù)廣播模式如圖1所示，用戶請(qǐng)求Qi包含d4，d15，d16，d1共 4 個(gè)數(shù)據(jù)項(xiàng)，對(duì)應(yīng)圖 1 中星號(hào)上標(biāo)所示。由于數(shù)據(jù)項(xiàng)d15，d16在信道1和信道2被同時(shí)廣播，所以用戶請(qǐng)求Qi不能在一個(gè)周期內(nèi)同時(shí)獲得d15，d16，即數(shù)據(jù)項(xiàng)d15，d16存在數(shù)據(jù)訪問(wèn)沖突。因?yàn)橐粋€(gè)用戶同時(shí)只能監(jiān)聽(tīng)一個(gè)信道，當(dāng)用戶所需的兩個(gè)數(shù)據(jù)項(xiàng)在兩個(gè)不同的信道被同時(shí)廣播，則用戶不可能同時(shí)訪問(wèn)到這兩個(gè)數(shù)據(jù)項(xiàng)。

圖1 多信道并行廣播模式

如果在一個(gè)用戶請(qǐng)求中存在數(shù)據(jù)訪問(wèn)沖突，那么用戶肯定不能在一個(gè)廣播周期內(nèi)獲取所有請(qǐng)求數(shù)據(jù)項(xiàng)，需要等待一個(gè)或多個(gè)廣播周期才能獲取所有訪問(wèn)沖突的數(shù)據(jù)項(xiàng)。因此，對(duì)于多信道并行數(shù)據(jù)廣播，數(shù)據(jù)訪問(wèn)沖突的存在極大地增加了用戶請(qǐng)求的訪問(wèn)時(shí)間，有效地解決數(shù)據(jù)訪問(wèn)沖突問(wèn)題能夠大大地減少用戶訪問(wèn)時(shí)間。

2 非重復(fù)廣播

非重復(fù)廣播，即在一個(gè)廣播周期內(nèi)每個(gè)數(shù)據(jù)項(xiàng)都出現(xiàn)一次，而且僅出現(xiàn)一次。顯然，非重復(fù)廣播適用于對(duì)所有數(shù)據(jù)項(xiàng)有相等請(qǐng)求概率的場(chǎng)合，而當(dāng)用戶對(duì)數(shù)據(jù)項(xiàng)的請(qǐng)求概率出現(xiàn)偏斜時(shí)，非重復(fù)廣播將不能很好適用。

文獻(xiàn)[7，8]提出的多信道并行廣播調(diào)度算法都是基于非重復(fù)廣播的，圖1是按PBA[7]調(diào)度算法實(shí)現(xiàn)的數(shù)據(jù)廣播序列，共有20個(gè)數(shù)據(jù)項(xiàng)需要廣播，分4個(gè)信道并行廣播，假設(shè)每個(gè)數(shù)據(jù)項(xiàng)廣播占用一個(gè)廣播時(shí)槽，則廣播周期是5個(gè)廣播時(shí)槽。假設(shè)一個(gè)用戶在第 i次廣播的 t4時(shí)刻發(fā)送 d4，d15，d16，d1的多數(shù)據(jù)項(xiàng)請(qǐng)求。由于這幾個(gè)數(shù)據(jù)項(xiàng)在本周期都已經(jīng)被廣播，所以只有等待下次廣播周期才能獲得對(duì)應(yīng)的數(shù)據(jù)項(xiàng)。又因?yàn)閐15，d16存在數(shù)據(jù)訪問(wèn)沖突，所以在第i+1次廣播中只能獲得d15和d16中的任意一個(gè)數(shù)據(jù)項(xiàng)，為了獲得另一個(gè)數(shù)據(jù)項(xiàng)則需要再等待一個(gè)廣播周期，最后在第i+2次廣播的t13時(shí)刻完成用戶請(qǐng)求。

在實(shí)際應(yīng)用中，數(shù)據(jù)項(xiàng)的數(shù)量是龐大的，相應(yīng)的廣播周期也相對(duì)較長(zhǎng)。假設(shè)需要廣播的數(shù)據(jù)項(xiàng)總量為1000，4個(gè)并行廣播信道，那么按照PBA調(diào)度算法得到的調(diào)度序列的廣播周期是250個(gè)廣播時(shí)槽。如果在用戶發(fā)送請(qǐng)求時(shí)剛好錯(cuò)過(guò)所請(qǐng)求的數(shù)據(jù)項(xiàng)，那么在不存在數(shù)據(jù)訪問(wèn)沖突的情況下，用戶將需要等待接近一個(gè)周期才能獲得請(qǐng)求的數(shù)據(jù)項(xiàng)。如果用戶請(qǐng)求的數(shù)據(jù)項(xiàng)存在數(shù)據(jù)訪問(wèn)沖突，那么用戶需要再等待一個(gè)或多個(gè)廣播周期?？梢?jiàn)，過(guò)長(zhǎng)的廣播周期嚴(yán)重影響了用戶訪問(wèn)性能。

因此，縮短廣播周期能夠有效地減少用戶訪問(wèn)時(shí)間，獲得更好的訪問(wèn)性能。一方面，可以通過(guò)增加并行廣播的信道來(lái)縮短廣播周期，但是大量增加并行信道是不現(xiàn)實(shí)的，而且廣播信道的增加也使索引數(shù)據(jù)項(xiàng)面臨挑戰(zhàn)，同時(shí)用戶在信道間的跳轉(zhuǎn)也將花費(fèi)更多的電量消耗。另一方面，可以通過(guò)對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行重復(fù)廣播的方法來(lái)降低熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播周期，從而有效地降低用戶訪問(wèn)時(shí)間。

3 多信道重復(fù)廣播調(diào)度算法

3.1 主要思想

針對(duì)多信道并行廣播的數(shù)據(jù)訪問(wèn)沖突問(wèn)題和非重復(fù)廣播中廣播周期過(guò)長(zhǎng)問(wèn)題，本文提出了多數(shù)據(jù)項(xiàng)請(qǐng)求的多信道并行廣播調(diào)度算法，在盡量減少數(shù)據(jù)訪問(wèn)沖突的基礎(chǔ)上對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行重復(fù)廣播，從而提高廣播性能。

在數(shù)據(jù)項(xiàng)廣播調(diào)度過(guò)程中，可以通過(guò)檢測(cè)并行廣播信道中的數(shù)據(jù)項(xiàng)是否存在數(shù)據(jù)訪問(wèn)沖突，及時(shí)調(diào)整數(shù)據(jù)項(xiàng)在廣播信道中的廣播位置，從而避免數(shù)據(jù)訪問(wèn)沖突。另外，考慮到在多數(shù)據(jù)項(xiàng)用戶請(qǐng)求中，用戶需要獲得所有請(qǐng)求的數(shù)據(jù)項(xiàng)才能完成請(qǐng)求，所以盡量將同個(gè)用戶請(qǐng)求的多個(gè)數(shù)據(jù)項(xiàng)放在臨近位置。

統(tǒng)計(jì)顯示，一般的數(shù)據(jù)訪問(wèn)都表現(xiàn)出“80-20”現(xiàn)象，即80%的訪問(wèn)請(qǐng)求落在20%的數(shù)據(jù)項(xiàng)上，因此對(duì)這20%的熱點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行重復(fù)廣播能夠有效地降低整體用戶請(qǐng)求的平均訪問(wèn)時(shí)間。

3.2 算法描述

假設(shè)每個(gè)數(shù)據(jù)項(xiàng)的大小是一樣的，并將每個(gè)廣播信道看成由一系列廣播時(shí)槽構(gòu)成，每個(gè)廣播時(shí)槽對(duì)應(yīng)廣播一個(gè)數(shù)據(jù)項(xiàng)。同時(shí)，不考慮同個(gè)用戶請(qǐng)求內(nèi)數(shù)據(jù)項(xiàng)的訪問(wèn)順序，并將多信道并行廣播模式看成AC×L矩陣。其中，AC為信道數(shù)，L為廣播周期，即每個(gè)信道有L個(gè)廣播時(shí)槽。其他符號(hào)含義見(jiàn)表1。

表1 符號(hào)說(shuō)明

數(shù)據(jù)調(diào)度過(guò)程如下所示：

(1)根據(jù)“80-20”原則，計(jì)算熱點(diǎn)數(shù)據(jù)項(xiàng)的數(shù)目Nh=D*20%，從而得到熱點(diǎn)數(shù)據(jù)項(xiàng)的并行廣播矩陣AC×Lh，非熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播矩陣AC×Lc。其中AC為信道數(shù)，Lh=Nh/AC為熱點(diǎn)數(shù)據(jù)項(xiàng)廣播周期，Lc=(D-Nh)/AC為非熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播周期。

(2)將每個(gè)用戶請(qǐng)求按訪問(wèn)概率進(jìn)行降序排序。

(3)構(gòu)建熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播矩陣AC×Lh。對(duì)用戶請(qǐng)求中的數(shù)據(jù)項(xiàng)按(6)處理直到確定Lh個(gè)熱點(diǎn)數(shù)據(jù)項(xiàng)，即生成對(duì)應(yīng)的熱點(diǎn)數(shù)據(jù)項(xiàng)廣播矩陣AC×Lh。

(4)構(gòu)建非熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播矩陣AC×Lc。對(duì)未被調(diào)度的用戶請(qǐng)求按(6)處理直到生成對(duì)應(yīng)的非熱點(diǎn)數(shù)據(jù)項(xiàng)廣播矩陣AC×Lc。

(5)將熱點(diǎn)數(shù)據(jù)項(xiàng)廣播矩陣AC×Lh在非熱點(diǎn)數(shù)據(jù)項(xiàng)廣播矩陣AC×Lc的前面及中間各廣播一次，即熱點(diǎn)數(shù)據(jù)項(xiàng)廣播兩次，非熱點(diǎn)數(shù)據(jù)項(xiàng)廣播一次。最后生成廣播矩陣AC×L，其中L=(Lh*2+Lc)，如圖 2 所示。

圖2 多信道熱點(diǎn)數(shù)據(jù)項(xiàng)重復(fù)廣播模式

(6)處理未調(diào)度的用戶請(qǐng)求方法如下。

1)對(duì)于一個(gè)未調(diào)度的用戶請(qǐng)求Qi，查找剩余空閑廣播時(shí)槽最多的信道作為該用戶請(qǐng)求的默認(rèn)廣播信道。

2)依次處理用戶請(qǐng)求數(shù)據(jù)項(xiàng)集合(QDSi)中未被調(diào)度的數(shù)據(jù)項(xiàng)。若用戶請(qǐng)求中的某些數(shù)據(jù)項(xiàng)已被調(diào)度，則臨近已經(jīng)調(diào)度的數(shù)據(jù)項(xiàng)查找不存在數(shù)據(jù)訪問(wèn)沖突的空閑廣播時(shí)槽。從默認(rèn)廣播信道開(kāi)始查找，若未找到，則依次查找其他廣播信道。最后將數(shù)據(jù)項(xiàng)安排在找到的空閑時(shí)槽內(nèi)廣播。

3)若在2)中遍歷所有信道都未找到不存在數(shù)據(jù)訪問(wèn)沖突的空閑廣播時(shí)槽，則放寬要求，查找距離已經(jīng)調(diào)度數(shù)據(jù)項(xiàng)最近的空閑時(shí)槽，不要求不存在數(shù)據(jù)訪問(wèn)沖突。從默認(rèn)信道開(kāi)始查找，若未找到，則依次查找其他信道。最后將數(shù)據(jù)項(xiàng)安排在找到的空閑時(shí)槽內(nèi)廣播。

本調(diào)度算法在步驟(5)中對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行重復(fù)廣播；在步驟(6)中處理數(shù)據(jù)訪問(wèn)沖突，并將同個(gè)用戶請(qǐng)求中的多個(gè)數(shù)據(jù)項(xiàng)分配在臨近廣播時(shí)槽廣播。數(shù)據(jù)調(diào)度完成后，生成AC×L的廣播矩陣，其中在一個(gè)廣播周期內(nèi)熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播頻率為兩次，非熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播頻率為一次。相比較非重復(fù)廣播，熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播周期接近于原來(lái)的一半，從而降低了平均訪問(wèn)時(shí)間。

4 性能分析

按照本文提出的多信道多數(shù)據(jù)項(xiàng)請(qǐng)求廣播調(diào)度算法進(jìn)行了仿真實(shí)驗(yàn)，并與文獻(xiàn)[7]的PBA和文獻(xiàn)[8]的Hybrid調(diào)度算法進(jìn)行了比較，為了方便說(shuō)明，將本文算法用RBA(repeatedly broadcast algorithm)表示。仿真程序主要步驟如下，首先將D(數(shù)據(jù)項(xiàng)總數(shù))個(gè)數(shù)據(jù)項(xiàng)按調(diào)度算法分別分配到相應(yīng)廣播信道的廣播時(shí)槽內(nèi)，然后針對(duì)生成的廣播模式計(jì)算每個(gè)用戶請(qǐng)求的訪問(wèn)時(shí)間(accesstime)，最后計(jì)算平均訪問(wèn)時(shí)間(averageaccess time)。

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

實(shí)驗(yàn)環(huán)境是Intel(R)Core(TM)2 CPU,2G內(nèi)存，Windows XP平臺(tái)，利用Microsoft Visual Studio 2010開(kāi)發(fā)仿真程序，仿真參數(shù)設(shè)置如表2所示。

表2 仿真系統(tǒng)參數(shù)設(shè)置

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

選取普遍使用的平均訪問(wèn)時(shí)間(averageaccesstime)作為評(píng)價(jià)標(biāo)準(zhǔn)。平均訪問(wèn)時(shí)間其中為用戶請(qǐng)求Qi的訪問(wèn)時(shí)間，Pi為用戶請(qǐng)求Qi的訪問(wèn)概率。訪問(wèn)時(shí)間是指用戶從發(fā)送用戶請(qǐng)求到完成下載所需數(shù)據(jù)項(xiàng)的時(shí)間間隔。對(duì)于用戶請(qǐng)求 Qi，AT(Qi)=Twait(Qi)+Tretrieve(Qi)+cyclei*L，其中Twait(Qi)表示用戶從發(fā)送用戶請(qǐng)求到獲得第一個(gè)請(qǐng)求數(shù)據(jù)項(xiàng)的時(shí)間間隔；Tretrieve(Qi)表示用戶從獲得第一個(gè)請(qǐng)求數(shù)據(jù)項(xiàng)到獲得最后一個(gè)請(qǐng)求數(shù)據(jù)項(xiàng)的時(shí)間間隔；cyclei表示存在數(shù)據(jù)訪問(wèn)沖突時(shí)需要經(jīng)歷的周期數(shù)；L為廣播周期。

4.3 實(shí)驗(yàn)結(jié)果及分析

4.3.1 斜率()對(duì)平均訪問(wèn)時(shí)間的影響

設(shè)置斜率()的取值范圍在[0.4,1.2]之間，其他參數(shù)按表2所示設(shè)置默認(rèn)值。隨機(jī)生成用戶請(qǐng)求數(shù)據(jù)項(xiàng)，用戶發(fā)送請(qǐng)求的時(shí)間，按照 Zipf分布生成用戶請(qǐng)求的概率，即。圖3顯示了斜率()對(duì)平均訪問(wèn)時(shí)間的影響，結(jié)果顯示隨著斜率()的增加，相比較PBA和Hybrid廣播調(diào)度算法，本文提出的RBA廣播調(diào)度算法具有更好的性能。因?yàn)?，一方面，RBA算法減少了數(shù)據(jù)訪問(wèn)沖突，且將同一用戶請(qǐng)求內(nèi)的數(shù)據(jù)項(xiàng)安排在鄰近位置，從而降低了平均訪問(wèn)時(shí)間。另一方面，隨著斜率()的增加，熱點(diǎn)數(shù)據(jù)項(xiàng)具有更高的訪問(wèn)概率，而RBA算法通過(guò)對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)的重復(fù)廣播能夠有效地減少熱點(diǎn)數(shù)據(jù)項(xiàng)的訪問(wèn)時(shí)間，所以RBA算法具有更好的廣播性能。Hybrid算法由于在避免數(shù)據(jù)訪問(wèn)沖突的同時(shí)考慮了數(shù)據(jù)項(xiàng)之間的關(guān)系，因此廣播性能也優(yōu)于PBA算法。

圖3 斜率()對(duì)平均訪問(wèn)時(shí)間的影響

4.3.2 數(shù)據(jù)項(xiàng)總數(shù)(D)對(duì)平均訪問(wèn)時(shí)間的影響

圖4 數(shù)據(jù)項(xiàng)總數(shù)(D)對(duì)平均訪問(wèn)時(shí)間的影響

設(shè)置廣播數(shù)據(jù)項(xiàng)總數(shù)(D)的取值范圍在[200,1000]之間，其他參數(shù)按表2所示設(shè)置默認(rèn)值，圖4顯示了廣播數(shù)據(jù)項(xiàng)總數(shù)(D)對(duì)平均訪問(wèn)時(shí)間的影響。結(jié)果顯示，隨著數(shù)據(jù)項(xiàng)總數(shù)的增加，RBA算法具有最好的廣播性能。這是因?yàn)殡S著數(shù)據(jù)項(xiàng)的增加，廣播周期也隨之變長(zhǎng)，而RBA算法中對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行重復(fù)廣播，相比較PBA和Hybrid調(diào)度算法縮短了熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播周期，所以降低了平均訪問(wèn)時(shí)間。

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

本文研究了在多信道多數(shù)據(jù)項(xiàng)用戶請(qǐng)求廣播模式下的廣播調(diào)度算法，針對(duì)多信道并行廣播中的數(shù)據(jù)訪問(wèn)沖突問(wèn)題和廣播周期過(guò)長(zhǎng)導(dǎo)致用戶請(qǐng)求平均訪問(wèn)時(shí)間過(guò)長(zhǎng)的問(wèn)題，提出了一種新的廣播調(diào)度算法。該算法能夠有效減少數(shù)據(jù)訪問(wèn)沖突，并通過(guò)對(duì)熱點(diǎn)數(shù)據(jù)項(xiàng)采用重復(fù)廣播技術(shù)從而縮短熱點(diǎn)數(shù)據(jù)項(xiàng)的廣播周期。經(jīng)仿真實(shí)驗(yàn)表明，該算法能夠很好的降低平均訪問(wèn)時(shí)間，提高廣播性能。目前的重復(fù)廣播調(diào)度算法比較簡(jiǎn)單，下一步將研究更好的重復(fù)廣播調(diào)度算法。

[1]Acharya S,Alonso R,Franklin M,et al.Broadcast disks:data management for asymmetric communication environments[C].San Jose,CA:Proceedings of the ACM SIGMOD Conference,1995:199-210.

[2]Chung D Y,Kim H M.QEM:A scheduling method for wireless broadcast data[C].Taiwan:Proceedings of International Conference on Database Systems for Advanced Applications proceedings,1999:135-142.

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

[4]Sun Weiwei,Zhang Zhuoyao,Yu Ping,et a1.Skewed wireless broadcast scheduling for multiitem queries[C].New York,USA:ProceedingsoftheInternationalConferenceonWirelessCommunications,Networking and Mobile Computing,2007:1865-1868.

[5]王亞軍,馬小琴.多數(shù)據(jù)項(xiàng)廣播調(diào)度策略[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(23):5329-5331.

[6]雷向東,段紅亮,唐麗.移動(dòng)環(huán)境下多數(shù)據(jù)項(xiàng)請(qǐng)求的廣播策略研究[J].計(jì)算機(jī)應(yīng)用研究,2009,26(9):3487-3489.

[7]Hung Hao Ping,Huang Jen Wei,Huang Jung Long,et al.Scheduling dependent items in data broadcasting environments[C].Dijon,France:ACM SAC,2006.

[8]CHANGYE-IN,CHIU SHIH-YING.A hybridapproach toquery sets broadcasting scheduling for multiple channels in mobile in information systems[J].Journal of Information Science and Engineering,2002,18(5):641-666.