多數據項請求的多信道并行廣播調度算法

呂承飛， 季林峰， 倪 寧

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

0 引 言

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

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

1 多信道并行數據廣播

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

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

圖1 多信道并行廣播模式

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

2 非重復廣播

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

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

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

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

3 多信道重復廣播調度算法

3.1 主要思想

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

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

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

3.2 算法描述

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

表1 符號說明

數據調度過程如下所示：

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

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

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

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

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

圖2 多信道熱點數據項重復廣播模式

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

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

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

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

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

4 性能分析

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

4.1 實驗環境及參數設置

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

表2 仿真系統參數設置

4.2 評價標準

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

4.3 實驗結果及分析

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

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

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

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

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

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

5 結束語

本文研究了在多信道多數據項用戶請求廣播模式下的廣播調度算法，針對多信道并行廣播中的數據訪問沖突問題和廣播周期過長導致用戶請求平均訪問時間過長的問題，提出了一種新的廣播調度算法。該算法能夠有效減少數據訪問沖突，并通過對熱點數據項采用重復廣播技術從而縮短熱點數據項的廣播周期。經仿真實驗表明，該算法能夠很好的降低平均訪問時間，提高廣播性能。目前的重復廣播調度算法比較簡單，下一步將研究更好的重復廣播調度算法。

[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]王亞軍,馬小琴.多數據項廣播調度策略[J].計算機工程與設計,2009,30(23):5329-5331.

[6]雷向東,段紅亮,唐麗.移動環境下多數據項請求的廣播策略研究[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.