A Class of Algorithms for Collision Resolution with Multiplicity Estimation

The wireless connectivity in pervasive computing has ephemeral character and can be used for creating ad hoc networks, sensor networks, connection with RFID (Radio Frequency Identification) tags etc. The communication tasks in such wireless networks often involve an inquiry over a shared channel, which can be invoked for: discovery of neighboring devices in ad hoc networks, counting the number of RFID tags that have a certain property, estimating the mean value contained in a group of sensors etc. Such an inquiry solicits replies from possibly large number of terminals n. This necessitates the usage of algorithms for resolving batch collisions (conflicts) with unknown conflict multiplicity n. In this paper we present a novel approach to the problem of collision resolution for batch conflicts. We show how the conventional tree algorithms for collision resolution can be used to obtain progressively accurate estimation of the multiplicity. We use the estimation to propose a more efficient binary tree algorithm, termed Estimating Binary Tree (EBT) algorithm. The EBT algorithm is suited for implementation when the conflicting nodes are passive, such as e.g. RFID tags. We extend the approach to design the Interval Estimation Conflict Resolution (IECR) algorithm. For n→∞ we prove that the efficiency achieved by IECR for batch arrivals is identical with the efficiency that Gallager’s FCFS algorithm achieves for Poisson packet arrivals. For finite n, the simulation results show that IECR is, to the best of our knowledge, the most efficient batch resolution algorithm reported to date.     

Genetically optimized fuzzy polynomial neural networks with fuzzy set-based polynomial neurons

In this paper, we propose and investigate a new category of neurofuzzy networks—fuzzy polynomial neural networks (FPNN) endowed with fuzzy set-based polynomial neurons (FSPNs) We develop a comprehensive design methodology involving mechanisms of genetic optimization, and genetic algorithms (GAs) in particular. The conventional FPNNs developed so far are based on the mechanisms of self-organization, fuzzy neurocomputing, and evolutionary optimization. The design of the network exploits the FSPNs as well as the extended group method of data handling (GMDH). Let us stress that in the previous development strategies some essential parameters of the networks (such as the number of input variables, the order of the polynomial, the number of membership functions, and a collection of the specific subset of input variables) being available within the network are provided by the designer in advance and kept fixed throughout the overall development process. This restriction may hamper a possibility of developing an optimal architecture of the model. The design proposed in this study addresses this issue. The augmented and genetically developed FPNN (gFPNN) results in a structurally optimized structure and comes with a higher level of flexibility in comparison to the one we encounter in the conventional FPNNs. The GA-based design procedure being applied at each layer of the FPNN leads to the selection of the most suitable nodes (or FSPNs) available within the FPNN. In the sequel, two general optimization mechanisms are explored. First, the structural optimization is realized via GAs whereas the ensuing detailed parametric optimization is carried out in the setting of a standard least square method-based learning. The performance of the gFPNN is quantified through experimentation in which we use a number of modeling benchmarks—synthetic and experimental data being commonly used in fuzzy or neurofuzzy modeling. The obtained results demonstrate the superiority of the proposed networks over the models existing in the references.     

Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions

A variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C=2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs.     

Optimal biocompatible solvent design for a two-stage extractive fermentation process with cell recycling

In this study, crisp and fuzzy multiple-goal optimization approaches are respectively introduced to design an optimal biocompatible solvent to a two-stage extractive fermentation with cell recycling for ethanol production. When designing a biocompatible solvent for the extractive fermentation process, many issues, such as extractive efficiency, conversion, amount of solvent utilized and so on, have to be considered. An interactive multiple-goal design procedure is introduced to determine a trade-off result in order to satisfy such contradicted goals. Both approaches could be iterated to solve the interactive multiple-goal design problem in order to yield a trade-off result. However, the crisp optimization design is a tedious task that requires the designer to provide various pairs of the upper bounds for the design problem to obtain the corresponding solution. The fuzzy optimization approach is able to be trade-off several goals simultaneously and to yield the overall satisfactory grade for the product/process design problem.     

Perceptual evaluation of color gamut mapping algorithms

The recommendation of the CIE has been followed as closely as possible to evaluate the accuracy of five color gamut mapping algorithms (GMAs)—two nonspatial and three spatial algorithms—by psychophysical experiments with 20 test images, 20 observers, one test done on paper and a second one on display. Even though the results do not show any overall “winner,” one GMA is definitely perceived as not accurate. The importance of a high number of test images to obtain robust evaluation is underlined by the high variability of the results depending on the test images. Significant correlations between the percentage of out‐of‐gamut pixels, the number of distinguishable pairs of GMAs, and the perceived difficulty to distinguish them have been found. The type of observers is also important. The experts, who prefer a spatial GMA, show a stronger consensus and look especially for a good rendering of details, whereas the nonexperts hardly make a difference between the GMAs. © 2008 Wiley Periodicals, Inc. Col Res Appl, 33, 470–476, 2008     

An efficient parallel strategy for the perfect domination problem on distance-hereditary graphs

A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs.     

A fast evolutionary pursuit algorithm based on linearly combining vectors

In this paper, we propose a fast Evolutionary pursuit algorithm. It searches for optimal discriminant vectors through linearly combining standard bases. Experiments on the Yale and ORL databases verify its effectiveness and enhanced efficiency.     

计算几何与并行算法

本文首先介绍了计算几何的基本概念,论述了计算几何的四个基本问题,即几何搜索问题、相交问题、邻接问题及凸壳问题。然后重点分析了凸壳构造问题,介绍了其最佳串行算法、及相应的并行算法。接着对一些计算几何的串行及并行算法进行了分析比较。最后提出了笔者对新一代并行计算机系统上设计计算几何并行算法的看法。     

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

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