淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0201201209331800
中文論文名稱 行動隨意網路中合作快取之研究
英文論文名稱 Research on Cooperative Cache in Mobile Ad-hoc Networks
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士班
系所名稱(英) Department of Electrical Engineering
學年度 100
學期 1
出版年 101
研究生中文姓名 陳昱佑
研究生英文姓名 Yu-Yiu Cheng
學號 698450409
學位類別 碩士
語文別 中文
口試日期 2011-12-16
論文頁數 70頁
口試委員 指導教授-莊博任
委員-陳省隆
委員-吳庭育
中文關鍵字 行動隨意網路  快取 
英文關鍵字 MANET  cooperative cache 
學科別分類 學科別應用科學電機及電子
中文摘要 無線隨意網路中,傳遞資料的內容主要分為兩大類,一種是在伺服器更新的資料,譬如天氣預報、新聞、車況、股票等等的情況,這些資料有些特性,就是普遍具有高度的熱門性,又依更新程度可以分為兩種,一種是如天氣預報以及新聞,這種熱門程度高更新情況低,一種如股票,更新較頻繁。另一類是經由伺服端認證的用戶端可以修改的資料,例如facebook等,由用戶端上傳資料給伺服器,這類的資料就不一定屬於熱門或是冷門的資料。
基於2004年Yin等學者提出快取路徑與快取檔案機制, 2010年由Zhao等學者提出每次Query都必須向伺服器做認證,做出需向伺服器認證的快取檔案機制,另外2007年的GroupCache是讓每個節點能夠周期性廣播快取路徑封包,不過跟Zhao’s Method不一樣的是GroupCache會直接回傳檔案給需求的節點,因此正確性不夠,如果資料更新率增高,效能也會降低得很快。
我們的方法區域性維護之合作快取機制(Regional Maintained Cooperative Cache ; RMCC),擷取了Zhao’s Method裡強調的檔案正確性,以及GroupCache的概念,利用經伺服器確認過的回傳封包當作觸發,將快取路徑插入歡迎訊息廣播,鄰居節點收到訊息後,會紀錄發送歡迎訊息節點擁有該筆資料這條路徑,當有需要時可以經由快取路徑向鄰居節點取得。
RMCC與對比的方法相比,在命中率的部分,RMCC因為快取路徑的命中量增加,而有最好的效能,在傳輸總量的部分,,GroupCache因為命中失誤要付出的成本以及維護成本都較高所以封包量也比較多,RMCC因為維護成本比GroupCache低,且快取失誤付出的代價較小,因此整個模擬中封包總量,RMCC是優於其他方法的。
經由以上的研究模擬,無線網路快取由有相同目的的一群人群聚在一起(軍方野外進行作戰或是觀光名勝地區分享旅遊導覽),因此如果這些節點可以各自提供一塊可以互相分享的平台,對於節點電量、頻寬的利用上都能有更好的效率,尤其是鄰近伺服器的節點封包碰撞的機率也是最高,藉由我們的方法可以減低伺服器的負擔平衡整個網路的負載,更可以提高節點的續航力,對於使用者可以提供更好的無線網路的品質。
英文摘要 Some recent studies have shown that cooperative cache can improve the system performance in ad hoc networks , mesh networks, and sensor networks. In this paper, In the mobile ad hoc network, a node can communicate with others anywhere and anytime. Cooperative caching scheme can improve the accessibility of data objects. However, the cache hit ratio is reduced and access latency becomes longer significantly due to the mobility of nodes, energy consumption in battery, and limited wireless bandwidth.
In this paper, we propose a novel cooperative caching scheme called Regional Maintained Cooperative Cache (RMCC) which allows each Node and its 1-hop neighbors form a group. The caching status is exchanged and maintained when any Node received a data reply message. For a data miss in the CacheData space, each Node searches the data in its CachePath table before forwarding the request to the next node that lies along routing path towards server.
We evaluate the performance of the RMCC by using NS2 and compare it with the existing schemes such as SimpleCache , GroupCache and Zhao’s method. Simulation experiments show that the RMCC caching mechanism achieves significant improvements in cache hit ratio and average query latency in comparison with other caching strategies.
論文目次 1. 第一章 緒論 1
1.1 快取環境介紹 1
1.2 快取分類 1
1.3 伺服端/用戶端架構 3
1.4 單跳合作快取 4
1.5 多跳合作快取 4
1.6 研究動機 5
2. 第二章 相關工作 7
2.1 內容分發網路與無線網路快取 8
2.1.1 內容分發網路 8
2.1.2 無線網路快取與內容分佈網路的探討 11
2.2 快取演進歷程 12
2.2.1 快取檔案(CacheData) 12
2.2.2 快取路徑(CachePath) 13
2.2.3 混合式快取(HybridCache) 13
2.3 多跳無線網路快取 14
2.4 COACS 19
2.4.1 網路的建立及更新 19
2.4.2 QD list維護 20
2.4.3 修復、刪除節點 20
2.4.4 資料探索流程 20
2.5 AODV路由協定 21
2.6 GroupCache 22
2.6.1 蒐集資料流程 22
2.6.2 資料探索流程 23
2.7 Zhao’s method 23
2.7.1 快取層的建立 24
2.7.2 蒐集資料流程 27
2.7.3 資料探索流程 28
3. 第三章 區域性維護之合作快取機制 30
3.1 新方法大綱 30
3.2 節點模型及舉例 30
3.2.1 節點模型 30
3.2.2 節點間合作快取的例子 31
3.3 詳細過程 36
3.3.1 資料蒐集流程 36
3.3.2 探索資料流程 41
3.4 新架構帶來的好處 43
4. 第四章 模擬結果 46
4.1 用戶端模型 46
4.2 伺服端模型 47
4.3 模擬參數 47
4.4 比較方法 48
4.5 比較參數 49
4.6 模擬結果 49
5. 第五章 結論 64
6. 第六章 參考文獻 67

圖目錄
圖1. 1快取無效的設計理念之分類方式 3

圖 2. 1簡單的無線網路快取模型 12
圖 2. 3 混合式無線網路快取架構 14
圖 2. 4 對稱式無線網路快取架構 16
圖 2. 5 非對稱式無線網路快取架構 17
圖 2. 6 非對稱式無線網路快取實例 19
圖 2. 7 快取層(一) 24
圖 2. 8快取層(二) 25
圖 2. 9快取層(三) 25
圖 2. 10快取層(四) 26
圖 2. 11快取層(五) 26
圖 2. 12快取層(六) 27
圖 2. 13 無線網路快取細部實作方式(一) 28
圖 2. 14無線網路快取細部實作方式(二) 28
圖 2. 15無線網路快取細部實作方式(三) 29

圖3. 1 新方法實例(一) 32
圖3. 2新方法實例(二) 33
圖3. 3新方法實例(三) 34
圖3. 4新方法實例(四) 35
圖3. 5 資料收集流程 38
圖3. 6 資料蒐集演算法 39
圖3. 7接收歡迎訊息流程 40
圖3. 8 接收歡迎訊息演算法 41
圖3. 9 探索資料流程 42
圖3. 10探索資料演算法 43

圖 4. 1 命中率 51
圖 4. 2 失誤率 52
圖 4. 3 快取率 54
圖 4. 4 快取正確率 56
圖 4. 5 CBR傳輸總量 57
圖 4. 6 控制封包總量 59
圖 4. 7 命中率vs. 快取空間 60

表目錄
表3.1快取機制差異點列表 44

表4. 1 模擬參數 48
表4. 2 檔案存取延時 61
參考文獻 [1] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker ,” Web caching and Zipf-like distributions: Evidence and implications”, IEEE Proceedings INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies , vol.1, Mar. 1999, PP. 126 – 134.
[2] Yan Chen, Lili Qiu, Weiyu Chen, Nguyen Luan and R. H. Katz, “Clustering Web content for efficient replication”, 10th IEEE International Conference on Network Protocols, 2002 Nov. 2002 , PP. 165 – 174.

[3] Liangzhong Yin and Guohong Cao, “Supporting cooperative caching in ad hoc networks”, Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies , Vol. 4, Jan. 2004, PP. 2537 – 2547.

[4] Ihn-Han Bae and S. Olariu, ”Design and Evaluation of a Fuzzy Cooperative Caching Scheme for MANETs”, 2010 6th International Conference on Wireless Communications Networking and Mobile Computing , Sep. 2010, PP. 1 – 5.

[5] H. Artail, H. Safa and S. Pierre ,“Database caching in MANETs based on separation of queries and responses”, IEEE International Conference on Wireless And Mobile Computing, Networking And Communications, 2005, Vol.3, Aug. 2005, PP. 237 – 244.

[6] Jing Zhao, Ping Zhang, Guohong Cao and C.R. Das ,“Cooperative Caching in Wireless P2P Networks : Design, Implementation, and Evaluation”, IEEE Transactions on Parallel and Distributed Systems, Vol. 21, Issue 2, PP. 229-241, Feb. 2010.

[7] Yi-Wei Ting and Yeim-Kuan Chang , “A Novel Cooperative Caching Scheme for Wireless Ad Hoc Networks: GroupCaching”, International Conference on Networking, Architecture, and Storage, 2007. July 2007, PP. 62-68.

[8] H. Artail, H. Safa, K. Mershad, Z. Abou-Atme and N. Sulieman , “COACS: A Cooperative and Adaptive Caching System for MANETs” , IEEE Transactions on Mobile Computing, Vol. 7, Issue: 8, PP. 961-977, Aug. 2008.

[9] Chi-Yin Chow, Hong Va Leong and A. Chan, “Peer-to-peer cooperative caching in a hybrid data delivery environment ”, 7th International Symposium on Parallel Architectures, Algorithms and Networks, 2004. May. 2004, PP. 79-84.

[10] Jun Tian and M.K. Denko ,“Exploiting Clustering and Cross-Layer Design Approaches for Data Caching in MANETs”, Third IEEE International Conference on Wireless and Mobile Computing, Networking andCommunications, 2007, Oct. 2007, PP. 52-52.

[11] Gaogang Xe, Zhenyu Li, Jianing Chen, Yifen Wei,V. Issarny and A. Conte, “DTCS: A Dynamic Tree-Based Consistency Scheme ofCooperative Caching in Mobile Ad Hoc Networks” , Third IEEE International Conference on Wireless and Mobile Computing, Networking andCommunications, 2007, Oct. 2007, PP. 48

[12] Jianyong Sun, Wanjin Xu and Xiaolin Chen ,”A Scheme of Cooperative Cache Placement in MANETs”, 2010 International Conference on Internet Technology and Applications, Aug. 2010, PP. 1-4.

[13] M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A review of routing protocols for mobile ad hoc networks”,journals of Elsevier Ad Hoc Networks , vol. 2, no. 1, pp. 1-22, Jan. 2004.

[14] C. E. Perkins and E. M. Royer, “Ad hoc On-Demand Distance Vector Routing”, 2nd IEEE Workshop on Mobile Computing Systems and Applications , Feb.1999, PP. 90-100.

[15] NS2, http://www.isi.edu/nsnam/ns/

[16] Han Ke ,“Cooperative caching algorithm based on grouping nodes in mobile ad hoc networks”, IEEE International Conference on Information and Automation, 2010 , June 2010 PP. 1294-1298.

[17] Thu Nguyen Tran Minh and Thuy Dong Thi Bich, “An Efficient Model for Cooperative Caching in Mobile Information Systems”, 2011 International Conference on Advanced Information Networking and Applications, Mar. 2011, PP. 90 – 95.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-01-03公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-01-03起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信