# Network Coding for Efficient Video Multicast in Device-to-Device Communications
## 3 System Model  
### Network Model  
In the wireless multi-hop multicast network, as shown in Figure 1, source node \(S\) encodes the data that needs to be transmitted and then sends it out through a multicast connection. The destination nodes \((\text{D}_{1},\text{ D}_{2},\text{ D}_{3},\text{ D}_{4})\) perform re-encoding operations after receiving part of the data, and then send the re-encoded packets to the surrounding nodes. To recover the original data, the mobile devices working as destination nodes only need to receive a certain number of linearly independent packets. Different from the traditional replication-based network transmission method, the network-coding-based transmission method needs to process the data slices before transmission. The source node divides the video frame with length \(L\) to \(K\) slices with equal size, each slice has a fixed length of \(L/K\), and when it cannot provide exact division, some zero elements are appended to the end of the last slice. Each video frame is divided into \(K\) data slices \(P(p_{1},\)\(p_{2},\)\(p_{3},\ldots\)\(p_{K})\); then, generate an \(n\)-by-\(K\) random matrix \(M(a_{i1},\)\(a_{i2},\)\(a_{\beta},\ldots\)\(a_{iK})(1\leq i\leq n)\) from finite field \(GF(2^{\ast}q)\), at last, multiply the random matrix \(M\) with data slices to generate \(n\) encoded slices \(Y_{1},\ Y_{2},\ Y_{3},\ldots\ Y_{n}\) with the same size, as shown in Equation (1), where \(n\geq K\). When \(n=K\), it implies that there is no redundant data; when \(n>K\), \(n-K\) is the number of redundant data slices. Since the scheme in this paper reduces the computational overhead of the source node through the re-encoding operation, we can reduce the redundancy as much as possible according to the network condition. After the encoding operation, all data slices \(Y_{i}(i\geq K)\) are linearly independent with a high probability [34]. \[\left[ \begin{array}{c}Y_{1}\\ Y_{2}\\ \vdots\\ Y_{n}\end{array} \right]=M^{T}=\left[ \begin{array}{cccc}a_{11}&a_{12}& \cdots&a_{1K}\\ a_{21}&a_{22}&\cdots&a_{2K}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nK}\end{array} \right]\left[ \begin{array}{c}p_{1}\\ p_{2}\\ \vdots\\ p_{K}\end{array} \right] \tag{1}\]  
The source node mixes the encoded data slices with corresponding row vectors in random matrix \(M\), and then sends out the newly generated packets. The destination nodes conduct a re-encoding operation after receiving sufficient linearly independent packets. During the re-encoding process, a \(t\)-by-\(h\) random matrix \(R(b_{j1},\)\(b_{j2},\)\(b_{j3},\ldots\)\(b_{jh})(1\leq j\leq t)\) is generated. \(h(h\leq K)\) is the number of received data slices; \(t\) is the number of data slices generated after re-encoding the \(h\) data slices; then, multiply the random matrix with the matrix data \(P_{M}(a_{i+1},\)\(a_{i+2},\)\(a_{i+3},\ldots\)\(a_{i+h})\) in \(h\) data slices and the encoded data \(P_{Y}(Y_{i+1},\)\(Y_{i+2},\)\(Y_{i+3},\ldots\)\(Y_{i+h})\) respectively, and \(t\) re-encoded data slices \((X_{t},Z_{t})\) are further generated, in which, \(X_{t}(c_{i+1},\)\(c_{i+2},\)\(c_{i+3},\ldots\)\(c_{i+h})\) is the corresponding random matrix of  
Figure 1: Network model. re-encoded data, as shown in Equation (2). Finally, the destination nodes send out the data obtained after re-encoding. \[\left[ \begin{array}{c}X_{1}\ Z_{1}\\ X_{2}\ Z_{2}\\ \vdots\\ X_{t}\ Z_{t}\end{array} \right]=R(P_{M}P_{Y})^{T}=\left[ \begin{array}{cccc}b_{ 11}&b_{12}&\cdots&b_{1h}\\ b_{21}&b_{22}&\cdots&b_{2h}\\ \vdots&\vdots&\ddots&\vdots\\ b_{t1}&b_{t2}&\cdots&b_{h}\end{array} \right]\left[ \begin{array}{c}a_{i+1}\ Y_{i+1}\\ a_{i+2}\ Y_{i+2}\\ \vdots\\ a_{i+h}\ Y_{i+h}\end{array} \right] \tag{2}\]  
The destination nodes will conduct decoding operation after receiving \(K\) linearly independent data slices. These \(K\) data slices could be the initially encoded data slices, or the combination of the initially encoded slices and re-encoded data slices.