Wireless Sensor Networks: Issues, Challenges and Survey of Solutions
Download 120.6 Kb.
|
- Navigate this page:
- 8.1 Beacon Placement
- Range Estimation
Location MechanismsThe problem of localization, that is, determining where a given sensor is physically located in a network, is a challenging one, and yet extremely crucial for many of the envisioned applications of sensornets. For example, localization opens up new ways of reducing power consumption in multihop wireless networks. GEAR(Geography and Energy Aware Routing) uses location information to achieve power savings in routing. In context aware applications, localization enables intelligent selection of appropriate devices, and also supports useful coordination among devices. The desired granularity of localization is application dependent [44]. Global Positioning System (GPS) [51] solves the problem of localization in outdoor environments for PC-class nodes. However for large networks of small, cheap, low-power devices like sensor networks, practical considerations such as size, form factor, cost and power constraints preclude the use of GPS on all nodes. Some of the design goals of localization in wireless sensor networks are [44]:
Localization methods typically rely on some form of communication between reference points with known positions and the receiver node that needs to be located. Various localization techniques can be classified into two broad categories based on the granularity of information inferred during the communication. Fine-grained localization systems (e.g., GPS) provide high precision location information, typically estimated ranges or angles relative to beacons (reference points) and compute location of the unknown node using trilateration (position estimation from distance to three points) or triangulation (position estimation from angles to three points). Coarse-grained localization systems estimate unknown node location from proximity to beacons or landmarks [52]. Doherty et.al [53] proposed a coarse-grained localization system based on RF-connectivity induced constraints. Known peer-to-peer communication in the network is modeled as a set of geometric constraints on the node position. As a physical example, if a particular RF system can transmit 20m and two nodes are in communication, their separation must be less than 20m. These constraints restrict the feasible set of unknown node positions. Formally, the network is a graph with n nodes at the vertices (each node having a Cartesian position) and with bi-directional communication constraints as the edges. Positions of the first m nodes are known (x1,y1...,xm,ym) and the remaining n-m positions are unknown. The feasibility problem is then to find (xm+1,ym+1... xn, yn) such that the proximity constraints are satisfied. There will be constraints among open nodes though their positions are unknown. Connections that are not reported are not detrimental to the performance of this algorithm. To calculate the feasible solutions to the position estimation problem convex optimization is used. This methodology requires centralized computation i.e., all nodes must communicate their communicate their connectivity information to a single computer to solve the optimization problem. This solution doesn't scale well for networks of the order of 1000s of nodes since the problem becomes too computationally intensive to be handles at one place. And also the communication cost increasers with the number of sensors. A decentralized approach, where large network is divided into sub networks and position estimation can be carried out for each member of the network based on unknown centroid of the local region. Following these local estimations, the sub network centroids can be abstracted to nodes in the larger network and placed accordingly with another iteration of position estimation. Bulusu et.al. [44] propose a GPS-less localization methodology suitable for outdoor environments using RF-connectivity. Multiple nodes in the network with overlapping regions of coverage serve as reference points. They are situated at known positions (these nodes can be capable of running GPS) (X1, Y1) - (Xn,Yn), that form a regular mesh and transmit periodic beacon signals (period = T) containing their respective positions. Sensors listen for a period t >> T to evaluate connectivity. If the percentage of messages received from a beacon in a time interval t exceeds a threshold Cmthresh, that beacon is considered connected. When the beacon placement is uniform, the centroid of the positions of all connected beacons is a feasible solution in the region of connectivity overlap. For non-uniform placement, a feasible solution can be found using the convex optimization techniques used in the previous method [53]. This coarse grained, decentralized protocol doesn't require coordination among reference points or sensor nodes. It is therefore potentially scalable to very large networks. Niculescu and Nath [54] propose APS (Ad hoc Positioning System), a method to extend the capabilities of GPS to non-GPS enabled nodes in a hop-by-hop fashion in an ad hoc network. Positioning is based on a hybrid method combining distance vector like propagation and GPS triangulation to estimate location in presence of signal strength measurement errors. This mechanism applied same principle as GPS with the difference that the landmarks are contacted in a hop by hop fashion rather than directly. This method is similar to the distance vector routing, in the sense that at any time each node communicates with its immediate neighbors and in each message exchange it communicates its available estimates to landmarks acquired so far. APS is distributed, doesn't require special infrastructure or setup, provides global coordinates and requires recomputation only for moving nodes. Actual locations obtained by APS are on average less than one radio hop from true location. 8.1 Beacon Placement Beacon nodes, which know their position and serve as a reference, are a vital aspect of almost all localization systems. Beacon placement strongly affects the quality of localization. Each node may need to hear from a certain minimum number of beacons to be able to localize itself, and the beacon nodes heard must be non-linear. Fixed beacon placement strategies such as uniform and very dense placement are not always viable, energy efficient and will be inadequate in very noisy environments in which sensor networks are expected to work [43]. It is virtually impossible to preconfigure to the terrain and propagational uncertainties and compute an ideal (or even a satisfying) beacon placement that uniformly achieves a desired quality of localization across the region. So the beacon placement needs to adapt to the noisy and unpredictable environmental conditions. The approach taken by Bulsu et.al. [44] is based on measurement based adaptation i.e., improving the quality of localization by adjusting beacon placement or adding a few beacons rather than by completely redeploying all beacons. By measurement based, the authors mean the deployment of additional beacons is influenced by the measurements of the operating localization systems rather than by careful off-line analysis of a complete system model. The authors propose three approaches to adaptive beacon placement. For sparse beacon densities, the algorithms augment the existing beacon infrastructure by adding new beacons at empirically determined points, based on (i) terrain exploration and measurements made by a mobile robot [44] (ii) HEAP: A distributed, hierarchical (heap based) approach in which beacons exchange information about their neighboring beacons. Based on this information beacons evaluate a suitable point in their immediate neighborhood for adding a beacon. Eventually, the candidate points selected by beacons must be sent to a central control site, which must decide from amongst various candidate points where to deploy new beacon nodes [55]. For dense beacon deployment, [52] propose STROBE (Selectivey TuRning Off Beacons), a localized algorithm that rotates functionality amongst beacons to reduce interference among the densely placed beacons, allows adaptation to noisy environments as well as extend the system lifetime. In unattended sensor networks, where new sensors cannot be physically deployed as needed, one could begin with a very dense initial beacon deployment for redundancy. Each beacon determines its role during a given time interval based on coordination with its neighbors rather than from an assignment by a central server.
[56] deals with range estimation, a critical requirement for fine-grained localization. While many mechanisms (e.g., RF, IR, Acoustic) for range estimation exist, any individual mode of sensing can be blocked or confused by the environment. Girod and Estrin [56] suggest the use of orthogonal sensory channel to detect and eliminate these measurements. This approach is based on the following three principles:
e.g., Consider a system composed of many standalone ranging units. Acoustic ranging performance suffers when the "line of sight" path is obstructed. Longer deflected paths lead to unbound error. It is very difficult to identify these errors based exclusively on analysis of acoustic data. Now if we use a camera, where each camera's filed of view contains several ranging units, which might be identified by a characteristic pattern strobed on an IR LED. Any ranging unit that the camera can see has a high probability of LOS to the camera and thus in those cases an accurate range can be determined with acoustics.
|