As deep learning (DL) continues to advance, effective feature extraction from large-scale data remains crucial for enhancing model performance. To leverage the advantages of the frequency domain, such as concentrated signal energy, prominent data features, and rich detailed characteristics, this paper proposes a novel frequency-domain feature extraction method. However, existing frequency component selection algorithms often struggle to adapt to diverse tasks, tend to yield only locally optimal solutions, and require prolonged processing times. To overcome these limitations, we introduce the Adaptive Fast Frequency Selection (AFFS) algorithm, which seamlessly integrates a frequency component selection factor layer into DL models to identify globally optimal frequency combinations suited to various downstream tasks. We further analyze the relationship between selected frequency components and model performance, providing theoretical guarantees regarding optimality, robustness, and generalization error bounds. Moreover, a fast selection procedure is developed to exploit the empirically observed rapid convergence of the selection-factor ranking, significantly accelerating the selection process. Extensive experiments on five datasets, ten DL models, and two subsequent tasks demonstrate that AFFS achieves superior performance: even when the input data size is reduced to only 10% of the original frequency features, model classification accuracy improves by approximately 1%, while the early stopping mechanism shortens the selection process by about 80%.

Mobile crowd sensing (MCS) has emerged as a promising sensing paradigm with the widespread adoption of smartphones. However, one of the key bottlenecks in MCS lies in the high sensing cost imposed on mobile users. To alleviate this burden, sparse sensing strategies are often employed, where data is collected from a limited number of locations and the remaining data is inferred by exploiting spatio-temporal correlations. Compared with vector-based inference approaches, matrix completion techniques can better capture two-dimensional correlations in the sensing data, thereby achieving higher recovery accuracy. Nevertheless, their performance degrades significantly when the actual sensing rate is low. In this paper, we propose a novel matrix-reshaping strategy that is applied prior to matrix completion to enhance recovery performance under sparse observations. We provide a theoretical analysis demonstrating that the reshaping process reduces the number of measurements required for successful matrix recovery. To validate our approach, we conduct extensive experiments using traditional matrix completion algorithms, deep learning models, and tensor completion methods on six real-world datasets. The results show that, to achieve the same level of recovery accuracy, our reshaped matrices consistently reduce the measurement overhead compared to their original ones.

Tensor wheel (TW) decomposition has been successfully applied to low-rank tensor completion (LRTC) to recover missing pixels in hyperspectral images (HSIs). However, existing TW models ignore the low-rank information in the factor space and the nonlinear geometric structure of HSIs, resulting in unsatisfactory recovery accuracy. To address these limitations, we propose a tensor wheel completion with low-rank factor prior and adaptive graph regularizer (TW-FPAG) for HSI recovery. First, we discover and prove the rank relationship between the tensor unfoldings and TW ring factors. Leveraging this relationship, we impose the matrix nuclear norm on factors, thereby enhancing the ability of TW decomposition to describe the low-rankness of HSIs. Second, we preserve the geometric proximity information of HSIs by constructing the nearest neighbor graph for each ring factor and integrating this information into the TW decomposition using the graph Laplacian. Finally, we extensively evaluate the proposed TW-FPAG on the hyperspectral image, multispectral image (MSI), and hyperspectral video (HSV). The experimental results demonstrate the superiority of our TW-FPAG method, with significant performance improvements of 2.81 to 5.07 dB for HSIs under a 10% sampling ratio compared to the best-compared results.

Sparse network monitoring, a breakthrough technology for cost-effective network-wide monitoring, has garnered significant attention from researchers and network equipment providers. By measuring only a subset of paths and nodes, it leverages the network’s low-rank property to obtain comprehensive monitoring data. However, a previously unnoticed vulnerability called the"global diffusion vulnerability"poses a significant threat to sparse network monitoring. This vulnerability suggests that if a few measurement samples are tainted, the entire network monitoring data can become inaccurate, leading to potential network failures and adverse effects on routing and bandwidth allocation. This paper presents the first exploration of the"global diffusion vulnerability"to launch effective attacks on sparse network monitoring. Sparse monitoring often employs various imputation models to estimate unmeasured data and collects multiple perspectives of network-wide data over extended periods. The challenges in attacking sparse monitoring lie in designing perturbations that can impact all views of network-wide data over time, regardless of the specific imputation models, while remaining unobtrusive. To tackle these challenges, we propose ModelFreeUP, the first perturbation generation algorithm designed for sparse network monitoring. ModelFreeUP creates imputation model-free, universal, and unobtrusive perturbations that exert a significant influence on multiple perspectives of network-wide data over time. Our experiments demonstrate that ModelFreeUP effectively disrupts the sparse monitoring process, causing substantial deviations in the network-wide monitoring data at a relatively low attack cost. Furthermore, when the manipulated monitoring data is used for downstream routing tasks, it triggers 100% Maximum Link Utilization in the Abilene network, indicating network congestion or failure. By shedding light on these critical mismeasurement issues, our work emphasizes the need for robust countermeasures against adversarial attacks in the network monitoring domain.

High-quality remote sensing imagery plays a vital role in environmental monitoring and disaster management. However, transmitting these images is challenging due to the unstable signal-to-noise ratio (SNR) and bandwidth limitations encountered in remote communications. Semantic communication, particularly deep learning-based methods, offers a promising solution by jointly optimizing source and channel coding to achieve data compression and noise resilience. Nevertheless, existing methods struggle to cope with varying channel noise and bandwidth, leading to unsatisfactory image reconstruction quality. To address these challenges, we propose a satellite-ground compression and transmission system called Adaptive Residual Joint Source-Channel Coding (ARJSCC), which is based on Deep Joint Source-Channel Coding (DeepJSCC). The ARJSCC system compresses remote sensing images into semantic information and residuals to achieve low overhead transmission and high-quality reconstruction. ARJSCC utilizes an attention module to adjust the semantic preference of the model for different SNRs, and deploys a variance-based position mask module to flexibly vary the semantic length and further compress it. These designs enable ARJSCC to automatically adapt to varying noise and bandwidth conditions. Moreover, for the residual, we apply BPG to compress it to reduce the transmission cost and design the corresponding enhancement module to recover its details from the noise-affected compressed residual. We experimentally compare our ARJSCC with the recent DeepJSCC-based wireless image transmission models in low-resolution dataset and high-resolution remote dataset under multiple wireless channel environments. The experimental results show that ARJSCC can achieve high reconstruction quality exceeding 44dB, and outperform the competitors by 4-6db even under low SNR and bandwidth environments.

As deep learning-based website fingerprinting (WF) attacks become increasingly accurate, user privacy faces mounting risks. Existing defenses struggle with the discrete nature of packet direction sequences, rendering gradient-based optimization infeasible and leading to inefficient, heuristic-based perturbation solutions. We propose a novel defense framework that bridges this gap by introducing gradient---aligned offset vectors and a cosine similarity---based reward to evaluate and select perturbation candidates aligned with the gradient direction. We further design a parallel reward computation algorithm to improve efficiency and integrate it into GAPDiS, a universal perturbation generation method that combines gradient guidance with improved tabu search for global optimization. For practical deployment, GAPDiS supports both PT bridge and P4 switch implementations. Experiments on the AWF dataset show that GAPDiS reduces the classification accuracy of WF models from over 98% to below 7% with only 2.56% bandwidth overhead---achieving a 68.1% improvement over state-of-the-art methods.

Matrix completion is a method for imputing missing data, typically based on the assumption of a low-rank structure. However, in practice, various factors can obscure this structure, leading to a perceived high-rank nature. Recently, a few studies begin to address high-rank data completion, their methods rely on specific hypothesis distributions that are often impractical to validate in real-world scenarios. Therefore, in this paper, we tackle high-rank data completion without any hypothesis distribution. Firstly, we theoretically demonstrate that the Radial Basis Function (RBF) kernel feature mapping has the capability to transform general high-rank data into low-rank data in a higher-dimensional feature space. Secondly, combining with the adaptive row and column neighbor information, a novel graph-based high-rank matrix completion algorithm is developed. Thirdly, experiments on four real datasets across three domains demonstrate that the proposed method reduces reconstruction error by up to 63% compared to the second-best method at the same missing rate. Furthermore, to achieve similar accuracy, it requires up to 40% fewer samples. Our code is released at https://github.com/shiqinyeah/Graph-HRMC.git.

Time-Sensitive Networking (TSN) is a fundamental technology for enabling deterministic communication in industrial Internet applications. Existing TSN traffic scheduling research primarily focuses on optimizing the scheduling of timetriggered (TT) flows to ensure low-delay transmission for these periodic and time-sensitive flows. However, another critical class of traffic exists in TSN that has received little attention-eventtriggered (ET) flows, such as sensor exception alarms. Unlike TT flows, ET flows exhibit higher time sensitivity and demand rapid response to ensure system security. Despite their importance, ET flows have been largely overlooked in prior studies. A few works only have explored dynamically expanding scheduling windows or sharing time slots to accommodate ET flows. However, these approaches treat ET flows as isolated events, neglecting the causal relationships between them. This oversight results in inefficient and unreliable ET flow transmission. To address this limitation, we propose GP-TSN, an event-triggered traffic scheduling framework based on causal inference. Firstly, GP-TSN introduces a Spatio-Temporal Graph Attention-based Hawkes Process (SGATPP) to model and mine event relationships, enabling the inference of future ET flows. Secondly, GP-TSN employs a geometric abstraction-based scheduling strategy to allocate slots for the inferred ET flows, ensuring compliance with TT/ET flow constraints. Additionally, a slot recycling mechanism is incorporated to minimize resource waste. By leveraging the causal dependencies among ET flows, GP-TSN enhances scheduling efficiency and improves the reliability of ET flow transmission. Experiments across four datasets demonstrate that SGATPP achieves superior event inference accuracy (F1-score up to 62.25 %). Moreover, under the condition of ensuring the transmission performance of TT flows, GP-TSN increases the number of ET flows transmitted with the minimum end-to-end delay by 1.7 to 9.7 x.

Mobile crowd sensing (MCS) has become a new paradigm for environment sensing. However, the sensing data often face the challenge of missing values, which can impact the performance of subsequent tasks. Although some deep learning-based imputation methods perform well, they still struggle with insufficient training data due to high missing rate and long-term missing data. To address these challenges, we propose a Historical Data-based Diffusion Imputation (HDDI) method. Unlike existing deep learning-based imputation methods, we design a historical data supplement module to match and fuse historical data to supplement the training data. Additionally, we propose a diffusion imputation module that utilizes the supplement training data to achieve high-accuracy imputation even under high missing rate and long-term missing scenarios. We conduct extensive experiments on four public datasets, the results show that our HDDI outperforms baseline methods across four datasets. Particularly, when the data missing rate is 90%, HDDI improves accuracy by 25.15% compared to the best baseline method in the random missing scenario, and by 13.64% in the long-term missing scenario.

Large-scale tensor completion plays a crucial role in data analysis and anomaly detection, with Alternating Least Squares (ALS)-based CANDECOMP/PARAFAC(CP) decomposition being widely adopted due to its convergence properties and computational stability. However, when accelerating ALS computation on GPUs, load imbalance caused by data partitioning significantly affects efficiency. Due to the sparsity and heterogeneity of data, different thread blocks handle varying amounts of non-zero values, leading to suboptimal utilization of computational resources. Moreover, updating factor matrices in ALS involves frequent global memory accesses, where the latency is 100 times higher than that of shared memory. Efficient utilization of shared memory is therefore critical for improving computational performance. To address these challenges, we propose a GPU-optimized ALS framework that incorporates a heat conduction-based load balancing strategy and a shared memory acceleration mechanism. The load balancing strategy dynamically adjusts subtensor partitioning based on the distribution of non-zero values, ensuring balanced workload allocation across GPU resources. Meanwhile, the shared memory acceleration mechanism caches frequently accessed factor matrices and employs element-wise implicit computation, eliminating explicit intermediate matrix storage and thereby reducing memory overhead and global memory access latency. Based on this, a comparison was made with the other three methods on four data sets. While ensuring accuracy, the time and memory usage were greatly reduced, providing a practical solution for efficient tensor completion.

Detailed system operations are recorded in logs. To ensure system reliability, developers can detect system anomalies through log anomaly detection. Log parsing, which converts semi-structured log messages into structured data, is a crucial step in log anomaly detection and advanced program analysis and verification. Despite the availability of various log parsing tools, they generally suffer from low parsing accuracy and slow efficiency due to the ignorance of variable characteristics and the use of costly pairwise comparison methods. In this paper, we propose a TCMS framework to parse logs, consisting of two main technologies. First, by studying 16 public log datasets, we find that most log variable tokens are structured variable tokens. Based on this discovery, we propose a token conversion algorithm to improve parsing accuracy. This algorithm converts the changed parts in structured variable tokens into wildcards (‘$< *> $’), preventing these tokens from being directly identified as constant tokens. Second, to improve efficiency, we propose the LogMLCS algorithm, which intelligently constructs a graph to facilitate the extraction of common parts from multiple log messages at once, instead of using pairwise comparisons. Comprehensive experiments conducted on 16 log datasets reveal that our TCMS outperforms seven other parsing methods, achieving the highest parsing accuracy at the fastest speed. Furthermore, experimental results from running a log anomaly detection algorithm in conjunction with different log parsing methods demonstrate that TCMS significantly boosts detection accuracy. For instance, on the OpenStack dataset, our TCMS-facilitated log anomaly detection algorithm achieves a perfect F1-score, precision, and recall of 100% each, surpassing the best peer method by 32.2, 0.8, and 19.5 percentage points, respectively.

Sparse data gathering has become a promising solution for reducing measurement costs by leveraging the inherent sparsity of data. However, most existing approaches rely on low-dimensional models such as compressive sensing or matrix completion, which are limited in capturing complex high-dimensional structures. To overcome these limitations, we proposeTensorMon, a novel tensor-based sparse data gathering framework that introduces a cuboid sampling strategy to more effectively exploit multidimensional correlations. Unlike traditional entry-based or tube-based sampling, TensorMon introduces the innovative concept ofcuboid sampling. We further develop a lightweight sampling scheduling algorithm and a non-iterative inference algorithm to ensure efficient measurement planning and accurate reconstruction of unmeasured data. Theoretical analysis establishes a new performance bound for our sampling strategy, which is significantly lower than those in existing literature. To validate our theoretical findings, we conduct extensive experiments on four real-world datasets: two network monitoring datasets, a city-scale crowd flow dataset, and a road traffic speed dataset. Experimental results demonstrate that TensorMon achieves substantial reductions in measurement cost, delivers high inference accuracy, and ensures rapid data recovery, highlighting its effectiveness and practicality across diverse application scenarios.

Deep neural networks (DNNs) have made great breakthroughs and seen applications in many domains. However, the incomparable accuracy of DNNs is achieved with the cost of considerable memory consumption and high computational complexity, which restricts their deployment on conventional desktops and portable devices. To address this issue, low-rank factorization, which decomposes the neural network parameters into smaller sized matrices or tensors, has emerged as a promising technique for network compression. In this article, we propose leveraging the emerging tensor ring (TR) factorization to compress the neural network. We investigate the impact of both parameter tensor reshaping and TR decomposition (TRD) on the total number of compressed parameters. To achieve the maximal parameter compression, we propose an algorithm based on prime factorization that simultaneously identifies the optimal tensor reshaping and TRD. In addition, we discover that different execution orders of the core tensors result in varying computational complexities. To identify the optimal execution order, we construct a novel tree structure. Based on this structure, we propose a top-to-bottom splitting algorithm to schedule the execution of core tensors, thereby minimizing computational complexity. We have performed extensive experiments using three kinds of neural networks with three different datasets. The experimental results demonstrate that, compared with the three state-of-the-art algorithms for low-rank factorization, our algorithm can achieve better performance with much lower memory consumption and lower computational complexity.

Network distance measurement is crucial for evaluating network performance, attracting significant research attention. However, conducting measurements for the entire network is exceedingly expensive and time-consuming, making the reduction of network distance measurement costs a top priority. The tensor completion method efficiently reduces measurement costs by utilizing a small amount of measured data to estimate the entire network’s distance data. Unfortunately, current tensor completion methods still suffer from issues such as complex sample selection, high measurement overhead, slow recovery, and low inference accuracy. To address the aforementioned challenges, we present an online network-wide distance measurement scheme. In this approach, continuous distance data are structured into sliding-window-based tensors. Our method incorporates a lightweight sample selection algorithm with a lowest sampling bound and a rapid, accurate unmeasured data inference algorithm. We have conducted extensive experiments using four real network distance datasets and two citywide crowd flow datasets. The empirical evaluations demonstrate the effectiveness of our approach, particularly in reducing measurement costs and enhancing data recovery accuracy.

The surge in demand for latency-sensitive services has propelled network distance measurement to the forefront of networking research. Utilizing the low-rank structure of full network data, the tensor completion method can efficiently estimate network distance from partially sampled distance data measured from a small set of node pairs. However, its performance is affected by sampling algorithm limitations, including unreliability and high overhead in dynamic networks. To tackle these challenges, we propose tube-based sampling as an alternative to point-based sampling, utilizing a partition-based algorithm to incorporate randomness for improved reliability. Additionally, we introduce a Tube Length Identification Algorithm to dynamically adjust tube length based on network status, balancing scheduling overhead reduction with estimation accuracy. Experimental results on three real network distance datasets, compared against 13 baseline algorithms, demonstrate the high accuracy and low scheduling overhead of our approach.

Network traffic matrices often suffer from incompleteness and sparsity due to various factors, including network device policies and system limitations. The incompleteness can undermine the reliability and accuracy of network traffic monitoring services, negatively impacting downstream tasks such as network planning and fault diagnosis. Our focus is on network traffic data recovery, intending to infer missing traffic data from partial measurements accurately. Although tensor completion algorithms are quite effective in recovering traffic data, existing models often overlook cross-domain traffic relationships and fail to account for the order and distribution of traffic, leading to reduced recovery accuracy. To overcome these limitations, we propose a new contrastive tensor completion model that utilizes pairwise joint embedding. This model employs innovative techniques, including a cross-domain embedding module to avoid information homogeneity and enhance model expressiveness, a contrastive module to preserve the order and distribution of traffic volumes, and an injective interaction module to map entry embeddings into the numerical space, ensuring convergence and retaining the original numerical distribution. Experiments on three real-world network traffic datasets show that our model significantly reduces the error in missing traffic data recovery compared to other existing models while maintaining traffic order and distribution.

Log analysis, especially log anomaly detection, can help debug systems and analyze root causes to provide reliable services. Deep learning is a promising technology for log anomaly detection. However, deep learning methods need a large amount of training data, which is hard for a newly deployed system to collect sufficient logs. Transfer learning becomes a possible method to solve the problem that can apply the knowledge from a long-term deployed system (source) to a newly deployed system (target). Existing transfer learning methods focus on transferring the knowledge from a source system to a single target system within the same service, in which the source and the target belong to the same service (e.g. operating system, supercomputer, or distributed system). They achieve low performance when applied to multiple target and different services systems because of the obvious differences in log format, syntax, semantics, and component call between different services and the individual training of multiple models for each target system. To tackle the problems, we propose an unsupervised multi-target cross-service log anomaly detection method based on transfer learning and contrastive learning (LogMTC). LogMTC exploits contrastive learning to learn a single model on combined data from the source and multiple target systems, which can fit multiple target systems simultaneously and improve efficiency. LogMTC exploits a hypersphere loss and two contrastive losses to minimize the feature differences crossing different services. Our experiments on two services (supercomputer and distributed system) and three log datasets show that our method is superior to the existing transfer learning methods in the same service, cross-service, and multi-target log anomaly detection. Compared with the best peer accurate transfer learning algorithm LogTAD, LogMTC improves 1.14%-8.28$\%$F1 score in multi-target transfer and is 1.12-1.22 times faster.

Remote sensing imagery plays a crucial role in areas such as environmental monitoring and urban planning. However, due to fragile communication links, limited bandwidth and harsh wireless environments, transmitting data from remote locations to ground applications faces the dilemma of high bit-error rates, which have a poor impact on downstream missions. Semantic communication is a feasible solution that transmits only the semantic features of the raw data extracted using neural networks. Although effective, existing semantic communication methods cannot cope with high compression rate requirements and complex communication environments. Therefore, in this paper, an effective image compression and transmission framework ASE-JSCC is proposed. To minimize the transmitted data, we design a semantic extraction module and an important feature selection module to efficiently extract, select, and compress critical semantic features required for downstream tasks. To improve the communication robustness of the model in complex environments affected by variable channels, we optimize the source-channel joint coding technique by randomly adding noise with different types and sizes. Finally, we deploy ASE-JSCC to the scene classification task of remote sensing images and conduct extensive experiments on four real datasets, achieving classification accuracy of 84.29%--88.62% under 384 times compression ratio, verifying the excellent performance of the proposed framework.

Accurately detecting traffic anomalies becomes increasingly crucial in network management. Algorithms that model the traffic data as a matrix suffers from low detection accuracy, while the work using the tensor model often assumes the tensor is regular without considering that network nodes may dynamically join in or leave, which will fail in a practical network with the change of node set as a result of mobility and churn behaviors. We propose a novel Tensor Recovery scheme in a Dynamic Network (TRDN) with traffic data modeled as a practical irregular tensor for accurate anomaly detection. To take advantage of correlations among small tensors, each formed with a short time duration to capture more hidden information in the data for higher detection accuracy, we propose several novel techniques: 1) a new joint tensor factorization model to capture the characteristic shared by the common nodes of small tensors, 2) a tensor partition algorithm to identify the data that can be applied to train the shared parameters efficiently, and 3) a bar-based algorithm that partitions nodes into the minimum number of no-overlapping subsets to form the shared tensor model. Extensive experiments on two Internet traffic data sets, Abilene and GÈANT, demonstrate the effectiveness of the proposed TRDN.

Deep learning has made remarkable progress across many domains, enabled by the capabilities of over-parameterized neural networks with increasing complexity. However, practical applications often necessitate compact and efficient networks because of device constraints. Among recent low-rank decomposition-based neural network compression techniques, Tucker decomposition has emerged as a promising method which effectively compresses the network while preserving the high-order structure and information of the parameters. Despite its promise, designing an efficient Tucker decomposition approach for compressing neural networks while maintaining accuracy is challenging, due to the complexity of setting ranks across multiple layers and the need for extensive fine-tuning. This paper introduces a novel accuracy-aware network compression problem under Tucker decomposition, which considers both network accuracy and compression performance in terms of parameter size. To address this problem, we propose an efficient alternating optimization algorithm that iteratively solves a network training sub-problem and a Tucker decomposition sub-problem to compress the network with performance assurance. The proper Tucker ranks of multiple layers are selected during network training, enabling efficient compression without extensive fine-tuning. We conduct extensive experiments, implementing image classification on five neural networks using four benchmark datasets. The experimental results demonstrate that, without the need for extensive fine-tuning, our proposed method significantly reduces the model size with minimal loss in accuracy, outperforming baseline methods.

Tensor data is widely used in fields such as smart grids, cloud systems, and deep learning. As the scale of this data increases, storage and transmission costs rise significantly. Many tensor data exhibit low-rank structures, offering the potential for data compression through low-rank decomposition techniques. Tucker decomposition, a typical low-rank decomposition technique, achieves data compression and interpretability by capturing complex data correlations and representing the original tensor with a compact core tensor and factor matrices. However, the compression ratio provided by Tucker decomposition is often insufficient, particularly for large-scale tensors. To tackle this issue, we propose a robust low-rank tensor compression method that leverages Tucker decomposition with quantization and coding. Initially, we establish a robust Tucker decomposition framework that decomposes the low-rank tensor into a core tensor and factor matrices using well-designed Tucker rank-setting rules. This framework effectively handles noise and missing values. Subsequently, we conduct an in-depth analysis of the numerical characteristics of the core tensor and factor matrices within the Tucker decomposition framework. Based on their distinct characteristics, we design tailored quantization and coding schemes to compress the core tensor and factor matrices, respectively, thereby significantly improving the compression ratio of Tucker decomposition while maintaining high accu-racy. Through extensive experiments on four publicly available datasets (which can form 3 or 4 order tensors), we demonstrate that our approach can achieve compression ratios$4\times-10\times$higher than the best competitor, with recovery errors improved by 8% - 42%.

Network telemetry, characterized by its efficient push model and high-performance communication protocol (gRPC), offers a new avenue for collecting fine-grained real-time data. Despite its advantages, existing network telemetry systems lack a theoretical basis for setting measurement frequency, struggle to capture informative samples, and face challenges in setting a uniform frequency for multi-metric monitoring. We introduce FineMon, an innovative adaptive network telemetry scheme for precise, fine-grained, multi-metric data monitoring. FineMon leverages a novel Two-sided Frequency Adjustment (TFA) to dynamically adjust the measurement frequency on the Network Management System (NMS) and infrastructure sides. On the NMS side, we provide a theoretical basis for frequency determination, drawing on changes in the rank of multi-metric data to minimize monitoring overhead. On the infrastructure side, we adjust the frequency in real-time to capture significant data fluctuations. We propose a robust Enhanced-Subspace-based Tensor Completion (ESTC) to ensure accurate recovery of fine-grained data, even with noise or outliers. Through extensive experimentation with three real datasets, we demonstrate FineMon's superiority over existing schemes in reduced measurement overhead, enhanced accuracy, and effective capture of intricate temporal features.

Robust PCA is a popular anomaly detection technique and has been widely used in many applications. Although Robust PCA is promising, it is usually designed in a two-order matrix form, which is inferior to the tensor that can capture multilinearity features of data. Moreover, the detection accuracy under Robust PCA further suffers due to its sensitivity to the rank parameter which is hard to set in practice and the limitation of PCA method in capturing the non-linear feature in the data. To address the issues, we propose a Robust Tensor Convolutional Autoencoder (RTCAE) where the autoencoder instead of SVD is exploited to recover the normal data from the corrupted measurement tensor data. However, directly exploiting deep autoencoder may suffer from the problem of high memory consumption and computation overhead due to the large number of parameters used in autoencoder. To make our anomaly detection lightweight, we further design a Light Convolutional Autoencoder (LightCAE) which contains a compressed autoencoder by exploiting tensor factorization to largely compress the parameters while significantly reducing the computation complexity. We conduct extensive experiments on three real data traces to compare the performance of our proposed schemes (RTCAE and lightCAE) with that of seven baseline algorithms. The experiment results demonstrate that our proposed RTCAE achieves the highest anomaly detection accuracy. Moreover, our LightCAE requires over 60 times smaller memory storage than that required in RTCAE while achieving the similar anomaly detection accuracy.

Packet level measurement in the data plane provides a microscopic view of the network’s state. Although advances in programmable switches and routers make it possible to measure the Sequence of Packet Lengths and Arrival Times (SPLT) in the data plane, collecting this information remains challenging due to limited storage, processing resources, and bandwidth. To address this issue, we propose MES, which Measures and Encodes Simultaneously the packet length and timestamp when each packet passes through the Network Processor (NP) in the switch/router. We design the packet length compression and timestamp compression algorithms to be lightweight and implement the designed algorithms using simple operations supported by the network processor, while taking into account the computation constraints of the NP. Through extensive experiments on five packet traces, we demonstrate that our MES achieves high precision SPLT measurements (up to 99.82% cosine similarity) while reducing storage and bandwidth overhead by up to 87%. Simulations conducted on the BMV2 P4 software switch demonstrate that our designed SPLT measurement mechanism imposes little impact on network throughput and delay.

In network distance measurement, how to estimate the whole network distance data from partially observed samples has attracted lots of attention because of its significance for network performance evaluation. Matrix completion becomes the most effective approach. However, the two-dimension matrix can only capture the spatial features in the network distance data while ignoring the temporal features. To conquer the problem, few recent studies begin to model the network distance data as a three-dimension tensor and propose tensor completion approaches for distance estimation. Although promising, existing tensor completion approaches still suffer the problem of low recovery accuracy and high measurement cost because they ignore the history priority information. To fully utilize both spatial and temporal features hidden in the distance data, this paper formulates a novel History Priority Enhanced Tensor Completion (HPETC) for distance estimation as a weighted tensor nuclear norm minimization problem where the weight is defined based on the history subspaces information. To solve the weighted tensor nuclear norm minimization problem, we firstly transform it into a factorization-based Frobenius norm minimization problem to avoid costly T-SVD computations, and then propose an iterative algorithm to solve the transformed problem. We further derive a theoretical sampling bound that is lower than the existing sampling bound, thus leads a lower measurement cost. We demonstrate the effectiveness of the proposed algorithm by conducting extensive experiments using two real network distance datasets. The result shows that the proposed algorithm can not only improve the estimation accuracy but also reduce the sampling complexity compared to the state-of-the-art approaches.

Accurately identifying IoT device types is crucial for IoT security and resource management. However, existing traffic-based device identification algorithms incur high measurement, storage, and computation costs, as they continuously need to capture, store, and parse device traffic. To overcome these challenges, we propose an innovative framework that employs a discontinuous traffic measurement strategy, reducing the number of packets captured, stored, and parsed. To ensure accurate identification, we introduce several novel techniques. First, we propose a graph neural network-based tensor completion model to estimate missing traffic features in unmeasured time slots. Our model can utilize historical information to flexibly and efficiently estimate missing features. Second, we propose a convolutional neural network-based classifier for device identification. The classifier utilizes traffic features and node embeddings learned from the tensor completion model to achieve precise device identification. Through extensive experiments on real IoT traffic traces, we demonstrate that our framework achieves high accuracy while significantly reducing costs. For instance, by capturing only 30% of the packets, our framework can identify devices with a high accuracy of 0.9558. Moreover, compared to current tensor completion methods, our method can estimate missing values with higher accuracy and achieve a 1.53-fold speedup over the next-fastest baseline.

The rapid expansion of the Internet of Things (IoT) has led to growing concerns about the security of IoT devices. A crucial aspect of ensuring their security is IoT device identification, which involves pinpointing the specific type of device. Existing solutions, however, either necessitate complex feature engineering or struggle to handle the ever-increasing number of new devices in open IoT environments. To tackle these challenges, this paper introduces GraphIoT, a lightweight IoT device detection method based on graph classifiers. GraphIoT leverages lightweight flow information, such as packet length, direction, and timestamp, to create an IoT Device Traffic Graph Representation (IoT-DTGR). This representation offers a comprehensive view of IoT device flows while preserving features in bidirectional IoT Device-Gateway interactions. By transforming the IoT device detection problem into a graph classification problem, GraphIoT employs a powerful Graph Neural Network that takes into account both node and edge features, as well as subgraph structures in IoT-DTGRs, to classify graphs and consequently identify device types. Additionally, the paper proposes an incremental learning framework called CL-GraphIoT that continuously learns features of new IoT device flows without forgetting previously learned device features. This is achieved through two strategies: parameter sharing and sample replaying. The paper gathers a real-world dataset from 18 IoT devices and conducts experiments on two datasets: the gathered real-world dataset and an open-source dataset covering 21 IoT device types. The experimental results demonstrate that both GraphIoT and CL-GraphIoT outperform state-of-the-art methods, achieving high accuracy in device detection with fast processing speed.

Traffic matrices (TMs) are essential for managing networks. Getting the whole TMs is difficult because of the high measurement cost. Several recent studies propose sparse measurement schemes to reduce the cost, which involve taking measurements on only a subset of origin and destination pairs (OD pairs) and inferring data for unmeasured OD pairs through matrix completion. However, existing sparse network measurement schemes suffer from the problems of high computation costs and low recovery quality. This paper investigates the coherence feature of real traffic flow data traces (Abilene and GÈANT). Both data sets are high coherence, with column coherence greater than row coherence. According to the coherence feature of both data sets, we propose our Redundant Row Subspace-based Matrix Completion (RRS-MC). RRS-MC involves several techniques. Firstly, we design an algorithm to identify subspace rows (OD pairs) from historical data. Secondly, based on the identified subspace rows, we design our sampling scheduling algorithm, which takes full measurement samples in subspace rows while taking partial measurement samples in the remaining rows. Moreover, we propose a redundant sampling rule prevent the recovery accuracy decrease caused by the subspace rows varying. Finally, we design a completion algorithm to recover the partially measured rows. We conduct extensive experiments. Results indicate that the proposed scheme is superior to the state-of-the-art sampling and completion scheme in computation costs and recovery accuracy.

Network trouble shooting, failure location, and anomaly detection rely heavily on network traffic measurement data. Due to the lack of measurement infrastructure, the high measurement cost, and the unavoidable transmission loss, network monitoring systems suffer from the problem that the network traffic data are incomplete. This article models the traffic data as a tensor to exploit its strong ability of feature extraction to recover the missing data. Different from traditional tensor completion which relies on tensor factorization, we design a novel Deep Adversarial Tensor Completion (DATC) scheme based on Deep Learning (DL) techniques. DATC is the first scheme that exploits the data reconstruction ability of autoencoder and the power of adversarial training from Generative Adversarial Networks to infer the missing data. Despite that DL techniques achieve great success in the image field, designing an algorithm based on DL techniques to recover the traffic data with missing entries faces additional challenges due to the skewed distribution and the sparsity of traffic data. To conquer these challenges, we propose the use of two techniques, adversarial training and missing data aware convolution. These techniques help DATC to learn the complex features of the traffic data and infer the missing data following the data distribution of traffic data. Our extensive experimental results using two public real-world network traffic datasets and running both offline and online demonstrate that DATC can achieve significantly better recovery accuracy while capturing the data distribution of the traffic data even when the sampling ratio is very low.

Detecting anomalous traffic is a crucial task for network management. Although many anomaly detection algorithms have been proposed recently, constrained by their matrix-based traffic data model, existing algorithms often suffer from low detection accuracy. To fully utilize the multi-dimensional information hidden in the traffic data, this paper uses the tensor model for more accurate Internet anomaly detection. Only considering the low-rank linearity features hidden in the data, current tensor factorization techniques would result in low anomaly detection accuracy. We propose a novel Graph-based Tensor Recovery model (Graph-TR) to well explore both low-rank linearity features as well as the non-linear proximity information hidden in the traffic data for better anomaly detection. We encode the non-linear proximity information of the traffic data by constructing nearest neighbor graphs and incorporate this information into the tensor factorization using the graph Laplacian. Moreover, to facilitate the quick building of neighbor graph, we propose a nearest neighbor searching algorithm with the simple locality-sensitive hashing (LSH). Besides only detecting random anomalies, our algorithm can also effectively detect structured anomalies that appear as bursts. We have conducted extensive experiments using Internet traffic trace data Abilene and GÈANT. Compared with the state of art algorithms on matrix-based anomaly detection and tensor recovery approach, our Graph-TR can achieve higher Accuracy and Recall.

Network measurements provide critical inputs for a wide range of network management. Existing network-wide monitoring methods face the challenge of incurring a high measurement cost. Some recent studies show that network-wide measurement data such as end-to-end latency and flow traffic, have hidden spatio-temporal correlations and thus low-rank features. Taking advantage of the low-rank feature, enlightened by tensor model's strong capability of information representation and extracting, this paper studies a novel sparse measurement scheduling problem which selects a proportion of Origin and Destination (OD) pairs to take measurements in the future time slots, while ensuring the data of the remaining un-measured OD pairs be accurately inferred through tensor completion. It is challenging to find the optimal sampling points (OD pairs) without knowing the structure of the future data and also infer the un-measured data in the presence of noise in the measurement samples. To conquer the challenges, we propose several techniques: a tripartite graph to illustrate the relationship between sample locations and tensor factorization, a graph-based sample selection algorithm, and a graph-based robust tensor completion algorithm. We have conducted extensive experiments based on two real network latency monitoring traces (PlanetLab and Harvard) and two other network monitoring traces (including a traffic trace Abilene and a throughput trace WS-Dream). Our results demonstrate that, even with a sampling ratio of less than 5%, our scheme can accurately obtain the complete network-wide monitoring data by inferring the missing ones based on the samples taken. To achieve similar recovery performance, the best peer tensor completion algorithm needs a significantly larger number of samples, with the sampling ratio up to 25-150 times ours.

Network traffic anomaly detection is critical for advanced network applications. However, network traffic monitoring data arrive in a streaming fashion and could be infinite, which makes the offline algorithms that attempt to store the entire stream monitoring data for analysis not scalable. To well utilize the strong ability of tensor model, we use a tensor to represent the prior non-anomalous traffic matrices and propose a novel unsupervised anomaly detection framework that can be used to detect anomalies in a streaming fashion by making only one pass over the data while utilizing limited storage. In the framework, we propose a succinct tensor sketch to maintain, in a streaming model, the subspace that can well represent all prior non-anomalous data detected. Using the subspace, anomalies in each new incoming traffic monitoring data can be quickly detected based on a simple outlier score calculation. Further, we prove that the tensor sketch is mergeable. Exploiting this property, we propose a distributed anomaly detection framework in which the distributed node only needs to upload its succinct tensor sketch instead of the raw monitoring data to the central node to calculate the global subspace of the whole network, which greatly saves the transmission cost. We theoretically prove that our tensor sketch based anomaly detection algorithm compares favorably with the offline approach which calculates the subspace based on expensive global Singular Value Decomposition (SVD). The experimental results demonstrate the effectiveness and efficiency of our approach over other popular online anomaly detection algorithms.

Network traffic engineering and anomaly detection rely heavily on network traffic measurement. Due to the lack of infrastructure to measure all points of interest, the high measurement cost, and the unavoidable transmission loss, network monitoring systems suffer from the problem that the network traffic data are incomplete with only a subset of paths or time slots measured. Recent studies show that tensor completion can be applied to infer the missing traffic data from partial measurements. Although promising, the interaction model adopted in current tensor completion algorithms can only capture linear and simple correlations in the traffic data, which compromises the recovery performance. To solve the problem, we propose a new tensor completion scheme based on Lightweight Trilinear Pooling, which designs (1) a Trilinear Pooling, a new multi-modal fusion method to model the interaction function to capture the complex correlations, (2) a low-rank decomposition based neural network compression method to reduce the storage and computation complexity, (3) an attention enhanced LSTM to encode and incorporate the temporal patterns in the tensor completion scheme. The extensive experiments on three real-world network traffic datasets demonstrate that our scheme can significantly reduce the error in missing data recovery with fast speed using small storage.

Recovery of missing network monitoring data is of great significance for network operation and maintenance tasks such as anomaly detection and traffic prediction. To exploit historical data for more accurate missing data recovery, some recent studies combine the data together as a tensor to learn more features. However, the need of performing high cost data decomposition compromises their speed and accuracy, which makes them difficult to track dynamic features from streaming monitoring data. To ensure fast and accurate recovery of network monitoring data, this paper proposes NMMF-Stream, a stream-processing scheme with a context extraction module and a generation module. To achieve fast feature extraction and missing data filling with a low sampling rate, we propose several novel techniques, including the context extraction based on both positive and negative monitoring data, context validation via measuring the Pointwise Mutual Information, GRU-based temporal feature learning and memorization, and a new composite loss function to guide the fast and accurate data filling. We have done extensive experiments using two real network traffic monitoring data sets and one network latency data set. The experimental results demonstrate that, compared with three baselines, NMMF-Stream can fill the newly arrived monitoring data very quickly with much higher accuracy.

Network-wide monitoring is important for many network functions. However, monitoring data are often incomplete due to the need of sampling to reduce high measurement cost, system failure, and unavoidable transmission loss under severe communication. Instead of only targeting to estimate all missing monitoring data entries with a small set of measurement samples, we study a new order-preserved monitoring data estimation problem to accurately estimate the missing data entries while preserving the data entries’ order in the dataset. We propose a novel order-preserved tensor completion model that integrates both the low rank property and the order information into a joint learning problem to estimate the missing data. With well designed non-convex function to directly approximate the tensor rank and order-preserved constraint under the linear self-recovery method, our model can not only more accurately capture the low-rank property of monitoring data to increase the estimation performance of missing data, but also can capture the order information in monitoring data to ensure the estimation accuracy. Extensive experiments using four real datasets demonstrate that compared with the state-of-the-art tensor completion algorithms, our proposed algorithm can provide more accurate estimation and keep the value order of recovered entries to more effectively retrieve top-k large entries.

Mobile crowdsensing (MCS) has become a new paradigm for the environment sensing. However, the sparse sensory data prevent the practical and large-scale deployment of MCS systems. Recent studies have demonstrated that the matrix factorization is an effective technique which can estimate the missing sensory data entries based on a small set of observed data entries. However, there could be multiple sensory data sets with each regarded as a different view on the environment. Applying current matrix factorization individually to each data set, the recovery performance will be low as some data sets do not have enough observed data entries thus enough information. By partitioning the parameters involved in matrix factorization, we design some novel regularizations to encode the similarities among different data sets and specific knowledge in the single data set. Based on the regularizations, we propose one basic multiview matrix factorization (MVMF) model and one neural MVMF (NMVMF) model to combine multiple sensory data sets to mutually reinforce the estimation of each single data set. The extensive experimental results demonstrate that, with the help of other data sets, our models can estimate the missing entries in the data set with a very low sampling ratio accurately while the other five baseline algorithms cannot.

Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.

In network-wide monitoring, finding the large monitoring data entries is a fundamental network management function. However, the retrieval of large entries is extremely difficult and challenging as a result of incompleteness of network measurement data. Enlightened by tensor model’s strong capability of information representation and extraction, we model the network-wide monitoring data as a 3-way tensor. With tensor completion, the retrieval can be performed after recovering all missing entries. However, this not only incurs an extremely high cost when the tensor is large, but is also unnecessary. Instead, to quickly retrieve large entries at low cost, we transform the large entry retrieving problem to a cosine similarity searching problem, and propose two algorithms: 1) Quickly reordering the factor vectors based on Locality Sensitive Hashing (LSH) hash table so that vectors with small cosine distances are placed in the same hash bucket; 2) Quickly finding the similar vector of a queried one that the two together determine a large entry without incurring the high cost of recovering all entries through the dot products. In the process of LSH table building and similarity query, several novel techniques are proposed, including LSH table representation with the LSH forest, good hash table building to support the flexible search of cosine similarity, and bit-shifting-based quick similarity query. Our experimental studies on 4 real world datasets indicate that our technique is at least up to 60 times faster than the approach based on direct tensor completion.

Time series forecasting is very important and plays critical roles in many applications. However, making accurate forecasting is a challenge task due to the requirements of learning complex temporal and spatial patterns and combating noise during the feature learning. To address the challenge issues, we propose TEGMNet, a Tensor projection Embedding and Gated Memory Network for multivariate time series forecasting. To more accurately extract local features and reduce the influence of noise, we propose to amplify the data using several data transformation techniques based on MDT (Multi-way delay embedding transform) and TFNN (tensor factorized neural network) to transform the original 2D matrix data to low dimensional 3D tensor data. The local features are then extracted through convolution and LSTM upon the 3D tensor. We also design a long-term feature extraction module based on the structure of gated memory network, which can largely enhance the longterm pattern feature learning ability when the multivariate time series has complex long-term dependencies with dynamic-period patterns. We have done extensive experiments by comparing our TEGMNet with 7 baseline algorithms using 4 real data sets. The experiment results demonstrate that TEGMNet can achieve very good prediction performance even through the data are polluted with noise.

Network-wide monitoring is important for many network functions. Due to the need of sampling to reduce high measurement cost, system failure, and unavoidable data transmission loss, network monitoring systems suffer from the incompleteness of network monitoring data. Different from the traditional network monitoring data estimation problem which aims to infer all missing monitoring data entries with incomplete measurement data, we study a challenging problem of inferring the top-$k$largest monitoring data entries. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top-$k$data entries. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top-$k$entry inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top-$k$largest entries with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. To quickly infer the top-$k$largest data entries when measurement data arrive sequentially, we also propose a sliding window based online algorithm using the discrete tensor completion model. Extensive experiments using five real data sets and one synthetic data set demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar top-$k$entry inference accuracy using significantly smaller time and storage space.

Monitoring the performance of a large network is very costly. Instead, a subset of paths or time intervals of the network can be measured while inferring the remaining network data by leveraging their spatiotemporal correlations. The quality of missing data recovery highly relies on the inference algorithms. Tensor completion has attracted some recent attentions with its capability of exploiting the multi-dimensional data structure for more accurate missing data inference. However, current tensor completion algorithms only model the three-order interaction of data features through the inner product, which is insufficient to capture the high-order, nonlinear correlations across different feature dimensions. In this paper, we propose a novel Neural Tensor Completion (NTC) scheme to effectively model three-order interaction among data features with the outer product and build a 3D interaction map. Based on which, we apply 3D convolution to learn features of high-order interaction from the local range to the global range. We demonstrate this will lead to good learning ability. We conduct extensive experiments on two real-world network monitoring datasets, Abilene and WS-DREAM, to demonstrate that NTC can significantly reduce the error in missing data recovery. When the sampling ratio is low at 1%, the recovery error ratios on the testing data are around 0.05 (Abilene) and 0.13 (WS-DREAM) when using NTC, but are 0.99 (Abilene) and 0.99 (WS-DREAM) using the best current tensor completion algorithms, which are 21 times and 8 times larger.

The attacks, faults, and severe communication/system conditions in Mobile Crowd Sensing (MCS) make false data detection a critical problem. Observing the intrinsic low dimensionality of general monitoring data and the sparsity of false data, false data detection can be performed based on the separation of normal data and anomalies. Although the existing separation algorithm based on Direct Robust Matrix Factorization (DRMF) is proven to be effective, requiring iteratively performing Singular Value Decomposition (SVD) for low-rank matrix approximation would result in a prohibitively high accumulated computation cost when the data matrix is large. In this work, we observe the quick false data location feature from our empirical study of DRMF, based on which we propose an intelligent Light weight Low Rank and False Matrix Separation algorithm (LightLRFMS) that can reuse the previous result of the matrix decomposition to deduce the one for the current iteration step. Depending on the type of data corruption, random or successive/mass, we design two versions of LightLRFMS. From a theoretical perspective, we validate that LightLRFMS only requires one round of SVD computation and thus has very low computation cost. We have done extensive experiments using a PM 2.5 air condition trace and a road traffic trace. Our results demonstrate that LightLRFMS can achieve very good false data detection performance with the same highest detection accuracy as DRMF but with up to 20 times faster speed thanks to its lower computation cost.

Gaining a full knowledge of end-to-end network performance is important for some advanced network management and services. Although it becomes increasingly critical, end-to-end network monitoring usually needs active probing of the path and the overhead will increase quadratically with the number of network nodes. To reduce the measurement overhead, matrix completion is proposed recently to predict the end-to-end network performance among all node pairs by only measuring a small set of paths. Despite its potential, applying matrix completion to recover the missing data suffers from low recovery accuracy and long recovery time. To address the issues, we propose MC-GPU to exploit Graphics Processing Units (GPUs) to enable parallel matrix factorization for high-speed and highly accurate Matrix Completion. To well exploit the special architecture features of GPUs for both task independent and data-independent parallel task execution, we propose several novel techniques: similar OD (origin and destination) pairs reordering taking advantage of the locality-sensitive hash (LSH) functions, balanced matrix partition, and parallel matrix completion. We implement the proposed MC-GPU on the GPU platform and evaluate the performance using real trace data. We compare the proposed MC-GPU with the state of the art matrix completion algorithms, and our results demonstrate that MC-GPU can achieve significantly faster speed with high data recovery accuracy.

Monitoring the performance of a large network would involve a high measurement cost. To reduce the overhead, sparse network monitoring techniques may be applied to select paths or time intervals to take the measurements, while the remaining monitoring data can be inferred leveraging the spatial-temporal correlations among data. The quality of missing data recovery, however, highly relies on the specific inference technique adopted. Tensor completion is a promising technique for more accurate missing data inference by exploiting the multi-dimensional data structure. However, data processing for higher dimensional tensors involves a large amount of computation, which prevents conventional tensor completion algorithms from practical application in the presence of large amount of data. This work takes the initiative to investigate the potential and methodologies of performing parallel processing for high-speed and high accuracy tensor completion over Graphics Processing Units (GPUs). We propose a GPU-accelerated parallel Tensor Completion scheme (GPU-TC) for accurate and fast recovery of missing data. To improve the data recovery accuracy and speed, we propose three novel techniques to well exploit the tensor factorization structure and the GPU features: grid-based tensor partition, independent task assignment based on Fisher-Yates shuffle, sphere facilitated and memory-correlated scheduling. We have conducted extensive experiments using network traffic trace data to compare the proposed GPU-TC with the state of art tensor completion algorithms and matrix-based algorithms. The experimental results demonstrate that GPU-TC can achieve significantly better performance in terms of two relative error ratio metrics and computation time.

Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms usually work off-line and cannot timely detect anomalies. They also suffer from high cost for storage and computation. Although online and accurate traffic anomaly detection is very important, it very difficult to achieve. We propose to utilize tensor model to well exploit the multi-dimensional information hidden in the traffic data for more accurate online Internet anomaly detection. We decouple the tensor recovery problem to iteratively solve two sub problems, a tensor factorization sub-problem and an anomaly detection sub-problem. To reduce the high cost for computation and storage involved in tensor factorization, we propose two lightweight techniques to effectively derive factor matrices of tensor in the current window and iteration, taking advantage of tensor decomposition results of the previous window and iteration. We have done extensive experiments using two real traffic traces to compare with three tensor based algorithms and three matrix based algorithms. The experiment results demonstrate that our online anomaly detection algorithm can achieve the same anomaly detection accuracy as that of the best offline tensor based algorithm, but at 6100 times faster speed and with very low storage cost.

With the proliferation of smartphones, a novel sensing paradigm called Mobile Crowd Sensing (MCS) has emerged very recently. However, the attacks and faults in MCS cause a serious false data problem. Observing the intrinsic low dimensionality of general monitoring data and the sparsity of false data, false data detection can be performed based on the separation of normal data and anomalies. Although the existing separation algorithm based on Direct Robust Matrix Factorization (DRMF) is proven to be effective, requiring iteratively performing Singular Value Decomposition (SVD) for low-rank matrix approximation would result in a prohibitively high accumulated computation cost when the data matrix is large. In this work, we observe the quick false data location feature from our empirical study of DRMF, based on which we propose an intelligent Light weight Low Rank and False Matrix Separation algorithm (LightLRFMS) that can reuse the previous result of the matrix decomposition to deduce the one for the current iteration step. Our algorithm can largely speed up the whole iteration process. From a theoretical perspective, we validate that LightLRFMS only requires one round of SVD computation and thus has very low computation cost. We have done extensive experiments using a PM 2.5 air condition trace and a road traffic trace. Our results demonstrate that LightLRFMS can achieve very good false data detection performance with the same highest detection accuracy as DRMF but with up to 10 times faster speed thanks to its lower computation cost.

Finding top- k elephant flows is a critical task in network measurement, with applications such as congestion control, anomaly detection, and traffic engineering. Traditional top- k flow detection problem focuses on using a small amount of memory to measure the total number of packets or bytes of each flow. Instead, we study a challenging problem of inferring the top- k elephant flows in a practical system with incomplete measurement data as a result of sub-sampling for scalability or data missing. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top- k elephant flows. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top- k flow inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top- k elephant flows with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. Extensive experiments using two real traces demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar data inference accuracy using significantly smaller time and storage space.

A major factor that prevents the large scale deployment of Mobile Crowd Sensing (MCS) is its sensing and communication cost. Given the spatio-temporal correlation among the environment monitoring data, matrix completion (MC) can be exploited to only monitor a small part of locations and time, and infer the remaining data. Rather than only taking random measurements following the basic MC theory, to further reduce the cost of MCS while ensuring the quality of missing data inference, we propose an Active Sparse MCS (AS-MCS) scheme which includes a bipartite-graph-based sensing scheduling scheme to actively determine the sampling positions in each upcoming time slot, and a bipartite-graph-based matrix completion algorithm to robustly and accurately recover the un-sampled data in the presence of sensing and communications errors. We also incorporate the sensing cost into the bipartite-graph to facilitate low cost sample selection and consider the incentives for MCS. We have conducted extensive performance studies using the data sets from the monitoring of PM 2.5 air condition and road traffic speed, respectively. Our results demonstrate that our AS-MCS scheme can recover the missing data at very high accuracy with the sampling ratio only around $11%$, while the peer matrix completion algorithms with similar recovery performance requires up to 4-9 times the number of samples of ours for both the data sets.

The inference of the network traffic data from partial measurements data becomes increasingly critical for various network engineering tasks. By exploiting the multi-dimensional data structure, tensor completion is a promising technique for more accurate missing data inference. However, existing tensor completion algorithms generally have the strong assumption that the tensor data have a global low-rank structure, and try to find a single and global model to fit the data of the whole tensor. In a practical network system, a subset of data may have stronger correlation. In this work, we propose a novel localized tensor completion model (LTC) to increase the data recovery accuracy by taking advantage of the stronger local correlation of data to form and recover sub-tensors each with a lower rank. Despite that it is promising to use local tensors, the finding of correlated entries faces two challenges, the data with adjacent indexes are not ones with higher correlation and it is difficult to find the similarity of data with missing tensor entries. To conquer the challenges, we propose several novel techniques: efficiently calculating the candidate anchor points based on locality-sensitive hash (LSH), building sub-tensors around properly selected anchor points, encoding factor matrices to facilitate the finding of similarity with missing entries, and similarity-aware local tensor completion and data fusion. We have done extensive experiments using real traffic traces. Our results demonstrate that LTC is very effective in increasing the tensor recovery accuracy without depending on specific tensor completion algorithms.

Offloading computation intensive applications to mobile cloud is promising for overcoming the problems of limited computational resources and energy of mobile devices. However, without considering the competition relationship of mobile users and cloudlets in the mobile cloud computing system, existing studies lack an incentive mechanism for the system to achieve efficient application offloading and cloud resource provisioning. In this paper, we design MPTMG, a Multi-dimensional Pricing mechanism based on Two-sided Market Game. We propose three types of prices: a multi-dimensional price corresponding to multi-dimensional resource allocation, a penalty price to encourage fair and high quality cloud services, and a benefit discount factor to motivate more even provisioning of resources on different dimensions in the cloud. Based on these prices, we propose a distributed price-adjustment algorithm for efficient resource allocation and QoS-aware offloading scheduling. We prove that the algorithm can converge in a finite number of iterations to the equilibrium core allocation at which the mobile cloud system achieves the Pareto efficiency by maximizing the total system benefit. To the best of our knowledge, this is the first paper that applies economic theories and pricing mechanisms to manage application offloading in mobile cloud systems. The simulation results demonstrate that our proposed pricing mechanism can significantly improve the system performance.

Ensuring transmission survivability is a crucial problem for high-speed networks. Path protection is a fast and capacity-efficient approach for increasing the availability of end to end connections. The emerging SDN infrastructure makes it feasible to provide diversity routing in a practical network. For more robust path protection, it is desirable to provide an alternative path that does not share any risk resource with the active path. We consider finding the SRLG-Disjoint paths, where a Shared Risk Link Group (SRLG) is a group of network links that share a common physical resource whose failure will cause the failure of all links of the group. Since the traffic is carried on the active path most of time, it is useful that the weight of the shorter path of the disjoint path pair is minimized, and we call it Min-Min SRLG-Disjoint routing problem. The key issue faced by SRLG-Disjoint routing is the trap problem, where the SRLG-disjoint backup path (BP) can not be found after an active path (AP) is decided. Based on the min-cut of the graph, we design an efficient algorithm that can take advantage of existing search results to quickly look for the SRLG-Disjoint path pair. Our performance studies demonstrate that our algorithm can outperform other approaches with a higher routing performance while also at a much faster speed.

Tensor completion can be applied to fill in the missing data, which is import for many data applications where the data are incomplete. To infer the missing data, existing tensor-completion algorithms generally assume that the tensor data have global low-rank structure and apply a single model to fit the overall observed data through the global optimization. However, there are different correlation levels among application data, thus the ranks of some sub-tensors can be even lower relative to that of the large tensor. Fitting a single model to all data will compromise the performance of data recovery. To increase the accuracy in missing data recovery, we propose to apply local tensor completion (Local-TC) to recover data from sub-tensors, with each containing data of higher correlations. Although promising, as the tensor data are only organized logically, it is difficult to determine the relationship among data. We propose to exploit locality-sensitive hash (LSH) to quickly find the data correlation and reorganize tensor data, based on which data entries with high correlations are put into the same sub-tensor. The experiment results demonstrate that Local-TC is very effective in increasing the recovery accuracy.

Detecting anomalous traffic is a crucial task of managing networks. Many anomaly detection algorithms have been proposed recently. However, constrained by their matrix-based traffic data model, existing algorithms often suffer from low detection accuracy. To fully utilize the multi-dimensional information hidden in the traffic data, this paper takes an initiative to investigate the potential and methodologies of performing tensor factorization for more accurate Internet anomaly detection. Only considering the low-rank linearity features hidden in the data, current tensor factorization techniques would result in low anomaly detection accuracy. We propose a novel Graph-based Tensor Recovery model (Graph-TR) to well explore both low rank linearity features as well as the non-linear proximity information hidden in the traffic data for better anomaly detection. We encode the non-linear proximity information of the traffic data by constructing nearest neighbor graphs and incorporate this information into the tensor factorization using the graph Laplacian. Moreover, to facilitate the quick building of neighbor graph, we propose a nearest neighbor searching algorithm with the simple locality-sensitive hashing (LSH). We have conducted extensive experiments using Internet traffic trace data Abilene and GEANT. Compared with the state of art algorithms on matrix-based anomaly detection and tensor recovery approach, our Graph-Trcan achieve significantly lower False Positive Rate and higher True Positive Rate.

Matrix completion has emerged very recently and provides a new venue for low cost data gathering in Wireless Sensor Networks (WSNs). Existing schemes often assume that the data matrix has a known and fixed low-rank, which is unlikely to hold in a practical system for environment monitoring. Environmental data vary in temporal and spatial domains. By analyzing a large set of weather data collected from 196 sensors in ZhuZhou, China, we reveal that weather data have the features of low-rank, temporal stability, and relative rank stability. Taking advantage of these features, we propose an on-line data gathering scheme based on matrix completion theory, named MC-Weather, to adaptively sample different locations according to environmental and weather conditions. To better schedule sampling process while satisfying the required reconstruction accuracy, we propose several novel techniques, including three sample learning principles, an adaptive sampling algorithm based on matrix completion, and a uniform time slot and cross sample model. With these techniques, our MC-Weather scheme can collect the sensory data at required accuracy while largely reducing the cost for sensing, communication, and computation. We perform extensive simulations based on the data traces from weather monitoring and the simulation results validate the efficiency and efficacy of the proposed scheme.

The inference of the network traffic matrix from partial measurement data becomes increasingly critical for various network engineering tasks, such as capacity planning, load balancing, path setup, network provisioning, anomaly detection, and failure recovery. The recent study shows it is promising to more accurately interpolate the missing data with a three-dimensional tensor as compared to interpolation methods based on two-dimensional matrix. Despite the potential, it is difficult to form a tensor with measurements taken at varying rate in a practical network. To address the issues, we propose Reshape-Align scheme to form the regular tensor with data from dynamic measurements, and introduce user-domain and temporal-domain factor matrices which takes full advantage of features from both domains to translate the matrix completion problem to the tensor completion problem based on CP decomposition for more accurate missing data recovery. Our performance results demonstrate that our Reshape-Align scheme can achieve significantly better performance in terms of two metrics: error ratio and mean absolute error (MAE).

Detecting anomalous traffic is a critical task for advanced Internet management. The traditional approaches based on Principal Component Analysis (PCA) are effective only when the corruption is caused by small additive i.i.d. Gaussian noise. The recent Direct Robust Matrix Factorization (DRMF) is proven to be more robust and accurate in anomaly detection, but it incurs a high computation cost due to its need of singular value decomposition (SVD) for low-rank matrix approximation and the iterative use of SVD execution to find the final solution. To enable the anomaly detection for large traffic matrix with the use of DRMF, we formulate the low-rank matrix approximation problem as a problem of searching for the subspace to project the traffic matrix with the minimum error. We propose a novel approach, LSH-subspace, for fast low-rank matrix approximation. To facilitate the matrix partition for the quick search of the subspace, we propose several novel techniques: a multi-layer locality sensitive hashing (LSH) table to reorder the OD pairs based on LSH function, a partition principle to guide the partition to minimize the projection error, and a lightweight algorithm to exploit the sparsity of the outlier matrix to update the LSH table at low overhead. Our extensive simulations based on real trace data demonstrate that our LSH-subspace is 3 times faster than DRMF with high anomaly detection accuracy.

Affected by hardware and wireless conditions in WSNs, raw sensory data usually have notable data loss and corruption. Existing studies mainly consider the interpolation of random missing data in the absence of the data corruption. There is also no strategy to handle the successive missing data. To address these problems, this paper proposes a novel approach based on matrix completion (MC) to recover the successive missing and corrupted data. By analyzing a large set of weather data collected from 196 sensors in Zhu Zhou, China, we verify that weather data have the features of low-rank, temporal stability, and spatial correlation. Moreover, from simulations on the real weather data, we also discover that successive data corruption not only seriously affects the accuracy of missing and corrupted data recovery but even pollutes the normal data when applying the matrix completion in a traditional way. Motivated by these observations, we propose a novel Principal Component Analysis (PCA)-based scheme to efficiently identify the existence of data corruption. We further propose a two-phase MC-based data recovery scheme, named MC-Two-Phase, which applies the matrix completion technique to fully exploit the inherent features of environmental data to recover the data matrix due to either data missing or corruption. Finally, the extensive simulations with real-world sensory data demonstrate that the proposed MC-Two-Phase approach can achieve very high recovery accuracy in the presence of successively missing and corrupted data.

Detecting anomalous traffic is a critical task for advanced Internet management. Many anomaly detection algorithms have been proposed recently. However, constrained by their matrix-based traffic data model, existing algorithms often suffer from low accuracy in anomaly detection. To fully utilize the multi-dimensional information hidden in the traffic data, this paper takes the initiative to investigate the potential and methodologies of performing tensor factorization for more accurate Internet anomaly detection. More specifically, we model the traffic data as a three-way tensor and formulate the anomaly detection problem as a robust tensor recovery problem with the constraints on the rank of the tensor and the cardinality of the anomaly set. These constraints, however, make the problem extremely hard to solve. Rather than resorting to the convex relaxation at the cost of low detection performance, we propose TensorDet to solve the problem directly and efficiently. To improve the anomaly detection accuracy and tensor factorization speed, TensorDet exploits the factorization structure with two novel techniques, sequential tensor truncation and two-phase anomaly detection. We have conducted extensive experiments using Internet traffic trace data Abilene and GÈANT. Compared with the state of art algorithms for tensor recovery and matrix-based anomaly detection, TensorDet can achieve significantly lower false positive rate and higher true positive rate. Particularly, benefiting from our well designed algorithm to reduce the computation cost of tensor factorization, the tensor factorization process in TensorDet is 5 (Abilene) and 13 (GÈANT) times faster than that of the traditional Tucker decomposition solution.

Vehicles equipped with various types of sensors can act as mobile sensors to monitor the road conditions. To speed up the information collection process, the monitoring data can be shared among vehicles upon their encounters to facilitate drivers to find a good route. The vehicular network experiences intermittent connectivity as a result of the mobility, which makes the inter-vehicle contact duration a scarce resource for data transmissions and the support of monitoring applications over vehicular networks a challenge. We propose a novel compressive sensing (CS)-based scheme to enable efficient decentralized context sharing in vehicular delay tolerant networks, called CS-Sharing. To greatly reduce the data transmission overhead and speed up the monitoring processing, CS-sharing exploits two techniques: sending an aggregate message in each vehicle encounter, and quick collection of information taking advantage of data sharing and the sparsity of events in vehicle networks to significantly reduce the number of measurements needed for global information recovery. We propose a novel data structure, and an aggregation method that can take advantage of the random and opportunistic vehicle encounters to form the measurement matrix. We prove that the measurement matrix satisfies the Restricted Isometry Property (RIP) property required by the CS technique. Our results from extensive simulations demonstrate that CS-Sharing allows vehicles in a large network to quickly obtain the full context data with the successful recovery ratio larger than 90%.

The inference of traffic volume of the whole network from partial traffic measurements becomes increasingly critical for various network engineering tasks, such as traffic prediction, network optimization, and anomaly detection. Previous studies indicate that the matrix completion is a possible solution for this problem. However, as a two-dimension matrix cannot sufficiently capture the spatial-temporal features of traffic data, these approaches fail to work when the data missing ratio is high. To fully exploit hidden spatial-temporal structures of the traffic data, this paper models the traffic data as a 3-way traffic tensor and formulates the traffic data recovery problem as a low-rank tensor completion problem. However, the high computation complexity incurred by the conventional tensor completion algorithms prevents its practical application for the traffic data recovery. To reduce the computation cost, we propose a novel Sequential Tensor Completion algorithm (STC) which can efficiently exploit the tensor decomposition result for the previous traffic data to deduce the tensor decomposition for the current data. To the best of our knowledge, we are the first to apply the tensor to model Internet traffic data to well exploit their hidden structures and propose a sequential tensor completion algorithm to significantly speed up the traffic data recovery process. We have done extensive simulations with the real traffic trace as the input. The simulation results demonstrate that our algorithm can achieve significantly better performance compared with the literature tensor and matrix completion algorithms even when the data missing ratio is high.

The popularity of smart phones fosters the growth of Proximity-based Mobile Social Networking (PMSN). Although some profile matching approaches have been proposed to facilitate a user to find another user that shares his/her interest in the proximity, these approaches usually model the matching problem as a Private Set Intersection problem or a Private Set Intersection Cardinality problem and require high complexity of computation. Different from current studies, to facilitate more effective building of PMSNs, we propose a novel similarity metric to evaluate the common interests of mobile users by considering the time-dependent features of their interests. To calculate the metric in a low cost and privacy- protection way, we propose a novel time-dependent bloom filter to encode the time-dependent interest and a novel probabilistic algorithm to estimate the time- dependent similarity metric based on the bloom filter. Based on the proposed BF-based profile matching approach, we further propose InterestMatch, a novel distributed mobile communication system to facilitate more efficient social networking among strangers in the physical proximity. We have done extensive experiments on real-world phones, our experiment results demonstrate that our approach is promising for facilitating mobile social interactions in the physical proximity due to its low complexity and consequently low power consumption.

There are a lot of recent interests on cooperative communication (CC) in wireless networks. Despite the large capacity gain of CC in small wireless networks with its capability of mitigating fading taking advantage of spatial diversity, cooperative communication can result in severe interference in large networks and even degraded throughput. The aim of this work is to concurrently exploit multi-radio and multi-channel (MRMC) technique and cooperative transmission technique to combat co-channel interference and improve the performance of multi-hop wireless network. Our proposed solution concurrently considers cooperative routing, channel assignment, and relay selection and takes advantage of both MRMC technique and spatial diversity in cooperative wireless networks to improve the throughput. We propose two important metrics, contention-aware channel utilization routing metric (CACU) to capture the interference cost from both direct transmission and cooperative transmission, and traffic aware channel condition metric (TACC) to evaluate the channel load condition. Based on these metrics, we propose three algorithms for interference-aware cooperative routing, local channel adjustment, and local path and relay adaptation respectively to ensure high performance communications in dynamic wireless networks. Our algorithms are designed to be fully distributed and can effectively mitigate co-channel interference and achieve cooperative diversity gain. To our best knowledge, this is the first distributed solution that supports cooperative communications in MRMC networks. Our performance studies demonstrate that our proposed algorithms can efficiently support cooperative communications in multi-radio multi-hop networks to significantly increase the aggregate throughput.

Cooperative communication (CC) for wireless networks has gained a lot of recent interests. It has been shown that CC has the potential to significantly increase the capacity of wireless networks, with its ability of mitigating fading by exploiting spatial diversity. However, most of the works on CC are limited to single radio wireless network. To demonstrate the benefits of CC in multiradio multihop wireless network, this paper studies a joint problem of multiradio cooperative routing and relay assignment to maximize the minimum rate among a set of concurrent communication sessions. We first model this problem as a mixed-integer programming (MIP) problem and prove it to be NP-hard. Then, we propose a centralized algorithm and a distributed algorithm to solve the problem. The centralized algorithm is designed within a branch-and-bound framework by using the relaxation of the formulated MIP, which can find a global (1+ε)-optimal solution. Our distributed algorithm includes two subalgorithms: a cooperative route selection subalgorithm and a fairness-aware route adjustment subalgorithm. Our simulation results demonstrate the effectiveness of the proposed algorithms and the significant rate gains that can be achieved by incorporating CC in multiradio multihop networks.

End-to-end network monitoring is essential to ensure transmission quality for Internet applications. However, in large-scale networks, full-mesh measurement of network performance between all transmission pairs is infeasible. As a newly emerging sparsity representation technique, matrix completion allows the recovery of a low-rank matrix using only a small number of random samples. Existing schemes often fix the number of samples assuming the rank of the matrix is known, while the data features thus the matrix rank vary over time. In this paper, we propose to exploit the matrix completion techniques to derive the end-to-end network performance among all node pairs by only measuring a small subset of end-to-end paths. To address the challenge of rank change in the practical system, we propose a sequential and information-based adaptive sampling scheme, along with a novel sampling stopping condition. Our scheme is based only on the data observed without relying on the reconstruction method or the knowledge on the sparsity of unknown data. We have performed extensive simulations based on real-world trace data, and the results demonstrate that our scheme can significantly reduce the measurement cost while ensuring high accuracy in obtaining the whole network performance data.

Matrix completion has emerged very recently and provides a new venue for low cost data gathering in WSNs. Existing schemes often assume that the data matrix has a known and fixed low-rank, which is unlikely to hold in a practical monitoring system such as weather data gathering. Weather data varies in temporal and spatial domain with time. By analyzing a large set of weather data collected from 196 sensors in ZhuZhou, China, we reveal that weather data have the features of low-rank, temporal stability, and relative rank stability. Taking advantage of these features, we propose an on-line data gathering scheme based on matrix completion theory, named MC-Weather, to adaptively sample different locations according to environmental and weather conditions. To better schedule sampling process while satisfying the required reconstruction accuracy, we propose several novel techniques, including three sample learning principles, an adaptive sampling algorithm based on matrix completion, and a uniform time slot and cross sample model. With these techniques, our MC-Weather scheme can collect the sensory data at required accuracy while largely reduce the cost for sensing, communication and computation. We perform extensive simulations based on the real weather data sets and the simulation results validate the efficiency and efficacy of the proposed scheme.

In recent years, cooperative communication has attracted researchers' attention as it showed a good capability to increase network performance. On the other hand, a cooperative transmission may cause more interference. This can cause difficulty in achieving cooperative diversity gain in multi-flow and multi-hop networks. In this paper, we propose a novel interference aware-cooperative-routing metric which will lead to creating a new scheme for cooperative routing and channel assignment in multi-flow and multi-hop networks. Then, we show through preliminary simulation results, by investigating the impact of the node density and impact of the flow number, that the proposed scheme minimizes interference while achieving maximum cooperative diversity gain.

Cooperative communication (CC) for wireless networks has gained a lot of recent interests. With its ability of mitigating fading by exploiting spatial diversity, CC has the potential to significantly increase the capacity of wireless networks. However, most of the works on CC are limited to single radio wireless network. To demonstrate the benefits of CC in multi-radio multi-hop wireless network, this paper studies a joint problem of multi-radio cooperative routing and relay assignment to maximize the minimum rate among a set of concurrent communication sessions. We first model this problem as a mixed integer linear programming (MILP) problem and prove it to be NP-hard. Then we propose a centralized algorithm and a distributed algorithm to solve the problem. The centralized algorithm is designed within a branch-and-bound framework by using the relaxation of the formulated MILP, which can find a global (1 + ε)-optimal solution. Our distributed algorithm includes two sub-algorithms: a cooperative route selection sub-algorithm and a fairness-aware route adjustment sub-algorithm. Our simulation results demonstrate the effectiveness of the proposed algorithms and the significant rate gains that can be achieved by incorporating CC in multi-radio multi-hop networks.

Cooperative communication for wireless networks has gained a lot of recent interests due to its ability to mitigate fading with exploration of spatial diversity. The objective of this paper is to design an efficient algorithm to minimize the total consumed power of the network while guaranteeing transmission reliability of multiple active transmission pairs through cooperative wireless communications. This problem has not been studied and is much more challenging than relay assignment considered in literature work which simply targets to reduce the transmission power for a single transmission pair. We achieve the objective by jointly considering transmission mode selection, relay assignment and power allocation. This requires us to solve a combinatorial optimization problem, namely Reliable and Energy Efficient Cooperative Communication problem (REECC), which is a hard problem as its complexity increases exponentially with the number of relay nodes. We propose an iterative solution framework by testing different power levels to find the optimal solution. To reduce the computational cost, we design several novel techniques in the solution framework. The simulation results demonstrate that our solution can run very efficiently to obtain the minimum total consumed power while satisfying the reliable transmission requirement.

Bloom filters allow membership queries over sets with allowable errors. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. However, the false positive errors are unavoidable, and the false positive rate increases intolerantly along with the date set expanding. To solve the scalability problem of Bloom filters, this paper presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The paper proposes algorithms for element insertion and query operation of SBF by employing the H3class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.