支持連續(xù)周期性查詢的數(shù)據(jù)廣播調(diào)度算法研究.pdf

1、隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)廣播已經(jīng)成為一種主流的通訊方式。在實(shí)際的廣播環(huán)境中，廣播帶寬資源往往有限，因此，如何在保證查詢?nèi)蝿?wù)實(shí)時(shí)性要求的前提下，減小廣播帶寬的開(kāi)銷，這是一個(gè)急需解決的問(wèn)題。
　　在一種新型的廣播環(huán)境中，用戶查詢實(shí)時(shí)數(shù)據(jù)并持續(xù)關(guān)注數(shù)據(jù)的變化。在此環(huán)境下，通常采用的查詢方式是連續(xù)周期性查詢。在現(xiàn)有研究中，只有RM-UO算法適用于此類環(huán)境，然而，此算法在帶寬利用方面存在著明顯不足。當(dāng)使用RM-UO算法調(diào)度查詢?nèi)蝿?wù)集時(shí)，算法

2、首先生成一個(gè)DC任務(wù)集，然后，調(diào)用Sr算法將DC任務(wù)集轉(zhuǎn)化為2諧波任務(wù)集。由于Sr算法往往縮短部分DC任務(wù)的周期，因而，在RM-UO算法的執(zhí)行過(guò)程中，往往存在著廣播帶寬的浪費(fèi)。
　　分析可知，當(dāng)DC任務(wù)集轉(zhuǎn)化為2諧波任務(wù)集時(shí)，一些DC任務(wù)（連續(xù)的或者周期上具有一定關(guān)系的DC任務(wù)）可以合并成一個(gè)任務(wù)，從而減少?gòu)V播帶寬開(kāi)銷?；谏鲜龇治鼋Y(jié)果，提出了兩個(gè)任務(wù)合并規(guī)則（MQM規(guī)則和RQM規(guī)則）和兩個(gè)分別使用這兩種規(guī)則的廣播調(diào)度算法（MQM

3、-UO算法和RQM-UO算法）。此外，由于MQM規(guī)則和RQM規(guī)則的執(zhí)行并不存在沖突，進(jìn)一步提出了一種結(jié)合MQM-UO算法優(yōu)點(diǎn)和RQM-UO算法優(yōu)點(diǎn)的廣播調(diào)度算法―UM算法。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)RM-UO算法相比，UM算法、MQM-UO算法和RQM-UO算法均能減少?gòu)V播帶寬開(kāi)銷，使廣播系統(tǒng)可以同時(shí)為更多查詢提供服務(wù)。
　　上述四種算法均為固定優(yōu)先級(jí)廣播調(diào)度算法，且均調(diào)用RM算法調(diào)度最終的任務(wù)集。由于RM算法的可調(diào)度性閾值較低，上述四

4、種算法的可調(diào)度性受到了影響。于是，嘗試用非固定優(yōu)先級(jí)調(diào)度方式解決支持連續(xù)周期性查詢的廣播調(diào)度問(wèn)題。出于兼顧廣播數(shù)據(jù)共享性的考慮，部分?jǐn)?shù)據(jù)需要周期性廣播，因此，首先對(duì)實(shí)時(shí)調(diào)度問(wèn)題進(jìn)行研究，提出了一種新型的實(shí)時(shí)調(diào)度算法―PEDF算法。當(dāng)使用PEDF算法調(diào)度實(shí)時(shí)任務(wù)集時(shí)，部分任務(wù)可以周期性執(zhí)行。然后，基于PEDF算法，首次提出了一種支持連續(xù)周期性查詢的非固定優(yōu)先級(jí)廣播調(diào)度算法―PCDI算法。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)RM-UO算法相比，PCDI算法