OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Feedback Mechanisms for FDD Massive MIMO under User-level Cooperation
Venue: arXiv cs.IT 2016
Year: 2016

Channel state information (CSI) feedback is a challenging issue in frequency division multiplexing (FDD) massive MIMO systems. This paper studies a cooperative feedback scheme, where the users first exchange their CSI with each other by exploiting device-to-device (D2D) communications, then compute the precoder by themselves, and feed back the precoder to the base station (BS). Analytical results are derived to show that the cooperative precoder feedback is more efficient than the CSI feedback in terms of interference mitigation. Under the constraint of limited D2D communication capacity, we develop an adaptive CSI exchange strategy based on signal subspace projection and optimal bit partition. Numerical results demonstrate that the proposed cooperative precoder feedback scheme with adaptive CSI exchange significantly outperforms the CSI feedback scheme, even when the CSI is exchanged via rate-limited D2D communications.
A Spatial and Temporal Non-Local Filter Based Data Fusion
Venue: arXiv cs.CV 2016
Year: 2016

The trade-off in remote sensing instruments that balances the spatial resolution and temporal frequency limits our capacity to monitor spatial and temporal dynamics effectively. The spatiotemporal data fusion technique is considered as a cost-effective way to obtain remote sensing data with both high spatial resolution and high temporal frequency, by blending observations from multiple sensors with different advantages or characteristics. In this paper, we develop the spatial and temporal non-local filter based fusion model (STNLFFM) to enhance the prediction capacity and accuracy, especially for complex changed landscapes. The STNLFFM method provides a new transformation relationship between the fine-resolution reflectance images acquired from the same sensor at different dates with the help of coarse-resolution reflectance data, and makes full use of the high degree of spatiotemporal redundancy in the remote sensing image sequence to produce the final prediction. The proposed method was tested over both the Coleambally Irrigation Area study site and the Lower Gwydir Catchment study site. The results show that the proposed method can provide a more accurate and robust prediction, especially for heterogeneous landscapes and temporally dynamic areas.
Autonomous Landing of a Multirotor Micro Air Vehicle on a High Velocity Ground Vehicle
Venue: arXiv cs.RO 2016
Year: 2016

While autonomous multirotor micro aerial vehicles (MAVs) are uniquely well suited for certain types of missions benefiting from stationary flight capabilities, their more widespread usage still faces many hurdles, due in particular to their limited range and the difficulty of fully automating their deployment and retrieval. In this paper we address these issues by solving the problem of the automated landing of a quadcopter on a ground vehicle moving at relatively high speed. We present our system architecture, including the structure of our Kalman filter for the estimation of the relative position and velocity between the quadcopter and the landing pad, as well as our controller design for the full rendezvous and landing maneuvers. The system is experimentally validated by successfully landing in multiple trials a commercial quadcopter on the roof of a car moving at speeds of up to 50 km/h.
Handover Management in 5G and Beyond: A Topology Aware Skipping Approach
Venue: arXiv cs.NI 2016
Year: 2016

Network densification is found to be a potential solution to meet 5G capacity standards. Network densification offers more capacity by shrinking base stations' (BSs) footprints, thus reduces the number of users served by each BS. However, the gains in the capacity are achieved at the expense of increased handover (HO) rates. Hence, HO rate is a key performance limiting factor that should be carefully considered in densification planning. This paper sheds light on the HO problem that appears in dense 5G networks and proposes an effective solution via topology aware HO skipping. Different skipping techniques are considered and compared with the conventional best connected scheme. To this end, the effectiveness of the proposed schemes is validated by studying the average user rate in the downlink single-tier and two-tier cellular networks, which are modeled using Poisson point process and Poisson cluster process, respectively. The proposed skipping schemes show up to 47% gains in the average throughput that would maximize the benefit of network densification.
Call Trace and Memory Access Pattern based Runtime Insider Threat Detection for Big Data Platforms
Venue: arXiv cs.CR 2016
Year: 2016

Big data platforms such as Hadoop and Spark are being widely adopted both by academia and industry. In this paper, we propose a runtime intrusion detection technique that understands and works according to the properties of such distributed compute platforms. The proposed method is based on runtime analysis of system and library calls and memory access patterns of tasks running on the datanodes (slaves). First, the primary datanode of a big data system creates a behavior profile for every task it executes. A behavior profile includes (a) trace of the system & library calls made, and (b) sequence representing the sizes of private and shared memory accesses made during task execution. Then, the process behavior profile is shared with other replica datanodes that are scheduled to execute the same task on their copy of the same data. Next, these replica datanodes verify their local tasks with the help of the information embedded in the received behavior profiles. This is realized in two steps: (i) comparing the system & library calls metadata, and (ii) statistical matching of the memory access patterns. Finally, datanodes share their observations for consensus and report an intrusion to the namenode (master) if they find any discrepancy. The proposed solution was tested on a small hadoop cluster using the default MapReduce examples and the results show that our approach can detect insider attacks that cannot be detected with the traditional analysis metrics.
Non-Orthogonal Multiple Access (NOMA) for Downlink Multiuser MIMO Systems: User Clustering, Beamforming, and Power Allocation
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the application of non-orthogonal multiple access (NOMA) with successive interference cancellation (SIC) in downlink multiuser multiple-input multiple-output (MIMO) cellular systems, where the total number of receive antennas at user equipment (UE) ends in a cell is more than the number of transmit antennas at the base station (BS). We first dynamically group the UE receive antennas into a number of clusters equal to or more than the number of BS transmit antennas. A single beamforming vector is then shared by all the receive antennas in a cluster. We propose a linear beamforming technique in which all the receive antennas can significantly cancel the inter-cluster interference. On the other hand, the receive antennas in each cluster are scheduled on power domain NOMA basis with SIC at the receiver ends. For inter-cluster and intra-cluster power allocation, we provide dynamic power allocation solutions with an objective to maximizing the overall cell capacity. An extensive performance evaluation is carried out for the proposed MIMO-NOMA system and the results are compared with those for conventional orthogonal multiple access (OMA)-based MIMO systems and other existing MIMO-NOMA solutions. The numerical results quantify the capacity gain of the proposed MIMO-NOMA model over MIMO-OMA and other existing MIMO-NOMA solutions.
Low Power Wide Area Networks (LPWANs) for Internet of Things (IoT) Applications: Research Challenges and Future Trends
Venue: arXiv cs.NI 2016
Year: 2016

Internet of things (IoT) changes significantly the requirements for connectivity, mainly with regards to long battery life, low device cost, low deployment cost, extended coverage and support for a massive number of devices. Driven from these requirements, several different cellular and non-cellular low power wide area network (LPWAN) solutions are emerging and competing for IoT business and the overall connectivity market. Motivated by this, in this paper, we review and compare the design specifications of different LPWAN solutions, as well as, we discuss their suitability for different IoT applications. Finally, we present the challenges, future trends, and potential research directions for LPWANs.
An Agent-Based Model of Message Propagation in the Facebook Electronic Social Network
Venue: arXiv cs.SI 2016
Year: 2016

A large scale agent-based model of common Facebook users was designed to develop an understanding of the underlying mechanism of information diffusion within online social networks at a micro-level analysis. The agent-based model network structure is based on a sample from Facebook. Using an erased configuration model and the idea of common neighbours, a new correction procedure was investigated to overcome the problem of missing graph edges to construct a representative sample of the Facebook network graph. The model parameters are based on assumptions and general activity patterns (such as posting rate, time spent on Facebook etc.) taken from general data on Facebook. Using the agent-based model, the impact of post length, post score and publisher's friend count on the spread of wall posts in several scenarios was analyzed. Findings indicated that post content has the highest impact on the success of post propagation. However, amusing and absorbing but lengthy posts (e.g. a funny video) do not spread as well as short but unremarkable ones (e.g. an interesting photo). In contrast to product adoption and disease spread propagation models, the absence of a similar "epidemic" threshold in Facebook post diffusion is observed.
Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we study the $k$-forest problem in the model of resource augmentation. In the $k$-forest problem, given an edge-weighted graph $G(V,E)$, a parameter $k$, and a set of $m$ demand pairs $\subseteq V \times V$, the objective is to construct a minimum-cost subgraph that connects at least $k$ demands. The problem is hard to approximate---the best-known approximation ratio is $O(\min\{\sqrt{n}, \sqrt{k}\})$. Furthermore, $k$-forest is as hard to approximate as the notoriously-hard densest $k$-subgraph problem. While the $k$-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are {\em not} connected. In particular, the objective of the $k$-forest problem can be viewed as to remove at most $m-k$ demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the $k$-forest problem that, for every $ε>0$, removes at most $m-k$ demands and has cost no more than $O(1/ε^{2})$ times the cost of an optimal algorithm that removes at most $(1-ε)(m-k)$ demands.
Cultivating Software Performance in Cloud Computing
Venue: arXiv cs.PF 2016
Year: 2016

There exist multitudes of cloud performance metrics, including workload performance, application placement, software/hardware optimization, scalability, capacity, reliability, agility and so on. In this paper, we consider jointly optimizing the performance of the software applications in the cloud. The challenges lie in bringing a diversity of raw data into tidy data format, unifying performance data from multiple systems based on timestamps, and assessing the quality of the processed performance data. Even after verifying the quality of cloud performance data, additional challenges block optimizing cloud computing. In this paper, we identify the challenges of cloud computing from the perspectives of computing environment, data collection, performance analytics and production environment.
On the linear quadratic problem for systems with time reversed Markov jump parameters and the duality with filtering of Markov jump linear systems
Venue: arXiv cs.SY 2016
Year: 2016

We study a class of systems whose parameters are driven by a Markov chain in reverse time. A recursive characterization for the second moment matrix, a spectral radius test for mean square stability and the formulas for optimal control are given. Our results are determining for the question: is it possible to extend the classical duality between filtering and control of linear systems (whose matrices are transposed in the dual problem) by simply adding the jump variable of a Markov jump linear system. The answer is positive provided the jump process is reversed in time.
Introduction of Static Quality Analysis in Small and Medium-Sized Software Enterprises: Experiences from Technology Transfer
Venue: arXiv cs.SE 2016
Year: 2016

Today, small and medium-sized enterprises (SMEs) in the software industry face major challenges. Their resource constraints require high efficiency in development. Furthermore, quality assurance (QA) measures need to be taken to mitigate the risk of additional, expensive effort for bug fixes or compensations. Automated static analysis (ASA) can reduce this risk because it promises low application effort. SMEs seem to take little advantage of this opportunity. Instead, they still mainly rely on the dynamic analysis approach of software testing. In this article, we report on our experiences from a technology transfer project. Our aim was to evaluate the results static analysis can provide for SMEs as well as the problems that occur when introducing and using static analysis in SMEs. We analysed five software projects from five collaborating SMEs using three different ASA techniques: code clone detection, bug pattern detection and architecture conformance analysis. Following the analysis, we applied a quality model to aggregate and evaluate the results. Our study shows that the effort required to introduce ASA techniques in SMEs is small (mostly below one person-hour each). Furthermore, we encountered only few technical problems. By means of the analyses, we could detect multiple defects in production code. The participating companies perceived the analysis results to be a helpful addition to their current QA and will include the analyses in their QA process. With the help of the Quamoco quality model, we could efficiently aggregate and rate static analysis results. However, we also encountered a partial mismatch with the opinions of the SMEs. We conclude, that ASA and quality models can be a valuable and affordable addition to the QA process of SMEs.
Learning Joint Feature Adaptation for Zero-Shot Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Zero-shot recognition (ZSR) aims to recognize target-domain data instances of unseen classes based on the models learned from associated pairs of seen-class source and target domain data. One of the key challenges in ZSR is the relative scarcity of source-domain features (e.g. one feature vector per class), which do not fully account for wide variability in target-domain instances. In this paper we propose a novel framework of learning data-dependent feature transforms for scoring similarity between an arbitrary pair of source and target data instances to account for the wide variability in target domain. Our proposed approach is based on optimizing over a parameterized family of local feature displacements that maximize the source-target adaptive similarity functions. Accordingly we propose formulating zero-shot learning (ZSL) using latent structural SVMs to learn our similarity functions from training data. As demonstration we design a specific algorithm under the proposed framework involving bilinear similarity functions and regularized least squares as penalties for feature displacement. We test our approach on several benchmark datasets for ZSR and show significant improvement over the state-of-the-art. For instance, on aP&Y dataset we can achieve 80.89% in terms of recognition accuracy, outperforming the state-of-the-art by 11.15%.
Symbolic BDD and ADD Algorithms for Energy Games
Venue: arXiv cs.LO 2016
Year: 2016

Energy games, which model quantitative consumption of a limited resource, e.g., time or energy, play a central role in quantitative models for reactive systems. Reactive synthesis constructs a controller which satisfies a given specification, if one exists. For energy games a synthesized controller ensures to satisfy not only the safety constraints of the specification but also the quantitative constraints expressed in the energy game. A symbolic algorithm for energy games, recently presented by Chatterjee et al., is symbolic in its representation of quantitative values but concrete in the representation of game states and transitions. In this paper we present an algorithm that is symbolic both in the quantitative values and in the underlying game representation. We have implemented our algorithm using two different symbolic representations for reactive games, Binary Decision Diagrams (BDD) and Algebraic Decision Diagrams (ADD). We investigate the commonalities and differences of the two implementations and compare their running times on specifications of energy games.
Towards the Secure Storage of Images on Multi-Cloud System
Venue: arXiv cs.CR 2016
Year: 2016

With the rapidly changing technological realm, there is an urgent need to provide and protect the confidentiality of confidential images when stored in a cloud environment. To overcome the security risks associated with single cloud, multiple clouds offered by unrelated cloud providers have to be used. This paper outlines an integrated encryption scheme for the secure storage of confidential images on multiple clouds based on DNA sequences.
On the locality of arb-invariant first-order formulas with modulo counting quantifiers
Venue: arXiv cs.LO 2016
Year: 2016

We study Gaifman locality and Hanf locality of an extension of first-order logic with modulo p counting quantifiers (FO+MOD_p, for short) with arbitrary numerical predicates. We require that the validity of formulas is independent of the particular interpretation of the numerical predicates and refer to such formulas as arb-invariant formulas. This paper gives a detailed picture of locality and non-locality properties of arb-invariant FO+MOD_p. For example, on the class of all finite structures, for any p >= 2, arb-invariant FO+MOD_p is neither Hanf nor Gaifman local with respect to a sublinear locality radius. However, in case that p is an odd prime power, it is weakly Gaifman local with a polylogarithmic locality radius. And when restricting attention to the class of string structures, for odd prime powers p, arb-invariant FO+MOD_p is both Hanf and Gaifman local with a polylogarithmic locality radius. Our negative results build on examples of order-invariant FO+MOD_p formulas presented in Niemistö's PhD thesis. Our positive results make use of the close connection between FO+MOD_p and Boolean circuits built from NOT-gates and AND-, OR-, and MOD_p- gates of arbitrary fan-in.
Timing Matters: Online Dynamics in Broadcast Games
Venue: arXiv cs.DS 2016
Year: 2016

A central question in algorithmic game theory is to measure the inefficiency (ratio of costs) of Nash equilibria (NE) with respect to socially optimal solutions. The two established metrics used for this purpose are price of anarchy (POA) and price of stability (POS), which respectively provide upper and lower bounds on this ratio. A deficiency of these metrics, however, is that they are purely existential and shed no light on which of the equilibrium states are reachable in an actual game, i.e., via natural game dynamics. This is particularly striking if these metrics differ significantly, such as in network design games where the exponential gap between the best and worst NE states originally prompted the notion of POS in game theory (Anshelevich et al., FOCS 2002). In this paper, we make progress toward bridging this gap by studying network design games under natural game dynamics. First we show that in a completely decentralized setting, where agents arrive, depart, and make improving moves in an arbitrary order, the inefficiency of NE attained can be polynomially large. This implies that the game designer must have some control over the interleaving of these events in order to force the game to attain efficient NE. We complement our negative result by showing that if the game designer is allowed to execute a sequence of improving moves to create an equilibrium state after every batch of agent arrivals or departures, then the resulting equilibrium states attained by the game are exponentially more efficient, i.e., the ratio of costs compared to the optimum is only logarithmic. Overall, our two results establish that in network games, the efficiency of equilibrium states is dictated by whether agents are allowed to join or leave the game in arbitrary states, an observation that might be useful in analyzing the dynamics of other classes of games with divergent POS and POA bounds.
Hardness of Liar's Domination on Unit Disk Graphs
Venue: arXiv cs.CG 2016
Year: 2016

A unit disk graph is the intersection graph of a set of unit diameter disks in the plane. In this paper we consider liar's domination problem on unit disk graphs, a variant of dominating set problem. We call this problem as {\it Euclidean liar's domination problem}. In the Euclidean liar's domination problem, a set ${\cal P}=\{p_1,p_2,\ldots,p_n\}$ of $n$ points (disk centers) are given in the Euclidean plane. For $p \in {\cal P}$, $N[p]$ is a subset of ${\cal P}$ such that for any $q \in N[p]$, the Euclidean distance between $p$ and $q$ is less than or equal to 1, i.e., the corresponding unit diameter disks intersect. The objective of the Euclidean liar's domination problem is to find a subset $D\; (\subseteq {\cal P})$ of minimum size having the following properties : (i) $|N[p_i] \cap D| \geq 2$ for $1 \leq i \leq n$, and (ii) $|(N[p_i] \cup N[p_j]) \cap D| \geq 3$ for $i\neq j, 1\leq i,j \leq n$. This article aims to prove the Euclidean liar's domination problem is NP-complete.
Guruswami--Sudan List Decoding for Complex Reed--Solomon Codes
Venue: arXiv cs.IT 2016
Year: 2016

We analyze the Guruswami--Sudan list decoding algorithm for Reed--Solomon codes over the complex field for sparse recovery in Compressed Sensing. We propose methods of stabilizing both the interpolation and the root-finding steps against numerical instabilities, where the latter is the most sensitive. For this purpose, we modify the Roth--Ruckenstein algorithm and propose a method to refine its result using Newton's method. The overall decoding performance is then further improved using Generalized Minimum Distance decoding based on intrinsic soft information. This method also allows to obtain a unique solution of the recovery problem. The approach is numerically evaluated and shown to improve upon recently proposed decoding techniques.