# Research on Wireless Sensor Network Positioning Based on Genetic Algorithm

Authors: Jing Zhang; Yajing Hu; Hongliang Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

For smart city wireless sensing network construction needs, a network positioning algorithm based on genetic algorithm is proposed. The genetic algorithm uses a real number encoding, and the positioning model is constructed by analyzing the communication constraint between unknown nodes and a small amount of anchor nodes and constructs the positioning model, and the model is solved. The results show that when the ranging error is 50%, the positioning error is only increased by approximately 15% compared to the nonranging error. In a more harsh environment, if the ranging error is equal to the node wireless range, the ranging error is 100%, and the positioning error and the positioning ratio are not significantly changed. The scheme obtained by this algorithm can be well approarded with an ideal limit. In the case where the sensor node is given, the algorithm can obtain the maximum coverage.


---

## Body

## 1. Introduction

In the past 30 years since the reform and opening up, the prototypes of rural development have basically formed, and the urban basic construction has received more attention from the urban construction industry in my country. With the vigorous development of my country’s infrastructure construction, the measurement of the quality of facilities and technology has become higher and higher, and the dynamic facility environment has also put forward higher requirements for the real-time performance of the environmental monitoring system. In urban infrastructure, traditional urban facilities have environmental factors such as soil, pressure, explosions, fire, and earthquakes, which can cause safety hazards, threatening the property and personal safety of the people. For example, in September 2012, a large area of roads in Xi’an, Shaanxi Province, collapsed causing cement tank cars to fall into the large pit, resulting in a serious natural gas pipeline rupture accident. In July 2014, the junction of Xinye Road and Fuchun Road, Hangzhou, due to the nearby river, collapsed, and river water was inverted, bringing great inconvenience to people’s travel. Globally, almost every year, a large number of urban infrastructures not only cause waste and environmental pollution but also interfere with people’s normal life, but even threaten people’s lives and property safety. On the other hand, traditional urban infrastructure monitoring is mostly manually monitored, and this means requires test personnel record, analysis and classification measurements, and excessive time spent. In addition, the monitoring method is often accompanied by the loss and mistiness of measurement data, high monitoring costs, and lower transmission efficiency. This will inevitably not meet real-time communication and feedback requests in infrastructure environments.Urban infrastructure construction has the characteristics of complex structure, frequent disasters, risk aggregation, and function, which have brought serious tests on urban infrastructure monitoring. It can be seen that how to establish a real-time, effective urban infrastructure monitoring system, timely and accurate prediction of the safety hazards in the infrastructure, avoiding the occurrence of the above accidents, is one of the major challenges of urban infrastructure construction. With the rapid development of intelligent information technology, people get information in the way. As an important representative of the IoT, wireless sensor network (WSN) is a wireless network configured by a node group that is self-organized and multi-hop-transmitted, which can process and transmit environmental information in the monitoring area. At present, the wireless sensor network has set off a new research boom in the world. Through wireless sensor networks, people can make more convenience of the perception and acquisition of objective world information, further enhancing human exploration of the world’s ability. At present, the wireless sensor network has been widely used in military, environmental monitoring, traffic management, intelligent home, and other fields [1].


## 2. Literature Review

Wireless sensor networks can collect valuable raw data in a realistic environment, and many of the data information is dependent on geographic location information. Therefore, positioning is an important technique for wireless sensing network and has obtained extensive attention and research interest in the academic circles and research in the domestic and foreign. Due to the advancement of information technology, researchers have continuously improved urban infrastructure monitoring systems through various ways, and the urban security levels have greatly improved.In recent years, some common smart city infrastructure, such as urban transportation monitoring system, urban environmental monitoring system, and urban waste management system, gradually applied wireless sensor network to the system’s construction, truly real-time accurate science management. Rady et al. installed a large number of sensors in the Fuhu Bridge on the Beijing-Hangzhou Grand Canal, which constitutes the largest wireless sensor network detection system in the world through the sensor node and detects all kinds of information on the bridge and use wireless sensing network [2]. “Pulse” large bridge. Xiao et al. have developed a set of smart city buildings [3]. The building is an event-driven architecture that can be used to monitor the management and collaboration of heterogeneous sensors in public spaces. Experimenting on the test bench of the subway scene, the results show that the proposed building can enhance the detection of abnormal events, simplify the operator’s task, and ensure the communication between the passengers in an emergency. Bhola et al. proposed an innovative mesh network architecture [4]. This structure allows WSN to collect environmental information more efficiently. In terms of future smart city concepts, it will have new technologies related to the Internet of Things to optimize environmental monitoring methods under smart cities. According to Keswani and Bhaskar for urban environmental pollution, two integer linear planning formulas based on actual pollutant proliferation models are proposed to handle minimal costs for air pollution monitoring WSN deployment [5]. They analyzed the model to actual data (i.e., Nordoham City Street Lights) and have got some effective WSN deployment to conduct air pollution monitoring. Niknamian proposed the urban waste management system based on the Internet of Things [6]. The system can confirm the monitoring of the garbage bin through the web page, and the level of garbage available in the trash. This page displays the tag level of the trash and displays the garbage level collected in the trash to operate it. The system optimizes the garbage management mechanism of smart cities. Niknamian proposed a novel intelligent visual sensor for simultaneous posture estimation [6]. By enhancing tracking of vehicle attitude, it is possible to better estimate the trajectory of the vehicle, which is well solved multivehicle detection and tracking problems in smart urban traffic monitoring applications. According to Talib, deployment depends on the close resource monitoring through large-scale urban perception and designs three different atomization architectures, which will be close to sex and clouds in a valuable filtration standard. Communication is combined [7]. The results show that these three architectures can correctly identify 73% to 100% false location statement. The British Cambridge laboratory first designed and developed an Active Badge indoor positioning system. The basic principle was to communicate and position between sensor nodes to communicate and position. The American Institute of Technology (MIT) research team, in the indoor positioning, combines fingerprint recognition and inertial sensors to achieve high precision positioning. Muruganantham and El-Ocla deploy sensor nodes in the monitoring area and use radio imaging positioning techniques to track targets. The location of the target is rendered by the target motion and the received signal strength fluctuation [8].


## 3. Wireless Sensor Network Node Positioning Algorithm Based on Genetic Algorithm

The wireless sensor network positioning algorithm based on genetic algorithm is to establish a positioning optimization model of the unknown node position as the parameter by analyzing the communication constraint between unknown nodes and a small amount of anchor node. Estimation is unknown for unknown nodes.The wireless sensor network has a number of nodes, wide distribution area, and more communication. The establishment of the positioning optimization model is a multiobjective multiconstraint nonlinear equation, and the genetic algorithm is a more mature evolutionary algorithm. There are simple application conditions and strong search capability, especially suitable for multiobjective, multiconstraint solution, so it is very suitable for the wireless sensor network node positioning optimization model. The node positioning problem description, node communication constraint, positioning optimization model, and genetic positioning algorithm are described in the following.


### 3.1. Positioning Problem Description

This paper adopts the vectorX=x1,x2,⋯,xM,yM,xM+1,yM+1,⋯xN,yNm≥1,n≥M+1 to simulate the initial position of the sensor node of the network topology area, where xi,yii=1,2,n is the abscissa and ordinate of the ith node and i is a unique identifier of the node in the network. Assuming that the first m node X=x1,x2,⋯,xM,yM is known, that is, the position of the anchor node, the post-nm node X=xM+1,yM+1,⋯xN,yN is the unknown node position of the pending node, and the positioning problem evolves into the coordinates known to the M node, asking them the coordinates of N−m unknown points of communication constraints [9, 10].


### 3.2. Node Communication Constraint

Each sensor node includes a radio frequency transmitter and receiver of a radio wave. The effective radius of the wireless connection isR (i.e., the node wireless range), the node wireless propagation model is the amphotericity of the radius of radius R. Circle model. If the distance between the two sensor network nodes is less than or equal to its wireless range R, the two nodes are regarded as communication. This article assumes that anchor nodes and unknown nodes are exactly the same on the hardware configuration. As shown in Figure 1(a), X1 and X2 are unknown nodes and Ai is an anchor node, and when the nodes X and X2 are in this circle, it is considered that the anchor node Ai and the unknown nodes X1 and X2 can communicate with each other. Think
(1)Ai−Xj≤R,j=1,2.Figure 1
Wireless propagation model of a sensor node.
(a)(b)Figure1(b) illustrates how to estimate the distance to an unknown node through the node wireless propagation model. The anchor node Ai sends radio frequency waves around it, assuming that the unknown nodes X1 and X2 can communicate with it. The approximate distance D1 and D2, of the anchor node Ai to the unknown nodes X1 and X2, is estimated by calculating the power loss based on the number of radio power received and the initial transmission power
(2)Ai−Xj≈dj,j=1,2.


### 3.3. Positioning Optimization Model

There is ann node in the WSN as shown in the WSN, where the first M is an anchor node, and then, N−M is an unknown node; the wireless sensor network node positioning problem can be summarized as known anchor node Ai and anchor node communication constraints with unknown nodes Xj and both Dij, looking for suitable unknown node positions, so that Ai−Xj=dij. However, due to the existence of ranging error, the problem is actually summarized to solve the
(3)min∑Ai−Xj−dij.Among them,Ai is an anchor node with communication constraints with Xj. This transforms the node positioning problem into model optimization, that is, the optimal solution of equation (3) is an estimate of unknown nodes [11, 12].


### 3.4. Genetic Location Algorithm

This paper increases the convergence speed of the genetic algorithm by increasing the positioning optimization model constraint conditions, setting various parameters such as genetic algorithms to accelerate the convergence speed of the genetic algorithm, and improving the efficiency of an algorithm.(1)
Constraint conditions for positioning optimization modelsIt is assumed that the unknown nodeXj and 3 anchor nodes can be communicated (with an anchor node which is Ai (i=1,2,3)), respectively, the communication radius is R, and the unknown node must be in all Ai (i=1,2,3) central, a square of a square with a side length of 2R. The coordinates of Ai are known. If 123 represents the coordinates of the Ai, the coordinates of the three square intersecting public rectangular regions can be described as
(4)r1=aimin+R,r2=aimax−R,r3=bimin+R,r4=bimax−R.Among them,R1 is the rectangular right boundary, R2 is the rectangular left boundary, and R3 and R4 are rectangular on the boundary and the lower boundary. That is, for unknown nodes Xjxi,yi,
(5)r2≤xj≤r1,r4≤yj≤r3.Based on the constraint ofXj in equation (5), the genetic algorithm in this paper randomly generates pop positions xi,yi as the initial population, where j=1,2⋯Pop [13–15].
(2)
Adaptive function settings for genetic positioning algorithmsAccording to the value of the parameters in formula (3), the adaptation function in the genetic algorithm is
(6)fx,y=∑i=1kx−ai2+y−bi2−di2,wherex,y is the coordinate of the node and ai,bi and Di are anchor node coordinates and distances that can communicate with them.
(3)
Individual encoding of genetic positioning algorithm is a large number of wireless sensor network nodes, and the amount of calculation is large. Considering that binary coding cannot directly reflect the individual structure, and the binary length is long, accounting for large memory, the positioning algorithm in this article is code type genetic algorithm, because of the real number encoding, easy operation, and transformation(4)
Genetic positioning operator design genetic operator mainly includes selection, crossing, and variation operations. The selection operation adopts the adaptive gambling selection method; the cross-adopted multipoint intersection, that is, theX-axis parameters and the Y-axis parameters, corresponds to cross; the variation operation selects the discrete single-point variant mode(5)
Genetic positioning algorithm termination determination when the number of iterations reaches a predetermined number, or when the maturity of the group satisfies certain conditions, the iteration is stopped [16–18]


## 3.1. Positioning Problem Description

This paper adopts the vectorX=x1,x2,⋯,xM,yM,xM+1,yM+1,⋯xN,yNm≥1,n≥M+1 to simulate the initial position of the sensor node of the network topology area, where xi,yii=1,2,n is the abscissa and ordinate of the ith node and i is a unique identifier of the node in the network. Assuming that the first m node X=x1,x2,⋯,xM,yM is known, that is, the position of the anchor node, the post-nm node X=xM+1,yM+1,⋯xN,yN is the unknown node position of the pending node, and the positioning problem evolves into the coordinates known to the M node, asking them the coordinates of N−m unknown points of communication constraints [9, 10].


## 3.2. Node Communication Constraint

Each sensor node includes a radio frequency transmitter and receiver of a radio wave. The effective radius of the wireless connection isR (i.e., the node wireless range), the node wireless propagation model is the amphotericity of the radius of radius R. Circle model. If the distance between the two sensor network nodes is less than or equal to its wireless range R, the two nodes are regarded as communication. This article assumes that anchor nodes and unknown nodes are exactly the same on the hardware configuration. As shown in Figure 1(a), X1 and X2 are unknown nodes and Ai is an anchor node, and when the nodes X and X2 are in this circle, it is considered that the anchor node Ai and the unknown nodes X1 and X2 can communicate with each other. Think
(1)Ai−Xj≤R,j=1,2.Figure 1
Wireless propagation model of a sensor node.
(a)(b)Figure1(b) illustrates how to estimate the distance to an unknown node through the node wireless propagation model. The anchor node Ai sends radio frequency waves around it, assuming that the unknown nodes X1 and X2 can communicate with it. The approximate distance D1 and D2, of the anchor node Ai to the unknown nodes X1 and X2, is estimated by calculating the power loss based on the number of radio power received and the initial transmission power
(2)Ai−Xj≈dj,j=1,2.


## 3.3. Positioning Optimization Model

There is ann node in the WSN as shown in the WSN, where the first M is an anchor node, and then, N−M is an unknown node; the wireless sensor network node positioning problem can be summarized as known anchor node Ai and anchor node communication constraints with unknown nodes Xj and both Dij, looking for suitable unknown node positions, so that Ai−Xj=dij. However, due to the existence of ranging error, the problem is actually summarized to solve the
(3)min∑Ai−Xj−dij.Among them,Ai is an anchor node with communication constraints with Xj. This transforms the node positioning problem into model optimization, that is, the optimal solution of equation (3) is an estimate of unknown nodes [11, 12].


## 3.4. Genetic Location Algorithm

This paper increases the convergence speed of the genetic algorithm by increasing the positioning optimization model constraint conditions, setting various parameters such as genetic algorithms to accelerate the convergence speed of the genetic algorithm, and improving the efficiency of an algorithm.(1)
Constraint conditions for positioning optimization modelsIt is assumed that the unknown nodeXj and 3 anchor nodes can be communicated (with an anchor node which is Ai (i=1,2,3)), respectively, the communication radius is R, and the unknown node must be in all Ai (i=1,2,3) central, a square of a square with a side length of 2R. The coordinates of Ai are known. If 123 represents the coordinates of the Ai, the coordinates of the three square intersecting public rectangular regions can be described as
(4)r1=aimin+R,r2=aimax−R,r3=bimin+R,r4=bimax−R.Among them,R1 is the rectangular right boundary, R2 is the rectangular left boundary, and R3 and R4 are rectangular on the boundary and the lower boundary. That is, for unknown nodes Xjxi,yi,
(5)r2≤xj≤r1,r4≤yj≤r3.Based on the constraint ofXj in equation (5), the genetic algorithm in this paper randomly generates pop positions xi,yi as the initial population, where j=1,2⋯Pop [13–15].
(2)
Adaptive function settings for genetic positioning algorithmsAccording to the value of the parameters in formula (3), the adaptation function in the genetic algorithm is
(6)fx,y=∑i=1kx−ai2+y−bi2−di2,wherex,y is the coordinate of the node and ai,bi and Di are anchor node coordinates and distances that can communicate with them.
(3)
Individual encoding of genetic positioning algorithm is a large number of wireless sensor network nodes, and the amount of calculation is large. Considering that binary coding cannot directly reflect the individual structure, and the binary length is long, accounting for large memory, the positioning algorithm in this article is code type genetic algorithm, because of the real number encoding, easy operation, and transformation(4)
Genetic positioning operator design genetic operator mainly includes selection, crossing, and variation operations. The selection operation adopts the adaptive gambling selection method; the cross-adopted multipoint intersection, that is, theX-axis parameters and the Y-axis parameters, corresponds to cross; the variation operation selects the discrete single-point variant mode(5)
Genetic positioning algorithm termination determination when the number of iterations reaches a predetermined number, or when the maturity of the group satisfies certain conditions, the iteration is stopped [16–18]


## 4. System Parameters and Algorithm Performance Parameters

This paper uses important system parameters in WSN and selects the position error and the positioning ratio as the algorithm performance index parameters. The performance of the algorithm can be clearly expressed by analyzing the effects of different system parameters on the performance of an algorithm.


### 4.1. System Parameters

(1)
Anchor node ratioλ. The number of anchors in the entire network accounts for the ratio of the total number of all nodes(2)
Anchor node densityρ. Represents an anchor node number of anchor nodes within the wireless range of each unknown node(3)
Network interconnectionδ. The number of nodes in each unknown node wireless range(4)
Ranging errorξ. Due to the influence of various environmental factors and the inaccurate signal propagation model, the error between the measured value and the true value of the measured distance of the node wireless communication module measures the distance. The ratio of the error value and the node wireless range is used. For example, the ranging error of 20% indicates 20% of the ranging error equivalent to the node wireless range R [19, 20]


### 4.2. Performance Parameters

(1)
Positioning errorε. The estimated actual position from a size range with respect to the wireless node. The formula is(7)ε=∑j−M+1Npj−p^jn′R,0≤n′≤N−M,wherej∈Mn, Mn=m+1,⋯,n∣m≥1,n≥m+1, n′ represents the number of positionable nodes, pj indicates the estimation position of the unknown node Xj, and p^j denotes an unknown node of the actual location of Xj(2)
Position ratioη. Indicates that the positionable node accounts for the ratio of the number of unknown nodes, i.e.,(8)η=n′N−M×100%


## 4.1. System Parameters

(1)
Anchor node ratioλ. The number of anchors in the entire network accounts for the ratio of the total number of all nodes(2)
Anchor node densityρ. Represents an anchor node number of anchor nodes within the wireless range of each unknown node(3)
Network interconnectionδ. The number of nodes in each unknown node wireless range(4)
Ranging errorξ. Due to the influence of various environmental factors and the inaccurate signal propagation model, the error between the measured value and the true value of the measured distance of the node wireless communication module measures the distance. The ratio of the error value and the node wireless range is used. For example, the ranging error of 20% indicates 20% of the ranging error equivalent to the node wireless range R [19, 20]


## 4.2. Performance Parameters

(1)
Positioning errorε. The estimated actual position from a size range with respect to the wireless node. The formula is(7)ε=∑j−M+1Npj−p^jn′R,0≤n′≤N−M,wherej∈Mn, Mn=m+1,⋯,n∣m≥1,n≥m+1, n′ represents the number of positionable nodes, pj indicates the estimation position of the unknown node Xj, and p^j denotes an unknown node of the actual location of Xj(2)
Position ratioη. Indicates that the positionable node accounts for the ratio of the number of unknown nodes, i.e.,(8)η=n′N−M×100%


## 5. Simulation

For the performance of the test algorithm, we conducted a series of simulation experiments. The content of this chapter mainly introduces the simulation environment and analyzes the results.


### 5.1. Simulation Environment

The simulation environment of the WSN in this article consists of 400 nodes, and the node is randomly distributed in the range of10R×10RM2 and assumes that all nodes are located in the first quadrant, where r is a node wireless range. To simplify the calculation, the wireless range R is 10 meters in the experiment.Due to the random distribution of the sensor node, the estimation of the anchor distance has a certain random error, and the positioning results derived by the experiment have randomness that cannot be ignored. In order to obtain an accurate experimental result, the statistical method is used to simulate the algorithm. That is, 500 experiments are repeated in the same network environment; each experimentally unknown node will be renewed in the monitoring area, and statistics of 500 positional experiments [21].


### 5.2. Analysis of Experiment Results

(1)
Influence of anchor node density. Unlike an increase in anchor nodes, this experiment increases the network node density by increasing an anchor node communication radius. Figure2 analyzes the relationship between anchor node density and algorithm performance. With the increase in the intercourse of the anchor node in the network, the positioning error is gradually decreased, and the positioning ratio has gradually increased. As can be seen from the figure, even if the anchor node density is only 2, the positioning error is less than 30%, and the positioning ratio is approximately equal to 70%, and the present algorithm is suitable for an anchor node sparse(2)
Influence of network communication. From Figure3, increasing network connectivity can improve algorithm performance. Since network communication includes communication between anchor nodes and unknown nodes, the anchor node is related to unknown nodes. There is no effect, just communicating between unknown nodes and anchor nodes. Therefore, when the simulation changes the network communication change, the anchor node density will increase, so the improvement in algorithm performance in Figure 3 is caused by an increase in the density of the anchor node, not because of network communication variety(3)
Effect of ranging error. For a positioning algorithm that requires a rough estimate between unknown nodes and anchor nodes, the sensitivity of the ranging error is a major factor for the evaluation algorithm. As can be seen from Figure4, when the ranging error is 50%, the positioning error is only about 15% higher than when the ranging error is not ranging. In a more harsh environment, if the ranging error is equal to the node wireless range, the ranging error is 100%, and the positioning error and the positioning ratio are not significantly changed. Therefore, the ranging error has little effect on the performance of the algorithm, making the algorithm have good anti-interference in a complex environment [22]Figure 2
ξ=0.05 and λ=0.15.Figure 3
ξ=0.05 and λ=0.15.Figure 4
ξ=0.05 and λ=0.15.


## 5.1. Simulation Environment

The simulation environment of the WSN in this article consists of 400 nodes, and the node is randomly distributed in the range of10R×10RM2 and assumes that all nodes are located in the first quadrant, where r is a node wireless range. To simplify the calculation, the wireless range R is 10 meters in the experiment.Due to the random distribution of the sensor node, the estimation of the anchor distance has a certain random error, and the positioning results derived by the experiment have randomness that cannot be ignored. In order to obtain an accurate experimental result, the statistical method is used to simulate the algorithm. That is, 500 experiments are repeated in the same network environment; each experimentally unknown node will be renewed in the monitoring area, and statistics of 500 positional experiments [21].


## 5.2. Analysis of Experiment Results

(1)
Influence of anchor node density. Unlike an increase in anchor nodes, this experiment increases the network node density by increasing an anchor node communication radius. Figure2 analyzes the relationship between anchor node density and algorithm performance. With the increase in the intercourse of the anchor node in the network, the positioning error is gradually decreased, and the positioning ratio has gradually increased. As can be seen from the figure, even if the anchor node density is only 2, the positioning error is less than 30%, and the positioning ratio is approximately equal to 70%, and the present algorithm is suitable for an anchor node sparse(2)
Influence of network communication. From Figure3, increasing network connectivity can improve algorithm performance. Since network communication includes communication between anchor nodes and unknown nodes, the anchor node is related to unknown nodes. There is no effect, just communicating between unknown nodes and anchor nodes. Therefore, when the simulation changes the network communication change, the anchor node density will increase, so the improvement in algorithm performance in Figure 3 is caused by an increase in the density of the anchor node, not because of network communication variety(3)
Effect of ranging error. For a positioning algorithm that requires a rough estimate between unknown nodes and anchor nodes, the sensitivity of the ranging error is a major factor for the evaluation algorithm. As can be seen from Figure4, when the ranging error is 50%, the positioning error is only about 15% higher than when the ranging error is not ranging. In a more harsh environment, if the ranging error is equal to the node wireless range, the ranging error is 100%, and the positioning error and the positioning ratio are not significantly changed. Therefore, the ranging error has little effect on the performance of the algorithm, making the algorithm have good anti-interference in a complex environment [22]Figure 2
ξ=0.05 and λ=0.15.Figure 3
ξ=0.05 and λ=0.15.Figure 4
ξ=0.05 and λ=0.15.


## 6. Conclusion

This paper is based on the construction of smart urban wireless sensing network as a background and proposes a network positioning algorithm based on genetic algorithm. The network positioning model is established. It is used to find the best solution through the genetic algorithm to implement the two anchor nodes to calculate the position of the unknown node. Simulation experiments show that the algorithm significantly increases the positioning accuracy and positioning coverage ratio compared to the traditional positioning algorithm.Wireless sensor networks are frontier research topics belonging to multilearning cross-edge research. The progress of technology in the relevant field has promoted the continuous development of wireless sensor network positioning techniques. After each emerging technology has its shortcomings, only constantly improved, can we let technology mature. Wireless sensor network target positioning accuracy. The algorithm of this paper compares the accuracy of the model, and the parameters of the ranging model may be changed for different environments. In terms of wireless sensor network target positioning coverage, the unknown nodes of it will be upgraded into a virtual anchor node to participate in the next round of positioning, further increasing the positioning coverage.



---

*Source: 3996401-2021-11-16.xml*