1、1,Towards A Holistic Approach for System Design in Sensor Networks,Chair: Prof. Nael Abu-GhazalehCommittee Members: Prof. Kenneth ChiuDr. Tony FountainProf. Wendi HeinzelmanProf. Kyoung-Don KangProf. Michael Lewis,Sameer Tilak,2,Outline,WSN Applications and Challenges Summary of Contributions Holist
2、ic Principle WSN critical Subsystems and Services Holistic Framework Architecture Abstractions and Virtualization Conclusion and Future Work,3,Enablers Micro-sensors,Small (coin-matchbox-PDA range) Limited resources Battery operated Embedded processor (8-bit to PDA-class processor) Memory: KbytesMby
3、tes range Radio: (Kbps Mbps; often small range) Storage (none to a few Mbits),4,Embed numerous distributed devices to monitor and interact with physical world: hospitals, homes, vehicles, and “the environment”,Network these devices so that they can coordinate to perform higher-level tasks. Requires
4、robust distributed systems of hundreds or thousands of devices.,5,Sensor Node Specific Challenges,Low Battery power Low bandwidth Error-prone air medium Low computing power and memory Heterogeneous software and Hardware architectures,6,Sensor Network Challenges,Large-scale fine-grained heterogeneous
5、 sensing 100s to 1000s of nodes providing high resolution Spaced a few feet to 10s of meters apartCollaborative Each sensor has a limited view Spatially In terms of sensed data type Distributed Communication is expensive Localized decisions and data fusion necessary,7,Summary of Contributions,WSN cr
6、itical subsystems and services Information dissemination Storage Management Localization Holistic Framework Abstraction and virtualization,8,Holistic Principle,Data centric, resource constrained operation effective operation requires careful balancing of application level utility and cost (Principle
7、 1) Communication is expensive Localized interactions - produce local estimates of utility and cost (Principle 2) Local estimates of application level utility and cost can significantly differ from actual value observed globally Information available globally that significantly impacts local estimat
8、es are called context Identify and track context when it is worth it to do so (Principle 3),9,Non-Uniform Information Dissemination,WSN Critical Subsystems/Services,ICNP 2003, NCA 2004, NCA 2005, TR,10,Non-Uniform Information Dissemination,Loss in precision as a function of distance is acceptable,11
9、,Intuition,Forward packets less aggressively the further away you are from the event deterministically: e.g., forward every nth packet, n increase with distance probabilistically: e.g., forward packets with a probability that drops with distance from event Here, the context is spatial and can be eff
10、iciently tracked by tracking the distance from the source on the event packet Significant energy saving results, while keeping information accurate close to the event source,12,Randomized Protocols,Biased protocol: Packet forwarding decisions are based on a coin toss and relative distance from sourc
11、e. Forwarding probability is higher for physically closer sources. (Context) Simple, low overhead and very scalable,13,Weighted Energy-Error Study,14,High-level concluding remarks,Energy-efficient light-weight protocols that capitalize on non-uniform information granularity Context embedded in the f
12、orm of TTL (distance from an event source).,15,WSN Critical Subsystems/Services,Storage Management,IJAHUC 2005, Wiley Book chapter 2005, TR,16,Intuition,Exploit spatio-temporal redundancy Coordinate for redundancy control Context is Spatial,17,Candidate Protocols,Local Storage Local-Buffer Clusterin
13、g CBCS: Aggregate and Store and Cluster Head Context: CLS: Coordinate and store locally CCS: Combined CBCS + CLS,18,Clustering,Only CH stores dataRotate CH Distributed storage, medium fault-tolerance Spatial aggregation possible,Round 1 (time = 0),Round 2 (time = 20),Round 1 (time = 40),19,Round 1 (
14、time = 0),Round 1 (time = 40),Feedback Data,CH,Feedback provides context for data utility,CH has more global view than individual sensor,20,Storage and Energy Study,21,High-level concluding remarks,Collaborative protocols are scalable, light-weight, does load balancing and increase storage lifetime
15、Context provided in terms of feedback for redundancy control Context in space,22,Localization,IEEE IWSEEASN 2005,WSN Critical Subsystems/Services,23,Mobile Sensor Localization,Localization: Determine physical coordinates of a given sensor Existing research considers static sensor nets. Mobile sensor
16、sEnergy versus accuracy trade-offs Protocols SFR (Static Fixed Rate) DVM (Dynamic Velocity Monotonic) MADRD (Mobility Aware Dead Reckoning Driven),24,Existing Research on Localization,Assumes Static Sensor Network Focus on How to Carry Localization and not When Range/Direction Based Calculate distan
17、ce from anchors and triangulate Received Signal Strength (e.g. RADAR) Time of Arrival (e.g. GPS) Time Difference of Arrival (Cricket, Bat) ProximityBased Centroid ATIP DV HOPS MDS,25,Motivation,What about Mobile Sensor Networks ?Interesting Energy-Accuracy trade off !,26,Problem Definition,27,SFR,Lo
18、calize every t seconds Very simple to implement Once Localize tag data with those coordinates till next localization Energy expenditure independent of Mobility Performance varies with Mobility Existing Projects such as Zebranet use this approach (3 minutes).,28,DVM,Adaptive Protocol Sensor Adapts it
19、s localization frequency to Mobility Goal maintain error under application-specific tolerance Compute current velocity and use it to decide next localization period Once Localize tag data with those coordinates till next localization Upper and Lower query threshold Energy expenditure varies with Mob
20、ility Performance almost invariant of Mobility,29,MADRD,Predictive Protocol Estimate mobility pattern and use it to predict future localization Localization triggered when actual mobility and predicted mobility differs by application-specific tolerance Tag data with predicted coordinates (differs fr
21、om SFR and DVM)Changes in mobility model affect the performance Upper and Lower query threshold Energy expenditure varies with Mobility Performance almost invariant of Mobility,30,MADRD State Diagram,31,High-level Summary of Analysis,Error in non-predictive protocols increase with any mobility that
22、moves the node away from its last localization pointError in Predictive protocols increase only when the predictive Model is inaccurate Model estimation in incorrect Model changes (pause, direction change),32,33,Medium Speed (4-5 m/s),34,Error versus Pause time,35,Summary,Studied energy versus accur
23、acy tradeoff in localization for mobile sensorsDVM and MARD are completely distributed scalable protocolsDVM and MADRD outperform SFR Context Temporal,36,HOLISTIC APPROACH,Operation Management,Principle 1,Principle 2,Initial Idea,37,Context,Localized decisions leads to scalability Local estimate of
24、utility of data can differ from global measurement Absence of relevant global knowledge: Context Feedback can be used to improve accuracy of local estimate,38,Patterns & Types Context,Patterns Context in time Context in space Application-specific (domain knowledge) Resource related (src-dest path) T
25、ypes Utility context Cost context,39,Research Challenges,Data Utility Assessment Resource Cost Assignment Utility-Cost Normalization Tracking, Building, and Maintaining Context Middleware,40,Holistic Framework Architecture,Point in design space,41,Holistic Framework Components,Benefit Estimator Cost
26、 Calculator Planner,42,Benefit Estimator,Data Significance Data scope in Time, Space App-specific (observer interest) Data Quality Data Freshness, accuracy, resolution, App-specific measures Output Benefit Vector (BV) MAUT,43,Cost Calculator,Sensing, Transmission, Storage, Computational, Reception.
27、Output Cost Vector (CV): Vector of pre-determined transformations MAUT,44,Planner,Rule based engine. Input BV, CV Incorporates application state Objective: Maximize Benefit/Cost ratio,45,Instance of a Planner Algorithm,IF (Utility = HIGH)IF(STATE= NEED_LOCALIZATION)LOCALIZE AND THEN TRANSMIT If (Uti
28、lity = MEDIUM) Transmit If (Utility = MEDIUM) Low drop.,46,Component Placement Trade-offs,Middleware versus Application Benefit Estimator? Application-specific knowledge Cost Calculator? App/infrastructure communication Resource cost in middleware Planner? Single versus multiple apps,47,Abstraction,
29、EESR 2005,48,Related Work,Database Abstraction Programming abstractions e.g. Nesc TinyOS Plan-9, Inferno,49,File System Abstraction,Treat entire sensor network as a distributed file system Application-specific namespaces Well understood interface Heterogeneity Applications get fine grained control o
30、ver resources,50,Application-specific Namespaces,Making Abstractions efficient Default resource namespace,51,Applications,Monitoring and Calibration Debugging Sense & Respond Data Centric Application etc. Sample Usages mount /dev/network /network ls /network/cluster1/sensors/ cat /network/cluster1/s
31、1/remaining-energy echo 2.5 /network/cluster1/s1/control,52,query /network/cluster1/Location,Query Execution Scenario,Fine-grained resource controlExposes cost and utility explicitlyOptimized query planner (Below DB),53,Sense & Respond System,Heterogeneity,54,Abstraction & Virtualization,WSN Virtual
32、izationNCUS 2005,55,Virtual Sensor Networks,56,Micro-sensor Hardware,Berkeley Motes (Mica2) Pasta nodes Mantis-nymph WINS,57,Software Architectures,Operating Systems TinyOS Linux Windows CE MOS Programming Languages C nesC JAVA,58,Motivation for Resource Discovery Middleware,Mobile and Ad-Hoc sensor
33、 networks Rescue operations Battlefield scenarios Seamless Integrating of sensors to Grids Sensors control, configuration (remote),59,Mobile Sensor Network,Ad-Hoc Network Self-Configuration,60,Service Discovery Protocols,Scalable to thousands to sensors Energy-efficient Standardization Design Space
34、Proactive versus reactive Distributed versus centralized Tuned for Sensor network characteristics Minimize Transmission and reception of messages Sensors have low duty cycle radios,61,Our Approach,Register MessageQuery MessageResource Info. message,Cluster-Head,Resource registry,62,XML versus propri
35、etary format,10 10 100 100 -40 -40 100 100 -1 -1Describing resource in XML consumes 10 times more power than proprietary binary message,63,Message Formats,64,Conclusions,Application-specific, light-weight, energy-efficient protocols for critical services and subsystems Holistic principle and framewo
36、rk Abstraction and virtualization,65,Future Work,Holistic Framework VSN ICTs for developing regions,66,Questions ?,67,Thank You,68,Direction Change,69,Analysis of the Proposed Protocols,Constant Velocity model SFR and DVM error increases linearly MADRD estimates location precisely (no error)Constant
37、 Velocity + pauseSFR and DVM error increasely linearly and stays thereMADRD has 0 initial error and then it increases linearlyContant Vecloty + change in directionSFR: performs better if the turn is towards the prev localization point (turn 90deg to 270 deg) MADRD: otherwise performs better (DOES NOT increase/decrease linearly),70,Direction Change,
