A Priority Scheduling Scheme Based on Adaptive Random Linear Network Coding
-
摘要: 该文针对无线多播网络中基于随机线性网络编码(RLNC)调度方案计算复杂度高，且网络传输性能易受反馈信息影响等问题，提出一种基于自适应RLNC的优先级调度方案(PSARLNC)。该方案结合视频流的特征采用适应多播的RLNC，相较于传统RLNC计算复杂度降低。经过初始传输后，在后续数据恢复阶段，综合考虑数据包剩余传输时隙，选取目的节点增益最大传输方式，最大化数据传输。同时，各中继节点根据接收情况，构建各自解码概率值，并以此为依据确定调度优先级并完成转发，自适应调整各节点传输，有效减少对反馈信息的依赖。仿真结果表明该方案与完全反馈方案性能十分接近，且在减小计算复杂度和降低对反馈信息依赖同时保证了较好的性能。Abstract: A Priority Scheduling scheme based on Adaptive Random Linear Network Coding (PSARLNC) is proposed, to avoid the high computation complexity of the scheduling scheme based on Random Linear Network Coding (RLNC) and the high feedback dependence of the network performance. The characteristics of the video stream and RLNC adapted to multicast are combined in this scheme. Compared with the traditional RLNC, the computation complexity of this scheme is reduced. After the initial transmission, the transmission slots left of the data packet are comprehensively considered in the subsequent data recovery phase, and the maximum transmission node of the destination node gain is selected to maximize data transmission. At the same time, the decoding probability is available according to the different receiving situations in each relay node. According to the decoding probability value, the scheduling priority is determined, and the forwarding is completed. The transmission of each node is adaptively adjusted, and the feedback information is effectively reduced. The simulation results show that the performance of this scheme is approached to the full-feedback scheme, with better performance in the reducing computational complexity and the decreasing feedback dependence.
-
Key words:
- Wireless multicast network /
- Random Linear Network Coding(RLNC) /
- Multi-relay /
- Scheduling /
- Feedback
-
表 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.00598GOU 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)
计量
- 文章访问数: 2156
- HTML全文浏览量: 692
- PDF下载量: 58
- 被引次数: 0
