外文翻译--可靠的UMTS地面接入网的设计 英文版

IEEE Communications Magazine January 200266Planning ReliableUMTS Terrestrial Access Networks 0163-6804/02/$17.00 2002 IEEEABSTRACTThe Universal Mobile TelecommunicationSystem (UMTS) will play a very important rolein the telecommunication market of the nearfuture. Due to the wide range of services and theincreased transmission capacity, UMTS willbecome one of the most important access net-work types. The proposed topology of the UMTSterrestrial access network is tree-like, but thehigh amount of carried traffic requires a morereliable network structure. In this article weintroduce two types of heuristic algorithms tosolve this problem, and we plan network topolo-gies having a low magnitude of traffic loss incase of failures. One of our algorithms solves theproblem by modifying the tree-topology, whileothers expand the network by inserting addition-al links. In this article, we show how to find agood compromise between topology refinementand network expansion in the case of realisticnetwork scenarios, and we confirm our results bydetailed tests. INTRODUCTIONToday it is already obvious that the UniversalMobile Telecommunication System (UMTS) 1will play a fundamental role in the telecommuni-cation market of the near future. New features,as well as the incorporation of several types ofservices, the special emphasis on data transfer,and the significantly increased transmissioncapacity will ensure the rapid growth of UMTS-based services. Because of the increased rate ofdata communication, the terrestrial access net-work of UMTS is a very complex and high-capac-ity system.The access network of UMTS basically con-sists of two types of network elements: the radionetwork controller (RNC) and the radio base sta-tion (RBS), as shown in Fig. 1. In the network,RNCs are connected in a ring or a mesh topolo-gy, and have the task of managing the radiochannels of the connected RBSs, and concen-trating/relaying their traffic to an upper-levelcore network. The task of an RBS is to handleradio channels belonging to it, and to forwardthe traffic of other RBSs. That way, RBSs canbe connected to their dedicated RNC directly orin a cascaded way. In the current releases ofUMTS, the RBSs do not have routing capability,therefore the traffic between them has to be for-warded through the dedicated RNC. The optimal construction of this kind ofaccess network topology is one of the mostimportant tasks in recent UMTS-related researchactivities. As the mobile market is competitive,the performance of the network configuration isa critical issue, since it will determine the long-term performance and service quality of the net-work. Based on existing GSM networktopologies, a basic approach is to create theaccess topology as a set of RNC-rooted, (multi-)constrained trees, where the constraints comefrom the technical limitations of equipment.Although this topology is simple, the great num-ber of RBSs and RNCs, as well as technical limi-tations (such as the strongly non-linear costfunctions) make the planning of this kind of net-works computationally difficult.If the correct number and location of RBSs isgiven, then basically two different problems canbe defined: The multi-RNC problem. Here the task istwo-fold. On the one hand we have todetermine the required number of RNCsand their location, while on the other handwe have to construct the tree of RBSs foreach RNC. The single-RNC problem. Our task here isto find an optimal RBS tree for a pre-defined RNC.In the literature there are papers dealing withboth tasks. Papers 2 and 3 deal with themulti-RNC problem, while 4 deals with the sin-Attila Szlovencsk, Istvn Gdor, and Jnos Harmatos, Ericsson Research, HungaryTibor Cinkler, Budapest University of Technology and EconomicsDESIGN OFRELIABLE COMMUNICATION NETWORKSIEEE Communications Magazine January 2002 67gle-RNC problem. In the present article we alsodeal with the single-RNC problem.Besides its simplicity and cost-effectiveness,the tree topology has a very important disadvan-tage: it is very sensitive to any kind of failures.This is an important factor because a single fail-ure may cause significant loss of data, and mayresult in critical degradation of the networks per-formance. Although these failures occur rarely,they need to be handled, thus a fault-toleranttopology is required. Due to the large number ofnodes to be interconnected, both the mesh-likeand the ring topologies can be very uneconomical.This has motivated us to examine how to design atopology with acceptable cost and with an averagetraffic loss lower than a certain value.In the literature, we can find many papersdealing with network reliability problems. Papers5 and 6 propose heuristic algorithms to mini-mize the cost of mesh-like networks while takinginto account a constraint to all-terminal reliabili-ty, while 7 solves the same problem using agenetic algorithm. (All-terminal reliabilitydefines the probability that every pair of networknodes can communicate with each other 8).However, these algorithms are infeasible in thecase of large networks. In this article we introduce a two-phasemethod for a simplified problem of reliable net-work planning, assuming tree-like topologies anda single-failure scenario. In the first phase of the method, we plan anRBS tree, while taking reliability into account.In this case we compute the expected traffic lossof a given tree topology and we use this value tocalculate a virtual additional cost. Hence thetotal cost of the network (used in the optimiza-tion) will be the weighted sum of the nominaland traffic loss-related network costs. The ratioof the two types of cost is adjustable accordingto the desired traffic loss level. Due to the addi-tional cost introduced, this algorithm is able todesign a tree topology that provides a good com-promise between network cost and reliability. In the second phase, we increase networkreliability by inserting new links into the net-work. This approach provides a more efficientprotection strategy, since in this case we createalternative paths to bypass the most failure sen-sitive parts. The remainder of the article is organized asfollows. First, we define the employed cost andreliability models. Second, we describe the pro-posed algorithms and present a detailed numeri-cal study of them. Finally, we conclude thearticle with a brief summary.PROBLEM STATEMENTAs we stated before, our aim is to find a mini-mum cost RBS sub-network for a dedicatedRNC, taking into account the given topologyconstraints, traffic demands, and reliabilityexpectations. In the following section we presentour network, cost, and reliability models. NETWORK MODELWe assume that all information about the RBSsand RNCs is given in advance (e.g., geographicalposition, traffic demand, cost parameters, etc.).In addition, from the viewpoint of the planningprocess there are two important technologicalconstraints to be considered: Cascading constraint denotes the maximumnumber of hops between the RNC and anRBS. In other words, the cascading con-straint is an upper bound for the level valueof an RBS, which is the length of the short-est path from the given RBS to the RNC inthe case of a certain network topology. RBS degree constraint denotes the maxi-mum number of lower-level RBSs connect-ed to an RBS directly. It limits the numberof incoming and outgoing links (i.e., itrestricts the sum of the input and outputdegree of the node). We must note that current technologies letthis degree constraint be a relatively weak limit-ing factor； however it could have significantimpact on reliability. For example, if we have astrong reliability expectation, it can only be ful-filled by a “very” meshed network, so the net-work nodes should have high degree values.RELIABILITY MODELIn our model of reliability, the network consists ofthree types of elements (as shown in Fig. 2) andeach component has an availability parameter.In the case of equipment and interfaces, thisparameter depends on the data processing ordata transmission capacity, while in the case of alink this value is determined by two parameters,namely, length and location. In the case of wiredlines we calculate the availability by using thelink length and a cuts/km/year constant. On theother hand, in the case of microwave links we usea73 Figure 1. UMTS network elements.Core networkRNCRBSIEEE Communications Magazine January 200268the location parameter, which specifies some fac-tors, e.g., the probability of heavy storms, affect-ing the availability. The number of repeaters,which also affects the availability of the links,may depend on both length and location.Between the RNC and an RBS we can definepaths, where each path is composed of the ele-ments shown above. The availability of a pathcan be calculated as the serial product of theavailability of its elements. Each RBS can havemore paths (namely, one default and one ormore backups), and the availability of the RBS(A) will be the joint availability of the pathsbelonging to it. This value can be computedusing the tie-set formula 8. However, availability is not a perfect metric.As the traffic demands of two RBSs can be com-pletely different, their importance will also bedifferent, even if they have the same availability.Therefore, we use the traffic loss parameter L =(1 A) T, where A is the availability and T isthe traffic demand for a given RBS. In a tree topology the average value of L isalways larger than the theoretical lower limit,denoted by Lmin, which is the average traffic lossin a star topology network.COST MODELIn the cost model we use, the total structuralcost of the network (Ctop) consists of the cost ofthe RNC, the RBS devices, and the cost of thelinks, similar the model presented in 9. In our model we allow both wired (leased-line, fiber, coax) and wireless (microwave) inter-connections. The link cost has both capacity-independent and capacity-dependent parts. Thecapacity-independent part of the transmissionlink cost consists of a sub-cost proportional tothe length of the link, and another sub-cost rep-resenting the cost of the repeaters requiredbetween the two endpoints. On the other hand,the capacity-dependent part of the link cost istypically represented by an increasing step-wiseor piece-wise function. Our model handles bothapproaches. The cost of RBS and RNC consists of the fol-lowing sub-costs: The cost of the number of ports belongingto a given RBS. This is given by a step-wisefunction and depends on the number ofother RBSs connected to the RBS in ques-tion. The capacity-dependent cost of ports. Thiscost function is also step-wise and describesthe cost of the required capacity of the cur-rent port. The equipment cost representing the instal-lation and investment cost of required sub-devices, namely, processors, boards, and soon. This cost is calculated as a linear com-bination of the sum of traffic passingthrough the current device and the numberof the physical ports in use.Besides the structural cost of the network, wealso define a second type of network cost,describing the reliability of the network in ques-tion. This so called penalty cost, denoted byCpen, makes it possible to take into account thereliability of the network during a cost-basednetwork planning procedure. To compute Cpen, we first calculate a penaltyvalue denoted by w . If we have a constraint forthe average traffic loss (Llim), using an appropri-ate function we can describe the “unreliability”of each RBS, according to the traffic loss. Com-puting the sum of the function values, we get thevalue of w , which expresses the distance of thecurrent level of network reliability from therequired level. In our case, we use a simplequadratic function shown in Fig. 3.To transform the value of w into a penaltycost, we need to perform the following two steps: First we need to normalize w to the range0, 1, where the value 0 defines the casewhen the traffic loss is below the expectedLlimvalue for each RBS, and value 1 standsfor the worst solution known so far. Second, we bring this normalized value intothe same order of magnitude with the struc-tural cost of the network. This will make iteasier to define the proportion of this costin the final optimization cost, as we will seelater. In later sections we will use the weighted sumof the previously defined structural and penaltycost for optimization.PENALTY-TREE ALGORITHM (PTA) After defining the appropriate cost functions, wedraw up a so called “tree refinement” algorithm,representing the first phase of our approach ofUMTS access network planning.This algorithm has the following inputs: a73 Figure 2. Network elements: equipment, interface, link.EquipmentInterface InterfaceTransmissionlinkRBSEquipmentInterface InterfaceRBSa73 Figure 3. An example of the penalty function.Traffic lossTraffic loss expectationPenalty costw = (L - Llim)2, if LLlim0 , otherwiseIEEE Communications Magazine January 2002 69 The location of RBSs and of the RNC, andthe traffic demands. The cascading and degree constraints andthe traffic loss expectation Llim The availability functions for equipment,interfaces, and links.The output of the algorithm is a minimumcost tree topology, which meets the require-ments defined by the given topology constraintsand traffic demands.In this phase of network design the key stepof our approach is to modify the tree-topologyby keeping the basic structure without any redun-dant links. In 4 we have proposed an algorithmthat builds up a cost-efficient (nearly optimal)degree- and level-constrained tree topologyunder similar conditions, without reliability con-siderations.Briefly, the algorithm has two major iterationsteps: First, it determines which RBSs have to beplaced at one hop from the RNC. Second, it connects the remaining set ofRBSs to these “first level” RBSs in order todesign a network topology being the best(cheapest).Based on the meta-heuristic method calledSimulated Annealing (see 10), the algorithmperiodically reassigns the RBSs in the first leveland rebuilds the topology in each iteration. Thedecision to accept the actual configuration isbased on the cost of the configuration. In this case we use the same algorithm, but ineach step we compute the total cost of configu-ration as a linear combination of the physical,and the virtual, traffic loss-related costs, as givenin (1). Ctotal= b Cpen+ (1 b ) Ctop(1)By adjusting the value of b we can make thealgorithm pay higher attention to reliability. It isimportant to mention that in the case of a rela-tively low b value, the required level of trafficloss (Llim) will not be reached, as the weight ofCpenis too weak in the total cost of optimization.On the other hand, in the case of a higher relia-bility demand, the expansion of the network withredundant links can be more efficient than thetree refinement presented here. RELIABILITY ENHANCEMENTALGORITHMSHere we propose algorithms for increasing net-work reliability by inserting additional links. Asan input, we have the constraint of Llim, and inaddition a tree topology network, which needs tobe expanded. As an output, we try to generate anetwork topology with a guaranteed averagetraffic loss less than Llim. Before defining the algorithms, we presentour assumptions for the network we optimize: First, we suppose a single failure scenario,meaning that only one error can occur with-in the network at a time. Second, we specify that any of the backuppaths of an RBS cannot be more than onehop longer than the default path of theRBS. Third, we assume that the degree of someRBSs in the input network is less than ourdegree constraint (otherwise, no new linkcan be created). Fourth, we state that the newly added back-up links do not carry any traffic, except inthe case of failures. These assumptions reduce the complexity ofour planning problem. For example, the assump-tion of the single error scenario enables the use ofshared protection strategies, as illustrated in Fig. 4.If we want to protect the traffic originatingfrom both RBSs i and j, then we create a newlink between them, and we assign new backuppaths accordingly. As the default paths of RBSs iand j are point-disjoint, in the case of a singlefailure scenario only one of these paths can failat any one time. That is why the commonly usedlink between i and j needs to handle not thesum, but the maximum of the traffic demands ofthe two RBSs. In the following two algorithms, we use thisstrategy when creating protection paths.GREEDY RELIABILITY ENHANCEMENT (GRE)As a first approach, we created a very simplealgorithm based on the assumption that the first-level RBSs are the most failure-sensitive ones.Therefore, here we connect first-level RBS pairswith a new link, and we assign backup paths inexactly the same way as presented in Fig. 4.When choosing an RBS pair to be connected, wesimply make a decision on their distance, thuswe connect the closest pair first, than we connectthe closest pair from the remaining set of RBSs,and so on. This method is very fast, but not effi-cient. Moreover, as the number of first-levelRBSs is limited, this algorithm has a limitedcapability of reliability enhancement, so we usethis method only as a reference.RANDOMIZEDRELIABILITY ENHANCEMENT (RRE)In this case we use a randomized method tosolve the same problem. In each step of thealgorithm, we do the following: We separate a set of RBSs violating a trafficloss constraint, derived from the parameterLlim.a73 Figure 4. An example of shared protection.k10 20Protection pathi jk10+20max (10,20)20+10i jIEEE Communications Magazine January 200270 Using a random function weighted by thetraffic loss, we choose one RBS from theset. The larger the traffic loss one RBS has,the higher will be the probability it will bechosen. In a deterministic way, taking into accountboth cost and reliability, we select an appro-priate neighbor for the previously chosenRBS, and we insert a new link between thetwo RBSs. By selecting the proper neigh-bor, we make our decision based on a sim-ple rate, calculated as given in (2):rate = lD C + m (1 D A) + n L (2)where D C and D A are the cost and the availabil-ity change, respectively, due to the link we cre-ate to a neighbor, and where L is simply thelength of the default path of the neighbor.Parameters l , m, and n are constants, used tofind a compromise between the three objectives. On the default path of the neighbor, weincrement the capacity of the links if need-ed, since in case of failure, this path needsto be able to also handle the redirectedbackup traffic. Finally, we record the new backup path inthe protected RBS, and in all the childRBSs belonging to it. (By definition, RBS jis the child of RBS i, if the default pathfrom j goes through i).We repeat these steps until we do not findany RBSs in the first step that need to be pro-tected. In Fig. 5 we demonstrate the steps of ouralgorithm on a simple network containing sixRBSs. As we can see, in phase one we sepa-rate RBSs b, c, and e (marked red), as theseRBSs are the most failure sensitive accordingto our point of view. RBS e will be the first tobe protected (we select it randomly), and RBSd is the only neighbor that meets our require-ments. Thus, we insert a link (phase two), andwe increase the capacity of the link between dand f, according to the new demands. In phasethree, we assign backup paths to e, and toboth unprotected children b and c. In the nextiteration (phase 4a) we recalculate the avail-ability of each RBS, and we find that RBS bstill violates the traffic lost constraints. Herewe have two possible RBSs to create a backuplink to (a and d), and we choose a based onthe rate value presented in (2). After insertinganother new link into the network, we incre-ment the link capacities along the defaultpath of a. As RBS b has two backup paths(one through a and one through d) on thelink between d and f, which is common forboth backup paths, we do not need to incre-ment capacity again.In addition we note that all the newly createdlinks will have capacity equal to the so calledprotection traffic value of the starting endpoints.For an RBS, this value is the sum of the trafficfor all the unprotected child nodes. Therefore, ifwe swap the insertion order of links (e, d) and(b, a), link (e, d) will need a lower capacity, andRBS b will have only one backup path (phase4b). This is the reason for employing the random-ized selection, as in the second case we find alower cost solution. NUMERICAL RESULTSIn this section we examine the behavior of ourproposed algorithms.First, we show planning results obtained byPTA (see earlier section). Using a network of100 RBSs, we created several network topologiesby changing parameter b . Figure 6 shows (amongother things) the cost and the traffic loss values,normalized to the value given at b = 0.Test results presented in Fig. 6 correspond tothe traffic loss expectation Llim= Lmin, so weexpected the algorithm to produce a tree topolo-gy with the lowest traffic loss value theoreticallyavailable.As parameter b increases and the penaltycost becomes more prioritized than the struc-tural cost, the structure of the network divergesfrom the cost-optimal tree topology. As we cansee, the cost and the traffic loss functions havetwo major inflexion points and three major partsaccordingly (in this case the inflexion points arelocated at b values of approximately 0.3 and0.8). The explanation of the different parts ofthe curves is as follows: Until the first inflexion point, traffic loss inthe network decreases as the averagedegree of RBSs decreases. Between the inflexion points, the averagelevel of RBSs (besides low degree values)decreases as well. Thus, the number of firstlevel nodes increases. Beyond the second inflexion point parame-ter b makes the penalty cost so dominantthat the tree topology begins to transforminto a star.Nevertheless, we must note that the positionof these inflexion points depends both on thechoice of the cost functions and parameter Llim.Of course, these characteristics also depend onthe chosen penalty cost function and on the opti-mization method.a73 Figure 5. Iteration steps of the RRE algorithm.fdabce221115fdabce7212155fdabce7213155fdabce72234a155fdabce72234b153IEEE Communications Magazine January 2002 71We now analyze the rest of Fig. 6. Based onnetwork topologies produced by PTA, we havemade further tests comparing the behavior ofour GRE and RRE algorithms (defined in anearlier section). During tests, in the case ofGRE we set Llim=0 in order to obtain the mostreliable network possible to reach with thisalgorithm. On the other hand, in the case ofRRE we set Llimto the average traffic lossvalue of the network that resulted from theGRE. Thus, the two algorithms provided thesame traffic loss levels, and could have beencompared according to the cost of the networksobtained.As Fig. 6 shows in accordance with ourhopes, the RRE algorithm gave better perfor-mance in all cases. The difference betweenGRE and RRE was 7 percent to 15 percent,depending on b . The relatively greater differ-ence on the segment between the two inflexionpoints resulted from the fact that, since RREis not limited to protect only first-level nodes,the resulting cost does not depend strongly onthe number of first-level nodes, thereforeRRE is able to provide a more cost effectivesolution.In the third test, an optimal b value issearched, where the full cost of the network isminimal. Therefore, as in the previous test, weused the networks obtained by PTA, but inthis case we used the same Llimconstraint forboth RRE and PTA (this value was equal toLminagain). As a first step, a preoptimizednetwork is created, using PTA with a given bvalue, then the network is expanded with addi-tional links to reach the required traffic losslimit. As Fig. 7 shows, the level of preopti-mization (b ) influences the efficiency of thenetwork expansion, and around the first inflex-ion point (it is approximately at b = 0.3 in thiscase) a minimum cost network is obtained bythe joint use of the two algorithms PTA andRRE.CONCLUSIONSIn this article we presented methods for reli-able UMTS access network design. Based onnetworks obtained by a tree topology networkplanner algorithm using the Simulated Anneal-ing technique, we developed two new methodsto reach the required reliability level. In ourfirst method (PTA) we modified the originalnetwork design algorithm to take the reliabilityof the network into consideration during thenetwork planning phase. Therefore, in PTA wejust modified the network topology while keep-ing the tree structure. In the second method(RRE) we made an expansion on the network,protecting the most failure-sensitive parts ofthe topology. We found that in the case of relatively weaktraffic loss requirements, it is more efficient touse the PTA algorithm only, while in the case ofhigher reliability demands, we also need expan-sion algorithms. In our tests, PTA was efficientuntil we had a traffic loss requirement approxi-mately 80 percent of the traffic loss value of theinitial network. Moreover, we found that the level of PTApreoptimization (b ) influenced the efficiency ofRRE, and we presented a b value at which thejoint use of PTA and RRE gives an optimalsolution.ACKNOWLEDGMENTThe authors would like to thank Gbor Magyarfor his useful comments.a73 Figure 6. Network cost and traffic loss using dif-ferent b parameters, comparing RRE.Percentage of the reliability costin the full cost ()000.5Traffic loss/cost change percentage11.522.50.2 0.4 0.6 0.8 1Cost after PTACost with GRECost with RRETraffic loss after PTATraffic loss after GRETraffic loss after RREa73 Figure 7. Network and expansion cost with fixedLlimand variable b parameter.Percentage of the reliability costin the cost used in PTA000.5Cost11.522.50.2 0.4 0.6 0.8 1Network cost after PTAIncremental cost of RREFull costThe relativelygreater differenceon the segmentbetween the twoinflexion pointshas the followingreason: as RRE isnot limited toprotect only firstlevel nodes, theresulting costdoes not dependstrongly on thenumber of firstlevel nodes,therefore RRE isable to provide amore costeffective solution.IEEE Communications Magazine January 200272REFERENCES1 T. Ojanper and R. Prasad, Wideband CDMA for ThirdGeneration Mobile Communication, 1998, ArtechHouse Pub.2 J. Harmat