Wireless Sensor Networks

Wireless Sensor Networks

1. MATRUSRI ENGINEERING COLLEGE
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
SUBJECT NAME: WIRELESS SENSOR NETWORKS(PE 831 EC)
FACULTY NAME: Mrs. P.SRAVANI
MATRUSRI
ENGINEERING COLLEGE

2. WIRELESS SENSOR NETWORKS(PE 831 EC)
COURSE OBJECTIVES:
Determine network architecture, node discovery and localization,
deployment strategies, fault tolerant and network security.
Build foundation for WSN by presenting challenges of wireless networking
at various protocol layers.
Determine suitable protocols and radio hardware.
Evaluate the performance of sensor network and identify bottlenecks.
Evaluate concepts of security in sensor networks.
COURSE OUTCOMES:
To understand network architecture, node discovery and localization,
deployment strategies, fault tolerant and network security.
To understand foundation for WSN by presenting challenges of
wireless networking at various protocol layers
Study suitable protocols and radio hardware.
To understand the performance of sensor network and identify
bottlenecks.
To understand concepts of security in sensor networks.
MATRUSRI
ENGINEERING COLLEGE

3. INTRODUCTION:
Wireless sensor networks (WSNs) have been considered as one of the most
important technologies that are enabled by recent advances in –
Micro-electronic-mechanical-systems(MEMS)
Wireless Communication technologies.
UNIT-I: OVERVIEW OF WIRELESS SENSOR NETWORKS
MATRUSRI
ENGINEERING COLLEGE

4. OUTCOMES:
To determine the network architecture, node discovery and localization,
deployment strategies, fault tolerant and network security.
To understand the gist of Wireless Sensor Networks.
MATRUSRI
ENGINEERING COLLEGE

5. Module 1: Challenges for Wireless Sensor Networks
MATRUSRI
ENGINEERING COLLEGE

6. MATRUSRI
ENGINEERING COLLEGE

7. MATRUSRI
ENGINEERING COLLEGE

8. MATRUSRI
ENGINEERING COLLEGE

9. MATRUSRI
ENGINEERING COLLEGE

10. Module 2: Characteristicsrequirements-required mechanisms
MATRUSRI
ENGINEERING COLLEGE

11. MATRUSRI
ENGINEERING COLLEGE

12. MATRUSRI
ENGINEERING COLLEGE

13. MATRUSRI
ENGINEERING COLLEGE

14. MATRUSRI
ENGINEERING COLLEGE

15. Module 3: Difference between mobile ad-hoc and sensor
networks
MATRUSRI
ENGINEERING COLLEGE

16. MATRUSRI
ENGINEERING COLLEGE

17. Module 4: Applications of sensor networks
MATRUSRI
ENGINEERING COLLEGE
Applications 1

18. MATRUSRI
ENGINEERING COLLEGE
Applications 2

19. MATRUSRI
ENGINEERING COLLEGE
Applications 3

20. MATRUSRI
ENGINEERING COLLEGE
Applications 4

21. Module 5: Enabling Technologies for
Wireless Sensor Networks
MATRUSRI
ENGINEERING COLLEGE

22. MATRUSRI
ENGINEERING COLLEGE
Conclusion

23. MATRUSRI
ENGINEERING COLLEGE
UNIT-II: ARCHITECTURES
INTRODUCTION
AWirelessSensorNetworkisonekindofwirelessnetworkincludesa
largenumberofcirculating,self-directed,minute,lowpowereddevices
namedsensornodescalledmotes.Thesenetworkscertainlycoverahuge
numberofspatiallydistributed,little,battery-operated,embeddeddevices
thatarenetworkedtocaringlycollect,process,andtransferdatatothe
operators,andithascontrolledthecapabilitiesofcomputing&processing.
Nodesarethetinycomputers,whichworkjointlytoformthenetworks.
Thesensornodeisamulti-functional,energyefficientwirelessdevice.
Theapplicationsofmotesinindustrialarewidespread.Acollectionof
sensornodescollectsthedatafromthesurroundingstoachievespecific
applicationobjectives.Thecommunicationbetweenmotescanbedone
witheachotherusingtransceivers.Inawirelesssensornetwork,the
numberofmotescanbeintheorderofhundreds/eventhousands.In
contrastwithsensorn/ws,AdHocnetworkswillhavefewernodeswithout
anystructure.

24. MATRUSRI
ENGINEERING COLLEGE
OUTCOMES:
Build foundation for WSN by presenting challenges of
wireless networking at various protocol layers.
CONTENTS:
Single node architecture-hardware components
Energy consumption of sensor nodes
Operating system and execution environment
Network architecture-sensor network scenarios
Optimization goals and figure of merit
Gate-way concepts

25. MATRUSRI
ENGINEERING COLLEGE
Module 1: Single node architecture-hardware components

26. MATRUSRI
ENGINEERING COLLEGE
Module 2: Hardware Components
Power supply
Microcontrollers vsMicroprocessors, FPGAs and ASIC
Memory
Communication devices
Sensors & Actuators
-Passive omnidirectional sensors
-Passive narrow-beam sensors
-Active sensors
-Actuators

27. MATRUSRI
ENGINEERING COLLEGE
Transceiver (Front end)

28. MATRUSRI
ENGINEERING COLLEGE
Power supply of sensor nodes:
Storing energy: Batteries
-Traditional batteries
-Capacity
-capacity under load
-self discharge
-Efficient recharging
-Relaxation
-Unconventional energy Sources
-DC-DC
-Energy Scavenging
-Photovolatic,Temparature gradients,
Vibrations, Pressure variations, flow and air/liquid

29. MATRUSRI
ENGINEERING COLLEGE
MEMS device for converting vibrations to electrical energy
(Based on a variable Capacitor)

30. MATRUSRI
ENGINEERING COLLEGE
Module 3: Energy consumption of sensor nodes
Astheprevioussectionhasshown,energysupplyfora
sensornodeisatapremium:batterieshavesmallcapacity,and
rechargingbyenergyscavengingiscomplicatedandvolatile.Hence,
theenergyconsumptionofasensornodemustbetightlycontrolled.
Themainconsumersofenergyarethecontroller,theradiofrontends,
tosomedegreethememory,anddependingonthetypethesensors.
Oneimportantcontributiontoreducepowerconsumptionof
thesecomponentscomesfromchip-levelandlowertechnologies:
Designinglow-powerchipsisthebeststartingpointforanenergy-
efficientsensornode.Butthisisonlyonehalfofthepicture,asany
advantagesgainedbysuchdesignscaneasilybesquanderedwhen
thecomponentsareimproperlyoperated.

31. MATRUSRI
ENGINEERING COLLEGE
Energy consumption of sensor nodes:
(Energy savings and overhead of sleeping nodes)

32. MATRUSRI
ENGINEERING COLLEGE
Microcontroller energy consumption
Memory (Intel Strong ARM SA-1100)
Radio transceivers
Power consumption of sensor and actuators

33. MATRUSRI
ENGINEERING COLLEGE
Module 4:Operating systems and Execution Environments
1.Embeddedoperatingsystems:Thetraditionaltasksofanoperating
systemarecontrollingandprotectingtheaccesstoresources(including
supportforinput/output)andmanagingtheirallocationtodifferentusersas
wellasthesupportforconcurrentexecutionofseveralprocessesand
communicationbetweentheseprocesses.
2.Programming paradigms and
application programming
interfaces (concurrent
programming):
-Process-based concurrency
-Event-based programming
-Interfaces to the operating
systems

34. MATRUSRI
ENGINEERING COLLEGE
Event based programming model

35. MATRUSRI
ENGINEERING COLLEGE
Timer component using Interfaces

36. MATRUSRI
ENGINEERING COLLEGE
Module 5: NETWORK ARCHITECTURE -Sensor network scenarios
Types of Sources and sinks:
-Single hop versus Multi hop
Three types of sinks in a very simple single-hop sensor network

37. MATRUSRI
ENGINEERING COLLEGE
Multi-hop network

38. MATRUSRI
ENGINEERING COLLEGE
Multiple sources and/or multiple sinks

39. MATRUSRI
ENGINEERING COLLEGEThree types of mobility
Node mobility
Sink mobility
Event mobility
A mobile sinks moves through a mobile sensor network as a information
being retrieves on its behalf

40. MATRUSRI
ENGINEERING COLLEGE
Module 6: Optimization goals and figure of merit
1.Quality of service
-Event detection/reporting probability
-Event classification error
-Event detection delay
-Missing reports
-Approximation accuracy
-Tracking accuracy
2. Energy efficiency
-Energy/correctly received
-Energy/reported event
-Delay
-N/w Life time
3. Scalability
4. Robustness
Forallthesescenariosandapplicationtypes,differentformsofnetworking
solutionscanbefound.Thechallengingquestionishowtooptimizeanetwork,howto
comparethesesolutions,howtodecidewhichapproachbettersupportsagiven
application,andhowtoturnrelativelyimpreciseoptimizinggoalsintomeasurable
figuresofmerit?Whileageneralanswerappearsimpossibleconsideringthelarge
varietyofpossibleapplications,afewaspectsarefairlyevident.

41. MATRUSRI
ENGINEERING COLLEGE
Area of sensor nodes detecting an event-an elephant-that moves through
the network along with the event source

42. MATRUSRI
ENGINEERING COLLEGE
Module 7: Gateway Concepts
The need for gate ways
WSN to Internet Communication
Internet to WSN communication
WSN tunneling

43. MATRUSRI
ENGINEERING COLLEGE
1. Need for Gate ways
Forpracticaldeployment,asensornetworkonlyconcernedwithitselfis
insufficient.Thenetworkratherhastobeabletointeractwithotherinformationdevices,
forexample,auserequippedwithaPDAmovinginthecoverageareaofthenetworkor
witharemoteuser,tryingtointeractwiththesensornetworkviatheInternet(the
standardexampleistoreadthetemperaturesensorsinone’shomewhiletravelingand
accessingtheInternetviaawirelessconnection).Figureshowsthisnetworkingscenario.

44. MATRUSRI
ENGINEERING COLLEGE
2. WSN to Internet Communication

45. MATRUSRI
ENGINEERING COLLEGE
3. Internet to WSN communication

46. MATRUSRI
ENGINEERING COLLEGE
4. WSN tunneling

47. MATRUSRI
ENGINEERING COLLEGE
CONCLUSION
Realizationofsensornetworksneedstosatisfyseveralconstraintssuchas
scalability,cost,hardware,topologychange,environmentandpower
consumption.
Sincetheseconstraintsarehighlytightandspecificforsensornetworks,
newwirelessadhocnetworkingprotocolsarerequired.
Tomeettherequirements,manyresearchersareengagedindeveloping
thetechnologiesneededfordifferentlayersofthesensornetworks
protocolstack.

48. MATRUSRI
ENGINEERING COLLEGE
UNIT-III: NETWORKING SENSORS
INTRODUCTION
Thephysicallayerismostlyconcernedwithmodulationanddemodulationof
digitaldata;thistaskiscarriedoutbyso-calledtransceivers.Insensor
networks,thechallengeistofindmodulationschemesandtransceiver
architecturesthataresimple,lowcost,butstillrobustenoughtoprovidethe
desiredservice.
1.Wirelesschannelsarethereforeanunguidedmedium,meaningthatsignal
propagationisnotrestrictedtowell-definedlocations,asisthecaseinwired
transmissionwithpropershielding.Forapracticalwireless,RF-based
system,thecarrierfrequencyhastobecarefullychosen.
2.Intheprocessofmodulation,(groupsof)symbolsfromthechannel
alphabetaremappedtooneofafinitenumberofwaveformsofthesame
finitelength;thislengthiscalledthesymbolduration.Themappingfroma
receivedwaveformtosymbolsiscalleddemodulation.Wavepropagation
effectsandnoiseresultsinbiterrors.

49. MATRUSRI
ENGINEERING COLLEGE
OUTCOMES
Todeterminethesuitableprotocolsandradiohardware.
CONTENTS:
Physical layer and Transceiver Design considerations
MAC protocols for wireless sensors networks
Low Duty cycle and wakeup concepts
-STEM
-S-MAC
-The mediation device protocol
-wakeup radio protocols
Address and Name management
Assignment of MAC Addresses
Routing Protocols
-Energy efficient Routing
-Geographic Routing

50. MATRUSRI
ENGINEERING COLLEGE
Module 1: Physical Layer and Transceiver Design
Considerations
Thephysicallayerinwirelessnetworkedsensorshastobe
designedwithsensornetworkingrequirementsinmind.Inparticular
TheCommunicationdevicemustbecontainableinasmallsize,since
thesensornodesaresmall.Socheaper,slightlylargerantennasmaybe
acceptableinthosecases.
TheCommunicationdevicesmustbecheap,sincethesensorswillbe
usedinlargenumbersinredundantfashion.
Theradiotechnologymustworkwithhigherlayersintheprotocol
stacktoconsumeverylowpowerlevels.

51. MATRUSRI
ENGINEERING COLLEGE
Physical layer Evaluation of Technologies:
We consider 3 main classes of physical layer technologies for use in
wireless sensor networks, based on bandwidth considerations:
Narrowband technologies.
Spread spectrum technologies
Ultra-Wideband (UWB) technologies.

52. MATRUSRI
ENGINEERING COLLEGE
Module 2: MAC protocols for wireless sensors networks
MediumAccessControl(MAC)protocolssolvea
seeminglysimpletask:theycoordinatethetimeswherea
numberofnodesaccessasharedcommunicationmedium.
An“unoverseeable”numberofprotocolshaveemerged
inmorethanthirtyyearsofresearchinthisarea.Theydiffer,
amongothers,inthetypesofmediatheyuseandinthe
performancerequirementsforwhichtheyareoptimized.

53. MATRUSRI
ENGINEERING COLLEGE
Fundamentals of (wireless) MAC protocols:
Requirements and design constraints for wireless MAC protocols:
Throughput, efficiency, stability, fairness, low access delay, low
transmission delay
Hidden Terminal Problem
Exposed terminal scenario

54. MATRUSRI
ENGINEERING COLLEGE
Important classes of MAC protocols
Fixed assignment protocols
-TDMA, FDMA, CDMA, and SDMA.
Demand assignment protocols
-HIPERLAN/2 protocol
-DQRUMA
-MASCARA protocol
-polling schemes
Random access protocols
-CSMA protocols
-Non-persistent CSMA
-Persistent CSMA

55. MATRUSRI
ENGINEERING COLLEGE
RTS/CTS handshake in IEEE 802.11

56. MATRUSRI
ENGINEERING COLLEGE
Two problems in RTS/CTS Handshake

57. MATRUSRI
ENGINEERING COLLEGE
MAC protocols for wireless sensor networks
Balance of requirements
Energy problems on the MAC layer
-Collisions
-Overhearing
-Protocol overhead
-Idle listening
Structure
-Contention-based
-Schedule-based protocols

58. MATRUSRI
ENGINEERING COLLEGE
Module 3: Low duty cycle protocols and wakeup concepts
Lowdutycycleprotocolstrytoavoidspending(much)
timeintheidlestateandtoreducethecommunication
activitiesofasensornodetoaminimum.
Periodic wake up scheme

59. MATRUSRI
ENGINEERING COLLEGE
Sparse topology and energy management (STEM)
TheSparseTopologyandEnergyManagement
(STEM)protocoldoesnotcoverallaspectsofaMAC
protocolbutprovidesasolutionfortheidlelistening
problem
STEM duty cycle for a single node

60. MATRUSRI
ENGINEERING COLLEGE
The S-MAC (Sensor-MAC) protocol provides mechanisms
to circumvent idle listening, collisions, and overhearing. As opposed
to STEM, it does not require two different channels.
S-MAC

61. MATRUSRI
ENGINEERING COLLEGE
S-MACadoptsaperiodicwakeupscheme,thatis,eachnode
alternatesbetweenafixed-lengthlistenperiodandafixed-
lengthsleepperiodaccordingtoitsschedule,asopposedto
STEM,thelistenperiodofS-MACcanbeusedtoreceiveand
transmitpackets.
S-MACattemptstocoordinatetheschedulesofneighboring
nodessuchthattheirlistenperiods
Startatthesametime.Anodex’slistenperiodissubdivided
intothreedifferentphases:
•Inthefirstphase(SYNCHphase),
•Inthesecondphase(RTSphase),
•Inthethirdphase(CTSphase),
S-MAC Principle

62. MATRUSRI
ENGINEERING COLLEGE
S-MAC Fragmentation and NAV settings

63. MATRUSRI
ENGINEERING COLLEGE
The Mediation device protocol
Themediationdeviceprotocoliscompatiblewiththepeer-to-
peercommunicationmodeoftheIEEE802.15.4low-rateWPAN
standard.ItallowseachnodeinaWSNtogointosleepmode
periodicallyandtowakeuponlyforshorttimestoreceivepackets
fromneighbornodes.Thereisnoglobaltimereference,eachnodehas
itsownsleepingschedule,anddoesnottakecareofitsneighborssleep
schedules.
Uponeachperiodicwakeup,anodetransmitsashortquery
beacon,indicatingitsnodeaddressanditswillingnesstoaccept
packetsfromothernodes.Thenodestaysawakeforsomeshorttime
followingthequerybeacon,toopenupawindowforincoming
packets.Ifnopacketisreceivedduringthiswindow,thenodegoes
backintosleepmode.
Dynamicsynchronization
Mediationdevice(MD)

64. MATRUSRI
ENGINEERING COLLEGE
The Mediation device protocol
Mediation device protocol with unconstrained protocol

65. MATRUSRI
ENGINEERING COLLEGE
Wakeup radio concepts
Theidealsituationwouldbeifanodewerealwaysin
thereceivingstatewhenapacketistransmittedtoit,inthe
transmittingstatewhenittransmitsapacket,andinthesleep
stateatallothertimes;theidlestateshouldbeavoided.The
wakeupradioconceptstrivestoachievethisgoalbya
simple,“powerless”receiverthatcantriggeramainreceiver
ifnecessary.

66. MATRUSRI
ENGINEERING COLLEGE
The IEEE 802.15.4 MAC protocol
Wireless Personal Area Network (WPAN)
ThestandarddistinguishesontheMAClayertwotypesof
nodes:
AFullFunctionDevice(FFD)canoperateinthree
differentroles:itcanbeaPANcoordinator(PAN=
PersonalAreaNetwork),asimplecoordinatororadevice.
AReducedFunctionDevice(RFD)canoperateonlyas
adevice.

67. MATRUSRI
ENGINEERING COLLEGE

68. MATRUSRI
ENGINEERING COLLEGE
ROUTING PROTOCOLS
Energy Efficient Routing
Geographic Routing

69. MATRUSRI
ENGINEERING COLLEGE
MATRUSRI
ENGINEERING COLLEGE
UNIT-IV: INFRASTRUCTURE ESTABLISHMENT
INTRODUCTION
Inadenselydeployedwirelessnetwork,asinglenodehasmanyneighboring
nodeswithwhichdirectcommunicationwouldbepossiblewhenusing
sufficientlylargetransmissionpower.
Thisis,however,notnecessarilybeneficial:hightransmissionpower
requireslotsofenergy,manyneighborsareaburdenforaMACprotocol,and
routingprotocolssufferfromvolatilityinthenetworkwhennodesmovearound
andfrequentlyformorsevermanylinks.
To overcome these problems, topology control can be applied.
Theideaistodeliberatelyrestrictthesetofnodesthatareconsidered
neighborsofagivennode.Thiscanbedonebycontrollingtransmissionpower,
byintroducinghierarchiesinthenetworkandsignalingoutsomenodestotake
overcertaincoordinationtasks,orbysimplyturningoffsomenodesfora
certaintime.

70. MATRUSRI
ENGINEERING COLLEGE
MATRUSRI
ENGINEERING COLLEGE
OUTCOMES
Toevaluatetheperformanceofsensornetworkandidentify
bottlenecks.
CONTENTS
Topology control
Clustering
Time synchronization
Localization and positioning
Sensor Tasking and control

71. MATRUSRI
ENGINEERING COLLEGE
Module 1: Motivation -Dense networks
Inaverydensenetworks,toomanynodesmightbeinrangeforan
efficientoperation
•Toomanycollisions/toocomplexoperationforaMAC
protocol,toomanypathstochoosefromforaroutingprotocol.
Idea:Maketopologylesscomplex
•Topology:Whichnodeisable/allowedtocommunicatewith
whichothernodes
•Topologycontrolneedstomaintaininvariants,e.g.,
connectivity

72. MATRUSRI
ENGINEERING COLLEGE
Options for Topology control

73. MATRUSRI
ENGINEERING COLLEGE
Flat networks
Main option: Control transmission power
•Do not always use maximum power
•Selectively for some links or for a node as a whole
•Topology looks “thinner”
•Less interference.
Alternative: Selectively discard some links
•Usually done by introducing hierarchies

74. MATRUSRI
ENGINEERING COLLEGE
Hierarchical networks –Backbone
Construct a backbonenetwork
•Some nodes “control” their neighbors –
they form a (minimal) dominating set
•Each node should have a controlling
neighbor
•Controlling nodes have to be connected
(backbone)
•Only links within backbone and from
backbone to controlled neighbors are used.

75. MATRUSRI
ENGINEERING COLLEGE
Hierarchical network –clustering
Construct clusters
Partition nodes into groups (“clusters”)
Each node in exactly one group
•Except for nodes “bridging” between two or more groups
Groups can have cluster heads
Typically: all nodes in a cluster are direct neighbors of their cluster head
Cluster heads are also a dominating set, but should be separated from each
other –they form an independent set
Formally: Given graph G=(V,E), construct C ½ V such that

76. MATRUSRI
ENGINEERING COLLEGE
Aspects of topology-control algorithms
Connectivity –If two nodes connected in G, they have to
be connected in G
0
resulting from topology
control
Stretch factor –should be small
Hop stretch factor: how much longer are paths in G
0
than in G?
Energy stretch factor: how much more energy does the
most energy-efficient path need?
Throughput–removing nodes/links can reduce
throughput, by how much?
Robustness to mobility
Algorithm overhead

77. MATRUSRI
ENGINEERING COLLEGE
Example: Price for maintaining connectivity
Maintaining connectivity can be very “costly” for a power control approach
Compare power required for connectivity compared to power required to reach a
very big maximum component

78. MATRUSRI
ENGINEERING COLLEGE
Controlling transmission range
Assume all nodes have identical transmission range r=r(|V|),
network covers area A, V nodes, uniformly distr.
Fact: Probability of connectivity goes to zero if:
Fact: Probability of connectivity goes to 1 for
if and only if 
|V|! 1 with |V|
Fact (uniform node distribution, density ):

79. MATRUSRI
ENGINEERING COLLEGE
Controlling number of neighbors
Knowledgeaboutrangealsotellsaboutnumberofneighbors
•Assumingnodedistribution(anddensity)isknown,e.g.,
uniform
Alternative:directlyanalyzenumberofneighbors
•Assumption:Nodesrandomly,uniformlyplaced,only
transmissionrangeiscontrolled,identicalforallnodes,only
symmetriclinksareconsidered
Result:Forconnectednetwork,requirednumberofneighborsper
nodeis(log|V|)
•Itisnotaconstant,butdependsonthenumberofnodes!
•Foralargernetwork,nodesneedtohavemoreneighbors&
largertransmissionrange!–Ratherinconvenient
•Constantscanbebounded

80. MATRUSRI
ENGINEERING COLLEGE
Example 1: Relative Neighborhood Graph (RNG)
Edge between nodes u and v if and only if there is no other node w that is
closer to either u or v
Formally:
RNG maintains connectivity of the original graph
Easy to compute locally
But: Worst-case spanning ratio is (|V|)
Average degree is 2.6

81. MATRUSRI
ENGINEERING COLLEGE
Example 2: Gabriel graph
Gabrielgraph(GG)similartoRNG
Difference:Smallestcirclewithnodesuandvonitscircumferencemustonly
containnodeuandvforuandvtobeconnected
Formally:
Properties:Maintainsconnectivity,Worst-casespanningratio(|V|
1/2
),energy
stretchO(1)(dependingonconsumptionmodel!),worst-casedegree(|V|)

82. MATRUSRI
ENGINEERING COLLEGE
Example 3: Delaunay triangulation
Assign, to each node, all points in the
plane for which it is the closest node
! Voronoidiagram
•Constructed in O(|V| log |V|) time
Connect any two nodes for which the
Voronoiregions touch
! Delaunay triangulation
Problem: Might produce very long
links; not well suited for power control

83. MATRUSRI
ENGINEERING COLLEGE
Example: Cone-based topology control
Assumption:Distanceandangleinformationbetweennodesisavailable
Two-phasealgorithm
Phase1
Everynodestartswithasmalltransmissionpower
Increaseituntilanodehassufficientlymanyneighbors
Whatis“sufficient”?–Whenthereisatleastoneneighborineach
coneofangle
=5/6isnecessaryandsufficientconditionforconnectivity!
Phase2
Removeredundantedges:Dropaneighborwofuifthereisanode
vofwandusuchthatsendingfromutowdirectlyislessefficient
thansendingfromuviavtow
Essentially,alocalGabrielgraphconstruction

84. MATRUSRI
ENGINEERING COLLEGE
Centralized power control algorithm
Goal: Find topology control algorithm minimizing the maximum
power used by any node
Ensuring simple or bi-connectivity
Assumptions: Locations of all nodes and path loss
between all node pairs are known; each node uses an
individually set power level to communicate with all its
neighbors
Idea: Use a centralized, greedy algorithm
Initially, all nodes have transmission power 0
Connect those two components with the shortest distance
between them (raise transmission power accordingly)
Second phase: Remove links (=reduce transmission power) not
needed for connectivity
Exercise: Relation to Kruskal’sMST algorithm?

85. MATRUSRI
ENGINEERING COLLEGE
Centralized power control algorithm
1 1
2
3
4 4
A B
C D
E F
D
Topology
1 1
A B
C D
E F
1) Connect A-C and B-D
1 1
2A B
C D
E F
2) Connect A-B
1 1
2
3
A B
C D
E F
3) Connect C-D
1 1
2
3
4 4
A B
C
E F
4) Connect C-E and D-F
1 1
3
4 4
A B
C D
E F
5) Remove edge A-B

86. MATRUSRI
ENGINEERING COLLEGE
Hierarchical networks –backbones
Idea:Selectsomenodesfromthenetwork/graphto
formabackbone
Aconnected,minimal,dominatingset(MDS
orMCDS)
Dominatingnodescontroltheirneighbors
Protocolslikeroutingareconfrontedwitha
simpletopology–fromasimplenode,routeto
thebackbone,routinginbackboneissimple
(fewnodes)
Problem:MDSisanNP-hardproblem
Hardtoapproximate,andevenapproximations
needquiteafewmessages

87. MATRUSRI
ENGINEERING COLLEGE
Performance of tree growing with look ahead
Dominatingsetobtainedbygrowingatreewiththe
lookaheadheuristicisatmostafactor2(1+H())larger
thanMDS
H(¢)harmonicfunction,H(k)=
i=1
k
1/i<=lnk+1
ismaximumdegreeofthegraph
Itisautomaticallyconnected
Canbeimplementedinadistributedfashionaswell

88. MATRUSRI
ENGINEERING COLLEGE
Start big, make lean
Idea:startwithsome,possiblylarge,connecteddominatingset,
reduceitbyremovingunnecessarynodes
Initialconstructionfordominatingset
Allnodesareinitiallywhite
Markanynodeblackthathastwoneighborsthatarenot
neighborsofeachother(theymightneedtobedominated)
Blacknodesformaconnecteddominatingset(proofby
contradiction);shortestpathbetweenANYtwonodesonly
containsblacknodes
Needed:Pruningheuristics

89. MATRUSRI
ENGINEERING COLLEGE
Pruning heuristics
Heuristic 1: Unmark node v if
Node v and its neighborhood are included in the neighborhood
of some node marked node u (then u will do the domination for v
as well)
Node v has a smaller unique identifier than u (to break ties)
Heuristic 2: Unmark node v if
Node v’sneighborhood is included in the neighborhood of two
marked neighbors u and w
Node v has the smallest
identifier of the tree nodes
Nice and easy, but only linear approximation
factor

90. MATRUSRI
ENGINEERING COLLEGE
One more distributed backbone heuristic: Span
Construct backbone, but take into account need to carry traffic –
preserve capacity
Means: If two paths could operate without interference in the
original graph, they should be present in the reduced graph as
well
Idea: If the stretch factor (induced by the backbone) becomes
too large, more nodes are needed in the backbone
Rule: Each node observes traffic around itself
If node detects two neighbors that need three hops to
communicate with each other,
node joins the backbone, shortening the path
Contention among potential
new backbone nodes handled
using random backoff

91. MATRUSRI
ENGINEERING COLLEGE
Module 2: Clustering
Partition nodes into groups of nodes –clusters
Many options for details
Are there cluster heads? –One controller/representative node per cluster
May cluster heads be neighbors? If no: cluster heads form an
independent set C:
Typically: cluster heads form a maximum independent set
May clusters overlap? Do they have nodes in common?

92. MATRUSRI
ENGINEERING COLLEGE
Clustering
Further options
How do clusters communicate? Some nodes need to act as
gatewaysbetween clusters
If clusters may not overlap, two nodes need to jointly act as a
distributed gateway
How many gateways exist between clusters? Are all active, or
some standby?
What is the maximal diameter of a cluster? If more than 2, then
cluster heads are not necessarily a maximum independent set
Is there a hierarchy of clusters?

93. MATRUSRI
ENGINEERING COLLEGE
Maximum independent set
ComputingamaximumindependentsetisNP-complete
Canbeapproximatewithin(+3)/5forsmall,within
O(log log/ log ) else; bounded degree
Show:Amaximumindependentsetisalsoadominatingset
Maximumindependentsetnotnecessarilyintuitivelydesired
solution
Example:Radialgraph,withonly(v
0,v
i)2E

94. MATRUSRI
ENGINEERING COLLEGE
Determining gateways to connect clusters
Suppose:Clusterheadshavebeenfound
Howtoconnecttheclusters,howtoselectgateways?
Itsufficesforeachclusterheadtoconnecttoallotherclusterheads
thatareatmostthreehops
Resultingbackbone(!)isconnected
Formally:Steinertreeproblem
Given:GraphG=(V,E),asubsetC½V
Required:FindanothersubsetT½VsuchthatS[T]is
connectedandS[T]isacheapestsuchset
Costmetric:numberofnodesinT,linkcost
Here:specialcasesinceCareanindependentset

95. MATRUSRI
ENGINEERING COLLEGE
Rotating cluster heads
Serving as a cluster head can put additional burdens on a node
For MAC coordination, routing, …
Let this duty rotate among various members
Periodically reelect –useful when energy reserves are used as
discriminating attribute
LEACH –determine an optimal percentage P of nodes to become
cluster heads in a network
•Use 1/P rounds to form a period
•In each round, nPnodes are elected as cluster heads
•At beginning of round r, node that has not served as cluster head in
this period becomes cluster head with probability P/(1-p(r mod 1/P))

96. MATRUSRI
ENGINEERING COLLEGE
Multi-hop clusters
Clusterswithdiameterslargerthan2canbeuseful,e.g.,when
usedforroutingprotocolsupport
Formally:Extend“domination”definitiontoalsodominatenodes
thatareatmostdhopsaway
Goal:FindasmallestsetDofdominatingnodeswiththis
extendeddefinitionofdominance
Onlysomewhatcomplicatedheuristicsexist
Differenttilt:Fixthesize(notthediameter)ofclusters
Idea:Usegrowthbudgets–amountofnodesthatcanstillbe
adoptedintoacluster,passthisnumberalongwithbroadcast
adoptionmessages,reducebudgetasnewnodesarefound

97. MATRUSRI
ENGINEERING COLLEGE
Passive clustering
Constructing a clustering structure brings overheads
Not clear whether they can be amortized via improved efficiency
Question: Eat cake and have it?
Have a clustering structure without any overhead?
Maybe not the best structure, and maybe not immediately, but
benefits at zero cost are no bad deal…
Passive clustering
Whenever a broadcast message travels the network, use it to
construct
clusters on the fly
Node to start a broadcast: Initial node
Nodes to forward this first packet: Cluster head
Nodes forwarding packets from cluster heads: ordinary/gateway
nodes
And so on… ! Clusters will emerge at low overhead

98. MATRUSRI
ENGINEERING COLLEGE
Adaptive node activity
Remainingoption:Turnsomenodesoff
deliberately
Onlypossibleifothernodesremainonthat
cantakeovertheirduties
Exampleduty:Packetforwarding
Approach:GeographicAdaptiveFidelity(GAF)
Observation: Any two nodes within a
square of length r < R/5
1/2
can
replace each other with respect to
forwarding
R radio range
Keep only one such node active, let
the other sleep

99. MATRUSRI
ENGINEERING COLLEGE
Module 3: SENSOR TASKING and CONTROL
Toefficientlyandoptimallyutilizescarceresourcesinasensor
network,suchaslimitedon-boardbatterypowersupplyandlimited
communicationbandwidth,nodesinasensornetworkmustbecarefully
taskedandcontrolledtocarryouttherequiredsetoftaskswhile
consumingonlyamodestamountofresources.
For example :a camera sensor may be tasked to look for animals of a
particular size and color, or an acoustic sensor may be tasked to detect
the presence of a particular type of vehicle.
To detect and track a moving vehicle, a pan-and-tilt camera may be
tasked to anticipate and follow the vehicle object. It should be noted that
to achieve scalability and autonomy, sensor tasking and control have to
be carried out in a distributed fashion, largely using only local
information available to each sensor.

100. MATRUSRI
ENGINEERING COLLEGE

101. MATRUSRI
ENGINEERING COLLEGE
TASK DRIVEN SENSING
However, this classical algorithm/complexity view needs to be
modified in the sensor network context because
The values of the relevant manifest variables are not known, but
have to be sensed.
The cost of sensing different variables or relations of the same type
can be vastly different—depending on the relative locations of targets
and sensors, the sensing modalities available, the environmental
conditions, and the communication costs.
Frequently the value of a variable, or a relationship between
variables, may be impossible to determine using the resources
available in the sensor network; however, alternate variable values or
relations may serve our purposes equally well.

102. MATRUSRI
ENGINEERING COLLEGE
TASK DRIVEN SENSING
Todesignanoverallstrategy,severalkeyquestionsneedtobe
addressed:
Whataretheimportantobjectsintheenvironmenttobesensed?
Whatparametersoftheseobjectsaremostrelevant?
Whatrelationsamongtheseobjectsarecriticaltowhateverhigh
levelinformationweneedtoknow?
Whichisthebestsensortoacquireaparticularparameter?
Howmanysensingandcommunicationoperationswillbeneeded
toaccomplishthetask?
Howcoordinateddotheworldmodelsofthedifferentsensors
needtobe?
Atwhatleveldowecommunicateinformation,inthespectrum
fromsignaltosymbol?

103. MATRUSRI
ENGINEERING COLLEGE
Roles of Sensor Nodes and Utilities
Sensorsinanetworkmaytakeondifferentroles.
Considerthefollowingexample:ofmonitoringtoxicitylevelsin
anareaaroundachemicalplantthatgenerateshazardouswaste
duringprocessing.
Anumberofwirelesssensorsareinitiallydeployedinthe,
Duetothenatureoftheenvironmentandthecostofdeployment,
furtherhumaninterventionornodereplacementisnotfeasible.
Thesensorsformameshnetwork,anddatacollectedbyasubset
ofnodesistransmitted,throughthemulti-hopnetwork.

104. MATRUSRI
ENGINEERING COLLEGE

105. MATRUSRI
ENGINEERING COLLEGE
INFORMATION BASED SENSOR TASKING
Sensorselection
Informationdrivensensorquery(IDSN)
Cluster-leaderbasedProtocol
Leaderelectionprotocol
Sensortaskingintaskingrelations

106. MATRUSRI
ENGINEERING COLLEGE

107. MATRUSRI
ENGINEERING COLLEGE

108. MATRUSRI
ENGINEERING COLLEGE

109. MATRUSRI
ENGINEERING COLLEGE
JOINT ROUTING and INFORMATION AGGREGEATION

110. MATRUSRI
ENGINEERING COLLEGE
JOINT ROUTING and INFORMATION AGGREGATION
Moving center of Aggregation
Locally optimization
Simulation Experiments
Multi step information-Directed Routing
Sensor Group management
Distributed group management

111. MATRUSRI
ENGINEERING COLLEGE
UNIT V : SURVEY OF SECURITY PROTOCOLS
INTRODUCTION
Advancementsinwirelesscommunications,low-powerelectronics,
batterytechnology,andpowerharvestingcapabilitieshaveenabledthe
developmentoflow-costWSNs.WSNsarecharacterizedbylimitedpower,
unreliablecommunication,needforself-configurationandscalability,harsh
environmentalconditions,smallsize,cooperativenetworkbehavior,data
centricity(asopposedtoaddresscentricity),verysmallpacketsize,
unattendedoperation,andrandomdeployment.Giventhosecharacteristics,
themostcommonWSNapplicationsareenvironmentalmonitoring,health
monitoring,terrorthreatdetection,terrestrialandunderwaterhabitat
monitoring,militarysurveillance,seismicoilandgasexplorations,inventory
tracking,processmonitoring,acousticdetections,objectlocalizationand
tracking,homelandsecurityprotection,disasterpreventionanddisaster
recovery,andpipelinescorrosiondetection.Figure1.showsanexampleof
WSNarchitecture.Eachnodeconsistsofasensingunit,aprocessingunit,a
communicationunit,abattery,andapowerharvester

112. MATRUSRI
ENGINEERING COLLEGE
CONTENTS
SecurityArchitectures
SurveyofSecurityprotocolsforWirelessSensor
Networks
Comparisons
OUTCOMES
Evaluate concepts of security in sensor networks

113. MATRUSRI
ENGINEERING COLLEGE
A typical sensor network and components of a sensor node

114. MATRUSRI
ENGINEERING COLLEGE
Problems Applying Traditional Network Security Techniques
Sensor devices are limited in their energy, computation, and
communication capabilities
Sensor nodes are often deployed in open areas, thus allowing physical
attack
Sensor networks closely interact with their physical environments and
with people , posing new security problems

115. MATRUSRI
ENGINEERING COLLEGE
Key Establishment and Trust
Sensordeviceshavelimitedcomputationalpower,
makingpublic-keycryptographicprimitivestoo
expensiveintermsofsystemoverhead
Simplestsolutionisanetwork-widesharedkey
Problem:ifevenasinglenodewerecompromised,
thesecretkeywouldberevealed,anddecryptionof
allnetworktrafficwouldbepossible
Slightlybettersolution:
Useasinglesharedkeytoestablishasetoflink
keys,oneperpairofcommunicatingnodes,then
erasethenetwork-widekey
Problem:doesnotallowadditionofnewnodes
afterinitialdeployment

116. MATRUSRI
ENGINEERING COLLEGE
Random-key pre-distribution protocols
Large pool of symmetric keys is chosen
Random subset of the pool is distributed to each sensor node
To communicate, two nodes search their pools for a common key
If they find one, they use it to establish a session key
Not every pair of nodes shares a common key, but if the key-
establishment probability is sufficiently high, nodes can securely
communicate with sufficiently many nodes to obtain a connected
network
No need to include a central trusted base station
Disadvantage: Attackers who compromised sufficiently many
nodes could also reconstruct the complete key pool and break the
scheme

117. MATRUSRI
ENGINEERING COLLEGE
Secrecy and Authentication
Weneedcryptographyasprotectionagainsteavesdropping,
injection,andmodificationofpackets
Trade-offswhenincorporatingcryptographyintosensor
networks:
End-to-endcryptographyachievesahighlevelofsecurity
butrequiresthatkeysbesetupamongallendpointsandbe
incompatiblewithpassiveparticipationandlocalbroadcast
Link-layercryptographywithanetwork-widesharedkey
simplifieskeysetupandsupportspassiveparticipationand
localbroadcast,butintermediatenodesmighteavesdropor
altermessages

118. MATRUSRI
ENGINEERING COLLEGE
Hardware vs. Software Cryptography
Hardwaresolutionsaregenerallymoreefficient,butalsomore
costly($)
UniversityofCalifornia,Berkeley,implementationofTinySec
incursonlyanadditional5%–10%performanceoverheadusing
software-onlymethods
Mostoftheoverheadisduetoincreasesinpacketsize
Cryptographiccalculationshavelittleeffectonlatencyor
throughput,sincetheycanoverlapwithdatatransfer
Hardwarereducesonlythecomputationalcosts,notpacketsize
Thus,software-onlytechniquesaresufficient(orreasonabletobe
morecareful)

119. MATRUSRI
ENGINEERING COLLEGE
Privacy
Issues
Employersmightspyontheiremployees
Shopownersmightspyoncustomers
Neighboursmightspyoneachother
Lawenforcementagenciesmightspyonpublicplaces
Technologicalimprovementswillonlyworsentheproblem
Deviceswillgetsmallerandeasiertoconceal
Deviceswillgetcheaper,thussurveillancewillbemore
affordable

120. MATRUSRI
ENGINEERING COLLEGE
Sensornetworksraisenewthreatsthatarequalitativelydifferent
fromwhatprivatecitizensworldwidefacedbefore
Sensornetworksallowdatacollection,coordinatedanalysis,
andautomatedeventcorrelation
Networkedsystemsofsensorscanenableroutinetrackingof
peopleandvehiclesoverlongperiodsoftime
EZPass+OnStar==BigBrother?
Suggestedwaysofapproachingsolutionincludeamixof:
Societalnorms
Newlaws
Technologicalresponses
Privacy(Contd)

121. MATRUSRI
ENGINEERING COLLEGE
Network Security Services
So far, we’ve explored low-level security primitives
for securing sensor networks.
Now, we consider high-level security mechanisms.
Secure group management
Intrusion detection
Secure data aggregation

122. MATRUSRI
ENGINEERING COLLEGE
Secure Group Management
Protocolsforgroupmanagementarerequiredto
Securelyadmitnewgroupmembers
Supportsecuregroupcommunication
Outcomeofgroupcomputationmustbeauthenticatedtoensure
itcomesfromavalidgroup
Anysolutionmustalsobeefficientintermsoftimeandenergy

123. MATRUSRI
ENGINEERING COLLEGE
Intrusion detection
Inwirednetworks,trafficandcomputationaretypically
monitoredandanalyzedforanomaliesatvariousconcentration
points
Expensiveintermsofthenetwork’smemoryandenergy
consumption
Hurtsbandwidthconstraints
Wirelesssensornetworksrequireasolutionthatisfully
distributedandinexpensiveintermsofcommunication,energy,and
memoryrequirements
Inordertolookforanomalies,applicationsandtypicalthreat
modelsmustbeunderstood
Itisparticularlyimportantforresearchersandpractitionersto
understandhowcooperatingadversariesmightattackthesystem
Theuseofsecuregroupsmaybeapromisingapproachfor
decentralizedintrusiondetection

124. MATRUSRI
ENGINEERING COLLEGE
Secure Data Aggregation
Onebenefitofawirelesssensornetworkisthefine-grain
sensingthatlargeanddensesetsofnodescanprovide
Thesensedvaluesmustbeaggregatedtoavoidoverwhelming
amountsoftrafficbacktothebasestation
Dependingonthearchitectureofthenetwork,aggregationmay
takeplaceinmanyplaces
Allaggregationlocationsmustbesecured
Iftheapplicationtoleratesapproximateanswers,powerful
techniquesareavailable
Randomlysamplingasmallfractionofnodesandchecking
thattheyhavebehavedproperlysupportsdetectionofmany
differenttypesofattacks

125. MATRUSRI
ENGINEERING COLLEGE
Conclusions
Constraintsandopenenvironmentsofwirelesssensornetworks
makesecurityforthesesystemschallenging.
Severalpropertiesofsensornetworksmayprovidesolutions.
Architectsecurityintothesesystemsfromtheoutset(they
arestillintheirearlydesignstages)
Exploitredundancy,scale,andthephysicalcharacteristicsof
theenvironmentinthesolutions
Buildsensornetworkssothattheycandetectandwork
aroundsomefractionoftheirnodeswhicharecompromised