移動(dòng)環(huán)境下數(shù)據(jù)廣播中的混合索引技術(shù)

摘 要：為了提高移動(dòng)客戶機(jī)的電能使用效率，提出結(jié)合兩種常用的索引技術(shù)——樹索引和哈希索引的復(fù)合性索引模型。該模型既減少了移動(dòng)客戶機(jī)的電量消耗延長了使用時(shí)間，同時(shí)又保證了訪問時(shí)間沒有大幅增加。最后用JavaSIM仿真工具對混合索引模型、樹索引模型和哈希索引模型進(jìn)行了仿真研究，仿真的結(jié)果表明，在訪問時(shí)間、調(diào)諧時(shí)間、索引效率等方面，混合索引模型具有較好的性能和實(shí)用價(jià)值，達(dá)到了設(shè)計(jì)目的。

關(guān)鍵詞：移動(dòng)計(jì)算;索引;諧調(diào)時(shí)間;訪問時(shí)間;仿真

中圖分類號：TP311.13文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)06-0315-03

0 引言

隨著移動(dòng)設(shè)備和通信設(shè)備的發(fā)展，移動(dòng)計(jì)算越來越普及，人們可以在移動(dòng)設(shè)備如手提電腦、手機(jī)、PDA等通過無線網(wǎng)絡(luò)來存儲數(shù)據(jù)。然而， 由于無線網(wǎng)絡(luò)的帶寬有限且具有非對稱性(下行帶寬遠(yuǎn)大于上行寬) ， 數(shù)據(jù)廣播技術(shù)是針對移動(dòng)環(huán)境中無線網(wǎng)絡(luò)的特點(diǎn)的一種有效數(shù)據(jù)訪問方式， 以較小的代價(jià)來支持大量移動(dòng)設(shè)備并行訪問數(shù)據(jù)庫［1］。

從廣播信道中有效地訪問數(shù)據(jù)有兩個(gè)關(guān)鍵的要求：節(jié)約電能和盡量減少移動(dòng)客戶端的等待時(shí)間。在基于數(shù)據(jù)廣播的系統(tǒng)中，移動(dòng)客戶端必須等待到服務(wù)器廣播它所需要的數(shù)據(jù)時(shí)才能獲得所需要的數(shù)據(jù)，而客戶端的等待時(shí)間取決于廣播數(shù)據(jù)的長度。廣播數(shù)據(jù)的長度又叫做廣播周期，廣播周期越長，數(shù)據(jù)訪問時(shí)間也就越長。

在無線環(huán)境中的，移動(dòng)設(shè)備所配備的電量是有限的。研究表明移動(dòng)設(shè)備的電量大部分是消耗在監(jiān)聽無線信道和檢查所接收的數(shù)據(jù)包上［2］。在文獻(xiàn)[3]中，有選擇地監(jiān)聽概念的提出就是減低基于數(shù)據(jù)廣播系統(tǒng)的電量消耗。通過有選擇性地監(jiān)聽，移動(dòng)客戶端可以在大部分時(shí)間處于休眠狀態(tài)僅僅是它想要的數(shù)據(jù)來到時(shí)才被激活。索引技術(shù)就是在無線環(huán)境下用來實(shí)現(xiàn)選擇性監(jiān)聽的，索引跟數(shù)據(jù)一起廣播幫助移動(dòng)客戶端定位請求的數(shù)據(jù)。移動(dòng)客戶端大部分時(shí)間處于休眠狀態(tài)，因此極大地減低了電量消耗。與之同時(shí)，帶索引的數(shù)據(jù)廣播增加了廣播周期的長度，這導(dǎo)致了移動(dòng)客戶端的等待時(shí)間的延長。在實(shí)際應(yīng)用中，不同的應(yīng)用對客戶端的等待時(shí)間和電量消耗的要求各不一樣。

近年來，為了改善數(shù)據(jù)的訪問性能，提出了不少數(shù)據(jù)訪問方法。大部分方法都是基于下列三種技術(shù)［3］：樹索引、簽名索引［4］和哈希索引，一些混合數(shù)據(jù)訪問方式同時(shí)被提出。評價(jià)數(shù)據(jù)訪問方式的優(yōu)劣有下面三個(gè)標(biāo)準(zhǔn)：（1）訪問時(shí)間（Access Time）。它是指從客戶提出訪問請求， 到結(jié)果返回所需的時(shí)間。訪問時(shí)間決定了用戶訪問數(shù)據(jù)的響應(yīng)時(shí)間。

（2）諧調(diào)時(shí)間（Tune－in Time）。它是指在完成一個(gè)訪問請求期間，移動(dòng)設(shè)備保持接聽廣播的總時(shí)間。調(diào)諧時(shí)間決定了移動(dòng)設(shè)備的電源消耗， 因?yàn)樵诓唤勇爮V播的時(shí)間里， 移動(dòng)設(shè)備可以轉(zhuǎn)入休眠模式， 此時(shí)移動(dòng)設(shè)備消耗的電源相對于啟動(dòng)狀態(tài)可以忽略不計(jì)。

（3）索引效率（Indexing Efficiency）。它是指每增加一單位的訪問時(shí)間能夠節(jié)約多少的諧調(diào)時(shí)間。它與訪問時(shí)間和諧調(diào)時(shí)間都相關(guān)，它是用來刻畫在維持可接受的訪問時(shí)間的增加的情況下把諧調(diào)時(shí)間減低到最小。

總之，一種節(jié)約電能的索引技術(shù)必須去平衡索引代價(jià)（訪問時(shí)間的增加）和諧調(diào)時(shí)間的節(jié)約目的是達(dá)到索引效率的最大化。

1 常見的索引技術(shù)

數(shù)據(jù)廣播中一般采用簡單的樹索引結(jié)構(gòu)和哈希索引結(jié)構(gòu)。 樹索引結(jié)構(gòu)能大幅減少調(diào)諧時(shí)間但同時(shí)也增加了數(shù)據(jù)的訪問時(shí)間，而且數(shù)據(jù)廣播的組織形式對其性能影響比較大。哈希索引結(jié)構(gòu)雖然減少調(diào)諧時(shí)間的性能沒有樹索引好，但它幾乎不增加數(shù)據(jù)的訪問時(shí)間，同時(shí)它的適應(yīng)能力強(qiáng)，其性能受數(shù)據(jù)廣播的組織形式比較少。

1.1 樹索引技術(shù)［5］

樹索引是一種比較傳統(tǒng)的數(shù)據(jù)索引技術(shù)，樹索引技術(shù)在無線數(shù)據(jù)廣播里，數(shù)據(jù)幀到達(dá)時(shí)間代替了數(shù)據(jù)記錄的物理存儲位置。 訪問采用樹索引的數(shù)據(jù)廣播分為下面幾步：

（1）初始探測。客戶機(jī)監(jiān)聽廣播信道，獲得廣播中下一個(gè)樹索引的到達(dá)時(shí)間。

（2）搜索。客戶機(jī)順著一系列指針找到想要幀的到達(dá)時(shí)間。遍歷的指針數(shù)目等于索引樹的高度。

（3）檢索。客戶機(jī)監(jiān)聽信道下載它請求的所有數(shù)據(jù)幀。

圖1 索引樹結(jié)構(gòu)

圖1描述了在一個(gè)廣播周期中具有81個(gè)節(jié)點(diǎn)的索引樹的例子。最下層的方塊代表幾個(gè)數(shù)據(jù)幀的集合，它分為兩部分，一部分為可重復(fù)部分，一部分為非重復(fù)部分。

1.2 哈希(Hash)索引技術(shù)

哈希方法廣泛用于信息檢索，一個(gè)數(shù)據(jù)幀的哈希值是數(shù)據(jù)幀的關(guān)鍵字通過一個(gè)特定的哈希函數(shù)運(yùn)算得來的。哈希函數(shù)的選擇對哈希索引技術(shù)性能來說至關(guān)重要。哈希索引技術(shù)一般包括一些步驟：

（1）初始監(jiān)聽。客戶機(jī)監(jiān)聽廣播信道去獲得第一個(gè)哈希值。

（2）過濾。客戶機(jī)訪問連續(xù)的哈希值和數(shù)據(jù)幀找到想要的數(shù)據(jù)，一般來說，它要花廣播的半個(gè)周期去找到它想要的第一個(gè)數(shù)據(jù)幀。

（3）檢索。客戶機(jī)監(jiān)聽信道得到連續(xù)想要的數(shù)據(jù)幀。

哈希值的長短與哈希函數(shù)的平均失效率對諧調(diào)時(shí)間和訪問時(shí)間都有影響。

2 混合索引的設(shè)計(jì)

樹索引技術(shù)和哈希索引技術(shù)都有其優(yōu)缺點(diǎn)，比如說，樹索引技術(shù)適合隨機(jī)數(shù)據(jù)訪問，哈希索引技術(shù)適合順序結(jié)構(gòu)數(shù)據(jù)，像廣播信道這樣的。樹索引技術(shù)對簇集的數(shù)據(jù)廣播非常有效，但簇集對哈希索引技術(shù)性能影響不大。哈希索引技術(shù)特別適合多屬性的數(shù)據(jù)索引，樹索引技術(shù)提供了一種基于索引值較準(zhǔn)確和完整的全局視圖，客戶機(jī)能快速地在樹索引上找到想得到的數(shù)據(jù)的到達(dá)時(shí)間，這樣，諧調(diào)時(shí)間自然就縮短了。由于哈希索引不包含數(shù)據(jù)幀的全局信息，它僅僅只能對客戶機(jī)判定當(dāng)前數(shù)據(jù)幀是否與查詢有關(guān)提供幫助。過濾的有效性很大程度上取決于哈希索引的平均失效率。

下面提出一種稱之為混合索引的新型索引方法，該方法結(jié)合了樹索引和哈希索引兩種索引技術(shù)，吸收了他們的優(yōu)點(diǎn)。廣播索引結(jié)構(gòu)如圖2所示。

圖2 混合索引的邏輯結(jié)構(gòu)圖

這個(gè)結(jié)構(gòu)的上層是一個(gè)索引樹可重復(fù)部分的結(jié)構(gòu)，最下層是一個(gè)哈希索引結(jié)構(gòu)。

客戶機(jī)能通過搜索索引樹獲取想要數(shù)據(jù)幀的大概位置信息。索引樹高度一般不高，因此檢索索引樹的代價(jià)不高。由于混合索引技術(shù)是建立在哈希索引技術(shù)之上的，它保留了哈希索引技術(shù)的所有優(yōu)勢；同時(shí)，索引樹提供數(shù)據(jù)的全局信息，進(jìn)一步減少了諧調(diào)時(shí)間。這種新的索引技術(shù)訪問數(shù)據(jù)分以下幾步：

（1）初始探測。客戶機(jī)監(jiān)聽信道判定下一棵索引樹的到達(dá)時(shí)間。

（2）搜索。根據(jù)接收到的索引樹，客戶機(jī)得到自己想得到的數(shù)據(jù)幀的最近監(jiān)聽時(shí)間。

（3）過濾。在最近的位置，通過哈希值進(jìn)行過濾，直到找到想要的數(shù)據(jù)幀。

（4）檢索。客戶機(jī)監(jiān)聽信道下載所需要的數(shù)據(jù)幀。

2．1 混合索引模型代價(jià)分析

為了分析這種新型的索引技術(shù)，定義了表1所示的參數(shù)表。

表1分析模型的參數(shù)表

參數(shù)含義

D數(shù)據(jù)廣播中數(shù)據(jù)幀的數(shù)量

N整個(gè)數(shù)據(jù)廣播中數(shù)據(jù)包的數(shù)量

P一個(gè)數(shù)據(jù)幀中包含的數(shù)據(jù)包數(shù)量

A訪問時(shí)間

T諧調(diào)時(shí)間

B哈希函數(shù)過濾的失效率

Tp訪問一個(gè)數(shù)據(jù)包所需的時(shí)間

H索引樹的高度

K索引樹的扇出度

S所要檢索數(shù)據(jù)包的數(shù)量

Q為哈希值所占的數(shù)據(jù)包的數(shù)量

假定一個(gè)數(shù)據(jù)幀里包含P個(gè)數(shù)據(jù)包，一個(gè)索引樹節(jié)點(diǎn)只占用一個(gè)數(shù)據(jù)包。同時(shí)在每個(gè)數(shù)據(jù)幀頭部都有一個(gè)哈希值，所檢索的數(shù)據(jù)包都聚集在一起。設(shè)X為索引樹的全部節(jié)點(diǎn)數(shù)，根據(jù)混合索引的索引結(jié)構(gòu)可知：

2.2 仿真實(shí)驗(yàn)

為進(jìn)一步測試新型混合索引的性能，本文用Java語言的一個(gè)仿真軟件包JavaSIM［6，7］進(jìn)行了仿真實(shí)驗(yàn)。仿真參數(shù)如表2所示。

表2模擬比較環(huán)境參數(shù)

圖3 訪問時(shí)間比較

從圖3中的訪問時(shí)間看，隨著數(shù)據(jù)幀數(shù)量的增大，每一種索引技術(shù)的訪問時(shí)間都會增加。在增加的幅度上，樹索引的增加最快，混合索引居中。跟以前的分析很擬合，在訪問時(shí)間上哈希索引的性能最好，混合索引居中，樹索引性能最差。

從圖4可知，隨著數(shù)據(jù)幀的數(shù)量增加，樹索引和混合索引在諧調(diào)時(shí)間上趨于穩(wěn)定，哈希索引有所增加；在諧調(diào)時(shí)間上哈希索引的性能最差，混合索引居中，樹索引性能最好。

從圖5可知，在數(shù)據(jù)幀數(shù)量較小時(shí)，哈希索引的效率最高，隨著數(shù)據(jù)幀的增加，索引樹和混合索引的效率逐漸提高，哈希索引效率趨向穩(wěn)定。在數(shù)據(jù)幀數(shù)量進(jìn)一步增大的時(shí)候，混合索引顯示出了它的優(yōu)勢。

圖4 諧調(diào)時(shí)間比較圖5 索引效率的比較

3 結(jié)束語

本文提出的混合索引方法達(dá)到了設(shè)計(jì)目的，在一定程度上減少了諧調(diào)時(shí)間具有很高的索引效率，具有一定的實(shí)用性。但該索引方法還有改進(jìn)的地方，如能否減低索引樹的高度，在哈希方法時(shí)采用多級哈希函數(shù)，這些新的思路還要有待研究。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。