Accurately Predicting Residual Energy Levels in MANETs

	Thomas Kunz
	Systems and Computer Engineering
	Carleton University

Outline

	Motivation
	OLSR and Our Modifications
	Initial Results
	Prediction Strategies
		Guessing
		Prediction
		Smart Prediction
	Prediction under Mobility and Heterogeneous Radios
	Conclusions and Future Work

Motivation

	QoS routing in MANETs
		Supports interesting applications
		Requires “accurate” state information
	Little work to quantify accuracy of state information
		QoS routing protocols exist
		State information aggregation discussed for LARGE wired networks, including loss of information (ATM, hierarchical networks, etc.)
		Some work on quantifying amount and accuracy of topology information
		Existing evidence seems to suggest that
			More accurate state information results in “better” routing decisions
			More accurate state information is difficult to collect
	We are interested in energy-efficient routing, a key piece of state information is the residual energy level of nodes

OLSR and Our Modification

	OLSR: uses MPRs to
		Efficiently propagate topology information
		Constrain routing to MPRs while guaranteeing shortest path -> only partial topology is known
	Two key protocol messages
		Hello: propagate 1-hop and 2-hop neighbor information, used to route to close neighbors and to select MPRs
		TC (topology control) messages: propagate partial topology information to all nodes, allows them to build a (partial) view of topology and determine shortest paths
	Modification:
		Piggyback nodal energy level onto Hello and TC messages, including a timestamp
		Nodes build a database for all known/reachable nodes and their known energy levels, based on most recent report
		Periodically report actual and perceived nodal energy levels

Initial Results

	All tests done with NS2 version 2.27 with OOLSR version 0.99.15
	Initial question: how accurate is the energy level information and do the OLSR protocol parameters (Hello interval, TC interval, MPR coverage, and TC redundancy) significantly impact the accuracy
		For example: decreasing TC interval should result in more frequent propagation of state information, but comes at a cost of increased control message traffic

Accuracy Matters

Inaccuracy Levels: Propagating Information through Periodic Control Packets (piggybacking it)

Inaccuracies Analysis (not in paper)

Prediction Strategy: Guessing (not in paper)

Increasing Accuracy: Predict

	Basic idea: adjust reported values by a consumption rate to predict current residual energy level (rather than using potentially “old” information) when making routing decisions
	How to derive “consumption rate”?
		Basic prediction: assume A learns that
			At time 4, B’s residual energy was 17
			At time 6, B’s residual energy was 13
			A calculates B’s consumption rate as 2/unit time, so at time 7, A will predict that B’s residual energy level is 11. Requires at least 2 successive reports
		Advanced prediction: enhanced basic prediction – in the absence of a second report, use average of all known consumption rates for adjustment

Prediction: Increases Overall Information Accuracy

Prediction and Smart Prediction: Mobility and Heterogeneous Radios (Different Power Characteristics)

Conclusions and Future Work

	Provided some empirical evidence on QoS state information inaccuracy under OLSR
	Initial results not too surprising, except that little control via OLSR protocol parameters
	Improvements in state information accuracy are possible
		Guessing was not a good idea J
		Prediction can be made to work for a metric like energy
		Mobility and/or heterogeneous radios increase inaccuracy, but smart prediction technique keeps overall inaccuracy level low
	Future Work
		How to apply similar ideas to other state information, for example Queue Length (used for load-balanced routing) or available link bandwidth?