1912292
Opportunistic Energy-Efficient Contact Probing in Delay-Tolerant Applications
In many delay-tolerant applications, information is opportunistically exchanged between mobile devices that encounter each other. In order to affect such information exchange, mobile devices must have knowledge of other devices in their vicinity. We consider scenarios in which there is no infrastructure and devices must probe their environment to discover other devices. This can be an extremely energy-consuming process and highlights the need for energy-conscious contact-probing mechanisms. If devices probe very infrequently, they might miss many of their contacts. On the other hand, frequent contact probing might be energy inefficient. In this paper, we investigate the tradeoff between the probability of missing a contact and the contact-probing frequency. First, via theoretical analysis, we characterize the tradeoff between the probability of a missed contact and the contact-probing interval for stationary processes. Next, for time-varying contact arrival rates, we provide an optimization framework to compute the optimal contact-probing interval as a function of the arrival rate. We characterize real-world contact patterns via Bluetooth phone contact-logging experiments and show that the contact arrival process is self-similar. We design STAR, a contact-probing algorithm that adapts to the contact arrival process. Instead of using constant probing intervals, STAR dynamically chooses the probing interval using both the short-term contact history and the long-term history based on time of day information. Via trace-driven simulations on our experimental data, we demonstrate that STAR requires three to five times less energy for device discovery than a constant contact-probing interval scheme.
8718926
Using mobile relays to prolong the lifetime of wireless sensor networks
In this paper we investigate the benefits of a heterogeneous architecture for wireless sensor networks composed of a few resource rich mobile nodes and a large number of simple static nodes. These mobile nodes can either act as mobile relays or mobile sinks. To investigate the performance of these two options and the trade-offs associated with these two options, we first consider a finite network. We then compute the lifetime for different routing algorithms for three cases (i) when the network is all static (ii) when there is one mobile sink and (iii) when there is one mobile relay. We find that using the mobile node as a sink results in the maximum improvement in lifetime. We contend however that in hostile terrains, it might not always be possible for the sink to be mobile. We then investigate the performance of a large dense network with one mobile relay and show that the improvement in network lifetime over an all static network is upper bounded by a factor of four. Also, the proof implies that the mobile relay needs to stay only within a two hop radius of the sink. We then construct a joint mobility and routing algorithm which comes close to the upper bound. However this algorithm requires all the nodes in the network to be aware of the location of the mobile node. We then proposed an alternative algorithm, which achieves the same performance, but requires only a limited number of nodes in the network to be aware of the location of the mobile. We finally compare the performance of the mobile relay and mobile sink and show that for a densely deployed sensor field of radius R hops, we require O(R) mobile relays to achieve the same performance as the mobile sink.
1107425
Information Coverage in Randomly Deployed Wireless Sensor Networks
Coverage is an important issue in wireless sensor networks. The most commonly used coverage model in the literature defines a point to be covered if its Euclidian distance to at least one sensor is less than a fixed threshold. This is a conservative definition of coverage which implicitly assumes that each sensor makes a decision independent of other sensors in the field. Sensors can cooperate to make an accurate estimation, even if any single sensor is unable to do so. We have previously proposed a new notion of information coverage and investigated its properties. In this paper, we study sensor density requirements for complete information coverage of a field with random sensor deployment. We provide an upper bound on the probability that an arbitrary point in a randomly deployed sensor field is not information covered and find the relationship between the sensor density and the average field vacancy. Simulation results validate our theoretical analysis and show that significant savings in terms of sensor density for complete coverage can be achieved with information coverage.
38794991
Localized Recursive Estimation in Wireless Sensor Networks
This paper proposes a localized recursive estimation scheme for parameter estimation in wireless sensor networks. Given any parameter occurred at some location and time, a number of sensors recursively estimates the parameter by using their local measurements of the parameter that is attenuated with the distance between a sensor and the target location and corrupted by noises. Compared with centralized estimation schemes that transmit all measurements to a sink (or a fusion center), the recursive scheme needs only to transmit the final estimate to a sink. When a sink is faraway from the sensors and multihop communications have to be used, using localized recursive estimation can help to reduce energy consumption and reduce network traffic load. Furthermore, the most efficient sequence of sensors for estimation is defined and the necessary condition for such a sequence is determined. Some numerical examples are also provided. By using some typical industrial sensor parameter values, it is shown that recursive scheme consumes much less energy when the sink is three hops or more faraway from the local sensors.
5843857
Extending the Lifetime of Wireless Sensor Networks Through Mobile Relays
We investigate the benefits of a heterogeneous architecture for wireless sensor networks (WSNs) composed of a few resource rich mobile relay nodes and a large number of simple static nodes. The mobile relays have more energy than the static sensors. They can dynamically move around the network and help relieve sensors that are heavily burdened by high network traffic, thus extending the latter's lifetime. We first study the performance of a large dense network with one mobile relay and show that network lifetime improves over that of a purely static network by up to a factor of four. Also, the mobile relay needs to stay only within a two-hop radius of the sink. We then construct a joint mobility and routing algorithm which can yield a network lifetime close to the upper bound. The advantage of this algorithm is that it only requires a limited number of nodes in the network to be aware of the location of the mobile relay. Our simulation results show that one mobile relay can at least double the network lifetime in a randomly deployed WSN. By comparing the mobile relay approach with various static energy-provisioning methods, we demonstrate the importance of node mobility for resource provisioning in a WSN.
42723008
Worst and Best Information Exposure Paths in Wireless Sensor Networks
This paper proposes the concept of information exposure for a point and for a path based on estimation theory. The information exposure of a point is defined as the probability that the absolute value of estimation error is less than some threshold; and the information exposure for a path is the average information exposure of all points along the path. The higher the information exposure, the higher the confidence level that some information of a target is exposed and the better the target is monitored. An approximation algorithm is proposed to solve the problem of finding the worst (best) information exposure path in wireless sensor networks, and its performance is evaluated via simulations. Furthermore, a heuristic for adaptive sensor deployment is proposed to increase the information exposure of the worst information exposure path.
2039223
Processing Sliding Window Join Aggregate in Continuous Queries over Data Streams
Processing continuous queries over unbounded streams require unbounded memory. A common solution to this issue is to restrict the range of continuous queries into a sliding window that contains the most recent data of data streams. Sliding window join aggregates are often-used queries in data stream applications. The processing method to date is to construct steaming binary operator tree and pipeline execute. This method consumes a great deal of memory in storing the sliding window join results, therefore it isn’t suitable for stream query processing. To handle this issue, we present a set of novel sliding window join aggregate operators and corresponding realized algorithms, which achieve memory-saving and efficient performance. Because the performances of proposed algorithms vary with the states of data streams, a scheduling strategy is also investigated to maximize the processing efficiency. The algorithms in this paper not only can process the complex sliding window join aggregate, but also can process the multi-way sliding window join aggregate.
9921122
Probabilistic Skyline Operator over Sliding Windows
Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of efficient processing of continuous skyline queries over sliding windows on uncertain data elements regarding given probability thresholds. We first characterize what kind of elements we need to keep in our query computation. Then we show the size of dynamically maintained candidate set and the size of skyline. We develop novel, efficient techniques to process a continuous, probabilistic skyline query. Finally, we extend our techniques to the applications where multiple probability thresholds are given or we want to retrieve "top-k" skyline data objects. Our extensive experiments demonstrate that the proposed techniques are very efficient and handle a high-speed data stream in real time.
1744203
SPARK: A Keyword Search Engine on Relational Databases
Relational database is the most widely adopted and mature technology for information storage. As many services on the Web (e.g., blog and wiki sites) and advanced applications (e.g., customer relationship management systems and content management systems) are built on RDBMSs, increasing amount of text data is now stored in relational databases, accompanied by increasing demands of retrieving relevant information by free-style keyword search.
2629783
Optimal Rate-Based Image Transmissions via Multiple Paths in Wireless Sensor Network
Many sensor applications such as monitoring and surveillance may require image sensor array to conduct collaborative image transmissions in wireless sensor network (WSN). The large size image transmission in WSN is a bottleneck due to the limited energy resources. In this paper, we propose an optimal scheme for image sensors to utilize inter-sensor correlations to decide transmission patterns based on a multi-level rate-oriented routing (MLRR) routing scheme, which achieves high energy efficiencies and longer network lifetime. This optimization scheme allows each image sensor to transmit optimal fractions of the overlapped images through appropriate multiple rate-oriented routing paths. The simulation results by using GA algorithm show that the proposed image transmission scheme can achieve considerable gains in terms of the WSN energy efficiency and network lifetime extension.
8027893
NOVA: A Novel and Efficient Framework for Finding Subgraph Isomorphism Mappings in Large Graphs
Considerable efforts have been spent in studying subgraph problem. Traditional subgraph containment query is to retrieve all database graphs which contain the query graph g. A variation to that is to find all occurrences of a particular pattern(the query) in a large database graph. We call it subgraph matching problem. The state of art solution to this problem is GADDI. In this paper, we will propose a more efficient index and algorithm to answer subgraph matching problem. The index is based on the label distribution of neighbourhood vertices and it is structured as a multi-dimensional vector signature. A novel algorithm is also proposed to further speed up the isomorphic enumeration process. This algorithm attempts to maximize the computational sharing. It also attempts to predict some enumeration state is impossible to lead to a final answer by eagerly pruning strategy. We have performed extensive experiments to demonstrate the efficiency and the effectiveness of our technique.