Question? Leave a message!




WSN Deployment

WSN Deployment 22
        Wireless Sensor Networks Prof. Jan Madsen Informatics and Mathematical Modelling Technical University of Denmark Richard Petersens Plads, Building 322 DK2800 Lyngby, Denmark Agenda for today  Wireless Sensor Networks (WSN)  What Why and How  WSN Deployment  Localization  WSN Networking  Routing protocols  MAC protocols  WSN Platforms  Hardware and software components  WSN Design methods  Summary and Future of WSN Graduate Course on Wireless Sensor Networks Jan Madsen 2      "  '         Towards Ambient Intelligence Weiser  Wireless network delivers infotainment, communication, navigation, ... anyplace, anytime, for every citizen ...  Hidden, pervasive computing. IT to background, people in the foreground, improves quality of life in noninvasive way ...  Things see, listen, feel, becomes sensitive and adaptive to people ... Graduate Course on Wireless Sensor Networks Jan Madsen 4 What is a sensor network Graduate Course on Wireless Sensor Networks Jan Madsen 5      "  '         Sensor Network Graduate Course on Wireless Sensor Networks Jan Madsen 6 intelligent dust 1 mm Graduate Course on Wireless Sensor Networks Jan Madsen 7      "  ' (        3 1 mm computer Graduate Course on Wireless Sensor Networks Jan Madsen 8 3 1 mm computer Thickfilm battery Solarcell Power capacitor Analog I/O, DSP, Control Sensors Passive optical transmitter Active optical transmitter Optical receiver RF radio Graduate Course on Wireless Sensor Networks Jan Madsen 9      "  ' )        3 1 mm computer 3 Thickfilm battery 1 J/mm 2 2 Solar cell 1 J/day/mm 110 mJ/day/mm 3 Power capacitor 10 mJ/mm Analog I/O, DSP, Control 1 nJ/sample 1 pJ/inst Sensors 0.1 nJ/bit Passive optical transmitter Active optical transmitter 1 nJ/bit Optical receiver Graduate Course on Wireless Sensor Networks Jan Madsen 10 3 1 mm computer still science fiction – but …  computations  1000 operations per sample  Indoor  one sample, compute and send per second Graduate Course on Wireless Sensor Networks Jan Madsen 11      "  '         The technology behind sensor networks Graduate Course on Wireless Sensor Networks Jan Madsen 12 CMOS Trends: miniaturization Itanium2 (241M ) nearly a thousand 8086’s would fit in a modern microprocessor S P C Actuation Communication Sensing Processing Storage I Σ∆ Q Σ∆ baseband PLL filters mixer LNA Graduate Course on Wireless Sensor Networks Jan Madsen 13      "  ' '        New Technology SweetSpot (uW – mW)  CMOS miniaturization 2  1 M trans/ = tiny (mm ), inexpensive processing and storage  110 mW active, 1 µ W passive (at 1 use 100 µ Wave)  Microsensors (MEMS, Materials, Circuits)  acceleration, vibration, gyroscope, tilt, magnetic, heat, motion, pressure, temp, light, moisture, humidity, barometric  chemical (CO, CO2, radon), biological, microradar, ... S P C  actuators too (mirrors, motors, smart surfaces, microrobots)  Communication  short range, low bitrate, CMOS radios (110 mW)  Power 3  batteries remain primary storage (1,000 mWs/mm ), fuel cells 10x 2,  solar (10 mW/cm 0.1 mW indoors), vibration (uW/gm), flow 3  1 cm battery = 1 year at 1 msgs/sec Graduate Course on Wireless Sensor Networks Jan Madsen 14 Sensor Node Architecture rtos sensor cpu radio S P C Mem battery       Graduate Course on Wireless Sensor Networks Jan Madsen 15      "  ' +        CMOS trend: miniaturisering Graduate Course on Wireless Sensor Networks Jan Madsen 16 How can we use sensor networks Graduate Course on Wireless Sensor Networks Jan Madsen 17      "  ' ,        Where Computing is Done Number Crunching Data Storage productivity interactive streaming information to/from physical world year Graduate Course on Wireless Sensor Networks Jan Madsen 18 Health monitoring ECG, Blood Blood Composition Pressure (e.g. lactate) Wearable Digital Wireless Assistant Link to Coach and Med Team Multiple Hop Position BAN Force Sensors courtisy Rudy Lauwereins (MPSOC02) Graduate Course on Wireless Sensor Networks Jan Madsen 19      "  '         Smartshirt wearable computing Graduate Course on Wireless Sensor Networks Jan Madsen 20 ... or implants Graduate Course on Wireless Sensor Networks Jan Madsen 21      "  '         Electronic devices for diagnostics Graduate Course on Wireless Sensor Networks Jan Madsen 22 Smart pills – 1st generation Graduate Course on Wireless Sensor Networks Jan Madsen 23      "  '         Smart pills – 2nd generation Graduate Course on Wireless Sensor Networks Jan Madsen 24 Examples of sensor networks Graduate Course on Wireless Sensor Networks Jan Madsen 25      "  '         Sensor Network Dataopsamling Graduate Course on Wireless Sensor Networks Jan Madsen 27 Sensor network sensor net sensor net sensor net gateway database internettet database Graduate Course on Wireless Sensor Networks Jan Madsen 28      "  ' (        Biologi Mainwaring(Intel),Anderson(COA),Szewczyk,Polastre(UCB) Acadia National Park Mt. Desert Island, ME 1000 ft Great Duck Island Nature Conservancy Leach’s Storm Petrel 2 ft Graduate Course on Wireless Sensor Networks Jan Madsen 29 Biology: State of the Art Graduate Course on Wireless Sensor Networks Jan Madsen 30      "  ' )        Solution using sensor networks http://www.greatduckisland.net Processing, Storage Wireless network Light, Temp, Humidity, Barometer, Passive IR (occupancy) Graduate Course on Wireless Sensor Networks Jan Madsen 31 Hierarchical deployment Graduate Course on Wireless Sensor Networks Jan Madsen 32      "  '         Sensors  Mica platform – Atmel AVR w/ 512kB Flash – 916MHz 40kbps RFM Radio  Range: max 100 ft  Affected by obstacles, RF propogation – 2 AA Batteries, boost converter  Mica weather board – “one size fits all” – Digital Sensor Interface to Mica  Onboard ADC sampling analog photo, humidity and passive IR sensors  Digital temperature and pressure sensors – Designed for Low Power Operation  Individual digital switch for each sensor – Designed to Coexist with Other Sensor Boards  Hardware “enable” protocol to obtain exclusive access to connector resources  Packaging – Conformal sealant + acrylic tube – Placement – Place above ground and in burrows (propagation) Graduate Course on Wireless Sensor Networks Jan Madsen 33 Gateway  Communicate with sensor and base station.  Solar powered (sensors are just battery powered).  Directional antenna pointed toward base station. Graduate Course on Wireless Sensor Networks Jan Madsen 34      "  ' '        Base station  Laptops  In lighthouse keepers house.  Log all data and transmit via satellite to D.C. and then on to the Internet. Graduate Course on Wireless Sensor Networks Jan Madsen 35 ZebraNet  Goal: Biologists want to track animals longterm, over longdistances  Interactions within a species  Interactions between species  Impact of human development Graduate Course on Wireless Sensor Networks Jan Madsen 36      "  ' +        ZebraNet as Computing Research © 2006 Tracking node with Martonosi CPU, FLASH, radio and GPS Data Storeandforward Data communications Data Data Base station (car or plane) ZebraNet vs. Other SensorNets  All sensing nodes are mobile Research Questions  Large area: 100’s1000s sq. kilometers  Protocols and mobility  “CoarseGrained” nodes  Energyefficiency  GPS onboard  Software layering design  Longrunning and autonomous Graduate Course on Wireless Sensor Networks Jan Madsen 37 ZebraNet basics F F F M F F F F F F M b F F F a F F F M F F F c Graduate Course on Wireless Sensor Networks Jan Madsen 38      "  ' ,        ZebraNet basics F F F F F F M M F F F F F a,b F F a,b F F M F F F c Graduate Course on Wireless Sensor Networks Jan Madsen 39 Construction monitoring Wind Response Of Golden Gate Bridge Low resolution Sensor, Test4, Increasing frequency 1 0.5 0 0.5 1 0 2 4 6 8 10 12 14 16 18 Time (sec) Graduate Course on Wireless Sensor Networks Jan Madsen 41      "  ' Acceleration (g)        Construction monitoring Earthquake Response, Glaser et al. Mote 1 Layout 54 1 1 1 ` 12 5 5 6 3 9 1 1 8 Graduate Course on Wireless Sensor Networks Jan Madsen 42 Industrial Automation: Predictive Maintenance                                   Dust Networks Graduate Course on Wireless Sensor Networks Jan Madsen 43      "  '         Security: Small to Medium Commercial Property       "                           Dust Networks Graduate Course on Wireless Sensor Networks Jan Madsen 44 Military applications Sentries, UVA, OSU Graduate Course on Wireless Sensor Networks Jan Madsen 45      "  '         Shooter localization Red circle: Shooter position Red line:  Shot direction Large green circle: Sensor node (good measurement) Small green dot: Sensor Node (no or unused measurement) Graduate Course on Wireless Sensor Networks Jan Madsen 46                                 Precision Agriculture Field Preparation Planting Planning Cultivation Water Management  Land Leveling  Subsurface Drainage Fertilizer Application Crop Protection Harvesting Soil Sampling Mapping Crop Scouting Graduate Course on Wireless Sensor Networks Jan Madsen 47      "  '         sensor network research at IMM/DTU Graduate Course on Wireless Sensor Networks Jan Madsen 48 Wireless Sensor Networks            .     /      " Graduate Course on Wireless Sensor Networks Jan Madsen 49      "  ' (        Motivation      0   (    (0 )0    ) ()                     Graduate Course on Wireless Sensor Networks Jan Madsen 50 Motivation Current status for the farmer  Farmer reads information about sows through RFID eartags  Has to be within 10 cm from the tag  Important to move sows between pens at the right point in time  Is there a better way Graduate Course on Wireless Sensor Networks Jan Madsen 51      "  ' )        Motivation  Let the sow phone the farmer when:  It needs to be moved  Has to give birth  Is ill  ...  Sensor network  Sensor nodes  Adhoc network infrastructur  Detection of abnormal animal behavior  The Hogthrob project Graduate Course on Wireless Sensor Networks Jan Madsen 52 The Hogthrob project  Developing a sensor network infrastructure for sow monitoring  Sensor nodes on a chip  Sensor network model  Monitoring application  Functionalities  Tracking  Detecting heat period  …             Low cost (1 €)        Low energy (2 years lifetime)  Consortium:  DTU  DIKU  KVL  National Committee for Pig Production  IO Technologies                 Graduate Course on Wireless Sensor Networks Jan Madsen 53      "  '         Sow monitoring Some issues: Initial application model  State transitions managed by timer + sensing   Different duty cycles (processing / sending)  Refined model based on observations of pig behavior     Tradeoffs:  Sleeping vs. Sensing and Networking     Inchannel wakeup vs. Additional, low power radio  Embedded detection model vs.  Feed to a serverbased detection model Graduate Course on Wireless Sensor Networks Jan Madsen 54 Sensor nodes (V0)        Graduate Course on Wireless Sensor Networks Jan Madsen 55      "  ' '              First field experiments  Sensor board with 2D and 3D accelerometer  Tracking motions correlated with video Graduate Course on Wireless Sensor Networks Jan Madsen 56 Results from first field experiments Graduate Course on Wireless Sensor Networks Jan Madsen 57      "  ' +        Results from first field experiments Moving average of hourly values (span=24,sigma=3) 0103 to 2003 Averages chip 1 acc 1.025 1.020  Moving average and 1.015 Control Chart 1 2 3 4 5 6 7 8 9 1011 1213 1415 16 1718 1920 chip 2 acc  EWMA to develop 1.05 1.00 0.95 Example 1 2 3 4 5 6 7 8 9 1011 1213 1415 16 1718 1920 chip 3  24 H Moving Average acc 1.07 1.06 1.05  Control Limit: 3 sigma 1.04 1 2 3 4 5 6 7 8 9 1011 1213 1415 16 1718 1920  under CL chip 4 acc 1.04 1.03 1.02  above CL 1.01 1.00 0.99 0.98 1 2 3 4 5 6 7 8 9 1011 1213 1415 16 1718 1920  Need more chip 5 acc 1.02 information 1.01 1.00 0.99 0.98 0.97 0.96 1 2 3 4 5 6 7 8 9 1011 1213 1415 16 1718 1920 Time, in days Graduate Course on Wireless Sensor Networks Jan Madsen 58 Deployment  Stochastic modelling  Random graphs Graduate Course on Wireless Sensor Networks Jan Madsen 59      "  ' ,        Localization  What to localize  When to localize  How well to localize  How to localize Graduate Course on Wireless Sensor Networks Jan Madsen 60 Networking  Graphs  Protocols  Peer to peer  broadcast  Routing Graduate Course on Wireless Sensor Networks Jan Madsen 61      "  '         Wireless communication  Bandwidth and latency  Collisions and how to avoid them  MAC Graduate Course on Wireless Sensor Networks Jan Madsen 62 WSN Platform os sensor cpu radio Mem batteri Graduate Course on Wireless Sensor Networks Jan Madsen 63      "  ' ( software        Agenda for today  Wireless Sensor Networks (WSN)  What Why and How  WSN Deployment  Localization  WSN Networking  Routing protocols  MAC protocols  WSN Platforms  Hardware and software components  WSN Design methods  Summary and Future of WSN Graduate Course on Wireless Sensor Networks Jan Madsen 64     Graduate Course on Wireless Sensor Networks Jan Madsen 65      "  ' (        Deployment Issues  Structured versus Randomized Deployment  Overdeployed versus Incremental Deployment  Connectivity and Coverage Metrics of Interest Graduate Course on Wireless Sensor Networks Jan Madsen 66 Network Topologies                                                                                                                   Graduate Course on Wireless Sensor Networks Jan Madsen 68      "  ' (        Random Graph Models  For some applications, WSN nodes could be scattered randomly (e.g. from an airplane)  Random Graph Theory is useful in analyzing such deployments  The most common random graph model is  G(n,R): deploy n nodes randomly with a uniform distribution in a unit area, placing an edge between any two that are within Euclidean range R. Graduate Course on Wireless Sensor Networks Jan Madsen 69 Geometric Random Graph G(n,R) sparse dense          Graduate Course on Wireless Sensor Networks Jan Madsen 71      "  ' ((        Some Key Results  All monotone graph properties have an asymptotic critical range R beyond which they are guaranteed with high probability (Goel, Rai, and Krishnamachari ‘04)  The critical range for connectivity is (Penrose ‘97, Gupta and Kumar ‘98)  The critical range to ensure that all nodes have at least k neighbors also ensures kconnectivity w.h.p. (Penrose ‘99) Graduate Course on Wireless Sensor Networks Jan Madsen 72 Connectivity in G(n,R)          Graduate Course on Wireless Sensor Networks Jan Madsen 73      "  ' ()        TransmitPower Control  Provides a degree of flexibility in configuring the network connectivity after deployment.  Must carefully balance several factors, including connectivity, energy usage, and interference.  The ConeBased Topology Control (Li et al. ‘01) provides a distributed rule for global connectivity:  increase power until there is a neighbor within range in every sector of angle α≤5π/6          Graduate Course on Wireless Sensor Networks Jan Madsen 74 Coverage Metrics  Much more application specific than connectivity.  Some that have been studied in particular detail are:  Path observation metrics: An example of this is the maximal breach distance, defined as the closest any evasive target must get to a sensor in the field (Meguerdichian et al. ‘99)  KCoverage: ensure that all parts of the field are within sensing range of K sensors (e.g. Wang et al. ‘03)          Graduate Course on Wireless Sensor Networks Jan Madsen 75      "  ' (        Key Results on KCoverage  A field is Kcovered if and only if all intersection points between sensing circles are at or inside the boundary of K+1 sensing circles. (Wang et al. ‘03) A 2covered region  If a region is Kcovered by n sensors, they also form a Kconnected graph if their communication range is at least twice the sensing range. (Wang et al. ‘03)          Graduate Course on Wireless Sensor Networks Jan Madsen 76                 Graduate Course on Wireless Sensor Networks Jan Madsen 77      "  ' ('        Localization Issues  Location information necessary/useful for many functions  measurement stamps  coherent signal processing  cluster formation  efficient querying  routing  Key Questions:  What to localize  When to localize  How well to localize  How to localize Graduate Course on Wireless Sensor Networks Jan Madsen 78 Coarse Grained Node Localization  Several techniques provide approximate solutions for node localization based on the use of minimal information:  Proximity  Centroids  Geometric Constraints  Approximation Point in Triangle  Identifying Codes Graduate Course on Wireless Sensor Networks Jan Madsen 79      "  ' (+        Geometric Constraints Reference node Unknown node Constrained location region Sector Disc Quadrant Annulus (Doherty, Pister and Ghaoui ‘01) Graduate Course on Wireless Sensor Networks Jan Madsen 80 IDCodes (Ray et al. ‘03) Graduate Course on Wireless Sensor Networks Jan Madsen 81      "  ' (,        FineGrained Node Localization  Basic Approach: Ranging  ranging using radio signal strengths (mlevel accuracy)  ranging using time difference of arrival (cmlevel accuracy over short distances)  Position estimation is then an MMSE problem: 2 2 E = R √ ((xx ) +(yy ) ) j i,j i j i j 2 Find (x,y) to minimize Σ (E ) i i j  Angle of arrival techniques are particularly useful in conjunction with ranging          Graduate Course on Wireless Sensor Networks Jan Madsen 82 Time Difference of Arrival T o Transmitter Acoustic RF Receiver T T r s Distance ≅ (T –T ) . V r s s          Graduate Course on Wireless Sensor Networks Jan Madsen 83      "  ' (        FineGrained Node Localization  Pattern matching techniques such as RADAR (Bahl and Padmanabhan, ‘00) require pre training of signal strengths at different locations in the environment.  Ecolocation (Yedavalli et al. ‘04) is based on sequence decoding.  Record the received signal strengths at different reference nodes from a given unknown node, and order these into a sequence  Return as the unknown node’s location the location that “best matches” the measured sequence          Graduate Course on Wireless Sensor Networks Jan Madsen 84 Network Localization  Different from node localization. Few reference nodes and several networked unknown nodes.  Several approaches:  Constraint satisfaction/optimization (centralized)  Joint estimation using ranging estimates (centralized)  Multihop distance estimation (distributed)  Iterative localization (distributed)  Potential fields (distributed)          Graduate Course on Wireless Sensor Networks Jan Madsen 85      "  ' )        Iterative Localization (0,10) C D (10,10) F (5,5) E I G J L K A H B (10,0) (0,0)          Graduate Course on Wireless Sensor Networks Jan Madsen 86 Localization protocol  Idea:  Wait for position/distance from 3 different neighbours  Calculate own position  Tell all neighbours about position  Assume  Sensors have unique identifier (number)  Sensors are fixed, i.e. not mobile  All sensors are deployed at start  All sensors are working and have unlimited power supply Graduate Course on Wireless Sensor Networks Jan Madsen 87      "  ' )        Exercise  Device a protocol for localization of all nodes in a network  Use the following  Messages:  HELLO() sender wants to know position of neighbours  HI(pos) senders position  Node data:  Neighbours tabel of neighbours  (no, pos,distance) for each neighbour  MyPos own position ( If unknown) Graduate Course on Wireless Sensor Networks Jan Madsen 88 Solution send HELLO() to all repeat receive b from nb with distance d if b=HELLO() send HI(MyPos) to nb if b=HI(pos) add (nb, pos, d) to Neighbours if MyPos= And MyPos can be calculated from Neighbours MyPos = position(Neighbours) send HI(MyPos) to all Graduate Course on Wireless Sensor Networks Jan Madsen 89      "  ' )        Referenceless Localization  What if there are no reference nodes with known locations  Threestep solution (Rao ‘03):  1. If all boundary nodes have known locations, use iterative centroid calculations  2. If boundary nodes do not have known locations, use pairwise hopcounts to get approximate locations and apply step 1.  3. If nodes are not aware of boundary, use a flood to identify boundary nodes and apply step 2.  The solution provides only a relative map, useful for geographic routing Graduate Course on Wireless Sensor Networks Jan Madsen 90 Illustration of Referenceless Localization Localization assuming only Correct locations known boundary nodes          Graduate Course on Wireless Sensor Networks Jan Madsen 91      "  ' )(        Agenda for today  Wireless Sensor Networks (WSN)  What Why and How  WSN Deployment  Localization  WSN Networking  Routing protocols  MAC protocols  WSN Platforms  Hardware and software components  WSN Design methods  Summary and Future of WSN Graduate Course on Wireless Sensor Networks Jan Madsen 92                Graduate Course on Wireless Sensor Networks Jan Madsen 93      "  ' ))        Routing Considerations in Sensor Networks  Traditional TCP/IP routing not attractive for sensor networks  Too much overhead and large routing tables  Sensor networks are more adhoc  Each node acts as a router  Still different than adhoc networks  Proactive routing is too expensive  Some possibility for reactive routing such as  Fisheye routing, AODV, DSR Graduate Course on Wireless Sensor Networks Jan Madsen 94 Routing Goal  Focus on localized stateless routing  Consider only local neighborhood  Classical separation of address and content does not hold  Care about reaching the nodes rather than a particular address – what can be sensed by a node can most probably be sensed by neighboring nodes  Interested in routing by attributes – data centric  Node’s location  Node’s type of sensors  Range of values in the sensed data  Notion of optimality can vary  QoS routing – latency is important = shortest path  Energy aware routing – longer paths are ok = avoid nodes with less energy Graduate Course on Wireless Sensor Networks Jan Madsen 95      "  ' )        Flooding  Simple routing protocol  Assumes connection to neighbors known  Packets are launched from sender through the whole network  A node will not send the same message twice    Very robust  but not very efficient in terms of cost Graduate Course on Wireless Sensor Networks Jan Madsen 96 Adaptive routing step N D(2) D(3) D(4) D(5) D(6)  Table based 0 1 2 1 3∞∞  Keep a table of possible paths (e.g. shortes) 1 1,3 2 1 2 4∞  Multiple paths in order to 2 1,2,3 2 1 2 3 4 increase robustness 3 1,2,3, 2 1 2 3 4  Linkstate protocols 4 4 1,2,3, 2 1 2 3 4  Use flooding to obtain routes 4,5    5 1,2,3, 2 1 2 3 4   4,5,6                        Graduate Course on Wireless Sensor Networks Jan Madsen 97      "  ' )'        When is the path computed  Static  or Demand Driven  Destination sends reply to each query it receives  Source selects one of more return paths  Approaches  Dynamic Source Routing (DSR)  Adhoc OnDemand Vector routing (AODV) Graduate Course on Wireless Sensor Networks Jan Madsen 98 Dynamic Source Routing (DSR)  RREQ: Route Request  RREP: Route Reply      Problem: header may be      large   Possible optimizations:                  A node may know about a route                 If 4 knows about the route      to 6, it may immediately tell         1 when receiving RREQ. Graduate Course on Wireless Sensor Networks Jan Madsen 99      "  ' )+        Adhoc OnDemand Vector routing (AODV)  Aim:  Eliminate routing header  Done by requiring nodes to         maintain routing tables              Has to be update if nodes change Graduate Course on Wireless Sensor Networks Jan Madsen 100 Geographic Routing  Aims to route based on very limited state information  Geographic routing protocols assume  All nodes know their geographic location  Each node knows its 1hop neighbors  Destination is a node with a given location  Each packet can hold a limited amount of information as to where it has been in the network  Any issues with this  Needs to maintain information between node IDs and node location (referred to as location service) Graduate Course on Wireless Sensor Networks Jan Madsen 101      "  ' ),        Geographic Forwarding Approaches  Greedy distance routing: select the neighbor geographically closest to the destination and forward the data to that neighbor  Compass routing: pick the next node as the one that minimizes the angle to destination  What are the problems with the basic approaches  Greedy distance routing – may get stuck in local minima  Compass routing – may go in loops Graduate Course on Wireless Sensor Networks Jan Madsen 102 Planarization of Routing Graph  To get protocols that guarantee data delivery, make graph planar  Remove some edges from your network graph G  Aim: Keep the same connectivity but make the graph planar  no two edges in G should intersect each other  In the planar subdivision of G each node is assumed to know the circular order of its neighbors  Convex perimeter routing and other face routing protocols use this property Graduate Course on Wireless Sensor Networks Jan Madsen 103      "  ' )        Common Planarization Methods  Relative Neighborhood Graph (RNG)  The edge xy is introduced if the intersection of circles centered at x and y with radius the distance d(x,y) is free of other nodes y x  Gabriel Graph  The edge xy is introduced if the diameter xy is free of other nodes y x  Both graphs RNG and Gabriel graphs can be found with distributed construction          Graduate Course on Wireless Sensor Networks Jan Madsen 104 Greedy Perimeter Stateless Routing(GPSR)  Geographic protocol based on the offline construction of planar graphs  RDG, Gabriel  Has 2 main phases forwarding and recovery  Forwarding is greedy  Recovery – uses a righthand rule to recover from holes. It stops as soon as a node closer to the destination is found Graduate Course on Wireless Sensor Networks Jan Madsen 105      "  '                                Graduate Course on Wireless Sensor Networks Jan Madsen 106 Network Communication  Flooding  Redundant data transmission  Multihop routing  Large routing tables  Frequent updates  Complexity Graduate Course on Wireless Sensor Networks Jan Madsen 107      "  '         Directed diffusion concepts  Applicationaware communication primitives  expressed in terms of named data (not in terms of the nodes generating or requesting data)  Consumer of data initiates interest in data with certain attributes Interest Reply type = fourlegged animal type = fourlegged animal interval = 20 ms instance = 125, 220 duration = 10 sec intensity = 0.6 rect = 100, 100, 200, 400 confidence = 0.85 timestamp = 01:20:40 Graduate Course on Wireless Sensor Networks Jan Madsen 108 Directed diffusion concepts  Nodes diffuse the interest towards producers via a sequence of local interactions thereby setting up gradients.  Reinforcement and negative reinforcement used to converge to efficient distribution  Intermediate nodes opportunistically fuse interests, aggregate, correlate or cache data.  Dirrected Diffusion illustration Graduate Course on Wireless Sensor Networks Jan Madsen 109      "  '         Directed Diffusion illustration B Event B C Event C Source A F A F Sink Sink D D E (b E (a) ) B B C C Source Source A A F F Sink Sink D D E E (c) (d) (Intanagonwiwat, Govindan, Estrin ‘00) Graduate Course on Wireless Sensor Networks Jan Madsen 110 Local Behavior Choices 1. For propagating interests  Flooding  More sophisticated behaviors possible: e.g. based on cached information, GPS 2. For setting up gradients  Highest gradient towards neighbor from whom we first heard interest  Others possible: towards neighbor with highest energy Graduate Course on Wireless Sensor Networks Jan Madsen 111      "  ' (        Local Behavior Choices 3. For data transmission  Different local rules can result in single path delivery, striped multipath delivery, single source to multiple sinks and so on. 4. For reinforcement  reinforce one path, or part thereof, based on observed losses, delay variances etc.  other variants: inhibit certain paths because resource levels are low Graduate Course on Wireless Sensor Networks Jan Madsen 112 Directed Diffusion  Paths formed probabilistically using a combination of activation and inhibition signals  Inspired by ants (swarm intelligence )  Ex. Minimizing energy over the path:  Activation: desire to send the message, for which a certain amount of energy is allotted  Inhibition: energy cost of traversing the remaining set of links to the destination Graduate Course on Wireless Sensor Networks Jan Madsen 113      "  ' )        Directed Diffusion example                                        Tiers  Probability to move inside tire is 50 of probability to move between tiers  Never move backwards Graduate Course on Wireless Sensor Networks Jan Madsen 114 Rumor Routing Source event notification Source Pointer to source located Sink interest Sink (Braginsky and Estrin ‘02) Graduate Course on Wireless Sensor Networks Jan Madsen 115      "  '         Initial simulation studies (Intanago, Estrin, Govindan)  Compare diffusion to  a) flooding,  b) centrally computed tree (“ideal”)  Key metrics:  total energy consumed per packet delivered (indication of network life time)  average packet delay Graduate Course on Wireless Sensor Networks Jan Madsen 116 Simulation results FLOODING DIFFUSION CENTRALIZED Graduate Course on Wireless Sensor Networks Jan Madsen 117      "  ' '        Simulation results CENTRALIZED DIFFUSION FLOODING Graduate Course on Wireless Sensor Networks Jan Madsen 118 Directed diffusion  Description of networking paradigm  Interests, gradients, reinforcement  Benefits of innetwork processing  Aggregation and nestedqueries  Efficient and stable  Handles dynamic network well  Not substantially more dissipation than static  Disadvantages  Design doesn’t deal with congestion or loss Graduate Course on Wireless Sensor Networks Jan Madsen 120      "  ' +        Agenda for today  Wireless Sensor Networks (WSN)  What Why and How  WSN Deployment  Localization  WSN Networking  Routing protocols  MAC protocols  WSN Platforms  Hardware and software components  WSN Design methods  Summary and Future of WSN Graduate Course on Wireless Sensor Networks Jan Madsen 121                 Graduate Course on Wireless Sensor Networks Jan Madsen 122      "  ' ,        Medium Access Control  A MAC protocol decides when competing nodes may access the shared channel  Tries to ensure interferencefree transmission  Two main classes of protocols:  Contentionbased  Schedulebased Graduate Course on Wireless Sensor Networks Jan Madsen 123 MAC protocol classification                                 "   '()(                                                                                                            Graduate Course on Wireless Sensor Networks Jan Madsen 124      "  '         ContentionBased Medium Access  ALOHA protocol  Transmit package as soon as it is generated  If no other node is sending  Data transmission succeeds  Receiver responds with an acknowledgement  If collision  Then no acknowledgement is received  Sender retries after random period  Very simple protocol  Basic version: Max. channel utilization 18  Slotted version can reach 35 Graduate Course on Wireless Sensor Networks Jan Madsen 125 Carrier Sense Multiple Access  CSMA  Before transmitting a package  Sender listens to the channel for a short period of time  If no traffic is sensed  Then channel is clear  Start transmitting package  Problem  Mode switching latency (receive mode to transmit mode)  i.e. collisions can occure  Max. channel utilization: 50 – 80 Graduate Course on Wireless Sensor Networks Jan Madsen 126      "  ' '           Carrier Sense Multiple Access  CSMA         Sequence diagram                            Graduate Course on Wireless Sensor Networks Jan Madsen 127 Carrier Sense Multiple Access  CSMA/CA           Graduate Course on Wireless Sensor Networks Jan Madsen 128      "  ' '                 Carrier Sense Multiple Access  CSMA/CA             ++  ++   Graduate Course on Wireless Sensor Networks Jan Madsen 129 Carrier Sense Multiple Access  CSMA                                  Graduate Course on Wireless Sensor Networks Jan Madsen 130      "  ' '              IEEE 802.11 (WLAN)  CSMA/CA and ACK                                                                                                                                   Graduate Course on Wireless Sensor Networks Jan Madsen 131 ScheduleBased Meduim Access  TDMA  Collision free  No idle listening …  Challenge  To adapt TDMA to operate efficiently in ad hoc sensor networks Graduate Course on Wireless Sensor Networks Jan Madsen 132      "  ' '(        Energy efficiency  Adhoc network with little traffic  Energy wasted due to:  Idle listening  Collisions  Overhearing  Protocol overhead  Traffic fluctuations Graduate Course on Wireless Sensor Networks Jan Madsen 133 EnergyEfficient Contentionbased MAC  Low Power Listening / Preamble Sampling: wake up the radio only when needed to transmit, and periodically to check for preamble from transmitter. No synchronization necessary.  SMAC/DMAC: periodic sleepwake duty cycle, adapted for higher traffic, adjusted to minimize delay.  Asynchronous: use a periodic schedule but not synchronized across nodes. Useful for highly dynamic scenarios. Graduate Course on Wireless Sensor Networks Jan Madsen 134      "  ' ')        Preamble Sampling Preamble Send Data Message Sender S R Receiver Active to Receive Message Preamble Sampling (El Hoiydi ‘02; Hill and Culler ‘02) Graduate Course on Wireless Sensor Networks Jan Madsen 135 SMAC Objectives  Main objectives  Reducing energy consumption  Main sources of energy waste  Collision  Overhearing  Control packet overheard  Idle listening  SMac should also provide good scalability and collision avoidance Graduate Course on Wireless Sensor Networks Jan Madsen 136      "  ' '        SMAC Design – Periodic Sleep Cycle  Nodes’ radios are turned down during sleep periods  Duty cycle reduced  Neighbouring nodes are synchronized together On Off On Off On Off On Off On Off On Off (Ye, Heidemann and Estrin ‘02)  Each node has its own schedule table  Synchronization is maintained by use of SYNC packets Graduate Course on Wireless Sensor Networks Jan Madsen 137 SMAC Design – Collision and Overhearing  Collision avoidance based on 802.11 technique  Physical and virtual carrier sense  Exchange of RTS/CTS messages  Overhearing avoidance  Nodes listen to ACK packet  Interfering nodes are put in sleep mode Graduate Course on Wireless Sensor Networks Jan Madsen 138      "  ' ''        SMAC Design – Message passing  High cost transmission errors in a long message  Message retransmitted if only a few bits corrupted  SMAC approach:  Message fragmented into small parts  Fragments transmitted in a burst  Uses CTS /RTS only once for whole message  ACK packets are transmitted after each fragments  Nodes that wake up in a middle of a transmission can return to sleep mode  Fragments lost can be retransmitted Graduate Course on Wireless Sensor Networks Jan Madsen 139 Agenda for today  Wireless Sensor Networks (WSN)  What Why and How  WSN Deployment  Localization  WSN Networking  Routing protocols  MAC protocols  WSN Platforms  Hardware and software components  WSN Design methods  Summary and Future of WSN Graduate Course on Wireless Sensor Networks Jan Madsen 141      "  ' '+               SW os sensor radio cpu Mem batteri Graduate Course on Wireless Sensor Networks Jan Madsen 142 Wide Spectrum of Devices  Sensors with inplantable RFIDs  Smartdust size nodes  Typically they act as datacollectors or “tripwires”  Cannot afford to have massive processing and communication  Motesize devices  More powerful gateway nodes etc  For some applications, form factor is also dictated by the size of individual sensors  Many designs out there, each design has its own philisophy Graduate Course on Wireless Sensor Networks Jan Madsen 143      "  ' ',        Sensor node  Ultra low energy  Low flexibility  Ultra low cost (1)  Small size (1..10 Mtr) rtos  Low clock frequency sensor cpu radio  DSP and RF dominated  Limited memory battery  Hardware/software codesign Graduate Course on Wireless Sensor Networks Jan Madsen 145 Sensor node design sensor sensor radio rtos rtos sensor asic cpu cpu radio battery       Graduate Course on Wireless Sensor Networks Jan Madsen 146      "  ' '        Challenges  Energy Efficiency  Responsiveness  Robustness  SelfConfiguration and Adaptation  Scalability  Heterogeneity  Systematic Design  Privacy and Security Graduate Course on Wireless Sensor Networks Jan Madsen 149                                 Graduate Course on Wireless Sensor Networks Jan Madsen 150      "  ' +        Sensor node rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 151 Requirements  Cost  Lifetime (when almost always on, when almost always off)  Performance:  Speed (in ops/sec, in ops/joule)  Comms range (in m, in joules/bit/m)  Memory (size, latency)  Capable of concurrent operation  Flexibility ()  Reliability, security, size, packaging Graduate Course on Wireless Sensor Networks Jan Madsen 152      "  ' +        Sensoractuator hardware platforms 1. RFID equipped sensors 2. Smartdust tags  typically act as datacollectors or “tripwires”  limited processing and communications 3. Mote/Stargatescale nodes  more flexible processing and communications 4. More powerful gateway nodes, potentially using wall power Graduate Course on Wireless Sensor Networks Jan Madsen 153 A closer look Graduate Course on Wireless Sensor Networks Jan Madsen 154      "  ' +        A Generic Sensor Network Architecture SENSING PROCESSING COMMUNICATION SUBSYSTEM SUBSYSTEM SUBSYSTEM ACTUATION POWER MGMT. SECURITY SUBSYSTEM SUBSYSTEM SUBSYSTEM Graduate Course on Wireless Sensor Networks Jan Madsen 155                          rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 156      "  ' +(        Sensor subsystem  Multiple types of sensors may be used:  Environmental: pressure, gas composition, humidity, light…  Motion or force: accelerometers, rotation, microphone, piezoresistive strain, position…  Electromagnetic: magnetometers, antenna, cameras…  Chemical/biochemical: Biochips  Digital or analog output  MEMS enabling size, cost and power miniaturization; nano coming  Components:  Transducer  Analog signal conditioning circuits  Analog to digital conversion  Digital signal processing Graduate Course on Wireless Sensor Networks Jan Madsen 157 Sensor subsystem  MEMS 3d acceleromter  Ability to simultaneously detect acceleration in three axial directions (X, Y and Z) with a single chip (acceleration rate 3G)  Applications  Motion sensors (electronic pets, robots and game controllers)  Image control in game machines and other devices with portable terminals with inclining image functions  Navigation for portable terminals  Inclination, vibration and seismic monitoring Graduate Course on Wireless Sensor Networks Jan Madsen 158      "  ' +)        Sensor subsystem  Biochips Graduate Course on Wireless Sensor Networks Jan Madsen 159                       rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 164      "  ' +        Processing subsystem  Many flavors of MCU  From embedded x86 processors 16 and 32bit processors all the way down to tiny 4bit processors  Some of the popular 8bit families  AVR, 8051, Z80, 6502, PIC, Motorola HC11  16bit families  Hitachi, Dragon  Many embedded Java controllers are also emerging Graduate Course on Wireless Sensor Networks Jan Madsen 166 Base Case: The Mica Mote (The most popular sensing platform today) 51PIN I/O Connector Programming Digital I/O Analog I/O Lines DS2401 AVR 128, 8bit MCU Unique ID Coprocessor Transmission Hardware Power Control Accelerators External Flash Radio Transceiver (CC1000 or CC2420) Power Regulation MAX1678(3V) Graduate Course on Wireless Sensor Networks Jan Madsen 167      "  ' +'        Processing Subsystem: Memory Considerations: Speed, capacity, price, power consumption, memory protection  SRAM: typical 0.5KB64MB  Typical power consumption  retained: 100ua; read/write: 10ma if separate chip  retained: 2ua100ua, read/write:5ma if in core  DRAM: high power consumption in retained mode  EEPROM:4KB512KB, often used as program store  Flash: 256KB1GB or beyond  Typical power consumption  retained: negligible; read/write: 7/20ma  erase operation is expensive  Large flashes are outside of core Graduate Course on Wireless Sensor Networks Jan Madsen 169 Processing Subsystem Clocks Hardware Timers Dividers Peripheral interfaces (for sensors, actuators, I/O, power) (analog and digital) (multiple busses with bridges between them)  SPI: Serial Peripheral Interface  I2C  UART: Serial communication  USB  PCI Graduate Course on Wireless Sensor Networks Jan Madsen 170      "  ' ++                                 rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 171 Communication Subsystem Considerations:  speed, range, power consumption, startup time  energy efficiency: joules/bit/m  signal propagation and interference characteristics  difference between receive power versus transmit power  not all devices need a receiver  choice of power level  antenna design  matching impedance Graduate Course on Wireless Sensor Networks Jan Madsen 172      "  ' +,        Communication Subsystem Mote Idle Startup Bluetooth Energy current per bit time IEEE 802.11 Tx Energy per Idle Startup Technology Data Rate Current bit Current time Mote 76.8 Kbps 10 mA 430 nJ/bit 7 mA Low Bluetooth 1 Mbps 45 mA 149 nJ/bit 22 mA Medium 802.11 11 Mbps 300 mA 90 nJ/bit 160 mA High Graduate Course on Wireless Sensor Networks Jan Madsen 174 Empirical Observations  Early studies all assumed a simple perfectconnectivitywithinrange model for simulations and analysis.  A number of empirical studies suggest this can be very misleading ( Ganesan ‘02; Zhao and Govindan ‘03; Woo, Tong and Culler ‘03).  A better characterization is that links fall into three regions: connected, transitional and unconnected. The transitional region will contain a large number of unreliable links. Graduate Course on Wireless Sensor Networks Jan Madsen 175      "  ' +        Link Regions          Graduate Course on Wireless Sensor Networks Jan Madsen 176 Received Signal Strength          Graduate Course on Wireless Sensor Networks Jan Madsen 177      "  ' ,                                        Graduate Course on Wireless Sensor Networks Jan Madsen 178 Where does the Power Go Peripherals Processing ASICs Display Programmable Disk µ Ps DSPs (apps, protocols etc.) Memory DCDC Converter RF Radio Transceiver Modem Communication Power Supply Graduate Course on Wireless Sensor Networks Jan Madsen 179      "  ' , Battery        DCDC Converter Inefficiency Current drawn from the battery Current delivered to the node Graduate Course on Wireless Sensor Networks Jan Madsen 180 Battery Capacity from Powers95  Current in “C” rating: load current normalized to battery’s capacity  e.g. a discharge current of 1C for a capacity of 500 mAhrs is 500 mA Graduate Course on Wireless Sensor Networks Jan Madsen 181      "  ' ,        Microprocessor Power Consumption CMOS Circuits (Used in most microprocessors) Static Component Dynamic Component Bias and leakage currents Digital circuit switching inside O(1mW) the processor 2 P= I V +I V +I V +αCV f sc standby dd leakage dd dd l dd clk Dynamic Static Graduate Course on Wireless Sensor Networks Jan Madsen 182                                rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 185      "  ' ,(        Power Management Subsystem  Voltage regulator  typical ranges: 1.8V, 3.3V, 5V  multiple voltages for various subsystem/power levels  Gauges for voltage or current  battery monitor (allows software to adapt computation)  Control of subsystems wakeup/sleep  latency is key in driving down the duty cycle  Control of platform clock rate, processor voltage Graduate Course on Wireless Sensor Networks Jan Madsen 186 Why energy harvesting  Cannot use wires  “wireless device  “practical” issues (interference, robustness, simplicity)  economical issues  Cannot use batteries  environmental issues  economical issues (disposable)  size/weight issues  no access to change/recharge Graduate Course on Wireless Sensor Networks Jan Madsen 188      "  ' ,)        Energy sources  Light  Vibration  Liquid or gas flow  Chemical reactions  Temperature  EM fields  From transceiver  ….. Graduate Course on Wireless Sensor Networks Jan Madsen 189 Commercially available energy harvesting  Harvesting devices from EnOcean Graduate Course on Wireless Sensor Networks Jan Madsen 190      "  ' ,        Vibes: Vibration energy scavenging Graduate Course on Wireless Sensor Networks Jan Madsen 191 Vibes: Vibration energy scavenging  Prototype demonstrated with 40 nW power for 0.5 g 200 Hz Graduate Course on Wireless Sensor Networks Jan Madsen 192      "  ' ,'        Energy harvesting  MEMS Graduate Course on Wireless Sensor Networks Jan Madsen 193                                 Graduate Course on Wireless Sensor Networks Jan Madsen 194      "  ' ,+        Popular Nodes Overview Graduate Course on Wireless Sensor Networks Jan Madsen 195 MICA  Current size around 3.25.7cm  Compressed variant with a size of a 2.5cm coin only 0.5cm thick  Battery lifetime up to several years Graduate Course on Wireless Sensor Networks Jan Madsen 196      "  ' ,,        MICA architecture block diagram 51PIN I/O Connector Programming Digital I/O Analog I/O Lines DS2401 AVR 128, 8bit MCU Unique ID Coprocessor Transmission Hardware Power Control Accelerators External Flash Radio Transceiver (CC1000 or CC2420) Power Regulation MAX1678(3V) Graduate Course on Wireless Sensor Networks Jan Madsen 197 MICA power consumption Graduate Course on Wireless Sensor Networks Jan Madsen 198      "  ' ,        Hogthrob platform  AVR Core (8bit, 8 MHz)  To ease startup  To be used as timer module (counter of limited size, cannot sleep for hours) and AD converter  FPGA (Xilinx Spartan3, 90nm)  400.000 gates  Codesign Hardware/Software  Hardware accelerators (radio, sensors)  Different MCUs  Clockbased (open core) vs. Asynchronous        Graduate Course on Wireless Sensor Networks Jan Madsen 201 Hogthrob platform  Addon radio board  2,4 GHz radio (Nordic VLSI)  transmit quickly to avoid interferences  Addon sensor board  motion detector  possibly microphones        Graduate Course on Wireless Sensor Networks Jan Madsen 202      "  '                    Hogthrob platform                                                                                                                                                                     Graduate Course on Wireless Sensor Networks Jan Madsen 203 Hogthrob platform   1 /"                                                  Tested in lab             Range 80m                                               Graduate Course on Wireless Sensor Networks Jan Madsen 204      "  '                       Hogthrob platform   1 /"                                                                                                                                            Graduate Course on Wireless Sensor Networks Jan Madsen 205 Hogthrob platform " 12   1 /"                                                                                                                                 Graduate Course on Wireless Sensor Networks Jan Madsen 206      "  '                        Nimbus Processor Core  AVR instruction set compatible  Simulated using 0.25 um technology Power results Benchmark ATMega128l Nimbus nop 47.5 mW 2.26 mW idle 17.0 uW 1.00 uW powersave 38.6 uW 1.22 uW powerdown 39.0 uW 0.59 uW add 30.1 mW 1.38 mW addmem 31.9 mW 1.90 mW hamming 32.3 mW 1.76 mW Graduate Course on Wireless Sensor Networks Jan Madsen 207                        rtos sensor cpu radio battery Graduate Course on Wireless Sensor Networks Jan Madsen 208      "  ' (        Operating system  MICA nodes use the TinyOS operating system  TinyOS is  Event based  Multithreaded  Nonpreemptive (preemption from lower layers allowed)  Component based  Most components are implemented in software, this allows for  Power saving – Processing is distributed over time to yield a very uniform power consumption without spikes Graduate Course on Wireless Sensor Networks Jan Madsen 209 TinyOS objectives  Diversity in design and usage Components  Lowpower consumption Eventsbased execution  Robustness Nonconcurrent programmation Graduate Course on Wireless Sensor Networks Jan Madsen 210      "  ' )        TinyOS Components  Internal storage: ”frame”, fixed size.  Set of tasks  Called commands  Commands handlers  Signaled events  Event handlers Graduate Course on Wireless Sensor Networks Jan Madsen 211 TinyOS Components  Component Graph example Graduate Course on Wireless Sensor Networks Jan Madsen 212      "  '         Why an eventbased approach  A stackbased threaded approach would require:  Stack space reserved for each execution context  Time costly execution context switches  An eventbased approach provides:  Memory gain  Robustness for long period runs  Hazardous behavior not allowed  Energy efficiency  Unused CPU cycles spent in sleep mode Graduate Course on Wireless Sensor Networks Jan Madsen 213 Design specification Design challenge related to TinyOS  Component based architecture  App’s build with OS from system components  Dedicated language: nesC  Task and Event based concurrency  Tasks don’t preempt tasks  Events preempt tasks  Events are ties to Interrupts  Split Phased operations  Commands request to execute and returns  Events completes Graduate Course on Wireless Sensor Networks Jan Madsen 214      "  ' '        SOS: Sensor network OS  Operating system for moteclass sensor nodes  consists of dynamicallyloaded modules  a common kernel, which implements  messaging,  dynamic memory  module loading and unloading  Achieves dynamic and generalpurpose OS semantics without much energy or performance sacrifices.  Provides significant energy saving over TinyOS and more expressivity than Mate Bombilla. Graduate Course on Wireless Sensor Networks Jan Madsen 215 SOS: Dynamic code  SOS both expects and support multiple modules executing and interacting on top of the SOS kernel at the same time.  SOS module updates can not replace the kernel and not force a node to reboot after updates.  SOS includes a publishsubscribe scheme that is similar to MOAP for distributing modules within a deployed sensor network. Graduate Course on Wireless Sensor Networks Jan Madsen 216      "  ' +        AmbientRT  AmbientRT is a RealTime Operating System for embedded devices which has very powerful features like, realtime scheduling, dynamic memory allocation, online reconfigure ability, and support for a data driven architecture based on very limited memory, processing, and energy sources.  Brings WSN closer to reality  Developed for limited resources  Relieve the burden of the developer  Efficiently use the resources of the node  Concepts used and tradeoffs involved in the system  Current hardware available for sensor networks, the real time concept is feasible Graduate Course on Wireless Sensor Networks Jan Madsen 217 AmbientRT: unique aspects  AmbientRT uses realtime preemptive scheduling and dynamically defines priorities based on the timing properties instead of assigning to tasks.  Other systems use cooperative scheduling, whose realtime behavior can not be guaranteed. Graduate Course on Wireless Sensor Networks Jan Madsen 218      "  ' ,        AmbientRT: Real time scheduling  EDF + DI = EDFI  EDFI uses deadline inheritance while Priority Ceiling protocol use fixed priorities for inheritance. It allows a considerable simplification of blocking computation during feasibility analysis.  EDFI uses static deadline inheritance. It is better than dynamic deadline modification in computation cost. Graduate Course on Wireless Sensor Networks Jan Madsen 219 Comparison Features TinyOS SOS AmbientRT Soft RT Soft RT Hard RT Real Time (Poor latency) (Better latency) (Much better latency) Reconfiguration Static Dynamic Dynamic Memory Static Dynamic Dynamic Allocation Preemption No No Yes Resource Not Required Not Required Scheduler Synchronization Module Level Compile Time Execution Not Mentioned Error Handling Time Graduate Course on Wireless Sensor Networks Jan Madsen 220      "  '                                        Graduate Course on Wireless Sensor Networks Jan Madsen 221 WSN Platform layers os os sensor radio sensor radio cpu cpu Mem Mem batteri batteri os sensor radio cpu Mem batteri Graduate Course on Wireless Sensor Networks Jan Madsen 222      "  ' software software software        Sensor node design space Hardware: Operating System:  Architecture: DPM Appl Custom design versus COTS architecture RTOS (µ C/OSII, embedded linux) or Power Management: Single processor, processor+accelerators, OS/middleware (TinyOS, Impala), multiprocessors, SoC HW  Scheduling algorithm (EDF, RM, DVS)  Node level : Communic  Componen attion chara Prot cter ocol istics: s (CPU, sensors, radio): predictive techniques, duty cycling. Power and delay characteristics. Network level : A  pplication: Link layer MAC protocol: OS even energy consumption distribution. Comm CSMA, TDMA, SMAC.  C Nomm etwork lay unicat e ion/ r R pro ouctin esg sipr ng oto tradeof col: f. static vs dynamic (innetwork processing, aggregation)  Tuning tsing he rle or equirm em ulti ent hop s of the application. App App (measurement rate, performance) OS OS OS2 Very large design spac sen sens so oe r r and i CP CP t is d U U ifficu rad CP lt iU2 to o forese rad e iw o hat consequences decision in the different directions affect each other. Network on Chip Systemlevel sensor network model Graduate Course on Wireless Sensor Networks Jan Madsen 223                           Graduate Course on Wireless Sensor Networks Jan Madsen 224      "  '         Layers of Abstraction Application Sensor Network Query Command Localization C. R. Others Service Platform Service Service Service Service (SNSP) Rialto Application class, E2E Latency, Loss Rate Sensor Network Randomized SERAN Others Adhoc Protocol PicoRadio Platform (SNAPP) Software generation Abstract performance Sensor Network Implementation Mica Telos PicoNode Others Platform (SNIP) Courtesy Alvise Bonivento Graduate Course on Wireless Sensor Networks Jan Madsen 225 Rialto Capture these specifications Allow user to describe the and produce a set of network in terms of logical constraints on LATENCY, components queries and ERROR RATES, SENSING, services (as in SNSP) COMPUTATION Rialto Application Domain Network Design Domain Bridging Application with Implementation Courtesy Alvise Bonivento Graduate Course on Wireless Sensor Networks Jan Madsen 226      "  '         Protocol Platform Modify and combine different Routing and MAC Refine application constraints strategies Derive mathematical model Constrained Synthesize Optimization and parametrized parameters Problem MAC+ Routing protocol Implement Abstract hardware performance Courtesy Alvise Bonivento Graduate Course on Wireless Sensor Networks Jan Madsen 227 Graduate Course on Wireless Sensor Networks Jan Madsen 228      "  ' (        Graduate Course on Wireless Sensor Networks Jan Madsen 229                  Graduate Course on Wireless Sensor Networks Jan Madsen 230      "  ' )        Major System Challenges  Large numbers of elements  Limited physical access  Extreme environmental conditions  = demand a fundamental reexamination of familiar layers of abstraction, hardware, algorithms  Suggestion: these are a radically different kind of computing system Graduate Course on Wireless Sensor Networks Jan Madsen 231 Scale  of sensors: 10’s to millions  Size of sensors (cubic feet to millimeters)  Spatial and temporal sampling rates (miles to mm’s and days to ms)  Capability (sensors, power, compute, communicate)  Compose and evolve as a system at scale  Question: what computing systems do we have that span these ranges Are they one kind Graduate Course on Wireless Sensor Networks Jan Madsen 232      "  '         Limited Access  Unwired, unpowered, limited networking (cost)  Physically remote or harsh enviroments  Limited human intervention support/administration  Resource limited  What are characteristics of our longest running, reliable systems, and techniques Graduate Course on Wireless Sensor Networks Jan Madsen 233 Extreme Dynamics  Activity in the physical world happens in bursts  Animals are built for this (adrenaline, fearflight, hunt, taste, smell, etc.)  Static network things passing, evolving  Mobile network things encountered  Dynamic range of sensory input is orders of magnitude  Systems must have passive vigilance, efficient triggering, and rapid transformation to high levels of concurrency and effectiveness.  Not quite “lazy computing”, or something analogous Graduate Course on Wireless Sensor Networks Jan Madsen 234      "  ' '        Breadth  Variable design structure – static, dynamic, regular and irregular  Single sensor type/mode, multiple, single application and multipleapplication  Static or mobile – fast and slow change  Autonomy and limited access  Degree of human involvement in both decision making/control as well as maintenance of system Graduate Course on Wireless Sensor Networks Jan Madsen 235 State of the Art  … rambling discussion of some current research activities…  Small devices increasing in environmental awareness and networking capability  Evolving radio, silicon technology enabling sensor networks  Maturing software environments Graduate Course on Wireless Sensor Networks Jan Madsen 236      "  ' +        State of the Art (cont.)  Outline of several specific challenges (not comprehensive)  Sensing and actuation – control loops and variable delays  Localization as a key challenge and foundation for coupling with the physical world  Self configuration – and reconfiguration Graduate Course on Wireless Sensor Networks Jan Madsen 237 Some “throw ins”  Data centric architecture and “directed diffusion” Tiered (hierarchical) architectures  Different capabilities, heterogeneity  Frontier for almost any CS subdiscipline is in this area Graduate Course on Wireless Sensor Networks Jan Madsen 238      "  ' ,        Trend in WSN research  From theoretical …  … to practical                   Graduate Course on Wireless Sensor Networks Jan Madsen 239 Future sensor networks Graduate Course on Wireless Sensor Networks Jan Madsen 240      "  '         Paradigme shift in computing  From  Interactive computing  People in the loop  To  Proactive computing Graduate Course on Wireless Sensor Networks Jan Madsen 241 PROactive computing  Get Physical  Pervasive contact with the physical world  Get Real  Running faster than humanspeed  Get Out  People out of the loop David Tennenhous, Intel Research Graduate Course on Wireless Sensor Networks Jan Madsen 242      "  '         Traditional sensor network sensor net sensor net sensor net gateway database internettet database Graduate Course on Wireless Sensor Networks Jan Madsen 243 Healthcare: Smart home Sensors Action Monitoring Graduate Course on Wireless Sensor Networks Jan Madsen 244      "  ' Only one ”user”        Small Technology, Broad Agenda, Unique Confluence  Social factors  security, privacy, information sharing  Applications  long lived, selfmaintaining, dense instrumentation of previously unobservable phenomena  interacting with a computational environment  Programming the Ensemble  describe global behavior, synthesis local rules that have correct, predictable global behavior  Distributed services  localization, time synchronization, resilient aggregation  Networking  selforganizing multihop, resilient, energy efficient routing  despite limited storage and tremendous noise  Operating system  extensive resourceconstrained concurrency, modularity  framework for defining boundaries  Architecture  rich interfaces and simple primitives allowing crosslayer optimization  lowpower processor, ADC, radio, communication, encryption Graduate Course on Wireless Sensor Networks Jan Madsen 245 The Hogthrob project  Developing a sensor network infrastructure for sow monitoring  Sensor nodes on a chip  Sensor network model  Monitoring application Graduate Course on Wireless Sensor Networks Jan Madsen 246      "  '         References: Slides Some slides in this presentation are based, in part or full, on slides from the following tutorial and course presentations.  An Introduction to Wireless Sensor Networks, Bhaskar Krishnamachari, USC Viterbi School of Engineering. Tutorial Presented at the Second International Conference on Intelligent Sensing and Information Processing (ICISIP), Chennai, India, January 2005.  Building Sensor Networks with TinyOS, David Culler, Phil Levis, Rob Szewczyk, Joe Polastre, University of California, Berkeley and Intel Research Berkeley. Mobisys Tutorial, San Francisco, 2003.  Introduction to Wireless Sensor Networks, Anish Arora, Ohio State University. Course CSE 788, Spring 2005.  Networked Embedded Systems Sensor Networks, Andreas Savvides , Yale University. Course EENG 460a  Directed diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks, Sandeep Gupta, Arizona State University. Course CSE 534 Advanced Computer Networks Graduate Course on Wireless Sensor Networks Jan Madsen 247 References: Books  “Networking Wireless Sensors” by Bhaskar Krishnamachari, Cambridge University Press, 2005  “Principles of Embedded Networked Systems Design” by Gregory Pottie and William Kaiser, Cambridge University Press, 2005  A Wireless Sensor Networks Bibliograhy  http://ceng.usc.edu/anrg/SensorNetBib.html Graduate Course on Wireless Sensor Networks Jan Madsen 248      "  ' (        References MAC Protocols  EnergyEfficient MAC Protocol for Wireless Sensor Network (SMAC) Wie Ye, John Heidemann, Deborah Estrin (University of california, Los Angeles, California, USA)  Sensor Network Media Access Design (BMAC) Joseph Polastre (University of California, Berkeley, California, USA)  An Adaptive EnergyEfficient MAC Protocol for Wireless Sensor Networks (TMAC), Tija van Dam, Koen Langendoen (Delft University of Technology, Netherlands)  Low Power MAC Protocols for Infrastructure Wireless Sensor Networks (WiseMAC), A. ElHoiydi, J.D. Decotignie, J. Hernandez (CSEM, Switzerland) Graduate Course on Wireless Sensor Networks Jan Madsen 249 References Localization  K. K. Chintalapudi, A. Dhariwal, R. Govindan and G. Sukhatme. Ad hoc localization using ranging and sectoring. In Proceedings of IEEE INFOCOM, 2004.  A. Howard, M.J. Mataric and G. Sukhatme. Relaxation on a mesh: a formalism for generalized localization. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), Wailea, Hawaii, October 2001.  Andreas Savvides, ChihChieh Han, and Mani B. Srivastava. Dynamic finegrained localization in adhoc networks of sensors. In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2001), Rome, Italy, July 2001.  D. Niculescu and B. Nath. Ad hoc positioning system (APS). In Proceedings of IEEE GLOBECOM, 2001. Graduate Course on Wireless Sensor Networks Jan Madsen 250      "  ' )        References Routing Protocols  Directed Diffusion for Wireless Sensor Networking, C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann and F. Silva. IEEE/ACM Transaction on Networking, vol.11, no.1, February 2003.  EnergyEfficient Communication Protocol for Wireless Microsensor Networks, W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan. Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000.  Rumor Routing Algorithm for Sensor Networks, D. Braginsky and D. Estrin. Proceedings of WSNA'02, Atlanta, September 2002.  Adaptive Protocols for Information Dissemination in Wireless Sensor Networks, W.R. Heinzelman, A. Chandrakasan and H. Balakrishnan. Proceedings of the 5th ACM/IEEE MOBICOM Conference, Seattle, August 1999. Graduate Course on Wireless Sensor Networks Jan Madsen 251 References Operating Systems  NetworkCentric Approach to Embedded Software for Tiny Devices, D. Culler, J. Hill, P. Buonadonna, R. Szewczyk and A. Woo. Technical report from Intel Research Berkeley, January 2001.  The nesC Language: A Holistic Approach to Networked Embedded Systems, D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer and D. Culler. In Proceedings of Programming Language Design and Implementation (PLDI), San Diego, June 2003.  A dynamic operating system for sensor nodes. Han, C., Kumar, R., Shea, R., Kohler, E., and Srivastava, M. In Proceedings of the 3rd international Conference on Mobile Systems, Applications, and Services (MobiSys '05), Seattle, Washington, June 2005.  AmbientRT real time system doftware support for data centric sensor networks. T.J. Hofmeijer, S.O. Dulman, P.G. Jansen and P.J.M. Havinga, In Proceedings of the 2nd Int. Conf. on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), Melbourne, Australia, 2004. Graduate Course on Wireless Sensor Networks Jan Madsen 252      "  '         References Design Methods  Amol Bakshi and Viktor K. Prasanna, Algorithm Design and Synthesis for Wireless Sensor Networks, 3rd International Conference on Parallel Processing (ICPP), August 2004.  A. Bakshi, J. Ou, and V. K. Prasanna. Towards automatic synthesis of a class of applicationspecific sensor networks. In International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), Oct. 2002.  A.Bonivento, L.P. Carloni, A. SangiovanniVincentelli, Platform based design for Wireless Sensor Networks, to appear in Mobile Networks and Applications (MONET), Springer  Péter Völgyesi, Ákos Lédeczi: ComponentBased Development of Networked Embedded Applications. In proceedings of the 28th EUROMICRO Conference 2002, pages 6873. 46 September 2002, Dortmund, Germany Graduate Course on Wireless Sensor Networks Jan Madsen 253 Appendices Graduate Course on Wireless Sensor Networks Jan Madsen 254      "  ' '        Swarm Intelligence Overview  Social insect colony  No central control  Stimergy  Selforganization  Positive feedback (amplification)  Negative feedback  Fluctuations  Multiple interactions between agents and reuse of information Graduate Course on Wireless Sensor Networks Jan Madsen 255 Natural Ant Colony Behavior  Selforganization  Pheromone trails Figure 2. Diagram of experimental setup used to demonstrate selforganization in ants. Graduate Course on Wireless Sensor Networks Jan Madsen 256      "  ' +        Ants in Action  Initially, no pheromone on edges Graduate Course on Wireless Sensor Networks Jan Madsen 257 Ants in Action  Obstacle causes split 1  No guiding factor, probable equal split 2  Shorter path causes faster travel Graduate Course on Wireless Sensor Networks Jan Madsen 258      "  ' ,        Ants in Action  Pheromone trails exist; 1 influence decision 2 Graduate Course on Wireless Sensor Networks Jan Madsen 259 Ants in Action  Pheromone exists on both trails, but amount 2 differs  Edge choice is still random, but is weighted towards ECB 1 Graduate Course on Wireless Sensor Networks Jan Madsen 260      "  '         Ants in Action  A route begins to emerge Graduate Course on Wireless Sensor Networks Jan Madsen 261 Ants in Action  A path is established  Selforganization through autocatalytic behavior  Negative feedback through evaporation Graduate Course on Wireless Sensor Networks Jan Madsen 262      "  ' 
Website URL
Comment