Bonafide certificate

2.7 DISTRIBUTED SCHEMES

The centralized methods for computing link active time proportion require global knowledge of network topology. Hence only a central entity that is aware of the entire network topology can perform this. Also the method of enumerating all the Maximal Independent Sets for a given graph is known to be a NP-hard problem. Due to its complexity and the requirement for global knowledge, the solution suggested is limited in its application. In this section, we outline two distributed approaches to estimate the active proportion of links using local topology knowledge. The distributed nature of solution finds application in wide ranging applications from QoS routing and admission control to rate based flow control.

2.7.1Two-hop Interference

In the distributed approach, the objective is to enable a node itself to calculate the ATPs of links incident on it. To achieve this, a node needs to have knowledge of all other nodes in its transmission and interfering range since these are the nodes it competes with. We extend the notion of interference from nodes to links, by introducing one-hop and two-hop interfering links. If we construct from a network graph G, an edge graph E , where links are the vertices, immediate neighbors of the link node are termed one-hop interfering links and the corresponding two-hop neighbors are called as two-hop interfering links.

We consider that interferers for a link includes only its one-hop and least two-other links between them alone can be active simultaneously or that one in m=3 consecutive links can be active simultaneously. It is fair to assume that a link experiences interference only till two-hop interfering links as illustrated in Guerien and Chaulet (2003) since considering hops greater than or lesser than 2 results in over estimation or under estimating the effect of interference. Evaluations on random graphs of the number of missed or over-detected neighbors showed that 2-hops is the best number that gives the least missed or over-detected neighbors Guerin and Chaudet (2002) two-hop interfering links.
Looking from the protocol constraints too, the consideration of 2-hop neighbors would suffice. In multi-hop networks, to address the hidden terminal problem, RTS/CTS handshake is used before data transmission. When this mode is used, only links that are separated at least by two hops can be active simultaneously. This can be explained with the following figure. At any time in a saturated 802.11 network, nodes contend for channel. This can be viewed as a set of links contending for activity. Each link has its own set of interfering links that compete for channel. We call it the contention set of the link. We illustrate that for any link, the contention set includes the one-hop and two-hop interfering links.

Fig 4 Sample topology to illiustrate two- hop interference

Consider the link cd in the above figure. When the link cd is active, its one-hop neighboring links bc, gc, ch & de are made inactive due to the reception of either RTS/CTS packets containing Network Allocation Vector (NAV) information. Apart from no transmission, they don’t either respond to any request for transmission from the other nodes in the form of RTS/DATA. This makes any activity impossible in either the one-hop or two-hop interfering links. Due to symmetry, any activity in these links makes the link cd too inactive. In the figure, links ab, ei and ef are the two-hop interfering links.

2.7.2Topology Discovery

In an IEEE 802.11 network, nodes decode packets both intended and not intended for them. We describe a simple approach to update a node’s one-hop and two-hop neighbors. Using our approach a node has to maintain one-hop and two-hop neighbor list. The RTS and DATA packets carry two fields namely Transmitter Address (TA) and Receiver Address (RA) in their header. For each RTS/DATA packet that a node decodes, a node updates its neighbor list as follows.

Inspect a MAC packet,
Add the TA field to 1-hop neighbor list.
Add the RA field to 2-hop neighbor list.
Since TA field refers to the address of the sender, it is updated as the immediate neighbor or 1-hop neighbor of a node. RA field refers to the destination address of the packet which means that the sender of the packet which is on-hop to this node is sending a packet to the node referred to by RA. This implies that the node referred to by RA must be reachable from this node by two-hops. However its doesn’t mean that only way of reaching RA is by two-hops. A node which is a two-hop neighbor could be a one-hop neighbor too. This only reflects the presence of cycles in the network. However its is possible that the topology of the network changes in due course of time. To accommodate that in our topology discovery method, we maintain a timer with each entry. The value of the timer will depend on the rate at which topology changes.

This method of update is robust in that it discovers all cycles in the network. In a saturated network, nodes can quickly discover its local topology this way. The stale entries in the table are cleaned with associated timers. This method also accommodates for low mobility as any change in node positions can be taken care of by new updates and update period.

With the topology discovery method, a node is aware of two-hop node topology. But we need to know the two-hop link neighbors. While both the end nodes of the link together get a complete information about the one-hop and two-hop neighboring links, it is possible that in some configurations, one of the end-nodes misses some node at the other end. This is illustrated by the following figure.

Fig 5 : Graph to illustrate need for 3 hop knowledge in some cases

In the figure, consider link 3--4, while node 3 discovers nodes 2 ,1, 4, 5and hence the links 2-3 and 1-2, 3-4 and 4-5 it doesn’t know about the link 5-6 since it doesn’t know its third hop neighbor 6. Similarly, node 4 is aware of the links 3-4, 4-5, 5-6, and 2-3 but not 1-2 since it has no knowledge of 1. To facilitate this, neighboring nodes can exchange the information about missing nodes to get the complete information on two-hop interfering links.

2.7.3Distributed Node probability based estimations ( DNP )

In this section we give a distributed approach for estimating the link active probabilities. This computes the link active time based on the node transmission probabilities. In this approach the probability that a link is active is the sum of product of probability of node transmission and probability that the traffic from the node is meant to the neighbor at the other end for either end nodes of a link.

Let

T_i : Transmission probability of node i.

CN_i : number of contending neighbor nodes of node i.

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

ATP_ij = T_i . P_ij+ T_j . P_ji. ---- (5)
We calculate the transmission probabilities of node based on the long-term node fairness property of IEEE 802.11 MAC protocol. According to this property, nodes contending for channel get equal opportunity for transmit in the long run. In a multi-hop network, since the different nodes have different contention set or different number of nodes to contend with, the transmission probability of a node depends on the number of nodes in its contention set. Using the topology discovery method, a node can estimate its transmission probability as T_i = 1/CN_i.
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.

2.7.4Distributed Link Neighborhood based Estimations

This is another distributed approach where a link’s opportunity to be active is calculated based on its link neighborhood activity. With our topology discovery method, a node acquires the knowledge of its one and two-hop interfering links. We extend the notion of node fairness to links. In this approach, we consider that channel is shared between contending neighbors equally. Hence we express the ATP of a link as 1/CL_ij, where CL_ij is the number of one-hop and two-hop interfering links plus itself. CL_ij is given by the number of links in the contending set.

We have a method to express a links chance to transmit based on its link neighborhood. The proportion of time each link gets to be active is dependent on the number of interfering link neighbors it has. However the effect of each link on this link’s activity is different and depends on its own link neighborhood. It will be a recursive effect. We don’t account for this in our work and just give initial estimates as ATPs.