Computer Sciences Commons^™

A Cross-Layer Protocol For Wireless Sensor Networks, Ian F. Akyildiz, Mehmet C. Vuran, Ӧzgür B. Akan

School of Computing: Conference and Workshop Papers

Severe energy constraints of battery-powered sensor nodes necessitate energy-efficient communication protocols in order to fulfill application objectives of wireless sensor networks (WSN). However, the vast majority of the existing solutions are based on classical layered protocols approach. It is much more resource-efficient to have a unified scheme which melts common protocol layer functionalities into a cross-layer module for resource-constrained sensor nodes. To the best of our knowledge, to date, there is no unified cross-layer communication protocol for efficient and reliable event communication which considers transport, routing, medium access functionalities with physical layer (wireless channel) effects for WSNs.
In this paper, …

Cross-Layer Analysis Of Error Control In Wireless Sensor Networks, Mehmet C. Vuran, Ian F. Akyildiz

School of Computing: Conference and Workshop Papers

Severe energy constraints and hence the low power communication requirements amplify the significance of the energy efficient and preferably cross-layer error control mechanisms in Wireless Sensor Networks (WSN). In this paper, a crosslayer methodology for the analysis of error control schemes in WSNs is presented such that the effects of multi-hop routing and the broadcast nature of the wireless channel are investigated. More specifically, the cross-layer effects of routing, medium access and physical layers are considered. This analysis enables a comprehensive comparison of forward error correction (FEC) and automatic repeat request (ARQ) in WSNs.
FEC schemes improve the error resiliency …

A Constraint-Based Approach To Solving Minesweeper, Ken Bayer, Josh Snyder, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

·Motivate the students for the study of Constraint Processing (CP). Minesweeper is perfect to this end because it allows us to illustrate the use of CP algorithms in a familiar context and show how they operate.

·Understand and demystify humans’ fascination with puzzles.

·Discourage graduate students from losing too much time playing the game by making a program that plays the game for them.

Evaluating The Effectiveness Of Slicing For Model Reduction Of Concurrent Object-Oriented Programs, Matthew B. Dwyer, John Hatcliff, Matthew Hoosier, Venkatesh Ranganath, Robby, Todd Wallentine

School of Computing: Book Chapters

Model checking techniques have proven effective for checking a number of non-trivial concurrent object-oriented software systems. However, due to the high computational and memory costs, a variety of model reduction techniques are needed to overcome current limitations on applicability and scalability. Conventional wisdom holds that static program slicing can be an effective model reduction technique, yet anecdotal evidence is mixed, and there has been no work that has systematically studied the costs/benefits of slicing for model reduction in the context of model checking source code for realistic systems. In this paper, we present an overview of the sophisticated Indus program …

A Maximum-Likelihood Approach To Symbolic Indirect Correlation, Ashutosh Joshi, George Nagy, Daniel Lopresti, Sharad C. Seth

School of Computing: Conference and Workshop Papers

Symbolic Indirect Correlation (SIC) is a nonparametric method that offers significant advantages for recognition of ordered unsegmented signals. A previously introduced formulation of SIC based on subgraph-isomorphism requires very large reference sets in the presence of noise. In this paper, we seek to address this issue by formulating SIC classification as a maximum likelihood problem. We present experimental evidence that demonstrates that this new approach is more robust for the problem of online handwriting recognition using noisy input.

On Reoptimizing Multi-Class Classifiers, Kun Deng, Chris Bourke, Stephen Scott, Robert E. Schapire, N. V. Vinodchandran

School of Computing: Technical Reports

Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously learned classifier to work under new conditions. We study the problem of reoptimizing a multi-class classifier based on its ROC hypersurface and a matrix describing the costs of each type of prediction error. For a binary classifier, it is straightforward to find an optimal operating point based on its ROC curve and the relative cost of true positive to false positive error. However, the corresponding multi-class problem (finding an optimal operating point based on a ROC hypersurface and cost matrix) …

Intelligent Resource Discovery Using Ontology-Based Resource Profiles, J. Steven Hughes, Dan Crichton, Sean Kelly, Chris A. Mattmann, Jerry Crichton, Thuy Tran

Copyright, Fair Use, Scholarly Communication, etc.

Successful resource discovery across heterogeneous repositories is highly dependent on the semantic and syntactic homogeneity of the associated resource descriptions in each repository. Ideally, consistent resource descriptions are easily extracted from each repository, expressed using standard syntactic and semantic structures, and managed and accessed within a distributed, flexible, and scalable software framework. In practice however, seldom do all three of these elements exist. To help address this situation, the Object Oriented Data Technology (OODT) project at the Jet Propulsion Laboratory has developed an extensible, standards-based resource description scheme that provides the necessary description and management facilities for the discovery of …

Survivable Traffic Grooming With Path Protection At The Connection Level In Wdm Mesh Networks, Wang Yao, Byrav Ramamurthy

School of Computing: Faculty Publications

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength-division-multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated-protection and shared-protection schemes are considered. Given network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures, such as fiber cut and duct cut, we consider the general shared-risklink- group (SRLG) diverse routing constraints. We first resort to the integer-linear-programming (ILP) approach to obtain optimal solutions. …

Profiling Deployed Software: Strategic Probe Placement, Madeline Diep, Sebastian Elbaum, Myra B. Cohen

School of Computing: Technical Reports

Profiling deployed software provides valuable insights for quality improvement activities. The probes required for profiling, however, can cause an unacceptable performance overhead for users. In previous work we have shown that significant overhead reduction can be achieved, with limited information loss, through the distribution of probes across deployed instances. However, existing strategies for probe distribution do not account for several relevant factors: acceptable overheads may vary, the distributions to be deployed may be limited, profiled events may have different likelihoods, and the user pool composition may be unknown. This paper evaluates strategies for probe distribution while manipulating these factors through …

Shared Risk Link Group (Srlg)-Diverse Path Provisioning Under Hybrid Service Level Agreements In Wavelength-Routed Optical Mesh Networks, Lu Shen, Xi Yang, Byrav Ramamurthy

School of Computing: Faculty Publications

The static provisioning problem in wavelength-routed optical networks has been studied for many years. However, service providers are still facing the challenges arising from the special requirements for provisioning services at the optical layer. In this paper, we incorporate some realistic constraints into the static provisioning problem, and formulate it under different network resource availability conditions.We consider three classes of shared risk link group (SRLG)-diverse path protection schemes: dedicated, shared, and unprotected. We associate with each connection request a lightpath length constraint and a revenue value. When the network resources are not sufficient to accommodate all the connection requests, the …

A Link Bundled Auxiliary Graph Model For Constrained Dynamic Traffic Grooming In Wdm Mesh Networks, Wang Yao, Byrav Ramamurthy

School of Computing: Faculty Publications

This paper addresses the two-layer dynamic traffic grooming problem in wavelength-division-multiplexed (WDM) mesh optical networks subject to resource constraints and the generalized wavelength continuity (GWC) constraint. The GWC constraint is a relaxed wavelength continuity constraint which incorporates various kinds of wavelength conversion capabilities that exist in optical networks. As an improvement over the existing layered auxiliary graph (layered-AG) approach which represents each wavelength separately in the auxiliary graph, we introduce a largely simplified link bundled auxiliary graph (LBAG) model and propose the SAG-LB method to find paths and assign wavelengths for new lightpaths subject to the GWC constraint.We propose the …

An Efficient Consistency Algorithm For The Temporal Constraint Satisfaction Problem, Berthe Y. Choueiry, Lin Xu

School of Computing: Faculty Publications

Dechter et al. [5] proposed solving the Temporal Constraint Satisfaction Problem (TCSP) by modeling it as a meta-CSP, which is a finite CSP with a unique global constraint. The size of this global constraint is exponential in the number of time points in the original TCSP, and generalized-arc consistency is equivalent to finding the minimal network of the TCSP, which is NP-hard. We introduce _AC, an efficient consistency algorithm for filtering the meta-CSP. This algorithm significantly reduces the domains of the variables of the meta-CSP without guaranteeing arc-consistency. We use _AC as a preprocessing step to solving the meta-CSP. We …

Geospatial Decision Support For Drought Risk Management, Steve Goddard, Sherri K. Harms, Stephen E. Reichenbach, Tsegaye Tadesse, William J. Waltman

School of Computing: Faculty Publications

Drought affects virtually all regions of the world and results in significant economic, social, and environmental impacts. The Federal Emergency Management Agency estimates annual drought-related losses in the U.S. at $6–$8 billion, which is more than any other natural hazard. Congress enacted the Agricultural Risk Protection Act of 2000 to encourage the U.S. Department of Agriculture (USDA) Risk Management Agency (RMA) and farmers to be more proactive in managing drought risk. Through the NSF’s Digital Government Program, the USDA RMA is working with the University of Nebraska–Lincoln Computer Science and Engineering Department, National Drought Mitigation Center (NDMC), and High Plains …

Experimental Program Analysis: A New Program Analysis Paradigm, Joseph R. Ruthruff, Sebastian Elbaum, Gregg Rothermel

School of Computing: Technical Reports

Program analysis techniques analyze software systems to collect, deduce, or infer information about them, which can then be used in software-engineering related tasks. Recent research has suggested that a new form of program analysis technique might be created by incorporating characteristics of experimentation into analyses. This paper reports the results of research exploring this suggestion. Building on background in classical experimentation, we provide descriptive and operational definitions of experimental program analysis, illustrate them by examples, and describe several differences between experimental program analysis and classical experimentation. We present three studies that show how the use of the paradigm can help …

Guest Editor’S Introduction: Ieee 2004 International Symposium On Software Testing And Analysis, Gregg Rothermel

School of Computing: Faculty Publications

The International Symposium on Software Testing and Analysis (ISSTA) is the leading research conference in software testing and analysis. ISSTA brings together academics, industrial researchers, and practitioners to present and discuss the most promising approaches for using testing and analysis to assess and improve software and the processes by which it is engineered.
ISSTA 2004 was held in at the Parker House Hotel in Boston, Massachusetts, July 11-14, 2004. On this occasion the conference was co-located with the 16th Computer- Aided Verification Conference (CAV 2004), with the two conferences sharing a day of sessions. The conference was also preceded by …

Survivable Lightpath Provisioning In Wdm Mesh Networks Under Shared Path Protection And Signal Quality Constraints, Xi Yang, Lu Shen, Byrav Ramamurthy

School of Computing: Faculty Publications

This paper addresses the problem of survivable lightpath provisioning in wavelength-division-multiplexing (WDM) mesh networks, taking into consideration optical-layer protection and some realistic optical signal quality constraints. The investigated networks use sparsely placed optical–electrical–optical (O/E/O) modules for regeneration and wavelength conversion. Given a fixed network topology with a number of sparsely placed O/E/O modules and a set of connection requests, a pair of link-disjoint lightpaths is established for each connection. Due to physical impairments and wavelength continuity, both the working and protection lightpaths need to be regenerated at some intermediate nodes to overcome signal quality degradation and wavelength contention. In the …

Leveraging User-Session Data To Support Web Application Testing, Sebastian Elbaum, Gregg Rothermel, Srikanth Karre, Marc Fisher Ii

School of Computing: Faculty Publications

Web applications are vital components of the global information infrastructure, and it is important to ensure their dependability. Many techniques and tools for validating Web applications have been created, but few of these have addressed the need to test Web application functionality and none have attempted to leverage data gathered in the operation of Web applications to assist with testing. In this paper, we present several techniques for using user session data gathered as users operate Web applications to help test those applications from a functional standpoint. We report results of an experiment comparing these new techniques to existing white-box …

Dynamic Routing In Translucent Wdm Optical Networks: The Intradomain Case, Xi Yang, Byrav Ramamurthy

School of Computing: Faculty Publications

Translucent wavelength-division multiplexing optical networks use sparse placement of regenerators to overcome physical impairments and wavelength contention introduced by fully transparent networks, and achieve a performance close to fully opaque networks at a much less cost. In previous studies, we addressed the placement of regenerators based on static schemes, allowing for only a limited number of regenerators at fixed locations. This paper furthers those studies by proposing a dynamic resource allocation and dynamic routing scheme to operate translucent networks. This scheme is realized through dynamically sharing regeneration resources, including transmitters, receivers, and electronic interfaces, between regeneration and access functions under …

Web Application Characterization Through Directed Requests, Sebastian Elbaum, Kalyanram Chilakamarri, Marc Randall Fisher Ii, Gregg Rothermel

School of Computing: Technical Reports

Web applications are increasingly prominent in society, serving a wide variety of user needs. Engineers seeking to enhance, test, and maintain these applications must be able to understand and characterize their interfaces. Third-party programmers (professional or end user) wishing to incorporate the data provided by such services into their own applications would also benefit from such characterization when the target site does not provide adequate programmatic interfaces. In this paper, therefore, we present methodologies for characterizing the interfaces to web applications through a form of dynamic analysis, in which directed requests are sent to the application, and responses are analyzed …

Disseminating Usability Design Knowledge Through Ontology-Based Pattern Languages, Scott Henninger, Padmapriya Ashokkumar

School of Computing: Technical Reports

Usability patterns represent knowledge about known ways to design graphical user interfaces that are usable and meet the needs and expectations of users. There is currently a plethora of usability patterns published in books, private repositories and the World-Wide Web. The dominance of pattern discovery efforts has neglected the emerging need to organize the patterns so they can become a proactive resource for developing interfaces. This paper presents an approach using Semantic Web concepts that turns informal patterns into formal representations capable of supporting systematic design methods. Through this method, loosely coupled pattern collections can be turned into strongly coupled …

Dcdp: A Novel Data-Centric And Design-Pattern Based Approach To Automatic Loop Transformation And Parallelization For A Shared-Object Environment In Clusters, Xuli Liu, Hong Jiang, Leen-Kiat Soh

School of Computing: Technical Reports

Most of the parallelism associated with scientific/numeric applications exists in the form of loops, and thus transforming loops has been extensively studied in the past, especially in the areas of programming languages and compiler designs. Almost all the existing transformation approaches are control-centric, in which the transformation process starts from partitioning the iteration space, followed by the decomposition of the data space only as a side-effect. Originally designed for shared-memory multi-processors, these control-centric approaches might not be suitable under some circumstances for current loosely-coupled clusters and the Grid with physically distributed memories. In this paper, we introduce a novel data-centric …

Survivable Waveband Switching In Wdm Mesh Networks Under Dedicated Path-Protection, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

This paper considers the problem of dedicated path-protection in wavelength-division multiplexed (WDM) mesh networks with waveband switching functionality under shared risk link group (SRLG) constraints. Two dedicated path protection schemes are proposed, namely the PBABL scheme and the MPABWL scheme. The PBABL scheme protects each working waveband-path through a backup waveband-path. The MPABWL scheme protects each working waveband-path by either a backup waveband-path or multiple backup lightpaths. Heuristic algorithms adopting random optimization technique are proposed for both the schemes. The performance of the two protection schemes is studied and compared. Simulation results show that both the heuristics can obtain optimum …

Profiling Deployed Software: Strategic Probe Placement, Madeline Diep, Sebastian Elbaum, Myra B. Cohen

School of Computing: Technical Reports

Profiling deployed software provides valuable insights for quality improvement activities. The probes required for profiling, however, can cause an unacceptable performance overhead for users. In previous work we have shown that significant overhead reduction can be achieved, with limited information loss, through the distribution of probes across deployed instances. However, existing strategies for probe distribution do not account for several relevant factors: acceptable overheads may vary, the distributions to be deployed may be limited, profiled events may have different likelihoods, and the user pool composition may be unknown. This paper evaluates strategies for probe distribution while manipulating these factors through …

A Controlled Experiment Assessing Test Case Prioritization Techniques Via Mutation Faults, Hyunsook Do, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Regression testing is an important part of software maintenance, but it can also be very expensive. To reduce this expense, software testers may prioritize their test cases so that those that are more important are run earlier in the regression testing process. Previous work has shown that prioritization can improve a test suite’s rate of fault detection, but the assessment of prioritization techniques has been limited to hand-seeded faults, primarily due to the belief that such faults are more realistic than automatically generated (mutation) faults. A recent empirical study, however, suggests that mutation faults can be representative of real faults. …

Efficient Test Compaction For Pseudo-Random Testing, Sheng Zhang, Sharad C. Seth, Bhargab B. Bhattacharya

School of Computing: Conference and Workshop Papers

Compact set of 3-valued test vectors for random pattern resistant faults are covered in multiple test passes. During a pass, its associated test cube specifies certain bits in the scan chain to be held fixed and others to change pseudo-randomly. We propose an algorithm to find a small number of cubes to cover all the test vectors, thus minimizing total test length. The test-cube finding algorithm repeatedly evaluates small perturbations of the current solution so as to maximize the expected test coverage of the cube. Experimental results show that our algorithm covers the test vectors by test cubes that are …

Face Recognition Using Landmark-Based Bidimensional Regression, Jiazheng Shi, Ashok Samal, David Marx

School of Computing: Conference and Workshop Papers

This paper studies how biologically meaningful landmarks extracted from face images can be exploited for face recognition using the bidimensional regression. Incorporating the correlation statistics of landmarks, this paper also proposes a new approach called eigenvalue weighted bidimensional regression. Complex principal component analysis is used for computing eigenvalues and removing correlation among landmarks. We evaluate our approach using two standard face databases: the Purdue AR and the NIST FERET. Experimental results show that the bidimensional regression is an efficient method to exploit geometry information of face images.

Ground Water Monitoring Using Smart Sensors, Srikanth Anumalla, Byrav Ramamurthy, David Gosselin

School of Computing: Conference and Workshop Papers

Groundwater resources are the principal source of drinking water for about 50 percent of the United States population. Groundwater resources in Nebraska are under increasing stress as there is a rapid growth in their usage. Water managers need more timely and accurate data to assess ground-water conditions to manage adverse situations such as drought and loss of pumpage in agriculture and domestic water supply. Currently groundwater researchers use stand-alone data logging equipment which is labor intensive and the method is not easily scalable if the number of logging locations increases. Commercially available real-time data monitoring solutions are either prohibitively costly …

A Heuristic With Bounded Guarantee To Compute Diverse Paths Under Shared Protection In Wdm Mesh Networks, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Establishing a fault-tolerant connection in a network involves computation of diverse working and protection paths. The Shared Risk Link Group (SRLG) [1] concept is used to model several types of failure conditions such as link, node, fiber conduit, etc. In this work we focus on the problem of computing optimal SRLG/link diverse paths under shared protection. Shared protection technique improves network resource utilization by allowing protection paths of multiple connections to share resources. In this work we propose an iterative heuristic for computing SRLG/link diverse paths. We present a method to calculate a quantitative measure that provides a bounded guarantee …

Least-Cost Disjoint Paths With Dependent Cost Structure In Wavelength Continuous Optical Wdm Networks, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

One of the important issues in establishing a fault tolerant connection in a wavelength division multiplexing optical network is computing a pair of disjoint working and protection paths and a free wavelength along the paths. While most of the earlier research focused only on computing disjoint paths, in this work we consider computing both disjoint paths and a free wavelength along the paths.

The concept of dependent cost structure (DCS) of protection paths to enhance their resource sharing ability was proposed in our earlier work. In this work we extend the concept of DCS of protection paths to wavelength continuous …

Helping End-Users “Engineer” Dependable Web Applications, Sebastian Elbaum, Kalyan-Ram Chilakamarri, Bhuvana Gopal, Gregg Rothermel

School of Computing: Conference and Workshop Papers

End-user programmers are increasingly relying on web authoring environments to create web applications. Although often consisting primarily of web pages, such applications are increasingly going further, harnessing the content available on the web through “programs” that query other web applications for information to drive other tasks. Unfortunately, errors can be pervasive in web applications, impacting their dependability. This paper reports the results of an exploratory study of end-user web application developers, performed with the aim of exposing prevalent classes of errors. The results suggest that end-users struggle the most with the identification and manipulation of variables when structuring requests to …