## 2 Routing Protocol Design
### TSR Design  
Nodes in UWSNs have to send route packets to establish a route tree. The first step is to check the format of the route packet. Nodes do not have to reply to their parent node, instead of broadcasting the route packet directly. The route packet also can be seen as the affirmance of the parent node, as well as taking route messages of all nodes to the sink. Therefore, we divide packets into broadcast-route packets and feedback-route packets during the process of route establishment. Broadcast-route packets are mainly used to find the next hop directly and can be sent to a parent node as ACK. They contain five fields in the format shown in Figure 2.  
Feedback-route packets are mainly used by lower layers to report to the parent node the construction of a route and be sent to a sink. A sink stores route packets in its buffer to check each state of each node. Feedback-route packets contain seven numeric fields, in the format shown in Figure 3.  
The meanings of the route format fields are shown as the following:  
Type: type of packet, 0 denotes broadcast packets, 1 denotes feedback packets  
Source: ID of node which sends a packet  
Birthtree: ID of node which creates a packet, and starts to send it back to a sink  
BTParent: ID of Birthtree's father node  
Dest: Packet destination  
Level: layer the node which creates a packet belongs to  
CRC: circulating redundancy check message  
Figure 3: Format of feedback-route packets. Figure 2: Format of a broadcast-route packet. The basic TSR establishment method is: sink sends the broadcast packet during the first period in its own time slot. Each node which received the broadcast packet sends back a feedback packet in a particular period in a given time slot. If the sink received the feedback from nodes, the sink will register these nodes, which are the child-nodes of the sink, as first layer child-nodes. When a node first receives a packet which is not come from the sink, it would determine the current time slot and whether it had missed its own time slot. If not, it will broadcast the packet in its own time slot and if yes, it would wait for another own time slot. If node \(x\) received a packet from other node \(y\), it registers \(y\) as its sub-layer. Then, it sends the packet to parent-node \(z\). Node \(z\) also sends a packet to its parent-node \(a\), until the parent-node is the sink. This process will continue until all nodes are registered. The interior communication process through a route tree would decrease conflict probability efficiently and decrease the establishment time of a route tree. The process of establishing a route tree is shown in Figure 4.  
To explain this more clearly, we divide the process of establishing a route tree into a sink route establishment process and a normal route tree establishment process. In the route establishment process a sink sends a broadcast route packet, and then just waits for packets whose destination is the sink. The other underwater nodes have to determine the received packet's type when they first receive it. Figure 4: **(a)** Sink sends broadcast-route packet. **(b)** First layer nodes send broadcast-route packets. **(c)** The second layer nodes send broadcast-route packets. **(d)** Established route tree. The TSR design process can be listed as follows:  
(1) Sink send packet \(<\)_0, 0, \(-\)1, 0, CRC\(>\)_ during the first period in a given time slot \(a_{I}T\). (2) Any node \(x\), whose time slot is denoted by \(a_{2}\), broadcasts its own packet \(<\)0, x, 0, 1, CRC\(>\) in a particular time slot if it receives a packet from a sink. (3) Any node y (time slot is \(a_{4}\)), in the case it did not receive a packet from a sink, but from another node \(z\) for the first time (packet is \(<\)0, \(z\), \(z_{Patent}\), \(n\), CRC\(>\)), and if \(y>z\), \(y\) will broadcast packet \(<\)0, \(y\), \(z\), \(n\)+1, CRC\(>\) in its own time slot in the next period.