CN109639393B - 一种基于二次置换多项式的滑动窗口网络编码方法 - Google Patents

Abstract

本发明属于网络编码技术领域，公开了一种基于二次置换多项式的滑动窗口网络编码方法，包括(1)确定无线网络中拟传输的数据分组大小；(2)确定二次置换多项式；(3)确定二次置换多项式的值以及滑动窗口的大小；(4)数据分组进入到滑动窗口；(5)将窗口中的数据分组进行网络编码后传输；(6)接收方接收数据分组并进行解码操作，直至接收完全部的数据分组、恢复原始数据分组；本发明提供的滑动窗口网络编码方法方法，只对进入滑动窗口内的数据分组进行编码操作，减少了网络编/解码操作的复杂性和计算时间，实现了快速的网络编码机制，从而最大化地提高了无线网络的数据吞吐量以及延长网络生存期。

Description

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

技术领域

本发明属于网络编码技术领域，更具体地，涉及一种基于二次置换多项式的滑动窗口网络编码方法。

背景技术

现有技术公开的滑动窗口数据确定方法及装置，用以解决现有技术中确定滑动窗口在某一时刻时包含的业务数据的统计值，所采用的方式所需获取的数据数目较多，对系统资源的消耗较大的问题。现有技术公开的制滑动窗口移动的方法及装置，解决了当服务器没有事件被输入时，服务器的滑动窗口不会向后滑动，导致之前落在滑动窗口内的事件无法被处理输出的问题。现有技术公开的二次置换多项式(Quadratic PermutationPolynomial，QPP)交织器，对输入交织器的序列u_k以函数f(i)＝(f_1i+f_2i)mod(k)进行交织，以提高Turbo码的性能。现有技术公开的基于滑动窗口的网络编码方法，通过确定滑动窗口大小，并仅对滑动窗口内的数据分组进行编码，进一步提高了网络编码的可靠性，显著降低了解码复杂性，在实现快速网络编码的同时，从而使网络的数据吞吐量最大化，大大延长了网络生存期。

但是现有技术主要是利用置换多项式对交织器与Turbo码在一些领域中的应用，而在滑动窗口机制中，对滑动窗口的大小、滑动步调大小等缺少较强的理论支持。当网络中出现丢失数据分组时，会导致后面的一系列数据分组都不能立即传输，因此接收节点需要缓存大量的数据分组，同时滑动窗口的大小、数据的传输控制、解码系数矩阵的规模增大，解码的复杂度也就增加。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于二次置换多项式的滑动窗口网络编码方法，其目的在于提高网络编码的编/解码效率，从而实现最大化地提高网络的数据吞吐量以及延长网络生存期。

为实现上述目的，按照本发明的一个方面，提供了一种基于二次置换多项式的滑动窗口网络编码方法，包括如下步骤：

(1)确定无线网络中拟传输的数据分组大小；

(2)构造二次置换多项式；

(3)确定二次置换多项式的值以及滑动窗口的大小；

(4)拟传输数据分组进入到滑动窗口，将滑动窗口中的数据分组进行网络编码后传输；

(5)接收方对接收的网络编码进行解码，恢复出原始数据分组。

优选地，上述基于二次置换多项式的滑动窗口网络编码方法，网络编码是在有限域GF(2ⁿ)中随机选取源向量系数的线性组合，允许从中间节点输入组合数据分组，每个组合数据分组包含一个源数据分组的线性组合。

优选地，上述基于二次置换多项式的滑动窗口网络编码方法，将二次置换多项式p(x)定义为：p(x)＝ax²+bx，其中a、b、x都是非负整数，p(x)＝ax²+bx的模是N。

优选地，上述基于二次置换多项式的滑动窗口网络编码方法，所采用的二次置换多项式p(x)＝84x²+41x模112，即N＝112；该二次置换多项式p支持4个窗口大小，分别为56、28、14和7。

优选地，上述基于二次置换多项式的滑动窗口网络编码方法，根据滑动过程中的二次置换多项式对滑动窗口的大小进行调整以提高滑动窗口的性。

优选地，上述基于二次置换多项式的滑动窗口网络编码方法，拟传输数据分组进入到滑动窗口中重新组合的方法，具体如下：

对于网络节点传输矩阵G的行的一个线性组合子集R＝{G_q0,…,G_q|R|-1}，首先从滑动窗口开始边f^r计算相关的滑动窗口结果边e^r＝f^r+w-1；

编码向量

其中，c_i是一个随机数并且满足P{c_i＝1}＝1/2，

是指第i个滑动窗口，w是指滑动窗口的长度，r是指滑动窗口的开始值。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

本发明提供的基于二次置换多项式的滑动窗口网络编码方法，只对进入滑动窗口内的数据分组进行编码操作，减少了网络编/解码操作的复杂性和计算时间，实现了快速网络编码，从而最大化地提高了无线网络的数据吞吐量以及延长网络生存期。

附图说明

图1是本发明提供的基于二次置换多项式的滑动窗口网络编码方法的流程示意图；

图2是本发明实施例中的子窗口的长度与外部值示意图。

图3是本发明实施例中基于二次置换多项式的滑动窗口长度的滑动机制结构示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

实施例提供的基于二次置换多项式的滑动窗口网络编码方法，参照图1，包括如下步骤：

(1)确定无线网络中拟传输的数据分组大小；

(2)构造二次置换多项式；

(3)确定二次置换多项式的值以及滑动窗口的大小；

(4)拟传输数据分组进入到滑动窗口，将窗口中的数据分组进行网络编码后传输；

(5)接收方对接收的网络编码并进行解码，恢复出原始数据分组，直至所有数据分组均解码完。

以下结合具体实施例来进一步阐述。实施例中，将无线网络表示为一个无向图G＝(V,E)，其中V表示网络中的节点集，E表示链路集。每个链路e＝(i,j)∈E代表节点i与节点j之间直接相连，如果(i,j)∈E且(j,i)∈E，假设链路是对称的，两个链路是否相互干扰取决于所采用的干扰模型。

实施例中的网络编码过程是在有限域GF(2ⁿ)中随机选取源向量系数的线性组合。x₀,x₁,…,x_n-1表示与该节点相关联的源数据分组。线性网络编码允许从中间节点输入组合数据分组，每个组合数据分组包含一个源数据分组的线性组合。

实施例中，二次置换多项式p(x)定义为：p(x)＝ax²+bx，其中a、b、x都是非负整数，p(x)＝ax²+bx的模是N。

多项式p(x)＝ax²+bx(mod N)作为置换多项式的充要条件包括：

1)对所有的N≥2，gcd(b,N)＝1，N的每个素数因子都是a的因子；其gcd(b,N)表示两个正整数b和N的最大公约数。

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

二次置换多项式p(x)＝ax²+bx(mod N)在整数集Z_N上是不可约的，当且仅当N>gcd(N,2a)。

令p(x)＝84x²+41x模112，即N＝112，通过观察N＝112的因子，得出二次置换多项式p支持4个窗口大小，分别为56、28、14和7，用于同时访问2、4、8和16个外部值。

图2示意了N＝112时，并行访问方法的并行度为4，子窗口的长度为14时，外部值由最大无竞争的并行访问存储方法计算；每个单元格中的数字表示外部值e_i的索引(i＝0,1,2,…,111)。

图3示意了实施例中基于二次置换多项式的滑动窗口长度而提出的滑动机制结构。假设数据的长度为N个信息位，滑动窗口的长度为w信息位或w的整数倍数，其第i(1≤i≤N/w)个滑动窗口的滑动机制如图3所示；为了有效地提高滑动窗口的性能，根据滑动过程中的二次置换多项式对滑动窗口的大小进行调整；基于二次置换多项式的滑动窗口长度可以自适应地调整每个滑动窗口的长度，避免滑动窗口的长度过大或过小。

网络节点利用编码向量对数据分组进行编码，递归地执行编码操作并获得编码后的数据分组。

假设一个节点已经接收并存储了一个集合(a₁,X₁),(a₂,X₂),…,(a_m,X_m)，其中X_i表示信息符号，a_i是数据分组的附加编码向量。该节点选择一组系数e_i＝(e_i0,e_i1,…,e_im)，计算线性组合

根据线性组合生成一个新的编码分组包(a',X')。同源编码向量a'不是简单地等于e，因为这些系数与原始数据分组X＝(x₀,x₁,…,x_n-1)有关，通过比较，得到

在网络中的多个节点上重复进行编码、获取编码向量，生成网络编码数据分组。

拟传输数据分组进入到滑动窗口，在滑动窗口中将数据分组重新组合，具体如下：

每次开始传输数据分组时，网络节点传输矩阵G的行的一个线性组合子集。首先从滑动窗口开始边f^r并计算相关的滑动窗口结果边e^r＝f^r+w-1。设R＝{G_q0,…,G_q|R|-1}是矩阵G的行的集合，

和

和

分别表示滑动窗口

的开始边和结果边。编码向量g^r开始累积元素R的线性组合，即：

c_i是一个随机数并且满足P{c_i＝1}＝1/2。

在无线网络中基于二次置换多项式的滑动窗口网络编码方法中，初始化滑动窗口需要O(N)时间，找到滑动编码窗口需要O(e)时间，为每个t∈T构造一个滑动窗口需要O(eTN)时间，全局编码向量在一个滑动窗口中的编码需要O(T²N)时间，编码总时间为O(eT²N)。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种基于二次置换多项式的滑动窗口网络编码方法，其特征在于，包括如下步骤：

(1)确定无线网络中拟传输的数据分组大小；

(2)构造二次置换多项式；

(3)确定二次置换多项式的值以及滑动窗口的大小；

(4)拟传输数据分组进入到滑动窗口，将滑动窗口中的数据分组进行网络编码后传输；

(5)接收方对接收的网络编码进行解码，恢复出原始数据分组；

拟传输数据分组进入到滑动窗口中重新组合的方法，具体如下：

对于网络节点传输矩阵G的行的一个线性组合子集R＝{G_q0,…,G_q|R|-1}，首先从滑动窗口开始边f^r计算相关的滑动窗口结果边e^r＝f^r+w-1；

编码向量

其中，c_i是一个随机数并且满足P{c_i＝1}＝1/2，

是指第i个滑动窗口，w是指滑动窗口的长度，r是指滑动窗口的开始值。

2.如权利要求1所述的滑动窗口网络编码方法，其特征在于，网络编码是在有限域GF(2ⁿ)中随机选取源向量系数的线性组合，允许从中间节点输入组合数据分组，每个组合数据分组包含一个源数据分组的线性组合。

3.如权利要求1或2所述的滑动窗口网络编码方法，其特征在于，将二次置换多项式p(x)定义为：p(x)＝ax²+bx，其中a、b、x都是非负整数，p(x)＝ax²+bx的模是N。

4.如权利要求1或2所述的滑动窗口网络编码方法，其特征在于，所采用的二次置换多项式p(x)＝84x²+41x模112，即N＝112；该二次置换多项式p支持4个窗口大小，分别为56、28、14和7。

5.如权利要求1或2所述的滑动窗口网络编码方法，其特征在于，根据滑动过程中的二次置换多项式对滑动窗口的大小进行调整以提高滑动窗口的性能。

Images