WO2006070135A1 - 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 terminal tout en satisfaisant des contraintes liées aux ressources du réseau mises à disposition des terminaux, 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

PROCEDE ET EQUIPEMENT D'ALLOCATION DE RESSOURCES

D'UN RESEAU CELLULAIRE DE TELECOMMUNICATION

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, estimée à partir de fonctions d'utilités propres à chaque terminal, tout en satisfaisant des contraintes liées aux ressources du réseau mis à disposition des terminaux.

Selon une caractéristique générale de l'invention, le procédé d'allocation des ressources comporte les étapes suivantes : - affectation d'une fonction d'utilité (fi) et de valeurs de ressources minimale (mi) et maximale (Mj) à chaque terminal ;

- détermination d'une fonction (fj¹) représentative des ressources consommées par chaque terminal; et

- détermination d'une valeur optimale (λ_t) de ressources pour chaque terminal à partir de valeurs de desdites fonctions représentatives des ressources consommées, et

- affectation de ladite valeur optimale au terminal pour lequel cette valeur a été déterminée.

Dans un mode de mise en œuvre, la fonction d'utilité globale est la somme des fonctions d'utilité propres à chaque terminal.

Dans une alternative, la fonction d'utilité globale est le produit des fonctions d'utilité propres à chaque terminal. Cependant, lors de la mise en œuvre du procédé selon l'invention, il est possible de se ramener au cas précédent, par utilisation des propriétés de la fonction logarithme et application du procédé décrit plus en détail ci-dessous au logarithme des fonctions d'utilité. „. 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 terminal pour chaque valeur minimale et maximale ; - on trie les valeurs calculées de la dérivée de la fonction d'utilité propre à chaque terminal ;

- on recherche un intervalle dans lequel 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 à un terminal 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 {λ_;) à partir de la valeur pivot est calculée, pour les terminaux i pour lesquels la valeur pivot est utilisée pour déterminer la valeur optimale, à partir de la relation suivante :

dans laquelle (Z¹,)^"1 représente l'inverse de la dérivée de la fonction d'utilité et /? *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 terminal 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 terminal doit être inférieure à la valeur de ressource maximale.

Enfin, la somme des valeurs de ressources affectées aux terminaux 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 terminaux. Par exemple, la fonction représentative de la ressource consommée par chaque terminal i est donnée par la relation :

φ(y) = Σm_i +ΣM_i +∑(ffⁱ⁾(y)

dans laquelle :

∑m, correspond à la somme des ressources affectées aux terminaux auxquels la valeur de ressource minimale est affectée ;

ΣM, correspond à la somme des ressources affectées aux terminaux auxquels la valeur de ressource maximale est affectée ;

( ^υY¹ >Y'^"1 représente l'inverse de la dérivée de la fonction d'utilité/..

En outre, la valeur pivot qui correspond aux valeurs optimales des ressources peut être donnée par la relation :

_/?* = [∑(/'.)-¹]^"1(C-Σm,. -ΣM,.)

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, lors duquel, à 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éîécomniuπicatioi t pour un ensemble de terminaux mobiles de télécommunication du réseau, l'équipement convenant à la mise en œuvre du procédé selon l'invention et comprenant,

- des moyens d'affectation d'une fonction d'utilité (ή) et de valeurs de ressources minimale (mi) et maximale (MO à chaque terminal (T) ;

- des moyens d'estimation d'une ^{fonction d}'^utilité 9^{|obale à} P^{artir de fonctions} d'utilité propres à chaque terminal,

- des moyens de détermination d'une fonction (fj¹) représentative des ressources consommées par chaque terminal; - des moyens de détermination d'une valeur optimale

de ressources pour chaque terminal à partir de valeurs desdites fonctions représentatives des ressources consommées, et

- des moyens d'affectation de ladite valeur optimale au terminal pour lequel cette valeur a été déterminée.

Cet équipement comprend notamment des moyens de traitement de données aptes à mettre en œuvre les différentes étapes du procédé selon l'invention. 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 I 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 terminaux ;

- 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

Q, C₂, et C₃. 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 Q, C₂ et C₃ 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 :

II s'agit en outre de satisfaire aux contraintes suivantes : λ -m, ≥ 0 V, ,P) (2)

M -X. ≥ 0 V,- e {l, .. -F} (3)

Dans ces relations (1 ) à (4) :

- X₁ est une variable dans l'ensemble des réels positifs et désigne des ressources affectées au terminal i,

- m,, est une donnée dans l'ensemble des réels positifs et désigne une borne minimale de ressources affectée au terminal i, - M,, est une donnée dans l'ensemble des réels positifs et désigne une borne maximale de ressources affectée au termina! i,

- C est une donnée dans l'ensemble des réels positifs et désigne la capacité globale du système, et

- /, 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 le terminal i.

En outre, dans ces relations (1 ) à (4), on suppose que p est un entier positif, que la fonction /, 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 terminal doit être comprise entre une borne minimale m, et une borne maximale M₁ , et que la somme des ressources affectées aux terminaux doit rester inférieure à la capacité globale C du système.

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 :

qui correspond à la somme des fonctions d'utilités f.{λ) affectées à chaque terminal i. Ces fonctions d'utilités individuelles // caractérisent des intérêts économiques ou privés à recevoir, pour un termina! i, une ressource λ.. Ainsi, !a fonction d'utilité globale permet de prendre en compte l'ensemble des terminaux. 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 terminal 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 terminaux 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 terminal reçoit une ressource A₁. bornée suivant les valeurs du tableau de la figure 3. En d'autres termes, chaque valeur de ressource A₁ est comprise entre les valeurs de seuil m, et M₁. Dans l'ensemble de réalisation considéré, un coefficient d'utilité β_t. est alloué à chaque terminal pour le calcul de la fonction d'utilité fj(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 du terminal 4, la cellule n'est pas saturée et chaque terminal 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 à affecier à chaque terminai \ une fonction d'utilité ft et des valeurs des ressources minimale et maximale m,

et M₁ (étape 22). En particulier, la fonction d'utilité fi peut s'exprimer sous la forme :

dans laquelle «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 terminal 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 {l, ..., 2p] les informations suivantes sur la k-ième valeur :

Utilisateur (k) = i Borne (k) = m_t. ou M₁.

Valeur (k) = f i (Borne (k)). On aura Valeur (1) ≤ Valeur (2) ≤ ... ≤ Valeur (2p) et pour chaque terminal i, il existe deux valeurs ki < k₂ avec Utilisateur (k-ι) = Utilisateur (k₂)= i, Borne (ki) = M. et Borne (k₂) = m, . On notera dans ce cas Début (i) = (ki) et Fin

(i) = (k₂).

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 terminaux. Elle se calcule en fonction de la capacité que l'on peut fournir aux terminaux. 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 : Tant que Haut - Bas > 1 Milieu : = (Haut + Bas)/ 2 Phi : = O

Pour tous les terminaux i Si Début (i) > Milieu phi : = phi + M₁. Si Fin (i) < Milieu phi : = phi + m.

Si Début (i) < Milieu et Fin (i) > Milieu phi : = phi + (f ι)^"1 (Milieu)

Si phi > 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 {l, ..., 2p). Lors de l'étape 30 suivante, on procède au calcul proprement dit de la valeur pivot p, à partir de la relation :

p* = ψ-^ι(Keste) Où ψ ≈ ∑/r (6) i

La valeur Reste est en particulier calculée à partir de l'algorithme suivant

Reste : = C Pour tous les terminaux i

Si Début (i) > Bas Reste : = Reste - M₁ Si Fin (i) < Haut Reste : = Reste -m. ψ désigne alors la somme des fonctions (//)^"' pour i vérifiant Début (i)

< Bas et Fin (i) > Haut.

On procède enfin à une affectation des valeurs calculées (étape 31). Pour chaque terminal i, la valeur de ressources λ. qui lui est affectée est donnée par :

Si Début (i) > Bas, alors λ, : = M,

Si Fin (i) < Haut, alors À, : = m. Sinon, V= (/',TV)-

Comme cela va maintenant être démontré par la suite, les ressources affectées aux terminaux ainsi calculées constituent une solution d'affectation des ressources optimale. Supposons que les fonctions fi, pour i compris dans l'intervalle

{l, ..., p] soient strictement concaves, que la contrainte :

est vérifié à l'égalité par une solution optimale, et que la fonction fj est calculable en une opération. Supposons que l'on puisse calculer l'inverse de toute somme d'inverses des f'i pour i compris dans l'intervalle {l, ..., p] en M opérations. Alors les ressources, c'est-à-dire Sa solution aux relations (1) à (4), sont calculables en M + O (p log(p)) opérations, O désignant la notation de Landau.

Par application des conditions de Kuhn-Tucker, on obtient, pour la solution optimale À^* pour i appartenant à l'intervalle {l, ..., p), et les coefficients réels positifs duaux pi, v_t pour i compris dans {l, ..., p} et p, rM)-μ, +v, +p ≈ 0 V, e {l, .„,/>},

//,(4 -ιn,)= 0 V,. e {l, ..., ;>},

V₁(M₁ -^)= O V₁ e {l, ..., />} , βt

Pour chaque i compris dans l'intervalle {l, ..., p) , trois cas peuvent se présenter.

1) λ^* -m. Dans ce cas v, = 0. Par conséquent - /',. (A^*)- //,. +p = 0 , ce qui donne /'. (λ^*)≤ p .

2) λ^*-M₁. Danscecas μ, =0. Parconséquent- /',.(λ^*)-v,+p=0, cequidonne /'.(λ^*)≥p.

3) λ^* e ]m.,M₍.[. On a alors v. = 0 et μ_{. - 0, soit rM)^{≈ p}- Autrement dit, si /.^' est strictement décroissante et continue avec i appartenant à l'intervalle {l, ..., p], elle est inversible et, à chaque valeur réelle de p , on peut associer une capacité "consommée" définie par :

Comme on le conçoit, φ est une fonction décroissante de p . Une solution optimale est alors donnée par une valeur p * qui vérifie :

<p(p *)= C (8)

L'algorithme de calcul de la solution aux relations (I) à (4) ci-dessus peut être réalisé comme suit.

Soit X={m m_p}U{Mi, ...M_p}. On a \x\ ≤ 2_p . On calcule tout d'abord des valeurs des fonctions f. pour obtenir l'ensemble Y défini par ia relation :

Y = {/'. {m). ,i e [l,p](u {/',. (M₁)J _€ [l,p]} 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 <= Y, on calcule φ (y) en O(p) opérations, et en O(log (p)) étapes on trouve deux valeurs consécutives yi<y₂, telles que φ(y_x)≥ C et φ(γ₂)< C . Dans les cas limites, V2 vaut 0, ou yi vaut l'infini.

Si ç?(y-ι) = C, alors l'équation p*= yi donne une solution.

Sinon, les ressources du réseau consommées par un terminal i sont données par :

vve]y,,_Λl M_{1 +}

(fiViy).

,':/;(Λ/,)≤_Λ<_Λ≤/;(/n,)

La valeur pivot p* est alors donnée par la relation suivante :

p* = kf_ι'(M_i)≤y_ι<y₁≤f_l(m_l) ur ^c~ Σ ™i - Σ ^M< O)

'-yi>fl{m,) i-y[<fi(^Mι)

La fonction d'utilité fj(x) affectée aux terminaux peut être de diverses formes. l-α

Dans le cas où f_i(x) = β. , pour α e ]θ ;l[l)]l,+∞[_> ^alors l - α l'allocation des ressources est calculable en O(plog(p)).

Dans ce cas, f!(x) = β_ix^~aet fi^~ι(y)≈ — y^~Ua - Donc, pour r i

J e {l, ..., p} si on pose

alors

Pour J donné, cette fonction est calculable en O(p) opérations. Dans le cas où fj(x)=ln(x), alors l'allocation des ressources est calculable en O(p log(p)).

Dans ce cas, f^'(_x)= - et f-^~{{y)= — - Donc, pour J e {l, ..., p] si on x y pose

i<=J

alors

Enfin, si

, alors la solution est calculable en O(p log(p)).

Dans ce cas, f_t ^'(x) = β_r En raisonnant de manière similaire au résultat ci-dessus, on considère Y={β, : i e{1 , ..., p}}, et

φ est une fonction en escalier décroissante. On cherche deux valeurs yi et y₂ consécutives de Y, telles que y-i<y₂, avec #>(yi)≥C et ç?(y₂)<C. Dans ce cas, une ressource optimale Z^* est donnée par :

De manière concrète, et en se référant maintenant aux figures 5 à 7,

Λ-a considérera tout d'abord le cas où f_s(x) = P₁ pour « =1/2,

\-a f- (χ)= β,l4χ . 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 terminal 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 :

U(M₄) = K(M₃) < W(M₁) < f₄ ^'(m₄) = f₃'(m₃) < Mm₁) < V(M₂) < f₂'(m₂)

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

Cette fonction est représentée sur la figure 6. !l s'agit de repérer ia position où φ (x) = 100. La valeur pivot est alors dans l'intervalle [0,91 ; 1 ,58], où la fonction φ est donnée par φ(x) = 60+50/x², ce qui donne un pivot pour x=0,73. Les débits obtenus vont donc réduire les terminaux 3 et 4 à la valeur commune de 20.

De même, en se référant à nouveau à la figure 5, dans le cas où fj(x)=1n(x), les valeurs calculées pour f se classent de la manière suivante :

W(M₁) < f3(M₃) = W(M₄) < f₂'(M2) < Mm₁) < W(In₂) = f₃'(m₃) = f₄'(m₄).

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

Enfin, si fj(x)=ιτijX, les valeurs de f peuvent être triées comme suit :

f₃'(m₃) = K(M₃) = U'(m₄) = W(M₄) < W(Ui₁) = W(M₁) < f₂'(m₂) = W(M₂).

La fonction φ(x) est alors une fonction constante par intervalles donnée par : pour x e [ 5; 10] „ φ(x) = 70 ; et pour x e [10; 20] φ (x) = 40, la valeur pivot est alors comprise dans l'intervalle de [5; 10].

Claims

REVENDICATIONS

1. Procédé d'allocation de ressources d'un réseau cellulaire (Ci, C2,

C₃) 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 estimée à partir de fonctions d'utilité propres à chaque terminal, tout en satisfaisant des contraintes liées aux ressources du réseau mises à disposition des terminaux, caractérisé en ce qu'il comporte les étapes suivantes :

- affectation d'une fonction d'utilité (fj) et de valeurs de ressources minimale (mi) et maximale (Mi) à chaque terminal (T) ;

- détermination d'une fonction (fi') représentative des ressources consommées par chaque terminal;

- détermination d'une valeur optimale vΛ) de ressources pour chaque terminal à partir de valeurs desdites fonctions représentatives des ressources consommées, et

- affectation de ladite valeur optimale au termina! pour lequel cette valeur a,, été déterminée.

2. Procédé selon la revendication 1 , dans lequel la fonction d'utilité globale est la somme des fonctions d'utilité propres à chaque terminal.

3. Procédé selon l'une des revendications 1 à 2, 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 terminal pour chaque valeur minimale et maximale ;

- tri des valeurs calculées de la dérivée de la fonction d'utilité propre à chaque terminal ; - 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 à un terminal correspondant soit à la valeur de ressource minimale, soit à la valeur de ressource maximale, soit à une valeur calculée à partir de la valeur pivot.

4. Procédé selon la revendication 3, caractérisé en ce que la valeur de ressources calculée (A₁) à partir de la valeur pivot est calculée, pour les terminaux i pour lesquels la valeur pivot est utilisée pour déterminer la valeur optimale, à partir de la relation suivante

dans laquelle (/ j ' représente l'inverse de la dérivée de la fonction d'utilité et p * désigne un coefficient dual réel.

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

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 terminal doit être supérieure à la valeur de ressources minimale.

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

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

9. Procédé selon l'une quelconque des revendications 1 à 8, 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 terminaux.

10. Procédé selon la revendication 9, caractérisé en ce que la fonction φ (y) représentative de la ressource consommée par chaque terminal i est donnée par la relation :

_<p(y)= ∑OT_/ +ΣΛ/_/ +∑(/-O^(~l)(y) dans laquelle : ∑m,. correspond à la somme des ressources affectées aux terminaux auxquels la valeur de ressources minimale est affectée ;

IM₁ correspond à la somme des ressources affectées aux terminaux auxquels la valeur de ressources maximale est affectée ; et

(fi) ¹ représente l'inverse de la dérivée de la fonction d'utilité fj.

11. Procédé selon la revendication 10, caractérisé en ce que la valeur pivot qui correspond aux valeurs optimales des ressources est donnée par la relation :

dans laquelle C désigné la capacité globale du réseau.

12. Procédé de gestion des ressources d'un réseau cellulaire (C-i, C₂, C₃) 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 à 10 pour accepter le terminal entrant.

13. 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 d'affectation d'une fonction d'utilité (fi) et de valeurs de ressources minimale (nrij) et maximale (Mj) à chaque terminal (T) ; - des moyens d'estimation d'une ^{fonction d}'^utilité 9^{|obale à} P^{artir de fonctions} d'utilité propres à chaque terminal,

- des moyens de détermination d'une fonction (fj¹) représentative des ressources consommées par chaque terminal;

- des moyens de détermination d'une valeur optimale vΛ/ de ressources pour chaque terminal à partir de valeurs desdites fonctions représentatives des ressources consommées, et

- des moyens d'affectation de ladite valeur optimale au terminal pour lequel cette valeur a été déterminée.

14. 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 à 12.