2.4.3 Architecture virtuelle d'un réseau de capteurs
: Algorithme de clustérisation de A. Wadaa et al.
Le protocole présenté ici est celui de la
construction d'une architecture virtuelle des RCSFs [26]. Il permet le
partitionnement d'un RCSF en secteurs et en couronnes de telle sorte
qu'après le partitionnement, chaque capteur ne se retrouve que dans un
seul secteur et une couronne bien précise. Le problème est
qu'initialement, un noeud ou un ensemble de noeuds ne sont pas directement
détectable dans l'espace par la BS, et aucune structure n'était
clairement définie. La solution proposée consiste donc à
la partition du réseau en différentes zone par la BS. Cette
dernière a la possibilité de diffuser des informations avec une
échelle plus ou moins grande, celle-ci étant utilisée pour
créer des couronnes; aussi, elle a la possibilité de diffuser des
informations
26
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
dans certaines directions, afin de créer divers
secteurs angulaires. La zone (i, j) est l'intersection d'un secteur
angulaire j et d'une Couronne i. Les capteurs d'une
même zone sont donc dans le même emplacement géographique et
forme un cluster. Ceci est illustré par la figure 2.7. Pour la suite, le
temps est divisé en slot s1, s2, ...,
sd_1 et on va considérer que
chaque capteur
FIGURE 2.7: Architecture Virtuelle
synchronise son temps avec le sink à interval de temps
régulier. D'autre part, on considère que si le sink émet
un signal et qu'un capteur le reçoit, celui-ci met son bit b1
à 0 et celui qui ne le reçoit pas met le sien à 1.
Partitionnement en couronne
Le partitionnement en couronne permettra à tout capteur
du réseau d'enregistrer l'identité de la couronne dans laquelle
il se trouve. les auteurs supposent que tous les capteurs connaissent le nombre
k de couronnes que l'on souhaite former. Pour cela, chaque capteur
doit déterminer une chaine de log2 k bits afin de
déterminer le numéro de la couronne de rayon ri
avec 1 < i < k à laquelle il appartient. Le
protocole de partitionnement en couronne se déroule comme suit :
Au premier slot, tous les capteurs sont éveillés
et le sink émet une transmission de rayon rk/2
et donc tous les capteurs situés dans les k/2 premières
couronnes mettent leur bit b1 à 0 tandis que les autres mettent
les leurs à 1. Après d - 1 slots, les capteurs auront
appris tous les bits nécessaires au calcul de leur numéro de
secteur. En effet, après avoir appris les bits b1,
b2, . .. , blogk, un
capteur effectue la somme
log k
l = 1 + X bj2log
k_j (2.1)
j=1
qui est le numéro de sa couronne [26].
Partitionnement en secteur
Tout comme précédemment, le partitionnement en
secteur permettra à tout capteur du réseau d'enregistrer
l'identité du secteur angulaire dans lequel il se trouve. On suppose
dans un premier temps que les capteurs connaissent le nombre d de
secteurs que le réseau doit contenir.
27
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
Ensuite, que tous les secteurs obtenus après le
partitionnement doivent couvrir les secteurs 360°
angulaires d'angles d et en fin que le
sink est capable d'effectuer une diffusion angulaire suivant un angle
donné. Ainsi seuls les capteurs situés dans la zone de couverture
recevront le signal. Chaque capteur doit apprendre une chaine de logd
bits afin de déterminer le numéro du secteur dans lequel il
se trouve.
Déroulement :
Au premier slot, tous les capteurs sont éveillés
et le sink émet un signal couvrant rd/2 premiers
secteurs angulaires. Tous les capteurs qui recevront le signal mettront leur
bit b1 à 0 tandis
360°
que les autres mettront les leurs à 1. Posons
á = d et considérons les résultats
obtenus aux lemme 1 et 2.
Corollaire 1. après avoir appris les
bits b1, b2, . .. , bi-1, un
capteur doit se réveiller au temps slot z = 1 + i-1
j=1 cj pour apprendre le bit bi.
d'autre part, au temps z, le sink effectue une transmission correspondant au
secteur angulaire d'angle z * á
conclusion : après d-1 slots, les
capteurs auront appris tous les bits nécessaires au calcul de leur
numéro de secteur. en effet, après avoir appris les bits
b1, b2, .. . , blogd, un
capteur effectue la somme l = 1 + log d
j=1 bj2log d-j qui
est le numéro de sa couronne.
| 
