Adaptive Cell Tower Location Using Geostatistics. 基于地统计学的适应性基站发射塔选址研究

摘要

In this article, we address the problem of allocating an additional cell tower (or a set of towers) to an existing cellular network, maximizing the call completion probability. Our approach is derived from the adaptive spatial sampling problem using kriging, capitalizing on spatial correlation between cell phone signal strength data points and accounting for terrain morphology. Cell phone demand is reflected by population counts in the form of weights. The objective function, which is the weighted call completion probability, is highly nonlinear and complex (nondifferentiable and discontinuous). Sequential and simultaneous discrete optimization techniques are presented, and heuristics such as simulated annealing and Nelder–Mead are suggested to solve our problem. The adaptive spatial sampling problem is defined and related to the additional facility location problem. The approach is illustrated using data on cell phone call completion probability in a rural region of Erie County in western New York, and accounts for terrain variation using a line-of-sight approach. Finally, the computational results of sequential and simultaneous approaches are compared. Our model is also applicable to other facility location problems that aim to minimize the uncertainty associated with a customer visiting a new facility that has been added to an existing set of facilities.En este articulo se aborda el problema de la localizaciÓn de una (o mÁs) torre(s) de telefonÍa celular adicional(es) en una red existente con el fin de maximizar la probabilidad realizar llamadas (call completion probability). La estrategia general consiste en una derivaciÓn del problema de muestreo espacial adaptativo (adaptive spatial sampling problem) utilizando krijeage (kriging). El mÉtodo propuesto aprovecha la (auto)correlaciÓn espacial presente en una base de datos de puntos que miden la potencia de seÑal, y toma en cuenta las caracterÍsticas morfolÓgicas del terreno. Para representar la demanda de telefonÍa celular, los autores asignan pesos en base a la poblaciÓn del Área de estudio. La funciÓn objetivo del modelo es definida como la probabilidad ponderada de completar una llamada telefÓnica (weighted call completion probability). Se trata de una funciÓn no-lineal y altamente compleja (no diferenciable y discontinua) y para cuya soluciÓn los autores utilizan una tÉcnica de optimizaciÓn discreta secuencial (sequentual and simultaneous discrete optimization), asÍ como mÉtodos heurÍsticos como el recocido simulado (simulated anealing) y el Nelder-Mead. De esta forma, el problema de muestreo espacial adaptativo es definido como y relacionado a el problema de la localizaciÓn de la instalaciÓn adicional (additional facility location problem). Para ilustrar el enfoque general y los mÉtodos propuestos por el estudio, los autores hacen uso de datos de probabilidad de realizar llamadas de telefonÍa celular correspondientes al Área rural del condado de Erie ubicado en el este del estado de Nueva York, E.E.U.U. Para controlar los efectos de la morfologÍa del terreno se realiza un ajuste al mÉtodo mediante la tÉcnica de “lÍnea de visibilidad”(line-of-sight). Como paso final, se lleva a cabo una comparaciÓn de los resultados de los cÁlculos obtenidos por los mÉtodos secuenciales y simultÁneos. El modelo propuesto en este artÍculo tambiÉn es aplicable a otros tipos de problemas de localizaciÓn de instalaciones que tienen por objeto minimizar la incertidumbre en casos similares al que motiva el estudio presente: el caso de un usuario que visita o hace uso de una instalaciÓn nueva que ha sido aÑadida recientemente a la red existente.本文解决了在现有通信基站发射塔网络中添加一个(或一组)基站发射塔，使通话完成率最大化的问题。研究方法源自于采用克里格的自适应空间采样问题，充分利用了手机信号强度数据点集间的空间相关性，并考虑了地形形态。手机需求量由人口数量以权重形式加以反映。目标函数为加权的最大通话完成率，它具有很高的非线性和复杂度（即不可微和非连续）。采用序贯和同步的离散优化方法以及诸如模拟退火法和Nelder-Mead一类的探索性方法来解决该问题。论文对自适应空间采样问题进行了定义，并将其与设施添加的选址问题相关联。以可视通路方法解释地形变化，采用纽约州西部伊利县农村地区的通话完成率观测数据为例对该方法进行说明。最后还对比了序贯的和同步的离散优化技术的计算结果。所构建的模型也适用于以在一组现有设施中添加新设施所导致的用户访问不确定性最小化为目标的其他设施选址问题。