# A Biologically Inspired Self-Organizing Underwater Sensor Network
## 5 Forwarding Guide
### Convergence of the Algorithm  
In this section, we explain the convergence of the algorithm. This can be proved with the help of [PERSON]'s algorithm. We model the sensor network as a directed graph model, with nodes being vertexes, composing set \(V\). For edges, to satisfy the definition of the classic Dijkstra Algorithm, for a pair of first-order neighbors, an edge is assigned from the receiver pointing at the sender, with the weight of this edge being the expected wait of the sender. Thus, we obtain the edge set \(E\) and the weight set \(W\). Based on this definition, we write the classic Dijkstra Algorithm as Algorithm 5, where \(dist[s,t]\) indicates the total cost for node \(s\) to receive a message packet from node \(t\). Set \(S\) stores the vertexes that already find their shortest path to the source vertex \(s\), where vertex \(s\) indicates the base station that collects all messages in the sensor network. The weight \(w_{s,t}\) is the expected wait of \(t\) if \(s\) is its first-order neighbor. If \(t=s\), \(w_{s,t}=0\). If \(t\
eq s\) and \(s\) is not a first-order neighbor of \(t\), then \(w_{s,t}=\infty\).  
```
0: Directed graph \(G=(V,E,W)\) with weight
0: All the shortest paths from source vertex \(s\) to every other vertex
1:\(S\gets s\)
2:\(dist[s,s]\gets 0\)
3:for\(v_{i}\in V-s\)do
4:\(dist[s,v_{i}]\gets w(s,v_{i})\) (when \(v_{i}\) not found, \(dist[s,v_{i}]\leftarrow\infty\))
5:endfor
6:while\(V-S\
eq\phi\)do
7: find \(min_{v_{j}\in V}dist[s,v_{i}]\) from the set \(V-S\)
8:\(S\gets S\cup v_{j}\)
9:for\(v_{i}\in V-S\)do
10:if\(dist[s,v_{j}]+w_{j,i}<dist[s,v_{i}]\)then
11:\(dist[s,v_{i}]\gets dist[s,v_{j}]+w_{j,i}\)
12:endif
13:endfor
14:endwhile
```  
**Algorithm 5** Dijkstra Algorithm  
Following the definitions above, we abstract the part of searching for the forwarding path in Algorithm 4 as Algorithm 6.  
```
1:while True do
2:for\(v\in V\)do
3:for\(v_{j}\in S_{1\text{-}neighbor}(v)\)do
4:if\(dist[s,v_{j}]+w_{j,i}<dist[s,v_{i}]\)then
5:\(dist[s,v_{i}]\gets dist[s,v_{j}]+w_{j,i}\)
6:endif
7:endfor
8:endwhile
```  
**Algorithm 6** Abstraction of Algorithm 4  
By comparing Algorithm 5 with Algorithm 7, we can see that both algorithms set the same initial conditions. Lines 5-7 in the Dijkstra Algorithm are used to set a termination condition, while Algorithm 7 does not. However, as the sensor network keeps working, it can be treated that the algorithm will loop forever, exceeding the time needed for convergence, and thus a termination condition is unnecessary. Then, in Algorithm 7, \(dist[s,v_{i}]\)will not change when \(v_{i}\
otin V-\text{Sb}\) because the node cannot find a shorter path; the same thing happens in the Dijkstra Algorithm. In the Dijkstra Algorithm, we update \(dist[s,v_{i}]\) with \(v_{j}\), which is currently not in \(S\) while having the shortest path to \(s\), as in Lines 9-13. Even though \(dist[s,v_{i}]\) may change in Lines 5-10, it will finally be updated in Lines 11-15, following the same operation in the Dijkstra Algorithm. Thus, the two algorithms are equivalent at this stage, except that for [PERSON]'s Algorithm, nodes need to know the whole graph, while our algorithm can work only based on local information. As a result, with the forwarding guide, the sensor network can finally converge to the state where message packets can be relayed to the base station with the shortest expected wait.  
```
1:while True do
2:for\(v_{i}\in V\)do
3:if\(v_{i}\in V-S\)then
4:for\(v_{j}\in S_{1\text{-neighbor}}(v)\)do
5:if\(v_{j}\in S\)then
6: Nothing will happen
7:endif
8:if\(v_{j}\in V-S\wedge dist[s,v_{j}]\
eq min_{v_{i}\in V-S}dist[s,v_{i}]\)then
9:\(dist[s,v_{i}]\) may be updated, but cannot ensure reaching the minimum value
10:endif
11:if\(v_{j}\in V-S\wedge dist[s,v_{j}]=min_{v_{j}\in V-S}dist[s,v_{i}]\)then
12:if\(dist[s,v_{j}]+w_{j,i}<dist[s,v_{i}]\)then
13:\(dist[s,v_{i}]\gets dist[s,v_{j}]+w_{j,i}\)
14:endif
15:endif
16:endfor
17:else
18: Nothing will happen
19:endif
20:endfor
21:endwhile
```  
**Algorithm 7** Another form of Algorithm 6