多跳无线Mesh网络中网络编码性能研究
|
摘要
近年来无线Mesh网络(WMNs)凭借其低成本接入互联网和高效的扩展性等优势而受到网络领域的关注。但无线Mesh网络由于吞吐量有限,可靠性低而难以满足高清视频,文件共享以及网络游戏等应用的需求。
网络编码自产生以来就被用于解决WMNs中的吞吐量问题,它已被应用到多种网络机制中来达到提高吞吐量的目的。无论这些机制是基于数学理论计算还是实际试验床,它们都利用了无线广播特性混合来自多个源的数据,从而节省带宽。随着近几年的发展,这些基于无线网络编码的吞吐量优化方法可以分为两类:第一类是依靠传统路由协议来确定从源节点到目的节点的路径,在该路径上寻找可能的编码机会来进行编码,这种方式称作非编码感知路由;而另一类为编码感知路由,它是指根据源节点与目的节点之间的路径的编码机会来确定路由。
本文对上述两类方法进行了调研与比较,并对两个代表性的网络编码协议进行了对比分析。其中一个是非编码感知的路由协议COPE,该协议在IP和MAC层之间加入了编码层,当节点发现编码机会时便对数据进行编码操作。而另一种协议采用了编码感知路由方法,它为接收到的数据包指定了两种报头分别来标记编码包和原始包,以此来主动寻找编码机会,并在此基础上确定从源节点到目的节点的路由,该协议被称作BEND协议。
我们在多个不同的WMNs拓扑下对COPE和BEND的协议性能进行了分析,比较在具有多个单播的多跳WMNs中的协议性能,包括数据编码的能力,资源共享效率,拥塞控制等。
实验表明,BEND协议在进行第一跳转发时可以达到预期的性能。但随着中继节点数量多于两跳时,COPE的性能相对于BEND来说具有更好的稳定性。
In the recent years wireless mesh networks become famous in the field of networking because of their advantages in providing cheap accessing to the internet and efficient scaling as the size of the network expand, however these networks suffer from limited throughput and low reliability, hence they can not meet the demands of applications like high definition videos, file sharing and gaming.
Network coding was introduced as a solution to throughput problems in WMNs, since its inception; it has been used by many techniques to achieve the goal of improving the throughput. Whether these mechanisms are theoretical based on mathematical calculations or practical test-beds, they all have utilized the broadcast nature of the wireless medium to mix the data from multiple sources and thus bandwidth saving will obtained. However along these years, these works on throughput optimization using wireless network coding has taken two branches, the first one depends on traditional routing protocol to determine the path from the source to the sink, while the mixing can be done along this path if there is a possible chance to code, this way is called the coding oblivious routing ,while the other branch called coding aware routing, which is mean the path between the source can be established according to where these chances form.
This thesis is a survey between these two branches, here we are investigating and comparing between two different techniques, the first one is coding oblivious routing, and so called COPE, it is a technique that modifies the node’s layer stacks by inserting a coding layer between the IP and MAC layers, thus the node will be able to mix the data when it find the chance to code along the path from the source to the sink. While the other one is coding aware-routing method, which specifies two types of headers for the received packets (encoded and native) that utilized by along with information obtained from the routing table, to proactively search the broadcast for the available coding chances and then draw the path from the source to the sink based on these chances, known by BEND.
We are subjecting these two mechanisms to several topologies of WMNs to provide a full understanding of both behaviors. We are studying their ability to mix multiple packet in single transmission, their capability to share the resources and to prevent congestions in the network and their performance in multi hop multiple unicast flow of WMNs.
The experiments has showed that BEND can offer a promising performance for the first hop forwarding, however COPE comparing to BEND show more stability performance with increasing the number of the node while the data travel more than 2 hop to is its sink.
网络编码自产生以来就被用于解决WMNs中的吞吐量问题,它已被应用到多种网络机制中来达到提高吞吐量的目的。无论这些机制是基于数学理论计算还是实际试验床,它们都利用了无线广播特性混合来自多个源的数据,从而节省带宽。随着近几年的发展,这些基于无线网络编码的吞吐量优化方法可以分为两类:第一类是依靠传统路由协议来确定从源节点到目的节点的路径,在该路径上寻找可能的编码机会来进行编码,这种方式称作非编码感知路由;而另一类为编码感知路由,它是指根据源节点与目的节点之间的路径的编码机会来确定路由。
本文对上述两类方法进行了调研与比较,并对两个代表性的网络编码协议进行了对比分析。其中一个是非编码感知的路由协议COPE,该协议在IP和MAC层之间加入了编码层,当节点发现编码机会时便对数据进行编码操作。而另一种协议采用了编码感知路由方法,它为接收到的数据包指定了两种报头分别来标记编码包和原始包,以此来主动寻找编码机会,并在此基础上确定从源节点到目的节点的路由,该协议被称作BEND协议。
我们在多个不同的WMNs拓扑下对COPE和BEND的协议性能进行了分析,比较在具有多个单播的多跳WMNs中的协议性能,包括数据编码的能力,资源共享效率,拥塞控制等。
实验表明,BEND协议在进行第一跳转发时可以达到预期的性能。但随着中继节点数量多于两跳时,COPE的性能相对于BEND来说具有更好的稳定性。
In the recent years wireless mesh networks become famous in the field of networking because of their advantages in providing cheap accessing to the internet and efficient scaling as the size of the network expand, however these networks suffer from limited throughput and low reliability, hence they can not meet the demands of applications like high definition videos, file sharing and gaming.
Network coding was introduced as a solution to throughput problems in WMNs, since its inception; it has been used by many techniques to achieve the goal of improving the throughput. Whether these mechanisms are theoretical based on mathematical calculations or practical test-beds, they all have utilized the broadcast nature of the wireless medium to mix the data from multiple sources and thus bandwidth saving will obtained. However along these years, these works on throughput optimization using wireless network coding has taken two branches, the first one depends on traditional routing protocol to determine the path from the source to the sink, while the mixing can be done along this path if there is a possible chance to code, this way is called the coding oblivious routing ,while the other branch called coding aware routing, which is mean the path between the source can be established according to where these chances form.
This thesis is a survey between these two branches, here we are investigating and comparing between two different techniques, the first one is coding oblivious routing, and so called COPE, it is a technique that modifies the node’s layer stacks by inserting a coding layer between the IP and MAC layers, thus the node will be able to mix the data when it find the chance to code along the path from the source to the sink. While the other one is coding aware-routing method, which specifies two types of headers for the received packets (encoded and native) that utilized by along with information obtained from the routing table, to proactively search the broadcast for the available coding chances and then draw the path from the source to the sink based on these chances, known by BEND.
We are subjecting these two mechanisms to several topologies of WMNs to provide a full understanding of both behaviors. We are studying their ability to mix multiple packet in single transmission, their capability to share the resources and to prevent congestions in the network and their performance in multi hop multiple unicast flow of WMNs.
The experiments has showed that BEND can offer a promising performance for the first hop forwarding, however COPE comparing to BEND show more stability performance with increasing the number of the node while the data travel more than 2 hop to is its sink.
引文
[1] I. F. Akyildiz, X. Wang, and W Wang. Wireless Mesh Networks: A Survey. Elsevier Journal of Computer Networks, 2005, 47(4):445-487
[2] Whitehead P.. Mesh networks: a new architecture for broadband wireless access systems. In: Proc. of IEEE RAWCON 2000, Denver Marriott, 2000:43-46
[3] Ekram Hossain. Wireless mesh networks: architectures and protocols. Springer, 2008
[4] A. Ramamoorthy, J. Shi, and R. Wesel. On the Capacity of Network Coding for Wireless Networks. In: Proc. of 41th Annual Allerton Conference on Communication, Control, and Computing, Allerton, 2003:1-10
[5] Langberg, M., Medard, M.. On the multiple unicast network coding,. In: Proc. of 47th Annual Allerton Conference on Communication, Control, and Computing. Allerton,2009:222-227
[6] T.C.Ho,Y.-H.Chang,andK.J.Han. On constructive network coding for multiple unicasts. In: Proc of 44th Annual Allerton Conference Communication, Control, Computting, Allerton, 2006:1-10
[7] Koetter, R., Medard, M.. An algebraic approach to network coding. Networking, IEEE/ACM Transactions on , 2003,11(5):782-795
[8] P. A. Chou, Y. Wu, and K. Jain. A Practical Network Coding. In: Proc. of 41st Allerton Conference on Communication, Control and Computing, 2003:1-10
[9] Fang-Chun Kuo, Kun Tan, XiangYang Li. XOR Rescue: Exploiting Network Coding in Lossy Wireless Networks. Sensor, In: Proc. of SECON '09, Rome, 2009:1-9
[10] Mikhail Afanasyev. Overhearing in 802.11 Mesh Networks. UNIVERSITY OF CALIFORNIA, SAN DIEGO, 2009
[11] Sagduyu Y.E., Ephremides A.. Crosslayer design for distributed MAC and network coding in wireless ad hoc networks. In: Proc. of ISIT, 2005:1863-1867
[12] Sudip Misra, Subhas Chandra Misra, Isaac Woungang. Guide to wireless mesh networks, Springer 2009.
[13] Bin Ni, Santhapuri N.; Zifei Zhong, et al. Routing with opportunistically coded exchanges in wireless mesh networks. In Proc. of 2nd IEEE Workshop on Wireless Mesh Networks, 2006:157-159
[14] Rozner E., Seshadri J., Mehta Y., et al. Simple opportunistic routing protocol forwireless mesh networks. In: Proc. of 2nd IEEE Workshop on Wireless Mesh Networks, 2006:48-54
[15] S. Katti, H. Rahul, W. Hu, et al. XORs in the air: Practical wireless network coding. In Proc. of ACM SIGCOMM. Pisa, Italy, 2006:1-12
[16] S. Biswas, R. Morris. ExOR: Opportunistic Routing in Multi-hop Wireless Networks. In: Proc. of ACM SIGGCOMM’05, 2005:133-144
[17] Tracey Ho. Network Coding: An Introduction. California Institute of Technology; Desmond Lun, Broad Institute of MIT and Harvard. Cambridge University Press New York, NY, USA , 2008
[18] Christina Fragouli, Emina Soljanin. Network Coding Fundamentals. Foundations and Trends in Networking, 2007, 2(1):1-133
[19] Shravan Rayanchu, Sayandeep Sen, Jianming Wu. Loss-Aware Network Coding for Unicast Wireless Sessions: Design, Implementation, and Performance Evaluation. In Proc. of the International Conference on Measurement and Modeling of Computer Systems, Annapolis, MD. 2008
[20] Sengupta S., Rayanchu S., Banerjee S.. An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing. In Proc. of INFOCOM’07, 2007:1028-1036
[21] Jilin Le, Lui J., Dah Ming Chiu. DCAR: Distributed Coding-Aware Routing in Wireless Networks. In Proc. of ICDCS '08, Beijing, 2008:462-469
[22] R. Ahlswede, N. Cai, S. R. Li, et al. Network Information Flow. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216
[23] S.Y. Li, R. Yeung, and N. Cai. Linear network coding. Information Theory, IEEE Transactions on, 2003, 49(2):371–381
[24] Jaggi S., Sanders P., Chou P.A.et al. Polynomial time algorithms for multicast network code construction. Information Theory, IEEE Transactions on, 2006, 51(6):1973- 1982
[25] Ho T., Medard M., Koetter, R. et al. Random Linear Network Coding Approach to Multicast. Information Theory, IEEE Transactions on, 2006, 52(10):4413-4430
[26] Campo, Adrian Tauste, Grant Alex. On Random Network Coding for Multicast. In Proc. of ISIT’07, 2007:1591-1595
[27] Sachin Katti, Dina Katabi, Hari Balakrishnan, et al. Symbol-level Network Coding for Wireless Mesh Networks. Seattle Massachusetts Institute of Technology Seattle, Washington, USA, 2008
[28] Zongpeng Li, Baochun Li. Network Coding: The Case of Multiple Unicast Sessions. In Proc. of Allerton Conference on Communications, Control and Computing, Allerton, 2004:1-10
[29] Omiwade S., Rong Zheng, Cunqing Hua. Practical Localized Network Coding in Wireless Mesh Networks. In Proc. of SECON '08, 2008:332-340
[30] Rajesh Prasad. Throughput Enhancement in Wireless Mesh Networks using Local Topology Aided Network Coding. A dissertation presented to the graduate faculty of the University of Louisiana at Lafayette, 2009
[31] Bin Guo, Hongkun Li, Chi Zhou, et al. General Network Coding Conditions in Multi-Hop Wireless Networks. In: Proc. of Communications (ICC), 2010 IEEE International Conference on, 2010:1-5
[32] Jian Zhang, Yuanzhu P. Chen, and I. Marsic. MAC-Layer Proactive Mixing for Network Coding in Multi-Hop Wireless Networks. Elsevier Journal of Computer Networks, 2010, 54(2):196-207
[33] J. Li, C. Blake, D. D. Couto, et al. Capacity of ad hoc wireless networks. In: Proc. of MOBICOM’01, 2001
[34] Gupta P., Kumar P.R.. Towards an information theory of large networks: an achievable rate region. Information Theory, IEEE Transactions on, 2003, 49(8):1877- 1894
[35] D. De Couto, D. Aguayo, J. Bicket, et al. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In: Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom'03), 2003
[36] IEEE Standard for Information Technology- Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std 802.11-1997, pp.i-445, 1997
[37] Issariyakul, E. Hossain. Introduction to Network Simulator NS2. Springer Science+Business Media, LLC 2009
[38] Source code of BEND. http://www.cs.mun.ca/~yzchen/code/BEND.tar.gz
[39] Ioanis Nikolaidis, Michel Barbeau, Evangelos Kranakis. Ad-hoc, mobile, and wireless networks. In: Proc. of 4th International Conference, ADHOC-NOW 2005, Cancun, Mexico, 2005
[40] http://www.comp.nus.edu.sg/~wuxiucha/research/reactive/release.html
[2] Whitehead P.. Mesh networks: a new architecture for broadband wireless access systems. In: Proc. of IEEE RAWCON 2000, Denver Marriott, 2000:43-46
[3] Ekram Hossain. Wireless mesh networks: architectures and protocols. Springer, 2008
[4] A. Ramamoorthy, J. Shi, and R. Wesel. On the Capacity of Network Coding for Wireless Networks. In: Proc. of 41th Annual Allerton Conference on Communication, Control, and Computing, Allerton, 2003:1-10
[5] Langberg, M., Medard, M.. On the multiple unicast network coding,. In: Proc. of 47th Annual Allerton Conference on Communication, Control, and Computing. Allerton,2009:222-227
[6] T.C.Ho,Y.-H.Chang,andK.J.Han. On constructive network coding for multiple unicasts. In: Proc of 44th Annual Allerton Conference Communication, Control, Computting, Allerton, 2006:1-10
[7] Koetter, R., Medard, M.. An algebraic approach to network coding. Networking, IEEE/ACM Transactions on , 2003,11(5):782-795
[8] P. A. Chou, Y. Wu, and K. Jain. A Practical Network Coding. In: Proc. of 41st Allerton Conference on Communication, Control and Computing, 2003:1-10
[9] Fang-Chun Kuo, Kun Tan, XiangYang Li. XOR Rescue: Exploiting Network Coding in Lossy Wireless Networks. Sensor, In: Proc. of SECON '09, Rome, 2009:1-9
[10] Mikhail Afanasyev. Overhearing in 802.11 Mesh Networks. UNIVERSITY OF CALIFORNIA, SAN DIEGO, 2009
[11] Sagduyu Y.E., Ephremides A.. Crosslayer design for distributed MAC and network coding in wireless ad hoc networks. In: Proc. of ISIT, 2005:1863-1867
[12] Sudip Misra, Subhas Chandra Misra, Isaac Woungang. Guide to wireless mesh networks, Springer 2009.
[13] Bin Ni, Santhapuri N.; Zifei Zhong, et al. Routing with opportunistically coded exchanges in wireless mesh networks. In Proc. of 2nd IEEE Workshop on Wireless Mesh Networks, 2006:157-159
[14] Rozner E., Seshadri J., Mehta Y., et al. Simple opportunistic routing protocol forwireless mesh networks. In: Proc. of 2nd IEEE Workshop on Wireless Mesh Networks, 2006:48-54
[15] S. Katti, H. Rahul, W. Hu, et al. XORs in the air: Practical wireless network coding. In Proc. of ACM SIGCOMM. Pisa, Italy, 2006:1-12
[16] S. Biswas, R. Morris. ExOR: Opportunistic Routing in Multi-hop Wireless Networks. In: Proc. of ACM SIGGCOMM’05, 2005:133-144
[17] Tracey Ho. Network Coding: An Introduction. California Institute of Technology; Desmond Lun, Broad Institute of MIT and Harvard. Cambridge University Press New York, NY, USA , 2008
[18] Christina Fragouli, Emina Soljanin. Network Coding Fundamentals. Foundations and Trends in Networking, 2007, 2(1):1-133
[19] Shravan Rayanchu, Sayandeep Sen, Jianming Wu. Loss-Aware Network Coding for Unicast Wireless Sessions: Design, Implementation, and Performance Evaluation. In Proc. of the International Conference on Measurement and Modeling of Computer Systems, Annapolis, MD. 2008
[20] Sengupta S., Rayanchu S., Banerjee S.. An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing. In Proc. of INFOCOM’07, 2007:1028-1036
[21] Jilin Le, Lui J., Dah Ming Chiu. DCAR: Distributed Coding-Aware Routing in Wireless Networks. In Proc. of ICDCS '08, Beijing, 2008:462-469
[22] R. Ahlswede, N. Cai, S. R. Li, et al. Network Information Flow. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216
[23] S.Y. Li, R. Yeung, and N. Cai. Linear network coding. Information Theory, IEEE Transactions on, 2003, 49(2):371–381
[24] Jaggi S., Sanders P., Chou P.A.et al. Polynomial time algorithms for multicast network code construction. Information Theory, IEEE Transactions on, 2006, 51(6):1973- 1982
[25] Ho T., Medard M., Koetter, R. et al. Random Linear Network Coding Approach to Multicast. Information Theory, IEEE Transactions on, 2006, 52(10):4413-4430
[26] Campo, Adrian Tauste, Grant Alex. On Random Network Coding for Multicast. In Proc. of ISIT’07, 2007:1591-1595
[27] Sachin Katti, Dina Katabi, Hari Balakrishnan, et al. Symbol-level Network Coding for Wireless Mesh Networks. Seattle Massachusetts Institute of Technology Seattle, Washington, USA, 2008
[28] Zongpeng Li, Baochun Li. Network Coding: The Case of Multiple Unicast Sessions. In Proc. of Allerton Conference on Communications, Control and Computing, Allerton, 2004:1-10
[29] Omiwade S., Rong Zheng, Cunqing Hua. Practical Localized Network Coding in Wireless Mesh Networks. In Proc. of SECON '08, 2008:332-340
[30] Rajesh Prasad. Throughput Enhancement in Wireless Mesh Networks using Local Topology Aided Network Coding. A dissertation presented to the graduate faculty of the University of Louisiana at Lafayette, 2009
[31] Bin Guo, Hongkun Li, Chi Zhou, et al. General Network Coding Conditions in Multi-Hop Wireless Networks. In: Proc. of Communications (ICC), 2010 IEEE International Conference on, 2010:1-5
[32] Jian Zhang, Yuanzhu P. Chen, and I. Marsic. MAC-Layer Proactive Mixing for Network Coding in Multi-Hop Wireless Networks. Elsevier Journal of Computer Networks, 2010, 54(2):196-207
[33] J. Li, C. Blake, D. D. Couto, et al. Capacity of ad hoc wireless networks. In: Proc. of MOBICOM’01, 2001
[34] Gupta P., Kumar P.R.. Towards an information theory of large networks: an achievable rate region. Information Theory, IEEE Transactions on, 2003, 49(8):1877- 1894
[35] D. De Couto, D. Aguayo, J. Bicket, et al. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In: Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom'03), 2003
[36] IEEE Standard for Information Technology- Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std 802.11-1997, pp.i-445, 1997
[37] Issariyakul, E. Hossain. Introduction to Network Simulator NS2. Springer Science+Business Media, LLC 2009
[38] Source code of BEND. http://www.cs.mun.ca/~yzchen/code/BEND.tar.gz
[39] Ioanis Nikolaidis, Michel Barbeau, Evangelos Kranakis. Ad-hoc, mobile, and wireless networks. In: Proc. of 4th International Conference, ADHOC-NOW 2005, Cancun, Mexico, 2005
[40] http://www.comp.nus.edu.sg/~wuxiucha/research/reactive/release.html