Sarmistha Nanda, Localization In Wireless Sensor Network 3

Localization In Wireless Sensor Network

Sarmistha Nanda1, Arun K Pujari2

1 Sambalpur University Institute of Information Technology, Sambalpur, India

2 Vice-Chancellor, Sambalpur University, India

Sarmistha Nanda, Localization In Wireless Sensor Network 3

Abstract

A Wireless Sensor Network (WSN) is a self-configuring network of small sensor nodes communicating among themselves using radio signals, sensors are deployed in quantity to sense, monitor and understand the physical world. Among all the challenges of WSN, localization is one of the most fundamental and difficult problems. There are many techniques to solve the localization problem and among them SDP is a powerful technique.

Here we use a new partition technique which makes the partition of sensor network. Then we apply SDP to each partition then combine the result to solve localization problem.

1. Introduction

Currently, wireless sensor networks are beginning to be deployed at many environments and applications including disaster management, agriculture, natural resource management, wild life and public health. A wireless sensor network(WSN) is a self-configuring network of small sensor nodes communicating among themselves using radio signals, and are deployed to sense, monitor and understand the physical world. The sensor nodes are also called as motes. Each sensor node is a small, inexpensive, low-power device which is capable of local processing and wireless communication. But when coordinated with the information from a large number of other nodes, they have the ability to measure a given physical environment in great detail. Recent technological advances have lead to the emergence of WSNs which are capable of observing the physical world, processing the data, making decisions based on the observations and performing appropriate actions. Sensors integrated into structures, machinery, and the environment, coupled with the efficient delivery of sensed information, could provide tremendous benefits to mankind. Unlike traditional networks, sensor networks depend on dense deployment and co-ordination to carry out their tasks.

WSN design is influenced by many factors, such as fault tolerance, scalability, network topology, hardware constraints, transmission media and power consumption [1]. The architecture of sensor hardware consists of the usual components like processor, memory, wireless interface, power supply as well as sensing devices [3]. However, the computational and energy resources are limited due to size and weight restriction. A sensor node can be in four states of communication: transmit, receive, idle or sleep and two sates in monitoring: idle and active [21].

Generally, the sensor nodes which are designed for specific application are randomly deployed to cover the area of interest. The random deployment allows the relief operation even in inaccessible terrain. After the deployment, these sensor nodes are generally stationary and self organized into networks. They gather information about the monitoring region and then send the information to the base station where decisions are to be made. In this way, the sensor networks provide information and better understanding of the monitored region. The network can be extended easily by adding additional sensor nodes without any extra complexity.

Sensors are deployed spontaneously to form efficient ad hoc networks with them by having limited computational, storage and short-range wireless communication capabilities. Sensor devices may be deployed in very harsh environments, and subject to destruction and dynamically changing conditions. The configuration of the network will frequently change due to constant change in accessibility of sensors, power availability and task requirements. When compared with traditional ad hoc networks, WSNs have some limitations such as limited power, computational capacity and memory.

This new technology is exciting with unlimited potential for numerous application areas including environmental, medical, military, transportation, entertainment, crisis management, homeland defense, industry, science, transportation, civil infrastructure, security, traffic control, health care, chemical attack detection, home security, disaster recovery etc.

2. ISSUES AND CHALLENGES

In recent years, there have been a lot of activities in WSN research. There are many issues that require research investigation.

Most sensor nodes are deployed in regions which have no infrastructure at all. Once deployed, sensor networks have no human intervention. In such a situation, it is up to the nodes to identify the connectivity and the nodes themselves are responsible for reconfiguration. It is required that a sensor network system be adaptable to changing connectivity as well as changing environmental stimuli. Routing becomes one of the major issues in this situation. Node localization is the problem of determining the geographical location of each node in the system. Localization is one of the most fundamental and difficult problems that must be solved for WSN. Clock synchronization is important for many reasons. When an event occurs in a WSN it is often necessary to know where and when it occurred. Clocks are also used for many system and application tasks. In WSN, there is only a finite source of energy, which must be optimally used for processing and communication. Since most systems require much longer lifetime, significant research has been undertaken to increase lifetime while still meeting functional requirements.

4. THE LOCALIZATION PROBLEM

In WSNs, sensor node localization is an important topic because sensor nodes are randomly scattered in the region of interest, their locations are unknown in the beginning, and they get connected into network on their own. Localization [23] is the process to determine the positions of the sensor nodes. Knowing the positions of the network nodes is essential because many other network functionalities such as location dependent computing, geographic routing, coverage and tracking, and event detection depend on location. One can see the problem to be very trivial and think of achieving through manual configuration or by exploiting the Global Positioning System (GPS)[19]. But these techniques do not scales well and both have physical limitations. For example, GPS receivers are costly both in terms of hardware and power requirements. Localization problem in WSN is one prime area of research and many researchers are trying to see this as an algorithmic problem. The problem can be viewed as a graph embedding problem on unit disk graph[20]. However the it is possible to solve only when the graph is dense. Researchers are still looking for efficient algorithms that work for sparse networks. Such algorithms are of great importance, because in the limit as a network with bounded communication range and fixed sensor density grows, the number of known distance pairs grows only linearly in the number of nodes.

Many solution approaches have been proposed for this problem. However it should be noted that the problem as stated could be ill-posed as there may be more than one solution satisfying the given distance measurements.

6. CATEGORY OF LOCALIZATION TECHNIQUE

Localization algorithms can be categorized according to a number of different aspects:

Input data: range-free, range-based - Range-free localization algorithms simply rely on connectivity information. Range-based methods extract distance information from radio signals. Range-free localization methods use the information of topology and connectivity for location estimation. Range-free methods have some advanced characteristics, such as low cost, small communication traffic, no extra hardware and flexible localization precision. Range-based localization methods depend on distance or angle between nodes to obtain unknown node’s location.

Accuracy: fine-grained, coarse-grained - A location discovery algorithm should estimate sensor position accurately. Accuracy, or grain size, can be expressed as percentage of sensor transmission range, or in meters. The level of accuracy usually depends on range measurement errors. Range measurements with less error will lead to more accurate position estimates.

Dynamics: mobile, fixed - In fixed networks, nodes can establish their location in the initialization phase. Their only task is to report events or relay information sent by other nodes. In mobile networks, nodes need to be aware of changes in their position and perhaps of position changes of other nodes. Systems provide more accurate location information when a node is at rest than when it is in motion.

Beacons: beacon-free, beacon-based - Nodes with known positions are called beacon or anchor nodes. Beacon-based algorithms usually produce an absolute location system where absolute positions of nodes are known - latitude, longitude and altitude. The accuracy of the estimated position is highly affected by the number of anchor nodes and their distribution in the sensor field. The ratio of beacon nodes to blind nodes is small. The location of a beacon node can be determined using an attached GPS device or by manual deployment.

Computational model: centralized, distributed - If an algorithm collects localization related data from the network and processes the data collectively at a single station, then it is said to be centralized. In this approach, the collection of information is performed by message exchange between nodes, hence, with large number of nodes, centralized localization algorithms become lower energy-efficient, longer delay and higher traffic. If, on the other hand, each node collects partial data relevant to it and executes an algorithm to locate itself, then the localization algorithm is categorized as distributed. Locally centralized algorithms are distributed algorithms that achieve a global goal by communicating with nodes in some neighborhood only. The sensor network can be divided into local clusters, where each cluster has a head. All the range measurements in a certain cluster are forwarded to the cluster head, where computation takes place.

Hops : single-hop, multi-hop - A direct link between two neighbor nodes is called a hop. When the distance between two nodes is larger than the radio range but there are other nodes that create a continuous path between them, the path is called a multi-hop path.

7. LOCALIZATION TECHNIQUES

There are a lot of sensor localization techniques [4][7][8][22]. Depending on the application the localization technique provides absolute coordinates or it may provide relative coordinates. Even in case of absolute localization the accuracy may be different. The technique must provide the desired type of accuracy, taking the available resources into

consideration. Here are some techniques.

Trilateration

Trilateration locates a node by calculating the intersection of three circles. If the ranges contains error, The intersection of three circles may not be a single point. In geometry, trilateration [30] is the process of determination of absolute or relative locations of points by measurement of distances, using the geometry of spheres.

Multilateration

In multilateration, the position is estimated from distances to three or more known nodes by minimizing the error between estimated position and actual position. Using the trilateration technique we can get the node position if the distance of three anchors to a particular sensor is given. But when the measurement of distances are not taken to be accurate, we use multilateration technique.

Convex Position Estimation

In recent years, there has also been great interest in applying convex optimization techniques [27], particularly that of SDP relaxation, to tackle the network localization problem. Although convex optimization based localization algorithms can usually produce highly accurate results they are also computationally demanding. Convex position estimation algorithm belongs to the class of centralized anchor based localization algorithm. The algorithm uses the connectivity between nodes to formulate a set of geometric constraints and solve it using convex optimization.

Binary Proximity

The most basic location technique is binary proximity. It has to take a simple decision ie. whether two nodes are within the reception range of each other. Here a set of reference nodes are placed in the environment in some non-overlapping manner. Then either the reference nodes periodically emit beacons, or a unknown node transmits beacon when it needs to be localized. If reference nodes emit beacons, these include their location IDs. Then the unknown node will determine to which reference node is closest to it. Alternatively, if the unknown node emits a beacon, the reference node that hears the beacon uses its own location to determine the location of unknown node. An example of proximity detection in localization is the Active Badge location system [6] meant for an indoor office environment.

MDS

Multidimensional scaling (MDS) has been recently applied to sensor localization [11][24][25][28] in the sensor network and gained some very impressive performance. MDS treats dissimilarities of pair-wise sensors in Euclidean distances.

Bounding Box method

Each node listens to the beacons in his neighborhood, and collects their positions. The position of the node is guaranteed to lie in the intersection of the bounding boxes corresponding to all the beacons within the radio range. This set itself is a box, whose minimum and maximum values are computed by iterating the process upon all the beacons heard: at each stage, the new boundary values are compared to the previous ones, and the smallest set is kept. Finally, the center of gravity of this last intersection set is computed, and said to be the estimated position,

APIT (Approximate Point In Triangle)

The APIT idea is to divide the environment into triangles, given by beaconing nodes. An individual node’s presence or absence in each of those triangles will allow to reduce the possible location area. This goes until all the possible sets are exhausted, or the desired accuracy reached. APIT technique requires a high density of nodes and if there is a high density of nodes then APIT will provide a good location accuracy.

.

Localization Using ISOMAP

To determine the sensors location in wireless sensor networks we may face the problem of having noise in the network which results measurement inaccuracy. In the complicated environment, rather than estimating the pair-wise Euclidean distance between sensors, we use the geodesic distance to measure the dissimilarity between sensors. Isomap algorithm achieves smaller average location error with little quantity of errors. Isomap is a manifold learning algorithm, which is first proposed for nonlinear dimension reduction, and has been widely used for the analysis of dissimilarity of data set, and can discover the low dimension spatial structure in data [17]. The key benefit of using isomap for location estimation is that it employs the geodesic distance to measure the dissimilarity between sensors and it can always generate relatively high accurate location estimation even based on the error-prone distance information.

Sequence Based Localization In WSN

In sequence based localization technique for wireless sensor network the localization space is divided into distinct regions that can each be uniquely identified by sequences [10] that represent the ranking of distances from the reference node to that region. For n nodes in localization space O(nn) sequences are possible but due to some geometric constraints, the actual number of feasible location sequences only O(n4). The procedure for localization of unknown nodes using location sequences is given as follows.