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

Broadcasting in Wireless Networks with Optimized Transmission Efficiency

賴勇良(Yung-liang Lai)

指導教授 ： 江振瑞

國立中央大學/資訊電機學院/資訊工程學系/博士(2011年)

摘要

廣播是無線網路中一種主要傳播資訊的方式，泛流 (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

參考文獻

[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.

[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.