無線行動網路上的資料存取技術｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	楊政儒 Cheng-Ru Young
論文名稱：	無線行動網路上的資料存取技術 Data Access Techniques in Wireless Mobile Networks
指導教授：	邱舉明 Ge-Ming Chiu
口試委員:	陳銘憲 Ming-Syan Chen 郭斯彥 Sy-Yen Kuo 莊裕澤 Yuh-Jzer Joung 莊東穎 Tong-Ying Juang 陳秋華 Chyouhwa Chen 陳孟璋 Meng-Chang Chen
學位類別：	博士 Doctor
系所名稱：	電資學院 - 資訊工程系 Department of Computer Science and Information Engineering
論文出版年：	2008
畢業學年度：	96
語文別：	英文
論文頁數：	83
中文關鍵詞：	資料存取、廣播環境、行動隨意網路、交易、同時控制、快取分享
外文關鍵詞：	broadcast environments, mobile ad hoc networks, data access, transaction, concurrency control, caching sharing
相關次數：	點閱：311 下載：11
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

在本論文中，我們將探討無線/行動計算環境中資料存取的相關議題並且提出一些技術來協助有效率的資料存取。我們將以兩種不同的環境來探討這些相關議題。在第一個議題中，我們處理廣播環境中一致性資料傳播的問題並且提出一個新的技術來保證資料可以達到view consistency，View consistency是一種在廣播環境中有用的資料一致性準則。我們的方法是利用伺服端所產生出來的同時控制資訊並於廣播週期一開始時送出此資訊，同時控制資訊主要是記錄伺服端更新交易間的read-from關係。我們方法的優點是同時控制資訊很小但卻很精確，因此可以減少行動交易不必要的放棄，而小的同時控制資訊同時也意味著可以降低通訊負擔。除此之外，我們演算法的計算量在伺服端與客戶端也都不大。我們也探討了無線通訊中可靠度的問題並且在我們的方法中整合了事先擷取的機制。模擬結果顯示我們的方法優於先前的方法。除了達到view consistency的方法外，我們另提出了一個可以達到local view consistency的方法，此方法保證所有在同一行動端所執行的行動交易所看到的更新交易間的次序都是相同的。
在第二個議題中，我們針對行動隨意網路的環境探討其快取分享的機制。為了讓更多的行動節點可以利用到其他行動節點快取內的資料，我們採用了兩種型態的快取分享技術：推播式(push-based)與拉曳式(pull-based)。根據這些技術，我們提出了兩個資料快取機制：IXP(是一種push-based的方法)與DPIP(是一種pull-based的方法)。這些方法與目前方法的不同點在於他們善用區域內廣播(in-zone broadcasts)來幫助快取分享運作。這些方法強調在資料要求結點附近資料快取分享的加強以提升網路效能。特別是DPIP提供一種隱喻式索引推播的特性，此種特性對於增進資料擷取節點附近的快取命中率是相當有幫助的。再者，這些方法也利用了區域內廣播來協助設計一種簡單而且有效率的計數式(count-based)的快取替換機制。在效能方面，我們所提出的這些方法大大的提升了行動隨意網路中資料存取的效能。

In the dissertation, we will study data access issues in wireless/mobile computing environments and present some techniques to facilitate efficient data access in these environments. Specifically, we will address related topics in two different settings. In the first topic, we deal with the problem of disseminating consistent data in broadcast environments and present a novel protocol to deal with the problem such that view consistency, a useful correctness criterion for broadcast environments, is guaranteed. Our protocol is based on concurrency control information that is constructed by the server and is broadcasted at the beginning of each broadcast cycle. The concurrency control information mainly captures read-from relations among update transactions. A salient feature of the protocol is that the concurrency control information is small in size but precise enough for reducing unnecessary abortion of mobile transactions. The small-sized concurrency control information implies low communication overhead on broadcasting system. In addition, the computation overheads imposed by the algorithm on the server and the clients are low. We also address the reliability issue of wireless communication and the incorporation of a prefetching mechanism into our protocol. Simulation results demonstrate the superiority of our protocol in comparison with existing methods. Furthermore, we have extended our protocol to deal with local view consistency which requires all mobile transactions submitted by the same client observe the same serial order of update transactions.
In the second topic, we study cache sharing techniques in mobile ad hoc networks. To allow more mobile nodes to capitalize on the cache contents of a mobile node we resort to two types of cache sharing techniques: push-based and pull-based. Based on the techniques, we propose two caching protocols, IXP (push-based) and DPIP (pull-based), which distinguish themselves from the existing ones in that they fully exploit in-zone broadcasts to facilitate cache sharing operation. Our protocols emphasize the enhancement of cache sharing in the neighborhood of a data requester for improving network performance. In particular, the DPIP protocol offers an implicit index push property, which is highly useful for enhancing cache hit ratio in the neighborhood of a data requester node. Moreover, our protocols also exploit the broadcasts to facilitate the design of a simple but efficient count-based cache replacement scheme. Performance study shows that the proposed protocols can significantly improve the performance of data access in a mobile ad hoc network.

Chapter 1 Introduction............................................................. 3
1 Background .......................................................... 3
2 Objectives of the Dissertation ...................................... 7
3 Organization of the Dissertation .................................... 9
Chapter 2 Related Works ................................................ 10
1 Dissemination of Consistent Data in Broadcast Environments ......... 10
2 Data Access in MENETs .............................................. 12
Chapter 3 Disseminating Consistent Data in Broadcast Environments ...... 16
1 View Consistency and Local View Consistency ........................ 18
1.1 View Consistency ................................................. 18
1.2 Local View Consistency ........................................... 19
2 System Model ....................................................... 19
3 Protocol for View Consistency ...................................... 20
3.1 Timestamp Record ................................................. 21
3.2 Identifying Descendant Transactions .............................. 22
3.3 The Algorithms ................................................... 24
4 Correctness of the Protocol and Relaxation of Blind Writes ......... 27
5 Achieving Local View Consistency ................................... 29
6 Related Extensions ................................................. 31
6.1 Loss of Information .............................................. 31
6.2 Prefetching Mechanism ............................................ 32
7 Performance Evaluation ............................................. 33
7.1 Experimental Setup ............................................... 34
7.2 Simulation Results with View Consistency ......................... 35
7.3 Simulation Results with Related Extensions ....................... 40
7.4 Simulation Results with Local View Consistency ................... 41
7.5 Simulation Results for Energy Consumption ........................ 42
Chapter 4 Push-Based Cache Sharing Scheme in MANETs .................... 46
1 System Model ....................................................... 46
2 Index Push (IXP) Protocol .......................................... 47
2.1 Data Access ...................................................... 48
2.2 Data Caching and IV Update ..........z............................ 49
2.3 Cache Replacement ................................................ 49
3 Looping Problem .................................................... 50
Chapter 5 Pull-Based Caching Sharing Scheme in MANETs .................. 53
1 Data Pull/Index Push (DPIP) Protocol ............................... 54
1.1 Data Access ...................................................... 54
1.2 Implicit Index Push and IV Update ................................ 55
2 Comparison with IXP ................................................ 55
3 Performance Analysis ............................................... 57
4 Performance Evaluation ............................................. 61
4.1 Simulation Setup ................................................. 61
4.2 Simulation Results ............................................... 64
5 Discussion of Related Issues ....................................... 72
5.1 Data Updates ..................................................... 72
5.2 Data Structure for Caching Information ........................... 73
Chapter 6 Conclusions and Future Works ................................. 75
1 Conclusions ........................................................ 75
2 Future Research Directions ......................................... 76
References ............................................................. 78

                                

[1] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast Disks: Data Management for Asymmetric Communication Environments,” Proceedings of ACM SIGMOD Conference, 1995, pp. 199-210.
[2] S. Acharya, M. Franklin, and S. Zdonik, “Dissemination-Based Data Delivery Using Broadcasting Disks,” IEEE Personal Communications, Vol.2, No.6, 1995, pp. 50-60.
[3] S. Acharya, M. Franklin, and S. Zdonik, “Prefetching from a broadcast disk,” Proceedings of the Twelfth International Conference on Data Engineering, 1996, pp. 276-285.
[4] S. Acharya, M. Franklin, and S. Zdonik, “Balancing Push and Pull for Data Broadcast,” Proceedings of ACM SIGMOD Conference, 1997, pp. 183-194.
[5] A. S. Al-Mogren and M. H. Dunham, “BUC, a Simple Yet Efficient Concurrent Control Technique for Mobile Data Broadcast Environment,” Database and Expert Systems Applications, 2001, pp. 564 –569.
[6] P. A. Bernstein, V. Hadzilacos, and N. Goodman, “Concurrency Control and Recovery in Database Systems,” Addison-Wesley, 1987.
[7] P.M. Bober, M.J. Carey, “Multiversion Query Lockig,” Proceedings of the VLDB Conference, 1992, pp. 497-510.
[8] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web Caching and Zipf-like Distribution: Evidence and Implication,” Proceedings of IEEE INFOCOM, 1999, pp. 126-134.
[9] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wiress Ad Hoc Network Routing Protocols,” Proceedings of ACM MobiCom, October 1998, pp. 85-97.
[10] R. Bruno, M. Conti, and E. Gregori, “Mesh Networks: Commodity multihop ad hoc networks,” IEEE Communications Magazine, March 2005, pp. 123-131.
[11] G. Cao, L. Yin, C. R. Das. “Cooperative Cache-Based Data Access in Ad Hoc Networks,” Computer, vol. 37, Issue 2, Feb 2004, pp. 32-39.
[12] N. Chand, R.C. Joshi, and M. Misra, “Cooperative caching in mobile ad hoc networks based on data utility,” Mobile Information System, Vol 3, No. 1, 2007, pp. 19-37.
[13] C.-Y. Chow, H.V. Leong, A. Chan, “Peer-to-Peer Cooperative Caching in Mobile Environments,” Proceedings of the ICDCS Workshops, 2004, pp. 528-533.
[14] C.-Y. Chow, H.V. Leong, A. Chan, “Cache Signatures for Peer-to-Peer Cooperative Caching in Mobile Environments,” Proceedings of AINA, 2004, pp. 96-101.
[15] C.-Y. Chow, H.V. Leong, A. T. S. Chan, “Group-based Cooperative Cache Management for Mobile Clients in Mobile Environments,” Proceedings of ICPP, 2004, pp. 83-90.
[16] T. Clause, P. Jacquet, and A. Laouti, P. Minet, P. Muhlethaler, A. Qayuam, L. Viennot, “Optimized link state routing protocol,” draft-ietf-manet-olsr-07.txt, IETF, http://www.ietf.org, November 2002.
[17] G. Coulouris, J. Dollimore, and T. Kindberg, “Distributed Systems Concept and Design,” Addison-Wesley, Third Edition, 2001.
[18] S. Das, C. Perkins, and E. Royer, “Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks,” Proceedings of IEEE INFOCOM, 2000, pp. 3-12.
[19] L. Fan, P. Cao, J. Almedia, and A. Broder, “Summary cache: A scalable wide area web cache sharing protocol,” Proceedings of ACM SIGCOMM, 1998, pp. 254-265.
[20] V. Grassi, “Prefetching policies for energy saving and latency reduction in a wireless broadcast data delivery system,” Proceedings of the ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile systems, 2000, pp. 77-84.
[21] Z. J. Haas and M. R. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Internet Draft, draft-ietf-manet-zone-zrp- 01.txt, 1998.
[22] T. Hara, “Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility,” Proceedings of IEEE INFOCOM, 2001, pp. 1568-1576.
[23] T. Hara, “Replica Allocation in Ad Hoc Networks with Periodic Data Update,” Proceedings of International Conference on Mobile Data Management, 2002, pp. 79–86.
[24] G. Herman, G. Gopal, K. C. Lee, and A. Weinreb, “The Datacycle Architecture for Very High Throughput Database Systems,” Proceedings of ACM SIGMOD Conference, 1987, pp. 97-103.
[25] J.-L. Huang and M.-S. Chen, “On the Effect of Group Mobility to Data Replication in Ad Hoc Networks,” IEEE Transaction on Mobile Computing, Vol 5, No. 5, May, 2006, pp. 492-507.
[26] Y. Huang and Y. H. Lee, “STUBcast-Efficient Support for Concurrency Control in Broadcast-based Asymmetric Communication Environment,” Computer Communications and Networks, 2001, pp. 262-267.
[27] Kadaba B.-K. and Jeffrey M. Jaffe, “Routing to Multiple Destinations in Computer Networks,” IEEE Transaction on Communications, Vol. Com-31, No. 3, March, 1983, pp. 343-351.
[28] S. S Kim, J. I. Y. Chung, S. Y. Jung, and C. S. Hwang, “Optimistic Transaction Processing Algorithms in Pure-Push and Adaptive Broadcast Environments,” Proceedings of the International Conference on Parallel and Distributed Systems, 2001, pp. 61-68.
[29] Y. Ko and N. Vaidya, “Location-Aided Routing in Mobile Ad Hoc Networks,” Proceedings of ACM MobiCom, 1998, pp. 66-75.
[30] K. W. Lam, V. C. S. Lee, and T. W. Kuo, “Group Consistency for Read-Only Transactions in Mobile Environments,” Proceedings of the Parallel and Distributed Processing Symposium, 2001, pp. 1009-1016.
[31] K. W. Lam, S. H. Son, V. C. S. Lee, and S. L. Hung, “Using Separate Algorithms to Process Read-Only Transactions in Real-Time Systems,” Proceedings of Real-Time Systems Symposium, 1998, pp. 50-59.
[32] K. Y. Lam, M. W. Au, and E. Chan “Broadcasting Consistent Data to Read-Only Transactions from Mobile Clients,” The Computer Journal, Vol. 45, No. 2, 2002, pp. 129-146.
[33] K. Y. Lam, E. Chan, H. W. Leung, and M. W. Au, “Concurrency Control Strategies for Ordered Data Broadcast in Mobile Computing Systems,” Information Systems, Vol. 29, Issue 3, May 2004, pp. 207-234.
[34] W. Lau, M. Kumar, and S. Venkatesh, “A Cooperative Cache Architecture in Supporting Caching Multimedia Objects in MANETs,” Proceedings of the Fifth International Workshop on Wireless Mobile Multimedia, 2002, pp. 56-63.
[35] S.K. Lee, C. S. Hwang, and M. Kitsuregawa, “Using Predeclaration for Efficient Read-Only Transaction Processing in Wireless Data Broadcast,” IEEE Transaction on Knowledge and Data Engineering, Vol. 15, No. 6. November/December 2003, pp. 1579-1583.
[36] S.K. Lee, M. Kitsuregawa, and C. S. Hwang, “Efficient Processing of Wireless Read-Only Transactions in Data Broadcast,” Research Issues in Data Engineering:Engineering E-Commerce/E-Business Systems, 2002, pp. 101-111.
[37] V. C. S. Lee, K. W. Lam, and S. H. Son, “Maintaining Data Consistency Using Timestamp Ordering in Real-Time Broadcast Environments,” Proceedings of International Conference on Real-Time Computing Systems and Applications, 1999, pp. 29-35.
[38] G. Li, B. Yang, and J. Chen, “Efficient Optimistic Concurrency Control for Mobile Real-Time Transactions in Wireless Data Broadcast Environment,” Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2005, pp. 443-446.
[39] G. Li, H. Wang, Y. Liu, and J. Chen, “Mobile Real-Time Read-Only Transaction Processing in Data Broadcast Environments,” Proceedings of the ACM symposium on Applied computing, 2005, pp. 1176-1177.
[40] S. Lim and H. Cho, “Timestamp Based Concurrency Control in Broadcast Disks Environment,” Proceedings of International Conference on AI, Simulation, and Planning in High Autonomy Systems, 2004, pp. 333-341.
[41] S. Lim, W. Lee, G. Cao and C.R. Das, “A novel caching scheme for improving internet-based mobile ad hoc networks performance,” Elsevier Journal on Ad Hoc Networks, vol. 4, no 2, 2006, pp. 225-239.
[42] J. M. Monteriro and A. Brayner, “Controlling Concurrency in Mobile Computing Environments with Broadcast-Based Data Dissemination,” Proceedings of International Euro-Par Conference, 2005, pp. 1069-1079.
[43] T. Moriya and H. Aida, “Cache Data Access System in Ad Hoc Networks,” Vehicular Technology Conference, Vol. 2, April 2003, pp. 1228-1232.
[44] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Shen, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proceedings of ACM Mobicom, August 1999, pp 151-162.
[45] M. Papadopouli and H. Schulzrinne, “Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices,” Proceedings of ACM MobiHoc, Oct. 2001, pp. 117-127.
[46] C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” Proceedings of IEEE WMCSA, 1999, pp. 90-100.
[47] E. Pitoura, “Supporting Read-Only Transactions in Wireless Broadcasting,” Proceedings of DEXA98 International Workshop on Mobility in Databases and Distributed Systems, 1998, pp. 428-443.
[48] E. Pitoura and P. K. Chrysanthis, “Scalable Processing of Read-Only Transactions in Broadcast Push,” Proceedings of IEEE International Conference on Distributed Computing System, 1999, pp. 432-439.
[49] E. Pitoura and P. K. Chrysanthis, “Multiversion Data Broadcast,” IEEE Transaction on Computers, Vol. 51, No. 10, October 2002, pp. 1224-1230.
[50] A. Rousskov and D. Wessels, “Cache Digests,” Computer Networks and ISDN Systems, Vol. 30, No. 22-23, 1998, pp. 2155-2168.
[51] P. M. Ruiz and A. F. Gomez-Skarmeta, “Heuristic Algorithms for Minimum Bandwith Consumption Multicast Routing in Wireless Mesh Networks,” In ADHOC-NOW, pp. 258-270, 2005.
[52] F. Sailhan and V. Issarny, “Energy-aware Web Caching for Mobile Terminals,” Proceedings of Distributed Computing Systems Workshops, July 2002, pp. 820-825.
[53] J. Shanmugasundaram, A. Nithrakashyap, R. Sivasankaran, and K. Ramamritham, “Efficient Concurrency Control for Broadcast Environments,” Proceedings of ACM SIGMOD Conference, 1999, pp. 85-96.
[54] J. Shim, P. Scheuermann, and R. Vingralek, “Proxy Cache Algorithm: Design, Implementation, and Performance,” IEEE Trans. Knowledge and Data Eng., vol. 11, no. 4, July/Aug. 1999, pp. 549-562.
[55] A. Silberschatz, P. B. Galvin, and G. Gagne, “Operating System Concepts,” John Wiley & Sons, 2004.
[56] D. Wessels and K. Claffy, “ICP and the Squid Web Cache,” IEEE Journal on Selected Areas in Communication, Mar. 1998, pp. 345-357.
[57] Y. Xu, J. Heidemann, and D. Estrin, “Geography-Information Energy Conservation for Ad Hoc Routing,” Proceedings of ACM MobiCom, July 2001, pp. 70-84.
[58] L. Yin and G. Cao, “Supporting Cooperative Caching in Ad Hoc Networks,” Proceedings of IEEE INFOCOM, 2004, pp. 2537-2547.
[59] L. Yin and G. Cao, “Supporting Cooperative Caching in Ad Hoc Networks,” IEEE Transaction on Mobile Computing, Vol 5, No. 1, January, 2006, pp. 77-89.
[60] G. Zipf, “Human Behavior and the Principle of Least Effort,” Addison Wesley, 1949.
[61] ns Notes and Documentation. (http://www.isi.edu/nsnam/ns/)

簡易檢索 / 詳目顯示

相關論文