## 4 New Routing Protocol for MWSNs
### Our Efficient Routing Strategy in MWSNs
#### 4.1.2 Building Routing Tree  
Here, we detailed the procedure of building the routing tree from source nodes to sink. This procedure consists of the following steps:  
_Step 1 Network initiation and neighbor discovery._ After all sensor nodes are deployed in the sensed field, all nodes can update their neighbor table using RSSI-based distant estimated scheme. _Step 2 Collect network statuses._ When a sink move in a target area, the first thing has to be completed is to find the appropriate agent by local-broadcasting 1-hop Agent Query packet (AQ). The sink selected the closest node as the agent, and then broadcasts a Data Query (DQ) packet using unicast local flooding. Each node that receives the DQ packet firstly forwards the DQ to its neighbors and then updates its neighbor table if necessary. When a source matches DQ packet, it replies a Success Response (SR) packet to the sink. Each node that receives the SR packet firstly forwards the SR to its neighbors, then broadcast Data Query Response (DQR) packet that includes its newest state information such as residual energy, delay, and neighbor table data and so on along with its ID to the sink. Once the SR packet is received by sink, the data query procedure is finished immediately or finished after a reasonable time from then. This procedure as illustrates as Figure 1a. There are two special operations in this process are noteworthy. One is that all query packets (i.e., AQ and DQ) and their reply packets (i.e., DQR) are unicast by local flooding to reduce the overall communication and energy overhead. The other one is that, when a source node receives multi DQ packets from multi sinks, it only replies to the first received DQ packet, which can assure it only sends its sense data to the nearest mobile sink to save energy. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**self\_ID** & **neighbor\_ID** & **Dis** & **isRelay** \\ \hline
7 & 3 & 20 & 1 \\
7 & 9 & 15 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Neighbor table. _Step 3 Build optimal routing tree._ In most situations, multi-source nodes send data packets to a same sink, therefore, we need to build a routing tree. Root node is the agent, and the leaf nodes mean its source nodes. An example of routing tree is shown in Figure 2a. There are two routing paths, i.e., \([Path_{1},Path_{2}]\), in the routing tree, the root node is \(Agent_{i}\) and the leaf nodes are \(Source_{1}\) and \(Source_{2}\). The routing tree contains 5 relay nodes. Once finished _Step 2_. Sink has collected a number of neighbor tables along with their remaining energy information and delay information which are wrapped in DQR packets. As illustrated in Figure 1b, the network topology of candidate relay nodes that extracted from the neighbor tables, i.e., \(G(V,E)\), can be constructed by sink. Where \(e_{i}\)\(\in\)\(E\) indicates that two adjacent sensor nodes can communicate with each other. \(G(V,E)\) is stored as adjacency matrix \(A\), \(A[i,j]\) can be calculated as follows:  
\[A\left[i,j\right]=\left\{ \begin{array}{ll}0&if\quad\quad i=j\\ \mathit{dis}\left(i,j\right)&\mathit{dis}\left(i,j\right)\leq R\\ \infty&if\quad\mathit{dis}\left(i,j\right)>R\end{array} \right. \tag{4}\]  
where \(i,j\) are two adjacent nodes, and \(\mathit{dis}(i,j)\) denote the length of \(e_{i}\)\(\in\)\(E\). Each optimal routing path from each source node towards the sink can be built by using the improved greedy forwarding mechanism from candidates based on the network topology. Notably, even though each routing path (or branch) of a sink is optimal, the routing tree of the sink may not be the optimal due to the intersection relay nodes shared by multi paths. Therefore, the optimal algorithm needs to be employed to achieve the global optimum (the optimal routing tree). We designed GMDPSO, which is detailed in Section 5, to solve the problem.