1	Accurately Predicting Residual Energy Levels in MANETs Thomas Kunz Systems and Computer Engineering Carleton University
2	Outline Motivation OLSR and Our Modifications Initial Results Prediction Strategies Guessing Prediction Smart Prediction Prediction under Mobility and Heterogeneous Radios Conclusions and Future Work
3	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
4	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
5	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
6	Accuracy Matters
7	Inaccuracy Levels: Propagating Information through Periodic Control Packets (piggybacking it)
8	Inaccuracies Analysis (not in paper)
9	Prediction Strategy: Guessing (not in paper)
10	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
11	Prediction: Increases Overall Information Accuracy
12	Prediction and Smart Prediction: Mobility and Heterogeneous Radios (Different Power Characteristics)
13	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?