Localización de antenas wifi y de telefonía móvil

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías de Telecomunicación Localización de antenas wifi y de telefonía móvil Autor: Kevin Hernández Díaz Tutor: Juan Antonio Mesa López-Colmenar Dep. Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2016 iii Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías de Telecomunicación Localización de antenas wifi y de telefonía móvil Autor: Kevin Hernández Díaz Tutor: Juan Antonio Mesa López-Colmenar Catedrático de Universidad Dep. Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2016 v Trabajo Fin de Grado: Localización de antenas wifi y de telefonía móvil Autor: Kevin Hernández Díaz Tutor: Juan Antonio Mesa López- Colmenar El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2016 El Secretario del Tribunal vii A mi familia A mis amigos . ix "Any sufficiently advanced technology is indistinguishable from magic." - Arthur C. Clarke - 8 Anexos 47 A: Código Base 49 B: Mejora 1 65 C: Mejora 2 79 D: Mejora 3 97 xvii Índice de Figuras Figura 1-1. Distribución del tiempo medio empleado en redes sociales por plataforma. 2 Figura 1-2. Tráfico global de datos móviles entre 2015-2020 3 Figura 3-1. Tipos de cobertura 9 Figura 3-2. Grosor de los arcos I 10 Figura 3-3. Grosor de los arcos II 10 Figura 3-4. Tipos de cortes 11 Figura 4-1. Escenario ejemplo 14 Figura 4-2. Diagrama de flujo del algoritmo base 17 Figura 5-1. Escenario cálculo computacional 21 Figura 5-2. Solución fija inicial Código Base 22 Figura 5-3. Solución aleatoria inicial Código Base caso 1 22 Figura 5-4. Solución aleatoria final Código Base caso 1 23 Figura 5-5. Solución fija final Código Base caso 1 23 Figura 5-6. Solución aleatoria inicial Código Base caso 2 23 Figura 5-7. Solución aleatoria final Código Base caso 2 24 Figura 5-8. Solución fija final Código Base caso 2 24 Figura 5-9. Solución aleatoria inicial Código Base caso 3 24 Figura 5-10. Solución aleatoria final Código Base caso 3 25 Figura 5-11. Solución fija final Código Base caso 3 25 Figura 5-12. Solución aleatoria inicial Código Base caso 4 25 Figura 5-13. Solución aleatoria final Código Base caso 4 26 Figura 5-14. Solución fija final Código Base caso 4 26 Figura 5-15. Solución fija inicial Código Mejora 1 26 Figura 5-16. Solución aleatoria inicial Código Mejora 1 caso 1 27 Figura 5-17. Solución aleatoria final Código Mejora 1 caso 1 27 Figura 5-18. Solución fija final Código Mejora 1 caso 1 27 Figura 5-19. Solución aleatoria inicial Código Mejora 1 caso 2 28 Figura 5-20. Solución aleatoria final Código Mejora 1 caso 2 28 Figura 5-21. Solución fija final Código Mejora 1 caso 2 28 Figura 5-22. Solución aleatoria inicial Código Mejora 1 caso 3 29 Figura 5-23. Solución aleatoria final Código Mejora 1 caso 3 29 Figura 5-24. Solución fija final Código Mejora 1 caso 3 29 Figura 5-25. Solución aleatoria inicial Código Mejora 1 caso 4 30 Figura 5-26. Solución aleatoria final Código Mejora 1caso 4 30 Figura 5-27. Solución fija final Código Mejora 1 caso 4 30 Figura 5-28. Solución fija inicial Código Mejora 2 31 Figura 5-29. Solución aleatoria inicial Código Mejora 2 caso 1 31 Figura 5-30. Solución aleatoria final Código Mejora 2 caso 1 32 Figura 5-31. Solución fija final Código Mejora 2 caso 1 32 Figura 5-32. Solución aleatoria inicial Código Mejora 2 caso 2 32 Figura 5-33. Solución aleatoria final Código Mejora 2 caso 2 33 Figura 5-34. Solución fija final Código Mejora 2 caso 2 33 Figura 5-35. Solución aleatoria inicial Código Mejora 2 caso 3 33 Figura 5-36. Solución aleatoria final Código Mejora 2 caso 3 34 Figura 5-37. Solución fija final Código Mejora 2 caso 3 34 Figura 5-38. Solución aleatoria inicial Código Mejora 2 caso 4 34 Figura 5-39. Solución aleatoria final Código Mejora 2 caso 4 35 Figura 5-40. Solución fija final Código Mejora 2 caso 4 35 Figura 5-41. Solución fija inicial Código Mejora 3 35 Figura 5-42. Solución aleatoria inicial Código Mejora 3 caso 1 36 Figura 5-43. Solución aleatoria final Código Mejora 3 caso 1 36 Figura 5-44. Solución fija final Código Mejora 3 caso 1 36 Figura 5-45. Solución aleatoria inicial Código Mejora 3 caso 2 37 Figura 5-46. Solución aleatoria final Código Mejora 3 caso 2 37 Figura 5-47. Solución fija final Código Mejora 3 caso 2 37 Figura 5-48. Solución aleatoria inicial Código Mejora 3 caso 3 38 Figura 5-49. Solución aleatoria final Código Mejora 3 caso 3 38 Figura 5-50. Solución fija final Código Mejora 3 caso 3 38 Figura 5-51. Solución aleatoria inicial Código Mejora 3 caso 4 39 Figura 5-52. Solución aleatoria final Código Mejora 3 caso 4 39 Figura 5-53. Solución fija final Código Mejora 3 caso 4 39 xix 1 1 INTRODUCCIÓN a aparición de los Smartphone ha revolucionado el uso de la telefonía móvil en los últimos años. En 2014 la penetración de este servicio alcanzaba las 95,5 líneas por cada 100 habitantes, por lo que existían casi tantas líneas móviles como habitantes del planeta. El crecimiento de la telefonía móvil ha estado liderado por los países en vías de desarrollo, países en los que la penetración ha crecido 21,7 puntos porcentuales entre 2010 y 2014 [1]. Sin embargo, el aspecto más notable de esta revolución se encuentra en el uso del internet móvil, siendo el servicio de comunicaciones que más ha crecido entre 2010 y 2014, con una tasa de crecimiento anual compuesto del 29%. Europa, América y la región CIS son las que alcanzan mayores niveles de penetración de la banda ancha móvil [1]. Solamente en España, a nivel de equipamiento individual, el Smartphone es el dispositivo electrónico que mayor penetración alcanza (59,3%). Siendo el porcentaje de hogares que disponen de telefonía móvil el primer trimestre de 2014 del 95,3% y entre la población de 15 años y más este porcentaje alcanza el 87,8%. La conexión a Internet a través del teléfono móvil es utilizada por ocho de cada diez hogares mientras que el acceso a través de tablets alcanza al 41% de los hogares [1]. En la figura 1-2 se muestra una previsión del tráfico de datos a través de las redes móviles desde 2015 al 220 [17]. Este aumento del uso de internet móvil ha ido de la mano del uso de las redes sociales, según “El informe de La sociedad en red” [1]. Participar en redes sociales es uno de los principales usos de Internet de los europeos, ya que el 46% declara acceder a la Red con este fin. En España el 51% de los usuarios de Internet declaran participar en este tipo de servicios. Este desarrollo conjunto ha permitido que las personas estén conectadas en todo momento mediante el uso de diferentes aplicaciones de los Smartphones. Algunas de las principales redes sociales como son Facebook, Twitter o Instagram son superadas en uso por dispositivos móviles frente al ordenador [2]. Tal como muestra la figura 1-1. Sin embargo, no sólo los usuarios individuales se han aprovechado de la situación, en 2014 el 36% de las empresas europeas utilizaban estos servicios, 6 puntos porcentuales más que en 2013. En 2014 el porcentaje de L We are all now connected by the Internet, like neurons in a giant brain. - Stephen Hawking - Introducción 2 las empresas que facilitaba dispositivos portátiles al menos al 20% de sus empleados se situó en el 25% [1]. Además, tal aumento de la demanda de los servicios ha contribuido a la aparición de nuevas operadoras, que junto con el desarrollo tecnológico ha permitido el abaratamiento de los servicios de cara al usuario, lo que ha contribuido a su expansión. Figura 1-1 El uso de los Smartphone ha causado la aparición del negocio de las aplicaciones móviles, en 2015 Apple publicó que los ingresos derivados de las compras de apps de su market en 2015 fue de 10 billones de dólares [3] y, según estudios, para 2017 se espera que las ganancias de las aplicaciones móviles a nivel mundial supere los 77 billones de dólares. [4] Solo en el Google Play Store en Febrero de 2016 había disponibles cerca de 2 millones de aplicaciones, el doble que en 2013 [5]. Este aumento se debe a la oportunidad de mercado y a la competencia por parte de los desarrolladores de aplicaciones que se esfuerzan por sacar aplicaciones más completas y con mejores características que los demás. Este desarrollo masivo de aplicaciones es el principal objetivo y uso tanto de los Smartphones como de la red móvil. En julio de 2016 'Pokemon Go' una aplicación lanzada ese mismo mes se convirtió en una de las palabras más buscadas de la red por el buscador google [6], convirtiéndose en un fenómeno mundial que saturó los servidores de la compañía y, por consiguiente, produjo un aumento importante en el uso de la red móvil. 3 3 Localización de antenas wifi y de telefonía móvil Este desarrollo ha llevado a las operadoras a fortalecer sus infraestructuras para aguantar la demanda creciente de los usuarios, tanto en los entornos urbanos como en las carreteras interurbanas ya que el teléfono móvil se ha convertido en el principal método de distracción para los viajes largos, tanto para los pasajeros haciendo uso de las redes sociales o juegos, como de los conductores que lo utilizan tanto para GPS, aplicaciones de música o podcasts, que van sustituyendo a la radio. Figura 1-2 Como vemos en la figura 1-2, el tráfico de datos previsto para los próximos años crece de forma exponencial, esto supone el desarrollo y despliegue de una tecnología por parte de las operadoras capaz de facilitar a los usuarios esas capacidades. En 2013 empezó el despliegue de la red 4g en España por parte de las principales operadoras con el objetivo de proporcionar unas velocidades que satisficieran las demandas y a su vez una mejora en la eficiencia en el uso de las bandas de frecuencia que les corresponde, permitiendo así una mejora tanto para los usuarios como para las empresas. Sin embargo, no fue hasta la liberación de la banda de 800 MHz por parte de la industria televisiva que las operadoras pudieron aprovechar el potencial de las redes 4g, que se había visto limitada en su expansión a los núcleos urbanos más importantes. Así comenzó el despliegue de la red 4g+ que permitía a las operadoras extender el radio de cobertura al usar la banda de los 800Mhz, que al tener una menor frecuencia de trabajo permitía un mayor alcance y mejor cobertura en interiores que con las bandas de 1.800 MHz o 2.600 MHz utilizadas antes. Además de un mayor ancho de banda al tener otra banda de frecuencia añadida [7]. Introducción 4 Ya se está investigando sobre la siguiente generación de telefonía, las redes 5g. Sin embargo, no se espera que esta nueva red se empiece a desplegar hasta el 2020 [8]. Mientras tanto las operadoras tienen otras opciones para mejorar los servicios ya existentes, una de estas soluciones son las llamadas micro células, que consiste en la instalación de antenas de corto alcance para dar mayor cobertura a una determinada zona. Este tipo de tecnología serviría para dar mayor potencia a zonas puntuales con una mayor demanda como son las playas en verano o por ejemplo los estadios. Esta tecnología a pesar de tener un coste material bajo, se dificulta debido a que los costes de permisos de instalación en tejados y otras zonas son muy caros. De aquí se deriva la importancia de este trabajo, intentar optimizar el rango de cobertura proporcionado por una antena en una región reduciría la necesidad de instalación de este tipo de antenas temporales así como proporcionar una mayor velocidad a los usuarios. De eso se deriva un ahorro monetario por parte de la operadora, así como una mejora en la imagen de cara al público al proporcionar un mejor servicio a sus usuarios en cuanto a cobertura y velocidad. Además, si nuestra red es suficientemente potente podemos vender parte de nuestra capacidad a otra operadora menor. Por lo tanto el análisis de la localización de las antenas de telefonía móvil es la piedra angular sobre la que recae la operadora. 5 2 ANTECEDENTES continuación se expondrán otros trabajos relacionados con el análisis de cobertura de un sistema. No se pretende una revisión exhaustiva del asunto, sino mostrar brevemente otras técnicas estudiadas para la aproximación a este tipo de problemas, tanto de telefonía móvil como con otro fin. Uno de los pilares fundamentales de este tipo de artículos es el modelo desarrollado por Church y ReVelle [9], Maximal Covering Location Problem (MCLP), en especial los algoritmos GA y GAS. Este modelo ha probado ser uno de los más útiles tanto teóricamente como desde un punto de vista práctico.  Greedy Adding (GA) Algorithm: este algoritmo parte de una solución vacía y va colocando instalaciones una a una en aquel sitio que cubre la mayor cantidad de población que no cubra la anterior instalación, continuando este proceso hasta que todas las instalaciones se hayan colocado o se cubra toda la población. Este algoritmo es óptimo en el caso de una única instalación, sin embargo para mas instalaciones no es seguro que sea la solución óptima, ya que una instalación colocada al principio del proceso puede no estar justificada más adelante.  Greedy Adding with Substitution (GAS): este algoritmo usa el mismo proceso que el GA, pero en cada interacción comprueba que cada una de las instalaciones ya colocadas no mejore la solución al cambiarla a otro sitio libre, si este es el caso cambia dicha instalación al sitio con la mayor mejora del objetivo y continúa el proceso.  Linear Programming: es posible usar la programación lineal para MCLP, sólo hay que restringir que las variables no puedan ser negativas. Siendo los resultados posibles de las variables: Todas ceros o unos, en cuyo caso se ha alcanzado el óptimo, o que algunas variables sean racionales decimales o mayor que 1, en cuyo caso se deberá aplicar distintos métodos para hallar una solución del tipo cero o uno, por ejemplo mediante Branch & Bound. En el artículo sobre el cual se ha basado este trabajo [10], se propone otra aproximación al problema de la localización de estaciones base. En este método se considera que la demanda está sobre nodos que representan la demanda de una zona o sobre los arcos que representan una demanda en movimiento. Para la solución de este problema los autores desarrollaron un nuevo algoritmo (GPAH - Greedy paired adding heuristic) basado en MCLP. En este algoritmo se busca localizar un par de estaciones base dentro de los sitios candidatos para maximizar la función objetivo considerando que un arco cubierto parcialmente no mejora el resultado. A Getting information off the Internet is like taking a drink from a fire hydrant. - Mitchell Kapor - Algoritmo 12 13 4 IMPLEMENTACIÓN n este capítulo vamos a describir como hemos implementado el algoritmo en un programa para la realización de cálculos computacionales. Hemos realizado 4 códigos, el código base el cual hemos realizado basándonos en el algoritmo explicado en el artículo y 3 mejoras sobre este código que hemos considerado interesantes para ampliar sus funcionalidades. 4.1. Código base La implementación del protocolo se ha hecho en MATLAB mediante el uso de dos funciones, principal.m que se encarga de realizar el algoritmo principal y optimiza.m que se encarga de calcular el resultado de la función objetivo. La función principal toma como argumentos:  X: matriz de 𝑛𝑥2 elementos con las coordenadas origen y destino de los arcos de la red sobre el eje x. Donde n es el número de arcos del sistema.  Y: matriz de 𝑛𝑥2 elementos con las coordenadas origen y destino de los arcos de la red sobre el eje y. Donde n es el número de arcos del sistema.  Demand: vector de 𝑛 elementos con las demandas de los arcos  Radio: longitud del radio de cobertura de las estaciones base  Single: peso de la cobertura simple  Double: peso de la cobertura doble  Triple: peso de la cobertura triple  nBS: número de estaciones base a colocar  xBS (opcional): vector inicial con las coordenadas de las N-1 estaciones base.  yBS (opcional): vector inicial con las coordenadas de las N-1 estaciones base. Un ejemplo de los parámetros para generar el escenario de la figura 4-1 sería: principal([1 14; 1 8], [1 1; 1 14], [60 90], 2, 100, 0, 0, 2, [5 10], [9 2]) A partir de las matrices X e Y se genera un plano limitado por los valores máximos y mínimos de ambas matrices. A continuación generamos sobre el plano puntos equiespaciados que serán las posibles localizaciones de las estaciones base. En la figura 4-1 se muestra un escenario de ejemplo en el que tenemos 2 arcos y hemos definido la distancia entre los puntos potenciales como 0.5 unidades del plano. E Implementación 14 Figura 4-1 Para la realización de este método necesitamos partir de una solución inicial con 𝑁−1 estaciones base, para ello utilizamos los argumentos xBS e yBS. Sin embargo, si se llama a la función sin estos parámetros o la longitud del vector no es 𝑁−1, se advertirá al usuario y se le preguntará como desea introducir la solución inicial. Los métodos implementados son:  Introducción de un vector xBS y un vector yBS: Se le pedirá al usuario que introduzca un vector de Matlab de 𝑁−1 elementos primero para el vector xBS y luego para el vector yBS, en el caso de introducir un vector de diferentes dimensiones saltará un error y terminará el programa. Una vez introducidos los vectores de forma correcta el programa colocará las estaciones en los puntos potenciales más cercanos a las coordenadas introducidas y luego continuará automáticamente.  Introducción gráfica de las estaciones base: Se generará una figura con el plano de la red y se le pedirá al usuario que marque 𝑁−1 puntos sobre este mapa. Con este método no cabe la posibilidad de que el usuario marque un número menor o mayor de puntos. Una vez introducida la cantidad necesaria el programa colocará las estaciones en los puntos potenciales más cercanos a las coordenadas introducidas y luego continuará automáticamente.  Solución aleatoria: si el usuario elige esta opción se generaran dos vectores aleatorios de manera independiente donde los resultados estarán comprendidos entre el mínimo y el máximo valor de las coordenadas de los arcos del plano. Cabe resaltar que aunque en el algoritmo principal no se contempla la posibilidad de que dos estaciones base sean colocadas en un mismo punto del plano, en la solución inicial si se permite esta posibilidad ya que mediante la ejecución del programa se corregirá este aspecto. Como hemos dicho este método tiene un enfoque puramente geométrico, por lo que necesitaremos las ecuaciones de las rectas que representan los arcos y las circunferencias centradas en las coordenadas de las estaciones base que representan los radios de las antenas. Para conseguir esto calculamos primero las pendientes de la rectas como la diferencia entre las coordenadas origen y destino del eje y de las rectas por cada unidad en el eje x. Una vez conseguida la pendiente calculamos el punto de corte con el origen usando la ecuación de la recta. 𝑦1=𝑚𝑥+𝑛 15 Localización de antenas wifi y de telefonía móvil Estos valores los guardamos en los vectores pendiente y origen respectivamente. Si quisiéramos acceder a toda la información del arco i solo tendríamos que hacer: x(i,1), x(i,2), y(i,1), y(i,2), demand(i), pendiente(i), origen(i). A continuación tenemos que calcular los puntos de cortes de las circunferencias de cobertura de las antenas con cada uno de los arcos del plano, para ello hacemos uso de un bucle anidado de tal forma que, para cada estación k, se calcule los puntos de cortes con todos los arcos. Para llevar a cabo esto calculamos la semicircunferencia superior e inferior de la estación base en cada iteración de k, haciendo uso de la siguiente ecuación. 𝑦2=+√𝑟2−(𝑥𝑎𝑢𝑥 −𝑎)2+𝑏 Donde 𝑥𝑎𝑢𝑥 es un vector auxiliar de 1000 unidades que va desde 𝑥𝐵𝑆(𝑘)−𝑟𝑎𝑑𝑖𝑜 hasta 𝑥𝐵𝑆(𝑘)+𝑟𝑎𝑑𝑖𝑜, 𝑎 es el valor 𝑥𝐵𝑆(𝑘) y 𝑏 es el valor 𝑦𝐵𝑆(𝑘). Calculamos así la semicircunferencia superior e inferior de la antena. Una vez conseguidas ambas semicircunferencias, vamos generando iteración a iteración el vector 𝑦𝑎𝑢𝑥 del arco i haciendo uso de la ecuación de la recta usando el mismo vector auxiliar 𝑥𝑎𝑢𝑥. Para averiguar las coordenadas de los puntos de corte restamos tanto a la semicircunferencia superior como a la inferior los valores de 𝑦𝑎𝑢𝑥 , hallando la posicion p del primer elemento del vector solución que es cero o cambia de signo y guardamos en las matrices cortesX y cortesY los valores de 𝑥𝑎𝑢𝑥(p) e 𝑦2(p) respectivamente. Se tiene en cuenta que ambos puntos de corte pueden pertenecer a una misma semicircunferencia, por lo cual se comprobará que no haya más cambios de signos. Recordemos que una estación base puede tener cero, uno o dos cortes con cada arco. Al generar los vectores 𝑦𝑎𝑢𝑥 del arco mediante la ecuación de la recta y el vector 𝑥𝑎𝑢𝑥, los puntos de corte encontrados podrían no estar incluidos en el arco. Dicho esto una vez tenemos los puntos de corte, en el caso que tengamos uno o dos puntos, comprobamos que éstos están dentro del rango origen y destino del arco, podemos realizar la comprobación o bien con las coordenadas Y o con las X. No hacen falta comprobar ambas puesto que se han calculado los puntos usando la ecuación de la recta. Se pueden dar los siguientes casos:  Ambos puntos de cortes están dentro del rango origen y destino: significa que ambos puntos de corte forman parte de un sub-segmento del arco.  Sólo un punto de corte está dentro del rango origen y destino: significa que la circunferencia de la estación sólo corta al arco en un punto, por lo tanto procederemos a cambiar el punto de corte que no está incluido en el arco por la coordenada origen o destino que se encuentren dentro del área de la circunferencia.  Ninguno de los puntos están dentro del rango. De aquí se derivan dos opciones: o El arco se encuentra fuera del área de cobertura de la antena. En este caso se borrarán los valores introducidos en las matrices cortesX y cortesY. o El arco es lo suficientemente pequeño como para estar incluido en su totalidad en el área de cobertura de la antena. En este caso los puntos de cortes serán los puntos origen y destino del arco. Una vez rellenadas las matrices cortesX y cortesY hallamos la solución de la función objetivo, para ello llamamos a la función optimiza.m. La función optimiza.m tiene los siguientes argumentos:  cortesX: matriz con las coordenadas X de los puntos de corte de las circunferencias de cobertura de las estaciones con los arcos Implementación 16  cortesY: matriz con las coordenadas Y de los puntos de corte de las circunferencias de cobertura de las estaciones con los arcos  single - peso de la cobertura simple  double - peso de la cobertura doble  triple - peso de la cobertura triple  demand - vector con las demandas de los arcos Esta función coge los puntos de corte de un arco y calcula la proporción del arco con cobertura simple, doble y triple y halla la demanda cubierta usando la siguiente ecuación 𝑟𝑒𝑠𝑢𝑙𝑡𝑎𝑑𝑜 = ∑∑𝑋𝑖𝑘 𝑙𝑘 3 𝑖=1 𝐾 𝑘=1 ∗𝛼𝑖∗𝑑𝑒𝑚𝑎𝑛𝑑𝑘 Siendo 𝑋𝑖𝑘 la longitud del arco k cubierta con cobertura i, 𝑙𝑘 la longitud total del arco k, 𝛼𝑖 el peso de las cobertura simple, doble y triple y 𝑑𝑒𝑚𝑎𝑛𝑑𝑘 la demanda del arco k. El doble sumatorio se corresponde a dos bucles anidados como los utilizados para el cálculo de los puntos de cortes. La proporción 𝑋𝑖𝑘 𝑙𝑘 ⁄ se ha calculado usando la proyección sobre los ejes del segmento formado por los puntos de cortes con respecto a la proyección del arco total y utilizando un vector auxiliar para distinguir las zonas con distinto tipo de cobertura. Una vez obtenido el valor de la función optimiza.m se tiene la solución inicial completa y estamos preparados para realizar el cuerpo del algoritmo. Se ha implementado usando un triple bucle anidado de tal forma que las nBS estaciones recorran todos los puntos de la matriz formada por las coordenadas x e y de las localizaciones potenciales. En cada paso del algoritmo la estación k comprueba que en el siguiente punto sobre el que se va a colocar no haya ninguna estación, en cuyo caso cambia sus coordenadas y calcula sus puntos de cortes y llama a optimiza.m siendo dos posibles situaciones: o bien el resultado obtenido es mejor que el guardado, en cuyo caso guarda la posición actual como la optima temporal, las matrices de los puntos de corte y el nuevo resultado como el optimo temporal, o en caso contrario avanza al siguiente punto. Una vez que una estación base ha recorrido todos los puntos potenciales guarda los óptimos temporales como definitivos y es el turno de la siguiente estación. Una vez que todas las estaciones han sido colocadas tenemos la solución al problema de localización y el programa dibuja una figura con la red, los puntos sobre los cuales se situarán las antenas y el radio de alcance de todas, además en los argumentos de salida se devuelven las coordenadas de las estaciones base (xBS,yBS), el resultado de la optimización y el porcentaje conseguido. La siguiente figura muestra un diagrama de flujo del sistema. 17 Localización de antenas wifi y de telefonía móvil Figura 4-2 4.2. Mejoras Hemos añadido diferentes versiones con mejoras para ampliar la funcionalidad y usos al código base, como la posibilidad de usar diferentes estaciones base que se diferenciarán en el radio de alcance de la antena. Sobre esta mejora añadimos la posibilidad de que el operador tenga ya construidas estaciones base sobre el mapa, en este caso esas estaciones aportan cobertura que hay que tener en cuenta y suponemos el coste de traslado o desmontaje es alto. Implementación 18 También hemos añadido la posibilidad de que el operador quiera asegurar una mínima demanda al finalizar la simulación y ver el coste y número final de estaciones base necesarias. En este caso una vez alcanzada la solución con el número de estaciones base correspondiente se analizará si se cumple el porcentaje de cobertura especificado y en caso contrario añadirá nuevas estaciones hasta que se alcance el objetivo. 4.2.1. Diferentes tipos de estaciones La mejora que hemos incluido en esta versión del programa es la posibilidad de usar estaciones base que se diferencien entre sí en el radio de cobertura que son capaces de suministrar. En cuanto a telefonía móvil, ésta tiene una estructura celular que se dividen entre macro células (15-20Km) para entornos rurales, micro células (1Km) y pico células (<1Km) para entornos urbanos y suburbanos, este radio también varía según el espectro de frecuencias que utiliza, así para una antena 4g es diferente a la red normal instalada, y a su vez la altura de la antena y el entorno también afectan mediante reflexiones, interferencias u obstáculos. En cuanto a antenas wifi este radio varía según la marca de la antena que usemos, la potencia que se le dé, la frecuencia que utilice y también a su vez el entorno, las interferencias, los cuerpos que estén por medio, las características de estos cuerpos... etc. La implementación en el código se ha hecho modificando el parámetro radio de la función principal.m para que sea un vector de n elementos siendo n el número de antenas en el sistema, de forma que para acceder al radio de la antena i, basta con acceder al elemento i de ese vector. 4.2.2. Estaciones fijas En las anteriores versiones del código se consideraba un despliegue total de la red para un operador nuevo, sin embargo la situación normal es que un operador tenga que aumentar el número de estaciones base dentro de un territorio debido al incremento de la demanda de servicios o a la aparición de nuevas tecnologías. O, en el caso de un operador nuevo, que le compre parte de los servicios a otra operadora. En esta versión añadimos la posibilidad de colocar antenas fijas en el mapa. Estas antenas proporcionan cobertura a la red y se consideran fijas, por lo tanto no estarán condicionadas a los lugares potenciales de las nuevas antenas ni entrarán en el algoritmo de colocación en los puntos candidatos, ya que se considera que el coste de mover una torre de telecomunicaciones es demasiado elevado. Para implementar esta mejora se han tenido que añadir 3 parámetros a la función principal.m, esos parámetros son:  xBSfijos: coordenadas del eje x sobre el plano de nuestro sistema de las n estaciones fijas. Vector de 1xn elementos.  yBSfijos: coordenadas del eje y sobre el plano de nuestro sistema de las n estaciones fijas. Vector de 1xn elementos.  radiofijos: vector de 1xn elementos que indican el radio de cobertura de las n estaciones base fijas 19 Localización de antenas wifi y de telefonía móvil La implementación de esta mejora requiere que en la solución inicial del problema cuente con la cobertura dada por estas estaciones fijas, para ellos hemos utilizado el código ya implementado en el código base para calcular los puntos de corte de los radios de cobertura de las estaciones base con los arcos y añadirlos a la matriz cortesx y cortesy para que, cuando se llame a la función optimiza.m para calcular el resultado inicial, cuente con las nuevas antenas. Esta versión incluye la anterior versión, por lo que tanto las nuevas estaciones como las fijas podrán tener radios distintos. 4.2.3. Porcentaje de demanda Uno de los intereses que tiene nuestra aplicación desde el punto de vista de un operador es asegurar que se satisface un cierto porcentaje de la demanda. Entre otras cosas para comprobar que la solución suministrada por el programa cumpla con las metas deseadas. Por ello nuestra última mejora a nuestro código considera que, si a partir de una solución inicial, se encuentra una solución factible que no cumple los requisitos del operador, se irán añadiendo tantas estaciones base como se necesite para cumplir con el objetivo o bien se alcance un valor crítico de antenas. Para la implementación de esta mejora se han añadido dos parámetros a la llamada de la función principal.m, estos son:  porcentaje: porcentaje sobre la demanda total del sistema que se desea asegurar.  exceso: número máximo de estaciones base adicionales que el operador consideraría instalar Una vez terminado el código base, en este caso el código explicado en el apartado anterior, se comprueba la demanda satisfecha, si es menor que el pasado por parámetro se añade una nueva estación base, la cual se colocará en la posición disponible donde maximice la función objetivo, siendo el proceso para calcular el resultado el mismo que el empleado en las anteriores versiones del código. Este proceso se repetirá hasta que el porcentaje requerido sea cumplido o hasta que se alcance el número máximo de estaciones base adicional. Cabe destacar que una vez llegado a esta parte del programa el algoritmo empleado sería el equivalente a usar el algoritmo Greedy Addition durante la iteración n. Este algoritmo, explicado anteriormente, fue expuesto por Church and ReVelle [9] y consiste en la adición progresiva de instalaciones sobre un plano en la posición óptima donde se cubra más cobertura. Como hemos dicho esta versión incluye las anteriores, sin embargo aunque tanto para las estaciones fijas como las nuevas se permite que tengan radios de alcance variables, se considera que las antenas adicionales a instalar en caso de no cumplirse el umbral de la demanda tienen todas el mismo radio, siendo este el máximo de entre las estaciones nuevas a colocar, esto se ha tomado así ya que el objetivo llegados a este punto cubrir la máxima cobertura posible con el menor número de estaciones adicionales. Implementación 20 21 5 CÁLCULO COMPUTACIONAL n este capítulo realizaremos una serie de simulaciones sobre un escenario para demostrar el comportamiento del programa y analizar los distintos resultados obtenidos en consecuencia de los parámetros suministrados. Todas las simulaciones se han realizado con la versión R2013b de MATLAB. El escenario será el mostrado en la figura 5-1, que se codificará en los parámetros x, y y demanda de la función principal.m. El resto de parámetros dependerán de la simulación, se realizarán diferentes casos variando los pesos de la cobertura simple, doble y triple, y por cada caso se realizarán dos experimentos, uno en el que las posiciones de las estaciones base se proporcionarán de forma aleatoria y otro en el que las posiciones sean proporcionadas al comienzo y sean las mismas en todas las simulaciones. Figura 5-1 La figura tiene un tamaño de 15 unidades por 15 unidades, el mallado de los puntos potenciales de colocación de estaciones base se ha considerado cada 0.5 unidades tanto en horizontal como en vertical. El radio de las antenas se ha considerado por defecto de 2 unidades. E Cálculo computacional 28 Figura 5-19 La figura 5-19 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-20 y 5-21 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Figura 5-20 Figura 5-21 5.2.3 Caso 3 En este caso estudiaremos los resultados computacionales del código con la mejora 1 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 20, 60 y 20 respectivamente. 29 Localización de antenas wifi y de telefonía móvil Figura 5-22 La figura 5-22 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-23 y 5-24 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Figura 5-23 Figura 5-24 5.2.4 Caso 4 En este caso estudiaremos los resultados computacionales del código con la mejora 1 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 0, 0 y 100 respectivamente. Cálculo computacional 30 Figura 5-25 La figura 5-25 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-26 y 5-27 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Figura 5-26 Figura 5-27 5.3 Mejora 3: Estaciones fijas En este apartado habrá 4 estaciones base fijas que se cogerán de las 11 estaciones del caso anterior, se usarán dos con radio 1 unidad, una con radio 2 unidades y una con radio 2.5 unidades, la solución inicial usada como constante en todos los casos es la mostrada en la figura 5-28, siendo las estaciones fijas las de color rojo. 31 Localización de antenas wifi y de telefonía móvil Figura 5-28 5.3.1 Caso 1 En este caso estudiaremos los resultados computacionales del código con la mejora 2 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 100, 0 y 0 respectivamente. Figura 5-29 La figura 5-29 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-30 y 5-31 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Cálculo computacional 32 Figura 5-30 Figura 5-31 5.3.2 Caso 2 En este caso estudiaremos los resultados computacionales del código con la mejora 3 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 70, 20 y 10 respectivamente. Figura 5-32 La figura 5-32 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-33 y 5-34 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. 33 Localización de antenas wifi y de telefonía móvil Figura 5-33 Figura 5-34 5.3.3 Caso 3 En este caso estudiaremos los resultados computacionales del código con la mejora 3 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 20, 60 y 20 respectivamente. Figura 5-35 La figura 5-35 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-36 y 5-37 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Cálculo computacional 34 Figura 5-36 Figura 5-37 5.3.4 Caso 4 En este caso estudiaremos los resultados computacionales del código con la mejora 3 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 0, 0 y 100 respectivamente. Figura 5-38 La figura 5-38 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-39 y 5-40 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. 35 Localización de antenas wifi y de telefonía móvil Figura 5-39 Figura 5-40 5.4 Mejora 4: Porcentaje de demanda En este apartado se irá cambiando el porcentaje de demanda requerido en cada caso para obtener un resultado viable sin tener que añadir un número elevado de estaciones base nuevas. El número máximo de estaciones base nuevas a colocar se ha establecido en 5. La figura 5-41 muestra la solución inicial usada como constante en todos los casos. Las nuevas estaciones base añadidas en las soluciones serán representadas de color verde. Figura 5-41 Cálculo computacional 36 5.4.1 Caso 1 En este caso estudiaremos los resultados computacionales del código con la mejora 4 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 100, 0 y 0 respectivamente. El porcentaje de demanda requerido se ha puesto al 80%. Figura 5-42 La figura 5-42 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-43 y 5-44 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Figura 5-43 Figura 5-44 37 Localización de antenas wifi y de telefonía móvil 5.4.2 Caso 2 En este caso estudiaremos los resultados computacionales del código con la mejora 4 en nuestro escenario si los pesos de las coberturas simple, doble y triple son 70, 20 y 10 respectivamente. El porcentaje de demanda requerido se ha puesto al 65%. Figura 5-45 La figura 5-45 mostrada arriba muestra la solución inicial generada de forma aleatoria. Las figuras 5-46 y 5-47 muestran las soluciones finales de las soluciones iníciales aleatoria y fijas respectivamente. Figura 5-46 Figura 5-47 Conclusiones 44 45 7 REFERENCIAS [1] Urueña, Alberto (coord.); Valdecasa, Elena; Ballestero, María Pilar; Ureña, Olga; Castro, Raquel; Cadenas, Santiago. Gobierno de España, Ministerio de Industria, Energía y Turismo, Secretaria de estado de telecomunicaciones y para la sociedad de la información, ONTSI. LA SOCIEDAD EN RED. Informe anual 2014.2015 [2] comScore, 2014, Distribution of times spent on social media sites in the United States in February 2014, by platform, disponible en: http://www.statista.com/statistics/294445/minutes-spent-on-us-media-sites- by-platform/ [3] Apple press info, 2015, disponible en: http://www.apple.com/pr/library/2015/01/08App-Store-Rings-in- 2015-with-New-Records.html [4] Gartner, 2014, by 2017, Mobile Users Will Provide Personalized Data Streams to More Than 100 Apps and Services Every Day, disponible en: http://www.gartner.com/newsroom/id/2654115 [5] Android; Google; App Annie; AppBrain, 2016, disponible en: http://www.statista.com/statistics/266210/number-of-available-applications-in-the-google-play-store/ [6] Google Trends, 2016, disponible en : https://www.google.co.uk/trends/explore?date=today%203- m&q=%22pokemon%20go%22 [7] Vodafone, curiosidades y consejos, cómo se implantó la red 4g, disponible en : https://www.vodafoneteayuda.es/2013/10/como-se-implanto-la-red-4g-de-vodafone/ [8] El mundo, conectividad 5g para el 2020, disponible en : http://www.elmundo.es/tecnologia/2016/02/24/56cdb618e2704e7c2d8b456d.html [9] Church, R.L.; ReVelle, C. The maximal covering location problem. 1974 Regional Science. 30 101-118 [10] Erdemir ET, Batta R, Spielman S, Rogerson PA, Blatt A, Flanigan M. Location coverage models with demand originating from nodes and paths: application to cellular network design. Eur J Oper Res 2008;190:610e32. [11] Akella, M.R.; Batta, R.; Delmelle, E.M.; Rogerson, P.A.; Blatt, A.; Wilson, G. Base station location and channel allocation in a cellular network with emergency coverage requirements. 2005 European Journal of Operational Research. 164 301-323 [12] Berman, O.; Krass, D.; Drezner, Z. The gradual covering decay problem on a network. 2003 European Journal of Operational Research. 151 474-480 [13] Karasakal, O.; Karasakal, E. A maximal covering location model in the presence of partial coverage. 2004 Computers and Operations Research. 31 1515-1526 [14] Murray, Alan; Wei, Ran; Batta, Rajan. A bounding-based solution approach for the continuous arc covering problem (2014). In: Journal of Geographical Systems. RePEc:kap:jgeosy:v:16:y:2014:i:2:p:161- 7 Referencias 46 182. [15] ReVelle, C.S.; Scholssberg, M.; Williamsa, J.: Solving the maximal covering location problem with heuristic concentration. In: Computers & Operations Research 35 (2008), S. 427435 [16] Brandeau, M.L.; Chiu, S.S. An overview of representative problems in location research. 1989 Management Science. 35 645-674 [17] Cisco 2016, Global mobile data traffic from 2015 to 2020 , disponible en : http://www.statista.com/statistics/271405/global-mobile-data-traffic-forecast/ [18] Manuales, ejemplos y programa Matlab: http://es.mathworks.com/matlabcentral/index.html 47 ANEXOS Anexos 48 49 ANEXO A: CÓDIGO BASE principal.m function [ xBS,yBS,resultado1,porcent ] = principal( x,y,demand,npaths,radio,nBS,single,double,triple,xBS2,yBS2,varargin) % se puede llamar como heuristicV4( x,y,xBS,yBS,demand,npaths,radio,nBS,single,double,triple ) % x - matriz de coordenadas origen-destino del eje x de los paths, matriz de n_path * 2 % y - matriz de coordenadas origen-destino del eje y de los paths, matriz de n_path * 2 % demand - vector con las demandas de los paths % n_path - numero de paths en el sistema % radio - radio de las BS % nBS - numero de BS a colocar % single - peso de cobertura simple % double - peso de cobertura doble % triple - peso de cobertura triple % xBS2 - coordenadas del eje x de la solución inicial de las estaciones % base (opcional) % yBS2 - coordenadas del eje y de la solución inicial de las estaciones % base (opcional) % % % Esta funcion lo que hace es recibir las coordenadas del los paths del % mapa, la demanda, el ancho del radio de los Bs, el numero de BS y los % pesos de cobertura simple, dual o triple. % % Ejecuta el algoritmo heuristico, fija las posiciones de n-1 estaciones % base y va cambiando la posicion de la primera BS hasta hallar la % posicion que maximice la funcion objetivo y reitera con las siguientes % BS. % argumentos: x,y,x_pot,y_pot,demand,n_paths,radio,nBS,single,double,triple %% Anexo A: Código Base 50 %creamos la malla para las posibles posiciones de las BSs paso=0.5; %% %para hayar las rectas de los paths usamos la formula de la recta y=mx+n %pendiente de la recta que une los puntos de un segmento pendiente=(y(:,2)-y(:,1))./(x(:,2)-x(:,1)); %punto de corte en el eje y de la recta que une los puntos de los segmentos origenY=y(:,1)-pendiente.*x(:,1); %como mucho una BS tendra dos puntos de cortes con cada segmento %campos: id de la BS, id del path, 2 puntos de cortes cortesx=zeros(npaths*nBS,4); cortesy=zeros(npaths*nBS,4); %variables auxiliares para guardar el óptimo temporal de la BS cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); %llenamos las matrices con los id de las BS for h=1:nBS cortesx(((h-1)*npaths)+1:npaths*h,1)=h; cortesy(((h-1)*npaths)+1:npaths*h,1)=h; end %% imprimir el escenario figure(1) axis([0 15 0 15]); hold on shg for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end %% Si no se han introducido xBS2 e yBS2 pedimos que se introduzcan if(nargin==9) 51 Localización de antenas wifi y de telefonía móvil disp('No has introducido los vectores de posicion de las BS, como quieres continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([0,30],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([0,30],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; Anexo A: Código Base 52 indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else %si se han introducido xBs e yBS se comprueba que las longitudes %sean correctas if(length(xBS2)~=(nBS-1) || length(yBS2)~=(nBS-1)) warning('los vectores yBS y xBS no tienen dimensiones correctas, como quiere continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([min(min(x))*2,max(max(x))*2],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([min(min(y))*2,max(max(y))*2],1,nBS-1)/2; 53 Localización de antenas wifi y de telefonía móvil elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else xBS=[xBS2 0]; yBS=[yBS2 0]; end end %se imprime sobre el esscenario la solución inicial for ej2=1:nBS-1 impXBS=xBS(ej2)-radio:0.001:xBS(ej2)+radio; impYBS1=sqrt(radio^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); end Anexo A: Código Base 60 de %corte excede los limites del path y ponerlo como el %punto extremo aux4=abs(xBS(ii)-x(jj,1)); aux5=abs(xBS(ii)-x(jj,2)); if(aux4==min([aux4 aux5])) cortesx(indice,4)=x(jj,1); cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) extremo=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(extremo(1)==1) cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) extremo=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(extremo(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path 61 Localización de antenas wifi y de telefonía móvil end indice=indice+1; end %calculamos el resultado en ese punto resultado2=optimiza(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %si el resultado en este punto es mayor que el guardado, %sobreescribe los datos if(resultado2>resultado1) resultado1=resultado2; xBSdef=gx; yBSdef=gy; cortesxdef=cortesx((ii*npaths-npaths+1):(ii*npaths),3:4); cortesydef=cortesy((ii*npaths-npaths+1):(ii*npaths),3:4); end end end end %cuando llegamos al punto final guardamos la posicion del óptimo xBS(ii)=xBSdef; yBS(ii)=yBSdef; cortesx((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesxdef; cortesy((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesydef; cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); end %% imprimir el mallado figure(2) hold on axis([0,15,0,15]); shg Anexo A: Código Base 62 for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',3); end shg %imprimimos las BS y sus radios for ej2=1:nBS impXBS=xBS(ej2)-radio:0.001:xBS(ej2)+radio; impYBS1=sqrt(radio^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); end plot(xBS(:),yBS(:),'*') hold off porcent=resultado1/sum(demand); end optimiza.m function resultado=optimiza(x,y,cortesx,cortesy,npaths,demanda,single,double,triple) resultado=0; for k=1:npaths if((max(x(k,:))-min(x(k,:)))<0.2) inicio=min(y(k,:)); final=max(y(k,:)); t=linspace(inicio,final,10001); control=zeros(1,length(t)); linea=cortesy(cortesy(:,2)==k,:); else inicio=min(x(k,:)); final=max(x(k,:)); t=linspace(inicio,final,10001); control=zeros(1,length(t)); linea=cortesx(cortesx(:,2)==k,:); 63 Localización de antenas wifi y de telefonía móvil end for n=1:length(linea(:,1)) if(linea(n,3)~=0 && linea(n,4)~=0) indicebajo=find(t>=min(linea(n,3:4)),1); indicealto=find(t>=max(linea(n,3:4)),1); control(indicebajo:indicealto)=control(indicebajo:indicealto)+1; end end % cobertura simple aux=sum(control>0); resultado=resultado+(aux/length(t))*demanda(k)*(single/100); %cobertura doble aux=sum(control>1); resultado=resultado+(aux/length(t))*demanda(k)*(double/100); %cobertura triple aux=sum(control>2); resultado=resultado+(aux/length(t))*demanda(k)*(triple/100); end end Anexo A: Código Base 64 65 ANEXO B: MEJORA 1 DISTINTOS RADIOS principal.m function [ xBS,yBS,resultado1,porcent ] = principal( x,y,demand,npaths,radio,nBS,single,double,triple,xBS2,yBS2,varargin) % se puede llamar como heuristicV4( x,y,xBS,yBS,demand,npaths,radio,nBS,single,double,triple ) % x - matriz de coordenadas origen-destino del eje x de los paths, matriz de n_path * 2 % y - matriz de coordenadas origen-destino del eje y de los paths, matriz de n_path * 2 % demand - vector con las demandas de los paths % n_path - numero de paths en el sistema % radio - radio de las BS vector de nBS elementos % nBS - numero de BS a colocar % single - peso de cobertura simple % double - peso de cobertura doble % triple - peso de cobertura triple % xBS2 - coordenadas del eje x de la solución inicial de las estaciones % base (opcional) % yBS2 - coordenadas del eje y de la solución inicial de las estaciones % base (opcional) % % % Esta funcion lo que hace es recibir las coordenadas del los paths del % mapa, la demanda, el ancho del radio de los Bs, el numero de BS y los % pesos de cobertura simple, dual o triple. % % Ejecuta el algoritmo heuristico, fija las posiciones de n-1 estaciones % base y va cambiando la posicion de la primera BS hasta hallar la % posicion que maximice la funcion objetivo y reitera con las siguientes % BS. % argumentos: x,y,x_pot,y_pot,demand,n_paths,radio,nBS,single,double,triple %% Anexo B: Mejora 1 distintos radios 66 %creamos la malla para las posibles posiciones de las BSs paso=0.5; %% %para hayar las rectas de los paths usamos la formula de la recta y=mx+n %pendiente de la recta que une los puntos de un segmento pendiente=(y(:,2)-y(:,1))./(x(:,2)-x(:,1)); %punto de corte en el eje y de la recta que une los puntos de los segmentos origenY=y(:,1)-pendiente.*x(:,1); %como mucho una BS tendra dos puntos de cortes con cada segmento %campos: id de la BS, id del path, 2 puntos de cortes cortesx=zeros(npaths*nBS,4); cortesy=zeros(npaths*nBS,4); %variables auxiliares para guardar el óptimo temporal de la BS cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); %llenamos las matrices con los id de las BS for h=1:nBS cortesx(((h-1)*npaths)+1:npaths*h,1)=h; cortesy(((h-1)*npaths)+1:npaths*h,1)=h; end %% imprimir el escenario figure(1) axis([0 15 0 15]); hold on shg for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end %% Si no se han introducido xBS2 e yBS2 pedimos que se introduzcan if(nargin==9) 67 Localización de antenas wifi y de telefonía móvil disp('No has introducido los vectores de posicion de las BS, como quieres continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([0,30],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([0,30],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; Anexo B: Mejora 1 distintos radios 68 indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else %si se han introducido xBs e yBS se comprueba que las longitudes %sean correctas if(length(xBS2)~=(nBS-1) || length(yBS2)~=(nBS-1)) warning('los vectores yBS y xBS no tienen dimensiones correctas, como quiere continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([min(min(x))*2,max(max(x))*2],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([min(min(y))*2,max(max(y))*2],1,nBS-1)/2; 69 Localización de antenas wifi y de telefonía móvil elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else xBS=[xBS2 0]; yBS=[yBS2 0]; end end %se imprime sobre el esscenario la solución inicial for ej2=1:nBS-1 impXBS=xBS(ej2)-radio(ej2):0.001:xBS(ej2)+radio(ej2); impYBS1=sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); end Anexo B: Mejora 1 distintos radios 76 cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path end indice=indice+1; end %calculamos el resultado en ese punto 77 Localización de antenas wifi y de telefonía móvil resultado2=optimiza_mio(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %si el resultado en este punto es mayor que el guardado, %sobreescribe los datos if(resultado2>resultado1) resultado1=resultado2; xBSdef=gx; yBSdef=gy; cortesxdef=cortesx((ii*npaths-npaths+1):(ii*npaths),3:4); cortesydef=cortesy((ii*npaths-npaths+1):(ii*npaths),3:4); end end end end %cuando llegamos al punto final guardamos la posicion del óptimo xBS(ii)=xBSdef; yBS(ii)=yBSdef; cortesx((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesxdef; cortesy((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesydef; cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); end %% imprimir el mallado figure(2) hold on axis([0,15,0,15]); shg for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end shg %% imprimimos la posicion de las BS y sus radios for ej2=1:nBS Anexo B: Mejora 1 distintos radios 78 impXBS=xBS(ej2)-radio(ej2):0.001:xBS(ej2)+radio(ej2); impYBS1=sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); end plot(xBS,yBS,'*'); hold off porcent=resultado1/sum(demand); end 79 ANEXO C: MEJORA 2 ESTACIONES BASE FIJAS principal.m function [ xBS,yBS,resultado1,porcent ] = principal( x,y,demand,npaths,radio,nBS,single,double,triple,xBSfijos,yBSfijos,radiofijos,xB S2,yBS2,varargin) % se puede llamar como heuristicV4( x,y,xBS,yBS,demand,npaths,radio,nBS,single,double,triple ) % x - matriz de coordenadas origen-destino del eje x de los paths, matriz de n_path * 2 % y - matriz de coordenadas origen-destino del eje y de los paths, matriz de n_path * 2 % demand - vector con las demandas de los paths % n_path - numero de paths en el sistema % radio - radio de las BS vector de nBS elementos % nBS - numero de BS a colocar % single - peso de cobertura simple % double - peso de cobertura doble % triple - peso de cobertura triple % xBSfijos - coordenadas del eje x de las estaciones base fijas % yBSfijos - coordenadas del eje y de las estaciones base fijas % xBS2 - coordenadas del eje x de la solución inicial de las estaciones % base (opcional) % yBS2 - coordenadas del eje y de la solución inicial de las estaciones % base (opcional) % % % Esta funcion lo que hace es recibir las coordenadas del los paths del % mapa, la demanda, el ancho del radio de los Bs, el numero de BS y los % pesos de cobertura simple, dual o triple. % % Ejecuta el algoritmo heuristico, fija las posiciones de n-1 estaciones % base y va cambiando la posicion de la primera BS hasta hallar la % posicion que maximice la funcion objetivo y reitera con las siguientes % BS. % argumentos: x,y,x_pot,y_pot,demand,n_paths,radio,nBS,single,double,triple Anexo C: Mejora 2 Estaciones Base Fijas 80 %% %creamos la malla para las posibles posiciones de las BSs paso=0.5; %para hayar las rectas de los paths usamos la formula de la recta y=mx+n %pendiente de la recta que une los puntos de un segmento pendiente=(y(:,2)-y(:,1))./(x(:,2)-x(:,1)); %punto de corte en el eje y de la recta que une los puntos de los segmentos origenY=y(:,1)-pendiente.*x(:,1); %como mucho una BS tendra dos puntos de cortes con cada segmento %campos: id de la BS, id del path, 2 puntos de cortes cortesx=zeros(npaths*nBS,4); cortesy=zeros(npaths*nBS,4); %variables auxiliares para guardar el óptimo temporal de la BS cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); %llenamos las matrices con los id de las BS for h=1:nBS cortesx(((h-1)*npaths)+1:npaths*h,1)=h; cortesy(((h-1)*npaths)+1:npaths*h,1)=h; end %% imprimir el mallado figure(1) axis([0 15 0 15]); hold on shg for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end %% imprimimos la posicion de las BS 81 Localización de antenas wifi y de telefonía móvil if(nargin==12) disp('No has introducido los vectores de posicion de las BS, como quieres continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([0,30],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([0,30],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo Anexo C: Mejora 2 Estaciones Base Fijas 82 aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else %si se han introducido xBs e yBS se comprueba que las longitudes %sean correctas if(length(xBS2)~=(nBS-1) || length(yBS2)~=(nBS-1)) warning('los vectores yBS y xBS no tienen dimensiones correctas, como quiere continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([min(min(x))*2,max(max(x))*2],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base 83 Localización de antenas wifi y de telefonía móvil yBS(1:end-1)=randi([min(min(y))*2,max(max(y))*2],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else xBS=[xBS2 0]; yBS=[yBS2 0]; end end %se imprime sobre el escenario la solución inicial for ej2=1:nBS-1 impXBS=xBS(ej2)-radio(ej2):0.001:xBS(ej2)+radio(ej2); impYBS1=sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); Anexo C: Mejora 2 Estaciones Base Fijas 84 end plot(xBS(1:end-1),yBS(1:end-1),'*') for ej2=1:length(xBSfijos) impXBS=xBSfijos(ej2)-radiofijos(ej2):0.001:xBSfijos(ej2)+radiofijos(ej2); impYBS1=sqrt(radiofijos(ej2)^2-(impXBS-xBSfijos(ej2)).^2)+yBSfijos(ej2); impYBS2=-sqrt(radiofijos(ej2)^2-(impXBS-xBSfijos(ej2)).^2)+yBSfijos(ej2); plot(impXBS,impYBS1,'r'); plot(impXBS,impYBS2,'r'); end plot(xBSfijos,yBSfijos,'r*'); hold off %% empezamos calculando los cortes de las BS colocadas al principio for ii=1:nBS-1 % todos los BS -1 fijos indice=ii*npaths-npaths+1; % cada Bs tiene tantas filas reservadas para ella como paths hay for jj=1:npaths %comprobamos que la estación esta dentro del rango del segmento %para ahorrar tiempo if(yBS(ii)<(max(y(jj,:))+radio(ii)) && yBS(ii)>(min(y(jj,:))-radio(ii))) %comprobamos q esta dentro del rango del segmento if(xBS(ii)<(max(x(jj,:))+radio(ii)) && xBS(ii)>(min(x(jj,:))- radio(ii))) %rango de valores del eje x valoresXBS=xBS(ii)-radio(ii):0.001:xBS(ii)+radio(ii); %segmento del path valoresy=pendiente(jj)*valoresXBS+origenY(jj); valoresYBS1=sqrt(radio(ii)^2-(valoresXBS- xBS(ii)).^2)+yBS(ii); valoresYBS2=-sqrt(radio(ii)^2-(valoresXBS- xBS(ii)).^2)+yBS(ii); %restamos los valores de y y buscamos cuando cambia %de signo aux=sign(valoresYBS1-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); aux3=0; if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); cortesx(indice,2)=jj; 85 Localización de antenas wifi y de telefonía móvil cortesy(indice,2)=jj; if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux)) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS1(pos(1)); aux3=1; else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS1(pos(1)); cortesy(indice,4)=valoresYBS1(pos(end)); aux3=2; end end end % HAY QUE CALCULAR LA PARTE DE ABAJO DE LA CIRCUNFERENCIA if(aux3<2) aux=sign(valoresYBS2-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); if(aux3==0) cortesx(indice,2)=jj; cortesy(indice,2)=jj; end if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux) && aux2>0) if(aux3==1) %consideraciones aqui: %un path siempre va a cortar al radio en dos puntos xq %esta hecho asi, por lo tanto comprobar si un punto de %corte excede los limites del path y ponerlo como el %punto extremo cortesx(indice,4)=valoresXBS(pos(1)); cortesy(indice,4)=valoresYBS2(pos(1)); aux3=2; elseif (aux3==0) Anexo C: Mejora 2 Estaciones Base Fijas 92 aux(aux(1,:)~=1)=0; aux2=sum(aux); aux3=0; if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); cortesx(indice,2)=jj; cortesy(indice,2)=jj; if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux)) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS1(pos(1)); aux3=1; else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS1(pos(1)); cortesy(indice,4)=valoresYBS1(pos(end)); aux3=2; end end end % HAY QUE CALCULAR LA PARTE DE ABAJO DE LA CIRCUNFERENCIA if(aux3<2) aux=sign(valoresYBS2-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); if(aux3==0) cortesx(indice,2)=jj; cortesy(indice,2)=jj; end if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux) && aux2>0) if(aux3==1) %consideraciones aqui: %un path siempre va a cortar al radio en dos puntos xq %esta hecho asi, por lo tanto comprobar si un punto de 93 Localización de antenas wifi y de telefonía móvil %corte excede los limites del path y ponerlo como el %punto extremo cortesx(indice,4)=valoresXBS(pos(1)); cortesy(indice,4)=valoresYBS2(pos(1)); aux3=2; elseif (aux3==0) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS2(pos(1)); aux3=1; end else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS2(pos(1)); cortesy(indice,4)=valoresYBS2(pos(end)); aux3=2; end end end end if(aux3==1) aux4=abs(xBS(ii)-x(jj,1)); aux5=abs(xBS(ii)-x(jj,2)); if(aux4==min([aux4 aux5])) cortesx(indice,4)=x(jj,1); cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(socorro(1)==1) Anexo C: Mejora 2 Estaciones Base Fijas 94 cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path end indice=indice+1; end %calculamos el resultado resultado2=optimiza_mio(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %si el resultado en este punto es mayor que el guardado, %sobreescribe los datos if(resultado2>resultado1) resultado1=resultado2; xBSdef=gx; yBSdef=gy; cortesxdef=cortesx((ii*npaths-npaths+1):(ii*npaths),3:4); cortesydef=cortesy((ii*npaths-npaths+1):(ii*npaths),3:4); end end end 95 Localización de antenas wifi y de telefonía móvil end %cuando llegamos al punto final guardamos la posicion del óptimo xBS(ii)=xBSdef; yBS(ii)=yBSdef; cortesx((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesxdef; cortesy((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesydef; cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); end %% imprimir el mallado figure(2) hold on axis([0,15,0,15]); shg for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end %% imprimimos la posicion de las BS for ej2=1:nBS impXBS=xBS(ej2)-radio(ej2):0.001:xBS(ej2)+radio(ej2); impYBS1=sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); impYBS2=-sqrt(radio(ej2)^2-(impXBS-xBS(ej2)).^2)+yBS(ej2); plot(impXBS,impYBS1); plot(impXBS,impYBS2); end plot(xBS,yBS,'*'); %imprimimos las fijas for ej2=1:length(xBSfijos) impXBS=xBSfijos(ej2)-radiofijos(ej2):0.001:xBSfijos(ej2)+radiofijos(ej2); impYBS1=sqrt(radiofijos(ej2)^2-(impXBS-xBSfijos(ej2)).^2)+yBSfijos(ej2); impYBS2=-sqrt(radiofijos(ej2)^2-(impXBS-xBSfijos(ej2)).^2)+yBSfijos(ej2); plot(impXBS,impYBS1,'r'); plot(impXBS,impYBS2,'r'); end plot(xBSfijos,yBSfijos,'r*'); hold off porcent=resultado1/sum(demand); end Anexo C: Mejora 2 Estaciones Base Fijas 96 97 ANEXO D: MEJORA 3 PORCENTAJE DE DEMANDA principal.m function [ xBS,yBS,resultado1,porcent ] = principal ( x,y,demand,npaths,radio,nBS,single,double,triple,xBSfijos,yBSfijos,radiofijos,po rcentaje,exceso,xBS2,yBS2,varargin) % se puede llamar como heuristicV4( x,y,xBS,yBS,demand,npaths,radio,nBS,single,double,triple ) % x - matriz de coordenadas origen-destino del eje x de los paths, matriz de n_path * 2 % y - matriz de coordenadas origen-destino del eje y de los paths, matriz de n_path * 2 % demand - vector con las demandas de los paths % n_path - numero de paths en el sistema % radio - radio de las BS vector de nBS elementos % nBS - numero de BS a colocar % single - peso de cobertura simple % double - peso de cobertura doble % triple - peso de cobertura triple % xBSfijos - coordenadas del eje x de las estaciones base fijas % yBSfijos - coordenadas del eje y de las estaciones base fijas % porcentaje - porcentaje de demanda minimo a cumplir % exceso - variable de control para indicar el número máximo de estaciones % adicionales a colocar % xBS2 - coordenadas del eje x de la solución inicial de las estaciones % base (opcional) % yBS2 - coordenadas del eje y de la solución inicial de las estaciones % base (opcional) % % % Esta funcion lo que hace es recibir las coordenadas del los paths del % mapa, la demanda, el ancho del radio de los Bs, el numero de BS y los % pesos de cobertura simple, dual o triple. % Anexo D: Mejora 3 Porcentaje de Demanda 98 % Ejecuta el algoritmo heuristico, fija las posiciones de n-1 estaciones % base y va cambiando la posicion de la primera BS hasta hallar la % posicion que maximice la funcion objetivo y reitera con las siguientes % BS. % argumentos: x,y,x_pot,y_pot,demand,n_paths,radio,nBS,single,double,triple %% %creamos la malla para las posibles posiciones de las BSs paso=0.5; %para hayar las rectas de los paths usamos la formula de la recta y=mx+n %pendiente de la recta que une los puntos de un segmento pendiente=(y(:,2)-y(:,1))./(x(:,2)-x(:,1)); %punto de corte en el eje y de la recta que une los puntos de los segmentos origenY=y(:,1)-pendiente.*x(:,1); %como mucho una BS tendra dos puntos de cortes con cada segmento %campos: id de la BS, id del path, 2 puntos de cortes cortesx=zeros(npaths*nBS,4); cortesy=zeros(npaths*nBS,4); %variables auxiliares para guardar el óptimo temporal de la BS cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); %llenamos las matrices con los id de las BS for h=1:nBS cortesx(((h-1)*npaths)+1:npaths*h,1)=h; cortesy(((h-1)*npaths)+1:npaths*h,1)=h; end %% imprimir el mallado %% imprimir el mallado figure(1) axis([0 15 0 15]); hold on shg 99 Localización de antenas wifi y de telefonía móvil for ej=1:npaths plot([x(ej,1) x(ej,2)],[y(ej,1) y(ej,2)],'k','LineWidth',2); end shg %% imprimimos la posicion de las BS if(nargin==14) disp('No has introducido los vectores de posicion de las BS, como quieres continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([0,30],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([0,30],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las Anexo D: Mejora 3 Porcentaje de Demanda 100 dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else %si se han introducido xBs e yBS se comprueba que las longitudes %sean correctas if(length(xBS2)~=(nBS-1) || length(yBS2)~=(nBS-1)) warning('los vectores yBS y xBS no tienen dimensiones correctas, como quiere continuar?'); eleccion=input('Introducir los vectores mediante dos vectores(v), generarlos de forma aleatoria(a) o introducirlos graficamente(g)?: ','s'); xBS=zeros(1,nBS); yBS=zeros(1,nBS); if(eleccion=='g') % se decide introducir los vectores de forma grafica [aux_xBS,aux_yBS]=ginput(nBS-1); xBS(1:(nBS-1))=aux_xBS; yBS(1:(nBS-1))=aux_yBS; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); 101 Localización de antenas wifi y de telefonía móvil aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end elseif(eleccion=='a') %se decide que sea de forma aleatoria xBS(1:end-1)=randi([min(min(x))*2,max(max(x))*2],1,nBS-1)/2; %fijamos las posiciones de nBS-1 estaciones base yBS(1:end-1)=randi([min(min(y))*2,max(max(y))*2],1,nBS-1)/2; elseif(eleccion=='v') %se decide que sea mediante un vector fprintf('introtuce un vector x de %d elementos',nBS-1); temp_vx=input(''); fprintf('introtuce un vector y de %d elementos \n',nBS-1); temp_vy=input(''); if(length(temp_vx)~=(nBS-1) || length(temp_vy)~=(nBS-1)) error('alguno de los vectores introducidos no tiene las dimensiones correctas') else xBS(1:(nBS-1))=temp_vx; yBS(1:(nBS-1))=temp_vy; malladox=0:paso:15; malladoy=0:paso:15; for varaux_bucle=1:(nBS-1) %decide aproximar las coordenadas introducidas al punto mas próximo aux_temp=(malladox-xBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); xBS(varaux_bucle)=malladox(indice_auxliar); aux_temp=(malladoy-yBS(varaux_bucle)).^2; indice_auxliar=(aux_temp==min(aux_temp)); yBS(varaux_bucle)=malladoy(indice_auxliar); end end end else xBS=[xBS2 0]; yBS=[yBS2 0]; end end Anexo D: Mejora 3 Porcentaje de Demanda 108 aux4=abs(xBSfijos(ii)-x(jj,1)); aux5=abs(xBSfijos(ii)-x(jj,2)); if(aux4==min([aux4 aux5])) cortesx(indice,4)=x(jj,1); cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path 109 Localización de antenas wifi y de telefonía móvil end indice=indice+1; end end % imprimimos la primera solucion resultado1=optimiza_mio(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %% algoritmo principal pause; for ii=nBS:-1:1 xBSdef=xBS(ii); yBSdef=yBS(ii); %la primera solución es dejarla en el mismo punto %esto se hace porque aunque cuando en el algoritmo vuelve a su posicion %no mejora nunca la solucion actual, entonces si ese es su optimo tiene %que quedarse ahi for gy=min(min(y)):paso:max(max(y)) %recorremos el mallado for gx=min(min(x)):paso:max(max(x)) %solo entra si no hay otra BS en ese punto if(sum(yBS(xBS==gx)==gy)==0) %solo entra si no hay otra BS en ese punto yBS(ii)=gy; xBS(ii)=gx; %accedemos a la parte correspondiente de la matriz de cortes %ponemos la matriz de cortes correspondiente a la BS a 0 indice=ii*npaths-npaths+1; cortesx(cortesx(:,1)==ii,3:4)=0; cortesy(cortesy(:,1)==ii,3:4)=0; for jj=1:npaths % todos los paths %comprobamos q esta dentro del rango del segmento if(yBS(ii)<(max(y(jj,:))+radio(ii)) && yBS(ii)>(min(y(jj,:))- radio(ii))) %comprobamos q esta dentro del rango del segmento if(xBS(ii)<(max(x(jj,:))+radio(ii)) && xBS(ii)>(min(x(jj,:))-radio(ii))) %creamos el rango de valores del eje x Anexo D: Mejora 3 Porcentaje de Demanda 110 valoresXBS=xBS(ii)-radio(ii):0.001:xBS(ii)+radio(ii); %calculamos los valores y de la recta valoresy=pendiente(jj)*valoresXBS+origenY(jj); valoresYBS1=sqrt(radio(ii)^2-(valoresXBS- xBS(ii)).^2)+yBS(ii); valoresYBS2=-sqrt(radio(ii)^2-(valoresXBS- xBS(ii)).^2)+yBS(ii); %restamos los valores de y y hallamos el punto %donde se cambia el signo aux=sign(valoresYBS1-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); aux3=0; if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); cortesx(indice,2)=jj; cortesy(indice,2)=jj; if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux)) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS1(pos(1)); aux3=1; else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS1(pos(1)); cortesy(indice,4)=valoresYBS1(pos(end)); aux3=2; end end end % HAY QUE CALCULAR LA PARTE DE ABAJO DE LA CIRCUNFERENCIA if(aux3<2) aux=sign(valoresYBS2-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); if(aux3==0) cortesx(indice,2)=jj; cortesy(indice,2)=jj; end 111 Localización de antenas wifi y de telefonía móvil if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux) && aux2>0) if(aux3==1) %consideraciones aqui: %un path siempre va a cortar al radio en dos puntos xq %esta hecho asi, por lo tanto comprobar si un punto de %corte excede los limites del path y ponerlo como el %punto extremo cortesx(indice,4)=valoresXBS(pos(1)); cortesy(indice,4)=valoresYBS2(pos(1)); aux3=2; elseif (aux3==0) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS2(pos(1)); aux3=1; end else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS2(pos(1)); cortesy(indice,4)=valoresYBS2(pos(end)); aux3=2; end end end end if(aux3==1) aux4=abs(xBS(ii)-x(jj,1)); aux5=abs(xBS(ii)-x(jj,2)); if(aux4==min([aux4 aux5])) cortesx(indice,4)=x(jj,1); cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); Anexo D: Mejora 3 Porcentaje de Demanda 112 end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path end indice=indice+1; end %calculamos el resultado resultado2=optimiza_mio(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %si el resultado en este punto es mayor que el guardado, %sobreescribe los datos if(resultado2>resultado1) resultado1=resultado2; 113 Localización de antenas wifi y de telefonía móvil xBSdef=gx; yBSdef=gy; cortesxdef=cortesx((ii*npaths-npaths+1):(ii*npaths),3:4); cortesydef=cortesy((ii*npaths-npaths+1):(ii*npaths),3:4); end end end end %cuando llegamos al punto final guardamos la posicion del óptimo xBS(ii)=xBSdef; yBS(ii)=yBSdef; cortesx((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesxdef; cortesy((ii*npaths-npaths+1):(ii*npaths),3:4)=cortesydef; cortesxdef=zeros(npaths,2); cortesydef=zeros(npaths,2); end %% % HA PARTIR DE AQUI ES LA ULTIMA VERSIÓN xBSad=zeros(1,exceso); yBSad=zeros(1,exceso); ii=0; % se añaden estaciones adicionales hasta que se cumpla el porcentaje o se % alcance el limite de estaciones while((resultado1/sum(demand))<porcentaje && ii<exceso) ii=ii+1; for gy=min(min(y)):paso:max(max(y)) % recorremos el mallado for gx=min(min(x)):paso:max(max(x)) %solo entra si no hay otra BS en ese punto if(sum(yBSad(xBSad==gx)==gy)==0) Anexo D: Mejora 3 Porcentaje de Demanda 114 yBSad(ii)=gy; xBSad(ii)=gx; indice=length(cortesx(:,1))-exceso*npaths+ii*npaths-npaths+1; %accedemos a la parte correspondiente de la matriz de cortes %ponemos la matriz de cortes correspondiente a la BS a 0 cortesx(indice:indice+npaths,3:4)=0; cortesy(indice:indice+npaths,3:4)=0; for jj=1:npaths % todos los paths %comprobamos q esta dentro del rango del segmento if(yBSad(ii)<(max(y(jj,:))+max(radio)) && yBSad(ii)>(min(y(jj,:))-max(radio))) if(xBSad(ii)<(max(x(jj,:))+max(radio)) && xBSad(ii)>(min(x(jj,:))-max(radio))) %creamos el rango de valores del eje x valoresXBS=xBSad(ii)- max(radio):0.001:xBSad(ii)+max(radio); %calculamos los valores y de la recta valoresy=pendiente(jj)*valoresXBS+origenY(jj); valoresYBS1=sqrt(max(radio)^2-(valoresXBS- xBSad(ii)).^2)+yBSad(ii); valoresYBS2=-sqrt(max(radio)^2-(valoresXBS- xBSad(ii)).^2)+yBSad(ii); %restamos los valores de y y hallamos el punto %donde se cambia el signo aux=sign(valoresYBS1-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); aux3=0; if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); cortesx(indice,2)=jj; cortesy(indice,2)=jj; if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux)) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS1(pos(1)); aux3=1; else cortesx(indice,3)=valoresXBS(pos(1)); 115 Localización de antenas wifi y de telefonía móvil cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS1(pos(1)); cortesy(indice,4)=valoresYBS1(pos(end)); aux3=2; end end end % HAY QUE CALCULAR LA PARTE DE ABAJO DE LA CIRCUNFERENCIA if(aux3<2) aux=sign(valoresYBS2-valoresy); aux(aux(1,:)~=1)=0; aux2=sum(aux); if(aux3==0) cortesx(indice,2)=jj; cortesy(indice,2)=jj; end if(aux2<length(aux) && aux2>0) pos=find(aux(1)~=aux); if(size(pos,2)~=0 && size(pos,2)~=1) if(pos(end)==length(aux) && aux2>0) if(aux3==1) %consideraciones aqui: %un path siempre va a cortar al radio en dos puntos xq %esta hecho asi, por lo tanto comprobar si un punto de %corte excede los limites del path y ponerlo como el %punto extremo cortesx(indice,4)=valoresXBS(pos(1)); cortesy(indice,4)=valoresYBS2(pos(1)); aux3=2; elseif (aux3==0) cortesx(indice,3)=valoresXBS(pos(1)); cortesy(indice,3)=valoresYBS2(pos(1)); aux3=1; end else cortesx(indice,3)=valoresXBS(pos(1)); cortesx(indice,4)=valoresXBS(pos(end)); cortesy(indice,3)=valoresYBS2(pos(1)); Anexo D: Mejora 3 Porcentaje de Demanda 116 cortesy(indice,4)=valoresYBS2(pos(end)); aux3=2; end end end end if(aux3==1) aux4=abs(xBSad(ii)-x(jj,1)); aux5=abs(xBSad(ii)-x(jj,2)); if(aux4==min([aux4 aux5])) cortesx(indice,4)=x(jj,1); cortesy(indice,4)=y(jj,1); else cortesx(indice,4)=x(jj,2); cortesy(indice,4)=y(jj,2); end end %resolucion de consideraciones en caso de que solo corte en %un punto if(min(cortesx(indice,3:4))<min(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==min(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=min(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==min(x(jj,:))); else cortesx(indice,4)=min(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==min(x(jj,:))); end end if(max(cortesx(indice,3:4))>max(x(jj,:)) && aux3>0) socorro=cortesx(indice,3:4)==max(cortesx(indice,3:4)); if(socorro(1)==1) cortesx(indice,3)=max(x(jj,:)); cortesy(indice,3)=y(jj,x(jj,:)==max(x(jj,:))); else 117 Localización de antenas wifi y de telefonía móvil cortesx(indice,4)=max(x(jj,:)); cortesy(indice,4)=y(jj,x(jj,:)==max(x(jj,:))); end end end % final de comprobacion del path end indice=indice+1; end end %calculamos el resultado resultado2=optimiza_mio(x,y,cortesx,cortesy,npaths,demand,single,double,triple); %si el resultado en este punto es mayor que el guardado, %sobreescribe los datos if(resultado2>resultado1) resultado1=resultado2; xBSdef=gx; yBSdef=gy; cortesxdef=cortesx((length(cortesx(:,1))- exceso*npaths+ii*npaths-npaths+1):(length(cortesx(:,1))- exceso*npaths+ii*npaths),3:4); cortesydef=cortesy((length(cortesx(:,1))- exceso*npaths+ii*npaths-npaths+1):(length(cortesx(:,1))- exceso*npaths+ii*npaths),3:4); end end end %cuando llegamos al punto final guardamos la posicion del óptimo xBSad(ii)=xBSdef; yBSad(ii)=yBSdef; cortesx((length(cortesx(:,1))-exceso*npaths+ii*npaths- npaths+1):(length(cortesx(:,1))-exceso*npaths+ii*npaths),3:4)=cortesxdef; cortesy((length(cortesx(:,1))-exceso*npaths+ii*npaths- npaths+1):(length(cortesx(:,1))-exceso*npaths+ii*npaths),3:4)=cortesydef; end %% imprimir el mallado figure(2) hold on axis([0,15,0,15]);