Federated unlearning (FU) aims to remove a participant’s data contributions from a trained federated learning (FL) model, ensuring privacy and regulatory compliance. Traditional FU methods often depend on auxiliary storage on either the client or server side or require direct access to the data targeted for removal—a dependency that may not be feasible if the data is no longer available. To overcome these limitations, we propose NoT, a novel and efficient FU algorithm based on weight negation (multiplying by -1), which circumvents the need for additional storage and access to the target data. We argue that effective and efficient unlearning can be achieved by perturbing model parameters away from the set of optimal parameters, yet being well-positioned for quick re-optimization. This technique, though seemingly contradictory, is theoretically grounded: we prove that the weight negation perturbation effectively disrupts inter-layer co-adaptation, inducing unlearning while preserving an approximate optimality property, thereby enabling rapid recovery. Experimental results across three datasets and three model architectures demonstrate that NoT significantly outperforms existing baselines in unlearning efficacy as well as in communication and computational efficiency.

In this paper, we propose a joint communication and sensing (JCAS) waveform design method for pulse amplitude modulation (PAM) signal based on visible light. Common communication and sensing performance metrics, including symbol error rate, achievable transmission rate, miss detection probability and Kullback-Leibler (KL) divergence are adopted. We provide an optimization criterion with respect to parameter of the integrated waveform under peak power constraint to balance the communication performance and the sensing performance. We conduct the JCAS experiments for the objects under short distance of 1 meter and long distance of 7 meters. Both numerical and experimental results show that, for PAM signals, there exists a fundamental tradeoff between the communication performance and the sensing performance. Given the same sampling rate and the same number of samples for target detection, high-order PAM signals provide better sensing performance due to the lower tail probability. Moreover, with longer distances and stronger diffuse reflections, the detection duration needs to be extended to obtain better sensing performance.

This paper explores the impact of signal-dependent noise (SDN) on the band-limited Nyquist pulse design in visible light communication (VLC) systems. We provide a bandlimited signal transmission model with SDN, and also extend the transmission scheme with time-varying bias in the existing work. We analyze the noise features of the band-limited VLC systems with SDN, and show that the SDN strength after receive filtering is determined by both transmitter and receiver pulses. For the inter-symbol interference (ISI)-free transmission with sampling receiver and time-varying bias, we provide a bandlimited Nyquist pulse design method to maximize the low bound of output signal-to-noise ratio (SNR) after receiver filtering, and the designed pulses are unrelated to channel condition and SDN strength. For the ISI-free transmission with matched filter, we prove that there is no theoretical optimal band-limited Nyquist pulse, and provide the Nyquist pulse design methods for the two transmission schemes without bias and with time-varying bias, respectively. Numerical results demonstrate that the designed pulses outperform the existing pulses for different excess bandwidth factors and modulation formats in VLC systems with SDN.

Since the passband of an optical filter will shift as the optical incidence angle changes, random receiver orientation will lead to variation of normalized channel matrix in multi-color visible light communication (VLC) systems. This work investigates the constellation design for color shift keying (CSK) system under random receiver orientation. We consider a multi-color visible light sensing and communication system. Taking the chromaticity and color rendering index constraints into account, we propose two CSK constellation design methods, one to generate constellations for each optical incidence angle and the other to generate constellations with the optical incidence angle regarded as a random variable. Then, taking the sensing information as a prior knowledge, we construct the CSK constellation maps to reduce the real-time computational complexity, and propose a sensing-aided communication mechanism. Moreover, to obtain the sensing information, we propose a 5D user equipment (UE) location and pose estimation method for the considered systems. Simulation results demonstrate the performance gain of the designed CSK constellations, the accuracy of the proposed UE location and pose estimation method, and the potential with CSK constellation map.

Avalanche photodiodes (APD) are key devices in optical communication, and its nonlinear characteristics have a significant impact on the communication performance of the system. Based on the detection principle of photodetector, we characterize the nonlinearity of avalanche photodiodes, and demonstrate the theoretical prediction results in experiments. For the APD module integrated with trans-impedance amplifer (TIA), the nonlinear AC signal response caused by amplifier saturation is observed and explained. Based on the nonlinear characteristics of the photodetector, we can reasonably set the DC operation point and ensure the signal extraction in nonlinear region.

In this work, a LOcation based RAN resource Management and Access (LOMA) map is designed for future radio access networks (RAN) to allocate radio resources in complex wireless environment, and to facilitate uplink/downlink data transmissions. Enabled by the AI and high-precise positioning techniques, the LOMA map can associate a set of radio resources and data transmission parameters (e.g, transmit power, MCS level) with a geographical location in the RAN area. Given the LOMA map, each user equipment (UE) or infrastructure associated with the RAN can directly determine the radio resources and parameters used for uplink/downlink data transmissions according to its location. An AI enabled LOMA map generation method are proposed to generate LOMA maps according to the statistical traffic and wireless environment data collected by UEs and infrastructures. A reinforcement learning (RL) based algorithm is further proposed in the LOMA map generation method to dynamically quantify the available radio resources according to the real-time data traffic and the performance of applied resource scheduling scheme. Case studies with numerical results are presented to show the benefits provided by LOMA map technique in terms of increasing resource sharing efficiency, reducing signal overheads in data transmissions, and enabling resource scheduling schemes with less computing cost.

The advances in artificial intelligence (AI) and edge computing enable edge intelligence to support pervasive intelligent Internet of Things (IoT) applications in the future wireless networks. We focus on deep neural network (DNN)-based classification tasks, and investigate how to improve the confidence level and delay performance of DNN inference via device-edge collaboration. We first develop a stochastic cumulative DNN inference scheme that aggregates multiple random DNN inference results and generates a cumulative DNN inference result with improved confidence level. Then, based on a computation-efficient DNN model deployment strategy with shared computation between a locally deployed fast DNN model and a full DNN model partitioned between the device and edge, a closed-loop adaptive device-edge collaboration scheme is developed to support cumulative DNN inference for multiple devices. We adaptively determine how to offload DNN inference computation to the edge and how to allocate transmission and edge-computing resources among multiple devices, for Quality-of-Service (QoS) satisfaction in terms of both confidence level and inference delay with resource and energy efficiency. A reinforcement learning (RL) approach is used for adaptive offloading decision, which relies on a resource allocation solution for reward calculation. Simulation results demonstrate the effectiveness of the adaptive device-edge collaboration scheme for cumulative DNN inference, in terms of confidence level improvement, delay violation minimization, network resource efficiency, and device energy efficiency.

Split learning (SL) is a collaborative learning framework, which can train an artificial intelligence (AI) model between a device and an edge server by splitting the AI model into a device-side model and a server-side model at a cut layer. The existing SL approach conducts the training process sequentially across devices, which incurs significant training latency especially when the number of devices is large. In this paper, we design a novel SL scheme to reduce the training latency, namedCluster-basedParallelSL(CPSL) which conducts model training in a “first-parallel-then-sequential” manner. Specifically, the CPSL is to partition devices into several clusters, parallelly train device-side models in each cluster and aggregate them, and then sequentially train the whole AI model across clusters, thereby parallelizing the training process and reducing training latency. Furthermore, we propose a resource management algorithm to minimize the training latency of CPSL considering device heterogeneity and network dynamics in wireless networks. This is achieved by stochastically optimizing the cut layer selection, device clustering, and radio spectrum allocation. The proposed two-timescale algorithm can jointly make the cut layer selection decision in a large timescale and device clustering and radio spectrum allocation decisions in a small timescale. Extensive simulation results on non-independent and identically distributed data demonstrate that the proposed solution can greatly reduce the training latency as compared with the existing SL benchmarks, while adapting to network dynamics.

Training a game-playing reinforcement learning agent requires multiple interactions with the environment. Ignorant random exploration may cause a waste of time and resources. It's essential to alleviate such waste. As discussed in this paper, under the settings of the off-policy actor critic algorithms, we demonstrate that the critic can bring more expected discounted rewards than or at least equal to the actor. Thus, the Q value predicted by the critic is a better signal to redistribute the action originally sampled from the policy distribution predicted by the actor. This paper introduces the novel Critic Guided Action Redistribution (CGAR) algorithm and tests it on the OpenAI MuJoCo tasks. The experimental results demonstrate that our method improves the sample efficiency and achieves state-of-the-art performance. Our code can be found at https://github.com/tairanhuang/CGAR.

Modeling visual question answering (VQA) through scene graphs can significantly improve the reasoning accuracy and interpretability. However, existing models answer poorly for complex reasoning questions with attributes or relations, which causes false attribute selection or missing relation in Figure 1(a). It is because these models cannot balance all kinds of information in scene graphs, neglecting relation and attribute information. In this paper, we introduce a novel Dual Message-passing enhanced Graph Neural Net-work (DM-GNN), which can obtain a balanced represen-tation by properly encoding multi-scale scene graph infor-mation. Specifically, we (i) transform the scene graph into two graphs with diversified focuses on objects and relations; Then we design a dual structure to encode them, which in-creases the weights from relations (ii) fuse the encoder out-put with attribute features, which increases the weights from attributes; (iii) propose a message-passing mechanism to en-hance the information transfer between objects, relations and attributes. We conduct extensive experiments on datasets in-cluding GQA, VG, motif-VG and achieve new state of the art.

Recently, visual Transformer (ViT) and its following works abandon the convolution and exploit the self-attention operation, attaining a comparable or even higher accuracy than CNN. More recently, MLP-mixer abandons both the convolution and the self-attention operation, proposing an architecture containing only MLP layers. To achieve cross-patch communications, it devises an additional token-mixing MLP besides the channel-mixing MLP. It achieves promising results when training on an extremely large-scale dataset such as JFT-300M. But it cannot achieve as outstanding performance as its CNN and ViT counterparts when training on medium-scale datasets such as ImageNet-1K. The performance drop of MLP-mixer motivates us to rethink the token-mixing MLP. We discover that token-mixing operation in MLP-mixer is a variant of depthwise convolution with a global reception field and spatial-specific configuration. In this paper, we propose a novel pure MLP architecture, spatial-shift MLP (S2-MLP). Different from MLP-mixer, our S2-MLP only contains channel-mixing MLP. We devise a spatial-shift operation for achieving the communication between patches. It has a local reception field and is spatial-agnostic. Meanwhile, it is parameter-free and efficient for computation. The proposed S2-MLP attains higher recognition accuracy than MLP-mixer when training on ImageNet1K dataset. Meanwhile, S2-MLP accomplishes as excellent performance as ViT on ImageNet-1K dataset with considerably simpler architecture and fewer FLOPs and parameters.

In this article, a two-level soft-slicing scheme is proposed for 5G-and-beyond radio access networks to support ultrareliable and low-latency communications (URLLC) and enhanced mobile broadband (eMBB) services with delay/reliability and throughput requirements, respectively. At the network level, we first determine the number of radio resources required for eMBB services and analyze the delay violation probability for URLLC services. Then, an integer nonlinear program is formulated for the network-level resource preallocation. Since the formulated problem is NP-complete, a low-complexity heuristic algorithm is proposed to obtain near-optimal solutions. Given the preallocated resources at each gNodeB (gNB), a gNB-level resource scheduling scheme is designed to enable real-time resource sharing among URLLC services considering the reliability and delay requirements. Simulation results show that the proposed soft-slicing scheme meets stringent quality-of-service requirements for both URLLC and eMBB services and achieves high resource utilization efficiency when compared with conventional hard resource slicing schemes.

Intensity modulation and direct detection (IM-DD) based optical wireless communication (OWC), requires the modulated signal to be real and non-negative. To satisfy the requirements, this paper proposes two types of mixed orthogonal frequency division multiplexing (X-OFDM) waveforms. The Hermitian symmetry (HS) characteristic of the sub-carriers in the frequency domain, guarantees the signal in the time domain to be real, which reduces the spectral efficiency to 1/2. For the odd sub-carriers in the frequency domain, the signal in the time domain after the inverse fast fourier transform (IFFT) is antisymmetric. For the even sub-carriers in the frequency domain, the signal in the time domain after the IFFT is symmetric. Based on the antisymmetric and symmetric characteristics, the two types of X-OFDM waveforms are designed to guarantee the signal in the time domain to be non-negative. With$M$sub-carriers in the frequency domain, the generated signal in the time domain has$3M/2$points, which further reduces the spectral efficiency to 1/3. The numerical simulations show that, the two types of X-OFDM waveforms greatly enhance the power efficiency considering the OWC channel with the signal-dependent noise and/or the signal-independent noise.

The wavelength division multiplexing radio over fiber (WDM-RoF) system is designed to provide broadband and high throughput services, but sensitive to the nonlinear distortion. This paper studies the nonlinear model with rate equations and multiple dimension behavior, and the corresponding digital linearization algorithms. The multi dimension parallel Hammer-stain (MD-PH) algorithm considers not only the nonlinearity of each path but also the intermodulation and interchannel crosstalk, which provides better performance than crosstalk memory polynomial (CO-MPM) algorithm. By means of VPI photonics design suite, a 4-WDM-RoF system and corresponding algorithms are verified. The simulation results demonstrate that the MD-PH algorithm outperforms the CO-MPM one in terms of the adjacent channel power ratio (ACPR) and the normalized mean square error (NMSE).

We focus on the wireless communication with several independent nodes in the bounded space. In particular, we discuss the existence and uniqueness of solutions for artificially constructing reachable intervals of wireless channel by adjusting the distribution of singular value of the multiple observation points simultaneously, under the point excitation sources in two-dimensional space. In this paper, it is theoretically proved that there is no physical exact solution for more than five observation points under part of the fixed wireless channel. In practical engineering, no amount of RIS arrays or elements can be deployed to construct a physical solution that accommodates more than five receivers simultaneously, when part of the wireless channel is given in advanced and unchangeable. Fundamental limits of wave control in smart environment is given by the number and range of independent variables of underdetermined functions.

Probabilistic shaping is widely used in optical communication to increase the data rate. Because the number of symbols is an integer, when modulating the input signals into the predefined symbol sequence, the modulated probabilistic distribution is a discrete M-type distribution. In this paper, a fast method of M-type approximation based on information divergence is proposed. Compared with traditional algorithm, the proposed fast M-type approximation can greatly reduce the computation complexity while achieving the same results. This paper also proves mathematically that the information divergence increment has boundaries for M-type approximation near the ideal distribution. Based on the bounds of information divergence increment, the M-type approximation distribution boundary related to ideal distribution can be obtained.

In the second part of this article, we develop a centralized packet transmission scheduling scheme to pair with the protocol designed in Part I and complete our medium access control (MAC) design for machine-type communications in the industrial Internet of Things. For the networking scenario, fine-grained scheduling that attends to each device becomes necessary, given stringent Quality-of-Service (QoS) requirements and diversified service types, but prohibitively complex for a large number of devices. To address this challenge, we propose a scheduling solution in two steps. First, we develop algorithms for device assignment based on the analytical results from Part I, when parameters of the proposed protocol are given. Then, we train a deep neural network for assisting in the determination of the protocol parameters. The two-step approach ensures the accuracy and granularity necessary for satisfying the QoS requirements and avoids excessive complexity from handling a large number of devices. Integrating the distributed coordination in the protocol design from Part I and the centralized scheduling from this part, the proposed MAC protocol achieves high performance, demonstrated through extensive simulations. For example, the results show that the proposed MAC can support 1000 devices under an aggregated traffic load of 3000 packets per second with a single channel and achieve <; 0.5 ms average delay and <; 1% average collision probability among 50 high priority devices.

In this two-part paper, we propose a novel medium access control (MAC) protocol for machine-type communications in the Industrial Internet of Things. The considered use case features a limited geographical area and a massive number of devices with sporadic data traffic and different priority types. We target supporting the devices while satisfying their Quality-of-Service (QoS) requirements with a single access point and a single channel, which necessitates a customized design that can significantly improve the MAC performance. In Part I of this paper, we present the MAC protocol that comprises a new slot structure, corresponding channel access procedure, and mechanisms for supporting high device density and providing differentiated QoS. A key idea behind this protocol is sensing-based distributed coordination for significantly improving channel utilization. To characterize the proposed protocol, we analyze its delay performance based on the packet arrival rates of devices. The analytical results provide insights and lay the groundwork for the fine-grained scheduling with QoS guarantee as presented in Part II.

In this paper, we investigate a radio access network (RAN) slicing problem for Internet of vehicles (IoV) services with different quality of service (QoS) requirements, in which multiple logically-isolated slices are constructed on a common roadside network infrastructure. A dynamic RAN slicing framework is presented to dynamically allocate radio spectrum and computing resource, and distribute computation workloads for the slices. To obtain an optimal RAN slicing policy for accommodating the spatial-temporal dynamics of vehicle traffic density, we first formulate a constrained RAN slicing problem with the objective to minimize long-term system cost. This problem cannot be directly solved by traditional reinforcement learning (RL) algorithms due to complicatedcoupled constraintsamong decisions. Therefore, we decouple the problem into a resource allocation subproblem and a workload distribution subproblem, and propose atwo-layer constrainedRL algorithm, namedResourceAllocation andWorkload diStribution (RAWS) to solve them. Specifically, anouter layerfirst makes the resource allocation decision via an RL algorithm, and then aninner layermakes the workload distribution decision via an optimization subroutine. Extensive trace-driven simulations show that the RAWS effectively reduces the system cost while satisfying QoS requirements with a high probability, as compared with benchmarks.

Training generative models that can generate high-quality text with sufficient diversity is an important open problem for Natural Language Generation (NLG) community. Recently, generative adversarial models have been applied extensively on text generation tasks, where the adversarially trained generators alleviate the exposure bias experienced by conventional maximum likelihood approaches and result in promising generation quality. However, due to the notorious defect of mode collapse for adversarial training, the adversarially trained generators face a quality-diversity trade-off, i.e., the generator models tend to sacrifice generation diversity severely for increasing generation quality. In this paper, we propose a novel approach which aims to improve the performance of adversarial text generation via efficiently decelerating mode collapse of the adversarial training. To this end, we introduce a cooperative training paradigm, where a language model is cooperatively trained with the generator and we utilize the language model to efficiently shape the data distribution of the generator against mode collapse. Moreover, instead of engaging the cooperative update for the generator in a principled way, we formulate a meta learning mechanism, where the cooperative update to the generator serves as a high level meta task, with an intuition of ensuring the parameters of the generator after the adversarial update would stay resistant against mode collapse. In the experiment, we demonstrate our proposed approach can efficiently slow down the pace of mode collapse for the adversarial text generators. Overall, our proposed method is able to outperform the baseline approaches with significant margins in terms of both generation quality and diversity in the testified domains.

Open Information Extraction (OIE) is a task of generating the structured representations of information from natural language sentences. Recently years, many works have trained an End-to-End OIE extractor based on Sequence-to-Sequence (Seq2Seq) model and applied Reinforce Algorithm to update the model. However, the model performance often suffers from a large training variance and limited exploration. This paper introduces a reinforcement learning framework that enables an Advantage Actor-Critic (AAC) algorithm to update the Seq2Seq model with samples from a novel Confidence Exploration (CE). The AAC algorithm reduces the training variance with a fine-grained evaluation of each individual word. The confidence exploration provides effective training samples by exploring the word at key positions. Empirical evaluations demonstrate the leading performance of our Advantage Actor-Critic algorithm and Confidence Exploration over other comparison methods.

In this paper, we propose a reinforcement learning based large scale multi-objective ranking system for optimizing short-video recommendation on an industrial video sharing platform. Multiple competing ranking objective and implicit selection bias in user feedback are the main challenges in real-world platform. In order to address those challenges, we integrate multi-gate mixture of experts and soft actor critic into the ranking system. We demonstrated that our proposed framework can greatly reduce the loss function compared with systems only based on single strategies.

To extract knowledge from general web text, it requires to build a domain-independent extractor that scales to the entire web corpus. This task is known as Open Information Extraction (OIE). This paper proposes to apply Monte-Carlo Tree Search (MCTS) to accomplish OIE. To achieve this goal, we define a Markov Decision Process for OIE and build a simulator to learn the reward signals, which provides a complete reinforcement learning framework for MCTS. Using this framework, MCTS explores candidate words (and symbols) under the guidance of a pre-trained Sequence-to-Sequence (Seq2Seq) predictor and generates abundant exploration samples during training. We apply the exploration samples to update the reward simulator and the predictor, based on which we implement another MCTS to search the optimal predictions during inference. Empirical evaluation demonstrates that the MCTS inference substantially improves the accuracy of prediction (more than 10%) and achieves a leading performance over other state-of-the-art comparison models.

Recent years have witnessed the continuing growth of people’s dependence on touchscreen devices. As a result, input speed with the onscreen keyboard has become crucial to communication efficiency and user experience. In this work, we formally discuss the general problem of input expectation prediction with a touch-screen input method editor (IME). Taken input efficiency as the optimization target, we proposed a neural end-to-end candidates generation solution to handle automatic correction, reordering, insertion, deletion as well as completion. Evaluation metrics are also discussed base on real use scenarios. For a more thorough comparison, we also provide a statistical strategy for mapping touch coordinate sequences to text input candidates. The proposed model and baselines are evaluated on a real-world dataset. The experiment (conducted on the PaddlePaddle deep learning platform1) shows that the proposed model outperforms the baselines.

The paradigm of network function virtualization (NFV) with the support of software defined networking (SDN) emerges as a promising approach for customizing network services in fifth generation (5G) networks. In this paper, a multicast service orchestration framework is presented, where joint traffic routing and virtual network function (NF) placement are studied for accommodating multicast services over an NFV-enabled physical substrate network. First, we investigate a joint routing and NF placement problem for a single multicast request accommodated over a physical substrate network, with both single-path and multipath traffic routing. The joint problem is formulated as a mixed integer linear programming (MILP) problem to minimize the function and link provisioning costs, under the physical network resource constraints, flow conservation constraints, and NF placement rules; Second, we develop an MILP formulation that jointly handles the static embedding of multiple service requests over the physical substrate network, where we determine the optimal combination of multiple services for embedding and their joint routing and placement configurations, such that the aggregate throughput of the physical substrate is maximized, while the function and link provisioning costs are minimized. Since the presented problem formulations are NP-hard, low complexity heuristic algorithms are proposed to find an efficient solution for both single-path and multipath routing scenarios. Simulation results are presented to demonstrate the effectiveness and accuracy of the proposed heuristic algorithms.

Software defined networking (SDN) and network function virtualization (NFV) are key enabling technologies in fifth generation (5G) communication networks for embedding service-level customized network slices in a network infrastructure, based on statistical resource demands to satisfy long-term quality of service (QoS) requirements. However, traffic loads in different slices are subject to changes over time, resulting in challenges for consistent QoS provisioning. In this paper, a dynamic flow migration problem for embedded services is studied, to meet end-to-end (E2E) delay requirements with time-varying traffic. A multi-objective mixed integer optimization problem is formulated, addressing the trade-off between load balancing and reconfiguration overhead. The problem is transformed to a tractable mixed integer quadratically constrained programming (MIQCP) problem. It is proved that there is no optimality gap between the two problems; hence, we can obtain the optimum of the original problem by solving the MIQCP problem with some post-processing. To reduce time complexity, a heuristic algorithm based on redistribution of hop delay bounds is proposed to find an efficient solution. Numerical results are presented to demonstrate the aforementioned trade-off, the benefit from flow migration in terms of E2E delay guarantee, as well as the effectiveness and efficiency of the heuristic solution.

We introduce the discussion mechanism into the multiagent communicating encoder-decoder architecture for Natural Language Generation (NLG) tasks and prove that by applying the discussion mechanism, the communication between agents becomes more effective. Generally speaking, an encoder-decoder architecture predicts target-sequence word by word in several time steps. At each time step of prediction, agents with the discussion mechanism predict the target word after several discussion steps. In the first step of discussion, agents make their choice independently and express their decision to other agents. In the next discussion step, agents collect other agents’ decision to update their own decisions, then express the updated decisions to others again. After several iterations, the agents make their final decision based on a well-communicated situation. The benefit of the discussion mechanism is that multiple encoders can be designed as different structures to fit the specified input or to fetch different representations of inputs.We train and evaluate the discussion mechanism on Table to Text Generation, Text Summarization and Image Caption tasks, respectively. Our empirical results demonstrate that the proposed multi-agent discussion mechanism is helpful for maximizing the utility of the communication between agents.

Recent neural network models have significantly advanced the task of coreference resolution.However, current neural coreference models are typically trained with heuristic loss functions that are computed over a sequence of local decisions.In this paper, we introduce an end-to-end reinforcement learning based coreference resolution model to directly optimize coreference evaluation metrics.Specifically, we modify the state-of-the-art higherorder mention ranking approach in Lee et al. (2018) to a reinforced policy gradient model by incorporating the reward associated with a sequence of coreference linking actions.Furthermore, we introduce maximum entropy regularization for adequate exploration to prevent the model from prematurely converging to a bad local optimum.Our proposed model achieves new state-of-the-art performance on the English OntoNotes v5.0 benchmark.

In this paper, a comprehensive software-defined networking (SDN) based transmission protocol (SDTP) is presented for fifth generation (5G) communication networks, where an SDN controller gathers network state information from the physical network to improve data transmission efficiency between end hosts, with in-path packet retransmission. In the SDTP, we first develop a new two-way handshake mechanism for connection establishment between a pair of end host. With the aid of SDN control module, signaling exchanges for establishing E2E connections are migrated to the control plane to improve resource utilization in the data plane. A new SDTP packet header format is designed to support efficient data transmission with in-path packet caching and packet retransmission. Based on the new data packet format, a novel in-path receiver-based packet loss detection and caching-based packet retransmission scheme is proposed to achieve in-path fast recovery of lost packets. Extensive simulation results are presented to validate the effectiveness of the proposed protocol in terms of low connection establishment delay and low end-to-end packet transmission delay.

Service-oriented virtual network deployment is based on statistical resource demands of different services, while data traffic from each service fluctuates over time. In this paper, a delay-aware flow migration problem for embedded services is studied to meet end-to-end (E2E) delay requirement with time-varying traffic. A non-convex multi-objective mixed integer optimization problem is formulated, addressing the trade-off between maximum load balancing and minimum reconfiguration overhead due to flow migrations, under processing and transmission resource constraints and QoS requirement constraints. Since the original problem is non-solvable in optimization solvers due to unsupported types of quadratic constraints, it is transformed to a tractable mixed integer quadratically constrained programming (MIQCP) problem. The optimality gap between the two problems is proved to be zero, so we can obtain the optimum of the original problem through solving the MIQCP problem with some post-processing. Numerical results are presented to demonstrate the aforementioned trade-off, as well as the benefit from flow migration in terms of E2E delay performance guarantee.

In this paper, an analytical end-to-end (E2E) packet delay modeling is established for multiple traffic flows traversing an embedded virtual network function (VNF) chain in fifth generation communication networks. The dominant-resource generalized processing sharing is employed to allocate both computing and transmission resources among flows at each network function virtualization (NFV) node to achieve dominant-resource fair allocation and high resource utilization. A tandem queueing model is developed to characterize packets of multiple flows passing through an NFV node and its outgoing transmission link. For analysis tractability, we decouple packet processing (and transmission) of different flows in the modeling and determine average packet processing and transmission rates of each flow as approximated service rates. An M/D/1 queueing model is developed to calculate packet delay for each flow at the first NFV node. Based on the analysis of packet interarrival time at the subsequent NFV node, we adopt an M/D/1 queueing model as an approximation to evaluate the average packet delay for each flow at each subsequent NFV node. The queueing model is proved to achieve more accurate delay evaluation than that using a G/D/1 queueing model. Packet transmission delay on each embedded virtual link between consecutive NFV nodes is also derived for E2E delay calculation. Extensive simulation results demonstrate the accuracy of our proposed E2E packet delay modeling, upon which delay-aware VNF chain embedding can be achieved.

We propose the task of Open-Domain Information Narration (OIN) as the reverse task of Open Information Extraction (OIE), to implement the dual structure between language and knowledge in the open domain.We then develop an agent, called Orator, to accomplish the OIN task, and assemble the Orator and the recently proposed OIE agent -Logician (Sun et al., 2018) into a dual system to utilize the duality structure with a reinforcement learning paradigm.Experimental results reveal the dual structure between OIE and OIN tasks helps to build better both OIE agents and OIN agents.

The software defined networking (SDN) enabled network function virtualization (NFV) architecture emerges as a cost-effective solution for service customization in fifth generation (5G) networks. In this paper, a joint traffic routing and virtual network function (VNF) placement problem is studied for a multicast service request accommodated over a physical substrate network, where the multipath traffic routing is considered between embedded VNFs. The joint problem is formulated as a mixed integer linear programming (MILP) problem to minimize the provisioning cost of both VNFs and links, under the physical network resource constraints, flow conservation constraints, and VNF placement rules. Since the problem is NP-hard, low complexity heuristic algorithms, with the consideration of both the single-path and multipath routing cases, are proposed to determine an efficient solution. Simulation results are presented to demonstrate the effectiveness and accuracy of the proposed heuristic algorithms especially for a large-size network.

Network function virtualization (NFV) is one of the enabling technologies for fifth generation (5G) networks. How to allocate physical resources to customized network services both fairly and efficiently remains a challenging research issue in NFV. This paper proposes a two-stage approach to jointly optimize the chaining and embedding of virtual network functions (VNFs), to obtain feasible composition and embedding results with low complexity, while the average embedding cost is minimized and the total revenue is increased. In the first stage, the VNF chaining order is optimized based on the location and functionality of substrate nodes, and the ratio of outgoing data rate over incoming data rate for each required VNF. In the second stage, we allocate the physical resources based on the preliminary VNF ordering under the resource capacity constraints. A node splitting mechanism is also employed to improve the resource allocation fairness and increase the service acceptance ratio for the substrate network. Simulation results are presented to validate the feasibility and effectiveness of the proposed approach.

In this paper, we consider the problem of open information extraction (OIE) for extracting entity and relation level intermediate structures from sentences in open-domain. We focus on four types of valuable intermediate structures (Relation, Attribute, Description, and Concept), and propose a unified knowledge expression form, SAOKE, to express them. We publicly release a data set which contains 48,248 sentences and the corresponding facts in the SAOKE format labeled by crowdsourcing. To our knowledge, this is the largest publicly available human labeled data set for open information extraction tasks. Using this labeled SAOKE data set, we train an end-to-end neural model using the sequence-to-sequence paradigm, called Logician, to transform sentences into facts. For each sentence, different to existing algorithms which generally focus on extracting each single fact without concerning other possible facts, Logician performs a global optimization over all possible involved facts, in which facts not only compete with each other to attract the attention of words, but also cooperate to share words. An experimental study on various types of open domain relation extraction tasks reveals the consistent superiority of Logician to other states-of-the-art algorithms. The experiments verify the reasonableness of SAOKE format, the valuableness of SAOKE data set, the effectiveness of the proposed Logician model, and the feasibility of the methodology to apply end-to-end learning paradigm on supervised data sets for the challenging tasks of open information extraction.

Network slicing often involves instantiation of certain network functionality into network nodes, possibly subject to function chaining constraints. In this paper, we introduce the novel concept of elastic service function chain (SFC), which is an ordered list of virtual functions that may be optional or recursive, and we address network slicing with such chaining constraints as a Software Defined Topology (SDT) problem. We formulate the SDT problem as a combinatorial optimization problem that includes a multi-commodity flow problem and a bin packing problem as sub-problems. Since it inherits NP hardness from the bin packing sub problem, we develop a heuristic algorithm to tackle it. The algorithm's effectiveness and performance are evaluated via simulation study.

MTC services are undergoing rapid increase; billions of MTC connections can be anticipated in a few years. When supporting MTC services in telecommunications networks, MTC traffic characteristics and its unique service requirements should be exploited in order to optimize resource utilization and offer satisfactory service quality for all devices. In this paper, we present an Information-Centric Virtual Network Architecture (IC-VNA) that allows to meticulously combine both the customer and operator specific virtual functions along with their requirements to construct an augmented virtual network topology. It is shown that through the IC-VNA it is feasible to rapidly roll-out highly programmable and flexible services while providing high degree of scalability and cost effectiveness for both MTC service providers and network operators.

Machine to machine (M2M) traffic is characterized as low-rate, small-packet traffic with correlated transmissions. In this paper, we propose a two-phase traffic control mechanism (2PTC) for carrying M2M traffic in the future fifth generation (5G) networks. In this mechanism, the packets from each machine are directed to a virtual serving gateway associated with the machine, which receives and aggregates traffic from multiple machines and forwards the aggregate traffic to the sink. The first communication phase takes place through a simple single-path routing technique, while the second phase is empowered by multipath traffic engineering (TE) optimization. At the virtual serving gateways, traffic aggregation (TA) may include network-layer flow trunking and application-layer content compression. At the core of 2PTC is joint gateway selection and machine-to-gateway association that favors TA potentials while minimizing association cost and virtual serving gateway count. The described problem is formulated as a mixed integer programming optimization problem. As the structure of the formulation is inherently NP hard, the problem is solved using relaxation and rounding techniques, whose solution quality is evaluated through numerical analysis. We also implement the solution in a network simulator and evaluate the performance of 2PTC, through extensive simulations. Simulation results indicate that routing M2M traffic to properly selected virtual serving gateways for TA can alleviate the large-quantity small-packet problem, while enhancing the performance of the background traffic. This paves the way for further performance enhancement or enabling new features when deploying virtual network functions at virtual serving gateways.

We consider traffic engineering (TE) in networks where quality of service (QoS)-guaranteed as well as best effort (BE) services are present. We propose a joint TE optimization technique for both QoS and BE traffic using multi-objective optimization framework. We show that joint TE optimization results in more efficient network resource usage compared to sequential TE methodology where TE decision (finding paths and traffic splitting among paths) is made for QoS-guaranteed traffic first by assigning appropriate network resources and then TE decision is made for BE traffic according to remaining network resources. Furthermore, we consider QoS traffic demand fluctuations and propose a joint TE problem formulation to address both QoS traffic demand fluctuations and efficient network resource usage for BE traffic.

Interference alignment (IA) is a scheme to approach the capacity at high signal-to-noise ratio (SNR) in multiuser multiple-input multiple-output (MIMO) interference networks. To implement the IA scheme in a frequency-division duplexing (FDD) system, transmitter channel state information (CSIT) is fed back from the receiver with finite bits. However, such CSIT is subject to quantization errors and delays of feedback channels. In this paper, we verify that interference leakage is bounded by chordal distance in the MIMO channel. Besides, a joint real Grassmannian quantization strategy is proposed to reduce chordal distance to improve CSIT quality. Meanwhile, under the noise-limited criterion, the lower bound of the codebook size of our proposed strategy is much smaller than that of the conventional complex Grassmannian quantization strategy. Simulations demonstrate that our proposed strategy provides substantial performance gains compared with the conventional strategy.

Interference alignment (IA) is a scheme to achieve degrees of freedom (DOF) of interference network at high signal-to-noise ratio (SNR). In order to implement IA scheme in frequency-division duplexing (FDD) system, receivers feedback channel state information to transmitters. The key problem is to acquire accurate transmitter channel state information (CSIT) in the presence of the quantization error. In this paper, a joint real Grassmannian quantization strategy is proposed to reduce codebook size in single-input single-output (SISO) frequency-selective channel with K user. More concretely, this strategy quantizes the real part and imaginary part of channel vector respectively to reduce the chordal distance. Meanwhile, a noise-limited criterion is assumed that interference leakage is smaller than thermal noise. Under this criterion, the codebook size using the proposed strategy is much smaller than the codebook size using conventional complex Grassmannian quantization strategy. With the same codebook size, simulations show a significant sum rate gain at high SNR compared with the conventional strategy.

We consider a cloud-based heterogeneous network of base stations (BSs) connected via a backhaul network of routers and wired/wireless links with limited capacity. The optimal provision of such networks requires proper resource allocation across the radio access links in conjunction with appropriate traffic engineering within the backhaul network. In this paper, we propose an efficient algorithm for joint resource allocation across the wireless links and flow control over the entire network. The proposed algorithm, which maximizes the min-rate among all the transmitted commodities, is based on a decomposition approach that leverages both the alternating direction method of multipliers (ADMM) and the weighted-MMSE (WMMSE) algorithm. We show that this algorithm is easily parallelizable and converges globally to a stationary solution of the joint optimization problem. The proposed algorithm can also be extended to networks with multi-antenna nodes and other utility functions.

The barrier coverage problem in emerging mobile sensor networks has been an interesting research issue due to many related real-life applications. Existing solutions are mainly concerned with deciding one-time movement for individual sensors to construct as many barriers as possible, which may not be suitable when there are no sufficient sensors to form a single barrier. In this paper, we aim to achieve barrier coverage in the sensor scarcity scenario by dynamic sensor patrolling. Specifically, we design a periodic monitoring scheduling (PMS) algorithm in which each point along the barrier line is monitored periodically by mobile sensors. Based on the insight from PMS, we then propose a coordinated sensor patrolling (CSP) algorithm to further improve the barrier coverage, where each sensor's current movement strategy is derived from the information of intruder arrivals in the past. By jointly exploiting sensor mobility and intruder arrival information, CSP is able to significantly enhance barrier coverage. We prove that the total distance that sensors move during each time slot in CSP is the minimum. Considering the decentralized nature of mobile sensor networks, we further introduce two distributed versions of CSP: S-DCSP and G-DCSP. We study the scenario where sensors are moving on two barriers and propose two heuristic algorithms to guide the movement of sensors. Finally, we generalize our results to work for different intruder arrival models. Through extensive simulations, we demonstrate that the proposed algorithms have desired barrier coverage performances.

Existing solutions to carrier-based sensor placement by a single robot in a bounded unknown Region of Interest (ROI) do not guarantee full area coverage or termination. We propose a novel localized algorithm, named Back-Tracking Deployment (BTD). To construct a full coverage solution over the ROI, mobile robots (carriers) carry static sensors as payloads and drop them at the visited empty vertices of a virtual square, triangular, or hexagonal grid. A single robot will move in a predefined order of directional preference until a dead end is reached. Then it back-tracks to the nearest sensor adjacent to an empty vertex (an “entrance” to an unexplored/uncovered area) and resumes regular forward movement and sensor dropping from there. To save movement steps, the back-tracking is carried out along a locally identified shortcut. We extend the algorithm to support multiple robots that move independently and asynchronously. Once a robot reaches a dead end, it will back-track, giving preference to its own path. Otherwise, it will take over the back-track path of another robot by consulting with neighboring sensors. We prove that BTD terminates within finite time and produces full coverage when no (sensor or robot) failures occur. We also describe an approach to tolerate failures and an approach to balance workload among robots. We then evaluate BTD in comparison with the only competing algorithms SLD [Chang et al. 2009a] and LRV [Batalin and Sukhatme 2004] through simulation. In a specific failure-free scenario, SLD covers only 40--50% of the ROI, whereas BTD covers it in full. BTD involves significantly (80%) less robot moves and messages than LRV.

Optimal routing in wireless mesh networks is a challenging problem considering inter- and intra-flow interference. To solve the problem, first, we define a new routing metric, expected path bandwidth (EPBW), where the varying link rate (due to wireless channel quality) and the dynamic link load (considering the inter- and intra-flow interference) have been considered to estimate EPBW accurately. Second, based on the proposed EPBW, we propose a distributed routing protocol for WMNs, aiming to maximize network throughput. We implement the proposed protocol and the routing metric EPBW in NS-2. We then design various scenarios to evaluate the protocol performance extensively using NS-2 simulation. Simulation results show that the proposed protocol and metric can substantially out-perform the state-of-the-art routing metrics, such as expected transmission count (ETX) and expected transmission time (ETT), and previous routing protocols including AODV, DSDV, and DSR.

In this paper, we address the problem of peer-to-peer networking for data dissemination among actors in wireless sensor and actor networks (WSANs), which consist of static sensors, responsible for environment monitoring, and mobile actors, in charge of data collection and task performing. This problem has not been received much attention although peer-to-peer networking has achieved great successes in other networks such as the Internet and mobile ad hoc networks (MANETs). Unlike the Internet and MANETs, WSANs contain static sensors that are energy-constrained and actors that cannot communicate with each other directly. These unique characteristics make the data dissemination problem in WSANs extremely challenging. We present an Energy-Efficient Message Dissemination protocol (EMD) to solve this problem in delay-tolerant WSANs. EMD is grounded on a novel principle of "Carry-Disseminate-Store-and-Forward" proposed for the first time here. While traveling, a source actor disseminates messages (data) to sensors upon contact, which will store the messages and forward them to other actors when they come into communication range. The actors receiving the messages from sensors work as source actors and help to distribute the messages. We theoretically analyze the data dissemination strategy under which the original source actor can distribute its messages to all other actors at minimum communication cost within a given delay bound. Through extensive simulations we demonstrate the performance of EMD.

In this paper, we study user profile matching with privacy-preservation in mobile social networks (MSNs) and introduce a family of novel profile matching protocols. We first propose an explicit Comparison-based Profile Matching protocol (eCPM) which runs between two parties, an initiator and a responder. The eCPM enables the initiator to obtain the comparison-based matching result about a specified attribute in their profiles, while preventing their attribute values from disclosure. We then propose an implicit Comparison-based Profile Matching protocol (iCPM) which allows the initiator to directly obtain some messages instead of the comparison result from the responder. The messages unrelated to user profile can be divided into multiple categories by the responder. The initiator implicitly chooses the interested category which is unknown to the responder. Two messages in each category are prepared by the responder, and only one message can be obtained by the initiator according to the comparison result on a single attribute. We further generalize the iCPM to an implicit Predicate-based Profile Matching protocol (iPPM) which allows complex comparison criteria spanning multiple attributes. The anonymity analysis shows all these protocols achieve the confidentiality of user profiles. In addition, the eCPM reveals the comparison result to the initiator and provides only conditional anonymity; the iCPM and the iPPM do not reveal the result at all and provide full anonymity. We analyze the communication overhead and the anonymity strength of the protocols. We then present an enhanced version of the eCPM, called eCPM+, by combining the eCPM with a novel prediction-based adaptive pseudonym change strategy. The performance of the eCPM and the eCPM+ are comparatively studied through extensive trace-based simulations. Simulation results demonstrate that the eCPM+ achieves significantly higher anonymity strength with slightly larger number of pseudonyms than the eCPM.

We propose a radically new family of geometric graphs, i.e., Hypocomb (HC), Reduced Hypocomb (RHC), and Local Hypocomb (LHC). HC and RHC are extracted from a complete graph; LHC is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity, and degree bound. All these graphs are connected (provided that the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and pinpoint some interesting open problems for future research.

Distributed collaborative spectrum sensing is a promising method to improve the precision and efficiency of primary user detection in cognitive radio networks. Despite its performance advantages, it introduces new security issues that malicious or selfish nodes may manipulate false sensing data to degrade or even covert the sensing result of the whole network. Existing research often utilizes a threshold to distinguish honest users and malicious ones. However, determining such a threshold is difficult due to the dynamic characteristic of cognitive radio networks, and it is likely to misjudge an honest node with a relatively large deviation to be malicious. In this paper, we propose an Adaptive Deviation-tolerant Secure Scheme (ADS) for distributed collaborative spectrum sensing, which aims to mitigate the misbehaviors of inside malicious nodes and, at the same time, tolerant the large deviation introduced by honest users. ADS achieves the trade off of sensing security and deviation tolerance by assigning a dynamic weight to each sensing node and utilizes an adaptive threshold to minimize the negative effect on honest users. We evaluate the performance of the scheme through both analytical and simulation based study.

Mobile robots nowadays can assist wireless sensor networks (WSNs) in many jeopardizing scenarios that unexpectedly arise during their operational lifetime. We focus on an emerging kind of cooperative networking system in which a small team of robotic agents lies at a base station. Their mission is to service an already-deployed WSN by periodically replacing all damaged sensors in the field with passive, spare ones so as to preserve the existing network coverage. This novel application scenario is here baptized as “multiple-carrier coverage repair” (MC2R) and modeled as a new generalization of the vehicle routing problem. A hybrid metaheuristic algorithm is put forward to derive nearly-optimal sensor replacement trajectories for the robotic fleet in a short running time. The composite scheme relies on a swarm of artificial fireflies in which each individual follows the exploratory principles featured by Harmony Search. Infeasible candidate solutions are gradually driven into feasibility under the influence of a weak Pareto dominance relationship. A repair heuristic is finally applied to yield a full-blown solution. To the best of our knowledge, our scheme is the first one in literature that tackles MC2R instances. Empirical results indicate that promising solutions can be achieved in a limited time span.

We propose to apply the concept of Cost-to-Progress Ratio (CPR) in greedy routing for load reduction and balancing. The load of a node is the percentage of time it is occupied by forwarding traffic or inability to forward due to interference. The resultant routing protocol, named CPR-routing, is a localized parameterless approach, optimizing the ratio of nodal load and geographic progress. Through extensive simulation, we evaluate it in comparison with an existing parameter-based localized solution, α-routing. Our simulation results indicate that CPR-routing outperforms α-routing in per node load, success rate, and average hop count.

Smart community is an emerging Internet of Things application. It supports a variety of high-value automated services such as pervasive healthcare through a multi-hop community network of smart homes in a local residential region. In this paper, we study privacy preserving data communication between patients and an online healthcare provider (referred to as vendor) for efficient remote healthcare monitoring (RHM) in a smart community environment. We adopt patients' attribute structures instead of their identities for authentication and preserve identity privacy during patient-to-vendor communication, and we build a receiver chain among smart homes to enable vendor-to-patient communication and achieve location privacy. The privacy preserving properties of the proposed data communication scheme are analyzed, and its effectiveness and efficiency are demonstrated through extensive simulations.

Cost function based routing has been widely studied in wireless sensor networks for energy efficiency and network lifetime elongation. Existing algorithms however have limited effects because they adopt a single cost function that does not fully capture nodal energy consumption situation. In this paper, we propose a novel Double Cost Function based Routing (DCFR) algorithm, which takes into account end-to-end energy consumption, nodal remaining energy, and energy consumption rate altogether. An extensive simulation indicates that DCFR can lead to more balanced and efficient energy usage among nodes than existing algorithms.

In this paper, we consider service-oriented mobile social networks (S-MSNs) and propose a Secure and Efficient service Review (SEER) system to enable user feedback. Each service provider independently maintains a SEER system for itself, which collects and stores user reviews about its services without requiring any central trusted authority. The service reviews can then be made available to interested users in making wise service selection decisions. We identify three unique service review attacks and then develop sophisticated security mechanisms for SEER to deal with these attacks. Specifically, SEER enables users to distributedly and cooperatively submit their reviews in an integrated chain form by using hierarchical and aggregate signature techniques. It discourages service providers to reject, modify or delete their reviews. The integrity of reviews is therefore improved. Through security analysis and performance evaluation, we show that SEER effectively resists the service review attacks and achieves significantly better performance in terms of submission rate and delay than a service review system that does not adopt user cooperation or the chain review structure.

Barrier coverage problem in emerging mobile sensor networks has been an interesting research issue. Existing solutions to this problem aim to decide one-time movement for individual sensors to construct as many barriers as possible, which may not work well when there are no sufficient sensors to form a single barrier. In this paper, we try to achieve barrier coverage in sensor scarcity case by dynamic sensor patrolling. In specific, we design a periodic monitoring scheduling (PMS) algorithm in which each point along the barrier line is monitored periodically by mobile sensors. Based on the insight from PMS, we then propose a coordinated sensor patrolling (CSP) algorithm to further improve the barrier coverage, where each sensor's current movement strategy is decided based on the past intruder arrival information. By jointly exploiting sensor mobility and intruder arrival information, CSP is able to significantly enhance barrier coverage. We prove that the total distance that the sensors move during each time slot in CSP is the minimum. Considering the decentralized nature of mobile sensor networks, we further introduce two distributed versions of CSP: S-DCSP and G-DCSP. Through extensive simulations, we demonstrate that CSP has a desired barrier coverage performance and S-DCSP and G-DCSP have similar performance as that of CSP.

In this paper, we propose a distributed Prediction-based Secure and Reliable routing framework (PSR) for emerging Wireless Body Area Networks (WBANs). It can be integrated with a specific routing protocol to improve the latter's reliability and prevent data injection attacks during data communication. In PSR, using past link quality measurements, each node predicts the quality of every incidental link, and thus any change in the neighbor set as well, for the immediate future. When there are multiple possible next hops for packet forwarding (according to the routing protocol used), PSR selects the one with the highest predicted link quality among them. Specially-tailored lightweight source and data authentication methods are employed by nodes to secure data communication. Further, each node adaptively enables or disables source authentication according to predicted neighbor set change and prediction accuracy so as to quickly filter false source authentication requests. We demonstrate that PSR significantly increases routing reliability and effectively resists data injection attacks through in-depth security analysis and extensive simulation study.

Without direct path, information delivery in sparse delay tolerant networks (DTNs) typically relies on intermittent relays, making the transmission not only unreliable but also time consuming. To make the matter even worse, the source nodes may transmit some encrypted “junk” information, similar as the spam emails in current mail systems, to the destinations; without effective control, the delivery of encrypted junk information would significantly consume the precious resource of DTN and accordingly throttle the network efficiency. To address this challenging issue, we propose PReFilter, an efficient privacy-preserving relay filter scheme to prevent the relay of encrypted junk information early in DTNs. In PReFilter, each node maintains a specific filtering policy based on its interests, and distributes this policy to a group of “friends” in the network in advance. By applying the filtering policy, the friends can filter the junk packets which are heading to the node during the relay. Note that the keywords in the filtering policy may disclose the node's interest/preference to some extent, harming the privacy of nodes, a privacy-preserving filtering policy distribution technique is introduced, which will keep the sensitive keywords secret in the filtering policy. Through detailed security analysis, we demonstrate that PReFilter can prevent strong privacy-curious adversaries from learning the filtering keywords, and discourage a weak privacy-curious friend to guess the filtering keywords from the filtering policy. In addition, with extensive simulations, we show that PReFilter is not only effective in the filtering of junk packets but also significantly improve the network performance with the dramatically reduced delivery cost due to the junk packets.

We propose a novel localized Integrated Location Service and Routing (ILSR) scheme, based on the geographic routing protocol GFG, for data communications from sensors to a mobile sink in wireless sensor networks. The objective is to enable each sensor to maintain a slow-varying routing next hop to the sink rather than the precise knowledge of quick-varying sink position. In ILSR, sink updates location to neighboring sensors after or before a link breaks and whenever a link creation is observed. Location update relies on flooding, restricted within necessary area, where sensors experience (next hop) change in GFG routing to the sink. Dedicated location update message is additionally routed to selected nodes for prevention of routing failure. Considering both unpredictable and predictable (controllable) sink mobility, we present two versions. We prove that both of them guarantee delivery in a connected network modeled as unit disk graph. ILSR is the first localized protocol that has this property. We further propose to reduce message cost, without jeopardizing this property, by dynamically controlling the level of location update. A few add-on techniques are as well suggested to enhance the algorithm performance. We compare ILSR with an existing competing algorithm through simulation. It is observed that ILSR generates routes close to shortest paths at dramatically lower (90% lower) message cost.

As sensors are energy constrained devices, one challenge in wireless sensor networks (WSNs) is to guarantee coverage and meanwhile maximize network lifetime. In this paper, we leverage prediction to solve this challenging problem, by exploiting temporal-spatial correlations among sensory data. The basic idea lies in that a sensor node can be turned off safely when its sensory information can be inferred through some prediction methods, like Bayesian inference. We adopt the concept of entropy in information theory to evaluate the information uncertainty about the region of interest (RoI). We formulate the problem as a minimum weight submodular set cover problem, which is known to be NP hard. To address this problem, an efficient centralized truncated greedy algorithm (TGA) is proposed. We prove the performance guarantee of TGA in terms of the ratio of aggregate weight obtained by TGA to that by the optimal algorithm. Considering the decentralization nature of WSNs, we further present a distributed version of TGA, denoted as DTGA, which can obtain the same solution as TGA. The implementation issues such as network connectivity and communication cost are extensively discussed. We perform real data experiments as well as simulations to demonstrate the advantage of DTGA over the only existing competing algorithm [1] and the impacts of different parameters associated with data correlations on the network lifetime.

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals and becomes localized with minimum delay. We propose a novel DeteRministic dynamic bEAcon Mobility Scheduling (DREAMS) algorithm, without requiring any prior knowledge of the sensory field. In this algorithm, the beacon trajectory is defined as the track of Depth-First Traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT dynamically, under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to Received Signal Strength (RSS)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free, and derive the upper bound of beacon total moving distance in this case. Then, we suggest to apply node elimination and Local Minimum Spanning Tree (LMST) to shorten beacon tour and reduce delay. Further, we extend DREAMS to multibeacon scenarios. Beacons with different coordinate systems compete for localizing sensors. Loser beacons agree on winner beacons' coordinate system, and become cooperative in subsequent localization. All sensors are finally localized in a commonly agreed coordinate systems. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path-based scheduling method.

The concept of smart grid has emerged as a convergence of traditional power system engineering and information and communication technology. It is vital to the success of next generation of power grid, which is expected to be featuring reliable, efficient, flexible, clean, friendly, and secure characteristics. In this paper, we propose an efficient and privacy-preserving aggregation scheme, named EPPA, for smart grid communications. EPPA uses a superincreasing sequence to structure multidimensional data and encrypt the structured data by the homomorphic Paillier cryptosystem technique. For data communications from user to smart grid operation center, data aggregation is performed directly on ciphertext at local gateways without decryption, and the aggregation result of the original data can be obtained at the operation center. EPPA also adopts the batch verification technique to reduce authentication cost. Through extensive analysis, we demonstrate that EPPA resists various security threats and preserve user privacy, and has significantly less computation and communication overhead than existing competing approaches.

In this paper, we propose a coordinate-free distributed boundary detection algorithm (CDBD). It adopts general sensing and communication models and exploits two centrality measures, i.e., betweenness and closeness. For CDBD, each node only needs to communicate with its $k$-hop neighbors twice and makes decision whether it itself is a boundary node independently. CDBD has advantages of fast convergence and low communication overhead. Extensive simulation demonstrates the desirable performance of CDBD.

In this paper, we propose a novel trust management scheme for improving routing reliability in wireless ad hoc networks. It is grounded on two classic autoregression models, namely Autoregressive (AR) model and Autoregressive with exogenous inputs (ARX) model. According to this scheme, a node periodically measures the packet forwarding ratio of its every neighbor as the trust observation about that neighbor. These measurements constitute a time series of data. The node has such a time series for each neighbor. By applying an autoregression model to these time series, it predicts the neighbors future packet forwarding ratios as their trust estimates, which in turn facilitate it to make intelligent routing decisions. With an AR model being applied, the node only uses its own observations for prediction; with an ARX model, it will also take into account recommendations from other neighbors. We evaluate the performance of the scheme when AR, ARX or a previously proposed Bayesian model is used. Simulation results indicate that the ARX model is the best choice in terms of accuracy.

Mobile social network (MSN) is a promising networking and communication platform for users having similar interests (or attributes) to connect and interact with one another. For many recently introduced secure MSN data communication schemes, attribute-based encryption is often adopted to preserve user privacy and prevent outside attackers from eavesdropping. In this paper, we propose an efficient and secure user revocation scheme to address inside attacks based on an attribute-based encryption technique. The proposed scheme enables a trusted authority (TA) to flexibly control the data decryption capability of mobile social users. It disables malicious users from decrypting any data packet. As a result, proper user behavior is encouraged, inside attacks are reduced, and network security is enhanced. Through the analysis, we demonstrate that the proposed user revocation scheme is able to resist attribute collusion attacks and revoke collusion attacks. Extensive simulation results further confirm that the proposed scheme has much smaller communication overhead and much shorter delay than the existing solution [1].

Wireless ad hoc networks have great potentials in a broad range of applications. Their inherent vulnerability to various network attacks however limits their wide adaptation and deployment in practice. In this paper we address one of the most dangerous attacks, packet drop attack, in wireless ad hoc networks by post-routing detection. We introduce a simple, effective detection technique Side Channel Monitoring (SCM). The idea is to use nodes adjacent to a data communication route to monitor the message forwarding behavior of the nodes en route. These monitoring nodes constitute a directional side channel toward the source, in parallel to the backward route (primary channel). On observing misbehavior, they issue alarm packets to the source node through both channels. Considering channel disconnectivity (topologically or due to malicious packet drop), we analytically study the security strength of SCM including detection rate and expected number of detected attacks. Numeric results show that it is effective in various network scenarios.

Mutual user identification is a necessary step for trust establishment among users in an unattended mobile social network (MSN). Directly exposing identity information to others unknown may cause total unfairness in identity loss when the other party of the identification process misbehaves. Using an on-line trusted third party (TTP) for user identification will cause communication and security problems, while a traditional off-line TTP solution will generate delay in fairness enforcement. In this paper, we propose a novel fine-grained identification protocol, which provides confidentiality, unlinkability, and real-time fairness without the involvement of TTP. In the protocol, identification is carried out by an iterative identification information exchange process, where two participating users have to disclose part of their identification information to each other in each iteration. The process terminates whenever one of them fails to do so. In this way, if a user loses part of its identification information to another user, then it must have obtained an approximately equal amount of identification information of that user. Therefore, misbehavior is discouraged, and fairness is improved. Through analysis we demonstrate that fairness can be well guaranteed as long as users strictly follow the protocol rules. Extensive simulation results further confirm that the proposed protocol can significantly reduce fairness loss in MSN environment.

We propose a radically new family of geometric graphs, i.e., Hypocomb, Reduced Hypocomb and Local Hypocomb. The first two are extracted from a complete graph; the last is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity and degree bound. All these graphs are connected (provided the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly-localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and some open problems.

We propose a localized Delay-bounded and Energy-efficient Data Aggregation scheme (DEDA) for wireless sensor and actor networks that are modeled as undirected graphs (URG). The scheme is based on a novel concept of Desired Hop Progress (DHP) and designed for low-traffic, request-driven network scenarios, where delay is proportional to hop count [10]. It builds a local minimal spanning tree (LMST) sub-graph of the network with links weighted by transmission powers. Using edges from LMST, it constructs a shortest path (thus energy-efficient) tree rooted at actor (sink) for data aggregation. The tree is used as is if it generates acceptable delay. Otherwise, it is adjusted by replacing LMST sub-paths with URG edges. The adjustment is done locally, according to the DHP value at each node, with hop count reduction corresponding to the delay allowance per hop (ratio of current LMST delay over maximal allowed one). Through extensive simulation, we show that DEDA may save 25–75% energy per node on average and extend up to 150% network life, depending on network conditions, in comparison with the only existing competing localized solution [11].

Wireless sensor and actor networks (WSANs) are service-oriented environments, where sensors request actors to service their detected events and actors move to deliver the desired services. Because of their openness and unattended nature, these networks are vulnerable to various security attacks. In this paper we address service fraud attacks for the first time, whose objective is to stop the normal use of actor services by fake service requests and/or delivery. To mitigate this type of security attacks, we propose a novel cooperative authentication scheme. With the scheme, a sensor's service request is cooperatively authenticated by the sensors that witness the same event, and an actor's service delivery effort is cooperatively authenticated by the sensors that witness the actor's behavior. Considering the presence of compromised sensor/actor nodes, the trustworthiness of each authenticated service delivery process is subject to location consistency check and witness diversity check. It may then be taken into account to adjust the corresponding actor's trust rating so as to influence future actor service selection. We analyze the communication overhead and the security strength of the scheme. We show that our scheme ensures fraud-resistant actor services in our considered WSAN environment.

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals with minimum delay. We propose a novel DeteRministic bEAcon Mobility Scheduling (DREAMS) algorithm, without requiring any prior knowledge of the sensory field. In this algorithm, beacon trajectory is defined as the track of depth-first traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to RSS (Received Signal Strength)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free. Then we suggest to apply node elimination and topology control (Local Minimum Spanning Tree) to shorten beacon tour and reduce delay. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path based scheduling method.

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, H-polygon and C-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI along locally computed H- or C-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

ABSTRACT In data aggregation, sensor measurements from the whole sensory field or a sub‐field are collected as a single report at an actor by using aggregate functions such as sum, average, maximum, minimum, count, deviation, and so on. We propose a localized delay‐bounded and energy‐efficient data aggregation (DEDA) protocol for request‐driven wireless sensor networks with IEEE 802.11 carrier sense multiple access with collision avoidance run at media access control layer. This protocol uses a novel two‐stage delay model, which measures end‐to‐end delay by using either hop count or degree sum along a routing path depending on traffic intensity. It models the network as a unit disk graph (UDG) and constructs a localized minimal spanning tree (LMST) sub‐graph. Using only edges from LMST, it builds a shortest‐path (thus energy‐efficient) tree rooted at the actor for data aggregation. The tree is used without modification if it generates acceptable delay, compared with a given delay bound. Otherwise, it is adjusted by replacing LMST sub‐paths with UDG edges. The adjustment is done locally on the fly, according to the desired progress value computed at each node. We further propose to integrate DEDA with a localized sensor activity scheduling algorithm and a localized connected dominating set algorithm, yielding two DEDA variants, to improve its energy efficiency and delay reliability. Through an extensive set of simulation, we evaluate the performance of DEDA with various network parameters. Our simulation results indicate that DEDA far outperforms the only existing competing protocol. Copyright © 2011 John Wiley & Sons, Ltd.

We introduce a novel combinatorial optimization problem: the one-commodity traveling salesman problem with selective pickup and delivery (1-TSP-SELPD), characterized by the fact that the demand of any delivery customer can be met by a relatively large number of pickup customers. While all delivery spots are to be visited, only profitable pickup locations will be included in the tour so as to minimize its cost. The motivation for 1-TSP-SELPD stems from the carrier-based coverage repair problem in wireless sensor and robot networks, wherein a mobile robot replaces damaged sensors with spare ones. The ant colony optimization (ACO) meta-heuristic elegantly solves this problem within reasonable time and space constraints. Six ACO heuristic functions are put forward and a recently proposed exploration strategy is exploited to accelerate convergence in dense networks. Results gathered from extensive simulations confirm that our ACO-based model outperforms existing competitive approaches.

We propose a novel localized carrier-based sensor placement algorithm, named Back-Tracking Deployment (BTD). Mobile robots (carriers) carry static sensors and drop them at visited empty vertices of a virtual square, triangular or hexagonal grid in a bounded 2D environment. A single robot will move forward along the virtual grid in open directions with respect to a pre-defined order of preference until a dead end is reached. Then it back tracks to the nearest sensor adjacent to an empty vertex on its backward path. The robot resumes regular forward moving and sensor dropping from there. To save movement steps, the back tracking is performed along a locally identified shortcut. We extend the algorithm to support multiple robots, which move independently and asynchronously. Once a robot reaches a dead end, it will back-track, giving preference to its own path. Otherwise it will take over the back-track path of another robot, by consulting with neighboring sensors. We prove that BTD terminates in finite time and produces full coverage when no sensor failures occur. We also describe an approach to handle sensor faults. Through extensive simulation we show that BTD far outperforms the only competing algorithm LRV in robot moves and robot messages.

In wireless sensor networks (WSN), stochastic node dropping and unpredictable node failure greatly impair coverage, creating sensing holes, while locally redundant sensors exist. If sensors are all equipped with locomotion, they will be able to relocate themselves to improve coverage. But this approach increases the complexity of hardware design for sensors as well as deployment budget. In this paper, we consider a small group of mobile robots to serve WSN. We propose an algorithm, named Randomized Robot-assisted Relocation of Static Sensors (R3S2), for coverage repair and a grid-based variant, called G-R3S2. By these algorithms, mobile robots move within the network to collect redundant sensors and deliver them to reported sensing hole positions. In R3S2, robots move completely at random and relocate encountered redundant sensors. In G-R3S2, the robots random movement is restricted on a virtual grid, and the robots continually move to the next least recently visited grid point so as to increase the chance of discovering redundant sensors and sensing holes. Through extensive simulation, we show their effectiveness and practicality and evaluate their performance. The simulation results indicate in particular that G-R3S2 outperforms R3S2 across all measured metrics.

Focused coverage is defined as the coverage of a wireless sensor network surrounding a point of interest (POI), and is measured by coverage radius, i.e., minimum distance from POI to uncovered areas. Sensor self-deployment algorithm GRG is designed for autonomous focused coverage formation. It however does not always produce optimal (i.e., maximized) coverage radius. In this paper, we propose optimized GRG, referred to as OGRG, for guaranteed coverage radius maximization, and evaluate its performance in comparison with GRG.

We pinpoint a new sensor self-deployment problem, constructing focused coverage around a point of interest (POI), and introduce an evaluation metric, coverage radius. We propose two solutions, greedy advance (GA) and greedy-rotation-greedy (GRG), which are to our knowledge the first sensor self-deployment algorithms that operate in a purely localized manner and yet provide coverage guarantee. The two algorithms drive sensors to move along a locally-computed equilateral triangle tessellation (TT) to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI to a TT vertex where greedy advance can resume. They both yield a connected network of TT layout with hole-free coverage; GRG furthermore assures a hexagon coverage shape centered at POI. We prove their correctness and analyze their coverage radius property. Our study shows that GRG guarantees optimal hexagonal coverage radius and near optimal circular coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

We propose a localized sensor localization scheme making full use of controlled mobility of a location-aware actor and the connectivity of the sensor network. It contains two new algorithms: a unscented particle filter (UPF) based localization algorithm and an actor mobility scheduling algorithm. The former is an application of UPF. It enables sensor self-localization using received signal strength indicator and actor position. The latter models actor mobility scheduling as traveling salesman problem and aims at fully localized network and minimized time delay. Navigated by sensors, the actor depth-first traverses a local minimum spanning tree of a connected 3-dominating set of the network.

We formalize the distance-sensitive service discovery problem in wireless sensor and actor networks, and propose a novel localized algorithm, iMesh. Unlike existing solutions, iMesh uses no global computation and generates constant per-node storage load. In iMesh, new service providers (i.e., actors) publish their location information in four directions, updating an information mesh. Information propagation for relatively remote services is restricted by a blocking rule, which also updates the mesh structure. Based on an extension rule, nodes along mesh edges may further advertise newly arrived relatively near service by backward distance-limited transmissions, replacing previously closer service location. The final information mesh is a planar structure constituted by the information propagation paths. It stores locations of all the service providers and serves as service directory. Service consumers (i.e., sensors) conduct a lookup process restricted within their home mesh cells to discover nearby services. We analytically study the properties of iMesh including construction cost and distance sensitivity over a static network model. We evaluate its performance in static/dynamic network scenarios through extensive simulation. Simulation results verify our theoretical findings and show that iMesh guarantees nearby (closest) service selection with very high probability, Gt99 percent (respectively, Gt95 percent).

In mobile sensor networks, self-deployment and relocation are two different research issues, both of which involve autonomous sensor movement. They share in most cases a common goal, that is, to improve overall network sensing coverage. Under this circumstance, some self-deployment algorithms may be applied to solving relocation problem without modification. However, considering efficiency, they will not be a good option in the scenario with high sensor failure rate. Existing sensor relocation protocols are not quite practical because they rely on strong assumptions and/or have weakness in maintaining network topology. In this paper, we propose a distributed zone-based sensor relocation protocol, ZONER, for mobile sensor networks on the basis of a restricted flooding technique, i.e., ZFlooding. Requiring zero-knowledge about sensor field, the ZONER is able to effectively discover previously-deployed redundant sensors without being concerned with obstacles or network ununiformity, and it relocates them in a shifting way to replace failed non-redundant ones without changing network topology. At the end of the paper, we prove the correctness of the ZONER and point out our future work