高级搜索

一种新的基于虚拟队列的无线多播网络编码调度策略

张瑞 占友 钱权

引用本文: 张瑞, 占友, 钱权. 一种新的基于虚拟队列的无线多播网络编码调度策略[J]. 电子与信息学报, doi: 10.11999/JEIT190059 shu
Citation:  Rui ZHANG, You ZHAN, Quan QIAN. New Coding Scheduling Strategy Based on Virtual Queuein Wireless Multicast Network[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190059 shu

一种新的基于虚拟队列的无线多播网络编码调度策略

    作者简介: 张瑞: 女,1981年生,副教授,研究方向为计算机网络、无线网络和网络编码等;
    占友: 男,1993年生,硕士生,研究方向为无线网络编码;
    钱权: 男,1972年生,研究员,研究方向为计算机网络、网络安全以及云计算、大数据分析和大规模分布式领域中的网络环境
    通讯作者: 张瑞,ruizhang@shu.edu.cn
  • 基金项目: 国家重点研发计划(2018YFB0704400, 2018YFB0704404),新型网络体系架构与关键技术(2018B010113001)

摘要: 网络编码由于其传输效率高的特性,近年来在无线多播网络中得到广泛的应用。针对无线多播网络中丢包自动重传效率低的问题,该文提出一种新的基于虚拟队列中数据包到达时间的编码调度策略(CSAT)。在CSAT策略中,为了提高编码效率,采用虚拟队列来存放初始以及未被所有接收者接收到的数据包。考虑到队列的稳定性,CSAT策略按照一定的比率从主次队列选择发送;在次队列发送数据包时,结合了编码和非编码两种方式,根据数据包到达队列的先后,选取能够使较多数据包参与编码的方式发送。仿真结果表明,该文所提的CSAT编码调度策略在有效提高了数据包传输效率的同时,提高了网络的吞吐量并降低了平均等待时延。

English

    1. [1]

      AHLSWEDE R, CAI Ning, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204–1216. doi: 10.1109/18.850663

    2. [2]

      AMERIMEHR M H, ASHTIANI F, and VALAEE S. Maximum stable throughput of network-coded multiple broadcast sessions for wireless tandem random access networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(6): 1256–1267. doi: 10.1109/TMC.2013.2296502

    3. [3]

      SUNDARARAJAN J K, SHAH D, MÉDARD M, et al. Feedback-based online network coding[J]. IEEE Transactions on Information Theory, 2017, 63(10): 6628–6649. doi: 10.1109/TIT.2017.2710192

    4. [4]

      CHEN Wei, LETAIEF K B, and CAO Zhigang. Buffer-aware network coding for wireless networks[J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1389–1401. doi: 10.1109/TNET.2011.2176958

    5. [5]

      SAGDUYU Y E and EPHREMIDES A. On Broadcast stability of queue-based dynamic network coding over erasure channels[J]. IEEE Transactions on Information Theory, 2009, 55(12): 5463–5487. doi: 10.1109/tit.2009.2032732

    6. [6]

      SAGDUYU Y E, GEORGIADIS L, TASSIULAS L, et al. Capacity and stable throughput regions for the broadcast erasure channel with feedback: An unusual union[J]. IEEE Transactions on Information Theory, 2013, 59(5): 2841–2862. doi: 10.1109/tit.2011.2171180

    7. [7]

      SHAO Pengfei, ZHAO Yanwei, YANG Mingxia, et al. Hash searching and network coding based constant retransmission for wireless multicast[J]. IET Communications, 2017, 11(2): 302–309. doi: 10.1049/iet-com.2016.0484

    8. [8]

      TAN Guoping, CHEN Yangjie, LI Yueheng, et al. PNCIA: An interference aware wireless multicast scheme with partial network coding[C]. 2016 IEEE Information Technology, Networking, Electronic and Automation Control Conference, Chongqing, China, 2016: 155–159. doi: 10.1109/ITNEC.2016.7560339.

    9. [9]

      MOHANDESPOUR M, GOVINDARASU M, and WANG Zhengdao. Rate, energy, and delay tradeoffs in wireless multicast: network coding versus routing[J]. IEEE Transactions on Mobile Computing, 2016, 15(4): 952–963. doi: 10.1109/TMC.2015.2439258

    10. [10]

      LI Yuzhou, SHI Yan, SHENG Min, et al. Energy-efficient transmission in heterogeneous wireless networks: A delay-aware approach[J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7488–7500. doi: 10.1109/TVT.2015.2472578

    11. [11]

      MOGHADAM N and LI Hongxiang. Improving queue stability in wireless multicast with network coding[C]. Proceedings of 2015 IEEE International Conference on Communications, London, UK, 2015: 3382–3387. doi: 10.1109/ICC.2015.7248847.

    12. [12]

      MOGHADAM N and LI Hongxiang. Queue stability analysis in network coded wireless multicast network[J]. IEEE Communications Letters, 2016, 20(5): 950–953. doi: 10.1109/LCOMM.2016.2524453

    13. [13]

      MOGHADAM N and LI Hongxiang. A new wireless multicast queuing design using network coding and data-flow model[J]. IEEE Communications Letters, 2016, 20(8): 1603–1606. doi: 10.1109/LCOMM.2016.2568212

    14. [14]

      BÓNA M. Introduction to Enumerative Combinatorics[M]. Boston: McGraw-Hill, 2007: 63–70.

    15. [15]

      杨雅琴. 第二类Stirling数计算公式的一种证明[J]. 青岛科技大学学报: 自然科学版, 2009, 30(4): 369–371. doi: 10.3969/j.issn.1672-6987.2009.04.023
      YANG Yaqin. The proof for formula of stirling numbers of the second-kind[J]. Journal of Qingdao University of Science and Technology:Natural Science Edition, 2009, 30(4): 369–371. doi: 10.3969/j.issn.1672-6987.2009.04.023

    1. [1]

      卢冀, 肖嵩, 吴成柯. 一种基于机会式网络编码的高效广播重传方法. 电子与信息学报,

    2. [2]

      王练, 王萌, 任治豪, 白佳洁. D2D网络中基于立即可解网络编码的时延最小化重传方案. 电子与信息学报,

    3. [3]

      王练, 张贺, 张昭, 张勋杨. 基于自适应随机线性网络编码的优先级调度方案. 电子与信息学报,

    4. [4]

      苏玉泽, 孟相如, 康巧燕, 韩晓阳. 核心链路感知的可生存虚拟网络链路保护方法. 电子与信息学报,

    5. [5]

      张广驰, 曾志超, 崔苗, 林凡. 无线供电混合多址接入网络的资源分配. 电子与信息学报,

    6. [6]

      肖楠, 王伟, 梁俊, 刘玉磊, 张振浩. 感知不确定下卫星认知无线网络多频谱接入优化策略. 电子与信息学报,

    7. [7]

      蒋友辉, 卢汉成, 洪佩琳, 薛开平. 基于网络编码的无线多播速率选择机制. 电子与信息学报,

    8. [8]

      王静, 刘景美, 王新梅. 基于网络编码的多播路由算法性能分析. 电子与信息学报,

    9. [9]

      周志恒, 周亮. 多播网络中基于网络编码的高效丢失恢复机制. 电子与信息学报,

    10. [10]

      林晓斌, 许胤龙, 詹成, 王青山. 基于网络编码的分层媒体多播中的层速率分配优化. 电子与信息学报,

    11. [11]

      李楠, 戚进勇, 蔡跃明, 程乃平. 无线Ad hoc网络中一种基于网络编码的协同MAC协议. 电子与信息学报,

    12. [12]

      郝琨, 金志刚. 一种最小化编码节点的网络编码优化算法. 电子与信息学报,

    13. [13]

      黄学军, 朱洪波. 乘法运算的模拟网络编码中继方法. 电子与信息学报,

    14. [14]

      朱艺华, 唐春光, 田贤忠. 基于交叉流网络编码的节能路由. 电子与信息学报,

    15. [15]

      吕振兴, 许魁, 徐友云. 基于网络编码的III型HARQ无线广播跨层设计. 电子与信息学报,

    16. [16]

      杨奎武, 郭渊博, 马骏, 郑康锋. 基于网络编码的延迟容忍移动传感器网络低时延广播传输机制. 电子与信息学报,

    17. [17]

      季彦呈, 葛建华, 李靖. 一种协作网络编码方案的功率优化分配方法. 电子与信息学报,

    18. [18]

      淦明, 李辉. 一种基于自适应网络卷积编码的协作中继方法. 电子与信息学报,

    19. [19]

      池新生, 郑宝玉, 姚刚, 陈建白. 非对称协作分集通信中网络编码的应用. 电子与信息学报,

    20. [20]

      王斌, 吴伟仁, 岩延, 张宝贤. 效率感知的无线网络编码机制. 电子与信息学报,

  • 图 1  虚拟队列结构模型

    图 2  两个接收者的虚拟队列模型

    图 3  不同条件下吞吐量的变化

    图 4  不同输入率下队列的最大长度

    图 5  比较不同算法的最大输入率随着信道丢包率的变化

    图 6  网络中的编码率和发包率与输入率的关系

    图 7  吞吐量、平均等待时延与输入率和丢包率的关系

    表 1  3个接收者时的网络编码策略

    队列编号Q0Q1Q2Q3Q4Q5Q6
    索引集合{1, 2, 3}{1, 2}{2, 3}{1, 3}}{1}{2}{3}
    NC01000000
    NC10000111
    NC20100001
    NC30010100
    NC40001010
    下载: 导出CSV

    表 2  CSAT调度策略流程

     输入: 队列Qi(0 ≤ i ≤ 6), QT ={Qi|0 ≤ i ≤ 6},主队列为Q0,次队列为Qi(1 ≤ i ≤ 6), $P_i^h $表示队列Qi的队首数据包,索引集合为I={Ri|1
    i ≤ 3}, $I_i^h $表示Qi队首数据包的索引集合,Ri表示接收者i,编码方式表示为NCk(1 ≤ k ≤ 4),主次队列发送比为m/n,令flag1=
    0, flag2=0。
     输出:  每个队列的最大长度max(Qi),被所有接收者成功接收到的数据包的个数num,每个时隙发送数据包的个数的和sum。
     步骤 1 若QT 不为空,执行步骤2;否则等待数据包的到达;
     步骤 2 如果Q0不为空并且flag1<m,发送队列Q0的队首数据包$P_i^h $, flag1++,根据反馈消息更新该数据包的索引集合Ihi;否则跳转步骤4;
     步骤 3 如果$I_i^h $集合为空,$P_i^h $数据包被成功接收,离开该队列系统;如果$I_i^h $={R1, R2, R3}, $P_i^h $数据包没有被任何接收者接收,继续停留
    队列Qi,否则该数据包将根据其索引集合进入其他队列;
     步骤 4 如果次队列非空并且flag2<n,选择最先到达队列的数据包$P_i^h $,寻找满足该数据包的编码方式集合{NCk|1 ≤ k ≤ 4},否则跳转步骤1;
     步骤 5 如果有3个数据包参与编码的编码方式存在并且其它队列与之编码的数据包均存在,则以该编码方式发送数据包$P_i^h $, flag2++;否
    则执行步骤6;
     步骤 6 若其它队列存在数据包与之编码发送,则以该编码方式发送数据包$P_i^h $, flag2++;否则,以非编码的方式发送数据包$P_i^h $, flag2++;
     步骤 7 输出各个队列的最大长度max(Qi),被所有接收者接收到的数据包个数num以及每个时隙发送的数据包个数和sum。
    下载: 导出CSV

    表 3  在不同的丢包率下达到的最大输入率以及最优的主次队列发送比

    信道丢包率ε0.10.20.30.40.50.60.70.80.9
    主次比(m/n)9:18:28:27:36:45:57:37:37:3
    最大输入率(λ)0.890.790.690.590.490.390.30.20.1
    下载: 导出CSV
  • 加载中
图(7)表(3)
计量
  • PDF下载量:  20
  • 文章访问数:  460
  • HTML全文浏览量:  350
文章相关
  • 通讯作者:  张瑞, ruizhang@shu.edu.cn
  • 收稿日期:  2019-01-22
  • 录用日期:  2019-07-24
  • 网络出版日期:  2019-09-17
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章