OpenRaiser/Intern-Atlas huggingface dataset:
Network Capability in Localizing Node Failures via End-to-end Path Measurements
Venue: arXiv cs.NI 2015
Year: 2015

We investigate the capability of localizing node failures in communication networks from binary states (normal/failed) of end-to-end paths. Given a set of nodes of interest, uniquely localizing failures within this set requires that different observable path states associate with different node failure events. However, this condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our first contribution is a set of sufficient/necessary conditions for identifying a bounded number of failures within an arbitrary node set that can be tested in polynomial time. In addition to network topology and locations of monitors, our conditions also incorporate constraints imposed by the probing mechanism used. We consider three probing mechanisms that differ according to whether measurement paths are (i) arbitrarily controllable, (ii) controllable but cycle-free, or (iii) uncontrollable (determined by the default routing protocol). Our second contribution is to quantify the capability of failure localization through (1) the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized, and (2) the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in (1-2) can be converted into functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions. We demonstrate how measures (1-2) proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.
A square root map on Sturmian words
Venue: arXiv cs.DM 2015
Year: 2015

We introduce a square root map on Sturmian words and study its properties. Given a Sturmian word of slope $α$, there exists exactly six minimal squares in its language (a minimal square does not have a square as a proper prefix). A Sturmian word $s$ of slope $α$ can be written as a product of these six minimal squares: $s = X_1^2 X_2^2 X_3^2 \cdots$. The square root of $s$ is defined to be the word $\sqrt{s} = X_1 X_2 X_3 \cdots$. The main result of this paper is that that $\sqrt{s}$ is also a Sturmian word of slope $α$. Further, we characterize the Sturmian fixed points of the square root map, and we describe how to find the intercept of $\sqrt{s}$ and an occurrence of any prefix of $\sqrt{s}$ in $s$. Related to the square root map, we characterize the solutions of the word equation $X_1^2 X_2^2 \cdots X_n^2 = (X_1 X_2 \cdots X_n)^2$ in the language of Sturmian words of slope $α$ where the words $X_i^2$ are minimal squares of slope $α$. We also study the square root map in a more general setting. We explicitly construct an infinite set of non-Sturmian fixed points of the square root map. We show that the subshifts $Ω$ generated by these words have a curious property: for all $w \in Ω$ either $\sqrt{w} \in Ω$ or $\sqrt{w}$ is periodic. In particular, the square root map can map an aperiodic word to a periodic word.
Harmonic Extension
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we consider the harmonic extension problem, which is widely used in many applications of machine learning. We find that the transitional method of graph Laplacian fails to produce a good approximation of the classical harmonic function. To tackle this problem, we propose a new method called the point integral method (PIM). We consider the harmonic extension problem from the point of view of solving PDEs on manifolds. The basic idea of the PIM method is to approximate the harmonicity using an integral equation, which is easy to be discretized from points. Based on the integral equation, we explain the reason why the transitional graph Laplacian may fail to approximate the harmonicity in the classical sense and propose a different approach which we call the volume constraint method (VCM). Theoretically, both the PIM and the VCM computes a harmonic function with convergence guarantees, and practically, they are both simple, which amount to solve a linear system. One important application of the harmonic extension in machine learning is semi-supervised learning. We run a popular semi-supervised learning algorithm by Zhu et al. over a couple of well-known datasets and compare the performance of the aforementioned approaches. Our experiments show the PIM performs the best.
Understand Scene Categories by Objects: A Semantic Regularized Scene Classifier Using Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Scene classification is a fundamental perception task for environmental understanding in today's robotics. In this paper, we have attempted to exploit the use of popular machine learning technique of deep learning to enhance scene understanding, particularly in robotics applications. As scene images have larger diversity than the iconic object images, it is more challenging for deep learning methods to automatically learn features from scene images with less samples. Inspired by human scene understanding based on object knowledge, we address the problem of scene classification by encouraging deep neural networks to incorporate object-level information. This is implemented with a regularization of semantic segmentation. With only 5 thousand training images, as opposed to 2.5 million images, we show the proposed deep architecture achieves superior scene classification results to the state-of-the-art on a publicly available SUN RGB-D dataset. In addition, performance of semantic segmentation, the regularizer, also reaches a new record with refinement derived from predicted scene labels. Finally, we apply our SUN RGB-D dataset trained model to a mobile robot captured images to classify scenes in our university demonstrating the generalization ability of the proposed algorithm.
Laypeople and Experts risk perception of Cloud Computing Services
Venue: arXiv cs.CY 2015
Year: 2015

Cloud computing is revolutionising the way software services are procured and used by Government organizations and SMEs. Quantitative risk assessment of Cloud services is complex and undermined by specific security concerns regarding data confidentiality, integrity and availability. This study explores how the gap between the quantitative risk assessment and the perception of the risk can produce a bias in the decision-making process about Cloud computing adoption. The risk perception of experts in Cloud computing (N=37) and laypeople (N=81) about ten Cloud computing services was investigated using the psychometric paradigm. Results suggest that the risk perception of Cloud services can be represented by two components, called dread risk and unknown risk, which may explain up to 46% of the variance. Other factors influencing the risk perception were perceived benefits, trust in regulatory authorities and technology attitude. This study suggests some implications that could support Government and non-Government organizations in their strategies for Cloud computing adoption.
Adaptive-Robust Control of a Class of Nonlinear Systems with Unknown Input Delay
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, the tracking control problem of a class of uncertain Euler-Lagrange systems subjected to unknown input delay and bounded disturbances is addressed. To this front, a novel delay dependent control law, referred as Adaptive Robust Outer Loop Control (AROLC) is proposed. Compared to the conventional predictor based approaches, the proposed controller is capable of negotiating any input delay, within a stipulated range, without knowing the delay or its variation. The maximum allowable input delay is computed through Razumikhin-type stability analysis. AROLC also provides robustness against the disturbances due to input delay, parametric variations and unmodelled dynamics through switching control law. The novel adaptive law allows the switching gain to modify itself online in accordance with the tracking error without any prerequisite of the uncertainties. The uncertain system, employing AROLC, is shown to be Uniformly Ultimately Bounded (UUB). As a proof of concept, experimentation is carried out on a nonholonomic wheeled mobile robot with various time varying as well as fixed input delay, and better tracking accuracy of the proposed controller is noted compared to predictor based methodology.
Tensorizing Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

Deep neural networks currently demonstrate state-of-the-art performance in several domains. At the same time, models of this class are very demanding in terms of computational resources. In particular, a large amount of memory is required by commonly used fully-connected layers, making it hard to use the models on low-end devices and stopping the further increase of the model size. In this paper we convert the dense weight matrices of the fully-connected layers to the Tensor Train format such that the number of parameters is reduced by a huge factor and at the same time the expressive power of the layer is preserved. In particular, for the Very Deep VGG networks we report the compression factor of the dense weight matrix of a fully-connected layer up to 200000 times leading to the compression factor of the whole network up to 7 times.
Energy-Aware Forwarding Strategy for Metro Ethernet Networks
Venue: arXiv cs.NI 2015
Year: 2015

Energy optimization has become a crucial issue in the realm of ICT. This paper addresses the problem of energy consumption in a Metro Ethernet network. Ethernet technology deployments have been increasing tremendously because of their simplicity and low cost. However, much research remains to be conducted to address energy efficiency in Ethernet networks. In this paper, we propose a novel Energy Aware Forwarding Strategy for Metro Ethernet networks based on a modification of the Internet Energy Aware Routing (EAR) algorithm. Our contribution identifies the set of links to turn off and maintain links with minimum energy impact on the active state. Our proposed algorithm could be a superior choice for use in networks with low saturation, as it involves a tradeoff between maintaining good network performance and minimizing the active links in the network. Performance evaluation shows that, at medium load traffic, energy savings of 60% can be achieved. At high loads, energy savings of 40% can be achieved without affecting the network performance.
Efficient and Anonymous Two-Factor User Authentication in Wireless Sensor Networks: Achieving User Anonymity with Lightweight Sensor Computation
Venue: arXiv cs.CR 2015
Year: 2015

A smart-card-based user authentication scheme for wireless sensor networks (hereafter referred to as a SCA-WSN scheme) is designed to ensure that only users who possess both a smart card and the corresponding password are allowed to gain access to sensor data and their transmissions. Despite many research efforts in recent years, it remains a challenging task to design an efficient SCA-WSN scheme that achieves user anonymity. The majority of published SCA-WSN schemes use only lightweight cryptographic techniques (rather than public-key cryptographic techniques) for the sake of efficiency, and have been demonstrated to suffer from the inability to provide user anonymity. Some schemes employ elliptic curve cryptography for better security but require sensors with strict resource constraints to perform computationally expensive scalar-point multiplications; despite the increased computational requirements, these schemes do not provide user anonymity. In this paper, we present a new SCA-WSN scheme that not only achieves user anonymity but also is efficient in terms of the computation loads for sensors. Our scheme employs elliptic curve cryptography but restricts its use only to anonymous user-to-gateway authentication, thereby allowing sensors to perform only lightweight cryptographic operations. Our scheme also enjoys provable security in a formal model extended from the widely accepted Bellare-Pointcheval-Rogaway (2000) model to capture the user anonymity property and various SCA-WSN specific attacks (e.g., stolen smart card attacks, node capture attacks, privileged insider attacks, and stolen verifier attacks).
Estimating Random Delays in Modbus Network Using Experiments and General Linear Regression Neural Networks with Genetic Algorithm Smoothing
Venue: arXiv cs.SY 2015
Year: 2015

Time-varying delays adversely affect the performance of networked control sys-tems (NCS) and in the worst-case can destabilize the entire system. Therefore, modelling network delays is important for designing NCS. However, modelling time-varying delays is challenging because of their dependence on multiple pa-rameters such as length, contention, connected devices, protocol employed, and channel loading. Further, these multiple parameters are inherently random and de-lays vary in a non-linear fashion with respect to time. This makes estimating ran-dom delays challenging. This investigation presents a methodology to model de-lays in NCS using experiments and general regression neural network (GRNN) due to their ability to capture non-linear relationship. To compute the optimal smoothing parameter that computes the best estimates, genetic algorithm is used. The objective of the genetic algorithm is to compute the optimal smoothing pa-rameter that minimizes the mean absolute percentage error (MAPE). Our results illustrate that the resulting GRNN is able to predict the delays with less than 3% error. The proposed delay model gives a framework to design compensation schemes for NCS subjected to time-varying delays.
Optimal Power Control and Rate Adaptation for Ultra-Reliable M2M Control Applications
Venue: arXiv cs.NI 2015
Year: 2015

The main challenge of ultra-reliable machine-to-machine (M2M) control applications is to meet the stringent timing and reliability requirements of control systems, despite the adverse properties of wireless communication for delay and packet errors, and limited battery resources of the sensor nodes. Since the transmission delay and energy consumption of a sensor node are determined by the transmission power and rate of that sensor node and the concurrently transmitting nodes, the transmission schedule should be optimized jointly with the transmission power and rate of the sensor nodes. Previously, it has been shown that the optimization of power control and rate adaptation for each node subset can be separately formulated, solved and then used in the scheduling algorithm in the optimal solution of the joint optimization of power control, rate adaptation and scheduling problem. However, the power control and rate adaptation problem has been only formulated and solved for continuous rate transmission model, in which Shannon's capacity formulation for an Additive White Gaussian Noise (AWGN) wireless channel is used in the calculation of the maximum achievable rate as a function of Signal-to-Interference-plus-Noise Ratio (SINR). In this paper, we formulate the power control and rate adaptation problem with the objective of minimizing the time required for the concurrent transmission of a set of sensor nodes while satisfying their transmission delay, reliability and energy consumption requirements based on the more realistic discrete rate transmission model, in which only a finite set of transmit rates are supported. We propose a polynomial time algorithm to solve this problem and prove the optimality of the proposed algorithm. We then combine it with the previously proposed scheduling algorithms and demonstrate its close to optimal performance via extensive simulations.
To What Extent Is Stress Testing of Android TV Applications Automated in Industrial Environments?
Venue: arXiv cs.SE 2015
Year: 2015

An Android-based smart Television (TV) must reliably run its applications in an embedded program environment under diverse hardware resource conditions. Owing to the diverse hardware components used to build numerous TV models, TV simulators are usually not high enough in fidelity to simulate various TV models, and thus are only regarded as unreliable alternatives when stress testing such applications. Therefore, even though stress testing on real TV sets is tedious, it is the de facto approach to ensure the reliability of these applications in the industry. In this paper, we study to what extent stress testing of smart TV applications can be fully automated in the industrial environments. To the best of our knowledge, no previous work has addressed this important question. We summarize the find-ings collected from 10 industrial test engineers to have tested 20 such TV applications in a real production environment. Our study shows that the industry required test automation supports on high-level GUI object controls and status checking, setup of resource conditions and the interplay between the two. With such supports, 87% of the industrial test specifications of one TV model can be fully automated and 71.4% of them were found to be fully reusable to test a subsequent TV model with major up-grades of hardware, operating system and application. It repre-sents a significant improvement with margins of 28% and 38%, respectively, compared to stress testing without such supports.
Twitter as a Transport Layer Platform
Venue: arXiv cs.SI 2015
Year: 2015

Internet messengers and social networks have become an integral part of modern digital life. We have in mind not only the interaction between individual users but also a variety of applications that exist in these applications. Typically, applications for social networks use the universal login system and rely on data from social networks. Also, such applications are likely to get more traction when they are inside of the big social network like Facebook. At the same time, less attention is paid to communication capabilities of social networks. In this paper, we target Twitter as a messaging system at the first hand. We describe the way information systems can use Twitter as a transport layer for own services. Our work introduces a programmable service called 411 for Twitter, which supports user-defined and application-specific commands through tweets.
End-to-end delay in two hop relay MANETs with limited buffer
Venue: arXiv cs.PF 2015
Year: 2015

Despite lots of literature has been dedicated to researching the delay performance in two-hop relay (2HR) mobile ad hoc networks (MANETs), however, they usually assume the buffer size of each node is infinite, so these studies are not applicable to and thus may not reflect the real delay performance of a practical MANET with limited buffer. To address this issue, in this paper we explore the packet end-to-end delay in a 2HR MANET, where each node is equipped with a bounded and shared relay-buffer for storing and forwarding packets of all other flows. The transmission range of each node can be adjusted and a group-based scheduling scheme is adopted to avoid interference between simultaneous transmissions, meanwhile a handshake mechanism is added to the 2HR routing algorithm to avoid packet loss. With the help of Markov Chain Theory and Queuing Theory, we develop a new framework to fully characterize the packet delivery processes, and obtain the relay-buffer blocking probability (RBP) under any given exogenous packet input rate. Based on the RBP, we can compute the packet queuing delay in its source node and delivery delay respectively, and further derive the end-to-end delay in such a MANET with limited buffer.
Fast Parallel Fixed-Parameter Algorithms via Color Coding
Venue: arXiv cs.CC 2015
Year: 2015

Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently \emph{sequential} and, thus, make no use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature -- including vertex cover, packing problems, cluster editing, cutting vertices, finding embeddings, or finding matchings -- but that there are parallel algorithms working in \emph{constant} time or at least in time \emph{depending only on the parameter} (and not on the size of the input) for these problems. Phrased in terms of complexity classes, we place numerous natural parameterized problems in parameterized versions of AC$^0$. On a more technical level, we show how the \emph{color coding} method can be implemented in constant time and apply it to embedding problems for graphs of bounded tree-width or tree-depth and to model checking first-order formulas in graphs of bounded degree.
Feasibility Evaluation of 6LoWPAN over Bluetooth Low Energy
Venue: arXiv cs.NI 2015
Year: 2015

IPv6 over Low power Wireless Personal Area Network (6LoWPAN) is an emerging technology to enable ubiquitous IoT services. However, there are very few studies of the performance evaluation on real hardware environments. This paper demonstrates the feasibility of 6LoWPAN through conducting a preliminary performance evaluation of a commodity hardware environment, including Bluetooth Low Energy (BLE) network, Raspberry Pi, and a laptop PC. Our experimental results show that the power consumption of 6LoWPAN over BLE is one-tenth lower than that of IP over WiFi; the performance significantly depends on the distance between devices and the message size; and the communication completely stops when bursty traffic transfers. This observation provides our optimistic conclusions on the feasibility of 6LoWPAN although the maturity of implementations is a remaining issue.
Designing Behaviour in Bio-inspired Robots Using Associative Topologies of Spiking-Neural-Networks
Venue: arXiv cs.RO 2015
Year: 2015

This study explores the design and control of the behaviour of agents and robots using simple circuits of spiking neurons and Spike Timing Dependent Plasticity (STDP) as a mechanism of associative and unsupervised learning. Based on a "reward and punishment" classical conditioning, it is demonstrated that these robots learnt to identify and avoid obstacles as well as to identify and look for rewarding stimuli. Using the simulation and programming environment NetLogo, a software engine for the Integrate and Fire model was developed, which allowed us to monitor in discrete time steps the dynamics of each single neuron, synapse and spike in the proposed neural networks. These spiking neural networks (SNN) served as simple brains for the experimental robots. The Lego Mindstorms robot kit was used for the embodiment of the simulated agents. In this paper the topological building blocks are presented as well as the neural parameters required to reproduce the experiments. This paper summarizes the resulting behaviour as well as the observed dynamics of the neural circuits. The Internet-link to the NetLogo code is included in the annex.
On the Doubly Sparse Compressed Sensing Problem
Venue: arXiv cs.IT 2015
Year: 2015

A new variant of the Compressed Sensing problem is investigated when the number of measurements corrupted by errors is upper bounded by some value l but there are no more restrictions on errors. We prove that in this case it is enough to make 2(t+l) measurements, where t is the sparsity of original data. Moreover for this case a rather simple recovery algorithm is proposed. An analog of the Singleton bound from coding theory is derived what proves optimality of the corresponding measurement matrices.