Search

This paper presents a novel method to determine the optimal routing of medium voltage distribution networks in sparse rural areas. The objective is evaluated through minimizing the net present cost of the network over a selected time period. A problem specific genetic algorithm is proposed to address the optimal network routing problem and compute the optimized topology throughout a geographically constrained region. The proposed method simultaneously considers nonfixed candidate lines to overcome search space restrictions through a variable length encoding structure and the use of Steiner points, and a shortest path algorithm to traverse between point-to-point connections in the constrained region. Geographical restrictions on network routing are considered through the formation of a rasterized map. The network is modeled at the branch level and considers both greenfield and expansion planning to highlight the effects of accessibility restrictions. The optimization model is applied to a real rural distribution network in the South–West of Western Australia. Alternative network topologies are found to provide significant improvements over the existing network and traditional reconfiguration based methods for evaluating the minimum cost sparse rural distribution network. [ABSTRACT FROM AUTHOR]

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(\sqrt n\log n) , the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data. [ABSTRACT FROM PUBLISHER]

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. [ABSTRACT FROM PUBLISHER]

In this paper, we present ObSteiner, an exact algorithm for the construction of obstacle-avoiding rectilinear Steiner minimum trees (OARSMTs) among complex rectilinear obstacles. This is the first paper to propose a geometric approach to optimally solve the OARSMT problem among complex obstacles. The optimal solution is constructed by the concatenation of full Steiner trees among complex obstacles, which are proven to be of simple structures in this paper. ObSteiner is able to handle complex obstacles, including both convex and concave ones. Benchmarks with hundreds of terminals among a large number of obstacles are solved optimally in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient method to solve the obstacle-avoiding rectilinear Steiner tree (OARSMT) problem optimally. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a rectilinear Steiner minimum tree (RSMT). We modify and extend the algorithm to allow obstacles in the routing region. For each routing obstacle, we first introduce four virtual terminals located at its four corners. We then give the definition of FSTs with blockages and prove that they will follow some very simple structures. Based on these observations, a two-phase approach is developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs with blockages. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Finally, experiments on several benchmarks are conducted. Results show that the proposed method is able to handle problems with hundreds of terminals in the presence of multiple obstacles, generating an optimal solution in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

In this paper, we present an algorithm called FOARS for obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction. FOARS applies a top-down approach which first partitions the set of pins into several subsets uncluttered by obstacles. Then an obstacle-avoiding Steiner tree is generated for each subset by an obstacle aware version of the rectilinear Steiner minimal tree algorithm FLUTE. Finally, the trees are merged and refined to form the OARSMT. To guide the partitioning of pins, we propose a novel algorithm to construct a linear-sized obstacle-avoiding spanning graph which guarantees to contain a rectilinear minimum spanning tree if there is no obstacle. Experimental results show that FOARS is among the best algorithms in terms of both wirelength and runtime for testcases both with and without obstacles. [ABSTRACT FROM AUTHOR]

Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and batched greedy algorithm (BGA) by Kahng et al., have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a considerably faster version, a partially parallelized and distributed form of this modified algorithm is proposed. Computational tests using large random data sets have shown the advantage of the modification on RST, and tests conducted on a cluster of workstations have proven the proposed distributed approach to be very promising particularly for large problem instances. [ABSTRACT FROM AUTHOR]

Given a set of pins and a set of obstacles on routing layers, a multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many very large scale integration designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. As a fundamental problem with extensive practical applications to routing and wirelength/congestion/timing estimations in early design stages, it is desired to develop an effective algorithm for the ML-OARSMT problem to facilitate the design flow. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem with rectangular obstacles and then identify key different properties of this problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph, we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any two-pin net and many multiple-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature. [ABSTRACT FROM AUTHOR]

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works. [ABSTRACT FROM AUTHOR]

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y-/X-architecture (λ3-/λ4-geometry) to improve the chip performance. This paper presents an O(n log n) heuristic, λ-OAT, for obstacle-avoiding Steiner minimal tree construction in the A-geometry plane (λ-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with most recent works on OARSMT problem, A-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of λ-OAT make it extremely practical and useful in the routing phase. [ABSTRACT FROM AUTHOR]