王鵬飛 張冬梅 許 魁 徐健卉

(解放軍陸軍工程大學通信工程學院, 江蘇南京 210007)

1 引言

伴隨著多媒體業(yè)務的興起以及智能終端設備的普及,移動數(shù)據(jù)流量將迎來爆發(fā)性增長[1]。海量的設備接入使得現(xiàn)有的蜂窩網(wǎng)絡變得越來越擁擠,從而惡化服務質量(Quality of Service,QoS)和降低用戶體驗(Quality of Experience,QoE)。與此同時,隨著終端設備在計算、存儲與連接方面的能力不斷提高,D2D(Device-to-Device)技術[2-3]有望滿足下一代無線通信網(wǎng)絡中不斷增長的吞吐量需求。D2D技術允許終端設備配備雙接口:一個接口使用遠程無線通信技術(如WLAN、LTE等)與基站連接;另一個接口使用短距離無線通信技術(如WiFi、藍牙等)與其他設備直接通信。鑒于蜂窩和D2D鏈路可以使用不同頻段同時運行,這樣的系統(tǒng)能夠極大地減輕基站負載,增加網(wǎng)絡的吞吐量和能量效率。

受益于無線通信的廣播性質,通過對不同的源數(shù)據(jù)包進行編碼合并,網(wǎng)絡編碼技術[4-5]可以有效地提高系統(tǒng)吞吐量和減少傳輸延遲。由于上述優(yōu)勢,無線廣播網(wǎng)絡中基于網(wǎng)絡編碼的數(shù)據(jù)傳輸已成為近年來的熱門話題。目前主要的網(wǎng)絡編碼策略有如下兩類:隨機線性網(wǎng)絡編碼(Random Linear Network Coding,RLNC)[6- 8]與立即可譯網(wǎng)絡編碼(Instantly Decodable Network Coding,IDNC)[9-11]。RLNC策略在提升吞吐量性能方面有著顯著優(yōu)勢,但是其缺點也很明顯:對于要求低譯碼時延的應用來說,RLNC難以滿足要求,因為它不支持數(shù)據(jù)包的逐個解碼。此外,譯碼過程(矩陣求逆)帶來的的高復雜度也不可避免。相比之下,盡管在吞吐量方面的提升不如RLNC,IDNC策略的優(yōu)勢在于編解碼操作簡單,支持數(shù)據(jù)包逐個解碼,能夠極大地降低譯碼時延。

網(wǎng)絡編碼最初應用于基站集中式的廣播/多播網(wǎng)絡[12-14],現(xiàn)有文獻表明,結合D2D技術可以進一步的提高系統(tǒng)性能[15-19]。文獻[15-16]分別針對基于D2D的無線廣播場景提出了隨機性和確定性算法,以最小化傳輸次數(shù)。文獻[17]結合IDNC 策略與D2D技術,旨在提高數(shù)據(jù)合作交換系統(tǒng)中的傳輸效率,降低譯碼時延。文獻[18]考慮不同數(shù)據(jù)對于視頻質量的貢獻來設計編碼策略,提出了一種聯(lián)合發(fā)送設備與數(shù)據(jù)包的選擇算法,使每個傳輸時隙后的整體視頻質量達到最大。文獻[19]研究了基于網(wǎng)絡編碼的實時視頻序列廣播問題,考慮數(shù)據(jù)傳輸具有截止時間的限制。然而,上述研究都是基于設備使用單個接口的場景,即在傳輸階段每次只能收到一個數(shù)據(jù)包(通過蜂窩鏈路或者D2D鏈路),針對設備配備雙接口,在數(shù)據(jù)包重傳階段聯(lián)合使用蜂窩與D2D鏈路的研究很少。

綜上所述,本文考慮設備配備有雙接口的網(wǎng)絡編碼廣播(Network coding for dual interfaces,NCDI)場景,重傳階段可以同時利用蜂窩與D2D鏈路恢復丟失數(shù)據(jù)包。在此場景下,結合網(wǎng)絡編碼技術可以提高系統(tǒng)吞吐量,聯(lián)合利用蜂窩與D2D鏈路能夠進一步的提高傳輸效率。然而,如何合理的進行編碼調度,充分發(fā)揮網(wǎng)絡編碼的潛力顯得至關重要。因此,文章旨在設計聯(lián)合蜂窩與D2D鏈路進行調度的網(wǎng)絡編碼廣播重傳方案,主要貢獻如下:

本文主要研究重傳階段NCDI方案的設計,通過分析與推導,我們首先給出了重傳次數(shù)的理論下限。

其次,針對RLNC策略下的聯(lián)合蜂窩與D2D鏈路調度,提出了NCDI-RLNC方案;針對IDNC策略下的聯(lián)合蜂窩與D2D鏈路調度,構建了用于表示所有編碼組合的IDNC圖,并給出了基于最大權重團搜尋的NCDI-IDNC方案。

不同條件(設備數(shù)量、數(shù)據(jù)包數(shù)目、以及鏈路丟包概率)下的仿真結果表明所提方案能夠極大地提高重傳效率,減少重傳次數(shù)。

2 系統(tǒng)模型

圖1 無線廣播網(wǎng)絡示意圖Fig.1 Example for wireless broadcast network

假設設備之間彼此鄰近,每個設備都屬于其他設備的傳輸覆蓋區(qū)域內(nèi),從而構成了一個完全連接的D2D網(wǎng)絡。因此,為避免D2D鏈路產(chǎn)生干擾,每個時隙只允許單個設備在D2D通信頻譜中進行廣播傳輸,而其余設備都處于偵聽狀態(tài)。此外,文中將物理信道的條件(例如衰落,陰影,信道估計誤差等)抽象為數(shù)據(jù)包能否成功接收,以擦除(丟包)概率來衡量信道條件,并假設各擦除信道之間彼此獨立。其中,基站到設備Ri之間的丟包概率表示為δi,設備Ri與Rj之間的丟包概率表示為δi, j,且假設δi, j=δj,i。

重傳階段,為迅速恢復丟失數(shù)據(jù)包的同時減輕基站負載,設備同時使用雙接口,聯(lián)合利用蜂窩鏈路與D2D鏈路進行重傳。換句話說,設備在每個重傳時隙最多能收到兩個編碼包,分別來自于基站與發(fā)送設備。重復上述“編碼—重傳—更新狀態(tài)信息”過程,直到所有設備都能正確接收到N個源數(shù)據(jù)包。

例 1 以圖1為例說明聯(lián)合蜂窩與D2D鏈路進行重傳的優(yōu)勢?；緦⑺膫€數(shù)據(jù)包{P1,P2,P3,P4}廣播給終端設備{A,B,C},設備將正確接收到的數(shù)據(jù)包放入緩存中。重傳時假設無“丟包”的理想信道,考慮只使用蜂窩鏈路進行數(shù)據(jù)包恢復重傳,基站依次重傳編碼包P1⊕P2⊕P3和P4,用戶需要兩個時隙能接收到完整數(shù)據(jù);考慮只使用D2D鏈路進行合作恢復重傳,設備A廣播編碼包P3⊕P4、設備B廣播編碼包P1⊕P2,兩次重傳后所有設備能夠恢復丟失數(shù)據(jù)包。然而,考慮在重傳階段聯(lián)合蜂窩與D2D鏈路進行調度,基站廣播編碼包P1⊕P2的同時用戶A廣播編碼包P3⊕P4,則傳輸次數(shù)可以減少為一次,進一步提高了重傳效率。

為了更有效地利用有限資源(如設備的能量、帶寬等),減少重傳次數(shù),我們需要在每個時隙做出最佳的調度決策。因此,本文的重點是設計和開發(fā)高效的網(wǎng)絡編碼調度方案,并對其吞吐量性能進行研究。

定義 1 重傳次數(shù)T—由于無線廣播信道的“丟包”影響,廣播階段結束后,用戶只能接收到部分數(shù)據(jù)包,我們將設備恢復所有數(shù)據(jù)包所需的傳輸時隙定義為重傳次數(shù)。

3 重傳次數(shù)下界

本節(jié)我們將給出重傳次數(shù)的下界,其反映了在理想情況下,設備同時利用蜂窩與D2D通信接口來恢復丟失數(shù)據(jù)包所需的最小重傳次數(shù)Tlb。值得注意的是,文章推出的下限并不一定保證能夠達到,但是它保證沒有其他任何方案可以優(yōu)于此下界。為了評估所提方案的有效性,可以將此下界視為一個很好的度量。

(1)

若系統(tǒng)中存在多個設備,那么系統(tǒng)總的重傳次數(shù)由所需重傳次數(shù)最大的設備決定,可表示為:

(2)

(3)

綜上所述,且考慮重傳次數(shù)為整數(shù)值,得出設備恢復所有丟失數(shù)據(jù)包的重傳次數(shù)下界為:

Tlb≥

(4)

4 方案描述

為充分發(fā)揮網(wǎng)絡編碼增益,最小化重傳次數(shù),基站需要充分利用收集到的數(shù)據(jù)包狀態(tài)信息,在每個時隙做出最優(yōu)調度決策。為此,本節(jié)針對隨機線性網(wǎng)絡編碼(RLNC)與立即可譯網(wǎng)絡編碼(IDNC)兩種不同的編碼策略,分別提出了NCDI-RLNC和NCDI-IDNC方案。

4.1 NCDI-RLNC方案

定義 3 有效編碼包—當設備接收到一個編碼包時,首先判斷該編碼包是否包含其丟失數(shù)據(jù)包的信息,我們將滿足此條件的編碼包稱為有效編碼包。換句話說,也就是判斷該編碼包是否與設備已有的數(shù)據(jù)包線性獨立,能否幫助設備解碼出丟失數(shù)據(jù)包。

表1 NCDI-RLNC方案調度流程

4.2 NCDI-IDNC方案

針對IDNC策略,本小節(jié)給出了基于最大權重團搜尋的NCDI-IDNC編碼調度方案。不同于RLNC,IDNC的核心思想為發(fā)送端對數(shù)據(jù)包采用簡單的異或(XOR)操作,以接收端直接可譯為目標進行編碼,無法譯碼的編碼包直接丟棄,不再用于后續(xù)譯碼過程中。因而,NCDI-IDNC方案更適用于要求數(shù)據(jù)包逐個解碼的實時多媒體應用。

(1)j=l,設備Ri與設備Rk需要同一個數(shù)據(jù)包Pj=Pl;

圖2 基站及設備A側的IDNC圖示例Fig.2 Example of IDNC Graph (a) IDNC Graph (b) IDNC Graph of Device A

對于NCDI場景下的廣播重傳,每個時隙我們需要確定兩個最佳編碼包,分別來自于蜂窩鏈路與D2D鏈路,使盡可能多的用戶能夠從中解碼出丟失數(shù)據(jù)包。表2中給出了NCDI-IDNC方案的具體調度流程,其核心思想在于分兩階段依次找出基站端與設備端的最大權重團CB、CD。其中,CB對應的編碼包由基站通過蜂窩鏈路廣播給所有設備,CD對應的編碼包由發(fā)送設備通過D2D鏈路廣播給其余設備。具體步驟描述如下:

表2 NCDI-IDNC方案調度流程

5 開銷與復雜度分析

5.1 通信開銷

文中系統(tǒng)采用基站集中控制的方式,即在每個時隙,基站依據(jù)收集到的反饋信息做出調度決策,并且將決策廣播給相應的D2D發(fā)送設備。因而,在實際環(huán)境下,重傳階段每個時隙的額外開銷主要由三個部分組成:發(fā)送決策信息的開銷,收集反饋信息的開銷以及編碼系數(shù)的包頭開銷。

對于NCDI-RLNC方案而言,重傳階段,基站選取一個設備作為D2D鏈路中的發(fā)送設備,該設備向其余設備廣播其已有數(shù)據(jù)包的線性組合。因而決策信息僅需要1比特,以告知該設備是否作為發(fā)送設備。其次,兩個RLNC編碼包分別由基站與設備廣播,編碼系數(shù)的包頭開銷為2Nlog(F)比特。最后,由于基站需要根據(jù)各個設備反饋的數(shù)據(jù)包接收狀態(tài)以便做出下一時隙的調度決策,設備需要向基站反饋接收狀態(tài)信息,指示兩個接口中的每一個接收/丟失數(shù)據(jù)包。每個設備需要使用2比特來確認兩個接收/丟失的數(shù)據(jù)包,對于網(wǎng)絡中的M個設備而言,收集反饋信息的開銷為2M比特。因此,重傳階段采用NCDI-RLNC方案的通信開銷為1+2Nlog(F)+2M比特每時隙。

對于NCDI-IDNC方案而言,每個時隙基站需要確定發(fā)送設備以及該設備需要廣播的編碼組合。實際上,一個IDNC編碼包最多由N個數(shù)據(jù)包異或,因此發(fā)送的決策信息包含N比特。由于IDNC策略采用的是二進制編碼,兩個IDNC編碼包的包頭開銷可視為2N比特。同樣,用于收集反饋信息的開銷為2M比特。綜上,重傳階段采用NCDI-IDNC方案的通信開銷為3N+2M比特每時隙。

5.2 計算復雜度

對于NCDI-RLNC方案來說,基站側構建編碼包的復雜度為O(N);計算設備作為發(fā)送設備時可提供的有效編碼包數(shù)量,其復雜度為O(M-1);對每個設備都重復此操作,從而選出發(fā)送設備的復雜度為O(M(M-1));設備側構建編碼包的復雜度為O(N)。因此,NCDI-RLNC方案的計算復雜度為O(N+M(M-1)+N)=O(M2+N)。

文獻[9]中的討論結果表明構建IDNC圖并求解最大權重團的復雜度為O(M2N)。為尋找最佳編碼策略,NCDI-IDNC方案首先需要在基站側構建IDNC圖并確定最佳編碼包,復雜度為O(M2N);其次,選擇Has集合最大的設備作為發(fā)送設備的復雜度為O(M),構建設備側IDNC圖并確定最佳編碼包,其復雜度最多為O((M-1)2N)。因此,NCDI-IDNC方案的計算復雜度為O(M2N+M+(M-1)2N)=O(M2N)。

6 仿真結果

表3 不同方案的計算復雜度比較

圖3 重傳次數(shù)vs.設備數(shù)量MFig.3 The retransmission times versus the number of devices

圖4 重傳次數(shù)vs.數(shù)據(jù)包數(shù)目NFig.4 The retransmission times versus the number of packets

圖5 重傳次數(shù)vs.蜂窩、D2D鏈路平均丟包概率δFig.5 The retransmission times versus mean cellular/D2D erasure probabilities

7 結論

本文對聯(lián)合蜂窩與D2D鏈路的網(wǎng)絡編碼廣播重傳方案進行了研究?？紤]移動設備配備有雙接口的無線網(wǎng)絡編碼廣播場景,設備之間彼此靠近,因此在重傳階段可以同時利用蜂窩與D2D鏈路來恢復丟失內(nèi)容。為最小化重傳次數(shù),合理的進行編碼調度,文章針對RLNC策略下的聯(lián)合蜂窩與D2D鏈路調度,提出了NCDI-RLNC方案;針對IDNC策略下的聯(lián)合蜂窩與D2D鏈路調度,提出了基于最大權重團搜尋的NCDI-IDNC方案。仿真結果表明,與其他方案相比,提出的兩種方案均能有效提高重傳效率、減少重傳次數(shù)。