[Tinyos-help] Cycle detection in multihoplqi (surge) for tinyos-1.x

[Philip Levis]

On Sep 11, 2007, at 12:11 AM, Paolo Masci wrote:

> Hi guys,
>
> Thanks for the replies. I agree with you on the fact that
> the routing tables are correct, i.e.
> * the end-to-end link quality embeds the concept of distance
> * routes have a cost that monotonically decreases
>   as the packet moves towards the base station.
>
> Nevertheless, the implementation of RouteSelect.selectRoute(..)
> still doesn't fully convince me: shouldn't we check that
> the packet is actually decreasing the cost while it is
> being forwarded? Both MintRoute and the old routing
> algorithm (tos/lib/Route) included this check.
>
> We know that routes have a cost that decreases when the
> packet gets closer to the sink, but routes can change
> while a packet is already being forwarded, and there
> is no relation (I guess) between the cost of different
> routes for different time instants.
> For example, consider the following:
> * suppose that node n0 sends a packet through
>   the path p0 = n1.n2...nx... with minimum cost
> * suppose that there is a route update while the packet
>   is being forwarded, and that node nx decides to change
>   parent and selects a new route with minimum cost
>   px = ny.nz....
> Although we know that px has a decreasing cost, we are
> missing the relation with the previous path p0, and
> the new path px may include some nodes of path p0, as well.
>
> What do you think about this?

Yes, MultihopLQI can have transient loops. I think it hopes that its  
duplicate detection will drop packets in them, and the parent  
selection algorithm will finally figure things out. MLQI greatly  
prefers links that have very high channel quality (and are therefore  
reasonably stable).

Phil