2009/6/24 Rémi Villé <[email protected]> > 2009/6/24 Rémi Villé <[email protected]> > >> 2009/6/24 Rémi Villé <[email protected]> >> >> 2009/6/23 Omprakash Gnawali <[email protected]> >>> >>> On Thu, Jun 18, 2009 at 4:41 AM, Rémi Villé<[email protected]> wrote: >>>> > Hi, >>>> > >>>> > I would like to discuss about how the path cost is calculated from the >>>> cost >>>> > of its arcs. >>>> > Currently this path is accumulated with an addition. I think it's >>>> bizarre >>>> > because we try to create the best path in term of ratio (msg >>>> received/msf >>>> > sent). So the cost of a path should be proportional to the chance of a >>>> > packet to reach the sink through this path, i.e. 1/q(a,b)*q(b,c) for >>>> the >>>> > path (a,b,c), and not 1/q(a,b) + 1/q(b,c). (q = PRR(a,b)*PRR(b,a)). >>>> > >>>> > I tried to find incoherent cases with this accumulation and I found >>>> this one >>>> > : >>>> > 3 motes : a, b and c (a is the sink). >>>> > q(a,b) = 0.5 >>>> > q(b,c) = 0.2 >>>> > >>>> > The cost of (a,b,c) should be 1/(0.5*0.2) = 10, but the effective cost >>>> is >>>> > 1/0.5 + 1/0.2 = 7. (q(a,b,c) = 0.5*0.2 = 0.1). >>>> > If we have cost(a,c) = 8, then q(a,c) = 1/8 = 0.125. >>>> > We have q(a,c) best then q(a,b,c) but cost(a,c) > cost(a,b,c), and c >>>> choose >>>> > a bad best parent/path (the path (a,b,c) instead of (a,c)). >>>> > >>>> > If I take ETX instead of EETX (10/q) it doesn't change this reasoning. >>>> > >>>> > I would like to know if I miss something, maybe there's a good reson >>>> to use >>>> > the addition instead of multiplication to accumulate the cost path, I >>>> would >>>> > like to understand... >>>> >>>> This paper goes into the details of additive path cost: >>>> http://pdos.csail.mit.edu/papers/grid:mobicom03/paper.pdf >>>> >>>> ETX gives you the expected number of transmissions for a link. So, the >>>> path cost is the sum of these per-link costs. >>>> >>>> - om_p >>>> >>> >>> Thanks a lot, it's exactly the paper I was looking for. >>> >>> I have a maybe strange question, I would like to know the exact sense of >>> "expected" in ETX, because I don't speak english fluently. >>> In an wordReference dictionary it's translated by "wait for" or "hope". I >>> think it's more "estimated"... >>> >> >> I think I have understand my mistake, ETX is an estimation of the number >> of transmissions/retransmissions to deliver a packet. >> So if we have 1/2 chance a packet to be lost between a mote A and B, ETX >> should be 2 because we expected that we'll need two transmissions to deliver >> the message. >> And through a path (A,B,C) (with 1/2 chance between B and C too) we repeat >> this reasoning twice, so here, using addition has sense. >> >> I'll continue to read the paper. >> > > In the paper, authors say they use addition instead of product, because it > fails to account for inter-hop interference, I didn't know this sort of > interference, so I do agree. > Maybe I'm nit-picking, but with my example above (using the addition), the > path chosen is either the worst in term of end-to-end ratio and minimum hop > count. > > To find this sort of example I try to find paths with quality links that > check this inequality : > > cost(a,b,c,...,n) > cost(a,b) + cost(b,c) + ... + cost(n-1, n) + 1, where > cost(a,b,c,...,n) = 1/(q(a,b)*q(b,c)*...*q(n-1,n)) > Then I can find a path (a,n) with : > (1) : cost(a,n) < cost(a,b,c,...,n) > (2) : cost(a,n) > cost(a,b) + cost(b,c) + ... + cost(n-1, n) > > Which is non trivial (I just find some examples with 3 motes). > > I admit this problem begins to bore me, so I think I will leave it aside an > adopt the authors point of view (inter-hop interference). >
In fact this sort of incoherent path is negligible because it imply that paths (a,b,c) and (a,c) to be very bad, for longer paths it becomes unrealistic and it always concerns very bad links.
_______________________________________________ Tinyos-help mailing list [email protected] https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-help
