计算机科学 ›› 2018, Vol. 45 ›› Issue (5): 69-74.doi: 10.11896/j.issn.1002-137X.2018.05.012

• 网络与通信 • 上一篇    下一篇

流间编码与流内编码相结合的机会路由算法

韩莉,钱焕延   

  1. 安徽大学计算机科学与技术学院 合肥230039;南京理工大学计算机科学与技术学院 南京210094,南京理工大学计算机科学与技术学院 南京210094
  • 出版日期:2018-05-15 发布日期:2018-07-25
  • 基金资助:
    本文受安徽省自然科学基金(1408085MF122),安徽省高校自然科学研究重点项目(KJ2016A041)资助

Opportunistic Routing Algorithm Combining Intra-session Coding and Inter-session Coding in Wireless Network

HAN Li and QIAN Huan-yan   

  • Online:2018-05-15 Published:2018-07-25

摘要: 文中提出了一个无线Mesh网络上的、结合流内和流间网络编码的MWS优化结构。在该优化结构中,编码分组的虚队列长度,即“信用度”积压,由信用度分配算法决定,节点根据信用度积压对编码方式进行选择,旨在各个流之间均衡分配资源,实现网络效用的最大化。同时,给出了该优化结构对偶算法的启发式实现MiiCode,该算法不使用确定路径,具有更大的灵活性,也有利于获得更多的流间编码机会。流内网络编码具有的良好本地补偿特性减少了源节点发送补偿分组的数量,降低了网络的整体开销。最后,在OMNET++仿真实验中将MiiCode与基于确定路由的COPE和LOR进行了比较。

关键词: 流内网络编码,流间网络编码,网络效用最大化,机会路由,无线Mesh网络,最大权值调度

Abstract: This paper proposed a maximum weight scheduling framework in wireless mesh network.In the framework,the virtual queues of coding packets (named “credit queue”) are updated according to a credit assignment algorithm.A node chooses the way of encoding according to its credit queues to achieve network utility maximization and fair resource allocation between flows.A heuristic algorithm MiiCode was given.In this algorithm,no deterministic routing is needed,which makes it more flexible and helpful for finding more chances for inter-session coding.Intra-session’s capacity of local reparation decreases the number of packets retransmitted from source nodes,and the total cost of the network is decreased.This paper compared MiiCode with COPE and LOR based on routing in simulation results of OMNET++.

Key words: Intra-session network coding,Inter-session network coding,Network utility maximization,Opportunistic routing,Wireless Mesh network,Maximum weight scheduling

[1] KATTI S,KATABI D,HU W,et al.The importance of being opportunistic:Practical network coding for wireless environments[C]∥43rd Annual Allerton Conference on Communication,Control and Computing.2009.
[2] KATTI S,RAHUL H,HU W,et al.Network coding madepractical: Technical Report MIT CSAIL[R].2006.
[3] KATTI S,RAHUL H,HU W,et al.Xors in the air:practicalwireless network coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.
[4] LE J,LUI J C,et al.DCAR:Distributed Coding-Aware Routing in Wireless Networks[J].IEEE Transactions on Mobile Computing,2010,9(4):596-608.
[5] CHACHULSKI S,JENNINGS M,KATTI S,et al.Tradingstructure for randomness in wireless opportunistic routing[J].ACM Sigcomm Computer Communication Review,2007,37(4):169-180.
[6] CHOUMAS K,SYRIGOS I,KORAKIS T,et al.Video-awareMulticast Opportunistic Routing over 802.11 two-hop mesh networks[C]∥Eleventh IEEE International Conference on Sensing,Communication,and Networking.IEEE,2014:486-494.
[7] TIAN X Z,ZHOU Q W.An Algorithm of Wireless RoutingBased on Intra-Flow and Inter-Flow Network Conding[J].ACTA Electronica Sinica,2013,1(2):396-402.(in Chinese) 田贤忠,周前伟.一种基于流内与流间网络编码的无线路由算法[J].电子学报,2013,41(2):396-402.
[8] ERYILMAZ A,SRIKANT R.Joint congestion control,routing and mac for stability and fairness in wireless networks[J].IEEE Journal on Selected Areasin Communications,2006,24(8):1514-1524.
[9] RADUNOVIC B.An Optimization Framework for OpportunisticMultipath Routing in Wireless Mesh Networks[C]∥The 27th Conference on Computer Communications(INFOCOM 2008).2008:2252-2260.
[10] LI B,ERYILMAZ A,SRIKANT R.On the Universality of Age-Based Scheduling in Wireless Networks[C]∥IEEE Conference on Computer Communications.2015.
[11] SEFEROGLU H,MARKOPOULOU A,RAMAKRISHNAN K K.I2NC:Intra- and inter-session network coding for unicast flows in wireless networks[C]∥IEEE INFOCOM.IEEE,2011:1035-1043.
[12] KELLY F P,MAULLOO A,TAN D.Rate control in communication networks:shadow prices,proportional fairness and stabi-lity[J].Journal of the Operational Research Society,1998,49:237-252.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[7] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[8] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[9] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[10] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .