Node-pair reliability of network systems with small distances between adjacent nodes

A new method for computing the node-pair reliability of network systems modeled by random graphs with nodes arranged in sequence is presented. It is based on a recursive algorithm using the “sliding window” technique, the window being composed of several consecutive nodes. In a single step, the connectivity probabilities for all nodes included in the window are found. Subsequently, the window is moved one node forward. This process is repeated until, in the last step, the window reaches the terminal node. The connectivity probabilities found at that point are used to compute the node-pair reliability of the network system considered. The algorithm is designed especially for graphs with small distances between adjacent nodes, where the distance between two nodes is defined as the absolute value of the difference between the nodes’ numbers. The maximal distance between any two adjacent nodes is denoted by Γ(G), where G symbolizes a random graph. If Γ(G)=2 then the method can be applied for directed as well as undirected graphs whose nodes and edges are subject to failure. This is important in view of the fact that many algorithms computing network reliability are designed for graphs with failure-prone edges and reliable nodes. If Γ(G)=3 then the method's applicability is limited to undirected graphs with reliable nodes. The main asset of the presented algorithms is their low numerical complexity—O(n), where n denotes the number of nodes.     

A preliminary study of a diagonal channel-routing model

The layout of two-terminal nets in a VLSI channel is realized in a new diagonal channel-routing model (DCRM), where the tracks are segments respectively displayed at +45 ° and –45 ° on the two layers of the channel. A new definition of channel density is introduced, and a lower bound to the channel width is derived by the application of an algorithm, whose complexity is evaluated as a function of the channel density, and other parameters of the problem.A simple linear-time algorithm is proposed, which produces an optimal layout (i.e., it requires a channel of minimum width) if the length of the longest net equals the lower bound for the channel width. In any case, the number of vias is at most one for each net. Some particular solutions are proposed for problems with long nets.Specific problems are much easier in DCRM than in the classical Manhattan model. For example, any shift-by-i can be realized in DCRM in a channel of widthi.This work has been supported by Consiglio Nazionale delle Ricerche of Italy under a research grant.     

一种基于拓扑结构的网络两终端可靠性评估方法

为了评估一个大规模的实时长距离通信网络的可靠性,提出一种基于拓扑结构的网络两终端可靠性的计算方法。在化简网络拓扑结构的基础上,充分考虑链路和节点的可靠性,通过转置矩阵的积来表示两终端可靠性。实验结果表明,有向链路对不同网络性能测量产生影响,虽然失效频率和链接失效率很相似,但两终端可靠性多项式的复零点的位置相差很大,同时,转置矩阵的尺寸随着网络增大而增大。该方法对于优化网络、合理分配平均维修时间有实际应用价值。     

双管S型负阻器件的研究

模拟电路实验证明用两个同极性的晶体管以多种电路接法都能获得具有Ｓ型负阻特性的两端器件。在此实验基础上研制得到一种双向两端Ｓ型负阻器件（ＴＢＮＲＤ器件）。本文还对该器件产生负阻的原因进行了理论分析。     

基于节点导纳方程的串联补偿线路双端故障测距算法

由于与串补电容并联的氧化锌非线性电阻(MOV)的非线性特性,一般的故障测距方法对于有串联补偿装置的输电线路不再适用。作者基于传输线的节点导纳方程考虑了故障时串补装置的状态,提出了一种适用于串补线路的故障定位算法。该算法使用相参数(而非序参数)及两端的不同步数据,采用分布参数的线路模型,利用两个子算法搜索故障距离,通过比较两个子算法得到的过渡阻抗值排除伪根,选择一组正确解,从而获得准确的故障位置。仿真分析结果表明了该算法具有较好的定位精度。     

A factoring approach for the Steiner tree problem in undirected networks

In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(|E|) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where |E| is the number of edges. Based on this algorithm, we proposed an O(2^2c·|E|) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in |K|.     

An efficient method for reliability evaluation of multistate networks given all minimal path vectors

The multistate networks under consideration consist of a source node, a sink node, and some independent failure-prone components in between the nodes. The components can work at different levels of capacity. For such a network, we are interested in evaluating the probability that the flow from the source node to the sink node is equal to or greater than a demanded flow of d units. A general method for reliability evaluation of such multistate networks is using minimal path (cut) vectors. A minimal path vector to system state d is called a d-MP. Approaches for generating all d-MPs have been reported. Given that all d-MPs have been found, the issue becomes how to evaluate the probability of the union of the events that the component state vector is greater than or equal to at least one of the d-MPs. There is a need for a more efficient method of determining the probability of this union of events. In this paper, we report an efficient recursive algorithm for this union probability evaluation based on the Sum of Disjoint Products (SDP) principle, and name it the Recursive Sum of Disjoint Products (RSDP) algorithm. The basic idea is that, based on the SDP principle and a specially defined “maximum” operator, “⊕”, the probability of a union with L vectors can be calculated via calculating the probabilities of several unions with L-1 vectors or less. The correctness of RSDP is illustrated. The efficiency of this algorithm is investigated by comparing it with an existing algorithm that is generally accepted to be efficient. It is found that RSDP is more efficient than the existing algorithm when the number of components of a system is not too small. RSDP provides us with an efficient, systematic and simple approach for evaluating multistate network reliability given all d-MPs.     

A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time (n logn). We present a bidirectional search algorithm that has expected running time (n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time (an) on graphs of average degreea, as compared with (an) for unidirectional search.     

一种新的网络2-终端可靠性评估算法

为了评估网络可靠性,提出一种计算网络2-终端可靠性的新方法.此方法在图的前沿描述的概念基础上,通过分析依赖树宽的复杂度,将其应用于网络可靠性问题中.该方法将平均维修时间应用到实际管理维修队列中,尤其对于优化网络、合理分配平均维修时间有实际应用价值.     

基于双回线环流的时域法故障定位

该文提出了一种利用双端电流量实现双回线故障定位的时域测距算法。该算法利用双回线环流网与两侧系统无关且两端电压为零的特点，只用线路两端的电流量，就可计算出环流网的沿线电压分布，并根据从两端计算得到的电压分布差值在故障点处最小的原理实现测距。由于避免了使用电压量，故该测距原理不受电容式电压互感器(CVT)不能传变高频电压暂态信号的限制，该算法能够利用故障全过程的任何一段数据实现测距，且该算法所需数据窗短，只要略大于被测线路传输时问的2倍即可。该算法采用分布参数线模，克服了忽略线路电容带来的误差，适用于高压长距离输电线。仿真结果表明：测距误差将小于0．15km，且测距精度不受故障类型和过渡电阻的影响。