由于移动网络技术和数据广播支持大量用户同时访问热点数据, 实时按需数据广播被广泛应用于热点数据的传播中, 如股票信息传送、交通信息发布^[1]等实时系统.数据广播包括静态周期广播和按需广播两种方式.由于移动网络用户对信息服务质量要求的不断提高, 实时按需数据广播调度成为当前研究的热点.时效性是按需数据广播调度的重要约束性条件^[2], 设计高效的数据广播调度算法^{[3, 4]}, 最大限度地满足用户请求, 是按需数据广播研究的重中之重.

按需数据广播系统实时接收用户请求, 利用相应的调度算法组织数据广播序列.按需数据广播调度具有按需性和实时性:按需性体现在每个周期所广播的数据由用户请求决定, 实时性体现在用户请求的数据必须在截止期内得到满足.按需数据广播调度有效地降低用户请求的平均等待时间以及移动终端的调谐时间^[5], 因而被广泛应用于动态、大规模数据的广播与传输中.大量文献研究了单一信道按需数据广播, 提出了大量优秀的算法, 如SIN-α, R×W算法等, 这些算法在降低系统请求失效率、平均等待时间、客户端调谐时间^[6]和终端能耗^[7]等方面都有出色表现.但随着移动网络技术的发展, 用户需求的多样化使得对广播调度系统支持多数据项请求的需求不断提高, 例如基于XML文档结构的数据请求等不断增加^[8], 单一信道按需数据广播调度不能发挥多信道并行广播优势.针对这一问题, 大量文献研究了固定多信道多数据项调度算法, 并证明了固定多信道多数据项请求调度是一个NP-hard的问题, 提出了大量的调度分配算法.如TOSA算法等都能很好地结合多信道并行广播的特点, 提高数据广播调度的效率.但固定多信道广播调度算法只能针对特定需求的网络, 不能适应多变的需求环境.

无论是单一信道广播还是固定多信道广播都无法自适应热点数据分散、热点变化快和数据特征差异性大的广播环境:首先, 在移动网络中, 基于结构的物理限制, 例如客户端可能有不同的通信能力, 制约了单一信道高速传输的可行性; 其次, 面向用户应用的需求, 信道可合并或者协调可提供可变的服务质量; 同时, 由于实时热点数据的分散, 多信道广播相对于单一信道广播具有更高的时效性; 最后, 依据广播数据特征实时地调整广播信道, 能够更好地适应多变的移动网络环境.因此, 基于当前用户需求多变的现实以及上述算法存在的若干局限性, 本文对自适应多信道广播调度进行了研究, 提出了一种实时按需数据广播的自适应信道划分与分配方法OCSM(optimized channel split method).

本文的主要研究工作包括如下几个方面.

(1)   提出一种R×W/SL数据项优先级评定算法(其中, R为数据请求数、W为请求最长等待时间、SL为系统即将失效数).该算法同时考虑数据请求数、数据请求最长等待时间和系统即将失效请求数这3个指标, 通过准确评定单个数据项的紧急程度, 为均衡聚类算法提供聚类指标;

(2)   综合考虑数据项大小、信道大小和数据项紧急程度等因素, 提出了广播数据项均衡聚类算法WASC (weight average and size cluster algorithm), 为自适应信道划分方法OCSM提供划分依据;

(3)   提出算法CSA(channel split algorithm), 其根据WASC算法聚类结果将信道划分成多个子信道, 同时, 调度数据广播队列匹配对应子信道进行广播.

本文第1节介绍相关研究工作.第2节介绍实时按需数据广播系统模型.第3节详细介绍自适应信道划分与分配OCSM方法.第4节通过仿真实验确定相应参数的最佳取值, 并通过对比实验验证OCSM方法的有效性.第5节是对全文的总结和未来研究方向的说明.

1 相关工作

实时按需数据广播系统中, 调度算法是关键, 其分为单一信道数据广播调度和多信道数据广播调度.本文主要从这两个方面介绍当前研究的相关成果.

在单一信道实时按需数据广播调度方面, Xuan等人^[9]提出了基于EDF(earliest deadline first)算法的按需广播模型BoD(broadcast on demand), 能有效地保证带宽使用和控制用户访问时间.Lei等人^[10]同时考虑失效率和访问时间, 提出最大价值优先算法MVGF(maximum value gained first).Kalyanasundaram和Velauthapillai^[11]考虑了在单一信道按需数据广播中请求长度和请求截止期因素, 提出了请求长度确定和不确定两种情况下的调度算法BCast和BCast2.Ng等人^[12]针对实时信息传输系统提出了一种MRS(most request served)广播算法, 并且提出一种客户端的缓存策略, MRS在MRF(most request first)的基础上考虑了数据项大小对带宽的敏感性.Lu等人^[13]针对用户请求, 数据项提出两层调度算法SLLH(scheduling scheme with maximum gain heuristic), 能够获得最佳的广播效率.Dewri等人^[14]研究了基于截止期约束的按需数据广播调度, 并指出, 数据项的响应时间和数据项请求的优先级决定了数据项调度效率.当前, 绝大部分考虑请求截止期的调度算法均集中在降低请求失效率^[15]上, 但很少能同时优化等待时间.文献[16]提出的R×W算法考虑了数据项请求数和数据项最长等待时间, 但其数据广播调度模型中各项请求是没有截止期约束的.Xu等人^[17]提出了一种典型的带有截止期约束的按需数据广播调度算法SIN-α(slack time inverse number of pending requests), SIN-α考虑了数据项截止期和数据项当前请求数两个指标.我们在前期研究工作^[18]中提出L×R×W算法, 提出将即将失效数L、数据项请求数R、数据项最长等待时间W同时考虑, 其Weight(d_i)权重指标能够全面的衡量数据项的优先级.对比实验表明, 该算法比EDF, MRF和R×W算法具有更低的失效率以及更短的等待时间.上述几种算法均不考虑数据项大小变化, 即假设数据项大小固定.我们在前期的另一项研究工作中^[19]考虑数据项大小不一的情况, 提出将数据项进行等大小拆分, 结合L×R×W算法, 较好地解决了考虑数据项大小的按需数据广播调度问题.虽然单一信道数据广播在一些情况下面能够取得很好的表现, 但由于单一信道模型的局限, 其不能并行广播来满足数据规模剧增和服务需求个性化提高的现状, 服务质量相对较低.

针对单一信道数据广播存在的缺陷, 许多学者对固定多信道数据广播进行了研究, FLAT^[20]是多信道中最简单的静态广播调度方法, 它以均等的机会将数据分配到多信道中, 因此, 访问热度高的数据同访问热度较低的数据需要花费相同的时间, 算法简单但效率不高.Yee和Navathe^[21]提出一种近似算法GREEDY, 该算法在缩短MCAED(multi-channel average expected delay)问题上取得了接近最优的表现.该算法先将数据按照访问热度排序, 然后在序列中找到最优分割点以降低MCAED, 找到足够的分割点以将队列分割成信道数相等的子队列. Waluyo等人^[22]研究多信道广播环境中多数据项请求的调度机制, 他们关注服务器端的广播顺序以最小化查询访问时间.他们同时提出一个全局的索引策略, 以最小化调谐时间和能量消耗.Lee等人^[23]基于系统负载提出动态的信道分配方法, 该方法根据已知的随机模型动态分配信道.Gao等人^[24]提出一种基于多信道的全局优化调度算法, 利用动态规划结构的AH-Tree(alphabetical huffman tree)索引方案, 在数据请求频率倾斜的情况下, 能最大限度地缩短调谐时间.Lim等人^[25]针对多信道广播系统中普遍存在的数据重叠问题, 提出一种新的用于重叠峰(各信道边界共享的频率范围)信号处理机制SOB(signal vai overlapped band), 能够有效地减少多信道中广播数据的重叠, 大大提高系统效率.Ali等人^[26]考虑多信道下多数据项请求的情况, 提出了一种新的接纳控制算法ILAC(item level admission control).ILAC将一个带有截止期的多数据项请求看作是多个带有相同截止期的虚拟单数据请求, 可以及时通知用户请求是否能够被满足; 同时, 其还提出一种多信道数据匹配调度算法MBA(matching based allocation), 能够最大化地实现请求之间的数据共享, 同时减小信道切换的可能性.Hu等人^[27]研究了多信道广播环境中混合数据传输的问题, 提出了自适应平衡方法ABS(adaptive balanced scheme)来执行确定性的搜索.Zheng等人^[28]同时考虑了数据优先级、数据大小和信道带宽这3个因素, 提出了近似算法TOSA(两层优化调度算法)来获取接近最优的多信道平均延迟MCAED:第1层调度策略将数据群集到信道中, 第2层调度在各个信道中进行以保证平均的最优表现.虽然固定多信道数据广播解决了单一信道数据广播存在的一些问题, 但随着用户请求多样性的提高, 固定信道数据广播无法自适应当前广播环境, 从而提供更灵活多变的服务.

尽管有大量学者对单一信道数据广播以及固定多信道数据广播进行了研究, 但仍缺乏一种有效的自适应信道划分算法.本文试图通过对数据请求分布、截止期分布、数据项大小分布进行分析和挖掘, 在广播之前对待广播数据项进行聚类, 根据聚类结果来自适应划分信道, 提高数据广播调度的服务质量.

2 系统模型

在按需数据广播调度模型^{[29, 30]}中, 我们假设广播系统包括一个服务器以及多个用户.服务器维护一个请求队列RQ(rquest queue)、一个准备队列PQ(pending queue)以及多个广播队列BQ_i, 0 < i < n(broadcast queue), 其中, n为系统广播队列个数.RQ负责收集用户请求, 服务器根据RQ从数据库中获取数据生成PQ.服务器周期性地运用OCSM方法从PQ提取数据组织广播.每当用户需要一个数据时, 通过上行信道上传一个请求至服务器.本文假设每个用户一次只产生一个请求, 并且同一用户前后两次请求的数据不具有关联性.上传请求后, 用户侦听下行信道获取数据, 数据项大小是不唯一的.系统包含一个上行信道、若干个下行信道, 上行信道带宽远小于下行信道, 本文假设用户可同时侦听多个下行信道.具体的, 基于OCSM的数据广播调度模型如图 1所示.

系统由4部分组成.

(1)   接收(接收移动客户端的请求).移动客户端通过上行信道提交自己的请求, 每个请求包括请求的数据项标签、请求截止期等信息.服务器接收请求, 先检查对应数据项是否存在于广播队列或准备队列中:如果在, 则直接将请求加入相应数据项的请求列表中; 如果不在, 则将请求按时序加入请求队列中;

(2)   获取(从数据库获取请求数据).服务器从请求队列中取出当前时间的请求, 从因特网、数据库或服务器的缓存中查找满足请求的数据项, 获取数据项组织成数据项信息.本文不考虑服务器获取数据的时间和服务器的缓存策略;

(3)   划分(将原信道划分成多个子信道).服务器根据OCSM方法依据获取的准备队列数据将原信道进行划分, OCSM方法首先利用R×W/SL算法确定PQ中每一个数据项d_i的权重值, 为下一步提供聚类指标; 然后, 利用WASC算法根据数据项权重值以及数据项大小将PQ划分成n个子集合; 最后, 利用算法CSA依据WASC生成的n个子集合对原信道进行划分以及分配;

(4)   调度(调度广播队列进行数据广播).服务器周期地将广播队列发送到卫星或者基站, 卫星或基站通过下行信道将广播队列中的数据项广播出去.基于OCSM方法的数据广播调度流程见表 1.

3 OCSM方法

数据项优先级${P_{{d_i}}}$、数据项大小$Siz{e_{{d_i}}}$能够很好地刻画数据项的特征.通过将PQ数据项按${P_{{d_i}}}, Siz{e_{{d_i}}}$这两个指标进行聚类, 将聚类的结果作为划分信道的依据, 能够找到最适合广播的子信道个数以及大小.最后, 将数据置于对应的子信道中进行广播, 这就是OCSM方法的基本思想.本节详细介绍OCSM框架, 如图 2所示.

OCSM方法包含R×W/SL算法、WASC算法和CSA算法.

●  R×W/SL确定PQ中每一个数据项d_i的权重值, 为下一步提供聚类指标;

●  WASC根据${P_{{d_i}}}$以及数据项大小$Siz{e_{{d_i}}}$将PQ划分成n个类别FG={g₁, …, g_i, …, g_n}, 其中, g_i表示第i个分组;

●  CSA根据FG将信道C划分成对应的相应的n子信道集合SC={c₁, …, c_i, …, c_n}, 并将g_i分组的数据项置于子信道c_i进行广播.

3.1 算法R×W/SL

请求失效率LR(request lost rate)、平均等待时间AAT(average access time)是衡量实时数据广播系统服务质量的指标.为了提高系统的服务质量, 通常采用的策略是:通过算法确定数据项优先级${P_{{d_i}}}$, 选取${P_{{d_i}}}$最大的数据项进行广播.在不考虑数据项大小的情况下, SIN-α算法以及L×R×W算法采用权重值$W{f_{{d_i}}}$来衡量数据项, 根据$W{f_{{d_i}}}$调度广播, 实验证明这了两种算法的有效性.如何在考虑数据项大小的情况下准确地衡量数据项的${P_{{d_i}}}$, 是本节致力解决的问题.

本文针对数据项大小不一的情况, 在L×R×W算法的基础上做出改进, 提出R×W/SL算法.由于我们无法预知$Siz{e_{{d_i}}}$, 故我们假设下一时刻广播数据项d_i, 得出广播结束时间, 由此计算出广播d_i将导致系统其他请求总的失效数$S{L_{{d_i}}}$, 选取使$S{L_{{d_i}}}$最小的d_i优先广播.同时, 考虑数据项请求数(${R_{{d_i}}}$)、最长等待时间(${W_{{d_i}}}$)两个因素.通过公式(1)计算$W{f_{{d_i}}}$值衡量数据项的紧急度, 以此确定数据项的优先级${P_{{d_i}}}:$

$W{f_{{d_i}}} = \frac{{{R_{{d_i}}} \times {W_{{d_i}}}}}{{S{L_{{d_i}}}}}$

(1)

其中, ${R_{{d_i}}}$表示数据项d_i请求数, ${W_{{d_i}}}$表示数据项d_i对应请求的最长等待时间, $S{L_{{d_i}}}$为广播d_i将导致系统其他请求总的失效数.

$W{f_{{d_i}}}$的值越大, 数据项优先级${P_{{d_i}}}$越高.在公式(1)中, $S{L_{{d_i}}}$可能为0, 此时就用${R_{{d_i}}} \times {W_{{d_i}}}$衡量d_i的优先级.因此, 公式(1)修改为公式(2):

$W{f_{{d_i}}} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{R_{{d_i}}} \times {W_{{d_i}}}}}{{S{L_{{d_i}}}}}, {\rm{ if }}~S{L_{{d_i}}} \ne 0} \\ {{R_{{d_i}}} \times {W_{{d_i}}}, {\rm{ if }}~S{L_{{d_i}}} = 0} \end{array}} \right.$

(2)

3.2 算法WASC

本节介绍均衡聚类算法WASC, WASC用于聚类PQ, 生成n个类别的集合FG.第3.2.1节对数据聚类进行分析, 提出两个聚类指标.第3.2.2节详细介绍了WASC算法的实现, 将PQ中数据项根据第3.2.1小节提出的聚类指标$Siz{e_{{d_i}}}, W{f_{{d_i}}}$自聚类生成FG, 为信道划分提供依据.

3.2.1 数据聚类分析

在按需数据广播调度算法中, 需要考虑的3个主要因素是数据项大小$Siz{e_{{d_i}}}$、数据项的权重值$W{f_{{d_i}}}$以及信道大小Bw.下面分析以上3个因素之间的关系.为了便于分析, 本文做出如下符号定义:信道C划分成n个子信道, SC={c₁, …, c_i, …, c_n}, 子信道c_i的带宽为$B{w_{{c_i}}}$, 即$Bw = \sum\limits_{i = 1}^{i = n} {B{w_{{c_i}}}} $; 广播周期k子信道c_i的广播价值定义为${V_{{c_i}, k}}$, 求解公式如公式(3)所示:

${V_{{c_i}, k}} = W{f_{{d_1}, {c_i}, k}} + W{f_{{d_2}, {c_i}, k}} + ... + W{f_{{d_i}, {c_i}, k}} = \sum\limits_{{d_i} \in {c_i}} {W{f_{{d_i}, {c_i}, k}}} $

(3)

其中, $W{f_{{d_i}, {c_i}, k}}$为广播周期k子信道c_i中第i个数据项的权重值.故信道C总的广播价值SumV_k求解如公式(4):

$Sum{V_k} = {V_{{c_1}, k}} + {V_{{c_2}, k}} + ... + {V_{{c_n}, k}} = \sum\limits_{j = 1}^{j = n} {{V_{c{}_j, k}}} = \sum\limits_{j = 1}^{j = n} {\sum\limits_{{d_i} \in {c_j}} {W{f_{{d_i}, {c_j}, k}}} } $

(4)

直观上认为, 一个周期内广播价值SumV_k越高, 广播系统的效率越高.

(1) 数据大小:分析数据大小对广播调度的影响.

假定将信道划分成两个子信道Bw₁=3, Bw₂=1, 数据项d₁, …, d₅大小为3, d₆, …, d₁₀大小为1, 各数据项权重值均为1, 广播周期为5s.按照数据项大小聚类如图 3(a)、图 3(b)所示.从图 3(a)结合公式(4)可以计算出SumV_k=10, 而若不将数据项放置于与其大小相对应的信道中广播, 会存在较大的信道浪费; 图 3(b)展示了一种较极端的情况, 信道存在3个单位的带宽浪费, 同时SumV_k=9, 小于按数据项大小聚类广播.同时, 通过图 3(a)、图 3(b)的对比可发现, 周期性数据广播调度在待广播数据饱和的情况下存在的带宽浪费主要来自于每个周期间隙带宽浪费.依据数据项大小进行聚类, 以聚类结果对信道进行划分, 能找到最适合当前待广播数据集的信道带宽, 从而大大减小周期间隙带宽浪费, 提高信道利用率.

(2) 数据权重值:分析数据项权重值对调度的影响.

假定将信道划分成两个子信道Bw₁=2, Bw₂=2, 被请求的数据项d₁, …, d₈大小均为2, 其中, d₁, …, d₄权重值为5, d₅, …, d₈权重值为1, 广播周期为3s.按照数据项权重值均衡化广播如图 3(c)、图 3(d)所示.在图 3(c)中, 权重值为5的数据项分散到两个信道中广播.广播周期结束后, 数据项d₇, d₈未能及时广播, 可以计算出总信道广播价值SumV_k=22.若不将权重值大的数据项均匀分散于各个广播队列, 将可能出现如图 3(d)所示的情形.权重值大的数据项拥挤与一个信道内, 导致总信道广播价值为SumV_k=18, 大大影响了广播效率.

通过上面的分析发现:将数据项大小相接近的数据项聚集在一起广播, 能够充分利用信道带宽, 减少周期间隙带宽的浪费; 将权重值大的数据项均匀分散至各个信道广播, 将有利于提高单位时间内信道所广播的总价值, 从而大大提高信道利用率.

3.2.2 WASC实现

通过上一小节的分析, 得出$Siz{e_{{d_i}}}, W{f_{{d_i}}}$两个聚类指标对聚类的影响.将数据项集合按照$Siz{e_{{d_i}}}$聚类, 有利于带宽的充分利用; 将数据项集合按照$W{f_{{d_i}}}$分散广播, 有利于提高单位时间内信道广播价值.本文提出WASC算法, 将数据项集合按$Siz{e_{{d_i}}}$进行聚类, 然后依据$W{f_{{d_i}}}$将聚类子集合G分散成FG.

下面将具体介绍均衡聚类算法的实现.WASC算法主要分为3步.

(1) $Siz{e_{{d_i}}}$聚类.

运用改进的KODAMA(knowledge discovery by accuracy maximization)^[31]算法, 将数据按大小聚类.

(ⅰ)  初始化:将N个数据项分成N类, 定义数组T={t₁, …, t_i, …, t_N}作为分类器, 其中, t_i为d_i的类标签.运用KNN算法对样本进行10倍交叉验证, 得出预分类标签Z_T={z₁, …, z_i, …, z_N}, 其中, z_i为d_i的预分类标签.计算分类精准度值A_T;

(ⅱ)  随机交换T与Z中错误分类样本标签, 生成新的分类标签数组V={v₁, …, v_i, …, v_N}.对V运用KNN算法进行10倍交叉验证, 得出预分类标签Z_V={z₁, …, z_i, …, z_N}, 计算分类精准度值A_V, 若A_V > A_T, 用V取代T, 将Z_V取代Z_T, A_T等于A_V.

循环执行步骤(ⅱ), 直到A_T等于1或者达到最大循环次数.

(2) 分类标签调整.

经过步骤(1)产生的T中各个类别的类标签并非连续的数列, 为方便信道的划分, 需要步骤(2)对T中类标签进行调整.采用分类标签调整策略TRS(tag rank strategy), 将数据项集合D分成n/2个子集合G={g₁, …, g_i, …, g_n/2}.具体的调整策略见表 2.

(3) $W{f_{{d_i}}}$均衡化处理

将数据项权重值均匀的分散各个子集合.对应于G中的每一个子集合g_i生成fg_2i-1, fg_2i两个子集合, 如果$S{W_{f{g_{2i - 1}}}} > S{W_{f{g_{2i}}}}$, 将g_i中数据项d_j添加到子集合fg_2i中; 否则, 添加到fg_2i-1中.其中, $S{W_g} = \sum\limits_{{d_i} \in g} {w{f_{{d_i}}}} $.通过$W{f_{{d_i}}}$的均衡化处理, 生成最终的分类子集合FG.

综上3步, WASC算法实现见表 3.

3.3 算法CSA

算法CSA根据分类子集合FG将信道进行划分, 随后将数据项分配至对应的子信道进行广播.其主要包含信道划分以及数据项分配两个部分.

(1)   信道划分:广播信道带宽由其待广播数据项特征决定.广播信道与广播数据项相适应, 可以进一步提高算法效率.通过均衡聚类挖掘待广播数据项数据特征.数据项大小聚类, 充分利用信道带宽, 数据项依据权重值分散, 提高了信道周期广播价值.将广播信道根据其待广播数据进行自适应划分, 划分子信道情况由聚类结果决定;

(2)   信道分配:将数据项分配至对应子信道内进行广播.根据每个待广播数据项的分类标签, 将其分配至对应的子信道组成子广播队列.然后, 根据算法确定的权重值将子广播队列进行排序, 权重值大的数据项优先于权重值小的数据项广播.具体CSA算法见表 4.

4 实验分析

为了验证多信道数据广播OCSM方法相对于单一信道数据广播的优势, 本文选取R×W算法来进行对比性实验.OCSM是基于按需的多信道单请求数据广播调度算法, 为了验证其在固定多信道按需广播调度中的有效性, 本文试图选取多种当前文献中最新最优的按需多信道单数据项调度算法进行对比, 但经过文献查阅, 未发现服从该约束条件的对应算法.因此, 本文选取两种高效的静态广播调度算法GREEDY和TOSA, 并依据本文研究对象和环境的不同进行适当改进, 编写算法程序与OCSM进行对比性实验.第4.1节介绍实验相关环境, 包括基本参数设定及仿真实验评价体系.第4.2节验证了OCSM中参数K在不同数据请求情况下的最佳取值集合.第4.3节在数据请求服从不同分布情况下, 对比了算法OCSM与R×W, GREEDY以及TOSA的表现.第4.4节在数据请求截止期服从不同分布情况下, 对比了算法OCSM与R×W, GREEDY以及TOSA的表现.第4.5节对比了不同数据项大小对算法OCSM, GREEDY以及TOSA算法的影响程度.

4.1 实验环境

(1) 实验数据

本文的对比实验采用了1998年世界杯期间官方网站每天的数据访问集^[32], 该数据集中, 平均每天有超过700 000个请求, 平均请求速率为83条/秒, 包括近22 000个不同的Web页面和图片对象.为了便于进行对比实验, 在进行实验前, 我们对数据项大小、带宽进行了归一化处理, 数据项平均大小为1个单位, 广播带宽为10单位/秒.为了模拟请求的时间限制, 每个请求被赋予一个随机生成的截止期, 平均截止期为60s.系统请求速率默认值设定为100条/秒, 仿真运行时间设定为3 600s, 一个仿真周期共产生360 000个请求, 数据集中包含20 000个数据项可被请求.OCSM方法划分形成的子信道数设定在4~6个之间浮动.为了保证对比实验的开展, 设定其余对比算法的默认广播信道数为5.第4.2节、第4.3节、第4.4节将在不同请求速率、截止期、数据项大小情况下进行对比实验, 具体的实验参数将在对应章节中详细说明, 公共实验参数设定见表 5.

(2) 评价指标

实时按需数据广播系统中, LR, AAT是衡量服务质量的两个重要指标.有效地降低请求失效率等同于有效地缩短平均访问时间.为了简化对比实验, 省去重复工作, 同时更直接地展示算法的效果, 本文选取请求失效率作为衡量算法有效性的评价指标.用户请求失效数总和与所有请求总和的比值被称为请求失效率.M个周期总请求失效数为${L_M} = \sum\limits_{k = 1}^M {\sum\limits_{i = 1}^N {Le{d_{{d_i}.k}}} } , Le{d_{{d_i}.k}}$为数据项d_i在第k个周期的请求失效数; M个周期总请求成功数为$S{C_M} = \sum\limits_{k = 1}^M {\sum\limits_{i = 1}^N {S{C_{{d_i}, k}}} } , S{C_{{d_i}, k}}$为数据项d_i在第k个周期的成功请求数.则请求失效率可表示如公式(5)所示:

$LR = \frac{{{L_{k < M}}}}{{{L_{k < M}} + S{C_{k < M}}}} = \frac{{\sum\limits_{k = 1}^M {\sum\limits_{i = 1}^N {Le{d_{{d_i}.k}}} } }}{{\sum\limits_{k = 1}^M {\sum\limits_{i = 1}^N {Le{d_{{d_i}.k}}} } + \sum\limits_{k = 1}^M {\sum\limits_{i = 1}^N {S{C_{{d_i}, k}}} } }}$

(5)

4.2 OCSM中最佳参数K的确定

OCSM方法中, 采用K最近邻(k-nearest neighbor, 简称KNN)分类算法作为有监督的分类器^[33], KNN中, K值的选取对聚类效果产生重要的影响:若K值较小, 则只有与预测样本较近的训练样本才会对预测结果起作用, 但容易发生过拟合; 若K值较大, 优点是可以减少学习的估计误差, 但缺点是学习的近似误差增大, 这时与预测样本较远的训练样本也会对预测起作用, 使预测准确率降低.在算法实际运行过程中, 聚类样本的数据特征随着截止期和请求数据分布的变化而变化.只有依据样本数据特征选取对应的最佳K值, 才能够使算法达到精准的聚类效果, 为CSA算法提供准确划分依据, 从而有效地利用信道.由于本文主要研究不同截止期分布和请求数据分布下算法的有效性, 所以在请求数据特征和请求截止期分布不同时, 本节验证不同的K值对数据广播调度的影响.

在本组实验中, 选取平均截止期为60s, 数据项平均大小为1, 数据请求速率为100条/秒.一般认为:具有N个样本的分类中将K取值为$\sqrt N $能取得较好的分类效果, 每个广播周期约有200个样本.本文设定K的取值范围为10~100.图 4是截止期服从不同分布(固定分布、均匀分布、指数分布)和请求数据服从不同分布(正态分布、均匀分布、Zipf分布)的情况, 分别展现了请求失效率LR、平均访问时见AAT、划分子信道个数NSC(number of sub-channel)三者在不同的K值时算法的效率比较, 其中, 请求失效率LR、平均访问时间AAT最能反映调度算法的有效性以及系统的信道利用率.

图 4描述了在不同请求截止期分布和不同数据请求分布的组合情况下, 有监督分类器KNN中K值对数据广播调度效率的影响.

通过图 4的实验结果, 本文得出如下结论.

(1)   随着K值的不断增加, 数据项样本聚类生成的子类类别数呈下降趋势;

(2)   在所有请求截止期和数据请求分布组合下, AAT随K值的增大先保持稳定, 随后呈现上升趋势, 最后逐渐趋于稳定.这是因为随着K值的增大, 样本的聚类精度变差, 系统广播调度效果受到聚类精度的影响, 从而导致平均等待时间变长;

(3)   当K值处于10~30区间时, 请求失效率呈现轻微下降趋势; 当K值处于35~45区间时, 请求失效率迅速增大, 然后随着K值的增大, 失效率基本保持在较高的服务水平状态.

通过上面的分析, 本文得出最优K值以及对应信道划分N值见表 6.

4.3 不同数据请求分布下OCSM有效性验证

本组实验对比在数据请求服从不同分布(Zipf分布、均匀分布、正态分布)下, OCSM, R×W, GREEDY和TOSA算法的效率, 评价指标采用LR.理论上数据请求越集中, 广播效率越高.因为请求越集中, 广播单个数据项所满足的用户请求数越多.数据请求在Zipf分布下的概率密度为${P_i} = \frac{{{{(1/i)}^\theta }}}{{\sum\limits_{i = 1}^{20000} {{{(1/i)}^\theta }} }}$, 其中, P_i为数据项d_i被访问的概率, 设定参数θ=1.数据请求均匀分布设定平均值为10 000, 数据正态分布为标准正态分布, 即μ=0, σ²=1.对于不考虑数据项大小的算法R×W, GREEDY, 数据项大小设定为1个单位, 其他对比算法设定数据项大小服从均匀分布, 平均大小为1个单位.请求截止期服从均匀分布, 平均大小为60秒.数据请求服从Zipf分布、均匀分布、正态分布时对应的K值分别设定为25, 18, 11.

图 5(a)~图 5(c)分别展示了数据请求服从Zipf分布、均匀分布、正态分布时, 请求速率变化对各对比算法的影响.

从图中可以得出如下结论.

(1)   4种对比算法的失效率都随着请求速率的增大而升高.其中, 两种静态调度算法GREEDY和TOSA在请求速率较低时失效率高于R×W和OCSM.这是因为静态调度算法所广播的数据不是由当前用户请求决定, 用户必须等待系统广播.当请求速率较高时, 用户所请求的数据覆盖了大部分静态广播内容, 此时, 静态多信道广播算法优势明显;

(2)   当请求服从Zipf分布情况下, 请求热点相对于其余两种分布更集中, 请求数据特征明显, 4种算法的表现都比较好.其中, OCSM表现最好, 这也证实了在数据特征明显的情况下, OCSM中的聚类效果能够较准确地找到适合广播的信道划分方式;

(3)   当数据请求服从正态分布、请求速率大于60条/秒时, GREEDY和TOSA失效率低于R×W算法.TOSA失效率一直优于GREEDY算法, 这得益于TOSA两层优化模式.同其余3种算法相比, OCSM算法表现优于R×W和GREEDY算法, 在请求速率较低时优于TOSA; 而随着请求速率的增大, 具有与TOSA算法表现相近.这是因为当请求服从正态分布时, 请求数据具有较大的偏向性, 这种情况更能发挥OCSM自适应划分信道的优势, 从而采用更适合的信道大小广播数据;

(4)   当数据请求服从均与分布时, 可以看出, 所有算法的失效率普遍偏高.当请求服从均匀分布时, 请求数据相对分散, 即热点数据不集中, 这种情况对数据广播调度十分不利.同时也可以发现:静态广播算法由于受请求分布影响较小, 随着请求速率增大, 失效率增长速度低于按需调度算法.OCSM在请求速率较低时同TOSA, R×W算法表现相近, 而当请求速率较高时, 其表现劣于TOSA算法.这是因为热点数据分散, 聚类算法不能发挥作用;

(5)   通过对比3种情况下各算法的表现可以发现, 请求热点数据相对集中有利于数据广播调度.因为热点数据集中, 广播一个热点数据所服务的用户量增多, 从而提高系统调度效率.同时也可以发现, 静态调度算法在请求速率较低时表现不如按需调度算法, 但其受速率变化影响较小, 在请求速率较高时仍能保持较低的失效率.在这3种请求分布下, OCSM算法综合表现较好, 尤其是在请求数据特征明显的Zipf分布时, 请求失效率相对于TOSA低接近5%;在其余两种情况下, 也同TOSA算法保持相近的失效率.

4.4 不同截止期分布下OCSM有效性验证

截止期是影响调度算法效率的重要因素之一, 截止期越短, 满足该请求的可能性越小, 请求失效率越高. OCSM算法采用降低系统总即将失效请求的思路, 充分考虑请求截止期这一因素.本组实验对比在截止期服从不同分布时, 算法OCSM, R×W, GREEDY, TOSA的LR变化情况.对比算法中:不考虑数据项大小的调度算法, 数据项大小固定为1个单位; 考虑数据项大小的调度算法, 数据项大小服从均匀分布, 平均大小设定为1个单位, 并设定数据请求分布服从Zipf分布, 请求速率为100条/秒.截止期服从均匀分布、指数分布、固定分布时K值分别设定为18, 17, 17.

图 6(a)~图 6(c)分别展示了截止期服从均匀分布、指数分布和固定分布时, 截止期大小变化对各对比调度算法的影响.

从图中可以得出如下结论.

(1)   不同分布情况下, 各对比算法请求失效率随着截止期增大的变化趋势基本相似, 即:随着截止期不断增大, 各算法的请求失效率降低.当截止期处于区间10~85时, 请求失效率下降迅速; 当截止期处于85到210区间时, 所有算法的失效率逐渐趋于平缓.在请求截止期较短的情况下, 4种算法的表现相近, 失效率都在40%以上; 而随着截止期的延长, 两种静态调度算法GREEDY和TOSA的失效率下降速度低于按需调度算法R×W和OCSM.这是因为静态调度算法广播数据项是由系统根据广播之前得到的数据热度来决定的, 其中有一部分数据并不会被广播, 因此即使截止期继续延长, 静态调度算法也会保持较高的失效率.OCSM将截止期因素考虑进去, 能够更加准确地衡量一个数据项的紧急度, 因此能够在截止期服从不同分布的情况下都取得比R×W算法更优的失效率, 后者仅考虑了数据请求数以及最长等待时间;

(2)   当截止期服从均匀分布时, R×W和OCSM在区间10~60内, LR下降速度明显快于GREEDY和TOSA.其中:OCSM表现最好, 一直处于请求失效率最低的状态; 而R×W算法在截止期大于85以后表现仅次于OCSM.两个静态调度算法GREEDY, TOSA则一直保持较高的失效率, 其中, TOSA算法略优于GREEDY;

(3)   当截止期服从指数分布时, 请求截止出现的概率随着截止期长度的增大而减小, 故截止期分布相对集中于较小的一端, 4种对比算法在这种情况下都表现最差.而由于截止期分布较集中, 特征明显, 有利于OCSM中聚类的准确性, OCSM在这种情况下仍然能够取得很好的表现, 请求失效率明显低于其余3种算法;

(4)   当截止期服从固定分布时, OCSM算法表现跟R×W算法相近, 因为所有请求截止期都相同, 这使得考虑了截止期因素的OCSM算法相对于不考虑截止期因素的R×W算法的优势不突出.然而, 得益于OCSM算法的自适应多信道广播, 其表现还是稍微优于R×W算法.因为截止期固定, 使得在截止期较小的10~60区间内, 各算法的失效率基本呈梯度下降趋势.这说明在截止期较小时, 截止期是影响失效率的主要因素; 但随着截止期的增大, 各算法失效率降低速度逐渐放缓.在这种情况下, TOSA算法的失效率略低于OCSM算法, 说明固定截止期更适合静态调度算法.

综上, 通过在截止期服从均匀分布、指数分布、固定分布时, 4种算法请求失效率的对比, 验证了OCSM算法的具有较好的有效性.当截止期服从均匀分布以及指数分布时, OCSM算法比R×W, GREEDY和TOSA算法表现更优; 当截止期服从固定分布时, OCSM算法表现接近TOSA.

4.5 数据项大小变化OCSM有效性验证

数据项大小是影响广播调度的另一个重要因素, 数据项越大, 单位时间广播的数据越少, 所能满足的请求越少, 请求失效率越高.OCSM算法综合运用数据项大小决定广播信道大小的思想, 自适应寻求更适合的信道大小.本组实验对比了OCSM同R×W, GREEDY, TOSA算法在数据项大小服从固定分布下的算法效率.设定数据请求服从Zipf分布, 请求速率为100条/秒, 请求截止期服从均匀分布, 截止期平均大小为60秒, K值设定为18(如图 7所示).

从图 7得出如下结论.

(1)   由于R×W, GREEDY算法没有考虑数据项大小的因素, 其表现较差, LR随着数据项的递增, 几乎呈线性递增的趋势.其中, GREEDY算法受数据项大小的影响最大, 随着数据项的增大而广播周期变长, 从而导致大量截止期较短的请求得不到满足而失效;

(2)   TOSA和OCSM算法考虑到数据项单位大小的广播价值, 优先广播单位价值高的数据, 从而随着数据项大小的增加, 仍能取得较低的失效率, 其中, OCSM算法表现一直优于TOSA.

5 结论与展望

为了克服现有固定信道数据广播调度的不足, 进一步提高实时按需数据广播的调度效率, 本文提出了一种基于实时按需数据广播调度的信道划分与分配方法OCSM.OCSM首先通过R×W/SL算法确定数据项权重值; 然后利用WASC算法根据数据项权重值以及数据项大小对数据进行均衡聚类; 最后利用CSA算法划分信道, 组织数据进行广播调度.为了验证OCSM的性能, 本文模拟现实广播环境, 进行了大量的对比实验, 并得出以下结论.

(1)   相对于单信道按需数据广播调度算法R×W, OCSM提出的自适应信道划分策略能够充分利用多信道并行广播的特性, 更好地降低失效率;

(2)   WASC算法在请求数据倾斜程度较大时表现更好, 因为此时的数据特征明显, 使得WASC算法聚类更准确;

(3)   相对于多信道数据广播调度算法GREEDY和TOSA, OCSM具有更强的自适应性, 在不同的情况下都有较好的表现.

本文在如下本文在如下几个方面需要进一步展开研究:(1)在自适应信道划分与分配的基础上, 研究索引策略, 进一步缩短用户请求的调谐时间; (2)考虑用户请求包含多个数据项的情况, 研究相应的信道划分算法.

致谢 我们真诚地向对本文的工作给予支持和建议的审稿人、主编、编辑、同行、同学和老师表示感谢.