Querying in Wireless Sensor NetworksQuerying Sensor NetworksCSN (chord for Sensor Networks)Slide 4Slide 5Slide 6Slide 7Slide 8Multi-Dimensional Range QueriesTraditional IndexingDIM (Distributed Index for Multi dimensional data)In short..Building zonesBuilding zones cont…When a new event is generated..Routing QueriesDrawback of DIMBloom filters in Hierarchical Clustering approachBloom filtersConstruction of bloom filterCluster FormationCluster formation cont…Cluster formation cont..Data DiscoveryMobility!!!Two Tier Data Dissemination(TTDD)TTDD Contd…Slide 28Slide 29Slide 30Slide 31Energy Efficient Data Dissemination(EEDD)EEDD Contd…Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Questions please…Querying in Wireless Sensor NetworksBy,Anil MoolaVaishnav KidambiPratapa Sanaga ReddyQuerying Sensor NetworksWhy querying?To retrieve the information To save energy in WSNDesign goals for querying methodsScalabilityEfficiencyReliabilityFault toleranceCSN (chord for Sensor Networks)Based on DHTWhy not DHTBounded Look up timeHierarchical Clustering approach CSN over comes implosion and overlapCSN (chord for Sensor Networks)Hierarchical clustering approachInitial set up: Ring Problem2 NP Complete problems!!Chain MethodSet Average MethodCSN (chord for Sensor Networks)Chain Method Chain Method for level 0(Base Station β , Set of all Sensorsπ0, Maximum no.of Sensors per Cluster λ0)1. cluster head ω = min(β )2. if (π0 == δ0) exit, where initially δ0 = /03. sensor αi = ω4. put αi in sets τ and δ0, where initially |τ | = 05. while(|τ| ≤λ0)6. αi.successor = min(αi)7. αi = αi.successor8. put αi in sets τ and δ09. αi.successor = ω10. ω = min(αi)11. goto 2CSN (chord for Sensor Networks)Set Average MethodSet-Average Method for level 0 (Base Station β , Set of allSensors π0, Maximum no.of Sensors per Cluster λ0)1. cluster head ω = min(β )2. if (π0 == δ0) exit, where initially δ0 = /03. list ν1 = min(ω,λ0), and let m =λ04. for k = 2,3, . . . ,m:5. νk = min(kth element of ν1,λ0)6. let ν be a set of lists7. ν = {ν1,ν2, . . . ,νm} 8. now, 1 ≤ occurrence of a sensor αi in ν ≤λ0)9. let set ε = / 0, and variable x =λ010. while(x ≥ 1 AND |ε| ≤λ0),11. for all sensors in ν :CSN (chord for Sensor Networks)12. if (occurrence of sensor αi in ν = x)13. insert sensor αi in set ε14. decrement x15. redefine min(X) to only return a sensor belongs to ε16. do step 3 to step 10 of the chain method17. goto 2CSN (chord for Sensor Networks)Incremental set up/ parallel set upEnergy efficient mode vs Robust ModeNaming sensor Nodes and data Incremental / parallel Naming Hashing Nodes and keys: Look up OperationMulti-Dimensional Range QueriesList all events that have temperature between 10C and 20C with humidity between 70% and 80%It help user efficiently drill down their search for event of interestIt enables application software to correlate eventsTraditional IndexingData is stored at a central point and uses indices which are computed when during insertion.Not feasible for sensor networks due to energy and bandwidth constraint.DIM (Distributed Index for Multi dimensional data)Foundations of DIMA locality preserving geographic hash - Consistently maps events to the some location with in the sensor network. Events whose attributes are closer are placed beside each other.User underlying geographic routing scheme such as GPSR to route events and queries to the corresponding node.In short..Each node in the network self organizes to own some attribute space for itself called zone, so events falling in that space are routed and stored in that node.Building zonesAssumption 1 : all nodes knowthe approximate geographic boundaries of the network. Sensor NodeWSN boundaryBuilding zones cont…If i is odd then parallel to Y-Axis else parallel to X-AxisZone of nodeLevel 2Level 3Level 4Code : 00Code : 010Code : 011Code : 100Code : 101Code : 110Code : 1110Code : 1111Assumption 2: Each node knows its geographic locationWhen a new event is generated..Hashing an event to a zone : Use an algorithm which maps the event to a code. Routing an event to its owner : Uses GPSR to send the event to its prospective owner.Routing QueriesNodeDrawback of DIMScalabilityEach node has to aware of it boundaryEach node has to aware of its geographic locationBloom filters in Hierarchical Clustering approachHierarchical clustering for data aggregation and reporting.ClusterHead – Summarize and forwards up data to application and guides queries down the hierarchy for appropriate dataBloom filter are integrated with hierarchical clusters.Bloom filtersTraditionally used it database and internet application.Conventional hash coding VS Bloom filtersSpace efficientConstruction of bloom filterSuppose we have n elements in set S and m bits of memoryFor each of n elements generate k different indices using k hash functions…………………0 12 3 M-2 M-1Cluster FormationCluster formation cont…Cluster formation cont..Top level sensor send beacon so some cluster heads will rebind to the cluster head on the shortest path to top.Remaining free sensors will go into hibernationData DiscoveryData retrieval by explicitly naming the node.Clusterhead maintains a set of bloom filtersOne represents all sensorsAnother represents the data that maybe found.To find the region of filters which has Temperature from 40 to 50 Moisture level from 20 to 30 etc…Mobility!!!What if the inquirer or the target are mobile?Two algorithms – Two Tier Data Dissemination. Energy Efficient Data Dissemination.Two Tier Data Dissemination(TTDD)Source based grid structure.Grid creation.(grid points, dissemination nodes…)Two Tier – Source -> Dissemination NodeDissemination Node -> Dissemination NodeGrid Maintenance – Grid lifetime.TTDD Contd…TTDD Contd…Aggregation and Routing.Query forwardingData forwardingTTDD Contd…TTDD Contd…Mobile Sink??? – Trajectory Data Forwarding.Primary Agent, Immediate AgentTTDD Contd…Energy Efficient Data Dissemination(EEDD)2 Disadvantages of TTDDSource based grid needs to be changed everytime the target moves.No emphasis on Energy Conservation!EEDD Contd…-Each sensor is aware of it’s location after deployment(virtual origin).-Nodes are stationary