莊緒路

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

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

中圖分類號：TP393 文獻標(biāo)志碼：A 文章編號：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é)科高度交叉的新興熱點研究領(lǐng)域[1]，具有十分廣闊的應(yīng)用前景，在軍事國防、工農(nóng)業(yè)、城市管理、生物醫(yī)療、環(huán)境監(jiān)測、搶險救災(zāi)、防恐反恐、危險區(qū)域遠(yuǎn)程控制等許多領(lǐng)域都有重要的科研價值和巨大的實用價值，已經(jīng)引起了世界許多國家軍界、工業(yè)界和學(xué)術(shù)界的高度重視，被認(rèn)為是對21世紀(jì)產(chǎn)生巨大影響力的技術(shù)之一。

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

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

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

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

2.1 查詢分析器

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

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

2.3 查詢處理器

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

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

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

2.5 預(yù)取模型

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

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

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

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

3 結(jié)束語

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

參考文獻：

[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].計算機工程，

2000.26：811-815

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

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

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

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