On efficient sensor scheduling for linear dynamical systems

Consider a set of sensors estimating the state of a process in which only one of these sensors can operate at each time-step due to constraints on the overall system. The problem addressed here is to choose which sensor should operate at each time-step to minimize a weighted function of the error covariances of the state estimates. This work investigates the development of tractable algorithms to solve for the optimal and suboptimal sensor schedules. A condition on the non-optimality of an initialization of the schedule is developed. Using this condition, both an optimal and a suboptimal algorithm are devised to prune the search tree of all possible sensor schedules. The suboptimal algorithm trades off the quality of the solution and the complexity of the problem through a tuning parameter. The performance of the suboptimal algorithm is also investigated and an analytical error bound is provided. Numerical simulations are conducted to demonstrate the performance of the proposed algorithms, and the application of the algorithms in active robotic mapping is explored.     

Energy efficient scheduling for real-time embedded systems with QoS guarantee

While the dynamic voltage scaling (DVS) techniques are efficient in reducing the dynamic energy consumption for the processor, varying voltage alone becomes less effective for the overall energy reduction as the static power is growing rapidly. On the other hand, Quality of Service (QoS) is also a primary concern in the development of today’s pervasive computing systems. In this paper, we propose a dynamic approach to minimize the overall energy consumption for soft real-time systems while ensuring the QoS-guarantee. The QoS requirements are deterministically quantified with the window-constraints, which require that at least m out of each non-overlapped window of k consecutive jobs of a task meet their deadlines. Necessary and sufficient conditions for checking the feasibility of task sets with arbitrary service times and periods are developed to ensure that the window-constraints can be guaranteed in the worst case. And efficient scheduling techniques based on pattern variation and dynamic slack reclaiming extensions are proposed to combine the task procrastination and dynamic slowdown to minimize the energy consumption. In contrast to the previous leakage-aware dynamic reclaiming work which never scales the job speed below the critical speed, we will show that it can be more energy efficient to reclaim the slack with speed lower than the critical speed when necessary. Through extensive simulations, our experiment results demonstrate that the proposed techniques significantly outperformed the previous research in both overall and idle energy reduction.     

Real-time scheduling for energy harvesting sensor nodes

Energy harvesting has recently emerged as a feasible option to increase the operating time of sensor networks. If each node of the network, however, is powered by a fluctuating energy source, common power management solutions have to be reconceived. This holds in particular if real-time responsiveness of a given application has to be guaranteed. Task scheduling at the single nodes should account for the properties of the energy source, capacity of the energy storage as well as deadlines of the single tasks. We show that conventional scheduling algorithms (like e.g. EDF) are not suitable for this scenario. Based on this motivation, we have constructed optimal scheduling algorithms that jointly handle constraints from both energy and time domain. Further we present an admittance test that decides for arbitrary task sets, whether they can be scheduled without deadline violations. To this end, we introduce the concept of energy variability characterization curves (EVCC) which nicely captures the dynamics of various energy sources. Simulation results show that our algorithms allow significant reductions of the battery size compared to Earliest Deadline First scheduling.

无线传感器网络中能量最优传输半径调整

在无线传感器网络中,为有效节省能量的消耗,一般将多跳路由上的冗余节点设置成休眠状态.针对节点均匀分布的线性网络,在候选路由节点随机确定,且各节点可有不同传输半径的情况下,利用动态规划算法选择合适的活动路由节点及其传输半径,达到总体最优能量消耗.数值结果证实算法的有效性.     

Energy efficient fault-tolerant earliest deadline first scheduling for hard real-time systems

Aggressive technology scaling has dramatically increased the power density and degraded the reliability of embedded real-time systems. The goal of our research in this paper is to develop effective scheduling methods that can minimize the energy consumption and, at the same time, tolerate up to \(K\) transient faults when executing a hard real-time system scheduled according to the EDF policy. Three scheduling algorithms are presented in this paper. The first algorithm is an extension of a well-known fault oblivious low-power scheduling algorithm. The second algorithm intends to minimize the energy consumption under the fault-free situation while reserving adequate resources for recovery when faults strike. The third algorithm improves upon the first two by sharing the reserved resources and thus can achieve better energy efficiency. Simulation results show that the proposed algorithms consistently outperform other related approaches in energy savings.     

Energy-aware lazy scheduling algorithm for energy-harvesting sensor nodes

The main problem in dealing with energy-harvesting (EH) sensor nodes is represented by the scarcity and non-stationarity of powering, due to the nature of the renewable energy sources. In this work, the authors address the problem of task scheduling in processors located in sensor nodes powered by EH sources. Some interesting solutions have appeared in the literature in the recent past, as the lazy scheduling algorithm (LSA), which represents a performing mix of scheduling effectiveness and ease of implementation. With the aim of achieving a more efficient and conservative management of energy resources, a new improved LSA solution is here proposed. Indeed, the automatic ability of foreseeing at run-time the task energy starving (i.e. the impossibility of finalizing a task due to the lack of power) is integrated within the original LSA approach. Moreover, some modifications have been applied in order to reduce the LSA computational complexity and thus maximizing the amount of energy available for task execution. The resulting technique, namely energy-aware LSA, has then been tested in comparison with the original one, and a relevant performance improvement has been registered both in terms of number of executable tasks and in terms of required computational burden.     

Dynamic sensor transmission power scheduling for remote state estimation

In this paper, we consider the problem of sensor transmission power scheduling for remote state estimation. We assume that the sensor has two transmission energy levels, where the high level corresponds to a high packet reception ratio. By exploiting the feedback information from the remote estimator, we aim to find an optimal transmission power schedule. We formulate the problem as a Markov decision process, and analytically develop a simple and optimal dynamic schedule which minimizes the average estimation error under the energy constraint. Furthermore, we derive the necessary and sufficient condition under which the remote state estimator is stable. It is shown that the estimation stability only depends on the high-energy packet reception ratio and the spectral radius of the system dynamic matrix.     

A cross-layer transmission scheduling scheme for wireless sensor networks

In a wireless sensor network, the sensor nodes are densely deployed for detecting in many cases. One design challenge for such a network is how to devise a good data fusion algorithm for information retrieval. Noting that the channel state information (CSI) between the cluster head and the sensor nodes will influence the received bit energy noise ratio of the sensor nodes, we propose an optimal data fusion algorithm taking into account the CSI for a one-hop clustered wireless sensor network. On the basis of the fusion algorithm, we consider the redundancy of the sensor deployment and propose a cross-layer transmission scheduling scheme. By selecting proper set of sensor nodes to transmit their local information back in turn, the scheme can prolong the lifetime of the sensor network. The numerical and simulation results show that it can get a good tradeoff between the energy efficiency and the performance.     

An efficient heuristic for selecting active nodes in wireless sensor networks

Energy saving is a paramount concern in wireless sensor networks (WSNs). A strategy for energy saving is to cleverly manage the duty cycle of sensors, by dynamically activating different sets of sensors while non-active nodes are kept in a power save mode. We propose a simple and efficient approach for selecting active nodes in WSNs. Our primary goal is to maximize residual energy and application relevance of selected nodes to extend the network lifetime while meeting application-specific QoS requirements. We formalize the problem of node selection as a knapsack problem and adopt a greedy heuristic for solving it. An environmental monitoring application is chosen to derive some specific requirements. Analyses and simulations were performed and the impact of various parameters on the process of node selection was investigated. Results show that our approach outperforms a naı¨ve scheme for node selection, achieving large energy savings while preserving QoS requirements.     

无线传感器网络中的簇头节点能耗平衡策略

无线传感器网络（WSNs）具有集中式数据收集和多对一数据通信等特点,使得越靠近汇聚节点的簇头节点能耗越大,最终导致网络中心出现能量空洞。提出一种基于簇内节点分配的簇头节点能耗平衡策略,根据WSNs的分簇汇聚拓扑结构,分析了其中簇头节点的能量消耗情况;在此基础上,通过在各簇内分配一定数量的基本节点,并成比例地增加附加节点的方式,使网络中各簇头节点的能量消耗相等。仿真结果表明：该策略能够适应网络规模和负载的动态变化,最终达到平衡簇头节点能耗的目的。     

Power efficient rate monotonic scheduling for multi-core systems

More computational power is offered by current real-time systems to cope with CPU intensive applications. However, this facility comes at the price of more energy consumption and eventually higher heat dissipation. As a remedy, these issues are being encountered by adjusting the system speed on the fly so that application deadlines are respected and also, the overall system energy consumption is reduced. In addition, the current state of the art of multi-core technology opens further research opportunities for energy reduction through power efficient scheduling. However, the multi-core front is relatively unexplored from the perspective of task scheduling. To the best of our knowledge, very little is known as of yet to integrate power efficiency component into real-time scheduling theory that is tailored for multi-core platforms. In this paper, we first propose a technique to find the lowest core speed to schedule individual tasks. The proposed technique is experimentally evaluated and the results show the supremacy of our test over the existing counterparts. Following that, the lightest task shifting policy is adapted for balancing core utilization, which is utilized to determine the uniform system speed for a given task set. The aforementioned guarantees that: (i) all the tasks fulfill their deadlines and (ii) the overall system energy consumption is reduced.     

An efficient dynamic scheduling algorithm for multiprocessorreal-time systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters     

无线传感器网络的能量有效加权分簇算法

在能量有效加权分簇(EWC)算法的基础上,提出一种簇首选择算法EWC-N(new EWC)。该算法根据节点的邻节点数量与剩余能量计算出权值,选出权值大的节点为簇首,在选择簇首的过程中,动态调整簇首之间的距离。该算法减少了分簇过程中能量的消耗,簇首的分布更加合理。仿真实验结果表明,该算法相对于EWC提高了能量有效利用率近9%,延长了约12%的网络生存时间。     

Energy efficient spatial TDMA scheduling in wireless networks

It is now widely acknowledged that packet scheduling can have a significant impact in the overall energy consumption levels of wireless networks. In this paper, a low complexity algorithm based on Local Search (LS) is proposed for spatial-TDMA networks such that the power consumption is minimized without sacrificing throughput or delay. More specifically, given a schedule of a pre-defined frame length we search for a low power schedule with the same length. Numerical investigations reveal that the proposed heuristic has a competitive performance and achieves considerable gains when compared to previously proposed scheduling techniques. Despite the centralized nature of the algorithm, its low complexity and high accuracy make it a very competitive solution for the power efficient scheduling problem.     

水下传感器网络节点定位信号设计

提出一种对于水下传感器网络节点位置信息进行码分多址的编码方式。介绍了码分多址编码的基本思想,用复杂可编程逻辑器件(CPLD)实现分频电路,m序列与正弦波产生电路,以及ASK调制电路。给出了整个程序设计的流程图。实验证明:电路设计简单,工作稳定,多个节点的位置信息能够简单有效的传输。     

Energy efficient algorithms for enhancing lifetime in wireless sensor networks

Microsystem Technologies - A crucial research problem in the field of wireless sensor network is to maximize its lifetime. One approach to solve this problem is to group the nodes in clusters or...     

An efficient weighted bi-objective scheduling algorithm for heterogeneous systems

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.     

Visual sensor network lifetime maximization by prioritized scheduling of nodes

Visual surveillance of a designated air space can be achieved by a randomly distributed camera sensor network spread over a large area. The location and field of view of each battery operated sensor, after a calibration phase, will be known to a central processing node. To increase the lifetime of the network, the density of distributed sensors could be such that a subset of sensors can cover the required air space. As a sensor dies another sensor should be selected to compensate for the dead one and reestablish the complete coverage. This process should be continued until complete coverage is not achievable by the existing sensors. Thereafter, a graceful degradation of the coverage is desirable.The goal is to elongate the lifetime of the network while maintaining a maximum possible coverage of the designated air space. Since the selection of a subset of sensors for complete coverage of the target area is an NP-complete problem, we present a number of heuristics for this case. The proposed methods are categorized in two groups. In one category, the sensors are prioritized based on their visual and communicative properties and the selection is performed according to the prioritizing function. In the other group, we propose traditional evolutionary and swarm intelligence algorithms. The performance of the proposed methods is evaluated through extensive simulations.     

无线传感器网络中一种能量有效的分簇算法

无线传感器网络的一个重要特点是能量受限,必须设计能量效率高的路由算法以延长网络生存时间.基于经典的低能耗自适应分簇算法(LEACH),提出了一种能量有效分簇算法(EECA).它由基站根据节点剩余能量和簇首之间的距离选择簇首,从而使簇的分布更均匀,簇首的负载更均衡,提高了能量的利用率,延长了网络生存时间.仿真结果表明:EECA算法与LEACH算法相比,网络的生存时间可以延长约37%,能量利用率提高近16%.