[Tinyos-devel] Metrics for Link quality

[Michael Newman]

I am throwing out this idea and experience in the hope that we don't spend
too much effort studying what I think is a poor way of establishing routing
and link metrics.
 
There has been a lot of discussion of late on using various metrics for link
quality. The metrics often measure signal strength and in past experiments I
have found that these metrics (RSSI and the CC2420 LQI) are poor predictors
of the likelihood that a message will get through. In careful experiments we
saw links with low metrics have excellent reliability and links with
excellent metrics work poorly.
 
Since the likelihood that a message gets through is what you really care
about the fact that the metrics were a poor predictor was a problem.
 
We decided to implement scoring that was based on actual message
reliability. We wanted to use little memory and kept scores for only 5
neighboring nodes. During network formation when a node was detected several
messages were sent and a record of the fraction that got ACKs was kept. When
a newly observed node was better than one of the 5 in the list the worse
node was replaced. After network formation two paths to the message sink
were used and a continuous record of how reliable the links operated was
kept. The best route was used for data and the less reliable route only for
heartbeats that kept it available as a backup route. When one of the two was
lost it got replaced by listening for a new neighbor and polling the link
quality again.
 
We measured how quickly the network formed and became a reliable message
transport. Using the message success rate turned out to be much better than
using the other link quality metrics. 
 
A nice side effect of using message success statistics is that it allows
direct estimates of path reliability to be computed and used for routing
strategy. The path computation was nice because it gave a good way to decide
how to gradually change the routing over time. It the path probability of
success was above a threshold it was simply used. If the reliability
diminished a new path with better predicted reliability could be sought.
Shorter paths were properly favored only if the path reliability justified
it. 
 
I hope this concept helps.
 
  _____  


Michael Newman

Dragonnorth Group


319 Dean Rd.
Brookline, MA 02445

Cell: 617 821-4608
Home: 617 566-7975
Fax: 617 566-7975


www.dragonnorth.com <http://www.dragonnorth.com/> 

mnewman at dragonnorth.com

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/tinyos-devel/attachments/20071227/f1afa736/attachment.html