馬小琴

（池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

1 引言

數(shù)據(jù)廣播是無(wú)線環(huán)境中數(shù)據(jù)訪問(wèn)和數(shù)據(jù)發(fā)布的一種有效方式[1]。服務(wù)器端廣播一次數(shù)據(jù)項(xiàng)，能夠同時(shí)滿(mǎn)足所有偵聽(tīng)該數(shù)據(jù)項(xiàng)的移動(dòng)客戶(hù)機(jī)端的請(qǐng)求，并且其性能不會(huì)受客戶(hù)機(jī)數(shù)量的限制，因而數(shù)據(jù)廣播具有很大的靈活性和可擴(kuò)展性。而怎樣組織數(shù)據(jù)項(xiàng)來(lái)盡可能地減小訪問(wèn)時(shí)間即廣播調(diào)度策略是數(shù)據(jù)廣播技術(shù)的一個(gè)重要研究方向。

訪問(wèn)時(shí)間[2-3]是衡量數(shù)據(jù)廣播調(diào)度策略?xún)?yōu)劣的重要指標(biāo)之一，多信道廣播通過(guò)多條信道廣播數(shù)據(jù)項(xiàng)在一定程度上減少了用戶(hù)的訪問(wèn)時(shí)間，現(xiàn)有不少文獻(xiàn)[4-5]對(duì)多信道廣播調(diào)度進(jìn)行了研究。但大部分都是基于訪問(wèn)概率相似的調(diào)度算法[6]，也就是說(shuō)在每個(gè)信道內(nèi)部各數(shù)據(jù)項(xiàng)只廣播一次，這樣不利于熱數(shù)據(jù)的訪問(wèn)，而現(xiàn)實(shí)應(yīng)用環(huán)境中，訪問(wèn)數(shù)據(jù)通常呈現(xiàn)80-20現(xiàn)象。針對(duì)這種不足，本文提出了多信道環(huán)境下的一種偏斜調(diào)度策略。首先引入了近似最優(yōu)的TOSA[7]的高層調(diào)度算法，然后將經(jīng)典的多盤(pán)調(diào)度[8]應(yīng)用于低層調(diào)度。該策略使用兩層調(diào)度來(lái)生成調(diào)度序列，高層借鑒了近似最優(yōu)的TOSA的高層調(diào)度方法，而低層用多盤(pán)調(diào)度使得熱數(shù)據(jù)在一個(gè)廣播周期中出現(xiàn)多次以減少對(duì)熱數(shù)據(jù)的訪問(wèn)時(shí)間，從而整體上降低了平均訪問(wèn)代價(jià)。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該策略能提高訪問(wèn)效率，且當(dāng)訪問(wèn)頻率相差較大時(shí)，多信道廣播性能更優(yōu)。

2 TOSA算法與多盤(pán)調(diào)度算法

2.1 TOSA算法

TOSA算法是由高層的數(shù)據(jù)分配算法和低層的log-time算法兩層算法構(gòu)成，高層的數(shù)據(jù)分配算法負(fù)責(zé)將數(shù)據(jù)項(xiàng)依次地分配到每個(gè)信道，低層的Log-time算法對(duì)每個(gè)信道內(nèi)的數(shù)據(jù)項(xiàng)進(jìn)行調(diào)整以進(jìn)一步優(yōu)化訪問(wèn)時(shí)間。其中，數(shù)據(jù)分配算法由初始化和調(diào)整兩個(gè)部分組成。初始化部分把N個(gè)數(shù)據(jù)項(xiàng)分配到K個(gè)信道中，其具體的算法思想是將每2B個(gè)數(shù)據(jù)項(xiàng)歸為一組，前B個(gè)數(shù)據(jù)項(xiàng)依次放入1至K的信道，后B個(gè)數(shù)據(jù)項(xiàng)依次放入信道K至1的信道，各信道中放入的數(shù)據(jù)項(xiàng)的總數(shù)正比于該信道帶寬的平方根。調(diào)整部分的算法思想是不斷地調(diào)整最大的信道和最小的信道，使得信道趨于相等，這樣進(jìn)一步地降低了用戶(hù)的平均訪問(wèn)時(shí)間，優(yōu)化了多信道廣播的訪問(wèn)性能。

2.2 多盤(pán)調(diào)度算法

多盤(pán)調(diào)度算法是一種廣泛使用的調(diào)度算法，該算法有利于用戶(hù)較快地訪問(wèn)到高頻數(shù)據(jù)，適合于偏斜訪問(wèn)的環(huán)境。其基本思想是將客戶(hù)機(jī)頻繁訪問(wèn)的數(shù)據(jù)（熱數(shù)據(jù)）放入高速磁盤(pán)，將不經(jīng)常訪問(wèn)的數(shù)據(jù)（冷數(shù)據(jù)）放入低速磁盤(pán)來(lái)減少熱數(shù)據(jù)的訪問(wèn)時(shí)間從而整體上減少平均訪問(wèn)時(shí)間，其性能明顯優(yōu)于平坦調(diào)度。

2.3 TOSA算法與多盤(pán)調(diào)度的聯(lián)系

TOSA的高層數(shù)據(jù)分配算法在多信道環(huán)境下達(dá)到近似最優(yōu)，而實(shí)際環(huán)境中數(shù)據(jù)訪問(wèn)往往呈現(xiàn)偏斜現(xiàn)象，而多盤(pán)調(diào)度是經(jīng)典的偏斜訪問(wèn)調(diào)度算法，因此在每個(gè)信道中采用多盤(pán)調(diào)度替代TOSA的低層調(diào)度，以此降低偏斜訪問(wèn)的平均訪問(wèn)時(shí)間。

3 多信道廣播調(diào)度策略（MSAS）

3.1 算法基本思想

MSAS算法的主要思想是根據(jù)近似最優(yōu)TOSA算法的高層數(shù)據(jù)分配算法將數(shù)據(jù)項(xiàng)順序地分配到各個(gè)信道，然后對(duì)每個(gè)信道中的數(shù)據(jù)項(xiàng)采用多盤(pán)調(diào)度算法廣播數(shù)據(jù)項(xiàng)，這樣大大縮短了熱數(shù)據(jù)的訪問(wèn)時(shí)間，從而進(jìn)一步減少了用戶(hù)的平均訪問(wèn)時(shí)間。

3.2 算法的具體實(shí)現(xiàn)

3.2.1 算法實(shí)現(xiàn)的適用范圍及符號(hào)定義 為使本算法更好地應(yīng)用于多信道廣播環(huán)境，首先作如下假設(shè)：

(1)多信道無(wú)差錯(cuò)地廣播所有數(shù)據(jù)項(xiàng)；

(2)單數(shù)據(jù)項(xiàng)請(qǐng)求；

(3)數(shù)據(jù)項(xiàng)長(zhǎng)度相等；

(4)數(shù)據(jù)訪問(wèn)是偏斜的。

為分析方便，約定表1的符號(hào)含義：

表1 符號(hào)含義

3.2.2 算法過(guò)程 算法實(shí)現(xiàn)的主要步驟：

（1）每2B個(gè)數(shù)據(jù)項(xiàng)劃為一組，前B個(gè)數(shù)據(jù)項(xiàng)依次放入1至K的信道，后B個(gè)數(shù)據(jù)項(xiàng)依次放入信道K至1的信道，實(shí)現(xiàn)N個(gè)數(shù)據(jù)項(xiàng)放入到K個(gè)信道中。

算法：

輸入：各個(gè)信道的帶寬、各數(shù)據(jù)項(xiàng)的長(zhǎng)度以及N個(gè)數(shù)據(jù)項(xiàng)的訪問(wèn)概率；

輸出：將N個(gè)數(shù)據(jù)項(xiàng)放到K個(gè)信道的初始分區(qū)的結(jié)果；

1:將數(shù)據(jù)項(xiàng)排序，使得對(duì)于任意的i≤j，

2:將信道排序，使得對(duì)于任意的 i≤j，Bi≥Bj;

（2）不斷地調(diào)整上面初始分區(qū)結(jié)果中的最大Aj/信道和最小信道，使得信道近似相等。

算法：

輸入：N個(gè)數(shù)據(jù)項(xiàng)的初始分區(qū)結(jié)果；

輸出：優(yōu)化后的N個(gè)數(shù)據(jù)項(xiàng)的結(jié)果；

（3）在每個(gè)信道中使用多盤(pán)廣播調(diào)度算法調(diào)度數(shù)據(jù)項(xiàng)。

為了適用于偏斜訪問(wèn)模式的廣播環(huán)境，本調(diào)度策略在步驟 （3）中采用經(jīng)典的多盤(pán)調(diào)度算法取代TOSA低層的log-time算法，使得在各個(gè)信道中的一個(gè)廣播周期內(nèi)熱數(shù)據(jù)項(xiàng)廣播多次，這樣大大減小了熱數(shù)據(jù)的訪問(wèn)時(shí)間，從而整體上優(yōu)化了用戶(hù)的平均訪問(wèn)時(shí)間。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

在這部分，我們估計(jì)MSAS算法的性能，并且與多信道的GREEDY[9]算法進(jìn)行比較。實(shí)驗(yàn)中性能衡量標(biāo)準(zhǔn)是平均訪問(wèn)時(shí)間（TAT，The average access time）。Zipf分布能夠比較好地描述偏斜的訪問(wèn)概率分布。在Zipf分布中，若數(shù)據(jù)項(xiàng)總數(shù)為N，則第h個(gè)數(shù)據(jù)項(xiàng)的訪問(wèn)概率為：

實(shí)驗(yàn)中假設(shè)數(shù)據(jù)項(xiàng)長(zhǎng)度和信道帶寬是固定不變的常數(shù)，實(shí)驗(yàn)參數(shù)如表2。依次比較了在偏斜因子、數(shù)據(jù)量的大小以及信道數(shù)目變化的情況下對(duì)算法性能的影響。

表2 實(shí)驗(yàn)參數(shù)

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

4.2.1 實(shí)驗(yàn)1：偏斜因子θ取值的影響 假設(shè)有10000個(gè)數(shù)據(jù)項(xiàng)，K=2，如圖1顯示隨著θ值的增加，MSAS算法的平均訪問(wèn)性能優(yōu)于GREEDY算法，這是因?yàn)镚REEDY算法在一個(gè)周期內(nèi)每個(gè)數(shù)據(jù)項(xiàng)只廣播一次，在偏斜因子增大的情況下，增加了熱數(shù)據(jù)的訪問(wèn)時(shí)間，從而影響了用戶(hù)的平均訪問(wèn)時(shí)間，而MSAS算法在低層采用了多盤(pán)調(diào)度對(duì)偏斜的數(shù)據(jù)訪問(wèn)更有利。

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

4.2.2 實(shí)驗(yàn)2：數(shù)據(jù)項(xiàng)個(gè)數(shù)N的影響 如圖2顯示了隨數(shù)據(jù)項(xiàng)個(gè)數(shù)增加的變化情況，設(shè)定信道個(gè)數(shù)K=3，=0.75，數(shù)據(jù)項(xiàng)個(gè)數(shù)的增加必然會(huì)加大用戶(hù)的平均等待時(shí)間，而MSAS算法在高層調(diào)度是近似最優(yōu)的調(diào)度算法，且在低層考慮了熱點(diǎn)數(shù)據(jù)的頻繁訪問(wèn)特性，因此在平均訪問(wèn)時(shí)間上優(yōu)于GREEDY算法。

圖2 N對(duì)總訪問(wèn)時(shí)間的影響

4.2.3 實(shí)驗(yàn)3：信道數(shù)目K的影響 本實(shí)驗(yàn)設(shè)定N=10000和=0.75。從圖3的實(shí)驗(yàn)結(jié)果可以看出，MSAS算法的性仍然優(yōu)于GREEDY算法。信道數(shù)目從2增加到12，信道個(gè)數(shù)的增加減少了每個(gè)信道中廣播的數(shù)據(jù)項(xiàng)，而MSAS算法在每個(gè)信道上考慮了偏斜訪問(wèn)的特性，因此比基于平坦調(diào)度基制的GREEDY算法的訪問(wèn)時(shí)間減小的更明顯。

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

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

本文提出了一種多信道環(huán)境下偏斜訪問(wèn)模式的調(diào)度策略，高層調(diào)度引入了TOSA算法的高層數(shù)據(jù)分算法，低層采用了多盤(pán)調(diào)度算法以進(jìn)一步優(yōu)化平均訪問(wèn)時(shí)間。本算法大大減少了熱數(shù)據(jù)的訪問(wèn)時(shí)間從而整體上減少了平均訪問(wèn)時(shí)間。實(shí)驗(yàn)結(jié)果表明，本算法比GREEDY算法有更好的性能，特別適用于偏斜訪問(wèn)模式的環(huán)境。

[1]Yun J.C.H.，Edwa rd C.，Lam K.Adaptive data broadcast strategyfortransactionswith multiple data requestsin mobile computing environments[C]//Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications，Washington，USA:IEEE press，1999:376-448.

[2]孟小峰，周龍?bào)J，王珊.數(shù)據(jù)庫(kù)技術(shù)發(fā)展趨勢(shì)[J].軟件學(xué)報(bào)，2004，15(12):1822-1836.

[3]余平.移動(dòng)環(huán)境中的數(shù)據(jù)廣播調(diào)度理論分析及算法研究[J].計(jì)算機(jī)科學(xué)，2011，38(9):168-172.

[4]Yu P，Sun W W，Qin Y R，et al.A Data Partition Based Near Optimal Scheduling Algorithm for wireless Multi-channel Data Broadcast[C]//DASFAA 2008.New Delli，India，2008.

[5]張鐵軍，王鴻鵬，楊孝宗.移動(dòng)計(jì)算環(huán)境中的數(shù)據(jù)有效訪問(wèn)技術(shù)研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(3):554-557.

[6]]Ardizzoni E，Bertossi A A，Pinotti M C，et al.Optimal skewed data allocation on multiple channels with flat broadcast per channel[J].IEEE Trans.on Computer，2005，54(5):558-572.

[7]Zheng Baihua，Wu Xia，Jin Xing，et al.TOSA:A Near-optimal Scheduling Algorithm for Multi-channel Data Broadcas[C]//Proc.ofthe 6th International Conference on Mobile Data Management，Ayia Napa:Cyprus，2005.

[8]Acharya S，Alonso R，F(xiàn)ranklin M，et al.Broadcast disks:data management for asymmetric communi- cations environment[C]//Proceedings of ACM SI-GMOD International Conference，San Jose:CA，1995:199-210.

[9]W.Yee， S.Navathe， E.Omiecinski， and C.Jermaine，Efficientdata allocation over multiple channels at broadcastservers[J]IEEE Transactions on computers，2002，51(10):1231-1236.