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).
_______________________________________________ Tinyos-help mailing list [email protected] https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-help
