DLS: A dynamic local stitching mechanism to rectify transmitting path fragments in wireless sensor networks

In this paper, a pair of novel rectification algorithms (greedy negative pressure push algorithm and dynamic local stitching algorithm) is proposed to cooperatively repair broken transmitting paths in Wireless Sensor Networks. Our approach is to overcome the poor data validity in WSNs, specifically for harsh application environments – such as unattended sensor nodes or frail wireless transmitting channels – where fault tolerant becomes a vital aspect. Using adjacency information, Greedy negative pressure push algorithm can efficiently grow the transmitting path to achieve the minimum energy consumption for relays model. Here, we measured packet travel time and the expectation of relay distance to set this model's key parameters to achieve the lowest possible end-to-end transmitting delay. Dynamic local stitching algorithm has a major difference with other existing routing algorithms in rectifying broken paths; despite others that reroute whole paths, our algorithms only stitch broken fragments of the original path spending minimum amount of energy as well as recovery time. Based on mathematical computing and simulation, our novel rectification algorithm could effectively (1) reduce the total number of routing overheads, (2) improve net throughput, and (3) increase system fault tolerant much better than four already designed routing algorithms. Results were also very promising to motivate other algorithms in this field.     

DCDedupe: Selective Deduplication and Delta Compression with Effective Routing for Distributed Storage

Data deduplication has been an essential part of storage systems for big data. Traditional compare-by-hash (CBH) deduplication does not fully address the challenges for similar files with small changes. Delta compression can be complementary to further optimize the storage efficiency. In this paper, we designed and implemented a distributed storage system called DCDedupe that efficiently and intelligently use delta compression or deduplication to improve storage efficiency based on characteristics of data. Unlike prior studies, this system works well when the data locality is weak or even barely exists. In DCDedupe, we propose a pre-processing step to identify content similarity and data chunks are classified into different categories. Then, the appropriate routing algorithm ensures the data chunks are sent to the right target storage nodes in the distributed system to boost the storage efficiency. Our evaluation shows that generally storage space saving by DCDedupe outweighs the performance penalties. In some use cases, DCDeupe may become meaningful to trade off some throughput with optimized storage costs. The overheads to Input/Output (IO) operation and memory usage have also been studied with design recommendations.     

Observations on using genetic algorithms for dynamic load-balancing

Load-balancing problems arise in many applications, but, most importantly, they play a special role in the operation of parallel and distributed computing systems. Load-balancing deals with partitioning a program into smaller tasks that can be executed concurrently and mapping each of these tasks to a computational resource such as a processor (e.g., in a multiprocessor system) or a computer (e.g., in a computer network). By developing strategies that can map these tasks to processors in a way that balances out the load, the total processing time will be reduced with improved processor utilization. Most of the research on load-balancing focused on static scenarios that, in most of the cases, employ heuristic methods. However, genetic algorithms have gained immense popularity over the last few years as a robust and easily adaptable search technique. The work proposed here investigates how a genetic algorithm can be employed to solve the dynamic load-balancing problem. A dynamic load-balancing algorithm is developed whereby optimal or near-optimal task allocations can “evolve” during the operation of the parallel computing system. The algorithm considers other load-balancing issues such as threshold policies, information exchange criteria, and interprocessor communication. The effects of these and other issues on the success of the genetic-based load-balancing algorithm as compared with the first-fit heuristic are outlined     

Game-Theoretic Approach for Load Balancing in Computational Grids

Load balancing is a very important and complex problem in computational grids. A computational grid differs from traditional high-performance computing systems in the heterogeneity of the computing nodes, as well as the communication links that connect the different nodes together. There is a need to develop algorithms that can capture this complexity yet can be easily implemented and used to solve a wide range of load-balancing scenarios. In this paper, we propose a game-theoretic solution to the grid load-balancing problem. The algorithm developed combines the inherent efficiency of the centralized approach and the fault-tolerant nature of the distributed, decentralized approach. We model the grid load-balancing problem as a noncooperative game, whereby the objective is to reach the Nash equilibrium. Experiments were conducted to show the applicability of the proposed approaches. One advantage of our scheme is the relatively low overhead and robust performance against inaccuracies in performance prediction information.     

An energy-efficient permutation routing protocol for single-hop radio networks

A radio network (RN) is a distributed system where each station or node is a small hand-held commodity device called a station. Typically, each station has access to a few channels for transmitting and receiving messages. By RN(p, k), we denote a radio network with p stations, where each station has access to k channels. In a single-hop RN, every station is within the transmission range of every other station. Each station consumes power while transmitting or receiving a message, even when it receives a message that is not destined for it. It is extremely important that the stations consume power only when it is necessary since it is not possible to recharge batteries when the stations are on a mission. We are interested in designing an energy-efficient protocol for permutation routing, which is one of the most fundamental problems in any distributed system. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination address which is the identity of the destination station to which the item should be sent. The goal is to route all the items to their destinations while consuming as little energy as possible. We show that the permutation routing problem of n packets on an RN(p, k) can be solved in 2n/k+(p/k)/sup 2/+p+2k/sup 2/ slots and each station needs to be awake for at most 6n/p+2p/k+8k slots. When k/spl Lt/p/spl Lt/n, our protocol is more efficient, both in terms of total number of slots and the number of slots each station is awake compared to a previously published protocol by Nakano et al. (2001).     

DomNet: protein domain boundary prediction using enhanced general regression network and new profiles

The accurate and stable prediction of protein domain boundaries is an important avenue for the prediction of protein structure, function, evolution, and design. Recent research on protein domain boundary prediction has been mainly based on widely known machine learning techniques. In this paper, we propose a new machine learning based domain predictor namely, DomNet that can show a more accurate and stable predictive performance than the existing state-of-the-art models. The DomNet is trained using a novel compact domain profile, secondary structure, solvent accessibility information, and interdomain linker index to detect possible domain boundaries for a target sequence. The performance of the proposed model was compared to nine different machine learning models on the Benchmark_2 dataset in terms of accuracy, sensitivity, specificity, and correlation coefficient. The DomNet achieved the best performance with 71% accuracy for domain boundary identification in multidomains proteins. With the CASP7 benchmark dataset, it again demonstrated superior performance to contemporary domain boundary predictors such as DOMpro, DomPred, DomSSEA, DomCut, and DomainDiscovery.     

A Bee Colony based optimization approach for simultaneous job scheduling and data replication in grid environments

This paper presents a novel Bee Colony based optimization algorithm, named Job Data Scheduling using Bee Colony (JDS-BC). JDS-BC consists of two collaborating mechanisms to efficiently schedule jobs onto computational nodes and replicate datafiles on storage nodes in a system so that the two independent, and in many cases conflicting, objectives (i.e., makespan and total datafile transfer time) of such heterogeneous systems are concurrently minimized. Three benchmarks – varying from small- to large-sized instances – are used to test the performance of JDS-BC. Results are compared against other algorithms to show JDS-BC's superiority under different operating scenarios. These results also provide invaluable insights into data-centric job scheduling for grid environments.     

A time-optimal solution for the path cover problem on cographs

We show that the notoriously difficult problem of finding and reporting the smallest number of vertex-disjoint paths that cover the vertices of a graph can be solved time- and work-optimally for cographs. Our result implies that for this class of graphs the task of finding a Hamiltonian path can be solved time- and work-optimally in parallel.

It was open for more than 10 years to find a time- and work-optimal parallel solution for this important problem. Our contribution is to offer an optimal solution to this important problem. We begin by showing that any algorithm that solves an instance of size n of the problem must take Ω(log n) time on the CREW, even if an infinite number of processors are available. We then go on to show that this time lower bound is tight by devising an EREW algorithm that, given an n-vertex cograph G represented by its cotree, finds and reports all the paths in a minimum path cover in O(log n) time using n/log n processors.     

Clustering techniques for dynamic location management in mobile computing

This paper presents a novel approach based on clustering algorithms in combination with the location area (LA) scheme to solve the mobility management problem. Users’ movement history is used by the network to predict future paging decisions. This approach integrates the LAs scheme and efficient clustering algorithms to find a network topology which can lead to massive savings in the number of signals made to locate users in the network. The approach is tested with several networks to show its advantages to the current GSM standards. The results provide new insights into the mobility management problem.