Performance Evaluation of Opportunistic Routing Protocols: A Framework-based Approach using OMNeT++

Performance Evaluation of Opportunistic Routing Protocols: A Framework-based Approach using OMNeT++

• 1.
  IFIP/ACM LANC 2012 7thLatin American Networking Conference Performance Evaluation of Opportunistic Routing Protocols: A Framework-based Approach using OMNeT++ Zhongliang Zhao, Björn Mosler, Torsten Braun Universität Bern, Switzerland braun@iam.unibe.ch, cds.unibe.ch
• 2.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Overview > Opportunistic Routing Protocols — Extreme Opportunistic Routing (ExOR) — MAC-independent Opportunistic Routing and Encoding (MORE) > Optimized Link State Routing (OLSR) > Simulation Framework for Opportunistic Routing Protocols — Common Functionalities of Simulation Framework > Evaluation — Simulation Setup — Throughput Dependent on Channel Rate — Impact of Node Density — Impact of Number of Disjoint Routes — Encountered Collisions — Throughput for Different Transmission Rates — Batch Transmission Delay for Different Channel Quality > Conclusions Medellin, October 4, 2012 2
• 3.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Opportunistic Routing Protocols > make of use broadcast nature of wireless communications > target transient nature of wireless channel and node mobility > Basic operation — Sender/forwarder does not select a next node, but a list of candidate forwarders. — Only one node will forward the packet based on current channel conditions and node availability. > Examples — ExOR — MORE Medellin, October 4, 2012 3
• 4.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols ExOR > ExOR operates on batches of packets > Source node includes in each packet a list of candidate forwarders prioritized by closeness (according to a cost metric, e.g., expected number of transmissions) to the destination. > Receiving nodes buffer correctly received packets and await end of batch. > Highest priority forwarder broadcasts buffered packets, including its copy of the ―batch map‖ in each packet. Batch map contains the sender's best guess of the highest priority node to have received each packet. > Remaining forwarders transmit in order, but only send packets that were not acknowledged in the batch maps of higher priority nodes. > Forwarders continue to cycle through the priority list until 90 % of the packets have been received. > Remaining packets are transferred with traditional routing. Medellin, October 4, 2012 4
• 5.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols MAC-independent Opportunistic Routing and Encoding (MORE) > MORE integrates opportunistic routing and intra-flow network coding. > Random mixing packets before forwarding ensures that routers hearing the same transmission do not forward the same packets. > Source — When ready to send, source keeps creating coded packets using a random linear combination of K native packets in the current batch. — Source proceeds with next batch when acknowledged by destination.. — Data packets are always coded and carry a list of forwarders / code vector. > Forwarder — If a node is in the forwarder list, the arrival of an innovative packet triggers broadcasting the packet by creating a new random linear combination > Destination — Once destination receives K innovative packets, it decodes the whole batch and sends an ACK back to the source. Medellin, October 4, 2012 5
• 6.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Optimized Link State Routing (OLSR) > Broadcast of link state information > Forwarding of broadcast messages by nodes in set of Multi-Point Relays (MPR) > Each node computes its MPRs. This allows to reach each hop in 2-hop-neighborhood (learning of 2-hop- neighborhood by Hello messages). Algorithm: — N1/2: set of 1/2-hop-neighbors — Selection of nodes in N1 that are the only neighbors in N1 of a node in N2. — Assignment of a degree for each node in N1: number of nodes not yet covered in N2 — Selection of nodes in N1 with highest degree until all nodes in N2 are covered. > Hello messages indicate asymmetry of links. > MPRs distribute Link State messages. MPR indicates nodes that selected itself as MPR (MPR selectors) > Proactive / periodic exchange of MPR selectors in Topology Control messages > Establishment of routing entries for each node in the network using Dijkstra‗s Shortest Path algorithm Medellin, October 4, 2012 6
• 7.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols OMNeT++ based Simulation Framework for Opportunistic Routing Protocols > Class hierarchy built on assumption that all opportunistic routing protocols share certain functionalities > Common procedures (virtual functions) — Opportunistic Candidate Selection – Sending node periodically polls neighbor nodes within its radio range. – Adoption of certain attributes, e.g., geographic region or movement values — Forwarder Selection – defines rules how the actual forwarding node is picked from candidate set. — Forwarder Role Change Notification – enables winning forwarder to announce its new role and responsibility to neighboring nodes and to make them aware of the selection winner. — Collision Avoidance – is about how the nodes coordinate with each other to avoid collisions. Medellin, October 4, 2012 7
• 8.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Common Functionalities of Simulation Framework > Neighbour Discovery & Management — important for forwarder selection — adopted from INETMANET > Packet Buffer Management — Related data structures and corresponding operation for nodes store and manipulate received packets > Transmission Reliability Control — INETMANET includes several channel propagation models — INETMANET link layer implementation is adapted to control packet transmission. > Node Interface Management — Nodes inside the network may be equipped with more than one antenna/interfaces to increase network throughput. — Management for multiple interfaces necessary to support multi-channel communication. > ETX/EAX Calculation and Distribution — Candidate selection is usually based on determining a forwarder priority list based on ETX/EAX values. Medellin, October 4, 2012 8
• 9.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Simulation Setup > Additional parameters — 32 packets per batch, 1024 bytes packet size — 20 simulation runs Medellin, October 4, 2012 9
• 10.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Throughput Dependent on Channel Rate Medellin, October 4, 2012 10
• 11.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Impact of Node Density Medellin, October 4, 2012 11
• 12.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Impact of Number of Disjoint Routes Medellin, October 4, 2012 12
• 13.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Encountered Collisions Medellin, October 4, 2012 13
• 14.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Throughput of ExOR and OLSR for Different Channel Qualities Medellin, October 4, 2012 14
• 15.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Batch Transmission Delay of ExOR and OLSR for Different Channel Qualities Medellin, October 4, 2012 15
• 16.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Conclusions > Framework implemented in OMNeT++ simulator — facilitates the implementation of opportunistic routing protocols. — decouples opportunistic routing into four general steps and abstracts them as virtual functions. — provides some other functions shared by most opportunistic routing protocols — has been used for evaluations of MORE and ExOR and comparison with OLSR > Obtained Results — Earlier related work reported that opportunistic routing makes sense under low traffic scenarios (inter-packet gap > 1 s). This does not hold for ExOR and MORE, since batch transmission sends packets continuously without any delay. — Opportunistic routing may achieve significant performance gain in a lossy wireless environment and it will reach an improvement for high channel transmission rate scenarios. — Number of potential forwarders has strong influence on performance. A large number of potential forwarders may introduce collisions that will eliminate the benefits it introduces. Medellin, October 4, 2012 16
• 17.
  Torsten Braun: PerformanceEvaluation of Opportunistic Routing Protocols Thanks for Your Attention ! > braun@iam.unibe.ch > http://cds.unibe.ch Medellin, October 4, 2012 17