Hybrid Location Algorithm Based on Cuckoo and Statistical Manifold

Xiaofeng Qin, Bin Xia^*, Liye Zhang, Xianzhi Zheng

School of Computer Science and Technology, Shandong University of Technology, Zibo, China.

DOI: 10.4236/jcc.2021.93008                

Abstract

To improve the location accuracy, a hybrid location algorithm based on cuckoo and statistical manifold method is proposed. It combines the cuckoo algorithm's strong global optimization ability and the statistical manifold’s accurate positioning ability fully. The simulation results show that the hybrid location algorithm has higher accuracy and reduces the influence of initial value selection on location accuracy.

Keywords

Hybrid Location Algorithm, Statistical Manifold Method, Cuckoo Algorithm, Location Accuracy

1. Introduction

The key of location service application for wireless sensor network is to obtain the accurate location of the node. For example, the location information of the node plays an important role in robot [1] [2] [3], modern agriculture [4] [5] and other fields. Therefore, improving the location accuracy is very important for the location service application. The disadvantage of traditional statistical manifold [6] [7] [8] [9] localization algorithm is that the location information between unknown nodes is not fully considered, which leads to incomplete location information and low location accuracy. Thus, an improved statistical manifold localization algorithm [10] which fully uses all the location information between unknown nodes is presented. Although the improved algorithm improves the location accuracy, its location accuracy depends heavily on the initial value. Meanwhile, the cuckoo algorithm [11] [12] [13] [14] [15] is a new intelligent bionic algorithm based on the cuckoo’s Levy flight and parasitic breeding mechanism, which can provide a good initial value for the improved statistical manifold algorithm. In view of this, a new hybrid location algorithm is proposed in this paper, which makes full use of the global optimization ability of the cuckoo algorithm and the high-precision location ability of the statistical manifold algorithm to optimize the overall location performance.

2. Cuckoo Algorithm

Cuckoo algorithm [16] is a population intelligent optimization algorithm. Its core idea is to expand the search scope and search the optimal solution through the Levy flight and parasitic breeding mechanism of the cuckoo.

Suppose that the cuckoo algorithm satisfies the following three conditions:

1) Each cuckoo can only lay one egg at a time, and the nest chosen for storage is random.

2) In the process of randomly searching for available nests, the best nest to keep the eggs was selected.

3) Let the probability of cuckoo eggs being found by the nest host be P. When the exotic eggs are found, the host will abandon the nest and find another place to rebuild the nest.

Assuming the above three conditions are satisfied, the updating formula of the nest’s location is as follows:

$X_n^{\left(t+1\right)}=X_n^{\left(t\right)}+a\oplus L\left(\lambda \right),n=1,2,\cdots ,N$ (1)

where $X_n^{\left(t\right)}$ represents the nth nest’s position of the tth generation; $X_n^{\left(t+1\right)}$ represents the nest’s position of the new generation; $\oplus$ represents the point-to-point multiplication operation; $\alpha$ is used to define the search range of the step size, and its value follows the normal distribution; $L\left(\lambda \right)$ represents the flight path.

3. Location Algorithm Based on Statistical Manifold

In the location region, $\left(x_i,y_i\right),i\in \left(1,2,\cdots ,I\right)$ is the location of the unknown node and $\left(u_k,v_k\right),k\in \left(1,2,\cdots ,K\right)$ is the location of the anchor node. According to the measurement distance between the unknown node and all nodes, the location model is established

$\{\begin{array}{l}\begin{array}{l}{d^{\prime }}_{i,j}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}+{e^{\prime }}_{i,j},\\ i<j,i=1,2,\cdots ,I;j=2,3,\cdots ,I\end{array}\}\\ \text{Distancebetweenunknownnodes}\\ \begin{array}{l}{d}_{i,k}=\sqrt{{\left(x_i-u_k\right)}^2+{\left(y_i-v_k\right)}^2}+e_{i,k},\\ i=1,2,\cdots ,I;k=1,2,\cdots ,K\end{array}\}\\ \text{Distancebetweenunknownnodeandanchornode}\end{array}$ (2)

where ${d^{\prime }}_{i,j}$ and $\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ represent the measurement distance and the true distance between the unknown node $\left(x_i,y_i\right)$ and the unknown node $\left(x_j,y_j\right)$ respectively; ${e^{\prime }}_{i,j}$ represents the measurement error. $d_{i,k}$ and

$\sqrt{{\left(x_i-u_k\right)}^2+{\left(y_i-v_k\right)}^2}$ represent the measurement distance and the true distance between the unknown node $\left(x_i,y_i\right)$ and the anchor node $\left(u_k,v_k\right)$ respectively; $e_{i,k}$ represents the measurement error.

Let $X={\left[x_1,y_1,\cdots ,x_I,y_I\right]}^{\text{T}}$ and $d={\left[d_{11},d_{12},\cdots ,d_{I,K},{d^{\prime }}_{1,2},{d^{\prime }}_{1,3},\cdots ,{d^{\prime }}_{\left(I-1\right),I}\right]}^{\text{T}}$, so the location model can be expressed as

$d=\Phi \left(X\right)+e\left(e~N\left(0,{\Sigma }_w\right)\right)$ (3)

where ${\Sigma }_w$ is the covariance matrix of the measurement error. The distribution of location model in (3) can be arranged into the form of bending index distribution

$p\left(d/X\right)=\exp \left\{C\left(d\right)+{\theta }^{\text{T}}\left(X\right)F\left(d\right)-\phi \left(\theta \left(X\right)\right)\right\}=p\left(d/\theta \left(X\right)\right)$ (4)

where $\theta \left(X\right)$ is the natural parameter; $F\left(d\right)$ is the sufficient statistic of $\theta \left(X\right)$ ; $\phi \left(\theta \left(X\right)\right)$ is the potential function of the distribution. Through the iterative calculation of the following formula, the estimated location can be obtained [10]

$X^{\left(k+1\right)}=X^{\left(k\right)}+\lambda G^{-1}\left(X^{\left(k\right)}\right)\nabla {\theta }^{\text{T}}\left(X^{\left(k\right)}\right)\times \left[F\left(d\right)-\eta \left(X^{\left(k\right)}\right)\right]$ (5)

where $\lambda$ is the iteration step; $G\left(X\right)$ is the metric tensor of the manifold; $\eta \left(X\right)$ is the expected parameter of the distribution.

4. Hybrid Location Algorithm

The hybrid algorithm based on cuckoo and statistical manifold improves the positioning accuracy by taking advantage of all the distance information. Firstly, the cuckoo algorithm is used to obtain the initial values of all unknown nodes. Then, based on the initial values, the statistical manifold algorithm is used to obtain the final values. The specific steps are as follows:

Step 1. Let i = 1.

Step 2. Assume that the number of nests is N, and the position of the nth nest is $X_n^{\left(l\right)}=\left(x_n^{\left(l\right)},y_n^{\left(l\right)}\right)$. The corresponding fitness function is defined as:

$F_n^{\left(l\right)}={\displaystyle \underset{k=1}{\overset{K}{\sum }}\sqrt{{\left(x_n^{\left(l\right)}-u_k\right)}^2+{\left(y_n^{\left(l\right)}-v_k\right)}^2-d_{n,k}^2}}$

where l is the iteration number, $\left(u_k,v_k\right)$ is the coordinate of the kth anchor node, and $d_{n,k}$ is the distance from the nth nest to the kth anchor node.

Step 3. Calculate the fitness value corresponding to the nest’s location, and search the best location $X^{\ast }$.

Step 4. A new nest’s location $X_n^{\left(l+1\right)}$ is generated by Levy flight mode, and the optimal location $x^{\ast }$ is obtained according to the corresponding fitness value $F_n^{\left(l+1\right)}$.

Step 5. The new nest’s location generated by random walk mode replaces the bad nest’s location discarded by probability p. Then, update the nest’s location of the new generation, and search the optimal location $x^{\ast }$.

Step 6. Compare the fitness value $F_n^{\left(l+1\right)}$ of the new generation with that of the best location $X^{\ast }$. If the fitness value of the new generation is better, replace the location $X^{\ast }$ with the location $x^{\ast }$.

Step 7. Keep the best nest’s location. If the number of iterations is reached, proceed to the next step; otherwise, go to step 4.

Step 8. If all the unknown nodes have been calculated, proceed to the next step; otherwise, turn to step 2 and calculate the initial location of the i + 1 th unknown node.

Step 9. The initial value $\left({\hat{x}}_1,{\hat{y}}_1,\cdots ,{\hat{x}}_I,{\hat{y}}_I\right)$ of all unknown nodes is obtained by cuckoo algorithm, and then the iteration step is $\lambda$, set $k=0$.

Step 10. Iteration loop.

while $e^{\left(k\right)}>\epsilon$

$X^{\left(k+1\right)}=X^{\left(k\right)}+\lambda {\left[{\nabla }_X\Phi \left(X^{\left(k\right)}\right)\right]}^{-1}\left[d-\Phi \left(X^{\left(k\right)}\right)\right]$ (6)

$G\left(X^{\left(k+1\right)}\right)={\nabla }_X^{\text{T}}\Phi \left(X^{\left(k+1\right)}\right){\Sigma }_w^{-1}{\nabla }_X\Phi \left(X^{\left(k+1\right)}\right)$

$e^{\left(k+1\right)}=\Vert X^{\left(k+1\right)}-X^{\left(k\right)}\Vert ,k+1\to k$

end

The final iteration result according to formula (6) is the estimated location. Using the proposed method, the location of all unknown nodes can be calculated simultaneously. The flow chart of the hybrid algorithm is shown in Figure 1.

5. Analysis of Simulation Results

In order to demonstrate the performance of the proposed method, we perform a

Figure 1. The flow chart of the hybrid algorithm.

simulation study, and the simulation parameters are shown in Table 1. The location error is defined as

${\displaystyle \underset{i=1}{\overset{I}{\sum }}\sqrt{{\left({\hat{x}}_i-x_i\right)}^2+{\left({\hat{y}}_i-y_i\right)}^2}}/I$

where $\left({\hat{x}}_i,{\hat{y}}_i\right)$ is the estimated location of the unknown node.

Figure 2 shows the influence of the variance of the measurement error on the location error. As can be seen from Figure 2, the hybrid algorithm uses the initial value provided by the cuckoo positioning, which leads to its location error is significantly smaller than that of the other two algorithms.

Figure 3 shows the influence of the nest number on the location error. Under the condition of the same nest number, the location accuracy of the hybrid algorithm is better than that of the cuckoo algorithm. With the increase of the nest number, the location error of the two algorithms decreases significantly. For example, the location error of the hybrid algorithm tends to be stable when nest number increases to 4.

Table 1. Simulation parameters.

Figure 2. Effect of the measurement error on the location error.

Figure 3. Effect of the nest number on the location error ( ${\sigma }^2=1$ ).

Figure 4. Effect of the maximum iteration number on the location error ( ${\sigma }^2=1$ ).

Figure 4 shows the influence of the maximum iteration number on the location error. Under the condition of the same iteration number, the location accuracy of the hybrid algorithm is better than that of the cuckoo algorithm. With the increase of the maximum iteration number, the location error of the two algorithms decreases significantly. For example, when the maximum iteration number increases to 20, the location error of the cuckoo algorithm tends to be stable.

6. Conclusion

A hybrid location algorithm based on cuckoo and statistical manifold method is proposed, which fully uses all the location information between unknown nodes. The simulation results show that the hybrid localization algorithm can reduce the impact of ranging error on the positioning accuracy.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grant 62001272, in part by Shandong Provincial Natural Science Foundation, China (ZR2019BF022).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Wu, P., Luo, Q. and Kong, L. (2017) Cooperative Localization of Network Robot System Based on Improved MPF. IEEE International Conference on Information & Automation, Macau, 18-20 July 2017, 796-800. https://doi.org/10.1109/ICInfA.2016.7831928
[2]	Qin, M., Wan, X., Shao, Y. and Li, S. (2018) The Comparison between FTF-VO and MF-VO for High Accuracy Mobile Robot Localization. 2018 International Conference on Robots & Intelligent System (ICRIS), Changsha, 26-27 May 2018, 48-51. https://doi.org/10.1109/ICRIS.2018.00020
[3]	Hafez, O.A., Arana, G.D., Chen, Y., Joerger, M. and Spenko, M. (2020) On Robot Localization Safety for Fixed-Lag Smoothing: Quantifying the Risk of Misassociation. 2020 IEEE/ION Position, Location and Navigation Symposium (PLANS), Portland, 20-23 April 2020, 306-317. https://doi.org/10.1109/PLANS46316.2020.9110126
[4]	Lian, J., Wang, D. and Hui, X. (2012) Intelligent Search Algorithm for Modern Tobacco Agriculture. Proceedings of the 10th World Congress on Intelligent Control and Automation, Beijing, 6-8 July 2012, 823-826. https://doi.org/10.1109/WCICA.2012.6357992
[5]	Mekala, M.S. and Viswanathan, P. (2017) A Novel Technology for Smart Agriculture Based on IoT with Cloud Computing. 2017 International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC), Palladam, 10-11 February 2017, 75-82. https://doi.org/10.1109/I-SMAC.2017.8058280
[6]	Cheng, Y.Q., Wang, X.Z., Caelli, T., Li, X. and Moran, B. (2011) Optimal Nonlinear Estimation for Localization of Wireless Sensor Networks. IEEE Transactions on Signal Processing, 59, 5674-5685. https://doi.org/10.1109/TSP.2011.2166547
[7]	Cheng, Y.Q. (2012) Information Theory and Geometric Methods of Radar Signal Processing. Ph.D. Dissertation, University of Defense Technology, Changsha, 118-120.
[8]	Akaho, S., Hino, H. and Murata, N. (2019) On a Convergence Property of a Geometrical Algorithm for Statistical Manifolds. 26th International Conference, ICONIP 2019, Sydney, 12-15 December 2019, Part V, 262-272. https://doi.org/10.1007/978-3-030-36802-9_29
[9]	Cui, P., Wang, X. and Yang, Y. (2020) Statistics Manifold Learning Approach and Its Application to Non-Gaussian Process Monitoring. Chinese Control Conference, Shenyang, 27-29 July 2020, 4054-4059. https://doi.org/10.23919/CCC50068.2020.9189523
[10]	Xia, B., Yuan, W.H., Xie, N. and Liu, Q. (2018) A Localization Algorithm Based on Statistical Manifold. Journal of Huazhong University of Science and Technology (Natural Science Edition), 46, 21-24.
[11]	Cheng, J. and Xia, L. (2016) An Effective Cuckoo Search Algorithm for Node Localization in Wireless Sensor Network. Sensors (Switzerland), 16, 1390. https://doi.org/10.3390/s16091390
[12]	Aziz, M. (2017) Source Localization Using TDOA and FDOA Measurements Based on Modified Cuckoo Search Algorithm. Wireless Networks, 23, 487-495. https://doi.org/10.1007/s11276-015-1158-y
[13]	Zhang, L.P., Peng, F., Cao, P. and Ji, W.J. (2017) An Improved Three-Dimensional DV-Hop Localization Algorithm Optimized by Adaptive Cuckoo Search Algorithm. International Journal of Online Engineering, 13, 102-118. https://doi.org/10.3991/ijoe.v13i02.6358
[14]	Niu, G., Gao, J. and Du, T.H. (2020) Passive Radar Source Localization Based on Cuckoo Search NVTDOA. International Journal of Antennas and Propagation, 2020, Article ID: 1410692. https://doi.org/10.1155/2020/1410692
[15]	Abd EI Aziz, M. (2017) Source Localization Using TDOA and FDOA Measurements Based on Modified Cuckoo Search Algorithm. Wireless Networks, 23, 487-495. https://doi.org/10.1007/s11276-015-1158-y
[16]	Yang, X.S. and Deb, S. (2009) Cuckoo Search via Lévy Flights. World Congress on Nature and Biologically Inspired Computing, Coimbatore, 9-11 December 2009, 210-214. https://doi.org/10.1109/NABIC.2009.5393690