Multi-Parametric Clustering for Sensor Node Coordination in Cognitive Wireless Sensor Networks

The deployment of wireless sensor networks for healthcare applications have been motivated and driven by the increasing demand for real-time monitoring of patients in hospital and large disaster response environments. A major challenge in developing such sensor networks is the need for coordinating a large number of randomly deployed sensor nodes. In this study, we propose a multi-parametric clustering scheme designed to aid in the coordination of sensor nodes within cognitive wireless sensor networks. In the proposed scheme, sensor nodes are clustered together based on similar network behaviour across multiple network parameters, such as channel availability, interference characteristics, and topological characteristics, followed by mechanisms for forming, joining and switching clusters. Extensive performance evaluation is conducted to study the impact on important factors such as clustering overhead, cluster joining estimation error, interference probability, as well as probability of reclustering. Results show that the proposed clustering scheme can be an excellent candidate for use in large scale cognitive wireless sensor network deployments with high dynamics.     

Distributed Clone Detection in Static Wireless Sensor Networks: Random Walk with Network Division

Wireless Sensor Networks (WSNs) are vulnerable to clone attacks or node replication attacks as they are deployed in hostile and unattended environments where they are deprived of physical protection, lacking physical tamper-resistance of sensor nodes. As a result, an adversary can easily capture and compromise sensor nodes and after replicating them, he inserts arbitrary number of clones/replicas into the network. If these clones are not efficiently detected, an adversary can be further capable to mount a wide variety of internal attacks which can emasculate the various protocols and sensor applications. Several solutions have been proposed in the literature to address the crucial problem of clone detection, which are not satisfactory as they suffer from some serious drawbacks. In this paper we propose a novel distributed solution called Random Walk with Network Division (RWND) for the detection of node replication attack in static WSNs which is based on claimer-reporter-witness framework and combines a simple random walk with network division. RWND detects clone(s) by following a claimer-reporter-witness framework and a random walk is employed within each area for the selection of witness nodes. Splitting the network into levels and areas makes clone detection more efficient and the high security of witness nodes is ensured with moderate communication and memory overheads. Our simulation results show that RWND outperforms the existing witness node based strategies with moderate communication and memory overheads.     

Geographic Wormhole Detection in Wireless Sensor Networks

Wireless sensor networks (WSNs) are ubiquitous and pervasive, and therefore; highly susceptible to a number of security attacks. Denial of Service (DoS) attack is considered the most dominant and a major threat to WSNs. Moreover, the wormhole attack represents one of the potential forms of the Denial of Service (DoS) attack. Besides, crafting the wormhole attack is comparatively simple; though, its detection is nontrivial. On the contrary, the extant wormhole defense methods need both specialized hardware and strong assumptions to defend against static and dynamic wormhole attack. The ensuing paper introduces a novel scheme to detect wormhole attacks in a geographic routing protocol (DWGRP). The main contribution of this paper is to detect malicious nodes and select the best and the most reliable neighbors based on pairwise key pre-distribution technique and the beacon packet. Moreover, this novel technique is not subject to any specific assumption, requirement, or specialized hardware, such as a precise synchronized clock. The proposed detection method is validated by comparisons with several related techniques in the literature, such as Received Signal Strength (RSS), Authentication of Nodes Scheme (ANS), Wormhole Detection uses Hound Packet (WHOP), and Wormhole Detection with Neighborhood Information (WDI) using the NS-2 simulator. The analysis of the simulations shows promising results with low False Detection Rate (FDR) in the geographic routing protocols.     

Algorithms for energy efficient mobile object tracking in wireless sensor networks

Wireless sensor networks have found more and more applications in a variety of pervasive computing environments, in their functions as data acquisition in pervasive applications. However, how to get better performance to support data acquisition of pervasive applications over WSNs remains to be a nontrivial and challenging task. The network lifetime and application requirement are two fundamental, yet conflicting, design objectives in wireless sensor networks for tracking mobile objects. The application requirement is often correlated to the delay time within which the application can send its sensing data back to the users in tracking networks. In this paper we study the network lifetime maximization problem and the delay time minimization problem together. To make both problems tractable, we have the assumption that each sensor node keeps working since it turns on. And we formulate the network lifetime maximization problem as maximizing the number of sensor nodes who don’t turn on, and the delay time minimization problem as minimizing the routing path length, after achieving the required tracking tasks. Since we prove the problems are NP-complete and APX-complete, we propose three heuristic algorithms to solve them. And we present several experiments to show the advantages and disadvantages referring to the network lifetime and the delay time among these three algorithms on three models, random graphs, grids and hypercubes. Furthermore, we implement the distributed version of these algorithms.     

Taxon sampling effects in molecular clock dating: an example from the African Restionaceae

Three commonly used molecular dating methods for correction of variable rates (non-parametric rate smoothing, penalized likelihood, and Bayesian rate correction) as well as the assumption of a global molecular clock were tested for sensitivity to taxon sampling. The test dataset of 6854 basepairs for 300 terminals includes a nearly complete sample of the Restio-clade of the African Restionaceae (272 of the 288 species), as well as 26 outgroup species. Of this, nested subsets of 35, 51, 80, 120, 150, and the full 300 species were used. Molecular dating experiments with these datasets showed that all methods are sensitive to undersampling, but that this effect is more severe in analyses that use more extreme rate smoothing. Additionally, the undersampling effect is positively related to distance from the calibration node. The combined effect of undersampling and distance from the calibration node resulted in up to threefold differences in the age estimation of nodes from the same dataset with the same calibration point. We suggest that the most suitable methods are penalized likelihood and Bayesian when a global clock assumption has been rejected, as these methods are more successful at finding optimal levels of smoothing to correct for rate heterogeneity, and are less sensitive to undersampling.     

Evolutionary distance estimation under heterogeneous substitution pattern among lineages

Most of the sophisticated methods to estimate evolutionary divergence between DNA sequences assume that the two sequences have evolved with the same pattern of nucleotide substitution after their divergence from their most recent common ancestor (homogeneity assumption). If this assumption is violated, the evolutionary distance estimated will be biased, which may result in biased estimates of divergence times and substitution rates, and may lead to erroneous branching patterns in the inferred phylogenies. Here we present a simple modification for existing distance estimation methods to relax the assumption of the substitution pattern homogeneity among lineages when analyzing DNA and protein sequences. Results from computer simulations and empirical data analyses for human and mouse genes are presented to demonstrate that the proposed modification reduces the estimation bias considerably and that the modified method performs much better than the LogDet methods, which do not require the homogeneity assumption in estimating the number of substitutions per site. We also discuss the relationship of the substitution and mutation rate estimates when the substitution pattern is not the same in the lineages leading to the two sequences compared.     

GPS-free Positioning in Mobile Ad Hoc Networks

We consider the problem of node positioning in ad hoc networks. We propose a distributed, infrastructure-free positioning algorithm that does not rely on GPS (Global Positioning System). Instead, the algorithm uses the distances between the nodes to build a relative coordinate system in which the node positions are computed in two dimensions. Despite the distance measurement errors and the motion of the nodes, the algorithm provides sufficient location information and accuracy to support basic network functions. Examples of applications where this algorithm can be used include Location Aided Routing [10] and Geodesic Packet Forwarding [2]. Another example are sensor networks, where mobility is less of a problem. The main contribution of this work is to define and compute relative positions of the nodes in an ad hoc network without using GPS. We further explain how the proposed approach can be applied to wide area ad hoc networks.     

Estimation of the true evolutionary distance under the fragile breakage model

Background

The ability to estimate the evolutionary distance between extant genomes plays a crucial role in many phylogenomic studies. Often such estimation is based on the parsimony assumption, implying that the distance between two genomes can be estimated as the rearrangement distance equal the minimal number of genome rearrangements required to transform one genome into the other. However, in reality the parsimony assumption may not always hold, emphasizing the need for estimation that does not rely on the rearrangement distance. The distance that accounts for the actual (rather than minimal) number of rearrangements between two genomes is often referred to as the true evolutionary distance. While there exists a method for the true evolutionary distance estimation, it however assumes that genomes can be broken by rearrangements equally likely at any position in the course of evolution. This assumption, known as the random breakage model, has recently been refuted in favor of the more rigorous fragile breakage model postulating that only certain “fragile” genomic regions are prone to rearrangements.

Results

We propose a new method for estimating the true evolutionary distance between two genomes under the fragile breakage model. We evaluate the proposed method on simulated genomes, which show its high accuracy. We further apply the proposed method for estimation of evolutionary distances within a set of five yeast genomes and a set of two fish genomes.

Conclusions

The true evolutionary distances between the five yeast genomes estimated with the proposed method reveals that some pairs of yeast genomes violate the parsimony assumption. The proposed method further demonstrates that the rearrangement distance between the two fish genomes underestimates their evolutionary distance by about 20%. These results demonstrate how drastically the two distances can differ and justify the use of true evolutionary distance in phylogenomic studies.

     

Compensation of large motion sensor displacements during long recordings of limb movements

In motion capture applications using electromagnetic tracking systems the process of anatomical calibration associates the technical frames of sensors attached to the skin with the human anatomy. Joint centers and axes are determined relative to these frames. A change of orientation of the sensor relative to the skin renders this calibration faulty. This sensitivity regarding sensor displacement can turn out to be a serious problem with movement recordings of several minutes duration. We propose the “dislocation distance” as a novel method to quantify sensor displacement and to detect gradual and sudden changes of sensor orientation. Furthermore a method to define a so called fixed technical frame is proposed as a robust reference frame which can adapt to a new sensor orientation on the skin. The proposed methods are applied to quantify the effects of sensor displacement of 120 upper and lower limb movement recordings of newborns revealing the need for a method to compensate for sensor displacement. The reliability of the fixed technical frame is quantified and it is shown that trend and dispersion of the dislocation distance can be significantly reduced. A working example illustrates the consequences of sensor displacement on derived angle time series and how they are avoided using the fixed technical frame.     

Tree and rate estimation by local evaluation of heterochronous nucleotide data

MOTIVATION: Heterochronous gene sequence data is important for characterizing the evolutionary processes of fast-evolving organisms such as RNA viruses. A limited set of algorithms exists for estimating the rate of nucleotide substitution and inferring phylogenetic trees from such data. The authors here present a new method, Tree and Rate Estimation by Local Evaluation (TREBLE) that robustly calculates the rate of nucleotide substitution and phylogeny with several orders of magnitude improvement in computational time. METHODS: For the basis of its rate estimation TREBLE novelly utilizes a geometric interpretation of the molecular clock assumption to deduce a local estimate of the rate of nucleotide substitution for triplets of dated sequences. Averaging the triplet estimates via a variance weighting yields a global estimate of the rate. From this value, an iterative refinement procedure relying on statistical properties of the triplets then generates a final estimate of the global rate of nucleotide substitution. The estimated global rate is then utilized to find the tree from the pairwise distance matrix via an UPGMA-like algorithm. RESULTS: Simulation studies show that TREBLE estimates the rate of nucleotide substitution with point estimates comparable with the best of available methods. Confidence intervals are comparable with that of BEAST. TREBLE's phylogenetic reconstruction is significantly improved over the other distance matrix method but not as accurate as the Bayesian algorithm. Compared with three other algorithms, TREBLE reduces computational time by a minimum factor of 3000. Relative to the algorithm with the most accurate estimates for the rate of nucleotide substitution (i.e. BEAST), TREBLE is over 10,000 times more computationally efficient. AVAILABILITY: jdobrien.bol.ucla.edu/TREBLE.html     

Improving metabolic flux estimation via evolutionary optimization for convex solution space

MOTIVATION: Flux estimation by using (13) C-labeling pattern information of metabolites is currently the only method that can give accurate, detailed quantification of all intracellular fluxes in the central metabolism of a microorganism. In essence, it corresponds to a constrained optimization problem which minimizes a weighted distance between measured and simulated results. Characteristics, such as existence of multiple local minima, non-linear and non-differentiable make this problem a special difficulty. RESULTS: In the present work, we propose an evolutionary-based global optimization algorithm taking advantage of the convex feature of the problem's solution space. Based on the characteristics of convex spaces, specialized initial population and evolutionary operators are designed to solve (13)C-based metabolic flux estimation problem robustly and efficiently. The algorithm was applied to estimate the central metabolic fluxes in Escherichia coli and compared with conventional optimization technique. Experimental results illustrated that our algorithm is capable of achieving fast convergence to good near-optima and maintaining the robust nature of evolutionary algorithms at the same time. AVAILABILITY: Available from the authors upon request.     

Accounting for radiotelemetry signal flux in triangulation point estimation

Triangulation by radiotelemetry is a method commonly used to estimate locations of wildlife. Despite the importance of the accuracy of resulting location estimates, there has been little development and comparison of alternative methods for point-location estimation for 25 years. Most methods assume that signal transmissions as they are received are consistent, but signal heterogeneity and fluxing is common. Using data from a beacon study, we determined that a subjective ranking of confidence in the accuracy of a signal was correlated with absolute bearing error. Using this factor and the distance from a telemetry station to the error triangle incenter, we developed an algorithm to place a weighted point-location estimate in relative proximity to each error triangle leg. We have termed this the weighted-incenter method. Despite previous findings that the major confidence ellipse axis of Lenth’s maximum likelihood estimator (MLE) correlated best to linear distance error, our beacon test data indicated that total bearing angle difference was the best single predictor of linear error with an optimal total angle of about 100°. The new and intuitive weighted-incenter method offered some improvement over previous methods such as the MLE estimator, but only with suboptimal angle bearings that may be common in field studies. By using a MATLAB function to produce data for site-specific regression analyses, one can determine which method should produce the more accurate point-location estimate for each triangulation observation. Further significance of this study for field biologists is discussed.     

Detecting the Influence of Spreading in Social Networks with Excitable Sensor Networks

Detecting spreading outbreaks in social networks with sensors is of great significance in applications. Inspired by the formation mechanism of humans’ physical sensations to external stimuli, we propose a new method to detect the influence of spreading by constructing excitable sensor networks. Exploiting the amplifying effect of excitable sensor networks, our method can better detect small-scale spreading processes. At the same time, it can also distinguish large-scale diffusion instances due to the self-inhibition effect of excitable elements. Through simulations of diverse spreading dynamics on typical real-world social networks (Facebook, coauthor, and email social networks), we find that the excitable sensor networks are capable of detecting and ranking spreading processes in a much wider range of influence than other commonly used sensor placement methods, such as random, targeted, acquaintance and distance strategies. In addition, we validate the efficacy of our method with diffusion data from a real-world online social system, Twitter. We find that our method can detect more spreading topics in practice. Our approach provides a new direction in spreading detection and should be useful for designing effective detection methods.     

A Service Approach for Architecting Application Independent Wireless Sensor Networks

The current sensor networks are assumed to be designed for specific applications, having data communication protocols strongly coupled to applications. The future sensor networks are envisioned as comprising heterogeneous devices assisting to a large range of applications. To achieve this goal, a new architecture approach is needed, having application specific features separated from the data communication protocol, while influencing its behavior. We propose a Web Services approach for the design of sensor network, in which sensor nodes are service providers and applications are clients of such services. Our main goal is to enable a flexible architecture in which sensor networks data can be accessed by users spread all over the world.     

An improved localization algorithm based on genetic algorithm in wireless sensor networks

Wireless sensor network (WSN) are widely used in many applications. A WSN is a wireless decentralized structure network comprised of nodes, which autonomously set up a network. The node localization that is to be aware of position of the node in the network is an essential part of many sensor network operations and applications. The existing localization algorithms can be classified into two categories: range-based and range-free. The range-based localization algorithm has requirements on hardware, thus is expensive to be implemented in practice. The range-free localization algorithm reduces the hardware cost. Because of the hardware limitations of WSN devices, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. However, these techniques usually have higher localization error compared to the range-based algorithms. DV-Hop is a typical range-free localization algorithm utilizing hop-distance estimation. In this paper, we propose an improved DV-Hop algorithm based on genetic algorithm. Simulation results show that our proposed algorithm improves the localization accuracy compared with previous algorithms.     

Walking the interactome for prioritization of candidate disease genes

The identification of genes associated with hereditary disorders has contributed to improving medical care and to a better understanding of gene functions, interactions, and pathways. However, there are well over 1500 Mendelian disorders whose molecular basis remains unknown. At present, methods such as linkage analysis can identify the chromosomal region in which unknown disease genes are located, but the regions could contain up to hundreds of candidate genes. In this work, we present a method for prioritization of candidate genes by use of a global network distance measure, random walk analysis, for definition of similarities in protein-protein interaction networks. We tested our method on 110 disease-gene families with a total of 783 genes and achieved an area under the ROC curve of up to 98% on simulated linkage intervals of 100 genes surrounding the disease gene, significantly outperforming previous methods based on local distance measures. Our results not only provide an improved tool for positional-cloning projects but also add weight to the assumption that phenotypically similar diseases are associated with disturbances of subnetworks within the larger protein interactome that extend beyond the disease proteins themselves.     

A Spark-based genetic algorithm for sensor placement in large scale drinking water distribution systems

Water pollution incidents have occurred frequently in recent years, causing severe damages, economic loss and long-lasting society impact. A viable solution is to install water quality monitoring sensors in water supply networks (WSNs) for real-time pollution detection, thereby mitigating the risk of catastrophic contamination incidents. Given the significant cost of placing sensors at all locations in a network, a critical issue is where to deploy sensors within WSNs, while achieving rapid detection of contaminant events. Existing studies have mainly focused on sensor placement in water distribution systems (WDSs). However, the problem is still not adequately addressed, especially for large scale WSNs. In this paper, we investigate the sensor placement problem in large scale WDSs with the objective of minimizing the impact of contamination events. Specifically, we propose a two-phase Spark-based genetic algorithm (SGA). Experimental results show that SGA outperforms other traditional algorithms in both accuracy and efficiency, which validates the feasibility and effectiveness of our proposed approach.     

A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks

How to identify influential nodes is a key issue in complex networks. The degree centrality is simple, but is incapable to reflect the global characteristics of networks. Betweenness centrality and closeness centrality do not consider the location of nodes in the networks, and semi-local centrality, leaderRank and pageRank approaches can be only applied in unweighted networks. In this paper, a bio-inspired centrality measure model is proposed, which combines the Physarum centrality with the K-shell index obtained by K-shell decomposition analysis, to identify influential nodes in weighted networks. Then, we use the Susceptible-Infected (SI) model to evaluate the performance. Examples and applications are given to demonstrate the adaptivity and efficiency of the proposed method. In addition, the results are compared with existing methods.     

Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about nodes, more than 15 times faster than PageRank.     

Controlling spatial chaos in metapopulations with long-range dispersal

We propose two methods to control spatial chaos in an ecological metapopulation model with long-range dispersal. The metapopulation model consists of local populations living in a patchily distributed habitat. The habitat patches are arranged in a one-dimensional array. In each generation, density-dependent reproduction occurs first in each patch. Then individuals disperse according to a Gaussian distribution. The model corresponds to a chain of coupled oscillators with long-range interactions. It exhibits chaos for a broad range of parameters. The proposed control methods are based on the method described by Güémez and Matías for single difference equations. The methods work by adjusting the local population sizes in a selected subset of all patches. In the first method (pulse control), the adjustments are made periodically at regular time intervals, and consist of always removing (or adding) a fixed proportion of the local populations. In the second method (wave control), the adjustments are made in every generation, but the proportion of the local population that is affected by the control changes sinusoidally. As long as dispersal distances are not too low, these perturbations can drive chaotic metapopulations to cyclic orbits whose period is a multiple of the control period. we discuss the influence of the magnitude of the pulses and wave amplitudes, and of the number and the distribution of controlled patches on the effectiveness of control. When the controls start to break down, interesting dynamic phenomena such as intermittent chaos can be observed.