With the proliferation of RFID-enabled applications, large-scale RFID systems often require multiple readers to ensure full coverage of numerous tags. In such systems, we sometimes pay more attention to a subset of tags instead of all, which are called key tags. This paper studies an under-investigated problemkey tag distribution identification, which aims to identify which key tags are beneath which readers. This is crucial for efficiently managing specific items of interest, which can quickly pinpoint key tags and help RFID readers covering these tags collaborate to improve the tag inventory efficiency. We propose a protocol called Kadept that identifies the key tag distribution by designing a sophisticated Cuckoo filter that teases out key tags as well as assigns each of them a singleton slot for response. With this design, a great number of trivial (non-key) tags will keep silent and free up bandwidth resources for key tags, and each key tag is sorted in a collision-free way and can be identified with only 1-bit response, which significantly improves the time efficiency. To enhance the scalability and efficiency of Kadept for high key tag proportions, we propose E-Kadept protocol, which accelerates the identification process by designing an incremental Cuckoo filter that reduces false positives and improves space efficiency. We theoretically analyze how to optimize protocol parameters of Kadept and E-Kadept, and conduct extensive simulations under different tag distribution scenarios. Compared with the state-of-the-art, E-Kadept can improve the time efficiency by a factor of 1.75×, when the ratio of key tags to all tags is 0.3.

The rise of pre-trained foundation models (FMs) has popularized the trend of fine-tuning FMs to fit downstream tasks, while Federated Learning (FL) has become the de-facto approach for training distributed data with privacy-preservation. However, fine-tuning FMs in FL faces overwhelming overheads due to its bulky nature. While freezing parameters in FM have the potential to accelerate FL training, existing freezing strategies statically freeze parameters on specified or already converged layers, incur severe accuracy degradation, and resource-inefficiency in heterogeneous environments. In this paper, we propose AFedLF, an adaptive freezing framework for FM in FL, to accelerate its wall-clock time for convergence without losing its final accuracy. However, this poses great challenges, as different freezing strategies lead to different accuracy gains and time overheads, while unfreezing more layers may bring marginal accuracy gains but significant time overheads. To address this challenge, AFedLF mathematically establishes a correlation between the freezing strategy and the accuracy gain and time overhead, and allocates adaptive freezing strategies to clients, based on our insight that unfreezing more layers on devices with strong computation and communication capabilities helps improve resource efficiency. Besides, AFedLF incorporates our well-designed intermediate result caching scheme with constant approximation ratios utilizing the limited storage capacity on mobile devices to cache intermediate results to skip forward propagation, further saving wall-clock time. Finally, we implemented AFedLF using an open-source FL benchmark, and extensive trace-driven experimental results showed that AFedLF accelerates wall-clock time by up to 6.1× compared to state-of-the-art solutions, without sacrificing accuracy.

Vehicle-Infrastructure Collaboration (VIC) integrates vehicles and roadside infrastructure using advanced communication technologies, forming a crucial component of intelligent transportation systems (ITS). In a VIC system, tasks generated by vehicles can either be processed locally or offloaded to nearby edge servers. Current research often focuses on optimizing task scheduling but overlooks the inherent spatiotemporal correlations among tasks, which can lead to redundant computations due to similar tasks producing identical results. Additionally, the diversity in research scenarios and model constructions has resulted in the absence of a unified simulation verification platform, making it difficult to compare and validate various scheduling algorithms. To address these challenges, we have developed a comprehensive VIC simulation platform (CVSP). This platform not only features vehicle simulation capabilities like those of SUMO for modeling vehicle movement, but it also allows for the customization of driving scenarios and configurations, including edge resource settings, and incorporates a unified algorithm execution module for evaluating the performance of scheduling algorithms. Using CVSP can provide a clearer understanding of the strengths and weaknesses of scheduling algorithms, which in turn benefits the development of VIC systems. To tackle the spatiotemporal correlations observed in vehicular tasks, we propose a branch and bound algorithm based on computation-reuse (BB-CR). This algorithm integrates a computational reuse model derived from fused vehicle and road data. We simulate both non-congested and congested scenarios of vehicles traversing intersections to validate the performance of the baseline and BB-CR on the CVSP. The results highlight the versatility of the CVSP, showing that the BB-CR algorithm reduces system costs and minimizes the probability of task loss compared to the baseline. The code is publicly available at https://github.com/lzp991105/comprehensive-VIC-simulation-platform.git.

Neural video compression (NVC) has emerged as a promising paradigm for improving rate-distortion performance. However, existing neural video codecs predominantly rely on convolutional neural networks (CNNs) with limited local receptive fields to generate the latent representations, often neglecting global–local spatial correlations. This leads to suboptimal feature modeling and redundancy in the latent space. To address this limitation, we propose a novel Dual-Scale Transformer (DST) block specifically tailored for NVC, which effectively enhances coding efficiency. The DST block incorporates a Global–Local (Shifted) Window-based Self-Attention (GL(S)WSA) mechanism to jointly capture global structure information and local texture details. Moreover, we design a Cross-Gated Feed-Forward Network (CGFFN) to adaptively modulate complementary components, producing more compact and expressive latent representations. Furthermore, to overcome the drawbacks of traditional asynchronous training and further boost rate-distortion performance, we introduce a Variable Bitrate Synchronization (VBRS) strategy that leverages multi-GPU parallel training, with each GPU dedicated to a specific bitrate and synchronized via gradient backpropagation for joint optimization. Experimental results demonstrate that our proposed method achieves the higher coding performance compared to the previous state-of-the-art (SOTA) methods and significantly outperforms H.266/VVC (VTM-13.2) under various low delay B (LDB) coding configurations.

With the proliferation of RFID-enabled applications, large-scale RFID systems containing numerous tags are becoming increasingly common. Efficient management of these systems requires the ability to quickly collect information from specific subsets of tags, known as target tags. However, existing works often rely on hardware modifications, limiting their applicability to commercial RFID systems. To address this, this paper proposes the Target Tag Information Collection (TTIC) protocol and its enhanced version E-TTIC, both designed for efficient target tag collection using off-the-shelf RFID devices. TTIC leverages the Cuckoo filter to eliminate non-target tags and accurately collect target tags. It first inserts all target tags into the Cuckoo filter and then designs select commands compatible with commercial RFID readers to identify target tags while silencing non-target tags. On top of TTIC, E-TTIC further reduces the collection time by designing a novel Cuckoo filter that requires fewer select commands. We implement our protocols in a commodity RFID system. Extensive experiments show that E-TTIC can improve time efficiency by up to 80 % compared to the baseline.

In the past decade, learning-based image compression has made significant advancements, with the Joint Photographic Experts Group (JPEG) working towards the launch of the first neural network-based image coding standard, JPEG AI. However, traditional codecs like JPEG and HEVC intra coding remain the most widely used. A key challenge arises when attempting to compress images pre-encoded with these traditional codecs using JPEG AI, as such images often carry artifacts that JPEG AI is not fully optimized to handle, leading to significant loss in performance. This paper addresses this issue by proposing a novel transcoding framework designed to optimize pre-encoded images for JPEG AI, bridging the gap between traditional and learning-based compression methods. The framework employs two branches for processing luminance and chrominance components, with a local-global modulation module (LGMM) for luminance and a dynamic fusion module (DFM) for chrominance. Experimental results demonstrate that the proposed scheme achieves up to 22.36% rate savings on images pre-encoded with HEVC intra and up to 22.29% rate savings on images pre-encoded with JPEG using JPEG AI reference software, highlighting its effectiveness in enhancing the performance of JPEG AI for real-world applications.

Range Query (RQ) is to check whether there are any RFID tags with data beyond a given range. With about 46 billion RFID tags sold worldwide in 2023, time-efficient RQ becomes increasingly important for practical use, which can help users quickly pinpoint the target tags (if any) and give an early warning (e.g., fire alarm) to them for taking urgent actions and reducing the potential risk. However, existing work can deal with only a single range rather than multiple ranges that are very common in real-world applications. For example, foods in the refrigerator and the freezer have different temperature ranges for safe storing; treating them as one would probably give rise to query errors. In this paper, we study an under-investigated problem called multi-range query, which aims to achieve RQ in an RFID system with multiple query ranges. We propose a tailored protocol called anomalous tag identification (ATI) that quickly separates target tags from others and avoids querying all tags for saving communication overhead. In ATI, we design a fixedlength encoding vector together with standards-compliant select commands to deal with different ranges individually, without the need for any hardware modification. We implement the proposed protocols in commodity RFID systems. Experimental results show that ATI is superior to the baseline under different parameters, in terms of the time efficiency and space efficiency.

The promptness of decision-making is of paramount importance in coordinate decision-making communication systems. In this paper, we envision a system in which a sender transmits information to a receiver for decision-making. The decision-making process encompasses the extraction of decision-related information followed by subsequent computation. To assess the impact of communication delays, randomness of decision-making and computational time on the immediacy of decisions, we introduce a novel performance metric, namely the age of decision (AoD). Specifically, AoD is defined as the time elapsed since the generation of the update upon which the most recent decision is based. Considering the stochastic nature of decision-making, we analyze the average peak AoD in systems where the arrival and service processes follow general processes or Poisson processes. To facilitate our derivations, we introduce the concept of effective decisions to denote those decisions that can lead to the system’s peak AoD. Simulation results confirm the validity of our derivations and illustrate that appropriately increasing the rate of decision-making can significantly reduce the system’s average peak AoD.

Graphics processing units (GPUs) are widely used to enhance deep learning inference throughput through batch processing, where multiple inference requests are processed simultaneously. When inference requests arrive randomly, waiting for more requests to form a batch can improve throughput but increases latency. Therefore, designing efficient batch scheduling strategies is crucial to strike a good balance. Current batch scheduling strategies are primarily heuristic and non-preemptive, meaning the next batch is scheduled only after the current one completes. In this paper, we first demonstrate that no non-preemptive online batch scheduling algorithm can achieve a constant competitive ratio that does not depend on system configuration parameters. We further propose a preemption restart based online batch scheduling algorithm, and theoretically prove that it achieves a constant competitive ratio. Finally, we demonstrate the effectiveness of our proposed algorithm through extensive simulations.

Previous optical flow based video compression is gradually replaced by unsupervised deformable convolution (DCN) based method. This is mainly due to the fact that the motion vector (MV) estimated by the existing optical flow network is not accurate and may introduce extra artifacts. However, DCN based method is difficult for training owing to the lack of explicit guidance in the feature space. In this work, we propose a learned video compression with spatial-temporal optimization. Specifically, we first propose the spatial-temporal motion refinement module to improve the accuracy of MV estimated by the optical flow network for prediction. Then, we propose the In-loop filter module to remove compression artifacts and improve the reconstructed frame quality. Finally, comprehensive experimental results demonstrate our proposed method outperforms the recent learned methods on three benchmark datasets. Moreover, our method also beats the H.266/VVC in terms of MS-SSIM metrics.

With the proliferation of RFID-enabled applications, multiple readers are required for the complete coverage of numerous tags in a large-scale RFID system. In this scenario, we sometimes pay more attention to a subset of tags instead of all, which are referred to as key tags. In this paper, we study an under-investigated problem key tag distribution identification, which aims to identify which key tags are beneath which readers. This is crucial for efficiently managing specific items of interest, which can quickly pinpoint key tags and help RFID readers covering these tags collaborate to improve the tag inventory efficiency. Since key tags typically make up a small part of all tags, it is time consuming to deal with all tags in the traditional way. We propose a protocol called Kadept that identifies the key tag distribution by using a sophisticatedly designed filter that teases out key tags as well as assigns each of them a singleton slot for response. With this design, a great number of trivial (non-key) tags will keep silent and free up bandwidth resources for key tags, and each key tag is sorted in a collision-free way and can be identified with only 1-bit response, which significantly improves the time efficiency. We theoretically analyze how can we optimize protocol parameters of Kadept and conduct extensive simulations under different tag distribution scenarios. Compared with the state-of-the-art, Kadept can improve the time efficiency by a factor of 3.7×, when the ratio of key tags to all tags is 0.1.

Over-the-air federated edge learning (Air-FEEL) shows promise as a distributed machine learning paradigm for edge devices. By leveraging the superposition property of a multiple access channel (MAC), Air-FEEL can achieve low communication latency during training while enhancing the data privacy of edge devices, though at the expense of compromised learning performance. Recent studies suggest that optimizing the convergence speed of Air-FEEL can be accomplished by regulating the transmission power of edge devices while ensuring their differential privacy (DP). In this paper, we advance by incorporating device sampling in Air-FEEL (Air-FEEL-DS) to improve privacy and reduce device energy consumption, where each edge device decides randomly and independently whether to participate in each training round. Firstly, we theoretically characterize both the DP guarantee and convergence performance of Air-FEEL-DS. Then, we formulate a power control optimization problem to optimize the convergence speed while ensuring a specified DP guarantee. Despite the non-convex nature of this problem, we propose an efficient algorithm by linking it to a variant, transforming the variant into a convex problem, and demonstrating that the convex problem accommodates an efficient waterfilling-like algorithm. Finally, simulation results show that our proposed power control scheme achieves much faster convergence for Air-FEEL-DS than the channel inversion method, and has close convergence performance with significantly lower energy consumption compared to Air-FEEL with optimized power control but without device sampling.

With their superior maneuverability and flexible deployment options, unmanned aerial vehicles (UAVs) present a viable solution to augment cellular network capabilities by serving as mobile base stations (BSs). Yet, the three-dimensional, dynamic nature of UAV deployments, along with changing aerial conditions, often results in frequent handovers, adversely affecting communication quality. Moreover, the impacts of transitions between line-of-sight (LoS) and non-line-of-sight (NLoS) links on handover and coverage probabilities in mobile UAV networks have not been thoroughly investigated. This paper provides an in-depth analysis of how multi-tier deployment altitudes and variations in LoS link probabilities influence handover and coverage probabilities. Utilizing stochastic geometry, we consider two association strategies: distance-based and strongest average received signal strength (RSS)-based. For both strategies, we provide semi-closed form expressions for handover probability and subsequently derive network coverage probabilities. Through numerical simulations, we not only unearth an optimal configuration of UAV density and deployment altitude that maximizes coverage probability for ground users, but also uncover that the relative benefits of the RSS-based association strategy wane as UAV density escalates compared to the distance-based association strategy. Furthermore, our results underscore the potential for enhancing coverage performance by adopting a strategy of deploying UAVs at various altitudes, contrasting with the traditional approach of uniform altitude deployment.

As a key technology of 5G, network function virtualization enables each monolithic service to be divided into microservices, facilitating their deployment and management in edge environments. One of the most critical issues in 5G is how to support dynamically arriving mission-critical services with low-latency and high-reliability requirements in distributed edge environments. However, most existing works focus on how to provide reliable services without considering latency, and their heuristics struggle to cope with high-dimensional constraints and complex environments with heterogeneous infrastructure and services. In this paper, we propose a SafeDRL algorithm to resource-efficiently support these dynamically arriving services while meeting their reliability and latency requirements. Specifically, we first formulate the problem as an integer nonlinear programming and prove its NP-hardness. To tackle this problem, our SafeDRL algorithm captures delayed rewards in dynamic environments by reinforcement learning, and corrects constraint violations with high-quality feasible solutions based on expert intervention, and prunes unnecessary backup instances for optimality. The algorithm is proved to have a bounded approximation ratio in general cases. Extensive trace-driven simulations show that, compared with the state-of-the-art solution, SafeDRL can save resource costs by up to 49.32% and improve the service acceptance ratio by up to 55% with acceptable execution time.

Lightweight and layered structure containers in serverless edge computing (SEC) provide flexible service configurations and computing for vehicles with diverse service requests in the Vehicle-Infrastructure Collaboration (VIC) environment. Despite progress in service request scheduling for the VIC system, the effect of layer sharing between different service images on request scheduling has not been fully explored. Additionally, the cold-start latency of service containers in SEC can significantly degrade the responsiveness of vehicle services, and container retention is proposed to minimize its impact and improve overall system performance. However, the existing research neglects the complex coupling relationship between request scheduling and container retention decisions, while focusing on the single decision optimization problem. Consequently, minimizing system costs by single decision optimization may not achieve the effect of joint decision optimization. To bridge this gap, we study the joint service request scheduling and container retention problem based on layer sharing and container caching. First, we model the joint decision problem with specific constraints and aim to minimize the long-term system cost while considering vehicle mobility. Second, an online co-decision scheme called Onco is proposed to solve the problem, which incorporates request scheduling and container retention for multiple vehicle services. Finally, both synthetic and real trace-driven simulation experiments have been conducted to evaluate the performance of Onco. The experimental results show that Onco outperforms state-of-the-art baselines in terms of system cost reduction and response time improvement.

The Metaverse is recognized as the next-generation Internet that provides immersive interaction experiences for users. Convolutional neural networks (CNNs) play a crucial role in providing strong immersive experiences in the Metaverse. However, the Metaverse faces challenges in meeting the escalating demands for computing and storage resources due to the explosive growth of convolution tasks, resulting in severe performance degradation. To tackle these issues, coded distributed computing (CDC) is commonly employed. In this paper, we first propose an efficient and reliable mobile-assisted CDC framework to perform large-scale CNN training tasks for the Metaverse. In this framework, the various mobile devices act as workers contributing their resources to collaborate with each other to complete convolution operation tasks. Furthermore, we design a novel resilient, secure, and private coded convolution (RSPCC) scheme for the proposed framework. The RSPCC scheme achieves several significant performances. First, it substantially reduces computation latency compared to conventional convolution. Second, it efficiently mitigates an adverse impact of straggling workers returning results exceedingly slow. Third, we integrate a verifiable computing approach into the encoding/decoding process to check the correctness of the final computation results. Fourth, the PSPCC scheme considers the existence of colluding workers, providing information-theoretic privacy protection for input data. Finally, experimental results demonstrate that our proposed RSPCC scheme can significantly reduce execution time while ensuring the correctness of computation results within the CDC-based Metaverse framework.

The conventional file system provides a hierarchical namespace by structuring it as a directory tree. Tree-based namespace structure leads to inefficient file path walk and expensive namespace tree traversal, underutilizing ultra-low access latency and superior sequential performance provided by non-volatile memories (NVMs). This article proposes FlatFS+, an NVM file system that features a flat namespace architecture while providing a compatible hierarchical namespace view. FlatFS+ incorporates three novel techniques: the direct file path walk model, range-optimized B r tree, and compressed index key design with scan and write dual optimization, to fully exploit flat namespace to improve file system metadata performance on ultra-fast, byte-addressable NVMs. Evaluation results demonstrate that FlatFS+ achieves significant performance improvements for metadata-intensive benchmarks and real-world applications compared to other file systems.

Deep video compression has attracted more and more attention in recent years. Previous works rely on feature space operations, which may cause the offset maps overflow degrading reconstructed frame quality. In this work, we propose a flow- guided module to guide the offset maps learning explicitly and alleviate offset maps overflow. Moreover, we introduce a context scheme to explore the temporal prior and fuse the hyper prior model to improve the compression ratio. For coding speed, we drop the time-consuming auto regressive module. Experimental results demonstrate that our method out-performs the previous learning-based schemes and traditional codecs. Compared to x265 with medium preset, our approach brings average 38.53% and 54.67% bit rate savings in PSNR and MS-SSIM metrics, respectively.

Lightweight containers in serverless-based vehicular edge computing (SVEC) offer flexible service provisioning for edge service providers (ESPs), enabling quick response to various service requests from mobile vehicles and improving the quality of service delivery. However, the unpredictability of vehicle mobility and the variability of service requests pose significant challenges to service placement for ESPs. Moreover, the cold-start latency experienced by service containers in SVEC can greatly hinder the responsiveness of vehicle services. To mitigate this impact and enhance the overall system performance, container retention is introduced as a solution. In this paper, we study the joint service placement and container retention problem in the dynamic SVEC system. First, we model the joint decision problem with specific constraints and aim to maximize the profit of each edge considering vehicle mobility. Second, an online co-decision scheme called CMU-O is proposed to solve the problem, which adopts an improved upper confidence bound method based on dynamic osmotic pressure (UCB-OP). Finally, the experimental results demonstrate that the service request success rate of the CMU-O is on average 7% higher than the baselines. Furthermore, the profits obtained under the CMU-O are also on average 23% higher than the baselines.

The use of unmanned aerial vehicles (UAVs) as base stations (BSs) is a promising solution to enhance the performance of the cellular networks. This architecture enables greater mobility for BSs, which affects both communication distance and the probability of line-of-sight (LoS) and non-line-of-sight (NLoS) links in air-to-ground channels. Consequently, handovers occur frequently, impacting communication performance. However, the analytical impact of LoS and NLoS links on handover probability in mobile UAV networks remains unknown. In this paper, we employ the random geometry theory to comprehensively investigate the impact of LoS link probability on handover while considering two association strategies based on the nearest-distance and the strongest average received signal strength. We present exact expressions for handover probability in semi-closed form under these two scenarios. Our proposed analytical results enable the exploration into how UAV-BSs density, the deployment height, and the adopted association strategy affect the handover probability.

In vehicular networks, handover can occur due to frequent changes in communication link status and transmission distance caused by the mobility of vehicles. Although handover is necessary for maintaining stable communication performance, it may cause interruptions in computing services within the distributed vehicular system. Recent literature has analysed the impact of blockage and mobility on handover performance. However, these works often assume that blockage probability during vehicle movement follows an independent distribution for ease of derivation. This assumption ignores some obstacles that can consecutively affect the blockage probability of the communication link during movement, leading to an inaccurate evaluation of the handover performance. To address this issue, this paper constructs a vehicular network scenario based on a spatially correlated blockage model where roadside obstacles and vehicle movement trajectories can jointly affect the communication link status between vehicles and roadside units. Using this model, we characterize the correlation between blockage probabilities during movement and theoretically derive a closedform expression for handover probability. Simulation results verify the accuracy of the analytical results while also revealing how factors such as vehicle speed, roadside unit density, blockage length affect handover performance.

Edge servers, which are located in close proximity to mobile users, have become emerging components for computation offloading in multiple Internet of Things (IoT) applications. As the edge resources are limited and shared among multiple mobile users, it is crucial for the users to choose appropriate edge server for task offloading, so that their cumulative utility can be maximized. Reinforcement learning (RL) algorithms, which are sequential and model-free, have been widely considered. However, it is still a critical challenge to coordinate the mobile users in a decentralized way. In this work, we propose a novel framework of Multiagent RL by learning to coordinate. The main idea is to introduce an additional “virtual” agent at the edge, which learns to broadcast public messages to the mobile users at each interval. We then enforce positive correlation between each user’s offloading policy and the message. The underlying intuition is that the message can contain information of edge resources and other users’ policies. Therefore, it is expected that the decentralized users can make coordinated decisions. Theoretical analysis shows that our algorithm can converge to equilibrium points under certain mild assumptions. In the experiments, our approach outperforms other baselines significantly in different scenarios. In addition, the results show that the broadcast message plays a very important role in coordinating the mobile users.

The software-defined network (SDN) enabled mobile edge network greatly facilitates network resource management and promotes many emerging applications. However, user mobility may cause the SDN controller to set flow rules frequently, introduce additional flow setup latency, cause delay jitter, and undermine latency-sensitive services. Proactive flow setup is an effective way to eliminate flow setup latency, but existing work fails to maximize the flow setup hit ratio, a metric for evaluating the quality of proactive flow setup decisions, which is critical for latency-sensitive services. In this paper, we study how to proactively set flow rules to maximize the flow setup hit ratio under limited available network resources to eliminate the flow setup latency as much as possible. Then, we formalize the proactive flow setup problem as two integer linear programming problems under two typical routing strategies, default routing and dynamic routing. Both problems are proved to be NP-hard. To tackle these two problems, we propose a linear programming-based polynomial-time approximation algorithm for the default routing case and a greedy-based heuristic algorithm for the dynamic routing case. Extensive trace-driven experimental and simulation results verify that our algorithms can improve the flow setup hit ratio by up to 30.99% compared to existing solutions.

We consider the multiuser detection (MUD) problem, i.e., how to separate and decode colliding data streams, in the uplink of massive Machine Type Communications (mMTC) at millimeter wave (mmWave). Operating on factor-graphs by passing messages, the sum-product algorithm and its variants are widely applied in many other scenarios. However, in this paper, we find that their performance in mMTC at mmWave could be dramatically degraded due to the ill-conditioned MUD channel gain matrix and the existence of enormous short cycles in their corresponding factor-graphs, which are caused by the limited scattering of mmWave and the sharing of a same codebook for error correction among densely located user equipments. Assuming LDPC codes are used for error correction, we further propose a novel sum-product based approach to dealing with the MUD problem in mMTC at mmWave. It first leverages the propagation characteristics of mmWave to optimize the factor-graph for MUD by removing short cycles based on node-split and node-contraction, and then takes a dynamic-programming based method to approximate the messages passing on the resulted factor-graph, which can achieve a higher decoding accuracy. Extensive simulation results show that our approach outperforms the state-of-the-art sum-product based approaches significantly.

As a key enabling technology for 5G, network function virtualization abstracts services into software-based service function chains (SFCs), facilitating mission-critical services with high-reliability requirements. However, it is challenging to cost-effectively provide reliable SFCs in dynamic environments due to delayed rewards caused by future SFC requests, limited infrastructure resources, and heterogeneity in hardware and software reliability. Although deep reinforcement learning (DRL) can effectively capture delayed rewards in dynamic environments, its trial-and-error exploration in a vast solution space with massive infeasible solutions may lead to frequent constraint violations and traps in poor local optima. To address these challenges, we propose a RuleDRL algorithm that combines the capability of DRL to capture delayed rewards and the strength of rule-based schemes to explore high-quality solutions without violating constraints. Specifically, we first formulate the reliable SFC provision problem as an integer nonlinear programming problem, which is proven to be NP-hard. Then, we jointly design DRL and rule-based schemes that are coupled to make the final decision and establish a bounded approximation ratio in general cases. Extensive trace-driven simulations show that RuleDRL can save the total cost by up to 65.67% and improve the SFC acceptance ratio by up to 82%, compared to the state-of-the-art solution.

Distributed gradient descent has been widely adopted in the machine learning field because considerable computing resources are available when facing the huge volume of data. Specifically, the gradient over the whole data is cooperatively computed by multiple workers. However, its performance can be severely affected by slow workers, namely stragglers. Recently, coding-based approaches have been introduced to mitigate the straggler problem, but they could hardly deal with the heterogeneity among workers. Besides, they always discard the results of stragglers causing huge resource waste. In this article, we first investigate how to tolerate stragglers by discarding their results and then seek to leverage the stragglers. For tolerating stragglers, we propose a heterogeneity-aware coding scheme that encodes gradients adaptive to the computing capability of workers. Theoretically, this scheme is optimal for stragglers tolerance. Relying on the scheme, we further propose an algorithm called DHeter-aware to exploit the gradients of stragglers which we called delayed gradients. Moreover, theoretical results characterized for DHeter-aware exhibits the same convergence rate as the gradient descent without delayed gradients. Experiments on various tasks and clusters demonstrate that our coding scheme outperforms all the state-of-the-art methods and the DHeter-aware further accelerates the coding scheme by achieving 25 percent time savings.

The design of optical buffers for packet contention resolution has been recognized as a key issue in all-optical packet switching. One of the most general buffering schemes is priority queues, which includes first-in first-out (FIFO) queues and last-in first-out (LIFO) queues as special cases. In a priority queue, each packet is associated with a unique priority upon its arrival, the packet with thehighestpriority is sent out from the queue whenever there is a departure request and there are packets in the queue, and the packet with thelowestpriority is dumped from the queue whenever there is a buffer overflow. In this paper, we consider the constructions of optical priority queues by using a feedback system consisting of an optical (bufferless) crossbar switch and multiple optical FIFO multiplexers with delay one (FM1’s) in the feedback path for buffering packets and feeding packets back to the switch. Such a feedback system is a generalization of that used in one of the authors’ earlier attempt for the constructions of optical priority queues in Tanget al.(2020). We fix theno-bufferingproblem in Tanget al.(2020) by using optical FM1’s to replace the optical FIFO multiplexers (FM’s) in Tanget al.(2020), which enables us to successfully achieve an exact emulation of a priority queue. We improve the utilization of buffering capacity over that in Tanget al.(2020) by routing packets to the optical FM1’s according to theirbuffering tagsinstead of theirtagsas used in Tanget al.(2020). We also extend and generalize the construction in Tanget al.(2020) and obtain a much larger class of constructions of optical priority queues. Our constructions are made possible by showing that the highest-priority (resp., lowest-priority) packet is always available at the input links of the switch whenever it needs to be routed to the departure (resp., loss) link, and by showing that there is no collision and there is no buffer overflow at any FM1 at any time so that there is no internal packet loss at any time. Our complexity analysis shows that by using a feedback system consisting of an optical$(M+2) \times (M+2)$(bufferless) crossbar switch and$M$fiber delay lines, we can achieve a buffer size of$2^{O(\sqrt {\alpha M})}$, where$\alpha $is a constant that depends on the parameters used in our constructions. Furthermore, we show that the best buffer size that we can achieve is$2^{O(\sqrt {4M/15})}$. Our result (exponential in$\sqrt {M}$) substantially improves on the best known result (polynomial in$M$) in the literature. Our numerical results show that the construction complexity of our constructions is lower than that of the construction in Tanget al.(2020), and the actual saving, in terms of the number of$2\times 2$switches needed, by our constructions could be quite significant even in the tiny-buffer and small-buffer regimes.

Federated Learning (FL) is a promising machine learning paradigm to cooperatively train a global model with highly distributed data located on mobile devices. Aiming to optimize the communication efficiency for gradient aggregation and model synchronization among large-scale devices, we propose a relay-assisted FL framework. By breaking the traditional transmission-order constraint and exploiting the broadcast characteristic of relay nodes, we design a novel synchronization scheme named Partial Synchronization Parallel (PSP), in which models and gradients are transmitted simultaneously and aggregated at relay nodes, resulting in traffic reduction. We prove that PSP has the same convergence rate as the sequential synchronization approaches via rigorous analysis. To further accelerate the training process, we integrate PSP with any unbiased and error-bounded compression technologies and prove that the convergence properties of the resulting scheme still hold. Extensive experiments are conducted in a distributed cluster environment with real-world datasets and the results demonstrate that our proposed approach reduces the training time up to 37 percent compared to state-of-the-art methods.

Distributed computing is the mainstream for large-scale machine learning and big data analytics, but its performance usually suffers from unpredictable stragglers, i.e., very slow nodes. Recently, coded computing has emerged as a new distributed computing paradigm that uses coding-theoretical approaches to mitigate the effect of stragglers. Most existing coding schemes only use the results from a certain number of fastest worker nodes to recover the output and completely ignore the partial work done by other worker nodes, leading to inferior performance. In this paper, for scenarios where each worker node transmits its local result to the master node only after it has finished the whole local computation, we introduce communication at full speed to characterize the full utilization of all the communication links between each worker node that has finished its local computation and the master node, and for scenarios where each worker node computes out the local result piece by piece and can forward each piece once available, we introduce computation at full speed to characterize the full utilization of the work done entirely or partially by all the worker nodes. Considering a general polynomial-based coding framework which encapsulates many advanced coding schemes for a variety of fundamental computing tasks, we propose a randomized approach where each worker node partitions its local result into pieces, generates and forwards random linear combinations of these pieces to the master node sequentially, and theoretically demonstrate that it can lead the coding framework to achieve communication at full speed. For some typical task scenarios, we further show that computation at full speed can be achieved by mapping the encoding operations in the randomized approach into a part of encoding on the input dataset. Experiments conducted on Alibaba Cloud as well as simulations show that our approaches can reduce the total runtime significantly.

MapReduce is a commonly used framework for parallel processing of data-intensive tasks, but its performance usually suffers from heavy communication load incurred by the shuffling of intermediate values (IVs) among computing servers. Recently, the Coded MapReduce framework is proposed which uses a coding scheme named coded distributed computing (CDC) to trade the communication load with extra computation in MapReduce. CDC can achieve the optimal computation-communication tradeoff when all the IVs have the same size. However, in many practical applications, the sizes of IVs can vary over a large range, leading to inferior performance. In this paper, we introduce a generalized CDC scheme which takes the sizes of IVs into account and then propose a combinatorial optimization problem aiming to minimize the communication load when the computation load is fixed. We show that the problem is NP-hard, and further propose a very efficient algorithm which achieves an approximation ratio of 2. Experiments conducted on Alibaba Cloud show that, compared to the original CDC scheme, our proposed IV size aware approach can significantly reduce the communication load and achieve a lower total execution time.

The emerging applications, e.g., virtual reality, online games, and Internet of Vehicles, have computation-intensive and latency-sensitive requirements. Mobile edge computing (MEC) is a powerful paradigm that significantly improves the quality of service (QoS) of these applications by offloading computation and deploying services at the network edge. Existing works on service placement in MEC usually ignore the impact of the different requirements of QoS among service providers (SPs), which is common in many applications such that online game requires extremely low latency and online video requires extremely large bandwidth. Considering the competitive relationship among SPs, we propose an auction-based resource allocation mechanism. We formulate the problem as a social welfare maximization problem to maximize effectiveness of allocated resources while maintaining economic robustness. According to our theoretical analysis, this problem is NP-hard, and thus it is practically impossible to derive the optimal solution. To tackle this, we design multiple rounds of iterative auctions mechanism (MRIAM), which divides resources into blocks and allocates them through multiple rounds of auctions. Finally, we conduct extensive experiments and demonstrate that our auction-based mechanism is effective in resource allocation and robust in economics.

Federated learning is a very promising machine learning paradigm where a large number of clients cooperatively train a global model using their respective local data. In this paper, we consider the application of federated learning in wireless networks featuring uplink multiuser multiple-input and multiple-output (MU-MIMO), and aim at optimizing the communication efficiency during the aggregation of client-side updates by exploiting the inherent superposition of radio frequency (RF) signals. We propose a novel approach named Physical-Layer Arithmetic (PhyArith), where the clients encode their local updates into aligned digital sequences which are converted into RF signals for sending to the server simultaneously, and the server directly recovers the exact summation of these updates as required from the superimposed RF signal by employing a customized sum-product algorithm. PhyArith is compatible with commodity devices due to the use of full digital operation in both the client-side encoding and the server-side decoding processes, and can also be integrated with other updates compression based acceleration techniques. Simulation results show that PhyArith further improves the communication efficiency by 1.5 to 3 times for training LeNet-5, compared with solutions only applying updates compression.

Caching popular videos at mobile edge servers (MESs) has been confirmed as a promising method to improve mobile users (MUs) perceived quality of experience (QoE) and to alleviate the server load. However, with the multiple bitrate encoding techniques prevalently employed in modern streaming services, caching deployment is challenging for the following three facts: (1) cooperative caching should be explored for MUs located at overlapped coverage areas of MESs; (2) there exists tradeoff consideration for caching either high bitrate videos or high diversity videos; and (3) the relationship between MU perceived QoE and MU received bitrate, known as QoE function, varies in different services. Aiming to maximize the MU perceived QoE, we formulate the multiple bitrate video caching problem, and prove this problem is NP-hard for any given positive and strictly increasing QoE function. We then propose a polynomial complexity algorithm based on a general QoE function, which can achieve an approximate ratio arbitrarily close to 1/2. Specifically, for a linear QoE function, we explore useful property of optimal solutions, based on which more efficient algorithms are proposed. We demonstrate the effectiveness of our solutions via both theoretical analysis and extensive simulations.

All-optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical buffers for packet contention resolution. One of the most general buffering schemes is optical priority queue, where every packet is associated with a unique priority upon its arrival and departs the queue in order of priority, and the packet with the lowest priority is always dropped when a new packet arrives but the buffer is full. In this paper, we focus on the feedback construction of an optical priority queue with a single (M + 2) × (M + 2) optical crossbar Switch and M fiber Delay Lines (SDL) connecting M inputs and M outputs of the switch. We propose a novel construction of an optical priority queue with buffer 2Θ(√M), which improves substantially over all previous constructions that only have buffers of O(Mc) size for constant integer c. The key ideas behind our construction include (i) the use of first in first out multiplexers, which admit efficient SDL constructions, for feeding back packets to the switch instead of fiber delay lines, and (ii) the use of a routing policy that is similar to self-routing, where each packet entering the switch is routed to some multiplexer mainly determined by the current ranking of its priority.

Supply chain management (SCM) is fundamental for gaining financial, environmental and social benefits in the supply chain industry. However, traditional SCM mechanisms usually suffer from a wide scope of issues such as lack of information sharing, long delays for data retrieval, and unreliability in product tracing. Recent advances in blockchain technology show great potential to tackle these issues due to its salient features including immutability, transparency, and decentralization. Although there are some proof-of-concept studies and surveys on blockchain-based SCM from the perspective of logistics, the underlying technical challenges are not clearly identified. In this paper, we provide a comprehensive analysis of potential opportunities, new requirements, and principles of designing blockchain-based SCM systems. We summarize and discuss four crucial technical challenges in terms of scalability, throughput, access control, data retrieval and review the promising solutions. Finally, a case study of designing blockchain-based food traceability system is reported to provide more insights on how to tackle these technical challenges in practice.

Gradient descent algorithms are widely used in machine learning. In order to deal with huge volume of data, we consider the implementation of gradient descent algorithms in a distributed computing setting where multiple workers compute the gradient over some partial data and the master node aggregates their results to obtain the gradient over the whole data. However, its performance can be severely affected by straggler workers. Recently, some coding-based approaches are introduced to mitigate the straggler problem, but they are efficient only when the workers are homogeneous, i.e., having the same computation capabilities. In this paper, we consider that the workers are heterogenous which are common in modern distributed systems. We propose a novel heterogeneity-aware gradient coding scheme which can not only tolerate a predetermined number of stragglers but also fully utilize the computation capabilities of heterogenous workers. We show that this scheme is optimal when the computation capabilities of workers are estimated accurately. A variant of this scheme is further proposed to improve the performance when the estimations of the computation capabilities are not so accurate. We conduct our schemes for gradient descent based image classification on QingCloud clusters. Evaluation results show that our schemes can reduce the whole computation time by up to 3× compared with a state-of-the-art coding scheme.

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization problems, which are called adaptive recoding, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern follows a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity property, we show that there always exists a preferred solution which not only can make the number of recoded packets almost deterministic but can also tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into one with the above desired properties.

In conventional 802.11, MAC protocol data units (MPDUs) that a receiver fails to decode will be simply discarded even when only a very few bits are corrupted. This makes conventional 802.11 hardly work when the channel fading or the interference is very severe. In this paper, we propose Rateless802.11, a novel scheme that is fully compatible with common commodity 802.11 devices, which can be used as a complement of 802.11 used in terrible channels. By concatenating LT codes with 802.11 convolutional codes, Rateless802.11 can introduce redundancy properly without the need of accurate channel status estimation, and exploit the uncorrupted bits of MPDUs adequately. To improve the decoding performance as well as reducing the decoding delay, we introduce an integrated decoder (IntBP) in Rateless802.11, which decodes convolutional codes and LT codes compactly and can be performed in an incremental manner. Evaluations based on numerical simulation and driven by universal software radio peripheral (USRP) captured real trace show that IntBP can dramatically improve decoding reliability compared with natural serial decoding approaches and compared with state-of-the-art solutions, throughput of 802.11 in terrible channels can be improved many times by Rateless802.11.

Remote Direct Memory Access (RDMA) technique allows the messaging service that directly access the memory on remote machines, which provides low CPU overhead, low latency, and high throughput network transmission. On the other hand, however, due to the limited cache space in RDMA NIC (RNIC), it is still challenging to achieve effective and fair resource sharing across different applications. To address this problem, we present a scalable RDMA as a service to manage resource and deliver fair scheduling to applications' requests. We study the thread contention and preemptive schedule issues at end-hosts, and report the corresponding performance degradation through experiments. Then, we introduce Avatar, a model to manage memory and Queue Pairs (QPs) resource for a large number of connections, which eliminates the lock contention and provides fair data scheduling for applications with different priorities. Finally, we implement Avatar and demonstrate that Avatar can support a thousand of connections, improve the fairness and reduce the requests completion time up to 50% in comparison with the native RDMA.

Modern datacenter networks employ Load-balancing (LB) in the large-scale multi-tier topology to ensure high network utilization as well as low flow completion time. This paper presents the design and evaluation of Nem, a robust Erasure Coding (EC) based load balancing scheme at end-host to spread data across multiple paths. Our design is based on two key insights. First, both theory and implementation have shown that redundancy is a powerful technique to reduce latency in networked system. Second, the commercial RDMA network interface card supports EC offload which can dramatically reduce the CPU consumption. Nem is an optimal user-level LB design, which leveraging redundant fine-grained data blocks and high speed lossless RDMA network to realize effective load balancing transmission. Evaluation over many workloads shows that Nem is adaptive to the asymmetric networks, and achieves better performance compared to the state-of-art host-based load balancing mechanism.

Efficient communication through a multi-hop network with packet loss requires random linear network coding schemes with low computation cost and high throughput. In this paper, we propose a low-density parity-check (LDPC)-based framework for constructing chunked code, a variation of random linear network code with low encoding/decoding computational cost and small coefficient vector overhead. Two classes of chunked codes with LDPC structures, named uniform LDPC-chunked codes and overlapped LDPC-chunked (OLC) codes, are studied under a general chunk transfer matrix model. ULC codes achieve rates close to the optimum and perform better than existing chunked codes that employ parity-check constraints. OLC codes are overlapped chunked codes, where it is not necessary to generate new packets for encoding, and demonstrate much higher rates in certain scenarios than the state-of-the-art designs of overlapped chunked codes. These results justifies the feasibility of this LDPC approach for communication through multi-hop networks with packet loss.

Opportunistic routing (OR) is a promising technology to enhance the throughput of wireless networks, which can be implemented in a distributed manner using random linear network coding (RLNC). To reduce the computational cost incurred by RLNC, most previous approaches partition the input packets into disjoint small chunks, apply RLNC within each chunk, and guarantee the decoding reliability by a feedback mechanism. However, a feedback mechanism can incur much transmission overhead, reducing the network performance significantly. Recently, chunked network codes (CC) are proposed to eliminate the requirement of feedback, where a linear block code is applied on the input packets before partitioning the packets into chunks. While several classes of CC can achieve a close-to-optimal encoding/decoding performance, the whole transmission performance depends on how the chunks are transmitted in the absence of feedback, which is little investigated in OR-based wireless networks. In this paper, we propose a simple chunk transmission scheme for CC in a common OR-based wireless network, which does not require any node coordination during the transmission and keep the buffer of the relay node stable. We further optimize the performance of the transmission scheme via linear programming, and demonstrate that our scheme performs near-optimally via extensive numerical evaluations.

Auction is a promising approach for dynamic spectrum access in cognitive radio networks. Existing auction mechanisms are mainly strategy-proof to stimulate bidders to reveal their valuations of spectrum truthfully. However, they can suffer significantly from a new cheating pattern, named false-name bids, where a bidder can manipulate the auction by submitting bids under multiple fictitious names. We show such false-name bid cheating is easy to make but difficult to detect in dynamic spectrum auctions. To address this issue, we propose ALETHEIA, a novel flexible, false-name-proof auction framework for large-scale dynamic spectrum access. ALETHEIA not only guarantees strategy-proofness but also resists false-name bids. Moreover, ALETHEIA enables spectrum reuse across a large number of bidders, to improve spectrum utilization. Following that, we extend ALETHEIA to its general version that supports more practical and flexible auction, where bidders accept the spectrum allocation under their partial satisfactions. Theoretical analysis and simulation results show that ALETHEIA achieves both high spectrum redistribution efficiency and auction efficiency.

Overlapped chunked (network) codes are variations of random linear network codes with low computational cost and small coefficient vector overhead, where the source node groups the input packets into chunks with overlapping and the intermediate network nodes only apply linear network coding among packets belonging to the same chunk. In this paper, we introduce a repetition Tanner graph representation of overlapped chunked codes and propose a random design of overlapped chunked codes, called the Repetition Tanner graph based Overlapped Chunked (ROC) codes. We analyze the performance of ROC codes under a general chunk transfer matrix model and demonstrate that ROC codes can achieve higher rates than the state-of-the-art overlapped chunked codes.

Optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical queues by using optical crossbar switches and fiber delay lines (SDLs). In this paper, we focus on the construction of an optical priority queue with a single (M+2)×(M+2) crossbar switch and M fiber delay lines, and evaluate it in terms of the buffer size of the priority queue. Currently, the best known upper bound of the buffer size is O(2M), while existing methods can only construct a priority queue with buffer O(M3). In this paper, we make a great step towards closing the above huge gap. We propose a very efficient construction of priority queues with buffer 2Θ(√M). We use 4-to-1 multiplexers with different buffer sizes, which can be constructed efficiently with SDL, as intermediate building blocks to simplify the design. The key idea in our construction is to route each packet entering the switch to some group of four 4-to-1 multiplexers according to its current priority, which is shown to be collision-free.

As a variation of random linear network coding, segmented network coding (SNC) has attracted great interest in data dissemination over lossy networks due to its low computational cost. In order to guarantee the success of decoding, SNC can adopt a feedbackless forward error correction (FEC) approach by applying a linear block code to the input packets before segmentation at the source node. In particular, if the empirical rank distribution of transfer matrices of segments is known in advance, several classes of coded SNC can achieve close-to-optimal decoding performance. However, the empirical rank distribution in the absence of feedback has been little investigated yet, making the whole performance of the FEC approach unknown. To close this gap, in this paper, we present the first comprehensive study on the transmission scheduling issue for the FEC approach, aiming at optimizing the rank distribution of transfer matrices with little control overhead. We propose an efficient adaptive scheduling framework for coded SNC in lossy unicast networks. This framework is one-sided (i.e., each network node forwards the segments adaptively only according to its own state) and scalable (i.e., its buffer cost will not keep on growing when the number of input packets goes to infinity). The performance of the framework is further optimized based on a linear programming approach. Extensive numerical results show that our framework performs near-optimally with respect to the empirical rank distribution.

Recently, device-to-device (D2D) communications have been leveraged to offload the traffic on cellular networks. In this paper, we focus on the content distribution problem over a hybrid cellular and local D2D network where mobile devices cooperatively download a same content. We assume that the transmissions over D2D communications are scheduled in a centralized fashion so as to achieve a high transmission efficiency. Aiming at minimizing the content download time, we formulate the minimum content download time (MinCD) problem as an integer linear programming problem, and show its hardness and inapproximability. For the case that only a single channel is available for D2D communications, we propose an asymptotically optimal algorithm. For the multi-channel case, we further propose a heuristic algorithm with low time complexity and demonstrate its efficiency via extensive simulations.

The paradigm of cloud computing has spontaneously prompted a wide interest in auction-based mechanisms for cloud resource allocation. To eliminate market manipulation, a number of strategy-proof (a.k.a. Truthful) cloud auction mechanisms have been recently proposed by enforcing bidders to bid their true valuations of the cloud resources. However, as discovered in this paper, they would suffer from a new cheating pattern, named false-name bids, where a bidder can gain profit by submitting bids under multiple fictitious names (e.g, Multiple e-mail addresses). Such false-name cheating is easy to make but hard to detect in cloud auctions. To tackle this issue, we propose FAITH, a new False-name-proof Auction for virtual machine instance allocation, that is proven both strategy-proof and false-name proof by our theoretical analysis. When N users compete for M different types of computing instances with multiple units, FAITH achieves a lower time complexity of O(N log N+NM) compared to exiting cloud auction designs. We further extend FAITH to support range-based requests as desired in practice for flexible auction. Through extensive simulation experiments, we show that FAITH highly improves auction efficiency, outperforming the extended mechanisms of conventional false-name-proof auctions in terms of generated revenue and social welfare by up to 220% and 140%, respectively.

The ever-increasing demands on mobile streaming over smartphones make the cellular networks always occupied by heavy load under traditional base-station-to-device (B2D) based streaming architecture, and even degrade the quality of service (QoS) seriously. To offload the traffic of cellular networks and provide scalable mobile streaming services with guaranteed QoS, in this paper we propose a device-to-device (D2D) communication motivated cooperative streaming framework by exploiting the capacity of both WiFi interface and cellular interface equipped with smartphones. Specifically, under the energy constraint of individual smartphone, we develop technique to minimize the over traffic of the cellular network by efficiently disseminating video over the D2D network with multi-hop routing supported. We formulate such an energy-aware cost-effective video dissemination problem as an integer linear programming problem, and show it to be NP-hard and even hard to approximate. We further present an energy allocation based algorithm and a simulated annealing heuristic algorithm which provide a trade-off between the performance and complexity to support the dissemination scheduling of cooperative mobile streaming. We evaluate the performance effectiveness of our proposal via both theoretical analysis and extensive simulation.

Auction is a promising approach for dynamic spectrum access in Cognitive Radio Networks. Existing auction mechanisms are mainly proposed to be strategy-proof to stimulate bidders to reveal their valuations of spectrum truthfully. However, they would suffer significantly from a new cheating pattern named false-name bids, where a bidder can manipulate the auction by submitting bids under multiple fictitious names. We show such false-name bid cheating is easy to make but hard to be detected in dynamic spectrum auctions. To resolve this issue, we propose ALETHEIA, a novel flexible, false-name-proof auction framework for large-scale dynamic spectrum access. ALETHEIA has the following important features: (1) it not only guarantees strategy-proofness but also resists false-name bids, (2) it enables spectrum reuse across a large number of bidders, (3) it provides the bidders the flexibility of diverse demand formats, and (4) it incurs low computational overhead. Simulation results show that ALETHEIA achieves both high spectrum redistribution efficiency and auction efficiency.

Chunked network code is a variation of random linear network code with low computational cost and small coefficient vector overhead. In a chunked network code, intermediate network nodes only apply network coding among packets of the same chunk. In this paper, we propose an approach to construct chunks using LDPC codes. For a given LDPC code, the chunks are simply formed by first partitioning the variable nodes into disjoint groups and then filling each group with a number of variable nodes of degree zero. The chunked network codes constructed using this approach are called L-chunked codes. We analyze the asymptotic achievable rates of L-chunked codes using belief propagation decoding for an arbitrary rank distribution of the chunk transfer matrices. Numerical evaluation shows that L-chunked codes achieve a rate very close to optimal.

We consider the problem of broadcasting a message in a mobile ad hoc network (MANET) with the objective of minimizing the broadcast latency. Due to the mobility of network nodes, the coordination among nodes is hard and expensive. Thus it is much desired to design efficient, one-sided broadcast protocols where each node acts according to its own state solely. Although random scheduling is a popular and effective one-sided approach for leveraging the broadcast nature of wireless medium while coping with transmission collisions, both critical for reducing the broadcast latency, in this paper, we show that when nodes move very fast, the performance of pure random scheduling must be sub-optimal, no matter how the forwarding probabilities are specified. Furthermore, we propose a novel one-sided broadcast protocol named R2, which first splits the message into a certain number of mini-messages and then couples a fine-grained random scheduling with random linear network coding for broadcasting the mini-messages. Theoretical analyses demonstrate that R$^2$ performs optimally in order sense, no matter how fast network nodes move around, although different mobility has distinct effect on the speed of message broadcast.

Motivated by various applications in mobile ad-hoc networks (MANETs) that require nodes to share their individual information to each other, we study the multi-message dissemination problem in a MANET, which is to distribute multiple messages to all mobile nodes in the network in parallel. The objective is to minimize the stopping time, i.e., the time taking for all nodes to receive a copy of the whole messages. We consider an intrinsically one-sided protocol based on random linear network coding (RLNC), where all packets forwarded are in the form of random linear combinations of packets received so far. Its supreme performance is demonstrated theoretically for two cases, low mobility and high mobility, according to the node velocity. In particular, we show that, under general settings, our derived upper bounds of the stopping time match the established lower bound in both cases, although the effects of mobility in the two cases are significantly different. Thus, we conclude that RLNC achieves order optimality for fast information dissemination in MANETs.

In recent years, OFDMA relay networks have become a key component in the 4G standards (e.g., IEEE 802.16j, 3GPP LTE-Advanced) for broadband wireless access. When numerous bidirectional flows pass through the relay stations in an OFDMA relay network that supports various interactive applications, plenty of network coding opportunities arise and can be leveraged to enhance the throughput. In this paper, we study the proportional-fair scheduling problem in the presence of network coding in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two models, global approach (GA) and local approach (LA), under which the corresponding problems are shown both NP-hard. For the GA model, we show that it cannot be approximated within some constant factor. Hence, we propose a heuristic algorithm with low time complexity. For the LA model, we propose a theoretical polynomial time approximation scheme (PTAS), and also present a practical greedy algorithm with approximation factor of 1/2. Simulation results show that our algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.

Chunked codes are a variation of random linear network codes with low computational complexities. In chunked codes, the packets in a file are grouped into small (non-overlapped or overlapped) chunks, and random linear encoding operations are performed within each chunk. Previous studies show that when the chunk size is lower bounded by some increasing function of the file length, chunked codes asymptotically achieve the min-cut capacity. However, in most real applications, the chunk size is required to be a small constant due to the computational constraints of network devices. In this case, it remains unknown which rates can be achieved by chunked codes. In this paper, we address the analysis and design of chunked codes with fixed constant chunk sizes. We first highlight the importance of precoding for chunked codes to achieve constant rates, and then present an analysis of non-overlapped chunked (NOC) codes with precoding. We further introduce a new class of chunked codes, called EOC codes, which are based on expander graphs to form overlapped chunks. Numerical and simulation results show that EOC codes achieve significantly higher rates than NOC codes, and also outperform other state-of-the-art overlapped chunked codes.

Broadcast is a fundamental operation in wireless ad hoc networks (WANETs). To design efficient broadcast protocols, one of the most important concerns is to reduce broadcast redundancy. In conventional WANETs where nodes are always active, due to the broadcast nature of wireless medium, minimizing broadcast redundancy is equivalent to finding a Minimum Connected Dominating Set (MCDS). However, this is not true for uncoordinated duty-cycled WANETs, where each node periodically switches between active and sleep states, and can only hear messages when it is active. In this paper, we investigate the minimum redundancy broadcast problem in uncoordinated duty-cycled WANETs. We first show that by modifying the conventional CDS-based approaches properly, a constant-approximation broadcast algorithm (MCA) can be obtained. We then propose a hierarchical CDS-based algorithm (HCA), improving the best known approximation ratio from 20 to 13.67. Both algorithms are distributed, and with low time and message complexities. Simulation results show that our algorithms achieve about 5%-30% performance improvement over the state-of-the art scheme.

Network virtualization has emerged as a powerful way to fend off the current ossification of the Internet. A major challenge is virtual network mapping, which is to assign substrate resources to virtual networks (VNs) such that some predefined constraints are satisfied and substrate resources are utilized in an effective and efficient manner. Due to the NP-completeness of this problem, a variety of heuristic algorithms have been proposed. However, existing solutions rarely consider the inefficient utilization of bandwidth resources due to the network traffic fluctuation. In this paper, we study the opportunistic bandwidth sharing in a single physical link among multiple virtual links from different VNs. We formulate the problem of assigning time slots to dispensable sub-flows with constraints on the performance guarantee and the objective of minimizing the number of time slots used, as an optimization problem. Two heuristic algorithms HA-I and HA-II, which consider the problem from different perspectives, are presented. Extensive simulations are conducted to evaluate the effectiveness and efficiency of our algorithms.

Service composition is a useful technique to assemble light, independent services to meet the complicated and dynamic requirements. Previous research has addressed the quality-of-service (QoS) aware composition path selection problem. However, as the requests growing, the selected service composition path may violate the QoS requirements. In this case, more service replicas should be deployed on suitable nodes to improve the QoS. But which service component should be selected and where these service replicas should be deployed is a challenge. In this paper, we make a deep study on this service replication problem. We give a detailed description of service replication triggering time. And then, we propose LDCS (Longest Delay Service Component Selection) to select the bottle-neck service component by evaluating the real-time performance of all these components. Finally, we employ MACP (Maximum Available Capacity Path) algorithm to select a suitable node to deploy this service replica. Simulation results approve that our approach is effective and efficient.