Wednesday, May 28, 2008

capacity of multihop networks...

We are interested in this as multihop networks may be built in an ad hoc way by consumers (same as P2P networks) and so the question is how much cpacity per user do you get as you scale up the number of users in a given area (or volume).

most useable radio frequencies mean we are not in near field (where there are really cool scaling results due to very fast fading) so as soon as you forward a signal more than one hop, you are causing interference with other nodes, and the question is
partly just geometric - increasing the number of nodes in a volume, with (say) a uniform random set of traffic between sources and destinations, the path length increases, so the number of hops that receive your signal (and therefore cannot receive someone else's signal) increases. However, the power needed to get the signal to a neighbour decreses (or the capacity increases at that shorter distance for the same power) - so there's a race between increasing capacity at each hop, and decreasign capacity because of the number of hops - the simplest answer is that the capacity of the system grows slower with N than the number of senders, so you get
a net that eventually has no capacity.

so there's a growing body of work on this topic - stemming, I guess, from the original work by Gupta/Kumar (1/srt(n ln (n)), then moving through the various modifications that allow for mobility (Grossglauser/Tse) (2 hop relaying has overall increasing capacity at expense of eventual diverging delay!), fading (various models, but typically still decreasing capacity with N), fading and mobility (has a worse lower bound than just mobility but better overall capacity in the system so growing with N), variable traffic demand (non uniform random traffic matrix, or multicast traffic).

All these are under the assumption of transmission on a "hop" being to one receiver, and all other senders to that receiver contributing noise, and all other receptions of that transmission being interference at other receivers. Of course, then one can add diversity (i.e. receive the signal from multiple diverse transmissions, and forward similarly) and there's constructive schemes for cooperative diversity (again due to Tse and others), which show you can increase the capacity again, including systems that have effectively fixed capacity per user no matter how many users, but require very good clock synch (well, perhaps similar to WCDMA).

so diversity is one trick - but I was wondering about _deliberate_ fading

can we take a simple 1D scheme with a set of nodes on a line at uniform (or random) distances from each other, and construct a transmission schedule where nodes relay in one direction in phase and nodes further "back" away from the forwarding path, re-relay out of phase. This is not quite the same as diversity - what we are trying to do is to build a "noise cancellor" from the previous hop to the current node. I have no idea if this is practical - but pretend the previous hop acts like a perfect radio mirror. we measure the distance between us and next hop, and previous hop and our next hop and any intermediate hops and we setup a reflection that is perfect multipath interference at the hops we dont want to receive our signal

Now re-do this in 2D (tricky) or 3D (trickier!)

problem (very bad) is that unlike diversity, this creates a massive growth in thermal (i.e. pure random) background...which will eventually swamp everything (except that it is also subject to some types of fading and path loss)...

No comments:

Blog Archive

About Me

My photo
misery me, there is a floccipaucinihilipilification (*) of chronsynclastic infundibuli in these parts and I must therefore refer you to frank zappa instead, and go home