吕承飞， 季林峰， 倪 宁

(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.