# EARP: Extended Area Multihop Node Localization Algorithm for Anisotropic Wireless Sensor Networks

Authors: Yinghui Meng; Yuewen Chen; Qiuwen Zhang; Erlin Tian
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Localization is one of the essential problems in the Internet of Things (IoT) and other wireless sensor applications. Most traditional range-free localization algorithms ignore the anisotropy factors, which are frequently observed in wireless sensor networks (WSNs) and result in low positioning precision. To mitigate the impact of anisotropy on localization, this paper proposes an extended area multihop node localization method. The proposed method classifies and discusses the boundaries of the concave area within the communication range of the node and then uses the maximum split communication distance of the node to identify and mark the boundary of the concave area. When the shortest communication path between the nodes is affected by the concave area, the boundary of the concave area is expanded to obtain the new shortest communication path, and the node distance is obtained by comparing the changes in the communication path. After a large number of simulation tests, it is shown that the calculation accuracy of this scheme is better than that of similar modern mainstream localization algorithms.


---

## Body

## 1. Introduction

Wireless sensor network is a kind of self-organizing network deployed in a controlled area [1]. It is widely used in intrusion detection, industrial automation, intelligent building, and other fields [2]. In any field, as long as the wireless sensor network is associated with the application, its node location will play an immeasurable role [3]. The wireless sensor network has realized rapid deployment, convenient networking, and low-cost data collection and has broad application prospects [4]. However, in most applications and the design of sensor network topology control, routing, and other core technologies, the location information of the nodes is crucial.Wireless sensor network nodes are limited by cost and energy consumption, so it is impossible to assemble localization modules for all nodes [5]. Therefore, sensor network nodes must determine their own locations according to the known nodes (beacon nodes) and the connection information between nodes, that is, sensor network node localization [6]. The existing localization technology can be divided into range-free localization method and range-based localization method according to whether additional physical ranging technology is required in the localization process [7].The range-based localization method uses technologies such as Received Signal Strength Indication (RSSI), Time of Arriva (TOA), Time Different of Arrival (TDOA), and Angle of Arrival (AOA), obtains the location measurement according to the localization geometric relationship [8], and then calculates the position (coordinate) information. Although the range-based localization method can calculate the location of nodes through the absolute distance between nodes with relatively high accuracy [9], it will produce higher hardware cost and higher energy consumption in a large area. However, the range-free localization method is free of hardware support, has the characteristics of low cost and low power consumption, and can better adapt to the application requirements of resource-constrained wireless sensor networks [10]. The range-free localization method does not directly measure the distance (or azimuth) but, by estimating the Euclidean distance between nodes or determining the possible region containing the unknown nodes, determines the location of the unknown nodes [11]. Classic range-free localization methods include Distance Vector-HOP (DV-HOP) algorithm, centroid algorithm, convex optimization algorithm, and Multidimensional Scaling-MAP (MDS-MAP) algorithm [12].The main contributions of this paper can be summarized into the following three points: (1) In the anisotropic sensor network, the concave area boundary within the communication range of the node is classified; the concept of split communication is proposed and summarizes three conditions for split communication, which provides the necessary conditions for the recognition of the concave area. (2) We analyze the split communication between nodes and use the maximum split communication distance to identify and mark the concave area boundary node. (3) For the nodes whose communication is affected by the concave area, an extended concave area node ranging method is designed to obtain more accurate node spacing information.


## 2. Related Work

The application of wireless sensor network is closely related to the real environment [13], so relevant research should fully consider the influence of the real environment on the research [14]. In practical applications, due to the randomness of sensor node deployment [15], the existence of large obstacles in the communication area, and the instability of communication signals between nodes, the node deployment area forms a concave area [16]. The communication ability of sensor nodes is limited, and the communication between nodes is usually carried out through multiple hops [17]. Due to the influence of concave boundary in the concave area, the shortest path between sensor nodes through multihop communication is likely to deviate far from a straight line, resulting in a large error in the shortest path between them [18]. Therefore, it is of great practical value to use the range-free localization method to obtain the accurate localization results of target nodes in concave area sensor networks, which is worthy of further study.With the research and development of the location algorithm of range-free nodes, some scholars have carried out research on the location algorithm of concave regional nodes from different angles and application fields. The research is mainly divided into four aspects: anchor node selection, region division, shortest distance correction, and unknown node classification. Anup Kumar Paul et al. proposed a FABL localization algorithm based on friendly anchor node selection [19]. FABL algorithm uses the estimate d distance between anchor nodes and the true distance between anchor nodes to calculate the angle value [19]. Each anchor node is arranged in descending order of the angle, and each unknown node takes the first 8 anchor nodes in descending order to carry out localization calculation, which reduces the influence of concave area on the localization results of unknown nodes. However, the premise of the FABL algorithm is that there must be more than 8 anchor nodes and the deployment of high-density nodes, and there is no guarantee that these 8 anchor nodes will not be affected by concave boundaries.Shang proposed an improved MDS-MAP localization algorithm [20]. The original intention of this algorithm is to make the MDS-MAP algorithm also suitable for distributed location computation. Since the improved MDS-MAP localization algorithm divides the whole region into small regions, the implementation of the MDS-MAP algorithm in a local region can reduce the influence of concave boundary on the localization accuracy to a certain extent. The advantage of this localization algorithm is that the region division process is relatively simple, but the algorithm does not provide how to divide the region, the small region divided is not necessarily a convex area, and there are certain requirements for node deployment. Hyuk Lim et al. proposed a correction method PDM for the measured distance between nodes [21]. Product data management (PDM) localization algorithm first identifies the actual distance between anchor nodes and the estimated distance of the shortest path as a matrix, respectively, and calculates the linear transformation matrix of the two matrices, then the estimated distance is transformed by a linear transformation, and finally, the location calculation is completed by multilateral measurement method. The advantage of the PDM localization algorithm is that more accurate localization results can be obtained under the premise of more anchor nodes and more unified deployment. However, if the distribution of anchor nodes is not uniform, the corresponding linear variation error of distance correction will be large. And the anchor nodes are required to have strong computing power.Aiming at some of the existing problems of such algorithms, this paper proposes a multihop node location algorithm for anisotropic wireless sensor networks, referred to as EARP localization algorithm. Firstly, concave area boundary recognition is performed for the wireless sensor network, and the boundary nodes distributed in the concave area are marked differently. When the shortest path between two nodes is affected by the concave area, the boundary nodes of the concave area will expand to obtain a new shortest communication path. Compare two different shortest communication paths and build a mathematical equation to get the estimated distance between nodes. Compared with the traditional LEAP algorithm [22], DV-RND [23], and PDM algorithm [21], this method proves the superiority of this algorithm.In anisotropic sensor networks, because there is a concave area, the localization results obtained by range-free localization methods are usually difficult to meet actual needs in terms of accuracy. There are two difficulties in current localization algorithms used in concave area sensor networks. The first difficulty is the identification of the concave area boundary, which means that randomly distributed sensor nodes do not know whether they are boundary nodes of the concave area. When the boundary nodes of a concave area can be identified, how to use the node connectivity information we have and design a reasonable algorithm to achieve high-precision node localization results is another difficult point. The following is a detailed introduction to the algorithm of this paper from these two aspects.


## 3. Boundary Identification of Concave Areas

From the connection information of nodes, we can get the shortest path between nodes, which is important information positively related to node spacing. However, the shortest path cannot accurately reflect node spacing. In a sensor network with a random distribution of nodes and complex application scenarios, it is very likely that no sensor nodes are distributed to the sensor nodes in a local area, resulting in a concave area. The shortest path of the two communication nodes affected by the concave area will bypass the concave area by passing the boundary of the concave area to realize the connection between the nodes. Therefore, the shortest communication path through the concave area boundary node deviates far from the straight line, with a large deviation from the actual distance, which results in a large error in node localization. As shown in Figure1, the shortest communication path Lb between node s and node t has a large deviation.Figure 1
The impact of concave areas on communication.If we can identify the concave area and mark its boundary nodes, then, in the stage of estimating node distance, we can identify the shortest communication path affected by the concave area, which provides a basic condition for solving the node location problem in the concave area.


### 3.1. Boundary Classification of Concave Areas

We cannot judge whether the direction of the shortest path has changed based on the connection information of the nodes, but we can obtain the distribution of neighboring nodes from it. Boundary recognition of concave area provides a method basis for the estimation of the distance between the nodes, so we analyze it from the shortest path between nodes. When the communication between two nodes is affected by concave area, the shortest path between nodes is bound to pass through the node at the boundary of concave area. Because the deployment environment of wireless sensor network is complex, the line shape of the concave area boundary is different, which may be irregular line segments such as straight lines, broken lines, and curves. We can simply classify the boundary of the concave area into the following four categories.


#### 3.1.1. Concave Boundary Type

The boundary of this type of concave area is obviously concave in the communication range of the boundary node, as shown in Figure2.Figure 2
Schematic diagram of concave boundary nodes.Of course, there are many situations for the concave boundary, such as the concave of the polyline type and the concave of the curve type. After experiments, we found that the shortest path between nonboundary nodes does not pass through the concave boundary nodes. The proof is as follows: Assuming that the shortest path between nodes passes through the concave boundary nodes, it means that there will be no shorter path than through the concave boundary nodes, which is obviously contrary to the actual situation. As shown in Figure3, in the area of the concave boundary, the nodes can be connected to each other, and the shortest path can directly pass through the area, instead of bypassing the longer path of the concave boundary nodes to realize the connection.Figure 3
The communication path of the concave boundary node.


#### 3.1.2. Convex Boundary Type

The characteristic of this type of boundary is that there are obvious bulges in the communication range of the boundary nodes, as shown in Figure4:Figure 4
Schematic diagram of convex boundary nodes.Observing the characteristics of this type of boundary, we find that the shortest communication paths of nodes distributed on both sides of the concave area often deviate from a straight line, which is far from the actual distance. In the localization algorithm that uses the shortest communication path to complete ranging, a large error will be caused. These boundaries need to be identified and optimized in the node localization algorithm of this paper.


#### 3.1.3. Straight Boundary Type

This type of boundary is within the communication range of the boundary node, and the concave area boundary is approximately a straight line, as shown in Figure5.Figure 5
Schematic diagram of straight boundary nodes.Only when the concave area is on the straight path of two communication nodes, the shortest communication path between the nodes will be affected. That is to say, the two communication nodes should be distributed on both sides of the concave area. Because the communication of the nodes cannot pass through the concave area but can only bypass the boundary of the concave area, the shortest communication path between the nodes has a large deviation. If it is only a straight-line boundary, all nodes are distributed on the same side of the boundary, and the shortest communication path between nodes will not be affected.


#### 3.1.4. Irregular Boundary Type

This type of boundary has no obvious characteristics. It not only is concave or convex but also may be straight or curved. We can regard the irregular concave area boundary as a combination of multiple different types of boundaries. For example, as shown in Figure6, we can regard it as a combination of concave and convex boundaries.Figure 6
Schematic diagram of irregular boundary nodes.To sum up, we know that the concave boundary and the straight boundary will not affect the communication between nodes. Only the convex boundary and the convex part of the irregular boundary will affect the node communication.


### 3.2. Split Communication

In summary, we know that the recognition of the convex class boundary is the focus of our work. Observing the characteristics of this type of boundary, we find that the convex boundary separates the communication of surrounding nodes into two parts. So we can try to identify the boundary of this kind of concave area from the connected relationship of the nodes. When there is a concave area between two nodes, even if the distance is less thanR, the two nodes cannot be directly connected. The intermediate node is required to forward the message to help them achieve the connection.As shown in Figure7, the distance dij is less than R, but intermediate node k is needed to assist in information interaction. From this, we can get the single-hop connectivity graph of this type of boundary node. As shown in Figure 8(a), node i is a concave boundary node. In the communication range of node i, the common neighbor node of node j is removed, and other nodes can only be self-organized into two sensor networks instead of one. We named this connection method split communication. This is essential for identifying this type of boundary node. However, not only will the boundary nodes of the concave area have split communication, but also the nonboundary nodes adjacent to the concave area will have similar connected graphs, as shown in Figure 8(b).Figure 7
Connected graph of convex boundary nodes.Figure 8
Schematic diagram of split communication between neighboring nodes in a concave area. (a) Split communication of concave area boundary node. (b) Split communication of concave area adjacent node.
(a)(b)After experiments, we found the following three conditions for split communication between two sensor nodes in the concave area:(1)
Nodei is an adjacent node of the concave area boundary: the distance between node i and the concave area boundary is less than R (the communication coverage of node i intersects with the concave area).(2)
Nodej is distributed on the other side of node i relative to the concave area and is a neighbor node of node i.(3)
The communication coverage area of nodej intersects the concave area, and the intersecting area is a subset of the intersection area of node i and the concave area.The following is a method to distinguish the concave area boundary nodes in the split communication. It can be determined that the distance between the concave area boundary node and the concave area boundary is smaller than the distance between the adjacent nonboundary nodes and the concave area boundary. According to condition (2) and condition (3), we can deduce that the distribution area of neighbor nodes that can produce split communication with boundary nodes is larger than that of neighboring nonboundary nodes that produce split communication under the same conditions. Then, the boundary nodes of the concave area can be distinguished by comparing the size of the distribution area. But in the sensor network, we cannot obtain area-related information.We can use the longest communication distance between the neighboring nodei of concave area and its neighbor node set to distinguish the proximity degree of node i and concave area when split communication occurs. According to condition (2), the closer the node is to the boundary of the concave area, the larger the node distribution area where split communication occurs will be and the larger the Euclidean distance between two nodes will be when segmentation communication occurs.As shown in Figure9, node i is a boundary node of the concave area, and node g is a nonboundary node adjacent to the concave area. dij and dvg in the figure are the farthest communication distances between these two nodes and their neighbor nodes when split communication occurs. We named the maximum Euclidean distance dc when the neighboring node of the concave area can produce split communication with its neighbor node as the maximum split communication distance. Obviously, it can be seen that the maximum split communication distance dij of the boundary node i is greater than the maximum split communication distance dvg of the adjacent nonboundary node g. Therefore, we can use the maximum split communication distance of adjacent nodes in the concave area to distinguish boundary nodes in the same situation. The distance between nodes can be obtained by the connection information between nodes (introduced in Section 3.1.3). Therefore, the node spacing is used to compare and screen out the boundary nodes of the concave area. The following details describe the method of using node connectivity information for node ranging.Figure 9
The maximum split communication distance of neighboring nodes in the concave area.


### 3.3. Isotropic Node Ranging Method

We assume that, in an anisotropic wireless sensor network, the distribution characteristics of other nodes except the concave area are isotropic. Then, we can calculate the distance between nodes according to the connection information of the nodes, as shown in Figure10; they are the single-hop communication diagram and the two-hop communication diagram of the nodes.Figure 10
Connectivity graph between nodes. (a) Communication between two nodes with one hop. (b) Communication between two nodes with two hops.
(a)(b)The black dots in the figure represent different neighbor nodes of nodesi and j. The yellow dots are their public neighbor nodes. It can be seen from Figure 10 that the area of the overlapping area of the communication range of the two nodes is inversely proportional to the distance. Through the relationship of geometric figures, the area Aij of the communication overlapping area of nodes i and j satisfies the following equation:(1)Aij=2R2cos−1dij2R−dijR2−dij24.We cannot calculate the areaAij in equation (1). We can divide the two sides of the equation by the communication area πR2 of the node:(2)AijπR2=S=φdij=2πcos−1dij2R−dijπR1−dij2R.In anisotropic sensor networks, the area ratio of different areas can be replaced by the ratio of the number of nodes distributed in the corresponding area. We useN (i) to denote the set of all neighbor nodes of node i, and the area ratio S in the equation is(3)S=φdij=Ni∩NjmaxNi,Nj,(4)dij=ϕS=ϕNi∩NjmaxNi,Nj.In equation (4), ϕS is the inverse function of φdij. Although there are no other unknowns except dij in ϕS, we cannot directly use the inverse function ϕS to solve dij, because the function ϕS has no closed expression. We can regard this problem as the root-finding problem of the function: φ˜x=φx−S^. The secant method is an iterative algorithm that finds the root by iteratively executing the following instructions. By executing the following instructions,(5)d^ijp+1=d^ijp−φ¯dijpdijp−dijp−1φdijp−φdijp.In equation (5), p represents the number of iterations before convergence; that is, p=pmax=infpd^ijp=d^ijp+s,∀s∈N∗. In the equation, use the initial values dij0 and dij1 to complete d^ijp=d^ijpmax. Only when dij0 and dij1 are within the range of dij, the secant method can quickly converge. We set d^ij0=R and d^ij1=2R. The equation for calculating the distance between nodes is as follows:(6)dij=∑l=1n−1/2ψN2l−1∩N2l+1maxN2l−1,N2l+1,(7)dij=∑l=1n−1/2ψN2l−1∩N2l+1maxN2l−1,N2l+1+dlast.Equation (6) describes the node spacing when the shortest communication path between nodes has an even number of hops, and equation (7) describes the node spacing when the hop number is odd. In order to reduce the error, we add two-hop distances as the unit to calculate the node spacing. The last hop dlast in equation (7) is the node distance of a single hop, and the calculation method is the same as above.(8)dlast=ψNn−1∩NnmaxNn−1,Nn.In an ideal situation, the maximum split communication distance of a boundary node of the concave area should be the communication radiusR. However, in actual situations, due to many factors such as the instability of node communication signals and uneven node distribution, there are certain errors in the estimation of node spacing. Therefore, the maximum split communication distance R cannot be used as a judgment condition for the boundary node of the concave area.After analyzing the experimental results, we will determine whether the maximum split communication distancedc of adjacent nodes in the concave area is in [0.8R, 1.2R] as a judgment condition for whether the node is a boundary node of the concave area. This condition not only has a good tolerance for communication errors between nodes but also expands the detection range of the boundary of the concave area and avoids the missed judgment of the boundary nodes.This method not only can effectively identify the boundary nodes of the convex class but also has a good recognition effect for other types of boundary nodes, for example, straight-line boundary nodes, recessed boundary nodes, and some irregular boundary nodes. As shown in Figure11, the maximum split communication distance dc between the straight-line boundary nodes and the recessed boundary nodes will also be in [0.8R, 1.2R].Figure 11
Split communication of other types of boundary nodes. (a) Straight boundary nodes. (b) Concave boundary nodes.
(a)(b)However, in a concave area sensor network, although there may be different types of concave area boundaries on the communication paths of two communication nodes, their shortest communication paths will only pass through convex boundary nodes. Therefore, this identification method can well identify the concave area boundary node in the shortest communication path of the node.


## 3.1. Boundary Classification of Concave Areas

We cannot judge whether the direction of the shortest path has changed based on the connection information of the nodes, but we can obtain the distribution of neighboring nodes from it. Boundary recognition of concave area provides a method basis for the estimation of the distance between the nodes, so we analyze it from the shortest path between nodes. When the communication between two nodes is affected by concave area, the shortest path between nodes is bound to pass through the node at the boundary of concave area. Because the deployment environment of wireless sensor network is complex, the line shape of the concave area boundary is different, which may be irregular line segments such as straight lines, broken lines, and curves. We can simply classify the boundary of the concave area into the following four categories.


### 3.1.1. Concave Boundary Type

The boundary of this type of concave area is obviously concave in the communication range of the boundary node, as shown in Figure2.Figure 2
Schematic diagram of concave boundary nodes.Of course, there are many situations for the concave boundary, such as the concave of the polyline type and the concave of the curve type. After experiments, we found that the shortest path between nonboundary nodes does not pass through the concave boundary nodes. The proof is as follows: Assuming that the shortest path between nodes passes through the concave boundary nodes, it means that there will be no shorter path than through the concave boundary nodes, which is obviously contrary to the actual situation. As shown in Figure3, in the area of the concave boundary, the nodes can be connected to each other, and the shortest path can directly pass through the area, instead of bypassing the longer path of the concave boundary nodes to realize the connection.Figure 3
The communication path of the concave boundary node.


### 3.1.2. Convex Boundary Type

The characteristic of this type of boundary is that there are obvious bulges in the communication range of the boundary nodes, as shown in Figure4:Figure 4
Schematic diagram of convex boundary nodes.Observing the characteristics of this type of boundary, we find that the shortest communication paths of nodes distributed on both sides of the concave area often deviate from a straight line, which is far from the actual distance. In the localization algorithm that uses the shortest communication path to complete ranging, a large error will be caused. These boundaries need to be identified and optimized in the node localization algorithm of this paper.


### 3.1.3. Straight Boundary Type

This type of boundary is within the communication range of the boundary node, and the concave area boundary is approximately a straight line, as shown in Figure5.Figure 5
Schematic diagram of straight boundary nodes.Only when the concave area is on the straight path of two communication nodes, the shortest communication path between the nodes will be affected. That is to say, the two communication nodes should be distributed on both sides of the concave area. Because the communication of the nodes cannot pass through the concave area but can only bypass the boundary of the concave area, the shortest communication path between the nodes has a large deviation. If it is only a straight-line boundary, all nodes are distributed on the same side of the boundary, and the shortest communication path between nodes will not be affected.


### 3.1.4. Irregular Boundary Type

This type of boundary has no obvious characteristics. It not only is concave or convex but also may be straight or curved. We can regard the irregular concave area boundary as a combination of multiple different types of boundaries. For example, as shown in Figure6, we can regard it as a combination of concave and convex boundaries.Figure 6
Schematic diagram of irregular boundary nodes.To sum up, we know that the concave boundary and the straight boundary will not affect the communication between nodes. Only the convex boundary and the convex part of the irregular boundary will affect the node communication.


## 3.1.1. Concave Boundary Type

The boundary of this type of concave area is obviously concave in the communication range of the boundary node, as shown in Figure2.Figure 2
Schematic diagram of concave boundary nodes.Of course, there are many situations for the concave boundary, such as the concave of the polyline type and the concave of the curve type. After experiments, we found that the shortest path between nonboundary nodes does not pass through the concave boundary nodes. The proof is as follows: Assuming that the shortest path between nodes passes through the concave boundary nodes, it means that there will be no shorter path than through the concave boundary nodes, which is obviously contrary to the actual situation. As shown in Figure3, in the area of the concave boundary, the nodes can be connected to each other, and the shortest path can directly pass through the area, instead of bypassing the longer path of the concave boundary nodes to realize the connection.Figure 3
The communication path of the concave boundary node.


## 3.1.2. Convex Boundary Type

The characteristic of this type of boundary is that there are obvious bulges in the communication range of the boundary nodes, as shown in Figure4:Figure 4
Schematic diagram of convex boundary nodes.Observing the characteristics of this type of boundary, we find that the shortest communication paths of nodes distributed on both sides of the concave area often deviate from a straight line, which is far from the actual distance. In the localization algorithm that uses the shortest communication path to complete ranging, a large error will be caused. These boundaries need to be identified and optimized in the node localization algorithm of this paper.


## 3.1.3. Straight Boundary Type

This type of boundary is within the communication range of the boundary node, and the concave area boundary is approximately a straight line, as shown in Figure5.Figure 5
Schematic diagram of straight boundary nodes.Only when the concave area is on the straight path of two communication nodes, the shortest communication path between the nodes will be affected. That is to say, the two communication nodes should be distributed on both sides of the concave area. Because the communication of the nodes cannot pass through the concave area but can only bypass the boundary of the concave area, the shortest communication path between the nodes has a large deviation. If it is only a straight-line boundary, all nodes are distributed on the same side of the boundary, and the shortest communication path between nodes will not be affected.


## 3.1.4. Irregular Boundary Type

This type of boundary has no obvious characteristics. It not only is concave or convex but also may be straight or curved. We can regard the irregular concave area boundary as a combination of multiple different types of boundaries. For example, as shown in Figure6, we can regard it as a combination of concave and convex boundaries.Figure 6
Schematic diagram of irregular boundary nodes.To sum up, we know that the concave boundary and the straight boundary will not affect the communication between nodes. Only the convex boundary and the convex part of the irregular boundary will affect the node communication.


## 3.2. Split Communication

In summary, we know that the recognition of the convex class boundary is the focus of our work. Observing the characteristics of this type of boundary, we find that the convex boundary separates the communication of surrounding nodes into two parts. So we can try to identify the boundary of this kind of concave area from the connected relationship of the nodes. When there is a concave area between two nodes, even if the distance is less thanR, the two nodes cannot be directly connected. The intermediate node is required to forward the message to help them achieve the connection.As shown in Figure7, the distance dij is less than R, but intermediate node k is needed to assist in information interaction. From this, we can get the single-hop connectivity graph of this type of boundary node. As shown in Figure 8(a), node i is a concave boundary node. In the communication range of node i, the common neighbor node of node j is removed, and other nodes can only be self-organized into two sensor networks instead of one. We named this connection method split communication. This is essential for identifying this type of boundary node. However, not only will the boundary nodes of the concave area have split communication, but also the nonboundary nodes adjacent to the concave area will have similar connected graphs, as shown in Figure 8(b).Figure 7
Connected graph of convex boundary nodes.Figure 8
Schematic diagram of split communication between neighboring nodes in a concave area. (a) Split communication of concave area boundary node. (b) Split communication of concave area adjacent node.
(a)(b)After experiments, we found the following three conditions for split communication between two sensor nodes in the concave area:(1)
Nodei is an adjacent node of the concave area boundary: the distance between node i and the concave area boundary is less than R (the communication coverage of node i intersects with the concave area).(2)
Nodej is distributed on the other side of node i relative to the concave area and is a neighbor node of node i.(3)
The communication coverage area of nodej intersects the concave area, and the intersecting area is a subset of the intersection area of node i and the concave area.The following is a method to distinguish the concave area boundary nodes in the split communication. It can be determined that the distance between the concave area boundary node and the concave area boundary is smaller than the distance between the adjacent nonboundary nodes and the concave area boundary. According to condition (2) and condition (3), we can deduce that the distribution area of neighbor nodes that can produce split communication with boundary nodes is larger than that of neighboring nonboundary nodes that produce split communication under the same conditions. Then, the boundary nodes of the concave area can be distinguished by comparing the size of the distribution area. But in the sensor network, we cannot obtain area-related information.We can use the longest communication distance between the neighboring nodei of concave area and its neighbor node set to distinguish the proximity degree of node i and concave area when split communication occurs. According to condition (2), the closer the node is to the boundary of the concave area, the larger the node distribution area where split communication occurs will be and the larger the Euclidean distance between two nodes will be when segmentation communication occurs.As shown in Figure9, node i is a boundary node of the concave area, and node g is a nonboundary node adjacent to the concave area. dij and dvg in the figure are the farthest communication distances between these two nodes and their neighbor nodes when split communication occurs. We named the maximum Euclidean distance dc when the neighboring node of the concave area can produce split communication with its neighbor node as the maximum split communication distance. Obviously, it can be seen that the maximum split communication distance dij of the boundary node i is greater than the maximum split communication distance dvg of the adjacent nonboundary node g. Therefore, we can use the maximum split communication distance of adjacent nodes in the concave area to distinguish boundary nodes in the same situation. The distance between nodes can be obtained by the connection information between nodes (introduced in Section 3.1.3). Therefore, the node spacing is used to compare and screen out the boundary nodes of the concave area. The following details describe the method of using node connectivity information for node ranging.Figure 9
The maximum split communication distance of neighboring nodes in the concave area.


## 3.3. Isotropic Node Ranging Method

We assume that, in an anisotropic wireless sensor network, the distribution characteristics of other nodes except the concave area are isotropic. Then, we can calculate the distance between nodes according to the connection information of the nodes, as shown in Figure10; they are the single-hop communication diagram and the two-hop communication diagram of the nodes.Figure 10
Connectivity graph between nodes. (a) Communication between two nodes with one hop. (b) Communication between two nodes with two hops.
(a)(b)The black dots in the figure represent different neighbor nodes of nodesi and j. The yellow dots are their public neighbor nodes. It can be seen from Figure 10 that the area of the overlapping area of the communication range of the two nodes is inversely proportional to the distance. Through the relationship of geometric figures, the area Aij of the communication overlapping area of nodes i and j satisfies the following equation:(1)Aij=2R2cos−1dij2R−dijR2−dij24.We cannot calculate the areaAij in equation (1). We can divide the two sides of the equation by the communication area πR2 of the node:(2)AijπR2=S=φdij=2πcos−1dij2R−dijπR1−dij2R.In anisotropic sensor networks, the area ratio of different areas can be replaced by the ratio of the number of nodes distributed in the corresponding area. We useN (i) to denote the set of all neighbor nodes of node i, and the area ratio S in the equation is(3)S=φdij=Ni∩NjmaxNi,Nj,(4)dij=ϕS=ϕNi∩NjmaxNi,Nj.In equation (4), ϕS is the inverse function of φdij. Although there are no other unknowns except dij in ϕS, we cannot directly use the inverse function ϕS to solve dij, because the function ϕS has no closed expression. We can regard this problem as the root-finding problem of the function: φ˜x=φx−S^. The secant method is an iterative algorithm that finds the root by iteratively executing the following instructions. By executing the following instructions,(5)d^ijp+1=d^ijp−φ¯dijpdijp−dijp−1φdijp−φdijp.In equation (5), p represents the number of iterations before convergence; that is, p=pmax=infpd^ijp=d^ijp+s,∀s∈N∗. In the equation, use the initial values dij0 and dij1 to complete d^ijp=d^ijpmax. Only when dij0 and dij1 are within the range of dij, the secant method can quickly converge. We set d^ij0=R and d^ij1=2R. The equation for calculating the distance between nodes is as follows:(6)dij=∑l=1n−1/2ψN2l−1∩N2l+1maxN2l−1,N2l+1,(7)dij=∑l=1n−1/2ψN2l−1∩N2l+1maxN2l−1,N2l+1+dlast.Equation (6) describes the node spacing when the shortest communication path between nodes has an even number of hops, and equation (7) describes the node spacing when the hop number is odd. In order to reduce the error, we add two-hop distances as the unit to calculate the node spacing. The last hop dlast in equation (7) is the node distance of a single hop, and the calculation method is the same as above.(8)dlast=ψNn−1∩NnmaxNn−1,Nn.In an ideal situation, the maximum split communication distance of a boundary node of the concave area should be the communication radiusR. However, in actual situations, due to many factors such as the instability of node communication signals and uneven node distribution, there are certain errors in the estimation of node spacing. Therefore, the maximum split communication distance R cannot be used as a judgment condition for the boundary node of the concave area.After analyzing the experimental results, we will determine whether the maximum split communication distancedc of adjacent nodes in the concave area is in [0.8R, 1.2R] as a judgment condition for whether the node is a boundary node of the concave area. This condition not only has a good tolerance for communication errors between nodes but also expands the detection range of the boundary of the concave area and avoids the missed judgment of the boundary nodes.This method not only can effectively identify the boundary nodes of the convex class but also has a good recognition effect for other types of boundary nodes, for example, straight-line boundary nodes, recessed boundary nodes, and some irregular boundary nodes. As shown in Figure11, the maximum split communication distance dc between the straight-line boundary nodes and the recessed boundary nodes will also be in [0.8R, 1.2R].Figure 11
Split communication of other types of boundary nodes. (a) Straight boundary nodes. (b) Concave boundary nodes.
(a)(b)However, in a concave area sensor network, although there may be different types of concave area boundaries on the communication paths of two communication nodes, their shortest communication paths will only pass through convex boundary nodes. Therefore, this identification method can well identify the concave area boundary node in the shortest communication path of the node.


## 4. Extended Concave Area Ranging Method

Through the above method, the boundary nodes of the concave area in the anisotropic sensor network can be identified and marked. Therefore, in the process of node communication, we can easily find the nodes whose communication is affected by the concave area. This provides conditions for us to perform nodes ranging in the concave area.We assume that, in an anisotropic sensor network, except for the concave area, the distribution of other nodes is isotropic. Then the calculation of the distance between nodes when the node communication is not affected by the concave area is relatively accurate. However, for those nodes whose communication is affected by the concave area, we have adopted a new method to calculate the distance, and relatively accurate distance estimation can also be obtained.


### 4.1. Single-Point Extended Area Ranging Method

As shown in Figure12, node s and node t are two nodes whose communication is affected by the concave area. The actual Euclidean distance between nodes is dst, but their shortest communication path length d is the sum of d1 and d2, which is larger than the actual distance.Figure 12
Schematic diagram of node communication passing through a single boundary node.According to the above-mentioned concave area boundary node identification method, we can identify that the shortest communication path of the two nodes passes through the concave area boundary nodeo and then know that there is a large error in the dst distance estimation. Assuming that, except for the concave area H, the distribution of other nodes conforms to the characteristics of isotropy, we can calculate d1 and d2 through the connectivity of the nodes. In the triangle sot, we have got the length of the two sides. If we can get the value of angle a or dio, dst can be calculated. But in the range-free localization method, we cannot calculate them. dst can only be calculated by the connection information of other nodes that are not affected by the concave area.In the triangle sot, there is no information that can be obtained by calculation, and it can only diverge to the area outside the triangle area to find a new solution.As shown in Figure13, we extend the straight line Lmo beyond the triangular area. It is found that if there is a node a on the extension of Lmo, this point shares the base Lst with the triangle sat triangle sot formed by nodes s and t. Moreover, the shortest communication path between node a and node s and node t is not affected by any concave area. Then, we can calculate the distance between nodes d1′, d2′, and d3′ according to the connectivity information of the nodes (the method of node spacing estimation introduced in Section 3.1.3). Furthermore, according to the geometric theorem of right-angled triangles, the node spacing dst affected by the concave area can be obtained. This is an effective method.Figure 13
Schematic diagram of single-point extended concave area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)First, we need to find the nodea that satisfies this condition. In the communication process, we cannot get the angle information between nodes, we can only find the target node a by filtering the connection information between nodes. As shown in Figure 13, the triangle sat formed by the target node a and the nodes s and t share the base Lst. The distances from target node a to nodes s and t are d1′ and d2′, respectively. Point m is the intersection point of passing points a and o perpendicular to the bottom edge Lst; then dst = dsm + dmt. According to the triangle theorem, the length of each side satisfies the following equation:(9)dsm2=d12−d32=d1′2−d3′+d32,(10)dmt2=d22−d32=d2'2−d3′+d32.Then equations (9) and (10) are added together as equation (11). After simplifying both sides of equation (11), equation (12) is obtained.(11)dsm2+dmt2=d12−d32+d2′2−d3′+d32=d22−d32+d1′2−d3′+d32,(12)d12+d2′2=d22+d1′2.We change the knownd1 and d2 in equation (12) to the same side of the equation and obtain the following equation:(13)d1′2−d2′2=d12−d22.In equation (13), d1 and d2 are the length of the shortest communication path from node s and node t to node o. For example, in the figure, Lso and Lot are clear paths, and d1 and d2 can be calculated using the connectivity information between nodes (the node spacing estimation method introduced in Section 3.1.3). Then, we can use the value of d12−d22 as the restriction condition to find the target node a that satisfies the condition in the area outside the triangle sot.We know that, in the process of node communication, the shorter the hop distance between two nodes, the smaller the error of node ranging. In order to reduce the calculation error ofd1 and d2, we narrow the target area to find the target node a. Set the neighboring node with the concave area boundary node o as the center and the shortest communication path not greater than 3 as the target area.As shown in Figure14, after finding the target node a, we can get the following equation according to the straight-line triangle theorem:(14)d1′2−d3′+d32=d12−d32,(15)d1′2−d3′+d32=d12−d32.Figure 14
Geometry schematic diagram of single-point extended concave area ranging method.The distance between nodes represented by the red line in the figure can be obtained from the connected information. Becaused3 is affected by the concave area, its size cannot be estimated. We set d3 to be x; then according to equations (14) and (15), we can get the unknown node spacing d3 as follows:(16)x1=d1′2−d3′2−d122d3′,x2=d2′2−d3′2−d222d3′,d3=x1+x22=d1′2+d2′2−2d3′2−d12−−d224d3′.Ideally,x1 and x2 should be equal. However, in actual application scenarios, the calculation of node spacing inevitably has errors, so the average of the two is taken as the value of d3. Therefore, all the node pitches except dst have been obtained. Given that dst = dsm + dmt, set the value of dsm to y; then according to the triangle som and triangle Sam in the figure, we can obtain the dsm equation as follows:(17)y1=d12−d32,y2=d1′2−d3′+d32,dsm=y1+y22=d12−d32+d1′2−d3′+d322.We set the value ofdmt to z. According to the triangle omt and triangle amt in the figure, we can obtain the dmt equation as follows:(18)z1=d22−d32,z2=d2′2−d3′+d32,dmt=z1+z22=d12−d32+d1′2−d3′+d322.Taking into account the error in the calculation of node spacing, we both use the average of the two as the calculation result. Then, the sum ofdsm and dmt is the value of dst.


### 4.2. Multipoint Extended Area Ranging Method

In anisotropic sensor networks, the shortest communication paths affected by the concave area are not all the same. As shown in Figure15, the shortest communication path between node s and node t not only passes through one concave area boundary node but also may pass through multiple concave area boundary nodes.Figure 15
Schematic diagram of node communication passing through multiple boundary nodes. (a) Arc-shaped communication path. (b) Polyline communication path.
(a)(b)This kind of node communication situation is much more complicated than the shortest communication path only passing through a single concave area boundary node. We can split the pathLst affected by the concave area into multiple short paths, then use the single-point extended area ranging method to calculate the short paths one by one, and finally superimpose them to obtain the final solution, as shown in Figure 16.Figure 16
Schematic diagram of cumulative calculation of multipoint extended area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)The shortest communication path between nodess and t passes through three concave area boundary nodes, namely, nodes i, j, and k. We divide the entire shortest communication path into two short paths Lsi and Lit, both of which pass through a single boundary node. Then for the two short paths, the single-point extended concave area ranging method is used to complete the ranging. We can get dsi and dit. Then the problem becomes a node ranging problem of finding the shortest communication path between nodes through a single concave area boundary node i, and dst can be obtained.Although this method can obtain the distance between nodes, it is not effective in practical applications. When we divide the shortest communication path of a node into multiple short paths and calculate them separately, there will be errors in the ranging of each short path, and the accumulated error becomes larger and larger. The final calculatedd has a large deviation from the actual distance.Obviously, the method of decomposing the shortest communication path into multiple short paths cannot meet the actual need. We should find a more accurate method. In order to obtain more accurate node spacing, we should minimize the number of single-point extended area ranging methods. If we can complete the distance measurement using this method only once, the result will be more accurate.Comparing these two cases, we find that their difference lies in how many concave regional boundary nodes are included in the pathLst. When the boundary of the concave area is a smooth protruding curve or there are multiple protrusions, the path Lst passing through the region often passes through multiple concave area boundary nodes. When the concave boundary is a single sharp bulge, the path Lst passing through the region often passes through a single concave boundary node.As shown in Figure17, the communication path Lst passes through multiple concave area boundary nodes. At this time, if we can expand the boundary of the concave area into a single sharp protrusion, then we can complete the node ranging by using the single-point extended area ranging method only once. This is not difficult to achieve. We are looking for an intermediate node o outside the boundary of the concave area, and the communication path between node s and node t must pass through this node, and the shortest communication path passing through the intermediate node o cannot pass through the concave area boundary node. There are many such intermediate points in the sensor network. In order to reduce the calculation error of the node spacing, we should choose the intermediate point with the shortest communication path with the smallest number of hops from the set of intermediate points that meet the conditions as the optimal intermediate point.Figure 17
Schematic diagram of multipoint extended area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)Suppose that we find that nodeo is the optimal intermediate point and the shortest communication path Lst passing node o is shown in the figure. This is like extending the original smooth boundary into a single sharp convex boundary so that we can complete the node ranging by using the single-point extended area ranging method only once.Addressing the problem of unknown node location in anisotropic sensor networks. First, we use the concave area boundary recognition method in this paper to identify and mark the nodes distributed on the boundary of the concave area. Then, for the two nodes whose shortest communication path is affected by the concave area, the distance between the nodes is obtained by the extended concave area ranging method. For the two nodes whose shortest communication path is not affected by the concave area, the connection information is used to realize node ranging. Finally, we use the MDS-MAP algorithm to locate unknown nodes.


## 4.1. Single-Point Extended Area Ranging Method

As shown in Figure12, node s and node t are two nodes whose communication is affected by the concave area. The actual Euclidean distance between nodes is dst, but their shortest communication path length d is the sum of d1 and d2, which is larger than the actual distance.Figure 12
Schematic diagram of node communication passing through a single boundary node.According to the above-mentioned concave area boundary node identification method, we can identify that the shortest communication path of the two nodes passes through the concave area boundary nodeo and then know that there is a large error in the dst distance estimation. Assuming that, except for the concave area H, the distribution of other nodes conforms to the characteristics of isotropy, we can calculate d1 and d2 through the connectivity of the nodes. In the triangle sot, we have got the length of the two sides. If we can get the value of angle a or dio, dst can be calculated. But in the range-free localization method, we cannot calculate them. dst can only be calculated by the connection information of other nodes that are not affected by the concave area.In the triangle sot, there is no information that can be obtained by calculation, and it can only diverge to the area outside the triangle area to find a new solution.As shown in Figure13, we extend the straight line Lmo beyond the triangular area. It is found that if there is a node a on the extension of Lmo, this point shares the base Lst with the triangle sat triangle sot formed by nodes s and t. Moreover, the shortest communication path between node a and node s and node t is not affected by any concave area. Then, we can calculate the distance between nodes d1′, d2′, and d3′ according to the connectivity information of the nodes (the method of node spacing estimation introduced in Section 3.1.3). Furthermore, according to the geometric theorem of right-angled triangles, the node spacing dst affected by the concave area can be obtained. This is an effective method.Figure 13
Schematic diagram of single-point extended concave area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)First, we need to find the nodea that satisfies this condition. In the communication process, we cannot get the angle information between nodes, we can only find the target node a by filtering the connection information between nodes. As shown in Figure 13, the triangle sat formed by the target node a and the nodes s and t share the base Lst. The distances from target node a to nodes s and t are d1′ and d2′, respectively. Point m is the intersection point of passing points a and o perpendicular to the bottom edge Lst; then dst = dsm + dmt. According to the triangle theorem, the length of each side satisfies the following equation:(9)dsm2=d12−d32=d1′2−d3′+d32,(10)dmt2=d22−d32=d2'2−d3′+d32.Then equations (9) and (10) are added together as equation (11). After simplifying both sides of equation (11), equation (12) is obtained.(11)dsm2+dmt2=d12−d32+d2′2−d3′+d32=d22−d32+d1′2−d3′+d32,(12)d12+d2′2=d22+d1′2.We change the knownd1 and d2 in equation (12) to the same side of the equation and obtain the following equation:(13)d1′2−d2′2=d12−d22.In equation (13), d1 and d2 are the length of the shortest communication path from node s and node t to node o. For example, in the figure, Lso and Lot are clear paths, and d1 and d2 can be calculated using the connectivity information between nodes (the node spacing estimation method introduced in Section 3.1.3). Then, we can use the value of d12−d22 as the restriction condition to find the target node a that satisfies the condition in the area outside the triangle sot.We know that, in the process of node communication, the shorter the hop distance between two nodes, the smaller the error of node ranging. In order to reduce the calculation error ofd1 and d2, we narrow the target area to find the target node a. Set the neighboring node with the concave area boundary node o as the center and the shortest communication path not greater than 3 as the target area.As shown in Figure14, after finding the target node a, we can get the following equation according to the straight-line triangle theorem:(14)d1′2−d3′+d32=d12−d32,(15)d1′2−d3′+d32=d12−d32.Figure 14
Geometry schematic diagram of single-point extended concave area ranging method.The distance between nodes represented by the red line in the figure can be obtained from the connected information. Becaused3 is affected by the concave area, its size cannot be estimated. We set d3 to be x; then according to equations (14) and (15), we can get the unknown node spacing d3 as follows:(16)x1=d1′2−d3′2−d122d3′,x2=d2′2−d3′2−d222d3′,d3=x1+x22=d1′2+d2′2−2d3′2−d12−−d224d3′.Ideally,x1 and x2 should be equal. However, in actual application scenarios, the calculation of node spacing inevitably has errors, so the average of the two is taken as the value of d3. Therefore, all the node pitches except dst have been obtained. Given that dst = dsm + dmt, set the value of dsm to y; then according to the triangle som and triangle Sam in the figure, we can obtain the dsm equation as follows:(17)y1=d12−d32,y2=d1′2−d3′+d32,dsm=y1+y22=d12−d32+d1′2−d3′+d322.We set the value ofdmt to z. According to the triangle omt and triangle amt in the figure, we can obtain the dmt equation as follows:(18)z1=d22−d32,z2=d2′2−d3′+d32,dmt=z1+z22=d12−d32+d1′2−d3′+d322.Taking into account the error in the calculation of node spacing, we both use the average of the two as the calculation result. Then, the sum ofdsm and dmt is the value of dst.


## 4.2. Multipoint Extended Area Ranging Method

In anisotropic sensor networks, the shortest communication paths affected by the concave area are not all the same. As shown in Figure15, the shortest communication path between node s and node t not only passes through one concave area boundary node but also may pass through multiple concave area boundary nodes.Figure 15
Schematic diagram of node communication passing through multiple boundary nodes. (a) Arc-shaped communication path. (b) Polyline communication path.
(a)(b)This kind of node communication situation is much more complicated than the shortest communication path only passing through a single concave area boundary node. We can split the pathLst affected by the concave area into multiple short paths, then use the single-point extended area ranging method to calculate the short paths one by one, and finally superimpose them to obtain the final solution, as shown in Figure 16.Figure 16
Schematic diagram of cumulative calculation of multipoint extended area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)The shortest communication path between nodess and t passes through three concave area boundary nodes, namely, nodes i, j, and k. We divide the entire shortest communication path into two short paths Lsi and Lit, both of which pass through a single boundary node. Then for the two short paths, the single-point extended concave area ranging method is used to complete the ranging. We can get dsi and dit. Then the problem becomes a node ranging problem of finding the shortest communication path between nodes through a single concave area boundary node i, and dst can be obtained.Although this method can obtain the distance between nodes, it is not effective in practical applications. When we divide the shortest communication path of a node into multiple short paths and calculate them separately, there will be errors in the ranging of each short path, and the accumulated error becomes larger and larger. The final calculatedd has a large deviation from the actual distance.Obviously, the method of decomposing the shortest communication path into multiple short paths cannot meet the actual need. We should find a more accurate method. In order to obtain more accurate node spacing, we should minimize the number of single-point extended area ranging methods. If we can complete the distance measurement using this method only once, the result will be more accurate.Comparing these two cases, we find that their difference lies in how many concave regional boundary nodes are included in the pathLst. When the boundary of the concave area is a smooth protruding curve or there are multiple protrusions, the path Lst passing through the region often passes through multiple concave area boundary nodes. When the concave boundary is a single sharp bulge, the path Lst passing through the region often passes through a single concave boundary node.As shown in Figure17, the communication path Lst passes through multiple concave area boundary nodes. At this time, if we can expand the boundary of the concave area into a single sharp protrusion, then we can complete the node ranging by using the single-point extended area ranging method only once. This is not difficult to achieve. We are looking for an intermediate node o outside the boundary of the concave area, and the communication path between node s and node t must pass through this node, and the shortest communication path passing through the intermediate node o cannot pass through the concave area boundary node. There are many such intermediate points in the sensor network. In order to reduce the calculation error of the node spacing, we should choose the intermediate point with the shortest communication path with the smallest number of hops from the set of intermediate points that meet the conditions as the optimal intermediate point.Figure 17
Schematic diagram of multipoint extended area ranging method. (a) Communication diagram. (b) Geometric diagram.
(a)(b)Suppose that we find that nodeo is the optimal intermediate point and the shortest communication path Lst passing node o is shown in the figure. This is like extending the original smooth boundary into a single sharp convex boundary so that we can complete the node ranging by using the single-point extended area ranging method only once.Addressing the problem of unknown node location in anisotropic sensor networks. First, we use the concave area boundary recognition method in this paper to identify and mark the nodes distributed on the boundary of the concave area. Then, for the two nodes whose shortest communication path is affected by the concave area, the distance between the nodes is obtained by the extended concave area ranging method. For the two nodes whose shortest communication path is not affected by the concave area, the connection information is used to realize node ranging. Finally, we use the MDS-MAP algorithm to locate unknown nodes.


## 5. Simulation Results and Analysis

The EARP algorithm has been implemented, but a lot of simulation experiments are needed to verify its accuracy and feasibility. In order to better verify the pros and cons of the EARP algorithm, under the same experimental conditions, we have selected three localization algorithms for comparison: LEAP [22], DV-RND [23], and PDM [21].We use MATLAB to do the simulation experiment and set up 400 sensor nodes, which are randomly deployed in a square area with a length of 100 m and a width of 100 m. The node communication radius isR.In order to fully reflect the influence of different variables on the algorithm, we have set up two different concave areas in the communication area. As shown in the figure above, the concave area in Figure18(a) is a basic rectangle, and Figure 18(b) is an ellipse. In the experiment, we calculated 10 sets of data in two sensor networks and used the average value as the experimental result.Figure 18
Schematic diagram of the concave area in the simulation experiment. (a) Square concave area. (b) Oval concave area.
(a)(b)A high-quality algorithm is reflected in the high accuracy of its results; that is, the calculation error of the algorithm is very small. We usually use the error as an indicator to measure the quality of the algorithm. During the localization process, the EARP algorithm in this paper successively outputs two types of results, namely, the estimated distance and the localization result. When the communication radius is uncertain, introducing the relative error of the radius can describe the superiority of the algorithm more appropriately. Therefore, we use the estimated distance error and the localization error as evaluation indicators [24].There are many factors in the process of node localization that will affect the localization results of nodes. In the case of random deployment and a fixed total number of nodes, the number of anchor nodes and the communication radius of the nodes are two important factors that affect the results of node localization. Next, we will start from these two aspects and compare the pros and cons of the algorithm through experiments.


### 5.1. The Effect of the Total Number of Anchor Nodes

We set the anchor node as a single variable. The total number of sensors is 400, the communication radius of nodes is 20 m, and the number of anchor nodes increases one by one from 4 to 20. Experimental results are recorded and the pictures are drawn as follows.As shown in Figure19, we see that, with the increase in the number of anchor nodes, the estimation error of the node spacing is getting smaller and smaller, but the error reduction is very small. When the number of anchor nodes increases, the shortest communication path between the unknown node and the anchor node is shortened, and the estimation error is relatively reduced. From the picture, we can see that the EARP algorithm in this paper has a much smaller estimated distance error than the other three algorithms under the same conditions. This is because of the fact that the EARP algorithm not only provides a reliable method for identifying the nodes on the boundary of the concave area but also adopts a new ranging method for the nodes where the shortest communication path is affected by the concave area, thus obtaining better ranging results, and reflects the superiority of the algorithm.Figure 19
The effect of the number of anchor nodes on RADE.As shown in Figure20, the localization errors of these four localization algorithms decrease significantly with the increase in the number of anchor nodes. Moreover, the EARP algorithm in this paper is significantly better than the other three localization algorithms, which proves the superiority of the EARP algorithm. The increase in the number of anchor nodes provides a more restrictive condition for the results of node localization, that is, the node distance information from the anchor node to the target node. In the range-free localization algorithm, the node spacing we obtain is biased, and the error of the node spacing affected by the concave area will be greater. Compared with the other three localization algorithms, the ERAP algorithm shows better accuracy in the results of node ranging. Because after identifying the boundary nodes of the concave area, the extended concave area ranging method can well avoid the influence of the concave area, obtain more accurate node spacing information, and then obtain the localization result with less error.Figure 20
The effect of the number of anchor nodes on RAPE.


### 5.2. The Effect of Communication Radius of Node

In the range-free localization algorithm of sensor nodes, because no additional hardware is needed to assist the calculation, we can only get the connectivity information between nodes. The communication radius directly affects the connectivity information between nodes. Therefore, the communication radius of a node has a great influence on node localization. In the process of estimating the distance between nodes, the increase in the communication range of the nodes will also more accurately reflect the relationship between the ratio of the number of nodes in the area and the ratio of the area. In this section, we set the node communication radius to increase from 15 to 30 one by one. The experimental results are as follows.As shown in Figure21, as the communication radius of nodes increases, the estimated distance error between the nodes gradually decreases. When the node communication radius increased to about 26 m, the estimated distance error of the four algorithms in the figure will not continue to decrease, and even the LEAP algorithm and the DV-RND algorithm increased. Because when the radius keeps increasing, the distance measurement method that simply uses the jump distance as the basis for calculation usually cannot accurately reflect the actual distance. Compared with the other three algorithms, the ranging results of the extended concave area node ranging method proposed in this paper are superior. Because the hop distance between nodes gradually decreases as the communication radius of the nodes increases, the shortest communication path tends to be a straight line. Moreover, the ERAP algorithm in this paper is based on the distribution characteristics of nodes to complete the node ranging calculation. The increase of the communication coverage area of the node helps to truly reflect the distance information of the node.Figure 21
The effect of node communication radius on RADE.As shown in Figure22, as the communication radius of the node increases, the localization errors of the four algorithms are reduced to varying degrees. The reduction range of the EARP algorithm is smaller than that of the other three algorithms because, at the initial value of the communication radius, the localization error of the EARP algorithm is much smaller than the other three. From Figure 22, we can see that, under the same conditions, the localization error of the EARP algorithm has obvious advantages. Since the node localization is completed based on the node spacing information, the ERAP algorithm in this paper has shown advancement in concave area boundary recognition and extended concave area ranging calculation, providing high-quality node spacing information for node localization.Figure 22
The effect of node communication radius on RAPE.


## 5.1. The Effect of the Total Number of Anchor Nodes

We set the anchor node as a single variable. The total number of sensors is 400, the communication radius of nodes is 20 m, and the number of anchor nodes increases one by one from 4 to 20. Experimental results are recorded and the pictures are drawn as follows.As shown in Figure19, we see that, with the increase in the number of anchor nodes, the estimation error of the node spacing is getting smaller and smaller, but the error reduction is very small. When the number of anchor nodes increases, the shortest communication path between the unknown node and the anchor node is shortened, and the estimation error is relatively reduced. From the picture, we can see that the EARP algorithm in this paper has a much smaller estimated distance error than the other three algorithms under the same conditions. This is because of the fact that the EARP algorithm not only provides a reliable method for identifying the nodes on the boundary of the concave area but also adopts a new ranging method for the nodes where the shortest communication path is affected by the concave area, thus obtaining better ranging results, and reflects the superiority of the algorithm.Figure 19
The effect of the number of anchor nodes on RADE.As shown in Figure20, the localization errors of these four localization algorithms decrease significantly with the increase in the number of anchor nodes. Moreover, the EARP algorithm in this paper is significantly better than the other three localization algorithms, which proves the superiority of the EARP algorithm. The increase in the number of anchor nodes provides a more restrictive condition for the results of node localization, that is, the node distance information from the anchor node to the target node. In the range-free localization algorithm, the node spacing we obtain is biased, and the error of the node spacing affected by the concave area will be greater. Compared with the other three localization algorithms, the ERAP algorithm shows better accuracy in the results of node ranging. Because after identifying the boundary nodes of the concave area, the extended concave area ranging method can well avoid the influence of the concave area, obtain more accurate node spacing information, and then obtain the localization result with less error.Figure 20
The effect of the number of anchor nodes on RAPE.


## 5.2. The Effect of Communication Radius of Node

In the range-free localization algorithm of sensor nodes, because no additional hardware is needed to assist the calculation, we can only get the connectivity information between nodes. The communication radius directly affects the connectivity information between nodes. Therefore, the communication radius of a node has a great influence on node localization. In the process of estimating the distance between nodes, the increase in the communication range of the nodes will also more accurately reflect the relationship between the ratio of the number of nodes in the area and the ratio of the area. In this section, we set the node communication radius to increase from 15 to 30 one by one. The experimental results are as follows.As shown in Figure21, as the communication radius of nodes increases, the estimated distance error between the nodes gradually decreases. When the node communication radius increased to about 26 m, the estimated distance error of the four algorithms in the figure will not continue to decrease, and even the LEAP algorithm and the DV-RND algorithm increased. Because when the radius keeps increasing, the distance measurement method that simply uses the jump distance as the basis for calculation usually cannot accurately reflect the actual distance. Compared with the other three algorithms, the ranging results of the extended concave area node ranging method proposed in this paper are superior. Because the hop distance between nodes gradually decreases as the communication radius of the nodes increases, the shortest communication path tends to be a straight line. Moreover, the ERAP algorithm in this paper is based on the distribution characteristics of nodes to complete the node ranging calculation. The increase of the communication coverage area of the node helps to truly reflect the distance information of the node.Figure 21
The effect of node communication radius on RADE.As shown in Figure22, as the communication radius of the node increases, the localization errors of the four algorithms are reduced to varying degrees. The reduction range of the EARP algorithm is smaller than that of the other three algorithms because, at the initial value of the communication radius, the localization error of the EARP algorithm is much smaller than the other three. From Figure 22, we can see that, under the same conditions, the localization error of the EARP algorithm has obvious advantages. Since the node localization is completed based on the node spacing information, the ERAP algorithm in this paper has shown advancement in concave area boundary recognition and extended concave area ranging calculation, providing high-quality node spacing information for node localization.Figure 22
The effect of node communication radius on RAPE.


## 6. Conclusions and Future Work

Aiming at the problem of node location in anisotropic sensor networks, this paper proposes the EARP algorithm. First, it classifies and discusses the concave area boundary within the communication range of the node and defines the split communication phenomenon according to the distribution characteristics of the concave area boundary node. The maximum split communication distance of a sensor node indirectly reflects the proximity of the node to the boundary of the concave area, which is used as a judgment condition for identifying and marking the boundary nodes. When the shortest communication path between nodes is affected by the concave area, the ERAP algorithm expands the boundary of the concave area to obtain a new shortest communication path and establishes a mathematical formula to find a new path that satisfies the geometric conditions to assist in the completion of node ranging. Simulation experiments show that this scheme can solve the problem of node localization in anisotropic sensor networks.The ERAP algorithm in this paper only uses the connection information between sensor nodes to perform localization calculations and has very low requirements on sensor nodes and communication networks. As long as the networks can communicate with each other, the localization calculation can be completed. Therefore, the method has good applicability whether it is the current mainstream communication network or the future communication network. Moreover, 5G technology has the characteristics of high speed, low latency, high density, and so on which can support more efficient information transmission and faster signal response. Sensor technology is one of the core technologies in the 5G era. Based on the accurate and high-speed detection of sensors and the real-time transmission characteristics of 5G networks, wireless sensor networks can accurately complete the monitoring and response process, greatly improving the reliability of wireless sensor networks. In the 5G era, wireless sensors will become faster, smaller, and cheaper.In future work, we will use relevant future technologies, such as future application networks such as CRN, SNMA, and NOMA, to explore and improve the nonranging node location of wireless sensor networks.



---

*Source: 4727476-2021-07-27.xml*