Design and Optimization Analysis of Energy-Efficient Routing Algorithms in Wireless Sensor Networks

One of the most important applications of sensors is to collect information about some characteristic changes in the environment and transmit this information to the gateway node (root node) for processing and analysis. According to this application characteristic, the most commonly used sensor routing technique is the tree topology. These routing techniques perform data acquisition by constructing tree-shaped transmission paths. However, the tree topology itself has great limitations; its single transmission path tends to increase the transmission delay, and the root node, which has multiple information collection sub-nodes at the same time, will be the first to run out of energy and become the breaking point of the whole transmission network. In order to solve this problem, we proposed an optimal path selection algorithm for mobile networks with node energy states in our previous research. The routing cost function algorithm that takes into account the relative mobility of nodes is explained below.

In recent years, there have been studies introducing reinforcement learning into routing for infinite networks. Most of these studies have focused on two aspects. One is to quickly find the shortest path for transmission in ad-hoc networks where nodes are mobile; the other is to solve the Qos problem in wireless networks.

Reinforcement learning is an important technique in machine learning that allows an intelligent body to autonomously decide the next optimal action to achieve a specific goal by using the feedback information from the environment about previous actions. Assuming that the time step of each learning is t , the learning process can be defined by the following parameters:

1) The state s_t ∈ S of the intelligent body at moment t , where S is the state set of the intelligent body;

This paper focuses on wireless sensor network systems for data collection. Each sensor node collects or forwards the monitored data information, and all the information will be transmitted to the gateway aggregation node for the next step. We form the network nodes into a multipath transmission topology MPHR [23-24], in MPHR each node maintains its own next-hop routing table, which includes Class A next-hop addresses, i.e., parent nodes that are one level higher than itself, and Class B next-hop addresses, i.e., nodes of the same level as itself. And the process of routing is the process of selecting a node from one’s own routing table as a next-hop forwarding node. If we consider the process of selecting a node from the routing table as a random process, then we define the probability that node i selects node j in the routing table as the next-hop forwarding address as μij$\mu _{i}^{j}$ . Since the goal of MPHR-RL is to try to average the number of times each node works, we define the return r_i at the moment of t to be the number of times the last next-hop node selected by node i was forwarded, i.e., as negative: (1) rt:=−Trans−Numlastnexhop \[{{r}_{t}}:=-Tran{{s}_{-}}Nu{{m}_{last\;nexhop}}\]

Following the previous definition, the average return expectation η(θ) is: (2) η(θ):=E[limT→∞1T∑t=1Trt] \[\eta (\theta ):=E[\underset{T\to \infty }{\mathop{\lim }}\,\frac{1}{T}\sum\limits_{t=1}^{T}{{{r}_{t}}}]\]

It can be known that when the number of node forwards is more average, the cumulative sum of the number of next-hop node forwards is smaller, and the sum of r_t is larger, and the sum of η(θ) is larger.

In order to make the sensor nodes learnable, we need to set a formal parameter θ for each node’s possible next hop, which is used to represent the node’s selection probability μ , and here the formal parameter of node i ‘s next hop node j is defined to be θij$\theta _{i}^{j}$ , and in order to make the computation easy, we apply the Gibbs distribution [25-26] to represent the probability μij$\mu _{i}^{j}$ , defined: (3) μij(θ):=eθij∑jeθij \[\mu _{i}^{j}(\theta ):=\frac{{{e}^{\theta _{i}^{j}}}}{\sum\limits_{j}{{{e}^{\theta _{i}^{j}}}}}\]

The summation in the above equation indicates that all the optional next hop nodes in the node’s own routing table are included. It is easy to introduce that the larger θij$\theta _{i}^{j}$ is in the Gibbs distribution, the larger the probability μij$\mu _{i}^{j}$ is.

The goal of enhanced learning performed by the nodes is to find the maximum η(θ) , i.e., the minimum number of forwarding sums, i.e., to find the case where the energy consumption of each node is most average. Each node will update its θ value in the direction of making η(θ) large during the interval t between two forwards, as shown in Equation (4): (4) θt+1=θt+Δθt \[{{\theta }_{t+1}}={{\theta }_{t}}+\Delta {{\theta }_{t}}\]

The rules for the value of Δθ_t are defined in the GPOMDP, and θ is updated as shown in the following equation: (5) θt+1:=θt+γt⋅rt⋅ztj \[{{\theta }_{t+1}}:={{\theta }_{t}}+{{\gamma }_{t}}\cdot {{r}_{t}}\cdot z_{t}^{j}\]

where r_i is the return at the moment of t , γ_i is the appropriate convergence step, here in order to speed up the convergence, we define γ_i to be a smaller constant, and z_i is a parameter of the same dimension as θ_i , which is also updated according to the changes of other covariates within each forwarding interval t , and the update rule is shown in Equation (6): (6) zt+1i:=β⋅zti+∇μji(θ)μji(θj) \[z_{t+1}^{i}:=\beta \cdot z_{t}^{i}+\frac{\nabla \mu _{j}^{i}(\theta )}{\mu _{j}^{i}({{\theta }^{j}})}\]

where the gradient operator ▽ is computed for parameter θ of node i . Since when a node forwards a packet to the next hop, the receiving node immediately replies to the sending node with an answer packet, which includes the number of times the receiving node has already forwarded the packet, i.e., the return r_i of that transmission, we can consider r_i as a parameter that is immediately available to the node. From Eqs. (1)~(6), it is clear that the node only needs to record the z_i,θ_i,μ_i(θ,t) and r_i4 parameters of the forwarded packet at the previous moment for the next step of route learning, which is very beneficial as well as achievable for sensor nodes with very limited memory space.

Based on the relative mobility between nodes and node energy, this paper establishes a mobility routing cost function [27-28] calculation method that considers the influence of these two factors at the same time, so that nodes can use this cost as the main index in the process of route establishment to select the optimal path to establish routes, so as to achieve the purpose of balancing energy consumption and ensuring network quality.

Define the remaining energy of the node as: (7) Ei(t)=E0−δ×t−ΔE×Csum \[{{E}_{i}}(t)={{E}_{0}}-\delta \times t-\Delta E\times {{C}_{sum}}\]

Where δ is a time factor to regulate the rate at which the energy left in the node decays with time, t is the running time of the node, and C_sum is the number of packets forwarded by the node after it starts running.

Equation (7) defines the remaining energy E_i(t) of a node, which is determined by the initial energy E₀ of the node, the running time t , the number of packets C_sum forwarded by the node in aggregate since it started running, and the energy consumption ΔE of the forwarded packets. To further measure the extent of the node’s remaining energy, the concept of node’s energy residual rate η is introduced and the energy residual rate η_i of node t is defined as: (8) ηi=Ei(t)E0=E0−δ×t−ΔE×CsumE0 \[{{\eta }_{i}}=\frac{{{E}_{i}}(t)}{{{E}_{0}}}=\frac{{{E}_{0}}-\delta \times t-\Delta E\times {{C}_{sum}}}{{{E}_{0}}}\]

To represent the relative mobility between nodes, define the speed of movement of node i with respect to node j as: (9) νij=(νix−νjx)2+(νiy−νjy)2+(νiz−νjz)2 \[{{\nu }_{ij}}=\sqrt{{{({{\nu }_{ix}}-{{\nu }_{jx}})}^{2}}+{{({{\nu }_{iy}}-{{\nu }_{jy}})}^{2}}+{{({{\nu }_{iz}}-{{\nu }_{jz}})}^{2}}}\]

where the velocity with subscript x, y, z respectively is the velocity component in the direction of the three coordinate systems of node , i, j respectively.

Similar to the definition of energy residual rate, to further measure the relative mobility between nodes, the concept of node relative mobility σ is introduced, and the relative mobility of node i with respect to node j is: (10) σij=νij×νijmax=(νix−νjx)2+(νiy−νjy)2+(νiz−νjz)2×|νi+νj| \[{{\sigma }_{ij}}={{\nu }_{ij}}\times {{\nu }_{ij\max }}=\sqrt{{{({{\nu }_{ix}}-{{\nu }_{jx}})}^{2}}+{{({{\nu }_{iy}}-{{\nu }_{jy}})}^{2}}+{{({{\nu }_{iz}}-{{\nu }_{jz}})}^{2}}}\times |{{\nu }_{i}}+{{\nu }_{j}}|\]

Where the former is the relative movement speed between the two nodes, the latter is the sum of the absolute movement speed between the two nodes, i.e., the maximum value of the relative movement speed of the two nodes, characterizing the relative speed between the nodes in the limit state of the movement of the two nodes in opposite directions. The three nodes with the same relative movement speed to each other, the greater the sum of absolute movement speed the greater the relative movement of the two nodes.

Combining the energy residual rate and relative mobility defined above, the weighted definition of the routing cost function of node i with respect to node j is: (11) CEV(i)=ασy^+β(1−ηi)=α(νy^×νijmax)+βE0−Ei(t)E0 \[{{C}_{EV}}(i)=\alpha {{\sigma }_{{\hat{y}}}}+\beta (1-{{\eta }_{i}})=\alpha ({{\nu }_{{\hat{y}}}}\times {{\nu }_{ij\max }})+\beta \frac{{{E}_{0}}-{{E}_{i}}(t)}{{{E}_{0}}}\]

Where α and β are weighting coefficients that indicate the importance of node mobility and energy possessed in a specific network, the more energy left in a node that satisfies α + β =1 , the lower the relative mobility represents the more stable the node is, i.e., the smaller the value of C_EV(i) is the more stable the node j is with respect to node i . Thus, the routing cost of a complete path from source node to target node is defined as: (12) CEV=∑i=1NCEV(i)=∑i=1N[ ασij+β(1−ηi) ]j∈[ i+1,N ] \[{{C}_{EV}}=\sum\limits_{i=1}^{N}{{{C}_{EV}}}(i)=\sum\limits_{i=1}^{N}{\left[ \begin{matrix} \alpha {{\sigma }_{ij}}+\beta (1-{{\eta }_{i}}) \\ \end{matrix} \right]}j\in \left[ i+1,N \right]\]

Where N denotes the number of nodes in the whole link. After the intermediate node receives the RREQ packet, it calculates the routing cost relative to the previous hop node by the speed and energy information of this node, and after the RREQ reaches the target node (or its parent node), it gets the routing cost of the whole link. The target node (or its parent node) will select the path with minimum C_EV among all links to respond to RREP and establish the route.

In this paper, the MPHR-RL algorithm is simulated and analyzed, and the node distribution of the simulation network is shown in Fig. 1. n sensor nodes are randomly distributed in the square area of L*L, and the mobile base station nodes start from the starting point (0, 0), visit the anchor points to collect the data in turn, and return to the starting point to complete a round of data collection. In order to better evaluate the performance of the algorithms proposed in this chapter, this paper sets up three comparison algorithms based on the algorithms in this chapter to compare and evaluate the three important parts of the algorithms respectively. The three algorithms are: Algorithm 1 (E-WA) uses the traditional shortest path for data transmission; Algorithm 2 (E-WM) uses the equivalent multipath routing algorithm, ECMP, for data transmission; and Algorithm 3 (E-WI) uses the adaptive wireless routing algorithm with enhanced learning algorithm for data transmission. The relevant parameters used in the simulation of this section are: T_lim = 1200s , τ_s = 4s , v = 5m / s , ε = 0.01 ; MPHR-RL algorithm related parameters: θ_i = 100, Z_i = 18, a = 1, β = 5, r_i = 0.5, C_EV = 1 ; network related parameters: L = 800m, N = 400 .

Figure 1.

Distribution of nodes in the simulation network

In this paper, the number of dead rounds of the first node is used as a measure of network lifetime. The number of surviving nodes in the network of different algorithms varies with the number of running rounds as depicted in Fig. 2. The experimental results show that the algorithm MPHR-RL in this paper has the longest network lifetime. When the number of network operation rounds is at 1400 rounds, the number of surviving nodes of MPHR-RL method is still 221 rounds, while the number of surviving nodes of E-WA, E-WM and E-WI methods are extremely small, 12, 23 and 5 rounds, respectively. Moreover, as shown in Fig. 2, the number of running rounds at half node death for the four algorithms MPHR-RL, E-WA, E-WM and E-WI are 1350 rounds, 1170 rounds, 1029 rounds and 954 rounds, respectively, and it is obvious that the number of running rounds at half node death as well as the number of running rounds at all node death for MPHR-RL algorithm is larger than that for the other comparative algorithms, which fully demonstrates that the MPHR-RL outstanding effect in prolonging the network lifetime.

Figure 2.

The operation of the network survival nodes of each algorithm

This may be related to the fact that the difference between the algorithm MPHR-RL and E-WA algorithm in this paper lies in the method of determining the anchor access sequences, MPHR-RL is optimized with the objective of shortest path length based on the mobility routing cost function algorithm and assisted by reinforcement learning methods. While E-WA by random path selection, MPHR-RL under the same anchor distribution will greatly reduce the mobile base station (BS) travel distance and shorten the mobile BS cruising time under the same number of anchor points. It maximizes the number of finalized anchor points within limited mobile BS range time, which reduces the upload distance between the node and the mobile BS. Thus, saving data transmission energy for the node and affecting network lifetime. The difference between MPHR-RL algorithm and E-WM algorithm in this paper lies in the routing method, MPHR-RL uses the office as the single-hop mode switching criterion, and the nodes with anchor distance less than the office use single-hop, which can effectively save energy. The nodes outside the office can save energy by choosing the nodes inside the office as relays, which helps to equalize the energy among the nodes. The difference between MPHR-RL algorithm and E-WI algorithm in this paper lies in the way of determining the distribution of anchor points, E-WI selects the center of the spray as the anchor point through K-means, which is random and does not take into account the energy of nodes, which is prone to the emergence of high-energy nodes, and the network has a shorter lifespan. Whereas, the algorithm in this paper is based on the energy trough coefficient and selects the nodes with low energy in the network as anchor points, which are approached by the mobile BS for data collection, which greatly reduces its energy consumption in that round, which helps in energy equalization and thus prolongs the network lifetime.

The structure for comparing the number of BS access anchor points under different algorithms is depicted in Fig. 3. In this paper, the first 100 rounds of relevant data from network operations are intercepted for algorithm performance analysis. The results show that the algorithm MPHR-RL in this paper, when the network edge length is 800m, the initial number of anchor points is 97, and under the restriction of mobile BS range inches, the finalized number of anchor points is 86, and the average value of the number of anchor points in the whole process is 90.87, with the highest number of anchor points reaching 100 and the smallest number of anchor points being 74. The average values of the number of anchors in the whole process are 90.87, with a maximum of 100 and a minimum of 74. The average values of the number of anchors in the whole process are 8.78, 7.33 and 6.70 for the three comparative methods of E-WA, E-WM and E-WI respectively, with the length of the network of 800m and 100 rounds of interception. Obviously different algorithms are affected by the network energy trough of each - round, the distribution of anchor points under different number of anchor points is different, and the corresponding anchor point access sequence is also different, which affects the cruising time of the final mobile BS, and thus there are fluctuations in the number of anchor points under different number of rounds. However, the MPHR-RL algorithm in this paper is generally at a high level and achieves the effect of maximizing the number of anchor points. Obviously, compared to other algorithms, this paper’s MPHR-RL algorithm has the highest number of anchor points visited by the BS under MPHR-RL. It can be seen that the adaptive wireless routing policy with enhanced learning algorithm proposed in this paper is extremely stable.

Figure 3.

The comparison of the number of anchor points in the different algorithm

The results of BS moving path length comparison under different algorithms are shown in Fig. 4. As can be seen from the figure, the MPHR-RL algorithm proposed in this paper is significantly better than the other three comparison methods, and the average value of the BS moving path length of the MPHR-RL algorithm is 5.5049 Km, while the average values of the E-WA, E-WM and E-WI methods are 4.2805 Km, 4.1161 Km and 3.7060 Km respectively for the three comparison methods with the length of the network side of 800m and the 100 rounds of interception of the network during the whole process. The mean values of the BS movement path lengths for the three comparison methods, E-WA, E-WM and E-WI, are 4.2805 Km, 4.1161 Km and 3.7060 Km, respectively, for a network edge length of 800 m and 100 rounds of network interception, and the reason for this result may be related to the optimization schemes of anchor distribution of different algorithms. In the first 100 rounds of network operation, the moving path length distribution of this paper’s algorithm MPHR-RL is greater than 5 Km, while the moving path length distribution of the remaining three methods is less than 5 Km. It can be seen that this paper’s anchor access sequence determination scheme can effectively optimize the BS moving paths, and at the same time, the fluctuation of MPHR-RL’s value is the smallest, which further proves the stability of the paper’s algorithm.

Figure 4.

Different algorithms are compared with the length of the BS mobile path

This experiment compares the latency differences between different algorithms under dynamic network load from the perspective of latency. The algorithms’ delay performance is evaluated before and after a node load change in dynamic network load. The results of the delay comparison under dynamic network load are shown in Fig. 5. In the case of dynamic network load, the load variation starts to change from the time when the number of iterations is zero. The MPHR-RL algorithm proposed in this paper has the lowest transmission delay of 29.99 ms, while the transmission delays of the three comparative methods, E-WA, E-WM and E-WI, are 102.24 ms, 138.09 ms and 164.34 ms, respectively, when the number of iterations is 0. It has been found that the transmission delay of the four methods tends to stabilize at 40 iterations, which is when the four methods’ performance under dynamic network loads stabilizes. It is found that the transmission delay of the four methods is 85.51 ms, 219.93 ms, 246.43 ms and 290.72 ms at 40 iterations, at which time the transmission delay of the four methods is 85.51 ms, 219.93 ms, 246.43 ms and 290.72 ms, respectively. It is obvious that the MPHR-RL algorithm reduces the transmission delay of the MPHR-RL algorithm by 61.11%, 65.30% and 70.59% compared with the other algorithms, respectively. In contrast, the comparison algorithms are not able to effectively adjust their strategies for the real-time network state, resulting in a large transmission delay. By comparing the fluctuation of transmission delays between different algorithms during load changes, it can be found that the proposed algorithm can quickly adapt to the dynamically changing network environment.

Figure 5.

The delay of the dynamic network load is the result

The experiment compares the differences in task transfer success rates between different algorithms under static and dynamic network loads from the perspective of task transfer success rates. Among them, under dynamic network load, the experiment counts the difference in the overall task transfer success rate of each algorithm, which is affected by the change of network load in iteration. The results of comparing the task transfer success rate of each algorithm are shown in Table 1. By comparing the task transmission success rate of each algorithm in static network under different network loads, it can be found that the success rates of the four algorithms, MPHR-RL, E-WA, E-WM, and E-WI, are 99.87%, 93.01%, 90.85%, and 89.93%, respectively, under low network loads. As the network becomes highly loaded, the success rates of the 4 algorithms MPHR-RL, E-WA, E-WM and E-WI are 98.01%, 53.83%, 65.87% and 74.23%, respectively. In contrast, only the MPHR-RL algorithm proposed in this paper keeps the transmission success rate basically unchanged, while the success rates of the 3 methods, E-WA, E-WM and E-WI, are reduced by 39.18%, 24.98% and 15.70%, respectively. The MPHR-RL algorithm is able to maintain a high task transfer success rate (98.85%) in a dynamic network load. Compared to this algorithm, the other 3 algorithms, E-WA, E-WM and E-WI, have a task transfer success rate of 73.27%, 76.16% and 79.786%, which are 25.58%, 22.69% and 19.07% less than the MPHR-RL algorithm, respectively. Combining the differences in the task transmission success rates of the algorithms under static and dynamic network loads, it can be seen that the MPHR-RL algorithm can adjust the routing strategy in time through the interaction with the environment to realize the stable transmission of the tasks, and avoid the task transmission success rate to be drastically reduced due to the network load becoming larger.