廣域傳感器數據庫中的緩存技術研究

莊緒路

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

關鍵詞： 廣域傳感器； 數據庫； 緩存技術； 預取技術

中圖分類號：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 引言

廣域傳感器數據庫是當前國際上備受關注的、由多學科高度交叉的新興熱點研究領域[1]，具有十分廣闊的應用前景，在軍事國防、工農業、城市管理、生物醫療、環境監測、搶險救災、防恐反恐、危險區域遠程控制等許多領域都有重要的科研價值和巨大的實用價值，已經引起了世界許多國家軍界、工業界和學術界的高度重視，被認為是對21世紀產生巨大影響力的技術之一。

1 現有緩存技術的局限性

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

2 緩存技術與預取技術相結合

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

2.1 查詢分析器

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

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

2.3 查詢處理器

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

2.4 缺失結點收集器

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

2.5 預取模型

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

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

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

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

3 結束語

本文在緩存技術與預取技術結合的基礎上，提出了一種緩存技術與預取技術相結合的體系結構，然后對體系結構中各個模塊的功能和實現算法進行了詳細闡述，最后對算法進行了復雜性和實例分析，有效地解決了廣域傳感器數據庫系統中，低頻結點數據進入緩存替換出高頻結點數據所造成的緩存命中率低和系統資源浪費問題。

參考文獻：

[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] 金志剛，楊晉生，胡琳.基于網絡性能的智能預取技術[J].計算機工程，

2000.26：811-815

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

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

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

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