On problem transformability in VLSI

The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT ² andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT²=(n ²log² n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT ² andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6.     

Swarm Intelligent Compressive Routing in Wireless Sensor Networks

This article proposes a novel algorithm to improve the lifetime of a wireless sensor network. This algorithm employs swarm intelligence algorithms in conjunction with compressive sensing theory to build up the routing trees and to decrease the communication rate. The main contribution of this article is to extend swarm intelligence algorithms to build a routing tree in such a way that it can be utilized to maximize efficiency, thereby rectifying the delay problem of compressive sensing theory and improving the network lifetime. In addition, our approach offers accurate data recovery from small amounts of compressed data. Simulation results show that our approach can effectively extend the network lifetime of a large‐scale wireless sensor network.     

Effect of membrane characteristics on the performance of membrane bioreactors for oily wastewater treatment

Influence of membrane material and pore size on the performance of a submerged membrane bioreactor (sMBR) for oily wastewater treatment was investigated. The sMBR had a working volume of about 19 L with flat sheet modules at the same hydrodynamic conditions. Five types of micro- and ultra-polymeric membranes containing cellulose acetate (CA), cellulose nitrate (CN), polyamide (PA), polyvinylidene difluoride (PVDF) and polyethersulfone (PES) were used and their filtration performance in terms of permeability, permeate quality and fouling intensity were evaluated. Characterization of the membranes was done by performing some analysis such as pore size distribution; contact angle and scanning electronic microscopy (SEM) microphotograph on all membranes. The quality of permeates from each membrane was identified by measuring chemical oxygen demand (COD). The results showed more irreversible fouling intensity for membranes with larger pore size which can be due to more permeation of bioparticles and colloids inside the pores. Membrane characteristics have a major role in the preliminary time of the filtration before cake layer formation so that the PA with the highest hydrophilicity had the lowest permeability decline by fouling in this period. Also, the PVDF and PES membranes had better performance according to better permeate quality in the preliminary time of the filtration related to smaller pore size and also their better fouling resistance and chemical stability properties. However, all membranes resulted in the same permeability and permeate quality after cake layer formation. An overall efficiency of about 95% in COD removal was obtained for oily wastewater treatment by the membranes used in this study.     

“How do you know that I don’t understand?” A look at the future of intelligent tutoring systems

Many software systems would significantly improve performance if they could adapt to the emotional state of the user, for example if Intelligent Tutoring Systems (ITSs), ATM’s, ticketing machines could recognise when users were confused, frustrated or angry they could guide the user back to remedial help systems so improving the service. Many researchers now feel strongly that ITSs would be significantly enhanced if computers could adapt to the emotions of students. This idea has spawned the developing field of affective tutoring systems (ATSs): ATSs are ITSs that are able to adapt to the affective state of students. The term “affective tutoring system” can be traced back as far as Rosalind Picard’s book Affective Computing in 1997.This paper presents research leading to the development of Easy with Eve, an ATS for primary school mathematics. The system utilises a network of computer systems, mainly embedded devices to detect student emotion and other significant bio-signals. It will then adapt to students and displays emotion via a lifelike agent called Eve. Eve’s tutoring adaptations are guided by a case-based method for adapting to student states; this method uses data that was generated by an observational study of human tutors. This paper presents the observational study, the case-based method, the ATS itself and its implementation on a distributed computer systems for real-time performance, and finally the implications of the findings for Human Computer Interaction in general and e-learning in particular. Web-based applications of the technology developed in this research are discussed throughout the paper.     

Cluster Size Optimization in Sensor Networks with Decentralized Cluster-Based Protocols

Network lifetime and energy-efficiency are viewed as the dominating considerations in designing cluster-based communication protocols for wireless sensor networks. This paper analytically provides the optimal cluster size that minimizes the total energy expenditure in such networks, where all sensors communicate data through their elected cluster heads to the base station in a decentralized fashion. LEACH, LEACH-Coverage, and DBS comprise three cluster-based protocols investigated in this paper that do not require any centralized support from a certain node. The analytical outcomes are given in the form of closed-form expressions for various widely-used network configurations. Extensive simulations on different networks are used to confirm the expectations based on the analytical results. To obtain a thorough understanding of the results, cluster number variability problem is identified and inspected from the energy consumption point of view.     

An optimal algorithm for rectilinear steiner trees for channels with obstacles

The channel rectilinear Steiner tree problem is to construct an optimal rectilinear Steiner tree interconnecting n terminals on the upper shore and the lower shore of a channel without crossing any obstacles inside the channel. However, intersecting boundaries of obstacles is allowed. We present an algorithm that computes an optimal channel rectilinear Steiner tree in O(F₁(k)n + F₂(k)) time, where k is the number of obstacles inside the channel and F₁ and F₂ are exponential functions of k. For any constant k the proposed algorithm runs in O(n) time.     

Fast template placement for reconfigurable computing systems

This article presents fast online placement methods for dynamically reconfigurable systems, as well as offline 3D placement algorithms for statically reconfigurable architectures     

Maximumk-covering of weighted transitive graphs with applications

Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn ²)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn ²), wheren is the input size.This Work was supported in part by the National Science Foundation under Grant MIP-8709074 and MIP-8921540.     

Discrete warehouse problem

A discrete warehouse is a collection of two-dimensional unit-square objects (robot and obstacles), which are allowed to move horizontally and vertically along grid lines. In this paper, we consider motion planning problems in a discrete warehouse with movable obstacles. In such a setup one is allowed to move some of the obstacles in order to:

1. (1) navigate the robot between an initial and a final position of the warehouse, and

2. (2) construct a clearing (path) between two specified points.

The final positions of the obstacles are unimportant for our problems.

We consider two forms of obstacle manipulations:

1. (a) remote, when the obstacles are moved by a remote mechanism, and

2. (b) contact, when the obstacles are moved only by direct contact of the robot.

We present necessary and sufficient conditions for the existence of a motion in both cases, and propose efficient algorithms for constructing feasible motions.     

On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.