## 4 The GPNC Routing Algorithm  
The proposed GPNC routing algorithm uses the geographic information on nodes for routing and partial network coding for data transmission. To forward a packet, it attempts to select a forwarding node that is nearest the destination node by considering the packet advancement. When a forwarding  
Figure 5: An intermediate node performing partial network coding.  
node needs to transmit data, it encodes the packet using partial network coding, and with the distance decreasing to the sink node, the encoded packet can finally arrive at the sink node. When the sink node has received N linear independently encoded data packets, it performs decoding to retrieve the packets.  
The GPNC algorithm uses a greedy forwarding strategy to determine the set of next-hop forwarding nodes. Let \(n_{i}\) be a source node that has a data packet to deliver, \(N(t)\) be \(n_{i}\)'s set of neighboring nodes at time \(t\), and \(S(t)\) be \(m\)'s known set of sink nodes at time \(t\). Considering a neighboring node \(n_{i}\in N_{i}(t)\), its packet advancement is defined as [4]:  
\[ADV(n_{j})=D(n_{i},s_{i})-D(n_{j},s_{j}) \tag{5}\]  
where \(D(n_{i},s_{i})\) is node \(n_{i}\)'s Euclidean distance to its closest sink node \(s_{i}\in S_{i}(t)\) at time \(t\) and \(D(n_{j},s_{j})\) is node \(n_{i}\)'s Euclidean distance to its closest sink node \(s_{i}\in S_{i}(t)\) at time \(t\).  
Generally speaking, the greater the packet advancement is, the higher priority the neighboring node is given. Then \(n_{i}\)'s set of next-hop forwarding nodes at time \(t\) is:  
\[C_{i}(t)=\{n_{j}\in N_{i}(t),ADV(n_{j}\textgreater 0)\} \tag{6}\]  
For a candidate forwarding node \(n_{c}\in C_{i}\), \(D(n_{i},n_{c})\) is the Euclidean distance between the source node \(n_{i}\) and the forwarding node \(n_{c}\). Assume the packet delivery probability of \(m\) bits over distance \(D(n_{i},n_{c})\) is \(p(D(n_{i},n_{c}),m)\) as given by Equation (4). The candidate forwarding node \(n_{c}\)'s normalized packet advancement is defined as:  
\[NADV(n_{c})=ADV(n_{c})\times p(D(n_{i},n_{c}),m) \tag{7}\]  
Based on a node's energy and NADV, we define the following weighting formula for ordering candidate forwarding nodes:  
\[W=\partial\frac{E_{r}}{E_{o}}+(1-\partial)NADV \tag{8}\]  
where \(\partial\) is an equivalence factor between a response node's energy and NADV, \(E_{o}\) and \(E_{r}\) are the initial and residual energy of the response node respectively.  
We use Equation (8) to calculate the weight of each candidate forwarding node in \(C_{i}(t)\) and create a sorted list \(F_{i}(t)\) from \(C_{i}(t)\) ordered by their weight from high to low. The first node in \(F_{i}(t)\) will be chosen as the next-hop forwarding node to transmit a data packet and only it fails to do so, the next one in \(F_{i}(t)\) would be chosen. The process continues in that order until the data has been successfully delivered. The \(h\)-\(th\) node in \(F_{i}(t)\) will start to transmit data if none of the preceding nodes has successfully done that within time \(T_{w}^{h}\) defined below:  
\[T_{w}^{h}=T_{d}+\sum_{j=1}^{h}D(n_{j},n_{j+1})/v+h\times T_{p} \tag{9}\]  
where \(v\) is the speed of sound under water, \(T_{p}\) is the packet processing time, and \(T_{d}=(R_{c}-D(n_{i},n_{c}))/v\) is the propagation delay.  
After the optimal next-hop node has been selected, the source node forwards the data packet to the selected forwarding node, which then encodes the packet and becomes the source node. The routing process continues as such until the data packet has been delivered to the sink node. When the sink node has received all the required linear independently encoded data, it starts decoding to retrieve the original data packets.