Events & News
CS Colloquium
| Category | Lecture |
| Date | Thursday, August 28, 2014 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Details | Please join us for coffee and light refreshments at 10:45am in the 9th floor atrium. Faculty Host: Alon Efrat |
| Speaker | Guy Grebla |
| Affiliation | Colombia University |
Scheduling Algorithms & Kinetic Energy Harvesting for the Internet of Things
Numerous energy harvesting wireless devices that will serve as building blocks for the Internet of Things (IoT) are currently under development. However, there is still only limited understanding of the properties of various energy sources and their impact on energy harvesting adaptive algorithms. Hence, we focus on characterizing the kinetic (motion) energy that can be harvested by a wireless node with an IoT form factor and on developing energy allocation algorithms for such nodes. We describe methods for estimating harvested energy from acceleration traces. To characterize the energy availability associated with specific human activities (e.g., relaxing, walking, cycling), we analyze a motion dataset with over 40 participants. Based on acceleration measurements that we collected for over 200 hours, we study energy generation processes associated with day-long human routines. We also briefly summarize our experiments with moving objects. We develop energy allocation algorithms that take into account practical IoT node design considerations, and evaluate the algorithms using the collected measurements. Our observations provide insights into the design of motion energy harvesters, IoT nodes, and energy harvesting adaptive algorithms.
As the number of connected devices increases, there is a growing need to provide constant and reliable connectivity to every device in every location. However, Deploying long-range wireless networks with good coverage is a complex task, one that introduces a trade-off between cost and performance. One example of this trade-off is the desire to decrease the size of the cells in order to increase the network bandwidth available to every user. But decreasing cell size by adding more Base Stations (BSs) increases installation costs substantially, because the most expensive factor in the installation of a new BS is connecting it to the optical backbone. To overcome this barrier, 4G cellular standards allow Relay Nodes (RNs) to be deployed as a substitute for BSs. Unlike a BS, an RN is not directly connected to the backbone. Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link. In the second part of my talk, I will discuss scheduling algorithms for a network with RNs. Because the scheduler in a network with RNs must take into account the transmission resources of the BS and the RNs, it needs to find a feasible schedule that does not exceed the resources of a multi-dimensional resource pool. This makes the scheduling problem computationally harder than in a network without RNs. In this paper we define and study the packet-level scheduling problem for a network with RNs. This problem is not only NP-hard, but also admits no efficient polynomial-time approximation scheme. To solve it, we propose an efficient algorithm with a performance guarantee, and a simple water-filling heuristic. To the best of our knowledge, our algorithm is the first packet-level scheduling algorithm that provides a performance guarantee for a network with RNs. Using simulations, we evaluate our new algorithms and show that they perform very well.