The Capacity of Wireless NetworksPiyush Gupta & P.R. KumarRahul Tandra --- EE228 PresentationIntroduction We consider wireless networks without any centralized control. Try to analyze the capacity of such networks. We consider two types of networks:a) Arbitrary networksb) Random networksArbitrary Networks ‘n’ nodes are arbitrarily located in a disc of unit area. Traffic pattern is completely arbitrary. Range or power level is also arbitrary. Two models for successful reception of a transmission over one hop:a) Protocol Modelb) Physical ModelThe protocol Model Suppose Xitransmits over the m-th sub-channel to a node Xj. This transmission is successfully received by node Xjif for every node Xksimultaneously transmitting over the same sub-channel. The quantity models situations where a guard zone is specified by the protocol.jijkXXXX −∆+≥− )1(0>∆The Physical Model Let be the subset of nodes simultaneously transmitting at some time instant over a certain sub-channel. Let Pkbe the power level chosen by node Xk. Then the transmission from a node Xiis successfully received by a node Xjif {}Τ∈kXk;βαα≥−+−∑≠Τ∈ikkjkkjiiXXPNXXPTransport Capacity of Arbitrary Networks We say that the network transports one bit-meter when one bit has been transported a distance of one meter towards it’s destination. This sum of products of bits and the distances over which they are carried is called the transport capacity of the network.Main Results for Arbitrary Networks Main Result 1: The transport Capacity of an Arbitrary Network under the protocol Model is bit-meters/sec if the nodes are optimally placed, the traffic pattern and the range are optimally chosen. If the transport capacity is equitably divided between all the n nodes, then each node would obtain bit-meters/sec. Further if, each node has its destination about the same distance of 1 meter away, then each node would obtain a throughput capacity of bits/sec.)( nWΘ)(nWΘ)(nWΘResults cont. Main Result 2: For the Physical Model, bit-meters/sec is feasible, whilebit-meters/sec is not, for appropriate constants c and c’.ncWαα1'−WncArbitrary Networks: An upper bound on transport capacityWe consider the setting on a planar disk of unit area with the following assumptions:(A1) There are ‘n’ nodes arbitrarily located indisk of unit area on the plane.(A2) The network transports bits over T seconds.(A3) The average distance between the sourceand the destination is .nTλLAssumptions cont.(A4) Each node can transmit over any subset ofM sub-channels with capacities Wmbits/sec, , where .(A5) Transmissions are slotted into synchronized slots of length .Mm ≤≤1WWMmm=∑=1τUpper bound for the Transport Capacity Theorem 1: In the Protocol model the transport capacity is bounded as follows:bit-meters/secnWLn∆≤18πλLower bound on the Transport Capacity Theorem 2: There is a placement of nodes and an assignment of traffic patterns such that the network can achievebit-meters/sec under the Protocol Model.π821+∆+nnWRandom Networks ‘n’ nodes are randomly, i.e., independently and uniformly located on the surface of a sphere of surface area 1 sq. meter. Each node randomly chooses a destination to transmit. The destination node is independently chosen to be the node nearest to this randomly located point. Also, we assume that all nodes are homogeneous ( same power or range).The Protocol Model All nodes employ a common range ‘r’ for transmission. When node Xitransmits to node Xj, the transmission is successfully received by Xjif:(i) (ii) For every other node Xktransmitting over the same sub-channelrXXji≤−rXXjk)1( ∆+≥−The Physical Model All nodes choose a common power level ‘P’ for transmission. Let be the subset of nodes simultaneously transmitting at some time instant over a certain sub-channel. Then the transmission from a node Xiis successfully received by a node Xjif {}Τ∈kXk;βαα≥−+−∑≠Τ∈ikkjkjiXXPNXXPThe Throughput Capacity of Random Networks Main Result 3: The order of the throughput capacity for the Protocol model is bits/sec Main Result 4: For the Physical Model a Throughput Capacity of bits/sec is feasible, while bits/sec is not for appropriate constants ‘c’ and c’Θ=nnWnlog)(λnncWnlog)( =λnWcn')( =λOutline of the Proof We use Voronoi tessellation on the surface S2of the sphere. Let {a1,a2,…,ap} be a set of ‘p’ points on S2. The Voronoi cell V(ai) is the set of point which are closer to aithan to any of the other aj’s. Note that the distances are measured on the surface of S2by segments of great circles connection two points. Lemma 1: For ever > 0, there is a Voronoi tessellation of S2with the property that every Voronoi cell contains a disk of radius and is contained in a disk of radius 2 . In the rest of the proof we will use a Voronoi tessellation Vnfor which:(a) Every Voronoi cell contains a disk of area (100logn)/n. Let be the radius of this disk.(b) Every Voronoi cell is contained in a disk of radius 2εεε)(nρ)(nρAdjacency and interference We say that two cells are adjacent, if they share a common point. Let us choose the range r(n) of each transmission so that Lemma 2: Every node in a cell is within a distance of r(n) from every node in its own cell or adjacent cell. We say that two cells are interfering neighbors if there is a point in one cell which is within a distance of some point in the other cell.)(8)( nnrρ=)()2( nr∆+Bound on the number of interfering neighbors of a cell Lemma 3: Every cell in Vnhas no more than c1interfering neighbors. c1depends only on and grows no faster than linearly in Lemma 4: In the Protocol model there is a schedule for transmitting packets such that in every (1+c1) slots, each cell in the tessellation Vngets one slot in which to transmit, and such that all transmissions are successfully received within a distance of r(n) from their transmitters.∆2)1( ∆+The source-destination Pairs Each node wishes to communicate with the node nearest to a randomly chosen location. Let Yibe a randomly chosen location such that Xiand Yiare independently and uniformly distributed on S2, and the
View Full Document
Unlocking...