UNIVERSIDAD SIMÓN BOLÍVAR Decanato de Estudios Profesionales Coordinación de Electrónica y Circuitos

LOCALIZACIÓN ÓPTIMA DE ANTENAS PARA COMUNICACIONES MÓVILES USANDO ALGORITMOS GENÉTICOS.

Realizador por: María José Peroza Marval

Sartenejas, julio 2005.

UNIVERSIDAD SIMÓN BOLÍVAR Decanato de Estudios Profesionales Coordinación de Electrónica y Circuitos

LOCALIZACIÓN ÓPTIMA DE ANTENAS PARA COMUNICACIONES MÓVILES USANDO ALGORITMOS GENÉTICOS

Por María José Peroza Marval Realizado con la Asesoría de Prof. Juan F. Gómez

PROYECTO DE GRADO Presentado ante la Ilustre Universidad Simón Bolívar como requisito parcial para optar al título de Ingeniero Electrónico Sartenejas, julio 2005

LOCALIZACIÓN ÓPTIMA DE ANTENAS PARA COMUNICACIONES MÓVILES USANDO ALGORITMOS GENÉTICOS POR: María José Peroza Marval Tutor Académico: Juan F. Gómez

RESUMEN

El presente trabajo plantea una metodología para ubicar las estaciones base de las empresas de telefonía móvil de manera de alcanzar un diseño optimizado de la red, es decir, calidad de servicio (cobertura total, mínima interferencia y capacidad para el manejo de tráfico) con mínimo costo de inversión. La metodología planteada consiste en diseñar un software basado en dos niveles: uno de optimización, que permita el diseño de una red que cumpla con ciertos requerimientos técnicos minimizando los costos de inversión, y un nivel de simulación que permita estimar la propagación de las distintas señales que operan en dicha red. El nivel de optimización consiste en la implementación de algoritmos genéticos, los cuales minimizan una función basada en cobertura, capacidad, interferencia y costo.

La metodología propuesta es utilizada para el diseño de dos redes celulares GSM, una para Singapur, la cual es comparada con un trabajo anterior, y otra para el área comercial de Caracas. En ambos casos se obtuvieron resultados satisfactorios, lo cual indica que el problema de la ubicación de estaciones base para telefonía celular puede ser planteado como un problema de optimización, y que además los algoritmos genéticos constituyen una poderosa arma para su tratamiento.

A Dios, por todo lo que él representa... A mis padres, a mi hermana y a mi novio por ser tan importantes en mi vida... Y a mi misma.

AGRADECIMIENTOS A Dios, por darme la fortaleza para superar los obstáculos, la confianza en mí, y sobre todo la fé para creer que los sueños se hacen realidad. A mis padres, Gladys y Rafael, por ser mi estímulo y mi ejemplo a seguir, mis pilares y mis maestros, y sobretodo mis amigos y grandes amores. Gracias por permitirme siempre buscar mis sueños. A mi hermana, Gladyra, por siempre recordarme que nunca se está sólo a pesar de estar lejos de la familia; por ser mi hermana y compañera; gracias sencillamente por existir y estar siempre a mi lado. A mi novio, Fernando, por su amor y comprensión, con su paciencia para conmigo, por se mi apoyo cada día, mi entusiasmo y mi compañía. Gracias Fernando por tu ayuda, tus palabras de aliento, tu fé en mí y por estar siempre dispuesto a ayudarme y acompañarme en todo. A mi amigo Cristo, por compartir conmigo tantas tardes en el 210 del LabC, por escucharme cuando necesité desahogo y por siempre tenderme su mano amiga, mil gracias. ¡Ah! Gracias por el lector SRTM. Al prof. Juan Francisco Gómez por haberme ofrecido este proyecto, no se imagina cuánto aprendí. Gracias por su fé en mí, y por darme la confianza y las herramientas para finalizar este trabajo de forma exitosa. Al prof. Diógenes Marcano, quien al principio nos acompañó en este proyecto, y muchas de sus ideas y conocimientos están aquí plasmados. Al prof. Villegas por su disponibilidad y por facilitarme todo lo que necesité en el LabC.

ÍNDICE GENERAL CAPÍTULO I :INTRODUCCIÓN

1

1.1. MarcoTeórico

2

1.1.1 Sistemas de telefonía móvil. Caracterización 1.1.1.1 Parámetros que definen la red de telefonía celular

2 3

1.1.1.1.1 Capacidad

4

1.1.1.1.2 Celda

6

1.1.1.1.3 Reuso de Frecuencias

8

1.1.1.2 Configuración del sistema de radiocomunicaciones móviles

10

1.1.1.2.1 Unidad móvil

11

1.1.1.2.2 Radiobase o Estación Base (EB)

11

1.1.1.2.3 Central de Telefonía Celular o MSC

11

1.1.1.2.4 Red de Telefonía Pública Conmutada

12

1.1.1.3 Calidad de Servicio

12

1.1.1.4 Hand off o Hand over

12

1.1.1.5 Interferencia

13

1.1.1.6 Proceso de Planificación de una Red Celular

13

1.1.2 Método para el cálculo de cobertura 1.1.2.1 Método de Okumura-Hata

14 14

1.1.3 Global System for Mobile Communications (GSM)

17

1.1.4 Algoritmos Genéticos (AGs)

19

1.1.4.1.1 Genes y Cromosomas

19

1.1.4.1.2 Poblaciones y Generaciones

19

1.1.4.1.3 Padres

20

1.1.4.1.4 Hijos

20

1.1.4.1.5 Mutación

20

1.1.4.1.6 Fitness o función de adaptabilidad

20

1.1.5 MATLAB

21

1.2 Antecedentes

22

CAPÍTULO II: OBJETIVOS

24

2.1 Objetivo General

24

i

2.2 Objetivos específicos

24

CAPÍTULO III: PLANTEAMIENTO DEL PROBLEMA

25

3.1 Método para el cálculo de cobertura

25

3.2 Función Objetivo

27

3.3 Modelo Matemático

27

CAPÍTULO IV: METODOLOGÍA PROPUESTA

36

4.1 Extensión

37

4.2 Dimensionamiento de la red

39

4.3 Programa de Simulación

41

4.3.1 Cobertura

43

4.3.2 Capacidad

47

4.3.3 Interferencia

48

4.3.4 Costo

49 50

4.4 Algoritmos Genéticos (AGs) 4.4.1 Población Inicial

50

4.4.2 Generaciones

51

4.4.2.1 Selección

51

4.4.2.2 Cruce

51

4.4.2.3 Mutación

52

CAPÍTULO V: RESULTADOS

53

5.1 Caso de prueba 1

53

5.2 Caso de Prueba 2

58

CAPÍTULO VI: CONCLUSIONES Y RECOMENDACIONES

64

6.1 Conclusiones

64

6.2 Recomendaciones

65

REFERENCIAS BIBLIOGRÁFICAS

66

ii

INDICE DE TABLAS Y FIGURAS Figura 1.1 Celdas formadas por antenas isotrópicas

7

Figura 1.2 Celdas de geometría hexagonal

7

Figura 1.3 La relación D/R

9

Figura 1.4 Patrón de Reuso de N celdas

10

Figura 1.5 Método para calcular la altura efectiva de la antena de una estación base

15

Tabla 3.1 Métodos de Cálculo de Cobertura y sus características

26

Tabla 3.2 Configuración y capacidad de las EBs

35

Figura 4.1 Datos para obtener la matriz Terreno

37

Figura 4.2 Ejemplo de Terreno

38

Figura 4.3 Matriz Terreno dividida en Cuadrículas

39

Figura 4.4 Matriz Terreno con cuadrículas numeradas

41

Figura 4.5 Matriz Terreno con tipos de estaciones base en cada cuadrícula

42

Figura 4.6 Ubicación de las EBs dada por los vectores Cromosoma y Ubicación

43

Figura 4.7 Matriz Cobertura

44

Figura 4.8 Matriz Pr(2)

45

Figure 4.9 Matriz Cobertura modificada

45

Figura 4.10 Matriz de Pertenencia

46

Figura 4.11 Matriz de Pertenencia modificada

46

Figura 5.1 Mapa de Singapur

53

Figura 5.2 Características Topográficas de Singapur

54

Figura 5.3 Máximo de la función de adaptabilidad y función de adaptabilidad promedio

55

Figura 5.4 Función Objetivo y función objetivo promedio. Caso1

56

Figura 5.5 Ubicación de las EBs del mejor individuo para Singapur

56

Tabla 5.1. Ubicación exacta de las EBs del mejor individuo

57

Figura 5.6 División del área de Singapur en celdas, de acuerdo con la solución obtenida

57

Tabla 5.2 Resultados de cobertura, capacidad e interferencia arrojados por la solución

58

iii

Figura 5.7. Características Topográficas de la zona comercial de Caracas

59

Figura 5.8 Máximo de la función de adaptabilidad y función de adaptabilidad promedio. 60 Caso2 Figura 5.9 Función Objetivo y función objetivo promedio. Caso2.

61

Figura 5.10 Mejor individu para el área comercial de Caracas. Ubicación de las EBs del 61 mejor individuo. Tabla 5.3. Ubicación exacta de las EBs del mejor individuo para el área comercial de 62 Caracas Figura 5.9.División en celdas del área comercial de Caracas, de acuerdo con la solución 62 obtenida. Tabla 5.4 Resultados de cobertura, capacidad e interferencia arrojados por la solución 63 obtenida para el área comercial de Caracas.

iv

LISTA DE ABREVIACIONES AGs.

Algoritmos Genéticos.

EB.

Estación Base.

FCC.

Comisión Federal de Comunicaciones (Federal Communication Comisión).

FDMA.

Acceso múltiple por división de frecuencia (Frequency Division Multiple Access).

GOS.

Grado de Servicio (Grade of Service).

GSM.

Sistema Global para Comunicaciones Móbiles (Global System for Mobile Communications).

MSC.

Central de Servicios Móbiles (Mobile Service Center).

MTSO.

Oficina de servicio de Telefonía Móvil (Mobile Telephone Service Office).

MTX.

Central de Telefonía Celular(Mobile Telephone Exchange).

PCS.

Sistema de Comunicación Personal (Personal Communication System).

PSTN.

Red de Telefonía Pública (Public Switching Telephone Network).

RTPC.

Red de Telefonía Pública Conmutada.

TDMA.

Acceso múltiple por división de tiempo (Time Division Multiple Access).

v

1 CAPÍTULO I INTRODUCCIÓN La situación actual en el mercado de las comunicaciones móviles se caracteriza por un impresionante aumento en la demanda. Este contexto obliga a las empresas de telefonía celular a crear o disponer de herramientas que permitan alcanzar un diseño optimizado de su red. Ante una mayor demanda por parte de los usuarios, las redes móviles crecen en dimensión y complejidad; los planificadores de redes celulares se enfrentan a una tarea cada vez más complicada esperándose de ellos mejores resultados, y se hace más evidente la necesidad de disponer de un software que facilite la planificación y optimización del diseño de redes celulares. Para hacerle frente a esta inquietud, esta investigación busca plantear una metodología que permita mejorar el proceso de planificación de redes celulares mediante la implementación de un software basado en dos niveles: uno de optimización, que permita el diseño de una red que cumpla con ciertos requerimientos técnicos minimizando los costos de inversión, y un nivel de simulación que permita estimar la propagación de las distintas señales que operan en dicha red. Con el fin de lograr un buen diseño de red, el software determina la mejor ubicación de las estaciones base tomando en cuenta diversos factores como: cobertura, capacidad de tráfico, costo, topología del terreno e interferencia. La optimización se lleva a cabo mediante la implementación de Algoritmos Genéticos, los cuales encuentran los valores mínimos de una función objetivo basada en costo, cobertura, tráfico e interferencia. El presente informe consta de 6 capítulos que explican detalladamente los objetivos, pasos, modelo matemático, etc. obtenidos o alcanzados con el desarrollo de este trabajo; haciendo un recorrido por el libro, encontramos, más adelante, en este mismo capítulo, una breve descripción teórica de los principales temas aquí tratados (sistemas de comunicación celular, algoritmos genéticos, etc.), además del desarrollo de dos trabajos previos, los cuales

2 sirvieron de base para esta investigación; el capítulo 2 enumera los objetivos alcanzados con el desarrollo de este proyecto. En el capítulo 3 se desarrolla un modelo matemático que describe y/o representa elementos como la cobertura, la interferencia, el tráfico telefónico y el costo, los cuales son utilizados para optimizar sistemas de redes celulares. El capítulo 4, metodología propuesta, engloba todo lo relacionado con los procedimientos seguidos para la elaboración del programa de optimización. En el capítulo 5 encontraremos lo resultados obtenidos a partir de dos casos de prueba realizados, y por último, en el capítulo 6 se exponen las conclusiones alcanzadas con el desarrollo de este trabajo.

1.1 Marco Teórico 1.1.1 Sistemas de telefonía móvil. Caracterización La radio celular ha aparecido debido a que era necesario proveer un servicio de telefonía móvil con una cobertura nacional e internacional; entendiéndose por cobertura la zona desde la cual un terminal móvil puede comunicarse con las estaciones bases y viceversa. El concepto celular consta de la distribución de transmisores de baja potencia que cubren un área limitada llamada celda. Dichas celdas son cada una de las unidades básicas de cobertura en que se divide un sistema celular. Cada celda contiene un transmisor y un número de canales de radiofrecuencia asignado. La red se encuentra diseñada para que los tamaños de las celdas sean relativos al número de usuarios; por lo tanto, mientras mayor sea el número de usuarios las celdas son más pequeñas y hay un mayor número de ellas para cubrir el área, como sería en las zonas urbanas; en las zonas rurales, sin embargo, las celdas son de mayor área y el número de ellas es menor. El conjunto de celdas que agrupan la totalidad de las frecuencias disponibles por la red celular, forman un clúster o “racimo” y éste se repite hasta alcanzar la cobertura final del sistema celular; de esta manera se demuestra que los sistemas celulares están diseñados bajo el concepto de utilización eficiente del espectro.

3

1.1.1.1 Parámetros que definen la red de telefonía celular. Según la Comisión Federal de Comunicaciones (FCC) hay tres parámetros básicos que definen el sistema de telefonía celular: •

Capacidad.

•

Célula (celda).

•

Reuso de frecuencia. A partir de esto y contando con que los sistemas de telefonía celular son redes

conmutadas que permiten la transmisión de voz y datos en forma confiable a través del espacio aéreo, al diseñar el sistema celular se debe cumplir con los siguientes objetivos:

•

Alta capacidad de servicios: Capacidad para dar servicio de tráfico a varios miles de usuarios dentro de una zona determinada y con un espectro asignado (Algunos cientos de canales de voz).

•

Uso eficiente del espectro: Uso eficiente de un recurso muy limitado como es el espectro de radio asignado al uso público.

•

Adaptabilidad a la densidad de tráfico: La densidad de tráfico varía en los distintos puntos de un área de servicio, el sistema se tiene que adaptar a estas variaciones.

•

Compatibilidad: Seguir un estándar, de forma tal de proveer el mismo servicio básico, con las mismas normas de operación a lo largo de todo el país.

•

Facilidad de extensión: Se trata que un usuario pueda cambiar de área de servicio pasando a una distinta y tener la posibilidad de comunicarse. Roaming.

•

Servicio a vehículos y portátiles.

•

Calidad de servicio: Implica seguir niveles estándares de bloqueo y calidad de voz.

•

Accesible al usuario: Es decir que el costo del servicio pueda ser pagado por un gran número de personas.

4 1.1.1.1.1 Capacidad. La capacidad de una red viene dada por la cantidad de tráfico que dicha red puede soportar, siendo el tráfico telefónico, la fracción de una hora durante la cual cierto circuito o grupo de circuitos estuvieron ocupados. El diseño de una red celular debe estar pensado para soportar el tráfico requerido por los usuarios en cualquier momento y al menor costo, pues en la práctica se ha comprobado que la probabilidad de que haya un número grande de llamadas simultáneas es muy pequeña, y por esta razón no resulta económico proveer equipos para un número grande de llamadas, debido a que una gran parte de los equipos permanecería ociosa la mayor parte del tiempo. La capacidad por cada bloque de canales distribuidos en una celda se calcula mediante la aplicación de la fórmula Erlang, como un sistema de llamadas perdidas (sin colas). Un circuito cursa un tráfico de un Erlang cuando se mantiene continuamente ocupado durante una hora. Un grupo de circuitos cursa un Erlang si la suma de los tiempos de ocupación de cada uno durante una hora es precisamente una hora. Cuando todo el equipo que provee facilidades para llamadas simultáneas está ocupado, un nuevo subscriptor no puede efectuar una llamada, se produce una condición llamada congestión, y la llamada se pierde. La capacidad es función del número de canales utilizado o ancho de banda disponible, del tamaño de las celdas y de la configuración en “clusters”. La capacidad será mayor cuanto mayor ancho de banda se disponga, cuanto menor sea el tamaño de la celda y cuantas menos celdas sean necesarias por “cluster”. Este último parámetro estará fuertemente ligado a la relación de interferencia cocanal que el sistema sea capaz de soportar. El diseño de la capacidad de los sistemas se realiza por zonas, tomando cada estación base independientemente, y suponiendo el caso de tráfico más desfavorable; es decir, el tráfico en la hora pico.

5 Para conocer la capacidad requerida por los usuarios se debe conocer el tráfico telefónico, el cual se puede expresar como el producto del número de usuarios por el uso promedio de llamada de cada usuario, por el porcentaje de intentos de llamadas en la hora pico [6].

Traf ( Erl ) = (nº usuarios )(uso promedio)(%llamada)

El uso promedio de la llamada por usuario está representado por el

(1.1)

número de

llamadas durante una hora que realiza un usuario en particular, por la duración promedio de las llamadas expresada como fracción de la hora; así para conocer el uso promedio de la llamada por usuario aplicamos la siguiente fórmula [8]:

uso promedio =

( nº llamadas / hora)( duración / llamada) s 3600s

(1.2)

Las especificaciones GSM establecen que el uso promedio por usuario varía aproximadamente entre 12 y 20 mE [8]. Es importante mencionar, que a medida que la red va creciendo los valores del uso promedio de la llamada, en base al análisis de las estadísticas, tienden en promedio hasta los 12mE por usuario. Existe un parámetro que aunque no se explica teóricamente en una bibliografía como tal, debe ser considerado a la hora de planificar una red móvil, ya que representa un factor de sobredimensionamiento; dicho parámetro es conocido como factor de movilidad de los usuarios [8]. A causa de que los suscriptores se van desplazando por toda la red, se hace necesario considerar aquellos casos en los cuales un gran número de ellos se concentra en un determinado sitio, por ejemplo cuando ocurren eventos especiales como conciertos o en las horas pico donde un gran número de usuarios confluye en una autopista; en esos casos puede ocurrir que la capacidad de las estaciones base no sea suficiente, lo cual puede traer como consecuencia que un alto porcentaje de las llamadas se encuentren bloqueadas. En tal sentido, se estima que para planificar una red joven el factor de movilidad está alrededor del 50%, debido a que un área geográfica es cubierta por el número mínimo de estaciones necesarias, por lo que una concentración inusual de usuarios debe ser atendida por una sola estación base.

6 En cambio a medida que la red va creciendo este factor puede ser menor, aproximadamente hasta el 20%, debido a que se tiene un mayor número de radio bases y la red está más apta para operar en tales concentraciones inusuales de usuarios. El factor de movilidad (fmov) es utilizado en la práctica según la siguiente fórmula [8]:

Traf ( Erl ) =

(n º usuarios)(uso promedio)(%llamadas) (1 − fmov )

(1.3)

1.1.1.1.2 Celda En los sistemas celulares, el área de cobertura de un operador es dividida en celdas. Una celda corresponde a una zona cubierta por un transmisor de baja potencia o una pequeña colección de los mismos; así, en lugar de cubrir un área desde un único sitio de transmisión con alta potencia y alta elevación, el proveedor de servicios puede subdividir el área en subáreas, zonas, células o celdas en donde cada una posea un transmisor de menor potencia. El tamaño de la celda depende de la potencia del transmisor, banda de frecuencia utilizada, altura y posición de la torre de la antena, el tipo de antena, la topografía del área y la sensibilidad del radio receptor. La celda es el área en el cual un sitio de transmisión particular es el más probable de servir las llamadas telefónicas móviles, utilizando cualquiera de los canales de RF específicos preferentemente y no exclusivamente. En principio, el área de cobertura de los sitios de transmisión no necesita ser regular, y las células no necesitan tener una forma geométrica definida; sin embargo, con el fin de trabajar apropiadamente, el nivel de potencia del transmisor dentro de una celda debe estar limitado, para así reducir la interferencia entre transmisores de celdas vecinas. El principal propósito de definir células es delinear zonas en las cuales cada canal es usado. Es necesario un grado de confinación geográfica del canal para evitar la interferencia co-canal.

7

Las zonas amorfas podrían ser aceptables para sistemas que no se modifiquen. En la práctica, es necesaria una estructura geométrica que facilite la adaptación al crecimiento del tráfico. Si una celda está cubierta por una antena isotrópica (que es la antena hipotética que irradia con igual intensidad en todas direcciones) ubicada en el centro, se puede pensar la célula como de forma circular. A este tipo de células se les conoce como células omnidireccionales. En este caso, existe solapamiento o bien zonas sin cobertura, tal como se muestra en la figura 1.1.

Figura 1.1 Celdas formadas por antenas isotrópicas

Un sistema podría estar diseñado con células en forma de cuadrados o triángulos equiláteros pero, por razones de dibujo y relaciones geométricas los diseñadores de sistemas de los Laboratorios Bell adoptaron la forma de hexágono como la forma teórica de las celdas. En este caso, en una matriz de celdas no existe solapamiento ni espacios vacíos, tal como se muestra en la figura 1.2.

Figura 1.2 Celdas de geometría hexagonal

8

1.1.1.1.3 Reuso de Frecuencias

La comunicación celular es un sistema de acceso múltiple en el que varios canales no interferentes entre sí, son combinados para formar grupos de canales y estos son asignados a radiobases. Debido a que el número de canales es limitado, estos grupos de canales son reutilizados a ciertas distancias regulares. Esta es una tarea importante de la ingeniería porque determina la capacidad del sistema y su operatividad. El reuso de frecuencia es el principal concepto de los sistemas móviles, permite que usuarios localizados en diferentes zonas geográficas puedan usar, simultáneamente, un canal con la misma frecuencia. El sistema de reuso de frecuencia puede incrementar drásticamente la eficiencia del espectro; no obstante, si no se diseña apropiadamente la red, se puede incurrir en serios problemas de interferencia. La interferencia producto del uso del mismo canal es llamada interferencia cocanal y es el principal elemento tomado en cuenta en el diseño de los sistemas de reuso de frecuencia. Existen varias técnicas de reutilización de frecuencias y son generalmente conocidas como técnicas de “Planeación de frecuencias” o “Asignación de canales”. Algunas de las técnicas de planeación de frecuencia más utilizadas a nivel mundial son las siguientes: Plan de reutilización de frecuencia N=7. Plan de reutilización de frecuencia N=9. Plan de reutilización de frecuencia N=4. Plan de reutilización de frecuencia N=3. donde N representa el número de celdas que forman un cluster, es decir, que utilizan la totalidad del espectro radioeléctrico disponible.

9

Un canal de radio consiste en un par de frecuencias, una en cada dirección de transmisión, que son usadas para una operación full-duplex. Un canal de radio en particular, F1, es usado en una zona geográfica llamada celda, C1, con un radio de cobertura R. Este mismo canal puede ser usado en otra celda con el mismo radio de cobertura a una distancia D de separación (ver Fig. 1.3).

Figura 1.3 La relación D/R

Debido a que la misma frecuencia es usada en dos celdas diferentes al mismo tiempo, un filtro no puede aislar la interferencia co-canal. Sólo una separación geográfica puede reducir dicha interferencia. Se define factor de reducción de interferencia cocanal o tasa de reuso cocanal q como:

q =

D R

(1.4)

Esta tasa tiene impacto en dos puntos importantes del sistema: la calidad de transmisión y la cantidad de usuarios que pueden ser atendidos por el sistema (capacidad del sistema). Cuanto más grande es la relación D/R menor será la interferencia co-canal, por ende habrá mejor calidad de transmisión. Cuanto más pequeña sea la relación D/R más grande será la capacidad del sistema, ya que la cantidad de canales asignados a una celda será mayor. La mínima distancia que permite reusar la misma frecuencia depende de muchos factores, tales como el número de celdas co-canales en la vecindad de la celda central, la característica geográfica del terreno circundante, la altura de la antena, y la potencia transmitida en cada celda.

10

La distancia D de reuso de frecuencia puede ser determinada mediante [7]

D = 3N R

(1.5)

donde N especifica el patrón de reuso y R es el radio de las celdas (ver fig. 1.4).

N=4 N=7 q=D/R=4.6 Figura 1.4 Patrón de Reuso de N celdas

1.1.1.2 Configuración del sistema de radiocomunicaciones móviles.

El sistema celular se compone de varios elementos cuyo funcionamiento es conjunto y conlleva a un mismo objetivo que es proporcionar el servicio de telefonía con una serie de características que lo distinguen de otros. Sus componentes más importantes son: La central de telefonía celular, también conocida como MTX (Mobile Telephone Exchange), MSC

11

(Mobile Service Center) o MTSO (Mobile Telephone Service Office); las radiobases o estaciones base; los teléfonos celulares también conocidos como equipo terminal o unidad móvil; y los enlaces o medios de transmisión que sirven para unir o enlazar los componentes del sistema. Un sistema de telefonía celular por definición funciona en interconexión con la Red de Telefonía Pública Conmutada (RTPC) o PSTN (Public Switching Telephone Network), por consiguiente es considerada como un elemento más para su operación. 1.1.1.2.1 Unidad móvil

Es lo que permite al usuario poder estar en contacto con el sistema, es la interfaz directa cuando se encuentra dentro del área de cobertura de una celda. Además de transmisión de voz, la unidad móvil está dirigida por el sistema y tiene la capacidad de sintonizar cualquier canal de radiofrecuencia y transmitir en un nivel de potencia determinado. 1.1.1.2.2 Radiobase o Estación Base (EB)

Entabla la comunicación entre la unidad móvil y el MTSO, hay una radiobase por celda, y es la encargada de encausar las llamadas originadas o destinadas en su área de cobertura. Monitorea y supervisa las llamadas y la ubicación de las unidades móviles en su área, además de realizar avisos para la transferencia de móviles a otras celdas (hand-off).

1.1.1.2.3 Central de Telefonía Celular o MSC

Es una central de conmutación dedicada especialmente a dar servicio celular. Realiza funciones relativas al tratamiento, monitoreo y control de los canales de radiofrecuencia. Sirve también de acceso entre el celular y la PSTN y otras áreas de servicio celular.

12 1.1.1.2.4 Red de Telefonía Pública Conmutada

Para integrar el sistema de telefonía celular, los MTSO se interconectan a una central de la PSTN a fin de permitir el acceso para los usuarios de telefonía celular con el resto del mundo. 1.1.1.3 Calidad de Servicio

Cuando se diseñan redes celulares se desea que la calidad del servicio sea comparable con el servicio de telefonía convencional. El nivel de calidad de un sistema móvil lo establece el Grado de Servicio (GOS) que puede ser definido como la porción de llamadas que no pueden cursarse en la hora pico debido a insuficiencia de equipos, con respecto al total de llamadas que se originan en el periodo. Para un buen diseño de red el GOS debe ser típicamente de 0.02% a 2% y si es posible menor. Esto significa que como máximo 2 llamadas en promedio, de cada 100 pueden ser bloqueadas, o considerarse llamadas perdidas en horas pico de servicio. Durante las horas no pico el sistema no debe tener problemas para llevar a cabo todas las llamadas. Cuando se habla de calidad en los sistemas de telefonía móvil no sólo se debe pensar en que todas las llamadas se deben procesar, sino que también el porcentaje de palabras y frases transmitidas a través del enlace radioeléctrico debe ser muy cercano a 100%. Esta calidad de fidelidad de señal se logra minimizando la interferencia cocanal y de canales adyacentes.

1.1.1.4 Hand off o Hand over

El usuario tiene que ser capaz de utilizar su unidad móvil a través de diferentes áreas de cobertura y por los diferentes sistemas celulares que ofrecen el servicio. El handoff es la habilidad que tiene el sistema de transferir responsablemente una señal móvil desde una estación base a otra, o dentro de la misma estación base de un canal a otro. Este mecanismo es

13

una característica única del sistema celular y lo diferencia de otros tipos de sistemas de radiocomunicaciones de concentración de enlaces.

1.1.1.5 Interferencia

Los sistemas celulares pertenecen a la clase de sistemas radioeléctricos limitados por interferencia. En estos sistemas, la interferencia múltiple cocanal es una situación normal aunque controlada, y constituyen el factor primordial para determinar el área de servicio. En

C efecto, la calidad del servicio depende de la relación portadora/interferencia   . I La interferencia en los sistemas telefónicos móviles, está íntimamente ligada al patrón de reuso de frecuencias. Para cluster que está formado por 4 celdas (N = 4), sólo tenemos 4 grupos distintos de frecuencias. Un usuario de una celda específica sólo percibe interferencia de las señales provenientes de celdas con el mismo grupo de frecuencias de la celda a la que él pertenece.

1.1.1.6 Proceso de Planificación de una Red Celular

Al momento de planificar una red celular se deben considerar elementos como: •

Costo de la construcción de la red.

•

Capacidad de la red.

•

Cobertura.

•

Máxima congestión permitida.

•

Calidad de las llamadas

Además se deben tomar en cuenta otros factores que afectan la demanda de los servicios de la red. Estos, comúnmente, están relacionados con la cantidad de habitantes en el

14

área, la distribución de la población y de los vehículos, así como las estadísticas del uso de la telefonía. Hoy en día, los pasos que se siguen para diseñar las redes son los siguientes [8]: 1. Recolección y análisis de toda la información relevante a ser utilizada, como por ejemplo: •

Mapas topográficos de cada una de las regiones a las que se le prestará servicio.

•

Información estadística y proyecciones de información de cada zona, la penetración inicial del servicio, los servicios de valor agregado a ser soportados.

•

Bandas de frecuencias disponibles, y las correspondientes permisologías dadas por el ente regulador.

2. Dimensionamiento de la red basado en los requerimientos de cobertura y calidad. 3. Selección de los sitios de las estaciones base. 4. Verificación de los sitios seleccionados mediante visitas de campo, de cada uno de los elementos que conforman la red, con el fin de determinar si cumplen con los requisitos necesarios como son: acceso a las vías y carreteras, suministros eléctricos cercanos, posible existencia de infraestructura y equipos de otras operadoras. 1.1.2 Método para el cálculo de cobertura 1.1.2.1 Método de Okumura-Hata

Este método se deriva del artículo de Okumura y hoy en día se ha convertido en el modelo de propagación más popular para entornos móviles debido a su facilidad de aplicación mediante el uso de una expresión empírica, y su posibilidad de emplear ordenadores.

15

Este modelo está basado en mediciones experimentales realizadas en la ciudad de Tokio, en diversas condiciones de terreno y entornos de propagación.

La necesidad de

optimizar el método, condujo al desarrollo de expresiones numéricas para las curvas normalizadas de propagación de Okumura.

Hata obtuvo, mediante análisis de regresión

múltiple, una serie de expresiones que proporcionan la pérdida básica de propagación para medios urbanos, suburbanos y rurales, conocida hoy como la ecuación del modelo de Okumura-Hata. Las limitaciones fundamentales del modelo de Hata son las siguientes [9]:

•

La frecuencia de transmisión (

f

c

) está limitada al siguiente rango:

150 ≤ f c ≤ 1500 Mhz 30 ≤ hT ≤ 200m

•

La altura efectiva de la antena ( hT ) debe estar entre

•

La distancia entre la estación transmisora y la receptora (d) se encuentra entre

1 ≤ d ≤ 20 Km •

La altura del móvil ( hM ) está limitada por 1 ≤

hM ≤ 10m

Es importante aclarar que la altura efectiva de la antena se define como la altura total de la antena sobre el nivel medio del terreno. Incluye por tanto su altura propia sumada a la de la colina, montaña o edificio sobre el que está instalada.

Figura 1.5 Método para calcular la altura efectiva de la antena de una estación base

16

Posteriormente el modelo de Hata fue extendido para el rango de frecuencias entre

1000 ≤ f c ≤ 2000 MHz .

La expresión para las pérdidas en zonas urbanas adoptado para

aplicaciones GSM900 y GSM1800 es la siguiente [8]:

L

50

= A + B log

f

c

[

]

− 13,83 log( hT ) − a( hR ) + 44,9 − 6,55 log hT log d

(1.6)

donde

y

A = 69,55  150 ≤ f ≤ 1000Mhz B = 26,16 

(1.7)

A = 46,30  1000 ≤ f ≤ 2000Mhz B = 33,9 

(1.8)

a(h ) es el factor de corrección para la altura de la antena del móvil, y está definida de la R

siguiente manera: Para pequeñas a medianas ciudades. a(hR) = (1,1log

f

c

− 0,7) hR − (1,56 log

f

c

− 0,8)dB

(1.9)

donde 1 ≤ hR ≤ 10m Para grandes ciudades.

a (hR ) = 8,29(log(1,54hR )) 2 − 1,1 dB, a (hR ) = 3,2(log(11,75hR )) 2 − 4,97 dB, Área Suburbana.

f c ≤ 200Mhz f c ≤ 400Mhz

(1.10) (1.11)

17

2   f  log( urbana = ( ) − 2 ) − 5 , 4 L50 L50   28  

dB

(1.12)

Área Rural.

L

50

= L50 (urbana ) − 4,78(log f ) 2 + 18,33 log f − 40,94 dB

(1.13)

El modelo de Hata no toma en cuenta las correcciones específicas del terreno disponibles en el modelo de Okumura (corrección por terreno montañoso, por montaña aislada, por terreno con pendiente, por terreno mixto Tierra-Mar, etc).

Este modelo es

apropiado para sistemas móviles de células cuyos radios sobrepasen 1 Km.

No es

recomendable para sistemas de comunicación personal (PCS).

1.1.3 Global System for Mobile Communications (GSM)

En las normas IS-54 (Interim Standard 54) y GSM, los radios comparten sus recursos de canal en los dominios de la frecuencia y del tiempo. Los métodos utilizados para hacer reservaciones adicionales en el dominio del tiempo son las técnicas TDMA (Time Division Multiple Access), y éstas incrementan considerablemente la complejidad del sistema, cuando se compara con celulares analógicos. La recompensa, sin embargo, es mejor rendimiento y funciones adicionales, sin necesidad de mayor ancho de banda por usuario. La tecnología GSM opera en configuración full dúplex en las bandas de frecuencias 800 MHz, 1800 MHz y 1900 MHz, con una combinación de técnicas FDMA (Frequency Division Multiple Access) y TDMA.

18

Las bandas de frecuencias son: GSM 900: Uplink

880 – 915 MHz

Downlink

925 – 960 MHz

Separación Tx/Rx

45 MHz

GSM 1800/DCS 1800: Uplink

1710 – 1785 MHz

Downlink

1805 – 1880 MHz

Separación Tx/Rx

95 MHz

GSM 1900/ PCS 1900: Uplink

1850 – 1910 MHz

Downlink

1930 – 1990 MHz

Separación Tx/Rx

80 MHz

Siendo Uplink la transmisión desde el móvil a la estación base, y downlink la transmisión desde la estación base al móvil. El sistema GSM subdivide el canal de frecuencia por medio de técnicas TDMA, subdividiendo cada canal de frecuencia en 8 ranuras de tiempo diferentes, enumeradas de 0 a 7. Cada una de las ranuras de tiempo es asignada a un usuario individual. A un grupo de 8 ranuras de tiempo se le llama trama TDMA, y todos los usuarios de una misma frecuencia comparten una trama común. Si un móvil, por ejemplo, tiene asignada la ranura número 1, transmite solamente en esta ranura de tiempo y se mantiene ocioso con el transmisor apagado durante las siguientes siete ranuras. El período de encendido y apagado del transmisor de un móvil es llamado “bursting”. La longitud de una ranura de tiempo, que es equivalente a un paquete de un móvil, es aproximadamente 576,9 µs (156,25 bits de duración), y la longitud de una trama TDMA es de 4,615 ms (8 x 576,9 µs) [10].

19 1.1.4 Algoritmos Genéticos (AGs)

Los AGs son un método de búsqueda basado en los principios y conceptos de la selección natural y la evolución. Son robustos y estocásticos, y constituyen un arma poderoso y efectivo a la hora de resolver problemas complejos. AGs son particularmente efectivos cuando el objetivo es encontrar un máximo global aproximado [12]. En AGs una población o grupo de soluciones potenciales es generada por la evolución hacia una solución óptima global. La evolución hacia un óptimo global ocurre como resultado de la presión ejercida por un proceso de selección basado en un fitness ponderado, y la exploración del espacio

de soluciones se logra por recombinación y mutación de las

características existentes en la población actual [12]. 1.1.4.1 Terminología en AGs 1.1.4.1.1 Genes y Cromosomas. Como en la evolución natural, el gen es el bloque de

construcción básico en la optimización por algoritmos genéticos. Generalmente, los genes son una representación codificada de los parámetros individuales de optimización. Dentro del paradigma de los AGs, una hilera o “string” de genes es denominado cromosoma. Los cromosomas pueden ser codificados como una hilera binaria, una hilera de números reales, o una combinación de las mismas. 1.1.4.1.2 Poblaciones y Generaciones. En optimizaciones basadas en AGs, un conjunto de

soluciones de prueba en la forma de cromosomas constituye una población. La población es la unidad que los AGs utiliza para buscar las soluciones óptimas. Las iteraciones en optimizaciones con AGs son llamadas generaciones.

La Reproducción consiste en la

selección y recombinación/mutación continua hasta que una nueva generación sea creada para remplazar la original. Idealmente, individuos con mejores características producen más copias de ellos mismos en generaciones subsecuentes, resultando en un cambio sistemático de la población hacia un punto de solución óptima. El proceso puede ser terminado de diferentes maneras: el proceso se termina cuando algún individuo tenga un error menor a un épsilon, el número de generaciones excede un valor preseleccionado, o algún otro criterio convergencia.

20

1.1.4.1.3 Padres. Siguiendo un proceso de inicialización en el cual la población es creada,

pares de individuos son seleccionados de la población de manera aleatoria pesada por la medida de cuán buenas son las características del individuo, y son designados como padres. En un esquema típico de selección, modelado como una rueda de la ruleta ponderada, a cada individuo de la población se le asigna un espacio en la rueda de la ruleta que es proporcional a la medida relativa de su característica. La rueda se gira cada vez que se requiera un padre. Los individuos con grandes espacios en la rueda tienen mayor probabilidad de ser seleccionados y, por lo tanto, mayores opciones de transmitir sus características a la siguiente generación. 1.1.4.1.4 Hijos.

La descendencia, o los hijos, son generados a partir de los padres

seleccionados utilizando operadores estocásticos simples. Los operadores principales son: cruce y mutación. El cruce ocurre con una probabilidad p cross (típicamente 0,6-0,8) [11] y comprende la selección de las partes que van a cruzarse y la combinación de la información genética de ambos padres. Específicamente en un cruce de punto simple, el primer hijo recibe la información que precede al punto de cruce del padre 1 y la información que sigue al punto de cruce del padre 2. El hijo 2 recibe la información genética restante, la que no se le dio al hijo 1.

Los dos hijos producidos comparten las características de ambos padres como

resultado de éste proceso de recombinación.

También son usados otros procesos de

recombinación, sin embargo el cruce es el más importante. La Recombinación (cruce) y selección son las maneras principales en que ocurre la optimización con AGs. 1.1.4.1.5 Mutación. La mutación es un mecanismo para asegurar que la selección excesiva no

conduzca a una convergencia prematura a una solución sub-óptima. La mutación también sirve como una medida para introducir nuevos e inexplorados puntos en el dominio de la búsqueda del optimizador de AGs. La mutación introduce material genético que no está presente en la población. La mutación es menos importante que el cruce en la mayoría de las optimizaciones con AGs y es generalmente ejecutado con una probabilidad p mutation (típicamente de 0,05), que es mucho más pequeña que p cross [11]. 1.1.4.1.6 Fitness o función de adaptabilidad. La función objetivo que define las metas de la

optimización, llamada función de adaptabilidad en el paradigma de los AGs, es una medida

21

para asignar un valor a cada individuo de la población. La función de adaptabilidad es usualmente el enlace entre el problema físico y el proceso de optimización con AGs. Esta función asigna a un individuo un número que expresa que tan buena es la solución que el individuo representa. 1.1.5 MATLAB

MATLA es una “poderosa herramienta para la investigación”. Es un entorno de computación y desarrollo de aplicaciones totalmente integrado, orientado para llevar a cabo proyectos en donde se encuentren implicados elevados cálculos matemáticos y la visualización gráfica de los mismos. Actualmente MATLAB dispone de un amplio abanico de programas de apoyo especializados, denominados Toolboxes, que extienden significativamente el número de funciones incorporadas en el programa principal. Estos Toolboxes cubren, prácticamente, todas las áreas principales en el mundo de la ingeniería y la simulación, destacando entre ellos por su importancia en este proyecto el Mapping Toolbox y el Genetic Algorithm and Direct Search Toolbox.

El Mapping Toolbox de MATLAB es una colección de funciones e interfaces con el usuario que permite leer, escribir, mostrar y manipular datos geoespaciales, como límites políticos, litorales o la topografía o elevación de cualquier punto ubicado en cualquier latitud y longitud del globo terrestre.

El Mapping Toolbox es capaz de leer formatos como

GTOPO30, DTED, ETOPO5, y además provee las herramientas para construir el lector de

cualquier formato de datos geoespaciales como el SRTM el cual es un modelo digital del terreno global con una resolución aproximada de 90 m por píxel (3arcseg). Por otro lado, el Genetic Algorithm and Direct Search Toolbox es un conjunto de funciones que permite extender las capacidades de optimización de MATLAB; contiene herramientas que facilita el uso de AGs y algoritmos de búsqueda directa para problemas difíciles de resolver con las técnicas de optimización tradicionales.

22 1.2 Antecedentes

Existen trabajos previos que han tratado el problema de planificación de redes celulares con algoritmos de optimización. En [3], se propone una metodología basada en 3 niveles; un primer nivel para calcular el número de EBs necesarias en un área estudio; un segundo nivel para obtener la mejor localización de las EBs, y por último, un tercer nivel para graduar los parámetros de las radiobases con el fin de minimizar el costo total del sistema, pero cumpliendo con ciertos requerimientos técnicos esperados. El trabajo citado anteriormente, emplea un algoritmo de optimización denominado “Recocimiento simulado” (Simulated Anneling), cuyo nombre se deriva de la forma como se consiguen ciertas aleaciones en forja. Este algoritmo, en este trabajo en particular, maximiza una función objetivo basada estrictamente en costo. Es importante destacar que en [3] se utiliza un factor de reuso de frecuencias de N=7, y el modelo de propagación empleado es el modelo de Hata. La principal ventaja de esta metodología es que considera la distribución no uniforme del tráfico. Sin embargo, para lograr el menor costo, descuida otros parámetros como la cobertura, el tráfico y la interferencia. Esta metodología es aplicada al diseño de una red celular para Singapur, obteniéndose resultados satisfactorios. Otra metodología para la planificación de redes celulares se describe en [2], donde un esquema de optimización basado en “Recocimiento simulado”, se emplea para minimizar una función objetivo cuyos componentes son la cobertura, la capacidad, la interferencia, el handover y el costo. Este trabajo se divide en dos niveles: uno para la localización de las estaciones base, y otro para la configuración de las mismas (potencia de transmisión de las antenas, tipo de antenas, ángulo de inclinación de las antenas, etc).

23

La principal ventaja de este método es que localiza las estaciones base a partir de una lista de “sitios” candidatos, y ofrece la posibilidad de reacondicionar una estación base existente. No obstante, los niveles de interferencia alcanzados son altos y la metodología no incluye un patrón de asignación de frecuencias.

24 CAPÍTULO II OBJETIVOS 2.1 Objetivo General

.- Diseñar una herramienta que facilite el proceso de planificación de redes celulares.

2.2 Objetivos específicos

.- Definir un modelo matemático que describa y/o represente los sistemas de telefonía móvil en cuanto a los parámetros utilizados para su diseño:

cobertura, capacidad,

interferencia, costo. .- Plantear una función de costo que permita evaluar las diferentes soluciones y determinar la óptima. .- Desarrollar una herramienta que permita estimar los niveles de cobertura, tráfico e interferencia en los sistemas de telefonía móvil. .- Implementar un software de optimización basado en AGs, que a partir de diferentes soluciones determine la óptima.

25 CAPÍTULO III PLANTEAMIENTO DEL PROBLEMA

El problema que se quiere tratar con el desarrollo de este proyecto es la escogencia de los “sitios” o puntos del terreno donde colocar las radiobases de las empresas de telefonía celular de una forma óptima; es decir, dada un área a la cual se le quiere brindar servicio de telefonía celular, se debe encontrar los puntos del terreno donde colocar las estaciones base de manera que garantice calidad de señal (mínima interferencia), servicio en todo el terreno (área de cobertura) y a todos los usuarios a las horas que ellos lo requieran (tráfico telefónico), al menor costo de inversión. Este problema no es fácil de solventar, para ello es indispensable determinar: 1. Un Método para el Cálculo de la Cobertura, el cual permita estimar la potencia de recepción en cada punto del terreno, proveniente de las radiobases, tomando en cuenta la topología del terreno, el grado de urbanización, la distancia entre el punto y la radiobase, etc. 2. Un Modelo Matemático, que describa y represente el problema planteado, en este caso, un Sistema de Telefonía Celular: usuarios, demanda de servicio, área de cobertura, etc. 3. Un Algoritmo de Optimización, que proporcione múltiples soluciones, que sea de búsqueda global y que sea fácil de implementar. 4. Una Función Objetivo, la cual permita la evaluación de las múltiples soluciones, hasta dar con la óptima.

3.1 Método para el cálculo de cobertura.

Calcular la propagación de las ondas en los sistemas de comunicaciones móviles es un asunto complejo. La radio transmisión en sistemas celulares se debe calcular tomando en cuenta diversos factores como: el perfil del terreno y la presencia de edificaciones, árboles y

26

otros obstáculos que impidan o perturben el paso de la señal que se desea propagar. Debido a esto, varios autores han desarrollado diversos modelos empíricos para estimar las perdidas de propagación en distintos ambientes clasificados, de acuerdo a lo mencionado anteriormente, en : urbanos, suburbanos y rurales. Entre estos modelos tenemos: •

Modelo de Okumura [13]

•

Modelo de Hata [9]

•

Modelo de Ibrahim y Parsons [7]

•

Modelo de Lee [6]

que son los que tomaremos en cuenta para este estudio. La escogencia del método apropiado para la implementación de este trabajo se realiza evaluando cada método con respecto a: •

Simplicidad del método.

•

Adaptabilidad a Caracas

•

Método más usado

•

Factibilidad de los datos usados

A continuación de muestran los resultados: Modelos/Características

Simplicidad

Okumura

9

Hata

9

9

Adaptabilidad

Más Usado

9

9

9

9

9

Ibrahim y Parsons Lee

Factibilidad

9

Tabla 3.1 Métodos de Cálculo de Cobertura y sus características

El método de cálculo de cobertura a usar es el Modelo de Hata.

27

3.2 Función Objetivo

La función objetivo, también llamada función de costo, se define con la finalidad de evaluar las soluciones arrojadas por el algoritmo de optimización implementado; así, nos da una idea que cuáles son las soluciones más convenientes para resolver nuestro problema, partiendo de los valores de la función objetivo debido a cada una de dichas soluciones. La función objetivo de este estudio tiene la siguiente forma:

Fo = ∑i =1Wi Ei n

(3.1)

En mayor detalle, la función objetivo es la siguiente: cuad 4 − N −U cobertura Nb Creq j Ct j 1 ∑ i=1 ∑i=1Y ij CBTS j CIA Fo = W1 N +W 2 Nb ∑1 Creq +W 3 Nb CBTS +W 4 UINTERFEREN N max 4

(3.19)

j

con W1+W2+W3+W4=1. El valor máximo de Fo es 1 y ocurre en el peor caso, el valor mínimo es 0 y es al que queremos llegar. 3.3 Modelo Matemático

El problema de la localización óptima de antenas en el diseño de redes de telefonía móvil, puede ser planteado como un problema de optimización, de manera que partiendo de un área específica a la que se desea dar cobertura, de la demanda de tráfico en dicha área y de la topología del terreno, se puedan minimizar los costos totales de inversión, sujeto a ciertas restricciones que definan la operación satisfactoria de la red. Se tiene un área S al cual se desea dar servicio de telefonía móvil, y un grupo de puntos del terreno definidos por U = {u1, u2, ..., uN} donde N es el número total de puntos.

28

Supongamos que cada punto del terreno representa un usuario. Cada usuario está definido por sus coordenadas cartesianas (xi, yi, zi) con 1 ≤ i ≤ N y z es la altura sobre el nivel del mar. Cada usuario está representado por: •

Un umbral de servicio requerido en dBm (Q), el cual depende del tipo de servicio (exteriores, interiores, en el carro, etc)

•

Una demanda de tráfico en Erlang (e)

•

Un estimado de las pérdidas de propagación en dB (Li)

Para poder dar cobertura a toda el área, S debe ser dividida en j celdas, donde cada celda (Cj) está delimitadas por: •

Un área específica de servicio (Sc)

•

Un radio (Rc)

Cada celda poseerá una estación base, la cual está definida por: •

Una capacidad de tráfico (Ct) definido por el número de transmisores.

•

Una potencia de transmisión en dBm (Pt)

•

Una o varias antenas An

Las pruebas se realizarán suponiendo que todas las antenas son omnidireccionales y que tienen asociada una ganancia GA. Para conocer si un punto cualquiera forma parte del área de cobertura de una célula, se debe calcular la potencia de recepción en dicho punto, de la siguiente manera:

Pr = PT + GA + GM − Li

(3.3)

donde Pr es la potencia de recepción que se quiere calcular, PT es la potencia de transmisión de la antena, GA es la ganacia de la antena, GM es la ganancia del terminal móvil, y Li representa las pérdidas del trayecto, las cuales, según el modelo de Hata, se define de la siguiente manera [5]:

29

L ( d B ) = 6 9 , 5 5 + 2 6 ,1 6 lo g f − 1 3 ,8 3 lo g (h ) − a ( h ) + [4 4 , 9 − 6 , 5 5 lo g h ]lo g d 50

T

c

R

T

(3.4) donde

L50

es el valor medio de las pérdidas del trayecto (dB).

fc hT

es la frecuencia de transmisión (MHz). y

d

hR

alturas de las antenas transmisoras y receptoras (m). distancia (km).

a (h ) R

es el factor de corrección para la altura de la antena del móvil.

Para que un punto cualquiera del terreno se considere cubierto por la señal de una EB específica, la potencia recibida por dicho punto debe ser mayor a Q (umbral de servicio requerido por un usuario), por lo tanto, para todo punto del terreno se debe cumplir

Pr (u i ) ≥ Q

(3.5)

donde Pr(ui) es la potencia de recepción en un punto ui del terreno. La potencia de recepción en un punto ui del terreno depende de su distancia d a la estación base, por lo tanto toda señal proveniente de una radio base puede cubrir un área hasta una distancia máxima, que está definida por la distancia a la cual Pr = Q ,esta distancia máxima está representada por RCMAX y su valor viene dado por:

log(dKm) ≤ log( Rc max ) =

Pt + G A + G M − Q − 69,55 − 26,16 log f c + 13,83 log(hT ) + a ( hR ) 44,9 − 6,55 log hT (3.6)

30

con

R

c max

igual al máximo radio de la célula. Por lo tanto el mínimo número de celdas

necesarias para dar cobertura al área S es [3]:

Nc =

S

S

(3.7)

C max

donde Scmax es el área máximo de una celda, y suponiendo geometría hexagonal, viene dado por:

S

C max

3 3 RC2 max = 2

(3.8)

Sin embargo, el servicio de telefonía celular no depende únicamente de que la potencia percibida por los usuarios o por todos los puntos del terreno sea mayor que Q , también es de vital importancia satisfacer las demandas de tráfico de los múltiples usuarios del servicio de telefonía móvil. Por consiguiente, la determinación del número de células requeridas para cubrir un área estudio, donde la demanda de tráfico es muy alta ( ∑ ei

>> N c Ct ),

viene

dado por: ei Nt = ∑ Ct

donde Ct es la capacidad de tráfico de una radio base y

(3.9)

∑e

i

es la demanda de tráfico de

todos los usuarios de S. Ahora podemos conocer el máximo número de células necesarias para servir toda el área S.

Nbmax = max{Nc, Nt}

(3.10)

Cabe destacar que Nbmax es el número máximo de células que podemos tener, pues la idea es optimizar, es decir, encontrar el número mínimo de celdas necesarias para solucionar el problema tanto por cobertura, como por tráfico. Una vez determinado el número de celdas es importante hablar de los usuarios pertenecientes a cada una de dichas celdas. Se dice que un punto del terreno ui pertenece a una

31

celda j (Cj) si

Prj (ui ) ≥ Q

P (u )

(con

rj

i

igual a la potencia de recepción del punto ui

proveniente de Cj). Por lo tanto, Cj está representada por [2] :

C = {u : P (u ) > Q ∨ P (u ) > P (u ), ∀k ,1 ≤ k ≤ Nb, k ≠ j} j

i

rj

i

rj

i

rk

i

(3.11)

Cobertura:

Cada usuario debe tener al menos una señal por encima del umbral requerido, de esta manera, para el área S el número de puntos del terreno que tienen cobertura es:

∑u =U i

cobertura

donde

1 si Pr (ui ) ≥ Q  µi =  0 en otro caso 

(3.12)

Idealmente se espera que Ucobertura = N, es decir que todos los puntos del terreno tengan cobertura. La ecuación normalizada que describe la total cobertura del sistema es la siguiente [2]:

E1 =

N − U cobertura N

(3.13)

donde Ucobertura es el número de puntos del terreno con cobertura y está definida como una función que depende de la potencia de recepción. Se puede notar que esta ecuación toma valores entre 0 y 1, es 1 cuando ningún punto del terreno tiene cobertura (peor caso), y vale cero cuando todos los puntos del terreno son cubiertos por el servicio (mejor caso).

32 Capacidad:

Cuando el tráfico telefónico es muy alto, se pueden congestionar las líneas ocasionando pérdidas de las llamadas; por esta razón es importante que la capacidad de las radio bases sea suficiente para cubrir la demanda de tráfico de todos los usuarios del sistema. La ecuación parametrizada que representa el tráfico telefónico se muestra a continuación:

E2 =

1 Nb Creqj − Ct j ∑ j =1 Nb Creqj

(3.14)

donde Creqj es la demanda de tráfico en los puntos pertenecientes a la celda j (Erlang), y Ctj es la capacidad de tráfico de la celda j (Erlang). Nb es el número de estaciones base. Para esta ecuación se debe cumplir:

 si   si  

Creq − Ct Creq − Ct > Gos =1 Creq Creq j

j

j

j

j

j

(3.15)

Creq − Ct Creq − Ct < Gos =0 Creq Creq j

j

j

j

j

j

Esta ecuación también varía entre cero y uno, cero para el mejor caso (la demanda es cubierta), y uno para el peor caso. Interferencia:

En cuanto a la interferencia, ésta se produce cuando un punto del terreno, no sólo percibe una señal proveniente de su EB (C), si no que además, recibe potencia de otra EB que transmite a la misma frecuencia que la suya (I). Es importante destacar que sólo se produce interferencia cocanal si la estación interferente tiene una frecuencia igual a la estación

33

interferida, y si además la relación entre las dos potencias es menor a un umbral   C < xd B  .  I  

U INTERFERENCIA = ∑k =1 λk donde N

 C 1 si I < xdB λk =  0 en otro caso 

(3.16)

donde U INTERFERENCIA son los puntos del terreno donde existe interferencia. Cada celda j lleva asociada un grupo de frecuencias (1, 2, 3, ó 4), de manera que al realizar la medición de

C para un usuario m, C será la potencia que percibe m proveniente de I

la celda a la que pertenece, e I será la potencia que recibe el usuario m provenientes de cada una de las celdas que tienen el mismo grupo de frecuencias que la celda a la que él pertenece. La ecuación parametrizada para la interferencia es la siguiente:

E3 = U INTERFERENCIA N

(3.17)

Esta ecuación representa la cantidad de puntos del terreno con interferencia, en relación a los puntos totales; mientras menor sea el número de puntos interferidos se tendrá mejor calidad de señal y la función se acerca a 0, en caso contrario se acerca a 1. Para un buen diseño se espera que

C ≥ 1 7 d B para el 90% de la zona de servicio. I

Por último es indispensable hablar de costo, pues al optimizar no sólo debemos garantizar un buen servicio, sino el mejor servicio al más bajo costo de inversión.

34 Costo:

La función de costo incluye, el costo de la estación base dependiendo del tipo de configuración (CBTSj). Los tipos de Estación base utilizados para el diseño de redes GSM son los siguientes [8]: ESTACIÓN BASE TIPO 1 (BTS1):

Estación base con 2 sectores, y 2 transmisores (TRX) por sector -

1 Caseta 4 TRX 2 Antenas RF 1 Fuente de poder 1 Antena de transmisión microondas

ESTACIÓN BASE TIPO 2 (BTS2):

Estación base con 3 sectores, y 2 transmisores por sector -

1 Caseta 6 TRX 3 Antenas RF 1 Fuente de poder 1 Antena de transmisión microondas

ESTACIÓN BASE TIPO 3 (BTS3):

Estación base con 3 sectores, y 3 transmisores (TRX) por sector -

1 Caseta 9 TRX 3 Antenas RF 1 Fuente de poder 1 Antena de transmisión microondas

ESTACIÓN BASE TIPO 4 (BTS4):

Estación base con 3 sectores, y 4 transmisores (TRX) por sector -

1 Caseta 12 TRX 3 Antenas RF 1 Fuente de poder 1 Antena de transmisión microondas

35

La capacidad de cada estación base viene dada por la siguiente tabla [8]: Configuración

Sectores

TRX/sect

Canales

Canales de

Capacidad/

Capacidad

de voz

señal/sec

Sector (Erl)

total (Erl)

2+2 (tipo 1)

2

2

14

2

8,2003

16,4006

2+2+2 (tipo 2)

3

2

14

2

8,2003

24,6009

3+3+3 (tipo 3)

3

3

22

2

14,896

44,688

4+4+4 (tipo 4)

3

4

29

3

21,039

63,117

Tabla 3.2 Configuración y capacidad de las EBs

Luego, la función que describe el costo viene dada por:

∑ ∑ Y CBTS E = Nb CBTS cuad

4

i =1

j =1

ij

j

4

max

(3.18)

4

Con

Y

ij

1  = 0 

si en la cuadricula i hay una radiobase de tipo j en otro caso

(3.19) donde CBTSj es el costo de la radiobase tipo j, con j = 1,2,3ó 4; y cuad es el número total de cuadrículas en el terreno.

36 CAPÍTULO IV METODOLOGÍA PROPUESTA

Una vez definido el modelo matemático, la función objetivo, y el método de cálculo de cobertura a utilizar, se procedió a diseñar el software que permitiría evaluar cada uno de los individuos de la población al momento de correr los algoritmos genéticos. La primera interrogante a responder fue sobre qué plataforma se haría dicho programa, ya que no sólo se debía contar con herramientas matemáticas y de cálculo, sino que esta plataforma debía facilitar el manejo de archivos de terreno (formatos como DTED, GTOPO 30, ETOPO5, GLOBE, etc) y la programación de AGs. MATLAB fue la opción escogida y SRTM el formato de archivo a utilizar. Cabe destacar que al principio se optó por utilizar el formato de archivo GTOPO30 para el manejo de los datos topográficos, puesto que Matlab permite el fácil manejo de estos archivos; sin embargo su separación entre puntos era muy grande (1km) y no se correspondía con el problema. Debido a esto, y gracias a la colaboración del Ing. Cristo Melá (quien me facilitó su lector de datos en formato SRTM) se pudo manejar archivos de terreno con una precisión de 90m entre puntos. Este lector de datos SRTM permite la obtención de puntos con distintas resoluciones, si la resolución es 1, los puntos está distanciados 100m aproximadamente, si la resolución se fija en 2, los datos se distancian 200m aproximadamente, y así sucesivamente. De acuerdo con los pasos que se deben seguir para la planificación de una red celular, ya se contaba con la información geográfica y topográfica de cualquier parte del mundo que se quisiera estudiar, ahora se necesitaban los datos concurrentes a la localidad: •

Extensión del área de estudio y la latitud y longitud del punto central de dicha área.

•

Cantidad de usuarios en toda el área.

•

Requerimiento (en Erlang) de cada usuario.

•

Frecuencia de transmisión.

•

Grado de Servicio (GOS).

•

Grado de urbanización de la zona.

37

Todos estos datos deben ser conocidos por el planificador de la red, por ello son considerados parámetros de entrada en el diseño de este programa.

4.1 Extensión

Para tener acceso a las características topográficas del terreno a estudiar es necesario calcular la extensión del terreno en cuanto al ancho y largo que se desea, pues el terreno se obtiene en forma rectangular, además se debe contar con la latitud y longitud del punto ubicado en el centro del rectángulo. Por ejemplo, sea Mapa el área que se quiere estudiar (ver Fig. 4.1), es necesario conocer la latitud y longitud del punto 0 y el valor de las distancias d1 y d2 en (km) .

MAPA d1 O

d2

Figura 4.1 Datos para obtener la matriz Terreno

Al disponer de estos datos, y fijar una resolución determinada, ya se pueden obtener las características topográficas del área estudio, las cuales vienen plasmadas en una matriz que se ha denominado “Terreno”. El lector SRTM también proporciona las latitudes y longitudes de cada punto de la matriz en forma de vectores; así, que cada elemento de la matriz contiene el valor de la elevación (en metros) de ese punto con respecto al nivel del mar, y tiene asociado una latitud y longitud en los vectores respectivos. El siguiente ejemplo ilustra la forma de la matriz Terreno (ver Fig. 4.2):

38

Se tiene el siguiente terreno:

1050 1000 950 900 10

10

5

5 0

0

Figura 4.2 Ejemplo de Terreno

Al acceder a sus datos topográficos obtenemos la siguiente matriz: Terreno = 932 937 939 957 995 1002 1005 1004 1005

943 961 955 979 1000 1003 1006 1008 1009

942 973 982 996 1012 1009 1004 1006 1006

922 956 987 996 1007 1007 1006 1006 1005

921 936 973 984 986 988 998 1006 1007

919 925 943 944 946 954 986 1003 1005

922 924 926 933 939 954 988 1001 1003

919 918 923 933 949 976 985 995 995

912 913 916 927 937 951 966 982 987

así el valor de cada elemento corresponde a la altura de ese punto sobre el nivel del mar, en metros.

39

El trabajar con formatos tan precisos (90m de distanciamiento entre puntos contiguos) trae como consecuencia que la matriz terreno sea muy grande; por esta razón se decidió dividir el terreno en cuadrículas. Cada cuadrícula puede verse como una matriz más pequeña de 5 filas por 5 columnas, como se muestra en la Fig. 4.3:

1

3

2

4

Figura 4.3 Matriz Terreno dividida en Cuadrículas

Los números dentro de cada cuadrícula se corresponde a su posición, es decir, si se habla de la cuadrícula 1, se está haciendo referencia a la cuadrícula superior izquierda, o sea la que tiene el 1 en su interior. Ahora la matriz terreno estaría formada por cuadrículas de 25 elementos cada una. Esto facilitaría el manejo de los datos, más adelante se verá. 4.2 Dimensionamiento de la red

Este paso nos permite determinar el número máximo de estaciones base que se deben utilizar para dar servicio al área anteriormente definida. Cabe destacar que la potencia de transmisión (PT=10W), la ganancia de la antena transmisora (GA=15dBi), y la ganancia de la antena móvil (GM=-3dBi), son valores fijados dentro del sistema, y son los valores típicos a la hora de planificar un sistema de telefonía celular [8] . El procedimiento es el siguiente:

40 En cuanto a la cobertura.

Se sabe que hay un umbral de señal que nos indica si un usuario tiene o no cobertura. También se sabe que la potencia recibida depende, entre otras cosas, de las pérdidas de propagación que a su vez depende de la distancia (ecuación 3.3). Como se conoce la potencia de transmisión y las ganancias de las antenas, se debe calcular d para obtener una Pr = Q dBm (Q esta por el orden de -95 dBm). Esa distancia representa el radio de las celdas (Rmax) (ecuación 3.6). Una vez obtenido el radio de la celda, se calcula su área suponiendo geometría hexagonal. Luego se divide el área del terreno, entre el área de las celdas y se obtiene el número mínimo de estaciones base necesarias para darle total cobertura al terreno (Nc, ecuación 3.7).

Superficie 3 3 R max 2 2

= Nc (4.1)

En cuanto al tráfico.

Según lo anteriormente expuesto, la demanda de tráfico de un área en particular, viene dada por el número de usuarios multiplicado por los requerimientos de cada usuario (en Erlang), multiplicado además por el porcentaje de intentos de llamadas, todo esto dividido entre 1 menos lo que se ha denominado factor de movilidad (ecuación 1.3). Como se desea conocer el número máximo de estaciones base que se necesitan para satisfacer los requerimientos de los usuarios, dividimos Traf entre la celda de menor capacidad llamada C1 (2 sectores con 2 TRXs cada uno).

Traf

C

1

= Nt

(4.2)

41

El número máximo de estaciones base será el máximo entre Nc y Nt (Ecuación 3.10). 4.3 Programa de Simulación.

El nivel de simulación realiza los cálculos necesarios para estimar los niveles de cobertura, tráfico e interferencia de una solución en particular. La entrada de este módulo son dos vectores (diploides) que tienen tantos elementos como cuadrícula tiene el terreno. El primer vector, llamado Cromosoma, está formado por elementos cuyos valores van de 0 a 4 (0,1,2,3,ó 4) y nos indica la existencia o no de estaciones base, y el tipo de dichas estaciones. El elemento número 1 del vector Cromosoma nos da información acerca de la cuadrícula número 1 de la matriz, el elemento 2 se corresponde con la cuadrícula 2 y así sucesivamente. La información suministrada por el vector viene dada por el valor de sus elementos, o sea, si el elemento número 1 del vector Cromosoma vale 0, quiere decir que en la cuadrícula 1 de la matriz Terreno no hay ninguna estación base; si en cambio hay un 1, en la cuadrícula número 1 hay una estación base tipo 1, si hay un 2, la estación base será del tipo 2, y así sucesivamente. Por ejemplo dado el vector:

Cromosoma = [0,4,0,0,1,0,2,3,0] y una Matriz (los números dentro de la matriz corresponden al número de la cuadrícula)

1

4

7

2

5

8

3

6

9

Figura 4.4 Matriz Terreno con cuadrículas numeradas

42

Se puede notar que el número de elementos del vector es igual al número de cuadrículas de la matriz (9), luego observamos que: La cuadrícula 1 no tiene estación base. La cuadrícula 2 tiene una estación base tipo 4. La cuadrícula 3 no tiene estación base. La cuadrícula 4 no tiene estación base. La cuadrícula 5 tiene una estación base tipo 1. La cuadrícula 6 no tiene estación base. La cuadrícula 7 tiene una estación base tipo 2. La cuadrícula 8 tiene una estación base tipo 3. La cuadrícula 9 no tiene estación base. Si relacionamos el Cromosoma con la matriz, se obtiene: (los números dentro de las cuadrículas representan el tipo de estación base)

0

0

2

4

1

3

0

0

0

Figura 4.5 Matriz Terreno con tipos de estaciones base en cada cuadrícula

El vector Cromosoma se genera en forma aleatoria y el número máximo de elementos distintos de cero (es decir, el número máximo de EBs) es Nbmax. El segundo vector, llamado vector Ubicación, puede tomar valores entre 1 y 25. Al igual que el vector Cromosoma el elemento número 1 del vector Ubicación nos da información acerca de la cuadrícula número 1 de la matriz y así sucesivamente, pero esta vez

43

la información consiste en el punto de la cuadrícula sobre el que se va a ubicar la EB, en caso de que exista (recordemos que cada cuadrícula está formada por 25 elementos). Ejemplo:

Cromosoma = [2,0,3,0] Ubicación = [8,16,1,24] De acuerdo con la información suministrada por los vectores se puede observar que hay una EB tipo 2 en el elemento 8 de la cuadrícula 1. En la cuadrícula 2 no hay EB. En el primer elemento de la cuadrícula 3 hay una EB tipo 3; y en la cuadrícula 4 no hay EB.

1 2 3 4 5

6 7 8

Figura 4.6 Ubicación de las EBs dada por los vectores Cromosoma y Ubicación

4.3.1 Cobertura

Una vez generados estos vectores, el vector Cromosoma es recorrido hasta dar con un valor distinto de cero. Con la posición de este elemento se obtiene el número de la cuadrícula en la matriz y el número del elemento en dicha cuadrícula, por lo tanto se tiene la posición exacta de la EB. Empleando los vectores de latitud y longitud devueltos por el lector SRTM se obtiene la latitud y la longitud del punto en cuestión y se hallan las distancias de ese punto a

44

todos los otros puntos de la matriz (utilizando también las latitudes y longitudes de dichos puntos). Esta distancia se emplea para hallar las pérdidas de propagación, que como sabemos es una función de la distancia (L(d)) y luego se halla la potencia de recepción en cada punto del terreno, proveniente de la EB en estudio (ecuación 3.3). Las potencias de recepción de todos los puntos, debido a una EB en particular son almacenadas en un arreglo de matrices, en este caso, Pr(1). Este procedimiento se realiza con cada punto del vector Cromosoma que sea distinto de cero, o sea, que implique la existencia de una EB. Por lo tanto, van a haber tantas matrices Pr como EBs. Cada vez que se encuentre un valor distinto de cero en el vector Cromosoma se dice que se ha encontrado una EB, y por consiguiente se genera su matriz Pr. Cada vez que se obtiene una matriz Pr, se actualiza una matriz denominada Cobertura. Esta matriz almacena un 1 en las posiciones de las EBs, y en los puntos del tereno donde no existe radio base se almacena el mayor valor de potencia de recepción proveniente de las distintas EBs. Por ejemplo: Supongamos que se encontró la primera EB, se halló su matriz Pr y se almacenaron sus valores en la matriz Cobertura; como es la primera EB, la matriz Cobertura será igual a Pr(1):

-64

-68

-72

-98

-102

-105

-52

1

-65

-76

-104

-107

-70

-84

-73

-89

-99

-113

-85

-90

-87

-100

-100

-110

-92

-95

-98

-101

-105

-109

-99

-101

-103

-105

-108

-111

Figura 4.7 Matriz Cobertura

45

Si ahora se da con la segunda EB y se halla su matriz Pr(2), obtendremos,

-107

-93

-74

-79

-71

-85

-105

-99

-66

-63

-69

-87

-103

-97

-62

-55

-58

-79

-108

-95

-66

1

-60

-76

-111

-100

-69

-61

-65

-88

-113

-100

-89

-85

-88

-96

Figura 4.8 Matriz Pr(2)

La nueva matriz Cobertura será modificada conservando los valores donde ella sea mayor que la matriz Pr(2): -64

-68

-72

-79

-71

-85

-52

1

-65

-63

-69

-87

-70

-84

-73

-55

-58

-79

-85

-90

-66

1

-60

-76

-92

-95

-69

-61

-65

-88

-99

-100

-89

-85

-88

-96

Figure 4.9 Matriz Cobertura modificada

A cada una de las EBs se le asigna un numero diferente a través de un contador (comenzando con el número 2, pues el 1 se utiliza para representar las EBs en la matriz Cobertura), y cada vez que la matriz cobertura se actualiza, en otra matriz – matriz de Pertenencia – se almacena el número de la EB que le provee una potencia a ese punto en particular, de esta manera se puede saber cuales puntos pertenecen a una celda específica, es decir, el área de cobertura de la celda.

46

Siguiendo con el ejemplo anterior tenemos que al principio la matriz de Pertenencia sería: 2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

Figura 4.10 Matriz de Pertenencia

puesto que a la EB 1 le corresponde el número 2 en la matriz de Pertenencia. Una vez que es modificada la matriz Cobertura, la matriz Pertenencia queda de la siguiente manera:

2

2

2

3

3

3

2

2

2

3

3

3

2

2

2

3

3

3

2

2

3

3

3

3

2

2

3

3

3

3

2

3

3

3

3

3

Figura 4.11 Matriz de Pertenencia modificada

Al concluir este proceso la matriz Cobertura se recorre buscando los puntos donde la recepción sea mayor que un umbral de potencia (Q). Estos puntos son considerados con cobertura (Ucob). Luego la función que mide la cobertura viene dada por:

E1 =

Elementos _ de _ la _ matriz − Ucob Elementos _ de _ la _ matriz

(4.3)

47 4.3.2 Capacidad

Cada vez que se encuentra un elemento distinto de cero en el vector Cromosoma, éste es almacenado en un arreglo llamado Tipo; tipo contiene puros elementos del 1 al 4 y representan el tipo de cada una de las EBs.

Como tipo se va llenando conforme van

apareciendo EBs, se sabe que el primer elemento de Tipo corresponde al tipo de la EB 1, y así sucesivamente. Una vez terminada la matriz Cobertura y Pertenencia, se procede a medir la capacidad de la red (esto se hace utilizando la matriz de Pertenencia). Cada EB tiene asignado un número en la matriz de Pertenencia que corresponde al orden en que fue encontrada en el vector Cromosoma más 1; así la EB 1 le corresponde el número 2, a la EB 2 le corresponde el número 3, etc. Sabiendo el tipo de la EB y el número que le corresponde en la matriz de Pertenencia, sólo resta hallar la cantidad de puntos con ese valor en la matriz de Pertenencia y así se puede saber el número de puntos que conforman la celda formada por dicha EB. Es decir, se sabe que la EB 1 está representada por el número 2 en la matriz de Pertenencia, luego si se contabiliza el número de 2 que existe en dicha matriz, se obtiene el número de puntos a los cuales la EB 1 le da servicio. Al obtener los puntos cubiertos por una EB en particular (o sea el área de cobertura de la celda) se calcula los requerimientos de capacidad de los usuarios en dicha celda. Esto se realiza de la siguiente manera:

Creq = N ° _ de _ puntos

Usuarios req _ user Elementos

(4.4)

donde req_user, es el uso promedio de cada usuario. La capacidad ofrecida (cap) por la celda viene dada por su tipo (1,2,3 ó 4). Luego se hacen las siguientes comparaciones.

48

Si

Creq − Cap < GOS ⇒ E = 0 Creq

(4.5)

Si

Creq − Cap > GOS ⇒ E = 1 Creq

(4.6)

La medición de capacidad viene dada por

E2 =

∑E Nb

(4.7)

Donde Nb es el número de estaciones base.

4.3.3 Interferencia

Para calcular los puntos del terreno con interferencia primero se realiza la asignación de grupos de frecuencia enumerados del 1 al 4 (ya que para GSM se emplean cuatro grupos de frecuencia). Para esto se sigue el patrón de reuso N=4. Después de asignar a cada celda su grupo de frecuencias se procede a realizar la medición de la interferencia. Como se sabe se tienen almacenadas las potencias de recepción de cada punto proveniente de cada una de las EBs. Luego para cada punto del terreno se calcula la relación entre la potencia recibida de la celda a la que pertenece, entre la potencia que recibe de cada una de las otras celdas con el mismo grupo de frecuencias. C < XdB Se dice que existe un punto con interferencia cuando I .

49

Luego la interferencia total se mide E 3 =

U int , donde Uint son los puntos Elementos

del terreno con interferencia.

4.3.4 Costo

El costo de cada una de las 4 configuraciones es sabido por el sistema, por lo tanto, sabiendo el número de estaciones base de cada tipo (mediante la utilización de contadores) se calcula el último parámetro necesario para el nivel de simulación.

E4 =

Con 1 * Costo 1 + Con 2 * Costo 2 + Con 3 * Costo 3 + Con 4 * Costo 4 Nb max* Costo 4 (4.8)

donde Con1, Con2, Con3 y Con4, son los contadores para cada tipo de EB, y los Costos (Costo1, Costo2, Costo3 y Costo4), son los costos de cada tipo de EB. Para este nivel de simulación, la función objetivo queda definida de la siguiente manera:

F = W1

Elementos − Ucob Elementos

∑ E +W

+ W2

Nb 1

3

U int Elementos

+ W 4E4

(4.9) Como los AGs están diseñados para obtener los puntos máximos de una función, el nivel de simulación devuelve:

Fitness

=

1 F

(4.10)

50 4.4 Algoritmos Genéticos (AGs)

Los AGs son los algoritmos de optimización escogidos para este proyecto. Su finalidad es encontrar la mejor solución al problema planteado mediante la búsqueda de soluciones. La calidad de esta solución es medida a través de su función de adaptabilidad (fitness) (que es el valor devuelto por el nivel de simulación), el individuo ( la solución) que tenga mayor fitness después de varias generaciones, será la mejor solución al problema planteado.

4.4.1 Población Inicial

La población inicial está formada por individuos diploides tales como el vector Cromosoma y el vector Ubicación descritos anteriormente. Estos individuos son generados aleatoriamente y están organizados en forma de estructuras. La estructura Individuo está formada por siete campos:

•

Individuo.Cromosoma: vector formado por 0,1,2,3,ó 4 que indican la existencia o no de EBs en las distintas cuadrículas del terreno.

•

Individuo.Ubicación: vector cuyos valores oscilan entre 1 y 25, e indican la posición exacta de la EB dentro de la cuadrícula.

•

Individuo.Fitness: número real que sirve para ponderar la calidad de dicha solución.

•

Individuo.Eint: número real que señala los niveles de interferencia que presenta esta solución.

•

Individuo.Ecost: número real que representa qué tan costosa es esta solución con respecto a un referenciado como máximo.

•

Individuo.Ecap: número real que indica en qué porcentaje la capacidad de la red cubre los requerimientos de los usuraos.

•

Individuo.Ecob: número real que señala el porcentaje de puntos del terreno que no tienen cobertura.

51

La población inicial es un arreglo de la estructura llamada Individuo. 4.4.2 Generaciones

Después de tener una población inicial se puede apuntar hacia la evolución para encontrar individuos más aptos. Las nuevas poblaciones son generadas por medio de la selección, el cruce y la mutación, y cabe destacar que el mejor individuo de cada generación pasará automáticamente a la siguiente generación, sustituyendo al individuo de menor fitness (elitismo); esto garantiza que el mejor individuo para la generación siguiente será aún mejor o el mismo en el peor de los casos. 4.4.2.1 Selección

Para seleccionar a los progenitores de la nueva generación se usa el método de la ruleta, el cual es un proceso de selección aleatoria basado en el funcionamiento de una ruleta ponderada, donde los individuos de mayor fitness tienen mayor probabilidad de ser seleccionados. El funcionamiento de la ruleta consiste en obtener la suma de los fitness de todos lo individuos de la población actual y multiplicarla por un número aleatorio entre 0 y 1; este número representa el lugar donde la ruleta se va parar. Ahora se van sumando los fitness de los individuos uno a uno hasta que dicha suma sea igual o contenga al número aleatorio definido anteriormente. El individuo con el cual la suma de su fitness alcance el valor aleatorio definido con anterioridad, será el individuo seleccionado.

4.4.2.2 Cruce

El cruce se realiza entre 2 individuos que han sido seleccionados previamente. Estos individuos pueden o no cruzarse, esto depende de la probabilidad de cruce que se halla definido.

52

Una vez que la condición de cruce sea VERDADERA, se genera, de forma aleatoria, un vector de 0s y 1s; este vector aleatorio nos señala que puntos van a heredar los hijos del padre y cuales de la madre. En los puntos donde el vector aleatorio contenga 1s, el hijo 1 tendrá la información genética del padre, y el hijo 2 heredará las características de la madre; en los puntos donde el vector aleatorio contenga 0s, el hijo 1 heredará las características de la madre, y el hijo 2 del padre (cruce uniforme). Ejemplo: Vector aleatorio [0 0 1 0 1 1 1 0 1] Padre [ 0 4 1 0 0 0 3 0 2 ] Madre [ 2 0 0 4 0 0 0 3 0 ] Hijo1 [ 2 0 1 4 0 0 3 3 2] Hijo2 [ 0 4 0 0 0 0 0 0 0] En caso de que la condición de cruce sea FALSA, el padre y la madre seleccionados pasarán a la siguiente generación. 4.4.2.3 Mutación

Después de realizar el cruce, existe la posibilidad de cambiar los bits de los vectores hijos. Esta probabilidad es muy baja (alrededor de 0.05), por lo tanto los nuevos individuos pueden sufrir múltiples mutaciones, como no. Cabe destacar que una vez que la condición de mutación sea VERDADERA, los bits mutados tienen mayor probabilidad de ser iguales a cero que a los valores restantes (1, 2, 3 ó 4).

53 CAPÍTULO V RESULTADOS

5.1 Caso de prueba 1

La metodología expuesta anteriormente es utilizada para diseñar un sistema celular GSM en el área de Singapur mostrada en las fig. 5.1 y 5.2. En la fig. 5.1 se puede observar que el área estudio (área encerrada en el rectángulo) es la parte sur de Singapur; ésta tiene una extensión de 260 km2 aproximadamente, y un grado de urbanización de 1, o sea es una zona urbana. Esta área se caracteriza por tener algunas zonas montañosas (ver fig. 5.2) y el borde inferior está rodeado de mar.

Figura 5.1 Mapa de Singapur

54

Figura 5.2 Características Topográficas de Singapur

Para este estudio los datos topográficos usados tienen una resolución igual a 5 (es decir, cada punto está distanciado por 500m aproximadamente) por lo tanto el área fue dividida en 44 cuadrículas de 2,5 x 2,5 km2. El sistema celular diseñado emplea un factor de reuso de frecuencias de N=4, un GOS de 5%, y un umbral de potencia de recepción (Q) igual a -93 dBm [3]. Se asume, según [3], que el promedio de duración de las llamadas es 1,76 min, lo cual, de acuerdo con la ecuación (1.2) es igual a un uso promedio de 30mErl por usuario. La probabilidad de llamada en la hora pico es 0,9 [3] y el número de usuarios en la zona es 18750 [3]. El factor de movilidad no fue tomado en cuenta. De la ecuación (3.7) se tiene que Nc = 9 y de la ecuación (3.9), Nt = 31 ; por lo tanto, Nbmax = 31 (ecuación 3.10). Luego, la localización de las antenas se determinó mediante la implementación de los AGs. Las probabilidades de cruce y mutación para los AGs, fueron fijadas en 0,8 y 0,05 respectivamente, y los pesos de la función objetivo fueron ajustados en 0.1 para la interferencia, 0.45 para el costo, 0.225 para la cobertura, y 0.225 para la capacidad. El número

55

de individuos por generación fue 50. El mejor individuo obtenido se muestra en la fig. 5.5. El AG fue detenido al observar que después de aproximadamente 15000 generaciones el mejor individuo no mejoraba, esto se hizo en la generación 20500 después de un tiempo de corrida igual a 92250s (25,625h). La función de adaptabilidad de este individuo tiene un valor de 0.85824 y presenta 10 EBs (4 EBs tipo 4 y 6 EBs tipo 3).

La evolución del máximo de la

función de adaptabilidad para el nivel de simulación (1-F) y el valor promedio de la misma se muestra en la siguiente figura (fig. 5.3):

Figura 5.3 Máximo de la función de adaptabilidad (mejor individuo, puntos rojos) Función de adaptabilidad promedio (puntos azules). Caso1.

56

La gráfica de la función objetivo hallada con el modelo matemático planteado (F), se muestra en la Fig. 5.3. Como era de esperar, a medida de que los AGs hallaban mejores soluciones, esta función tiende a cero.

Figura 5.3 Función Objetivo (mejor individuo, puntos verdes) Función objetivo promedio (puntos rosados). Caso1.

Figura 5.5 Mejor individuo para el diseño de la red GSM para Singapur. Ubicación de las EBs del mejor individuo.

57

La localización exacta del punto del terreno donde se ubican las EBs del mejor individuo, en cuanto a latitud y longitud, y el tipo de EB, se muestra en la siguiente tabla:

Latitud

Longitud

Tipo

1.3000

103.7817

4

1.3458

103.7775

3

1.2708

103.8108

3

1.2792

103.8442

3

1.3250

103.8317

4

1.3208

103.8525

3

1.3083

103.8900

4

1.3417

103.8900

3

1.3083

103.9317

3

1.3417

103.9525

4

Tabla 5.1. Ubicación exacta de las EBs del mejor individuo para Singapur

La división del área en celdas de acuerda a esta solución es:

Figura 5.6 División del área de Singapur en celdas, de acuerdo con la solución obtenida

58

Esta solución tiene asociado los siguientes parámetros de diseño:

Cobertura

99.88%

Interferencia

9,80%

Capacidad

100,00%

Tabla 5.2 Resultados de cobertura, capacidad e interferencia arrojados por la solución para el área de Singapur.

Este mismo caso es estudiado en [3], obteniéndose un número de EBs igual a 9. En [3] no se mencionan los parámetros obtenidos, pero se señala que la red fue diseñada para obtener un 90% de cobertura, lo que permite suponer que el porcentaje de cobertura obtenido en este trabajo, justifica la EB adicional. Es importante señalar que los niveles de interferencia obtenidos se ajustan a los requerimientos técnicos exigidos por los entes reguladores de las comunicaciones móviles.

5.2 Caso de Prueba 2

En esta ocasión la metodología propuesta es utilizada para diseñar una red GSM en el área comercial de Caracas; las características topográficas de esta área se muestran en la fig. 5.6. El área objeto de estudio tiene una extensión de aproximadamente 40 km2, y abarca las zonas desde La Urbina hasta Los Chaguaramos. La latitud y longitud media empleada fueron 10.492 y -66.85, respectivamente. Se utilizó un grado de urbanización igual a 1 debido a que es una zona urbana.

59

Figura 5.7. Características Topográficas de la zona comercial de Caracas

Para este caso los datos topográficos usados tienen una resolución igual a 2 (es decir, cada punto está distanciado por 200m aproximadamente) por lo tanto el área fue dividida en 44 cuadrículas de 1 x 1 km2. El sistema celular diseñado emplea un factor de reuso de frecuencias de N=4, un GOS de 5%, y un umbral de potencia de recepción (Q) igual a -93 dBm, al igual que en el caso anterior. Se asume, según las estimaciones citadas en [8], que el promedio de duración de las llamadas es de 45s, lo cual, de acuerdo con la ecuación (1.2) es igual a un uso promedio de 12,5mErl por usuario. La probabilidad de llamada en la hora pico empleada es 0,75 [6] y el número de usuarios en la zona es 50000 (el número de usuarios se obtuvo suponiendo una población de 1000000 de habitantes para el área comercial de Caracas, de los cuales el 20% son usuarios de telefonía móvil; si suponemos que estos usuarios son repartidos entre 4 empresas de telefonía celular, cada empresa da servicio a 50000 usuarios). El factor de movilidad no fue tomado en cuenta.

60

De la ecuación (3.7) se tiene que

Nc = 2 y De la ecuación (4.4), Nt = 35 por lo

tanto, Nb max = 35 (ecuación 3.10) Luego, por segunda vez, la localización de las antenas se determinó mediante la implementación de los AGs. Las probabilidades de cruce y mutación para los AGs, fueron fijadas en 0,8 y 0,025 respectivamente, y los pesos de la función objetivo fueron ajustados en 0.1 para la interferencia, 0.45 para el costo, 0.225 para la cobertura, y 0.225 para la capacidad. El número de individuos por generación fue 50. El mejor individuo obtenido se muestra en la Fig. 5.10.

El AG fue detenido al observar que después de aproximadamente 15000

generaciones el mejor individuo no mejoraba, esto se hizo en la generación 49500 después de un tiempo de corrida igual a 148500s (41.25h). La función de adaptabilidad de este individuo tiene un valor de 0.88645 y presenta 10 EBs (5 EBs tipo 1, 1 EB tipo 2 y 4 EBs tipo 3). La evolución del máximo de la función de adaptabilidad (mejor individuo, puntos rojos) y el valor promedio de la misma (puntos azules) se muestra en la siguiente figura (Fig. 5.8):

Figura 5.8 Máximo de la función de adaptabilidad (mejor individuo, puntos rojos) Función de adaptabilidad promedio (puntos azules). Caso2.

61

Figura 5.9 Función Objetivo (mejor individuo, puntos verdes) Función objetivo promedio (puntos rosados). Caso2.

Figura 5.10 Mejor individuo para el diseño de la red GSM para el área comercial de Caracas. Ubicación de las EBs del mejor individuo.

62

La localización exacta del punto del terreno donde se ubican las EBs del mejor individuo, en cuanto a latitud y longitud, y el tipo de EB, se muestra en la siguiente tabla: Latitud

Longitud

Tipo

10.495

-66.89083

1

10.5066

-66.89083

1

10.4783

-66.88416

3

10.4966

-66.8825

1

10.5

-66.87583

2

10.4816

-66.87083

3

10.505

-66.8625

3

10.5016

-66.84583

3

10.476

-66.83583

1

10.483

-66.83583

1

Tabla 5.3. Ubicación exacta de las EBs del mejor individuo para el área comercial de Caracas

La división del área en celdas de acuerdo a la solución encontrada:

Figura 5.9.División en celdas del área comercial de Caracas, de acuerdo con la solución obtenida.

63

Esta solución tiene asociado los siguientes parámetros de diseño:

Cobertura

100,00%

Interferencia

9,08%

Capacidad

90,00%

Tabla 5.4 Resultados de cobertura, capacidad e interferencia arrojados por la solución obtenida para el área comercial de Caracas.

Como se puede observar en la Tabla 5.4, los parámetros de diseño obtenidos de la mejor solución encontrada, tienen valores aceptados dentro de los parámetros de diseño. Se brinda servicio en la totalidad del área (100% de cobertura), el 90% de los puntos del terreno no presentan interferencia, y sólo un 10% de las EBs (una EB en este caso) no cubre la capacidad total requerida por sus usuarios durante la hora pico. Por lo tanto, esta metodología cumple con los objetivos propuestos, ya que minimiza los costos de inversión, sin olvidar la calidad del servicio que se desea prestar.

64 CAPÍTULO VI CONCLUSIONES Y RECOMENDACIONES 6.1 Conclusiones:

•

El esquema de planificación celular puede ser modelado matemáticamente a partir de sus parámetros básicos de diseño, con el fin de obtener una función que permita evaluar la calidad del diseño.

•

Los requerimientos de cobertura y tráfico dan una aproximación del número de EBs necesarias para dar servicio a un área particular; sin embargo, el número de EBs necesarias para alcanzar calidad de servicio al menor costo de inversión, está íntimamente relacionado con la ubicación de las EBs.

•

La localización óptima de las EBs para los sistemas celulares puede ser visto como un problema de optimización, por lo tanto, en el proceso de planificación y diseño de redes celulares se deben incluir algoritmos de optimización que permitan alcanzar diseños óptimos de la red tanto en calidad de servicio como en costo de inversión.

•

Los resultados obtenidos indican que el problema de planificación y diseño de sistemas de telefonía móvil puede ser tratado mediante la implementación de un software basado en dos niveles: uno de optimización, que permita el diseño de una red que cumpla con ciertos requerimientos técnicos minimizando los costos de inversión, y un nivel de simulación que permita estimar la propagación de las distintas señales que operan en dicha red.

•

La utilización de los AGs como algoritmo de optimización arrojó resultados satisfactorios, puesto que se alcanzaron diseños de red con baja interferencia, total cobertura y un buen manejo del tráfico.

65

6.2 Recomendaciones:

•

El diseño óptimo e una red se puede alcanzar si además de localizar las EBs de manera de proveer cobertura total y manejo de tráfico al menor costo, se realiza una asignación óptima de los canales de frecuencia disponibles.

•

Se puede mejorar el planteamiento de la función objetivo si se incluye un operador que represente el hanover, puesto que éste es un parámetro importante a la hora de diseñar redes celulares.

•

Al manejar datos topográficos tan extensos, se debe pensar, desde el primer momento, en vectorizar y hacer operaciones matriciales debido a que los tiempos de ejecución disminuyen enormemente.

66 REFERENCIAS BIBLIOGRÁFICAS

[1] B. Abolhassani, E. Salt y D. Dodds, “A Two-Phase Genetic K-Means Algorithm for Placement of Radioports in Cellular Networks,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 34, No 1, pp. 533-538, febrero, 2004. [2] S. Hurley, “Planning Effective Cellular Mobile Radio Networks,” IEEE Trans. on Vehicular Technology, vol. 51, No 2, pp. 243-253, marzo, 2002. [3] Q. Hao, B. Soong, E. Gunawan, J. Ong, C. Soh y Z. Li, “A Low-Cost Cellular Mobile Communication Systems: A Hierarchical Optimization Network Resource Planning Approach,” IEEE J. Select. Areas Commun., vol. 15, No 7, pp. 1315-1326, septiembre, 1997. [4] R. Mathar, E. Salt y M. Schmeink, “Integrated Optimal Cell Site Selection and Frequency Allocation for Cellular Radio Networks,” IEEE Telecom. Systems, vol. 21, No 2-4, pp. 339-347, 2002. [5] RAPPAPORT, Theodore, (1996). Wireless Communications Principles & Practice. Edit: Prentice Hall.

[6] WILKES, Joseph y Vigía Garg, (1996) Wireless & personal Communications Systems. Edit: Prentice Hall.

[7] LEE, Willians, (1995) Mobile Cellular Telecommunications analog and digital systems. Edit: McGraw-Hill.

[8] MAITA, William, (2002)

Proyecto de telefonía móvil GSM en la banda

1800 MHz, Región Oriental del país, para la corporación Digitel, C.A. presentado ante la

Universidad Central de Venezuela para optar por el título de Ingeniero electricista mención comunicaciones. [9] M. Hata, “Empirical formula for propagation loss in land mobile radio service,” IEEE Trans. Veh. Technol., vol. VT-29, pp. 317-325, Agosto 1980. [10] SCHMEICHLER, Alejandro, (1996) Simulación en MATLAB de un sistema de telefonía celular digital según las normas IS-54 y GSM, presentado ante la Universidad

Simón Bolívar para optar por el título de Ingeniero Electrónico. [11] GOLDBERG, David (2004) Genetic Algorithms in Search, Optimization, and Machine Learning. E.E.U.U.: Addison-Wesley.

67

[12] JOHNSON, Michael (1999) An Introduction to Genetic Algorithms. Edit: Ramat-Samii. [13] RODRIGUEZ, Ramón (1993) Diseño de un sistema inteligente para cálculos de cobertura de sistemas de comunicaciones móviles, presentado ante la Universidad Simón

Bolívar para optar por el título de Magíster.