# Q-RPL: Q-Learning-Based Routing Protocol for Advanced Metering Infrastructure in Smart Grids
## 4 Q-RPL: Q-Learning-Based Routing Protocol Design
### Reward and Policy Design  
The reward \((r)\) is another important component in the Q-learning algorithm. Reward refers to the feedback that the agent (in this case, a network node) receives after taking a specific action. This feedback is crucial as it guides the learning process, shaping the node's understanding of which actions are beneficial and should be repeated in the future. We consider that the reward function in the context of routing protocols must be designed to reflect the effectiveness of routing decisions in the most direct way. Different from previous studies, such as [39; 40], that assigned weights to distinct indirect performance metrics (number of hops, ETX, congestion status, etc.) to estimate the performance of taking an action, our reward function is assigned based on the success and efficiency of packet transmissions to the next hop. Thus, we take into account the number of transmission attempts required to successfully deliver a packet. Consequently, the structure of the reward is as follows:  
* **First attempt success. ** A reward of \(+2\) is granted for a packet that successfully reaches its next hop on the first attempt, not requiring re-transmissions. This scenario represents the ideal case, where the routing decision leads to an efficient and effective outcome. * **Success on the first re-transmission. ** After a failure on the first transmission attempt, if the packet is successfully transmitted on the first re-transmission attempt, the reward is set to \(+1\). This represents a less optimal successful transmission. * **Success on the second re-transmission. ** A reward of \(0\) is given for a packet that reaches the next hop on the second re-transmission. This situation indicates a less efficient routing decision. * **Success on the third re-transmission. ** A reward of \(-1\) is given for a packet that reaches the next hop on the third re-transmission. This situation warrants a slight penalty. \begin{table}
\begin{tabular}{c c} \hline \hline
**State-Action Pair (s, a)** & **Q-Value** \\ \hline \((s^{i}_{1},a^{i}_{1})\) & \(Q(s^{i}_{1},a^{i}_{1})\) \\ \hline \(\vdots\) & \(\vdots\) \\ \hline \((s^{i}_{1},a^{i}_{k})\) & \(Q(s^{i}_{1},a^{i}_{k})\) \\ \hline \((s^{i}_{n},a^{i}_{1})\) & \(Q(s^{i}_{n},a^{i}_{1})\) \\ \hline \(\vdots\) & \(\vdots\) \\ \hline \((s^{i}_{n},a^{i}_{k})\) & \(Q(s^{i}_{n},a^{i}_{k})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Q-table representation for node \(i\). * **Failure to transmit. ** If the packet fails to reach the next hop after all attempts, the reward is \(-2\). This condition represents an action failure and is penalized accordingly. Differentiating between the varying levels of transmission efficiency ensures that the learning process inherently favors routing decisions that lead to successful and efficient packet deliveries. The negative reward for failed transmissions further reinforces the need for reliable routing choices. Over time, this mechanism allows the Q-learning algorithm to discern and prefer routing paths that not only succeed in delivering packets but do so with optimal efficiency. For instance, consider a dynamic scenario in which different levels of signal interference or congestion can affect transmission success and where a node must choose between two potential candidates for routing data packets to a destination. Option A is a node that often experiences signal interference due to its location, while option B benefits from a clear and unobstructed link. Initially, the node may randomly select between these options, but will evaluate the number of re-transmissions required to successfully deliver a packet. When sending packets via option A, three re-transmissions are typically necessary, each resulting in a reward of \(-1\). In contrast, choosing option B usually requires no re-transmissions, yielding a reward of \(+2\). Given the operation of the Q-learning algorithm, this reward system will naturally favor option B in the long run.