OpenRaiser/Intern-Atlas huggingface dataset:
Neighbor Discovery in a Wireless Sensor Network: Multipacket Reception Capability and Physical-Layer Signal Processing
Venue: arXiv cs.NI 2011
Year: 2011

In randomly deployed networks, such as sensor networks, an important problem for each node is to discover its \textit{neighbor} nodes so that the connectivity amongst nodes can be established. In this paper, we consider this problem by incorporating the physical layer parameters in contrast to the most of the previous work which assumed a collision channel. Specifically, the pilot signals that nodes transmit are successfully decoded if the strength of the received signal relative to the interference is sufficiently high. Thus, each node must extract signal parameter information from the superposition of an unknown number of received signals. This problem falls naturally in the purview of random set theory (RST) which generalizes standard probability theory by assigning \textit{sets}, rather than values, to random outcomes. The contributions in the paper are twofold: first, we introduce the realistic effect of physical layer considerations in the evaluation of the performance of \textit{logical} discovery algorithms; such an introduction is necessary for the accurate assessment of how an algorithm performs. Secondly, given the \textit{double} uncertainty of the environment (that is, the lack of knowledge of the number of neighbors along with the lack of knowledge of the individual signal parameters), we adopt the viewpoint of RST and demonstrate its advantage relative to classical matched filter detection method.
Multi-Connected Ontologies
Venue: arXiv cs.DL 2011
Year: 2011

Ontologies have been used for the purpose of bringing system and consistency to subject and knowledge areas. We present a criticism of the present mathematical structure of ontologies and indicate that they are not sufficient in their present form to represent the many different valid expressions of a subject knowledge domain. We propose an alternative structure for ontologies based on a richer multi connected complex network which contains the present ontology structure as a projection. We demonstrate how this new multi connected ontology should be represented as an asymmetric probability matrix.
Solving XCSP problems by using Gecode
Venue: arXiv cs.PL 2011
Year: 2011

Gecode is one of the most efficient libraries that can be used for constraint solving. However, using it requires dealing with C++ programming details. On the other hand several formats for representing constraint networks have been proposed. Among them, XCSP has been proposed as a format based on XML which allows us to represent constraints defined either extensionally or intensionally, permits global constraints and has been the standard format of the international competition of constraint satisfaction problems solvers. In this paper we present a plug-in for solving problems specified in XCSP by exploiting the Gecode solver. This is done by dynamically translating constraints into Gecode library calls, thus avoiding the need to interact with C++.
A general framework for online audio source separation
Venue: arXiv cs.SD 2011
Year: 2011

We consider the problem of online audio source separation. Existing algorithms adopt either a sliding block approach or a stochastic gradient approach, which is faster but less accurate. Also, they rely either on spatial cues or on spectral cues and cannot separate certain mixtures. In this paper, we design a general online audio source separation framework that combines both approaches and both types of cues. The model parameters are estimated in the Maximum Likelihood (ML) sense using a Generalised Expectation Maximisation (GEM) algorithm with multiplicative updates. The separation performance is evaluated as a function of the block size and the step size and compared to that of an offline algorithm.
Scheduling Light-trails in WDM Rings
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of scheduling communication on optical WDM (wavelength division multiplexing) networks using the light-trails technology. We seek to design scheduling algorithms such that the given transmission requests can be scheduled using minimum number of wavelengths (optical channels). We provide algorithms and close lower bounds for two versions of the problem on an $n$ processor linear array/ring network. In the {\em stationary} version, the pattern of transmissions (given) is assumed to not change over time. For this, a simple lower bound is $c$, the congestion or the maximum total traffic required to pass through any link. We give an algorithm that schedules the transmissions using $O(c+\log{n})$ wavelengths. We also show a pattern for which $Ω(c+\log{n}/\log\log{n})$ wavelengths are needed. In the {\em on-line} version, the transmissions arrive and depart dynamically, and must be scheduled without upsetting the previously scheduled transmissions. For this case we give an on-line algorithm which has competitive ratio $Θ(\log{n})$. We show that this is optimal in the sense that every on-line algorithm must have competitive ratio $Ω(\log{n})$. We also give an algorithm that appears to do well in simulation (for the classes of traffic we consider), but which has competitive ratio between $Ω(\log^2n/\log \log{n})$ and $O(\log^2n)$. We present detailed simulations of both our algorithms.
Rate Region of the Vector Gaussian One-Helper Source-Coding Problem
Venue: arXiv cs.IT 2011
Year: 2011

We determine the rate region of the vector Gaussian one-helper source-coding problem under a covariance matrix distortion constraint. The rate region is achieved by a simple scheme that separates the lossy vector quantization from the lossless spatial compression. The converse is established by extending and combining three analysis techniques that have been employed in the past to obtain partial results for the problem.
Topologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies
Venue: arXiv cs.SI 2011
Year: 2011

We analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. We call these payoffs as localized payoffs. In this game, the payoff of each individual captures (1) the gain from immediate neighbors, (2) the bridging benefits, and (3) the cost to form links. This implies that the payoff of each individual can be computed using only its single-hop neighbourhood information. Based on this simple model of network formation, our study explores the structure of networks that form, satisfying one or both of the properties, namely, pairwise stability and efficiency. We analytically prove the pairwise stability of several interesting network structures, notably, the complete bi-partite network, complete equi-k-partite network, complete network and cycle network, under various configurations of the model. We validate and extend these results through extensive simulations. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bi-partite network) is the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability, which is the ratio of the sum of payoffs of the players in an optimal pairwise stable network to that of an efficient network. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations of the parameters, we obtain a lower bound of 0.5 on the price of stability. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs.
Resource Allocation with Subcarrier Pairing in OFDMA Two-Way Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

This study considers an orthogonal frequency-division multiple-access (OFDMA)-based multi-user two-way relay network where multiple mobile stations (MSs) communicate with a common base station (BS) via multiple relay stations (RSs). We study the joint optimization problem of subcarrier-pairing based relay-power allocation, relay selection, and subcarrier assignment. The problem is formulated as a mixed integer programming problem. By using the dual method, we propose an efficient algorithm to solve the problem in an asymptotically optimal manner. Simulation results show that the proposed method can improve system performance significantly over the conventional methods.
A Localization Method for the Internet of Things
Venue: arXiv cs.NI 2011
Year: 2011

Many localization algorithms and systems have been developed by means of wireless sensor networks for both indoor and outdoor environments. To achieve higher localization accuracy, extra hardware equipments are utilized by most of the existing localization solutions, which increase the cost and considerably limit the location-based applications. The Internet of Things (IOT) integrates many technologies, such as Internet, Zigbee, Bluetooth, infrared, WiFi, GPRS, 3G, etc, which can enable different ways to obtain the location information of various objects. Location-based service is a primary service of the IOT, while localization accuracy is a key issue. In this paper, a higher accuracy localization scheme is proposed which can effectively satisfy diverse requirements for many indoor and outdoor location services. The proposed scheme composes of two phases: 1) partition phase, in which the target region is split into small grids; 2) localization refinement phase, in which a higher accuracy of localization can be obtained by applying an algorithm designed in the paper. A trial system is set up to verify correctness of the proposed scheme and furthermore to illustrate its feasibility and availability. The experimental results show that the proposed scheme can improve the localization accuracy.
A Secured Health Care Application Architecture for Cyber-Physical Systems
Venue: arXiv cs.NI 2011
Year: 2011

Cyber-physical systems (CPS) can be viewed as a new generation of systems with integrated control, communication and computational capabilities. Like the internet transformed how humans interact with one another, cyber-physical systems will transform how people interact with the physical world. Currently, the study of CPS is still in its infancy and there exist many research issues and challenges ranging from electricity power, health care, transportation and smart building etc. In this paper, an introduction of CPeSC3 (cyber physical enhanced secured wireless sensor networks (WSNs) integrated cloud computing for u-life care) architecture and its application to the health care monitoring and decision support systems is given. The proposed CPeSC3 architecture is composed of three main components, namely 1) communication core, 2) computation core, and 3) resource scheduling and management core. Detailed analysis and explanation are given for relevant models such as cloud computing, real time scheduling and security models. Finally, a medical health care application scenario is presented based on our practical test-bed which has been built for 3 years.
Building Smart Communities with Cyber-Physical Systems
Venue: arXiv cs.SI 2011
Year: 2011

There is a growing trend towards the convergence of cyber-physical systems (CPS) and social computing, which will lead to the emergence of smart communities composed of various objects (including both human individuals and physical things) that interact and cooperate with each other. These smart communities promise to enable a number of innovative applications and services that will improve the quality of life. This position paper addresses some opportunities and challenges of building smart communities characterized by cyber-physical and social intelligence.
A Statistical Approach Towards Robust Progress Estimation
Venue: arXiv cs.DB 2011
Year: 2011

The need for accurate SQL progress estimation in the context of decision support administration has led to a number of techniques proposed for this task. Unfortunately, no single one of these progress estimators behaves robustly across the variety of SQL queries encountered in practice, meaning that each technique performs poorly for a significant fraction of queries. This paper proposes a novel estimator selection framework that uses a statistical model to characterize the sets of conditions under which certain estimators outperform others, leading to a significant increase in estimation robustness. The generality of this framework also enables us to add a number of novel "special purpose" estimators which increase accuracy further. Most importantly, the resulting model generalizes well to queries very different from the ones used to train it. We validate our findings using a large number of industrial real-life and benchmark workloads.
Interconnection of Communities of Practice: A Web Platform for Knowledge Management
Venue: arXiv cs.CY 2011
Year: 2011

Our works aim at developing a Web platform to connect various Communities of Practice (CoPs) and to capitalise on all their knowledge. This platform addresses CoPs interested in a same general activity, for example tutoring. For that purpose, we propose a general model of Interconnection of Communities of Practice (ICP), based on the concept of Constellation of Practice (CCP) developed by Wenger (1998). The model of ICP was implemented and has been used to develop the TE-Cap 2 platform which has, as its field of application, educational tutoring activities. In particular, we propose an indexation and search tool for the ICP knowledge base. The TE-Cap 2 platform has been used in real conditions. We present the main results of this descriptive investigation to validate this work.
Using Dynamic Simulation in the Development of Construction Machinery
Venue: arXiv cs.CE 2011
Year: 2011

As in the car industry for quite some time, dynamic simulation of complete vehicles is being practiced more and more in the development of off-road machinery. However, specific questions arise due not only to company structure and size, but especially to the type of product. Tightly coupled, non-linear subsystems of different domains make prediction and optimisation of the complete system's dynamic behaviour a challenge. Furthermore, the demand for versatile machines leads to sometimes contradictory target requirements and can turn the design process into a hunt for the least painful compromise. This can be avoided by profound system knowledge, assisted by simulation-driven product development. This paper gives an overview of joint research into this issue by Volvo Wheel Loaders and Linkoping University on that matter, lists the results of a related literature review and introduces the term "operateability". Rather than giving detailed answers, the problem space for ongoing and future research is examined and possible solutions are sketched.
Dynamic Simulation of Construction Machinery: Towards an Operator Model
Venue: arXiv cs.CE 2011
Year: 2011

In dynamic simulation of complete wheel loaders, one interesting aspect, specific for the working task, is the momentary power distribution between drive train and hydraulics, which is balanced by the operator. This paper presents the initial results to a simulation model of a human operator. Rather than letting the operator model follow a predefined path with control inputs at given points, it follows a collection of general rules that together describe the machine's working cycle in a generic way. The advantage of this is that the working task description and the operator model itself are independent of the machine's technical parameters. Complete sub-system characteristics can thus be changed without compromising the relevance and validity of the simulation. Ultimately, this can be used to assess a machine's total performance, fuel efficiency and operability already in the concept phase of the product development process.
An Event-driven Operator Model for Dynamic Simulation of Construction Machinery
Venue: arXiv cs.CE 2011
Year: 2011

Prediction and optimisation of a wheel loader's dynamic behaviour is a challenge due to tightly coupled, non-linear subsystems of different technical domains. Furthermore, a simulation regarding performance, efficiency, and operability cannot be limited to the machine itself, but has to include operator, environment, and work task. This paper presents some results of our approach to an event-driven simulation model of a human operator. Describing the task and the operator model independently of the machine's technical parameters, gives the possibility to change whole sub-system characteristics without compromising the relevance and validity of the simulation.
Flat Holonomies on Automata Networks
Venue: arXiv cs.DC 2011
Year: 2011

We consider asynchronous networks of identical finite (independent of network's size or topology) automata. Our automata drive any network from any initial configuration of states, to a coherent one in which it can carry efficiently any computations implementable on synchronous properly initialized networks of the same size. A useful data structure on such networks is a partial orientation of its edges. It needs to be flat, i.e. have null holonomy (no excess of up or down edges in any cycle). It also needs to be centered, i.e. have a unique node with no down edges. There are (interdependent) self-stabilizing asynchronous finite automata protocols assuring flat centered orientation. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative, responsible for a simple limited task. We describe an efficient reduction of any computational task to any such set of protocols compliant with our interface conditions.
A study of the edge-switching Markov-chain method for the generation of random graphs
Venue: arXiv cs.DM 2011
Year: 2011

We study the problem of generating connected random graphs with no self-loops or multiple edges and that, in addition, have a given degree sequence. The generation method we focus on is the edge-switching Markov-chain method, whose functioning depends on a parameter w related to the method's core operation of an edge switch. We analyze two existing heuristics for adjusting w during the generation of a graph and show that they result in a Markov chain whose stationary distribution is uniform, thus ensuring that generation occurs uniformly at random. We also introduce a novel w-adjusting heuristic which, even though it does not always lead to a Markov chain, is still guaranteed to converge to the uniform distribution under relatively mild conditions. We report on extensive computer experiments comparing the three heuristics' performance at generating random graphs whose node degrees are distributed as power laws.
The Tree Inclusion Problem: In Linear Space and Faster
Venue: arXiv cs.DS 2011
Year: 2011

Given two rooted, ordered, and labeled trees $P$ and $T$ the tree inclusion problem is to determine if $P$ can be obtained from $T$ by deleting nodes in $T$. This problem has recently been recognized as an important query primitive in XML databases. Kilpeläinen and Mannila [\emph{SIAM J. Comput. 1995}] presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when $P$ and $T$ have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. Let $n_S$, $l_S$, and $d_S$ denote the number of nodes, the number of leaves, and the %maximum depth of a tree $S \in \{P, T\}$. In this paper we show that the tree inclusion problem can be solved in space $O(n_T)$ and time: O(\min(l_Pn_T, l_Pl_T\log \log n_T + n_T, \frac{n_Pn_T}{\log n_T} + n_{T}\log n_{T})). This improves or matches the best known time complexities while using only linear space instead of quadratic. This is particularly important in practical applications, such as XML databases, where the space is likely to be a bottleneck.
Coding Solutions for the Secure Biometric Storage Problem
Venue: arXiv cs.IT 2011
Year: 2011

The paper studies the problem of securely storing biometric passwords, such as fingerprints and irises. With the help of coding theory Juels and Wattenberg derived in 1999 a scheme where similar input strings will be accepted as the same biometric. In the same time nothing could be learned from the stored data. They called their scheme a "fuzzy commitment scheme". In this paper we will revisit the solution of Juels and Wattenberg and we will provide answers to two important questions: What type of error-correcting codes should be used and what happens if biometric templates are not uniformly distributed, i.e. the biometric data come with redundancy. Answering the first question will lead us to the search for low-rate large-minimum distance error-correcting codes which come with efficient decoding algorithms up to the designed distance. In order to answer the second question we relate the rate required with a quantity connected to the "entropy" of the string, trying to estimate a sort of "capacity", if we want to see a flavor of the converse of Shannon's noisy coding theorem. Finally we deal with side-problems arising in a practical implementation and we propose a possible solution to the main one that seems to have so far prevented real life applications of the fuzzy scheme, as far as we know.
Randomized Work-Competitive Scheduling for Cooperative Computing on $k$-partite Task Graphs
Venue: arXiv cs.DC 2012
Year: 2012

A fundamental problem in distributed computing is the task of cooperatively executing a given set of $t$ tasks by $p$ processors where the communication medium is dynamic and subject to failures. The dynamics of the communication medium lead to groups of processors being disconnected and possibly reconnected during the entire course of the computation furthermore tasks can have dependencies among them. In this paper, we present a randomized algorithm whose competitive ratio is dependent on the dynamics of the communication medium and also on the nature of the dependencies among the tasks.
On the Morse-Hedlund complexity gap
Venue: arXiv cs.FL 2012
Year: 2012

In 1938, Morse and Hedlund proved that the subword complexity function of an infinite word is either bounded or at least linearly growing. In 1982, Ehrenfeucht and Rozenberg proved that this gap property holds for the subword complexity function of any language. The aim of the present paper is to present a self-contained, compact proof of Ehrenfeucht and Rozenberg's result.