A kind of sliding window network coding method based on twice replaced polynomialTechnical field
The invention belongs to network coding technique fields, more particularly, to a kind of sliding based on twice replaced polynomialWindow-Network coding method.
Background technique
Sliding window data disclosed in the prior art determines method and device, determines sliding window in the prior art to solveMouth at a time when include business datum statistical value, the data number obtained needed for used mode is more, to beingThe larger problem of the consumption for resource of uniting.The mobile method and device of sliding window processed, solves when service disclosed in the prior artWhen device does not have event to be entered, the sliding window of server will not be slided backward, and the event in sliding window is fallen in front of causingCan not output processed the problem of.(the Quadratic Permutation of twice replaced polynomial disclosed in the prior artPolynomial, QPP) interleaver, to the sequence u of input interleaverkWith function f (i)=(f1i+f2i) mod (k) is interleaved,To improve the performance of Turbo code.Network coding method based on sliding window disclosed in the prior art, by determining sliding windowSize, and only the data grouping in sliding window is encoded, the reliability of network code is further improved, is significantly reducedDecoding complexity, to make the data throughput maximization of network, substantially prolongs while realizing fast network codingNetwork lifetime.
But the prior art mainly utilizes application of the permutation polynomial to interleaver and Turbo code in some fields,And in sliding window mechanism, stronger theories integration is lacked to size, the sliding step size etc. of sliding window.When in networkWhen there is lost data packet, will lead to subsequent series of data packets cannot all transmit immediately, therefore receiving node needsA large amount of data grouping is cached, while the transmission control of the size of sliding window, data, the scale of desorption coefficient matrix increase,Decoded complexity is also increased by.
Summary of the invention
Aiming at the above defects or improvement requirements of the prior art, the present invention provides a kind of based on twice replaced polynomialSliding window network coding method is maximumlly improved its object is to improve the coding/decoding efficiency of network code to realizeThe data throughout and extension network lifetime of network.
To achieve the above object, according to one aspect of the present invention, a kind of cunning based on twice replaced polynomial is providedDynamic Window-Network coding method, includes the following steps:
(1) data packet size for intending transmission in wireless network is determined；
(2) twice replaced polynomial is constructed；
(3) value of twice replaced polynomial and the size of sliding window are determined；
(4) intend transmission data grouping and enter sliding window, after the data grouping in sliding window is carried out network codeTransmission；
(5) recipient is decoded received network code, recovers original data packet.
Preferably, the above-mentioned sliding window network coding method based on twice replaced polynomial, network code is limitedDomain GF (2n) in randomly select the linear combination of source vector coefficient, allow to input data splitting from intermediate node and be grouped, each groupClose the linear combination that data grouping includes the grouping of a source data.
Preferably, the above-mentioned sliding window network coding method based on twice replaced polynomial, by twice replaced polynomial p(x) is defined as: p (x)=ax2+ bx, wherein a, b, x are nonnegative integer, p (x)=ax2The mould of+bx is N.
Preferably, the above-mentioned sliding window network coding method based on twice replaced polynomial, it is used twice replacedMultinomial p (x)=84x2+ 41x mould 112, i.e. N=112；Twice replaced polynomial p 4 window sizes of support, respectively 56,28,14 and 7.
Preferably, the above-mentioned sliding window network coding method based on twice replaced polynomial, according in sliding processTwice replaced polynomial is adjusted the size of sliding window to improve the property of sliding window.
Preferably, the above-mentioned sliding window network coding method based on twice replaced polynomial, intend transmission data grouping intoEnter the method reconfigured into sliding window, specific as follows:
For a linear combination subset R={ G of the row of network node transmissions matrix Gq0,…,Gq|R|-1, first from cunningDynamic window starts side frCalculate relevant sliding window result side er=fr+w-1；
Coding vector
Wherein, ciIt is a random number and meets P { ci=1 }=1/2,Refer to that i-th of sliding window, w refer to cunningThe length of dynamic window, r refer to the initial value of sliding window.
In general, through the invention it is contemplated above technical scheme is compared with the prior art, can obtain down and showBeneficial effect:
Sliding window network coding method provided by the invention based on twice replaced polynomial, only to enter sliding windowInterior data grouping performs the encoding operation, and reduces the complexity of network coding/decoding operation and calculates the time, realizes quick netNetwork coding, to maximumlly improve the data throughout of wireless network and extend network lifetime.
Detailed description of the invention
Fig. 1 is the process signal of the sliding window network coding method provided by the invention based on twice replaced polynomialFigure；
Fig. 2 is the length and external value schematic diagram of the child window in the embodiment of the present invention.
Fig. 3 is the sliding mechanism structural representation of the sliding window length in the embodiment of the present invention based on twice replaced polynomialFigure.
Specific embodiment
In order to make the objectives, technical solutions, and advantages of the present invention clearer, with reference to the accompanying drawings and embodiments, rightThe present invention is further elaborated.It should be appreciated that the specific embodiments described herein are merely illustrative of the present invention, andIt is not used in the restriction present invention.As long as in addition, technical characteristic involved in the various embodiments of the present invention described belowNot constituting a conflict with each other can be combined with each other.
The sliding window network coding method based on twice replaced polynomial that embodiment provides, referring to Fig.1, including it is as followsStep:
(1) data packet size for intending transmission in wireless network is determined；
(2) twice replaced polynomial is constructed；
(3) value of twice replaced polynomial and the size of sliding window are determined；
(4) intend transmission data grouping and enter sliding window, transmitted after the data grouping in window is carried out network code；
(5) recipient to received network code and is decoded, and recovers original data packet, until all data pointGroup has decoded.
It is further described below in conjunction with specific embodiment.In embodiment, wireless network is expressed as a non-directed graph G=(V, E), wherein V indicates that the node collection in network, E indicate link set.Each link e=(i, j) ∈ E represents node i and node jBetween be connected directly, if (i, j) ∈ E and (j, i) ∈ E, it is assumed that link be it is symmetrical, whether two links, which interfere with each other, depends onIn used interference model.
Network code process in embodiment is in finite field gf (2n) in randomly select the linear combination of source vector coefficient.x0,x1,…,xn-1Indicate source data grouping associated with the node.Linear network encoding, which allows to input from intermediate node, to be combinedData grouping, each linear combination of the data splitting grouping comprising the grouping of a source data.
In embodiment, twice replaced polynomial p (x) is defined as: p (x)=ax2+ bx, wherein a, b, x are nonnegative integers,P (x)=ax2The mould of+bx is N.
Multinomial p (x)=ax2+ bx (mod N) includes: as the necessary and sufficient condition of permutation polynomial
1) to all N >=2, each prime factor of gcd (b, N)=1, N is the factor of a；Its gcd (b, N) is indicatedThe greatest common divisor of two positive integers b and N.
It 2) is each element of odd number, gcd (b, N/2)=1, N not equal to 2 to all a and b (a >=1, b >=1), a+bThe number factor is all the factor of a.
Twice replaced polynomial p (x)=ax2+ bx (mod N) is in set of integers ZNOn be it is irreducible, and if only if N > gcd(N,2a)。
Enable p (x)=84x2+ 41x mould 112, i.e. N=112 are obtained twice replaced multinomial by observing the factor of N=112Formula p supports 4 window sizes, and respectively 56,28,14 and 7 are used for while accessing 2,4,8 and 16 external values.
When Fig. 2 illustrates N=112, the degree of parallelism of concurrent access method is 4, when the length of child window is 14, external value byMaximum uncompetitive concurrent access storage method calculates；Digital representation external value e in each celliIndex (i=0,1,2,…,111)。
Fig. 3 illustrates the sliding window length in embodiment based on twice replaced polynomial and the sliding mechanism knot that proposesStructure.Assuming that the length of data is N number of information bit, the length of sliding window is w information bit or the integer multiple of w, i-th (1≤i≤ N/w) a sliding window sliding mechanism it is as shown in Figure 3；In order to effectively improve the performance of sliding window, according to sliding processIn twice replaced polynomial the size of sliding window is adjusted；Sliding window length based on twice replaced polynomial canTo be adaptively adjusted the length of each sliding window, avoid the length of sliding window excessive or too small.
Network node encodes data grouping using coding vector, after recursively executing encoding operation and obtaining codingData grouping.
Assuming that a node has received and stored a set (a1,X1),(a2,X2),…,(am,Xm), wherein XiTableShow information symbol, aiIt is the additional code vector of data grouping.The node selects one group of coefficient ei=(ei0,ei1,…,eim), meterCalculate linear combinationA new coding groups packet (a', X') is generated according to linear combination.Homologous coding vectorA' is not to be simply equal to e, because of these coefficients and original data packet X=(x0,x1,…,xn-1) related, by comparing, obtainIt arrivesRepeat coding on multiple nodes in a network, obtain coding vector, generates network code data pointGroup.
Quasi- transmission data grouping enters sliding window, reconfigures data grouping in sliding window, specific as follows:
When starting to transmit data grouping every time, a linear combination subset of the row of network node transmissions matrix G.First fromSliding window starts side frAnd calculate relevant sliding window result side er=fr+w-1.If R={ Gq0,…,Gq|R|-1It is matrix GRow set,WithWithRespectively indicate sliding windowBeginning while and when result.Coding vector grStart the linear combination of accumulation element R, it may be assumed thatciIt is a random number and meets P { ci=1 }=1/2.
In the wireless network in the sliding window network coding method based on twice replaced polynomial, sliding window is initializedO (N) time is needed, sliding coding window is found and needs O (e) time, construct a sliding window for each t ∈ T and need O(eTN) time, coding of the global coding vector in a sliding window need O (T2N) time, coding total time are O(eT2N)。
As it will be easily appreciated by one skilled in the art that the foregoing is merely illustrative of the preferred embodiments of the present invention, not toThe limitation present invention, any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention should all includeWithin protection scope of the present invention.