OpenRaiser/Intern-Atlas huggingface dataset:
Sensitive Ants in Solving the Generalized Vehicle Routing Problem
Venue: arXiv cs.AI 2012
Year: 2012

The idea of sensitivity in ant colony systems has been exploited in hybrid ant-based models with promising results for many combinatorial optimization problems. Heterogeneity is induced in the ant population by endowing individual ants with a certain level of sensitivity to the pheromone trail. The variable pheromone sensitivity within the same population of ants can potentially intensify the search while in the same time inducing diversity for the exploration of the environment. The performance of sensitive ant models is investigated for solving the generalized vehicle routing problem. Numerical results and comparisons are discussed and analysed with a focus on emphasizing any particular aspects and potential benefits related to hybrid ant-based models.
Distributed Pharaoh System for Network Routing
Venue: arXiv cs.AI 2012
Year: 2012

In this paper it is introduced a biobjective ant algorithm for constructing low cost routing networks. The new algorithm is called the Distributed Pharaoh System (DPS). DPS is based on AntNet algorithm. The algorithm is using Pharaoh Ant System (PAS) with an extra-exploration phase and a 'no-entry' condition in order to improve the solutions for the Low Cost Network Routing problem. Additionally it is used a cost model for overlay network construction that includes network traffic demands. The Pharaoh ants (Monomorium pharaonis) includes negative pheromones with signals concentrated at decision points where trails fork. The negative pheromones may complement positive pheromone or could help ants to escape from an unnecessarily long route to food that is being reinforced by attractive signals. Numerical experiments were made for a random 10-node network. The average node degree of the network tested was 4.0. The results are encouraging. The algorithm converges to the shortest path while converging on a low cost overlay routing network topology.
The Japanese Smart Grid Initiatives, Investments, and Collaborations
Venue: arXiv cs.SY 2012
Year: 2012

A smart grid delivers power around the country and has an intelligent monitoring system, which not only keeps track of all the energy coming in from diverse sources but also can detect where energy is needed through a two-way communication system that collects data about how and when consumers use power. It is safer in many ways, compared with the current one-directional power supply system that seems susceptible to either sabotage or natural disasters, including being more resistant to attack and power outages. In such an autonomic and advanced-grid environment, investing in a pilot study and knowing the nation readiness to adopt a smart grid absolves the government of complex intervention from any failure to bring Japan into the autonomic-grid environment. This paper looks closely into the concept of the Japanese government go green effort, the objective of which is to make Japan a leading nation in environmental and energy sustainability through green innovation, such as creating a low-carbon society and embracing the natural grid community. This paper paints a clearer conceptual picture of how Japan smart grid effort compares with that of the US.
Compression and Sieve: Reducing Communication in Parallel Breadth First Search on Distributed Memory Systems
Venue: arXiv cs.DC 2012
Year: 2012

For parallel breadth first search (BFS) algorithm on large-scale distributed memory systems, communication often costs significantly more than arithmetic and limits the scalability of the algorithm. In this paper we sufficiently reduce the communication cost in distributed BFS by compressing and sieving the messages. First, we leverage a bitmap compression algorithm to reduce the size of messages before communication. Second, we propose a novel distributed directory algorithm, cross directory, to sieve the redundant data in messages. Experiments on a 6,144-core SMP cluster show our algorithm outperforms the baseline implementation in Graph500 by 2.2 times, reduces its communication time by 79.0%, and achieves a performance rate of 12.1 GTEPS (billion edge visits per second)
An Efficient Group Key Management Using Code for Key Calculation for Simultaneous Join/Leave: CKCS
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents an efficient group key management protocol, CKCS (Code for Key Calculation in Simultaneous join/leave) for simultaneous join/leave in secure multicast. This protocol is based on logical key hierarchy. In this protocol, when new members join the group simultaneously, server sends only the group key for those new members. Then, current members and new members calculate the necessary keys by node codes and one-way hash function. A node code is a random number which is assigned to each key to help users calculate the necessary keys. Again, at leave, the server just sends the new group key to remaining members. The results show that CKCS reduces computational and communication overhead, and also message size in simultaneous join/leave.
Optimal Random Access and Random Spectrum Sensing for an Energy Harvesting Cognitive Radio
Venue: arXiv cs.NI 2012
Year: 2012

We consider a secondary user with energy harvesting capability. We design access schemes for the secondary user which incorporate random spectrum sensing and random access, and which make use of the primary automatic repeat request (ARQ) feedback. The sensing and access probabilities are obtained such that the secondary throughput is maximized under the constraints that both the primary and secondary queues are stable and that the primary queueing delay is kept lower than a specified value needed to guarantee a certain quality of service (QoS) for the primary user. We consider spectrum sensing errors and assume multipacket reception (MPR) capabilities. Numerical results are presented to show the enhanced performance of our proposed system over a random access system, and to demonstrate the benefit of leveraging the primary feedback.
Attraction-Based Receding Horizon Path Planning with Temporal Logic Constraints
Venue: arXiv cs.RO 2012
Year: 2012

Our goal in this paper is to plan the motion of a robot in a partitioned environment with dynamically changing, locally sensed rewards. We assume that arbitrary assumptions on the reward dynamics can be given. The robot aims to accomplish a high-level temporal logic surveillance mission and to locally optimize the collection of the rewards in the visited regions. These two objectives often conflict and only a compromise between them can be reached. We address this issue by taking into consideration a user-defined preference function that captures the trade-off between the importance of collecting high rewards and the importance of making progress towards a surveyed region. Our solution leverages ideas from the automata-based approach to model checking. We demonstrate the utilization and benefits of the suggested framework in an illustrative example.
Two for the Price of One: Lifting Separation Logic Assertions
Venue: arXiv cs.PL 2012
Year: 2012

Recently, data abstraction has been studied in the context of separation logic, with noticeable practical successes: the developed logics have enabled clean proofs of tricky challenging programs, such as subject-observer patterns, and they have become the basis of efficient verification tools for Java (jStar), C (VeriFast) and Hoare Type Theory (Ynot). In this paper, we give a new semantic analysis of such logic-based approaches using Reynolds's relational parametricity. The core of the analysis is our lifting theorems, which give a sound and complete condition for when a true implication between assertions in the standard interpretation entails that the same implication holds in a relational interpretation. Using these theorems, we provide an algorithm for identifying abstraction-respecting client-side proofs; the proofs ensure that clients cannot distinguish two appropriately-related module implementations.
Survey on Using GIS in Evacuation Planning
Venue: arXiv cs.CY 2012
Year: 2012

Natural crises form a big threat on environment; these crises mean the loss of enterprises and individuals, and therefore losses in the sum total of community development. Management to these crises is required through a crisis management plan to control the crises before, during, and after the event. One of the most needed things to consider during preparing the crisis management plan is preparing the evacuation plan in order to transfer people from the incident place to a safe place; this must be done quickly and carefully. Because of the geographic nature of the evacuation process, Geographical Information System (GIS) has been used widely and effectively for over 20 years in the field of crisis management in general and in evacuation planning in particular. This paper provides an overview about evacuation process and the basic concepts of GIS systems. The paper also demonstrates the importance of evacuation planning and how GIS systems used in other studies to assists in evacuation process.
M-ATTEMPT: A New Energy-Efficient Routing Protocol in Wireless Body Area Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper presents an energy efficient routing algorithm for heterogeneous Wireless Body Area Sensor Networks (WBASNs). A prototype is defined for employing heterogeneous sensors on human body. Direct communication is used for real-time traffic (critical data) and on-demand data while multi-hop communication is used for normal data delivery in this proposed routing algorithm. One of the prime challenges in WBASNs is sensing of heat generated by implanted sensor nodes. The proposed routing algorithm is thermal-aware which sense the link Hot-spot and routes the data away from these links. Continuous mobility of human body causes disconnection between previous established links. We introduce mobility support and energy-management to overcome the problem of disconnection due to continuous mobility of human body. MATLAB simulations of proposed routing algorithm are performed for lifetime and reliability in comparison with multi-hop communication. The results show that the proposed routing algorithm has less energy consumption and more reliable as compared to multi-hop communication.
G2 Matrix Manifold: A Software Construct
Venue: arXiv cs.CG 2012
Year: 2012

An ensemble of symbolic, numeric and graphic computations developed to construct the Octonionic and compact G2 structures in Mathematica 8.0. Cayley-Dickenson Construction symbolically applied from Reals to Octonions. Baker- Campbell-Hausdorff formula (BCH) in bracket form verified for Octonions. Algorithms for both exponentiation and logarithm of Octonions developed. Exclusive validity of vector Product verified for 0, 1, 3 and 7 dimensions. Symbolic exponential computations carried out for two distinct g2 basis(s) and arbitrary precision BCH for G2 was coded. Example and counter-example Maximal Torus for G2 was uncovered. Densely coiled shapes of actions of G2 rendered. Kolmogorov Complexity for BCH investigated and upper bounds computed: Complexity of non-commutative non- associative algebraic expression is at most the Complexity of corresponding commutative associative algebra plus K(BCH).
Access Points Placement as a Discrete Optimization Problem
Venue: arXiv cs.NI 2012
Year: 2012

In this work, we consider a method of searching of the direction of a wireless network development (the places of new access points or base stations etc.) optimized with criteria of coverage of important territories and minimum cost of equipment and additional needed infrastructure which does not need the execution of special field testings and determination of the exact geometry of elements of RF-propagation medium and their RF absorbing properties but takes into account the minimum accessible information obtained from built-in measuring instruments of wireless hardware and approximate data of the medium elements shape. The problem of search of a disposition and types of the infrastructure elements of the growing network is formulated as a multicriteria discrete constrained optimization problem solvable with variant probability method [1]. The problem of a medium RF-propagation properties modeling is also formulated and solved as a discrete optimization task.
Performance Evaluation of Flash File Systems
Venue: arXiv cs.OS 2012
Year: 2012

Today, flash memory are strongly used in the embedded system domain. NAND flash memories are the building block of main secondary storage systems. Such memories present many benefits in terms of data density, I/O performance, shock resistance and power consumption. Nevertheless, flash does not come without constraints: the write / erase granularity asymmetry and the limited lifetime bring the need for specific management. This can be done through the operating system using dedicated Flash File Systems (FFSs). In this document, we present general concepts about FFSs, and implementations example that are JFFS2, YAFFS2 and UBIFS, the most commonly used flash file systems. Then we give performance evaluation results for these FFSs.
Parallel Random Search Algorithm of Constrained Pseudo-Boolean Optimization for Some Distinctive Large-Scale Problems
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we consider an approach to the parallelizing of the algorithms realizing the modified probability changigng method with adaptation and partial rollback procedure for constrained pseudo-Boolean optimization problems. Existing optimization algorithms are adapted for the shared memory and clusters (PVM library). The parallel efficiency is estimated for the lagre-scale non-linear pseudo-Boolean optimization problems with linear constraints. Initially designed for unconstrained optimization, the probability changing method (MIVER) allows us finding the approximate solution of different linear and non-linear pseudo-Boolean optimization problems with constraints. Although, in case of large-scale problems, the computational demands are also very high and the precision of the result depends on the time spent. In case of the constrained optimization problem, even the search of any permissibly solution can take very large computational resources. The rapid development of the parallel processor systems which are often implemented even in the computer systems designed for home use allows to reduce significantly the time spent to find the acceptable solution with a speed-up close to ideal.
Combinatorial Gradient Fields for 2D Images with Empirically Convergent Separatrices
Venue: arXiv cs.CV 2012
Year: 2012

This paper proposes an efficient probabilistic method that computes combinatorial gradient fields for two dimensional image data. In contrast to existing algorithms, this approach yields a geometric Morse-Smale complex that converges almost surely to its continuous counterpart when the image resolution is increased. This approach is motivated using basic ideas from probability theory and builds upon an algorithm from discrete Morse theory with a strong mathematical foundation. While a formal proof is only hinted at, we do provide a thorough numerical evaluation of our method and compare it to established algorithms.
A Session Based Blind Watermarking Technique within the NROI of Retinal Fundus Images for Authentication Using DWT, Spread Spectrum and Harris Corner Detection
Venue: arXiv cs.CV 2012
Year: 2012

Digital Retinal Fundus Images helps to detect various ophthalmic diseases by detecting morphological changes in optical cup, optical disc and macula. Present work proposes a method for the authentication of medical images based on Discrete Wavelet Transformation (DWT) and Spread Spectrum. Proper selection of the Non Region of Interest (NROI) for watermarking is crucial, as the area under concern has to be the least required portion conveying any medical information. Proposed method discusses both the selection of least impact area and the blind watermarking technique. Watermark is embedded within the High-High (HH) sub band. During embedding, watermarked image is dispersed within the band using a pseudo random sequence and a Session key. Watermarked image is extracted using the session key and the size of the image. In this approach the generated watermarked image having an acceptable level of imperceptibility and distortion is compared to the Original retinal image based on Peak Signal to Noise Ratio (PSNR) and correlation value.
A Novel Session Based Dual Steganographic Technique Using DWT and Spread Spectrum
Venue: arXiv cs.CR 2012
Year: 2012

This paper proposed a DWT based Steganographic technique. Cover image is decomposed into four sub bands using DWT. Two secret images are embedded within the HL and HH sub bands respectively. During embedding secret images are dispersed within each band using a pseudo random sequence and a Session key. Secret images are extracted using the session key and the size of the images. In this approach the stego image generated is of acceptable level of imperceptibility and distortion compared to the cover image and the overall security is high.
Counting Plane Graphs: Cross-Graph Charging Schemes
Venue: arXiv cs.CG 2012
Year: 2012

We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of $O^*(187.53^N)$ (where the $O^*()$ notation hides polynomial factors) for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of $N$ points in the plane (improving upon the previous best upper bound $207.85^N$ in Hoffmann et al.). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of $k$ pairwise-crossing edges (more commonly known as $k$-quasi-planar graphs). For $k=3$ and $k=4$, we prove that, for any set $S$ of $N$ points in the plane, the number of graphs that have a straight-edge $k$-quasi-planar embedding over $S$ is only exponential in $N$.
Optimizing Supply Chain Management using Gravitational Search Algorithm and Multi Agent System
Venue: arXiv cs.MA 2012
Year: 2012

Supply chain management is a very dynamic operation research problem where one has to quickly adapt according to the changes perceived in environment in order to maximize the benefit or minimize the loss. Therefore we require a system which changes as per the changing requirements. Multi agent system technology in recent times has emerged as a possible way of efficient solution implementation for many such complex problems. Our research here focuses on building a Multi Agent System (MAS), which implements a modified version of Gravitational Search swarm intelligence Algorithm (GSA) to find out an optimal strategy in managing the demand supply chain. We target the grains distribution system among various centers of Food Corporation of India (FCI) as application domain. We assume centers with larger stocks as objects of greater mass and vice versa. Applying Newtonian law of gravity as suggested in GSA, larger objects attract objects of smaller mass towards itself, creating a virtual grain supply source. As heavier object sheds its mass by supplying some to the one in demand, it loses its gravitational pull and thus keeps the whole system of supply chain per-fectly in balance. The multi agent system helps in continuous updation of the whole system with the help of autonomous agents which react to the change in environment and act accordingly. This model also reduces the communication bottleneck to greater extents.
Approximate Similarity Search for Online Multimedia Services on Distributed CPU-GPU Platforms
Venue: arXiv cs.MM 2012
Year: 2012

Similarity search in high-dimentional spaces is a pivotal operation found a variety of database applications. Recently, there has been an increase interest in similarity search for online content-based multimedia services. Those services, however, introduce new challenges with respect to the very large volumes of data that have to be indexed/searched, and the need to minimize response times observed by the end-users. Additionally, those users dynamically interact with the systems creating fluctuating query request rates, requiring the search algorithm to adapt in order to better utilize the underline hardware to reduce response times. In order to address these challenges, we introduce hypercurves, a flexible framework for answering approximate k-nearest neighbor (kNN) queries for very large multimedia databases, aiming at online content-based multimedia services. Hypercurves executes on hybrid CPU--GPU environments, and is able to employ those devices cooperatively to support massive query request rates. In order to keep the response times optimal as the request rates vary, it employs a novel dynamic scheduler to partition the work between CPU and GPU. Hypercurves was throughly evaluated using a large database of multimedia descriptors. Its cooperative CPU--GPU execution achieved performance improvements of up to 30x when compared to the single CPU-core version. The dynamic work partition mechanism reduces the observed query response times in about 50% when compared to the best static CPU--GPU task partition configuration. In addition, Hypercurves achieves superlinear scalability in distributed (multi-node) executions, while keeping a high guarantee of equivalence with its sequential version --- thanks to the proof of probabilistic equivalence, which supported its aggressive parallelization design.
On the Use of Smart Ants for Efficient Routing in Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

Routing in wireless mesh networks (WMNs) has been an active area of research for the last several years. In this paper, we address the problem of packet routing for efficient data forwarding in wireless mesh networks (WMNs) with the help of smart ants acting as intelligent agents. The aim of this paper is to study the use of such biologically inspired agents to effectively route the packets in WMNs. In particular, we propose AntMesh, a distributed interference-aware data forwarding algorithm which enables the use of smart ants to probabilistically and concurrently perform the routing and data forwarding in order to stochastically solve a dynamic network routing problem. AntMesh belongs to the class of routing algorithms inspired by the behaviour of real ants which are known to find a shortest path between their nest and a food source. In addition, AntMesh has the capability to effectively utilize the space/channel diversity typically common in multi radio WMNs and to discover high throughput paths with less inter-flow and intra-flow interference while conventional wireless network routing protocols fail to do so. We implement our smart ant-based routing algorithm in ns-2 and carry out extensive evaluation. We demonstrate the stability of AntMesh in terms of how quickly it adapts itself to the changing dynamics or load on the network. We tune the parameters of AntMesh algorithm to study the effect on its performance in terms of the routing load and end-to-end delay and have tested its performance under various network scenarios particularly fixed nodes mesh networks and also on mobile WMN scenarios. The results obtained show AntMesh's advantages that make it a valuable candidate to operate in mesh networks.