基于网络编码的无线网络数据分发系统研究

张乐

(厦门工学院计算机与人工智能学院，厦门361021)

0 引言

随着无线网络技术的快速发展，基于无线传输的各种应用越来越丰富。在商场、车站、机场等人流量大的地方，往往有基于地理位置的信息分发的需求，例如针对当前位置的无线广告分发。然而，无线信道往往较为脆弱，尤其是在节点移动且障碍物较多的室内场景，往往存在连接传输不稳定、丢包率较高的情况。

网络编码技术可以有效提高无线传输的稳定性与效率[1，2]，研究利用网络编码技术进行无线网络的数据分发是重要课题之一。Ho等人[3]提出了一种随机线性网络编码(Random Linear Network Coding，RLNC)算法，可以令发送出去的每一个数据包都携带等量的信息，已经得到大量的应用。Nandan等人[4]提出了一种基于网络编码的位置感知广告服务。在车联网中也可以利用线性编码技术对数据包进行编码发送[5]，但过于频繁的数据请求导致下载延迟较大。除了在数据包发送前进行编码以外，还可以加入优先级的技术，令拥有较多编码数据包的节点优先发送[6]。李业等[2]则利用随机线性网络编码有效地降低了传输的时延。

1 随机线性网络编码

对于不稳定的无线传输，网络编码在可靠性和吞吐上都起到十分重要的作用[7]。无连接的传输中往往没有确认机制，因此对于传输失败的情况很难精确重传，一旦重传的是已成功发送的数据，对于无线带宽来说是极大的浪费。在随机线性网络编码中，每一个编码包都是唯一的，因此可以解决重传重复数据的问题。经过随机线性编码的数据包，所包含的信息量都是均等的，也没有先后次序。从信宿节点来看，编码包可认为是无差异的，因此特别适合使用广播的方式进行发送，有效利用无线网络的空间冗余。要接收完整的一份报文，信宿节点并不需要接收特定的数据包。信源节点也不需要重传某个丢失的数据包，只需要继续发送下一个编码包即可，信宿节点只要接收足够的线性无关的编码包就可以解码获取完整报文。随机线性网络编码的这种特性，十分适合网络环境恶劣、传输质量较差的无线分发场合。

在随机线性网络编码策略中，假设要发送的信息被分成k个包pi，那么就可以在有限域上随机选取k个系数ci进行线性组合形成编码包P=∑cipi，重复系数选取并编码的过程，就可以根据需要产生若干编码包。中间节点接收到这些编码包后，先判断是否线性无关，若无关则可以保存。同时，中间节点仍然可以继续随机选取系数进行组合重新编码成一个编码包转发出去。随机线性网络编码的全部操作均是基于有限域的线性运算，所有编码系数均从有限域中独立随机地选取。只要选取系数的有限域Fq足够大，随机线性网络编码就能以较高的概率获得线性无关的组合进行解码[8]。实际应用当中，q=28就已经足够令各个节点产生远超k个线性无关的编码包进行解码。

假设信源节点发出的信息为X=[x1，x2，…，xk]，其中第i个编码包的编码向量为[ci1，ci2，…，cik]，则该编码包可以表示如下：

(1)

对于信宿节点，输入的信息流可以表示如下：

(2)

其中C是信宿节点的编码系数矩阵。信宿节点只要接收任意k个系数为线性无关的编码包，就可以通过解线性方程组的方法解码得出原始数据。

2 基于随机线性网络编码的数据分发

2.1 问题描述

假设一个数据分发源节点S，需要分发一个广告文件给其它客户节点，分发范围为以S所在坐标为圆心，以R为半径的圆。在分发区域内，不断有客户节点进入与离开，若停留超过一定的时间，就需要完整接收S正在分发的广告文件。整个系统中需要发送的数据包分为两类：分发包和通告包。

分发包：经过随机线性网络编码的广告文件分发数据包。可由分发源节点S广播发送，也可由客户节点广播发送，仅客户节点接收。

通告包：各个客户节点进入分发区域，就通告自己接收分发包的情况；通告包仅由客户节点发送，分发源节点与客户节点均可接收。

数据分发源节点S需要分发的数据包数量为：

m=M/q

(3)

其中M为需要分发的广告文件大小，q为设定的分发数据包大小，单位均为字节。

2.2 算法设计

为了描述方便，表1给出了相关的定义。

表1 算法中使用的定义

客户节点进入分发区域后，接收源节点以及其它邻居节点发送的分发包。当接收到分发包时，判断是否与已接收的分发包线性无关，若无关则保存，然后判断是否满秩，满秩则解方程，成功接收被分发的广告文件。

客户节点Ci进入分发区域，还需要周期广播发送自己的通告包，通告邻居节点自己接收的线性无关的分发包数量Ri。若在下一轮周期发送前已收到其它邻居j的通告包且对方的线性无关分发包更少，即Rj

当接收到通告包时，若本节点拥有的线性无关分发包更多，则可能需要广播发送分发包。为了避免多个拥有更多分发包的节点同时发送产生冲突，在发送分发包之前还需要启动一个定时器等待，若在定时器耗尽前收到比自己更多无关包的通告，则放弃发送分发包，转由拥有更多无关分发包的节点发送。定时器启动设定时间T的计算如下：

T=(m/K_max)·t

(4)

其中t是一个可调的计时单位。这个定时器表明，比邻居拥有更多线性无关分发包的节点，定时器时间越短，即发送分发包的优先级越高。

客户节点Ci或源节点S接收到客户节点Cj发送的通告包的具体处理算法如下：

初始化：

If(是源节点)

Ri←m;

Else

Ri←0;

K_max←0;

T_remain←正无穷大

接收处理流程：

If(接收的是分发包){

If(本节点是客户节点且分发包线性无关){

Ri←Ri+1;

If(Ri==m)

解码，成功接收。

}

}

Else{

k←Ri-Rj

If(k>0){

If(k>K_max){

K_max←k;

T←(m/K_max)*t

T_remain←当前计时器剩余时间;

If(T

T替换当前计时器;

}

}

}

Else if(k<0){

若存在计时器，则删除计时器取消发送。

}

}

算法首先初始化节点所拥有的线性无关分发包的数量，若为数据源节点，则拥有的是全部的分发包数量，否则初始化为零；接着初始化与邻居节点之间的线性无关的数据包的最大差值为零，分发包发送计时器的剩余时间为无穷大。

接收到分发包时，若本节点是源节点且接收到的分发包与已接收的分发包线性无关，则本节点拥有的线性无关分发包数量加1，若数量已达m个，则可以成功解码。

接收到通告包时，先计算本节点i与发送节点j之间线性无关的分发包数量的差值k。分两种情况：

k>0：这表示对方已接收的线性无关分发包不如本节点多。若差值大于之前的最大差值，用当前的差值更新为当前最大差值，然后根据当前最大差值计算一个新的退避时间T；若T小于当前计时器剩余时间T_remain，则用T更新当前计时器的剩余时间。

K<0：这表示对方已接收的线性无关分发包比本节点更多，可以由对方先发送分发包；因此如果本节点存在发送分发包的计时器，删除计时器取消发送即可。

当定时器到期时，则在有限域随机选取Ri个系数，然后重新编码组合成一个新的编码包，重复选取系数进行编码的过程，直到产生新的K_max个分发包，然后连续发送出去。

3 实验结果及其分析

本节将使用NS-3进行仿真实验与分析，并与传统分发方式进行比较。在传统的分发方式中，数据源节点把待分发的文件分成同样大小的数据包，并按顺序持续循环分发。

仿真实验场景设定分发区域为半径80米的圆，所有节点设定的最大通信距离是80米，除了数据源节点固定在分发区域的圆心外，其他节点随机移动，仿真时间为30秒。在仿真实验中，分发包的大小是1400字节，而通告包的大小是50字节。实验分析不同节点密度和分发内容大小的情况下对分发时延和分发成功率的影响。其中分发时延指客户节点发送第一个通告包到获取一份完整的分发文件所需的时间，分发成功率则是整个场景中获取完整分发内容的客户节点与全部客户节点的比率。节点密度分为低密度100个节点，中密度200个节点和高密度300个节点。

3.1 分发时延

如图1所示，当分发内容增多时，显然需要更多的时间，因此接收完整的分发内容的时延也会变大。不过，使用网络编码的分发方法，时延增长速度较慢，而传统方法则快速增加。在分发内容只有200K字节的时候，两种方法在各种密度场景下的分发时延都非常接近。然而，当分发内容超过800K时，两种方法的性能差异较为明显。特别是在1600K字节时，即使是高密度的场景，网络编码方法的分发时延也只有4.372秒，而传统方法的分发时延为8.71秒，网络编码方法性能提升接近50%。这说明在分发内容体积较小的情况下，两种方法没有明显的差异性，而当分发内容体积越大，网络编码分发的优势越明显。这是因为网络编码使得数据包之间不存在差异性，丢失或者接收任何一个数据包所影响的信息量是一样的，而传统方法中，一旦某个数据包丢失，需要在下一轮循环中才有机会发送，当分发内容体积较大时，这个间隔的时间较长。另外，从图上可以看出，因为客户节点只是被动接收数据，因此不同的节点密度对传统分发方法的影响并不明显。由于客户节点也需要发送通告包甚至分发包，因此节点密度较大时，在网络编码的分发方法中会引起一些冲突。这种现象导致高密度场景下编码的时延比低密度下的时延有一定的增长，不过中等密度下的时延反而最小，这主要是因为中等节点密度下，邻近的一些节点辅助源节点发送分发包，有效降低了分发时延。

图1 分发时延

3.2 分发成功率

随着分发内容增大，所需的时延增加，因此，分发成功率会下降，图2也展示了这种趋势。得益于编码后数据包的无差异性，编码方法的分发成功率下降较慢，即使是1600K字节的分发内容，成功率也超过了95%，在体积较小时，更是接近100%。和分发时延快速增加相对应，如图2所示，传统方法的分发成功率也随着分发内容的增大而快速下降。产生这个现象的主要原因是部分距离数据源节点较远的客户节点，在传输过程中丢包率较高，而广播分发的方式并没有针对某个丢失的包的重传，而是整个分发内容的重复发送，这种方式浪费了较多的时间和网络带宽，也较难保证每一个数据包都能成功接收。所以在高密度大体积的情况下，传统方法的分发成功率只有81.8%，分发体积越大，劣势越明显。

图2 分发成功率

4 结语

在需要给大量用户分发数据的时候，为了避免连接产生的负载，往往采用无连接的广播方式发送。但采用无线网络进行广播发送的时候，难以对丢失的数据包进行精准重传。本文提出了基于随机线性网络编码的无线网络分发方法，可以避免丢包引起的重传，提升了数据分发的效率。本文提出的数据分发方法中，节点发送的数据包分为编码包与通告包两种，通过通告包的设计，可由邻居节点辅助发送已经接收到的编码包的组合，进一步降低了分发的时延，从而提高了分发的成功率。通过仿真实验与传统循环发送的方法进行对比，实验结果表明，本文提出的方法可以在分发时延和分发成功率上都有较大的提升，分发内容体积越大，优势越明显。未来工作可以考虑继续改进通告包辅助发送的机制，并应用到多跳长距离分发的场景。