Quorum-based power-saving (QPS) protocols have been proposed for ad hoc networks (e.g., IEEE 802.11 ad hoc mode) to increase energy efficiency and prolong the operational time of mobile stations. These protocols assign to each station a cycle pattern that specifies when the station should wake up (to transmit/receive data) and sleep (to save battery power). In all existing QPS protocols, the cycle length is either identical for all stations or is restricted to certain numbers (e.g., squares or primes). These restrictions on cycle length severely limit the practical use of QPS protocols as each individual station may want to select a cycle length that is best suited for its own need (in terms of remaining battery power, tolerable packet delay, and drop ratio). In this paper, we propose the notion of hyper quorum system (HQS)-a generalization of QPS that allows for arbitrary cycle lengths. We describe algorithms to generate two different classes of HQS given any set of arbitrary cycle lengths as input. We also describe how to find the optimal cycle length for a station to maximize energy efficiency, subject to certain performance constraints. We then present analytical and simulation results that show the benefits of HQS-based power-saving protocols over the existing QPS protocols. The HQS protocols yield up to 41% improvement in energy efficiency under heavy traffic loads while eliminating more than 90% delay drops under light traffic loads.

The Support Vector Machines (SVMs) have been widely used for classification due to its ability to give low generalization error. In many practical applications of classification, however, the wrong prediction of a certain class is much severer than that of the other classes, making the original SVM unsatisfactory. In this paper, we propose the notion of Asymmetric Support Vector Machine (ASVM), an asymmetric extension of the SVM, for these applications. Different from the existing SVM extensions such as thresholding and parameter tuning, ASVM employs a new objective that models the imbalance between the costs of false predictions from different classes in a novel way such that user tolerance on false-positive rate can be explicitly specified. Such a new objective formulation allows us of obtaining a lower false-positive rate without much degradation of the prediction accuracy or increase in training time. Furthermore, we show that the generalization ability is preserved with the new objective. We also study the effects of the parameters in ASVM objective and address some implementation issues related to the Sequential Minimal Optimization (SMO) to cope with large-scale data. An extensive simulation is conducted and shows that ASVM is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.

Location-based channel access protocols have been proposed as a means to broadcast safety related messages through inter-vehicle communications. The protocols divide the road into fixed-size cells and assign a channel to each cell. To broadcast, a vehicle would use the channel assigned to the cell it is currently traveling within. To improve bandwidth utilization, a vehicle may acquire channels dynamically from adjacent cells that are not occupied by other vehicles. In a TDMA setting where each channel is a time slot, message delay occurs as the vehicle must wait for the arrival of the next time slot it owns. This message delay time depends heavily on the adopted cell-to-channel mapping function. We examine an existed naive channel allocation scheme and proposed three new ones. An analysis shows that the proposed schemes may reduce the delay by 50% to 90% .

Several contention-based Medium Access Control (MAC) protocols have been proposed for the vehicles to gain the radio channels to distribute active safety messages timely, e.g., Safety Critical Application (SCA) information, for inter-vehicle communications in Vehicular Ad Hoc Networks (VANETs). In these MAC protocols, a contention period is introduced before the vehicle for channel access so that we may not have the timely and reliably message dissemination in VANETs. To reduce the contention period, this paper proposes a Region-based Clustering Mechanism (RCM) to be applied in these MAC protocols. We propose analytical models to investigate the performance of the RCM, which are validated by the simulation experiments.

Clustering in wireless ad hoc networks has shown to be a promising technique to ensure the scalability and efficiency of various communication protocols. Since stations in these networks are usually equipped with batteries as the power source, it is critical to ensure the energy efficiency of a clustering scheme. The Quorum-based Power Saving (QPS) protocols are widely studied over the past years, as they render extensive energy conservation comparing to the IEEE 802.11 Power Saving (PS) mode. However, most existing QPS protocols adopt a symmetric design where each pair of stations in a network are guaranteed to discover each other. Observing that in clustered environments there is no need to insist on all-pair neighbor discovery, we propose an Asymmetric Cyclic Quorum (ACQ) system. The ACQ system guarantees the neighbor discovery between each member node and the clusterhead in a cluster, and between clusterheads in the network. We show that by taxing slightly more energy consumption on the clusterhead, the average energy consumption of stations in a cluster can reduce substantially than can be achieved by traditional QPS protocols. A novel construction scheme is proposed in this work, which assembles the ACQ system in O(1) time. The constructing scheme is adaptive. Stations in a cluster can adjust their awake/sleep ratio collaboratively to strike the balance between energy efficiency and delay under various cluster conditions. Simulation results show that the ACQ system outperforms the previous studies up to 52% in energy efficiency, while introducing no extra worst-case latency.

Intelligent Transportation Systems (ITS) improve passenger/pedestrian safety and transportation productivity through the use of vehicle-to-vehicle and vehicle-to-roadside wireless communication technologies. Communication protocols in these environments must meet strict delay requirements due to the high moving speed of the vehicles. In this paper, we propose an energy-conservative MAC layer protocol, named DSRC-AA, based on IEEE 802.11 that provides power saving to the ITS communication modules (e.g., On Board Units, portable devices, and Road Side Units) while ensuring the bounded delay. DSRC-AA, a generalization of the Asynchronous Quorum-based Power-Saving (AQPS) protocols, capitalizes on the clustering nature of moving vehicles and assigns different wake-up/sleep schedules to the clusterhead and the members of a cluster. DSRC-AA is able to dynamically adapt the schedules to meet the communication delay requirements at various vehicle moving speed. Simulation results show that DSRC-AA is able to yield more than 44 percent reduction in average energy consumption as compared with the existing AQPS protocols, if to be used in vehicular networks.

We study the power-aware buffering problem in battery-powered sensor networks, focusing on the fixed-size and fixed-interval buffering schemes. The main motivation is to address the yet poorly understood size variation-induced effect on power-aware buffering schemes. Our theoretical analysis elucidates the fundamental differences between the fixed-size and fixed-interval buffering schemes in the presence of data-size variation. It shows that data-size variation has detrimental effects on the power expenditure of the fixed-size buffering in general, and reveals that the size variation induced effects can be either mitigated by a positive skewness or promoted by a negative skewness in size distribution. By contrast, the fixed-interval buffering scheme has an obvious advantage of being eminently immune to the data-size variation. Hence the fixed-interval buffering scheme is a risk-averse strategy for its robustness in a variety of operational environments. In addition, based on the fixed-interval buffering scheme, we establish the power consumption relationship between child nodes and parent node in a static data-collection tree, and give an in-depth analysis of the impact of child bandwidth distribution on the parent's power consumption. This study is of practical significance: it sheds new light on the relationship among power consumption of buffering schemes, power parameters of radio module and memory bank, data arrival rate, and data-size variation, thereby providing well-informed guidance in determining an optimal buffer size (interval) to maximize the operational lifespan of sensor networks.

The Quorum-based Power Saving (QPS) protocols have been proposed to increase the energy efficiency of wireless communication. However, it remains challenging to apply existing QPS protocols to the Mobile Ad Hoc Networks (MANETs) as the timers of nodes are usually asynchronous, the incurred delay are expected to be adaptive, and the network topology is asymmetric. In this paper, we propose an Asynchronous, Adaptive, and Asymmetric (AAA) power management protocol that fulfills the unique requirements of MANETs. We present the asymmetric grid quorum system, a generalization of traditional grid-based quorum systems, to ensure the network connectivity. Theoretical analysis is conducted to demonstrate the benefits of AAA over previous arts.

Quorum-based power saving (QPS) protocols have been proposed for ad hoc networks (e.g., IEEE 802.11 ad hoc mode) to increase energy efficiency and prolong the operational time of mobile stations. These protocols assign to each station a cycle pattern that specifies when the station should wake up (to transmit/receive data) and sleep (to save battery power). In all existing QPS protocols, the cycle length is either identical for all stations or is restricted to certain numbers (e.g. squares or primes). These restrictions on cycle length severely limit the practical use of QPS protocols as each individual station may want to select a cycle length that is best suited for its own need (in terms of remaining battery power, tolerable packet delay, and drop ratio). In this paper we propose the notion of hyper quorum system (HQS)-a generalization of QPS that allows for arbitrary cycle lengths. We describe algorithms to generate two different classes of HQS given any set of arbitrary cycle lengths as input. We then present analytical and simulation results that show the benefits of HQS-based power saving protocols over the existing QPS protocols.

Many practical applications of classification require the classifier to produce a very low false-positive rate. Although the Support Vector Machine (SVM) has been widely applied to these applications due to its superiority in handling high dimensional data, there are relatively little effort other than setting a threshold or changing the costs of slacks to ensure the low false-positive rate. In this paper, we propose the notion of Asymmetric Support VectorMachine (ASVM) that takes into account the false-positives and the user tolerance in its objective. Such a new objective formulation allows us to raise the confidence in predicting the positives, and therefore obtain a lower chance of false-positives. We study the effects of the parameters in ASVM objective and address some implementation issues related to the Sequential Minimal Optimization (SMO) to cope with large-scale data. An extensive simulation is conducted and shows that ASVM is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.

The K-nearest neighbors (KNN) query has been of significant interest in many studies and has become one of the most important spatial queries in mobile sensor networks. Applications of KNN queries may include vehicle navigation, wildlife social discovery, and squad/platoon searching on the battlefields. Current approaches to KNN search in mobile sensor networks require a certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free itinerary-based approach called density-aware itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme takes into account several challenging issues such as the trade-off between degree of parallelism and network interference on query response time, and the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. To optimize the performance of DIKNN, a detailed analytical model is derived that automatically determines the most suitable degree of parallelism under various network conditions. This model is validated by extensive simulations. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as kappa increases and as the sensor node mobility increases. It outperforms the second runner with up to a 50 percent saving in energy consumption and up to a 40 percent reduction in query response time, while rendering the same level of query result accuracy.

Current approaches to k nearest neighbor (KNN) search in mobile sensor networks require certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free, itinerary-based approach called density-aware itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme also takes into account challenging issues such as the the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as k increases and as the sensor node mobility increases. It outperforms the second runner with up to 50% saving in energy consumption and up to 40% reduction in query response time, while rendering the same level of query result accuracy.

This paper presents a study on the impact of buffering schemes on wireless sensor power consumption. Two common buffering paradigms are studied: fixed-size buffering and fixed-interval buffering. We present theoretical analyses of the power consumption of the buffering schemes, in relation to parameters of the sensor node's wireless radio and memory modules, as well as the sensor data arrival rate. Our results indicate that, under the same circumstances, the optimal fixed-size buffering scheme outperforms the optimal fixed-interval scheme in terms of overall power conservation. We also show that a power-aware buffering scheme can save significant energy consumption over a power-oblivious buffering scheme, thus prolonging the useful lifespan of the sensor nodes.

Load balancing for distributed servers is a common issue in many applications and has been extensively studied. Several distributed load balancing schemes have been proposed that proactively route individual requests to appropriate servers to best balance the load and shorten request response time. These schemes do not require a centralized load balancer. Instead, each server is responsible for determining, for each request it receives from a client, to which server in the pool the request should be forwarded for processing. We propose a new request routing scheme that is more scalable to increasing number of servers and request load than the existing schemes. The method combines random server selection and next-neighbor load sharing techniques that together prevent the staleness of load information from building up when the number of servers increases. Our simulation shows that it outperforms existing schemes under a piggyback-based load update model.

The need of a data stream management system (DSMS), with the capability of querying continuous data streams, has been well understood by the database research community. We provide an overview on a DSMS prototype called T2. T2 inherits some of the concepts of an early prototype, Tribeca [M. Sullivan et al. (1998)], developed also at Telcordia, but with complete new design and implementation in Java with an SQL-like query language. Our goal is to build a framework that provides a programming infrastructure as well as useful operators to support stream processing in different applications. We set our first targeted application to healthcare biosensor networks, where we applied T2 to monitoring and analyzing electrocardiogram (ECG) data streams, arriving via wireless networks from mobile subjects wearing ECG sensors. Monitoring remote patients via wireless sensors not only provides convenience and safety assurance to the patients, but also saves health care cost in many aspects.

Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering schemeD, itsresponse timewith respect to a queryQ,rt(Q), is defined to be the maximum number of data blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks inQandMis the number of disks, thenrt(Q) is at least ⌈|Q|/M⌉. One way to evaluate the performance ofDwith respect to a set of range queries Q is to measure itsadditive error---the maximum difference ofrt(Q) from ⌈|Q|/M⌉ over all range queriesQ∈ Q.In this article, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in ad-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that for a fixed dimensiond≥ 2, any declustering scheme on anMdgrid, a grid with lengthMon each dimension, will always incur an additive error with respect to range queries of Ω(logM) whend= 2 and Ω(logd−1/2M) whend> 2.Asymptotically optimal declustering schemes exist for 2-dimensional data. However, the best general upper bound known so far for the worst-case additive errors ofd-dimensional declustering schemes,d≥ 3, isO(Md−1), which is large when compared to the lower bound. In this article, we propose two declustering schemes based on low-discrepancy points ind-dimensions. Whendis fixed, both schemes have an additive error ofO(logd−1M) with respect to range queries, provided that certain conditions are satisfied: the first scheme requires that the side lengths of the grid grow at a rate polynomial inM, while the second scheme requiresd≥ 2 andM=ptwhered≤p≤C,Ca constant, andtis a positive integer such thatt(d− 1) ≥ 2. These are the first multidimensional declustering schemes with additive errors proven to be near optimal.

Aside from enhancing data availability during disk failures, replication of data is also used to speed up I/O performance of read-intensive applications. There are two issues that need to be addressed: (a) data placement (Which disks should store the copies of each data block?) and (b) scheduling (Given a query Q, and a placement scheme P of the data, from which disk should each block in Q be retrieved so that retrieval time is minimized?) In this paper, we consider range queries and assume that the dataset is a multidimensional grid and r copies of each unit block of the grid must be stored among M disks. To accurately measure performance of a scheduling algorithm, we consider a metric that takes into account the scheduling overhead as well as the time it takes to retrieve the data blocks from the disks. We describe several combinations of data placement schemes and scheduling algorithms and analyze their performance for range queries with respect to the above metric. We then present simulation results for the most interesting case r=2, showing that the strategies do perform better than the previously known method, especially for large queries.

Multi-disk systems, coupled with declustering schemes, have been widely used in various applications to improve I/O performance by enabling parallel disk accesses. A declustering scheme determines how data blocks should be placed among multiple disks to maximize the parallelism. We focus on the problem of declustering grid-structured multidimensional data with the objective of reducing the response time for range queries. Because of the combinatorial nature of the problem, it is not computationally feasible to perform an exhaustive search for the best scheme for large values of $M$ (the number of disks). In this paper, we present an efficient technique for building good-performance declustering schemes for large values of $M$, based on known good declustering schemes for small values of $M$. We analyze the performance of the declustering schemes generated by this hierarchical technique, giving tight bounds on their query response times. For example we show, in two dimensions, that using optimal declustering schemes for $M_1$ and $M_2$ disks we can construct a scheme for $M_1\times M_2$ disks whose response time, expressed in terms of the maximum number of data blocks to be retrieved from any of the disks, is at most five more than the optimal response time. Our technique generalizes to any value of $M$ in two dimensions and selected values of $M$ in higher dimensions. We also present simulation results to show the effectiveness of these schemes in practice.

We propose a new declustering scheme for allocating uniform multidimensional data among parallel disks. The scheme, aimed at reducing disk access time for range queries, is based on Golden Ratio Sequences for two dimensions and Kronecker Sequences for higher dimensions. Using exhaustive simulation, we show that, in two dimensions, the worst-case (additive) deviation of the scheme from the optimal response time for any range query is one when the number of disks (M) is at most 22; its worst-case deviation is two when M /spl les/ 94; and its worst-case deviation is four when M /spl les/ 550. In two dimensions, we prove that whenever M is a Fibonacci number, the average performance of the scheme is within 14 percent of the (generally, unachievable) strictly optimal scheme and its worst-case response time is within a multiplicative factor three of the optimal response time for any query, and within a factor 1.5 of the optimal for large queries. We also present comprehensive simulation results, on two-dimensional as well as on higher-dimensional data, that compare and demonstrate the advantages of our scheme over some recently proposed schemes in the literature.

Top-k queries arise naturally in many database applications that require searching for records whose attribute values are close to those specified in a query. We study the problem of processing a top-k query by translating it into an approximate range query that can be efficiently processed by traditional relational DBMSs. We propose a sampling-based approach, along with various query mapping strategies, to determine a range query that yields high recall with low access cost. Our experiments on real-world datasets show that, given the same memory budgets, our sampling-based estimator outperforms a previous histogram-based method in terms of access cost, while achieving the same level of recall. Furthermore, unlike the histogram-based approach, our sampling-based query mapping scheme scales well for high dimensional data and is easy to implement with low maintenance cost.

Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme D, its response time with respect to a query Q, rt(Q), is defined to be the maximum number of disk blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks in Q and M is the number of disks then rt(Q) is at least |Q|/M. One way to evaluate the performance of D with respect to a set of queries 𝑄 is to measure its additive error - the maximum difference between rt(Q) from |Q|/M over all range queries Q ε 𝑄.In this paper, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a d-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that such declustering schemes will have an additive error of Ω(log M) when d = 2 and Ω(log d-1/2 M) when d > 2 with respect to range queries.Asymptotically optimal declustering schemes exist for 2-dimensional data. For data in larger dimensions, however, the best bound for additive errors is O(Md-1), which is extremely large. In this paper, we propose the two declustering schemes based on low discrepancy points in d-dimensions. When d is fixed, both schemes have an additive error of O(logd-1 M) with respect to range queries provided certain conditions are satisfied: the first scheme requires d ≥ 3 and M to be a power of a prime where the prime is at least d while the second scheme requires the size of the data to grow within some polynomial of M, with no restriction on M. These are the first known multidimensional declustering schemes with additive errors near optimal.

Declustering schemes enable parallel data retrieval by placing data blocks across multiple disk devices. Various declustering schemes have been proposed for multidimensional data to reduce the response time of range queries. However, efficient schemes, which must be easy to compute and provide good performance, are only known for a restricted number of disks and dimensions. In this paper, we propose a novel technique to construct efficient multidimensional declustering schemes, for any number of disks and dimensions. Simulation results show that the new schemes outperform the best previously-known non-exhaustive search-based multidimensional declustering schemes.

Linear algebra-based techniques have long been used to correlate similar documents. They map the documents to a multidimensional vector space, in which each document is represented by a vector. Searching related documents then translates into searching nearest neighbors in the vector space. We propose an indexing structure, called cosine R-tree, which indexes multidimensional vector space and provides efficient nearest neighbor search. Our preliminary results show that it gives better performance than a brute-force linear scan strategy.

To effectively compete in the competitive telecommunications marketplace, telecommunication service providers need to execute business transactions and exchange business information electronically with each other. The article describes Telcordica/sup TM/ Exchange Link, an interconnection clearinghouse that has been developed at Telcordia Technologies specifically to support B2B exchanges in the telecommunications industry.

We propose a new data declustering scheme for range queries. Our scheme is based on Golden Ratio Sequences (GRS), which have found applications in broadcast disks, hashing, packet routing, etc. We show by analysis and simulation that GRS is nearly the best possible scheme for 2-dimensional range queries. Specifically, it is the best possible scheme when the number of disks (M) is at most 22; has response time at most one more than that of the best possible scheme for M/spl les/94; and has response time at most three more than that of the best possible scheme for M/spl les/550. We also show that it outperforms the cyclic declustering scheme-a recently proposed scheme that was shown to have better performance than previously known schemes for this problem. We give some analytical results to suggest that the average performance of our scheme is within 14 percent of the optimal scheme. Our analytical results also suggest a worst case response time within a factor 3 of the optimal for any query, and within a factor 1.5 of the optimal for large queries. We also give a multidimensional extension of our scheme, which has better performance than the multidimensional generalization of the cyclic declustering scheme.

We report on a network traffic warehousing project at Telcordia. The warehouse supports a variety of applications that require access to Internet traffic data. The applications include Service Level Agreement (SLA), web traffic analysis, network capacity engineering and planning, and billing. We describe the design of the warehouse and the issues encountered in building the warehouse.

Declustering schemes enable parallel retrievals of raster-spatial data by allocating data among multiple disks. Previous work in the literature has focused on static range queries. In this paper, we focus on interactive navigation queries, which exhibit a new class of data access patterns. We analyze and compare the performance of previously known declustering schemes from the perspective of navigation queries. These schemes include a class of latin-square-based schemes, Disk Modulo, Fieldwise Exclusive-OR, Hilbert Curve Allocation Method, and a random assignment scheme. We show that, unlike the case of range queries, disk module outperforms other schemes and gives nearly optimal performance for navigation queries. In addition, we propose a new scheme under the constraint of bounded window size-a common constraint in practice due to resource limitation such as monitor resolution or memory size. Through extensive analysis, we establish guidelines on how these schemes can be tuned to provide guaranteed performance under the constraint of bounded window size.

Data Warehousing for INventory management (DWIN) is a production project at Telcordia aimed at providing telecommunications service providers with decision support functions for inventory control and monitoring. In this paper, we report some interesting issues related to the design of the data warehouse. Specifically, we will discuss the issues of slow-evolving fact, transaction-oriented fact table, and large dimensions. We also propose the concept of virtual data cubes and show its usefulness. We address these issues through a data mart case study and present benchmarking results. Finally, based on the experiences learned, we discuss potential research issues that may benefit the data warehousing and OLAP practice.

Various declustering techniques have been proposed in the literature for raster-geospatial data. Their primary focus is on reducing response time for static range queries. We focus on interactive navigation queries, which exhibit a new class of data access patterns. We analyze and compare the performance of three well-known declustering schemes: Disk Modulo, Exclusive-OR, and Hilbert Curve Access Method. The results show that Disk Modulo is close to optimal and, contrary to the case of range queries, is significantly better than Hilbert Curve Access Method. In addition, we propose a new scheme that further improves Disk Module for a realistic situation when the navigation window is bounded by a maximum size-a common constraint due to either monitor resolution or limited memory size. Performance properties of the scheme are also analyzed.

We present the Distributed Batch Controller (DBC), a system built to support batch processing of large scientific datasets. The DBC implements a federation of autonomous workstation pools, which may be widely distributed. Individual batch jobs are executed using idle workstations in these pools. Input data are staged to the pool before processing begins. We describe the architecture and implementation of the DBC, and present the results of experiments in which it is used to perform image compression.

In this paper, we propose a novel approach for estimating the record selectivities of database queries. The real attribute value distribution is adaptively approximated by a curve-fitting function using a query feedback mechanism. This approach has the advantage of requiring no extra database access overhead for gathering statistics and of being able to continuously adapt the value distribution through queries and updates. Experimental results show that the estimation accuracy of this approach is comparable to traditional methods based on statistics gathering.