# A Novel Relay Selection Scheme Based on Q-Learning in Multi-Hop Wireless Networks
## 3 Proposed Relay Selection Scheme
### Proposed Relay Selection Scheme  
Figure 4 shows the agent-environment for Q-learning in the proposed scheme. First, when the agent takes an action in current state, the environment updates the information about the next state and next reward to the current state and current reward. Next, depending on the reward which is defined in this paper, the Q-value is updated according to the Q-function and updated values are stored in the Q-table. Finally, the highest value among the updated Q-values can be found when the learning is completed and the relay which has the highest Q-value is selected as an optimal relay. If the learning process is briefly described, action is randomly performed and Q-value is stored one by one. When this process is repeated through the learning, various Q-values are stored in the Q-table. When the learning is completed, the highest state among those values is selected as an optimal state and this state represents an optimal relay [15]. The proposed scheme uses a SNR based Q-learning algorithm to select an optimal relay for cooperative communication. In this paper, the states, actions and a reward are defined for proposed relay selection scheme. First, the proposed scheme for relay selection in cooperative communication has total \(N\) nodes. This paper defines states as \(s_{i}\) where \(i\) denotes an index of the node for cooperative communication. Second, an action \(a\) means the selection of a relay from available \(K\) relays and is defined as \(a_{m}\). As a result, the action is changed from a current state to next state. Such action may improve or degrade the performance. Optimal action is naturally learned when appropriate rewards are given. Third, the Q-table is composed with Q-values for each state and action. Initially, the Q-table elements are set to zero. When the learning starts, the agent chooses an action and observes the state to update the Q-table. The Q-matrix defined in this paper is as follows, The Q-value is updated after the learning according to the reward. Reinforcement learning is conducted through random action, so before learning, Q-matrix does not know the included Q-value. So, the definition of a reward is important. The reward is defined by mutual information in terms of the information theory [8]. However, the maximum mutual information is the same as capacity and the capacity depends on SNR and bandwidth. Since bandwidth is normalized, only SNR is considered for the reward. To set a  
Figure 4: Proposed agent-environment system model. reward value, the size of the channel coefficient between source-relay-destination node is compared and then the SNR is obtained based on the these values and set as a reward value. The reward defined in this paper is as follows,  
\[\text{R}(\text{s},\text{a})=SNR_{S,R_{m},D}(s_{t},a_{t}), \tag{7}\]  
where the reward \(R\) is defined as a SNR of the source, relay and destination at state \(s_{t}\) and action \(a_{t}\). This paper sets the reward function by obtaining SNR that can perform an accurate comparison while annalistic complexity is reduced. Equation (7) is a generalized representation of all SNR values between source-relay-destination. A high Q-value is obtained and stored in Q-matrix in state \(s_{t+1}\) if the Q-value in state \(s_{t+1}\) is greater than the Q-value in state \(s_{t}\). Finally, when the Q-table is updated, the Q-learning finds the optimal policy by selecting the state that has the highest reward. The reward matrix defined in this paper is as follows,  
\[R=\left[ \begin{array}{cccc}SNR_{S,S}&SNR_{S,R_{1}}&\cdots&SNR_{S,D}\\ SNR_{R_{1},S}&SNR_{R_{1},R_{1}}&\cdots&SNR_{R_{1},D}\\ \vdots&\vdots&\ddots&\vdots\\ SNR_{D,S}&SNR_{D,R_{1}}&\cdots&SNR_{D,D}\end{array} \right]. \tag{8}\]  
In this environment, the reward is initialized to zero when the learning process returns to the source node. The reward matrix is a collection of the reward values of all source-relay-destination for optimal Q-value calculation. The size and value of the reward matrix are determined according to the reward.