# An Enhanced Tree Routing Based on Reinforcement Learning in Wireless Sensor Networks +
## 2 Related Work  
The routing protocol has an important role in a WSN, ensuring a reliable transmission and satisfying the QoS of individual nodes. The node batteries of a network in the wild are difficult to replace; hence, the routing protocols should create a routing path at low computational cost. In reactive routing protocols, e.g., ad hoc on-demand distance vector (AODV) routing [1], a source node sends a route request message whenever it needs a routing path to the destination node. To maintain a reliable routing path, the node periodically broadcasts control messages and checks the status of the links with its neighboring nodes. Reactive routing can guarantee a reliable transmission in a network in which the nodes frequently move, such as mobile ad hoc networks; however, the control overhead is significantly increased to maintain the routing paths. To reduce the number of control messages, proactive routing protocols, e.g., optimized link state routing protocol [2], select nodes with high connectivity between neighboring nodes as the parent nodes. To maintain the topology information, the parent nodes are obliged to broadcast control messages periodically. This table-driven routing can minimize the number of control messages because only the parent nodes broadcast the topology information; however, the broadcast overhead and memory usage are increased when there is a large amount of node information to be transmitted. Moreover, in a network in which the nodes frequently move, the control overhead significantly increases because topology information must be frequently broadcast. To reduce the energy consumption from the broadcast overhead, tree-based routing is the best solution for a small-scale WSN. A tree-based routing protocol consists of one root node and multiple sensor nodes, which have parent-child relationships and are interconnected based on a tree structure. Each node chooses the optimal parent node and forwards the data to the parent until it reaches the root node. Tree-based routing can eliminate a path search and avoid extensive broadcast messages. The communication links between parent and child nodes are used as routing paths, and parent selection is a key aspect of the tree-based routing protocol. For example, conventional tree-based routing protocols [22; 23; 24] select as the parent node the neighbor node with the lowest number of hops to the sink node. By using the hop count as a decision metric, they can minimize the end-to-end delay; however, the PDR is reduced because frequent node movements degrade the link quality between the child and parent nodes. To build a stable tree structure, the authors of [4] propose a route stability framework in which each node calculates an overall score for each neighboring node. The scores are weighted based on the link quality and relative distance with the neighboring node. The neighbor node with the best overall score is selected as a parent node. In [5], each node chooses the neighboring node with the best link quality metric as a parent node. The link quality metric is calculated using cognitive metrics, i.e., the link packet delivery and link stability. However, this approach does not consider the load balancing during the parent selection process. In other words, an excessive load may be placed on a particular node; thus, congestion occurs at certain nodes, resulting in significant packet loss. In addition, the network lifetime is shortened due to unbalanced energy consumption between nodes. To prevent congestion, the authors of [6] propose a congestion-aware tree routing protocol. With this scheme, each node evaluates the link cost of each neighboring node, and the node with the best link cost is selected. A weighted-sum equation is used to determine the link cost, and the average queue size and remaining energy of the nodes are considered in the proposed formula. The authors of [7] propose a load-aware dynamic cost function to weight the links between the parent and child nodes. The cost of the links is updated based on the congestion metric.