Computer Engineering Commons^™

Towards An Optimal Algorithm For Computing Fixed Points: Dynamical Systems Approach, With Applications To Transportation Engineering, Ruey L. Cheu, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical problems, it is desirable to find an equilibrium. For example, equilibria are important in transportation engineering.

Many urban areas suffer from traffic congestion. Intuitively, it may seem that a road expansion (e.g., the opening of a new road) should always improve the traffic conditions. However, in reality, a new road can actually worsen traffic congestion. It is therefore extremely important that before we start a road expansion project, we first predict the effect of this project on traffic congestion.

When a new road is built, some traffic moves to this road to avoid congestion on the other …

Efficient Peer Assignment For Low-Latency Transmission Of Scalable Coded Images, Xiao Su, Tao Wang

Faculty Publications

In this paper, we propose efficient peer assignment algorithms for low-latency transmission of scalable coded images in peer-to-peer networks, in which peers may dynamically join and leave the networks. The objective of our algorithm is to minimize the transmission time of a requested image that is scalable coded. When an image is scalable coded in different bit rates, the bit stream encoded in a lower bit rate is a prefix subset of the one encoded in a higher bit rate. Therefore, a peer with the same requested image coded in any bit rate, even when it is different from the …

How To Reconcile Physical Theories With The Idea Of Free Will: From Analysis Of A Simple Model To Interval And Fuzzy Approaches, Julio C. Urenda, Olga Kosheleva

Departmental Technical Reports (CS)

Most modern physical theories are formulated in terms of differential equations. As a result, if we know exactly the current state of the world, then this state uniquely determines all the future events -- including our own future behavior. This determination seems to contradict the intuitive notion of a free will, according to which we are free to make decisions -- decisions which cannot be determined based on the past locations and velocities of the elementary particles. In quantum physics, the situation is somewhat better in the sense that we cannot determine the exact behavior, but we can still determine …

Towards More Adequate Representation Of Uncertainty: From Intervals To Set Intervals, With The Possible Addition Of Probabilities And Certainty Degrees, J. T. Yao, Y. Y. Yao, Vladik Kreinovich, Paulo Pinheiro Da Silva, Scott A. Starks, Gang Xiang, H. T. Nguyen

Departmental Technical Reports (CS)

In the ideal case of complete knowledge, for each property Pi (such as "high fever", "headache", etc.), we know the exact set Si of all the objects that satisfy this property. In practice, we usually only have partial knowledge. In this case, we only know the set Si- of all the objects about which we know that Pi holds and the set Si+ about which we know that Pi may hold (i.e., equivalently, that we have not yet excluded the possibility of Pi). This pair of sets is called a set interval.

Based on the knowledge of the original properties, …

Estimating Variance Under Interval And Fuzzy Uncertainty: Parallel Algorithms, Karen Villaverde, Gang Xiang

Departmental Technical Reports (CS)

Traditional data processing in science and engineering starts with computing the basic statistical characteristics such as the population mean E and population variance V. In computing these characteristics, it is usually assumed that the corresponding data values x1,...,xn are known exactly. In many practical situations, we only know intervals [xi-,xi+] that contain the actual (unknown) values of xi or, more generally, a fuzzy number that describes xi. In this case, different possible values of xi lead, in general, to different values of E and V. In such situations, we are interested in producing the intervals of possible values of E …

How To Measure A Degree Of Mismatch Between Probability Models, P-Boxes, Etc.: A Decision-Theory-Motivated Utility-Based Approach, Luc Longpre, Scott Ferson, W. Troy Tucker

Departmental Technical Reports (CS)

Different models can be used to describe real-life phenomena: deterministic, probabilistic, fuzzy, models in which we have interval-valued or fuzzy-valued probabilities, etc. Models are usually not absolutely accurate. It is therefore important to know how accurate is a given model. In other words, it is important to be able to measure a mismatch between the model and the empirical data. In this paper, we describe an approach of measuring this mismatch which is based on the notion of utility, the central notion of utility theory.

We also show that a similar approach can be used to measure the loss of …

Relations Between Interval Computing And Soft Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper starts with a brief reminder of why data processing and knowledge processing are needed in the first place, why interval and fuzzy methods are needed for data and knowledge processing, and which of the possible data and knowledge processing techniques we should use. Then, we explain how these reasonable soft computing techniques are naturally related with interval computing. Finally, we explain the need for interval-valued fuzzy techniques -- techniques which will be used a lot in our future applications -- and how the transition to such techniques is also related to interval computing.

Towards Fast Algorithms For Processing Type-2 Fuzzy Data: Extending Mendel's Algorithms From Interval-Valued To A More General Case, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

It is known that processing of data under general type-1 fuzzy uncertainty can be reduced to the simplest case -- of interval uncertainty: namely, Zadeh's extension principle is equivalent to level-by-level interval computations applied to alpha-cuts of the corresponding fuzzy numbers.

However, type-1 fuzzy numbers may not be the most adequate way of describing uncertainty, because they require that an expert can describe his or her degree of confidence in a statement by an exact value. In practice, it is more reasonable to expect that the expert estimates his or her degree by using imprecise words from natural language -- …

Cahsi Year 2 Evaluation Report: Recruiting, Retaining, And Advancing Hispanics In Computing, Heather Thiry, Sarah Hug, Lecia Barker

Departmental Technical Reports (CS)

No abstract provided.

Applications Of 1-D Versions Of Image Referencing Techniques To Hydrology And To Patient Rehabilitation, Roberto Araiza, Martine Ceberio, Naga Suman Kanagala, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

In this paper, we consider two seemingly unrelated problems: the hydrology problem of relation between groundwater and surface water, and a problem of identification of human gait in neuro-rehabilitation. It turns out that in both problems, we can efficiently use soft computing-motivated algorithms originally developed for image referencing.

Beyond Intervals: Phase Transitions Lead To More General Ranges, Karen Villaverde, Gilbert Ornelas

Departmental Technical Reports (CS)

One of the main tasks of science and engineering is to use the current values of the physical quantities for predicting the future values of the desired quantities. Due to the (inevitable) measurement inaccuracy, we usually know the current values of the physical quantities with interval uncertainty. Traditionally, it is assumed that all the processes are continuous; as a result, the range of possible values of the future quantities is also known with interval uncertainty. However, in many practical situations (such as phase transitions), the dependence of the future values on the current ones becomes discontinuous. We show that in …

Selecting The Most Representative Sample Is Np-Hard: Need For Expert (Fuzzy) Knowledge, J. Esteban Gamez, Francois Modave, Olga Kosheleva

Departmental Technical Reports (CS)

One of the main applications of fuzzy techniques is to formalize the notions of "typical", "representative", etc.

The main idea behind fuzzy techniques is that they formalize expert knowledge expressed by words from natural language.

In this paper, we show that if we do not use this knowledge, i.e., if we only use the data, then selecting the most representative sample becomes a computationally difficult (NP-hard) problem. Thus, the need to find such samples in reasonable time justifies the use of fuzzy techniques.

Computing Lightweight Spanning Subgraphs Locally, Iyad A. Kanj, Ljubomir Perkovic, Ge Xia

Technical Reports

We consider the problem of computing bounded-degree lightweight plane spanning subgraphs of unit disk graphs in the local distributed model of computation. We are motivated by the hypothesis that such subgraphs can provide the underlying network topology for efficient unicasting and/or multicasting in wireless distributed systems. We start by showing that, for any integer $k \geq 2$, there exists a $k$-local distributed algorithm that, given a unit disk graph $U$ embedded in the plane, constructs a plane subgraph of $U$ containing a Euclidean Minimum Spanning Tree (EMST) of $V(U)$, whose degree is at most 6, and whose total weight is …

Priority Based Buffering Over Multiple Lossy Links Using Tcp Aware Layer Buffering, Kevin J. Savidge

Theses and Dissertations

Wireless military information systems require high reliability, which is difficult to achieve in adverse conditions. To provide high reliability, one must overcome packet loss across multiple wireless hops. Buffering packets in a lossy environment is well explored; however, the ability to selectively buffer TCP traffic across multiple lossy links is a new area of research. This document seeks to explore the delivery of high priority traffic in a lossy environment and conclude that prioritized buffing can increase the probability that a high priority download will finish, where others will fail. It is shown that buffering provides six times the throughput …

Mission Impact Analysis Visualization For Enhanced Situational Awareness, Sean C. M. Carroll

Theses and Dissertations

This research effort examines the creation of mission impact analysis visualizations to enhance situational awareness. It focuses on using prefuse to create a visualization that allows the user to quickly understand the impact of the failure of any element needed directly or indirectly for a mission. The visualization correctly identifies the direct or indirect impact on physical requirements such as network links and servers as well as non-physical elements such as the generation of a report, or ability to perform a task. The visualization provides an overview of the situation, as well as including enhancements to allow for greater detail …

Evaluating Security And Quality Of Service Considerations In Critical Infrastructure Communication Networks, Gregory R. Roberts

Theses and Dissertations

This thesis demonstrates the benefits of utility communication based on Internet technology, some dangers in using Internet technology in establishing a utility intranet connecting protection and control systems, and compares three different approaches to making reservations for routing traffic in the utility intranet based on different levels of background traffic. A model of expected background traffic on a national utility intranet is presented. The Utility Communication Architecture 2.0 and the International Electrotechnical Commission (IEC) 61850 began laying the groundwork in 2002 in establishing an infrastructure allowing power substations, program logic controllers, remote terminal units, intelligent electronic devices, and other devices …

Hot Swapping Protocol Implementations In The Opnet Modeler Development Environment, Mark E. Coyne

Theses and Dissertations

This research effort demonstrates hot swapping protocol implementations in OPNET via the building of a dependency injection testing framework. The thesis demonstrates the externalization (compiling as stand-alone code) of OPNET process models, and their inclusion into custom DLL's (Dynamically Linked Libraries). A framework then utilizes these process model DLL's, to specify, or “inject,” process implementations post-compile time into an OPNET simulation. Two separate applications demonstrate this mechanism. The first application is a toolkit that allows for the testing of multiple routing related protocols in various combinations without code re-compilation or scenario re-generation. The toolkit produced similar results as the same …

Hardware Algorithm Implementation For Mission Specific Processing, Jason W. Shirley

Theses and Dissertations

There is a need to expedite the process of designing military hardware to stay ahead of the adversary. The core of this project was to build reusable, synthesizeable libraries to make this a possibility. In order to build these libraries, Matlab® commands and functions, such as Conv2, Round, Floor, Pinv, etc., had to be converted into reusable VHDL modules. These modules make up reusable libraries for the Mission Specific Process (MSP) which will support AFRL/RY. The MSP allows the VLSI design process to be completed in a mere matter of days or months using an FPGA or ASIC design, as …

Scripted Mobile Network Routing In A Contested Environment, Anthony R. Otto

Theses and Dissertations

Mobile wireless network protocols currently run on optimistic routing algorithms, adjusting node connectivity only when the chosen connectivity metrics, such as signal strength, pass beyond minimum thresholds. Optimistic routing has several weaknesses. Optimistic routing suffers from increased network overhead during increased frequency of node movement and increased node density per area, and optimistic routing also suffers from non-optimistic access change for individual nodes. The overall communication throughput of a network may be increased if the network topology change is scripted; a scripted plan can allow messages to travel along a more efficient topological path while creating less topology control traffic. …

Globally Optimal Grouping For Symmetric Closed Boundaries By Combining Boundary And Region Information, Joachim S. Stahl, Song Wang

Faculty Publications

Many natural and man-made structures have a boundary that shows a certain level of bilateral symmetry, a property that plays an important role in both human and computer vision. In this paper, we present a new grouping method for detecting closed boundaries with symmetry. We first construct a new type of grouping token in the form of symmetric trapezoids by pairing line segments detected from the image. A closed boundary can then be achieved by connecting some trapezoids with a sequence of gap-filling quadrilaterals. For such a closed boundary, we define a unified grouping cost function in a ratio form: …

Embedded Noninteractive Continuous Bot Detection, Roman V. Yampolskiy, Venu Govindaraju

Faculty and Staff Scholarship

Multiplayer online computer games are quickly growing in popularity, with millions of players logging in every day. While most play in accordance with the rules set up by the game designers, some choose to utilize artificially intelligent assistant programs, a.k.a. bots, to gain an unfair advantage over other players. In this article we demonstrate how an embedded noninteractive test can be used to prevent automatic artificially intelligent players from illegally participating in online game-play. Our solution has numerous advantages over traditional tests, such as its nonobtrusive nature, continuous verification, and simple noninteractive and outsourcing-proof design. © 2008 ACM.

2008 (Spring) Ensi Informer Magazine, Morehead State University. Engineering Sciences Department

ENSI Informer Magazine Archive

The ENSI Informer Magazine published in the spring of 2008.

Network Visualization Design Using Prefuse Visualization Framework, John Mark Belue

Theses and Dissertations

Visualization of network simulation events or network visualization is an effective and low cost method to evaluate the health and status of a network and analyze network designs, protocols, and network algorithms. This research designed and developed a network event visualization framework using an open source general visualization toolkit. This research achieved three major milestones during the development of this framework: A robust network simulator trace file parser, multiple network visualization layouts {including user-defined layouts, and precise visualization timing controls and integrated display of network statistics. The parser architecture is extensible to allow customization of simulator trace formats that are …

Semantic Components: A Model For Enhancing Retrieval Of Domain- Specific Information, Susan Loucette Price

Dissertations and Theses

Despite the success of general Internet search engines, information retrieval remains an incompletely solved problem. Our research focuses on supporting domain experts when they search domain-specific libraries to satisfy targeted information needs. The semantic components model introduces a schema specific to a particular document collection. A semantic component schema consists of a two-level hierarchy, document classes and semantic components. A document class represents a document grouping, such as topic type or document purpose. A semantic component is a characteristic type of information that occurs in a particular document class and represents an important aspect of the document’s main topic. …

Extracting Computable Bounds (And Algorithms) From Classical Existence Proofs: Girard Domains Enable Us To Go Beyond Local Compactness, Vladik Kreinovich, Karen Villaverde

Departmental Technical Reports (CS)

In classical mathematics, the existence of a solution is often proven indirectly, non-constructively, without an efficient method for constructing the corresponding object. In many cases, we can extract an algorithm from a classical proof: e.g., when an object is (non-constructively) proven to be unique in a locally compact space (or when there are two such objects with a known lower bound on the distance between them). In many other practical situations, a (seemingly) natural formalization of the corresponding practical problem leads to a non-compact set. In this paper, we show that often, in such situations, we can extract efficient algorithms …

Identification Of Human Gait In Neuro-Rehabilitation: Towards Efficient Algorithms, Naga Suman Kanagala, Martine Ceberio, Thompson Sarkodie-Gyan, Vladik Kreinovich, Roberto Araiza

Departmental Technical Reports (CS)

Many neurological diseases such as stroke, traumatic body injury, spinal cord injury drastically decrease the patient's ability to walk without physical assistance. To re-establish normal gait, patients undergo extensive rehabilitation. At present, rehabilitation requires gait assessment by highly qualified experienced clinicians. To make rehabilitations easier to access and to decrease the rehabilitation cost, it is desirable to automate gait assessment. In precise terms, gait assessment means comparing the recorded patient's gait with a standard (average) gait of healthy people of the same body measurements. One of the problems in this comparison is that patients walk slower; so, to properly compare …

Integrating Random Testing With Constraints For Improved Efficiency And Diversity, Yoonsik Cheon, Antonio Cortes, Martine Ceberio, Gary T. Leavens

Departmental Technical Reports (CS)

Random testing can be fully automated, eliminates subjectiveness in constructing test cases, and increases the diversity of test data. However, randomly generated tests may not satisfy program's assumptions (e.g., method preconditions). While constraint solving can satisfy such assumptions, it does not necessarily generate diverse tests and is hard to apply to large programs. We blend these techniques by extending random testing with constraint solving, improving the efficiency of generating valid test data while preserving diversity. For domains such as objects, we generate input values randomly; however, for values of finite domains such as integers, we represent test data generation as …

A Library-Based Approach To Translating Ocl Constraints To Jml Assertions For Runtime Checking, Carmen Avila, Guillermo Flores, Jr., Yoonsik Cheon

Departmental Technical Reports (CS)

OCL is a formal notation to specify constraints on UML models that cannot otherwise be expressed by diagrammatic notations such as class diagrams. Using OCL one can document detailed design decisions and choices along with the behavior, e.g., class invariants and method pre and postconditions. However, OCL constraints cannot be directly executed and checked at runtime by an implementation, thus constraint violations may not be detected or noticed, causing many potential development and maintenance problems. In this paper we propose an approach to checking OCL constraints at runtime by translating them to executable JML assertions. The key components of our …

Multimodal News Story Clustering With Pairwise Visual Near-Duplicate Constraint, Xiao Wu, Chong-Wah Ngo, Alexander G. Hauptmann

Research Collection School Of Computing and Information Systems

Story clustering is a critical step for news retrieval, topic mining, and summarization. Nonetheless, the task remains highly challenging owing to the fact that news topics exhibit clusters of varying densities, shapes, and sizes. Traditional algorithms are found to be ineffective in mining these types of clusters. This paper offers a new perspective by exploring the pairwise visual cues deriving from near-duplicate keyframes (NDK) for constraint-based clustering. We propose a constraint-driven co-clustering algorithm (CCC), which utilizes the near-duplicate constraints built on top of text, to mine topic-related stories and the outliers. With CCC, the duality between stories and their underlying …

Mobile User Movement And Service Usage Prediction Using Bayesian Learning For Neural Networks, Sherif Hany Akoush

Archived Theses and Dissertations

No abstract provided.