Bonafide certificate

1.5CONTRIBUTION in this THESIS

Contributions made in the thesis are three fold.

A framework for estimating capacities of individual links in a multi-hop ad hoc network using graph theoretical approach is provided through the centralized estimations.
Distributed approaches with very low complexity algorithms to estimate the link capacities are outlined. They have the advantage of being used in real-time applications.
Analytical model for multi-hop networks are obtained that study individual node performance and provides insight into the modeling of multi-hop networks.

1.6THESIS ORGANIZATION

Chapter 2 details centralized and distributed approaches used for estimating the link capacities. It discusses the approaches and algorithms involved and their complexity.

Chapter 3 deals with analytical modeling of IEEE 802.11 based multi-hop networks in string and grid topologies.
Chapter 4 discusses the results of the estimation schemes, compares the schemes with simulation. It also discusses the analytical results and validates them with simulation.
Chapter 5 concludes the thesis discussing the benefits of the solution schemes, improvements possible in them and future scope of the work.

CHAPTER 2

BANDWIDTH ESTIMATION METHODS

2.1OVERVIEW

Ad hoc networks are topology-free, infrastructure-less, self-organizing wireless networks. The nodes might have asymmetric capabilities. They can be either single-hop or Multi-hop networks. A single-hop network is one in which all nodes are within the transmission range of each other and every node can reach every other node in one hop. In a Multi-hop ad hoc network each node acts as a router to other nodes in its neighborhood and a node might reach another node in the network only after multiple hops. In this chapter we describe various methods to estimate the capacities of links in such a network.

2.2THE IEEE 802.11 STANDARD

The IEEE 802.11 standard (1999) specifies MAC protocols for operation in ad hoc mode and centrally coordinated mode. The distributed coordination function (DCF) is used for operation in the ad hoc mode and of interest to our work.

2.2.1Distributed Coordination Function

The DCF is based on carrier sense multiple access with collision avoidance (CSMA/CA). The standard defines the common duration for carrier sensing by the Clear Channel Assessment (CCA) function or DCF Inter Frame Space (DIFS) at every node and also the contention window ranges (CWmin, CWmax). The time gap between two packets in the handshake sequence or an atomic operation, defined as Short Inter Frame Space (SIFS), is less than DIFS. This prevents other nodes from capturing the channel when one transmission (in the same area) is already going on.

All nodes that can hear each other and agree to join and form an Independent Basic Service Set (IBSS). These nodes remain in synchrony with a special management frame called the ‘Beacon frame’. This frame is periodically generated by one of the nodes in the IBSS. Once a node captures the channel, it can send data packet of at most one MAC Service Data Unit (MSDU) which might be broken into fragments or MAC Protocol Data Units (MPDUs) as specified by the variable Fragmentation Threshold. A four-way handshake is optionally used.
A typical sequence (depicted in Fig 1 ) would be :

Fig 1 DCF mode of Operation

• 
  A node willing to transmit performs carrier sensing
  
• 
  If it finds the channel free for a DIFS duration, it may transmit.
  
• 
  To avoid collision situation, it backs off in random multiples of a constant time (Slot-time) chosen from the contention window (CW_min and CW_max).
  
• 
  After the backoff countdown, a request to send (RTS) frame is sent by the source node.
  
• 
  If the destination node ( S2 in Fig 1 ) is ready to receive then it initiates a clear to send (CTS) frame within a SIFS duration.
  
• 
  The source node initiates the sending of the Data frame (MPDU or fragment) within a SIFS duration.
  
• 
  If the destination node properly receives the MPDU it responds with an acknowledgement (ACK) packet.
  

In case of failure the source node backs-off again with a random number chosen from a doubled contention window. Absence of ACK is treated as collision in which case, the node has to carrier sense for an extended IFS (EIFS).

The duration for which the transmission would go on is continuously updated through the network allocation vector (NAV) field in the handshake frames. The NAV information is used by other nodes (like S3 in Fig 1 ) in the network to stay away from transmitting. When one transmission is going on the same area, another transmission will lead to collision. This combined with the handshake helps overcome the hidden node problem to a good extent but creates more number of exposed nodes. MSDUs in MAC queue for duration longer than a (configurable) constant 'maxMSDULifetime' are dropped from the queue. In addition to this a retransmit limit can also be fixed.
For handling data packets a simple First Come First Serve (FCFS) queue is used by all the nodes. This protocol allows fair-channel access on the long-run, given the traffic generation characteristics and channel condition due to environmental changes are even across all nodes in the network. This doesn't differentiate nodes or traffic in anyway and hence it is suitable for best-effort type of traffic only.

2.3SYSTEM MODEL

The network is represented as a graph G =(N,L) with vertices and edges in our model. The nodes in the network correspond to the vertices and the links correspond to the edges. A wireless link can be defined as follows. A link L is assumed to exist between two nodes u and v if they are within the transmission range of each other. This is the same as the first condition for successful transmission given in chapter 1. This link assumption is also used by Kodialam and Nandagopal (2003). Some of the work in literature consider a link to exist between two nodes only when there is a flow through the link. In this work, a wirless link is assumed to exist between between two nodes if the nodes are within the transmission range of each other. This is appropriate for deriving bounds on link capacity as this doesn’t make any assumption about existence or non-existence of flows which can change with time while our approach gives a general solution based on network connectivity.