基于自適應(yīng)隨機(jī)線性網(wǎng)絡(luò)編碼的優(yōu)先級調(diào)度方案

王練; 張賀; 張昭; 張勛楊

doi:10.11999/JEIT180885

基于自適應(yīng)隨機(jī)線性網(wǎng)絡(luò)編碼的優(yōu)先級調(diào)度方案

doi: 10.11999/JEIT180885

重慶郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 ??重慶 ??400065

基金項目: 國家自然科學(xué)基金(61876200, 61602073)，國家重點(diǎn)研發(fā)計劃(2018YFB0904900, 2018YFB0904905)

詳細(xì)信息

作者簡介:
王練：女，1976年生，博士，副教授，研究方向為網(wǎng)絡(luò)編碼，無線網(wǎng)絡(luò)安全

張賀：男，1991年生，碩士生，研究方向為網(wǎng)絡(luò)編碼

張昭：男，1993年生，碩士生，研究方向為安全網(wǎng)絡(luò)編碼

張勛楊：男，1993年生，碩士生，研究方向為網(wǎng)絡(luò)編碼

通訊作者:
王練　wanglian@cqupt.edu.cn

中圖分類號: TP393
計量
- 文章訪問數(shù): 2282
- HTML全文瀏覽量: 767
- PDF下載量: 61
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-09-18
- 修回日期: 2019-02-20
- 網(wǎng)絡(luò)出版日期: 2019-03-04
- 刊出日期: 2019-08-01

A Priority Scheduling Scheme Based on Adaptive Random Linear Network Coding

School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Funds: National Natural Science Foundation of China (61876200, 61602073), National Key R&D Program of China (2018YFB0904900, 2018YFB0904905)

摘要

摘要: 該文針對無線多播網(wǎng)絡(luò)中基于隨機(jī)線性網(wǎng)絡(luò)編碼(RLNC)調(diào)度方案計算復(fù)雜度高，且網(wǎng)絡(luò)傳輸性能易受反饋信息影響等問題，提出一種基于自適應(yīng)RLNC的優(yōu)先級調(diào)度方案(PSARLNC)。該方案結(jié)合視頻流的特征采用適應(yīng)多播的RLNC，相較于傳統(tǒng)RLNC計算復(fù)雜度降低。經(jīng)過初始傳輸后，在后續(xù)數(shù)據(jù)恢復(fù)階段，綜合考慮數(shù)據(jù)包剩余傳輸時隙，選取目的節(jié)點(diǎn)增益最大傳輸方式，最大化數(shù)據(jù)傳輸。同時，各中繼節(jié)點(diǎn)根據(jù)接收情況，構(gòu)建各自解碼概率值，并以此為依據(jù)確定調(diào)度優(yōu)先級并完成轉(zhuǎn)發(fā)，自適應(yīng)調(diào)整各節(jié)點(diǎn)傳輸，有效減少對反饋信息的依賴。仿真結(jié)果表明該方案與完全反饋方案性能十分接近，且在減小計算復(fù)雜度和降低對反饋信息依賴同時保證了較好的性能。
- 無線多播網(wǎng)絡(luò) /
- 隨機(jī)線性網(wǎng)絡(luò)編碼 /
- 多中繼 /
- 調(diào)度 /
- 反饋
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.
- Wireless multicast network /
- Random Linear Network Coding(RLNC) /
- Multi-relay /
- Scheduling /
- Feedback

HTML全文

圖 1 系統(tǒng)模型圖

下載: 全尺寸圖片幻燈片

圖 2 ${R_i}$的狀態(tài)記錄表

下載: 全尺寸圖片幻燈片

圖 3 接收概率相同的兩個中繼情況

下載: 全尺寸圖片幻燈片

圖 4 平均解碼層數(shù)隨傳輸時隙的變化

下載: 全尺寸圖片幻燈片

圖 5 反饋開銷比隨傳輸時隙的變化

下載: 全尺寸圖片幻燈片

圖 6 平均解碼層數(shù)隨中繼節(jié)點(diǎn)的變化

下載: 全尺寸圖片幻燈片

圖 7 反饋開銷比隨中繼節(jié)點(diǎn)的變化

下載: 全尺寸圖片幻燈片

圖 8 平均解碼層數(shù)隨數(shù)據(jù)包數(shù)的變化

下載: 全尺寸圖片幻燈片

圖 9 反饋開銷比隨數(shù)據(jù)包數(shù)的變化

下載: 全尺寸圖片幻燈片

表 1 主要符號含義

符號		含義
$S$		源節(jié)點(diǎn)
$R_i$		第$i$個中繼節(jié)點(diǎn)
${P_{S{R_i}}}$		$S$到$R_i$鏈路丟包率
${P_{{R_i}D}}$		$R_i$到$D$鏈路丟包率
${{C}_{Rf}}$		中繼對傳輸信息的覆蓋
${{{G}}_n}$		信源生成的第$n$代數(shù)據(jù)包
$T\;$		系統(tǒng)所允許傳輸時限
${{R}^*}$		根據(jù)中繼選擇算法所選中繼集合

下載: 導(dǎo)出CSV

表 2 傳輸調(diào)度偽代碼

　輸入：$x$,${{C}}_{{R_1}},{{{C}}_{{R_2}}}, ·\!·\!· ,{{C}}_{{R_N}}$

　輸出：$C_D$

　//調(diào)度過程

　${{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$ //如果對應(yīng)包丟失

　　　${{U}} = {{U}} \cup m$ //將$m$加入到集合${{U}}$中

　　　由${{U}}$得出連續(xù)最大代號$n$

　　end if

　end for

　if $n \ge x$

　　　while $x > 0$

　　　　運(yùn)行中繼節(jié)點(diǎn)調(diào)度算法；

　　　　$x \leftarrow x - 1$；

　　　end while

　end if

　while $n < x$

　　　　源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包；

　　　　$x \leftarrow x - 1$；

　　　　if $n = x$

　　　　　break；

　　　　end if

　　end while

　while $x > 0$

　　　　運(yùn)行中繼節(jié)點(diǎn)調(diào)度算法；

　end while

下載: 導(dǎo)出CSV

表 3 中繼節(jié)點(diǎn)調(diào)度主要偽代碼

　輸入：$x$,${{C}}_{{R_1}},{{{C}}_{{R_2}}}, ·\!·\!· ,{{C}}_{{R_N}}$

　輸出：${R^*}$

　//中繼調(diào)度

　$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$；//獲得中繼權(quán)值

　　　　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\} $ //獲得
轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)中繼轉(zhuǎn)發(fā)數(shù)據(jù)包；

　　$x \leftarrow x - 1$；

　　${{R}^{\rm{t}}} \leftarrow {{R}^t}{\rm{ - }}{{R}^*}$；//去除已轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)

　end while

下載: 導(dǎo)出CSV

參考文獻(xiàn)(19)

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

茍亮, 張更新, 孫偉, 等. 無線網(wǎng)絡(luò)中基于機(jī)會網(wǎng)絡(luò)編碼的加權(quán)廣播重傳[J]. 電子與信息學(xué)報, 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計