多源多中繼無線網絡中基于隨機線性網絡編碼的調度方案

王 練 梁申虎 彭代淵

?

多源多中繼無線網絡中基于隨機線性網絡編碼的調度方案

王 練*①②梁申虎①彭代淵②

①(重慶郵電大學計算機科學與技術學院 重慶 400065)②(西南交通大學信息科學與技術學院 成都 611756)

現有多中繼無線網絡中傳輸調度方案主要針對單信源且轉發鏈路狀態相同的情況，多采用順序轉發的調度方式，傳輸效率較低。針對此問題，該文提出一種基于隨機線性網絡編碼的優先級調度方案。該方案在不同的傳輸階段，利用信息包接收狀態或編碼向量之間的線性關系生成反饋信息，計算中繼節點的有效信息包數。在轉發鏈路狀態不同的情況下，綜合考慮各中繼節點的有效信息與鏈路傳輸可靠性，確定優先級，從而完成調度。該方案實現了多中繼對多信源信息的協同轉發，在轉發鏈路狀態差異較大時，能自適應地選擇最優轉發節點和路徑，提高信息包的傳輸成功率。仿真結果表明，相比傳統基于單信源或順序調度的方案，該方案能有效提高網絡吞吐量，減少重傳次數。

無線網絡；隨機線性網絡編碼；調度；多源多中繼

1 引言

Ahlswede等人[1]在2000年提出了網絡編碼的思想，并證明其可以逼近最大理論傳輸容量。隨著研究的深入，網絡編碼被廣泛應用于無線網絡傳輸。其中，文獻[2-4]指出將網絡編碼應用于無線廣播重傳能有效提升無線傳輸吞吐量。中繼協作傳輸的應用實現了遠距離無線網絡的有效通信[5,6]。在此基礎上，Fan等人[7]率先研究了機會式網絡編碼在中繼協作多播中的應用，考慮了兩個接收端的情況。隨后，Lu等人[8,9]提出該場景下基于隨機線性網絡編碼(Random Linear Network Coding, RLNC)的高效調度方案，并將該方案拓展到雙小區廣播系統，Huang等人[10]改進此方案，以稀疏矩陣為基礎，采用確定性的算法獲取線性無關編碼向量，降低了編解碼復雜度。由于網絡節點的分布式特性，總可能出現多個信源同時傳輸信息。針對該情況，Amerimehr等人[11]對使用網絡編碼的雙向單中繼無線網絡調度進行了時延和吞吐量的分析，但只適合于兩者或兩者為一組的相互通信。Wei等人[12]提出一種多源多中繼無線網絡中計算與轉發的網絡編碼信道設計方案，用基于候選集的搜索算法確定網絡編碼系數，提高了網絡傳輸速率，對于調度只是概念性的涉及。Ding等人[13]提出了多中繼無線網絡中基于網絡編碼的自適應轉發調度(Adaptive Forwarding with Network Coding, AF-NC)和結合自動重傳請求(Automatic Repeat Quest, ARQ)的自適應轉發重傳調度(Adaptive Forwarding with Network Coding and Retransmission, AFR-NC)，減少了傳輸所需時隙，但該方案中的多中繼轉發和重傳均是采用順序調度，對給定的多源模型，也只是依次單獨執行各源節點的傳輸。Aslam等人[14]將多跳轉發抽象為馬爾科夫隨機過程，對使用隨機網絡編碼的多源多跳協作網絡的網絡覆蓋進行了研究，但要求每跳能夠解碼原始信息的節點不少于源節點數才能保證信息繼續傳輸。

上述多中繼調度方案多是基于順序轉發，但廣播會使多個中繼節點有相同的信息，若按該方法總會優先傳輸順序靠前的中繼節點所擁有的有效信息包，這并不是最理想的方式，傳輸成功率也會受到很大影響。此外，這些調度方案只適用于單信源且具有相同轉發鏈路狀態的網絡環境，與實際網絡傳輸有差異。在上述研究基礎上，本文研究了不同鏈路狀態下的多中繼協作傳輸，針對多信源信息在多中繼節點的轉發，以提高吞吐量和可靠性為目標，提出一種多源多中繼無線網絡中基于隨機線性網絡編碼的優先級調度方案(Priority Scheduling based on Network Coding, PSNC)。該方案根據不同的轉發鏈路狀態，通過預算有效信息包的最優到達數實現調度。為了驗證PSNC方案的有效性，本文對吞吐量和重傳次數進行了分析和仿真。結果表明，與基于網絡編碼的多中繼順序調度(Order Schedulingbased on Network Coding, OSNC)、基于網絡編碼的多中繼隨機轉發調度(Random Schedulingbased on Network Coding, RSNC)以及AF-NC方案相比，所提方案在一定條件下吞吐量和可靠性都具有明顯優勢。

2 網絡模型

PSNC方案分為初始階段和重傳階段。初始階段，所有源節點分別廣播信息包給中繼節點，中繼節點緩存收到的信息包；根據各中繼節點的信息包覆蓋數和各轉發鏈路的丟包率兩個條件進行初始調度，轉發有效信息給節點。在重傳階段，源節點根據反饋信息，重傳所有中繼節點都丟失的信息包；再利用節點和各個中繼節點的全局編碼矩陣之間的向量線性關系與不同的鏈路丟包率確定調度優先級，獲取重傳節點，并對該節點已經收到信息進行再次隨機編碼后發送給。兩個階段采用完全不同于現有方案的分階段反饋方式和預算優先級的調度策略。

圖1 系統模型

圖2的緩存結構

使用確定性網絡編碼時會采用接收狀態表征信息包接收情況，優點是簡單且易實現。本方案采用RLNC，在傳輸過程中可局部使用該表示方法，是由于沒有進入重傳階段前，所有已傳輸的原始編碼信息包都是唯一且確定的。因此，使本方案的編碼傳輸過程得到局部簡化。

3 優先級調度方案

PSNC方案是從各個中繼節點對源節點信息的覆蓋情況出發，利用節點與各中繼節點之間的原始信息接收差異以及各轉發鏈路的不同丟包率選取最優中繼傳輸點。其優勢主要體現在，整個傳輸方案都從多個源節點發送信息的角度出發，考慮多緩存隊列，使基于RLNC的傳輸方案變得簡單。此外，所有的轉發調度是建立在傳輸最優到達的選擇機制之上，充分利用網絡資源的同時提高傳輸吞吐量。本節主要的符號含義，如表1所示。

表1 符號的含義

符號含義 第個源節點 第個中繼節點 到的鏈路丟包率 中繼節點到的鏈路丟包率 的編碼矩陣 的編碼矩陣 中繼對原始信息的覆蓋 節點的接收狀態矩陣 兩個節點之間的接收狀態差異 節點能為提供的有效信息包數 中繼對第個源節點所發信息的覆蓋數 能為提供線性無關的編碼向量數

3.1 初始傳輸調度

根據各中繼節點的接收狀態矩陣了解相應的信息包接收情況，通過調度中繼節點將已經收到的信息包轉發給。在節點沒有接收到任何信息包之前，其接收狀態矩陣為的零矩陣。

定義1 所有中繼節點的接收狀態矩陣相對應元素進行邏輯或運算的結果表示中繼對原始信息的覆蓋。

定義2 兩個節點的狀態矩陣之差表示它們的信息包接收差異，即。

由式(2)可知，被選節點是所有候選節點中理論上能成功傳輸最多新信息包給的。被選節點完成轉發后，更新和候選節點集。根據變化結果重復調度步驟，獲取下一個轉發節點，直到與相等或候選節點集為空，就結束初始階段。由上文可知，已獲取的信息包不會再被后續節點轉發，避免了信息包的重復發送。通過調度，減少了參與轉發的中繼節點數，讓傳輸更集中，也更有效。初始傳輸調度的主要偽代碼如表2所示。

表2 初始調度主要偽代碼

輸入：輸出：//初始調度; //獲得對信息的覆蓋；; //初始為的零矩陣while(1)for ()//初始; //計算和的信息包差異由得出; //可提供的有效信息包數if ; //加入集合endifendfor; //獲得最佳轉發節點轉發a緩存的有效信息包；; //記錄轉發節點數更新；if ||Break;else; //去除已轉發的節點endifendwhile

3.2 重傳調度

完全覆蓋原始信息后的中繼節點，通過重傳調度，轉發有效信息給。此時，和各中繼節點已接收到各源節點的部分或全部信息。經過到的重傳，已經打破了初始階段的接收狀態反饋。根據文獻[15]可知RLNC是在有限域GF(28)內隨機選取編碼系數，生成兩個線性相關編碼包的概率可以小到忽略不計，而生成兩個相同編碼包的概率還要小很多，因此不能像確定性網絡編碼那樣，固定性地重傳丟失的那些信息包。那么，再發送確定性的反饋信息也就沒有意義，這也是RLNC最根本的特點。所以，在接下來的傳輸中將編碼向量之間的線性關系作為新的反饋信息。

(4)

(6)

在重傳之前，先再次編碼被選節點已有的信息。根據RLNC的原理，當接收節點的編碼矩陣達到滿秩則該矩陣可逆，就能實現完全解碼。對于中繼節點，若收到個編碼包后，對這些編碼包再次編碼并不能生成與原個編碼包線性無關的新編碼包。對應到向量，由原有的個線性無關向量隨機任意表示而成的新向量與原個向量一定存在線性相關關系。由此看來，重新編碼無實際意義。但當可以為節點提供線性無關信息包時，對中所有編碼包重新編碼后獲得的任意一個編碼包都能使增加1，促進解碼。因此，為了使重傳更有效，對被選節點原有的信息再次編碼后再發送。被選節點重傳后，若仍不能完全解碼，重復該調度過程獲取新的重傳節點，直到能完全解碼為止。重傳調度過程的主要偽代碼如表3所示。

當原始傳輸的文件很大時，同時處理多源節點的信息會對節點的資源提出更高的要求，為了保證有效的調度傳輸，采取分塊傳輸模式，將各源節點的文件分批次進行傳輸。

表3 重傳調度主要偽代碼

輸入：,輸入：//重傳調度while (不為全1矩陣)//未完全覆蓋for (); //所傳信息被覆蓋的數量if //的信息存在絕對丟失至少重傳個編碼包；endif根據接收包更新; //更新；endforendwhile//達到完全覆蓋；構建; //的編碼矩陣構建; //的編碼矩陣while ()//可完全解碼就結束for (); //能提供給的線性無關包數if ；endifendfor；再次編碼中的信息包；發送至少個編碼包給；更新；endwhile

4 性能分析

4.1 吞吐量

(8)

同理，若轉發數據包全部由丟包率最大的鏈路傳輸給接收端，再加上初始階段的所需傳輸時隙期望，可以得出的最大期望值。

4.2 重傳次數

重傳次數由兩部分構成，一是各中繼節點在初始階段未完全覆蓋原始信息，源節點重傳信息包達到該狀態的重傳次數；二是中繼節點重傳階段傳輸信息包的次數。因為本方案考慮同一鏈路上的重傳信息包和初始傳輸具有相同的丟包率，加上各轉發鏈路的狀態不同，使得轉發過程具有不確定性，所以無法給出所需重傳次數的準確表達式，只能通過仿真結果進行描述。

4.3 復雜度分析

表4 算法時間和空間復雜度

復雜度AF-NCOSNCRSNCPSNC 時間 空間

5 仿真結果

本文采用Matlab R2015a仿真軟件，測試計算機為Intel Core i7-5500U, 8 G RAM, Windows7操作系統。在此環境下，將本文PSNC方案與OSNC, RSNC以及AF-NC方案進行了仿真對比和分析。由于編碼系數的隨機性和信息包丟失的偶然性，導致相同條件下的兩次完整傳輸在吞吐量和重傳次數上可能有明顯差異。為了更準確地分析系統性能，采用平均吞吐量和平均重傳次數作為指標。根據仿真條件，設,，鏈路丟包率(,),,是一個隨機序列的丟包率數組。通過多次仿真實驗和數據處理后得到以下結果。

圖3(a)中，OSNC方案和AF-NC方案的吞吐量很接近，且明顯低于其他方案。而PSNC方案的吞吐量最大，因為同時考慮了中繼節點能否提供有效信息、提供多少有效信息和信息包傳輸到達率，使傳輸更集中，成功率更高。RSNC方案的吞吐量介于PSNC和AF-NC之間，原因在于隨機調度產生的結果肯定低于每次按最佳選擇的PSNC方案，基于順序轉發的OSNC和AF-NC方案極其依賴節點序列，而隨機調度使每次的結果或好或壞，但RSNC方案獲得較大吞吐量的概率要大，平均結果更好。

圖3(b)是各方案的平均重傳次數隨傳輸數據包數變化的對比結果。4種方案的平均重傳次數均隨原數據包數的增加而增加，當原數據包數為20時，各方案的平均重傳次數相差較??；而原數據包數增加到120時，PSNC的平均重傳次數明顯優于RSNC, AF-NC和OSNC方案。隨著原數據包數的增加PSNC的增加趨勢明顯緩和很多，優勢更加突出。在相同的條件下，PSNC會選擇低丟包率的鏈路進行轉發，從而減少丟失，所需重傳次數減少。

其他條件不變，平均吞吐量和平均重傳次數隨中繼節點數變化的對比如圖4所示，隨中繼節點數的增加，4種方案的吞吐量有所增大，而平均重傳次數不斷減少，最終都逐漸趨于平穩。說明一定范圍內，適當增加中繼節點數量可以減少數據包的絕對丟失，從而提高吞吐量，減少重傳次數。但系統性能由多個條件共同決定，中繼節點數所帶來的影響只是一定程度上的。

平均吞吐量和平均重傳次數隨轉發鏈路狀態差異變化(轉發鏈路丟包率的平均值和方差都增加，以方差和平均值的比值為橫坐標，表示轉發鏈路之間狀態差異在增大)的對比，如圖5所示。

從圖5(a)可看出，其他條件不變，各轉發鏈路狀態差異不斷增大時，由于丟包率的增加，使吞吐量整體呈現下降的趨勢，但PSNC方案的優勢會越來越明顯，下降的趨勢較為平緩。如圖5(b)所示，PSNC的平均重傳次數優勢也隨著鏈路狀態差異的增大而逐漸明顯，整體呈增加趨勢是由于丟包率是增大的。OSNC和AF-NC方案到后邊急劇上升主要是由于隨著丟包率和丟包率差異的增大使原本就存在劣勢被繼續放大，而RSNC方案的隨機方式在鏈路集不大的情況下不會持續出現極端劣勢。

6 結論

本文改進了多源多中繼無線網絡傳輸模型，基于隨機線性網絡編碼提出了優先級調度方案PSNC。該方案綜合考慮了節點的有效信息包數與鏈路傳輸可靠性，在轉發鏈路狀態不同的情況下，優先選擇有效信息包數較多且鏈路可靠性較高的節點傳輸信息，使傳輸更集中，更有效，從而提高信息包的傳輸成功率，減少反饋次數和傳輸次數。分析與仿真結果表明，PSNC具有吞吐量高，可靠性強的特點，使多源多中繼無線網絡協作傳輸性能得以明顯提升。特別在丟包率較高，轉發鏈路間狀態差異較大的無線網絡環境下，優勢會更加突出。該方案可推廣到移動通信網絡、Ad hoc網絡等。

圖3 不同原信息包個數下的性能對比

圖4 不同中繼節點個數下的性能對比

圖5 不同轉發鏈路狀態差異下的性能對比

[1] AHLSWEDE R, CAI N, LI S Y R,. Network information flow[J]., 2000, 46(4): 1204-1216. doi: 10.1109/18.850663.

[2] NGUYEN D, TRAN T, NGUYEN T,. Wireless broadcast using network coding[J]., 2009, 58(2): 914-925. doi: 10.1109/ TVT.2008.927729.

[3] 周志恒, 周亮. 多播網絡中基于網絡編碼的高效丟失恢復機制[J]. 電子與信息學報, 2012, 34(8): 1962-1967. doi: 10.3724/SP.J.1146.2011.01233.

ZHOU Zhiheng and ZHOU Liang. Efficient loss recovery based on network coding in multicast networks[J].&, 2012, 34(8): 1962-1967. doi: 10.3724/SP.J.1146.2011.01233.

[4] 茍亮, 張更新, 孫偉, 等. 無線網絡中基于機會網絡編碼的加權廣播重傳[J]. 電子與信息學報, 2014, 36(3): 749-753. doi: 10.3724/SP.J.1146.2013.00598.

GOU Liang, ZHANG Gengxin, SUN Wei,. Weighted broadcasting retransmission based on opportunistic network coding in wireless networks[J].&, 2014, 36(3): 749-753. doi: 10.3724/ SP.J.1146.2013.00598.

[5] KRAMER G, GASTPAR M, and GUPTA P. Cooperative strategies and capacity theorems for relay networks[J]., 2005, 51(9): 3037-3063. doi: 10.1109/TIT.2005.853304.

[6] LIANG Y and VEERAVALLI V V. Cooperative relay broadcast channels[J]., 2007, 53(3): 900-928. doi: 10.1109/TIT.2006.890726.

[7] FAN P, ZHI C, WEI C,. Reliable relay assisted wireless multicast using network coding[J]., 2009, 27(5): 749-762. doi: 10.1109/JSAC.2009.090615.

[8] LU L, XIAO M, RASMUSSEN L K,. Efficient scheduling for relay-aided broadcasting with random network codes[C]. 2011 IEEE 22nd International Symposium on Personal Indoor and Mobile Radio Communications, Toronto, Canada, 2011: 1815-1819. doi: 10.1109/PIMRC.2011. 6139821.

[9] LU L, SUN F, XIAO M,. Relay-aided multi-cell broadcasting with random network coding[C]. IEEE International Symposium on Information Theory and its Applications, Taichung, China, 2010: 957-962. doi: 10.1109/ ISITA. 2010.5649536.

[10] HUANG L and SUNG C W. Scheduling and network coding for relay-aided wireless broadcast: Optimality and heuristic[J]., 2014, 63(2): 674-687. doi:10.1109/TVT.2013.2281392.

[11] AMERIMEHR M H and ASHTANI F. Delay and throughput analysis of a two-way opportunistic network coding-based relay network[J]., 2014, 13(5): 2863-2873. doi: 10.1109/TWC. 2014.040914.121461.

[12] WEI L and CHEN W. Compute-and-forward network coding design over multi-source multi-relay channels[J]., 2012, 11(9): 3348-3357. doi: 10.1109/TWC.2012.070912.111948.

[13] DING L, Bi Y, SUN D,. Efficient scheduling with random network coding in multi-relay wireless network[J].(), 2014, 19(1): 59-64. doi: 10.1007/s12204-014-1475-9.

[14] ASLAM M A and HASSAN S A. Analysis of multi-source multi-hop cooperative networks employing network coding [C]. IEEE 81st Vehicular Technology Conference, Glasgow, United Kingdom, 2015: 1-5. doi: 10.1109/VTCSpring. 2015.7145700.

[15] HO T, MEDARD M, KOETTER R,. A random linear network coding approach to multicast[J]., 2006, 52(10): 4413-4430. doi: 10.1109/TIT.2006.881746.

Scheduling Scheme for Multi-source Multi-relay Wireless Network Based on Random Linear Network Coding

WANG Lian①②LIANG Shenhu①PENG Daiyuan②

①(,,400065,)②(,,611756,)

Current scheduling schemes in multi-relay wireless network mainly focuse on single source wireless network with the same link status. Furthermore, the sequential-forward scheduling scheme is used usually, and the transmission efficiency is comparatively low. To solve this problem, a priority scheduling scheme based on random linear network coding is proposed. In different transmission stages, the feedback information is generated according to the packets accepting state or the linear relation among the encoding vectors. The number of the effective packets of the corresponding relay node is calculated. In the condition of different link status, the effective information of each relay node and the link transmission reliability is taken into consideration comprehensively to generate the priority index and complete scheduling. This scheme can realize cooperation transmission in multi-relays for multi-sources information. When the link status difference is obvious, the optimal forwarding node and the path can be adaptively chosen to improve the information transmission efficiency. According to the simulation results, this scheme can effectively improve network throughput and reduce the number of retransmission compared with the traditional scheduling schemes for single source wireless network.

Wireless network; Random linear network coding; Scheduling; Multiple-source multiple-relay

TP393

A

1009-5896(2017)03-0532-07

10.11999/JEIT160454

2016-05-03；改回日期：2016-11-11；

2017-01-11

王練 wanglian@cqupt.edu.cn

國家高技術研究發展計劃(2015AA01A705)，國家自然科學基金(61571375)

The National High-Technology Research and Development Program of China (2015AA01A705), The National Natural Science Foundation of China (61571375)

王 練： 女，1976年生，博士生，副教授，研究方向為網絡編碼、無線網絡安全.

梁申虎： 男，1988年生，碩士生，研究方向為網絡編碼.