莊緒路

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

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

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

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

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

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

為了進一步縮短用戶查詢的響應時間，可以根據(jù)服務器中用戶的訪問歷史在網(wǎng)絡帶寬可以滿足的條件下對一些結(jié)點數(shù)據(jù)進行預取[4]。因此，本文提出了一個緩存技術(shù)與預取技術(shù)相結(jié)合的體系結(jié)構(gòu)。結(jié)點數(shù)據(jù)在進入緩存之前必須經(jīng)過預取模型的判斷，把訪問頻率低于一定值的結(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風格名字，并且用數(shù)組形式存放。

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

2.3 查詢處理器

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

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

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

2.5 預取模型

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

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

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

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

3 結(jié)束語

本文在緩存技術(shù)與預取技術(shù)結(jié)合的基礎上，提出了一種緩存技術(shù)與預取技術(shù)相結(jié)合的體系結(jié)構(gòu)，然后對體系結(jié)構(gòu)中各個模塊的功能和實現(xiàn)算法進行了詳細闡述，最后對算法進行了復雜性和實例分析，有效地解決了廣域傳感器數(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)絡性能的智能預取技術(shù)[J].計算機工程，

2000.26：811-815

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

天津大學學報，2009.34（5）：563-567

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

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