研究生: |
李柏緯 Li, Po-Wei |
---|---|
論文名稱: |
運用網路編碼與譜圖理論於無線全網路廣播之研究 Applied Network Coding and Spectral Graph Theory on Wireless Network-Wide Broadcast |
指導教授: |
林輝堂
Lin, Hui-Tang |
學位類別: |
碩士 Master |
系所名稱: |
電機資訊學院 - 電腦與通信工程研究所 Institute of Computer & Communication Engineering |
論文出版年: | 2016 |
畢業學年度: | 104 |
語文別: | 英文 |
論文頁數: | 80 |
中文關鍵詞: | 全網路廣播 、網路編碼 、譜圖理論 、分散式演算法 |
外文關鍵詞: | network-wide broadcast, network coding, spectral graph theory, distributed algorithm |
相關次數: | 點閱:73 下載:3 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
最近全網路廣播的應用越來越廣泛,例如:程式碼更新、雲端機器人…等,所以本論文探討的問題是在全網路廣播上要如何做有效率的傳輸,意思就是如何從一個來源節點,有效率的將訊息轉傳到網路上的全部節點,而近年來網路編碼興起,也被證實可以大大的提升網路效能,但如何利用網路編碼是一個重要的議題,本篇論文主要介紹如何根據譜圖理論來判斷節點的狀態與重要性並決定編碼封包的長度,使得重要性高的節點可以盡早收集編碼封包來成功解回原本的封包使用,加速封包的轉傳速度,希望提出一個有效率的可調適網路編碼機制,期望目標是使用此分散式的演算法來減少廣播次數,降低整體網路的完成時間,並延長網路運作時間,最後我們也將提出一個簡易的分析模型來預測我們的方法在一跳網路中的封包延遲時間以及傳輸失敗的機率。而主要測試方法是將研究實作在模擬程式NS-2上來驗證方法的正確性與效能的好壞。
Network-wide broadcasting is used increasingly for code updates, cloud robot construction, and so on. In such broadcasts, there exists a single source node, and the aim is to disseminate the data from this source node to all of the nodes in the network in the most efficient manner possible. Recent studies have suggested that network coding provides an effective means of improving the throughput of ad hoc networks, while simultaneously reducing the bandwidth consumption. However, the performance of network coding schemes is critically dependent on the coding length employed at each node. Accordingly, the present study proposes a distributed algorithm for improving the transmission performance in wireless broadcast networks, in which spectral graph theory is employed to determine the critical value of each node based on an examination of its two-hop neighborhood, and the network coding length at the node is then set accordingly. A simple analytical model is derived to investigate the performance of the proposed broadcast protocol in terms of the average throughput, average packet delay and transmission failure probability. In general, the results show that the proposed scheme shortens the total broadcast time, reduces the total number of packet transmissions, and prolongs the network lifetime with that of existing methods.
[1] A. Fu, and P. Sadeghi, “Queue-Based Rate Control for Low Feedback RLNC,”IEEE ICC 2014 – Mobile and Wireless Networking Symposium
[2] C. Ho, K. Obraczka, G.Tsudik, and K.Viswanath, “Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks,”In Proceedings of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication (DIALM), pp. 64-71, 1999
[3] C.Fragouli, J. Widmer, and J. Y. L.Boudec, “Efficient Broadcasting Using Network Coding,”IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008
[4] C. Y. Wang, and H. Y. Wei, “ IEEE 802.11n MAC enhancement and Performance Evaluation,”ACM Mobile Network and Applications, VOL. 14,December 2009
[5] D. Nguyen, T. Tran, T. Nguyen, and B. Bose, “Wireless Broadcasting Using Network Coding,”IEEE TRANSACTIONS ON VEHICULAR TECHONOLOGY, VOL. 16, NO. 2, FEBRUARY 2009
[6] D.Katsaros, N.Dimokas, and L.Tassiulas, “Social Network Analysis Concepts in the Design of Wireless Ad Hoc Network Protocols,” 2010 IEEE Network
[7] D. A. Spielman, “Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices,”Proceedings of the International Congress of Mathematicians Hyderabad, India, 2010
[8] D. Fay, H. Haddadi, A. Thomason, R. Mortier, A. Jamakovic, S. Uhlig, and M. Rio, “Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications,” J. IEEE/ACM Trans. Networking (TON), vol. 18, Issue 1, pp. 164-176, Feb. 2010.
[9] G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,”IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 18, NO. 3, MARCH 2000
[10] H. Lim, and C. Kim, “Multicast Tree Construction and Flooding in wireless Ad Hoc Networks,”In Proceedings of the ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM), 2000.
[11] H. Y. Shwe, and F. Adachi, “Power Efficient Adaptive Network Coding in Wireless Sensor Networks,”Communications (ICC), 2011 IEEE International Conference on
[12] H. T. Lin, and B. S. Lin, “Efficient Broadcast in Wireless Networks Using Adaptive Network Coding and Spectral Graph Analysis,” July 2014
[13] I. H. Hou, Y. E. Tsai, T. Abdelzaher, and I. Gupta, “Adapcode: Adaptive Network Coding for Code Updates in Wireless Sensor Network,”INFOCOM 2008, Apr. 2008.
[14] J. Xie, A. Das, S. Nandi, and A. K. Gupta, “Improving the reliability of IEEE 802.11 broadcast scheme for multicasting in mobile ad hoc networks,”IEEE Wireless Communications and Networking Conference, VOL. 1, pp. 126-131, MARCH 2005
[15] J. C. P. Wang, M.Abolhasan, D. R. Franklin, and F. Safaei, “Characterising the Behavior of IEEE 802.11 Broadcast Transmissions in Ad Hoc Wireless LANs,” Communication, 2009. ICC ’09. IEEE International Conference on
[16] J. S. Lin, K. T. Feng, Y. Z. Huang, and L. C. Wang, “Novel Design and Analysis of Aggregated ARQ Protocols for IEEE 802.11n Networks,”IEEE TRANSACTIONS ONMOBILE COMPUTING, VOL. 12, NO. 3, MARCH 2013
[17] K. H. Lee, and D. H. Cho, “A Multiple Access Collision Avoidance Protocol for Multicast Service in Mobile Ad Hoc Networks,”IEEE Vehicular Technology Conference, vol. 3, pp. 1793-1797, 2003.
[18] K. Wehmuth, A. Ziviani, “Distributed Location of the Critical Nodes to Network Robustness based on Spectral Analysis,” in Proc. Of the Latin American network Operations and Management Symposium – LANOMS. IEEE, Oct. 2011
[19] K. Wehmuth, A. Ziviani, “DACCER: Distributed Assessment of the Closeness Centrality Ranking in complex networks,” Computer Network: The International Journal of Computer and Telecommunications Networking, vol. 57, no. 13, pp. 2536-2548, Sep. 2013
[20] N. Hajlaoui, and I. Jabri, “On the Performance of IEEE 802.11n Protocol,”Wireless and Mobile Networking Conference (WMNC),2012 5th Joint IFIP
[21] P. Chatzimisios, A. C. Boucouvalas and V.Vitsas, “IEEE 802.11 Packet Delay – A Finite Retry Limit Analysis,”Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE (Volume:2 )
[22] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network information flow,”IEEE Transactions on Information Theory, VOL. 46, NO. 4, JULY 2000
[23] S. Y. Ni, Y. C. Tseng, Y. S. Chen, and J. P.Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,”In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, 1999.
[24] S. Y. R. Li, R. W. Yeung, and N. Cai, “Linear Network Coding,”IEEE TRANSACTION ON INFORMATION THEORY, VOL. 49, NO. 2, FEBRUARY 2003
[25] S. W. Kim, B. S. Kim, and I. Lee, “MAC Protocol for Reliable Multicast over Multi-Hop Wireless Ad Hoc Networks,”IEEE Journal of Communications and Networks, VOL. 14,pp. 63-74, Feb. 2012
[26] J. Xie, A. Das, S. Nandi, and A. K. Gupta, “Improving the reliability of IEEE 802.11 broadcast scheme for multicasting in mobile ad hoc networks,”IEEE Wireless Communications and Networking Conference, VOL. 1, pp. 126-131, MARCH 2005
[27] T. Li, Q. Ni, D. Malone, D. Leith, Y. Xiao, and T.Turletti, “Power Efficient Adaptive Network Coding in Wireless Sensor Networks,”IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 2, APRIL 2009
[28] W. S. Lim, D. W. Kim, and Y. J. Suh, “Design of Efficient Multicast Protocol for IEEE 802.11n WLANs and Cross-Layer Optimization for Scalable Video Streaming,”IEEE TRANSACTIONS ONMOBILE COMPUTING, VOL. 11, NO. 5, MAY 2012
[29] Y. Lin and V. W.S. Wong, “Frame Aggregation and Optimal Frame Size Adaptation for IEEE 802.11n WLANs,” IEEE GLOBECOM, Nov. 2006