聯(lián)合蜂窩與D2D鏈路的網(wǎng)絡(luò)編碼廣播重傳方案

王鵬飛 張冬梅 許 魁 徐健卉

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

1 引言

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

3 重傳次數(shù)下界

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

(1)

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

(2)

(3)

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

Tlb≥

(4)

4 方案描述

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

4.1 NCDI-RLNC方案

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

表1 NCDI-RLNC方案調(diào)度流程

4.2 NCDI-IDNC方案

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

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

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

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

表2 NCDI-IDNC方案調(diào)度流程

5 開銷與復(fù)雜度分析

5.1 通信開銷

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

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

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

5.2 計(jì)算復(fù)雜度

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

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

6 仿真結(jié)果

表3 不同方案的計(jì)算復(fù)雜度比較

圖3 重傳次數(shù)vs.設(shè)備數(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 結(jié)論

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