一種新的基于虛擬隊(duì)列的無(wú)線多播網(wǎng)絡(luò)編碼調(diào)度策略

張瑞; 占友; 錢權(quán)

doi:10.11999/JEIT190059

一種新的基于虛擬隊(duì)列的無(wú)線多播網(wǎng)絡(luò)編碼調(diào)度策略

doi: 10.11999/JEIT190059

上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院上海 200000

基金項(xiàng)目: 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2018YFB0704400, 2018YFB0704404)，新型網(wǎng)絡(luò)體系架構(gòu)與關(guān)鍵技術(shù)(2018B010113001)

詳細(xì)信息

作者簡(jiǎn)介:
張瑞：女，1981年生，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、無(wú)線網(wǎng)絡(luò)和網(wǎng)絡(luò)編碼等

占友：男，1993年生，碩士生，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)編碼

錢權(quán)：男，1972年生，研究員，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、網(wǎng)絡(luò)安全以及云計(jì)算、大數(shù)據(jù)分析和大規(guī)模分布式領(lǐng)域中的網(wǎng)絡(luò)環(huán)境

通訊作者:
張瑞　ruizhang@shu.edu.cn

中圖分類號(hào): TN919.31, TP393
計(jì)量
- 文章訪問(wèn)數(shù): 1917
- HTML全文瀏覽量: 982
- PDF下載量: 72
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-01-22
- 修回日期: 2019-07-24
- 網(wǎng)絡(luò)出版日期: 2019-09-17
- 刊出日期: 2020-02-19

New Coding Scheduling Strategy Based on Virtual Queuein Wireless Multicast Network

School of Computer Engineering and Science, Shanghai University, Shanghai 200000, China

Funds: The National Key Research and Development Program of China (2018YFB0704400, 2018YFB0704404), The New Network Architecture and Key Technologies (2018B010113001)

摘要

摘要:
網(wǎng)絡(luò)編碼由于其傳輸效率高的特性，近年來(lái)在無(wú)線多播網(wǎng)絡(luò)中得到廣泛的應(yīng)用。針對(duì)無(wú)線多播網(wǎng)絡(luò)中丟包自動(dòng)重傳效率低的問(wèn)題，該文提出一種新的基于虛擬隊(duì)列中數(shù)據(jù)包到達(dá)時(shí)間的編碼調(diào)度策略(CSAT)。在CSAT策略中，為了提高編碼效率，采用虛擬隊(duì)列來(lái)存放初始以及未被所有接收者接收到的數(shù)據(jù)包。考慮到隊(duì)列的穩(wěn)定性，CSAT策略按照一定的比率從主次隊(duì)列選擇發(fā)送；在次隊(duì)列發(fā)送數(shù)據(jù)包時(shí)，結(jié)合了編碼和非編碼兩種方式，根據(jù)數(shù)據(jù)包到達(dá)隊(duì)列的先后，選取能夠使較多數(shù)據(jù)包參與編碼的方式發(fā)送。仿真結(jié)果表明，該文所提的CSAT編碼調(diào)度策略在有效提高了數(shù)據(jù)包傳輸效率的同時(shí)，提高了網(wǎng)絡(luò)的吞吐量并降低了平均等待時(shí)延。
- 網(wǎng)絡(luò)編碼 /
- 虛擬隊(duì)列 /
- 無(wú)線多播網(wǎng)絡(luò) /
- 自動(dòng)重傳 /
- 吞吐量
Abstract:
Network coding is widely used in wireless multicast networks in recent years due to its high transmission efficiency. To address the low efficiency of automatic retransmission caused by packet loss in wireless multicast network, a new Coding Scheduling strategy based on Arriving Time (CSAT) in virtual queue is proposed. For improving encoding efficiency, virtual queues are used to store packets that are initially generated and not received by all receivers. Considering the stability of the queue, CSAT strategy chooses to send packet from the primary and secondary queue at a certain ratio. Both encoding and non-encoding methods are combined to send in the secondary queue. According to the arrival sequence of packets in the queue, the sending method that makes more packets participate in encoding is selected. Simulation results show that the proposed CSAT not only effectively improves packet transmission efficiency, but also improves network throughput and reduces average wait delay.
- Network coding /
- Virtual queue /
- Wireless multicast network /
- Automatic retransmission /
- Throughput

HTML全文

圖 1 虛擬隊(duì)列結(jié)構(gòu)模型

下載: 全尺寸圖片幻燈片

圖 2 兩個(gè)接收者的虛擬隊(duì)列模型

下載: 全尺寸圖片幻燈片

圖 3 不同條件下吞吐量的變化

下載: 全尺寸圖片幻燈片

圖 4 不同輸入率下隊(duì)列的最大長(zhǎng)度

下載: 全尺寸圖片幻燈片

圖 5 比較不同算法的最大輸入率隨著信道丟包率的變化

下載: 全尺寸圖片幻燈片

圖 6 網(wǎng)絡(luò)中的編碼率和發(fā)包率與輸入率的關(guān)系

下載: 全尺寸圖片幻燈片

圖 7 吞吐量、平均等待時(shí)延與輸入率和丟包率的關(guān)系

下載: 全尺寸圖片幻燈片

表 1 3個(gè)接收者時(shí)的網(wǎng)絡(luò)編碼策略

隊(duì)列編號(hào)	Q₀	Q₁	Q₂	Q₃	Q₄	Q₅	Q₆
索引集合	{1, 2, 3}	{1, 2}	{2, 3}	{1, 3}}	{1}	{2}	{3}
NC₀	1	0	0	0	0	0	0
NC₁	0	0	0	0	1	1	1
NC₂	0	1	0	0	0	0	1
NC₃	0	0	1	0	1	0	0
NC₄	0	0	0	1	0	1	0

下載: 導(dǎo)出CSV

表 2 CSAT調(diào)度策略流程

輸入：　隊(duì)列Q_i(0 ≤ i ≤ 6), Q_T={Q_i\|0 ≤ i ≤ 6}，主隊(duì)列為Q₀，次隊(duì)列為Q_i(1 ≤ i ≤ 6), $P_i^h $表示隊(duì)列Q_i的隊(duì)首數(shù)據(jù)包，索引集合為I={R_i\|1 ≤ i ≤ 3}, $I_i^h $表示Q_i隊(duì)首數(shù)據(jù)包的索引集合，R_i表示接收者i，編碼方式表示為NC_k(1 ≤ k ≤ 4)，主次隊(duì)列發(fā)送比為m/n，令flag1= 0, flag2=0。
輸出： ?每個(gè)隊(duì)列的最大長(zhǎng)度max(Q_i)，被所有接收者成功接收到的數(shù)據(jù)包的個(gè)數(shù)num，每個(gè)時(shí)隙發(fā)送數(shù)據(jù)包的個(gè)數(shù)的和sum。
步驟 1　若Q_T不為空，執(zhí)行步驟2；否則等待數(shù)據(jù)包的到達(dá)；
步驟 2　如果Q₀不為空并且flag1<m，發(fā)送隊(duì)列Q₀的隊(duì)首數(shù)據(jù)包$P_i^h $, flag1++，根據(jù)反饋消息更新該數(shù)據(jù)包的索引集合I^h_i；否則跳轉(zhuǎn)步驟4；
步驟 3　如果$I_i^h $集合為空，$P_i^h $數(shù)據(jù)包被成功接收，離開該隊(duì)列系統(tǒng)；如果$I_i^h $={R₁, R₂, R₃}, $P_i^h $數(shù)據(jù)包沒(méi)有被任何接收者接收，繼續(xù)停留隊(duì)列Q_i，否則該數(shù)據(jù)包將根據(jù)其索引集合進(jìn)入其他隊(duì)列；
步驟 4　如果次隊(duì)列非空并且flag2<n，選擇最先到達(dá)隊(duì)列的數(shù)據(jù)包$P_i^h $，尋找滿足該數(shù)據(jù)包的編碼方式集合{NC_k\|1 ≤ k ≤ 4}，否則跳轉(zhuǎn)步驟1；
步驟 5　如果有3個(gè)數(shù)據(jù)包參與編碼的編碼方式存在并且其它隊(duì)列與之編碼的數(shù)據(jù)包均存在，則以該編碼方式發(fā)送數(shù)據(jù)包$P_i^h $, flag2++；否則執(zhí)行步驟6；
步驟 6　若其它隊(duì)列存在數(shù)據(jù)包與之編碼發(fā)送，則以該編碼方式發(fā)送數(shù)據(jù)包$P_i^h $, flag2++；否則，以非編碼的方式發(fā)送數(shù)據(jù)包$P_i^h $, flag2++；
步驟 7　輸出各個(gè)隊(duì)列的最大長(zhǎng)度max(Q_i)，被所有接收者接收到的數(shù)據(jù)包個(gè)數(shù)num以及每個(gè)時(shí)隙發(fā)送的數(shù)據(jù)包個(gè)數(shù)和sum。

下載: 導(dǎo)出CSV

表 3 在不同的丟包率下達(dá)到的最大輸入率以及最優(yōu)的主次隊(duì)列發(fā)送比

信道丟包率ε	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
主次比(m/n)	9:1	8:2	8:2	7:3	6:4	5:5	7:3	7:3	7:3
最大輸入率(λ)	0.89	0.79	0.69	0.59	0.49	0.39	0.3	0.2	0.1

下載: 導(dǎo)出CSV

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

楊雅琴. 第二類Stirling數(shù)計(jì)算公式的一種證明[J]. 青島科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 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

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問(wèn)統(tǒng)計(jì)