Huawei Ji, Yuanhao Sun, Yuan Jin, Cheng Deng, Jiaxin Ding, Luoyi Fu, Xinbing Wang. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Fine-grained inspection of ferrous structures, such as steel rebars and iron pipes, is essential for ensuring structural health/integrity. However, existing non-destructive imaging techniques often suffer from coarse spatial resolution, high operational costs, and limited mobility support, hence severely restricting their practical deployment. For example, ground-penetrating radar (GPR), constrained by its operating wavelength, cannot resolve sub-centimeter features or recover fine contours of embedded ferrous structures.

Rapid development of web services has led to an explosion of multimodal content, making multimodal recommender systems (MRSs) vital tools for mitigating information overload. Current MRSs have achieved remarkable progress by incorporating advanced technologies such as Graph Neural Networks (GNNs) and Large Language Models (LLMs). However, these studies still suffer from the semantic shift problem. Generally, item's multimodal content usually contain multiple objects, including target object (core content of item) and auxiliary objects (decorations of item). Existing MRSs overlooked this distinction, failing to prevent auxiliary objects from dominating the representation, leading to biased item representation. To address this issue, we propose a model-agnostic framework ''TargetMR''. Concretely, TargetMR comprises two core modules, including Object Disentangler and Object Identifier. The Object Disentangler decouples item text and image into multiple objects via text syntactic parsing and image segmentation. The Object Identifier performs knowledge distillation based on LLMs to efficiently identify the target text object. It then identifies the target image object through cross-modal semantic evaluation. Moreover, this module refines the representation of image target object by optimizing the semantic correlation. Owing to the model-agnostic design of TargetMR, it can be integrated into various backbone MRSs. Extensive experiments on three benchmark datasets show that TargetMR consistently improves the performance of five backbone MRSs, with an average improvement of 12.26%. Our codes are available at https://github.com/gutang-97/TargetMR/.

Graph generation underlies many critical applications, from social network modeling to knowledge graph reasoning. Across these diverse domains, many graphs are rationale–dominated : a small, semantically meaningful subgraph determines the property of interest, while the remaining edges contribute largely noisy variation. Despite the significance of this inherent structure, existing generative methods often fail to preserve these task–critical substructures. We introduce RARD (Rationale-first blockwise AutoRegressive Diffusion), a topology-guided framework that learns to separate and prioritize the rationale. RARD employs a persistent-homology-based learning objective to discover an optimal graph filtration, an edge ordering that explicitly separates rationale from noise. Building upon this learned filtration, RARD generates graphs blockwise: it adds filtration-aligned blocks autoregressively and refines each new block with a shared local discrete diffusion module, ensuring the rationale appears early while peripheral structure is added later. We provide theoretical analysis showing that maximizing the topological gap yields rationale-first ordering and collapses to a two-level filtration. Comprehensive experiments across seven benchmarks demonstrate that RARD achieves state-of-the-art performance on widely used metrics.

Deep learning has demonstrated remarkable generalization capability with independent and identically distributed (i.i.d.) training and test data, however, it often struggles with data drawn from different, albeit causally related, distributions. This problem is generally known as Out-of-Distribution (OoD) generalization. While there is a plethora of algorithms proposed for OoD generalization, the current understanding of the data commonly employed to evaluate these algorithms remains relatively naive. In this study, we identify two distinct types of distribution shifts, namely diversity shift and correlation shift, that are ubiquitous in various OoD datasets. We propose a quantifiable formal definition for the two shifts and show that the performance of OoD algorithms is upper bounded by them. To validate our theoretical insight, we evaluate a number of OoD generalization algorithms across two groups of datasets from both classification and object detection areas, each dominated by one of the shifts, exposing the strengths of the algorithms against one shift as well as their limitations against the other. We further proved that all performance degradations according to data distribution shifts can be attributed to these two types of shifts defined in our paper. The benchmark integrates existing datasets and algorithms from different research areas that seem unrelated into a coherent picture, which may serve as a foundation for future OoD generalization research.

In real-world scenarios, training and test data are often collected in diverse settings, leading to domain shifts arising from evolving environments and selection bias. While causality-inspired methods have shown promising results in tackling the out-of-distribution (OOD) generalization issue, prior methods treat the discovered differences across domains as confounding variables. While effective in handling domain differences (i.e., unseen environmental features in test data), they may fail when confronted with intricate spurious correlations in real-world datasets. In this study, we first analyze this limitation to inadequate modeling of causal intervention and derive the OOD generalization bound to explain the challenges it introduces. To address this problem, we propose a modified causal intervention approach to mitigate various types of confounders. Motivated by the mathematical formulation of our modified causal intervention, we introduce the Causal Feature Selection Module (CFSM) to suppress model weights on both domain-differences features and spurious correlation features. Integrated within the Base Feature Extraction Module, In-Sample Module, and Cross-Sample Module (B-I-C architecture), CFSM collectively neutralizes the confounding effects arising from both domain discrepancies and correlation distinctions, thereby achieving causal feature selection. Under mild assumptions, we prove that the proposed CFSM method can achieve strictly lower OOD errors. Further experiments conducted on various benchmark datasets demonstrate the effectiveness of the proposed method. Compared to previous deconfounding methods, our method not only mitigates the effect of domain-differences features but also the hard-to-identify spurious correlation features, achieving significant improvements in two-dimensional OOD generalization.

Out-of-Distribution (OOD) generalization is a promising yet challenging goal that guarantees the test performance of Graph Neural Networks (GNNs) in open-world settings. However, due to the intricate internal topology of graph-structured data, redundant information from the spurious topologies severely confuses GNNs to deviate from the labels. Extracting concise and label-relevant subgraphs from the original graphs can alleviate this problem. Unfortunately, existing methods either overlook the global structural distribution or rely heavily on manually predefined assumptions. As a result, they fall short of well capturing the structural distribution changes between input graph and extracted subgraph, thus compromising adaptability of extracted invariant subgraphs to diverse OOD scenarios. This motivates us to propose a framework called S tructural- E ntropy-guided I nformation B ottleneck (OOD-SEIB) that aims to more traceably measure the inherent information changes for better and more flexible OOD generalization. The core of OOD-SEIB lies in concise topology extraction module, where we measure the mutual information flow between input graph and extracted subgraph based on structural entropy, termed Compression Index (CI). Specifically, the CI is a quantifiable metric that calculates the codeword length required to describe entire graph structure via a biased random walk. Under this guidance, OOD-SEIB then launches a structural information bottleneck compression module that jointly optimizes both CI and label-relevance of the subgraph topology by iteratively balancing between informativeness and compression. To further improve GNN’s invariant subgraph identification capability, OOD-SEIB generates multiple augmented environments and distill the invariant subgraphs into GNN as knowledge in an inside-out manner. When iteratively optimizing in above prescribed way, OOD-SEIB progressively reinforce the invariant subgraph extraction, thereby enhancing its generalization capability. Extensive experiments on synthetic and three real-world graph-level OOD benchmarks demonstrate that our proposed OOD-SEIB improves classification accuracy by 4.85%–38.03% on average compared to state-of-the-art baselines. Additionally, we extend OOD-SEIB to two node-level benchmarks, achieving average classification accuracy improvements of 14.52% and 13.15%.

The deployment of sensors enables data-driven urban management, but necessitates inductive spatio-temporal kriging to infer unmonitored areas. Existing methods impute these unknown observations by smoothing temporal features based on spatial dependencies, overlooking the decoupling ofinherent propertiesanddynamic correlationsin message passing. In particular, the inherent properties reveal non-transitive signals, and current coupled aggregation leads to inaccurate results. To this end, we proposeTempoRAl deCoupledKriging, named TRACK, to decouple two factors with the help of node-specific inherency. Specifically, we first construct a node-specific profile to represent its inherency including geographical and periodic features, which is subsequently transformed into decoupling prompts. Secondly, the coupled temporal features are separated through querying each prompt embedding, facilitating precise temporal aggregation for inherent properties and spatial aggregation for dynamic correlations. Finally, a multi-task training strategy is further adopted to mimic the inductive scenarios during testing. We evaluate TRACK on four real-world datasets spanning urban traffic and air quality prediction tasks. TRACK achieves state-of-the-art performance, with average improvements of 3.10% in MAE and 4.45% in RMSE over strong baselines. Moreover, we further demonstrated its robust generalization in a challenging cross-city inductive setting. Code is available athttps://github.com/JeremyChou28/TRACK.

This paper proposes a novel address mapping mechanism for multi-robot communication and collaboration systems, named SPing. SPing addresses each robot with a dynamicphysical-world address- an encoding of the robot's physical location - rather than a pre-assigned digital-world ID (e.g., the IP address). This enables a “see-and-point” communication mode for robots: a robot can establish an immediate connection pointing to any other robot it intends to collaborate with in its visual field, without relying on a pre-existing multi-robot network. This on one hand improves the robustness and usefulness of multi-robot systems in uncertain and unstructured environments where network infrastructures are unavailable. On the other hand, it makes the robots' communication behavior tightly coupled with and more supportive of the collaboration tasks in the physical world. We build an end-to-end prototype of SPing and evaluate its performance in both static and mobile scenarios. The results show that SPing can always establish a connection precisely pointing to the target receiver with an average matching rate of 99.58%, and a spatial resolution of 0.3 m$\sim$0.5m.

This paper tries to answer a question: “Can we achieve spatial-selective transmission on IoT devices?” A positive answer would enable more secure data transmission among IoT devices. The challenge, however, is how to manipulate signal propagation without relying on beamforming antenna arrays which are usually unavailable on low-end IoT devices. We give an affirmative answer by introducing SpotSound, a novel acoustic communication system that exploits the diversity of multi-path indoors as a naturalbeamformer. By judiciously controlling the way how the information is embedded into the signal, SpotSound can make the signal decodable only when the signal propagates along a certain multipath channel. Since the multipath channel decorrelates rapidly over the distance between receivers, SpotSound can ensure the signal is decodable only at the target position, achieving precise physical isolation. SpotSound is a purely software-based solution that can run on most IoT devices where speakers and microphones are widely used. We implement SpotSound on Raspberry Pi connected with COTS microphone and speaker. Experimental results show that SpotSound could precisely focus its signal on spots with customized sizes ranging from 0.04m2to 0.5m2.

This paper presents μTag, an ultra-low-power backscatter sensor that supports high-rate sensing of a large number of targets simultaneously. The core of μTag is an RF “gene editing” technique that embeds both the identity of the sensor and the real-time motion or vibration state of the attached target intensively in the transient features of the sensor’s RF signal, in a collision-resilient manner. We provide practical techniques which i) generate such “genetic signal” with purely analog and extremely simple circuits; and ii) separate the signals from a large scale of sensors reliably. Our experimental results show that our design can support concurrent tracking of 150 targets with a 12 kHz per-tag sampling rate. We also demonstrate with multiple sensing applications that μTag can achieve high-speed and large-scale motion tracking, rotation frequency sensing, and contactless sensing. The PCB power consumption of μTag is 38∼107 μW, according to the operating frequency of the tag. Our ASIC simulation based on the 40 nm CMOS process shows that the power consumption can be further reduced to 0.13∼0.52 μW.

Shao Zhang, Xihuai Wang, Wenhao Zhang, Chaoran Li, Junru Song, Tingyu Li, Lin Qiu, Xuezhi Cao, Xunliang Cai, Wen Yao, Weinan Zhang, Xinbing Wang, Ying Wen. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Checkpointing is becoming a hotspot of interest in both academia and industry as the primary fault-tolerance method for large model training. However, existing checkpoint designs are tightly coupled with the training process, leading to interruptions that reduce overall training efficiency. To reduce the impact of checkpoints on training, this paper presents FlowCheck, a novel checkpointing system that decouples checkpoint operations from the training process, enabling checkpoint saving without blocking the training. Specifically, FlowCheck updates the checkpoints by extracting complete gradient information from the network traffic of normal training. FlowCheck deploys a traffic-mirroring network to support this design. To utilize mirrored traffic for checkpointing operations, two key challenges need to be addressed. First, we need to achieve precise identification and extraction of gradient packets from training traffic. Second, the transmission on the mirror link is unreliable due to its inability to trigger retransmission upon packet loss. Through two key designs: (1) packet-counting-based traffic identification, and (2) packet redundancy recovery mechanism, FlowCheck implements an efficient checkpointing system using the existing training network and solves the above two challenges. Experiments and estimations verify that FlowCheck achieves checkpoint operations with zero impact on training, and demonstrate that FlowCheck achieves over 98% effective training time under practical fault conditions.

Single Root I/O Virtualization (SR-IOV) technology has advanced in recent years and can simultaneously satisfy the network requirements of high data plane performance, high deployment density, and fast startup for applications in traditional containers. However, it falls short with secure containers, which have become the mainstream choice in multi-tenant clouds. SR-IOV requires secure containers to use passthrough I/O for higher data plane performance, which hinders the container startup performance and prevents its usage in time-sensitive tasks like serverless computing. In this paper, we advocate that the startup performance of SR-IOV enabled secure containers can be further boosted, making SR-IOV suitable for building a Container Network Interface (CNI) for secure containers. We first dissect the end-to-end concurrent startup process and identify three key bottlenecks that lead to the slow startup, including Virtual Function I/O device set management, Direct Memory Access memory mapping, and Virtual Function (VF) driver initialization. We then propose a CNI named FastIOV that addresses these bottlenecks through lock decomposition, unnecessary mapping skipping, decoupled zeroing, and asynchronous VF driver initialization. Our evaluation shows that FastIOV reduces the overhead of enabling SR-IOV for secure containers by 96.1%, achieving 65.7% and 75.4% reductions in the average and 99th percentile end-to-end startup time.

Transformer-based models have achieved great success in document ranking, yet they suffer from substantial computational costs due to the quadratic complexity of attention, particularly for Long Document Ranking (LDR). Token pruning is a promising approach to reducing computational costs, while existing methods have largely overlooked the interaction and alignment between document and query for guiding the token pruning process, which may result in mistakenly pruned tokens that are critical for the query but not for the document. Additionally, these methods often lack the flexibility required for varying input samples. To this end, we propose a novel framework, Adaptive Token Pruning with Query-Document Alignment (QD-ATP) for accelerating LDR. Specifically, we first introduce a well-designed Query-Document Alignment Guidance (QDAG) module to effectively align the semantic and matching information between query and document, ensuring that the pruned tokens are less important for both two fields. Furthermore, we design a novel Adaptive Token Pruning (ATP) module, which can dynamically adjust pruning ratios based on different input samples. Experimental results on three benchmark datasets demonstrate that QD-ATP can achieve up to a 7.3× latency speedup while preserving competitive performance.

With the development of data-centric AI, the focus has shifted from model-driven approaches to improving data quality. Academic literature, as one of the crucial types, is predominantly stored in PDF formats and needs to be parsed into texts before further processing. However, parsing diverse structured texts in academic literature remains challenging due to the lack of datasets that cover various text structures. In this paper, we introduce AceParse, the first comprehensive dataset designed to support the parsing of a wide range of structured texts, including formulas, tables, lists, algorithms, and sentences with embedded mathematical expressions. Based on AceParse, we fine-tuned a multimodal model, named AceParser, which accurately parses various structured texts within academic literature. This model outperforms the previous state-of-the-art by 4.1% in terms of F1 score and by 5% in Jaccard Similarity, demonstrating the potential of multimodal models in academic literature parsing. Our dataset is available at https://github.com/JHW5981/AceParse.

Reasoning over Knowledge Graphs (KGs) plays a pivotal role in knowledge graph completion or question answering systems, providing richer and more accurate triples and attributes. As numerical attributes become increasingly essential in characterizing entities and relations in KGs, the ability to reason over these attributes has gained significant importance. Existing graph-based methods such as Graph Neural Networks (GNNs) and Knowledge Graph Embeddings (KGEs), primarily focus on aggregating homogeneous local neighbors and implicitly embedding diverse triples. However, these approaches often fail to fully leverage the potential of logical paths within the graph, limiting their effectiveness in exploiting the reasoning process. To address these limitations, we propose ChainsFormer, a novel chain-based framework designed to support numerical reasoning. Chainsformer not only explicitly constructs logical chains but also expands the reasoning depth to multiple hops. Specially, we introduces Relation-Attribute Chains (RA-Chains), a specialized logic chain, to model sequential reasoning patterns. ChainsFormer captures the step-by-step nature of multi-hop reasoning along RA-Chains by employing sequential in-context learning. To mitigate the impact of noisy chains, we propose a hyperbolic affinity scoring mechanism that selects relevant logic chains in a variable-resolution space. Furthermore, ChainsFormer incorporates an attention-based numerical reasoner to identify critical reasoning paths, enhancing both reasoning accuracy and transparency. Experimental results demonstrate that ChainsFormer significantly outperforms state-of-the-art methods, achieving up to a 20.0% improvement in performance. The implementations are available at https://github.com/zhaodazhuang2333/ChainsFormer.

Evolving graphs are prevalent in real-world systems where nodes and edges continuously expand over time, resulting in persistent topological changes across temporal snapshots. As the graph expands, the increasing structural discrepancy between earlier and later timesteps often leads to poor generalization-a phenomenon widely recognized as Temporal out-of-distribution (TOOD) generalization. This issue has spurred growing research interest in generalized graph learning. Existing approaches often rely on modeling latent environments or incorporating structural causal reasoning, but they frequently face scalability limitations when applied to rapidly expanding graphs. In this work, we carry out a detailed analysis of temporal drift in evolving graphs and identify two complementary forms: structural role drift reflected by changes in degree proportions, and semantic drift measured by embedding divergence. To capture this graph evolution, we propose PromptEG, a scalable prompt-based framework that generates node-specific prompts using degree signals and KL-divergence between representations. These prompts are optimized via consistency and contrastive objectives, and injected into GNNs to enhance temporal generalization. Experiments on largescale evolving graphs-containing up to 500 K edges and tens of thousands of nodes-demonstrate that PromptEG achieves strong long-horizon generalization while maintaining high computational efficiency.

Given a style-reference image as the additional image condition, text-to-image diffusion models have demonstrated impressive capabilities in generating images that possess the content of text prompts while adopting the visual style of the reference image. However, current state-of-the-art methods often struggle to disentangle content and style from style-reference images, leading to issues such as content leakages. To address this issue, we propose a masking-based method that efficiently decouples content from style without the need of tuning any model parameters. By simply masking specific elements in the style reference's image features, we uncover a critical yet under-explored principle: guiding with appropriately-selected fewer conditions (e.g., dropping several image feature elements) can efficiently avoid unwanted content flowing into the diffusion models, enhancing the style transfer performances of text-to-image diffusion models. In this paper, we validate this finding both theoretically and experimentally. Extensive experiments across various styles demonstrate the effectiveness of our masking-based method and support our theoretical results.

Constrained Reinforcement Learning (CRL) aims to maximize cumulative rewards while satisfying constraints. However, existing CRL algorithms often encounter significant constraint violations during training, limiting their applicability in safety-critical scenarios. In this paper, we identify the underestimation of the cost value function as a key factor contributing to these violations. To address this issue, we propose the Memory-driven Intrinsic Cost Estimation (MICE) method, which introduces intrinsic costs to mitigate underestimation and control bias to promote safer exploration. Inspired by flashbulb memory, where humans vividly recall dangerous experiences to avoid risks, MICE constructs a memory module that stores previously explored unsafe states to identify high-cost regions. The intrinsic cost is formulated as the pseudo-count of the current state visiting these risk regions. Furthermore, we propose an extrinsic-intrinsic cost value function that incorporates intrinsic costs and adopts a bias correction strategy. Using this function, we formulate an optimization objective within the trust region, along with corresponding optimization methods. Theoretically, we provide convergence guarantees for the proposed cost value function and establish the worst-case constraint violation for the MICE update. Extensive experiments demonstrate that MICE significantly reduces constraint violations while preserving policy performance comparable to baselines.

Ensuring safety is a critical challenge in applying Reinforcement Learning (RL) to real-world scenarios. Constrained Reinforcement Learning (CRL) addresses this by maximizing returns under predefined constraints, typically formulated as the expected cumulative cost. However, expectation-based constraints overlook rare but high-impact extreme value events in the tail distribution, such as black swan incidents, which can lead to severe constraint violations. To address this issue, we propose the Extreme Value policy Optimization (EVO) algorithm, leveraging Extreme Value Theory (EVT) to model and exploit extreme reward and cost samples, reducing constraint violations. EVO introduces an extreme quantile optimization objective to explicitly capture extreme samples in the cost tail distribution. Additionally, we propose an extreme prioritization mechanism during replay, amplifying the learning signal from rare but high-impact extreme samples. Theoretically, we establish upper bounds on expected constraint violations during policy updates, guaranteeing strict constraint satisfaction at a zero-violation quantile level. Further, we demonstrate that EVO achieves a lower probability of constraint violations than expectation-based methods and exhibits lower variance than quantile regression methods. Extensive experiments show that EVO significantly reduces constraint violations during training while maintaining competitive policy performance compared to baselines.

Improving the generalization of multi-camera 3D object detection is essential for safe autonomous driving in the real world. In this paper, we consider a realistic yet more challenging scenario, which aims to improve the generalization when only single source data available for training, as gathering diverse domains of data and collecting annotations is time-consuming and labor-intensive. To this end, we propose the Fourier Cross-View Learning (FCVL) framework including Fourier Hierarchical Augmentation (FHiAug), an augmentation strategy in the frequency domain to boost domain diversity, and Fourier Cross-View Semantic Consistency Loss to facilitate the model to learn more domain-invariant features from adjacent perspectives. Furthermore, we provide theoretical guarantees via augmentation graph theory. To the best of our knowledge, this is the first study to explore generalizable multi-camera 3D object detection with a single source. Extensive experiments on various testing domains have demonstrated that our approach achieves the best performance across various domain generalization methods.

With the increasing popularity of autonomous driving based on the Bird's-Eye-View (BEV) representation, improving the generalization of such detection models is key for safe real-world applications. However, a realistic yet challenging scenario: Single Domain Generalization (SDG) for BEV, is still under-explored. A key ingredient for SDG is to increase data diversity via common image augmentation or adversarial data generation first. However, common image-level augmentation is not sufficient enough to ensure domain diversity in most part of latent space. The adversarial generation has the problem of unstable training or mode collapsing as well. To address these limitations, we present Tri-level Automatic Augmentation (Tri-AutoAug), a simple yet effective method to enlarge the diversity and quantity of data from image and 2D features and facilitate the model to learn more domain-invariant features in BEV space. Besides, Tri-AutoAug can automatically learn augmentation strategies to avoid spending too much time manually adjusting hyperparameters and maximize the benefit of Tri-level Augmentation. To the best of our knowledge, this is the first study to explore automatic augmentation for SDG BEV. Extensive experiments on NuScenes-C including eight testing domains have demonstrated that our approach can achieve the best performance across various domain generalization methods. More importantly, we evaluate the proposed method in real-world autonomous driving scenarios. Tri-AutoAug improves the out-of-distribution (ood) performance by 8.54% (mAP), which demonstrates that Tri-AutoAug provides a practical and feasible solution for the applications of 3D detectors in the real world. The code is available at https://github.com/ClaireTunlTri-AutoAug.

With the explosive growth of online multimodal content, multimodal recommender systems(MRSs) have brought significant benefits to multimedia platforms. As MRSs evolve, many studies incorporate advanced technologies like graph neural networks(GNNs) and self-supervised learning(SSL), achieving remarkable results. However, these efforts still suffer from the quality disparity problem. It refers to the mixture of high and low quality across items' multiple modalities, owing to disparities in construction costs or design levels. These low-quality modalities often lack crucial details or introduce noise to the depiction of item, leading to insufficient or polluted item representation. Therefore, we propose a novel framework R2MR: Review and Rewrite Modality for Recommendation to tackle this issue. Specifically, R2MR is composed of two key components: Modality Reviewer and Modality Rewriter. The Modality Reviewer introduces a Consensus Review Mechanism. It performs perspective decomposition based on user representations and learns the consensus quality scores for modalities from diverse perspectives of multiple users. The Modality Rewriter proposes a Latent Mapping Model, which improves the quality of inferior modalities by learning various mapping patterns from high-quality modalities. Comprehensive experiments across three benchmark datasets reveal that R2MR substantially outperforms state-of-the-art methods, achieving an average improvement of 9.20%. The implementations are available at https://github.com/gutang-97/R2MR.

Nowadays, the explosive growth of academic literature has been going far beyond scientists' limited capability to read through, making it increasingly difficult for them to absorb disciplinary insights and extract intellectual essences critical for generating novel research ideas in interdisciplinary studies. To address this, we develop DeepReport, an AI-assisted scientific idea generation system to alleviate the research burden. Technically, DeepReport maintains evolving concept co-occurrence graphs to extract core insights from over 260 million publications across all disciplines. These concepts are periodically collected and updated, enabling the automatic extraction of hidden cross-domain connections. Combining temporal link prediction and analysis techniques with large language models, DeepReport is able to further transform these patterns of insights into actionable ideas. With the function of integrating up-to-date academic databases, visualizing dynamic relationships of concepts, and automatically generating new ideas, DeepReport empowers researchers to navigate complex knowledge landscapes, reduce cognitive burdens, and accelerate the generation of groundbreaking concepts. This work provides an in-depth exploration of DeepReport's architecture, functionalities, and applications, highlighting its transformative potential for advancing interdisciplinary research and fostering innovation. DeepReport is available at https://idea.acemap.cn/.

This paper investigates the problem of maintaining the connectivity between two vertices, a source and a destination, in an uncertain network under adversarial attack, where a defender preserves crucial links to prevent the source–destination vertex pair from being disconnected by an attacker. In contrast with prior art that mostly focuses on the overall network connectivity, in this work connectivity maintenance is restricted to a pair of selected vertices, which may provide insights into reliable point-to-point connection. We model the network as a random graph where each link carries both an existence probability and a probing cost, and seek to design a defensive strategy that ensures source–destination connectivity under minimum probing expenditure, regardless of adversarial behavior. To this end, we first delve into the computational complexity of the problem by establishing its NP-hardness, and put forth an optimal defensive strategy leveraging dynamic programming. Due to the prohibitive price of attaining optimality, we further design two approximate defensive strategies aimed at pursuing effective defensive performance within polynomial time, in which the first one is a path-based heuristic strategy that iteratively extends a preserved path by probing links with high utility regarding source–destination connectivity, and the second one is a cut-based minimax strategy that prioritizes the links in the minimum potential source–destination cut in order to minimize the possible worst-case loss suffered by the defender with a constant approximation ratio. Extensive experiments conducted on synthetic and real-world network datasets under diverse attacking strategies validate the superiority of the proposed strategies in both effectiveness and robustness over baselines.

This paper delves into the challenge of maintaining connectivity in adversarial networks, focusing on the preservation of essential links to prevent the disintegration of network components under attack. Unlike previous approaches that assume a stable and homogeneous network topology, this study introduces a more realistic model that incorporates both link uncertainty and heterogeneity. Link uncertainty necessitates additional probing to confirm link existence, while heterogeneity reflects the varying resilience of links against attacks. We model the network as a random graph where each link is defined by its existence probability, probing cost, and resilience. The primary objective is to devise a defensive strategy that maximizes the expected size of the largest connected component at the end of an adversarial process while minimizing the probing cost, irrespective of the attack patterns employed. We begin by establishing the NP-hardness of the problem and then introduce an optimal defensive strategy based on dynamic programming. Due to the high computational cost of achieving optimality, we also develop two approximate strategies that offer efficient solutions within polynomial time. The first is a heuristic method that assesses link importance across three heterogeneous subnetworks, and the second is an adaptive minimax policy designed to minimize the defender’s potential worst-case loss, with guaranteed performance. Through extensive testing on both synthetic and real-world datasets across various attack scenarios, our strategies demonstrate significant advantages over existing methods.

In real-world scenarios, distribution shifts give rise to the importance of two problems: out-of-distribution (OoD) generalization, which focuses on models' generalization ability against covariate shifts (i.e., the changes of environments), and OoD detection, which aims to be aware of semantic shifts (i.e., test-time unseen classes). Real-world testing environments often involve a combination of both covariate and semantic shifts. While numerous methods have been proposed to address these critical issues, only a few works tackled them simultaneously. Moreover, prior works often improve one problem but sacrifice the other. To overcome these limitations, we delve into boosting OoD detection and OoD generalization from the perspective of information theory, which can be easily applied to existing models and different tasks. Building upon the theoretical bounds for mutual information and conditional entropy, we provide a unified approach, composed of Mutual Information Minimization (MI-Min) and Conditional Entropy Maximizing (CE-Max). Extensive experiments and comprehensive evaluations on multi-label image classification and object detection have demonstrated the superiority of our method. It successfully mitigates trade-offs between the two challenges compared to competitive baselines.

Optic disc (OD) segmentation in abnormal fundus images is crucial for glaucoma screening, and different screening populations may alter the types and proportions of abnormalities. Since annotating all abnormal types or re-annotating for each screening scenario is costly, an alternative is to utilize existing annotated data. However, these datasets only contain limited abnormal types, leading to a domain shift issue. Unsupervised domain adaptation alleviates this issue through adversarial learning or self-training. Yet, adversarial learning methods tend to overemphasize brightness as a discriminative feature, which fails under pathological changes, while self-training approaches remain vulnerable to noisy pseudo-labels. Existing denoising methods assume noise lies near decision boundaries, but abnormalities can produce noise far from them. In this letter, we propose an unsupervised domain adaptation method integrating anatomical-aware self-training with adversarial learning for OD segmentation. By exploiting the OD's convex shape and boundary consistency, we develop two pseudo-labeling strategies to suppress noise. Experiments on four fundus image datasets demonstrate the effectiveness of our method in diverse screening scenarios.

Due to detector malfunctions and communication failures, missing data is ubiquitous during the collection of traffic data. Therefore, it is of vital importance to impute the missing values to facilitate data analysis and decision-making for Intelligent Transportation System (ITS) . However, existing imputation methods generally perform zero pre-filling techniques to initialize missing values, introducing inevitable noise. Moreover, we observe prevalent over-smoothed interpolations, falling short in revealing the intrinsic spatio-temporal correlations of incomplete traffic data. To this end, we propose Mask-Aware Graph Imputation Network (MagiNet) . Our method designs an adaptive mask spatio-temporal encoder to learn the latent representations of incomplete data, eliminating the reliance on pre-filling missing values. Furthermore, we devise a spatio-temporal decoder that stacks multiple blocks to capture the inherent spatial and temporal dependencies within incomplete traffic data, alleviating over-smoothed imputation. Extensive experiments demonstrate that our method outperforms state-of-the-art imputation methods on five real-world traffic datasets, yielding an average improvement of 4.31% in RMSE and 3.72% in MAPE under Missing Completely at Random (MCAR) pattern. Code is available at https://github.com/JeremyChou28/MagiNet .

We investigate tight end-to-end delay guarantees for real-time flows with stochastic arrivals in multi-hop networks. The existing multi-hop scheduling policy either only serves for real-time flows with deterministic arrivals or cannot offer a tight end-to-end delay guarantee for multi-hop flows. In this paper, we prove a closed-form formula, which offers a sufficient and necessary condition for the EDF (Earliest Deadline First) scheduling policy to meet all the end-to-end deadlines for flows with stochastic arrivals in converge-cast tree networks. To the best of our knowledge, this is the first formula that characterizes the exact schedulability region for EDF in multi-hop networks. Moving beyond converge-cast tree networks to general multi-hop networks, we introduce the Segment EDF approach. This method partitions a general network into multiple converge-cast networks using a novel concept called the critical links. By determining segment deadlines within the schedulability region of each converge-cast tree, Segment EDF offers a tight end-to-end delay guarantee for each flow. We present a theoretical analysis showcasing the superior performance of Segment EDF over the existing scheduling policy of hop-by-hop EDF. Furthermore, we evaluate the performance of Segment EDF based on two key metrics: guaranteed flow completion time and admission ratio, in both real-world and synthetic networks. Our simulation results show that Segment EDF can provide 61.31%-96.4% tighter end-to-end delay guarantee and increase admission ratio by about 3.52%-107.59% for sequential arrival flow set and 1.04%-95.50% for batch arrival flow set than hop-by-hop EDF.

Deterministic Networking (DetNet) is a rising technology that offers deterministic delay & jitter and extremely low packet loss in large IP networks. To achieve determinism under failure scenarios, DetNet requires finding at least two paths with close end-to-end delay, i.e., adelay-diffconstraint, for mission-critical flows. However, how to find two routing paths subject to thedelay-diffconstraint remains open. We study the DetNet routing problem in two scenarios. First, given a primary path, we propose Pulse+, which finds a secondary path whose end-to-end delay is within a range determined by the end-to-end delay of the primary path and the delay-diff requirement. Second, we propose CoSE-Pulse+, which integrates Pulse+ with a divide-and-conquer approach to find a pair of paths that meet DetNet’s delay-diff constraint. Both Pulse+ and CoSE-Pulse+ guarantee solution optimality. Notably, although Pulse+ and CoSE-Pulse+ do not have a polynomial worst-case time complexity, their empirical solver running time is better than that of other algorithms. We evaluate Pulse+ and CoSE-Pulse+ against the K-Shortest-Path and Lagrangian-dual based algorithms using synthetic test cases generated over networks with up to 10000 nodes. Both Pulse+ and CoSE-Pulse+ can solve more test cases than other algorithms under a predefined time limit. Compared to the second best algorithm, Pulse+ achieves an average-time speedup of$5\times $and CoSE-Pulse+ achieves an average-time speedup of$22\times $. Our code and test cases are available athttps://gitee.com/zsz2019_shizhenzhao/drcr

In this paper, we focus on a realistic yet challenging task, Single Domain Generalization Object Detection (S-DGOD), where only one source domain's data can be used for training object detectors, but have to generalize multiple distinct target domains. In S-DGOD, both high-capacity fitting and generalization abilities are needed due to the task's complexity. Differentiable Neural Architecture Search (NAS) is known for its high capacity for complex data fitting and we propose to leverage Differentiable NAS to solve S-DGOD. However, it may confront severe over-fitting issues due to the feature imbalance phenomenon, where parameters optimized by gradient descent are biased to learn from the easy-to-learn features, which are usually non-causal and spuriously correlated to ground truth labels, such as the features of background in object detection data. Consequently, this leads to serious performance degradation, especially in generalizing to unseen target domains with huge domain gaps between the source domain and target domains. To address this issue, we propose the Generalizable loss (G-loss), which is an OoD-aware objective, preventing NAS from over-fitting by using gradient descent to optimize parameters not only on a subset of easy-to-learn features but also the remaining predictive features for generalization, and the overall framework is named G-NAS. Experimental results on the S-DGOD urban-scene datasets demonstrate that the proposed G-NAS achieves SOTA performance compared to baseline methods. Codes are available at https://github.com/wufan-cse/G-NAS.

Out-of-distribution (OOD) generalization has long been a challenging problem that remains largely unsolved. Gaussian processes (GP), as popular probabilistic model classes, especially in the small data regime, presume strong OOD generalization abilities. Surprisingly, their OOD generalization abilities have been under-explored before compared with other lines of GP research. In this paper, we identify that GP is not free from the problem and propose a domain invariant learning algorithm for Gaussian processes (DIL-GP) with a min-max optimization on the likelihood. DIL-GP discovers the heterogeneity in the data and forces invariance across partitioned subsets of data. We further extend the DIL-GP to improve Bayesian optimization's adaptability on changing environments. Numerical experiments demonstrate the superiority of DIL-GP for predictions on several synthetic and real-world datasets. We further demonstrate the effectiveness of the DIL-GP Bayesian optimization method on a PID parameters tuning experiment for a quadrotor. The full version and source code are available at: https://github.com/Billzxl/DIL-GP.

A surge in data-driven applications enhances everyday life but also raises serious concerns about private information leakage. Hence many privacy auditing tools are emerging for checking if the data sanitization performed meets the privacy standard of the data owner. Blackbox auditing for differential privacy is particularly gaining popularity for its effectiveness and applicability to a wide range of scenarios. Yet, we identified that blackbox auditing is essentially flawed with its setting --- small probabilities/densities are ignored due to inaccurate observation. Our argument is based on a solid false positive analysis from a hypothesis testing perspective, which is missed out by prior blackbox auditing tools. This oversight greatly reduces the reliability of these tools, as it allows malicious or incapable data curators to pass the auditing with an overstated privacy guarantee, posing significant risks to data owners. We demonstrate the practical existence of such threats in classical differential privacy mechanisms against four representative blackbox auditors with experimental validations. Our findings aim to reveal the limitations of blackbox auditing tools, empower the data owner with the awareness of risks in using these tools, and encourage the development of more reliable differential privacy auditing methods.

Missing values are prevalent in multivariate time series, compromising the integrity of analyses and degrading the performance of downstream tasks. Consequently, research has focused on multivariate time series imputation, aiming to accurately impute the missing values based on available observations. A key research question is how to ensure imputation consistency, i.e., intra-consistency between observed and imputed values, and inter-consistency between adjacent windows after imputation. However, previous methods rely solely on the inductive bias of the imputation targets to guide the learning process, ignoring imputation consistency and ultimately resulting in poor performance. Diffusion models, known for their powerful generative abilities, prefer to generate consistent results based on available observations. Therefore, we propose a conditional diffusion model for Multivariate Time Series Consistent Imputation (MTSCI). Specifically, MTSCI employs a contrastive complementary mask to generate dual views during the forward noising process. Then, the intra contrastive loss is calculated to ensure intra-consistency between the imputed and observed values. Meanwhile, MTSCI utilizes a mixup mechanism to incorporate conditional information from adjacent windows during the denoising process, facilitating the inter-consistency between imputed samples. Extensive experiments on multiple real-world datasets demonstrate that our method achieves the state-of-the-art performance on multivariate time series imputation task under different missing scenarios. Code is available at https://github.com/JeremyChou28/MTSCI.

The majority of GNNs are based on message-passing mechanisms. However, Message Passing Neural Networks (MPNNs) have inherent limitations in capturing long-range interactions. The exponentially growing node information is compressed into fixed-size representations through multiple rounds of message passing, leading to the over-squashing problem. This issue severely hinders the flow of information across the graph and creates a bottleneck in graph learning. The natural idea of introducing global attention to point-to-point communication, as adopted in Graph Transformers (GTs), lacks inductive biases on graph structures and relies on complex positional encodings to enhance their performance in practical tasks. In this paper, we observe that the sensitivity between nodes in MPNNs decreases exponentially with the shortest path distance. In contrast, GTs have constant sensitivity, which leads to a loss of inductive bias. To address these issues, we introduce structured state spaces to capture the hierarchy of rooted trees, achieving linear sensitivity with theoretical guarantees. We further propose a novel state-space model-based graph convolution, resulting in a new paradigm that retains both the strong inductive biases from MPNNs and the long-range modeling capabilities from GTs. Extensive experimental results on long-range and general graph benchmarks demonstrate the superiority of our approach.

Shuqian Sheng, Yi Xu, Tianhang Zhang, Zanwei Shen, Luoyi Fu, Jiaxin Ding, Lei Zhou, Xiaoying Gan, Xinbing Wang, Chenghu Zhou. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Human trajectories, representing sequences of location points over time, are extensively collected and analyzed for various real-world applications such as urban planning, transportation management, and personalized location-based services. Trajectory embedding transforms raw trajectories into vector representations, capturing the underlying patterns and structures in the data. However, the abstraction provided by vector representations introduces significant security and privacy risks. These embeddings, often shared between entities or organizations, can be exploited by adversaries to reconstruct original trajectories, thereby compromising individual privacy. In this paper, we investigate the privacy issues of trajectory embeddings from an adversary's perspective. We propose two types of attacks to reconstruct original trajectories using road network information, addressing scenarios where the adversary has varying degrees of access to the black-box representation model. The first attack assumes unrestricted access to the model, allowing the adversary to construct a large-scale dataset and train a neural network to predict the road sequence of the trajectories. The second attack considers limited access, where the adversary computes distance coordinates between selected trajectory landmarks and road segments to infer different parts of the trajectory. Our experiments on a real-world dataset demonstrate that the reconstructed trajectories outperform baseline methods, achieving substantially lower reconstruction errors and more accurate alignment with the original trajectories, highlighting the significant vulnerability of trajectory embeddings to privacy breaches. These findings underscore the need for robust privacy-preserving mechanisms in spatio-temporal data analysis.

The sheer volume of scientific experimental results and complex technical statements, often presented in tabular formats, presents a formidable barrier to individuals acquiring preferred information. The realms of scientific reasoning and content generation that adhere to user preferences encounter distinct challenges. In this work, we present a new task for generating fluent and logical descriptions that match user preferences over scientific tabular data, aiming to automate scientific document analysis. To facilitate research in this direction, we construct a new challenging dataset CTRLSciTab consisting of table-description pairs extracted from the scientific literature, with highlighted cells and corresponding domain-specific knowledge base. We evaluated popular pre-trained language models to establish a baseline and proposed a novel architecture outperforming competing approaches. The results showed that large models struggle to produce accurate content that aligns with user preferences. As the first of its kind, our work should motivate further research in scientific domains.1

Learning with noisy labels is a challenging task in machine learning. Furthermore in reality, label noise can be highly non-uniform in feature space, e.g. with higher error rate for more difficult samples. Some recent works consider instance-dependent label noise but they require additional information such as some cleanly labeled data and confidence scores, which are usually unavailable or costly to obtain. In this paper, we consider learning with non-uniform label noise that requires no such additional information. Inspired by stratified sampling, we propose a cluster-dependent sample selection algorithm followed by a contrastive training mechanism based on the cluster-dependent label noise. Despite its simplicity, the proposed method can distinguish clean data from the corrupt ones more precisely and achieve state-of-the-art performance on most image classification benchmarks, especially when the number of training samples is small and the noise rate is high. The code is released at https://github.com/MattZ-99/ClusterCL.

Graph Neural Networks (GNNs) are widely deployed in vast fields, but they often struggle to maintain accurate representations as graphs evolve. We theoretically establish a lower bound, proving that under mild conditions, representation distortion inevitably occurs over time. To estimate the temporal distortion without human annotation after deployment, one naive approach is to pre-train a recurrent model (e.g., RNN) before deployment and use this model afterwards, but the estimation is far from satisfactory. In this paper, we analyze the representation distortion from an information theory perspective, and attribute it primarily to inaccurate feature extraction during evolution. Consequently, we introduce Smart, a straightforward and effective baseline enhanced by an adaptive feature extractor through self-supervised graph reconstruction. In synthetic random graphs, we further refine the former lower bound to show the inevitable distortion over time and empirically observe that Smart achieves good estimation performance. Moreover, we observe that Smart consistently shows outstanding generalization estimation on four real-world evolving graphs. The ablation studies underscore the necessity of graph reconstruction. For example, on OGB-arXiv dataset, the estimation metric MAPE deteriorates from 2.19% to 8.00% without reconstruction.

Graph pooling compresses graph information into a compact representation. State-of-the-art graph pooling methods follow a hierarchical approach, which reduces the graph size step-by-step. These methods must balance memory efficiency with preserving node information, depending on whether they use node dropping or node clustering. Additionally, fixed pooling ratios or numbers of pooling layers are predefined for all graphs, which prevents personalized pooling structures from being captured for each individual graph. In this work, inspired by bottom-up grammar induction, we propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph. GPN benefits from the discrete assignments generated by the graph parsing algorithm, allowing good memory efficiency while preserving node information intact. Experimental results on standard benchmarks demonstrate that GPN outperforms state-of-the-art graph pooling methods in graph classification tasks while being able to achieve competitive performance in node classification tasks. We also conduct a graph reconstruction task to show GPN's ability to preserve node information and measure both memory and time efficiency through relevant tests.

Accurately reconstructing the global ocean deoxygenation over a century is crucial for assessing and protecting marine ecosystem. Existing expert-dominated numerical simulations fail to catch up with the dynamic variation caused by global warming and human activities. Besides, due to the high-cost data collection, the historical observations are severely sparse, leading to big challenge for precise reconstruction. In this work, we propose OxyGenerator, the first deep learning based model, to reconstruct the global ocean deoxygenation from 1920 to 2023. Specifically, to address the heterogeneity across large temporal and spatial scales, we propose zoning-varying graph message-passing to capture the complex oceanographic correlations between missing values and sparse observations. Additionally, to further calibrate the uncertainty, we incorporate inductive bias from dissolved oxygen (DO) variations and chemical effects. Compared with in-situ DO observations, OxyGenerator significantly outperforms CMIP6 numerical simulations, reducing MAPE by 38.77%, demonstrating a promising potential to understand the “breathless ocean” in data-driven manner.

Recent vision-language pre-trained models (VL-PTMs) have shown remarkable success in open-vocabulary tasks. However, downstream use cases often involve further fine-tuning of VL-PTMs, which may distort their general knowledge and impair their ability to handle distribution shifts. In real-world scenarios, machine learning systems inevitably encounter both covariate shifts (e.g., changes in image styles) and semantic shifts (e.g., test-time unseen classes). This highlights the importance of enhancing out-of-distribution (OOD) generalization on covariate shifts and simultaneously detecting semantic-shifted unseen classes. Thus a critical but underexplored question arises: How to improve VL-PTMs’ generalization ability to closed-set OOD data, while effectively detecting open-set unseen classes during fine-tuning? In this paper, we propose a novel objective function of OOD detection that also serves to improve OOD generalization. We show that minimizing the gradient magnitude of energy scores on training data leads to domain-consistent Hessians of classification loss, a strong indicator for OOD generalization revealed by theoretical analysis. Based on this finding, we have developed a unified fine-tuning framework that allows for concurrent optimization of both tasks. Extensive experiments have demonstrated the superiority of our method. The code is available at https://github.com/LinLLLL/CRoFT.

In this paper, we use empirical measurements to show that container network startup is a key factor that contributes to the slow startup of secure containers in multi-tenant clouds, especially in the scenario of serverless computing, where the issue is pronounced by high-volume concurrent container invocations. We conduct extensive and detailed analysis on existing Container Network Interface (CNI) plugins and show that even the fastest one doubles the startup time from the no-network scenario. We show that the major cause of the blowup in total startup time is that enabling networking significantly increases the contention among different startup stages, particularly for global Linux kernel locks, including the Routing Table NetLink (RTNL) mutex lock and various spin locks. We reveal that contending for these locks hinders startup performance in three ways, including directly increasing stage time, causing poor pipeline overlap and wasting CPU resources. To mitigate such kernel lock contention, we propose a multi-stage concurrency control mechanism based on Bayesian optimization to limit the concurrency of each contended stage. Our results show that this lightweight mechanism can effectively reduce the end-to-end container startup time by 18.8% with negligible extra overhead.

Recently, there has been a surge in machine-generated natural language content being misused by unauthorized parties. Watermarking is a well-recognized technique to address the issue by tracing the provenance of the text. However, we found that most existing watermarking systems for texts are subject to ad hoc design and thus suffer from fundamental vulnerabilities.

Fiducial marking is indispensable in mobile robots, including their pose calibration, contextual perception, and navigation. However, existing fiducial markers rely solely on vision-based perception which suffers such limitations as occlusion, energy overhead, and privacy leakage.

This paper presents μTag, an ultra-low-power backscatter sensor that supports high-frequency sensing of a large number of targets simultaneously. The core of μTag is an RF "gene editing" technique that embeds both the identity of the sensor and the real-time motion state of the attached target intensively in the transient features of the sensor's RF signal, in a collision-resilient manner. We provide practical techniques which i) generate such "genetic signal" with purely analog and extremely simple circuits; and ii) separate the signals from a large scale of sensors reliably. Our experimental results show that our design can support concurrent tracking of 150 targets with a 12kHz per-tag sampling rate. We also demonstrate with multiple sensing applications that μTag can achieve high-speed and large-scale motion tracking and rotation frequency sensing. The PCB power consumption of μTag is 38~107μW, according to the operating frequency of the tag. Our ASIC simulation based on the 40nm CMOS process shows that the power consumption can be further reduced to 0.13~0.52μW.

Shuqian Sheng, Yi Xu, Luoyi Fu, Jiaxin Ding, Lei Zhou, Xinbing Wang, Chenghu Zhou. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

We investigate the entity alignment (EA) problem with unlabeled dangling cases, meaning that partial entities have no counterparts in the other knowledge graph (KG), yet these entities are unlabeled. The problem arises when the source and target graphs are of different scales, and it is much cheaper to label the matchable pairs than the dangling entities. To address this challenge, we propose the framework \textit{Lambda} for dangling detection and entity alignment. Lambda features a GNN-based encoder called KEESA with a spectral contrastive learning loss for EA and a positive-unlabeled learning algorithm called iPULE for dangling detection. Our dangling detection module offers theoretical guarantees of unbiasedness, uniform deviation bounds, and convergence. Experimental results demonstrate that each component contributes to overall performances that are superior to baselines, even when baselines additionally exploit 30\% of dangling entities labeled for training.

Protecting the copyright of large language models (LLMs) has become crucial due to their resource-intensive training and accompanying carefully designed licenses. However, identifying the original base model of an LLM is challenging due to potential parameter alterations. In this study, we introduce HuRef, a human-readable fingerprint for LLMs that uniquely identifies the base model without interfering with training or exposing model parameters to the public. We first observe that the vector direction of LLM parameters remains stable after the model has converged during pretraining, with negligible perturbations through subsequent training steps, including continued pretraining, supervised fine-tuning, and RLHF, which makes it a sufficient condition to identify the base model. The necessity is validated by continuing to train an LLM with an extra term to drive away the model parameters' direction and the model becomes damaged. However, this direction is vulnerable to simple attacks like dimension permutation or matrix rotation, which significantly change it without affecting performance. To address this, leveraging the Transformer structure, we systematically analyze potential attacks and define three invariant terms that identify an LLM's base model. Due to the potential risk of information leakage, we cannot publish invariant terms directly. Instead, we map them to a Gaussian vector using an encoder, then convert it into a natural image using StyleGAN2, and finally publish the image. In our black-box setting, all fingerprinting steps are internally conducted by the LLMs owners. To ensure the published fingerprints are honestly generated, we introduced Zero-Knowledge Proof (ZKP). Experimental results across various LLMs demonstrate the effectiveness of our method. The code is available at https://github.com/LUMIA-Group/HuRef.

With the proliferation of online data intensive applications and virtualized services, the growing complexity of traffic patterns in data centers increases the likelihood of congestion, especially in incast scenarios and with a combination of short and large flows. To ensure lossless transmission, RDMA over Converged Ethernet networks rely on Priority-based Flow Control (PFC) to prevent packet loss due to buffer overflow. However, it is widely acknowledged that PFC gives rise to several issues, such as Congestion Spreading, Head-of-Line Blocking, and Deadlock, which are increasingly prominent in modern highly congested data centers. In this paper, we analyze the primary causes of congestion spreading and head-of-line blocking issues associated with PFC and propose Original congestion-based fine-grained priority Flow Control (OFC) as a solution. The performance of OFC is assessed using the programmable switch Tofino and simulations carried out with a packet-level simulator across various scenarios, encompassing incast, realistic, deadlock, and in-depth scenarios. The validation of the simulation results through testbed evaluation confirmed that OFC effectively reduces flow completion time, buffer occupancy, and deadlock occurrence by up to 60.28%, 51.47%, and 48.7%, respectively.

Traffic Engineering (TE) is critical for improving network performance and reliability. A key challenge in TE is the management of sudden traffic bursts. Existing TE schemes either do not handle traffic bursts or uniformly guard against traffic bursts, thereby facing difficulties in achieving a balance between normal-case performance and burst-case performance. To address this issue, we introduce FIGRET, a Fine-Grained Robustness-Enhanced TE scheme. FIGRET offers a novel approach to TE by providing varying levels of robustness enhancements, customized according to the distinct traffic characteristics of various source-destination pairs. By leveraging a burst-aware loss function and deep learning techniques, FIGRET is capable of generating high-quality TE solutions efficiently. Our evaluations of real-world production networks, including Wide Area Networks and data centers, demonstrate that FIGRET significantly outperforms existing TE schemes. Compared to the TE scheme currently deployed in Google's Jupiter data center networks, FIGRET achieves a 9%-34% reduction in average Maximum Link Utilization and improves solution speed by 35×-1800×. Against DOTE, a state-of-the-art deep learning-based TE method, FIGRET substantially lowers the occurrence of significant congestion events triggered by traffic bursts by 41%-53.9% in topologies with high traffic dynamics.

Large language models (LLMs) have achieved great success in general domains of natural language processing. In this paper, we bring LLMs to the realm of geoscience with the objective of advancing research and applications in this field. To this end, we present the first-ever LLM in geoscience, K2, alongside a suite of resources developed to further promote LLM research within geoscience. For instance, we have curated the first geoscience instruction tuning dataset, GeoSignal, which aims to align LLM responses to geoscience-related user queries. Additionally, we have established the first geoscience benchmark, GeoBench, to evaluate LLMs in the context of geoscience. In this work, we experiment with a complete recipe to adapt a pre-trained general-domain LLM to the geoscience domain. Specifically, we further train the LLaMA-7B model on 5.5B tokens of geoscience text corpus, including over 1 million pieces of geoscience literature, and utilize GeoSignal's supervised data to fine-tune the model. Moreover, we share a protocol that can efficiently gather domain-specific data and construct domain-supervised data, even in situations where manpower is scarce. Meanwhile, we equip K2 with the abilities of using tools to be a naive geoscience aide. Experiments conducted on the GeoBench demonstrate the effectiveness of our approach and datasets on geoscience knowledge understanding and utilization.We open-source all the training data and K2 model checkpoints at https://github.com/davendw49/k2

Securing coordination between AI agent and teammates (human players or AI agents) in contexts involving unfamiliar humans continues to pose a significant challenge in Zero-Shot Coordination. The issue of cooperative incompatibility becomes particularly prominent when an AI agent is unsuccessful in synchronizing with certain previously unknown partners. Traditional algorithms have aimed to collaborate with partners by optimizing fixed objectives within a population, fostering diversity in strategies and behaviors. However, these techniques may lead to learning loss and an inability to cooperate with specific strategies within the population, a phenomenon named cooperative incompatibility in learning. In order to solve cooperative incompatibility in learning and effectively address the problem in the context of ZSC, we introduce the Cooperative Open-ended LEarning (COLE) framework, which formulates open-ended objectives in cooperative games with two players using perspectives of graph theory to evaluate and pinpoint the cooperative capacity of each strategy. We present two practical algorithms, specifically COLESV and COLER, which incorporate insights from game theory and graph theory. We also show that COLE could effectively overcome the cooperative incompatibility from theoretical and empirical analysis. Subsequently, we created an online Overcooked human-AI experiment platform, the COLE platform, which enables easy customization of questionnaires, model weights, and other aspects. Utilizing the COLE platform, we enlist 130 participants for human experiments. Our findings reveal a preference for our approach over state-of-the-art methods using a variety of subjective metrics. Moreover, objective experimental outcomes in the Overcooked game environment indicate that our method surpasses existing ones when coordinating with previously unencountered AI agents and the human proxy model. Our code and demo are publicly available at https://sites.google.com/view/cole-2023.

Generalizing out-of-distribution (OoD) is critical but challenging in real applications such as unmanned aerial vehicle (UAV) flight control. Previous machine learning-based control has shown promise in dealing with complex real-world environments but suffers huge performance degradation facing OoD scenarios, posing risks to the stability and safety of UAVs. In this paper, we found that the introduced random noises during training surprisingly yield theoretically guaranteed performances via a proposed functional optimization framework. More encouragingly, this framework does not involve common Lyapunov assumptions used in this field, making it more widely applicable. With this framework, the upperbound for control error is induced. We also proved that the induced random noises can lead to lower OoD control errors. Based on our theoretical analysis, we further propose OoD-Control to generalize control in unseen environments. Numerical experiments demonstrate the superiority of the proposed algorithm, surpassing previous state-of-the-art by 65% under challenging unseen environments. We further extend to outdoor real-world experiments and found that the control error is reduced by 50% approximately.

Many complex networks in the real world have community structures. Typical examples include online social networks and ecology networks. While the identification of communities bears numerous practical applications, with the increasing awareness of data security and privacy concerns, the need to protect the community affiliations of individuals from disclosing by attackers emerges. This raises the community deception (CD) problem, that is, the opposite of community detection, which asks for ways to minimally perturb the network structures by rewiring nodes so that the target communities maximally hide themself from community detection algorithms. To this end, we investigate the CD problem through a Laplacian spectrum lens and propose a method named$\mathtt {ComDeceptor}$to hide a flexible target set of communities, which is more universal than most existing methods that either focus on hiding the entire communities or a single community. The key idea of$\mathtt {ComDeceptor}$is to first allocate the resources of perturbations fairly and effectively. By proving that hiding communities through intercommunity edge addition and intracommunity edge deletion correspond to maximizing the second smallest eigenvalue$\lambda _{2}$and minimizing the largest eigenvalue$\lambda _{n}$of the graph Laplacian, respectively,$\mathtt {ComDeceptor}$then incorporates efficient heuristics for approximately solving the problems, thus selecting the appropriate edge to perturb. Experimental results over nine real-world networks and six community detection algorithms not only demonstrate the efficiency of$\mathtt {ComDeceptor}$, but also the superior performance on obfuscating community structures over the baselines.

Running on host mobile applications, mini apps have gained increasing popularity these days for its convenience in installation and usage. However, being easy to use allows mini apps to freely access a large amount of user information, mostly without close inspection of privacy violations. Hence it becomes a crucial issue to automatically track sensitive flows in mini apps. Although flow analysis has been widely studied, unique challenges emerge: the analysis tool should not only handle mini app-specific features such as flows that interweave between rendering and logic, and asynchronous executions, but also deal with problems raised by Javascript development: the performance tradeoff between precision and efficiency, and function aliases. To this end, we proposeMiniTracker, an automatic sensitive flow tracking tool which well handles mini app features, constructs assignment flow graphs as common representation across different host apps, searches function aliases, and analyzes the graph by property chains. We show our design choices achieve a sweet spot in the tradeoff between precision and efficiency, with superior performance compared to the state-of-the-art. We also perform a large-scale study on 150 k mini apps, which reveals the common leakage patterns and offers insights into the privacy threats of mini apps.

The robustness of deep neural networks (DNNs) against adversarial example attacks has raised wide attention. For smoothed classifiers, we propose the worst-case adversarial loss over input distributions as a robustness certificate. Compared with previous certificates, our certificate better describes the empirical performance of the smoothed classifiers. By exploiting duality and the smoothness property, we provide an easy-to-compute upper bound as a surrogate for the certificate. We adopt a noisy adversarial learning procedure to minimize the surrogate loss to improve model robustness. We show that our training method provides a theoretically tighter bound over the distributional robust base classifiers. Experiments on a variety of datasets further demonstrate superior robustness performance of our method over the state-of-the-art certified or heuristic methods.

Graph pooling refers to the operation that maps a set of node representations into a compact form for graph-level representation learning. However, existing graph pooling methods are limited by the power of the Weisfeiler–Lehman (WL) test in the performance of graph discrimination. In addition, these methods often suffer from hard adaptability to hyper-parameters and training instability. To address these issues, we propose Hi-PART, a simple yet effective graph neural network (GNN) framework with Hi erarchical Par tition T ree (HPT). In HPT, each layer is a partition of the graph with different levels of granularities that are going toward a finer grain from top to bottom. Such an exquisite structure allows us to quantify the graph structure information contained in HPT with the aid of structural information theory. Algorithmically, by employing GNNs to summarize node features into the graph feature based on HPT’s hierarchical structure, Hi-PART is able to adequately leverage the graph structure information and provably goes beyond the power of the WL test. Due to the separation of HPT optimization from graph representation learning, Hi-PART involves the height of HPT as the only extra hyper-parameter and enjoys higher training stability. Empirical results on graph classification benchmarks validate the superior expressive power and generalization ability of Hi-PART compared with state-of-the-art graph pooling approaches.

Network alignment, pairing corresponding nodes across the source and target networks, plays an important role in many data mining tasks. Extensive studies focus on learning node embeddings across different networks in a unified space. However, these methods have not taken the large structural discrepancy between aligned nodes into account and, thus, are largely confined by the deterministic representations of nodes. In this work, we propose a novel network alignment framework highlighted by distributional learning and globally optimal alignment. By modeling the uncertainty of each node by Gaussian distribution, our framework builds similarity matrices on the Wasserstein distance between distributions and applies Sinkhorn operation, which learns the globally optimal mapping in an end-to-end fashion. We show that each integrated part of the framework contributes to the overall performance. Under a variety of experimental settings, our alignment framework shows superior accuracy and efficiency to the state-of-the-art.

The great power of Graph Neural Networks (GNNs) relies on a large number of labeled training data, but obtaining the labels can be costly in many cases. Graph Active Learning (GAL) is proposed to reduce such annotation costs, but the existing methods mainly focus on improving labeling efficiency with fixed classes, and are limited to handle the emergence of novel classes. We term the problem as Open-World Graph Active Learning (OWGAL) and propose a framework of the same name. The key is to recognize novel-class as well as informative nodes in a unified framework. Instead of a fully connected neural network classifier, OWGAL employs prototype learning and label propagation to assign high uncertainty scores to the targeted nodes in the representation and topology space, respectively. Weighted sampling further suppresses the impact of unimportant classes by weighing both the node and class importance. Experimental results on four large-scale datasets demonstrate that our framework achieves a substantial improvement of 5.97% to 16.57% on Macro-F1 over state-of-the-art methods.

A networked time series (NETS) is a family of time series on a given graph, one for each node. It has a wide range of applications from intelligent transportation to environment monitoring to smart grid management. An important task in such applications is to predict the future values of a NETS based on its historical values and the underlying graph. Most existing methods require complete data for training. However, in real-world scenarios, it is not uncommon to have missing data due to sensor malfunction, incomplete sensing coverage, and so on. In this article, we study the problem of NETS prediction with incomplete data . We propose networked time series Imputation Generative Adversarial Network (NETS-ImpGAN), a novel deep learning framework that can be trained on incomplete data with missing values in both history and future. Furthermore, we propose Graph Temporal Attention Networks , which incorporate the attention mechanism to capture both inter-time series and temporal correlations. We conduct extensive experiments on four real-world datasets under different missing patterns and missing rates. The experimental results show that NETS-ImpGAN outperforms existing methods, reducing the Mean Absolute Error by up to 25%.

Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. However, due to the selection bias of training and testing data (e.g., training on small graphs and testing on large graphs, or training on dense graphs and testing on sparse graphs), distribution deviation is widespread. More importantly, we often observehybrid structure distribution shiftof both scale and density, despite of one-sided biased data partition. The spurious correlations over hybrid distribution deviation degrade the performance of previous GNN methods and show large instability among different datasets. To alleviate this problem, we proposeOOD-GMixupto jointly manipulate the training distribution withcontrollable data augmentationin metric space. Specifically, we first extract the graph rationales to eliminate the spurious correlations due to irrelevant information. Secondly, we generate virtual samples with perturbation on graph rationale representation domain to obtain potential OOD training samples. Finally, we propose OOD calibration to measure the distribution deviation of virtual samples by leveraging Extreme Value Theory, and further actively control the training distribution by emphasizing the impact of virtual OOD samples. Extensive studies on several real-world datasets on graph classification demonstrate the superiority of our proposed method over state-of-the-art baselines.

Graph Contrastive Learning (GCL) with Graph Neural Networks (GNN) has emerged as a promising method for learning latent node representations in a self-supervised manner. Most of existing GCL methods employ random sampling for graph view augmentation and maximize the agreement of the node representations between the views. However, the random augmentation manner, which is likely to produce very similar graph view samplings, may easily result in incomplete nodal contextual information, thus weakening the discrimination of node representations. To this end, this paper proposes a novel trainable scheme from the perspective of node augmentation, which is theoretically proved to be injective and utilizes the subgraphs consisting of each node with its neighbors to enhance the distinguishability of nodal view. Notably, our proposed scheme tries to enrich node representations via a multi-scale contrastive training that integrates three different levels of training granularity, i.e., subgraph level, graph- and node-level contextual information. In particular, the subgraph-level objective between augmented and original node views is constructed to enhance the discrimination of node representations while graph- and node-level objectives with global and local information from the original graph are developed to improve the generalization ability of representations. Experiment results demonstrate that our framework outperforms existing state-of-the-art baselines and even surpasses several supervised counterparts on four real-world datasets for node classification.

Information cascading, referred as the phenomenon of an individual following the behavior of the preceding individual after observing its actions, is prevalent in real social networks and triggers intense research interests for the purpose of monitoring and controlling network epidemics. One of the typical lines of information cascading study belongs to the Influence Maximization Problem, which aims to algorithmically find the optimal seeds that can spread the information to the maximum number of nodes. Regardless of the tremendous efforts made in various algorithm design of finding such optimal seeds, it has not yet been well understood how the absolute influence power of the “optimal” source set affects the ultimate cascading, i.e., under which conditions the seeds are able or unable to influence an substantial fraction of the entire network. Most existing works have investigated the conditions of network scale influence under linear threshold model, where the activation of a node requires a large number of infected neighbors. Instead, in this paper we focus on the case of single source cascading, which is only possible to occur under the independent cascading model. We launch information cascading analysis from two aspects, i.e., the influence scale and network-scale cascading probability. Firstly, percolation analysis of the cascading outcome shows that estimating influence scale is equivalent to solving fixed point equations. Then, we investigate the speed and stability of information cascading based on fixed point analysis, which shows that the information cascading process almost surely terminates within logarithmic time complexity. Furthermore, the results are generalized to the stochastic block model, where we find that network-scale cascading is determined by the spectral radius of the community matrix. The analysis presented in this paper could help us better understand the conditions for different information cascading outcomes.

This paper presents the design, implementation, and evaluation of TaGroup, a fast, fine-grained, and robust grouping technique for RFIDs. It can achieve a nearly 100% accuracy in distinguishing multiple groups of closely located RFIDs, within only a few seconds. It would benefit many inventory tracking applications, such as self-checkout in retails and packaging quality control in logistics. We make two technical innovations. First, we propose a novel method which can measure the channels between multiple pairs of commercial RFID tags simultaneously, and then estimate the proximity relations between them based on the channel information. Second, we introduce a spatio-temporal graph model which captures a full picture of proximity relations among all the tags, based on which TaGroup can perform a robust grouping of the tags. These two designs together boost the grouping speed and accuracy of TaGroup. Our experiments show that in grouping 120 tags into 4 closely located groups, TaGroup can achieve a nearly 100% accuracy, at the cost of only 2 seconds.

This paper studies connectivity maintenance in uncertain networks under adversarial attack, where a defender conceals crucial links to prevent the largest connected component from being decomposed by an attacker. In contrast with its static counterpart, connectivity maintenance in uncertain networks involves additional probing on links to determine their existence. Therefore, by modeling an uncertain network as a random graph with each link associated with an existence probability and a probing cost, our goal is to design a defensive strategy for link selection that maximizes the expected size of the largest remaining connected component with the minimum expected probing cost, and moreover, the strategy should be independent of the attacking patterns. To this end, we first unravel the computational complexity of the problem by proving its NP-hardness, and then propose optimal defensive strategies based on dynamic programming and multi-objective optimization. Due to the prohibitive computational cost of optimality, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity, in which the first one is a heuristic approach that quantifies the link vulnerability through an analogy from the degree centrality of a vertex in static networks to the connectivity weight of a link in uncertain networks, and the second one is an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario and has a constant approximation ratio. Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

This paper presents dual-band Wi-Fi backscatter (DBscatter), which is the first system supporting 2.4GHz and 5GHz Wi-Fi backscatter simultaneously in a single tag. Our key insight is that most existing Wi-Fi devices communicate in the clean 5GHz band. The 5GHz band provides more chances for ”free riding” with less interference, while the 2.4GHz band presents better NLoS performance. DBscatter combines the strengths of the existing 2.4GHz band with the unexplored 5GHz backscatter in a unified design, developing a robust and high-throughput ambient Wi-Fi backscatter system. We make the following technical contributions: (1) We design a dual-band RF frontend to support dual-band Wi-Fi signals. (2) We propose a tag data demodulation algorithm, which merges the common phase error in multi-antenna received signals, improving the tag transmission reliability while reducing the number of required receivers. (3) We build a prototype of DBscatter system using COTS FPGAs and SDRs. Compared to TiScatter and FreeRider, DBscatter boosts Wi-Fi backscatter throughput by 3.74X and 7.35X, and energy efficiency by 1.78X and 1.38X respectively.

Along with the proliferation of IoT devices, people have a lot of concerns on the privacy issues brought by them. Existing solutions, employing encryption or trying to hide the communication in PHY layer, often suffer from the limited capability of IoT devices. To address this issue, we propose Rustle, an acoustic communication design which builds covert connection among IoT devices using random noise. Noise signal can be easily generated and exchanged by the widely used speakers and microphones on IoT devices. Based on a fine-grained control of signal’s wave shape, Rustle generates a series of mutually uncorrelated random signals that contain “hidden patterns” to embed information. Extensive evaluations demonstrate that Rustle can achieve a lower than 1% BER while the eavesdropper’s error rate on detecting the signal is higher than 80%.

We in this paper present TiSee, an RFID-based sensing system that supports miniature robots to perform agile tasks in everyday environments. TiSee’s unique capability is that it uses a single arbitrarily-deployed antenna to locate a target with sub-cm-level accuracy and identify its orientation to within few degrees. Compared with existing solutions which rely on either antenna arrays or multiple RFID readers, TiSee is cheap, compact, and applicable to miniature robots. The idea of TiSee is to stick an RFID tag on the robot (or its gripper) and use it as a moving “antenna” to locate the tags on the target. The core of this design is a novel technique which can build a “channel” between two commercial RFID tags. Such an inter-tag channel is proved to be highly sensitive to the change in inter-tag distance and is resistant to multipath. By leveraging this channel and the mobility of the robot, we emulate an antenna array and use it for fine-grained localization and orientation estimation. Our experiments show that TiSee achieves a median accuracy of 9.5mm and 3.1° in 3D localization and orientation estimation. TiSee brings an eye-in-hand “camera” to miniature robots, supporting them to perform agile tasks in dark, cluttered, and occluded settings.

This paper presents MobiScatter, which enhances capacity of CSS based backscatter networks for accommodating drone-carried access points (APs). CSS based backscatter design has favorable features including long range and high concurrency. However, the concurrency of the network can be reduced by 34% when the drone-carried AP is introduced due to the mobility and fast fading. In order to maintain high concurrency, MobiScatter presents a series of new designs. In particular, we propose to enhance concurrency of the CSS based backscatter network with symmetric upchirps and downchirps, which neutralizes the impact of imperfect frequency orthogonality. Then, to mitigate the impact of fast fading on decoding, we present a novel half-period chirp modulation scheme for crossed chirps. Finally, we provide a power management method for tags by controlling transmitting time of chirps. We construct a MobiScatter prototype, which contains a drone-carried AP implemented with a mobile USRP and 200 tags. We deploy those tags in an area of$200 m\times 180 m$on a meadow. Experimental results show that MobiScatter can support 160 concurrent backscatter transmissions when the AP moves at$15 m/s$.

This paper for the first time demonstrates how to enable OFDMA in Wi-Fi backscatter for capacity and concurrency enhancement. With our design, the excitation signal is reflected, modulated and shifted to lie in the frequency band of the OFDM subcarrier by the tag; OFDMA is realized by coordinating tags to convey information to the receiver with orthogonal subcarriers concurrently through backscatter. The crux of the design is to achieve strict synchronization among communication components, which is more challenging than in regular OFDMA systems due to the more prominent hardware diversity and uncertainty for backscattering. We reveal how the subtle synchronization scenarios particularly for backscattering can incur system offsets, and present a series of novel designs for the excitation signal transmitter, tag, and receiver to address the issue. We build a prototype in 802.11g OFDM framework to validate our design. Experimental results show that our system can achieve 5.2-$16Mbps$aggregate throughput by allowing 48 tags to transmit concurrently, which is 1.45-$5\times $capacity and$48\times $concurrency compared with the existing design respectively. We also design an OFDMA tag IC, with the corresponding simulation and numerical analysis results show that the tag’s power consumption is in tens of$\mu W$.

This article studies time-sensitive multicast in wireless sensor networks (WSNs) with link uncertainty, where information from the source needs to be delivered to multiple receivers within an imposed delay constraint. Prior art on static WSNs minimizes the multicast delay via the construction of a multicast tree that approximates the Steiner tree in length, which, however, may be invalidated by the time-varying network topology of WSNs with uncertain link states. Moreover, for multicast in WSNs with link uncertainty, the possible link failure necessitates a suitable measurement of the uncertain communication distance and calls for the performance guarantee in both delay and delivery ratio. In this work, by modeling a WSN as a random graph with each link associated with a transmission probability, we propose FlowerCast, an efficient multicast scheme, to jointly minimize the expected multicast delay and to maximize the expected delivery ratio of multicast under delay constraint. The core of FlowerCast is to quantify the uncertain communication distance by the expected transmission delay of a time-varying path, based on which a delay-optimal multicast tree is constructed in accordance with the directionality of delay. Candidate paths with a high expected delivery ratio and low expected delay are then selected in a distributed manner to conditionally connect adjacent multicast members and thus transform the multicast tree into a multicast flower. Despite the NP-hardness of optimal candidate paths’ addition, the transformation with the highest expected delivery ratio of multicast under delay constraint can be guaranteed through a pseudo-polynomial time derandomization-based greedy approach. We further demonstrate the time and energy efficiency of FlowerCast through asymptotic analysis. To make full use of the possible overlapping links in a multicast flower, a hybrid routing strategy is presented to wisely switch between sequential routing and synchronous routing for extra enhancement of the multicast performance. Extensive experiments on various datasets verify the superiority of FlowerCast and hybrid routing over baselines and indicate their wide applicability to practical scenarios.

In recent years, multi-agent reinforcement learning (MARL) has presented impressive performance in various applications. However, physical limitations, budget restrictions, and many other factors usually impose constraints on a multi-agent system (MAS), which cannot be handled by traditional MARL frameworks. Specifically, this paper focuses on constrained MASes where agents work cooperatively to maximize the expected team-average return under various constraints on expected team-average costs, and develops a constrained cooperative MARL framework, named DeCOM, for such MASes. In particular, DeCOM decomposes the policy of each agent into two modules, which empowers information sharing among agents to achieve better cooperation. In addition, with such modularization, the training algorithm of DeCOM separates the original constrained optimization into an unconstrained optimization on reward and a constraints satisfaction problem on costs. DeCOM then iteratively solves these problems in a computationally efficient manner, which makes DeCOM highly scalable. We also provide theoretical guarantees on the convergence of DeCOM's policy update algorithm. Finally, we conduct extensive experiments to show the effectiveness of DeCOM with various types of costs in both moderate-scale and large-scale (with 500 agents) environments that originate from real-world applications.

Recent advances in large pre-trained models showed promising results in few-shot learning. However, their generalization ability on two-dimensional Out-of-Distribution (OoD) data, i.e., correlation shift and diversity shift, has not been thoroughly investigated. Researches have shown that even with a significant amount of training data, few methods can achieve better performance than the standard empirical risk minimization method (ERM) in OoD generalization. This few-shot OoD generalization dilemma emerges as a challenging direction in deep neural network generalization research, where the performance suffers from overfitting on few-shot examples and OoD generalization errors. In this paper, leveraging a broader supervision source, we explore a novel Bayesian cross-modal image-text alignment learning method (Bayes-CAL) to address this issue. Specifically, the model is designed as only text representations are fine-tuned via a Bayesian modelling approach with gradient orthogonalization loss and invariant risk minimization (IRM) loss. The Bayesian approach is essentially introduced to avoid overfitting the base classes observed during training and improve generalization to broader unseen classes. The dedicated loss is introduced to achieve better image-text alignment by disentangling the causal and non-casual parts of image features. Numerical experiments demonstrate that Bayes-CAL achieved state-of-the-art OoD generalization performances on two-dimensional distribution shifts. Moreover, compared with CLIP-like models, Bayes-CAL yields more stable generalization performances on unseen classes. Our code is available at https://github.com/LinLLLL/BayesCAL.

Yi Xu, Shuqian Sheng, Jiexing Qi, Luoyi Fu, Zhouhan Lin, Xinbing Wang, Chenghu Zhou. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Researchers usually come up with new ideas only after thoroughly comprehending vast quantities of literature.The difficulty of this procedure is exacerbated by the fact that the number of academic publications is growing exponentially.In this study, we devise a framework based on concept co-occurrence for academic idea inspiration, which has been integrated into a research assistant system.From our perspective, the fusion of two concepts that co-occur in an academic paper can be regarded as an important way of the emergence of a new idea.We construct evolving concept graphs according to the co-occurrence relationship of concepts from 20 disciplines or topics.Then we design a temporal link prediction method based on masked language model to explore potential connections between different concepts.To verbalize the newly discovered connections, we also utilize the pretrained language model to generate a description of an idea based on a new data structure called co-occurrence citation quintuple.We evaluate our proposed system using both automatic metrics and human assessment.The results demonstrate that our system has broad prospects and can assist researchers in expediting the process of discovering new ideas.1 * Luoyi Fu is the corresponding author. 1 The project is publicly available for research purpose https://github.com/xyjigsaw/Kiscovery.

Tianhang Zhang, Lin Qiu, Qipeng Guo, Cheng Deng, Yue Zhang, Zheng Zhang, Chenghu Zhou, Xinbing Wang, Luoyi Fu. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Various tasks are reformulated as multi-label classification problems, in which the binary cross-entropy (BCE) loss is frequently utilized for optimizing well-designed models. However, the vanilla BCE loss cannot be tailored for diverse tasks, resulting in a suboptimal performance for different models. Besides, the imbalance between redundant negative samples and rare positive samples could degrade the model performance. In this paper, we propose an effective Asymmetric Polynomial Loss (APL) to mitigate the above issues. Specifically, we first perform Taylor expansion on BCE loss. Then we ameliorate the coefficients of polynomial functions. We further employ the asymmetric focusing mechanism to decouple the gradient contribution from the negative and positive samples. Moreover, we validate that the polynomial coefficients can recalibrate the asymmetric focusing hyperparameters. Experiments on relation extraction, text classification, and image classification show that our APL loss can consistently improve performance without extra training burden.1

Real-world data usually exhibits a long-tailed distribution, with a few frequent labels and a lot of few-shot labels. The study of institution name normalization is a perfect application case showing this phenomenon: there are many institutions worldwide, with enormous variations of their names in the publicly available literature. In this work, we first collect a large-scale institution name normalization dataset containing over 25k classes whose frequencies are naturally long-tail distributed. We construct our test set from four different subsets: many-, medium-, and few-shot sets, as well as a zero-shot open set, which are meant to isolate the few-shot and zero-shot learning scenarios from the massive many-shot classes. We also replicate several important benchmarks on our data, covering a wide range from search-based methods to neural network methods. Further, we propose our specially pretrained, BERT-based model that shows better out-of-distribution generalization on few-shot and zero-shot test sets. Compared to other datasets focusing on the long-tailed phenomenon, our dataset has one order of magnitude more training data than the largest existing long-tailed datasets and is naturally long-tailed rather than manually synthesized. We believe it provides an important and different scenario to study this problem. To our best knowledge, this is the first natural language dataset that focuses on this long-tailed and open-set classification problem.1

Zero-shot coordination in cooperative artificial intelligence (AI) remains a significant challenge, which means effectively coordinating with a wide range of unseen partners. Previous algorithms have attempted to address this challenge by optimizing fixed objectives within a population to improve strategy or behaviour diversity. However, these approaches can result in a loss of learning and an inability to cooperate with certain strategies within the population, known as cooperative incompatibility. To address this issue, we propose the Cooperative Open-ended LEarning (COLE) framework, which constructs open-ended objectives in cooperative games with two players from the perspective of graph theory to assess and identify the cooperative ability of each strategy. We further specify the framework and propose a practical algorithm that leverages knowledge from game theory and graph theory. Furthermore, an analysis of the learning process of the algorithm shows that it can efficiently overcome cooperative incompatibility. The experimental results in the Overcooked game environment demonstrate that our method outperforms current state-of-the-art methods when coordinating with different-level partners. Our demo is available at https://sites.google.com/view/cole-2023.

We study the online restless bandit problem, where each arm evolves according to a Markov chain independently, and the reward of pulling an arm depends on both the current state of the corresponding Markov chain and the pulled arm. The agent (decision maker) does not know the transition functions and reward functions, and cannot observe the states of arms even after pulling. The goal is to sequentially choose which arms to pull so as to maximize the expected cumulative rewards collected. In this paper, we propose TSEETC, a learning algorithm based on Thompson Sampling with Episodic Explore-Then-Commit. The algorithm proceeds in episodes of increasing length and each episode is divided into exploration and exploitation phases. During the exploration phase, samples of action-reward pairs are collected in a round-robin fashion and utilized to update the posterior distribution as a mixture of Dirichlet distributions. At the beginning of the exploitation phase, TSEETC generates a sample from the posterior distribution as true parameters. It then follows the optimal policy for the sampled model for the rest of the episode. We establish the Bayesian regret bound $\tilde {\mathcal{O}}(\sqrt{T})$ for TSEETC, where $T$ is the time horizon. We show through simulations that TSEETC outperforms existing algorithms in regret.

User review data is considered as auxiliary information to alleviate the data sparsity problem and improve the quality of learned user/item or interaction representations in review-based recommender systems. However, existing methods usually model user-item interactions in a holistic manner and neglect the entanglement of the latent intents behind them, e.g., price, quality, or appearance, resulting in suboptimal representations and reducing interpretability. In this paper, we propose a Self-supervised Graph Disentangled Networks for review-based recommendation (SGDN), to separately model the user-item interactions based on the latent factors through the textual review data. To this end, we first model the distributions of interactions over latent factors from both semantic information in review data and structural information in user-item graph data, forming several factor graphs. Then a factorized message passing mechanism is designed to learn disentangled user/item and interaction representations on the factor graphs. Finally, we set an intent-aware contrastive learning task to alleviate the sparsity issue and encourage disentanglement through dynamically identifying positive and negative samples based on the learned intent distributions. Empirical results over five benchmark datasets validate the superiority of SGDN over the state-of-the-art methods and the interpretability of learned intent factors.

Data with missing values is ubiquitous in many applications. Recent years have witnessed increasing attention on prediction with only incomplete data consisting of observed features and a mask that indicates the missing pattern. Existing methods assume that the training and testing distributions are the same, which may be violated in real-world scenarios. In this paper, we consider prediction with incomplete data in the presence of distribution shift. We focus on the case where the underlying joint distribution of complete features and label is invariant, but the missing pattern, i.e., mask distribution may shift agnostically between training and testing. To achieve generalization, we leverage the observation that for each mask, there is an invariant optimal predictor. To avoid the exponential explosion when learning them separately, we approximate the optimal predictors jointly using a double parameterization technique. This has the undesirable side effect of allowing the learned predictors to rely on the intra-mask correlation and that between features and mask. We perform decorrelation to minimize this effect. Combining the techniques above, we propose a novel prediction method called StableMiss. Extensive experiments on both synthetic and real-world datasets show that StableMiss is robust and outperforms state-of-the-art methods under agnostic mask distribution shift.

Overlapping gradient communication with backward computation is a popular technique to reduce communication cost in the widely adopted data parallel S-SGD training. However, the resource contention between computation and All-Reduce communication in GPU-based training reduces the benefits of overlap. With GPU cluster network evolving from low bandwidth TCP to high speed networks, more GPU resources are required to efficiently utilize the bandwidth, making the contention more noticeable. Existing communication libraries fail to account for such contention when allocating GPU threads and have suboptimal performance. In this paper, we propose to mitigate the contention by balancing the overlapped computation and communication time. We formulate an optimization problem that decides the communication thread allocation to reduce overall backward time. We develop a dynamic programming based near-optimal solution and extend it to co-optimize thread allocation with tensor fusion. We conduct simulated study and real-world experiment using an 8-node GPU cluster with 50Gb RDMA network training four representative DNN models. Results show that our method reduces backward time by 10%-20% compared with Horovod-NCCL, by 6%-13% compared with tensor-fusion-optimization-only methods. Simulation shows that our method achieves the best scalability with a training speedup of 1.2x over the best-performing baseline as we scale up cluster size.

Given an aftermath of an information spreading, i.e., an infected network GNafter the propagation of malicious rumors, malware or viruses, how can we identify the sources of the cascade? Answering this problem, which is known as the multiple source detection (MSD) problem, is critical whether for forensic use or insights to prevent future epidemics.Despite the recent considerable effort, most of them are built on a preset propagation model, which limits their application range. Some attempts aim to break this limitation via a label propagation scheme where the nodes surrounded by a large proportion of infected nodes are highlighted. Nonetheless, the detection accuracy may suffer since the node labels are simply integers with all infected or uninfected nodes sharing the same initialization setting respectively, which fall short of sufficiently distinguishing their structural properties. To this end, we propose a community based label propagation (CLP) framework that locates multiple sources through exploiting the community structures formed by infected subgraphs of different sources. Besides, CLP tries to enhance the detection accuracy by incorporating node prominence and exoneration effects, namely the nodes surrounded by larger proportions of infected nodes are more likely to be sources, and the uninfected nodes or infected ones in neighboring community hold the key in exonerating an infected node from being the source. As such, CLP is applicable in more propagation models, and is provably convergent. Experiments on both synthetic and real-world networks further validate the superiority of CLP to the state-of-the-art, boosting the F-score from few percents to approximately 68× in large-scale networks.

Due to the universality of graph data, node classification shows its great importance in a wide range of real-world applications. Despite the successes of Graph Neural Networks (GNNs), GNN based methods rely heavily on rich connections and perform poorly on low-degree nodes. Since many real-world graphs follow a long-tailed distribution in node degrees, they suffer from a substantial performance bottleneck as a significant fraction of nodes is of low degree. In this paper, we point out that under-represented self-representations and low neighborhood homophily ratio of low-degree nodes are two main culprits. Based on that, we propose a novel method Grace which improves the node representation by self-distillation, and increases neighborhood homophily ratio of low-degree nodes by graph completion. To avoid error propagation of graph completion, label propagation is further leveraged. Experimental evidence has shown that our method well supports real-world graphs, and is superior in balancing degree-related bias and overall performance on node classification tasks.

This paper tries to answer a question: "Can we achieve spatial-selective transmission on IoT devices?" A positive answer would enable more secure data transmission among IoT devices. The challenge, however, is how to manipulate signal propagation without relying on beamforming antenna arrays which are usually unavailable on low-end IoT devices.

This paper presents the design, implementation, and evaluation of TaGroup, a fast, fine-grained, and robust grouping technique for RFIDs. It can achieve a nearly 100% accuracy in distinguishing multiple groups of closely located RFIDs, within only a few seconds. It would benefit many inventory tracking applications, such as self-checkout in retails and packaging quality control in logistics.

Cloud providers, such as AWS and Azure, have started providing 5G services on their cloud infrastructure. In this paper, we present the design and implementation of X-Plane, a system that uses commercial programmable ASICs and DRAM servers on today's cloud infrastructure to implement high-performance 5G User Plane Function (UPF). Building X-Plane is hard because we need to address the following challenges: consistency issues when concurrently accessing UPF state data, slow UE table lookup due to repetitive and numerous Packet Detection Rule (PDR) matching, and the need to handle out-of-order packets from disconnected UEs. X-Plane addresses these challenges by designing three novel technologies: concurrent state data access protocol, fast flow table and paging buffer for handling out-of-order packets. We demonstrate its feasibility and practicality with our implementation on a Tofino-based programmable ASIC. Our evaluation shows that X-Plane can support over ~490Gbps throughput per ASIC pipeline, over 10 million UEs, and finish packet processing within predictable ~4 us on average.

Reconfigurable reflective arrays can be used to program the radio propagation environment in order to form favorable wireless channel conditions. Previous designs have used large-scale arrays containing hundreds to thousands of reflecting elements located external to the receiving node, with the reflection coefficients of all array elements managed by a controller. However, these designs can be costly to deploy and are challenging to quickly adapt to the time-varying nature of wireless channels caused by mobility.

Road surface markings, like symbols and line markings, are vital traffic infrastructures for driving safety and efficiency. However, real-world conditions can impair the utility of existing road markings. For example, adverse weather conditions such as snow and rain can quickly obliterate visibility.

Bundle recommendation aims to recommend a bundle of items to users as a whole with user-bundle (U-B) interaction information, and auxiliary user-item (U-I) interaction and bundle-item affiliation information. Recent methods usually use two graph neural networks (GNNs) to model user's bundle preferences separately from the U-B graph (bundle view) and U-I graph (item view). However, by conducting statistical analysis, we find that the auxiliary U-I information is far underexplored due to the following reasons: 1) Loosely combining the predicted results cannot well synthesize the knowledge from both views. 2) The local U-B and U-I collaborative relations might not be consistent, leading to GNN's inaccurate modeling of user's bundle preference from the U-I graph. 3) The U-I interactions are usually modeled equally while the significant ones corresponding to user's bundle preference are less emphasized.

Verifying the correctness of computation without revealing the input is a critical issue intensively studied in real-world applications. The recent surge of zero knowledge arguments has been focusing on its efficiency and practicality. Among them, GKR-based arguments have received wide attention and become the foundation of many zero-knowledge proof protocols. However, GKR-based protocols are restricted to layered arithmetic circuits. We proposeTerrace, a new, efficient zero-knowledge argument system for general circuits, based on GKR. By dynamically patching cross-layer claims to the original circuit for verification instead of verifying those claims separately,Terraceis able to reduce the total circuit size and thus enjoys a logarithmic factor less verification time and proof size.Terraceis further extended to include the verification of non-arithmetic operations by rewriting those claims in the multilinear extension form. Experimental results demonstrate that Terrace enjoys a competitive performance on efficiency, and shows great promise in enabling low-cost verification of neural networks.

Differential mymargin privacy has been deployed to machine learning platforms to preserve the privacy of data in use. A long neglected but important fact is that data privacy is a non-replenishable resource and should be carefully scheduled to maximize its utility gain. In this work, we propose a new privacy budgeting system—DPlanner, which estimates data blocks’ importance to queries and assigns fractional privacy budget to those data blocks contributing most to a query. The scheduler is novelly designed to include two-fold randomness, which satisfies differential privacy with tight budgets, at the same time guarantees the expected utility in the worst-case query sequence when queries arrive in an online fashion. Experiments in a variety of machine learning settings have shown that our DPlanner outperforms the state-of-the-art schedulers by serving at least 25% more queries, or reducing the total privacy consumption by over 50%.

Social network de-anonymization, which refers to re-identifying users by mapping an anonymized network to a correlated real-name network, is an important problem in network science that has received intensive study. Although different de-anonymization algorithms have been proposed, the performance limit of any algorithm on a de-anonymization problem remains less explored. In this paper, we investigate the Optimal De-Anonymization Yield (ODAY), i.e., the maximum extent to which the network can be de-anonymized, of a given de-anonymization problem. Specifically, due to the uncertainty of the true mapping, we define ODAY as the maximum expected number of correctly mapped nodes, and propose general approaches for its quantification in general networks. Therefore, ODAY can be viewed as a quantitative and non-asymptotic concretization of the concept of network de-anonymizability, which is mostly investigated in an asymptotic manner in prior art. Inspired by the effect of network symmetry on the de-anonymizability, we show that for a graph pair with arbitrary topologies, ODAY equals the maximum diagonal sum of a matching probability matrix generated from graph homomorphisms. Due to the exponential complexity of enumerating all the possible homomorphisms, we further obtain an upper bound of ODAY by counting the orbits of each of the two graphs, which significantly reduces the computational cost. Two case studies apply our general findings on symmetry and ODAY to specific network models, and a sampling-based algorithm framework is proposed for ODAY calculation in practice. Extensive experiments are performed to validate our findings. To the best of our knowledge, this work is the first effort that quantifies the de-anonymizability of general networks in a non-asymptotic manner from the perspective of network symmetry, and thus sheds light on privacy enhancement for social network design.

Recent years have witnessed a vastly increasing popularity of location-based social networks (LBSNs), which facilitates studies on the next Point-of-Interest (POI) recommendation problem. A user’s POI visiting behavior shows the sequential transition correlation with previous successive check-ins and the global spatial-temporal correlation with those check-ins that happened a long time ago at a similar time of day and in geographically close areas. Although previous POI recommendation methods attempted to capture these two correlations, several limitations remain to be solved: (1) RNNs are widely adopted to capture the sequential transition correlation, whereas training an RNN is rather time-consuming given the long input check-in sequence. (2) The pairwise proximities on time of day and geographical area of check-ins are crucial for global spatial-temporal correlation learning, but have not been comprehensively considered by previous methods. To tackle these issues, we propose a novel next POI recommendation framework named STA-TCN. Specifically, instead of RNNs, STA-TCN augments the Temporal Convolutional Network with gated input injection to learn sequential transition correlation. Furthermore, STA-TCN fuses two novel grid-difference and time-sensitivity learning mechanisms with attention network to learn the pairwise spatial-temporal proximities among a user’s check-ins. Extensive experiments are conducted on two large-scale real-world LBSN datasets, and the results show that STA-TCN outperforms the best state-of-the-art baseline with an average improvement of 9.71% and 7.88% on hit rate and normalized discounted cumulative gain, respectively.

Self-supervised graph-level representation learning has recently received considerable attention. Given varied input distributions, jointly learning graphs’ unique and common features is vital to downstream tasks. Inspired by graph contrastive learning (GCL), which targets maximizing the agreement between graph representations from different views, we propose an Ada ptive self-supervised framework, Ada-MIP, considering both M utual I nformation between views (unique features) and inter-graph P roximity (common features). Specifically, Ada-MIP learns graphs’ unique information through a learnable and probably injective augmenter, which can acquire more adaptive views compared to the augmentation strategies applied by existing GCL methods; to learn graphs’ common information, we employ graph kernels to calculate graphs’ proximity and learn graph representations among which the precomputed proximity is preserved. By sharing a global encoder, graphs’ unique and common information can be well integrated into the graph representations learned by Ada-MIP. Ada-MIP is also extendable to semi-supervised scenarios, with our experiments confirming its superior performance in both unsupervised and semi-supervised tasks.

The drastic increase of metro passengers in recent years inevitably causes the overcrowdedness in the metro systems. Accurately predicting passenger flows at metro stations is critical for efficient metro system management, which helps alleviate such overcrowdedness. Compared to the prevalent next-step prediction, multi-step passenger flow prediction could prominently increase the prediction duration and reveal finer-grained passenger flow variations, which better helps metro system management. Thus, in this paper, we address the problem ofmulti-step metro station passenger (MSP) flow prediction. In light of MSP flows’ unique spatial-temporal characteristics, we proposeSTP-TrellisNets+, which for the first time augments the newly-emerged temporal convolutional frameworkTrellisNetfor multi-step MSP flow prediction. The temporal module of STP-TrellisNets+ (namedCP-TrellisNetsED) employs a Closeness TrellisNet followed by aPeriodicity TrellisNets-based Encoder-Decoder (P-TrellisNetsED)to jointly capture the short- and long-term temporal correlation of MSP flows. In parallel to CP-TrellisNetsED, its spatial module (namedGC-TrellisNetsED) adopts a novel transfer flow-based metric to characterize the spatial correlation among MSP flows, and implements another TrellisNetsED on multiplediffusion graph convolutional networks (DGCNs)in time-series order to capture the dynamics of such spatial correlation. Extensive experiments with two large-scale real-world automated fare collection datasets demonstrate that STP-TrellisNets+ outperforms the state-of-the-art baselines.

Influence maximization through social networks has aroused tremendous interests nowadays. However, people’s various expressions or feelings about a same idea often cause ambiguity via word of mouth. Consequently, the problem of how to maximize the spread of “effective information” still remains largely open. In this paper, we consider a practical setting where ideas can deviate from their original version to invalid forms during message passing, and make the first attempt to seek a union of users that maximizes the spread of effective influence, which is formulated as an Influence Maximization with Information Variation (IMIV) problem. To this end, we model the information as a vector, and quantify the difference of two arbitrary vectors as a distance by a matching function. We further establish a process where such distance increases with the propagation and ensure the recipient whose vector distance is less than a threshold can be effectively influenced. Due to the NP-hardness of IMIV, we greedily select users that can approximately maximize the estimation of effective propagation. Especially, for networks of small scales, we derive a condition under which all the users can be effectively influenced. Our models and theoretical findings are further consolidated through extensive experiments on real-world datasets.

A crucial privacy-driven issue nowadays is re-identifying anonymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through varied cost functions. However, many cost functions are empirically proposed without sufficient theoretical support. For some other works probing the theoretical bound, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to minimize the cost functions. Besides, only few prior works have discussed the de-anonymization of social networks with communities. We address those concerns in a social network modeling parameterized by community structures that can be leveraged as side information for de-anonymization. Based on the Maximum A Posteriori (MAP) estimation, our first contribution is a series of MAP-based cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized. We prove the general multiplicative inapproximability and thus propose two heuristics, which, respectively, enjoy an$\epsilon$-additive approximation and a conditional optimality in carrying out successful user re-identification. Our theoretical findings are also empirically validated under classical synthetic and real-wrold social networks. Both theoretical and empirical observations manifest the importance of community in enhancing privacy inferencing.

With the increasing popularity of mobile devices, each user is able to conveniently acquire messages from others, and share diverse forms of information, like texts, images, or videos through online mobile apps. The full freedom of speech makes a great amount of truth (i.e., true information) and rumor (i.e., false information) propagate rapidly in a hybrid way through mobile platforms. As a huge variety of information floods pouring over us each day, identifying the authenticity of massive events becomes a necessary task to maintain the stability of Mobile Social Networks (MSNs). An important way to realize it is to trace their diffusions and make judgements according to the reliability of sources. With this regard, this paper proposes a diffusion model that characterizes the simultaneous diffusion of both truth and rumor in realistic MSNs, and makes the first attempt to figure out their respective sources. The problem of interest can be stated as: Given an outcome of cascade of both truth and rumor in MSNs, i.e., a set of nodes that might be the ignorant, the spreader of truth or rumor, or simply the silent receiver, how can we infer both truth sources and rumor sources? Different from previous sources detection works considering single type of nodes, the interplay between truth diffusions and rumor diffusions makes the conventional methods not work. To answer this question, we aim to maximize thesimilarity index, i.e., the number of nodes possessing the same states between the resulting network triggered by our estimated sources with the proposed diffusion model and the given observation network. Compared with existing techniques to trace diffusions of truth or rumor, it is much harder to find two kinds of sets at the same time, including truth sources and rumor sources, due to two primary reasons: (i) our biset optimization makes the submodularity techniques fail; (ii) our objective function is proven to be non-bisubmodular. To overcome above limitations, we first convert the objectivesimilarity indexinto a bisubmodular function by virtue of set covering. Based on this, we propose an approximation algorithm called Truth and Rumor Sources Detection (TRSD) algorithm via multiple reverse samplings with a provable$\frac{1}{4(1+\epsilon)^2}$approximation ratio. Further, a novel “time reversal” sources optimization strategy is proposed to converge the number of output sources from TRSD to a steady state. The effectiveness of our models and algorithms are empirical validated in two various datasets, from which we observe an up to 15% ofsimilarity indexgain as well as a narrowed down gap 0.6% to the ground truth.

This paper presents BatchQR, a mobile APP that can batch read densely arranged QR codes attached to caps of the tubes and vials in clinical and biological labs. BatchQR could work in two modes: photo mode and preview mode, which are respectively suitable for scenarios that favor one-time batch processing capacity and real-time tracking performance. For the photo mode, we first propose an IFFT based lightweight code detection mechanism, which can adaptively adjust operating parameters to identify densely arranged QR codes in practice. We propose an image refocus mechanism to deal with blurs/distorts that may appear in the photo, and a lightweight learning based classifier to filter out falsely detected QR codes. We further optimize BatchQR by enabling batch reading in the preview mode of the camera, which is more in line with common usage habits. To this end, we develop a QR code tracking algorithm based on Kalman filtering, which keeps track of each code image dynamically. We also design a parallel acceleration mechanism based on multi-core CPU and GPU, which significantly mitigates the end-to-end delay. Comprehensive experimental results show that BatchQR can read up to 160 Version 1-H QR codes in one shot, with 95 percent accuracy and 100-400ms delay, which is only 0.1 percent of the time consumed by the regular QR code reader in the same situation.

Recent years have witnessed the increasing popularity of electric buses (e-buses) around the globe due to their environment friendly nature. However, various factors, such as the prohibitive purchasing costs and the scarcity of large-scale charging facilities, hinder the wider adoption of e-buses. Thus, to effectively cut the cost of building and maintaining urban e-bus systems, we optimize the dispatching strategy for urban e-bus systems to satisfy public transportation demands with the minimum e-bus fleet. Specifically, we propose to systematically exploit at city-scale cross-line dispatching, a smart dispatching strategy allowing one bus to serve multiple bus lines when necessary. Technically, we construct a novel and generalizable graph-theoretic model for urban e-bus systems integrating e-buses non-negligible charging time, the spatio-temporal constraints of bus trips, and various other real-world factors. We prove that it is NP-hard, and has no$(2-\epsilon)$-approximation algorithm. Next, we propose a polynomial-time algorithm solving the problem with a guaranteed approximation ratio. Furthermore, we conduct extensive experiments on a large-scale real-world bus dataset from Shenzhen, China, which validate the effectiveness of our algorithms. As shown by our experimental results, to serve 300 bus lines, our dispatching strategy needs 38.2% less e-buses than the one currently used in practice.

The omnipresence of information cascading process in mobile social networking applications makes the identification of a small set$S$of influential users, which is widely believed to trigger the information outbreak, always an crucial issue in various applications such as the mobile advertising and viral marketing. Formulated as Influence maximization (IM) in 2003, this NP-hard problem has received a multitude of studies with diverse angles. However, these works often unable to provide reliable solutions, due to the loss of an exact metric for evaluating users’ contributions on information cascading in the state-of-the-art sampling based IM schemes. In this paper, we evaluate users in IM based on the collective influence (CI), a metric on the structural features of the users in network graph that reflects the contributions of the users’ neighborhoods on shaping collective dynamics of the users over the whole network. For conducting the influencer identification under probabilistic diffusion model based on the CI, we specify a quantified structural feature of the most influential users from the scope of diffusion over the whole network, and reveal that the structural influence power (CI value) of each user is a weighted cumulation of the diffusion probabilities from neighbors within certain hops. Utilizing CI, we design a novel algorithm which identifies the influencers via iteratively choosing the users with top CI values. Moreover, we point out that directly computing CI values requires to traverse the network which is originally represented by a high-dimensional matrix, and leads to huge complexity of influencer identification. To improve scalability, we further trade precision for efficiency by incorporating network embedding, a dimensionality reduction technology for networks, into algorithm design, and propose a minor variant, where CI is jointly recapitulated by low-dimensional user representations and user degrees. The superiority of our algorithms is empirically validated over 8 datasets, with an increment in influence size up to 50 percent and a comparable or even less running time comparing with existing baselines.

With the popularity of deep learning applications, the privacy of training data has become a major concern as the data sources may be sensitive. Recent studies have found that deep learning models are vulnerable to privacy attacks, which are able to infer private training data from model parameters. To mitigate such attacks, differential privacy has been proposed to preserve data privacy by adding randomized noise to these models. However, since deep learning models usually consist of a large number of parameters and complicated layered structures, an overwhelming amount of noise is often inserted, which significantly degrades model accuracy. We seek a better tradeoff between model utility and data privacy, by choosing directions of noise w.r.t. the utility subspace. We propose an optimized mechanism for differentially-private stochastic gradient descent, and derive a closed-form solution. The form of the solution makes the mechanism ready to be deployed in real-world deep learning systems. Experimental results on a variety of models, datasets, and privacy settings show that our proposed mechanism achieves higher accuracies at the same privacy guarantee compared to the state-of-the-art methods. Further, we extend the privacy guarantee to a mutual information bound, and propose a general form to the utility-privacy problem.

The wide deployment of machine learning algorithms has become a severe threat to user data privacy. As the learning data is of high dimensionality and high orders, preserving its privacy is intrinsically hard. Conventional differential privacy mechanisms often incur significant utility decline as they are designed for scalar values from the start. We recognize that it is because conventional approaches do not take the data structural information into account, and fail to provide sufficient privacy or utility. As the main novelty of this work, we proposeMatrix Gaussian Mechanism(MGM), a new$ (\epsilon,\delta)$-differential privacy mechanism for preserving learning data privacy. By imposing the unimodal distributions on the noise, we introduce two mechanisms based on MGM with an improved utility. We further show that with the utility space available, the proposed mechanisms can be instantiated with optimized utility, and has a closed-form solution scalable to large-scale problems. We experimentally show that our mechanisms, applied to privacy-preserving federated learning, are superior than the state-of-the-art differential privacy mechanisms in utility.

The popularity of intelligent devices provides straightforward access to the Internet and online social networks. However, the quick and easy data updates from networks also benefit the risk spreading, such as rumor, malware, or computer viruses. To this end, this article studies the problem of source detection, which is to infer the source node out of an aftermath of a cascade, that is, the observed infected graph G N of the network at some time. Prior arts have adopted various statistical quantities such as degree, distance, or infection size to reflect the structural centrality of the source. In this article, we propose a new metric that we call the infected tree entropy (ITE), to utilize richer underlying structural features for source detection. Our idea of ITE is inspired by the conception of structural entropy [ 21 ], which demonstrated that the minimization of average bits to encode the network structures with different partitions is the principle for detecting the natural or true structures in real-world networks. Accordingly, our proposed ITE based estimator for the source tries to minimize the coding of network partitions brought by the infected tree rooted at all the potential sources, thus minimizing the structural deviation between the cascades from the potential sources and the actual infection process included in G N . On polynomially growing geometric trees, with increasing tree heterogeneity, the ITE estimator remarkably yields more reliable detection under only moderate infection sizes, and returns an asymptotically complete detection. In contrast, for regular expanding trees, we still observe guaranteed detection probability of ITE estimator even with an infinite infection size, thanks to the degree regularity property. We also algorithmically realize the ITE based detection that enjoys linear time complexity via a message-passing scheme, and further extend it to general graphs. Extensive experiments on synthetic and real datasets confirm the superiority of ITE to the baselines. For example, ITE returns an accuracy of 85%, ranking the source among the top 10%, far exceeding 55% of the classic algorithm on scale-free networks.

Despite the bandwidth scaling limit of electrical switching and the high cost of building Clos data center networks (DCNs), the adoption of optical DCNs is still limited. There are two reasons. First, existing optical DCN designs usually face high deployment complexity. Second, these designs are not full-optical and the performance benefit over the non-blocking Clos DCN is not clear. After exploring the design tradeoffs of the existing optical DCN designs, we propose TROD (ThresholdRouting basedOpticalDatacenter), a low-complexity optical DCN with superior performance than other optical DCNs. There are two novel designs in TROD that contribute to its success. First, TROD performs robust topology optimization based on the recurring traffic patterns and thus does not need to react to every traffic change, which lowers deployment and management complexity. Second, TROD introduces tVLB (threshold-based Valiant Load Balance), which can avoid network congestion as much as possible even under unexpected traffic bursts. We conduct simulation based on both Facebook’s real DCN traces and our synthesized highly bursty DCN traces. TROD reduces flow completion time (FCT) by about 1.15-2.16$\times$compared to Google’s Jupiter DCN, at least 2$\times$compared to other optical DCN designs, and about 2.4-3.2$\times$compared to expander graph DCN. Compared with the non-blocking Clos, TROD reduces the hop count of the majority packets by one, and could even outperform the non-blocking Clos with proper bandwidth over-provision at the optical layer. Note that TROD can be built with commercially available hardware and does not require host modifications.

Secure Device-to-Device (D2D) communication is important for the Internet-of-Things (IoT) devices. Key agreement between devices is the important first step in building a secure D2D channel. Due to the lack of third-party certification, key agreement for IoT devices has to rely on the untrusted channel between them, which makes the pairing process vulnerable to attacks such as eavesdropping, jamming, and predictable channel attack. We solve this problem with a novel key agreement method named EchoKey, where two nearby devices can generate a symmetric key independently, leveraging the ambient sound signal that can be locally collected by devices. The intuition of this idea is that the propagation delays of the ambient sounds and the echoes will carry fine-grained information about the spatial context of the receiving device, which can be transformed to a special key for that device. So, nearby devices which have similar spatial context will generate similar echo profiles. We implement a prototype of EchoKey and evaluate its performance in resisting different attacks. The results tell that, with EchoKey, the key agreement process is even undetectable by an attacker which is only 50cm away from the pairing devices, and is thus resistant to all attacks mentioned above.

Training Transformer-based models demands a large amount of data, while obtaining aligned and labelled data in multimodality is rather cost-demanding, especially for audio-visual speech recognition (AVSR).Thus it makes a lot of sense to make use of unlabelled unimodal data.On the other side, although the effectiveness of large-scale self-supervised learning is well established in both audio and visual modalities, how to integrate those pretrained models into a multimodal scenario remains underexplored.In this work, we successfully leverage unimodal self-supervised learning to promote the multimodal AVSR.In particular, audio and visual front-ends are trained on large-scale unimodal datasets, then we integrate components of both front-ends into a larger multimodal framework which learns to recognize parallel audio-visual data into characters through a combination of CTC and seq2seq decoding.We show that both components inherited from unimodal selfsupervised learning cooperate well, resulting in that the multimodal framework yields competitive results through fine-tuning.Our model is experimentally validated on both word-level and sentence-level tasks.Especially, even without an external language model, our proposed model raises the state-of-the-art performances on the widely accepted Lip Reading Sentences 2 (LRS2) dataset by a large margin, with a relative improvement of 30%.

Relation extraction is a fundamental task to construct a knowledge graph, which aims to find the relation categories between two entities from a string of text input sequences. Considering the fact that high-quality labeled data is rare, a recent trend is low-resource setting. Existing works either utilize prompt-based learning method to achieve encouraging results for few-shot tasks by determining an appropriate prompt template, or leverage unlabeled data by generating pseudo labels. However, the manual design of the prompt template requires not only labor-intensive but also expert knowledge. Roughly utilizing a semi-supervised method to assign pseudo-label to unlabeled data will suffer from noise accumulation. To tackle these problems, we propose a novel semi-supervised prompt learning framework with relation-aware gradient denoising for low-resource relation extraction(PromptRGD). Firstly, using learnable template words and virtual labels for prompt learning, we introduce entity type and relation prior knowledge into prompt template construction. Secondly, given the relation-aware gradient similarity between labeled and unlabeled data, PromptRGD generates a pseudo label and then improves the quality of pseudo labels on unlabeled samples in a self-training fashion. The main experimental results and a series of analyses prove the effectiveness of PromptRGD.

Jiexing Qi, Jingyao Tang, Ziwei He, Xiangpeng Wan, Yu Cheng, Chenghu Zhou, Xinbing Wang, Quanshi Zhang, Zhouhan Lin. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.

With the proliferation of the mobile networks and location-based services, huge volume of user trajectories are collected to analyze the similarity among users and further unveil human mobility patterns for downstream tasks, such as point-of-interest recommendation and tourism planning. In recent works, trajectory embedding methods have been studied as efficient ways of trajectory similarity computation and effective inputs for downstream tasks, which embed trajectories into latent vector spaces equipped with the Euclidean distance to approximate the trajectory similarity and capture the characteristics of human mobility patterns. However, we demonstrate that such embedding, though hiding the locations, can leak the sensitive information of the trajectories, combined with auxiliary data. In this work, we propose trajectory embedding attack schemes to analyze the sensitive information leakage of the embedding vectors. In the experiment, we demonstrate that the passing areas, visited ROIs, and exact shapes of the trajectories are vulnerable under attacks on embedding vectors by the adversary with auxiliary information.

Trajectory representation learning studies the problem of embedding trajectories into low-dimensional vectors, while preserving mutual similarity for the convenience of downstream tasks, such as nearest neighbor search, clustering, classification, etc. In this work, we propose the Trajectory Similarity Network Embedding (TSNE) which exploits representation learning on the k-nearest neighbor partial similarity graph to generate trajectory embeddings, that preserve different similarity efficiently. In theory, we prove that TSNE is equivalent to factorizing the similarity graph, while in practice, TSNE achieves better performance. In the experiment, we show that TSNE outperforms the state-of-the-art baselines, including matrix factorization approaches and RNN based models in terms of similarity preserving and dimension reduction.

Nowadays, the rapid development of self-driving technology and its fusion with the current vehicle electrification process has given rise to electric self-driving taxis (es-taxis). Foreseeably, es-taxis will become a major force that serves the massive urban mobility demands not far into the future. Though promising, it is still a fundamental unsolved problem of effectively deciding when and where a city-scale fleet of es-taxis should be charged, so that enough es-taxis will be available whenever and wherever ride requests are submitted. Furthermore, charging decisions are far from isolated, but tightly coupled with the order dispatch process that matches orders with es-taxis. Therefore, in this paper, we investigate the problem of joint order dispatch and charging in es-taxi systems, with the objective of maximizing the ride-hailing platform’s long-term cumulative profit. Technically, such problem is challenging in a myriad of aspects, such as long-term profit maximization, partial statistical information on future orders, etc. We address the various arising challenges by meticulously integrating a series of methods, including distributionally robust optimization, primal-dual transformation, and second order conic programming to yield far-sighted decisions. Finally, we validate the effectiveness of our proposed methods though extensive experiments based on two large-scale real-world online ride-hailing order datasets.

This paper studies the problem of connectivity maintenance in adversarial uncertain networks, where a defender prevents the largest connected component from being decomposed by an attacker. In contrast with its deterministic counterpart, connectivity maintenance in an uncertain network involves additional testing on edges to determine their existence. To this end, by modeling a general uncertain network as a random graph with each edge associated with an existence probability and a testing cost, our goal is to design a general adaptive defensive strategy to maximize the expected size of the largest remaining connected component with minimum expected testing cost and, moreover, the strategy should be independent of the attacking patterns. The computational complexity of the connectivity maintenance problem is unraveled by proving its NP-hardness. To accurately tackle the problem, based on dynamic programming we first propose an optimal defensive strategy for a specific class of uncertain networks with uniform testing costs. Thereafter multi-objective optimization is adopted to generalize the optimal strategy for general uncertain networks through weighted sum of normalized size and cost. Due to the prohibitive price of an optimal strategy, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity. We first derive a heuristic approach by quantifying the edge vulnerability through an analogy from the degree centrality in deterministic networks to the probability degree and connectivity weight in uncertain networks. For performance guarantee, we then devise an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario caused by the attacker and has an approximation ratio of (1 − 1/e). Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

Along with the proliferation of Internet of Things (IoT) devices, people have a lot of concerns on the privacy issues brought by those devices. Existing solutions, employing strong encryption al-gorithms or trying to hide the communication in PHY layer, often suffer from the limited capability of IoT devices. In order to address the issue, we propose Rustle, an acoustic communication design which builds covert connection among IoT devices using random noise signal. Noise signal can be easily generated and exchanged by the widely used speakers and microphones on IoT devices. Based on the weak transitivity of signal's correlation and a fine-grained control of signal's wave shape, Rustle generates a series of mutu-ally uncorrelated random signals that contain “hidden patterns” to embed information. Extensive evaluations demonstrate that Rustle can achieve a lower than 1% BER while the eavesdropper's error rate on detecting the signal is higher than 80%.

Secure Device-to-Device (D2D) communication is important for the Internet-of-Things (IoT) devices. Key agreement between devices is the important first step in building a secure D2D channel. Due to the lack of third-party certification, key agreement for IoT devices has to rely on the untrusted channel between them, which makes the process vulnerable to attacks such as eavesdropping, jamming, and predictable channel attack. We solve this problem with a novel key agreement method named EchoKey, where two nearby devices can generate symmetric key independently, leveraging the ambient sound signal that can be locally collected by devices. The intuition of this idea is that the propagation delays of the ambient sounds and its echoes will carry fine-grained information about the spatial context of the receiving device, which can be transformed to a special key for that device. So, nearby devices which have similar spatial context will generate similar keys. We implement a prototype of EchoKey and evaluate its performance in resisting different attacks. The results tell that, with EchoKey, the key agreement process is even undetectable by an attacker which is only 50cm away from the pairing devices, and is thus resistant to all attacks mentioned above.

Spatio-temporal graph learning is a key method for urban computing tasks, such as traffic flow, taxi demand and air quality forecasting. Due to the high cost of data collection, some developing cities have few available data, which makes it infeasible to train a well-performed model. To address this challenge, cross-city knowledge transfer has shown its promise, where the model learned from data-sufficient cities is leveraged to benefit the learning process of data-scarce cities. However, the spatio-temporal graphs among different cities show irregular structures and varied features, which limits the feasibility of existing Few-Shot Learning (FSL) methods. Therefore, we propose a model-agnostic few-shot learning framework for spatio-temporal graph called ST-GFSL. Specifically, to enhance feature extraction by transferring cross-city knowledge, ST-GFSL proposes to generate non-shared parameters based on node-level meta knowledge. The nodes in target city transfer the knowledge via parameter matching, retrieving from similar spatio-temporal characteristics. Furthermore, we propose to reconstruct the graph structure during meta-learning. The graph reconstruction loss is defined to guide structure-aware learning, avoiding structure deviation among different datasets. We conduct comprehensive experiments on four traffic speed prediction benchmarks and the results demonstrate the effectiveness of ST-GFSL compared with state-of-the-art methods.

With the tremendous expansion of graphs data, node classification shows its great importance in many real-world applications. Existing graph neural network based methods mainly focus on classifying unlabeled nodes within fixed classes with abundant labeling. However, in many practical scenarios, graph evolves with emergence of new nodes and edges. Novel classes appear incrementally along with few labeling due to its newly emergence or lack of exploration. In this paper, we focus on this challenging but practical graph few-shot class-incremental learning (GFSCIL) problem and propose a novel method called Geometer. Instead of replacing and retraining the fully connected neural network classifier, Geometer predicts the label of a node by finding the nearest class prototype. Prototype is a vector representing a class in the metric space. With the pop-up of novel classes, Geometer learns and adjusts the attention-based prototypes by observing the geometric proximity, uniformity and separability. Teacher-student knowledge distillation and biased sampling are further introduced to mitigate catastrophic forgetting and unbalanced labeling problem respectively. Experimental results on four public datasets demonstrate that Geometer achieves a substantial improvement of 9.46% to 27.60% over state-of-the-art methods.

The ride-hailing service offered by mobility-on-demand platforms, such as Uber and Didi Chuxing, has greatly facilitated people's traveling and commuting, and become increasingly popular in recent years. Efficiency (e.g., gross merchandise volume) has always been an important metric for such platforms. However, only focusing on the efficiency inevitably ignores the fairness of driver incomes, which could impair the sustainability of the overall ride-hailing system in the long run. To optimize the aforementioned two essential metrics, order dispatching and driver repositioning play an important role, as they impact not only the immediate, but also the future order-serving outcomes of drivers. Thus, in this paper, we aim to exploit joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness for ride-hailing platforms. To address this problem, we propose a novel multi-agent reinforcement learning framework, referred to as JDRL, to help drivers make distributed order selection and repositioning decisions. Specifically, to cope with the variable action space, JDRL segments the action space into a fixed number of action groups, and fixes the policy output dimension for order selection as the number of action groups. In terms of the fairness criterion, JDRL adopts the max-min fairness, and augments the vanilla policy gradient to an iterative training algorithm that alternates between a minimization step and a policy improvement step to maximize both the worst and the overall performance of agents. In addition, we provide the theoretical convergence guarantee of our JDRL training algorithm even under non-convex policy networks and stochastic gradient updating. Extensive experiments are conducted with three public real-world ride-hailing order datasets, including over 2 million orders in Haikou, China, over 5 million orders in Chengdu, China, and over 6 million orders in New York City, USA. Experimental results show that JDRL demonstrates a consistent advantage compared to state-of-the-art baselines in terms of both efficiency and fairness. To the best of our knowledge, this is the first work that exploits joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness in a ride-hailing system.

Magnetic sensing is emerging as an enabling technology for various engaging applications. Representative use cases include high-accuracy posture tracking, human-machine interaction, and haptic sensing. This technology uses multiple MEMS magnetometers to capture the changing magnetic field at a close distance. However, magnetometers are susceptible to real-world disturbances, such as hard- and soft-iron effects. As a result, users need to perform a cumbersome and lengthy calibration process frequently, severely limiting the usability of magnetic tracking.

In this paper, we for the first time show how to enable software-defined PHY (SD-PHY) to achieve agile reprogrammability in wireless backscatter networks. This can facilitate innovations in this field by relieving researchers from unnecessary engineering work. With SD-PHY, the tag's PHY-layer behavior can be neatly defined by configuring a set of parameters, which allows the common hardware to generate backscattered signals complying with various wireless protocols. The SD-PHY architecture is based on the key insight that the tag's PHY-layer behavior is essentially determined by reflection coefficient sequence.

We in this paper present TiSee, an RFID-based sensing system that supports miniature robots to perform agile tasks in everyday environments. TiSee's unique capability is that it uses a single arbitrarily-deployed antenna to locate a target with sub-cm-level accuracy and identify its orientation to within few degrees. Compared with existing solutions which rely on either antenna arrays or multiple RFID readers, TiSee is cheap, compact, and applicable to miniature robots.

OFDMA downlink design allowing parallel processing OFDM subcarriers is adopted by a number of commercial wireless standards such as LTE, 5G, and 802.11ax. However, the widespread adoption of OFDMA downlink on low-end IoT devices is stymied due to the existing digital receiver framework's ≈100mW power consumption, which is mainly incurred by LO+mixer, ADC, and complex digital processing. In this paper, we present an ultra-low-power OFDMA downlink demodulation design, which achieves ≈100 μW receiving power. Our basic idea is to transform the current digital demodulation approach into the analog one based on filtering, which avoids those power-hungry components. We achieve this by proposing a series of novel RF front-end hardware designs: 1) a μW-level two-stage mixing scheme that enables adjustable and precise subcarrier filtering, 2) a quartz crystal-based filter circuit incurring negligible insertion loss, and 3) a passive phase-to-envelope conversion technique enabling low-power non-coherent phase demodulation. We build a prototype to verify the proposed schemes. Experimental and IC simulation results show that: our new design can achieve 130 -- 1500 times power savings depending on the number of subcarriers that need to be processed in parallel, compared with the traditional all-digital design.

Emerging crowdsensing paradigm enables a large number of sensing applications, where much attention is drawn to the fundamental problems of data collection and truth inference. Existing works have devised manifold techniques to discover truth from collected noisy data, but they frequently ignore various expertise of workers and dynamic information of crowdsensing system, thus leading to error-prone estimated truth and unqualified sensing data. In this paper, we design an online location-aware crowdsensing system to accurately estimate truth and efficiently assign tasks. Specifically, we unify diverse types of numerical and categorical tasks based on probabilistic graphical model, and then propose unsupervised learning methods which can dynamically infer ground truth and various worker expertise at the same time. Furthermore, we develop online task allocation schemes to gradually gather high quality data considering location awareness and inferred worker expertise. In particular, we convert the complicated task allocation into the additive form of probability improvement and entropy reduction, thereby solving the allocation problem via linearly selecting worker-task pair with low computation complexity. We finally carry out extensive evaluations using two datasets collected by our smartphones, where results demonstrate the superiority of our algorithms over the state-of-the-art approaches.

Urban traffic flow forecasting is a critical issue in intelligent transportation systems. Due to the complexity and uncertainty of urban road conditions, how to capture the dynamic spatiotemporal correlation and make accurate predictions is very challenging. In most of existing works, urban road network is often modeled as a fixed graph based on local proximity. However, such modeling is not sufficient to describe the dynamics of the road network and capture the global contextual information. In this paper, we consider constructing the road network as a dynamic weighted graph through attention mechanism. Furthermore, we propose to seek both spatial neighbors and semantic neighbors to make more connections between road nodes. We propose a novel Spatiotemporal Adaptive Gated Graph Convolution Network ( STAG-GCN ) to predict traffic conditions for several time steps ahead. STAG-GCN mainly consists of two major components: (1) multivariate self-attention Temporal Convolution Network ( TCN ) is utilized to capture local and long-range temporal dependencies across recent, daily-periodic and weekly-periodic observations; (2) mix-hop AG-GCN extracts selective spatial and semantic dependencies within multi-layer stacking through adaptive graph gating mechanism and mix-hop propagation mechanism. The output of different components are weighted fused to generate the final prediction results. Extensive experiments on two real-world large scale urban traffic dataset have verified the effectiveness, and the multi-step forecasting performance of our proposed models outperforms the state-of-the-art baselines.

The von Neumann graph entropy is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by the networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between the Laplacian spectrum and the degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might be a good approximation of the von Neumann graph entropy that is both scalable and interpretable. In this work, we thereby study the difference between the structural information and the von Neumann graph entropy named asentropy gap. Based on the knowledge that the degree sequence is majorized by the Laplacian spectrum, we for the first time prove that the entropy gap is between 0 and$\log _{2} e$in any undirected unweighted graphs. Consequently we certify that the structural information is a good approximation of the von Neumann graph entropy that achieves provable accuracy, scalability, and interpretability simultaneously. This approximation is further applied to two entropy-related tasks: network design and graph similarity measure, where a novel graph similarity measure and the corresponding fast algorithms are proposed. Meanwhile, we show empirically and theoretically that maximizing the von Neumann graph entropy can effectively hide the community structure, and then propose an alternative metric calledspectral polarizationto guide the community obfuscation. Our experimental results on graphs of various scales and types show that the very small entropy gap readily applies to a wide range of simple/weighted graphs. As an approximation of the von Neumann graph entropy, the structural information is the only one that achieves both high efficiency and high accuracy among the prominent methods. It is at least two orders of magnitude faster than SLaQ (Tsitsulinet al., 2020) with comparable accuracy. Our structural information based methods also exhibit superior performance in downstream tasks such as entropy-driven network design, graph comparison, and community obfuscation.

Influence maximization (IM) aims at maximizing the spread of influence by offering discounts to influential users (called seeding). In many applications, due to user’s privacy concern, overwhelming network scale etc., it is hard to target any user in the network as one wishes. Instead, only a small subset of users is initially accessible. Such access limitation would significantly impair the influence spread, since IM often relies on seeding high degree users, which are particularly rare in such a small subset due to the power-law structure of social networks. In this paper, we attempt to solve the limited IM in real-world scenarios by the adaptive approach with seeding and diffusion uncertainty considered. Specifically, we consider fine-grained discounts and assume users accept the discount probabilistically. The diffusion process is depicted by the independent cascade model. To overcome the access limitation, we prove the set-wise friendship paradox (FP) phenomenon that neighbors have higher degree in expectation, and propose a two-stage seeding model with the FP embedded, where neighbors are seeded. On this basis, for comparison we formulate the non-adaptive case and adaptive case, both proven to be NP-hard. In the non-adaptive case, discounts are allocated to users all at once. We show the monotonicity of influence spread w.r.t. discount allocation and design a two-stage coordinate descent framework to decide the discount allocation. In the adaptive case, users are sequentially seeded based on observations of existing seeding and diffusion results. We prove the adaptive submodularity and submodularity of the influence spread function in two stages. Then, a series of adaptive greedy algorithms are proposed with constant approximation ratio. Extensive experiments on real-world datasets show that our adaptive algorithms achieve larger influence spread than non-adaptive and other adaptive algorithms (up to a maximum of 116 percent).

Recent years have witnessed the proliferation of electric vehicles (EVs) that enable environment-friendly commuting and traveling. However, the increasing number of EVs inevitably create massive charging demands that are challenging to satisfy. Oftentimes in practice, EVs have to wait in queues for a long time outside charging stations before chargers become available. To address this challenge, we fully capture the elasticity of EVs’ charging demands in response to the charging prices, and propose a dynamic charging pricing mechanism that jointly controls the lengths of the demand queues at multiple charging stations and maximizes the charging platform’s long-term profit for offering charging services. Clearly, such an approach is more feasible than the financially and temporally expensive way of constructing extra charging facilities. Technically, we augment the Lyapunov stochastic optimization technique to decompose the challenging long-term decision-making problem into a series of single-time-slot optimization programs which require zero knowledge of future system parameters. However, due to the correlation of charging demands among different stations, the aforementioned optimization program in each time slot is non-convex. We handle the non-convexity by jointly constructing independent sets of charging stations and adapting the block coordinate descent method to iteratively obtain approximately optimal charging prices. Through rigorous theoretical analysis and extensive simulations based on the real-world dataset in the Chinese city Shenzhen which consists of 4000 taxis and 171 charging stations, we demonstrate that our control policy ensures an arbitrarily close-to-optimal profit with a flexible trade-off between the profit and queue lengths, has a low computational complexity, and requires zero knowledge of future system dynamics.

Mobile edge computing enables resource-limited edge clouds (ECs) in federation to help each other with resource-hungry yet delay-sensitive service requests. Contrary to common practice, we acknowledge that mobile services are heterogeneous and the limited storage resources of ECs allow only a subset of services to be placed at the same time. This paper presents a jointly optimized design of cooperative placement and scheduling framework, named JCPS, that pursuessocial cost minimizationover time while ensuring diverse user demands. Our main contribution is a novel perspective on cost reduction by exploiting thespatial-temporal diversitiesinworkload and resource costamong federated ECs. To build a practical edge cloud federation system, we have to consider two major challenges:user deadline preferenceandECs’ strategic behaviors. We first formulate and solve the problem of spatially strategic optimization without deadline awareness, which is proved$\mathcal {NP}$-hard. By leveraging user deadline tolerance, we develop a Lyapunov-baseddeadline-drivenjoint cooperative mechanism under the scenario where the workload and resource information of ECs are known for one-shot global cost minimization. Theservice priorityimposed by deadline urgency drives time-critical placement and scheduling, which, combined with cooperative control, enables workloads migrated across different times and ECs. Given selfishness of individual ECs, we further design an auction-based cooperative mechanism to elicittruthful bidson workload and resource cost. Rigorous theoretical analysis and extensive simulations are performed, validating the efficiency of JCPS in realizing cost reduction and user satisfaction.

Many realistic mobile social networks can be characterized by evolving bipartite graphs, in which dynamically added elements are divided into two entities and connected by links between these two entities, such as users and items in recommendation networks, authors and scientific topics in scholarly networks, male and female in dating social networks, etc. However, given the fact that connections between two entities are often weighted, how to mathematically model such weighted evolving bipartite relationships, along with quantitative characterizations, remains unexplored. Motivated by this, we develop a novel evolving bipartite model (EBM), which, based on empirically validated power-law distribution on multiple realistic mobile social networks, discloses that the distribution of total weights of incoming and outgoing edges in networks is determined by the weighting scale and bounded by certain ceilings and floors. Based on these theoretical results, for evolving bipartite networks whose degree follows power-law distribution, their overall weights of vertices can be predicted by EBM. To illustrate, in recommendation networks, the evaluation of items, i.e., total rating scores, can be estimated through the given bounds; in scholarly networks, the total numbers of publications under specific topics can be anticipated within a certain range; in dating social networks, the favorability of male/female can be roughly measured. Finally, we perform extensive experiments on 10 realistic datasets and a synthetic network with varying weights, i.e., rating scales, to further evaluate the performance of EBM, and experimental results demonstrate that given weighting scales, both the upper bound and the lower bound of total weights of vertices in mobile social networks can be properly predicted by the EBM.

Nowadays, most of the taxi drivers have become users of the relocation recommendation service offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing), which could oftentimes lead drivers to places with profitable orders. At the same time, electric taxis (e-taxis) are increasingly adopted and gradually replacing gasoline taxis in today’s public transportation systems due to their environmental-friendly nature. Though effective for traditional gasoline taxis, existing relocation recommendation schemes are rather suboptimal for e-taxi drivers’ user experience. On one hand, the existing schemes take no account of taxis’ refueling decisions, as the refueling durations of gasoline taxis are usually short enough to be ignored. However, the charging duration of the e-taxis spent at charging stations can be as long as hours. Obviously, an e-taxi’s battery could be easily depleted by the continuous relocations suggested by existing schemes, and thus will have to be charged for a long time afterwards, making the e-taxi driver miss numerous order-serving opportunities. On the other hand, charging posts are typically sparsely and unevenly distributed across a city. With no consideration of charging opportunities, existing schemes could probably send an e-taxi to an area with no charging post around, even though its battery is running low. To optimize e-taxi drivers’ user experience, in this paper, we design a jointcharging and relocation recommendation system for e-taxi drivers (CARE). We take the perspective of e-taxi drivers and formulate their decision making as a multi-agent reinforcement learning problem where each e-taxi driver aims to maximize his own cumulative rewards. More specifically, we propose a novelmulti-agent mean field hierarchical reinforcement learning (MFHRL)framework. The hierarchical architecture of MFHRL helps the proposed CARE provide far-sighted charging and relocation recommendations for e-taxi drivers. Besides, we integrate each hierarchical level of MFHRL separately with the mean field approximation to incorporate e-taxis’ mutual influences in decision making. We set up a simulator with one of the largest real-world e-taxi datasets in Shenzhen, China, which contains the GPS trajectory data and transaction data of 3848 e-taxis from June 1st to June 30th, 2017, coupled with 165 charging stations including 317 fast charging posts and 1421 slow charging posts. We adopt this simulator to generate 6 dynamic urban environments, which reflect the different real-world scenarios faced by e-taxi drivers. In all of these environments, we conduct extensive experiments to validate that the proposed MFHRL framework greatly outperforms all baselines by significantly increasing the rewards obtained by e-taxi drivers. Besides, we also show that the charging policy learned by MFHRL can effectively reduce the range anxiety of e-taxi drivers, which significantly boosts e-taxi drivers’ quality of experience.

As Internet users interacting with their different friends in different social networks, the de-anonymization problem has been raising improving concern. Since the assailants may de-anonymize a social network by matching it with a correlated sanitized network and identifying anonymized user identities, multifarious arts study on the theoretical conditions or practical algorithms for correctly de-anonymizing a social network. Except for the structural information of these social networks, there has also been bounteous works taking advantage of some pre-identified seed nodes for reference in the anonymized network. In this paper, we systematically probe the theoretical conditions and algorithmic approaches for correctly matching two different-sized social networks by leveraging the multi-hop neighborhood relationships. A limited number of seeds are also taken into consideration as auxiliary information. To this end, we introduce the de-anonymization problem with the aid of the collectiveness and the collective adjacency disagreements, which are the collection of disagreements of different multi-hop adjacency matrices. We theoretically demonstrate that minimizing the collective adjacency disagreements can help match two social networks even in a very sparse circumstance, as it significantly enlarges the difference between the mismatched node pairs and the correctly matched pairs. Besides, the seeds is proved to bring positive influence in improving the de-anonymization accuracy. Algorithmically, we relax the domain of the matching function to continuum and adopt the conditional gradient descending method on the collective-form objective, to efficiently minimize the collective adjacency disagreements of two networks. We conduct tremendous experiments on different networks with or without seeds, the results of which return desirable de-anonymization accuracies and reveal the advantages of the collectiveness: the collectiveness manifests rich structural information, thereby most nodes can be correctly matched with their correspondences even in some sparse networks, where merely utilizing the 1-hop adjacency relationships might fail to work.

Anonymization techniques have tranquilized current social network users in terms of privacy leakage, however, it does not radically prevent adversaries from de-anonymizing users, as they may map the users to an un-anonymized network. Till now, researchers share a common thread in such de-anonymization attack: unveiling conditions leading to successful de-anonymization under the chosen network model. However, it has not yet been well understand how the structural property in different network models intrinsically determines de-anonymizability. We address the above issue in this paper by making the two contributions: (i) We discover that the automorphic degree and homomorphic degree of social networks determine their de-anonymizability universally. The automorphic degree characterizes the distinguishability of the users in a network, while the homomorphic degree models the similarities of users between two networks. We conclude that a smaller automorphic degree and a larger homomorphic degree conduce to a higher de-anonymizability. Such model-independent phenomenon refreshes us with a latitudinal study as it generalizes the essential commonness of de-anonymization in different network models. (ii) We derive explicit parametric bounds of the de-anonymizability for three classic network models, showing that such bounds correspond well to our conclusion about morphism property. We then algorithmically and experimentally show that such theoretical results literally make sense to adversaries. Such longitudinal study, including welding theory, algorithm and validation, promises applicability of our results on morphism property in real cases.

Recent studies have shown that graph neural networks (GNNs) are vulnerable to unnoticeable adversarial perturbations, which largely confines their deployment in many safety-critical domains. Robust graph structure learning has been proposed to improve the GNN performance in the face of adversarial attacks. In particular, the low-rank methods are utilized to purify the perturbed graphs. However, these methods are mostly computationally expensive with O(n3) time complexity and O(n2) space complexity. We propose LRGNN, a fast and robust graph structure learning framework, which exploits the low-rank property as prior knowledge to speed up optimization. To eliminate adversarial perturbation, LRGNN decouples the adjacency matrix into a low-rank component and a sparse one, and learns by minimizing the rank of the first part while suppressing the second part. Its sparse variant is formed to reduce the memory footprint further. Experimental results on various attack settings have shown LRGNN acquires comparable robustness with the state-of-the-art much more efficiently, boasting a significant advantage on large-scale graphs.

The research of geoscience plays a strong role in helping people gain a better understanding of the Earth. To effectively represent the knowledge (KG) from enormous geoscience research papers, knowledge graphs can be a powerful means. In the face of enormous geoscience research papers, knowledge graphs can be a powerful means to manage the relationships of data and integrate knowledge extracted from them. However, the existing geoscience KGs mainly focus on the external connection between concepts, whereas the potential abundant information contained in the internal multimodal data of the paper is largely overlooked for more fine-grained knowledge mining. To this end, we propose GAKG, a large-scale multimodal academic KG based on 1.12 million papers published in various geoscience-related journals. In addition to the bibliometrics elements, we also extracted the internal illustrations, tables, and text information of the articles, and dig out the knowledge entities of the papers and the era and spatial attributes of the articles, coupling multimodal academic data and features. Specifically, GAKG realizes knowledge entity extraction under our proposed Human-In-the-Loop framework, the novelty of which is to combine the techniques of machine reading and information retrieval with manual annotation of geoscientists in the loop. Considering the fact that literature of geoscience often contains more abundant illustrations and time scale information compared with that of other disciplines, we extract all the geographical information and era from the geoscience papers' text and illustrations, mapping papers to the atlas and chronology. Based on GAKG, we build several knowledge discovery benchmarks for finding geoscience communities and predicting potential links. GAKG and its services have been made publicly available and user-friendly.

In this paper, we introduce LiteratureQA, a large question answering (QA) corpus consisting of publicly available academic papers. Different from other QA corpus, LiteratureQA has its unique challenges such as how to leverage the structured knowledge of citation networks. We further examine some popular QA method and present a benchmark approach of answering academic questions by combining both semantic text and graph knowledge to improve the prevalent pre-training model. We hope this resource could help research and development of tasks for machine reading over academic text.

Nowadays, the urban vehicle sharing (UVS) service offered by online platforms such as Car2Go and Zipcar has become an attractive choice for short-term mobility demands of city residents. Such way of shared mobility also demonstrates its potential in addressing various urban traffic problems (e.g., congestion, exhaust gas emission). However, the power of UVS systems could not be fully unleashed, unless the demand-supply gaps, incurred by the uneven spatial-temporal distributions of vehicle sharing orders and available vehicles, are effectively bridged. In this paper, we propose to resolve such problem by performing joint order dispatch and repositioning, which eventually maximizes the UVS platform's long-term cumulative profit. Specifically, we have addressed the various arising challenges, including capturing the interactive effect between order dispatch and repositioning, incorporating properly vehicles' fuel levels in our model, and dealing with stochastic demand with partially known statistical information. Technically, the problem is formulated as a stochastic dynamic program, and by integrating a series of methods, involving distributionally robust optimization, primal-dual transformation, as well as second order conic programming, we finally yield long-term optimal decisions. Furthermore, we validate our proposed methods using a large-scale real-world UVS dataset with over 300 vehicles and 300 thousand orders spanning overall 18 months.

Despite the bandwidth scaling limit of electrical switching and the high cost of building Clos data center networks (DCNs), the adoption of optical DCNs is still limited. There are two reasons. First, existing optical DCN designs usually face tremendous deployment complexity. Second, these designs are not full-optical and the performance benefit against the non-blocking Clos DCN is not clear.After exploring the design tradeoffs of the existing optical DCN designs, we propose TROD (Threshold Routing based Optical Datacenter), a low-complexity optical DCN with superior performance than other optical DCNs. There are two novel designs in TROD that contribute to its success. First, TROD performs robust topology optimization based on the recurring traffic patterns and thus does not need to react to every traffic change, which lowers deployment and management complexity. Second, TROD introduces tVLB (threshold-based VLB), which can avoid network congestion as much as possible even under unexpected traffic bursts. We conduct simulation based on both Facebook’s real DCN traces and our synthesized highly bursty DCN traces. TROD reduces flow completion time (FCT) by at least 2× compared with the existing optical DCN designs, and by approximately 2.4-3.2× compared with expander graph DCN. Compared with the non-blocking Clos, TROD reduces the hop count of the majority packets by one, and could even outperform the non-blocking Clos with proper bandwidth over-provision at the optical layer. Note that TROD can be built with commercially available hardware and does not require host modifications.

Recently, vehicular crowd sensing (VCS) that leverages sensor-equipped urban vehicles to collect city-scale sensory data has emerged as a promising paradigm for urban sensing. Nowadays, a wide spectrum of VCS tasks are carried out by for-hire vehicles (FHVs) due to various hardware and software constraints that are difficult for private vehicles to satisfy. However, such FHV-enabled VCS systems face a fundamental yet unsolved problem of striking a balance between the order-serving and sensing outcomes. To address this problem, we propose a novel graph convolutional cooperative multi-agent reinforcement learning (GCC-MARL) framework, which helps FHVs make distributed routing decisions that cooperatively optimize the system-wide global objective. Specifically, GCC-MARL meticulously assigns credits to agents in the training process to effectively stimulate cooperation, represents agents' actions by a carefully chosen statistics to cope with the variable agent scales, and integrates graph convolution to capture useful spatial features from complex large-scale urban road networks. We conduct extensive experiments with a real-world dataset collected in Shenzhen, China, containing around 1 million trajectories and 50 thousand orders of 553 taxis per-day from June 1st to 30th, 2017. Our experiment results show that GCC-MARL outperforms state-of-the-art baseline methods in order-serving revenue, as well as sensing coverage and quality.

Vehicular urban sensing (VUS), which uses sensors mounted on crowdsourced vehicles or on-board drivers' smartphones, has become a promising paradigm for monitoring critical urban metrics. Due to various hardware and software constraints difficult for private vehicles to satisfy, for-hire vehicles (FHVs) are usually the major forces for VUS systems. However, FHVs alone are far from enough for fine-grained spatio-temporal sensing coverage, because of their severe distribution biases. To address this issue, we propose to use a hybrid approach, where a centralized platform not only leverages FHVs to conduct sensing tasks during their daily movements of serving passenger orders, but also controls multiple dedicated sensing vehicles (DSVs) to bridge FHVs' coverage gaps. Specifically, we aim to achieve fine-grained spatio-temporal sensing coverage at the minimum long-term operational cost by systematically optimizing the repositioning policy for DSVs. Technically, we formulate the problem as a stochastic dynamic program, and solve various challenges, including long-term cost minimization, stochastic demand with partial statistical knowledge, and computational intractability, by integrating distributionally robust optimization, primal-dual transformation, and second order conic programming methods. We validate the effectiveness of our methods using a real-world dataset from Shenzhen, China, containing 726,000 trajectories of 3848 taxis spanning overall 1 month in 2017.

While community detection has been one of the cornerstones in network analysis and data science, its opposite, community obfuscation, has received little attention in recent years. With the increasing awareness of data security and privacy protection, the need to understand the impact of such attacks on traditional community detection algorithms emerges. To this end, we investigate the community obfuscation problem which aims to hide a target set of communities from being detected by perturbing the network structure. We identify and analyze the Matthew effect incurred by the classical quality function based methods, which essentially results in the imbalanced allocation of perturbation resources. To mitigate such effect, we propose a probabilistic framework named as ProHiCo to hide communities. The key idea of ProHiCo is to first allocate the resource of perturbations randomly and fairly and then choose the appropriate edges to perturb via likelihood minimization. Our ProHiCo framework provides the additional freedom to choose the generative graph model with community structure. By incorporating the stochastic block model and its degree-corrected variant into the ProHiCo framework, we develop two scalable and effective algorithms called SBM and DCSBM. Via extensive experiments on 8 real-world networks and 5 community detection algorithms, we show that both SBM and DCSBM are about 30x faster than the prominent baselines in the literature when there are around 500 target communities, while their performance is comparable to the baselines.

Ranking has significant applications in real life. It aims to evaluate the importance (or popularity) of two categories of objects, i.e., individuals and communities. Numerous efforts have been dedicated to these two types of rankings respectively. Instead, in this paper, we for the first time explore the co-ranking of both individuals and communities. Our insight lies in that co-ranking may enhance the mutual evaluation on both sides. To this end, we first establish an Evolving Coupled Graph that contains a series of smoothly weighted snapshots, each of which characterizes and couples the intricate interactions of both individuals and communities till a certain evolution time into a single graph. Then we propose an algorithm, called MIERank to implement the co-ranking of individuals and communities in the proposed evolving graph. The core idea of MIERank lies in a novel unbiased random walk, which, when sampling the interplay among nodes over different generation times, incorporates the preference knowledge of ranking by utilizing nodes' future actions. MIERank returns the co-ranking of both individuals and communities by iteratively alternating between their corresponding stationary probabilities of the unbiased random walk in a mutually-reinforcing manner. We prove the efficiency of MIERank in terms of its convergence, optimality and extensiblity. Our experiments on a big scholarly dataset of 606862 papers and 1215 fields further validate the superiority of MIERank with fast convergence and an up to 26% ranking accuracy gain compared with the separate counterparts.

This paper studies social network de-anonymization problem, which aims to identify users of an anonymized network by matching its user set with that of another auxiliary sanitized network. Prior arts primarily assume that both networks share exactly the same set of users, as opposed to many real situations of partially shared users in between. Different from the full matching case that only needs to take care of increasing the number of correctly matched pairs, the case of partial overlapping imposes additional demand on avoiding the wrong matches of those who do not have accounts across networks.To this end, we establish a new cost function, which we call the structural F-score to incorporate both the structural commonness and difference across networks. Intrinsically, the structural F-score computes the ratio of link agreements and disagreements, thus serving as the harmonic mean of precision and recall for any given matching function. Theoretically, we show that for networks parameterized by node overlap t2and link overlap s2, as long as the mean degree of networks grows as Ω(t-2s-3log n), maximizing the structural F-score provably ensures the perfect matching, where the nodal precision and recall are both maximized to 1. Algorithmically, for small-scale networks, we propose a two-step heuristic of F-score based de-anonymization, which firstly finds the optimal full matching between networks and then removes those pairs hindering structural F-score maximization. Due to the universal adaptability of the structural F-score, we further extend the algorithm to large-scale networks via a progressive matching process. Empirical results also validate the effectiveness of our methods in terms of improving the nodal F-score.

This paper studies the problem of source detection, which is to infer the source node out of an aftermath of a cascade, i.e., the observed infected graph GN of the network at some time. Prior arts have adopted various statistical quantities such as degree, distance or infection size to reflect the structural centrality of the source. In this paper, we propose a new metric which we call the infected tree entropy (ITE), to utilize richer underlying structural features for source detection. Our idea of ITE is inspired by the conception of structural entropy [1], which demonstrated that the minimization of average bits to encode the network structures with different partitions is the principle for detecting the natural or true structures in real-world networks. Accordingly, our proposed ITE based estimator for the source tries to minimize the coding of network partitions brought by the infected tree rooted at all the potential sources, thus minimizing the structural deviation between the cascades from the potential sources and the actual infection process included in GN. On polynomially growing geometric trees, with increasing tree heterogeneity, the ITE estimator remarkably yields more reliable detection under only moderate infection sizes. In contrast, for regular expanding trees, we still observe guaranteed detection probability of ITE estimator even with an infinite infection size, thanks to the degree regularity property. We also algorithmically realize the ITE based detection that enjoys linear time complexity via a message-passing scheme, and further extend it to general graphs. Experiments on various network topologies confirm the superiority of ITE to the baselines. For example, ITE returns an accuracy of 75% ranking the source among top 5%, far exceeding 45% of the classic algorithms on scale-free networks.

We study how to design edge server placement and server scheduling policies under workload uncertainty for 5G networks. We introduce a new metric called resource pooling factor to handle unexpected workload bursts. Maximizing this metric offers a strong enhancement on top of robust optimization against workload uncertainty. Using both real traces and synthetic traces, we show that the proposed server placement and server scheduling policies not only demonstrate better robustness against workload uncertainty than existing approaches, but also significantly reduce the cost of service providers. Specifically, in order to achieve close-to-zero workload rejection rate, the proposed server placement policy reduces the number of required edge servers by about 25% compared with the state-of-the-art approach; the proposed server scheduling policy reduces the energy consumption of edge servers by about 13% without causing much impact on the service quality.

Accurate tracking of the hands and fingers allows users to employ natural gestures in various interactive applications. Hand tracking also supports health applications, such as monitoring face-touching, a common vector for infectious disease. However, for both types of applications, the utility of hand tracking is often limited by the impracticality of bulky tethered systems (e.g., instrumented gloves) or inherent limitations (e.g., Line of Sight or privacy concerns with vision-based systems). These limitations have severely restricted the adoption of hand tracking in real-world applications. We present MagX, a fully untethered on-body hand tracking system utilizing passive magnets and a novel magnetic sensing platform. Since passive magnets require no maintenance, they can be worn on the hands indefinitely, and only the sensor board needs recharging, akin to a smartwatch.

Accurate tracking of the hands and fingers allows users to employ natural gestures in various interactive applications, e.g., controller-free interaction in augmented reality. Hand tracking also supports health applications, such as monitoring face-touching, a common vector for infectious disease. However, for both types of applications, the utility of hand tracking is often limited by the impracticality of bulky tethered systems (e.g., instrumented gloves) or inherent limitations (e.g., Line of Sight or privacy concerns with vision-based systems). These limitations have severely restricted the adoption of hand tracking in real-world applications. We demonstrate MagX, a fully untethered on-body hand tracking system utilizing passive magnets and a novel magnetic sensing platform. Since passive magnets require no maintenance, they can be worn on the hands indefinitely, and only the sensor board needs recharging, akin to a smartwatch.

The von Neumann graph entropy (VNGE) is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between Lapalcian spectrum and degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might approximate VNGE well.

The cascading of sensitive information such as private contents and rumors is a severe issue in online social networks. One approach for limiting the cascading of sensitive information is constraining the diffusion among social network users. However, the diffusion constraining measures limit the diffusion of non-sensitive information diffusion as well, resulting in the bad user experiences. To tackle this issue, in this paper, we study the problem of how to minimize the sensitive information diffusion while preserve the diffusion of non-sensitive information, and formulate it as a constrained minimization problem where we characterize the intention of preserving non-sensitive information diffusion as the constraint. We study the problem of interest over the fully-known network with known diffusion abilities of all users and the semi-known network where diffusion abilities of partial users remain unknown in advance. By modeling the sensitive information diffusion size as the reward of a bandit, we utilize the bandit framework to jointly design the solutions with polynomial complexity in the both scenarios. Moreover, the unknown diffusion abilities over the semi-known network induce it difficult to quantify the information diffusion size in algorithm design. For this issue, we propose to learn the unknown diffusion abilities from the diffusion process in real time and then adaptively conduct the diffusion constraining measures based on the learned diffusion abilities, relying on the bandit framework. Extensive experiments on real and synthetic datasets demonstrate that our solutions can effectively constrain the sensitive information diffusion, and enjoy a 40 percent less diffusion loss of non-sensitive information comparing with four baseline algorithms.

Recent years have witnessed the rising popularity of urban vehicular crowd sensing (UVCS) systems that leverage drivers' mobile devices equipped with on-board sensors for various urban sensing tasks. Because of the importance of ensuring satisfactory spatio-temporal sensing coverage in such UVCS systems, most existing work has focus on designing efficient scheduling mechanisms to maximize the task completion rate under drivers' traveling constraints. Different from prior work, we propose Hector, a joint trajectory scheduling and incentive mechanism for spatio-temporal UVCS systems, which concentrates on capturing the interactive effects between scheduling and incentive mechanisms. Technically, we first reduce the dimensions of the original scheduling problem by mapping it into an augmented set cover problem with spatio-temporal constraints. Then, based on reverse combinatorial auctions, we design Hector, whose incentive mechanism with the presence of uncertain future trajectory information makes scheduling and compensation decisions in real-time. Specifically, Hector is truthful, individual rational and computationally efficient. Furthermore, the social cost yielded by Hector is close-to-optimal, and the approximation ratio is Hm. The advantageous properties of Hector are verified by both rigorous theoretical analysis and extensive simulations based on the real world datasets in the Chinese city Shenzhen which consists of 726,000 taxi trajectories.

In networks where massive sources make observations of same entities, we intend to seek thetruth– the most trustworthy value of each entity from conflicting information claimed by multiple sources. Various methods are proposed for accurately inferring both source reliability and truths, yet relying heavily on centralized settings that incur tremendous overhead to source side. In this paper, we offer adecentralizeddesign of truth discovery task that can fit favorably to the environments with limited resources. Considering that sources forming the connected network and making individual observations, we undertake the joint maximum likelihood estimation (MLE) of truth and source reliability. Our decentralization framework simply allows each source to maintain local information exchange at a time, and computes very basic functions of data observations. To this end, we facilitate the decentralization by simplifying the MLE problem into optimizing an objective function. Upon the proof of NP-hardness, two proposed decentralized algorithms (exact and approximation) are decentralized and randomized via a combination of algorithms from their centralized counterparts that ensure performance guarantee. The derived time complexity features explicit data/network dependent terms, which leads to further acceleration in truth finding. Remarkably, in two well connected networks like random geometric and preferential attachment graphs, the accelerated approximation method enjoys logarithmic time complexity while preserving comparable accuracy to the centralized counterparts. The effectiveness of the proposed decentralizations are further empirically confirmed.

Channel state information (CSI) based Wi-Fi localization can achieve admirable decimeter-level accuracy; however, such systems require labor-intensive site survey to calibrate the AP position and the antenna array direction, which hinders practical large-scale deployment. In this article, we reveal an interesting finding that the calibration efforts for deploying the CSI localization system can be significantly reduced by simply replacing the ordinary linear antenna layout of the AP with the non-linear layout. In particular, we first present an autonomous self-calibrating method to significantly facilitate site survey for deploying CSI localization systems. Then we propose a systematical evaluation mechanism to show the fundamental reason why linear antenna layout usually leads to serious errors and why non-linear antenna layout is better off. Finally, we build a testbed with COTS devices and conduct comprehensive experiments. Results show that triangular antenna layout can achieve 80% angle of arrival (AoA) measurement error within 9° for any direction in contrast to 16° based on linear antenna layout. Moreover, we can realize promising localization accuracy as previous works even without labor-intensive site survey, where 80% localization error is within$0.60m$.

Fingerprinting indoor localization systems exploit wireless signal propagation features to estimate the location of wireless devices, where the major challenge in practice is the all-consuming training process: it requires site survey to establish the mapping between the signal feature and the location where the feature is observed. In this paper, we present a Wi-Fi localization scheme based on channel state information (CSI) of wireless signals, which manages to relieve time-consuming site survey. In particular, we first propose how to automatically generate the theoretical fingerprints database based on the signal propagation model and geometric methods. Localization with the theoretical fingerprints database yields accuracy close to existing methods. Second, we improve localization accuracy by parsing the user's trajectory instead of restricting to the single spot, where human movement features introduce more information for localization. Third, we present an automatic update scheme for the theoretical fingerprints database to improve time efficiency for localization, which can save 94 - 98% processing time for utilizing the CSI fingerprints database. We implement a prototype with COTS devices and conduct comprehensive experiments to verify proposed mechanisms. Results show that our design achieves 80% localization errors within 0.3m, which is 3× accuracy compared with the state-of-the-art design leveraging CSI.

Author name ambiguity causes inadequacy and inconvenience in academic information retrieval, which raises the necessity of author name disambiguation (AND). Existing AND methods can be divided into two categories: the models focusing on content information to distinguish whether two papers are written by the same author, the models focusing on relation information to represent information as edges on the network and to quantify the similarity among papers. However, the former requires adequate labeled samples and informative negative samples, and are also ineffective in measuring the high-order connections among papers, while the latter needs complicated feature engineering or supervision to construct the network. We propose a novel generative adversarial framework to grow the two categories of models together: (i) the discriminative module distinguishes whether two papers are from the same author, and (ii) the generative module selects possibly homogeneous papers directly from the heterogeneous information network, which eliminates the complicated feature engineering. In such a way, the discriminative module guides the generative module to select homogeneous papers, and the generative module generates high-quality negative samples to train the discriminative module to make it aware of high-order connections among papers. Furthermore, a self-training strategy for the discriminative module and a random walk based generating algorithm are designed to make the training stable and efficient. Extensive experiments on two real-world AND benchmarks demonstrate that our model provides significant performance improvement over the state-of-the-art methods.

Recent years have witnessed a drastic increase in the number of urban metro passengers, which inevitably causes the overcrowdedness in the metro systems of many cities. Clearly, an accurate prediction of passenger flows at metro stations is critical for a variety of metro system management operations, such as line scheduling and staff preallocation, that help alleviate such overcrowdedness. Thus, in this paper, we aim to address the problem of accurately predicting metro station passenger (MSP) flows. Similar to other traffic data, such as road traffic volume and highway speed, MSP flows are also spatial-temporal in nature. However, existing methods for other traffic prediction tasks are usually suboptimal to predict MSP flows due to MSP flows' unique spatial-temporal characteristics. As a result, we propose a novel deep learning framework STP-TrellisNets, which for the first time augments the newly-emerged temporal convolutional framework TrellisNet for spatial-temporal prediction. The temporal module of STP-TrellisNets (named CP-TrellisNets) employs two TrellisNets in serial to jointly capture the short- and long-term temporal correlation of MSP flows. In parallel to CP-TrellisNets, its spatial module (named GC-TrellisNet) adopts a novel transfer flow-based metric to characterize the spatial correlation among MSP flows, and implements multiple diffusion graph convolutional networks (DGCNs) in time-series order with their outputs connected to a TrellisNet to capture the dynamics of such spatial correlation. Clearly, GC-TrellisNet essentially integrates TrellisNet with graph convolution, and empowers TrellisNet with the ability to capture dynamic graph-structured correlation. We conduct extensive experiments with two large-scale real-world automated fare collection datasets, which contain respectively about 1.5 billion records in Shenzhen, China and 70 million records in Hangzhou, China. The experimental results demonstrate that STP-TrellisNets outperforms the state-of-the-art baselines.

Nowadays, ridesharing has become one of the most popular services offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing). Existing ridesharing platforms adopt the strategy that dispatches orders over the entire city at a uniform time interval. However, the uneven spatio-temporal order distributions in real-world ridesharing systems indicate that such an approach is suboptimal in practice. Thus, in this paper, we exploit adaptive dispatching intervals to boost the platform's profit under a guarantee of the maximum passenger waiting time. Specifically, we propose a hierarchical approach, which generates clusters of geographical areas suitable to share the same dispatching intervals, and then makes online decisions of selecting the appropriate time instances for order dispatch within each spatial cluster. Technically, we prove the impossibility of designing constant-competitive-ratio algorithms for the online adaptive interval problem, and propose online algorithms under partial or even zero future order knowledge that significantly improve the platform's profit over existing approaches. We conduct extensive experiments with a large-scale ridesharing order dataset, which contains all of the over 3.5 million ridesharing orders in Beijing, China, received by Didi Chuxing from October 1st to October 31st, 2018. The experimental results demonstrate that our proposed algorithms outperform existing approaches.

Distributed computing is known for its high efficiency of processing large amounts of data in parallel, at the expense of communication load between different servers. Coding was introduced to minimize the communication load by exploiting the repetitive computing, thus drawing great attention within the academia. Most existing works assume that all servers are identical in computational capability, which is inconsistent with practical scenarios. In this paper, we investigate a distributed computing system that consists of two types of servers, i.e., fast servers and slow servers. Due to the heterogeneous computational capabilities within the system, the overall computation time will be delayed by the slow servers, which is called the straggling effect. To this end, we develop a novel framework of coding-based distributed computing to alleviate the straggling effect. Specifically, for a given number of fast servers and slow servers with their corresponding computational capabilities, we aim to minimize the overall computation time by assigning different amounts of workloads to different servers. Further, we derive the information-theoretic lower bound of the communication load of the system, which is shown to be within a constant multiplicative gap to the achievable communication load by our scheme.

Most of today's high-speed switches and routers adopt an input-queued crossbar switch architecture. Such a switch needs to compute a matching (crossbar schedule) between the input ports and output ports during each switching cycle (time slot). A key research challenge in designing large (in number of input/output ports N) input-queued crossbar switches is to develop crossbar scheduling algorithms that can compute “high quality” matchings - i.e., those that result in high switch throughput (ideally 100%) and low queueing delays for packets - at line rates. SERENA is one such algorithm: it outputs excellent matching decisions that result in 100% switch throughput and reasonably good queueing delays. However, since SERENA is a centralized algorithm with O(N) time complexity, it cannot support switches that both are large and have a very high line rate per port. In this work, we propose SERENADE (SERENA, the Distributed Edition), a parallel iterative algorithm that provably precisely emulates SERENA in only O(logN) iterations between input ports and output ports, and hence has a time complexity of only O(logN) per port.

While deep neural networks (DNNs) have led to a paradigm shift, its exorbitant computational requirement has always been a roadblock in its deployment to the edge, such as wearable devices and smartphones. Hence a hybrid edge-cloud computational framework is proposed to transfer part of the computation to the cloud, by naively partitioning the DNN operations under the constant network condition assumption. However, real-world network state varies greatly depending on the context, and DNN partitioning only has limited strategy space. In this paper, we explore the structural flexibility of DNN to fit the edge model to varying network contexts and different deployment platforms. Specifically, we designed a reinforcement learning-based decision engine to search for model transformation strategies in response to a combined objective of model accuracy and computation latency. The engine generates a context-aware model tree so that the DNN can decide the model branch to switch to at runtime. By the emulation and field experimental results, our approach enjoys a 30% − 50% latency reduction while retaining the model accuracy.

In the contemporary era of information explosion, we are often faced with the mixture of massive truth (true information) and rumor (false information) flooded over social networks. Under such circumstances, it is very essential to infer whether each claim (e.g., news, messages) is a truth or a rumor, and identify their sources, i.e., the users who initially spread those claims. While most prior arts have been dedicated to the two tasks respectively, this paper aims to offer the joint inference on truth/rumor and their sources. Our insight is that a joint inference can enhance the mutual performance on both sides.To this end, we propose a framework named SourceCR, which alternates between two modules, i.e., credibility-reliability training for truth/rumor inference and division-querying for source detection, in an iterative manner. To elaborate, the former module performs a simultaneous estimation of claim credibility and user reliability by virtue of an Expectation Maximization algorithm, which takes the source reliability outputted from the latter module as the initial input. Meanwhile, the latter module divides the network into two different subnetworks labeled via the claim credibility, and in each subnetwork launches source detection by applying querying of theoretical budget guarantee to the users selected via the estimated reliability from the former module. The proposed SourceCR is provably convergent, and algorithmic implementable with reasonable computational complexity. We empirically validate the effectiveness of the proposed framework in both synthetic and real datasets, where the joint inference leads to an up to 35% accuracy of credibility gain and 29% source detection rate gain compared with the separate counterparts.

The interaction among users in different social networks raises deep concern on user privacy, as it may facilitate the assailants to identify user identities by matching the anonymized networks with a correlated sanitized one. Prior arts regarding such de-anonymization problem can be primarily divided into a seeded case or a seedless one, depending on whether or not there are a subset of pre-identified nodes. The seedless case is much more complicated since the adjacency matrix representation of one-hop user relations delivers limited structural information. To address this issue, we, for the first time, integrate the multi-hop neighborhood relationships, which exhibit more structural commonness between the anonymized and the sanitized networks, into seedless de-anonymization process. Our aim is to sufficiently leverage these multi-hop neighbors of all nodes and minimize the total disagreements of these multi-hop adjacency matrices, which we call collective adjacency disagreements (CADs), between two networks of different sizes. Theoretically, we demonstrate that CAD enlarges the difference between wrongly matched node pairs and correctly matched pairs, whereby two networks can be correctly matched with high probability even when the network density is below logn. Algorithmically, we adopt the conditional gradient descending method on a collective-form objective, which can efficiently find the minimal CADs for networks with broad degree distributions. Experiments on both synthetic and realworld networks return desirable de-anonymization accuracies thanks to the rich structural information manifested by such collectiveness, since most nodes can be correctly matched with their correspondences, especially in sparse networks where merely utilizing adjacency relations might fail to work.

Video streaming commonly uses Dynamic Adaptive Streaming over HTTP (DASH) to deliver good Quality of Experience (QoE) to users. Videos used in DASH are predominantly encoded by single-layered video coding such as H.264/AVC. In comparison, multi-layered video coding such as H.264/SVC provides more flexibility for upgrading the quality of buffered video segments and has the potential to further improve QoE. However, there are two challenges for using SVC in DASH: (i) the complexity in designing ABR algorithms; and (ii) the negative impact of SVC's coding overhead. In this work, we propose a deep reinforcement learning method called Grad for designing ABR algorithms that take advantage of the quality upgrade mechanism of SVC. Additionally, we quantify the impact of coding overhead on the achievable QoE of SVC in DASH, and propose jump-enabled hybrid coding (HYBJ) to mitigate the impact. Through emulation, we demonstrate that Grad-HYBJ, an ABR algorithm for HYBJ learned by Grad, outperforms the best performing state-of-the-art ABR algorithm by 17% in QoE.

Recently proposed OFDMA backscatter could improve both concurrency and spectrum allocation flexibility for backscatter systems based on OFDM. However, we find that it is remarkably inefficient for the existing design to scale up in prototyping: it requires one-by-one offline computation to obtain tags' operating parameters, in order to ensure orthogonality among subcarriers in the system; moreover, the tag hardware has to be dedicatedly modified offline before being assigned multiple subcarriers. The inefficiency is caused by the current analog frequency synthesis design for the tag. This paper proposes DigiScatter, an OFDMA backscatter system realizing digital frequency synthesis, which provides an efficient prototyping approach for large-scale OFDMA backscatter networks. In DigiScatter, we for the first time integrate IDFT into the tag design; such a simple but effective improvement enables the system to support high concurrency and flexible spectrum resource allocation through pure software configurations in an online manner. We build a prototype and conduct comprehensive experiments to validate our design. DigiScatter physically realizes 100 and 300 concurrent OFDMA backscatter transmissions in 2.4GHz and 900MHz respectively, and provides frequency synthesis capability for supporting 1019 concurrent transmissions.

In camera sensor networks (CSNs), full view coverage, meaning that any direction of any point in the operational region is covered by at least one camera sensor, plays a significant role in object identification. While prior work is dedicated to static CSNs for the sake of critical condition to achieve full view coverage, such performance still remains unknown in mobile CSNs. In this paper, we take the initiative to address this issue, where a centralized parameter, i.e., equivalent sensing radius (ESR), is defined to unravel the critical requirement for asymptotic full view coverage in mobile heterogeneous CSNs in the sense that camera sensors of different sensing capabilities are moving around in target area. Specifically, we derive ESR under three different mobilities, i.e., 1-dimensional and 2-dimensional random walks and random rotating model, and then explore respectively the corresponding critical conditions to achieve almost surely coverage.1 The static network is introduced as a baseline in order to gain a clear understanding of how mobility affects coverage performance differently. Interestingly, we find that both 1-dimensional and 2-dimensional random walks exhibit a smaller ESR than static one whereas ESR is even larger in random rotating mobility than that in static CSNs. Moreover, the almost surely coverage is found to be around 1.225 times of the critical condition to achieve coverage with high probability,2 and therefore turns out to be a stronger result compared to the traditional coverage with high probability. We then turn to the impact of various mobility patterns on sensing energy consumption, a metric that is closely related to ESR, and show that it can be decreased by random walks under certain delay tolerance. The relationship between ESR and percentage of full view coverage is also discussed and the results unify those under homogeneous CSNs.

Cooperative offloading in mobile edge computing enables resource-constrained edge clouds to help each other with computation-intensive tasks. However, the power of such offloading could not be fully unleashed, unless trust risks in collaboration are properly managed. As tasks are outsourced and processed at the network edge, completion latency usually presents high variability that can harm the offered service levels. By jointly considering these two challenges, we propose OLCD, an Online Learning-aided Cooperative offloaDing mechanism under the scenario where computation offloading is organized based on accumulated social trust. Under co-provisioning of computation, transmission, and trust services, trust propagation is performed along the multi-hop offloading path such that tasks are allowed to be fulfilled by powerful edge clouds. We harness Lyapunov optimization to exploit the spatial-temporal optimality of long-term system cost minimization problem. By gap-preserving transformation, we decouple the series of bidirectional offloading problems so that it suffices to solve a separate decision problem for each edge cloud. The optimal offloading control can not materialize without complete latency knowledge. To adapt to latency variability, we resort to the delayed online learning technique to facilitate completion latency prediction under long-duration processing, which is fed as input to queued-based offloading control policy. Such predictive control is specially designed to minimize the loss due to prediction errors over time. We theoretically prove that OLCD guarantees close-to-optimal system performance even with inaccurate prediction, but its robustness is achieved at the expense of decreased stability. Trace-driven simulations demonstrate the efficiency of OLCD as well as its superiorities over prior related work.

With the rapid spread of mobile devices, many traditional online social network services, like academic applications, start to develop mobile apps and improve their service quality through mobile sensing. A rich friendship among users can provide support for such applications, e.g., help to delegate sensing tasks in mobile crowd sensing. Therefore, studying friend recommendation that offers users' suggestions on who to connect to, so as to enrich the user's friendship, is necessary to Mobile Social Networks (MSNs). Most existing strategies utilize user's relationship, or similarity, to make the recommendation, which overlooks the existence of multi-type connections among users, e.g., common paper based and common topic based connections among authors in academic networks. To overcome such limitation, we characterize each type of connections by a corresponding network layer and then propose a novel algorithm for joint recommendations in multilayer MSNs. Particularly, two types of results are presented in the paper. (i) Our proposed algorithm, named as Cross-layer 2-hop Path (C2P) algorithm, implements the joint recommendation by suggesting a user establish connections to his cross-layer two-hop neighbors, i.e., those who link to the user by two-hop paths with the two hops belonging to two different layers, respectively. In doing so, each produced recommendation item is a combination of user relationships in both two layers and therefore can better meet user demands. (ii) By analytical derivations, along with further empirical validation on real datasets, we give the performance evaluation on our proposed algorithm. First, we prove that the algorithm is efficiently implementable with a constant complexity of each recommendation in most cases. Then, we evaluate its recommendation performance by two metrics, i.e., accuracy and diversity, where the former metric measures recommendation accuracy and the latter one measures an algorithm's capability to provide diverse recommendation items. Our results show that C2P algorithm is optimal in terms of accuracy and for diversity, its performance is no less than the algorithm that is applied in single layers. And finally, the effectiveness of the proposed algorithm is validated on both synthetic and large-scale real datasets, where it outperforms the baseline algorithms with an up to 32 percent accuracy gain and obtains an approximately 0.5 ratio of the algorithm's diversity to the theoretical upperbound.

Cellular network positioning is a mandatory requirement for localizing emergency callers, such as E911 in North America. Although smartphones are normally equipped with GPS modules, there are still a large number of users with cell phones only as basic devices, and GPS could be ineffective in urban canyon environments. To this end, the RF fingerprints based positioning mechanism is incorporated into LTE architecture by 3GPP, where the major challenge is to collect geo-tagged RF fingerprints in vast areas. This paper proposes to utilize the subspace identification approach for large-scale RF fingerprints prediction. We formulate the problem into the problem of finding the optimal subspace over Stiefel manifold, and redesign the Stiefel-manifold optimization method with fast convergence rate. Moreover, we propose a sliding window mechanism for the practical large-scale fingerprints prediction scenario, where recorded fingerprints are unevenly distributed in the vast area. Combining the two proposed mechanisms enables an efficient method of large-scale fingerprints prediction in the city level. Further, we validate our theoretical analysis and proposed mechanisms by conducting experiments with real mobile data, which shows that the resulted localization accuracy and reliability with our predicted fingerprints exceed the requirement of E911.

Crowdsensing paradigm facilitates a wide range of data collection, where great efforts have been made to address its fundamental issues of matching workers to their assigned tasks and processing the collected data. In this paper, we reexamine these issues by considering the spatio-temporal worker mobility and task arrivals, which more fit the actual situation. Specifically, we study the location-aware and location diversity based dynamic crowdsensing system, where workers move over time and tasks arrive stochastically. We first exploit offline crowdsensing by proposing a combinatorial algorithm, for efficiently distributing tasks to workers. After that, we mainly study the online crowdsensing, and further consider an indispensable aspect of worker's fair allocation. Apart from the stochastic characteristics and discontinuous coverage, the non-linear expectation is incurred as a new challenge concerning fairness issue. Based on Lyapunov optimization with perturbation parameters, we propose online control policy to overcome those challenges. Hereby, we can maintain system stability and achieve a time average sensing utility arbitrarily close to the optimum. Finally, we propose an optimization framework to aggregate the sensing data which can estimate worker expertise and task truth simultaneously. Performance evaluations on real and synthetic data set validate the proposed algorithm, where 80 percent gain of fairness is achieved at the expense of 12 percent loss of sensing value on average.

Influence Maximization (IM) aims to maximize the number of people that become aware of a product by finding the “best” set of “seed” users to initiate the product advertisement. Unlike most prior arts on the static networks containing fixed number of users, we study the evolving IM in more realistic evolving networks with temporally growing topology. The task of evolving IM, however, is far more challenging over static cases in the sense that the seed selection should consider its impact on future users who will join network during influence diffusion and the probabilities that users influence one another also evolve over time. We address the challenges brought by network evolution through EIM, a newly proposed bandit-based framework that alternates between seed nodes selection and knowledge (i.e., nodes’ growing speed and evolving activation probabilities) learning during network evolution. Remarkably, the EIM framework involves three novel components to handle the uncertainties brought by evolution: (1) A fully adaptive particle learning of nodes’ growing speed for accurately estimating future influenced size, with real growing behaviors delineated by a set of weighted particles. (2) A bandit-based refining method with growing arms to cope with the evolving activation probabilities via growing edges from previous influence diffusion feedbacks. (3) Evo-IMM , an evolving seed selection algorithm, which leverages the Influence Maximization via Martingale (IMM) framework, with the objective to maximize the influence spread to highly attractive users during evolution. Theoretically, the EIM framework returns a regret bound that provably maintains its sublinearity with respect to the growing network size. Empirically, the effectiveness of the EIM framework is also validated with three notable million-scale evolving network datasets possessing complete social relationships and nodes’ joining time. The results confirm the superiority of the EIM framework in terms of an up to 50% larger influenced size over four static baselines.

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, their cost functions, whose minimizers may remain algorithmically unknown, usually bring imponderable mapping errors when the true mapping cannot minimize these cost functions. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: 1) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; 2) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), effectively finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities: 90% users are re-identified averagely in a series of networks when communities overlap densely, and the re-identification ratio is enhanced about 70% compared to non-overlapping cases.

With the popularization of smart devices and social platforms (Facebook, Instagram and etc.), content transmission is becoming an increasingly prevalent form of human interaction with transmission time being a critical issue in miscellaneous applications. Extensive works have been devoted to this problem with the typical assumption that the network is non-evolving. In contrast, real-world networks which the transmission runs through are widely observed to be evolving over time and thus display distinctive properties. In this paper, we make the first study of content transmission in evolving networks. Particularly, we focus on the specific transmission time of the content, which is an important performance metric. For a comprehensive analysis, we consider both static and mobile cases. The network evolves in the following sense: each new user randomly chooses a geographic location while establishing social relations with existing users according to the evolving model, called Affiliation Networks. The transmission scheme running on the network exploits both social relationships and geographic information. While revealing the microscopic property of evolving social networks as the basis, in both static and mobile cases we manage to bound the transmission time in evolving networks which departs from results in non-evolving networks. In both cases, we find that the transmission time in evolving networks is smaller than the non-evolving counterpart under our scheme, and the gap is constantly increasing over time. Especially, the mobile case obtains such gain with less geographic knowledge. The theoretical findings are confirmed by experiments on both synthetic and real networks under different settings. We find that transmission time in evolving networks is smaller than non-evolving counterparts under the tested settings, and our proposed algorithms outperform the baselines.

We present Academic Reader, a system which can read academic literatures and answer the relevant questions for researchers. Academic Reader leverages machine reading comprehension technique, which has been successfully applied in many fields but has not been involved in academic literature reading. An interactive platform is established to demonstrate the functions of Academic Reader. Pieces of academic literature and relevant questions are input to our system, which then outputs answers. The system can also gather users’ revised answers and perform active learning to continuously improve its performance. A case study is provided presenting the performance of our system on all papers accepted in KDD 2018, which demonstrates how our system facilitates massive academic literature reading.

This paper presents BatchQR, a mobile APP that can batch read the densely arranged QR codes attached to caps of the tubes and vials in clinical and biological labs. The basic idea of BatchQR is to detect each code in the image and then decode in an one-by-one manner. However, the unique characteristics of the QR code and the application scenario bring technical challenges: First, off-the-shelf lightweight object detection mechanisms are unable to distinguish those densely arranged codes that are highly similar to each other; second, the focus area of the camera is limited, which blurs or distorts parts of the image. To this end, we propose a lightweight code detection mechanism, which can adaptively adjust operating parameters to identify densely arranged QR codes in practice. We also propose a simple but effective image refocus mechanism, which takes an auto-focused image and multiple refocused ones, and then replaces the blurred or distorted code parts with the high-quality counterparts in the refocused images. Comprehensive experimental results show that BatchQR can read 160-180 Version 1-L QR codes in batch with 90%-95% accuracy in 10-14s, which is only 4% of the time consumed by the regular QR code reader in the same situation.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems, where a myriad of data requesters outsource their sensing tasks to a crowd of workers via a cloud-based platform. In order to incentivize participation, requesters typically compensate workers with specific amount of payments. Clearly, setting an appropriate task price is critical for a requester to attract enough worker participation without unnecessary expenses. Therefore, we investigate the problem of task pricing in MCS systems with multi-requester price competition, and also dynamically arriving workers. Task pricing in such scenario is challenging, because of each requester's incomplete information about the others, uncertainty of future information, etc. So as to address these challenges, we use Markov game to model requesters' competitive task pricing, and Markov correlated equilibrium (MCE) as the solution concept. We propose that the platform uses the social cost-minimizing MCE to coordinate requesters' prices, which is self-enforcing, and optimizes the system-wide objective of social cost. Technically, we propose a computationally efficient algorithm to compute an approximately optimal MCE. Furthermore, through extensive performance evaluation, we show numerically that our algorithm yields close-to-minimum social cost in very short running time.

Many practical applications have observed knowledge evolution, i.e., continuous born of new knowledge, with its formation influenced by the structure of historical knowledge. This observation gives rise to evolving knowledge graphs whose structure temporally grows over time. However, both the modal characterization and the algorithmic implementation of evolving knowledge graphs remain unexplored. To this end, we propose EvolveKG, a framework that reveals cross-time knowledge interaction with desirable performance of storage and computation. The novelty of EvolveKG lies in Derivative Graph - a static weighted snapshot of evolution at a certain time. Particularly, each weight quantifies knowledge effectiveness with a temporarily decaying function of consistency and attenuation, two proposed factors depicting whether or not the effectiveness of a fact fades away with time. Thanks to the cross-time interaction, EvolveKG allows future knowledge prediction by virtue of the influence from the historical ones. Empirically tested under two real datasets, the superiority of EvolveKG is confirmed via its prediction accuracy.

Recent studies show that the voice control system (VCS) is subject to the inaudible voice command attack, which can not be heard by human ears but can be recorded by the microphone. An adversary could leverage the attack to disable the VCS user's home security system, leak the victim's privacy or download malware stealthily. Efforts have been dedicated to developing forensics based defense mechanisms, which target at detecting traces of the attack signal; however, we find that existing approaches of the kind still leave loopholes. Moreover, a complete defense mechanism should be able to not only detect the attack but also cancel out the attack signal, and meanwhile ensure the legitimate voice commands unaffected, which however is still unavailable to the best of our knowledge. This paper is an attempt to fill the gap. We first systematically analyze existing forensics based defense mechanisms and reveal the root cause of their loopholes. Then we present an active inaudible-voice-command cancellation (AIC) design, which can reliably detect and capture the attack signal facilitated by our custom-designed "guard'' signal transmitter. AIC can create a special spectrum in the passband of the VCS microphone, based on which we are able to neutralize the attack signal in software means. We implement a prototype of our defense system and conduct comprehensive experiments to validate our design.

In this paper, we for the first time demonstrate how to enable OFDMA in Wi-Fi backscatter for capacity and concurrency enhancement. With our approach, the excitation signal is reflected, modulated and shifted to lie in the frequency band of the OFDM subcarrier by the tag; OFDMA is realized by coordinating tags to convey information to the receiver with orthogonal subcarriers concurrently through backscatter. The crux of the design is to achieve strict synchronization among communication components, which is more challenging than in regular OFDMA systems due to the more prominent hardware diversity and uncertainty for backscattering. We reveal how the subtle asychnronization scenarios particularly for backscattering can incur system offsets, and present a series of novel designs for the excitation signal transmitter, tag, and receiver to address the issue. We build a prototype in 802.11g OFDM framework to validate our design. Experimental results show that our system can achieve 5.2-16Mbps aggregate throughput by allowing 48 tags to transmit concurrently, which is 1.45-5x capacity and 48x concurrency compared with the existing design respectively. We also design an OFDMA tag IC, and the simulation and numerical analysis results show that the tag's power consumption is in tens of μW.

We study the source detection problem using limited timestamps on a given network. Due to the NP-completeness of the maximum likelihood estimator (MLE), we propose an approximation solution called infection-path-based estimator (INF), the essence of which is to identify the most likely infection path that is consistent with observed timestamps. The source node associated with that infection path is viewed as the estimated source û. For the tree network, we transform the INF into integer linear programming and find a reduced search region using BFS, within which the estimated source is provably always on a path termed as candidate path. This notion enables us to analyze the accuracy of the INF in terms of error distance on arbitrary tree. Specifically, on the infinite g-regular tree with uniform sampled timestamps, we get a refined performance guarantee in the sense of a constant bounded d(u*, û). By virtue of time labeled BFS tree, the estimator still performs fairly well when extended to more general graphs. Simulations on both trees and general networks further demonstrate the superior performance of the INF.

The omnipresence of cascading process in complex phenomena makes the identification of a small set of influential units, which is widely believed to trigger the outbreak, always an crucial issue in network science. Formulated as Influence maximization (IM) in 2003, this NP-hard problem has received a multitude of heuristic solutions with diverse angles. However, these methods are often unable to provide reliable solutions, due to the lack of an exact metric for evaluating units' contributions on cascading.

Channel state information (CSI) based Wi-Fi localization can achieve admirable decimeter-level accuracy; however, such systems require labor-intensive site survey to calibrate the AP position and the antenna array orientation, which hinders practical large-scale deployment. In this paper, we reveal an interesting finding that the calibration efforts for deploying the CSI localization system can be significantly reduced by simply replacing the ordinary linear antenna layout of the AP with the non-linear layout. In particular, we first present an autonomous self-calibrating method to significantly facilitate site survey for deploying CSI localization systems. Then we propose a systematical evaluation mechanism to show the fundamental reason why linear antenna layout usually leads to serious errors and why non-linear antenna layout is better off. Finally, we build a testbed with COTS devices and conduct comprehensive experiments. Results show that triangular antenna layout can achieve 80% angle of arrival (AoA) measurement error within 9◦for any direction in contrast to 16◦based on linear antenna layout. Moreover, we can realize promising localization accuracy as previous works even without labor-intensive site survey, where 80% localization error is within 0.60m.

Community detection refers to the task of discovering groups of vertices sharing similar properties or functions so as to understand the network data. With the recent development of deep learning, graph representation learning techniques are also utilized for community detection. However, the communities can only be inferred by applying clustering algorithms based on learned vertex embeddings. These general cluster algorithms like K-means and Gaussian Mixture Model cannot output much overlapped communities, which have been proved to be very common in many real-world networks. In this paper, we propose CommunityGAN, a novel community detection framework that jointly solves overlapping community detection and graph representation learning. First, unlike the embedding of conventional graph representation learning algorithms where the vector entry values have no specific meanings, the embedding of CommunityGAN indicates the membership strength of vertices to communities. Second, a specifically designed Generative Adversarial Net (GAN) is adopted to optimize such embedding. Through the minimax competition between the motif-level generator and discriminator, both of them can alternatively and iteratively boost their performance and finally output a better community structure. Extensive experiments on synthetic data and real-world tasks demonstrate that CommunityGAN achieves substantial community detection performance gains over the state-of-the-art methods.

Crowdsourcing is an effective paradigm in human centric computing for addressing problems by utilizing human computation power, especially in booming social Internet of Things (IoT). By leveraging mutual friendship between computing entities (i.e., workers), collaborative tasks can thus be routed and finally fulfilled by multihop friends with high expertise. However, crowdsourcing in social IoT may reveal the privacy of task requesters which results in a large dilemma. In this paper, we focus on designing a multihop routing incentive mechanism which can also preserve task requester's privacy. Specifically, a utility maximization problem under privacy and budget feasibility constraints is formulated. Defining the conditions for privacy insurance, we give guidelines on how many subtasks should an entire task be divided into, and analyze the tradeoff between privacy and task accuracy. To enable efficient crowdsourcing task routing in social IoT, we first consider 1-hop myopic routing case and propose a near-optimal task assignment algorithm with 1/2 approximation ratio for an arbitrary prior knowledge. We further design multihop payment policy to establish an equilibrium where workers are motivated to forward subtasks to their friends with the best expertise. The extensive simulations validate that our mechanism achieves a high level of average information gain with modest privacy guarantee.

Network functions virtualization (NFV) architecture enables quick and cost-effective response of mobile network operators to various Internet-of-Things (IoT) applications, where the crux is to effectively and efficiently allocate resources to virtual network functions (VNFs). However, a systematical approach for resource allocation in virtualized mobile core network is still unavailable. In this paper, we propose a synthetic approach based on analysis of both network processing procedures and users' behaviors. Inspired by the static user behavior model adopted by equipment manufacturers' load test procedures, we construct a more practical user behavior model by analyzing over 20TB real data from an operator. With the model, we propose a matrix mapping-based dynamic resource allocation mechanism for the virtualized mobile core networks. To demonstrate the effectiveness of our approach, we conduct experiments using application and signaling records of millions of real users. Results show that the new approach significantly increases the resource utilization and system capacity of the mobile core networks.

Combined with many different attack forms, advanced persistent threats (APTs) are becoming a major threat to cyber security. Existing security protection works typically either focus on one-shot case, or separate detection from response decisions. Such practices lead to tractable analysis, but miss key inherent APTs persistence and risk heterogeneity. To this end, we propose a Lyapunov-based security-aware defense mechanism backed by threat intelligence, where robust defense strategy-making is based on acquired heterogeneity knowledge. By exploring temporal evolution of risk level, we introduce priority-aware virtual queues, which together with attack queues, enable security-aware response among hosts. Specifically, a long-term time average profit maximization problem is formulated. We first develop risk admission control policy to accommodate hosts' risk tolerance and response capacity. Under multiple attacker resources, defense control policy is implemented on two-stage decisions, involving proportional fair resource allocation and host-attack assignment. In particular, distributed auction-based assignment algorithm is designed to capture uncertainty in the number of resolved attacks, where high-risk host-attack pairs are prioritized over others. We theoretically prove our mechanism can guarantee bounded queue backlogs, profit optimality, no underflow condition, and robustness to detection errors. Simulations on real-world data set corroborate theoretical analysis and reveal the importance of security awareness.

Energy-efficient and secure wireless communications have recently earned tremendous interests due to economic, environmental, and military concerns. This paper investigates the tradeoff between the secrecy throughput and the energy efficiency in cognitive radio networks (CRNs), where primary and secondary users with different priorities of spectrum access can either interfere or cooperate with each other. To gain an understanding of the intricate effects that system parameters have on underlay network's performance, we exclusively focus on characterizing several key aspects that may have potential impacts on secure underlay CRNs, including the transmission power, the number of interfering users, and the designed interference resistance coefficient. Based on the obtained analytical results, we further propose a cooperative spectrum sharing paradigm to improve both the secrecy throughput and the energy efficiency of primary users. The main idea is that primary users allow secondary users to simultaneously access the licensed spectrum and in return, the secondary transmitter acts as both a relay for primary transmissions and a friendly jammer against eavesdropping, in case the primary transmission fails. Both theoretical and numerical results reveal that: (i) When the interference from secondary transmitters is small, there is an optimal transmission power that maximizes the secrecy throughput for primary users compared to CRNs without the security issue. (ii) When the interference from secondary transmitters is large, the secrecy throughput increases with the transmission power for primary users. (iii) The transmission power that maximizes the energy efficiency is smaller than that maximizes the secrecy throughput for primary users. (iv) The number of interfering users has a slight impact on the secrecy throughput and the energy efficiency of primary users due to the secondary power control. (v) The proposed cooperative paradigm is an efficient approach to boost both the secrecy throughput and the energy efficiency of primary users compared with the traditional non-cooperative spectrum sharing, and provides an alternative method to compensate for the interference caused by secondary users.

This paper characterizes the throughput and delay performance of Cognitive Radio Networks (CRNs), where both primary and secondary networks coexist in a unit torus. Specifically, the primary network consists of static primary nodes (PNs) of density n, which have a higher priority to access the spectrum. In contrast, the secondary network consists of mobile secondary nodes (SNs) of density m = nβwithβ≥ 1, which move according to a hybrid random walk mobility model and have opportunistic access to the spectrum without affecting primary packet transmissions. Motivated by the fact that cooperation between primary and secondary nodes leads to possible improvement on the performance of CRNs, as well as the fact that the heterogeneous moving regions of secondary nodes will bring about further improvement, we propose a novel hierarchical cooperative scheduling mechanism, where secondary nodes serve as relays for primary packet transmissions by exploiting their mobility heterogeneity and geographic information. Our findings include: (i) For the primary network, stronger mobility heterogeneity of secondary nodes leads to better delay performance of the primary network, and meanwhile the delay scaling can be significantly reduced to Θ (n√(β/(4 log n)) log3/2n) when a near-optimal per-node throughput of Θ(1/log n) is obtained. (ii) For the secondary network, we also adopt a similar hierarchical cooperative scheduling mechanism, and obtain a near-optimal per-node throughput of Θ (1/log m) with the delay scaling of Θ(m1-(1√logm)). (iii) The delay of secondary source-destination pairs is determined by the moving region of destinations and has no relation with sources. Our work provides deeper understandings of the cooperation, heterogeneous mobility, and geographic information on the performance of CRNs, and sheds light on designing more efficient CRNs.

Facial paralysis makes patients lose their facial movements, which can incur eye damage even blindness since patients are incapable of blinking. We design and implement a pair of smart glasses iBlink to assist facial paralysis patients to blink. The basic idea is to monitor the normal side of the face with a camera and stimulate the paralyzed side, so that the blink of the both eyes become symmetric. Our contributions are: First, we propose an eye-blink detection mechanism based on support vector machine (SVM), which can detect asymmetric blinks of patients under various illumination conditions with an accuracy above 99 percent. Our eye-image library for training the model is published online for further related studies, which contains more than 30,000 eye images. Second, we design and implement an automatic stimulation circuits to generate electrical impulse for stimulating the patient's facial nerve branches, which can configure operational parameters in a self-adaptive manner for different patients. Third, we implement the entire iBlink system, which integrates the two functions above and a communication function module for tele-medicine applications. We conduct experiments in a hospital to obtain the design basis and verify effectiveness of our device.

Recently proposed Wi-Fi indoor localization systems utilizing channel state information (CSI) derived from the received signal achieve admirable accuracy. This paper presents an information-theoretical analysis in the received waveform level to explore the fundamental limits of the approach. In particular, we perform frequency domain Cramer-Rao bound (CRB) analysis for location estimation with CSI. Our analysis resolves the high-rank Fisher information matrix challenge, and establishes intrinsic connection between parameters to be estimated for localization and the received waveform information observable with the CSI retrieving toolkit. We also analyze the influence of the asynchronization between the transmitter and the receiver to the performance bound of the CSI approach. Moreover, we shed light on the insight into the design of the CSI localization systems. In particular, we show that the CSI approach presents varying performance for localizing targets in different distances and directions with respect to the CSI retrieving anchor point (AP), and the geometric distribution of AP antennas could fundamentally influence the localization performance. Comprehensive experimental results are demonstrated to validate our theoretical analysis.

Self-calibrating wireless indoor localization systems construct the radio map even the indoor floor plan automatically, which avoids the labor-intensive site survey process; however, existing systems utilizing the feature of Wi-Fi signals can only provide coarse-grained indoor maps, which hinders improvement of localization accuracy. In this paper, we present FineLoc, a fine-grained self-calibrating localization system based on the freely-deployed Bluetooth low energy (BLE) nodes and crowd-sourced data, which can profile more detailed layout information of the indoor space. We first reveal that existing systems can only generate inaccurate floor plans owning to the coarse-grained Wi-Fi reference information. Then, we utilize the increasingly popular BLE beacon nodes as the source of reference information, with which a series of dead-reckoning optimization and new schemes particularly for finer-grained indoor map construction are presented. We implement a prototype FineLoc system, which is deployed in around 11,000 m2areas. Our experimental results with the prototype show that FineLoc can achieve 80 percent localization errors within 1.6 m, 1.4 m, and 1.1 m in the library, classroom building, and office building, respectively, with an average density of deployed BLE nodes less than 2.6/100 m2.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource sensory data collection to the public crowd. In order to identify truthful values from (crowd) workers' noisy or even conflicting sensory data, truth discovery algorithms, which jointly estimate workers' data quality and the underlying truths through quality-aware data aggregation, have drawn significant attention. However, the power of these algorithms could not be fully unleashed in MCS systems, unless workers' strategic reduction of their sensing effort is properly tackled. To address this issue, in this paper, we propose a payment mechanism, named Theseus, that deals with workers' such strategic behavior, and incentivizes high-effort sensing from workers. We ensure that, at the Bayesian Nash Equilibrium of the non-cooperative game induced by Theseus, all participating workers will spend their maximum possible effort on sensing, which improves their data quality. As a result, the aggregated results calculated subsequently by truth discovery algorithms based on workers' data will be highly accurate. Additionally, Theseus bears other desirable properties, including individual rationality and budget feasibility. We validate the desirable properties of Theseus through theoretical analysis, as well as extensive simulations.

In many real-world networks, entities of different types usually form an evolving network with hybrid interactions. However, how to theoretically model such networks, along with quantitive characterizations, remains unexplored. Motivated by this, we develop a novel evolving model, which, as validated by our empirical results, can well capture some basic properties such as power-law degree distribution, densification, shrinking diameter, and community structure embodied in most real datasets. Particularly, two types of results are presented in this paper. First, our proposed model, namely, evolving K-Graph, consists of K-node sets representing K different types of entities. The hybrid interactions among entities, based on whether they belong to the same type, are classified into inter-type and intra-type ones that are, respectively, characterized by two joint graphs evolving over time. Following our newly proposed mechanism called interactive-evolution, potential connections can be established among nodes with common features and further form a positive feedback. The superiorities of our model are three folded: good capture of realistic networks, mathematical tractability and efficient implementation. Second, by analytical derivations, along with empirical validation on real datasets, we disclose two aspects of network properties: basic ones as power-law degree distribution, densification, shrinking diameter and community structure, as well as a distinctive one, that is, positive correlation observed in real networks, implying that a hub in one inter-type relationship network also has many neighbors in another one. An additional interesting finding is that through further comparison of models with or without interactive-evolution, the former one leads to an even earlier occurrence of network connectivity.

Due to the random and dynamic energy-harvesting process, it is challenging to conduct optimal rate control in Energy-Harvesting Communication Systems (EHCSs). Existing works mainly focus on two cases: (1) the traffic load is infinite (as long as there is energy, there is data to transmit), in which the objective is to optimize the rate control policy subject to the dynamic energy arrivals, thus maximizing the average system throughput; and (2) the traffic load is finite, in which the objective is to optimize the rate control policy, thus minimizing the time by which all packets are delivered. In this work, we focus on the optimal rate control of EHCSs from another important and practical perspective, where the data and energy arrivals are both random. Given any deadline of T , our goal is to maximize the total throughput in [0, T ]. Specifically, two scenarios are considered: (1) energy is ready before the transmission; and (2) energy arrives randomly during the transmission. In both scenarios, we assume that the data arrive randomly during the transmission. For the first scenario, we develop a novel Stepwise Searching Algorithm (SSA) based on the cumulative curve methodology, which is shown to achieve the optimal solution and the complexity grows only linearly with the problem size. In addition, the SSA can provide a simple and appealing graphical visualization of approximating the optimal solution. For the second scenario, we provide a simplified case study that can be solved by the SSA with low computation overhead and demonstrate the difficulties in solving the general setting, which initiates a first step toward the full understanding of the scenario when energy arrives randomly during the transmission.

Motivated by the requirement of heterogeneity in the Internet of Things, we initiate the joint study of capacity and energy efficiency scaling laws in heterogeneous wireless sensor networks, and so on. The whole network is composed of n nodes scattered in a square region with side length L = n α , and there are m = n ν home points { c j } j=1 m , where a generic home point c j generates q j nodes independently according to a stationary and rotationally invariant kernel k ( c j , ⋅). Among the n nodes, we schedule n s independent multicast sessions each consisting of k − 1 destination nodes and one source node. According to the heterogeneity of nodes’ distribution, we classify the network into two regimes: a cluster-dense regime and a cluster-sparse regime. For the cluster-dense regime, we construct single layer highway system using percolation theory and then build the multicast spanning tree for each multicast session. This scheme yields the Ω( n ½+(α − ½)γ / n s √ k ) per-session multicast capacity. For the cluster-sparse regime, we partition the whole network plane into several layers and construct nested highway systems. The similar multicast spanning tree yields the Ω( n ½−(1− ν)γ/2 / n s √ k ) per-session multicast capacity, where γ is the power attenuation factor. Interestingly, we find that the bottleneck of multicast capacity attributes to the network region with largest node density, which provides a guideline for the deployment of sensor nodes in large-scale sensor networks. We further analyze the upper bound of multicast capacity and the per-session multicast energy efficiency. Using both synthetic networks and real-world networks (i.e., Greenorbs), we evaluate the asymptotic capacity and energy efficiency and find that the theoretical scaling laws are gracefully supported by the simulation results. To our best knowledge, this is the first work verifying the scaling laws using real-world large-scale sensor network data.

In this paper, we propose a novel community detection model, which explores the dynamic community evolutions in temporal social networks by modeling temporal affiliation strength between users and communities. Instead of transforming dynamic networks into static networks, our model utilizes normal distribution to estimate the change of affiliation strength more concisely and comprehensively. Extensive quantitative and qualitative evaluation on large social network datasets shows that our model achieves improvements in terms of prediction accuracy and reveals distinctive insight about evolutions of temporal social networks.

Most existing knowledge graphs (KGs) in academic domains suffer from problems of insufficient multi-relational information, name ambiguity and improper data format for large-scale machine processing. In this paper, we present AceKG, a new large-scale KG in academic domain. AceKG not only provides clean academic information, but also offers a large-scale benchmark dataset for researchers to conduct challenging data mining projects including link prediction, community detection and scholar classification. Specifically, AceKG describes 3.13 billion triples of academic facts based on a consistent ontology, including necessary properties of papers, authors, fields of study, venues and institutes, as well as the relations among them. To enrich the proposed knowledge graph, we also perform entity alignment with existing databases and rule-based inference. Based on AceKG, we conduct experiments of three typical academic data mining tasks and evaluate several state-of-the-art knowledge embedding and network representation learning approaches on the benchmark datasets built from AceKG. Finally, we discuss promising research directions that benefit from AceKG.

With the development of D2D (Device-to- Device) communications, the ever increasingly growing demand for content sharing caused by nearby devices can be satisfied. D2D communications based on social relationships are taken into consideration in extant literature, while how to select friends with whom users share contents efficaciously and voluntarily remains a problem. To this end, social tie, as a measurement of content similarity and mutual trust, is introduced in our work to facilitate contents sharing. In the paper, we first model friend selection problem as a finite horizon optimal stopping problem in the frame of optimal stopping theory and derive the optimal social cost threshold. We further prove the optimal social cost threshold is endowed with monotonically non- decreasing property. Moreover, we develop an iterative algorithm based on derived social cost threshold to select friends with whom users are inclined to share contents. Last but not the least, numerous simulation results validate the effectiveness of our proposed algorithm for content sharing over random D2D communications.

Erasure codes provide higher reliability than replication for a same level of redundancy to store data in distributed storage systems, yet with more bandwidth overhead. Recently, regenerating codes are introduced, which significantly reduce the repair bandwidth by analyzing the fundamental tradeoff between storage capacity and repair bandwidth via the information flow graph. In reality, distributed storage systems with hierarchical structures are more common in data centers where data are organized in racks, and the cross-rack communication is more costly than the in-rack communication. Hence, in this paper, we introduce a class of codes to repair a failed node by downloading data from nodes in the same rack only, which are termed as multi-rack regenerating codes (MRC). Different with existing works, the cross-rack repair bandwidth under our codes can be reduced to zero. Meanwhile, we obtain the optimal tradeoff between storage and bandwidth of MRC, and present an explicit construction of MRC with the common product-matrix framework.

Social recommendation has been widely applied to offer users suggestions on who to connect to, where most existing strategies overlook the existence of multi-type connections among users. To overcome such limitation, we characterize each type of connections by a corresponding network layer and then propose a novel algorithm for joint recommendations in cross-layer social networks. Particularly, two types of results are presented in the paper. (i) Our proposed algorithm, named as Cross-layer 2-hop Path (C2P) algorithm, implements the joint recommendation by suggesting a user establish connections to his cross-layer two-hop neighbors, i.e., those who link to the user by two-hop paths with the two hops belonging to two different layers, respectively. In doing so, each produced recommendation item is a combination of user relationships in both two layers and thus can better meet user demands. (ii) By analytical derivations, along with further empirical validation on real datasets, we give the performance evaluation on our proposed algorithm. Firstly, we prove that the algorithm is efficiently implementable with a constant complexity in each recommendation. Then, we evaluate its recommendation performance by two metrics, i.e., acceptance and diversity, where the former metric measures recommendation accuracy and the latter one measures an algorithm's capability to provide diverse recommendation items. Our results show that C2P algorithm is optimal in terms of acceptance and for diversity, its performance is in the same order of the theoretical upperbound. And finally, the effectiveness of the proposed algorithm is validated by our simulations on three real datasets, where it outperforms baseline algorithms with an up to 38% acceptance gain and obtains an around 0.5 diversity ratio to the theoretical upperbound.

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, there is generally a lacking of rationale behind the cost functions, whose minimizer also remains algorithmically unknown. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: (i) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; (ii) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities, in terms of averagely 90% re-identified users in the rare true cross-domain co-author networks when communities overlap densely, and roughly 70% enhanced reidentification ratio compared to non-overlapping cases.

Cellular network positioning is a mandatory requirement for localizing emergency callers, such as E911 in North America. Although smartphones are normally with GPS modules, there are still a large number of users with cell phones only as basic devices, and GPS could be ineffective in urban canyon environments. To this end, the fingerprinting positioning mechanism is incorporated into LTE architecture by 3GPP, where the major challenge is to collect geo-tagged wireless fingerprints in vast areas. This paper proposes to utilize the subspace identification approach for large-scale wireless fingerprints prediction. We formulate the problem into the problem of finding the optimal subspace over Stiefel manifold, and redesign the Stiefel-manifold optimization method with fast convergence rate. Moreover, we propose a sliding window mechanism for the practical large-scale fingerprints prediction scenario, where fingerprints are unevenly distributed in the vast area. Combining the two proposed mechanisms enables an efficient method of large-scale fingerprints prediction in the city level. Further, we validate our theoretical analysis and proposed mechanisms by conducting experiments with real mobile data, which shows that the resulted localization accuracy and reliability with our predicted fingerprints exceed the requirement of E911.

Fingerprinting indoor localization systems have been studied from different perspectives in the past decades; however, a vitally important piece in the puzzle is still missing: how does the system scale with the number of users? In this paper, we study the issue from a theoretical perspective, where the upper and lower bound of the system's localization reliability with respect to the number of users are derived. Our theoretical results can be verified by experiments thus can provide meaningful guidance for practical system design, which is in contrast to the traditional scaling-law work utilizing asymptotical analysis that is valid only under unverifiable extreme conditions. The theoretical and experimental results of our work reveal two interesting observations that shed light on the insight into the scalability of the fingerprinting localization system: First, the localization reliability drops dramatically before the number of users increases to a critical point and then decreases smoothly, where the critical point tends to appear when the number of users equals the number of access points (APs) deployed in the service region; second, even if the number of users approaches to infinity, the fingerprinting localization system still retains certain level of reliability.

Distributed storage systems provide reliability by distributing data over multiple storage nodes. Once a node fails, a new node is introduced to the system to maintain the availability of the stored data. The new node downloads information from other surviving nodes called helper nodes to recover the lost data in the failed node. The number of helper nodes is called repair degree. Compared to traditional approaches, e.g., replication and erasure codes, the regenerating codes proposed recently can significantly reduce the repair bandwidth in homogeneous distributed storage systems. Most existing works focus on uniform settings (e.g., in terms of repair degree and repair bandwidth). However, due to network structures or connectivity limitations, for each failed node, the number of required helper nodes may be different for distinct failed nodes. Furthermore, considering the limits of network traffic of bandwidth, the amount of information allowed to be downloaded from each helper node could also vary. Thus we are motivated to investigate heterogeneous distributed storage systems where the repair degree and the amount of information downloaded from each helper node can be different. In order to obtain the minimal bandwidth to recover a failed node, we construct an information flow graph for such heterogeneous systems. By analyzing the cut-set bound of the information flow graph, the optimal tradeoff between storage capacity and repair bandwidth is derived. We then propose asymmetric regenerating codes that can achieve the curve of the optimal tradeoff. A linear construction of asymmetric regenerating codes is presented. Compared with previous regenerating codes, asymmetric regenerating codes are shown to have a lower repair bandwidth under a certain constraint condition, whose reduction can be up to 36.2%.

Caching plays an important role in reducing the backbone traffic when serving high-volume multimedia content. Recently, a new class of coded caching schemes have received significant interest, because they can exploit coded multi-cast opportunities to further reduce backbone traffic. Without considering file popularity, prior works have characterized the fundamental performance limits of coded caching through a deterministic worst-case analysis. However, when heterogeneous file popularity is considered, there remain open questions regarding the fundamental limits of coded caching performance. In this paper, for an arbitrary popularity distribution, we first derive a new information-theoretic lower bound on the expected transmission rate of any coded caching schemes. We then show that a simple coded-caching scheme attains an expected transmission rate that is at most a constant factor away from the lower bound. Unlike other existing studies, the constant factor that we derived is independent of the popularity distribution.

Real-time road traffic information brings great convenience for drivers. Various road information acquisitions are enabled by recent mobile crowdsensing paradigm. However, the accuracy of information can not be guaranteed, and appropriate incentive mechanism is still unavailable. In this paper, we study the problem of extracting the actual road traffic information according to the reports from an amount of unknown contributors. To obtain the accurate road traffic result with high probability, we establish a reputation system to evaluate the reliability of each contributor, which takes both location and time deviation factors into account. We also design an incentive mechanism to elicit the truthful report of each qualified contributor. Furthermore, we improve the existing answer inference methods and derive the correct result in an efficient way. Extensive simulations are carried out to evaluate the proposed algorithms.

This paper investigates how to optimize the fingerprints reporting strategy to improve localization accuracy, and how the optimal strategy theory can be utilized to streamline the design of WLAN fingerprinting localization systems. In particular, we first reveal that the fingerprints reporting problem is essentially an NP-Hard size-constrained supermodular maximization problem, and then show the inapplicability of the state-of-the-art approximation algorithms to the problem. We then propose a new algorithm and show that if the number of fingerprints measurements is large enough, then the localization accuracy is at most 1 - ε times worse than the optimal value, with ε any given constant close to 0. Moreover, we demonstrate how the optimal strategy theory can be utilized to improve accuracy of location estimation by resolving the issue of similar fingerprints for both faraway and close-by locations, with an iterative algorithm developed to cross check fingerprints sampled in different locations, in order to derive the best possible result of localization. Further, we reveal the relationship between accuracy of location estimation and coverage of Wi-Fi signals in indoor spaces when planning deployment of APs. Experiment results are presented to validate our theoretical analysis.

Recent study presents a fundamental limit of the RSS fingerprinting based indoor localization. In this paper, we theoretically show that the temporal correlation of the RSS can further improve accuracy of the fingerprinting localization. In particular, we construct a theoretical framework to evaluate how the temporal correlation of the RSS can influence reliability of location estimation, which is based on a newly proposed radio propagation model considering the time-varying property of signals from Wi-Fi APs. The framework is then applied to analyze localization in the one-dimensional physical space, which reveals the fundamental reason why localization performance can be improved by leveraging temporal correlation of the RSS. We extend our analysis to high-dimensional scenarios and mathematically depict the boundaries in the RSS sample space, which distinguish one physical location from another. Moreover, we develop an algorithm to utilize temporal correlation of the RSS to improve the location estimation accuracy, where the process for choosing key design parameters are provided through experiments. Experiment results show that the localization reliability and accuracy can be improved by up to 13 and 30 percent with appropriate leveraging the RSS temporal correlation information.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than (1/4) lnk. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: 1) Generality- ConMap exhibits strong applicability to a wide range of energy models; 2) Flexibility- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; 3) Efficiency- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

Location-aware viral marketing is crucial in modern commercial applications for attracting customers to certain points of interests. Prior works are mainly based on formulating it into a location-aware influence maximization problem in Geo-social Networks (GSNs), where $K$ initial seed individuals are selected in hope of maximizing the number of final influenced users. In this paper, we present the first look into the group-level location promotion, which can potentially enhance its performance, with the phenomenon that users belonging to the same geo-community share similar moving preferences. We propose GLP, a new and novel framework of group-level location promotion by virtue of geo-communities, each of which is treated as a group in GSNs. Aiming to attract more users to designated locations, GLP firstly carries out user grouping through an iterative learning approach based on information extraction from massive check-ins records. The advantage of GLP is three-folded: i) by aggregating movements of group members, GLP significantly avoids the sparsity and sporadicity of individual check-ins, and thus obtains more reliable mobility models; ii) by generalizing a new group-level social graph, GLP can exponentially reduce the computational complexity of seed nodes selection that is algorithmically executed by a greedy algorithm; iii) in comparison with prior individual-level cases, GLP is theoretically demonstrated to drastically increase influence spread under the same given budget. Extensive experiments on real datasets demonstrate that the GLP outperforms four baselines, with notably up to 10 times larger influence spread and 100 times faster seed selection over two individual-level cases, meanwhile verifying the impact of group numbers in final influence spread.

Many realistic wireless social networks are evolving over time. While network evolution has its important influence on network performances, it is nevertheless overlooked in most existing studies on information diffusion. Motivated by this, in this paper, we investigate the delivery accuracy of interest-aware information diffusion in evolving social networks. In doing so, we adopt a model, named affiliation networks, to characterize network evolution from three aspects, i.e., the arrival of new users, the generation of new interests, and the creation of new links between them. Based on that, we consider a publishing based information diffusion mechanism that widely exists in wireless networking services such as Facebook, Twitter, and Sina Weibo, where a user receives data items from his friends and then republishes the ones he is interested in to all his friends. Under the above network model, we study how the performance metric such as delivery accuracy is affected by the network evolution. The publishing based information diffusion mechanism is a blind targeting one that may suffer a low delivery accuracy. However, our analytical results demonstrate a contrary finding that the delivery accuracy is improved over time, and even more surprisingly, we disclose that with a sufficiently long evolving time, the delivery accuracy can achieve a perfect state where those who receive the data are exactly the ones that are interested in it. In addition, our theoretical findings are verified by experimental measurements through a social network dataset from Facebook.

Cache-enabled wireless networks have gained increasing popularity in recent years for facilitating the delivery of content. Most existing works assumed that the network is static without the change of users and content, which is not the case in the real world. In this paper, we study the content delivery in cache-enabled wireless networks, where the network evolves in terms of users and content. We adopt the affiliation network model to reveal the network evolution process, where new users and content are added into the network randomly and connected with existing nodes via the preferential attachment. Users with strong social relations tend to request the same content objects, thus content popularity is sharply concentrated. Therefore, caching technique is more effective. To maximize the content delivery rate, we formulate the optimization problem of caching replication jointly with routing strategy. We show that network evolution can greatly improve the content delivery rate. In particular, when per-user cache capacity is in the order of Θ(1), per-user delivery rate can achieve constant, i.e., the network can scale. Finally, theoretical results are validated based on a real-world data set from Facebook.

Autonomous vehicle industry is developing by leaps and bounds. We envisage a situation where autonomous vehicles act as taxis to transport clients. During the transportation, vehicle sharing is enabled and encouraged. We propose fair allocation in payment for passengers of a shared vehicle. The allocation is endowed with the characteristics of envy freeness and maximin utilities. Furthermore, we devise working mechanisms for autonomous vehicles, including (i) planning routes with minimum detour; (ii) choosing clients to recommend vehicle sharing; (iii) carrying passengers continuously. Our work may serve as a good preparation for the marketization of autonomous taxis.

A crucial privacy-driven issue nowadays is re- identifying ano-nymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through cost functions that are proposed without sufficient rationale. Also, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to find the minimizer of the cost functions. We address those concerns in a more realistic social network modeling parameterized by community structures that can be leveraged as side information for de- anonymization. By Maximum A Posteriori (MAP) estimation, our first contribution is new and well justified cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized. While proving the general multiplicative inapproximability, we are able to propose two heuristics, which, respectively, enjoy an ε-additive approximation and a conditional optimality in carrying out successful user re- identification. Our theoretical findings are empirically validated,with a notable dataset extracted from rare true cross-domain networks that reproduce genuine social network de-anonymization.

Network tomography can help detect network link delay. End-to-end path measurement is a promising method in network tomography which could reduce measurement overhead. In end-to-end path measurement, however, deriving link states is computational complex due to the existence of massive links. Because only a few links are congested at the same time, we can locate sparsely congested links by using compressed sensing (CS). In this paper, based on expander graphs, we demonstrate that routing matrix constructed by full tree network can satisfy Restricted Isometry Property (RIP) and be used as measurement matrix. Finally, sparsely congested links are given with CS. Evaluation results show that routing matrix constructed in this paper can help achieve high link delay recovery accuracy, i.e., small recovery error by using 1i-minimization in CS. It also illustrate that the recovery error decreases with the number of congested links decrease.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it has comparable performance than some other seemingly more sophisticated algorithms. Second, by harnessing the sub-modularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than ¼ ln k. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: i) Generality-- ConMap exhibits strong applicability to a wide range of energy models; ii) Flexibility-- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; iii) Efficiency-- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

In many realistic networks, entities of different types usually form an evolving network with hybrid interactions. However, how to mathematically model such networks remains unexplored. Motivated by this, we develop a novel evolving model, which, as validated by our empirical results, can well capture some basic features such as power-law distribution, densification and shrinking diameter. Particularly, in our proposed model, named Evolving K-Graph, the hybrid interactions among entities are classified into inter-type and intra-type connections that are respectively characterized by two joint graphs evolving over time. By empirical validation, we disclose two new network properties: a positive correlation of any two layers of the network, and an earlier occurrence of network connectivity resulted by our model.

Core percolation is crucial in network controllability and robustness. Prior works are mainly based on single, non-interacting network where core nodes are obtained by a classic Greedy Leaf Removal (GLR) procedure that takes of leaf nodes along with their neighbors iteratively. We take a first look into core percolation in coupled networks with two fully-interdependent networks. To obtain core nodes in both networks, we propose a new algorithm, called Alternating GLR procedure, that recursively switches between networks in carrying out GLR for node removal. We prove that the proposed algorithm can guarantee the uniqueness in the sense that the final remaining nodes and edges in either of the coupled networks remain the same, and then present analytical solutions for the fraction of core nodes that will be ultimately left when the algorithm terminates. Our simulation demonstrates that the presence of core exhibits a jump at the critical point as a first order transition in coupled networks.

Facial paralysis is a disease caused by nerve damage, which can make patients lose facial movements. Facial paralysis patients usually have muscles on one side of the face noticeably droop, which seriously impacts the person's quality of life as shown in Fig. [skull]. Worse still, the eye on the affected side is unable to blink and will become dry and infected by debries, which can incur eye damage even blindness. To the best of scientists' knowledge, the paralysis is due to the pressure incurred by infection in the tunnel containing main trunk of facial nerves, where the tunnel is inside of the people's head termed as the Facial canal. In this demo, we present iBlink [1], a novel system to help paralysis patients to blink. Paralysis usually occurs in just one side of the face, and clinical trials show that electrical stimulation could trigger blink. Based on such observations, the basic idea of iBlink is to monitor the normal side of the face with a camera and stimulate the paralysed side, so that eye-movements of the both sides become symmetric.

Facial paralysis makes patients lose their facial movements, which can incur eye damage even blindness since patients are incapable of blinking. The paralysis usually occurs on just one side of the face, and clinical trials show that electrical stimulation could trigger blink. Based on such observations, we design and implement a pair of smart glasses iBlink to assist facial paralysis patients to blink. The basic idea is to monitor the normal side of the face with a camera and stimulate the paralysed side, so that the blink of the both eyes become symmetric. To the best of our knowledge, this is the first piece of wearable device for facial paralysis therapy. Our contributions are: First, we propose an eye-blink detection mechanism based on deep convolutional neural network (CNN), which can detect asymmetric blinks of patients under various illumination conditions with an accuracy above 99%. Our eye-image library for training CNN models is published online for further related studies, which contains more than $30,000$ eye images. Second, we design and implement an automatic stimulation circuits to generate electrical impulse for stimulating the patient's facial nerve branches, which can configure operational parameters in a self-adaptive manner for different patients. Third, we implement the entire iBlink system, which integrates the two functions above and a communication function module for tele-medicine applications. Moreover, we conduct clinical trials in a hospital, in order to obtain the design basis and verify effectiveness of our device.

Coded caching has demonstrated the superiority in mitigating traffic pressure through jointly considering content delivery and storage schemes. However, existing works mainly focus on the situation where users have uniform demands with multiple layer of caches. In this paper, we propose a multilevel hierarchical coded caching scheme when users have nonuniform demands in a multi-hop content delivery network scenario. Specifically, to maintain the symmetry constraint of coded caching we utilize K-means to separate the file set with arbitrary distribution of popularity into several file subsets. We also formulate the Jensen's inequality and derive the upper bound of the transmission rate in each layer. To evaluate the system efficiency, we leverage the open-source Netflix dataset as our file set and conduct an experiment on a content delivery network with two layers of caches. Experimental results demonstrates that our multilevel hierarchical coded caching scheme performs much better than the baseline LFU caching scheme.

In this paper, we propose a novel game-based incentive mechanism for multi-resource sharing, where users are motivated to share their idle resources in view of conditional voluntary. Through social networking service platforms, such a crowdsourcing service fully explores the significant influence and computing potential of mobile social networks. Specifically, a combination of task allocation process, profit transfer process, and reputation updating process are involved in this sharing incentive mechanism, satisfying truthfulness, individual rationality, and robustness. To maintain the social fairness-efficiency tradeoff, we further develop a resource sharing algorithm on the basis of dominant resource fairness, revealing that the sacrifice of fairness properties is necessary for the improvement of efficiency. Real-world traces from Facebook are numerically studied, validating social fairness and efficiency of our social crowdsourcing mechanism.

Crowdsourcing systems allocate tasks to a group of workers over the Internet, which have become an effective paradigm for human-powered problem solving, such as image classification, optical character recognition, and proofreading. In this paper, we focus on incentivizing crowd workers to label a set of multi-class labeling tasks under strict budget constraint. We properly profile the tasks’ difficulty levels and workers’ quality in crowdsourcing systems, where the collected labels are aggregated with sequential Bayesian approach. To stimulate workers to undertake crowd labeling tasks, the interaction between workers and the platform is modeled as a reverse auction. We reveal that the platform utility maximization could be intractable, for which an incentive mechanism that determines the winning bid and payments with polynomial-time computation complexity is developed. Moreover, we theoretically prove that our mechanism is truthful, individually rational, and budget feasible. Through extensive simulations, we demonstrate that our mechanism utilizes budget efficiently to achieve high platform utility with polynomial computation complexity.

The widespread of smart phones has brought new social-aware features to wireless networks. Users prefer to forward traffic to their social contacts in social-aware networks, which is highly different from the traditional uniform traffic pattern. To this end, we analyze a social-aware wireless network, which is modeled by the social contacts between nodes, and explore its impact on network throughput capacity. We present that it can refine social contacts, thus improving the network capacity. Moreover, directional antennas are applied to further enhance the capacity performance, which can reduce the interference brought by other simultaneous communications. We derive the throughput capacity for social-aware networks with single-beam and multi-beam directional antenna, respectively. For single-beam directional antenna, we prove that when wireless networks are dominated by traffics of short-distance social contact, the throughput capacity can be promoted from order of (θ(1/θ2n log n)1/2) to Θ(1/θ2log n). In addition, when the beamwidth θ is at order of Ω(1/(log n)1/2), the throughput capacity is a constant. Thus, the wireless network is scalable. For multi-beam antennas, we prove that when sidelobe gain Gsis at order of o(Gm), where Gmis main lobe gain, compared with the single-beam case, the network capacity can achieve the order of θ(1/θ2log n).

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(√(n log n)), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.

With the soaring development of large scale online social networks, online information sharing is becoming ubiquitous everyday. Various information is propagating through online social networks including both the positive and negative. In this paper, we focus on the negative information problems such as the online rumors. Rumor blocking is a serious problem in large-scale social networks. Malicious rumors could cause chaos in society and hence need to be blocked as soon as possible after being detected. In this paper, we propose a model of dynamic rumor influence minimization with user experience (DRIMUX). Our goal is to minimize the influence of the rumor (i.e., the number of users that have accepted and sent the rumor) by blocking a certain subset of nodes. A dynamic Ising propagation model considering both the global popularity and individual attraction of the rumor is presented based on a realistic scenario. In addition, different from existing problems of influence minimization, we take into account the constraint of user experience utility. Specifically, each node is assigned a tolerance time threshold. If the blocking time of each user exceeds that threshold, the utility of the network will decrease. Under this constraint, we then formulate the problem as a network inference problem with survival theory, and propose solutions based on maximum likelihood principle. Experiments are implemented based on large-scale real world networks and validate the effectiveness of our method.

Indoor localization for quadrotors has attracted much attention recently. While efforts have been made to perform location estimation of quadrotors leveraging dedicated indoor infrastructures, the low-cost and commonly used RSS fingerprinting based approach utilizing existing Wi-Fi APs has yet to be applied. The challenge is that the high-speed flight reduces the RSS measuring opportunities for fingerprints comparison; moreover, the 3D space fingerprints collection incurs more overhead than in the traditional 2D case. In this paper, we present HiQuadLoc, a RSS fingerprinting based indoor localization system for quadrotors. We propose a series of mechanisms including path estimation, path fitting, and location prediction to deal with the negative influence incurred by the high-speed flight; moreover, we develop a 4D RSS interpolation algorithm to reduce the site survey overhead, where 3D is for the indoor physical space and 1D is for the RSS sample space. Experimental results demonstrate that HiQuadLoc reduces the average location error by more than 50 percent compared with simply applying the RSS fingerprinting based approach for 2D localization, and the overhead of RSS training data collection is reduced by more than 80 percent.

Indoor localization has been an active research field for decades, where received signal strength (RSS) fingerprinting based methodology is widely adopted and induces many important localization techniques, such as the recently proposed one building fingerprints database with crowdsourcing. While efforts have been dedicated to improve accuracy and efficiency of localization, performance of the RSS fingerprinting based methodology itself is still unknown in a theoretical perspective. In this paper, we present a general probabilistic model to shed light on a fundamental issue: how good the RSS fingerprinting based indoor localization can achieve? Concretely, we present the probability that a user can be localized in a region with certain size. We reveal the interaction among accuracy, reliability, and the number of measurements in the localization process. Moreover, we present the optimal fingerprints reporting strategy that can achieve the best localization accuracy with given reliability and the number of measurements, which provides a design guideline for the RSS fingerprinting based indoor localization system. Further, we analyze the influence of imperfect database information on the reliability of localization, and find that the impact of imperfect information is still under control with reasonable number of samplings when building the database.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph, where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P = NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov decision process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, and it enjoys significantly better performance guarantee than some other seemingly more sophisticated algorithms. Second, by harnessing the submodularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms is justified through extensive simulations on three real network data sets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source S, and a destination D are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with n nodes, where there is an edge between two nodes with probability p, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30log2n operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.

Recently, performance analysis for large-scale content-centric mobile ad hoc networks (MANETs) has received intense attention. In content-centric MANETs, content delivery consists of two operations, i.e., content placement and content retrieval, which may involve different network costs. However, the existing performance studies in content-centric MANETs mainly focus on content retrieval, and hence may not reflect the impact of content placement. In this paper, we investigate the asymptotic throughput and delay performance by considering the two operations of possibly different network costs. In particular, we introduce a general weighted sum delay cost of content placement and content retrieval as the delay performance metric. We consider an arbitrary content popularity distribution and study two mobility models in different time scales, i.e., fast and slow mobility. For each mobility model, we characterize the impacts of the network parameters on the network performance. By optimizing the content placement and retrieval for contents of different popularities, we design a general near-optimal scheme, the parameters of which reflect the delay weights of the two phases. We show that the network performance improves as the number of cached replicas increases until the number reaches a threshold. Finally, we show that our results are general and can incorporate some existing results as special cases.

Since it was found that real mobility processes exhibit significant degree of correlation (correlated mobility) and nodes are often heterogeneously distributed in clustered networks (cluster scalability), there has been a great interest in studying their impact on network performance, such as throughput and delay. However, limited works have been done to investigate their impact jointly, which may due to the challenges in capturing both features under a unified network model. In this paper, we focus on their impact on asymptotic connectivity and propose correlated mobile k-hop clustered network model. Two connectivity metrics are considered. One is network connectivity with probability (w.p.). The other is connectivity almost surely (a.s.), which requires a stronger condition than connectivity with probability. With mobility correlation and cluster scalability vary, we show that there are three distinct states for network connectivity, i.e., cluster-sparse, cluster-dense state, and cluster-inferior dense state, respectively. We first prove the exact value of the critical transmission range for each state, respectively, and then further generalize the three states into a unified one, which we call it cluster mixed state. The critical transmission range for connectivity almost surely is √2 times the range for connectivity with probability. Our main contribution lies in how to group correlated nodes into independent ones in various settings, and reveals the interrelated relationship between correlated mobility and cluster scalability through state transitions.

To accommodate exponentially increasing traffic demands, operators are seeking to offload cellular traffic to small base stations (BSs) in heterogeneous cellular networks (HCNs), which is promising in alleviating traffic congestion. In HCNs, operators are eager to balance the traffic globally, where users may be pushed to less preferred small BSs, resulting in possible conflict with user local preference. Thus, it is a big challenge to achieve dynamic load balancing for operators and provide participation incentive for users simultaneously. Due to the dynamics of network state and user traffic demand, we are inspired to utilize Lyapunov optimization to develop a congestion-aware cellular offloading scheme. Specifically, an operator profit maximization problem involving network selection and rate control is formulated. To achieve long-term network stability, we propose a congestion-aware network selection algorithm, obtaining the BS alternative set that maintains traffic congestion constraint. By exploring the heterogeneity of user quality sensitivity, we devise the optimal quality-price contract, which maximizes operator profit. With effective pricing and resource allocation, users are motivated to make proper association strategy chosen from the BS alternative set. Simulation results demonstrate the effectiveness of our scheme in improving operator profit. User incentive and network stability are also validated.

Social characteristics have been observed to significantly affect the communications in wireless social networks, especially that within a group following the multicast manner. To model the multicast group in wireless social networks, we should incorporate two important social characteristics, i.e., social relationship and group size. In most existing works, the modeling of social relationship only considers geographic factor. However, such models fail to well characterize wireless social networks, since unlike that in traditional wireless networks, geographic distance is no longer the major factor that affects people's communications and some non-geographic factors, such as user popularity, become more and more important. Moreover, group size is always assumed to be known a priori in previous works, which cannot fully meet the realistic condition. Therefore, in this paper, we model the multicast group from a combination of geographic and non-geographic (GN) perspectives. Specifically, we propose the GN Model to characterize social relationship and the independently-selected model to characterize group size. In addition to the geographic distance considered in the modeling of social relationship, we also introduce user popularity which reflects the influence of each user on others. Then, we assume that the source transmits the data packet to all his friends following the multicast manner. Based on the proposed model, we calculate transmission distance and network traffic load, and then discuss how they are influenced by both geographic and GN factors. Moreover, our proposed models are verified through experimental measurements based on real datasets.

Crowd sensing systems enable a wide range of data collection, where the data are usually tagged with private locations. How to incentivize users to participate in such systems while preserving location-privacy is coming up as a critical issue. To this end, we consider location-privacy protection when motivating users to sense data instead of viewing them separately. Without loss of generality,$k$-anonymity is utilized to reduce the risk of location-privacy disclosure. Specifically, we propose a location aggregation method to cluster users into groups for$k$-anonymity preserving, and meanwhile mitigating the incurred information loss. After that, an incentive mechanism is carefully designed to select efficient users and calculate rational compensations based on clustered groups obtained in location aggregation, where the influences of both the information loss and$k$-anonymity in location-privacy preserving are captured into group values and sensing costs. Through theoretical analysis and extensive performances evaluated on real and synthetic data, we find out that the incentive payment increases sharply with more stringent privacy protection and the information loss can be further mitigated compared with conventional methods.

Rumor blocking is a serious problem in large-scale social networks. Malicious rumors could cause chaos in society and hence need to be blocked as soon as possible after being detected. In this paper, we propose a model of dynamic rumor influence minimization with user experience (DRIMUX). Our goal is to minimize the influence of the rumor (i.e., the number of users that have accepted and sent the rumor) by blocking a certain subset of nodes. A dynamic Ising propagation model considering both the global popularity and individual attraction of the rumor is presented based on realistic scenario. In addition, different from existing problems of influence minimization, we take into account the constraint of user experience utility. Specifically, each node is assigned a tolerance time threshold. If the blocking time of each user exceeds that threshold, the utility of the network will decrease. Under this constraint, we then formulate the problem as a network inference problem with survival theory, and propose solutions based on maximum likelihood principle. Experiments are implemented based on large-scale real world networks and validate the effectiveness of our method.

With the explosive development of social networks, users' behaviors are prone to be socially connected. Social Network Operator (SNO) can effectively collect communication data which reflects users' social behaviors and construct a social graph which precisely characterize relationship among users. Users who exert online influence on their friends can potentially affect their friends' demand for wireless service. Therefore, the knowledge of users' influence would help Wireless Network Operator (WNO) make optimal operating decisions to maximize profit. This paper focus on the optimal pricing strategy of WNO when users' social influence is taken into consideration. We model SNO and WNO's relationship as a cooperative game. By formulating the interaction between SNO-WNO's coalition and users as a two-stage Stackelberg game, the optimal pricing strategy is derived which brings about extra profits. Moreover, we propose a generalized bargaining scheme based on contribution factor to divide extra profits between operators. Simulation results reveal the fact that wireless network operator's possession of influence information does incur extra profits. In addition, feasibility of SNO and WNO's cooperation is validated.

When social behaviors are considered into ad hoc wireless networks, the users prefer to forward the traffic from their social contacts. In this way, the network capacity is highly related with the social characteristics. To this end, we apply a social contact based wireless network model and explore its throughput capacity. The wireless network capacity will get improved when the contacts are located nearby the source node. Directional antennas are applied to further enhance the capacity performance, which can reduce the interference brought by other simultaneous communications. Our results demonstrate that when the wireless communications are dominated by the short-distance social contact traffics, the throughput capacity can be greatly improved. Meanwhile, when the directional antenna beamwidth is at the order of Ω( 1 √log ), the throughput capacity is a constant. The wireless network with social contacts is scalable.

Data volume has been increasing explosively in recent years and learning methods are vitally important to extract key information in such mass data. Traditional offline learning requires multiple traversals to the dataset, thus frequently suffering from lack of computational resources. Online learning can benefit in shrinking total time consumed by training model and lowering computational capacity. However they often converge slowly due to memory loss. Considering partial feedback, we uniquely propose online Confidence- Weighted learning in Bandit setting (CWB) for lower cumulative error and higher convergence rate. Specifically, historical information is preserved to adjust the weights of features for speeding up the convergence rate. Moreover, we novelly integrate the random sampling into the confidence-weighted learning, which can balance the exploitation and exploration in bandit setting. Extensive experiments demonstrate efficiency and effectiveness of our proposed scheme.

The ubiquitous QR codes and some similar barcodes are becoming a convenient and popular approach to impromptu communication between mobile devices and their surrounding cyber-physical world. However, such codes suffer from two common drawbacks: poor viewing experience and inability to be identified through itself. In this work, we propose ART-code-- Adaptive Robust doT matrix barcode, which aims to preserve ART and CODE features in one visual pattern. It works on any surface (paper or electronic displays) and is able to convert any image or any form of human-readable contents (e.g., a picture, a logo, a slogan) into an ARTcode. It looks like an image which retains human-readable and aesthetically pleasant contents, and in the meanwhile, it acts as a QR code which conveys data bits over the visual channel. The core enablers in ARTcode are (1) the design of the colored dot matrix for data embedding with little distortion from the original image and (2) a comprehensive error correction scheme which enhances decoding robustness against noises and interferences from the original image in ARTcode. We implement ARTcode with the receiver on Android phones and the sender from a PC or a phone (it can be printed in paper). We conduct extensive user survey and experiments for evaluation. It validates the effectiveness and wide applicability of ARTcode: It works well with all of 197 images randomly downloaded, covering representative categories of the gray-scale images, logos, colored ones with low/medium/strong contrasts. The image quality is quite acceptable in a subjective user-perception survey with 50 participants and data communication accuracy achieves as high as 99% in almost all the cases (> 96% raw accuracy in ARTcode without error detection and other schemes).

Wireless sensor networks (WSNs) always collect an enormous amount of rich diverse environmental information. When WSNs grow large in scale, it is difficult for the sink to gather data due to the increasing transmission overhead. In order to improve the fidelity of data recovery and save energy, we propose a novel data aggregation and space-time global recovery scheme. The scheme exploits block Compressed Sensing (CS) to achieve both recovery fidelity and energy efficiency. We employ diffusion wavelets to partition a large WSN into sub-networks, which are regarded as blocks. For each sub-networks, diffusion wavelets are applied to get the sparse basis for the data to be compressed. In addition, we introduce temporal and spatial correlation into the optimum target function of global recovery algorithm. Simulation results show that space-time global recovery scheme holds higher fidelity of data recovery and greatly reduces the energy consumption. Typically, the normalized mean absolute error of our recovery scheme is less than 5%. Furthermore, the energy consumption is reduced more than 50% against plain CS.

In social networks, most information is stored, displayed and propagated in the form of text which is characterized by latent topics. With the discovery of latent topics, we can make more accurate prediction, inference and therefore, better applications, in social networks. Considering the dynamics and noise in social networks, we analyze data evolution from different perspectives including both common and discriminative topics. We adopt a basic model to factorize data matrix into components with an order representing latent topic and apply non-negative matrix factorization to two datasets as contrast to each other simultaneously. Time is taken into consideration as one order of the data matrix. Our basic model converts the decomposition problem into an optimization problem solved by block coordinate gradient descent, based on which the penalized model separates common part and discriminative part by adding penalty items. Next, a Bayesian generative model is established to avoid parameter tuning and overfitting, with the model parameters estimated via Gibbs sampling. Finally, we apply the models to both synthesized data and contrastive corpora of papers accepted by different conferences, as well as provide analysis of topic variation along with time.

Crowdclustering clusters data items in a crowdsourcing manner, which makes discovered item categories more consistent with human perception. However, due to diversity of crowdsourcing workers and fluctuation of the number of tasks assigned to each worker, inferring stable and reliable clusters is challenging. Moreover, an item may be associated with multiple attributes, and such items should be put into different clusters, which makes inferring accurate clusters more complicated. To address the challenges above, in this paper we present a robust and fast crowdclustering scheme for finding overlapping clusters of items. Distinguished from existing works, we extract reliable and stable cluster information from workers' answers by majority voting. We then formulate an optimization problem to find overlapping clusters, and develop a nonnegative matrix factorization based approach to approximate the optimal solution. Experiments show the robustness, accuracy and efficiency of our approach.

How to integrate labels from multiple labelers in order to obtain an accurate estimate of the ground truth is a major topic of crowdsourcing. One challenging issue is that, the labelers' abilities may vary significantly and the tasks distinguish each other in difficulties. Moreover, for a crowdsourcing system, task distributors have no idea in advance how many labels will be enough for each task. Consequently, an online task assignment mechanism based on the labeler expertise and question heterogeneousness becomes necessary. In this paper, we present such an online task assignment algorithm based on a probabilistic model consisting of both labeler abilities and question difficulties. We apply the online EM (Expectation Maximization) algorithm to make online estimations of system parameters, based on which we assign tasks adaptively. A series of simulation results have been demonstrated to show that our proposed scheme outperforms the conventional EM algorithm in efficiency and accuracy.

Indoor localization based on RSS fingerprinting approach has been attracting many research efforts in the past decades. Recent study presents a fundamental limit of the approach: given requirement of estimation accuracy, reliability of the user's localization result can be derived. As highly accurate indoor localization is essential to enable many location based services, a natural question to ask is: can we further improve the accuracy of the localization scheme fundamentally? In this paper, we theoretically show that the temporal correlation of the RSS can improve accuracy of the RSS fingerprinting based indoor localization. In particular, we construct a theoretical framework to evaluate how the temporal correlation of the RSS can influence the reliability of location estimation, which is based on a newly proposed radio propagation model considering the time-varying property of signals from a given Wi-Fi AP. Such a theoretical framework is then applied to analyze localization in the one dimensional physical space, which reveals the fundamental reason why performance improvement of localization can be brought by temporal correlation of the RSS. We further extend our analysis to high-dimensional scenarios. Experimental results corroborate our theoretical analysis.

In this paper, we show how to partition K users in a coded caching domain into L groups to reduce the complexity from O(2K) to [EQUATION]. We first show that the negative effects of the heterogeneity of cache sizes and partitioning on coded caching performance neutralize each other, which is the theoretical foundation of our partitioning schemes. We then prove the submodularity of the coded caching traffic volume function, based on which we develop a partition algorithm for minimizing the traffic volume. We show that the approximation ratio of proposed algorithm is better than the state-of-art result. Moreover, we develop a rounding algorithm to obtain the final partition based on Lovász extension, which resolves the issue of unbalanced partition. We implement our schemes in a testbed and validate our analysis and design with experiment results.

Periodic broadcasting has achieved prominent performance in VoD (Video on Demand) service in wired network. However, the development of wireless VoD service still has gone on hard and slowly in comparison to the rapid growth of mobile video service. In this paper, we propose a scalable video streaming method HQOBA (Heterogeneous Quality-Oriented Bandwidth Allocation) to address the problems in wireless network. To be concrete, in order to tackle the heterogeneous client type problem, we employ variable bandwidth allocation, instead of fixed bandwidth value for each channel. Moreover, to handle the problem of scarce server bandwidth and unpredictable wireless channel conditions, the proposed method takes the advantage of FGS (Fine Granular Scalable) video coding and Periodic Broadcasting to successfully transmit video segment. Further-more, we develop a bandwidth allocation algorithm to maximize client perceptual visual quality for the proposed transmit scheme. The experimental results of HQOBA scheme also validate the effectiveness.

Lane-level vehicular localization has been regarded as a critical technology component for future vehicle navigation services. Current lane-level vehicular localization systems require dedicated devices, making the systems difficult to popularize. Moreover, most systems depend heavily on continuous accurate GPS data, which may be interfered under specific environments. Efficient lane-level map building is another problem to deal with. In this paper, we propose an integrated system with the capability of map building and lane- level localization using smartphones. This system employs a crowdsourcing-based approach to collect information from multiple sensors (including GPS, orientation sensor and acceleration sensor), such as lane changes and turns. Based on the information, a lane localization schemes is designed using the tool of machine learning. The experimental results show that the proposed system achieves high accuracy of map building and lane-level localization.

Device-to-device (D2D) communication underlaying cellular networks is a promising technology for improving network resource utilization, and cooperative communication technology is usually used to mitigate the interference caused by D2D communication. Due to the additional signal processing cost introduced by cooperative communication, the cellular links who have the exclusive usage right of the network spectrum can charge the D2D links a fee for spectrum usage to enhance their profit. In this paper, we propose a contract-based cooperative spectrum sharing mechanism to exploit transmission opportunities for the D2D links and meanwhile achieve the maximum profit of the cellular links. We first design a cooperative relaying scheme that employs superposition coding at both the cellular transmitters and D2D transmitters. The cooperative relaying scheme can maximize the data rate of the D2D links without deteriorating the performance of the cellular links. Then, we employ a contract-theoretic framework to model the spectrum trading process based on the cooperative relaying scheme, and derive the optimal power-payment contracts for the cellular links under both the cases that the private information (i.e., channel quality) of the D2D links is continuous and discrete using tools from continuous-and discrete-time optimal control theories, respectively. Analytic and numerical results confirm the efficiency of the proposed spectrum sharing mechanism.

Rate adaptation (RA) has been traditionally used to achieve high goodput. In this work, we design RA for 802.11n NICs from an energy-efficiency perspective. We show that current MIMO RA algorithms are not energy efficient for NICs despite ensuring high throughput. The fundamental problem is that, the high-throughput setting is not equivalent to the energy-efficient one. Marginal throughput gain may be realized at high energy cost. We then propose EERA and EERA+, two energy-based RA schemes that trade off goodput for energy savings at NICs. EERA applies multidimensional ternary search and simultaneous pruning to speed up its runtime convergence in single-client operations, and uses fair airtime sharing to handle multiple-client operations. EERA+ further searches for multiple, staged rates to yield more energy savings over EERA. Our experiments have confirmed their effectiveness in various scenarios.

In this paper, we investigate the impact of information-theoretic secrecy constraint on the capacity and delay of mobile ad hoc networks (MANETs) with mobile legitimate nodes and static eavesdroppers whose location and channel state information (CSI) are both unknown. We assume n legitimate nodes move according to the fast i.i.d. mobility pattern and each desires to communicate with one randomly selected destination node. There are also nνstatic eavesdroppers located uniformly in the network and we assume the number of eavesdroppers is much larger than that of legitimate nodes, i.e., ν > 1. We propose a novel simple secure communication model, i.e., the secure protocol model, and prove its equivalence to the widely accepted secure physical model under a few technical assumptions. Based on the proposed model, a framework of analyzing the secrecy capacity and delay in MANETs is established. Given a delay constraint D, we find that the optimal secrecy throughput capacity is ~Θ(W((D/n))(2/3)), where W is the data rate of each link. We observe that: 1) the capacity-delay tradeoff is independent of the number of eavesdroppers, which indicates that adding more eavesdroppers will not degenerate the performance of the legitimate network as long as ν > 1; 2) the capacity-delay tradeoff of our paper outperforms the previous result Θ((1/nψe)) in , where ψe=nν-1=ω(1) is the density of the eavesdroppers. Throughout this paper, for functions f(n) and g(n), we denote f(n)=o(g(n)) if limn→∞(f(n)/g(n))=0; f(n)=ω(g(n)) if g(n)=o(f(n)); f(n)=O(g(n)) if there is a positive constant c such that f(n) ≤ cg(n) for sufficiently large n; f(n)=Ω(g(n)) if g(n)=O(f(n)); f(n)=Θ(g(n)) if both f(n)=O(g(n)) and f(n)=Ω(g(n)) hold. Besides, the order notation ~Θ omits the polylogarithmic factors for better readability.

This paper investigates the multicast capacity of static wireless social networks. We adopt the two-layer network model, which includes the social layer and the networking layer. In the social layer, the social group size of each source node is modeled as power-law distribution. Moreover, the rank-based model is utilized to describe the relation between source and destinations in the networking layer. Based on the two-layer network model, the probability density function (PDF) of the destination positions is analyzed and verified by numerical simulation, which is different from the traditional ad hoc networks. According to the PDF, the bound of the network capacity is derived, and we propose a Euclidean minimum-spanning-tree-based transmission scheme, which is proved to achieve the order of capacity bound for most cases. Finally, the capacity of social networks is compared to the traditional multicast ad hoc networks, which indicates that the capacity scaling performs better in social networks than traditional ones. To our best knowledge, this is the first work of analyzing the impact on the capacity of social relation and group size in multicast ad hoc networks for the rank-based model.

Comparing with the unicast technology, multiple flows from the same source in multicast scenario can be aggregated even if their destinations are different. This paper evaluates such distinction by the multicast gain on per-node capacity and delay, which are defined as the per-node capacity and delay ratios between multi-unicast and multicast ( m destinations for each multicast session). Particularly, the restricted mobility model is proposed, which is a representative mobility model characterizing a class of mobility models with different average moving speeds. The theoretical analysis of this model indicates that the mobility significantly decreases the multicast gain on per-node capacity and delay, though the per-node capacity of both unicast and multicast can be enhanced by mobility. This finding suggests that mobility weakens the distinction between multicast and unicast. Finally, a general framework of multicast study is constituted by analyzing the upper-bound ( Θ(m)), the lower-bound ( Θ(1)) and the main determinants of the multicast gain on both per-node capacity and delay regardless of mobility model.

This paper studies the throughput capacity of wireless networks with social characteristics. We propose a simple model to reflect both the social relations between nodes and power-law node degree distribution, and then examine their impact on capacity. We show the fact that two features above lead to traffic locality and improve capacity. Moreover, multicasting may be employed to further enhance performance when information is desired to be published from the source to all its contacts, of which the number follows power-law distribution. In addition, we propose the corresponding capacity-achieving communication schemes, which optimally exploit the underlying structure. Our study is an attempt to understand how social relations may impact on network capacity from a theoretical perspective, and provides fundamental insight on the design and analysis of real wireless networks.

Delayed traffic offloading is a promising paradigm to alleviate the cellular network congestion caused by explosive traffic demands. As we all know, in mobile networks, the delay profile for traffic is remarkable due to users’ mobility. How to exploit user delay tolerance to improve the profit of operator as well as mobile users becomes a big challenge. In this paper, we model this delayed offloading process as a monopoly market based on contract theory, where operator acts as the monopolist setting up the optimal contract by statistical information on user satisfaction. We propose an incentive mechanism to motivate users to leverage their delay and price sensitivity in exchange for service cost. To capture the heterogeneity of user satisfaction, we classify users into different types. Each user chooses a proper quality–price contract item according to its type. More specifically, we investigate this delayed offloading scheme under strongly incomplete information scenario, where user type is private information. We derive an optimal contract, which maximizes operator’s profit for both the continuous-user-type model and the discrete-user-type model. Numerical results validate the effectiveness of our incentive mechanism for delayed traffic offloading in cellular networks.

In this paper, we derive the critical transmission range, i.e., the smallest transmission distance of nodes such that wireless network can be connected, in large-scale clustered wireless networks. Contrary to most previous literature on independent and homogeneous mobility of nodes, we consider general settings with inhomogeneous node distribution and correlated mobility. In particular, we consider three network states based on the degree of correlation among nodes, i.e., cluster-sparse state (strong correlations), cluster-dense state (weak correlations), and cluster-transitional state (medium correlations). Under each state, we focus on the following problems: 1) how to place cluster-head nodes to minimize the critical transmission range and 2) what is the corresponding minimum critical transmission range. We derive the optimal distribution of cluster-head nodes that minimizes the critical transmission range, and show that the inhomogeneous distribution of mobile nodes leads to a smaller critical transmission range.

This paper studies the impacts of social relationships and inhomogeneous node distribution on wireless network performance. Motivated by the social characteristic that makes nodes more likely to communicate with nearby nodes, we present a model that captures the small-world property, power-law distribution, and multi-clustering topology of wireless networks. We compute the average traffic distance to derive the optimal per-node capacity, which is then analyzed from the social perspective. Based on the communication pattern, we introduce the quasi-strong ties and quasi-weak ties in order to discover how system parameters control the amount of network flows with different strengths of social relationships. Moreover, we propose an indicator of information propagation speed (IIPS), and show that there is a tradeoff between the IIPS and the per-node capacity of overall nodes.

Abstract In this paper, we focus on maximizing the influence of online social networks (OSNs). Particularly, we try to answer how to select proper information initiators such that information can propagate as widely as possible. We stress our attention on the susceptible‐infected model, a type of epidemic models, to describe the process of information diffusion. In general, OSNs can be classified into two categories, Facebook‐like OSNs and Twitter‐like OSNs. The former ones require bidirectional connections, while the latter do not, so we use the undirected unweighted graph and directed unweighted graph to describe them, respectively. We also pay additional attention to the nonidentity of the link probability on information transmission and build the weight graph, which can also cover both the two types of OSNs. In order to determine values of weight graph's weights, we introduce a learning method to obtain useful factors from raw data for assessing the true link probability on information transmission. Based on spectral analysis within the three graphs, our investigations on the information diffusion show that the spectral radius of the graph adjacency matrix can reflect the capability of information propagation, according to which we could determine effective initiators. We conduct our simulations on real OSNs. Experimental results show that our approach could effectively discover the initiators that spread information widely. Copyright © 2016 John Wiley & Sons, Ltd.

Abstract Device‐to‐device (D2D) communication underlaying cellular networks is a promising technology to improve network resource utilization. In D2D‐enabled cellular networks, interference among spectrum‐sharing links is severer than that in traditional cellular networks, which motivates the adoption of interference cancelation (IC) techniques at the receivers. However, to date, how IC can affect the performance of D2D‐enabled cellular networks is still unknown. In this paper, we present an analytical framework for studying the performance of two IC methods, that is, unconditional IC and successive IC, in large‐scale D2D‐enabled cellular networks using the tools from stochastic geometry. To facilitate the interference analysis, we propose an approach of stochastic equivalence of the interference, which converts the two‐tier interference (interference from the cellular tier and D2D tier) to an equivalent single‐tier interference. Based on the proposed stochastic equivalence models, we derive the general expressions for the successful transmission probabilities of both cellular uplinks and D2D links in the networks where unconditional IC and successive IC are respectively applied. We demonstrate how these IC methods affect the network performance using both analytical and numerical results. Copyright © 2016 John Wiley & Sons, Ltd.

Vehicular Ad Hoc Network (VANET) has been a hot topic in the past few years. Compared with vehicular networks where vehicles are densely distributed, sparse VANET have more realistic significance. The first challenge of a sparse VANET system is that the network suffers from frequent disconnections. The second challenge is to adapt the transmission route to the dynamic mobility pattern of the vehicles. Also, some infrastructural requirements are hard to meet when deploying a VANET widely. Facing these challenges, we devise an infrastructure-less unmanned aerial vehicle (UAV) assisted VANET system called Vehicle-Drone hybrid vehicular ad hoc Network (VDNet), which utilizes UAVs, particularly quadrotor drones, to boost vehicle-to-vehicle data message transmission under instructions conducted by our distributed vehicle location prediction algorithm. VDNet takes the geographic information into consideration. Vehicles in VDNet observe the location information of other vehicles to construct a transmission route and predict the location of a destination vehicle. Some vehicles in VDNet equips an on-board UAV, which can deliver data message directly to destination, relay messages in a multi-hop route, and collect location information while flying above the traffic. The performance evaluation shows that VDNet achieves high efficiency and low end-to-end delay with controlled communication overhead. Copyright © 2016 John Wiley & Sons, Ltd.

VoLTE (Voice-over-LTE) is the designated voice solution to the LTE mobile network, and its worldwide deployment is underway. It reshapes call services from the traditional circuit-switched telecom telephony to the packet-switched Internet VoIP. In this work, we conduct the first study on VoLTE security before its full rollout. We discover several vulnerabilities in both its control-plane and data-plane functions, which can be exploited to disrupt both data and voice in operational networks. In particular, we find that the adversary can easily gain free data access, shut down continuing data access, or subdue an ongoing call, etc. We validate these proof-of-concept attacks using commodity smartphones (rooted and unrooted) in two Tier-1 US mobile carriers. Our analysis reveals that, the problems stem from both the device and the network. The device OS and chipset fail to prohibit non-VoLTE apps from accessing and injecting packets into VoLTE control and data planes. The network infrastructure also lacks proper access control and runtime check.

Traffic offloading over Delay Tolerant Networks (DTNs) is a promising paradigm to alleviate the network congestion caused by explosive traffic demands. As we all know, in mobile networks, the delay profile for traffic is remarkable due to user's mobility. How to exploit delay tolerance to improve the profit of the operator as well as mobile users becomes a big challenge. In this paper, we investigate the problem of the interrelation of delay and user QoS. Inspired by contract theory, we model the delayed offloading process as a monopoly market where the operator makes pricing by considering statistical information about user satisfaction. In addition, we propose an incentive framework to motivate users to leverage their delay and price sensitivity in exchange for service cost. To capture the heterogeneity of user satisfaction, we classify users into different types. Each user chooses an appropriate quality-price contract item according to its type. Moreover, we derive an optimal contract which is feasible and maximizes the operator's profit as well. Numerical results validate the effectiveness of our incentive framework for traffic offloading over DTNs.

The minimum-length multicast tree can achieve efficient multicast transmissions and can be formulated as a Steiner Tree. Its construction is non-trivial and has been proven to be NP-hard. In this paper, we combine the design wisdoms in the minimum spanning tree and the shortest path, and propose a new distributed algorithm for constructing an approximate Steiner Tree, particularly applicable to dynamic wireless networks without centralized control. We rigorously prove the performance bounds of our algorithm in terms of tree length, running time and energy consumption. Let m be the multicast group size and n be the network size. We theoretically show that the ratio of our tree length to the minimum value is upper bounded by 2(1 + δ)/√3 (where δ can be any positive value). Simulation results show that this ratio is in fact very close to 1. We also prove that the running time is O( √(mn log m log3n)). The energy consumption is evaluated in terms of message complexity, and is upper bounded by O(n logm). In all, our algorithm achieves the near-optimal tree length, as well as the shortest running time and the lowest message complexity among all solutions we are aware of. We believe our algorithm provides a significant improvement in designing practical routing policies in wireless networks.

We study the throughput and delay scaling laws of cognitive radio networks (CRN) with mobile primary and secondary users. They operate at the same time, space and share the spectrum. The primary users (PUs) have higher priority to access the spectrum while the secondary users (SUs) should access opportunistically. Furthermore, we consider a unique situation where both PUs and SUs move according to a General Heterogeneous Speed-restricted Mobility (GHSM) model. In this model, we define (h + 1) heterogeneous moving patterns using a universal set T ={Ti|0 ≥ i ≤ h, Ai= n-iχ0/h}, where Aidetermines the moving area of each pattern. The set of primary (secondary) moving patterns T(p)(T(s)) is a randomly and independently selected subset of T. We assign n (nβ, where β > 1) primary (secondary) nodes to each moving pattern, and their initial positions are subject to a poisson point process. In addition, we have |T(p)|~|T(s)| = Θ1(h) = Θ(log n). By proposing a cooperative routing strategy, we fully utilize the mobility heterogeneity of primary and secondary users and achieve near-optimal throughput and delay performance of order Θ(poly log n) when χ0≥ β. In other cases, our transmission scheme shows advantages over [1] in delay performance of the primary network (PN) and over [2] in capacity of the secondary network (SN).

Multiple-Input Multiple-Output (MIMO) technology has become an efficient way to improve the capacity and reliability of wireless networks. Traditional MIMO schemes are designed mainly for the scenario of contiguous spectrum ranges. However, in cognitive radio networks, the available spectrum is discontiguous, making traditional MIMO schemes inefficient for spectrum usage. This motivates the design of new MIMO schemes that apply to networks with discontiguous spectrum ranges. In this paper, we propose a scheme called VSMC MIMO, which enables MIMO nodes to transmit variable numbers of streams in multiple discontinuous spectrum ranges. This scheme can largely improve the spectrum utilization and meanwhile maintain the same spatial multiplexing and diversity gains as traditional MIMO schemes. To implement this spectral-efficient scheme on cooperative MIMO relays in cognitive radio networks, we propose a joint relay selection and spectrum allocation algorithm and a corresponding MAC protocol for the system. We also build a testbed by the Universal Software Radio Peripherals (USRPs) to evaluate the performances of the proposed scheme in practical networks. The experimental results show that VSMC MIMO can efficiently utilize the discontiguous spectrum and greatly improve the throughput of cognitive radio networks.

Latency-sensitive applications (e.g., wireless gaming and TV remote play) are increasingly popular in home WiFi networks. Such millisecond-level latency requirements call for new fine-grained approaches at the link layer. In this paper, we show that current solutions work well for throughput but not for latency due to the long tail of the packet delay distribution. We thus propose LLRA, a new latency-aware rate adaptation scheme that reduces the tail latency for delay-sensitive applications. LLRA takes concerted design in rate control, frame aggregation scheduling and software/hardware retransmission dispatching. Our implementation and evaluation confirm the viability of LLRA in 802.11n home networks.

Device-to-device (D2D) communication underlaying cellular networks is a promising technology to improve network resource utilization. In D2D-enabled cellular networks, the interference among spectrum-sharing links is more severer than that in traditional cellular networks, which motivates the adoption of interference cancellation techniques such as successive interference cancellation (SIC) at the receivers. However, to date, how SIC can affect the performance of D2D-enabled cellular networks is still unknown. In this paper, we present an analytical framework for studying the performance of SIC in large-scale D2D-enabled cellular networks using the tools from stochastic geometry. To facilitate the interference analysis, we propose the approach of stochastic equivalence of the interference, which converts the two-tier interference (interference from both the cellular tier and D2D tier) to an equivalent single-tier interference. Based on the proposed stochastic equivalence models, we derive the general expressions for the successful transmission probabilities of cellular uplinks and D2D links with infinite and finite SIC capabilities respectively. We demonstrate how SIC affects the performance of large-scale D2D-enabled cellular networks by both analytical and numerical results.

With the pervasion of mobile devices, crowdsourcing based received signal strength (RSS) fingerprint collection method has drawn much attention to facilitate the indoor localization since it is effective and requires no pre-deployment. However, in large open indoor environment like museums and exhibition centres, RSS measurement points cannot be collocated densely, which degrades localization accuracy. This paper focuses on measurement point collocation in different cases and their effects on localization accuracy. We first study two simple preliminary cases under assumption that users are uniformly distributed: when measurement points are collocated regularly, we propose a collocation pattern which is most beneficial to localization accuracy; when measurement points are collocated randomly, we prove that localization accuracy is limited by a tight bound. Under the general case that users are distributed asymmetrically, we show the best allocation scheme of measurement points: measurement point density ρ is proportional to (cμ)2/3in every part of the region, where μ is user density and c is a constant determined by the collocation pattern. We also give some guidelines on collocation choice and perform extensive simulations to validate our assumptions and results.

Indoor localization has been an active research field for decades, where the received signal strength (RSS) fingerprinting based methodology is widely adopted and induces many important localization techniques such as the recently proposed one building the fingerprint database with crowd-sourcing. While efforts have been dedicated to improve the accuracy and efficiency of localization, the fundamental limits of RSS fingerprinting based methodology itself is still unknown in a theoretical perspective. In this paper, we present a general probabilistic model to shed light on a fundamental question: how good the RSS fingerprinting based indoor localization can achieve? Concretely, we present the probability that a user can be localized in a region with certain size, given the RSS fingerprints submitted to the system. We reveal the interaction among the localization accuracy, the reliability of location estimation and the number of measurements in the RSS fingerprinting based location determination. Moreover, we present the optimal fingerprints reporting strategy that can achieve the best accuracy for given reliability and the number of measurements, which provides a design guideline for the RSS fingerprinting based indoor localization facilitated by crowdsourcing paradigm.

Crowdsourcing systems allocate tasks to a group of workers over the Internet, which have become an effective paradigm for human-powered problem solving such as image classification, optical character recognition and proofreading. In this paper, we focus on incentivizing crowd workers to label a set of binary tasks under strict budget constraint. We properly profile the tasks' difficulty levels and workers' quality in crowdsourcing systems, where the collected labels are aggregated with sequential Bayesian approach. To stimulate workers to undertake crowd labeling tasks, the interaction between workers and the platform is modeled as a reverse auction. We reveal that the platform utility maximization could be intractable, for which an incentive mechanism that determines the winning bid and payments with polynomial-time computation complexity is developed. Moreover, we theoretically prove that our mechanism is truthful, individually rational and budget feasible. Through extensive simulations, we demonstrate that our mechanism utilizes budget efficiently to achieve high platform utility with polynomial computation complexity.

Coded caching can exploit new multicast opportunities even when multiple users request different pieces of content, and thus can significantly reduce the backhaul requirement for serving high-volume content. However, existing studies of coded caching have been limited to the scenarios where all files of interest are of a common size. This work studies the performance limits of coded caching when the file sizes are different. We derive a new lower bound and an achievable upper bound for the worst-case transmission rate under coded caching, and show that these two bounds differ by at most a Θ(log K) factor, where K is the number of users in the system. There are two key novelties in our analysis. First, our lower bound is derived by considering a new cut-set bound where larger files are requested more times. The analysis of this new cut-set bound requires careful concatenation of several entropy inequalities. Compared to a lower bound using standard cut-set arguments, our lower bound is improved by a Θ(log K) factor. Second, our achievable scheme uses a caching probability that increases proportionally with the file size. Compared to schemes that use a common caching probability, the achievable rate of our scheme is reduced by a Θ K/logk2factor.

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multicast tree can be modeled as the Steiner Tree Problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multicast trees in wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple and distributed algorithm, which we call Toward Source Tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running time, tree length and energy efficiency. We prove that its running time is O(√nlog n), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, give a theoretical upper bound and use simulations to show the ratio between them is only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of the number of forwarding nodes in multicast trees, and prove that it is order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.

In this paper, we study the impact of human mobility on throughput and delay for people-centric applications in mobile ad hoc networks (MANETs). We consider a general human mobility model for MANETs, which can capture important features of human mobility, such as time correlation, node correlation, location heterogeneity, and node heterogeneity. Multiple unicasts with general arrival processes are delivered, and nodes are equipped with infinite buffers. Under our system model, we first characterize the network stability region in terms of the probability of each node set visiting each location and the amount of transmission resources at each location. We show that the node correlation and heterogeneity of locations' popularity usually decrease the size of the network stability region, whereas the diversity of locations visited by a node usually increases the size of the network stability region. Then, by solving a stability-related optimization problem, we develop a throughput-optimal policy based on the obtained optimal solution. We obtain the upper and lower bounds of the delay performance under the proposed policy. Finally, using simulations based on a theoretical model and some real traces, we verify the analytical results and compare the performance of the proposed policy with some existing policies.

Device-to-device (D2D) communication underlaying cellular networks is a promising technology to improve network resource utilization. In D2D-enabled cellular networks, interference generated by D2D communications is usually viewed as an obstacle to cellular communications. However, in this paper, we present a new perspective on the role of D2D interference by taking security issues into consideration. We consider a large-scale D2D-enabled cellular network with eavesdroppers overhearing cellular communications. Using stochastic geometry, we model such a network and analyze the signal-to-interference-plus-noise ratio (SINR) distributions, connection probabilities and secrecy probabilities of both the cellular and D2D links. We propose two criteria for guaranteeing performances of secure cellular communications, namely the strong and weak performance guarantee criteria. Based on the obtained analytical results of link characteristics, we design optimal D2D link scheduling schemes under these two criteria respectively. Both analytical and numerical results show that the interference from D2D communications can enhance physical layer security of cellular communications and at the same time create extra transmission opportunities for D2D users.

In this paper, we study the throughput and delay scaling laws for cognitive radio network with static primary users and heterogeneous mobile secondary users coexist in the unit planar region for both without base-station case and with base-station case. The primary network consists of $n$ randomly and uniformly distributed static primary users with higher priority to access the spectrum. The secondary network consists of $m=(h+1)n^{1+\epsilon}$ heterogeneous mobile secondary users with $h=O(\log n)$ We use standard asymptotic notations in our paper. Consider two nonnegative function $f(\cdot)$ and $g(\cdot)$ : (1) $f(n)=o(g(n))$ means $\lim_{n\rightarrow\infty}f(n)/\break g(n)= 0$ . (2) $f(n)=O(g(n))$ means $\lim_{n\rightarrow\infty}f(n)/g(n) . (3) $f(n)=\omega(g(n))$ means $\lim_{n\rightarrow\infty}f(n)/g(n)=\infty$ . (4) $f(n)=\Omega(g(n))$ means $\lim_{n\rightarrow\infty}f(n)/g(n) > 0$ . (5) $f(n)=\Theta(g(n))$ means $f(n)=O(g(n))$ and $g(n)=O(f(n))$ . (6) $f(n)=\mathtilde{\Theta}(g(n))$ means that $f(n)=\Theta(g(n))$ when poly-logarithmic factors are ignored.

In this paper, we study the capacity and delay scaling laws of cognitive radio networks (CRN) with static primary nodes (PNs) and mobile secondary nodes (SNs). The primary network consists of randomly distributed primary nodes of density n, which have a higher priority to access the spectrum. The secondary network consists of randomly distributed secondary nodes of density m = nβ, where β represents the density relationship in CRN. Secondary nodes move according to hybrid random walk models with parameter α (0 ≤ α-2α). Motivated by observation that the performance of CRN can benefit from the cooperation among primary nodes and secondary nodes, we propose a novel cooperative scheduling mechanism to fully utilize the mobility and geographic information of secondary nodes to enhance the performance of the primary network. For both networks, the delay performance varies with α. We show that the delay performance of primary network can be significantly improved from O(n/log n) [16] to Θ(nβ/3log n) when β <; 3 for an optimal value of α, while a near-optimal throughput of Θ(1/log n) is obtained. Furthermore, the secondary network can still achieve the same throughput and delay scaling laws as a stand-alone network simultaneously.

Even the greedy routing is widely used in wireless networks, its theoretical study is still limited in vehicle environments. In this paper, we theoretically analyze the performance of the greedy routing under three typical vehicle scenarios, i.e., the single-lane road, the multilane road, and the multilevel road. We first propose the analytical model by analyzing characteristics of traffic environments, which contain the width and multilevel features of roads. Specifically, we prove that the road-width is ignorable under certain conditions, whereas the data measured in an outdoor experiment reveal that the multilevel feature is non-ignorable because its existence dramatically degrades the transmission range. Based on the model, we analyze the routing length of the greedy routing for all scenarios in the following three aspects. 1) We derive the distribution function for the first one-hop progress. 2) We prove that routing increments are history-dependent and give one sufficient condition that ensures these increments are approximately i.i.d. 3) We calculate the routing length described by the$h$-hop coverage and hop count using the renewal theory. Finally, simulations are conducted to verify the accuracy of our analysis.

With the advent of smart portable devices and location-based applications, user's mobility pattern is found to be highly dependent on varying locations. In this paper, we analyze asymptotic throughput-delay performance of mobile ad hoc networks (MANETs) under a location popularity based scenario, where users are more likely to visit popular locations. This work provides a complementary perspective compared with previous studies on fundamental scaling laws for MANETs, mostly assuming that nodes move uniformly in the network. Specifically, we consider a cell-partitioned network model with cells of known popularity, which follows a Zipf's law distribution with popularity exponent α. We first conduct the analysis under traditional store-carry-forward paradigm, and find that location heterogeneity affects the network performance negatively, which is due to the waste of potential transmission opportunities in popular cells. Motivated by this observation, we further propose a novel store-carry-accelerate-forward paradigm to enhance the network communication, exploiting these potential transmissions. Theoretical results demonstrate that our proposed scheme outperforms all delay-capacity results obtained in conventional scheme for any α. In particular, when α = 1, it can achieve a constant capacity with an average delay of Θ(√n) (except for a polylogarithmic factor), while the delay is Θ(n) in conventional scheme. And by letting α = 0, our results can cover Neely's scaling laws. Moreover, we show that the delay-capacity tradeoff ratio satisfies ≥Θ(√n), revealing that exploiting location popularity can effectively improve the performance in MANETs.

In cognitive radio networks (CRNs), secondary users (SUs) can flexibly access primary users' (PUs') idle spectrum bands, but such spectrum opportunities are dynamic due to PUs' uncertain activity patterns. In a multihop CRN consisting of SUs as relays, such spectrum dynamics will further cause the invalidity of predetermined routes. In this paper, we investigate spectrum-mobility-incurred route-switching problems in both spatial and frequency domains for CRNs, where spatial switching determines which relays and links should be reselected and frequency switching decides which channels ought to be reassigned to the spatial routes. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved. We further formulate the route-switching problem as the Route-Switching Game, which is shown to be a potential game and has a pure Nash equilibrium (NE). Accordingly, efficient algorithms for finding the NE and the$\epsilon $–NE are proposed. Then, we extend the proposed game to the incomplete-information scenario and provide a method to compute the Bayesian NE. Finally, we prove that the price of anarchy of the proposed game has a deterministic upper bound.

In this paper,1we investigate the throughput and delay in heterogeneous cognitive radio networks (HCRN), where the data source and the destination (S-D) is heterogeneously distributed following a rank based model and secondary users (SUs) provide relay service for primary users (PUs). We consider two scenarios: 1) PUs and SUs are both static; and 2) PUs are static and SUs are mobile. For scenario 1, we show that the primary network throughput is the same for different heterogeneous extents of S-D distribution owing to the flexible assistance of SUs, while the throughput of secondary networks is proven to be changing with the S-D heterogeneity exponent α, which depicts the variation of different heterogeneous extents of S-D distribution. In addition, the delay of both primary and secondary networks are shown to be altering with α. Further, we reveal that the number of SUs required to assist PUs can be dramatically reduced when considering the S-D heterogeneity, while achieving the same primary network throughput. For scenario 2, we utilize a modified uniform mobility (MUM) model to depict the motion of SUs and mainly focus on the analysis of throughput and delay for primary networks. It shows that the primary network throughput is also free of the heterogeneous extent of S-D distribution, while the delay changes with α. Due to the mobility of SUs, a better delay-throughput tradeoff of primary networks is achieved compared with that in scenario 1.

This paper investigates random walk mobility models with location heterogeneity, where different locations may have different neighboring regions. We consider$n$locations in a one-dimension network and investigate two cases, i.e.,full-range locationswhere nodes situated have the capability to shuffle throughout the network andlong-range locationswhere nodes are allowed to move to positions nearby within a certain range. In the former situation, with the exact expressions derived, we find location heterogeneity has a critical impact on the first hitting time of random walk, varying from$\Theta (n)$to$\Theta \left(n^3\right)$according to different extent of heterogeneity. The result covers, as two special cases, both the classic independent and identically distributed (i.i.d) mobility and traditional random walk when varying the number of full-range locations. In the latter one, our asymptotic results on both the first crossing time and cover time suggest that they are inversely proportional to the range of neighboring region$r$($\propto r^{-2}$and$\propto r^{-1}$, respectively). Furthermore, with multiple concurrent random walks introduced, the first hitting time can be drastically decreased and the effect is strengthened if combined with location heterogeneity. In addition, our investigation into the stationary distribution of nodes indicates that the uniformity no longer holds due to different transition probabilities, as a result of location heterogeneity. We also conduct extensive simulation results to verify our observations and enhance the understanding on the impact of network parameters. Based on the insights obtained, we move forward to investigate the impact of location heterogeneity in two-dimension networks.

In this paper, we study the problem of data gathering with compressive sensing (CS) in wireless sensor networks (WSNs). Unlike the conventional approaches, which require uniform sampling in the traditional CS theory, we propose a random walk algorithm for data gathering in WSNs. However, such an approach will conform to path constraints in networks and result in the non-uniform selection of measurements. It is still unknown whether such a non-uniform method can be used for CS to recover sparse signals in WSNs. In this paper, from the perspectives of CS theory and graph theory, we provide mathematical foundations to allow random measurements to be collected in a random walk based manner. We find that the random matrix constructed from our random walk algorithm can satisfy the expansion property of expander graphs. The theoretical analysis shows that a k-sparse signal can be recovered using `1 minimization decoding algorithm when it takes m = O(k log(n=k)) independent random walks with the length of each walk t = O(n=k) in a random geometric network with n nodes. We also carry out simulations to demonstrate the effectiveness of the proposed scheme. Simulation results show that our proposed scheme can significantly reduce communication cost compared to the conventional schemes using dense random projections and sparse random projections, indicating that our scheme can be a more practical alternative for data gathering applications in WSNs.

In this paper, we investigate connectivity and transmission delay of secondary users in large-scale wireless cognitive radio (CR) ad hoc networks from a percolation-based perspective. Using the random connection model, we study the unreliability of wireless secondary links in CR ad hoc networks, which has not been well studied in the existing literature. By introducing two auxiliary random graphs and using continuum percolation theory, we study the impacts of key system parameters on connectivity and transmission delay in a CR network. We first characterize three behavioral regions of connectivity for a secondary network, i.e., disconnectivity, long-term connectivity and instantaneous connectivity regions. We show that the unreliability of secondary links does not affect the disconnectivity region, but affects the long-term connectivity and instantaneous connectivity regions. Using the ergodic theorem, we then study the scaling behavior of transmission delay with respect to the distance between two randomly chosen secondary users in a connected secondary network for two cases. Specifically, when propagation delay is negligible, we show that transmission delay scales linearly and sub-linearly with distance in the long-term connectivity and instantaneous connectivity regions, respectively. When propagation delay is considered, we show that transmission delay scales linearly with respect to distance in both the long-term connectivity and instantaneous connectivity regions.

In the asymptotic analysis of large scale mobile networks, most previous works assume that nodes move in all the cells identically. We put forward this line of research by considering location popularity, which is verified by recent experimental studies. Nodes tend to visit some popular locations and go to other locations less frequently. We first analyze its multicast capacity and delay under the traditional 2-hop store-carry and forward paradigm. With different location popularity distributions, network capacity and delay will vary according to the distribution exponent. As the popularity becomes more diverse, less concurrent transmissions are tolerated in the network, which brings down the performance. Observing that transmission opportunity is not fully utilized in popular cells for 2-hop paradigm, we put forward a 3-hop scheme, which is called store-carry-accelerate-forward scheme. In this 3-hop scheme, each packet is first sent to an initial relay, who carries the packets into the popular cells and then broadcasts to multiple nodes to accelerate the delivery. By so doing, we showed that the 3-hop scheme outperforms the 2-hop scheme for all popularity distributions. Furthermore, we study the delay-capacity tradeoffs for multicast under both schemes and the buffer needed for stability requirement. Our results reveals the joint impact of multicast and location heterogeneity on the design of transmission schemes, and may shed new insights for future studies.

In this paper, we focus on the capacity and delay tradeoff for multicast traffic pattern in cognitive radio mobile ad hoc networks (MANETs). In our system model, the primary network consisting of n primary nodes overlaps with the secondary network consisting of m secondary nodes in a unit square. Assume that all nodes move according to an independent and identically distributed mobility model, and each primary node serves as a source that multicasts its packets to kp primary destination nodes, whereas each secondary source node multicasts its packets to ks secondary destination nodes. Under the cell partitioned network model, we study the capacity and delay for the primary networks under two communication schemes, i.e., noncooperative scheme and cooperative scheme. The communication pattern considered for the secondary network is cooperative scheme. Given that m = nβ(β > 1), we show that per-node capacities O(1/kp) and O(1/ks) are achievable for the primary network and the secondary network, with average delays Θ(n log kp) and Θ(m log ks), respectively. Moreover, to reduce the average delay in the secondary network, we employ a redundancy scheme and prove that a per-node capacity O(1/ks√m log ks) is achievable with average delay Θ(√m log ks). We find that the fundamental delay-capacity tradeoff in the secondary network is delay/capacity ≥ O(mkslog ks) under both cooperative and redundancy schemes.

We consider the problem of cooperative spectrum sharing among primary users PUs and secondary users SUs in cognitive radio networks. In our system, each PU selects a proper set of SUs to serve as the cooperative relays for its transmission and in return, leases portion of channel access time to the selected SUs for their own transmission. PU decides how to select SUs and how much time it would lease to SUs, and the cooperative SUs decide their respective power levels in helping PU's transmission, which are proportional to their access times. We assume that both PUs and SUs are rational and selfish. In single-PU scenario, we formulate the problem as a noncooperative game and prove that it converges to a unique Stackelberg equilibrium. We also propose an iterative algorithm to achieve the unique equilibrium point. We then extend the proposed cooperative mechanism to a multiple-PU scenario and develop a heuristic algorithm to assign proper SUs to each PU considering both performance and fairness. The simulation results show that when the competition among SUs is fierce, the performance gap between our heuristic algorithm and the optimal one is smaller than 3%. Copyright © 2013 John Wiley & Sons, Ltd.

Abstract As a powerful economic theory, auction mechanism has been extensively studied in dynamic spectrum allocation for cognitive radio networks (CRNs) recently. Different from most of existing works that focused on the mechanism design from the spectrum owner's side, we study from a new perspective on profit maximization of the secondary users (SUs). Because the spectrum auction mechanism has already been designed by the spectrum owner, we derive SUs' optimal bid strategies, which maximize their profits. First, we relax the limitation of SU's value on spectrum band, which is formerly defined as the transmission rate on channel, and introduce the affiliated value considering the impacts from other SUs. Further, the optimal value determination function is derived, which maximizes SU's expected profit; second, we analyze the auctioneer cheating issue, which has great influence on SU's profit, and the Nash equilibrium strategies for both spectrum owner and SUs are derived. Moreover, the repeated auction game mechanism is proposed that resists the auctioneer cheating effectively. Copyright © 2013 John Wiley & Sons, Ltd.

Online Social Network becomes the most prevalent platform for exchanging information between users, maintaining friendships online. As is well-known to us, however, some friendships even those intimate ones might vanish. Therefore, precisely modeling and predicting state of each online relationship is worthwhile in many respects. For social communication services such modeling permits new and novel online services. In addition, constructing this model might enlighten us in exploiting information spreading pattern in online social network. In this paper, we propose a model in determining a probability distribution which describes the ‘surviving time’ of each friendships by applying one commonly used method in sociology, survival analysis. We discuss a series of social explanatory variables that highly affect this probability distribution. Moreover, methods in the moving average process are devoted to determining the appropriate parameter in survival model. Furthermore, to avoid the high computational complexity in kernel learning we impose sparsity in our model. Finally, with the experiments on real data, the proposed survival model is proven to be of high accuracy, and thus of great potential for further applications.

Auction is often applied in cognitive radio networks due to its efficiency and fairness properties. An important issue in designing an auction mechanism is how to utilize the limited spectrum resource in an efficient manner. In order to achieve this goal, we propose a predictive double spectrum auction model in this paper. Our auction model first obtains the bidding range from statistical analysis, and then separates the interval into independent states and employees a Markovian prediction based algorithm to generate guidelines for the bidding range of primary and secondary users, respectively. Comparing with existing approaches, our proposed auction model is more efficient in spectrum utilization and satisfies the economic properties. Extensive simulation results show that our work achieves an utilization ratio up to 91%.

Network throughput and packet delay are both important performance metrics in Ad-Hoc networks. While uncorrelated mobility has been proved to be able to increase the network capacity at the cost of delay, the influence of correlated mobility on network performance has not been well studied. In correlated mobility model, nodes in the same group are constrained to lie in a disc area, whose center moves uniformly according to the i.i.d. model; however, it is still an open issue how to evaluate the performance of capacity and delay tradeoff in hybrid Ad-Hoc networks. In this paper, we propose a theoretical framework to examine such issue when relay nodes are under correlated mobility and static nodes are acting as transmitters and receivers. Simulation results shows that our algorithm provides better throughput delay tradeoff than i.i.d. model.

Crowdsourcing is an effective paradigm in human centric computing for addressing problems by utilizing human computation power. While efforts have been made to study the crowdsourcing systems for labeling tasks such as classification, those for scoring tasks with continuous and correlative answers have not been well studied. In this paper, we propose two inference algorithms, MCE (Maximum Correlation Estimate) and WMCE (Weighted Maximum Correlation Estimate), to infer true answers based on answers submitted by workers. When estimating answers, WMCE algorithm assigns diverse weight to submitted answers of workers based on their quality while MCE algorithm assigns identical weight to submitted answers of all workers. For a fixed worker population, we reveal that the increase in task redundancy1can improve accuracy of estimated answers but such improvement is limited within a certain level. We further show that WMCE algorithm can reduce the influence of this limitation better than MCE algorithm for the same crowdsourcing system. Simulation results validate our theoretical analysis and show that WMCE algorithm outperforms MCE algorithm in the accuracy of estimated answers.

Mobile Crowdsensing is an effective paradigm to perform tasks in many scenarios by utilizing crowd intelligence and sensing resources. However, the responses from users are often unreliable due to the low-paid rewards and their biased expertise of the crowd. In this paper, we propose a multi-class labeling scheme based on BCH codes (BCH-MCL) for the mobile crowdsensing system where the quality of crowd is unknown. For multi-class labeling tasks, BCH-MCL provides each label a BCH codeword with maximum error correction capability, and maps the responses of the crowd into an estimated codeword to determine the final estimated label. The theoretical analysis characterizes the fault-tolerance capability of BCH-MCL, and derives an upper bound of the mis-label probability for the proposed BCH-MCL scheme, with a necessary condition and a sufficient condition presented. Furthermore, we prove that BCH-MCL can achieve a more accurate estimation and much lower computational complexity, compared with prior work DCFECC. Simulation results validate our theoretical analysis and indicate the effectiveness and efficiency of the proposed BCH-MCL.

Offloading data from cellular networks to WiFi or femtocell networks is an efficient way to alleviate the network congestion caused by rapidly increasing demands for mobile data. To this end, an Internet Service Provider (ISP) is willing to deploy WiFi/femtocell networks. With the advent of such networks, it is necessary to analyze how the ISP sets data plans to improve its profit while mobile data offloading is supported. In this paper, we develop a contract-based scheme to deal with data plan setting problem in two-tier networks. The contract offered by the ISP is a set of data plans which provide different combinations of data volume and price. We classify consumers into different types according to their percentages of data traffic offloaded to WiFi/femtocell networks. Each consumer can choose its own data plan based on its type, which is private information. Under asymmetric information scenario, we provide the necessary and sufficient conditions for the feasibility of a contract and then we derive the optimal contract which maximizes the ISP's profit. Numerical results validate the effectiveness of our scheme and indicate that the ISP can improve its profit by raising the throughput of its WiFi/femtocell networks and/or lowering its energy cost.

Recently, security of cognitive radio (CR) is becoming a severe issue. There is one kind of threat, which we call greedy spectrum occupancy threat (GSOT) in this paper, has long been ignored in previous work. In GSOT, a secondary user may selfishly occupy the spectrum for a long time, which makes other users suffer additional waiting time in queue to access the spectrum and leads to congestion or breakdown. In this paper, a queueing model is established to describe the system with greedy secondary user (GSU). Based on this model, the impacts of GSU on the system are evaluated. Numerical results indicate that the steady-state performance of the system is influenced not only by average occupancy time, but also by the number of users as well as number of channels. Since a sudden change in average occupancy time of GSU will produce dramatic performance degradation, the greedy second user prefers to increase its occupancy time in a gradual manner in case it is detected easily. Once it reaches its targeted occupancy time, the system will be in steady state, and the performance will be degraded. In order to detect such a cunning behavior as quickly as possible, we propose a wavelet based detection approach. Simulation results are presented to demonstrate the effectiveness and quickness of the proposed approach.

In camera sensor networks (CSNs), full view coverage, in which any direction of any point in the operational region is covered by at least one camera sensor, is of great significance since image shot at the frontal viewpoint considerably increases the possibility to recognize the object. However, finding the critical condition to achieve full view coverage in mobile heterogeneous CSNs remains an open question. In this paper, we analyze both the static and mobile random deployed camera sensor networks. A centralized parameter - equivalent sensing radius (ESR) - is defined to evaluate the critical requirement for asymptotic full view coverage in heterogeneous CSNs. We derive the critical sensing range for full view coverage under static model, 2-dimensional random walk mobility model, 1-dimensional random walk mobility model and random rotating model. We then discuss the impact of various mobility patterns on sensing energy consumption and study the relationship between ESR and percentage of full view coverage, and show that random walk mobility model can decrease the sensing energy consumption under certain delay tolerance. To our knowledge, our work is the very first that derive the critical condition to achieve full view coverage in mobile heterogeneous CSNs.

Cognitive radio (CR) technique is considered an effective mechanism to relieve the spectrum scarcity issue, where the secondary users (SUs) can utilize the idle spectrum of the primary users (PUs). How the performance of the wireless network will be influenced by the introduction of CR technique has been attracting much attention in past years. While many efforts have been made to study the cognitive radio network, where the data source and the destination (S-D) is homogeneously distributed, the research on cognitive radio networks (CRN) with heterogeneous S-D distribution is still very limited. In this paper, we investigate the throughput and delay scaling law in the heterogeneous cognitive radio network (HCRN), where the S-D pair follows a rank based model and SUs provide relay service for PUs in reciprocating the utilization of PUs' idle spectrum. By applying a cellular TDMA scheduling scheme, we show that the primary network throughput is the same for different heterogeneous extents of S-D distribution owing to the flexible assistance of SUs, while the throughput of secondary networks is proven to be changing with respect to the S-D heterogeneity exponent denoted by α. In addition, the delay scaling are derived for both primary and secondary networks and shown to be altering in accordance with α. Further, we reveal that the density of SUs required to assist PUs can be dramatically reduced when considering the S-D heterogeneity, while achieving the same primary network throughput.

We analyze the scaling law in wireless ad hoc networks with the correlated mobility model. The former work about correlated mobility has shown the maximum throughput and the corresponding delay of several sub-cases, but the optimal throughput performances under various delay tolerant condition (the optimal delay-throughput tradeoff) remains open. We study the properties of correlated mobility model and establish the upper bound of delay-throughput tradeoff for several sub-cases. Then we find out an achievable lower bound by studying the optimal scheduling parameters and their constrains. We exploit the node correlation to achieve the delay-throughput tradeoff and give a picture that how node correlation impacts the packet delay, asymptotic throughput, and their tradeoff.

The contradiction between dynamic user traffic and fixed data plans has drawn increasing attention in the field of mobile applications. In this paper we build a data plan sharing system named INDAPSON to consider a scenario where some smartphone users have surplus data traffic and are willing to help others download data. Virtual credits can be gained as reward, which can be used to ask for future help in downloading. To realize this model, we make the following contributions: 1) A dynamic self-organization strategy to adapt to mobile terminals; 2) An incentive mechanism named RAP to encourage participation; 3) Power-saving strategies to reduce power consumption. The main advantage of our system is that users gain improvement in download rate while being able to convert their surplus data traffic to virtual credits. The results of experiment and simulation show that users in our system can manage their surplus data plan more efficiently while a highspeed download rate can be achieved.

There have been many traffic light control systems around the globe, but the high cost of infrastructure and maintenance hinders their wide deployment. However, speed-advisory systems enabled by on-vehicle devices are much cheaper and easier to deploy. The first challenge of such systems is to get the traffic signal schedule in complex intersections. The second challenge is to get map information and calculate the distance. Facing these challenges we devise and implement a speed-advisory driving system called CityDrive, which harnesses the sensor and GPS data from a wide participation of smartphones to suggest proper speed for drivers so that they arrive at intersections in green phase. CityDrive first generates a road map and then infers traffic signal schedules, using only smartphones and a server. CityDrive does not eliminate stops at intersections, but it tries to maximize the probability that vehicles cruise through intersections in green phase. Both simulation and real test show that this continuous speed advisory service effectively smoothes traffic flow and significantly reduces energy consumption.

Increasingly, more spectrum bands are utilized for unlicensed use in wireless cognitive networks. It is important to study how information-theoretic secrecy capacity is affected in large-scale cognitive networks. We consider two scenarios: (1) non-colluding case, where eavesdroppers decode messages individually. In this case, we propose a new secure protocol model to analyze the transmission opportunities of secondary nodes. We show that the secrecy capacity of the primary network is not affected, while the secondary network can achieve the same performance as a standalone network in the order sense. Since our analysis is general as we only make a few relaxed assumptions on both networks, the conclusions hold when both networks are classic static networks, networks with i.i.d mobility, multicast networks etc. (2) colluding case where eavesdroppers can collude to decode a message. In that case, we show that the lower bound of per-node secrecy capacity of the primary network is Ω(1/√n φe-2/α-1(n)) when the eavesdropper density is φe(n)=Ω(log2n). Interestingly the existence of secondary nodes increases the secrecy capacity of the primary network.

This paper investigates the problem of optimally determining source-destination connectivity in random graphs. We consider the classic Erdos-Renyi (ER) random graph with $n$ nodes, where an edge independently exists between any two nodes with probability p. The problem examined is that of determining whether a given pair of nodes, a source S and a destination D, are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which leads to the most opportunities for connection. Interestingly, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30 log2n operations to determine which edge to test next. The result also extends to some more general graphs.

We propose the correlated mobile k-hop clustered networks model to implement correlated node movements and scalable clusters. We divide network states into three categories, i.e., cluster-sparse state, cluster-dense state and cluster-inferior dense state, and achieve the critical transmission range for the last two states. Furthermore, we find that correlated mobility and cluster scalability are closely related with each other and the impact of these two properties on connectivity is mainly through influencing network state transition.

We study the relay-based communication schemes for cooperative spectrum sharing among multiple primary users (PUs) and multiple secondary users (SUs) with incomplete information. Inspired by the matching theory, we model the network as a matching market. In this market, each PU proposes a certain proposal representing a combination of relay power and spectrum access time to attract the SUs, while each SU maximizes its utility by selecting the most suitable PU. We derive the sufficient and necessary conditions for a stable matching in which none of the PUs or SUs would like to change its decision. We further establish a distributed matching algorithm (DMA) and a DMA with utility increasing (DMA-UI) to achieve the equilibria in partially incomplete and incomplete information scenarios, respectively. Moreover, we provide detailed discussions on the implementation of the distributed algorithms in practical networks. Simulation results show that the losses of PUs' total utilities caused by incomplete information are diminished when the number of SUs increases. Specifically, the effects of the incomplete information are reduced as the competition among SUs (PUs) is more intensive than that among PUs (SUs).

In this paper, we study the throughput and delay in wireless cognitive social networks. Specifically, we consider a common scenario for cognitive radio networks (CRNs) where the primary and secondary networks operate at the same time and space and share the spectrum. On this basis, we integrate a social relationship into the CRN where each source node selects its destination upon a rank-based model, which captures the social characteristic well. By applying a cellular time-division multiple-access scheduling scheme, we first characterize the distinct traffic pattern caused by the social relationships between nodes. Then, we derive the achievable throughput and delay for both primary and secondary networks under the new network setting. In addition, we also study the cognitive social networks with infrastructure where I = o1(n) base stations are regularly deployed within the primary network. Given a probabilistic routing strategy, throughput of the proposed network is recalculated. Particularly, due to the social relationships between nodes, we reveal that a larger I is required if we expect a significant capacity gain within the primary network compared with previous works.

In this paper, we give a global perspective of multicast capacity and delay analysis in Mobile Ad Hoc Networks (MANETs). Specifically, we consider four node mobility models: (1) two-dimensional i.i.d. mobility, (2) two-dimensional hybrid random walk, (3) one-dimensional i.i.d. mobility, and (4) one-dimensional hybrid random walk. Two mobility time-scales are investigated in this paper: (i) fast mobility where node mobility is at the same time-scale as data transmissions and (ii) slow mobility where node mobility is assumed to occur at a much slower time-scale than data transmissions. Given a delay constraint$D$, we first characterize the optimal multicast capacity for each of the eight types of mobility models, and then we develop a scheme that can achieve a capacity-delay tradeoff close to the upper bound up to a logarithmic factor. In addition, we also study heterogeneous networks with infrastructure support.

In this paper, we investigate the multicast capacity for static ad hoc networks with heterogeneous clusters. We study the effect of heterogeneous cluster traffic (HCT) on the achievable capacity. HCT means cluster clients are more likely to appear near the cluster head instead of being uniformly distributed across the network. Such a property is commonly found in real networks. By adopting max-min fairness, the minimum among all individual multicast capacities of clusters can be maximized. Since this minimal individual multicast capacity will not be maximized unlimitedly, our work focuses on deriving the upper bound of the minimum individual multicast capacity (we refer it as minimum capacity for simplicity) in HCT, which provides the best performance for the minimum multicast capacity to attain in the whole network. We find that HCT increases minimum capacity for ad hoc networks. Furthermore, the multicast capacity achieving scheme is provided to justify the derived asymptotic upper bound for the minimum capacity. Our work can generalize various results obtained under nonheterogeneous networks in previous literature.

Since wireless channel is vulnerable to eavesdroppers, the secrecy during message delivery is a major concern in many applications such as commercial, governmental, and military networks. This paper investigates information-theoretic secrecy in large-scale networks and studies how capacity is affected by the secrecy constraint where the locations and channel state information (CSI) of eavesdroppers are both unknown. We consider two scenarios: 1) noncolluding case where eavesdroppers can only decode messages individually; and 2) colluding case where eavesdroppers can collude to decode a message. For the noncolluding case, we show that the network secrecy capacity is not affected in order-sense by the presence of eavesdroppers. For the colluding case, the per-node secrecy capacity of Θ([1/(√n)]) can be achieved when the eavesdropper density ψe(n) is O(n-β), for any constant β > 0 and decreases monotonously as the density of eavesdroppers increases. The upper bounds on network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ψe(n)=O(n-β) or ψe(n)=Ω(log[(α-2)/(α)]n), where α is the path-loss gain. We show that there is a clear tradeoff between the security constraints and the achievable capacity. Furthermore, we also investigate the impact of secrecy constraint on the capacity of dense network, the impact of active attacks and other traffic patterns, as well as mobility models in the context.

We study the delay performance in large-scale wireless multihop networks with unreliable links from percolation perspective. Previous works have showed that the end-to-end delay scales linearly with the source-to-destination distance, and thus the delay performance can be characterized by the delay-distance ratio γ. However, the range of γ, which may be the most important parameter for delay, remains unknown. We expect that γ may depend heavily on the node density λ of a wireless multihop network. In this paper, we investigate the fundamental relationship between γ and λ. Obtaining the exact value of γ(λ) is extremely hard, mainly because of the dynamically changing network topologies caused by the link unreliability. Instead, we provide both upper bound and lower bound to the delay-distance ratio γ(λ). Simulations are conducted to verify our theoretical analysis.

The problem of function computation in large scale heterogeneous wireless sensor networks (WSNs) is studied. Suppose n sensors are placed in a disk network area with radius nα, where α is a positive constant. The sensors are located heterogeneously around the sink node, i.e, the density of sensors decreases as the distance from the sink node increases. At one instant, each sensor is assigned an input bit. The target of the sink is to compute a function f of the input bits, where f is either a symmetric or the identity function. Energy-efficient algorithms based on inhomogeneous tessellation of the network are designed and the corresponding optimal energy consumption scaling laws are derived. We show that the proposed algorithms are indeed optimal (except for some polylogarithmic terms) by deriving matching lower bounds on the energy consumption required to compute f. At last, based on the results obtained in this paper as well as those obtained by previous works, some discussions and comparisons are presented. We observe that 1) the heterogeneity extent has a great impact on the computation of both symmetric function and identity function, and 2) the energy usage of computing symmetric function can be significantly smaller than that of computing identity function under certain parameter condition, i.e, performing in-network computation helps save energy.

This paper characterizes an evolving network with growing number of nodes, which are associated with each other through social relations but employ transmission via wireless communications. The network exhibits social relations between nodes by attaching a new arriving node to a sample node already existing as well as some nodes the sample directly links to. We study capacity in this evolving network in terms of both geographic distribution of nodes and traffic patterns. Our results show that in heterogeneous geographic distribution where nodes having strong social relations tend to locate more closer, the corresponding capacity is significantly impacted by both social relations and network evolution. In particular, with appropriate control on the initial number of nodes as well as links between them, it is even possible to achieve almost constant per-node capacity except for a poly-logarithmic factor. For homogeneous geographic topology where nodes' positions exhibit uniform distribution, social relations among nodes is useless for improving capacity, which is mainly affected by network evolution and therefore degrades sharply with time. To our best knowledge, this is the first work studying capacity from the perspective of social evolving network.

We study the multicast capacity under a network model featuring both node's mobility and infrastructure support. Combinations between mobility and infrastructure, as well as multicast transmission and infrastructure, have already showed effective ways to increase multicast capacity. In this work, we jointly consider the impact of the above three factors on network capacity. We assume that$m$static base stations and$n$mobile users are placed in an ad hoc network. A general mobility model is adopted, such that each user moves within a bounded distance from its home-point with an arbitrary pattern. In addition, each mobile node serves as a source of multicast transmission, which results in a total number of$n$multicast transmissions. We focus on the situations in which base stations actually benefit the capacity improvement, and find that multicast capacity in a mobile hybrid network falls into several regimes. For each regime, reachable upper and lower bounds are derived. Our work contains theoretical analysis of multicast capacity in hybrid networks and provides guidelines for the design of real hybrid systems combing cellular and ad hoc networks.

In this paper, we develop a truthful and efficient combinatorial auction scheme under a novel spectrum allocation model that can achieve a worst-case approximation ratio \sqrt{m} in social welfare. We propose to tackle the dynamic spectrum access problem in cognitive radio (CR) networks with time-frequency flexibility requirements. We model the spectrum opportunity in a time-frequency division manner and the spectrum allocation as a combinatorial auction. Then we design an auction mechanism to reach the upper bound in polynomial time and propose a combined approach to improve the bound in the cost of increasing computational complexity. A truthful payment that gives incentive to the SUs for revealing the truthful valuation of the desirable bundle of slots is presented. In order to reduce the complexity, we simplify the general model to a modified model that only allows frequency flexibility, and then present a truthful, optimal and computationally efficient auction mechanism. Extensive simulation results of the social welfare and spectrum ratio show that the performance of the combined approximation algorithm is better than the sorting based greedy algorithm.

In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m=nb(0v) (0 <; v ≤ 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes' communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes' topologies for any given obstacles' distributions. We further analyze its performance for regularly distributed obstacles, which can be taken to estimate the lower bound of the algorithm's performance.

Recently, many dynamic spectrum allocation schemes based on economics are proposed to improve spectrum utilization in cognitive radio networks (CRNs). However, existing mechanisms do not take into account the economic efficiency and the spatial reusability simultaneously, which leaves room to further enhance the spectrum efficiency. In this paper, we introduce the coalition double auction for efficient spectrum allocation in CRNs, where secondary users (SUs) are partitioned into several coalitions and the spectrum reusability can be executed within each coalition. The partition formation process is not only related to the interference condition between SUs, but also the expected economic goals. Therefore, we propose a fully-economic spatial spectrum allocation mechanism by incorporating the coalition formation approach with auction theory. With the proposed scheme, the primary operator acts as an auctioneer, who performs multiple virtual auctions to form a stable partition of SUs and conducts a final auction to decide the winning SUs. Moreover, we propose a possible operation rules for the primary operator to iteratively change the partition, and prove that the virtual auctions could converge in finite time. Comprehensive theoretical analysis and simulation results are presented to show that our scheme can satisfy the crucial economic robustness properties of double auction, and outperform existing mechanisms.

Previous works on multicast capacity mainly focus on deriving asymptotic order results in large-scale wireless networks, which can explore the general scaling laws of throughput capacity but cannot predict the exact achievable throughput. In this paper, we investigate the non-asymptotic capacity of multihop wireless networks for multicast applications wherein for each source node, k nodes are randomly selected as receivers. Since multicast routing has a dynamic nature, it is challenging for the exact performance analysis. To tackle the problem, we propose an explicit analytical model which describes multicast transmissions, considers networks of arbitrary size, takes data burst into account, and also covers the notion of time scales for transient analysis. By developing a practical multicast scheme, stochastic network calculus is employed for the exact analysis. With the analytical model, we derive lower and upper bounds on multicast capacity, which are non-asymptotic functions of the above variables, and also recover the scaling laws from an asymptotic point of view. Simulations further verify the accuracy of the analytical bounds.

Intra-cell interference management is one of the technical challenges for device-to-device (D2D) communication underlaying cellular networks. In this paper, we propose two superposition coding-based cooperative relaying schemes to exploit the transmission opportunities for the D2D users without deteriorating the performance of the cellular users. In the first scheme, the D2D transmitter (DT) is enabled to decode and regenerate the cellular signal, and transmit the cellular signal by superposing it with its own signal. In this way, the interference from the D2D pair to the cellular pair can be canceled by properly allocating time and power. To further exploit the transmission opportunity for the D2D pair, in the second scheme the cellular transmitter splits its signal into two parts and broadcasts these two parts in a superposition signal. DT relays only one part of the cellular signal. Analytic and numerical results confirm the efficiency of the proposed schemes.

This paper investigates random walk mobility models with location heterogeneity, where different locations may have different neighboring regions.With the assumption of totally n locations, we consider two cases, i.e., full-range locations where nodes situated have the capability to shuffle throughout the network and long-range locations where nodes are allowed for moving to positions nearby within a certain range. In the former situation, with the exact expressions derived, we find location heterogeneity has a critical impact on the first hitting time of random walk, varying from Θ(n) to Θ(n3) according to different extent of heterogeneity. The result covers, as two special cases, both the classic independent and identically distributed (i.i.d) mobility and traditional random walk as we vary the number of full-range locations. In the latter one, our asymptotic results on both the first crossing time and cover time suggest that they are inversely proportional to the range of neighboring region r (∝ r−2and ∝ r−1, respectively). Furthermore, extensive simulation is conducted to verify our observations and enhance the understanding on the effect of network parameters.

In cognitive radio network, cooperation between primary users and secondary users can improve their data rate and achieve dynamic spectrum sharing. This paper proposes a novel spectrum sharing model to solve the opportunistic access problem in cooperative cognitive radio network (CCRN). In this model, primary users select sets of secondary users as their relays and allocate channel resource to secondary users according to their cooperative transmitting power. Secondary users have their own data rate requirement, and they have to determine their optimal relay power to satisfy their requirement. Primary users have to select the best relay group and maximize their throughput. We model this problem as a Stackelberg game and prove the existence and uniqueness of Nash Equilibrium. A low-complexity algorithm is proposed to realize the cooperative transmission mechanism. Simulation results show significant throughput enhancement in the primary network and more opportunities for secondary users to get access into the spectrum.

Spectrum sensing is a key approach for the realization of cognitive radio and needs to efficiently detect the presence of the licensed users to eliminate interference and find the spectrum holes for transmission. Even though the available holes have been successfully detected, how to allocate remains a challenge. In this paper, we model a scheme combining spectrum sensing and spectrum allocation to overcome these challenges. Specifically, we frame a training period and introduce Linear Discriminant Analysis (LDA) aiming at improving the accuracy of the spectrum sensing in the data fusion process. Also a channel allocation scheme is carefully designed to guarantee the fairness among secondary users (SUs) and improve the sensing performance. Besides, with this information, fusion center can balance sensing performance and spectrum utilization so as to maximize global utility. Simulations results illustrate a significant improvement in detect accuracy and the utility of fusion center and secondary users ensured by the proposed scheme.

The concept of femtocell access points underlying existing macrocell network has recently emerged as a key technology that provides better coverage and improves wireless system capacity. Among all three access control mechanism adopted by Femtocell Access Points (FAPs), Hybrid access is regarded as the most desirable because this mechanism makes it possible to allow both femto and macro end users to access femtocell network, which significantly enhances overall network performance. In this paper, we propose an incentive mechanism for the two-tier macro-femtocell network under hybrid access control, in which FAPs expect to lease licensed spectrum from the coexisting Macrocell Service Provider (MSP) to serve their end users (FUs), in return FAPs grant the MSP a fraction of Access Permission (ACP) so that macro end users (MUs) can access FAPs to increase the Quality of Service and macrocell network capacity. We introduce the concept of contract to specify the relationship between FAPs and the MSP. We study how the MSP can obtain the optimal contract by designing different ACP-spectrum combinations (i.e., the amount of spectrum sold from the MSP to FAPs and the corresponding quantity of ACP sold from FAPs to the MSP) for different types of FAPs. Numerical results show that both MSP and FAPs can benefit from this incentive mechanism in term of their utilities.

The existence of under-utilized spectrum and the congestion of certain spectrum give rise to development on cognitive radios as a promising technology to address these problems. However, the general precondition that secondary users should evacuate from the channel which primary users are willing to use, makes the cognitive ad hoc networks vulnerable and unstable since network partition may occur since the links affected by primary users may form a cut set of the network. In this paper, we address this problem through a hybrid channel assignment scheme, where channels are carefully assigned to each link to guarantee the connectivity and the capacity based on spanning trees. Since the optimal solution is NP-hard, we propose an effective approximation algorithm. Also, dynamic channel assignment is proposed to further improve the network performance.

In Cognitive Radio Networks (CRNs), Secondary Users (SUs) are provided with the flexibility of accessing Primary Users' (PUs') idle spectrum bands but the availability of spectra is dynamic due to PUs' uncertain activities of channel reclamation. In the multi-hop CRNs consisting of SUs as relays, such spectrum mobility will cause the invalidity of pre-determined routes of data flows since some of the channels pre-assigned to the routes become unavailable. In this paper, we investigate the spectrum-mobility-incurred route-switching problem in both spatial and frequency domains for CRNs, where the spatial switching determines which relays and links should be re-selected and the frequency switching decides which channels ought to be re-assigned to the spatial routes. We further formulate the route-switching problem as the Route-Switching Game which is shown to be a potential game and has a pure Nash Equilibrium (NE). Accordingly, an efficient algorithm for finding the NE is proposed. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved.

Previous works usually simplify the network area as a disk, a square or a torus without obstacles. However, geometry in practical environment is much more intricate. Rectilinear communication between nodes is often blocked by external surroundings, such as buildings and mountains. Complicated shapes of the obstacles may cause the computation intractable. In this paper, we propose a characteristic function of connectivity to capture the geometric features of an ad-hoc network. The function can be expressed as power series, of which the orders and coefficients is based on the characteristics of the network. We formulate the shapes with fundamental factors and investigate their algebraic impact on connectivity. The critical transmission range is also calculated to mitigate the influence of obstacles.

Recently, machine-to-machine (M2M) communication becomes an attractive topic due to the rapid evolution of wireless communication systems and the potential market size of Internet of Things. In this paper, we investigate a M2M network with typical M2M features. Three key parameters, throughput capacity, delay and energy consumption, are analyzed to evaluate the performance of the M2M network under multi-hop and single-hop manner. By scrutinizing these parameters, we find that as r grows from √logn over πn to 1, delay increases progressively from order √nlogn to order n. Meanwhile, throughput keeps the same at order W/n. And there exists an optimal transmission range to minimize average energy consumption. Our results state that multi-hop manner is effective to decrease the delay and energy consumption of M2M network, without benefit on the throughput. To answer the question “to hop or not to hop in massive machine-to-machine communications”, we provide guidelines based on different optimal transmission ranges for the M2M network with different M2M features respectively.

Cognitive radio is a promising paradigm to achieve efficient utilization of spectrum resource by allowing the unlicensed users to access the licensed spectrum. Designing mechanism with proper economic incentives is essential for the success of dynamic spectrum sharing. In this paper, we study both the long-term market (i.e. contract-theoretic model) and short-term market (i.e. Stackelberg game model) between a single primary spectrum owner (PO) and multiple unlicensed secondary users (SUs) in a Market-driven secondary spectrum trading. In long-term market, we design optimal contracts, which are offered by PO. Then SUs choose whether to accept the contract based on both their demand and their types. We can show these optimal contracts maximize both PO and SUs profit. After long-term market, secondary spectrum trading enters into short-term market, where SUs can buy some amount of licensed spectrum at each time slot. We model and analyze the interactions between PO and SUs as a Stackelberg game. Finally, our simulation result demonstrates that this integrated design mechanism is effective to improve spectrum utilization and address profit maximization problem in both PO and SUs' side.

The problem of jointly estimating clock skew and offset for wireless sensor networks (WSNs) in a pairwise broadcast synchronization (PBS) protocol is considered. The random part of the delay is supposed to be an exponential random variable. We consider two estimators, i.e., joint maximum-likelihood estimator (JMLE) and generalized ML-like estimator (GMLLE) proposed by Leng and Wu . For both estimators, the corresponding algorithms are explicitly derived and presented. For the GMLLE, the corresponding performance bound based on the reduced set of observations is derived and the optimal value of a user-defined parameter is identified accordingly. At last, analytical results are corroborated by numerical experiments. We observe that: (i) JMLE usually outperforms GMLLE at the cost of larger computational complexity; (ii) JMLE, while achieving the same estimation accuracy as that of the LP method presented in , enjoys significantly lower computational complexity than that of the latter.

In this paper, we investigate the connectivity for large-scale clustered wireless sensor and ad hoc networks. We study the effect of mobility on the critical transmission range for asymptotic connectivity ink-hop clustered networks and compare to existing results on nonclustered stationary networks. By introducingk-hop clustering, any packet from a cluster member can reach a cluster head withinkhops, and thus the transmission delay is bounded as Θ(1) for any finitek. We first characterize the critical transmission range for connectivity in mobilek-hop clustered networks where all nodes move under either the random walk mobility model with nontrivial velocity or the i.i.d. mobility model. By the term nontrivial velocity, we mean that the velocity of a nodevis ω(r(n)), wherer(n) is the transmission range of the node. We then compare with the critical transmission range for stationaryk-hop clustered networks. In addition, the critical number of neighbors is studied in a parallel manner for both stationary and mobile networks. We also study the transmission power versus delay tradeoff and the average energy consumption per flow among different types of networks. We show that random walk mobility with nontrivial velocities increases connectivity ink-hop clustered networks, and thus significantly decreases the energy consumption and improves the power-delay tradeoff. The decrease of energy consumption per flow is shown to be Θ([(logn)/(nd)]) in clustered networks. These results provide insights on network design and fundamental guidelines on building a large-scale wireless network.

This paper addresses the issue of multicast scaling performance in multichannel multiradio (MC-MR) networks. Under the assumption of both limited bandwidth and node tunability, a total fixed bandwidth $(W)$ is equally split into $(c)$ channels with $(0<m\le c)$ interfaces equipped on each node for channel switching. The network contains totally $(n)$ nodes, each serving as a source with $(k)$ randomly and uniformly selected destinations. We try to give a comprehensive picture of multicast scalings by investigating both the static and mobile networks, with the metrics being capacity and delay. Previous literature has indicated that unicast capacity is solely determined by the ratio of channels to interfaces $(c/m)$ in MC-MR networks. However, in multicast our problem is made more complicated by the interplay among $(k)$, $(c/m)$ and node mobility (if considered in mobile scenario). We characterize their impact on multicast scaling and obtain three remarkable findings from our results. First, we find capacity loss exists in static networks even if the ratio $(c/m=O(\log n))$ (We use the following notation throughout our paper: $(f(n)=O(g(n))\Leftrightarrow \limsup _{n\rightarrow \infty }{f(n)\over g(n)} <\infty)$, $(f(n)=\Omega (g(n))\Leftrightarrow \liminf _{n\rightarrow \infty }{f(n)\over g(n)} <\infty)$, $(f(n)=\Theta (g(n))\Leftrightarrow f(n)=O(g(n)))$ and $(g(n)=O(f(n)))$, $(f(n)=\widetilde{\Theta }(\cdot ))$: The corresponding order $(\Theta (\cdot ))$ which contains a logarithmic order.) when $(k)$ is close to $(\Theta (n))$. This differs from unicast that is free of capacity loss as long as $(c/m=O(\log n))$. Second, mobility is manifested to improve multicast capacity in MC-MR networks, where two major capacity bottlenecks, i.e., connectivity and interference constraints, in static networks can be effectively broken. Third, a largely reduced delay is possible by simply seeking for multichannel reuse in 2-hop algorithm without redundancy. This even outperforms the delay scaling in single channel framework , where a delay smaller than $(\Theta (\sqrt{n\log k}))$ is not achievable even with more than $(\Theta (\sqrt{n\log k}))$ relay nodes involved in 2-hop mode. As a high-level summary of our results, our work discloses analytically where the performance improvement and degradation exhibit in MC-MR networks, meanwhile unifying the previous bounds on unicast (setting $(k=1)$) in .

We study the fundamental lower bound for node buffer size in intermittently connected wireless networks. The intermittent connectivity is caused by the possibility of node inactivity due to some external constraints. We find even with infinite channel capacity and node processing speed, buffer occupation in each node does not approach zero in a static random network where each node keeps a constant message generation rate. Given the condition that each node has the same probability p of being inactive during each time slot, there exists a critical value pc(λ) for this probability from a percolation-based perspective. When pc(λ), the network is in the supercritical case, and there is an achievable lower bound (In our paper, “achievable” means that node buffer size in networks can achieve the same order as the lower bound by applying some transmission scheme) for the occupied buffer size of each node, which is asymptotically independent of the size of the network. If p > pc(λ), the network is in the subcritical case, and there is a tight lower bound Θ(√n) for buffer occupation, where n is the number of nodes in the network.

Compressive sensing (CS) provides a new paradigm for efficient data gathering in wireless sensor networks (WSNs). In this paper, with the assumption that sensor data is sparse we apply the theory of CS to data gathering for a WSN where n nodes are randomly deployed. We investigate the fundamental limitation of data gathering with CS for both single-sink and multi-sink random networks under protocol interference model, in terms of capacity and delay. For the single-sink case, we present a simple scheme for data gathering with CS and derive the bounds of the data gathering capacity. We show that the proposed scheme can achieve the capacity Θ(\frac{nW}{M}) and the delay Θ(M\sqrtfrac{nlog n}), where W is the data rate on each link and M is the number of random projections required for reconstructing a snapshot. The results show that the proposed scheme can achieve a capacity gain of Θ (\frac{n}{M}) over the baseline transmission scheme and the delay can also be reduced by a factor of Θ(\fracsqrt{n\log n}{M}). For the multi-sink case, we consider the scenario where n_d sinks are present in the network and each sink collects one random projection from n_s randomly selected source nodes. We construct a simple architecture for multi-session data gathering with CS. We show that the per-session capacity of data gathering with CS is Θ(\frac{n\sqrt{n}W}{M n_d \sqrt{n_s \log n}}) and the per-session delay is Θ(M\sqrtfrac{{n}{log n}}). Finally, we validate our theoretical results for the scaling laws of the capacity in both single-sink and multi-sink networks through simulations.

While the spectrum resource of modern society is more and more insufficient, Cognitive Radio, which allows the Secondary Users (unlicensed users, SU) to access the licensed spectrum, is a promising solution to make the utilization of spectrum resource more efficient. Among many different paradigms of cognitive radio, market-driven spectrum trading has been proved to be an efficient way to deal with Cognitive Radio problems. In this paper, we consider the problem of spectrum trading with single primary user (PU) who has multiple spectra selling his idle spectra to multiple SUs in multiple types. Since there is only one PU, so it is a monopoly market, in which the PU sets the prices, powers and time for the spectrum he sells, just as a monopolist. SUs as customers choose the spectrum with exact price, power and time to buy. We model it as a two-dimensional power-time-price contract which is much different from the usual contract because the time could either be a strategy that an SU could decide to choose itself or a type which is not decided by SUs. We first discuss the situation in which the time is set as the strategy and we will prove that it can derive a feasible contract with some conditions. Then we will discuss the second situation in which the time is set as a type. In this situation, because the SU has two kinds of types, so it's difficult to make it become a feasible contract, however we will provide a solution to deal with this problem.

In this paper, we consider a general scenario where tphe wireless network is modeled as a rectangle with side lengths √n and n1/2−β, where 0 ≤ β ≤ 1/2 is a variance independent of n. n source-destination pairs are randomly located in the network, with their communication subject to the short-distance SNR, the long-distance SNR and the path loss. Based on these conditions, we identify the scaling laws of capacity for the network. The upper bound of the capacity is derived for the network, with the adoption of Multiple Input Multiple Output (MIMO) technology. Furthermore, we propose three different schemes, i.e., multihop, MIMO and hybrid schemes to achieve the upper bound. The capacity performance exhibits distinctive intriguing results as the side length of the network varies. Moreover, our results capture the impact of network shape on capacity and can unify the previous capacity results obtained in square networks.

In cognitive radio networks (CRNs), Secondary Users (SUs) are provided opportunities to access Primary Users' (PUs') idle spectrums but the availability of spectrums is dynamic due to PUs' uncertain activities of channel reclamation. In this paper, we investigate such spectrum mobility by proposing Singleton Bayesian Spectrum Mobility Games based on the Singleton Congestion Games, where each SU distributively reselects one switch-to (and available) channel which can bring it the maximum SINR when the spectrum environment varies, accounting for other SUs' switching strategies at the same time. Unlike previous game-theoretic schemes for handling the spectrum mobility that assume SUs' complete knowledge of the CRN, we present our scheme in two information scenarios. We first demonstrate the proposed game in the complete-information scenario and prove the existence of pure Nash equilibriums. Then the game is extended to the incomplete-information scenario with the existence of Bayesian equilibriums. Besides, the other major contribution of this paper is that we provide a polynomial-time algorithm for finding the socially optimal equilibrium among all possible equilibriums, which can optimize the (expected) overall performance of the entire CRN in terms of SUs' average SINR.

Smart Grid integrates digital processing, sensor technology, automatic control and communication to the traditional power grid to achieve more efficient electricity distribution and management. Applying wireless sensor networks (WSNs) to Smart Grid can greatly facilitate the real-time information exchange within the power management system, and enable fast adaptation of the system to environmental changes. However, there are many challenges that need to be addressed for applying WSNs to the Smart Grid. One critical issue is how to receive data at the controller's node in a timely manner considering the typically time sensitive environment in Smart Grid and the limited battery power supply in WSNs. Based on data classification, this paper proposes a data transmission strategy in WSNs. After appropriate processing while collecting those large and complex data during aggregation, they are classified into different priority levels according to their various features. This classification process ensures the most important data which occupy a quite small percent of the total amount. The proposed cognitive transmission measure can guarantee a minimum delay for the most key data under the constraints of the electric-power-system environment and battery power supply. We offer simulation results to show the performance of the proposed cognitive transmission scheme.

In cognitive radio networks, secondary users (SUs) are considered as selfish spectrum users, thus how to maximize the spectrum efficiency by these selfish users becomes an endless research topic. Recent studies mostly focus on the competition analysis between SUs using economic mechanism, such as game theory and auction, but the spectrum owner can hardly increase the spectrum efficiency directly when SUs apply the distributed manner. In this paper, we consider the slotted uplink scenario where several SUs have data transmitted to secondary access point (AP) under distributed random access manner. The AP decides how to divide its spectrum which maximizes the whole throughput, then SUs select the channels which would maximize their own profit. Our results show that SUs' channel selection process leads to a Nash Equilibrium, and the AP derives the proper number of channels based on the properties of NE. Moreover, we derive a rule for AP to decide which SUs should access the spectrum and lead to the increment in the whole throughput.

Cognitive radio networks (CRN) is a promising technology for the efficient utilization of spectrum resource. However, how to dynamically allocate the spectrum combining with the characteristics of CRN is a crucial challenge for the mechanism design. In this paper, from the perspective of frequency-time characteristics of the spectrum opportunity in CRN and the secondary users' flexible requirements, we model the dynamic spectrum allocation problem as a knapsack problem and prove that maximizing the social welfare is NP-hard. Therefore, a spectrum auction mechanism is developed to approximate the optimal social welfare, and we prove its approximate ratio. Further, to guarantee the truthfulness, we devise a corresponding payment scheme. In simulation results, we show that no matter how many SUs are in the CRN, our scheme can approximate the maximal social welfare perfectly, and the spectrum utilization can be improved to over 96.5% or even larger.

The fc-connectivity of cognitive radio networks is discussed in this paper. By combining asymptotic k-connectivity and percolation, we define that the cognitive radio networks are k-connected if there exists an infinite k-connected component in the secondary network. Utilizing continuum percolation theory, we prove that the secondary network is k-disconnected if secondary users' density λ2, where l → ∞ is the side length of a square-shaped network, r is the transmission range of the secondary network, and θ = Ω(1). And the network is k-connected when λs≥ log l + (k − 1 − + ξ) log, log l/πr2, where ξ = Ω(1). Finally, we provide the necessary condition and sufficient condition of k-connectivity on primary user density λp.

In this paper, we propose a novel multi-lane model in Delay Tolerant Network (DTN). Different from traditional ad hoc network, DTN allows nodes to forward information in a store-and-carry manner so as to deal with the absence of end-to-end connectivity. Vehicles are classified into different categories according to their everyday routine, so called multi-lane. The main purpose is to decide a reliable next-hop forwarding procedure based on incomplete surrounding information. Furthermore, considering the searching interval during which nodes carry the information, we aim to explore the VANETs system performance under different network constraints like node density, velocity.

In Cognitive Radio (CR) networks, Primary Users (PUs) can share their idle spectrums with Secondary Users (SUs) under certain mechanisms. Centralized schemes and market-driven mechanisms are two major considerations in solving the spectrum sharing problems in the multiple-PU scenario. Centralized schemes can achieve the social optimal spectrum allocation among multiple PUs and multiple SUs but require a central control entity, which is impractical in the CR environment due to its distributed nature. Market-driven mechanisms can be implemented in a distributed manner but are hard to obtain the social optimal spectrum utilization in the multiple-PU scenario. Furthermore, many market-driven mechanisms are not economic-robust (Incentive Compatible, Individual Rational, etc). In this paper, we propose a distributed-centralized spectrum sharing scheme based on contracts for the multiple-PU scenario, which introduces a Random Leader who is elected randomly among SUs or PUs. The distributed aspect of our scheme lies in that our scheme requires no central control entities, which can be independently implemented within a distributed spectrum market. The centralized aspect is that the leader draws up and assigns the social optimal spectrum allocation contracts as well as the payment contracts for all PUs and SUs in a centralized manner. The former contracts maximize the spectrum utilization of the whole network, and the latter contracts help attain the economic robustness of our scheme. Under the leadership of the Random Leader, those non-cooperative SUs and PUs behave in a cooperative manner, which mitigates the complexity and time overhead needed for information exchange.

Energy efficiency is the core issue in wireless sensor network's scheduling algorithm design, which calls up wide attention from researchers. However, few of the previous works notice the constraints on sensors caused by limited buffer size. It challenges the system's meeting deadlines performance. To alleviate this concern, we propose a scheduling policy: the least energy and free storage remaining first, which extends wireless sensor network's lifetime and provides a high real-time service's quality. To make our strategy more practical, we consider the user's non-cooperative behavior out of self-interests. It increases the system's packet lost in buffer overflow and reduces the energy efficiency. Based on a mixed strategy game model, we show that the non-cooperative game converges to an inefficient Nash Equilibrium, where the spectrum resource is significantly wasted. In order to eliminate user's selfish manner, we design a punishment scheme via a repeated game, which considers the time-variant character of network and can detect non-cooperative action precisely and rapidly.

With the increasing demand of communication, it is of great necessity to maximize the utility of vehicular network. VANETs (Vehicular Ad-hoc Networks) especially in the context of high mobility attract more attention all over the world. Pure vehicle-to-vehicle(V2V) networks may relatively have long delay and worse performance compared to vehicle-to-infrastructure(V2I) networks, while V2V networks have larger communication area. Consequently, vehicular network integrated with 3G network is of significance. In these networks, gateways are generally used as interfaces between hybrid networks, thus gateway selection becomes the primary challenge. The most important thing considered in our work is that whenever infrastructures and 3G networks are considered, price is a core problem. The justice of caring the interests of all the vehicle nodes is going to be considered. In this paper, we consider the VANET and 3G connected model under cognitive situations, and then a price based on hierarchical strategy on the cooperative sensing and cluster head selection is proposed to ensure the maximum benefit of both the cluster heads and the cluster members.

In this paper, we study the multicast capacity of wireless ad hoc networks with infrastructure support. The network under study is termed as hybrid wireless network, where L-Maximum-Hop resource allocation strategy is adopted. There are n uniformly deployed normal wireless nodes and m regularly placed base stations dividing the network region into m cells. We show that the maximum capacity O(n1/2/k1/2(log n)1/2W1) + O(mW2) is achieved when the hop number L = Θ (n1/4/(k1/4(log n)3/4)) with the number of destinations k = O (a2/r2), where a is the side length of network region and r is transmission range of wireless terminals. This result provides a meaningful guide for the design of hybrid wireless networks. Moreover, we demonstrate that it is more efficient to adopt Infrastructure Mode than Ad Hoc Mode when k = Ω(a2/r2), because infrastructure nodes can cover the whole cell and broadcast to nodes more efficiently. In this case, maximum capacity is O (W1) + O(mW2), when L = Θ(1). Furthermore, we reveal that the per-node capacity does not vanish to zero only if the number of base stations m = Ω(n).

A brand-new concept about the coverage problem of camera sensor networks, full view coverage, has been proposed recently to judge whether an object's face is guaranteed to be captured. It is specially significant for camera networks since image shot at the frontal viewpoint considerably increases the possibility to recognize the object. In this paper, we investigate the necessary and sufficient conditions to achieve full view coverage under two random deployment schemes, uniform deployment and Poisson deployment. In uniform deployment, we define a centralized parameter -- critical sensing area (CSA) -- to evaluate the total requirements to reach symptotic full view coverage for all heterogeneous sensors in the network. In Poisson deployment, we develop the probability for a point to be full view covered. Our results reveal that under uniform deployment, whether full view coverage is achieved depends largely on the area of the sensing region, rather than its shape.

We study the multicast capacity under a network model featuring both node's mobility and infrastructure support. Combinations between mobility and infrastructure, as well as multicast transmission and infrastructure, have already been shown effective ways to increase capacity. In this work, we jointly consider the impact of the above three factors on network capacity. We assume that m static base stations and n mobile users are placed in an ad hoc network, of which the area scales with n as f2(n). A general mobility model is adopted, such that each user moves within a bounded distance from its homepoint with an arbitrary pattern. In addition, each mobile node serves as the source of a multicast transmission, which results in a total number of n multicast transmissions. We focus on the situations that base stations actually benefit the capacity, and prove that multicast capacity of mobile hybrid network falls into three regimes. For each regime, matching upper and lower bounds are derived.

In this paper, we tackle the spectrum allocation problem in cognitive radio (CR) networks with time-frequency flexibility consideration using combinatorial auction. Different from all the previous works using auction mechanisms, we model the spectrum opportunity in a time-frequency division manner. This model caters to much more flexible requirements from secondary users (SUs) and has very clear application meaning. The additional flexibility also brings theoretical and computational difficulties. We model the spectrum allocation as a combinatorial auction and show that under the time-frequency flexible model, reaching the social welfare maximal is NP hard and the upper bound of worst-case approximation ratio is √m, m is the number of time-frequency slots. Therefore, we design an auction mechanism with near-optimal winner determination algorithm, whose worst-case approximation ratio reaches the upper bound √m. Further we devise a truthful payment scheme under the approximation winner determination algorithm to guarantee that all the bids submitted by SUs reflect their true valuation of the spectrum. To further address the issue and reach optimality, we simplify the general model to that only frequency flexibility is allowed, which is still useful, and propose a truthful, optimal and computationally efficient auction mechanism under modified model. Extensive simulation results show that all the proposed algorithms generate high social welfare as well as high spectrum utilization ratio. What's more, the actual approximation ratio of near-optimal algorithm is much higher than the worst-case approximation ratio.

Market based spectrum trading has been extensively studied to realize efficient spectrum utilization in cognitive radio networks (CRNs). In this paper, we utilize the concept of insurance in spectrum trading so as to improve spectrum efficiency in CRNs. We show that by additionally purchasing a specifically designed insurance contract from a PU, an SU can improve its utility since it will be insured against the potential accident, i.e., transmission failure incurred by excessively low SINR. Therefore insurance provides SUs more incentive to purchase PUs' channels and spectrum utilization in CRNs can be improved. In this paper, the original spectrum market including multiple PUs and multiple SUs are modeled as a hybrid market consisting of a spectrum market and an insurance market. In this hybrid market PUs serve as spectrum sellers as well as insurers and SUs act as spectrum buyers as well as insureds. We further model the hybrid market game as a four-stage Bayesian game between PUs and SUs. We characterize the second-best Pareto optimal (SBPO) market allocations and players' perfect Bayesian equilibrium (PBE) strategies. Furthermore, through extensive simulation, we have demonstrated that at the PBE, high risk and low risk SUs will respectively experience improvement in their utilities for approximately 23.5% and 4.6%.

In this paper, we study the throughput-optimal control in the multi-radio multi-channel (MR-MC) wireless networks, which is particularly challenging due to the coupled link scheduling and channel/radio assignment. This paper has threefold contributions: 1) We develop a new model by transforming a network node into multiple node-radio-channel (NRC) tuples. Such modeling facilitates the development of a tuple-based back pressure algorithm, the solution of which can jointly solve the link scheduling, routing and channel/radio assignment in the MRMC network. 2) The tuple-based model enables the extensions of some well-known algorithms, e.g., greedy maximal scheduling and maximal scheduling, to MR-MC networks with guaranteed performance. We provide stability and capacity efficiency ratio analysis to the tuple-based scheduling algorithms. 3) The tuple-based framework facilitates a decomposable cross-layer formulation that enhances the delay performance of throughput-optimal control by integrating the link-layer scheduling with the network-layer path selection, where both hop-count and queuing delay are considered. Simulation results are presented to demonstrate the capacity region and delay performance of the proposed methodology, with comparison to the existing approach [3].

We study the capacity and delay scaling laws for cognitive radio network (CRN) with static primary users and heterogeneous mobile secondary users coexisting in the unit planar area. The primary network consists of n randomly and uniformly distributed static primary users (PUs) with higher priority to access the spectrum. The secondary network consists of m = (h + 1)n1+∈heterogeneous mobile secondary users (SUs) which should access the spectrum opportunistically, here h = O(log n) and ∈ > 0. Each secondary user moves within a circular area centered at its initial position with a restricted speed. The moving area of each mobile SU is n−α, where a is a random variable which follows the discrete uniform distribution with h + 1 different values, ranging from 0 to α0(α0> 0). α0and h together determine the mobility heterogeneity of secondary users. By allowing the secondary users to relay the packets for primary users, we have proposed a joint routing and scheduling scheme to fully utilize the mobility heterogeneity of secondary users. We show that the primary network and secondary network can achieve optimal capacity and delay scalings if we increase the mobility heterogeneity of secondary users, i.e., the value of h and α0, until h = Θ(log n) and α0≥ 1 + ∈. In this optimal condition, both the primary network and part of the secondary network can achieve almost constant capacity and delay scalings except for poly-logarithmic factor.

This paper investigates the capacity, delay and energy consumption for MotionCast (a multicast mechanism for MANETs) with general Markovian mobility. We consider MotionCast in an extended cell partitioned network under a Markovian node mobility model and exactly compute the pernode throughput capacity. A Two hop relay algorithm is proposed to guarantee such capacity, which also achieves a better delay-capacity tradeoff, i.e., Θ(N log k). Considering that redundancy can significantly improve network delay, we present a Two hop relay algorithm with redundancy and study the general influence of redundancy on the capacity and delay of MotionCast network. Moreover, we use the minimum energy function to characterize the energy consumption for the MotionCast network. An accurate piecewise minimum energy function to keep network stable is derived. Furthermore, a simple Minimum energy algorithm is designed, which reduces actual energy consumption arbitrarily close to the minimum energy function at the cost of increasing delay. Our result shows that the proposed algorithm achieves the optimal energy-delay tradeoff.

In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m = nb(0 < b < 1) helping nodes, and evaluate the impact of topology on its throughput capacity. For networks without obstacles, we find that uniformly distributed sensor nodes and regularly distributed helping nodes have some advantages in improving the throughput capacity. We also explore properties of networks composed of some isomorphic sub-networks. For networks with obstacles, we assume there are M = Θ(nv) (0 < v ≤ 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes' communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes' topologies for any given obstacles' distributions.

Since wireless channel is vulnerable to eavesdroppers, the secrecy during message delivery is a major concern in many applications such as commercial, governmental and military networks. This paper investigates information-theoretic secrecy in large-scale networks and studies how capacity is affected by the secrecy constraint where the locations and channel state information (CSI) of eavesdroppers are both unknown. We consider two scenarios: 1) non-colluding case where eavesdroppers can only decode messages individually; and 2) colluding case where eavesdroppers can collude to decode a message. For the non-colluding case, we show that the network secrecy capacity is not affected in order-sense by the presence of eavesdroppers. For the colluding case, the per-node secrecy capacity of Θ(1/√n) can be achieved when the eavesdropper density ψe(n) is O(n-β), for any constant β >; 0 and decreases monotonously as the density of eavesdroppers increases. The upper bounds on network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ψe(n) = O(n-β) or ψe(n) = Ω(log α-2/α n), where α is the path loss gain. We show that there is a clear tradeoff between the security constraints and the achievable capacity.

In this paper, we study data gathering with compressive sensing from the perspective of in-network computation in random networks, in which n nodes are uniformly and independently deployed in a unit square area. We formulate the problem of data gathering to compute multiround random linear function. We study the performance of in-network computation with compressive sensing in terms of energy consumption and latency in centralized and distributed fashions. For the centralized approach, we propose a tree-based protocol for computing multiround random linear function. The complexity of computation shows that the proposed protocol can save energy and reduce latency by a factor of Θ(√n= log n) for data gathering comparing with the traditional approach, respectively. For the distributed approach, we propose a gossip-based approach and study the performance of energy and latency through theoretical analysis. We show that our approach needs fewer transmissions than the scheme using randomized gossip.

Rate adaptation (RA) has been used to achieve high goodput. In this work, we explore to use RA for energy efficiency in 802.11n NICs. We show that current MIMO RA algorithms are not energy efficient for NICs despite ensuring high throughput. The fundamental problem is that, the high-throughput setting is not equivalent to the energy-efficient one. Marginal throughput gain may be realized at high energy cost. We propose EERA, an energy-based RA solution that trades off goodput for energy savings at NICs. Our experiments have confirmed its energy savings at NICs while keeping the cost at the device level and across clients acceptable.

There has been recent interest within the networking research area to understand the transmission delay in Cognitive Radio (CR) Networks with overlapping primary network and secondary network. In this paper, we investigate the scaling behavior of transmission delay in large scale ad hoc CR networks. We take different scenarios of CR networks into consideration and thus obtain a wind range of results. We first neglect propagation delay and study the ratio of transmission delay to distance, denoted by γ (λsAp and figure out its exact value in supercritical secondary network. In case of subcritical secondary network, we introduce a multi-cluster hop transmission process to get the lower bound of γ (λsAp. Then we take propagation delay into consideration to obtain further results. Finally, we use simulation results to verify our theoretical analysis. The results present the scaling behavior of transmission delay in CR networks and provide the design guidelines for large scale wireless networks.

Cognitive radio is promising in improving spectrum efficiency by enabling unlicensed users to access to the licensed spectrum. Spectrum auction is perceived as a potential way to realize it. Primary users (PUs) act as sellers selling unused spectrum bands and secondary users (SUs) act as buyers who intend to get spectrum bands from PUs. In situations where multiple PUs and SUs exist, double auction is a paradigm to assign spectrum. Efficiency and economic robustness are considered two essential properties in the model. Previous work often employ bid-independent uniform pricing to maintain economic robust at the substantial cost of efficiency. In this paper, we investigate the tradeoff between efficiency and robustness. We propose DIPA, a DIscriminatory Pricing double Auction for spectrum, in which bidders are charged of varying prices for the same item they purchase. We demonstrate that DIPA is robust and improves efficiency largely over the previous design.

A cognitive network refers to the one where two overlaid structures, called primary and secondary networks coexist. The primary network consists of primary nodes who are licensed spectrum users while the secondary network comprises unauthorized users that have to access the licensed spectrum opportunistically. In this paper, we study the percolation degree of the secondary network to achieve k-percolation in large scale cognitive radio networks. The percolation degree is defined as the number of nearest neighbors for each secondary user when there are at least k vertex-disjoint paths existing between any two secondary relays in the percolated cluster. The percolated cluster is formed when there are an infinite number of mutually connected secondary users spanning the whole network. Each user in the cluster is possibly connected to several neighbors, inducing more communication links between any two of them. Since nodes located near the boundary have fewer neighbors, the boundary effect becomes a bottleneck in determining the percolation degree. For cognitive networks, when the primary node density becomes considerably large, the boundary effect spreads inside the network. The transmission area of most secondary users who are located near the primary nodes decreases due to the restriction of the primary network. Therefore, to ensure k-connectivity in the percolated cluster, each secondary user must be connected to more neighbors, and the percolation degree of the secondary network yields a function of the primary node density. We specify the relationship into three regimes regarding the topology variation of the cognitive network. A closed-form expression of the percolation degree under different primary node densities is presented. The expression characterizes the connectivity strength in the secondary percolated cluster, therefore providing analytical insight on fault tolerance improvement in cognitive networks.

In Cognitive Radio Networks (CRNs), Primary Users (PUs) can share their idle spectra with Secondary Users (SUs) under certain mechanisms. In this paper, we propose a distributed-centralized and incentive-aware spectrum sharing scheme for the multiple-PU scenario, which introduces a Random Leader who is elected randomly from SUs or PUs. The distributed aspect of our scheme lies in that it requires no central control entities, which can be independently implemented within a distributed spectrum market. The centralized aspect is that the leader draws up and assigns the socially optimal contracts for all PUs and SUs in a centralized manner, which maximizes the throughput of the whole network and attains the economic robustness (including Incentive Compatibility and Individual Rationality). Analysis shows that the proposed scheme takes in the advantages of both centralized and distributed schemes but overcomes their weaknesses. We use the proposed scheme to study two sharing scenarios: the short-term and the long-term spectrum sharing. The Short-Term Sharing (STS) focuses on distributing PUs' idle spectra within one time slot while the Long-Term Sharing (LTS) considers multiple slots, where the spectrum mobility must be investigated. As an integrated design of both STS and LTS, our scheme not only fulfils SUs' heterogeneous spectrum requirements but also obtains the socially optimal throughput while accounting for both SUs' and PUs' incentives.

Vehicular Ad Hoc Networks (VANETs) with base stations are called hybrid VANET, where base stations are deployed to improve the throughput capacity. In this paper, we study the multicast throughput capacity for hybrid wireless VANET with a directional antenna on each vehicle and the end-to-end delay is constrained. In the hybrid VANET, there are n mobile vehicles (or nodes) distributed in a unit area with m strategically deployed base stations connected using high-bandwidth wire links. There are n_s multicast sessions and each multicast session has one source which transmits identical data to its associated p destinations. We investigate the multicast throughput capacity for two mobility models with two mobility scales, respectively, while each vehicular node is equipped with a directional antenna and with a tolerant delay D. That is, a source node transmits to its p destinations only with the help of normal nodes within D consecutive time slots. Otherwise, the transmission will be performed with in the infrastructure mode, i.e., with the help of base stations. We demonstrate that the one dimensional i.i.d. slow mobility pattern catch the main feature of VANETs. And we find that the multicast throughput capacity of the hybrid wireless VANET greatly depends on the delay constraint D, the number of base stations m, and the beamwidth of directional antenna θ. In the order of magnitude, we obtain the closed form of the multicast throughput capacity of the hybrid directional VANET, where the impact of D, m and θ on the multicast throughput capacity is analyzed. Moreover, we derive the lower bound of the muticast throughput using a similar raptor coding approach.