Bonafide certificate

BONAFIDE CERTIFICATE

Certified that this thesis titled “Bandwidth Estimation and Analysis of Multi-hop Ad hoc Networks” is a bonafide work of Ms. K.Vijayalakshmi who carried out the research under my supervision. Certified further, that to the best of my knowledge, the work reported herein does not form part of any other thesis or dissertation on the basis of which a degree or award was conferred on an earlier occasion on this or any other candidate.

Date : 4/07/2005 Place : Chennai.

Dr.S.Srikanth, Member Research Staff, AU-KBC Research Centre, MIT Campus, Anna University, Chromepet, Chennai, TN – 600 044 – India

ABSTRACT

Medium access control protocols and its effect on capacity are important aspects in communication system design for any shared medium like wireless. In multi-hop ad hoc networks that use a distributed and contention based channel access mechanism such as those specified in the IEEE 802.11 standard, the capacity of individual links are not known. Existing methods in literature attempt to solve this using measurement based approaches. This thesis proposes graph theoretical and

real-time approaches to estimate the capacities of individual links in a multi-hop ad hoc network and uses analytical modeling to derive node throughputs and successful transmission probabilities of individual nodes in multi-hop ad hoc networks.
In a contention based system based on the IEEE 802.11 standard, the capacity of links depends on the time available for the links to be active which in turn depends on the probability of nodes’ transmission. While the link capacity can be expressed by the number of times it gets activated, it can be more accurately expressed in probabilistic terms. This is due to the randomness introduced in the channel access procedure in the form of virtual carrier sensing and binary exponential backoff. This thesis proposes centralized and distributed methods to estimate the active time of links. The centralized approaches have the knowledge of the entire network topology and use graph theoretic approaches to derive individual link active times. The distributed approaches on the other hand only have the partial knowledge of network topology to derive the link active times. This thesis proposes another approach to the link capacity problem using the analytical modeling of multi-hop network for string and grid topologies. The analytical modeling uses Markov models to derive node throughputs and successful transmission probabilities of individual nodes in multi-hop ad hoc networks. The advantages of the estimation methods are topology independent nature of the solution, a wide spectrum of applications using the estimates and real-time applications using the distributed approach. It also provides insight into the performance evaluation of multi-hop networks. The accuracy of the estimations is validated through simulations and it is observed that there is a difference between the estimated and simulated values only of the order of 10e-02. The values obtained through analytical model too matches the values obtained in simulations to a good degree.

ACKNOWLEDGEMENTS
My foremost thanks and deep sense of gratitude goes to my supervisor Dr.S.Srikanth for giving me a free hand in research along with continued guidance and support throughout the long course of the programme. My heart-felt thanks to my co-supervisor Dr.V.Vaidehi for the encouragement and valuable guidance that motivated me to achieve my goals in phased manner.
I’m greatly indebted to Dr.C.N.Krishnan, the Director of AU- KBC Research centre for being responsible for the inspirational department . His dedication to work and idealogy are sure fires for young minds. My immense thanks to Dr.S.V.Ramanan for the short but most effective periods of interaction that gave the much needed impetus to my thesis. My sincere thanks to Dr. S.Anand for the numerous enlightening discussions and constant encouragement and to Ms. R.Jayaparvathy for continued support and useful suggestions throughout the program. Special thanks to KRK for the support and valuable suggestions during the last leg of the programme.
Immense gratitude to all my wonderful friends and specially to friend and guide Rajesh for the incredible support throughout. The thesis would not have seen the light of the day had it not been for the constant care and blessings of my parents and loving support of my sister. Finally my salutations to God for being with me all through.
TABLE OF CONTENTS

LIST OF TABLES

Table 1 : Simulation prarameters 44

LIST OF FIGURES

Fig 1 DCF mode of Operation 16

Fig 2 Sample String Network 19

Fig 3 Interference Graph for String Network 19

Fig 4 Sample topology to illiustrate two- hop interference 26

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

Fig 6 Channel moled for IEEE 802.11 MAC 35

Fig 7 Node moled for IEEE 802.11 MAC 39

Fig 8 : 10 Node string- centralized 46

Fig 9 : 18 Nodes string – centralized 46

Fig 10 : 9 Nodes Grid - Centralized 47

Fig 11 : 16 Node Grid – Centralized 47

Fig 12 : Random Topology – 10 Nodes – Centralized 48

Fig 13 : String topology, 8 nodes - Distributed 49

Fig 14 : String Topology 12 Nodes - Distributed 50

Fig 15 : Grid Topology 9 Nodes - Distributed 50

Fig 16 : Random Topology, 10 Nodes – Distributed 51

Fig 17 : : Random Topology, 8Nodes - Distributed 51

Fig 18 : String topology – Analytical results 53

Fig 19 : Grid topology – Analytical results 53

Fig 20 Simulation results of string topology 55

Fig 21 Simulation results of 9 Nodes grid toplogy 55

Fig 22 : Simulation results of 16 Nodes grid toplogy 56