In wireless sensor networks (WSNs), the target positioning and tracking are very important topics. There are many different methods used in target positioning and tracking, for example, angle of arrival (AOA), time of arrival (TOA), time difference of arrival (TDOA), and received signal strength (RSS). This paper uses an artificial fish swarm algorithm (AFSA) and the received signal strength indicator (RSSI) channel model for indoor target positioning and tracking. The performance of eight different method combinations of fixed or adaptive steps, the region segmentation method (RSM), Hybrid Adaptive Vision of Prey (HAVP) method, and a Dynamic AF Selection (DAFS) method proposed in this paper for target positioning and tracking is investigated when the number of artificial fish is 100, 72, 52, 24, and 12. The simulation results show that using the proposed HAVP total average positioning error is reduced by 96.1%, and the positioning time is shortened by 26.4% for the target position. Adopting HAVP, RSM, and DAFS in target tracking, the positioning time can be greatly shortened by 42.47% without degrading the tracking success rate.
Keywords: WSNs; target positioning; target tracking; AFSA; region segmentation method
A wireless sensor network is a network system consisting of one to several wireless data collectors and a big number of sensors, and the communication mode between components is wireless communication. A wireless sensor network is a kind of ad hoc network. It is a distributed network that does not require fixed infrastructure. Each network node communicates directly with other nodes within its range. The packets are forwarded by nearby nodes or other nodes on the path from the source node to the destination node. In the absence of fixed infrastructure and central management, wireless ad hoc networks must be able to establish cooperation between nodes on their own. Network nodes must also be able to adapt to changes in the network and have a dynamic network topology. In other words, we can place any sensor or wireless data collector in the network, which saves considerable deploying costs and is very convenient to use. In the framework of the wireless sensor network, the sensor is designed for saving power, lower costs, being smaller in size, and sensing the environment. The sensor is like a small computer and equipped with simple sensing components, computing, and wireless transmission devices. The sensing elements can detect the things we are interested in in the environment, such as temperature, light source, etc., and after simple calculation processing of the collected data, through the wireless transmission device, the data are sent back to the data collector. Finally, according to the data collected by the data collector, different applications can be developed such as military surveillance, environmental detection, smart home, and target positioning and tracking [[
Wireless sensor network positioning estimates the position of sensors whose initial position information is unknown by using the absolute position information of a few sensors and measuring data such as distance and azimuth between sensors. Generally speaking, the positioning methods of wireless sensor networks can be divided into range-based and range-free types [[
This paper proposes the Hybrid Adaptive Vision of Prey (HAVP) method and the region segmentation method (RSM) for the target positioning and tracking methods in the wireless sensor network using AFSA combined with the received signal strength indicator (RSSI) channel model to improve the accuracy of target localization and tracking methods. At the same time, a dynamic artificial fish selection (DAFS) method is proposed for the target tracking system to improve the efficiency of target tracking. In addition, this paper also investigates the impact of the number of sensors on different target positioning and tracking methods.
The rest of this paper is as follows. Section 2 depicts the AFSA and RSSI model, and the system model is introduced in Section 3. Section 4 describes the simulation results, and discussions are made in Section 5. Finally, a conclusion is given in Section 6.
The AFSA was proposed by Xiao-Lei Li et al. in 2002 [[
In bodies of water where the number of fish is the largest is generally the place where the water is rich in nutrients. Fish can swim quickly and agilely in the water to find food, relying on information sharing among fish schools. The artificial fish swarm algorithm imitates the behaviors of a fish swarm, such as praying, swarming, and following, based on this feature and then achieves the purpose of seeking the best solution in the whole domain [[
In the AFSA, the state of the AFs is expressed as a vector
Preying behavior: Let the current state of ith AF be X
(
where Rand() is a random number between zero and one. In the problem of finding the maximum value, if
(
where
Swarming behavior: Let the current state of the AF be X
(
Following behavior: Assume that the current state of ith AF is X
(
Random behavior: random behavior is to find a direction randomly in the field of vision and compensate for preying behavior.
According to the previously described behavior, a movement strategy can be formulated. Each AF performs swarming and following behaviors, respectively. If it does not meet the movement requirements of the behavior, it carries out foraging behavior. If the movement requirements of the preying behavior are still not met, it carries out random behavior. After multiple moves to find the best solution in the whole domain, the AFSA process is shown in Figure 3.
The AFSA has five parameters, which are visual range Visual, step size Step, number of individuals M, number of tries Try_Number, and crowding factor δ [[
Visual: When the Visual is small because each individual can see a relatively small number of other individuals in the algorithm at the same time, the ability of the individual to carry out swarming and following behaviors decreases, but the chance of the individual to search the adjacent area will also increase. The chances of individuals performing preying behaviors and random behaviors will also increase at this time. On the contrary, when the Visual is larger, the chances of individuals executing following behaviors and swarming behaviors will increase, while preying and random behaviors will decrease. Overall, the larger the Visual, the easier it is for the individual to find the global optimum solution, but it may also cause oscillations around the global optimum solution.
Step: The step size affects the accuracy and speed of the convergence of the algorithm. If a larger step size is selected, it can help the individual to converge to the extreme value quickly, but it may cause the individual to oscillate back and forth around the global optimum solution in the later stage of convergence, thus affecting the accuracy of convergence. If you choose a smaller step size, the convergence speed will be slower, but its accuracy is relatively better.
M: The larger the number of individuals is, the more information the individuals can exchange, the higher the accuracy of convergence, and the stronger the ability to jump out of the local optimum solution, but the greater the amount of calculation for each iteration of the algorithm. Therefore, in practical applications, on the premise of satisfying stable convergence, the number of algorithm individuals should be reduced as much as possible.
Try_Number: If the number of tries increases, the ability of the individual to perform preying behavior will increase, and the probability of the individual random moving will decrease. However, for problems with prominent local optimal solutions, if there are too many tries, it is easy for the individual to fall into the vicinity of the local optimum solution, thus missing the global optimum solution. Therefore, for general problems, the number of tries can be appropriately increased to speed up the convergence speed. For the problem with prominent local optimal solutions, the number of tries can be reduced to increase the probability of random movement of the individual to avoid falling into the local optimum solution.
δ: The crowd factor affects the results of the individual following and swarming behaviors. By combining the crowd factor with the field of view, it is possible to limit the swarming size of the individuals and further decide whether to perform the following and flocking behaviors. In the follow-up simulation experiments, we will ignore the crowding factor. In other words, as long as the AF X
The RSSI channel model is also known as the Propagation Path Loss Model [[
(
where P
In general, the average loss
(
where n is the path loss index, which represents the path loss rate. In the natural environment, the interference received by the signal changes with the environment. Therefore, in the simulation analysis, we can only describe this phenomenon with logarithmic normal distribution, so the average power of the path can be expressed as
(
and the received power can be expressed as
(
where
This section will give a complete and detailed description of the AFSA-based wireless sensor network's target positioning and tracking methods. The RSSI channel model is used to estimate the distance between the target point and the individual in the algorithm. Relying on the AFSA to simulate the creature preying characteristics, the highest point of the individual moving to find the food source (RSSI value) is regarded as the estimated point. In addition, this thesis also discusses the impact of sensor arrangement and quantity on the system.
The AFs (mobile sensors) were arranged on a square plane with an area of 100 m × 100 m. After each AF performs the algorithm behavior, the point with the highest food concentration (RSSI value) is obtained through communication with each AF as the global best solution. After a while, if the current global best solution meets the stop search condition, the corresponding position of the current global best solution is the estimated point, as shown in Figure 4.
In Figure 4, N target points are generated randomly. The optimum solution of the current time is obtained through the algorithm's behaviors and compared with the global optimum solution. The bulletin board is a recording matrix with a size of 1
Because the step size and field of view of AFSA will affect the performance of the system to find the optimal solution, the method of adaptive step size is proposed in [[
(
Here, ζ is the convergence factor and is an integer greater than one, which determines the convergence time of the curve. The larger the value, the later the convergence of the field of vision and step length; Visual is the field of vision; Step indicates the step size. In general, the initial value of Visual is networkSize/5 (networkSize is the maximum search range). The Step is Visual/8 [[
In this paper, based on the composite adaptive artificial fish swarm algorithm (AAFSA4) in [[
In AAFSA4, the forward mode to the direction with a large fitness value is shown in Equation (
(
(
The region segmentation method (RSM) involves dividing a 100 m × 100 m square wireless sensor network into four equal zones and positioning an anchor node in the center of each zone. The mobile sensor is equally divided into four segments and placed in each region. The anchor nodes of these four regions receive signal strength from the target point, and it is used to determine the approximate location of the target point. The boundaries [X
Figure 6 is the AFSA target tracking flowchart [[
(
In this paper, two moving tracks, a snake track and a random track of target points, are designed in the target tracking method, as shown in Figure 7a,b. The moving speed is 4~7 m/s, so the students in the algorithm need to find the location of the target point within a limited number of moves. Therefore, the parameter setting of the algorithm is slightly different from the parameters of the algorithm in the target positioning method, such as step size and visual field. How to adjust the parameters in the algorithm so that the AFs can quickly find the target point is one of the problems discussed in this paper.
Due to the moving characteristics of the target in the target tracking system, the target's moving speed is 4~7 m/s. In other words, the AF needs to move as much as possible within one second and reach the set threshold value alpha, which affects the system's success rate. If the signal strength received by the AF is greater than or equal to alpha, it is considered that the AF has found the target position and ended this search. The information, such as the current estimated point position and fitness value, is recorded in the record matrix for subsequent success rate calculation. On the other hand, the AF can perform the algorithm behavior within one second. If the fitness value of any AF does not reach alpha within one second, the AF with the highest fitness value among all AFs in the algorithm is selected as the estimated point. Figure 8 is the flow chart of the movement restriction of AFs in the algorithm. Equation (
(
Here, S is the number of all estimated points reaching alpha. Record is the recording matrix, recording the fitness values of all estimated points. Total is the number of all estimated points.
For the AFSA target tracking system, a Dynamic AF Selection (DAFS) method is proposed in this paper to reduce the number of AFs used in the algorithm and reduce the search area to improve the efficiency of the target tracking system. This study assumes the target's moving speed is 4~7 m/s, and the distance between the current and the previous target positions is very close. The DAFS method selects the AFs within 20 m from the last estimate point and starts a new algorithm iteration. If there is no AF in the range of 20 m, the AFs within 30 m are selected. Otherwise, all AFs will be considered in the algorithm. In addition, if the fitness value of the estimated point is less than the correction factor beta, all the AFs will be used in the algorithm to prevent error propagation. The DAFS method can reduce the search area and the number of AFs used in the algorithm to improve the efficiency of the target tracking system. Figure 9 shows the procedure of the DAFS method [[
In this study, the hardware and software used for simulations are listed in Table 1 [[
In this paper, the AFSA was used with different numbers of AF for target positioning and tracking to investigate the impact of the number of AFs on the system. Additionally, the placement of the initial positions of the AFs was random deployment and the numbers of AF used in AFSA are 100, 72, 52, 24, 12, respectively, to address different applications in real-world environments.
The RSSI channel model parameters of the simulation experiment are shown in Table 2 [[
In order to calculate the error between the estimated point and the target point obtained by AFSA target positioning, the average error is calculated through Equation (
(
where N is the number of target points,
In this study, the performance of the proposed methods, RSM and HAVP, along with the adaptive step and adaptive vision methods, will be analyzed in terms of positioning accuracy. Various analysis modes are shown in Table 4. P1 and P2 are the traditional AFSA methods, and P3 to P8 are the proposed methods in this paper.
Table 5 shows the simulation results of the average error in random deployment, and the average positioning time is shown in Table 6. The average time is the average time required to locate a target point in 100 iterations using the MATLAB software calculation algorithm.
The methods proposed in this paper, such as RSM, HAVP, and DAFS, are added into the target tracking system, respectively. The analysis modes for the target tracking method are shown in Table 7 to analyze their influence on the system efficiency. In addition, in the simulation experiment, different numbers of AFs are placed in the sensor network for the simulation experiment of each analysis method, and the influence of the number of AFs in the algorithm on the system efficiency is discussed. K1 is a traditional method, and K2 to K8 are the proposed ones.
Table 8 shows the simulation results of the average tracking time, and the average tracking success rate is shown in Table 9. The average tracking time is the average time required to track a target point in 100 iterations using the MATLAB software calculation algorithm.
According to the simulation results in Table 5 and Table 6, some discussions for the target positioning system are as follows.
The average positioning error decreases as the number of AFs increases. The results in Table 10 were obtained based on the number of AFs. The average error is minimum at 100 AFs and becomes higher with the decrease in AFs. However, the average positioning time will increase with the increase in AFs because the more AFs there are, the longer the calculation time of the algorithm will be.
There is no significant difference between fixed step size and adaptive step size and visual field on positioning efficiency. According to Table 5 and Table 6, the values of all methods using fixed and adaptive step size are averaged, respectively, and the results are shown in Table 11. It shows that the simulation results of the fixed step size algorithm or the adaptive step size algorithm have little difference in the average positioning error and positioning time. The reason is that in the simulation environment of the wireless sensor network in this study, when there are a large number of AFs in the algorithm, whether it is a fixed or adaptive step size algorithm can satisfy the need to move AFs in the algorithm to the region of the global optimum solution within 100 iterations. On the contrary, when the number of AFs in the algorithm is fewer, such as reducing to 12, no matter the fixed step size or the adaptive step size, the AFs in the algorithm cannot move around the global optimum solution after 100 iterations.
RSM will increase the average error but greatly reduce the average positioning time. Table 12 shows the average error and positioning time of using and not using RSM. The average positioning error increases by about 26 cm, but the positioning time is shortened by 74.4%.
The HAVP method effectively improves the positioning error and positioning time. Table 13 shows the total average error and positioning time of using HAVP and not using HAVP. The average positioning error is reduced by about 96.1%, and the positioning time is shortened by 26.4%. If the analysis is carried out on whether to use RSM and HAVP, the results are shown in Table 14. It is obvious that using RSM will effectively improve the positioning time, but the positioning error will become worse. However, if the proposed HAVP is used, not only can the advantages of RSM to improve the positioning time be maintained, but the positioning error will not become worse.
For target positioning, the proposed AFSA algorithms, P7 and P8, combined with RSM and HAVP have better performance in both average error and average positioning time than the traditional AFSA methods, P1 and P2, in random deployment for target positioning. Especially in P8, the average positioning time is reduced by 81.9% compared with P2.
From the simulation results in Table 8 and Table 9, the further discussions for target tracking can be depicted as follows.
RSM can use less time to achieve a better tracking success rate when there are many AFs, and the tracking performance of the modes without RSM is better when the number of AFs is fewer. Table 15 shows the total average positioning time and success rate of using RSM and not using RSM, which shows that the average positioning time of the analysis mode with RSM is less than that of the analysis mode without RSM. However, as the number of Afs used decreases, the difference between the average positioning time using RSM and those without RSM is smaller. The reason is that, after using RSM, the number of AFs used at the same time is less than that without RSM, so an AF in the AFSA can obtain less information from other AFs at the same time, so the AF needs to perform more algorithmic actions to reach the global optimal solution. Therefore, when the number of AFs is 12, the average positioning time using the RSM is longer than that without using the RSM.
When the number of AFs is large, using DAFS can shorten the positioning time and maintain a good tracking success rate. Analysis mode K1 without DAFS and K5 with DAFS were used to analyze the impact of DAFS on the performance of the target tracking system, as shown in Table 16. It can be found that the larger the number of AFS, the more data the algorithm needs to process, and the longer the target position estimation time is, and after using DAFS to track the AFSA target, it can be found that the greater the number of AFs used, the shorter the average positioning time. The reason is that when the DAFS method performs the algorithm by selecting the AF around the last estimated point, a larger number of AFs in the algorithm can ensure that there is an AF around the last estimated point and vice versa. The fewer the number of AFs, such as 12, the probability of an AF around the last estimated point is relatively small, so the use of all AFs for algorithm behavior increases, which in turn leads to the average positioning time when the number of AFs is 12. On the contrary, it is longer; in addition, when the number of AFs is greater than 52, DAFS can achieve a good tracking success rate at a faster speed, but when the number of AFs is less than 52, the DAFS method will make the system performance poor.
The average performance of the related modes using HAVP is shown in Table 17. It shows that using HAVP alone can improve the tracking success rate without increasing the positioning time. When using both DAFS and RMS for target tracking, the average positioning time of K8 is shorter by 42.47% than that of the traditional one, K1, and the average success rate remains the same as that of K1.
In this paper, AFSA is used to study indoor space target positioning and tracking. The simulation results show that the greater the number of AFs used in algorithm, the better the accuracy of target positioning but the longer the time of target positioning. The HAVP method is proposed to improve the positioning error and positioning time in this paper. The simulation results show that, when using HAVP, the total average positioning error is reduced by about 96.1%, and the positioning time is shortened by 26.4%. In addition, the DAFS method is proposed in the target tracking system to further reduce the number of AFs used in the target tracking system. The simulation results show that when the number of AFs is large, using DAFS can shorten the positioning time and maintain a good tracking success rate. Moreover, HAVP can improve the tracking success rate without increasing the positioning time. If DAFS and RMS are used at the same time, the positioning time can be greatly shortened by 42.47%, and the original success rate of the conventional method can be maintained.
Graph: Figure 1 Flow chart of swarming behavior in AFSA.
Graph: Figure 2 Flow chart of following behavior in AFSA.
Graph: Figure 3 Flow chart of AFSA.
Graph: Figure 4 Flow chart of AFSA target positioning method.
Graph: Figure 5 Illustration of RSM region judgment.
Graph: Figure 6 Flow chart of AFSA target tracking.
Graph: Figure 7 Moving tracks of target points for the target tracking method: (a) snake track; (b) random track.
Graph: Figure 8 Procedure of AF movement restriction in the algorithm.
Graph: Figure 9 The procedure of DAFS method.
Table 1 Simulation equipment.
Name Specification OS Windows 7 Enterprise 64 bits CPU Intel(R) Core(TM) i5-4590 3.30 GHz RAM 8 GB MATLAB Edition R2015a
Table 2 Parameters of RSSI channel model.
Parameter Value Transmission Power 2 mW Carrier Frequency 2.4 GHz Path Loss Exponent 4.5 Reference Distance 0.5 m Antenna Gains 1 Standard Deviation 9 dBm
Table 3 AFSA parameters for target positioning and target tracking.
Parameter Value Target Positioning Target Tracking Network size 100 m 100 m Number of executions 100 Number of iterations 100 Number of sensors 100, 72, 52, 24, 12 Number of targets 10 1 Try number 100 Initial step Initial visual Minimum step 5 1,2 Minimum visual 50 1,2 Convergence factor 4 2 Threshold * −6.5 dBm Correction factor * −15 dBm
Table 4 Analysis modes for target positioning method.
Mode Condition Fixed Step Adaptive Step and Vision RSM HAVP P1 ✓ P2 ✓ P3 ✓ ✓ P4 ✓ ✓ P5 ✓ ✓ P6 ✓ ✓ P7 ✓ ✓ ✓ P8 ✓ ✓ ✓
Table 5 Average error of random deployment in target positioning.
Number of AF P1 P2 P3 P4 P5 P6 P7 P8 100 0.874 0.892 2.516 2.562 0.000 0.000 0.000 0.000 72 1.117 1.113 3.359 3.358 0.000 0.000 0.000 0.000 54 1.614 1.500 4.320 4.418 0.000 0.000 0.000 0.000 24 2.953 2.991 8.370 8.694 0.000 0.000 0.000 0.000 12 5.520 5.341 251.316 231.705 0.121 0.000 11.162 10.247 Average 2.416 2.367 53.976 50.147 0.024 0.000 2.232 2.049
Table 6 Average positioning time of random deployment in target positioning.
Number of AF P1 P2 P3 P4 P5 P6 P7 P8 100 12.986 13.790 3.406 3.191 9.184 10.018 2.382 2.363 72 8.916 9.613 2.203 2.541 6.546 7.642 1.749 1.650 54 6.634 6.750 1.624 1.787 4.778 4.996 1.362 1.236 24 2.974 3.085 0.860 0.782 2.108 2.236 0.676 0.732 12 1.326 1.352 0.174 0.206 1.049 1.176 0.308 0.290 Average 6.567 6.918 1.653 1.701 4.733 5.214 1.295 1.254
Table 7 Analysis modes for target tracking method.
Mode RSM HAVP DAFS K1 K2 ✓ K3 ✓ K4 ✓ ✓ K5 ✓ K6 ✓ ✓ K7 ✓ ✓ K8 ✓ ✓ ✓
Table 8 Average tracking time of random deployment in target tracking.
Number of AF K1 K2 K3 K4 K5 K6 K7 K8 100 0.081 0.058 0.076 0.040 0.041 0.032 0.040 0.026 72 0.065 0.041 0.067 0.030 0.038 0.034 0.041 0.028 54 0.061 0.043 0.061 0.033 0.051 0.048 0.040 0.032 24 0.044 0.039 0.046 0.023 0.109 0.098 0.042 0.038 12 0.041 0.064 0.037 0.058 0.123 0.109 0.048 0.044 Average 0.0584 0.049 0.0574 0.0368 0.0724 0.0642 0.0422 0.0336
Table 9 Average tracking success rate of random deployment in target tracking.
Number of AF K1 K2 K3 K4 K5 K6 K7 K8 100 99% 81% 100% 83% 100% 97% 100% 98% 72 99% 100% 100% 100% 99% 99% 98% 99% 54 100% 100% 100% 99% 95% 96% 97% 96% 24 97% 100% 99% 95% 85% 94% 96% 96% 12 94% 76% 100% 85% 85% 80% 95% 97% Average 97.8% 91.4% 99.8% 92.4% 92.8% 93.2% 97.2% 97.2%
Table 10 Total average error and positioning time when the number of AFs is 100, 72, 54, 24, and 12.
Number of AF Average Error (cm) Average Positioning Time (s) 100 0.849 7.272 72 1.121 5.081 54 1.467 3.638 24 2.839 1.658 12 66.064 0.741
Table 11 Total average error and positioning time of the fixed and adaptive steps.
Parameter Fixed Step Adaptive Step Average error (cm) 14.589 14.347 Average positioning time (s) 3.587 3.587
Table 12 Total average error and positioning time of using and not using RSM.
Parameter No RSM RSM Average error (cm) 1.185 27.750 Average positioning time (s) 5.866 1.490
Table 13 Total average error and positioning time of using and not using HAVP.
Parameter No HAVP HAVP Average error (cm) 27.861 1.074 Average positioning time (s) 4.237 3.120
Table 14 Average error and positioning time for methods using and not using RSM and/or HAVP.
Parameter No RSM + HAVP RSM HAVP RSM + HAVP Average error (cm) 2.36 53.36 0.01 2.14 Average positioning time (s) 6.76 1.71 4.97 1.27
Table 15 Total average positioning time and success rate of methods using or not using RSM.
Number of AF Average Positioning Time (s) Average Success Rate No RSM RSM No RSM RSM 100 0.060 0.039 99.8% 99.5% 72 0.053 0.033 99.0% 99.5% 54 0.053 0.039 98.0% 97.8% 24 0.060 0.050 94.3% 96.3% 12 0.062 0.069 93.5% 84.5%
Table 16 Average positioning time and success rate of modes K1 and K5.
Number of AF Average Positioning Time (s) Average Success Rate K1 K5 K1 K5 100 0.081 0.041 99% 100% 72 0.065 0.038 99% 99% 54 0.061 0.051 100% 95% 24 0.044 0.109 97% 85% 12 0.041 0.123 94% 85%
Table 17 Average positioning time and success rate for K1, K3, K7, and K8.
Parameter K1 K3 K7 K8 Average positioning time (s) 0.0584 0.0574 0.0422 0.0336 Average success rate 97.8% 99.8% 97.2% 97.4%
Conceptualization, C.-H.C. and Y.-F.H.; investigation, C.-H.C., C.-C.L. and Y.-F.H.; methodology, S.-H.L. and Y.-F.H.; software, C.-H.C. and C.-C.L.; supervision, C.-H.C. and Y.-F.H.; writing—original draft, C.-H.C., S.-H.L., C.-C.L. and Y.-F.H.; writing—review and editing, S.-H.L., C.-H.C. and Y.-F.H. All authors have read and agreed to the published version of the manuscript.
Not applicable.
The authors declare no conflict of interest.
By Shu-Hung Lee; Chia-Hsin Cheng; Chien-Chih Lin and Yung-Fa Huang
Reported by Author; Author; Author; Author