The project leading to this application has received funding from the European Union’s Horizon 2020research and innovation programme under grant agreement No 825012.

Priority is claimed to European Patent Application No. EP 20 191 206.0, filed on August 14, 2020, the entire disclosure of which is hereby incorporated by reference herein.

The present invention relates to a computer-implemented method as well as to a computer system for design planning of a cellular network, in particular a 5G-NR network or beyond.

Accurate knowledge of users’ positions is of paramount importance for network operators. Indeed, by means of such piece of information, they may enable themselves or allow over-the-top (OTT) business entities to deliver location-based added-value services in order to increase their revenue sources. Moreover, realtime users’ positions can be exploited to effectively manage the network by performing users’ flow forecasting and proactive resource allocation along the expected users’ trajectories.

Therefore, network-based positioning is gaining more and more interest within the standardization of new cellular network technologies. In particular, positioning has been identified as a paramount characteristic for 5G networks as it supports the tracking of goods and products within kitting processes in manufacturing, helps driving automated guided vehicles (AGVs) in logistic operations or localizes victims and people in distress during rescue procedures. Therefore, 5G networks are expected to offer advanced features to handle it, such as wide bandwidth for time resolution, additional frequency bands and massive Ml MO for the angle-of-arrival calculation. This fosters operators to rely on their own infrastructures to directly obtain such information without using third-party solutions, such as GLONASS, GPS or GALILEO. For instance, 5G-NR will deliver much higher accuracy than the current LTE radio access technology (RAT), due to its higher bandwidth and superior RAT design (cf. R. Keating, M. Saily, J. Hulkkonen and J. Karjalainen, “Overview of Positioning in 5G New Radio”, 2019 16th international Symposium on Wireless Communication Systems (iSWCS), pp. 320-324). However, such improvementswill be only marginal if limited to the enhancement of single-link localization accuracy. Specifically, base station positions play a major role in localization accuracy as a sub-optimal placement may lead to i) high Geometrid Dilution of Precision (GDOP) as the positioning error along each axis depends on the information provided by ranging signals coming from any base station in that direction (cf. I. Sharp, K. Yu and Y. J. Guo, “GDOP Analysis for Positioning System Design”, IEEE Transactions on Vehicular Technology, vol. 58, no. 7, pp. 3371 -3382, Sept. 2009, doi: 10.1109/TVT.2009.2017270), and ii) possibly higher single-link measurement error due to higher path-loss attenuation or fading effects.

Indeed, state-of-the-art radio networks are designed to only optimize throughput (cf. Jyrki T. J. Penttinen, “Planning of the LTE-Advanced Radio Network”, in The L TE- Advanced Deployment Handbook: The Planning Guidelines for the Fourth Generation Networks, Wiley, 2014, pp.257-292) and neglect the User Equipment (UE) location accuracy, thus a paradigm shift is required in classical network design to take into account such a new KPI (Key Performance Indicator).

It is therefore an object of the present invention to improve and further develop a method and a system of the initially described type for design planning of a cellular network in such a way that the positioning accuracy of localizing end-users by means only of network infrastructures is improved so as to allow network operators to deliver additional services to end-users and provide better quality of experience, while keeping reasonable the overall throughput performance.

In accordance with the invention, the aforementioned object is accomplished by a computer-implemented method for optimizing positioning performance of a cellular network, in particular a 5G-NR network or beyond, the method comprising: defining a target area; identifying a set Sof base station deployment candidate sites /within the target area; obtaining, by executing a joint performance optimization routine that aims at jointly optimizing network throughput and positioning performance, wherein a tuning parameter regulates a throughput-positioning ratio of the joint performance optimization routine, active candidate sites as a subset of the set Sof base station deployment candidate sites and determining the obtained active candidate sites as the sites at which base stations are to be deployed.

Furthermore, the aforementioned object is accomplished by a computer system for optimizing positioning performance of a cellular network, in particular a 5G-NR network or beyond, the system comprising memory and one or more processors which, alone or in combination, are configured to provide for execution of the above method

The aforementioned object is also accomplished by a tangible, non-transitory computer-readable medium having instructions thereon, which upon execution by one or more processors, alone or in combination, provide for execution of the above method for optimizing positioning performance of a cellular network, in particular a 5G-NR network or beyond.

Embodiments of the present invention provide a cellular network design solution that pursues jointly localization accuracy and user throughput. More specifically, embodiment of the invention provide a solution for 5G (and beyond) network design that improves network-based localization performances by taking into account both user throughput, fairness and positioning KPIs (Key Performance Indicators).

Embodiments of the present invention provide methods and systems for 5G roll-out planning that, in contrast to state-of-the-art radio planning solutions, introduce mobile users localization accuracy guarantees as a requirement. The radio planning framework is designed to address the needs of service providers when considering where to place 5G base stations to maximize throughput performance while guaranteeing a predefined localization accuracy target. The positioning-optimized radio planning solution according to embodiments of the present invention provides a solution for 5G (and beyond) network design that improves network-based localization performances by taking into account both users throughput, fairness and positioning KPIs. In order to achieve this, embodiments of the invention utilize a novel configuration parameter, herein referred to as Throughput-Positioning Ratio (TPR), which enables operators to configure customized policies towards an improved localization accuracy, for instance towards a maximum Position Error Bound (PEB). As such, embodiments of the invention achieve the advantage of enabling operators to offer more accurate localization services, which is a key requirement for various applications (e.g. for autonomous driving).

According to an embodiment, executing the joint performance optimization routine may include specifying a set T of test points t that sample the target area; and implementing decision variables / e {0,1} and ^ e {0,1}, wherein xj indicates whether a base station is deployed at candidate site j, and wherein ay indicates the maximum Signal-to-Noise-and-lnterference-Ratio, SINR, association between a UE at a test point /and candidate site j. When sampling the target area by means of the T test points, in each of the test points / a typical UE should meet the desired requirements in terms of throughput and positioning performances.

According to an embodiment, the distribution of the test points / within the target area may be configured to match an expected distribution of cellular users within the target area. Nevertheless, the solution according to the present invention is not tailored to a specific set of test points and can be readily applied to any user distribution.

In a realistic operation scenario, network operators must submit to logistical and administrative constraints while deploying new base stations. On the one hand, they are required to comply with municipal regulations in terms of electromagnetic emissions and public land occupation. On the other hand, they seek one-to-one agreements with private parties to install network equipment in their facilities. Therefore, according to an embodiment, the set S of base station deployment candidate sites /may be derived from a pre-negotiation phase between operators and the above-mentioned third parties in consideration of logistical and/or administrative constraints. According to an alternative embodiment, the set S of base station deployment candidate sites /may be determined to be a superset of the sites where LTE base stations have already been deployed. In this embodiment, it may be provided that the coordinates of pre-deployed/existing eNBs are fed into the joint performance optimization routine, and kept fixed during the optimization process.

It is worth pointing out that the joint performance optimization routine may likewise be executed even if there is not any a-priori knowledge of base station deployment candidate sites. In this case, according to another alternative embodiment, it may be provided that the set Sof base station deployment candidate sites /is determined as some random sampling of the target area.

According to embodiments of the invention, executing the joint performance optimization routine includes solving a joint throughput-positioning radio planning problem formulated as a single max-min problem that aims at maximizing the balance among test points /, both with respect to network throughput and positioning performance. In this context, it may be provided that the tuning parameter that regulates the throughput-positioning ratio of the joint performance optimization routine is incorporated into the objective function.

In order to simplify the analytical manageability, embodiments of the present invention provide for methods and systems that do not tackle the joint optimization problem directly, but break down the original problem into two problems and derive a sub-optimal solution for each of them. Specifically, embodiments relate to a solution wherein executing the joint performance optimization routine includes solving a network throughput optimization sub-problem that aims at optimizing the network throughput performance, while keeping the positioning performances below a configurable positioning performance threshold; and solving a positioning optimization sub-problem that aims at optimizing the positioning performance, while keeping the network throughput performance above a configurable network throughput performance threshold.

According to an embodiment may be provided that the network throughput optimization problem is formulated as a max-min problem that aims at maximizing the minimum network throughput experienced at the test points t. On the other hand, the positioning optimization problem may be formulated as a min-max problem that aims at minimizing the maximum position error bound, PEB, experienced at the test points t.

According to an embodiment, the positioning performance threshold and the network throughput performance threshold may be configured by adaptively processing the optimal values of each of the optimization sub-problems. Specifically, it may be provided that the optimization sub-problems are computed in a closed- loop fashion. In this context it may be provided that, first, a throughput optimization subroutine is run to obtain an optimal throughput performance value that represents a KPI for the system. Then, this optimal throughput performance value may be scaled and used as network throughput performance threshold for a positioning optimization subroutine to obtain an optimal positioning performance value, and vice-versa. This process may be iteratively repeated until convergence. The scaling process may be adaptive, meaning that the system monitors the convergence and the feasibility of each sub-problem and changes the scaling factor accordingly.

According to an embodiment, the target area may encompass a number of predeployed legacy base stations (in particular, LTE base stations). In this case, the parameters of the joint performance optimization routine may be adapted in such a way that the pre-deployed base stations provide a performance baseline for the joint performance optimization.

According to an embodiment, it may be provided that the tuning parameter regulates the flavor of the joint performance optimization, namely the throughput-positioning ratio (TPR), which indicates how much bit-rate an operator would compromise in order to gain one unit of accuracy in the users’ positions. The tuning parameter may be implemented in such a way that backward compatibility in the network deployment process is provided by setting the tuning parameter to 0.

There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the dependent claims on the one hand and to the following explanation of preferred embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the preferred embodiments of the invention by the aid of the figure, generally preferred embodiments and further developments of the teaching will be explained. In the drawing

Fig. 1 is a high level diagram illustrating a general architecture of a system for design planning of a cellular network in accordance with an embodiment of the present invention,

Fig. 2 illustrates the problem formulation of a joint throughput-positioning radio planning system in accordance with an embodiment of the present invention,

Fig. 3 is a high level diagram illustrating a closed-loop architecture of a system for design planning of a cellular network in accordance with an embodiment of the present invention,

Fig. 4 illustrates a throughput sub-problem formulation of a joint throughputpositioning radio planning system in accordance with an embodiment of the present invention,

Fig. 5 illustrates a positioning sub-problem formulation of a joint throughputpositioning radio planning system in accordance with an embodiment of the present invention, and

Fig. 6 is a high level diagram illustrating an architecture of a system for design planning of a cellular network with coexisting RAT in accordance with an embodiment of the present invention.

The problem of selecting where to install base stations is fundamental since the first cellular network deployments. The typical KPI for such works is coverage probability, which is shown to be almost invariant with respect to base station location geometry in case of massive deployments. The advent of 5G and its advanced RAT has lead to a paradigm change and brought up a series of new challenges, such as the usage of millimeter wave radio transceivers and ultra-dense non-uniform deployment in which case a number of heuristic algorithms have been developed to optimize both coverage and throughput. However, in order enable operators to offer advanced features and additional services providing better quality- of-experience, embodiments of the present invention address the joint optimization of network throughput and positioning performances in the network deployment process.

Embodiments of the present invention address the above-described crucial need of guaranteeing higher network-based localization accuracy by providing a novel network-design solution that takes into account jointly the required localization accuracy and the expected user throughput requirements while deciding the best position of the base stations among available candidate sites within a target area. Advantageously, the outcome of the joint performance optimization routine implemented in accordance with the embodiment may complement and support existing LTE deployments to improve this joint optimization goal as well as provide guidance on BSs positioning in 5G stand-alone (SA) deployments.

Embodiments of the present invention involve the following aspects:

- Joint optimization of localization and user throughput KPIs in next-generation radio deployments, e.g. 5G-NR but also 6G in the future

- Fine tuning of a novel parameter, namely throughput-positioning ratio (TPR) that can adapt to different operator’s policies

- Iterative algorithm to decide the best base station position between available candidate sites in addition to existing RAT deployment according to joint throughput and localization policies (output).

Embodiments of the invention provide a network design solution involving a novel radio planning scheme that aims at finding the best balance between throughput and (network-based) localization performance of a cellular network based on operators’ policies. Such policies and associated requirements may be taken into account by means of a tuning parameter that regulates the flavor of the joint performance optimization, hereinafter referred to as TPR (Throughput-Positioning Ratio). In a specific embodiment, this parameter may be defined to indicate how much bit-rate an operator would compromise in order to gain one unit of accuracy in the users’ positions. The parameter may be implemented in such a way that, when being set to 0, the solution obtains similar results as the legacy radio planning solutions, thereby providing backward compatibility in the network deployment process.

According to an embodiment, the present invention provides a method for allocating next-generation base stations based on localization and throughput requirements, the method comprising the steps of admitting as input a list of available base stations candidate site, expected localization in terms of PEB, expected user throughout and TPR parameter; solving jointly an optimization problem by running a novel algorithm that balances throughput and localization accuracy based on the operator requirements; and providing the position of next-generation base stations as output.

Fig. 1 shows a high-level architecture of a computer implemented network design system 100 in accordance with the embodiment of the invention. The system 100 is fed with two inputs 110, namely a Deployment Candidate Sites 112 and the tuning parameter TPR 114. The Deployment Candidate Sites 112 take into account that in a realistic operation scenario, network operators must adhere to logistical and administrative constraints when deploying their base stations, which leads to the definition of a set of candidate sites within a given target area. In particular, they must comply with electromagnetic emission limits, take into account the physical footprint of network equipment on public/private land, obtain administrative authorizations, etc.

As a shown in Fig. 1 , these inputs 110 are processed by a joint throughputpositioning planning system 120 that executes a joint performance optimization routine in order to calculate as output 130 an Active Candidate Sites 132, namely a subset of the Deployment Candidate Sites 112 at which base stations are (to be) deployed. The joint performance optimization routine may be executed by one or more processors, alone or in combination, of the joint throughput-positioning planning system 120. In some embodiments, a non-transitory computer readable medium includes a set of instructions that when executed by the processor(s) cause the processor(s) to perform the tasks of the joint performance optimization routine.

According to embodiments of the invention, the target area is sampled by means of Rest points /, wherein a typical UE should meet the desired requirements in terms of throughput and positioning performances. Preferably, the test point distribution matches the expected distribution of cellular users in such area.

To facilitate the installation procedure, it is assumed that base stations may be deployed only at operator-defined sites, thus calling for coordinate discretization. However, it is worth pointing out that the routing may likewise be executed even if there is not any a-priori knowledge of candidate sites (CSs) by taking as input some sampling of the target area. Herein, S denotes the set of such CSs with coordinates s/e Q, Vj e S, where Q denotes the target deployment area. For example, Smay be a superset of the sites where LTE base stations have already been deployed.

As already mentioned above, the planning system 120 illustrated in Fig. 1 outputs the set of CSs wherein gNBs will be deployed, while providing the maximum-SINR association between the typical UE in each test point t and its associated base station. Therefore, decision variables /G {0, 1} and atj^ {0, 1} are introduced, which indicate whether a gNB is deployed at CS /and the association between a typical UE at test point /and CS respectively.

In principle, to calculate the network throughput experienced at each test point /, the user throughput could be averaged over time. However, user rate depends on the serving base station scheduler, which assigns the optimal Modulation and Coding Scheme (MCS) given the current channel quality. Indeed, for the sake of tractability, we only consider Shannon’s channel capacity, assuming that the base station schedulers perform near-optimal MCS assignments. This provides an upper bound on the throughput that a typical UE experiences at test point /with coordinates ?G Q while being served by base station i. According to an embodiment, the Joint Throughput-Positioning Planning System 120 is implemented and configured to solve the problem shown in Fig. 2. In the illustrated embodiment the problem is formalized as a joint throughput-positioning planning problem. Here, the joint goal is to maximize the fairness among test points, both throughput and positioning-wise. In this context it is important to note that the former objective maps onto a max-min problem, while the latter translates into a min-max problem. Against this background, the problem illustrated in Fig. 2 can be set up as follows:

First, as explained above, one may define as S the set of candidate sites and as T a set of test points, where the continuous target deployment is sampled. Then, decision variables xj e {0,1} and a _tj e {0,1} are introduced, indicating whether a base station is deployed at candidate site j and the maximum Signal-to-Noise-and- Interference-Ratio (SINR) association between a typical UE at a point t and candidate site j, respectively.

With regard to the flavour tuning implemented according to embodiments of the invention, it should be noted that throughput and localization performances are different metrics that employ different unit of measurements. Such different nature raises the need for a tuning parameter p, dubbed as Throughput-Positioning Ratio (TPR), which reflects the desired flavour of the planning solution. Specifically, TPR p may take into account how much an operator values a unit gain towards throughput or localization performances, in other words how many bit/s would it put at stake to improve the PEB by 1 meter.

Therefore, to properly account for heterogeneous objectives, the design planning method according to embodiments of present invention introduces in the objective function the tuning factor TPR in form of a scalar factor p that trades off between throughput and positioning performances. In the extreme case of p = 0, the optimization will provide only throughput guarantees. Conversely, when p -> », the solution will optimize positioning performances regardless of the experienced throughput values. In the problem of the Joint Throughput-Positioning Planning shown in Fig. 2 the decision variables xj e {0,1} and a _tj e {0,1} are used as follows: x = [x^ ...,x _s ] ^T , with (-^indicating the transpose operator, and { } _t; = a _tj is a matrix containing the association variables. Moreover, 1 _K denotes a unit column vector of size K x 1. The objective function is the fairness among every test point in terms of throughput and positioning performances, being the generic element r _t of r where 14^ is the base stations bandwidth, g _tj is the channel gain between point t and candidate site j, N' is the noise power and g _t ' _j indicates the normalized interference experienced by a typical UE at site t given deployment decision x, namely

As already mentioned above, g is the TPR of the specific operator, which drives the optimization objective according to operator’s policy requirements.

In addition, the generic element b _t of b is the Position Error Bound (PEB) given such deployment decisions, that is where parameters v _jt can be written as in D. B. Jourdan, D. Dardari and M. Z. Win, "Position error bound for UWB localization in dense cluttered environments," in IEEE Transactions on Aerospace and Electronic Systems, vol. 44, no. 2, pp. 613-628, April 2008, the entire disclosure of which is hereby incorporated by reference herein, and depends on the real distance between test point t and candidate site j as well as on the measurement bias statistics, while is their relative angular position.

With respect to the Position Error Bound, it should be noted that to assess the localization performance of cellular networks, the above embodiment leverages on the Cramer-Rao Lower Bound (CRLB), which provides a lower bound on the covariance matrix of any unbiased estimator. This allows treating the problem in a general fashion, without tailoring it to a specific localization technique, while still providing useful insights on the expected performances of a real positioning system. The above formula gives the PEB of ToA (Time-of-Arrival) measurements with uniformly distributed measurement biases and represents a lower bound on the mean-square error (MSE) of the distance between the UE position and its corresponding estimate.

With respect to the ToA measurements, it should be noted that, generally, timebased positioning is a fundamental positioning technique, which combines Time-of- Flight (ToF) measurements related to a set of (at least three) base stations to derive the location of some UE by means of the multilateration technique. To this aim, the UE receives periodic Positioning Reference Signals (PRSs) from the serving and the adjacent base stations and records their respective Time of Arrivals (ToAs).

Fig. 2 shows a high-level architecture of a computer implemented network design system 200 in accordance with a second embodiment of the invention. Like in the embodiment described in connection with Fig. 1 , the system 200 is fed with two inputs 210, namely a Deployment Candidate Sites 212 and the tuning parameter TPR 214. Both inputs 210 can be determined in the same or similar way as described above in connection with Fig. 1.

The planning tool 220 of the network design planning system 200 depicted in Fig. 2 is a closed-loop solution, where the joint throughput-positioning problem is decomposed into two subroutines, namely a throughput-optimized subroutine 222 and a positioning-optimized subroutine 224.

According to the illustrated embodiment, the throughput-optimized subroutine 222 solves a throughput sub-problem, which optimizes the network throughput r while enforcing that contribution b that takes into account the positioning performances is below a tunable threshold z _b . Conversely, the positioning sub-problem optimizes b while guaranteeing that r is over a tunable threshold z _r . The respective sub- problems are shown in Fig. 4 and Fig. 5, respectively. The employed notation is the same as in Fig. 2.

According to embodiments, the thresholds _b and i _r may be set by adaptively processing the optimal values of each sub-problem as follows: First, the throughput- optimized subroutine 222 obtains its optimal value r* that represents a KPI for the system. Then, this is scaled and used as z _r for the next subroutine 224 and vice- versa. This process, which may be executed by a dedicated adaptive KPI processing component 226 of the planning tool 220, is iterative until convergence. In some embodiments, the scaling process is adaptive, meaning that the system monitors the convergence and the feasibility of each sub-problem and changes the scaling factor accordingly.

As a shown in Fig. 3, the planning tool 220 provides as output 230 an Active Candidate Sites 232, namely a subset of the Deployment Candidate Sites 212 at which base stations are (to be) deployed. The throughput-optimized subroutine 222 and the positioning-optimized subroutine 224 may be executed by one or more processors, alone or in combination, of the planning tool 220. In some embodiments, a non-transitory computer readable medium includes a set of instructions that when executed by the processor(s) cause the processor(s) to perform the tasks of the performance optimization routines.

It should be noted that the joint planning problem to be solved by the joint throughput-positioning planning system 120 of Fig. 1 , i.e. the joint planning problem shown in Fig. 2, is highly non-convex. In particular, the binary constraint leads to a combinatorial optimization problem, which is not solvable in polynomial time. Although, after relaxing this constraint, the set of constraints becomes convex, the joint objective function is still non-convex, being the sum of non-convex components r and b.

Moreover, both sub-problems shown in Fig. 3 are non-convex as they retain the non-convexity of the objective function (by keeping r and b, respectively) while adding a new set of non-convex constraints (including the threshold constraints on b and r respectively). Therefore, embodiments of the present invention may utilize an iterative algorithm that relies on a convex relaxation of such sub-problems.

Fig. 6 shows a high-level architecture of a computer implemented network design system 600 in accordance with a third embodiment of the invention. The embodiment relates to a planning solution with coexisting RATs, in particular preexisting LTE deployments. Accordingly, the input 610 to system 600 not only includes a Deployment Candidate Sites Q 2. and the tuning parameter TPR \4, like in the embodiments described in connection with Fig. 1 and 3, but includes an additional input 610, namely the current pre-existing eNB deployment 616 of other RATs. While inputs 612 and 614 can be determined in the same or similar way as described above in connection with Figs. 1 and 3, additional input 616 may just include the known coordinates of existing base stations.

Advantageously, the solution illustrated in Fig. 6 supports pre-existing deployments of other RATs as the joint planning problem keeps the same formulation. However, the elements r _t and b _t need to account for the performances provided by the other RAT deployment, which represent a baseline for the network. This translates into the following new objective functions where c _t is the throughput baseline and u _t is the PEB baseline, obtained by setting all Xj to 1 in the respective equations. It should be noted that for the PEB calculation it is assumed that a UE at a test point t is able to exploit all covering base stations for its localization, as indicated by 3GPP, “NG Radio Access Network (NG-RAN); Stage 2 functional specification of User Equipment (UE) positioning in NG-RAN”, 3 ^rd Generation Partnership Project(3GPP), Technical Specification (TS) 38.305, 2020, version 16.0.0, the entire disclosure of which is hereby incorporated by reference herein. As a shown in Fig. 6, the planning tool 620 provides as output 630 an Active Candidate Sites 632, namely a subset of the Deployment Candidate Sites 612 at which base stations are (to be) deployed. The joint performance optimization routine may be executed by one or more processors, alone or in combination, of the planning tool 620. In some embodiments, a non-transitory computer readable medium includes a set of instructions that when executed by the processor(s) cause the processor(s) to perform the tasks of the performance optimization routines.

Validations of the proposed solutions by means of exhaustive simulations based on synthetic scenarios and realistic existing deployments unveiled that solutions according to embodiments of the invention outperform legacy approaches terms of Position Error Bound(PEB) and minimum experienced throughput, respectively. The obtained results, considering real base station deployments, demonstrate the effectiveness of the solution along with the trade-offs between throughput and localization to be expected.

Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.