Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks

Several localized position based routing algorithms for wireless networks were described recently. In greedy routing algorithm (that has close performance to the shortest path algorithm, if successful), sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to destination. The algorithm fails if S does not have any neighbor that is closer to destination than S. FACE algorithm guarantees the delivery of m if the network, modeled by unit graph, is connected. GFG algorithm combines greedy and FACE algorithms. Greedy algorithm is applied as long as possible, until delivery or a failure. In case of failure, the algorithm switches to FACE algorithm until a node closer to destination than last failure node is found, at which point greedy algorithm is applied again. Past traffic does not need to be memorized at nodes. In this paper we further improve the performance of GFG algorithm, by reducing its average hop count. First we improve the FACE algorithm by adding a sooner-back procedure for earlier escape from FACE mode. Then we perform a shortcut procedure at each forwarding node S. Node S uses the local information available to calculate as many hops as possible and forwards the packet to the last known hop directly instead of forwarding it to the next hop. The second improvement is based on the concept of dominating sets. Each node in the network is classified as internal or not, based on geographic position of its neighboring nodes. The network of internal nodes defines a connected dominating set, i.e., and each node must be either internal or directly connected to an internal node. In addition, internal nodes are connected. We apply several existing definitions of internal nodes, namely the concepts of intermediate, inter-gateway and gateway nodes. We propose to run GFG routing, enhanced by shortcut procedure, on the dominating set, except possibly the first and last hops. The performance of proposed algorithms is measured by comparing its average hop count with hop count of the basic GFG algorithm and the benchmark shortest path algorithm, and very significant improvements were obtained for low degree graphs. More precisely, we obtained localized routing algorithm that guarantees delivery and has very low excess in terms of hop count compared to the shortest path algorithm. The experimental data show that the length of additional path (in excess of shortest path length) can be reduced to about half of that of existing GFG algorithm.     

Traffic-aware routing protocol for wireless sensor networks

In wireless sensor networks, when a sensor node detects events in the surrounding environment, the sensing period for learning detailed information is likely to be short. However, the short sensing cycle increases the data traffic of the sensor nodes in a routing path. Since the high traffic load causes a data queue overflow in the sensor nodes, important information about urgent events could be lost. In addition, since the battery energy of the sensor nodes is quickly exhausted, the entire lifetime of wireless sensor networks would be shortened. In this paper, to address these problem issues, a new routing protocol is proposed based on a lightweight genetic algorithm. In the proposed method, the sensor nodes are aware of the data traffic rate to monitor the network congestion. In addition, the fitness function is designed from both the average and the standard deviation of the traffic rates of sensor nodes. Based on dominant gene sets in a genetic algorithm, the proposed method selects suitable data forwarding sensor nodes to avoid heavy traffic congestion. In experiments, the proposed method demonstrates efficient data transmission due to much less queue overflow and supports fair data transmission for all sensor nodes. From the results, it is evident that the proposed method not only enhances the reliability of data transmission but also distributes the energy consumption across wireless sensor networks.     

An Efficient Next Hop Selection Algorithm for Multi-Hop Body Area Networks

Body Area Networks (BANs) consist of various sensors which gather patient’s vital signs and deliver them to doctors. One of the most significant challenges faced, is the design of an energy-efficient next hop selection algorithm to satisfy Quality of Service (QoS) requirements for different healthcare applications. In this paper, a novel efficient next hop selection algorithm is proposed in multi-hop BANs. This algorithm uses the minimum hop count and a link cost function jointly in each node to choose the best next hop node. The link cost function includes the residual energy, free buffer size, and the link reliability of the neighboring nodes, which is used to balance the energy consumption and to satisfy QoS requirements in terms of end to end delay and reliability. Extensive simulation experiments were performed to evaluate the efficiency of the proposed algorithm using the NS-2 simulator. Simulation results show that our proposed algorithm provides significant improvement in terms of energy consumption, number of packets forwarded, end to end delay and packet delivery ratio compared to the existing routing protocol.     

The circular topology of rhythm in asynchronous random Boolean networks

The analysis of previously evolved rhythmic asynchronous random Boolean networks [Biosystems 59 (2001) 185] reveals common topological characteristics indicating that rhythm originates from a circular functional structure. The rhythm generating core of the network has the form of a closed ring which operates as a synchronisation substrate by supporting a travelling wave of state change; the size of the ring corresponds well with the period of oscillation. The remaining nodes in the network are either stationary or follow the activity of the ring without feeding back into it so as to form a coherent whole. Rings are typically formed early on in the evolutionary search process. Alternatively, long chains of nodes are favoured before they close upon themselves to stabilize. Analysis of asynchronous networks with de-correlated (non-rhythmic, non-stationary) attractors reveals no such common topological characteristics. These results have been obtained using statistical analysis and a specifically developed bottom-up pruning algorithm. This algorithm works from local interactions to global configuration by eliminating redundant links. The suitability of the algorithm has been confirmed by both numerical and single lesion analysis. The ring topology solution for the generation of rhythm implies that it will be harder to evolve rhythmic networks for big sizes and small periods and for bigger number of connections per node. These trends are confirmed empirically. Finally, the identified mechanisms are utilised to handcraft rhythmic networks of different periods showing that a low number of connections suffices for a large variety of rhythms. Random asynchronous update forces the evolved solutions to be highly robust maintaining their performance in the presence of intrinsic noise. The biological implications of such robust designs for molecular clocks are discussed.     

An efficient grid layout algorithm for biological networks utilizing various biological attributes

Background  

Clearly visualized biopathways provide a great help in understanding biological systems. However, manual drawing of large-scale biopathways is time consuming. We proposed a grid layout algorithm that can handle gene-regulatory networks and signal transduction pathways by considering edge-edge crossing, node-edge crossing, distance measure between nodes, and subcellular localization information from Gene Ontology. Consequently, the layout algorithm succeeded in drastically reducing these crossings in the apoptosis model. However, for larger-scale networks, we encountered three problems: (i) the initial layout is often very far from any local optimum because nodes are initially placed at random, (ii) from a biological viewpoint, human layouts still exceed automatic layouts in understanding because except subcellular localization, it does not fully utilize biological information of pathways, and (iii) it employs a local search strategy in which the neighborhood is obtained by moving one node at each step, and automatic layouts suggest that simultaneous movements of multiple nodes are necessary for better layouts, while such extension may face worsening the time complexity.     

狗牙根营养繁殖体对模拟水淹的生物学响应

研究了水淹条件下狗牙根(Cynodon daetylon)繁殖体的形态特征和生物量的变化及其水淹后的恢复状况.结果表明,水淹深度的增加会诱导植株茎快速增高,而叶片数则明显下降.水淹时间对植株叶片数、茎直径、茎与根长比的影响显著,而对分枝数、茎长、根长、茎节数不显著.植株地上部生物量和总生物量随着水淹时间的延长而显著减少,但地下部生物量的变化不显著.所有实验处理的植株水淹后都能存活且恢复生长.但水淹对恢复期植株的生长仍有影响,植株的茎长、根长、分枝数、直径、叶片数、叶长、宽度以及叶的长宽比都随水淹时间的延长而显著减少,但茎节数与叶片数的差异不显著.根、茎、叶生物量和植株总生物量也随着水淹时间的延长而减少.实验表明狗牙根繁殖体通过延长茎长、改变叶形和减少生物量等方式对水淹显示出较强的耐受能力.     

Particle Swarm Optimization with Scale-Free Interactions

The particle swarm optimization (PSO) algorithm, in which individuals collaborate with their interacted neighbors like bird flocking to search for the optima, has been successfully applied in a wide range of fields pertaining to searching and convergence. Here we employ the scale-free network to represent the inter-individual interactions in the population, named SF-PSO. In contrast to the traditional PSO with fully-connected topology or regular topology, the scale-free topology used in SF-PSO incorporates the diversity of individuals in searching and information dissemination ability, leading to a quite different optimization process. Systematic results with respect to several standard test functions demonstrate that SF-PSO gives rise to a better balance between the convergence speed and the optimum quality, accounting for its much better performance than that of the traditional PSO algorithms. We further explore the dynamical searching process microscopically, finding that the cooperation of hub nodes and non-hub nodes play a crucial role in optimizing the convergence process. Our work may have implications in computational intelligence and complex networks.     

Duplication models for biological networks.

Are biological networks different from other large complex networks? Both large biological and nonbiological networks exhibit power-law graphs (number of nodes with degree k, N(k) approximately k(-beta)), yet the exponents, beta, fall into different ranges. This may be because duplication of the information in the genome is a dominant evolutionary force in shaping biological networks (like gene regulatory networks and protein-protein interaction networks) and is fundamentally different from the mechanisms thought to dominate the growth of most nonbiological networks (such as the Internet). The preferential choice models used for nonbiological networks like web graphs can only produce power-law graphs with exponents greater than 2. We use combinatorial probabilistic methods to examine the evolution of graphs by node duplication processes and derive exact analytical relationships between the exponent of the power law and the parameters of the model. Both full duplication of nodes (with all their connections) as well as partial duplication (with only some connections) are analyzed. We demonstrate that partial duplication can produce power-law graphs with exponents less than 2, consistent with current data on biological networks. The power-law exponent for large graphs depends only on the growth process, not on the starting graph.     

Fast computing betweenness centrality with virtual nodes on large sparse networks

Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in O(wDN2) time for integer-weighted networks, where w is the average weight of edges and D is the average degree in the network. Considerable time can be saved with the proposed algorithm when w < log N/D + 1, indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.     

Detecting controlling nodes of boolean regulatory networks

Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than ?k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.     

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.     

Cytoscape ESP: simple search of complex biological networks

SUMMARY: Cytoscape enhanced search plugin (ESP) enables searching complex biological networks on multiple attribute fields using logical operators and wildcards. Queries use an intuitive syntax and simple search line interface. ESP is implemented as a Cytoscape plugin and complements existing search functions in the Cytoscape network visualization and analysis software, allowing users to easily identify nodes, edges and subgraphs of interest, even for very large networks. Availabiity: http://chianti.ucsd.edu/cyto_web/plugins/ CONTACT: ashkenaz@agri.huji.ac.il.     

WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks

In this paper, we propose an on-demand distributed clustering algorithm for multi-hop packet radio networks. These types of networks, also known as ad hoc networks, are dynamic in nature due to the mobility of nodes. The association and dissociation of nodes to and from clusters perturb the stability of the network topology, and hence a reconfiguration of the system is often unavoidable. However, it is vital to keep the topology stable as long as possible. The clusterheads, form a dominant set in the network, determine the topology and its stability. The proposed weight-based distributed clustering algorithm takes into consideration the ideal degree, transmission power, mobility, and battery power of mobile nodes. The time required to identify the clusterheads depends on the diameter of the underlying graph. We try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control (MAC) protocol. The non-periodic procedure for clusterhead election is invoked on-demand, and is aimed to reduce the computation and communication costs. The clusterheads, operating in dual power mode, connects the clusters which help in routing messages from a node to any other node. We observe a trade-off between the uniformity of the load handled by the clusterheads and the connectivity of the network. Simulation experiments are conducted to evaluate the performance of our algorithm in terms of the number of clusterheads, reaffiliation frequency, and dominant set updates. Results show that our algorithm performs better than existing ones and is also tunable to different kinds of network conditions.     

An Efficient Immunization Strategy for Community Networks

An efficient algorithm that can properly identify the targets to immunize or quarantine for preventing an epidemic in a population without knowing the global structural information is of obvious importance. Typically, a population is characterized by its community structure and the heterogeneity in the weak ties among nodes bridging over communities. We propose and study an effective algorithm that searches for bridge hubs, which are bridge nodes with a larger number of weak ties, as immunizing targets based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. Applying the algorithm to simulated networks and empirical networks constructed from social network data of five US universities, we show that the algorithm is more effective than other existing local algorithms for a given immunization coverage, with a reduced final epidemic ratio, lower peak prevalence and fewer nodes that need to be visited before identifying the target nodes. The effectiveness stems from the breaking up of community networks by successful searches on target nodes with more weak ties. The effectiveness remains robust even when errors exist in the structure of the networks.     

Searching for pharmacophoric patterns in databases of three-dimensional chemical structures

This paper provides an overview of the research that has been carried out in Sheffield over the last decade into searching techniques for databases of three-dimensional (3D) chemical structures. A 3D structure or query pattern is represented by a labelled graph, in which the nodes and the edges of the graph are used to represent atoms and the associated inter-atomic distances, respectively. The presence of a pharmacophore in each of the structures in a database can then be tested by means of a subgraph isomorphism algorithm, the computational requirements of which are minimized by the use of an initial screening procedure that eliminates the majority of the structures from the subgraph-isomorphism search. Analogous graph-based representation and searching methods can also be used with flexible 3D structures: in this case, the edges of the graphs represent inter-atomic distance ranges and a final conformational search needs to be carried out for those molecules that match the query pharmacophore in the subgraph-isomorphism search. The paper also reviews related work on the automatic identification of pharmacophoric patterns and on 3D similarity searching.     

A Heuristic-Based Wormhole Routing Algorithm for Hypercube Multicomputer Networks

In this paper, we consider fault-tolerant routing algorithms in hypercube multicomputer networks. In particular, one of the most quoted adaptive fault-tolerant routing algorithm for hypercubes in the literature is studied in detail and its limited ability to route messages in the presence of some fault patterns (i.e., combination of node and link faults), is pointed out. A modified algorithm is proposed and its performance, using simulation, is compared to that of the above mentioned algorithm. It is shown that the proposed algorithm outperforms the existing one in terms of its ability to route routable messages around the hypercube in the presence of node and/or links faults. This improvement is achieved while using the same average path length or even improving it. Illustrative examples are shown in support of such improvement.     

Blackboard Mechanism Based Ant Colony Theory for Dynamic Deployment of Mobile Sensor Networks

A novel bionic swarm intelligence algorithm, called ant colony algorithm based on a blackboard mechanism, is proposed to solve the autonomy and dynamic deployment of mobiles sensor networks effectively. A blackboard mechanism is introduced into the system for making pheromone and completing the algorithm. Every node, which can be looked as an ant, makes one information zone in its memory for communicating with other nodes and leaves pheromone, which is created by ant itself in naalre. Then ant colony theory is used to find the optimization scheme for path planning and deployment of mobile Wireless Sensor Network （WSN）. We test the algorithm in a dynamic and unconfigurable environment. The results indicate that the algorithm can reduce the power consumption by 13% averagely, enhance the efficiency of path planning and deployment of mobile WSN by 15% averagely.     

linkcomm: an R package for the generation, visualization, and analysis of link communities in networks of arbitrary size and type

SUMMARY: An essential element when analysing the structure, function, and dynamics of biological networks is the identification of communities of related nodes. An algorithm proposed recently enhances this process by clustering the links between nodes, rather than the nodes themselves, thereby allowing each node to belong to multiple overlapping or nested communities. The R package 'linkcomm' implements this algorithm and extends it in several aspects: (i) the clustering algorithm handles networks that are weighted, directed, or both weighted and directed; (ii) several visualization methods are implemented that facilitate the representation of the link communities and their relationships; (iii) a suite of functions are included for the downstream analysis of the link communities including novel community-based measures of node centrality; (iv) the main algorithm is written in C++ and designed to handle networks of any size; and (v) several clustering methods are available for networks that can be handled in memory, and the number of communities can be adjusted by the user. AVAILABILITY: The program is freely available from the Comprehensive R Archive Network (http://cran.r-project.org/) under the terms of the GNU General Public License (version 2 or later).     

Forwarding Group Multicast Protocol (FGMP) for multihop, mobile wireless networks

In this paper we propose a new multicast protocol for multihop mobile wireless networks. Instead of forming multicast trees, a group of nodes in charge of forwarding multicast packets is designated according to members' requests. Multicast is then carried out via “scoped” flooding over such a set of nodes. The forwarding group is periodically refreshed to handle topology/membership changes. Multicast using forwarding group takes advantage of wireless broadcast transmissions and reduces channel and storage overhead, thus improving the performance and scalability. The key innovation with respect to wired multicast schemes like DVMRP is the use of flags rather than upstream/downstream link state, making the protocol more robust to mobility. The dynamic reconfiguration capability makes this protocol particularly suitable for mobile networks. The performance of the proposed scheme is evaluated via simulation and is compared to that of DVMRP and global flooding. This revised version was published online in August 2006 with corrections to the Cover Date.     

Optimizing provider recruitment for influenza surveillance networks

The increasingly complex and rapid transmission dynamics of many infectious diseases necessitates the use of new, more advanced methods for surveillance, early detection, and decision-making. Here, we demonstrate that a new method for optimizing surveillance networks can improve the quality of epidemiological information produced by typical provider-based networks. Using past surveillance and Internet search data, it determines the precise locations where providers should be enrolled. When applied to redesigning the provider-based, influenza-like-illness surveillance network (ILINet) for the state of Texas, the method identifies networks that are expected to significantly outperform the existing network with far fewer providers. This optimized network avoids informational redundancies and is thereby more effective than networks designed by conventional methods and a recently published algorithm based on maximizing population coverage. We show further that Google Flu Trends data, when incorporated into a network as a virtual provider, can enhance but not replace traditional surveillance methods.