Bonafide certificate

2.4LINK ACTIVATION CONSTRAINTS

The link activation constraints can be represented using graphs. There are two ways of representing the link activation constraints (contention between links) in multi-hop networks. One is based on the set of links that can be activated simultaneously, Link Independent sets and the other, based on the set of links that cannot be active simultaneously due to mutual interference, the Interference graph. In our centralized approach, both the models are used to obtain the active time of links. A sample network with string topology is used to illustrate these representations by a graph.

Consider the graph of string network. Each node is separated from its neighbor by a distance of 250m. We consider a transmission range of 250m and an interference range of 500m.

Fig 2 Sample String Network

2.4.1Interference Graph

Consider the given graph G = (N,L) of the network. To represent the set of links that cannot be active simultaneously, a link graph F = (N_f, L_f) is constructed from the given graph G. Here N_f denotes the set of all links in graph G and L_f respresents the edge set of F where an edge between any two links i, j N_f exists if i and j interfere with each other’s transmission. For the sake of simplicity and ease of analysis, the condition for interference can be denoted in terms of link distance. In an edge graph, link distance can be specified in terms of no of hops between links, which are edges in the graph.

Fig 3 Interference Graph for String Network

The above figure represents the interference graph constructed from the string network. It is an edge graph of G where there is an edge between links if they were either adjacent or have a link distance of m. In this case, m is considered as 2.

2.4.2Maximal Independent Sets

In this section, we introduce a construct that defines the set of links that cannot be active simultaneously. An independent set of a graph G is a subset of vertices such that no two vertices in the subset represent an edge in G. A Maximal Independent Set (MIS) is an independent set such that no new vertex can be added to the set without affecting the independence property

An independent set obtained from the interference graph F, gives the set of possible links that can be simultaneously active in a network. An enumeration of all MIS for the interference graph gives all the possible configuration of active links in the network.
For example, the set of all MIS in the above graph F is (1,4,7), (3,7), (2,7), (1,5), (2,5), (1,6), (3,6), and (2,7).

2.5LINK CAPACITY ESTIMATIONS

Unlike in a wired network, the notion of link capacity is not well defined in a contention based wireless network. Capacity of a link may be described as the number of bits that can be carried per second through the link. While link capacity in wired networks is determined by fixed bandwidth cables laid between nodes, in some wireless systems deploying TDMA and FDMA, the capacity can be calculated due to existence of a central entity that allocates resources to each node.

In a contention based wireless system, it is the need for every node all over the domain to share the portion of the channel it is utilizing with the nodes in its local neighborhood. The IEEE 802.11 standard based MAC is one example of a distributed contention based medium access system in which a common channel is shared among the participating nodes. It is of interest to us to find the time available for each link to access the common channel
In a single hop network, the probability for each link to be active is same for all links given the assumption of equal traffic at all nodes whereas in a multi-hop network, a link’s activity depends on all other contending neighboring links’ activity. With the assumption of saturated traffic at nodes and its equal distribution to links, there is competition among links at all times.
The capacity of a link is directly related to the time a link gets to be active. If this time is obtained, it can be converted to capacity by multiplying it with channel capacity. In a shared contention based system such as the IEEE 802.11 standard based system, the amount of time for which a link becomes active per unit time cannot be determined exactly as in a TDMA system. Neither can be rate available for a user or node be determined exactly using the existing methods. This is due to the contention based channel access where nodes get to transmit only when its neighbors relinquish the channel. Also the Binary Exponential Back-off (BEB) introduces further probabilistic component in channel access. In this context we would like to estimate the time for which a link can be active and give bounds on the link throughput.
In this section, different approaches to estimate the capacity of wireless links between nodes are presented . Also various schemes to derive upper bounds for link active times and hence link capacities are outlined. The schemes can be classified into centralized and distributed. Two approaches are proposed in each of the category.

2.5.1ACTIVE TIME PROPORTION of LINKS

A notion of time available for each link relative to other links in its neighborhood is defined. Active Time Proportion or ATP of links is defined as a fraction of time for which a link gets to be active. This is obtained for each method of estimation and compared across different approaches and with simulation.

2.6CENTRALIZED SCHEMES

In this approach, it is assumed that the topology of the entire network is known to a central entity which makes use of it to derive the active times of links.

2.6.1MIS - Equal Probabilities (EW-MIS)

In this approach, a central entity with its knowledge of global topology constructs an interference graph F from the network graph as illustrated for the string network above. This corresponds to a graph where the neighboring vertices, which are links in the edge graph are the ones that cannot be active simultaneously. From the graph F, all the Maximal Independent Sets (MIS) are enumerated. This gives the set of all the possible configurations of active links in the network. Each MIS corresponds to a state of the network.

In this approach, called EW-MIS or Equally weighted MIS approach, the probability of occurrence of MIS is uniformly distributed. Hence if the total number of MISs in the network is M, then each MIS is assigned a uniform probability of 1/M. Active Time Proportion or ATPs of links are obtained by summing the probabilities of occurrence of MISs in which a link occurs. It is given by

ATP_ij = ---- (1)

Where

ATP_ij is the Active Time Proportion of link ij.

R_i = Probability of occurrence of ith MIS.

M – Total number of MIS in the network.

2.6.2MIS – Node Probability based Approach (NP-MIS)

The Node transmission probability weighted MIS approach or NP-MIS approach is similar to that of the first approach yet different from it in that it assigns different weights to different MISs. The weights are probabilities of occurrence of an MIS, assigned taking into account the probabilities with which end nodes of the constituent links transmit on the channel. First initial link probabilities are estimated. Using this weights are assigned to MISs. These weights are then used to update the active time proportion (ATP) of links.

Let

Ti : Probability that node i starts transmitting in a given time slot.

Pij : Probability that node i’s transmission is intended to node j.

WMi : probabilistic weight given to the ith MIS.

Lij : Initial link active probability.

Cij : No. of MIS in which link ij occurs.

M : set of all MISs.

Mi : refers to the ith MIS.

We first assign initial active probabilities to links based on the transmission probabilities of nodes that are the endpoints of the link. Ti is calculated based on the assumption of Poisson arrivals. In a small fraction of time, only one node is assumed to begin or initiate transmission. Based on this each node has equal probability of initiating data packet transmission. Hence T_i is 1/N, where N refers to total number of nodes in the network. Probability of a node’s transmission to its neighbor can be calculated based on the traffic pattern. If traffic is going to be equally distributed to a nodes neighbor, it can be taken as 1/no. of immediate neighbors. It is a generic method which can take values depending on the assumed traffic model.
L_ij = T_i.P_ij + T_j.P_ji ------ (2)
We compute the probability of occurrence of an MIS with the initial active probabilities of links. Since a link could occur in more than one MIS, we calculate the probabilistic weight of an MIS as the sum of initial link active probabilities L_ijs of the links constituting an MIS normalized by the number of occurrences in all MISs.

W_Mi = ------- (3)

Now we calculate the available Time proportion of a link by summing the probabilistic weights given to MIS in which the link occurs.
ATP_ij = . -------- (4)

While the initial link probabilities L_ij are assigned by considering local node distribution, they don’t take into account the parallel transmission in the network due to spatial reuse. By assigning weights to MIS based on the initial L_ij and then re-computing the active time of links we are able to capture the parallel activity of links well.