Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P4

Digital Data Service (DDS) is widely used for providing private high quality digital transport service in the telecommunications industry. The network connections of DSS are permanent and its transmission facilities are dedicated, enabling it to transfer digital data with less interference and greater security than switched service. DSS also proves to be appropriate for linking sites that have applications which require a permanent connection and a demonstrated need for frequent data transfer.
Nội dung trích xuất từ tài liệu:
Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P4 Telecommunications Optimization: Heuristic and Adaptive Techniques. Edited by David W. Corne, Martin J. Oates, George D. Smith Copyright © 2000 John Wiley & Sons Ltd ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic)4Tabu Search and EvolutionaryScatter Search for ‘Tree-Star’Network Problems, withApplications to Leased-LineNetwork DesignJiefeng Xu, Steve Y. Chiu and Fred Glover4.1 IntroductionDigital Data Service (DDS) is widely used for providing private high quality digitaltransport service in the telecommunications industry. The network connections of DSS arepermanent and its transmission facilities are dedicated, enabling it to transfer digital datawith less interference and greater security than switched service. DSS also proves to beappropriate for linking sites that have applications which require a permanent connectionand a demonstrated need for frequent data transfer. For example, it can be used for remoteLocal Area Network (LAN) access, entry into frame relay networks, support for transaction-based systems, and can be incorporated in IBM’s System Network Architecture (SNA) andother networks. With optimal DSS network design and sufficient use, DSS becomeseconomically competitive with frame relay service in the higher transmission speed ranges,and with analog private line service in the lower transmission speed ranges.Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd58 Telecommunications Optimization: Heuristic and Adaptive Techniques In this chapter, we address a fundamental DDS network design problem that arises inpractical applications of a telecommunications company in the United States. The decisionelements of the problem consist of a finite set of inter-offices (hubs) and a finite set ofcustomer locations that are geographically distributed on a plane. A subset of hubs arechosen to be active subject to the restriction of forming a network in which every two activehubs to communicate with each other, hence constituting a spanning tree. Each hub has afixed cost for being chosen active and each link (edge) has a connection cost for beingincluded in the associated spanning tree. Each customer location must be connected directlyto its own designated end office which in turn needs to be connected with exactly one activehub, thereby permitting every two customers to communicate with each other via the hubnetwork. This also incurs a connection cost on the edge between the customer location andits associated hub. The objective is to design such a network at minimum cost. 4m 0m 10m 16m 4m 8m Digital Hub 5m 3m End Office Customer LocationFigure 4.1 A DDS network. Figure 4.1 shows a practical scenario of a small DDS network. The number of dedicatedlines required for the link between an end office and its assigned hub is equal to the numberof customer locations connected to the end office. Since the links between customerlocations and end offices are always fixed, the costs of these links are constant and therebycan be ignored from the network design. In practice, the line connection cost is distance sensitive and is calculated according tothe tariff charges established by the Federal Communications Commission (FCC). Thesecharges include a fixed cost for use and a variable cost that is related to the distance. Foreach active hub, in addition to the fixed bridging cost, a charge is also accessed for eachincoming and outgoing line connected to this hub. To illustrate how these costs areassociated with the DSS network, suppose the monthly cost data are given as in Table 4.1.Then, the monthly costs for the network given in Figure 4.1 are as detailed in Table 4.2. The foregoing representation of the DDS network design problem can be simplified byreference to a Steiner Tree framework. Since the linking cost per line between an end officeand a potential hub is known and the bridging cost per line for that hub is also available, weTabu Search and Evolutionary Scatter Search for ‘Tree-Star’ Network Problems 59can pre-calculate the cost of connecting a customer location to a hub by adding up these twoterms. Thus, the intermediate end offices can be eliminated and the DDS network problemcan be conve ...