進階搜尋


下載電子全文  
系統識別號 U0026-1607201310223600
論文名稱(中文) 在行動隨意網路上之節能廣播與協同式資料快取研究
論文名稱(英文) Energy-Aware Broadcasting and Low-Latency Cooperative Caching Data Access for Mobile Ad Hoc Networks
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 101
學期 2
出版年 102
研究生(中文) 丁義偉
研究生(英文) I-Wei Ting
學號 P78931139
學位類別 博士
語文別 英文
論文頁數 100頁
口試委員 指導教授-張燕光
口試委員-陳永源
召集委員-陳啟彰
口試委員-陳培殷
口試委員-謝孫源
口試委員-朱治平
口試委員-楊朝成
中文關鍵字 網路廣播  連接集合  協同式快取  節能  平衡能源  多點傳遞  路徑穩固  隨意無線網路 
英文關鍵字 Network Broadcasting  Connected Dominating Set (CDS)  Cooperative Caching  Energy-Aware  Energy-Balanced  Multipoint Relays  Path-Stable  Mobile Ad hoc Networks 
學科別分類
中文摘要 在行動隨意無線網路裡,”廣播”是一個基礎的通訊方法,主要是用來給行動主機,作彼此間的資料交換。此外,協同式的資料快取也更進一步的用來減少資料存取的延遲性。
在這篇論文中,我們將審視並討論現有的各種廣播方法與協同式資料快取的作法,並且提出改善的方法。在隨意無線網路中,最簡單的廣播方法是採用洪流式(flooding)演算法,但這可能會導致大量的重覆訊息產生,並充斥在無線網路頻寬上,此為稱是”廣播風暴問題” (Broadcast Storm Problem)。
多點式的訊息傳送(Multi-Point Relays;MPR)是另一種廣播的作法,主要是被用來減少廣播風暴所造成的負面影響。在此方法上,行動主機將週期性的執行一個貪婪演算法,藉著交換鄰近的主機資訊,來找出一個連接網路集合(Connected Dominating Set;CDS)。只有屬於CDS的行動節點才需要回應並傳送廣播訊息。因此,基於CDS的廣播方法是一個可以被使用的方法,因為可以減少重覆的廣播訊息。為了減少CDS的節點個數大小,此類貪婪的演算法執行時,通常會選擇離自己最遠的行動節點(邊界節點),來當作繼續傳遞廣播封包的節點。但是邊界節點有很高的機率會離開訊號範圍外,造成來源到目的的繞路路徑很容易不穩定。因此我們首先提出一個新的廣播方法,稱為動態能源與穩固的多點廣播方法 (Dynamic Power-aware and Stability-aware MultiPoint Relays; DPS-MPR),來避免選擇邊界節點來當作傳遞節點。因此行動節點的傳輸距離可以被減少以達到省電節能,並且減少選擇邊界節點所造成的負面影響。此外,我們也使用一個調整緩衝傳輸距離的方式,來提昇傳遞節點的穩固性,我們用網路模擬器來測試所提出的方法。實驗結果顯示,所提的方法可以節省20~25%的能源,並且提昇傳遞節點的生命週期。
能源的平衡消耗在行動節點之間也是一個重要的議題。因此,我們提出一個改進的CDS方法,稱為節能CDS廣播 (Energy-aware CDS; ECDS),用來平衡網路行動節點的能量消耗。ECDS節點的選擇演算法,是根據計算加權權重函數,來決定要傳遞的節點,加權函數包含了移動主機的移動性與剩餘電力。我們也提出兩種類型的週期性更新機制 (ECDS-I與ECDS-II),用來處理動態網路拓撲的改變與改善能量消耗的不平衡問題。ECDS-I在一個更新的週期內,計算一個CDS集合,而ECDS-II則是在一個週期內,計算多個CDS,以平衡傳輸資料。模擬結果顯示,無論是ECDS-I或ECDS-II,皆成功的改善行動節點能源消耗不平衡的影響。
在有線或是無線網路裡,資料快取是一個通用的技術,可以提高資料的存取性。然而,在行動隨意無線網路裡,會因為行動主機的移動與有限的暫存快取空間,而造成快取命中率減少,並提高了資料延遲性。在此論文中,我們將研究目前的文獻,討論其各種作法的差異性,並提出一個通用式的協同快取來提昇效能,稱為集合式協同快取 (Group-based Cooperative Caching; GCC)。GCC使行動節點與鄰近的節點,形成一個集合,並且交換快取位元資料,此資料用來給資料探索(Data Discovery)、快取儲存(Cache Placement)與快取取代(Cache Replacement)演算法參考。目的是為了減少資料請求的延遲,並能有效地利用自已與鄰近節點的快取空間。兩個最佳化技術也提出用來提昇GCC效能,以減少計算代價與通訊負荷。第一種技術採用叢集式的位元樹來壓縮快取目錄資料。第二種則利用多點傳輸(MPR)的方法來減少群組裡的廣播訊息。我們的模擬結果顯示,最佳化的GCC方法,比起現有的協同式快取方法,能產生較好的結果,包含快取命中率,資料延遲性與平均主機資料跳躍數。
英文摘要 Broadcasting is the primary method used for data communication and exchange among the mobile hosts (MHs) in mobile ad hoc networks (MANETs). Meanwhile, cooperative data caching is useful for reducing the latency of data access. In this thesis, we will survey and discuss various broadcasting and cooperative caching schemes and propose improved methods for both.
The flooding algorithm is a straightforward broadcasting scheme that may result in a substantial amount of redundant messages contending the network bandwidth. This resulting problem is called the broadcast storm problem. The multipoint relay (MPR) is another broadcasting scheme that reduces the effect of the broadcast storm problem. In MPR, MHs perform a greedy algorithm to find a connected dominating set (CDS) through an exchange of neighbor information. Only the MHs belonging to precomputed CDSs are responsible for relaying the broadcast messages. Thus, CDS-based broadcast schemes are promising because they can reduce the number of redundant broadcast messages.
To reduce the size of CDSs, the greedy algorithm used in MPR usually selects the farthest nodes from the source called the border nodes as the forwarding nodes. As border nodes have a high probability of moving out of the transmission range, the routing paths from the source to some destinations in MPR may be unstable. Thus, we first propose a broadcasting scheme called the dynamic power-aware and stability-aware MPR (DPS-MPR). This scheme avoids selecting the border nodes as the forwarding nodes. Therefore, the negative impact of unstable forwarding nodes and the transmission range required by MHs can be reduced, thus saving energy. We also use a range buffer to further enhance the stability of forwarding nodes. We evaluate the performance of the proposed DPS-MPR using NS2 and compare it with existing schemes. The experimental result shows that DPS-MPR saves 20% to 25% of energy and increases the lifetime of forwarding nodes by several seconds.
The balance of energy consumption among MHs is an important issue in MANETs. Therefore, we also propose an improved CDS scheme called the energy-aware CDS (ECDS) broadcast scheme to balance the energy consumption of MHs. The CDS node selection algorithm in ECDS is based on a weighted utility function parameterized with the mobility and remaining power of MHs. Two types of periodical CDS update mechanisms, namely, ECDS-I and ECDS-II, are proposed to deal with the dynamics of network topology and energy-consumption imbalance. ECDS-I computes only one CDS in an update cycle, whereas ECDS-II computes multiple CDSs in a cycle using a simple round-robin approach. Simulation results show that both ECDS-I and ECDS-II outperform the original CDS-based scheme in terms of successful broadcast rate and network lifetime.
Data caching is a popular technique that improves data accessibility in wired or wireless networks. However, in MANETs, improvement on access latency and cache hit ratio may diminish because of the mobility and limited cache space of MHs. An improved cooperative caching scheme called group-based cooperative caching (GCC) is proposed to generalize and enhance the performance of most group-based caching schemes. GCC allows MHs and their neighbors to form a group and exchange a bitmap data directory that is periodically used in the proposed algorithms, including in data discovery, cache placement, and cache replacement. The goal is to reduce the latency of data access and efficiently use available caching space among MH groups. Two optimization techniques are also developed for GCC to reduce computation and communication overheads. The first technique compresses the directories using an aggregate bitmap. The second employs MPRs to develop a forwarding node selection scheme that can reduce the number of broadcast messages inside the group. Our simulation results show that the optimized GCC yields better results than existing cooperative caching schemes in terms of cache hit ratio, access latency, and average hop count.
論文目次 Chapter 1 Introduction .......... 12
Chapter 2 Background .......... 14
Chapter 3 Dynamic Power-aware and Stability-aware Multipoint Relays .......... 19
3.1 Motivation .......... 19
3.2 Related Works .......... 20
3.2.1 Multipoint Relays .......... 20
3.2.2 Power Adaptive Broadcasting .......... 22
3.3 Proposed DPS-MPR .......... 22
3.3.1 Notations and network model .......... 22
3.3.2 Assumption .......... 24
3.3.3 DPS-MPR .......... 24
3.3.4 Algorithm_Hello .......... 24
3.3.5 Algorithm_Adjust .......... 27
3.3.6 Algorithm_Select .......... 29
3.3.7 Algorithm_Expand .......... 30
3.4 Performance Evaluation .......... 31
3.4.1 Simulation environment .......... 31
3.4.2 Experimental results on forwarding rate (efficiency) .......... 32
3.4.3 Expended energy ratio (power saving) .......... 33
3.4.4 Ltime (Stability) .......... 36
3.5 Summary .......... 36
Chapter 4 Energy-Aware Connected Dominating Set Broadcasting .......... 38
4.1 Motivation .......... 38
4.2 Related works .......... 38
4.3 Energy-aware Broadcasting .......... 41
4.3.1 Algorithm_Hello .......... 42
4.3.2 Algorithm_ECDS .......... 46
4.3.3 Multiple CDSs .......... 47
4.4 Simulation results .......... 49
4.4.1 Simulation model .......... 50
4.4.2 Average CDS Size .......... 52
4.4.3 Successful Broadcast Rate (SBR) .......... 53
4.4.4 Living Node Rate (LNR) .......... 55
4.5 Summary .......... 56
Chapter 5 Low-Latency Cooperative Caching Data Access .......... 58
5.1 Motivation .......... 58
5.2 Related works .......... 60
5.3 Improved Group-based Cooperative Caching .......... 65
5.3.1 Assumption and definition .......... 65
5.3.2 Maintaining directory using bitmap .......... 66
5.3.3 Data discovery process .......... 67
5.3.4 Cache placement and replacement algorithm .......... 69
5.3.5 Mobility effect .......... 71
5.3.6 Cache consistency issue .......... 72
5.4 Optimized GCC .......... 73
5.4.1 Aggregate bitmap .......... 73
5.4.2 Forwarding node selection scheme .......... 77
5.5 Simulation Results .......... 80
5.5.1 Simulation model and environment .......... 80
5.5.2 Memory usage .......... 82
5.5.3 Communication overhead .......... 83
5.5.4 Group hit ratio .......... 84
5.5.5 Cache hit ratios .......... 86
5.5.6 Hop count .......... 88
5.5.7 Access latency .......... 89
5.5.8 Optimized GCC (GCCopt) .......... 90
5.6 Summary .......... 92
Chapter 6 Conclusions and Future Works .......... 93
References .......... 95
參考文獻 Bibliography
[1] C. Aggarwal, J. Wolf, and P. Yu, “Caching on the World Wide Web,” IEEE Trans. on Knowledge and Data Eng., vol. 11, no. 1, Jan./Feb. 1999.
[2] H. Artail, H. Safa, K. Mershad, Z. Abou-Atme, and N. Sulieman, “COACS: A Cooperative and Adaptive Caching System for MANETs,” IEEE Trans. on Mobile Computing, vol. 7. no. 8, pp. 961–977, August, 2008.
[3] R. Beraldi and R. Baldoni, “A Caching Scheme for Routing in Mobile Ad Hoc Networks and Its Application to ZRP,” IEEE Transactions on Computers, Vol. 52, No. 8, pp. 1051-1062, Aug. 2003.
[4] Douglas B. West, “Introduction to Graph Theory”, Prentice Hall, USA, 1996.
[5] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web Caching and Zipf-like Distributions: Evidence and Implications,” Proc. IEEE INFOCOM, 1999.
[6] J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. of ACM/IEEE Mobicom’98, pp. 85–97, 1998.
[7] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Comm. & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, pp. 483–502.
[8] G. Cao, L. Yin and C. R. Das, “Cooperative Cache Based Data Access Framework for Ad Hoc Networks,” IEEE Computer, pp. 32–39, February 2004.
[9] J. Cartigny, D. Simplot, and I. Stojmenovi´c. “Localized energy efficient broadcast for wireless networks with directional antennas.” In Proceedings of the Mediterranean Ad Hoc Networking Workshop (MedHocNet’02), Sardegna, 2002.
[10] N. Chand, R.C. Joshi, and M. Misra, “Efficient Cooperative Caching in Ad Hoc Networks Communication System Software and Middleware,” First International Conference on Comsware, pp.1–8, Jan. 2006.
[11] X. Chen, M. Faloutsos, and S. Krishnamurthy. “Power adaptive broadcasting with local information in ad hoc networks”. IEEE ICNP, November 2003.
[12] G.-M. Chiu and C.-R. Young, “Exploiting In-Zone Broadcasts for Cache Sharing in Mobile Ad Hoc Networks,” IEEE Trans. on Mobile Computing, VOL. 8, NO. 3, MARCH 2009.
[13] J. Cho, S. Oh, J. Kim, H. Ho Lee, J. Lee, “Neighbor caching in multi-hop wireless ad hoc networks,” IEEE Communications Letters, vol. 7, Issue 11, pp. 525–527, 2003.
[14] C.-Y. Chow, H.-V. Leong, and A. Chan, “Peer-to-Peer Cooperative Caching in Mobile Environments,” Intl. Conf. on Distributed Computing Systems Workshop, 2004.
[15] Fei Dai, Jie Wu, “An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks”, IEEE Transactions on Parallel and Distributed Systems, 15(10), pp. 908-920, 2004.
[16] Cartigny and D. Simplot, “Border Node Retransmission Based Probabilistic Broadcast Protocols in Ad-Hoc Networks.” In Proc. 36th International Hawaii International Conference on System Sciences (HICSS’03), Hawaii, USA. 2003.
[17] Kevin Fall, Kannan Varadhan, The NS2 manual, the VINT Project, Apr. 2011, http://www.isi.edu/nsnam/ns/doc/. Accessed 3 Sept. 2012.
[18] L. Fan, P. Cao, J. Almeida, and A. Z. Broder, “Summary Cache: A Scalable Wide Area Web Cache Sharing Protocol,” Proc. ACM SIGCOMM, 1998, pp. 254–265.
[19] IETF MANET Working Group, http://www.ietf.org/html.charters/manet-charter.html. Accessed 3 Sept. 2012.
[20] F. Ingelrest, D. Simplot-Ryl, I. Stojmenović. “Optimal Transmission Radius for Energy Efficient Broadcasting Protocols in Ad Hoc Networks.” in IEEE Transactions on Parallel and Distributed Systems, 2006.
[21] T. Hara, “Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility,” Proc. IEEE INFOCOM 2001, pp. 1568–1576.
[22] T. Hara, “Replica Allocation Methods in Ad Hoc Networks with Data Update,” Mobile Networks and Applications, 8, 343–354, 2003.
[23] Zhuo Liu, Bingwen Wang, Lejiang Guo, “A Survey on Connected Dominating Set Construction Algorithm for Wireless Sensor Networks”, Information Technology Journal, 9, pp. 1081-1092, 2010.
[24] W. Lou and J. Wu. “Double-covered broadcast (DCB): A simple reliable broadcast algorithm in manets.” In IEEE Infocom, 2004.
[25] C. Imrich, M. Conti, and J. Liu, “Mobile Ad Hoc Networking: Imperatives and Challenges,” Ad Hoc Networks, vol. 1, Jul. 2003, pp. 13–64.
[26] Mamoun Hussein Mamoun, "A New Proactive Routing Protocol for MANET", AISS: Advances in Information Sciences and Service Sciences, Vol. 3, No. 2, pp. 132-140, 2011.
[27] W. H. O. Lau, M. Kumar, and S. Venkatesh, “A Cooperative Cache Architecture in Supporting Caching Multimedia Objects in MANETs,” Fifth Int’l Workshop Wireless Mobile Multimedia, 2002.
[28] S. Lim, W.-C. Lee, G. Cao, and C.-R. Das, “A Novel Caching Scheme for Internet-Based Mobile Ad Hoc Networks,” Proc. IEEE Int’l Conf. Computer Comm. and Networks (ICCCN), IEEE Press, 2003, pp. 38–43.
[29] Mirela Marta, Mihaela Cardei, “Improved sensor network lifetime with multiple mobile sinks”, Pervasive and Mobile Computing, 5(5), pp. 542–555, 2009.
[30] M. Papadopouli and H. Schulzrinne, “Effects of Power Conservation, Wireless Coverage and Cooperation on Data Dissemination among Mobile Devices,” Proc. MobiHoc, ACM Press, 2001, pp. 117–127.
[31] W. Peng and X. Lu, “On the reduction of broadcast redundancy in mobile ad hoc networks,” Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 129-130, 2000.
[32] C. Perkins, E. Belding-Royer, and I. Chakeres, “Ad Hoc On Demand Distance Vector (AODV) Routing,” IETF Internet draft, draft-perkins-manet-aodvbis-00.txt, Oct. 2003.
[33] A. Qayyum, L. Viennot, and A.Laouiti, “Multipoint relaying for Flooding broadcast messages in mobile wireless networks,” in Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS’02), Hawaii, 2002.
[34] A. Rousskov and D. Wessels, “Cache Digests,” Computer Networks and ISDN Systems, vol. 30, 1998, pp. 2155–2168.
[35] F. Sailhan and V. Issarny, “Cooperative Caching in Ad Hoc Networks,” International Conference on Mobile Data Management (MDM), pp. 13–28, 2003.
[36] Andreas Savvides, Chih-Chieh Han, Mani B. Strivastava, “Dynamic fine-grained localization in ad-hoc networks of sensors”, In ACM MOBICOM, Rome, Italy, pp.166-179, July 2001.
[37] J. Shim, P. Scheuermann, and R. Vingralek, “Proxy Cache Algorithms: Design, Implementation, and Performance,” IEEE Trans. on Knowledge and Data Eng., vol. 11, no. 4, July/Aug. 1999.
[38] M. Sheng, J. Li, and Y. Shi,. “Relative degree adaptive flooding broadcast algorithm for ad hoc networks.” IEEE Transactions on Broadcasting, vol. 51, pp. 216- 222, 2005.
[39] J. Soo Kim, D. J. Scott, and A. Yasinsac. “Probabilistic broadcasting based on coverage area and neighbor confirmation in mobile ad hoc networks.” Proceedings of IEEE Globecom, Nov-Dec 2004.
[40] 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, NAS 2007, pp. 62–68.
[41] Y.-C. Tseng, S.-Y. Ni, and E.-Y. Shih, “Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network,” Proc. IEEE 21st International Conference on Distributed Computing Systems, 2001, pp. 481-488.
[42] Amir Qayyum, Laurent Viennot, Anis Laouiti, “Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks”, In Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS’02), Hawaii, pp. 3866-3875, 7-10 Jan. 2002.
[43] Mrs. Razan Al-Ani, "Simulation and Performance Analysis Evaluation for Variant MANET Routing Protocols", IJACT: International Journal of Advancements in Computing Technology, Vol. 3, No. 1, pp. 1-12, 2011.
[44] D. Wessels and K. Claffy, “ICP and the Squid Web Cache,” IEEE Jour. Selected Areas in Comm., pp. 345–357, 1998.
[45] B. Williams and T. Camp, “Comparison of broadcasting techniques for mobile ad hoc networks,” Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp, 194-205, 2002.
[46] J. Wu, Hailan Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Network”, In Proceedings of the 30th Southeastern Int'l Conf. on Combinatorics, Graph Theory, and Computing (Dial-M), pp.7-14, 1999.
[47] J. Wu and W. Lou. ” Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs,“ IEEE Transactions on COMPUTERS, vol. 55, pages. 334-347, Mar 2006.
[48] J. Wu, Fei Dai, “A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks,” IEEE Transactions on Computers, v.53 n.10, p.1343-1354, October 2004.
[49] J. Wu, Fei Dai, “Broadcasting in Ad Hoc Networks Based on Self-pruning”, In Proceedings of IEEE Infocom, pp. 2240-2250, March 2003.
[50] J. Wu, “An Enhanced Approach to Determine a Small Forward Node Set Based on Multipoint Relay,” Proc. IEEE Semi-Ann. Vehicular Technology Conf. Fall (VTC 2003), Sept. 2003.
[51] J. Wu, Fei Dai, Shuhui Yang, “Iterative Local Solutions for Connected Dominating Set in Ad Hoc Wireless Networks”, IEEE Transactions on Computers, 57(5), pp. 702-715, 2008.
[52] S.-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proc. International Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, 1999.
[53] Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, Jang-Ping Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network”, Wireless Networks, 8(2-3), pp. 153-167, 2002.
[54] Yaxiong Zhao, Jie Wu, Feng Li, Sanglu Lu, “On Maximizing the Lifetime of Wireless Sensor Networks Using Virtual Backbone Scheduling”, IEEE Transactions on Parallel and Distributed Systems, 23(8), pp. 1528-1535, 2012.
[55] L. Yin and G. Cao, “Supporting Cooperative Caching in Ad Hoc Networks,” IEEE INFOCOM, pp. 2537–2547, March 2004.
[56] L. Yin and G. Cao, “Supporting cooperative caching in ad hoc networks,” IEEE Trans. on Mobile Computing, vol. 5, Issue 1, pp. 77–89, Jan. 2006.
[57] Chunhui Zhu, M.Lee, T.Saadawi. “A Border-aware Broadcast Scheme for Wireless Ad Hoc Network.”, IEEE Consumer Communications & Networking, Las Vegas, January 2004.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2013-07-26起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2013-07-26起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw