22-08-2013, 02:09 PM
Capacity of Large Networks with Immobile Nodes
Capacity of Large .pdf (Size: 386.76 KB / Downloads: 13)
Why knowing the capacity is important
• Capacity: theoretical bounds on the performance, under perfect node
coordination
• If we know the capacity of the network, we have an objective measure of
how good are our protocols.
– We just compare the capacity with the performance of our protocols.
– This can lead to big surprises [1].
• In the process of finding the capacity, we also gain intuition about
– how our protocols can achieve it.
– what are the fundamental limitations of the network.
• Parallelism: we want to know the capacity of ad hoc networks for the
same reasons we want to know the Shannon capacity of channels.
Information Theoretic Capacity
• We are given a communication channel (typically in terms of a conditional
probability distribution p(x|y)).
• The capacity is the maximum amount of information that can be
transmitted through the channel.
• No constraints are placed on the modulation used, the complexity of the
transceivers, etc.
• As an example, the channel below has a capacity C = W log2(1 + ηW
Erlang Capacity
• Consider a communications system.
– A cellular CDMA system.
– An M/M/m queue.
• Erlang capacity is the maximum traffic load such that the performance
is satisfactory (according to some metric).
• Examples:
– In a cellular CDMA system, the Erlang capacity could be the maximum
traffic load so that blocking probability is below a certain value [5].
– In a M/M/m queue, the Erlang capacity could be the maximum traffic
load so that the expected delay is less than some value [6].
Finding the capacity region is a very hard problem
• At any given time, the network can be in a huge number of states:
Each node has many neighbors to which it may transmit.
It may have many packets awaiting transmission.
It may have many modulation scheme to choose from.
The channel may be in any of a large number of states (due to fading
and/or mobility), etc.
• To find if a point belongs to the capacity region, we need to find if these
(practically infinite) states can be combined in a way that will achieve
the point.
• Various attempts exist [9, 10, 11, 12].
– None of them is provides an easy solution.
– [12] in particular is a classic reference that introduces the brilliant idea
of ”back pressure”.