their minimum Aij or maximum bij values will form a tree graph or a collection of dis- connected tree graphs. This is another desirable feature of network flow formulations, since a tree graph has some nice mathematical structure. 26.1.4 Fan-out backhaul solutions We can shape the backhaul problem into a network flow optimization by adding some phantom arcs to the graph. Figure 26.5 illustrates the network flow graph that we can use to show that backhaul is a network flow optimization. Since the backhaul problem 5 As in Chap. 22, we beg the forgiveness of operations research professionals for such a simplis- tic presentation of a vast area of study. Source Figure 26.5 Network flow formulation of backhaul optimization. Downloaded from Digital Engineering Library @ McGraw-Hil (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. Capacity Calculations for Cellular Networks Capacity Calculations for Cellular Networks has no upper bounds (bij = 8 for all i and j) and the minimum values are all zero (aij = 0 for all i and j), the backhaul problem looks like Eq. (26.1): Minimize Eason (26.1) subject to Exu-Exp= for all j Xij 00 for all i and j The value of rj is the required transport at node j. The constraints are linear equations, so the entire system would be linear if the cost functions were linear, if Cij(Xij) = Cijxij. The linear constraints and linear cost functions would be enough to ensure that there is an optimal solution that is a fan-out network like the solution shown in Fig. 26.4. The tree graph determines the flow pattern, and the link configuration determines how much capacity each link requires, the flow in each arc of the graph. Equations (26.2) show the flows for the example in Fig. 26.4. X12=r2+r3+r4 X23 = r3 X24 = r4 (26.2) X56 = r5 Base stations at nodes 2 and 6 serve as cross-connects for the others. There are two assumptions we can make about the backhaul costs that are enough to ensure 