Problem C
Multi-Parameter Wireless Network Optimization based on Coverage Simulation

1 Background Information

In a wireless network, one of the main factors that affect the experience of mobile users (e.g., data rate when downloading files, latencies when playing games) is the strength of signal received by cellphones. To provide stable and satisfactory network services, network operators optimize the quality of network signal coverage by continuously adjusting the antennas (a device on a base station that transmits radio signals). However, this coverage optimization problem is quite challenging for the following reasons:

• Challenge 1: the objective function of this problem is usually non-convex and non-smooth, and function execution is very time-consuming. The function is essentially a model that describes the relationships between the antenna configurations and the network coverage quality. It involves complicated environment modelling and principles of signal propagation, and is usually treated as a black-box function for optimizers.

• Challenge 2: coverage optimization is a large-scale problem. The configurations of nearby antennas are correlated because the radio signals transmitted by these antennas will interfere with each other. Therefore, optimizing the configuration of each antenna separately may result in local optimums. However, optimizing all the antenna parameters in one shot will necessitate a tremendously huge search space, which makes searching with limited computing resources and time budgets infeasible.

Currently, Huawei has a high-precision coverage simulation model, which can calculate an antenna-level coverage quality value given the configuration of an antenna. Then the network-level coverage quality value is derived by summarizing the antenna-level quality values of all the antennas (explained in detail in "Coverage calculation" Section). However, only a limited number of simulations can be done because of their high computation complexity. In this contest, the contestants can treat the coverage simulation model as a black box and solve this expensive optimization problem (EOP) by designing online combinatorial optimization methods. Specifically, $X$ candidate configurations are provided for each antenna. Then the optimizer should explore the best configuration among the $X$ candidates for each antenna and minimize the number of calls to the coverage simulation model so that the overall network-level coverage quality is optimal.

2 Problem Definition

2.1 Coverage Modeling

Network coverage modeling consists of three parts: grids, antenna parameters and coverage calculation.

Grids

To facilitate coverage simulation, a 3-D geographical area is rasterized into multiple 5m*5m*3m grids according to the height of buildings, which are used as the smallest unit for subsequent object calculations. The coordinate of each grid can be represented with a 3-D coordinate $(x, y, z)$. As shown in Figure 1, the grids of the area with buildings are divided according to the height of the buildings, and the ground without buildings has only one layer of grids (the colors in the picture don’t mean anything). The shape of the ground area covered by the simulation is a polygon where $x\in [60,1900], y\in [20,1800]$. For the simulation map information, the contestants only need to consider the relative locations of base stations and buildings.

Figure 1: illustration of spatial rasterization

Antenna Parameters

In the geographical area, there are $C$ base stations $BS=\{ BS_{1},BS_{2},...,BS_{C}\} $, where the location of a base station $BS_{i}$ is denoted as $\{ x_{BS_{i}},y_{BS_{i}},z_{BS_{i}}\} $. As shown in Figure 2, each base station has three antennas: $\{ ant_{BSi}^{1},ant_{BSi}^{2},ant_{BSi}^{3}\} $, facing different directions and covering different areas (in our test cases, there is a situation where a base station has only two antennas). Note that we use $ant$ to denote an antenna in the rest of the problem description if it is irrelevant on which base station the antenna is deployed. Each antenna is a rectangular cuboid shape. For ease of understanding, the area covered by an antenna is a sector. The closer to the center of the sector, the higher the signal strength the antenna transmits (similar to the light transmitted from a flashlight). We focus on three parameters of each antenna:

Figure 2: illustration of horizontal direction of the three antennas on a base station, their coverage shape and signal strength distribution.

• Azimuth $Azm_{ant}$. This denotes the horizontal angle (the angular bisector of the central angle of the sector) of an antenna $ant$ from the north direction (clockwise), as shown in Figure 3. The north direction is the direction of increasing Y coordinate. The east direction is the direction of increasing X coordinate. Each antenna has an initial azimuth, and we focus on the relative azimuth (the difference between adjusted and initial azimuths). The range of $Azm_{ant}$ is:

  \[ Azm_{ant} \in \{ -30^{o},-20^{o},-10^{o},0^{o},10^{o},20^{o},30^{o}\} \]
  

  Figure 3: the azimuth of an antenna

• Tilt $Tlt_{ant}$. This denotes the vertical angle (the angular bisector of the central angle of the sector) of the antenna $ant$ from the horizontal direction (clockwise), as shown in Figure 4. Each antenna has an initial tilt, and we focus on relative tilt. The range of $Tlt_{ant}$ is:

  \[ Tlt_{ant} \in \{ 0^{\circ },2^{\circ },4^{\circ },6^{\circ },8^{\circ },10^{\circ },-2^{\circ },-4^{\circ },-6^{\circ },-8^{\circ },-10^{\circ }\} \]
  

  Figure 4: the tilt of an antenna

• Beam Pattern $Ptn_{ant}$. This parameter controls the shape (the vertical and horizontal central angles) of the sector transmitted by an antenna. The pattern value ranges from 0 to 16, indicating 17 different beam patterns. Figure 5 illustrates the angle settings of Pattern 0 and 16. The angle settings of all the patterns will be given as part of the inputs.

  

  Figure 5: an example of the beam patterns of an antenna

In this manner, there are 1309 parameter combinations ($7 \times 11 \times 17 = 1309$) for each antenna, and the size of global search space is $1309^{3\times C}$.

Coverage calculation

Each grid can receive radio signals from multiple nearby antennas, and each antenna can cover multiple grids. The signal strength transmitted by an antenna and received on a grid $(x,y,z)$ is denoted as $Strength_{x,y,z}^{ant}$ (unit: dBm, higher is better). $Strength_{x,y,z}^{ant}$ is the signal strength in the upper left corner of the top surface of the 3D grid, the same for the grid partially covered by the building. Figure 6 shows an example of 2 antennas covering 28 grids, in which Grid 1 can receive signals from $Ant1$, Grid 2 can receive signals from $Ant2$, and Grid 3 can receive signals from both antennas. The signal strength on a grid from an antenna can be derived by the aforementioned coverage simulation model.

• Antenna-level coverage quality values: this refers to the set of signal strength values on the grids covered by an antenna. For example, the antenna-level coverage quality values of $Ant1$ in Figure 6 denote the Strength value on the blue grids from $Ant1$.

• Network-level coverage quality values: this refers to the set of signal strength values on the grids covered by all antennas. Note that some grids may have Strength values from multiple antennas (e.g., the green grids in Figure 6).

Figure 6: an example of grid coverage with 2 antennas

On each grid, the antenna with the strongest signal strength is the serving antenna. Other antennas are named neighboring antennas. Specifically, the serving antenna and neighboring antenna set of grid $(x,y,z)$ are calculated as follows:

And the serving antenna signal strength is denoted as follows:

For a grid, if the difference in signal strength between the neighboring and the serving antennas is less than 6, then the grid has an overlapping effect. Specifically, the set of overlapping antennas on grid $(x,y,z)$ is calculated as follows:

We also consider signal interference, indicated by Signal to Interference and Noise Ratio (SINR). On grid $(x,y,z)$, SINR is calculated with $Strength_{x,y,z}$, $Neighs_{x,y,z}$ and $Noise$ as follows, where $Noise$ is a constant with value $5.98579 \times 10^{-13}$.

2.2 Objectives

The coverage optimization problem involves the minimization of the following three objectives:

• Overall weak coverage ratio R1. A grid is considered having weak coverage issue if the signal strength of its serving antenna is lower than a pre-defined threshold $\delta _{1}$. The $\delta _{1}$ is set to -108 in our cases. The overall weak coverage ratio is the sum of the grids that have weak coverage issues:

  \[ R1 = \frac{\sum _{x,y,z = 1}^{N_{grid}} \textbf{1}_{Strength_{x,y,z}< \delta _{1}}}{N_{grid}} \]

• Overall overlapping ratio R2. A grid is considered to have overlapping coverage issue if: 1) the Strength value of its serving antenna is greater than or equal to -110 dBm, and 2) the cardinality of the set of its overlapping antennas is greater than or equal to a pre-defined threshold $\delta _{2}$. The $\delta _{2}$ is set to 3 in our cases. The overall overlapping ratio is the sum of the grids that have overlapping coverage issues:

  \[ R2 = \frac{\sum _{x,y,z = 1}^{N_{grid}} \textbf{1}_{Strength_{x,y,z}\ge -110} \cdot \textbf{1}_{|ANT_{x,y,z}^{overlap}| \ge \delta _{2}}}{N_{grid}} \]

• Overall interference ratio R3. A grid is considered having interference issue if its SINR value is lower than a pre-defined threshold $\delta _{3}$. The $\delta _{3}$ is set to -1 in our cases. The overall interference ratio is the sum of the grids that have interference issues:

  \[ R3 = \frac{\sum _{x,y,z = 1}^{N_{grid}} \textbf{1}_{SINR_{x,y,z}< \delta _{3}}}{N_{grid}} \]

${N_{grid}}$ is the total number of grids, which is set to 200768 in our cases. $R1$, $R2$ and $R3$ retain two decimal places, and the lower the value the better.

3 Input

• 1.EPT
  Each contestant is provided with an Engineering Parameter Table (EPT), you can get this from attachment 1.EPT(Original_Engineering_Parameter_Table.csv):
  BS is the name of base station. Each base station is deployed at a point location.
  ant is the name of antennas. A maximum of three ants under a base station. If the names are the same, the antennas are deployed at the same point, but the azimuths are different.
  X, Y, Z recording the location of each base station in absolute coordinates, which can be rasterized by grid size.

  \[ Location_{0}^{N} = \{ (X_{BS_{i}}^{j},Y_{BS_{i}}^{j},Z_{BS_{i}}^{j})_{0}^{N} | i \in [1,C],j \in [1,3]\} \]

  Azimuth, Tilt, Beam Pattern recording the original parameter of each base station:

  \[ \theta _{0}^{N} = \{ (Azm_{BS_{i}}^{j},Tlt_{BS_{i}}^{j},Ptn_{BS_{i}}^{j})_{0}^{N} | i \in [1,C],j \in [1,3]\} \]

  Table 2: Initial parameter Table of EPT
  BS	ant	X	Y	Z	Azimuth	Tilt	Beam Pattern
  site1	1	138.07	1101.27	11	100	3	0
  site1	2	138.07	1101.27	11	270	3	0
  site1	3	138.07	1101.27	11	0	3	0
  site2	4	419.5	1186.36	25	335	5	0
  site2	5	419.5	1186.36	25	125	8	0
  site2	6	419.5	1186.36	25	175	5	0

• 2.Building Information around the base station.
  We divide the space of a city into 5m*5m*3m grids, which are layered on top of each other according building heights. Empty space without any buildings is composed of only one layer of grids.
  X, Y, Z describes the location of the building in absolute coordinates, which can be rasterized by grid size. X, Y is the outline of a building in a clockwise direction as a polygon, and Z is the height of the building. You can get all building information from the attachment (2. Building Information around the base station.csv). The existence of buildings can block the signal propagation of the antenna, resulting in a weaker signal from the grids blocked by the building. Therefore, contestants can make full use of the building information for optimal selection of antenna parameters.
  

  Table 3: A buildings around the base station.
  buildingid	X	Y	Z
  1	895.94	845.28	45
  1	880.61	844.75	45
  1	880.28	854.08	45
  1	893.51	854.54	45
  1	893.47	856.65	45
  1	908.22	857.19	45
  1	908.47	848.2	45
  1	895.81	847.83	45
  1	895.94	845.28	45

• 3.Candidate parameters for antenna.
  For each antenna, the contestant needs to select one of the pre-defined X parameters as the output which is provided in attachment CASE_x.csv. Candidate parameters for each case can be obtained only from the corresponding attached parameters.
  In this problem, there are six cases in the attachment. It is important to note that all cases are run on the same map, with the location of buildings and base stations remaining the same, the only thing that differs is the parameters of the antenna. For each case, the contestant needs to select only one parameter for each ant from 20 candidate parameter provided. In total, there are 56 antennas with a search space is $20^{56}$, and the maximum network-level coverage quality is obtained by selecting the optimal combination of parameters.
  Example:
  One antenna candidate parameter is as follows: One BS and ant represent one antenna, (e.g., There are 10 candidate parameters of one antenna in Figure 7).
  

Figure 7: N candidate parameters of an antenna

4 Score Calculation

It is known that the smaller the objective values $R1$, $R2$ and $R3$, the better. In order to better evaluate and equalize the three objectives, first obtain the maximum target $u1$ and the average objective $u2$.

In order to increase the score gap between the contestants, $u1_{Original}$ and $u2_{Original}$ are computed based on original EPT as a way to calculate the network performance gain obtained from EPT submitted by contestants. The score of each case is written as:

The $Score$ is a weighted sum of $Score1$ and $Score2$. If the value of $u1<u1_{Original}$, $Score1$ is 0. If the value of $u2<u2_{Original}$, $Score2$ is 0. The full score is 100, and six cases’ score need to be averaged to obtain the final score.

5 Program Structure

Figure 8: program structure

The main interaction program structure is shown in Figure 8. The antenna parameters submitted by the contestants are used to get score through the interactive system. A simple code about the whole process is in the attachment 4.example_submission.py. The main interactions are as follows:

Step1: Interaction start

The platform:

Contestant program:

The platform:

The / means no input or output in this step. The interaction data has to be a string. $\theta = \{ \theta _{k}|k \in [1,X]\} $ is provided in attachment CASE_x.csv. The k-th set of parameters is denoted as $\theta _{k} = \{ (BS_{i}, ant_{i}, Azm_{BS_{i}}^{j},Tlt_{BS_{i}}^{j},Ptn_{BS_{i}}^{j})_{k} | i \in [1,C],j \in [1,3]\} $, recording the BS name, the ant id, the azimuth, the tilt, and the beam pattern of each antenna. The interaction data has to be a string, so the platform outputs $\theta $ in the following form: [[’site1’, 1, 100, 3, 0], [’site1’, 1, 80, -5, 1], [’site1’, 1, 80, -5, 4], ...]

Step2: Interaction continue

Contestant program:

The contestants need to parse the contents of the case string output by the platform as input, and select the optimal parameter $\theta ^{*} = \{ (BS_{i}, ant_{i}, Azm_{BS_{i}}^{j},Tlt_{BS_{i}}^{j},Ptn_{BS_{i}}^{j})^{*} | i \in [1,C],j \in [1,3]\} $ as output to obtain the optimal network performance. Note that only one parameter be selected for each antenna from the parameters provided in the case, meaning that 56 parameters must be output. The format of the output string is as follows:

Step3: Score calculation

The platform:

If there is an invalid parameter in $\theta ^{*}$, it will be judged as a wrong answer. The platform outputs scores in the following format:

Contestant program:

The contestants need to parse the above strings to get the score. Step2 and Step3 can be looped multiple times for each case. However, since the black box for coverage simulation is time consuming, the number of loops can’t exceed 50 (the platform will only give the score for the first 50 loops if the time limit is not exceeded).

Step4: Interaction end

If the interaction end, contestants need to output a sign to inform the platform.

Contestant program:

The platform:

The platform saves the highest score for the current case. The final score displayed by the platform is the average of six cases. The information about the interaction process of case1 is provided to the contestants to facilitate the design of the algorithm.