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

1、隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)廣播已經(jīng)成為一種主流的通訊方式。在實際的廣播環(huán)境中，廣播帶寬資源往往有限，因此，如何在保證查詢?nèi)蝿?wù)實時性要求的前提下，減小廣播帶寬的開銷，這是一個急需解決的問題。
　　在一種新型的廣播環(huán)境中，用戶查詢實時數(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ù)集時，算法

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

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

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