L fc/n o M / fc "I 'DBm I o*l i9rh\ MOBILE USER BEHAVIOUR DETERMINATION IN WCDMA USING HIDDEN MARKOV MODELS A dissertation submitted to the Department of Electronic and Telecommunication Engineering, University of Moratuwa in partial fulfillment of the requirements for the Master of Engineering in Telecommunication By r;$i f UD AYA DAMPAGE O 6 . • ■* "* ■ Supervised by: Professor Dileeka Dias • n- Department of Electronic and Telecommunication Engineering, University of Moratuwa, Sri Lanka. 8 77s /December 2006 University of Moratuwa 87787 87787 DECLARATION The work submitted in this dissertation is the result of my own investigations, except where otherwise stated. It has not already been accepted for any degree, and is also not being concurrently submitted for any other degree. Name of Candidate: S U Dampage 01st February 2007Date: I endorse the declaration by the candidate. Name of each Supervisor: Professor Dileeka Dias I Abstract The vision of this research paper is that the mobile phone is aware of its user's motion state and surroundings and modifies its behaviour especially the characteristics of Location- Based-Services based on this information. In the research it is evaluated and implemented, a methodology which can identify individual user states. This learning is expected to occur online and does not require any external supervision. The proposed system relies on Hid­ den Markov Modelling and Log Likelihood Method. The underlying assumption of the statistical model is that the signal can be well characterized as a parametric random proc­ ess, and that the parameters of the stochastic process can be determined (estimated) in a precise, well defined manner. The basic philosophy of Hidden Markov model is that an ob­ servation sequence can be well modelled if parameters of a Hidden Markov Model are carefully and correctly chosen. The problem with this philosophy is that it is sometimes in accurate, either because the signal does not obey the constraints of the Hidden Markov Model, or because it is too difficult to get reliable estimates of all Hidden Markov Model parameters .The implementation of the methodology is performed by first training the Hid­ den Markov Model for the required number of speed states by the intended network trace. The log likelihood value of the data for each hidden markov model in the set is computed and identifies the motion state-speed, by choosing the Hidden Markov Model that pro­ duced the highest value. The method of maximum likelihood provided estimators that have both a reasonable intuitive basis and many desirable statistical properties. The main reason for the selection of maximum likelihood method is that it is very broadly applicable and simple to apply. The results of simulations indicate that the proposed method is able to as­ sist to create a meaningful user context model at various propagation conditions defined by both 3rd Generation Partnership Project (3GPP) and Wireless World Initiative New Radio (WINNER) propagation scenarios while only requiring a network trace-i.e. a received bit length, without having an integrated sensor onboard cellular phone or any other wearable sensor device. Acknowledgement I owe a debt of gratitude to, My supervisor Professor Dileeka Dias for her flexibil­ ity/extended support, To Professor RMP Rajatheva and Course coordinator Dr RP Thilakumara for assisting me in finding required research papers and to keep me moving forward. For all researchers and authors for the stimulating ideas I gained from their works listed in the references. Finally heartfelt appreciation is deserved by all my lecturers who really supplied most of oxygen to dive in deep trenches of the blue ocean of Electronic & Telecommunication Engineering. iii Table of Contents Decleration........... Abstract......... ...... Acknowledgement Table of Contents.. List of Figures...... i ii iii iv vii 1 Introduction..................................................................... 1.1 Background and Context............................................ 1.2 Scope and Objectives................................................. 1.3 Overview of Dissertation........................................... 1.4 An Overview of Mobile Location............................... 1.4.1 Classifications........................................................ 1.4.2 Problem of position estimation............................... 1.4.3 Types of Measurements......................................... 1.4.4 Measures of Accuracy........................................... 1.4.5 Limits on location covariance................................. 1.4.6 Positioning methods and statistical modelling........ 1.5 An Overview of Location Based Services.................. 1.5.1 Classifications........................................................ 1.5.2 Location based Services......................................... 1.5.3 Location Based Services Communication Model, 1.5.4 Key Implementation requirements...................... 1.5.5 Major Challenges.................................... .......... 1.6 Basics of WCDMA............................................... . 1.6.1 Introduction.......................................................... 1.6.2 Basic concepts...................................................... 1.6.3 Channel Structure................................................. 1.6.4 Channel Estimation............................................... 1.6.5 Location techniques for UMTS............................. 1 1 1 2 3 2 4 4 6 6 8 8 9 10 11 12 12 12 13 14 16 16 iv 182 Statement of Problem........ 2.1 The Vision................... 2.2 Problem Identification 18 ...18 203 Survey of Previous Work, 234 Theoretical development... 4.1 Statistical Modelling.... 4.2 Implementation........... 4.3 Markov Property......... 9 4.4 N-State Markov Model 23 23 .24 ....25 .265 Proposed Methodology...................... 5.1 Process Summery............................. 5.2 Training of the hidden markov model 5.3 Identification of state....................... 26 26 30 326 Simulation.................................................................... 6.1 Assumptions.................................................... ...... 6.2 Simulation of Physical Layer of 3G wireless system 6.2.1 Basic Operation of Simulator............................. 6.2.2 The Uplink Simulator........................................ 6.2.3 Simulation Parameters....................................... 6.2.4 Simulator Output............................................... 6.3 Simulation of Propagation Conditions.................... 6.4 Software Implementation........................................ 32 32 33 33 34 36 36 37 387 Results and Analysis 7.1 Results obtained for Specific cases defined in 3GPP and WINNER Propagation Conditions given in Paragraph 6.3....................................... 7.1.1 Results obtained for Case-1, at a speed of 3 kmh with an Average Power of -lOdB Error Sequence 39 39 v 7.1.2 Results obtained for a Case-Cl Metropol at a speed of 70 kmh with an Average Power of -lOdB Error Sequence............................................. 7.1.3 Results obtained for Case-3 at a speed of 120 kmh with an Average Power of -3 dB Error Sequence........................ 41 43 7.2 Results obtained at intermediate speeds to check the reliability of proposed method ,46 7.2.1 Results obtained at a speed of 60 kmh with an Average Power of-10 dB Error Sequence 7.2.2 Results obtained at a speed of 65 kmh with an Average Power of 0 dB Error Sequence 7.2.3 Results obtained at a speed of 75 kmh with an Average Power of -10 dB Error Sequence 7.2.4 Results obtained at a speed of 100 kmh with an Average Power of 0 dB Error Sequence 7.2.5 Results obtained at a speed of 110 kmh with an Average Power of 0 dB Error Sequence 7.2.6 Results obtained at a speed of 125 kmh with an Average Power of-3 dB Error Sequence 7.2.7 Results obtained at a speed of 130 kmh with an Average Power of 0 dB Error Sequence 47 48 49 50 51 52 53 537.3 Analysis.... 7.4 Evaluation.. 7.5 Applications. 54 56 588 Conclusion....... 8.1 Summary.... 8.2 Future Work 58 58 60References vt List of Figures 101 LBS Communication Model............................................ ...... 2. Signal Spreading and Correlation in WCDMA...................... 3. WCDMA Channel Structure................................................... 4. A Hidden Markov Model................. ...................................... . 5. Computation of forward variables......................................... 6. Computation of backward variables........................................ 7. Variation of Normalized Error with Number of Bits................ 8. Variation of Resolution with Number of Bits.......................... 9. Variation of Resolution with Number of Bits.......................... 10. Variation of Resolution with Number of Bits......................... 11. Variation of Magnitude of Error with Speed of Mobile Station 14 15 24 27 28 40 40 42 44 45 vii