移動環(huán)境下多數(shù)據(jù)項請求的廣播策略研究

摘 要:提出了一種移動環(huán)境下的多信道試探廣播策略MCHM(multiple channel heuristic method)。該廣播策略在多信道廣播中采用高效的數(shù)據(jù)調(diào)度算法，在不重復(fù)廣播的情況下，消除了多信道廣播中多數(shù)據(jù)請求的訪問沖突，大大減少了移動客戶機的訪問時間，提高了數(shù)據(jù)廣播的性能。

關(guān)鍵詞:移動計算; 多信道; 數(shù)據(jù)廣播; 訪問沖突; 訪問時間

中圖分類號:TP311.13文獻標志碼:A

文章編號:1001-3695(2009)09-3487-03

doi:10.3969/j.issn.1001-3695.2009.09.081

Research of broadcast scheme for multi-item requests under mobile environment

LEI Xiang-dong， DUAN Hong-liang， TANG Li

(College of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:This paper proposed a multiple channel heuristic method(MCHM). This model used high efficiency data scheduling scheme under multi-channel broadcast environment， avoided data-item access collision and didn’t broadcast repeatedly. From the result of experiments， this model reduces the access time greatly and improves the data broadcast capability efficiently.

Key words:mobile computing; multi-channel; data broadcast; access collision; access time

由于無線網(wǎng)絡(luò)的帶寬具有非對稱性(下行帶寬遠大于上行帶寬)，數(shù)據(jù)廣播技術(shù)是一種有效數(shù)據(jù)訪問方式，以較小的代價來支持大量移動設(shè)備并行訪問數(shù)據(jù)庫，且具有很好的可擴展性。

近年來，為了改善數(shù)據(jù)廣播的性能，提出了不少數(shù)據(jù)調(diào)度策略，但大部分均是假設(shè)移動客戶機(mobile client， MC)在任意時刻只請求廣播信道中的單個數(shù)據(jù)項。在很多應(yīng)用系統(tǒng)中，移動客戶機需要同時請求廣播信道中的多個數(shù)據(jù)項。例如，一個MC要獲取Cisco、Microsoft和IBM三只股票的價格。在單數(shù)據(jù)項廣播系統(tǒng)中，MC需分別提交三次數(shù)據(jù)訪問請求。而在多數(shù)據(jù)項廣播中，用戶只需提交“申請Cisco. Microsoft和IBM 股票價格”一次數(shù)據(jù)訪問請求即可。

在文獻[1～3]中提出的高效單個數(shù)據(jù)項的訪問模式并不適合多數(shù)據(jù)項的訪問，因為在多數(shù)據(jù)項訪問模式中必須考慮同一用戶請求中內(nèi)部數(shù)據(jù)項間的訪問沖突。文獻[4]提出了單信道中多數(shù)據(jù)請求的QEM方法，它以訪問概率為基準，以貪婪的方式擴展數(shù)據(jù)請求中的所有數(shù)據(jù)項。文獻[5]提出了改進的MQEM算法，通過放松QEM的兩個約束條件，獲得了比QEM算法更好的性能。為了進一步提高訪問效率，本文分析了多信道中的多數(shù)據(jù)項請求策略，提出了一種多信道試探廣播策略(MCHM)，最后通過仿真實驗驗證該策略能提高數(shù)據(jù)廣播的性能。

1 多信道并行數(shù)據(jù)廣播

多信道并行數(shù)據(jù)廣播是指多個信道同時進行數(shù)據(jù)廣播，與單信道數(shù)據(jù)廣播相比，多信道并行數(shù)據(jù)廣播能大大減少MCs的訪問時間，更好地滿足人們對實時性的要求。在多信道并行數(shù)據(jù)廣播中，由于多個數(shù)據(jù)項被同時廣播，多個數(shù)據(jù)項之間可能存在數(shù)據(jù)訪問沖突。

數(shù)據(jù)訪問沖突是指在多數(shù)據(jù)請求中，被同一用戶請求的兩個或多個數(shù)據(jù)項在多信道廣播中被同時廣播。

假設(shè)廣播模式如圖1所示，用戶請求Q需一次性請求四個數(shù)據(jù)項d2、d3、d5、d6。由于d5、d6同時被廣播，用戶請求Q不能在一個廣播周期中獲取d5、d6 ，即d5、d6存在數(shù)據(jù)訪問沖突。因為一個用戶一次只能監(jiān)聽一個信道，當兩個不同的數(shù)據(jù)項在兩個不同的信道中被同時廣播，則不可能同時被一個用戶訪問到。

t1t2t3t4t5t6

channel1

d4d6d2

channel2

d1d3

channel3

d5

圖1 數(shù)據(jù)訪問沖突

若在一個用戶請求中出現(xiàn)數(shù)據(jù)訪問沖突，該用戶不可能在一個廣播周期中獲取所有所需數(shù)據(jù)項，需要等待下一個廣播周期再訪問沖突的數(shù)據(jù)項。因此，數(shù)據(jù)訪問沖突的存在大大增加了移動客戶端的訪問時間。

2 多信道試探廣播策略(MCHM)

本文在多信道并行廣播模式的基礎(chǔ)上，提出了試探廣播策略，充分考慮到了多信道廣播的優(yōu)勢以及可能出現(xiàn)的數(shù)據(jù)訪問沖突。以下從數(shù)據(jù)調(diào)度和實例運行兩方面進行分析。

2.1 數(shù)據(jù)調(diào)度

本文假設(shè)每個用戶需要訪問的數(shù)據(jù)項如表1所示。

表1 用戶請求數(shù)據(jù)表

d1d2d3d4d5d6d7d8d9d10

Q11111

Q21111

Q31111

Q41111

Q51111

其中:di為第i數(shù)據(jù)項;Qi為第i個用戶請求，標志為1表示用戶需要請求的數(shù)據(jù)項。本文符號說明如表2所示。

表2 符號說明

符號含義

di第i個數(shù)據(jù)項

Qi第i個用戶請求

n數(shù)據(jù)項的個數(shù)

m用戶請求的個數(shù)

freqi第i個用戶請求的訪問頻率

QDSi第i個用戶請求的數(shù)據(jù)項集

Blist已調(diào)度的用戶請求集

Bset已調(diào)度的所有數(shù)據(jù)項集

QRi第i個請求未調(diào)度數(shù)據(jù)項集

Remi第i個請求未調(diào)度數(shù)據(jù)項個數(shù)

Overlapi第i個請求的數(shù)據(jù)項重疊個數(shù)

其中:Overlapi=|QDSi∩Bset|，即未調(diào)度的用戶請求Qi的數(shù)據(jù)項與已調(diào)度的數(shù)據(jù)項集的重疊個數(shù);QRi=QDSi-(QDSi∩Bset)，Remi=|QDSi|-Overlapi;D ={d1，d2，d3，…，dn}，Q ={Q1，Q2，Q3，…，Qm}。

在數(shù)據(jù)調(diào)度過程中，應(yīng)該盡量避免數(shù)據(jù)訪問沖突。訪問沖突的發(fā)生將會直接導(dǎo)致客戶端訪問時間的增長。本文假設(shè)不考慮同一用戶請求中數(shù)據(jù)項的訪問順序，將多信道并行廣播模式看成一個c×t矩陣。其中，c為信道數(shù)，t為時間數(shù)。數(shù)據(jù)調(diào)度過程分為以下幾步:

a)將freqi最大的用戶請求中的數(shù)據(jù)項調(diào)入信道中，每列(ti)只調(diào)入一個數(shù)據(jù)項。

b)計算剩下未調(diào)度的每個用戶請求的(freqi/ Remi)值，選擇其中最大者。

c) 對b)中用戶請求中的每一個未調(diào)度的數(shù)據(jù)項(dk∈QRi)，從第一列開始，從上至下檢查該列中每個數(shù)據(jù)項是否與當前數(shù)據(jù)項存在訪問沖突(同時存在于任一個用戶請求中)。若存在沖突或該列已滿，則轉(zhuǎn)入下一列檢查，否則將數(shù)據(jù)項放入該列。



d)跳至c)，直至所有用戶請求調(diào)度完成。

算法描述如下:

Bset=， Blist=

set Qc= the query with the highest value of freqi/Remi in Q

put(Qc， c×t)/*put Qc in c×t model， each column has only one data item*/ 

Q=Q- Qc， Blist=Blist∪Qc

while(Q!=)

set Qc= the query with the highest value of freqi / Remi in Q

for each data item dK in QRi /*find right column for each data item in QRi*/

for each collumn/*examine collisions in each column*/

set int l=1;

if (collision(dK， l))

then jump to the next column;

else

{if the lth column is full

then jump to the next

column;

else

{put di in the lth column;

return;}

}

end for

end for

Q=Q-Qc， Blist=Blist∪Qc

end while

boolean collision(dcurrent， int l)/*check collision between data items in the lth column and the current data item dcurrent. */

{

for each data item dc in the lth column

if (Qi (dc∈QDSi and dcurrent∈QDSi))

then return true;

else

return 1;

}

2.2 實例運行

在表2中，有五個用戶請求Q1、Q2、 Q3、 Q4、 Q5，假設(shè)在三個信道中進行廣播，用戶請求的訪問頻率分別為30、35、20、40、25，即Q1:d2、 d4、 d5、 d10freq1=30;Q2:d1、 d3、 d7、d10freq2=35;Q3:d2、 d5、d8、d9freq3=20;Q4:d3、d4、d6、d9freq4=40;Q5:d1、d6、d7、d10freq6=25。

調(diào)度過程有以下幾個步驟:

a)首先選擇freqi最大者(Q4)調(diào)入廣播信道中，如圖2(a)所示。

b)在剩下的Q1、Q2、Q3、Q5中計算Remi，Rem1=30/3=10，Rem2=35/3=11.67，Rem3=20/3=6.67，Rem5=25/3=8.33，將Q2調(diào)入廣播信道中，如圖2(b)所示。

c)在剩下的Q1、Q3、Q5中計算Remi，Q5已經(jīng)調(diào)入廣播信道中，再依次將Q1、Q5調(diào)入廣播信道中，最終如圖2(c)所示。廣播周期統(tǒng)一為調(diào)度后的所有信道中從開始到結(jié)束的長度。廣播周期的長度為5。

t1t2t3t4t5t6

channel1

d3d4d6d9

channel2

channel3

(a)調(diào)入Q4

t1t2t3t4t5t6

channel1

d3d4d6d9d7

channel2

d1d10

channel3

(b)調(diào)入Q2

t1t2t3t4t5t6

channel1

d3d4d6d9d7

channel2

d2d1d5d10

channel3

d8

(c)依次調(diào)入Q1，Q5

圖2 實例運行

3 性能分析

本文在Pentium M處理器、256 MB內(nèi)存環(huán)境下進行仿真實驗，主要從平均訪問時間(average access time，AAT)對本文提出的MCHM策略以及QEM、MQEM多數(shù)據(jù)項訪問策略進行了分析比較。假設(shè)移動客戶機查詢請求的訪問概率服從Zipf分布，描述為pi=(1/i)θ/∑mi=1(1/i)θ。其中:pi為第i個用戶請求的訪問概率(0≤pi≤1)，θ為斜率;訪問時間(access time， AT)是指從MC開始偵聽到完成下載所需數(shù)據(jù)項的時間間隔。ATi表示Qi的訪問時間，AAT=∑mi=1ATi×pi。由于被訪問數(shù)據(jù)項的重疊會影響到訪問時間，文獻[4]提出了選擇度(selecti-vity)，即存在重疊的數(shù)據(jù)項個數(shù)與所有數(shù)據(jù)項個數(shù)的比率。仿真參數(shù)如下:1 000個不同的數(shù)據(jù)項，每個用戶請求訪問數(shù)據(jù)項的個數(shù)為2～20，五個廣播信道，有300個用戶請求，選擇度的默認值為0.3，斜率(θ) 默認值為0.5。

圖3中顯示了不同的斜率(θ)對平均訪問時間的比較。圖4為不同的選擇度對平均訪問時間的比較。可見，MCHM的平均訪問時間比QEM、MQEM都低，原因是在MCHM中，由多個信道來承擔數(shù)據(jù)廣播，大大縮短了廣播周期，同時消除了數(shù)據(jù)訪問沖突，MCs能在一個廣播周期內(nèi)獲取所需的所有數(shù)據(jù)項。通過分析比較，MCHM能進一步提高多數(shù)據(jù)項訪問的廣播性能。

4 結(jié)束語

為了能夠適應(yīng)信息量的不斷增加以及用戶對數(shù)據(jù)訪問效率的不斷提高，本文提出了移動環(huán)境下多信道數(shù)據(jù)試探廣播策略(MCHM)，消除了數(shù)據(jù)訪問沖突，減少了MCs的平均訪問時間，提高了移動環(huán)境下的廣播性能。在本文提出的高效廣播策略的基礎(chǔ)上建立相應(yīng)的高效索引策略是筆者下一步要完成的工作。

參考文獻:

[1]ZHENG Bai-hua， WU Xia， JIN Xing， et al. TOSA: a near-optimal scheduling algorithm for multi-channel data broadcast[C]//Proc of the 6th International Conference on Mobile Data Management. Cyprus:ACM Press，2005:29-37.

[2]YEE W G， NAVATHE S B. Efficient data access to multi-channel broadcast programs[C]//Proc of the 12th International Conference on Information and Knowledge Management. New Orleans:ACM Press，2003:153-160.

[3]HSU C H， LEE G， CHEN A L P. A near optimal algorithm for generating broadcast programs on multiple channels[C]//Proc of the 10th International Conference on Information and Knowledge Management. Atlanta:ACM Press，2001:303-309.

[4]CHUNG Y D，KIM M H. QEM: a scheduling method for wireless broadcast data[C]// Proc of the 6th International Conference on Database Systems for Advanced Applications. Washington DC:IEEE Press，1999:135-142.

[5]LEE G L ， LO S C. Broadcast data allocation for efficient access of multiple data items in mobile environments[J]. Mobile Networks and Applications， 2003，8(4):365-375.