Reliable, Robust Data Collection in Sensor NetworksMotivationOur approachAlgorithm overviewStatus and Future WorkSlide 6PrerequisitesSketch of algorithmReliable, Robust Data Collection in Sensor NetworksMurali RanganRussell SearsFall 2005 – SensornetMotivationData collection apps like habitat monitoringAll of the logged data is valuableReal time / in order delivery not importantIn-network aggregation not requiredCurrent data collection mechanismsLose data during temporary network partitionsOr, store all data in each nodeOur goalReliable, robust scheme to collect ALL the data in a steady stream, without in order guaranteesOur approachReliabilityLink level, hop-by-hop acknowledgementsIntroduce redundancy with k replicas of dataReplicas ensure their data reaches the base station, or pass responsibility to a parent.Take advantage of broadcast mediumTake advantage of existing routing algorithms (like MintRoute) for parent selectionKeep basic mechanism simple, add optimization on topAlgorithm overviewNode with new dataBroadcasts request for k volunteers (for replicas)Parent(s) agree to volunteerBroadcasts data to volunteer(s)Volunteer(s) broadcast hop ACK (HACK)Once k volunteers are found, deletes dataVolunteer transfers responsibility upstreamRepeats above process, seeking 1 volunteerOnce responsibility is transferred, deletes dataCan volunteer for same data again!Status and Future WorkBasic algorithm details are fleshed outImplement and simulate using TOSSIMWork in progress!Address the following challengesHow many replicas?Depends upon network density, reliabilityBase station broadcasts ACK to remove replicas of collected dataUse bloom filters to summarize?Limit broadcast to ‘interested’ nodes?How to bound k replicas?Eavesdropping?How do we deal with fan-in near the base station?Few parents / replicas share pathsPrerequisitesUse any routing protocol thatAssigns ‘parent(s)’ to each moteAdapts to changes in network topologyReliable link level deliveryMake use of broadcast mediumTransfer data from a child node to its parentsACK’s transfer responsibility for a piece of data. (Dropped ACK’s lead to more replicas)Broadcast ACK from base stationGuarantees replicas are eventually deletedEfficient, reliable broadcast? Bloom filters?Reverse path routing + eavesdropping?Sketch of algorithmInserting data into the networkBroadcast request for k volunteersBroadcast data, volunteers (parents) ACKOnce k volunteers are found, node deletes data.Volunteers request enough volunteers to create k replicas in network. (Usually, just create 1 volunteer)Pass ACK’s to children after creating > 1 replica.ChallengesHow many replicas?What about fan-in? Replicas share < k parentsShared paths?How can we optimize
View Full Document
Unlocking...