Soil monitoring plays an essential role in agricultural systems. Rather than deploying sensors' antennas above the ground, burying them in the soil is an attractive way to retain a non-intrusive aboveground space. Low Power Wide-Area Network (LPWAN) has shown its long-distance and low-power features for aboveground Internet-of-Things (IoT) communication, presenting a potential of extending to underground cross-soil communication over a wide area, which however has not been investigated before. The variation of soil conditions brings significant signal polarization misalignment, degrading communication reliability. In this paper, we propose Demeter, a low-cost low-power programmable antenna design to keep reliable cross-soil communication automatically. First, we propose a hardware architecture to enable polarization adjustment on commercial-off-the-shelf (COTS) single-RF-chain LoRa radio. Moreover, we develop a low-power programmable circuit to obtain polarization adjustment. We further design an energy-efficient heuristic calibration algorithm and an adaptive calibration scheduling method to keep signal polarization alignment automatically. We implement Demeter with a customized PCB circuit and COTS devices. Then, we evaluate its performance in various soil types and environmental conditions. The results show that Demeter can achieve up to 11.6 dB SNR gain indoors and 9.94 dB outdoors, 4× horizontal communication distance, at least 20 cm deeper underground deployment, and up to 82% energy consumption reduction per day compared with the standard LoRa.

Sleep quality plays a significant role in personal health. A great deal of effort has been paid to design sleep quality monitoring systems, providing services ranging from bedtime monitoring to sleep activity detection. However, as sleep quality is closely related to the distribution of sleep duration over different sleep stages, neither the bedtime nor the intensity of sleep activities is able to reflect sleep quality precisely. To this end, we present Sleep Hunter, a mobile service that provides a fine-grained detection of sleep stage transition for sleep quality monitoring and intelligent wake-up call. The rationale is that each sleep stage is accompanied by specific yet distinguishable body movements and acoustic signals. Leveraging the built-in sensors on smartphones, Sleep Hunter integrates these physical activities with sleep environment, inherent temporal relation and personal factors by a statistical model for a fine-grained sleep stage detection. Based on the duration of each sleep stage, Sleep Hunter further provides sleep quality report and smart call service for users. Experimental results from over 30 sets of nocturnal sleep data show that our system is superior to existing actigraphy-based sleep quality monitoring systems, and achieves satisfying detection accuracy compared with dedicated polysomnography-based devices.

Time synchronization plays an important role in wireless sensor networks (WSNs). Due to the unique features of WSNs such as remote deployment, low-cost hardware, and restrictive energy supply, accurate and robust time synchronization is still a challenging task. Many approaches have been proposed to improve the performance and efficiency of time synchronization. Existing schemes, however, do not pay enough attention to the impacts of varying network topology properties, including network diameter, degree distribution, and the like. They can experience unexpected performance degradation in many real systems. To address these issues, we present a novel approach, which tries to improve the performance of existing time synchronization algorithms by introducing a virtual overlay. We propose an integrated model, called topo-refiner, which encodes the impact of different network topology features to the precision and robustness of time synchronization. Also, we design a novel optimization algorithm to build a virtual overlay from the underlying communication network. Our approach is orthogonal to existing clock synchronization methods, and can improve their performance by operating these methods atop the virtual layer. Finally, in order to verify the effectiveness of our approach, we conduct extensive simulations on synthetic and real system traces, as well as testbed experiments. Results show that topo-refiner is practical, and quickly adapts to varying time synchronization accuracy requirements for applications in WSNs.

Neighbor discovery is crucial for both wireless sensor networks and mobile computing applications. The crux of the problem is to achieve energy efficiency, which has been demonstrated to be difficult by prior work. In this paper we propose Hello, a generic flexible protocol for neighbor discovery. With an unrestricted parameter, it serves as a generic framework that incorporates existing deterministic protocols. Under the framework, we expose optimal parameters for either symmetric or asymmetric duty cycles, which is the first to our knowledge. As a result, it exhibits great flexibility by adjusting itself to any configuration that best meets application demands. Besides, several techniques are applied to removing redundant discoveries without sacrificing the worst-case latency. We evaluate Hello through extensive simulation and real-world sensor experiments. The results show that Hello is highly energy-efficient under symmetric and asymmetric duty cycles. In particular, it is two times better than the state of the art in terms of the worst-case latency under asymmetric duty cycles.

Wireless LANs, especially WiFi, have been pervasively deployed and have fostered myriad wireless communication services and ubiquitous computing applications. A primary concern in designing each scenario-tailored application is to combat harsh indoor propagation environments, particularly Non-Line-Of-Sight (NLOS) propagation. The ability to distinguish Line-Of-Sight (LOS) path from NLOS paths acts as a key enabler for adaptive communication, cognitive radios, robust localization, etc. Enabling such capability on commodity WiFi infrastructure, however, is prohibitive due to the coarse multipath resolution with mere MAC layer RSSI. In this work, we dive into the PHY layer and strive to eliminate irrelevant noise and NLOS paths with long delays from the multipath channel responses. To further break away from the intrinsic bandwidth limit of WiFi, we extend to the spatial domain and harness natural mobility to magnify the randomness of NLOS paths while retaining the deterministic nature of the LOS component. We prototype LiFi, a statistical LOS identification scheme for commodity WiFi infrastructure and evaluate it in typical indoor environments covering an area of 1500 m2. Experimental results demonstrate an overall LOS identification rate of 90.4% with a false alarm rate of 9.3%.

Crowdsourcing-based mobile applications are becoming more and more prevalent in recent years, as smartphones equipped with various built-in sensors are proliferating rapidly. The large quantity of crowdsourced sensing data stimulates researchers to accomplish some tasks that used to be costly or impossible, yet the quality of the crowdsourced data, which is of great importance, has not received sufficient attention. In reality, the low-quality crowdsourced data are prone to containing outliers that may severely impair the crowdsourcing applications. Thus in this work, we conduct pioneer investigation considering crowdsourced data quality. Specifically, we focus on estimating user motion trajectory information, which plays an essential role in multiple crowdsourcing applications, such as indoor localization, context recognition, indoor navigation, etc. We resort to the family of robust statistics and design a robust trajectory estimation scheme, name TrMCD, which is capable of alleviating the negative influence of abnormal crowdsourced user trajectories, differentiating normal users from abnormal users, and overcoming the challenge brought by spatial unbalance of crowdsourced trajectories. Two real field experiments are conducted and the results show that TrMCD is robust and effective in estimating user motion trajectories and mapping fingerprints to physical locations.

Indoor localization has enabled a great number of mobile and pervasive applications, attracting attentions from researchers worldwide. Most of current solutions rely on Received Signal Strength (RSS) of wireless signals as location fingerprint, to discriminate locations of interest. Fingerprint uniqueness with respect to locations is a basic requirement in these fingerprinting-based solutions. However, due to insufficient number of signal sources, temporal variations of wireless signals, and rich multipath effects, such requirement is not always met in complex indoor environments, which we refer to as fingerprint ambiguity. In this work, we explore the potential of leveraging user motion against fingerprint ambiguity. Our basic idea is that user motion patterns collected by built-in sensors of mobile phones add to the diversity built by RSS fingerprints. On this basis, we propose MoLoc, a motion-assisted localization scheme implemented on mobile phones. MoLoc can easily be integrated in existing localization systems by simply adding a motion database that is constructed automatically by crowdsourcing. We conducted experiments in a large office hall. The experiment results show that MoLoc doubles the localization accuracy achieved by the fingerprinting method, and limits the mean localization error to less than 1m.

Traditional sampling-based estimators infer the actual selectivity of a query based purely on runtime information gathering, excluding the previously collected information, which underutilizes the information available. Table-based and parametric estimators extrapolate the actual selectivity of a query based only on the previously collected information, ignoring online information, which results in inaccurate estimation in a frequently updated environment. We propose a novel hybrid estimator that utilizes and optimally combines the online and previously collected information. A theoretical analysis demonstrates that the online and previously collected information is complementary, and that the comprehensive utilization of the online and previously collected information is of value for further performance improvement. Our theoretical results are validated by a comprehensive experimental study using a practical database, in the presence of insert, delete and update operations. The hybrid approach is very promising in the sense that it provides an adaptive mechanism that allows the optimal combination of information obtained from different sources in order to achieve a higher estimation accuracy and reliability.

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. Lamport's (1978) algorithm and Ricart and Agrawal's (1981) algorithm both have a synchronization delay of T, but their message complexity is O(N). Maekawa's (1985) algorithm reduces message complexity to O(/spl radic/N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm, many quorum-based mutual exclusion algorithms have been proposed to reduce message complexity or increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from long synchronization delay 2T. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has the low message complexity O(K) (K is the size of the quorum, which can be as low as log N). A correctness proof and detailed performance analysis are provided.

We present a new algorithm for detecting generalized deadlocks in distributed systems. Our algorithm incrementally constructs and reduces a wait-for graph (WFG) at an initiator process. This WFG is then searched for deadlock. The proposed algorithm has two primary advantages: First, it avoids sending messages along the edges of the global wait-for graph (WFG), thereby achieving a worst-case message complexity of 2n, where n is the number of processes in the WFG. Since information must be obtained from every process reachable from the initiator, this is optimal to within a constant factor. All the existing algorithms for the same problem construct a distributed snapshot of the WFG. As this involves sending messages along the edges of the WFG, the best available message complexity among these algorithms is 4e-2n+2l, which is O(n/sup 2/) in the worst case, where e and l are the number of edges and leaves in the WFG, respectively. Second, since the information about a detected deadlock is readily available at the initiator process, rather than distributed among different processes, it significantly simplifies the task of deadlock resolution, and helps to reduce system overhead associated with the resolution. The time complexity of our algorithm is also better than or equal to the existing algorithms.

Satisfiability, equivalence, and implication problems involving conjunctive queries are important and widely encountered problems in database management systems. These problems need to be efficiently and effectively solved. In this paper, we consider queries which are conjunctions of the inequalities of the form (X op C), (X op Y), and/or (X op Y+C), where X and Y are two attributes, C is a constant, and op /spl epsiv/ {, /spl ges/}. These types of inequalities are widely used in database systems, since the first type is a selection, the second type is a /spl theta/-join, and the third type is a very popular clause in a deductive database system. The satisfiability, equivalence, and implication problems in the integer domain (for attributes and constants) have been shown to be NP-hard. However, we show that these problems can be solved efficiently in the real domain. The incorporation of the real domain is significant, because the real domain is practically and widely used in a database. Necessary and sufficient conditions and algorithms are presented. A novel concept of the "module closure" and a set of sound and complete axioms with respect to the "module closure" are also proposed to infer all correct and necessary inequalities from a given query. The proposed axioms generalize Ullman's axioms (1989) where queries only consist of /spl theta/-joins.

Satisfiability, implication, and equivalence problems involving conjunctive inequalities are important and widely encountered database problems that need to be efficiently and effectively processed. In this article we consider two popular types of arithmetic inequalities, ( X op Y ) and ( X op C ), where X and Y are attributes, C is a constant of the domain or X , and op ∈{<, ≤, =, ≠, >, ≥). These inequalities are most frequently used in a database system, inasmuch as the former type of inequality represents a 0-join, and the latter is a selection. We study the satisfiability and implication problems under the integer domain and the real domain, as well as under two different operator sets ({<, ≤, =, ≥, >} and {<, ≤, =, ≠, ≥, >}). Our results show that solutions under different domains and/or different operator sets are quite different. Out of these eight cases, excluding two cases that had been shown to be NP-hard, we either report the first necessary and sufficient conditions for these problems as well as their efficient algorithms with complexity analysis (for four cases), or provide an improved algorithm (for two cases). These iff conditions and algorithms are essential to database designers, practitioners, and researchers. These algorithms have been implemented and an experimental study comparing the proposed algorithms and those previously known is conducted. Our experiments show that the proposed algorithms are more efficient than previously known algorithms even for small input. The C++ code can be obtained by an anonymous ftp from .

The results of a performance study of the representative sampling-based size estimation methods in database management systems are reported in this paper. Major performance measurement includes estimation accuracy, the amount of sample taken, and the coverage. The impact of skewed data on the performance is also discussed. These results allow a better understanding and assessment of sampling estimation methods and determine the suitability of different methods under different situations.>

Implication testing of arithmetic inequalities has been widely used in different areas in database systems and has received extensive research as well. Klug and Ullman (A. Klug, 1988; and J.D. Ullman, 1989) proposed an algorithm that determines whether S implies T, where T and S consist of inequalities of form (X op Y), X and Y are two variables, and op/spl epsiv/ {=, /spl ges/}. The complexity of the algorithm is O(n/sup 3/), where n is the number of inequalities in S. We reduce the problem to matrix multiplication, thus improving the time bound to O(n/sup 2.376/). We also demonstrate an O(n/sup 2/) algorithm if the number of inequalities in T is bounded by O(n). Since matrix multiplication has been well studied, our reduction allows the possibility of directly adopting many practical results for managing matrices and their operations, such as parallel computation and efficient representation of sparse matrices.>

Semantic query optimization, or knowledge-based query optimization, has received increasing interest in recent years. The authors provide an effective and systematic approach to optimizing queries by appropriately choosing semantically equivalent transformations. Basically, there are two different types of transformations: transformations by eliminating unnecessary joins, and transformations by adding/eliminating redundant beneficial/nonbeneficial selection operations (restrictions). A necessary and sufficient condition to eliminate a single unnecessary join is provided. We prove that it is /spl Nscr//spl Pscr/-/spl Cscr/omplete to eliminate as many unnecessary joins as possible for various types of acyclic queries with the exception of the closure chain queries whose query graphs are chains and all equi-join attributes are distinct. An algorithm is provided to minimize the number of joins in tree queries. This algorithm has an important property that, when applied to a closure chain query, it will yield an optimal solution with the time complexity O(n*m), where n is the number of relations referenced in the chain query, and m is the time complexity of a restriction closure computation.>

This paper proposes a novel strategy for estimating the size of the resulting relation after an equi-join and selection using a regression model. An approximating series representing the underlying data distribution and dependency is derived from the actual data. The proposed method provides an instant and accurate size estimation by performing an evaluation of the series, with no run-time overheads in page faults and space, and with negligible CPU overhead. In contrast, the popular sampling methods incur run-time overheads in page faults (for sampling), CPU time and space. These overheads of sampling methods increase the response time of processing a query. The results of a comprehensive experimental study are also reported, which demonstrate that the estimation accuracy by the proposed method is comparable with that of the sampling methods which are believed to provide the most accurate estimation. The proposed method seems ideal for retrieval-intensive database and information systems. Since the overheads involved in deriving the approximating series are fairly moderate, we believe that this method is also an extremely competent method when moderate or periodical updates are present.

The IS-A relationship (the class-subclass relationship) is one of the most fundamental and important properties in an object-oriented (OO) language and OO database management system (OODBMS). Due to the popularity and domination of relational database management systems (RDBMSs) and the fundamental importance of inheritance, supporting IS-A relationships in a RDBMS becomes very desired, and is essential to adapt a RDBMS to more advanced applications. The authors present an extended SQL system called ESQL which facilitates IS-A relation hierarchies in a RDBMS. The proposed ESQL uses constraints to resolve data redundancy and updating abnormality problems that exist in current OO languages such as C++ and Smalltalk, and OODBMS such as GemStone, PostGres, O/sub 2/, Iris, and Orion. Features such as inheritance constraints, subrelation assertions, mappings, and automatic tuple placement into its most specific subrelation are distinct in ESQL. These features are missing in current RDBMSs, OODBMSs and OO languages.>

Basing on the algebraic representation of Petri net models of Ada tasking programs, the authors have defined a set of linear programming problems to support the static analysis of various queries about tasking behavior, such as queries about deadlock existence, possible parallelism, possible occurrence of an event, reachable states, definite occurrence of events, and quantitative questions. The linear programming problems are defined in such a way that their solutions can be used to guide net simulation to confirm the analysis conclusion. The stress of this method is that the enumeration of the entire state space of a Petri net is avoided. The defined problems are valid as long as the underlying net model is a safe net.>

In this paper, query processing and optimisation in distributed object-oriented database systems are discussed. The processing and optimisation of typical queries, called chain queries, in distributed object-oriented database systems are investigated in detail. An algorithm with complexity of O(n3 * hI) to minimise the total cost is provided using dynamic programming, where n is the number of classes referenced in the query, hI ≤ min (n + 2, h) and h is the number of sites in the network. A wide range of diversified issues are addressed and uniformly integrated into our basic solution to the problem. These issues include sorted states of classes; local processing of selections and projections, allowing multiple intermediate results; arbitrary target class at an arbitrary answer site; replicated data; class hierarchies (which captures the IS-A relationship among objects); different sites with different processing speeds, and communication lines between different sites with different transfer speeds. The uniformity of this algorithm under so many diversified situations strongly demonstrates the usefulness and the flexibility of the algorithm.

Optical Character Recognition (OCR) has become a highly demanded information transfer technology in recent years. A problem of current OCR technology is that texts produced by the state-of-the-art OCR software contain an unacceptable frequency of errors. This prevents the OCR technology from being efficiently used for vast-volume information transfer or daily office operation applications. To correct these errors in a conventional way requires a significant amount of costly human-machine interaction. In this article, we identify and classify the types and distributions of optical recognition errors. We proposed a novel post-processing strategy, based on machine learing techniques, to correct errors resulted from unrecognized process

The authors present an approach to acquiring knowledge from previously processed queries. By using newly acquired knowledge together with given semantic knowledge, it is possible to make the query processor and/or optimizer more intelligent so that future queries can b processed more efficiently. The acquired knowledge is in the form of constraints. While some constraints are to be enforced for all database states, others are known to be valid for the current state of the database. The former constraints are statistic integrity constraints, while the latter are called dynamic integrity constraints. Some situations in which certain dynamic semantic constraints can be automatically extracted are identified. This automatic tool for knowledge acquisition can also be used as an interactive tool for identifying potential static integrity constraints. The concept of minimal knowledge base is introduced, and a method to maintain the knowledge base is presented. An algorithm to compute the restriction (selection) closure, i.e. all deductible restrictions, from a given set of restrictions, join predicates (as given in a query), and constraints is given.>