15452852
Battery-aware router scheduling in wireless mesh networks
Wireless mesh networks emerge as a flexible, low-cost and multipurpose networking platform with wired infrastructure connected to the Internet. A critical issue in mesh networks is to maintain network activities for a long lifetime with high energy efficiency. As more and more outdoor applications require long-lasting, high energy efficient and continuously-working mesh networks with battery-powered mesh routers, it is important to optimize the performance of mesh networks from a battery-aware point of view. Study in battery technology reveals that discharging of a battery is nonlinear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. Intuitively, to optimize network performance, a mesh router should recover its battery periodically to prolong the lifetime. In this paper, we introduce a mathematical model on battery discharging duration and lifetime for wireless mesh networks. We also present a battery lifetime optimization scheduling algorithm (BLOS) to maximize the lifetime of battery-powered mesh routers. Based on the BLOS algorithm, we further consider the problem of using battery powered routers to monitor or cover a few hot spots in the network. We refer to this problem as the spot covering under BLOS policy problem (SCBP). We prove that the SCBP problem is NP-hard and give an approximation algorithm called the spanning tree scheduling (STS) to dynamically schedule mesh routers. The key idea of the STS algorithm is to construct a spanning tree according to the BLOS policy in the mesh network. The time complexity of the STS algorithm is O(r) for a network with r mesh routers. Our simulation results show that the STS algorithm can greatly improve the lifetime, data throughput and power consumption efficiency of a wireless mesh network
18001096
Optimal scheduling algorithms in WDM optical interconnects with limited range wavelength conversion capability
Optical communication is a promising candidate for many emerging networking and parallel/distributed computing applications because of its huge bandwidth. Wavelength division multiplexing (WDM) is a technique that can better utilize the optical bandwidth by dividing the bandwidth of a fiber into multiple wavelength channels. In this paper, we study optimal scheduling algorithms to resolve output contentions in bufferless time slotted WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion with arbitrary conversion capability, as limited range wavelength conversion is easier to implement and more cost effective than full range wavelength conversion, and it also includes full range wavelength conversion as a special case. We first consider the conversion scheme in which each wavelength can be converted to multiple wavelengths in an interval of wavelengths and the intervals for different wavelengths are "ordered". We show that the problem of maximizing network throughput can be formalized as finding a maximum matching in a bipartite graph. We then give an optimal scheduling algorithm called the first available algorithm that runs in O(k) time, where k is the number of wavelengths per fiber. We also study the case where the connection requests have different priorities. We formalize the problem as finding an optimal matching in a weighted bipartite graph and give a scheduling algorithm called the downwards expanding algorithm that runs in O(kD + Nklog(Nk)) time where N is the number of input fibers of the interconnect and D is the conversion degree. Finally, we consider the circular symmetrical wavelength conversion scheme and give optimal scheduling algorithms for nonprioritized scheduling in O(Dk) time and prioritized scheduling in O(k/sup 2/+Nklog(Nk)) time.
12591737
Distributed scheduling algorithms for wavelength convertible WDM optical interconnects
Optical communication is attracting more and more attention because of its huge bandwidth to meet the ever increasing demand of emerging computing/networking applications. In this paper we study distributed scheduling algorithms to resolve output contentions in WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion, including the full range wavelength conversion. Two types of limited range wavelength conversions, circular symmetrical and non circular symmetrical, are studied. We introduce the request graph and show that finding the largest group of contention-free connection requests to achieve maximum network throughput is equivalent to finding a maximum matching in the request graph. Compared with the existing algorithm for finding a maximum matching in an arbitrary bipartite graph with time complexity O(N/sup 3/2/ k /sup 3/2/d), the algorithms we present have time complexity of O(k) and O(dk) (independent of interconnect size N) for non-circular symmetrical and circular symmetrical wavelength conversion, respectively, where k is the number of wavelengths per fiber and d is the conversion degree. In addition, our algorithms can be easily implemented in hardware, and used for time slotted WDM optical interconnects where connections hold for different number of time slots.
18081212
A novel analytical model for electronic and optical switches with shared buffer
Switches with shared buffer have lower packet loss probabilities than other types of switches when the sizes of the buffers are the same. In the past, the performance analysis for electronic shared buffer switches has been carried out extensively. However, due to the strong dependencies of the output queues in the buffer, it is very difficult to find a good analytical model. Existing models are either accurate but have exponential complexities or not very accurate. In this paper, we propose a novel analytical model called the aggregation model for switches with shared buffer. This model can be used for analyzing both electronic and optical switches, and has perfect accuracies under all tested conditions and has polynomial time complexity. It is based on the idea of induction: first find the behavior of 2 queues, then aggregate them into one block; then find the behavior of 3 queues while regarding 2 of the queues as one block, then aggregate the 3 queues into one block; then aggregate 4 queues and so on. When a sufficient number of queues have been aggregated, the behavior of the entire switch is found. We believe that the new model represents the best analytical model for shared buffer switches so far.
14844081
Constructing battery-aware virtual backbones in sensor networks
A critical issue in wireless sensor networks is to construct energy efficient virtual backbones for routing, broadcasting and data propagating. The minimum connected dominating set (MCDS) has been proposed as a backbone to reduce power dissipation and prolong network lifetime. However, we find that an MCDS cannot guarantee maximum network lifetime as it does not consider the battery discharging behavior. Recent study in battery technology reveals that the discharging of a battery is not linear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. In order to optimize network performance and construct an energy efficient virtual backbone in sensor networks, battery-awareness should be considered. In this paper we first study the mathematical battery discharging model and provide a simplified battery model suitable for implementation in sensor networks. We then introduce the concept of battery-aware connected dominating set (BACDS) and show that in general the BACDS can achieve longer lifetime than the MCDS. Then we show that finding a minimum BACDS (MBACDS) is NP-hard and give a distributed approximation algorithm to construct the BACDS. The resulting BACDS constructed by our algorithm is at most (8+/spl Delta/)opt size where /spl Delta/ is the maximum node degree and opt is the size of an optimal BACDS. The time and message complexities of the algorithm are O(n) and O(n(/spl radic/n+logn+/spl Delta/)), respectively, where n is the number of nodes in the network. The simulation results show that the BACDS constructed by our algorithm can save a significant amount of energy and achieve up to 30% longer network lifetime than the MCDS. To the best of our knowledge, this is the first work considering battery-awareness in the construction of connected dominating sets.
17015903
Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability
All optical networking is a promising candidate for supporting high-speed communications because of the huge bandwidth of optics. In this paper, we study optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability. We formalize the problem of maximizing network throughput and minimizing total delay as a problem of finding an optimal matching in a weighted bipartite graph. We then give a simple algorithm, called the Scan and Swap Algorithm, that finds the optimal matching in O(kB) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to directly adopting other existing algorithms that need at least O(k/sup 2/N/sup 2/ + k/sup 2/BN) time, where N is the number of input fibers.
5700504
Localized algorithm for aggregate fairness in wireless sensor networks
For data-collection applications in sensor networks, it is important to ensure all data sources have equal (or weighted) access to network bandwidth so that the base stations receive a complete picture about the monitored area. We point out the fairness problem in the current design of sensor networks, which may cause extremely biased bandwidth allocations. It is a challenge to design a fully distributed fairness solution due to the lack of global knowledge about the distribution of data sources and their routing paths. This paper proposes a new aggregate fairness model and a localized algorithm (called AFA) that implements the model. AFA is designed to work with any routing protocol. In particular, it allows the packets from a data source to follow an arbitrary set of forwarding paths to the base stations. This flexibility makes it considerably harder to allocate bandwidth fairly among different data sources. AFA solves the problem with only localized operations at the sensors. It is easy to implement, which is an attractive property for sensor networks. Moreover, the algorithm automatically adjusts a sensor's forwarding rate to avoid packet drops due to downstream congestion, which helps improve energy efficiency. We perform extensive simulations, demonstrating that the proposed algorithm can effectively improve end-to-end fairness.
6152130
Estimation via compressed information
Some results from classical estimation theory are extended to the case in which data must be communicated from several places where observations are made to the place where the estimate is generated. Particular emphasis is placed on determining how the variance of an unbiased estimator depends on the communication rates. Explicit result are given for Gaussian sources. >
32960689
On Maximal Shadows of Members in Left-compressed Sets
Whereas Stanley, Proctor and others studied Sperner properties of the poset L(k,m) we consider shadows of left-compressed sets and derive asymptotic bounds on their sizes.
782860
Exploiting as hierarchy for scalable route selection in multi-homed stub networks
Multi-homing is a common practice among many (especially large) customer (or stub) networks. Although the purpose of multi-homing is primarily for enhanced reliability, it has also increasingly been used for load balancing and latency reduction. In this paper, we address the problem of how to perform <i>scalable</i> route selection in a multi-homed <i>stub</i> network to optimize network latency to various destinations as measured by round-trip-time (RTT). A straight forward method is to simply perform RTT measurements (e.g., using ping) to each destination via each provider and select the one with the minimum RTT as the "best" next-hop to the destination. Is there a more.
 To answer this question, we carry out a measurement-based study to analyze the differences of RTTs in using two different providers in a multi-homed stub network to reach a large number of randomly selected destinations. Our study reveals that because of the AS hierarchy, for a large fraction of the network prefixes, the two AS paths through two providers merge in the core of the Internet. Furthermore, the router at which the two router level paths merge is actually in the AS at which the AS level paths merge. This phenomenon causes the RTT difference between the two paths through the two providers to be determined by the <i>non shared</i> portion of the paths. Our study reveals that most of the two router level paths through the two upstream providers merge at the AS at which the two AS level paths merge. Based on this finding, we devise a scalable route (next-hop provider) selection algorithm using BGP information in a multi-homed stub network. We also present a preliminary evaluation.
26926083
Local Multiple Alignment Via Subgraph Enumeration
Abstract We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.