# A Biologically Inspired Self-Organizing Underwater Sensor Network
## 4 Ecological Niche-Inspired Slot Distributor
### Collision Resolver  
The collision resolver is shown in Algorithm 3. It can update communication table \(L_{f}\) according to the received message. The message packet received contains a set of slots the sender asks its neighbors to abandon as \(S_{abandon}^{sender}\). The algorithm also provides \(S^{abandon}\), which contains a set of slots that the current node asks its neighbors to abandon. ```
0: Communication table \(L_{f}\), Communication packet received, contains \(S_{abandon}^{sender}\)
0: Update communication \(L_{f}\) and generate \(S_{abandon}\) that needs to be packed in the message packet to send. 1:\(L_{abandon}\leftarrow[0,0,\ldots,0],L_{recorded}\leftarrow[0,0,\ldots,0]\)
2:while New slot with address=\(id_{slot}\)do
3:if\(L_{f}(id_{slot})=1\)then
4:\(S_{abandon}\leftarrow\{i|L_{abandon}(i)=1,\forall i=1,2,\ldots,N\}\)
5:\(L_{record}(i)\leftarrow ids_{slot},\forall L_{abandon}(i)=1\)
6:\(L_{abandon}\leftarrow[0,0,\ldots,0]\)
7:endif
8:if collided with first-order neighbor then
9:if\(id_{slot}\
eq id_{self}\)then
10:\(L_{f}(id_{slot})\gets 0\)
11:endif
12:endif
13:if receive multiple signals while self not speaking then
14:if\(L_{record}(id_{slot})\
eq 0\)then
15:\(id_{temp}\gets L_{record}(id_{slot})\)
16:if\(id_{temp}\
eq id_{self}\)then
17:\(L_{f}(id_{temp})\gets 0\)
18:endif
19:else
20:\(L_{abandon}(id_{slot})\gets 1\)
21:endif
22:endif
23:if successfully receives one message packet and \(S_{abandon}^{sender}\
eq\phi\)then
24:\(L_{f}(i)\gets 0,i\in S_{abandon}^{sender}-\{id_{self}\}\)
25:endif
26:\(L_{record}(id_{slot})\gets 0\)
27:endwhile
```  
**Algorithm 3** Collision resolver  
Each node maintains two lists: \(L_{abandon}\) and \(L_{record}\). Let \(L_{abandon}(i)\) be the \(i^{th}\) element of \(L_{abandon}\). Then \(L_{abandon}(i)=1\) indicates the current node should ask its first-order neighbors to abandon slot \(i\). Let \(L_{record}(i)\) be the \(i^{th}\) element of \(L_{record}\). Then \(L_{record}(i)=k(k\
eq 0)\) indicates a current node has broadcast a message at slot k to ask its neighbors to abandon slot \(i\). In the algorithm, Lines 3-7 describe the behavior of a node at the slot it occupies. It sends a message packet containing \(S_{abandon}\) asking its neighbors to abandon slots in \(L_{abandon}\) and record to which slot the requirement is sent in \(L_{record}\). Lines 8-26 describe the behavior based on the message received. If the current node collides with any of its first-order neighbors, it will abandon the current slot unless the slot is its identical slot, as in Lines 8-12. In Lines 13-22, if multiple first-order neighbors speak at the same time, the current node checks if it has asked neighbors to abandon this slot before according to \(L_{record}\). If so, the current node abandons the current slot unless it is its identical slot. Otherwise, the current node records this slot in \(L_{abandon}\). In the case that the current node successfully receives a message packet, the node abandons slots in \(S_{abandon}^{under}\) in the message packet except for its identical slot, as in Lines 23-25. Finally, \(L_{record}\) is updated in Line 26. With the collision resolver, the network can converge to the state where:  
* No collision exists in the network. * Each node occupies at least one slot in a frame. This is because with Algorithm 3, if a collision occurs between a pair of first-order neighbors and if the slot is not the identical slot of either of the nodes, both nodes abandon the slot. If the slot is the identical slot of a node, then the node keeps this slot and the other node abandons the slot. When a collision occurs among second-order neighbors, the nodes cannot realize this collision, but their common first-order neighbor will receive multiple signals and realize the existence of the collision. Then, the node will ask all its neighbors to abandon this slot. On receiving this message, nodes will abandon this slot, except for the identical node. Generally, collisions can be eliminated with the operation above.