Véhicules et Injustice…Quand l’Anarchie renverse le pouvoir local

Le probleme` est modelisable´ sous forme de jeu de strategie´ non cooperatif´ note´ < N; (Si); (Ui) > avec, N l’ensemble de joueurs, Si, l’ensemble de strategies´ du joueur i, Ui, ensemble de gains de i. Intuitivement, l’ensemble des joueurs correspond aux nœuds, les strategies´ correspondent aux choix de la technologie de communication et du nœud adjacent pour chaque flot. Enfin le gain signifie le debit´ passant pour chaque flot dans le noeud i.

Si on considere` que les ressources (fournies par les stations de base k) sont limitees´ et doivent etreˆ partagees´ entre les nœuds, alors le probleme` appartient a` la categorie´ des jeux de congestion.

L’equilibre´ de Nash se definit´ dans le cas de la strategie´ ADS comme le fait qu’aucun joueur, pour un flot donne,´ ne peut augmenter son gain (le debit)´ en changeant de nœud adjacent. Pour un nœud i, wv;k est le debit´ du nœud adjacent v utilisant la station de base k . La fonction x(k) : N ! N comptabilise le nombre de nœuds du systeme` utilisant la station de base k. L’ensemble de nœuds adjacents d’un nœuds i, correspon-dant aux D demandes est note´ (v1; :::; vD). L’ensemble des N nœuds du systeme` est note´ (n1; :::; nN ). si est le gain de l’entite´ i, defini´ tel que si(v1; :::; vD) = åk2vi Wk(xk(n1; :::; nN )), avec Wk : N ! R, la fonction correspondant au debit´ fournit par la station de base k.

La preuve de la convergence dans le cas de l’ADS est realis´ee´ en plusieurs etapes´. Dans un premier temps, l’existence d’une fonction potentielle est demontr´ee´ (pour chacune des deux classes formalisant le debit´ dans [AKWC13]), en prouvant que le choix de la station de base converge vers un equilibre´ de Nash.

Ce resultat´ est enrichi ensuite avec le choix des nœuds adjacents, menant a` la convergence vers un equilibre´ de Nash dans des systemes` utilisant l’apprentissage intelligent.

Cette hypothese` reprend les el´ements´ de [HLCL17] qui permettent de concilier dynamicite´ du graphe et equilibre´ de Nash par le calcul de multiples equilibres´ de Nash specifiques´ aux topologies du graphe. Le scenario´ appartient donc a` un sous-graphe de SG . Il y a donc au maximum jSGj convergences vers des equilibres´ de Nash.

Cette hypothese` provient de l’article de [JG17] et assure l’existence d’une fonction potentielle. Prouver la convergence necessite´ la presentation´ prealable´ de notions, telles les classes de debit´ intro-duites dans l’article [AKWC13]. Ces debits´ calcules´ sont utilises´ par algoRAT pour selectionner´ la tech-nologie de communication.

Definition´ 1 (debit´ de classe 1) Un modele` de debit´ de classe 1 pour un utilisateur i sur une station de base k depend´ de leur utilisation sachant que tous les utilisateur d’une memeˆ station de base partagent le memeˆ debit´. Il correspond a` l’equation´ suivante :

Que ce soit dans l’equation´ de la classe 1 ou de la classe 2, wi;k est le debit´ de l’utilisateur i sur la station de base k avec Ri;k le ratio specifique´ de sa couche PHY et fk fonction caracterisant´ la gestion des ressources d’une station de base k particuliere`.

Definition´ 3 (equilibre´ de Nash dans le cas du choix de la station de base) L’equilibre´ de Nash correspon-dant au choix de la station de base est la combinaison de (k1; :::; kN ) issue d’une strategie´ avec k1 la station de base du nœud adjacent v1 est un equilibre´ de Nash si si(k1; :::; kN ) si(k1; :::; k j 1; k j; k j 1; ::::; kN ) avec N, le nombre d’entites´ et k j la station de base utilisee´ par le nœud adjacent v j.

Lemme 1 Pour un memeˆ sous-graphe SG et pour des debits´ fournis par les stations de base constants et toutes de classe 1, alors le choix des stations de base converge vers un equilibre´ de Nash.

Cette preuve constitue une variante de la preuve de [EDKM07], basee´ sur l’algorithme qui calcule un equilibre´ de Nash dans les jeux de potentiels.

Dans le cas ou` tous les debits´ proposes´ par les nœuds adjacents sont de classe 1, alors le choix des stations de bases de ces nœuds adjacents entraˆıne un equilibre´ de Nash.

On appelle pour un nœud w(v j ;k), le debit´ du nœud adjacent v j elu´ pour la station de base k. W(v j ;k j ) correspond a` l’utilisation du debit´ w(v j ;k j ). Donc W(v j ;k j ) w(v j ;k j ) D.

L’ordre suivant est defini´ arbitrairement : W(v1;k1) ::: W(vN ;kN ), avec N, le nombre de nœuds et k j la station de base choisie par le nœud j.

Avec S tres` superieur´ a` W(i;ki); 8i; S W(i;ki). On suppose que le nœud adjacent v change de station de base et passe de la station ka vers kb.

D’apres` la definition´ des debits´ de classe 1, la station de base a a un debit´ en moins, w(i;ka) va augmenter et donc aussi W(i;ka). La station de base b a un debit´ en plus, w(i;kb) diminue et W(i;kb) aussi. Or pour justifier le changement, on avait W(i;kb) > W(i;ka). Donc la valeur de g augmente drastiquement. Or g est borne´ et n’augmente pas indefiniment´.

Des` lors, le choix de la station de base mene` a` un equilibre´ de Nash avec definition´ d’une fonction potentielle

Lemme 2 Pour un memeˆ sous-graphe SG et pour des debits´ fournis par les stations de base constants et toutes de classe 2, alors le choix des stations de base converge pour tout nœud vers un equilibre´ de Nash.

Preuve : Cette preuve constitue une variante de [AKWC13] utilisant une preuve par contradiction. Soit un systeme` dont toutes les stations de base sont de classe 2 et qui possede` une boucle. Dans cette boucle, il existe une sequence´ d’etats´ avec un debut´ et une fin identique. Au moins une station de base notee´ k fournit donc le memeˆ debit´ au debut´ et a` la fin de la sequence´. Soit dans la boucle, un nœud i utilisant la station de base k qui apparaˆıt ci fois comme nœud adjacent lors des differentes´ demandes. Des` lors, d’apres` l’equation´ des debits´ relattifs a` la classe 2 (Eq 2), w(i;k) = Ri;k fk(nk). Lorsque i change de station de base pour aller vers une station de base k0, le debit´ de la station k augmente (Eq 4).

A la fin de la boucle, le debit´ propose´ par la station de base k retourne a` Ri;k fk nk . Il existe donc des nœuds qui changent leur station de base de fac¸on a` retrouver le debit´ correspondant a` nk et tel que le nouveau debit´ s’avere` plus interessant´ (Eq 5).

Or, les deux equations´ prec´edentes´ (Eq 4 et 5) sont contradictoires. Comme une boucle ne peut pas exister, chaque systeme` avec debit´ exclusif de classe 2 se termine par une situation d’equilibre´ de Nash.

Remarque : Cet equilibre´ est formalisable a` travers une fonction potentielle, qui lorsque l’equilibre´ est atteint ne peut pas augmenter (fonction bornee´ superieurement)´.

Lemme 3 Pour un memeˆ sous-graphe SG et pour des debits´ fournis par les stations de base constants et avec a` la fois des classes 1 et 2, alors le choix des stations de base converge pour tout nœud vers un equilibre´ de Nash.

Preuve : Cette preuve est une adaptation de la preuve de [AKWC13] se basant sur une contradiction. Soit un systeme` compose´ d’etats´ dans un reseau´ constitue´ d’un ensemble de stations de base et d’utilisateurs connectes´. Soit une boucle rep´etable´ indefiniment´ avec au moins un changement de classe.

Par exemple, l’utilisateur i quitte la station de base de classe 2 et de debit´ w(i;a) pour aller a` une station de base 1 et enfin revenir a` une station de base de classe 2 et dont le debit´ est w(i;d). A cause de l’hysteresis,´ le nouveau debit´ doit etreˆ ameliorant´. Soit une base virtuelle v specifique´ a` chaque changement de base et n’appartenant qu’a` un seul utilisateur i tel que W = w(i;a)  cia+w(i;d)  cid avec w (i;a) le debit´ fournit au nœud ca+cdi par la station de base a, cai le nombre de fois ou` i utilisant la station de base a est un nœud adjacent choisit pour une demande et W(i;a) le debit´ global tel que W(i;a) = w(i;a) cai. Si v est utilise´ par un autre utilisateur j alors W( j;v) = 0; 8 j 6= i. Dans cet exemple, et a` cause de l’hysteresis,´ wi;a < wi;d . Cependant, cai et cdi ne sont pas forcement´ ordonnees´ (Eq 6,7,8).

Dans ces trois equations´ (Eq 6,7,8), la station de base virtuelle remplace la station de base de classe intermediaire´ entre deux classes identiques. De plus la station de base virtuelle uniformise les classes. Ainsi, elle se comporte comme une station de classe 2 entre deux classes 2. Or le lemme prec´edent´ (Lemme 2) a montre´ qu’il etait´ impossible d’avoir une boucle quand l’ensemble des stations de base est de classe 2.

Remarque : Cet equilibre´ est formalisable a` travers une fonction potentielle, qui lorsque l’equilibre´ est atteint ne peut augmenter (fonction bornee´ superieurement)´.

Definition´ 4 (equilibre´ de Nash dans le cas de l’ADS) La combinaison de (v1; :::; vD) issue strategie´ d’un nœud i est un equilibre´ de Nash si si(v1; :::; vD) si(v1; :::; v j 1; v j; v j 1; ::::; vD) avec D, le nombre de demandes rec¸ues par i et v j nœud adjacent de i elu´ pour la demande j.

Theor´eme` 1 (convergence vers un equilibre´ de Nash dans le cas du systeme` de l’ADS) Pour un memeˆ sous-graphe SG et pour des debits´ fournis par les stations de base constants, alors l’heuristique fournie par l’ADS converge pour tout nœud vers un equilibre´ de Nash.

Preuve : Cette preuve est une adaptation de la preuve de [JG17] centree´ sur l’equilibre´ de Nash dans les jeux de potentiels. L’ADS, variante de [CGM15] insere` le probleme` de routage dans le cadre de la theorie´ des jeux en le classant parmi les problemes` de routage atomique. Les nœuds sont des joueurs, la strategie´ reside´ dans le choix de la station de base et du nœud adjacent correspondant a` une demande et enfin, le gain correspond au debit´ total.

Le lien entre les jeux de routage atomiques a` taux 1 et les jeux de potentiels a et´e´ prec´edemment´ etudi´e´ par [ORS93]. Les jeux de potentiels sont caracteris´es´ par une fonction potentielle notee´ f(p) = åk åni=k(1p) w(i;k) avec p une configuration, k une station de base, nk(p) nombre de nœuds adjacents utilisant la station de base k pour une configuration p et w(i;k), le debit´ du nœud i utilisant la station de base k. Un simple changement d’unite´ permet d’atteindre le taux 1. Cette propriet´e´ est garantie par l’hypothese` 2 fournissant un debit´ constant.