By Dolores Morales,2014-05-27 14:59
11 views 0



     Wireless Sensor Networks Chapter 11: Routing protocols

     Qinmin Yang qmyang@iipc.zju.edu.cn

     Department of Control Science and Engineering Zhejiang University

     Homework 2

     Given an application with wireless sensor networks (as the one discussed in Homework 1), design a new mechanism to power the nodes. The whole systematic solution should be present and different scenarios should be considered. The advantages and disadvantages of the proposed scheme are also expected to see. Write a report with as many details as you can. (1 page)


     Goals of this chapter

     In any network of diameter > 1, the routing & forwarding problem appears ?C no train running between Beijing and Lijiang ? We will discuss mechanisms for constructing routing tables in ad hoc/sensor networks

     ? ? ? Specifically, when nodes are mobile Specifically, for broadcast/multicast requirements Specifically, with energy efficiency as an optimization metric Specifically, when node position is available

     Note: Presentation here partially follows Beraldi & Baldoni, Unicast Routing Techniques for Mobile Ad Hoc Networks, in M. Ilyas (ed.), The Handbook of Ad Hoc Wireless Networks 3


     ? ? ? ? Basics Gossiping Energy efficiency & unicast routing Multi-/broadcast routing Geographical routing


     Basics ?C Problem definition

     Given: a network/a graph

     Each node has a unique identifier (ID)

     Goal: Derive a mechanism that allows a packet sent from an arbitrary node to arrive at some arbitrary destination node

     The routing & forwarding problem ? Routing: Construct data structures (e.g., tables) that contain information how a given destination can be reached ? Forwarding: Consult these data structures to forward a given packet to its next hop


     Basics ?C Challenges

     Nodes may move around, neighborhood relations change ? Optimization metrics may be more complicated than ??smallest hop count?? ?C e.g., energy efficiency

     5 6 2 3 2 4 13 2 5 2 3 2 4



     Simple solution: Flooding

     ? ? ? Does not need any information (routing tables) ?C simple Packets are usually delivered to destination But: overhead and communication cost is prohibitive Usually not acceptable, either

     Another simple solution: Gossiping

     Wish it luck ?? God knows how much the delay will be


     Basics ?C An alternative

     What if every node keeps a routing table

     Examples: Dijkstra??s link state algorithm; Bellman-Ford distance vector algorithm ? Too big an overhead, too slow in reacting to changes ? Only works for stationary networks


     Ad hoc routing protocols ?C classification

     Main question to ask: When does the routing protocol operate? ? Option 1: Routing protocol always tries to keep its routing data up-to-date

     Protocol is proactive (active before tables are actually needed) or table-driven ?C conservative

     Option 2: Route is only determined when actually needed

     Protocol operates on demand

     Option 3: Combine these behaviors

     Hybrid protocols


     Ad hoc routing protocols ?C classification

     Is the network regarded as flat or hierarchical?

     Compare topology control, traditional routing

     Which data is used to identify nodes? ?C naming & addressing

     An arbitrary identifier? ? The position of a node?

     Can be used to assist in geographic routing protocols because choice of next hop neighbor can be computed based on destination address

     Identifiers that are not arbitrary, but carry some structure?

     As in traditional routing ? Structure akin to position, on a logical level?



     ? ? ? ? Basics Gossiping Energy efficiency & unicast routing Multi-/broadcast routing Geographical routing



     Protocols without routing table

     Reason ?C again, too much overhead involved ? Dynamic networks with

    mobile nodes ? A good topology architecture could do most part of the job

     Backbone or clustering structure

     The node forwards the newly received data packet to an arbitrary neighbor periodically and randomly with a certain probability, for a certain period of time

     How often? Which neighbor? ? It is possible that the destination has not received the data before the forwarding process ends

     Statistics and probability theory is required to answer them



     How to avoid that the destination node does not receive the data, especially for the nodes near the boundary

     Have their neighbors transmit with higher probability ? The initial transmission probability is high enough to prevent the gossip from dying too soon ? Retransmit the message if a node does not overhear it repeated from its neighbors

     The probability of receiving a gossip is increased, but so does the overhead


     Gossiping/rumor routing

     Turn routing problem around: Think of an ??agent?? wandering through the network, looking for data (events, suspects ??) ? Upon detecting an event, the middle node sends out agents initially to perform random walk ? Leave two ??traces?? in the network


     Gossiping/rumor routing

     In case a node is interested the event, it also sends out agents to search for the traces ? Later agents can use these traces to find data (event) ? The traces are similar to the backbone nodes ? Essentially: works due to high probability of line intersections



     ? ? ? ? Basics Gossiping Energy efficiency & unicast routing Multi-/broadcast routing Geographical routing


     Energy-efficient unicast: Goals

     Particularly interesting performance metric: Energy efficiency ? Goals

     Minimize energy/bit

     Example: A-B-E-H 3 A 1 2 3 D B 1 2 3 E 1 4 H 2 2 G 2 4 2 F 1 C 2 4 2

     Maximize network lifetime

     Time until first node failure, loss of coverage, partitioning

     Seems trivial ?C use proper link/path metrics (not hop count) and standard routing

     Example: Send data from node A to node H


     Different perspectives of energy efficiency

     Minimum energy per packet

     Total energy cost for the transmission ? Not necessarily equivalent to the path with minimum hops ? Example: A-B-E-H ? Depends on the definition of network lifetime

     4 3 A 1 2 3 D B 1 2 3 E 1 4 H 2 2 G 2 4 2 F 1 C 2 2

     Maximum network lifetime ? Maximum total available battery capacity

     Path metric: Sum of battery levels ? Should not contain a path subset ? Example: A-C-F-H


     Different perspectives of energy efficiency

     Minimum battery cost routing

     In order to protect nodes with low energy battery resources ? Path metric: Sum of reciprocal battery levels ? Example: A-D-H

     Simply the largest reciprocal level of all nodes is compared ? Example: A-D-H

     4 3 A 1 2 3 D B 1 2 3 E 1 4 H 2 2 G 2 4 2 F 1 C 2 2

     Min-Max battery cost routing

     Conditional max-min battery capacity routing

     Only take battery level into account when below a given level, otherwise minimum energy per packet ? A-D-H


     Different perspectives of energy efficiency

     Minimize variance in power levels

     In order to reduce the variance in battery levels between different routes ? To ensure a long network lifetime

     4 3 A 1 2 3 D B 1 2 3 E 1 4 H 2 2 G 2 4 2 F 1 C 2 2

     Minimum total transmission power

     Take into account the interference between channels


     A non-trivial path metric

     Previous path metrics do not perform particularly well ? One non-trivial link weight:

     wij weight for link node i to node j ? eij required energy, ?Ë>1 some constant, ?Ái fraction of battery of node i already used up ? The more battery energy exhausted, the higher the link weight

     Path metric: Sum of link weights

     Use path with smallest metric

     Properties: Many messages can be send, high network lifetime

     With admission control, the lowest cost path can be selected to

transmit the packet


     Multipath unicast routing

     Instead of only a single path, it can be useful to compute multiple paths between a given source/destination pair

     Multiple paths can be disjoint or braided ? Can be built in a centralized or distributed manner ? Robustness improved if some nodes fail

     Disjoint paths Secondary path

     Source Braided paths

     Sink Primary path


     Sink Primary path


     Multipath unicast routing

     Multiple paths can be used simultaneously

     Transmit efficiency can be increased ? Delay may be involved ? Additional computation is needed for the source and sink nodes

     ?? alternatively

     If a path fails, there are still backups

     ?? randomly

     To share the burden with all available paths ? Statistically, the available battery capacity is exploited better



     ? ? ? ? Basics Gossiping Energy efficiency & unicast routing Multi-/broadcast routing Geographical routing


     Broadcast & multicast (energy-efficient)

     Definitions ?C Distribute a packet to all reachable nodes (broadcast) or to a somehow (explicitly) denoted subgroup (multicast) ? Given a source set and a destination set for each source, basic options

     Source-based tree: Construct a tree (one for each source) to reach all addressees ?C two options

     Minimize total cost (= sum of link weights) of the tree ? Minimize maximum cost to each destination

     Shared, core-based trees: Construct a tree for a core node

     Use only a single tree for all sources to save cost ? Every source sends packets to the tree where they are distributed


     Trees are only 1-connected! Use meshes to provide higher redundancy and thus robustness in mobile environments. Costly!


     Optimization goals for source-based trees

     For each source, minimize total cost

     This is the Steiner tree problem again ?C a NPcomplete problem, minimum cost spanning tree

     Steiner tree Source 2 2 1 Destination 2

     Destination 1 Shortest path tree Source 2 2 1 Destination 2

     For each source, minimize maximum cost to each destination

     This is obtained by overlapping the individual shortest paths as computed by a normal routing protocol

     Destination 1


     Summary of options (broadcast/multicast)



     One tree per source

     Shared tree (core-based tree)


     Minimize total cost (Steiner tree)

     Minimize cost to each node (e.g., Dijkstra)

     Single core

     Multiple core


     Wireless multicast advantage

     Broad-/Multicasting in wireless is unlike broad-/multicasting in a wired medium

     Wires: locally distributing a packet to n neighbors: n times the cost of a unicast packet ? Wireless: sending to n neighbors can incur costs

     As high as sending to a single neighbor ?C if receive costs are neglected completely ? As high as sending once, receiving n times ?C if receives are tuned to the right moment ? As high as sending n unicast packets ?C if the MAC protocol does not support local multicast

     If local multicast is cheaper than repeated unicasts, then wireless multicast advantage is present

     Can be assumed realistically


     Steiner tree approximations

     Computing Steiner tree is NP complete ? A simple approximation

     Pick some arbitrary order of all destination nodes + source node ? Successively add these nodes to the tree: For every next node, construct a shortest path to some other node already on the tree ? Performs reasonably well in practice

     Takahashi Matsuyama heuristic

     Similar, but let algorithm decide which is the next node to be added ? Start with source node, add that destination node to the tree which

    has shortest path ? Iterate, picking that destination node which has the shortest path to some node already on the tree ? And does not really fit to the Steiner tree formulation ?C nodes are added one by one


     Problem: Wireless multicast advantage not exploited!

     Broadcast incremental power (BIP)

     How to broadcast, using the wireless multicast advantage?

     Goal: use as little transmission power as possible

     Idea: Use a minimum-spanning-tree-type construction (Prim??s algorithm) ? Reason: Once a node transmits at a given power level & reaches some neighbors, it becomes cheaper to reach additional neighbors ? From BIP to multicast incremental power (MIP):

     Start with broadcast tree construction, then prune unnecessary edges out of the tree


     BIP ?C Algorithm


     BIP ?C Example

     Round 1.1 A 5 S 10 1 C 3 1 7 Round 1.4: A 4 S (1) 9 1 C 2 7 D 1 C


     Round 1.2 A 3 B S 10 1 C 3 B S (1) 9 2 3 5 1 7 Round 1.5: A 4 3 B

     Round 1.3: A 5 S 9 1 C 3 B 7 2 1 7 3 B





     BIP ?C Example

     Round 1: A 5 S 10 1 C Round 4: A 2 S (3) 7 6 D C (1) D C (1)


     Round 2: 3 1 B 7 D 1 S (1) 9

     A 4 3 B 2 7 Round 5:

     Round 3:

     A 2 3 B 7

     S (3) 7 1 C 3



     D A

     C 3 B

     S (5) 10 7



     Multicast Incremental Power (MIP)

     BIP + pruning ? Start with broadcast tree construction, then prune unnecessary edges out of the tree

     Embedded wireless multicast

     Based viability lemma

     Distributed position-based wireless multicast

     Collect the information about all neighbors ? Then use a ??neighbor elimination?? procedure to remove edges in terms of physical distance

     Shared core-based tree protocols

     Key ?C find a good core node, which should be representative


     Example for mesh-based multicast

     Two-tier data dissemination

     Overlay a mesh, route along mesh intersections ? Broadcast within the quadrant where the destination is (assumed to be) located



     Further topics

     Gossiping for multicast

     Network-wise gossiping

     Multicast with directed antennas

     Change of hardware to save transmission power

     Relationship to topology control

     Extremely close. Usually they are designed together

     Optimal solutions by linear programming

     To achieve the minimum power broadcasted ? Related to optimal control or optimality ? Dynamic programming ?C solving HJB equation

     Optimal solution for tree networks

     To achieve the optimal data collection and distribution ?C tree construction


     Further topics

     Time to complete a multicast

     So far, we have been concentrating on power. How about time?

     Data placement

     Data caches are added for the Steiner tree

     Cooperative multihop broadcast

     Data could be lost during transmission ? Data fusion



     ? ? ? ? Basics Gossiping Energy efficiency & unicast routing Multi-/broadcast routing Geographical routing

     Position-based routing ? Geocasting


     Geographic routing

     Routing tables contain information to which next hop a packet should be forwarded

     Explicitly constructed

     Alternative: Implicitly infer this information from physical placement of nodes

     Position of current node, current neighbors, destination known ?C send to a neighbor in the right direction as next hop ? Geographic routing


     Send to any node in a given area ?C geocasting ? Use position information to aid in routing ?C position-based routing

     Might need a location service to map node ID to node position


     Basics of position-based routing

     ??Most forward within range r?? strategy

     Send to that neighbor that realizes the most forward progress towards destination ? NOT: farthest away from sender! ? Topology is ignored

     Nearest node with (any) forward progress

     Idea: Minimize transmission power ? It is a step forward anyway

     Directional routing

     Choose next hop that is angularly closest to destination ? Or choose next hop that is closest to the connecting line to destination ? Problem: Might result in loops!


     Problem: Dead ends

     Simple strategies might send a packet into a dead end


     How to get out of dead ends

     Restricted flooding?

     Forward data to some or all of the nodes that are closer to the destination ? Not working for this example


     Right hand rule to leave dead ends ?C GPSR

     Basic idea to get out of a dead end: Put right hand to the wall, follow the wall ?C remember the childhood maze puzzles?

     Does not work if on some inner wall ?C will walk in circles ? Need some additional rules to detect such circles

     Geometric Perimeter State Routing (GPSR)

     Earlier versions: Compass Routing II, face-2 routing ? Use greedy, ??most forward?? routing as long as possible ? If no progress possible: Switch to ??face?? routing

     Face: largest possible region of the plane that is not cut by any edge of the graph; can be exterior or interior ? Send packet around the face using right-hand rule ? Use position where face was entered and destination position to determine when face can be left again, switch back to greedy routing

     Requires: planar graph! (topology control can ensure that)


     GPSR ?C Example

     Route packet from node A to node Z

     Leave face routing

     E I





     Z A D J C G L

     Enter face routing


     Randomized forwarding ?C GeRaF

     Given a network with all nodes distributed uniformly ? Each node turns on or off at arbitrary times to save energy

     It is possible that some of the nodes are asleep while broadcasting

     Use polar coordinates from a center point ? Assign ??virtual angle range?? to neighbors of a node, bigger radius ? Angles are recursively redistributed to children nodes


     Geographic routing without positions ?C GEM

     Apparent contradiction: geographic, but no position? ? Construct virtual coordinates that preserve enough neighborhood information to be useful in geographic routing but do not require actual position determination ? Use polar coordinates from a center point ? Assign ??virtual angle range?? to neighbors of a node, bigger radius ? Angles are recursively redistributed to children nodes



     How to combine position knowledge with nodes turning on/off?

     Goal: Transmit message over multiple hops to destination node; deal with topology constantly changing because of on/off node

     Idea: Receiver-initiated forwarding

     Forwarding node S simply broadcasts a packet, without specifying next hop node ? Some node T will pick it up (ideally, closest to the source) and forward it

     Problem: How to deal with multiple forwarders?

     Position-informed randomization: The closer to the destination a forwarding node is, the shorter does it hesitate to forward packet ? Use several annuli to make problem easier, group nodes according to distance (collisions can still occur)


     GeRaF ?C Example

     A4 A3 A2 A1

Report this document

For any questions or suggestions please email