Brevet FR2790626A1 — publié le 20000908

PROCEDE D'ALLOCATION DE FREQUENCES A UN ENSEMBLE D'EMETTEURS PAR RECHERCHE TABOU La présente invention concerne un procédé d'allo- cation de fréquences à un ensemble d'émetteurs, formant un réseau d'émetteurs, par recherche tabou. Le récent avènement de l'échange d'informations, en particulier de la diffusion d'informations sous forme de programmes télédiffusés ou radiodiffusés par voie hert- zienne, par l'intermédiaire de réseaux de télédiffusion ou de radiodiffusion, en raison de la très forte demande en matière de diffusion culturelle par ce type de réseaux, soumet les autorités chargées d'attribuer et de gérer les fréquences d'émission au problème délicat de l'allocation des fréquences radioélectriques aux émetteurs de ces ré- seaux. L'allocation de fréquences à un réseau radioélec- trique d'émetteurs est un problème complexe qui ne peut être résolu de façon déterministe que par l'intermédiaire d'un processus calculatoire à comportement exponentiel par rapport à la taille des données, considérées comme varia- bles indépendantes. En effet, pour un ensemble de n émet- teurs et un nombre c de canaux de fréquences disponibles, rechercher de manière déterministe la solution optimale minimisant les interférences entre les canaux de fréquen- ces allouées à ces émetteurs passe par l'exploration sys- tématique d'un espace de recherche comportant cn éléments. Une telle recherche n'est possible que pour des petites valeurs de c et n. Pour des cas de réseaux réalistes, com- portant plusieurs centaines d'émetteurs, cas des réseaux de radiodiffusion/télédiffusion, une telle recherche est exclue, car elle conduirait à des temps de calculs effec- tifs rédhibitoires en pratique. Afin de résoudre le problème précité, des techni- ques issues du domaine de l'optimisation combinatoire ont été développées, afin de proposer au moins une solution au caractère optimal relatif, mais accessible en un temps raisonnable, de l'ordre de quelques minutes, grâce à la mise en oeuvre de moyens de calculs non spécialisés. Les techniques précitées les plus récentes mettent en oeuvre une méthode d'exploration de l'espace de recher- che connue sous le nom de recherche "tabou", laquelle sera tout d'abord rappelée ci-après. Dans un premier temps, il est nécessaire de modé- liser, par des relations entre les données de l'espace de recherche, les contraintes induites, sur les émetteurs du réseau, par les critères de protection des zones de servi- ces de ces émetteurs. Pour un ensemble E d'émetteurs {e0,...,en-1}, un émetteur correspondant à un point d'émission d'un pro- gramme sur une fréquence porteuse donnée occupant un canal de fréquences, un ensemble C de canaux de fréquences {Co,...CN}, constituant un intervalle de canaux de fréquen- ces est disponible. Généralement, pçc " p9E, le nombre de canaux de fréquences étant très inférieur au nombre d'émetteurs du réseau, çc et ps représentant la cardinalité de chaque ensemble. Les critères de protection des zones de couverture d'émetteurs interférant potentiellement entre eux s'expri- ment sous la forme d'écarts minimaux entre les canaux de fréquences correspondant à leurs fréquences porteuses. Pour des canaux de fréquences ci et cj alloués respective- ment à deux émetteurs ei et ej, la contrainte d'espacement en fréquence s'exprime selon la relation: ci -c,À m. Le paramètre m est un nombre entier 2 1 lorsque chaque ca- nal de fréquences est exprimé sous la forme d'un rapport d'une fréquence centrale à un intervalle de fréquence in- cluant la largeur de bande de chaque canal et séparant, nécessairement, deux canaux de fréquences consécutifs. Le paramètre m peut ainsi prendre différentes valeurs pos- sibles, en fonction des positions et des puissances radio- électriques relatives des émetteurs i et j. Ainsi, m=1 dans le cas de la contrainte co-canal et m>1 dans le cas de la contrainte canaux adjacents. L'ensemble des contraintes relatives à un réseau d'émetteurs déterminé peut alors être modélisé sous forme d'un graphe, les noeuds de ce dernier représentant les émetteurs et les arcs reliant deux émetteurs, pondérés chacun par la valeur m, représentant la contrainte d'allo- cation ou de réallocation de fréquence entre les deux émetteurs considérés. A partir d'une telle modélisation, le problème d'allocation de fréquences peut être ramené à celui du co- loriage de graphe. Dans ce cas, la palette de couleurs n'est autre que l'ensemble des canaux de fréquences C. Pour une approche théorique des graphes, on pourra utile- ment se reporter à l'ouvrage publié par R.GOULD intitulé Graph Theory et édité par The Benjamin/Cummings Publishing Company, 1988. Toutefois, la construction du graphe des contraintes s'ap- puie sur des calculs de propagation d'ondes radioélectri- ques à partir des données physiques sur les émetteurs tels que position, caractéristiques d'antennes, puissance appa- rente rayonnée et rapports de protection du système, afin d'évaluer les brouillages mutuels induits entre les émet- teurs pris deux à deux. En prenant en compte les valeurs des rapports de protection, il est alors possible de dé- duire l'écart minimal en fréquence, ou en nombre d'inter- valles de fréquence, qui doit être respecté entre les fréquences porteuses des canaux de fréquences des émet- teurs considérés. L'ensemble des noeuds, c'est-à-dire des émetteurs, est partitionné en deux sous-ensembles, l'un regroupant les émetteurs dont la fréquence est modifiable, l'autre contenant les émetteurs dont la fréquence est fixée défi- nitivement. L'optimisation de l'allocation consiste en une amélioration d'une allocation initiale, au moyen d'une ex- ploration itérative de l'espace de recherche. Lorsque l'ensemble E des émetteurs comporte certains émetteurs dont la fréquence, pour des raisons techniques, de gestion ou autres, doit être maintenue inchangée, le plan de fré- quences correspondant à l'allocation initiale prend en compte de tels impératifs. La recherche tabou constitue, dans un tel contexte initial, une technique heuristique particulièrement adap- tée à ce type de recherche. Cette technique consiste, à partir de l'allocation initiale, à explorer l'espace de recherche suivant une séquence de déplacements ou modifi- cations des valeurs de canaux de fréquences alloués, à ti- tre d'essai, afin d'optimiser une fonction de coût calculable en tout point de l'espace de recherche. Le pas- sage d'une configuration d'allocation d'essai à une autre est effectué en retenant celle qui procure le gain le plus grand sur la fonction de coût. Cependant, à chaque itéra- tion de la recherche, certains déplacements sont classés tabous, et sont donc interdits, afin d'éviter l'introduc- tion d'optima locaux ou de séquences de déplacements cy- cliques. Le processus algorithmique de recherche tabou tient donc à jour l'ensemble des déplacements interdits, sous forme d'une liste, pour chaque émetteur courant ap- partenant à l'ensemble des émetteurs non tabous. L'ensem- ble des émetteurs tabous peut lui-même être actualisé, sur la base de critères spécifiques. L'ensemble ou la liste des déplacements tabous est formé à partir de l'historique des déplacements précédents. Le processus algorithmique de recherche tabou comprend en ou- tre des critères d'aspiration qui permettent de transgres- ser les interdictions introduites par la liste des déplacements tabous. Ce mécanisme de critères d'aspiration vise essentiellement à éviter les optima locaux. Pour une description plus détaillée d'une méthode de recherche tabou appliquée à un processus d'allocation de fréquences, on pourra utilement se reporter à l'article intitulé "A Tabu Search Algorithm for Frequency As- signment", publié par S. HURLEY, S-U. THIEL, D-H. smith, Annals of Operations Research, vol.63, pp.301-319, 1996. La méthodologie retenue dans le procédé décrit par le do- cument précité, outre les étapes précédemment décrites, vise avant tout à fixer le nombre maximum d'itérations mi- ses en oeuvre, la fonction de coût consistant uniquement en un recensement, dans le graphe, du nombre de contraintes violées lors de chaque essai. Un tel mode opératoire reste avant tout théorique car les paramètres d'entrée, nombre d'itérations, et le critère de calcul du nombre de contraintes violées sont choisis comp- te tenu de la puissance de calcul du calculateur mise en oeuvre et des critères de complexité calculatoire en temps correspondante, mais non pas en fonction des paramètres physiques du réseau à optimiser. En conséquence, alors qu'une telle méthode donne toute satisfaction au plan théorique, une application directement utilisable par l'autorité chargée, dans un espace national ou supra na- tional, de gérer l'allocation de fréquences de réseaux de radiodiffusion ou de télédiffusion ne peut être envisagée. La présente invention a pour objet de remédier à l'inconvénient précité par la mise en oeuvre d'un procédé d'allocation de fréquences par recherche tabou directement utilisable par les autorités et acteurs économiques char- gés de gérer et contrôler l'allocation de fréquences de réseaux de radiodiffusion ou de télédiffusion. Un autre objet de la présente invention est en conséquence la mise en oeuvre d'un procédé d'allocation de fréquences par recherche tabou paramétrable selon diffé- rentes stratégies prenant en compte certains paramètres physiques ou de gestion du réseau de radiodiffusion ou de télédiffusion à optimiser. En particulier, un autre objet de la présente in- vention est la mise en euvre d'un procédé d'allocation de fréquences permettant d'exploiter au maximum la bande de fréquences allouée au réseau tout en conférant à l'alloca- tion retenue un taux de violation de contraintes minimal. Un autre objet de la présente invention est la mise en oeuvre d'un procédé d'allocation de fréquences per- mettant de n'utiliser qu'un nombre limité de canaux de fréquences dans le plan de fréquences finalement retenu tout en ne dépassant pas une valeur de seuil déterminée du taux de violation des contraintes. Un autre objet de la présente invention est la mise en oeuvre d'un procédé d'allocation de fréquences per- mettant, à partir d'un même jeu de données, ensemble d'émetteurs et ensemble de fréquences disponibles, de fournir des plans de fréquences aux caractéristiques très différentes, afin de permettre à l'autorité ou aux acteurs économiques chargés de gérer et de contrôler l'allocation de fréquences de réseaux de radiodiffusion ou de télédif- fusion, de déterminer le meilleur compromis entre réutili- sation du spectre et respect des contraintes d'espacement en fréquence. Le procédé d'allocation de fréquences par recher- che tabou, objet de la présente invention, s'applique à un ensemble (E) d'émetteurs {eo,...,eN-1}, formant un réseau à partir d'un ensemble (C) de canaux de fréquences, l'ensem- ble (E) d'émetteurs et (C) de canaux de fréquences étant soumis en fonction de la topographie du réseau d'émetteurs {e0,...,eN-1} et des canaux de fréquences (co,...,cn-1} al- loués à chaque émetteur à des critères de protection de zones de couverture selon un graphe de contraintes d'espa- cement de canaux de fréquences de la forme ici-cjl m o m est un entier positif supérieur ou égal à 1 représentatif du risque d'interférence co-canal et canaux adjacents res- pectivement. Cet ensemble d'émetteurs est subdivisé en un sous-ensemble d'émetteurs Ef pour lequel aucun changement de canal de fréquences n'est réalisable, et en un sous- ensemble d'émetteurs Em (el,..., eM) pour lequel un change- ment de canal est réalisable à partir des canaux de fré- quences disponibles, ceci afin de permettre une réalloca- tion partielle éventuelle des fréquences sur un réseau d'émetteurs. Ce procédé est remarquable en ce qu'il consiste, à partir d'une fonction de coût h(p) représentative du taux de sa- tisfaction, respectivement de non-satisfaction de l'ensem- ble des contraintes d'espacement de canaux de fréquences, à initialiser cette allocation par un plan de fréquences spécifique, établi à partir de l'ensemble des canaux de fréquences disponibles pour ce réseau d'émetteurs, à cha- que émetteur (e1,..., eM) du sous-ensemble Em étant alloué un canal de fréquences (ci,..., cj) de cet ensemble de ca- naux disponibles, le plan de fréquences spécifique consti- tuant ainsi un plan de fréquences courant. L'allocation de fréquences est alors soumise à une étape de test à la va- leur vraie de conditions d'arrêt entraînant la fin du pro- cédé d'allocation de fréquences, au réseau d'émetteurs étant alloué le plan de fréquences courant. Sur réponse négative à l'étape de test de la valeur vraie des condi- tions d'arrêt, l'allocation est alors soumise à un test à la valeur vraie d'un critère d'aspiration relatif au taux de l'ensemble des contraintes d'espacement de canaux, pour un couple émetteur/fréquence correspondant à une contribu- tion maximale de non-satisfaction de la fonction de coût. Sur réponse positive au test à la valeur vraie du critère d'aspiration, à l'émetteur considéré, ek, est alloué le canal de fréquences ck de ce couple émetteur/fréquence. Sur réponse négative au test à la valeur vraie du critère d'aspiration, le procédé consiste alors à choisir un émet- teur courant appartenant à l'ensemble Em des émetteurs pour lequel un changement de canal est réalisable et à dé- terminer l'ensemble des canaux de fréquences amenant un gain sur la valeur courante de la fonction de coût pour cet émetteur courant non tabou, et à soumettre cet ensem- ble des canaux de fréquences amenant un gain sur la valeur courante de la fonction de coût pour cet émetteur courant non tabou à un test de vacuité. Sur réponse négative au test de vacuité, un canal de fréquences déterminé est choisi pour l'émetteur courant non tabou. Sur réponse positive au test de vacuité, le procédé d'al- location consiste alors, pour chaque émetteur voisin de cet émetteur courant, à choisir une valeur de canal de fréquences parmi l'ensemble des canaux de fréquences per- mettant de diminuer la valeur courante de la fonction de coût, à affecter la valeur de canal de fréquences choisie à cet émetteur voisin considéré et à mettre à jour la fonction de coût et le critère d'aspiration relatif au taux de satisfaction, respectivement de non- satisfaction, de l'ensemble des contraintes d'espacement de canaux. Suite à ces étapes de choix, d'affectation et de mise à jour relatives à chaque émetteur voisin de cet émetteur courant, le procédé consiste alors à mettre à jour le plan de fréquences courant par affectation du canal de fréquen- ces du couple émetteur/fréquence à l'émetteur considéré, la valeur de la fonction de coût et le sous-ensemble d'émetteurs tabous, par affectation de la valeur d'émet- teur tabou à cet émetteur considéré auquel le canal de fréquences a été attribué. Le plan de fréquences courant mis à jour obtenu est alors soumis à un processus itératif par retour à l'étape de test à la valeur vraie des condi- tions d'arrêt. Le procédé, objet de l'invention, trouve applica- tion à la gestion et au contrôle des réseaux de radio- et de télédiffusion. Il sera mieux compris à la lecture de la descrip- tion et à l'observation des dessins ci-après dans les- quels: - la figure la représente, à titre d'exemple pure- ment illustratif, un graphe des contraintes obtenu confor- mément au processus indiqué précédemment, seul un nombre limité d'émetteurs étant représenté, afin de ne pas sur- charger le dessin; - la figure lb représente, à titre de pur exemple non limitatif, un organigramme général représentatif du procédé d'allocation de fréquences, objet de la présente invention; - la figure 2a représente, à titre illustratif, un organigramme du critère relatif aux conditions d'arrêt du procédé objet de la présente invention, dans un mode de réalisation préférentiel, non limitatif; - la figure 2b représente, à titre purement illus- tratif, une matrice des violations de contrainte d'émet- teur/fréquence, pour toute allocation de fréquence courante, cette matrice permettant de contrôler le choix d'au moins un émetteur non tabou et le déplacement de fré- quence élémentaire appliqué à cet émetteur, ainsi que le processus d'itération; - la figure 2c représente à titre illustratif un tableau de coefficients de pondération disponible et per- mettant à l'utilisateur de paramétrer la fonction de coût; Il - la figure 3a représente un organigramme illus- tratif d'un processus de choix d'un émetteur non tabou au- quel un déplacement de fréquence élémentaire doit être appliqué dans un mode de réalisation préférentiel non li- mité; - la figure 3b représente un organigramme illus- tratif d'un processus de choix disponible et du déplace- ment de fréquence élémentaire appliqué à un émetteur non tabou choisi. Préalablement à la description proprement dite du procédé, objet de la présente invention, quelques rappels descriptifs relatifs à des éléments et à une notation for- melle des paramètres mis en jeu par une recherche tabou seront donnés ci-après. D'une manière générale, on indique que pour un es- pace de recherche S donné, un procédé d'allocation de fré- quences par recherche tabou consiste à chercher la valeur minimale d'une fonction de coût. Le processus de recherche tabou suppose qu'il existe, sur l'espace de recherche S, un ensemble de k fonctions déplacements, ensemble noté D = {d1,..., dk} ap- plicable à une configuration ou allocation possible, notée s. Ces déplacements produisent un ensemble D(s) = {d1(s), dk(s)} de k autres configurations possibles dans l'es- pace de recherche S. On définit alors un sous-ensemble, noté V(s) strictement inclus dans l'ensemble des configu- rations D(s), ce sous-ensemble V(s) étant appelé voisinage de la configuration possible s. Formellement, le processus d'allocation par re- cherche tabou peut être schématisé de la façon suivante: engendrer une configuration initiale s E S; * fixer un nombre déterminé d'itérations maximal I; * pour chaque itération successive: tant qu'une variable de comptage est inférieure au nom- bre maximal I d'itérations: - déterminer un voisinage V(s) inclus dans l'espace de recherche S; - déterminer un ensemble tabou T(s) inclus dans ce voi- sinage V(s)); - déterminer A(s) ensemble des conditions satisfaisant * au critère d'aspiration appartenant à l'ensemble ta- bou T(s); - choisir une configuration s' appartenant à un ensem- ble formé par l'union de l'ensemble déterminé par les critères d'aspiration A(s) et de l'intersection de l'ensemble de voisinage V(s) et de l'ensemble tabou T(s), pour laquelle la fonction de coût h(s') est mi- nimale, s'e(v(s)-T(s)) u A(s) pour lequel h(s') est minimale; - affecter à la configuration initiale considérée comme configuration courante la configuration choisie s', s = S'; - procéder à une itération jusqu'à la fin du proces- sus. Dans le processus précédemment décrit, la condi- tion d'arrêt est réalisée lorsque le nombre d'itérations a atteint le nombre I d'itérations maximum. En outre, on indique que les conditions qui défi- nissent un élément du voisinage V(s) comme aspirant ou ta- bou sont bien sûr spécifiques à chaque problème, c'est-à- dire à chaque réseau de radiodiffusion ou télédiffusion pour lequel il est souhaité de procéder à une allocation de fréquences. Une description plus détaillée du procédé d'allo- cation de fréquences par recherche tabou, conforme à l'ob- jet de la présente invention, sera maintenant donnée en liaison avec la figure la. En référence à la figure précitée, on indique que: - G désigne le graphe de contraintes associé à un ensemble d'émetteurs E, cet ensemble sur la figure préci- tée étant réputé, à titre d'exemple non limitatif, compor- ter cinq émetteurs, notés e1 à e5; - de même, Ef désigne le sous-ensemble des émet- teurs dont la fréquence est fixée, ces émetteurs, dans l'exemple non limitatif de la figure la, pouvant a priori consister en les émetteurs e5 et e4 par exemple. Ces émet- teurs sont par exemple des émetteurs de forte puissance ou extérieurs à la zone à replanifier; - Em = {e1,..., eM} désigne le sous-ensemble des émetteurs de E dont les fréquences sont modifiables. - en référence à la figure la, Em = {el, e2,e3}. - C = {Co,..., ck} désigne l'intervalle des canaux disponibles dans une bande de fréquences donnée, définie par exemple par l'autorité chargée de la gestion et du contrôle de l'allocation de fréquences dans l'espace ra- dioélectrique d'un état ou un groupe d'états. L'espace de recherche S est défini comme l'ensem- ble O des fonctions d'allocation p faisant correspondre au sous- ensemble Em des émetteurs à fréquence modifiable l'ensemble des canaux de fréquences disponibles dans la bande de fréquences attribuée, c'est-à-dire l'ensemble C, chaque fonction d'allocation p étant notée p: Em-> C. On indique qu'à chaque fonction p correspond une allocation courante par exemple. Pour un spectre de fréquences limité correspondant à l'ensemble C de l'intervalle des canaux de fréquences disponibles et pour une allocation de canaux de fréquences p, la fonction de coût à minimiser, et de préférence à an- nuler, dans l'ensemble O des fonctions précitées, c'est- à-dire sur l'espace de recherche S, est le nombre de con- traintes non respectées dans le graphe de contraintes tel que représenté à titre d'exemple illustratif en figure la, par la fonction d'allocation p. Pour toute fonction d'allocation p appartenant à l'ensemble O précité, le voisinage V(9), voisinage cor- respondant à l'allocation courante 9, peut être défini par la relation (1): V(ç) = {lye/3iE[0...n],y(ei) É p(el) et Vjó i,T(ej) = p(ej)} En référence à la relation précédente, on indique que le passage d'une configuration ou allocation courante à une allocation voisine est effectué en changeant unique- ment le canal de fréquences affecté à un émetteur donné du sous-ensemble des émetteurs Em dont les fréquences sont modifiables, c'est-à-dire l'un des émetteurs el,e2 ou e3 dans le cadre de l'exemple non limitatif de la figure la. Une condition simple de définition de l'ensemble tabou lors de chaque itération peut consister, pour un en- tier r déterminé, en une condition d'appartenance à cet ensemble tabou consistant en la reprise sur un émetteur quelconque, les émetteurs e1,e2, e3 précités, d'un canal de fréquences qui lui a déjà été attribué au cours des r pré- cédentes itérations. Un critère d'aspiration simple peut également con- sister à retenir dans l'ensemble tabou, s'il la contient, la configuration ou allocation de fréquences la meilleure depuis le début du processus de recherche. En référence à la figure lb et aux notations et définitions précédemment introduites, le procédé d'alloca- tion de fréquences à un ensemble E d'émetteurs {e0,..., en_} formant un réseau d'émetteurs par recherche tabou à partir d'un ensemble C de canaux de fréquences, objet de la pré- sente invention, consiste à établir un graphe de contrain- tes G d'espacement de canaux de fréquences de la forme c1-cjI>m, m étant un entier positif supérieur ou égal à 1 représentatif du risque d'interférence co-canal et canaux adjacents entre ces émetteurs. Le graphe des contraintes G est établi à partir des ensembles E d'émet- teurs et de canaux de fréquences C soumis, en fonction de la topographie du réseau d'émetteurs et des canaux de fré- quences alloués à chaque émetteur à des critères de pro- tection de zones de couverture selon le graphe des contraintes précitées. A titre d'exemple non limitatif, ainsi que repré- senté en figure la, le graphe des contraintes est établi de la manière ci-après: Ic1-c21 2 4 IC2-c31 2 2 Ic3-c41 2 4 Ic4-c51 2 5 ICl-c31 2 1IC2-c41 En outre, ainsi que représenté en figure la, l'en- semble d'émetteurs E est subdivisé en un sous-ensemble d'émetteurs à fréquence fixée a priori, noté Ef, pour le- quel aucun changement de canal de fréquences n'est réali- sable, et en un sous-ensemble d'émetteurs à fréquence modifiable Em {el,..., eM}, soit {e1,e2,e3} en référence à la figure la, pour lequel un changement de canal de fréquen- ces est réalisable à partir des canaux de fréquences dis- ponibles. Selon un aspect particulièrement remarquable du procédé, objet de la présente invention, celui-ci con- siste, à partir d'une fonction de coût h(p) o p désigne la fonction d'allocation précédemment mentionnée dans la description, cette fonction de coût étant représentative du taux de satisfaction, respectivement de non- satisfaction de l'ensemble des contraintes d'espacement de canaux, à initialiser, en une étape 1000, cette allocation de fréquences par un plan de fréquences spécifique établi à partir de l'ensemble des canaux de fréquences disponi- bles pour le réseau d'émetteurs à planifier. Sur la figure lb, et de façon non limitative, l'étape d'initialisation 1000, outre une étape de début non référencée conformément à la représentation conven- tionnelle habituelle, en une étape d'instanciation ou de définition du réseau à planifier, cette étape d'instancia- tion correspondant par exemple en une définition de chaque sommet du graphe, c'est-à-dire des émetteurs el à e5 ainsi que des arcs reliant ces émetteurs et en la définition des contraintes inter-émetteurs pondérant chacun des arcs pré- cités. Ces opérations réalisées sous forme informatique ne seront pas décrites en détail car elles correspondent à des opérations classiques en matière de prestations infor- matiques. L'étape 1000 précitée peut également consister à établir un plan de fréquences initial à l'étape 1000b. Le plan de fréquences initial peut être constitué par un plan de fréquences arbitraire ou, de préférence, en un plan de fréquences spécifique, ainsi qu'il sera décrit ultérieure- ment dans la description. Enfin, l'étape d'initialisation 1000 comporte également une étape 1000c consistant à dé- terminer les canaux de fréquences disponibles, c'est-à- dire l'ensemble C précédemment mentionné dans la descrip- tion. Cette étape est réalisée à partir de la bande de fréquences allouée par l'autorité chargée de gérer l'allo- cation de fréquences au réseau d'émetteurs de radiodiffu- sion ou de télédiffusion considéré. On comprend ainsi que lors de l'étape d'initiali- sation 1000, à chaque émetteur el,..., eM du sous-ensemble Em d'émetteurs à fréquence modifiable, est alloué un canal de fréquences ci,... cj de cet ensemble de canaux disponi- bles. Le plan de fréquences spécifique constitue ainsi un plan de fréquences courant pour la mise en ouvre du procé- dé, objet de la présente invention. Bien entendu, en ce qui concerne les émetteurs e5 et e4, lesquels sont considérés au départ comme consti- tuant l'ensemble d'émetteurs à fréquence fixée a priori Ef, dans le plan de fréquences spécifique, à ces émetteurs est alloué un canal de fréquences déterminé, fixe, compte tenu des impératifs de radioprotection et de protection de zones de couverture correspondantes. Il est bien entendu que, conformément au procédé, objet de la présente inven- tion, lorsqu'aucun des émetteurs ne fait partie de l'en- semble Ef, celui-ci s'applique à un réseau dans lequel tous les émetteurs de ce réseau sont susceptibles d'être soumis à un déplacement de fréquences. Ainsi qu'on l'observera en outre sur la figure lb, le procédé, objet de la présente invention, consiste, suite à l'étape 1000 précitée, en une étape 1001 consis- tant à soumettre l'allocation de fréquences considérée, c'est-à-dire, lors de la première passe de recherche, le plan de fréquences spécifique constituant le plan de fré- quence courant, à une étape de test à la valeur vraie de conditions d'arrêt spécifiques à certains paramètres pro- pres au réseau et à l'utilisation de ce dernier. Ces para- mètres seront explicités plus en détail dans la description. Sur réponse positive au test 1001 précité, la va- leur vraie des conditions d'arrêt entraîne la fin du pro- cédé d'allocation de fréquences à l'étape 1010 représentée en figure lb. Dans ces conditions, au réseau d'émetteurs est alloué le plan de fréquences courant. Il est bien en- tendu que, sauf cas particulier peu probable, le plan de fréquences spécifique établi à l'étape 1000b de l'étape d'initialisation 1000, ne peut a priori constituer un plan de fréquences satisfaisant aux conditions d'arrêt de l'étape 1001. Au contraire, sur réponse négative à l'étape de test 1001, la valeur vraie des conditions d'arrêt n'étant pas établie, le procédé, objet de la présente invention, consiste à soumettre l'allocation de fréquences courante à un test à la valeur vraie d'un critère d'aspiration rela- tif au taux de l'ensemble des contraintes d'espacement de canaux pour un couple émetteur/fréquence correspondant à une contribution maximale de non-satisfaction de la fonc- tion de coût. En pratique, on indique que la fonction de coût précitée est appliquée localement à l'émetteur considéré afin d'évaluer la contribution de ce dernier. Une description plus détaillée d'un mode de réa- lisation avantageux du test 1002 à la valeur vraie du cri- tère d'aspiration sera donnée ultérieurement dans la description. Sur réponse positive au test 1002 à la valeur vraie de ce critère d'aspiration, à l'émetteur considéré ek est alloué le canal de fréquencess ck de ce couple émetteur/fréquence à l'étape 1003 tel que représentée en figure lb. Sur réponse négative à la valeur vraie 1002 du critère d'aspiration, le procédé, objet de la présente in- vention, consiste ensuite, en une étape 1004, à choisir un émetteur courant appartenant à l'ensemble des émetteurs non tabous et à déterminer l'ensemble des canaux de fré- quences disponibles pour cet émetteur courant non tabou. Suite à l'opération 1004 précitée, l'ensemble des canaux de fréquences disponibles pour cet émetteur courant non tabou étant réputé constitué, le procédé, objet de la présente invention, est alors suivi d'une étape 1005 con- sistant à soumettre l'ensemble des canaux de fréquences offrant un gain sur la valeur courante de la fonction de coût pour cet émetteur courant non tabou, c'est-à-dire l'ensemble précédemment constitué à l'étape 1004, à un test de vacuité consistant à déterminer si cet ensemble est vide ou non. En pratique, on indique que l'ensemble des canaux de fréquences offrant un gain sur la valeur courante de la fonction de coût pour cet émetteur courant peut avantageusement être constitué par une liste dont les éléments correspondent à des valeurs de canaux de fréquen- ces et pour laquelle il est particulièrement aisé de re- connaître le caractère de vacuité ou d'absence de vacuité. L'ensemble des canaux de fréquences considéré est désigné par Fk pour l'émetteur ek considéré. Sur réponse négative au test de vacuité 1005 pré- cédemment mentionné, le procédé, objet de la présente in- vention, consiste à choisir dans l'ensemble Fk de canaux de fréquences disponibles pour cet émetteur courant non tabou ek un canal de fréquences déterminé, noté fK ou, plus précisément ck sur la figure lb. Le choix du canal de fréquences ck ou de la fréquence fk alloué effectivement à l'émetteur courant considéré ek peut être effectué de ma- nière arbitraire dans l'ensemble ds valeurs de fréquences ou de canaux de fréquences correspondantes, ou de manière plus particulière, ainsi qu'il sera décrit ultérieurement dans la description. Au contraire, sur réponse positive au test 1005 de vacuité, le procédé, objet de la présente invention, con- siste, pour chaque émetteur voisin v, émetteur voisin de l'émetteur courant ek, à effectuer à l'étape 1007 les opé- rations ci-après: En premier lieu, un choix d'une valeur de canal de fréquences f est effectué parmi l'ensemble des canaux de fréquences disponibles de façon à diminuer la valeur de la fonction de coût h(). Cette opération est suivie d'une opération consistant à affecter la valeur de canal de fré- quences choisie f à cet émetteur voisin considéré v, puis d'une opération consistant à mettre à jour, d'une part, la valeur de la fonction de coût h(T), compte tenu de cette nouvelle affectation, ainsi que le critère d'aspiration relatif à la valeur courante de la fonction de coût h(p). On comprend en particulier que la mise à jour à l'étape 1007 du critère d'aspiration relatif au taux de satisfac- tion ou de non-satisfaction de l'ensemble des contraintes d'espacement des canaux consiste en fait à mettre à jour tous les outils permettant l'évaluation de ce critère d'aspiration à l'étape 1002 précédemment décrite, ainsi qu'il sera décrit ultérieurement dans la description. L'étape 1007 est alors suivie d'une étape 1008 consistant elle-même à mettre à jour le plan de fréquences courant par affectation du canal de fréquences du couple émetteur/fréquence à l'émetteur considéré, c'est-àdire à la suite du choix du couple ek,fk à l'étape 1003 ou à la suite du choix - canal de fréquence3 fK dans l'ensemble Fk lorsque celui- ci n'est pas vide à la suite de l'étape 1006. En outre, l'étape 1008 consiste également à mettre à jour le sous-ensemble d'émetteurs tabous constitué par une liste d'émetteurs tabous par affectation de la valeur d'émetteurs tabous à l'émetteur ek considéré précédemment mentionné auquel le canal de fréquences fk a été attribué. En fait, l'émetteur ek considéré est inséré dans la liste d'émetteurs tabous. De la même manière qu'à l'étape 1007, le critère d'aspiration relatif au taux de satisfaction ou de non- satisfaction de l'ensemble des contraintes d'espacement de canaux est mis à jour à l'étape 1008 suite aux opérations 1003 et 1006 précédemment mentionnées. Suite à l'étape 1008 précédemment citée, le procé- dé, objet de la présente invention, consiste alors, en une étape 1009, à soumettre le plan de fréquences courant, le- quel a été mis à jour dans les conditions précédemment mentionnées, à un processus itératif par retour à l'étape de test à la valeur vraie des conditions d'arrêt 1001. On comprend en particulier qu'en l'absence de sa- tisfaction aux conditions d'arrêt à l'étape de test 1001 précitée, le processus est répété par itérations sur un ensemble d'émetteurs non tabous, lequel évolue et certai- nement diminue au cours de la mise en ouvre du procédé, objet de la présente invention, ce qui permet de mettre en oeuvre ce dernier sur un nombre donné d'itérations qui n'est pas directement limité par la puissance de calcul du système de calcul permettant la mise en ouvre de ce der- nier, mais au contraire par les conditions d'arrêt véri- fiées qui dépendent essentiellemep.t de certains paramètres du réseau auquel le plan de fréquences doit être alloué. Lorsque ces conditions d'arrêt sont vérifiées à l'étape 1001, ainsi que représenté en figure lb, l'étape 1010 de fin de procédé est alors mise en oeuvre. Différents éléments descriptifs plus spécifiques relatifs aux étapes ou aux sous-étapes de mise en oeuvre du procédé, objet de la présente invention tel que décrit en figure lb, seront donnés maintenant ci- après: En ce qui concerne en premier lieu les conditions d'arrêt de l'étape de test 1001, en référence à la figure la, on indique que, de manière particulièrement avanta- geuse, celles-ci peuvent comprendre un critère de test 1001b de comparaison d'infériorité, pour le plan de fré- quences courant considéré, du taux de non-satisfaction des contraintes définies comme le rapport du nombre de con- traintes non respectées au nombre total de contraintes du graphe des contraintes à une première valeur de seuil dé- terminée. Ce taux de non-satisfaction T est calculé à l'étape 1001a. Dans un autre mode de mise en oeuvre plus spécifi- que, le test 1001 des conditions d'arrêt peut comprendre un critère de test de comparaison 1001c de supériorité du nombre déterminé d'itérations du processus itératif à l'étape 1009 à une deuxième valeur de seuil déterminée pour lesquelles aucune amélioration de la valeur de la fonction de coût n'est obtenue. Ce dernier mode opératoire permet de supprimer toute oscillation en boucle infinie du processus d'itération, en particulier lorsque ce test est associé au test précédent et que le test précédent de com- paraison d'infériorité pour le plan de fréquences courant !5 ccns-_4-Idér du t d2 rCl-*.jfa7c -J' r. d-3 1i- teint une valeur proche de mais supérieure à la première valeur de seuil déterminée précitée. Le taux de violation est calculé globalement sur le graphe. De préférence, la réponse positive au test 1001 précité et la sortie vers l'étape de fin du procédé 1010 est obtenue pour l'une ou l'autre des conditions de test telles que représentées en figure 2a, dans laquelle T dé- signe le taux de violation des contraintes, S1 la première valeur de seuil, K le nombre déterminé d'itérations suc- cessives du processus itératif pour lequel aucune amélio- ration de la fonction de coût n'est obtenue, S2 la deuxième valeur de seuil. hi(p) désigne la valeur de la fonction de coût à l'itération i et ho(p) la valeur mini- male de cette fonction antérieurement aux K itérations successives. En ce qui concerne le test de critère d'aspiration vérifié 1002, un mode de réalisation préférentiel non li- mitatif sera décrit en liaison avec les figures la et 2b. D'une manière générale, on indique que le test 1002 à la valeur vraie d'un critère d'aspiration relative au taux de satisfaction ou de non-satisfaction de l'ensem- ble des contraintes d'espacement de canaux pour un couple émetteur/fréquence ek,fk donné, correspond à une contribu- tion de non-satisfaction de la fonction de coût. Il peut comprendre un critère d'appréciation sur le gain en dimi- nution obtenu sur la fonction de coût précitée. Cette opération, telle que représentée en figure 2b, peut consister à établir une matrice des violations de contraintes dans laquelle les valeurs de contraintes ef- t5 fe tives. peur des dn.ux de fré_ences..tés fo fI sur la figure 2b susceptibles d'être alloués aux émetteurs el à e5 tels que représentés en figure la, sont portées dans un arrangement de lignes correspondant aux valeurs de ca- naux de fréquences précités et de colonnes correspondant à chacun des émetteurs. Sur la figure 2b, les valeurs de violation de contraintes sont données en valeur relative à titre purement arbitraire, illustratif pour l'allocation courante indiquée. Conformément à un aspect particulière- ment remarquable du procédé, objet de la présente inven- tion, le processus itératif mis en oeuvre s'appuie sur une matrice de violation des contraintes, permettant d'évaluer les violations induites par chaque émetteur ek à replani- fier. Pour un plan de fréquences courant 9 donné, on pro- cède dans ce but au calcul, pour chaque couple émetteur/fréquence ek, fk, d'un terme v(ek, fk,) correspon- dant à la somme pondérée des violations induites par l'en- semble des couples ek, fk, si l'on procède à un déplace- ment élémentaire dans l'espace de recherche S consistant à allouer une fréquence donnée, f0 à f7 sur la figure 2b, la fréquence ou le canal de fréquences alloué aux autres émetteurs ej, jÉk restant inchangée. Ainsi, l'arrangement en lignes, colonnes précité représenté en figure 2b per- met de déterminer, sur une colonne donnée, pour un émet- teur ek donné, la valeur de fréquence allouée à et émetteur qui contribue le plus à la fonction de coût, et en conséquence quels sont les changements de fréquences sur cet émetteur qui conduisent à un gain par diminution de la fonction de coût. * A titre d'exemple non limitatif, sur la figure 2b, on peut constater que la fréquence f0 = 0 est celle qui cctrib!e 1 'plu à 'la fnctitnr de coût pour ifmfetteur el. Le critère d'aspiration est considéré comme véri- fié à l'étape 1002 lorsqu'une valeur de fréquence allouée à cet émetteur e1 permet de diminuer la fonction de coût précitée. Dans ces conditions, il est possible de choisir une fréquence fk pour laquelle la valeur v(ek,fk) est infé- rieure, ce qui bien entendu permet de diminuer en consé- quence la fonction de coût. En référence à la figure 2b, pour une allocation courante telle que représentée sur cette figure et pour une fréquence f5 = 5 allouée à l'émetteur e1, pour laquelle la valeur de violation v(e1,f5) = 5, il est possible de choisir pour cet émetteur e1 la fréquence f6 = 6 pour laquelle la valeur v(e1,f6) = 1, la fonction de coût étant ainsi diminuée. Le choix optimal correspond à v(e1,f7) = 0. A l'étape 1003, le couple e1, f6 ou e1,f7 est alors choisi comme allocation au couple ek,fk de l'étape précitée. A chaque étape de la recherche, la matrice de violation est remise à jour en tenant compte de la modification de l'allocation courante. Cette opération peut être réalisée pour chaque émetteur, pourvu que ces émetteurs ne soient pas classés dans la liste des émetteurs tabous, ainsi que mentionné précédem- ment dans la description. On comprend ainsi que la condi- tion 1002 de critère d'aspiration vérifiée consiste en fait à appliquer localement à un émetteur considéré, l'un des émetteurs non tabous, la fonction de coût pour déter- miner le couple d'émetteur/fréquence considéré. Toutefois, selon un aspect particulièrement avan- tageux de ce dernier, on indique que celui-ci consiste également à mémoriser dans une liste auxiliaire l'ensemble des émetteurs ai, a1i çCours d'.ll..ombre dàterm d'itirn- tions précédentes, ont fait l'objet d'une modification de fréquence satisfaisante pour laquelle une mise à jour du plan de fréquences courant, de la valeur de la fonction de coût et du critère d'aspiration a été réalisée. On com- prend ainsi, grâce à l'exemple précédemment mentionné en liaison avec la figure 2b, que, pour l'émetteur e1, lors- que la fréquence f6 a été attribuée à ce dernier, celui-ci peut être introduit dans la liste auxiliaire des émetteurs tabous. Cette liste auxiliaire n'est pas nécessairement permanente, ainsi qu'il sera décrit ultérieurement dans la description. Lorsqu'aucune des conditions d'arrêt à l'étape 1001 n'a été satisfaite pour un nombre déterminé K d'ité- rations, il est alors possible de modifier la liste des émetteurs tabous par un retour par exemple à la liste ini- tiale d'émetteurs tabous à partir de la configuration du plan de fréquences courant pour lequel le processus d'al- location est poursuivi. Une description plus détaillée de la mise en ouvre d'une fonction de coût h(9p) particulièrement adaptée à la conduite du procédé d'allocation, objet de la présente in- vention, sera maintenant donnée en liaison avec la figure 2c. Selon un aspect particulièrement remarquable du procédé, objet de l'invention, pour toute contrainte de valeur cij entre un émetteur ei et un émetteur ej de l'en- semble d'émetteurs E, la fonction de coût h(p) vérifie la relation (2): h(9)= E'p(cu,)6 ci,ejEG cij*O Dans cette relation, on indique que: p(cij) désigne un coefficient de pondération défini a priori pour chaque valeur d'espacement en nombre de canaux de fréquences pour la contrainte cij dans le graphe des contraintes précité et ôij désigne la contribution, à la fonction de coût h(p), du couple émetteur/fréquence entre deux émet- teurs ei et ej auxquels ont été affectées les fré- quences fi et fj respectivement. Sur la figure 2c, on a représenté, d'une part, les valeurs des contraintes cij pour des valeurs arbitraires comprises entre 1 et 5, la valeur 5 représentant une con- trainte relative à des émetteurs très voisins. En outre, les valeurs de contribution du couple émetteur/fréquence 5ij entre deux émetteurs à la fonction de coût vérifient avantageusement les relations (3) ci- après: 3 j =0 si l(p(ei)-y(ej)l>c avec a =Cii - sp(ei)- p(ej) siei)-(ej) Dans les relations précédentes, ainsi que repré- senté en figure 2c, on indique que les coefficients de pondération p(cij) sont définis a priori, pour l'utilisa- tion du procédé objet de la présente invention, pour cha- que valeur possible d'espacement en canaux de fréquences présente dans le graphe des contraintes. La fonction de coût introduite permet ainsi de pondérer les violations de contraintes selon leur degré. Il est en effet plus pénalisant d'affecter la même fré- quence à deux émetteurs liés par une contrainte de degré élevé, par exemple degré 5 correspondant le cas échéant à des émetteurs sur le même site, que ceux liés par une con- trainte de degré faible, par exemple degré 1. Les coefficients de pondération p(cij) sont définis par l'utilisateur, pour un réseau de radiodiffusion ou de télédiffusion à replanifier. Pour des valeurs de contraintes croissantes de 1 à la contrainte m, et par rapport à un coefficient de pondé- ration p(cij) égal à une constante 1 en l'absence de pon- dération, le coefficient de pondération p(cij) choisi par l'utilisateur peut alors être constitué par une fonction monotone croissante de la valeur de la contrainte cij. A titre d'exemple non limitatif, pour des valeurs de con- traintes cij variant de 1 à 5 par valeurs discrètes, le coefficient de pondération peut être choisi en correspon- dance comme une progression du type 1-10-100-500 et 1000. L'introduction des coefficients de pondération permet en fait de privilégier la résolution des contraintes de degré 3, 4, 5 dans la solution. En référence à la figure la et pour un plan de fréquences courant donné et pour les émetteurs e5 et e2, pour des fréquences f5 et f2 allouées dans ce plan de fré- quences courant, la valeur Ifs-f21 = 1 entraîne un violation de la contrainte, laquelle est égale à 5. Dans ces conditions, 625=5-1=4. Avec l'indice de pondération introduit p(cij)=1000, la valeur pondérée de la contribution du couple émet- i3 teur/'fréquence considéré à la fonction de coût pour les émetteurs e2 et e5 8 pour valeur 4000, Si au contraire, pour un autre plan de fréquences courant Ifs-f21 = 4, alors, 625=5-4=1 et dans ce cas, la va- leur pondérée de la contribution du couple émet- teur/fréquence entre deux émetteurs à la fonction de coût est alors égale à 1000. Ce mode opératoire permet ainsi de pondérer et de graduer la violation des contraintes au cours des déplace- ments introduits lors de chaque itération pour l'établis- sement d'un plan de fréquences courant. Des indications seront maintenant données en ce qui concerne de manière plus particulière l'établissement des plans de fréquences spécifiques d'initialisation à l'étape 1000lb de la figure lb. Dans un premier mode de réalisation non limitatif, on indique que le plan de fréquences spécifique d'initia- lisation est un plan de fréquences aléatoire obtenu pour chaque émetteur ei considéré successivement par tirage aléatoire non exhaustif d'un canal de fréquences parmi l'ensemble C des canaux de fréquences. D'une manière générale, on indique que pour une bande de fréquences attribuée par l'autorité de gestion et de contrôle de l'allocation de fréquences, et en particu- lier pour un nombre discret déterminé de canaux de fré- quences susceptibles d'être utilisés, on comprend que le nombre de canaux de fréquences est le plus souvent infé- rieur au nombre d'émetteurs pour lequel une allocation doit être effectuée. Dans ces conditions, la notion de ti- rage aléatoire non exhaustif implique que lors du tirage aléatoire, la valeur d'une même fréquence puisse être bien entendu att ribuée & deux etteurs distincts pourvu que La contribution d'une telle allocation à la fonction de coût ne soit pas rédhibitoire. Dans un autre mode de réalisation non limitatif, on indique que le plan de fréquences spécifique d'initia- lisation est un plan de fréquences obtenu à partir d'un processus d'allocation de type glouton dans lequel, à cha- que émetteur affecté d'un index ordinal pris dans un ordre aléatoire, est affecté un canal de fréquences respectant le mieux possible les contraintes locales relatives à cet émetteur, en l'absence de remise en cause des choix de fréquences allouées aux émetteurs antérieurs. Les deux processus opératoires relatifs à l'ini- tialisation et à la définition du plan de fréquences spé- cifique d'initialisation permettent d'introduire de la diversité dans le choix du point de départ de cette ini- tialisation et, en conséquence, de mieux explorer l'espace de recherche si l'on effectue plusieurs optimisations suc- cessives sur le même jeu de données. En particulier, en référence à la figure lb, le choix du type de plan de fré- quences initial est paramétrable, type aléatoire AL ou type glouton GL, au choix de l'utilisateur, afin de donner toute latitude et initiative à ce dernier dans la conduite du processus d'allocation de fréquences. Une description plus détaillée du choix du dépla- cement de fréquence élémentaire correspondant sensiblement à la mise en oeuvre des étapes 1002, 1003, 1004, 1005 et 1006 de la figure lb, sera maintenant donnée en liaison avec les figures 3a et 3b. D'une manière générale, on indique que le choix du déplacement élémentaire dans l'espace de recherche S pré- aime est ett)4 D. caSidrt li vrile. 'me.t.eur. et les variables de fréquences susceptibles d'être al- louées à ces émetteurs comme indépendantes, le choix de l'émetteur à replanifier étant effectué selon un processus décrit en liaison avec la figure 3a et le choix de la fré- quence à allouer à cet émetteur choisi étant effectué se- lon le processus tel que décrit en référence à la figure 3b. D'une manière générale, on indique que, conformé- ment au procédé d'allocation de fréquences, objet de la présente invention, le critère de choix du déplacement élémentaire est adapté, lors du processus d'exploration de l'espace de recherche S, de manière à: - tenter de résoudre en premier lieu les viola- tions de contraintes sur les émetteurs contribuant forte- ment à la valeur courante de la fonction de coût; - introduire une certaine part de hasard dans ce choix afin de tirer parti des techniques d'algorithmes aléatoires qui permettent de minimiser la probabilité d'aboutir à un optimum local. En ce qui concerne la choix de l'émetteur à repla- nifier, ainsi que représenté en figure 3a, le procédé, ob- jet de la présente invention, consiste, à l'aide de la matrice des violations représentée en figure 2b, à effec- tuer une étape 1100 de tri des émetteurs ej en fonction des violations que leur fréquence fj engendre pour l'allo- cation courante considérée. Cette étape de tri peut être réalisée à l'aide de tout programme de tri permettant d'effectuer la discrimination des valeurs de violation précédemment décrites. L'étape 1100 est suivie d'une étape *5 1 iné. consistant en uzn A-ii Rué, -,Iv Sli 1 g- forme, de l'émetteur ek. A l'étape 1101, on dispose de l'émetteur ejM con- tribuant le plus à la fonction de coût h(p) précédemment mentionnée dans la description. Pour un nombre n donné d'émetteurs, ce nombre n étant égal à 3 lors de la pre- mière passe dans le cas purement illustratif de la figure la, cet émetteur est choisi avec une probabilité 1/p. Le paramètre p est choisi par l'utilisateur. L'étape 1101 précitée est alors suivie d'une étape 1102 consistant àchoisir un émetteur donné ek parmi ceux qui provoquent une violation des contraintes. Ce choix est effectué avec une probabilité 1-1/p. A la fin de l'étape 1102, on dispose d'un émetteur ek choisi auquel un dépla- cement de fréquence peut être appliqué. Le mode opératoire permettant de déterminer le choix d'une fréquence et, en définitive, du déplacement de fréquence à appliquer à l'émetteur choisi précédemment, peut être réalisé de manière avantageuse, ainsi que repré- senté en figure 3b. En référence à la figure 3b, on indique que, dans une étape 2001, les valeurs de canaux de fréquences ou de fréquences conduisant à un meilleur coût global pour l'émetteur ek considéré sont identifiées à l'aide de la matrice des violations telle que représentée en figure 2b et triés dans une liste selon le gain induit sur la fonc- tion de coût. A l'étape 2001, cette opération est désignée par identification et tri des fréquences selon la gain sur la fonction de coût h(q) permettant d'établir une liste des fréquences précitées désignée par Lf. Une étape classique de calcul du nombre de fré- quences Nf dans la Liste des fréquences Lf est ràalise a l'étape 2002 à partir d'un programme de calcul classique. Suite à l'étape 2002, une étape 2003 est effec- tuée, cette étape 2003 présentant un caractère particuliè- rement avantageux dans le cadre de la mise en oeuvre du procédé, objet de la présente invention. A l'étape 2003, on considère un objectif OB cons- titué par un paramètre introduit par l'autorité chargée de gérer l'allocation de fréquences. Ce paramètre d'objectif OB peut être par exemple un nombre de fréquences maximum à ne pas dépasser dans l'allocation de fréquences considé- rée. Le test 2003 représenté en figure 3b consiste à com- parer la valeur du nombre de fréquences Nf dans la liste de fréquences Lf à la valeur du paramètre OB. Si le nombre de fréquences utilisé pour le plan d'allocation courant est supérieur à l'objectif OB, seules les fréquences con- duisant à une meilleure réutilisation du spectre sont con- servées dans la liste précitée. Cette étape précédemment mentionnée est réalisée à l'étape 2004 sur la figure 3b o Max(Lf) désigne un sousensemble de la liste Lf conduisant à une meilleure réutilisation du spectre, ce sous-ensemble étant désigné par NLf permettant l'obtention d'une meilleure réutilisation du spectre de fréquences considé- ré. Si la nouvelle liste NLf ainsi constituée n'est pas vide, un test de vacuité d'une telle liste étant re- présenté en 2005 à la figure 3b par la relation NLf > 0, une nouvelle fréquence est attribuée à l'émetteur ek choi- si précédemment en relation avec la figure 3a. Le choix de cette fréquence est réalisé à l'étape 2006 représentée sur la figure 3b. A titre d'exemple non limitatif, on indique que le choix de cette fréquence peut être réalisé de la façon ci- après: - avec une probabilité 1/q, q étant fixé par l'utilisateur du procédé objet de l'invention, on choisit la fréquence de cette liste conduisant au plus grand gain Ah(q)max sur la fonction de coût h(p); - avec une probabilité 1-1/q, on effectue un ti- rage au sort selon une loi uniforme d'une fréquence dans la liste NLf considérée. Si au contraire aucune fréquence de la nouvelle liste NLf n'aboutit à une amélioration de la fonction de coût, alors, sur réponse négative à l'étape 2005, on re- cherche, en une étape 2007 pour chacun des émetteurs voi- sin de l'émetteur ek choisi précédemment, une meilleure fréquence selon le même procédé, l'étape 2007 étant rame- née à l'étape 2001 de la figure 3b. En ce qui concerne la détermination du choix et de l'attribution d'une nouvelle fréquence à l'étape 2006, ce choix est désigné par la relation: fM E NLf > Ah(q)max. Dans la relation précédente, fM désigne la valeur de fré- quence ou de canal de fréquences appartenant à la liste NLf pour laquelle le gain par diminution de la fonction de coût, Ah(ç) atteint sa valeur maximale Ah(q)max. Le mode opératoire du choix de la fréquence al- louée à l'étape 2006 permet en particulier d'éviter l'ap- parition systématique de maxima locaux dans l'allocation des fréquences précitée. En outre, le mode opératoire pré- cité permet de traiter localement les contraintes particu- lièrement difficiles à respecter. Enfin, dans un mode de réalisation non limitatif préférentiel, le critère d'aspiration peut consister, con- formément à un aspect particulièrement avantageux du pro- cédé, objet de la présente invention, à retenir le meilleur déplacement tabou si celui-ci offre un gain plus important que tous les déplacements non tabous effectués au cours de l'ensemble des déplacements élémentaires sur les émetteurs non tabous. En ce qui concerne le calcul du graphe des con- traintes, toute méthode préconisée par la recommandation UIT 370-R peut être utilisée. Le procédé, objet de la présente invention, met en oeuvre un processus capable de traiter le problème généri- que de l'allocation de canaux de fréquences pour des ré- seaux de radiodiffusion exploitant des plans de fréquence fixe. Des tests ont été réalisés en France par le titu- laire de la présente demande de brevet, à la fois sur des données de synthèse et sur des matrices de contraintes ob- tenues à partir des données réelles sur des émetteurs de radiodiffusion sur un nombre d'environ 5000 émetteurs. En particulier, le procédé, objet de la présente invention, présente une très grande souplesse d'utilisa- tion en raison du paramétrage possible du processus, ainsi que mentionné précédemment dans la description, ce paramé- trage autorisant la production de plans de fréquences aux caractéristiques différentes suivant le but recherché par l'utilisateur. Il est ainsi possible, grâce à la mise en oeuvre du procédé, objet de la présente invention, de pri- vilégier la résolution des contraintes au détriment du taux de réutilisation des fréquences ou de chercher à ré- soudre en priorité certains types de contraintes comme celles correspondant à des émetteurs placés sur le même site par exemple. Ainsi, les principaux paramètres ajustables par l'utilisateur lors de la mise en ouvre du procédé, objet de la présente invention, concernent respectivement les paramètres ci-après et leur fonction: PARAMETRE DESCRIPTION Bande de fréquences disponible Bande de spectre allouée au système AF ó> C exprimée en intervalle de canaux. Taux de violation des con- Permet de fixer a priori un objectif traintes souhaité dans la so- en terme de respect des contraintes au lution. processus d'optimisation. Ce paramètre T est exprimé en pourcentage du nombre de contraintes total dans le graphe. Plage de valeurs typique: 0 à 1%. Nombre de fréquences maximum à Permet de fixer a priori un objectif utiliser dans la solution en terme de nombre de fréquences uti- OB lisées dans le plan de fréquences dé- terminé par le procédé. Il est ainsi possible de forcer l'algorithme à un certain niveau de réutilisation spec- trale dans la solution produite. Type de plan de fréquences Ce paramètre permet de fixer la ma- initial nière dont sera choisi le point de dé- AL, GL part de l'optimisation dans l'espace de recherche. Pondération Permet d'adapter le procédé à diffé- P(cij) rents types de réseau à planifier. On a ainsi décrit un procédé d'allocation de fré- quences particulièrement performant dans la mesure o ce- lui-ci permet à l'autorité de gestion et de contrôle des fréquences dans un espace radioélectrique, de traiter des cas concrets d'allocation de fréquences selon des straté- * gies différentes grâce au paramétrage utilisé: - une première possibilité de paramétrage consis- tant à exploiter au maximum la bande de fréquences al- louées au système pour obtenir un taux de violation des contraintes minimal; - une deuxième possibilité consistant à effectuer une optimisation formant le processus d'allocation à n'utiliser qu'un nombre limité de canaux dans le plan de fréquences finalement retenu tout en ne dépassant pas un seuil donné de taux de violation des contraintes. L'entité utilisatrice du procédé, objet de la pré- sente invention, peut ainsi produire sur un même jeu de données des plans de fréquences aux caractéristiques très différentes afin de déterminer le meilleur compromis entre réutilisation du spectre de fréquences et respect des con- traintes d'espacement en fréquences. REVENDICATIONS 1. Procédé d'allocation de fréquences à un ensem- ble (E) d'émetteurs {eo,... eN-} formant un réseau d'émet- teurs par recherche tabou à partir d'un ensemble (C) de canaux de fréquences, l'ensemble (E) d'émetteurs et (C) de canaux de fréquences étant soumis, en fonction de la topo- graphie du réseau d'émetteurs {eo,... eN-1} et des canaux {c0,... cn-1} de fréquences alloués à chaque émetteur, à des critères de protection de zones de couverture selon un graphe de contraintes d'espacement de canaux de fréquences de la forme óci-cjl m o m est un entier positif supérieur ou égal à 1 représentatif du risque d'interférence co- canal et canaux adjacents respectivement, cet ensemble d'émetteurs étant subdivisé en un sous-ensemble d'émet- teurs Ef, pour lequel aucun changement de canal de fré- quences n'est réalisable et en un sous-ensemble d'émetteurs Em (el,..., eM) pour lequel un changement de ca- nal est réalisable à partir des canaux de fréquences dis- ponibles, caractérisé en ce que ledit procédé consiste, à partir d'une fonction de coût h(p) représentative du taux de satisfaction respectivement de non satisfaction de l'ensemble des contraintes d'espacement de canaux: - à initialiser cette allocation par un plan de fréquences spécifique, établi à partir de l'ensemble des canaux de fréquences disponibles pour ledit réseau d'émet- teurs, à chaque émetteur (el,..., eM) dudit sous-ensemble Em pour lequel un changement est réalisable étant alloué un canal (ci,..., cj) de cet ensemble de canaux disponibles, ledit plan de fréquences spécifique constituant un plan de fréquences courant; - à soumettre ladite allocation à une étape de test à la valeur vraie de conditions d'arrêt, la valeur vraie des conditions d'arrêt entraînant la fin du procédé d'allocation de fréquences, audit réseau d'émetteurs étant alloué le plan de fréquences courant; et sur réponse né- gative à ladite étape de test à la valeur vraie des condi- tions d'arrêt, - à soumettre ladite allocation à un test à la va- leur vraie d'un critère d'aspiration relatif audit taux de l'ensemble des contraintes d'espacement de canaux, pour un couple émetteur/fréquence correspondant à une contribution de non satisfaction de la fonction de coût, sur réponse positive audit test à la valeur vraie du critère d'aspira- tion à l'émetteur considéré (ek) étant alloué le canal de i5 fréquences (Ck) de ce coup-le eettteur/fr&qunce, et, sur réponse négative audit test à la valeur vraie du critère d'aspiration; - à choisir un émetteur courant appartenant à l'ensemble des émetteurs Em pour lequel un changement est réalisable et à déterminer l'ensemble des canaux de fré- quences disponibles pour cet émetteur courant non tabou; - à soumettre ledit ensemble des canaux de fré- quences disponibles pour cet émetteur courant non tabou à un test de vacuité, et, sur réponse négative audit test de vacuité, choisir dans ledit ensemble de canaux de fréquen- ces disponibles pour cet émetteur courant non tabou un ca- nal de fréquences déterminé, et, sur réponse positive audit test de vacuité; - pour chaque émetteur voisin dudit émetteur cou- rant * choisir une valeur de canal de fréquences parmi l'en- semble des canaux de fréquences permettant de diminuer la valeur courante de la fonction de coût; * affecter la valeur de canal de fréquencess choisie à cet émetteur voisin considéré; * mettre à jour la valeur de la fonction de coût et le critère d'aspiration relatif au taux de satisfaction respectivement de non satisfaction de l'ensemble des contraintes d'espacement de canaux, et, suite aux éta- pes de choix, d'affectation et de mise à jour relatives à chaque émetteur voisin dudit émetteur courant; - à mettre à jour le plan de fréquences courant, par affectation du canal de fréquences du couple émet- teur/fréquence à l'émetteur considéré, la valeur de la fonction de coût et le sous-ensemble d'émetteurs tabous, par insertion dans l'ensemble tabou dudit émetteur consi- déré auquel le canal de fréquences a été attribué; et - à soumettre le plan de fréquences courant mis à jour ainsi obtenu à un processus itératif par retour à l'étape de test à la valeur vraie des conditions d'arrêt. 2. Procédé selon la revendication 1, caractérisé en ce que lesdites conditions d'arrêt comprennent un cri- tère de test de comparaison d'infériorité, pour le plan de fréquences courant considéré, du taux de non satisfaction des contraintes, défini comme le rapport du nombre de con- traintes non respectées au nombre total de contraintes du graphe des contraintes, à une première valeur de seuil dé- terminée. 3. Procédé selon la revendication 1 ou 2, caracté- risé en ce que lesdites conditions d'arrêt comprennent un critère de test de comparaison de supériorité du nombre déterminé d'itérations dudit processus itératif à une deuxième valeur de seuil déterminée pour lesquelles aucune amélioration de la valeur de la fonction de coût n'est ob- tenue. 4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce que ledit test à la valeur vraie d'un critère d'aspiration relatif au taux de satisfaction res- pectivement de non satisfaction de l'ensemble des con- traintes d'espacement de canaux, pour un couple émetteur/fréquence correspondant à une contribution de non satisfaction de la fonction de coût, comprend un critère d'appréciation sur le gain, en diminution, obtenu sur cette fonction de coût. 5. Procédé selon l'une des revendications précé- dentes, caractérisé en ce que dans le but de constituer ledit ensemble d'émetteurs tabous, ce procédé consiste à mémoriser, dans une liste, l'ensemble des émetteurs qui, au cours d'un nombre déterminé d'itérations précédentes, ont fait l'objet d'une modification de fréquence satisfai- sante, pour laquelle une mise à jour du plan de fréquences courant, de la valeur de la fonction de coût et enfin d'itération, ont été réalisés. 6. Procédé selon l'une des revendications 1 à 5, caractérisé en ce que, pour toute contrainte de valeur cij entre un émetteur ei et un émetteur ej de l'ensemble d'émetteurs E, ladite fonction de coût h(p) vérifie la re- lation: h(q)= p(cij)=o relation dans laquelle: - relation dans laquelle: p(cij) désigne un coefficient de pondération défini a priori pour chaque valeur d'espacement en nombre de canaux de fréquences pour la contrainte cij dans le graphe des contraintes; ôij désigne la contribution à la fonction de coût h(p) du couple émetteur/fréquence entre deux émetteurs ei, ej. 7. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que ledit plan de fréquences spécifique d'initialisation est un plan de fréquences aléatoire obte- nu, pour chaque émetteur ei considéré successivement, par tirage aléatoire non exhaustif d'un canal de fréquences parmi l'ensemble (C) des canaux de fréquences. 8. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que ledit plan de fréquences spécifique d'initialisation est un plan de fréquences obtenu à partir d'un processus d'allocation de type glouton, à chaque émetteur, affecté d'un index ordinal, pris dans un ordre aléatoire, étant affecté un canal de fréquencess respec- tant les contraintes locales relatives à cet émetteur, en l'absence de remise en cause des choix de fréquences al- loués aux émetteurs antérieurs.