Energy-Efficient MANET Routing:
Ideal vs. Realistic Performance

Thomas Kunz

Systems and Computer Engineering

Carleton University

Overview of Presentation

Motivation

Brief Review of OLSR

Modifications to OLSR

Energy-Efficient Protocol

Collect state information (residual nodal energy level)

Simulation Results

Conclusions

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

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

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

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)

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.

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

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

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.

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

Simulation Results: Static Scenarios

Simulation Results: Low Mobility Scenarios

Simulation Results: High Mobility Scenarios

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


	Thomas Kunz
	Systems and Computer Engineering
	Carleton University


	Motivation
	Brief Review of OLSR
	Modifications to OLSR
		Energy-Efficient Protocol
		Collect state information (residual nodal energy level)
	Simulation Results
	Conclusions


	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


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


	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


	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)


	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.


	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


	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


	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.


	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


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