Wireless Sensor Network: WSN Routing,CS 80240333 Instructor: CUI Yong,1,Outline,Introduction Design issues Routing design Flat routing Hierarchical routing Location-based routing Programming and database perspective Future directions Conclusions,2,Outline,Introduction Design issues Routing design Flat routing Hierarchical routing Location-based routing Programming and database perspective Future directions Conclusions,3,Introduction,Routing protocols in WSNs Differ depending on the application and network architecture Classified into three categories based on the underlying network structure: Flat: Nodes are assigned equal roles Hierarchical: Nodes will play different roles Location-based: Nodes positions are exploited to route data Classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent-based depending on the protocol operation Trade-offs between energy and communication overhead savings,4,Modified from presentation of Jamal N. Al-Karaki et al. Wireless Communications 2004 http:/oplab.im.ntu.edu.tw/Download/93/94_0425/Routing%20Techniques%20in%20Wireless%20Sensor%20Networks.ppt,Introduction (contd),5,Outline,Introduction Design issues Routing design Flat routing Hierarchical routing Location-based routing Programming and database perspective Future directions Conclusions,6,Design issues,Design goals Carry out data communication Prolong the lifetime of the network Prevent connectivity degradation by employing aggressive energy management techniques,7,Design issues (contd),Node deployment: application-dependent Manual (deterministic): data is routed through predetermined paths Randomized: nodes are scattered randomly, creating an ad hoc routing infrastructure Distribution of nodes is not uniform, optimal clustering becomes necessary Energy consumption without losing accuracy Use up their limited supply of energy The malfunctioning of some sensor nodes Data reporting method Time-driven: for application requiring periodic data monitoring Event-driven: react due to a certain event (time-critical ap) Query-driven: response to a query (time-critical ap) Hybrid,8,Design issues (contd),Node/link heterogeneity For example, hierarchical protocols designate a cluster head node Fault tolerance The failure of sensor nodes should not affect the overall task of the sensor network Scalability Any routing scheme must be able to work with huge number of sensor nodes Network dynamics Nodes can be mobile The phenomenon can be mobile Transmission media The required bandwidth is low(1-100 kb/s) TDMA-based protocols conserve more energy than contention-based protocols (like CSMA),9,Design issues (contd),Connectivity Density in sensor networks Depends on the possibly random distribution of nodes Coverage A sensors view of the environment is limited in both range and accuracy Data aggregation Sensor nodes may generate significant redundant data To reduce the number of transmissions Quality of service Network lifetime often is considered more important Bounded latency for data delivery is a condition for time-constrained applications,10,Outline,Introduction Design issues Routing design Flat routing Hierarchical routing Location-based routing Programming and database perspective Future directions Conclusions,11,Flat routing,Each node plays the same role Data-centric routing Due to not feasible to assign a global id to each node Save energy through data negotiation and elimination of redundant data Protocols Sensor Protocols for Information via Negotiation (SPIN): Heinzelman et.al.Mobicom99&Wireless Networks 2002 Directed diffusion (DD): Intanagonwiwat et al.Mobicom00 Rumor routing: Braginsky et al.WSNA2002 Minimum Cost Forwarding Algorithm (MCFA): F.YeICCCN2001,12,Sensor protocols for information via negotiation (SPIN),Features Negotiation to operate efficiently and to conserve energy using a meta-data Resource adaptation To extend the operating lifetime of the system monitoring their own energy resources SPIN Message ADV new data advertisement REQ request for ADV data DATA actual data message ADV, REQ messages contain only meta-data,13,Heinzelman et.al.Mobicom99&Wireless Networks2002,Sensor protocols for information via negotiation (SPIN) (contd),Operation process,14,Sensor protocols for information via negotiation (SPIN) (contd),Resource adaptive algorithm When energy is plentiful Communicate using the 3-stage handshake protocol When energy is approaching a low-energy threshold If a node receives ADV, it does not send out REQ Energy is reserved to sensing the event Advantage Simplicity Each node performs little decision making when it receives new data Need not forwarding table Robust to topology change Drawback Large overhead Data broadcasting,15,Directed Diffusion (DD),Feature Data-centric routing protocol A path is established between sink node and source node Localized interactions The propagation and aggregation procedures are all based on local information Fou