合作快取是一項能在無線隨意網路中，提高資料存取效率的有效技術。在合作快取技術下，無線隨意網路中的節點彼此合作，快取常用的資料項，以降低資料存取的時間。然而，合作快取也帶來一項新議題－快取一致性。在先前的研究中[26][23][24]，研究者提出了數種在無線隨意網路下的 pull-based 或是 push-based 的快取驗証方法，來 處理此議題。但在現有的 pull-based 快取驗証方法中，行動節點在存取快取資料項時，需每次向伺服器確認其快取資料項是否仍為有效；在現有的 push-based 快取驗証方法中，行動節點在存取快取資料項時，需等待伺服器週期性發佈的的快取驗証報告 (Invalidation Report) 封包，以此來驗証節點中的快取資料項。因此，這兩種類型的快取驗証方法，都會造成資料存取上的延遲。在本論文中，我們提出了一個在無線隨意網路下以發佈/訂閱樹為基礎的快取驗証 (Publish/Subscribe Tree-Based Cache Invalidation, PST-CI)機制，來克服此問題。PST-CI 為結合了 push-based 與 pull-based 兩種類型策略特性的混合式快取驗証策略。我們將快取驗証問題視為是一種特殊的發佈/訂閱系統，在此系統中，資料庫伺服器是唯一的發佈者，向網路中發佈資料更新的資訊；而其他行動節點為訂閱者，訂閱者向伺服器訂閱與其內部快取的資料項相關的更新資訊。在本論文中，我們使用並建立了發佈/訂閱樹 (publish/subscribe tree, P/S tree)作為系統中的基礎設施，伺服器使用 P/S tree 發佈資料更新資訊，而行動節點使用 P/S tree 散佈其訂閱內容。透過數學分析與電腦模擬的結果顯示，與現有的 ACOD[26] 快取驗証策略相比，PST-CIS 可以提供更少的資料存取延遲時間，並消耗較少的電力。

Cooperative Caching is one of effective techniques to improve the performance of data accessing in a mobile ad hoc network (MANET). With cooperative caching, mobile nodes in a MANET cooperate with each other to cache frequent accessed data items so as to reduce the access time of data access. However, for a cached data item to be useful, it should remain consistent with its counterpart in the database server. This requirement is called the cache consistency constraint. In the previous works [26] [23] [24], authors proposed either pull-based or push-based cache invalidation strategies to address the data consistency constraint. With the existing pull-based schemes, a mobile client needs to consult with the server in each query to validate the consistency of its cached data items; on the other hand, with the existing push-based schemes, a mobile client needs to wait the periodically invalidation report (IR) packets which are broadcasted by database server to validate the cached data items. These schemes therefore inevitably incur extra access delay. To reduce the access delay, this thesis propose a new cache invalidation scheme, called publish/subscribe tree-based cache invalidation (PST-CI) scheme. The PST-CI scheme is a hybrid scheme that takes advantages of both the pull-based and push-based schemes, and treats the cache invalidation problem as an special case of a publish/subscribe system. The database server is the only publisher in the system, and all other mobile nodes are the subscribers. Subscribers are only interested in the update events relating to their cached data items. They therefore subscribe these events from the database server. The PST-CI scheme uses a publish/subscribe tree as an infrastructure for handling the update events in the database server. When a mobile client changes its cached data items, it utilizes the publish/subscribe tree to issue a new subscription of update events from the database server. When data update event occurs in the database server, the database server uses the publish/subscribe tree to publish the updated content of the data item to the mobile nodes which subscribing this event. The performancec of the PST-CI and ACOD[26] schemes are compared through mathmetical analysis and performance simulation. The results show that the PST-CI scheme provides lower access delay and lower energy consumption, compared with the ACOD.

[1] “ns notes and documentation,” 2009, http://www.isi.edu/nsnam/ns/.
[2] H. Artail, H. Safa, K. Mershad, Z. Abou-Atme, and N. Sulieman, “Coacs:
A cooperative and adaptive caching system for manets,” Mobile Computing,
IEEE Transactions on, vol. 7, no. 8, pp. 961–977, Aug. 2008.
[3] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,”
Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.
[4] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and zipflike
distributions: evidence and implications,” in INFOCOM ’99. Eighteenth
Annual Joint Conference of the IEEE Computer and Communications Societies.
Proceedings. IEEE, vol. 1, Mar 1999, pp. 126–134 vol.1.
[5] A. Broder and M. Mitzenmacher, “Network applications of bloom filters: A
survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509, Jan. 2004.
[6] J. Cao, Y. Zhang, G. Cao, and L. Xie, “Data consistency for cooperative
caching in mobile environments,” Computer, vol. 40, no. 4, pp. 60–66, April
2007.
[7] J. Cao, Y. Zhang, L. Xie, and G. Cao, “Consistency of cooperative caching in
mobile peer-to-peer systems over manet,” in Distributed Computing Systems
Workshops, 2005. 25th IEEE International Conference on, June 2005, pp. 573–579.
51
[8] X. Cao and C.-C. Shen, “Subscription-aware publish/subscribe tree construction
in mobile ad hoc networks,” vol. 2, Dec. 2007, pp. 1–9.
[9] A. Carzaniga, D. S. Rosenblum, and A. L. Wolf, “Design and evaluation of a
wide-area event notification service,” ACM Transactions on Computer Systems,
vol. 19, no. 3, pp. 332–383, 2001.
[10] N. Chand, R. C. Joshi, and M. Misra, “Cooperative caching strategy in mobile
ad hoc networks based on clusters,”Wireless Personal Communications, vol. 43,
2007.
[11] N. Chand, R. Joshi, and M. Misra, “Cooperative caching in mobile ad hoc
networks based on data utility,” Mobile Information Systems, vol. 3, 2007.
[12] G.-M. Chiu and C.-R. Young, “Exploiting in-zone broadcasts for cache sharing
in mobile ad hoc networks,” Mobile Computing, IEEE Transactions on,
vol. 8, no. 3, pp. 384–397, March 2009.
[13] C.-Y. Chow, H. V. Leong, and A. T. Chan, “Grococa: group-based peer-topeer
cooperative caching in mobile environment,” Selected Areas in Communications,
IEEE Journal on, vol. 25, no. 1, pp. 179–191, Jan. 2007.
[14] Y. Du, S. K. Gupta, and G. Varsamopoulos, “Improving on-demand data
access efficiency in manets with cooperative caching,” Ad Hoc Networks,
vol. 7, no. 3, pp. 579 – 598, 2009.
[15] P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec, “The many
faces of publish/subscribe,” ACM Computing Surveys, vol. 35, no. 2, pp. 114–
131, 2003.
[16] L. Feeney and M. Nilsson, “Investigating the energy consumption of a wireless
network interface in an ad hoc networking environment,” in INFOCOM
52
2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications
Societies. Proceedings. IEEE, vol. 3, 2001, pp. 1548–1557 vol.3.
[17] T. Hara and S. Madria, “Consistency management among replicas in peerto-
peer mobile ad hoc networks,” in Reliable Distributed Systems, 2005. SRDS
2005. 24th IEEE Symposium on, Oct. 2005, pp. 3–12.
[18] ——, “Data replication for improving data accessibility in ad hoc networks,”
Mobile Computing, IEEE Transactions on, vol. 5, no. 11, pp. 1515–1532, Nov.
2006.
[19] J.-L. Huang and M.-S. Chen, “On the effect of group mobility to data replication
in ad hoc networks,” Mobile Computing, IEEE Transactions on, vol. 5,
no. 5, pp. 492–507, May 2006.
[20] Y. Huang and H. Garcia-Molina, “Publish/subscribe tree construction in wireless
ad-hoc networks,” in MDM ’03: Proceedings of the 4th International Conference
on Mobile Data Management. London, UK: Springer-Verlag, 2003, pp.
122–140.
[21] ——,“Publish/subscribe in a mobile environment,”Wireless Networks, vol. 10,
no. 6, pp. 643–652, Nov. 2004.
[22] Y. Huang, J. Cao, Z. Wang, B. Jin, and Y. Feng, “Achieving flexible cache
consistency for pervasive internet access,” in Pervasive Computing and Communications,
2007. PerCom ’07. Fifth Annual IEEE International Conference on,
March 2007, pp. 239–250.
[23] Y. Leu, J.-J. Hung, and M.-B. Lin, “A new cache invalidation and searching
policy for mobile ad hoc networks,” WSEAS Transactions on Computers
Research, vol. 2, pp. 66–72, 2007.
53
[24] W. Li, E. Chan, Y. Wang, and D. Chen, “Cache invalidation strategies for
mobile ad hoc networks,” Sept. 2007, pp. 57–57.
[25] S. Lim, W.-C. Lee, G. Cao, and C. R. Das, “A novel caching scheme for
improving internet-based mobile ad hoc networks performance,” Ad Hoc
Networks, vol. 4, no. 2, pp. 225 – 239, 2006.
[26] ——, “Cache invalidation strategies for internet-based mobile ad hoc networks,”
Computer Communications, vol. 30, no. 8, pp. 1854 – 1869, 2007.
[27] L. Mottola, G. Cugola, and G. Picco, “A self-repairing tree topology enabling
content-based routing in mobile ad hoc networks,” Mobile Computing, IEEE
Transactions on, vol. 7, no. 8, pp. 946–960, Aug. 2008.
[28] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem
in a mobile ad hoc network,” in MobiCom ’99: Proceedings of the 5th annual
ACM/IEEE international conference on Mobile computing and networking. New
York, NY, USA: ACM, 1999, pp. 151–162.
[29] Y. Sawai, M. Shinohara, A. Kanzaki, T. Hara, and S. Nishio, “Consistency
management among replicas using a quorum system in ad hoc networks,”
in Mobile Data Management, 2006. MDM 2006. 7th International Conference on,
May 2006, pp. 128–128.
[30] B. Tang, H. Gupta, and S. Das, “Benefit-based data caching in ad hoc networks,”
Mobile Computing, IEEE Transactions on, vol. 7, no. 3, pp. 289–304,
March 2008.
[31] Y.-W. Ting and Y.-K. Chang, “A novel cooperative caching scheme for wireless
ad hoc networks: Groupcaching,” July 2007, pp. 62–68.
54
[32] V. D. Tracy Camp, Jeff Boleng, “A survey of mobility models for ad hoc
network research,”Wireless Communications and Mobile Computing, vol. 2, pp.
483–502, 2002.
[33] X. Yang and Y. Hu, “A dht-based infrastructure for content-based publish
/subscribe services,” Sept. 2007, pp. 185–192.
[34] L. Yin and G. Cao, “Supporting cooperative caching in ad hoc networks,”
Mobile Computing, IEEE Transactions on, vol. 5, no. 1, pp. 77–89, Jan. 2006.
[35] S. Yoo, J. H. Son, and M. H. Kim, “A scalable publish/subscribe system for
large mobile ad hoc networks,” Journal of Systems and Software, vol. 82, no. 7,
pp. 1152 – 1162, 2009.