A Location Service for Beacon Vector RoutingMotivation and Problem FormulationKey Solution IdeasCurrent Status and Future PlansQuestions?A Location Service for A Location Service for Beacon Vector RoutingBeacon Vector RoutingChris Baker, Daekyeong Moon,Chris Baker, Daekyeong Moon,Jorge OrtizJorge OrtizMotivation and Problem Motivation and Problem FormulationFormulationBeacon Vector Routing (BVR)Beacon Vector Routing (BVR)Point-to-point routing schemePoint-to-point routing schemeDynamic beacon-derived coordinate systemDynamic beacon-derived coordinate systemEach node in network has an associated node id and a runtime-derived Each node in network has an associated node id and a runtime-derived coordinatecoordinateAssumptionsAssumptionsNode id’s are unique and unchangingNode id’s are unique and unchangingBeacon Vector Coordinates are subject to change with topology of the Beacon Vector Coordinates are subject to change with topology of the networknetworkCurrent BVR Current BVR sends [node_id, BVCoords] mapping through Ethernet backchannelsends [node_id, BVCoords] mapping through Ethernet backchannelKey Solution IdeasKey Solution IdeasDistributed Cache/Lookup SchemeDistributed Cache/Lookup SchemeConsistent hashing to spread the lookup-request load amongst Consistent hashing to spread the lookup-request load amongst beaconsbeaconsCache entry replacementCache entry replacementExplore cache size and replacement schemes to minimize Explore cache size and replacement schemes to minimize packets moving through network and balance with system packets moving through network and balance with system constraints (i.e. memory size, power, etc)constraints (i.e. memory size, power, etc)Eavesdropping schemeEavesdropping schemeNodes eavesdrop packets on route to beacons and cache Nodes eavesdrop packets on route to beacons and cache beacon responsesbeacon responsesNodes respond to beacon request to shorten response time and Nodes respond to beacon request to shorten response time and decrease network trafficdecrease network trafficCurrent Status and Future PlansCurrent Status and Future PlansCurrently implemented/tested:Currently implemented/tested:Initial version of BVR Location Service modules in place (no local Initial version of BVR Location Service modules in place (no local caching)caching)Cache modules in progressCache modules in progressCode tested in TOSSIMCode tested in TOSSIMHigh-level simulator (HLS) in progress for testing different High-level simulator (HLS) in progress for testing different caching schemescaching schemesFuture Plans:Future Plans:Integrate local caching into version 0.1 of Location ServiceIntegrate local caching into version 0.1 of Location ServiceTest and implement cache entry replacement in HLS and TOSSIMTest and implement cache entry replacement in HLS and TOSSIMTest BVR Location Service on MotesTest BVR Location Service on MotesTweak and turn knobs to find best performance/overhead Tweak and turn knobs to find best performance/overhead tradeoffs in real test-bedtradeoffs in real test-bedImplement Beacon election algorithmImplement Beacon election
View Full Document