## 3 Cluster-Disjoint Multipath Routing Protocol
### Grid Cluster Construction
For example, the cluster head of grid cluster C(1, 2) which received the packet from the cluster head of grid cluster C(0, 3) informs the cluster heads of grid clusters C(1, 1), C(0, 2), C(2, 2) and C(1, 3) that it is participating in the first path. Through this process, when the cluster head of grid cluster C(0, 3) transmits the packet exploiting other paths based on grid cluster C(0, 2) or C(1, 3), cluster head of grid clusters C(0, 2) or C(1, 3) could prevent duplicate path selection. That is, since cluster head of grid cluster C(0, 2) already knows C(1, 2) has participated in the first path, the cluster head of grid cluster C(0, 2) selects grid cluster C(1, 1) as the next cluster. Similarly, in the case of grid cluster C(1, 1), since grid cluster C(2, 1) participated in the first path, cluster head of grid cluster C(1, 1) selects grid cluster C(2, 0) as the next cluster to transmit the packet. In the same manner as in the above process, the cluster head of grid cluster C(1, 3) transmits the packet through grid clusters C(2, 3), C(3, 2) and C(3, 1). Finally, to deal with the last mile delivery, the grid cluster in which the sink is located does not indicate that it is participating in any path. Thus, the cluster head of the neighboring grid cluster C(2, 0) could forward the packet to the sink in grid cluster C(3, 0). However, if the packet can be directly transmitted without relaying through the cluster head of grid cluster C(3, 0), such as in the case of grid cluster C(3, 1), the packet is directly transmitted to the sink. The cluster-disjoint multipath constructed by the above process is exploited until the last packet is delivered. In the process of transmitting the packet, each packet can be forwarded through different nodes within the same cluster. Finally, the multipath is released in the process of transmitting the last packet. Now, we describe the process of selecting the next intermediate node to transmit the packet from the previous cluster head to the next cluster head. The process by which a cluster selects the next intermediate node depends on whether there is a sink node in the neighborhood. If there is a sink node, the packet is forwarded directly to the sink node to complete the packet transmission without selecting another intermediate node. (In Figure 3, the cluster head at C(3, 1) relays the packet to the sink node at C(3, 0)). However, when it is necessary to select the next intermediate node to relay data to the sink, a similar criterion to selecting a cluster head is applied. In other words, nodes with higher remaining energy that are closer to the sink are given priority in the selection process. The equation for calculating priority \(P\) for the cluster head considering the remaining energy \(E_{remaining}\), the total energy amount \(E_{total}\), and the distance from the intermediate node to sink node \(D\) is as follows:

\[P=E_{remaining}/E_{total}*\alpha+D*\beta\]In the above equation, \(\alpha\) and \(\beta\) are user-defined variables that could be used if the user wants to assign more weight to energy or distance. The intermediate node selected based on the equation selects the next intermediate node depending on whether there is a cluster head in the neighborhood. If there is a cluster head, the packet directly forwards to the cluster head without selecting another intermediate node to complete packet transmission (in Figure 3, the intermediate node at C(1, 2) forwards the packet to the cluster head at C(2, 2)). However, if it is necessary to select the next intermediate node to forward the packet to the next cluster, the process is repeated and the next intermediate node is selected (in Figure 3, the intermediate node at C(0, 3) selects the next intermediate node to forward the packet to the cluster head at C(1, 2)). ## 4 Performance Evaluation

In this section, we present the simulation results for FD-AOMDV, RMR, and the proposed scheme. FD-AOMDV is a scheme that constructs a node-disjoint multipath through a route discovery phase which exploits RREQ flooding and the RREP response.