OpenRaiser/Intern-Atlas huggingface dataset:
A Genetic Algorithm Based Finger Selection Scheme for UWB MMSE Rake Receivers
Venue: arXiv cs.IT 2005
Year: 2005

Due to a large number of multipath components in a typical ultra wideband (UWB) system, selective Rake (SRake) receivers, which combine energy from a subset of multipath components, are commonly employed. In order to optimize system performance, an optimal selection of multipath components to be employed at fingers of an SRake receiver needs to be considered. In this paper, this finger selection problem is investigated for a minimum mean square error (MMSE) UWB SRake receiver. Since the optimal solution is NP hard, a genetic algorithm (GA) based iterative scheme is proposed, which can achieve near-optimal performance after a reasonable number of iterations. Simulation results are presented to compare the performance of the proposed finger selection algorithm with those of the conventional and optimal schemes.
MAEC : A Movement-Assisted Energy Conserving Method in Event Driven Wireless Sensor Networks
Venue: arXiv cs.NI 2005
Year: 2005

Energy is one of the most important resources in wireless sensor networks. Recently, the mobility of base station has been exploited to preserve the energy. But in event driven networks, the mobility issue is quite different from the continuous monitoring one because only a small portion of sensor node has data to send at one time. The number of sensor node that forward traffic should be minimized to prolong the network lifetime. In this paper, we propose a movement-assisted energy conserving method which tries to reduce the amount of forwarding sensor node by directing the base station to move close to the hotspots. This method achieves good performance especially when applied to a network with a set of cooperative mobile base station. Extensive simulation has been done to verify the effectiveness of the propose schema.
A Utility-Based Approach to Power Control and Receiver Design in Wireless Data Networks
Venue: arXiv cs.IT 2005
Year: 2005

In this work, the cross-layer design problem of joint multiuser detection and power control is studied using a game-theoretic approach. The uplink of a direct-sequence code division multiple access (DS-CDMA) data network is considered and a non-cooperative game is proposed in which users in the network are allowed to choose their uplink receivers as well as their transmit powers to maximize their own utilities. The utility function measures the number of reliable bits transmitted by the user per joule of energy consumed. Focusing on linear receivers, the Nash equilibrium for the proposed game is derived. It is shown that the equilibrium is one where the powers are SIR-balanced with the minimum mean square error (MMSE) detector as the receiver. In addition, this framework is used to study power control games for the matched filter, the decorrelator, and the MMSE detector; and the receivers' performance is compared in terms of the utilities achieved at equilibrium (in bits/Joule). The optimal cooperative solution is also discussed and compared with the non-cooperative approach. Extensions of the results to the case of multiple receive antennas are also presented. In addition, an admission control scheme based on maximizing the total utility in the network is proposed.
Distributed Regression in Sensor Networks: Training Distributively with Alternating Projections
Venue: arXiv cs.LG 2005
Year: 2005

Wireless sensor networks (WSNs) have attracted considerable attention in recent years and motivate a host of new challenges for distributed signal processing. The problem of distributed or decentralized estimation has often been considered in the context of parametric models. However, the success of parametric methods is limited by the appropriateness of the strong statistical assumptions made by the models. In this paper, a more flexible nonparametric model for distributed regression is considered that is applicable in a variety of WSN applications including field estimation. Here, starting with the standard regularized kernel least-squares estimator, a message-passing algorithm for distributed estimation in WSNs is derived. The algorithm can be viewed as an instantiation of the successive orthogonal projection (SOP) algorithm. Various practical aspects of the algorithm are discussed and several numerical simulations validate the potential of the approach.
Monotone Conditional Complexity Bounds on Future Prediction Errors
Venue: arXiv cs.LG 2005
Year: 2005

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x_1...x_t. We bound the future prediction performance on x_{t+1}x_{t+2}... by a new variant of algorithmic complexity of m given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
Defensive Universal Learning with Experts
Venue: arXiv cs.LG 2005
Year: 2005

This paper shows how universal learning can be achieved with expert advice. To this aim, we specify an experts algorithm with the following characteristics: (a) it uses only feedback from the actions actually chosen (bandit setup), (b) it can be applied with countably infinite expert classes, and (c) it copes with losses that may grow in time appropriately slowly. We prove loss bounds against an adaptive adversary. From this, we obtain a master algorithm for "reactive" experts problems, which means that the master's actions may influence the behavior of the adversary. Our algorithm can significantly outperform standard experts algorithms on such problems. Finally, we combine it with a universal expert class. The resulting universal learner performs -- in a certain sense -- almost as well as any computable strategy, for any online decision problem. We also specify the (worst-case) convergence speed, which is very slow.
Finite automata for testing uniqueness of Eulerian trails
Venue: arXiv cs.CC 2005
Year: 2005

We investigate the condition under which the Eulerian trail of a digraph is unique, and design a finite automaton to examine it. The algorithm is effective, for if the condition is violated, it will be noticed immediately without the need to trace through the whole trail.
Paving the Way for Image Understanding: A New Kind of Image Decomposition is Desired
Venue: arXiv cs.CV 2005
Year: 2005

In this paper we present an unconventional image segmentation approach which is devised to meet the requirements of image understanding and pattern recognition tasks. Generally image understanding assumes interplay of two sub-processes: image information content discovery and image information content interpretation. Despite of its widespread use, the notion of "image information content" is still ill defined, intuitive, and ambiguous. Most often, it is used in the Shannon's sense, which means information content assessment averaged over the whole signal ensemble. Humans, however,rarely resort to such estimates. They are very effective in decomposing images into their meaningful constituents and focusing attention to the perceptually relevant image parts. We posit that following the latest findings in human attention vision studies and the concepts of Kolmogorov's complexity theory an unorthodox segmentation approach can be proposed that provides effective image decomposition to information preserving image fragments well suited for subsequent image interpretation. We provide some illustrative examples, demonstrating effectiveness of this approach.
Software Performance Analysis
Venue: arXiv cs.PF 2005
Year: 2005

The key to speeding up applications is often understanding where the elapsed time is spent, and why. This document reviews in depth the full array of performance analysis tools and techniques available on Linux for this task, from the traditional tools like gcov and gprof, to the more advanced tools still under development like oprofile and the Linux Trace Toolkit. The focus is more on the underlying data collection and processing algorithms, and their overhead and precision, than on the cosmetic details of the graphical user interface frontends.
ATTENTION: ATTackEr traceback using MAC layer abNormality detecTION
Venue: arXiv cs.NI 2005
Year: 2005

Denial-of-Service (DoS) and Distributed DoS (DDoS) attacks can cause serious problems in wireless networks due to limited network and host resources. Attacker traceback is a promising solution to take a proper countermeasure near the attack origins, to discourage attackers from launching attacks, and for forensics. However, attacker traceback in Mobile Ad-hoc Networks (MANETs) is a challenging problem due to the dynamic topology, and limited network resources. It is especially difficult to trace back attacker(s) when they are moving to avoid traceback. In this paper, we introduce the ATTENTION protocol framework, which pays special attention to MAC layer abnormal activity under attack. ATTENTION consists of three classes, namely, coarse-grained traceback, fine-grained traceback and spatio-temporal fusion architecture. For energy-efficient attacker searching in MANETs, we also utilize small-world model. Our simulation analysis shows 79% of success rate in DoS attacker traceback with coarse-grained attack signature. In addition, with fine-grained attack signature, it shows 97% of success rate in DoS attacker traceback and 83% of success rate in DDoS attacker traceback. We also show that ATTENTION has robustness against node collusion and mobility.
Spectral Factorization, Whitening- and Estimation Filter -- Stability, Smoothness Properties and FIR Approximation Behavior
Venue: arXiv cs.IT 2005
Year: 2005

A Wiener filter can be interpreted as a cascade of a whitening- and an estimation filter. This paper gives a detailed investigates of the properties of these two filters. Then the practical consequences for the overall Wiener filter are ascertained. It is shown that if the given spectral densities are smooth (Hoelder continuous) functions, the resulting Wiener filter will always be stable and can be approximated arbitrarily well by a finite impulse response (FIR) filter. Moreover, the smoothness of the spectral densities characterizes how fast the FIR filter approximates the desired filter characteristic. If on the other hand the spectral densities are continuous but not smooth enough, the resulting Wiener filter may not be stable.
Terminated LDPC Convolutional Codes with Thresholds Close to Capacity
Venue: arXiv cs.IT 2005
Year: 2005

An ensemble of LDPC convolutional codes with parity-check matrices composed of permutation matrices is considered. The convergence of the iterative belief propagation based decoder for terminated convolutional codes in the ensemble is analyzed for binary-input output-symmetric memoryless channels using density evolution techniques. We observe that the structured irregularity in the Tanner graph of the codes leads to significantly better thresholds when compared to corresponding LDPC block codes.
Channel combining and splitting for cutoff rate improvement
Venue: arXiv cs.IT 2005
Year: 2005

The cutoff rate $R_0(W)$ of a discrete memoryless channel (DMC) $W$ is often used as a figure of merit, alongside the channel capacity $C(W)$. Given a channel $W$ consisting of two possibly correlated subchannels $W_1$, $W_2$, the capacity function always satisfies $C(W_1)+C(W_2) \le C(W)$, while there are examples for which $R_0(W_1)+R_0(W_2) > R_0(W)$. This fact that cutoff rate can be ``created'' by channel splitting was noticed by Massey in his study of an optical modulation system modeled as a $M$'ary erasure channel. This paper demonstrates that similar gains in cutoff rate can be achieved for general DMC's by methods of channel combining and splitting. Relation of the proposed method to Pinsker's early work on cutoff rate improvement and to Imai-Hirakawa multi-level coding are also discussed.
Energy Optimal Data Propagation in Wireless Sensor Networks
Venue: arXiv cs.DC 2005
Year: 2005

We propose an algorithm which produces a randomized strategy reaching optimal data propagation in wireless sensor networks (WSN).In [6] and [8], an energy balanced solution is sought using an approximation algorithm. Our algorithm improves by (a) when an energy-balanced solution does not exist, it still finds an optimal solution (whereas previous algorithms did not consider this case and provide no useful solution) (b) instead of being an approximation algorithm, it finds the exact solution in one pass. We also provide a rigorous proof of the optimality of our solution.
Sensing Capacity for Markov Random Fields
Venue: arXiv cs.IT 2005
Year: 2005

This paper computes the sensing capacity of a sensor network, with sensors of limited range, sensing a two-dimensional Markov random field, by modeling the sensing operation as an encoder. Sensor observations are dependent across sensors, and the sensor network output across different states of the environment is neither identically nor independently distributed. Using a random coding argument, based on the theory of types, we prove a lower bound on the sensing capacity of the network, which characterizes the ability of the sensor network to distinguish among environments with Markov structure, to within a desired accuracy.
On the Performance of Turbo Codes in Quasi-Static Fading Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we investigate in detail the performance of turbo codes in quasi-static fading channels both with and without antenna diversity. First, we develop a simple and accurate analytic technique to evaluate the performance of turbo codes in quasi-static fading channels. The proposed analytic technique relates the frame error rate of a turbo code to the iterative decoder convergence threshold, rather than to the turbo code distance spectrum. Subsequently, we compare the performance of various turbo codes in quasi-static fading channels. We show that, in contrast to the situation in the AWGN channel, turbo codes with different interleaver sizes or turbo codes based on RSC codes with different constraint lengths and generator polynomials exhibit identical performance. Moreover, we also compare the performance of turbo codes and convolutional codes in quasi-static fading channels under the condition of identical decoding complexity. In particular, we show that turbo codes do not outperform convolutional codes in quasi-static fading channels with no antenna diversity; and that turbo codes only outperform convolutional codes in quasi-static fading channels with antenna diversity.
MAP estimation via agreement on (hyper)trees: Message-passing and linear programming
Venue: arXiv cs.IT 2005
Year: 2005

We develop and analyze methods for computing provably optimal {\em maximum a posteriori} (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: (a) a {\em tree-relaxed linear program} (LP), which is derived from the Lagrangian dual of the upper bounds; and (b) a {\em tree-reweighted max-product message-passing algorithm} that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem, and a reweighted form of the max-product (min-sum) message-passing algorithm.
ZEUS - A Domain-Oriented Fact Comparison Based Authentication Protocol
Venue: arXiv cs.CR 2005
Year: 2005

In this paper, facts existing in different domains are explored, which are comparable by their end result. Properties of various domains and the facts that are part of such a unit are also presented, examples of comparison and methods of usage as means of zero-knowledge protocols are given, finally a zero-knowledge protocol based on afore-mentioned concept is given.
Search Process and Probabilistic Bifix Approach
Venue: arXiv cs.IT 2005
Year: 2005

An analytical approach to a search process is a mathematical prerequisite for digital synchronization acquisition analysis and optimization. A search is performed for an arbitrary set of sequences within random but not equiprobable L-ary data. This paper derives in detail an expression for probability distribution function, from which other statistical parameters - expected value and variance - can be obtained. The probabilistic nature of (cross-) bifix indicators is shown and application examples are outlined, ranging beyond the usual telecommunication field.
Investigations of Process Damping Forces in Metal Cutting
Venue: arXiv cs.CE 2005
Year: 2005

Using finite element software developed for metal cutting by Third Wave Systems we investigate the forces involved in chatter, a self-sustained oscillation of the cutting tool. The phenomena is decomposed into a vibrating tool cutting a flat surface work piece, and motionless tool cutting a work piece with a wavy surface. While cutting the wavy surface, the shearplane was seen to oscillate in advance of the oscillation of the depth of cut, as were the cutting, thrust, and shear plane forces. The vibrating tool was used to investigate process damping through the interaction of the relief face of the tool and the workpiece. Crushing forces are isolated and compared to the contact length between the tool and workpiece. We found that the wavelength dependence of the forces depended on the relative size of the wavelength to the length of the relief face of the tool. The results indicate that the damping force from crushing will be proportional to the cutting speed for short tools, and inversely proportional for long tools.
Relations between semantic security and indistinguishability against cpa, non-adaptive cca and adaptive cca in comparison based framework
Venue: arXiv cs.CR 2005
Year: 2005

In this paper we try to unify the frameworks of definitions of semantic security, indistinguishability and non-malleability by defining semantic security in comparison based framework. This facilitates the study of relations among these goals against different attack models and makes the proof of the equivalence of semantic security and indistinguishability easier and more understandable. Besides, our proof of the equivalence of semantic security and indistinguishability does not need any intermediate goals such as non devidability to change the definition framework.
Unified Theory of Source Coding: Part I -- Two Terminal Problems
Venue: arXiv cs.IT 2005
Year: 2005

Since the publication of Shannon's theory of one terminal source coding, a number of interesting extensions have been derived by researchers such as Slepian-Wolf, Wyner, Ahlswede-Körner, Wyner-Ziv and Berger-Yeung. Specifically, the achievable rate or rate-distortion region has been described by a first order information-theoretic functional of the source statistics in each of the above cases. At the same time several problems have also remained unsolved. Notable two terminal examples include the joint distortion problem, where both sources are reconstructed under a combined distortion criterion, as well as the partial side information problem, where one source is reconstructed under a distortion criterion using information about the other (side information) available at a certain rate (partially). In this paper we solve both of these open problems. Specifically, we give an infinite order description of the achievable rate-distortion region in each case. In our analysis we set the above problems in a general framework and formulate a unified methodology that solves not only the problems at hand but any two terminal problem with noncooperative encoding. The key to such unification is held by a fundamental source coding principle which we derive by extending the typicality arguments of Shannon and Wyner-Ziv. Finally, we demonstrate the expansive scope of our technique by re-deriving known coding theorems. We shall observe that our infinite order descriptions simplify to the expected first order in the known special cases.
Point Process Models of 1/f Noise and Internet Traffic
Venue: arXiv cs.NI 2005
Year: 2005

We present a simple model reproducing the long-range autocorrelations and the power spectrum of the web traffic. The model assumes the traffic as Poisson flow of files with size distributed according to the power-law. In this model the long-range autocorrelations are independent of the network properties as well as of inter-packet time distribution.
COMODI: Architecture for a Component-Based Scientific Computing System
Venue: arXiv cs.CE 2005
Year: 2005

The COmputational MODule Integrator (COMODI) is an initiative aiming at a component based framework, component developer tool and component repository for scientific computing. We identify the main ingredients to a solution that would be sufficiently appealing to scientists and engineers to consider alternatives to their deeply rooted programming traditions. The overall structure of the complete solution is sketched with special emphasis on the Component Developer Tool standing at the basis of COMODI.
NP-hardness of the cluster minimization problem revisited
Venue: arXiv cs.CC 2005
Year: 2005

The computational complexity of the "cluster minimization problem" is revisited [L. T. Wille and J. Vennik, J. Phys. A 18, L419 (1985)]. It is argued that the original NP-hardness proof does not apply to pairwise potentials of physical interest, such as those that depend on the geometric distance between the particles. A geometric analog of the original problem is formulated, and a new proof for such potentials is provided by polynomial time transformation from the independent set problem for unit disk graphs. Limitations of this formulation are pointed out, and new subproblems that bear more direct consequences to the numerical study of clusters are suggested.
Achievable Rates for Pattern Recognition
Venue: arXiv cs.IT 2005
Year: 2005

Biological and machine pattern recognition systems face a common challenge: Given sensory data about an unknown object, classify the object by comparing the sensory data with a library of internal representations stored in memory. In many cases of interest, the number of patterns to be discriminated and the richness of the raw data force recognition systems to internally represent memory and sensory information in a compressed format. However, these representations must preserve enough information to accommodate the variability and complexity of the environment, or else recognition will be unreliable. Thus, there is an intrinsic tradeoff between the amount of resources devoted to data representation and the complexity of the environment in which a recognition system may reliably operate. In this paper we describe a general mathematical model for pattern recognition systems subject to resource constraints, and show how the aforementioned resource-complexity tradeoff can be characterized in terms of three rates related to number of bits available for representing memory and sensory data, and the number of patterns populating a given statistical environment. We prove single-letter information theoretic bounds governing the achievable rates, and illustrate the theory by analyzing the elementary cases where the pattern data is either binary or Gaussian.