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

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

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

1 網(wǎng)絡模型

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

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

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

2 理論分析

2.1 時間復雜度

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

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

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

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

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

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

3 結(jié)果分析

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（收稿日期： 2019.11.18）

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