ABSTRACT

An algorithm is presented for the optimization of distribution points in a (broadband) wireless network, linking provider to end-user. It is particularly suitable for large numbers of subscribers for which exhaustive search optimization is not possible. The solution is delivered in two stages: an initial reduction phase followed by a process of fine-tuning. The algorithm is flexible, allowing for a number of practical performance constraints to be applied.

KEYWORDS

Broadband
Wireless
Optimization algorithms
Reduction
Perturbation

INTRODUCTION

Various technologies exist for providing high-speed or broadband Internet access to the home or small business user. Along with cable and xDSL, the wireless approach has shown itself as one of the more promising options. With a fibre backbone in place, it is simply necessary to provide a wireless connection to each subscriber. However, it will be to the benefit of all for this system of connections to be effected in as efficient a manner as possible.

The connection to each subscriber starts from one of a number of primary distribution points (PDPs), adjacent to the backbone. Ideally a single link can then be established between PDP and subscriber through a simple transmitter/receiver (transceiver) system at each end. These transceivers may be omni-directional or steered. There are, however, a number of reasons why such direct connections may not be practical.

Firstly, the single link option will only be possible if a line-of-sight (l-o-s) line exists between the two points. In the absence of l-o-s, the connection must be achieved via one or more intermediate points and two or more l-o-s links. In this paper we use the term connection to mean the complete PDP-subscriber path and link for a single l-o-s step. Secondly, direct transmission may not be possible above a given distance irrespective of whether l-o-s exists. This will be a feature of the particular technology being used.

Fowler (2000) suggests that a solution may be to install relay equipment at appropriate subscriber locations to avoid the need for dedicated stations. Although realistic, this approach introduces a third constraint, that (again dependent upon the technology) there may be a maximum number of links supported by each subscriber relay. A fourth constraint arises if some dedicated stations already exist or certain subscribers already have relay equipment installed. Under such circumstances, it will be necessary to influence the otherwise free optimization.

DEFINITION AND ANALYSIS

We begin with a general formulization of the problem and constraints and follow it with a discussion of its characteristics and complexity.

The inputs to the problem are the physical locations and the restrictions upon valid solutions. If there are p PDPs (1 £ k £ p) and s subscribers (1 £ i £ s) then the problem essentially is to connect each subscriber i to a PDP k. Let the set of PDPs be P^*, the set of subscribers S^* and, for convenience, define N^* = P^*ÈS^*, the set of all nodes of size n = p + s. This will simplify much of what is to follow. Each node iÎ N^* is defined by its co-ordinates (x_i, y_i). We also define a distance matrix D = (d_ij: i,jÎ N^*). For convenience in this paper, we assume Euclidean distances d_ij = Ö [(x_i-x_j)² + (y_i-y_j)²] but non-Euclidean distances (natural obstacles, preferences, etc.) are easily accommodated. The presence or absence of l-o-s between nodes is represented by the l-o-s matrix L = (l_ij: i,jÎ N^*), a set of Boolean (zero-one) values. Both D and L are symmetric. The maximum distance for a single link is given by d and the maximum number of links supported by a single relay is l. We seek to minimize the number of relay points and hence the cost of full connection.

If an l-o-s link of acceptable distance exists between each node and a PDP, that is if

          "iÎ S^*, ($ kÎ P^* ® l_ik = 1 Ù d_ik £d)

then the problem is trivially solved. If, however, there are nodes with no such valid link, that is if

          $iÎ S^* ® (" kÎ P^*, l_ik = 0 Ú d_ik > d)

then the connection for each must be provided through one or more relays. On a node-by-node basis, this is a relatively simple process to optimize. A modified (Boolean) version of Dijkstra’s algorithm (Dijkstra 1959), the calculation behind the OSPF routing protocol (Moy 1989) can be used to find the shortest path (see section 3.2). However, taking all nodes together, this process will not achieve optimality. In simple terms, it may be worthwhile to provide sub-optimal connectivity for individual nodes, that is a connection passing through more than the necessary minimum number of relays, if these relays can also be used to provide connections to other nodes rather than installing additional relays.

A solution to this problem is the interrelating set of connection paths from PDP to subscriber. The optimum will be that solution making best combined use of subscriber relays to minimize the number of such relays in the overall network. There is an extremely large number of possible solutions from which to select this optimum and an exhaustive search approach is infeasible.

In principle, any of the s subscriber nodes may (or may not) act as a relay. This gives the number of possible relay sets as 2^s which is exponential in its own right without any consideration given to the path each node is to take through these relays to establish its connection to a PDP. A full discussion of polynomial and exponential complexity, deterministic and non-deterministic algorithms and the classes P, NP and NP Complete would extend this paper unnecessarily and can be found elsewhere (Lawler 1985) but it is clear that this is a complex problem indeed.

3. OPTIMIZATION

A standard approach to combinatorial problems of this form is to apply small variations (perturbations) to some initial solution in the hope of finding a succession of improvements until an apparent optimum is reached. That this may not be the true optimum is discussed in Section 4 together with a possible solution. One such initial solution and perturbation process is described in Section 3.2. However, in the light of the previous section, it may first be necessary to reduce the size of the problem.

The complexity of any given combinatorial problem is effectively a function of its input parameters. The key inputs to this connection problem are the n nodes and its complexity is thus given by some function f(n). If f(n) is too large to manage, then our options divide into two:

• Replace the function f by a (less complex) function y with y(n) < f (n).
• Replace the parameters (nodes) n by a (smaller) number q with f(q) < f (n).

3.1 Representative reduction

We are seeking q nodes representing the original n. This representation will be on the basis of the (x,y) co-ordinates of the nodes together with their weights, reflecting the underlying distribution. Large weights will indicate that a node represents a large number of subscribers; smaller weights, fewer. Alternatively, they may be used to ‘anchor’ PDPs or other sites with relay equipment already installed. These weights will be discussed again and used later. For now, the reduction may take two forms.

3.1.1 Grid reduction

If the number of nodes is very large then significant, and necessarily crude reduction, is appropriate. we define an A ´ B sided area of a' ´ b' cells with the subscriber density of each cell (a, b) given by z_ab.  This gives n’ = a'b' initial nodes with x_i = A(a - ½)/a', y_i = B(b - ½)/b' and w_i = z_ab where a = (i-1) mod a + 1 and b = (i-1) div a + 1. (mod a is taken to mean the integer remainder on division by a and div a the quotient.) This will be a two-dimensional set of grid points in a square lattice formation.

This form of reduction lacks any form of sophistication. It should be applied only when the number of nodes is too large to permit any of the more flexible methods that follow. The n’ nodes obtained in this manner can be regarded as the starting point for the optimization in the next section. Although each node will reasonably reflect the underlying distribution of the cell it represents, no consideration has been given to how these cells themselves have been determined. The process is blind to the overall distribution. If, for example, an area of heavy subscriber density straddles a potential cell boundary then this area, a candidate for representation in its own right (see next section), will be arbitrarily split and thereafter considered separately. Whilst, such reduction, for very large distributions and moderate values of n’, may be justified by the absence of any viable alternative, it should only be used where absolutely necessary.

3.1.2 Stepwise reduction

As soon as computationally feasible, the previous stage should be terminated and a more sophisticated method begun. For subscriber patterns (that is values of n) of moderate size (discussed in Section 3.3), this phase may be entered from the outset and grid reduction omitted entirely.

Instead of a single phase of global reduction, consisting of a number of independent calculations, stepwise reduction seeks to repeatedly reduce the number of nodes, initially n (or n’ if grid reduction is necessary), by one in an adaptive and locally representative manner, until the q nodes that remain are sufficiently small in number to proceed to the perturbation stage described in Section 3.2. The complete process follows. A single step is described first.

Our objective, at each step, is to replace two nodes by one in a representative fashion. These will the closest nodes from the original n subject to the constraints (if appropriate) that a single relay in the final network may not serve more than l links or a single link exceed the distance d. We seek to find a and b such that

          dab £ dÙ wa + wb£ lÙ dab = min _{i,jÎ S*} d_ij.

If, through the application of the constraints, no such pair exist, then no (further) reduction is possible and this stage of the optimization must terminate. If appropriate a and b can be found then the reduction step is completed by setting

,           and .

The new node g thus represents a and b in terms of both position and weight. a and b are removed from S^* (and hence N^*) and g added.

This single reduction step can be repeated until the number of nodes has been reduced sufficiently to proceed directly to the next stage or until no such replacement is possible subject to the constraints dab£dand wa + wb£l. Essentially then, this reduced number of nodes may be used to obtain a solution from the next section. This will give an outline solution from which a full system may be developed by linking each representative to the nodes it represents. Section 3.3 describes a number of variations.

3.2 Perturbation

The final stage of optimization involves applying a series of perturbations to an initially approximated solution. A version of Dijkstra’s algorithm provides the starting point and the perturbations seek for variations that lower the total cost. For simplicity, the algorithms that follow are described as acting on n nodes, that is, as if no reduction has taken place. Various combinations of reduction and perturbation are described in Section 3.3.

3.2.1 Initial solution

Dijkstra’s algorithm will find the shortest path between any two points in a network with various costs assigned to each link. Here, the cost is unimportant since each additional link simply requires an extra relay and we seek to minimize the total number of relays. We instead use a zero-one cost matrix to reflect whether the link between two nodes is valid in terms of l-o-s and distance. We modify the algorithm to find the shortest path from subscriber to PDP for each node. Any PDP will serve as a destination point in a subscriber connection.

The following variables are required in the modified algorithm. P^*, S^* and N^* are the sets of PDPs, subscribers and all nodes as defined in Section 2. The matrices D and L and the maximums d and lare also as specified. The cost matrix C = (c_ij: i,jÎ N^*) has elements defined as

In addition, r_ij is the predecessor of node j in the path from subscriber i, d_ij is the shortest known distance to j in the path from i and P_i is the set of nodes whose shortest distance from i is known at any time. The algorithm can be expressed as follows.

        for iÎ S^* do
                         begin
                         P_i = Æ
                                for jÎ N^*-{i} do
                                        begin
                                      r_ij = 0 {undefined}
                                     d_ij = ¥
                                        end
                         d_ii = 0
                                while not $kÎ P^* ® kÎP_i do
                                        begin
                                                Find j, j’ ® d_ij+c_jj’ = 
                                      P_i = P_i È {j’}
                                      r_ij’ = j
                                                for j"Î N^*-P_ido
                                               d_ij" = min(d_ij",d_ij’+c_j’j")
                                        end
                         end

The iteration continues until a PDP is reached. The set of predecessors, thus derived, defines the path from each node i to a PDP. Any PDP k with d_ik = 0 is a valid destination for subscriber i. (If there are no such PDPs then the problem has no valid solution.) The PDP selected by the above algorithm for each subscriber is arbitrary but serves as an initial solution.

3.2.2 Perturbations

The process of applying perturbations to an initial solution is a straightforward one. We are simply looking for a sequence of improvements, if one exists, until no more are possible. In this case the objective is to minimize the number of relays in the network; thus a solution will be an improvement if it has fewer relays than its predecessor. Once again, this section will outline the general principle. The following section will put the individual components together.

We start with the set of connections, one for each node, produced by the modified Dijkstra algorithm of Section 3.2.1. Each path will be independently optimal but the complete solution may not be. We seek, with each perturbation stage, to find an improved solution by re-routing the connection for one node via one or more relays already in use in the connection for another or others. There are various forms that this algorithm may take, with different levels of sophistication. The following is one possibility although different options are discussed in the next section.

           for iÎ S^* do
                              if $j (in the path of i) Ù $ j’ (in the path of some other i’) ® d_jj’£dÙl_jj’ = 1 then
                                       [re-route connection for i through j’ from j]

This algorithm is intentionally given in a less formal form than the previous one as it is intended to be as flexible as possible. The next section considers various options.

3.3 A compound algorithm and variations

We now have all of the components of a complete algorithm. It remains only to connect them. However, there are a number of ways in which this can be achieved. The variations arise from the different ways in which the individual components may interact. Essentially, we must ask: what scale of reduction is necessary, at what point should the reduction stop, when should permutation begin, what depth of permutation is appropriate and are reduction and permutation entirely disjoint or may they be overlapped? We identify the following components.

          G: Grid reduction producing n (or n’) nodes from a large subscriber distribution,
          R: A single reduction step reducing the number of nodes by one,
          P: A single perturbation step looking for a reduction in the number of relays by re-routing a single connection via another path.
          S: A state following reduction in which the problem is small enough for perturbation to proceed,
          A: A state following perturbation in which no further improvements can be found - an apparent optimum has been reached.

The following routine combinations are then possible:
 

ALGORITHM A repeat R            until S repeat P            until A	ALGORITHM B repeat R            until S P repeat R           P           until A
ALGORITHM C G repeat R            until S repeat P            until A	ALGORITHM D G repeat R            until S P repeat R           P           until A

In each case, grid reduction may or may not be necessary dependent on the overall size of the problem. The use of the R and P steps is subtler. Essentially we may apply the two stages independently or combine them when possible to increase the scope of the optimization. Starting from any reduced state S, we will find an apparent optimum A. The true optimum will be O. A will be equal to O if the scope of the perturbation is sufficiently large to escape from local minima in the optimization process. One way of making this more likely is to use a ‘larger’ perturbation at each stage. Instead of looking to re-route a single connection each time, we look to perturbate two or more. Algorithm A, for example, would become:
 

ALGORITHM A’ repeat R             until S repeat P             P             :             P             until A

with similar extensions applying to Algorithms B, C and D. These algorithms are more sophisticated than their predecessors but more complex. A full discussion of complexity issues is beyond the scope of this paper (Lawler 1985).

4. RESULTS AND CONCLUSION

The problem with any large-scale optimization process is that, by its very nature, heuristic methods of solution are difficult to test. If it were possible to test all cases exhaustively then this would effectively dispense with the need for heuristics. However, without an exhaustive search comparison, conclusive analysis is difficult.

We approach this problem in three ways. Firstly, it is possible to perform exhaustive search comparisons for small numbers of nodes and this is a reasonable place to start. Secondly, we may address larger problems by stealth. Thirdly, we can apply theoretical analysis where appropriate.

4.1 Exhaustive search comparisons

Depending on the computing resources available and the time regarded as acceptable for completion we are able to perform exhaustive search comparisons for between 20 and 30 nodes. 70 such tests have been completed with node placement and constraints generated randomly. The reduction phase is unnecessary in these circumstances. The perturbation stage, acting in isolation, was found to be optimal in 62 cases. Of the eight remaining cases, the maximum error (sub-optimal, that is too many relays) was 5.2% and the average (mean), 2.2%. This gives an average (mean) over the 70 tests of 0.25%.

4.2 Intuitive comparisons

The second approach is to perform the optimization on selected sets of nodes for which the solution is intuitive. Features such as symmetry and weighting may be used to build in predictability to the problem as an alternative to the formal exhaustive search. 18 tests of this type have been completed, for between 30 and 95 nodes with apparent optimality achieved in every case. However this may have more to do with the intuitive nature of the algorithm rather than its accuracy!

4.3 Theoretical analysis

For very large numbers of nodes, we are forced to resort to theoretical analysis. From Section 4.4.1 we have some faith in the perturbation stage and it really remains to consider the reliability of the reduction. This can be achieved by geometric analysis and has been carried out previously in related cases (Grout 1988). The full argument is too long to include here; however, it can be shown that the reduction stage is sound.

4.4 Summary

This paper has presented a compound algorithm for a very current problem. The algorithm is composed of a number of components and the interaction between components is flexible. Testing is difficult due to the very nature of the problem under consideration. However, a combination of approaches suggests that the algorithm to be a good one. Ultimately, as with any heuristic, its greatest strength lies in its simple ability to deal, however accurately, with large-scale problems that would be otherwise impossible to solve.

REFERENCES

Dijkstra, E.W., 1959. A Note on Two Problems in Connection with Graphs. Numerische Math., Vol. 1, pp269-271.
Fowler, T., 2000. Mesh Networks for Broadband Access. IEE Review, January, pp17-22.
Grout, V.M., 1988. Optimisation Techniques for Telecommunication Networks. PhD Thesis, Plymouth Polytechnic
Lawler, E.L., et al, 1985. The Traveling Salesman Problem. Wiley.
Moy, J,. 1989. The OSPF Specification. Request for Comments (RFC) no. 1131, http://www.rfc-editor.org