# WSN Routing Protocol Using a Multiobjective Greedy Approach

Authors: Seyed Reza Nabavi; Nafiseh Osati Eraghi; Javad Akbari Torkestani
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Due to the widespread use of communication networks and the ease of transmitting and gathering information through these networks, wireless sensor networks (WSN) have become increasingly popular. Usability in any environment without the need for environmental monitoring and engineering of these networks has led to their increasing usage in various fields. Routing information from the sensor node to sink, so that node energy is consumed uniformly and network life is not reduced, is one of the most important challenges in wireless sensor networks. Most wireless networks have no infrastructure, and embedded sensor nodes have limited power. Thus, the early termination of the wireless node’s energy based on the transmission of messages over the network can disrupt the entire network process. In this paper, the object is designed to find the optimal path in WSN based on the multiobjective greedy approach to the near optimal path. The proposed model is presented in this method to transfer sensed data of the sensor network to the base station for the desired applications. In this method, the sensor nodes are identified as adjacent nodes based on their distance. The energy of all nodes initially is approximately equal, which decreases with the transfer of information between the nodes. In this way, when a node senses a message, it checks several factors for transmitting information to its adjacent nodes and selects the node with the largest amount of factors as the next hop. The simulation results show that the energy consumption in the network grids is almost symmetrically presented, and the network lifetime is reduced with a gentle slope that provides optimum energy consumption in the networks. Also, the packet transmission delay in the network reaches 450 milliseconds for the transmission of information between 15 nodes and 650 connections. Besides, network throughput increases by approximately 97%. It also shows better performance compared to other previous methods in terms of evaluation criteria.


---

## Body

## 1. Introduction

Due to the widespread use of communication networks as well as the ease of communication over wireless networks, these types of networks have received much attention. Usability in any environment without the need for infrastructure and physical communications and the need for environmental monitoring and engineering are unique features of these networks and have led to the increasing use of wireless networks in various fields. Wireless sensor networks (WSN) is a subset of wireless networks created to collect information from the environment [1].Sensor-based systems cover a wide range of potential applications, including military and civil engineering (such as environmental monitoring, health care, and disaster forecasting). As such, the increasing use of WSNs has led to challenges in sending and receiving information, and one of the most important challenges is routing of these types of networks. Routing in WSN is very complex due to the prominent features that distinguish these types of networks from many contemporary wireless networks. Many ad hoc routing protocols have been introduced in the publications, but none of them can be directly implemented with limited resources and sensor networks. WSNs have been characterized by their unsupervised behavior and the nature of all data dissemination, and the often topology changes in the network are making it very complex to design routing protocols for WSNs. Therefore, due to the changing topology and interference in communications, paths may be easily stopped and deadlocked. Sensors with limited resources are often unable to cope with such disruptions and barriers. In addition, interconnections may have limited bandwidth and may not utilize the power required at a specific time. Since sensors face such resource constraints, routing protocols must be such that the complexity of communication and power consumption are not imposed on the network [2].Given this application, routing protocols should utilize high congestion and more WSN nodes to increase network capacity by multiple paths. In fact, multiple routing is considered as a viable alternative to single route routing, as this enables WSN to accumulate network bandwidth. However, the nature of all broadcasting hampers these goals in the context of high-speed programs. Simultaneous use of adjacent routes at high rates results in severe interspatial interference, which increases the likelihood of closed collisions on active routes. In the publications, this is known as the problem of route connectivity and seriously affects the capacity of wireless sensor networks. This problem gets worse as the size of the network becomes larger [3].On the other hand, due to the limitation of sensor energies in the network, sending and receiving information between sensor networks have the highest energy consumption. By unnecessarily energy consuming of the sensors, their energy will end and will reduce the overall network life and will disrupt the collection of information from the environment. In addition, due to the use of wireless sensor networks, delays in these types of networks may not be acceptable. Therefore, finding the shortest path in the network will in addition to reducing the transmission time of information will also increase the lifetime of the network [4].In this paper, the object is designed to find the optimal path in WSN based on the multiobjective greedy approach to near optimal path. Due to the widespread and dynamic nature of the wireless sensor network, this paper used the multiobjective greedy approach to optimize these parameters. The contribution of this paper is stated as follows:(1)
Finding the closest nodes to the source node as local neighbors in each hop of data transmission(2)
Defining a multiobjective fitness function based on the fusion of destination node distance estimation, residual energy, and link quality(3)
Choosing the best neighbor node according to the evaluation of the proposed fitness function in a greedy manner(4)
Evaluate the route in terms of energy consumption, network life, data delivery rate, throughput, and end-to-end delay(5)
Comparison with previous methods in order to evaluate criteriaThe structure of the article is as follows. In the second part, we will discuss the WSN routing tasks. The third section will detail the proposed method. The fourth section will be stated the results of the experiments. Finally, in Section5, we will discuss and conclude the article.


## 2. Related Work

Due to the importance of routing methods in data transmission and WSN lifetime, many approaches have been proposed. Lu et al. have proposed that a location-based multiobjective optimization routing protocol (LMOR) based on residual energy estimation, the rate of upgrade, and the quality of each hop link is in the form of a multiobjective optimization function, and packet routing is based on the maximum value of this function [4]. Liu et al. have determined the capability of data transfer from greedy routing to the ratio of successful data transfer from the sensors to the base station and guaranteed packet delivery based on the ratio of successful data delivery that is not less than the η threshold and examines the relationship between transmission power of sensors and the likelihood of achieving guaranteed delivery [5]. Benserbaj et al. represented position-based routing based on two greedy routing strategies by advanced parameters in the sink node via symmetric links that have the least path loss (PSPL) and maximum transmission distance [6]. Sun et al. have presented a location-based routing plan for WSN that will vigorously attempt to find a solution for data transmission in the WSN. This method not only puts the current nodes and the mobile nodes in a single scheme but also considers the full energy consumption in evaluating the next hop potential [7]. Kulkarani et al. developed a multiobjective hybrid routing algorithm (Q-MOHRA) for heterogeneous WSN that considers optimal path selection, link characteristics (energy, hop count, link quality index, etc.), and path metrics [8].Atia et al. have analyzed the routing problem from the perspective of game theory and modeled the problem of route selection in a wireless sensor network as an evolutionary adaptation path. In this study, they have obtained a stable evolutionary strategy of the game and have proved that the derivative strategy cannot be implemented with a greedy strategy, i.e., a mutated strategy [9]. Rahat et al. have introduced a multifunctional evolutionary algorithm to find optimal paths that have an approximate balance between network lifetime and robustness. In this research, a new criterion of network strength, fragility, is introduced, according to which the distribution of traffic between paths in a multipath path optimize lifetime or fragility and can be found by solving an appropriate linear program [3]. Doggy et al. have developed a path satisfaction model based on the frog jump algorithm that takes into account the predicted tendency, residual energy, and minimum hop number. The algorithm updated individually in the local optimization process and introduced a variable learning factor [10].Sun et al. have proposed a Secure Routing Protocol based on Multiobjective Ant-colony-optimization for WSN by considering the residual energy and path confidence, which has used multipheromone information and the multiheuristic information to optimize two objective functions [11]. Vijayalakshmi et al. have proposed a near-optimal routing protocol based on the combination of particle swarm optimization and tabu search algorithm to optimize a number of cluster percentage of nodes alive, average packet loss rate, and average end-to-end delay [12]. Raychaudhuri et al. have used bioinspired algorithms like particle swarm optimization (PSO) and ant colony optimization (ACO) to solve the issues of WSN. [13] Singh et al. have presented multiobjective tournament harmony search-based coverage aware load balanced clustering algorithm. This method has considered coverage rate, dead gateways, dead sensors, energy consumption, and network lifetime as objective functions [14]. Tingqing et al. have proposed a multiobjective energy-aware routing optimization scheme. This method has used priority of path by pruning founded paths to avoid the searching space explosion problem caused by the increase of nodes. It also has used a new crossover and mutation method in a genetic algorithm based on the gene fragments connected by the adjacent node or the same node to maximize the effectiveness of the evolution result [15].Guruprakash et al. have proposed a method based on energy efficient and delay aware routing using multiobjective clustering and asleep schedule scheme for WSN. In this method, firstly, a multiobjective wolf optimization algorithm for clustering has presented. Then, in order to reduce energy consumption, this method has used a sleep scheduling scheme. Also, this method has used a selective track search algorithm to collect data in an optimal manner to improve lifetime and other quality of service factors in WSN [16]. Malakar et al. have proposed an intelligent method for CH selection in WSN using teaching-learning-based optimization (TLBO) that has tried to optimize several conflicting objectives of the network by selecting CH efficiently and dynamically in each iteration of the network [17].Wang et al. introduce a new algorithm for covering control based on particle swarm optimization (PSO). In the first step, the sensor nodes are randomly placed and remain fixed until the end of the simulation. Then, all area in the network are divided into subnetworks, and the coverage and energy consumption of each subnetwork have been calculated. Finally, the measurement radius of each sensor node in each subnetwork is considered related according to the coverage and energy consumption [18].Wang et al. introduce the common big data service construction and the technical treating context, which covered data gathering and storing. They, also argue big data treating and analysis due to diverse service supplies, which can provide valuable information for service clients. They introduce the complete cloud computing facility scheme based on big data, which present high utilization solutions for extensive data storage, processing, and examination. Finally, they have conducted some big data usage scenarios into different contexts [19].Wang et al. have presented an Enhanced Power Efficient Gathering in Sensor Information Systems (EPEGASIS) algorithm to improve the hot spots issue from multisubject. Firstly, near-optimal connection distance is determined to decrease the energy ingestion during communication. Then, the edge value is set to support the vanishing nodes, and moveable sink equipment is utilized to balance the energy consumption amongst nodes. Next, the node can set its connection range due to its distance to the sink node [20].Wang et al. have introduced a new route planning approach based on the coverage rate for several mobile sinks, especially for extensive networks. An enhanced PSO joined with a mutation operator is presented to search the stopping place with a near-optimal coverage rate. Then, the genetic algorithm (GA) has assumed to plan the moving route for several moveable sinks [21].Wang et al. have presented an affinity propagation-based self-adaptive (APSA) clustering method. The benefit ofK-medoids, which is a basic machine learning algorithm, is joined with the similarity broadcast scheme to reach more realistic clustering utilization. This approach is used to set the number of cluster heads and to find the primary cluster centers forK-medoids. Then, the improved K-medoids are used to configure the network in an international manner. This approach solves the weakness of the basic K-medoids in terms of the uniform clustering and convergence rate [22].


## 3. Methodology

### 3.1. Definition of Network Parameters

In this study, we consider a multihop WSN with a sink node andN wireless sensor. The sink node collects information from the sensor and sends the processing results to the external server. Sensor nodes act as information sources and relays that are used to send data packets. In the proposed method of energy calculation algorithm, packet transmission powers are selected consistently to ensure packet transport at different distances that require different energy consumptions. Hence, the weight (Wd) represents the constant energy consumption when a node transmits a packet at distance l. The energy of the sensor nodes is mainly done for two tasks: sensing and transmitting the information. The second (communication) involves the energy consumed in receiving and transmitting the message. Since the power consumption for sending and receiving packets is constant in all nodes of the system, it focuses only on the consumed energy for sending packets. Therefore, the total energy consumption of n nodes can be expressed as C=∑n=1N∑d=1DwdCn, where n∈1,2,N and Cn=mn,dR+mn,dS denote the energy consumption of n, mn,dR is the number of packets sent by n (as relay node) in the interval d, and mn,dS is the number of packets transmitted from the source of n (as source node).Since the quality of wireless links is usually rapidly changing in WSN, sending data at a constant transmission power over different distances may result in energy savings, but it reduces reliability. Therefore, the power of the sensor nodes should be adjusted according to the link quality of the sensor nodes. Sensor nodes can also transfer data to a high power level in sink node with a single-hop or multihop path to meet QoS requirements. However, the energy of involved sensor nodes in routing can be quickly depleted. It is reasonable to increase the traffic load balance of sensor nodes to improve network lifetime. Therefore, in this study, we consider not only the power consumption of the entire network but also the energy consumption of each of the sensor nodes.This research is based on a greedy approach that has received widespread attention in wireless network routing. The main idea is to greedily select the best node at each step based on evaluation factors. Each node in its vicinity has several neighboring nodes that reach the root node through a number of paths. So, creating one or more multiple paths, each of which leads to the sink, are optimal to transfer information to WSN. Sensor nodes in a path use the save and send approach with the maximum number of allowedM removals. Each node sends not only its own data but also sends information about other nodes.For the following reasons, the greedy approach is chosen as the basic design in the proposed method. First, the greedy approach is a dynamic approach that is compatible with any environment due to its simple topology in WSN. Therefore, this approach provides good flexibility in different physical environments and optimizes the performance of dynamic functions. Second, this approach assumes optimal values for the parameters at each step in order to transfer data. Therefore, parameter values are optimized for the whole network by the combination of several parameters.In the greedy method, a criterion called ETX (expected transfer) is used to indicate the quality of the link between two nodes. For a source node, the ETX path is the sum of the ETX path from the previous node and the ETX link between its next nodes to the sink. ETX of the route is calculated based on the success rate of the route in sending messages and data packets. Since in WSN routing, the energy of the relay nodes is crucial; in this paper, we will also use the energy parameter in the ETX calculation. Hence, in the proposed method, according to relation (1), the channel quality for each node will be equal to the ratio of the number of successful send packets from source node to n and multiplied by the ratio of route energy consumption from destination to the current node versus ratio of packets from n+1 node to multiplied sink in the ratio of the required energy to send packets according to hop distance. This parameter, called eETX (Energy-aware ETX), used to measure transmission quality and will be considered as transmission cost.
(1)eEtx=1/hp∗Et−E/w,n1/bp∗ETX/wn+1,D,(2)ETX=Cn+αpdβ,where h is the number of steps from the source node to the current node, p is the number of sent packets, Et is the initial energy of the nodes that assumed to be constant, b the number of routing responses (beacons) to the sink, α is the power consumption coefficient per pocket, and β is the energy loss coefficient per unit distance. The larger the eETX link, the better the transmission quality of the next node message to the sink than the source to the current node.


### 3.2. Proposed Method

The present research is based on a greedy approach in which the node carrying the packets examines the routing parameters at each step, and accordingly it selects the node that has the best value of the parameters as the next hop. Routing parameters in this study include transmission channel quality between sensor nodes in the network, node power consumption, and residual energy, number of packets sent by node as a relay, number of packets sent by node as the source node, the distance between the two nodes, and the distance of the next node to the sink, which is calculated as the direct distance between the node to the sink. In fact, in the present study, routing wireless sensor networks in addition to the energy level and quality of the communication channel between two sensor nodes are also evaluated the distance between two nodes and sending packets to the sink.In this study, when the sensor node senses a message in the network and needs to send that message to the sink node, it sends the message to the optimal neighbor node based on the mentioned parameters. The optimal neighbor node is selected based on the highest channel quality, the minimum distance to the current node and the sink, and the maximum energy. In other words, the node is selected to transmit the released information on the greedy multichannel path of the network, which is the nearest path; it consumes less power and has higher link quality.In WSN, cluster member nodes must send information to the cluster head node. When cluster member nodes in each cluster surround the cluster head, this means that the distance between the cluster member nodes and the cluster head node is the closest, and the packet transmission distance is the shortest. In fact, when cluster head nodes are almost in the middle of the other nodes of the cluster, their distance from all nodes will be almost the same size and minimum distance. Thus, the transmission of data in the shortest distance requires the least amount of energy. The intracluster distance model is expressed in equation (3).
(3)Dni,nj=xi−xj2+yi−yj2,(4)dncluster=min∑m=1M∑n=1NDni,nj,where xi and xj are the coordinates of the wireless sensor nodes and the sink, respectively, and dncluster is the intracluster distance.In clustering-based protocols, the cluster head node combines the information on the received information and sends it to the sink. In fact, in the cluster head node, a processing step is performed on the data to eliminate incomplete and duplicate information. The remaining information is then sent to the sink as useful information. In the initial protocols, packets were sent from the cluster head node to the sink in a single hop. Such a strategy would waste too much energy on the cluster head node. Therefore, using multihop data transfer is a solution to eliminate this problem, which is used in the proposed method. Cluster nodes use a multihop approach to transmit information. In this paper, the shorter the distance between the cluster node and the sink, the shorter the transmission and consequently the lower energy consumption. The distance model between the threaded node and the sink is expressed in Equation (5).
(5)Dcs=min∑m=1MdCsink,where d_Csink is the direct distance between cluster head node and sink. Since the transmission quality reflects the link quality and energy consumption in the proposed method, eETX denotes the link quality between node n and its neighbor n+1, E is the node current energy, and d (n, n+1) is the distance between two nodes. We present the current and next node, and d (n+1, D) is the distance between the next node and the sink. Hence, as an evaluation function in the proposed method, we solve the opposite optimization relation.
(6)MinZ=∑i=1N∑j=1NDni,nj+dnj,nD−eEtxij−Ej,SubjecttoDn+1,D<=DS,D,E<=Et,n>0,where Z is the evaluation function. In this respect, since the quality of the link, the power consumption for transmitting packets from source node to current node, and the intervals between nodes have different values, so these values cannot be aggregated. Therefore, these values need to be normalized to convert them to values of the interval [0, 1]. By normalizing the values in the mentioned interval, the effect ratio of each parameter is shown on the next node selection. In fact, a node that has the lowest energy consumption from the source node to the current node and its link quality is better than other nodes, and the distance to the sink is less than the other node and generates a higher relative valuation. It will indicate the optimality to choose as the next node.Normalization of data results in mapping values to zero and one and eliminates the negative impact of values with different scales. The well-known normalization relationships in the journals include the Gaussian normalization (Z-score) and the min-max normalization, and in this study, it used the min-max normalization. The min-max normalization relationship is as follows:
(7)min−maxnormalization=xi,j−xminxmax−xmin,where xi and j are the values of each attribute for each sample, and xmin is the smallest value for attribute, and xmax is the largest value for the attribute. The flowchart of the proposed method is shown in Figure 1.Figure 1
Flowchart of the proposed method.


## 3.1. Definition of Network Parameters

In this study, we consider a multihop WSN with a sink node andN wireless sensor. The sink node collects information from the sensor and sends the processing results to the external server. Sensor nodes act as information sources and relays that are used to send data packets. In the proposed method of energy calculation algorithm, packet transmission powers are selected consistently to ensure packet transport at different distances that require different energy consumptions. Hence, the weight (Wd) represents the constant energy consumption when a node transmits a packet at distance l. The energy of the sensor nodes is mainly done for two tasks: sensing and transmitting the information. The second (communication) involves the energy consumed in receiving and transmitting the message. Since the power consumption for sending and receiving packets is constant in all nodes of the system, it focuses only on the consumed energy for sending packets. Therefore, the total energy consumption of n nodes can be expressed as C=∑n=1N∑d=1DwdCn, where n∈1,2,N and Cn=mn,dR+mn,dS denote the energy consumption of n, mn,dR is the number of packets sent by n (as relay node) in the interval d, and mn,dS is the number of packets transmitted from the source of n (as source node).Since the quality of wireless links is usually rapidly changing in WSN, sending data at a constant transmission power over different distances may result in energy savings, but it reduces reliability. Therefore, the power of the sensor nodes should be adjusted according to the link quality of the sensor nodes. Sensor nodes can also transfer data to a high power level in sink node with a single-hop or multihop path to meet QoS requirements. However, the energy of involved sensor nodes in routing can be quickly depleted. It is reasonable to increase the traffic load balance of sensor nodes to improve network lifetime. Therefore, in this study, we consider not only the power consumption of the entire network but also the energy consumption of each of the sensor nodes.This research is based on a greedy approach that has received widespread attention in wireless network routing. The main idea is to greedily select the best node at each step based on evaluation factors. Each node in its vicinity has several neighboring nodes that reach the root node through a number of paths. So, creating one or more multiple paths, each of which leads to the sink, are optimal to transfer information to WSN. Sensor nodes in a path use the save and send approach with the maximum number of allowedM removals. Each node sends not only its own data but also sends information about other nodes.For the following reasons, the greedy approach is chosen as the basic design in the proposed method. First, the greedy approach is a dynamic approach that is compatible with any environment due to its simple topology in WSN. Therefore, this approach provides good flexibility in different physical environments and optimizes the performance of dynamic functions. Second, this approach assumes optimal values for the parameters at each step in order to transfer data. Therefore, parameter values are optimized for the whole network by the combination of several parameters.In the greedy method, a criterion called ETX (expected transfer) is used to indicate the quality of the link between two nodes. For a source node, the ETX path is the sum of the ETX path from the previous node and the ETX link between its next nodes to the sink. ETX of the route is calculated based on the success rate of the route in sending messages and data packets. Since in WSN routing, the energy of the relay nodes is crucial; in this paper, we will also use the energy parameter in the ETX calculation. Hence, in the proposed method, according to relation (1), the channel quality for each node will be equal to the ratio of the number of successful send packets from source node to n and multiplied by the ratio of route energy consumption from destination to the current node versus ratio of packets from n+1 node to multiplied sink in the ratio of the required energy to send packets according to hop distance. This parameter, called eETX (Energy-aware ETX), used to measure transmission quality and will be considered as transmission cost.
(1)eEtx=1/hp∗Et−E/w,n1/bp∗ETX/wn+1,D,(2)ETX=Cn+αpdβ,where h is the number of steps from the source node to the current node, p is the number of sent packets, Et is the initial energy of the nodes that assumed to be constant, b the number of routing responses (beacons) to the sink, α is the power consumption coefficient per pocket, and β is the energy loss coefficient per unit distance. The larger the eETX link, the better the transmission quality of the next node message to the sink than the source to the current node.


## 3.2. Proposed Method

The present research is based on a greedy approach in which the node carrying the packets examines the routing parameters at each step, and accordingly it selects the node that has the best value of the parameters as the next hop. Routing parameters in this study include transmission channel quality between sensor nodes in the network, node power consumption, and residual energy, number of packets sent by node as a relay, number of packets sent by node as the source node, the distance between the two nodes, and the distance of the next node to the sink, which is calculated as the direct distance between the node to the sink. In fact, in the present study, routing wireless sensor networks in addition to the energy level and quality of the communication channel between two sensor nodes are also evaluated the distance between two nodes and sending packets to the sink.In this study, when the sensor node senses a message in the network and needs to send that message to the sink node, it sends the message to the optimal neighbor node based on the mentioned parameters. The optimal neighbor node is selected based on the highest channel quality, the minimum distance to the current node and the sink, and the maximum energy. In other words, the node is selected to transmit the released information on the greedy multichannel path of the network, which is the nearest path; it consumes less power and has higher link quality.In WSN, cluster member nodes must send information to the cluster head node. When cluster member nodes in each cluster surround the cluster head, this means that the distance between the cluster member nodes and the cluster head node is the closest, and the packet transmission distance is the shortest. In fact, when cluster head nodes are almost in the middle of the other nodes of the cluster, their distance from all nodes will be almost the same size and minimum distance. Thus, the transmission of data in the shortest distance requires the least amount of energy. The intracluster distance model is expressed in equation (3).
(3)Dni,nj=xi−xj2+yi−yj2,(4)dncluster=min∑m=1M∑n=1NDni,nj,where xi and xj are the coordinates of the wireless sensor nodes and the sink, respectively, and dncluster is the intracluster distance.In clustering-based protocols, the cluster head node combines the information on the received information and sends it to the sink. In fact, in the cluster head node, a processing step is performed on the data to eliminate incomplete and duplicate information. The remaining information is then sent to the sink as useful information. In the initial protocols, packets were sent from the cluster head node to the sink in a single hop. Such a strategy would waste too much energy on the cluster head node. Therefore, using multihop data transfer is a solution to eliminate this problem, which is used in the proposed method. Cluster nodes use a multihop approach to transmit information. In this paper, the shorter the distance between the cluster node and the sink, the shorter the transmission and consequently the lower energy consumption. The distance model between the threaded node and the sink is expressed in Equation (5).
(5)Dcs=min∑m=1MdCsink,where d_Csink is the direct distance between cluster head node and sink. Since the transmission quality reflects the link quality and energy consumption in the proposed method, eETX denotes the link quality between node n and its neighbor n+1, E is the node current energy, and d (n, n+1) is the distance between two nodes. We present the current and next node, and d (n+1, D) is the distance between the next node and the sink. Hence, as an evaluation function in the proposed method, we solve the opposite optimization relation.
(6)MinZ=∑i=1N∑j=1NDni,nj+dnj,nD−eEtxij−Ej,SubjecttoDn+1,D<=DS,D,E<=Et,n>0,where Z is the evaluation function. In this respect, since the quality of the link, the power consumption for transmitting packets from source node to current node, and the intervals between nodes have different values, so these values cannot be aggregated. Therefore, these values need to be normalized to convert them to values of the interval [0, 1]. By normalizing the values in the mentioned interval, the effect ratio of each parameter is shown on the next node selection. In fact, a node that has the lowest energy consumption from the source node to the current node and its link quality is better than other nodes, and the distance to the sink is less than the other node and generates a higher relative valuation. It will indicate the optimality to choose as the next node.Normalization of data results in mapping values to zero and one and eliminates the negative impact of values with different scales. The well-known normalization relationships in the journals include the Gaussian normalization (Z-score) and the min-max normalization, and in this study, it used the min-max normalization. The min-max normalization relationship is as follows:
(7)min−maxnormalization=xi,j−xminxmax−xmin,where xi and j are the values of each attribute for each sample, and xmin is the smallest value for attribute, and xmax is the largest value for the attribute. The flowchart of the proposed method is shown in Figure 1.Figure 1
Flowchart of the proposed method.


## 4. Implementation of the Proposed Method

In this section, in order to implement the proposed approach, we first simulate the data transfer scenario in the wireless sensor network in order to record the information related to the signals by NS-2 simulator and location data, and we extract the number of send and received packets by network providers, the energy of nodes, the time of sending and receiving data packets, confirmation messages, and other useful information from the network. The proposed scenario is implemented according to the mentioned parameters in Table1. The output implementation of the proposed script is written in two separate files with the extensions ∗ .nam and ∗ .tr. The .nam file is a mobile case for visualizing the network to understand better what is happening on the network. The .tr file is simulated to capture the events step by step and in accordance with the scenario process.Table 1
Network-related parameters.
ValueParameterWirelessChannel typeMac/802_11Standard channel protocol50 packetMaximum size of queue1020 bytesMaximum size of packet10 nodesThe number of nodesAODV, UDPTransmission protocol500×500Dimensions of the simulation environment50 secondsSimulation timeIn Figure2, there is an overview of the initial configuration of the wireless sensor network in the nam file for simulation of the D scenario. Initial configuration of the network is done to obtain location information of nodes. The scenario consists of 15 grids, including one sink and one access point. The information table is formed by receiving local information about the primary energy and energy of each node. In the next step, the stored information of nodes is used to determine the routing parameters for each node that are in relation to the other nodes. Table 2 shows the data about first location of nodes in the proposed network.Figure 2
Initial configuration of the proposed wireless sensor network.Table 2
Information about node primary position in wireless sensor networks.
#nodePosition#nodePosition#nodePosition1(258, 216)6(650, 450)11(215, 30)2(325, 423)7(730, 320)12(300, 300)3(56, 283)8(635, 625)13(735, 130)4(480, 239)9(462, 532)14(140, 430)5(550, 175)10(320, 730)15(250, 400)As shown in Table2, the values of the initial location of the grids are presented in the network, and we will use these values to obtain link quality and distances. Primary energy in the network is assumed to be equal to 10 joules. In the proposed wireless sensor network, the transmitted of information is carried out to determine the amount of consumed energy per network, constant consumption of energy in data transmission, cost of transmitting information between neighbors, set of neighbors on the network, relocations on the network, and others information needed to calculate link quality. Figure 3 shows an overview of the information transmission across the network.Figure 3
Overview of the information transmission in the proposed network.As shown in Figure3, data transmission over the wireless sensor network occurs during a random data transmission scenario to collect the required information in the network. This information is needed to calculate the value of the evaluation function in the proposed greedy method for each node. According to relation (3), we must calculate the distances of nodes from each other and from the destination defined in this scenario as the sink. Then, we calculate the link quality parameter between the current and neighbor links and finally, we calculate the remained energy in the nodes. By calculating the values of the above calculated parameters, we calculate the value of the evaluation function. The maximum value of the evaluation function for each of the nodes in each step is the best choice in the greedy method to send packets of information.Spatial coordinates of nodes can be used to calculate the distance between each node with each other and the distance to the destination node. The distance between the two nodes is calculated by Euclidean relation, and it calculates the direct distance between two nodes. In order to calculate the distance between a node and a target node, we also calculate the direct distance by this relation, which can be said to be an estimate of the actual distance between the other nodes and the target node. Table3, therefore, shows the distance between the nodes and the embedded sink in the grid.Table 3
The distance between nodes.
Node123456789101112131415Sink1Inf218213223295457483556376518191944852441848252218Inf303241335326418370175307408126504185786623213303Inf4265066176756724765192992456961692277194223241426Inf95271263416294516337190277390281900529533550695Inf2932314583686013652801904833759926457326617271293Inf1531762054336053813315104038517483418675263231153Inf3193425805914301906004879988556370672416458176319Inf1963327284675055324467379376175476294368205342196Inf24455928348633825065810518307519516601433580332244Inf70843073035033741911191408299337365605591728559708Inf2835304073729941294126245190280381430467283430283Inf46720611276213485504696277190331190505486730530467Inf666555113914244185169390483510600532338350407206666Inf1145871518478227281375403487446250337372112555114Inf650As shown in Table3, the distances between each node and sink node in the grid is calculated based on the location coordinates and their motion in the simulation.In order to calculate the service quality parameter, we first need to calculate the energy consumption cost per transmission. The cost of energy consumption is actually the average amount of energy consumed per unit based on the number of send messages and the power of packets in sending. The power to send packets in the simulation is assigned in the random weights of nodes. Also, the parameterα, which is considered as the packet transfer constant, is 8 in this study. The parameter α is determined according to the standard of other publications, which is a random number in the interval [1, 10]. Therefore, to calculate the cost of energy consumption, it is sufficient to determine the weight and constant amount of sent packets by multiplying the number of sent packets as the source and the number of packets that a packet plays in the relay. Table 4 shows the cost of packet transfer per node.Table 4
Package transfer cost.
#nodeCost (j)#nodeCost (j)#nodeCost (j)10.069960.0336110.094520.132070.1079120.634530.022880.2280130.667340.190590.4715140.361450.1797100.5317150.6338As shown in Table4, each packet must consume a certain amount of energy, which is called the transfer cost, in order to transfer a packet, depending on the packet transmitting power, the packet transfer constant, and the number of transmitters as the source and as the relay. In order to send data packets to neighbor nodes, each node must consume some energy depending on the number of packets transmitted, the fixed power consumption per packet, and the length of the transmission path. Table 4 shows that the amount of energy has calculated that is required to forward packets from defined nodes in the network to the nearest next hop. Therefore, the values obtained in Table 4 can be used to calculate the residual energy in each step and the link quality.After calculating the cost of energy consumption, one can now calculate the link quality for each node, to calculate the link quality of each node in relation to the other node of the network calculated the parameters: the number of hops traversed from the source to the current node, the number of expected hops left to the destination, the distance between a current node to the source, the distance between next node to sink, residual energy for current and neighbor node, constant energy consumption coefficient for each data transfer, number of packets sent from current node (as the relay node), and the number of packets sent from the current node source. Table5 shows the amount of link quality for each node compared to the other nodes.Table 5
Link quality between nodes.
Node123456789101112131415101.60.42.41.21.20.42221.6222.40.80121.1501.150.7661.911.530.3831.151.531.530.7661.910.3832.30.76630.3321.6601.331.331.331.330.331.660.330.991.331.991.331.9940.4550.3030.9100.150.150.150.450.600.300.300.750.300.300.9151.121.872.240.37300.740.740.371.490.372.242.241.121.492.2461.161.941.550.3870.7700.771.940.381.940.771.551.161.161.5570.3061.221.530.3060.610.6101.841.840.610.611.840.910.611.5380.5210.340.691.040.170.861.0400.170.170.170.521.040.520.1792.172.610.861.741.740.432.610.4300.860.861.300.432.171.30101.842.211.840.730.362.210.730.360.7300.731.470.362.210.73111.871.561.251.871.561.870.930.310.620.6201.871.561.250.31121.941.301.621.940.640.641.300.640.971.940.6400.641.301.30131.830.910.300.301.221.220.911.830.300.301.830.3000.910.30141.141.710.851.430.571.430.280.851.430.570.281.431.1401.71151.470.291.760.291.470.581.760.290.8811.470.580.291.171.470As shown in Table5, the quality function of the links for each node is calculated in relation to the other nodes. The link quality in the proposed method indicates the estimated cost of transferring packets from the next node to the sink. Given that the highest cost in WSN is related to energy consumption, so in fact, it can be said that the link quality estimates the amount of energy needed to transmit packets along the path through other nodes in the network. Obviously, the node with the lowest link quality will consume the least energy with the least number of hops to sink; so, with a greedy look at the issue, such a node is the best option to choose as the next hop, but the remaining node energy issue is also influential.Now, in order to calculate the evaluation function of the proposed method, we need the residual energy in each node. As mentioned, the initial energy of each node is assumed to be 10 joules, which is recorded as residual energies after simulating the network. The residual energy in each node after simulating the proposed network is shown in Table6.Table 6
Residual energy of nodes.
#nodeRemained energy (j)#nodeRemained energy (j)#nodeRemained energy (j)19.09846769.658467119.66957629.69846779.238467129.76974638.99846789.154979139.59846748.29846799.509746149.71846758.698467109.728467159.508467As shown in Table6, the amount of residual energy for each node at each step of the packet transmission is calculated. Calculating the residual energy of the nodes in the wireless sensor network allows us to ensure the balance of energy consumption in the network. Having the amount of residual energy in the nodes prevents forwarding packets to nodes that have less residual energy. In this way, the balance of energy consumption in the network will be observed.Now, after calculating the mentioned parameters, we can calculate the value of the proposed method evaluation function based on relation (3). This value indicates the rate of improvement in each step. These values are updated for each transfer, and the best node for sending information packets has the highest evaluation function at each step. Table 7 shows the value of the evaluation function for each node that sends to other nodes in the same step.Table 7
Value of the evaluation function.
Node12345678910129977810897210377810810210334345355244798137108975655418785665233524132765454111338557544315496396668832106489699734As shown in Table7, the value of the evaluation function for each node is shown to send packets to the other nodes. The value of the evaluation function is selected as a criterion for selecting the next hop node in each step according to the fusion of the parameters distance, link quality, and residual energy. In other words, if the current node is node i in the transmission path between the source node and the sink, the next node to transfer packets will be the node with the highest value of the evaluation function in the related row in Table 7. In other words, in rows i of Table 7, each node that has the highest value will be the next node in transferring information from node i. As an example, Table 8 shows the routing of the best packets forwarding from the node 7 to the sink node.Table 8
Routing best nodes in sending packages from number 7 to sink node.
The best node to send data in step 1 is node 7The best node to send data in step 2 is node 1The best node to send data in step 3 is node 5The best node to send data in step 4 is node 7The best node to send data in step 5 is node 6The best node to send data in step 6 is node 1The best node to send data in step 7 is node 1The best node to send data in step 8 is node 3The best node to send data in step 9 is node 3The best node to send data in step 10 is node 4The best node to send data in step 11 is node 3The best node to send data in step 12 is node 7The best node to send data in step 13 is node 15The best node to send data in step 14 is node 6The best node to send data in step 15 is node 3As shown in Table8, the best nodes are selected to send packets at each step according to the greedy method. As shown in Table 8, some nodes can be seen to have loops, which indicate that there is a deadlock in the route and back to routing. One of the problems of greedy methods is to get caught up in local optimizations, which is also inevitable in the proposed method. As shown in Table 8, in such a case, the proposed method takes a step back and chooses an alternative path, and the same process continues into the sink.


### 4.1. Evaluation of the Recommended Method

The proposed evaluation is designed to provide improvement based on the proposed approach based on the initial problem. In order to evaluate the proposed recommendations, this research measured the metrics of energy consumption and residual energy, network lifetime, message transmission latency, delivery rate, and performance. Figures4–7 illustrate the figures for these criteria.Figure 4
The amount of consumed energy in the network nodes.Figure 5
The amount of remained energy in the network nodes.Figure 6
The network lifetime value.Figure 7
Delay value of sent packets in the network.As shown in Figure5, the energy consumption in the grid nodes is approximately symmetric. Therefore, the energy of some nodes will not expire sooner than others, and the energy consumption will be the same in all nodes. Therefore, the energy consumption of all nodes in the grid is attenuated slowly, indicating the longevity of the grid. Figure 6 illustrates the process of reducing network lifetime.As shown in Figure6, the lifetime of the network is reduced by a gentle slope, which represents the optimal energy consumption of the network. In the proposed method, the data delivery rate has been calculated that is initially low, which increases by increasing communication and tends to have a constant value of about 80%. Also, the network throughput has been considered that is reduced in parts of the scenario due to local optimizations but again continues to rise and increased to approximately 97%. Local optimality is a trap that captures the proposed method in it, but since the evaluation function is composed of several parameters, the local optimal discovered quickly and prevented complete deadlock. Eventually, the delay of data transmission in the proposed method has obtained the summation of end to end delay of nodes in transmission hops. Figure 7 illustrates the packet transmission delay in the network.As shown in Figure7, the packet transmission delay in the network is increasing to a certain threshold with a gentle slope, and then it is increasing as the local optimality increases and finally, the time for information transmission between 15 nodes reaches 450 milliseconds by 650 connections. In the next subsection of this paper, the proposed method will be compared with other existing methods. Figures 8 and 9 show that the proposed methodology is comparable in terms of evaluation criteria to other methods.Figure 8
Comparison of previous methods with proposed methods in terms of the number of messages sent over the network.Figure 9
Comparison of prior methods with the proposed method in terms of rate of delivery data in network.


### 4.2. Comparison of the Suggested Method with Previous Ones

Since routing in WSN is one of the new research topics in the field of wireless networks, researchers have shown great interest in researchers in this area. It should be noted that most of these studies attempt to maximize data delivery rate and network lifetime and minimize packet delivery delays and energy consumption in network energies. Therefore, in this study, we compared the predictions of some previous patterns such as ZAODV, ZAG [12], Standard ZigBee, and NAR [13] in terms of network latency, delivered packages, and delivery rates on the network. To this end, we increase the number of proposals in the network to 50 in order to compare, in equal terms, the proposals with previous ones. Figures 8–10 represent the comparison of the previous procedure with the proposed one.Figure 10
Comparison of previous methods with the proposed method in terms of end-to-end delay messages in the network.As shown in Figures8–10, the proposed method works better in terms of message transmission delay, the number of sent messages, and rate of data delivery in the network than previous procedures.


## 4.1. Evaluation of the Recommended Method

The proposed evaluation is designed to provide improvement based on the proposed approach based on the initial problem. In order to evaluate the proposed recommendations, this research measured the metrics of energy consumption and residual energy, network lifetime, message transmission latency, delivery rate, and performance. Figures4–7 illustrate the figures for these criteria.Figure 4
The amount of consumed energy in the network nodes.Figure 5
The amount of remained energy in the network nodes.Figure 6
The network lifetime value.Figure 7
Delay value of sent packets in the network.As shown in Figure5, the energy consumption in the grid nodes is approximately symmetric. Therefore, the energy of some nodes will not expire sooner than others, and the energy consumption will be the same in all nodes. Therefore, the energy consumption of all nodes in the grid is attenuated slowly, indicating the longevity of the grid. Figure 6 illustrates the process of reducing network lifetime.As shown in Figure6, the lifetime of the network is reduced by a gentle slope, which represents the optimal energy consumption of the network. In the proposed method, the data delivery rate has been calculated that is initially low, which increases by increasing communication and tends to have a constant value of about 80%. Also, the network throughput has been considered that is reduced in parts of the scenario due to local optimizations but again continues to rise and increased to approximately 97%. Local optimality is a trap that captures the proposed method in it, but since the evaluation function is composed of several parameters, the local optimal discovered quickly and prevented complete deadlock. Eventually, the delay of data transmission in the proposed method has obtained the summation of end to end delay of nodes in transmission hops. Figure 7 illustrates the packet transmission delay in the network.As shown in Figure7, the packet transmission delay in the network is increasing to a certain threshold with a gentle slope, and then it is increasing as the local optimality increases and finally, the time for information transmission between 15 nodes reaches 450 milliseconds by 650 connections. In the next subsection of this paper, the proposed method will be compared with other existing methods. Figures 8 and 9 show that the proposed methodology is comparable in terms of evaluation criteria to other methods.Figure 8
Comparison of previous methods with proposed methods in terms of the number of messages sent over the network.Figure 9
Comparison of prior methods with the proposed method in terms of rate of delivery data in network.


## 4.2. Comparison of the Suggested Method with Previous Ones

Since routing in WSN is one of the new research topics in the field of wireless networks, researchers have shown great interest in researchers in this area. It should be noted that most of these studies attempt to maximize data delivery rate and network lifetime and minimize packet delivery delays and energy consumption in network energies. Therefore, in this study, we compared the predictions of some previous patterns such as ZAODV, ZAG [12], Standard ZigBee, and NAR [13] in terms of network latency, delivered packages, and delivery rates on the network. To this end, we increase the number of proposals in the network to 50 in order to compare, in equal terms, the proposals with previous ones. Figures 8–10 represent the comparison of the previous procedure with the proposed one.Figure 10
Comparison of previous methods with the proposed method in terms of end-to-end delay messages in the network.As shown in Figures8–10, the proposed method works better in terms of message transmission delay, the number of sent messages, and rate of data delivery in the network than previous procedures.


## 5. Discussion

As noted in this study, a routing approach is presented based on finding the shortest random path by greedy routing in wireless sensor networks. The greedy approach tries to find the best way to send data by sending packets from source to destination according to the nature of local search at every step. In order to implement this approach in the network, the proposed approach is achieved to optimize results by combining the essential parameters of information transmission. The only disadvantage of this is the local maximum stuck where due to the greedy property, selected node in one step may have locally maximized parameters, and with the progress of this path, the value of the parameters will not maximize or the route will end in deadlock. In that case, there is a need to go back and run away from the local maximum. This problem can only cause delays in sending information and, by back-propagation, guaranteed to find the optimal global route.According to the results chart, it can be seen that the consumed energy in the network is almost identical in terms of finding the shortest path to send a packet of information. Balanced use of energy in nodes causes all energy to remain at the same level and prevents interruption when one or more energy is lost before the rest. This increases the lifetime of the network, and given the energy conservation of the network, information transmission will take a long time according to the proposed approach.Another result of the proposed method is the data transmission rate over the network, which can be seen with respect to the delivery rate diagram. This parameter initially has a small amount which increases with time and increases with the number of transfers in the network. The network will expand to a fixed amount of about 80%. This graph indicates that, at first, the data may not be sent correctly to the destination due to the complete lack of knowledge of the network but due to the metaheuristic nature of the suggestions, and the transfer of this recognition is enhanced. And transferring information to the sink would be more accurate.On the other hand, the delay parameter in the grid is increased to a certain threshold with a gentle slope according to the delay graph. After reaching the threshold due to overwhelming transmission on the network and due to the local optimum available on the route, it will increase with more slopes. The overwhelming delay in sending information packets of the network can be cited as the main weakness of the proposed method. On the other hand, according to the comparison chart in the proposed method, it can be seen that, with the increase of delay in local maxima, the proposed method has still less delay than other available methods in this field.Another parameter that can be argued in this context is the permutation parameter of the network. This parameter is set as messages sent to the destination network. According to the diagrams, we can see that in two parts of the diagram, due to the local optimizations in the path, the slope of diagrams are increasing and then decreasing. As noted, this diagram terminates in the deadlock path based on local optimizations and again attempts to return to the optimal path, which reduces the permutation at points of the diagram.


## 6. Conclusions

With the expansion of communication networks, WSN is expanding rapidly due to its scalability and use in many cases and environments. The extend of WSN and the size of this network have raised challenges, and finding the shortest path is one of the most fundamental challenges. WSN energy constraints can cause packet routing problems that affect overall network performance. Therefore, it is necessary to provide optimal solutions to find the shortest path in the network for data transmission. This problem cannot solve by deterministic search methods. Recently, evolutionary and metaheuristic algorithms are able to find real-time optimal or near-optimal solutions. This article introduces a greedy method to find the shortest random path in WSN. The greedy local search method is faster than other existing methods and reaches the optimal solution in solving some problems. The simulation results show that in the proposed method, the energy consumption of nodes is almost symmetric, and the network lifetime is reduced with a gentle slope. Also, the packet transmission delay in the network increases in a balanced manner, and finally, the data transfer time between 15 nodes with 650 connections reaches 450 milliseconds. In addition, network deadlocks have been reduced due to local optimizations, and the data delivery rate has increased by approximately 97%. It also shows better performance in terms of evaluation criteria compared to other previous methods.The dynamic and widespread nature of wireless networks has revealed the need for routing adaptation changes in these types of networks. Traditional routing routines and finds the shortest route through static routing but cannot supply users’ needs due to the enormous amount of nodes in the network and the dynamic topology of these types of networks. Therefore, other metaheuristic techniques such as cuckoo optimization algorithm, wall optimization algorithm, and other optimization algorithms can be used to overcome these challenges that represent as a recommendation for future work to optimize the results of this study.



---

*Source: 6664669-2021-04-14.xml*