OpenRaiser/Intern-Atlas huggingface dataset:
Green Modulation in Proactive Wireless Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

Due to unique characteristics of sensor nodes, choosing energy-efficient modulation scheme with low-complexity implementation (refereed to as green modulation) is a critical factor in the physical layer of Wireless Sensor Networks (WSNs). This paper presents (to the best of our knowledge) the first in-depth analysis of energy efficiency of various modulation schemes using realistic models in IEEE 802.15.4 standard and present state-of-the art technology, to find the best scheme in a proactive WSN over Rayleigh and Rician flat-fading channel models with path-loss. For this purpose, we describe the system model according to a pre-determined time-based process in practical sensor nodes. The present analysis also includes the effect of bandwidth and active mode duration on energy efficiency of popular modulation designs in the pass-band and Ultra-WideBand (UWB) categories. Experimental results show that among various pass-band and UWB modulation schemes, Non-Coherent M-ary Frequency Shift Keying (NC-MFSK) with small order of $M$ and On-Off Keying (OOK) have significant energy saving compared to other schemes for short range scenarios, and could be considered as realistic candidates in WSNs. In addition, NC-MFSK and OOK have the advantage of less complexity and cost in implementation than the other schemes.
A Local Search Modeling for Constrained Optimum Paths Problems (Extended Abstract)
Venue: arXiv cs.AI 2009
Year: 2009

Constrained Optimum Path (COP) problems appear in many real-life applications, especially on communication networks. Some of these problems have been considered and solved by specific techniques which are usually difficult to extend. In this paper, we introduce a novel local search modeling for solving some COPs by local search. The modeling features the compositionality, modularity, reuse and strengthens the benefits of Constrained-Based Local Search. We also apply the modeling to the edge-disjoint paths problem (EDP). We show that side constraints can easily be added in the model. Computational results show the significance of the approach.
Violating the Ingleton Inequality with Finite Groups
Venue: arXiv cs.IT 2009
Year: 2009

It is well known that there is a one-to-one correspondence between the entropy vector of a collection of n random variables and a certain group-characterizable vector obtained from a finite group and n of its subgroups. However, if one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al that linear network codes cannot achieve capacity in general network coding problems (since linear network codes form an abelian group). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S_5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2,p) with primes p > 3, i.e., the projective group of 2 by 2 nonsingular matrices with entries in F_p. This family of groups is therefore a good candidate for constructing network codes more powerful than linear network codes.
On the Sample Complexity of Compressed Counting
Venue: arXiv cs.DS 2009
Year: 2009

Compressed Counting (CC), based on maximally skewed stable random projections, was recently proposed for estimating the p-th frequency moments of data streams. The case p->1 is extremely useful for estimating Shannon entropy of data streams. In this study, we provide a very simple algorithm based on the sample minimum estimator and prove a much improved sample complexity bound, compared to prior results.
Convergence Time Evaluation of Algorithms in MANETs
Venue: arXiv cs.DS 2009
Year: 2009

Since the advent of wireless communication, the need for mobile ad hoc networks has been growing exponentially. This has opened up a Pandoras Box of algorithms for dealing with mobile ad hoc networks, or MANETs, as they are generally referred to. Most attempts made at evaluating these algorithms so far have focused on parameters such as throughput, packet delivery ratio, overhead etc. An analysis of the convergence times of these algorithms is still an open issue. The work carried out fills this gap by evaluating the algorithms on the basis of convergence time. Algorithms for MANETs can be classified into three categories: reactive, proactive, and hybrid protocols. In this project, we compare the convergence times of representative algorithms in each category, namely Ad hoc On Demand Distance Vector (AODV) reactive, Destination Sequence Distance Vector protocol (DSDV) proactive, and Temporally Ordered Routing Algorithm (TORA) hybrid. The algorithm performances are compared by simulating them in ns2. Tcl is used to conduct the simulations, while perl is used to extract data from the simulation output and calculate convergence time. The design of the experiments carried on is documented using Unified modeling Language. Also, a user interface is created using perl, which enables the user to either run a desired simulation and measure convergence time, or measure the convergence time of a simulation that has been run earlier.
Length of the Shortest Word in the Intersection of Regular Languages
Venue: arXiv cs.FL 2009
Year: 2009

In this note, we give a construction that provides a tight lower bound of mn-1 for the length of the shortest word in the intersection of two regular languages with state complexities m and n.
Local and global approaches of affinity propagation clustering for large scale data
Venue: arXiv cs.LG 2009
Year: 2009

Recently a new clustering algorithm called 'affinity propagation' (AP) has been proposed, which efficiently clustered sparsely related data by passing messages between data points. However, we want to cluster large scale data where the similarities are not sparse in many cases. This paper presents two variants of AP for grouping large scale data with a dense similarity matrix. The local approach is partition affinity propagation (PAP) and the global method is landmark affinity propagation (LAP). PAP passes messages in the subsets of data first and then merges them as the number of initial step of iterations; it can effectively reduce the number of iterations of clustering. LAP passes messages between the landmark data points first and then clusters non-landmark data points; it is a large global approximation method to speed up clustering. Experiments are conducted on many datasets, such as random data points, manifold subspaces, images of faces and Chinese calligraphy, and the results demonstrate that the two approaches are feasible and practicable.
A zonotopic framework for functional abstractions
Venue: arXiv cs.LO 2009
Year: 2009

This article formalizes an abstraction of input/output relations, based on parameterized zonotopes, which we call affine sets. We describe the abstract transfer functions and prove their correctness, which allows the generation of accurate numerical invariants. Other applications range from compositional reasoning to proofs of user-defined complex invariants and test case generation.
Towards Participatory Design of Multi-agent Approach to Transport Demands
Venue: arXiv cs.MA 2009
Year: 2009

The design of multi-agent based simulations (MABS) is up to now mainly done in laboratories and based on designers' understanding of the activities to be simulated. Domain experts have little chance to directly validate agent behaviors. To fill this gap, we are investigating participatory methods of design, which allow users to participate in the design the pickup and delivery problem (PDP) in the taxi planning problem. In this paper, we present a participatory process for designing new socio-technical architectures to afford the taxi dispatch for this transportation system. The proposed dispatch architecture attempts to increase passenger satisfaction more globally, by concurrently dispatching multiple taxis to the same number of passengers in the same geographical region, and vis-avis human driver and dispatcher satisfaction.
Can Component/Service-Based Systems Be Proved Correct?
Venue: arXiv cs.SE 2009
Year: 2009

Component-oriented and service-oriented approaches have gained a strong enthusiasm in industries and academia with a particular interest for service-oriented approaches. A component is a software entity with given functionalities, made available by a provider, and used to build other application within which it is integrated. The service concept and its use in web-based application development have a huge impact on reuse practices. Accordingly a considerable part of software architectures is influenced; these architectures are moving towards service-oriented architectures. Therefore applications (re)use services that are available elsewhere and many applications interact, without knowing each other, using services available via service servers and their published interfaces and functionalities. Industries propose, through various consortium, languages, technologies and standards. More academic works are also undertaken concerning semantics and formalisation of components and service-based systems. We consider here both streams of works in order to raise research concerns that will help in building quality software. Are there new challenging problems with respect to service-based software construction? Besides, what are the links and the advances compared to distributed systems?
A Branch and Cut Algorithm for the Halfspace Depth Problem
Venue: arXiv cs.CG 2009
Year: 2009

The concept of \emph{data depth} in non-parametric multivariate descriptive statistics is the generalization of the univariate rank method to multivariate data. \emph{Halfspace depth} is a measure of data depth. Given a set $S$ of points and a point $p$, the halfspace depth (or rank) of $p$ is defined as the minimum number of points of $S$ contained in any closed halfspace with $p$ on its boundary. Computing halfspace depth is NP-hard, and it is equivalent to the Maximum Feasible Subsystem problem. In this paper a mixed integer program is formulated with the big-$M$ method for the halfspace depth problem. We suggest a branch and cut algorithm for these integer programs. In this algorithm, Chinneck's heuristic algorithm is used to find an upper bound and a related technique based on sensitivity analysis is used for branching. Irreducible Infeasible Subsystem (IIS) hitting set cuts are applied. We also suggest a binary search algorithm which may be more numerically stable. The algorithms are implemented with the BCP framework from the \textbf{COIN-OR} project.
Congestion Control in the Internet by Employing a Ratio dependent Plant Herbivore Carnivorous Model
Venue: arXiv cs.NI 2009
Year: 2009

The demand for Internet based services has exploded over the last decade. Many organizations use the Internet and particularly the World Wide Web as their primary medium for communication and business. This phenomenal growth has dramatically increased the performance requirements for the Internet. To have a high performance Internet, a good congestion control system is essential for it. The current work proposes that the congestion control in the Internet can be inspired from the population control tactics of the nature. Toward this idea, each flow (W) in the network is viewed as a species whose population size is congestion window size of the flow. By this assumption, congestion control problem is redefined as population control of flow species. This paper defines a three trophic food chain analogy in congestion control area, and gives a ratio dependent model to control population size of W species within this plant herbivore carnivorous food chain. Simulation results show that this model achieves fair bandwidth allocation, high utilization and small queue size. It does not maintain any per flow state in routers and have few computational loads per packet, which makes it scalable.
Interference Mitigation Using Uplink Power Control for Two-Tier Femtocell Networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes two interference mitigation strategies that adjust the maximum transmit power of femtocell users to suppress the cross-tier interference at a macrocell base station (BS). The open-loop and the closed-loop control suppress the cross-tier interference less than a fixed threshold and an adaptive threshold based on the noise and interference (NI) level at the macrocell BS, respectively. Simulation results show that both schemes effectively compensate the uplink throughput degradation of the macrocell BS due to the cross-tier interference and that the closed-loop control provides better femtocell throughput than the open-loop control at a minimal cost of macrocell throughput.
State of the Art Review for Applying Computational Intelligence and Machine Learning Techniques to Portfolio Optimisation
Venue: arXiv cs.CE 2009
Year: 2009

Computational techniques have shown much promise in the field of Finance, owing to their ability to extract sense out of dauntingly complex systems. This paper reviews the most promising of these techniques, from traditional computational intelligence methods to their machine learning siblings, with particular view to their application in optimising the management of a portfolio of financial instruments. The current state of the art is assessed, and prospective further work is assessed and recommended
Utility of Beamforming Strategies for Secrecy in Multiuser MIMO Wiretap Channels
Venue: arXiv cs.IT 2009
Year: 2009

This paper examines linear beamforming methods for secure communications in a multiuser wiretap channel with a single transmitter, multiple legitimate receivers, and a single eavesdropper, where all nodes are equipped with multiple antennas. No information regarding the eavesdropper is presumed at the transmitter, and we examine both the broadcast MIMO downlink with independent information, and the multicast MIMO downlink with common information for all legitimate receivers. In both cases the information signal is transmitted with just enough power to guarantee a certain SINR at the desired receivers, while the remainder of the power is used to broadcast artificial noise. The artificial interference selectively degrades the passive eavesdropper's signal while remaining orthogonal to the desired receivers. We analyze the confidentiality provided by zero-forcing and optimal minimum-power beamforming designs for the broadcast channel, and optimal minimum-MSE beamformers for the multicast channel. Numerical simulations for the relative SINR and BER performance of the eavesdropper demonstrate the effectiveness of the proposed physical-layer security schemes.
Effectiveness and Limitations of Statistical Spam Filters
Venue: arXiv cs.LG 2009
Year: 2009

In this paper we discuss the techniques involved in the design of the famous statistical spam filters that include Naive Bayes, Term Frequency-Inverse Document Frequency, K-Nearest Neighbor, Support Vector Machine, and Bayes Additive Regression Tree. We compare these techniques with each other in terms of accuracy, recall, precision, etc. Further, we discuss the effectiveness and limitations of statistical filters in filtering out various types of spam from legitimate e-mails.
Polynomially Correlated Knapsack is NP-complete
Venue: arXiv cs.CC 2009
Year: 2009

0-1 Knapsack is a fundamental NP-complete problem. In this article we prove that it remains NP-complete even when the weights of the objects in the packing constraints and their values in the objective function satisfy specific stringent conditions: the values are integral powers of the weights of the objects.
An Agent Based Classification Model
Venue: arXiv cs.AI 2009
Year: 2009

The major function of this model is to access the UCI Wisconsin Breast Can- cer data-set[1] and classify the data items into two categories, which are normal and anomalous. This kind of classifi cation can be referred as anomaly detection, which discriminates anomalous behaviour from normal behaviour in computer systems. One popular solution for anomaly detection is Artifi cial Immune Sys- tems (AIS). AIS are adaptive systems inspired by theoretical immunology and observed immune functions, principles and models which are applied to prob- lem solving. The Dendritic Cell Algorithm (DCA)[2] is an AIS algorithm that is developed specifi cally for anomaly detection. It has been successfully applied to intrusion detection in computer security. It is believed that agent-based mod- elling is an ideal approach for implementing AIS, as intelligent agents could be the perfect representations of immune entities in AIS. This model evaluates the feasibility of re-implementing the DCA in an agent-based simulation environ- ment called AnyLogic, where the immune entities in the DCA are represented by intelligent agents. If this model can be successfully implemented, it makes it possible to implement more complicated and adaptive AIS models in the agent-based simulation environment.
An Idiotypic Immune Network as a Short Term Learning Architecture for Mobile Robots
Venue: arXiv cs.AI 2009
Year: 2009

A combined Short-Term Learning (STL) and Long-Term Learning (LTL) approach to solving mobile robot navigation problems is presented and tested in both real and simulated environments. The LTL consists of rapid simulations that use a Genetic Algorithm to derive diverse sets of behaviours. These sets are then transferred to an idiotypic Artificial Immune System (AIS), which forms the STL phase, and the system is said to be seeded. The combined LTL-STL approach is compared with using STL only, and with using a handdesigned controller. In addition, the STL phase is tested when the idiotypic mechanism is turned off. The results provide substantial evidence that the best option is the seeded idiotypic system, i.e. the architecture that merges LTL with an idiotypic AIS for the STL. They also show that structurally different environments can be used for the two phases without compromising transferability
Towards a Semantic Preservation System
Venue: arXiv cs.DL 2009
Year: 2009

Preserving access to file content requires preserving not just bits but also meaningful logical structures. The ongoing development of the Data Format Description Language (DFDL) is a completely general standard that addresses this need. The Defuddle parser is a generic parser that can use DFDL-style format descriptions to extract logical structures from ASCII or binary files written in those formats. DFDL and Defuddle provide a preservation capability that has minimal format-specific software and cleanly separates issues related to bits, formats, and logical content. Such a system has the potential to greatly reduce overall system development and maintenance costs as well as the per-file-format costs for long term preservation.
Testing Distribution Identity Efficiently
Venue: arXiv cs.DS 2009
Year: 2009

We consider the problem of testing distribution identity. Given a sequence of independent samples from an unknown distribution on a domain of size n, the goal is to check if the unknown distribution approximately equals a known distribution on the same domain. While Batu, Fortnow, Fischer, Kumar, Rubinfeld, and White (FOCS 2001) proved that the sample complexity of the problem is O~(sqrt(n) * poly(1/epsilon)), the running time of their tester is much higher: O(n) + O~(sqrt(n) * poly(1/epsilon)). We modify their tester to achieve a running time of O~(sqrt(n) * poly(1/epsilon)).
A Fuzzy Petri Nets Model for Computing With Words
Venue: arXiv cs.AI 2009
Year: 2009

Motivated by Zadeh's paradigm of computing with words rather than numbers, several formal models of computing with words have recently been proposed. These models are based on automata and thus are not well-suited for concurrent computing. In this paper, we incorporate the well-known model of concurrent computing, Petri nets, together with fuzzy set theory and thereby establish a concurrency model of computing with words--fuzzy Petri nets for computing with words (FPNCWs). The new feature of such fuzzy Petri nets is that the labels of transitions are some special words modeled by fuzzy sets. By employing the methodology of fuzzy reasoning, we give a faithful extension of an FPNCW which makes it possible for computing with more words. The language expressiveness of the two formal models of computing with words, fuzzy automata for computing with words and FPNCWs, is compared as well. A few small examples are provided to illustrate the theoretical development.
Improved Approximation of Linear Threshold Functions
Venue: arXiv cs.CC 2009
Year: 2009

We prove two main results on how arbitrary linear threshold functions $f(x) = \sign(w\cdot x - θ)$ over the $n$-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every $n$-variable threshold function $f$ is $\eps$-close to a threshold function depending only on $\Inf(f)^2 \cdot \poly(1/\eps)$ many variables, where $\Inf(f)$ denotes the total influence or average sensitivity of $f.$ This is an exponential sharpening of Friedgut's well-known theorem \cite{Friedgut:98}, which states that every Boolean function $f$ is $\eps$-close to a function depending only on $2^{O(\Inf(f)/\eps)}$ many variables, for the case of threshold functions. We complement this upper bound by showing that $Ω(\Inf(f)^2 + 1/ε^2)$ many variables are required for $ε$-approximating threshold functions. Our second result is a proof that every $n$-variable threshold function is $\eps$-close to a threshold function with integer weights at most $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2/3})}.$ This is a significant improvement, in the dependence on the error parameter $\eps$, on an earlier result of \cite{Servedio:07cc} which gave a $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2})}$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original \cite{Servedio:07cc} result, and extends to give low-weight approximators for threshold functions under a range of probability distributions beyond just the uniform distribution.
A Fault-tolerant Structure for Reliable Multi-core Systems Based on Hardware-Software Co-design
Venue: arXiv cs.AR 2009
Year: 2009

To cope with the soft errors and make full use of the multi-core system, this paper gives an efficient fault-tolerant hardware and software co-designed architecture for multi-core systems. And with a not large number of test patterns, it will use less than 33% hardware resources compared with the traditional hardware redundancy (TMR) and it will take less than 50% time compared with the traditional software redundancy (time redundant).Therefore, it will be a good choice for the fault-tolerant architecture for the future high-reliable multi-core systems.
Dynamics of the Orthoglide parallel robot
Venue: arXiv cs.RO 2009
Year: 2009

Recursive matrix relations for kinematics and dynamics of the Orthoglide parallel robot having three concurrent prismatic actuators are established in this paper. These are arranged according to the Cartesian coordinate system with fixed orientation, which means that the actuating directions are normal to each other. Three identical legs connecting to the moving platform are located on three planes being perpendicular to each other too. Knowing the position and the translation motion of the platform, we develop the inverse kinematics problem and determine the position, velocity and acceleration of each element of the robot. Further, the principle of virtual work is used in the inverse dynamic problem. Some matrix equations offer iterative expressions and graphs for the input forces and the powers of the three actuators.