Chaîne de Markov - Télétrafic - Files D'attente [PDF]

Zitiervorschau

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

Chaîne de Markov - Télétrafic - Files d'attente Version 5.0

Michel Terré Electronique ELE111 [email protected]

Electronique B11

1

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

1 Rappels de probabilité Le dimensionnement d'un réseau de Télécommunications demande quelques calculs de probabilités élémentaires. Il n'est pas nécessaire de développer une théorie très complète pour suivre ces calculs. Il est cependant nécessaire de savoir calculer quelques probabilités conditionnelles et quelques moments statistiques. Ce paragraphe rappelle les notions de probabilité nécessaires pour ce cours. Les lecteurs connaissant bien le domaine peuvent donc passer directement au paragraphe 2.

1.1 Evénements et probabilité Considérons le cas d'une partie de roulette à 6 coups. A chaque tentative il y a 6 sorties possibles. On définit ainsi l'espace des résultats possibles : S = {1 2 3 4 5 6 }

On peut alors définir un événement comme un sous ensemble de S. Ainsi l'événement A = {2 4} correspond aux sorties 2 ou 4 de la roulette. On peut alors définir l'événement complémentaire A = {1 3 5 6 } . Deux événements sont dits exclusifs si ils n'ont aucun point commun. C'est à dire si la réalisation d'un des événements rend l'autre impossible. L'événement B = {1 3 6 } est ainsi exclusif par rapport à l'événement A. De la même manière, A et A sont exclusifs.

On définit la somme ou l'union de deux événements comme l'ensemble des valeurs des deux événements. Ainsi en introduisant C = {1 2 3} , l'événement D = B ∪ C représente l'ensemble les valeurs D = {1 2 3 6 } . On définit l'intersection de deux événements comme l'ensemble des valeurs qui sont communes aux deux événements. Ainsi E = B ∩ C est constitué par l'ensemble des valeurs E = {1 3} .

Une mesure de probabilité P ou plus simplement une probabilité est une application qui associe à chaque élément de S un réel compris entre 0 et 1. P : S → [0,1]

et qui vérifie les propriété suivantes :




A chaque événement A appartenant à l'ensemble S on associe sa probabilité P ( A) . Cette probabilité est positive est inférieure ou égale à 1. 0 ≤ P ( A) ≤ 1




P (∅ ) = 0 et P (S ) = 1




Pour tous les évènements A et B tels que A ∩ B = ∅ alors P( A ∪ B ) = P( A) + P (B )

En déduit alors :

( )

P A = 1 − P ( A)

Pour deux évènements quelconques : P ( A ∪ B ) = P ( A ) + P (B ) − P ( A ∩ B )

Electronique B11

2

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

Enfin, si l'on considère une famille d'événements exclusifs Ai alors : Ai ∩ A j = ∅ ceci ∀i ≠ j

et :

P ∪ Ai  = ∑ P( Ai ) i  i

Exemple : Pour le cas de la roulette considérée chaque valeur a une probabilité

1 2 de "sortir". La probabilité de A est P ( A) = 6 6

et la probabilité de A ∪ B , A et B étant exclusifs est donnée par : P( A ∪ B ) =

2 3 5 + = 6 6 6

Considérons maintenant des ensembles quelconques, c'est à dire pas obligatoirement exclusifs, et plaçons nous dans le cas de deux événements Ai et B j . Dans le cas général on écrit : P( Ai , B j ) = P( Ai ∩ B j ) P( Ai ∪ B j ) = P( Ai ) + P( B j ) − P( Ai ∩ B j )

(∪ = ou , ∩ = et ) 1.1.1

Probabilités conditionnelles

On définit aussi les probabilités conditionnelles. C'est à dire la probabilité d'avoir un événement Ai sachant qu'un autre événement B j est vérifié. Cette probabilité conditionnelle s'écrit P ( Ai B j ) , et elle s'obtient au moyen de l'équation : P ( Ai B j ) =

P ( Ai , B j ) P( B j )

On peut écrire l'équation dans l'autre sens, on obtient alors : P( B j Ai ) =

P ( Ai , B j ) P( Ai )

Exemple : En reprenant les cas de la roulette évoquée précédemment, il vient : 2 2 P (C B) = 6 = 3 3 6

Electronique B11

3

Cnam 1.1.2

INTRODUCTION AUX TELECOMMUNICATIONS Indépendance

L'indépendance statistique de deux événements signifie que la probabilité d'un des deux événements n'est pas influencée par la réalisation ou non réalisation de l'autre événement. Dans le cas de deux événements indépendants Ai et B j , on a donc : P ( Ai B j ) = P ( Ai ) On en déduit alors au moyen des probabilités conditionnelles : P( Ai , B j ) = P ( Ai ) P( B j )

1.2 Variable Aléatoire, densité et fonction de répartition 1.2.1

Variable aléatoire

Si l'on considère un espace S et un élément s ∈ S , on peut définir une fonction X (s ) dont le domaine est S et qui est à valeurs réelles. La fonction X (s ) est appelée une variable aléatoire.

Exemple : Considérons une partie de pile ou face. L'espace S contient deux points P(ile) et F(ace). S = {P F } On peut alors définir une fonction X (s ) de la manière suivante :

1 ( s = P ) X ( s) =  − 1 ( s = F ) Les exemples présentés jusqu'alors ont toujours considéré un ensemble S comportant un nombre fini de valeurs. On parle alors de variables aléatoires discrètes. Cependant l'ensemble S peut très bien être constitué de valeurs continues. On parle alors, pour X ( s ) , de variable aléatoire continue. 1.2.2

Fonction de répartition

On considère alors des événements du type {X ≤ x} , expression dans laquelle x est une valeur réelle entre [−∞ +∞] . La probabilité de cet événement s'écrit alors : F ( x) = P( X ≤ x)

On parle aussi de fonction de répartition pour la fonction F ( x ) 1.2.3

Densité de probabilité

On définit la densité de probabilité p ( x) de la variable aléatoire X comme la dérivée de la fonction de répartition F ( x ) par rapport à x. p( x) =

dF ( x ) x ∈ [−∞ +∞] dx

ou encore F ( x) =

x

∫ p(u )du

x ∈ [−∞ +∞]

−∞

Lorsque l'on est confronté au problème d'estimer la probabilité pour qu'une variable aléatoire X soit comprise dans un intervalle (x1 , x 2 ) avec x 2 > x1 , on considère les deux événements suivants :

Electronique B11

4

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

{X ≤ x 2 } et {X ≤ x1 } On peut alors décomposer l'événement {X ≤ x 2 } en deux événement exclusifs {X ≤ x1 } et {x1 < X ≤ x 2 } On a alors l'équation de probabilité suivante : P ( X ≤ x 2 ) = P ( X ≤ x 1 ) + P ( x1 < X ≤ x 2 ) D'où : F ( x 2 ) = F ( x1 ) + P( x1 < X ≤ x 2 ) P( x1 < X ≤ x 2 ) = F ( x 2 ) − F ( x1 ) x2

P( x1 < X ≤ x 2 ) =

∫ p( x)dx

x1

1.3 Moments statistiques Si l'on considère une variable aléatoire de densité de probabilité p(x) , on définit la moyenne ou l'espérance de X de la manière suivante : E(X ) = m X =

+∞

∫ xp( x)dx

−∞

On définit la variance de X par : Var ( X ) = σ 2X = E ( X − m X

)2

=

+∞

∫ (x − m X )

2

p ( x)dx

−∞

( )

En développant l'expression précédente, on montre que σ 2X = E X 2 − m 2X

On démontre facilement les propriétés suivantes : Soit X i un ensemble de variables aléatoires, alors :   E ∑ X i  = ∑ E( X i )    i  i En introduisant un coefficient scalaire α , on a : E (αX i ) = αE ( X i ) Var (αX i ) = α 2Var ( X i ) Dans le cas de variables aléatoire X i indépendantes :

  Var  ∑ X i  = ∑ Var ( X i )    i  i

1.4 Quelque lois usuelles 1.4.1

Variable aléatoire uniforme

Une variable aléatoire uniformément répartie entre [0 + a ] est une variable aléatoire continue à valeurs dans [0 + a ] dont la densité de probabilité est de la forme :

Electronique B11

5

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS 1 , x ∈ [0 + a ] a p( x) = 0 , x ∉ [0 + a ]

p( x) =

Le calcul de l'espérance donne : +∞

1 E ( X ) = ∫ xp( x)dx = a −∞

+a

1  x2  xdx =   ∫ a  2  0

+a

a 2

= 0

Le calcul de la variance donne : Var ( X ) =

+∞

2 ∫ x p( x)dx =

−∞

1.4.2

1 a

+a

2 ∫ x dx =

0

1  x3    a  3 

+a

= 0

a2 3

Variable aléatoire gaussienne

Une variable aléatoire gaussienne est une variable aléatoire continue prenant valeur dans [−∞ +∞] et dont la densité de probabilité est de la forme : −( x − m X )2

p( x) =

1

e

2 σ 2X

2πσ 2X

, x ∈ [− ∞ + ∞ ]

La densité gaussienne est exprimée au moyen de la moyenne m X et de la variance σ 2X . La loi est dite centrée si la moyenne est nulle et réduite si la variance est égale à 1.

1.4.3

Variable aléatoire exponentielle

Une variable aléatoire exponentielle est une variable aléatoire continue prenant valeur dans [0 +∞] et dont la densité de probabilité est de la forme : p( x) = 0 , x < 0 p ( x ) = λ e − λx , x ≥ 0 Le calcul de la moyenne et de la variance sont présentés dans le cours sur les modèles de trafic.

E(X ) =

1 λ

( )

2

E X2 =

λ2

( )

Var ( X ) = E X 2 − E ( X )2 = 1.4.4

1 λ2

Variable aléatoire binomiale

Une variable aléatoire binomiale est une variable aléatoire discrète prenant valeur dans {0 1} définie par les probabilités suivantes : P( X = 0) = 1 − p P( X = 1) = p Le calcul de l'espérance donne :

Electronique B11

6

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS E ( X ) = 0.(1 − p ) + 1. p = p Var ( X ) = (0 − p )2 .(1 − p ) + (1 − p )2 . p = p − p 2

2 Chaîne de Markov Un processus stochastique {X (t )}t∈T est une fonction du temps dont la valeur à chaque instant dépend de l'issue d'une expérience aléatoire. A chaque instant t ∈ T , X (t ) est donc une variable aléatoire. Si l'on considère un temps discret on note alors {X n }n∈N un processus stochastique à temps discret. Si l'on suppose enfin que les variables aléatoires X n ne peuvent prendre qu'un ensemble discret de valeurs, on parlera de processus à temps discret et à espace d'état discret. Ce paragraphe va aborder les processus à temps discret et à espace d'état discret. Le chapitre sur le télétrafic abordera pour sa part les processus à temps continu et à espace d'état discret.

2.1 Définition d'une chaîne de Markov

{X n }n∈N

est une chaîne de Markov à temps discret si et seulement si : P (X n = j X n −1 = i n −1 , X n − 2 = i n − 2 ,..., X 0 = i0 ) = P (X n = j X n −1 = i n −1 )

La probabilité pour que la chaîne soit dans un certain état à la n ième étape du processus ne dépend donc que de l'état du processus à l'étape précédente (la n − 1ième ) et pas des états dans lequel il se trouvait aux étapes antérieures. On définira une chaîne de Markov comme homogène lorsque cette probabilité ne dépend pas de n. On peut alors définir la probabilité de transition d'un état i vers un état j notée p ij :

p ij = P (X n = j X n −1 = i ) ∀n ∈ N En introduisant l'ensemble des états possibles noté E, on a :

∑ pij

=1

j∈E

[ ]

On définit alors la matrice de transition P = p ij i , j∈E

 p11  p P =  21 M   M 

Electronique B11

p12 p 22

K p 23

p 32

O

K     O

7

Cnam 2.1.1

INTRODUCTION AUX TELECOMMUNICATIONS Représentation sous forme de graphes

Les chaînes de Markov peuvent être représentées graphiquement sous la forme d'un graphe orienté. On associe alors un nœud à chaque état et un arc orienté à la probabilité de transition.

Exemple

p12

p23

2 p31

1

p33

3 p14

p41 4

Dans cet exemple on a : L'ensemble des état est E = {1,2,3,4} L'analyse du graphe permet de déterminer immédiatement : p 23 = p 41 = 1 Ainsi que : p12 + p14 = 1 et p 31 + p 33 = 1 La matrice de transition s'écrit : p12 0 p14   0   0 0 1 0   P= p 0 p 33 0   31   1 0 0 0  

2.1.2

Régime transitoire

L'analyse du régime transitoire d'une chaîne de Markov consiste à déterminer le vecteur p(n) des probabilités d'être dans un état j à l'étape n :

[

p( n ) = p1 ( n )

p2 ( n ) K

]

p Card ( E ) ( n )

Ce vecteur de probabilités dépend :
de la matrice de transition P
du vecteur de probabilités initiales p(0 ) Pour étudier ce vecteur de probabilité on peut faire les remarques suivantes : p j ( n ) = P[ X n = j ] or

P[X n = j ] =

∑ P[X n =

i∈E

]

j X n −1 = i . P[X n −1 = i ]

ce qui s'écrit encore : p j ( n) =

∑ p ij . pi (n − 1)

i∈E

ce qui peut s'écrire matriciellement : p(n) = p(n − 1).P

Electronique B11

8

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

En utilisant n fois cette expression, il vient : p(n) = p (0).P n On peut aussi introduire la probabilité de transition de l'état i à l'état j en m étapes, notée p ij( m) :

[

]

p ij( m) = P X n + m = j X n = i ∀n ∈ N 2.1.3

Classification des états

Une chaîne de Markov est dite irréductible si et seulement si de tout état i on peut atteindre tout état j en un nombre fini d'étapes : ∀i, j ∈ E , ∃m > 1 / p ij( m) ≠ 0 Une chaîne de Markov est dite absorbante si il existe une sous chaîne d'états dont on ne peut plus ressortir. Toute chaîne non, irréductible possède donc au moins une sous chaîne absorbante. La chaîne suivante possède une la chaîne absorbante {4,5} :

p23

2

p12 p31

1

p33

3 p14 p45

Sous chaîne absorbante

4

5 p54

Un état j est périodique si on ne peut y revenir qu'après un nombre d'étapes multiple de k > 1 :

∃k > 1 / p (jjm) = 0 pour m non multiple de k La période d'une chaîne de Markov est le PGCD de la période de chacun de ses états. Une chaîne de Markov est dite périodique si sa période est supérieure à 1. Dans le cas contraire, elle est dite apériodique.

2.1.4

Quelques probabilités

On introduit la probabilité f jj( n ) qui est la probabilité de revenir à l'état j , n étapes après l'avoir quitté. La probabilité

f jj de revenir en j après l'avoir quitté s'écrit alors : f jj =

∞

∑ f jj

n =1

On peut alors introduire le temps moyen de retour à l'état j , M

Electronique B11

(n)

j

:

9

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS ∞

∑ n. f jj

Mj = On introduit la probabilité

f ij( n )

( n)

n =1

qui est la probabilité d'aller de l'état i à l'état j en exactement n étapes (s'en repasser de

manière intermédiaire par j). On a alors de manière immédiate :

 f (1) = p ij  ij  ( n) ( n −1) ,n≥2  f ij = ∑ p ik f kj k≠ j  On introduit enfin la probabilité f ij d'aller de l'état i à l'état j en un nombre quelconque d'étapes :

f ij =

∞

∑ f ij

( n)

n =1

En utilisant les équations précédentes, il vient : (1)

f ij = f ij

f ij = p ij +

f ij = p ij +

∞

∑ f ij

( n)

n=2 ∞

( n −1)

∑ ∑ pik f kj

n = 2k ≠ j

∑ p ik

k≠ j

f ij = p ij +

2.1.5

+

∞

∑ f kj(n−1)

n=2

∑ pik f kj

k≠ j

Régime permanent

L’analyse du régime permanent consiste à s’intéresser à la limite, lorsque n tend vers l’infini du vecteur des probabilités p(n) . Cette limite existe-t-elle et comment la calculer ? Pour répondre à cette question, il faut calculer le vecteur p(n) = p (0) P n et faire tendre n vers l’infini. Pour calculer P n , il peut être avantageux de diagonaliser la matrice P :

P = UDU −1 expression dans laquelle U représente la matrice des vecteurs propres de P et D la matrice diagonale des valeurs propres associées. Il est alors aisé d’obtenir :

P n = UD nU −1 Le régime stationnaire existe si lim p(0 ).UD nU −1 existe. n →∞

On peut montrer (la démonstration n’est pas présentée dans ce polycopié), que pour une chaîne de Markov irréductible et apériodique, le vecteur p des probabilités limites p j = lim p j (n) existe toujours et est indépendant du vecteur des n →∞

probabilités initiales p(0 )

Electronique B11

10

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

2.2 Récapitulatif p ij probabilité de transition de l'état i à l'état j.

[ ]

P = p ij matrice des probabilités transition. p(n) vecteur de probabilités d'états après n étapes. p(0 ) vecteur de probabilités d'état à l'origine. p(n) = p(0 ).P n p ij(n) probabilité d'aller de l'état i à l'état j en n étapes. f jj(n) probabilité de revenir en j, n étapes après l'avoir quitté M j temps moyen de retour en j

f ij(n) probabilité d'aller de i à j, en exactement n étapes, c'est à dire s'en repasser de manière intermédiaire par j. f ij probabilité d'aller de l'état i à l'état j en un nombre quelconque d'étapes :

3 Télétrafic Ce chapitre présente les principaux résultats qui permettent de dimensionner les équipements d'un réseau de Télécommunications. D'un point de vue pratique, on imagine bien que, lorsqu'un central téléphonique (commutateur local CL) regroupe les lignes d'un ensemble d'immeubles dans une ville, ce central ne possède pas autant de lignes allant vers le réseau que de lignes allant vers les différents particuliers qu'il dessert.

Central Téléphonique M lignes

N t ) Or Prob(τ > t ) représente la probabilité qu'il n'y ait aucune arrivée d'appels durant un temps t. Cette probabilité a justement été établie au paragraphe précédent : Prob(τ > t ) = p 0 Prob(τ > t ) = e −λt On en déduit donc : A(t ) = 1 − e −λt

Electronique B11

14

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

On peut aussi introduire la densité de probabilité de la variable aléatoire τ . On rappelle que la densité s'obtient simplement en dérivant la probabilité par rapport à t. On obtient ainsi :

∂A(t ) ∂t

a(t ) = d'où :

a(t ) = λe −λt

Remarque : On rencontre plus souvent le calcul inverse, c'est à dire compte tenu d'une densité de probabilité a (t ) , t

A(t ) = ∫ a (u )du . On part de 0 car il s'agit d'une durée entre deux appels. On peut vérifier que l'intégrale donne alors 0

[

]

t

A(t ) = − e −λu 0 = 1 − e −λt L'expression de la densité de probabilité permet de calculer la durée moyenne τ = E [τ] entre deux arrivées d'appel :

E [τ] =

+∞

∫ t.a(t )dt

0

E [τ] =

+∞

∫ λte

− λt

dt

0

En intégrant par partie, il vient : +∞

 − 1 − λt  E [τ] = λt. e  λ  0

+

+∞

∫

0

λ.

− 1 − λt e dt λ

D'où :

E [τ] =

1 λ

On obtient donc que, pour un taux d'arrivée d'appels de λ appels par secondes, le temps moyen entre appel est égal à

1 λ

Absence de mémoire du processus d'arrivée d'appels On peut remarquer que, pour une loi exponentielle négative, le nombre d'appels qui ont pu arriver jusqu'à un temps t 0 n'a pas d'influence sur le nombre d'appels qui vont arriver après t 0

Supposons qu'aucun appel ne soit arrivé jusqu'à un temps t 0 et calculons la probabilité qu'un appel arrive durant une durée t après le temps t 0 . On doit donc calculer la probabilité d'avoir une durée entre deux appels inférieure à t + t 0 tout en étant supérieure à t 0 . Cette probabilité s'écrit : prob(τ ≤ t + t 0 τ > t 0 ) . En utilisant la formule de Bayes sur les probabilités conditionnelles (P( A B) P( A) = P( A et B ) ) , il vient :

prob(τ ≤ t + t 0 τ > t 0 ) =

prob(t 0 < τ ≤ t + t 0 ) prob(τ > t 0 )

Cette probabilité peut encore s'écrire

Electronique B11

15

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS prob(τ ≤ t + t 0 τ > t 0 ) =

prob(τ ≤ t + t 0 ) − prob(τ ≤ t 0 ) prob(τ > t 0 )

prob(τ ≤ t + t 0 τ > t 0 ) =

prob(τ ≤ t + t 0 ) − prob(τ ≤ t 0 ) 1 - prob(τ ≤ t 0 )

En reprenant les expressions des différentes probabilités :

prob(τ ≤ t + t 0 τ > t 0 ) =

1 − e −λ (t +t0 ) − 1 + e −λt0 1 - 1 + e -λt0

D'où finalement :

prob(τ ≤ t + t 0 τ > t 0 ) = 1 − e −λt On voit donc que la probabilité d'apparition d'un appel durant un temps t après une durée t 0 pendant laquelle aucun appel n'est arrivé est la même que la probabilité d'apparition d'un appel pendant une durée t, indépendamment de ce qui a pu arriver avant. On considère donc que la densité exponentielle négative est sans mémoire.

3.2 Loi de probabilité de modélisation des durées d'appels Pour étudier les lois de probabilité qui modélisent les durées des appels on procède comme précédemment. On considère donc un intervalle de temps de durée t que l'on décompose en n sous intervalles de durée

t . On choisit n de n

telle sorte que les hypothèses suivantes restent justifiées : -

La probabilité qu'un appel se termine durant un sous intervalle est proportionnelle à la durée du sous intervalle. On notera

-

µt cette probabilité, expression dans laquelle µ représente le coefficient de proportionnalité. n

La probabilité qu'un appel se termine durant un sous intervalle est indépendante du sous intervalle considéré

On introduit alors une variable aléatoire θ représentant la durée d'un appel. On introduit alors la probabilité H (t ) que la durée d'un appel soit inférieure ou égale à t.

H (t ) = Prob(θ ≤ t ) La probabilité qu'un appel ayant débuté à t = 0 ne se termine pas avant t s'écrit alors :

Prob(θ > t ) = 1 − H (t ) cette probabilité est égale à la probabilité que l'appel ne se termine dans aucun des n sous intervalles de durée

t  1 − H (t ) =  1 − µ  n 

t . n

n

En faisant alors tendre n vers l'infini, on obtient :

t  1 − H (t ) = lim  1 − µ  n n →∞  1 − H (t ) = lim

n →∞

t  n.Ln 1−µ  n   e

n

≈ lim

n→∞

 t n. −µ  e  n

D'où

1 − H (t ) = e −µt

Electronique B11

16

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

On obtient donc l'expression de la probabilité qu'un appel ait une durée inférieure ou égale à t :

H (t ) = 1 − e −µt On peut en déduire la densité de probabilité associée, notée h(t ) :

h(t ) =

∂H (t ) ∂t

h(t ) = µe −µt De la même que dans les paragraphes précédents, la durée moyenne θ = E [θ] d'appel s'obtient en calculant :

E [θ] =

+∞

∫ t.h(t ).dt

0

En intégrant par partie on obtient :

E [θ] =

1 µ

En conclusion on a µ appels qui cessent par secondes et on a une durée moyenne d'appel égale à

1 µ

Les probabilités d'apparition d'appels et de fin d'appels qui ont été développées dans les deux paragraphes précédents permettent de modéliser le processus complet d'apparition et de fin d'appels.

3.3 Modélisation des processus d'apparition et de fin d'appels A chaque instant un certain nombre d'appels vont apparaître et d'autres vont se terminer. On peut donc modéliser l'état où l'on se trouve à un instant donné comme une chaîne d'états. Chaque état représente le nombre de communications en cours. On conçoit donc bien que si, à un instant donné, il y a k communications on ne peut passer que dans deux états adjacents qui sont les états k − 1 et k + 1 . On reconnaît alors une chaîne de Markov. La différence par rapport au chapitre 1 vient ici du fait que cette chaîne est à temps continu. La probabilité de passer d’un état i à un état j pendant un temps dt sera donc notée p ij (dt )

On introduit alors les probabilités de transition d'état suivantes : Etant dans l'état k, la probabilité p k ,k +1 (dt ) pour passer à l'état k + 1 durant un intervalle de temps dt s'écrit λ k dt Etant dans l'état k, la probabilité p k ,k −1 (dt ) pour passer à l'état k − 1 durant un intervalle de temps dt s'écrit µ k dt

Etant dans l'état k + 1 , la probabilité p k +1,k (dt ) pour passer à l'état k durant un intervalle de temps dt s'écrit µ k +1 dt Etant dans l'état k − 1 , la probabilité p k −1,k (dt ) pour passer à l'état k durant un intervalle de temps dt s'écrit λ k −1 dt λ k −1 dt

k-1

k µ k dt

Electronique B11

λ k dt

k+1 µ k +1 dt

17

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

Les grandeurs λ k et µ k sont des taux d'apparition et de fin d'appels du même type que ceux utilisés lors des paragraphes précédents. La seule différence tient au fait que ces taux ont en indice l'état où se trouve le système.

On peut alors introduire la probabilité d'état, c'est à dire la probabilité d'être dans un état k à un instant t. Notons p k (t ) cette probabilité (à rapprocher de la notation p j (n) utilisée pour les chaînes de Markov à temps discret lors du

chapitre 2).

La variation de cette probabilité durant un intervalle de temps dt est alors égale à la probabilité de rejoindre cet état en "venant" d'un état k − 1 ou d'un état k + 1 moins la probabilité de "quitter" cet état pour aller vers un état k − 1 ou vers un état k + 1 .

On a donc : dp k (t ) = λ k −1 dt. p k −1 (t ) + µ k +1 dt. p k +1 (t ) − (λ k dt + µ k dt ) p k (t

En supposant le système stable, c'est à dire en supposant qu'il se stabilise sur des probabilités d'état fixes lorsque le

dp k (t ) = 0 lorsque t → ∞ dt

temps tend vers l'infini, on peut écrire On peut alors noter p k = p k (t ) D'où finalement :

λ k −1 . p k −1 + µ k +1 . p k +1 − (λ k + µ k ) p k = 0

Cette équation est vérifiée pour tout k ≥ 0 avec les conditions p −1 = 0 , λ −1 = 0 et µ 0 = 0 . La stabilité des probabilités signifie qu'il y a une probabilité égale de quitter l'état p k que de le rejoindre. En écrivant le système d'équation précédent, on trouve : µ 1 p1 = λ 0 p0

λ 0 p0 + µ 2 p 2 = (λ 1 + µ 1 ) p1

λ 1 p1 + µ 3 p 3 = (λ 2 + µ 2 ) p 2 ... En résolvant le système on trouve :

p1 =

λ0 p0 µ1

  λ λ λ  (λ 1 + µ 1 ) 0 p0 − λ 0 p0  = 1 0 p0 µ1   µ 2µ1  λ λ λ λ λ λ 1   (λ 2 + µ 2 ) 1 0 p0 − λ 1 0 p0  = 2 1 0 p0 p3 = µ3  µ 2µ1 µ1  µ 2µ 2µ1 p2 =

1 µ2

... On trouve alors assez facilement la forme générale :  k −1 λ  p k =  ∏ i  p0    i =0 µ i +1  Le système se trouvant obligatoirement dans un des états on a : +∞

∑ pk

=1

k =0

Electronique B11

18

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

En remplaçant dans l'équation précédente, on obtient : 1

p0 =

∞ k −1

λi

∑∏µ

1+

k =1 i =0

i +1

3.4 Probabilité de blocage et formule d'Erlang B On s'intéresse ici à un système disposant de N canaux de communications. Si les N canaux sont occupés, les appels qui arrivent alors sont perdus (absence de tonalité ou tonalité d'occupation par exemple). On parle alors de blocage du système. On va chercher à estimer cette probabilité de blocage en fonction du nombre de canaux disponibles et du trafic. Compte tenu de ce qui a été énoncé sur le caractère sans mémoire du processus d'arrivée d'appels, on peut considérer que la probabilité λ k dt et indépendante de l'état du système, d'où : λ k .dt = λ.dt , ∀k ≤ N − 1

Pour la probabilité de fin d'appel on a par contre : µ k .dt = k .µ.dt , ∀k < N

Cette probabilité de transition traduit juste que si k appels sont en cours chacun a une probabilité µdt de se terminer, d'où la somme qui donne kµ.dt . En toute rigueur il faudrait soustraire à cette probabilité les probabilités

correspondantes à plusieurs appels qui se terminent dans l'intervalle dt car alors, on passe directement à un état plus k

éloigné. Cependant on admettra que l'on peut négliger ces probabilités qui sont de la forme

∑ C ki (µdt )i

.

i =2

En utilisant ces expressions de λ k et de µ k dans les équations donnant p k et p0 , il vient : 1

p0 = 1+

N k −1

λ

∑ ∏ (i + 1)µ

k =1 i =0

1

p0 = 1+

k

λ 1 ∑  µ  k! k =1  N

En introduisant alors la variable : A=

λ µ

qui représente le nombre d'appels qui apparaissent sur le nombre d'appels qui se terminent pendant un intervalle de temps, ce qui représente en fait tout simplement le trafic, il vient : 1

p0 = 1+

Ak k =1 k! N

∑

ou encore en introduisant le 1 dans la sommation : p0 =

1 Ak k =0 k! N

∑

En reportant alors dans l'expression de p k , il vient :

Electronique B11

19

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS Ak p k = k! N Ai ∑ i! i =0

La probabilité de blocage d'un système disposant de N canaux et pour un trafic A s'écrit alors E ( A, N ) , elle est égale à la probabilité de se trouver dans l'état N E ( A, N ) = p N et elle s'obtient grâce à l'équation suivante : AN E ( A, N ) = N ! N Ai ∑ i! i =0

    ( ) E A , N − 1  E ( A, N ) =  N   + E ( A, N − 1)   A  

Cette formule est très importante en Télécommunications et elle porte le nom de : formule d'Erlang-B. Pour les grandes valeurs de N on peut approcher le dénominateur par e A et la formule devient : E ( A, N ) =

AN −A e N!

3.5 Probabilité de mise en attente et formule d'Erlang C Si l'on considère un système pour lequel les appels bloqués peuvent être mis en file d'attente avant d'être servis, on peut alors définir une probabilité d'être mis en attente. Avec ce système on a toujours λ k .dt = λ.dt mais, pour la probabilité de fin d'appel on a par contre :

k .µ.dt , ∀0 ≤ k ≤ N µ k .dt =   N .µ.dt , k ≥ N En utilisant :  k −1 λ  p k =  ∏ i  p0    i =0 µ i +1  On obtient, pour k > N : k −1  N −1 λ λ  pk =  ∏ p ∏   0  i =0 (i + 1)µ i = N Nµ 

 A N Ak −N pk =  .  N! N k − N 

  p0  

D'où finalement :  Ak p , ∀0 ≤ k ≤ N   k! 0 pk =  k A N −k p0 , ∀k > N  N ! N En utilisant l'expression de p0 :

Electronique B11

20

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS 1

p0 =

∞ k −1

λi

∑∏µ

1+

k =1 i =0

i +1

et en décomposant la sommation, il vient : 1

p0 = 1+

N −1 k −1

∞ N −1

λ

k −1

λ

λ

+ ∑ ∏ ∑∏ ∏ k =1 i =0 (i + 1)µ k = N i =0 (i + 1)µ i = N Nµ

p0 =

1 N −1

A Ak 1 + ∑ k −N k =0 k! k = N N! N

∑

p0 =

1 ∞ Ak−N A A + ∑ N! k = N N k − N k =0 k!

N −1

∑

p0 =

∞

k

k

N

1 N −1

Ak A N ∞  A  ∑ k! + N ! ∑  N   k =0 k =0

k

∞ A A 1   < 1 donc ∑   = A N N  k =0 1− N

k

or

p0 =

1 N −1

k

A AN 1 + ∑ k! N ! A k =0 1− N

La probabilité de mise en file d'attente se note C ( N , A) et elle est égale à

∞

∑ pk

k=N

D'où : C ( N , A) =

∞

A k N −k N p0 k = N N!

∑

Cette formule est aussi très importante et elle porte le nome de : formule d'Erlang-C

3.6 Cas d'une population finie et distribution d'Engset Les calculs précédents ont considéré le cas d'un trafic de type Poisson généré par une population infinie. Si l'on considère maintenant le cas d'une population finie constituée de M clients, la probabilité d'apparition d'appels et fonction du nombre d'appels déjà en cours. On se retrouve alors avec la configuration suivante (on se replace ici dans un cas sans mise en file d'attente, où les appels sont perdus lorsque tous les canaux sont occupés et avec M>N) : λ k .dt = (M − k ).λ.dt , ∀k ≤ N − 1 La probabilité de fin d'appel reste inchangée : µ k .dt = k .µ.dt , ∀k < N La probabilité p k devient alors :

Electronique B11

21

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS  k −1 ( M − i )λ   p0 pk =  ∏   ( i + 1 ) µ  i =0  pk =

M! A k p0 ( M − k )! k!

D'où : k pk = C M A k p0

Pour p0 , on obtient : 1

p0 = 1+

N k −1 ( M

− i )λ ( i + 1)µ k =1 i =0

∑∏

d'où : p0 =

1 N

∑ C Ni A i

i =0

Soit en remplaçant dans l'expression de p k : pk =

k CM Ak N

∑ C Mi A i

i =0

Cette formule représente la distribution d'Engset

4 Files d'attente 4.1 File d'attente simple Les premiers paragraphes de ce document ont essentiellement, à l'exception de l'analyse de la mise en file d'attente, considéré un trafic de nature téléphonique. Si l'on s'intéresse maintenant à un trafic de données on peut considérer que dans un échange d'informations entre deux applications on va souvent rencontrer un écart de débit entre les systèmes locaux et les liens d'interconnexion. Les messages ne pourront pas tous être transmis et vont être mis en file d'attente.

Application A

Application B

Les files d'attente sont en général décrites au moyen d'une notation dite de Kendall qui est la suivante :

Electronique B11

22

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS A/B/C/K/m/Z

Six facteurs sont ainsi précisés : A : qui représente le processus d'entrée B : qui représente le processus de service C : qui représente le nombre de serveurs K : qui représente la capacité maximale m : qui représente la population des usagers Z : qui représente la discipline de service

Pour décrire les processus d'entrée (lettre A), on utilise les notations suivantes : GI : loi générale indépendante G : loi générale Hk : loi hyperexponenetielle d'ordre k Ek : loi d'Erlang k M : loi exponentielle D : loi constante On s'intéressera essentiellement ici à des arrivées de type exponentielle et de paramètre λ . Les autres lois d'arrivée ont moins d'intérêt dans le cadre de ce cours. Il a été vu que la loi exponentielle était sans mémoire et que le processus d'arrivée pouvait donc être considéré comme un processus Markovien. C'est cette propriété qui explique l'emploi de la lettre M pour la loi exponentielle.

Les principales méthodes de service sont les suivantes : PAPS : premier arrivé, premier servi (terme anglais FIFO, first in first out) DAPS : dernier arrivé premier servi (terme anglais LCFS, last come fisrt served) A : aléatoire (terme anglais FIRO : first in random out)

Lorsque les trois derniers éléments de la notation de Kendall ne sont pas précisés, il est sous entendu que Z=PAPS, m = +∞ et K = +∞ .

Si les instants d'arrivée suivent un loi exponentielle de paramètre λ , il en est de même pour les instants de départ des données en sortie de la file d'attente. Ces instants forment aussi un processus Markovien. Enfin dans le cas où l'on suppose enfin qu'il n'y a qu' 1 seul processeur pour gérer la file d'attente, cette dernière est dite de type :

M/M/1.

Dans un système M/M/1, on définit le temps de queue t q comme étant la somme du temps d'attente t a et du temps de service t s . tq = ta + ts

Electronique B11

23

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS file d'attente

unité de traitement

ts

ta

tq

On définit alors la charge c du système comme le rapport entre le nombre d'items à traiter divisé par la capacité de traitement du système en item. Cette capacité de traitement est aussi appelée le taux de service : S. C'est tout simplement l'inverse du temps de service. On a donc : S=

1 λ et c = ts ts

On rappelle que λ est le paramètre de la loi des instants d'arrivée et que c'est aussi le taux d'arrivée de paquets par secondes dans la file d'attente. Si on introduit la capacité de traitement du système D en bits/sec et que L représente la taille moyenne des paquets en bits, alors : S=

1 D = ts L

En remplaçant dans l'expression de la charge c, on obtient : c=

λL D

On peut montrer que le temps d'attente dans la file d'attente t a se déduit du temps de service t s et de la charge c par la formule suivante : ta =

c ts 1− c

Si l'on considère le temps passé dans la queue t q , on obtient finalement :     c  1   1  L = L tq = ta + t s = 1 + t s =  t s =  λL  D D − λL   1− c   1− c   1−  D   On suppose ici que le débit D en bits/sec est supérieur au taux d'arrivée λL en bits/sec. Dans le cas contraire la file d'attente déborde et le temps dans la queue n'est plus déterminé. On rencontre assez souvent cette formule sous la forme :

Electronique B11

24

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

tq =

1 D −λ L

t q : temps passé dans la queue en secondes

D : débits de transmission en bits par secondes L : taille moyenne des paquets en bits λ : taux d'arrivée de paquets en paquets/sec

4.2 File d'attente en série Lorsque deux files d'attente sont en série, si la première file d'attente est du type MM1 alors les instants d'arrivée suivent une loi exponentielle et les instants de sortie aussi. L'entrée de la deuxième file d'attente est aussi un processus Markovien. On a donc deux files MM1. Le temps de queue global est la somme des temps de chaque file

4.3 File d'attente à entrées multiples Si on considère une file d'attente connectée à plusieurs sources de trafic alors, à condition d'avoir des messages de même longueur sur toutes les entrées, on peut calculer le temps dans la queue en utilisant une paramètre λ égal à la somme des λ i des différentes entrées. λ = ∑ λi i

5 Conclusion Ce cours a présenté un aperçu des méthodes de modélisation du trafic et des files d'attente. Un certain nombre de formules ont été introduites. Elles permettent de dimensionner un réseau de Télécommunications. Les calculs de probabilité qui y conduisent restent finalement assez simples.

6 Références [1] Foundation of Mobile Radio Engineering, Michel Daoud Yacoub, CRC Press, 1993 [2] Digital Communications, J.G. Proakis, Mc Graw Hill, 1995 [3] Autoformation en télécoms et réseaux, Maxime Maiman, Claude Servin, InterEditions, 1998 [4] Théorie des files d'attente, Bruno Baynat, Hermès, 2000 [5] Probabilités, Nino Boccara, Ellipses, 1995

Electronique B11

25

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS Table d'Erlang B nombre de canaux 1 2 3 4 5 6 7 8 9 10

Niveau de service ( taux de blocage admissible ) 1% 2% 3% 5% 10% 20% 0.0101 0.0204 0.0309 0.0526 0.1111 0.25 0.1526 0.2235 0.2815 0.3813 0.5954 1 0.4555 0.6022 0.7151 0.8994 1.2708 1.9299 0.8694 1.0923 1.2589 1.5246 2.0454 2.9452 1.3608 1.6571 1.8752 2.2185 2.8811 4.0104 1.909 2.2759 2.5431 2.9603 3.7584 5.1086 2.5009 2.9354 3.2497 3.7378 4.6662 6.2302 3.1276 3.6271 3.9865 4.543 5.5971 7.3692 3.7825 4.3447 4.7479 5.3702 6.5464 8.5217 4.4612 5.084 5.5294 6.2157 7.5106 9.685

nombre de canaux 1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

5.1599 5.876 6.6072 7.3517 8.108 8.875 9.6516 10.437 11.23 12.031

5.8415 6.6147 7.4015 8.2003 9.0096 9.8284 10.656 11.491 12.333 13.182

6.328 7.141 7.9667 8.8035 9.65 10.505 11.368 12.238 13.115 13.997

7.0764 7.9501 8.8349 9.7295 10.633 11.544 12.461 13.385 14.315 15.249

8.4871 9.474 10.47 11.473 12.484 13.5 14.522 15.548 16.579 17.613

10.857 12.036 13.222 14.413 15.608 16.807 18.01 19.216 20.424 21.635

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

12.838 13.651 14.47 15.295 16.125 16.959 17.797 18.64 19.487 20.337

14.036 14.896 15.761 16.631 17.505 18.383 19.265 20.15 21.039 21.932

14.885 15.778 16.675 17.577 18.843 19.392 20.305 21.221 22.14 23.062

16.189 17.132 18.08 19.031 19.985 20.943 21.904 22.867 23.833 24.802

18.651 19.692 20.737 21.784 22.833 23.885 24.939 25.995 27.053 28.113

22.848 24.064 25.281 26.499 27.72 28.941 30.164 31.388 32.614 33.84

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

21.191 22.048 22.909 23.772 24.638 25.507 26.378 27.252 28.129 29.007

22.827 23.725 24.626 25.529 26.435 27.343 28.254 29.166 30.081 30.997

23.987 24.914 25.844 26.776 27.711 28.647 29.585 30.526 31.468 32.412

25.773 26.746 27.721 28.698 29.677 30.657 31.64 32.624 33.609 34.596

29.174 30.237 31.301 32.367 33.434 34.503 35.572 36.643 37.715 38.787

35.067 36.297 37.524 38.754 39.985 41.216 42.448 43.68 44.913 46.147

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

29.888 30.771 31.656 32.543 33.432 34.322 35.215 36.109 37.004 37.901

31.916 32.836 33.758 34.682 35.607 36.534 37.462 38.392 39.323 40.255

33.357 34.305 35.253 36.203 37.155 38.108 39.062 40.018 40.975 41.933

35.584 36.574 37.565 38.557 39.55 40.545 41.54 42.537 43.534 44.533

39.861 40.936 42.011 43.088 44.165 45.243 46.322 47.401 48.481 49.562

47.381 48.616 49.851 51.086 53.322 53.559 54.796 56.033 57.27 58.508

41 42 43 44 45 46 47 48 49 50

Electronique B11

26

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

7 Exercices Exercice 1.

Démontrez que E ( X 2 ) =

2

pour une variable aléatoire de densité exponentielle et de paramètre λ .

λ2

Exercice 2.

On considère un loto avec des tirages de numéros de 1 à 43. Calculez la probabilité d'avoir un numéro qui se termine par 7 sachant que c'est un numéro impair qui a été tiré. Exercice 3.

On considère le mot de verrouillage de trame suivant : 0 1 0 1 1 0

-

En moyenne, au bout de combien de temps, risque t on de rencontrer une séquence de bits identique au mot de verrouillage de trame lorsque l'on considère une transmission à 10 kbits/s.

-

Pour éviter une telle fausse détection, le mot est répété tous les 100 bits et on ne verrouille la trame que si on le rencontre 3 fois successivement. Quelle est la probabilité de faire une fausse détection ?

Exercice 4.

Les chaînes de Markov suivantes sont-elles périodiques : Chaîne n°1

Chaîne n°2 2

2

1

3

4

1

3

4

Chaîne n°3 2

1

3

4

Electronique B11

27

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

Exercice 5.

On considère la chaîne de Markov suivante : 0.6

0.4

1

0.6

0.2

0.6

2

0.2

2

0.4

Donner sa matrice de transition P La chaîne est elle irréductible ? La chaîne est elle apériodique ? Si elle existe donnez la valeur limite du vecteur des probabilités d’états : lim p(n) n →∞

Devoir

Une entreprise industrielle du secteur de l’automobile fait procéder à une enquête auprès des propriétaires d’automobiles. Cette enquête concerne les intentions d’achat. Les propriétaires d’automobiles sont regroupés dans trois classes suivant la cylindrée de leur véhicule. Classe 1 : petite cylindrée Classe 2 : moyenne cylindrée Classe 3 : grosse cylindrée

Sur 10 propriétaires de la classe 1 : 6 resteront fidèles à la petite cylindrée 4 achèteront une moyenne cylindrée Sur 20 propriétaires de la classe 2 : 12 resteront fidèles à la moyenne cylindrée 4 achèteront une grosse cylindrée 4 achèteront une petite cylindrée Sur 15 propriétaires de la classe 3 : 9 resteront fidèles à la grosse cylindrée 6 achèteront une moyenne cylindrée.



Interprétez les résultats de cette enquête à l’aide d’un processus stochastique. Justifiez que ce processus est une chaîne de Markov. Donnez le graphe associé et la matrice de transition P .



Ecrire P sous la forme P = UDU −1



On suppose la distribution initiale des probabilités d’état p (0 ) connue. Que devient ce vecteur de probabilités au bout de n étapes. Vers quelle solution converge ce vecteur lorsque n tend vers l’infini.

Electronique B11

28

Cnam

INTRODUCTION AUX TELECOMMUNICATIONS

Exercice 6.

La capacité d'un autocommutateur public est de 5000 Erlangs. Il dessert des abonnés résidentiels et professionnels respectivement de 40 et 60%. On sait qu'un professionnel a un trafic, à l'heure de pointe, 3 fois supérieur à celui d'un résidentiel qui est supposé égal à 0.1 Erlang. Quel est le nombre d'abonnés desservis. Exercice 7.

Un système à refus (formule d'Erlang-B) dispose de M circuits. Quel est le trafic offert pour que la probabilité de refus soit de 1%, 10%, 50%, lorsque M est respectivement égal à 2,5 ou 10? (Utilisez l'abaque fourni en dehors du poly). Exercice 8.

Deux systèmes de commutation sont reliés par deux faisceaux de 10 circuits chacun. En supposant un taux de perte de 1%, on demande : le trafic autorisé par chaque faisceau ainsi que le rendement de la ligne le trafic total autorisé par les deux faisceaux on regroupe les deux faisceaux en un seul de 20 circuits, en supposant le même taux de perte, quels sont le nouveau trafic autorisé et le rendement par ligne. Exercice 9.

Une PME de 50 personnes souhaite changer son autocommutateur (PABX) et l'affecter uniquement à la téléphonie. Elle dispose des données suivantes : -

il y a 40 postes téléphoniques

-

le trafic mesuré à l'heure de pointe rapporté au poste est le suivant

-

5 mn / heure pour les appels sortant

-

3 mn / heure pour les appels rentrant

-

le trafic moyen est la moitié du trafic de pointe

-

l'activité de l'entreprise est de 8 heures/jour et de 21 jours/mois.

Déterminez -

le trafic total en Erlang

-

le nombre de circuits nécessaires pour écouler ce trafic avec un taux de perte de 10% maximal

Exercice 10.

On considère un système de transmission ayant une capacité de 10kbits/s. On demande le temps passée dans la queue d'une file d'attente MM1 pour un taux d'arrivée λ = 14 s −1 et une taille moyenne de paquet égale à 400 bits. Exercice 11.

On considère un système dans lequel une application dialogue avec une application B à travers une liaison spécialisée de débit D. Déterminez le temps de réponse (ou temps de queue) lorsque les messages allant de A vers B ont une taille moyenne de 900 octets et que ceux de B vers A ont une taille moyenne de 100 octets. On précise qu'il y a 20 transactions par heure et que le débit de la ligne est égal à 19200 bits/s. On admettra que la signalisation accompagnant les données provoque une augmentation de 20% du volume des données échangées.

Electronique B11

29