key: cord-0989591-xcunytmn
authors: Cai, Xingjuan; Wang, Penghong; Cui, Zhihua; Zhang, Wensheng; Chen, Jinjun
title: Weight convergence analysis of DV-hop localization algorithm with GA
date: 2020-06-18
journal: Soft comput
DOI: 10.1007/s00500-020-05088-z
sha: 93b763260242f5e0b1ae97f0de16e55bfe6eb529
doc_id: 989591
cord_uid: xcunytmn

The distance vector-hop (DV-hop) is a typical localization algorithm. It estimates sensor nodes location through detecting the hop count between nodes. To enhance the positional precision, the weight is used to estimate position, and the conventional wisdom is that the more hop counts are, the smaller value of weight will be. However, there has been no clear mathematical model among positioning error, hop count, and weight. This paper constructs a mathematical model between the weights and hops and analyzes the convergence of this model. Finally, the genetic algorithm is used to solve this mathematical weighted DV-hop (MW-GADV-hop) positioning model, the simulation results illustrate that the model construction is logical, and the positioning error of the model converges to 1/4R.

In this unprecedented age of technology-driven modernization, technologies contribute greatly to the development of human society. For instance, fifth-generation wireless systems (5G) (Andrews et al. 2014; Boccardi et al. 2014) and the internet of things (IoT) (Gubbi et al. 2013; Al-Fuqaha et al. 2015) have greatly improved the speed of people's communication and access to information and improved the user experience. In 2020, during the process of fighting the epidemic (COVID-19) (Zhou et al. 2020; Shi et al. 2020) worldwide, big data technology has played an irreplaceable role in the analysis of epidemic prevention and control. In these applications, location information plays an irreplaceable role.

Generally, satellite positioning is the main way to obtain location information. However, in areas where satellite signals are weak, such as tunnels and factory control systems, the positioning method based on wireless communication has become the main means of acquiring location. DV-hop (Niculescu and Nath 2003) , as a prevailing and typical wireless communication-based localization algorithm, estimates sensor nodes location through detecting the hop count and acquiring estimated distance between nodes. However, this simple principle and operation cause the instability of the positional precision of the standard DV-hop algorithm. It makes the algorithm is unreliable in applications where accuracy is critical, such as medical health (Al Ameen et al. 2012) . To reduce the error, scholars have proposed different improvement measures, including the introduction of weight models and optimization algorithms, and achieving a certain degree of accuracy improvement.

However, the conventional wisdom thinks that the weights will decrease with the hop counts increase. But there has been no clear mathematical model among positioning error, hop count, and weight. To address this issue, this paper improves the weight model and performs a convergence analysis. And the motivation and contribution are shown as follows: the goal of this study is to explore the convergence of the traditional weight model. Therefore, we construct a mathematical model between the weights and hops, reveal the relationship between the traditional weight model and the positioning error, and analyze and prove that the weight model is convergent. Through the proof of convergence, it provides a theoretical basis for scholars to improve the DV-hop positioning model. And this study uses the genetic algorithm (GA) (Goldberg 1989) to conduct a preliminary test of the model.

The remainder of this study is organized as follows. Section 2 provides a brief description of related work and introduces the traditional weight (TW) model with optimization algorithm; in Sect. 3, we construct a mathematical weight model (MW) based on the node communication features and analyze the convergence of this model. Section 4 uses the GA to solve this MW model and carries out the simulation test. Finally, the conclusions are drawn in Sect. 5.

Initially, the third phase of the DV-hop algorithm is to implement position calculation by a deterministic algorithm, such as the trilateration and the least square method. These methods require the algorithm provide an estimated distances with small error to achieve precise precision. But according to Eqs. (1) and (2), we can know this assumption that the acquisition of the highly accurate estimated distance is unrealistic for the DV-hop algorithm. Therefore, scholars use weight model and intelligent optimization algorithms to optimize the DV-hop algorithm to achieve a high accurate precision.

DV-hop with the optimization algorithms contains three stages. 1st phase: anchor nodes (ANs) transmit the packs to the network, other sensor nodes (contains the anchor and unknown nodes, UNs) receive the packs and retransmission them to network. During this process, each node counts the minimum number of hops required to communicate with other nodes. 2nd phase: according to the number of hops recorded, the distance per hop (dis_per) is calculated as follows:

where AN i and AN j denote the positions of the AN i and AN j , hop_count i,j denotes the minimum hop count between AN i and AN j . Then, the distance (dis i,k ) between AN i and UN k is estimated as follows:

3rd phase: the optimization algorithm is used to solve the location of the UNs, and the model is as follows:

where (x i , y i ) denotes the location of the AN i , (x k , y k ) denotes the location of the UN i . In 2007, Chuan (2008) proposed the concept of the weight and she thinks that the value of the weight is decrease with the hop count increase. In 2009, according to this viewpoint, Li et al. (2009) proposed a method for calculating the weight, which follows:

where the Wh j denotes the hop-size weight of AN j .

And the objective function model is calculated as follows:

For the collinearity phenomenon of sensor nodes, Zhang et al. (2014) proposed to use the Voronoi diagram to divide the sensors network into difference multiple regions, each region containing an anchor node. Then, a weighted method is used to calculate the location of the UN. Gui et al. (2015) argued that when the hop count between the AN and UN is large, this AN will interfere rather than promote the positioning process of the UN. Therefore, he proposed to select three ANs closest to the UN for positioning, that is, select the three ANs with the smallest hop number for positioning. Song and Tam (2015) improved DV-hop with the weighted centroid, and the weight (W i ) is calculated as follows (where hop i denotes the minimum hop count between the AN i and UN). This model makes the closest AN has the greatest impact on the positioning results. Li et al. (2015) adapted a similar weight setting method to optimize the DV-hop algorithm.

In recent years, with the recognition of this weight model, scholars have begun to seek to optimize it using various evolutionary algorithms; Mehrabi et al. (2017) proposed to optimize DV-hop with GA-PSO algorithm. Cui et al. (2017) developed a novel oriented cuckoo search (OCS) (Gandomi et al. 2013) algorithm to enhance the DVhop performance. Sharma and Kumar (2018) also applied GA to the positioning process of wireless sensor nodes in three-dimensional (3D) space. Shi et al. (2019) proposed an improved DV-hop approach based on path matching and PSO. Cai et al. (2019a) introduced the rank transformation strategy to the bat algorithm (BA), proposed a fast triangle flip BA, and applied the algorithm to wireless sensor node localization. Further, scholars have also proposed new model improvements, such as the establishment of a multiobjective positioning model (Cai et al. 2019b; Wang et al. 2020; Kanwar and Kumar 2020) based on the theoretical hop distance.

However, it must be mentioned that although these algorithms improve the positional precision of the sensor nodes, they do not provide a convincing proof of the relationship among the errors, hop counts and weights. Therefore, based on the weighted conjectures put forward by scholars, this study constructs the corresponding model and analyzes the convergence of the model to reveal the potential relationship among the weights, hop counts, and errors.

In the WSNs, according to the characteristics of the sensor node, we can get Fig. 1 . In Fig. 1 , the blue point denotes the anchor node, and the black points denote the UNs. Assumption all of the nodes is following the uniform distribution within the detecting area, and the maximum communication radius is R. The theoretical average distance per hop (Per_dis) when the hop count is one is calculated as follows in Eq. (7). Obviously, the calculation method of the Per_dis is different from the dis_per i . The dis_per i is obtained by the multi-hop transmission process; generally, the value of the dis_per i is different from the dis_per k . The Per_dis is obtained by probability statistics, and for different anchor nodes, the average distance is the same.

According to Eq. (7) and Fig. 1 , we can obtain Fig. 2 when the hop count is two. Let the a n indicate the maximum detectable range (also named the up bound) when the hop count is n, and the a 1 is the R. Let the b n represent the average detection distance (also named the estimated distance) at the nth hop. In Fig. 2 , the relationship between the a n and a nÀ1 is shown in Eq. (8), because the communication radius is R, and the value of distance between the dotted line and the anchor node is 14 = 9 R, it is calculated by Eq. (9).

After obtaining the maximum detectable range and the average detection distance model, we also investigate the error model, as shown in Fig. 3 , where the blue point denotes the anchor node, the black nodes denote the other sensor nodes, and the hop count is two. Let the n n represent the error when the hop count is n. As shown in Fig. 3 , the error (n 2 ) is that the distance between the sensor nodes (O i ) and the estimated distance (14/9R) within the detectable range when the hop count is two. Thus, the error model is expressed as Eq. (10).

In this subsection, we analyze the convergence of the error model. Firstly, when the hop count tends to infinity, Eq. (8) is follows: lim n!1 a n ¼ lim

Similarly, Eq. (9) is calculated as follows: 

Then, when the hop count tends to infinity, the error model can be indicated as follows:

Thus, we can obtain that when the hop count tends to infinity (where, the sensor nodes are following the uniform distribution and the number of sensor nodes tends to infinity), the error of estimated distance converges to 1/4R. To reveal the convergence trend of the error, we calculated the error of this model with different hop counts, and the results are shown in Fig. 4 . Obviously, the error increases as the number of hops increases and eventually converges to 1/4R. 

2a 3 n À 3a 2 n R þ 1 2 a n R 2 þ 2a n R 2 À 3 4 R 3 À 2a 3 n À 2a 2 n R þ a n R 2 À a n R 2 À 1 2 R 3

X. Cai et al.

The traditional weight model considers that the smaller the hop count, the stronger the influence on unknown nodes. However, this viewpoint ignores the relationship between the weight and the errors, because the convergence is not analyzed. Based on this deficiency, this study constructs the mathematical model based on the weight and errors, and the convergence of the error is analyzed in the subsection 3.2. And the weight model is expressed as follows:

where n denotes the total number of ANs,d i denotes the weight model, and it means the larger the theoretical error, the smaller the value of the weight.

Then, the weight model is normalized, as shown in Eq. (15).

Thus, the objective of localization is expressed as:

Inspired by the traditional weight model, a weight model based on error variation was established and proved to be convergent. And this study solves this mathematical weighted DV-hop with genetic algorithm, named the MW-GADV-hop. The implementation of MW-GADV-hop is shown in Algorithm 1. Weight convergence analysis of DV-hop localization algorithm with GA 5 Simulation results

To test the performance of the proposed weight model, experimental simulations were conducted in MATLAB 2016a. Then, we analyzed the performance of the algorithm and compared it with the DV-hop, TW-GADV-hop (Sharma and Kumar 2018) , TW-PSODV-hop (Shi et al. 2019) , and FTF-BADV-hop (Cai et al. 2019a) . And the parameters are listed in Table 1 .

To evaluate the performance proposed algorithms, this study uses the average localization error (ALE) as the evaluation criteria, as follows: The main purpose of this study is to construct a mathematical model of weight based on the traditional weight concept and to prove the convergence of the model, instead of creating a new weight model. Therefore, our weight model should theoretically have similar positioning performance to the traditional weight model. In order to test the positioning performance, we execute the algorithm within the different network topologies, as shown in Fig. 5 , where the '.' denotes the UNs and the '*' denotes the ANs.

Obviously, the network topology contains the C-shaped, O-shaped and X-shaped networks. Table 2 and Fig. 6 show the simulation results with the different radii. From the distribution of the smallest error in Table 2 , the MW-GADV-hop proposed in this paper does not show outstanding positioning advantages. And it has similar performance to other DV-hop algorithms solved by optimization algorithms (FTF-BADV-hop, TW-PSODVhop, and TW-GADV-hop) in different network topologies. Obviously, in Fig. 6 , DV-hop always maintains the maximum positioning error with different radii. And in C-shaped and X-shaped networks, MW-GADV-hop is significantly better than TW-GADV-hop solved by the same genetic algorithm. Table 3 and Fig. 7 show the simulation results with the different numbers of nodes. From Table 3 , MW-GADVhop always maintains the minimum positioning error in O-shaped and X-shaped networks. And compared with DV-hop algorithm, the errors of MW-GADV-hop dropped by 33.64%, 20.81%, and 11.41%, respectively. From Fig. 7 , in C-shaped network, the positioning performance of MW-GADV-hop is inferior to TW-GADV-hop, but similar to the FTF-BADV-hop and TW-PSODV-hop. Table 4 and Fig. 8 show the simulation results with the different numbers of ANs. From Table 4 , the performance of MW-GADV-hop is slightly inferior to TW-GADV-hop in C-shaped network and superior to FTF-BADV-hop, TW-PSODV-hop, and TW-GADV-hop in other networks. From Table 5 shows the time complexity of these algorithms, where the MaxG denotes the maximum generation and NP indicates the number of population in the algorithms. From Table 5 , it can observe that the time complexity of the TW-GADV-hop and MW-GADV-hop is similar, and they are superior to the time complexity of the FTF-BADV-hop and TW-PSODV-hop. Therefore, our algorithm has higher timeliness than other algorithms during the location process. Figure 9 shows boxplot analysis of the results, and this figure exhibits the distribution of the simulation results. And the 'mean error' denotes the mean of the results of thirty runs, and the 'Whisker lower bound' and 'Whisker up bound,' respectively, denote the minimum and maximum error. From Fig. 9 , FTF-BADV-hop has the smallest error interval; however, although the error interval of MW-GADV-hop is larger than FTF-BADV-hop, the error distribution interval is lower, which means MW-GADV-hop has higher reliability. In C-shaped network, MW-GADVhop is inferior to TW-GADV-hop.

In this study, to explore the convergence of traditional weight models, we analyze the communication principle of sensor nodes. According to the traditional weight models, this study constructs a mathematical weight model based on the node communication features. Then, we analyze the convergence of the model and prove that when the number of hop count tends to infinity, the error of the model converges to 1/4R (where the sensor nodes are following the uniform distribution in the detection region and needs to have enough nodes). Finally, to test the model performance of this model, this algorithm is widely tested on different complex networks. The simulation results illustrate that the performance of this model is similar to other algorithms on the C-shaped network, and it is superior to other algorithms on the O-shaped and X-shaped networks. Although the model achieved better positioning performance and proved to be convergent, we notice that some results do not converge to 1/4R. Therefore, we will explore a more reasonable and generalized weight model based on the communication principle of nodes to achieve better positioning performance.

Security and privacy issues in wireless sensor networks for healthcare applications

Internet of things: a survey on enabling technologies, protocols, and applications

What will 5G be?

Five disruptive technology directions for 5G

Fast triangle flip bat algorithm based on curve strategy and rank transformation to improve DV-Hop performance

Multiobjective three-dimensional DV-Hop localization algorithm With NSGA-II

Research on improved DV-HOP localization algorithm based on weighted least square method

A novel oriented cuckoo search algorithm to improve DV-Hop performance for cyber-physical systems

Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems

Genetic algorithm in search, optimization, and machine learning

Internet of things (IoT): a vision, architectural elements, and future directions

Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks

Multiobjective optimization-based DVhop localization using NSGA-II algorithm for wireless sensor networks

A weighted DV-hop localization scheme for wireless sensor networks

Optimization of DV-hop localization algorithm in hybrid optical wireless sensor networks

An improved DV-Hop localization algorithm based on evolutionary algorithms

DV based positioning in Ad Hoc networks

Improved range-free localization for three-dimensional wireless sensor networks using genetic algorithm

An improved DV-Hop scheme based on path matching and particle swarm optimization algorithm

Radiological findings from 81 patients with COVID-19 pneumonia in Wuhan, China: a descriptive study

Two novel DV-hop localization algorithms for randomly deployed wireless sensor networks

A Gaussian error correction multi-objective positioning model with NSGA-II

Improved normalized collinearity DV-hop algorithm for node localization in wireless sensor network

Clinical course and risk factors for mortality of adult inpatients with COVID-19 in Wuhan, China: a retrospective cohort study

Conflict of interest The author declares that they have no conflict of interest.Ethical approval This article does not contain any studies with human participants performed by any of the authors.Informed consent Informed consent was obtained from all individual participants included in the study.