1	Energy-Efficient MANET Routing: Ideal vs. Realistic Performance Thomas Kunz Systems and Computer Engineering Carleton University
2	Overview of Presentation Motivation Brief Review of OLSR Modifications to OLSR Energy-Efficient Protocol Collect state information (residual nodal energy level) Simulation Results Conclusions
3	Motivation Wireless nodes are severely energy-constrained Typically operated using a battery of finite capacity Limited to no opportunity for energy scavenging Nodes in multihop wireless networks cooperate by routing packets Lots of research interest/proposed protocols, some standards approved by IETF (AODV, DSR, TBRPF, OLSR) Routing metrics: shortest hop (best effort), QoS routing (max throughput, min delay), load balanced routing, energy-efficient routing Sources of energy consumption Radio consumes bulk of energy (more than say CPU or disk) Radio: Transmit > Receive > Idle >> Sleep
4	Motivation (cont.) Energy-Efficient Routing Protocols: Range of energy metrics/routing objectives (some are contradictory): Maximize network lifetime (time until first node, 50% of nodes die) Minimize energy cost per packet (particularly for radios with power control) Balance residual nodal energy (allow all nodes to continue operation longer) Maximize “useful” work of network (i.e., send more packets before running out of energy, either at sender/receiver or intermediate nodes) Many different routing approaches Pro-active vs. reactive New protocols vs. extending standard protocols Existing energy-efficient protocols require a node to have state information (node’s residual energy level, etc.) No discussion of accuracy of collected information/impact on performance QoS routing: little work as well, some evidence that accuracy of information impacts quality of routing decisions and protocol overhead
5	OLSR: Optimized Link State Routing Pro-active protocol (i.e., nodes determine/maintain paths to all other nodes, through periodic exchange of control messages) Optimizes the link state flooding mechanism Multipoint Relay (MPR) nodes achieve the optimization A set of MPR nodes is chosen by each node in the network The node’s view of the topology becomes partial
6	MPR Selection Basis: periodic HELLO messages, that contain information about sender’s 1-hop neighbourhood à allows receiver to collect information about 2-hop neighbourhood Each node selects its own MPRs from its 1-hop symmetric neighbours Through the MPRs all symmetric strict 2-hop neighbours must be reached Recalculated when symmetric neighbourhoods change (1-hop or strict 2-hop)
7	MPR Selection (cont.) MPR set = Ø MPR += 1-hop neighbors with willingness=Will_always MPR += 1-hop neighbors that are the only ones reaching a 2-hops neighbor Remove the 2-hop neighbors reached by the MPRs Add 1-hop nodes (to the MPR set) providing maximum reachability of 2-hop neighbors UNTIL reaching all 2-hop neighbors.
8	Path Determination Information dissemination to construct routes Broadcast by MPRs only through periodic TC (Topology Control) messages, all nodes receive these messages and store the topology information Links between an MPR and its selector set (Advertised Neighbor set) are the minimum information that must be broadcast Run a Shortest Path algorithm on partial topology info to determine shortest hop path guaranteed to be not longer than minimum hop path in full network topology
9	Modifying OLSR to make it Energy-Efficient Two (obvious) choices for modifying OLSR routing decisions MPR Selection Path Determination Prior work: change one or the other (or both) to achieve QoS routing, etc. Typically: best results are achieved when both components are modified Our changes: modify both components as explained below, explore performance of all combinations MPR Selection: pick 1-hop neighbors with max residual energy level until all 2-hop neighbors are covered (note: may not result in minimum set of MPRs) Path determination: run Dijkstra, but assign weight to links based on receiving node’s reciprocal energy level (steers routes away from nodes with low energy level, avoids need for threshold) Prior results: best option is to only change Path Determination, second best often is to combine modified path determination with modified MPR Selection
10	Modifying OLSR to Propagate State Information Extend Hello and TC messages to include a node’s state information and a timestamp, in addition to a node’s address etc. Store this information in the relevant OLSR information bases (topology base, neighourhood base, etc.) Search through databases to determine most recent value every time a node’s residual energy level is needed Note: does not, per se, require nodes to be synchronized, as we only compare entries for the same node/clock. But if nodes were to be coarsely synchronized, we could then use this to reason about age of information as well…. Alternative using sequence numbers has similar overheads and would not allow reasoning about information age.
11	Simulation Setup (NS2 version 2.27 with OOLSR 0.99.15) Basically 4 Protocol Variations Protocol Variants: Modified Routing and Modified MPR/Routing Two versions each: Ideal (nodes have omniscent, accurate info about state information) and realistic (nodes learn about state information through control messages) Three mobility scenarios: static, low mobility, high mobility Traffic model: three CBR flows randomly chosen, senders send data at 4 different rates (low to overload traffic) Performance metric: number of data packets successfully delivered
12	Simulation Results: Static Scenarios
13	Simulation Results: Low Mobility Scenarios
14	Simulation Results: High Mobility Scenarios
15	Conclusions Accuracy of state information does matter Realistic versions always performed poorer than ideal versions of the same protocol variant Performance loss due to inaccurate state information can be as high as 10% Initially exploration: some of the state information is really old (in excess of 20 seconds) and therefore very inaccurate In particular under high traffic load: control messages sometimes get lost Future work Explore sources/reasons for inaccuracy in more depth Explore ways to increase accuracy Wicon 2007: paper on “smart prediction”, which works well for monotonic state information such as residual energy level Probing old information adds more control messages to the network and does not help