呂承飛， 季林峰， 倪 寧

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

0 引 言

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

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

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

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

一個典型的數(shù)據(jù)廣播模式如圖1所示，用戶請求Qi包含d4，d15，d16，d1共 4 個數(shù)據(jù)項，對應圖 1 中星號上標所示。由于數(shù)據(jù)項d15，d16在信道1和信道2被同時廣播，所以用戶請求Qi不能在一個周期內(nèi)同時獲得d15，d16，即數(shù)據(jù)項d15，d16存在數(shù)據(jù)訪問沖突。因為一個用戶同時只能監(jiān)聽一個信道，當用戶所需的兩個數(shù)據(jù)項在兩個不同的信道被同時廣播，則用戶不可能同時訪問到這兩個數(shù)據(jù)項。

圖1 多信道并行廣播模式

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

2 非重復廣播

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

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

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

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

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

3.1 主要思想

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

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

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

3.2 算法描述

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

表1 符號說明

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

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

(2)將每個用戶請求按訪問概率進行降序排序。

(3)構(gòu)建熱點數(shù)據(jù)項的廣播矩陣AC×Lh。對用戶請求中的數(shù)據(jù)項按(6)處理直到確定Lh個熱點數(shù)據(jù)項，即生成對應的熱點數(shù)據(jù)項廣播矩陣AC×Lh。

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

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

圖2 多信道熱點數(shù)據(jù)項重復廣播模式

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

1)對于一個未調(diào)度的用戶請求Qi，查找剩余空閑廣播時槽最多的信道作為該用戶請求的默認廣播信道。

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

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

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

4 性能分析

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

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

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

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

4.2 評價標準

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

4.3 實驗結(jié)果及分析

4.3.1 斜率()對平均訪問時間的影響

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

圖3 斜率()對平均訪問時間的影響

4.3.2 數(shù)據(jù)項總數(shù)(D)對平均訪問時間的影響

圖4 數(shù)據(jù)項總數(shù)(D)對平均訪問時間的影響

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

5 結(jié)束語

本文研究了在多信道多數(shù)據(jù)項用戶請求廣播模式下的廣播調(diào)度算法，針對多信道并行廣播中的數(shù)據(jù)訪問沖突問題和廣播周期過長導致用戶請求平均訪問時間過長的問題，提出了一種新的廣播調(diào)度算法。該算法能夠有效減少數(shù)據(jù)訪問沖突，并通過對熱點數(shù)據(jù)項采用重復廣播技術(shù)從而縮短熱點數(shù)據(jù)項的廣播周期。經(jīng)仿真實驗表明，該算法能夠很好的降低平均訪問時間，提高廣播性能。目前的重復廣播調(diào)度算法比較簡單，下一步將研究更好的重復廣播調(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ù)項廣播調(diào)度策略[J].計算機工程與設計,2009,30(23):5329-5331.

[6]雷向東,段紅亮,唐麗.移動環(huán)境下多數(shù)據(jù)項請求的廣播策略研究[J].計算機應用研究,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.