Maximizing the Lifetime of Embedded Systems Powered by Fuel Cell-Battery Hybrids

Fuel cell (FC) is a viable alternative power source for portable applications; it has higher energy density than traditional Li-ion battery and thus can achieve longer lifetime for the same weight or volume. However, because of its limited power density, it can hardly track fast fluctuations in the load current of digital systems. A hybrid power source, which consists of a FC and a Li-ion battery, has the advantages of long lifetime and good load following capabilities. In this paper, we consider the problem of extending the lifetime of a fuel-cell-based hybrid source that is used to provide power to an embedded system which supports dynamic voltage scaling (DVS). We propose an energy-based optimization framework that considers the characteristics of both the energy consumer (the embedded system) and the energy provider (the hybrid power source). We use this framework to develop algorithms that determine the output power level of the FC and the scaling factor of the DVS processor during task scheduling. Simulations on task traces based on a real-application (Path Finder) and a randomized version demonstrate significant superiority of our algorithms with respect to a conventional DVS algorithm which only considers energy minimization of the embedded system.      

Performance evaluation of sensor deployment using optimization techniques and scheduling approach for K-coverage in WSNs

In the wireless sensor networks, sensor deployment and coverage are the vital parameter that impacts the network lifetime. Network lifetime can be increased by optimal placement of sensor nodes and optimizing the coverage with the scheduling approach. For sensor deployment, heuristic algorithm is proposed which automatically adjusts the sensing range with overlapping sensing area without affecting the high degree of coverage. In order to demonstrate the network lifetime, we propose a new heuristic algorithm for scheduling which increases the network lifetime in the wireless sensor network. Further, the proposed heuristic algorithm is compared with the existing algorithms such as ant colony optimization, artificial bee colony algorithm and particle swarm optimization. The result reveals that the proposed heuristic algorithm with adjustable sensing range for sensor deployment and scheduling algorithm significantly increases the network lifetime.     

HashHeat: A hashing-based spatiotemporal filter for dynamic vision sensor

Neuromorphic event-based dynamic vision sensors (DVS) have much faster sampling rates and a higher dynamic range than frame-based imagers. However, they are sensitive to background activity (BA) events that are unwanted. We propose HashHeat, a hashing-based spatiotemporal BA filter for DVS. It is the first spatiotemporal filter that doesn't scale with the DVS output size and doesn't store the 32-bits timestamps. We not only give the visual denoising effect of the filter but also use two metrics for quantitatively analyzing the filter's global performance and local performance respectively, where we introduce a novel metric for evaluating global performance. The experimental results show that HashHeat achieves similar global performance as baseline filters, but increases the signal to noise ratio by about 1.5x to nearly 5x compared with other baseline filters concerning the local performance. The hardware implementation enables HashHeat to output a labeled event every 10ns and meets the real-time requirement. And it can reduce the storage cost by 128x to 256x compared with baseline filters.     

Energy-efficient scheduling for multiprocessors

An energy-efficient scheduling algorithm is proposed for parallel tasks in a multiprocessor system. The proposed algorithm utilises the dynamic voltage scaling (DVS) method for low energy consumption and executes tasks in parallel to compensate for the execution delay induced by the DVS method     

几种实时嵌入式系统DVS策略的分类比较

动态电压调节是一种有效的运用于实时嵌入式系统中的低功耗技术。实时嵌入式系统DVS技术不仅要实现系统功耗的降低,同时也要兼顾系统的实时性,满足任务的截止时间限。该文针对近几年实时嵌入式系统中DVS策略,首先介绍实时系统中DVS策略模型,对主流策略进行分类比较,并且对相应策略进行仿真,DVS策略可以取得10%～40%的能耗节省。     

A multiprocessor-oriented power-conscious scheduling algorithm for periodic tasks

With the rapid development of advanced technology in VLSI circuit designs, many processors could provide dynamic voltage scaling (DVS) to save power consumption when the supply voltage is allowed to be lower. In this paper, we propose a multiprocessor-oriented power-conscious scheduling algorithm for the real-time periodic tasks with task migration constrained scheme. We classify periodic tasks into fixed tasks and migration tasks, and limit the number of migration tasks and the number of destination processors which execute migration tasks. The proposed algorithm is made up of two steps. Firstly, choosing a processor to sort all of the periodic tasks in a non-increasing order according to task utilization, afterwards, allocating them to other processors. Secondly, scheduling the migration tasks with a virtual execution windows policy, and then scheduling the fixed tasks with EDF algorithm. The experiment results show that compared with arbitrary task migration policy and no task migration allowed policy, the power consumption in multiprocessor real-time periodic tasks scheduling is lowered significantly with the proposed algorithm.     

Fast direct solution of standard moment-method matrices

All of the matrices which arise in the method-of-moments solution of scattering and antenna problems have a hidden structure. This structure is due to the physics of electromagnetic interactions. Matrix-algebra routines are used to uncover this structure in moment-method matrices, after they have been calculated. This structure is used to create a sparse representation of the matrix. Although this step involves an approximation, the error involved can be nearly as small as the precision of the calculation. Then, without further approximation, a sparse representation of the LU factorization of this matrix is computed. A significant speed improvement is realized over that of the standard LU factorization of this matrix. The resulting method can be added to any of a variety of moment-method programs to solve the matrix problem more quickly, and with less computer memory. For large problems this is the time-critical operation, so this allows larger problems to be solved. The computer program we have written can be used immediately with most moment-method programs, since it amounts to simply a better matrix-inversion package. The method presented is referred to as the LU sparse integral factored representation (LUSIFER)     

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

A distributed mobile DSP system consists of a group of mobile devices with different computing powers. These devices are connected by a wireless network. Parallel processing in the distributed mobile DSP system can provide high computing performance. Due to the fact that most of the mobile devices are battery based, the lifetime of mobile DSP system depends on both the battery behavior and the energy consumption characteristics of tasks. In this paper, we present a systematic system model for task scheduling in mobile DSP system equipped with Dynamic Voltage Scaling (DVS) processors and energy harvesting techniques. We propose the three-phase algorithms to obtain task schedules with shorter total execution time while satisfying the system lifetime constraints. The simulations with randomly generated Directed Acyclic Graphs (DAG) show that our proposed algorithms generate the optimal schedules that can satisfy lifetime constraints.     

Real-Time Dynamic Voltage Loop Scheduling for Multi-Core Embedded Systems

In this brief, we propose a novel real-time loop-scheduling technique to minimize energy consumption via dynamic voltage scaling (DVS) for applications with loops considering transition overhead. One algorithm, dynamic voltage loop scheduling (DVLS), is designed integrating with DVS. In DVLS, we repeatedly regroup a loop based on rotation scheduling and decrease the energy by DVS as much as possible within a timing constraint. We conduct the experiments on a set of digital signal processing benchmarks. The experimental results show that DVLS achieves big energy saving compared with the traditional time-performance-oriented scheduling algorithm     

Power-Saving Scheduling for Multiple-Target Coverage in Wireless Sensor Networks

We address the multiple-target coverage problem (MTCP) in wireless sensor networks (WSNs). We also propose an energy-efficient sensor-scheduling algorithm for multiple-target coverage (MTC) that considers both the transmitting energy for collected data and overlapped targets. We introduce two algorithms: one optimal, the other heuristic. Simulation results show that the proposed algorithms can contribute to extending the lifetime of network and that the heuristic algorithm is more practical than the optimal algorithm with respect to complexity.     

Optimal 3-Coverage with Minimum Separation Requirements for Ubiquitous Computing Environments

Sensors have been increasingly used for many ubiquitous computing applications such as asset location monitoring, visual surveillance, and human motion tracking. In such applications, it is important to place sensors such that every point of the target area can be sensed by more than one sensor. Especially, many practical applications require 3-coverage for triangulation, 3D hull building, and etc. Also, in order to extract meaningful information from the data sensed by multiple sensors, those sensors need to be placed not too close to each other—minimum separation requirement. To address the 3-coverage problem with the minimum separation requirement, our recent work  (Kim et al. 2008) proposes two heuristic methods, so called, overlaying method and TRE-based method, which complement each other depending on the minimum separation requirement. For these two methods, we also provide mathematical analysis that can clearly guide us when to use the TRE-based method and when to use the overlaying method and also how many sensors are required. To make it self-contained, in this paper, we first revisit the two heuristic methods. Then, as an extension, we present an ILP-based optimal solution targeting for grid coverage. With this ILP-based optimal solution, we investigate how much close the two heuristic methods are to the optimal solution. Finally, this paper discusses the impacts of the proposed methods on real-deployed systems using two example sensor systems. To the best of our knowledge, this is the first work that systematically addresses the 3-coverage problem with the minimum separation requirement.     

Load balancing techniques for lifetime maximizing in wireless sensor networks

Energy consumption has been the focus of many studies on Wireless Sensor Networks (WSN). It is well recognized that energy is a strictly limited resource in WSNs. This limitation constrains the operation of the sensor nodes and somehow compromises the long term network performance as well as network activities. Indeed, the purpose of all application scenarios is to have sensor nodes deployed, unattended, for several months or years.This paper presents the lifetime maximization problem in “many-to-one” and “mostly-off” wireless sensor networks. In such network pattern, all sensor nodes generate and send packets to a single sink via multi-hop transmissions. We noticed, in our previous experimental studies, that since the entire sensor data has to be forwarded to a base station via multi-hop routing, the traffic pattern is highly non-uniform, putting a high burden on the sensor nodes close to the base station.In this paper, we propose some strategies that balance the energy consumption of these nodes and ensure maximum network lifetime by balancing the traffic load as equally as possible. First, we formalize the network lifetime maximization problem then we derive an optimal load balancing solution. Subsequently, we propose a heuristic to approximate the optimal solution and we compare both optimal and heuristic solutions with most common strategies such as shortest-path and equiproportional routing. We conclude that through the results of this work, combining load balancing with transmission power control outperforms the traditional routing schemes in terms of network lifetime maximization.     

基于ERPMT改进启发式方法的WSN寿命最大化算法

针对传感器节点的电池容量限制导致无线传感网络寿命低的问题,基于容量最大化(CMAX)、线上最大化寿命(OML)两种启发式方法以及高效路由能量管理技术(ERPMT),提出了基于ERPMT改进启发式方法的无线传感网络寿命最大化算法。首先,通过启发式方法初始化每个传感器节点,将节点能量划分为传感器节点起源数据和其它节点数据延迟;然后利用加入的一种优先度量延迟一跳节点的能量消耗;最后,根据路径平均能量为每个路由分配一个优先级,并通过ERPMT实现最终的无线传感网络优化。针对不同分布类型网络寿命的实验验证了本文算法的有效性及可靠性,实验结果表明,相比较为先进的启发式方法CMAX及OML,本文算法明显增大了无线传感网络的覆盖范围,并且大大地延长了网络的寿命。     

Low-energy GALS NoC with FIFO—Monitoring dynamic voltage scaling

In this paper we propose two dynamic voltage scaling (DVS) policies for a GALS NoC, which is designed based on fully asynchronous switch architectures. The first one is a history-based DVS policy, which exploits the link utilization and adjusts the voltages of different parts of the router among a few voltage levels. The second one is a FIFO-adaptive DVS, which uses two FIFO threshold levels for decision making. It judiciously adjusts supply voltage of each switch among only three voltage levels. The introduced architecture is simulated in 90 nm CMOS technology with accurate Spice simulations. Experimental results show that the FIFO-adaptive DVS not only lowers the implementation cost, but also in a 86 % saturated network achieves 36 % energy-delay product (ED) saving compared to the DVS policy based on link utilization.     

Multi-objective design space exploration for system partitioning of FPGA-based Dynamic Partially Reconfigurable Systems

Dynamic Partial Reconfiguration (DPR) enables resource sharing in FPGA-based systems. It can also be used for the mitigation of aging-related permanent faults by increasing the number of redundant Partially Reconfigurable Regions (PRRs). Normally, these PRRs are able to host any of the Partially Reconfigurable Modules (PRMs), or tasks, at one particular instance. This kind of system is called homogeneous. However, the FPGA resource constraints limit the amount of homogeneous redundancy that can be used and hence affect the lifetime of the system. This issue can be addressed by utilizing the heterogeneous approach where each PRR now only hosts a subset of the tasks. Further, the deadlines of the applications must also be taken care of in the design phase to decide the mapping and scheduling of tasks to PRRs. To this end, we propose an application-specific multi-objective system-level design methodology to determine the appropriate number of PRRs and the mapping and scheduling of tasks to the PRRs. Specifically, we propose a lifetime-aware scheduling method that maximizes the system's mean time to failure (MTTF) with different tolerances in the makespan specification of an application. We use the scheduler along with an automated floorplanner for design space exploration at design-time to generate a feasible heterogeneous PRR-based system. Our experiments show that the heterogeneous systems can offer more than 2x lifetime improvement over homogeneous ones. It also offers better scaling with increased tolerance in makespan specification.     

OFDM调制中高速FFT处理器的设计与实现

通过对通用算法对比和分析，介绍了一种利用混合基、多块存储器的原位算法构成、能够实现持续处理的多模式FFT处理器的设计和实现。该FFT处理器采用类似块浮点的数据收缩方法，结构简单、速度高、性能好、功耗低，不仅满足高速计算的要求，而且减小了硬件实现的复杂度、易于FPGA实现，因此可以适用于多载波OFDM调制系统中。     

Elastic DVS Management in Processors With Discrete Voltage/Frequency Modes

Applying classical dynamic voltage scaling (DVS) techniques to real-time systems running on processors with discrete voltage/frequency modes causes a waste of computational resources. In fact, whenever the ideal speed level computed by the DVS algorithm is not available in the system, to guarantee the feasibility of the task set, the processor speed must be set to the nearest level greater than the optimal one, thus underutilizing the system. Whenever the task set allows a certain degree of flexibility in specifying timing constraints, rate adaptation techniques can be adopted to balance performance (which is a function of task rates) versus energy consumption (which is a function of the processor speed). In this paper, we propose a new method that combines discrete DVS management with elastic scheduling to fully exploit the available computational resources. Depending on the application requirements, the algorithm can be set to improve performance or reduce energy consumption, so enhancing the flexibility of the system. A reclaiming mechanism is also used to take advantage of early completions. To make the proposed approach usable in real-world applications, the task model is enhanced to consider some of the real CPU characteristics, such as discrete voltage/frequency levels, switching overhead, task execution times nonlinear with the frequency, and tasks with different power consumption. Implementation issues and experimental results for the proposed algorithm are also discussed     

Design and analysis of asynchronous wakeup for wireless sensor networks

In wireless sensor networks, scheduling the sleep duration of each node is one of the key elements for controlling critical performance metrics such as energy consumption and latency. Since the wakeup interval is a primary parameter for determining the sleeping schedule, how to tune the wakeup interval is crucial for the overall network performance. In this paper, we present an effective framework for tuning asynchronous wakeup intervals of IEEE 802.15.4 sensor networks from the energy consumption viewpoint. First, we derive an energy consumption model of each node as an explicit function of the wakeup interval, and empirically validate the derived model. Second, based on the proposed model, we formulate the problem of tuning the wakeup interval with the following two objectives: to minimize total energy consumption and to maximize network lifetime. We show that these two problems can be optimally solved by an iterative algorithm with global information by virtue of the convexity of the problem structure. Finally, as practical solutions, we further propose heuristic optimization algorithms that only exploit local information. In order to develop heuristic algorithms, we propose two broadcasting schemes, which are entitled as maximum wakeup interval broadcasting and efficient local maximum broadcasting. These broadcasting algorithms enable nodes in the network to have heterogeneous wakeup intervals.     

Energy-efficient DSPs for wireless sensor networks

There are many new challenges to be faced in implementing signal processing algorithms and designing energy-efficient DSPs for microsensor networks. We study system partitioning of computation to improve the energy efficiency of a wireless sensor networking application. We explore system partitioning between the sensor cluster and the base station, employing computation-communication tradeoffs to reduce energy dissipation. Also we show that system partitioning of computation within the cluster can also improve the energy efficiency by using dynamic voltage scaling (DVS)     

Synthesizing Energy-Efficient Embedded Systems with LOPOCOS

In this paper, we introduce the LOPOCOS (Low Power Co-synthesis) system, a prototype CAD tool for system level co-design. LOPOCOS targets the design of energy-efficient embedded systems implemented as heterogeneous distributed architectures. In particular, it is designed to solve the specific problems involved in architectures that include dynamic voltage scalable (DVS) processors. The aim of this paper is to demonstrate how LOPOCOS can support the system designer in identifying energy-efficient hardware/software implementations for the desired embedded systems. Hence, highlighting the necessary optimization steps during design space exploration for DVS enable architectures. The optimization steps carried out in LOPOCOS involve component allocation and task/communication mapping as well as scheduling and dynamic voltage scaling. LOPOCOS has the following key features, which contribute to this energy efficiency. During the voltage scaling valuable power profile information of task execution is taken into account, hence, the accuracy of the energy estimation is improved. A combined optimization for scheduling and communication mapping based on genetic algorithm, optimizes simultaneously execution order and communication mapping towards the utilization of the DVS processors and timing behaviour. Furthermore, a separation of task and communication mapping allows a more effective implementation of both task and communication mapping optimizationsteps. Extensive experiments are conducted to demonstrate the efficiency of LOPOCOS. We report up to 38% higher energy reductions compared to previous co-synthesis techniques for DVS systems. The investigations include a real-life example of an optical flow detection algorithm.