OBJECTIVE: Estimating the hospitalization risk for people with comorbidities infected by the SARS-CoV-2 virus is important for developing public health policies and guidance. Traditional biostatistical methods for risk estimations require: (i) the number of infected people who were not hospitalized, which may be severely undercounted since many infected people were not tested; (ii) comorbidity information for people not hospitalized, which may not always be readily available. We aim to overcome these limitations by developing a Bayesian approach to estimate the risk ratio of hospitalization for COVID-19 patients with comorbidities. MATERIALS AND METHODS: We derived a Bayesian approach to estimate the posterior distribution of the risk ratio using the observed frequency of comorbidities in COVID-19 patients in hospitals and the prevalence of comorbidities in the general population. We applied our approach to 2 large-scale datasets in the United States: 2491 patients in the COVID-NET, and 5700 patients in New York hospitals. RESULTS: Our results consistently indicated that cardiovascular diseases carried the highest hospitalization risk for COVID-19 patients, followed by diabetes, chronic respiratory disease, hypertension, and obesity, respectively. DISCUSSION: Our approach only needs (i) the number of hospitalized COVID-19 patients and their comorbidity information, which can be reliably obtained using hospital records, and (ii) the prevalence of the comorbidity of interest in the general population, which is regularly documented by public health agencies for common medical conditions. CONCLUSION: We developed a novel Bayesian approach to estimate the hospitalization risk for people with comorbidities infected with the SARS-CoV-2 virus.

BACKGROUND: Species-level classification for 16S rRNA gene sequences remains a serious challenge for microbiome researchers, because existing taxonomic classification tools for 16S rRNA gene sequences either do not provide species-level classification, or their classification results are unreliable. The unreliable results are due to the limitations in the existing methods which either lack solid probabilistic-based criteria to evaluate the confidence of their taxonomic assignments, or use nucleotide k-mer frequency as the proxy for sequence similarity measurement. RESULTS: We have developed a method that shows significantly improved species-level classification results over existing methods. Our method calculates true sequence similarity between query sequences and database hits using pairwise sequence alignment. Taxonomic classifications are assigned from the species to the phylum levels based on the lowest common ancestors of multiple database hits for each query sequence, and further classification reliabilities are evaluated by bootstrap confidence scores. The novelty of our method is that the contribution of each database hit to the taxonomic assignment of the query sequence is weighted by a Bayesian posterior probability based upon the degree of sequence similarity of the database hit to the query sequence. Our method does not need any training datasets specific for different taxonomic groups. Instead only a reference database is required for aligning to the query sequences, making our method easily applicable for different regions of the 16S rRNA gene or other phylogenetic marker genes. CONCLUSIONS: Reliable species-level classification for 16S rRNA or other phylogenetic marker genes is critical for microbiome research. Our software shows significantly higher classification accuracy than the existing tools and we provide probabilistic-based confidence scores to evaluate the reliability of our taxonomic classification assignments based on multiple database matches to query sequences. Despite its higher computational costs, our method is still suitable for analyzing large-scale microbiome datasets for practical purposes. Furthermore, our method can be applied for taxonomic classification of any phylogenetic marker gene sequences. Our software, called BLCA, is freely available at https://github.com/qunfengdong/BLCA .

Optical data center networks (DCNs) are becoming increasingly attractive due to their technological strengths compared with the traditional electrical networks. However, existing optical DCNs are either hard to scale, vulnerable to single point of failure, or provide limited network bisection bandwidth for many practical data center workloads. To this end, we present WaveCube, a scalable, fault-tolerant, high-performance optical DCN architecture. To scale, WaveCube removes MEMS,1a potential bottleneck, from its design. WaveCube is fault-tolerant, since it does not have single point of failure and there are multiple node-disjoint parallel paths between any pair of top-of-rack switches. WaveCube delivers high performance by exploiting multi-pathing and dynamic link bandwidth along the path. For example, our evaluation results show that, in terms of network bisection bandwidth, WaveCube outperforms prior optical DCNs by up to 400% and is 70%-85% of the ideal non-blocking network (ı.e., theoretical upper bound) under both realistic and synthetic traffic patterns. WaveCube's performance degrades gracefully under failures-it drops 20% even with 20% links cut. WaveCube also holds promise in practice-its wiring complexity is orders of magnitude lower than Fattree, BCube, and c-Through at scale, and its power consumption is 35% of them.

Optical data center networks (DCNs) are becoming increasingly attractive due to their technological strengths compared to traditional electrical networks. However, prior optical DCNs are either hard to scale, vulnerable to single point of failure, or provide limited network bisection bandwidth for many practical DCN workloads. To this end, we present WaveCube, a scalable, fault-tolerant, high-performance optical DCN architecture. To scale, WaveCube removes MEMS1, a potential bottleneck, from its design. Wave-Cube is fault-tolerant since it does not have single point of failure and there are multiple node-disjoint parallel paths between any pair of Top-of-Rack (ToR) switches. WaveCube delivers high performance by exploiting multi-pathing and dynamic link bandwidth along the path. Our extensive evaluation results show that WaveCube outperforms previous optical DCNs by up to 400% and delivers network bisection bandwidth that is 70%–85% of an ideal non-blocking network under both realistic and synthetic traffic patterns. WaveCube's performance degrades gracefully under failures — it drops 20% even with 20% links cut. WaveCube also holds promise in practice — its wiring complexity is orders of magnitude lower than Fattree, BCube and c-Through at large scale, and its power consumption is 35% of them.

The wide availability and the Single-Instruction Multiple-Thread (SIMT)-style programming model have made graphics processing units (GPUs) a promising choice for high performance computing. However, because of the SIMT style processing, an instruction will be executed in every thread even if the operands are identical for all the threads. To overcome this inefficiency, the AMD's latest Graphics Core Next (GCN) architecture integrates a scalar unit into a SIMT unit. In GCN, both the SIMT unit and the scalar unit share a single SIMT style instruction stream. Depending on its type, an instruction is issued to either a scalar or a SIMT unit. In this paper, we propose to extend the scalar unit so that it can either share the instruction stream with the SIMT unit or execute a separate instruction stream. The program to be executed by the scalar unit is referred to as a scalar program and its purpose is to assist SIMT-unit execution. The scalar programs are either generated from SIMT programs automatically by the compiler or manually developed by expert developers. We make a case for our proposed flexible scalar unit through three collaborative execution paradigms: data prefetching, control divergence elimination, and scalar-workload extraction. Our experimental results show that significant performance gains can be achieved using our proposed approaches compared to the state-of-art SIMT style processing.

In this paper we design, implement and evaluate NameFilter, a two-stage Bloom filter-based scheme for Named Data Networking name lookup, in which the first stage determines the length of a name prefix, and the second stage looks up the prefix in a narrowed group of Bloom filters based on the results from the first stage. Moreover, we optimize the hash value calculation of name strings, as well as the data structure to store multiple Bloom filters, which significantly reduces the memory access times compared with that of non-optimized Bloom filters. We conduct extensive experiments on a commodity server to test NameFilter's throughput, memory occupation, name update as well as scalability. Evaluation results on a name prefix table with 10M entries show that our proposed scheme achieves lookup throughput of 37 million searches per second at low memory cost of only 234.27 MB, which means 12 times speedup and 77% memory savings compared to the traditional character trie structure. The results also demonstrate that NameFilter can achieve 3M per second incremental updates and exhibit good scalability to large-scale prefix tables.

Regular expression pattern matching is the foundation and core engine of many network functions, such as network intrusion detection, worm detection, traffic analysis, web applications and so on. DFA-based solutions suffer exponentially exploding state space and cannot be remedied without sacrificing matching speed. Given this scalability problem of DFA-based methods, there has been increasing interest in NFA-based methods for memory efficient regular expression matching. To achieve high matching speed using NFA, it requires potentially massive parallel processing, and hence represents an ideal programming task on Graphic Processor Unit (GPU). Based on in-depth understanding of NFA properties as well as GPU architecture, we propose effective methods for fitting NFAs into GPU architecture through proper data structure and parallel programming design, so that GPU's parallel processing power can be better utilized to achieve high speed regular expression matching. Experiment results demonstrate that, compared with the existing GPU-based NFA implementation method [9], our proposed methods can boost matching speed by 29~46 times, consistently yielding above 10Gbps matching speed on NVIDIA GTX-460 GPU. Meanwhile, our design only needs a small amount of memory space, growing exponentially more slowly than DFA size. These results make our design an effective solution for memory efficient high speed regular expression matching, and clearly demonstrate the power and potential of GPU as a platform for memory efficient high speed regular expression matching.

Regular expression matching as the core packet inspection engine of network systems has long been striving to be both fast in matching speed (like DFA) and scalable in storage space (like NFA). Recently, ternary content addressable memory (TCAM) has been investigated as a promising way out, by implementing DFA using TCAM for regular express matching. In this paper, we present the first method for implementing NFA using TCAM. Through proper TCAM encoding, our method matches each input byte with one single TCAM lookup --- operating at precisely the same speed as DFA, while using a number of TCAM entries that can be close to NFA size. These properties make our method an important step along a new path --- TCAM-based NFA implementation --- towards the long-standing goal of fast and scalable regular expression matching.

BACKGROUND: Modern pyrosequencing techniques make it possible to study complex bacterial populations, such as 16S rRNA, directly from environmental or clinical samples without the need for laboratory purification. Alignment of sequences across the resultant large data sets (100,000+ sequences) is of particular interest for the purpose of identifying potential gene clusters and families, but such analysis represents a daunting computational task. The aim of this work is the development of an efficient pipeline for the clustering of large sequence read sets. METHODS: Pairwise alignment techniques are used here to calculate genetic distances between sequence pairs. These methods are pleasingly parallel and have been shown to more accurately reflect accurate genetic distances in highly variable regions of rRNA genes than do traditional multiple sequence alignment (MSA) approaches. By utilizing Needleman-Wunsch (NW) pairwise alignment in conjunction with novel implementations of interpolative multidimensional scaling (MDS), we have developed an effective method for visualizing massive biosequence data sets and quickly identifying potential gene clusters. RESULTS: This study demonstrates the use of interpolative MDS to obtain clustering results that are qualitatively similar to those obtained through full MDS, but with substantial cost savings. In particular, the wall clock time required to cluster a set of 100,000 sequences has been reduced from seven hours to less than one hour through the use of interpolative MDS. CONCLUSIONS: Although work remains to be done in selecting the optimal training set size for interpolative MDS, substantial computational cost savings will allow us to cluster much larger sequence sets in the future.

BACKGROUND: Web-based synteny visualization tools are important for sharing data and revealing patterns of complicated genome conservation and rearrangements. Such tools should allow biologists to upload genomic data for their own analysis. This requirement is critical because individual biologists are generating large amounts of genomic sequences that quickly overwhelm any centralized web resources to collect and display all those data. Recently, we published a web-based synteny viewer, GSV, which was designed to satisfy the above requirement. However, GSV can only compare two genomes at a given time. Extending the functionality of GSV to visualize multiple genomes is important to meet the increasing demand of the research community. RESULTS: We have developed a multi-Genome Synteny Viewer (mGSV). Similar to GSV, mGSV is a web-based tool that allows users to upload their own genomic data files for visualization. Multiple genomes can be presented in a single integrated view with an enhanced user interface. Users can navigate through all the selected genomes in either pairwise or multiple viewing mode to examine conserved genomic regions as well as the accompanying genome annotations. Besides serving users who manually interact with the web server, mGSV also provides Web Services for machine-to-machine communication to accept data sent by other remote resources. The entire mGSV package can also be downloaded for easy local installation. CONCLUSIONS: mGSV significantly enhances the original functionalities of GSV. A web server hosting mGSV is provided at http://cas-bioinfo.cas.unt.edu/mgsv.

Regular expression matching is the core engine of many network functions such as intrusion detection, protocol analysis and so on. In spite of intensive research, we are still in need of a method for fast and scalable regular expression matching, where it takes one simple memory lookup to match each input character (like DFA) and storage space growing linearly with regular expression pattern set size (like NFA). Most recently, TCAM-based DFA implementation has been proposed as a promising approach, for TCAM's unique parallel and wildcard matching capabilities. However, the number of TCAM entries needed is still above exponentially growing DFA size and hence not scalable. In this paper, we propose a chain-based DFA deflation method for fast and scalable regular expression matching using TCAM, which takes one simple TCAM lookup to match each input character and effectively deflates DFA size. Experiments based on real life pattern sets demonstrate that, the number of TCAM entries used by our DFA deflation method is up to two orders of magnitude lower than the DFA size, and comes quite close to the linearly growing NFA size. This not only means superior scalability, but also allows us to implement regular expression matching at extremely fast matching speed, up to two orders of magnitude faster than the existing TCAM-based DFA implementation method.

Multi-class network traffic classification is a fundamental function for network services and management. Support vector machine (SVM) based network traffic classification has recently attracted increasing interest, for its high accuracy and low training sample size requirement. However, to better fit applications with delay requirements, it is desirable to reduce the high computation cost of existing SVM-based traffic classifiers. In this paper, we propose a novel scheme for SVM-based traffic classification (called fuzzy tournament). Experiment results based on real network traffic traces show that our proposed scheme can reduce computation cost by as much as 7.65 times; in the mean time, misclassification ratio is consistently reduced by up to 2.35 times as well.

The paper discusses the implementation of deterministic finite automaton (DFA) using ternary content addressable memory (TCAM) for regular expression matching. Regular expression matching is the foundation of many network functions including intrusion detection, worm detection, traffic analysis and so on, where known patterns such as worm fingerprints are characterized using regular expressions and searched in network traffic for pattern match. As the quantity and diversity of known patterns keep increasing, regular expression pattern sets have rapidly grown in both size and complexity, while having to be matched in network traffic at accelerating wire speeds. Fast and scalable regular expression matching, therefore, is fundamental to the development of practical network systems.Regular expression matching is carried out using either nondeterministic finite automaton (NFA) or deterministic finite automaton (DFA). The paper states that no existing method has been able to deflate exponentially growing DFA state space, without paying penalty on matching efficiency. Fast and scalable regular expression matching, where it takes merely a small constant number of memory accesses to match each input character and storage space growing linearly with pattern set size, remains an open problem calling for innovative research.

BACKGROUND: The analysis of genome synteny is a common practice in comparative genomics. With the advent of DNA sequencing technologies, individual biologists can rapidly produce their genomic sequences of interest. Although web-based synteny visualization tools are convenient for biologists to use, none of the existing ones allow biologists to upload their own data for analysis. RESULTS: We have developed the web-based Genome Synteny Viewer (GSV) that allows users to upload two data files for synteny visualization, the mandatory synteny file for specifying genomic positions of conserved regions and the optional genome annotation file. GSV presents two selected genomes in a single integrated view while still retaining the browsing flexibility necessary for exploring individual genomes. Users can browse and filter for genomic regions of interest, change the color or shape of each annotation track as well as re-order, hide or show the tracks dynamically. Additional features include downloadable images, immediate email notification and tracking of usage history. The entire GSV package is also light-weighted which enables easy local installation. CONCLUSIONS: GSV provides a unique option for biologists to analyze genome synteny by uploading their own data set to a web-based comparative genome browser. A web server hosting GSV is provided at http://cas-bioinfo.cas.unt.edu/gsv, and the software is also freely available for local installations.

SUMMARY: Ergatis is a flexible workflow management system for designing and executing complex bioinformatics pipelines. However, its complexity restricts its usage to only highly skilled bioinformaticians. We have developed a web-based prokaryotic genome annotation server, Integrative Services for Genomics Analysis (ISGA), which builds upon the Ergatis workflow system, integrates other dynamic analysis tools and provides intuitive web interfaces for biologists to customize and execute their own annotation pipelines. ISGA is designed to be installed at genomics core facilities and be used directly by biologists. AVAILABILITY: ISGA is accessible at http://isga.cgb.indiana.edu/ and the system is also freely available for local installation.

Multi-hop wireless networks using directional antennas are increasingly deployed for various applications such as wireless backhaul. In such systems, each node is equipped with a few directional antennas. Each antenna is exclusively used for establishing a point-to-point link with another antenna on some neighboring node. Thus in the constructed network, each node cannot have more links than its number of installed antennas, which defines a degree bound on all nodes. Hence, a practically important problem is to construct fault resilient and high capacity networks with bounded node degree. The main contribution of this paper is two-fold. First, we propose a localized algorithm for building fault resilient wireless networks that contain the path with highest possible capacity for every pair of nodes, not only in normal cases but also in the presence of any node/link failure. Second, we give an algorithm for building fault resilient wireless networks with the lowest possible degree bound.

SUMMARY: The Generic Genome Browser (GBrowse) is one of the most widely used tools for visualizing genomic features along a reference sequence. However, the installation and configuration of GBrowse is not trivial for biologists. We have developed a web server, WebGBrowse that allows users to upload genome annotation in the GFF3 format, configure the display of each genomic feature by simply using a web browser and visualize the configured genomic features with the integrated GBrowse software. AVAILABILITY: WebGBrowse is accessible via http://webgbrowse.cgb.indiana.edu/ and the system is also freely available for local installations.

SUMMARY: Investigating the conservation of gene clusters across multiple genomes has become a standard practice in the era of comparative genomics. However, all existing software and databases rely heavily on pre-computation to identify homologous genes by genome-wide comparisons. Such pre-computing strategies lack accuracy and updating the data is computationally intensive. Since most molecular biologists are often interested only in a small cluster of genes, catering to this need, we have developed a web-based software system that allows users to upload a list of genes, perform dynamic search against the genomes of their choices and interactively visualize the gene cluster conservation using a novel multi-genome browser. Our approach avoids expensive genome-wide pre-computing and allows users to dynamically change the search criteria to fit their genes of interest. Our system can be customized for any genome sequences. We have applied it to both prokaryotic and eukaryotic genomes to illustrate its usability. AVAILABILITY: Our software is freely available at http://cgcv.cgb.indiana.edu/cgi-bin/index.cgi.

Recently, wireless mesh technology has been used for military applications and fast recovery networks, referred to as nomadic wireless mesh networks (NWMNs). In such systems, wireless routers, termed nodes, are mounted on top of vehicles or vessels, which may change their location according to application needs; and the nodes are required to establish a reliable wireless mesh network. For improving network performance, some vendors use directional antennas, and the mesh topology comprises of point-to-point connections between adjacent nodes. The number of point-to-point connections of a node is upper-bounded by the number of directional radios it has, which is typically a small constant. This raises the need to build robust (i.e., two-node/edge- connected) mesh networks with bounded node degree, regardless of node locations. In this paper, we present simple elegant schemes for constructing such efficient and robust wireless mesh networks with provably small constant degree bounds. Our extensive simulations show our schemes build robust and efficient topologies for various settings with node degree bounded by 4 and small hop-count distance between nodes and gateways.

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. In this paper we, therefore, address this load balancing problem for readers - given a set of tags that are within range of each reader, which of these tags should each reader be responsible for such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We show that a generalized variant of the load balancing problem is NP-hard and hence present a 2-approximation centralized algorithm. We next present an optimal centralized solution for a specialized variant. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.

Network coding is seen as a promising technique to improve network throughput. In this paper, we study two important problems in localized network coding in wireless networks, which only requires each node to know about and coordinate with one-hop neighbors. In particular, we first establish a condition that is both necessary and sufficient for useful coding to be possible. We show this condition is much weaker than expected, and hence allows a variety of coding schemes to suit different network conditions and application preferences. Based on the understanding we establish, we are able to design a robust coding technique called loop coding that can improve network throughput and TCP throughput simultaneously.

Packet classification is the foundation of many Internet functions such as QoS and security. A long thread of research has proposed efficient software-based solutions to this problem. Such software solutions are attractive because they require cheap memory systems for implementation, thus bringing down the overall cost of the system. In contrast, hardware-based solutions use more expensive memory systems, e.g., TCAMs, but are often preferred by router vendors for their faster classification speeds. The goal of this paper is to find a "best-of-both-worlds" solution -- a solution that incurs the cost of a software-based system and has the speed of a hardware-based one. Our proposed solution, called smart rule cache achieves this goal by using minimal hardware -- a few additional registers -- to cache evolving rules which preserve classification semantics, and additional logic to match incoming packets to these rules. Using real traffic traces and real rule sets from a tier-1 ISP, we show such a setup is sufficient to achieve very high hit ratios for fast classification in hardware. Cache miss ratios are 2 ∼ 4 orders of magnitude lower than flow cache schemes. Given its low cost and good performance, we believe our solution may create significant impact on current industry practice.

BACKGROUND: Whole genome shotgun sequencing produces increasingly higher coverage of a genome with random sequence reads. Progressive whole genome assembly and eventual finishing sequencing is a process that typically takes several years for large eukaryotic genomes. In the interim, all sequence reads of public sequencing projects are made available in repositories such as the NCBI Trace Archive. For a particular locus, sequencing coverage may be high enough early on to produce a reliable local genome assembly. We have developed software, Tracembler, that facilitates in silico chromosome walking by recursively assembling reads of a selected species from the NCBI Trace Archive starting with reads that significantly match sequence seeds supplied by the user. RESULTS: Tracembler takes one or multiple DNA or protein sequence(s) as input to the NCBI Trace Archive BLAST engine to identify matching sequence reads from a species of interest. The BLAST searches are carried out recursively such that BLAST matching sequences identified in previous rounds of searches are used as new queries in subsequent rounds of BLAST searches. The recursive BLAST search stops when either no more new matching sequences are found, a given maximal number of queries is exhausted, or a specified maximum number of rounds of recursion is reached. All the BLAST matching sequences are then assembled into contigs based on significant sequence overlaps using the CAP3 program. We demonstrate the validity of the concept and software implementation with an example of successfully recovering a full-length Chrm2 gene as well as its upstream and downstream genomic regions from Rattus norvegicus reads. In a second example, a query with two adjacent Medicago truncatula genes as seeds resulted in a contig that likely identifies the microsyntenic homologous soybean locus. CONCLUSION: Tracembler streamlines the process of recursive database searches, sequence assembly, and gene identification in resulting contigs in attempts to identify homologous loci of genes of interest in species with emerging whole genome shotgun reads. A web server hosting Tracembler is provided at http://www.plantgdb.org/tool/tracembler/, and the software is also freely available from the authors for local installations.

Abstract — There is an inherent well-known conflict between fairness and throughput that arises in many networking scenarios. A number of researchers have studied this problem in the context of (single-hop) wireless local area networks (WLANs), where clients directly exchange traffic with access points (APs). More recently, researchers have proposed multi-hop extensions to WLANs where client traffic is forwarded via a series of client-client links. In this paper, we show that the objective of improving throughput without sacrificing fairness can be much better met in multi-hop WLANs. We decouple this objective into two separate but related problems. First, we need an algorithm to organize clients into a multi-hop structure such that fair bandwidth allocation within this structure leads to improved throughput. Second, we need algorithms for performing fair bandwidth allocation within the determined multi-hop structure. In this paper, we first design optimal fair bandwidth allocation algorithms for both max-min throughput fairness and max-min time fairness in multi-hop WLANs. Subsequently, design an efficient algorithm to find desirable multi-hop structures. With slight modification, our results in this paper can be generalized to other multi-hop wireless networks, such as the emerging wireless backhaul networks and wireless mesh networks. Our proposed solutions seamlessly integrate with legacy devices and hence are incrementally deployable. Simulation results demonstrate that our solutions can effectively improve throughput (by up to 114% or more) as well as network coverage while preserving fairness. I.

Probabilistic packet marking is a general technique which routers can use to reveal internal network information to end-hosts. Such information is probabilistically set by the routers in headers of regular IP packets on their way to destinations. A number of potential applications have been identified, such as IP traceback, congestion control, robust routing algorithms, dynamic network reconfiguration, and locating Internet bottlenecks, etc. In this paper, we define EPPM, an efficient general probabilistic packet marking scheme with a wide range of potential applications, of which locating Internet bottlenecks and IP traceback are investigated as two representative examples to demonstrate its effectiveness. Our proposed scheme imposes only a single-bit overhead in the IP packet headers. More importantly, it significantly reduces the number of IP packets required to convey the relevant information when compared to the prior best known scheme (almost by two orders of magnitude).

Maximizing system lifetime in battery-powered wireless sensor networks with power aware topology control protocols and routing protocols has received intensive research. In the past, this problem has been mostly studied from the indirect perspective of energy conservation. Although this leads to solutions that help extend network lifetime, energy conservation is not the same problem as network lifetime maximization. Some researchers have formally studied network lifetime maximization problems, based on the assumption that energy is only consumed by packet transmission. However, it is well known that in many cases energy is significantly consumed during idle periods and overhearing. In this paper, we try to present a survey and formal analysis of a variety of network lifetime maximization problems in different energy consumption models. In particular, we identify different energy consumption models, define a variety of fundamental network lifetime maximization problems in individual energy consumption models, and formally analyze their complexities. Polynomial time algorithms are presented for tractable problems, and NP-hardness proofs are presented for intractable problems.

We address the problem of energy-efficient reliable wireless communication in the presence of unreliable or lossy wireless link layers in multi-hop wireless networks. Prior work [1] has provided an optimal energy efficient solution to this problem for the case where link layers implement perfect reliability. However, a more common scenario --- a link layer that is not perfectly reliable, was left as an open problem. In this paper we first present two centralized algorithms, BAMER and GAMER, that optimally solve the minimum energy reliable communication problem in presence of unreliable links. Subsequently we present a distributed algorithm, DAMER, that approximates the performance of the centralized algorithm and leads to significant performance improvement over existing single-path or multi-path based techniques.