Long-term patient monitoring is an important issue especially for the elderly. This can be done using a wearable wireless sensor network. These sensors have limited resources in terms of computation, storage memory, s...
详细信息
Long-term patient monitoring is an important issue especially for the elderly. This can be done using a wearable wireless sensor network. These sensors have limited resources in terms of computation, storage memory, size and mainly in power. In this work, a real-time resource-efficient algorithm has been implemented and tested practically such that not all the Electrocardiography (ECG) data are transmitted to the server for later processing. The algorithm reads a sample window and processes it on the sensor node using an adaptive filter with a differentiator and then a fast and simple algorithm for feature extraction of the ECG signal to find P, Q, R, S and T waves. Finally, a classifier algorithm has been designed to distinguish between normal and abnormal ECG signals. The work has been implemented using Shimmer sensor nodes and uses the open source TinyOS 2.1.2 and Python 2.7.
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 b...
详细信息
ISBN:
(纸本)9781450375825
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.. 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 Omega(root log n/log log n) 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 prob
暂无评论