廣域傳感器數(shù)據(jù)庫中的緩存技術(shù)研究

莊緒路

摘 要： 廣域傳感器數(shù)據(jù)庫是當(dāng)前國際上備受關(guān)注的由多學(xué)科高度交叉的新興熱點(diǎn)研究領(lǐng)域。廣域傳感器數(shù)據(jù)庫具有巨大的應(yīng)用價(jià)值，應(yīng)用前景十分廣闊?；诰彺婕夹g(shù)和預(yù)取技術(shù)，提出了一種緩存技術(shù)與預(yù)取技術(shù)相結(jié)合的體系結(jié)構(gòu)。對(duì)體系結(jié)構(gòu)中各個(gè)模塊的功能和實(shí)現(xiàn)算法進(jìn)行了詳細(xì)闡述，對(duì)算法進(jìn)行了復(fù)雜性和實(shí)例分析，有效地解決了廣域傳感器數(shù)據(jù)庫系統(tǒng)中，低頻結(jié)點(diǎn)數(shù)據(jù)進(jìn)入緩存替換出高頻結(jié)點(diǎn)數(shù)據(jù)所造成的緩存命中率低和系統(tǒng)資源浪費(fèi)問題。

關(guān)鍵詞： 廣域傳感器； 數(shù)據(jù)庫； 緩存技術(shù)； 預(yù)取技術(shù)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2015）03-25-02

Abstract： Wide area sensor database is the current international concerns and the interdisciplinary emerging hot research field， it has very broad application prospect and great application value. Based on combination of the caching with prefetching technology， a system structure is put forward， the function and the algorithm of each module in the system structure is set forth，and the complexity of the algorithm is analysed with the example. The problem of low hit ratio and the waste of system resources in wide area sensor database， that is caused by the high frequency node data be replaced when the low frequency node data get into the cache， is effectively solved.

Key words： wide area sensor； database； cache technology； prefetching technology

0 引言

廣域傳感器數(shù)據(jù)庫是當(dāng)前國際上備受關(guān)注的、由多學(xué)科高度交叉的新興熱點(diǎn)研究領(lǐng)域[1]，具有十分廣闊的應(yīng)用前景，在軍事國防、工農(nóng)業(yè)、城市管理、生物醫(yī)療、環(huán)境監(jiān)測(cè)、搶險(xiǎn)救災(zāi)、防恐反恐、危險(xiǎn)區(qū)域遠(yuǎn)程控制等許多領(lǐng)域都有重要的科研價(jià)值和巨大的實(shí)用價(jià)值，已經(jīng)引起了世界許多國家軍界、工業(yè)界和學(xué)術(shù)界的高度重視，被認(rèn)為是對(duì)21世紀(jì)產(chǎn)生巨大影響力的技術(shù)之一。

1 現(xiàn)有緩存技術(shù)的局限性

廣域傳感器數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)的存儲(chǔ)和訪問是以結(jié)點(diǎn)的形式來實(shí)現(xiàn)的。在一個(gè)時(shí)間段內(nèi)用戶訪問結(jié)點(diǎn)數(shù)據(jù)的頻率高低不同，加之系統(tǒng)緩存的容量有限，當(dāng)系統(tǒng)要緩存一些低頻結(jié)點(diǎn)數(shù)據(jù)時(shí)，很可能會(huì)將某些高頻結(jié)點(diǎn)數(shù)據(jù)替換出去。隨后用戶再次訪問這些高頻結(jié)點(diǎn)時(shí)，在緩存中無法找到相應(yīng)的信息，則需要發(fā)送子查詢重新收集該結(jié)點(diǎn)數(shù)據(jù)，這樣勢(shì)必導(dǎo)致傳感器網(wǎng)絡(luò)中用于傳遞查詢語句和查詢結(jié)果消息的數(shù)量增加，繼而用戶訪問延遲增加，影響了整個(gè)系統(tǒng)的工作效率。為了在緩存中保留那些高頻結(jié)點(diǎn)數(shù)據(jù)，必須有效地限制低頻結(jié)點(diǎn)數(shù)據(jù)進(jìn)入緩存，而單純的緩存技術(shù)解決此問題具有很大的局限性[2～3]。

2 緩存技術(shù)與預(yù)取技術(shù)相結(jié)合

為了進(jìn)一步縮短用戶查詢的響應(yīng)時(shí)間，可以根據(jù)服務(wù)器中用戶的訪問歷史在網(wǎng)絡(luò)帶寬可以滿足的條件下對(duì)一些結(jié)點(diǎn)數(shù)據(jù)進(jìn)行預(yù)取[4]。因此，本文提出了一個(gè)緩存技術(shù)與預(yù)取技術(shù)相結(jié)合的體系結(jié)構(gòu)。結(jié)點(diǎn)數(shù)據(jù)在進(jìn)入緩存之前必須經(jīng)過預(yù)取模型的判斷，把訪問頻率低于一定值的結(jié)點(diǎn)篩選掉，同時(shí)保證那些高頻結(jié)點(diǎn)數(shù)據(jù)存入緩存中。此方法不僅可以減少用戶訪問延遲，而且可以提高緩存的命中率，是對(duì)緩存技術(shù)的有效補(bǔ)充[5～7]。如圖1所示。與傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)文檔形式的緩存有所區(qū)別，廣域傳感器數(shù)據(jù)庫系統(tǒng)中緩存的是結(jié)點(diǎn)數(shù)據(jù)。

2.1 查詢分析器

查詢分析器的主要功能是對(duì)用戶輸入的XPath查詢進(jìn)行分析，確定用戶要查詢的結(jié)點(diǎn)名稱。根據(jù)XPath查詢自身的特點(diǎn)，我們將用戶輸入的XPath查詢Q寫成數(shù)組形式Q[m]，其中m為常數(shù)，表示查詢Q中字符的個(gè)數(shù)。查詢分析器通過QueryParser掃描分析器對(duì)用戶輸入的XPath查詢語句進(jìn)行分析，得到用戶要查詢的結(jié)點(diǎn)的DNS風(fēng)格名字，并且用數(shù)組形式存放。

查詢分析算法中用到的變量說明：

2.3 查詢處理器

查詢處理器就是將用戶輸入的XPath查詢等價(jià)分解為眾多子查詢，分別采用確定性或是非確定性查詢處理方式加以處理，最后將所得的查詢結(jié)果進(jìn)行組合，得到用戶查詢的最終結(jié)果。

2.4 缺失結(jié)點(diǎn)收集器

當(dāng)用戶要查詢的結(jié)點(diǎn)數(shù)據(jù)不在站點(diǎn)服務(wù)器中時(shí)，系統(tǒng)就根據(jù)結(jié)點(diǎn)的DNS風(fēng)格名字找到該結(jié)點(diǎn)所在源站點(diǎn)服務(wù)器的IP地址，然后向源站點(diǎn)發(fā)送子查詢收集缺失的結(jié)點(diǎn)數(shù)據(jù)，并把收集到的數(shù)據(jù)發(fā)送到查詢處理器中進(jìn)行查詢處理。

2.5 預(yù)取模型

在停車位置搜索服務(wù)系統(tǒng)中增加預(yù)取機(jī)制，雖然不減少結(jié)點(diǎn)數(shù)據(jù)的實(shí)際傳輸時(shí)間，但由于預(yù)取結(jié)點(diǎn)數(shù)據(jù)的傳輸利用了系統(tǒng)的相對(duì)空閑時(shí)間，使得結(jié)點(diǎn)數(shù)據(jù)的傳輸與查詢結(jié)果返回給用戶操作能夠并行進(jìn)行。

預(yù)取算法是預(yù)取方法的核心。預(yù)取算法需要控制兩個(gè)方面才能得到良好的效果。一方面需要控制對(duì)哪些結(jié)點(diǎn)進(jìn)行預(yù)取，另一方面需要控制預(yù)取的量，不能對(duì)網(wǎng)絡(luò)應(yīng)用產(chǎn)生較大的影響。根據(jù)停車位置搜索服務(wù)系統(tǒng)的特點(diǎn)，本文采用基于訪問歷史的預(yù)取方法，根據(jù)服務(wù)器上所有用戶的訪問歷史對(duì)未來的訪問進(jìn)行預(yù)測(cè)。

在預(yù)取代價(jià)基礎(chǔ)上，可得預(yù)取門限函數(shù)H=1-其中ρ=λs/b是系統(tǒng)的利用率，γ=αT /αB。

通過分析可知，隨著系統(tǒng)負(fù)載的增加，預(yù)取門限也相應(yīng)增大，較小量的結(jié)點(diǎn)將被預(yù)取。從門限函數(shù)H的計(jì)算公式可以看出，隨著系統(tǒng)利用率的增加，門限函數(shù)H也變大，將會(huì)使較少的結(jié)點(diǎn)數(shù)據(jù)進(jìn)入緩存，以免對(duì)網(wǎng)絡(luò)性能造成更大的影響。

3 結(jié)束語

本文在緩存技術(shù)與預(yù)取技術(shù)結(jié)合的基礎(chǔ)上，提出了一種緩存技術(shù)與預(yù)取技術(shù)相結(jié)合的體系結(jié)構(gòu)，然后對(duì)體系結(jié)構(gòu)中各個(gè)模塊的功能和實(shí)現(xiàn)算法進(jìn)行了詳細(xì)闡述，最后對(duì)算法進(jìn)行了復(fù)雜性和實(shí)例分析，有效地解決了廣域傳感器數(shù)據(jù)庫系統(tǒng)中，低頻結(jié)點(diǎn)數(shù)據(jù)進(jìn)入緩存替換出高頻結(jié)點(diǎn)數(shù)據(jù)所造成的緩存命中率低和系統(tǒng)資源浪費(fèi)問題。

參考文獻(xiàn)：

[1] Fran?oise Sailhan， Valerie Issarny.Cooperative Caching in Ad Hoc

Networks. Proceedings of the 4th International Conference on Mobile Data Management[J].London， 2003. Springer-Verlag，2013：13-28

[2] Zhimei Jiang， L. Kleinrock. Web prefetching in a mobile

environment[C]. IEEE Personal Communications，1998.5：25-34

[3] Zhimei J， Kleinrock L. Prefetching links on the WWW.In

Proceedings of the 1997 IEEE International Conference on Communications，Towards the Knowledge Millennium，Montreal [C]. Que， Canada，1997：483-489

[4] Z Jiang，L Kleinrock. An adaptive network prefetch scheme[C].

IEEE Journal on Selected Areas in Communications，1998.16（3）：358-368

[5] 金志剛，楊晉生，胡琳.基于網(wǎng)絡(luò)性能的智能預(yù)取技術(shù)[J].計(jì)算機(jī)工程，

2000.26：811-815

[6] 趙政，張鋼，楊潔，王松，舒炎泰.Web智能代理的預(yù)取技術(shù)和緩存技術(shù)[J].

天津大學(xué)學(xué)報(bào)，2009.34（5）：563-567

[7] 金志剛，張鋼，舒炎泰.基于網(wǎng)絡(luò)性能的智能Web加速技術(shù)—緩存與

預(yù)取[J].計(jì)算機(jī)研究與發(fā)展，2011.38（8）：1001-1004