In a code-division multiple-access cellular system, the soft handoff with macrodiversity is known to increase the number of available channels in each cell from the interference-reduced radio environment. This capability, however, also incurs extra load on the system due to the increase in the number of channels occupied and reserved for macrodiversity. The objective is to evaluate the associated loads, thereby enabling effective channel management. We first differentiate two kinds of loads attributable to new and handoff calls, respectively. Further dividing handoff calls into two kinds, we derive a load balance equation from which three different loads at a cell are all exactly obtained in association with the size of the soft handoff region. Comparative analysis with the case of no soft handoff region, i.e., of hard handoff, shows the appropriate proportion of channels reserved for the macrodiversity in a given soft handoff region.

We propose a new lower bound on the number of frequencies required to meet the frequency demands in a cellular network. It extends Gamst's (1986) work by devising a procedure of frequency insertion, which makes the best of unexploited frequency spaces between the assigned frequencies. Our lower bound is claimed to have much wider and easier real-world applicability due to its relaxed prerequisite condition. Furthermore, it is shown via an illustrative example to be much tighter than its previous counterpart.

The widespread use of SONET technology makes the self-healing ring (SHR) architecture the most basic building-block in designing a large fiber-optic network which is not only survivable but also cost-effective. We address the design problem of placing a single SONET unidirectional ring with a single gateway hub in a region administered by a community of interest. Introduced for the purpose of further cost-saving in our problem setting is the flexibility that some offices, instead of being included in the ring, can be homed to the ring via two arc-disjoint paths. Given the set of offices and potential arcs, the objective is then to determine at the minimum total cost both the ring location and the homing to the ring of its nonmember nodes. We formulate the problem as a mixed integer programming model and develop an efficient solution procedure by devising six improvement heuristics. Extensive computational experiments are conducted with input data instances selected from the data ranges of the real-world environments. The practical value of the solution procedure for network planners is well evidenced by its excellent and consistent performance of quickly generated good-quality solutions over various input data instances.

Abstract This paper considers the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose nodes are partitioned into mutually exclusive and exhaustive node sets, The GMSTP is then to find a minimum‐cost tree which includes exactly one node from each node set. Here, we show that the GMSTP is NP‐hard and that unless P = NP no polynomial‐time heuristic algorithm with a finite worst‐case performance ratio can exist for the GMSTP. We present various integer programming formulations for the problem and compare their linear programming relaxations. Based on the tightest formulation among the ones proposed, a dual‐based solution procedure is developed and shown to be efficient from computing experiments.

Addresses a comprehensive design issue of a centralized communication network with logical star-star topology: each established hub is connected to the center node via its own cable route which may pass through a number of sites, and so is the connection from a user to its destination hub. The study distinguishes itself from other network design studies in the literature by explicitly addressing the reality that the cable can be installed only in the conduit, and some hub devices such as line concentrators and multiplexers, if properly installed, would provide more economical cable paths. A cost minimization model is first made to cover three types of decisions in one setting: locating hubs, placing conduit system, and installing cable therein. It is then formulated as a variant of classical network design model, allowing the incorporation of the well-known dual-ascent solution strategy. Despite the complexity inherent to the design problem, the performance of the proposed solution heuristic is shown via the extensive computational experiments with large-scale test problems to be very satisfactory in both speed and quality of the solutions generated.>

Abstract This paper is concerned with information dissemination in a tree. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. Under a minisum criterion, a necessary and sufficient condition for an optimal call sequence at each vertex is established. Based on this, an O(N log N) algorithm is designed to find optimal call sequences at all vertices and to determine the broadcast center of a tree—the set of all vertices from which minisum broadcasting can be accomplished. © 1993 John Wiley & Sons, Inc.

Dimensioning procedures for prioritized channel assignment in a cellular radio network are considered. Under the cutoff priority discipline, the prioritized channel assignment procedures for a single cell and multicell system are formulated as nonlinear discrete capacity allocation problems. Exact incremental algorithms which efficiently solve the proposed problems are devised. They are based on the properties of the blocking probabilities of new calls and handoff calls. Given the number of available frequency channels together with the arrival rates and the grade of service (GOS) for both types of calls in each cell, algorithm SP1 generates an optimal channel assignment which ensures priority for handoff calls. Given the arrival rates and distinct GOSs for new and handoff calls, algorithm SP2 finds the minimum number of channels required in each cell. Algorithm MP extends algorithm SP1 to a multicell system and provides the prioritized channel assignment for all calls in the system. The algorithms are very fast and are appropriate for the fair allocation of frequency channels among cells.>

The information dissemination process in a tree is considered. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. For the case of uniform edge transmission times, P. Slater et al. (1981) showed that a simple ordering policy achieves the minimum broadcast time and presented an algorithm which determines a set of broadcast centers. It is shown that a simple ordering policy is still optimal for the case of nonuniform edge transmission times, and modifications of the algorithm that enables it to solve this general problem within O(N log N) time are suggested.>