CN109495213A - A kind of broadcast repeating method and system based on Hamming weight coding - Google Patents

Abstract

The invention discloses a broadcast retransmission method and system based on Hamming weight coding. The method includes: S1, a satellite light source node broadcasts M information packets to N receiving ends at a fixed interval; S2, the satellite light source node broadcasts M information packets to N receiving ends; After the receiving end broadcasts M original information packets, each receiving end sends an ACK/NACK control packet to the satellite light source node to feedback its loss situation; S3. The satellite light source node records whether it has lost the information packet according to the number of lost information packets fed back by the receiving end. In the feedback matrix W; S4. According to the packet loss distribution data recorded in the feedback matrix W, the satellite light source node encodes and combines the information packets lost by the receiving end through Hamming weight coding, and broadcasts and resends it to all receiving ends. In the method and system provided by the present invention, the Hamming weight coding method is used to encode and combine the information packets, and the new encoded information packets are retransmitted, so that the receiving end can recover its loss from the less retransmission process in an optimal way. information package.

Description

A method and system for broadcast retransmission based on Hamming weight coding

technical field

The invention relates to the field of satellite optical communication, in particular to a method and system for broadcast retransmission based on Hamming weight coding.

Background technique

With the development of satellite optical communication technology and the huge increase in the amount of social transmission information, the packet error rate of the channel also increases, which cannot guarantee the fast and timely transmission of information. Therefore, the characteristics of broadcast retransmission technology make network coding have a good application in improving the transmission rate. Ho et al. proposed a method of applying random linear network coding in finite fields, and concluded that random linear network coding can improve the efficiency of the transmission process and reduce the overhead. Katti et al. proposed an opportunistic network coding method COPE. The COPE protocol requires each node to use the known self-information to determine which packets need to be encoded and how to encode the existing packets. For wireless broadcast networks, Gou Liang et al. proposed a weighted broadcast retransmission scheme WONCR based on opportunistic network coding in wireless networks. The scheme constructs a weighted packet distribution matrix to XOR-encode the packets to be encoded and transmit the encoded packets through the channel. Fan et al proposed to use the search method to generate retransmission coded packets through coding for all lost information packets. Sengupta et al. proposed a network coding protocol for wireless mesh networks, which theoretically shows that if a reasonable combination of coding is performed, the maximum network throughput can be obtained. Xiao Xiao et al. proposed a wireless network broadcast retransmission method NCWBR based on network coding. This algorithm has a large delay in the retransmission process.

In the above scheme, the existing broadcast retransmission algorithm has complex operations, low transmission efficiency, and poor robustness when encoding information packets, and the encoded information packets generated by it can be decoded by all receiving nodes, so that a large number of encoding opportunities are used. waste.

SUMMARY OF THE INVENTION

Aiming at the defects existing in the prior art, the purpose of the present invention is to provide a method and system for broadcast retransmission based on Hamming weight coding. The encoded packets are retransmitted, so that the receiver can recover its lost packets in an optimal way from the fewer retransmissions.

For achieving the above object, the technical scheme adopted in the present invention is as follows:

A broadcast retransmission method based on Hamming weight coding, comprising:

S1. The satellite light source node broadcasts M information packets to N (N≥2) receiving ends at a fixed interval period Δt. The satellite light source node and the receiving end obey Bernoulli distribution, and their packet loss rates are mutually exclusive. independent;

S2. After the satellite light source node broadcasts M original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation, where the loss situation includes: whether the information packet is lost, and The label of the lost packet and the label of the lost node;

S3. According to the number of lost information packets fed back by the receiving end, the satellite light source node records whether the information packets are lost or not in the feedback matrix W, wherein the feedback matrix W is an N×M matrix, and the row represents N(N≥ 2) receivers, the column represents M packets, W(i,j)=1 indicates that the ith receiver Ti has not received the jth packet Pj, and W(i,j)=0 represents the ith packet Pj The receiver Ti receives the jth information packet Pj;

S4, according to the packet loss distribution data recorded in the feedback matrix W, the satellite light source node encodes and combines the information packets lost by the receiving end through Hamming weight coding, and broadcasts and resends it to all the receiving ends until all the receiving ends are received. both ends recover their lost packets.

Further, a kind of broadcast retransmission method based on Hamming weight coding as above, step S4 comprises:

S41. Calculate the Hamming weight value Yi of each column of information packets in the feedback matrix W (0≤Yi≤N, 1≤i≤M), and according to the calculated Hamming weight values for the information packets of the M columns from large to Arrange the small ones, and update the feedback matrix W;

S42, according to the batch sending strategy, calculate the number of batches required for the information packets, and divide the information packets contained in each batch according to the calculated Hamming weight value:

If the Hamming weight value Yi=N, divide it into a batch separately;

If the Hamming weight value Yi<N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Yi≤N-s and meet the coding conditions into one batch until the required batch is completed;

S43. For each batch of information packets, adaptively encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets, and then start searching from the remaining information packets. Satisfy the sending policy, that is, assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. If s=N at this time, the code combines the two information The packet is broadcast and retransmitted;

S44. Update the feedback matrix W in time according to the receiving condition of the receiving end. If the new matrix is a non-zero matrix, repeat step S43 until the feedback matrix W is an all-zero matrix.

Further, in the above-mentioned broadcast retransmission method based on Hamming weight coding, the coding condition is: assuming that during the Mth retransmission, For the encoding combination package, the Hamming weight values corresponding to P1, P2, P3,..., Pn, Pk are Y1, Y2, Y3,..., Yn, Yk, if and only if the receiving end Ti has only one message In the case of packet loss, only one original information packet can be decoded. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2+Y3+...Yn=Yk.

Further, the above-mentioned broadcast retransmission method based on Hamming weight coding, because the channel between the satellite light source node and the receiving end has consistent statistical properties, when the number of information packets M is large enough, it can be considered that all The number of lost packets generated by the satellite light source node after a single batch of packets is sent is roughly the same, namely:

T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L )

Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of information packets that the satellite light source node needs to broadcast is:

Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤i) represents the i-th transmission The probability of successful reception of the latter receiver k, namely:

in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is

A broadcast retransmission system based on Hamming weight coding, comprising: a satellite light source node and N (N≥2) receivers,

The satellite light source node is used to broadcast M information packets to N (N≥2) receiving ends at a fixed interval period Δt, the satellite light source node and the receiving end obey Bernoulli distribution, and the packets are lost. rates are independent of each other;

The satellite light source node is also used to broadcast M original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation, and the loss situation includes: whether the information packet is lost, and the label of the lost packet and the label of the lost node;

The satellite light source node is also used to record whether the lost information packets are lost in the feedback matrix W according to the number of lost information packets fed back by the receiving end, wherein the feedback matrix W is an N×M matrix, and the row represents N (N ≥2) receivers, the column represents M packets, W(i,j)=1 indicates that the ith receiver Ti has not received the jth packet Pj, and W(i,j)=0 represents the ith packet Pj A receiver Ti receives the jth information packet Pj;

The satellite light source node is also used to encode and combine the information packets lost by the receiving end according to the packet loss distribution data recorded in the feedback matrix W by means of Hamming weight coding, and broadcast and resend to all the receiving ends until all the until the receiver recovers its lost packets.

Further, in the above-mentioned broadcast retransmission system based on Hamming weight coding, the satellite light source node is specifically used for:

Calculate the Hamming weight value Y _i of each column of information packets in the feedback matrix W (0≤Y _i ≤N, 1≤i≤M), according to the calculated Hamming weight values for the M column information packets from large to Arrange the small ones, and update the feedback matrix W;

According to the batch sending strategy, the number of batches required for the packet is calculated, and the packets contained in each batch are divided according to the calculated Hamming weight value:

If the Hamming weight value Y _i =N, divide it into a batch separately;

If the Hamming weight value Y _i <N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Y _i ≤ Ns and meet the coding conditions into a batch until the required batch is completed ;

For each batch of information packets, firstly encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets adaptively, and then start searching from the remaining information packets. The strategy is to assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. broadcast retransmission;

The feedback matrix W is updated in time according to the reception situation of the receiving end. If the new matrix is a non-zero matrix, the encoding sub-module is repeatedly executed until the feedback matrix W is an all-zero matrix.

Further, in the above-mentioned broadcast retransmission system based on Hamming weight coding, the coding condition is: assuming that during the Mth retransmission, For the encoding combination package, the Hamming weight values corresponding to P1, P2, P3,..., Pn, Pk are Y1, Y2, Y3,..., Yn, Yk, if and only if the receiving end Ti has only one message In the case of packet loss, only one original information packet can be decoded. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2+Y3+...Yn=Yk.

Further, the above-mentioned broadcast retransmission system based on Hamming weight coding, because the channel between the satellite light source node and the receiving end has consistent statistical properties, when the number of information packets M is large enough, it can be considered that all The number of lost packets generated by the satellite light source node after a single batch of packets is sent is roughly the same, namely:

T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L )

Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of information packets that the satellite light source node needs to broadcast is:

Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤i) represents the i-th transmission The probability of successful reception of the latter receiver k, namely:

in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is

The beneficial effects of the present invention are: in the method and system provided by the present invention, the Hamming weight coding method is used to encode and combine the information packets, and then the satellite light source node retransmits the new encoded information packets, which is compared with the traditional automatic request for retransmission. The Hamming weight coding method enables the receiver to recover its lost packets in an optimal way from fewer retransmissions.

Description of drawings

1 is a schematic flowchart of a broadcast retransmission method based on Hamming weight coding provided in an embodiment of the present invention;

2 is a schematic diagram of information packet feedback provided in an embodiment of the present invention;

FIG. 3 is a schematic diagram of an information packet batch sending strategy provided in an embodiment of the present invention;

4 is a schematic diagram of updating a feedback matrix provided in an embodiment of the present invention;

5 is a schematic diagram of encoding condition judgment provided in an embodiment of the present invention;

6(a)-(c) are schematic diagrams showing the performance comparison between the Hamming weight coding algorithm, the NCWBR algorithm and the ARQ algorithm provided in the embodiment of the present invention.

Detailed ways

The present invention will be further described in detail below with reference to the accompanying drawings and specific embodiments.

As shown in Figure 1, a broadcast retransmission method based on Hamming weight coding includes:

S1. The satellite light source node broadcasts M information packets to N (N≥2) receivers at a fixed interval period Δt. The satellite light source node and the receiver obey Bernoulli distribution, and their packet loss rates are independent of each other;

S2. After the satellite light source node broadcasts M original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation. The loss situation includes: whether the information packet is lost, and the label and number of the lost information packet. The label of the missing node;

S3. According to the number of lost information packets fed back by the receiving end, the satellite light source node records whether the information packets are lost or not in the feedback matrix W, where the feedback matrix W is an N×M matrix, and the rows represent N (N≥2) receiving end, the column represents M information packets, W(i,j)=1 means that the ith receiving end Ti has not received the jth information packet Pj, W(i,j)=0 means that the ith receiving end Ti receives to the jth packet Pj;

S4. According to the packet loss distribution data recorded in the feedback matrix W, the satellite light source node encodes and combines the information packets lost by the receiving end by means of Hamming weight coding, and re-sends the broadcast to all the receiving ends until all the receiving ends restore their until the packet is lost.

Step S4 includes:

S41. Calculate the Hamming weight value Yi (0≤Yi≤N, 1≤i≤M) of each column of information packets in the feedback matrix W, and perform the operations on the M column information packets from large to small according to the calculated Hamming weight values Arrange, update the feedback matrix W;

S42, according to the batch sending strategy, calculate the number of batches required for the information packets, and divide the information packets contained in each batch according to the calculated Hamming weight value:

If the Hamming weight value Yi=N, divide it into a batch separately;

If the Hamming weight value Yi<N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Yi≤N-s and meet the coding conditions into one batch until the required batch is completed;

S43. For each batch of information packets, adaptively encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets, and then start searching from the remaining information packets. Satisfy the sending policy, that is, assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. If s=N at this time, the code combines the two information The packet is broadcast and retransmitted;

S44. Update the feedback matrix W in time according to the receiving condition of the receiving end. If the new matrix is a non-zero matrix, repeat step S43 until the feedback matrix W is an all-zero matrix.

The coding conditions are: assuming that during the Mth retransmission, For the encoding combination package, the Hamming weight values corresponding to P1, P2, P3,..., Pn, Pk are Y1, Y2, Y3,..., Yn, Yk, if and only if the receiving end Ti has only one message In the case of packet loss, only one original information packet can be decoded. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2+Y3+...Yn=Yk.

Since the channel between the satellite light source node and the receiver has consistent statistical properties, when the number of information packets M is large enough, it can be considered that the number of lost information packets generated by the satellite light source node after a single batch of information packets is sent is roughly same, i.e.:

T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L )

Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of packets that the satellite light source node needs to broadcast is:

Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤ i) means that the i-th transmission is received after the The probability of successful reception of terminal k, namely:

in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is

Example 1

S101, the satellite light source node broadcasts M information packets to N (N≥2) receiving ends at a fixed interval period Δt, the satellite light source node and the receiving end obey Bernoulli distribution, and their packet loss rates are independent of each other, That is, the packet loss rate of the receiving end i (1≤i≤N) is R _i (0≤R _i ≤1);

S102. After the satellite light source node broadcasts K original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation: (1) whether the information packet is lost; (2) the label of the lost information packet and the label of the lost node;

S103: The satellite light source node records in the feedback matrix W whether it has lost information packets according to the number of lost information packets fed back by the receiving end. The matrix is an N×M matrix, where the rows represent N (N≥2) receivers, and the columns represent M packets. W(i,j)=1 means that the receiving end Ti has not received the information packet Pj, and W(i,j)=0 means that the receiving end Ti has received the information packet Pj;

S104, according to the packet loss distribution data recorded in the feedback matrix W, the satellite light source node encodes the packet lost by the receiver, and broadcasts it to all receivers again, until all receivers recover their lost packets;

S105. Given the receiving end Ti and the encoding package Pj, if the element W(i, j) at the position of the row and column in the feedback matrix W is equal to 0, it means that Ti has received all the information packets participating in the encoding combination, so this transmission has no effect on Ti. If the benefit is 0, the entire transmission process ends; if not, skip to S104 to continue execution.

Figure 2 shows a feedback matrix with 7 packets and 5 receiving nodes. In Figure 2, 7 packets are lost at the receiving end. If the traditional automatic request retransmission method is used, it needs to be retransmitted 7 times, and the network coding method needs to find an appropriate encoding method to encode the packets. combined, and then the source node retransmits the new encoded packet. The present invention uses the Hamming weight coding algorithm to code and combine the information packets.

Hamming Weight Coding (BRSOC) Algorithm and Performance Analysis

Definition 1 Hamming weight is the Hamming distance between a string and an all-zero string, where the Hamming weight of a binary string is the number of 1s, so the Hamming weight of a binary string 10001 is 2.

Definition 2: Self-adaptation is to automatically adjust the encoding method according to the pre-set constraints of the processing data during the transmission process to make it adapt to the characteristics of the processed data to ensure the real-time transmission.

Description of Hamming Weight Coding (BRSOC) Strategy Implementation Mechanism

Assuming that the total number of information packets to be sent is M under the condition of no information loss, the N information packets that satisfy the algorithm conditions can be regarded as a broadcast transmission batch, and the M information packets can be complexed by batch division. The problem of broadcast sending becomes N simple information packets, the complexity of the algorithm is reduced, and finally the remaining packets are regarded as a batch. Assuming that the number of information packets that need to be broadcasted is 21, according to the calculation of 4 packets in each batch, it can be known that 21 broadcast information packets are all sent through 21/4=6 batches, as shown in Figure 3.

The first step is to calculate the Hamming weight value Yi (0≤hi≤N, 1≤i≤7) of each column of information packets in the feedback matrix W, and then arrange and update the Hamming weight values from large to small according to the calculated Hamming weight values. Feedback matrix W, as shown in Figure 4.

The second step is to calculate the number of batches required by the packet according to the batch sending strategy, and then divide the packets contained in each batch by the Hamming weight value:

(a) If the Hamming weight Yi=N, divide it into one batch individually.

(b) If the Hamming weight of the packet Yi<N, assign its Hamming weight to s, and divide the packet of the column where the Hamming weight Yi≤N-s and satisfy Theorem 1 into a batch until the required batch is completed. Second-rate.

The third step is to adaptively encode the information packet corresponding to the largest Hamming weight value and the remaining information packets for each batch of information packets, and then start searching from the remaining information packets. The sending strategy is to assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. If s=N at this time, the code combines the two information packets. Perform broadcast retransmission.

The fourth step is to update the packet loss feedback matrix in time according to the receiving conditions of the receiving node. If the new matrix is a non-zero matrix, the third step is repeated until the receiving state matrix is an all-zero matrix.

As shown in Figure 4, the updated feedback matrix is calculated according to 3 packets per batch. According to the formula calculation, the known packets are divided into 3 batches. Then, starting from the first column P2 in the updated matrix, the Hamming weight Yi is searched according to the principle. ≤Ns=5-4=1, it can be seen that only the information packet P3 satisfies the coding condition, then the coding obtains Similarly, other batches of encoding packages can be obtained

The core of the coding condition algorithm is to give priority to retransmission of important packets, that is, to preferentially transmit packets with a large Hamming weight. Suppose the Mth retransmission It is an encoding combination package. The characters in the encoding package represent the Hamming weights of P1, P2, P3,...Pn,Pk. The values are represented by the following letters Y1, Y2, Y3...Yn, Yk respectively, when and Only when the receiving end Ti has only 1 information packet lost, Ti can decode 1 original information packet. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2 +Y3+...Yn=Yk.

Prove: In a low-latency broadcast retransmission network, the encoding combination packet has at most one lost packet at each receiver, because the number of packets lost in each line will be corresponding to the number of packets lost after the XOR encoding operation. Decrease by an integer multiple of 2, resulting in the encoding combination packet cannot be decoded at the receiving end, as shown in Figure 5(a) The Hamming weight of Yh=3, the Hamming weight of P1 is Y1=1, and the Hamming weight of P2 is Y2=4, then it can be seen that Yh<Y1+Y2, and it is reduced to one time of 2, which does not meet the coding condition. In Figure 5(b) Hamming weight Encoding conditions are met.

In this paper, the broadcast retransmission based on network coding in satellite optical communication is coded by Hamming weight coding. Compared with the NCWBR method, the BRSOC method enables the receiver to recover its lost packets in an optimal way from fewer retransmissions. Considering that the channel between the satellite source node and the receiver has consistent statistical properties, when the number of packets M is large enough, it can be considered that the number of lost packets generated by the node after a single batch of packets is sent is roughly the same. ,Right now

T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L )

Where Q is the number of original packets sent, p _c p _e p _u are parameters, and L is the length of the packet. In order to ensure that the receiver can successfully receive a batch of packets, the broadcast source node needs to broadcast the total number of packets for

where the random variable X _k is the average number of transmissions required by node k to correctly receive a single packet, then p(x _k ≤ i) represents the successful reception probability of node k after the i-th transmission, namely

in Indicates the number of encoding combinations for broadcast retransmission. Therefore, the average number of transmissions required for all receivers to successfully receive a single packet is

Since the coding combination judgment strategy of the BRSOC algorithm is to first process the information packets in batches, and then preferentially encode the important information packets through the Hamming weight coding method, if the information packets can be successfully transmitted in the communication network, the receiving end can also timely If the important information packets are decoded, then in the communication network that requires high real-time information transmission, the time used for encoding and decoding calculation can be ignored on the network performance. Therefore, in the same satellite optical communication network, this algorithm can improve the transmission efficiency of important data packets and reduce the number of retransmissions.

In order to verify the feasibility and effectiveness of the BRSOC algorithm, in the low-latency wireless network channel transmission state, the average retransmission times of different retransmission algorithms are compared by changing different parameters of lost packets (1) The retransmission algorithm proposed in this paper , BRSOC (2) traditional automatic request retransmission algorithm, ARQ; (3) wireless broadcast retransmission strategy based on random linear network coding, NCWBR. The simulation environment in this paper is Dell PC, and the processor is Intel(R) Core(TM) i5-4210U CPU 2.40GHz, the operating system is 64-bit win10 system, and Matlab2012b is used for simulation.

Figure 6(a) shows that when the packet loss rate and the number of packets at the receiver are the same, the packet loss rate at the receiver is 0.2, and the number of packets is 60. Compare the three types of retransmissions with the number of receivers ranging from 5 to 35. Average number of retransmissions required by the algorithm. It can be seen from (a) that the average number of transmissions of BRSOC is much smaller than that of traditional ARQ, and with the increase of the number of receivers, the average number of retransmissions of BRSOC does not increase significantly, because BRSOC judges the feasibility of packet coding through the coding combination judgment strategy. , to determine the encoding method, thereby reducing the number of retransmissions. In traditional ARQ, the slope becomes smaller as the number of receivers increases, but the average number of retransmissions of NCWBR increases approximately linearly, because NCWBR cannot guarantee the solvability of the coded packets at the receiver, if any one of the terminals is used.

Figure 6(b) shows that the number of receivers is 20, the number of packets is 50, the packet loss rate of the receiver varies from 0.1 to 0.7, and each time increases by 0.1. With the increase of the receiver's packet loss rate, the average number of ARQ retransmissions The increase is obvious, while the average number of retransmissions of BRSOC and NCWBR does not change much, but when the packet loss rate increases to about 0.5, the curve slope of NCWBR gradually increases. Therefore, the advantage of using the mechanism proposed in this paper is more obvious when the network has a high packet loss rate.

Figure 6(c) shows that the packet loss rate at the receiver is 0.2, the number of receivers is 15, and the number of packets varies from 20 to 140. With the continuous increase of the number of information packets, the lost information packets for retransmission will increase correspondingly, and the more times the retransmission needs to be performed, the efficiency of retransmission will be reduced, and the delay of retransmission will be increased. It can be seen from (c) that the BRSOC hardly changes with the growth of data packets, which indicates that the algorithm is less affected by the number of original packets, thus ensuring that the number of retransmissions is less affected by the encoded packets.

As shown in Figure 2, a broadcast retransmission system based on Hamming weight coding includes: a satellite light source node and N (N≥2) receivers,

The satellite light source node is used to broadcast M information packets to N (N≥2) receivers at a fixed interval period Δt. The satellite light source node and the receiver obey Bernoulli distribution, and their packet loss rates are independent of each other;

The satellite light source node is also used to broadcast M original information packets to the receiving end, and each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation. The loss situation includes: whether the information packet is lost, and the label of the lost information packet and the label of the lost node;

The satellite light source node is also used to record whether the lost information packets are lost in the feedback matrix W according to the number of lost information packets fed back by the receiving end, where the feedback matrix W is an N×M matrix, and the rows represent N (N≥2) Receiver, the column indicates M packets, W(i,j)=1 indicates that the ith receiver Ti has not received the jth packet Pj, and W(i,j)=0 indicates that the ith receiver Ti Receive the jth packet Pj;

The satellite light source node is also used to encode and combine the lost packets at the receiving end according to the packet loss distribution data recorded in the feedback matrix W by means of Hamming weight coding, and re-send the broadcast to all the receiving ends until all the receiving ends recover. its lost packets.

The satellite light source node is specifically used for:

Calculate the Hamming weight value Y _i of each column of information packets in the feedback matrix W (0≤Y _i ≤N, 1≤i≤M), and carry out the M column information packets from large to small according to the calculated Hamming weight value. Arrange, update the feedback matrix W;

According to the batch sending strategy, the number of batches required for the packet is calculated, and the packets contained in each batch are divided according to the calculated Hamming weight value:

If the Hamming weight value Y _i =N, divide it into a batch separately;

If the Hamming weight value Y _i <N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Y _i ≤ Ns and meet the coding conditions into a batch until the required batch is completed ;

For each batch of information packets, firstly encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets adaptively, and then start searching from the remaining information packets. The strategy is to assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. broadcast retransmission;

The feedback matrix W is updated in time according to the reception situation of the receiving end. If the new matrix is a non-zero matrix, the encoding sub-module is repeatedly executed until the feedback matrix W is an all-zero matrix.

Since the channel between the satellite light source node and the receiver has consistent statistical properties, when the number of information packets M is large enough, it can be considered that the number of lost information packets generated by the satellite light source node after a single batch of information packets is sent is roughly same, i.e.:

T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L )

Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of packets that the satellite light source node needs to broadcast is:

Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤ i) means that the i-th transmission is received after the The probability of successful reception of terminal k, namely:

in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is

The invention proposes network coding-based broadcast retransmission in satellite optical communication on the basis of improving the information transmission rate. In this strategy, in the satellite optical communication network, the information packet is divided into multiple batches according to the judgment principle of coding combination, and then the Hamming weight of each information packet in the feedback matrix is calculated, and a new Hamming weight matrix is constructed according to the calculated value. In the new matrix, the coding combination package that meets the conditions can be quickly retransmitted, so that the retransmission efficiency can be effectively improved and the number of retransmissions can be reduced.

It will be apparent to those skilled in the art that various modifications and variations can be made in the present invention without departing from the spirit and scope of the invention. Thus, provided that these modifications and variations of the present invention fall within the scope of the claims of the present invention and their technical equivalents, the present invention is also intended to include such modifications and variations.

Claims (8)

1. a broadcast retransmission method based on Hamming weight coding, is characterized in that, comprises: S1. The satellite light source node broadcasts M information packets to N (N≥2) receiving ends at a fixed interval period Δt. The satellite light source node and the receiving end obey Bernoulli distribution, and their packet loss rates are mutually exclusive. independent; S2. After the satellite light source node broadcasts M original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation, where the loss situation includes: whether the information packet is lost, and The label of the lost packet and the label of the lost node; S3. According to the number of lost information packets fed back by the receiving end, the satellite light source node records whether the information packets are lost or not in the feedback matrix W, wherein the feedback matrix W is an N×M matrix, and the row represents N(N≥ 2) receivers, the column represents M packets, W(i,j)=1 indicates that the ith receiver Ti has not received the jth packet Pj, and W(i,j)=0 represents the ith packet Pj The receiver Ti receives the jth information packet Pj; S4, according to the packet loss distribution data recorded in the feedback matrix W, the satellite light source node encodes and combines the information packets lost by the receiving end through Hamming weight coding, and broadcasts and resends it to all the receiving ends until all the receiving ends are received. both ends recover their lost packets. 2. a kind of broadcast retransmission method based on Hamming weight coding according to claim 1, is characterized in that, step S4 comprises: S41. Calculate the Hamming weight value Yi of each column of information packets in the feedback matrix W (0≤Yi≤N, 1≤i≤M), and according to the calculated Hamming weight values for the information packets of the M columns from large to Arrange the small ones, and update the feedback matrix W; S42, according to the batch sending strategy, calculate the number of batches required for the information packets, and divide the information packets contained in each batch according to the calculated Hamming weight value: If the Hamming weight value Yi=N, divide it into a batch separately; If the Hamming weight value Yi<N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Yi≤N-s and meet the coding conditions into one batch until the required batch is completed; S43. For each batch of information packets, adaptively encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets, and then start searching from the remaining information packets. Satisfy the sending policy, that is, assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. If s=N at this time, the code combines the two information The packet is broadcast and retransmitted; S44. Update the feedback matrix W in time according to the receiving condition of the receiving end. If the new matrix is a non-zero matrix, repeat step S43 until the feedback matrix W is an all-zero matrix. 3. a kind of broadcast retransmission method based on Hamming weight coding according to claim 2, is characterized in that, described coding condition is: when assuming the Mth retransmission, For the encoding combination package, the Hamming weight values corresponding to P1, P2, P3,..., Pn, Pk are Y1, Y2, Y3,..., Yn, Yk, if and only if the receiving end Ti has only one message In the case of packet loss, only one original information packet can be decoded. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2+Y3+...Yn=Yk. 4. a kind of broadcast retransmission method based on Hamming weight coding according to claim 2, is characterized in that, because the channel between described satellite light source node and receiving end has consistent statistical property, when the number of packets M When it is large enough, it can be considered that the number of lost information packets generated by the satellite light source node after a single batch of information packets is sent is roughly the same, that is: T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L ) Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of information packets that the satellite light source node needs to broadcast is: Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤i) represents the i-th transmission The probability of successful reception of the latter receiver k, namely: in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is 5. A broadcast retransmission system based on Hamming weight coding, characterized in that, comprising: a satellite light source node and N (N≥2) receiving ends, The satellite light source node is used to broadcast M information packets to N (N≥2) receiving ends at a fixed interval period Δt, the satellite light source node and the receiving end obey Bernoulli distribution, and the packets are lost. rates are independent of each other; The satellite light source node is also used to broadcast M original information packets to the receiving end, each receiving end sends an ACK/NACK control packet to the satellite light source node to feed back its loss situation, and the loss situation includes: whether the information packet is lost, and the label of the lost packet and the label of the lost node; The satellite light source node is also used to record whether the lost information packets are lost in the feedback matrix W according to the number of lost information packets fed back by the receiving end, wherein the feedback matrix W is an N×M matrix, and the row represents N (N ≥2) receivers, the column represents M packets, W(i,j)=1 indicates that the ith receiver Ti has not received the jth packet Pj, and W(i,j)=0 represents the ith packet Pj A receiver Ti receives the jth information packet Pj;; The satellite light source node is also used to encode and combine the information packets lost by the receiving end according to the packet loss distribution data recorded in the feedback matrix W by means of Hamming weight coding, and broadcast and resend to all the receiving ends until all the until the receiver recovers its lost packets. 6. A kind of broadcast retransmission system based on Hamming weight coding according to claim 5, is characterized in that, described satellite light source node is specifically used for: Calculate the Hamming weight value Yi (0≤Yi≤N, 1≤i≤M) of each column of information packets in the feedback matrix W, and perform the M column information packets from large to small according to the calculated Hamming weight value. Arrange, update the feedback matrix W; According to the batch sending strategy, the number of batches required for the packet is calculated, and the packets contained in each batch are divided according to the calculated Hamming weight value: If the Hamming weight value Yi=N, divide it into a batch separately; If the Hamming weight value Yi<N, assign its Hamming weight value to s, and divide the column information packet where the Hamming weight value Yi≤N-s and meet the coding conditions into one batch until the required batch is completed; For each batch of information packets, firstly encode the information packet corresponding to the largest Hamming weight value Y _i and the remaining information packets adaptively, and then start searching from the remaining information packets. The strategy is to assign this column to 0, put the number of the information packet into the array C, and reassign the number of 1s in the two data packets to s. broadcast retransmission; The feedback matrix W is updated in time according to the reception situation of the receiving end. If the new matrix is a non-zero matrix, the encoding sub-module is repeatedly executed until the feedback matrix W is an all-zero matrix. 7. A kind of broadcast retransmission system based on Hamming weight coding according to claim 6, is characterized in that, described coding condition is: when assuming the Mth retransmission, For the encoding combination package, the Hamming weight values corresponding to P1, P2, P3,..., Pn, Pk are Y1, Y2, Y3,..., Yn, Yk, if and only if the receiving end Ti has only one message In the case of packet loss, only one original information packet can be decoded. If the receiving end Ti wants to correctly decode the lost information packet data in the encoded combined packet, it needs to satisfy: Y1+Y2+Y3+...Yn=Yk. 8. a kind of broadcast retransmission system based on Hamming weight coding according to claim 6, is characterized in that, because the channel between described satellite light source node and receiving end has consistent statistical property, when the number of packets M When it is large enough, it can be considered that the number of lost information packets generated by the satellite light source node after a single batch of information packets is sent is roughly the same, that is: T=Q((1-p _c )(1- _pe ) ^L -p _c (1-p _u ) ^L ) Among them, T is the number of lost packets generated, Q is the number of original packets sent, p _c p _e p _u are parameters, L is the packet length, in order to ensure that the receiver can successfully receive a batch of packets, The total number of information packets that the satellite light source node needs to broadcast is: Among them, N is the total number of information packets that the satellite light source node needs to broadcast, and the random variable X _k is the average number of transmissions required by the receiver k to correctly receive a single information packet, then it can be known that p(x _k ≤i) represents the i-th transmission The probability of successful reception of the latter receiver k, namely: in, Represents the number of encoded packets retransmitted by broadcast, then the average number of transmissions required by all receivers to successfully receive a single packet is