高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于自适应随机线性网络编码的优先级调度方案

王练 张贺 张昭 张勋杨

王练, 张贺, 张昭, 张勋杨. 基于自适应随机线性网络编码的优先级调度方案[J]. 电子与信息学报, 2019, 41(8): 1861-1868. doi: 10.11999/JEIT180885
引用本文: 王练, 张贺, 张昭, 张勋杨. 基于自适应随机线性网络编码的优先级调度方案[J]. 电子与信息学报, 2019, 41(8): 1861-1868. doi: 10.11999/JEIT180885
Lian WANG, He ZHANG, Zhao ZHANG, Xunyang ZHANG. A Priority Scheduling Scheme Based on Adaptive Random Linear Network Coding[J]. Journal of Electronics & Information Technology, 2019, 41(8): 1861-1868. doi: 10.11999/JEIT180885
Citation: Lian WANG, He ZHANG, Zhao ZHANG, Xunyang ZHANG. A Priority Scheduling Scheme Based on Adaptive Random Linear Network Coding[J]. Journal of Electronics & Information Technology, 2019, 41(8): 1861-1868. doi: 10.11999/JEIT180885

基于自适应随机线性网络编码的优先级调度方案

doi: 10.11999/JEIT180885
基金项目: 国家自然科学基金(61876200, 61602073),国家重点研发计划(2018YFB0904900, 2018YFB0904905)
详细信息
    作者简介:

    王练:女,1976年生,博士,副教授,研究方向为网络编码,无线网络安全

    张贺:男,1991年生,硕士生,研究方向为网络编码

    张昭:男,1993年生,硕士生,研究方向为安全网络编码

    张勋杨:男,1993年生,硕士生,研究方向为网络编码

    通讯作者:

    王练 wanglian@cqupt.edu.cn

  • 中图分类号: TP393

A Priority Scheduling Scheme Based on Adaptive Random Linear Network Coding

Funds: National Natural Science Foundation of China (61876200, 61602073), National Key R&D Program of China (2018YFB0904900, 2018YFB0904905)
  • 摘要: 该文针对无线多播网络中基于随机线性网络编码(RLNC)调度方案计算复杂度高,且网络传输性能易受反馈信息影响等问题,提出一种基于自适应RLNC的优先级调度方案(PSARLNC)。该方案结合视频流的特征采用适应多播的RLNC,相较于传统RLNC计算复杂度降低。经过初始传输后,在后续数据恢复阶段,综合考虑数据包剩余传输时隙,选取目的节点增益最大传输方式,最大化数据传输。同时,各中继节点根据接收情况,构建各自解码概率值,并以此为依据确定调度优先级并完成转发,自适应调整各节点传输,有效减少对反馈信息的依赖。仿真结果表明该方案与完全反馈方案性能十分接近,且在减小计算复杂度和降低对反馈信息依赖同时保证了较好的性能。
  • 图  1  系统模型图

    图  2  ${R_i}$的状态记录表

    图  3  接收概率相同的两个中继情况

    图  4  平均解码层数随传输时隙的变化

    图  5  反馈开销比随传输时隙的变化

    图  6  平均解码层数随中继节点的变化

    图  7  反馈开销比随中继节点的变化

    图  8  平均解码层数随数据包数的变化

    图  9  反馈开销比随数据包数的变化

    表  1  主要符号含义

    符号含义
    $S$源节点
    $R_i$第$i$个中继节点
    ${P_{S{R_i}}}$$S$到$R_i$链路丢包率
    ${P_{{R_i}D}}$$R_i$到$D$链路丢包率
    ${{C}_{Rf}}$中继对传输信息的覆盖
    ${{{G}}_n}$信源生成的第$n$代数据包
    $T\;$系统所允许传输时限
    ${{R}^*}$根据中继选择算法所选中继集合
    下载: 导出CSV

    表  2  传输调度伪代码

     输入:$x$,${{C}}_{{R_1}},{{{C}}_{{R_2}}}, ·\!·\!· ,{{C}}_{{R_N}}$
     输出:$C_D$
     //调度过程
     ${{C}_{{R_f}}} = {{C}}_{{R_1}} \vee {{C}}_{{R_2}} \vee ·\!·\!· \vee {{C}}_{{R_N}}$;//获得${{R}}$对信息的覆盖${{C}_{{R_f}}}$
     $n \leftarrow 0$;
     ${{U}} = \varnothing $;
     for ($m = 1,2, ·\!·\!· ,\operatorname{length} ({{C}_{{R_f}}})$)//
      if ${{C}_{{R_f}}}(m) = = 0$ //如果对应包丢失
       ${{U}} = {{U}} \cup m$ //将$m$加入到集合${{U}}$中
       由${{U}}$得出连续最大代号$n$
      end if
     end for
     if $n \ge x$
       while $x > 0$
        运行中继节点调度算法;
        $x \leftarrow x - 1$;
       end while
     end if
     while $n < x$
        源节点发送数据包;
        $x \leftarrow x - 1$;
        if $n = x$
         break;
        end if
      end while
     while $x > 0$
        运行中继节点调度算法;
     end while
    下载: 导出CSV

    表  3  中继节点调度主要伪代码

     输入:$x$,${{C}}_{{R_1}},{{{C}}_{{R_2}}}, ·\!·\!· ,{{C}}_{{R_N}}$
     输出:${R^*}$
     //中继调度
     $k \leftarrow 0$;
     $P \leftarrow 0$;
     $I \leftarrow 0$;
     while $x > 0$
      for ($m = 1,2, ·\!·\!· ,\operatorname{length} ({{R}^{\rm{t}}})$) //初始${{R}^{\rm{t}}} = \{ {R_1},{R_2}, ·\!·\!· ,{R_N}\} $
       for $n = 1:L$
        if $(m,n) \ne 0$
         $k \leftarrow k + 1$;
         $P \leftarrow P + n$;
         $I \leftarrow 1/P$;//获得中继权值
        end if
       end for
      end for
      ${{R}^*} \leftarrow \arg \max \left\{ I \cdot \prod {_{l = 1}^L {C}_L^k{{(1 - {P_{S{R_i}}})}^k}{P_{S{R_i}}}^{L - k} \cdot } {P_{{R_i}D}}\right\} $ //获得
    转发中继节点中继转发数据包;
      $x \leftarrow x - 1$;
      ${{R}^{\rm{t}}} \leftarrow {{R}^t}{\rm{ - }}{{R}^*}$;//去除已转发的中继节点
     end while
    下载: 导出CSV
  • 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
    KOETTER R and MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782–795. doi: 10.1109/TNET.2003.818197
    LI S Y R, YEUNG R W, and CAI Ning. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371–381. doi: 10.1109/tit.2002.807285
    苟亮, 张更新, 孙伟, 等. 无线网络中基于机会网络编码的加权广播重传[J]. 电子与信息学报, 2014, 36(3): 749–753. doi: 10.3724/SP.J.1146.2013.00598

    GOU Liang, ZHANG Gengxin, SUN Wei, et al. Weighted broadcasting retransmission based on opportunistic network coding in wireless networks[J]. Journal of Electronics &Information Technology, 2014, 36(3): 749–753. doi: 10.3724/SP.J.1146.2013.00598
    HO T, KOETTER R, MEDARD M, et al. The benefits of coding over routing in a randomized setting[C]. IEEE International Symposium on Information Theory Proceedings, Yokohama, Japan, 2003: 442.
    TSOKALO I, GABRIEL F, PANDI S, et al. Reliable feedback mechanisms for routing protocols with network coding[C]. IEEE International Symposium on Power Line Communications and ITS Applications, Manchester, UK, 2018: 1–7.
    NGETH R, KURKOSKI B M, LIM Y, et al. Random linear network coding over compute-and-forward in multi-source multi-relay networks[C]. The 13th International Wireless Communications and Mobile Computing Conference, Valencia, Spain, 2017: 805–810.
    HO T, MEDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413–4430. doi: 10.1109/tit.2006.881746
    WANG M and LI Baochun. R2: Random push with random network coding in live peer-to-peer streaming[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(9): 1655–1666. doi: 10.1109/JSAC.2007.071205
    SORENSEN C W, LUCANI D E, FITZEK F H P, et al. On-the-fly overlapping of sparse generations: A tunable sparse network coding perspective[C]. The 80th Vehicular Technology Conference, Vancouver, Canada, 2014: 1–5.
    ZHAN Cheng and GAO Kailun. Video delivery in heterogeneous wireless networks with network coding[J]. IEEE Wireless Communications Letters, 2016, 5(5): 472–475. doi: 10.1109/LWC.2016.2586485
    TASSI A, CHATZIGEORGIOU I, and LUCANI D E. Analysis and optimization of sparse random linear network coding for reliable multicast services[J]. IEEE Transactions on Communications, 2016, 64(1): 285–299. doi: 10.1109/TCOMM.2015.2503398
    LI Bin, LI Hongxiang, and ZHANG Ruonan. Adaptive random network coding for multicasting hard-deadline-constrained prioritized data[J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 8739–8744. doi: 10.1109/TVT.2015.2509503
    LI Bin, BAN Dengke, and ZHANG Ruonan. Efficient scheduling for multicasting multimedia data with adaptive random liner network coding in relay-aided network[C]. 2015 Wireless Communications and Networking Conference, New Orleans, USA, 2015: 1584–1589.
    LI Bin, LI Xiaoping, ZHANG Ruonan, et al. Joint power allocation and adaptive random network coding in wireless multicast networks[J]. IEEE Transactions on Communications, 2018, 66(4): 1520–1533. doi: 10.1109/tcomm.2017.2785238
    YU Mingchao, SADEGHI P, and SPRINTSON A. Feedback-assisted random linear network coding in wireless broadcast[C]. 2016 IEEE GLOBECOM Workshops, Washington, USA, 2017: 1–6.
    ESMAEILZADEH M, SADEGHI P, and ABOUTORAB N. Random linear network coding for wireless layered video broadcast: General design methods for adaptive feedback-free transmission[J]. IEEE Transactions on Communications, 2017, 65(2): 790–805. doi: 10.1109/tcomm.2016.2630062
    GARRIDO P, LUCANI D E, and AGÜERO R. Markov chain model for the decoding probability of sparse network coding[J]. IEEE Transactions on Communications, 2017, 65(4): 1675–1685. doi: 10.1109/TCOMM.2017.2657621
    FEIZI S, LUCANI D E, SØRENSEN C W, et al. Tunable sparse network coding for multicast networks[C]. 2014 International Symposium on Network Coding (NetCod), Aalborg, Denmark, 2014.
  • 加载中
图(9) / 表(3)
计量
  • 文章访问数:  2225
  • HTML全文浏览量:  744
  • PDF下载量:  59
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-09-18
  • 修回日期:  2019-02-20
  • 网络出版日期:  2019-03-04
  • 刊出日期:  2019-08-01

目录

    /

    返回文章
    返回