UI ECE 5995 - Introduction to Wireless Sensor Networks

Unformatted text preview:

Introduction to Wireless Sensor NetworksOrganizationalRoutingSlide 4Examples of AttributesWSN RoutingGraphsGreedy Distance and Compass RoutingProblem With Greedy DistanceSide-Bar Maze SolverPlanar GraphsPlanerizationPlanarization Requirements for WSNSlide 14ExamplesConvex Perimeter RoutingVariationsSide-Bar Parametric EquationsRouting on A CurveSlide 20Optimal PathReview QuestionsSlide 231The University of Iowa. Copyright© 2005A. KrugerIntroduction to Wireless Sensor Networks Routing in WSNs28 February 20052The University of Iowa. Copyright© 2005A. KrugerOrganizationalMonday 4:30-5:20 Room 4511 SCThursday 12:30-1:20 Room 3220 SCPlease note that the room numbers are different for Mondays and Thursdays.Class Websitewww.engineering.uiowa.edu/~ece195/2005/Class TimeMidterm Exam Time: March 10, 2005Monday 5:20-620 Room 1126 SCThursday 1:30-2:30 Room 1126 SCOffice Hours3The University of Iowa. Copyright© 2005A. KrugerRouting•What is meant by “routing”?•Internet (TCP/IP)–Routing tables often large–Can be updated frequently•WSN–Frequent topology changes–Modest local storage–Expensive to update frequently–=> Need local, stateless algorithms where nodes know only immediate neighbors4The University of Iowa. Copyright© 2005A. KrugerRouting•Consider the following–The fundamental difference between classical routing and routing for sensor networks is that the separation between address and content of packet no longer viable•What does it mean?–Network is a system, individual nodes come and go, information sensed by one node can be sensed by another close by•Data-centric view–Routing decision as based not on destination address, but rather on destination attributes and relation to attribute of packet content–Information providers and information seekers must be matched using data attributes and not (hard) network address5The University of Iowa. Copyright© 2005A. KrugerExamples of Attributes•Node location–But is this not just its address?–Get the rain data from the nodes at the Iowa City airport•Types of sensor connected to a node–Send a control packet to all nodes that have a light sensor connected to it•Certain range of values in certain type of sensed data–Get max, min temperature values in from the sensor network•Pull model–Network is queried similar to a database•Push model–Network can initiate flow of information based on events6The University of Iowa. Copyright© 2005A. KrugerWSN Routing•Geographic routing (more traditional view)–Greedy distance–Compass–Convex perimeter routing–Routing on a curve–Energy-minimizing broadcast•Attribute-based routing (data-centric view)–Directed diffusion–Rumor routing–Geographic hash tables7The University of Iowa. Copyright© 2005A. KrugerGraphs8The University of Iowa. Copyright© 2005A. KrugerGreedy Distance and Compass Routing•Greedy distance –pick the locally optimum (distance) neighbor•Compass routing – pick the locally optimum (angle) neighbor9The University of Iowa. Copyright© 2005A. KrugerProblem With Greedy Distance•Here both x’s neighbors are further than destination10The University of Iowa. Copyright© 2005A. KrugerSide-Bar Maze Solver11The University of Iowa. Copyright© 2005A. KrugerPlanar Graphsnot planarplanar12The University of Iowa. Copyright© 2005A. KrugerPlanerizationBasic idea – keep connectivity between nodesConvex PolygonConcave Polygon13The University of Iowa. Copyright© 2005A. KrugerPlanarization Requirements for WSN•WSNs: local planarization algorithms, where edge xy is introduced if a geometric region (witness region) around xy is free of other nodes.•Require accurate information about location of nodes14The University of Iowa. Copyright© 2005A. KrugerPlanerization•Basic idea – keep connectivity between nodes•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 •Grabriel Graph–The edge xy is introduced if the diameter xy is free of other nodes•Key for WSN: RNG and Gabriel graphs can be found with distributed constructionxyxy15The University of Iowa. Copyright© 2005A. KrugerExamplesRNG Gabriel16The University of Iowa. Copyright© 2005A. KrugerConvex Perimeter Routing•Objective: route from s to d (assume planar graph)•Start in the face just beyond s along sd and walk around that face. Stop if d is reached. If the segment sd is about to be crossed, cross over to the next face along sd, and repeat17The University of Iowa. Copyright© 2005A. KrugerVariations•Non-convex routing adaptation•OFR – Other face routing18The University of Iowa. Copyright© 2005A. KrugerSide-Bar Parametric Equations•Circle–Non parametric: x2 + y2 = a2 –Parametric: x = a cos(t), y = a sin(t), t the parameter•Straight Line–Non parametric: y = mx+c–Parametric: line through point (a, b) parallel to vector (u, v) is given by (x, y) = (a, b) + t·(u, v), t the parameter•Given t one can compute x and y19The University of Iowa. Copyright© 2005A. KrugerRouting on A Curve•Specify a curve a packet should follow•Analytical description of a curve carried by the packet•Curves may correspond to natural features of the environment where the network is deployed•Can be implemented in a local greedy fashion that requires no global knowledge•Curve specified in parametric form C(t)=(x(t),y(t))–t – time parameter – could be just relative time•Each node makes use of nodes trajectory information and neighbor positions to decide the next hop for the packet•Also called trajectory-based routing20The University of Iowa. Copyright© 2005A. Kruger21The University of Iowa. Copyright© 2005A. KrugerOptimal Path•What do we mean by “optimal”–Minimum delay => fewest hops–Minimum Energy => frequent hops (why)•Formally, cost of a path–Where l(e) is the length of the edge in the graph–k is in range 1…5 –k = 0 => Hop length, measure delay–k = 1 => Euclidian path length–k > 1 => Capture energy of path, depending on attenuation modelekelc )()(22The University of Iowa. Copyright© 2005A. KrugerReview Questions•Write a short (5 sentence) paragraph contrasting the needs and resources available in WSN as opposed to, say, the Internet.•Explain the statement “When routing a packet in a WSN, more hops increase delay, but the advantage is that it increases


View Full Document

UI ECE 5995 - Introduction to Wireless Sensor Networks

Download Introduction to Wireless Sensor Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Wireless Sensor Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Wireless Sensor Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?