# An Efficient Grid-Based Geocasting Scheme for Wireless Sensor Networks
## 3 The Proposed Scheme
### Gateway Selection  
Geocasting refers to the delivery of data from a group of destinations identified by locations. The sink assigns one or more location areas as the target regions, and collects the sensing data from these target regions to the sink. However, the sensors are usually power limited. This work aims to construct the shortest path tree to achieve the energy-saving objective via Fermat points. The Fermat point is decided using the Fermat point theorem [17]. The Fermat point is characterized by the smallest sum of distances from the three vertices of the triangle. This Fermat point in any triangle can be found by the Fermat Point Finding Process, as shown in Process 1. The Gateway Selection Algorithm is shown in Algorithm 2 and the flowchart of the Gateway Selection Algorithm is shown in Figure 3.  
```
Step 1: At any edges in \(\triangle ABC\), we can construct three regular triangles: \(\triangle A^{\prime}BC\), \(\triangle AB^{\prime}C\), and \(\triangle ABC^{\prime}\). Step 2: The Fermat point is the intersection point of the three straight line segments: \(\overline{AA^{\prime}}\), \(\overline{BB^{\prime}}\), and \(\overline{CC^{\prime}}\).
```  
Figure 2: Region head election.  
We give an example to illustrate gateway selection, as shown in Figure 4. In the example, there are two target regions in the network area. After the region head is determined, the sink \(S\) calculates the Fermat point \(F\) and its GID. In this work, the cell head where the Fermat point is located is defined as gateway \(G\). The purpose of gateway \(G\) is to merge the information from \(H_{1}\) and \(H_{2}\), and forward the data to the sink.  
In general, the geocasting could be constructed alone the line segments \(\overline{H_{1}G}\), \(\overline{H_{2}G}\), and \(\overline{SG}\). In the mathematical view, the geocasting along the line segments \(\overline{H_{1}G}\), \(\overline{H_{2}G}\), and \(\overline{SG}\) is the shortest path tree. However, in the grid-based network, this topology is not the best one due to the fact that any cell head can communicate directly with neighboring cell heads. The gateway of the cell where Fermat point \(F\) is located will cause the redundant path. Thus, the location of the gateway should be adjusted. If gateway \(G\)' is closer to the Fermat point \(F\) than gateway \(G\), gateway \(G\)' is then instead gateway \(G\).  
Figure 3: Flowchart of Gateway Selection Algorithm.  
The cell candidate set is the set of cells where the gateway candidates are located. As shown in Figure 5, there are eight cells around the cell where gateway \(G\) is located, and cell candidate set \(\theta\) is <[4, 6], [5, 6], [6, 6], [4, 5], [6, 5], [4, 4], [5, 4], [6, 4]>. The cell candidate set is along the line segment \(\overline{H_{1}G}\) and the line segments \(\overline{H_{2}G}\) are \(\rho_{1}\) and \(\rho_{2}\), respectively. The available cell candidate set \(\mu\) can then be determined by Equation (1).  
\[\mu=\theta\ -\ (\rho_{1}\cup\rho_{2}) \tag{1}\]  
Figure 4: Gateway selection.  
Figure 5: Gateway adjustment.  
We suppose the available gateway candidate set is \(S_{agc}\) for the available cell candidate set \(\mu\). Gateway \(G^{\prime}\) can then be determined by Equation (2).  
\[G^{\prime}=\{\ p\ |\ p=p_{i}\ \text{with minimum}\ d(p_{i},\ s),\ \text{where}\ p_{i}\in S_{agc}\ \text{and}\ 1\leq i\leq n\ \} \tag{2}\]  
where \(\ d(p_{i},\ s)\) is the distance between the location of each available gateway candidate \(\ p_{i}\), the sink is \(s\), and the number of members in \(S_{agc}\) is \(n\).