OpenRaiser/Intern-Atlas huggingface dataset:
Secret Key Agreement by Soft-decision of Signals in Gaussian Maurer's Model
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of secret key agreement in Gaussian Maurer's Model. In Gaussian Maurer's model, legitimate receivers, Alice and Bob, and a wire-tapper, Eve, receive signals randomly generated by a satellite through three independent memoryless Gaussian channels respectively. Then Alice and Bob generate a common secret key from their received signals. In this model, we propose a protocol for generating a common secret key by using the result of soft-decision of Alice and Bob's received signals. Then, we calculate a lower bound on the secret key rate in our proposed protocol. As a result of comparison with the protocol that only uses hard-decision, we found that the higher rate is obtained by using our protocol.
The Capacity Of Two Way Relay Channel
Venue: arXiv cs.IT 2008
Year: 2008

This paper investigates the capacity of a wireless two way relay channel in which two end nodes exchange information via a relay node. The capacity is defined in the information-theoretic sense as the maximum information exchange rate between the two end nodes. We give an upper bound of the capacity by applying the cut-set theorem. We prove that this upper bound can be approached in low SNR region using "separated" multiple access for uplinks from the end nodes to the relay in which the data from the end nodes are individually decoded at the relay; and network-coding broadcast for downlinks from the relay to the end nodes in which the relay mixes the information from end nodes before forwarding. We further prove that the capacity is approachable in high SNR region using physical-layer network coding (PNC) multiple access for uplinks, and network-coding broadcast for downlinks. From our proof and observations, we conjecture that the upper bound may be achieved with PNC in all SNR regions.
Optimization Approach for Detecting the Critical Data on a Database
Venue: arXiv cs.DB 2008
Year: 2008

Through purposeful introduction of malicious transactions (tracking transactions) into randomly select nodes of a (database) graph, soiled and clean segments are identified. Soiled and clean measures corresponding those segments are then computed. These measures are used to repose the problem of critical database elements detection as an optimization problem over the graph. This method is universally applicable over a large class of graphs (including directed, weighted, disconnected, cyclic) that occur in several contexts of databases. A generalization argument is presented which extends the critical data problem to abstract settings.
Stability and Throughput of Buffered Aloha with Backoff
Venue: arXiv cs.NI 2008
Year: 2008

This paper studies the buffered Aloha with K-exponential backoff collision resolution algorithms. The buffered Aloha network is modeled as a multi-queue single-server system. We adopt a widely used approach in packet switching systems to decompose the multi-queue system into independent first-in-first-out (FIFO) queues, which are hinged together by the probability of success of head-of-line (HOL) packets. A unified method is devised to tackle the stability and throughput problems of K-exponential backoff with any cutoff phase K. For networks with a finite number of nodes, we show that the K-exponential backoff is stable if the retransmission factor is properly chosen from the stable region. The maximum stable throughput is derived and demonstrated via examples of geometric retransmission (K=1) and exponential backoff (K=infinity). For networks with an infinite number of nodes, we show that geometric retransmission is unstable, and the stable network throughput of exponential backoff can only be achieved at the cost of potential unbounded delay in each input queue. Furthermore, we address the stability issue of the systems at the undesired stable point. All analytical results presented in this paper are verified and confirmed by simulations.
On generic frequency decomposition. Part 1: vectorial decomposition
Venue: arXiv cs.NA 2008
Year: 2008

The famous Fourier theorem states that, under some restrictions, any periodic function (or real world signal) can be obtained as a sum of sinusoids, and hence, a technique exists for decomposing a signal into its sinusoidal components. From this theory an entire branch of research has flourished: from the Short-Time or Windowed Fourier Transform to the Wavelets, the Frames, and lately the Generic Frequency Analysis. The aim of this paper is to take the Frequency Analysis a step further. It will be shown that keeping the same reconstruction algorithm as the Fourier Theorem but changing to a new computing method for the analysis phase allows the generalization of the Fourier Theorem to a large class of nonorthogonal bases. New methods and algorithms can be employed in function decomposition on such generic bases. It will be shown that these algorithms are a generalization of the Fourier analysis, i.e. they are reduced to the familiar Fourier tools when using orthogonal bases. The differences between this tool and the wavelets and frames theories will be discussed. Examples of analysis and reconstruction of functions using the given algorithms and nonorthogonal bases will be given. In this first part the focus will be on vectorial decomposition, while the second part will be on phased decomposition. The phased decomposition thanks to a single function basis has many interesting consequences and applications.
Towards Usage-based Impact Metrics: - First Results from the MESUR Project
Venue: arXiv cs.DL 2008
Year: 2008

Scholarly usage data holds the potential to be used as a tool to study the dynamics of scholarship in real time, and to form the basis for the definition of novel metrics of scholarly impact. However, the formal groundwork to reliably and validly exploit usage data is lacking, and the exact nature, meaning and applicability of usage-based metrics is poorly understood. The MESUR project funded by the Andrew W. Mellon Foundation constitutes a systematic effort to define, validate and cross-validate a range of usage-based metrics of scholarly impact. MESUR has collected nearly 1 billion usage events as well as all associated bibliographic and citation data from significant publishers, aggregators and institutional consortia to construct a large-scale usage data reference set. This paper describes some major challenges related to aggregating and processing usage data, and discusses preliminary results obtained from analyzing the MESUR reference data set. The results confirm the intrinsic value of scholarly usage data, and support the feasibility of reliable and valid usage-based metrics of scholarly impact.
On the inner and outer bounds for 2-receiver discrete memoryless broadcast channels
Venue: arXiv cs.IT 2008
Year: 2008

We study the best known general inner bound[MAR '79] and outer bound[N-EG'07] for the capacity region of the two user discrete memory less channel. We prove that a seemingly stronger outer bound is identical to a weaker form of the outer bound that was also presented in [N-EG'07]. We are able to further express the best outer bound in a form that is computable, i.e. there are bounds on the cardinalities of the auxiliary random variables. The inner and outer bounds coincide for all channels for which the capacity region is known and it is not known whether the regions described by these bounds are same or different. We present a channel, where assuming a certain conjecture backed by simulations and partial theoretical results, one can show that the bounds are different.
Hardware In The Loop Simulator in UAV Rapid Development Life Cycle
Venue: arXiv cs.RO 2008
Year: 2008

Field trial is very critical and high risk in autonomous UAV development life cycle. Hardware in the loop (HIL) simulation is a computer simulation that has the ability to simulate UAV flight characteristic, sensor modeling and actuator modeling while communicating in real time with the UAV autopilot hardware. HIL simulation can be used to test the UAV autopilot hardware reliability, test the closed loop performance of the overall system and tuning the control parameter. By rigorous testing in the HIL simulator, the risk in the field trial can be minimized.
Minimum-energy broadcast in random-grid ad-hoc networks: approximation and distributed algorithms
Venue: arXiv cs.DS 2008
Year: 2008

The Min Energy broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min energy broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the $n$ points of a $\sqrt n \times \sqrt n$ square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. By using information-theoretic arguments, we prove a lower bound $(1-ε) \frac nπ$ on the energy cost of any feasible solution for this problem. Then, we provide an efficient solution of energy cost not larger than $1.1204 \frac nπ$. Finally, we present a fully-distributed protocol that constructs a broadcast range assignment of energy cost not larger than $8n$,thus still yielding constant approximation. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is asymptotically optimal. The completion time of the protocol is only an $O(\log n)$ factor slower than the optimum. The approximation quality of our distributed solution is also experimentally evaluated. All bounds hold with probability at least $1-1/n^{Θ(1)}$.
Network Coding Capacity of Random Wireless Networks under a SINR Model
Venue: arXiv cs.IT 2008
Year: 2008

Previous work on network coding capacity for random wired and wireless networks have focused on the case where the capacities of links in the network are independent. In this paper, we consider a more realistic model, where wireless networks are modelled by random geometric graphs with interference and noise. In this model, the capacities of links are not independent. By employing coupling and martingale methods, we show that, under mild conditions, the network coding capacity for random wireless networks still exhibits a concentration behavior around the mean value of the minimum cut.
On the Capacity Bounds of Undirected Networks
Venue: arXiv cs.IT 2008
Year: 2008

In this work we improve on the bounds presented by Li&Li for network coding gain in the undirected case. A tightened bound for the undirected multicast problem with three terminals is derived. An interesting result shows that with fractional routing, routing throughput can achieve at least 75% of the coding throughput. A tighter bound for the general multicast problem with any number of terminals shows that coding gain is strictly less than 2. Our derived bound depends on the number of terminals in the multicast network and approaches 2 for arbitrarily large number of terminals.
The Complexity of Coverage
Venue: arXiv cs.PL 2008
Year: 2008

We study the problem of generating a test sequence that achieves maximal coverage for a reactive system under test. We formulate the problem as a repeated game between the tester and the system, where the system state space is partitioned according to some coverage criterion and the objective of the tester is to maximize the set of partitions (or coverage goals) visited during the game. We show the complexity of the maximal coverage problem for non-deterministic systems is PSPACE-complete, but is NP-complete for deterministic systems. For the special case of non-deterministic systems with a re-initializing ``reset'' action, which represent running a new test input on a re-initialized system, we show that the complexity is again co-NP-complete. Our proof technique for reset games uses randomized testing strategies that circumvent the exponentially large memory requirement in the deterministic case.
Rateless Coding for MIMO Block Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper the performance limits and design principles of rateless codes over fading channels are studied. The diversity-multiplexing tradeoff (DMT) is used to analyze the system performance for all possible transmission rates. It is revealed from the analysis that the design of such rateless codes follows the design principle of approximately universal codes for parallel multiple-input multiple-output (MIMO) channels, in which each sub-channel is a MIMO channel. More specifically, it is shown that for a single-input single-output (SISO) channel, the previously developed permutation codes of unit length for parallel channels having rate LR can be transformed directly into rateless codes of length L having multiple rate levels (R, 2R, . . ., LR), to achieve the DMT performance limit.
Wavelet Based Iterative Learning Control with Fuzzy PD Feedback for Position Tracking of A Pneumatic Servo System
Venue: arXiv cs.RO 2008
Year: 2008

In this paper, a wavelet-based iterative learning control (WILC) scheme with Fuzzy PD feedback is presented for a pneumatic control system with nonsmooth nonlinearities and uncertain parameters. The wavelet transform is employed to extract the learnable dynamics from measured output signal before it can be used to update the control profile. The wavelet transform is adopted to decompose the original signal into many low-resolution signals that contain the learnable and unlearnable parts. The desired control profile is then compared with the learnable part of the transformed signal. Thus, the effects from unlearnable dynamics on the controlled system can be attenuated by a Fuzzy PD feedback controller. As for the rules of Fuzzy PD controller in the feedback loop, a genetic algorithm (GA) is employed to search for the inference rules of optimization. A proportional-valve controlled pneumatic cylinder actuator system is used as the control target for simulation. Simulation results have shown a much-improved positiontracking performance.
Analysis of Stability, Response and LQR Controller Design of a Small Scale Helicopter Dynamics
Venue: arXiv cs.RO 2008
Year: 2008

This paper presents how to use feedback controller with helicopter dynamics state space model. A simplified analysis is presented for controller design using LQR of small scale helicopters for axial and forward flights. Our approach is simple and gives the basic understanding about how to develop controller for solving the stability of linear helicopter flight dynamics.
SimDialog: A visual game dialog editor
Venue: arXiv cs.HC 2008
Year: 2008

SimDialog is a visual editor for dialog in computer games. This paper presents the design of SimDialog, illustrating how script writers and non-programmers can easily create dialog for video games with complex branching structures and dynamic response characteristics. The system creates dialog as a directed graph. This allows for play using the dialog with a state-based cause and effect system that controls selection of non-player character responses and can provide a basic scoring mechanism for games.
Monotony in Service Orchestrations
Venue: arXiv cs.NI 2008
Year: 2008

Web Service orchestrations are compositions of different Web Services to form a new service. The services called during the orchestration guarantee a given performance to the orchestrater, usually in the form of contracts. These contracts can be used by the orchestrater to deduce the contract it can offer to its own clients, by performing contract composition. An implicit assumption in contract based QoS management is: "the better the component services perform, the better the orchestration's performance will be". Thus, contract based QoS management for Web services orchestrations implicitly assumes monotony. In some orchestrations, however, monotony can be violated, i.e., the performance of the orchestration improves when the performance of a component service degrades. This is highly undesirable since it can render the process of contract composition inconsistent. In this paper we define monotony for orchestrations modelled by Colored Occurrence Nets (CO-nets) and we characterize the classes of monotonic orchestrations. We show that few orchestrations are indeed monotonic, mostly since latency can be traded for quality of data. We also propose a sound refinement of monotony, called conditional monotony, which forbids this kind of cheating and show that conditional monotony is widely satisfied by orchestrations. This finding leads to reconsidering the way SLAs should be formulated.
Communicating the sum of sources over a network
Venue: arXiv cs.IT 2008
Year: 2008

We consider a network (that is capable of network coding) with a set of sources and terminals, where each terminal is interested in recovering the sum of the sources. Considering directed acyclic graphs with unit capacity edges and independent, unit-entropy sources, we show the rate region when (a) there are two sources and $n$ terminals, and (b) $n$ sources and two terminals. In these cases as long as there exists at least one path from each source to each terminal we demonstrate that there exists a valid assignment of coding vectors to the edges such that the terminals can recover the sum of the sources.
Morphing of Triangular Meshes in Shape Space
Venue: arXiv cs.CG 2008
Year: 2008

We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space $\mathcal{S}$. For triangulated 3D polygons, we prove that interpolating linearly in this shape space corresponds to the most isometric morph in $\mathbb{R}^3$. We then extend this shape space to arbitrary triangulations in 3D using a heuristic approach and show the practical use of the approach using experiments. Furthermore, we discuss a modified shape space that is useful for isometric skeleton morphing. All of the newly presented approaches solve the morphing problem without the need to solve a minimization problem.
Capacity of The Discrete-Time Non-Coherent Memoryless Gaussian Channels at Low SNR
Venue: arXiv cs.IT 2008
Year: 2008

We address the capacity of a discrete-time memoryless Gaussian channel, where the channel state information (CSI) is neither available at the transmitter nor at the receiver. The optimal capacity-achieving input distribution at low signal-to-noise ratio (SNR) is precisely characterized, and the exact capacity of a non-coherent channel is derived. The derived relations allow to better understanding the capacity of non-coherent channels at low SNR. Then, we compute the non-coherence penalty and give a more precise characterization of the sub-linear term in SNR. Finally, in order to get more insight on how the optimal input varies with SNR, upper and lower bounds on the non-zero mass point location of the capacity-achieving input are given.
On Distributed Function Computation in Structure-Free Random Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider in-network computation of MAX in a structure-free random multihop wireless network. Nodes do not know their relative or absolute locations and use the Aloha MAC protocol. For one-shot computation, we describe a protocol in which the MAX value becomes available at the origin in $O(\sqrt{n/\log n})$ slots with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of $Ω(1/(\log^2 n)).$
Prediction and Mitigation of Crush Conditions in Emergency Evacuations
Venue: arXiv cs.CE 2008
Year: 2008

Several simulation environments exist for the simulation of large-scale evacuations of buildings, ships, or other enclosed spaces. These offer sophisticated tools for the study of human behaviour, the recreation of environmental factors such as fire or smoke, and the inclusion of architectural or structural features, such as elevators, pillars and exits. Although such simulation environments can provide insights into crowd behaviour, they lack the ability to examine potentially dangerous forces building up within a crowd. These are commonly referred to as crush conditions, and are a common cause of death in emergency evacuations. In this paper, we describe a methodology for the prediction and mitigation of crush conditions. The paper is organised as follows. We first establish the need for such a model, defining the main factors that lead to crush conditions, and describing several exemplar case studies. We then examine current methods for studying crush, and describe their limitations. From this, we develop a three-stage hybrid approach, using a combination of techniques. We conclude with a brief discussion of the potential benefits of our approach.
Network-based consensus averaging with general noisy channels
Venue: arXiv cs.IT 2008
Year: 2008

This paper focuses on the consensus averaging problem on graphs under general noisy channels. We study a particular class of distributed consensus algorithms based on damped updates, and using the ordinary differential equation method, we prove that the updates converge almost surely to exact consensus for finite variance noise. Our analysis applies to various types of stochastic disturbances, including errors in parameters, transmission noise, and quantization noise. Under a suitable stability condition, we prove that the error is asymptotically Gaussian, and we show how the asymptotic covariance is specified by the graph Laplacian. For additive parameter noise, we show how the scaling of the asymptotic MSE is controlled by the spectral gap of the Laplacian.
Decoding Generalized Concatenated Codes Using Interleaved Reed-Solomon Codes
Venue: arXiv cs.IT 2008
Year: 2008

Generalized Concatenated codes are a code construction consisting of a number of outer codes whose code symbols are protected by an inner code. As outer codes, we assume the most frequently used Reed-Solomon codes; as inner code, we assume some linear block code which can be decoded up to half its minimum distance. Decoding up to half the minimum distance of Generalized Concatenated codes is classically achieved by the Blokh-Zyablov-Dumer algorithm, which iteratively decodes by first using the inner decoder to get an estimate of the outer code words and then using an outer error/erasure decoder with a varying number of erasures determined by a set of pre-calculated thresholds. In this paper, a modified version of the Blokh-Zyablov-Dumer algorithm is proposed, which exploits the fact that a number of outer Reed-Solomon codes with average minimum distance d can be grouped into one single Interleaved Reed-Solomon code which can be decoded beyond d/2. This allows to skip a number of decoding iterations on the one hand and to reduce the complexity of each decoding iteration significantly - while maintaining the decoding performance - on the other.
The Gaussian MAC with Conferencing Encoders
Venue: arXiv cs.IT 2008
Year: 2008

We derive the capacity region of the Gaussian version of Willems's two-user MAC with conferencing encoders. This setting differs from the classical MAC in that, prior to each transmission block, the two transmitters can communicate with each other over noise-free bit-pipes of given capacities. The derivation requires a new technique for proving the optimality of Gaussian input distributions in certain mutual information maximizations under a Markov constraint. We also consider a Costa-type extension of the Gaussian MAC with conferencing encoders. In this extension, the channel can be described as a two-user MAC with Gaussian noise and Gaussian interference where the interference is known non-causally to the encoders but not to the decoder. We show that as in Costa's setting the interference sequence can be perfectly canceled, i.e., that the capacity region without interference can be achieved.