# An Enhanced Tree Routing Based on Reinforcement Learning in Wireless Sensor Networks +
## 4 Proposed Tree Routing Protocol
### Parent Selection
#### 4.2.2 Proposed Algorithm  
To find the best parent node, we define multiple cognitive metrics (i.e., hop count, received signal strength, buffer occupancy ratio, and power consumption ratio). Our key idea is that each node adaptively changes its parent node according to the current network state using the cognitive metrics. Obviously, the more cognitive metrics we consider, the more benefits achieved when choosing the parent node; however, complex decision-making problems may arise. To solve this problem, in this work, we present the RL-based parent selection algorithm.  
The proposed algorithm selects the node with the highest reward as a parent node. Algorithm 2 shows the detailed process of the parent selection. Given a state \(s\), each node chooses a parent node among the neighboring nodes based on epsilon-greedy algorithm (lines 4-5). When the parent node selection is complete, the node observes the reward \(r\) and new state \(s^{\prime}\) from the network environment (lines 6-8). The node then sends a join request to the candidate parent node (line 9). After receiving the join request message, the selected parent node replies to the corresponding node with a join acceptance message or a join rejection message (lines 12-18). Until the episode ends, each node finds an optimal parent node through trial and error.  
Recall that the node selects the neighboring node with the same or fewer number of hops to the sink node than itself as a parent node; thus, the hierarchical level of nodes is autonomously configured based on the number of hops. However, each node can select a neighbor node in the same level (i.e., a node with the same number of hops to the sink node) as a parent node. As a result, a cycle can be generated. To check the cycle between the parent and child nodes, each node sends a join request message to the candidate parent node with its list of child nodes (line 9). The node receiving the join request message detects a loop based on the list of child nodes (lines 19-24). If a loop is not detected, the node replies a join acceptance message. Otherwise, it returns a join rejection message.  
Figure 4: An example: RL-based parent selection.  
```
1:Initialization:
2:\(N_{child}\): List of child nodes \(PID\leftarrow\varnothing\) // The ID of parent node Initialize \(Q(s,a)\) arbitrarily
3:
4:for each episode do
5: Initialize \(s\)
6:for each step of episode do
7: Choose \(a\) from \(s\) using policy derived from \(Q\)
8:\(PID\gets a\)
9: Observe \(r\), \(s^{\prime}\)
10:\(Q(s,a)\gets Q(s,a)+\alpha[r+\gamma max_{a^{\prime}}Q(s^{\prime},a^{\prime}) -Q(s,a)]\)
11:\(s\gets s^{\prime}\)
12: Send a join request message \(I_{request}\) with \(N_{child}\) to the selected parent node (\(PID\))
13:endfor
14:endfor
15:upon receiving a join request message \(I_{request}\) from node \(i\)
16:\(r\leftarrow\)Loop_Detection (\(N_{child}\) of \(I_{request}\))
17:if\(r=True\)then
18: Send a join rejection message \(I_{reject}\) to node \(i\)
19:else
20: Send a join acceptance message \(J_{accept}\) to node \(i\)
21:endif
22:Function: Loop_Detection (\(N_{child}\))
23:for each node \(i\) in \(N_{child}\)do
24:if\(my\_id=i\)then
25: return True
26:endif
27:endfor
28:return False
```  
**Algorithm 2** Parent selection at node \(k\).