The Anti-Packets Can Increase the Achievable Throughput of a Wireless Multi-Hop Network, by Petar Popovski and Hiroyuki Yomo, of Aalborg University, ICC'06.
The idea is very simple, and it is one of the few applications that I have seen of the field of network coding, which may actually work. Surprisingly enough, the authors don't seem to know what network coding is. At least, they don't mention it.
This paper came at about the same time as the COPE paper from Dina Katabi's group at MIT which presents the same idea with a slightly different approach (COPE is more general). I would guess that, due to the MIT reputation and the publication forum, the citation count for COPE will outnumber the number of citations for this paper by a factor 100, even though both had the same idea at about the same time.
Assume a multi-hop wireless network with 3 nodes, A, B and C. A needs to send a packet AC to C, and C a packet CA to A (both packets of same length and errorless transmissions). The current way of doing it is in 4 time slot: 1-AC from A to B; 2-CA from C to B; 3-AC from B to C; 4-CA from B to A.
The idea of the paper is to combine 3 and 4, and to use the fact that since A and C both hear B, the last step can be: 3-B transmits ACA = XOR(AC,CA) to both B and A.
A, using ACA and AC, can recover CA, and similarly C can recover AC. The gain in bandwidth is 33%.
The throughput can be doubled in an analog manner: if A and C transmit at the same time (slot 1), then B hears a signal composed of both A and C components, A+C. Assuming B hears them both with the same power, then it can just replay the signal it heared in slot 1 in slot 2. It acts only as an amplificator. A hears A+C and can substract its own component to recover the packet from C, and C similarly. Bandwidth gain is 100%.
There are a lot of implementation issues and assumptions that should be debated (it requires symmetric traffic from A to C and C to A, at least bit-wise; synchronization; error recovery mechanisms look more complicated; etc) but the main idea is quite sexy.
Subscribe to:
Post Comments (Atom)
5 comments:
I guess you forgot to mention 'Coded Bi-Directional Relaying' by Peter Larsson, Niklas Johansson and Kai-Erik Sunell, which appeared before both of the papers you mentioned
I don't know that paper, but I'll look it up.
I just finished reading 'Anti-packets...', and they actually reference the paper I just mentioned. Actually, they reference the slides of a presentation that this paper was based on. But in the end, both of these papers got their basic idea from 'Information Exchange in Wireless Networks with Network Coding and Physical layer Broadcast' which paved the way for the first 'practical' implementation of network coding for wireless applications.
Thanks for the pointer. I did not know about that one either.
To avoid further speculation...
Well, actually the CBR idea (as well as the NC-multihop idea) arose at end march 2004 when I had the pleasure to listend to an excellent talk given by Ken Zeger at UCSD on Network coding, (Roughly on the topic "Linear NC is not always enough", which specifically dealt with fixed wired, and fairly complex, multicast networks).
Extension to the bi-directional wireless topology was quite natural due to some previous work I've done on linear interference cancellation for bi-directional relaying in 2001.
BR,
PL
Post a Comment