多数据项请求的多信道并行广播调度算法

为减少数据广播中用户请求的平均访问时间、提高广播性能,提出了一种新的基于减少数据访问冲突和应用重复广播技术的广播调度算法。该算法有效减少了多信道并行广播中多数据项请求的访问冲突,对热点数据项采取重复广播技术,极大地减少了对热点数据项请求的访问时间。仿真实验结果表明,该算法有效地降低了平均访问时间,提高了数据广播性能,特别是在访问概率偏斜率较大时具有更好的性能。     

多数据项广播调度策略

多数据项广播是移动计算环境中一种重要的数据访问方式.为减少用户的平均访问时间和响应最多事务请求,提出了一种新的多数据项广播调度策略.调度策略分为两个阶段,第一阶段根据各事务包含的数据项数目和对重复申请数据项的处理选择事务请求;第二阶段对已选择的事务请求用QEM算法进行调度.实验结果表明,它比现有的QEM算法有更高事务调度成功率和更短的平均访问时间.     

基于贪心策略的多信道数据广播调度算法

为减少多信道数据广播环境中的多信道平均延迟时间,提出一种基于贪心策略的多信道数据广播调度算法,将数据项合理地分配到各信道,最小化多信道数据项平均访问时间,在每个信道内采用近似最优的Log-time算法。实验结果表明,在不同的系统环境下,该算法都能够达到近似最优的性能。     

移动环境下多数据项请求的广播策略研究*

提出了一种移动环境下的多信道试探广播策略MCHM（multiple channel heuristic method）。该广播策略在多信道广播中采用高效的数据调度算法,在不重复广播的情况下,消除了多信道广播中多数据请求的访问冲突,大大减少了移动客户机的访问时间,提高了数据广播的性能。     

移动环境下多数据项请求广播的改进算法

在移动计算环境下,为提高多数据项请求广播的响应率,提高服务器的响应能力,研究了广播内容选择对响应率的影响,提出了一种新的广播内容选择方式,并对多数据项请求广播调度算法QEM（Query Extend Method）进行了改进。试验结果表明改进后的算法能进一步提高多数据项请求广播的响应率。     

非对称网络环境中数据广播的启发式多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,我们分析了数据广播访问时间的最优值,并提出了一种启发式多盘调度算法（ＨＭＤ）,该算法能够根据给定的数据项访问概率分布,自动生成广播调度。 欠的理论分析和实验结果表明,ＨＭＤ算法是一种高效的数据广播调度算法,具有接近于理论最优值的性能,并且具有良好的可操作性。     

移动环境中请求多数据项的广播调度算法

提出移动环境中请求多数据项的广播调度算法——基于权重的调度算法(BWS)和权重比截止时间算法(WID)。BWS算法根据数据项对客户的满足情况确定权重,并以数据项的总权重作为调度的依据,同时考虑数据项的使用频率和数据项对于客户的满足情况。WID算法以总权重与截止时间的比值作为调度依据,同时考虑广播效率和紧急性的要求。在数据广播调度方面这2种算法比传统的算法具有更好的性能。     

多盘广播的偏斜索引算法

在移动环境中,多盘广播是被广泛使用的数据广播调度算法之一。为广播数据建立索引可以使移动客户机选择性地监听信道,以减少电源消耗,但过多地插入索引会增加数据访问时间。针对该问题,为多盘广播建立偏斜索引,设计索引树构造算法和广播数据的索引树算法。与可变扇出算法相比,多盘广播的偏斜索引算法需要的平均访问时间和平均调谐时间较短。     

基于期限的多请求数据检索问题研究

给定一个包含多条信道的集合以及一个包含多个请求的集合,其中每一个请求包含多个请求数据项并且希望在一定期限内下载到,基于期限的多请求数据检索问题指当客户配有多条天线时寻找一个在期限内下载多个请求的数据检索序列,使得所有天线的最大访问延迟最小化。大多数现有数据检索方法关注于单个请求或者单条天线,很少研究当客户配有多条天线时多请求的数据检索问题,尤其是每一个请求的检索有时间约束。基于此,本文提出一种多请求的数据检索算法,以调度合适地天线检索这些请求并找到关于这些请求的检索序列,从而平衡在各天线上的访问延迟。针对单请求的数据检索,本文采用最大团思想寻找下载该请求中所有请求数据项的访问模式,使得检索该请求的访问延迟以及期限丢失率最小化。     

移动计算环境中数据广播的启发式遗传调度算法

数据广播调度是移动计算环境中数据管理技术的研究热点之一.现有的广播调度算法在移动数据库环境中缺乏一定的实用性.在数据项长度可变的条件下,理论上分析了多盘数据广播的平均访问时间,并提出了一种启发式的遗传调度算法,在广播调度中引入贪婪变换的启发式求解策略.理论分析和实验结果表明,该算法在访问概率偏斜率较大和数据项长度不等的情况下,平均访问时间较小,能很好的适应于移动数据库环境.     

移动计算环境中的自适应混合广播

提出一种自适应混合广播算法。在周期广播数据分配时采用多信道非均匀分配,使高访问率的数据获得高广播频率。在确定周期广播数据和联机请求数据个数时考虑联机请求信道响应时间和访问率之间的关系,从而在少量比较次数后获得数据最佳分割点。实验结果表明,该算法可以根据系统负载和用户访问模式的变化动态调节信道和数据的分配,性能优于纯广播和纯基于请求的广播,访问时间少于现有的混合数据广播方式。     

On-demand broadcast for multiple-item requests in a multiple-channel environment

On-demand broadcast is an effective approach to disseminating data in mobile computing environments. Substantial efforts have been devoted to improving the scheduling efficiency of on-demand broadcast. Previous studies focused mainly on the case of scheduling single-item requests in single-channel environments. However, requesting multiple dependent data items is common in many advanced applications such as electronic stock trading and traffic information enquiry services. In addition, multi-channel architectures are widely deployed in data broadcast systems. In this work, we investigate the issues arising in scheduling multi-item requests in multi-channel on-demand broadcast environments. Two problems, namely, the request starvation problem and the bandwidth utilization problem are identified in existing algorithms. To tackle the observed problems, an innovative algorithm is proposed. Results from our simulation study demonstrate the superiority of the proposed algorithm.     

数据广播调度自适应信道划分与分配方法

随着移动网络的不断发展,移动终端设备的计算能力与日俱增,越来越多的用户倾向于通过移动网络获取信息资源,这使得实时按需数据广播面临新的挑战：（1）数据内容和规模的多样化;（2）用户请求的实时性与需求多样性使得热点数据增加,直接导致广播数据总量的剧增;（3）用户对服务质量和水平的要求越来越高.当前的研究成果主要集中在固定信道模型和算法上,一定程度上忽略了当前数据广播调度环境的变化.固定信道存在如下问题：（1）局限于特定的网络,缺乏通用性;（2）信道大小、个数不能随着网络环境的变化而自动调整,降低了广播效率.基于以上考虑,对实时按需数据广播调度的自适应信道划分和分配进行研究,提出一种自适应信道划分与分配方法OCSM （optimized channel split method）,其根据数据请求特征的不同,实时自适应地调整信道个数和大小,从而提高系统敏感性、鲁棒性以及广播效率.该方法包括：（1）广播数据均衡聚类算法WASC （weight average and size clusteralgorithm）,其挖掘数据特征,为信道划分提供依据;（2）数据项广播优先级评定算法R×W/SL,其实时评定数据项调度优先级;（3）信道划分与分配算法CSA （channel split algorithm）.实验包括两个方面：（1）确定不同数据项大小和请求截止期分布下的信道划分策略,并分析聚类算法中聚类距离K在不同情况下的最佳取值以及最佳信道划分;（2）验证自适应信道划分与分配策略的有效性,并通过对比实验验证在不同情况下OCSM的有效性.实验结果表明：OCSM优于其他调度算法,并具有较强的自适应.     

面向紧急数据的异步多信道工业无线网络调度方法

针对现有时分多址(TDMA)调度方法在面对异步多信道条件下工业紧急数据调度时表现出的时延大、控制信道(CC)饱和、能耗过高等问题,提出一种基于接收端的紧急数据调度方法--EOAM.首先,采用基于接收端的策略,解决了异步多信道调度中存在的控制信道饱和问题;其次,采用特殊信道(SC)结合优先级指示的方法保证紧急数据快速切换信道进行实时传输的同时,允许非紧急数据基于优先级指示标志采用退避机制占用信道,保证了特殊信道的利用率.该方法既适用于单播通信,也适用于广播通信.仿真实验结果表明,相比分布式控制算法(DCA),EOAM的传输延时最低可达8 ms,可靠性可达95%以上,能量消耗降低了12.8%,能满足工业紧急数据的传输需求.     

Channel dynamic adjustment in data broadcast

Data broadcasting has become the preferred method to dispense data to a large number of mobile users. Current researches on on-demand data broadcast mainly propose algorithms based on a single broadcast channel or fixed multi-channel, i.e., fixed channel model. As a result of the dynamic diversity of data characteristics and client demands, the fixed channel model faces significant challenges in parallel broadcast diverse data. Further, the dynamic adjustment of the broadcast channel (dynamic channel model) based on client requests is favorable to service quality because it determines the number and sizes of channels that adapt to client demand in real-time. However, the dynamic channel model has not yet been thoroughly investigated for on-demand wireless data broadcasts. Accordingly, in this paper, a channel dynamic adjustment method (CDAM) is proposed. The innovations behind CDAM lie in three aspects. First, a data item priority evaluation and selection algorithm (S-RxW/SL) is proposed for evaluating the priority of data items and selecting the high priority data items to be considered in a broadcast cycle. Second, a weight and size average cluster algorithm (WSAC) is proposed for mining data item characteristics and clustering them. Third, based on the clustering results of WSAC, a channel splitting and data allocation algorithm (CSDA) is proposed for dynamically splitting the channel and allocating data items to the corresponding sub-channel. We compare the proposed method with some state-of-the-art scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better request loss rate (LR) can be obtained by using our method as compared to its alternatives.     

Multicast Pull Scheduling: When Fairness Is Fine

We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We first show that there is no O(1) -competitive algorithm for this problem. We then give a method to convert any nonclairvoyant unicast scheduling algorithm A to nonclairvoyant multicast scheduling algorithm B . We show that if A works well, when jobs can have parallel and sequential phases, then B works well if it is given twice the resources. More formally, if A is an s -speed c -approximation unicast algorithm, then its counterpart algorithm B is a 2s -speed c -approximation multicast algorithm. It is already known [5] that Equi-partition, which devotes an equal amount of processing power to each job, is a (2 + ε) -speed O(1 + 1/ε) -approximation algorithm for unicast scheduling of such jobs. Hence, it follows that the algorithm {BEQUI}, which broadcasts all requested files at a rate proportional to the number of outstanding requests for that file, is a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. We give another algorithm BEQUI-EDF and show that BEQUI-EDF is also a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. However, BEQUI-EDF has the advantage that the maximum number of preemptions is linear in the number of requests, and the advantage that no preemptions occur if the data items have unit size.