Monday, June 4, 2007

Capacity of ad hoc networks

Unlike the conventional cellular networks with single hopping from every terminal to
the base station, traffic in ad hoc networks may be relayed via intermediate nodes to the distant destination. The advantage of this multi-hop communication scheme is: the required transmission power can be reduced exponentially with shortened transmission distance, and more concurrent transmissions may be available in the whole network because of spatial reuse of the resource, such as frequency or channelizing codes. However, it is very difficult to achieve the best of both worlds. With shortened transmission link, the number of hops from the source to the destination increases too. Partial system bandwidth must be used to deliver those relayed traffic. On the other hand, more concurrent transmissions result in increased number of interferers. Therefore, one of the fundamental challenges in ad hoc network research is what capacity can be achieved and how to achieve it.

Capacity of a network means the theoretical bounds on the performance under perfect network operation. Generally speaking, capacity or throughput analysis of wireless ad hoc networks may be explored in the following three ways:

1) The first solution is to find the exact capacity region (defined as closure set of feasible rates) in the perspective of information theory as in the conventional cellular network.

However, it is very difficult to obtain the exact capacity region because multiple nodes in the network can cooperate in very complicated and sophisticated ways. As an example, even the capacity of the simplest relay channel, which consists of just three nodes, a source, a relay and a destination, is not fully solved yet.

Recently, a breakthrough on the network information theory was obtained in [Xie 04]. With the assistance of the Max-Flow Min-Cut lemma, the authors indicate that the network capacity is always upper bounded by sum of total power used by the transmissions of all the nodes in the network.

2) The second method is to study the long term available throughput coarsely, e.g. analyzing the asymptotic capacity and scaling law with respect to the network size.

This method recently gained much attention, although it is coarser than the first one. The well-known result is given by [Gupta 00], who demonstrates that capacity per user goes to zero as the number of the nodes per unit area goes to infinity. This is a pessimistic result, because it means large ad hoc network’s capacity is poor.

After Gupta’s work, many people engaged in the ad hoc network capacity and tried to find a better solution. One important paper is the one written by Grossglauser and David Tse in 2002. The policy is, introduce the mobility of nodes into traffic transmission. Source node will first transfer to near relays, and those relays will not transmit to desired destinations until they move close. The throughput can be increased to the order of N, but the delay is too high.

Recently an interesting paper [Jafar-tit05] shows that too much mobility may limit the capacity of ad hoc networks. His argument is when mobility is too high, the node cannot track the channel in time to get the instantaneous CSI, then makes it difficult to distinguish between nearest neighbors and distant nodes at each moment.

3) The third one is measuring the practical throughput under some specific configurations by numerical simulation.

Many great simulation platforms have been developed for this purpose and a lot of research work can be found in this area. Some well-known examples are Network Simulator 2 (NS2), OPNet, QualNet (commercial version of Glomosim) etc.

NS2 is free to use, but OPNet and QualNet require licenses. I used NS2 for about more than one year. The learning curve is a little bit long. If you just want to use existing funcational modules to run simulation, it's not too hard. You can use TCL/OTCL to set up environment and parameters. If you want to modify the existing modules or add something new, you have to know how to interface TCL/OTCL with C++, because the kernel of NS2 is programed in C++.

However, when I used it, the version 2.28 has a problem in the interference and noise calculation in the physical layer: the SNIR (Signal to Noise and Interference ratio) is not recalculated every time the interference changes. A paper given by Mineo Takai addressed this problem in depth. Fading channel was not supported either. Someone made an extension with Rayleigh and Ricean fading but it only worked with old version. Fortunately, I found a solution by modifying some lines of the source code. Moreover, a difficult thing is how to compare your results with other guys'. Especially when you modified the program, no one knows if your modification can be justified (I think most of the simulators have the similar problem, but commercial platforms may be better because they keep the consistency well). So finally I abandoned it.


Anonymous said... is very informative. The article is very professionally written. I enjoy reading every day.
calgary payday loan
online payday loans canada

Anonymous said...

Can anyone recommend the top performing Script Deployment utility for a small IT service company like mine? Does anyone use or How do they compare to these guys I found recently: N-able N-central system management
? What is your best take in cost vs performance among those three? I need a good advice please... Thanks in advance!

Anonymous said...

Keep this going please, great job!

my web page; job online search

Anonymous said...

Thanks for sharing your thoughts about good online casinos.

Also visit my web-site :: real money slot machines