Estimation of Mobility for Network Planning Based on Highway Maps and Traffic Data

1. Technical Field

The present invention relates generally to wireless digital communications systems and in particular to wireless digital communications systems employing code division multiple access or the like within a geographic region having empirically measurable traffic patterns. Still more particularly, the present invention relates to minimizing inter-switch handoff of expected service to mobile subscriber units within a code division multiple access wireless digital communications network.

2. Description of the Related Art

Digital telecommunications networks are increasingly based on code division multiple access (CDMA), a form of spread spectrum multiple access. Each signal within a CDMA system occupies all of the bandwidth all of the time. Separation of the signals depends on each being carried by an underlying waveform which is nearly orthogonal to all other signals. Digital codes are employed in CDMA to form the underlying quasi-orthogonal waveforms. Each user within a CDMA systems has a unique long period digital sequence called a pseudorandom sequence, which appears random to a casual observation of insufficient duration. This sequence is usually either (1) combined directly with the information stream to be sent, as in direct sequence transmission, or (2) used to select pre-planned spectrum channels among which the transmission is hopped, as in frequency hopping transmission.

CDMA provides a degree of protection against frequency-selective fading and reduces multipath interference. Signals which arrive late at the receiver do not match the portion of the code currently being utilized to decode the signal, and are thus rejected as interference. CDMA is also excellent in discriminating against noise. However, all signals within a given spectrum other than the signal of interest are treated as noise by a CDMA unit. Therefore, as more users attempt to communicate via a particular spectrum, performance for all users of that spectrum gradually degrades.

A cellular CDMA systems includes base transceiver stations (BTS's) or repeaters, referred to herein as cells, from which signals are routed into mobile switching centers (MSC), also called mobile telecommunications switching offices (MTSO) or electronic mobile exchanges (EMX) but referred to herein as simply switches. When a mobile unit moves across cell boundaries, an automatic handoff occurs. Depending on whether the two cells--current and destination--are routed to the same switch or to different switches, the type of handoff which occurs may be classified as intra-switch or inter-switch, respectively.

An intra-switch handoff is implemented as a soft handoff, in which a subscriber set near a cell boundary is served by two cells simultaneously. Concurrent service from both the old and new cells as the mobile subscriber crosses cell boundaries results in a smooth transition from cell to cell, with no noticeable change in voice quality. An inter-switch handoff, on the other hand, is implemented as a hard handoff, with the potential for a brief discontinuity of services from the two cells, where a first cell disconnects before the second cell, to which service has been handed off, completes a connection. This potential discontinuity results in a short disruption in the communication link, thereby causing a momentary degradation of the voice quality. Additionally, due to the large amount of information that needs to be transferred from one switch to another during a hard handoff, the inter-switch handoff consumes a larger amount of switch processor time than an intra-switch handoff. It is desirable, therefore, to minimize the number of inter-switch handoffs to the extent possible for typically mobile subscriber usage. The number of inter-switch handoffs may be controlled by the way cells are assigned to switches. However, cell usage by mobile subscribers and cell coverage depend in part on traffic patterns and the terrain within the cell, respectively.

Where the location and boundaries of each cell in a network and the number of switches in the network are known, it would be desirable to partition the cells among the switches in such a manner as to minimize the number of inter-switch handoffs. It would further be desirable to utilize available traffic and terrain data to partition cells in a given geographic area among the switches available to minimize the number of expected inter-switch handoffs. It would further be advantageous if the process developed could be applied to partitioning a new network based on geographical and traffic flow information, as well as to repartitioning existing networks based on operational mearurements.

It is therefore one object of the present invention to provide an improved wireless digital communications systems.

It is another object of the present invention to provide an improved wireless digital communications system employing code division multiple access or the like within a geographic region having empirically measurable traffic patterns.

It is yet another object of the present invention to minimize inter-switch handoff of expected service to mobile subscriber units within a code division multiple access wireless digital communications network.

The foregoing objects are achieved as is now described. The mobility of mobile subscribers within a wireless digital communications system is estimated based on highway maps and traffic data. Cells within the network are modelled as nodes connected by edges where neighboring cells are connected by roads. Each edge has two edge weight components representing traffic flow from one cell to the other and vice versa. The edge weight components are calculated from terrain factors based on the size or capacity of the roads connecting the two cells and the total traffic within the subject cell, which information may be obtained from commercial geographic databases and/or government agencies. The resulting edge weight represents an expected number of handoffs between the two cells. The problem of partitioning cells among available switches within the network is thus reduced to the purely mathematical problem of minimizing the total edge weights of edges intersected by the partition boundaries. Existing mathematical optimization techniques for optimizing node-edge systems may therefore be applied to reduce the total number of expected inter-switch handoffs as mobile subscribers pass from cell to cell within the network.

The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 depicts a block diagram of a portion of a digital communications network in which a preferred embodiment of the present invention may be implemented;

FIG. 2 is a diagram of a cell arrangement within a digital communications network in accordance with a preferred embodiment of the present invention;

FIG. 3 depicts a block diagram of a data flow associated with optimizing the routing of cells to switches within a wireless digital communications network in accordance a preferred embodiment of the present invention;

FIG. 4 is a high level flowchart for a process of partitioning cells among available switches in accordance with a preferred embodiment of the present invention;

FIG. 5 depicts a diagram of the model employed in partitioning cells among available switches in accordance with a preferred embodiment of the present invention is depicted;

FIG. 6 is a high level flowchart for a process of optimizing the partitioning of cells among available switches in accordance with a preferred embodiment of the present invention;

FIG. 7 depicts an ad hoc partition of cells having defined locations and boundaries among two switches within a wireless digital communications system;

FIGS. 8A-8B are the results of partitioning the cells of FIG. 7 among two switches in accordance with a preferred embodiment of the present invention;

FIGS. 9A-9B depict the results of partitioning the cells of FIG. 7 among three switches in accordance with a preferred embodiment of the present invention; and

FIGS. 10A-10B are the results of partitioning the cells of FIG. 7 among four switches in accordance with a preferred embodiment of the present invention.

With reference now to the figures and in particular with reference to FIG. 1, a block diagram of a portion of a digital communications network in which a preferred embodiment of the present invention may be implemented is depicted. Network 102 includes a plurality of switches 104 and 106, such as the Nortel MTX switch available from Northern Telecom Limited. Connected to each switch 104 and 106 are sets of repeaters or base transceiver stations (BTS's) 108-114 and 116-122, respectively. Each BTS 108-122 defines a cell within the overall network. Although only four BTS's are depicted connected to each switch, those skilled in the art will recognize that many more BTS's may be routed to each switch within network 102.

Referring to FIG. 2, a diagram of a cell arrangement within a digital communications network in accordance with a preferred embodiment of the present invention is illustrated. Network 102 includes a plurality of cells, with cells 202 in urban areas smaller and denser than cells 204 in rural areas. The cell locations and boundaries are defined, as is the number of switches in network 102. However, cells are routed to specific switches within the network in such a manner as to minimize the number of expected inter-switch handoffs of mobile subscriber units passing between cells given the traffic flow and terrain within network 102.

With reference now to FIG. 3, a block diagram of a data flow associated with optimizing the routing of cells to switches within a wireless digital communications network in accordance a preferred embodiment of the present invention is depicted. Initial data is obtained through PLANET, as depicted in block 302. PLANET is a commercial radio frequency calculator software package. The initial data includes the location and boundaries of each cell. The initial data also includes the total traffic in each cell and the type of road that connects each pair of neighboring cells, which may be obtained from a geographical database, estimations, and/or marketing research.

The initial data is pre-processed as illustrated in block 304 using mathematical calculator software such as Matlab, a commercially available product. The pre-processing converts the initial data into a format recognized by the optimization routine. The formatted initial data is then passed to the optimization routine as depicted in block 306. The optimization routine, which in the exemplary embodiment is written in C, attempts to find the optimal partition of cells to the available switches. The output of the optimization routine is post-processed as illustrated in block 308 using Matlab to convert the output to a format recognized by the visualization software. The formatted output data may then be passed as depicted in block 310 to the visualization software, which may be either PLANET or MATLAB. The exemplary embodiment utilizes Matlab, which may be utilized to generate graphical representations of the output data such as those described below.

Referring to FIG. 4, a high level flowchart for a process of partitioning cells among available switches in accordance with a preferred embodiment of the present invention is illustrated. The process begins at step 402, which illustrates receiving the formatted initial data required. This initial data includes the cell locations and boundaries, the total automobile traffic in each cell, and the type of roads which connects each pair of neighboring cells. The initial data may also include the automobile traffic from each cell to each neighboring cell and the automobile traffic from neighboring cells into each cell. The process then passes to step 404, which illustrates defining a node for each cell within the system for the purposes of modelling the system. Step 404 is the first step in modelling the system for optimizing partitioning of cells among available switches.

With reference now to FIGS. 5A and 5B, a diagram of the model employed in partitioning cells among available switches in accordance with a preferred embodiment of the present invention is depicted. In order to apply powerful existing numerical optimization methods to the problem of partitioning cells among available switches, an abstract model of a wireless digital communications network is constructed. The model employed according to the present invention is a graph consisting of nodes and edges. Each node represents a cell, such as cell A 502, cell B 504, or cell C 506 depicted in FIG. 5A. Each edge between two nodes represents the roads, such as roads 510 and 512 depicted in FIG. 5A, connecting the corresponding cells. Each edge has two associated edge weight components: one edge weight component representing traffic flow from a first cell into the second, and a second edge weight component representing traffic flow from the second cell into the first.

The arrangement depicted in FIG. 5A may be modelled as shown in FIG. 5B. Node 520 represents cell A, node 522 represents cell B, and node 524 represent cell C. Edge 526 connecting nodes 520 and 522 includes two associated weights: edge weight 526a representing traffic flow from cell A into cell B and edge weight 526b representing traffic flow from cell B into cell A. Similarly, edge 528 connecting nodes 520 and 524 includes associated edge weight 528a representing traffic flow from cell A into cell C and edge weight 528b representing traffic flow from cell C into cell A. Note that no edge connects nodes 522 and 524 because no roads connect cell B and cell C. Alternatively, the model may be viewed as including an edge between nodes 522 and 524, but with a total edge weight of zero.

Using the model described, minimization of the total number of expected inter-switch handoffs for a defined network reduces to partitioning the model graph into a given number of subgraphs, with the number of subgraphs corresponding to the number of available switches. The model graph is partitioned in such a way as to minimize the total sum of edge weights which are cut by the partition. Because the original problem is transformed under the model into a pure mathematical problem, existing software implementing a powerful algorithm with good theoretical properties may be employed to solve the problem.

Referring again to FIG. 4, the process continues from step 404 with the modelling of the system in accordance with the model described above. The process passes to step 406, which depicts selecting a neighboring pair of cells within the system. The process then passes to step 408, which illustrates a determination as to whether the cell pair selected is connected by at least one vehicular traffic path, such as a road, rail line, etc. If not, the process proceeds to step 414, which is described below. If at least one road or rail line connects the selected cell pair, however, the process proceeds to step 410, which depicts defining an edge between the nodes corresponding to each cell within the selected cell pair. The process then passes to step 412, which illustrates calculating terrain factors for the cells within the selected cell pair and an edge weight for the edge.

The calculation of edge weights (or estimation when actual data is not available) illustrated in step 412 is an important necessary step for partitioning the cells among available switches in accordance with the present invention. The edge weights are defined as functions of both the vehicular traffic (as opposed to call traffic) in the cells and the types of roads or rail lines connecting neighboring cells. The higher the total vehicular traffic within a cell, it may be inferred, the higher the vehicular traffic from that cell to a specific neighboring cell. Also, the larger the size of the roads which connected the cell to that specific neighboring cell, the higher the vehicular traffic going from the cell to that specific neighboring cell.

The validity of these inferences may be established from traffic flow data obtained from an appropriate government agency, and may be tested with reference to the arrangement depicted in FIG. 5A. Road 510 connecting cell A 502 to cell B 504 in the depicted example is a highway while road 512 connecting cell A 502 to cell C 506 is a small street. The larger street between cell A 502 and cell B 504 implies that more traffic will pass from cell A 502 into cell B 504 than from cell A 502 into cell C 506. Thus a terrain factor may be associated with each pair of neighboring cells, the terrain factor corresponding to the types of roads connecting the two cells and having a larger value when the connecting roads are larger. For the purposes of the model being utilized, terrain factor components of three values may be employed: a terrain factor component of 10 for each major highway connecting the two cells; a terrain factor component of 6 for medium sized roads; and a terrain factor component of 4 for small roads. The terrain factor for two cells will equal the sum of the terrain factor components for all roads connecting the two cells. It will be understood that any number of terrain factors may be utilized, and that any values may be utilized for the terrain factors. Where data regarding the actual average traffic per day on a given road or road segment is available, for example, these numbers may be used directly as terrain factors.

It may be reasoned, that the edge weight associated with traffic going from cell A into cell B is equal to the traffic volume in cell A times the terrain factor corresponding to cells A and B. Similarly, the edge weight associated with traffic going from cell B into cell A is equal to the traffic volume in cell B times the terrain factor corresponding to cells A and B. The validity of these relationships may be shown to hold using a more rigorous approach. The edge weight associated with handoffs from cell A to cell B (E[HO.sub.A.fwdarw.B ]) may be expressed as: ##EQU1## where E[HO.sub.A ] is the edge weight associated with all handoffs from cell A to neighboring cells. The edge weight E[HO.sub.A ] may itself be expressed as: ##EQU2## where E[HO/call.sub.A ] is an edge weight associated with the average number of handoffs per call within cell A and Erlangs.sub.A is the average traffic load (usage) of cell A in terms of the average number of users requesting service resulting in the probability that a new user will find all channels busy and hence be denied service in cell A. The edge weight associated with average number of handoffs per call within cell A may be further expressed as: ##EQU3## where E[HO/call] is the edge weight associated with the average number of handoffs per call within the entire network or system. Combining equations (1), (2), and (3), the edge weight associated with handoffs from cell A to cell B may be compactly expressed as:

where ##EQU4## is constant over all cells within the network or system. As described above, the edge weight associated with handoffs from cell A to cell B is equal to the total traffic in cell A times a terrain factor corresponding to cells A and B.

Referring again to FIG. 4, the process depicted proceeds from calculation of terrain factors and an edge weight in step 412 to step 414, which depicts a determination of whether all unique neighboring cell pairs within the system have been examined. If not, the process returns to step 406 for examination of another cell pair. If so, however, the modelling of the system is complete and the process proceeds to step 416, which illustrates optimizing the partition of cells between available switches based on the edge weights as described below with respect to FIG. 6. The process then passes to step 418, which illustrates the partitioning process becoming idle until again required.

Referring to FIG. 6, a high level flowchart for a process of optimizing the partitioning of cells among available switches in accordance with a preferred embodiment of the present invention is illustrated. The process depicted is described in B. W. Kernighan & S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Sys. Tech. J., pp. 291-307 (February 1970) and S. Subramanian & S. Madhavapeddy, "System Partitioning in a Cellular Network," Proceedings VTC, pp. 106-110 (April 1996). The process begins at step 602, which depicts receiving the edge weights associated with the model of the system being partitioned, together with an existing ad hoc partition of cells among the available switches. The process then passes to step 604, which illustrates selecting a pair of nodes within the system, the node pair including a node in each partition, and swapping the nodes between the partitions. The process next passes to step 606, which depicts calculating a gain (decrease) in the partition crossing edge weights--that is, edge weights which the partition crosses--resulting from the swap. The process then passes to step 608, which illustrates a determination of whether all node pairs have been examined. If not, the process returns to step 604 for selection of a new node pair and repetition of step 606. In this manner, the process generates gain for each node pair within the system.

Once the gain for each prospective node pair is calculated, the process proceeds to step 610, which depicts ordering the node pairs in an indexed array of descending order of the computed gains. Once the array has been generated, the process proceeds to step 612, which illustrates locating the maximal gain index to the array. The maximal gain index identifies the point within the array where the summation of gains up to and including the selected index position is maximized. The process then passes to step 614, which depicts aggregating all node pairs having an index which is not larger than the maximal gain index into a single pair of nodes. The process next passes to step 616, which illustrates swapping the aggregate node pair, and then to step 618, which depicts the process becoming idle until again required.

When there are more than two switches in a system to be partitioned, the process described may be extended by working with two switches at a time and applying process described above for partitioning a two-switch system. By sequentially working through all possible pairs of two switches for the system, the two-switch process is effectively generalized for optimizing partitioning of an n-switch system.

The process described above assumes that the partition is balanced, i.e., that the number of cells routed to each switch is equal. Where there is no strict requirement that the same number of cells be routed to each switch, or at most the partitioning problem is only bounded by ranges of cell numbers which may be routed to each switch, dummy nodes may be added to the model. Dummy nodes represent fictitious cells and have no edges to any other nodes. Dummy nodes are assigned a unit node weight, effectively transforming the model back into a balanced partition. Once the final partition is found, the dummy nodes are discarded to yield a solution which contains only real cells and is weight-minimized. The number of dummy nodes added to a model may be selected according to the requirements on the range of the cell numbers which may be routed to each switch. A software implementation of this process is commercially available.

The process described above may be applied to both partitioning new networks and repartitioning existing networks. When applied to partitioning a new network, the model is constructed with terrain factors and edge weights derived from road data, available from any commercial geographical database, and traffic flow data, which is typically available from one or more government agencies (such as a state Department of Transportation). When applied to repartitioning or optimizing existing networks, however, operational measurements may be utilized. Typically switches are equipped with a plurality of counter for tracking handoffs from each cell to each other cell neighboring the first cell. These measurements may be utilized--alone or in conjunction with road data and traffic flow information--to defined terrain factors and edge weights in modelling the existing network.

With reference now to FIGS. 7, 8A, and 8B, comparative results of partitioning cells having defined locations and boundaries among two switches within a wireless digital communications system in accordance with a preferred embodiment of the present invention are depicted. FIG. 7 depicts cell locations for a wireless digital communications network for a typical metropolitan trading area (MTA), demonstrating that the present invention may be applied to new or existing networks at any geographic location. The network is modelled as nodes and edges in accordance with a preferred embodiment of the present invention. The x- and y-axis of the plot depicted defines the grid location of a base transceiver station for a cell. An ad hoc partition of the cells among two switches results in 142 cells being allocated to a first switch and 80 switches allocated to a second switch. Utilizing terrain factors of 10, 6 and 4 as described earlier in conjunction with available traffic data, edge weights are calculated. The ad hoc partition results in edges with a total weight of 310.4 being cut, representative of the number of inter-switch handoffs which may be expected to occur within the network from which the results are drawn.

Referring to FIG. 8A, the same network as that depicted in FIG. 7 is illustrated with the partition of cells among the two switches optimized in accordance with the present invention. The same terrain factors and traffic data are utilized, together with dummy nodes to emulate a balanced partition. The optimization results in 139 cells being allocated to the first switch and 83 being allocated to the second switch, a change of three cells from the ad hoc partition. From the same edge weights between nodes employed for the partition characterized in FIG. 7, the new partition results in edges with a total weight of only 147.6 being cut. Thus, for the optimized partition there is a decrease of approximately 50% in the number of expected inter-switch handoffs over the ad hoc partition. FIG. 8B is a table listing cell names according to the switch to which the cells are allocated under the optimized partition.

With reference to FIGS. 9A and 9B, the results of partitioning the cells of FIG. 7 among three switches in accordance with a preferred embodiment of the present invention are depicted. In some cases additional switches may be required for the future, due to an increase in the number of subscribers and a corresponding increase in the number of cells. FIG. 9A illustrates the results of optimizing the partitioning of the existing cells depicted in FIG. 7 among three switches as described above. The same terrain factors and traffic data are again employed, resulting in allocation of 71 cells to a first switch, 83 cells to a second switch, and 68 cells to a third switch within the network. The two partitions combined cut edges having a total weight of 497.0, representing an expected number of inter-switch handoffs for the three switch system. FIG. 9B lists the cell names according to the switches to which they were allocated.

FIGS. 10A-10B are the results of partitioning the cells of FIG. 7 among four switches in accordance with a preferred embodiment of the present invention. Again, the same terrain factors and traffic data are employed to optimize the partitioning of the existing cells depicted in FIG. 7 among four switches using the process described earlier. FIG. 10A depicts the resulting allocation of cells: 61 to a first switch, 46 to a second switch, 61 to a third switch, and 54 to a fourth switch. The three partitions together cut edges having a total weight of 581.6, representing an expected number of inter-switch handoffs for the four switch system. FIG. 10B lists the cell names according to the switches to which they were allocated.

In both the three switch and four switch cases demonstrated, the process of the present invention for optimizing the partitioning of cells among the available switches will almost always find a solution with significantly reduced total edge weights cut by the partitions in comparison to ad hoc or rule-of-thumb methods.

Although described in the context of cells, the present invention may also be employed in the context of cell sectors. In a typical wireless communications network, each cell is usually divided into a number of sectors, generally either three (120.degree. sectors) or six (60.degree. sectors), with multiple base transceiver stations having directional antennas employed to service each sector. While sectors for the same cell are normally routed to the same switch, there are no technical limitations requiring adherence to this convention. Each sector may be individually routed, improving the granularity of the partitions and potentially achieving even further reductions in inter-switch handoffs. In such a circumstance, each sector would be modeled as a node and each edge weights defined for traffic into and out of adjoining sectors, regardless of whether the sectors may be found in the same cell.

The present invention provides a method of estimating mobility based on road maps and traffic data for planning a wireless digital communications network. Cells are modelled as nodes connected by edges where the cells are connected by roads. Each edge includes two edge weight comparisons representing the traffic flow from one cell to the other and vice versa. Partitioning the cells among available switches is thus reduced to a purely mathematical problem of minimizing the total weights of edges cut by the partition boundaries. Therefore, powerful existing algorithms may be applied to the problem of optimizing the partitions. Using the optimization of the present invention, it is possible to drastically reduce the number of expected inter-switch handoffs. This will improve overall voice quality of the services provided and save processor time within the switches of the system. It should be noted that the methodology applied to optimizing partitioning of cells among available switches may be applied to other problems in configuring wireless digital communications networks, such as location area optimization and base station controller partitioning.

It is important to note that while the present invention has been described in the context of a fully functional communications system, those skilled in the art will appreciate that the mechanism of the processes of the present invention is capable of being distributed in the form of a computer readable medium of instructions in a variety of forms, and that the present invention applies equally regardless of the particular type of signal bearing media used to actually carry out the distribution. Examples of computer readable media include: recordable type media such as floppy disks and CD-ROMs and transmission type media such as digital and analog communication links.

The description of the preferred embodiment of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limit the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.