© Bhaskar Krishnamachari 2005, All Rights Reserved 1An Introduction toWireless Sensor NetworksBhaskar KrishnamachariAutonomous Networks Research GroupDepartment of Electrical EngineeringUSC Viterbi School of [email protected]://ceng.usc.edu/~bkrishna/Tutorial Presented at the Second International Conference on Intelligent Sensing and Information Processing (ICISIP), Chennai, India,January 2005.© Bhaskar Krishnamachari 2005 2Overview© Bhaskar Krishnamachari 2005 3Wireless Sensor Networks (WSN)• The “many - tiny” principle: wireless networks ofthousands of inexpensive miniature devices capable ofcomputation, communication and sensing• Their use throughout society “could well dwarf previousmilestones in the information revolution”: U.S. NationalResearch Council Report, 2001.Berkeley Mote (MICAz MPR 2400 Series)© Bhaskar Krishnamachari 2005 4Timeline• 1970’s: Wired sensors connected to central location• 1980’s: Distributed wired sensor networks• 1993: LWIM project at UCLA• 1999-2003: DARPA SensIT project: UC Berkeley, USC, Cornell etc.• 2001: Intel Research Lab at Berkeley focused on WSN• 2002: NSF Center for Embedded Networked Sensing• 2001-2002: Emergence of sensor networks industry; startupcompanies including Sensoria, Crossbow, Ember Corp, SensiCastplus established ones: Intel, Bosch, Motorola, General Electric,Samsung.• 2003-2004: IEEE 802.15.4 standard, Zigbee Alliance.© Bhaskar Krishnamachari 2005 5Wireless Sensor Networks (WSN)• Provide a bridge between the real physical and virtualworlds• Allow the ability to observe the previously unobservableat a fine resolution over large spatio-temporal scales• Have a wide range of potential applications to industry,science, transportation, civil infrastructure, and security.© Bhaskar Krishnamachari 2005 6Some Sample Applications• Habitat and Ecosystem Monitoring• Seismic Monitoring• Civil Structural Health Monitoring• Monitoring Groundwater Contamination• Rapid Emergency Response• Industrial Process Monitoring• Perimeter Security and Surveillance• Automated Building Climate Control© Bhaskar Krishnamachari 2005 7Basic Components of aWSN Node© Bhaskar Krishnamachari 2005 8Challenges• Energy Efficiency• Responsiveness• Robustness• Self-Configuration and Adaptation© Bhaskar Krishnamachari 2005 9Challenges (contd.)• Scalability• Heterogeneity• Systematic Design• Privacy and Security© Bhaskar Krishnamachari 2005 10Outline for the Rest of the Tutorial• Deployment• Localization• Time Synchronization• Wireless Link Characteristics• Medium Access• Sleep Based Topology Control• Routing• Data Centric Networking• Transport© Bhaskar Krishnamachari 2005 11Deployment© Bhaskar Krishnamachari 2005 12Deployment Issues• Structured versus Randomized Deployment• Overdeployed versus Incremental Deployment• Connectivity and Coverage Metrics of Interest© Bhaskar Krishnamachari 2005 13Network Topologies© Bhaskar Krishnamachari 2005 14Random Graph Models• For some applications, WSN nodes could be scatteredrandomly (e.g. from an airplane)• Random Graph Theory is useful in analyzing suchdeployments• The most common random graph model is G(n,R):deploy n nodes randomly with a uniform distribution in aunit area, placing an edge between any two that arewithin Euclidean range R.© Bhaskar Krishnamachari 2005 15Geometric Random Graph G(n,R)sparsedense© Bhaskar Krishnamachari 2005 16• All monotone graph properties have an asymptoticcritical range R beyond which they are guaranteed withhigh 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 kneighbors also ensures k-connectivity w.h.p. (Penrose‘99)Some Key Results© Bhaskar Krishnamachari 2005 17Connectivity in G(n,R)© Bhaskar Krishnamachari 2005 18• Provides a degree of flexibility in configuring the networkconnectivity after deployment.• Must carefully balance several factors, includingconnectivity, energy usage, and interference.• The CBTC (Li et al. ‘01) provides a distributed rule forglobal connectivity: increase power until there is aneighbor within range in every sector of angle α≤5π/6Power Control© Bhaskar Krishnamachari 2005 19Coverage 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 maximalbreach distance, defined as the closest any evasive target mustget to a sensor in the field (Meguerdichian et al. ‘99)– K-Coverage: ensure that all parts of the field are within sensingrange of K sensors (e.g. Wang et al. ‘03)© Bhaskar Krishnamachari 2005 20Key Results on K-Coverage• A field is K-covered if and only if all intersection pointsbetween sensing circles are at or inside the boundary ofK+1 sensing circles. (Wang et al. ‘03)• If a region is K-covered by n sensors, they also form a K-connected graph if their communication range is at leasttwice the communication range. (Wang et al. ‘03)A 2-covered region© Bhaskar Krishnamachari 2005 21Localization© Bhaskar Krishnamachari 2005 22Localization Issues• Location information necessary/useful for many functions,including measurement stamps, coherent signalprocessing, cluster formation, efficient querying androuting.• Key Questions:– What to localize?– When to localize?– How well to localize?– How to localize?© Bhaskar Krishnamachari 2005 23Coarse Grained Node LocalizationSeveral techniques provide approximate solutions for nodelocalization based on the use of minimal information:• Proximity• Centroids• Geometric Constraints•APIT• Identifying Codes© Bhaskar Krishnamachari 2005 24Geometric ConstraintsReference nodeUnknown nodeConstrainedlocation regionDiscAnnulusSectorQuadrant(Doherty, Pister and Ghaoui ‘01)© Bhaskar Krishnamachari 2005 25Approximate Point in Triangle (APIT)(He, Huang, et al. ‘03)© Bhaskar Krishnamachari 2005