## 4 Design of Network Coding Tree Algorithm  
In our model, it is assumed that all sink nodes can encode and decode packets freely, while the rock-bottom sensor nodes cannot. When a particular sink node receives original packets from associated sensor nodes, it attempts to encode the native information into a single message. The sink node will then deliver those encoded messages. An elastic transmission mechanism following the principle of random linear coding [29; 30] is presented to ensure that the entire sink node information encoding will be not linearly dependent. This fault-tolerant mechanism consists of two parts: the construction of a network coding tree and the design of a greedy grouping algorithm. The construction of the spanning tree used for illustration of the coding relationship focuses on generating a tree that can associate all rock-bottom sensor nodes \(U_{s}\), while all leaf nodes on the tree are located among their associated sink nodes \(L_{s}\). With this method, destination nodes can construct linearly independent combinations according to the connection relationships of network nodes. The five-step algorithm to establish the spanning tree is given in detail below. In the first step, a depth-first search (DFS) or breadth-first search (BFS) strategy can be employed to scan the full logical topology established by a WSN. In this way, a spanning tree can be produced with the root node deployed at node \(L_{s}\). In the second step, it is assumed that the leaf elements in this spanning tree include some sensor node \(U_{s}\). If there exist some sensors which are leaf nodes in coding tree, these nodes are denoted as \(u\). In the third step, the algorithm constantly scans the entire network topology until it finds a neighbour node \(L_{s}\) of \(u\). We indicate this sink node as \(x\). Note that node \(u\) cannot be a child node of node \(x\). In the fourth step, the algorithm pollards this coding spanning tree to ensure its leaf elements do not include any \(U_{s}\) elements. In the fifth step, the algorithm continues to pollard unnecessary \(L_{s}\) nodes if leaf nodes contain any \(U_{s}\) elements. The fourth step of this algorithm can benefit from a spanning-tree construction proposed in the literature [31; 32]. It can be proven that the polynomial time-complexity analysis of establishing this spanning tree will be \(O(\left|V\right|)\), while the time complexities of both the BFS and DFS algorithms are \(O(\left|E\right|)\). The pseudo-code of the network coding algorithm is given in Table 1 below. In order to better explain the implementation of the coding tree, below is a concrete implementation example. The example network topology is shown in Figure 3. Figure 3(a) depicts the result of DFS search with \(C\) as the root node. Using the steps 2-6, we can get the result in Figure 3(b). Figure 3(c),d depict cutting off the corresponding edge and trimming off excess leaf nodes. \begin{table}
\begin{tabular}{l} \hline \hline
**Algorithm for Constructing Coding Tree** \\ \hline
1: Use the DFS (depth-first search) or BFS (breadth-first search) algorithm to search the entire network topology to generate a node-rooted tree rooted at \(L_{s}\). 2: If there exist sensors which are leaf nodes in tree, denote it as \(u\). 3: End if 4: Keep on search until finding one \(u^{\prime}\) neighbor node who is not \(u^{\prime}\) parent node, denote it as \(x\). 5: connect the node \(u\) and \(x\) to construct a ring, denote it as \(C\). 6: Traverse all the nodes in ring \(C\) until finding one sensor v whose \(L_{s}\) neighbor node w in not in ring \(C\). 7: IF node \(u\) and v are already connected, then Cut the loop directly in front or behind \(v\). 8: Else 9: Cut the ring on both sides of v, Repeat steps 4–6 until tree trimming ends. 10: End if 11: keep on Pruning trees until There is no leaf node in the tree. 12: The algorithm ends. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Pseudo-Code of Network Coding Tree Algorithm.