1 Computer Communications - CSCI 551 Copyright © William C. ChengCS551Routing inSensor Networks[Intanagonwiwat00a]Bill Chenghttp://merlot.usc.edu/cs551-f12few, large, expensive sensors arefar from phenomenaRemote approach2Remote Sensing Computer Communications - CSCI 551 Copyright © William C. Chengthey use complex algorithms tofactor out noiseSNR decreases rapidly withdistanceProblem:e.g. satellite-based sensingnoise limits performance(resolution)some, cheap?, dumb sensors areclose to phenomenaCentralized approach 3Sensor Arrays Computer Communications - CSCI 551 Copyright © William C. Chengbandwidth requirements highProblem:collected data is sent to processat smart, expensive central node(or nodes) can’t use wirelessdifficult to deployLARGE DATAmany small, smart, cheap sensorsclose to phenomenaDistributed approach4Future Wireless Sensor Networks Computer Communications - CSCI 551 Copyright © William C. Chengnodes will have processingcapabilitydeployment is trivialWhy wireless?dense sensing small eventalso enables large numbers ofnodessmall eventfor ease of deployment, must also bebattery operatedChallenges5Future Wireless Sensor Networks Computer Communications - CSCI 551 Copyright © William C. Chengenergy management now becomesan important issueenergy cost of communicationoutweighs other costs in the systemenergy required to transmit 1 bit10m is same as energy for 1000processor operationsprocess data within the networkHow do we overcome this?data must be self-describinguser names data, not nodesmall event6 Computer Communications - CSCI 551 Copyright © William C. Cheng Directed Diffusionspecified by attributes, not IP addressUsers express interest in data (becoming sink)by default: flooded through networkSink sends out interestsfirst, send exploratory (low rate) dataSources reply to interests with datasets up reinforced pathSink reinforces a pathcould use attributes for help (geography)could use cached old routes flooded on return pathsnon-exploratory (high rate) data only follows reinforcedpaths7 Computer Communications - CSCI 551 Copyright © William C. Cheng Interest Propagation The desired data rate will beachieved by reinforcementInitial interest specifies low datarate as exploratoryFlood the interestAfter receiving an interest, thenode creates states and re-sendsto a subset of its neighborsDirect interest or limit scopeusing GPS infoDirect interest using routehistory8 Computer Communications - CSCI 551 Copyright © William C. Cheng Exploratory Data Propagation andGradient EstablishmentSensor’s first data is exploratory(low-rate data)map attributes to next hop ateach node in networkSent throughout network,establishing gradientsnodes have multiple gradients9 Computer Communications - CSCI 551 Copyright © William C. Cheng Reinforcementdefault: lowest latency Sink reinforces some path to gethigh rate or non-exploratory dataEach hop propagatesreinforcement back to sourcesWhich link to reinforce?alternatives: maximumremaining energy, orgreedy tree 10 Computer Communications - CSCI 551 Copyright © William C. Cheng Negative Reinforcement(paths that send the same info)Should detect and pruneunnecessary pathsimplicit negative reinforcement(just let gradient time out)Negative reinforcementexplicit negative reinforcement11 Computer Communications - CSCI 551 Copyright © William C. Cheng Naming and attributesneeds resource discoveryhumans use search enginesIP has node address and ports and DNS and URLsembedded systems use something like Jini sinks subscribe to sensor EQ acoustic; target IS lions;lat GT 100; lat LT 101; long GT 43; long LT 44 Directed diffusion uses attribute-based namingsensors publish sensor IS acoustic; target EQ *;lat IS 100.5; long IS 43.0512 Computer Communications - CSCI 551 Copyright © William C. Cheng Filtersduplicate suppressionSupport app-specific, in-network processing aggregationcollaborative signal processingcaching, etc.assume filters are pre-deployed in netMechanism:match on attributesfilter can take any action (send new msgs, suppressmessages, etc.)F: watch for sensor data typelion and aggregate itFFFFFFFFFFsourcesinkadditional sourcefilter suppressesduplicate data13 Computer Communications - CSCI 551 Copyright © William C. Cheng Differences from Traditional NetworkingNeighbor-to-neighbor communication (not end-to-end)no globally unique IDsLocalized algorithmsno explicit global information (routing tables)Data and queries are named independently from theirproducersIn-network processingApplication-specific net-wide attributes (like sensor type or latitude/longitude)app-specific data aggregation14 Computer Communications - CSCI 551 Copyright © William C. Cheng Energy Scalinghow?duplicate suppression(cannot do it in IP networks)Good performanceeven as number ofnodes growsDiffusion uses lessenergy thanomniscientmulticast (optimal)diffusion does in-network aggregation[Intanagonwiwat00a,figure 4a]15 Computer Communications - CSCI 551 Copyright © William C. Cheng In-Network ProcessingDuplicate suppression is critical to diffusion[Intanagonwiwat00afigure 6b]Shows the importance of app-specific in-network processing16 Computer Communications - CSCI 551 Copyright © William C. Cheng Critique100s of embedded, unattended, small devices Looking at sensor networksnot end-to-end coordinate communication between sensors and usersMulti-hop communicationuses in-network processing (ex. aggregation)Data-centric communicationuses application-specific routing (mixes routing layer andapplication)uses attribute-based names (rather than addresses)17 Computer Communications - CSCI 551 Copyright © William C. Cheng Discussionin-network processingReally, a radically new networking architecture ...motivated by a new technologyArticulates the rationale behind this architecture wellRouting scheme a bit too
View Full Document
Unlocking...