1 引言

隨著 IT 產業的兩大領域Internet和移動通信的飛速發展，連接這兩大領域，即

利用移動終端實現隨時隨地訪問Internet具有了更加廣闊的應用前景。為了將Intenret的接入從固定的終端延伸到移動領域，WAP技術規范應運而生^[1-2]。近年

來，隨著WAP技術的日漸成熟和無線網絡的飛速發展，WAP將移動網絡和Intern

et以及公司的局域網緊密地聯系起來，通過這種技術，無論何時何地，都可以

打開WAP終端，享受無窮無盡的網上資源和網上信息。

在3G網絡高速推廣和發展的今天，隨著文本信息和音頻，視頻、動畫等大容量

信息資源爆炸性的呈現，使得網絡信息的增長速度要遠遠超過存儲空間和網絡

速度的增長^[3-5]，移動終端用戶對于速度的需求越來越高，如何提高網絡帶寬

使用的效率?如何提供穩定高效的服務?如何確保網絡服務質量(QoS)?在WEB應

用中，作為網絡加速器的Web緩存技術已經被實踐證明是解決以上問題的一個

有效的途徑^[6-7]，其優勢在于：減少網絡帶寬的使用；減少用戶的延遲；減少

需要訪問網站的負載；提供更加穩定的服務。

在日益膨脹的海量WAP信息的環境中，面對人為產生動態的、不可預測的訪問

請求，如何使得WAP緩存更好的發揮功效，關鍵在于評估WAP對象可能再次

被訪問的概率。由于WAP網絡資源和WEB網絡資源在本質上的一致性^[8]，同時

考慮到WAP應用又不是完全等同于WEB應用，論文分析了WAP圖片資源的特

點，提出了取回代價的概念，對傳統的WEB緩存替換算法進行了改進，提出了

一種基于取回代價的LFU圖片緩存算法；在應用算法到WAP瀏覽器時，采取了

瀏覽器退出緩存圖片即銷毀的策略，保證了緩存內容與服務器同步的同時，改

善了瀏覽器的整體性能。

2 WEB緩存技術

WEB網絡緩存系統^[3]的主要思想就是將WEB對象，如頁面、圖像及其它Internet

內容，進行本地存儲，使得這些被訪問過的WEB對象更靠近需要使用它們的用

戶，從而大大提高用戶WEB訪問的速度。

Web緩存的核心是緩存內容的替換算法．緩存替換是指當緩存已滿時，用新對

象替換舊對象的過程．緩存可以實施在服務器、網絡或客戶端。替換策略以最

小化損耗（失誤率、字節失誤率、平均延時和總體損耗）為標準，目前主要的

策略有：

OPT（Optimal Replacement）最佳替換算法：從過去歷史及未來行為考量，將未

來最不可能被用到的緩存對象取代，很不幸，過去的歷史可以追蹤記錄，但是

未來行為是不可能完全預測成功的，因此最佳替換法是不可能被實現的。

LRU（Least Recently Used）最近最少使用算法：其基本思想是把最近一次訪問

間隔時間最長的對象從緩存中清除出去，其優點是具有較好的時間復雜性并且

易于實現，但沒有考慮到訪問頻率等其他因素，是Web緩存最常使用的一種算法。

LFU（Least Frequently Used）最少使用頻率算法：其基本思想是最近被引用次

數最多的對象就越可能被再次引用，而系統只替換那些引用次數最少的對象。

該算法一般使用以引用次數的大小順序鏈接排列的列表。每個對象均有一個計

數器（Conuter）與之對應，起始值為0，當某個對象被引用時，計數器便被加

1，當需要替換時，系統選用計數器值最小的對象作替換。

例如：設定緩存集大小為4,訪問串為：4，5，2，3，6，2，5，3，4，2，6，

4，6，7，5，3，6，7，2，3。在LFU控制下緩存駐留集的變化如表1所示^[9]。

表1 LFU控制下緩存駐留集的變化情況

3 基于取回代價的LFU算法

3.1 取回代價

用戶使用瀏覽器訪問WAP資源時，請求對象的取回取決于服務端響應的速度、網絡帶寬的限制、索取對象的大小以及瀏覽器本身的處理速度等因素，由此引入取回代價的定義。即：

  (1)

其中，對應于對象i， 為服務端響應速度； 為網絡帶寬； 為索取對象的大��； 為其他影響因素。對于同一個瀏覽器而言，其本身的處理速度對于任意對象i( )都是相同的，因此 的大小主要是由,和來決定。在請求對象的緩存替換算法中，優先保存取回代價大的對象。

3.2 算法設計思路

一般來說，一個曾經多次被訪問過的對象將來被再次訪問的可能性通常要高于

那些過去很少被訪問的對象。正是基于這種認識，LFU以對象的使用次數作為

緩沖區清理的依據，一些使用次數較低的對象將優先從緩沖區中被清除。

WAP瀏覽器基于隨時隨地得到最新消息應運而生，避開了客戶端緩存獲取的有

可能是過時的內容^[3]這個缺陷，WAP瀏覽器暫不對請求文本內容作緩存，而是

對WAP資源中一類特定的資源——圖片資源作緩存處理。由于此類資源（如網

站Logo，導航條圖片等等）具有用戶請求頻繁、服務端更新速度遠沒有文本內

容更新快、取回代價大等特點，所以考慮對此類資源作緩存處理。同時在瀏覽

器退出時，緩存內容自動銷毀，這樣既保證了用戶在瀏覽WAP資源時對圖片信

息的二次或多次請求能夠瞬間獲取，也保證了用戶在下次瀏覽過程中取回的是

服務端最新的圖片信息。

本文提出的基于取回代價的LFU算法，其基本思想是區分具有不同取回代價和

訪問次數的圖片對象，將其存放在緩存空間中進行管理。算法綜合考慮取回代

價、訪問次數作為緩存替換的依據，并且緩存空間采用哈希結構存儲緩存對

象，由此降低算法計算復雜性，使得算法具有低開銷、高性能的特點。算法的核心思想是當緩存已滿時，依據緩存空間中對象再次被訪問的權重 ，選擇權重最小的對象 進行替換，即：

  (2)

其中 , ,, , 均為調節參數， 為對象i的被訪問次數，U為給定的緩存對象集。式(2)的最優解即為被替換的對象。

3.3 哈希存儲

論文中圖片對象的緩存結構采用哈希存儲，Key為所請求圖片對象的URL，Value存儲URL映射的圖片資源及其被訪問的次數，具體的請求對象訪問和替換哈�？臻g的過程如圖1所示。

 圖1 哈希緩存空間圖片請求流程圖

3.4 算法參數的確定

3.4.1 取回代價參數的確定

從瀏覽器自身的角度，其處理速度對于每一個取回對象都是相同的，為常量級的影響，可以忽略不計；從時間局限性的角度^[10-11]，在瀏覽器訪問過程中，服務器的響應速度和網絡帶寬的

限制在固定的 時間內可以粗略的看作是固定不變的，其中 是當前時間和對象上次被訪問的時間間隔，因此上述取回代價演變為索取對象大小的單變量函數，即 ，其中為影響因子，在 時間內可以取值為 。

3.4.2 替換對象權重 參數的確定

通過上述分析，考慮取回代價和訪問次數的權重可表示為：

  (3)

其中,為調節參數。由此，在WAP瀏覽器中，基于取回代價的LFU圖片替換算法就演變為尋找式(3)的最優解，該最優解即為被替換的對象。

文獻[12]指出即使在離線情況下Web緩存求最優解也是一個NP完全問題，又由

于WAP網絡資源和WEB網絡資源在本質上的一致性，因此WAP緩存求最優解

也是一個NP完全問題,通常算法都是尋找次優解。

在互聯網領域，大量的特征研究顯示，訪問請求頻繁的那些對象，它們的流行

度符合power-law關系的Zipf's law或Zipf-like分布^[13]（即對于內容的訪問遵循

80/20原則，也就是20%的內容，會占有80%的訪問量），這是一個定性的原

則。定量來說，內容訪問近似符合Zipf定律(Zipf's law)。因此在確定調節參數方

面，論文將應用Zipf規律于圖片緩存替換算法中，同時根據不同分類網絡的訪

問歷史來訓練調整算法參數，以期達到較為理想的緩存效果。

4 實驗與分析

論文在利用J2ME^[14]實現的WAP瀏覽器的基礎上，成功運用圖片緩存算法到

WAP瀏覽器中：通過運用不同的移動終端，對特定網站多個網絡資源和對各大

流行WAP門戶網站進行訪問測試，對以下三種情況：不顯示圖片(nodisplay)、顯示

但不緩存圖片(nocache)、顯示且緩存圖片（dispcache），作了瀏覽器端服務響應速

度的對比。

4.1 對特定網站多個網絡資源的的測試

論文特定網站選用http://m.139.com，分別運用Nokia5320和SE W810c兩部移動終

端，測試了該網站中包含不同圖片數量的各頁面的請求響應時間，圖片數量與

以上各情況下頁面請求響應時間的關系曲線如圖2所示。

圖2 圖片數量和響應時間關系曲線(左nokia5320 右se_w810c)

4.2 對各大流行WAP門戶網站的測試

論文選用3g.qq.com, sina.cn, wap.sohu.com, wap.monternet.com, kong.net以及空中網

娛樂頻道（圖片數量比較多）等幾個網站作了同4.1相同的測試。其關系曲線

如圖3所示。

圖3 圖片數量和響應時間關系曲線(左nokia5320 右se_w810c)

4.3 實驗結果分析

分析關系圖2-3可以看出：隨著圖片數量的增加，在瀏覽器端，使用圖片緩存

算法的速度響應曲線較之沒有使用算法的曲線平穩很多，即運用圖片緩存算法

的瀏覽器響應速度受圖片數量的影響較小。同時通過實驗發現：運用該算法后

的瀏覽器響應速度變快、用戶請求延遲變小、服務更穩定，網絡請求更平穩。

5 結論

論文根據WAP瀏覽器自身及其應用的特點，避開了傳統的LFU的一些缺陷，對

其作了改進，提出了基于取回代價的LFU圖片緩存算法，使得圖片對象請求時

在緩存中的命中率更高；對緩存空間采用哈希結構存儲，降低了算法復雜度；

在應用緩存算法到瀏覽器時，采取了瀏覽器退出緩存內容即銷毀的策略，保證

了緩存內容與服務器同步的同時，改善了其整體性能，實驗表明運用該算法的

瀏覽器更趨向于用戶的滿意度需求，即響應速度更快、請求延遲更小、服務更

穩定、網絡請求更平穩。

同時論文提出的基于取回代價的LFU圖片緩存算法，最終運用到實際中的模型

作了一些特定條件下的忽略和簡化，各個調節參數是根據歷史數據和科學經驗

確定，因此論文算法還有一定的改進空間。

參考文獻 (References)

[1] Xylomerios G, Polyzos C. Iternet Protocol Performancevover Networks With Wireless Link IEEE network 1999, (5)

[2] Jiang Jie, Fang Li. The Technique and The Application of WAP. Mobile Communication. 2001,(9).

[3] He Chen, Chen Zhao-xiong，He—yan H. Summary of web caching technology. Mini—Micro Systems, 2004,25(5):836—842.

[4] Balamash A. Kruaz M. An overview of web caching replacement algorithms. IEEE Communications Surveys and Tutorials. 2004,6(2);44-66．

[5] Podlipnig S，Boszormenyi L．A survey of web cache replacement Strategies．ACM Computing Surveys．2003，35(4)；374-398．

[6] Barish G，Obraczka K．World wide web caching ; trends and techniques．IEEE Communications Magazine，2000，38(5):178-185.

[7] Aggarwal C-Wolf J L,Yu P S. Caching on the world wide Web. IEEE Transactions on Knowledge and Data Engineering，1999.11(1):94-107.

[8] Wang Jun-ming. WAP Technology—The Gate of Mobile Mulmedia. Mobile Communication. 2001,(9)

[9] Yang Hui. The Research and Implemention Of The algorithm about LFU. Computer Era. 2004(2):28-29

[10] Lin Yong-wang．Zhang Da-jiang．Hua-lin Q．A novel replacement algorithm for web caching. Journal of Software. 2001, 12 (011):1710—1715．

[11] Busari M，Williamson C. ProWGen：a synthetic workload generation tool for simulation evaluation of web proxy caches. Computer Networks．2002, 38(6):779—794．

[12] Hosseini-Khayat S．On optimal replacement of nonuniform cache objects. IEEE Transactions on Computers，2000，49(8):769—778.

[13] Breslau L, Cao P, Fan L, et a1. Web caching and Zipf—like distributions：evidence and implications. In Proceedings IEEE Infocom．1999.

[14] Du Rui. The Research and Application of J2ME Network Program. Computer KnowledgeAnd Technology. 2008(4):111-112,116

作者簡介：

陳慧光，男，1985年生，山西臨汾人，北京工業大學計算機學院碩士研究生,主要研究領域為無線通信網絡；

肖創柏，男，1962年生，研究員(教授), 博士研究生導師。

09100