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

MANET中基于二次置换多项式的滑动窗口网络编码算法 Quadratic Permutation Polynomials-Based Sliding Window Network Coding Algorithm in MANET 1 first-author 孙宝林，男，教授，现从事移动网络技术、移动计算技术等方面的研究。E-mail：blsun@163.com 孙宝林，男，教授，现从事移动网络技术、移动计算技术等方面的研究。E-mail：blsun@163.com blsun@163.com 1 1 corresp E-mail: prisong@163.com E-mail: prisong@163.com prisong@163.com 1 2 1 2 3 湖北经济学院 信息与通信工程学院，湖北 武汉 430205 湖北经济学院 信息与通信工程学院，湖北 武汉 430205 School of Information and Communication Engineering, Hubei University of Economics, Wuhan 430205, Hubei, China School of Information and Communication Engineering, Hubei University of Economics, Wuhan 430205, Hubei, China 湖北大学 计算机与信息工程学院，湖北 武汉 430062 湖北大学 计算机与信息工程学院，湖北 武汉 430062 School of Computer Science and Information Engineering, Hubei University, Wuhan 430062, Hubei, China School of Computer Science and Information Engineering, Hubei University, Wuhan 430062, Hubei, China 广东青年职业学院 计算机工程系，广东 广州 510507 广东青年职业学院 计算机工程系，广东 广州 510507 Computer Engineering Department, Guangdong Youth Vocational College, Guangzhou 510507, Guangdong, China Computer Engineering Department, Guangdong Youth Vocational College, Guangzhou 510507, Guangdong, China 针对移动自组网络(mobile Ad hoc network，MANET)的数据传输机制和数据吞吐量问题，提出了一种MANET中基于二次置换多项式的滑动窗口网络编码(quadratic permutation polynomials-based sliding window network coding, QPP-SWNC)算法。该算法根据QPP理论优化滑动窗口的大小，对进入滑动窗口中的分组进行网络编码操作，恢复原始数据分组，降低每个滑动窗口的编码/解码复杂性。利用NS-2仿真器进行了仿真实验，分析本文算法性能。仿真实验结果表明，相较于典型的Block-LDPC和ACODI算法，本文算法可以优化MANET中编码开销、解码时延和网络吞吐量等性能。 Aiming at the data transmission mechanism and data throughput of mobile Ad hoc network (MANET), this paper proposes a quadratic permutation polynomials-based sliding window network coding (QPP-SWNC) algorithm in MANETs. According to the QPP theory, this algorithm optimizes the size of the sliding window, carries out network coding operation on the packets entering the sliding window, restores the original data packet, and reduces the encoding/decoding complexity of each sliding window. The performance of the proposed algorithm was studied using NS-2 software. Simulation results show that compared with the typical Block-LDPC and ACODI algorithms, the proposed algorithm can optimize the performance of MANET, such as the encoding overhead, decoding delay and network throughput. 移动自组网络 网络编码 二次置换多项式 滑动窗口 mobile Ad hoc network (MANET) network coding quadratic permutation polynomials (QPP) sliding window 孙宝林,桂超,宋莺, 等.MANET中基于二次置换多项式的滑动窗口网络编码算法[J].武汉大学学报（理学版）,2019,65(6):547-553. DOI:10.14188/j.1671-8836.2019.06.003. 0　 引 言 1 移动自组网络(mobile Ad hoc network, MANET)是由大量具有移动性、计算能力、路由功能和通信能力的移动节点组成的网络。该网络具有多跳性能，即当一个移动节点移出或进入另一个节点的传输范围时，两个节点之间的无线链路就会断开或连接 [ 1 1 , 2 2 , 3 3 , 4 4 , 5 5 ] 。 网络编码(network coding, NC)是无线通信领域的突破性研究成果之一。它最初是由Ahlswede等 [ 1 1 ] 提出的，目前已经应用到无线通信和移动网络的所有领域。NC实际上是基于有限域GF(2 q )上的代数运算设计的，可降低空间复杂性并提高数据吞吐量。Yeung [ 2 2 ] 针对NC的理论和性质，提出了NC的构造方案。文献[ 3 3 , 4 4 ]综述了近年来NC的分类、研究进展以及优缺点，论述了NC理论与实际应用的差距，展望了NC的发展前景。 近几年来，一些算法对MANET实时数据流的缓存机制、协同机制以及NC算法进行了有机结合，实现了数据流的快速传输 [ 5 5 , 6 6 ] 。文献[ 7 7 , 8 8 ]针对实时视频流媒体的应用问题，提出了分散决策、最大比例组合的网络编码算法，减少了带宽消耗、数据传输的误码率和故障概率。为了优化网络编码误码性能并降低编码/解码复杂度，Nieminen [ 9 9 ] 提出了一种基于蝶形网络的二次置换多项式（quadratic permutation polynomials，QPP）的并行代码访问的编码方案；Guan等 [ 10 10 ] 提出了一种基于QPP的非单位矩阵的不规则Block-LDPC代码方案,提高了数据流的快速传输质量。 为实现高效、全面的数据恢复机制，文献[ 11 11 ]提出了无线网络中编码时间与解码延迟之间平衡的可即时解码网络编码算法；文献[ 12 12 ]提出了一种用户使用无线视频流数据生成NC分组的机制，通过一个辅助通道将数据传输给它的直接邻居。在MANET数据的传输效率和安全性方面，Kim等 [ 13 13 ] 提出了一种基于链路传输质量的自适应代码传播算法（ACODI)，提高了数据的传输效率；Ostovari等 [ 14 14 ] 提出了一种轻量级的三角层网络编码代替层间网络编码的算法，以减少优化编码的时间复杂度；杜瑞颖等 [ 15 15 ] 提出了一种基于网络编码的容错路由传输算法，较好地提升了数据的传输质量和安全性。 在本课题组以往的研究中，文献[ 16 16 ]提出了一种针对无线传感器网络(wireless sensor network，WSN)的网络编码多路径路由算法(NC-WSN)，该算法提高了网络数据传输的可靠性、负载均衡性；文献[ 17 17 ]提出了一种MANET中以伪随机方式构造自适应长度的滑动窗口和网络编码系数的算法——ALSW-NCEE，该算法能够根据能源效率和滑动窗口等参数自适应调整滑动窗口的大小。 为优化MANET的数据传输机制并提高数据吞吐量问题，本文提出了一种MANET中基于二次置换多项式的滑动窗口网络编码(quadratic permutation polynomials-based sliding window network coding, QPP-SWNC)算法；论证了最优传输QPP理论，推导了QPP-SWNC算法复杂度的分析模型；进行了仿真实验研究，分析了QPP-SWNC算法在编码开销、解码时延、分组丢失率和网络吞吐量等方面的性能。 1　 预备知识 1 QPP是近年来编码学和密码学等领域中非常活跃的一类代数研究对象，它为优化滑动窗口大小、减少网络编码的编码/解码复杂性提供了重要的代数理论基础。 1.1　置换多项式 2 考虑一个从0到 k -1的整数集 <math id="M1"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 3.38666677 3.72533321 ，其中整数 k ≥1，本文定义一个长度为 N 的从 <math id="M2"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>N</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 到 <math id="M3"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>N</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 的函数 p ( x )， p ( x ) = a k x k + … + a 1 x + a 0 (mod N )。当 p ( x )∈ <math id="M4"><mfenced open="{" close="}" separators="|"><mrow><mn mathvariant="normal">0</mn><mtext>,</mtext><mtext> </mtext><mn mathvariant="normal">1</mn><mtext>,</mtext><mtext> </mtext><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext> </mtext><mtext>…</mtext><mtext>,</mtext><mtext> </mtext><mi>N</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 32.08866501 3.97933340 时，则称 p ( x )为模 N 上的置换多项式（permutation polynomials，PP）。 定理1 [ 18 18 ] 当 p 为素数集合 P = <math id="M5"><mfenced open="{" close="}" separators="|"><mrow><mn mathvariant="normal">2</mn><mtext>,</mtext><mtext> </mtext><mn mathvariant="normal">3</mn><mtext>,</mtext><mtext> </mtext><mn mathvariant="normal">5</mn><mtext>,</mtext><mtext> </mtext><mn mathvariant="normal">7</mn><mtext>,</mtext><mtext> </mtext><mtext>…</mtext></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 24.38399887 3.97933340 中任意确定素数时，任何正整数 N 的因数可以表示为 <math display="block" id="M6"><mi>N</mi><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∏</mtext></mrow><mrow><mi>i</mi><mtext>=</mtext><mn mathvariant="normal">1</mn></mrow></munder></mrow><mrow><mi>n</mi><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></mover><msup><mrow><mi>p</mi></mrow><mrow><mi>n</mi><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msup></math> http://notExist.jpg http://notExist.jpg 17.61066628 9.22866726 其中， n 为正整数， p i 为不同的素数。当 p i 是不同的素数时， p ( x )是模 N 上的PP，当且仅当满足对于 <math id="M7"><mtext>∀</mtext></math> http://notExist.jpg http://notExist.jpg 2.28600001 2.96333337 i ， p ( x )是模 <math id="M8"><msubsup><mrow><mi>p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup></math> http://notExist.jpg http://notExist.jpg 4.48733330 4.31799984 上的PP时成立。例如 N =112=2 4 7 1 。 定理2 [ 18 18 , 19 19 ] 当且仅当以下两个条件均能满足时， p ( x )= a k x k +…+ a 1 x + a 0 (mod N )是 <math id="M9"><mi mathvariant="double-struck">Z</mi></math> http://notExist.jpg http://notExist.jpg 2.37066674 2.79399991 N 上的PP。 1) 对于素数因子 N 以及所有素数 a i ， p ( x ) = a k x k +…+ a 1 x + a 0 (mod N )都为PP。 2) 对于一个给定的最大整数 n （ n =1, 2, 3, …），满足 p n | N 。 1.2　二次置换多项式 2 定义1 [ 19 19 ] 当 k =2时， p ( x )可写成 p ( x ) = a 2 x 2 + a 1 x + a 0 。其中， a 0 相当于交错序列中的循环旋转系数，在 p ( x )为置换多项式时是不存在的，且不会影响 p ( x )的性能。为了简化，把 a 0 去掉， p ( x )成为二次置换多项式 p ( x )= a 2 x 2 + a 1 x ，可以简写为： p ( x )= ax 2 + bx 。 对于 <math id="M10"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>N</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 中的所有 x 来说， p ( x )= ax 2 + bx 的模是 N 。自然地，整数 a ， b 和 N 必须满足给定的要求，才能使 p ( x )是 <math id="M11"><mi mathvariant="double-struck">Z</mi></math> http://notExist.jpg http://notExist.jpg 2.37066674 2.79399991 N 上的PP，反之亦然，如果 p ( x )是 <math id="M12"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>N</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 上的PP，则整数 a ， b 和 N 必须满足给定的条件，见定理3。每一个正整数都可以表示为素数幂的乘积。本文用gcd( x , y )表示两个正整数 x 和 y 的最大公约数。 定理3 [ 19 19 , 20 20 ] 使 <math id="M13"><mi>N</mi><mtext>=</mtext><msub><mo>∏</mo><mrow><mi>p</mi><mtext>∈</mtext><mi>P</mi></mrow></msub><mrow><msup><mrow><mi>p</mi></mrow><mrow><msub><mrow><mi>n</mi></mrow><mrow><mi>N</mi><mtext>,</mtext><mi>p</mi></mrow></msub></mrow></msup></mrow></math> http://notExist.jpg http://notExist.jpg 23.11400032 5.24933338 ， y | z 表示 z 能整除 y ， y <math id="M14"><mtext>⊥</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.30199981 z 表示 z 不能整除 y 。二次多项式 p ( x )= ax 2 + bx (mod N )作为PP的充要条件可分为两种情况： 1） 2| N 和4 <math id="M15"><mtext>⊥</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.30199981 N (即 n N ,2 =1)， a + b 是奇数，gcd( b , N /2)=1，且 <math id="M16"><mi>a</mi><mtext>=</mtext><msub><mo>∏</mo><mrow><mi>p</mi><mtext>∈</mtext><mi>P</mi></mrow></msub><mrow><msup><mrow><mi>p</mi></mrow><mrow><msub><mrow><mi>n</mi></mrow><mrow><mi>p</mi><mtext>(</mtext><mi>x</mi><mtext>)</mtext><mtext>,</mtext><mi>p</mi></mrow></msub></mrow></msup></mrow><mtext>,</mtext><msub><mrow><mi>n</mi></mrow><mrow><mi>p</mi><mtext>(</mtext><mi>x</mi><mtext>)</mtext><mtext>,</mtext><mi>p</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 41.82533264 5.33399963 ，对于 <math id="M17"><mtext>∀</mtext></math> http://notExist.jpg http://notExist.jpg 2.28600001 2.96333337 p ， p <math id="M18"><mtext>≠</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.04799986 2且 n N,p ≥1。 2） 无论是2 <math id="M19"><mtext>⊥</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.30199981 N 或4| N (即 n N,p <math id="M20"><mtext>≠</mtext></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.04799986 1)，gcd( b , N )=1且 <math id="M21"><mi>a</mi><mtext>=</mtext><msub><mo>∏</mo><mrow><mi>p</mi><mtext>∈</mtext><mi>P</mi></mrow></msub><mrow><msup><mrow><mi>p</mi></mrow><mrow><msub><mrow><mi>n</mi></mrow><mrow><mi>p</mi><mtext>(</mtext><mi>x</mi><mtext>)</mtext><mtext>,</mtext><mi>p</mi></mrow></msub></mrow></msup></mrow><mtext>,</mtext><msub><mrow><mi>n</mi></mrow><mrow><mi>p</mi><mtext>(</mtext><mi>x</mi><mtext>)</mtext><mtext>,</mtext><mi>p</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 41.82533264 5.33399963 ，对于 <math id="M22"><mtext>∀</mtext></math> http://notExist.jpg http://notExist.jpg 2.28600001 2.96333337 p ， n N,p ≥1。 当且仅当 N > gcd( N , 2 a )时， <math id="M23"><msub><mrow><mi mathvariant="double-struck">Z</mi></mrow><mrow><mi>N</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 4.06400013 3.72533321 上的二次置换多项式 p ( x )= ax 2 + bx (mod N )不能化简。 1.3　最优传输QPP 2 定义2 [ 19 19 , 20 20 ] 在二次置换多项式 p ( x )= ax 2 + bx 中，当 a= 2 k +1 ， b= (2 k - 1)， k =1, 2, 3, …时， p ( x )为一个无穷序列，称其为最优传输QPP p ( x )=2 k +1 x 2 +(2 k -1) x (2) 最优传输QPP的区间如 表1 表1 所示。 k N p ( x ) Sqr(2 N ) 2 8 8 x 2 + 3 x 4 3 32 16 x 2 + 7 x 8 4 128 32 x 2 + 15 x 16 5 288 64 x 2 + 31 x 24 例如，当数据长度 N =32且子窗口中的最优数据长度为8时，可产生4个最优子窗口。 图1 图1 为其最优窗口分组示意图。 2　 本文算法 1 在本文中，根据最优传输QPP理论可生成最优大小的滑动窗口，发送方并不是将所有的发送数据分组都进行网络编码，只是对进入到滑动窗口中的数据分组进行网络编码。接收方接收到相应的编码数据后，就进行解码操作，此时需要在发送节点和接收者节点之间进行恒定的信息反馈，以确定在接收节点上能知道多少分组进入到窗口中，达到降低编码/解码复杂性的目的。 2.1　滑动窗口机制 2 MANET可表示为一个无向图 G =( V , E )，其中 V 表示网络中的移动节点集， E 表示无线链路集。每个无线链路 e =( i' , j' ) <math id="M24"><mtext>∈</mtext></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.13266659 E 代表移动节点 i' 与移动节点 j' 之间的无线链路是直接相连，并且假设无线链路是对称的，即( i' , j' )=( j' , i' ) <math id="M25"><mtext>∈</mtext></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.13266659 E 。 对于每个需要传输的数据分组来说，源节点选择将分组块( x 0 , x 1 , …, x M- 1 )和编码向量( c 0 , c 1 , …, c M- 1 )与大小为SW(1≤SW≤ M )的滑动编码窗口相结合，不属于编码窗口中编码向量的元素等于零。对于 P 个数据分组，则有 P /SW+1个大小为SW的滑动窗口，SW= e - f +1，大小为SW的滑动编码窗口是块( x f , x f +1 ,…, x e )的序列，0≤ f , e ≤ M -1， f ≤ e 。当确定了 f 后，滑动编码窗口中的最后分组可为 e = f +SW-1。第 i 个滑动编码窗口的开始分组和结束分组可以分别用 f i 和 e i 表示，第 i 个滑动编码窗口的长度为SW i = e i - f i +1。 图2 图2 表示滑动编码窗口大小为8的滑动机制。 2.2　网络编码机制 2 本文使用线性网络编码方案。线性网络编码方案中编码向量 c i = ( c i 0 , c i 1 , …, c i （ M- 1） )被给定，将输入分组向量 X =( x 0 , x 1 , …, x M -1 )转换成输出分组 P i 的编码方法如下 <math display="block" id="M26"><msub><mrow><mi>P</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>j</mi><mtext>=</mtext><mn mathvariant="normal">0</mn></mrow></munder></mrow><mrow><mi>M</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></mover><msub><mrow><mi>c</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 20.82799911 8.88999939 然后，目的节点可以解码接收的编码分组，因为编码向量 c i = ( c i 0 , c i 1 ,…, c i （ M- 1） )和输出分组数据 P = ( P 0 , P 1 , …, P M- 1 )是从接收的分组中获得的，并且系数矩阵存在逆矩阵。 2.3　算法描述 2 在QPP-SWNC算法中，滑动窗口机制可以减少网络编码/解码的计算复杂性，有效地提高网络数据吞吐量。其算法描述如算法1所示。 算法1 QPP-SWNC算法 输入： 需要传输的数据分组 P' ，滑动窗口的大小SW，初始值 i =1，滑动窗口的开始数据 f =0; 输出： 编码节点输出滑动窗口中的编码分组，接收节点输出解码分组; 过程： 1） 确定需要传输的数据分组 P' ，根据最优传输QPP，确定滑动窗口的大小SW； 2） 初始滑动窗口数， i =1，确定滑动窗口的开始分组 f ，确定滑动窗口的结束分组 e ； 3） 确定滑动窗口的总数， n = P /SW+1; 4） 对每一个 i <math id="M27"><mtext>∈</mtext></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.13266659 P' ，重复如下步骤，如果 <math id="M28"><mi>i</mi><mtext>∉</mtext><mi>P</mi></math> http://notExist.jpg http://notExist.jpg 8.04333305 3.55599999 '，则转第10步； 5） 如果 i ≤ n ，则继续如下步骤，如果 i > n ，则转到第9步； 6） 使SW个分组( x f , …, x e )进入到滑动窗口中，利用线性网络编码方案进行编码， <math id="M29"><msub><mrow><mi>P</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>j</mi><mtext>=</mtext><mn mathvariant="normal">0</mn></mrow></munder></mrow><mrow><mi>M</mi><mtext>-</mtext><mn mathvariant="normal">1</mn></mrow></mover><msub><mrow><mi>c</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mrow><mi>x</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 20.06599998 8.88999939 ，然后传输到下一个节点； 7） i ← i + 1, f i = f i -1 +SW i , e i = e i -1 +SW i ； 8） 转到第5步； 9） 接收节点接收到网络编码分组，并利用线性网络编码方案进行解码，转到第4步； 10） 数据分组传输结束。 3　 QPP-SWNC算法复杂性分析 1 本文中，设 t i 为分组 i ( i =1,2,…)在滑动窗口中的时间， D i ( t i )为分组 i 在滑动窗口 t i (s)时间内解码分组的数量。设计目标是最大化总分组数量 D SW ,即 <math display="block" id="M30"><mi mathvariant="normal">M</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><msub><mrow><mi>D</mi></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi></mrow></msub><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi></mrow></munder><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>)</mtext><mtext>,</mtext><mtext>   </mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi></mrow></munder><mtext>(</mtext><mi>p</mi><mtext>×</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>)</mtext><mtext>≤</mtext><mi>p</mi><mtext>×</mtext><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi><mtext>×</mtext><mi>T</mi></math> http://notExist.jpg http://notExist.jpg 79.24799347 6.60399961 其中， p 为分组大小， T 为滑动窗口工作时间。 同一个滑动窗口中的分组划分为一组，用 n h 表示第 h(h =1,2,…)组的数据分组数量，则设计目标可表示为 <math display="block" id="M31"><mi mathvariant="normal">M</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><msub><mrow><mi>D</mi></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi></mrow></msub><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>h</mi></mrow></munder><msub><mrow><mi>n</mi></mrow><mrow><mi>h</mi></mrow></msub><msub><mrow><mi>D</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 37.25333405 6.60399961 这里，我们将滑动窗口的解码效率定义为 <math display="block" id="M32"><msub><mrow><mi>E</mi></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi></mrow></msub><mtext>=</mtext><mfrac><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi></mrow></msub></mrow><mrow><mi>p</mi><mtext>×</mtext><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi><mtext>×</mtext><mi>T</mi></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 33.61266708 8.46666718 定义分组 i 的解码效率为 <math display="block" id="M33"><msub><mrow><mi>E</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>)</mtext><mtext>=</mtext><mfrac><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>)</mtext></mrow><mrow><mi>p</mi><mtext>×</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 23.87599945 8.63599968 根据公式(4)~(7)，本文设计的最大化目标可以改写为 <math display="block" id="M34"><mi mathvariant="normal">M</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><msub><mrow><mi>E</mi></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi></mrow></msub><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>h</mi></mrow></munder><mtext>(</mtext><mfrac><mrow><msub><mrow><mi>n</mi></mrow><mrow><mi>h</mi></mrow></msub><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi><mtext>×</mtext><mi>T</mi></mrow></mfrac><mtext>⋅</mtext><mfrac><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>)</mtext></mrow><mrow><mi>p</mi><mtext>×</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub></mrow></mfrac><mtext>)</mtext><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>h</mi></mrow></munder><msub><mrow><mi>a</mi></mrow><mrow><mi>h</mi></mrow></msub><msub><mrow><mi>E</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>(</mtext><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 81.19533539 8.63599968 其中,第 h 组滑动窗口 <math display="block" id="M35"><msub><mrow><mi>a</mi></mrow><mrow><mi>h</mi></mrow></msub><mtext>=</mtext><mfrac><mrow><msub><mrow><mi>n</mi></mrow><mrow><mi>h</mi></mrow></msub><msub><mrow><mi>t</mi></mrow><mrow><mi>h</mi></mrow></msub></mrow><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">W</mi><mtext>×</mtext><mi>T</mi></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 23.45266724 7.70466709 可以看出，QPP-SWNC算法的解码复杂度是比较低的，解码编码数据分组的平均复杂度可简化为 O ( n· SW)。 4　 仿真实验 1 4.1　仿真环境 2 在仿真实验研究中，采用文献[ 21 21 ]中的算法来构造随机无线网络生成图结构，该结构与真实无线网络比较接近，可以确保仿真实验结果的真实性。在一个数据流环境中对QPP-SWNC算法进行评价，源节点将数据分组序列分配给了多个协作接收节点。 在仿真软件NS-2 [ 22 22 ] 中，100个移动节点随机分布在1 000 m×1 000 m区域内，移动节点的传输半径为250 m，移动节点的移动性遵循随机点移动模型 [ 22 22 ] 。网络编码数据分组的丢失率是独立的且具有相同的分布，平均值为0.001%。源节点自由选择并分布在1 000 m×1 000 m区域内。 表2 表2 为仿真实验的环境参数。 参数 值 网络移动节点数 100 网络仿真区域/ m×m 1 000 ×1 000 移动节点传输半径/m 250 仿真时间/s 600 无线信道带宽/Mb·s -1 2 数据载入/B·packet -1 512 传输类型 constant bit rate (CBR) 4.2　实验分析 2 4.2.1　滑动窗口大小的影响 3 为了验证最优传输QPP确定的滑动窗口的性能，研究MANET中不同滑动窗口大小情况下，编码开销、解码时延、分组丢失率和网络吞吐量等参数随网络大小的变化。根据最优传输QPP理论，其优化滑动窗口大小SW的取值可为：8、16和24。 图3 图3 所示为SW不同时，编码开销随网络大小的变化。从 图3 图3 中可以看出，QPP-SWNC算法的编码开销与SW具有很强的相关性。当滑动窗口值SW＝16时，其编码开销最小，主要是因为QPP使滑动窗口的大小达到最优值，参与编码的分组也是最优状态，降低了分组的编码开销。 图4 图4 所示为SW不同时，解码时延随网络大小的变化。从 图4 图4 可知，当滑动窗口值SW＝8时，其解码时延最小，这是因为滑动窗口最小时，接收节点接收到的编码分组个数也是最少的，所以解码时延也是最小的。 图5 图5 所示为SW不同时，分组丢失率随网络大小的变化。从 图5 图5 中可以看出，当SW＝16时，QPP较好地控制了参与编码的分组数量，接收节点接收到的编码分组携带的解码信息量达到最优状态，较好地恢复出原始分组，因此分组丢失率最低。 图6 图6 所示为SW不同时，网络吞吐量随网络大小变化的性能比较。从 图6 图6 中可以看出，当SW＝16时，其网络吞吐量是最高的，主要是因为SW=16时，参与编码分组的数量是最优，使得编码/解码的处理时间相对较低，网络有较多的时间传输编码分组，而且分组丢失率也较低，所以网络吞吐量最高。 4.2.2　与典型算法的性能比较 3 为了验证本文QPP-SWNC算法的性能，分析固定滑动窗口大小(SW=16)情况下，QPP-SWNC算法、典型的Block-LDPC [ 10 10 ] 、ACODI [ 13 13 ] 算法的编码开销、解码时延和网络吞吐量随网络大小的变化。 首先，分析3种算法的编码开销随网络大小的变化情况。从 图7 图7 中可以看出，整体而言，相较于Block-LDPC和ACODI算法，本文QPP-SWNC算法的编码开销最低，这主要是由于该算法采用了QPP机制，滑动窗口中编码分组的数量是最优的，因此对分组进行的网络编码操作也是最优。 然后，分析3种算法的解码时延随网络大小的变化。从 图8 图8 可知， 当网络大小即网络节点的数量增加时，3种算法的解码时延也在增加，但本文QPP-SWNC算法的解码时延比Block-LDPC和ACODI算法的解码时延低，这主要是因为采用本文算法时，接收节点接收到的编码分组数量是最优的，解码分组时能获得最多的解码信息，减少了解码所需要的额外计算时间。 最后，分析3种算法的网络吞吐量随网络大小的变化情况。从 图9 图9 可知， 当网络节点的数量增加时，3种算法的网络吞吐量也随之增大，但与典型的Block-LDPC和ACODI算法相比，本文QPP-SWNC算法的网络吞吐量最大。这主要是因为采用本文算法时，接收节点每次能够接收最优数量的编码分组，而且能够快速、准确地解码分组，恢复原始数据，从而提高了网络吞吐量。 5　 结 论 1 本文提出QPP-SWNC算法，该算法首先根据最优传输QPP性质确定最优滑动窗口的大小；然后利用线性网络编码机制对滑动窗口中的分组进行网络编码，接收节点对接收到的编码分组进行解码操作，从而恢复原始数据；接着对滑动窗口中的分组编码/解码操作进行了复杂性分析；最后利用NS-2仿真器进行了仿真实验。结果表明，相较于典型的Block-LDPC和ACODI算法，本文算法优化了MANET网络中编码开销、解码时延和网络吞吐量等性能。 参考文献 AHLSWEDE R , CAI N , LI S⁃Y R , et al . Network information flow [J]. IEEE Transactions on Information Theory , 2000 , 46 ( 4 ): 1204 ⁃ 1216 . DOI: 10.1109/18.850663 http://dx.doi.org/10.1109/18.850663 . Network information flow YEUNG R W . Network coding: A historical perspective [J]. Proceedings of the IEEE , 2011 , 99 ( 3 ): 366 ⁃ 371 . DOI: 10.1109/JPROC.2010.2094591 http://dx.doi.org/10.1109/JPROC.2010.2094591 . Network coding: A historical perspective MOHAMMED A H , DAI B , HUANG B X , et al . A survey and tutorial of wireless relay network protocols based on network coding [J]. Journal of Network and Computer Applications , 2013 , 36 ( 2 ): 593 ⁃ 610 . DOI: 10.1016/j.jnca.2012.12.018 http://dx.doi.org/10.1016/j.jnca.2012.12.018 . A survey and tutorial of wireless relay network protocols based on network coding MAGLI E , WANG M , FROSSARD P , et al . Network coding meets multimedia: A review [J]. IEEE Transactions on Multimedia , 2013 , 15 ( 5 ): 1195 ⁃ 1212 . DOI: 10.1109/TMM.2013.2241415 http://dx.doi.org/10.1109/TMM.2013.2241415 . Network coding meets multimedia: A review YANG Z , LI M , LOU W . R-code: Network coding-based reliable broadcast in wireless mesh networks [J]. Ad Hoc Networks , 2011 , 9 ( 5 ): 788 ⁃ 798 . DOI: 10.1016/j.adhoc.2010.09.009 http://dx.doi.org/10.1016/j.adhoc.2010.09.009 . R-code: Network coding-based reliable broadcast in wireless mesh networks AYATOLLAHI H , KHANSARI M , RABIEE H R . A push-pull network coding protocol for live peer-to-peer streaming [J]. Computer Networks , 2018 , 130 : 145 - 155 . DOI: 10.1016/j.comnet.2017.11.007 http://dx.doi.org/10.1016/j.comnet.2017.11.007 . A push-pull network coding protocol for live peer-to-peer streaming BAYAT N , LUTFIYYA H . Network coding for coping with flash crowd in P2P multi-channel live video streaming [C] // 11st International Conference on the Design of Reliable Communication Networks . New York : IEEE Press , 2015 : 243 ⁃ 246 . DOI: 10.1109/DRCN.2015.7149019. Network coding for coping with flash crowd in P2P multi-channel live video streaming ZHANG S W , SONG R F , HONG T . Network-coding-based two-way relay cooperation with energy harvesting [J]. International Journal of Distributed Sensor Networks , 2017 , 13 ( 4 ): 1 - 8 . DOI: 10.1177/1550147717706437 http://dx.doi.org/10.1177/1550147717706437 . Network-coding-based two-way relay cooperation with energy harvesting NIEMINEN E . On quadratic permutation polynomials, turbo codes, and butterfly networks [J]. IEEE Transactions on Information Theory , 2017 , 63 ( 9 ): 5793 - 5801 . DOI: 10.1109/TIT.2017.2717579 http://dx.doi.org/10.1109/TIT.2017.2717579 . On quadratic permutation polynomials, turbo codes, and butterfly networks GUAN W , LIANG L . Construction of Block-LDPC codes based on quadratic permutation polynomials [J]. Journal of Communications and Networks , 2015 , 17 ( 2 ): 157 - 161 . DOI: 10.1109/JCN.2015.000029 http://dx.doi.org/10.1109/JCN.2015.000029 . Construction of Block-LDPC codes based on quadratic permutation polynomials ABOUTORAB N , SADEGHI P , SOROUR S . Enabling a tradeoff between completion time and decoding delay in instantly decodable network coded systems [J]. IEEE Transactions Communications , 2014 , 62 ( 4 ): 1296 ⁃ 1309 . DOI: 10.1109/TCOMM.2014.021614.130172 http://dx.doi.org/10.1109/TCOMM.2014.021614.130172 . Enabling a tradeoff between completion time and decoding delay in instantly decodable network coded systems ZHANG B , LIU Z , CHAN G S H , et al . Collaborative wireless freeview video streaming with network coding [J]. IEEE Transactions on Multimedia , 2016 , 18 ( 3 ): 521 - 536 . DOI: 10.1109/TMM.2016.2518485 http://dx.doi.org/10.1109/TMM.2016.2518485 . Collaborative wireless freeview video streaming with network coding KIM D , NAM H , KIM D . Adaptive code dissemination based on link quality in wireless sensor networks [J]. IEEE Internet of Things Journal , 2017 , 4 ( 3 ): 685 - 695 . DOI: 10.1109/JIOT.2016.2643659 http://dx.doi.org/10.1109/JIOT.2016.2643659 . Adaptive code dissemination based on link quality in wireless sensor networks OSTOVARI P , WU J , KHREISHAH A , et al . Scalable video streaming with helper nodes using random linear network coding [J]. IEEE/ACM Transactions on Networking , 2016 , 24 ( 3 ): 1574 - 1587 . DOI: 10.1109/TNET.2015.2427161 http://dx.doi.org/10.1109/TNET.2015.2427161 . Scalable video streaming with helper nodes using random linear network coding 杜瑞颖 ， 陈晶 ， 陈建军 . 无线传感器网络中基于网络编码的容错路由 [J]. 武汉大学学报(理学版) , 2013 , 59 ( 3 ): 267 - 271 . DOI： 10.14188/j.1671-8836.2013.03.009 http://dx.doi.org/10.14188/j.1671-8836.2013.03.009 . 无线传感器网络中基于网络编码的容错路由 DU R Y , CHEN J , CHEN J J . Fault tolerant routing based on network coding in wireless sensor network [J]. Journal of Wuhan University (Natural Science Edition) , 2013 , 59 ( 3 ): 267 - 271 . DOI：10.14188/j.1671-8836.2013.03.009 (Ch) . Fault tolerant routing based on network coding in wireless sensor network SUN B L , GUI C , SONG Y , et al . A novel network coding and multi-path routing approach for wireless sensor network [J]. Wireless Personal Communications , 2014 , 77 ( 1 ): 87 ⁃ 99 . DOI: 10.1007/s11277-013-1496-y http://dx.doi.org/10.1007/s11277-013-1496-y . A novel network coding and multi-path routing approach for wireless sensor network SUN B L , GUI C , SONG Y , et al . Adaptive length sliding window-based network coding for energy efficient algorithm in MANETs [C] // 14th IFIP International Conference on Network and Parallel Computing (LNCS 10578) . Heidelberg : Springer-Verlag , 2017 : 13 - 23 . DOI: 10.1007/978-3-319-68210-5_2. Adaptive length sliding window-based network coding for energy efficient algorithm in MANETs LAHTONEN J , RYU J , SUVITIE E . On the degree of the inverse of quadratic permutation polynomial interleavers [J]. IEEE Transactions on Information Theory , 2012 , 58 ( 6 ): 3925 - 3932 . DOI: 10.1109/TIT.2012.2190492 http://dx.doi.org/10.1109/TIT.2012.2190492 . On the degree of the inverse of quadratic permutation polynomial interleavers 查正邦 , 胡磊 . 有限域上置换多项式的几种构造 [J]. 密码学报 , 2017 , 4 ( 3 ): 291 - 298 . DOI： 10.13868/j.cnki.jcr.000182 http://dx.doi.org/10.13868/j.cnki.jcr.000182 . 有限域上置换多项式的几种构造 ZHA Z B , HU L . Several constructions of permutation polynomials over finite fields [J]. Journal of Cryptologic Research , 2017 , 4 ( 3 ): 291 - 298 . DOI：10.13868/j.cnki.jcr.000182 (Ch) . Several constructions of permutation polynomials over finite fields 袁媛 , 张焕国 . 关于正形置换多项式的注记 [J]. 武汉大学学报(理学版) , 2007 , 53 ( 1 ) : 33 - 36 . DOI： 10.14188/j.1671-8836.2007.01.009 http://dx.doi.org/10.14188/j.1671-8836.2007.01.009 . 关于正形置换多项式的注记 YUAN Y , ZHANG H G . A note on orthormophic permutation polynomials [J]. Journal of Wuhan University (Natural Science Edition) , 2007 , 53 ( 1 ) : 33 - 36 . DOI：10.14188/j.1671-8836.2007.01.009 (Ch) . A note on orthormophic permutation polynomials WAXMAN B . Routing of multipoint connections [J]. IEEE Journal on Selected Areas in Communications , 1988 , 6 ( 9 ): 1617 ⁃ 1622 . DOI: 10.1109/49.12889 http://dx.doi.org/10.1109/49.12889 . Routing of multipoint connections VINT PROJECT . The Network Simulator-NS- 2 [ EB/OL ]. [ 2018-01-05 ]. http://www.isi.edu/nsnam/ns/ http://www.isi.edu/nsnam/ns/ . The Network Simulator-NS- 10.14188/j.1671-8836.2019.06.003 TP 393 A 1671-8836（2019）06-0547-07 SUN Baolin,GUI Chao,SONG Ying, et al .Quadratic Permutation Polynomials-Based Sliding Window Network Coding Algorithm in MANET [J]. J. Wuhan Univ. （ Nat. Sci. Ed ）,2019,65(6):547-553. DOI:10.14188/j.1671-8836.2019.06.003(Ch). SUN Baolin,GUI Chao,SONG Ying,et al.Quadratic Permutation Polynomials-Based Sliding Window Network Coding Algorithm in MANET [J].J. Wuhan Univ.（Nat. Sci. Ed）,2019,65(6):547-553. DOI:10.14188/j.1671-8836.2019.06.003(Ch). 孙宝林,桂超,宋莺, 等.MANET中基于二次置换多项式的滑动窗口网络编码算法[J].武汉大学学报（理学版）,2019,65(6):547-553. DOI:10.14188/j.1671-8836.2019.06.001 孙宝林,桂超,宋莺, 等.MANET中基于二次置换多项式的滑动窗口网络编码算法[J].武汉大学学报（理学版）,2019,65(6):547-553. DOI:10.14188/j.1671-8836.2019.06.001 国家自然科学基金资助项目（61572012）；湖北省自然科学基金资助项目（2018CFB661, 2017CFB677） 2018-10-28 2019-12-24 2020-05-21 武汉大学学报（理学版） 6 65