Method for characterizing performance of wireless network

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a wireless communication network, and more particularly to a technique for acquiring and processing network parameter information in the design, implementation, or operation of a wireless communication network.

【0002】

[Conventional technology]

A typical wireless network includes many interconnected base stations that provide wireless traffic to a wide variety of fixed or mobile users distributed across geographically well-defined coverage areas. Wireless interfaces generally must operate under conditions such as multiple access requirements to the network, uncontrollable signal propagation, and limited bandwidth. A request for multiple access to a network means that the location and time of the service request is unknown in advance. Therefore, the network must provide the required level of service with sufficient capacity over a large geographic area. The above-mentioned uncontrollable signal propagation is an environment in which the wireless link between the base station and the user is usually accompanied by high propagation loss and reflection, diffraction, or scattering effects on clutter, terrain, and other types of obstacles. Shows that it relies on signal propagation in.

【0003】

These propagation effects also lead to interference between wireless communication channels. Interference increases with the amount of traffic carried by the network, which can result in poor quality of service, service interruptions, or outages (eg, call abandonment). This is highly undesirable and sets an upper limit on the traffic that can be carried by the network. These restrictions are highly dependent on the local propagation environment, network layout and configuration, and spatial traffic distribution.

【0004】

Network modeling tools are often used to get the best performance from wireless networks in terms of quality of service and the amount of traffic that can be carried. Such network modeling tools include, for example, Mobile Systems. International's (http://www.rmrdesign.com/msi) Planet tool and Aircom's (www.aircom.co.uk) Asset tool (which is a network design tool that includes frequency planning algorithms). There are commercial tools like. These tools typically use propagation prediction algorithms and data on network configuration, traffic load, terrain, and communication standard-specific link budget parameters for radio frequency (RF) link metrics (eg, RF field strength). Calculate spatial distribution and quality of service measures (eg, frame error rate). Based on the result, the network configuration can be adjusted. This approach involves many networks such as number of cells, number of communication channels per cell, antenna position, pattern, tilt, orientation, communication channel and transmit power level per cell, frequency plan, handoff threshold, etc. Can handle parameters. Traditional network modeling tools can be used during the design phase when the network is upgraded or when the network needs to be readjusted in response to changes in the environment or traffic patterns.

【0005】

In addition to providing information on the spatial distribution of link performance, it is important to predict overall network performance measures, such as network coverage and total network blocking rate (blockage rate). Such measures help to absolutely quantify the performance of the entire network and to make improvements when the network configuration changes. Defining and predicting all such network performance measures is also necessary when improving networks using optimization algorithms.

【0006】

The conventional network modeling tools described above have some serious drawbacks. For example, the accuracy in predicting local link performance is limited by the finite resolution of terrain and clutter and the rough approximation of the propagation prediction algorithm. Moreover, these traditional network modeling tools are usually so unreliable in predicting measures over the entire network that they generally cannot be used as the basis for mathematical or numerical optimization processes. This is due to the fact that predictions of network performance measures such as network coverage can produce reliable results only if the local traffic distribution is captured by the modeling process. For example, areas with high traffic should have a higher weight in network coverage analysis than areas with low or no traffic.

【0007】

Similar problems arise when predicting network capacity and network blocking rate measures using traditional tools. For example, the interference generated by a traffic hotspot is highly dependent on its exact location. This problem becomes even more important in modern networks with power control capabilities. Small local fluctuations in the traffic distribution can lead to large fluctuations in the associated propagation loss. This results in inaccurate power level estimates (evaluations) for the associated communication channels, affecting interference and power budget predictions, both of which are reflected in the effective network capacity.

【0008】

Another problem is that traditional network modeling tools typically analyze local link performance parameters on a regular topological grid. Such a tool cannot provide a representative picture of the overall network performance measure, as such grids do not reflect actual traffic patterns. Moreover, the discrete nature of the grid does not allow the mathematically sound definition of differentiation required when such tools are used as the basis for differential optimization procedures. Numerical methods can be used instead, but such methods generally require very fine grid spacing and are unacceptably long.

【0009】

[Problems to be Solved by the Invention]

Therefore, obviously, in order to solve the above-mentioned problems of the prior art, it is necessary to improve the technique of estimating (evaluating) and interpolating the network parameters used for modeling the wireless network.

【0010】

[Means for solving problems]

The present invention improves the technique of estimating and interpolating network parameters used for modeling wireless networks. The present invention is feasible, for example, in processor-based systems for characterizing, tuning or optimizing the overall performance of wireless networks. In the embodiment, the values of one or more link parameters of the wireless network are estimated on test points derived at least partially from the road location data (eg, road map) that characterizes the area served by the wireless network (eg, road map). Be evaluated). This estimation (evaluation) can be performed using a linked model. In another embodiment, the values of one or more link parameters of a wireless network are interpolated along multiple edges between the data points that define the mesh. The edge corresponds to the road. A measure of network performance is then generated using the interpolated values. The edges of the mesh are associated with a set of edge weights that represent traffic in the wireless network. The edge weights can be adjusted to match the available network traffic data. Meshes can be generated, for example, from road map files or image files, and mesh simplification operations such as edge collapsing can be applied prior to interpolation.

【0011】

Examples of link parameters that can be interpolated along the edges of the mesh are the signal level of the communication channel, the signal-to-interference ratio of the communication channel, and the path loss between the network user and the base station. Network performance measures include network coverage measures, such as, for example, the percentage of target coverage areas that can access the base station pilot signal with a signal-to-interference ratio above a specified threshold.

【0012】

According to the present invention, by interpolation between data points in a road-based mesh, statistical variations are averaged and network performance measures can be calculated as a smooth differentiable function of one or more link parameters of the network. Simplifies characterization, tuning and optimization. Moreover, road-based interpolation according to the present invention can provide significantly better results than the conventional topological grids described above in the design, tuning and optimization of wireless networks.

【0013】

The present invention can be realized as one or more software programs running on a personal computer, workstation, microcomputer, mainframe computer, or other type of processor-based information processing device.

【0014】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, the present invention will be described with respect to an exemplary wireless network information processing technology realized in a computer-based processing system. However, it should be understood that the present invention is not limited to use in any particular type of processing system. The techniques of the present invention are suitable for use in a variety of other systems and in a variety of applications. Further, the techniques of the present invention are applicable and mobile to many different types of wireless networks, including time division multiple access (TDMA), frequency division multiple access (FDMA) and code division multiple access (CDMA) wireless networks. It can also be applied to a subscriber device, a fixed subscriber device, or a combination of a mobile device and a fixed device. The term "wireless network" as used herein includes these and other types of networks, as well as subnetworks or other parts of such networks or combinations of multiple networks. The term "mesh" as used herein includes any arrangement of data points that are at least partially interconnected. The term "optimization" as used herein should be understood to include any kind of improvement in network performance (eg, an improvement that provides performance that is considered acceptable to a given application). Therefore, these terms as used herein do not require any kind of true optimization, such as the actual minimum or maximum of a particular performance function.

【0015】

Examples of the present invention relate to processor-implemented methods and devices for road-based estimation and interpolation of network parameters.

【0016】

FIG. 1 shows an exemplary processing system 10 in which the road-based estimation / interpolation technique according to the present invention is realized. The processing system 10 has a processor 12 and a memory 14, which are connected so as to communicate through the bus 16. System 10 further includes an input / output (I / O) controller 18 connected to bus 16 to communicate with processor 12 and memory 14. The I / O controller 18, along with the processor 12, directs the operation of some peripheral components such as the display 20, the printer 22, the keyboard 24 and the external storage device 26.

【0017】

One or more elements of system 10 represent, for example, a portion of a processor-based information processor of a desktop or portable personal computer, workstation, microcomputer, mainframe computer, or other type. The memory 14 and the external storage device 26 can be electronic, magnetic or optical storage devices. The external storage device 26 can include a database of wireless network information (eg, a database of information about wireless network operating parameters and the like used to generate the graphical displays described below). The external storage device 26 can be a single device or can be distributed (eg, distributed across multiple computers or similar devices). The term "database" as used herein includes the construction of any stored data that can be used with road-based interpolation techniques.

【0018】

The present invention, at least in part, can be realized in the form of computer software programs stored in memory 14 or external storage device 26. Such a program is produced by the processor 12 in order to produce the desired output in a predetermined format (eg, on the display 20 or in the printout produced by the printer 22) according to the input data supplied by the user. It is feasible. The input data supplied by the user can be input by the keyboard 24, read from one or more files in the external storage device 26, or obtained from a server or other source through a network connection. Is also possible.

【0019】

As mentioned above, overall performance metrics for wireless networks, such as network coverage and network capacity, can be estimated by computing RF link properties on topological grids using statistical propagation models. However, the present invention provides significantly improved results using irregular meshes based on road maps. Road maps provide valuable information about how traffic is distributed. Statistical variability is averaged by taking RF link metrics such as estimated receive power and carefully interpolating along the road with an irregular mesh, and network performance is described as a smooth function of basic network parameters. You will be able to.

【0020】

[1. Example of Modeling Procedure] Next, a procedure exemplifying how the road-based traffic estimation / interpolation according to the present invention is realized will be described.

【0021】

[1.1 Modeling network parameters] Various network parameters can be associated with modeling the performance of wireless networks. The network parameters that define the configuration of the network generally must be determined in advance during the modeling process. Some of these parameters are related to, for example, hardware, terrain, clutter, or traffic, and some are specific to a particular communication standard. Examples of such configuration parameters include cell position, antenna parameters, power level, handoff threshold, channel bandwidth, terrain elevation data, and the like. Some of the network configuration parameters are considered fixed network parameters (eg, terrain elevation data, and possibly antenna position, antenna altitude, etc.), while other network configuration parameters are adjustable network parameters (eg, antenna altitude). , Antenna tilt, power level per communication channel, frequency planning, etc.).

【0022】

If the wireless network is optimized using an optimization algorithm, the network parameters that change during the optimization process are considered tunable network parameters. For example, when a frequency planning algorithm is used, this adjustable network parameter can be the network frequency per channel unit in each cell. As another example, when a derivative-based optimization algorithm is used, this adjustable network parameter should be antenna tilt, power level per communication channel, or any other mathematically continuous network configuration parameter. Is possible. Commercially available tools, including frequency planning algorithms, are the Aircom (www.aircom.co.uk) Asset network design tools mentioned above. An example of a differential-based algorithm is a US patent application (inventor: KL). Clarkson et al., Title of the Invention: Methods and MFP for Derivative-Based Optimization of Wireless Network Performance).

【0023】

In addition to the configuration parameters, there are network parameters that are determined within the modeling process. Such parameters are usually link-related parameters such as path loss, cell allocation, field strength at a point, other local link performance metrics, and overall network performance measure. These parameters provide information about the performance of the network. An example of a network design tool that models link performance metrics for wireless networks is the Mobile Systems International (http://www.rmrdesign.com/msi) Planet tool described above. An example of a path loss model on which tools like Planet are based is the well-known Hata model. This is described in M. Hata, "Empirical formula for propagation lossin land mobile radio services", IEEE Trans. On Vehicular Technology, VT-29: 317-325, August 1980.

【0024】

For example, in the CDMA IS-95 standard, forward link pilot coverage is an important factor in link performance. At a given test point i, the forward link coverage is estimated from the signal-to-interference ratio of the dominant server as follows:

[Number 1]

<img file="JP2001203631A_D0001.tif" />However, n is the number of sectors and α_kAnd β_jIs a constant derived from network parameters, Etot_ijIs the power received from antenna j at test point i, η is the total noise term, and fm_iCan represent an additional fade margin. Equation (1) is an appropriate threshold Y₀If higher, test point i is covered (has a cover).

【0025】

Based on this definition of coverage at one test point i, network coverage can be defined as the percentage of all test points that have a forward link pilot coverage. Individual test points can have different weights, for example representing the importance or traffic density of individual locations. Since such a network coverage measure has one value for each network configuration, it is possible to compare the performance of various network configurations. In addition, this makes it possible to discover the "best" network configuration and use optimization algorithms that maximize this network performance value.

【0026】

[1.2 Traffic Modeling] The quality of the network performance measure obtained from such a modeling process strongly depends on the selection and distribution of test points. If the test points are distributed on a regular grid, the plots obtained for covered or uncovered areas do not reflect network performance in operation. Uncovered test points may be in low traffic areas. Therefore, network coverage measures based on these test points make little sense.

【0027】

If the goal is to tune the network parameters with a derivative-based algorithm to maximize the network coverage and other measures of overall network performance, then the network tune parameters (eg, antenna tilt) are tuned and functioned. It is important that the fluctuations are smooth. The reason is that advanced optimization algorithms require that the function have a well-defined first derivative and, in some cases, the second derivative. Without meaningful differentiation, direct search methods (eg Margaret H. Wright, "Direct search methods: Once scorned, now respectable", in DF Griffiths and GA You will have to rely on Watson, eds., Numerical Analysis 1995 (Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis, pp.191-208). Such a direct search method may have very poor convergence, especially when the dimensions are high. In the usual case where there is at least one independent variable per sector, the dimensions often exceed 100.

【0028】

In order for an overall performance measure such as cover register to be a differentiable function of network parameters such as antenna tilt, it is preferable that the traffic distribution be approximated by something other than just a set of discrete points. .. A possible alternative approach is to add lines connecting the above test points to form a mesh, assign traffic densities to each connecting line, and integrate on these connecting lines. For example, (1) is evaluated at each endpoint of each connecting line, the resulting value is interpolated along the connecting line, and the interpolated value of (1) is Y for any proportion of each line.₀Determine if the threshold is exceeded.

【0029】

It should be noted that the mesh is used to describe the region as a set of non-overlapping triangles or parallelograms, and at the vertices of each such triangle or parallelogram, the value of (1) is used. It is also possible to determine what proportion of triangles or parallelograms is covered. However, such techniques have some serious drawbacks. For example, this technique is not really needed to achieve the differentiability required for optimization, complicates interpolation conditions and is incompatible with real-world traffic.

【0030】

Therefore, the best set of test points should be based on knowledge of real-world traffic distribution. Road maps are an important source of data on the spatial distribution of wireless traffic. The reason is that, for example, many mobile phone calls are made on or near roads, and densely populated areas tend to have many roads. Another advantage of road maps is that they usually distinguish between small roads and various types of major roads. Therefore, the embodiments of the present invention use road maps to understand that the weights in the resulting mesh should match observed measurements such as traffic per base station sector. Provides details on how is distributed.

【0031】

The structure of the following description is as follows. Section 2 describes the conversion of road location data to an appropriately weighted network of connecting lines between test points. Section 3 describes how to interpolate RF link metrics along the edges of such a mesh. Section 4 describes an example of a mesh and shows that such a mesh produces a comparatively smooth function for network parameters such as coverage ratio.

【0032】

[2. Road Map Data] An example of a set of publicly available road maps for the United States (including Puerto Rico and the US Islands) is the US Census Bureau's Tiger database (TIGER / LINE 1997 Census Files). , Technical Report, Bereau of the Census, US Dept. of Commerce, Washington, DC, http://www.census.gov/geo/tiger/TIGER97D.pdf). This includes features such as rivers, railroads, administrative boundaries, and some types of buildings, in addition to roads. Roads are polygonal lines identified by names and categories such as "divided highway", "secondary road", "local road", etc. Given as. When two roads intersect, the two polygonal lines are guaranteed to intersect at exactly one vertex.

【0033】

According to the present invention, an edge weighted graph is defined using this set of exemplary road map data. Simply assign each polygon line segment its length and weights based on the above categories, and use a hash table to match the common vertices where the polygon lines intersect. The result can be stored as an edge weighted graph, along with an adjacency list of edges and longitude / latitude pairs of vertices. An example of such an edge weighted graph will be described below with respect to FIGS. 7 and 8.

【0034】

Map data may also be obtained in vector graphics formats such as DXF (described in AutoCAD 2000 DXF reference, http://www.autodesk.com/techpubs/autocad/dxf, 1999). Converting such data into an edge weight graph is similar to the above Tiger database data processing. However, it differs in that the input syntax is different and that manual work may be required if there are different types of roads on different DXF "layers". Since these layer names are not standardized, an edge weighting multiplier must be selected for each layer.

【0035】

[2.1 Finding Roads in Images] If the map is only available as an image file, converting it to an edge weighted graph generally requires vectorization. Vectorization is described, for example, in David S. Doermann, "An introduction to vectorization and segmentation", in GREG'97 Proc. Of 2nd IAPR Workshop on Graphics Recognition, pp.1-7,1997. Suppose that an automatic or semi-automatic method is available that determines which pixels in the image are drawing the road, eg, by selecting all the pixels of a color. This leaves the task of finding a vector description of the black and white image. The basic idea is to find the "skeleton" (skeleton) and then calculate the polygonal approximation that removes the pixel quantization noise by smoothing.

【0036】

Figure 2 shows, as an example, a part of a road map image together with its polygonal skeleton obtained using the Wakayama algorithm. The Wakayama algorithm is described in TadaoWakayama, "A core-line tracing algorithm based on maximal square moving", IEEE Transactions on Pattern Analysis and Machine Intelligence, 4 (1): 68-74, January 1982. In the figure, polygonal skeletons are marked with black dots and white lines. The noise that needs to be smoothed out is due to the way the white lines have a jagged appearance and the location of the black spots is affected by the pixel grid.

【0037】

Scan the vertices of this skeleton graph (ie, the black dots in the figure) to identify all vertices of order higher than 2. Then, the polygonal lines entering and exiting such vertices are subjected to polygonal approximation algorithms (eg, J. Sklansky and V. Gonzalez, "Fast polygonal approximation of digitized contours", Pattern Recognition, 12 (5): 327-331, Can be entered in 1980). This creates a network of polygonal lines. Each line corresponds to a specific part of the skeleton. Edge weights are obtained by counting the pixels of each line segment. The advantage of the Wakayama algorithm above is that it is relatively easy to count the image pixels of the individual parts of the skeleton. This result is improved by refining to fill the missing pixels (ie, non-road pixels surrounded by road pixels) before seeking the skeleton or after finding the skeleton and before removing the short side chains. can do.

【0038】

[2.2 Adding Edges] If map images are not available, a possible alternative approach is to distribute the test points in a pseudo-random manner with a probability based on the information available anyway. For example, if only elevation data is available, it can be assumed that the valley is more populous than the summit.

【0039】

Pseudo-randomly generated test points generally use the Delaunay triangulation algorithm (eg, SJ Fortune, "Voronoi diagrams and Delaunay triangulations", in FK Hwang and D.-Z. Du, eds., Requires an algorithm such as Computingin Euclidean Geometry, pp.193-233, World Scientific, 1992). Although this algorithm is acceptable, it is preferable to use a simpler algorithm for finding near-vertical and horizontal connecting lines as found on road maps.

【0040】

An example of such an algorithm is as follows. First, the vector (x, y) is divided into four quadrants based on the signs of x + y and xy. Then, for each quadrant, each test point (x)_i, y_i), The test point is (x)_j-x_i, y_j-y_i) Is the shortest possible Euclidean length and the test point (x) is within that quadrant._j, y_j). Test points like this (x_j, y_j) Is absent, or if the shortest Euclidean length is greater than a fixed lower bound (eg, one-sixth the diameter of a set of test points), the connecting line is not generated. Otherwise, the test point (x)_j, y_j), Test point (x)_i, y_i) Is called a quadrant-restricted nearest neighbor.

【0041】

It should be noted that (x_i, y_i) Is (x_i, y_i) Orthant constraint A test point (x) that is not one of the most recent contacts_j, y_j) Orthant constraint Since it can be a recent contact, this algorithm may generate a graph with vertices of degree greater than 4. If a more sparse graph is preferred, first the quadrant constraint adds only edges with symmetric recent contact relationships, then in ascending order of length, with the constraint that none of the vertices have a degree greater than 4. Add another edge at a time, one at a time.

【0042】

Using a simple brute-force search, it is possible to find all quadrant constraint recent contacts from a set of test points in quadratic time. If this is too slow, the sweep-line algorithm may give a better time limit.

【0043】

[2.3 Graph Simplification] Given the actual set of road map data has so many vertices and edges that it is not possible to use such a mesh to optimize coverage ratios and other network parameters. It can be practical. There are many ways to simplify the graph. One possibility is to crush (shrink) the shortest edge in the mesh and repeat this shrinking process as many times as needed in the revised mesh. When crushing an edge, its weight should be distributed to neighboring edges (preferably the edges that fall into the vertices created by crushing the edges). For more information on simplifying meshes by crushing edges, see, for example: Hugues Hoppe, "View-dependent refinement of progressive meshes", inComputer Graphics Proceedings, pp.189-198, 1997. Hoppe, "Progressive simplicial complexes", in Computer Graphics Proceedings, pp.217-224, 1997.

【0044】

[2.4 Adjust Edge Weights to Match Traffic Statistics] Before the graph above can be used as a traffic pattern for optimizing network parameters, the edge weights are used for all available traffic. It should be adjusted to match the data. For example, network statistics may be available that give traffic per base station sector. In this case, a propagation prediction model is used to determine which edge or part of it is assigned to each sector based on standard requirements (eg, best signal-to-interference ratio), and then traffic statistics for that sector. The edge weights can be readjusted to match.

【0045】

As an example, the weight w between test points i and j_ijEach of these test points has an edge of sector a_iAnd a_jSuppose you are in the cover area. Treating traffic as being distributed along the connecting edges is a percentage of the edges f_ijIs sector a_iRequire that it be treated as part of the cover area. This edge is sector a_iEdge weight of f_ijw_ijContributes to sector a_jTo the edge weight of (1-f_ij) w_ijMake a contribution. After adding up all such edge weights, for each sector a, there is a multiplier ω that must be multiplied by that edge weight to match the traffic statistic for that sector._aCan be calculated. w_i_jThe effect on edge weights such as is to multiply it by the following equation.

[Number 2]

<img file="JP2001203631A_D0002.tif" />【0046】

[3. Defining the RF link metric on the mesh] In the mesh for which the RF link metric is defined by the present invention, the edge weight represents the traffic, and the apex of the mesh is obtained from the measurement or the propagation model of the route loss data. It is a graph that seems to be a possible test point. This generally requires a set of interpolation rules to determine what happens along the edge given path loss data for the vertices at both ends of the edge. These rules preferably make it easy to determine how much of the edge is allocated to each sector based on standard requirements (eg, signal-to-interference ratio), and this is antenna tilt or power. It is set to be a reasonably smooth function of parameters such as levels.

【0047】

[3.1 Interpolation rule for signal-to-interference ratio] The signal-to-interference ratio (1) at vertex i is [Number 3]

<img file="JP2001203631A_D0003.tif" />Can be rewritten as. However, k where the maximum occurs gives the sector to which the vertex i is assigned, Sn_ikIs the signal-to-interference ratio for receiving the sector k at the vertex i, and is given by the following equation.

[Number 4]

<img file="JP2001203631A_D0004.tif" />Consider the edge between vertices i and j, both assigned to sector k. This is Sn for any other sector l_ik Sn_ilAnd Sn_jkAlso means that it is maximal at vertex j. A simple rule to determine what proportion of this edge is covered is the signal-to-interference ratio for sector k, Sn._ikAnd Sn_jkIt is treated as changing linearly between. For example, Sn_ik Y₀And Sn_jk Y₀If, of the edge [Number 5]

<img file="JP2001203631A_D0005.tif" />However, the signal-to-interference ratio threshold value Y₀Covered above.

【0048】

If the vertices i and j are assigned to different sectors k and l, the question of how much of the edge ij is covered concerns two different signal-to-interference ratios. In order to match the same sector interpolation rule above, it is set as follows. Sn_ijk(t) = (1-t) Sn_ik+ tSn_jk Sn_ijl(t) = (1-t) Sn_il+ tSn_jl (Four) This ensures that any percentage of the edge is assigned to sector k, any percentage is assigned to sector l, any percentage has a signal-to-interference ratio of Y.₀It is possible to calculate whether it is not covered because it is lower than the threshold value.

【0049】

In Fig. 3 (a) to Fig. 3 (d), Sn_ijk(t) and Sn_ijlThe plot of (t) is shown as a function of the proportion t along the edge ij from vertex i to vertex j for different types of coverage. The dashed line in each plot is the signal-to-interference ratio threshold Y₀Is. Figure 3 (a) shows the case where the edge ij is completely covered by two sectors. Figure 3 (b) shows the case where one end of the edge ij is covered by two sectors. Figure 3 (c) shows the case where the two sectors cover other than the central part of the edge ij. Figure 3 (d) shows the case where one end of the edge ij is covered by a single sector.

【0050】

Figure 4 shows an example of the more extreme case where linear interpolation of the signal-to-interference ratio along the edge ij splits the edge into parts assigned to four different sectors. The figure shows Sn for 4 different sectors a_ijaThe plot of (t) is shown as a function of the proportion t along the edge ij from vertex i to vertex j for different types of coverage. The dashed line in each plot is the signal-to-interference ratio threshold Y₀Is. In practice, it is possible to avoid this kind of complexity by ignoring sectors that are not assigned any endpoints of the edge and using only the highest signal-to-interference ratio in (4). Is. In return, such "injustice" can make it difficult to guarantee that a performance measure such as a cover register is a continuous function of network tuning parameters such as antenna tilt.

【0051】

[3.2 Smoothness and Derivatives] The purpose of the above interpolation rules is to provide an approximation of the actual conditions, while ensuring that network performance measures such as coverregs do not show discontinuities that make optimization difficult. is there. Some degree of discontinuity can also be tolerated if it requires an unlikely coincidence and the optimization algorithm is unlikely to be derived by that coincidence. However, it is still desirable to try to avoid discontinuity. Sn for a sector a_ija(t) Y₀The percentage of edge ij such as_ijIf, each C_ijIf is a continuous function of parameters, then cover [Number 6]

<img file="JP2001203631A_D0006.tif" />Is clearly a continuous function of parameters.

【0052】

In the situation shown in Fig. 3 (a) to Fig. 3 (d), C_ijShows no discontinuity. The reason is that infinitesimal changes in parameters are Sn._maAt each test point m and Sn for each sector a_maGenerates an infinitesimal change of, and also Sn_ijk(t) and Sn_ijlThis is because it generates an infinitesimal shift of the function of (t).

【0053】

In such cases, C for any network parameter_ijThe derivative of is the derivative Sn of the signal-to-interference ratio at each vertex._ik, Sn_il, Sn_jk, Sn_jlIt can be represented by . For example, C_ijReduces to (3) in the situation of Fig. 3 (d), and its derivative is as follows.

[Number 7]

<img file="JP2001203631A_D0007.tif" />【0054】

Figure 5 (a) and Figure 5 (b) show C_ijSn as a function of proportion t in situations where_ijk(t) and Sn_ijlThe plot of (t) is shown. Again, for each plot, the dashed line is the threshold Y₀give. The potential problem shown in the plot in Figure 5 (a) is Sn._ijk(t) is Y₀If it becomes constant, the denominator of (5) becomes 0. As is clear from (4), Sn_ikOr Sn_jkInfinitesimal change of the function Sn_ijkSn to shift (t) downward_ijk(t) is Y₀Smaller and half of the edges are no longer covered, C_ijSuddenly drops from 1 to 0.5.

【0055】

Another potential problem is if the interpolation rules are simplified to avoid the complexity of Figure 4 by considering only the two sectors with the highest signal-to-interference ratio for the endpoints of each edge. Occurs in. Seeing Figure 5 (b), Sn_jl= Sn_jlSn to be_ijl(1) = Sn_ijlIn the case of (1), the infinitesimal change can determine whether l or l'is in the ignored third sector. This leads to significant discontinuity. Sn_ijlSn instead of (t)_ijlIgnoring (t), C_ijIncreases from 67% to 93%.

【0056】

The contextual discontinuities shown in Figures 5 (a) and 5 (b) are part of the optimization process (eg Philip E. Gill, Walter Murray, and Michael A. Saunders, Technical Report NA 97-2, Dept. The process described in .of Math., UC San Diego, 1997) may not cause problems, but such discontinuities can still be removed if necessary. For example, in order to eliminate the problem shown in Fig. 5 (b), all sectors a are considered at the signal-to-interference ratio t along the edge ij in the definition of the following equation.

[Number 8]

<img file="JP2001203631A_D0008.tif" />Eliminating the problems shown in Figure 5 (b) generally requires a soft threshold. That is, [Number 9]

<img file="JP2001203631A_D0009.tif" />And. However, Cov (s) is s Y₀0, s Y₀Any smooth function that is 1 in. Depending on these conditions, each C_ijIs a function that is continuously and piecewise differentiable with respect to network parameters.

【0057】

[3.3 Interpolation rules for other RF link metrics] Next, the interpolation rules for RF link metrics other than the signal-to-interference ratio will be described. In general, it is not safe to linearly interpolate all metrics. The reason is that this can violate mathematical relationships between RF link metrics, such as the rules for calculating signal-to-interference ratios from path loss. However, other RF link metrics can be calculated immediately from the received power level, which is particularly strongly dependent on the distance from the base station, so such received power levels are described below. As such, it is possible to interpolate to match the interpolated signal-to-interference ratio.

【0058】

Linear interpolation function Sn for all n sectors a_ijaUsing (t) gives the complete set of signal-to-interference ratios (from which the received power can be calculated in principle). However, this usually involves excessive complexity and may not give a valid answer, so it is preferable to use a simpler approach.

【0059】

The basis for this simplification is that only a few Sns are usually needed to define the signal-to-interference ratio as a function of the percentage t of the paths along the edge ij._ija(t) It is only a function, and these values of a are only in the sectors where the received power estimate is likely to be needed. n receive powers are selected and the signal-to-interference ratio is Sn_ijaSince there are only a few (usually much smaller than n) that are supposed to match the (t) function, we can make further assumptions so that the equation based on (2) can be solved for the received power.

【0060】

Generalizing (2) so that the path along the edge from vertex i to vertex j holds at a certain ratio t, the following equation is obtained.

[Number 10]

<img file="JP2001203631A_D0010.tif" />However, s_ij(t) is s_ij(0) = s_iAnd s_ij(1) = s_jInterpolation function that satisfies E_ijk(t) is a function determined to give the power received from the antenna k. The above "further assumption" is s_ij(t) is the following linear interpolation. s_ij(t) = (1-t) s_i+ ts_j (7) This makes (6) E_ijkIt becomes possible to solve (t), and the following equation is obtained.

[Number 11]

<img file="JP2001203631A_D0011.tif" />However, s_ij(t) is as in (7), Sn_ija(t) is as in (4).

【0061】

[4. Example Results] Figure 6 shows the antenna downtilt function for the cover area assigned to a specific one of the three cell sectors using the set of road map examples from the Tiger database above. The plot of all edge weights (unit: erlang) is shown as. The set of road data used in this example is San Juan, Puerto Rico. Juan), edge weights are based on road type and traffic statistics per sector. Figure 7 shows a portion of the unsimplified traffic distribution graph for a portion of the San Juan region. The line width in the graph is based on the edge weights per unit length. The traffic distribution graph for the entire San Juan region had 45,358 vertices and 54,875 edges. The simplification by crushing the edges as described in Section 2.3 above resulted in 9071 vertices and 12241 edges, but still to a reasonable degree for each of the 169 sectors in total. Provided details. Figure 8 shows a portion of the resulting simplified traffic distribution graph that corresponds to the non-simplified graph in Figure 7. The traffic distribution graphs of FIGS. 7 and 8 are examples of "mesh" that can be used in road-based estimation / interpolation according to the present invention.

【0062】

The plot in Figure 6 shows how the total edge weight covered by a particular sector depends on the downtilt of that antenna. As can be clearly seen from FIG. 6, the edge-based interpolation technique in Section 3 gives the coverage for this sector a as a much smoother function of its downtilt. Since the total coverage ratio is the sum of such functions multiplied by a constant, it exhibits the same behavior except for some tendency to smooth and remove the discontinuity. This applies to the discontinuity in the dashed curve and the gradient discontinuity in the solid curve, but the effect is rather small. This is because simply readjusting the antenna tilt has a large effect on the coverage of several neighboring sectors.

【0063】

[Effect of the invention]

[5. Conclusion] The present invention uses road position data (for example, road map data) to estimate and interpolate network parameters of a wireless network. Such road location data can be used to obtain accurate estimates of actual traffic distribution in wireless networks. According to the present invention, the traffic distribution based on the road map can be easily adjusted to the observed value of the traffic per antenna in the actual network, and the test is much less than the conventional approach such as sampling on a uniform grid. I only need points. Also, the road-based interpolation approach of the present invention provides interpolation rules that produce a noise-free network performance measure that makes it much easier to apply automatic optimization algorithms.

【0064】

It should be noted that the present invention is at least partially feasible in the form of one or more software programs (eg, software program instructions executed by processor 12 of system 10). A properly configured software program according to the invention obtains network parameter and road location data from, for example, one or more sources and processes the network parameter data according to the road-based interpolation process according to the invention described above. It produces a display or other suitable output that presents the resulting network configuration information in the desired format.

【0065】

The above embodiment of the present invention is merely an example. For example, the techniques described above can be used to design wireless networks or to optimize or improve existing networks that are already in operation. In addition, the present invention relates to subnetworks (eg, designated parts of a given wireless network) and many different types of networks (eg, mobile subscribers or fixed subscribers or mobiles and fixeds). It is also applicable to networks with combinations).

[Simple explanation of drawings]

[Figure 1]

It is a block diagram of the processing system which can realize the estimation / interpolation based on the road by this invention.

[Figure 2]

It is a figure which shows a part of the road map image which can be used in the process of estimation / interpolation based on the road by this invention.

[Fig. 3]

It is a figure which shows the plot of the signal-to-interference ratio for the different two-sector coverage arrangement.

[Fig. 4]

It is a figure which shows the plot of the signal-to-interference ratio with respect to the 4-sector coverage arrangement.

[Fig. 5]

It is a figure which shows the plot of the signal-to-interference ratio for the different two-sector coverage arrangement that the edge coverage function may be discontinuous.

[Fig. 6]

It is a figure which shows the plot of the traffic as a function of the antenna down tilt for a specific antenna sector in the Example of this invention.

[Fig. 7]

It is a figure which shows the example of the unsimplified edge weighted traffic distribution graph used in the process of estimation / interpolation based on the road by this invention.

[Fig. 8]

It is a figure which shows the example of the simplified edge weighted traffic distribution graph used in the process of estimation / interpolation based on the road by this invention.

[Explanation of symbols]

10 Processing system 12 processors 14 memory 16 bus 18 Input / output (I / O) controller 20 display 22 printer 24 keyboard 26 External storage