Last year, I was investigating the scaling laws of ad hoc wireless networks, that is how different parameters, mainly throughput and end-to-end delay scale (asymptotically) with the number of nodes in the network. I've already written a very brief description of the mathematical model, the problem statement and the design challenges here.

Moving on with ad hoc wireless networks, I am currently investigating, along with another student and two faculty professors at UT, how network coding can improve (if it does) the throughput (or decrease delay) of a given ad hoc wireless network. Our research is supported by Cisco. If you haven't heard of the term "network coding before", here's a very simplistic example to illustrate the concept. Say you have two wireless nodes A and B and a wireless router R as shown in the configuration below:

Let's assume that A and B each has a package to transmit to the other, and that each transmission must happen through the router R, i.e. there's no direct channel between A and B. The trivial solution would require 4 transmissions:

1. A sends a message to R.
2. R forwards the message to B.
3. B sends a message to R.
4. R forwards it to A.

But with network coding, one can achieve the same result in 3 transmissions. Can you find a way to do so? I'll give you some time to think about it and will post the solution later as a comment. Feel free to post your guesses as comments below. [Hint: The solution is simple.]

Although the example above demonstrates the key idea of network coding, the setting itself is very unrealistic. In an actual ad hoc wireless network, we have much more than two nodes and one router. As interference comes into play, it's not obvious how to extend the solution that works for few nodes efficiently to one that works for hundreds or thousands of nodes. Moreover, the network topology can be very complicated (in the above example, it's a simple linear chain) which significantly increases the complexity of the problem. Finally, in an ad hoc network, there are no routers but rather other nodes that act as routers. This tremendously increase the number of possible routing schemes as the number of nodes in the network increases. Depending on the network topology, optimizing over all possible routing schemes can be very challenging.

- Rayyan