[Tinyos-devel] Metrics for Link quality

[Philip Levis]

On Dec 27, 2007, at 6:18 AM, Michael Newman wrote:

> 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.

You're right on the nose.

Generally, protocols today tend to use ETX, estimated transmissions,  
which is the inverse of the PRR. It has the nice property that you  
can measure it for links yet easily compose it additively for routes.  
ETX tends to be insufficient when you have variable bit rates (e.g.,  
802.11b), where instead ETT, estimated time of transmission, is better.

Take a look at the recent HotNets paper entitled "Four Bit Wireless  
Link Estimation." It talks about how CTP measures ETX. Just counting  
acks is not necessarily sufficient, as you need a way to bootstrap  
the network and detect neighbors (your heartbeat messages). The neat  
thing about 4B is that it unifies broadcast based ETX (slow, not very  
accurate, but cheap) with data-driven unicast ETX (fast, accurate,  
but requires unicast data packets).

Phil