TMCnet News
CESILA: Communication Circle External Square Intersection-Based WSN Localization Algorithm [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Localization algorithm is one of the key technologies of WSN (wireless sensor networks), and there are two kinds of WSN localization algorithm, distance-based and distance-free algorithms. APIT (approximate point in time) is a distance-free algorithm which is not depends on hardware and has a relative low localization error rate. But there are two obviously shortages of APIT, firstly, the average cover rate is not 100 %, and it will decrease with the communication radius dramatically; secondly, the average cover rate will be lower and the localization error rate will be higher when there are obstacles in distribution environment. In order to solve the problem above, this paper proposed a new localization algorithm-CESILA (Communication Circle External Square Intersection-Based Localization Algorithm), this algorithm can decrease the localization error by experience parameters, and can guarantee cover rate by external square intersection. Experiment shows that the average localization error rate is 5 % lower than APIT algorithm in regular distribution environment, and 7 % lower than APIT in environment with obstacles; the cover rate is 100 % in any case. Copyright © 2013 IFSA. Keywords: WSN, Localization algorithm, APIT, CESILA, Localization error rate, Localization cover rate, Different distribution. (ProQuest: ... denotes formulae omitted.) 1. Introduction WSN (Wireless sensor network) is organized by nodes with characters of small size, low price and low computing power, which can organized automatically through wireless communications. There are mainly four key technology of WSN, they are routing, security, energy consumption and localization. Localization can provide support to other aspect; therefore, more and more researchers pay their attention to localization algorithm [1], There are two kinds of nodes in WSN, one kind called anchor nodes which can locate their location with hardware such as GPS and etc., the other kind called unknown nodes which cannot locate themselves with hardware. So, localization algorithm's goal is to locate the unknown nodes. Currently, the localization algorithms have been separated into two kinds [2-4]: distance-based localization algorithm and distance-free localization algorithm, distance-based algorithm evaluate unknown node's location with actual distances and angles of nodes which can be get by hardware, distance-free algorithm, the distance-free localization algorithm has been used widely since the distance-free algorithm is lower in price and simple to distribute. Classical distance-free localization algorithms including Centroid algorithm, DV-Hop algorithm [5], Amorphous algorithm [6] and APIT [7, 8] algorithm, APIT algorithm has lowest average localization error rate among them which is appropriate to the applications require high location accuracy such as military target tracking, mine personnel positioning and etc.. But there is a common character of these kinds of environment, that is full of obstacles in distribution environment, is it affect to the localization error rate and cover rate? Actually, because of the point in test, the average localization cover rate is low especially when the communication radius is short, and APIT algorithm is an obstacle-aware algorithm which means the localization error rate is high and cover rate is very high in distribution environment with obstacles. So, focusing on those disadvantages of APIT, this paper proposed a new localization algorithm which can decrease the average localization error rate and increase the cover rate especially in environment with obstacles. This paper is organized as follows: Sec 2, related work, performance of localization and principle of APIT are introduced, the simulations of APIT has been done in Sec 3, and the advantage and disadvantage of APIT is analysis through the simulations, in Sec 4, the principles of CESILA (communication circle external square intersection-based localization algorithm) is introduced, and the comparison and experimental result has been given in Sec 4, and included in Sec 5. 2. Related Work 2.1. Performance of Localization Algorithm Performances are used to evaluate an algorithm, according to the usage and characters of localization algorithm, the mainly performance is localization error rate, localization accuracy localization cover rate, grid density and ratio of localization error and cover rate, their definition are as follows: 1) Localization error rate. Localization error rate presents the degree of the difference between the estimated coordinates and actual coordinates, the localization error rate is calculate as formula 1. ... (1) In formula (1), N presents assemble of node that can be located by the localization algorithm, L presents the length of assemble of N, (xie) presents the estimated coordinates calculated by localization algorithm, (xit), is the actual coordinates when the node has been deployed. R presents the communication radius of the node. 2) Localization accuracy. Localization accuracy is opposite to localization error rate, the method of calculating localization accuracy is shown as formula (2). ... (2) 3) Localization cover rate. Localization cover rate presents the ratio of located nodes to all unknown node, thus, if a localization algorithm has a higher means it has a better performance, the monitoring region will be larger simultaneously, the cover rate is calculated by formula (3): ... (3) In formula (3), NResoved presents the number of located nodes, NUnknown presents the number of all unknown node, so cover rate is larger with NResoved . 4) Grid density. Grid density presents the relationship of distribution side length and grid length; it will be calculate by formula 4: ... (4) 5) Ratio of localization error rate and cover rate. Ratio of localization error rate and cover rate presents both the performance of localization error rate and cover rate, the Ratio will be calculated by formula (5). ... (5) Form the formula (5), we can conclude that the performance of the localization algorithm is proportional to ratio _ error _ cov er . 2.2. Principles of APIT Algorithm APIT (approximate point in test) algorithm is a distance-free WSN localization algorithm which is proposed by Tian He and etc., the principles of APIT is triangle approach, the principle is shown as Fig. 1, assume that there are n unknown node which can be communicate with the unknown node, the algorithm will traverse C_nA3 different triangles, and calculate the overlap of the triangles. As shown in Fig. 1, the centroid of the overlap polygon is the estimated coordinates of unknown nodes. The main phrase of APIT is as followings: 1) Anchor node information collecting phrase. Anchor node will broadcast message to its neighbor nodes, the message composed of anchor node ID, anchor node coordinates and the anchor node's signal strength and etc. The format of the message is shown as Fig. 2. The node (includes other anchor nodes and all unknown nodes) who receive the broadcast message will work as the rules, first, it will analysis the head of the message, and get the ID of the anchor node who broadcasted the message; then, it will judge if the anchor node already in its forwarding table, if it is, broadcast the message, but do not update the forwarding table; if it is not, also broadcast the message, but update the forwarding table with the content of the message. 2) Point in test (PIT) executing phase. After the first phase, every unknown node mastered much information of anchors nodes, so, the unknown node traverse every three of them and test if the unknown node in the triangle composed by the three anchor nodes. The principles of PIT is shown as Fig. 3(a) and Fig. 3(b), we can deduce form Fig. 3(a) that, if unknown node in the triangle, when the unknown node is close to one of the anchor nodes, it must be far away from the other two nodes; we also can deduce that if the unknown is out of the triangle shown as Fig. 3(b), when the unknown node is far away from one of the anchor nodes, it must be far away from the other two nodes simultaneously. However, the WSN node is static when it has been deployed in the most conditions, so we cannot locate the unknown node by moving the node, instead, we can judge if the unknown in the triangle by calculate its neighbors and their signal strength. 3) Grid scanning phase. If the unknown node in the triangle composed by some three anchor nodes, then the grids' count (initialized by 0) in the triangle will be crease by 1. 4) Centroid calculate phase. After the above three steps, we can find the entire grid who has the max count, then calculate the centroid of the polygon that composed by the grids. The formulas are as shown in (6) and (7). ... (6) ... (7) In the formula, presents the horizontal coordinate of the unknown node, presents the vertical coordinate of the unknown node, ( xi, yi ) and presents the coordinates of the grids with the max count. 3. Performance Analysis of APIT Localization Algorithm The greatest advantage of APIT is the low localization error rate, but the inherent characters of APIT decide that there are some obvious disadvantages as follows. 1) Low localization cover rate. There must be some unknown node not in any triangles, especially when the communication radius is short. 2) Localization error rate change with the distribution and environment dramatically, especially when the distribution environment with obstacles, because some nodes cannot communicate even their physical distance is very short. For example, this paper has analyzed the affection of localization error rate and cover rate of C-shape distribution environment. 3) localization error rate is related with grid density, in a certain region, localization error rate will be lower when the density is larger, but the localization error rate will go steady when the grid density is large enough, what's the value of it? In order to analyze the APIT algorithm, simulation and performance analysis has been done in this paper. The conditions of simulations are shown as Table 1. The analyzed performance of APIT include localization error rate, cover rate, relationship of grid density and localization error rate, C-shape affection of localization error rate and cover rate. Three groups of experiments have been done in the conditions show as Table 1. 1) Test the localization error rate. First, fixing the communication radius short for R, let R=100 m, ten experiments in different random distribution has been done, and the localization error rate is shown as Fig. 4 (a). Secondly, changing the grid density, the grid density changed from L/10,L/20,..., L/20 (L presents the side of the rectangle), the localization error rate is shown as Fig. 4 (b); Thirdly, changing the communication radius, let R equals 100, 200, 300,..., 1000 separately, the localization error rate is shown as Fig. 4 (c). As shown in Fig. 4 (a), the average localization error rate is around 40 % when the communication radius R=100 m; as shown in Fig. 4 (b), localization error rate is proportional to the grid density in a certain limitation, but it will be coming steady when the grid density is large enough; as shown in Fig. 4 (c), localization error rate is also proportional to communication radius, when the radius of the nodes equals with the side of the distribution areas, the localization error rate is approximated to 60 % which can be took as a limitation. The reason of this phenomenon is that more and more unknown nodes has been located as the communication radius is larger, but the localization error rate of these node are larger and larger, since the average localization error rate increased. 2) Test the localization cover rate. First, fixing the communication radius short for R, let R=100 m, ten experiments in different random distribution has been done, and the localization cover rate is shown as Fig. 5 (a); Secondly, changing the communication radius, let R equals 100, 200, 300, ..., 1000 separately, the localization cover rate is shown as Fig. 5 (b). As shown in Fig. 5 (a), the average localization cover rate is about 76 % - 90 %, the cover rate is increasing with communication radius, when the communications is about 400-500 m, the cover rate can be reach 100 %. 3) Test the affection of the different distributions of APIT's localization error rate and cover rate, the condition of the experiment are shown as table 1, the average localization error rate is shown as Fig. 6 (a), and the average rate is shown as Fig. 6 (b), the horizontal coordinate of both Fig. 6 (a) and Fig. 6 (b) presents the communication radius. As shown in Fig. 6(a), the localization error rate in C-shape distribution is higher than the one in Rectangle-shape, and as shown in Fig. 6(b), localization cover rate of C-shape distribution is lower than the one of Rectangle-shape. Concluded from the above, the main disadvantages of APIT are: 1) Average localization error rate is proportional to communication radius; the value of the error rate is range from 40 % to 60 %. 2) The cover rate of APIT cannot reach 100 % when the communication radius is less than half of the side of distribution area. 3) Not adaptive when there are obstacles in distributions environment, such as C-shape distribution, the localization error rate is higher and the cover rate is lower compared with the rectangle distributions. 4. Communication Circle External Square Intersection-Based Localization Algorithm Focusing on the three disadvantage of APIT algorithm, this paper proposed another geometry-intersection localization algorithm CESILA (Communication Circle External Square Intersection-Based Localization Algorithm), the principles of CESILA is shown as Fig. 7 (a) and Fig. 7 (b). As shown in Fig. 7 (a), the red circle presents unknown nodes, and the blue circle presents the anchor nodes, the black circle presents the forwarding nodes, R is short for communication radius, n presents the hops from unknown node to anchor node. As shown in the figure, the unknown node j must be in a circle of which the anchor node i as the center of the circle and with 2nR for the radius of the circle if unknown node j can communicate with anchor node i through n hops, so it must be in the external square of the circle. Thus we estimated the coordinates of the unknown node by the intersection of the rectangles, shown as Fig. 7 (b), which is easy to calculate and convenient to unified computing because the intersections is also rectangle. According to the principles of CESILA, the procedures of it are as follows: 1) Anchor node information collecting phrase, anchor nodes broadcast message with NodelD which is used to identify nodes from each other, Hop, and coordinates of itself. The format of the message is shown as Fig. 8. When the forwarding nodes receive the message, it will update forwarding table as formula (8) ...(8) In the formula, FT presents the forwarding table; the format of FT is the same as message format which is compose of ID of anchor node, hop from one anchor node to this node, and the coordinates of anchor node. The triple (i,hop+ l,(Pix,Piy)) presents information of anchor node i in forwarding tables. The value of FT (NodelD) returns the ID of anchor node, FT (I, Hop) returns hops from anchor node i to this node, nodes update their forwarding table according to rules defined by formula (8). 2) Grid partition and scanning phase. Assume that the distribution area is rectangle, thus the coordinates of each grid is calculated by formula (9). ...(9) As shown in formula (9), L presents the side of distribution; n presents the grid density, (fx (h J )> fy(h J )) presents the coordinates of the grid, and present the location of the grid (row and column), the count of each is initialized by 0, that is gk(i,j), k presents the ID of this unknown node, so, for each unknown node 's count gk (i, j) is calculated by formula (10). ...(10) As shown in formula (10), gk(i,j) presents anchor node h who can communicate with unknown node , m is the number of anchor node that can communicate with , if L(k)=(-1, -1) means the node is not located yet, the calculate method of gk(i,j) is shown as formula (11). ...(11) 3) Calculate the centroid of the intersection rectangle which has the max count of the grids, the calculate formula is shown as formula (12). ...(12) In the formula, xmax , xmin , ymax , ymin present the max horizontal coordinate, the min horizontal coordinate, the max vertical coordinate, and the min vertical coordinate among the grids with the max count separately. 5. Simulation Result In order to prove the correctness and effective of CESI localization algorithm, simulations have been done in this paper. CESILA is simulated in MATLAB 2012, and the comparison of CESILA and APIT algorithm is given, the result analysis mainly about localization error rate, localization cover rate, grid density's affection to localization error rate and cover rate, different distribution's affection to localization error rate and cover rate, the condition of the simulation is also shown as Table 1. In order to prove the performance of CESILA, five experiments have been done in this paper, and the comparison has been done between APIT and CESILA. 1) Fixing the communication radius short for R, let R=200 m, the results of localization error rate of the two algorithms in ten different Rectangle distributions are shown as Fig. 9. 2) Changing the communication radius, let R equals 100 meters, 200 meters, ... 1000 meters separately, the results of localization cover rate of the two algorithm in ten is shown as Fig. 10, the horizontal coordinate of the figure presents the communication radius of the node, and vertical coordinate presents the localization cove rate of the algorithm. Form the Fig. 9, we can get that the average localization error rate of CESILA is lower than APIT by about 5.9 %; and we can get form Fig. 10 that the cover rate of CESILA is 100 % whatever the experimental conditions are, while the cover rate of APIT is changing with the communication radius. 3) Changing the grid density, let the grid length form 100 meters, 90 meters, ... 0.5 meters, the values of the gird length is shown as the horizontal axis, grid density is in inverse proportion to grid length. The localization error rate in different grid density is shown as Fig. 11, we can get that the localization error rate is in inverse proportion to grid density in a certain range, and the localization error rate will tend to a constant when the gird density is large enough. 4) Fixing the communication radius let R=200 meters, the localization error rate has been concluded in Rectangle distribution and C-Shape distribution, the result is shown as Fig. 12. Form Fig. 12, APIT is a distribution aware localization algorithm, and its localization error rate is higher when the node is distributed in C-shape distributions, while CESILA is not a distribution aware localization algorithm, and its localization error rate in C-shape distributions is the same as the one in Rectangle distributions. 5) Changing the communication radius R, let R equals 100 meters, 200 meters, 300 meters,..., 1000 meters separately, the cover rate of the two algorithms are shown as Fig. 13. Form Fig. 13, we can get that APIT is a distribution aware localization algorithm, and its localization cover rate is lower when the node is distributed in C-shape distributions, while CESILA is not a distribution aware localization algorithm, and its localization cover rate in C-shape distributions is the same as the one in Rectangle distributions. 6. Conclusion The research of the this paper is about one of the key technology of WSN, that is localization algorithm, this paper analyzed and summarized the disadvantages of APIT according to the problem of low cover rate of APIT. In order to solve the problem, a new localization algorithm-CESILA has been proposed in this paper, the principles of CESILA is the communication external square intersection method. In addition, the simulations and performance analysis has been done in this paper, the simulation results show that the localization error rate of CESILA is lower than APIT by about 5.9 %, and the cover rate of the CESILA is 100 % in any conditions. However, CESILA is limited by parameters, for example, the cover rate of CESILA might reach 100 % and has a lower localization error rate when the one each side of the square is less than 2nR, so what is the optimized value of the one each side of the square will be further research in future work. Reference [1] . M. B. Srivastava, R. Muntz and M. Potkonjak, Smart Kindergarten: Sensor-based Wireless Networks for Smart Developmental Problem-solving Environments, in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, July 2001, Rome, Italy, pp. 132-138. [2] . J. Li, J. Jannotti, D. S. J. DeCouto, D. R. Karger and R. Morris, A Scalable Location Service for Geographic Ad-Hoc Routing, in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, August 2000, Boston, Massachusetts, USA, pp. 120-130. [3] . K. Amouris, S. Papavassiliou, M. Li, A Position-Based Multi-Zone Routing Protocol for Wide Area Mobile Ad-Hoc Networks, in Proceedings of the IEEE Vehicular Technology Conference (VTC '99), May 1999, Houston, Texas, USA, Vol. 2, pp. 1365-1369. [4] . M. Mauve, J. Widmer and H. Hartenstein, A Survey on Position Based Routing in Mobile Ad-hoc Networks, IEEE Network Magazine, Vol. 15, No. 6, November 2001, pp. 30-39. [5] . Hongbin Tan, Feng Liu, Research and Implementation of APIT Positioning Algorithm in WSN, in Proceedings of the 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD'12), 2012. [6] . Amitangshu Pal, Localization Algorithms in Wireless Sensor Networks: Current Approaches and Future Challenges, Network Protocols and Algorithms, 2010, pp. 45-74. [7] . Yong Zhou, Xin Ao, Shixiong Xia, An Improved APIT Node Self-localization Algorithm in WSN, in Proceedings of the 7th World Congress on Intelligent Control and Automation, Chongqing, China, 25-27 June 2008, pp. 7582-7586. [8] . Ji Zeng Wang, Improvement on APIT Localization Algorithms for Wireless Sensor Networks, in Proceedings of the International Conference on Networks Security, Wireless Communications and Trusted Computing, 2009, pp. 719-723. Sun Hongyu, Fang Zhiyi, Qu Guannan College of Computer Science and Technology Jilin University Changchun, 130012, P. R. China E-mail: [email protected] Received: 13 June 2013 /Accepted: 25 October 2013 /Published: 30 November 2013 (c) 2013 International Frequency Sensor Association |