CN103532674B - The transmission coded method of a kind of file based on complex network - Google Patents

Abstract

The invention discloses a file transmission encoding method based on a complex network, which relates to the field of reliable transmission of wireless network data. The process is: count the size of the files to be transmitted, and group the files to be transmitted; select a degree distribution; generate new groups based on multiple groups of the original files to be output, that is, encoding symbols, so that the original files are encoded in the sequence of symbols The form is transmitted in the network; the present invention establishes the mapping relationship between the short ring structure in the LT code and its corresponding complex network structure, detects and avoids the short ring structure in the LT code encoding process to the greatest extent according to the complex network structure, and improves its translation. Based on the success probability of encoding, an efficient and reliable file transfer encoding scheme based on complex network is constructed. Especially for data transmission in a wireless channel with time-varying characteristics, the invention enables the receiving end to recover the original data after receiving less data, effectively improving the bandwidth utilization rate of the channel and reducing the transmission delay.

Description

A File Transfer Encoding Method Based on Complex Network

technical field

The invention relates to the field of reliable transmission of wireless network data, in particular to a method for transmitting files by adopting an LT code coding scheme based on a complex network-based short loop detection and avoidance algorithm.

Background technique

Luby Transform codes (abbreviated as LT codes) are a kind of digital fountain codes proposed by Luby in 2002 with no code rate. Its encoding and decoding performance directly depends on the degree distribution of its encoded symbols. The ideal soliton distribution can theoretically achieve optimal LT code encoding and decoding performance, that is, the number of encoding symbols required to recover K input symbols is K. However, since the LT code based on the ideal soliton distribution cannot guarantee that the number of elements in the preprocessing set is always 1 during the whole decoding process, the slight fluctuation of the preprocessing set causes the failure of the whole decoding process. In order to solve the above problems, Luby further proposed an LT code based on robust soliton distribution, which makes the number of elements in preprocessing stable within a range greater than 1 during the entire decoding process. The performance of LT codes based on robust soliton distribution is better than that of LT codes based on ideal soliton distribution, and has become a standard design method of LT codes. Most of the existing LT code coding schemes are improvements based on LT codes based on robust soliton distribution, such as LT codes based on suboptimal degree distribution, multi-objective optimized LT codes, and LT codes designed using chaos theory. In 2012, using the shortest average path length characteristic of scale-free networks, Zhao et al. proposed a class of LT codes with scale-free characteristics, which greatly improved the encoding and decoding efficiency and decoding success probability of LT codes. And on this basis, combined with the advantages of ideal soliton distribution in degree release probability, a class of LT codes with robust scale-free properties is proposed, which further improves the encoding and decoding performance of LT codes.

Researches in recent years have found that the appearance of short loops has a certain impact on the encoding (decoding) performance of LT codes. For the encoding process, the encoding symbols expect to obtain more information from the input symbols. However, the existence of short loops makes the information of the input symbols repeatedly transmitted to the encoding symbols, resulting in a waste of encoding symbols. In the article "Little Cycleelimination of Fountain codes using Distilling Correlative Columns" in 2008, Zhang et al proposed to use the method of extracting correlation columns to avoid the short cycle structure in LT codes, Zhou et al. The algorithm is used in the short loop detection and avoidance algorithm of the LT code, so that the data has a better decoding success probability in the ideal channel.

The above two methods are only proposed for the four-ring structure appearing in the Tanner diagram, and do not consider the influence of the short ring structure greater than or equal to six rings on the LT code. In addition, since the coded symbols of the LT code are generated on demand, when the channel condition is poor, the random generation of degrees will inevitably produce four-ring and six-ring structures. At this time, these two schemes change the original coded symbols degree distribution. As a result, decoding the same number of input symbols requires the transmission of more coded symbols and occupies more channel bandwidth. Therefore, the problem of maximizing the short cycle of LT codes is still an urgent problem to be solved.

Contents of the invention

In view of the deficiencies in the prior art, the purpose of the present invention is to provide a file transfer encoding method based on a complex network, which avoids the four-ring and six-ring structures of the LT code in the detection process, so as to overcome the problem of maximizing the short ring of the LT code. question.

The technical scheme of the present invention is achieved in that a kind of file transfer coding method based on complex network comprises the following steps:

Step 1: Count the size of the files to be transferred, and group the files to be transferred;

The grouping process is: divide the files to be transmitted into k groups evenly according to the bit order, where k is a positive integer, and k>10 ³ , if the amount of data in the last group is less than the average amount of data, then the group Fill the remaining bits with zeros;

Step 2: Select a degree distribution according to the value of k;

Step 3: Generate a new group based on the multiple groups of the original file to be output, that is, the encoding symbol, so that the original file is transmitted in the network in the form of an encoding symbol sequence;

Step 3.1: Generate the first encoding symbol;

Step 3.1.1: Randomly generate a value d from the degree distribution selected in step 2, randomly select d different groups in the original output file, where d is a natural number;

Step 3.1.2: XOR operation is performed on the d different groups to form a new group, which is the first coded symbol generated;

Step 3.1.3: Using the encoding symbol generated in step 3.1.2 as the initial node, generate a network structure consisting of one node;

Step 3.1.4: Put the coded symbol on the channel for transmission;

Step 3.2: Generate the next encoding symbol;

Step 3.2.1: According to the degree distribution in step 2, randomly generate another positive integer d′ from the degree distribution, randomly select a group from the k groups in the original file, and this group is the first choice for generating the next coding symbol The grouping of the selected original files is also the first optional grouping for generating the next encoding symbol. Add a new node to the network structure. If a grouping of the selected original file is a grouping that generates some or some existing coding symbols, then the relationship between this new node and the corresponding nodes of the above-mentioned one or some existing coding symbols in the network structure There are connected edges, and the weight of the edge is the serial number of a group of the selected original file in all the groups of k original files; if d'=1, then perform step 3.2.2; otherwise, perform step 3.2.3;

Step 3.2.2: XOR the grouping of an original file selected in step 3.2.1 with its equal-length all-zero bit sequence to form a new grouping, which is the next coded symbol generated, and place this coded symbol in Transmission in the channel, proceed to step 3.3;

Step 3.2.3: In all the groups of the original file, except for the selected group for generating the next encoding symbol, select another group of the original file in the remaining groups, which is another already selected group for generating the next encoding symbol. selected groups;

Step 3.2.4: Find out all existing coding symbols and their corresponding nodes in the network structure generated by another group participating in step 3.2.3, and check whether the new nodes in step 3.2.1 correspond to these corresponding nodes Edges exist. If there is no connecting edge, it shows that another grouping selected will not cause the four-ring structure of the LT code, then continue to perform from step 3.2.5; if there is a connecting edge, it shows that this other grouping will cause the four-ring structure of the LT code , this other packet is not an optional packet to generate the next encoded symbol. At this point, if there are still groups of unselected original files for generating the next coding symbol, then return to step 3.2.3 and continue to execute, otherwise continue to execute to step 3.2.9;

Step 3.2.5: Find out all existing coding symbols generated by another group in step 3.2.3 and their corresponding nodes in the network structure, and check whether the nodes that are connected to the new node in the network structure are connected to The existing coded symbols generated by another group are connected to the corresponding nodes in the network structure. If there is no connection or there is a connection and the weight of the side is equal to the sequence number of another group in all the groups of the original file, then it shows that another group will not cause the six-ring structure of the LT code, and this another group is to generate the next Optional grouping of encoding symbols, continue to step 3.2.6; if there is an edge, and the weight of the edge is not equal to the serial number of another group in the original file, it indicates that there is a six-ring structure, that is, the other The grouping will result in the six-ring structure of the LT code, this other grouping is not an optional grouping to generate the next encoded symbol. At this point, if there are still groups of unselected original files, then go back to step 3.2.3 and continue to execute; otherwise, continue to execute from step 3.2.9;

Step 3.2.6; find out all existing coding symbols generated by another group in step 3.2.3 and their corresponding nodes in the network structure, and add the edges connecting these corresponding nodes and new nodes in the network structure , the weight of the edge is the serial number of another group in all the groups of the original file;

Step 3.2.7: If the number of optional groups is equal to d', continue to execute from step 3.2.8, if the number of optional groups is less than d', then continue to execute from step 3.2.9;

Step 3.2.8: XOR these d′ groups to obtain a new group, which is the next coding symbol. Put the encoded symbol in the channel for transmission; perform step 3.3;

Step 3.2.9: If there are still groups of original files that have not been selected, repeat step 3.2.3; if there is no group that has not been selected, then select any group of the original file from the optional group until it is selected The number of groups is d'. These d' groups are XORed to generate a new group, that is, the next coded symbol, and the coded symbol is placed in the channel for transmission;

Step 3.3: Repeat the process of step 3.2 to generate the rest of the encoding symbols until the sending end receives the feedback information that the file has been correctly restored returned by the receiving end.

Beneficial effects of the present invention: the present invention establishes the mapping relationship between the short ring structure in the LT code and its corresponding complex network structure, detects and avoids the short ring structure in the LT code encoding process to the greatest extent according to the complex network structure, and improves its translation. Based on the success probability of encoding, an efficient and reliable file transfer encoding scheme based on complex network is constructed. Especially for data transmission in a wireless channel with time-varying characteristics, the invention enables the receiving end to recover the original data after receiving less data, effectively improving the bandwidth utilization rate of the channel and reducing the transmission delay.

Description of drawings

Fig. 1 is that the file that the number of bits is N=k L is divided into k grouping diagrams on average in the embodiment of the present invention;

Fig. 2 divides the file that the number of bits is N=k L-δ (δ<L) into k grouping schematic diagrams according to the embodiment of the present invention;

Fig. 3 is a schematic diagram of randomly generating degree value d according to an embodiment of the present invention;

Fig. 4 selects d=3 different grouping schematic diagrams in the original file according to the embodiment of the present invention;

FIG. 5 is a schematic diagram of a network G with only one node in the embodiment of the present invention;

Fig. 6 is a schematic diagram of the network structure after the second encoding symbol is generated according to the embodiment of the present invention;

Fig. 7 is a schematic diagram of a network structure of a four-ring structure if a group that generates the third coded symbol is selected as S ₂ in the embodiment of the present invention;

FIG. 8 is a schematic diagram of a network structure of a six-ring structure that selects a group that generates the fourth coded symbol as S ₄ according to an embodiment of the present invention;

Fig. 9 is a schematic diagram of the network structure formed after the fifth coded symbol is generated according to the embodiment of the present invention;

FIG. 10 is a flowchart of a complex network-based file transfer encoding method according to an embodiment of the present invention;

FIG. 11 is a flow chart of the first code generation process in the embodiment of the present invention;

Fig. 12 is a comparison curve of the decoding success probability between the LT code and the traditional LT code according to the embodiment of the present invention, where the number of blocks is 10 ⁴ .

detailed description

The embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings.

The complex network-based file transfer encoding method adopted in this embodiment is shown in FIG. 10 . Specific steps are as follows:

Step 1: Count the size of the files to be transferred, and group the files to be transferred.

If the data to be transmitted is a file, the file size will be counted first. In this embodiment, the fopen () function of the C language is used to open the file, the fseek () function is used to locate the pointer to the position of the file, and the ftell () function is passed Identify the position of the last byte to get the size of the file. If the data to be transmitted is a bit stream, the bit stream to be transmitted can be directly grouped. The grouping process is: divide the files to be transmitted into K groups evenly according to the bit order, where K is a positive integer, and K>10 ³ . Assuming that the file to be transmitted can be converted into a 2KB bit stream, the above method can be used to divide the bit stream into K=2000 groups, where each group contains L=8 bits. As shown in Figure 1, where

The first group: a total of 8 bits, the content is 01011000;

The second group: a total of 8 bits, the content is 10110011;

...

K=2000th packet: 8 bits in total, the content is 11100101.

In this embodiment, a 2KB (16000bit) file can be divided into exactly 2000 8bit groups. However, for some files, it cannot be exactly divided into multiple groups, that is, the data volume of the last divided group is smaller than the average data volume of the groups. At this time, it is necessary to pad zero at the end of the last packet, so that the number of bits contained in the last packet is equal to the average number of bits in each packet. For example: suppose a 15994bit file is grouped, but the bit stream is still divided into 2000 groups, each group contains L=8 bits of data, then the last group will be less than 8 bits, and we need to add 0 after it. As shown in Figure 2, where

The first group: a total of 8 bits, the content is 01011000;

The second group: a total of 8 bits, the content is 10110011;

...

K=2000th packet: 8 bits in total, the content is 11000000. Among them, the last 6 bits are padding bits.

After the above process, we can divide a 2KB file into 2000 groups.

Step 2: Select a degree distribution according to the value of the number of groups K;

The degree distribution can be a robust soliton distribution, a scale-free distribution and a robust scale-free distribution, etc. The degree distribution of the coding symbols of the existing common LT codes can be used, and the user can choose the distribution function according to his own needs . In this embodiment, the robust soliton distribution μ(d) is taken as an example to illustrate the determination process of the degree distribution as follows:

μ(d) is defined as follows,

$\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&tau;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; K</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&tau;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1,2</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

in

and

$\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; K</span>}}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 2,3</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; K</span>}\end{array}\right.$

In the formula, S is the expected number of remaining encoded symbols with degree 1 in each step of the decoding process:

$\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}\sqrt{\mathrm{<span\; class="notranslate">\; K</span>}}\mathrm{<span\; class="notranslate">\; ln</span>}\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

In the formula, β∈(0,1) is a free variable, and δ represents the tolerable decoding error probability when the receiver receives K encoded symbols.

For all values of K, a robust soliton distribution needs to satisfy the following formula:

${\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; K</span>}}\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}$

It is found that the LT code based on the robust soliton distribution has better performance when the parameters of the robust soliton distribution are β=0.1 and δ=1.0. Substituting β=0.1, δ=1.0 and K=10000 into formula (2), S=92.10 can be obtained. Furthermore, when K=10000, the degree distribution of coded symbols can be obtained.

Similarly, a similar method can be used to obtain the parameters in the scale-free distribution and the robust scale-free distribution, and determine the degree distribution of the LT code with a given K value.

Taking K=2000 groups divided into 2KB files in this embodiment as an example, substituting β=0.1, δ=1.0, and K=2000 into the formula (2) obtains the value of S as 33.99. Substituting the values of S and δ into the formula (1) can obtain the degree distribution based on the robust soliton indexing with the group number of 2000.

Step 3: On the basis of the 2000 groups of the original file to be output with a size of 2KB, a new group is generated, that is, an encoding symbol, so that the original file is transmitted in the network in the form of an encoding symbol sequence; the 2000 groups of the original file are called Enter the symbol. In order to simplify the description of this implementation process, only 5 input symbols out of 2000 input symbols are selected as an example to describe the generation process of part of the encoding symbols. These 5 sets of input symbols are recorded as S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ , where S ₁ =01011000, S ₂ =10110011, S ₃ =11100101, S ₄ =01011000, and S ₅ =10110010.

Step 3.1: Generate the first encoding symbol, as shown in Figure 11.

Step 3.1.1: In this embodiment, a value d ₁ is randomly generated according to the degree distribution selected in step 2, which is intended to be the degree of the first coded symbol. Select group d ₁ from the 5 groups of input symbols S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ to generate the first encoding symbol. _The selection process for the value d1 is as follows:

According to the degree distribution selected in step 2, the variable d in formula (1) takes different values of 1,...,K respectively to obtain the probability of encoding symbols with degrees 1,...,K. Since the encoding process of 5 out of 2000 groups is used as an example in this embodiment, here we assume K=5, and limit d to be an integer between [1,5]. First, divide the range of 0-1.0 into 5 segments according to this probability; then use the rand() function in C language to generate a random number, and determine which segment the random number is in the 5 segments of 0-1.0, In which segment, then what is the degree value of the first coding symbol selected in step 3.1.1. As shown in Figure 3, assume that the probability of degree 1 is 0.1, the probability of degree 2 is 0.4, the probability of degree 3 is 0.3, the probability of degree 4 is 0.15, and the probability of degree 5 is 0.05. Apply cumulative distribution, if the size of the random number is between 0 and 0.1, the selected degree value is 1; if the size of the random number is between 2 and 0.5, the selected degree value is 2; and so on.

At this point, assume that a random number with a value of 0.51 is generated, as shown in Figure 3, it can be seen that 0.51 is greater than 0.5 and less than 0.8, that is, it falls in the third segment. Therefore, the degree d of the _first coded symbol is proposed to be The assigned value is 2.

Three different groups are randomly selected from the 5 groups of the original file, and the probability of selecting any group of the original file is the same, and in this embodiment, the probability is 1/5.

In this embodiment, the rand() function in the C language is used to generate two random numbers, which are 0.29 and 0.17 respectively. They fall in the 2nd segment and the 1st segment as shown in Figure 4, therefore, the groupings of the 2 original files used to generate the first encoding symbol selected by this step are respectively the 1st grouping and the 2nd grouping.

Step 3.1.2: The first group in this embodiment is denoted as C ₁ , and the value of C ₁ is equal to the XOR of the two different original file groups selected in step 3.1.1. That is, C ₁ =S ₁ ⊕S ₂ =11101011;

Step 3.1.3: Take the encoding symbol generated in step 3.1.2 as the initial node, and generate a network structure G consisting of one node, as shown in Figure 5. In this embodiment, it refers to generating the network structure G with the node _V0 corresponding to the coding symbol _C1 . This step is mainly for initializing G, and the involved content mainly includes the initialization of G using the malloc() function in the C language. nodes and edges.

Step 3.1.4: Put the coded symbol C ₁ in the channel for transmission;

Step 3.2: In this embodiment, generate the second encoding symbol;

Step 3.2.1: According to the degree distribution in step 2, the degree d ₂ =1 of the second coded symbol is randomly selected from the 5 groups of S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ according to the degree distribution. Select 1 group, assuming that the selected group is S ₁ . Add a new node V ₁ to the network structure G, because S ₁ is a group that generates C ₁ , then there is an edge between the corresponding nodes V ₁ and V ₀ of C ₂ and C ₁ on G, and the edge The weight is S ₁ , as shown in FIG. 6 .

Since the degree value of the second coding symbol is 1, and the only group selected is S ₁ , the second coding symbol C ₂ =S ₁ =01011000 is generated by step 3.2. And put _C2 in the channel for transmission.

Step 3.3: In this embodiment, generate the third encoding symbol;

Step 3.3.1: Randomly select the degree of the _third coding symbol according to the degree distribution in step ₂ , _assuming its value is _{d 3} = ₃ , at this time we need Select 3 groups that meet the conditions from the 5 groups. The process is as follows:

Randomly select the first group to generate the third coding symbol from the five groups S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ , assuming that the selected group is S ₁ . Add a new node V ₂ in the network structure G, since S ₁ is a group of original files that generate C ₁ and C ₂ , then add a link in G that connects node V ₂ and node V ₀ with a weight of S ₁ , and an edge connecting node V ₂ and node V ₁ with weight S ₁ .

Randomly select a group from the four original file groups of S ₂ , S ₃ , S ₄ , and S ₅ as the second selected group for generating the third encoding symbol, assuming it is S ₂ . S ₂ participates in generating code symbol C ₁ , and at the same time, new node V ₂ has an edge with weight S ₁ to node V ₀ corresponding to C ₁ , as shown in FIG. 7 . Because of this, choosing S2 here will result in a four _- ring structure, which is not an optional grouping.

Randomly select a group S ₃ from the remaining groups S ₃ , S ₄ , and S _5. Since it does not form a four-ring and six-ring structure, S ₃ can be used as an option for generating the third coded symbol grouping. Then randomly select a group from the remaining groups S ₄ and S ₅ , assuming it is S ₄ , and find that if S ₄ is placed in a complex network structure, it will not form a four-ring or six-ring structure, so S ₄ can also be used as a generator An optional grouping of 3rd encoded symbols.

Therefore, the third coding symbol C ₃ can be obtained by XOR of the three coding symbols S ₁ , S ₃ , and S ₄ , that is, C ₃ =S ₁ ⊕S ₃ ⊕S ₄ =01100101, put the coding symbol C ₃ Transmit in the channel.

Step 3.4: In this embodiment, generate the fourth coding symbol C ₄ ;

Step 3.4.1: Randomly select the degree of the fourth coding symbol according to the degree distribution in step 2, assuming its value d ₄ =2, at this time we need to be in S ₁ , S ₂ , S ₃ , S ₄ , S ₅ these 5 Select 2 groups that meet the criteria from the groupings. The process is as follows:

Randomly select the first group to generate the fourth coding symbol from the five groups S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ , assuming that the selected group is S ₂ . Add a new node V ₃ in the network structure G, since S ₂ is a group of an original file that generates the coding symbol C ₁ , therefore, the weight of adding a link between node V ₃ and node V ₀ in G is S ₂ even side.

Randomly select a group S ₄ from the remaining 4 groups S ₁ , S ₃ , S ₄ , and S ₅ as the second selected group for generating the fourth coding symbol. Because in the network structure G, there is an edge between the node V ₀ connected to the new node V ₃ and the node V ₂ corresponding to the existing code symbol C ₃ generated by the group S ₄ , and the weight of the edge is S ₁ ≠ S ₄ , as shown in Fig. 8 . Therefore, choosing S4 here will result in a six _- ring structure, that is, S4 is not an optional group to generate _{C4 .}

Randomly select a group from the remaining three groups S ₁ , S ₃ , and S ₅ , assuming that the selected group is S ₅ , that is, S ₅ is the next selected group for generating the fourth coded symbol. Since S ₅ does not form a four-ring structure and a six-ring structure, S ₅ is another optional group for generating the coding symbol C ₄ .

Through step 3.4, the fourth coding symbol C ₄ =S ₂ ⊕S ₅ =00000001 is generated in this embodiment. Put coded symbol C ₄ into the channel for transmission.

Step 3.5: In this embodiment, generate the fifth coding symbol C ₅ ;

According to the degree distribution in step 2, the degree of the fifth coding symbol is randomly selected, assuming its value d ₅ =2, at this time, it is necessary to select among the five groups of S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ to meet the conditions 2 groups of . The process is as follows:

Randomly select a group from the five groups S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ as an optional group for generating the fifth code symbol, assuming that the group is S ₃ . Add a new node V ₄ in G, because S ₃ participates in generating coded symbol C ₃ , therefore, add an edge connecting nodes V ₂ and V ₄ whose weight is S ₃ in G.

Randomly select one group from the remaining four groups S ₁ , S ₂ , S ₄ , and S ₅ , assuming it is S ₂ . Since the node V ₂ that has an edge with the new node V ₄ in G has an edge with the node V ₀ corresponding to the code symbol C ₁ generated by S ₂ in G, and the weight of the edge is S ₁ ≠ S ₂ , therefore , if S2 is used as an optional group here, a six _- ring structure will be formed.

Randomly select one group from the remaining three groups S ₁ , S ₄ , and S ₅ , assuming it is S ₁ , as the selected group. Since the code symbol C3 that S1 participates in generating corresponds to the node V2 in G and the new node _V4 has _an edge with a weight _of S3, therefore, S1 as _an optional group will form a _{four -} ring structure.

Randomly select one group from the remaining two groups S ₄ and S ₅ as the next selected group for generating code symbol C ₅ , assuming it is S ₄ . Since the code symbol C3 that S4 participates in generating corresponds to the node V2 in G and the new node _V4 has an edge with a weight _{of S3} , therefore, if S4 is used as an optional group, a _{four -} ring structure will be formed _.

Randomly select a group from the remaining group S ₅ , which is S ₅ , if S ₅ is selected here, neither a four-ring structure nor a six-ring structure will be formed, so S ₅ is to generate coding symbols An optional grouping of C ₅ . Since S ₅ participates in generating coded symbol C ₄ , an edge connecting nodes V ₃ and V ₄ with a weight of S ₅ is added to G. As shown in Figure 9.

Through step 3.5, in this embodiment, the fifth encoded symbol C ₅ =S ₃ ⊕S ₅ =01010111 is generated, and C ₅ is transmitted in the channel.

Step 3.6: In this embodiment, generate the sixth coding symbol C ₆ ;

Randomly select the degree of the sixth coded symbol according to the degree distribution in step 2, assuming its value d ₆ =3. At this time, it is necessary to select 3 groups satisfying the conditions among the 5 groups S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ . The process is as follows:

Randomly select a group from the five groups S ₁ , S ₂ , S ₃ , S ₄ , and S ₅ as an optional group for generating the sixth code symbol, assuming that the group is S ₂ . Add a new node V ₅ in G, because S ₂ participates in generating coded symbols C ₁ and C ₄ , therefore, add connection V ₅ in G, the weight of V ₀ is the edge connected with S ₂ and connection V ₅ , the weight of V ₃ is the edge of S ₂ .

Randomly select one group from the four groups S ₁ , S ₃ , S ₄ , and S ₅ as the second selected group for generating the sixth code symbol, assuming that the group is S ₁ . Since in the network structure G, the code symbol C ₁ that S ₁ participates in generating corresponds to the node V ₀ in G and the new node V ₅ has an edge with a weight of S ₂ , therefore, if S ₁ is selected here, it will resulting in a four-ring structure.

Randomly select one group from the remaining three groups S ₃ , S ₄ , and S ₅ as the third selected group for generating C ₆ , assuming that the group is S ₃ . Since there is an edge between the node V ₀ and S ₃ in G that has an edge with the new node V ₅ and the code symbol C ₃ that is generated by the corresponding node V ₂ in G, and the weight of the edge is S ₁ ≠ S ₃ , Therefore, _S3 is not an optional packet here.

Randomly select a group from the remaining two groups S ₄ and S ₅ as the fourth selected group for generating C ₆ , assuming it is S ₄ . Since the code symbol C3 generated by the nodes V ₀ and S ₄ that have an edge with the new node V ₅ in G has _{an edge between the corresponding node V 2 in G and the weight of the edge is S 1 ≠ S 4} , Therefore, if S4 is used as an optional group here, it will constitute a six _- ring structure.

Analyzing the last group S ₅ , since the node V ₃ corresponding to the coding symbol C ₄ generated by S ₅ in G already has an edge with the weight of S ₂ to the new node V ₅ , therefore, S ₅ as an optional group will resulting in a four-ring structure.

In summary, if the first group selected to generate the sixth coding symbol is S ₂ , no matter whether S ₁ , S ₃ , S ₄ or S ₅ is selected, a short ring structure will result. At this time, randomly select 2 groups from the 4 groups of S ₁ , S ₃ , S ₄ , and S ₅ except S ₂ , assuming that they are S ₁ and S ₄ , as the other two options for generating coded symbols C ₆ group.

Obtain the sixth coded symbol C ₆ =S ₂ ⊕S ₁ ⊕S ₄ =10110011 through step 3.6, put C6 in the channel for transmission.

Through the above process, 6 coding symbols are generated, all of which are generated by 5 groups in the original file. In this embodiment, for the original file containing 2000 groups, the same method can also be used to generate the encoding symbol sequence. At the receiving end, the original file is recovered according to the value of the encoding symbol and the relationship between the encoding symbol and multiple groups of the original file.

The present invention can be directly applied to the reliable transmission of large data volume data such as video and images in wireless channels. In order to facilitate the verification of the feasibility and advantages of the method, here only from the perspective of decoding success probability and the traditional LT code encoding scheme Conduct comparative analysis.

The present invention takes 1000 sets of LT codes with robust scale-free characteristics and LT codes based on robust soliton distribution with 1000 groups of input symbols as 10 ⁴ and 1 bit as an example to verify the effectiveness of the present invention. The LT codes participating in the comparison Code includes;

(1) RD-SF (cycle-6priority): parameter selection P ₁ =0.1, λ=1.9, minimize LT codes with four-ring and six-ring structures with robust scale-free properties;

(2) RD-SF (cycle-4priority): parameter selection P ₁ =0.1, λ=1.9, reduce the fourth ring as far as possible, do not consider the LT code with robust scale-free characteristics of the six rings;

(3) RD-SF (random): parameter selection P ₁ =0.1, λ=1.9, LT codes with robust scale-free properties regardless of four-ring and six-ring;

(4) RSD (cycle-6priority): parameter selection c=0.1, δ=1, minimize the LT code based on the robust soliton distribution of the four-ring and six-ring structure;

(5) RSD (cycle-4priority): parameter selection c=0.1, δ=1, minimize the fourth ring, and do not consider the LT code based on the robust soliton distribution of the six rings;

(6) RSD (random): parameter selection c=0.1, δ=1, LT code based on robust soliton distribution without considering the fourth and sixth rings.

This invention does not change the degree distribution of coded symbols, so the average number of XORs needed to generate coded symbols is not much different from the original coding scheme, but the number of coded symbols needed to recover the same input symbols is reduced due to the reduced probability of four-ring and six-ring occurrence will be reduced, so that the average number of exclusive OR times in the decoding process of this scheme is reduced. Table 1 shows the comparative relationship of redundancy factors in different coding schemes. The lower the redundancy factor, the fewer encoding symbols are needed to restore the original input symbols, and the lower the decoding delay is:

Table 1 Performance comparison between the LT code constructed in this embodiment and the traditional LT code

Analysis of Table 1 shows that the average redundancy factor of LT codes using the six-ring priority algorithm is smaller than the average redundancy factor of LT codes using the four-ring priority algorithm, and they are all smaller than the average redundancy factor of LT codes without short-ring optimization, so LT codes using short-cycle avoidance algorithm need less coding symbols to recover the same number of input symbols than LT codes without short-cycle optimization.

Since the degree of each encoded symbol is generated independently, and the LT code with robust scale-free properties and the LT code based on the ideal soliton distribution can ensure that the receiver can completely decode as long as it receives enough encoded symbols, it is different from the transmitted data Therefore, only the decoding success probability of the LT code under the ideal channel condition is considered here by applying the short loop avoidance algorithm based on the complex network theory.

Fig. 12 shows that the number of input symbols is 10 ⁴ , and 1000 groups of the above six kinds of LT codes are respectively constructed, and the relationship between their decoding success probability and redundancy factor is obtained.

Analyzing Figure 12, it can be seen that under the premise of the same redundancy factor, the decoding success probability of the LT code with robust scale-free characteristics generated by applying the short-loop avoidance algorithm is higher than that of the LT code with robust scale-free characteristics without considering the short-loop structure. code and three other LT codes based on robust soliton distribution. However, for the LT code based on the robust soliton distribution generated by the short-loop avoidance algorithm, the receiving end receives the same number of coded symbols N=(1+α)K, and the decoding success probability is higher than that based on the robust soliton distribution without considering the short-loop structure. LT code.

The above research shows that the LT code designed by using the short loop avoidance algorithm can greatly improve the decoding success probability under the premise of ensuring the encoding (decoding) efficiency.

Although the specific embodiments of the present invention have been described above, those skilled in the art should understand that these are only examples, and various changes or modifications can be made to these embodiments without departing from the principles and principles of the present invention. substance. The scope of the invention is limited only by the appended claims.

Claims (1)

1. file based on a complex network transmission coded method, it is characterised in that: comprise the following steps:

Step 1: add up file size to be transmitted, is grouped file waiting for transmission；

Described grouping process is: by bit order, file to be transmitted is divided into k group, and wherein, k is positive integer, and k ＞ 10³If the data volume in last packet is less than average amount, then by the remaining bits position zero padding in this packet；

Step 2: select a degree distribution according to k value；

Step 3: generate new packet, i.e. coded identification in multiple packet by packet basis of original to be output, makes original to compile The form of code sign sequence is transmitted in a network；

Step 3.1: generate first coded identification；

Step 3.1.1: degree distribution one value d of stochastic generation selected by step 2, randomly chooses d not in former output file Same packet, wherein, d is natural number；

Step 3.1.2: this d different packet carries out XOR, forms one new packet, this packet is just for the of generation One coded identification；

Step 3.1.3: the coded identification that generated with step 3.1.2, as start node, generates one and is made up of a node Network structure；

Step 3.1.4: this coded identification is put and transmits in the channel；

Step 3.2: generate next coded identification；

Step 3.2.1: be distributed according to the degree of step 2, this degree be distributed stochastic generation another positive integer d ', at random from original K packet in select a packet, this is grouped into first original selected generating the selection of next coded identification Packet, be also first the optional packet generating next coded identification；Add a new node in the network architecture, if choosing One packet of the original selected be generate other certain or some there is a packet of coded identification, then, this is new Even limit, and the power on limit is had between the node that node is the most corresponding with above-mentioned certain or some already present coded identification Value is the sequence number in a packet being grouped in all k originals of the original selected；If d '=1, then perform step 3.2.2；Otherwise perform step 3.2.3；

Step 3.2.2: all zero bit sequence isometric with it that be grouped of the original that step 3.2.1 selects carries out XOR, Forming a new packet, this is grouped into the next coded identification of generation, this coded identification is put and transmits in the channel, arrives Step 3.3 continues executing with；

Step 3.2.3: in all packets of original in addition to for generating the packet that next coded identification had been selected, remaining Selecting another packet of original in packet, this is grouped into another packet selected generating next coded identification；

Step 3.2.4: find out that all another packets by step 3.2.3 participate in generating exist coded identification and Node corresponding in network structure, checks that the node that the new node in step 3.2.1 is the most corresponding with these exists even limit, if not There is even limit, show that another packet selected does not results in the tetracyclic structure of LT code, then continue executing with from step 3.2.5；If There is even limit, then show that this another packet will result in the tetracyclic structure of LT code, this another packet is not to generate the next one to compile The optional packet of code sign, now, if yet suffering from the packet of the original into generating the next the most selected mistake of coded identification, then Return to step 3.2.3 continue executing with, otherwise arrive step 3.2.9 and continue executing with；

Step 3.2.5: find out that all another packets by step 3.2.3 participate in generating exist coded identification and Node corresponding in network structure, checks whether the node that there is even limit in the network architecture with new node participates in another packet There is even limit in the node that there is coded identification correspondence in the network architecture of generation, if there is not even limit or existence to connect limit also And the weights on limit are grouped in the sequence number in all packets of original equal to another, then show that another packet does not results in Six ring structures of LT code, this another be grouped into the optional packet generating next coded identification, continue executing with to step 3.2.6； If there is even limit, and the weights connecting limit are not equal to another sequence number being grouped in the packet of original, then show to have six Ring structure, i.e. this another packet will result in six ring structures of LT code, and this another packet is not to generate next coded identification Optional packet, now, if yet suffering from the packet of the original of the most selected mistake, then returns to step 3.2.3 and continues executing with；Otherwise, Continue executing with from step 3.2.9；

Step 3.2.6: find out that all another packets by step 3.2.3 participate in generating exist coded identification and Node corresponding in network structure, adds the node of these correspondences and the company limit of new node in the network architecture, and the weights on limit are Another is grouped in the sequence number in all packets of original；

Step 3.2.7: if optional grouping number continues executing with from step 3.2.8, if optional grouping number is less than equal to d ' D ' is individual, then continue executing with from step 3.2.9；

Step 3.2.8: the individual packet of this d ' carries out XOR and obtains a new packet, what this was new is grouped into next coding symbol Number, this coded identification is put and is transmitted in the channel；Perform step 3.3；

Step 3.2.9: if yet suffering from the packet of the original of the most selected mistake, then repeat step 3.2.3；If it is the most selected The packet crossed, then arbitrarily select the packet of original beyond optional packet, until selected packet count is d '；This The individual packet of d ' carries out XOR and generates a new packet, i.e. next coded identification, and puts to enter in the channel by this coded identification Row transmission；

Step 3.3: the process of repeated execution of steps 3.2, generates remaining coded identification, until transmitting terminal receives receiving terminal and returns Back to the feedback information that the most correctly recovers of file till.