In the first part of this thesis we focus on the mobility and the message delay in mobile ad hoc networks. This is done by focusing on the characteristics of a number of different mobility models. Derived are the positions of the nodes in stationary regime, the amount of time until two nodes meet (again), and the amount of time that two nodes remain within communication range of one other. This information provides us with a basis for the derivation of the message delay in mobile ad hoc networks. In particular, closed-form expressions are obtained for the message delay under a number of different relay protocols and mobility models.The second part is devoted to the study of polling systems composed of two queues. The distinction from classical results is that the sequences of switchover times from each queue need not be i.i.d. nor independent from each other; each sequence is merely required to form a stationary ergodic sequence. With stochastic recursive equations explicit expressions are derived for a number of performance measures, including the average delay of a customer and the average queue lengths. With these expressions a comparison is made between two service disciplines and through a number of examples it is shown that the correlations can significantly increase the mean delay and the average queue lengths. This has important implications for communication systems in which a common communication channel is shared amongst various users and where the time between consecutive data transfers is correlated (as is the case in ad-hoc networks). In the third part we consider a tandem queue with holding costs for each customer. An explicit expression is obtained for the value function of the average costs when there is no inflow of customers. The expression obtained provides an intuitive explanation and can be used for optimisation purposes and for the full derivation of the value function when there is an inflow of customers.
Authors
- Bibliographic Reference
- Robin Groenevelt. Modèles stochastiques pour les réseaux ad hoc mobiles. Réseaux et télécommunications [cs.NI]. Université Nice Sophia Antipolis, 2005. Français. ⟨NNT : ⟩. ⟨tel-00274901⟩
- HAL Collection
- ['INRIA - Institut National de Recherche en Informatique et en Automatique', 'INRIA Sophia Antipolis - Méditerranée', 'INRIA-SOPHIA', 'TESTALAIN1', 'INRIA 2']
- HAL Identifier
- 274901
- Institution
- Institut National de Recherche en Informatique et en Automatique
- Laboratory
- Inria Sophia Antipolis - Méditerranée
- Published in
- France
Table of Contents
- Universite de Nice - Sophia Antipolis UFR Sciences 2
- Robin 2
- Mod les Stochastiques pour les R seaux Ad Hoc Mobiles 4
- Stochastic Models for Mobile Ad Hoc Networks 4
- Remerciements 8
- Contents 10
- Introduction 22
- Message Delay in Ad Hoc Networks 30
- Message Delay for One-dimensional Brownian Motions 32
- 1.1 Introduction 33
- 1.2 Two mobiles moving along a line segment 35
- 1.3 A chain of relaying mobiles 39
- 1.4 Numerical results and discussion 42
- 1.5 Extensions to the model 44
- 1.6 Concluding remarks 45
- Acknowledgments 45
- 1.A The Brownian motion 46
- 1.B Proof of Proposition 1.2.2 48
- 1.C Proof of Proposition 1.3.1 50
- Message Delay for One-dimensional Random Walkers 52
- 2.1 Two random walkers jumping on a finite state space 53
- 2.2 A chain of relaying nodes 59
- 2.3 Extensions to the model 64
- 2.4 Concluding remarks 65
- Acknowledgements 65
- 2.A The stationary distribution of a random walker 66
- 2.B Proof of Proposition 2.1.1 66
- 2.C Proof of Proposition 2.1.2 70
- 2.D Proof of Proposition 2.2.1 81
- Message Delay in Two-dimensional Networks 84
- 3.1 Introduction 85
- 3.2 The stochastic model 87
- 3.3 Applications 96
- 3.4 Large networks 105
- 3.5 Concluding Remarks 106
- 3.A Proof of Lemma 3.2.1 107
- 3.B Derivation of the time until the next event 109
- The Mysterious Parameter 112
- 4.1 Introduction 113
- 4.2 The values for 114
- 4.3 Examples 119
- 4.4 Implications for the message delay 119
- 4.5 Concluding remarks 121
- 4.A Proof of Theorem 4.2.1. 122
- 4.B Proof of Proposition 4.2.1. 124
- 4.C Proof of Proposition 4.2.2. 125
- 4.D Probability of contact at a random moment 126
- Polling Systems with Correlated Switchover Times 128
- An Alternating-Priority Server with Correlated Switchover Times 130
- 5.1 Introduction and Motivation 131
- 5.2 Model Description 132
- 5.3 ExhaustiveExhaustive Service System 135
- 5.4 ExhaustiveGated Service System 145
- 5.5 Examples 156
- 5.6 Concluding Remarks 164
- Acknowledgements 166
- 5.A Proof of Theorem 5.3.2. 166
- 5.B Proof of Theorem 5.3.3. 168
- 5.C Alternative proof of Theorem 5.3.4. 171
- 5.D Proof of Theorem 5.4.3. 171
- 5.E List of Notation 178
- Appendix 180
- The Value Function of a Tandem Queue 182
- A.1 Introduction 183
- A.2 A tandem queue with no arrivals 183
- A.3 A tandem queue with arrivals 189
- A.4 Appendix Proof of Proposition A.2.1 191
- A.5 Appendix Proof of Proposition A.2.2 193
- Bibliography 196