## 3 Cluster-Disjoint Multipath Routing Protocol
### Grid Cluster Construction  
In this section, we explain the grid cluster construction scheme in the network initialization phase consisting of the following two phases:  
* The first phase is detection of the boundary of the network where the sensors are scattered. * The second phase is division of the detected boundary into appropriate grid clusters. The sensors in WSNs usually appear in a scattered form [1]. Therefore, although the network does not represent the regular form, it is possible to specify the area of the network through various network boundary detection schemes [15]. However, we focus on grid cluster-based multipath routing, and we assume that the entire network  
Figure 1: An Overview of Cluster-disjoint Multipath Routing. is modeled as a rectangular shape through the network boundary detection process in network initialization. Figure 2 shows the sink node finding out the network boundaries and calculating a rectangle containing all the sensors. To calculate a rectangle, the following coordinate information is finally stored in the packet relayed during the boundary detection process: (1) the coordinates of the sensor with minimum/maximum x-coordinates and (2) the coordinates of the sensor with minimum/maximum y-coordinates. In Figure 2, sensor (\(x_{1}\), \(y_{1}\)) has maximum x-coordinates, sensor (\(x_{2}\), \(y_{2}\)) has coordinates with minimum x, y-coordinates, and sensor (\(x_{3}\), \(y_{3}\)) has coordinates with maximum y-coordinates. Algorithm 1 shows the pseudo-code for calculating a rectangle including the whole network. This algorithm is performed in two phases. ```
1: Start network boundary detection process exploiting detection packet
2: Packet contains coordinate information to calculate rectangle
3:
4:if the packet arrives at node then
5:if\(x_{min}>x_{node}\)then\(x_{min}=x_{node}\)
6:endif
7:if\(x_{max}<x_{node}\)then\(x_{max}=x_{node}\)
8:endif
9:if\(y_{min}>y_{node}\)then\(y_{min}=y_{node}\)
10:endif
11:if\(y_{max}<y_{node}\)then\(y_{max}=y_{node}\)
12:endif
13:endif\(\triangleright\) Detecting the boundary and updating the coordinates
14:
15:if the packet returned to sink then
16:\(w=x_{max}-x_{min}\)
17:\(h=y_{max}-y_{min}\)
18:endif\(\triangleright\) The vertex coordinates are \((x_{max},y_{max})\), \((x_{max},y_{min})\), \((x_{min},y_{max})\) and \((x_{min},y_{min})\), respectively. Figure 2: The Extreme Node Detection based on the Boundary Detection Scheme [15]. Phase 1 (lines 4-13): The coordinate information is stored in a packet sent by the sink for boundary detection. When a packet reaches each node while traversing the boundary, maximum/minimum coordinate information is compared and updated. Phase 2 (lines 15-18): When the packet exploited in Phase 1 returns to the sink, the sink could obtain coordinate information of nodes located at the extreme of the network from the packet. Thus, the vertex of the square could be specified exploiting the maximum/minimum x, y coordinates, and the width and height of the square could be calculated. After the rectangle is calculated, the sink node divides the rectangle into the grid cluster. In this case, the size of the grid cluster depends on the requirements of users and applications. However, it should be wider than the communication range of the sensors to prevent collisions and interference between packet transmission through the grid cluster. The minimum cluster size \(L\) is calculated through the transmission range of sensor \(R\) as follows:

\[L=\frac{R}{2\sqrt{2}}\]

After the grid cluster is divided, a cluster head which can represent the grid cluster is elected. The cluster head is responsible for collecting data from its grid cluster and relaying the packet to the sink through the neighboring grid cluster. The criteria for selecting the cluster head are as follows: (1) node location, (2) remaining energy capacity. First, the cluster head is responsible for relaying the packet from the grid cluster, the node should have the largest amount of energy.