2.2.4 Poursuite cyclique à L liens
En comparant, dans la partie qui va suivre, les deux techniques
étudiées précédemment, la pour- suite cyclique
hiérarchique donne un taux de convergence plus élevé que
le schéma traditionnel. Cependant, elle demande plus de liens de
communication entre les agents, chaque agent perçoit plus d'un agent
contrairement au traditionnel où chaque agent ne capte que l'agent qui
le suit dans l'ordre. Pour cette raison, un schéma
intermédiaire a été introduit où le nombre de
connexions entre agents est inférieur au schéma traditionnel,
ou plus ou moins contrôlé, et où chaque agent chasse le
FIG. 2-4 - Structure d'une poursuite cyclique de 5 agents
à 2 liens.
centre d'un groupe d'agents.
Dans une poursuite cyclique à L liens, chaque agent
possède un lien de communication avec "L" agents. S'il y a NL agents,
alors il y aura un total de LNL connexions dans le système. La
stratégie que nous adopterons est la suivante :
Dans un système de NL agents, l'agent "i" poursuit le
centre des agents de "i+1" jusqu'à "i+L" (modulo NL). Formellement ceci
s'écrit :
1 L
_zi=
XL m=1
zi+m(modNL) ~ zi i=1, . . . ,NL.
ou sous une forme vectorielle : _zi = Az avec ANLXNL
une matrice circulante de la forme :
,0,...0) (2.17)
| {z }
L uns
circ(--L,1,... 1
1
A= L
Exemple 2.3 Prenons le cas de NL = 5 agents, avec L = 2
(voirFigure e-4). la matrice de transformation A est la suivante :
A = 1 2circ(-2, 1,1,0,0) = circ(-1,1 2,
1 2,0,0).
2.2.5 Comparaison et taux de convergence
Dans cette partie, nous comparerons entre les trois
différentes méthodes de la poursuite cyclique. Cette comparaison
servira à faire une sélection entre les méthodes selon
différents facteurs, elle sera ensuite appuyée par les
résultats de notre simulation au dernier chapitre.
En plus du temps de convergence et de la vitesse moyenne des
agents calculés à la fin de la simulation, un rapport est
calculé pour exprimer l'augmentattion dans le taux de convergence
entre
chaque couple de méthodes : Schéma traditionnel /
l'hiérarchique, hiérarchique / Poursuite cyclique à L
liens et ce dernier / schéma traditionnel.
Définition 2.4 Le taux de convergence des agents
à leur centre est déterminée à partir de la valeur
propre non nulle de A2 avec la partie réelle absolue la plus petite,
nous appellerons cette dernière "valeur 'y".
Définition 2.5 L'augmentation dans le taux de
convergence (R) calculé représente la rapidité de
convergence du groupe d'agents au centre, avec une méthode
comparé à l'autre méthode, c'est un rapport entre les
parties réelles des valeurs 'y des deux différentes
méthodes :
Ï(valeur 'y(m~ethode 1))
R = Ï(valeur 'y(m~ethode 2)) Ï: La partie
réelle du nombre complexe.
Poursuite cyclique traditionnelle / hiérarchique
Soit : NL le nombre d'agents total.
Le taux de convergence correspondant à cette comparaison
est:
Ï(valeur 'yhier)(2.18) Ï(valeur 'ytrad)
RL = traditionnel
hierarchique
Pour trouver la valeur 'y, nous devons d'abord calculer les
valeurs propres de la matrice de transformation correspondant à la
méthode utilisé AL (A1).
D'après 2.15, la matrice Am est une matrice
circulante à blocs, ses valeurs propres sont donc :
VP(Am) = nm[ VP(Am_1 +
(e2~j(r_1)Inm - 1)I)
r=1
donc, les VP(Am) sont les nm ensembles de
VP(Am_1) décalées à gauche par am(r)
= e2~i(r_1)Inm1. Nous remarquons que :
-2< Ï(am(r))<0 Vr=1,...,nm.
car : Ï(om(r)) = cos(2r(r - 1)/nm) -
1. et -1 < cos(2r(r - 1)/nm) < +1.
Pour trouver la valeur 'y, nous devons d'abord déterminer
toutes les valeurs 'y possibles de VP(Am). Ces valeurs 'y
appartiennent aux ensembles des VP avec le décalage à gauche le
plus petit.
- Le premier ensemble des VP(Am), elles sont
simplement les VP(Am_1) décalées par am(1)
= 0, donc les valeurs 'y possibles de cet ensemble sont les valeurs 'y des
VP(Am_1).
- L'ensemble des VP avec le décalage suivant le plus
petit est donné par Am_1 + am(2)I (ou également
am(nm))[1]. Pour cet ensemble, la VP nulle de
Am_1(la VP la plus à droite) est décalée
à gauche de am(2). Elle est donc la valeur 'y de cet
ensemble, et est donnée par:
'ym := e2~jInm - 1
De cette façon, on constitue l'ensemble des valeurs 'y
possibles. Ensuite, la 'y-value des VP(Am) doit être, ou la
valeur 'y des VP(Am_1), ou bien 'ym. Ceci est un
schéma récursif, pour chaque couche ajoutée, une autre VP
est ajoutée à l'ensemble des 'y - values possibles. Plus
concrètement :
Pour la première couche, la valeur 'y des VP(A1) est : 'y1
:= e2~u/n1 - 1.
La deuxième couche, la valeur 'ye des VP(A2) est la valeur
'y des VP(A1) qui n'est autre que 'y1 ou bien : 'y2 := e2~3/n2 - 1.
De même pour la troisième couche, la valeur 'y des
VP(A3) est 'y1, 'y2 ou : 'y3 := e2~3In3 - 1.
...
Pour les VP(Am) la valeur 'y du schéma
hiérarchique à L couches est donnée par:
'y := e2~j' - 1 w = max
m
|
{nm}, m=1,...,L.
|
Pour la poursuite cyclique traditionnelle, il n'existe qu'une
seule couche donc, la valeur 'y est donnée par : 'y := e2~j'NL - 1.
Ainsi, à partir de 2.18 l'augmentation du taux de
convergence utilisant le schéma hiérarchique en comparaison avec
la poursuite cyclique traditionnelle est :
Hi~erarchique R = Traditionnel
|
<(e2~iI -
1) <(e2~iINL - 1)
|
cos(2r/w) - 1 cos(2r/NL) - 1
|
Pour simplifier cette expression, nous remplaçons le cos
par son développement limité de l'ordre
1 avec :
cos(x) = Pn
i=0 (_1)i
(2i)! x2n + o(x2n) à l'ordre 2n avec
o(x2n) -! 0 cos(x) à l'ordre 1 : cos(x) = 1 -
1 2x2. d'où :
1_1 2 (2ir/$)2_1 R 1_ 2 1 (21r/NL)2_1
|
~ 2=$ ) 2 ~NL 2 ~ NL 2
= = =
21r/NL $ maxm{nm}
|
Remarque 2.4 Dans le schéma hiérarchique à
deux couches, le taux de convergence est directement:
max{n1, n2}
NL = min{n1,n2}2
(R2 =
2
Cas particulier: Lorsque n1 = n2 = /N2 les N2 agents convergent
approximativement N2 fois
plus rapidement utilisant le schéma hiérarchique
qu'utilisant la P.C traditionnelle.
.
Remarque 2.5 Pour la distribution optimale des nm,
trouvée précédemment concernant le schéma
hiérarchique général. Et d'après 2.16 Le taux de
convergence est :
~ (
( NL J 2 ~ 2 ~ J 2 ~ 2
L1
NL L
R L = NL ~ N_1IL = N2(L_1)=L
L pNL = = = N
N1/L L L L
L
Dans tous les cas, RL ~ 1 et donc, la convergence au centre
utilisant une hiérarchie se fait plus rapidement que le schéma
traditionnel.
Cependant, le schéma hiérarchique nécessite
plus de liens de communications que le traditionnel, d'où plus de
senseurs => il est donc plus coûteux.
Poursuite cyclique hiérarchique / à liens
De la même manière, nous retrouvons la valeur 'y de
la poursuite cyclique à L liens, pour la comparer à celle du
schéma hiérarchique, et calculer le taux de convergence.
D'après la formule 2.17 et utilisant la forme polynomiale
de la matrice A qui est : A = qc(P) avec : qc(s) = 1
LsL + 1 LsL_1 + ... +
1 Ls - s0,
VP(A) = ~qc(1), qc(w),
qc(w2), ..., qc(wNL_1)~
avec : w = e2~j=NL
La matrice A est circulante, elle possède donc une
seule VP nulle qc(1) et toutes les autres se situent dans la partie
gauche du plan. S.L. Smith [1] a montré qu'il faut que NL » L pour
que la valeur 'y des VP(A) soit donnée par qc(w) = 'y.
XL
1
'y = qc(w) = L(w + w2 + ~ ~ ~ +
wL) - 1 = 1
L
m=1
|
e2~jm=NL - 1
|
et la partie réelle de est :
XL
1
<('y) = L
m=1
|
(cos(2mr/NL)) - 1
|
CHAPITRE 2. DIFFÉRENTES APPROCHES DE LA STRATÉGIE
DE RENDEZ-VOUS 29
Ainsi, le taux de convergence est :
Hi~erarchique R = L-lien
cos(2r/w) - 1
(cos(2mr/NL)) - 1
=
avec w = max{n1, n2, ..., nL}
1 L
PL m=1
Toujours en utilisant le développement limité du
cosinus, simplifions cette expression :
1_1 2 (2ir/$)2_1
R = PL
m=1
(27r $ )2
=
( 27r )2 1 PL
m2
NL L m=1
(NL )2
L ~ :
$
(1_1 2 ( 27rm
NL )2)_1
PL m=1
1 L
m2
1 L
PL m=1
De même, nous avons: R ~ 1 et donc, le schéma
hiérarchique à L couches converge plus rapidement que celui
à L liens, même s'ils demandent tous les deux le même nombre
de capteurs.
Poursuite cyclique à L liens / Traditionnelle
Dans les comparaisons précédentes, nous avons
calculé les valeurs 'y correspondant aux deux méthodes
respectives (traditionnelle, L-liens). D'où l'augmentation dans le taux
de convergence de la P.C à liens comparée à la
traditionnelle est la suivante :
L - liens
R = Traditionnelle
(cos(2mr/NL)) - 1
=
cos(2r/NL) - 1
Après simplification du cos par son développement
limité de l'ordre 1 :
(1_1 2 ( 27rm
NL )2)_1
1_ 1 2 (21r/NL)2_1
PL
Pm=1 2 ( 27r
1 NL )2 =m=
m2 ~ 1 = Les agents avec le schéma à L liens
R=
1
1_1 2 ( NL 27r )2
m2_1 L
1 L
PL m=1
convergent plus rapidement qu'avec le traditionnel, mais
demandent plus de liens de communications et donc plus de senseurs.
|