應用網路編碼之多源節點廣播設計機制

這篇論文主要探討在無線感測網路下，多個感測器有多個資料要散佈至網路中所有節點的廣播效率問題。我們利用網路編碼(network coding)的技術以及提出一套預防死結(deadlock-prevention)發生的機制使得整體的傳輸次數可以大幅地降低，進而讓整體網路有效率的傳輸。我們主要的貢獻如下：第一點，我們將多對全(many-to-all)的最小廣播傳輸問題定義清楚，並將此問題轉化為整數線性規畫(integer linear programming, ILP)可以解的問題。而使用ILP獲得的解可以視為我們所要探討的最少傳輸次數的下界；第二點是我們對此問題結合網路編碼的技術設計了一套分散式的廣播協定機制。這個機制主要分為兩個階段：建廣播樹階段以及應用網路編碼之廣播傳輸階段。在建廣播樹階段，每個節點以分散式選擇parent的方法，並以三個規則進行篩選，有效率地完成建樹階段。而在第二階段利用廣播樹的資訊使用網路編碼進行有效率的傳輸。此外，我們也使用資料優先序的方法預防死結。在模擬結果中，我們所提出的方法能大幅降低整體的傳輸次數，也比現有提出的相關機制好出許多同時也能夠接近ILP的最佳解。

關鍵字

廣播；網路編碼；無限感測網路；能源效率

並列摘要

This thesis addresses the minimum transmission broadcast problem for the many-to-all scenario in wireless sensor networks and presents how a network-coding broadcast protocol with priority-based deadlock prevention can reduce the number of transmissions effectively. Our main contributions are as follows: First, we formulate the MTB problem for the many-to-all with network coding scenario as an integer linear programming (ILP) problem. The solutions obtained by ILP can serve as a lower bound for any protocol. Second, we propose a distributed network-coding broadcast protocol, which constructs efficient broadcast trees and dictates nodes to transmit packets in a network coding manner according to the constructed trees. In addition, we present the priority-based deadlock prevention mechanism to avoid deadlocks. Simulation results confirm that compared with existing protocols in the literature and the performance bounds obtained by our ILP technique, our proposed network-coding broadcast protocol performs very well in terms of the number of transmissions needed.

並列關鍵字

broadcasting ； network coding ； wireless sensor networks ； energy efficiency

參考文獻

[2] J. Hong, W. Li, S. Lu, J. Cao, and D. Chen, “Sleeping Schedule Aware Minimum Transmission Broadcast in Wireless Ad Hoc Networks,” in Proc. IEEE ICPADS, pp. 399-406, Melbourne, Victoria, Australia, Dec. 2008.

[5] Y. Sasson, D. Cavin, and A. Schiper, “Probabilistic Broadcast for Flooding in Wireless Mobile Ad Hoc Networks,” in Proc. IEEE WCNC, pp. 1124-1130, New Orleans, LA, March 2003.

[6] D. Kim, Y. Wu, Y. Li, F. Zou, and D. Du, “Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 20, pp. 147-157, Feb. 2009.

[7] Y. Li, M. T. Thai, F. Wang, C.-W. Yi, P.-J. Wan, and D.-Z. Du, “On Greedy Construction of Connected Dominating Sets in Wireless Networks,” Wireless Communications and Mobile Computing, Vol. 5, pp. 927-932, Dec. 2005.

[11] Y. Wu, P. A. Chou, and S.-Y. Kung, “Minimum-Energy Multicast in Mobile Ad Hoc Networks Using Network Coding,” IEEE Transactions on Communications, Vol. 53, pp. 1906-1918, Nov. 2005.

國際替代計量

應用網路編碼之多源節點廣播設計機制

全文下載

主題瀏覽