Computer Science
Computer Science-2021.gz:143423
Computer Science
f0424198406e7a15dbfde63739414339feb4b093
Low Power Fast and Accurate Localization Algorithm in Wireless Sensor Networks

: Finding precise node localization is one of the critical issues in wireless sensor networks (WSNs), as the nodes are generally deployed randomly in the area of interest and without location stamp of the event, there is no use of that particular information. In this paper, a range-free localization algorithm called Horizontal-Vertical (H-V) scan method is presented which works mainly on collinearity concept. This method firstly estimates the collinearity of anchor nodes and rules out those anchor nodes which are collinear for location estimation of target nodes. By ruling out collinear anchor nodes, location is calculated by other than these ruled out anchor nodes through trilateration method which improves the localization accuracy. A new trajectory is also proposed for this method which improves coverage, accuracy and time for calculating localization. Simulation results show that the proposed method performs better in terms of localization accuracy, than the existing similar range-free localization methods.


I. INTRODUCTION
Wireless sensor networks are widely used for large-scale networks having very small embedded devices called as sensor nodes with sensing, transmitting, receiving and computational capabilities [1][2][3]. These sensor nodes are small in size with limited power, memory and communication bandwidth. Therefore, efficient uses of these resources become necessary for proper working of WSNs for a long time. Sensor nodes are mostly expected to be aware of their positions in network area. For instance, the location of occurrence is essential in applications which are designed to detect some phenomena like fire detection. Further, since some routing protocols are position-based, that must know the position of each node in the network [1]. Therefore, calculating or obtaining the position of the nodes in the network is a challenge in WSNs which is called localization [2].
In recent years, a large body of research has been conducted regarding the estimation of the node position in the network area and several localization methods were employed in WSNs in this regard. As shown in Fig. 1, these methods are mainly categorized into centralized and distributed (self-localization) localization techniques. In the first technique, the localization process and its calculations are obtained by the Base Station while in the latter, each node separately calculates its position [3]. Therefore, different studies concentrated on anchor-based localization in which a few numbers of anchor nodes are equipped with GPS receivers [4].
However, energy consumption and overhead cost are reported as two main drawbacks of GPS based localization methods [5]. The localization methods can be divided into anchor-free or anchor-based methods based on the use of anchor nodes. Moreover, these anchor nodes can be static or mobile for traversing the network region [6]. Eventually, the localization algorithms which estimate and calculate the node positions are classified into range-free and range-based groups [7]. The position of nodes in rangefree techniques is estimated based on exchange information among nodes known as connectivity information [8]. However, the location of nodes in range-based techniques is obtained by distance or angle of multiple nodes in the network. Accordingly, these methods impose extra cost, volume and energy usage to the network, since they must calculate the distance or angle among nodes [9].
In range-free methods, the Distance Vector by Hop counting (DV-hop) algorithm [7] is considered as a standard technique for obtaining the necessary information for localization. In contrast, range-based methods use several approaches to calculate the distance or angle among nodes in order to estimate the location of each node. These techniques include the Time of Arrival ToA) [10], Time Difference of Arrival (TDoA) [11][12], Received Signal Strength Indicator (RSSI) [13], techniques for calculating distance and the Angle of Arrival of the signal (AoA) [14], technique for calculating angle ,and also hybrid methods that are combination of the abovementioned techniques [15], [16]. The present study focuses on random deployment of static sensor nodes which used one mobile anchor node as a reference node to calculate the nodes positions in network area.

II. RELATED WORKS
As previously mentioned, localization algorithms are categorized into range-based and range-free methods. The relevant localization algorithms presented in the literature are provided in the following paragraphs.
First, several studies in the area of the range-free method are discussed. Safa [23] proposed an algorithm based on the DV-hop method. Accordingly, the anchor nodes are located on a circle, or a semi-circle around the desired area in order to improve the localization accuracy. This placement strategy is suitable for military surveillance or tracking applications and environmental monitoring. The current E-ISSN 2581 -7957 CVR Journal of Science and Technology, Volume 20, June 2021 P-ISSN 2277 -3916 DOI: 10.32377/cvrjst2008 CVR College of Engineering study shares the calculation process among the nodes and the base stations, which increases the network traffic. Furthermore, K.F Ssu et al. [18] presented the HiRLoc localization algorithm. In this algorithm, nodes calculate the centroid which is related to the overlapping region of the antenna pattern as the position of the unknown nodes. The overlapping region can be reduced by changing the direction of the antenna and increasing/decreasing the power of transmission which enhance the localization accuracy. This method needs extra hardware and therefore increases the cost and power consumption. Moreover, Darakeh et al. [13] introduced the DCRL-WSN localization method which defines a ball-shaped extended bound for each node and takes advantage of the certainty rule for reducing this area. Then, a bounding box zone is estimated for every node (the unknown node) based on the radio radius of the anchor and extended bounds of the nodes by evaluating two constrained convex optimization problems. Additionally, Darakeh et al. [13] attempted to calculate the initial node position using convex optimization and then enhance the position of the nodes by two novel heuristic techniques for location correction. These two methods need plenty of anchor nodes to estimate the position and thus increase the cost and power consumption increment. As a result, recent studies have only used one mobile anchor node to reduce the cost and power consumption and sought to find the optimum path of this mobile anchor. Such a node that obtained its location with a GPS receiver and sends its location to other nodes when it traverses the network area based on predesigned trajectory. In this regard, Koutsonikolas et al. [15] suggested Hilbert, Double Scan and Scan paths. In Scan trajectory, the mobile anchor node travels along a single dimension (x-or ydirection) and sends its position packets, therefore it creates collinear position packets (i.e., packets which are sent by the anchor node when it travels on a straight line) which are not efficient for localization. However, in the Double scan, the mobile anchor moves in both x and y directions leading to an increase in the length of the path, but no collinear problems are raised. In the Hilbert trajectory, the path of the anchor node is curved which increases various turns to create more non-collinear packets. Accordingly, the path length is reduced compared to the Double Scan trajectory. Han et al. [16] used one mobile anchor node and suggested a hexagon trajectory for this node. Further, Huang et al. [17] proposed circular paths which include several concentric circles centered on the network area.
Furthermore, Han et al. [16] introduced a localization algorithm with a Mobile Anchor node based on Trilateration (LMAT) in order to increase the coverage area and accuracy. The results of the present study, reveal that the vertices of equilateral triangle were the best place for points in trilateration methods, thus, an anchor node's path was designed according to equilateral triangle shape, in addition, Z-curve method was proposed by Rezazadeh et al. [20]. Since the method was inspired from the shape of Z character, the anchor node trajectory was designed according to this shape to improve the accuracy, coverage area, and localization time. In this regard, Alomari et al. [20] suggested the H-curve path.

III. PROPOSED ALGORITHM
In this study, an accurate localization technique called H-V (Horizontal-Vertical) Scan method is introduced. The proposed method used one mobile anchor (beacon) node as a reference for unknown node to estimate the nodes positions in the network. This proposed method is known as Horizontal-vertical (H-V) scan Method, which is described as follows: Non-collinearity is a major challenge in localization techniques and most of the previous proposed methods have tried to reduce the collinear position packets. However, this study used the concept of collinearity and estimated the location of nodes by collinear position [18][19][20]. Therefore, this method requires collinear position packet to estimate the position of nodes accurately. Accordingly, the anchor node moves in a straight line in X or Y direction (horizontally or vertically) and broadcasts its position by the position packets according to SendIntervalTime parameter. As shown in Fig.  1, the position packets are received by the unknown nodes. Thus, the average of X positions exactly equals to the X position of the node if all of these received positions are exactly in the X direction and notice that their Y positions are equal. The same process is true for the Y direction. That is, the average of Y positions equals the Y position of the unknown node if the anchor node horizontally traverses around the node and broadcast its position [21]. Moreover, in this method, a new trajectory is designed for the anchor node based on the concept of the collinear position. Accordingly, anchor node traverses the network area vertically and horizontally in order to create the collinear position packets. Fig. 3 illustrates this trajectory called Horizontal-Vertical Scan path. This method separately estimates the X and Y locations of nodes, thus, it has two phases which are shown in Fig. 3.

A. Horizontal ScanningPhase
This phase calculates the X location of nodes in network area. To this end, each node needs collinear position in X direction, so mobile anchor node traverses the network area horizontally (Fig. 3) and broadcast position packets to unknown nodes that include only its X coordinate. Therefore, each unknown node stores the location of the anchor node since it enters into the coverage area of the anchor node until it gets out of that area. Unknown nodes store only the packets which are in their radio range (i.e. black packets in Fig. 3). Then each unknown node calculates the average of received positions to estimate the X coordinate of itself as follow:

B. Vertical ScanningPhase
Similar to the first phase and based on the collinearity concept, anchor node traverses the network area vertically and send its Y coordinate as a position packet, so the unknown node must calculate only the average of the received positions (i.e., Y location of anchor node) in order to estimate the Y coordinate of the node as follows: In this trajectory, the anchor node traverses to the outside of the network area when it reaches to the network borders since the position of the nodes is estimated by calculating the average of the all collinear positions. Therefore, this method can estimate the position of the unknown nodes which are placed at the network borders (Fig. 3). Further, the distance of two parallel lines is known as resolution (d) in anchor trajectory , which affects the localization accuracy.

IV. EVALUATION METRICS
Localization error is defined as the average and standard deviation error between the real and estimated positions and is calculated as follows: To have a fair comparison, RWP [18] (which the anchor node randomly traversed the network area with constant speed), Circle path [17], LMAT [16], Z-curve [20], and Hcurve [25] methods, as well as the H-V scan method are implemented by MATLAB. All the above-mentioned methods apply one mobile anchor which traverses the network area based on their movement paths.
To evaluate the performance of the proposed localization methods, the proposed techniques were applied to the network including one mobile anchor node and N static nodes that were randomly distributed in network area. The simulation parameters were set as follows:   Further, the localization error of the H-V Scan method vs. the SendIntervalTime is depicted in Fig. 5. However, the localization error is reduced for the H-V Scan method by reducing the SendIntervalTime. This occurs since the number of position packets is increased by lowering the SendIntervalTime. Increasing the number of position packets results in reducing the localization error and improving the accuracy since the average of position packets is used to calculate the position (in each dimension).  The localization time is another critical parameter used to evaluate the performance of localization methods. This parameter is inversely proportional to the speed of the anchor node, thus the localization time decreases if the speed of the anchor node increases. The localization time of the H-V Scan method vs. the speed of the anchor node (V) is shown in Fig. 7. As expected, localization time reduced when the speed of the anchor node increased.

VI. CONCLUSIONS
H-V Scan localization technique was introduced in the present study in order to estimate the position of sensor nodes in the network area. This method suggested a new optimum trajectory for anchor node to traverse the network area. In addition, it used different algorithms to calculate the position of the nodes. H-V scan method is range-free method which used collinearity feature and calculated the location of nodes in the network based on collinearity concept. The simulation results indicated that this method can significantly improve the accuracy of localization with time overheads compared to other methods (i.e., RWP, Circle, LMAT, Z-curve, and H-curve) used in other studies.