OpenRaiser/Intern-Atlas huggingface dataset:
De-randomizing Shannon: The Design and Analysis of a Capacity-Achieving Rateless Code
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents an analysis of spinal codes, a class of rateless codes proposed recently. We prove that spinal codes achieve Shannon capacity for the binary symmetric channel (BSC) and the additive white Gaussian noise (AWGN) channel with an efficient polynomial-time encoder and decoder. They are the first rateless codes with proofs of these properties for BSC and AWGN. The key idea in the spinal code is the sequential application of a hash function over the message bits. The sequential structure of the code turns out to be crucial for efficient decoding. Moreover, counter to the wisdom of having an expander structure in good codes, we show that the spinal code, despite its sequential structure, achieves capacity. The pseudo-randomness provided by a hash function suffices for this purpose. Our proof introduces a variant of Gallager's result characterizing the error exponent of random codes for any memoryless channel. We present a novel application of these error-exponent results within the framework of an efficient sequential code. The application of a hash function over the message bits provides a methodical and effective way to de-randomize Shannon's random codebook construction.
Synergy-Based Hand Pose Sensing: Optimal Glove Design
Venue: arXiv cs.RO 2012
Year: 2012

In this paper we study the problem of improving human hand pose sensing device performance by exploiting the knowledge on how humans most frequently use their hands in grasping tasks. In a companion paper we studied the problem of maximizing the reconstruction accuracy of the hand pose from partial and noisy data provided by any given pose sensing device (a sensorized "glove") taking into account statistical a priori information. In this paper we consider the dual problem of how to design pose sensing devices, i.e. how and where to place sensors on a glove, to get maximum information about the actual hand posture. We study the continuous case, whereas individual sensing elements in the glove measure a linear combination of joint angles, the discrete case, whereas each measure corresponds to a single joint angle, and the most general hybrid case, whereas both continuous and discrete sensing elements are available. The objective is to provide, for given a priori information and fixed number of measurements, the optimal design minimizing in average the reconstruction error. Solutions relying on the geometrical synergy definition as well as gradient flow-based techniques are provided. Simulations of reconstruction performance show the effectiveness of the proposed optimal design.
New Technique for Proposing Network's Topology using GPS and GIS
Venue: arXiv cs.DC 2012
Year: 2012

The problem of proposed topology for network comes when using Prim's algorithm with default distance (unrealistic distances) between network's nodes and don't care about the lakes, high hills, buildings, etc. This problem will cause incorrect estimations for cost (budget) of requirements like the media (optic fibre) and the number or type of Access-points, regenerator, Optic Amplifier, etc. This paper proposed a new technique of implementing Prim's algorithm to obtain realistic topology using realistic distances between network's nodes via Global Positioning System GPS and Geographic Information Systems GIS packages. Applying the new technique on academic institutes network of Erbil city from view of media (optic fibre) shows that there is disability in cost (budget) of the media which is needed (nearly) 4 times if implement default Prim's algorithm (don't using GPS & GIS) base on unrealistic distances between the nodes.
Learning in Hierarchical Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

We study a social network consisting of agents organized as a hierarchical M-ary rooted tree, common in enterprise and military organizational structures. The goal is to aggregate information to solve a binary hypothesis testing problem. Each agent at a leaf of the tree, and only such an agent, makes a direct measurement of the underlying true hypothesis. The leaf agent then makes a decision and sends it to its supervising agent, at the next level of the tree. Each supervising agent aggregates the decisions from the M members of its group, produces a summary message, and sends it to its supervisor at the next level, and so on. Ultimately, the agent at the root of the tree makes an overall decision. We derive upper and lower bounds for the Type I and II error probabilities associated with this decision with respect to the number of leaf agents, which in turn characterize the converge rates of the Type I, Type II, and total error probabilities. We also provide a message-passing scheme involving non-binary message alphabets and characterize the exponent of the error probability with respect to the message alphabet size.
New Method of Measuring TCP Performance of IP Network using Bio-computing
Venue: arXiv cs.NI 2012
Year: 2012

The measurement of performance of Internet Protocol IP network can be done by Transmission Control Protocol TCP because it guarantees send data from one end of the connection actually gets to the other end and in the same order it was send, otherwise an error is reported. There are several methods to measure the performance of TCP among these methods genetic algorithms, neural network, data mining etc, all these methods have weakness and can't reach to correct measure of TCP performance. This paper proposed a new method of measuring TCP performance for real time IP network using Biocomputing, especially molecular calculation because it provides wisdom results and it can exploit all facilities of phylogentic analysis. Applying the new method at real time on Biological Kurdish Messenger BIOKM model designed to measure the TCP performance in two types of protocols File Transfer Protocol FTP and Internet Relay Chat Daemon IRCD. This application gives very close result of TCP performance comparing with TCP performance which obtains from Little's law using same model (BIOKM), i.e. the different percentage of utilization (Busy or traffic industry) and the idle time which are obtained from a new method base on Bio-computing comparing with Little's law was (nearly) 0.13%. KEYWORDS Bio-computing, TCP performance, Phylogenetic tree, Hybridized Model (Normalized), FTP, IRCD
Frequent Patterns mining in time-sensitive Data Stream
Venue: arXiv cs.DB 2012
Year: 2012

Mining frequent itemsets through static Databases has been extensively studied and used and is always considered a highly challenging task. For this reason it is interesting to extend it to data streams field. In the streaming case, the frequent patterns' mining has much more information to track and much greater complexity to manage. Infrequent items can become frequent later on and hence cannot be ignored. The output structure needs to be dynamically incremented to reflect the evolution of itemset frequencies over time. In this paper, we study this problem and specifically the methodology of mining time-sensitive data streams. We tried to improve an existing algorithm by increasing the temporal accuracy and discarding the out-of-date data by adding a new concept called the "Shaking Point". We presented as well some experiments illustrating the time and space required.
A Linear Circuit Model For Social Influence Analysis
Venue: arXiv cs.SI 2012
Year: 2012

Understanding the behaviors of information propagation is essential for the effective exploitation of social influence in social networks. However, few existing influence models are both tractable and efficient for describing the information propagation process and quantitatively measuring social influence. To this end, in this paper, we develop a linear social influence model, named Circuit due to its close relation to the circuit network. Based on the predefined four axioms of social influence, we first demonstrate that our model can efficiently measure the influence strength between any pair of nodes. Along this line, an upper bound of the node(s)' influence is identified for potential use, e.g., reducing the search space. Furthermore, we provide the physical implication of the Circuit model and also a deep analysis of its relationships with the existing methods, such as PageRank. Then, we propose that the Circuit model provides a natural solution to the problems of computing each single node's authority and finding a set of nodes for social influence maximization. At last, the effectiveness of the proposed model is evaluated on the real-world data. The extensive experimental results demonstrate that Circuit model consistently outperforms the state-of-the-art methods and can greatly alleviate the computation burden of the influence maximization problem.
A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model
Venue: arXiv cs.DC 2012
Year: 2012

A fundamental problem in wireless networks is the \emph{minimum spanning tree} (MST) problem: given a set $V$ of wireless nodes, compute a spanning tree $T$, so that the total cost of $T$ is minimized. In recent years, there has been a lot of interest in the physical interference model based on SINR constraints. Distributed algorithms are especially challenging in the SINR model, because of the non-locality of the model. In this paper, we develop a fast distributed approximation algorithm for MST construction in an SINR based distributed computing model. For an $n$-node network, our algorithm's running time is $O(D\log{n}+μ\log{n})$ and produces a spanning tree whose cost is within $O(\log n)$ times the optimal (MST cost), where $D$ denotes the diameter of the disk graph obtained by using the maximum possible transmission range, and $μ=\log{\frac{d_{max}}{d_{min}}}$ denotes the "distance diversity" w.r.t. the largest and smallest distances between two nodes. (When $\frac{d_{max}}{d_{min}}$ is $n$-polynomial, $μ= O(\log n)$.) Our algorithm's running time is essentially optimal (upto a logarithmic factor), since computing {\em any} spanning tree takes $Ω(D)$ time; thus our algorithm produces a low cost spanning tree in time only a logarithmic factor more than the time to compute a spanning tree. The distributed scheduling complexity of the spanning tree resulted from our algorithm is $O(μ\log n)$. Our algorithmic design techniques can be useful in designing efficient distributed algorithms for related "global" problems in wireless networks in the SINR model.
Cumulative Step-size Adaptation on Linear Functions: Technical Report
Venue: arXiv cs.LG 2012
Year: 2012

The CSA-ES is an Evolution Strategy with Cumulative Step size Adaptation, where the step size is adapted measuring the length of a so-called cumulative path. The cumulative path is a combination of the previous steps realized by the algorithm, where the importance of each step decreases with time. This article studies the CSA-ES on composites of strictly increasing with affine linear functions through the investigation of its underlying Markov chains. Rigorous results on the change and the variation of the step size are derived with and without cumulation. The step-size diverges geometrically fast in most cases. Furthermore, the influence of the cumulation parameter is studied.
MACS: An Agent-Based Memetic Multiobjective Optimization Algorithm Applied to Space Trajectory Design
Venue: arXiv cs.CE 2012
Year: 2012

This paper presents an algorithm for multiobjective optimization that blends together a number of heuristics. A population of agents combines heuristics that aim at exploring the search space both globally and in a neighborhood of each agent. These heuristics are complemented with a combination of a local and global archive. The novel agent- based algorithm is tested at first on a set of standard problems and then on three specific problems in space trajectory design. Its performance is compared against a number of state-of-the-art multiobjective optimisation algorithms that use the Pareto dominance as selection criterion: NSGA-II, PAES, MOPSO, MTS. The results demonstrate that the agent-based search can identify parts of the Pareto set that the other algorithms were not able to capture. Furthermore, convergence is statistically better although the variance of the results is in some cases higher.
Evidence-Based Robust Design of Deflection Actions for Near Earth Objects
Venue: arXiv cs.CE 2012
Year: 2012

This paper presents a novel approach to the robust design of deflection actions for Near Earth Objects (NEO). In particular, the case of deflection by means of Solar-pumped Laser ablation is studied here in detail. The basic idea behind Laser ablation is that of inducing a sublimation of the NEO surface, which produces a low thrust thereby slowly deviating the asteroid from its initial Earth threatening trajectory. This work investigates the integrated design of the Space-based Laser system and the deflection action generated by laser ablation under uncertainty. The integrated design is formulated as a multi-objective optimisation problem in which the deviation is maximised and the total system mass is minimised. Both the model for the estimation of the thrust produced by surface laser ablation and the spacecraft system model are assumed to be affected by epistemic uncertainties (partial or complete lack of knowledge). Evidence Theory is used to quantify these uncertainties and introduce them in the optimisation process. The propagation of the trajectory of the NEO under the laser-ablation action is performed with a novel approach based on an approximated analytical solution of Gauss' Variational Equations. An example of design of the deflection of asteroid Apophis with a swarm of spacecraft is presented.
A weighted combination similarity measure for mobility patterns in wireless networks
Venue: arXiv cs.AI 2012
Year: 2012

The similarity between trajectory patterns in clustering has played an important role in discovering movement behaviour of different groups of mobile objects. Several approaches have been proposed to measure the similarity between sequences in trajectory data. Most of these measures are based on Euclidean space or on spatial network and some of them have been concerned with temporal aspect or ordering types. However, they are not appropriate to characteristics of spatiotemporal mobility patterns in wireless networks. In this paper, we propose a new similarity measure for mobility patterns in cellular space of wireless network. The framework for constructing our measure is composed of two phases as follows. First, we present formal definitions to capture mathematically two spatial and temporal similarity measures for mobility patterns. And then, we define the total similarity measure by means of a weighted combination of these similarities. The truth of the partial and total similarity measures are proved in mathematics. Furthermore, instead of the time interval or ordering, our work makes use of the timestamp at which two mobility patterns share the same cell. A case study is also described to give a comparison of the combination measure with other ones.
Analysis study of time synchronization protocols in wireless sensor networks
Venue: arXiv cs.NI 2012
Year: 2012

One of the main pervasive problems Wireless Sensor Networks (WSN) encounter is to maintain flawless communication sharing and cooperative processing between sensors via radio links to ensure a reliable treatment of information. Many applications based on these WSNs consider local clocks at each sensor node that need to be synchronized to a common notion of time. In this context, the majority of previous researches were focused on the study of protocols, and algorithms that address these issues in order to resolve synchronization problems. Previous fforts and empirical studies in wireless sensor network (WSN) proposed several solutions (algorithms). The focus of this this paper is to examine and evaluate the most important synchronization algorithms based on the positions of various quantitative and qualitative synchronization protocols for energy-efficient information processing and routing in WSNs.
Distance Based Asynchronous Recovery Approach in Mobile Computing Environment
Venue: arXiv cs.DB 2012
Year: 2012

A mobile computing system is a distributed system in which at least one of the processes is mobile. They are constrained by lack of stable storage, low network bandwidth, mobility, frequent disconnection and limited battery life. Checkpointing is one of the commonly used techniques to provide fault tolerance in mobile computing environment. In order to suit the mobile environment a distance based recovery scheme is proposed which is based on checkpointing and message logging. After the system recovers from failures, only the failed processes rollback and restart from their respective recent checkpoints, independent of the others. The salient feature of this scheme is to reduce the transfer and recovery cost. While the mobile host moves with in a specific range, recovery information is not moved and thus only be transferred nearby if the mobile host moves out of certain range.
Adaptive Sensing of Congested Spectrum Bands
Venue: arXiv cs.IT 2012
Year: 2012

Cognitive radios process their sensed information collectively in order to opportunistically identify and access under-utilized spectrum segments (spectrum holes). Due to the transient and rapidly-varying nature of the spectrum occupancy, the cognitive radios (secondary users) must be agile in identifying the spectrum holes in order to enhance their spectral efficiency. We propose a novel {\em adaptive} procedure to reinforce the agility of the secondary users for identifying {\em multiple} spectrum holes simultaneously over a wide spectrum band. This is accomplished by successively {\em exploring} the set of potential spectrum holes and {\em progressively} allocating the sensing resources to the most promising areas of the spectrum. Such exploration and resource allocation results in conservative spending of the sensing resources and translates into very agile spectrum monitoring. The proposed successive and adaptive sensing procedure is in contrast to the more conventional approaches that distribute the sampling resources equally over the entire spectrum. Besides improved agility, the adaptive procedure requires less-stringent constraints on the power of the primary users to guarantee that they remain distinguishable from the environment noise and renders more reliable spectrum hole detection.
Performance Analysis of Unsymmetrical trimmed median as detector on image noises and its Fpga implementation
Venue: arXiv cs.CV 2012
Year: 2012

This Paper Analyze the performance of Unsymmetrical trimmed median, which is used as detector for the detection of impulse noise, Gaussian noise and mixed noise is proposed. The proposed algorithm uses a fixed 3x3 window for the increasing noise densities. The pixels in the current window are arranged in sorting order using a improved snake like sorting algorithm with reduced comparator. The processed pixel is checked for the occurrence of outliers, if the absolute difference between processed pixels is greater than fixed threshold. Under high noise densities the processed pixel is also noisy hence the median is checked using the above procedure. if found true then the pixel is considered as noisy hence the corrupted pixel is replaced by the median of the current processing window. If median is also noisy then replace the corrupted pixel with unsymmetrical trimmed median else if the pixel is termed uncorrupted and left unaltered. The proposed algorithm (PA) is tested on varying detail images for various noises. The proposed algorithm effectively removes the high density fixed value impulse noise, low density random valued impulse noise, low density Gaussian noise and lower proportion of mixed noise. The proposed algorithm is targeted on Xc3e5000-5fg900 FPGA using Xilinx 7.1 compiler version which requires less number of slices, optimum speed and low power when compared to the other median finding architectures.
An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem
Venue: arXiv cs.AI 2012
Year: 2012

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.
Flexible Data Dissemination Strategy for Effective Cache Consistency in Mobile Wireless Communication Networks
Venue: arXiv cs.NI 2012
Year: 2012

In mobile wireless communication network, caching data items at the mobile clients is important to reduce the data access delay. However, efficient cache invalidation strategies are used to ensure the consistency between the data in the cache of mobile clients and at the database server. Servers use invalidation reports (IRs) to inform the mobile clients about data item updates. This paper proposes and implements a multicast based strategy to maintain cache consistency in mobile environment using AVI as the cache invalidation scheme. The proposed algorithm is outlined as follows - To resolve a query, the mobile client searches its cache to check if its data is valid. If yes, then query is answered, otherwise the client queries the DTA (Dynamic Transmitting Agent) for latest updates and the query is answered. If DTA doesn't have the latest updates, it gets it from the server. So, the main idea here is that DTA will be multicasting updates to the clients and hence the clients need not uplink to the server individually, thus preserving the network bandwidth. The scenario of simulation is developed in Java. The results demonstrate that the traffic generated in the proposed multicast model is simplified and it also retains cache consistency when compared to the existing methods that used broadcast strategy.
Fuzzy Knowledge Representation, Learning and Optimization with Bayesian Analysis in Fuzzy Semantic Networks
Venue: arXiv cs.AI 2012
Year: 2012

This paper presents a method of optimization, based on both Bayesian Analysis technical and Gallois Lattice, of a Fuzzy Semantic Networks. The technical System we use learn by interpreting an unknown word using the links created between this new word and known words. The main link is provided by the context of the query. When novice's query is confused with an unknown verb (goal) applied to a known noun denoting either an object in the ideal user's Network or an object in the user's Network, the system infer that this new verb corresponds to one of the known goal. With the learning of new words in natural language as the interpretation, which was produced in agreement with the user, the system improves its representation scheme at each experiment with a new user and, in addition, takes advantage of previous discussions with users. The semantic Net of user objects thus obtained by these kinds of learning is not always optimal because some relationships between couple of user objects can be generalized and others suppressed according to values of forces that characterize them. Indeed, to simplify the obtained Net, we propose to proceed to an inductive Bayesian analysis, on the Net obtained from Gallois lattice. The objective of this analysis can be seen as an operation of filtering of the obtained descriptive graph.