Parallel path consistency

Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, AC is still the preferred technique because it has a much lower time complexity. We are implementing parallel path consistency algorithms on multiprocessors and comparing their performance to the best sequential and parallel arc consistency algorithms.^(1,2) (See also work by Kerethoet al. ⁽³⁾ and Kasif⁽⁴⁾) Preliminary work has shown linear performance increases for parallelized path consistency and also shown that in many cases performance is significantly better than the theoretical worst case. These two results lead us to believe that parallel path consistency may be a superior filtering technique. Finally, we have implemented path consistency as an outer product computation and have obtained good results (e.g., linear speedup on a 64K-node Connection Machine 2).     

Metric-based reasoning about pseudocode design in the partial metrics system

The goal of the PMS project is to produce an environment in which the intelligent online assessment of the design for large-scale ADA programming projects is provided. The focus is on the representation of knowledge about the design process for an individual module. Changes in pseudocode complexity are measured in terms of partial metrics. These metrics can take the designers inferences about the pseudocode program structure into account when assessing module complexity. Next, a model of the stepwise refinement process is given which demonstrates how pseudocode elaboration decisions can be modelled in partial metric terms. Finally, the decisions associated with each refinement step for 17 example refinements taken from the computer science literature are described using partial metrics.     

基于栅格法-模拟退火法的机器人路径规划

路径规划是机器人技术中的重要组成部分,分全局路径规划和局部路径规划。本文将栅格法与模拟退火法结合,采用栅格法表示环境信息。局部路径规划主要基于模拟退火法,使路径跳出局部极小点,到达目标位置。     

Dynamic Survivability in WDM Mesh Networks Under Dynamic Traffic

Network survivability is a crucial requirement in WDM mesh networks. In this paper, we systematically consider the problem of dynamic survivability with dynamic single link failure in WDM networks under dynamic traffic demands. Specifically, we investigate various protection schemes, such as dedicated path protection (DPP), shared path protection (SPP), dedicated link protection (DLP), shared link protection (SLP), and two restoration schemes, path restoration (PR) and link restoration (LR). Moreover, two new shared protection methods are proposed, i.e., SRLG-based shared link protection (SRLG-SLP) and SRLG-based shared path protection (SRLG-SPP). The SRLG (shared risk link group) constraint defines the availability of protection resources to a working path, which requires that any two working paths sharing the same risk of failure (or in the same SRLG) cannot share the same protection resources. Furthermore, in our study, we consider a more practical dynamic single-link failure model, in which the link-failure-interarrival time and link-failure-holding time are considered as two independent parameters. Based on this link-failure model, extensive simulations are done to analyze and compare the dynamic survivable performance of various protection and restoration schemes. Resource utilization, protection efficiency, restoration efficiency, and service disruption ratio are employed as survivable performance metrics versus traffic load, link-failure frequency, and link-failure reparation time to evaluate the survivable performance. Many meaningful results are given. In addition, we show that the developed SRLG-SLP and SRLG-SPP protection schemes perform very well in terms of protection efficiency and service disruption ratio, while sacrificing some performance in terms of resource utilization.     

Using rainbow net simulation to measure fault tolerance in a multiprocessor

The Rainbow net simulation technique is applied to modelling the impact of system load and fault handling on the availability of a fault-tolerant multiprocessor architecture. Rainbow nets are described along with the motivation for creating this modelling technique. A Rainbow net fault-handling model is created for the fault-tolerant multiprocessor architecture and the topology is shown to remain constant in size, independent of the number of processor, memory and I/O elements configured in the system. Simulation is performed with a varying load in terms of the number of active jobs the system must support. Results are given showing how the fault-tolerant capability varies with load. Two new metrics for evaluating fault tolerance are introduced; namely full fault-tolerability and partial fault-tolerability. They are based on simple observations in the model.     

Quality of manual data collection in Java software: an empirical investigation

Data collection, both automatic and manual, lies at the heart of all empirical studies. The quality of data collected from software informs decisions on maintenance, testing and wider issues such as the need for system re-engineering. While of the two types stated, automatic data collection is preferable, there are numerous occasions when manual data collection is unavoidable. Yet, very little evidence exists to assess the error-proneness of the latter. Herein, we investigate the extent to which manual data collection for Java software compared with its automatic counterpart for the same data. We investigate three hypotheses relating to the difference between automated and manual data collection. Five Java systems were used to support our investigation. Results showed that, as expected, manual data collection was error-prone, but nowhere near the extent we had initially envisaged. Key indicators of mistakes in manual data collection were found to be poor developer coding style, poor adherence to sound OO coding principles, and the existence of relatively large classes in some systems. Some interesting results were found relating to the collection of public class features and the types of error made during manual data collection. The study thus offers an insight into some of the typical problems associated with collecting data manually; more significantly, it highlights the problems that poorly written systems have on the quality of visually extracted data.     

由有穷自动机构造正则表达式的新算法

本文借助图论的理论，通过识别回路和不包含回路的由起始状态到终止状态的路径的方法，提出一种构造给定有穷自动机对应的正则表达式的新算法，并给出具体实例。     

Layout Optimization for Greenhouse WSN Based on Path Loss Analysis

When wireless sensor networks (WSN) are deployed in the vegetable greenhouse with dynamic connectivity and interference environment, it is necessary to increase the node transmit power to ensure the communication quality, which leads to serious network interference. To offset the negative impact, the transmit power of other nodes must also be increased. The result is that the network becomes worse and worse, and node energy is wasted a lot. Taking into account the irregular connection range in the cucumber greenhouse WSN, we measured the transmission characteristics of wireless signals under the 2.4 Ghz operating frequency. For improving network layout in the greenhouse, a semi-empirical prediction model of signal loss is then studied based on the measured data. Compared with other models, the average relative error of this semi-empirical signal loss model is only 2.3%. Finally, by combining the improved network topology algorithm and tabu search, this paper studies a greenhouse WSN layout that can reduce path loss, save energy, and ensure communication quality. Given the limitation of node-degree constraint in traditional network layout algorithms, the improved algorithm applies the forwarding constraint to balance network energy consumption and constructs asymmetric network communication links. Experimental results show that this research can realize the energy consumption optimization of WSN layout in the greenhouse.     

Heuristic collision-free path planning for an autonomous platform

In this paper, a heuristic and learning, algorithmic scheme for collision-free navigation is presented. This scheme determines an optimum collision-free navigation path of an autonomous platform by using a trial and error process, past navigation knowledge and current information extracted from the generated surrounding environment.