Mini-Projet 2013

Sujet 2 : Réseau de capteurs

RICM4 SUN Xuan/ZHANG Zhengmeng

Question 2.1: Algorithme de génération 

set.seed(50)
n <- 100  #nombre de capteurs
i <- 1
j <- 1

x <- 1:n  #Création du tableau des valeurs contenant les position des capteurs sur l'axe x
y <- 1:n  #Création du tableau des valeurs contenant les position des capteurs sur l'axe y


for (i in 1:n) {
    x[i] <- runif(1)%/%0.001/1000
    y[i] <- runif(1)%/%0.001/1000
}
# (x[i],y[i]) est la position de la capteur numéro i. la partie '%/% 0.001 /
# 1000' est pour garder que les trois chiffres après la virgule.

# --------------------------------------------------------------------------
# le graphe des positions des capteurs
# --------------------------------------------------------------------------

plot(x[], y[], pch = 19, col = "blue", main = "Les positions des capteurs avec n=100")

plot of chunk unnamed-chunk-1 




# ---------------------------------------------------------------------------
# La Matrice des carrés des distances entre les capteurs
# ---------------------------------------------------------------------------


# d[k,j] est le carré de la distance entre la capteur j et k.  d[k,j] = 0 si
# j = k.  d est la matrice des carrés des distances entre les differents
# capteurs

d <- matrix(nrow = 100, ncol = 100)  #définition de matrice

i <- 1
j <- 1

for (i in 1:n) {
    for (j in i:n) {
        d[i, j] <- (x[i] - x[j])^2 + (y[i] - y[j])^2
    }
}


# ---------------------------------------------------------------------------
# Le Graphe de Connexion
# ---------------------------------------------------------------------------


theta <- 0.1  #2 capteurs à une portée inférieur à theta peuvent échanger des informations
t <- theta^2  #t est le carré de theta 


plot(x[], y[], pch = 19, col = "blue", main = "Le graphe de connexion avec n=100,theta=0.1")  #le graphe de connexion
i <- 1
j <- 1
for (i in 1:n) {
    for (j in i:n) {
        if (d[i, j] < t) {
            segments(x[i], y[i], x[j], y[j], col = "red")
        }
    }
}

plot of chunk unnamed-chunk-1 

# il y a une arête rouge entre capteurs numéro i et j , si la distance entre
# eux est plus petite que theta

Question 2.2 : Connectivité

et

Question 2.3 : portée critique

La probabilité que deux capteurs soient connectées est pa = pi * theta2 / 1,c'est-à-dire que la position d'une capteur tombe dans le cercle dont le centre est l'autre capteur avec demi-diamètre=theta .

Puis,on a trouvé que le graphe de connexion au dessus est un graphe aléatoire,donc cette question 2.2 égale à la connectivité d'un graphe aléatoire.(Avec Chacune des n(n-1)/2 arêtes est présente avec probabilité pa)

Après avoir lu beaucoup d'articles, on a trouvé que la probabilité qu'un graphe aléatoire avec n sommets soit connexe：

pc(n) = 1 - n * qn-1

avec q = 1 - pa

Donc,les graphes de la probabilité pc(n,theta) en fonction de theta:

Quand n = 10

connect <- function(n, theta) {
    pa <- pi * theta^2
    q <- 1 - pa
    pc <- 1 - n * q^(n - 1)
    pc
}

# pour dessiner le graphe de pc en fonction de theta,on génère 100 valeurs
# de pc avec 100 theta différents
n <- 10  #nombre de capteurs
pd <- 1:100  #Création du tableau contenant les valeurs de pc
theta <- 0  #valeur initiale

for (i in 1:100) {
    pd[i] <- connect(n, theta)
    theta <- theta + 0.01

    if (pd[i] > 1) 
        {
            pd[i] <- 1
        }  #la probabilité ne peut pas être supérieur à 1

}


plot(pd, xlab = "100*theta", ylab = "pc", xlim = c(0, 100), ylim = c(0, 1), 
    main = "pc(n,theta) en fonction de theta avec n = 10", type = "n")
lines(pd, col = "red")

plot of chunk unnamed-chunk-2 

# Remarque:l'axe x n'est pas la valeur de theta,c'est la valeur de
# 100*theta.

Quand n = 20

On dessine le graphe de même façon： 

n <- 20
pd <- 1:100  #Création du tableau contenant les valeurs de pc
theta <- 0  #valeur initiale

for (i in 1:100) {
    pd[i] <- connect(n, theta)
    theta <- theta + 0.01
    if (pd[i] > 1) 
        {
            pd[i] <- 1
        }  #la probabilité ne peut pas être supérieur à 1
}

plot(pd, xlab = "100*theta", ylab = "pc", xlim = c(0, 100), ylim = c(0, 1), 
    main = "pc(n,theta) en fonction de theta avec n = 20", type = "n")
lines(pd, col = "green")

plot of chunk unnamed-chunk-3 

# Remarque:l'axe x n'est pas la valeur de theta,c'est la valeur de
# 100*theta.

Quand n = 100

On dessine le graphe de même façon：

n <- 100
pd <- 1:100  #Création du tableau contenant les valeurs de pc
theta <- 0  #valeur initiale

for (i in 1:100) {
    pd[i] <- connect(n, theta)
    theta <- theta + 0.01
    if (pd[i] > 1) 
        {
            pd[i] <- 1
        }  #la probabilité ne peut pas être supérieur à 1
}

plot(pd, xlab = "100*theta", ylab = "pc", xlim = c(0, 100), ylim = c(0, 1), 
    main = "pc(n,theta) en fonction de theta avec n = 100", type = "n")
lines(pd, col = "purple")

plot of chunk unnamed-chunk-4 

# Remarque:l'axe x n'est pas la valeur de theta,c'est la valeur de
# 100*theta.

Selon les 3 graphes au dessus,on voit que pc(n,theta) varient tous brutalement à partir de d'une certaine valeur theta.

Question 2.4:Couverture

pour n et theta fixé la probabilité qu'un point à distance r du centre soit couvert

c'est-à-dire que parmi les n capteurs, il y a au moins une capteur dont la position tombe dans le cercle avec le point choisi comme centre et theta comme demi-diamètre.

donc la probabilité pr est: pr = 1 - po, po est la probabilité que toutes les n capteurs soient hors du cercle .


n <- 20
theta <- 0.2

pr <- 1 - (1 - (pi * theta^2/1))^n

pr

## [1] 0.9318