Localization In Wireless Sensor Network

Localization In Wireless Sensor Network

Anil Kumar H1, Manjunath CR2, Nagaraj GS3 ,Rajashekar. A4 1,4MTech 4thsem, Dept of CSE, SET, Jain University,

2Asst prof, Dept of CSE, JainUniversity, 3Prof,Dept of CSE, RVCE, VTU

Abstract:

Wireless sensor networks are particularly interesting in hazardous or remote environments, or when a large number of sensor nodes have to be deployed. Localization is one of the fundamental problems in wireless sensor networks (WSNs), since locations of the sensor nodes are critical to both network operations and most application level tasks. Monitoring applications define an important class of applications used in wireless sensor networks. In this paper, we attempt to present theoverview of various challenges, different techniques, and algorithms related to localization.

Keywords:Localization,Localizationtechnique

,Localization algorithm,Wireless sensor networks

1. Introduction

   Wireless Sensor Networks have emerged as one of the key enablers for a variety of applications such as environment monitoring, vehicle tracking and mapping, and emergency response. Sensors are deployed in a large physical environment where location information of each sensor is critical to the applications,

   e.g. habitat monitoring, target tracking, battlefield surveillance, etc[3]. However, localization remains a challenging problem in wireless sensor networks. Anchors nodes are sensors equipped with GPS receivers or having prior knowledge about their physical locations. The location information of anchors is used for multilateration, transformation of relative coordinates to absolute coordinates or constraints in mathematical programming-based algorithms. Distributed algorithms based on multilateration requires significant amount of anchors to maintain the accuracy of the solution. However the cost of anchors is much higher than a normal sensor. Furthermore, the placement of anchors also affects the performance of multilateration based methods.

   Localization

   Localization is the process by which sensor nodes determine their location, and is a mechanism for discovering spatial relationships between objects. The various approaches are considered to solve issue with respect to localization problem, with different assumptions consider base on the type of network and sensor capabilities. The assumptions includes like device hardware, signal propagation models, timing and energy requirements, and composition of network (homogeneous vs. heterogeneous), operational environment (indoor vs. outdoor), beacon density, time synchronization, communication costs, error requirements, and node mobility.However the assumption consideration depends on the application and parameters which includes accuracy, Cost, Power, Static Nodes and Mobile Nodes [8]. There are different wayto estimate location information with parameters and to distinguish the similarities and differences between different approaches.

   Challenges implementing localization

   WSN is a resourced constraint network, in order to avoid interference, the effective communication range is limited to some extent. The sensed data may arrive at the destination via multi-hop. The reliability of a routing path is not guaranteed, so the routing path between the data source and data sink may vary with time. In multi-hop routing path, to estimate the distance between a node and the beacons, the errors caused in these approximation have adverse impact on the accuracy of localization is WSN. Another factor influencing localization accuracy is the ranging errors. Whatever kind of ranging approaches is adopted, there will always exist some noise in the ranging measurements. Moreover, because the characteristics between each transmitter- receiver pair may not the same, this kind of un- uniformity between different modes also exerts negative impact on the accuracy of localization.

   Current aspects in localization [8]:

   Resource constraints: Nodes must be cheap to fabricate, and trivially easy to deploy. Deployment must be easy as well. The designers must actively work to minimize the power cost, hardware cost and deployment cost of their localization algorithms.

   Node density: Many localization algorithms are sensitive to node density. For instance, hop count based schemes general require high node density so that the hop count approximation for distance is accurate. Algorithms that depend on beacon nodes fail when the beacon density is not high enough in a particular region. When designing or analyzing an algorithm, algorithms implicit density assumptions is important, since high node density can sometimes be expensive if not totally infeasible.

   Environmental obstacles and terrain irregularities: Environmental obstacles and terrain irregularities can also wreak havoc on localization. For instance, in outdoor Large rocks can occlude line of sight, preventing TDoA ranging, or interfere with radios, introducing error into RSSI ranges and producing incorrect hop count ranges. Indoors, like walls can impede measurements as well. All of these issues are likely to come up in real deployments, so localization systems should be able to cope.

   Security: Security is the main issue in localization as the data is transferred from beacon node to anchor node then any of mobile beacons which is not secure, acting as original mobile beacons transmit false messages due to this an error will occur which is harmful for computation.

   Non convex topologies: Border nodes are a problem because less information is available about them and with the possibility of lower quality. This problem is exacerbated when a sensor network has a non-convex

   shape. Sensors outside the main convex body of the network can often prove un-localizable. Even when locations can be found, the results tend to feature disproportionate error.

   Localization systems [2]

   Localization systems can be divided into three distinct components:

   • Distance/angle estimation: This component is responsible for estimating information about the distances and/or angles between two nodes. This information will be used by the other components of the localization system.

   • Position computation: This component is responsible for computing a nodes position based on available information concerning distances/angles and positions of reference nodes.

   • Localization algorithm: This is the main component of a localization system. It determines how the available information will be manipulated in order to allow most or all of the nodes of a WSN to estimate their positions

2. Localization Techniques

   Measurement techniques in WSN localization can be broadly classified into three categories: AOA measurements, distance related measurements

   Angle of Arrival (AoA): AOA is defined as the angle between the propagation direction of an incident wave and some reference direction, which is known as orientation[5].Range information is obtained by estimating and mapping relative angles between neighbors make use of AoA for localization [3]. AoA estimates the angle at which signals are received and use simple geometric relationships to calculate node positions. When the orientation is 0 or pointing to the North, the AOA is absolute, otherwise, relative. One common approach to obtain AOA measurements is to use an antenna array on each sensor node[5].

   Fig 1 :Triangulation in AOA localization : (a) Localization with orientation information ;(b) Localization without orientation information

   AoA schemes are described where sensor nodes ar forwarding their bearings with respect to anchors, i.e. nodes which is assumed to know their own coordinates and orientations. Unfortunately, these methods require a strong cooperation between neighbor nodes, and they are prone to error accumulations. Anchor nodes with adaptive antennas are used to communicate with sensors located in different parts of a network. A similar concept assumes a single anchor in the center of a network sending an angle bearing. The other nodes calculate their coordinates with the aid of the bearing and some extra information from their neighbors. However, both these solutions also need some RSS data. The position of a sensor node is determined as an intersection of antenna sectors of different anchor nodes. More precise

   algorithms assume that sensors can receive exact AoA information from anchors. This can be accomplished if the anchors have directional antennas rotating with a constant angular speed. The sensors can estimate the AoA of the signal registering the time when the rotating beacon has the strongest power. However, the anchors with unrealistic radiation patterns are analyzed, the radio noise is not taken into consideration and the calculations are possible only for three anchors .The rotating antennas are too large for tiny anchor nodes. Generally, the main challenge of the AoA localization schemes for WSNs is the difficulty in achieving good accuracy while keeping the system simple and feasible to implement in pocket- size devices [6].

   Distance related measurements

   Distance related measurements include propagation time based measurements, time of arrival (ToA) measurements, and time difference-of-arrival (TDoA) measurements.

   Time of Arrival (ToA):TOA is a widely used technology to perform localization. To obtain range information using ToA, the signal propagation time from source to destination is measured. A GPS is the most basic example that uses ToA. To use ToA for range estimation, a system needs to be synchronous, which necessitates use of expensive hardware for precise clock synchronization with the satellite[3]. It is for example used in radar systems. The basic TOA technology describes the reference nodes and the blindfolded node, co-operating to determine the inter-node distances by using timing results. The blindfolded node will send a message to each of the reference nodes to measure the distance. The moment the blindfolded node transmits a message, it attaches a timestamp (t1), indicating the clock time in the blindfolded node at the start of the data transmission. At arrival of the message at the reference node, the clock time in the reference node is stored as timestamp (t2). The difference between timestamp (t1) and (t2) indicates the time needed for the signal to travel from the blindfolded to the reference node through the air [4]. The propagation time can be directly translated into distance, based on the known signal propagation speed. These methods can be applied to many different signals, such as RF, acoustic, infrared and ultrasound. TDoA methods are impressively accurate under line-of-sight conditions. But this line-of-sight condition is difficult to meet in some environments. Furthermore, the speed of sound in air varies with air temperature and humidity, which introduce inaccuracy into distance estimation. Acoustic signals also show multi-path propagation effects that may impact the accuracy of signal detection.

   Time Difference of Arrival (TDoA):To obtain the range information using TDoA, an ultrasound is used to estimate the distance between the node and the source. Like ToA, TDoA necessitates the use of special hardware, rendering it too expensive for WSNs[3].The propagation time can be directly translated into distance, based on the known signal propagation speed. These methods can be applied to many different signals, such as RF, acoustic, infrared and ultrasound. TDoA methods are impressively accurate under line-of-sight conditions. But this line-of-sight condition is difficult to meet in some environments. Furthermore, the speed of sound in air varies with air temperature and humidity, which introduce inaccuracy into distance estimation. Acoustic

   signals also show multi-path propagation effects that may impact the accuracy of signal detection[7]

   Received Signal Strength Indicator (RSSI): The energy of radio signal is an electromagnetic wave, which decreases as it propagates in space. As the signal propagates, its energy decreases with distance. RADAR is one of the first to make use of RSSI. RSSI has also been employed for range estimation, when the signal is received and have an estimate of the distance between sender and receiver.RSSI measures the power of the signal at the receiver and based on the known transmit power, the effective propagation loss can be calculated. After this by using theoretical and empirical models, this signal loss can be translated into a distance estimate[3], as used for RF signals. RSSI is a relatively cheap solution without any extra devices, as all sensor nodes are likely to have radios[8]

   Limitations for RSSI approach

   Radio propagation is affected by fading and shadowing. For an indoor application, thus will have an even more important effect, as the radio signal can be affected by the surrounding environment, and the reflections will create a multipath solution. The walls and the furniture will of course work as obstacles for the radio signal, but those are permanent obstacles. The received power at the reference distance for the model would vary. The performance, however, is not as good as other ranging techniques due to the multipath propagation of radio signals [7]

3. Localization algorithm

   Many localization algorithms have been proposed for WSNs. Localization algorithms can be categorized as

   1. Centralized vs. Distributed : based on their computational organization

   2. Range-Free vs. Range-Based : to determining the location of a sensor node

   3. Anchor-Based vs. Anchor-Free : based on whether or not external reference nodes (i.e., anchors) are needed

   4. Individual vs. Collaborative Localization : calculating node position

   Centralized vs. Distributed

   Localization algorithms can be categorized as centralized or distributed algorithms based on their computational organization.

   InCentralized algorithms:Sensor nodes send data to a central location where computation is performed and the location of each node is determined and sent back to the nodes[1]. In certain networks where centralized information architecture already exists, such as road traffic monitoring and control, environmental monitoring, health monitoring, and precision agriculture monitoring networks, the measurement data of all the nodes in the network are collected in a central processor unit. In such a network, it is convenient to use a centralized localization scheme. Once feasible to implement, the main motive behind the interest in centralized localization schemes is the likelihood of providing more accurate location estimates than those provided by distributed algorithms. Centralized localization is basically migration of inter-node ranging and connectivity data to a sufficiently powerful central

   base station and then the migration of resulting locations back to respective nodes [1].

   There exist three main approaches for designing centralized distance-based localization algorithms: multidimensional scaling (MDS), linear programming and stochastic optimization approaches. The advantage of centralize algorithms are that it eliminates the problem of computation in each node, at the same time the limitations lie in the communication cost of moving data back to the base station[7].The high communication costs and intrinsic delay.In most cases, costs increase as the number of nodes in the network increases, thus making centralized algorithms inefficient for large networks.

   MDS-MAP

   MDS-MAP consists of three steps.

   Step 1: the scheme computes shortest paths between all pairs of nodes in the region of consideration by the use of all pair shortest path algorithm such as Dijkstras or Floyds algorithm. The shortest path distances are used to construct the distance matrix for MDS.

   Step 2: the classical MDS is applied to the distance matrix, retaining the first 2 (or 3) largest eigenvalues and eigenvectors to construct a 2-D (or 3-D) relative map that gives a location for each node. Although these locations may be accurate relative to one another, the entire map will be arbitrarily rotated and flipped relative to the true node positions.

   Step 3: Based on the position of sufficient anchor nodes (3 or more for 2-D, 4 or more for 3-D), transform the relative map to an absolute map based on the absolute positions of anchors which includes scaling, rotation, and reflection. The goal is to minimize the sum of squares of the errors between the true positions of the anchors and their transformed positions in the MDS map.

   The advantage of this scheme is that it does not need anchor or beacon nodes to start with. It builds a relative map of the nodes even without anchor nodes and next with three or more anchor nodes; the relative map is transformed into absolute coordinates. This method works well in situations with low ratios of anchor nodes [8].

   A drawback of MDS-MAP is that it requires global information of the network and centralized computation.

   In Distributed algorithms: This algorithm distributes the computational load across the network to decrease delay and to minimize the amount of inter-sensor communication have been introduced.Each node determines its location by communication with its neighboring nodes. Generally, distributed algorithms are more robust and energy efficient since each node determines its own location locally with the help of its neighbors, without the need to send and receive location information to and from a central server. Distributed algorithms however can be more complex to implement and at times may not be possible due to the limited computational capabilities of sensor nodes [1].Similarly to the centralized ones, the distributed distance based localization approaches can be obtained as an extension of the distributed connectivity-based localization algorithm to incorporate the available inter-sensor distance information.In Distributed localizations all the relevant computations are done on the sensor nodes themselves and the nodes communicate with each other

   to get their positions in a network. Distributed localizations can be categorized into different classes.

   • Beacon-based distributed algorithms: Beacon- based distributed algorithms start with some group of beacons and nodes in the network to obtain a distance measurement to a few beacons, and then use these measurements to determine their own location.

   • Relaxation-based distributed algorithms: In relaxation-based distributed algorithms use a coarse algorithm to roughly localize nodes in the network. This coarse algorithm is followed by a refinement step, which typically involves each node adjusting its position to approximate the optimal solution.

   • Coordinate system stitching based distributed algorithms: In Coordinate system stitching the network is divided into small overlapping sub regions, each of which creates an optimal local map, then merge the local maps into a single global map.

   • Hybrid localization algorithms: Hybrid localization schemes use two different localization techniques such as proximity based map (PDM) and Ad-hoc Positioning System (APS) to reduce communication and computation cost

   • Interferometric ranging based localization: Radio interferometric positioning exploits interfering radio waves emitted from two locations at slightly different frequencies to obtain the necessary ranging information for localization.

   • Error propagation aware localization: When sensors communicate with each other, error propagation can be caused due to the undesirable wireless environment, such as channel fading and noise corruption. To suppress error propagation various schemes are proposed, like error propagation aware (EWA) algorithm [7].

   Range-Free vs. Range-Based

   Range Free:Range-free techniques use connectivity information between neighboring nodes to estimate the nodes position. Range-free techniques do not require any additional hardware and use proximity information to estimate the location of the nodes in a WSN, and thus have limited precision [1].Range-free localization never tries to estimate the absolute point to-point distance based on received signal strength or other features of the received communication signal like time, angle, etc. This greatly simplifies the design of hardware, making range- free methods very appealing and a cost-effective alternative for localization in WSNs. Amorphous localization, Centroid localization, APIT, DV-Hop localization, SeRLoc and ROCRSSI are some examples of range-free localization techniques [3].

   Range Based: Range-based techniques require ranging information that can be used to estimate the distance between two neighboring nodes.Range-based techniques use range measurements such as time of arrival (ToA), angle of arrival (AoA), received signal strength indicator (RSSI), and time difference of arrival (TDoA) to measure the distances between the nodes in order to estimate the location of the sensors[1].In range-based localization, the location of a node is computed relative to other nodes in its vicinity. Range-based localization depends on the assumption that the absolute distance between a sender and a receiver can be estimated by one or more features of the communication signal from the sender to the

   receiver. The accuracy of such an estimation, however, is subject to the transmission medium and surrounding environment. Range based techniques usually rely on complex hardware which is not feasible for WSNs since sensor nodes are highly resource-constrained and have to be produced at throwaway prices as they are deployed in large numbers[3]. The range methods exploit information about the distance to neighboring nodes. Although the distances cannot be measured directly they can, at least theoretically, be derived from measures of the time-of- flight for a packet between nodes, or from the signal attenuation. The simplest range method is to require knowledge about the distances to three nodes with known positions (called anchors or beacons depending on the literature), and then use triangulation.

   Anchor-Based vs. Anchor-Free

   Localization algorithms for WSNs, based on whether or not external reference nodes (i.e., anchors) are needed. These nodes usually either have a GPS receiver installed on them or know their position by manual configuration. They are used by other nodes as reference nodes in order to provide coordinates in the absolute reference system being used[1]

   Anchor-based algorithms:Anchor nodes are used to rotate, translate and sometimes scale a relative coordinate system so that it coincides with an absolute coordinate system. In anchor based algorithms, a fraction of the nodes must be anchor nodes or at least a minimum number of anchor nodes are required for adequate results. At least three non collinear anchor nodes for 2- dimensional spaces and four non coplanar anchor nodes for 3-dimensional spaces are required. The final coordinate assignments of the sensor nodes are valid with respect to a global coordinate system or any other coordinate system being used. A drawback to anchor- based algorithms is that another positioning system is required to determine the anchor node positions. Therefore, if the other positioning system is unavailable, for instance, for GPS-based anchors located in areas where there is no clear view of the sky, the algorithm may not function properly. Another drawback to anchor- based algorithms is that anchor nodes are expensive as they usually require a GPS receiver to be mounted on them Therefore, algorithms that require many anchor nodes are not very cost-effective. Location information can also be hard-coded into anchor nodes, however, careful deployment of anchor nodes is required, which may be very expensive or even impossible in inaccessible terrainsb[1].

   Anchor-free localization algorithms: [They do not require anchor nodes. These algorithms provide only relative node locations, i.e., node locations that reflect the position of the sensor nodes relative to each other. For some applications, such relative coordinates are sufficient. For example, in geographic routing protocols, the next forwarding node is usually chosen based on a distance metric that requires the next hop to be physically closer to the destination, a criteria that can be evaluated based on relative coordinates only[1]].

   Individual vs. Collaborative Localization

   When a node has enough information about distances and/or angles and positions, it can compute its own position using one of the methods trilateration, multilateration, and triangulation. Several other methods

   can be used to compute the position of a node includes probabilistic approaches, bounding box, and the central position. The choice of which method to be used also impacts the final performance of the localization system. Such a choice depends on the information available and the processors limitations. Localization protocols also differ in their basic approach to calculating node position. In one class of protocols, nodes individually determine their location, using information collected from other nodes, typically involving trilateration, triangulation, or multilateration.

   In a straightforward way, direct reach of at least three anchor nodes is needed for a node to compute its location coordinates. In computing the position using any of the above methods, algorithms often employ iterations, to start from the anchor nodes in the network and to propagate to all other free nodes calculating their positions. One of the problems of this approach is its low success ratio when the network connectivity level is not very high or when not enough well-separated anchor nodes exist in the network. To localize all the nodes, these algorithms quite often require that 20%40% of the total nodes in the network be anchor nodes, unless anchor nodes can increase their signal range.To solve the problem of demanding large numbers of anchor nodes, some approaches apply limited flooding to allow reach of anchor nodes in multiple hops, and to use approximation of shortest distances over communication paths as the Euclidean distance.

   Fig-2a)Triangulation,b)Trileteration,c)Multilateration

   Triangulation:A large number of localization algorithms fall into this class. In simple terms, the triangulation method involves gathering Angle of Arrival (AoA) measurements at the sensor node from at least three sources. Then using the AoA references, simple geometric relationships and properties are applied to compute the location of the sensor node [3]. In triangulation information about angles is used instead of distances. Position computation can be done remotely or by the node itself, the latter is more common in WSNs. The unknown node estimates its angle to each of the three reference nodes and, based on these angles and the positions of the reference nodes (which form a triangle), computes its own position using simple trigonometrically relationships [6].Triangulation method is used when the direction of the node instead of the distance is estimated, as in AoA systems. The node positions are calculated in this case by using the trigonometry laws of sines and cosines [8].

   Trilateration:Trilateration is a method of determining the relative positions of objects using the geometry of triangles similar to triangulation. Unlike triangulation, which uses AoA measurements to calculate a subjects location, trilateration involves gathering a number of reference tuples of the form (x; y; d). In this tuple, d represents an estimated distance between the source providing the location reference from (x; y) and the

   sensor node. To accurately and uniquely determine the relative location of a point on a 2D plane using trilateration, a minimum of 3 reference points are needed [3].Trilateration is the most basic and intuitive method. To estimate its position using trilateration, a node needs to know the positions of three reference nodes and its distance from each of these nodes. In real-world applications the distance estimation inaccuracies as well as the inaccurate position information of reference nodes make it difficult to compute a position. In order to do localization in a network, generally some beacons, also known as anchor notes should be set up. These beacons know exactly their coordinates. If a node with unknown coordinate can measure by some approaches the distances away from these beacons, the node can calculate its coordinate using trilateration algorithm. The geometrical representation of trilateration is illustrated in the graph above. If d1, d2, and d3 are accurate, Nk will locate at the intersection point of three circles; if d1, d2, and d3 have some noise with them, Nk will locate at the intersection region of the three circles. the trilateration algorithm can be converted into linear equations.

   Fig-3 the geometrical meaning of trilateration: if Nk knows the exact distances to A1, A2, and A3, it can calculate its coordinate

   Multilateration:Multilateration is the process of localization by solving for the mathematical intersection of multiple hyperbolas based on the Time Difference of Arrival (TDoA). In multilateration, the TDoA of a signal emitted from the object to three or more receivers is computed accurately with tightly synchronized clocks. When a large number of receivers are used, more than 4 nodes, then the localization problem can be posed as an optimization problem that can be solved using, among others, a least squares method[3]].when a larger number of reference points are available, multilateration can be considered to compute the nodes position. The number of floating point operations needed to compute a position depends on the method used to solve the system of equations.

4. Conclusion

   This paper has addressed the localization problem from the WSN perspective.The localization systems divided into three components- distance/angle estimation, position computation,and localization techniques.paper have discussed different localization algorithm/techniqueslike centralized or distributed Range-Free vs. Range-Based,Anchor-Based vs. Anchor- Free, Individual vs. Collaborative Localization depends on the application. Furthermore there is need for further research in the area localization techniques.

5. References

1. Thomas Kunz and Benjamin Tatham Localization in Wireless Sensor Networks and Anchor Placement Journal of Sensor and Actuator Networks 2012

2. Azzedineboukerche Localization systems for wireless sensor networks IEEE Wireless Communications December 2007

3. AvinashSrinivasan and Jie Wu A Survey on Secure Localization in Wireless Sensor Networks Florida Atlantic University, Boca Raton, FL, USA

4. Anneleen Van nieuwenhuyse, jeroenwyffels, jean- pierregoemaere, lieven de strycker, Bart nauwelaersTime of Arrival Based on Chirp Pulses as a means to Perform Localization in IEEE 802.15.4a Wireless Sensor Networks 10th International Conference on DEVELOPMENT AND APPLICATION SYSTEMS, Suceava, Romania,2010

5. RongPeng and Mihail L. SichitiuAngle of Arrival Localization for Wireless Sensor Networks Department of Electrical and Computer Engineering North Carolina State University Raleigh

6. PaweKuakowski a, Javier Vales-Alonso b, Esteban Egea- Lopez b, WiesawLudwina,Joan Garcia-HaroAngle-of- arrival localization based on antenna arrays for wireless sensor networks

7. Amitangshu Pal Localization Algorithms in Wireless Sensor Networks:Current Approaches nd Future ChallengesNetwork Protocols and Algorithms,2010

8. P.K Singh, Bharat Tripathi, Narendra Pal Singh Node localization in wireless sensor networksInternational Journal of Computer Science and Information Technologies,2011.