Planification de réseaux cellulaires Chapitre 6 I.Généralité II.Allocation de fréquences III.Placement des émetteurs IV.Méthodes globales

Planification de réseaux cellulaires

Chapitre 6

I. GénéralitéII. Allocation de fréquencesIII. Placement des émetteursIV. Méthodes globales

Stéphane Ubéda et Fabrice Valois ARM Chapitre 7

2

Planification

Réalisé par l’opérateurOptimisation en continueDonnées de bases Caractéristiques de l’environnement Caractéristiques de l'utilisateur Caractéristiques du systèmes

Objectif : minimiser le coût de l’infrastructure radio & réseau

Contraintes : QoS Qualité de l ’appel Taux de pertes Taux de blocage


3

Moyens

Modèles Trafic, propagation, mobilité

Logiciels Ingénierie cellulaire, allocation de

fréquencesValidation

Simulations, mesures, comportement du système


4

Schéma général de planification

Contraintesdu système

Prédiction decouverture etd’interférences Plan fréquences

Définition duréseau

Implantation du système

Ajustementdes paramètres

Densificationdu système


5

Estimation du trafic

Durée moyenne d’un appelTaux d’arrivée des appelsTaux de pénétrationVariations

Temporelles Géographiques


6

Un exemple

Zone de 1500 habitants 0,02 Erlang Croissance +50 %/an Taux de pénétration 5% (pouvoir d ’achat)

Visiteurs 2000 (heures de pointes) 0,1 Erlang Croissance +20 %/an Taux de pénétration 8 %

Une route principale 0,2 Erlang Maximum 300 véhicules simultanément Taux de pénétration 4 % Croissance 5 %


7

Prédiction sur 5 ansHabitants Visiteurs Voiture

Pénétration 0,05 0,08 0,04Erlang 0,02 0,1 0,2Année TOTAL

1 1,50 16,00 2,40 19,902 2,25 19,20 2,52 23,973 3,38 23,04 2,65 29,064 5,06 27,65 2,78 35,495 7,59 33,18 2,92 43,69

Si l ’on désire un taux de blocage en année 1 de 1%29 canaux minimum, donc 4x8 Trames TDMA

En année 5, avec nos 32 canaux, on a un taux de blocage de 51% !!!! Le système s ’écroule en année 3

(taux de blocage supérieure à 5%)


8

Formule de calcul Erlang

http://mmc.et.tudelft.nl/~frits/Erlang.htm


9

Critères d’optimisation

Couverture Argument commercial

Demande Génère réellement des revenus

Évolution Robustesse a l’augmentation du trafic

Impact sur le taux de blocage Souplesse de modification


10

Contraintes

Positionnement des émetteurs Légalités, accessibilité

Maintenance, approvisionnement en énergie, connexion au réseau fixe (au BSC pour GSM)

Rapport signal bruits Variables suivant les types de réseaux

Coûts de l’infrastructures Matériels, locations des sites, coût de

connexion au réseau fixe


11

Etat actuel

Outils existants Bases sur la couverture et sur les C/I Planet, Parcell, GRAND

Méthodes Reverses-ingineering

Changement avec l’UMTS Forward-ingineering Bases essentiellement sur la demande


12

Schema general

Déploiement des stations

Analyses de la propagation

Gestion des frequences

Analyses de la charge

Planification de réseau

Allocation de fréquences


14

Présentation du problème

Problématique générale Objectif : maximiser la réutilisation Contraintes : minimiser les interférences

Co-channel, Channel-adajcentOn parle du CIR = Carrier-to-Interference

ratio

Interférence provenant essentiellement des stations co-canal


15

Formule du CIR

dt

d4

d3

d2

d1

p1

p2

p3

p4

p

0Ndp

pdCIR

ii

t


16

Évolution du CIR

0Ndp

pdCIR

ii

t

Zones Ideal 3Rural 3.5Urbain 4Indoor 4.5

0

0.2

0.4

0.6

0.8

1

1.2

1 1.5 2 2.5 3

3

3.5

4

4.5


17

Influencer le CIR

Augmenter la distance entre cellules co-canal Technique de séparation

Augmenter la puissance d’émission sur le perturbe le lien radio Techniques de contrôle de puissances

min

0

CIRNdp

pdCIR

ii

t


18

Gestion des canauxFCA : fixed channel allocation

La région est divisée en cellules, chaque cellules recevant des canaux suivant un schéma de réutilisation

DCA : dynamic channel allocation Les canaux sont placés dans une file d ’attente

et attribués aux appels en fonction de la valeur des CIR

HCA : hybrid channel allocation Une partie fixe et une partie dynamique

Planification

Allocation de canauxMETHODES FIXES


20

Méthodes fixes

Une listes de canaux optimaux sont alloués a chaque cellule

Les allocations sont réalisées en respectant la distance de réutilisation

Le modèle le plus employé est le modèle hexagonal

Comment gérer le trafic non-uniforme !


21

Pavage hexagonal


22

Taille des cellulesZone à fort trafic

2 km x 2 km Trafic de 120 Erlangs Une station peut servir 20 Erlangs maximum Il faut 120/20=6 cellules Rayon des cellules

Zone à faible trafic 200 km x 200 km Trafic de 60 Erlangs Cellule de rayon max 30 km 15 cellules avec une capacité de 2 Erlangs

kmR 46,06

22


23

Clusterisation


24

Facteur de réutilisation

Facteur 1/NGéométrie hexagonale

6 cellules co-canal N=i2+ij+j2 1 2 3 4

1 3 7 13 212 7 12 19 283 13 19 27 374 21 28 37 48


25

Cellules co-canal


26

Motif à 12 cellules


27

Facteur de réutilisation co-canal

Modèle hexagonal Cellule de même taille

NR

DQ 3

6

)3()/(

0

nn N

i

RD

I

S


28

Motif et rapport S/I

Un système (AMPS) Pour la voix S/I supérieur à 18 dB

Taille de la cellule (atténuation 4)

49.6103

2

18)6

)3(log(10

8.1

2

N

N


29

Formule approximative

4444

4

4)()2/()2/()(2

DRDRDRDRD

R

I

S

Atténuation de 4 et N=7Première formule 73,5 18,6 dBDeuxième formule 49.56 16,9 dBValeur exacte 60,25 17.8 dB


30

Augmentation de la capacité

Sectorisation Utilisation d’antennes directives

Reuse partitionning Superposer deux schémas cellulaires

Division cellulaireMéthodes exotiques

Schéma de Stockholm


31

Sectorisation

Centre de cellule sectoriséeRegroupement de cellules


32

Tri-sectorielle ou 6-sectiorielle

120°60°


33

Sectorisation et S/I

3 secteurs 2 cellules6 secteurs 1 cellule


34

Combinaisons motifs/secteurs

12

37

45

128

6

911

10

12

37

45

128

6

911

10

12

37

45

128

6

911

10

12

37

45

128

6

911

10 Motif 4/12

Secteur iCanal i, 12i et 24i


35

Motifs combinés (reuse partitioning)

1 2

3 4 5

6 7

1 2

6 7

1

3 4

67

A B

C

C A

A B C

A B C A

A B CC


36

Division cellulaire


37

5

4

31

2

6

Motif de Stockholm

6

5

4

3

2

1

1

23

4

5

6


38

Trafic non-uniforme (I)

Allocationuniforme de 7 canaux

64.5

6

55

5.5 6.56.5

5

46

77

Nombrede Erlang


39

Trafic non-uniforme (II)

Allocationuniforme de 7 canaux

18.59

18.5

1212

15.2 21.721.7

12

6.218.5

24.824.8

Facteurde blocage


40

Trafic non-uniforme (III)

7.25.8

7.2

6.36.3

6.8 7.77.7

6.3

5.47.2

8.28.2

Facteur deblocagefixe 17%


41

Trafic non-uniforme (IV)

76

7

66

7 88

6

57

88

Facteur deblocagefixe 17%

Nombrede canaux :4-7=-3 !!!!


42

Répondre aux demandes

Emprunt de canaux De nombreuses variantes

Allocation non uniforme Statistiquement

Facteur de blocage réduit de 4%Trafic total écoulé augmente de 10-22%


43

Emprunt de canaux

Règle générale Une cellule utilisant l’ensemble de ces canaux

nominaux peut emprunter un canal à une cellule voisine

Une cellule peut prêter l’un de ces canaux non utilisés si cela n’entraîne pas d’interférences au niveau des appels en cours

Lors d ’un emprunt, un certain nombre de cellules doivent recevoir une interdiction d’utilisation de ce canal


44

Channel locking

Distancede réutilisation = 2

4


45

Emprunt de canaux

Emprunt plus performant que fixe en cas de réseau faible à moyennement chargé

Le fixe permet d ’écouler plus de trafic

Quel canal emprunter ? Les stratégies diffèrent...


46

Stratégies d’empruntsSBR : borrow from the richest

a la cellule qui à le plus de canaux libresBA : basic algorithm

de façon à maximiser le nombre de canaux libres dans la plus pauvre des cellules

BAR : basic algorithm with reassignment BA + handover intra-cellulaire dès que possible

BFA : borrow first available Les canaux sont ordonnés et les cellules effectuent

un scan jusqu ’au prochain libre (liste circulaire)


47

Stratégies hybrides

SHCB : Simple Hybrid Channel Borrowing Les canaux sont divisés en 2 ensembles

Empruntables et non empruntables

BCO : Borrowing with Channel Ordering On ordonne les canaux de chaque cellule

On affecte localement par le bas, on prête par le haut


48

Méthode statique pour lesdemandes non-uniformes

Basée sur le maillage hexagonal

Capable de prendre en compte des contraintes de séparations


49

Définitions des contraintes

Deux contraintes : Contrainte co-site K0 Contrainte inter-site K

Pour tout sommet v f1 et f2 affectées à v, |f2-f1|>K0

Pour tout sommets v1, v2 f1 affectée à v1 et f2 affectée à v2, |f2-f1|

>K


50

Borne inférieure

Cas K0=K=1 (coloriage classique)On ne peut faire mieux en nombre

de fréquences que le poids de la clique maximale :

W (G)= max {d(x)+d(y)+d(z)}(x,y,z) cliquede G


51

Résultat de la méthode

Si W(G) est la borne inférieure pour GOn définit quatre ensembles de

fréquences R, G, B et W (Red, Green, Blue, White) Chacun de taille W(G)/3

On attribuera les fréquences aux sommets du graphe qu’en utilisant les quatre ensembles définis


52

Coloriage RGB

W(G)=RGB

G


53

Graphe résultant

G1


54

Reduction à des arbres

R sans voisin B avec 2 ou 3 voisins emprunte aux B

G sans voisins R avec 2 ou 3 voisins emprunte aux R

B sans voisins G avec 2 ou 3 voisins emprunte aux G


55

Suppressing configurations

W(G)RGB


56

Graphe résultant

Collection d’arbres = bipartis


57

Fin de l’algorithme

Sur chaque arbre, on numéroteles sommets 0 ou 1 en alternantet en partant du centre

0 0

0

0

1

1

1

0 1dA dB

Fréquences WLes voisins piochent dans W

Par le haut ou le bas !

Allocation des canaux

METHODES DYNAMIQUES


59

Méthodes dynamiques

Définition Lorsque les canaux sont sans relations

avec les cellulesFamilles méthodes

Canaux utilisables dès que les conditions radio le permettent

Évaluation du coût de l’utilisation d ’un canal en fonction du contexte

Décision centralisée ou non


60

DCA centralisée (I)

FA : first avaible Le premier non utilisé dans la distance

de réutilisationLODA : Locally Omptimized Dynamic

Assignment Choix de celui qui minimise la

probabilité de blocage dans le voisinage de la cellule ou il va être employé


61

DCA centralisé (II)RING

Le canal utilisé est celui le plus utilisé dans les cellules co-canal

MSQ Le canal utilisé est celui qui minimise le moindre carré

des distances de toutes les cellules utilisant ce canalNN : Nearest neigbhbor

Le canal utilisé est celui employé dans la cellule la plus proche au delà de la distance de réutilisation

Variante NN+1, permet d’éviter un Handover assez fréquemment puisque la fréquence sera souvent libre dans le voisinage


62

DCA decentralisés

Les décisions se prennent localement avec une information locale uniquement

BTS 1 2 3 4 … M Nb CanauxI x 3

V1 x 2V2 x…Vk 0

Canaux

Recherche d ’une colonne vide ou de 3 colonnes consécutives

Permet de réaliser des Handoverintracellulaire pour diminuer les blocages


63

Systèmes avec mesures

Base sur la mesure du CIR Attention : très coûteux en temps Objectif : minimiser les mesures

Technique dite du Channel Segregation Le canal i est sélectionné en fonction

d ’une probabilité p(i)S ’il est libre p(i) augmente et on l’utiliseS ’il n ’est pas libre, p(i) diminue et on

cherche le suivant


64

Channel segregation

P(I)

0.000

0.200

0.400

0.600

0.800

1.000

1.200

1.00

03.

000

5.00

07.

000

9.00

0

11.00

0

13.00

0

15.00

0

P(I)

1)()(

1)(

1)()()(

iNiN

iN

iNiPiP

1)()(

1)(

)()()(

iNiN

iN

iNiPiP

IDLE

BUSY


65

Recherche des sitesSites théoriques

MNT Modèles de prédiction de couverture Dimensionnement théorique

Sites pratiques Visibilité réelle Morphologie des bâtiments, structures Alimentation électrique, problèmes juridiques Essais avec talkie-walkie


66

Heuristiques de recherche de sites

Méthode des quadtrees Découpage récursif « cell-spliting »

Points de concentrations Réduire le temps de calcul

Méthodes par sur-présentation On a dimensionné N sites On en prend 5-10 fois plus Recherche d’un sous ensemble


67


Systèmes à allocation fixe Calcul du nombre de canaux Calcul des contraintes du systèmes

Systèmes à allocation dynamiques Modélisation des contraintes physiques Allocation avec vérification « à la

demande »Systèmes hybrides

Stratégie d’emprunts


68

Matrice de réutilisationPour chaque cellule, on calcul le

C/Iij, pour chaque point de la cellule Histogramme

0

0,1

0,2

0,3

0,4

0,5

0,6

1 3 5 7 9 11 13

C/I

Les cellulesconsidéréescommeco-canal


69

Matrice de réutilisationAij = 0 95% du diagramme > 5

dBAij = 1 5% du diagramme < 5

dBAij = 2 5% du diagramme < 18

dB

Cellules C1 C2 Cij ... CN

C1

C2 ...

Cj Cij

... ...CN


70

Coloriage de graphe

Nombre chromatique du graphe GNP Complet


71


3

5

6

4

7

4

6

3 3

4

42

2

2

Demandes

Fréquencesminimales19 !!! 0

1

2

2

11

1

1

0

11

22

2

22

0

0

0

1 1

1

1

1

0

0

00

0

1

Contraintes inter-sites


72

Quelques heuristiques

Type « recuits simulés » On génère une affectation

aléatoirement On prend une configuration conflictuelle On chance localement l’affectation

Type génétique On génère N affectations On évalue chaque solution On combine les meilleurs


73

Algorithmes génétiques

De loin le plus courant chez les opérateursPopulations : P

Individus : P1,…,Pn

Pour 1 i n Pi solution aléatoire

Tant que fin non décidée

Pour 1 i < n/2, choisir deux individus Pa et Pb

croisement (Pa, Pb) suivant probabilité p

Pour 1 i n , mutation (Pi ) suivant probabilité p

P sélection(P)


74

Schéma génétique

1

4

7

6

83

2

9 10

5

Les sites sont numérotés de 1 à 10Les fréquences de 1 à 7

Chromosome :Site 1 2 3 4 5 6 7 8 9 10Fréquence 5 3 6 1 4 3 7 3 1 2


75

Croisement (Exemple)

Site 1 2 3 4 5 6 7 8 9 10Fréquence 5 3 6 1 4 3 7 3 1 2

Site 1 2 3 4 5 6 7 8 9 10Fréquence 2 1 5 7 4 5 2 4 4 1

1 0 1 1 0 0 1 0 1 1

Site 1 2 3 4 5 6 7 8 9 10Fréquence 2 3 5 7 4 3 2 3 4 1

Site 1 2 3 4 5 6 7 8 9 10Fréquence 5 1 6 1 4 5 7 4 1 2


76

Mutation (Exemple)

Site 1 2 3 4 5 6 7 8 9 10Fréquence 5 3 6 1 4 3 7 3 1 2

Choisir un gène au hasard

Site 1 2 3 4 5 6 7 8 9 10Fréquence 5 3 2 1 4 3 7 3 1 2

Remplacer par Random(7)


77

Sélection (Exemple)

On évalue le niveau d’interférence (maximum ou moyen)

On sélectionne parmi les 2N individus les N qui obtiennent les meilleurs scores !


78

Optimisation du réseau fixe

A partir de la position des cellules Détermination de la matrice de trafic Choix du nombre de contrôleur de

stationsMinimiser le Handover inter-BSC

Choix du nombre de commutateursOptimisation des zones de localisation


79

Densification du réseau

Adjonction de canaux En GSM, ajouter du hardware (TRX) Modification du motif cellulaire Emprunt de canaux Replanification avec contraintes

Cell-splitingSectorisationDown-tiling

Planification

Sélection des sites


81

Les différentes techniques

Définition du DNC = Demand Node Concept Un point xi dans le plan qui correspond au

centre d’une concentration de demande ai

Maximum Covering Location ProblemMethode par surdimensionnement

On explore la combinatoire des solutions à partir d’une solution contenant une représentation des sites


82

Methode MCLP

Concentrationde demande

Site potentiel(éventuellementplusieurs configurationspossibles)

Pour chaque site, évaluation de la zone de couverture(seuillage sur le niveau de reception)


83

MCLP : PL en 0/1

}max{ ii yaY

iNj

j yxIii

,

px j

0 : noeud i non couvert 1 : noeud i couvert

Valeur du noeud i

0 : site i non selectionne1 : site i selectionne

Ni est l’ensembledes sites couvrant i

Nombre maxde sites


84

MLCP : heuristique

BeginS = ensemble des configurations/sites

possiblesC=vide /* ensemble retenu */D=ensemble des points de demandesTantque cardinal(C)<=p faireChercher dans S l’element x

qui maximise couverture(c+x,d)C=C U xS=S-{Sx} /* Sx configurations

du site correspondant a x*/End


85

Méthode par sur-représentation

Utilisé dans l’outil STORMSBasé sur la notion de recouvrementObjectif : lever le problème du

multicritère Un bon réseau

Minimise les interférences : peu de BTSMaximise la couverture : beaucoup de BTS

CONTRADICTOIRE !


86

Zone d’interférences

Modélisation par sur représentation

Graphes d’interdictions définis par des intersection d’ensemble

Graphe de recouvrementGraphe d’interférence

Zone de service


87

Problèmes de ce modèle

Nombreux artefacts : Non symétrique :

A brouille B, mais B ne brouille pas A

Reliefs amplificateursLac (surfaces réfléchissantes), rivières

(guide d ’ondes), collines etc...• Une station qui brouille presque toutes etc...

Ces artefacts doivent recevoir un traitement particulier


88

Sur-représentation initiale

• Calcul des ZoC pour toutes les BTS• Construction d’un graphe de recouvrement


89

Construction d’un graphe de recouvrement

Définition d’un seuil maximal de recouvrement

A

B

C

A

B

C

17%

46% 23%

))(),((

)(

BSASMin

ISR


90

Objectif

Si le R entre les cellules A et B est supérieur au seuil : Les deux BTS se recouvrent trop pour

appartenir à la même solutionObjectif :

Choisir un sous ensemble de BTS qui ne viole pas la contrainte et qui maximise la couverture


91

Le graphe

Une arête entre A et B si le seuil est dépassé.Trouver le Stable de poids maximal....


92

Heuristiques

1. Sélectionner un sommet v du graphe G

2. On ajoute v à la solution

3. On retire du graphe G le sommet v et N(v)

4. S’il reste des sommets dans G recommencer à 1.


93

Sélection du sommet

Méthode Rand Min Dem DemMinNb BTS 27 35 31 34couverture 49 69 62 69demande 45 64 65 66

Méthode Rand Min Dem DemMinNb BTS 42 45 39 44couverture 78 83 81 81demande 73 80 80 83

Pourcentage de recouvrement autorisé : 40%

Pourcentage de recouvrement autorisé : 20%


94

Nuées dynamiques (I)


95

Nuées dynamiques (II)


96

Planification : conclusion

Planification initiale (1990) Entièrement manuelle

Planification moderne (1995) Quelques outils d’aides, en Europe Planet Outil de France Télécom : Parcell / Atoll

Futur de la planification Outils à inventer

Investigation du IndoorAdaptation à l’UMTS (services / fréquences)

Documents

Planification de réseaux cellulaires Chapitre 6 I.Généralité II.Allocation de fréquences III.Placement des émetteurs IV.Méthodes globales