Using FPGA as accelerators is gaining popularity in Cloud computing. Usually, FPGA accelerators in a datacenter are managed as a single resource pool. By issuing a request to this pool, a tenant can transparently access FPGA resources. FPGA requests usually arrive in batches. The objective of scheduling is to minimize the make-span of a given batch of requests, which is the completion time of the entire batch of jobs. As a result, either the responsiveness is improved, or the system throughput is maximized. The key technical challenge is the existence of multiple resource bottlenecks. An FPGA job can be bottlenecked by either computation (i.e., computation-intensive) or network (i.e., network-intensive), and sometimes by both. To the best of our knowledge, this is the first work that minimizes the make-span of batched requests for an FPGA accelerator pool in Cloud computing that considers multiple resource bottlenecks. In this paper, we design several scheduling algorithms to address the challenge. We implement our scheduling algorithms in an IBM Cloud system. We conduct extensive evaluations on both a small scale testbed and a large-scale simulator. Compared with the Shortest-Job-First scheduling, our algorithms can reduce the make-span by 36.25 percent, and improve the system throughput by 36.05 percent.

Many distributed applications, such as BitTorrent, need to know the distance between each pair of network hosts in order to optimize their performance. For small-scale systems, explicit measurements can be carried out to collect the distance information. For large-scale applications, this approach does not work due to the tremendous amount of measurements that have to be completed. To tackle the scalability problem, network coordinate system (NCS) was proposed to solve the scalability problem by using partial measurements to predict the unknown distances. However, the existing NCS schemes suffer seriously from either low prediction precision or unsatisfactory convergence speed. In this paper, we present a novel distributed network coordinate system (DISCS) that utilizes a limited set of distance measurements to achieve high-precision distance prediction at a fast convergence speed. Technically, DISCS employs the innovative robust nonnegative matrix completion method to improve the prediction accuracy. Through extensive experiments based on various publicly-available data sets, we found that DISCS outperforms the state-of-the-art NCS schemes in terms of prediction precision and convergence speed, which clearly shows the high usability of DISCS in real-life Internet applications.

Mobile indoor localization is the foundation for the location-based features of many pervasive computing applications. Due to the popularity of WiFi networks in indoor environments, WiFi-based indoor localization has been considered to be a promising approach. Despite the feasibility of WiFi-based localization, the existing WiFi-based schemes suffer from the serious problem of low precision. In this paper, we propose a high-precision indoor localization scheme for mobile networks, Mobile Indoor Localization (MIL). Technically, MIL adopts a matrix completion approach which efficiently utilizes the collected information to achieve high localization precision at low computation cost. Our experimental results indicate that MIL outperforms the state-of-the-art mobile indoor localization schemes in terms of localization precision.

Over the past decades, many large-scale social network systems, such as Facebook and Twitter, have been deployed in different countries. How to efficiently analyze the topological characteristics of large-scale social networks has been a challenging problem in the research community. One of the critical topological characteristics is the shortest distance between two nodes in a network. The existing shortest distance algorithms, such as Breadth First Search (BFS), work well with small networks. For a network with billions of nodes, calculating the pairwise shortest distances with these algorithms requires an overlong period of time. In this paper, we present a high-precision ShOrtest Distance Approximation (SODA) scheme, which utilizes a small set of pre-calculated distances to estimate the shortest distance between each pair of nodes in large-scale social networks. Compared with the existing shortest distance estimation schemes for social networks, SODA leads to high estimation accuracy since it utilizes a novel optimization method, Robust Discrete Matrix Decomposition (RDMD), to eliminate the impact of significant errors/outliers and generate the coordinates of the nodes in a network simultaneously. In addition, SODA differentiates the asymmetric distances in directed graphs. Consequently, SODA works well with both directed and undirected social networks. Finally, SODA only involves convex optimization. Therefore, SODA is highly competitive in terms of computation complexity. Our experimental results indicate that SODA outperforms the state-of-the-art shortest distance estimation schemes in terms of estimation accuracy and running time.

Localization is one of the key operations in mobile networks. Due to the limitations of GPS, many researchers have devised a variety of different range-free and range-based localization schemes. Range-free schemes utilize the connectivity information to localize mobile nodes. However, the use of the connectivity information allows a high degree of freedom in terms of pinpointing the location of mobile nodes, which leads to low localization precision. Range-based schemes can achieve high localization precision because they require the fine-granularity distance information. Nevertheless, they normally result in high computation complexity and do not work well when part of the distance measurements are missing. In this paper, we propose a distributed range-based localization scheme, DISCO, that uses a series of minimization problems that only involve convex optimization to arrive at high localization precision and low computation complexity. In addition, when some distance measurements are not available, DISCO utilizes the partial distance information to achieve satisfactory localization results. Furthermore, DISCO is a distributed algorithm, which means that it scales well. The performance of DISCO is analyzed through simulation experiments. An in-depth analysis of the time complexity of DISCO is also included in this paper.

The Global Positioning System (GPS) has been widely used to determine the location for a variety of different applications. However, it doesn't work well in indoor environments because it requires the line of sight to the satellites and therefore stops working when the line of sight is not available. High-precision indoor localization is critical to many personal and business applications. After Bluetooth Low Energy (BLE), an energy-efficient version of Bluetooth, is widely deployed, Bluetooth-based indoor localization turns out to be a practical method to locate Bluetooth-enabled devices due to its low battery cost. In this paper, we present two novel BLE-based localization schemes, Low-precision Indoor Localization (LIL) and High-precision Indoor Localization (HIL). Different than most of the existing localization methods that attempt to find the specific location of the object under investigation, LIL and HIL utilize the collected RSSI measurements to generate a small region in which the object is guaranteed to be found. Compared with LIL, HIL leads to smaller localization regions. However, HIL requires an extra data-training phase.

Network Coordinate System (NCS) has drawn much attention over the past years thanks to the increasing number of large-scale distributed systems that require the distance prediction service for each pair of network hosts. The existing schemes suffer seriously from either low prediction precision or unsatisfactory convergence speed. In this paper, we present a novel distributed network coordinate system based on Robust Principal Component Analysis, RNC, that uses a few local distance measurements to calculate high-precision coordinates without convergence process. To guarantee the non-negativity of predicted distances, we propose Robust Nonnegative Principal Component Analysis (RUN-PACE) which only involves convex optimization, consequently resulting in low computation complexity. Our experimental results indicate that RNC outperforms the state-of-the-art NCS schemes.

Localization in mobile networks is of paramount importance to a variety of pervasive applications. Due to the limitations of GPS, such as high deployment cost, many researchers have devised a variety of different localization schemes based on the measurements of connectivity or distance between neighboring nodes. The existing schemes suffer seriously from either low localization precision or overlong computation time. In this paper, we present a novel localization scheme based on matrix completion, MALL, that utilizes the collected connectivity and distance information to achieve high-precision localization. Since MALL only involves convex optimization and low-complexity non-convex optimization, it can localize mobile nodes at a fast pace. Furthermore, MALL leads to low communication cost. Through intensive simulation and testbed experiments, we found that MALL outperforms the state-of-the-art localization schemes. An in-depth analysis of the time complexity and communication cost of MALL is also included in this paper.

Localization is a fundamental operation in wireless networks. Location determination is normally accomplished using the Global Positioning System (GPS) for outdoor applications. For indoor localization, GPS does not work due to the lack of the line of sight to satellites. High-precision indoor localization is critical to many personal and business applications. WiFi-based indoor localization was proposed to be a practical method to locate WiFi-enabled devices due to the popularity of WiFi networks. However, it suffers from large localization errors. Our experimental results indicate that this scheme consistently leads to an average error around 3 meters. The existence of different locations with similar WiFi signal strength is the reason behind the large errors. To improve the localization precision, a hybrid indoor localization scheme, HILL, is proposed in this paper. Inspired by the fact that a large number of WiFi-enabled mobile devices have been deployed, HILL uses 3 phases to improve the precision of WiFi-based localization. First of all, it measures the distances between each pair of peer devices through acoustic ranging. Secondly, the Classical Metric Multidimensional Scaling (MDS) method is applied to the collected distances, which results in a graph consistent with the distances. Finally, the graph generated by MDS is embedded onto the graph corresponding to WiFi-based localization in order to achieve high localization precision. Our experimental results indicate that the average localization error of HILL is about 1 meter.

Data gathering in sensor networks is required to be efficient, adaptable and robust. Recently, compressive sensing (CS) based data gathering shows promise in meeting these requirements. Existing CS-based data gathering solutions require that a transform that best sparsifies the sensor readings should be used in order to reduce the amount of data traffic in the network as much as possible. As a result, it is very likely that different transforms have to be determined for varied sensor networks, which seriously affects the adaptability of CS-based schemes. In addition, the existing schemes result in significant errors when the sampling rate of sensor data is low (equivalent to the case of high packet loss rate) because CS inherently requires that the number of measurements should exceed a certain threshold. This paper presents STCDG, an efficient data gathering scheme based on matrix completion. STCDG takes advantage of the low-rank feature instead of sparsity, thereby avoiding the problem of having to be customized for specific sensor networks. Besides, we exploit the presence of the short-term stability feature in sensor data, which further narrows down the set of feasible readings and reduces the recovery errors significantly. Furthermore, STCDG avoids the optimization problem involving empty columns by first removing the empty columns and only recovering the non-empty columns, then filling the empty columns using an optimization technique based on temporal stability. Our experimental results indicate that STCDG outperforms the state-of-the-art data gathering algorithms in terms of recovery error, power consumption, lifespan, and network capacity.

Wireless sensor networks are expected to be used in many different applications such as disaster relief, environmental control, and intelligent buildings. In this paper, we focus on a sensor network that collects environment data from all sensor nodes periodically. To gather the sensing data quickly and reliably, the scheduling algorithm should be able to coordinate the data transmissions in the network and react to node/link failures effectively. In this paper, we present an innovative scheduling algorithm, Fault-Tolerant Scheduling for data collection (FTS), that leads to short data collection time and high fault tolerance. Our experimental results show that FTS outperforms the DCSB algorithm and exhibits strong fault-tolerant capabilities.

MAP is a connectivity-based routing protocol aimed at improving the load balance performance of traditional geographical routing methods. It attempts to find parallel routing paths by taking advantage of the concept of skeleton in the continuous domain. However, MAP suffers seriously from overloading the sensor nodes that are close to the skeleton. In this paper, we propose a contour-based routing protocol, CAR, that does not require geographical information, produces short routing paths, and achieves outstanding load balancing. Our experimental results show that CAR outperforms MAP in terms of both load balancing and routing path length.

Top-k query has long been a crucial problem in multiple fields of computer science, such as data processing and information retrieval. In emerging cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, users may request different sets of information, with different priorities and at different times. Thus, top-k search should not only be multidimensional, but also be across time domain. From the system's perspective, data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy demands from the two aspects. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for user query processing and two schemes are proposed to further reduce communication cost. Our methods can be used for top-k query with any linear convex query function. The framework is adaptive enough to incorporate some advanced features; for example, we show how approximate queries and data aging can be applied. To the best of our knowledge, this is the first work for continuous multidimensional top-k query processing in sensor networks. Simulation results show that our schemes can reduce the total communication cost by up to 90 percent, compared with a centralized scheme or a straightforward extension from previous top-k algorithm on 1D sensor data.

Top-k query has long been an important topic in many fields of computer science. Efficient implementation of the top-k queries is the key for information searching. With the new frontier such as the cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, different users may request different set of information, with different priorities and at different times. Thus, the top-k search not only should be multi-dimensional, but also across time domain. From the system's perspective, the data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource-constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy the two ends. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for the user query processing and two schemes are proposed to further reduce communication cost. Our proposed methods can be used for top-k query with any linear convex query function. To the best of our knowledge, this is the first work for continuous multi-dimensional top-k query processing in sensor networks; and our simulation results show that our schemes can reduce the total communication cost by up to 90%, compared with the centralized scheme or a straightforward extension from previous top-k algorithm on one-dimensional sensor data.

Data collection is of paramount importance in many applications of wireless sensor networks (WSNs). Especially, to accommodate ever increasing demands of signal source coding applications, the capacity of processing multi-user data query is crucial in WSNs where the efficiency is one key consideration. To that end, this paper presents EDCA: an Efficient Data Collection Approach for data query in WSNs, which exploits recent matrix completion techniques. Specifically, for the efficiency of energy consumption, we randomly select a part of nodes from the sensor network to sample at each time instance and directly forward the data to the sink. Then, to recover the data precisely, we shift the rank minimization problem, which is NP-hard, to a convex optimization one. Compared with the centralized scheme, energy consumption using EDCA is significantly reduced due to lower sampling rate and fewer packets to transmit. The experimental results demonstrate that EDCA significantly outperforms the existing naive method in terms of energy consumption and the introduced errors are quite trivial.

Routing is one of the most challenging open problems in pocket-switched-networks (PSN). In this paper, we propose a novel co-route media content forwarding scheme (CRMF), in which new contact opportunities are created for occasionally disconnected mobile users. Our study is inspired by two observations: one is that many people tend to make regular journeys to the same place, so their trajectories show a high degree of temporal and spatial regularity. The other is that the number of repeated journeys for an individual commuter is greater than that of the repeated contacts with another commuter who possess similar seasonal movement patterns. Our main contributions include: we properly install store-and-forward routers based on vehicle mobility patterns and human regular movement behaviors; we also propose a router-centric prediction scheme that collects passenger historical trajectory information to determine the delivery scheme. The simulation results demonstrate that this approach improves delivery ratio and also reduces the delivery latency compared to memory (history)-less delivery scheme.