Bonafide certificate

2.8ACHIEVABLE BANDWIDTH ESTIMATION

The above estimate of the time available for each link can be converted into available rate of the link in bps.

Available Bandwidth = ATP*Channel bandwidth. – (6)
This gives an estimate of available bandwidth / capacity in a link under saturation condition. However this estimate is only probabilistic without considering all the protocol characteristics. One of the main aspects of IEEE 802.11 protocol is the BEB. The delay in accessing the channel is dependent on the load or contention in the local neighborhood. By taking this into account, our bandwidth estimate becomes improved. We accommodate this into our estimation method by measuring the loss rate in the local neighborhood. This loss rate is a measure of both packet losses due to contention collision and channel errors. Loss rate is expected to follow a time series pattern. We use the loss rate measurement to obtain the achievable bandwidth of a link. Loss rate given by the number of bits lost per second is observed and periodically updated for every update period using exponential weighed average method given by eqn (7).
l_new-average = (1- )l_current + l _previous ----- (7 )
We adopt the parameters for  as 0.75 and 1 second as update period in our simulation. The value of  chosen helps in removing the short term fluctuation and reflects long-term trend. Since this estimate is made per link, losses per link are appropriately captured. Now the achievable bandwidth is given by
Achievable Bandwidth = Available Bandwidth(1 – Loss Rate). ----- (8)

The results for centralized and distributed estimations are discussed in chapter 4.

CHAPTER 3

ANALYTICAL MODELING OF MULTI-HOP NETWORKS

3.1 MOTIVATION

In the IEEE 802.11 standard based MAC protocol, channel as a common resource is shared among contending nodes using a distributed and random scheme. Each node competes with all other nodes in its neighborhood. In the previous section, the link capacity problem was solved from the node perspective since links become active only when one of the nodes it is attached to becomes active. In this section, a node’s transmission probability is calculated using the analytical model developed for channel and node. Once this is obtained, a link’s probability of being active can be easily found out. This is a more accurate way of characterizing a link’s capacity in a system where the channel access mechanism uses a random procedure.

3.1.1Characteristics of the IEEE 802.11 based Multi-hop Networks

In the IEEE 802.11 standard based multi-hop network, neighborhood of each node is different. Hence the probablity of each node accessing the channel is affected differently depending on the node distribution around it. Each neighboring node would affect a node’s channel access probability to a different degree. We can represent this with a circle around a node that includes the nodes that compete with this each affecting the node’s time for channel access to a different degree.

Apart from the neighborhood contention of nodes, a node’s channel access is affected by constraints imposed by the medium access protocol, the IEEE 802.11 DCF in this case. We use the model developed by Wang and Acves (2004) as a basis for multi-hop networks using CSMA/CA to derive the node transmission probabilities for IEEE 802.11 networks. While the work assumes a two-dimensional poisson node distribution, we assume node distributions of string and grid topologies.

3.2 PROTOCOL MODEL AND ASSUMPTIONS

We make the following assumptions for the sake of simplicity and without loss of generality

• 
  Each node has the same transmission and receiving range ‘R’.
  
• 
  Heavy traffic assumption : A node always has a packet in its buffer to be sent and that traffic is distributed equally to its neighbors.
  
• 
  To simplify our analysis, we assume that nodes operate in time slotted mode, where length of a time slot ‘τ’ equals one propagation delay, overhead due to the transmit-to –receive turn around time, carrier sensing delay and processing delay.
  
• 
  We assume that a node is ready to transmit with probability ‘p’ and not ready with probability ‘1-p’. p is a slot-independent, protocol specific parameter. However at the level of individual nodes, the probability of being ready to transmit varies for each time slot depending on the current state of the channel and the node. Hence we are interested in calculating the probability that a node transmits in a time slot denoted by p’.
  

p’ = p. P{Channel is sensed idle in a slot } =

= p.П_l. ----- (9)

where П_l denotes the limiting probability that the channel is in idle state.

3.3 CHANNEL MODEL

The DCF access procedure of the IEEE 802.11 standard requires a node to do most or all of the following before transmitting a packet onto the common ‘Channel’. They include carrier sensing, wait for inter frame space time, backoff. Hence even when a node is ready to transmit, it may or may not transmit in a slot depending on the state of a channel, the node’s neighborhood and the constraints imposed by the MAC protocol. To model this, we use the Markov model to capture the effect of channel on a node.

The channel around each node is modeled as a circular region with some more nodes. It is assumed that nodes within the region can communicate with each other while they have weak interactions with nodes outside the region. The model is simplified by considering weak interactions where the decision of inner nodes to transmit, defer and backoff is almost not affected by that of outer nodes and vice-versa.
With the above assumptions, the channel is modeled as a four-state Markov chain as in Wang and Aceves (2004) with the following states.

Fig 6 Channel moled for IEEE 802.11 MAC

Idle : is the state when the channel around the node x is sense idle, its duration is ‘τ’. This denotes the state where there is no transmission.
Long is the state when a successful four-way handshake is initiated in the channel by some other node.

Tlong = l_rts + τ + l_cts + τ + l_data + τ + l_ack

= l_rts + l_cts + l_data + l_ack + 3τ.

where l_rts, l_cts, l_data and l_ack represent the length of rts, cts, data and ack packets.

Short 1 is the state when multiple nodes around the channel transmit RTS packets during the same time slot and their transmissions collide. The busy time of the channel in this state is T_short1.

T_short1 = l_rts + τ.

Short 2 is the state when one node around the channel initiates a failed handshake with a node outside the region. Even though CTS packet may not be sent due to collision at or deferral of the receiving node, those nodes that overhear the RTS as well as the sending nodes do not know if the handshake is successfully continued, until the time required for receiving a CTS packet elapses. Since the channel is in effect unusable for that period, for all the nodes sharing the channel, the duration of this state is

T_short2 = l_rts + τ + l_cts + τ

= l_rts + l_cts + 2 τ.
Using the channel model, steady state probabilities of channel being idle can be derived for string and grid topologies. The derivation applied to the centre nodes of string and grid networks since for a string and grid network with large number of nodes, the edge nodes can be neglected without loss of generality. Also the Markov chain can be solved easily when the number of neighbors are fixed. Expressions for edge nodes can be derived similarly.
First the transition probabilities of the channel Markov chain for string network is calculated. The transition probabilities from any other state to idle is one since before the start of any other transmission, the channel stays in idle state at least for τ seconds.
P_ii is the transition probability from idle to idle state of channel. A node ‘x’ in the middle of the string network, has two immediate neighbors. Since the node x senses the channel to be busy even when the two immediate neighbors receive packets from their neighbors, transmissions from their neighbors to this node is also considered Since all these nodes are assumed to be in the centre of the network, p’ is same for all these nodes.

P_ii= (1- p´)⁴ ---- (10)

P_il is the transition prob. from idle to long state. For the node x to be observe a successful packet transmission in the channel, only one neighboring node of x should be involved in a successful transmission.

P_il = 2p_s (1- p´). ----- (11)

where p_s denotes the probability that a node begins a successful four-way handshake. It is not known yet and will be derived

The transition probability, P_is1 from idle to short1 state is the probability that more than one node transmit RTS packets in the same slots. In our case, its is just the probability that both the neighbors of node x transmit simultaneously, given by,

P_is1 = p´ ². ----- (12)

Now with these probabilities known, we can calculate the transition probability from idle to short2 state, P_is2.

P_is2 = 1 – (P_ii + P_il + P_is1)_.

= 2(1- p´) (p´ - p_s). ------ (13)

Let , , _, denote the steady-state probabilities of states idle, long, short1, and short2 respectively. From the Markov chain, we have

= ----- (14)
The limiting probability or long run probability that the channel around the node x is found idle, can be obtained by

=

, , _,

Since P_il = , P_{is1 =} , and P_is2 = , we obtain

= .

= . ---- (15)

Since p’= p.П_l,

p’ = .

p’ = p τ (τ + 2p_s(1- p´)T_long + p’² T_short1 + 2(1- p´)(p´-p_s)T_short2)^-1. ---- (16)
The derivation for centre nodes of a grid network can be similarly derived and the final express is as below.

P_ii = (1 - p´)⁴ ---- (17)

P_il = 4p_s(1- p´)³. ---- (18)
P_is1 = 1 – [(1 - p´)⁴ - 4p_s(1- p´)].

p´ ² [ 3p’² – 8p´ + 6] ---- (19)
P_is2 = 1 - P_ii - P_il – P_is1.

4(1 - p´)³(p´ - p_s) ------- (20)

.

=. ------ (21)

p´ = p. _.

= p . [  + 4* p_s *(1 - p´)³T_long + p´ ²(3 p´² – 8 p´ +6)T_short1 + 4(1- p´)³(p´- p_s) T_short2 ]. ------ (22)

In the above equation the values of p_s is yet to be determined which will be obtained from the next steps.