FR2880231A1 - Procede et equipement d'allocation de ressources d'un reseau cellulaire de telecommunication pour terminaux mobiles - Google Patents

Abstract

Pour allouer des ressources à un ensemble de terminaux mobiles de télécommunication d'un réseau cellulaire de manière à maximiser une fonction d'utilité globale correspondant à une somme de fonctions d'utilités propres à chaque utilisateur tout en satisfaisant des contraintes liées aux ressources du réseau mises à disposition des utilisateurs, on affecte des valeurs de ressources minimale et maximale pour chaque terminal ; on calcule pour chaque terminal une fonction représentative des ressources consommées par le terminal ; et on affecte une valeur optimale de ressources pour chaque terminal à partir des valeurs de ladite fonction calculée.

Description

Procédé et équipement d'allocation de ressources d'un réseau cellulaire de

télécommunication pour terminaux mobiles

L'invention concerne, de manière générale, les réseaux de télécommunication de type mobile, et se rapporte plus particulièrement à l'allocation des ressources disponibles d'un réseau téléphonique cellulaire à des terminaux mobiles d'un téléphone réseau.

Par affectation des ressources, on entend la mise à disposition des moyens proposés par le réseau pour permettre à un terminal situé dans une cellule du réseau d'échanger des données.

Ainsi, une application particulièrement intéressante de l'invention concerne l'allocation optimale et équitable de débits à des mobiles d'un réseau de télécommunication.

En effet, les exploitants des réseaux de télécommunication cherchent généralement à maximiser le nombre d'utilisateurs pouvant être servis par un réseau donné. Dans les réseaux de téléphonie de type CDMA, pour un utilisateur donné, les autres utilisateurs, dans le sens montant, ou les stations de base autres que celles avec laquelle il communique, dans le sens descendant, constituent des sources de bruits qui perturbent l'utilisateur. Si le nombre d'utilisateurs devient trop important, le bruit augmente et entraîne une chute de la qualité, voire un blocage de la communication. Un contrôle du débit de données des mobiles peut permettre de contrôler et limiter ce bruit et d'améliorer ainsi les performances.

C'est pour ces raisons que l'un des soucis constants des opérateurs de télécommunication est d'optimiser la gestion des débits des mobiles et d'optimiser l'admission de nouveaux terminaux dans les cellules de manière à maximiser le nombre de terminaux dans chaque cellule, tout en assurant une qualité de service (QoS) donnée.

Généralement, les algorithmes mis en oeuvre pour contrôler le débit de données des terminaux dans les cellules ainsi que pour contrôler l'admission de nouveaux terminaux sont basés sur le contrôle du niveau de charge. Par exemple, si l'admission d'un mobile dans une cellule provoque une augmentation du niveau de charge telle que la charge totale excède un seuil donné, le mobile entrant est contraint de diminuer son débit pour être admis. Au-delà d'un certain seuil, tous les nouveaux terminaux entrants sont rejetés.

Ainsi, dans l'état de la technique, lorsque la charge d'une cellule est trop importante pour autoriser l'admission d'un nouveau terminal, le débit autorisé pour ce terminal est réduit, ce qui engendre une baisse de la qualité de service pour le terminal entrant. Les terminaux déjà en communication ne sont pas concernés.

Les politiques d'admission de nouveaux terminaux peuvent être mises en oeuvre de diverses manières. Par exemple, il est possible d'adapter le débit du mobile entrant en lui garantissant un débit donné. Cette mise en oeuvre induit des taux de rejet relativement importants et limite par conséquent la capacité du réseau. On peut également adapter le débit du terminal entrant de manière à toujours l'admettre, même avec un débit nul. Cette mise en oeuvre ne garantit pas la qualité de service (QoS).

Enfin, ces diverses stratégies ne sont pas optimales, dans la mesure où il est possible d'augmenter le débit d'un mobile sans nécessairement diminuer celui d'un autre.

Ainsi, les techniques conventionnelles d'allocation de débits ne permettent pas d'allouer des débits à des terminaux dans un réseau de manière optimale et équitable. Elles ne permettent généralement pas d'explorer toute la gamme des stratégies équitables de gestion dynamique des débits des mobiles dans le réseau. Elles ne permettent pas non plus d'utiliser toute la gamme des stratégies de gestion de l'admission des mobiles permettant d'obtenir un taux de rejet compris entre des valeurs extrêmes correspondant l'une à une qualité de service garantie et l'autre à une qualité de service non garantie.

Pour pallier ces inconvénients, il a été proposé de calculer les débits affectés à chaque terminal, lorsqu'un nouveau terminal entre dans une cellule, de manière à maximiser une fonction d'utilité. Diverses techniques peuvent être utilisées pour la résolution d'une telle équation. Des algorithmes de calcul à l'aide de relaxation Lagrangienne, de programmation semi-définie positive ou de programmation mixte linéaire/entière peuvent être utilisées pour la résolution d'une telle équation. La maximisation d'une fonction d'utilité pour allouer des ressources à des terminaux d'un réseau implique l'utilisation de contraintes supplémentaires liées aux ressources du réseau. C'est ainsi que les ressources affectées aux utilisateurs ne peuvent être inférieures à des valeurs de seuil minimales respectives affectées aux utilisateurs. De même, elles ne peuvent être supérieures à des valeurs de seuil maximales respectives affectées aux utilisateurs. Enfin, la somme des ressources affectées aux utilisateurs ne peut être supérieure à la capacité globale du système.

Toutefois, les techniques de calcul connues utilisées pour maximiser la fonction d'utilité en tenant compte de ces contraintes ont toutes l'inconvénient d'être très lentes en temps de calcul et d'une fiabilité limitée. Or, l'utilisation des équations permettant de maximiser la fonction utilité tout en tenant compte des contraintes liées aux ressources du réseau repose sur des contraintes de temps réel et de réponses fiables. Il s'agit, en pratique, de déterminer quelle sera une nouvelle allocation de débits lors de chaque entrée d'un mobile dans le réseau et ce, en temps réel.

Au vu de ce qui précède, le but de l'invention est de permettre d'allouer des ressources d'un réseau cellulaire de télécommunication à des terminaux mobiles de télécommunication situés dans le réseau en temps réel et de manière fiable.

L'invention a donc pour objet un procédé d'allocation de ressources d'un réseau cellulaire de télécommunication pour un ensemble de terminaux mobiles de télécommunication du réseau, selon lequel la ressource est affectée aux terminaux de manière à maximiser une fonction d'utilité globale élaborée à partir d'une sommation de fonctions d'utilité propres à chaque utilisateur, tout en satisfaisant des contraintes liées aux ressources du réseau mis à disposition des utilisateurs.

Selon une caractéristique générale de l'invention, le procédé d'allocation des ressources comporte les étapes de: - affectation de ressources minimale et maximale pour chaque terminal; - calcul d'une fonction représentative des ressources consommées par chaque terminal; et affectation d'une valeur optimale de ressources pour chaque terminal à partir des valeurs de ladite fonction calculée.

Dans un mode de mise en oeuvre, pour calculer la fonction représentative des ressources consommées par chaque terminal, on calcule la valeur des dérivées de la fonction d'utilité propre à chaque utilisateur pour chaque valeur minimale et maximale; - on trie les valeurs calculées de la dérivée de la fonction d'utilité propre à chaque utilisateur; - on recherche un intervalle dans laquelle se situe une valeur pivot des valeurs calculées qui correspond à une valeur optimale de ressource; et, - on calcule, dans l'intervalle recherché, la valeur pivot, la valeur optimale affectée aux terminaux des utilisateurs correspondant soit à la valeur de ressource minimale, soit à la valeur de ressource maximale, soit à une valeur calculée à partir de la valeur pivot.

Par exemple, la valeur des ressources calculée (Xi) à partir de la valeur pivot est calculée, pour les utilisateurs i pour lesquels la valeur pivot est utilisée pour déterminer la valeur optimale, à partir de la relation suivante: = (f'i)-' (p*) dans laquelle (f';)-' représente l'inverse de la dérivée de la fonction d'utilité et p désigne un coefficient dual réel.

De même, par exemple, les valeurs calculées sont triées par valeurs croissantes.

Selon une autre caractéristique de l'invention, les contraintes liées aux ressources du réseau imposent qu'une valeur de ressources affectée à un utilisateur doit être supérieure à la valeur de ressources minimale.

En outre, les contraintes liées aux ressources du réseau imposent qu'une valeur de ressources affectée à un utilisateur doit être inférieure à la valeur de ressource maximale.

Enfin, la somme des valeurs de ressources affectées aux utilisateurs doit être inférieure à la capacité globale du système.

Selon encore une autre caractéristique de l'invention, la fonction représentative des ressources consommées par chaque terminal est déterminée à partir des fonctions d'utilité de tous les utilisateurs. Par exemple, la fonction représentative de la ressource consommée par chaque utilisateur i est donnée par la relation: cP(y) = + EMi + (f')'-"(y) dans laquelle: lm; correspond à la somme des ressources affectées aux utilisateurs à qui la valeur de ressource minimale est affectée; correspond à la somme des ressources affectées aux utilisateurs à qui la valeur de ressource maximale est affectée; (f')-' représente l'inverse de la dérivée de la fonction d'utilité f.

En outre, la valeur pivot qui correspond aux valeurs optimales des ressources peut être donnée par la relation: p* = [E(fi l-1(C Em; IM,) dans laquelle C désigne la capacité globale du réseau.

L'invention a également pour objet un procédé de gestion des ressources d'un réseau cellulaire de télécommunication pour un ensemble de terminaux mobiles de télécommunication du réseau, caractérisé en ce qu'à chaque nouveau terminal entrant dans le réseau, on procède à une détection de surcharge d'une cellule du réseau et, dans le cas où une des cellules du réseau est surchargée, on procède à une allocation de ressource par mise en oeuvre du procédé d'allocation tel que défini ci- dessus, pour accepter le terminal entrant.

Selon un troisième aspect, l'invention concerne un équipement d'allocation de ressources d'un réseau cellulaire de télécommunication pour un ensemble de terminaux mobiles de télécommunication du réseau, caractérisé en ce qu'il comporte des moyens de calcul d'une fonction représentative des ressources consommées par chaque terminal et des moyens pour affecter une valeur optimale de ressource pour chaque terminal à partir de la valeur de ladite fonction calculée.

2880231 7 Enfin, l'invention concerne, selon un quatrième aspect, un module logiciel enregistré sur un support, caractérisé en ce qu'il comporte des codes d'instruction pour l'exécution d'un procédé d'allocation de ressource tel que défini ci-dessus.

Un tel support de données peut être un support matériel de stockage, par exemple, un CD-ROM, une disquette magnétique ou un disque dur, ou bien un support mobile tel qu'un signal électrique, optique ou radio.

D'autres buts, caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée uniquement à titre d'exemple non limitatif, et faite en référence aux dessins annexés sur lesquels: la figure 1 illustre schématiquement l'architecture d'un réseau cellulaire de télécommunication mettant en oeuvre un procédé selon l'invention; - la figure 2 est un schéma illustrant les principales phases d'un procédé de gestion des ressources d'un réseau cellulaire selon l'invention; - la figure 3 est un tableau montrant des exemples de valeurs de ressources affectées à des utilisateurs; - la figure 4 illustre les principales phases du procédé d'allocation de débits selon l'invention; - la figure 5 est un tableau illustrant le calcul des valeurs de ressources affectées; et - les figures 6 et 7 montrent des courbes illustrant l'évolution des ressources consommées.

Sur la figure 1, on a représenté l'architecture générale d'un réseau de téléphonie mobile cellulaire mettant en oeuvre un procédé d'allocation de ressource conforme à l'invention.

Ce procédé est destiné à être appliqué au réseau de type CDMA ou W- CDMA.

Sur cette figure, seules trois cellules ont été représentées, par souci de clarté.

Comme on le voit, le territoire à desservir est décomposé en cellules Cl, C2, et C3. Une cellule est liée à une station de base BS (ou "node B"), qui possède une antenne permettant d'émettre vers les terminaux, tels que T, et de recevoir des signaux en provenance de ces derniers.

Comme on le voit sur la figure, les stations de base sont gérées par un contrôleur de ressource radio ou RNC ("Radio Network Controller", en anglais) qui gère l'interface radio. En particulier, le contrôleur RNC comporte tous les moyens matériels et logiciels et est dûment programmé pour procéder à une allocation des ressources à chaque terminal des cellules Cl, C2 et C3 du sous-système radio dont il assure la gestion. A cet effet, il comporte en particulier les moyens matériels et logiciels et est programmé pour calculer une fonction qui représente les ressources consommées par les terminaux du réseau et pour affecter des valeurs optimales de ressources, en particulier de débit, à partir de cette fonction, comme cela sera exposé par la suite.

Cette allocation est une allocation optimale des ressources qui se traduit, à l'admission d'un mobile dans une cellule, par la renégociation des ressources allouées à chaque terminal de manière à obtenir une valeur de ressource maximale pour les terminaux tel qu'il n'est plus possible d'augmenter les ressources affectées à l'un des terminaux sans nécessiter de diminuer les ressources d'un ou de plusieurs autres terminal.

Par exemple, il s'agit de renégocier les débits de manière à optimiser la capacité du réseau.

Selon une caractéristique de l'invention, le calcul des ressources passe par la maximisation d'une fonction d'utilité. Il s'agit en particulier de maximiser la fonction suivante: P f(AÏ) (1) Il s'agit en outre de satisfaire aux contraintes suivantes >_ 0 di E 11, ...,p (2) M;-X; z 0 di E 11, ...,p (3)

P

C- ;Li z 0 di E 11, ...,p (4) Dans ces relations (1) à (4) : - ?, est une variable dans l'ensemble des réels positifs et désigne des ressources affectées à l'utilisateur i, - m; est une donnée dans l'ensemble des réels positifs et désigne une borne minimale de ressources affectée à l'utilisateur i, - M; est une donnée dans l'ensemble des réels positifs et désigne une borne maximale de ressources affectée à l'utilisateur i, - C est une donnée dans l'ensemble des réels positifs et désigne la capacité globale du système, et - f; est une fonction de l'ensemble des réels positifs dans l'ensemble des réels positifs et désigne une fonction d'utilité associée aux ressources pour l'utilisateur i.

En outre, dans ces relations (1) à (4), on suppose que p est un entier positif, que la fonction f; est une fonction concave, et que C, m;, M, sont des réels positifs pour i appartenant à (1, ..., p).

Les contraintes définies par les relations (2) à (4) imposent qu'une ressource affectée à un utilisateur doit être comprise entre une borne minimale m; et une borne maximale M, et que la somme des ressources affectées aux utilisateurs doit rester inférieure à la capacité globale C du système.

2880231 10 Ainsi, en se référant à la figure 2, à chaque nouvelle entrée d'un terminal dans une cellule du réseau (étape 10), on détecte s'il existe dans le réseau une cellule surchargée (étape 12) de manière connue en soi. Si tel n'est pas le cas, on accepte le terminal (étape 14).

Au contraire, s'il existe une cellule surchargée, on procède à une allocation des ressources du réseau en réallouant les débits des mobiles sur la cellule (étape 16). Si, lors de l'étape 18 suivante, le calcul de la réallocation des débits permet d'aboutir, la procédure retourne à l'étape 12 précédente. Dans le cas contraire, le mobile est refusé (étape 20).

On va maintenant décrire la procédure d'allocations des ressources au terminal, lorsqu'une cellule est surchargée.

Comme indiqué précédemment, la surcharge d'une cellule peut être détectée lors de l'admission d'un mobile c'est-à-dire, de manière générale, lors de l'entrée d'un terminal dans une cellule, par exemple lors de l'établissement d'un appel ou lors du passage d'un terminal d'une cellule à une autre.

Cette procédure d'allocation des ressources est mise en oeuvre au sein du contrôleur de station de base qui comporte tous les moyens matériels et logiciels appropriés pour mettre en oeuvre cette procédure.

Une telle procédure consiste à calculer une nouvelle valeur de débit pour les terminaux de la cellule afin de maximiser la fonction F d'utilité globale suivante p F=J(2) qui correspond à la somme des fonctions d'utilités f1(21) affectées à chaque utilisateur i.

Ces fonctions d'utilités individuelles f; caractérisent des intérêts économiques ou privés à recevoir, pour un utilisateur i, une 2880231 11 ressource X,. Ainsi, la fonction d'utilité globale permet de prendre en compte l'ensemble des utilisateurs.

Cependant, cette procédure nécessite avant tout le respect des contraintes précitées liées au fonctionnement de la cellule. Il convient donc, en particulier, de vérifier que la charge de chaque station, en particulier celle de la station dans laquelle le mobile entre, ne dépasse pas une charge maximale admissible. Par ailleurs, la puissance demandée à un ensemble des stations de base, en particulier à la station de la cellule dans laquelle le mobile entre, ne doit pas dépasser une puissance maximale admissible. Enfin, la somme des ressources allouées aux utilisateurs ne doit pas dépasser la capacité globale du système.

Ainsi, les contraintes à satisfaire correspondent aux relations (2) à (4) mentionnées précédemment.

On notera que, dans une cellule, chaque utilisateur reçoit une ressource X bornée suivant les valeurs du tableau de la figure 3. En d'autres termes, chaque valeur de ressource X, est comprise entre les valeurs de seuil m; et M;. Dans l'ensemble de réalisation considéré, un coefficient d'utilité (3; est alloué à chaque utilisateur pour le calcul de la fonction d'utilité f;(x). Par exemple, dans le cas illustré sur le tableau de la figure 3, la capacité totale C du système est égale à 100. Avant l'arrivée de l'utilisateur 4, la cellule n'est pas saturée et chaque mobile i reçoit sa demande maximale de débit M;.

On va maintenant décrire, en référence à la figure 4, la procédure d'allocation des ressources mise en oeuvre lors de l'étape 16 précédemment mentionnée. Cette procédure consiste tout d'abord à affecter à chaque utilisateur i une fonction d'utilité f, et des valeurs des ressources minimale et maximale m, et M, (étape 22). En particulier, la fonction d'utilité f; peut s'exprimer sous la forme: fi(x) = x'-a 1 a dans laquelle a désigne un coefficient réel strictement positif et différent de 1.

On procède ensuite au calcul de la valeur de la dérivée de la fonction d'utilité pour les valeurs m; et M;, pour chaque utilisateur i (étape 24).

Lors de l'étape 26 suivante, on procède à un tri des valeurs calculées lors de l'étape 24 précédente, par valeurs croissantes.

On applique à cet effet un algorithme de tri rapide conventionnel pour obtenir la liste triée des valeurs. On obtient en sortie une liste qui donne pour chaque k appartenant à l'intervalle 11, ..., 2p les informations suivantes sur la k-ième valeur: Utilisateurs (k) = i Borne (k) = m; ou M; Valeur (k) = f'; (Borne (k)).

On aura Valeur (1) s Valeur (2) s... s Valeur (2p) et pour chaque utilisateur i, il existe deux valeurs k, < k2 avec Utilisateur (kl) = Utilisateur (k2) = i, Borne (kl) = M; et Borne (k2) = m;. On notera dans ce cas Debut (i) = (k1) et Fin(i) = (k2).

Lors de l'étape 28 suivante, on procède à une localisation de l'intervalle de la valeur pivot qui correspond à une valeur optimale des débits. Cette valeur correspond pratiquement à une valeur qui est utilisée pour l'optimisation des ressources et qui donne un indice global de satisfaction des utilisateurs. Elle se calcule en fonction de la capacité que l'on peut fournir aux utilisateurs.

Pour localiser l'intervalle de la valeur pivot on utilise la liste précédente et on cherche par dichotomie. On affecte alors les valeurs Bas: = 1 et Haut: = 2p, et on applique l'algorithme suivant: 12 (5) 2880231 13 Tant que Haut Bas > 1 Milieu: = (Haut + Bas)/ 2 Phi: = 0 Pour tous les utilisateurs i Si Début(i) > Milieu phi: = phi + Mi Si Fin (i) < Milieu phi: = phi + mi Si Debut(i) Milieu et Fin(i) z Milieu phi: = phi + (f'i)"' (Milieu) Si phi z C alors Bas: = Milieu sinon Haut: = Milieu En sortie, on fournit la valeur de Haut et Bas, avec Haut-Bas = 1 et Haut, Bas compris dans l'intervalle 1, ..., 2p Lors de l'étape 30 suivante, on procède au calcul proprement 15 dit de la valeur pivot p, à partir de la relation 10 p* _ 'tJï' (Reste) où (6) La valeur Reste est en particulier calculée à partir de l'algorithme suivant: Reste: = C Pour tous les utilisateurs i Si Début (i) > Bas Reste: = Reste - Mi Si Fin (i) < Haut Reste: = Reste -mi 4, désigne alors la somme des fonctions (fi') ' pour i vérifiant Début (i) s Bas et Fin (i) z Haut.

On procède enfin à une affectation des valeurs calculées (étape 31) .

Pour chaque utilisateur i, la valeur de ressources qui lui est affectée est donnée par: Si Debut(i) > Bas, alors X; : = M; Si Fin(i) < Haut, alors X; : = m; Sinon, X; : = (f';)-1 (p*).

c Ou p* = [(f?)1](C-1m,i I M,) Comme cela va maintenant être démontré par la suite, les ressources affectées aux utilisateurs ainsi calculées constituent une solution d'affectation des ressources optimale.

Supposons que les fonctions f;, pour i compris dans l'intervalle 1,

., p soient strictement concaves, que la contrainte p C z 0 est vérifié à l'égalité par une solution optimale, et que la fonction f'; est calculable en une opération. Supposons que l'on puisse calculer l'inverse de toute somme d'inverses des f'; pour i compris dans l'intervalle 11, ... , p en M opérations. Alors les ressources, c'est-à-dire la solution aux relations (1) à (4), sont calculables en M + O (p log(p)) opérations, O désignant la notation de Landau...DTD: Par application des conditions de Kuhn-Tucker, on obtient, pour la solution optimale À; pour i appartenant à l'intervalle 11, p et les coefficients réels positifs duaux p;, v; pour i compris dans 11, ...,petp, f' (Xr) ,+v,+p=0 Vie 11, ..., p v;(M; Â,*) = 0 d;E 11, ..., p et p(C ;1 =0 _l 2880231 15 Pour chaque i compris dans l'intervalle 1, ..., p trois cas peuvent se présenter.

1) ); =mi. Dans ce cas v; = O. Par conséquent - f'(Î.) + p = 0, ce qui donne f'(Â;) p. 2) ); = Mi. Dans ce cas ; = 0. Par conséquent - f'(Âi) + v; + p = 0, ce qui donne f'(2) z p. 3) ?; E m;,M. On a alors v; = 0 et ; = 0, soit f'(Âi)=p Autrement dit, si f' est strictement décroissante et continue avec i appartenant à l'intervalle 1, ..., elle est inversible et, à chaque valeur réelle de p, on peut associer une capacité "consommée" définie par cp(P) _ m; + ) M; + (f)-1(P)É (7) i:p> (m;) i:p< (M;) i:f'(M)sp f (m;) Comme on le conçoit, cp est une fonction décroissante de p. Une solution optimale est alors donnée par une valeur p* qui vérifie: cp(p*) = C. (8) L'algorithme de calcul de la solution aux relations (1) à (4) ci- dessus peut être réalisé comme suit.

Soit X={m;,...mp}U{M,,...Mp}. On a 2p. On calcule tout d'abord toutes les valeurs à partir de la relation: Y={ f'(x),x E X}.

L'ensemble Y est alors trié. Ce tri est effectué en O(p log(p)) opérations. On raisonne ensuite par dichotomie sur Y. Pour une valeur y E Y, on calcule cp(y) en 0(p) opérations, et en O(log (p)) étapes on trouve deux valeurs consécutives y,<y2, telles que cp(y,)zC et cp(y2)<C Dans les cas limites, y2 vaut 0, ou y, vaut l'infini.

Si cp(y,) = C, alors l'équation p* = y, donne une solution. Sinon, les ressources du réseau consommées par un utilisateur i sont données par Vy E _Y1,Y2[ q7(Y) = mi + Mi + (f 1(Y) i:Y > (m1) ,y, (Mr) i:.ft(Mi)sY, <Yzsf'(mr) La valeur pivot p* est alors donnée par la relation suivante: p*= (f')-il (C mi Mil. (9) i:f,(M,)y1<Yzsff'(ml) \ i:Yz>fi(m,) t:Y,<fi(M,) La fonction d'utilité fi(x) affectée aux utilisateurs peut être de diverses formes. xl-"

Dans le cas où fi(x) = 1 a, pour a E]0;1[U]1,+oo[, alors 1 l'allocation des ressources est calculable en O(plog(p)).

Dans ce cas, f'(x) = fi2,x-a et f,.'l -1(y) = -1 y-lia. Donc, pour J E {1,...,p} si on pose îr(Y)=fi y), 1E] alors 20.,'(x) _ _, x Pour J donné, cette fonction est calculable en 0(p) opérations.

Dans le cas où fi(x)=ln(x), alors l'allocation des ressources est calculable en O(p log(p)).

Dans ce cas, f'(x)= x et fi-1 (y) =-- . Donc, pour J E {1,...p}, si on pose PJ(Y)= fy 1(Y) iEJ alors IJIx Enfin, si fi(x)=(3;x, alors la solution est calculable en 10 O(p log(p)).

Dans ce cas, f'(x)=(3;. En raisonnant de manière similaire au résultat ci-dessus, on considère Y={(3; : i E{1,...,p}}, et (Y)= mi+ Mi i:Y>Pi i:Ysfi, cp est une fonction en escalier décroissante. On cherche deux valeurs y, et Y2 consécutives de Y, telles que y,<y2, avec cp(yl)zC et cp(y2)<C. Dans ce cas, une ressource optimale X., est donnée par: mi si /3i < y, Mi mi + (Mi mi) Mi mi i:/Ji Yh si pi' Y, si /3i=y1 De manière concrète, et en se référant maintenant aux figures 5 x1-a à 7, on considérera tout d'abord le cas où f1(x) = ' , pour a=1/2, 1 a f'(x) _ l J. Le calcul des valeurs de ressources optimales s'effectue, comme indiqué précédemment, en plusieurs étapes.

Il convient tout d'abord de calculer la valeur de la dérivée de la fonction d'utilité pour chaque valeur minimale et chaque valeur maximale de ressources, et pour chaque utilisateur i. On obtient alors les valeurs visibles sur le tableau de la figure 5. Les valeurs de ce tableau sont alors triées en O(p log(p)), et on obtient: f4(M4) = f3(M3) < f'(M1) < f4(m4) = f3(m3) < J11(mi) < f2(M2) < f2(m2).

La fonction cp se décrit comme suit: pour x E [0,91; 1,58] pour x E [1,58; 2,24] pour x E [2,24; 3,16] pour x E [3,16; 4,47] pour x E [4,47; 8,94] cp(x) = 60 + 50/x2; cp(x) = 20 + 150/x2; cp(x) = 30 + 100/x2; cp(x) = 40; et cp(x) = 20 + 400/x2.

Cette fonction est représentée sur la figure 6. Il s'agit de repérer la position où cp(x)=100.

La valeur pivot est alors dans l'intervalle [0,91;1,58], où la fonction cp est donnée par cp(x) = 60+50/x2, ce qui donne un pivot pour 25 x=0,73. Les débits obtenus vont donc réduire les utilisateurs 3 et 4 à la valeur commune de 20.

2880231 19 De même, en se référant à nouveau à la figure 5, dans le cas où f1(x)=1n(x), les valeurs calculées pour f' se classent de la manière suivante: f11 (M1) < f3 (M3) = f4 (M4) < f21(M2) < f'(m1) < f2 (m2) = f31(m3) = f4 (m4).

La fonction cp, tracée sur la figure 7, se décrit comme suit: pour x E [0,025; 0,033] cp(x) = 80 + 1/x; pour x E [0,033; 0,050] cp(x) = 20 + 3/x; pour x E [0,050; 0,100] cp(x) = 4/x; et pour x E [0,100; 0,200] cp(x) = 10 + 3/x, ce qui donne un intervalle pour la valeur pivot de [0,033; 0, 050], et 15 une valeur finale de 0,0375.

Enfin, si f;(x)=m;x, les valeurs de f' peuvent être triées comme suit: f3 (m3) = f3 (M3) = f>14) = f4 (M4) < J 1,\ m7) = f'(M1) < f2 (m2) = f2 M2 É La fonction cp(x) est alors une fonction constante par intervalles donnée par: pour x E [ 5; 10] cp(x) = 70; et pour x E [10; 20] cp(x) = 40, la valeur pivot est alors comprise dans l'intervalle de [5; 10]. 10

Claims (13)

REVENDICATIONS

1. Procédé d'allocation de ressources d'un réseau cellulaire (C,, C2, C3) de télécommunication pour un ensemble de terminaux mobiles (T) de télécommunication du réseau, les ressources étant affectées aux terminaux de manière à maximiser une fonction d'utilité globale correspondant à une somme de fonctions d'utilités propres à chaque utilisateur, tout en satisfaisant des contraintes liées aux ressources du réseau mises à disposition des utilisateurs, caractérisé en ce qu'il comporte les étapes de: - affectation des valeurs de ressources minimale et maximale pour chaque terminal (T) ; - calcul d'une fonction représentative des ressources consommées par chaque terminal; et - affectation d'une valeur optimale de ressources pour chaque terminal à partir des valeurs de ladite fonction calculée.

2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte les étapes de: - calcul des valeurs de la dérivée de la fonction d'utilité propre à chaque utilisateur pour chaque valeur minimale et maximale; - tri des valeurs calculées de la dérivée de la fonction d'utilité propre à chaque utilisateur; - recherche de l'intervalle dans laquelle se situe une valeur pivot des valeurs calculées qui correspond à une valeur optimale de ressource; et - calcul, dans l'intervalle recherché, de la valeur pivot, la valeur optimale affectée aux terminaux de l'utilisateur correspondant soit à la valeur de ressource minimale, soit à la valeur de ressource maximale, soit à une valeur calculée à partir de la valeur pivot.

3. Procédé selon la revendication 2, caractérisé en ce que la valeur de ressources calculée (?) à partir de la valeur pivot est calculée, pour les utilisateurs i pour lesquels la valeur pivot est utilisée pour déterminer la valeur optimale, à partir de la relation suivante: k; = (f)- p), dans laquelle (f')-' représente l'inverse de la dérivée de la fonction d'utilité et p* désigne un coefficient dual réel.

4. Procédé selon l'une des revendications 2 et 3, caractérisé en ce que les valeurs calculées sont triées par valeurs croissantes.

5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que les contraintes liées aux ressources du réseau imposent qu'une valeur de ressources affectée à un utilisateur doit être supérieure à la valeur de ressources minimale.

6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que les contraintes liées aux ressources du réseau imposent qu'une valeur de ressources affectée à un utilisateur doit être inférieure à la valeur de ressources maximale.

7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que la somme des valeurs de ressources affectées aux utilisateurs doit être inférieure à la capacité globale du système.

8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que la fonction représentative des ressources consommées par chaque terminal est déterminée à partir des fonctions d'utilité de tous les utilisateurs.

9. Procédé selon la revendication 8, caractérisé en ce que la fonction cp(y) représentative de la ressource consommée par chaque utilisateur i est donnée par la relation: cp(y) = 1mi + + (f';)c- (y) dans laquelle: correspond à la somme des ressources affectées aux utilisateurs à qui la valeur de ressources minimale est affectée; ENI, correspond à la somme des ressources affectées aux utilisateurs à qui la valeur de ressources maximale est affectée; et (f')-' représente l'inverse de la dérivée de la fonction d'utilité f;.

10. Procédé selon la revendication 9, caractérisé en ce que la valeur pivot qui correspond aux valeurs optimale des ressources est donnée par la relation: p * = [s( f;)-'T' C gym, M1) dans laquelleJJC désigne la capacité globale du réseau.

11. Procédé de gestion des ressources d'un réseau cellulaire (Cl, C2, C3) de télécommunication pour un ensemble de terminaux mobiles (T) de télécommunication du réseau, caractérisé à ce qu'à chaque nouveau terminal entrant dans le réseau, on procède à une détection de surcharge d'une cellule du réseau et, dans le cas où l'une des cellules du réseau est surchargée, on procède à une allocation des ressources par mise en oeuvre du procédé d'allocation selon l'une quelconque des revendications 1 à 9 pour accepter le terminal entrant.

12. Equipement d'allocation des ressources d'un réseau cellulaire de télécommunication pour un ensemble de terminaux mobiles de télécommunication du réseau, caractérisé en ce qu'il comporte des moyens de calcul d'une fonction représentative des ressources consommées par chaque terminal et des moyens pour affecter une valeur optimale de ressource pour chaque terminal à partir de la valeur de ladite fonction calculée.

13. Module logiciel enregistré sur un support, caractérisé en ce qu'il comporte des codes d'instruction pour l'exécution d'un procédé d'allocation de ressources selon l'une quelconque des revendications 1 à 11.