More Like this

1. On the Accuracy of Network Synchronization Using Persistent Hourglass Clocks

   https://doi.org/10.1145/3362053.3363497  

   Çürük, Eren; Yıldırım, Kasim Sinan; Pawelczak, Przemyslaw; Hester, Josiah (January 2019, Proceedings of the 7th International Workshop on Energy Harvesting & Energy-Neutral Sensing Systems)

   Batteryless sensor nodes compute, sense, and communicate using only energy harvested from the ambient. These devices promise long maintenance free operation in hard to deploy scenarios, making them an attractive alternative to battery-powered wireless sensor networks. However, complications from frequent power failures due to unpredictable ambient energy stand in the way of robust network operation. Unlike continuously-powered systems, intermittently-powered batteryless nodes lose their time upon each reboot, along with all volatile memory, making synchronization and coordination difficult. In this paper, we consider the case where each batteryless sensor is equipped with a hourglass capacitor to estimate the elapsed time between power failures. Contrary to prior work that focused on providing a continuous notion of time for a single batteryless sensor, we consider a network of batteryless sensors and explore how to provide a network-wide, continuous, and synchronous notion of time. First, we build a mathematical model that represents the estimated time between power failures by using hourglass capacitors. This allowed us to simulate the local (and continuous) time of a single batteryless node. Second, we show--through simulations--the effect of hourglass capacitors and in turn the performance degradation of the state of the art synchronization protocol in wireless sensor networks in a network of batteryless devices. 

   more » « less
2. DRE ² : Achieving Data Resilience in Wireless Sensor Networks: A Quadratic Programming Approach

   https://doi.org/10.1109/MASS50613.2020.00019  

   Hsu, Shanglin; Yu, Yuning; Tang, Bin (December 2020, 2020 IEEE 17th International Conference on Mobile Ad Hoc and Sensor Systems (MASS))

   null (Ed.)

   We focus on sensor networks that are deployed in challenging environments, wherein sensors do not always have connected paths to a base station, and propose a new data resilience problem. We refer to it as DRE2: data resiliency in extreme environments. As there are no connected paths between sensors and the base station, the goal of DRE2 is to maximize data resilience by preserving the overflow data inside the network for maximum amount of time, considering that sensor nodes have limited storage capacity and unreplenishable battery power. We propose a quadratic programming-based algorithm to solve DRE2 optimally. As quadratic programming is NP-hard thus not scalable, we design two time efficient heuristics based on different network metrics. We show via extensive experiments that all algorithms can achieve high data resilience, while a minimum cost flow-based is most energy-efficient. Our algorithms tolerate node failures and network partitions caused by energy depletion of sensor nodes. Underlying our algorithms are flow networks that generalize the edge capacity constraint well-accepted in traditional network flow theory. 

   more » « less
3. DRE2: Achieving Data Resilience in Wireless Sensor Networks: A Quadratic Programming

   Hsu, Shanglin; Yu, Yuning; Tang, Bin (December 2020, IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2020))

   null (Ed.)

   We focus on sensor networks that are deployed in challenging environments, wherein sensors do not always have connected paths to a base station, and propose a new data resilience problem. We refer to it as DRE2: data resiliency in extreme environments. As there are no connected paths between sensors and the base station, the goal of DRE2 is to maximize data resilience by preserving the overflow data inside the network for maximum amount of time, considering that sensor nodes have limited storage capacity and unreplenishable battery power. We propose a quadratic programming-based algorithm to solve DRE2 optimally. As quadratic programming is NP-hard thus not scalable, we design two time efficient heuristics based on different network metrics. We show via extensive experiments that all algorithms can achieve high data resilience, while a minimum cost flow-based is most energy-efficient. Our algorithms tolerate node failures and network partitions caused by energy depletion of sensor nodes. Underlying our algorithms are flow networks that generalize the edge capacity constraint well-accepted in traditional network flow theory. 

   more » « less
4. Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity

   https://doi.org/10.1145/3382734.3405718  

   Chatterjee, Soumyottam; Gmyr, Robert; Pandurangan, Gopal (July 2020, PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing)

   null (Ed.)

   Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the worst-case time for all nodes to finish. The best-known (randomized) MIS algorithms take O(log n) worst-case rounds on general graphs (where n is the number of nodes). Breaking the O(log n) worst-case bound has been a longstanding open problem, while currently the best-known lower bound is [EQUATION] rounds. Motivated by the goal to reduce total energy consumption in energy-constrained networks such as sensor and ad hoc wireless networks, we take an alternative approach to measuring performance. We focus on minimizing the total (or equivalently, the average) time for all nodes to finish. It is not clear whether the currently best-known algorithms yield constant-round (or even o(log n)) node-averaged round complexity for MIS in general graphs. We posit the sleeping model, a generalization of the traditional model, that allows nodes to enter either "sleep" or "waking" states at any round. While waking state corresponds to the default state in the traditional model, in sleeping state a node is "offline", i.e., it does not send or receive messages (and messages sent to it are dropped as well) and does not incur any time, communication, or local computation cost. Hence, in this model, only rounds in which a node is awake are counted and we are interested in minimizing the average as well as the worst-case number of rounds a node spends in the awake state, besides the traditional worst-case round complexity (i.e., the rounds for all nodes to finish including both the awake and sleeping rounds). Our main result is that we show that MIS can be solved in (expected) O(1) rounds under node-averaged awake complexity measure in the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expected O(1)-rounds node-averaged awake complexity and, with high probability1 has O(log n)-rounds worst-case awake complexity and O(log3.41 n)-rounds worst-case complexity. Our work is a step towards understanding the node-averaged complexity of MIS both in the traditional and sleeping models, as well as designing energy-efficient distributed algorithms for energy-constrained networks. 

   more » « less
5. “Multi-Modulation Scheme for RFID-based Sensor Networks"

   https://doi.org/10.1007/978-3-030-67720-6_2  

   Z. Tian and Z.J. Haas (January 2021, Lecture notes of the Institute for Computer Sciences Social Informatics and Telecommunications Engineering)

   Gao, H.; Fan, P.; Wun, J.; Xiaoping, X.; Yu, J.; Wang, Y. (Ed.)

   RFID technology is playing an increasingly more important role in the Internet of Things, especially in the dense deployment model. In such networks, in addition to communication, nodes may also need to harvest energy from the environment to operate. In particular, we assume that our network model relies on RFID sensor network consisting of Wireless Identification and Sensing Platform (WISP) devices and RFID exciters. In WISP, the sensors harvest ambient energy from the RFID exciters and use this energy for communication back to the exciter. However, as the number of exciters is typically small, sensors further away from an exciter will need longer charging time to be able to transmit the same amount of information than a closer by sensor. Thus, further away sensors limit the overall throughput of the network. In this paper, we propose to use a multi-modulation scheme, which trades off power for transmission duration. More specifically, in this scheme, sensors closer to the exciter use a higher-order modulation, which requires more power than a lower-order modulation assigned to further away sensors, for the same bit error rate of all the sensors’ transmissions. This reduces the transmission time of the closer sensors, while also reducing the charging time of the further away sensors, overall increasing the total net-work throughput. The evaluation results show that the RFID sensor network with our multi-modulation scheme has significantly higher throughput as compared with the traditional single-modulation scheme. 

   more » « less