Note: Pour tracer et générer les graphes, on utilisera la librairie igraph dont documentation est disponible à http://igraph.org/r/doc/

On se donne un graphe d’interférence \(G=(V,E)\) à \(n=|V|\) sommets. Un sommet \(v\in V\) correspond à un éméteur wifi. La présence d’une arrête \((v,t)\in E\) indique que \(v\) et \(t\) ne peuvent pas émettrent en même temps (à cause des interférences générées).

Dans ce projet, on veut étudier le modèle suivant (qui est une approximation du protocole de communication CSMA). Chaque noeud est dans un état actif / non-actif. Initialement, tous les noeuds sont inactifs.

A chaque pas de temps, un noeud est choisit au hazard. - s’il est inactif, il devient actif avec probabilité \(p\in(0,1)\). - s’il est actif, il devient inactif avec probabilité \(q\in(0,1)\)

On note \(X_i(t)\in\{TRUE,FALSE\}\) une variable valant \(TRUE\) si le sommet \(i\) est actif à l’instant \(t\) et \(X(t)=(X_1(t)\dots X_n(t))\) le vecteur d’activation. On note \(N(t)\) le nombre de sommets actifs à l’instant \(t\).

Analyse théorique: le cas de l’étoile et de la ligne

On considère deux graphes d’intéractions suivants: une ligne à \(n\) sommets et une étoile à de \(n\) sommets. On répondra à toutes les questions en prenant \(n=4\) sommets.

Chaîne de Markov?

Le processus \(X\) est-il une chaîne de Markov? Le processus \(N\) est-il une chaîne de Markov? (justifier)

Configurations possibles

Une configuration possible est un vecteur pouvant être atteint par la chaîne de Markov en partant de l’état \((0,0\dots,0)\).

Pour chacun des graphes, donner l’ensemble des configurations possibles et tracer le graphe de transition (pour \(n=4\))?

Irréductibilité

La chaîne \(X\) est-elle irréductible? Apériodique?

Mesure stationnaire

On note \(\rho=p/q\). Exprimer la mesure stationnaire \(\pi_\rho\) en fonction de \(\rho\) (pour l’étoile et la ligne)

Régimes limites

Vers quoi converge la loi \(\pi_\rho\) lorsque \(\rho\to0\) et \(\rho\to\infty\)?

Application numérique

Pour chacun des deux graphes ci dessus, quelle est la proportion du temps pendant laquelle le sommet \(1\)émet? Même question pour le sommet \(2\).

Dans le cas \(\rho=1\).

Dans le cas \(\rho=100\).

Graphe général: analyse théorique et simulation

On cherche maintenant à étudier le protocole sur un graphe général.

Mesure stationnaire

En se servant du fait que le processus est réversible, exprimer la probabilité stationnaire d’une configuration en fonction de \(\rho\).

Quelle est la loi limite lorsque \(\rho\) tend vers \(0\) ou \(\infty\)?

Simulation

set.seed(42)
graphe_random = function (n){return(sample_grg(n, .2, torus=FALSE, coords = TRUE))}
n = 50
p = 0.5
q = 0.5 
g = graphe_random(n)
plot(g)

Une allocation est un vecteur de \(0\) et de \(1\). La fonction “are_adgacent(g,v1,v2)” permet de tester si v1 et v2 sont voisins dans le graphe \(g\).

are_adjacent(g,1,2)
## [1] TRUE

Une allocation est un vecteur de \(\{0,1\}\). On se donne la fonction suivante permettant de tracer une allocation.

plot_graphe= function(g,X){
  plot(g,vertex.color=sapply(X,function(x) ifelse(x,'green','red')))
}
X = rep(0,n);
X[c(3,29,30)] = TRUE
plot_graphe(g,X)

Compléter le code du simulateur ci dessous.

simulateur = function ( g, p, q, T ){
  n = length(g)
  X = matrix(0,T,n)
  N = rep(0,T)
  for (t in (2:T)){
    X[t,]=X[t-1,]
    ## CODE POUR MODIFIER X[t,] ICI 
    
    ## 
    N[t] = sum(X[t,])
  }
  return(list(X,N))
}

Observations

Pour chaque simulation, on fera attention au choix du temps de simulation \(T\). A chaque fois, on comparera une valeur de \(\rho\) petite (par exemple \(\rho=1\)) et une valeur de \(\rho\) grande (par exemple \(\rho=10\)).

Le code suivant montre comment on peut visualiser le résultat d’une simulation:

Étoile

Tracer \(X_1(t)\) et \(X_2(t)\) en fonction du temps. Commenter.

Graphe aléatoire

Tracer \(X_i(t)\) en fonction du temps pour plusieurs valeur de \(i\) que vous choisirez. Tracer \(N\) en fonction du temps. Commenter.

Conclusion

Que pensez vous de l’impact de \(\rho\) sur le protocole (en terme d’efficacité et d’équité entre les différents utilisateurs)

MISC: visualisation sans igraph

graphe = function(N,c){
  X = runif(N)
  Y = runif(N)
  plot(X,Y)
  M = matrix(FALSE,N,N)
  for (i in 1:N) {
    for (j in 1:N) {
      M[i,j] = (X[i]-X[j])**2 + (Y[i]-Y[j])**2 < c
    }
  }
  return(list(X,Y,M))
}
g = graphe(100,.05)
M = g[[3]]
plot_graphe= function(g){
  X = g[[1]]
  Y = g[[2]]
  M = g[[3]]
  plot(X,Y)
  for (i in 1:100){
    for (j in i:100){
      if (M[i,j]){
        lines(X[c(i,j)],Y[c(i,j)])
      }
    }
  }
}
plot_allocation= function(g,alloc){
  X = g[[1]]
  Y = g[[2]]
  plot_graphe(g)
  for (i in 1:100){
    if (alloc[i]){
      points(X[i],Y[i],col="red")
    }
  }
}
plot_graphe(g)
plot_allocation(g, runif(100)<.1)