無線網路廣播傳輸效率最佳化研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：47

、訪客IP：18.224.55.193

姓名

賴勇良(Yung-liang Lai) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

無線網路廣播傳輸效率最佳化研究
(Broadcasting in Wireless Networks with Optimized Transmission Efficiency)

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

廣播是無線網路中一種主要傳播資訊的方式，泛流 (Flooding)是一種簡單的廣播方式，然而，其易於引發許多冗餘的傳輸，使得傳輸效率不高，如何用最少的傳輸次數來進行廣播以提升廣播的傳輸效率是一個重要的問題。在本論文中，我們針對在二維和三維空間上的廣播傳輸效率最佳化問題，以幾何位置為主(Geometry-based)的廣播方式分別進行探討。
針對二維空間廣播傳輸效率問題，我們提出一個最佳化的廣播協定Optimized Broadcasting Protocol(OBP)。在OBP當中，廣播節點的選擇是根據於六角環結構(hexagon ring structure)，每個節點會根據六角環結構來計算出廣播位置，且唯有最靠近這些位置的節點才需進行廣播。根據分析得知，OBP的傳輸效率為0.55優於其他目前已提出的廣播方式，並且OBP的傳輸效率可以達到理論上界的90%。
針對三維空間廣播傳輸效率問題，我們推導了三維空間上之理論上界值，並提出一個最佳化廣播協定3-Dimensional Optimized Broadcast Protocol(3DOBP)。在3DOBP當中，廣播節點的選擇是根據於六角柱環結構(hexagon prism ring structure)，其基本想法為將一個三維廣播空間視為由許多層組成，而每一層由許多個六角柱體(hexagon prism)組成。根據六角柱環結構來選擇節點進行廣播，可以降低廣播所需的節點數進而提昇廣播效率。根據分析得知，3DOBP的廣播傳輸效率為1/?，優於其他多面體填充(polyhedron-filling)的廣播方法，例如立方體、六角柱、菱形十二面體、及截角八面體。

摘要(英)

Broadcasting is one of the fundamental operations to disseminate information throughout a wireless network. Flooding is a simple method to realize broadcasting. However, flooding will incur a large number of redundant retransmissions, leading to low transmission efficiency, which is the ratio of the effective transmission area to the total transmission area. In this dissertation, we study the problem about how to optimize the transmission efficiency of broadcasting in the 2-dimensional wireless networks and 3-dimensional wireless networks.
In the 2D broadcasting, we propose a geometry-based wireless broadcast protocol, called Optimized Broadcast Protocol (OBP), to improve the transmission efficiency. In OBP, each node calculates the retransmission locations based on a hexagon ring pattern in order to minimize the number of retransmissions, and only the nodes nearest to the calculated locations need to retransmit the broadcast packet. As shown by analysis, the transmission efficiency bound of OBP is 0.55, which is about 90% of the theoretical optimal bound 0.61 and is better than that of BPS, the geometry-based broadcast protocol with the highest transmission efficiency 0.41 known so far. Since the transmission efficiency is inversely proportional to the number of required nodes to cover a network area, in a static deployed network, the number of deployed nodes is minimized by OBP.
In the 3D broadcasting, we derive the upper bound of 3D transmission efficiency and propose a 3D broadcast protocol, called 3DOBP (3-Dimensional Optimized Broadcast Protocol), to achieve optimized transmission efficiency by partitioning the 3D space into multi-layer hexagonal prisms of a hexagon ring pattern in each layer. As we will show, the transmission efficiency of the proposed protocol is 1/π, which is better than those of polyhedron-filling 3D broadcasting approaches using cubes, hexagon prisms, rhombic dodecahedrons, and truncated octahedrons. To the best our knowledge, the proposed broadcast protocol is the one with the highest 3D transmission efficiency so far.

關鍵字(中)

★ 傳輸效率
★ 廣播
★ 無線網路
★ 三維空間廣播

關鍵字(英)

★ Wireless Networks
★ Broadcasting
★ Transmission Efficiency
★ 3-Dimensional Broadcasting

論文目次

摘要
Abstract
Acknowledge
Contents
List of Figures
List of Tables
1. Introduction
1.1. Optimizing transmission efficiency in 2D wireless networks
1.2. Optimizing transmission efficiency in 3D wireless networks
2. Related Work
2.1. Related Work on Broadcasting in 2D wireless network
2.2. Related Work on Broadcasting in 3D wireless network
3. Optimizing Transmission Efficiency in 2-Dimensional Wireless Networks
3.1. Optimized Broadcast Protocol
3.1.1. Basic Idea
3.1.2. Geometric Mapping
3.1.3. Activation Target Mapping
3.1.4. Activation Activation Mapping
3.2. Performance Analysis
3.3. Simulation Experiments
3.3.1. The Number of Transmissions
3.3.2. Transmission Redundancy
3.3.3. Reachability
3.3.4. Energy Consumption
3.3.5. Collision Probability
3.4. Summary
4. Optimizing Transmission Efficiency in 3-Dimensional Wireless Networks
4.1. The Proposed Protocol
4.1.1. Overview of 3DOBP
4.1.2. Geometric Mapping
4.1.3. Activation Target Mapping
4.2. Performance Analysis
4.2.1. Transmission Efficiency Upper Bound
4.2.2. Transmission Efficiency of Cubes
4.2.3. Transmission Efficiency of Hexagonal Prisms
4.2.4. Transmission Efficiency of Rhombic Dodecahedrons
4.2.5. Transmission Efficiency of Truncated Octahedrons
4.2.6. Transmission Efficiency of 3DOBP
4.2.7. Transmission Efficiency Comparison
4.3. Summary
5. Conclusions
Bibliography

參考文獻

[1] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proceeding of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999, pp. 151-162.
[2] D. Kim and N. F. Maxemchuk, “A comparison of flooding and random routing in mobile ad hoc network,” in Proceeding of Third New York Metro Area Networking Workshop, 2003.
[3] B. Das and V. Bharghavan, “Routing in ad-hoc networks using minimum connected dominating sets,” in Proceeding of IEEE International Conference on Communications, 1997, pp. 376-380.
[4] A. Durresi, V. Paruchuri, R. Kannan, S.S. Iyengar, “Optimized Broadcast Protocol for Sensor Networks,“ IEEE Transactions on Computers, Vol. 54, 2005, pp. 1013 – 1024.
[5] V. Paruchuri, Arjan Durresi, Durga S. Dash, Raj Jain, “Optimal Flooding Protocol for Routing in Ad-Hoc Networks,” Technical report, Ohio State University, CS Department, 2002.
[6] W. Peng and X. Lu, “On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks,” in Proceeding of the 1st ACM international symposium on Mobile ad hoc networking & computing, 2000, pp. 129 - 130.
[7] B. Williams and T. Camp, “Comparison of broadcasting techniques for mobile ad hoc networks,” in Proceeding of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002, pp. 194-205.
[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman San Francisco, 1979.
[9] M. V. Marathe, H. Breu, H. B. Iii, S. S. Ravi, and D. J. Rosenkrantz, “Simple heuristics for unit disk graphs,” Networks, Vol. 25, pp. 59-68, 1995.
[10]S. Guha, “Approximation algorithms for connected dominating sets,” Algorithmica, vol. 20, Issue 4, pp. 374-387, Apr. 1998.
[11] J. Wu and H. Li, “On calculating connected dominating set for efficient routing in ad hoc wireless networks,” in Proceeding of the 3rd international Workshop on Discrete Algorithms and Methods For Mobile Computing and Communications, 1999, pp. 7-14.
[12] F. Dai and J. Wu, “Performance Analysis of Broadcast Protocols in Ad Hoc Networks Based on Self-Pruning,” IEEE Trans. Parallel and Distributed Systems, vol. 15, 2004, pp. 1027-1040.
[13] J. Wu and F. Dai, “Broadcasting in Ad Hoc Networks Based on Self-Pruning,” in Proceeding of IEEE INFOCOM, 2003, pp. 2240-2250.
[14] K. S. Prabh and T. Abdelzaher. “On scheduling and real-time capacity of hexagonal wireless sensor networks,” in Proceeding of the 19th Euromicro Conference on Re-al-Time Systems, 2007, pp. 136-145.
[15] K.S. Prabh, C. Deshmukh, and S. Sachan, “A distributed algorithm for hexagonal topology formation in wireless sensor networks,” in Proceedings of the IEEE Conference on Emerging Technologies & Factory Automation, 2009, pp.1-7.
[16] Arjan Duresi and Vamsi Paruchuri, “Adaptive backbone protocol for heterogeneous wireless networks,” Journal of Telecommunication Systems, Special Issue – Advances in Modeling and Evaluation of Communication Systems, vol. 38, 2008, pp. 83-97.
[17] Vamsi Paruchuri, Arjan Durresi, “Broadcast Protocol for Energy-Constrained Net-works,” IEEE Transaction on Broadcasting, Vol. 53, 2007, pp. 112-119.
[18] D. G. Zill, S. Wright, and W. S. Wright, Calculus: Early Transcendentals, Jones & Bartlett Learning, Massachusetts, 2009.
[19] R. Kershner, “The number of circles covering a set,” American Journal of Mathematics, vol. 61, 1939, pp. 665-671.
[20] Vamsi Paruchuri, “Adaptive scalable protocols for heterogeneous wireless networks,” PhD dissertation, Louisiana State University, 2006.
[21] Matlab, The MathWorks, Inc., http://www.mathworks.com.
[22] The network simulator ns-2. http://www.isi.edu/nsnam/ns/
[23] O. Younis and S. Fahmy, “HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 4, 2004, pp. 366-379.
[24] S. M. N. Alam and J. H. Zygmunt, “Coverage and connectivity in three-dimensional networks,” in Proceeding of Mobicom 2006. Los Angeles, CA, 2006.
[25] J. Carle, J.F. Myoupo, and D. Seme, “A Basis for 3-D Cellular Networks,” in Proceeding of the 15th International Conference on Information Networking, 2001.
[26] C. Decayeux and D. Seme, “A new model for 3D cellular mobile networks,” Workshop on Parallel and Distributed Computing, Third International Symposium on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, 2004.
[27] A. Durresi, V. Paruchuri, L. Barolli, and R. Jain, “Air to air communication protocol,” IEEE Aerospace Conference, 2006.
[28] K. Hatzis, G. Pentaris, P. Spirakis, B. Tampakas, and R. Tan, “Fundamental distributed protocols in mobile networks”, chapter in Principle of Distributed Computing, 1999.
[29] W. Heinzelman, A. Chandrakasan, H. Balakrishnan, and C. MIT, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, pp. 660-670, 2002.
[30] V. Paruchuri, A. Durresi, L. Barolli, and M. Takizawa, “Three Dimensional Broadcast Protocol for Wireless Networks,” in Proceeding of International Conference on Parallel Processing, 2007.
[31] M. K. Watfa and S. Commuri, “Optimal 3-dimensional sensor deployment strategy,” in Proceedings of IEEE Consumer Communications and Networking Conference, 2006.
[32] Eric W. Weisstein, “Sphere-Sphere Intersection,” from MathWorld -- A Wolfram Web Resource. http://mathworld.wolfram.com/Sphere-SphereIntersection.html
[33] Aristotle. On the Heaven, Vol. 3, Chapter 8, 350 BC.
[34] Hilbert D, Cohn-Vossen S. Geometry and the Imagination. Chelsea: New York, 1999.
[35] M. Krizek “Super convergence phenomena on three-dimensional meshes.” International Journal of Numerical Analysis and Modeling 2005; 2(1): 43–56.
[36] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai, “Deploying wireless sensors to achieve both coverage and connectivity,” in Proc. ACM MobiHoc, 2006, pp. 131–142.
[37] Z. Yun, X. Bai, D. Xuan, T-H Lai and W. Jia, “Optimal Deployment Patterns for Full Coverage and k-Connectivity (k<=6) Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, Vol 18, No. 3, June 2010, pp. 934-947.
[38] S.Kumar, T.H. Lai, and J. Balogh, “On k-coverage in a mostly sleeping sensor network,” in Proceeding of ACM MobiCom, 2004, pp. 144–158.
[39] S. Kumar, T. H. Lai, and A. Arora, “Barrier coverage with wireless sensors,” in Proceeding of ACM MobiCom, 2005, pp. 284–298.
[40] R. Iyengar, K. Kar, and S. Banerjee, “Low-coordination topologies for redundancy in sensor networks,” in Proceeding of ACM MobiHoc, 2005, pp. 332–342.

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2011-7-28

推文