Filter (type):

Sort (year):

Acheron: Persisting Tombstones in LSM Engines

Zichen Zhu, Subhadeep Sarkar, Manos Athanassoulis
D-2 Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, USA, June 2023

Abstract

Coming soon!

The LSM Design Space and its Read Optimizations

Subhadeep Sarkar, Niv Dayan, Manos Athanassoulis
T-2 Proceedings of the IEEE International Conference on Data Engineering (ICDE), Anahiem, CA, USA, April 2023

Abstract

Log-structured merge (LSM) trees have emerged as one of the most commonly used storage-based data structures in modern data systems as they offer high throughput for writes and good utilization of storage space. However, LSM-trees were not originally designed to facilitate efficient reads. Thus, state-of-the-art LSM engines employ numerous optimization techniques to make reads efficient. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with the various optimization techniques and hybrid designs adopted by LSM engines to accelerate reads.

Toward this, we first discuss the basic LSM operations and their access patterns. We then discuss techniques and designs that optimize point and range lookups in LSM-trees: (i) index and (ii) filter data structures, (iii) caching, and (iv) read- friendly data layouts. Next, we present the performance tradeoff between writes and reads, outlining the rich design space of the LSM paradigm and how one can navigate it to improve query performance. We conclude by discussing practical problems and open research challenges. This will be a 1.5-hour tutorial.

Read full paper

Indexing for Near-Sorted Data

Aneesh Raman, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis
C-12 Proceedings of the IEEE International Conference on Data Engineering (ICDE), Anahiem, CA, USA, April 2023

Abstract

Indexing in modern data systems facilitates efficient query processing when the selection predicate is on an indexed key. As new data is ingested, indexes are gradually populated with incoming entries. In that respect, indexing can be perceived as the process of adding structure to incoming, otherwise unsorted data. Adding structure, however, comes at a cost. Instead of simply appending the incoming entries, we insert them into the index. If the ingestion order matches the indexed attribute order, the ingestion cost is entirely redundant and can be avoided altogether (e.g., via bulk loading in a B+-tree). However, classical tree index designs do not benefit when incoming data comes with an implicit ordering that is close to being sorted, but not fully sorted.

In this paper, we study how indexes can exploit near-sortedness. Particularly, we identify sortedness as a resource that can accelerate index ingestion. We propose a new sortedness-aware (SWARE) design paradigm that combines opportunistic bulk loading, index appends, variable node fill and split factors, and an intelligent buffering scheme, to optimize ingestion and read queries in a tree index in the presence of near-sortedness. We apply SWARE to two state-of-the-art search trees (B+tree and Bε-tree), and we demonstrate that their Sortedness-Aware counterparts (SA B+-tree and SA Bε-tree) outperform their respective baselines by up to 8.8x (SA B+-tree) and 7.8x (SA Bε-tree) for a write-heavy workload in the presence of data sortedness, while offering competitive read performance, leading to overall benefits between 1.3x-5x for mixed read/write workloads with near-sorted data. Overall, we highlight that SWARE can be applied to other tree-like data structures to accelerate index ingestion and improve their performance in the presence of data sortedness.

Read full paper

Toward Building Deletion Compliant Data Systems

Subhadeep Sarkar
A-1 International Workshop on High Performance Transaction Systems (HPTS), Pacific Grove, CA, USA, October 2022

Abstract

Modern data systems are designed around the silent underlying assumption of perpetual data retention. Systems are designed to offer high performance for data ingestion and queries, while deletion of data is realized by simply logically invalidating the target entries (instead of modifying them in place). This has severe implications on the privacy front, especially, in light of the newly enforced privacy regulations which are aimed toward enabling the users to express their preferences about the deletion of their data. In this paper, we present our vision of enabling privacy-through-deletion as a design element in modern data systems empowering them with the ability to ensure timely and persistent deletion of data, and we envision doing so without hurting performance or increasing operational cost.

Read full paper

BODS: A Benchmark on Data Sortedness

Aneesh Raman, Konstantinos Karatsenidis, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis
C-11 Proceedings of the TPC Technology Conference on Performance Evaluation & Benchmarking (TPCTC), Sydney, Australia, September 2022

Abstract

Indexes in data systems accelerate data access by adding structure to otherwise unstructured data at the cost of index construction and maintenance. Data systems, and particularly, the underlying indexing data structures are designed to offer favorable ingestion (and query) performance for the two extremes of data sortedness, i.e., unsorted data (often assumed to follow a uniform random distribution) or fullysorted data. However, in practice, data may arrive with an intermediate degree of pre-sortedness. In such cases, where data arrives nearly (but not necessarily fully) sorted, the intuition is that the indexing cost should be lower than when ingesting unsorted data. Such sortedness-aware index designs lack from the literature. In fact, there is a need for a framework to explore how index designs may be able to exploit pre-existing sortedness during data ingestion to amortize the index construction cost.

In this paper, we present Benchmark on Data Sortedness, BoDS for short, that highlights the performance of data systems in terms of index construction and navigation costs when operating on data ingested with variable sortedness. To quantify data sortedness, we use the stateof-the-art (K,L)-sortedness metric. Specifically, BoDS benchmarks the indexing performance of a data system as we vary the two fundamental components of the metric: (i) K, that measures how many elements are out-of-order in a data collection; and (ii) L, that measures by how much the out-of-order entries are displaced from their respective in-order positions; as well as (iii) the distribution of L. We present in detail the benchmark, and we run it on PostgreSQL, a popular, production-grade relational database system. Unsurprisingly, we observe that PostgreSQL cannot exploit data sortedness; however, through our experiments we show the headroom for improvement, and we lay the groundwork for experimentation with sortedness-aware index designs. The code for BoDS is available at: https://github.com/BU-DiSC/bods.

Read full paper

Dissecting, Designing, and Optimizing LSM-based Data Stores

Subhadeep Sarkar, Manos Athanassoulis
T-1 Proceedings of the ACM SIGMOD International Conference on Management of Data, Philadelphia, PA, USA, June 2022

Abstract

Log-structured merge (LSM) trees have emerged as one of the most commonly used disk-based data structures in modern data systems. LSM-trees employ out-of-place ingestion to support high throughput for writes, while their immutable file structure allows for good utilization of disk space. Thus, the log-structured paradigm has been widely adopted in state-of-the-art NoSQL, relational, spatial, and time-series data systems. However, despite their popularity, there is a lack of pedagogical textbook-like material on LSM designs. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with a digest of optimizations and new designs proposed in recent research and adopted by modern LSM engines. This will serve as introductory material for non-experts, and as a roadmap to cutting-edge LSM results for the LSM-aware researchers and practitioners.

Toward this, we first discuss in detail the basic operations (inserts, updates, deletes, point and range queries), their access patterns and their paths through the LSM data structure. We then dive into the details of recent research on optimizing each of those operations. We first discuss techniques and designs that optimize data ingestion, and then, we discuss new data structures that optimize read queries. Finally, we present the rich design space of the log-structured paradigm and outline how to navigate it and tune LSM-based systems. We conclude with a discussion on open challenges on LSM systems. This will be a 1.5-hour tutorial.

Read full paper

Compactionary: A Dictionary for LSM Compactions

Subhadeep Sarkar, Kaijei Chen, Zichen Zhu, Manos Athanassoulis
D-1 Proceedings of the ACM SIGMOD International Conference on Management of Data, Philadelphia, PA, USA, June 2022

Abstract

Log-structured merge (LSM) trees are widely used as the storage layer of production NoSQL data stores, as they offer efficient ingestion performance. To enable competitive read performance and reduce space amplification, LSM-trees periodically re-organize data layout on disk iteratively, through compactions. Compactions are at the heart of every LSM-based storage engine, fundamentally influencing their performance in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. However, the process of compaction in LSM-engines is often treated as a black-box that is rarely exposed as a tuning knob. In this paper, we demonstrate Compactionary, a dictionary for LSM compactions, outlining the implications of compactions on performance, and how different LSM tunings and workloads influence compactions.

Compactionary breaks down the LSM compaction black-box, expressing compactions as an ensemble of four first-order design choices: (i) when to compact, (ii) how to organize the data after compaction, (iii) how much data to compact, and (iv) which data to compact. We configure Compactionary to demonstrate the operational flow of a family of state-of-the-art LSM compaction strategies and how each strategy influences the performance of the storage engine. The participants can (i) customize the workload, (ii) configure the LSM tuning, and (iii) switch between advanced compaction options, to understand individually the impacts of the different factors on performance. Further, to engage the interested participants, we extend the demonstration by allowing the participants (i) to create custom hybrid compaction strategies, as well as (ii) to configure the settings separately for each strategy in an individual analysis phase. The demo is available at https://disc-projects.bu.edu/compactionary/\#interactiveDemo.

Read full paper

Building Deletion-Compliant Data Systems

Manos Athanassoulis, Subhadeep Sarkar, Tarikul Islam Papon, Zichen Zhu, Dimitris Staratzis
J-10 IEEE Data Engineering Bulletin (DEBull), Volume 45, Issue 1, March 2022

Abstract

Most modern data systems have been designed with two goals in mind -- fast ingestion and low-latency query processing. The first goal has led to the development of a plethora of write-optimized data stores that employ the out-of-place paradigm. Due to their write-optimized design, out-of-place data systems perform deletes logically via invalidation, and retain the invalid data for arbitrarily long. However, due to the recent enactment of new data privacy regulations, the requirement of timely deletion of user data has become central. The right to be forgotten (in EU's GDPR), right to delete (in California's CCPA and CPRA), or deletion right (in Virginia's VCDPA) mandates service providers to persistently delete a user's data within a pre-set time duration. Logical deletion in out-of-place data systems, however, does not offer guarantees for timely and persistent deletion, and attempting to enforce it using existing tools leads to poor performance and increased operational costs.

In this paper, we present a new framework for building deletion-compliant data systems from a holistic perspective. We analyze the new regulations and the requirements derived from the new policies, and we propose changes in the application and the system layer of data management. We outline the new types of deletion requests that need to be supported, the query language modifications needed to be able to request for timely persistent data deletion, and the system-level changes needed to realize timely and persistent deletes. The proposed framework for deletion compliance lays the groundwork for a new class of data systems that can offer system-level guarantees for user data privacy. We present recent results spanning all layers of the framework: the requirements and the application layer target any database system, while the system layer discussion is geared towards out-of-place systems. Finally, we conclude with a discussion on the next steps and the open challenges on building deletion-compliant data systems.

Read full paper

Query Language Support for Timely Data Deletion

Subhadeep Sarkar, Manos Athanassoulis
C-8 Proceedings of the International Conference on Extending Database Technology (EDBT), Edinburgh, UK, March-April 2022

Abstract

A key driver of modern data systems is the requirement for fast ingestion while ensuring low-latency query processing. This has led to the birth of write-optimized data stores that realize ingestion (inserts, updates, and deletes) in an out-of-place manner. Deletes in such out-of-place data stores are performed logically via invalidation while retaining the invalidated data for arbitrarily long. At the same time, with new policy changes, such as the introduction of the right to be forgotten (in EU's GDPR), the right to delete (in California's CCPA and CPRA), and the deletion right (in Virginia's VCDPA), the importance of timely and persistent deletion of user data has become critical.

In this paper, we point out that state-of-the-art query languages lack the necessary support to express a user's preferences for data retention and deletion. Toward this, we first identify two classes of deletes: (i) retention-based deletion and (ii) on-demand deletion, that need to be supported for regulation compliance. Next, we present the challenges in transforming these user deletion requirements into application-level specifications. For this, we propose query language extensions that can express both on-demand and timely persistent deletion of user data. Finally, we discuss how the application and system level modifications work hand-in-hand under the privacy regulations and act as stepping stones toward designing deletion-compliant data systems.

Read full paper

Constructing and Analyzing the LSM Compaction Design Space

Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, Manos Athanassoulis
C-7 Proceedings of the PVLDB Endowment, Volume 11, Issue 14, Copenhagen, Denmark, August 2021

Abstract

Log-structured merge (LSM) trees offer efficient ingestion by appending incoming data, and thus, are widely used as the storage layer of production NoSQL data stores. To enable competitive read performance, LSM-trees periodically re-organize data to form a tree with levels of exponentially increasing capacity, through iterative compactions. Compactions fundamentally influence the performance of an LSM-engine in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. Hence, choosing the appropriate compaction strategy is crucial and, at the same time, hard as the LSM compaction design space is vast, largely unexplored, and has not been formally defined in the literature. As a result, most LSM-based engines use a fixed compaction strategy, typically hand-picked by an engineer, which decides how and when to compact data.

In this paper, we present the design space of LSM-compactions, and evaluate state-of-the-art compaction strategies with respect to key performance metrics. Toward this goal, our first contribution is to introduce a set of four design primitives that can formally define any compaction strategy: (i) the compaction trigger, (ii) the data layout, (iii) the compaction granularity, and (iv) the data movement policy. Together, these primitives can synthesize both existing and completely new compaction strategies. Our second contribution is to experimentally analyze 10 compaction strategies. We present 12 observations and 7 high-level takeaway messages, which show how LSM systems can navigate the compaction design space.

Read full paper

Lethe: A Tunable Delete-Aware LSM Engine

Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Manos Athanassoulis
C-6 Proceedings of the ACM SIGMOD International Conference on Management of Data, Portland, OR, USA, June 2020

Abstract

Data-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource.

To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17-1.4x) and lower space amplification (2.1-9.8x), with a modest increase in write amplification (between 4% and 25%). In addition, Lethe supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance nor employing a costly full tree merge.

Read full paper

i-MAC: In-Body Sensor MAC in Wireless Body Area Networks for Healthcare IoT

Sudip Misra, Pradyumna Kumar Bishoyi, Subhadeep Sarkar
J-9 IEEE Systems Journal, Volume 15, Issue 3, 2020

Abstract

The application of Internet-of-Things (IoT) technology in modern healthcare environment has given rise to a new paradigm known as healthcare IoT. The wireless body area network (WBAN) is one of the basic building blocks of IoT-based healthcare system, comprising many wearable (on-body) and implant (in-body) sensors placed in or around patient body connected to a hub for physiological signal monitoring. In in-body sensor-based WBAN, guaranteeing quality-of-service and prolonging network lifetime are major impediments due to the sensor location and limited battery capacity. In this article, we propose a novel energy-efficient medium access control (MAC) protocol for IEEE 802.15.6 standard complaint in-body sensor-based WBAN. Typically, the in-body sensor-based WBAN communication is hub-initiated; however, in case of an emergency event, the in-body sensor node transmits an emergency frame arbitrarily without sensing the channel. This inadvertent in-body sensor-initiated transmission has a very high probability of collision with the ongoing hub-initiated transmission, and/or another in-body sensor-initiated emergency frame transmission. This results in emergency frame retransmission and consequently affects the node's energy consumption and lifetime. To alleviate this issue, we propose a modified superframe structure, in which separate access phases are introduced for the emergency event and regular event. In case of an emergency event, a novel emergency event handling scheme and a ranking and priority assignment protocol is proposed to detect and address the critical event of in-body sensors. To minimize the collision, a scheduled access mechanism is proposed according to the criticality of the node. Performance analysis of the proposed in-body sensor MAC is done in terms of latency and overall power consumption, in case of both emergency and regular events.

Read full paper

Sensors, Cloud, and Fog: The Enabling Technologies for the Internet of Things

Sudip Misra, Subhadeep Sarkar, Subarna Chatterjee
B-1 CRC Press, Taylor & Francis Group, July 2019

Summary

This book provides an in-depth understanding of Internet of Things (IoT) technology. It highlights several of today's research and technological challenges of translating the concept of the IoT into a practical, technologically feasible, and business-viable solution. It introduces two novel technologies -- sensor-cloud and fog computing -- as the crucial enablers for the sensing and compute backbone of the IoT. The book discusses these two key enabling technologies of IoT that include a wide range of practical design issues and the futuristic possibilities and directions involving sensor networks and cloud and fog computing environments towards the realization and support of IoT.

Get Full Version

Towards Enforcement of the EU GDPR: Enabling Data Erasure

Subhadeep Sarkar, Jean-Pierre Banatre, Loius Rilling, Christine Morin
C-5 IEEE International Conference on Internet of Things (iThings), Halifax, Canada, July - August 2018

Abstract

With the emergence of the Internet of Things (IoT), an increasing need for preserving the privacy of personal data has been realized. In this context, the EU has recently published the general data protection regulation (GDPR), which ensures strengthening of the privacy rights of the data subjects concerning their personal data. In this paper, we present the importance of having a holistic solution aimed towards the enforcement of the GDPR. As a first step towards the enforcement of the GDPR, we present the research challenges in facilitating the erasure of data as per the right to erasure. We also propose the envisaged technical solutions to work through the challenges.

Read full paper

Privacy-Aware Blind Cloud Framework for Advanced Healthcare

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra
J-8 IEEE Communications Letters, Volume 21, Issue 11, August 2017

Abstract

This letter proposes a novel privacy-aware “blind” cloud infrastructure to be utilized for storage, processing, and organization of health data. Traditional healthcare systems rely on cloud computing servers for back-end storage and processing. However, cloud servers are heavily vulnerable to privacy threats and the problem is even more intense as physiological data carry sensitive information. To resolve the aforementioned issue, this letter proposes the blind cloud framework. The goal is to take advantage of the enormous computing and storage abilities of the cloud servers, and yet maintain data anonymity simultaneously. To preserve the privacy of the medical data, the cloud server is forcefully blinded, i.e., the identities of the patients are masked off and a pseudo-identity is generated, thereby, obtaining unidentified in-cloud data for storage and analysis. We also propose a parallel method to be executed within the non-cloud servers for efficient and lossless identity management and retrieval. Results indicate that the performance of the processes of pseudo-identity generation and identity retrieval is independent of the data volumes, and negligibly vary with the increase in the number of the clients of the system.

Read full paper

Assessment of the Suitability of Fog Computing in the Context of Internet of Things

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra
J-6 IEEE Transactions on Cloud Computing, Volume 6, Issue 1, January 2018

Abstract

This work performs a rigorous, comparative analysis of the fog computing paradigm and the conventional cloud computing paradigm in the context of the Internet of Things (IoT), by mathematically formulating the parameters and characteristics of fog computing – one of the first attempts of its kind. With the rapid increase in the number of Internet-connected devices, the increased demand of real-time, low-latency services is proving to be challenging for the traditional cloud computing framework. Also, our irreplaceable dependency on cloud computing demands the cloud data centers (DCs) always to be up and running which exhausts huge amount of power and yield tons of carbon dioxide (CO2) gas. In this work, we assess the applicability of the newly proposed fog computing paradigm to serve the demands of the latency-sensitive applications in the context of IoT. We model the fog computing paradigm by mathematically characterizing the fog computing network in terms of power consumption, service latency, CO2 emission, and cost, and evaluating its performance for an environment with high number of Internet-connected devices demanding real-time service. A case study is performed with traffic generated from the 100 highest populated cities being served by eight geographically distributed DCs. Results show that as the number of applications demanding real-time service increases, the fog computing paradigm outperforms traditional cloud computing. For an environment with 50% applications requesting for instantaneous, real-time services, the overall service latency for fog computing is noted to decrease by 50:09%. However, it is mentionworthy that for an environment with less percentage of applications demanding for low-latency services, fog computing is observed to be an overhead compared to the traditional cloud computing. Therefore, the work shows that in the context of IoT, with high number of latency-sensitive applications fog computing outperforms cloud computing.

Read full paper

Optimal Decision Rule-Based Ex-ante Frequency Hopping for Jamming Avoidance in Wireless Sensor Networks

Prasenjit Bhavathankar, Subhadeep Sarkar, Sudip Misra
J-7 Computer Networks, Elsevier, Volume 128, March 2017

Abstract

In this paper, we consider a static wireless sensor network (WSN) affected by a constant, static jammer. Both the nodes in the network and the jammer are capable of switching frequencies. Existing literature mostly thrive on mechanisms with a mutually pre-decided hopping-sequence or on random frequency-hopping techniques. However, these mechanisms often fall short in the context of energy-constrained WSNs. We propose a frequency-hopping strategy based on the optimal decision rule. The proposed solution takes into account the individual decision profiles of all the concerned nodes, and finally, makes the decision for the welfare of the overall network. The objective is to find an optimal frequency hopping rule to obtain the maximum throughput. We observe that the packet delivery ratio of the network improves by approximately 30% after the application of the optimal decision rule for frequency-hopping. The overall network energy consumption is also improved by approximately 53% by the application of the proposed solution approach, as observed from the results.

Read full paper

Resource Allocation for Wireless Body Area Networks in Presence of Selfish Agents

Subhadeep Sarkar, Sudip Misra, Mohammad S. Obaidat
C-4 IEEE GLOBECOM, Washington, DC, USA, December 2016

Abstract

In medical emergency situations, fair distribution of resources in a multi-tenant scenario is crucial. In such resource-constrained situations, these organizations may behave in a non-cooperative and selfish manner to maximize their individual incentives at the cost of the overall system welfare. Existing research works on dynamic resource allocation, have mostly assumed that the participating agents always behave truthfully, and place bids in accordance with their actual requirements. In practice, this assumption may not always hold true, as organizations have positive incentives for overstating. We design an algorithm, grounded in the theory of distributed mechanism design, to effectively alleviate untruthful demeanor of the organizations. The proposed resource allocation algorithm allows such organizations to maximize their individual incentives only by acting truthfully, whilst the overall system welfare is also maximized. The mechanism designed is resilient to selfish behavior of the organizations, and ensures voluntary participation of the organizations in the auction. It is also incentive compatible in nature, and dictates a truthful incentive-payment scheme.

Read full paper

Theoretical Modelling of Fog Computing: A Green Computing Paradigm to Support IoT Applications

Subhadeep Sarkar, Sudip Misra
J-5 IET Networks, Volume 5, Issue 2, March 2016

Abstract

In this study, the authors focus on theoretical modelling of the fog computing architecture and compare its performance with the traditional cloud computing model. Existing research works on fog computing have primarily focused on the principles and concepts of fog computing and its significance in the context of internet of things (IoT). This work, one of the first attempts in its domain, proposes a mathematical formulation for this new computational paradigm by defining its individual components and presents a comparative study with cloud computing in terms of service latency and energy consumption. From the performance analysis, the work establishes fog computing, in collaboration with the traditional cloud computing platform, as an efficient green computing platform to support the demands of the next generation IoT applications. Results show that for a scenario where 25% of the IoT applications demand real-time, low-latency services, the mean energy expenditure in fog computing is 40.48% less than the conventional cloud computing model.

Read full paper

From Micro to Nano: The Evolution of Wireless Sensor-Based Health Care

Subhadeep Sarkar, Sudip Misra
J-4 IEEE PULSE, Volume 7, Issue 1, January 2016

Abstract

Over the past decade, embedded systems and micro-electromechanical systems have evolved in a radical way, redefining our standard of living and enhancing the quality of life. Health care, among various other fields, has benefited vastly from this technological development. The concept of using sensors for health care purposes originated in the late 1980s when sensors were developed to measure certain physiological parameters associated with the human body. In traditional sensor nodes, the signal sources are mostly different environmental phenomena (such as temperature, vibration, and luminosity) or man-made events (such as intrusion and mobile target tracking), whereas in case of the physiological sensors, the signal source is living human tissue. These sensor nodes, as their primary sensing element, have a diaphragm that converts pressure into displacement. This displacement, in turn, is subsequently transformed into an electrical signal. The concept of wireless physiological sensor nodes, however, gained popularity in the mid-2000s, with the sensed data from the nodes transmitted to the hub via a wireless medium. The network formed by this heterogeneous set of wireless body sensor nodes is termed a wireless body-area network (WBAN). Each WBAN is essentially a composition of multiple wireless body sensor nodes and a single hub. The hub is primarily responsible for acquisition of the raw sensed data from all the component sensor nodes and first-level aggregation of the data before transmitting the aggregated data for further analysis to a remote data acquisition center. Here, we outline the evolution of WBANs in the context of modern health care and its convergence with nanotechnology.

Read full paper

A Privacy-Aware Ambulatory Healthcare System Using Wireless Body Area Networks (WBANs)

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra, Ezaj A. Ansari, Dipayan Ghatak, Saurav Sarkar
IP-1 Indian Patent (filed) | January 2016 | File number: 201631000214

Abstract

The proposed invention relates to the development of a Wireless Body Area Network (WBAN)-equipped "blind" cloud system to enhance the existing ambulatory healthcare system without having extensive infrastructural dependence. As per the traditional healthcare techniques of the country, the diagnosis of a patient commences only after s/he is admitted to a medical unit or hospital. Thus, in cases of extreme criticality or medical emergency, the patient often undergoes tremendous inconvenience which may even be fatal. The proposed invention aims at introducing a novel ambulatory healthcare system coupled with the recent technological advancements. The idea behind this invention is to provide majorly unmanned, automated, pervasive, remote, real-time ambulatory healthcare services. After getting into an ambulance, a patient would be made to wear a set of easy, light-weighted, and convenient wireless body sensor nodes which would form a WBAN, and would instantaneously initiate the capturing the patient’s physiological data. These data would be fed to remote cloud servers in real time from where it would undergo a perfunctory analysis. To enhance the precision of the analytics, the invention envisions gathering a real-time medical history of the patient through a simple, form-based interface (with assistance from a paramedic). Based on the data criticality and medical history, voice or text-based feedback directives will be delivered at the patient’s end and will be executed by the paramedic within the ambulance. The invention is strongly dependent on cloud computing technology as the cloud servers serve as the primary hubs of storage and computation of the system. However, to address the issues related to security, data confidentiality, and vulnerability of cloud computing, the invention proposes to develop a completely “blind” cloud platform. The goal is to take advantage of the enormous computing and storage abilities of the cloud servers by maintaining data anonymity simultaneously. To preserve the privacy of the medical data, we propose an intelligent method to mask the identity of the patients, i.e., the users of the system, and thereby, obtaining unidentified data for storage and analysis. We also propose a parallel method to be executed within the non-cloud servers for efficient and lossless identity management and retrieval.

Quantification of Node Misbehavior in Wireless Sensor Networks: A Social Choice-Based Approach

Subarna Chatterjee, Subhadeep Sarkar, Sudip Misra
C-3 IEEE International Conference on Communications (ICC) Workshops, London, UK, June 2015

Abstract

This work focuses on the quantification of node misbehavior in wireless sensor networks (WSNs). Misbehaving nodes are common within WSNs which are once detected, are penalized and in some cases eliminated from the network. However, node misbehavior might be relative i.e., a node may exhibit maliciousness or selfishness only to a specific set of nodes and may function normally for the rest. In these cases, a complete elimination of the node from the network is unfair. This work mitigates the aforesaid problem and mathematically evaluates the extent of misbehavior of a node through the proposed Metric of Misbehavior (MoM). Based on the Theory of Social Choice, the proposed algorithm considers the misbehaving nodes as the voting alternatives and the normally behaving nodes as the voters. Based on majority ranking of social choice, eventually MoM is obtained for every alternative in a fair manner.

Read full paper

Priority-Based Time-Slot Allocation in Wireless Body Area Networks During Medical Emergency Situations: An Evolutionary Game-Theoretic Perspective

Subhadeep Sarkar, Sudip Misra
J-3 IEEE Journal of Biomedical and Health Informatics, Volume 19, Issue 2, March 2015

Abstract

In critical medical emergency situations, wireless body area network (WBAN) equipped health monitoring systems treat data packets with critical information regarding patients' health in the same way as data packets bearing regular healthcare information. This snag results in a higher average waiting time for the local data processing units (LDPUs) transmitting data packets of higher importance. In this paper, we formulate an algorithm for Priority-based Allocation of Time Slots (PATS) that considers a fitness parameter characterizing the criticality of health data that a packet carries, energy consumption rate for a transmitting LDPU, and other crucial LDPU properties. Based on this fitness parameter, we design the constant model hawk-dove game that ensures prioritizing the LDPUs based on crucial properties. In comparison with the existing works on priority-based wireless transmission, we measure and take into consideration the urgency, seriousness, and criticality associated with an LDPU and, thus, allocate transmission time slots proportionately. We show that the number of transmitting LDPUs in medical emergency situations can be reduced by 25.97%, in comparison with the existing time-division-based techniques.

Read full paper

Evacuation and Emergency Management Using a Federated Cloud

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra
J-2 IEEE Cloud Computing, Volume 1, Issue 4, March 2015

Abstract

Contemporary disaster relief techniques fall significantly short in terms of efficiency and timeliness. In a postdisaster scenario, the generation and transmission of voluminous data at a high velocity impacts the communication framework. This work exploits the benefits of opportunistic communication and efficient big data management policies, focusing on the collaboration of multiple private and/or public clouds of diverse nature to perform damage assessment and determine the spatial distribution of the live victims and their physical and mental status. Based on the analytics, real-time decision making of the rescue operation is achieved.

Read full paper

Energy-Efficient Data Transmission in Sensor-Cloud

Subarna Chatterjee, Subhadeep Sarkar, Sudip Misra
C-2 International Conference on Applications and Innovations in Mobile Computing (AIMoC), Kolkata, India, February 2015

Abstract

Sensor-cloud has been perceived as a potential paradigm for executing wireless sensor based applications. In sensor-cloud, the underlying sensor network is highly heterogeneous in terms of the hardware, sensing and communication ability, and other configuration issues. Thus, the transmission from the underlying networks to the cloud is challenging and induces research interest. The underlying physical sensor nodes for a virtual sensor network (VSN) that transmit the data through a set of intermediate nodes, namely, the bridge nodes to the cloud. This work focuses on obtaining an optimal decision rule to select a bridge node on behalf of a VSN. The work achieves the reduce energy consumption of every node which, in turn, improves the energy expenditure of the entire VSN.

Read full paper

Performance Analysis of IEEE 802.15.6 MAC Protocol under Non-Ideal Channel Conditions and Saturated Traffic Regime

Subhadeep Sarkar, Sudip Misra, Bitan Banerjee, Chandan Chakraborty, Mohammad S. Obaidat
J-1 IEEE Transactions on Computers, Volume 64, Issue 10, January 2015

Abstract

Recently, the IEEE 802.15.6 Task Group introduced a new wireless communication standard that provides a suitable framework specifically to support the requirements of wireless body area networks (WBANs). The standardization dictates the physical (PHY) layer and medium access control (MAC) layer protocols for WBAN-based communications. Unlike the pre-existing wireless communication standards, IEEE 802.15.6 standardization supports short-range, extremely low power wireless communication with high quality of service and support for high data rates upto 10 Mbps in the vicinity of living tissues. In this work, we construct a discrete-time Markov chain (DTMC) that efficiently depicts the states of an IEEE 802.15.6 CSMA/CA-based WBAN. Following this, we put forward a thorough analysis of the standard in terms of reliability, throughput, average delay, and power consumption. The work concerns non-ideal channel characteristics and a saturated network traffic regime. The major shortcoming of the existing literature on Markov chain-based analysis of IEEE 802.15.6 is that the authors did not take into consideration the time spent by a node awaiting the acknowledgement frame after transmission of a packet, until time-out occurs. Also, most of the work assume that ideal channel characteristics persist for the network which is hardly the case in practice. This work remains distinctive as we take into account the waiting time of a node after it transmits a packet while constructing the DTMC. Based on the DTMC, we perform a user priority (UP)-wise analysis, and justify the importance of the standard from a medical perspective.

Read full paper

Analysis of reliability and throughput under saturation condition of IEEE 802.15.6 CSMA/CA for wireless body area networks

Subhadeep Sarkar, Sudip Misra, Bitan Banerjee, Chandan Chakraborty, Mohammad S. Obaidat
C-1 IEEE GLOBECOM, Austin, TX, USA, December 2014

Abstract

The standardization of the IEEE 802.15.6 protocol for wireless body area networks (WBANs) dictates the physical layer and medium access control layer standards from the communication perspective. The standard supports short-range, extremely low power wireless communication with high quality of service and data rates upto 10 Mbps in the vicinity of any living tissue. In this paper, we develop a discrete-time Markov model for the accurate analysis of reliability and throughput of an IEEE 802.15.6 CSMA/CA-based WBAN under saturation condition. Existing literature on Markov chain-based analysis of IEEE 802.15.6, however, do not take into consideration the time a node spends waiting for the immediate acknowledgement frame after transmission of a packet, until time-out occurs. In this work, we take into consideration the waiting time for a node after its transmission, and accordingly modified the structure of the discrete-time Markov chain (DTMC). We also show that as the payload length increases, the reliability of a node decreases; whereas its throughput sharply increases.

Read full paper