OpenRaiser/Intern-Atlas huggingface dataset:
Reinforcement Learning Based on Active Learning Method
Venue: arXiv cs.AI 2010
Year: 2010

In this paper, a new reinforcement learning approach is proposed which is based on a powerful concept named Active Learning Method (ALM) in modeling. ALM expresses any multi-input-single-output system as a fuzzy combination of some single-input-singleoutput systems. The proposed method is an actor-critic system similar to Generalized Approximate Reasoning based Intelligent Control (GARIC) structure to adapt the ALM by delayed reinforcement signals. Our system uses Temporal Difference (TD) learning to model the behavior of useful actions of a control system. The goodness of an action is modeled on Reward- Penalty-Plane. IDS planes will be updated according to this plane. It is shown that the system can learn with a predefined fuzzy system or without it (through random actions).
Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
Venue: arXiv cs.IT 2010
Year: 2010

The paper considers gossip distributed estimation of a (static) distributed random field (a.k.a., large scale unknown parameter vector) observed by sparsely interconnected sensors, each of which only observes a small fraction of the field. We consider linear distributed estimators whose structure combines the information \emph{flow} among sensors (the \emph{consensus} term resulting from the local gossiping exchange among sensors when they are able to communicate) and the information \emph{gathering} measured by the sensors (the \emph{sensing} or \emph{innovations} term.) This leads to mixed time scale algorithms--one time scale associated with the consensus and the other with the innovations. The paper establishes a distributed observability condition (global observability plus mean connectedness) under which the distributed estimates are consistent and asymptotically normal. We introduce the distributed notion equivalent to the (centralized) Fisher information rate, which is a bound on the mean square error reduction rate of any distributed estimator; we show that under the appropriate modeling and structural network communication conditions (gossip protocol) the distributed gossip estimator attains this distributed Fisher information rate, asymptotically achieving the performance of the optimal centralized estimator. Finally, we study the behavior of the distributed gossip estimator when the measurements fade (noise variance grows) with time; in particular, we consider the maximum rate at which the noise variance can grow and still the distributed estimator being consistent, by showing that, as long as the centralized estimator is consistent, the distributed estimator remains consistent.
Fundamentals of Mathematical Theory of Emotional Robots
Venue: arXiv cs.RO 2010
Year: 2010

In this book we introduce a mathematically formalized concept of emotion, robot's education and other psychological parameters of intelligent robots. We also introduce unitless coefficients characterizing an emotional memory of a robot. Besides, the effect of a robot's memory upon its emotional behavior is studied, and theorems defining fellowship and conflicts in groups of robots are proved. Also unitless parameters describing emotional states of those groups are introduced, and a rule of making alternative (binary) decisions based on emotional selection is given. We introduce a concept of equivalent educational process for robots and a concept of efficiency coefficient of an educational process, and suggest an algorithm of emotional contacts within a group of robots. And generally, we present and describe a model of a virtual reality with emotional robots. The book is meant for mathematical modeling specialists and emotional robot software developers.
Asymptotically Optimal Randomized Rumor Spreading
Venue: arXiv cs.DS 2010
Year: 2010

We propose a new protocol solving the fundamental problem of disseminating a piece of information to all members of a group of n players. It builds upon the classical randomized rumor spreading protocol and several extensions. The main achievements are the following: Our protocol spreads the rumor to all other nodes in the asymptotically optimal time of (1 + o(1)) \log_2 n. The whole process can be implemented in a way such that only O(n f(n)) calls are made, where f(n)= ω(1) can be arbitrary. In contrast to other protocols suggested in the literature, our algorithm only uses push operations, i.e., only informed nodes take active actions in the network. To the best of our knowledge, this is the first randomized push algorithm that achieves an asymptotically optimal running time.
Pushing BitTorrent Locality to the Limit
Venue: arXiv cs.NI 2010
Year: 2010

Peer-to-peer (P2P) locality has recently raised a lot of interest in the community. Indeed, whereas P2P content distribution enables financial savings for the content providers, it dramatically increases the traffic on inter-ISP links. To solve this issue, the idea to keep a fraction of the P2P traffic local to each ISP was introduced a few years ago. Since then, P2P solutions exploiting locality have been introduced. However, several fundamental issues on locality still need to be explored. In particular, how far can we push locality, and what is, at the scale of the Internet, the reduction of traffic that can be achieved with locality? In this paper, we perform extensive experiments on a controlled environment with up to 10,000 BitTorrent clients to evaluate the impact of high locality on inter-ISP links traffic and peers download completion time. We introduce two simple mechanisms that make high locality possible in challenging scenarios and we show that we save up to several orders of magnitude inter-ISP traffic compared to traditional locality without adversely impacting peers download completion time. In addition, we crawled 214,443 torrents representing 6,113,224 unique peers spread among 9,605 ASes. We show that whereas the torrents we crawled generated 11.6 petabytes of inter-ISP traffic, our locality policy implemented for all torrents could have reduced the global inter-ISP traffic by up to 40%.
Mobility and Handoff Management in Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

With the increasing demands for new data and real-time services, wireless networks should support calls with different traffic characteristics and different Quality of Service (QoS)guarantees. In addition, various wireless technologies and networks exist currently that can satisfy different needs and requirements of mobile users. Since these different wireless networks act as complementary to each other in terms of their capabilities and suitability for different applications, integration of these networks will enable the mobile users to be always connected to the best available access network depending on their requirements. This integration of heterogeneous networks will, however, lead to heterogeneities in access technologies and network protocols. To meet the requirements of mobile users under this heterogeneous environment, a common infrastructure to interconnect multiple access networks will be needed. In this chapter, the design issues of a number of mobility management schemes have been presented. Each of these schemes utilizes IP-based technologies to enable efficient roaming in heterogeneous network. Efficient handoff mechanisms are essential for ensuring seamless connectivity and uninterrupted service delivery. A number of handoff schemes in a heterogeneous networking environment are also presented in this chapter.
Evaluation of Lifetime Bounds of Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper we estimate lifetime bounds of a network of motes which communicate with each other using IEEE 802.15.4 standard. Different frame structures of IEEE 802.15.4 along with CSMA/CA medium access mechanism are investigated to discover the overhead of channel acquisition, header and footer of data frame, and transfer reliability during packet transmission. This overhead makes the fixed component, and the data payload makes the incremental component of a linear equation to estimate the power consumed during every packet transmission. Finally we input this per-packet power consumption in a mathematical model which estimates the lower and upper bounds of routings in the network. We also implemented a series of measurements on CC2420 radio used in a wide range of sensor motes to find the fixed and incremental components, and finally the lifetime of a network composed of the motes using this radio.
On Secure Transmission over Parallel Relay Eavesdropper Channel
Venue: arXiv cs.IT 2010
Year: 2010

We study a four terminal parallel relay-eavesdropper channel which consists of multiple independent relay-eavesdropper channels as subchannels. For the discrete memoryless case, we establish inner and outer bounds on the rate-equivocation region. For each subchannel, secure transmission is obtained through one of the two coding schemes at the relay: decoding-and-forwarding the source message or confusing the eavesdropper through noise injection. The inner bound allows relay mode selection. For the Gaussian model we establish lower and upper bounds on the perfect secrecy rate. We show that the bounds meet in some special cases, including when the relay does not hear the source. We illustrate the analytical results through some numerical examples.
Static and dynamic characteristics of protein contact networks
Venue: arXiv cs.CE 2010
Year: 2010

The principles underlying protein folding remains one of Nature's puzzles with important practical consequences for Life. An approach that has gathered momentum since the late 1990's, looks at protein hetero-polymers and their folding process through the lens of complex network analysis. Consequently, there is now a body of empirical studies describing topological characteristics of protein macro-molecules through their contact networks and linking these topological characteristics to protein folding. The present paper is primarily a review of this rich area. But it delves deeper into certain aspects by emphasizing short-range and long-range links, and suggests unconventional places where "power-laws" may be lurking within protein contact networks. Further, it considers the dynamical view of protein contact networks. This closer scrutiny of protein contact networks raises new questions for further research, and identifies new regularities which may be useful to parameterize a network approach to protein folding. Preliminary experiments with such a model confirm that the regularities we identified cannot be easily reproduced through random effects. Indeed, the grand challenge of protein folding is to elucidate the process(es) which not only generates the specific and diverse linkage patterns of protein contact networks, but also reproduces the dynamic behavior of proteins as they fold. Keywords: network analysis, protein contact networks, protein folding
Pareto Optimal Solutions for Smoothed Analysts
Venue: arXiv cs.DS 2010
Year: 2010

Consider an optimization problem with $n$ binary variables and $d+1$ linear objective functions. Each valid solution $x \in \{0,1\}^n$ gives rise to an objective vector in $\R^{d+1}$, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in $n$. Unfortunately, the bound obtained had a rather bad dependence on $d$; roughly $n^{d^d}$. In this paper we show a significantly improved bound of $n^{2d}$. Our proof is based on analyzing two algorithms. The first algorithm, on input a Pareto optimal $x$, outputs a "testimony" containing clues about $x$'s objective vector, $x$'s coordinates, and the region of space $B$ in which $x$'s objective vector lies. The second algorithm can be regarded as a {\em speculative} execution of the first -- it can uniquely reconstruct $x$ from the testimony's clues and just \emph{some} of the probability space's outcomes. The remainder of the probability space's outcomes are just enough to bound the probability that $x$'s objective vector falls into the region $B$.
A network model with structured nodes
Venue: arXiv cs.SI 2010
Year: 2010

We present a network model in which words over a specific alphabet, called {\it structures}, are associated to each node and undirected edges are added depending on some distance between different structures. It is shown that this model can generate, without the use of preferential attachment or any other heuristic, networks with topological features similar to biological networks: power law degree distribution, clustering coefficient independent from the network size, etc. Specific biological networks ({\it C. Elegans} neural network and {\it E. Coli} protein-protein interaction network) are replicated using this model.
A Stable Explicit Scheme for Solving Inhomogeneous Constant Coefficients Differential Equation using Green's Function
Venue: arXiv cs.NA 2010
Year: 2010

A numerical explicit method to evaluates transient solutions of linear partial differential inhomogeneous equation with constant coefficients is proposed. A general form of the scheme for a specific linear inhomogeneous equation is shown. The method is applied to the wave equation and the diffuse equation and is investigated by simulating simple models. The numerical solutions of the proposed method show good agreement to the exact solutions. Comparing with explicit FDM, FDM shows the instability by the violation of CFL condition whereas the proposed method is always stable irrespective of any time step width.
Recursive Sketching For Frequency Moments
Venue: arXiv cs.DS 2010
Year: 2010

In a ground-breaking paper, Indyk and Woodruff (STOC 05) showed how to compute $F_k$ (for $k>2$) in space complexity $O(\mbox{\em poly-log}(n,m)\cdot n^{1-\frac2k})$, which is optimal up to (large) poly-logarithmic factors in $n$ and $m$, where $m$ is the length of the stream and $n$ is the upper bound on the number of distinct elements in a stream. The best known lower bound for large moments is $Ω(\log(n)n^{1-\frac2k})$. A follow-up work of Bhuvanagiri, Ganguly, Kesh and Saha (SODA 2006) reduced the poly-logarithmic factors of Indyk and Woodruff to $O(\log^2(m)\cdot (\log n+ \log m)\cdot n^{1-{2\over k}})$. Further reduction of poly-log factors has been an elusive goal since 2006, when Indyk and Woodruff method seemed to hit a natural "barrier." Using our simple recursive sketch, we provide a different yet simple approach to obtain a $O(\log(m)\log(nm)\cdot (\log\log n)^4\cdot n^{1-{2\over k}})$ algorithm for constant $ε$ (our bound is, in fact, somewhat stronger, where the $(\log\log n)$ term can be replaced by any constant number of $\log $ iterations instead of just two or three, thus approaching $log^*n$. Our bound also works for non-constant $ε$ (for details see the body of the paper). Further, our algorithm requires only $4$-wise independence, in contrast to existing methods that use pseudo-random generators for computing large frequency moments.
A Discrete Time Markov Chain Model for High Throughput Bidirectional Fano Decoders
Venue: arXiv cs.IT 2010
Year: 2010

The bidirectional Fano algorithm (BFA) can achieve at least two times decoding throughput compared to the conventional unidirectional Fano algorithm (UFA). In this paper, bidirectional Fano decoding is examined from the queuing theory perspective. A Discrete Time Markov Chain (DTMC) is employed to model the BFA decoder with a finite input buffer. The relationship between the input data rate, the input buffer size and the clock speed of the BFA decoder is established. The DTMC based modelling can be used in designing a high throughput parallel BFA decoding system. It is shown that there is a tradeoff between the number of BFA decoders and the input buffer size, and an optimal input buffer size can be chosen to minimize the hardware complexity for a target decoding throughput in designing a high throughput parallel BFA decoding system.
Multipath Parameter Estimation from OFDM Signals in Mobile Channels
Venue: arXiv cs.IT 2010
Year: 2010

We study multipath parameter estimation from orthogonal frequency division multiplex signals transmitted over doubly dispersive mobile radio channels. We are interested in cases where the transmission is long enough to suffer time selectivity, but short enough such that the time variation can be accurately modeled as depending only on per-tap linear phase variations due to Doppler effects. We therefore concentrate on the estimation of the complex gain, delay and Doppler offset of each tap of the multipath channel impulse response. We show that the frequency domain channel coefficients for an entire packet can be expressed as the superimposition of two-dimensional complex sinusoids. The maximum likelihood estimate requires solution of a multidimensional non-linear least squares problem, which is computationally infeasible in practice. We therefore propose a low complexity suboptimal solution based on iterative successive and parallel cancellation. First, initial delay/Doppler estimates are obtained via successive cancellation. These estimates are then refined using an iterative parallel cancellation procedure. We demonstrate via Monte Carlo simulations that the root mean squared error statistics of our estimator are very close to the Cramer-Rao lower bound of a single two-dimensional sinusoid in Gaussian noise.
Approximately Optimal Wireless Broadcasting
Venue: arXiv cs.IT 2010
Year: 2010

We study a wireless broadcast network, where a single source reliably communicates independent messages to multiple destinations, with the aid of relays and cooperation between destinations. The wireless nature of the medium is captured by the broadcast nature of transmissions as well as the superposition of all transmit signals plus independent Gaussian noise at the received signal at any radio. We propose a scheme that can achieve rate tuples within a constant gap away from the cut-set bound, where the constant is independent of channel coefficients and power constraints. The proposed scheme operates in two steps. The inner code, in which the relays perform a quantize-and-encode operation, is constructed by lifting a scheme designed for a corresponding discrete superposition network. The outer code is a Marton code for the non-Gaussian vector broadcast channel induced by the relaying scheme, and is constructed by adopting a ``receiver-centric'' viewpoint.
A Survey of System Security in Contactless Electronic Passports
Venue: arXiv cs.CR 2010
Year: 2010

A traditional paper-based passport contains a Machine- Readable Zone (MRZ) and a Visual Inspection Zone (VIZ). The MRZ has two lines of the holder's personal data, some document data, and verification characters encoded using the Optical Character Recognition font B (OCRB). The encoded data includes the holder's name, date of birth, and other identifying information for the holder or the document. The VIZ contains the holder's photo and signature, usually on the data page. However, the MRZ and VIZ can be easily duplicated with normal document reproduction technology to produce a fake passport which can pass traditional verification. Neither of these features actively verify the holder's identity; nor do they bind the holder's identity to the document. A passport also contains pages for stamps of visas and of country entry and exit dates, which can be easily altered to produce fake permissions and travel records. The electronic passport, supporting authentication using secure credentials on a tamper-resistant chip, is an attempt to improve on the security of the paper-based passport at minimum cost. This paper surveys the security mechanisms built into the firstgeneration of authentication mechanisms and compares them with second-generation passports. It analyzes and describes the cryptographic protocols used in Basic Access Control (BAC) and Extended Access Control (EAC).
A Trust Model Based on Service Classification in Mobile Services
Venue: arXiv cs.DC 2010
Year: 2010

Internet of Things (IoT) and B3G/4G communication are promoting the pervasive mobile services with its advanced features. However, security problems are also baffled the development. This paper proposes a trust model to protect the user's security. The billing or trust operator works as an agent to provide a trust authentication for all the service providers. The services are classified by sensitive value calculation. With the value, the user's trustiness for corresponding service can be obtained. For decision, three trust regions are divided, which is referred to three ranks: high, medium and low. The trust region tells the customer, with his calculated trust value, which rank he has got and which authentication methods should be used for access. Authentication history and penalty are also involved with reasons.
On the Energy Efficiency of LT Codes in Proactive Wireless Sensor Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents an in-depth analysis on the energy efficiency of Luby Transform (LT) codes with Frequency Shift Keying (FSK) modulation in a Wireless Sensor Network (WSN) over Rayleigh fading channels with pathloss. We describe a proactive system model according to a flexible duty-cycling mechanism utilized in practical sensor apparatus. The present analysis is based on realistic parameters including the effect of channel bandwidth used in the IEEE 802.15.4 standard, active mode duration and computation energy. A comprehensive analysis, supported by some simulation studies on the probability mass function of the LT code rate and coding gain, shows that among uncoded FSK and various classical channel coding schemes, the optimized LT coded FSK is the most energy-efficient scheme for distance d greater than the pre-determined threshold level d_T , where the optimization is performed over coding and modulation parameters. In addition, although the optimized uncoded FSK outperforms coded schemes for d < d_T , the energy gap between LT coded and uncoded FSK is negligible for d < d_T compared to the other coded schemes. These results come from the flexibility of the LT code to adjust its rate to suit instantaneous channel conditions, and suggest that LT codes are beneficial in practical low-power WSNs with dynamic position sensor nodes.