# An Unequal Clustering and Multi-Hop Routing Protocol Based on Fuzzy Logic and Q-Learning in WSNs
## 4 Proposed Method
### Q-Learning-Based Inter-Cluster Routing  
After the clustering phase, the next task is to establish the optimal transmission path for data to travel from CHs to BS. This routing process can be modeled using finite Markov decision processes and addressed with Q-learning [37]. Q-learning focuses on determining the optimal action strategy within these processes, comprising elements such as the agent, states, actions, rewards, the Q-table, and the environment. Figure 12 presents the Q-learning model employed in this study, demonstrating the approach for optimizing path selection.  
1. The agent (packet) in the current state \(s_{i}\) (represented as \(CH_{i}\)) uses the \(\epsilon\)-greedy strategy to choose the action \(a_{i}\)
2. After executing the action \(a_{i}\), the agent (packet) transitions to a new state, \(s_{j}\) (represented as \(CH_{j}\)), and receives an observed reward, \(r^{a_{i}}_{S_{i}S_{j}}\). The reward value is \[r^{a_{i}}_{S_{i}S_{j}}=\begin{cases}\frac{E_{\text{res}}(s_{j})}{\frac{\sum_{j= 1}^{k}d\left(s_{i}\
eq j\right)}{k}+d\left(s_{j},BS\right)}&if\ s_{j}\text{ is not BS}\\ R_{BS}&el\text{se}\end{cases}\] (12)  
Figure 12: Block diagram of Q-learning.  
where \(E_{res}(s_{j})\) is the residual energy of \(CH_{j}\), \(k\) represents the number of neighbor CHs, \(d(s_{i},s_{j})\) is the distance between \(CH_{i}\) and \(CH_{j}\), and \(d(s_{j},BS)\) is the distance between \(CH_{j}\) and \(BS\).
3. \(s_{j}\) (represented as \(CH_{j}\)) obtains \(\max_{a_{j}\in A_{j}}Q\big{(}s_{j},a_{j}\big{)}\). Note that \(\max_{a_{j}\in A_{j}}Q_{t}(s_{j},a_{j})\) refers to the highest Q-value among all actions available for the state \(s_{j}\), where \(A_{j}\) is the action set of the state \(s_{j}\).
4. \(s_{i}\) (represented as \(CH_{i}\)) updates \(Q(s_{i},a_{i})\) using Equation (12). \[\begin{split} Q(s_{i},a_{i})&\longleftarrow(1- \alpha)Q(s_{i},a_{i})\\ &+\alpha\left[r_{s_{i}s_{j}}^{a_{i}}+\gamma\max_{a_{j}\in A_{j}}Q \big{(}s_{j},a_{j}\big{)}\right]\end{split}\] (13) The multi-hop routing process is outlined in Algorithm 2.  
```
0: CHs set \(CH\_List=\{CH_{1},CH_{2},CH_{3},\cdots,CH_{m}\}\)
0: Route \(R\) from \(CH_{i}\) to \(BS\)(base station)
1: Initialize and each CH constructs its Q-table
2:\(s_{i}\leftarrow\) A CH is randomly selected from the \(CH\_List\)\(/^{*}s_{i}\) is the current state */
3:for each episode do
4:\(R\gets R\cup\{s_{i}\}\)
5:repeat
6:if\(N_{s_{i}}\
eq\{\varnothing\}\)then
7: /* \(N_{s_{i}}\) is the next hop set of CH \(s_{i}\)*/
8: generate random number \(r\)
9:if\(r<e\)then
10:\(s_{i}\) selects action \(a_{i}\) that has the maximum Q-value.
11:else
12:\(s_{i}\) randomly selects action \(a_{i}\)
13:endif/*Select action \(a_{i}\) using \(\epsilon-greedy\) strategy,\(a_{i}\in N_{s_{i}}\)*/
14:endif
15: /*Once the action \(a_{i}\) is performed, the agent's state will change from \(s_{i}\) to \(s_{j}\)*/
16:\(s_{j}\) obtains \(\max_{a_{j}\in A_{j}}Q\big{(}s_{j},a_{j}\big{)}\) Calculate reward \(r_{s_{j}s_{j}}^{a_{i}}\) using Equation (12);
17:\(s_{j}\) feedback \(r_{s_{j}s_{j}}^{a_{i}}\) and \(\max_{a_{j}\in A_{j}}Q\big{(}s_{j},a_{j}\big{)}\) to \(s_{i}\);
18:\(s_{i}\) Update \(Q(s_{i},a_{i})\) using Equation (13) ;
19:\(s_{i}=s_{j}\)
20:until\(s_{j}==BS\)
21:endfor
```  
**Algorithm 2** Q-learning for routing.