在無線網路的環境中，大致上可分為伺服器(Server)、及用戶端(Mobile Client)。伺服器的資料庫有全部資料，而用戶端的快取僅儲存部份資料。當用戶端要求資料時，用戶端上傳要求的訊息給伺服器，伺服器收到後將被要求的資料回傳給用戶端。為了要減少頻寬及能源的浪費，於是在用戶端建立快取，便成了普遍的解決方法。然而快取與資料庫間必須達到同步，才不致於誤用過期的資料。故如何讓用戶端快取資料與伺服器資料保持一致性，即為本論文的研究重點。
    本論文提出了兩個方法，一個是先將資料分類之後，給與熱門資料較短廣播週期，冷門資料較長廣播週期的ABI+HCQU(Adaptive Broadcast Interval + Hot/ Cold/ Query/ Update)；另一個則是用低功率向鄰近節點要求自己快取內沒有或無效的資料，並採用電腦內快取資料的同步方式MESI修改成適合Client-Server環境的同步方式，此方法即為SWRCC+MUVI(SleepWakeup/ Recovery/ Check/ Confirm + Modified/ Uncertain/ Valid/ Invalid)。
    模擬結果顯示出ABI+HCQU的平均存取時間及快取失誤比率，皆能達到不錯的效能。而SWRCC+MUVI透過向鄰近節點取得快取失誤資料的方式，成功的減少頻寬消耗量，而且其所消耗的頻寬也相當少。另外，本論文也將提出的方法應用在XML資料庫之上，同樣也獲得相當不錯的成效，因此也驗證了本論文所提出方法之實用性。

Cache invalidation is an effective approach to maintain data consistency between the server and mobile clients in a mobile environment. This paper presents two new cache invalidation schemes, ABI+HCQU and SWRCC+MUVI, which are designed according to the real situations in a mobile environment, like MANET. ABI+HCQU divides data into different groups based on their utilization ratios (Hot/ Cold/ Query/ Update) and adapts their broadcasting intervals (ABI) accordingly to suit the actual needs. 
    SWRCC+MUVI (SleepWakeup/ Recovery/ Check/ Confirm + Modified/ Uncertain/ Valid/ Invalid) aims to solve the validity problem of cached data after a client is disconnected from the server. The two schemes are shown through experimental evaluation and performance analyses to outperform most existing schemes in terms of data access time, cache miss ratios, query uplink ratios and bandwidth consumption. We also implement our two schemes – with slight modifications – on the XML database and prove that both schemes can achieve the same goal (as TS) with more favorable results. This further confirms that our cache invalidation schemes are not only theoretically but practically feasible.

誌謝	I
中文摘要	II
英文摘要	III
目錄	V
圖目錄	IX
表目錄	XIII
第一章 緒論	1
第二章 相關研究及背景說明	6
2.1 背景說明	6
2.2 現有的快取無效策略	9
2.2.1 TS 快取無效策略	9
2.2.2 IAVI快取無效策略	12
2.2.3 BS快取無效策略	13
2.2.4 UIR快取無效策略	16
2.2.5 CONT快取無效策略	18
2.2.6 RIH快取無效策略	22
2.2.7 AEECIS快取無效策略	25
第三章 新方法之研發	30
3.1 研究動機與目的	30
3.2 依熱門程度將資料分類的方式(HCQU)	31
3.3 動態調整廣播週期的快取無效方式(ABI)	33
3.4 ABI+HCQU	38
3.5 基於主動式斷線及被動式斷線的快取無效機制(SWRCC)	42
3.5.1 主動式斷線之處理方式(SWR)	43
3.5.2 被動式斷線的處理方式(CC)	45
3.6 斷線後的用戶端之快取同步機制(MUVI)	49
3.7 SWRCC+MUVI	56
3.8 設計準則總整理	58
第四章 模擬結果與效能評估	59
4.1 模擬環境及模擬方法	59
4.2 模擬結果	62
4.2.1 平均存取時間	65
4.2.2 快取失誤比率	66
4.2.3 要求上傳比率	68
4.2.4 頻寬消耗	70
4.2.5 主動式與被動式斷線的比率	74
4.2.6 廣播的無效驗證報告之大小	75
4.3 效能評估	75
4.3.1 IR廣播的資料量	76
4.3.2 平均存取時間	86
4.3.3 頻寬消耗	95
4.3.4 有斷線的效能分析探討	98
第五章 XML資料庫與快取無效策略之結合	101
5.1 XML之背景說明	102
5.1.1 XML之簡介	103
5.1.2 XML的更新指令介紹	120
5.1.3 基於XML的TS及XIR快取無效策略	126
5.2 應用ABI+HCQU及SWRCC+MUVI在XML資料庫的方式	128
5.2.1 應用ABI+HCQU在XML資料庫的方式	128
5.2.2 應用SWRCC+MUVI在XML資料庫的方式	131
5.3 基於XML資料庫之快取無效策略的模擬環境及基準測試程式	134
5.3.1 模擬環境	134
5.3.2 基準測試程式	137
5.4 基於XML資料庫之快取無效策略之模擬結果	138
5.4.1 平均存取時間	139
5.4.2 快取命中比率	142
5.4.3 要求上傳比率	145
第六章 結論	148
第七章 參考文獻	151
Publications List	153

圖目錄
圖1. 1：無線通訊之環境架構圖	2
圖2. 1：快取無效策略的設計理念之分類方式	6
圖2. 2：TS快取無效策略之運作示意圖	11
圖2. 3：BS之位元序列實例	15
圖2. 4：UIR快取無效策略之示意圖	18
圖2. 5：CONT快取無效策略之示意圖	19
圖2. 6：減少回應要求的延遲時間之概念圖	23
圖2. 7：RR的架構圖	24
圖2. 8：UR的架構圖	24
圖2. 9：建構RRi,k的方式	24
圖2. 10：建構URi,k的方式	24
圖3. 1：HCQU之實例	32
圖3. 2：ABI的運作方式	34
圖3. 3：熱門資料之門檻值設定探討	36
圖3. 4：冷門資料之門檻值設定探討	37
圖3. 5：SWRCC處理斷線的過程圖	44
圖3. 6：被動式斷線的處理連續過程	48
圖3. 7：快取內的MUVI狀態轉換圖	52
圖4. 1：模擬架構圖	61
圖4. 2：各個方法在不同斷線機率下之平均存取時間	64
圖4. 3：各個方法在不同斷線時間下之平均存取時間	64
圖4. 4：各個方法在不同斷線機率下之快取失誤比率	66
圖4. 5：各個方法在不同斷線時間下之快取失誤比率	66
圖4. 6：各個方法在不同斷線機率下之要求上傳比率	68
圖4. 7：各個方法在不同斷線時間下之要求上傳比率	68
圖4. 8：各個方法在不同斷線機率下之頻寬消耗	71
圖4. 9：各個方法在不同斷線時間下之頻寬消耗	71
圖4. 10：各個方法在不同資料庫大小下之頻寬消耗	73
圖4. 11：各個方法在不同快取大小下之頻寬消耗	73
圖4. 12：主動式斷線情況下之SWRCC+MUVI快取失誤比率	74
圖4. 13：主動式斷線情況下之TS(SWR)快取失誤比率	74
圖4. 14：各個不同方法的模擬數據及數學分析之IR廣播的資料量	85
圖4. 15：平均存取時間之數學分析與模擬比較	93
圖4. 16：各個方法之頻寬消耗的模擬及數學分析的結果比較圖	97
圖5. 1：XML文件之實例	104
圖5. 2：建構XML資料樹之實例	107
圖5. 3：已建構完成之XML資料樹的實例	117
圖5. 4：前序編碼(PSN)之實例	118
圖5. 5：XML資料庫之實例	119
圖5. 6：樹狀架構之實例(初始狀態)	121
圖5. 7：執行Rename(ptr，a3)指令之後的結果	121
圖5. 8：執行Replace(ptr，data1)指令之後的結果	122
圖5. 9：執行Insert(ptr，b3，data2)指令之後的結果	122
圖5. 10：執行Delete(ptr)指令之後的結果	123
圖5. 11：用戶端更新伺服器內Database的例子	124
圖5. 12：被影響區域(IA)之實例	126
圖5. 13：在不同OFFSET之下的要求與更新樣式比較圖	136
圖5. 14：第i個節點的要求到達時間的產生模式	136
圖5. 15：各個方法在不同OFFSET下的平均存取時間	139
圖5. 16：各個方法在不同快取大小下的平均存取時間	140
圖5. 17：各個方法在不同斷線機率下的平均存取時間	141
圖5. 18：各個方法在不同斷線時間下的平均存取時間	141
圖5. 19：各個方法在不同OFFSET下的快取命中比率	142
圖5. 20：各個方法在不同快取大小下的快取命中比率	143
圖5. 21：各個方法在不同斷線機率下的快取命中比率	144
圖5. 22：各個方法在不同斷線時間下的快取命中比率	144
圖5. 23：各個方法在不同OFFSET下的要求上傳比率	145
圖5. 24：各個方法在不同快取大小下的要求上傳比率	145
圖5. 25：各個方法在不同斷線機率下的要求上傳比率	147
圖5. 26：各個方法在不同斷線時間下的要求上傳比率	147

表目錄
表3. 1：設計準則總整理	58
表4. 1：效能評估參數設定	77
表4. 2：IR廣播資料量的效能分析	84
表4. 3：效能分析之參數設定	86
表4. 4：平均存取時間(AAT)之效能分析	94
表4. 5：頻寬消耗之數學分析結果	96

[1]	N. Chand, R.C. Joshi, and M. Misra, “Energy Efficient Cache Invalidation in Wireless Mobile Environment,” Proc. 2005 IEEE Int’l Conf. on Personal Wireless Communications, Jan. 2005, pp. 244-248.
[2]	A. Madhukar and R. Alhajj, “An Adaptive Energy Efficient Cache Invalidation Scheme for Mobile Databases,” Proc. 2006 ACM Symp. on Applied Computing, Apr. 2006, pp. 1122-1126.
[3]	D. Barbara and T. Imielinski, “Sleepers and Workaholics: Caching Strategies in Mobile Environments, ” Proc. 1994 ACM Int’l Conf. on Management of Data, vol. 23, no. 2, pp. 1-12, May 1994.
[4]	J. Jing, A. Elmagarmid, A. Heal, and R. Alonso, “Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments, ” Mobile Networks and Applications, vol. 2, no. 2, pp. 115-127, Oct. 1997.
[5]	J. C.H. Yuen, E. Chan, K.Y. Lam, and H.W. Leung, “An Adaptive AVI-based Cache Invalidation Scheme for Mobile Computing Systems,” Proc. 2000 Int’l Workshop on Mobility in Databases and Distributed Systems, Sept. 2000, pp. 155-159.
[6]	G. Cao, “A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments,” IEEE Trans. on Knowledge and Data Engineering, vol. 15, no. 5, pp. 1251-1265, Sept./Oct. 2003.
[7]	C.C. Wu, J.F. Fang, and P.C. Hung, “A Counter-Based Cache Invalidation Scheme for Mobile Environments with Stateless Servers,” Proc. 2003 IEEE Pacific Rim Conf. On Communications, Computers and Signal Processing, Aug. 2003, pp. 623-626.
[8]	Y. Bao, R. Alhajj, and K. Barker, “Hybrid Cache Invalidation Schemes in Mobile Environments,” Proc. 2005 IEEE Int’l Conf. on Pervasive Services, July 2004, pp. 209-218.
[9]	Q. Hu and D. L. Lee, “Adaptive Cache Invalidation Methods in Mobile Environments,” Proc. 1997 IEEE 6th Int’l Conf. on High Performance Distributed Computing, Aug. 1997, pp. 264-273.
[10]	Y. K. Chang, M. H. Hong, and Y. W. Ting, “Web-based Energy-efficient Cache Invalidation in Wireless Mobile Environment,” Proc. 2005 IEEE 19th Int’l Conf. on Advanced Information Networking and Applications, Mar. 2005, pp. 519-524.
[11]	H. Shen, M. Kumar, S. K. Das, and Z. Wang, “Energy-Efficient Caching and Prefetching with Data Consistency in Mobile Distributed Systems,” Proc. 2004 Int’l Conf. on Parallel and Distributed Processing Symposium, Apr. 2004, pp. 67-76.
[12]	A. Elmagarmid, J. Jing, A. (Sumi) Helal, and C. Lee, “Scalable Cache Invalidation Algorithms for Mobile Data Access,” IEEE Trans. on Knowledge and Data Engineering, vol.15, no.6, pp.1498–1511, Nov./Dec. 2003.
[13]	H. Lee, J. Suh, and S. Jung, “An Efficient Cache Invalidation Method in Mobile Client/Server Environment,” IEICE Transactions on Information and Systems E90-D, no.10, pp. 1672-1677, Oct. 2007.
[14]	N. Chand, R. Joshi, and M. Misra, “Efficient Cache Invalidation in Mobile Environment,” Proc. of IEEE INDICON, Dec. 2004, pp. 107-112.
[15]	M. K. H. Yeung and Y. K. Kwok, “Wireless Cache Invalidation Schemes with Link Adaptation and Downlink Traffic,” IEEE Trans. on Mobile Computing, vol.4, no.1, pp. 68-83, Jan.-Mar. 2005.
[16]	A. Kahol, S. Khurana, S. K. S. Gupta, and P. K. Srimani, “A Strategy to Manage Cache Consistency in a Disconnected Distributed Environment”, IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 7, pp. 686-700, July 2001.
[17]	M. K. H. Yeung and Y. K. Kwok, “New Invalidation Algorithms for Wireless Data Caching with Downlink Traffic and Link Adaptation,” Proc. of the 2004 IPDPS Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, Apr. 2004, pp. 222-229.
[18]	G. Cao, “Proactive Power-Aware Cache Management for Mobile Computing Systems,” IEEE Transactions on Computers, vol. 51, no. 6, pp. 608-621, June 2002.
[19]	G. Cao, “On Improving the Performance of Cache Invalidation in Mobile Environments,” ACM/Kluwer Mobile Network and Applications, vol. 7, no. 4, pp. 291-303, Aug. 2002.
[20]	K. L. Wu, P. S. Yu, and M. S. Chen, “Energy-Efficient Caching for Wireless Mobile Computing,” Proc. 20th Int'l Conf. Data Engineering, Mar. 1996, pp. 336-343.
[21]	W. C. Hou, M. Su, H. Zhang, and H. Wang, “An Optimal Construction of Invalidation Reports for Mobile Databases,” Proc. of the 10th int’l conf. on Information and knowledge management, Oct. 2001, pp. 458-465.
[22]	M. Su, C. F. Wang, and W. C. Hou, “An Approach of Composing Near Optimal Invalidation Reports,” Proc. of the 6th int’l conf. on Mobile Data Management, May 2005, pp. 116-124.
[23]	Y. S. Lu and X. K. Shao, “Improve Performance of Disconnected Operation through Submitting by Probability and Transferring Transactions in Groups,” Proc. of the 2003 Int'l Conf. on Computer Networks and Mobile Computing, Oct. 2003, pp. 502-505.
[24]	J. Jing, A. Helal, and A. Elmagarid, “Client-Server Computing in Mobile Environments,” ACM Computing Surveys, vol. 31, no. 2 pp.117-157, June 1999.
[25]	S. Lee, M. Kitsuregawa, and C. S. Hwang, “Efficient Processing of Wireless Read-only Transactions in Data Broadcast,” Proc. of the 12th Int’l Workshop on Research Issues in Data Engineering: Engineering E-Commerce/E-Business Systems, Feb. 2002, pp.101-111.
[26]	H. Safa, H. Artail, and M. Nahhas, “Enhancing Cache Invalidation in Mobile Environments,” Int’l Conf. On Mobile Technology, Applications, And Systems, Sept. 2008, Article no. 1.
[27]	C. Kumar, G.R. Madhuri, and S. Agrawal, “Efficient Bandwidth Utilization in Mobile Environments for Temporal Based Cache Invalidation,” TENCON 2008, Nov. 2008, pp. 1-5.
[28]	S. Lim, S. H. Chae, Yu Chansu, and C.R. Das, “On Cache Invalidation for Internet-Based Vehicular Ad Hoc Networks,” Proc. 5th Int’l Conf. on MASS 2008, Sept. 2008, pp. 712-717.
[29]	Y. Wang, E. Chan, W. Li, and S. Lu, “Caching Invalidation Strategies for Supporting 'Weak' Location Dependent Queries,” Proc. 28th Int’l Conf. on ICDCS‘08, June 2008, pp. 459-464.
[30]	Y. K. Chang, I. W. Ting, and T. H. Lin, “Dynamic Cache Invalidation Scheme in IR-Based Wireless Environments,” Proc. 22nd Int’l Conf. on AINA’08, Mar. 2008, pp. 697-704.
[31]	J. Cao, Y. Zhang, G. Cao, and L. Xie, “Data Consistency for Cooperative Caching in Mobile Environments”, IEEE Computer, vol. 40, no. 4, pp. 60-66, Apr. 2007.
[32]	W. Stallings, Computer Organization and Architecture: Designing for Performance, 4th Ed, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1996.
[33]	http://ece.ut.ac.ir/classpages/S85/SystemModeling&Simulations/
[34]	http://www.w3.org/XML/
[35]	http://www.w3.org/TR/xquery/
[36]	http://www.w3.org/TR/xquery-update-10/
[37]	http://saxon.sourceforge.net/dtdgen.html
[38]	http://www.cs.washington.edu/research/xmldatasets/www/repository.html
[39]	J. H. Choi, S. H. Park, M. S. Lee, Y. D. Chung, and S. K. Lee, “XIR: Cache Invalidation Strategy for XML Data in Mobile Environments,” Proc. of the 6th Int’l ACM Workshop on Data Engineering for Wireless and Mobile Access, June 2007, pp. 79-82.
[40]	J. Lu, T. W. Ling, C. Y. Chan, and T. Chen, “From Region Encoding to Extended Dewey: On Efficient Processing of XML Twig Pattern Matching,” In Proc. of VLDB, Aug. 2005, pp. 193-204.
[41]	S. H. Park, J. H. Choi, and S. Lee, “An Effective, Efficient XML Data Broadcasting Method in a Mobile Wireless Network,” In Proc.of DEXA, Sept. 2006, pp. 358-367.
[42]	Y. D. Chung and J. Y. Lee, “An Indexing Method for Wireless Broadcast XML Data,” Information Sciences: an International Journal, vol.177, no. 9, pp.1931-1953, May, 2007.
[43]	C. S. Park, C. S. Kim, and Y. D. Chung, “Efficient Stream Organization for Wireless Broadcasting of XML Data,” In Proc. of Asian Computing Science Conference, Dec. 2005, pp. 223-235.
[44]	S. Acharya, M. J. Franklin, and S. B. Zdonik, “Disseminating Updates on Broadcast Disks,” In Proc.of VLDB, Sept. 1996, pp 354-365.
[45]	I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld, “Updating XML,” In Proc. of SIGMOD Conf., May. 2001, pp 413-424.
[46]	A. Schmidt, F. Waas, M. L. Kersten, M. J. Carey, I. Manolescu, and R. Busse, “Xmark: A Benchmark for XML Data Management,” In Proc. of VLDB, Mar. 2002, pp. 974-985.
[47]	http://monetdb.cwi.nl/xml/generator.html
[48]	C. Byun, I. Yun, and S. Park, “An Efficient Detection of Conflicting Updates in Valid XML,” Proc. 7th IEEE Int’l Conf. on Computer and information Technology, Oct. 2007, pp. 17-22.
[49]	A. Gabillon, “A Logical Formalization of a Secure XML Database,” Computer Science and System Engineering Journal. vol. 21, no. 5, Sept. 2006.
[50]	A. Gabillon, “A Secure XML Database,” 4th Conf. on Security and Network Architectures (SAR), June 2005.
[51]	J. H. Choi and S. K. Lee, “An Efficient Cache Access Protocol in a Mobile Computing Environment,” ISPA 2005, Nov. 2005, pp 1123-1134.
[52]	B. Mandhani and D. Suciu, “Query Caching and View Selection for XML Databases,” Proc.31st Int'l Conf. Very Large Databases (VLDB '05), Aug.-Sept. 2005, pp. 469-480.
[53]	http://www.informatik.uni-freiburg.de/~may/Mondial/florid-mondial.html