CN108616332B - Multi-user data transmission method based on random linear network coding - Google Patents

Abstract

The invention discloses a multi-user data transmission method based on random linear network coding. This method uses network coding technology on the storage server: the server first calculates the set of files to be transmitted according to the download requests of all users; then uses the random linear network coding method to encode these files, and then encodes the encoded The data is sent to the user; when the user receives a sufficient number of data packets, all the original files involved in the encoding can be decoded, and the files that he is interested in are selected from them, and other files are discarded; finally, the storage server uses the user's feedback information. Know whether the user has successfully decoded; when the confirmation information from all users is received, the transmission ends. The multi-user data transmission method of the present invention can improve the overall transmission efficiency and increase the throughput of the network.

Description

A Multi-User Data Transmission Method Based on Random Linear Network Coding

technical field

The invention belongs to the technical field of wireless network communication, and in particular relates to a multi-user data transmission method based on random linear network coding.

Background technique

With the development of social economy and science and technology, and the continuous advancement and deepening of information construction, wireless networks and wireless communication data transmission are more and more widely used in various fields. Among them, multicast is one of the most commonly used data transmission methods in wireless networks. In wireless multicast, because the wireless channel is easily affected by interference, attenuation, weakening, etc., the wireless channel sometimes presents a high channel bit error rate or packet loss rate, resulting in poor wireless link quality and easy packet transmission. loss, which seriously affects the transmission efficiency. To solve this problem, one of the traditional solutions is to use retransmission technology, such as Automatic Repeat Request (ARQ) strategy: when a data packet is not successfully received by all users, the source node will continue to retransmit the data packet. packet until all receiving nodes have successfully received the packet. Therefore, the transmission efficiency of the retransmission technology is actually not high.

Network coding is another technique that improves the efficiency of wireless multicast. The sender first uses the network coding technology to encode the original data packet, generates the encoded data packet, and then sends it to the user. For the user, all the original data packets can be successfully decoded only by receiving a sufficient number of linearly independent encoded data packets. Therefore, there is no packet retransmission problem that seriously affects multicast efficiency.

The present invention applies network coding to a single-hop wireless network, and is mainly used to improve the transmission efficiency of data packets. There is a group of mobile users who want to download one or more files they are interested in from a central storage server; the files that different users want to download may be duplicated, for example, some popular resources will be downloaded by multiple users. In view of the above-mentioned characteristics, the present invention uses network coding technology on the storage server: the server first calculates the set of files to be transmitted according to the download requests of all users; Send the encoded data to the user; when the user receives a sufficient number of data packets, all the original files involved in the encoding can be decoded, and the files that they are interested in can be selected from them, and other files are discarded; finally, the storage server can pass the user The feedback information to know whether the user has successfully decoded; when the confirmation information from all users is received, the transmission ends.

SUMMARY OF THE INVENTION

The invention provides a multi-user data transmission method based on random linear network coding for file transmission in wireless network.

The technical scheme of the present invention is:

A data transmission method based on random linear network coding, comprising the following processing steps:

记第i个用户收到的线性独立的数据包的个数为c_i,其初始值设为0，即

Suppose the storage server has m data packets, denoted as X _i , X ₂ , K, X _m ; there are n users, and each user must download one or more data packets they want from the storage server; denote the first The set of data packets to be downloaded by i users is A _i , we have

The number of linearly independent data packets received by the i-th user is c _i , and its initial value is set to 0, that is,

(1) Transmission preparation stage:

Each user establishes a connection with the storage server, and initiates a data packet transmission request to the storage server, informing the storage server of the set of data packets A _i ,i∈{1,K,n} to be downloaded; the server receives all user-initiated After downloading the request, calculate the set of all data packets that need to be transmitted, denoted as B, so we have B=A ₁ UA ₂ UKUA _n .

(2) Transmission stage:

In each time slot in the transmission phase, the storage server and the user transmit and receive data packets according to the following steps:

其中|B|表示集合B中的元素的个数，a₁,K,a_|B|为编码系数，在每次编码的时候从编码域F_q＝{0,1,K,q-1}中随机选取,q表示编码域的大小，为事先确定好的整数。进入步骤(2.2)。(2.1) The storage server uses the random linear network coding method to generate an encoded data packet Y, which is a random linear combination of all the data packets in the set B, namely

where |B| represents the number of elements in the set B, a ₁ , K, a _|B| are the coding coefficients, from the coding field F _q ={0,1,K,q-1} in each coding It is randomly selected from , and q represents the size of the coding field, which is an integer determined in advance. Proceed to step (2.2).

(2.2) The storage server broadcasts the generated encoded data packet to all users through a wireless channel. Proceed to step (2.3).

(2.3) At the receiving end, if the i-th user successfully receives the data packet broadcast by the storage server in the current time slot, the user determines whether the data packet is linearly independent from other data packets in its own cache. If so, add the data packet to the cache, and at the same time increase the value of c _i by 1, that is, c _i = _ci +1, and enter step (2.4); otherwise, discard the data packet and enter step (2.6).

用户可从集合B中找出所有自己所要下载的数据包，并丢弃那些自己不需要的数据包，进入步骤(2.5)。反之，则返回步骤(2.1)。(2.4) If c _i = |B|, it means that the i-th user has received a sufficient number of linearly independent encoded data packets, so Gaussian elimination method can be used to decode all the original data packets in set B. because

The user can find all the data packets that he wants to download from the set B, and discard those data packets that he does not need, and go to step (2.5). Otherwise, go back to step (2.1).

(2.5) The i-th user sends an ACK confirmation message to the storage server to inform the storage server that it has decoded the data packet to be downloaded. After that, the user enters a silent state, discards other data packets received in the subsequent time slot, and proceeds to step (2.6).

(2.6) The storage server determines whether ACK confirmation information has been received from all users. If so, the transmission phase ends, otherwise, return to step (2.1).

The present invention has the following characteristics:

The storage server of the present invention does not simply broadcast the original data packets to the users, but utilizes the characteristic of the repetition of the files that different users want to download, adopts the method of random linear network coding, and collects all the data packets to be sent first. post-encoded and then sent to the user. Using this method, although the number of data packets that each user needs to receive becomes more than before, the storage node does not need to retransmit the lost data packets, so the overall transmission efficiency can be improved and the network throughput can be increased. .

Description of drawings

FIG. 1 is a schematic diagram of a network of the present invention.

FIG. 2 is a flow chart of the data transmission method of the present invention.

Detailed ways

In order to further illustrate the present invention, a preferred embodiment is given below. This example only illustrates the principle of the present invention and does not represent any limitation of the present invention.

Suppose there is a storage server with a total of 10 different files. It is assumed that each file contains only one data packet, so there are 10 original data packets on the server, denoted as X ₁ , X ₂ , K, X ₁₀ . There are currently 3 users, and the sets of data packages to be downloaded are A ₁ ={X ₁ ,X ₂ ,X ₃ },A ₂ ={X ₃ ,X ₄ ,X ₅ ,X ₆ },A ₃ ={ X ₂ , X ₃ , X ₆ , X ₇ }. The number of linearly independent data packets received by the user, and its initial value is 0, that is, c ₁ =c ₂ =c ₃ =0. Let the size of the coding field be q=16, so the coding field is F ₁₆ ={0,1,K,15}.

The three users first establish a connection with the server, send a download request to the server, and inform the server of the data packet sets A ₁ , A ₂ , and A ₃ that they want to download. After the server receives all user download requests, it calculates the set of all data packets to be transmitted, that is, B=A ₁ UA ₂ UA ₃ ={X ₁ ,X ₂ ,X ₃ ,X ₄ ,X ₅ ,X ₆ , X ₇ }.

其中编码系数a₁,a₂,K,a₇从编码域F₁₆＝{0,1,K,15}中随机选取。服务器将编码后的数据包Y₁广播给3个用户。假设第1，2个用户成功接收到了数据包Y₁，而第3个用户因为噪声的影响没有成功接收。由于用户1和用户2的缓存中没有任何数据包，所以用户1和用户2将Y₁放入自己的缓存中，并更新用户收到的线性独立的数据包的个数c₁和c₂，即c₁＝c₂＝1。由于c₁,c₂,c₃的值都小于|B|＝7，因此3个用户都不需要发送ACK确认信息给服务器。In the first time slot of the transmission phase, the server uses the random linear network coding method to generate the first encoded data packet, denoted as

The coding coefficients a ₁ , a ₂ , K, a ₇ are randomly selected from the coding field F ₁₆ ={0,1,K,15}. The server broadcasts the encoded packet Y ₁ to 3 users. It is assumed that the 1st and 2nd users successfully receive the data packet Y ₁ , while the 3rd user fails to receive it due to the influence of noise. Since user 1 and user 2 do not have any data packets in their caches, user 1 and user 2 put Y ₁ into their own caches, and update the numbers c ₁ and c ₂ of linearly independent data packets received by users, That is, c ₁ =c ₂ =1. Since the values of c ₁ , c ₂ , and c ₃ are all less than |B|=7, the three users do not need to send ACK confirmation information to the server.

其中编码系数a₁,a₂,K,a₇从编码域F₁₆＝{0,1,K,15}中随机选取。服务器将编码后的数据包Y₂广播给3个用户。假设只有第2个用户成功接收到了数据包Y₂。由于用户2的缓存已有数据包Y₁，所用户2需判断Y₂和Y₁是否线性独立。若是，则将Y₂放入自己的缓存，同时更新c₂＝2；反之，则丢弃Y₂。由于c₁,c₂,c₃的值仍小于|B|＝7，因此3个用户都不需要发送ACK确认信息给服务器。In the second slot of the transmission phase, the server generates the second encoded packet

The coding coefficients a ₁ , a ₂ , K, a ₇ are randomly selected from the coding field F ₁₆ ={0,1,K,15}. The server broadcasts the encoded packet Y ₂ to 3 users. Suppose that only the 2nd user successfully receives the packet Y ₂ . Since the cache of user 2 already has data packet Y ₁ , user 2 needs to judge whether Y ₂ and Y ₁ are linearly independent. If so, put Y ₂ into its own cache, and update c ₂ =2 at the same time; otherwise, discard Y ₂ . Since the values of c ₁ , c ₂ , and c ₃ are still smaller than |B|=7, the three users do not need to send ACK confirmation information to the server.

In the next time slot, the storage server and the user transmit and receive data packets according to the above method. If a user receives a sufficient number of linearly independent data packets, for example, c ₁ =7, then user 1 can decode all data packets in set B through Gaussian elimination, and send an ACK to the server at the same time. message to inform the server that it has successfully decoded. If the server receives the ACK information from all three users, the entire transmission process ends.

The present invention is a data transmission method based on random linear network coding, and belongs to the technical field of wireless network communication; the present invention uses encoded data packets to send instead of original data packets, avoids the problem of retransmission of lost data packets in the traditional transmission method, and improves the The data transmission efficiency and network throughput are improved.

The preferred embodiments and principles of the present invention have been described in detail above. For those of ordinary skill in the art, according to the ideas provided by the present invention, there will be changes in the specific embodiments, and these changes should also be regarded as the present invention. scope of protection.

Claims (1)

1. a multi-user data transmission method based on random linear network coding, is characterized in that, comprises the following processing steps: Suppose the storage server has m data packets, denoted as X _i , X ₂ ,..., X _m ; there are _n users, each user needs to download one or more data packets they want from the storage server; Denote the set of data packets to be downloaded by the i-th user as A _i ,

The number of linearly independent data packets received by the i-th user is c _i , and its initial value is set to 0, that is,

(1) Transmission preparation stage: Each user establishes a connection with the storage server, and initiates a data packet transmission request to the storage server, informing the storage server of the set of data packets A _i ,i∈{1,...,n} to be downloaded by the storage server; the server receives all users After the download request is initiated, calculate the set of all data packets to be transmitted, denoted as B, B=A ₁ ∪A ₂ ∪...∪A _n ; (2) Transmission stage: In each time slot in the transmission phase, the storage server and the user transmit and receive data packets; The concrete steps of the described step (2) transmission stage are: (2.1) The storage server uses the random linear network coding method to generate an encoded data packet Y, which is a random linear combination of all the data packets in the set B, namely

Where |B| represents the number of elements in the set B, a ₁ ,...,a _|B| is the coding coefficient, which is obtained from the coding field F _q ={0,1,..., q-1} is randomly selected, and q represents the size of the coding field, which is an integer determined in advance; go to step (2.2); (2.2) The storage server broadcasts the generated encoded data packet to all users through the wireless channel, and enters step (2.3); (2.3) At the receiving end, if the i-th user successfully receives the data packet broadcast by the storage server in the current time slot, the user determines whether the data packet is linearly independent from other data packets in its own cache; The data packet is added to the cache, and the value of c _i is increased by 1 at the same time, that is, c _i = _ci +1, enter step (2.4); otherwise, discard the data packet and enter step (2.6); (2.4) If c _i =|B|, it means that the i-th user has received a sufficient number of linearly independent encoded data packets, so Gaussian elimination method can be used to decode all the original data packets in set B; because

The user can find all the data packets that he wants to download from the set B, and discard those data packets that he does not need, and go to step (2.5); otherwise, go back to step (2.1); (2.5) The i-th user sends an ACK confirmation message to the storage server to inform the storage server that it has decoded the data packet to be downloaded; then the user enters a silent state and discards other data packets received in the subsequent time slot, Enter step (2.6); (2.6) The storage server judges whether the ACK confirmation information has been received from all users; if so, the transmission phase ends, otherwise, it returns to step (2.1).

Images