Using Cramer-Rao-Lower-Bound to Reduce Complexity of Localization in Wireless Sensor Networks Dominik Lieckfeldt, Dirk Timmermann Department of Computer.

Slide 1Using Cramer-Rao-Lower-Bound to Reduce Complexity of Localization in Wireless Sensor Networks Dominik Lieckfeldt, Dirk Timmermann Department of Computer Science and Electrical Engineering Institute of Applied Microelectronics and Computer Engineering University of Rostock [email protected] Slide 2Outline 1. Introduction 2. Goal 3. Localization in wireless sensor networks  Overview  Cramer-Rao-Lower-Bound  Complexity and energy consumption 4. Characterizing Potential Benefits 5. Conclusions / Outlook 6. Literature Using CRLB to Reduce Complexity of Localization in WSNs 2 Slide 3Introduction Wireless Sensor Network (WSN):  Random deployment of large number of tiny devices  Communication via radio frequencies  Sense parameters of environment Applications  Forest fire  Volcanic activity  Precision farming  Flood protection Using CRLB to Reduce Complexity of Localization in WSNs 3 Location of sensed information  important parameter in WSNs Slide 4Introduction – Localization Example 4 Using CRLB to Reduce Complexity of Localization in WSNs Parameters:  m … Number of beacons  n … Number of unknowns  N=m+n … Total number of nodes Beacon Unknown Error ellipse Slide 5Goal of this Work Investigate potential impact and applicability of adapting and scaling localization accuracy to:  Activity  Importance  Energy level  Other parameters (context) Obey fundamental trade-off between: accuracy complexity Benefits:  Decreased communication  Prolonged lifetime of WSN Using CRLB to Reduce Complexity of Localization in WSNs 5 Slide 6Localization in WSN Possible approaches  Lateration (typically used)  Angulation  Proximity Lateration  Use received signal strength (RSS) to estimate distances : RSS ~ 1/d²  Idea: – Estimate distances to beacons – Solve non-linear system of equations Using CRLB to Reduce Complexity of Localization in WSNs 6 2 3 4 1 Beacon Unknown Slide 7Localization in WSN Measurements of RSS are disturbed:  Interference  Noise How accurate can estimates of position be?  Cramer-Rao-Lower-Bound (CRLB) poses lower bound on variance of any unbiased estimator Using CRLB to Reduce Complexity of Localization in WSNs 7 …Path loss coefficient … standard deviation of RSS measurements …true parameter …estimated parameter Distance Geometry Slide 8Cramer-Rao-Lower-Bound Using CRLB to Reduce Complexity of Localization in WSNs 8 CRLB Error model of RSS measurements Number of beacons Geometry Lower bound on variance of position error Slide 9Cramer-Rao-Lower-Bound Example  1 dimension  True position at x=0  Disturbed position estimates  Probability density of position estimates  Standard deviation or root mean square error more intuitive than variance Using CRLB to Reduce Complexity of Localization in WSNs 9 Slide 10Cramer-Rao-Lower-Bound – An Example 2 beacons, 1 unknown Using CRLB to Reduce Complexity of Localization in WSNs 10 Beacon Unknown Slide 11Complexity of Localization Complexity depends on:  Dimensionality (2D/3D)  Number of Beacons  Number of nodes with unknown position Using CRLB to Reduce Complexity of Localization in WSNs 11 Slide 12Energy Consumption and Localization Communication  Two-way communication beacon unknown  Main contribution to total energy consumption Calculation  Simplest case: Energy spend ~ number of beacons Using CRLB to Reduce Complexity of Localization in WSNs 12 Energy  Number of beacons  Slide 13Reducing Complexity of Localization in WSNs How to reduce Complexity?  Constrain number of beacons used  Idea: Select those beacons first that contribute most to localization accuracy! Using CRLB to Reduce Complexity of Localization in WSNs 13 Slide 14Related Work Impact of geometry not considered No local rule which prevents insignificant beacons from broadcasting their position Using CRLB to Reduce Complexity of Localization in WSNs 14 Beacon Placement Weighting range measurements Simulate localization error Variance/Distance [LZZ06, CPI06, BRT06] Variance/Distance [LZZ06, CPI06, BRT06] Detect outliers [OLT04, PCB00] Detect outliers [OLT04, PCB00] Choose nearest k beacons [CTL05] Choose nearest k beacons [CTL05] Slide 15Characterizing Potential Benefits Simulations using Matlab Aim:  Proof of Concept  Determine how likely it is that constraining the number of beacons is possible without increasing CRLB significantly Using CRLB to Reduce Complexity of Localization in WSNs 15 Slide 16Characterizing Potential Benefits Simulation setup:  Random deployment of m beacons and 1 unknown Using CRLB to Reduce Complexity of Localization in WSNs 16  For every deployment calculate: – – k=m: consider all beacons – k