OpenRaiser/Intern-Atlas huggingface dataset:
Network Coded Transmission of Fountain Codes over Cooperative Relay Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, a transmission strategy of fountain codes over cooperative relay networks is proposed. When more than one relay nodes are available, we apply network coding to fountain-coded packets. By doing this, partial information is made available to the destination node about the upcoming message block. It is therefore able to reduce the required number of transmissions over erasure channels, hence increasing the effective throughput. Its application to wireless channels with Rayleigh fading and AWGN noise is also analysed, whereby the role of analogue network coding and optimal weight selection is demonstrated.
Channel Estimation for Opportunistic Spectrum Access: Uniform and Random Sensing
Venue: arXiv cs.IT 2010
Year: 2010

The knowledge of channel statistics can be very helpful in making sound opportunistic spectrum access decisions. It is therefore desirable to be able to efficiently and accurately estimate channel statistics. In this paper we study the problem of optimally placing sensing times over a time window so as to get the best estimate on the parameters of an on-off renewal channel. We are particularly interested in a sparse sensing regime with a small number of samples relative to the time window size. Using Fisher information as a measure, we analytically derive the best and worst sensing sequences under a sparsity condition. We also present a way to derive the best/worst sequences without this condition using a dynamic programming approach. In both cases the worst turns out to be the uniform sensing sequence, where sensing times are evenly spaced within the window. With these results we argue that without a priori knowledge, a robust sensing strategy should be a randomized strategy. We then compare different random schemes using a family of distributions generated by the circular $β$ ensemble, and propose an adaptive sensing scheme to effectively track time-varying channel parameters. We further discuss the applicability of compressive sensing for this problem.
Eigenvectors for clustering: Unipartite, bipartite, and directed graph cases
Venue: arXiv cs.LG 2010
Year: 2010

This paper presents a concise tutorial on spectral clustering for broad spectrum graphs which include unipartite (undirected) graph, bipartite graph, and directed graph. We show how to transform bipartite graph and directed graph into corresponding unipartite graph, therefore allowing a unified treatment to all cases. In bipartite graph, we show that the relaxed solution to the $K$-way co-clustering can be found by computing the left and right eigenvectors of the data matrix. This gives a theoretical basis for $K$-way spectral co-clustering algorithms proposed in the literatures. We also show that solving row and column co-clustering is equivalent to solving row and column clustering separately, thus giving a theoretical support for the claim: ``column clustering implies row clustering and vice versa''. And in the last part, we generalize the Ky Fan theorem---which is the central theorem for explaining spectral clustering---to rectangular complex matrix motivated by the results from bipartite graph analysis.
Pebbles and Branching Programs for Tree Evaluation
Venue: arXiv cs.CC 2010
Year: 2010

We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root. We show that the standard black pebbling algorithm applied to the binary tree of height h yields a deterministic k-way branching program with Theta(k^h) states solving this problem, and we prove that this upper bound is tight for h=2 and h=3. We introduce a simple semantic restriction called "thrifty" on k-way branching programs solving tree evaluation problems and show that the same state bound of Theta(k^h) is tight (up to a constant factor) for all h >= 2 for deterministic thrifty programs. We introduce fractional pebbling for trees and show that this yields nondeterministic thrifty programs with Theta(k^{h/2+1}) states solving the Boolean problem "determine whether the root has value 1". We prove that this bound is tight for h=2,3,4, and tight for unrestricted nondeterministic k-way branching programs for h=2,3.
An Algebraic Approach to Physical-Layer Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.
On the Subspace of Image Gradient Orientations
Venue: arXiv cs.CV 2010
Year: 2010

We introduce the notion of Principal Component Analysis (PCA) of image gradient orientations. As image data is typically noisy, but noise is substantially different from Gaussian, traditional PCA of pixel intensities very often fails to estimate reliably the low-dimensional subspace of a given data population. We show that replacing intensities with gradient orientations and the $\ell_2$ norm with a cosine-based distance measure offers, to some extend, a remedy to this problem. Our scheme requires the eigen-decomposition of a covariance matrix and is as computationally efficient as standard $\ell_2$ PCA. We demonstrate some of its favorable properties on robust subspace estimation.
Cross-Band Interference Considered Harmful in OFDM Based Distributed Spectrum Sharing
Venue: arXiv cs.IT 2010
Year: 2010

In the past few years we have witnessed the paradigm shift from static spectrum allocation to dynamic spectrum access/sharing. Orthogonal Frequency-Division Multiple Access (OFDMA) is a promising mechanism to implement the agile spectrum access. However, in wireless distributed networks where tight synchronization is infeasible, OFDMA faces the problem of cross-band interference. Subcarriers used by different users are no longer orthogonal, and transmissions operating on non-overlapping subcarriers can interfere with each other. In this paper, we explore the cause of cross-band interference and analytically quantify its strength and impact on packet transmissions. Our analysis captures three key practical artifacts: inter-link frequency offset, temporal sampling mismatch and power heterogeneity. To our best knowledge, this work is the first to systematically analyze the cause and impact of cross-band interference. Using insights from our analysis, we then build and compared three mitigating methods to combat cross-band interference. Analytical and simulation results show that placing frequency guardband at link boundaries is the most effective solution in distributed spectrum sharing, while the other two frequency-domain methods are sensitive to either temporal sampling mismatch or inter-link frequency offset. We find that the proper guardband size depends heavily on power heterogeneity. Consequently, protocol designs for dynamic spectrum access should carefully take into account the cross-band interference when configuring spectrum usage.
A note on concentration of submodular functions
Venue: arXiv cs.DM 2010
Year: 2010

We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables.
Constructing Path Efficient and Energy Aware Virtual Multicast Backbones in Static Ad Hoc Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

For stationary wireless ad hoc networks, one of the key challenging issues in routing and multicasting is to conserve as much energy as possible without compromising path efficiency measured as end-to-end delay. In this paper, we address the problem of path efficient and energy aware multicasting in static wireless ad hoc networks. We propose a novel distributed scalable algorithm for finding a virtual multicast backbone (VMB). Based on this VMB, we have further developed a multicasting scheme that jointly improves path efficiency and energy conservation. By exploiting inherent broadcast advantage of wireless communication and employing a more realistic energy consumption model for wireless communication which not only depends on radio propagation losses but also on energy losses in transceiver circuitry, our simulation results show that the proposed VMB-based multicasting scheme outperforms existing prominent tree based energy conserving, path efficient multicasting schemes.
On Testing Constraint Programs
Venue: arXiv cs.SE 2010
Year: 2010

The success of several constraint-based modeling languages such as OPL, ZINC, or COMET, appeals for better software engineering practices, particularly in the testing phase. This paper introduces a testing framework enabling automated test case generation for constraint programming. We propose a general framework of constraint program development which supposes that a first declarative and simple constraint model is available from the problem specifications analysis. Then, this model is refined using classical techniques such as constraint reformulation, surrogate and global constraint addition, or symmetry-breaking to form an improved constraint model that must be thoroughly tested before being used to address real-sized problems. We think that most of the faults are introduced in this refinement step and propose a process which takes the first declarative model as an oracle for detecting non-conformities. We derive practical test purposes from this process to generate automatically test data that exhibit non-conformities. We implemented this approach in a new tool called CPTEST that was used to automatically detect non-conformities on two classical benchmark programs, namely the Golomb rulers and the car-sequencing problem.
A Multiprocessor Communication Architecture For High Speed Networks
Venue: arXiv cs.NI 2010
Year: 2010

Over the years, communication speed of networks has increased from a few Kbps to several Mbps, as also the bandwidth demand, Communication Protocols, however have not improved to that extent. With the advent of Wavelength Division Multiplexing (WDM), it is now possible to "tune" protocols to current and future demands. The purpose of this paper is to evolve a High Speed Network architecture, which will cater to the needs of bandwidth-consuming applications, such as voice, video and high definition image transmission.
Multi-sensorial interaction with a nano-scale phenomenon : the force curve
Venue: arXiv cs.GR 2010
Year: 2010

Using Atomic Force Microscopes (AFM) to manipulate nano-objects is an actual challenge for surface scientists. Basic haptic interfacesbetween the AFM and experimentalists have already been implemented. Themulti-sensory renderings (seeing, hearing and feeling) studied from acognitive point of view increase the efficiency of the actual interfaces. Toallow the experimentalist to feel and touch the nano-world, we add mixedrealities between an AFM and a force feedback device, enriching thus thedirect connection by a modeling engine. We present in this paper the firstresults from a real-time remote-control handling of an AFM by our ForceFeedback Gestural Device through the example of the approach-retract curve.
Key Distribution Protocols Based on Extractors Under the Condition of Noisy Channels in the Presence of an Active Adversary
Venue: arXiv cs.IT 2010
Year: 2010

We consider in this paper the information-theoretic secure key distribution problem over main and wire-tap noise channels with a public discussion in presence of an active adversary. In contrast to the solution proposed by ourselves for a similar problem using hashing for privacy amplification, in the current paper we use a technique of extractors. We propose modified key distribution protocols for which we prove explicit estimates of key rates without the use of estimates with uncertain coefficients in notations $O,Ω,Θ$. This leads in the new conclusion that the use of extractors is superior to the use of hash functions only with the very large key lengths $\ell$ (of order $\ell>10^5$ bits). We suggest hybrid key distribution protocols consisting from two consecutively executed stages. At the fist stage it is generated a short authentication key based on hash function, whereas at the second stage it is generated the final key with the use of extractors. We show that in fact the use of extraction procedure is effective only at the second stage. We get also some constructive estimates of the key rates for such protocols.
Power Control and Performance Analysis of Outage-Limited Cellular Network with MUD-SIC and Macro-Diversity
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we analyze the uplink goodput (bits/sec/Hz successfully decoded) and per-user packet outage in a cellular network using multi-user detection with successive interference cancellation (MUD-SIC). We consider non-ergodic fading channels where microscopic fading channel information is not available at the transmitters. As a result, packet outage occurs whenever the data rate of packet transmissions exceeds the instantaneous mutual information even if powerful channel coding is applied for protection. We are interested to study the role of macro-diversity (MDiv) between multiple base stations on the MUD-SIC performance where the effect of potential error-propagation during the SIC processing is taken into account. While the jointly optimal power and decoding order in the MUD-SIC are NP hard problem, we derive a simple on/off power control and asymptotically optimal decoding order with respect to the transmit power. Based on the information theoretical framework, we derive the closed-form expressions on the total system goodput as well as the per-user packet outage probability. We show that the system goodput does not scale with SNR due to mutual interference in the SIC process and macro-diversity (MDiv) could alleviate the problem and benefit to the system goodput.
Efficient Algorithms and Data Structures for Massive Data Sets
Venue: arXiv cs.DS 2010
Year: 2010

For many algorithmic problems, traditional algorithms that optimise on the number of instructions executed prove expensive on I/Os. Novel and very different design techniques, when applied to these problems, can produce algorithms that are I/O efficient. This thesis adds to the growing chorus of such results. The computational models we use are the external memory model and the W-Stream model. On the external memory model, we obtain the following results. (1) An I/O efficient algorithm for computing minimum spanning trees of graphs that improves on the performance of the best known algorithm. (2) The first external memory version of soft heap, an approximate meldable priority queue. (3) Hard heap, the first meldable external memory priority queue that matches the amortised I/O performance of the known external memory priority queues, while allowing a meld operation at the same amortised cost. (4) I/O efficient exact, approximate and randomised algorithms for the minimum cut problem, which has not been explored before on the external memory model. (5) Some lower and upper bounds on I/Os for interval graphs. On the W-Stream model, we obtain the following results. (1) Algorithms for various tree problems and list ranking that match the performance of the best known algorithms and are easier to implement than them. (2) Pass efficient algorithms for sorting, and the maximal independent set problems, that improve on the best known algorithms. (3) Pass efficient algorithms for the graphs problems of finding vertex-colouring, approximate single source shortest paths, maximal matching, and approximate weighted vertex cover. (4) Lower bounds on passes for list ranking and maximal matching. We propose two variants of the W-Stream model, and design algorithms for the maximal independent set, vertex-colouring, and planar graph single source shortest paths problems on those models.
Using machine learning to make constraint solver implementation decisions
Venue: arXiv cs.AI 2010
Year: 2010

Programs to solve so-called constraint problems are complex pieces of software which require many design decisions to be made more or less arbitrarily by the implementer. These decisions affect the performance of the finished solver significantly. Once a design decision has been made, it cannot easily be reversed, although a different decision may be more appropriate for a particular problem. We investigate using machine learning to make these decisions automatically depending on the problem to solve with the alldifferent constraint as an example. Our system is capable of making non-trivial, multi-level decisions that improve over always making a default choice.
Two-Way Writing on Dirty Paper
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, the Two-Way Channel (TWC) with Cannel State Information (CSI) is investigated. First, an achievable rate region is derived for the discrete memoryless channel. Then by extending the result to the Gaussian TWC with additive interference noise, it is shown that the capacity region of the later channel is the same as the capacity when there is no interference, i.e. a two-way version of Costa's writing on dirty paper problem is established.
Criticism of Knapsack Encryption Scheme
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we analyze a knapsack schemes. The one is suggested by Su, which is relied on a new method entitled permutation combination method. We demonstrate that this permutation method is useless to the security of the scheme. Since the special super increasing construction, we can break this scheme employ the algorithm provided by Shamir scheme. Finally, we provide an enhanced version of Su scheme to avoid these attacks.
Energy Efficient Multi-Level Clustering To Prolong The Lifetime of Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Clustering in wireless sensor networks (WSNs) is an important technique to ease topology management and routing. Clustering provides an effective method for prolonging lifetime of a WSN. This paper proposes energy efficient multi-level clustering schemes for wireless sensor networks. Wireless sensor nodes are extremely energy constrained with a limited transmission range. Due to large area of deployment, the network needs to have a multi-level clustering protocol that will enable far-off nodes to communicate with the base station. Simulation is used to analyze the proposed protocols and compare their performance with existing protocol EEMC. Simulation results demonstrate that our proposed protocols are effective in prolonging the network lifetime.
Bucklin Voting is Broadly Resistant to Control
Venue: arXiv cs.CC 2010
Year: 2010

Electoral control models ways of changing the outcome of an election via such actions as adding/deleting/partitioning either candidates or voters. These actions modify an election's participation structure and aim at either making a favorite candidate win ("constructive control") or prevent a despised candidate from winning ("destructive control"), which yields a total of 22 standard control scenarios. To protect elections from such control attempts, computational complexity has been used to show that electoral control, though not impossible, is computationally prohibitive. Among natural voting systems with a polynomial-time winner problem, the two systems with the highest number of proven resistances to control types (namely 19 out of 22) are "sincere-strategy preference-based approval voting" (SP-AV, a modification of a system proposed by Brams and Sanver) and fallback voting. Both are hybrid systems; e.g., fallback voting combines approval with Bucklin voting. In this paper, we study the control complexity of Bucklin voting itself and show that it behaves equally well in terms of control resistance for the 20 cases investigated so far. As Bucklin voting is a special case of fallback voting, all resistances shown for Bucklin voting in this paper strengthen the corresponding resistance for fallback voting.
Reduction in iron losses in Indirect Vector-Controlled IM Drive using FLC
Venue: arXiv cs.OH 2010
Year: 2010

This paper describes the use of fuzzy logic controller for efficiency optimization control of a drive while keeping good dynamic response. At steady-state light-load condition, the fuzzy controller adaptively adjusts the excitation current with respect to the torque current to give the minimum total copper and iron loss. The measured input power such that, for a given load torque and speed, the drive settles down to the minimum input power, i.e., operates at maximum efficiency. The low-frequency pulsating torque due to decrementation of flux is compensated in a feed forward manner. If the load torque or speed commands changes, the efficiency search algorithm is abandoned and the rated flux is established to get the best dynamic response. The drive system with the proposed efficiency optimization controller has been simulated with lossy models of converter and machine, and its performance has been thoroughly investigated.
Selection of Architecture Styles using Analytic Network Process for the Optimization of Software Architecture
Venue: arXiv cs.SE 2010
Year: 2010

The continuing process of software systems enlargement in size and complexity becomes system design extremely important for software production. In this way, the role of software architecture is significantly important in software development. It serves as an evaluation and implementation plan for software development and software evaluation. Consequently, choosing the correct architecture is a critical issue in software engineering domain. Moreover,software architecture selection is a multicriteria decision-making problem in which different goals and objectives must be taken into consideration. In this paper, more precise and suitable decisions in selection of architecture styles have been presented by using ANP inference to support decisions of software architects in order to exploit properties of styles in the best way to optimize the design of software architecture.
Inaccuracy Minimization by Partioning Fuzzy Data Sets - Validation of Analystical Methodology
Venue: arXiv cs.AI 2010
Year: 2010

In the last two decades, a number of methods have been proposed for forecasting based on fuzzy time series. Most of the fuzzy time series methods are presented for forecasting of car road accidents. However, the forecasting accuracy rates of the existing methods are not good enough. In this paper, we compared our proposed new method of fuzzy time series forecasting with existing methods. Our method is based on means based partitioning of the historical data of car road accidents. The proposed method belongs to the kth order and time-variant methods. The proposed method can get the best forecasting accuracy rate for forecasting the car road accidents than the existing methods.