## 2 Coding Opportunity over a Wireless Network
### Coding Opportunity Analysis  
Suppose that two packets \(M_{1}\) and \(M_{2}\) are received by relay node \(r\), and the predecessor and successor nodes of \(M_{1}\) and \(M_{2}\) are (\(S_{1},D_{1}\)) and (\(S_{2},D_{2}\)), respectively. Packets \(M_{1}\) and \(M_{2}\) can be encoded in node \(r\) if one of the following four situations happens:  
Case (1) \(S_{1}=D_{2}\), \(S_{2}=D_{1}\)  
Case (2) \(S_{2}=D_{1}\
eq S_{1}\
eq D_{2}\), \(0<d(D_{2},S_{1})\leq R\)  
Case (3) \(S_{1}=D_{2}\
eq S_{2}\
eq D_{1}\), \(0<d(D_{1},S_{2})\leq R\)  
Case (4) \(D_{1}\
eq D_{2}\
eq S_{1}\
eq S_{2}\), \(0<d(D_{2},S_{1})\leq R\), \(0<d(D_{1},S_{2})\leq R\)  
Four possibility probabilities mentioned above are denoted by \(P_{\textit{cascel}}\), \(P_{\textit{cave2}}\), \(P_{\textit{cave3}}\) and \(P_{\textit{cave4}}\),respectively. We denoted \(P_{\textit{coding}}(N)\) as the probability that packets \(M_{1}\)and \(M_{2}\) can be encoded in node \(r\) with \(N\) neighbors. We also denote \(p,(N,L)\) as the probability that there exists a coding opportunity at node \(r\) with \(N\) neighbors and \(L\) packets buffered in its coding queue. (1) Calculation of \(P_{\textit{cascel}}\)  
As shown in Figure 3a, two selected nodes \(S_{1}\) and \(D_{1}\) are in the communication range of the given coding node \(r\). In such case, the neighboring node pairs (\(S_{1},D_{1}\)) among the \(N\) neighbors of node \(r\) may appear \(N(N-1)\)times. The expression for \(P_{\textit{cascel}}\) is  
\[P_{\textit{cascel}}=\frac{1}{N(N-1)} \tag{1}\]  
(2) Calculation of \(P_{\textit{cave2}}\)  
Figure 3b illustrates the second case, where the selected node \(D_{2}\) is in the communication range of the selected node \(S_{1}\) and the given coding node \(r\). Note that the nodes \(S_{1}\) and \(D_{2}\) are the neighbors of node \(r\). Next, we explore the location relationship of nodes \(S_{1}\), \(D_{2}\)and \(r\). Figure 4 illustrates a location model that node \(D_{2}\) is located within the communication range of \(S_{1}\) and \(r\). As shown in Figure 4, the selected node \(D_{2}\) is located at the intersecting communication range of the selected node \(S_{1}\) and the given coding node \(r\). We also denote this probability as \(P_{h}\). From Figure 4, it is observed that \(P_{h}\) is the probability that \(D_{2}\) is located within the overlapping area between the ice-blue and the olive circles. In this figure, the distance between \(S_{1}\)and \(r\)is \(d(d\leq R)\). A and B are the two distinct intersecting points of the two circles with \(d(S_{1},r)<R\). Denote \(\Pi_{2}\) as the expected area of the region jointly covered by node \(S_{1}\) and node \(r\). To calculate \(P_{h}\), we first calculate the area of \(\Pi_{2}\). As shown in Figure 4, in the ice-blue circle being centered at \(S_{1}\), the area of \(\Pi_{2}\)/2 equals to the area of sector \(S_{1}AB\) minus the area of triangle \(S_{1}AB\). Thus, we have  
\[ \begin{split}&\Pi_{2}=2\{\frac{1}{2}\times R^{2}\times 2\arccos( \frac{d}{2R})-\frac{1}{2}\times\frac{d}{2}\times 2\sqrt{R^{2}-\frac{d^{2}}{4}} \}\\ &=2R^{2}\arccos(\frac{d}{2R})-\frac{d}{2}\sqrt{4R^{2}-d^{2}}\end{split}  \tag{2}\]  
Since the nodes are uniformly distributed, \(\Pr(d\leq x)\) equals to the area of the circle having radius \(x\) and being centered at \(S_{1}\) over the area having radius \(R\) and being centered at \(S_{1}\)[19]. Thus, we have  
\[F_{1}(x)=\Pr(d\leq x)=\frac{\pi x^{2}}{\pi R^{2}}=\frac{x^{2}}{R^{2}} \tag{3}\]  
Figure 4: The location relationship between \(S_{1}\) and \(r\). Figure 3: **(a)** Illustration of situation in Case One; **(b)** Illustration of situation in Case Two; **(c)** Illustration of situation in Case Three; **(d)** Illustration of situation in Case Four.