A Dynamic Priority-Based Multipath Routing Algorithm for Wireless Sensor Networks
Author: Liu Yu (Ma’anshan Vocational and Technical College, Department of Electronic Information, Ma’anshan, Anhui 243031)
Abstract
This paper proposes a dynamic priority-based multipath routing algorithm for wireless sensor networks, addressing the defects and reasons of existing multipath routing algorithms. The algorithm uses the number of hops from nodes to the sink node to replace the path energy consumption cost for determining priority, and continuously adjusts the priority during data transmission based on the energy consumption of nodes, thus reducing the complexity of the algorithm and avoiding time and energy losses caused by periodic routing maintenance. Simulation results show that this algorithm effectively reduces and balances the energy consumption of each node, extending the overall network lifetime.
Keywords
Wireless Sensor Networks; Routing Algorithm; Energy Multipath; Dynamic Priority; Path Hops
The task of the routing algorithm in wireless sensor networks is to find an optimized path for data transmission between the source node and the sink node. In wireless sensor networks, nodes have limited energy that is difficult to replenish, so routing algorithms must efficiently utilize energy.
Routing algorithms for wireless sensor networks can be divided into planar routing algorithms and cluster routing algorithms. The energy multipath routing algorithm proposed in the literature is one of the earliest planar routing algorithms for wireless sensor networks, focusing on energy efficiency. During data transmission, it selects paths with low energy consumption and relatively sufficient energy to complete the transmission from the source node to the sink node. However, the algorithm does not dynamically consider the energy loss of each node, and once the probability is determined, it does not change throughout the lifetime of the network. This leads to the frequently selected paths having high selection probabilities, causing uneven energy consumption among nodes.
This paper proposes a dynamic priority-based multipath routing algorithm. In this algorithm, priorities are set for nodes to measure their communication energy cost to the sink node and their remaining energy. During data transmission, paths are selected according to the size of the priority. At the same time, the priority of nodes dynamically changes with their energy consumption. Initially, all nodes have the same energy and are assigned the same initial priority. During the path establishment process, the priority of nodes is updated based on the hop count to the sink node. During data dissemination, the priority is updated in real-time based on the amount of data collected by the node and the number of forwarded data packets. This algorithm effectively reduces and balances the energy consumption of each node, thereby extending the network’s lifetime.
1 Energy Multipath Routing Algorithm
1.1 Steps of Path Establishment Algorithm in Energy Multipath Routing Algorithm
The specific execution steps of the path establishment algorithm in the energy multipath routing algorithm are as follows:
Step 1 Start path establishment, and the sink node broadcasts the path establishment data packet.
Step 2 After receiving the path establishment data packet, adjacent nodes calculate the distance to the sink node based on the coordinate information in the data packet. They then compare this distance with the distance of the previous node to the sink node. If the current node is further away from the sink node than the previous node, it forwards the data packet; otherwise, it discards the packet to avoid loops.
Step 3 As shown in Figure 1, if node Dj receives the path establishment data packet sent by node Di, after the judgment in Step 2, it calculates the communication energy cost C(Dj, Di) for the path connected through node Di to the sink node Ds before forwarding the data packet, calculated as follows:
Exp(Dj, Di) is the energy consumed when node Dj communicates with node Di, calculated based on the direct energy consumption from node Dj to node Di and the remaining energy of node Di, considering both direct energy consumption and the remaining energy of the previous node.
Step 4 Nodes filter paths, discarding those with excessive energy consumption. For instance, if node Dj is to determine whether to store node Di in its routing table, it checks the following condition:
Here, the value of γ is preset based on the storage capacity of the node’s routing table and the system’s demand for the number of routing paths. When γ is small, the number of paths stored in the node’s routing table is limited; conversely, it can store more paths.
Step 5 Nodes calculate the selection probability of all next-hop nodes in their routing tables. For example, node Di in the routing table of node Dj is the next node, so node Dj calculates the selection probability of node Di as follows:
Where PDj(Di) represents the probability of selecting node Di as the next node for data transmission in the routing table of node Dj. It can be seen that the higher the path communication energy cost through a certain node, the lower the selection probability of that node.
Step 6 Nodes calculate the weighted average of the energy cost for all next-hop nodes in their routing tables, such as node Dj calculating the new energy cost Cost(Dj) as follows:
Next, node Dj will place the new energy cost Cost(Dj) into the path establishment message and broadcast this message to neighboring nodes. It then returns to Step 2, continuously repeating until the routing information of all nodes is established.
1.2 Data Transmission Path Selection Process
After the path establishment is complete, when the source node wants to transmit the collected information to the sink node, it starts from the source node, selecting the node with the highest selection probability from its routing table as the next node, and sequentially forwards the information until it reaches the sink node.
1.3 Analysis of Defects in Energy Multipath Routing Algorithm
The energy multipath routing algorithm selects the optimal path by comprehensively considering the energy consumption on each path and the remaining energy of each node along the path, achieving energy load balancing. However, analysis reveals several defects in the energy multipath routing algorithm.
1) During path establishment, it is necessary to calculate the energy consumption required for data transmission between nodes and the remaining energy of nodes, which is difficult to implement in real systems as these energy consumptions and remaining energies are hard to measure.
2) During path establishment, each node must perform a large number of complex calculations, which poses a challenge to the performance and energy consumption of the nodes themselves.
3) The algorithm does not dynamically consider the energy loss of each node; once the probability is determined, it does not change throughout the lifetime of the network. This leads to frequently selecting paths with high probabilities, causing excessive energy consumption in the nodes along these paths and premature failure.
4) If periodic flooding is used from the sink node to other nodes to recalculate parameters, it generates a significant amount of computation and data transmission each time, accumulating considerable energy losses and shortening the overall network lifetime.
2 Dynamic Priority-Based Energy Multipath Routing Algorithm
This study proposes a Dynamic Priority-Based Energy Multipath Routing (DPEMR) algorithm to address the defects of existing energy multipath routing algorithms.
2.1 Basic Idea of DPEMR Algorithm
In the DPEMR algorithm, the role of setting priorities is to select the node with the highest priority from the routing table when a node needs to forward data to the next node during data transmission, sequentially forwarding data until it reaches the sink node. During the path establishment phase, the hop count from each node to the sink node is recorded to replace the energy cost between them, and the initial priority of nodes is calculated based on the hop count. During the network operation phase, the priority of nodes is continuously updated based on the frequency and load of their work (the number of data packets received and forwarded by the node).
2.2 Steps of Path Establishment Algorithm in DPEMR
The specific execution steps of the path establishment algorithm in the DPEMR algorithm are as follows:
Step 1 The sink node broadcasts the path establishment data SetPath(idi, x0, y0, si, hopsi). Here, idi is the ID number of the sending node i (each node in the network has a unique ID); (x0, y0) are the coordinates of the sink node (after network deployment, each node calculates its own coordinates using a positioning algorithm and stores them); si is the distance between node i and the sink node (the value in the data packet sent by the sink node is 0); hopsi is the hop count from node i to the sink node (the value in the data packet sent by the sink node is 0).
Step 2 When adjacent node j receives the SetPath data packet sent by node i, it calculates its distance sj to the sink node based on the coordinates of the sink node and itself, compares sj with si, and if sj > si, it indicates that node j is further from the sink than node i. It then computes, records, and updates the relevant data in the data packet (executing Steps 3 to 5) before forwarding it to adjacent nodes; otherwise, it discards the data packet. The distance calculation formula for node j to the sink node is as follows:
Step 3 If node j receives the path establishment data packet SetPath sent by node i, after the judgment in Step 2, it calculates the path cost (the hop count hopsi = hopsi + 1, as the hop count increases by 1 when the sink node passes through node i to node j) before forwarding the data packet, deciding whether to add node i to its routing table based on the following condition:
After the judgment in (6), if node i meets the condition, it is stored in the routing table of node j.
Here, the hop count to the sink node is used to replace the path energy cost, as a higher hop count on a path indicates more data forwarding and consequently greater energy cost.
The data structure of the node’s routing table is defined as follows:
Step 4 After the node’s routing table is established, nodes calculate the initial priority of each next-hop node in their routing table based on the hop count. Taking node i in the routing table of node j as an example, the priority calculation formula is as follows:
Where n is the number of nodes in the routing table of node j, and (Σk ∈ RTjhopsk)/n is the average hop count of all next-hop nodes in the routing table of node j to the sink node, hopsi is the hop count from node i to the sink node, and Emax is the initial energy value of node i.
Step 5 Node j updates the SetPath(idj, x0, y0, sj, hopsj) data packet, where sj is the distance to the sink node calculated in Step 2, and hopsj is the weighted average hop count to the sink node through each node in its routing table, calculated as follows:
From (8), the hop count hopsj from node j to the sink node is the hop count through each node in its routing table to the sink node, weighted by priority, reflecting the average energy cost of transmitting data from node j to the sink node.
After updating the new SetPath data packet, node j forwards it to neighboring nodes.
Step 6 Return to Step 2, iterating until the routing tables of all nodes are established, completing the path establishment process.
2.3 Data Transmission Path Selection and Node Priority Update Process
After the routing paths of the entire network are established, the network enters the operational state. The data collected by the source node needs to be transmitted to the sink node. At this time, it is necessary to select the path with the highest priority from the routing tables of each node to transmit data from the source node to the sink node. Both the source node and the nodes on the selected transmission path consume energy during data collection and transmission, so it is also necessary to update the priority of the source node and each node along the transmission path. The following steps analyze the specific process based on the situation shown in Figure 2.
Step 1 Assume that at a certain moment, node i collects external information, forming a data packet Message(idi, idnext, data) to be sent to the sink node s, where idi is the ID of node i, and idnext is the ID of the next-hop node with the highest priority in the routing table of node i (for example, node j in Figure 2).
At this time, node i updates the priority of the relevant nodes in its routing table, for example, if node i selects the next-hop node as node j, which will receive and forward the data packet, the priority of node j is updated based on the energy consumed, calculated as follows:
Where Etx(n, d) is the energy consumed by the node to forward an n bit data packet, and Etx(n) is the energy consumed by the node to receive an n bit data packet. Pmin is the uniform priority lower limit of the entire network, mainly considering the energy consumption other than data transmission; if the priority of a node drops to this value, it is considered dead.
Step 2 Node i broadcasts the Message data packet to neighboring nodes, and all nodes within one hop range of node i will receive this data packet. For example, nodes j and m in the dashed box of Figure 2, a total of six nodes, are all neighbors of node i within its direct communication range.
Neighboring nodes of node i are categorized into four situations, and different processing is performed upon receiving the Message data packet, as described below:
1) When a neighboring node receives the Message data packet and finds that its ID matches the idnext in the data packet (for example, node j in Figure 2), this node is the next node selected for forwarding data by the previous node. It then queries its routing table for the next node with the highest priority (for example, node g in Figure 2), updates the idnext in the Message data packet with this node’s ID, and lowers the priority of the idnext node in its routing table by recalculating it using formula (9). It then forwards the Message data packet to neighboring nodes.
2) When a neighboring node receives the Message data packet and finds that its ID does not match the idnext in the data packet, but the idnext node exists in its routing table (for example, nodes h and j in Figure 2), it lowers the priority of the idnext node in its routing table according to formula (9) and discards the Message data packet.
3) When a neighboring node receives the Message data packet and finds that its ID does not match the idnext in the data packet, and the idnext node is not in its routing table, but the idi node exists in its routing table (for example, nodes m and i in Figure 2), it lowers the priority of the idi node in its routing table and discards the Message data packet. The priority update formula is as follows:
4) When a neighboring node receives the Message data packet and does not meet any of the above conditions, it discards the Message data packet.
Step 3 The next node continues to forward the Message data packet, returning to Step 2, repeating until the data packet reaches the sink node.
3 Experimental Simulation
To verify the performance of the DPEMR algorithm, simulations were conducted in the NS-2 simulation environment comparing the energy multipath routing algorithm and the DPEMR algorithm, focusing on network load balancing (load balance factor, LBF) and network lifetime. The parameter settings of the simulation environment are shown in Table 1.
Formulas (11) and (12) are the calculations for the energy consumed by nodes during sending and receiving data.
From Figure 3, it can be seen that as the number of rounds increases, the LBF of the DPEMR algorithm is significantly lower than that of the original algorithm, with a smaller increase. This indicates that the DPEMR algorithm has better network load balancing than the original routing algorithm, due to its use of dynamic priorities for more reasonable path selection during data transmission.
The relationship between the number of surviving nodes and the number of rounds for both algorithms is shown in Figure 4.
From Figure 4, it can be seen that in the network using the DPEMR algorithm, the time from the first node’s energy depletion to the last node’s energy depletion is later than that in the network using the original routing algorithm. This is because the DPEMR algorithm significantly improves the network’s load balancing, avoiding the excessive energy consumption of certain nodes that occurs in the original algorithm, thus extending the network’s lifetime.
4 Conclusion
This paper proposes the DPEMR algorithm based on existing energy multipath routing algorithms. This algorithm sets priorities for nodes to measure their communication energy cost to the sink node and their remaining energy. During the path establishment process, the initial priorities of nodes are calculated based on the hop counts to the sink node. During data transmission, paths are selected based on the size of these priorities. Simultaneously, the priorities are updated in real-time based on the number of data packets received and forwarded by the nodes. Analysis shows that the DPEMR algorithm is simple to implement, has low complexity, and requires minimal computation. The priority updates are completed during data transmission, avoiding the time and energy losses associated with periodic routing maintenance. Simulation results indicate that the DPEMR algorithm effectively reduces and balances the energy consumption of each node, extending the overall network lifetime.
References omitted
Funding Project: Key Research Project of Natural Science of Anhui Provincial Department of Education (KJ2017A894); Key Project of Excellent Young Talent Support Program of Anhui Provincial Department of Education (gxyqZD2016584); Provincial Quality Engineering Project of Anhui Universities (2017jxtd138)
Source of Literature: Liu Yu. A Dynamic Priority-Based Multipath Routing Algorithm for Wireless Sensor Networks [J]. Journal of Jianghan University (Natural Science Edition), 2019, 47(3): 239-245.
DOI: 10.16389/j.cnki.cn42-1737/n.2019.03.008
