基于时间复杂度无线网络编码数据包传输优化分析

摘 要： 为了提高无线网络中节点反馈信息丢失导致真实反馈的问题，提出了一种基于时间复杂度无线网络编码数据包传输优化方法。在进行时间复杂度分析的基础上，分析了数据包平均传输次数。开展仿真分析得到：形成更多的目的节点数后，数据包发生了更多次的传输，使数据包更易发生丢失，降低了编码的机会。保持其它各项条件恒定时，各方案性能都表现为当原始数据包数量上升后持续了下降，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-），男，本科，高级工程师，研究方向：计算机网络技术。