Search

Data transmission from sensor nodes to a base station or a sink node often incurs significant energy consumption, which critically affects network lifetime. We generalize and solve the problem of deploying multiple base stations to maximize network lifetime in terms of two different metrics under one-hop and multihop communication models. In the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution and a heuristic approach based on the minimal enclosing circle algorithm to deploy a base station at the geometric center of each cluster. In the multihop communication model, both base station location and data routing mechanism need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing paths for data transmission. Simulation results show the distinguished performance of the proposed deployment algorithms in maximizing network lifetime.

There are an increasing number of high-performance networks that provision dedicated channels through circuit-switching or MPLS/GMPLS techniques to support bulk data transfer in large-scale science or e-commerce applications. These dedicated links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time periods. Therefore, efficient advance bandwidth reservation algorithms are needed to improve the utilization of network resources and meet the transport requirements of application users. We investigate the bandwidth-oriented path computation problem for two types of data transfer: (i) fixed path with variable bandwidth and (ii) variable path with variable bandwidth to minimize the transfer end time of a given data size. We prove that both problems are NP-complete and propose a heuristic algorithm for each of them. Extensive simulation results illustrate the performance superiority of the proposed heuristics over methods based on greedy strategies.

UNLABELLED High-throughput genomic technologies enable researchers to identify genes that are co-regulated with respect to specific experimental conditions. Numerous statistical approaches have been developed to identify differentially expressed genes. Because each approach can produce distinct gene sets, it is difficult for biologists to determine which statistical approach yields biologically relevant gene sets and is appropriate for their study. To address this issue, we implemented Latent Semantic Indexing (LSI) to determine the functional coherence of gene sets. An LSI model was built using over 1 million Medline abstracts for over 20,000 mouse and human genes annotated in Entrez Gene. The gene-to-gene LSI-derived similarities were used to calculate a literature cohesion p-value (LPv) for a given gene set using a Fisher's exact test. We tested this method against genes in more than 6,000 functional pathways annotated in Gene Ontology (GO) and found that approximately 75% of gene sets in GO biological process category and 90% of the gene sets in GO molecular function and cellular component categories were functionally cohesive (LPv

An increasing number of high performance research network testbeds and production networks have the capability of provisioning dedicated channels for high speed data transfer in support of large scale scientific applications. Each dedicated channel in these networks typically consists of one or more physical links that are shared by multiple applications in both time and bandwidth through in advance reservation. The design of efficient bandwidth scheduling algorithms is critical to maximizing the utilization of dedicated network resources and meeting diverse end-to-end transport performance requirements. The topology of a dedicated network is represented by a graph, where each link maintains a list of residual bandwidths specified as segmented constant functions of time. Given a graph with an aggregated time-bandwidth table combining the reservation information on all links, designated source, and destination vertices, and a specified data size, we formulate and investigate five bandwidth scheduling problems to minimize the data transfer end time under different path and bandwidth constraints: (i) variable path with variable bandwidth (VPVB), which computes the widest (highest bandwidth) path in each time slot; (ii) fixed path with variable bandwidth (FPVB), which computes a fixed path with varying bandwidths across different time slots; (iii) variable path with fixed bandwidth (VPFB), which computes one path in each time slot with the same bandwidth; (iv) fixed path with fixed bandwidth (FPFB), which computes a fixed path with a constant bandwidth; and (v) multiple fixed paths with fixed bandwidths (MFPFB), which computes multiple concurrent fixed paths with constant bandwidths. Among these problems, VPVB represents the most flexible scenario where the network resources are fully utilized and the minimal transfer end time is achieved, while FPFB imposes the most stringent transport conditions by fixing both path and bandwidth. We design an optimal algorithm for each of these scheduling problems. VPVB is solved using an extension of the classical Dijkstra's algorithm, and FPVB is solved using Maximum Permutation Algorithm, which tries all possible permutations of throughputs at different time slots to obtain the minimal transfer end time. The algorithm for VPFB, FPFB, and MFPFB are based on Adjacent Time Slots Search, which finds the minimum transfer end time by examining the possibility of data transfer in any number of contiguous time slots. All these algorithms are of polynomial or pseudo polynomial time complexity with respect to the network size and the total number of time slots in a bandwidth reservation table.