# Energy-Efficient Spatial Query-Centric Geographic Routing Protocol in Wireless Sensor Networks
## 3 QTGrid Routing Protocol
### CH and PCH Election
#### 3.2.2 PCH Election  
An effective network topology control structure can improve the efficiency of network communication protocols while extending the network lifetime [47]. After quadtree hierarchical partitioning of the network, QTGrid adds management nodes at the corresponding quadtree level. In addition to the sink node, each cluster level sets a PCH as the management node responsible for collecting information on the four lower sub-CHs (SCH), aggregating the collected data, and transmitting them to the PCH. To reduce computing expenses of the PCH selection algorithm, QTGrid selects the SCH closest to the sink node as its PCH. The Algorithm 1 is the pseudo-code of PCH election. In this algorithm, a CH can calculate the M code of the cluster, where its PCH is located only based on its own identification code. Therefore, no extra communication consultation is required. ```
\(m\leftarrow\) the M code of the CH Level \(i\leftarrow\) the level of the PCH \(d\leftarrow\) the depth of the quadtree \(sink\leftarrow\) the location of Sink node Get PCH (\(m\), level \(i\), \(d\), sink) \(l\) begin [CHs] = [NW, NE, SW, SE]/ Get the 4 CHs of the \(i\)-th level whose M code are \(m\) [Xc,Yc] = (M,i)/ Get the center coordinate of the area where the M code is \(m\) [Xs,Ys] = sink/Get the coordinates of the sink node  If(Xs>Xc)\(\in\)/(Ys>Yc)  PCH =SE Else if(Xs<Xc)\(\in\)/(Ys>Yc)  PCH = SW Else if(Xs<Xc)\(\in\)/(Ys>Yc)

### Routing Strategy

The topology structure of the network is shown in Figure 4, where Z is the depth of the quadtree. Hence, QTGrid is a multilevel clustering network structure, in which the data routing process adopts the transmitting-while-aggregating method (details in Section 3.4). QTGrid was performed in a grid-by-grid manner by using level-Z CHs to transmit data packets. The sensor nodes collect and forward the data to the level-Z PCHs. The level-Z PCHs fused the data and forward them to the upper level-(Z-1) PCH. In this manner, sensing data were collected and sent to the PCHs of the next level then aggregated and forwarded to the higher-level PCH until they were received by the sink node. Therefore, next-hop node selection for data forwarding is a key issue in the routing strategy. To solve the premature death of management nodes (CHs) and the energy hole problem, QTGrid defines \(NHop\) to select the next-hop routing node. As shown in Figure 5, we assume that D \((x_{1},y_{1})\) is a level-2 PCH, A, B, and C are the SCH of D, J \((x_{0},y_{0})\) is the level-3 PCH, and E \((x_{2},y_{2})\), H \((x_{3},y_{3})\) and I \((x_{4},y_{4})\) are D's adjacent level-2 PCHs. Assuming that D needs to send data to its PCH J, eight adjacent peer CHs were available in each grid for selection. To ensure a relatively short path, we selected three CHs whose grid centers were close to the Sink node as candidate next-hop routing nodes. \(l_{i}\) (where \(1\leq i\leq 3\)) is the distance from D to its i-th adjacent peer CH, \(s_{i}\) is the distance from the i-th adjacent peer CH to J, and \(L_{i}\) is the distance from D to J via the i-th adjacent CH. Then, we obtained

\[L_{i}=l_{i}+s_{i} \tag{3}\]

where \(l_{i}=\sqrt{\left(x_{i}-x_{1}\right)^{2}+\left(y_{i}-y_{1}\right)^{2}}\), \(s_{i}=\sqrt{\left(x_{0}-x_{i}\right)^{2}+\left(y_{0}-y_{i}\right)^{2}}\). Therefore, \(L_{i}\) can be rewritten as

Figure 4: Topology structure of the network.