Recently, benefiting from rapid development of energy harvesting technologies, the research trend of wireless sensor networks has shifted from the battery‐powered network to the one that can harvest energy from ambient environments. In such networks, a proper use of harvested energy poses plenty of challenges caused by numerous influence factors and complex application environments. Although numerous works have been based on the energy status of sensor nodes, no work refers to the issue of minimizing the overall data transmission cost by adjusting transmission power of nodes in energy‐harvesting wireless sensor networks. In this paper, we consider the optimization problem of deriving the energy‐neutral minimum cost paths between the source nodes and the sink node. By introducing the concept of energy‐neutral operation, we first propose a polynomial‐time optimal algorithm for finding the optimal path from a single source to the sink by adjusting the transmission powers. Based on the work earlier, another polynomial‐time algorithm is further proposed for finding the approximated optimal paths from multiple sources to the sink node. Also, we analyze the network capacity and present a near‐optimal algorithm based on the Ford–Fulkerson algorithm for approaching the maximum flow in the given network. We have validated our algorithms by various numerical results in terms of path capacity, least energy of nodes, energy ratio, and path cost. Simulation results show that the proposed algorithms achieve significant performance enhancements over existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.
- Award ID(s):
- 1763627
- NSF-PAR ID:
- 10352311
- Date Published:
- Journal Name:
- Lecture notes of the Institute for Computer Sciences Social Informatics and Telecommunications Engineering
- Volume:
- 352
- ISSN:
- 1867-822X
- Page Range / eLocation ID:
- 17-36
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract -
Battery-free sensing devices harvest energy from their surrounding environment to perform sensing, computation, and communication. This enables previously impossible applications in the Internet-of-Things. A core challenge for these devices is maintaining usefulness despite erratic, random or irregular energy availability; which causes inconsistent execution, loss of service and power failures. Adapting execution (degrading or upgrading) seems promising as a way to stave off power failures, meet deadlines, or increase throughput. However, because of constrained resources and limited local information, it is a challenge to decide when would be the best time to adapt, and how exactly to adapt execution. In this paper, we systematically explore the fundamental mechanisms of energy-aware adaptation, and propose heuristic adaptation as a method for modulating the performance of tasks to enable higher sensor coverage, completion rates, or throughput, depending on the application. We build a task based adaptive runtime system for intermittently powered sensors embodying this concept. We complement this runtime with a user facing simulator that enables programmers to conceptualize the tradeoffs they make when choosing what tasks to adapt, and how, relative to real world energy harvesting environment traces. While we target battery-free, intermittently powered sensors, we see general application to all energy harvesting devices. We explore heuristic adaptation with varied energy harvesting modalities and diverse applications: machine learning, activity recognition, and greenhouse monitoring, and find that the adaptive version of our ML app performs up to 46% more classifications with only a 5% drop in accuracy; the activity recognition app captures 76% more classifications with only nominal down-sampling; and find that heuristic adaptation leads to higher throughput versus non-adaptive in all cases.more » « less
-
Currently, there is an increasing interest in the use of RFID systems with passive or battery-less tags with sensors incorporated, also known as computational RFID (CRFID) systems. These passive tags use the reader signal to power up their microcontroller and an attached sensor. Following the current standard EPC C1G2, the reader must identify the tag (receive the tag's identification code) prior to receive data from its sensor. In a typical RFID scenario, several sensor tags share the reader interrogation zone, and during their identification process, their responses often collide, increasing their identification time. Therefore, RFID application developers must be mindful of tag anti-collision protocols when dealing with CRFID tags in dense RFID sensor networks. So far, significant effort has been invested in simulation-based analysis of the performance of anti-collision protocols regarding the tags identification time. However, no one has explored the experimental performance of anti-collision protocols in an RFID sensor network using CRFID. This paper: (i) demonstrates that the impact of one tag identification time over the total time required to read one sensor data from that same tag is very significant, and (ii) presents an UHF-SDR RFID system which validates the improvement of FuzzyQ, a fast anticollision protocol, in relation to the protocol used in the current RFID standard.more » « less
-
Battery-free sensing devices harvest energy from their surrounding environment to perform sensing, computation, and communication. A core challenge for these devices is maintaining usefulness despite erratic, random, or irregular energy availability, which causes inconsistent execution, loss of service, and power failures. Adapting execution (degrading or upgrading) based on available or predicted power/energy seems promising to stave off power failures, meet deadlines, or increase throughput. However, due to constrained resources and limited local information, deciding what and when exactly to adapt is challenging. This article explores the fundamentals of energy-aware adaptation for intermittently powered computers and proposes heuristic adaptation mechanisms to dynamically modulate the program complexity at run-time to enable higher sensor coverage and throughput. While we target battery-free, intermittently powered, resource-constrained sensors, we see a general application to all energy harvesting devices.more » « less
-
Real-time embedded systems perform many important functions in the modern world. A standard way to tolerate faults in these systems is with Byzantine fault-tolerant (BFT) state machine replication (SMR), in which multiple replicas execute the same software and their outputs are compared by the actuators. Unfortunately, traditional BFT SMR protocols are
slow , requiring replicas to exchange sensor data back and forth over multiple rounds in order to reach agreement before each execution. The state of the art in reducing the latency of BFT SMR iseager execution , in which replicas execute on data from different sensors simultaneously on different processor cores. However, this technique results in 3–5× higher computation overheads compared to traditional BFT SMR systems, significantly limiting schedulability.We present
CrossTalk , a new BFT SMR protocol that leverages the prevalence of redundant switched networks in embedded systems to reduce latency without added computation. The key idea is to use specific algorithms to move messages between redundant network planes (which many systems already possess) as the messages travel from the sensors to the replicas. As a result,CrossTalk can ensure agreementautomatically in the network, avoiding the need for any communication between replicas. Our evaluation shows thatCrossTalk improves schedulability by 2.13–4.24× over the state of the art. Moreover, in a NASA simulation of a real spaceflight mission,CrossTalk tolerates more faults than the state of the art while using nearly 3× less processor time.