Bonafide certificate

CHAPTER 1

INTRODUCTION

1.1OVERVIEW

A multi-hop ad hoc network is a self-organized system that can comprise many mobile nodes connected without a pre-determined topology or central control. It provides quick and easy networking in circumstances that require un-tethered connectivity or temporary network services. It finds widespread applications in scenarios such as hospitals, search and rescue operation, battle fields and disaster sites. Hass et al (1992) outline some of the applications. With the growing popularity of applications, it has become necessary to provide solutions for efficient data or multimedia communication over the network. Link bandwidth estimation is an essential component of rate control and Quality of Service (QoS) support schemes like admission control, resource reservation and QoS routing. The IEEE 802.11 standard based Medium access control (MAC) detailed in the IEEE standard (1999) is the commonly used channel access scheme for ad hoc networks.

1.2LITERATURE SURVEY

The capacity and performance studies of multi-hop networks in the literature is as follows. Yang et al (2003) obtained expressions for throughput of a semi-saturated and unsaturated network. But they did not consider in the model the hidden terminal problem, which is an important aspect of multi-hop networks. Chhaya and Gupta (1997) analyzed the effect of capture and hidden nodes. Li and Blake (2001) studied the capacities of multi-hop networks for standard topologies and random traffic pattern. The analysis however is for the entire network and not on a per link basis. Liaw et al (2004) proposed a method to estimate the throughput available to a node based on local measurements and neighbor information and channel occupancy of the node. However the approach is traffic dependent.

Jain et al (2003) analyzed the impact of interference on multi-hop networks using a linear programming framework. They gave a framework for getting upper and lower bounds for flow throughput. Similarly Kodialam and Nandagopal (2003) characterized the achievable rates for single and multiple flows. In both the above approaches, the computation of feasible single or multiple flows assumes the knowledge of link capacity or a link’s bit rate. Samrath et al (2003), Li et al (2003) and Kazantzidis et al (2001) in their work used the channel access time of a station’s current traffic to predict the achievable bandwidth of flows. With new flows getting added, the competition for the channel intensifies among the flows and the old channel access time measured doesn’t reflect the bandwidth allocation for the new flows.
The efficiency of the IEEE 802.11 protocol directly affects the utilization of the channel capacity and system performance. Performance evaluation of single-hop ad hoc networks using IEEE 802.11 MAC is done in Bianchi (2000), Carvalho and Aceves (2003), Li et al (2003), and Liwa et al (2004) In the case of multi-hop ad hoc networks using DCF protocol, performance analysis needs consideration of many factors. Much work has gone into studying the interaction between higher layers and IEEE 802.11 MAC in multi-hop networks. Xu and Saadawi (2003) brought out the problems in fairness and throughput variations when TCP is used with 802.11 MAC. Fairness issues and enhancement of MAC are studied by Tang and Gerla (1999) and Bensaou et al (2000). Eladly and Chen (2003) extended the saturation throughput model of Bianchi (2000) to the case of multiple overlapping BSSs. However a comprehensive analysis of performance of the IEEE 802.11 based multi-hop networks is still an ongoing research work. Wang and Aceves (2004) analyzed the performance of CSMA/CA based multi-hop networks using different Markov models for channel and node. Yawen and Biaz (2005) combined the Bianchi (2000) model to get a three dimensional model to analyze the performance of a multi-hop network under different traffic loads and network densities.
In this work, we address the problem of estimating the active time of links in a multi-hop network and give a general framework for such estimations. A general solution that works for any topology is proposed. The analytical model for IEEE 802.11 provides a much needed insight into performance modeling of multi-hop networks.

1.3PROBLEM DEFINITION

Multi-hop ad hoc networks are gaining attention due its vast application potential. For multimedia applications, it is necessary that Quality of Service (QoS) schemes are in place. An essential component of QoS and traffic management schemes is the knowledge of link capacity information. Most work in the literature use measurement based approaches to get the values of link capacities. This thesis addresses the problem of estimating link capacities using a number of approaches. Another way of addressing is the issue is by modeling the network. This helps in performance evaluation and getting probabilistic estimates of capacities. This thesis addresses it by the modeling the IEEE 802.11 based multi-hop networks for string and grid topologies.

1.4ASSUMPTIONS

The following assumptions have been made regarding the problem in hand while arriving at the solution. These assumptions define the scope or the boundaries of the solution formulated.

We consider a static multi-hop ad hoc network with N nodes using Distributed Co-ordination Function (DCF) of IEEE 802.11 to schedule their transmission. In a multi-hop network using DCF, channel is spatially reused and nodes transmit simultaneously when they are not within the interference range ‘R’ of each other. We will use the protocol model used by Gupta and Kumar (2000) to describe the conditions under which a successful wireless transmission takes place.

Each node can transmits to other nodes in its transmission range ‘d’. We assume that all nodes employ a common range ‘d’ for their transmission. Let X_i, denote the location of node i. When node i transmits to node j directly, over the channel, this transmission is received successfully by j if,

The distance between node i and j is no more than d. i.e.,

For every other node m simultaneously transmitting over the channel,

where is the Euclidean norm. The quantity k>d models the interference range of the nodes.

Traffic at every node is assumed to be saturated and hence a node always has a packet to transmit. And the destination is assumed chosen randomly from one of its neighbors.