利用網路編碼增進網格網路的效能

Performance Improvement by Network Coding on Grid

甘效原(Hsiao-Yuan Kan)

指導教授 ： 易志偉

國立交通大學/資訊學院/網路工程研究所/碩士(2008年)

https://doi.org/10.6842/NCTU.2008.00037

摘要

近年來無線隨意繞徑協定開始利用地理資訊在大型的無線隨意網路中進行繞徑。其中一個廣為人知的地理資訊繞徑協定－網格繞徑協定－目前已有許多的應用架構於此之上。然而，隨著科技的進步和裝置價格越來越便宜，使得一個裝置將同時負責越來越多的工作，以及無線隨意網路的裝置密度會越來越高，如此會造成無線網格網路負載將越來越重，因此如何增進無線網格網路傳輸效能將會是一個重要的議題。有人提出一個技術-網路編碼，網路編碼主要用來增進網路傳輸效能、網路頻寬等。由於網格網路有多點傳播和路徑分岔的特性，所以網路編碼適用於網格網路之中。
在此篇論文中，我們利用網路編碼演算法- XOR編碼演算法，建構於貪婪網格繞徑協定上面-來增進網格網路的傳輸效能。我們假設網格網路中，每個節點在每個時間槽會以某個機率產生封包，並以隨機媒體存取控制(Random MAC)的方式單點傳播封包。每個封包的容量一樣而且來源點和目的點都是均勻分布在網格網路中。在網格網路達到穩定狀態的模擬實驗中(執行500000時間槽)，XOR編碼演算法可以增進網格網路吞吐量74.0%，點對點延遲55.7%。當節點緩衝存儲器儲存容量小於30個封包量時，儲存容量對網格網路的吞吐量有明顯的改變，但超過30個封包後，增加儲存容量對吞吐量的影響即不顯著。在經過一系列的各種不同的網路環境實驗模擬和分析後，我們可以得到以下結論:在網格網路中使用網路編碼傳遞封包時，不但可以增加網路吞吐量並且可以降低點對點延遲。在未來我們將會對這作相關的理論分析，並把網路編碼應用到三角形和六角形等網路拓墣，以了解網路編碼和網路拓撲的關係。

關鍵字

網格網路 ； 網路編碼 ； XOR 編碼 ； 效能增進

並列摘要

In the recent years, geographic information is exploited for routing in large scale ad hoc networks. One of most famous geographic-based routing protocol, GRID routing, is applied to many applications nowadays. Moreover, with the advance of information technology and cost down in wireless devices, each device can take many more tasks and the device density becomes even denser than before. As, the traffic load becomes heavier and heavier, and how to efficiently utilize the limited wireless resource becomes the most important issue. Recently, a novel technique, network coding, is proposed to improve network throughput and bandwidth. Due to the broadcast nature and path diversity of wireless networks, network coding is applicable to grid networks.
In this thesis, to improve the throughput of grid network, a network coding algorithm, XOR encoding, is exploited in the grid networks with greedy grid routing. We assume that each node unicasts packets with packet generating rate and transmits packets followed Random MAC model in the grid network. Each packet has the same size, and the source and destination pairs are randomly chosen and distributed uniformly over the grid network. Under the stable state run for 500000 time slots, the XOR encoding algorithm improves network throughput and end-to-end delay about 74.0% and 55.7%, respectively. Meanwhile, the network throughput increases when the buffer size is smaller than 30 and slows down when the buffer size exceeds 30. As a summary of the series simulation analyses, it can be concluded that the network coding can both increase network throughput and reduce end-to-end delay for the grid network under different network environments. In the future, we will do some theoretical analysis of grid networks with network coding and exploits network coding to delauney network, hexagonal network, etc. to know the relationship between network topologies and network coding.

並列關鍵字

Grid network ； network coding ； XOR encoding ； performance improvement.

參考文獻

[2] R. Jain, A. Puri, and R. Sengupta, Geographical routing using partial information for wireless ad hoc networks, Personal Communications, IEEE [see also IEEE Wireless Communications], vol. 8, no. 1, pp. 4857, Feb 2001.

[3] W.-H. Liao, J.-P. Sheu, and Y.-C. Tseng, GRID: A fully location-aware routing protocol for mobile ad hoc networks, Telecommunication Systems, vol. 18, no. 1-3, pp. 3760, 2001. [Online]. Available: citeseer.ist.psu.edu/liao01grid.html

[6] C.-W. Huang and C.-W. Yi, The critical grid size and transmission radius for local- minimum-free grid routing in wireless ad hoc networks, Master Thesis of Institute of Network Engineering, College of Computer Science, National Chiao-Tung University , 2007.

[8] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, Op- timized link state routing protocol for ad hoc networks, Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International , pp. 6268, 2001.

[11] Y. H. D. Johnson and D. Maltz, RFC 4728 the dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4, 2007.