## 4 The Proposed Routing Protocol: HPA-SR
### The Proposed Hybrid-Price Auction-Based Secure Routing Protocol: HPA-SR  
In this subsection, we explain in detail the proposed hybrid-price auction-based secure routing protocol, named HPA-SR protocol. As can be observed in Figure 4, the source node S begins to establish a routing route to the destination node D.  
The event of route establishment happens (on demand-reactive). We propose a HPA-SR protocol that contains the first price auction (FPA) and second price auction (SPA) in which each node employs the Markov decision process (MDP) to select which kind of auction method is used to establish the secure route by avoiding the sinkhole attack, as explained in Section 4.4. Figure 5 illustrates the flowchart of the proposed routing procedure, which can be summarized as follows:  
**Route Request Process:**  
* **Step 1: Initialization** The source node S starts to establish a routing route between the source node S and the destination node D. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Packet Name** & **Full Name** & **Field Information** \\ \hline INFO & Information Packet & Type, \(\texttt{SID},\texttt{DID},\texttt{S},\texttt{Dir}\) \\ CHI & Cluster Head Info Packet & Type, \(\texttt{SID},\texttt{DID},\texttt{S},\texttt{Loc},\texttt{Dir}\) \\ JC & Joint-Cluster Packet & Type, \(\texttt{SID},\texttt{DID},\texttt{S},\texttt{Loc},\texttt{Dir},\texttt{Status}\) \\ AC & Accept-Cluster Packet & Type, \(\texttt{SID},\texttt{DID},\texttt{Status}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: List of Packets for The ASCS clustering protocol. Figure 4: The proposed routing protocol: HPA-SR.  
* **Step 2: Source Node Operation for Route Request: Generates and Sends RREQ Packet** If the source node S does not have the routing information to the destination node D, the source node S generates a RREQ packet and sends RREQ packet to the cluster head CH\({}_{k}\) in its cluster. The RREQ packet contains the following fields: \[\langle\text{Type},\text{S}_{\text{ID}},\text{D}_{\text{ID}},\text{S}_{\text{Seq }},\text{D}_{\text{Seq}},\text{RREQ}_{\text{ID}},\text{hop}\rangle\] where Type represents packet type, S\({}_{\text{Seq}}\) is the source sequence, and D\({}_{\text{Seq}}\) is the destination sequence, which is the number of attempts to confirm control messages, RREQ\({}_{\text{ID}}\) is the number of generating RREQ packet on the same session at the source, and hop is denoted as the number of hop to the destination, respectively. * **Step 3: Intermediate Node Operation at Cluster Head for Route Request** When CH\({}_{k}\) receives the RREQ packet, CH\({}_{k}\) records sender's ID and updates the routing table, then CH\({}_{k}\) broadcasts RREQ to the gateway node (GW\({}_{k}\)) in its cluster or the next cluster heads and goes to **step 4**. * **Step 4: Intermediate Node Operation at Gateway for Route Request** When the gateway node GW\({}_{k}\) receives RREQ packet from CH\({}_{k}\), GW\({}_{k}\) records sender's ID and updates the routing table, then GW\({}_{k}\) broadcasts RREQ to their neighbors node NB\({}_{k}\) and goes to **step 5**. Otherwise, RREQ packet will be dropped. **Route Reply Process:**
* **Step 5: Destination Node Operation for Route Reply: Generates and Sends RREP Packet** When NB\({}_{k}\) is the destination node D, the destination node D records sender's ID and updates the routing table, then generates a RREP packet. The destination node D unicasts the RREP packet to the previous node. The RREP packet contains the following fields: \[\langle\text{Type},\text{S}_{\text{ID}},\text{D}_{\text{ID}},\text{Energy}, \text{D}_{\text{Seq}},\text{hop}\rangle\] where Energy represents remaining energy of the node. Then, go to **step 6**
* **Step 6: Intermediate Node Operation at Previous Node (to the source node) for Route Reply** When the intermediate node NB\({}_{j}\) receives RREP packet, NB\({}_{j}\) records sender's ID of RREP packet and updates the routing table. Then, go to **step 7**. Otherwise, NB\({}_{j}\) waits until it receives RREP packet.