CN103107875B - Broadcast retransmission system based on network coding and method thereof - Google Patents

Abstract

The invention discloses a broadcast retransmission system based on network coding and a method of the broadcast retransmission system and mainly solves the problem that existing broadcast retransmission technology is low in retransmission efficiency. The broadcast retransmission system based on the network coding comprises a sending end and a plurality of receiving ends, wherein the sending end comprises a negotiation module, a dynamic list module, a retransmission cache module, a network coding module and a sending buffering module, and each receiving end comprises an information cache module, a decoding module and a feedback module. The method of the broadcast retransmission system comprises the following achieving steps. (1) A test pack is sent; (2) the system single frame largest survival time is obtained; (3) a dynamic linked list is initialized; (4) a information frame is sent; (5) a dynamic list is updated; (6) a retransmission frame is constructed; (7) the retransmission frame is sent; (8) the dynamic list is updated again; (9) remaining information in the dynamic list is processed; (10) preparation is conducted before transmission; (11) a data frame is received; (12) frame decoding is retransmitted. The broadcast retransmission system based on the network coding and the method of the broadcast retransmission system have the advantages of being low in transmission time delay and high in retransmission efficiency.

Description

Broadcast retransmission system and method based on network coding

technical field

The invention belongs to the technical field of communication, and further relates to a broadcast retransmission system and method based on network coding in the technical field of wireless communication broadcast engineering. The present invention can be used in various radio reliability broadcast scenarios, and realizes a network coding-based, dynamic broadcast retransmission method and broadcast retransmission process control for both the sender and the receiver.

Background technique

Automatic retransmission request (Automatic-repeat-request, ARQ) is a mainstream type of retransmission protocol, and it is a reliable data transmission protocol used in communication to deal with errors caused by packet loss or packet bit damage in the channel. The advantage of the ARQ technology is that it is relatively simple, but the disadvantage is that the utilization rate of the communication channel is not high. Multicast or broadcast is a form of data transmission widely used in wireless communication networks. Its topology diagram is shown in Figure 1. It consists of a sender node and multiple receiver nodes. The sender sends data to multiple receivers. . Compared with broadcast in traditional wired communication, wireless broadcast has higher frame error rate, transmission delay and lower retransmission efficiency. For example, if a receiver fails to receive data at this time, according to the traditional ARQ protocol, the sender needs to broadcast the failed data frame until all receivers receive the data frame correctly. Network Coding (NC, Network Coding) performs linear or non-linear processing on the information received on each channel at the intermediate node of the network, and then forwards it to the next node, which can improve network throughput, reduce the number of data frame transmissions, Enhance the fault tolerance and robustness of the network.

The patent application "Wireless Reliable Broadcasting Method Based on Random Linear Coding" (application date: March 16, 2012, application number: 201210071101.9, publication number: CN102638331A) filed by Beijing University of Posts and Telecommunications discloses a wireless broadcasting method based on random linear coding. A reliable broadcast method to solve the inefficiency of broadcast retransmission in wireless communication. The implementation steps of the method are as follows: first, the sending end broadcasts a plurality of specified information frames. Second, the sender performs random linear network coding on the information frames lost by the receiver. Third, the receiving end uses the Gaussian elimination method to obtain the lost information frame. The disadvantage of this method is that this patent application does not take into account some requirements in actual engineering, such as the timeliness of information frames, the memory space that can be allocated by the receiving end in communication, whether it is compatible with different channel codes, etc., resulting in This method is not suitable for a wide range of engineering applications. Since the patent application only adopts the block transmission mode, the information frames between groups cannot be network coded, so the performance brought by network coding cannot be maximized, and the overall transmission delay of all information frames is relatively large ; It simply uses random linear network coding, it is difficult to achieve the optimal combination of network coding, and the improvement of retransmission efficiency that can be brought is very limited. This patent application does not consider the reception of retransmission frames in detail, so that the method may cause the reception of some data frames to time out in some special cases.

Since 2008, there have been 13 patented technologies to solve the broadcast retransmission problem. Basically, they simply group information frames and then find the optimal combination in the group. This solution limits the retransmission efficiency.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the above-mentioned prior art, aiming at the problem of broadcast retransmission, propose a broadcast retransmission system and method based on network coding, which can effectively reduce retransmission delay, improve retransmission efficiency, and is widely applicable to various This engineering application scenario meets the real-time and high-throughput requirements of the next-generation broadband wireless communication system.

In order to achieve the above object, the idea of the method of the present invention is: determine the maximum survival time of a single frame of the system through the transmission test packet; through the dynamic update method based on the dynamic list, track the receiving situation of each information frame in real time; according to the maximum matching and perfect matching method, to find a relatively optimal network coding scheme; by updating the dynamic list method based on the feedback information of the retransmission frame, the situation of receiving the data frame overtime is avoided; the data transmission realized by the broadcast retransmission system has higher retransmission Transmission efficiency, lower overall transmission delay, suitable for various broadcast scenarios in wireless communication systems.

The system of the present invention includes a sending end and a plurality of receiving ends.

The sending end is composed of a negotiation module, a dynamic list module, a retransmission buffer module, a network coding module, and a sending buffer module; any one of the multiple receiving ends is composed of an information buffering module, a decoding module, and a feedback module. The negotiation module is used for sending the test frame, receiving the test frame response information from the receiving end, calculating the maximum survival time of the system single frame, and sending the system survival time to the dynamic list module; the dynamic list module is used for receiving the response information from the receiving end Receiving information frames or retransmission frame response information, establishing and storing dynamic lists, and performing matching operations on dynamic lists; retransmission cache module, used to store multiple information frames to be retransmitted; network coding module, used for different The information frame is network encoded, the retransmission frame is constructed, the retransmission frame is sent, and the retransmission frame is temporarily stored; the sending buffer module is used to store the current information frame to be sent; the information buffer module is used to store multiple correctly received The information frame and the retransmission frame; the decoding module is used to decode the retransmission frame to restore the original information frame; the feedback module is used to feed back the reception status of the data frame to the receiving end.

The concrete steps of the inventive method are as follows:

(1) Send test package:

1a) The negotiation module records the sending time of the broadcast test frame, and waits for feedback information from multiple receiving ends;

1b) If the negotiating module receives confirmation response information from all multiple receiving ends, then perform step 1c); if the negotiating module receives a negative response or does not receive feedback information from any receiving terminal, then perform step 1a);

1c) The negotiation module records the receiving time of each acknowledgment response information, and records the single-frame waitable delay and allocable storage space fed back by each of the multiple receiving ends;

(2) Obtain the maximum survival time of a single frame in the system:

2a) The negotiation module selects the largest one among multiple confirmation response message receiving times, subtracts the sending time of the test frame from the maximum receiving time, and obtains the system propagation delay;

2b) Select the smallest one among multiple single-frame waitable delays as the single-frame waitable delay of the system;

2c) Selecting the smallest one of multiple allocatable storage spaces as the system allocatable storage space;

2d) The largest integer that satisfies the following formula is used as the maximum survival time of a single frame in the system:

(NH-1)TR<TM

(NH-1)C _O <CM

Among them, NH represents the maximum survival time of a single frame of the system, TR represents the propagation delay of the system, TM represents the waiting delay of a single frame of the system, C _O represents the storage space required by an information frame, and CM represents the storage space that the system can allocate;

(3) Dynamic linked list initialization:

3a) The sending buffer module divides the maximum survival time of a single frame of the system by 2, rounds the tail to an integer, and obtains the initial amount;

3b) The sending buffer module continuously broadcasts an initial amount of information frames to multiple receiving ends;

3c) The storage sub-module establishes a dynamic linked list corresponding to the initial number of information frames;

3d) The storage sub-module assigns the serial numbers of the initial number of dynamic linked lists to the corresponding information frame serial numbers, respectively assigns the survival time of the initial number of dynamic linked lists to the initial number after subtracting the initial number of information frame serial numbers Add 1, assign several node values of each dynamic linked list to be respectively, and return the user serial number of the receiving end of negative information to the information frame corresponding to the dynamic linked list;

3e) Traversing all linked lists in the storage submodule, sequentially extracting the serial numbers in the header, transferring the information frames corresponding to the extracted information frame serial numbers from the sending buffer module to the retransmission buffer module, and recording the data transferred at this time The address of the information frame stored in the retransmission buffer module, and the corresponding relationship between the extracted information frame sequence number and the information frame storage address is established by the mapping submodule; the node number item of all linked lists in the storage submodule is traversed again, and the The dynamic linked list whose number of nodes is 0 is deleted from the dynamic list, and the information frame corresponding to the dynamic linked list is deleted from the retransmission buffer module at the same time, and the corresponding relationship corresponding to the dynamic linked list is deleted from the mapping submodule;

(4) Send information frame:

4a) sending buffer module checks whether there is information frame to be sent, if there is, then sending buffer module broadcasts next information frame, execution step 4b); Otherwise, execution step 9a);

4b) If the storage submodule receives confirmation response information from all multiple receiving ends, then perform step 5a); if a negative response is received or no feedback information from any receiving terminal is received, then step 5b) is performed;

(5) Update the dynamic list:

5a) The sending buffer module releases the storage space of the sent information frame, and the storage sub-module adds 1 to the survival time of all current linked lists, and then executes step 6a);

5b) The sending buffer module transfers the sent information frame to the retransmission buffer module, and the mapping sub-module creates the corresponding relationship between the information frame storage address and the serial number;

5c) The storage submodule uses the serial number of the sent information frame as the serial number of the dynamic linked list, uses 0 as the survival time of the dynamic linked list, and uses the number of receiving ends that fail to receive the information frame as the number of nodes of the dynamic linked list , using the user serial number of the receiving end that failed to receive the information frame as a node of the dynamic linked list to obtain a new dynamic linked list;

5d) the storage submodule adds 1 to the survival time of all linked lists in the storage submodule, and executes step 6a);

(6) Construct a retransmission frame:

6a) Judging among all dynamic linked lists, whether the survival time of the dynamic linked list with the smallest serial number is less than the difference between the maximum survival time of a single frame of the system minus 2, if less than, then perform step 6c); if greater than or equal to, perform step 6b);

6b) The matching sub-module invokes the maximum matching algorithm, performs the maximum matching operation on the dynamic linked list with the smallest sequence number in all dynamic linked lists, and obtains the retransmission frame construction set, and the matching sub-module sends the retransmission frame construction set to the network coding module, and executes the steps 7a);

6c) The matching submodule invokes the perfect matching algorithm to perform perfect matching on the dynamic linked list with the smallest serial number in all dynamic linked lists, and judges whether the matching result is a retransmission frame construction set, and if so, the matching submodule sends the retransmission frame construction set To the network coding module, perform step 7a); if the result of the operation is "unable to perform a perfect match", then perform step 4a);

(7) Send retransmission frame:

7a) The network coding module takes out all the elements from the retransmission frame construction set, sends the value of this group of elements to the mapping sub-module, and for the value of each element, indexes one by one the storage location of the information frame whose serial number is the same as the element value , extracting information frames one by one from the retransmission cache module according to the storage location;

7b) The network coding module takes the frame whose length is the length of the content part of the information frame and each bit is 0 as the initial retransmission frame, and performs a bit-by-bit XOR operation on the extracted multiple information frames and the initial retransmission frame one by one , get the quasi-retransmission frame;

7c) The network coding module adds the retransmission frame construction set after the quasi-retransmission frame to obtain the retransmission frame;

7d) The network coding module broadcasts retransmission frames to multiple receivers, and waits for the receivers to return response information;

(8) Update the dynamic list again:

8a) The storage submodule adds 1 to the survival time of all linked lists, records the user serial numbers of the receivers that return confirmation responses among multiple receivers, and combines the recorded user serial numbers into a feedback user set;

8b) Determine whether the feedback user set is an empty set, if so, perform step 7d); if not an empty set, then perform step 8c);

8c) The dynamic list module extracts all elements from the retransmission frame construction set, and for the value of each element, index the dynamic linked list whose serial number is the same as the value of the element one by one in the storage submodule, and store the dynamic linked list for all obtained dynamic links by the storage submodule For all nodes on , if the value of any node exists in the feedback user collection, delete the node, and reduce the number of nodes in the linked list to which the node belongs;

8d) The dynamic list module deletes the linked list whose number of nodes is 0, and adds 1 to the survival time of all remaining linked lists;

8e) The dynamic list module deletes the retransmission frame construction set, the network coding module deletes the retransmission frame construction set, the quasi-retransmission frame and the retransmission frame, clears the feedback user set, and executes step 6a);

(9) Process the remaining information in the dynamic list:

9a) judge whether it is empty in the dynamic list, if it is empty, then execute step 9i); otherwise execute step 9b);

9b) The matching submodule invokes the maximum matching algorithm, and performs a maximum matching operation on the dynamic linked list with the smallest serial number in all dynamic linked lists to obtain a retransmission frame construction set, and the matching submodule sends the retransmission frame construction set to the network coding module;

9c) The network coding module takes out all elements from the retransmission frame construction set, sends the value of this group of elements to the mapping sub-module, and for the value of each element, indexes one by one the storage location of the information frame whose serial number is the same as the element value , extracting information frames one by one from the retransmission cache module according to the storage location;

9d) The network coding module takes the frame whose length is the length of the content part of the information frame and each bit is 0 as the initial retransmission frame, and performs a bit-by-bit exclusive OR operation on the obtained multiple information frames with the initial retransmission frame one by one , get the quasi-retransmission frame;

9e) The network coding module adds the retransmission frame construction set after the quasi-retransmission frame, thereby obtaining the retransmission frame, and temporarily saves the retransmission frame; the network coding module broadcasts the retransmission frame to multiple receivers, and waits for the receiver to return a response information;

9f) The storage sub-module records the user serial numbers of several receiving terminals that return confirmation responses among multiple receiving terminals, and combines the serial numbers of the several receiving terminals into a feedback user set;

9g) The dynamic list module extracts all elements from the retransmission frame construction set. For the value of each element, index the dynamic linked list with the same sequence number as the value of the element in the storage sub-module one by one, and the storage sub-module compares all obtained dynamic linked lists. For all the nodes above, judge whether the value of the node exists in the feedback user set, if the value of any node exists in the feedback user set, delete the node, and reduce the number of nodes in the linked list to which the node belongs;

9h) The dynamic list module deletes the retransmission frame construction set, the network coding module deletes the retransmission frame construction set, the quasi-retransmission frame and the retransmission frame; clears the feedback user set, and executes step 9a);

9i) end;

The receiving process includes the following steps:

(10) Preparation before transmission:

10a) Empty the cache contents in the information cache module and the decoding module;

10b) judge whether there is a data frame that needs to be received, if so, then execute step 10c); otherwise, execute step 12h);

10c) If the receiving sub-module does not receive the data frame, the feedback module sends a negative response to the sending end, and executes step 10c); otherwise, executes step 10d);

10d) judging that the received data frame is a test frame, an information frame, and a retransmission frame; if it is a test frame received, perform step 10e); if it is an information frame, then perform step 11a); if received is a retransmission frame, then perform step 11c);

10e) The feedback module returns the acknowledgment response information, and returns the single frame waiting time delay and allocatable storage space, and executes step 10c);

(11) Receive data frame:

11a) The feedback module returns an acknowledgment response to the sending end, and the parsing submodule extracts the serial number of the information frame from the frame header of the information frame, and the cache module judges whether there is enough storage space, and if so, executes step 11b); otherwise, cache The submodule releases the storage space of an information frame with the smallest sequence number among the plurality of information frames stored, resolves the submodule to delete the correspondence between the sequence number and the storage address of the information frame, and executes step 11b);

11b) The cache submodule stores the received information frame, and the parsing submodule stores the corresponding relationship between the information frame storage address and the serial number, and executes step 10b);

11c) The parsing submodule reads the first bit after the frame header of the retransmission frame and the length bits of the subsequent information frame, and uses the read content as a quasi-recovery frame;

11d) The parsing submodule reads all the bits after the information frame length bits, and uses the read content as a retransmission frame construction set, sends the retransmission frame construction set and the quasi-recovery frame to the decoding module, and performs step 12a) ;

(12) Retransmission frame decoding:

12a) The decoding module uses two empty sets as the decoding set and the target set. The decoding module will extract the values of all elements in the retransmission frame construction set. For the value of each element, if there is an information frame sequence in the information buffer module If there is an information frame with the same number as the value of the element, add this information frame sequence number as an element to the decoding set, otherwise add this information frame sequence number as an element to the destination set;

12b) Determine the number of elements in the destination set, if the number of elements is 0, the feedback module returns a confirmation response to the sending end, and execute step 12g); if the number of elements is greater than or equal to two, call the feedback module to return a negative response to the sending end , execute step 12g); if the number of elements is only 1, call the feedback module to return a confirmation response to the sender, and execute step 12c);

12c) The decoding module takes out all the elements from the decoding set, sends the value of this group of elements into the parsing sub-module, and for the value of each element, indexes the storage locations of the information frames whose serial numbers are the same as the element values one by one, Extract information frames one by one from the cache sub-module according to the storage location;

12d) performing bit-by-bit XOR operation on the extracted multiple information frames one by one with the quasi-recovery frame to obtain the recovery frame, and using the unique element in the target set as the serial number of the recovery frame;

12e) The cache module judges whether there is enough storage space, and if so, executes step 12f); otherwise, the cache submodule releases the storage space of an information frame with the smallest sequence number among the stored information frames, and the resolution submodule releases the sequence number The serial number of the smallest information frame and the corresponding relationship between the storage address are deleted, and step 12f is performed);

12f) The cache sub-module stores the recovery frame obtained, and the parsing sub-module saves the serial number of the recovery frame and the corresponding relationship between the storage address of the recovery frame;

12g) Delete the retransmission frame construction set, quasi-recovery frame, decoding set, purpose set and recovery frame existing in each module of the receiving end, and execute step 10b);

12h) end.

Compared with the prior art, the present invention has the following advantages:

First, because the present invention introduces the maximum survival time of a single frame in the system during data transmission, it overcomes the shortcomings of the existing technology that ignores the timeliness of information frames and the memory space that can be allocated in the communication of the receiving end, so that the present invention has a higher Practical engineering applicability, suitable for a variety of broadcast scenarios in wireless communication systems.

Second, because the present invention adopts a dynamic update method based on a dynamic list during data transmission, it overcomes the shortcoming of block transmission in the prior art, and realizes that information frames between groups can still be network coded, making this The invention has higher retransmission efficiency and lower overall transmission delay.

Third, since the present invention introduces the maximum matching algorithm and the perfect matching algorithm in network coding, it overcomes the disadvantage that it is difficult to realize the optimal combination of network coding in the prior art, so that the present invention has higher retransmission efficiency and is suitable for wireless Various broadcast scenarios in communication systems.

Fourth, because the present invention adopts the method of updating the dynamic list based on the feedback information of the retransmission frame, it overcomes the shortcoming that the prior art does not consider the reception of the retransmission frame carefully, so that the present invention avoids the situation that the data frame reception times out.

Description of drawings

Fig. 1 is a broadcast network topology diagram of the present invention;

Fig. 2 is a schematic structural diagram of the system of the present invention;

Fig. 3 is the flowchart of sending process in the method of the present invention;

Fig. 4 is a flow chart of the receiving process in the method of the present invention.

detailed description

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

With reference to accompanying drawing 1, the application scene of the present invention is wireless broadcasting, and sending end S broadcasts data frame to M receiving ends, and _M receiving ends are represented by T ₁ , T _2, ..., TM respectively, and each receiving end Each has a unique user serial number. When the receiving end feeds back information to the sending end, the sending end can identify which receiving end sent the feedback information through the user serial number contained in the feedback information. In the embodiment of the present invention, M receiving end The user serial numbers of the end are 1, 2, ..., M, wherein M is any natural number less than 255. In the embodiment of the present invention, the user serial number in the information fed back by the receiving end to the sending end is represented by 8 bits, and the sending end broadcasts There are three types of data frames: test frames, information frames, and retransmission frames. The frame headers of each type of data frame contain information that can identify the type of data frame, and the length of the information frame is a fixed value. Embodiments of the present invention The middle is l bit, and the frame header of the information frame includes the serial number of the information frame. Each information frame has a serial number, and the serial number is stored in the frame header of the information frame. In the engineering agreement, it is represented by 8bit or 16bit. For convenience, In the embodiment of the present invention, the serial number of the information frame is 8bit, that is, the serial number can be expressed as any natural number in 0 to 255, if the number of frames to be sent exceeds 255, the serial number of the information frame is the order modulo two and the result of.

Referring to accompanying drawing 2, the system of the present invention includes a sending end and a plurality of receiving ends.

The sending end is composed of a negotiation module, a dynamic list module, a retransmission buffer module, a network coding module, and a sending buffer module. Among them, the negotiation module is connected to the sending buffer module through a data line, the dynamic list module is connected to the network coding module through a data line, the dynamic list module is connected to the retransmission cache module through a data line, and the retransmission cache module is connected to the network coding module through a data line , the retransmission buffer module is connected to the send buffer module through a data line. The negotiation module is used for sending test frames, receiving test frame response information from the receiving end, calculating the maximum survival time of a single frame of the system, and sending the system survival time to the dynamic list module. The dynamic list module is used to receive the information frame and retransmission frame response information from the receiving end, establish, store, and update the dynamic list, establish the corresponding relationship between the dynamic linked list and the storage address of the information frame, and perform matching operations on the dynamic list, and The calculation result is sent to the network coding module. The retransmission buffer module is used for storing multiple information frames to be retransmitted. The network coding module is used for network coding different information frames, constructing retransmission frames, sending retransmission frames, and temporarily storing retransmission frames. The sending buffer module is used for storing and sending the information frame currently to be sent. Wherein, the dynamic list module includes a storage submodule, a matching submodule, and a mapping submodule. The storage sub-module is connected to the matching sub-module through a data line, and the storage sub-module is connected to the mapping sub-module through a data line. The storage sub-module is used to receive the information frame and retransmission frame response information from the receiving end, store and update the receiving status fed back by the receiving end. The matching sub-module performs the perfect matching algorithm or the maximum matching algorithm, and returns the retransmission frame construction set to the network coding module. The mapping sub-module is used to establish a one-to-one correspondence between the linked list sequence and the storage address of the information frame.

Any one of the multiple receiving ends is composed of an information buffer module, a decoding module and a feedback module. The information cache module is connected to the decoding module through a data line, the information cache module is connected to the feedback module through a data line, and the decoding module is connected to the feedback module through a data line.

The information cache module is used to receive data frames, analyze the types of data frames, establish the corresponding relationship between information frame storage addresses and information frame serial numbers, and store multiple correctly received information frames and retransmission frames. The decoding module is used to decode the retransmission frame and restore the original information frame. The feedback module is used to feed back the receiving condition of the data frame to the receiving end. Wherein, the information cache module includes a receiving submodule, a parsing submodule, and a cache submodule. The receiving sub-module is connected to the analyzing sub-module through a data line, and the analyzing sub-module is connected to the buffering sub-module through a data line. The receiving sub-module is used to receive the data frame from the sending end, and select the sending analysis sub-module or the notification feedback module for the received data frame. The parsing sub-module is used to analyze the frame header of the information frame or the retransmission frame to obtain the sequence number of the information frame or the construction vector of the retransmission frame, and store a mapping table representing the corresponding relationship between the sequence number of the information frame and the storage address. The cache sub-module is used for storing multiple information frames and the current retransmission frame.

In conjunction with specific examples, the concrete steps of the inventive method are described in detail:

With reference to accompanying drawing 3, the sending process of the present invention comprises the following steps:

Step 1, send a test packet:

1a) The negotiation module records the sending time of the broadcast test frame, and waits for feedback information from multiple receiving ends;

1b) If the negotiating module receives confirmation response information from all multiple receiving ends, then perform step 1b); if the negotiating module receives a negative response or does not receive feedback information from any receiving terminal, then perform step 1a);

1c) The negotiation module records the receiving time of each acknowledgment response information, and records the single-frame waitable delay and allocable storage space fed back by each of the multiple receiving ends;

Single-frame waitable delay refers to the maximum tolerable waiting time from the first request for any data frame to the correct reception of the data frame for any one of the multiple receivers T _i , this parameter reflects Requirements for the timeliness of information at the receiving end T _i ; the allocatable storage space refers to the storage space of the cache sub-module of any receiving end among multiple receiving ends, and this parameter reflects the willingness of the receiving end T _i to The allocated memory space; therefore, the significance of the whole step 1 is that the sending end understands the timeliness requirements of each of the M receiving ends for information and the memory space that can be allocated in this communication through the test frame.

Step 2. Obtain the maximum survival time of a single frame in the system:

2a) The negotiation module selects the largest one among multiple confirmation response message receiving times, subtracts the sending time of the test frame from the maximum receiving time, and obtains the system propagation delay;

2b) Select the smallest one among multiple single-frame waitable delays as the single-frame waitable delay of the system;

2c) Selecting the smallest one of multiple allocatable storage spaces as the system allocatable storage space;

2d) The largest integer that satisfies the following formula is used as the maximum survival time of a single frame in the system:

(NH-1)TR<TM

(NH-1)C _O <CM

Among them, NH represents the maximum survival time of a single frame of the system, TR represents the propagation delay of the system, TM represents the waiting delay of a single frame of the system, C _O represents the storage space required by an information frame, and CM represents the storage space that the system can allocate;

The significance of the maximum survival time of a single frame in the system is that it will ensure that all receiving ends have different requirements for information timeliness, and will not exceed the memory space that any receiving end is willing to allocate in this communication.

Step 3, dynamic linked list initialization:

3a) The sending buffer module divides the maximum survival time of a single frame of the system by 2, rounds the tail to an integer, and obtains the initial amount;

3b) The sending buffer module continuously broadcasts an initial number of information frames to multiple receiving ends; here, if the total number of information frames to be sent is less than the initial number of frames, then directly and continuously broadcast the number of information frames that need to be sent; Continuous broadcasting means that the sending buffer module broadcasts information frame 1 to the receiving end, after the storage sub-module receives the feedback information, the sending buffer module broadcasts information frame 2 to the receiving end, and after the storage sub-module receives the feedback information, the sending buffer module sends the The receiving end broadcasts information frame 3...until broadcasting the initial number of information frames, and during this process, the storage submodule records all the feedback information for the initial number of information frames; if any of the M receiving ends is not received A receiving end T _i , for the feedback information of any information frame P _i , the storage sub-module records T _i as feedback negative information for P _i ;

3c) the storage submodule establishes a dynamic linked list corresponding to the initial number of information frames; the one-to-one correspondence described here means that the serial number of the information frame P _i is identical to the serial number stored in the dynamic linked list L _j ;

3d) The storage sub-module assigns the serial numbers of the initial number of dynamic linked lists to the corresponding information frame serial numbers, respectively assigns the survival time of the initial number of dynamic linked lists to the initial number after subtracting the initial number of information frame serial numbers Add 1, assign several node values of each dynamic linked list to be respectively, and return the user serial number of the receiving end of negative information to the information frame corresponding to the dynamic linked list;

In the embodiment of the present invention, the numbers of M receivers that return negative responses to the initial amount of NH/2 information frames are respectively: ET ₁ , ET ₂ , ..., ET _NH/2 , the initialization result of the dynamic list Can be expressed as follows:

{1, NH/2, ET ₁ } {E(1, 1), E(1, 2), ..., E(1, ET ₁ )}

{ ₂ ,NH/2-1,ET2}{E(2,1),E(2,2),...,E( ₂ ,ET2)}

{NH/2, 1, ET _NH/2 } {E(NH/2, 1), E(NH/2, 2), ..., E(NH/2, ET _NH/2 )}

Among them, each row represents a dynamic linked list in the dynamic list, and each dynamic linked list is represented by two sets; the first set represents the header of the linked list, and its first element is the serial number MF of the dynamic linked list, and the second The element is the survival time TL of the dynamic linked list, and the third element is the number of nodes ET of the dynamic linked list; the second set represents the elements contained in the linked list; the entire dynamic list is composed of the initial number of such dynamic linked lists; NH/2 Indicates the initial quantity, ET ₁ , ET ₂ , ..., ET _NH/2 respectively represent the number of receiving ends that the receiving end believes to return a negative response to the information frame P ₁ , P ₂ , ..., P _NH/2 , E (i, j) represents that for the i-th frame data, the jth returns the user serial number of the negative acknowledgment receiving end, where 0<i<NH/2, 0<j<ET _i ;

3e) Traverse all linked lists in the storage sub-module, sequentially extract the information frame serial number in the table header, transfer the information frame corresponding to the extracted information frame serial number to the retransmission buffer module by the sending buffer module, and record the information transferred at this time The stored address of the stored information frame in the retransmission buffer module, and the corresponding relationship between the sequence number of the extracted information frame and the storage address of the information frame is established by the mapping submodule; the item number of nodes in all linked lists in the storage submodule is traversed again , deleting the dynamic linked list whose number of nodes is 0 from the dynamic list, deleting the information frame corresponding to the dynamic linked list from the retransmission buffer module, and deleting the corresponding relationship corresponding to the dynamic linked list from the mapping submodule;

(4) Send information frame:

4a) sending buffer module checks whether there is information frame to be sent, if there is, then sending buffer module broadcasts next information frame, execution step 4b); Otherwise, execution step 9a); The present invention only cares about solving this problem of broadcast retransmission, It belongs to the application of the data link layer in wireless communication. The present invention does not care about how many information frames need to be sent by the upper layer of the link layer. The information frames that need to be sent by the upper layer of the link layer are input in the sending buffer module. If there is no input, And the sending buffer module is empty, the system will consider that there is no information frame to be sent;

4b) If the storage submodule receives confirmation response information from all multiple receiving ends, then perform step 5a); if a negative response is received or no feedback information from any receiving terminal is received, then step 5b) is performed;

(5) Update the dynamic list:

5a) The sending buffer module releases the storage space of the sent information frame, and the storage sub-module adds 1 to the survival time of all current linked lists, and then executes step 6a);

5b) The sending buffer module transfers the sent information frame to the retransmission buffer module, and the mapping sub-module creates the corresponding relationship between the information frame storage address and the serial number;

5c) The storage submodule uses the serial number of the sent information frame as the serial number of the dynamic linked list, uses 0 as the survival time of the dynamic linked list, and uses the number of receiving ends that fail to receive the information frame as the number of nodes of the dynamic linked list , using the user serial number of the receiving end that failed to receive the information frame as a node of the dynamic linked list to obtain a new dynamic linked list;

In the embodiment of the present invention, the sequence number of the information frame sent is MF _x , and the receiver believes that the number of receivers returning negative responses among the M receivers of the information frame is ET _x , which corresponds to the information frame sent. The dynamic linked list of is:

{MF _x , 0, ET _x } {E(x, 1), E(x, 2), ..., E(x, ET _x )}

Wherein, E(x, j) represents for the information frame of information frame serial number position MF _x , jth returns the user serial number of negative acknowledgment receiving end, here 0<j<ET _i ;

5d) the storage submodule adds 1 to the survival time of all linked lists in the storage submodule, and executes step 6a);

(6) Construct a retransmission frame:

6a) Judging among all dynamic linked lists, whether the survival time of the dynamic linked list with the smallest serial number is less than the difference between the maximum survival time of a single frame of the system minus 2, if less than, then perform step 6g); if greater than or equal to, perform step 6b);

6b) The matching sub-module sets the retransmission frame construction set and the target user set to an empty set, adds the serial number in the dynamic linked list with the smallest serial number in all dynamic linked lists as an element to the retransmission frame construction set, and puts all the dynamic linked lists in the dynamic linked list All the nodes contained in the dynamic linked list with the smallest sequence number are added to the target user collection one by one as elements;

6c) traverse all dynamic linked lists in the storage submodule, and find whether there is a dynamic linked list satisfying the following formula:

Among them, ψ _CRS represents the retransmission frame construction set, and ψ _i represents the set of all nodes in any dynamic linked list of the storage submodule;

6d) Judging whether there is a dynamic linked list that satisfies the equation 6c), if it exists, execute 6e); otherwise execute 6f);

6e) Select the one with the largest number of nodes among all the dynamic linked lists that satisfy the equation in 6c), if there is more than one dynamic linked list with the largest number of nodes, then arbitrarily select a dynamic linked list in the dynamic linked list with the largest number of nodes , assign values to the retransmission frame construction set and the destination user set according to the following formula:

_ψCRS ＝ _ψCRS ∪{MF _j }

ψ _CUD = ψ _CUD ∪ψ _j

Among them, ψ _CRS represents the retransmission frame construction set, MF _j represents the sequence number of the selected dynamic linked list, ψ _CUD represents the set of destination users, and ψ _j represents the set of all nodes in the selected dynamic linked list, execute 6c);

6f) The matching submodule sends the retransmission frame construction set to the network coding module, and performs step 7a);

6g) The matching sub-module sets the retransmission frame construction set and the target user set to an empty set, adds the serial number in the dynamic linked list with the smallest serial number in all dynamic linked lists as an element to the retransmission frame construction set, and adds the serial number in all dynamic linked lists to the retransmission frame construction set. All the nodes contained in the dynamic linked list with the smallest sequence number are added to the target user collection one by one as elements;

6h) traverse all dynamic linked lists in the storage submodule, and find whether there is a dynamic linked list satisfying the following formula:

Among them, ψ _CRS represents the retransmission frame construction set, and ψ _i represents the set of all nodes in any dynamic linked list of the storage submodule;

6i) Judging whether there is a dynamic linked list that satisfies 6h) equation, if it exists, execute 6j); otherwise execute 6k);

6j) Select the one with the largest number of nodes among all the dynamic linked lists satisfying the equation in 6h), if there is more than one dynamic linked list with the largest number of nodes, then arbitrarily select a dynamic linked list in the dynamic linked list with the largest number of nodes , assign values to the retransmission frame construction set and the destination user set according to the following formula:

_ψCRS ＝ _ψCRS ∪{MF _j }

ψ _CUD = ψ _CUD ∪ψ _j

Among them, ψ _CRS represents the retransmission frame construction set, MF _j represents the serial number of the selected dynamic linked list, ψ _CUD represents the set of destination users, and ψ _j represents the set of all nodes of the selected dynamic linked list, execute 6h);

6k) If the target user set includes the user serial numbers of all receivers, the matching submodule sends the retransmission frame construction set to the network coding module, and executes step 7a); otherwise, executes step 4a);

(7) Send retransmission frame:

7a) The network coding module takes out all the elements from the retransmission frame construction set, sends the value of this group of elements to the mapping sub-module, and for the value of each element, indexes one by one the storage location of the information frame whose serial number is the same as the element value , extract information frames one by one from the retransmission cache module according to the storage location, and the information frames used in network encoding are the content of the information frame excluding the frame header;

7b) The network coding module takes the frame whose length is the length of the content part of the information frame and each bit is 0 as the initial retransmission frame, and performs a bit-by-bit XOR operation on the extracted multiple information frames and the initial retransmission frame one by one , to obtain a quasi-retransmission frame; the bit-by-bit XOR operation refers to, from the first bit to the last bit of two frames of the same length, for each pair of bits at the same position, perform a modulo two sum; When information frame P ₁ and information frame P ₂ are subjected to bit-by-bit XOR operation, the information in P ₁ is expressed as [λ1, λ2, ..., μl], l is the content length of the information frame, and the information in P ₂ is expressed as [ε ₁ ,ε ₂ ,…,ε _l ], the result of bit-by-bit XOR operation between P ₁ and P ₂ is expressed as:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&CirclePlus;</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; [</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ]</span>$

Among them, λi is the value of the _i - _th bit of the content part of the information frame P1, and εi is the value of the _i -th bit of the content part of the information frame P2, where ₀ <i<l, and l is the content length of the information frame ;

7c) The network coding module expresses each element in the retransmission frame construction set into 8-bit form through binary conversion, and adds all the elements expressed in 8-bit form into an empty vector one by one, Obtain a binary vector, add this vector to the quasi-retransmission frame, so as to realize the retransmission frame construction set is added to the quasi-retransmission frame, and obtain the retransmission frame;

7d) The network coding module broadcasts retransmission frames to multiple receivers, and waits for the receivers to return response information;

(8) Update the dynamic list again:

8a) The storage sub-module adds 1 to the survival time of all linked lists, records the user serial number of the receiving end that returns the confirmation response among multiple receiving ends, and takes each recorded user serial number as an element, and the combination of all elements into a collection of feedback users;

8b) Determine whether the feedback user set is an empty set, if so, perform step 7d); if not an empty set, then perform step 8c);

8c) The dynamic list module extracts all elements from the retransmission frame construction set, and for the value of each element, index the dynamic linked list whose serial number is the same as the value of the element one by one in the storage submodule, and store the dynamic linked list for all obtained dynamic links by the storage submodule For all nodes on , if the value of any node exists in the feedback user collection, delete the node, and reduce the number of nodes in the linked list to which the node belongs;

8d) The dynamic list module deletes the linked list whose number of nodes is 0, and adds 1 to the survival time of all remaining linked lists;

8e) The dynamic list module deletes the retransmission frame construction set, the network coding module deletes the retransmission frame construction set, the quasi-retransmission frame and the retransmission frame, clears the feedback user set, and executes step 6a);

(9) Process the remaining information in the dynamic list:

9a) judge whether it is empty in the dynamic list, if empty, then execute step 91); otherwise execute step 9b);

9b) traverse all dynamic linked lists in the storage submodule, and find whether there is a dynamic linked list satisfying the following formula:

Among them, ψ _CRS represents the retransmission frame construction set, and ψ _i represents the set of all nodes in any dynamic linked list of the storage submodule;

9c) Judging whether there is a dynamic linked list that satisfies the equation 9b), if it exists, execute 9d); otherwise execute 9e);

9d) Select the one with the largest number of nodes among all the dynamic linked lists that satisfy the equation in 9b), if there is more than one dynamic linked list with the largest number of nodes, then arbitrarily select a dynamic linked list in the dynamic linked list with the largest number of nodes , assign values to the retransmission frame construction set and the destination user set according to the following formula:

_ψCRS ＝ _ψCRS ∪{MF _j }

ψ _CUD = ψ _CUD ∪ψ _j

Among them, ψ _CRS represents the retransmission frame construction set, MF _j represents the serial number of the selected dynamic linked list, ψ _CUD represents the set of destination users, and ψ _j represents the set of all nodes of the selected dynamic linked list, execute 9b);

9e) The matching submodule sends the retransmission frame construction set to the network coding module;

9f) The network coding module takes out all the elements from the retransmission frame construction set, sends the value of this group of elements to the mapping sub-module, and for the value of each element, indexes one by one the storage location of the information frame whose serial number is the same as the element value , extracting information frames one by one from the retransmission cache module according to the storage location;

9g) The network coding module takes the frame whose frame length is the length of the content part of the information frame and each bit is 0 as the initial retransmission frame, and performs a bit-by-bit exclusive OR operation on the obtained multiple information frames with the initial retransmission frame one by one , get the quasi-retransmission frame;

9h) The network coding module adds the retransmission frame construction set after the quasi-retransmission frame, thereby obtaining the retransmission frame, and temporarily saves the retransmission frame; the network coding module broadcasts the retransmission frame to multiple receivers, and waits for the receiver to return a response information;

9i) The storage sub-module records the user serial numbers of several receiving terminals that return confirmation responses among multiple receiving terminals, and combines the serial numbers of the several receiving terminals into a feedback user set;

9j) The dynamic list module extracts all elements from the retransmission frame construction set. For the value of each element, index the dynamic linked list with the same serial number as the value of the element in the storage sub-module one by one, and the storage sub-module compares all obtained dynamic linked lists. For all the nodes above, judge whether the value of the node exists in the feedback user set, if the value of any node exists in the feedback user set, delete the node, and reduce the number of nodes in the linked list to which the node belongs;

9k) The dynamic list module deletes the retransmission frame construction set, the network coding module deletes the retransmission frame construction set, the quasi-retransmission frame and the retransmission frame; clears the feedback user set, and executes step 9a);

9l) end;

With reference to accompanying drawing 4, receiving process of the present invention comprises the following steps:

(10) Preparation before transmission:

10a) Empty the cache contents in the information cache module and the decoding module;

10b) judge whether there is a data frame that needs to be received, if so, then perform step 10c); otherwise, perform step 12h); the present invention only cares about solving the problem of broadcast retransmission, and belongs to the application of the data link layer in wireless communication, The present invention does not care about how many information frames the upper layer of the link layer needs to receive. If the upper layer of the link layer needs an information frame, it will be extracted in the information cache module. If there is no information frame to be extracted, the system will consider that there is no information frame frame to be received;

10c) If the receiving sub-module does not receive the data frame, the feedback module sends a negative response to the sending end, and executes step 10c); otherwise, executes step 10d); the present invention only cares about solving the problem of broadcast retransmission, and belongs to the data link in wireless communication In the application of the channel layer, if the data frame passes the inspection of channel decoding, the receiving sub-module will receive the data frame after channel decoding; if the data frame fails the inspection of channel decoding, it will directly return Negative information, without going through the system;

10d) judging that the received data frame is a test frame, an information frame, and a retransmission frame; if it is a test frame received, perform step 10e); if it is an information frame, then perform step 11a); if received is a retransmission frame, then perform step 11c);

10e) The feedback module returns the confirmation response information, and returns the single-frame waiting time delay and allocable storage space, and executes step 10c); the single-frame waiting time delay is based on the timeliness requirements of the receiving end user, before the system runs Determined by the user, the latency of a single frame and the allocatable storage space are stored in the feedback module as fixed values;

(11) Receive data frame:

11a) The feedback module returns an acknowledgment response to the sending end, and the parsing submodule extracts the serial number of the information frame from the frame header of the information frame, and the cache module judges whether there is enough storage space, and if so, executes step 11b); otherwise, cache The submodule releases the storage space of an information frame with the smallest sequence number among the plurality of information frames stored, resolves the submodule to delete the correspondence between the sequence number and the storage address of the information frame, and executes step 11b); 11b) the cache submodule stores the received information frame, the parsing submodule saves the correspondence between the information frame storage address and the serial number, and executes step 10b);

11c) The parsing submodule reads the first bit after the frame header of the retransmission frame and the length bits of the subsequent information frame, and uses the read content as a quasi-recovery frame;

11d) The parsing submodule reads all the bits after the information frame length bits, and uses the read content as a retransmission frame construction set, sends the retransmission frame construction set and the quasi-recovery frame to the decoding module, and performs step 12a) ;

(12) Retransmission frame decoding:

12a) The decoding module uses two empty sets as the decoding set and the target set. The decoding module will extract the values of all elements in the retransmission frame construction set. For the value of each element, if there is an information frame sequence in the information buffer module If there is an information frame with the same number as the value of the element, add this information frame sequence number as an element to the decoding set, otherwise add this information frame sequence number as an element to the destination set;

12b) Determine the number of elements in the destination set, if the number of elements is 0, the feedback module returns a confirmation response to the sending end, and execute step 12g); if the number of elements is greater than or equal to two, call the feedback module to return a negative response to the sending end , execute step 12g); if the number of elements is only 1, call the feedback module to return a confirmation response to the sender, and execute step 12c);

12c) The decoding module takes out all the elements from the decoding set, sends the value of this group of elements into the parsing sub-module, and for the value of each element, indexes the storage locations of the information frames whose serial numbers are the same as the element values one by one, Extract information frames one by one from the cache sub-module according to the storage location;

12d) performing bit-by-bit XOR operation on the extracted multiple information frames one by one with the quasi-recovery frame to obtain the recovery frame, and using the unique element in the target set as the serial number of the recovery frame;

12e) The cache module judges whether there is enough storage space, and if so, executes step 12f); otherwise, the cache submodule releases the storage space of an information frame with the smallest sequence number among the stored information frames, and the resolution submodule releases the sequence number The serial number of the smallest information frame and the corresponding relationship between the storage address are deleted, and step 12f is performed);

12f) The cache sub-module stores the recovery frame obtained, and the parsing sub-module saves the serial number of the recovery frame and the corresponding relationship between the storage address of the recovery frame;

12g) Delete the retransmission frame construction set, quasi-recovery frame, decoding set, purpose set and recovery frame existing in each module of the receiving end, and perform step 10b);

12h) end.

Claims (6)

1. a broadcast repeating method for coding Network Based, adopts the broadcast retransmission system of network code to realize, comprises two steps in process of transmitting and receiving course; Wherein:

Described process of transmitting comprises the steps:

(1) test pack is sent:

1a) the transmitting time of negotiation module recorded announce test frame, waits for the feedback information coming from multiple receiving terminal;

If 1b) negotiation module receives the confirmation response message of all multiple receiving terminals, then perform step 1c); If negotiation module have received negative response or do not receive the feedback information of any one receiving terminal, then perform step 1a);

1c) negotiation module record each confirm the time of reception of response message, and the single frames recording each feedback in multiple receiving terminal can wait for time delay and can memory allocated space;

(2) the system single frames maximum keep alive time is obtained:

2a) negotiation module chooses one maximum in multiple confirmation response message time of reception, maximum time of reception is deducted the transmitting time of test frame, obtains Systematic Communication time delay;

2b) choose minimum one in Yanzhong when multiple single frames can be waited for and can wait for time delay as system single frames;

2c) choose multiple can be minimum in memory allocated space one can memory allocated space as system;

2d) will the maximum integer of following formula be met, as the system single frames maximum keep alive time:

(NH-1)TR＜TM

(NH-1)C _O＜CM

Wherein, NH represents the system single frames maximum keep alive time, and TR represents Systematic Communication time delay, and TM represents that system single frames can wait for time delay, C _orepresent the memory space required for an information frame, CM represents that system can memory allocated space;

(3) dynamic link table initialization:

3a) send buffer module by the system single frames maximum keep alive time divided by 2, house tail rounds, and obtains primary quantity;

3b) send buffer module and broadcast a primary quantity information frame continuously to multiple receiving terminal;

3c) sub module stored is set up and primary quantity information frame dynamic link table one to one;

3d) sub module stored by the sequence number of a primary quantity dynamic link table respectively assignment be corresponding information frame sequence number, 1 is added after primary quantity being deducted the individual information frame sequence number of primary quantity, using the result that the obtains life span as a primary quantity dynamic link table, by nodal value each in each dynamic link table respectively assignment be, to the information frame corresponding to this dynamic link table, return user's sequence number of the receiving terminal of NACK messages;

3e) travel through all chained lists in sub module stored, extract the sequence number in gauge outfit successively, by information frame corresponding for extracted information frame sequence number by sending buffer module unloading to re-transmission buffers module, record the memory address of the information frame of now unloading, and set up extracted information frame sequence number and the corresponding relation of information frame memory address by mapping submodule; Again travel through the node number of all chained lists in sub module stored, deletion of node number is the dynamic link table of 0, deletes the information frame that this dynamic link table is corresponding, deletes the corresponding relation that this dynamic link table is corresponding;

(4) information frame is sent:

4a) send buffer module and checked whether that information frame is to be sent, if had, then send buffer module and broadcast next information frame, perform step 4b); Otherwise, perform step 9a);

If 4b) sub module stored receives the confirmation response message of all multiple receiving terminals, then perform step 5a); If have received negative response or do not receive the feedback information of any one receiving terminal, then perform step 5b);

(5) Regeneration dynamics list:

5a) send buffer module the storage area of sent information frame is discharged, after the life span of current all chained lists is added 1 by sub module stored, perform step 6a);

5b) send buffer module by sent information frame unloading to retransmitting cache module, mapping submodule creates the corresponding relation of information frame memory address and sequence number;

5c) sub module stored is using the sequence number of the sequence number of sent information frame as dynamic link table, using 0 as the life span of dynamic link table, by the number of the receiving terminal receiving information frame that fails, as the node number of dynamic link table, by the user's sequence number of the receiving terminal receiving information frame that fails, as the node of dynamic link table, obtain a new dynamic link table;

5d) life span of chained lists all in sub module stored is added 1 by sub module stored, performs step 6a);

(6) retransmission frame is constructed:

6a) judge in all dynamic link tables, whether the time-to-live of the dynamic link table that sequence number is minimum is less than the difference that the system single frames maximum keep alive time deducts 2, if be less than, then performs step 6c); If be greater than or equal to, perform step 6b);

6b) matched sub-block calls maximum matching algorithm, the dynamic link table minimum to sequence number in all dynamic link tables carries out maximum matching operation, obtain retransmission frame construction set, retransmission frame construction set is sent to network code module by matched sub-block, performs step 7a);

6c) matched sub-block calls perfect matching algorithm, the dynamic link table minimum to sequence number in all dynamic link tables carries out perfect matching, judge whether matching result is retransmission frame construction set, if, then retransmission frame construction set is sent to network code module by matched sub-block, performs step 7a); If the result of computing is " cannot carry out perfect matching ", then perform step 4a);

(7) retransmission frame is sent:

7a) network code module takes out all elements from retransmission frame construction set, the value of this group element is sent into mapping submodule, for the value of each element, the memory location of the information frame that index information number of frames is identical with element value one by one, according to memory location information extraction frame one by one from repeating transmission cache module;

7b) network code module will, frame length is the length of information frame content part, each bit be the frame of 0 as initial transmission frame, by extract multiple information frames carry out with initial transmission frame by bit XOR one by one, obtain accurate retransmission frame;

7c) network code module adds retransmission frame construction set after accurate retransmission frame, obtains retransmission frame;

7d) network code module is to multiple receiving terminal broadcast retransmission frame, and wait-receiving mode end returns response message;

(8) Regeneration dynamics list again:

8a) life span of all chained lists is added 1 by sub module stored, is recorded by the user's sequence number returning the receiving terminal confirming response, and user's set of serial numbers of record is synthesized a feedback user set in multiple receiving terminal;

8b) judge whether feedback user set is empty set, if so, then perform step 7d); If not empty set, then perform step 8c);

8c) dynamic listing module extracts all elements from retransmission frame construction set, for the value of each element, the sequence number dynamic link table identical with the value of element is indexed out one by one in sub module stored, sub module stored is to all nodes on all dynamic link tables obtained, if the value of any one node is present in feedback user set, then by this knot removal, and the node number of chained list belonging to this node is subtracted 1;

8d) dynamic listing module deletion of node number is the chained list of 0, and the life span of all remaining chained lists is added 1;

8e) dynamic listing module deletes retransmission frame construction set, and network code module deletes retransmission frame construction set, accurate retransmission frame and retransmission frame, empties feedback user set, performs step 6a);

(9) remaining information in dynamic listing is processed:

9a) judge in dynamic listing whether be empty, if it is empty, then perform step 9i); Otherwise perform step 9b);

9b) matched sub-block calls maximum matching algorithm, and the dynamic link table minimum to sequence number in all dynamic link tables carries out maximum matching operation, obtains retransmission frame construction set, and retransmission frame construction set is sent to network code module by matched sub-block;

9c) network code module takes out all elements from retransmission frame construction set, the value of this group element is sent into mapping submodule, for the value of each element, the memory location of the information frame that index information number of frames is identical with element value one by one, according to memory location information extraction frame one by one from repeating transmission cache module;

9d) network code module be the length of information frame content part using frame length, each bit be the frame of 0 as initial transmission frame, the multiple information frames obtained are carried out with initial transmission frame one by one, by bit XOR, obtain accurate retransmission frame;

9e) network code module adds retransmission frame construction set after accurate retransmission frame, thus obtains retransmission frame, and retransmission frame is temporarily preserved; Network code module is to multiple receiving terminal broadcast retransmission frame, and wait-receiving mode end returns response message;

9f) the user's sequence number returning the receiving terminal confirming response in multiple receiving terminal is recorded by sub module stored, and described receiving terminal set of serial numbers is synthesized a feedback user set;

9g) dynamic listing module extracts all elements from retransmission frame construction set, for the value of each element, the sequence number dynamic link table identical with the value of element is indexed out one by one in sub module stored, sub module stored is to all nodes on all dynamic link tables obtained, whether the value of decision node is present in feedback user set, if the value of any one node is present in feedback user set, then by this knot removal, and the node number of chained list belonging to this node is subtracted 1;

9h) dynamic listing module deletes retransmission frame construction set, and network code module deletes retransmission frame construction set, accurate retransmission frame and retransmission frame; Empty feedback user set, perform step 9a);

9i) terminate;

Described receiving course comprises the steps:

(10) prepare before transmission:

10a) empty the cache contents in information cache module and decoding module;

10b) judge whether to exist the Frame needing to receive, if having, then perform step 10c); Otherwise, perform step 12h);

If 10c) receive submodule not receive Frame, feedback module sends negative response to transmitting terminal, performs step 10c); Otherwise perform step 10d);

The Frame that 10d) judgement receives is test frame, information frame, retransmission frame; If what receive is test frame, perform step 10e); If what receive is information frame, then perform step 11a); If what receive is retransmission frame, then perform step 11c);

10e) feedback module returns confirmation response message, and return single frames can wait for time delay and can memory allocated space perform step 10c);

(11) receiving data frames:

11a) feedback module to transmitting terminal return confirm response, analyzing sub-module from the frame head of information frame, the sequence number of information extraction frame, cache module judges whether enough memory spaces, if having, then perform step 11b); Otherwise, the memory space of the information frame that sequence number is minimum in multiple information frames that cache sub-module release stores, analyzing sub-module deletes the sequence number of information frame and the corresponding relation of memory address, performs step 11b);

11b) cache sub-module stores the information frame received, and analyzing sub-module preserves the corresponding relation of information frame memory address and sequence number, performs step 10b);

First bit 11c) after analyzing sub-module reading retransmission frame frame head and an information frame length bit afterwards, recover frame using read content as standard;

11d) all bits after an analyzing sub-module reading information frame length bit, and using read content as retransmission frame construction set, retransmission frame construction set is recovered frame with standard and is sent to decoding module, perform step 12a);

(12) retransmission frame decoding:

12a) decoding module using two empty sets as decoding set and destination aggregation (mda), decoding module will extract the value of all elements in retransmission frame construction set, for the value of each element, if there is the information frame that information frame sequence number is identical with the value of element in information cache module, then this information frame sequence number is added in decoding set as an element, otherwise this information frame sequence number is added in destination aggregation (mda) as an element;

12b) judge the element number of destination aggregation (mda), if element number is 0, feedback module returns to transmitting terminal and confirms response, performs step 12g); If element number is more than or equal to two, then calls feedback module and return negative response to transmitting terminal, perform step 12g); If element number is only 1, then calls feedback module and return confirmation response to transmitting terminal, perform step 12c);

12c) decoding module takes out all elements from decoding set, the value of this group element is sent into analyzing sub-module, for the value of each element, the memory location of the information frame that index information number of frames is identical with element value one by one, according to memory location information extraction frame one by one from cache sub-module;

12d) the multiple information frames extracted being recovered frame one by one with standard carries out by bit XOR, and be restored frame, using element unique in destination aggregation (mda) as the sequence number recovering frame;

12e) cache module judges whether enough memory spaces, if having, performs step 12f); Otherwise the memory space of minimum for sequence number in the multiple information frames a stored information frame discharges by cache sub-module, and the corresponding relation of the sequence number of information frame minimum for sequence number and memory address is deleted by analyzing sub-module, performs step 12f);

12f) cache sub-module stores the recovery frame obtained, the sequence number of analyzing sub-module saving/restoring frame and the corresponding relation of the memory address of recovery frame;

12g) delete the retransmission frame construction set existed in each module of receiving terminal, accurate recovery frame, decoding set, destination aggregation (mda) and recover frame, performing step 10b);

12h) terminate.

2. the broadcast repeating method of coding Network Based according to claim 1, it is characterized in that: step 1c) and step 10e) described in single frames can wait for that time delay refers to, any one receiving terminal in multiple receiving terminal, from any one Frame being carried out to first time request to the correct maximum stand-by period of bearing receiving this Frame.

3. the broadcast repeating method of coding Network Based according to claim 1, it is characterized in that: step 1c) and step 10e) described in can refer in memory allocated space, the memory space of the cache sub-module of any one receiving terminal in multiple receiving terminal.

4. the broadcast repeating method of coding Network Based according to claim 1, is characterized in that: step 6b) and step 9b) described in maximum matching algorithm concrete steps as follows:

The first step, retransmission frame construction set, object user set are set to empty set, sequence number in dynamic link table minimum for sequence number in all dynamic link tables is added in retransmission frame construction set as element, using in dynamic link table minimum for sequence number in all dynamic link tables comprise all nodes as element add one by one object user set in;

Second step, dynamic link tables all in traversal sub module stored, find whether there is the dynamic link table meeting following formula:

Wherein, ψ _cRSrepresent retransmission frame construction set, ψ _irepresent the set that all nodes of any one dynamic link table of sub module stored are formed;

3rd step, judges whether to be filled with equation dynamic link table in sufficient second step, if exist, performs the 4th step; Otherwise perform the 5th step;

4th step all meet in the dynamic link table of equation in second step choose maximum one of node number, if more than one of the dynamic link table that node number is maximum, then in the dynamic link table that described node number is maximum, choose arbitrarily a dynamic link table, according to following formula retransmission frame construction set and object user gathered and carry out assignment:

ψ _CRS＝ψ _CRS∪{MF _j)

ψ _CUD＝ψ _CUD∪ψ _j

Wherein, ψ _cRSrepresent retransmission frame construction set, MF _jthe sequence number of this dynamic link table selected by expression, ψ _cUDrepresent object user set, ψ _jthe set that all nodes of this dynamic link table selected by expression are formed, performs second step;

5th step, return retransmission frame construction set to matched sub-block, maximum matching algorithm terminates.

5. the broadcast repeating method of coding Network Based according to claim 1, is characterized in that: step 6c) described in perfect matching algorithm concrete steps as follows:

The first step, retransmission frame construction set, object user set are set to empty set, sequence number in dynamic link table minimum for sequence number in all dynamic link tables is added in retransmission frame construction set, by dynamic link table minimum for sequence number in all dynamic link tables comprise all nodes add one by one object user set in;

Second step, dynamic link tables all in traversal sub module stored, find whether there is the dynamic link table meeting following formula:

Wherein, ψ _cRSrepresent retransmission frame construction set, ψ _irepresent the set that all nodes of any one dynamic link table of sub module stored are formed;

3rd step, judgement judges whether to be filled with equation dynamic link table in sufficient second step, if exist, performs the 4th step; Otherwise perform the 5th step;

4th step, all meet in the dynamic link table of equation in second step choose maximum one of node number, more than one that if node number is maximum, if then choose arbitrarily a dynamic link table in the dynamic link table that described node number is maximum, according to following formula retransmission frame construction set and object user gathered and carry out assignment:

ψ _CRS＝ψ _CRS∪{MF _j)

ψ _CUD＝ψ _CUD∪ψ _j

Wherein, ψ _cRSrepresent retransmission frame construction set, MF _jthe sequence number of this dynamic link table selected by expression, ψ _cUDrepresent object user set, ψ _jthe set that all nodes of this dynamic link table selected by expression are formed, performs Step2;

5th step, if object user set includes user's sequence number of all receiving terminals, then returns retransmission frame construction set to matched sub-block, terminates perfect matching; Otherwise, send the information of " cannot perfect matching be carried out " to matched sub-block, terminate perfect matching.

6. the broadcast repeating method of coding Network Based according to claim 1, it is characterized in that: step 7b), 9d), 12d) described in refer to by bit XOR, from first bit of identical two frames of length to last bit, for a pair bit of each same position, carry out mould two He.