Massive data streams from IoT and cyber-physical systems must be processed under strict bandwidth, latency, and resource constraints. Generalized Deduplication (GD) is a promising lossless compression framework, as it supports random access and direct analytics on compressed data. However, existing GD algorithms exhibit quadratic complexity $\mathcal{O}(nd^{2})$, which limits their scalability for high-dimensional datasets. This paper proposes \textbf{EntroGD}, an entropy-guided GD framework that decouples analytical fidelity from compression efficiency to achieve linear complexity $\mathcal{O}(nd)$. EntroGD adopts a two-stage design, first constructing compact condensed samples to preserve information critical for analytics, and then applying entropy-based bit selection to maximize compression. Experiments on 18 IoT datasets show that EntroGD reduces configuration time by up to $53.5\times$ compared to state-of-the-art GD compressors. Moreover, by enabling analytics with access to only $2.6\%$ of the original data volume, EntroGD accelerates clustering by up to $31.6\times$ with negligible loss in accuracy. Overall, EntroGD provides a scalable and system-efficient solution for direct analytics on compressed IoT data.

Sensors provide a critical link between digital and physical systems in the Internet of Things (IoT). However, as they age, their accuracy degrades due to drift. This reduces data trustworthiness and requires significant maintenance investment to mitigate, especially in large-scale sensor deployments typical of IoT systems. Previous approaches to drift correction typically require large volumes of ground truth data and do not consider measurement or prediction uncertainty. In this paper, we propose a probabilistic sensor drift correction method that takes a fundamental approach to modelling the sensor response using Gaussian Process Regression. Tested using dissolved oxygen sensors, our method delivers mean squared error (MSE) reductions of up to 90% and more than 20% on average. We also propose a novel uncertainty-driven calibration schedule optimisation approach that builds on top of drift correction and further reduces MSE by up to 15.7%.

We propose a novel event-trigger threshold (ETT) regulation mechanismETTρbased on Signal Temporal Logic (STL) properties significantly extending recent work on ETT regulation for Propositional Logic properties. We utilize the quantitative semantics of STL to construct a method for computing and merging suitable ETTs for different requirements in complex STL specifications. Contrary to related work on event-triggered control for STL properties, we apply the event-triggering logic to the measured signals individually rather than the control output and assume that an existing periodic controller is defined. By exploiting the early satisfaction detection capabilities of STL and analyzing the property structure, our method aims to reduce the number of triggered events, while maintaining satisfaction of system properties. To evaluateETTρ, we consider a simulated adaptive cruise control case-study where STL is used to encode complex safety and performance properties and the ETTs of measured signals are regulated accordingly. We test three different properties in two different scenarios to showcase how STL andETTρcan identify intricate circumstances where it is possible to significantly reduce the number of triggered events relative to a constant ETT.

We introduce a novel event-trigger threshold (ETT) regulation mechanism based on the quantitative semantics of propositional logic (PL). We exploit the expressiveness of the PL vocabulary to deliver a precise and flexible specification of ETT regulation based on system requirements and properties. Additionally, we present a modified ETT regulation mechanism that provides formal guarantees for satisfaction/violation detection of arbitrary PL properties. To validate our proposed method, we consider a convoy of vehicles in an adaptive cruise control scenario. In this scenario, the PL operators are used to encode safety properties and the ETTs are regulated accordingly, e.g., if our safety metric is high there can be a higher ETT threshold, while a smaller threshold is used when the system is approaching unsafe conditions. Under ideal ETT regulation conditions in this safety scenario, we show that reductions between 41.8% and 96.3% in the number of triggered events is possible compared to using a constant ETT while maintaining similar safety conditions.

Local differential privacy techniques for numerical data typically transform a dataset to ensure a bound on the likelihood that, given a query, a malicious user could infer information on the original samples. Queries are often solely based on users and their requirements, limiting the design of the perturbation to processes that, while privatizing the results, do not jeopardize their usefulness. In this paper, we propose a privatization technique called Zeal, where perturbator and aggregator are designed as a unit, resulting in a locally differentially private mechanism that, by-design, improves the compressibility of the perturbed dataset compared to the original, saves on transmitted bits for data collection and protects against a privacy vulnerability due to floating point arithmetic that affects other state-of-the-art schemes. We prove that the utility error on querying the average and median is invariant to the bias introduced by Zeal in a wide range of conditions, and that under the same circumstances, Zeal also guarantees protection against the aforementioned vulnerability. Moreover, we show that in many scenarios Zeal can outperform other privatization techniques in terms of utility error, compression and data transmission efficiency. Our experiments show up to 94 % improvements in compression and up to 95 % more efficient data transmissions with respect to the original.

IoT applications often require devices to continuously send huge amounts of sensor data to the cloud in order to detect anomalies. This paper proposes a novel preprocessing stage selecting small portions of the sensor data worth sending for further analysis, resulting in significant savings in transmission costs and processing time in the cloud, down to less than 1% of the complete stream, while achieving comparable detection results.

The EU-funded EMPYREAN project (empyrean-horizon.eu) aims to establish a hyper-distributed computing paradigm, leveraging collaborative, heterogeneous IoT devices and federated resources. EMPYREAN focuses on developing technologies for efficient AI workload processing, secure distributed edge storage and cloud-native application development. It will offer open and standardised APIs and use open-source platforms. EMPYREAN's capabilities will be demonstrated through three use cases: advanced manufacturing, smart agriculture, and warehouse automation.

We introduce RAGE, an image compression framework that achieves four generally conflicting objectives: 1) good compression for a wide variety of color images, 2) computationally efficient, fast decompression, 3) fast random access of images with pixel-level granularity without the need to decompress the entire image, 4) support for both lossless and lossy compression. To achieve these, we rely on the recent concept of generalized deduplication (GD), which is known to provide efficient lossless (de)compression and fast random access in time-series data, and deliver key expansions suitable for image compression, both lossless and lossy. Using nine different datasets, incl. graphics, logos, natural images, we show that RAGE has similar or better compression ratios to state-of-the-art lossless image compressors, while delivering pixel-level random access capabilities. Tests in an ARM Cortex-M33 platform show seek times between 9.9 and 40.6 ns and average decoding time per pixel between 274 and 1226 ns. Our measurements also show that RAGE’s lossy variant, RAGE-Q, outperforms JPEG by several fold in terms of distortion in embedded graphics and has reasonable compression and distortion for natural images.

Exponential growth in data collection is creating significant challenges for data storage and analytics latency. Approximate Query Processing (AQP) has long been touted as a solution for accelerating analytics on large datasets, however, there is still room for improvement across all key performance criteria. In this paper, we propose a novel histogram-based data synopsis called PairwiseHist that uses recursive hypothesis testing to ensure accurate histograms and can be built on top of data compressed using Generalized Deduplication (GD). We thus show that GD data compression can contribute to AQP. Compared to state-of-the-art AQP approaches, Pairwise-Hist achieves better performance across all key metrics, including 2.6× higher accuracy, 3.5× lower latency, 24× smaller synopses and 1.5--4× faster construction time.

The exponential growth of data generated by the Internet of Things presents significant challenges for data communication, storage, and analytics. Consequently, organizations often face high costs when attempting to leverage their own data. Novel techniques that holistically optimize data storage and analytics in IoT systems are therefore required. One promising approach is generalized deduplication (GD), which is a lossless compression technique that delivers high compression while also enabling low-cost random access directly on compressed data. In this article, we introduce GreedyGD, a novel GD data compression algorithm that offers reliable, efficient data analytics, along with more compression and faster runtime compared to previous GD compressors. Evaluating GreedyGD on 18 real-world datasets revealed excellent performance: a 11.2× speed-up, 1.6× more compression, and more accurate and reliable analytics while using 4× less data compared to previous GD compressors.

Local differential privacy techniques for numerical data typically transform a dataset to ensure a bound on the likelihood that, given a query, a malicious user could infer information on the original samples. Queries are often solely based on users and their requirements, limiting the design of the perturbation to processes that, while privatizing the results, do not jeopardize their usefulness. In this paper, we propose a privatization technique called Zeal, where perturbator and aggregator are designed as a unit, resulting in a locally differentially private mechanism that, by-design, improves the compressibility of the perturbed dataset compared to the original, saves on transmitted bits for data collection and protects against a privacy vulnerabilities due to floating point arithmetic that affect other state-of-the-art schemes. We prove that the utility error on querying the average is invariant to the bias introduced by Zeal in a wide range of conditions, and that under the same circumstances, Zeal also guarantee protection against the aforementioned vulnerability. Our numerical results show up to 94 % improvements in compression and up to 95 % more efficient data transmissions, while keeping utility errors within 2 %.

The number of IoT devices is expected to continue its dramatic growth in the coming years and, with it, a growth in the amount of data to be transmitted, processed and stored. Compression techniques that support analytics directly on the compressed data could pave the way for systems to scale efficiently to these growing demands. This paper proposes two novel methods for preprocessing a stream of floating point data to improve the compression capabilities of various IoT data compressors. In particular, these techniques are shown to be helpful with recent compressors that allow for random access and analytics while maintaining good compression. Our techniques improve compression with reductions up to 80% when allowing for at most 1% of recovery error.

With the increasing amount of digital data, data deduplication has become an increasingly popular method for reducing data in large-scale storage systems. Generalized deduplication is an alternative technique for reducing the cost of data storage by identifying similar data chunks. This paper proposes TL-GD, a method for improving cloud storage efficiency using generalized deduplication focusing on textual datasets. The core concept of this study is to develop an efficient deduplication system that combines an alternative technique for splitting data into smaller pieces and a new approach for transforming data pieces into bases and deviations. The performance of the system has been validated using two real-world datasets. We also compare the results to state-of-the-art deduplication methods. Our evaluation results show that TL-GD achieves nearly 67% lossless compression for textual navigation instructions datasets, which is a 25% improvement on average compared to existing deduplication techniques.

The Internet of Things (IoT) has brought about exponential growth in sensor data. This has led to increasing demands for efficient and novel data transmission, storage, and analytics solutions for sustainable IoT ecosystems. It has been shown that the generalized deduplication (GD) compression algorithm offers not only competitive compression ratio and throughput but also random access properties that enable direct analytics of compressed data. In this article, we thoroughly stress test existing methods for direct analytics of GD compressed data with a diverse collection of 103 data sets, identify the need to optimize GD for analytics, and develop a new version of GD to this end. We also propose the generalized deduplication-enabled approximate edge analytics (GLEAN) framework. This framework applies the aforementioned analytics techniques at the Edge server to deliver end-to-end lossless data compression and high-quality Edge analytics in the IoT, thereby addressing challenges related to data transmission, storage, and analytics. Impressive analytics performance was achieved using this framework, with a median increase in$k$-means clustering error of just 2% relative to analytics performed on uncompressed data, while running$7.5\times $faster and requiring$3.9\times $less storage at the Edge server compared to universal compressors.

Distributed storage systems spanning across different cloud data centers have substantially improved availability and flexibility for data storage and retrieval operations. However, stringent latency requirements of emerging applications necessitate optimized selection of storage resources that exhibit smaller delay. Introducing edge resources into distributed storage systems enables data placement closer to its source, but simultaneously increases the complexity of decision-making and orchestration processes for optimal data placement. In this work, we develop mechanisms for storing data across an infrastructure that includes both edge and cloud resources. Our approach focuses on optimizing data integrity, longevity, security, and cost, while leveraging erasure coding when performing the resource allocation. We first present a comprehensive mixed integer linear programming formulation of the storage resource orchestration problem. As the search space for the optimal solution can be vast and the execution time prohibitively large for real size problems, we also propose an innovative multi-agent heuristic approach that uses the rollout, a reinforcement based policy, to balance performance and execution time efficiently. Through various simulation experiments, we evaluate the developed mechanisms and trade-offs involved in our approach. By incorporating data from a multi-cloud provider, we further enhance the validity of the simulations and the conclusions drawn.

This work proposes a novel design for secure cloud storage systems using a third party to meet three seemingly opposing demands: reduce storage requirements on the cloud, protect against erasures (data loss), and maintain confidentiality of the data. More specifically, we achieve storage cost reductions using data deduplication without requiring system users to trust that the cloud operates honestly. We analyze the security of our scheme against honest-but-curious and covert adversaries that may collude with multiple parties and show that no novel sensitive information can be inferred, assuming random oracles and a high min-entropy data source. We also provide a mathematical analysis to characterize its potential for compression given the popularity of individual chunks of data and its overall erasure protection capabilities. In fact, we show that the storage cost of our scheme for a chunk with r replicas is O(log(r)/r), while deduplication without security or reliability considerations is O(1/r), i.e., our added cost for providing reliability and security is only O(log(r)). We provide a proof of concept implementation to simulate performance and verify our analytical results.

Emerging Edge Computing (EC) technology has shown promise for many delay-sensitive Deep Learning (DL) based applications of smart cities in terms of improved Quality-of-Service (QoS). EC requires judicious decisions which jointly consider the limited capacity of the edge servers and provided QoS of DL-dependent services. In a smart city environment, tasks may have varying priorities in terms of when and how to serve them; thus, priorities of the tasks have to be considered when making resource management decisions. In this paper, we focus on finding optimal offloading decisions in a three-tier user-edge-cloud architecture while considering different priority classes for the DL-based services and making a trade-off between a task’s completion time and the provided accuracy by the DL-based service. We cast the optimization problem as an Integer Linear Program (ILP) where the objective is to maximize a function called gain of system (GoS) defined based on provided QoS and priority of the tasks. We prove the problem is NP-hard. We then propose an efficient offloading algorithm, called PGUS, that is shown to achieve near-optimal results in terms of the provided GoS. Finally, we compare our proposed algorithm, PGUS, with heuristics and a state-of-the-art algorithm, called GUS, using both numerical analysis and real-world implementation. Our results show that PGUS outperforms GUS by a factor of 45% in average in terms of serving the top 25% higher priority classes of the tasks while still keeping the overall percentage of the dropped tasks minimal and the overall gain of system maximized.

Smart electricity meters typically upload power consumption readings once or few times a day. Utility providers aim to increase the upload frequency in order to access consumption information in near real time, but the currently used data compressors fail to provide sufficient savings in this new scenario on the low-bandwidth, high-cost data connection. We propose a new compression method and data format for DLMS smart meter readings, which is significantly better with frequent uploads and makes it feasible to report every reading in near real time with the same or lower data sizes than the currently available compressors in the DLMS protocol.

Due to power limitations and coexistence in ISM bands, up to 50% of the Long Range (LoRa)-frames are corrupted at low signal strengths (≈ -115dBm) and the built-in redundancy schemes in LoRa-Wide Area Network (LoRaWAN) cannot correct the corrupted bytes. To address this, higher Spreading Factors (SF) are used resulting in wasted energy, increased traffic load, and highly compromised effective data rate. Our on-field experiments showed a high correlation in the corruption of close-by frames. We propose a novel Divide & Code (DC) scheme for LoRaWANs as an alternative to using higher SF. DC pre-encodes LoRa payloads using lightweight and memoryless encoding. After receiving a corrupted frame, DC uses a combination of most probable patterns of errors, Time Thresholds (TT), and splitting of payloads into subgroups for batch processing to recover frames effectively and maintain low complexity and timely operation. By implementing DC on our LoRa-testbed, we show it outperforms vanilla-LoRaWAN and Reed-Solomon codes in decoding and energy consumption. Our schemes decode up to 80.5% of corrupted payloads on SF10 by trying only 0.03% of all patterns of error combinations. TT keeps processing times below 2 ms with only minor reductions in the decoding ratio of corrupted payloads. Finally, we showcase that introducing 30% redundancy with DC results in minimum energy consumption and high decoding ratio at low SNRs.

Given the ever increasing volume of data generated by the Internet of Things, data compression plays an essential role in reducing the cost of data transmission and storage. However, it also introduces a barrier, namely decompression, between users and the data-driven insights they require. We propose methods for direct analytics of compressed data based on the Generalized Deduplication compression algorithm. When applied to data clustering, the accuracy of the best performing method differs by merely 1-5% when compared to analytics performed upon the uncompressed data. However, it runs four times faster, accesses only 14% as much data and requires significantly less storage since the data is always compressed. These results show that it is possible to simultaneously reap the benefits of compression and accurate, high-speed analytics in many applications.

High frame-corruption is widely observed in Long Range Wide Area Networks (LoRaWAN) due to the coexistence with other networks in ISM bands and an Aloha-like MAC layer. LoRa's Forward Error Correction (FEC) mechanism is often insufficient to retrieve corrupted data. In fact, real-life measurements show that at least one-fourth of received transmissions are corrupted. When more frames are dropped, LoRa nodes usually switch over to higher spreading factors (SF), thus increasing transmission times and increasing the required energy. This paper introduces ReDCoS, a novel coding technique at the application layer that improves recovery of corrupted LoRa frames, thus reducing the overall transmission time and energy invested by LoRa nodes by several-fold. ReDCoS utilizes lightweight coding techniques to pre-encode the transmitted data. Therefore, the inbuilt Cyclic Redundancy Check (CRC) that follows is computed based on an already encoded data. At the receiver, we use both the CRC and the coded data to recover data from a corrupted frame beyond the built-in Error Correcting Code (ECC). We compare the performance of ReDCoS to (i) the standard FEC of vanilla-LoRaWAN, and to (ii) Reed Solomon (RS) coding applied as ECC to the data of LoRaWAN. The results indicated a 54x and 13.5x improvement of decoding ratio, respectively, when 20 data symbols were sent. Furthermore, we evaluated ReDCoS on-field using LoRa SX1261 transceivers showing that it outperformed RS-coding by factor of at least 2x (and up to 6x) in terms of the decoding ratio while consuming 38.5% less energy per correctly received transmission.

With the increasing demand for computationally intensive services like deep learning tasks, emerging distributed computing platforms such as edge computing (EC) systems are becoming more popular. Edge computing systems have shown promising results in terms of latency reduction compared to the traditional cloud systems. However, their limited processing capacity imposes a trade-off between the potential latency reduction and the achieved accuracy in computationally-intensive services such as deep learning-based services. In this paper, we focus on finding the optimal accuracy-time trade-off for running deep learning services in a three-tier EC platform where several deep learning models with different accuracy levels are available. Specifically, we cast the problem as an Integer Linear Program, where optimal task scheduling decisions are made to maximize overall user satisfaction in terms of accuracy-time trade-off. We prove that our problem is NP-hard and then provide a polynomial constant-time greedy algorithm, called GUS, that is shown to attain near-optimal results. Finally, upon vetting our algorithmic solution through numerical experiments and comparison with a set of heuristics, we deploy it on a testbed implemented to measure for real-world results. The results of both numerical analysis and real-world implementation show that GUS can outperform the baseline heuristics in terms of the average percentage of satisfied users by a factor of at least 50%.

This paper proposes Yggdrasil, a protocol for privacy-aware dual data deduplication in multi-client settings. Yggdrasil is designed to reduce cloud storage space while safeguarding the privacy of clients’ data. This is achieved by exploiting a ‘dual’ setting, where both the cloud and the clients store a fraction of the data. Yggdrasil combines two innovative techniques to achieve this goal. First, generalized deduplication, an emerging solution to reduce data footprint; second, non- deterministic lightweight transformations that ensure a high level of privacy while improving the degree of cross-user data compression in the cloud. Our client preprocessing guarantees that an honest-but-curious cloud storage provider faces a high degree of uncertainty in determining the original clients’ data. We introduce an uncertainty metric to measure the privacy of the client’s outsourced data and three compression metrics to investigate the performance of Yggdrasil. Our experiments with a dataset of DVI files show that Yggdrasil achieves an overall compression rate of 43%, which means that Yggdrasil can represent the same database using less than half of the original space. Moreover, for the same experiment clients only store 17% of the original data, the cloud hosts the remaining 26%, and the client preprocessing ensures each outsourced fragment has 10293possible original strings. Higher uncertainty is possible, but reduces the cloud’s compression capability.

This paper considers benefits of coding techniques in recommendation systems operating over wireless channels with erasures. We identify scenarios where coded broadcasting can increase the overall user satisfaction at a fixed channel utilization level. Such opportunities arise both when user preferences are unknown, and must be explored, and when they are known and must be exploited to recommend optimally. We determine the magnitude of the potential gains and show that coding is most beneficial if users have heterogeneous preferences. Finally, we provide inequalities that can be evaluated to determine whether coding would be beneficial for a certain reward structure.

Mobile edge computing pushes computationally-intensive services closer to the user to provide reduced delay due to physical proximity. This has led many to consider deploying deep learning models on the edge – commonly known as edge intelligence (EI). EI services can have many model implementations that provide different QoS. For instance, one model can perform inference faster than another (thus reducing latency) while achieving less accuracy when evaluated. In this paper, we study joint service placement and model scheduling of EI services with the goal to maximize Quality-of-Servcice (QoS) for end users where EI services have multiple implementations to serve user requests, each with varying costs and QoS benefits. We cast the problem as an integer linear program and prove that it is NP-hard. We then prove the objective is equivalent to maximizing a monotone increasing, submodular set function and thus can be solved greedily while maintaining a (1 – 1/e)-approximation guarantee. We then propose two greedy algorithms: one that theoretically guarantees this approximation and another that empirically matches its performance with greater efficiency. Finally, we thoroughly evaluate the proposed algorithm for making placement and scheduling decisions in both synthetic and real-world scenarios against the optimal solution and some baselines. In the real-world case, we consider real machine learning models using the ImageNet 2012 data-set for requests. Our numerical experiments empirically show that our more efficient greedy algorithm is able to approximate the optimal solution with a 0.904 approximation on average, while the next closest baseline achieves a 0.607 approximation on average.

Long Range Wide Area Networks (LoRaWAN) offer ubiquitous communications for The Internet of Things (IoT). However, there are many challenges in rolling out LoRaWAN - mainly scalability, energy efficiency, Packet Reception Ratio (PRR), and keeping the channel access as simple as unslotted ALOHA. To this end, we design non-persistent Capture Effect Channel Activity Detection Algorithm (np-CECADA), which is a novel, distributed protocol for the MAC layer of LoRaWAN. It utilizes Channel Activity Detection (CAD), which is a built-in imperfect mechanism for channel sensing and minimal feedback from the gateways. In np-CECADA each device independently adapts backoff times based on the traffic in its vicinity and the transmission power based on the heuristically inferred probability of capturing the channel. To achieve this, first, we carried out an extensive on-field evaluation to measure the effectiveness of CAD and capture effect in LoRa. Using them we designed np CECADA and developed $ns-3$ modules. Packet Reception Ratio of np-CECADA is $ 15.74\times$ and $ 5.13\times$ higher than vanilla LoRaWAN and p-CARMA, respectively. Channel utilization is $ 11.24\times$ higher compared to LMAC. Further, on a testbed of 30 LoRa devices np-CECADA outperforms LoRaWAN up to 5 times.

Deduplication exploits the presence of similar data chunks to reduce storage overhead. Generalised deduplication (GD) uses transformation functions to split data into a basis (common to millions of chunks) and a deviation with respect to the basis. Doing so, it avoids computing additional hashes, comparing or differentiating against previously stored chunks. Minervafs is the first FUSE-based file system for GD. We implement and evaluate it using several real-world datasets, e.g., satellite images and virtual machine images, comparing against classical deduplication approaches (ZFS, SDFS), delta compression (xdelta) or compression (Gzip). Compared to ZFS, Minervafs achieves up to 63.53% (average of 27.38%) saving in storage usage and a speedup of 16% in read-heavy workloads. For VM images, MINERVAFS's data compression is on par with Gzip, while outperforming ZFS by severalfold. In contrast to ZFS’ growing RAM costs when more data is stored, MinervaFS’ RAM usage is independent from the amount of data stored, making it well suited to handle growing storage demands.

Peer-to-peer distributed storage systems can be instrumental to develop solutions able to store the massive amounts of data generated by the Internet of Things (IoT) users. Given the higher probability of node failures, losses in the communication channels, and limited resources of devices compared to centralized storage solutions, it is key to minimize data retrieval time, while also maintaining high resiliency in the system. We propose a method based on random linear network coding (RLNC) for data storage and retrieval and the use of Kademlia for our peer-to-peer design to address these challenges. We analyze the performance of the proposed RLNC-based method theoretically as well as the traditional Kademlia in terms of data retrieval time and resiliency to node failures and channel losses. We use PeerSim to simulate the proposed method. Our theoretical analysis and simulation results show that the proposed RLNC-based method significantly outperforms traditional Kademlia for our core performance metrics. These gains in resiliency and data retrieval time are achieved while also reducing the data storage time for a wide region of operation. Our simulations show that only if the redundancy of the RLNC-based scheme is significantly increased (> 100 % redundant RLNC packets), then a small degradation (<; 10 %) in data storage time occurs.

We introduce Titchy, which is a compression method for time-series data generated by the Internet of Things. Our proposed method is flexible and has several advantages when applied in the IoT ecosystem: 1) it is able to compress even when only a small amount of memory can be allocated to it; 2) it compresses data in tiny chunks, so it introduces very little latency during online operation and thus, enables frequent and timely updates with compressed data; and 3) it facilitates efficient data storage and retrieval by enabling low-cost random access to the compressed data, eliminating the need to decompress large chunks when only a small amount of data is requested. To evaluate each of these advantages, we have implemented the compressor and conducted extensive experiments with long-term real-world data captured over days or weeks. We also present results for seven state-of-the-art compression methods to act as a baseline. Our evaluation shows that Titchy not only outperforms all seven on random access capability and for frequent transmissions but also provides great compression ratios as well as high compression and decompression speeds.

Timely delivery of sensor data is crucial for a wide array of Internet-of-Things (IoT) applications. Due to the large space and time correlation of sensor data, there is a high potential for compression. However, conventional wisdom dictates that compression is at odds with information freshness and timely delivery of data. The reason is that sufficient data needs to be accumulated in order to achieve reasonable compression rates, which introduces additional delays on data transmission. This article studies a novel approach to perform online compression of data across multiple data sources which achieves significantly better performance in both Age of Information (AoI) and compression for sensor applications. More specifically, we show that our approach can remove the tradeoff between these two metrics, particularly, when considering an instantly decodable variant of our approach. We also propose and study techniques to further improve both these metrics by using preset and dynamically created dictionaries at the source nodes. Using real-world data sets, we show that our solution reduces the AoI (by up to a factor of 2.3) and compression ratio (by up to an order of magnitude) with respect to DEFLATE and LZW. Finally, we show that using multiple sources benefits results in an improvement of AoI and compression for each involved source compared to compressing individually.

Network appliances continue to offer novel opportunities to offload processing from computing nodes directly into the data plane. One popular concern of network operators and their customers is to move data increasingly faster. A common technique to increase data throughput is to compress it before its transmission. However, this requires compression of the data---a time and energy demanding preprocessing phase---and decompression upon reception---a similarly resource consuming operation. Moreover, if multiple nodes transfer similar data chunks across the network hop (e.g., a given pair of switches), each node effectively wastes resources by executing similar steps. This paper proposes ZipLine, an approach to design and implement (de)compression at line speed leveraging the Tofino hardware platform which is programmable using the P416 language. We report on lessons learned while building the system and show throughput, latency and compression measurements on synthetic and real-world traces, showcasing the benefits and trade-offs of our design.

Utility providers are relying more often on smart, wirelessly connected smart meters to collect consumption information of their customers. The sheer amount of connected smart meters and the growing requirements to provide more frequent reports from each device are putting a large strain on existing systems and protocols. In this paper, we propose three novel lossless compression schemes that significantly reduce the size of standard DLMS data messages uploaded by smart electricity meters. Using real life data sets, we show that these methods can achieve compression rates of over 90% while being transparent to the DLMS protocol.

In cloud storage systems, malicious users may exploit client-side deduplication responses to infer what other users are storing in the cloud. We propose CIDER, a low overhead approach to mitigate this side channel by obfuscating the existence status of data stored in the cloud. We analyze the scheme's ability to obfuscate the side-channel and discuss attacks that a user may still employ and what he could learn from such attacks. Finally, we use simulated and real data to examine the performance under realistic deduplication workloads, revealing that CIDER ends up transmitting less redundant information than similar methods, thus enabling a more efficient utilization of the available bandwidth.

Vehicles generate a large amount of data from their internal sensors. This data is not only useful for a vehicle's proper operation, but it provides car manufacturers with the ability to optimize the performance of individual vehicles and companies with fleets of vehicles (e.g., trucks, taxis, tractors) to optimize their operations to reduce fuel costs and plan repairs. This paper proposes algorithms to compress CAN bus data, specifically, packaged as MDF4 files. In particular, we propose lightweight, online and configurable compression algorithms that allow limited devices to choose the amount of RAM and flash memory allocated to them. We show that our proposals can outperform LZW for the same RAM footprint, and can even deliver comparable or better performance to DEFLATE under the same RAM limitations.

Generalized deduplication (GD) has been proposed as a new approach for reducing the cost of storage. Recent work has adapted this technique to provide distributed, multisource lossless compression to reduce the total number of bits transmitted in sensor networks. In this paper, we characterize its performance and advantages from an age of information perspective. For simplicity, we analyze the case of one source node receiving one symbol/sample per unit time and transmitting bits to the sink node. We show the potential for GD to also deliver instant decoding of the data to further reduce the average age of information. Using real-world data sets, our solution reduces the information age by 25% and 36% when considering the standard and the instantly decodable versions, respectively compared to the use of the DEFLATE algorithm for compression.

We detail a practical compression scheme for lossless compression of time-series data, based on the emerging concept of generalized deduplication. As data is no longer stored for just archival purposes, but needs to be continuously accessed in many applications, the scheme is designed for low-cost random access to its compressed data, avoiding decompression. With this method, an arbitrary bit of the original data can be read by accessing only a few hundred bits in the worst case, several orders of magnitude fewer than state-of-the-art compression schemes. Subsequent retrieval of bits requires visiting at most a few tens of bits. A comprehensive evaluation of the compressor on eight real-life data sets from various domains is provided. The cost of this random access capability is a loss in compression ratio compared with the state-of-the-art compression schemes BZIP2 and 7z, which can be as low as 5% depending on the data set. Compared to GZIP, the proposed scheme has a better compression ratio for most of the data sets. Our method has massive potential for applications requiring frequent random accesses, as the only existing approach with comparable random access cost is to store the data without compression.

The massive increase and assimilation of Internet of Things (IoT) devices and services imposes new challenges in sensing, communication, and reliable storage of data generated by the IoT. We focus on scenarios where the IoT devices may lose connectivity for long periods of time and can only rely on other IoT devices to store data reliably. This constitutes a problem of distributed storage where lost devices cannot be replaced by others in the network due to the fact that there are no additional devices arriving to the system and that each device has a limited storage capability. Thus, state-of-the-art approaches for distributed storage in data centers are not applicable. We show that optimal policies for data repair, in terms of bandwidth and storage usage, for this novel scenario can be implemented efficiently in real-devices using network coding. We provide a translation from the theoretical results in [1] into an implementation using Raspberry Pi devices.

This paper proposes a low-complexity solution for the data protection problem without newcomer nodes in Internet of Things (IoT) scenarios, i.e., when device losses cannot be replaced by new devices. Application scenarios include environmental monitoring, data collection, and industrial automation. Although the optimal solution and optimization framework have been studied in previous work to minimize the network costs and storage capacity requirements, this paper shows that the optimal solution has a high complexity as the number of devices increases. Given the massive number of IoT devices, we propose a relaxation to the cut capacity constraints that (a) guarantees data recoverability, (b) achieves the minimum network use, and (c) reduces the problem's complexity dramatically. Our numerical results show that the proposed relaxation allows us to change the computational scaling of the problem. More specifically, we show that the time taken to compute the optimal transmission policy with the relaxation for a system with 800 devices is the same as the time it takes the optimal solution to solve the case of 15 devices.

To provide compressed storage for large amounts of time series data, we present a new strategy for data deduplication. Rather than attempting to deduplicate entire data chunks, we employ a generalized approach, where each chunk is split into a part worth deduplicating and a part that must be stored directly. This simple principle enables a greater compression of the often similar, non-identical, chunks of time series data than is the case for classic deduplication, while keeping benefits such as scalability, robustness, and on-the-fly storage, retrieval, and search for chunks. We analyze the method's theoretical performance, and argue that our method can asymptotically approach the entropy limit for some data configurations. To validate the method's practical merits, we finally show that it is competitive when compared to popular universal compression algorithms on the MIT-BIH ECG Compression Test Database.

We study a generalization of deduplication, which enables lossless deduplication of highly similar data and show that classic deduplication with fixed chunk length is a special case. We provide bounds on the expected length of coded sequences for generalized deduplication and show that the coding has asymptotic near-entropy cost under the proposed source model. More importantly, we show that generalized deduplication allows for multiple orders of magnitude faster convergence than classic deduplication. This means that generalized deduplication can provide compression benefits much earlier than classic deduplication, which is key in practical systems. Numerical examples demonstrate our results, showing that our lower bounds are achievable, and illustrating the potential gain of using the generalization over classic deduplication. In fact, we show that even for a simple case of generalized deduplication, the gain in convergence speed is linear with the size of the data chunks.

Next generation use-cases of mesh networks, such as connected vehicles and industrial devices, require low latency transmissions while fulfilling high reliability constraints. However, they also suffer from an increased protocol encapsulation overhead when handling a large number of messages with small payloads. A solution to this problem is to employ header compression algorithms in order to reduce the size of the individual protocol headers. Unfortunately, the current state-of-the-art header compression schemes cannot be readily applied to network topologies that contain a combination of multiple-hops and paths, as the compression only works favourably on a peer-to-peer, single-hop basis. With the unique combination of network coding and header compression one can always utilise unidirectional compression with maximum gain. In this paper we introduce and evaluate, for the first time, an integrated network coded header compression solution, which we call unidirectional Robust Header Compression (uRoHC). We show that one can - proportionally to the logical payload size - double the payload delivery efficiency compared to standard IPv4 and that we achieve results 10-15 % better than that of RoHCv2 for streams containing 33 bytes of payload.

The upcoming wireless network generation has put a large emphasis on the fulfilment of high reliability constraints. Nonetheless, the trade- off between these and other network aspects, mainly delay and bandwidth, is a constant optimisational question and a tough challenge. The various employed protocols add certain encapsulation overheads, which albeit necessary, however could potentially be excessive, such as in the case of various IoT, and similar applications with small payloads. Header compression aims to reduce these headers, but a general problem still plagues the standards since their introduction to loss-prone wireless networks, which is the issue of lost context (re)initialisation packets that can make the compression upstart and the transmission of major changes unreliable, slow and costly. In this paper we propose a solution that circumvents some concerns of traditional header compression context initialisation by the employment of network coding, which we call the reliable base proposal technique. This provides a finely tunable method for balancing reliability and delay of decompression with bandwidth gain. Our results show that both compression gain and reliability can be increased over the previous standards.

Coding techniques that are employed to resolve packet losses on wireless channels, such as Random Linear Network Coding (RLNC), market themselves with the advantage of requiring less signalling, as well as, retransmissions of missing packets to compensate for losses on unreliable links. However, as packet sizes of IP-based protocols can be distributed irregularly over the available maximum frame size and can vary considerably packet-by-packet, the current implementations of RLNC suffer from shifting header and/or payload lengths and lack a suitable way of compensation. The simplest solution adopted by most RLNC approaches is to pad the unequal packets with zeros to the maximum packet size, thus creating an unnecessary transmission overhead of 100 % or more. This paper presents a practical implementation of the new progressive shortening based RLNC for the first time. This scheme utilizes fixed-sized regions inside the packets to resolve the zero-padding overhead and generates unequal-sized coded packets. Furthermore, it introduces a recoding feature for this scheme, which is another advantage of RLNC over other coding techniques, and breaks with the point-to-point topology considered in previous works. Moreover, we combine this novel macro-symbol based coding scheme with Robust Header Compression version 2 (RoHCv2) to show the gain over traditional implementation of RLNC in a real-life application where varying packet lengths dominate during transmissions. Our implementations results, using the KODO network coding library, show that the encoding throughput is as good as the established RLNC methods, and the payload delivery efficiency can be enhanced by up to 20 %.

Although cloud systems provide a reliable and flexible storage solution, the use of a single cloud service constitutes a single point of failure, which can compromise data availability, download speed, and security. To address these challenges, we advocate for the use of multiple cloud storage providers simultaneously using network coding as the key enabling technology. Our goal is to study two challenges of network coded storage systems. First, the efficient update of the number of coded fragments per cloud in a system aggregating multiple clouds in order to boost the download speed of files. We developed a novel scheme using recoding with limited packets to trade-off storage space, reliability, and data retrieval speed. Implementation and measurements with commercial cloud providers show that up to 9x less network use is needed compared to other network coding schemes, while maintaining similar download speeds and reliability. Second, the ability to update coded fragments from a linear erasure code when the original file is modified. We exploit code structure to provide efficient representations of the evolution of the file. Evaluations using file changes on software library repositories show that a five-order of magnitude reduction in network and storage use is possible compared to state-of-the-art.

Although network coding has shown the potential to revolutionize networking and storage, its deployment has faced a number of challenges. Usual proposals involve two approaches. First, deploying a new protocol (e.g., Multipath Coded TCP), or retrofitting another one (e.g., TCP/NC) to deliver benefits to any application in a computer. However, incorporating new protocols to the Internet is a challenging and slow process. Second, deploying coding at the application layer, which forces each application to implement network coding. This paper proposes an alternative approach through the use of a network coded filesystem shim (NCFSS), where coded data is generated at the filesystem level supporting any application and any network protocol. Our design allows multiple sources of a content to serve data without coordination to a receiver over multiple data paths. Another interesting feature of our approach is that it allows caches in the network to store only a fraction of a specific content in coded form, but sharing the same object identification, i.e., it simplifies the signaling and search of coded content. We describe the NCFSS design and implementation using FUSE and carry out measurements using servers in six countries to demonstrate gains of two to five fold in download speed.

The goal of this paper is two-fold. First, to expand an opportunistic network coding protocol for wireless networks, called PlayNCool, in order to incorporate new mechanisms to improve performance in the presence of packet losses. In particular, exploiting additional helper nodes to improve the quality of each link and even across neighbouring links and using simulations to show that an additional reduction of packet transmission in the order of 40% is possible. Second, to advocate for the use of network coding (NC) jointly with software defined networking (SDN) providing an implementation of the expanded PlayNCool protocol using SDN. This implementation uses an architecture developed with OpenFlow switches and a Pox controller to periodically gather statistics related to packet losses and the number of packets coded, recoded and decoded on a per link basis in order to adapt the configuration for the PlayNCool protocol optimally. The measurements carried out were validated with theoretical and simulated results.

Despite their high computational complexity, Random Linear Network Coding (RLNC) techniques have been shown to offer a good robustness against packet erasure wireless channels. Some approaches have been recently proposed to reduce such computational burden, for both encoder and decoder elements. One of those approaches are the so- called Tunable Sparse Network Coding (TSNC) techniques, which advocate limiting the number of packets that are combined to build a coded packet. They also propose dynamically adapting the corresponding sparsity level, as the transmission evolves, although an optimum tuning policy has not been yet found. In this paper we present a TSNC implementation that exploits a novel analytical model to estimate the probability of generating an innovative packet (linearly independent combination), given the current status at the decoder. Taking advantage of the model's accuracy, the proposed scheme offers a better trade-off between computational complexity and network performance. Furthermore, we broaden the analysis of TSNC techniques by thoroughly assessing their behavior over wireless networks using the ns-3 platform. The results yield a remarkable complexity reduction (approx. 3.33x less complexity), without jeopardizing network performance.

Random linear network coding has been shown to offer an efficient communication scheme, leveraging a remarkable robustness against packet losses. However, it suffers from a high-computational complexity, and some novel approaches, which follow the same idea, have been recently proposed. One of such solutions is sparse network coding (SNC), where only few packets are combined with each transmission. The amount of data packets to be combined can be set from a density parameter/distribution, which could be eventually adapted. In this paper, we present a semi-analytical model that captures the performance of SNC on an accurate way. We exploit an absorbing Markov process, where the states are defined by the number of useful packets received by the decoder, i.e., the decoding matrix rank, and the number of non-zero columns at such matrix. The model is validated by the means of a thorough simulation campaign, and the difference between model and simulation is negligible. We also include in the comparison of some more general bounds that have been recently used, showing that their accuracy is rather poor. The proposed model would enable a more precise assessment of the behavior of SNC techniques.

Random Linear Network Coding (RLNC) has been shown to be a technique with several benefits, in particular when applied over wireless mesh networks, since it provides robustness against packet losses. On the other hand, Tunable Sparse Network Coding (TSNC) is a promising concept, which leverages a trade-off between computational complexity and goodput. An optimal density tuning function has not been found yet, due to the lack of a closed-form expression that links density, performance and computational cost. In addition, it would be difficult to implement, due to the feedback delay. In this work we propose two novel tuning functions with a lower computational cost, which do not highly increase the overhead in terms of the transmission of linear dependent packets compared with RLNC and previous proposals. Furthermore, we also broaden previous studies of TSNC techniques, by means of an extensive simulation campaign carried out using the ns-3 simulator. This brings the possibility of assessing their performance over more realistic scenarios, e.g considering MAC effects and delays. We exploit this implementation to analyze the impact of the feedback sent by the decoder. The results, compared to RLNC, show a reduction of 3.5 times in the number of operations without jeopardizing the network performance, in terms of goodput, even when we consider the delay effect on the feedback sent by the decoder.

Although random linear network coding (RLNC) constitutes a highly efficient and distributed approach to enhance communication networks and distributed storage, it requires additional processing to be carried out in the network and in end devices. For mobile devices, this processing translates into energy use that may reduce the battery life of a device. This paper focuses not only on providing a comprehensive measurement study of the energy cost of RLNC in eight different computing platforms, but also explores novel approaches (e.g., tunable sparse network coding) and hardware optimizations for Single Instruction Multiple Data (SIMD) available in the latest generations of Intel and Advanced RISC Machines (ARM) processors. Our measurement results show that the former provides gains of two-to six-fold from the underlying algorithms over RLNC, while the latter provides gains for all schemes from 2× to as high as 20×. Finally, our results show that the latest generation of mobile processors reduce dramatically the energy per bit consumed for carrying out network coding operations compared to previous generations, thus making network coding a viable technology for the upcoming 5G communication systems, even without dedicated hardware.

Point-to-multipoint communications are expected to play a pivotal role in next-generation networks. This paper refers to a cellular system transmitting layered multicast services to a multicast group of users. Reliability of communications is ensured via different random linear network coding (RLNC) techniques. We deal with a fundamental problem: the computational complexity of the RLNC decoder. The higher the number of decoding operations is, the more the user's computational overhead grows and, consequently, the faster the battery of mobile devices drains. By referring to several sparse RLNC techniques, and without any assumption on the implementation of the RLNC decoder in use, we provide an efficient way to characterize the performance of users targeted by ultra-reliable layered multicast services. The proposed modeling allows to efficiently derive the average number of coded packet transmissions needed to recover one or more service layers. We design a convex resource allocation framework that allows to minimize the complexity of the RLNC decoder by jointly optimizing the transmission parameters and the sparsity of the code. The designed optimization framework also ensures service guarantees to predetermined fractions of users. The performance of the proposed optimization framework is then investigated in a LTE-A eMBMS network multicasting H.264/SVC video services.

Although Network Coding (NC) has been proven to increase throughput and reliability in communication networks, its adoption is typically hindered by the additional complexity it introduces at various nodes in the network and the overhead to signal the coding coefficients associated with each coded packet. This work advocates the use of multiple composite extension finite fields to address these challenges. The key of our approach is to design a series of finite fields where increasingly larger fields are based on a previous smaller field. For example, the design of a field with 256 elements F2222is based on polynomial arithmetic over a field with 16 elements F222, in turn based on a field with 4 elements F22. We propose a technique to modify standard Random Linear Network Coding (RLNC) to utilize a set of these fields instead of a single field and analyze the performance. The results show that total overhead is reduced due to reduced size of the coding vector, while maintaining low linear dependency between coded packets. The overhead can in some cases be reduced to less than one-fifth compared to standard RLNC and importantly the ability to recode is preserved.

Conventional cloud storage services offer relatively good reliability and performance in a cost-effective manner. However, they are typically structured in a centralized and highly controlled fashion. In more dynamic storage scenarios, these centralized approaches are unfeasible and developing decentralized storage approaches becomes critical. The novelty of this paper is the introduction of the highly dynamic distributed mobile cloud, which uses free resources on user devices to move storage to the edges of the network. At the core of our approach, lies the use of random linear network coding to provide an effective and flexible erasure correcting code. This paper identifies and answers key questions regarding the feasibility of such a system. We show that the mobile cloud has sufficient network resources to adapt to changes in node numbers and also study the redundancy level needed to maintain data availability. We have found that as little as 75% redundancy is enough to offer 99.28% availability for the examined period and essentially 100% availability is achieved when using 50% redundancy along with high-availability nodes. We have leveraged traces from a popular P2P mobile application to simulate the processes governing user behavior to show feasibility of mobile storage clouds in real scenarios.

Although Random Linear Network Coding (RLNC) has been shown to reduce the number of transmissions for multi-cast scenarios, there is an inherent signaling overhead to achieve this benefit. Employing a large field result in less transmissions but at the cost of a large coding vector of coefficients. Conversely, a smaller field fewer bits to represent the coding coefficients, but has the drawback of requiring more transmissions to deliver the data due to a high probability of linear dependence. This work advocates for the use of telescopic network codes as a way to achieve low overhead for cooperation in multicast transmissions over mobile networks. The idea behind them is to design a field with a larger size as a composite of a smaller field in order to be able to use some of the arithmetics of the extended field as operations in the base field, in order to allow for the use of different fields within a single generation. The resulting codes posses very low overhead by having a short coded packet representation and still maintain a low linearly dependent probability for the last packets. We provide an analytical framework and numerical results showing that is feasible to attain less than 3% total mean overhead. This is considerably lower than what can be achieved with RLNC schemes in most of the considered cases and achieving at least 1.5-2x gains.

Distributed storage solutions have become widespread due to their ability to store large amounts of data reliably across a network of unreliable nodes, by employing repair mechanisms to prevent data loss. Conventional systems rely on static designs with a central control entity to oversee and control the repair process. Given the large costs for maintaining and cooling large data centers, our work proposes and studies the feasibility of a fully decentralized systems that can store data even on unreliable and, sometimes, unavailable mobile devices. This imposes new challenges on the design as the number of available nodes varies greatly over time and keeping track of the system's state becomes unfeasible. As a consequence, conventional erasure correction approaches are ill-suited for maintaining data integrity. In this highly dynamic context, random linear network coding (RLNC) provides an interesting solution. Our goal is to characterize RLNC's guaranteed data integrity region in terms of the total number of storage devices that need to be available and stored data per device. We compare our fully distributed RLNC approach to centralized (genie aided) and fully decentralized replication and Reed-Solomon mechanisms. Our results use traces from a BitTorrent client for Android devices to show that RLNC outperforms the next best scheme (fully centralized Reed-Solomon) not only by having a much lower probability of data loss, but by reducing storage requirements by up to 50% and reconstruction traffic by up to 40%. Gains over decentralized schemes are even larger.

Network-coded cooperative communication (NC-CC) has been proposed and evaluated as a powerful technology that can provide a better quality of service in the next-generation wireless systems, e.g., D2D communications. Previous contributions have focused on performance evaluation of NC-CC scenarios rather than searching for optimal policies that can minimize the total cost of reliable packet transmission. We break from this trend by initially analyzing the optimal design of NC-CC for a wireless network with one source, two receivers, and half-duplex erasure channels. The problem is modeled as a special case of Markov decision process (MDP), which is called stochastic shortest path (SSP), and is solved for any field size, arbitrary number of packets, and arbitrary erasure probabilities of the channels. The proposed MDP solution results in an optimal transmission policy per time slot, and we use it to design near-optimal heuristics for packet transmission in a network of one source and N ≥ 2 receivers. We also present numerical results that illustrate the performance of the proposed heuristics under a variety of scenarios. To complete our analysis, our heuristics are implemented in Aalborg University's Raspberry Pi testbed and compared with random linear network coding (RLNC) broadcast in terms of completion time, total number of required transmissions, and percentage of delivered generations. Our measurements show that enabling cooperation only among pairs of devices can decrease the completion time by up to 4.75 times, while delivering 100% of the 10000 generations transmitted, as compared to RLNC broadcast delivering only 88% of them in our tests.

A fundamental understanding of the delay and throughput benefits of network coding over multiple heterogeneous half-duplex communication interfaces is critical to fully exploit current and future devices that incorporate multiple communication technologies. The goal of this paper is twofold. First, to present fundamental limits and several strategies to tradeoff data and feedback when using multiple interfaces. Our work sets forth a systematic approach to i) analyze a variety of schemes in the presence of channels with heterogeneous round-trip delays, packet transmission rates, and packet loss probability, and to ii) determine the optimal number of transmissions to be allocated to each channel based on these characteristics. Our analytical results show that the gains over a variety of uncoded approaches can be several fold and that our proposed strategies are within 1 dB to an optimal system with full duplex interfaces over a wide range of operating conditions. Our second goal is to understand the practical implications of these results by designing a protocol for file transmissions, implement it in Android smart phones, and measure its performance when combining various interfaces, including, Bluetooth, WiFi, and 3G cellular networks. Our measurements show that throughput is increased not only by the aggregation of multiple interfaces but also by providing a much more robust erasure correction mechanism.

The design of the communication protocols in wireless sensor networks (WSNs) often neglects several key characteristics of the sensor's hardware, while assuming that the number of transmitted bits is the dominating factor behind the system's energy consumption. A closer look at the hardware specifications of common sensors reveals, however, that other equally important culprits exist, such as the reception and processing energy. Hence, there is a need for a more complete hardware abstraction of a sensor node to reduce effectively the total energy consumption of the network by designing energy-efficient protocols that use such an abstraction, as well as mechanisms to optimize a communication protocol in terms of energy consumption. The problem is modeled for different feedback-based techniques, where sensors are connected to a base station, either directly or through relays. We show that for four example platforms, the use of relays may decrease up to 4.5 times the total energy consumption when the protocol and the hardware are carefully matched. We conclude that: 1) the energy budget for a communication protocol varies significantly on different sensor platforms; and 2) the protocols can be judiciously adapted to the underlying hardware. The results are cross-validated using real-life measurements.

This paper studies the problem of optimal use of a relay for reducing the transmission time of data packets from a source to a destination using network coding. More importantly, we address an effect that is typically overlooked in previous studies: the presence of active transmitting nodes in the neighborhood of such devices, which is typical in wireless mesh networks. We show that in systems with a fair medium access control mechanism (MAC), the use of a relay in a crowded medium brings forth considerable and unforeseen improvements, including up to 3.5x gains in terms of throughput compared to using only the direct link in some of our examples, and a considerable extension of the operating region where using a relay is beneficial. The problem is formulated as a Markov Decision Process (MDP) and numerical results are provided comparing simple, close-to-optimal heuristics to the optimal scheme.

Packet losses in wireless networks dramatically curbs the performance of TCP. This paper introduces a simple coding shim that aids IP-layer traffic in lossy environments while being transparent to transport layer protocols. The proposed coding approach enables erasure correction while being oblivious to the congestion control algorithms of the utilised transport layer protocol. Although our coding shim is indifferent towards the transport layer protocol, we focus on the performance of TCP when ran on top of our proposed coding mechanism due to its widespread use. The coding shim provides gains in throughput that exceed 10x for TCP traffic while requiring a limited sacrifice in terms of fairness towards other flows on the channel.

This paper presents the design and performance evaluation of an inexpensive testbed for network coding protocols composed of Raspberry Pis. First, we show the performance of random linear network coding primitives on the Raspberry Pi in terms of processing speed and energy consumption under a variety of configuration setups. Our measurements show that processing rates of up to 230 Mbps are possible with the Raspberry Pi. Also, the energy consumption per bit can be as small as 3 nJ/bit, which is several orders of magnitude smaller than the transmission/reception energy use. Surprisingly, overclocking the Raspberry Pi from 700 MHz to 1000 MHz not only produces an increase in processing speed of up to 68 % for large generation sizes, but also provides a reduction of 64 % in the processing energy per bit for most tested scenarios. Then, we show Raspberry Pi as an inexpensive, viable, and flexible platform to deploy large research networking testbeds for the evaluation of network coding protocols. We propose key parameters and representations to evaluate protocol performance in network nodes as well as validating the testbed's statistics using the case of a one-hop broadcast with random linear network coding, which is well understood in theory.

Traditionally, the idea of overlapping generations in network coding research has focused on reducing the complexity of decoding large data files while maintaining the delay performance expected of a system that combines all data packets. However, the effort for encoding and decoding individual generations can still be quite high compared to other sparse coding approaches. This paper focuses on an inherently different approach that combines (i) sparsely coded generations configured on-the- fly based on (ii) controllable and infrequent feedback that allows the system to remove some original packets from the pool of packets to be mixed in the linear combinations. The latter is key to maintain a high impact of the coded packets received during the entire process while maintaining very sparsely coded generations. Interestingly, our proposed approach naturally bridges the idea of overlapping generations with that of tunable sparse network coding, thus providing the system with a seamless and adaptive strategy to balance complexity and delay performance. We analyze two families of strategies focused on these ideas. We also compare them to other standard approaches both in terms of delay performance and complexity as well as providing measurements in commercial devices to support our conclusions. Our results show that a judicious choice of the overlapping of the generations provides close-to-optimal delay performance, while reducing the decoding complexity by up to an order of magnitude with respect to other schemes.

In this paper, we investigate the optimal design of cooperative network-coded strategies for a three-node wireless network with time-varying half-duplex erasure channels. To this end, we formulate the problem of minimizing the total cost of transmitting M packets from source to two receivers as a Markov decision process (MDP). The actions of the MDP model include the source and the type of transmission to be used in a given time slot given perfect knowledge of the system state. The cost of packet transmission is defined such that it can incorporate the difference between broadcast and unicast transmissions, e.g., in terms of the rate of packet transmission or the energy consumption. A comprehensive analysis of the MDP solution is carried out under different network conditions to extract optimal rules of packet transmission. Inspired by the extracted rules, we propose two near-optimal heuristics that are suitable for practical systems. We use two wireless channel models to analyze the performance of the proposed heuristics in practical wireless networks, namely; an infrastructure-to-vehicle communication in a highway scenario considering Rayleigh fading; and real packet loss measurements for WiFi using Aalborg University's Raspberry Pi testbed. We compare our results with random linear network coding broadcasting schemes showing that our heuristics can provide up to 2 × gains in completion time and up to 4 × gains in terms of reliably serviced data packets.

A characterization of systematic network coding over multi-hop wireless networks is key towards understanding the trade-off between complexity and delay performance of networks that preserve the systematic structure. This paper studies the case of a relay channel, where the source's objective is to deliver a given number of data packets to a receiver with the aid of a relay. The source broadcasts to both the receiver and the relay using one frequency, while the relay uses another frequency for transmissions to the receiver, allowing for a full-duplex operation of the relay. We analyze the decoding complexity and delay performance of two types of relays: one that preserves the systematic structure of the code from the source; another that does not. A systematic relay forwards uncoded packets upon reception, but transmits coded packets to the receiver after receiving the first coded packet from the source. On the other hand, a non-systematic relay always transmits linear combinations of previously received packets. We compare the performance of these two alternatives by analytically characterizing the expected transmission completion time as well as the number of uncoded packets forwarded by the relay. Our numerical results show that, for a poor channel between the source and the receiver, preserving the systematic structure at the relay (i) allows a significant increase in the number of uncoded packets received by the receiver, thus reducing the decoding complexity, and (ii) preserves close to optimal delay performance.

Network coding has the potential to enhance energy efficiency of multicast sessions by providing optimal communication subgraphs for the transmission of the data. However, the coding requirement at intermediate nodes may introduce additional complexity and energy consumption in order to code the data packets. Previous work has shown that in lossless wireline networks, the performance of tree-packing mechanisms is comparable to network coding, albeit with added complexity at the time of computing the trees. This means that most nodes in the network need not code. Thus, mechanisms that identify intermediate nodes that do require coding is instrumental for the efficient operation of coded networks and can have a significant impact in overall energy consumption. We present a distributed, low complexity algorithm that allows every node to identify if it should code and, if so, through what output link should the coded packets be sent. Our algorithm uses as input the optimal subgraph determined by Lun et al's optimization formulation [13]. Numerical results are provided using common Internet Service Provider (ISP) network topologies and also random network deployments. Our results show that the number of coding nodes in the expectation is very low (typically below 1) and that the number of sessions that require coding is limited, e.g., less than 15% for sessions of 4 receivers for the ISP networks and below 0.1% for networks with random node deployments in a square of 1 × 1 km2with of up to 30 nodes and up to 20 receivers.

A fundamental knowledge of the trade-off between sensor cooperation and autonomous vehicles' (AV) trajectory planning is pivotal towards characterizing the sensing capabilities of wireless sensor networks that employ AV for collecting the data and to ensure their successful integration in large scale sensor deployments. We formulate the problem of efficient data gathering as a mixed integer linear programming (MILP) problem that provides a joint optimization of AV trajectory and data-routing. Since MILP formulations are not scalable, we propose an approach to develop heuristics where the joint optimization is decoupled into three sub-problems. The first is to determine clusters of sensors with communication range limitations. The second is to efficiently connect the clusters. The third is to design the route inside the cluster that will minimize the cost of data collection. We characterize performance of the proposed heuristics through Monte-Carlo simulations. Performance is measured in terms of (a) the joint energy cost for cooperation and AV movement for different number of sensor nodes and communication ranges of these sensors, and (b) computational effort of the various heuristics. For small deployments, we compare the heuristics to the MILP global optimization and show that the gap between them can be lower than 2% for deployments as large as 18 nodes and typically below 25% for a wide range of scenarios.

Network coding (NC) has attracted tremendous attention from the research community due to its potential to significantly improve networks' throughput, delay, and energy performance as well as a means to simplify protocol design and naturally providing security support. The possibilities in code design have produced a large influx of new ideas and approaches to harness the power of NC. But, which of these designs are truly successful in practice? and which designs will not live up to their promised theoretical gains due to real-world constraints? Without attempting a comprehensive view of all practical pitfalls, this paper seeks to identify key ingredients to a successful design, critical and common limitations to most intra-session NC systems as well as promising techniques and ideas to guide future models and research problems grounded on practical concerns.

We consider the performance of network coding for a wireless cooperative network in which a source wants to transmit M data packets to two receivers. We assume that receivers can share their received packets with each other or simply wait to receive the packets from the source. The problem of finding an optimum packet transmission policy that minimizes the completion time in such a network is solved by modeling the problem as a Markov Decision Process (MDP). Our analysis is useful for a series of network coding and forwarding schemes with or without feedback. Our results show that the optimal network coding solution in terms of completion time, outperforms broadcasting with network coding by a factor of 2.13 and outperforms forwarding mechanisms by a factor of 6.1. Beyond computing the optimal completion time, we identify the critical decision policies derived from the MDP solution.

This paper presents a detailed performance evaluation of inter-session network coding in wireless meshed networks in terms of throughput and energy consumption. A full analytical model is given for three different communication approaches for the bidirectional cross topology using an IEEE 802.11 medium access. One of the three approaches is pure relaying, while the other two approaches are using network coding with and without overhearing of other flows. The main outcome of the paper is that network coding without and with overhearing can increase the throughput by the factor of two and four, respectively, for high load scenarios. Furthermore we show that the energy/bit ratio is decreased by the use of network coding approaches, underlining that the added complexity of network coding pays off when considering the overall system.

State-of-the-art in network coding for wireless, meshed networks typically considers two problems separately. First, the problem of providing reliability for a single session. Second, the problem of opportunistic combination of flows by using minimalistic coding, i.e., by XORing packets from different flows. Instead of maintaining these approaches separate, we propose a protocol (CORE) that brings together these coding mechanisms. Our protocol uses random linear network coding (RLNC) for intra- session coding but allows nodes in the network to setup inter- session coding regions where flows intersect. Routes for unicast sessions are agnostic to other sessions and setup beforehand, CORE will then discover and exploit intersecting routes. Our approach allows the inter-session regions to leverage RLNC to compensate for losses or failures in the overhearing or transmitting process. Thus, we increase the benefits of XORing by exploiting the underlying RLNC structure of individual flows. This goes beyond providing additional reliability to each individual session and beyond exploiting coding opportunistically. Our numerical results show that CORE outperforms both forwarding and COPE-like schemes in general. More importantly, we show gains of up to 4 fold over COPE-like schemes in terms of transmissions per packet in one of the investigated topologies.

This paper seeks to understand and characterize policies that exploit multiple available technologies and/or heterogeneous communication routes simultaneously with the goal of improving throughput and energy performance or economical costs in a converged networks scenarion. We present an optimization framework and a set of allocation policies to provide efficient, channel-aware load allocation for multi-homed devices under different cost criteria. Network coding is used as a key enabler of these techniques as coding across packets requires less coordination, simpler and less frequent feedback mechanisms, and higher resiliency to changes in the transmission channel. Our formulation incorporates bursty erasure channels, multiple simultaneous communication routes, and different channel coding and modulations available to each technology as part of the resource allocation optimization. Numerical results are provided showing that dynamic allocation policies are instrumental to improving resource efficiency by reducing energy consumption and/or channel utilization. The energy gains of our proposed policies outperform the best fixed network coding multi-homing policies by a factor of 2 in some scenarios.

The throughput benefits of random linear network codes have been studied extensively for wirelined and wireless erasure networks. It is often assumed that all nodes within a network perform coding operations. In energy-constrained systems, however, coding subgraphs should be chosen to control the number of coding nodes while maintaining throughput. In this paper, we explore the strategic use of network coding in the wireless packet erasure relay channel according to both throughput and energy metrics. In the relay channel, a single source communicates to a single sink through the aid of a half-duplex relay. The fluid flow model is used to describe the case where both the source and the relay are coding, and Markov chain models are proposed to describe packet evolution if only the source or only the relay is coding. In addition to transmission energy, we take into account coding and reception energies. We show that coding at the relay alone while operating in a rateless fashion is neither throughput nor energy efficient. Given a set of system parameters, our analysis determines the optimal amount of time the relay should participate in the transmission, and where coding should be performed.

Aiming to exploit the capabilities of next generation terminals to receive and process several, partially overlapping beams of a multibeam satellite, we present a mathematical analysis and propose algorithms to provide enhanced and robust load-balancing to unequal load demands between beams. At the core of our mechanisms is a resource allocation problem that aims to minimize the time to deliver packets taking into account the load (traffic demands) per beam and channel conditions. Network coding is a key enabler of our mechanism, allowing a seamless and efficient exploitation of the multiple, available paths from satellite gateways to end-users and leading to a more efficient allocation of resources in each beam. Advantages over current state-of-the-art for load balancing for multibeam satellites include: i) cooperation amongst neighboring beams to improve system stable throughput, ii) use of random linear network coded packets to enhance reliability and simplify the allocation of packets to the different beams, and iii) adaptation to short-term dynamics of the traffic of each beam, instead of only long term traffic characteristics. We provide numerical results for the case of a multibeam satellite covering Europe with 70 beams showing that our technique can increase the stable throughput by 30% or higher with respect to current techniques.

Autonomous Vehicles (AV) are used to solve the problem of data gathering in large scale sensor deployments with disconnected clusters of sensors networks. Our take is that an efficient strategy for data collection with AVs should leverage i) cooperation amongst sensors in communication range of each other forming a sensor cluster, ii) advanced coding and data storage techniques for easing the cooperation process, and iii) AV route-planning that is both content and cooperation-aware. Our work formulates the problem of efficient data gathering as a cooperative route-optimization problem with communication constraints. We also analyze (network) coded data transmission and storage for simplifying cooperation amongst sensors as well as data collection by the AV. Given the complexity of the problem, we focus on heuristic techniques, such as particle swarm optimization, to calculate the AV's route and the times for communication with each sensor and/or cluster of sensors. We analyze two extreme cases, i.e., networks with and without intra- cluster cooperation, and provide numerical results to illustrate that the performance gap between them increases with the number of nodes. We show that cooperation in a 100 sensor deployment can increase the amount of data collected by up to a factor of 3 with respect to path planning without cooperation.

In networks with large latency, feedback about received packets may lag considerably the transmission of the original packets, limiting the feedback's usefulness. Moreover, time duplex constraints may entail that receiving feedback may be costly. In this work, we consider tailoring feedback and coding jointly in such settings to reduce the expected delay for successful in order reception of packets. We find that, in certain applications, judicious choices provide results that are close to those that would be obtained with a full-duplex system. We study two cases of data transmission: one-to-all broadcast and all-to-all broadcast. We also analyze important practical considerations weighing the trade off between performance and complexity in applications that rely on random linear network coding. Finally, we study the problem of transmission of information under the large latency and time duplexing constraints in the presence of random packet arrivals. In particular, we analyze the problem of using a batch by batch approach and an online network coding approach with Poisson arrivals. We present numerical results to illustrate the performance under a variety of scenarios and show the benefits of the proposed schemes as compared to typical ARQ and scheduling schemes.

We consider a line of terminals which is connected by packet erasure channels and where random linear network coding is carried out at each node prior to transmission. In particular, we address an online approach in which each terminal has local information to be conveyed to the base station at the end of the line and provide a queueing theoretic analysis of this scenario. First, a genie-aided scenario is considered and the average delay and average transmission energy depending on the link erasure probabilities and the Poisson arrival rates at each node are analyzed. We then assume that all nodes cannot send and receive at the same time. The transmitting nodes in the network send coded data packets before stopping to wait for the receiving nodes to acknowledge the number of degrees of freedom, if any, that are required to decode correctly the information. We analyze this problem for an infinite queue size at the terminals and show that there is an optimal number of coded data packets at each node, in terms of average completion time or transmission energy, to be sent before stopping to listen.

A fundamental understanding of the delay behavior of network coding is key towards its successful application in real-time applications with strict message deadlines. Previous contributions focused mostly on the average decoding delay, which although useful in various scenarios of interest is not sufficient for providing worst-case delay guarantees. To overcome this challenge, we investigate the entire delay distribution of random linear network coding for any field size and arbitrary number of encoded symbols (or generation size). By introducing a Markov chain model we are able to obtain a complete solution for the erasure broadcast channel with two receivers. A comparison with Automatic Repeat reQuest (ARQ) with perfect feedback, round robin scheduling and a class of fountain codes reveals that network coding on GF(24) offers the best delay performance for two receivers. We also conclude that GF(2) induces a heavy tail in the delay distribution, which implies that network coding based on XOR operations although simple to implement bears a relevant cost in terms of worst-case delay. For the case of three receivers, which is mathematically challenging, we propose a brute-force methodology that gives the delay distribution of network coding for small generations and field size up to GF(24).

We study an online random linear network coding approach for time division duplexing (TDD) channels under Poisson arrivals. We model the system as a bulk-service queue with variable bulk size and with feedback, i.e., when a set of packets are serviced at a given time, they might be reintroduced to the queue to form part of the next service batch. We show that there is an optimal number of coded data packets that the sender should transmit back-to-back before stopping to wait for an acknowledgement from the receiver. This number depends on the latency, probability of packet erasure, degrees of freedom at the receiver, the size of the coding window, and the arrival rate of the Poisson process. Random network coding is performed across a moving window of packets that depends on the packets in the queue, design constraints on the window size, and the feedback sent from the receiver. We study the mean time between generating a packet at the source and it being "seen", but not necessarily decoded, at the receiver. We also analyze the mean time between a decoding event and the next, defined as the decoding of all the packets that have been previously "seen" and those packets involved in the current window of packets. Inherently, a decoding event implies an in-order decoding of a batch of data packets. We present numerical results illustrating the trade-off between mean delay and mean time between decoding events.

Multi-resolution codes enable multicast at different rates to different receivers, a setup that is often desirable for graphics or video streaming. We propose a simple, distributed, two-stage message passing algorithm to generate network codes for single-source multicast of multi-resolution codes. The goal of this pushback algorithm is to maximize the total rate achieved by all receivers, while guaranteeing decodability of the base layer at each receiver. By conducting pushback and code assignment stages, this algorithm takes advantage of inter-layer as well as intra-layer coding. Numerical simulations show that in terms of total rate achieved, the pushback algorithm outperforms routing and intra-layer coding schemes, even with field sizes as small as 2^10(10 bits). In addition, the performance gap widens as the number of receivers and the number of nodes in the network increases. We also observe that naive inter-layer coding schemes may perform worse than intra-layer schemes under certain network conditions.

We present a systematic network coding approach for time-division duplexing channels. In particular, we study the case of a node transmitting to a single receiver. We show that the use of systematic network coding using XORs can provide the same or close to the same performance in terms of completion time as a random linear network coding scheme that uses a large field size, with the added advantage of requiring fewer and simpler operations during the decoding process. We show that the average computation required to decode using systematic network coding in an erasure channel grows as O(M3Pe3), where M is the number of original packets being coded together, and Pe is the packet erasure probability. This means that systematic network coding requires Pe-3times fewer operations on average than random linear network coding with the same field size.

Capacity scaling laws are analyzed in an underwater acoustic network with n regularly located nodes. A narrow-band model is assumed where the carrier frequency is allowed to scale as a function of n. In the network, we characterize an attenuation parameter that depends on the frequency scaling as well as the transmission distance. A cut-set upper bound on the throughput scaling is then derived in extended networks. Our result indicates that the upper bound is inversely proportional to the attenuation parameter, thus resulting in a highly power-limited network. Furthermore, we describe an achievable scheme based on the simple nearest-neighbor multi-hop (MH) transmission. It is shown under extended networks that the MH scheme is order-optimal as the attenuation parameter scales exponentially with √n (or faster). Finally, these scaling results are extended to a random network realization.

We study the effect of the field size on the performance of random linear network coding for time division duplexing channels proposed in [1]. In particular, we study the case of a node broadcasting to several receivers. We show that the effect of the field size can be included in the transition probabilities of the Markov chain model of the system. Also, an improved upper bound on the mean number of coded packets required to decode M original data packets using random linear network coding is presented. This bound shows that even if the field size is 2, i.e. we perform XORs amongst randomly selected packets from the pool of M original ones, we will need on average at most M + 2 coded packets in order to decode. Thus, there will be only a very small degradation in performance if M is large. We present numerical results showing that the mean completion time of our scheme with a field size of 2 is close in performance to our scheme when we use larger field sizes. We also show that as M increases, the difference between using a field size of 2 and larger field sizes decreases. Finally, we show that we can get very close to the optimal performance with small field sizes, e.g. a field size of 4 or 8, even when M is not very large.

We study the energy performance of random linear network coding for time division duplexing channels. We assume a packet erasure channel with nodes that cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge the number of degrees of freedom, if any, that are required to decode correctly the information. Our analysis shows that, in terms of mean energy consumed, there is an optimal number of coded data packets to send before stopping to listen. This number depends on the energy needed to transmit each coded packet and the acknowledgment (ACK), probabilities of packet and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. We show that its energy performance is superior to that of a full-duplex system. We also study the performance of our scheme when the number of coded packets is chosen to minimize the mean time to complete transmission as in. Energy performance under this optimization criterion is found to be close to optimal, thus providing a good trade-off between energy and time required to complete transmissions.

A new random linear network coding scheme for reliable communications for time division duplexing channels is proposed. The setup assumes a packet erasure channel and that nodes cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge (ACK) the number of degrees of freedom, if any, that are required to decode correctly the information. We provide an analysis of this problem to show that there is an optimal number of coded data packets, in terms of mean completion time, to be sent before stopping to listen. This number depends on the latency, probabilities of packet erasure and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. This scheme is optimal in terms of the mean time to complete the transmission of a fixed number of data packets. We show that its performance is very close to that of a full duplex system, while transmitting a different number of coded packets can cause large degradation in performance, especially if latency is high. Also, we study the throughput performance of our scheme and compare it to existing half-duplex go-back-N and selective repeat ARQ schemes. Numerical results, obtained for different latencies, show that our scheme has similar performance to the selective repeat in most cases and considerable performance gain when latency and packet error probability is high.

We study the performance of random linear network coding for time division duplexing channels with Poisson arrivals. We model the system as a bulk-service queue with variable bulk size. A full characterization for random linear network coding is provided for time division duplexing channels by means of the moment generating function. We present numerical results for the mean number of packets in the queue and consider the effect of the range of allowable bulk sizes. We show that there exists an optimal choice of this range that minimizes the mean number of data packets in the queue.

We propose a linear network coding scheme to disseminate a finite number of data packets in arbitrary networks. The setup assumes a packet erasure channel, slotted time, and that nodes cannot transmit and receive information simultaneously. The dissemination process is completed when all terminals can decode the original data packets. We also assume a perfect knowledge of the information at each of the nodes, but not necessarily a perfect knowledge of the channel. A centralized controller decides which nodes should transmit, to what set of receiver nodes, and what information should be broadcasted. We show that the problem can be thought of as a scheduling problem, which is hard to solve. Thus, we consider the use of a greedy algorithm that only takes into account the current state of the system to make a decision. The proposed algorithm tries to maximize the impact on the network at each slot, i.e. maximize the number of nodes that will benefit from the coded packet sent by each active transmitter. We show that our scheme is considerably better, in terms of the number of slots to complete transmission, than schemes that choose the node with more information as the transmitter at every time slot.

The goal of this paper is two-fold. First, to establish a tractable model for the underwater acoustic channel useful for network optimization in terms of convexity. Second, to propose a network coding based lower bound for transmission power in underwater acoustic networks, and compare this bound to the performance of several network layer schemes. The underwater acoustic channel is characterized by a path loss that depends strongly on transmission distance and signal frequency. The exact relationship among power, transmission band, distance and capacity for the Gaussian noise scenario is a complicated one. We provide a closed-form approximate model for 1) transmission power and 2) optimal frequency band to use, as functions of distance and capacity. The model is obtained through numerical evaluation of analytical results that take into account physical models of acoustic propagation loss and ambient noise. Network coding is applied to determine a lower bound to transmission power for a multicast scenario, for a variety of multicast data rates and transmission distances of interest for practical systems, exploiting physical properties of the underwater acoustic channel. The results quantify the performance gap in transmission power between a variety of routing and network coding schemes and the network coding based lower bound. We illustrate results numerically for different network scenarios.

As WiFi networks and IP telephony grow increasingly popular, the standard Distributed Control Function (DCF) MAC protocol in IEEE 802.11b, which is not designed to support realtime applications, has become a major hurdle in the effort to increase Voice over IP (VoIP) capacity. This work identifies the FAIR algorithm as a viable solution for increasing VoIP capacity in 802.11b networks, since it is aimed at providing a more balanced use of medium resources in infrastructure-based networks and it can be implemented by simply changing the MAC protocol at the Access Point only. Simulations using real traffic scenarios (including both VoIP and HTTP users) show VoIP capacity gains of 50% and more, and also provide an insight on the issues that may further accentuate the effectiveness of FAIR.