my Master 4

Information about my Master 4

Published on June 18, 2007

Author: Techy_Guy

Source: authorstream.com

Content

Location-sensing using the IEEE 802.11 Infrastructure and the Peer-to-peer Paradigm for Mobile Computing Applications:  Location-sensing using the IEEE 802.11 Infrastructure and the Peer-to-peer Paradigm for Mobile Computing Applications Anastasia Katranidou Supervisor: Maria Papadopouli Master Thesis, University of Crete andamp; FORTH-ICS, Hellas 20 February 2006 Overview:  Overview Location-sensing Motivation Proposed system - CLS Evaluation of CLS Conclusions Future work Pervasive computing century:  Pervasive computing century Pervasive computing enhances computer use by making many computers available throughout the physical environment but effectively invisible to the user Why is location-sensing important ?:  Why is location-sensing important ? Navigation systems Locating people andamp; objects Wireless routing Smart spaces Supporting location-based applications transportation industry medical community security entertainment industry emergency situations Location-sensing properties:  Location-sensing properties Metric (signal strength, AoA, ToA, TDoA) Techniques (triangulation, proximity, scene analysis) Multiple modalities (RF, ultrasound, infrared) Limitations andamp; dependencies (e.g., infrastructure vs. ad-hoc) Localized or remote computation Physical vs. symbolic location Absolute vs. relative location Scalability Cost Specialized hardware Privacy Related work:  Related work Motivation:  Motivation Build a location-sensing system for mobile computing applications that can provide position estimates: using the available communication infrastructure within a few meters accuracy without the need of specialized hardware and extensive training operating on indoors and outdoors environments Use peer-to-peer paradigm knowledge of the environment and mobility Design goals:  Design goals Robust to tolerate network failures, disconnections, delays due to host mobility Extensible to incorporate application-dependent semantics or external information (e.g., floorplan, signal strength map) Computationally inexpensive Scalable Use of cooperation of the devices and information sharing No need for extensive training and specialized hardware Suitable for indoor and outdoor environments Thesis:  Thesis Implementation of the Cooperative Location System (CLS) Extension of the CLS design signal strength map information about the environment (e.g., floorplan) heuristics based on confidence intervals Extensive performance analysis range error density of hosts mobility Empirical study of the range error in FORTH-ICS Cooperative Location System (CLS):  Cooperative Location System (CLS) Communication Protocol Each host estimates its distance from neighboring peers refines its estimations iteratively as it receives new positioning information from peers Voting algorithm accumulates and evaluates the received positioning information Grid-representation of the terrain Communication protocol:  CLS beacon neighbor discovery protocol with single-hop broadcast beacons respond to beacons with positioning information (positioning entry andamp; SS) CLS entry set of information (positioning entry andamp; distance estimation) that a host maintains for a neighboring host CLS update messages dissemination of CLS entries CLS table all the received CLS entries CLS table of host u Positioning entry Distance estimation CLS entries Communication protocol Voting algorithm:  Voting algorithm Grid for host u (unknown position) Corresponds to the terrain Peer A has positioned itself Positive votes from peer A The value of a cell = sum of the accumulated votes The higher the value of a cell, the more hosts agree that this cell is likely position of the host Peer B has positioned itself Positive votes from peer B Negative vote from peer C Voting algorithm termination:  Voting algorithm termination Set of cells with maximal values defines possible position A cell is a possible position If the num of votes in a cell is above ST and the num of cells with max value below LECT terminate the iteration process report the centroid of the set as the host position u Evaluation of CLS:  Evaluation of CLS Impact of several parameters on the accuracy ST and LECT thresholds range error density of hosts and landmarks Simulation testbed 100x100 square units in size Randomly placed nodes (10 landmarks + 90 nodes) in the terrain Location andamp; range errors as % of the transmission range (R=20 m) Impact of range error :  Impact of range error avg connectivity degree = 10 avg connectivity degree = 12 Impact of connectivity degree & percentage of landmarks:  Impact of connectivity degree andamp; percentage of landmarks For low connectivity degree or few landmarks the location error is bad For 10% or more landmarks and connectivity degree of at least 7 the location error is reduced considerably 5% range error Extension of CLS:  Extension of CLS Incorporation of: signal strength map information about the environment (e.g., floorplan) confidence intervals topological information pedestrian speed Signal strength map:  Signal strength map Training phase: each cell andamp; every AP 60 measured SS values 1 signal strength (SS) value / sec 95% - confidence intervals Estimation phase: SS measurements in 45 cells if LBi[c] ≤ ŝi ≤ UBi[c] cell c accumulates vote from APi final position: centroid of cells with maximal values CLS with signal strength map:  CLS with signal strength map 95% - confidence intervals no CLS: 80% hosts ≤ 2 m extended CLS: 80% hosts ≤ 1 m Impact of mobility:  Impact of mobility Movement paths Speed Frequency of CLS runs Simulation setting 10 landmarks, 10 mobile and 80 stationary nodes transmission range (R) = 20 m range error = 10% R Impact of movement paths:  Impact of movement paths Simulation setting 10 different scenarios max speed = 2 m/s time= 100 sec Mean location error [%R] Simulation time (sec) Impact of the speed:  Impact of the speed Simulation setting 6 times the same scenario fixed initial and destination position of each node at each run time = 100 sec Simulation time (sec) location error [%R] Impact of the frequency of CLS runs:  Impact of the frequency of CLS runs Simulation setting 6 times the same scenario every 120, 60, 40, 30, 20 sec CLS run = 1, 2, 3, 4, 6 times speed = 2 m/s time = 120 sec Tradeoff accuracy vs. overhead message exchanges computations Simulation time (sec) location error [%R] Evaluation of the extended CLS under mobility:  Evaluation of the extended CLS under mobility Incorporation of: topological information signal strength map pedestrian speed Simulation setting 5 landmarks, 30 mobile and 15 stationary nodes speed = 1m/s R = 20 m range error = 10% R sim time = 120 sec CLS every 10 sec Use of topological information:  Use of topological information mobile node cannot: walk through walls enter in some forbidden areas negative weights CLS under mobility: 80% of hosts ≤ 90% location error (%R) CLS andamp; topological information: 80% of hosts ≤ 60% location error (%R) Use of signal strength map:  Use of signal strength map CLS andamp; topological information andamp; SS map: 80% of hosts ≤ 30% location error (%R) Use of the pedestrian speed:  Use of the pedestrian speed pedestrian speed: 1 m/s time instance t1: at point X after t sec: at any point of a disc centered at X with radius equal to t meters CLS andamp; topological information andamp; SS map andamp; pedestrian speed: 80% of hosts ≤ 13% location error (%R) Estimation of Range Error in FORTH-ICS:  Estimation of Range Error in FORTH-ICS 50x50 cells, 5 APs For each cell we took 60 SS values 95% confidence intervals (CI) for each cell c and the respective APs i Range errori[c] = max{|d(i,c) - d(i,c’)|},  c' such that: CIi[c]∩CIi[c’] ≠ Ø 90% cells ≤ 4 meters range error (10% R) Maximum range error due to the topology ≤ 9.4 meters Conclusions:  Conclusions Evaluation and extension of the CLS algorithm 80% of hosts ≤ 0.8 m estimations from peers give better accuracy than SS measurements Evaluation of CLS under mobility 80% of hosts ≤ 2.6 m great impact of frequency of CLS runs Comparison with related work static RADAR: 80% ≤ 4.5 m mobile RADAR: 80% ≤ 5 m Future work:  Future work Incorporate heterogeneous devices (e.g, RF tags, sensors) to enhance the accuracy Employ theoretical framework (e.g., particle filters) to support the grid-based voting algorithm and mobility models Provide guidelines for tuning the weight votes of hosts Use more sophisticated radio propagation model Publications:  Publications Under preparation for submission to the Mobile Computing and Communications Review (MC2R) journal Location-sensing using the IEEE 802.11 Infrastructure and the Peer-to-peer Paradigm for Mobile Computing Applications:  Location-sensing using the IEEE 802.11 Infrastructure and the Peer-to-peer Paradigm for Mobile Computing Applications Anastasia Katranidou Supervisor: Maria Papadopouli Master Thesis, University of Crete andamp; FORTH-ICS, Hellas 20 February 2006 THANK YOU! APPENDIX:  APPENDIX Appendix RADAR vs. CLS:  RADAR vs. CLS RADAR: 3 APs 90% hosts ≤ 6 m sampling density: 1 sample every 13.9 m2 Extended static CLS: 5 APs 90% hosts ≤ 2 m sampling density: 1 sample every 14.8 m2 Ladd et al. vs. CLS:  Ladd et al. vs. CLS Static localization Ladd et al. 9 APs 77% of hosts ≤ 1.5 m Extended static CLS 5 APs 77% of hosts ≤ 0.8 m Static fusion Ladd et al. 9 APs 64% of hosts ≤ 1 m Extended mobile CLS 5 APs 45% of hosts ≤ 1 m Savarese et al. vs. CLS:  Savarese et al. vs. CLS Savarese et al. better with very small connectivity degree (4) or less than 5 landmarks Extended static CLS better with connectivity degree of at least 8 and 10% or more landmarks Impact of ST and LECT thresholds:  Impact of ST and LECT thresholds Terminate the iteration process ST: the num of votes in a cell must be above it LECT: the num of cells with max value must be below it LECT Host h defined solely from host g not acceptable: the possible cells of host h correspond to a ring Host h defined from host g and k 1 case: not acceptable 2 case: location errormax = √ [Dmax2 – (Dmin + e)2 ] Host h defined from host g, k and m Possible area: (2· ε +1)2 location errormax: √[(2· ε +1)2 / 2] ST eventually each host will receive votes from every landmark and every other host (CLS updates) wall_landmarks +wall_hosts ST and LECT:  ST and LECT Simulation setting 10 landmarks and 90 nodes avg connectivity degree = 10 range error = 10% R Best values ST = 800 LECT = 5 Interpolation methods:  Interpolation methods Cubic interpolation Least squares Linear interpolation Impact of connectivity degree under mobility:  Impact of connectivity degree under mobility Simulation setting 5 landmarks 30 mobile nodes 15 stationary nodes Simulation setting 5 landmarks 5 mobile nodes 5 stationary nodes Grid size:  Grid size 100x100: reasonable choice Message exchanges:  Message exchanges Movement example:  Movement example Random waypoint model Max speed Pause time

Related presentations


Other presentations created by Techy_Guy

Character Analysis
04. 01. 2008
0 views

Character Analysis

Roosevelt and Latin America
22. 10. 2007
0 views

Roosevelt and Latin America

S10 Processor Performance
17. 09. 2007
0 views

S10 Processor Performance

Hawaiian Humpback Whale
17. 09. 2007
0 views

Hawaiian Humpback Whale

rainforest
02. 10. 2007
0 views

rainforest

Comvalid BGPsentinel
07. 10. 2007
0 views

Comvalid BGPsentinel

PETERPAN
10. 10. 2007
0 views

PETERPAN

across crocodile lake
11. 10. 2007
0 views

across crocodile lake

MLM basic info
12. 10. 2007
0 views

MLM basic info

VortragRichter
15. 10. 2007
0 views

VortragRichter

azerbaijan
15. 10. 2007
0 views

azerbaijan

ch02jjm
19. 10. 2007
0 views

ch02jjm

PRNAV Eurocontrol presentation
19. 10. 2007
0 views

PRNAV Eurocontrol presentation

Hakkarainen 091104
17. 09. 2007
0 views

Hakkarainen 091104

Extreme Ostrich2
17. 09. 2007
0 views

Extreme Ostrich2

Soy Protein in Baking
04. 10. 2007
0 views

Soy Protein in Baking

McMurrenTidbits
23. 10. 2007
0 views

McMurrenTidbits

Larijani stemcell ABA2007 Final
24. 10. 2007
0 views

Larijani stemcell ABA2007 Final

F Gauze
24. 10. 2007
0 views

F Gauze

TornadoSafetyAMS
07. 10. 2007
0 views

TornadoSafetyAMS

nii report
09. 10. 2007
0 views

nii report

NS102 3a S07 Fighting Sail
21. 10. 2007
0 views

NS102 3a S07 Fighting Sail

am0845 Khanna
16. 11. 2007
0 views

am0845 Khanna

culturechange
10. 12. 2007
0 views

culturechange

Jeopardy
29. 10. 2007
0 views

Jeopardy

masstheory
02. 11. 2007
0 views

masstheory

Finnish Chemicals information
21. 08. 2007
0 views

Finnish Chemicals information

zodiac
21. 08. 2007
0 views

zodiac

ICT Expo Presentation
21. 08. 2007
0 views

ICT Expo Presentation

words alive notes
21. 08. 2007
0 views

words alive notes

notes 13
21. 08. 2007
0 views

notes 13

200612011440150 ser mama
01. 10. 2007
0 views

200612011440150 ser mama

t5f2
07. 11. 2007
0 views

t5f2

PHYS 124 lt 2
13. 11. 2007
0 views

PHYS 124 lt 2

Localization days1 2
14. 11. 2007
0 views

Localization days1 2

Barlow
15. 11. 2007
0 views

Barlow

CEO breakfast Mar
16. 11. 2007
0 views

CEO breakfast Mar

SEVESO II 28 04 2003 d jansen
23. 11. 2007
0 views

SEVESO II 28 04 2003 d jansen

farawayplaces quiz
31. 10. 2007
0 views

farawayplaces quiz

lino hospitalstay 2005
28. 12. 2007
0 views

lino hospitalstay 2005

eno
05. 10. 2007
0 views

eno

Destinos Tradicionale
22. 10. 2007
0 views

Destinos Tradicionale

El Karib Hagmann 2001 HEKS ACORD
23. 10. 2007
0 views

El Karib Hagmann 2001 HEKS ACORD

Bioceramics
05. 01. 2008
0 views

Bioceramics

dennis
07. 01. 2008
0 views

dennis

DNR wetland benefits
07. 01. 2008
0 views

DNR wetland benefits

Norm Wright Presentation06
17. 09. 2007
0 views

Norm Wright Presentation06

Tudor Sports
21. 08. 2007
0 views

Tudor Sports

watson 2006
21. 08. 2007
0 views

watson 2006

IBM Presentation Roel Spee
24. 10. 2007
0 views

IBM Presentation Roel Spee

david simek
17. 09. 2007
0 views

david simek

75thWinter Silver
02. 08. 2007
0 views

75thWinter Silver

Revay Presentation
17. 09. 2007
0 views

Revay Presentation

week12 f03
17. 09. 2007
0 views

week12 f03

Ch12 ResolutionTheoremPro ving
17. 09. 2007
0 views

Ch12 ResolutionTheoremPro ving

INFOCOM99
05. 10. 2007
0 views

INFOCOM99

RoHS Presentation3 May
12. 10. 2007
0 views

RoHS Presentation3 May

Botany
07. 12. 2007
0 views

Botany

Week6February20 07
20. 02. 2008
0 views

Week6February20 07

Microcosmo Parte II
12. 10. 2007
0 views

Microcosmo Parte II

TSW
29. 02. 2008
0 views

TSW

HazMat Flow Study
26. 02. 2008
0 views

HazMat Flow Study

Vegetarian Nutrition 101
04. 03. 2008
0 views

Vegetarian Nutrition 101

White 10th Inter mountain
21. 08. 2007
0 views

White 10th Inter mountain

hondaimobil
02. 01. 2008
0 views

hondaimobil

Cfi
10. 03. 2008
0 views

Cfi

Timber Bridge Presentation
01. 01. 2008
0 views

Timber Bridge Presentation

carstenschymik
29. 12. 2007
0 views

carstenschymik

Ch 22 WB
07. 04. 2008
0 views

Ch 22 WB

Macroclean
10. 04. 2008
0 views

Macroclean

agingandwork
13. 04. 2008
0 views

agingandwork

nyBrazeau
14. 04. 2008
0 views

nyBrazeau

presentation total
16. 04. 2008
0 views

presentation total

3 Tufano2002
17. 04. 2008
0 views

3 Tufano2002

Chapter 18
18. 04. 2008
0 views

Chapter 18

Baltic states and Russia
12. 10. 2007
0 views

Baltic states and Russia

quotes
03. 10. 2007
0 views

quotes

WDR 2008
29. 11. 2007
0 views

WDR 2008

CHLA PSRS Overview
30. 04. 2008
0 views

CHLA PSRS Overview

15 UKernel
02. 05. 2008
0 views

15 UKernel

Mr Logan OCCAR
06. 03. 2008
0 views

Mr Logan OCCAR

shen
15. 10. 2007
0 views

shen

Industry Brief
22. 10. 2007
0 views

Industry Brief

sess 4 solano
18. 06. 2007
0 views

sess 4 solano

sess 2 vollmer
18. 06. 2007
0 views

sess 2 vollmer

NSDI05 poster
18. 06. 2007
0 views

NSDI05 poster

NLC talk
18. 06. 2007
0 views

NLC talk

My Proxy GW06
18. 06. 2007
0 views

My Proxy GW06

More Mosaics
18. 06. 2007
0 views

More Mosaics

MEM SPI Jan00
18. 06. 2007
0 views

MEM SPI Jan00

VCA Org Charts
11. 12. 2007
0 views

VCA Org Charts

cjdim com Boudchiche
23. 10. 2007
0 views

cjdim com Boudchiche

GA Conf06China1
25. 03. 2008
0 views

GA Conf06China1

lecture 7 deadlock
17. 09. 2007
0 views

lecture 7 deadlock

Neptune Presentation
15. 06. 2007
0 views

Neptune Presentation

neptune
15. 06. 2007
0 views

neptune

Mehregan
18. 06. 2007
0 views

Mehregan

Plants are very useful
15. 06. 2007
0 views

Plants are very useful

Learning Phonics
15. 06. 2007
0 views

Learning Phonics

Learning Percent III
15. 06. 2007
0 views

Learning Percent III

Learning Percent I
15. 06. 2007
0 views

Learning Percent I

Physical Education Procedures
15. 06. 2007
0 views

Physical Education Procedures

Penguins
15. 06. 2007
0 views

Penguins

Olympic Wax Museum
15. 06. 2007
0 views

Olympic Wax Museum

howe9
17. 09. 2007
0 views

howe9

GSantin Siena 2 SpaceTools
03. 01. 2008
0 views

GSantin Siena 2 SpaceTools

gunderia powerpointlab
26. 11. 2007
0 views

gunderia powerpointlab

MySQL UC solid DB xact
18. 06. 2007
0 views

MySQL UC solid DB xact

Civics Lecture
31. 12. 2007
0 views

Civics Lecture

Physics and psycho2
14. 02. 2008
0 views

Physics and psycho2

TOUREDIT
12. 03. 2008
0 views

TOUREDIT

harvard deas
03. 01. 2008
0 views

harvard deas

Angelology
01. 10. 2007
0 views

Angelology

HenryVIII wwtbam
21. 08. 2007
0 views

HenryVIII wwtbam

AGU 2002
03. 10. 2007
0 views

AGU 2002

RubÃn Blades
22. 10. 2007
0 views

RubÃn Blades

tran present
21. 08. 2007
0 views

tran present

BU01
17. 09. 2007
0 views

BU01

Thode
17. 09. 2007
0 views

Thode

PP R CAJAR
22. 10. 2007
0 views

PP R CAJAR

moore lightning uw05
17. 09. 2007
0 views

moore lightning uw05

Space- The Outside World
15. 06. 2007
0 views

Space- The Outside World

arts and humanities applications
22. 11. 2007
0 views

arts and humanities applications

Session9 CATHALAC UNDP
25. 10. 2007
0 views

Session9 CATHALAC UNDP

use sunscreen
17. 09. 2007
0 views

use sunscreen

aatom
20. 11. 2007
0 views

aatom

9681
02. 08. 2007
0 views

9681

HHDL
15. 10. 2007
0 views

HHDL