Partition Anticipation for Wireless

Partition Anticipation for Wireless Local Area Networks Andrew Butterly A dissertation submitted to the University of Dublin, in partial fulfillment of the requirements for the degree of Master of Science in Computer Science thSeptember 16 2002 i  Declaration I declare that the work described in this dissertation is, except where otherwise stated, entirely my own work and has not been submitted as an exercise for a degree at this or any other university. Signed: ___________________ Andrew Butterly th,Date: September 16 2002 ii  Permission to lend and/or copy I agree that Trinity College Library may lend or copy this dissertation upon request. Signed: ___________________ Andrew Butterly th,Date: September 16 2002 iii Acknowledgements I would like to thank my supervisor, Dr. Vinny Cahill, for his guidance throughout the year. Many thanks also go to Mr. Gregor Gärtner, Mr. Raymond Cunningham, and Mr. Fergal O'Hart for their generous gifts of time and advice. iv Abstract Wireless networks introduce new possibilities for computer networking. They also bring some new problems, while enhancing some already established ones. One new problem is a network’s increased sensitivity to its environment, while the issues of failure detection, and efficient network routing, are examples of traditional problems that have been exacerbated. The possibility and severity of partition on a network is another problem that has been made worse by the use of wireless solutions. In the case of wireless partitions, there is less scope for predicting a failure than in traditional networks, or judging it correctly as such once it has happened. This is due to the current lack of experience in predicting the characteristics of the wireless medium, as well its inherent unpredictability. This document describes and evaluates solutions for a network location information dissemination protocol, and a framework for a wireless network partition anticipator that uses this location information service. The location service presents a process for relative and absolute user location tracking, network view construction, and routing table construction. The partition anticipator framework analyses the output of the location dissemination service and makes inferences for network quality based on an expert system knowledge base. Potential partitions between nodes, as well as excellent quality connections are highlighted as being interesting. v Table of contents Partition Anticipation for Wireless Local Area Networks..............................................i Declaration.................................................................................................................ii Permission to lend and/or copy................................................................................ iii Acknowledgements...................................................................................................iv Abstract......................................................................................................................v Chapter 1 ..................................................................................................................1 Introduction..............................................................................................................1 1.1 Motivation........................................................................................................1 1.2 Wireless Networks...........................................................................................1 1.3 Concept of a network information service.......................................................4 1.4 Concept of a partition anticipator ....................................................................4 1.5 Objectives for this project................................................................................5 1.6 Document Structure .........................................................................................7 e7 Chapter 28 State of the Art .........................................................................................................8 2.1 Motivation........................................................................................................8 2.2 Group communication .....................................................................................8 2.3 Routing Protocols...........................................................................................10 2.4 Location determination ..................................................................................14 2.5 Signal modelling in real time.........................................................................16 2.5 The Terminodes Project.................................................................................18 2.6 Comment on the preceding projects / papers.................................................20 2.7 Proximity Groups21 2.8 Chapter conclusion.........................................................................................24 Chapter 3 ................................................................................................................25 IEEE 802.11............................................................................................................25 3.1 Introduction....................................................................................................25 3.2 Common terms used in wireless communication ..........................................25 3.3 Overview of 802.11 .......................................................................................26 3.4 Experiments ...................................................................................................29 3.5 Chapter conclusion42 Chapter 443 Analysis and Design ...............................................................................................43 4.1 Introduction....................................................................................................43 4.2 Should a partition anticipator be a centralised algorithm?.............................43 4.3 Analysis of this LID protocol ........................................................................46 4.4 Design of the LID protocol............................................................................47 4.5 Analysis of a partition anticipator..................................................................65 4.6 Design of a partition anticipator ....................................................................67 4.7 Chapter conclusion.........................................................................................70 Chapter 5 ................................................................................................................71 Implementation ......................................................................................................71 5.1 Introduction71 5.2 The 802.11 driver extension ..........................................................................71 5.3 Implementation of the LID protocol..............................................................73 vi 5.4 Implementation of the PA protocol................................................................80 5.5 Conclusion .....................................................................................................84 Chapter 6 ................................................................................................................85 Evaluation...............................................................................................................85 6.1 Introduction....................................................................................................85 6.2 Evaluation of the location information dissemination protocol.....................85 6.3 Evaluation of the partition anticipator ...........................................................89 6.4 A grammar for knowledge .............................................................................92 6.5 Limitations of a partition anticipator .............................................................92 6.6 Comments ......................................................................................................93 6.7 General comments .........................................................................................93 6.8 Chapter conclusion95 Chapter 7 ................................................................................................................96 Conclusion ..............................................................................................................96 Objectives revisited..............................................................................................96 What has been achieved in this project................................................................96 Summation ...........................................................................................................97 Bibliography98 vi i Table of figures Figure 1, Lucent and Compaq distance to throughput comparison .............................33 Figure 2, decrease in signal strength as distance increases..........................................35 Figure 3, 6 samples taken across three tests ................................................................36 Figure 4, two nodes received signal strengths during a test ........................................37 Figure 5, comparison of throughput on grass and sand ...............................................38 Figure 6, rotation in the Y-Axis...................................................................................40 Figure 7, notion of a pair of unidirectional links .................................................