K终端可靠度分解算法中多边形→链简化定理的完善

无向网络K终端可靠度的分解算法中,包括多边形→链简化在内的等可靠度简化和分解定理结合,可以降低算法的复杂度。本文完善了边随机无向网络和混合随机无向网络的4#,6#,7#型多边形→链简化定理。计算机编程验证了其正确性。     

利用因子分解方法计算网络的根通信可靠性

本文使用因子分解(factoring)的方法计算网络的根通信可靠性(存在从根点到每一个其它结点正常运行道路的概率)。我们充分利用无圈有向网络的拓扑结构提出了两个新的可靠性保护缩减(Reliability-Preserving Reduction)和一个进行因子分解的选边规则。在此基础上,给出一个因子分解算法(factoring algorithm)。对于不是非常稠密的网络,该算法是非常有效的。     

Factoring Algorithms for Computing K-Terminal Network Reliability

Let GK denote a graph G whose edges can fail and with a set K ? V specified. Edge failures are independent and have known probabilities. The K-terminal reliability of GK, R(GK), is the probability that all vertices in K are connected by working edges. A factoring algorithm for computing network reliability recursively applies the formula R(GK) = piR(GK * ei) + qiR(GK - ei) where GK * ei is GK, with edge ei contracted, GK - ei is GK with ei deleted and pi ? 1 - qi is the reliability of edge ei. Various reliability-preserving reductions can be performed after each factoring operation in order to reduce computation. A unified framework is provided for complexity analysis and for determining optimal factoring strategies. Recent results are reviewed and extended within this framework.     

Polygon-to-chain reductions work for networks with imperfect vertices

One of the techniques known as the Polygon-to-Chain reductions for computing the terminal reliabilities of networks with perfect vertices is generalised for computing the terminal reliabilities of networks with imperfect vertices. The necessary reduction formulas and new vertex/edge reliabilities are established. Consequently, the terminal reliabilities of any series-parallel network with imperfect vertices can also be computed in linear time. This extends a result of Satyanarayana and Wood on the case where all vertices are perfect.     

Spatial error concealment with edge related perceptual considerations

Video transmission over error-prone networks can suffer from packet erasures which can greatly reduce the quality of the received video. Error concealment methods reduce the perceived quality degradation at the receiving end by masking the effects of such errors. They accomplish this by exploiting temporal and spatial correlations that exist in image sequences. Spatial error concealment approaches conceal errors by making use of spatial information only which is necessary in cases where motion information is not available or reliable. The performance of such methods can be greatly increased if perceptual considerations are taken into account as, e.g., the preservation of edge information. This paper proposes a spatial error concealment method that uses edge-related information in order not only to preserve existing edges but also to avoid introducing new strong ones by switching to a smooth approximation of missing information where necessary. A novel switching algorithm which uses the directional entropy of neighbouring edges chooses between two interpolation methods, a directional along detected edges or a bilinear using the nearest neighbouring pixels. Results show that the performance of the proposed method is better compared to both ‘single interpolation’ and to edge strength-based switching methods.     

A practical implementation of the factoring theorem for networkreliability

The factoring theorem is a simple tool for determining the K -terminal reliability of a network, i.e. the probability that a given set K of terminals in the network are connected to each other by a path of working edges. An implementation of an algorithm which uses the factoring theorem, in conjunction with degree-1 and degree-2 vertex reductions, to determine the reliability of a network is presented. Networks treated have completely reliable nodes and have edges which fail statistically and independently with known probabilities. The reliability problem is to determine the probability that all nodes in a designated set of nodes can communicate with each other. Such an implementation of the factoring theorem can be incorporated in a small, stand-alone program of about 500 lines of code. A program of this type requires little computer memory and is ideally suited for microcomputer use     

Maximizing the Mean Number of Communicating Vertex Pairs in Series-Parallel Networks

A communication network can be modelled as a probabilistic graph where each of b edges represents a communication line and each of n vertices represents a communication processor. Each edge e (vertex v) functions with probability Pe (pv). If edges fail independently with uniform probability p and vertices do not fail, the probability that the network is connected is the probabilistic connectedness and is a standard measure of network reliability. The most reliable maximal series-parallel networks by this measure are those with exactly two vertices of degree two. However, as p becomes small, or n becomes large, the probability that even the most reliable series-parallel network is connected falls very quickly. Therefore, we wish to optimize a network with respect to another reliability measure, mean number of communicating vertex pairs. Experimental results suggest that this measure varies with p, with the diameter of the network, and with the number of minimum edge cutsets. We show that for large p, the most reliable series-parallel network must have the fewest minimum edge cutsets and for small p, the most reliable network must have maximum pairs of adjacent edges. We present a construction which incrementally inproves the communicating vertex pair mean for many networks and demonstrates that a fan maximizes this measure over maximal series parallel networks with exactly two edge cutsets of size two.     

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

Extracting the overlapped sub-regions in wireless sensor networks

In wireless sensor networks, the overlapped sub-regions (faces) are generated due to the intersections among the sensing ranges of nodes. The faces play a significant role in solving the three problems k-coverage (i.e., all the points in the interested field should be covered by at least k active nodes while maintaining connectivity between all active nodes), coverage scheduling and cover sets. To find the faces and discover their coverage degrees, this article presents a distributed algorithm that runs in three steps. First, a colored graph called Intersection Points Colored Graph (IPCG) is proposed, in which the vertices are defined by the range-intersections of nodes-devices and are colored according to the position of these intersections in relation to the ranges of the nodes. The vertex that located on perimeter of the node’s range is colored by red, while the green vertex is an intersection of two ranges inside the range of a third node. The edge that joins two red vertices is colored by red and the edge that joins two green vertices is colored by green while the edge that joins two distinct colored vertices is colored by blue. Second, based on their properties and distinct features, the faces in IPCG are classified into five classes (simple, negative, red, green and positive). Third, based on faces classification, the Three Colored Trees algorithm is proposed to extract the faces in linear time in terms of the number of vertices and edges in IPCG.

     

On the reliability of a number of s-p reducible graphs

Let G=(V,E) be a graph whose edges may fail with known probabilities and let K a subset of V be specified. The overall reliability of G, denoted by R(G), is the probability that all vertices in K=V communicate with each other. We have two types of graphs, s-p reducible and s-p complex, depending on whether after series-arallel reductions the result is a single edge or not. A number of s-p reducible graphs are presented and expressions that evaluate their overall reliability are introduced.     

激光再制造中缺陷识别关键技术研究

损伤零件缺陷区域的三维形貌检测对于激光机器人加工过程的智能化具有重要作用。系统实现了激光加工中损伤零件的缺陷识别,并提出损伤零件缺陷边界检测的高精度算法。利用基于点特征面积累加的法矢法识别出缺陷边界点,生成初始缺陷边界,针对初始缺陷边界具有不连续、多分支、锯齿状边界等问题,提出了三步优化处理方法,最终得到封闭、高精度的损伤零件的缺陷边界。系统运行处理速度快,精度高,可完全满足工业零件智能化激光再制造的要求。     

Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of ?(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.     

车辆网络多平台卸载智能资源分配算法

为了降低计算任务的时延和系统的成本,移动边缘计算(MEC)被用于车辆网络,以进一步改善车辆服务。该文在考虑计算资源的情况下对车辆网络时延问题进行研究,提出一种多平台卸载智能资源分配算法,对计算资源进行分配,以提高下一代车辆网络的性能。该算法首先使用K临近(KNN)算法对计算任务的卸载平台(云计算、移动边缘计算、本地计算)进行选择,然后在考虑非本地计算资源分配和系统复杂性的情况下,使用强化学习方法,以有效解决使用移动边缘计算的车辆网络中的资源分配问题。仿真结果表明,与任务全部卸载到本地或MEC服务器等基准算法相比,提出的多平台卸载智能资源分配算法实现了时延成本的显著降低,平均可节省系统总成本达80%。     

Efficient and Exact Reliability Evaluation for Networks With Imperfect Vertices

The factoring theorem, and BDD-based algorithms have been shown to be efficient reliability evaluation methods for networks with perfectly reliable vertices. However, the vertices, and the links of a network may fail in the real world. Imperfect vertices can be factored like links, but the complexity increases exponentially with their number. Exact algorithms based on the factoring theorem can therefore induce great overhead if vertex failures are taken into account. To solve the problem, a set of exact algorithms is presented to deal with vertex failures with little additional overhead. The algorithms can be used to solve terminal-pair, k-terminal, and all-terminal reliability problems in directed, and undirected networks. The essential variable is defined to be a vertex or a link of a network whose failure has the dominating effect on network reliability. The algorithms are so efficient that it takes less than 1.2 seconds on a 1.67 GHz personal computer to identify the essential variable of a network having 2⁹⁹ paths. When vertex failures in a 3 times 10 mesh network are taken into account, the proposed algorithms can induce as little as about 0.3% of runtime overhead, while the best result from factoring algorithms incurs about 300% overhead     

Unsupervised contour closure algorithm for range image edge-based segmentation.

This paper presents an efficient technique for extracting closed contours from range images' edge points. Edge points are assumed to be given as input to the algorithm (i.e., previously computed by an edge-based range image segmentation technique). The proposed approach consists of three steps. Initially, a partially connected graph is generated from those input points. Then, the minimum spanning tree of that graph is computed. Finally, a postprocessing technique generates a single path through the regions' boundaries by removing noisy links and closing open contours. The novelty of the proposed approach lies in the fact that, by representing edge points as nodes of a partially connected graph, it reduces the contour closure problem to a minimum spanning tree partitioning problem plus a cost function minimization stage to generate closed contours. Experimental results with synthetic and real range images, together with comparisons with a previous technique, are presented.     

Hypermedia and network reliability

A simple algorithm utilizing the factoring theorem and other elementary network reductions is available to determine network reliability in a number of different forms. This paper describes a computer-based implementation of such an algorithm housed in a hypermedia environment. The environment can provide for both the formulation and the solution of reliability problems. In our treatment the user draws the network interactively on the computer screen and clicks an on-screen button to perform the reliability analysis. This provides an alternative to manual calculations that become tedious or impossible with networks which are neither series-parallel nor extremely small.     

QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

Computing 2-terminal reliability for radio-broadcast networks

The authors present a probabilistic graph model for radio broadcast networks where nodes fail randomly and the edges are perfectly reliable. This model can represent the general case where both the nodes and edges can fail. Using this model, it is shown that the two-terminal reliability problem for radio broadcast networks is computationally difficult, in particular #P-complete, even in two important restricted cases. Efficient bounding techniques based on subgraph counts and vertex-packing methods are presented. The subgraph counting and vertex-packing bounds are the counterparts of the subgraph counting and edge-packing bounds for wired point-to-point networks with reliable nodes and unreliable links. The authors define series and parallel node reductions for arbitrary networks with unreliable nodes and reliable edges, and they incorporate these reductions into a new polynomial-time algorithm to improve the vertex-packing bounds via approximation by series-parallel reducible graphs