基于時間復雜度無線網絡編碼數據包傳輸優化分析

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

關鍵詞： 時間復雜度; 無線網絡; 數據包; 傳輸優化

中圖分類號： 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 引言

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

1 網絡模型

構成整個無線網絡的部分包括源節點S，中繼節點R以及M個目的節點，如圖1所示。

首先由源節點S處理目的節點發送的請求，之后在以上目的節點中輸入N個數據包。根據圖1可知，各信道的丟包率呈現伯努利分布狀態。

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

2 理論分析

2.1 時間復雜度

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

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

2.2 數據包平均傳輸次數

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

次數Nnum所能達到的上界與下界是包含丟失數據包目的節點時所達到的最高丟包數，L是完成初期傳輸過程后，各個目的節點對應的丟失數據包數量。當包含N個原始數據包時，處于可靠的重傳條件下，數據包能夠實現的平均傳輸次數是：

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

3 結果分析

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

在不同的目的節點數量M下得到的數據包平均傳輸次數，如圖3所示。

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

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

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

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

源節點S至中繼節點R產生的丟包率與數據包傳輸次數的關系，如圖5所示。

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

4 結論

1） 形成更多的目的節點數M后，數據包發生了更多次的傳輸，從而使數據包更易發生丟失的現象，導致數據包發生更頻繁丟失，降低了編碼的機會。

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

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

參考文獻

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

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

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

[4] 王國仲，余夢佳.物聯網協作通信中混合編碼調制方法研究[J].廣東通信技術，2019，39（03）：21-25.

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

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

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

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

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

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

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

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

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

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

（收稿日期： 2019.11.18）

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