## 7 Approximation Algorithm  
It is a NP-hard problem [21] to compute the minimum transmission count in the case of various link quality. Given a graph \(G(V,E)\), an _independent set_ of \(G\) is a set of vertices where there is no edge between any two vertices. The maximum independent set problem is a known NP-hard problem. To solve the minimum transmission count can be converted to a maximum independent set problem. So to solve the minimum transmission count is also NP-hard. The main proof process is as follows: In a graph \(G(V,E)\), we specify two nodes as the source and destination nodes. Each edge is a corresponding link between two related nodes. The link capacity between any two nodes is assumed to be one unit. It is assumed that there are conflicts between the links. Therefore, the minimum transmission count can be obtained only after the sequence of the maximum independent set of the graph \(G\) is arranged. That is to say, to solve the minimum transmission count of a network is equivalent to solve the maximum independent set of the graph established on the network. The latter is a known NP-hard problem. So the former is also a NP-hard problem. Therefore, we use a local search heuristic to adjust routing paths in partial section to minimize the transmission count. As discussed in Section 3, in order to get a network coding opportunity, we need to modify the local path(s) near a cross node where two data streams' paths intersect. In addition, the \"Alice-Bob structure\" or \"X structure\" coding opportunity can be found at least in a two-hop communication range. Thus we choose a cross node as a center and take its one-hop communication range as the neighborhood range to carry out the local search heuristic. The neighbor search algorithm includes two primary steps as follows: (1) to determine the initial path of each data stream: The algorithm takes the transmission success rate of each link as the weight, and generates a new path for each data stream by finding the path on which the sum of weights of the links is maximum (the ETX is minimum); (2) to optimize the initial paths: The algorithm adjusts (or creates) a cross node for the initial paths so that the sum of the ETXs of all the paths passing through the cross node decreases and the total number of transmission in the network is as small as possible. The specific implementation process is shown in Table 1, where a cross node refers to the node through which there are at least two paths of data streams; a pseudo cross node is such a node that belongs to only one path and whose neighbor nodes belong to another path, or that can be added to another path as a transit node. To illustrate the algorithm clearly, some symbols are defined as follow:  
\(v\): a current node. \(Int\): an initial local path strategy. \(St\): a local path strategy of node \(v\) with network coding. \(E(St)\): the sum of the ETXs of a local path strategy \(St\). \(L(v)\): a collection of local path strategies of node \(v\). \(a\): a neighbor node of the current node \(v\). \(l(v)\): a local path strategy \(St\) that makes \(E(St)\) minimum in \(L(v)\). \(p_{i}\): the predecessor node of the current node \(v\) in the path of a data stream \(i\). \(n_{i}\): the successor node of the current node \(v\) in the path of a data stream \(i\). \(\alpha_{i,j}\): the ETX of a link between the nodes \(i\) and \(j\). Three main cases dealt with by the algorithm are shown in Figure 4. Suppose that the current node is \(v\). Figure 4a indicates the case that the quality of the current node \(v\)'s input link (e.g., \(p_{2}\),\(v\)) is poor. In the figure, there are two paths \(s_{1},...,p_{1},v,n_{1},...,d_{1}\) and \(s_{2},...,p_{2},v,n_{2},...,d_{2}\), which respectively belong to two data streams passing through the cross node \(v\), and the transmission success rates of the related links are marked.