OpenRaiser/Intern-Atlas huggingface dataset:
Topology and Non-Deterministic Polynomial Time Computation : Avoidance of The Misbehaviour of Hub-Free Diagrams and Consequences
Venue: arXiv cs.CC 2013
Year: 2013

To study groups with small Dehn's function, Olshanskii and Sapir developed a new invariant of bipartite chords diagrams and applied it to hub-free realization of S-machines. In this paper we consider this new invariant together with groups constructed from S-machines containing the hub relation. The idea is to study the links between the topology of the asymptotic cones and polynomial time computations. Indeed it is known that the topology of such metric space depends on diagrams without hubs that do not correspond to the computations of the considered S-machine. This work gives sufficient conditions that avoid this misbehaviour, but as we shall see the method has a significant drawback.
Electrical Structure-Based PMU Placement in Electric Power Systems
Venue: arXiv cs.SY 2013
Year: 2013

Recent work on complex networks compared the topological and electrical structures of the power grid, taking into account the underlying physical laws that govern the electrical connectivity between various components in the network. A distance metric, namely, resistance distance was introduced to provide a more comprehensive description of interconnections in power systems compared with the topological structure, which is based only on geographic connections between network components. Motivated by these studies, in this paper we revisit the phasor measurement unit (PMU) placement problem by deriving the connectivity matrix of the network using resistance distances between buses in the grid, and use it in the integer program formulations for several standard IEEE bus systems. The main result of this paper is rather discouraging: more number of PMUs are required, compared with those obtained using the topological structure, to meet the desired objective of complete network observability without zero injection measurements. However, in light of recent advances in the electrical structure of the grid, our study provides a more realistic perspective of PMU placement in power systems. By further exploring the connectivity matrix derived using the electrical structure, we devise a procedure to solve the placement problem without resorting to linear programming.
Characterization of the Least Periods of the Generalized Self-Shrinking Sequences
Venue: arXiv cs.IT 2013
Year: 2013

In 2004, Y. Hu and G. Xiao introduced the generalized self-shrinking generator, a simple bit-stream generator considered as a specialization of the shrinking generator as well as a generalization of the self-shrinking generator. The authors conjectured that the family of generalized self-shrinking sequences took their least periods in the set {1, 2, 2**(L-1)}, where L is the length of the Linear Feedback Shift Register included in the generator. In this correspondence, it is proved that the least periods of such generated sequences take values exclusively in such a set. As a straight consequence of this result, other characteristics of such sequences (linear complexity or pseudorandomness) and their potential use in cryptography are also analyzed.
The Stability Region of the Two-User Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

The stable throughput region of the two-user interference channel is investigated here. First, the stability region for the general case is characterized. Second, we study the cases where the receivers treat interference as noise or perform successive interference cancelation. Finally, we provide conditions for the convexity/concavity of the stability region and for which a certain interference management strategy leads to broader stability region.
Ergodic Randomized Algorithms and Dynamics over Networks
Venue: arXiv cs.SY 2013
Year: 2013

Algorithms and dynamics over networks often involve randomization, and randomization may result in oscillating dynamics which fail to converge in a deterministic sense. In this paper, we observe this undesired feature in three applications, in which the dynamics is the randomized asynchronous counterpart of a well-behaved synchronous one. These three applications are network localization, PageRank computation, and opinion dynamics. Motivated by their formal similarity, we show the following general fact, under the assumptions of independence across time and linearities of the updates: if the expected dynamics is stable and converges to the same limit of the original synchronous dynamics, then the oscillations are ergodic and the desired limit can be locally recovered via time-averaging.
Mixed Polling with Rerouting and Applications
Venue: arXiv cs.PF 2013
Year: 2013

Queueing systems with a single server in which customers wait to be served at a finite number of distinct locations (buffers/queues) are called discrete polling systems. Polling systems in which arrivals of users occur anywhere in a continuum are called continuous polling systems. Often one encounters a combination of the two systems: the users can either arrive in a continuum or wait in a finite set (i.e. wait at a finite number of queues). We call these systems mixed polling systems. Also, in some applications, customers are rerouted to a new location (for another service) after their service is completed. In this work, we study mixed polling systems with rerouting. We obtain their steady state performance by discretization using the known pseudo conservation laws of discrete polling systems. Their stationary expected workload is obtained as a limit of the stationary expected workload of a discrete system. The main tools for our analysis are: a) the fixed point analysis of infinite dimensional operators and; b) the convergence of Riemann sums to an integral. We analyze two applications using our results on mixed polling systems and discuss the optimal system design. We consider a local area network, in which a moving ferry facilitates communication (data transfer) using a wireless link. We also consider a distributed waste collection system and derive the optimal collection point. In both examples, the service requests can arrive anywhere in a subset of the two dimensional plane. Namely, some users arrive in a continuous set while others wait for their service in a finite set. The only polling systems that can model these applications are mixed systems with rerouting as introduced in this manuscript.
Experiments in Sustainable Software Practices for Future Architectures
Venue: arXiv cs.SE 2013
Year: 2013

In the process of rewriting large physics codes at Los Alamos National Laboratory to perform well on new architectures such as many-core, GPU, and Intel MIC, we have found a number of areas in which sustainable software practices can provide significant advantages. We describe several specific advantages of sustainable practices for future architectures, and report on two small experimental projects at LANL intended to raise awareness of new software practices and programming approaches for new architectures.
Formally expressing the semantics of observer-based fault detection software
Venue: arXiv cs.SE 2013
Year: 2013

The aim is to create reliable and verifiable fault detection software to detect abrupt changes in safety-critical dynamic systems. Fault detection methods are implemented as software on digital computers that monitor and control the system. We implement three observer-based fault detection methods on a 3 degrees of freedom (3DOF) laboratory helicopter, in the form of software. We examine the performance of those methods to detect different faults during flight in a closed-loop setup. All selected methods show acceptable detection performance. However, it is not possible to repeat the test for every possible conditions, inputs and fault scenarios. In this paper, we translate fault detection properties and mathematical proofs into a formal language, previously used in software validation and verification. We include the translated properties in software in the form of non-executable annotations that can be read by machine. Consequently, some high level functional properties of the code can be verified by automatic software verification tools. This certifies fault detection software for a set of bounded data and increases the reliability in practice.
Semantic-driven Configuration of Internet of Things Middleware
Venue: arXiv cs.NI 2013
Year: 2013

We are currently observing emerging solutions to enable the Internet of Things (IoT). Efficient and feature rich IoT middeware platforms are key enablers for IoT. However, due to complexity, most of these middleware platforms are designed to be used by IT experts. In this paper, we propose a semantics-driven model that allows non-IT experts (e.g. plant scientist, city planner) to configure IoT middleware components easier and faster. Such tools allow them to retrieve the data they want without knowing the underlying technical details of the sensors and the data processing components. We propose a Context Aware Sensor Configuration Model (CASCoM) to address the challenge of automated context-aware configuration of filtering, fusion, and reasoning mechanisms in IoT middleware according to the problems at hand. We incorporate semantic technologies in solving the above challenges. We demonstrate the feasibility and the scalability of our approach through a prototype implementation based on an IoT middleware called Global Sensor Networks (GSN), though our model can be generalized into any other middleware platform. We evaluate CASCoM in agriculture domain and measure both performance in terms of usability and computational complexity.
Guided Self-Organization of Input-Driven Recurrent Neural Networks
Venue: arXiv cs.NE 2013
Year: 2013

We review attempts that have been made towards understanding the computational properties and mechanisms of input-driven dynamical systems like RNNs, and reservoir computing networks in particular. We provide details on methods that have been developed to give quantitative answers to the questions above. Following this, we show how self-organization may be used to improve reservoirs for better performance, in some cases guided by the measures presented before. We also present a possible way to quantify task performance using an information-theoretic approach, and finally discuss promising future directions aimed at a better understanding of how these systems perform their computations and how to best guide self-organized processes for their optimization.
A Comparism of the Performance of Supervised and Unsupervised Machine Learning Techniques in evolving Awale/Mancala/Ayo Game Player
Venue: arXiv cs.LG 2013
Year: 2013

Awale games have become widely recognized across the world, for their innovative strategies and techniques which were used in evolving the agents (player) and have produced interesting results under various conditions. This paper will compare the results of the two major machine learning techniques by reviewing their performance when using minimax, endgame database, a combination of both techniques or other techniques, and will determine which are the best techniques.
Combinatorial optimization with 2-joins
Venue: arXiv cs.DM 2013
Year: 2013

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset. We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.
Convergence of Nearest Neighbor Pattern Classification with Selective Sampling
Venue: arXiv cs.LG 2013
Year: 2013

In the panoply of pattern classification techniques, few enjoy the intuitive appeal and simplicity of the nearest neighbor rule: given a set of samples in some metric domain space whose value under some function is known, we estimate the function anywhere in the domain by giving the value of the nearest sample per the metric. More generally, one may use the modal value of the m nearest samples, where m is a fixed positive integer (although m=1 is known to be admissible in the sense that no larger value is asymptotically superior in terms of prediction error). The nearest neighbor rule is nonparametric and extremely general, requiring in principle only that the domain be a metric space. The classic paper on the technique, proving convergence under independent, identically-distributed (iid) sampling, is due to Cover and Hart (1967). Because taking samples is costly, there has been much research in recent years on selective sampling, in which each sample is selected from a pool of candidates ranked by a heuristic; the heuristic tries to guess which candidate would be the most "informative" sample. Lindenbaum et al. (2004) apply selective sampling to the nearest neighbor rule, but their approach sacrifices the austere generality of Cover and Hart; furthermore, their heuristic algorithm is complex and computationally expensive. Here we report recent results that enable selective sampling in the original Cover-Hart setting. Our results pose three selection heuristics and prove that their nearest neighbor rule predictions converge to the true pattern. Two of the algorithms are computationally cheap, with complexity growing linearly in the number of samples. We believe that these results constitute an important advance in the art.
nanoHUB.org: Experiences and Challenges in Software Sustainability for a Large Scientific Community
Venue: arXiv cs.SE 2013
Year: 2013

Managing and growing a successful cyberinfrastructure such as nanoHUB.org presents a variety of opportunities and challenges, particularly in regard to software. This position paper details a number of those issues and how we have approached them.
Context Aware Sensor Configuration Model for Internet of Things
Venue: arXiv cs.NI 2013
Year: 2013

We propose a Context Aware Sensor Configuration Model (CASCoM) to address the challenge of automated context-aware configuration of filtering, fusion, and reasoning mechanisms in IoT middleware according to the problems at hand. We incorporate semantic technologies in solving the above challenges.
Cactus: Issues for Sustainable Simulation Software
Venue: arXiv cs.CE 2013
Year: 2013

The Cactus Framework is an open-source, modular, portable programming environment for the collaborative development and deployment of scientific applications using high-performance computing. Its roots reach back to 1996 at the National Center for Supercomputer Applications and the Albert Einstein Institute in Germany, where its development jumpstarted. Since then, the Cactus framework has witnessed major changes in hardware infrastructure as well as its own community. This paper describes its endurance through these past changes and, drawing upon lessons from its past, also discusses future
Reusability in Science: From Initial User Engagement to Dissemination of Results
Venue: arXiv cs.SE 2013
Year: 2013

Effective use of parallel and distributed computing in science depends upon multiple interdependent entities and activities that form an ecosystem. Active engagement between application users and technology catalysts is a crucial activity that forms an integral part of this ecosystem. Technology catalysts play a crucial role benefiting communities beyond a single user group. An effective user-engagement, use and reuse of tools and techniques has a broad impact on software sustainability. From our experience, we sketch a life-cycle for user-engagement activity in scientific computational environment and posit that application level reusability promotes software sustainability. We describe our experience in engaging two user groups from different scientific domains reusing a common software and configuration on different computational infrastructures.
Design and Implementation of Wireless Energy Meter System for Monitoring the Single Phase Supply
Venue: arXiv cs.OH 2013
Year: 2013

Wireless energy meter is a system developed to serve as a basic single-phase energy meter with advanced functionalities such as Peak hour setting, Peak load setting Wireless reading transmission; further the system eliminates the role of a Meter Reader.
Cooperative Wireless Sensor Network Positioning via Implicit Convex Feasibility
Venue: arXiv cs.IT 2013
Year: 2013

We propose a distributed positioning algorithm to estimate the unknown positions of a number of target nodes, given distance measurements between target nodes and between target nodes and a number of reference nodes at known positions. Based on a geometric interpretation, we formulate the positioning problem as an implicit convex feasibility problem in which some of the sets depend on the unknown target positions, and apply a parallel projection onto convex sets approach to estimate the unknown target node positions. The proposed technique is suitable for parallel implementation in which every target node in parallel can update its position and share the estimate of its location with other targets. We mathematically prove convergence of the proposed algorithm. Simulation results reveal enhanced performance for the proposed approach compared to available techniques based on projections, especially for sparse networks.
An optimal fuzzy-PI force/motion controller to increase industrial robot autonomy
Venue: arXiv cs.RO 2013
Year: 2013

This paper presents a method for robot self-recognition and self-adaptation through the analysis of the contact between the robot end effector and its surrounding environment. Often, in off-line robot programming, the idealized robotic environment (the virtual one) does not reflect accurately the real one. In this situation, we are in the presence of a partially unknown environment (PUE). Thus, robotic systems must have some degree of autonomy to overcome this situation, especially when contact exists. The proposed force/motion control system has an external control loop based on forces and torques exerted on the robot end effector and an internal control loop based on robot motion. The external control loop is tested with an optimal proportional integrative (PI) and a fuzzy-PI controller. The system performance is validated with real-world experiments involving contact in PUEs.
Discretization and fitting of nominal data for autonomous robots
Venue: arXiv cs.RO 2013
Year: 2013

This paper presents methodologies to discretize nominal robot paths extracted from 3-D CAD drawings. Behind robot path discretization is the ability to have a robot adjusting the traversed paths so that the contact between robot tool and work-piece is properly maintained. In addition, a hybrid force/motion control system based on Fuzzy-PI control is proposed to adjust robot paths with external sensory feedback. All these capabilities allow to facilitate the robot programming process and to increase the robots autonomy.
Accelerometer-based control of an industrial robotic arm
Venue: arXiv cs.RO 2013
Year: 2013

Most of industrial robots are still programmed using the typical teaching process, through the use of the robot teach pendant. In this paper is proposed an accelerometer-based system to control an industrial robot using two low-cost and small 3-axis wireless accelerometers. These accelerometers are attached to the human arms, capturing its behavior (gestures and postures). An Artificial Neural Network (ANN) trained with a back-propagation algorithm was used to recognize arm gestures and postures, which then will be used as input in the control of the robot. The aim is that the robot starts the movement almost at the same time as the user starts to perform a gesture or posture (low response time). The results show that the system allows the control of an industrial robot in an intuitive way. However, the achieved recognition rate of gestures and postures (92%) should be improved in future, keeping the compromise with the system response time (160 milliseconds). Finally, the results of some tests performed with an industrial robot are presented and discussed.
A Fair Scheduling Model for Centralized Cognitive Radio Networks
Venue: arXiv cs.NI 2013
Year: 2013

We formulate throughput maximizing, max-min fair, weighted max-min fair, and proportionally fair scheduling problems for cognitive radio networks managed by a centralized cognitive base station. We propose a very general scheduling model accomplishing goals such as making frequency, time slot, and data rate allocation to secondary users with possibly multiple antennas, in a heterogenous multi-channel and multi-user scenario. Moreover, our schedulers ensure that reliable communication between the cognitive base station and secondary users are maintained, no collisions occur among secondary users, and primary users in the service area of the cognitive base station are not disturbed. Two distinctive features of our fair schedulers are that they provide joint temporal and throughput fairness, and take throughput values experienced by secondary users in the recent past, referred to as window size, into account and use this information in the current scheduling decision. We also propose a heuristic algorithm for our fair schedulers and demonstrate through simulations that our proposed heuristic yields very close solutions to the values obtained from the optimization softwares. Furthermore, we make extensive simulations to evaluate our schedulers' performance in terms of both total throughput and fairness for varying number of secondary users, frequencies, antennas, and window size.
An Efficient Key Agreement Scheme for Wireless Sensor Networks Using Third Parties
Venue: arXiv cs.CR 2013
Year: 2013

This paper contributes to the challenging field of security for wireless sensor networks by introducing a key agreement scheme in which sensor nodes create secure radio connections with their neighbours depending on the aid of third parties. These third parties are responsible only for the pair-wise key establishment among sensor nodes, so they do not observe the physical phenomenon nor route data packets to other nodes. The proposed method is explained here with respect to four important issues: how secret shares are distributed, how local neighbours are discovered, how legitimate third parties are verified, and how secure channels are established. Moreover, the performance of the scheme is analyzed with regards to five metrics: local connectivity, resistance to node capture, memory usage, communication overhead, and computational burden. Our scheme not only secures the transmission channels of nodes but also guarantees high local connectivity of the sensor network, low usage of memory resources, perfect network resilience against node capture, and complete prevention against impersonation attacks. As it is demonstrated in this paper, using a number of third parties equals to 10% of the total number of sensor nodes in the area of interest, the proposed method can achieve at least 99.42% local connectivity with a very low usage of available storage resources (less than 385 bits on each sensor node).