Road-based evaluation and interpolation of wireless network parameters

• US 6,631,267 B1
• Filed: 11/04/1999
• Issued: 10/07/2003
• Est. Priority Date: 11/04/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hobby, John D., Hampel, Karl Georg, Polakos, Paul Anthony, Clarkson, Kenneth L.
• Primary Examiner(s): Bost, Dwayne
• Assistant Examiner(s): SHARMA, SUJATHA R
• Application Number:
  US09/434,580
• Time in Patent Office: 1,433 Days
• Field of Search: 455/446, 455/67.1, 455/67.3, 455/423-425, 455/67.7, 370/397, 340/934, 340/905
• US Class Current: 455/446
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition

Abstract

Techniques for determination of network parameters in, e.g., a processor-implemented system for characterizing, adjusting or optimizing the performance of a wireless network. In an illustrative embodiment, values of one or more link parameters of the wireless network are interpolated along edges in a mesh of data points derived at least in part from road location data characterizing an area serviced by the wireless network. A measure of network performance, e.g., a coverage measure based on pilot signal-to-interference ratio, may be generated using the interpolated values. The edges of the mesh have associated therewith a set of edge weights representative of traffic in the wireless network. The edge weights may be adjusted so as to be in agreement with available network traffic data. Interpolating between the data points of the road-based mesh permits the network performance measure to be computed as a smooth, differentiable function of the one or more link parameters, thereby simplifying network characterization, adjustment and optimization.

Claims

1. A processor-implemented method for characterizing the performance of a wireless network, the method comprising the steps of:

determining values of at least link parameter of the wireless network over a set of data points derived at least in part from road location data over at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weight traffic distribution graph; and

utilizing the determined values to generate a network performance measure;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.

2. The method of claim 1 wherein the step of determining values comprises utilizing a link model to determine the values.

3. The method of claim 1 wherein the road location data is derived from road map data.

4. The method of claim 1 wherein the road location data is derived from one or more image files.

5. The method of claim 4 wherein the road location data are derived from the image file by first generating a skeleton graph and subsequently applying a polygonal approximation to the skeleton graph.

6. The method of claim 1 wherein a value of at least one link parameter of the wireless network is evaluated on a mesh comprised of at least a subset of the data points and a plurality of corresponding interconnecting edges.

7. The method of claim 6 wherein a value of at least one link parameter of the wireless network is evaluated by interpolating along one or more of the edges.

8. The method of claim 6 wherein each of at least a subset of the edges corresponds at least in part to one or more roads.

9. The method of claim 6 wherein associated with the edges of the mesh are a plurality of edge weights.

10. The method of claim 9 wherein at least a subset of the edge weights represent traffic in the wireless network.

11. The method of claim 9 wherein at least a subset of the edge weights are adjusted so as to be in agreement with available network traffic data.

12. The method of claim 6 wherein the mesh comprises an irregular mesh generated by applying at least one simplifying operation to a finer mesh generated from the road location data.

13. The method of claim 12 wherein the simplifying operation comprises an edge collapsing operation.

14. The method of claim 7 wherein the interpolating step permits the network performance measure to be computed as a smooth function of the at least one link parameter.

15. The method of claim 1 wherein the link parameter comprises a signal strength.

16. The method of claim 1 wherein the link parameter comprises a signal-to-interference ratio.

17. The method of claim 1 wherein the link parameter comprises a path loss.

18. The method of claim 1 wherein the link parameter is used to generate a measure of network performance.

19. The method of claim 18 wherein the network performance measure comprises a network coverage measure.

20. The method of claim 18 wherein the network performance measure comprises a network capacity measure.

21. The method of claim 18 wherein the network performance measure is generated at least in part using values interpolated along edges in a mesh of data points.

22. The method of claim 18 wherein the network performance measure is at least in part a differentiable function of a network parameter.

23. The method of claim 22 wherein the network performance measure is differentiated with respect to a network parameter along edges in a mesh including at least a subset of the data points.

24. The method of claim 22 wherein the network performance measure is optimized with respect to the network parameter using a derivative-based algorithm.

25. The method of claim 19 wherein the network coverage measure comprises a fraction of a target coverage area having at least one link parameter above a specified threshold.

26. An apparatus for characterizing the performance of a wireless network, the apparatus comprising:

a processor-based system comprising a processor coupled to a memory and operative to determine values of at least one link parameter of the wireless network over a set of data points derived at least in part from road location data over at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weighted traffic distribution graph, and to utilize the determined values to generate a network performance measure;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.

27. An article of manufacture comprising a computer-readable medium storing one or more software programs for use in characterizing the performance of a wireless network, wherein the one or more programs when executed by a processor perform the steps of:

determining values of at least one link parameter of the wireless network over a set of data points derived at least in part from road location data over at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weighted traffic distribution graph; and

utilizing the determined values to generate a network performance measure;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.

28. A processor-implemented method for characterizing the performance of a wireless network, the method comprising the steps of:

interpolating values of at least one link parameter of the wireless network along a plurality of edges interconnecting data points derived at least in part from location data characterizing at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weighted traffic distribution graph; and

generating a measure of network performance based at least in part on the interpolated values;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.

29. An apparatus for characterizing the performance of a wireless network, the apparatus comprising:

a processor-based system operative (i) to interpolate values of at least one link parameter of the wireless network along a plurality of edges interconnecting data points derived at least in part from location data characterizing at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weighted traffic distribution graph, and (ii) to generate a measure of network performance based at least in part on the interpolated values;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.

30. An article of manufacture comprising a computer-readable medium storing one or more software programs for use in characterizing the performance of a wireless network, wherein the one or more programs when executed by a processor perform the steps of:

interpolating values of at least one link parameter of the wireless network along a plurality of edges interconnecting data points derived at least in part from map data characterizing at least a portion of an area serviced by the wireless network, the values comprising elements of an edge-weighted traffic distribution graph; and

generating a measure of network performance based at least in part on the interpolated values;

wherein the network performance measure comprises a differentiatable function of the at least one link parameter, so as to thereby facilitate derivative-based optimization of the network performance measure.