Tasks with precedence constraints to be scheduled.
Abstract
This chapter studies a power management problem for supercapacitor-based wireless sensor nodes with energy harvesting capabilities. A dependent task scheduling algorithm for nonpreemptable tasks with precedence constraints is developed. The modified first in first out (MFIFO) algorithm takes into account supercapacitor state and energy harvesting. Task precedence constraints are handled by defining a variable called task effective release time. Results show that the MFIFO algorithm improves the energy performance of the first in first out (FIFO) algorithm and maintains the timing perform-ance at the same time.
Keywords
- algorithm
- energy harvesting
- power management
- supercapacitor charge redistribution
- dependent task scheduling
- wireless sensor network
1. Introduction
Wireless sensor networks have been developed for many applications. A wireless sensor network is composed of a large number of spatially distributed wireless sensor nodes. Wireless sensor nodes are usually powered by nonrechargeable batteries with limited capacity. Therefore, energy efficiency is a major concern. To maximize the network lifetime, various power management strategies have been proposed to minimize the energy consumption. In the meantime, numerous energy harvesting technologies have been developed to increase the energy income. Environmentally powered wireless sensor nodes usually need energy storage systems [1] to buffer the harvested energy. Typical energy storage systems include rechargeable batteries [2], supercapacitors [3–5], and hybrid systems [6, 7]. In general, rechargeable batteries have a larger capacity while supercapacitors have a much longer cycle life. The major drawback of supercapacitors is their high self-discharge rate. Supercapacitor characteristics must be taken into account to develop effective power management solutions. For instance, supercapacitor self-discharge is considered in Refs. [3, 6]. This is because the supercapacitor terminal voltage is a critical parameter in analyzing the power behavior of supercapacitor-based energy storage systems, and self-discharge results in voltage drop. Because of the significance of the voltage drop during self-discharge, this characteristic has been extensively examined [8–14].
While supercapacitor self-discharge leads to voltage drop, this characteristic cannot completely characterize the supercapacitor voltage behavior. In fact, the supercapacitor voltage may increase under the open circuit condition [15], which is due to the charge redistribution characteristic. A mechanism of the low ionic mobility in supercapacitor micropores is identified in Ref. [16]. The impact of charge redistribution on power management is qualitatively investigated in Ref. [17]. A detailed analysis of the voltage change during charge redistribution is performed in Ref. [18]. In Ref. [19], the modified earliest deadline first (MEDF) algorithm is developed for scheduling independent tasks.
This chapter extends the results in Refs. [17–19] and studies a new power management problem. Specifically, this chapter develops a modified first in first out (MFIFO) algorithm for scheduling tasks with precedence constraints in environmentally powered wireless sensor nodes that use supercapacitor-based energy storage systems. The MFIFO algorithm takes into account supercapacitor charge redistribution and energy harvesting. Task precedence constraints are handled by defining a variable called task effective release time. While the first in first out (FIFO) algorithm only considers the timing constraints of tasks, the MFIFO algorithm also considers the energy constraints.
The remainder of this chapter is organized as follows. Section 2 describes a system model for analyzing the power flow in wireless sensor nodes. Section 3 develops the MFIFO algorithm. Section 4 illustrates the implementation setup. A case study and extensive simulations are performed to evaluate the algorithm performance. These qualitative and quantitative results demonstrate that the MFIFO algorithm improves the energy performance of the FIFO algorithm while maintaining its timing performance. Section 5 concludes this chapter.
2. A power model for wireless sensor nodes
2.1. System model
This chapter adopts the wireless sensor node power model used in Ref. [19]. As shown in Figure 1, this model is composed of five modules: energy harvester, input power conditioning unit, energy buffer, output power conditioning unit, and energy user. Energy harvesters such as solar cells and piezoelectric films convert energy in other forms to electricity. Typically, an input power conditioning unit is needed to bridge the energy harvester and the energy buffer. For example, a solar-powered wireless sensor node usually includes a maximum power point tracker (MPPT). Energy buffers such as rechargeable batteries and supercapacitors are devices that store the harvested energy. An output power conditioning unit is often necessary to generate a suitable power supply for the energy user. DC-DC converters are commonly used modules to bridge the energy buffer and the energy user. Energy users are mainly RF transceivers, microcontrollers, and sensors.
The power model can be further abstracted to facilitate analyzing the power flow in wireless sensor nodes. As shown in Figure 1, the power model has three components: energy source, energy storage, and energy consumer. The energy source includes the energy harvester and the input power conditioning unit. For clarity, the energy buffer is referred to as the energy storage in this three-component model. The energy consumer combines the output power conditioning unit and the energy user. This abstracted model introduces two benefits. First, by separating energy buffers and power conditioning units, it is more convenient to study the impact of energy buffer characteristics on power management in wireless sensor nodes. Second, experiments with energy buffers can be readily designed and performed. The effects of input and output power conditioning units are taken into account in the process of designing the experiments.
2.2. Energy source model
The component models are shown in Figure 2. The energy source is modeled as a current pulse train. As shown in Figure 2(a), each current pulse is characterized by three parameters: begin time
2.3. Energy storage model
The energy storage system is a single supercapacitor. Figure 2(b)
shows the variable leakage resistance (VLR) model [10, 11, 17, 18] for supercapacitors, which is a simplified equivalent circuit model. In this model, the first branch has three components: resistor
In addition to the model parameters, the voltages across the capacitors in the VLR model are also critical to determine the supercapacitor state. The charge stored in a supercapacitor tends to redistribute among
2.4. Energy consumer model
When the energy consumer initiates an event, the energy storage system is assigned a task. The energy consumer is therefore modeled as a current pulse train. As shown in Figure 2(c), each task is defined by four parameters: release time
2.5. Task precedence constraint and effective release time
In this chapter, the tasks are assumed to be dependent and nonpreemptable. In addition to the four parameters (release time, execution time, deadline, and weight) used to characterize the task model, a task may also have precedence constraints. If tasks are constrained to execute in some order, they are said to have precedence constraints. The precedence constraints among tasks are specified using precedence relations [20]. A task
The release times of tasks with precedence constraints are sometimes inconsistent with the precedence constraints, which means that the release time of a task may be later than that of its successor. Figure 3
shows two tasks
3. MFIFO algorithm development
The MFIFO algorithm has three steps. First, create an initial schedule using the FIFO algorithm. This step takes care of the timing constraints and precedence constraints of tasks. Second, calculate the ready time adjustment margin based on the initial schedule. This margin determines how much delay is allowed if the ready time of the initial schedule is adjusted. Third, the ready time offset is determined based on supercapacitor state and energy harvesting. The start time of a task is the ready time plus the ready time offset.
3.1. Create an initial schedule using FIFO algorithm
The FIFO algorithm is used to create an initial schedule to ensure that the task precedence constraints are satisfied. The tasks are originally defined by the task set
1:
2:
3:
4:
5:
6:
7:
8: Sort
9: Current Time
10:
11: Ready Time
12: Current Time
13:
14: Algorithm output is initial schedule
3.2. MFIFO algorithm
Once the initial schedule is determined, the ready time adjustment margin and ready time offset are calculated using the algorithms for the second and third steps in the MEDF algorithm [19], respectively. In particular, the release times used in the MEDF algorithm should be replaced by the effective release times. The complete MFIFO algorithm is summarized in Algorithm 2. The inputs of this algorithm include a set of
1.
2.
3.
1: Step 1: Create an initial schedule using Algorithm 1.
2: Input: task set
3: Output: initial schedule
4: Step 2: Calculate ready time adjustment margin of the initial schedule using the second algorithm in Ref. [19].
5: Input: modified task set
6: Output: task ready time adjustment margin
7: Step 3: Determine ready time offset of the initial schedule using the third algorithm in Ref. [19].
8: Input: modified task set
9: Output: modified schedule
10: MFIFO Algorithm Output: modified schedule
4. MFIFO algorithm implementation and evaluation
4.1. Simulation setup
The MFIFO algorithm is implemented and evaluated using a simulation setup similar to the one used for the MEDF algorithm [19]. The energy source and energy storage models are exactly the same. The energy consumer model is modified. Each task set has six periodic tasks and each periodic task has five jobs. Therefore, each task set is composed of 30 tasks. The timing and energy parameters of a task are defined in the same way as the one used for the MEDF algorithm, too. The precedence constraints are assigned with controlled randomness. The six periodic tasks are partitioned into three groups. Each group consists of two periodic tasks. For convenience, the six periodic tasks are numbered as {
4.2. An example
An example is used to illustrate the implementation and evaluation of the MFIFO algorithm. The simulation setup is adopted from Ref. [19], which is used to illustrate the MEDF algorithm implementation and evaluation. The supercapacitor initial state is
T1 | T2 | T3 | T4 | T5 | T6 | |
---|---|---|---|---|---|---|
Release time ( |
0 | 80 | 160 | 30 | 130 | 230 |
Effective release time ( |
0 | 80 | 160 | 88 | 130 | 230 |
Execution time ( |
8 | 8 | 8 | 10 | 10 | 10 |
Deadline ( |
80 | 160 | 240 | 130 | 230 | 330 |
Weight ( |
35 | 30 | 40 | 42 | 37 | 33 |
The FIFO schedule determined using Algorithm 1 is shown in Figure 5
. All the tasks are scheduled for execution at their effective release times. The task
The task ready time adjustment margin and task ready time offset results are listed in Tables 2 and 3, respectively. The task start time is then determined, and the MFIFO schedule is finalized. The MFIFO schedule is shown in Figure 7. Tasks
FIFO schedule | T1 | T2 | T4 | T5 | T3 | T6 |
---|---|---|---|---|---|---|
FIFO schedule ready time ( |
0 | 80 | 88 | 130 | 160 | 230 |
Ready time flag ( |
0 | 0 | 0 | 0 | 0 | 0 |
Maximum delay margin |
72 | 72 | 32 | 90 | 72 | 90 |
Available delay margin ( |
72 | 72 | 32 | 90 | 72 | 90 |
End time interval ( |
72 | 0 | 32 | 20 | 62 | N/A |
Ready time adjustment margin |
72 | 0 | 32 | 20 | 62 | N/A |
FIFO schedule | T1 | T2 | T4 | T5 | T3 | T6 |
---|---|---|---|---|---|---|
FIFO schedule ready time ( |
0 | 80 | 88 | 130 | 160 | 230 |
Ready time adjustment margin |
72 | 0 | 32 | 20 | 62 | N/A |
Execution time ( |
8 | 8 | 10 | 10 | 8 | 10 |
Latest end time |
80 | 88 | 130 | 160 | 230 | N/A |
1 | 1.1005 | 1.0738 | 0.8825 | 1.1539 | N/A | |
1 | 1.0247 | 1.0287 | 1.0109 | 1.0352 | N/A | |
If |
False | True | True | False | True | N/A |
If |
False | True | True | False | True | N/A |
Ready time offset ( |
72 | 0 | 0 | 20 | 0 | N/A |
MFIFO start time |
72 | 80 | 88 | 150 | 160 | 230 |
4.3. Evaluation results
The simulations are run for 200 times using the setup specified in Ref. [19]. The deadline miss rates and energy violation rates are recorded for the FIFO and MFIFO schedules. The obtained evaluation metrics are sorted in the ascending order and plotted. As shown in Figure 9
, 35 out of the 200 simulation runs have zero deadline miss rates. The FIFO and MFIFO algorithms always have the same deadline miss rates. The timing and precedence constraints of the FIFO schedules are preserved in the MFIFO schedules. The energy violation rates are shown in Figure 10
. For the FIFO algorithm, 96 out of the 200 simulation runs have an energy violation rate
The simulation setup is slightly modified to quantitatively compare the energy violation rates of the FIFO and MFIFO algorithms. The duty cycles of the six periodic tasks take the same value for each utilization. The utilization is
5. Conclusion
This chapter proposes the MFIFO algorithm for nonpreemptable tasks with precedence constraints. The task precedence constraints are transformed into timing constraints by defining the effective release time of a task. The MFIFO algorithm takes into account the energy constraints of tasks in addition to the timing constraints. The MFIFO algorithm is implemented and evaluated. Simulation results show that the MFIFO algorithm improves the energy performance of the FIFO algorithm and maintains the timing performance at the same time.
References
- 1.
S. Sudevalayam, P. Kulkarni, Energy harvesting sensor nodes: Survey and implications, IEEE Communications Surveys & Tutorials 13 (3) (2011) 443–461. - 2.
C. Alippi, C. Galperti, An adaptive system for optimal solar energy harvesting in wireless sensor network nodes, IEEE Transactions on Circuits and Systems I, Regular Papers 55 (6) (2008) 1742–1750. - 3.
T. Zhu, Z. Zhong, Y. Gu, T. He, Z.-L. Zhang, Leakage-aware energy synchronization for wireless sensor networks, in: MobiSys ’09, 2009, pp. 319–332. - 4.
D. Brunelli, C. Moser, L. Thiele, L. Benini, Design of a solar-harvesting circuit for batteryless embedded systems, IEEE Transactions on Circuits and Systems I: Regular Papers 56 (11) (2009) 2519–2528. - 5.
F. Simjee, P. H. Chou, Everlast: Long-life, supercapacitor-operated wireless sensor node, in: ISLPED ’06, 2006, pp. 197–202. - 6.
X. Jiang, J. Polastre, D. Culler, Perpetual environmentally powered sensor networks, in: IPSN ’05, 2005, pp. 463–468. - 7.
H. Yang, Y. Zhang, Modeling and analysis of hybrid energy storage systems for wireless sensor networks, in: Proceedings of SPIE, Vol. 7647, 2010, pp. 76472U:1–76472U:10. - 8.
B. E. Conway, W. Pell, T.-C. Liu, Diagnostic analyses for mechanisms of self-discharge of electrochemical capacitors and batteries, Journal of Power Sources 65 (1997) 53–59. - 9.
Y. Diab, P. Venet, H. Gualous, G. Rojat, Self-discharge characterization and modeling of electrochemical capacitor used for power electronics applications, IEEE Transactions on Power Electronics 24 (2009) 510–517. - 10.
Y. Zhang, H. Yang, Modeling and characterization of supercapacitors for wireless sensor network applications, Journal of Power Sources 196 (8) (2011) 4128–4135. - 11.
H. Yang, Y. Zhang, Self-discharge analysis and characterization of supercapacitors for environmentally powered wireless sensor network applications, Journal of Power Sources 196 (20) (2011) 8866–8873. - 12.
H. Yang, Y. Zhang, Evaluation of supercapacitor models for wireless sensor network applications, in: Proceedings of the 5th International Conference on Signal Processing and Communication Systems, 2011, pp. 1–6. - 13.
H. Yang, Y. Zhang, Modeling and analysis of a solar powered wireless sensor node, in: Proceedings of the 2012 International Conference on Computing, Networking and Communications, 2012, pp. 970–974. - 14.
H. Yang, Task scheduling in supercapacitor based environmentally powered wireless sensor nodes, Ph.D. thesis, Georgia Institute of Technology, 2013 Atlanta, GA, USA. - 15.
M. Kaus, J. Kowal, D. U. Sauer, Modelling the effects of charge redistribution during self-discharge of supercapacitors, Electrochimica Acta 55 (25) (2010) 7516–7523. - 16.
J. W. Graydon, M. Panjehshahi, D. W. Kirk, Charge redistribution and ionic mobility in the micropores of supercapacitors, Journal of Power Sources 245 (2014) 822–829. - 17.
H. Yang, Y. Zhang, Analysis of supercapacitor energy loss for power management in environmentally powered wireless sensor nodes, IEEE Transactions on Power Electronics 28 (11) (2013) 5391–5403. - 18.
H. Yang, Y. Zhang, A study of supercapacitor charge redistribution for applications in environmentally powered wireless sensor nodes, Journal of Power Sources 273 (2015) 223–236. - 19.
H. Yang, Y. Zhang, A task scheduling algorithm based on supercapacitor charge redistribution and energy harvesting for wireless sensor nodes, Journal of Energy Storage 6 (2016) 186–194. - 20.
J. W. S. Liu, Real-Time Systems, 1st Edition, Prentice Hall, 2000 Upper Saddle River, NJ, USA.