臺灣博碩士論文加值系統

有別於以往傳統儲存轉發的傳輸機制，網路編碼可在封包被傳輸之前，將不同來源端所送出的封包結合。近年來很多研究顯示，無線網路廣播的特性，應用上網路編碼的技術，可以有效的提升整體的網路效能。在無線網路中，封包是透過廣播到特定範圍來傳送，因此其鄰居節點能有機會竊聽到其他點所傳輸的封包。當節點有傳送機會時，考慮其他節點所偷聽到的封包資訊，則可以利用編碼來減少傳輸的次數。在本論文我們將研究結合網路編碼與媒體存取控制，來改善無線網路的效能。

Unlike the traditional store-and-forward mechanism in packet-switching networks,network coding schemes could combine and modify the contents of a number of packets from different source before the packets are forwarded.It has been recently shown that network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks,each transmitted packet is broadcasted within a certain area and can be overheard by the neighboring nodes.When a node needs to transmit packets,it employs the coding approach that uses the knowledge of what the node''s neighbors have heard in order to reduce the number of transmissions.
In this thesis,I propose jointly designing the network coding scheme and the media access control scheme to improve the performance of wireless networks.

致謝 I
中文摘要 II
ABSTRACT III
目錄 IV
圖目錄.. VI
第一章 緒論 1
1-1 網路編碼的簡介 1
1-2 無線網路之網路編碼 3
1-3 文獻探討 4
1-4 研究動機與目標 7
1-5 文章組織 7
第二章 系統模型 8
2-1 模型架構 8
2-2 預測性輪詢演算法 10
2-3 考量封包生命時間之預測性輪詢演算法 19
第三章 網路編碼排程演算法 24
3-1 問題描述與介紹 24
3-2 編碼架構 25
3-3 最大編碼機會優先演算法 28
3-4 模擬結果 33
第四章 模擬結果 37
4-1 模擬方法與環境與參數 37
4-2 各節點之封包到達率皆相同，各節點之封包生命時間皆相同 38
4-3 各節點之封包到達率不完全相同，各節點之封包生命時間皆相同 40
4-4 各節點之封包到達率皆相同，各節點之封包生命時間不完全相同 42
4-5 各節點之封包到達率不完全相同，各節點之封包生命時間不完全相同 44
第五章 總結 47
參考文獻 48

[1] 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, pp. 1204-1216.
[2] A.Argyriou, “Wireless network coding with improved opportunistic listening,”IEEE Transactions on Wireless Communications ,Vol. 8, No. 4, April 2009, pp. 2014 - 2023.
[3] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading Structure for Randomness in Wireless Opportunistic Routing,” Proceedings of ACM SIGCOMM, August 2007, pp. 169–180.
[4] K.Chi , X.Jiang and S.Horiguchi , “Network Coding Opportunity Analysis of COPE in Multihop Wireless Networks,” IEEE Wireless Communications and Networking Conference, March , April 3 2008, pp. 2858-2863.
[5] Chung-Hua Chu , De-Nian Yang and Ming-Syan Chen. “Using Network Coding for Dependent Data Broadcasting in a Mobile Environment,” IEEE Global Telecommunications Conference, November 2007, pp. 5346-5350.
[6] S. Deb, M. Effros, T. Ho, D. R. Karger, R. Koetter, D. S. Lun, M. Médard, and N. Ratnakar, “Network Coding for Wireless Applications: A Brief Tutorial,” International Workshop on Wireless Ad-hoc Networks, May 2005.
[7]Q.Dong, J.Wu,W.Hu,and J. Crowcroft, “Practical Network Coding in Wireless Networks,”Proceedings of the 13th annual ACM international conference on Mobile computing and networking,2007, pp.306-309.
[8]R.Dougherty,C.Freiling,and K.Zeger, “Insufficiency of Linear Coding inNetwork Information Flow,” IEEE Transactions on Information Theory , Vol. 51, No. 8, August 2005,pp. 2745-2759.
[9] C. Fragouli, J. L. Boudec, and J. Widmer. "Network Coding: An Instant Primer,"ACM SIGCOMM Computer Communication Review, Vol. 36 , No.1,January 2006, pp. 63-68.
[10] Rung-Hung Gau and Kuan-Mei Chen, "Predictive Multicast Polling for Wireless Networks with Multipacket Reception and Queueing," IEEE Transactions on Mobile Computing, Vol. 5, No. 6, June 2006, pp. 725-737.
[11] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros, “The Benefits of Coding Over Routing in a Randomized Setting,"
IEEE International Symposium on Information Theory, June 29 – July 4 2003.
[12] T. Ho, M. Médard, J. Shi, M. Effros, and D. Karger, “On Randomized Network Coding,” Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing, October 2003.
[13] T. Ho, M. M′edard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A Random Linear Network Coding Approach to Multicast,” IEEE Transactions on Information Theory , Vol. 52, No. 10 , pp. 413–4430.
[14] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen,“ Polynomial Time Algorithms for Multicast Network Code Construction,” IEEE Transactions on Information Theory , Vol. 51, No. 6, June 2005, pp. 1973-1982.
[15]S.Katti,D.Katabi, W.Hu,H.S.Rahul,and Medard,”The Importance of being Opportunistic:Practical Network Coding for Wireless Environments,”Proceedings of 43st Annual Allerton Conference on Communication, Control,and Computing, September 2005 .
[16] S. Katti, H. Rahul, D. Katabi, W. Hu M. M′edard, and J. Crowcroft, “XORs in the Air : Practical Wireless Network Coding,” IEEE Transactions on Networking, Vol. 16 ,No. 3, June 2008, pp. 497- 510
[17] R. Koetter and M. Médard, “An Algebraic Approach to Network Coding,” IEEE/ACM Transactions on networking , Vol. 11, No. 5, October 2003,pp. 782-795.
[18] J. Le,et al., “How Many Packets Can We Encode? – An Analysis of Practical Wireless Network Coding”, Proceedings of IEEE INFOCOM, April 2008,pp. 371-375.
[19] S. R. Li, R. W. Yeung, and N. Cai, “Linear Network Coding,” IEEE Transactions on Information Theory, Vol. 49, No. 2, February 2003, pp. 371–381.
[20] Z.Li and B.Li, “Network Coding:The Case for Multiple Unicast Sessions,” Proceedings of the 42nd Allerton Annual
Conference on Communication,Control,and Computing, 2004.
[21] J. Liu, D. Goeckel, and D. Towsley, “Bounds On the Gain of Network Coding and Broadcasting in Wireless Networks,” Proceedings of IEEE INFOCOM , May 2007, pp. 24-732.
[22] D. S. Lun, M. Medard, and R. Koetter, “Efficient Operation of Wireless Packet Networks Using Network Coding,” International Workshop on Convergent Technologies , June 2005.
[23]Soji Omiwade,Rong Zheng,Cunqing Hua,"Practical Localized Network Coding in Wireless Mesh Networks", i IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks , June 2008, pp. 332-
340.
[24]S.El Rouayheb, M.A.R. Chaudhry, and A. Sprintson,“On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks,”IEEE Information Theory Workshop, September 2007, pp. 120-125.
[25] S. Sengupta, S. Rayanchu, and S. Banerjee, “An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing,” Proceedings of IEEE INFOCOM, May 2007, pp. 1028–1036.
[26] Y. Wu, P. A. Chou, and S. Y. Kung, “Information Exchange in Wireless Networks with Network Coding and Physical-Layer Broadcast,” Microsoft Corp., Redmond, WA, Tech. Rep. MSR-TR-2004-78.
[27] Y. Wu, J. Padhye, R. Chandra, V. Padmanabhan, and P. A. Chou, “The Local Mixing Problem,” Information Theory and Applications Workshop, February.2006.
[28]Jian Zhang,Yuanzhu Peter Chen,Ivan Marsic,"Network Coding Via Opportunistic Forwarding in Wireless Mesh Networks," IEEE Wireless Communications and Networking Conference, March 31 2008-April 3 2008, pp. 1775-1780
[29] D. Gross and C.M. Harris, Fundamentals of Queueing Theory, thirded. John Wiley and Sons, 1998.