基于時間復(fù)雜度無線網(wǎng)絡(luò)編碼數(shù)據(jù)包傳輸優(yōu)化分析

摘 要： 為了提高無線網(wǎng)絡(luò)中節(jié)點(diǎn)反饋信息丟失導(dǎo)致真實(shí)反饋的問題，提出了一種基于時間復(fù)雜度無線網(wǎng)絡(luò)編碼數(shù)據(jù)包傳輸優(yōu)化方法。在進(jìn)行時間復(fù)雜度分析的基礎(chǔ)上，分析了數(shù)據(jù)包平均傳輸次數(shù)。開展仿真分析得到：形成更多的目的節(jié)點(diǎn)數(shù)后，數(shù)據(jù)包發(fā)生了更多次的傳輸，使數(shù)據(jù)包更易發(fā)生丟失，降低了編碼的機(jī)會。保持其它各項(xiàng)條件恒定時，各方案性能都表現(xiàn)為當(dāng)原始數(shù)據(jù)包數(shù)量上升后持續(xù)了下降，NCIF方案能夠達(dá)到比CLIF方案更優(yōu)的效果。當(dāng)丟包率增大后，NCIF與CLIF方案都出現(xiàn)了性能降低的情況，使更多數(shù)據(jù)包需通過源節(jié)點(diǎn)來完成重傳恢復(fù)過程。

關(guān)鍵詞： 時間復(fù)雜度; 無線網(wǎng)絡(luò); 數(shù)據(jù)包; 傳輸優(yōu)化

中圖分類號： TP 393文獻(xiàn)標(biāo)志碼： A

Optimization analysis of average transmission times of coded

packets in wireless network based on time complexity

ZHENG Jun

（School of transportation information， Shanxi College of Communication Technology， Xian， Shanxi 710018， China）

Abstract： In order to improve the problem of real feedback caused by the loss of feedback information of nodes in wireless network， an optimization method of packet transmission in wireless network coding based on time complexity is proposed. On the basis of time complexity analysis， the average transmission times of data packets are analyzed. The simulation analysis shows that after the formation of more destination nodes， the packet is transmitted more times， which makes the packet more likely to be lost and reduces the chance of coding. When other conditions are kept constant， the performance of each scheme is shown as a continuous decline after the increase in the number of original packets， and the NCIF scheme can achieve better results than CLIF scheme. When packet loss rate increases， both NCIF and CLIF schemes suffer performance degradation， so that more packets need to complete the retransmission and recovery process through the source node.

Key words： time complexity; wireless network; packets; transmission optimization

0 引言

在無線傳輸過程中，信號質(zhì)量受到實(shí)際傳輸媒介特性、不同信道的干擾情況等因素的共同影響，從而引起很高的丟包率，為了優(yōu)化無線傳輸性能，需要采取合適的方法來增強(qiáng)重傳有效性[1-4]?，F(xiàn)階段，許多學(xué)者對網(wǎng)絡(luò)編碼進(jìn)行了研究，相關(guān)理論也獲得了較快發(fā)展，可以利用網(wǎng)絡(luò)編碼來增加網(wǎng)絡(luò)吞吐量并改善傳輸性能[5-7]。假定無線網(wǎng)絡(luò)重傳屬于一類完美反饋的過程，跟實(shí)際傳輸情況存在一定的差異。有學(xué)者針對單跳網(wǎng)絡(luò)運(yùn)行過程進(jìn)行了分析，結(jié)果顯示當(dāng)出現(xiàn)反饋信息丟失的問題時將會改變通過網(wǎng)絡(luò)編碼實(shí)現(xiàn)的重傳性能，同時認(rèn)為當(dāng)丟包率提高后，目的節(jié)點(diǎn)對于數(shù)據(jù)包的丟失概率將比接收概率更大[8-10]。處于單跳無線多播網(wǎng)絡(luò)沒有形成完美反饋的狀態(tài)下，有學(xué)者[11]先對各種不確定的數(shù)據(jù)包狀態(tài)概率進(jìn)行了分析，再利用廣義方法求解得到網(wǎng)絡(luò)編碼圖的計(jì)算模型，利用最大權(quán)重團(tuán)搜索方式的啟發(fā)算法完成傳輸編碼包的過程，使丟失數(shù)據(jù)包達(dá)到更低的重傳次數(shù)。在無線通信規(guī)模快速擴(kuò)大的情況下，需通過中繼協(xié)作網(wǎng)絡(luò)來實(shí)現(xiàn)無線應(yīng)用場景，但到目前為止還很少有文獻(xiàn)報(bào)道不完美反饋條件下的中繼協(xié)作網(wǎng)絡(luò)傳輸過程。

1 網(wǎng)絡(luò)模型

構(gòu)成整個無線網(wǎng)絡(luò)的部分包括源節(jié)點(diǎn)S，中繼節(jié)點(diǎn)R以及M個目的節(jié)點(diǎn)，如圖1所示。

首先由源節(jié)點(diǎn)S處理目的節(jié)點(diǎn)發(fā)送的請求，之后在以上目的節(jié)點(diǎn)中輸入N個數(shù)據(jù)包。根據(jù)圖1可知，各信道的丟包率呈現(xiàn)伯努利分布狀態(tài)。

處于傳輸初期時，源節(jié)點(diǎn)S將P包含的初始數(shù)據(jù)包傳輸至各目的節(jié)點(diǎn)時是利用有損信道來完成，各目的節(jié)點(diǎn)都會對發(fā)送節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包實(shí)施監(jiān)聽?；謴?fù)丟包數(shù)據(jù)的過程中，發(fā)送節(jié)點(diǎn)將根據(jù)各目的節(jié)點(diǎn)發(fā)生丟包的現(xiàn)象，通過異或運(yùn)算方式獲得重傳包。對上述恢復(fù)過程進(jìn)行重復(fù)處理，確保各目的節(jié)點(diǎn)都能夠接收所有數(shù)據(jù)包。處于傳輸初期與恢復(fù)丟包的過程中，各目的節(jié)點(diǎn)都會對ACK進(jìn)行反饋并將其傳輸?shù)桨l(fā)送節(jié)點(diǎn)[12-14]。從圖1中可以看到，虛線箭頭對應(yīng)的是無線反饋信道，說明未獲得可靠反饋信道，q和p各自表示反饋信道的丟包率，表現(xiàn)為伯努利分布的特征。當(dāng)目的節(jié)點(diǎn)產(chǎn)生的反饋信息沒有到達(dá)發(fā)送節(jié)點(diǎn)時，說明發(fā)生了丟失反饋信息的情況。

2 理論分析

2.1 時間復(fù)雜度

采用NCIF方案時，需要先分析是否每個目的節(jié)點(diǎn)都能夠接收數(shù)據(jù)包，當(dāng)未接受所有數(shù)據(jù)包時，應(yīng)對各項(xiàng)反饋信息進(jìn)行判斷，之后選擇置信度作為系統(tǒng)數(shù)據(jù)接收情況的評價(jià)依據(jù)，控制時間復(fù)雜度，每完成1次傳輸過程，只能通過發(fā)送節(jié)點(diǎn)獲得一種狀態(tài)，由此得到Z取值為1，當(dāng)系統(tǒng)狀態(tài)被確定后，只需利用一個編碼完成發(fā)送過程，此時A取值為1，系統(tǒng)的實(shí)際運(yùn)行狀況只取決于丟失的反饋數(shù)據(jù)個數(shù)，最多丟

失M個反饋信息。由此得到估計(jì)系統(tǒng)進(jìn)行數(shù)據(jù)接收時產(chǎn)生時間復(fù)雜度;形成編碼包的時候，可以利用M×N丟包分布矩陣來計(jì)算相互丟包的編碼方式，根據(jù)可編碼性生成編碼包，由于目的節(jié)點(diǎn)能夠丟失的最大包數(shù)是N，由此得到生成編碼包的時間復(fù)雜度，通過源節(jié)點(diǎn)與中繼節(jié)點(diǎn)進(jìn)行編碼包發(fā)送時，只對中繼丟包分布矩陣實(shí)施遍歷處理，將其維度控制在1×N，由此得到編碼包生成和選擇時間復(fù)雜度，如圖2所示。

2.2 數(shù)據(jù)包平均傳輸次數(shù)

處于較高可靠性的重傳條件下，利用ONC重傳機(jī)制建立的重傳

次數(shù)Nnum所能達(dá)到的上界與下界是包含丟失數(shù)據(jù)包目的節(jié)點(diǎn)時所達(dá)到的最高丟包數(shù)，L是完成初期傳輸過程后，各個目的節(jié)點(diǎn)對應(yīng)的丟失數(shù)據(jù)包數(shù)量。當(dāng)包含N個原始數(shù)據(jù)包時，處于可靠的重傳條件下，數(shù)據(jù)包能夠?qū)崿F(xiàn)的平均傳輸次數(shù)是：

達(dá)到可靠的重傳狀態(tài)屬于一種理想的情況，在實(shí)際運(yùn)行階段通常會受到各類因素的干擾，往往不能形成穩(wěn)定的重傳狀態(tài)（會出現(xiàn)丟失數(shù)據(jù)包的情況），同時還會表現(xiàn)出明顯的隨機(jī)性，這使得遇到不可靠的重傳現(xiàn)象時，將會使上界超出重傳可靠的上界。

3 結(jié)果分析

比較CLIF和NCIF兩種方案在不完美反饋狀態(tài)下的運(yùn)行情況。為了更加深入分析網(wǎng)絡(luò)編碼性能與反饋信息之間的關(guān)系，測試時選擇完美反饋結(jié)果作為參考依據(jù)。處于完美反饋的狀態(tài)下進(jìn)行傳輸反饋的過程中，發(fā)送節(jié)點(diǎn)能夠接收所有目的節(jié)點(diǎn)產(chǎn)生的反饋信息，滿足丟包率=0。因此發(fā)送節(jié)點(diǎn)能夠準(zhǔn)確掌握目的節(jié)點(diǎn)實(shí)際接收情況，測試時把完美反饋方案表示成MBNC。

在不同的目的節(jié)點(diǎn)數(shù)量M下得到的數(shù)據(jù)包平均傳輸次數(shù)，如圖3所示。

可以發(fā)現(xiàn)，目的節(jié)點(diǎn)數(shù)M由2逐漸增多為12，并且單次增加2。將各項(xiàng)系統(tǒng)參數(shù)設(shè)定成原始數(shù)據(jù)包數(shù)量N=50，傳輸過程發(fā)生丟包率0.3，反饋鏈路發(fā)生丟包的概率為0.25。通過仿真測試發(fā)現(xiàn)，形成更多的目的節(jié)點(diǎn)數(shù)M后，數(shù)據(jù)包發(fā)生了更多次的傳輸，從而使數(shù)據(jù)包更易發(fā)生丟失的現(xiàn)象，導(dǎo)致數(shù)據(jù)包發(fā)生更頻繁丟失，降低了編碼的機(jī)會。保持其它各項(xiàng)條件恒定的情況下，中繼節(jié)點(diǎn)可以穩(wěn)定接收各數(shù)據(jù)包，需使源節(jié)點(diǎn)S獲得更多的重傳數(shù)據(jù)包，由于S到目的節(jié)點(diǎn)完成成功傳輸?shù)母怕实陀谟赗到目的節(jié)點(diǎn)的概率，由此導(dǎo)致性能發(fā)生降低的情況。

發(fā)生不完美反饋時，NCIF方案具備比CLIF更優(yōu)的性能，并且相對于SR-WPSIF與SR-WPSCL也具備更強(qiáng)的性能，不過比MBNC與SR-WPS二個方案更差，由于反饋信息發(fā)生丟失后，編碼機(jī)會也將受到明顯影響，由此引起性能的明顯降低。CLIF與SR-WPSCL的性能比通過置信狀態(tài)實(shí)施估計(jì)的方案更低，采用CLIF方案時，發(fā)送節(jié)點(diǎn)把未接收到的反饋編碼包按照丟失方式進(jìn)行處理，這使得發(fā)送節(jié)點(diǎn)無法獲得實(shí)際接收狀態(tài)，沒有選擇合適的編碼包模式，導(dǎo)致系統(tǒng)整體效率受到影響。NCIF方案通過置信度方法評價(jià)系統(tǒng)的各個狀態(tài)，能夠有效降低CLIF方案由于對編碼方式的不合理選擇而引起系統(tǒng)效率的降低，但也不是只需根據(jù)置信度結(jié)果便可以對系統(tǒng)實(shí)際狀況作出準(zhǔn)確評估，這使其表現(xiàn)出比完美反饋更差的性能，對NCIF方案來說則需要繼續(xù)優(yōu)化重傳效率。

在不同的數(shù)據(jù)包個數(shù)N下達(dá)到的平均傳輸次數(shù)，如圖4所示。

其中，原始數(shù)據(jù)的數(shù)量N由10按照每次間隔10的方式增加至50。對系統(tǒng)的各項(xiàng)參數(shù)進(jìn)行設(shè)定，其中，目的節(jié)點(diǎn)數(shù)M=8，傳輸鏈路產(chǎn)生的丟包率0.3，反饋鏈路產(chǎn)生的丟包率0.05。通過仿真測試發(fā)現(xiàn)，保持其它各項(xiàng)條件恒定時，各方案性能都表現(xiàn)為當(dāng)原始數(shù)據(jù)包數(shù)量N上升后持續(xù)了下降的情況，當(dāng)形成了更多的原始數(shù)據(jù)包之后，將使發(fā)送節(jié)點(diǎn)得到更高編碼機(jī)會，使一次傳輸編碼包能夠更多恢復(fù)在目的節(jié)點(diǎn)發(fā)生丟失的數(shù)據(jù)包，從而顯著減小數(shù)據(jù)包的傳輸次數(shù)，并在最后達(dá)到一個穩(wěn)定狀態(tài)，處于更多的原始數(shù)據(jù)包狀態(tài)下，每次發(fā)送編碼包能夠使原始數(shù)據(jù)恢復(fù)的個數(shù)最多為M。NCIF方案能夠達(dá)到比CLIF方案更優(yōu)的效果，這是由于利用置信度估計(jì)的方法能夠減弱由于發(fā)送節(jié)點(diǎn)沒有接收反饋數(shù)據(jù)而受到的干擾。

源節(jié)點(diǎn)S至中繼節(jié)點(diǎn)R產(chǎn)生的丟包率與數(shù)據(jù)包傳輸次數(shù)的關(guān)系，如圖5所示。

按照以下條件設(shè)定系統(tǒng)參數(shù)，其中原始數(shù)據(jù)包數(shù)量N=30，目的節(jié)點(diǎn)數(shù)M=8，傳輸鏈路的丟包率0.4，反饋鏈路出現(xiàn)的丟包率=0.15。經(jīng)仿真測試發(fā)現(xiàn)，當(dāng)丟包率增大后，NCIF與CLIF方案都出現(xiàn)了性能降低的情況，這是由于當(dāng)丟包率增大后，在最初傳輸期間，中繼節(jié)點(diǎn)R逐漸接受更少的數(shù)據(jù)包，引起R作用的降低，使更多數(shù)據(jù)包需通過源節(jié)點(diǎn)來完成重傳恢復(fù)過程。

4 結(jié)論

1） 形成更多的目的節(jié)點(diǎn)數(shù)M后，數(shù)據(jù)包發(fā)生了更多次的傳輸，從而使數(shù)據(jù)包更易發(fā)生丟失的現(xiàn)象，導(dǎo)致數(shù)據(jù)包發(fā)生更頻繁丟失，降低了編碼的機(jī)會。

2） 保持其它各項(xiàng)條件恒定時，各方案性能都表現(xiàn)為當(dāng)原始數(shù)據(jù)包數(shù)量N上升后持續(xù)了下降的情況，NCIF方案能夠達(dá)到比CLIF方案更優(yōu)的效果，利用置信度估計(jì)的方法能夠減弱由于發(fā)送節(jié)點(diǎn)沒有接收反饋數(shù)據(jù)而受到的干擾。

3） 當(dāng)丟包率增大后，NCIF與CLIF方案都出現(xiàn)了性能降低的情況，使更多數(shù)據(jù)包需通過源節(jié)點(diǎn)來完成重傳恢復(fù)過程。

參考文獻(xiàn)

[1] 孟利民，王中冠.無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼與Hash查找的廣播重傳研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2019，47（02）：204-209.

[2] 楊競，范明鈺，王光衛(wèi).基于消息認(rèn)證混合同態(tài)簽名的無線網(wǎng)絡(luò)抗污染攻擊方案[J].計(jì)算機(jī)工程與科學(xué)，2019，41（03）：458-465.

[3] 王瑩，李洪林，費(fèi)子軒，趙竑宇，王虹.5G多接入網(wǎng)絡(luò)TCP研究與展望[J].北京郵電大學(xué)學(xué)報(bào)，2019，42（01）：1-15.

[4] 王國仲，余夢佳.物聯(lián)網(wǎng)協(xié)作通信中混合編碼調(diào)制方法研究[J].廣東通信技術(shù)，2019，39（03）：21-25.

[5] 陳杰，謝顯中，黃倩，黎佳.無線車載網(wǎng)絡(luò)中一種基于跨層優(yōu)化的網(wǎng)絡(luò)編碼TCP協(xié)議[J].計(jì)算機(jī)科學(xué)，2019，46（02）：88-94.

[6] 徐志平，茍亮.散射通信中的網(wǎng)絡(luò)編碼協(xié)同傳輸[J].無線電工程，2018，48（12）：1048-1053.

[7] 韓曉冬，高飛.抗污染攻擊的流內(nèi)安全網(wǎng)絡(luò)糾錯編碼[J].北京理工大學(xué)學(xué)報(bào)，2018，38（11）：1182-1187.

[8] 梁滿.一個基于LPN問題的網(wǎng)絡(luò)編碼同態(tài)MAC加密方案[J].計(jì)算機(jī)應(yīng)用與軟件，2019，36（01）：308-315.

[9] 劉鋒，姜曉晴，曾連蓀.基于單中繼的雙向Y信道并存網(wǎng)絡(luò)設(shè)計(jì)[J].電視技術(shù)，2019，43（01）：17-22.

[10] 歸俊芳，李立.網(wǎng)絡(luò)編碼在SDN下的應(yīng)用研究[J].信息與電腦（理論版），2018，18（24）：153-154.

[11] 趙立新.節(jié)點(diǎn)社會性下的無線網(wǎng)絡(luò)編碼傳輸分析[J].三門峽職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2018，17（04）：139-143.

[12] 劉宴濤，劉珩.一種基于網(wǎng)絡(luò)編碼的云存儲系統(tǒng)[J].計(jì)算機(jī)科學(xué)，2018，45（12）：293-298.

[13] 胡楊添秀，孟利民，蔣維，江培瑞，商宇洲.基于螢火蟲算法的層間網(wǎng)絡(luò)編碼優(yōu)化[J].高技術(shù)通訊，2018，28（Z2）：915-922.

[14] 程青青，陳戈珩.車聯(lián)網(wǎng)中基于概率和網(wǎng)絡(luò)密度的多跳廣播協(xié)議[J].電子技術(shù)與軟件工程，2018，32（23）：21-23.

（收稿日期： 2019.11.18）

作者簡介：鄭君（1974-），男，本科，高級工程師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)。