多信道环境下的偏斜调度策略研究

马小琴

（池州学院 数学与计算机科学系，安徽 池州 247000）

1 引言

数据广播是无线环境中数据访问和数据发布的一种有效方式[1]。服务器端广播一次数据项，能够同时满足所有侦听该数据项的移动客户机端的请求，并且其性能不会受客户机数量的限制，因而数据广播具有很大的灵活性和可扩展性。而怎样组织数据项来尽可能地减小访问时间即广播调度策略是数据广播技术的一个重要研究方向。

访问时间[2-3]是衡量数据广播调度策略优劣的重要指标之一，多信道广播通过多条信道广播数据项在一定程度上减少了用户的访问时间，现有不少文献[4-5]对多信道广播调度进行了研究。但大部分都是基于访问概率相似的调度算法[6]，也就是说在每个信道内部各数据项只广播一次，这样不利于热数据的访问，而现实应用环境中，访问数据通常呈现80-20现象。针对这种不足，本文提出了多信道环境下的一种偏斜调度策略。首先引入了近似最优的TOSA[7]的高层调度算法，然后将经典的多盘调度[8]应用于低层调度。该策略使用两层调度来生成调度序列，高层借鉴了近似最优的TOSA的高层调度方法，而低层用多盘调度使得热数据在一个广播周期中出现多次以减少对热数据的访问时间，从而整体上降低了平均访问代价。最后，通过仿真实验验证该策略能提高访问效率，且当访问频率相差较大时，多信道广播性能更优。

2 TOSA算法与多盘调度算法

2.1 TOSA算法

TOSA算法是由高层的数据分配算法和低层的log-time算法两层算法构成，高层的数据分配算法负责将数据项依次地分配到每个信道，低层的Log-time算法对每个信道内的数据项进行调整以进一步优化访问时间。其中，数据分配算法由初始化和调整两个部分组成。初始化部分把N个数据项分配到K个信道中，其具体的算法思想是将每2B个数据项归为一组，前B个数据项依次放入1至K的信道，后B个数据项依次放入信道K至1的信道，各信道中放入的数据项的总数正比于该信道带宽的平方根。调整部分的算法思想是不断地调整最大的信道和最小的信道，使得信道趋于相等，这样进一步地降低了用户的平均访问时间，优化了多信道广播的访问性能。

2.2 多盘调度算法

多盘调度算法是一种广泛使用的调度算法，该算法有利于用户较快地访问到高频数据，适合于偏斜访问的环境。其基本思想是将客户机频繁访问的数据（热数据）放入高速磁盘，将不经常访问的数据（冷数据）放入低速磁盘来减少热数据的访问时间从而整体上减少平均访问时间，其性能明显优于平坦调度。

2.3 TOSA算法与多盘调度的联系

TOSA的高层数据分配算法在多信道环境下达到近似最优，而实际环境中数据访问往往呈现偏斜现象，而多盘调度是经典的偏斜访问调度算法，因此在每个信道中采用多盘调度替代TOSA的低层调度，以此降低偏斜访问的平均访问时间。

3 多信道广播调度策略（MSAS）

3.1 算法基本思想

MSAS算法的主要思想是根据近似最优TOSA算法的高层数据分配算法将数据项顺序地分配到各个信道，然后对每个信道中的数据项采用多盘调度算法广播数据项，这样大大缩短了热数据的访问时间，从而进一步减少了用户的平均访问时间。

3.2 算法的具体实现

3.2.1 算法实现的适用范围及符号定义 为使本算法更好地应用于多信道广播环境，首先作如下假设：

(1)多信道无差错地广播所有数据项；

(2)单数据项请求；

(3)数据项长度相等；

(4)数据访问是偏斜的。

为分析方便，约定表1的符号含义：

表1 符号含义

3.2.2 算法过程 算法实现的主要步骤：

（1）每2B个数据项划为一组，前B个数据项依次放入1至K的信道，后B个数据项依次放入信道K至1的信道，实现N个数据项放入到K个信道中。

算法：

输入：各个信道的带宽、各数据项的长度以及N个数据项的访问概率；

输出：将N个数据项放到K个信道的初始分区的结果；

1:将数据项排序，使得对于任意的i≤j，

2:将信道排序，使得对于任意的 i≤j，Bi≥Bj;

（2）不断地调整上面初始分区结果中的最大Aj/信道和最小信道，使得信道近似相等。

算法：

输入：N个数据项的初始分区结果；

输出：优化后的N个数据项的结果；

（3）在每个信道中使用多盘广播调度算法调度数据项。

为了适用于偏斜访问模式的广播环境，本调度策略在步骤 （3）中采用经典的多盘调度算法取代TOSA低层的log-time算法，使得在各个信道中的一个广播周期内热数据项广播多次，这样大大减小了热数据的访问时间，从而整体上优化了用户的平均访问时间。

4 实验

4.1 实验模型

在这部分，我们估计MSAS算法的性能，并且与多信道的GREEDY[9]算法进行比较。实验中性能衡量标准是平均访问时间（TAT，The average access time）。Zipf分布能够比较好地描述偏斜的访问概率分布。在Zipf分布中，若数据项总数为N，则第h个数据项的访问概率为：

实验中假设数据项长度和信道带宽是固定不变的常数，实验参数如表2。依次比较了在偏斜因子、数据量的大小以及信道数目变化的情况下对算法性能的影响。

表2 实验参数

4.2 实验结果及分析

4.2.1 实验1：偏斜因子θ取值的影响 假设有10000个数据项，K=2，如图1显示随着θ值的增加，MSAS算法的平均访问性能优于GREEDY算法，这是因为GREEDY算法在一个周期内每个数据项只广播一次，在偏斜因子增大的情况下，增加了热数据的访问时间，从而影响了用户的平均访问时间，而MSAS算法在低层采用了多盘调度对偏斜的数据访问更有利。

图1 对平均访问时间的影响

4.2.2 实验2：数据项个数N的影响 如图2显示了随数据项个数增加的变化情况，设定信道个数K=3，=0.75，数据项个数的增加必然会加大用户的平均等待时间，而MSAS算法在高层调度是近似最优的调度算法，且在低层考虑了热点数据的频繁访问特性，因此在平均访问时间上优于GREEDY算法。

图2 N对总访问时间的影响

4.2.3 实验3：信道数目K的影响 本实验设定N=10000和=0.75。从图3的实验结果可以看出，MSAS算法的性仍然优于GREEDY算法。信道数目从2增加到12，信道个数的增加减少了每个信道中广播的数据项，而MSAS算法在每个信道上考虑了偏斜访问的特性，因此比基于平坦调度基制的GREEDY算法的访问时间减小的更明显。

图3 K对平均访问时间的影响

4 结束语

本文提出了一种多信道环境下偏斜访问模式的调度策略，高层调度引入了TOSA算法的高层数据分算法，低层采用了多盘调度算法以进一步优化平均访问时间。本算法大大减少了热数据的访问时间从而整体上减少了平均访问时间。实验结果表明，本算法比GREEDY算法有更好的性能，特别适用于偏斜访问模式的环境。

[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]孟小峰，周龙骧，王珊.数据库技术发展趋势[J].软件学报，2004，15(12):1822-1836.

[3]余平.移动环境中的数据广播调度理论分析及算法研究[J].计算机科学，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]张铁军，王鸿鹏，杨孝宗.移动计算环境中的数据有效访问技术研究[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，Franklin 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.