基于二次置换多项式的滑动窗口网络编码算法

桂 超，夏承林，孙宝林，宋 莺

(1.湖北经济学院信息与通信工程学院，武汉 430205;2.湖北大学计算机与信息工程学院，武汉 430062)

无线网络的能量、链路带宽、计算和存储能力等都受到一定的限制，提高无线网络的链路带宽、网络吞吐量是无线网络一直探索解决的问题.网络编码最早是由Ahlswede等学者提出的一种基于有限域GF(2q)上的代数运算，可以最大限度地提升无线网络的带宽、数据传输可靠性、网络吞吐量等，较好地降低数据分组编码的计算复杂性和解码过程[1-6].

在无线网络中，相关文献研究表明网络编码在有限域上的性能比二进制编码域上具有更好的稳定性.牛腾等学者针对基于Device-to-Device的无线多媒体网络编码广播重传策略，提出了一种最大权重网络编码选择算法(MWSA-NC)，MWSA-NC算法能极大地提高系统吞吐量，降低解码时延和减少视频流失真[7].Fiandrotti等学者基于无线网络中提出了一种带码网络编码算法，该算法的目的是在数据分组编码、分组重组和解码分组机制中保持良好的数据分组信息[8].Seferoglu等学者以感知队列技术为基础，在编码过程中，以感知队列管理形式构建算法(NCAQM)，该算法在中间节点上实现数据分组的网络编码[9].Lucian等学者分别研究了不同的线性置换多项式(LPPs)、QPPs、CPPs等之间的数量关系及特性.分析了基于二次多项式系数和三次多项式系数的QPPs和CPPs的充要条件和中国剩余定理.构建了一种新的基于线性置换多项式的编码/解码算法，可以更好地降低数据传输的差错率和降低网络编码的计算复杂性[10].Hong等学者针对网络中的滑动窗口机制问题进行了研究，提出了一种带滑动窗口解码(SNNC-SW)的短消息噪声网络编码，该算法的网络编码解码复杂性低、解码时延低、扩展速度较快[11].Lee等学者提出了一种生成网络编码数据分组的协议，它利用多播路由信息和视频数据分组流信息对数据分组流进行网络编码，该协议通过随机线性网络编码算法对数据分组进行批量解码，较好地提升了数据的传输效率、降低了数据分组的差错率和解码时延[12].

考虑到无线网络中节点的移动性强和网络拓扑的快速变化，田贤忠等学者提出了一种基于网络编码的优化策略，该策略让瓶颈区域的部分节点进行网络编码，然后再转发给汇聚节点，较好地减少了数据分组的转发次数和降低了能量消耗[13].Kiss等学者针对无线网络的数据传输可靠性和协作编码机制，提出了一种无线传感器网络的数据协作传输可伸缩的算法，该算法是一种基于Reed-Solomon编码为基础的网络编码协作算法，较好地提升了数据传输的可靠性[14].Ostovari等学者针对编码/解码的时间复杂性，采用随机线性编码技术，基于辅助节点提出了一种代替层间网络编码的一般形式，能够较好地降低了节点的编码时间和解码时间[15].Junior等学者针对无线传感器网络中的能源效率、数据传输可靠性等问题，提出了一个基于数据分布的最小能源消耗的网络编码算法(CodeDrip)，CodeDrip算法可以较好地提高节点的能源效率、数据传输的可靠性和数据吞吐量，可以应用于无线传感器网络中提升网络的性能.考虑到无线网络中不同接收节点间的计算能力、解码能力等相关复杂性问题[16]，Qu等[17]学者提出了一种分类网络编码的编码参数选择算法.

Nieminen等学者提出了一种基于蝶形网络的二次置换多项式(QPP)，作为译码器单元与存储器之间的互连网络，支持多种灵活、无冲突的并行代码访问方法.主要优点是为高速轮机译码器提供了大量新的并行架构，支持集上的二次置换多项式[18].王冠等学者提出的不规则Block-LDPC代码方案可以提供更好的误码性能和降低复杂度[19].Trifina等[19]学者将二次置换多项式编码器和几乎正则置换多项式(ARP)编码器的等价条件扩展为三次置换多项式(CPP)编码器.实验结果表明，CPP编码器的性能赞同于始终等同于(ARP)，但编码长度小于一个的ARP编码器.

针对无线网络的分组传输机制、数据吞吐量和编码的解码延迟等相关问题.本文将二次置换多项式、滑动窗口机制应用于网络编码方法中，构造了一种无线网络中基于二次置换多项式的滑动窗口网络编码算法(QPPSW-NC)，为无线网络的编码效率、解码复杂度、能源效率等性能的改善提供理论支持和性能评价.

1 二次置换多项式的滑动窗口机制

本节基于二次置换多项式、滑动窗口和随机线性网络编码技术，探讨在同一窗口中的数据分组进行编码/解码的有关操作基本原理和机制.

1.1 二次置换多项式(QPP)

一个二次置换多项式p(x)可以定义为：p(x)=ax2+bx，其中a、b、x都是非负整数，即对于任意x∈ZN，p(x) 的模是N.因此，整数a，b，N之间需要满足一定的条件，方可让p(x)是ZN上的置换多项式.相反地，若p(x)是ZN上的置换多项式，那么整数a，b，N之间需要满足一定条件.按阿基米德定理，正整数均可能够分解为若干素数带一定幂次方的乘积，正整数的素数因式分解中每个素数的值总是大于或等于1.只有有限数量的素数才能进入到正整数的素数形式乘积分解.以下用gcd(x，y)代表正整数x和y的最大公约数.

定理1二次多项式p(x)=ax2+bx(modN)作为置换多项式的充要条件可分为两种情况：

1)对所有的N≥2，gcd(b，N)=1，N的每个素数因子都是a的因子；

2)对所有的a和b(a≥1，b≥1)，a+b是奇数、gcd(b，N/2)=1，N的不等于2的每个素数因子都是a的因子.

定理2如果p(x)是二次置换多项式，则p(x)可以生成一个无穷序列：

p(x)=2k+1x2+(2k-1)x，k=1，2，3，….

(1)

严格地说，只有当k>3时，才有二次置换多项式编码器的存在.第一个观察结果是k=1和k=2时对应的.

定理3二次置换多项式p(x)=ax2+bx(modN)在整数集ZN上是不可约的，当且仅当N>gcd(N，2a).

设p(x)=84x2+41x模112，即N=112=2471和84=223171.如此N=112的素数因子都是a=84的因子，且gcd(41，112)=1，这里p是一个二次置换多项式和校验gcd(112，168)=56，得到p是不可约的.通过观察N=112的因子，可以得出二次置换多项式p支持4个窗口大小，分别为56、28、14和7，用于同时访问2、4、8和16个外部值.

图1展示了当N=112时，子窗口的长度为14时的外部值计算方法.每个单元格中的数字表示外部值ei的索引(i=0，1，2，…，111).

图1 子窗口的长度为14和外部值N=112Fig.1 The length of the child window is 14 and the external value N=112

1.2 滑动编码窗口

传统的滑动窗算法的窗长是固定的，算法的复杂度与滑动窗的长度成正比.将滑动窗口和随机网络编码方法进行融合，可以适当降低参加滑动窗口中进行编码/解码的数据分组数量，减少网络时延和能量消耗.

为进一步提高无线网络的服务质量和效率，结合滑动窗口的特点，本文提出了一种二次置换多项式(QPP)确定长度的滑动窗口算法.QPP滑动窗口长度算法的一般结构和过程与传统的滑动窗算法类似，但是滑动窗口的大小是根据滑动过程中的二次置换多项式进行调整的.算法的QPP滑动窗口长度可以自适应地调整每个滑动窗口的长度，避免滑动窗口的长度过大或过小.

图2显示了为QPP长度滑动而提出滑动机制的结构.假设数据的长度为N个信息位，滑动窗口的长度为w信息位和w的整数倍数.让我们定义第i(1≤i≤N/w)向前递归和第i个向后递归计算的度量，向后递归计算从第(i-1)次滑动窗口开始的位置到第i个滑动窗口开始的位置.

图2 QPP滑动窗口机制Fig.2 QPP sliding window mechanism

1.3 滑动窗口的概率分配

一旦设置了滑动窗口的边界区域，就可以对滑动窗口中数据分组数量、编码/解码过程进行数学上的描述研究.

滑动窗口w内数据分组d在位置q的相关概率用P(dq，w|s)表示，则在此机制下输入系统s的概率可表示为：

(2)

在此概率下，滑动窗口可以较好地使得窗口平滑移动.

2 QPP-SWNC编码机制与解码复杂度的分析

2.1 编码/解码规则

数学上，无线网络结构可用无向图G=(V，E)表示，集合V代表移动节点的集合，集合E代表无线网络链路边集.链路可用e=(i，j)∈E代表节点i与节点j之间有边相连，如果(i，j)∈E且(j，i)∈E，假设无线链路是对称的，两个无线链路是否相互干扰取决于所采用的干扰模型.

网络编码过程是在有限域GF(2q)中随机选取的源向量系数的线性组合.让x0，x1，…，xn-1表示与该移动节点相关联的源数据分组.线性网络编码允许从中间移动节点输入组合数据分组.每个组合数据分组包含一个源数据分组的线性组合，它被描述为编码向量的源数据分组的因子向量，也被附加到数据分组上.

无线网络移动节点利用编码向量对数据分组进行编码和解码操作.该算法可以递归地执行编码操作并获得已编码后的数据分组.

2.2 QPP-SWNC解码复杂度的分析

假设移动源节点对于发送的数据分组有一个大小为W的滑动窗口.设ti表示分组i在滑动窗口中的时间，Di(ti)表示分组i的滑动窗口ti秒时间内解码数据分组的数量.则最大化目标可以表示为最大化DW的总数量：

(3)

其中，M为数据分组大小，W为以数据分组计算的滑动窗口大小，T是在滑动窗口内对数据分组进行编码和解码的处理时间.

将具有同样数量的滑动窗口内的待编/解码处理的数据分组归并为一个序列，nk代表第k组的数据分组个数，则最多有效可处理总量如下：

(4)

这里将滑动窗口的解码效率定义为

(5)

从而可以定义分组i的解码效率为

(6)

根据公式(4)～(7)，其最大化目标可以改写为：

(7)

其中，ak表示k组滑动窗口：

(8)

在QPP-SWNC算法中，对任意时刻t，初始化滑动窗口需要O(N)时间，找到滑动编码窗口需要O(e)时间，从而构造一个滑动窗口需要O(eTN)时间，可以得到QPP-SWNC算法在一个滑动窗口中的解码需要O(T2N)时间.

3 仿真实验

在本节中将对QPPSW-NC算法进行性能评价和比较仿真研究，在仿真实验中，将QPPSW-NC算法与SNNC-SW算法[10]和CodeDrip算法[15]进行对比分析.在仿真实验中，将采用网络仿真软件NS2[20]进行仿真实验研究.

3.1 实验环境

在这一节中给出了一种无线网络中基于二次置换多项式滑动窗口的网络编码算法(QPPSW-NC)的仿真实验.移动节点是随机和均匀坐落在1000×1000 m2的区域内，移动节点的传输半径为250米，在此区域内，源节点自由选择并发送数据分组，其他节点接收数据分组.各移动节点自主随机移动，编码数据分组的丢失率分布相同，均值为0.01%且彼此独立.表1为仿真实验参数.

表1 仿真实验参数Tab.1 Simulation experiment parameters

3.2 实验结果

首先仿真分析QPPSW-NC在网络移动节点移动速度变化情况下的网络吞吐量的性能.将网络吞吐量与移动节点的移动速度变化情况下进行比较分析，其QPPSW-NC、SNNC-SW和CodeDrip三种算法的仿真结果如图3所示.从图3中可以看出，当节点的移动速度从慢到快增加时，QPPSW-NC算法的平均网络吞吐量要高于SNNC-SW和CodeDrip算法.因此，使用二次置换多项式滑动窗算法可以更好地提高滑动窗数据编码的效率.

图3 在节点移动速度变化下网络吞吐量的比较Fig.3 Comparison of network throughput under the change of node movement speed

然后测试和分析QPPSW-NC算法中编码开销与节点移动速度的性能.将编码开销与移动节点移动速度变化情况下进行了性能分析，其QPPSW-NC、SNNC-SW和CodeDrip三种算法的仿真结果如图4所示.编码开销随着移动节点移动速度的增加而增加，即当节点的移动速度增加时，编码成本也相应增加.从图4中可以看出，QPPSW-NC算法的编码开销在节点的移动速度增加时，也表现出编码开销最低的性能.

图4 在节点移动速度变化下编码开销的比较Fig.4 Comparison of coding overhead under the change of node movement speed

图5中比较了QPPSW-NC算法与SNNC-SW算法和CodeDrip算法在移动节点移动速度变化下的平均解码延迟.从图5中可以看出，QPPSW-NC算法的解码延迟最小，因为QPPSW-NC算法采用了QPP长度滑动窗口机制，QPP长度滑动窗口中可以提供最优数量的编码/解码数据分组，从而使得解码数据分组的时延最低.

图5 在节点移动速度变化下解码延迟的比较Fig.5 Comparison of decoding delay under the change of node movement speed

随着移动节点移动速度的增加，移动节点之间的距离不断变化，移动节点的能耗也随之增加.图6中比较了QPPSW-NC算法与SNNC-SW算法和CodeDrip算法在移动节点移动速度变化下的网络能源消耗情况.从图6可以看出，QPPSW-NC的能耗消耗低于SNNC-SW算法和CodeDrip算法.这说明QPPSW-NC比其他算法具有更低的能耗.

图6 在节点移动速度变化下网络能源消耗的比较Fig.6 Comparison of network energy consumption under the change of node movement speed

图7展示了移动节点在不同移动速度下能源效率与移动节点移动速度的比较关系.当移动节点的移动速度变大时，移动节点的能源消耗也开始增加从而其能源效率也开始下降.从图7可以看出，QPPSW-NC的能源效率高于SNNC-SW算法和CodeDrip算法的能源效率.这说明QPPSW-NC比其他算法具有更高的能源效率.

图7 在节点移动速度变化下网络能源效率的比较Fig.7 Comparison of network energy efficiency under the change of node movement speed

4 结束语

本文利用二次多项式和滑动窗口技术提出了一个新的网络编码算法(QPPSW-NC)，设计了一个QPPSW-NC解码复杂度的分析模型，使用网络仿真软件NS2对QPPSW-NC算法进行性能分析，并从网络吞吐量、编码开销、数据包传输时延、能源消耗和能源效率等方面进行评估.仿真结果表明，QPPSW-NC算法可以提高网络的可靠性、提高网络的性能.