# 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
\[L_{i}=\sum_{j=0}^{1}\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}} \tag{4}\]

By comprehensively considering the distance and residual energy when selecting the next-hop routing node, QTGrid defines _NHop_ as an evaluation factor for the candidate CHs, and the i-th candidate CH's _NHop\({}_{i}\)_ can be obtained by

\[\textit{NHop}_{i}=\lambda\frac{L_{i}}{L_{\max}}+\mu(1-p_{i}) \tag{5}\]

where \(\lambda\) and \(\mu\) are balance coefficients (where \(\lambda+\mu=1\), \(\lambda>0\) and \(\mu>0\)); \(L_{max}\) is the maximum among \(L_{2}\), \(L_{3}\), and \(L_{4}\); \(p_{i}=E_{\textit{current}\,i}/E_{\textit{initial}\,i}\) (\(E_{\textit{current}\,i}\) and \(E_{\textit{initial}\,i}\) are the residual and initial energy of the CH, respectively). In reference to Figure 5, the routing strategy steps were as follows:

1. The sink node sent the data collection request to the event area, and the nodes in the routing area added their own energy information to the data package. 2. After receiving the package, the sensor nodes in the event area sent the data to the CH. Then, CHs A, B, and C sent the data to PCH D.
3. D aggregated the data and calculated the _NHop_ values of the candidate next-hop routing nodes (E, H, I) using Equation (5). 4. [PERSON] sent the data to the node with the smallest _NHop\({}_{i}\)_ value. Here, we assumed that the _NHop_ value of E was the smallest. Then, E continued to aggregate and forward the data to its next-hop routing node with the smallest _NHop_ value until [PERSON] received the data and forwarded them to the sink. Finally, data routing was completed. In this demo, the routing path was \(\mathrm{D}\rightarrow\mathrm{E}\rightarrow\mathrm{F}\rightarrow\mathrm{J} \rightarrow\mathrm{sink}\). ### Data Aggregation

Data aggregation is an important mechanism for achieving energy efficiency in WSNs. Many data aggregation protocols have been developed based on various techniques of optimizing delay and energy [48]. QTGrid employs a simple and efficient lossless data aggregation method to ensure data integrity. During the QTGrid routing protocol, CHs at each level was regarded as an intermediate node in data aggregation. Sensing data were forwarded by strictly following the hierarchical structure of the quadtree, and data aggregation was performed simultaneously with forwarding. According to the routing hierarchy of the network, the CHs collected the sensing data of their SCHs and ranked them in ascending order according to the M codes. When the attribute values of adjacent M codes were equal,

Figure 5: Routing strategies of QTGrid. they were merged, and only the tuple with the smallest M code value was reserved. Figure 6 depicts a three-level WSN. Each level-3 CH sent the data to the level-2 PCH, and the level-2 PCH aggregated the data and sendt them to the level-1 PCH. The level-1 PCH aggregated the data and forwarded them to the sink node. Therefore, the data received by the sink node were the source data of the smaller space sent by the aggregated level-3 CHs. The literature [43] used a similar lossless aggregation method to collect the details of network sensing data and reduce the communication cost considerably. ### Spatial Query

The spatial query of QTGrid has two main processes: sending a spatial query request and sensor data feedback. Window queries are the most common type of spatial queries [7]. In QTGrid, the spatial query request was sent to the defined region of interest (called window) and asked for data collected by the sensor nodes inside this region. On the basis of the advantage of the multi-level clustering network structure, the spatial query was transmitted through multi-level CHs. The grid level of the queried area can be customized by the user, which makes the spatial query flexible and suitable for practical application needs. Combining Figure 7, the two algorithms are given below. The Algorithm 2 is the pseudo-code of spatial query request sent, and the Algorithm 3 is the pseudo-code of sensor data feedback.