Indoor localization is critical for Internet of Things (IoT) applications, yet challenges such as non-Gaussian noise, environmental interference, and measurement outliers hinder the robustness of traditional methods. Existing approaches, including Kalman filtering and its variants, often rely on Gaussian assumptions or static thresholds, limiting adaptability in dynamic environments. This paper proposes a hierarchical robust framework integrating Variational Bayesian (VB) parameter learning, Huber M-estimation, and Conformal Outlier Detection (COD) to address these limitations. First, VB inference jointly estimates state and noise parameters, adapting to time-varying uncertainties. Second, Huber-based robust filtering suppresses mild outliers while preserving Gaussian efficiency. Third, COD provides statistical guarantees for outlier detection via dynamically calibrated thresholds, ensuring a user-controlled false alarm rate. Theoretically, we prove the Semi-positive Definiteness of Huber-based Kalman filtering covariance and the coverage of sliding window conformal prediction. Experiments on geomagnetic fingerprint datasets demonstrate significant improvements: fingerprint matching accuracy increases from 81.25% to 93.75%, and positioning errors decrease from 0.62–4.37 m to 0.03–1.53 m. Comparative studies further validate the framework’s robustness, showing consistent performance gains under non-Gaussian noise and outlier conditions, achieving 95% outlier detection precision with controlled false alarms.

With the commercialization of private data, location privacy trading in Mobile Crowd Sensing (MCS) has become a fascinating research topic. In consideration of location-dependent sensing tasks, mobile workers take risks at location privacy disclosure when reporting their actual locations. Existing work fail to take workers' diverse privacy protection and trading into account. This paper proposes a novel trading framework with personalized differential privacy guarantee, referred to asLeaper, to bridge the gap between location privacy protection and task allocation efficiency. In particular,Leaperoutputs a personalized obfuscated range for each worker and further obfuscates his location based on a perturbation set within this range by incorporating differential privacy and$k$-anonymity techniques, and thus improves the efficiency of task allocation. Moreover,Leaperquantifies each worker's location privacy loss and compensates him with reasonable payment by running auction in a cost-effective way. Through real-world datasets, our evaluations and analysis demonstrate thatLeaperindeed guarantees all desired properties of personalized differential privacy, truthfulness, individual rationality and budget feasibility.

User trajectory publication has promoted various location-based applications like user travel recommendation. However, possible privacy leakages have hindered more inclusive trajectory data analysis and utilization. Privacy-preserving trajectory synthesis is a popular approach to address the above privacy issues. Existing methods unavoidably produce low trajectory utility since they usually apply perturbed versions of human moving patterns. Worse still, they cannot adaptively adjust this synthesis according to the varying granularity demands of different users. This paper proposes a novel adaptive trajectory synthesis framework with generated data, namelyADGTrace. Our model achieves privacy preservation without introducing additional noise while maintaining high adaptation.ADGTracedirectly synthesizes artificial trajectories that share the similar patterns with real ones through agenerative and selectiveoptimization process. Additionally, we present a grid granularity alignment strategy to achieve adaptive trajectory synthesis, satisfying varying user demands. Extensive experiments on real-world datasets demonstrate the superiority ofADGTraceover the state-of-the art methods under various utility metrics, maintaining strong attack resilience.

Mobile Edge Computing (MEC) shifts the computing power to the edge of core networks and provides important impetus in the flourishment of delay sensitive services at the network edge. Digital Twin (DT) technique enables object behavior monitoring, analysis, and prediction through data analytics and artificial intelligence, which facilitates inference service provisioning based on machine learning models. In this paper, we deal with the Quality-of-Experience (QoE) issue of user satisfaction on inference services in DT-assisted MEC networks, through executing user tasks locally or offloaded to the MEC network. We formulate two novel optimization problems: the utility maximization problem, and the dynamic utility maximization problem, with the aim to maximize the total utility of user task executions in terms of QoEs and service delays of users with the services. We first provide an Integer Linear Programming solution for the utility maximization problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, at the expense of bounded resource violations. We then develop an efficient online heuristic for the dynamic utility maximization problem. We also devise an online algorithm with a provable competitive ratio for a special case of the dynamic utility maximization problem without the bandwidth constraint. We finally evaluate the performance of proposed algorithms through simulations. The simulation results show that the proposed algorithms are promising.

Distributed Quantum Computing (DQC) expands qubit capacity by interconnecting multiple Quantum Processing Units (QPUs), but remote gate execution introduces significant entanglement overhead. In this paper, we study the Remote Gate Scheduling problem in DQC (RGS-DQC) under a hybrid Telegate and Teledata model, provide a formal formulation, and establish its NP hardness. To address this challenge, we proposeLABUBU, a layer buffered bundled optimization framework that integrates coordinate wise pruned greedy refinement with bounded perturbation under QPU capacity constraints while maintaining linear complexity per iteration. Extensive simulations on both structured Quantum Fourier Transform circuits and unstructured random circuits show that Labubu consistently reduces entanglement cost compared with Telegate-SA, Telegate-RD, Teledata-ZS, and the competitive GateCover baseline. Experiments on QEC encoded circuits further confirm its potential for large scale fault tolerant distributed quantum computing.

Quantum computing has the potential to outperform classical computing in solving specific problems. However, the limited qubit capacity of existing Quantum Processing Units (QPUs) poses significant barriers to the practical implementation of quantum computing. Distributed quantum computing (DQC) offers a promising approach to scaling the qubit capacity of quantum systems by interconnecting multiple QPUs and enabling collaborative computation. Nevertheless, DQC necessitates implementing remote quantum gate operations that consume entangled qubit pairs, which poses a significant challenge for DQC. In this work, we formulate and investigate the remote gate scheduling (RGS) problem, considering two approaches for remote gate operations: Telegate and Teledata. We propose a hybrid heuristic algorithm that dynamically schedules quantum gate operations within a circuit, executed on distributed QPUs, while minimizing entanglement consumption. We conducted extensive simulations using real-world quantum circuits and processors to evaluate the proposed approach. The results show that our approach reduces entanglement consumption by up to 90% and 25% compared to the two baselines, Telegate-SA and Teledata-ZS, respectively. Furthermore, the execution time of our approach is significantly shorter than that of the baselines.

Vehicle-to-vehicle (V2V) based cooperative perception enhances autonomous driving by overcoming single-agent perception limitations such as occlusions, without relying on extensive infrastructure. However, most existing methods have two key limitations. They treat cooperative perception in isolation, with little consideration for downstream tasks such as planning, leading to poor coordination and inefficient planning decisions. They also assume perception model homogeneity across all vehicles, which can be impractical among vehicles from different manufacturers. To bridge such gaps, we propose Scout, an early-fusion framework for planning-oriented cooperative perception among vehicles of heterogeneous models. Specifically, we formalize a notion of$\Delta \theta$-Risk Increment Distribution (RID) to capture the distribution of the risk increment by incomplete perception to the current trajectory plan, and define a Priority Index (PI) metric for prioritizing cooperative perception on riskier regions. We develop algorithms to estimate$\Delta \theta$-RID and PI at run-time with theoretical bounds. Empirical results demonstrate that Scout surpasses state-of-the-art methods and strong baselines on challenging benchmarks, achieving higher success rates with only 3-10% of their communication volume.

Secure data sharing and storage are critical to realizing the ultra-high safety and efficiency promised by intelligent transportation systems (ITS). However, ensuring data integrity under stringent resource constraints of ITS remains an open challenge. Existing approaches either incur substantial computational and transmission overhead or demand resources beyond what ITS environments can provide. To address this dilemma, we propose a lightweight blockchain-based data sharing and storage framework tailored for ITS. The system features a distributed, asynchronous reputation mechanism that enables trustworthy data evaluation and dissemination without burdening critical computing and communication paths. Additionally, a resource-efficient blockchain storage layer ensures low-latency, tamper-resistant access to locally shared data. Extensive simulations demonstrate that our approach outperforms existing solutions in both integrity assurance and resource efficiency.

Heterogeneous devices in edge computing bring challenges as well as opportunities for edge computing to utilize powerful and heterogeneous hardware for a variety of complex tasks. In this paper, we propose a service function chain placement strategy considering the heterogeneity of devices in deviceless edge computing environments. The service function chain system utilizes lightweight virtualization technologies to manage resources, considering the heterogeneity of devices to support various complex tasks, and offer low latency services to user requests. We propose an optimal service function chain placement problem minimizing the service delay and formulate it into a quasi-convex problem. We implement different edge applications that can be served by function chains and conduct extensive experiments over real heterogeneous edge devices. Results from the experiments and simulations show that our proposed service function chain scheme is applicable in edge environments, and perform well over services latency, resource utilization as well as the power consumption of edge devices.

Cloud storage makes it easier for users to access and share data remotely, but it often requires integration with cryptographic technologies to address consumer-oriented applications, such as fine-grained data access, secure data sharing and retrieval. This paper focuses on the fine-grained access problem of media applications based on time sequence, that is, certain critical media applications based on time sequences should ideally be accessible only to authorized clients. The traditional keyword-based searchable encryption (SE) allows effective search and access over encrypted data while preserving data privacy, but most existing solutions do not support temporal access control (i.e., a mechanism that grants access permissions to users within a specified time range). In this paper, we propose PAC-MC, an efficient password-based access control framework for media cloud relying on content control with the time sequence attribute. PAC-MC not only supports multi-keyword search using any monotonic boolean formulas but also allows media owners to control content-encryption keys for different time periods with an updatable password. Furthermore, it supports the self-retrieval of content-encryption keys. In addition, PAC-MC is provably secure under the standard model. Finally, the detailed performance evaluation results and experimental comparisons indicate that PAC-MC is very efficient and outperforms the previous solutions in terms of computation, communication, and storage costs.

The integration of Artificial Itelligence (AI) and edge computing has sparked significant interest in edge inference services. In this paper, we consider delay-sensitive, differential accuracy inference services in a Mobile Edge Computing (MEC) network while meeting user stringent delay and accuracy requirements. We formulate two novel profit maximization problems under static and dynamic settings of service request arrivals, with the aim of maximizing the accumulative profit of admitted requests. We assign differential accuracy service requests to the corresponding resolution instances of their requested service models, assuming that each resolution instance can serve up to$L\geq 1$the same type of service requests. Since the profit maximization problem is NP-hard, we first formulate an Integer Linear Program (ILP) solution if the problem size is small or medium; otherwise, we devise a constant randomized algorithm with high probability. Then, we consider dynamic service request admissions without the knowledge of future request arrivals for a given finite time horizon, for which we develop a simple yet effective prediction mechanism to accurately predict the number of different resolution instances of each model needed, and pre-deploy the predicted number of resolution instances into cloudlets to reduce instantiating delays. We then devise an online algorithm with a provable competitive ratio for the dynamic profit maximization problem by leveraging the primal-dual dynamic updating technique. Finally, we evaluate the performance of the proposed algorithms by simulations. The simulation results demonstrate that the proposed algorithms are promising.

Quantum computing, utilizing the unique properties of quantum mechanics, has the potential to revolutionize various fields. However, current quantum processors face challenges in scaling the number of qubits, limiting their practical applications. In response, Distributed Quantum Computing (DQC) has emerged as a promising paradigm where multiple interconnected Quantum Processing Units (QPUs) collaborate to execute quantum circuits. In this paper, we focus on designing networks to interconnect QPUs for the implementation of DQC. We find that in real-world experiments and systems, the photon collection and coupling efficiency is low, leading to significant performance degradation in direct connection networks. To address this limitation, we propose a novel multistage switching network tailored for DQC, which has low system complexity and high entanglement generation rates. The proposed switching network comprises$\log _{2}(N)$stages and$N/2$binary switches at each stage, where N represents the number of QPUs. We prove that the proposed network is nonblocking and develop an efficient routing algorithm with a time complexity of$\mathcal {O}(N\log (N))$. Additionally, we show the success probability of entanglement generation in the proposed switching network. Extensive simulations demonstrate that our network significantly outperforms the highly efficient circuit-switching Beneš network and three direct connection networks.

Network Function Virtualization (NFV) has the potential for cost-efficiency, manage-convenience, and flexibility services but meanwhile poses challenges for the service function chain (SFC) deployment problem, which is NP-hard. It is so complicated that existing work conspicuously neglects the flow changes along the chains and only gives heuristic algorithms without a performance guarantee. In this paper, we fill this gap by formulating a traffic-sensitive online joint SFC placement and flow routing (TO-JPR) model, with the objective of jointly optimize the resource cost and network latency, and proposing a novel two-stage scheme to solve it. We design a dynamic segmental packing (DSP) algorithm for the first stage, which not only maintains the minimal traffic burden for the network but also achieves an approximation ratio of a small constant on the resource cost. Besides, we propose the greedy mapping (GM) algorithm for the second stage, which can guarantee a global approximation ratio of O(d) on the network latency. Here d is the diameter of the network graph and is typically smaller than O(log(M)), where M is the number of servers in the network. Finally, we perform extensive simulations to demonstrate the outstanding performance of our algorithms compared with the optimal solutions and benchmarks.

Open Radio Access Networks (O-RANs) are transforming the landscape of telecommunications to better performance and higher cost-efficiency by enabling network operators to integrate diverse vendor components. Nevertheless, the involvement of multiple Network Service Providers (NSPs) and Mobile Network Operators (MNOs) also brings new challenges in the management of computation and network resources. To resolve this challenge, we propose a blockchain-based framework to guarantee secure, transparent, and decentralized resource allocation in O-RAN systems. Our resource allocation mainly considers the tradeoff of cost and service quality. Our design facilitates real-time adjustments to resource distribution based on dynamic network conditions and incorporates user feedback to optimize service quality continuously. By integrating a Proof-of-Reputation (PoR) consensus mechanism, the framework enhances the reliability and integrity of transactions among competing vendors without central oversight. We evaluate the performance of our design through extensive simulations, which demonstrate significant improvements over the baselines in resource utilization and service delivery across various network scenarios.

Quantum computing has the potential to solve complicated problems that are impossible for classical servers. Nevertheless, the applications of current quantum processors are restricted by their limited qubit capacity. Distributed Quantum Computing (DQC) is promising to scale up the computing capability by interconnecting quantum processors and performing computing collectively. The network interconnecting quantum processors can impact the efficiency of DQC. In this paper, we analyze and compare the performance of various interconnection networks for DQC. First, we meticulously derive the success probabilities of entanglement generation and the fidelity of shared Bell states generated within three typical static networks: line, ring, and grid. In addition, we propose a switching network with a minimal number of switch stages and evaluate its performance in terms of probability and fidelity. Moreover, we conduct extensive simulations based on real-world parameters to compare the static and switching networks, and the results reveal that the switching network performs better and is more scalable.

Intelligent reflecting surface (IRS) has been widely recognized as one of the key techniques to improve secure communications performances. However, most existing works mainly focus on the passive beamforming, i.e., phase-shifts, design of a single IRS, without taking into account the cooperations among multiple IRSs and the optimizations of their relative positions. To overcome these deficiencies, in this paper we propose the joint optimizations between the transmit beamforming of massive multiple-input multiple-output (massive-MIMO) access point (AP) and double-IRS’ positions and passive beamforming over 6G secure mobile networks. In our proposed networking architectures, AP transmits data to multiple mobile users (MUs) through reflections of two cooperative IRSs under the existence of one eavesdropper (Eve). First, we formulate a secrecy rate optimization problem to maximize the expectations of all MUs’ aggregate secrecy rates when Eve’s exact position is unknown. Second, leveraging the deep reinforcement learning (DRL), we develop two joint deploying and beamforming schemes to tackle the uncertainty of Eve’s exact position. Finally, we validate and evaluate our developed schemes by conducting the extensive simulations, showing the significant performances improvements of our developed schemes through jointly optimizing IRSs’ positions/orientations and transmit-beamforming of massive-MIMOAP as the function of the predicted Eve’s deploying areas.

Distributed Quantum Computing (DQC) has the potential to solve industrial large-scale problems by connecting multiple small quantum processors together to form a larger computing system. Concerning the emerging distributed paradigm, a pivotal challenge lies in crafting specialized network topologies to establish efficient connections among quantum processors while minimizing communication costs. In this paper, we propose a novel DQC topology generation algorithm (DQC-TG) to create optimal and near-optimal network topologies for homogeneous and heterogeneous quantum computers, respectively. Furthermore, for specific quantum circuits requiring diverse communication demands between each pair of qubits, we extend the original algorithm into DQC- TG- Plus to design network topologies tailored for these circuits to further enhance the performance. We perform extensive simulations to evaluate the superiority of the generated network topology designs by our algorithms to baselines.

Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.

Decentralized model training for on-road vehicles offers the potential to harness huge amounts of data at low costs. However, existing approaches usually depend on the existence of a coordinator, tight synchronization, or a connected cluster, all of which can be challenging or infeasible for fast-moving vehicles. In this work, we propose Learning by Chatting (LbChat), a fully decentralized and asynchronous model training approach leveraging coreset-sharing to eliminate the need for a coordinator, tight synchronization, or even a connected cluster. Different from conventional decentralized learning methods, a vehicle not only exchanges its local model but also a coreset, a condensed abstract of its local training data, with opportunistically encountered peers. A vehicle measures its model's performance on a peer's coreset, and a lower performance indicates more different data, thus a more “valuable” model from the peer. Such models are compressed less during exchange to maximize the aggregate gain from each encounter. Extensive evaluations on the driving decision-making task demonstrate that LbChat is strongly competitive with the central server or roadside infrastructure-based approaches (e.g., federated learning). Compared to recent fully decentralized vehicular learning benchmarks, LbChat out-performs them significantly by up to 20% higher driving success rate in the most challenging driving condition, demonstrating the power of insights gained from coresets on peer models' value.

Network Function Virtualization (NFV) is becoming one of the most popular paradigms for providing cost-efficient, flexible, and easily-managed network services by migrating network functions from dedicated hardware to commercial general-purpose servers. Despite the benefits of NFV, it remains a challenge to deploy Service Function Chains (SFCs), placing virtual network functions (VNFs) and routing the corresponding flow between VNFs, in the edge-cloud continuum with the objective of jointly optimizing resource and latency. In this paper, we formulate the SFC Deployment Problem (SFCD). To address this NP-hard problem, we first introduce a constant approximation algorithm for a simplified SFCD limited at the edge, followed by a promotional algorithm for SFCD in the edge-cloud continuum, which also maintains a provable constant approximation ratio. Furthermore, we provide an online algorithm for deploying sequentially-arriving SFCs in the edge-cloud continuum and prove the online algorithm achieves a constant competitive ratio. Extensive simulations demonstrate that on average, the total costs of our offline and online algorithms are around 1.79 and 1.80 times the optimal results, respectively, and significantly smaller than the theoretical bounds. In addition, our proposed algorithms consistently outperform the popular benchmarks, showing the superiority of our algorithms.

Serverless Computing and Function-as-a-Service (FaaS) offer convenient and transparent services to developers and users. The deployment and resource allocation of services are managed by the cloud service providers. Meanwhile, the development of smart mobile devices and network technology enables the collection and transmission of a huge amount of data, which shifts tasks to the network edge for mobile users. In this paper, we propose a deviceless edge computing system targeting the mobility of end users using the data migration of virtual functions. We focus on the adjustment of migration among virtual functions to provide uninterrupted services to mobile users. We introduce the deviceless edge computing model and propose a seamless data migration scheme of virtual functions with limited involvement of function developers. We formulate the migration decision problem into integer linear programming and use receding horizon control (RHC) for online solutions. We implement the migration system to support delay-sensitive scenarios over real edge devices and develop a streaming game as the virtual function to test the performance. Extensive experiments in real scenarios exhibit the system has the ability to support high-mobility and delay-sensitive application scenarios. Extensive simulation results show the applicability of the proposed system over large-scale networks.

With the proliferation of smart devices in recent years, many applications requiring high computing capability and low latency have emerged. Edge computing is one of the promising paradigms to support such applications. Due to the high volatility of edge environments, e.g., frequent movements of mobile devices, varying task sizes, and time-variant channel conditions, we have to make the offloading and resource management decisions on the fly. This paper formulates and studies the problem of online task offloading and resource management in heterogeneous mobile edge environments. The goal of the problem is to minimize the overall system latency. We prove that the problem is NP-hard. Moreover, traditional algorithms needing long decision-making times are insufficient to support applications with high volatility. This paper proposes a deep learning-assisted online algorithm that can make fast decisions. In particular, we design an offline solver for the proposed problem and use a deep neural network to emulate the solver. We conduct extensive simulations to evaluate the proposed approach. Results show that the proposed approach is around$50,000\times$and$500\times$faster than the commercial Gurobi solver for the optimal solution and the proposed offline approximation solver, respectively. Moreover, the overall latency under the proposed approach is near-optimal.

Mobile edge computing has emerged as a prevalent computing paradigm to support applications that demand low latency and high computational capacity. Hardware reconfigurable accelerators exhibit high energy efficiency and low latency compared to general-purpose servers, making them ideal for integration into mobile edge computing systems. This paper investigates the problem of joint task offloading, access point selection, and resource allocation in heterogeneous edge environments for latency minimization. Given the heterogeneity of edge computing devices and the interdependence of the decisions required for offloading, access point selection, and resource allocation, it is challenging to optimize over them simultaneously. We decomposed the proposed problem into two disjoint subproblems and developed algorithms for each of them. The first subproblem is to jointly determine access point selection and communication resource allocation decisions, for which we have proposed an algorithm with a provable approximation ratio of$2.62/(1-8\lambda )$, where$\lambda$is a tunable parameter balancing the approximation ratio and time complexity. Additionally, we offer a faster variant of the algorithm with an approximation ratio of$(\sqrt{3}+1)^{2}$. The second subproblem is to determine offloading and computing resource allocation decisions jointly and is NP-hard, where we developed algorithms based on relaxation and rounding. We conducted comprehensive numerical simulations to evaluate the proposed algorithms, and the results demonstrated that our algorithms outperformed existing baselines and achieved near-optimal performance across various settings.

With the rapid advancement of edge computing and network function virtualization, it is promising to provide flexible and low-latency network services at the edge. However, due to the vulnerability of edge services and the volatility of edge computing system states, i.e., service request rates, failure rates, and resource prices, it is challenging to minimize the online service cost while providing the availability guarantee. This paper considers the problem of online virtual network function backup under availability constraints (OVBAC) for cost minimization in edge environments. We formulate the problem based on the characteristics of the volatility system states derived from real-world data and show the hardness of the formulated problem. We use an online backup deployment scheme named Drift-Plus-Penalty (DPP) with provable near-optimal performance for the AVBAC problem. In particular, DPP needs to solve an integer programming problem at the beginning of each time slot. We propose a dynamic programming-based algorithm that can optimally solve the problem in pseudo-polynomial time. Extensive real-world data-driven simulations demonstrate that DPP significantly outperforms popular baselines used in practice.

Federated learning (FL) enables collaborative model training over distributed computing nodes without sharing their privacy-sensitive raw data. However, in FL, iterative exchanges of model updates between distributed nodes and the cloud server can result in significant communication cost, especially when the data distributions at distributed nodes are imbalanced with requiring more rounds of iterations. In this paper, with our in-depth empirical studies, we disclose that extensive cloud aggregations can be avoided without compromising the learning accuracy if frequent aggregations can be enabled at edge network. To this end, we shed light on the hierarchical federated learning (HFL) framework, where a subset of distributed nodes can play as edge aggregators to support edge aggregations. Under the HFL framework, we formulate a communication cost minimization (CCM) problem to minimize the total communication cost required for model learning with a target accuracy by making decisions on edge aggragator selection and node-edge associations. Inspired by our data-driven insights that the potential of HFL lies in the data distribution at edge aggregators, we propose ShapeFL, i.e., SHaping dAta distRibution at Edge, to transform and solve the CCM problem. In ShapeFL, we divide the original problem into two sub-problems to minimize the per-round communication cost and maximize the data distribution diversity of edge aggregator data, respectively, and devise two light-weight algorithms to solve them accordingly. Extensive experiments are carried out based on several opened datasets and real-world network topologies, and the results demonstrate the efficacy of ShapeFL in terms of both learning accuracy and communication efficiency.

Quantum networks have emerged as a future platform for quantum information exchange and applications, with promising capabilities far beyond traditional communication networks. Remote quantum entanglement is an essential component of a quantum network. How to efficiently design a multi-routing entanglement protocol is a fundamental yet challenging problem. In this paper, we study a quantum entanglement routing problem to simultaneously maximize the number of quantum-user pairs and their expected throughput. Our approach is to formulate the problem as two sequential integer programming problems. We propose efficient entanglement routing algorithms for these two optimization problems and analyze their time complexity and performance bounds. Evaluation results highlight that our approach outperforms existing solutions in both the number of quantum-user pairs served and network throughput.

Mobile edge computing with the near-data processing paradigm can support applications requiring low latency and high computing capability, where energy cost is a significant part of the expenditure. This paper formulates and studies the problem of online joint task offloading and resource allocation for latency minimization subjecting to a time average energy cost constraint in mobile edge computing systems. The formulated problem has four time-variant system states, i.e., data lengths, task sizes, channel conditions, and electricity prices, which are modeled based on real-world data. At the beginning of each time slot, the system has to make five online decisions jointly: base station selection, server selection for task offloading, communication bandwidth allocation, computing resource allocation, and frequency scaling. We prove the offline version of the formulated problem is NP-hard. We design an online algorithm with a provable approximation ratio and low computational complexity for the proposed problem. In particular, it balances energy cost and latency based on the drift-plus-penalty algorithm and makes server and base station selection decisions using a game theoretic-based algorithm. We conduct extensive real-world data-driven simulations to evaluate the proposed algorithm. Simulation results show that the proposed approach outperforms popular baselines.

Distributed learning has been widely adopted to train a global model from local data. However, its performance can be severely affected by stragglers. Recently, some research has been dedicated to resolving the straggler problem by adopting gradient coding, the essence of gradient coding is to solve the straggler problem by adding data redundancy. However, the large amount of data redundancy as well as computation and communication overhead that it brings is still hard to be resolved. Besides, the complexity of the encoding and decoding will increase linearly with the number of the local workers. To this end, in this paper, we design a lightweight coding method in the computing phase and seek to ensure fair transmission in the communication phase. Specifically, to tolerate stragglers in computing phase, we propose a two-stage dynamic coding scheme, part of the workers start computing the partial gradients from the data partitions assigned in the first stage, and the remaining workers for computation in the second stage is decided based on which workers have finished in the first stage. To further tolerate stragglers in the communication phase, a perturbed Lyapunov function is designed to maximize admission data balancing fairness as well as the throughput. The experimental result verifies the derived properties and demonstrates that our proposed solution can achieve a better performance for practical network parameters and benchmark data in terms of accuracy and resource utilization in the distributed learning system.

Generating a long-distance quantum entanglement is one of the most essential functions of a quantum network to support quantum communication and computing applications. The successful entanglement rate during a probabilistic entanglement process decreases dramatically with distance, and swapping is a widely-applied quantum technique to address this issue. Most existing entanglement routing protocols use a classic entanglement-swapping method based on Bell State measurements that can only fuse two successful entanglement links. This paper appeals to a more general and efficient swapping method, namely n-fusion based on Greenberger-Horne-Zeilinger measurements that can fuse n successful entanglement links, to maximize the entanglement rate for multiple quantum-user pairs over a quantum network. We propose efficient entanglement routing algorithms that utilize the properties of n-fusion for quantum networks with general topologies. Evaluation results highlight that our proposed algorithm under n-fusion can greatly improve the network performance compared with existing ones.

Fully decentralized model training for on-road vehicles can leverage crowdsourced data while not depending on central servers, infrastructure or Internet coverage. However, under unreliable wireless communication and short contact duration, model sharing among peer vehicles may suffer severe losses thus fail frequently. To address these challenges, we propose “RoADTrain”, a route-assisted decentralized peer model training approach that carefully chooses vehicles with high chances of successful model sharing. It bounds the per round communication time yet retains model performance under vehicle mobility and unreliable communication. Based on shared route information, a connected cluster of vehicles can estimate and embed the link reliability and contact duration information into the communication topology. We decompose the topology into subgraphs supporting parallel communication, and identify a subset of them with the highest algebraic connectivity that can maximize the speed of the information flow in the cluster with high model sharing successes, thus accelerating model training in the cluster. We conduct extensive evaluation on driving decision making models using the popular CARLA simulator. RoADTrain achieves comparable driving success rates and 1.2–4.5× faster convergence than representative decentralized learning methods that always succeed in model sharing (e.g., SGP), and significantly outperforms other benchmarks that consider losses by 17–27% in the hardest driving conditions. These demonstrate that route sharing enables shrewd selection of vehicles for model sharing, thus better model performance and faster convergence against wireless losses and mobility.

Mobile edge computing is becoming one of the ubiquitous computing paradigms to support applications requiring low latency and high computing capability. FPGA-based reconfigurable accelerators have high energy efficiency and low latency compared to general-purpose servers. Therefore, it is natural to incorporate reconfigurable accelerators in mobile edge computing systems. This paper formulates and studies the problem of joint task offloading, access point selection, and resource allocation in heterogeneous edge environments for latency minimization. Due to the heterogeneity in edge computing devices and the coupling between offloading, access point selection, and resource allocation decisions, it is challenging to optimize over them simultaneously. We decomposed the proposed problem into two disjoint subproblems and developed algorithms for them. The first subproblem is to jointly determine offloading and computing resource allocation decisions and is NP-hard, where we developed an algorithm based on semidefinite relaxation. The second subproblem is to jointly determine access point selection and communication resource allocation decisions, where we proposed an algorithm with a provable approximation ratio of 2.62. We conducted extensive numerical simulations to evaluate the proposed algorithms. Results highlighted that the proposed algorithms outperformed baselines and were near-optimal over a wide range of settings.

Network Function Virtualization (NFV) emerges as a promising paradigm with the potential for cost-efficiency, manage-convenience, and flexibility, where the service function chain (SFC) deployment scheme is a crucial technology. In this paper, we propose an Ant Colony Optimization (ACO) meta-heuristic algorithm for the Online SFC Deployment, called ACO-OSD, with the objectives of jointly minimizing the server operation cost and network latency. As a meta-heuristic algorithm, ACO-OSD performs better than the state-of-art heuristic algorithms, specifically 42.88% lower total cost on average. To reduce the time cost of ACO-OSD, we design two acceleration mechanisms: the Next-Fit (NF) strategy and the many-to-one model between SFC deployment schemes and ant-tours. Besides, for the scenarios requiring real-time decisions, we propose a novel online learning framework based on the ACO-OSD algorithm, called prior-based learning real-time placement (PLRP). It realizes near real-time SFC deployment with the time complexity of O(n), where n is the total number of VNFs of all newly arrived SFCs. It meanwhile maintains a performance advantage with 36.53% lower average total cost than the state-of-art heuristic algorithms. Finally, we perform extensive simulations to demonstrate the outstanding performance of ACO-OSD and PLRP compared with the benchmarks.

Introducing the emerging serverless paradigm into edge computing could avoid over- and under-provisioning of limited edge resources and make complex edge resource management transparent to application developers, which largely facilitates the cost-effectiveness, portability, and short time-to-market of edge applications. However, the computation/data dispersion and device/network heterogeneity of edge environments prevent current serverless computing platforms from acclimating to the network edge. In this paper, we address such challenges by formulating a container placement and data flow routing problem, which fully considers the heterogeneity of edge networks and the overhead of operating serverless platforms on resource-limited edge servers. We design an online algorithm to solve the problem. We further show its local optimum for each arriving container and prove its theoretical guarantee to the optimal offline solution. We also conduct extensive simulations based on practical experiment results to show the advantages of the proposed algorithm over existing baselines.

The trading of social media data has attracted wide research interests over years. In particular, the trading for Web browsing histories, when being applied to targeted advertising, produces tremendous economic value for data consumers. However, the disclosure of entire browsing histories, even in form of anonymous data sets, poses a huge threat to user privacy. Although some existing solutions have investigated privacy-preserving outsourcing of social media data, unfortunately, they neglected the impact on the data consumer’s utility. In this article, we propose CEATSE, a correlated data trading framework for various kinds of private Web browsing histories. CEATSE first models the correlation among multiple dimensional features, and then generates the optimal feature clustering scheme. Combined with this scheme, CEATSE next incorporates a correlated data perturbation strategy on each feature cluster, in order to balance the privacy-utility tradeoff. It then quantifies each chosen data contributor’s privacy loss on optimal feature clusters. Through real-data-based experiments, our analysis and evaluation results demonstrate CEATSE indeed achieves user privacy protection, the data consumer’s accuracy requirement, and truthfulness, individual rationality as well as budget balance.

Data immutability, transparency and decentralization of blockchain make it widely used in various fields, such as Internet of things, finance, energy and healthcare. With the advent of the Big Data era, various companies and organizations urgently need data from other parties for data analysis and mining to provide better services. Therefore, data sharing and data exchange have become an enormous industry. Traditional centralized data platforms face many problems, such as privacy leakage, high transaction costs and lack of interoperability. Introducing blockchain into this field can address these problems, while providing decentralized data storage and exchange, access control, identity authentication and copyright protection. Although many impressive blockchain-based schemes for data sharing or data exchange scenarios have been presented in recent years, there is still a lack of review and summary of work in this area. In this paper, we conduct a detailed survey of blockchain-based data sharing and data exchange platforms, discussing the latest technical architectures and research results in this field. In particular, we first survey the current blockchain-based data sharing solutions and provide a detailed analysis of system architecture, access control, interoperability, and security. We then review blockchain-based data exchange systems and data marketplaces, discussing trading process, monetization, copyright protection and other related topics.

Multi-access Edge Computing has come forth as a promising paradigm to provide low-latency computing service to mobile end users. Its basic idea is to deploy computation resources at the edge of core networks such as wireless access points, and then users can offload their tasks to nearby edge nodes for processing. Plenty of works have well studied the task offloading problem, aiming to reduce task completion delays. Also, a few recent works have focused on task dispatching among edge nodes to balance their workloads and improve resource utilization. In this work, we jointly consider the task offloading and dispatching problem in an edge computing system with interconnected access points. Furthermore, we assume both end devices and access points are rational, which only care about their own benefits. To solve the joint problem, we firstly formulate it as a multi-leader multi-follower Stackelberg game, and rigorously prove the existence of a Stackelberg equilibrium. Then, we propose two algorithms for task offloading and dispatching, respectively. Extensive simulations are conducted to show the superiority of our proposed approach. We also demonstrate that an upper bound with a constant approximation ratio is achieved by our approach.

Mobile edge computing (MEC) can use wireless access network (RAN) to provide users with nearby information technology (IT) services and cloud computing functions, which creates a high-performance and low latency service environment. By caching the popular content at small base station (SBS) can reduce the heavy backhaul load and the content retransmission. However, the time-varying and dynamic of the content requests may lead to the base station to cache the useless contents. In this paper, we study a distributed caching optimization problem in edge networks (ENs) with the spatio-temporal requirements. In the considered ENs, the cache control is described as a stochastic differential game (SDG) in which each SBS defines a caching strategy to reduce the total cost in terms of the service delay and backhaul link load. To reduce the computational complexity, the original optimization problem is transformed into a mean field game (MFG). We propose a distributed caching iterative control algorithm that decouples the information interaction between the general SBS and others through the mean field distribution. In addition, we obtain the optimal edge caching control strategy, while the existence and uniqueness of the mean field equilibrium (MFE) can also be guaranteed. Simulation results demonstrate that our proposed caching control algorithm can average reduce 27.12% storage cost and achieve better performance than other existing schemes.

Innovative edge devices (e.g., smartphones, IoT devices) are becoming much more pervasive in our daily lives. With powerful sensing and computing capabilities, users can generate massive amounts of data. A new business model has emerged where data producers can sell their data to consumers directly to make money. However, how to protect the profit of the data producer from rogue consumers that may resell without authorization remains challenging. In this paper, we propose a smart-contract based protocol to protect the profit of the data producer while allowing consumers to resell the data legitimately. The protocol ensures the revenue is shared with the data producer over authorized reselling, and detects any unauthorized reselling. We also introduce a data relay process that can enhance data accessibility in wireless edge networks. We formulate a revenue sharing problem to maximize the profit of both the data producer and resellers/relayers. We formulate the problem into a two-stage Stackelberg game and determine a ratio to share the reselling revenue between the data producer and resellers/relayers. Extensive simulations show that with resellers and relayers, our mechanism can achieve up to 49.5 percent higher profit for the data producer and resellers/relayers.

Due to the urgent emergence of computation-intensive intelligent applications on end devices, edge computing has been put forward as an extension of cloud computing, to satisfy the low-latency requirements of these applications. To process heterogenous computation tasks on an edge node, the corresponding services should be placed in advance, including installing softwares and caching databases/libraries. Considering the limited storage space and computation resources on the edge node, services should be elaborately selected and deployed on the edge node and its computation resources should be carefully allocated to placed services, according to the arrivals of computation workloads. The joint service placement and computation resource allocation problem is particularly complicated, in terms of considering the stochastic arrivals of tasks, the additional latency incurred by service migration, and the waiting time of unprocessed tasks. Benefiting from deep reinforcement learning, we propose a novel approach based on parameterized deep Q networks to make the joint service placement and computation resource allocation decisions, with the objective of minimizing the total latency of tasks in a long term. Extensive simulations are conducted to evaluate the convergence and performance achieved by our proposed approach.

With the proliferation of versatile mobile applications, offloading compute-intensive tasks to the MEC/Cloud becomes a dramatic technique due to the limited resources and high user experience requirements at mobile devices. However, most existing works design their task offloading schemes without considering the dependence of tasks and the orchestration of the MEC and Cloud, and thus may limit the system performance. In this paper, we propose a dependent task offloading framework for multiple mobile applications, named COFE, where mobile devices can offload their compute-intensive tasks with dependent constraints to the MEC-Cloud system. It can assign the offloaded tasks to the MEC and Cloud adaptively to improve the user experience. Based on COFE, we formulate the task offloading problem as an average makespan minimization problem, which is proved to be NP-hard. Then, we propose a heuristic ranking-based algorithm to assign the offloaded tasks according to their bottom levels. Theoretical analysis proves the stability of the system under the proposed algorithm and extensive simulations validate that the proposed algorithm can significantly reduce the average makespan and deadline violation probabilities of offloaded applications.

Deduplication (redundancy elimination) and cooperative video delivery are two effective ways to save the bandwidth and energy consumption and ensure video collection in damaged networks. However, deduplication in mobile crowd sensing (MSC) is primarily performed on texts and images. Furthermore, most of deduplication technologies require global information and are separated from video routing. To solve such problems, this paper propose a cooperative upload method for sensing videos, which performs the local video deduplication without excessive comparison and feature exchange. Also, we combine the content-aware deduplication with the dynamic relay selection to avoid the propagation of redundant items caused by the content-free video routing. Besides, we integrate a novel mutual-assisted mechanism into our method to motivate relay cooperation and load balance. We formulate the deduplication-supported cooperative video upload as a multi-stage decision problem. To solve the uncertainty of destinations in the decision problem, we develop a stepwise Mutual-Assisted Video Upload Algorithm (MAVU) to schedule video chunks and remove duplicates. Extensive experiments are conducted to compare MAVU with the existing algorithms. The numerical results validate that our MAVU has advantages over the other algorithms in collected video size and upload latency

With the rapid growth of global mobile data traffic, Wi-Fi plays an increasingly important role in expanding network capacity. To overcome the geographical coverage limit of Wi-Fi APs, especially for mobile users, the crowdsourced wireless community network has emerged as a cost-effcient way for providing Internet access services. For instance, it is plausible to share their private residential Wi-Fi APs with each other by designing some tailored incentive/pricing mechanisms. Thus motivated, we propose a distributed pricing and bandwidth allocation scheme to maximize the profit of Wi-Fi providers and provide better Internet services to mobile users. Firstly, we study the stationary networks with incomplete information of users and propose distributed pricing and bandwidth allocation algorithms for single-AP regions and AP group regions, respectively. Then, we generalize the study to dynamic networks and explore distributed pricing based on the statistics of users mobility. Further, we design an online bandwidth allocation algorithm according to the real-time user information. Simulation results demonstrate that the proposed distributed pricing and bandwidth allocation scheme, comparing with the operators pricing scheme, has a better performance on both Wi-Fi APs profit and user experience.

Smart transportation shall address utility waste, traffic congestion, and air pollution problems with least human intervention in future smart cities. To realize the sustainable operation of smart transportation, we leverage solar-harvesting charging stations and rooftops to power electric autonomous vehicles(AVs) solely via design. With a fixed budget, our framework first optimizes the locations of charging stations based on historical spatial-temporal solar energy distribution and usage patterns, achieving $(2+\epsilon)$ factor to the optimal. Then a stochastic algorithm is proposed to update the locations online to adapt to any shift in the distribution. Based on the deployment, a strategy is developed to assign energy requests in order to minimize their traveling distance to stations while not depleting their energy storage. Equipped with extra harvesting capability, we also optimize route planning to achieve a reasonable balance between energy consumed and harvested en-route. As a promising application, utility optimization of shared electric AVs is discussed, and $(2k\!+\!1)$ -approx algorithm is proposed to manage $k$ vehicles simultaneously. Our extensive simulations demonstrate the algorithm can approach the optimal solution within 10-15% approximation error, improve the operating range of vehicles by up to 2-3 times, and improve the utility by more than 50% compared to other competitive strategies.

Internet of Things (IoT) is progressively becoming an essential aspect of daily life that can be sensed anywhere and anytime, transforming the traditional lifestyle into a high-tech one. Numerous applications in the edge are brought to life based on IoT infrastructures. Especially, edge computing has witnessed the proliferation and impact of IoT-enabled devices benefiting from the data collection and computation capabilities of IoT. However, establishing an IoT from scratch can be monetarily expensive, and leasing the existing sub-networks confronts the potentially dishonest behavior of service providers. To address these issues, we propose a novel framework of leasing edge IoT networks and analyze the influence of sub-network owners’ dishonest behavior on the network. We model the interaction between the edge user and the owners of sub-networks by a Stackelberg game with a unique equilibrium, jointly analyzing the pricing and data collection mechanisms. The Primal-dual Decomposition algorithm and its theoretical analyses are provided for the corresponding strategies of the edge user and sub-network owners. Evaluations demonstrate that the proposed algorithm in the leasing model can save data collection cost up to 53% compared with existing data collection strategies, and illustrate the difference in network performance compared with the game without dishonest owners.

The commoditization of private data has become an attractive research topic with the emergence of Big Data era. In this paper, we study the trading of high-dimensional private data with differential privacy guarantee. We proposeCheap, which is a novel Correlated data trading framework for High-dimEnsionAl Private data.Cheapfirst models data correlations among high-dimensional user attributes, and builds an initial attribute clustering scheme. Combined with this scheme,Cheapdevises a novel data perturbation mechanism by solving optimal attribute clustering (OAC) problem, in order to improve data utility of traded data and further generate a privacy-preserving high-dimensional dataset with close joint distribution with the original one. It then quantifies privacy loss based on near-optimal attribute cluster scheme due to the NP-hardness of theOACproblem, and further compensates data owners by running auction in a cost-effective way. We evaluate the performance ofCheaponUserBehaviordataset andObesitydataset, respectively. Our evaluation and analysis demonstrate thatCheapwell balances data utility and privacy protection, and achieves all desired economic properties of budget balance, individual rationality and truthfulness.

Smart contract technologies can be used to implement almost arbitrary business logic. They can revolutionize many businesses such as payments, insurance, and crowdfunding. The resulting birth of decentralized finance (DeFi) has gained significant momentum. Smart contracts and DeFi are now attractive targets for attacks. An important research question is how to protect deployed smart contracts and DeFi. Smart contracts cannot be modified once deployed, namely vulnerabilities cannot be fixed by patching. In this case, vulnerabilities in deployed contracts and DeFi might cause devastating consequences. In this paper, we put forward SolSaviour, a framework for protecting deployed smart contracts and DeFi. The core of SolSaviour is to build a smart contract protection mechanism based on democratic voting using a distributed trusted execution environment (TEE) cluster. Once a vulnerability in deployed contracts or DeFi is found, SolSaviour can destroy the defective contract and redeploy a patched contract via the distributed TEE cluster. Moreover, SolSaviour can migrate funds and state variables from the destroyed contract to the patched one. Compared with previous work, our approach can protect smart contracts and DeFi in a distributed manner, avoiding reliance on privileged users or trusted third parties. Our experiment results show that SolSaviour can protect smart contracts and complex DeFi protocols with feasible overhead.

We investigate a cooperative federated learning framework among devices for mobile edge computing,named (CFLMEC), where devices co-exist in a shared spectrum with interference. Keeping in view the time-average network throughput of cooperative federated learning framework and spectrum scarcity, we focus on maximize the admission data to the edge server or the near devices, which fills the gap of communication resource allocation for devices with federated learning. In CFLMEC,devices can transmit local models to the corresponding devices or the edge server in a relay race manner, and we use a decomposition approach to solve resource optimization problem by considering maximum data rate on sub-channel, channel reuse and wireless resource allocation in which establishes a primal-dual learning framework and batch gradient decent to learn the dynamic network with outdated information and predict the sub-channel condition. With aim at maximizing throughput of devices, we propose communication resource allocation algorithms with and without sufficient sub-channels for strong reliance on edge servers (SRs) in cellular link, and interference aware communication resource allocation algorithm for less reliance on edge servers (LRs) in D2D link. Extensive simulation results demonstrate the CFLMEC can achieve the highest throughput of local devices comparing with existing works, meanwhile limiting the number of the sub-channels.

With the development of 5G, edge computing has raised as a promising technology to satisfy the requirements of computation-intensive and delay-sensitive applications. In this work, we try to propose a task offloading strategy for end users, with considering their individual rationality and collective rationality at the same time. Specially, a user only with individual rationality aims to minimize the completion time of its own task, while a user only with collective rationality aims to minimize the total task completion time achieved by the system. The problem is particularly difficult, as there exist essential conflicts between the individual utility of each user and the collective utility of the system, which cannot be optimized simultaneously. To overcome the difficulties, we first reformulate the problem as a coalition formation game. Then, we propose an iterative algorithm, in which each user can make its task offloading decision in a decentralized way. Additionally, we rigorously prove the properties achieved by our algorithm in terms of stability, optimality, and convergence rate. Extensive simulations are also conducted to validate the performance of our algorithm compared with baselines.

Computation offloading is an effective method to relieve user equipment (UE) from the limited battery capacity and computation resource in mobile edge computing (MEC) networks. However, it is challenging to obtain offloading strategy timely and accurately under diverse computation task requirements and changeable network channel states in multi-user and resource-constrained network environment. In this paper, we consider the network dynamics and UE's resource constraints and aim to minimize the energy consumption of all UEs by jointly optimizing the offloading decision, the central processing unit (CPU) frequency and the power split ratio in a dynamic MEC network. To be specific, we introduce simultaneous wireless information and power transmission (SWIPT) technology in MEC networks to prolong UE's operation time. More importantly, we propose an online computation offloading algorithm based on deep deterministic policy-gradient (DDPG), named Enhanced DDPG (EDDPG), to solve the energy consumption minimization problem. In particular, EDDPG can make real-time decisions without complete network information and adapt to time-varying environments and different requirements. Furthermore, we introduce the priority experience replay technology in EDDPG to accelerate the convergence by using experience tuples. Simulation results show that our proposed algorithm can effectively reduce the energy consumption of UEs and enable them complete more computing tasks within the time limit. Compared with other baseline methods, it can accelerate the convergence and improve the system performance effectively.

Next-generation wireless technology and machine-to-machine technology can provide the ability to connect and share data at any time among IoT smart devices. However, the traditional centralized data sharing/trading mechanism lacks trust guarantee and cannot satisfy the real-time requirement. Distributed systems, especially blockchain, provide us with promising solutions. In this paper, we propose a blockchain based non-repudiation scheme for IoT data trading to resolve the credibility and real-time limits. The proposed scheme has two parts, i.e., a trading scheme and an arbitration scheme. The trading scheme employs a divide-and-conquer method and two commitment methods to support efficient IoT data trading, which runs in a two-round manner. The arbitration scheme first leverages a smart contract to solve disputes on-chain in real time. In case of on-chain arbitration dissatisfaction, the arbitration scheme also employs an off-line arbitration to make a final resolution. Short-term and long-term analysis show that the proposed scheme enforces non-repudiation among the data trading parties and runs efficiently for rational data owners and buyers. We implemented the proposed scheme. Experimental results confirm that the proposed scheme has an orders-of-magnitude performance speedup than the state-of-the-art scheme.

Caching popular contents at the network edge is promising to reduce the retrieval latency, the network congestion, and the number of requests to the remote content provider during peak hours. In general, edge caching resource is costly and highly limited. Nevertheless, it is possible to provide cost-effective caching services using unreliable resources, which are resources reserved for other applications but have not been fully used or resources on vulnerable servers. In this paper, we consider the problem of caching popular contents over unreliable resources as a less expensive solution to limited edge caching capacity. In particular, to address the unreliability of edge resources, erasure coding is leveraged to increase the availability of cached contents. We formulate the problem as a discrete optimization problem and prove it is NP-hard. We start with two special cases of the problem and provide optimal algorithms for them. We then design an algorithm for the general version of the proposed problem and provide a provable performance guarantee. Real-world data-driven simulations demonstrate that the proposed algorithms significantly outperform popular baselines, and the rewards for the general version of the problem are near-optimal.

Network Function Virtualization (NFV) migrates network functions from proprietary hardware to commercial servers on the edge or cloud, making network services more cost-efficient, manage-convenient, and flexible. To facilitate these advantages, it is critical to find an optimal deployment of the chained virtual network functions, i.e. service function chains (SFCs), in hybrid edge-and-cloud environment, considering both resource and latency. It is an NP-hard problem. In this paper, we first limit the problem at the edge and design a constant approximation algorithm named chained next fit (CNF), where a sub-algorithm called double spanning tree (DST) is designed to deal with virtual network embedding. Then we take both cloud and edge resources into consideration and create a promotional algorithm called decreasing sorted, chained next fit (DCNF), which also has a provable constant approximation ratio. The simulation results demonstrate that the ratio between DCNF and the optimal solution is much smaller than the theoretical bound, approaching an average of 1.25. Moreover, DCNF always has a better performance than the benchmarks, which implies that it is a good candidate for joint resource and latency optimization in hybrid edge-and-cloud networks.

Network Function Virtualization (NFV) has the potential of cost-efficiency, manage-convenience, and flexibility but meanwhile poses challenges for the service function chain (SFC) deployment problem, which is NP-hard. It is so complicated that existing work conspicuously neglects the flow changes along the chains and only gives heuristic algorithms without a performance guarantee. In this paper, we fill this gap by formulating a traffic-sensitive online joint SFC placement and flow routing (TO-JPR) model and proposing a novel two-stage scheme to solve it. Moreover, we design a dynamic segmental packing (DSP) algorithm for the first stage, which not only maintains the minimal traffic burden for the network but also achieves an approximation ratio of 2 on the resource cost. Such a two-stage scheme and DSP can pave the way for efficiently solving TO-JPR. For example, simply applying the nearest neighbor (NN) algorithm for the second stage can guarantee a global approximation ratio of O(log(M)) on the network latency, where M is the number of servers. More future work can be done based on our scheme to get better performance on the network latency. Finally, we perform extensive simulations to demonstrate the outstanding performance of DSP+NN compared with the optimal solutions and benchmarks.

The fast development of mobile edge computing (MEC) and service virtualization brings new opportunities to the deployment of interactive applications, e.g., VR education, stream gaming, autopilot assistance, at the network edge for better performance. Ensuring quality of experience (QoE) for such services often requires the satisfaction of multiple quality of service (QoS) factors, e.g., short delay, high throughput rate, low packet loss. Nevertheless, existing mobile edge networks often fail to meet these requirements due to the mobility of end users and the volatility of network conditions. In this paper, we propose a novel scheme that both reduces delay and adjusts data throughput rate for QoE enhancement. We design an online service placement and throughput rate adjustment (SPTA) algorithm which coordinately migrates virtual services while tuning their data throughput rates based on real-time bandwidth fluctuation. By implementing a small-scale prototype supporting stream gaming at the edge, we show the necessity and feasibility of our work. Based on data from the experiments, we conduct real-world trace driven simulations to further demonstrate the advantages of our scheme over existing baselines.

Quantum networks are considered as a promising future platform for quantum information exchange and quantum applications, which have capabilities far beyond the traditional communication networks. Remote quantum entanglement is an essential component of a quantum network. How to efficiently design a multi-routing entanglement protocol is a fundamental yet challenging problem. In this paper, we study a quantum entanglement routing problem to simultaneously maximize the number of quantum-user pairs and their expected throughput. Our approach is to formulate the problem as two sequential integer programming steps. We propose efficient entanglement routing algorithms for the two integer programming steps and analyze their time complexity and performance bounds. Results of evaluation highlight that our approach outperforms existing solutions in both served quantum-user pairs numbers and the network expected throughput.

Edge computing has been widely used in recent years for bringing services closer to end users, resulting in faster response for applications. However, the sensitive information that leaves the data owner is at risk of being disclosed because the service provider is generally honest-but-curious. Federated learning (FL) is a popular method for preserving privacy by transferring the model from the edge node to local devices and training on the local data set. Nonetheless, the training parameter that communicates between local mobile devices and the edge node may contain the original data and be guessed by adversaries. In order to address the privacy threats, we propose the PL-FedIPEC scheme in this article, which is a privacy-preserving and low-latency FL method that transmits parameters encrypted with the improved Paillier, a homomorphic encryption algorithm, to protect the privacy of end devices without transmitting data to the edge node. Our method introduces the improved Paillier encryption, which brings a new hyperparameter and previously computes multiple random intermediate values in the key generation phase so that the time for the encryption phase has a significant reduction. With this new algorithm, the time for model training is decreased, and the sensitive information is in ciphertext format and cannot be analyzed. To evaluate the efficiency of our proposed scheme, we conduct extensive experiments and the results validate and demonstrate that our scheme with the improved Paillier algorithm can achieve the same accuracy as the original Paillier algorithm and the baseline FedAVG algorithm. At the same time, our method can save a massive amount of time when training the learning model with various settings.

The applications of Internet of Things have emerged in every aspect of people’s life. The volume of data gathered can be enormous. Enterprises and personal consumers are increasingly reliant on cloud storage services instead of local storage. While they enjoy the convenience of cloud storage services, they also worry about the integrity of the cloud-stored data since they do not physically own the data. To enable public integrity auditing, third-party auditors as trusted ones verify data integrity on behalf of the data owner. However, the vulnerability of auditors should also be considered. We propose a consortium blockchain-based public integrity verification system (CBPIV). In CBPIV, the auditor behaviors are recorded in the consortium blockchain so that authorized parties can audit the auditor to see if the verification results are correct. A smart contract is deployed to check the behavior of the auditor automatically, which can trigger alerts for unusual behaviors. The evaluation on both security and performance shows that our proposed scheme is secure and alleviates the burden on data owners of limited computation capability.

Edge computing is becoming pervasive in our daily lives with emerging smart devices and the development of communication technology. Resource-rich smart devices and high-density supportive networks make data transactions prevalent over edge environments. To ensure such transactions are unmodifiable and undeniable, blockchain technology is introduced into edge environments. In this paper, we propose a hybrid blockchain system to enhance the security for transactions and determine the incentive for miners in edge computing environments. We propose a Proof of Work (PoW) and Proof of Stake (PoS) hybrid consensus blockchain system utilizing the heterogeneity of devices to adapt to the characteristic of edge environments. We raise the incentive assignment problem for a fair incentive to PoW miners. We formulate the problem and propose an iterative and another heuristic algorithm to determine the incentive that the miner will receive for a new block. We further prove that the iterative algorithm can obtain global optimal results. Numerical simulation results show that our proposed algorithm can give a reasonable incentive to miners under different system parameters in edge blockchain systems.

The emerging network function virtualization is migrating traditional middleboxes, e.g., firewalls, load balancers, proxies, from dedicated hardware to virtual network functions (VNFs) running on commercial servers defined as network points of presence (N-PoPs). VNFs further chain up for more complex network services called service function chains (SFCs). SFCs introduce new flexibility and scalability which greatly reduce expenses and rolling out time of network services. However, chasing the lowest cost may lead to congestion on popular N-PoPs and links, thus resulting in performance degradation or violation of service-level agreements. To address this problem, we propose a novel scheme that reduces the operating cost and controls network congestion at the same time. It does so by placing VNFs and routing flows among them jointly. Given the problem is NP-hard, we design an approximation algorithm named candidate path selection (CPS) with a theoretical performance guarantee. We then consider cases when SFC demands fluctuate frequently. We propose an online candidate path selection (OCPS) algorithm to handle such cases considering the VNF migration cost. OCPS is designed to preserve good performance under various migration costs and prediction errors. Extensive simulation results highlight that CPS and OCPS algorithms perform better than baselines and comparably to the optimal solution.

Blockchain protocols require nodes to verify all received transactions before forwarding them. However, massive spam transactions cause the participants in blockchain systems to consume many resources in verifying and propagating transactions. This paper proposes a reputation-based mechanism to increase the efficiency of processing transactions by considering the reputations of the sending nodes. Reputations are in turn adjusted based on the quality of transaction processing. Our proposed reputation-based mechanism offers three main contributions. First, we modify the verification strategy so that nodes set a probability of verifying a received transaction considering the likelihood of it being spam: transactions from a node with a low reputation have a high probability of being verified. Second, we optimize the transaction forwarding protocol to reduce propagation delay by prioritizing forwarding transactions to reputable receivers. Third, we design a data request protocol that provides alternative data exchange methods for nodes with different reputations. A series of simulations demonstrate the performance of our reputation-based mechanism.

Multi-armed bandits problem has been widely utilized in economy-related areas. Incentives are explored in the sharing economy to inspire users for better resource allocation. Previous works build a budget-feasible incentive mechanism to learn users’ cost distribution. However, they only consider a special case that all tasks are considered as the same. The general problem asks for finding a solution when the cost for different tasks varies. In this paper, we investigate this problem by considering a system with$k$levels of difficulty. We present two incentivizing strategies for offline and online implementation, and formally derive the ratio of utility between them in different scenarios. We propose a regret-minimizing mechanism to decide incentives by dynamically adjusting budget assignment and learning from users’ cost distributions. We further extend the problem to a more generalized k-MAB problem by removing the contextual information of difficulties. CUE-UCB algorithm is proposed to address the online advertisement problem for multi-platforms. Our experiment demonstrates utility improvement about 7 times and time saving of 54% to meet a utility objective compared to the previous works in sharing economy, and up to 175% increment of utility for online advertising.

Software defined networking (SDN) with separated control plane and data plane brings new opportunities for traffic measurement in data center networks. However, in the SDN-enabled switches, available TCAM (Ternary Content Addressable Memory) resources for traffic measurement are limited. Thus, it is necessary to utilize traffic matrix (TM) estimation to derive a hybrid network monitoring scheme through combining the partial direct measurement offered by SDN with some inference techniques. Although large size flows play an important role in improving TM estimation accuracy, directly monitoring each flow and finding out large size flows consume massive channel bandwidth resource between control plane and data plane. Therefore, in this paper, we identify large size flows from multiple historical TMs instead of monitoring each flow. First, we analyze multiple historical TMs and observe that origin-to-destination (OD) pair whose flow size is selected as large size flow at last time slot is most likely to be selected for per-flow monitoring at next time slot, so these OD pairs are identified by gradient boosting machine and are directly regarded as sampled OD pairs in order to reduce resource consumption. Then, we propose a greedy heuristic algorithm to solve SDN-enabled switch selection problem to best utilize the TCAM resources and guarantee that most of sampled OD pairs are measured in the flow table. We also present a source node prefix tree based bit merging aggregation (SPTBMA) scheme to design feasible forwarding rules to be inserted in TCAM of SDN-enabled switches and reserve more TCAM space for sampled OD pairs. Finally, the experimental results based on real traffic dataset demonstrate that our proposed scheme outperforms the existing algorithms in terms of improving TM estimation accuracy and overcoming limitation of TCAM resources.

With the prosperity of cloud computing and video services, the demand for network resources has increased dramatically, leading to the remarkable growth in the amount of network energy consumption, a key factor restricting the development of data centers. Numerous existing works reduce network energy consumption by optimizing data transmission, but they ignore the energy consumption for data transmission preparation, such as activating devices and installing rules. In this paper, we jointly optimize device activation, rule installation and data transmission to minimize network energy consumption. Specifically, we first formulate the minimization problem of the energy consumption of device activation, rule installation, and data transmission. We then prove that it is NP-complete to get the optimal solution of the minimization problem, furthermore, we propose a heuristic algorithm to plan the path with minimum network energy consumption for each flow. The simulation results show that the energy consumption of our algorithm is close to the optimal solution solved by Gurobi, and our algorithm has lower complexity. Compared with the state-of-the-art algorithm, our algorithm always consumes less energy and has shorter flow completion time.

Design an optimization model for task management among Mobile Terminal (MT), Macro cell Base Station (MBS), and multiple Small cell Base Stations (SBS) for the large-scale Mobile Edge Computing (MEC) system, is a challenging issue due to the large number of tasks and SBSs. Inspired by this, we propose a Parallel Optimal Task Allocation Mechanism (POTAM) framework for MEC, which includes Device to Device (D2D)-enabled computing, MBS computing and Edge Computation Resource Distribution (ECRD) computing. In POTAM, we exploit a parallel multi-block Alternating Direction Method of Multipliers (ADMM) based method to model both requirements of delay and energy consumptions, which formulates the task allocation under these requirements as a nonlinear 0–1 integer programming problem. To solve this problem, we develop an efficient combination of conjugate gradient, Newton and linear search techniques based algorithm with Logarithmic Smoothing and Cyclic Block coordinate Gradient Projection (CBGP) methods, which can guarantee convergence and reduce computational complexity with a good scalability. In order to allocate task cooperatively, an optimal approach is proposed, ECRD-A, which is used to find the shortest path among each node. Numerical results demonstrate the effectiveness of the POTAM and it can effectively reduce delay and energy consumption for a large-scale MEC system.

Edge devices with sensing, storage, and communication resources are penetrating our daily lives. These resources make it possible for edge devices to conduct data transactions (e.g., micro-payments, micro-access control). The blockchain technology can be used to ensure transaction unmodifiable and undeniable. In this paper, we propose a blockchain system that adapts to the limitations of edge devices. The new blockchain system can fairly and efficiently allocate storage resources on edge devices, which makes it scalable. We find the optimal peer nodes for transaction data storage and propose a recent block storage allocation scheme for quick retrieval of missing blocks. We develop data migration algorithms to dynamically reallocate data and block storage to adapt topology changes in the network. The proposed blockchain system can also reach consensus with low energy consumption in edge devices with a new Proof of Stake mechanism. Extensive simulations show that our proposed blockchain system works efficiently in edge environments. On average, the new system uses 18.4 percent less time and consumes 87 percent less battery power when compared with traditional blockchain systems.

Due to the explosion of mobile devices and the evolution of wireless communication technologies, novel applications with intensive computation demands and low-latency requirements have arisen. Edge computing has been proposed as an extension of cloud computing, which moves computation workloads from remote cloud to network edge. Cooperating edge computing and cloud computing can significantly reduce the latency of computation tasks. However, considering the heterogeneity and stochastic arrivals of tasks and the limited computation and communication resources on the edge, task offloading and resource allocation are two joint crucial problems in an edge-cloud orchestrated computing system. In this paper, we propose an online task offloading and resource allocation approach for edge-cloud orchestrated computing, with the aim to minimize the average latency of tasks over time. We first build system models to analyze the latency and energy consumption incurred under different computing modes and formally formulate the joint problem as a mixed-integer optimal decision problem. Then, we employ Lyapunov optimization and duality theory to decompose the problem into a set of subproblems, which can be solved in a semi-decentralized way. We also formally analyze that our approach can achieve near-optimal performance. Extensive simulations are conducted to verify the superiority of our approach.

Emerging virtual network functions (VNFs) bring new opportunities to network services on the edge within customers’ premises. Network services are realized by chained up VNFs, which are called service function chains (SFCs). These services are deployed on commercial edge servers for higher flexibility and scalability. Despite such promises, it is still unclear how to provide highly available and cost-effective SFCs under edge resource limitations and time-varying VNF failures. In this paper, we propose a novel Reliability-aware Adaptive Deployment scheme named RAD to efficiently place and back up SFCs over both the edge and the cloud. Specifically, RAD first deploys SFCs to fully utilize edge resources. It then uses both static backups and dynamic ones created on the fly to guarantee the availability under the resource limitation of edge networks. RAD does not assume failure rates of VNFs but instead strives to find the sweet spot between the desired availability of SFCs and the backup cost. Theoretical performance bounds, extensive simulations, and small-scale experiments highlight that RAD provides significantly higher availability with lower backup costs compared with existing baselines.

Wireless data collection requires a sequence of resource provisioning decisions due to the limited battery capacity of wireless sensors. The corresponding online resource provisioning problem is challenging. Recently, many prediction methods have been proposed that can be used to benefit the performance of various systems through their incorporation. Therefore, in this article, we focus on online resource provisioning problems with short-term predictions motivated by the wireless data collection problem. Specifically, we design separate online algorithms for systems in which the state evolves in either a stationary manner or an arbitrarily determined manner and prove their performance bounds where their bounds improve as the amount of available predictions increases. Additionally, we design a meta-algorithm that can choose which online algorithm to implement at each point in time, depending on the recent behavior of the system environment. The practical performances of the proposed algorithms are corroborated in trace-driven numerical simulations of data collection of shared bikes. Additionally, we show that the performance of our meta-algorithm in various system environments can be better than that of the single best algorithm chosen in hindsight.

With the commoditization of private data, data trading in consideration of user privacy protection has become a fascinating research topic. The trading for private web browsing histories brings huge economic value to data consumers when leveraged by targeted advertising. And the online pricing of these private data further helps achieve more realistic data trading. In this paper, we study the trading and pricing of multiple correlated queries on private web browsing history data at the same time. We propose CTRADE, which is a novel online data CommodiTization fRamework for trAding multiple correlateD queriEs over private data. CTRADE first devises a modified matrix mechanism to perturb query answers. It especially quantifies privacy loss under the relaxation of classical differential privacy and a newly devised mechanism with relaxed matrix sensitivity, and further compensates data owners for their diverse privacy losses in a satisfying manner. CTRADE then proposes an ellipsoid-based query pricing mechanism according to a given linear market value model, which exploits the features of the ellipsoid to explore and exploit the close-optimal dynamic price at each round. In particular, the proposed mechanism produces a low cumulative regret, which is quadratic in the dimension of the feature vector and logarithmic in the number of total rounds. Through real-data based experiments, our analysis and evaluation results demonstrate that CTRADE balances total error and privacy preferences well within acceptable running time, indeed produces a convergent cumulative regret with more rounds, and also achieves all desired economic properties of budget balance, individual rationality, and truthfulness.

Cloud storage synchronization among different computing terminals has attracted large-scale uses among enterprise and individual users. It enables users to maintain the same copy of data in real time, which eases users the tedious yet error-prone data management burden. However, existing cloud storage synchronization systems are in a closed form. Users are fixed to a certain cloud service provider, which makes it hard to transfer from one provider to another when balancing factors such as performance, cost, security, etc. To bridge this gap, this article proposes a new synchronization system based on standard cloudobjectstorage. Specifically, we first formulate the cloud object storage synchronization problem by defining some useful concepts. We then use the idea of state encoding and a push-pull paradigm to propose a cloud object storage synchronization system. The proposed system supports real-time, multiple-terminal, and cloud-independent storage synchronization. We also prototyped the proposed system. The experimental results show that the proposed system is promising for practical usages.

The security of HTTPS fundamentally relies on SSL/TLS certificates issued by Certificate Authorities (CAs), which, however, are vulnerable to be compromised to issue unauthorized certificates (i.e., certificates issued without domains’ permission). Current countermeasures such as Certificate Transparency (CT) can only detect unauthorized certificates rather than preventing them. In this article, we presentPistis, a framework for issuing authorized and trusted certificates with the distributed ledger and Trusted Execution Environment (TEE) technology. InPistis, TEE nodes validate whether the domain in a requested certificate passes the domain ownership validation (i.e., under corresponding applicants’ control) and submit attested results to a smart contract in the distributed ledger. The smart contract issues a certificate to the applicant when an attested result shows a pass. Therefore,Pistiscan ensure its issued certificates are authorized due to the domain ownership validation mechanism in the TEE. Furthermore, as the issued certificates are stored in a Merkle Patricia Tree (MPT) inPistis, they are trusted and can be verified by a normal user easily. The security ofPistisis formally proved in the Universally Composable (UC) framework. Compared with state-of-the-art,Pistisavoids potential damages by preventing unauthorized certificates from issuing.

Despite increasingly emerging applications, a primary concern for blockchain to be fully practical is the inefficiency of data query. Direct queries on the blockchain take much time by searching every block, while indirect queries on a blockchain database greatly degrade the authenticity of query results. To conquer the authenticity problem, we propose a Verifiable Query Layer (VQL) that can be deployed in the cloud to provide both efficient and verifiable data query services for blockchain systems. The middleware layer extracts data from the underlying blockchain system and efficiently reorganizes them in databases. To prevent falsified data from being stored in the middleware, a cryptographic fingerprint is calculated based on each constructed database. The database fingerprint will be first verified by miners and then written into the blockchain. Moreover, public users can verify the entire databases or several databases that interest them in the middleware layer. We implement VQL together with the verification schemes and conduct extensive experiments based on a practical blockchain system. The evaluation results demonstrate that VQL can efficiently support various data query services and guarantee the authenticity of query results for blockchain systems.

Edge computing has been an efficient way to provide prompt and near-data computing services for resource-and-delay sensitive IoT applications via computation offloading. Effective computation offloading strategies need to comprehensively cope with several major issues, including 1) the allocation of dynamic communication and computational resources, 2) delay constraints of heterogeneous tasks, and 3) requirements for computationally inexpensive and distributed algorithms. However, most of the existing works mainly focus on part of these issues, which would not suffice to achieve expected performance in complex and practical scenarios. To tackle this challenge, in this paper, we systematically study a distributed computation offloading problem with delay constraints, where heterogeneous computational tasks require continually offloading to a set of edge servers via a limiting number of stochastic communication channels. The task offloading problem is formulated as a delay-constrained long-term stochastic optimization problem under unknown prior statistical knowledge. To solve this problem, we first provide a technical path to transform and decompose it into several slot-level sub-problems. Then, we devise a distributed online algorithm, namely TODG, to efficiently allocate resources and schedule offloading tasks. Further, we present a comprehensive analysis for TODG in terms of the optimality gap, the worst-case delay, and the impact of system parameters. Extensive simulation results demonstrate the effectiveness and efficiency of TODG.

This paper considers a federated temporal difference() (TD()) learning algorithm and provides both asymptotic and finite-time analyses. To protect each worker agent cost information from being accessed by possible attackers, we propose a privacy-preserving variant of the algorithm by adding perturbation to the exchanged information. We show the rigorous differential privacy guarantee by using moments accountant and derive an upper bound of the utility loss for the privacy-preserving algorithm. Evaluations are also provided to corroborate the efficiency of the algorithms.

How to serve mobile users in rural areas by 5G networks is challenging due to the sparse distribution of base stations and poor connection to the cloud. Existing solutions focus on transmission frequency implementation such as frequency multiplexing, In this paper, we consider a decentralized caching scheme for two reasons. First, caching contents in the edge is an effective approach to reduce the transmission latency and improve the quality of service for mobile users. Second, the decentralized caching allows base stations to serve mobile users without any coordination of the cloud. Meanwhile, data privacy in the edge is critical for individual users. This paper aims to jointly determine the caching and routing policy in rural areas of 5G networks in a decentralized manner and simultaneously design a proper privacy-preserving mechanism. We tackle the challenges in two progressive steps. First, we design a decentralized algorithm with the convergence guarantee. Furthermore, we enhance the developed decentralized algorithm with a privacy-preserving mechanism based on (local) differential privacy and prove its privacy guarantee. We conduct extensive numerical simulations based on real-world traces to evaluate the proposed algorithms. Results highlight significant performance improvements compared to existing baselines.

In order to solve the problem of flow scheduling in cluster computing framework, the scheduling strategy based on coflow has become a research hot spot. A coflow is a collection of data flows between two different stages of the same parallel computing task. Coflow scheduling in the case of unknown prior information depends on the data flow information of the sent part to infer the data size of coflow and allocate the scheduling sequence for coflow, which is easy to cause congestion. In this paper, we design an effective coflow scheduling mechanism namely, Classification According to Ports Number (CAPN). In the mechanism, firstly, coflows are quickly classified according to the Few Ports Number Scheduling First (FPSF) algorithm, and then coflows with different priorities are scheduled and adjusted, which greatly reduce the average coflow completion time (CCT). Simulation results show that compared with the classical Aalo and MCS mechanisms, our CAPN mechanism can reduce the completion time of coflow by by 31.32% and 25.72%, respectively.

Federated learning (FL) can enable distributed model training over mobile nodes without sharing privacy-sensitive raw data. However, to achieve efficient FL, one significant challenge is the prohibitive communication overhead to commit model updates since frequent cloud model aggregations are usually required to reach a target accuracy, especially when the data distributions at mobile nodes are imbalanced. With pilot experiments, it is verified that frequent cloud model aggregations can be avoided without performance degradation if model aggregations can be conducted at edge. To this end, we shed light on the hierarchical federated learning (HFL) framework, where a subset of distributed nodes are selected as edge aggregators to conduct edge aggregations. Particularly, under the HFL framework, we formulate a communication cost minimization (CCM) problem to minimize the communication cost raised by edge/cloud aggregations with making decisions on edge aggregator selection and distributed node association. Inspired by the insight that the potential of HFL lies in the data distribution at edge aggregators, we propose SHARE, i.e., SHaping dAta distRibution at Edge, to transform and solve the CCM problem. In SHARE, we divide the original problem into two sub-problems to minimize the per-round communication cost and mean Kullback-Leibler divergence of edge aggregator data, and devise two light-weight algorithms to solve them, respectively. Extensive experiments under various settings are carried out to corroborate the efficacy of SHARE.

Network Functions Virtualisation (NFV) has a magnificent prospect due to its cost-efficiency, manage-convenience, and flexibility. To promote these advantages, the placement of virtual network functions (VNFs) is a key technology. In this paper, we focus on minimizing the total resources of used commercial servers to provide an optimal VNF placement scheme in edge networks. As for the NP-hard problem, we first design a Largest Fit Decreasing algorithm (LFD) with a provable constant approximation ratio of 2 and the computational complexity of$O(N^{2})$, where N is the number of VNFs. Besides, we improve it and further produce the Judge and Repeated Largest Fit Decreasing algorithm (JR-LFD), which has a bit larger computational complexity$O(kN^{2})$, but a smaller asymptotic approximation ratio of$\frac{3}{2}$, where k is the number of different server sizes. The simulation results demonstrate that the used resources derived by JR-LFD are always smaller than those by LFD. They both are extremely close to the optimal results and much smaller than the benchmark, which implies they improve the network resource utilization dramatically.

Cloud computing is becoming one of the ubiquitous computing paradigms for enterprises and organizations in recent years. Due to the volatility of system states such as cloud resource price and workload demand, it is challenging to provision cloud resources efficiently. This paper studies online cloud resource provisioning problems under cost budget where no accurate or distributional future information is available. We develop an algorithmic framework and design online algorithms based on the framework. We prove the competitive ratio of the proposed algorithms. We further show the proposed algorithms have better performance than a prominent existing algorithm named CR-Pursuit. While prior works on the problem require the objective functions to be concave, the proposed algorithms work for non-convex and non-concave objective functions. We conduct real-world trace-driven simulations. Results highlight the proposed algorithms outperform baselines significantly over a wide range of settings.

For a blockchain system, the network layer is of great importance for scalability and security. The critical task of blockchain networks is to provide a fast delivery of data. A rapid spread accelerates the transactions to be included into blocks and then confirmed. Existing blockchain systems, especially the cryptocurrencies like Bitcoin, take a simple strategy that requires relay nodes to verify all received transactions and then forward valid ones to all outbound neighbors. Unfortunately, this design is inefficient and slows down the transmission of transactions. In this paper, we introduce the concept of reputation and propose a novel relay protocol, RepuLay, to accelerate the transmission of transactions across the network. First of all, we design a reputation mechanism to help each node identify the unreliable and inactive neighbors. In this mechanism, two values are used to define one’s reputation. Each node keeps a local list of reputations of all its neighbors. Based on the reputation mechanism, RepuLay adopts probabilistic strategies to process transactions. More specifically, after receiving a transaction, the relay node verifies it with a certain probability, which is deduced from the first value of sender’s reputation. Next, the valid and unverified transactions are forwarded to some neighbors. Each neighbor has some probability to be chosen as a receiver and the probability is determined by its second value of reputation. Theoretically, we prove that our design can guarantee the quality of relayed transactions. Further simulation results confirm that RepuLay effectively accelerates the spread of transactions and optimize the usage of nodes’ bandwidths.

Edge computing guides the collaborative work of widely distributed nodes with different sensing, storage, and computing resources. For example, sensor nodes collect data and then store it in storage nodes so that computing nodes can access the data when needed. In this paper, we focus on the quality of service (QoS) in storage allocation in edge networks. We design a reputation mechanism for nodes in edge networks, which enables interactive nodes to evaluate the quality of service for reference. Each node publicly broadcasts a personal reputation list to evaluate all other nodes, and each node can calculate the global reputation of all nodes by aggregating personal reputations. We then propose a storage allocation algorithm that stores data to appropriate locations. The algorithm considers fairness, efficiency, and reliability which is derived from reputations. We build a novel Proof-of-Reputation (PoR) blockchain to support consensus on the reputation mechanism and storage allocation. The PoR blockchain ensures safety performance, saves computing resources, and avoids centralization. Extensive simulation results show our proposed algorithm is fair, efficient, and reliable. The results also show that in the presence of attackers, the success rate of honest nodes accessing data can reach 99.9%.

With the explosion of mobile smart devices, many computation intensive applications have emerged, such as interactive gaming and augmented reality. Mobile-edge computing (EC) is put forward, as an extension of cloud computing, to meet the low-latency requirements of the applications. In this article, we consider an EC system built in an ultradense network with numerous base stations. Heterogeneous computation tasks are successively generated on a smart device moving in the network. An optimal task offloading strategy, as well as optimal CPU frequency and transmit power scheduling, is desired by the device user to minimize both task completion latency and energy consumption in a long term. However, due to the stochastic task generation and dynamic network conditions, the problem is particularly difficult to solve. Inspired by reinforcement learning, we transform the problem into a Markov decision process. Then, we propose an attention-based double deep Q network (DDQN) approach, in which two neural networks are employed to estimate the cumulative latency and energy rewards achieved by each action. Moreover, a context-aware attention mechanism is designed to adaptively assign different weights to the values of each action. We also conduct extensive simulations to compare the performance of our proposed approach with several heuristic and DDQN-based baselines.

The 5G heterogeneous network architecture integrates different radio access technologies (RATs), which will support the large-scale communication connection of massive Internet-of-Things (IoT) devices. However, as the rapid growth of IoT connections, personalized requirements of services requested and heterogeneity deepening of the network system, how to design an intelligent network selection scheme for user devices (UDs) is becoming a crucial challenge in the 5G heterogeneous network system. Most of the existing network selection methods only optimize the selection strategies from the user side or network side, which results in heavy network congestion, poor user experience, and system performance degradation. Accordingly, we propose a multiagent$Q$-learning network selection (MAQNS) algorithm based on Nash$Q$-learning, which can learn a joint optimal selection strategy to improve system throughput and reduce user blocking on the premise of ensuring the requirements of IoT services. In particular, we apply the discrete-time Markov chains to model the network selection, and the analytic hierarchy process (AHP) and gray relation analysis (GRA) are jointly utilized to obtain user preferences for each network. Finally, performance evaluation demonstrates that comparing to the existing schemes, MAQNS proposed cannot only improve system throughput and reduce user blocking but also promote user experience on average energy efficiency and delay.

Mobile-edge computing (MEC) is considered as a promising technology in 5G, as it can solve the contradiction between the explosive growth of computation-intensive tasks and the limited computation power and battery life of local devices. However, in the 5G environment, most of the existing studies on task offloading in MEC have either failed to study the compatible multiple access technologies or have not considered the hierarchical relationship between small cell base station (SBS) and macro base station (MBS). Therefore, to explore the MEC offloading problem under the unique 5G architecture is of great significance at present. In light of this, we study the task offloading strategy in the nonorthogonal multiple access (NOMA)-enabled small cell MEC network. Specifically, we first describe a noval small cell MEC architecture in which MBS and SBS are both deployed with edge servers and there is a hierarchical relationship between the two. Based on this architecture, we have established the communication model and computation model, respectively. Then, we formulate the energy and delay weighted sum minimization problem, which aims at minimizing the total cost of task offloading under different requirements and takes into account the constraints of computation capabilities. To solve the problem, we develop a hybrid genetic hill climbing (HGHC) algorithm that can quickly find the optimal solution. Moreover, we perform a lot of simulation experiments to evaluate the performance of our algorithm under different parameters. The experimental results show that our algorithm can converge within about 20 iterations, which is superior to traditional heuristic algorithms.

We consider the problem of the intelligent and efficient resource management framework in mobile-edge computing (MEC), which can reduce delay and energy consumption, and features distributed optimization and efficient congestion avoidance. In this article, we present a cooperative learning framework for resource management in MEC from an alternating direction method of multipliers (ADMMs) perspective, named the CL-ADMM framework. First, computing a task requires both the user personal data and corresponding program that processes it, to efficiently cache program in a group, a novel program popularity estimation scheme is proposed, which is based on a semi-Markov process model. Then, a greedy program cooperative caching mechanism is established, which can effectively reduce delay and energy consumption. Second, to address group congestion, a dynamic task migration scheme based on improved cooperative Q-learning is proposed, which can effectively reduce delay and alleviate congestion. Third, to minimize delay and energy consumption for resource allocation in a group, we formulate it as an optimization problem with a large number of variables, and then exploit a novel ADMM-based scheme to solve this problem, which can reduce the complexity of the problem with a new set of auxiliary variables, these subproblems are all convex problems that can be solved by using a primal-dual approach, which guarantees its convergence. Finally, we prove its convergence by using the Lyapunov theory. The numerical results demonstrate the effectiveness of the CL-ADMM framework in reducing delay and energy consumption in MEC.

In this paper, we propose a versatile network architecture, named VFTree, for data centers. VFTree provisions unique versatility in the sense that its topology and performance can be tailored with great freedom. The wide dynamic range and fine granularity of its configurations allow this architecture to closely follow the demands of the running traffic. Also, this versatility facilitates the reuse of network devices, so that upgrades could be achieved by rearranging existing devices, avoiding the expenditure on new generations of hardware in each upgrade cycle. Furthermore, this versatility allows VFTree to be elaborately tuned into cost efficient zones. This way, compared to widely adopted industrial solutions including fat-tree, VFTree can provide even higher aggregate bandwidth and richer path availability at the same cost. In this paper, we first design the network topology of VFTree. We parameterize the topology so that it is flexible and generalized. For example, we can configure the numbers of upward and downward ports for the switches, which are fixed in the classic fat-tree. Based on that, we propose routing algorithms, implement the abstraction from packet level to the flow level, and handle the flow collisions. We also analyze VFTree’s performance, demonstrate its aforementioned features, and compare it with its predecessors. VFTree can be seen as a generalization of, and is backward-compatible to fat-tree. We believe it is ready to be deployed in industry, as a perfect replacement of the fat-tree DCNs.

The development of Virtual Network Functions (VNFs) migrates network functions from dedicated hardware to groups of commodity servers called network points of presence (N-PoPs). In this way, network services are redefined as interconnected VNFs called Service Function Chains (SFCs). The emerging of SFCs significantly reduces the cost of network services and improves scalability. However, the availability of SFCs brings new challenges since a failure of any N-PoP along an SFC affects its availability. In this paper, we propose two rerouting strategies to improve the availability of SFCs. First, we propose a local rerouting strategy to bypass the failed N-PoPs on SFCs using locally rerouted paths (LRPs). In the strategy, we formulate an optimization model to minimize the maximum load on links while deploying SFCs and LRPs to reduce the risk of congested links caused by local rerouting. We then propose an approximation algorithm to solve the optimization problem, preserving an approximation ratio of$\mathcal {O}(\log (|V|))$, where$|V|$is the number of N-PoPs in the network. We also propose an alternative heuristic algorithm to improve efficiency. Second, we propose a supplementary rerouting strategy with an online algorithm to provide supplementary rerouted paths when original SFCs and corresponding LRPs fail at the same time in the local rerouting strategy. The online algorithm is proved to have an$\mathcal {O}(\log (|V|))$competitive ratio to the offline optimum. Finally, our extensive simulation results show that the proposed algorithms can provide highly available SFCs with less congested links.

With mobile devices extensively used in daily life, there are ample opportunities to exchange sensing data through them, even without centralized management. In this paper, we design a peer based data exchanging model, where relay nodes move to certain locations to connect data providers and consumers to facilitate data delivery. Consumers are willing to pay for the data and these rewards are given to both relays and data providers. We first prove the NP-hardness of the problem on how to assign relay nodes to proper locations, and present a centralized optimal method with an approximation ratio. Then we define an autonomous compensation game for relays to make their individual decisions without any central authority. The sufficient and necessary condition for the existence of Nash equilibrium is derived, and an efficient reinforcement learning solver is designed to find the exact forms of equilibria. We analyze and compare this distributed game to the centralized social optimal solution, showing that the game incurs small bounded social costs, and is efficient under various network sizes, number of providers, number of consumers and device mobility.

Presents an editorial analsis of the state of the IEEE Transactions on Cloud Computing.

Scalable, fine-grained access control for Internet-of-Things is needed in enterprise environments, where tens of thousands of users need to access smart objects which have a similar or larger order of magnitude. Existing solutions offer all-or-nothing access, or require all access to go through a cloud backend, greatly impeding access granularity, robustness and scale. In this paper, we propose Heracles, an IoT access control system which achieves robust, fine-grained access control and responsive execution at enterprise scale. Heracles adopts a capability-based approach using secure, unforgeable tokens that describe the authorizations of users, to either individuals or collections of objects in single or bulk operations. It has a 3-tier architecture to provide centralized policy and distributed execution desired in enterprise environments. Extensive analysis and performance evaluation on a testbed prove that Heracles achieves fine-grained access control and responsive execution at enterprise scale. Compared with systems using access control list, Heracles eliminates or reduces by 10x-100x the updating overhead under frequent changes of subject memberships and policies. Besides, Heracles achieves responsive execution: it takes 0.57 second to access 18 objects which are scattered 1-9 hops away, and execution on a 1-hop or 2-hop object needs only 0.07 or 0.13 second respectively.

Due to that Service Function Chain (SFC) permits the forwarding of flows along a predetermined sequence chain of Virtual Network Functions (VNFs), it has become a common service in Network Function Virtualization (NFV)-enabled Software Defined Networks (SDNs). Generally, since there are multiple same VNF-instances in NFV-Enabled SDNs, this brings a great challenge for selecting or placing the required VNF-instances to satisfy the routing of SFC Request flows (SRs). In this paper, we study the routing problem for SRs by jointly considering dynamical VNF placement and multiple Resources and Quality of Service (QoS) constraints in NFV-Enabled SDNs. Specifically, we first define two optimization problems: one is the Dynamical VNF Placement and Routing Problem for SRs (DVPRP) and the other is the Delay, packet Loss and Jitter Aware Dynamical VNF Placement and Routing Problem for SRs (DLJA-DVPRP). We then formulate the two problems as Integer Linear Programming (ILP) problems. Next, we creatively devise an auxiliary edge-weight graph and propose two efficient algorithms to solve the problems with the aim of minimizing the resource consumption costs as well as ensuring multiple QoS constraints. Especially, we utilize the shortest path algorithm based on Lagrange relaxation method to solve the DLJA-DVPRP with multiple QoS constraints. Compared with existing algorithms, simulation results demonstrate our proposed algorithms have better performance in terms of throughput, traffic acceptance rate and load balance.

Energy provisioning plays a key role in the sustainable operations of Wireless Sensor Networks (WSNs). Recent efforts deploy multi-source energy harvesting sensors to utilize ambient energy. Meanwhile, wireless charging is a reliable energy source not affected by spatial-temporal ambient dynamics. This article integrates multiple energy provisioning strategies and adaptive adjustment to accomplish self-sustainability under complex weather conditions. We design and optimize a three-tier framework with the first two tiers focusing on the planning problems of sensors with various types and distributed energy storage powered by environmental energy. Then we schedule the Mobile Chargers (MC) between different charging activities and propose an efficient, 4-factor approximation algorithm. Finally, we adaptively adjust the algorithms to capture real-time energy profiles and jointly optimize those correlated modules. Our extensive simulations demonstrate significant improvement of network lifetime ( ), increase of harvested energy (15%), reduction of network cost (30%), and the charging capability of MC by 100%.

Originated from distributed learning, federated learning enables privacy-preserved collaboration on a new abstracted level by sharing the model parameters only. While the current research mainly focuses on optimizing learning algorithms and minimizing communication overhead left by distributed learning, there is still a considerable gap when it comes to the real implementation on mobile devices. In this article, we start with an empirical experiment to demonstrate computation heterogeneity is a more pronounced bottleneck than communication on the current generation of battery-powered mobile devices, and the existing methods are haunted by mobile stragglers. Further, non-identically distributed data across the mobile users makes the selection of participants critical to the accuracy and convergence. To tackle the computational and statistical heterogeneity, we utilize data as a tuning knob and propose two efficient polynomial-time algorithms to schedule different workloads on various mobile devices, when data is identically or non-identically distributed. For identically distributed data, we combine partitioning and linear bottleneck assignment to achieve near-optimal training time without accuracy loss. For non-identically distributed data, we convert it into an average cost minimization problem and propose a greedy algorithm to find a reasonable balance between computation time and accuracy. We also establish an offline profiler to quantify the runtime behavior of different devices, which serves as the input to the scheduling algorithms. We conduct extensive experiments on a mobile testbed with two datasets and up to 20 devices. Compared with the common benchmarks, the proposed algorithms achieve 2-100× speedup epoch-wise, 2–7 percent accuracy gain and boost the convergence rate by more than 100 percent on CIFAR10.

With the advancement of edge computing and network function virtualization, it is promising to provide flexible and low-latency network services at the network edge. However, due to resource limitation and heterogeneity of servers at the edge, it is unlikely to achieve an efficient service function chain deployment without considering the resource management of edge servers jointly. In this article, we consider the Joint Service function chain Deployment and Resource Management problem (JSDRM) in heterogeneous edge environments with the goal of minimizing the total system latency. We prove the NP-hardness of JSDRM and propose a scheme called JOint service function chain deployment and resource management Scheme (JOS) based on a game-theoretic approach to deploy service function chains and manage resources. We prove that JOS has a constant approximation ratio of 2.62 Extensive simulation results show that our scheme performs comparably to the optimal solution and much better than the baselines. The simulation results also show that the proposed scheme is time-efficient.

Multi-access Edge Computing (MEC) comes forth as a promising computing paradigm to meet the low-delay requirements of computation-intensive applications. In this work, we focus on the task offloading and dispatching problem in MEC, where mobile devices (MDs) can decide to execute tasks locally or offload them to access points (APs), and each AP can dispatch its received tasks to other APs. Specially, we consider both APs and MDs are selfish, which aim to minimize their respective task completion delay. The problem is particularly difficult, as there exists computing resource competition among MDs and APs, respectively. Furthermore, the offloading decisions made by MDs and the dispatching decisions made by APs are interactive. To overcome the challenges, we first formulate the problem as a multi-leader multi-follower Stackelberg game, and rigorously prove the existence of a Stackelberg equilibrium. Then, we propose an efficient approach to achieve a Stackelberg equilibrium, which includes a Q-learning based offloading strategy for MDs and a best response based dispatching strategy for APs. We also demonstrate an upper bound of the total completion delay achieved by our approach with a constant approximation ratio. Extensive simulations are also conducted to show the performance of our approach, compared with baselines.

Distributed edge caching has drawn great attention with the fast development of smart edge devices. Caching popular contents in the edge can reduce latency and improve the quality of service of edge mobile users. Meanwhile, the data privacy in the edge is critical to preserve the privacy of individual users and devices. How to jointly determine the caching and routing policy in the edge network in a distributed manner and simultaneously design the proper privacy preserving mechanism are challenging. We tackle these challenges in two progressive steps. First, we design a distributed algorithm which can achieve the global optimum. Second, we propose a privacy-preserving mechanism based on differential privacy and prove the privacy guarantee. We conduct extensive numerical simulations based on real-world requests to evaluate the performance of the proposed distributed algorithm and the privacy mechanism. Results highlight a significant improvement of the proposed distributed algorithm while only up to 10.1% of the total serving cost increased by the privacy mechanism.

The rise of dockless electric bike sharing becomes a new urban lifestyle recently. More than just the first-and-last mile, it offers a new modality of green transportation. However, in addition to the traditional re-balance and overcrowding problems, it also brings new challenges to urban management and maintenance. Due to the safety risks of batteries, customers are regulated to park at designated locations, which potentially causes dissatisfaction and customer loss. Meanwhile, service providers should charge those scattering low-energy batteries in time. To address these issues, we propose E-sharing, a two-tier optimization framework that leverages data-driven online algorithms to plan parking locations and maintenance. First, we balance the user dissatisfaction and the number of parking locations by minimizing their sum. To account for real-time dynamics while not losing track of the historical optimality, we propose an online algorithm based on its near-optimal offline solution. Second, we develop an incentive mechanism to motivate users to aggregate low-battery bikes together, saving the cost of bike charging. Our experiment based on the public dataset demonstrates that the online algorithm can minimize the cost from the conflicting objectives and incentive mechanism further reduces the maintenance cost by 47%.

Edge computing means that computing tasks are executed on edge devices closer to the data source. It can effectively improve system response speed and reduce the risk of user data leakage. However, current data access control schemes usually focus on cloud computing and rarely on edge computing. Although attribute-based encryption (ABE) scheme can realize flexible and reliable access control, computing cost is too high with the increase of access policy complexity. Therefore, combining computation outsourcing technology with dynamic policy updating technology, we propose a data access control scheme based on ciphertext-policy ABE (CP-ABE) for edge computing. We outsource part of storage service and part of decryption computing to edge nodes, effectively reducing the computing pressure of users. When data owner requires a new access policy, policy update key is generated timely and transmitted to cloud service provider, which is used to update the access policy, reducing the risk of bandwidth consumption and leakage of the ciphertext back and forth transmission. Finally, security analysis and experiment results verify the safety and effectiveness of our scheme.

Peer communication among edge devices (e.g., mobiles, vehicles, IoT and drones) is frequently data-centric: most important is obtaining data of desired content from suitable nodes; who generated or transmitted the data matters much less. Typical cases are robust one-to-many data sharing: e.g., a vehicle sending weather, road, position and speed data streams to nearby cars continuously. Unfortunately, existing address-based wireless communication is ill-suited for such purposes. We propose V-MAC, a novel data-centric radio that provides a pub/sub abstraction to replace the point-to-point abstraction in existing radios. It filters frames by data names instead of MAC addresses, thus eliminating complexities and latencies in neighbor discovery and group maintenance in existing radios. V-MAC supports robust, scalable and high rate multicast with consistently low losses across receivers of varying reception qualities. Experiments using a Raspberry Pi and a commodity WiFi dongle based prototype show that V-MAC reduces loss rate from WiFi broadcast's 50-90% to 1-3% for up to 15 stationary receivers, 4-5 moving people, and miniature and real vehicles. It cuts down filtering latency from 20μs in WiFi to 10μ s for up to 2 million data names, and improves cross stack latency 60-100× for TX/RX paths. We have ported V-MAC to 4 major WiFi chipsets (including 802.11 a/b/g/n/ac radios), 6 different platforms (Android, embedded and FPGA systems), 7 Linux kernel versions, and validated up to 900Mbps multicast data rate and interoperation with regular WiFi. We will release V-MAC as a mature, reusable asset for edge computing research.

With the commoditization of private data, data trading in consideration of user privacy protection has become a fascinating research topic. The trading for private web browsing histories brings huge economic value to data consumers when leveraged by targeted advertising. In this paper, we study the trading of multiple correlated queries on private web browsing history data. We propose TERBE, which is a novel trading framework for correlaTed quEries based on pRivate web Browsing historiEs. TERBE first devises a modified matrix mechanism to perturb query answers. It then quantifies privacy loss under the relaxation of classical differential privacy and a newly devised mechanism with relaxed matrix sensitivity, and further compensates data owners for their diverse privacy losses in a satisfying manner. Through real-data based experiments, our analysis and evaluation results demonstrate that TERBE balances total error and privacy preferences well within acceptable running time, and also achieves all desired economic properties of budget balance, individual rationality, and truthfulness.

Innovative edge devices (e.g., smartphones, IoT devices) are becoming much more pervasive in our daily lives. With powerful sensing and computing capabilities, users can generate massive amounts of data. A new business model has emerged where data producers can sell their data to consumers directly to make money. However, how to protect the profit of the data producer from rogue consumers that may resell without authorization remains challenging. In this paper, we propose a smart-contract based protocol to protect the profit of the data producer while allowing consumers to resell the data legitimately. The protocol ensures the revenue is shared with the data producer over authorized reselling, and detects any unauthorized reselling. We formulate a fair revenue sharing problem to maximize the profit of both the data producer and resellers. We formulate the problem into a two-stage Stackelberg game and determine a ratio to share the reselling revenue between the data producer and resellers. Extensive simulations show that with resellers, our mechanism can achieve higher profit for the data producer and resellers.

The fast development of virtual network functions (VNFs) brings new opportunities to network service deployment on edge networks. For complicated services, VNFs can chain up to form service function chains (SFCs). Despite the promises, it is still not clear how to backup VNFs to minimize the cost while meeting the SFC availability requirements in an online manner. In this paper, we propose a novel self-adapting scheme named SAB to efficiently backup VNFs over both the edge and the cloud. Specifically, SAB uses both static backups and dynamic ones created on the fly to accommodate the resource limitation of edge networks. For each VNF backup, SAB determines whether to place it on the edge or the cloud, and if on the edge, which edge server to use for load balancing. SAB does not assume failure rates of VNFs but instead strives to find the sweet point between the desired availability of SFCs and the backup cost. Both theoretical performance bounds and extensive simulation results highlight that SAB provides significantly higher availability with lower backup cost compared with existing baselines.

Electric autonomous vehicles provide a promising solution to the traffic congestion and air pollution problems in future smart cities. Considering intensive energy consumption, charging becomes of paramount importance to sustain the operation of these systems. Motivated by the innovations in renewable energy harvesting, we leverage solar energy to power autonomous vehicles via charging stations and solar-harvesting rooftops, and design a framework that optimizes the operation of these systems from end to end. With a fixed budget, our framework first optimizes the locations of charging stations based on historical spatial-temporal solar energy distribution and usage patterns, achieving (2 + ε) factor to the optimal. Then a stochastic algorithm is proposed to update the locations online to adapt to any shift in the distribution. Based on the deployment, a strategy is developed to assign energy requests in order to minimize their traveling distance to stations while not depleting their energy storage. Equipped with extra harvesting capability, we also optimize route planning to achieve a reasonable balance between energy consumed and harvested en-route. Our extensive simulations demonstrate the algorithm can approach the optimal solution within 10-15% approximation error, and improve the operating range of vehicles by up to 2-3 times compared to other competitive strategies.

Smart grid is a highly intelligent power system integrating advanced communication technology, sensor measurement and automatic control technology, which is gradually replacing the traditional power grid. However, the smart grid faces challenges of balancing privacy, efficiency and functionality when processing massive amount of data. In this paper, a smart grid model based on edge computing paradigm is established, and then an efficient privacy-preserving multidimensional data aggregation scheme is proposed. This scheme adopts an improved identity-based signature algorithm and Paillier homomorphic cryptosystem to protect the privacy of users. In addition, super-increasing sequence is used in the proposed scheme to enable smart meters to report multiple types of data in a single reporting message, so that the Service Center (SC) can perform one-way analysis of variance on the data to provide users with more personalized services. Also the security analysis indicates that the proposed scheme works in protecting user's electricity consumption privacy. Finally, performance analyses indicate that this scheme can effectively reduce the computational overhead.

Edge computing is becoming pervasive in our daily lives with emerging smart devices and the development of communication technology. Resource-rich smart devices and high-density supportive networks make data transactions prevalent over edge environments. To ensure such transactions are unmodifiable and undeniable, blockchain technology is introduced into edge environments. In this paper, we propose a hybrid blockchain system in edge environments to enhance the security for transactions and determine the incentive for miners. We propose a Proof of Work (PoW) and Proof of Stake (PoS) hybrid consensus blockchain system utilizing the heterogeneity of devices to adapt to the characteristic of edge environments. We raise the incentive assignment problem that gives the corresponding PoW miner when a new block generates. We further formulate it into a two-stage Stackelberg game. We propose an algorithm and prove that it can obtain the global optimal results for the incentive that the miner will receive for a new block. Numerical simulation results show that our proposed algorithm can give reasonable incentive to miners under different system parameters in edge blockchain systems.

The fast development of virtual network functions (VNFs) brings new challenges to providing reliability. The widely adopted approach of deploying backups incurs financial costs and environmental impacts. On the other hand, the recent trend of incorporating renewable energy into computing systems provides great potentials, yet the volatility of renewable energy generation presents significant operational challenges. In this paper, we optimize availability of VNFs under a limited backup budget and renewable energy using a dynamic strategy GVB. GVB applies a novel online algorithm to solve the VNF reliability optimization problem with non-stationary energy generation and VNF failures. Both theoretical bound and extensive simulation results highlight that GVB provides higher reliability compared with existing baselines.

Edge caching is an effective approach to improve the quality of service for mobile users and therefore a critical component for 5G networks. Despite the importance, it is not clear how to determine which contents to cache and how to the serve requests in 5G networks to minimize the total operational cost in a distributed and online manner, especially when some mobile users can be served by multiple small base stations. In this paper, we formulate an optimization problem to jointly decide the caching policy and the routing decision. There are two challenges: the need for distributed control and the lack of future information. We therefore develop an online distributed algorithm with provable performance guarantees in terms of convergence and competitive ratio compared to the offline optimal solution. Numerical simulations based on real-world traces highlight the significant performance improvement compared to existing baselines.

With the explosion of mobile smart devices, many computation intensive applications have emerged, such as interactive gaming and augmented reality. Mobile edge computing is put forward, as an extension of cloud computing, to meet the low-latency requirements of the applications. In this paper, we consider an edge computing system built in an ultra-dense network with numerous base stations, and heterogeneous computation tasks are successively generated on a smart device moving in the network. An optimal task offloading strategy, as well as optimal CPU frequency and transmit power scheduling, is desired by the device user, to minimize both task completion latency and energy consumption in a long-term. However, due to the stochastic computation tasks and dynamic network conditions, the problem is particularly difficult to solve. Inspired by reinforcement learning, we transform the problem into a Markov decision process. Then, we propose an online offloading approach based on a double deep Q network, in which a specific neural network model is also provided to estimate the cumulative reward achieved by each action. We also conduct extensive simulations to compare the performance of our proposed approach with baselines.

As one of the fastest-growing applications in the Peer-to-Peer (P2P) network, the development of blockchain technology is accompanied by different attacks. Those include whitewashing, free-riding, and distributed denial of service (DDoS) attacks, particularly because of features such as anonymity, distributed, permissionless in the blockchain network. One popular of them is spam transactions. Although the blockchain protocol requires each node to verify all received transactions, many nodes choose to forward transactions without verification to conserve their computational power, as there is no punishment for such a shirking. And it makes the blockchain vulnerable to the spreading of spam transactions over the network and creates extra burdens for all nodes in the network. We propose a reputation mechanism for the blockchain system to tackle this problem: Each node will locally compute reputations of its neighbors, and decide the probability to verify a received transaction based on the reputation value of the transaction sender. In turn, its neighbors will have an incentive to conduct verification to keep its reputation high. Subsequently, spam transactions can be blocked before reaching the miners. We have conducted a series of simulations, which clearly demonstrate the advantage of our reputation mechanism.

Summary In wireless sensor networks (WSNs), the volume of data is increasing at an unpredictable rate, which inevitably leads to high spatial‐temporal correlation. To eliminate data redundancy, some researchers have proposed many data aggregation methods. However, a few of aggregation approaches can handle energy consumption and latency simultaneously. Therefore, in this paper, we propose an efficient algorithm, called Delay‐Minimum Energy‐Balanced (DMEB) data aggregation, which benefits from the superiority of the sparse random measurement matrix and minimum delay algorithm. Owing to the sparsity characteristics of the measurement matrix, only the nodes whose corresponding elements in the matrix are non‐zero take part in the measurement. Each measurement can form an aggregation tree with minimum delay. After a sink node receives all the measurements, original readings can be recovered precisely. In addition, we adopt a novel scheduling method to avoid information interference. Experiment results demonstrate that, under recovering the original data accurately, the proposed data aggregation algorithm can not only shorten delay in data collection process but also reduce communication cost and prolong network lifetime during data transmission process.

In this paper, we propose a novel server-centric network for data centers, called RRect. Compared to existing server-centric networks, RRect provides a more graceful degradation performance in the presence of component failure. Meanwhile, RRect enjoys a linear diameter to the network order and multiple parallel paths. We present algorithms to find paths and to construct all parallel paths between any pair of servers in RRect. We also show that without using any power-aware routing algorithm, RRect behaves more power efficient in its interconnection network. To meet today's stringent high availability requirement, RRect can be configured into redundancy and failover scheme. In particular, RRect can be configured into both symmetric and asymmetric redundancy modes to cater different applications' needs, which cannot be implemented in existing server-centric networks. Moreover, RRect gives more flexibility to adjust the network size. Given the same switches, by fine tuning the parameters, RRect provides numerous structures with different sizes, while preserving the properties of short diameter and multiple parallel paths. Our comprehensive simulations show that RRect gives much better graceful degradation performance in the presence of component failure, and RRect saves much energy in the interconnection network. Meanwhile, RRect can maintain the same performance on many critical metrics as BCube, including short diameter and excellent aggregate throughput. All these features make RRect a very empirical structure for enterprise dater center network products.

Presents the introductory editorial for this issue of the publication.

Edge devices with sensing, storage, and communication resources (e.g., smartphones, tablets, connected vehicles, and IoT nodes) are increasingly penetrating our daily lives. Many novel applications can be created through sharing data among nearby peer edge devices. In such applications, caching data at some edge devices can greatly improve data availability, retrieval robustness, and delivery latency. In this paper, we study the unique problem of caching fairness in edge computing environments. Due to the heterogeneity of peer edge devices, load balance is a critical issue that affects the fairness in caching. We propose fairness metrics to characterize this issue and formulate the caching fairness problem as an integer linear programming problem, which is shown as the summation of multiple Connected Facility Location (ConFL) problems. We provide an approximation algorithm by leveraging an existing ConFL approximation algorithm, and prove that it preserves a 6.55 approximation ratio. We further develop a distributed algorithm where devices exchange data reachability information and identify popular candidates as caching nodes. Finally, we update the fairness metric and apply it to algorithms for making continuous caching decisions overtime. Our extensive evaluation results show that compared with existing caching algorithms for wireless networks, our proposed algorithms significantly improve the data caching fairness while keeping the contention induced latency comparable to the best existing algorithms.

With the technological advances in wireless multimedia domain, these videos made by mobile edge devices dominate network traffics. The video summarization technology enables users to understand the storyline of a video before a client requests the complete video content. Summarizing a video on edge devices and transmitting the summary between them requires a user-oriented and adaptive solution due to the limited capability and the dynamic wireless links of edge devices. Therefore, it is beneficial to improve the user's viewing experience and the bandwidth utilization ratio if we generate and transmit a video summary based on network connections and the user's tolerant latency. Unfortunately, previous summarization approaches are incapable of adjusting the summary size adapted to the varying network bandwidth and the user's attitude towards latency. To timely and flexibly deal with mobile videos, we first formulate the video summarization optimization problem with the elastic number of selected representative segments and the outlier detection within a bounded time budget. Furthermore, we develop an online greedy algorithm called the Elastic Video Summarization Algorithm (EVS) to solve the NP hard problem. We analyze the properties associated with EVS and further design an improved EVS-II to reduce computation complexity. Finally, the experimental results demonstrate that our proposed algorithms outperform other existing researches in fitting network bandwidth and detecting outliers.

Mobile edge computing (MEC) is a new paradigm to alleviate resource limitations of mobile IoT networks through computation offloading with low latency. This article presents an efficient and secure multi-user multi-task computation offloading model with guaranteed performance in latency, energy, and security for mobile-edge computing. It does not only investigate offloading strategy but also considers resource allocation, compression and security issues. Firstly, to guarantee efficient utilization of the shared resource in multi-user scenarios, radio and computation resources are jointly addressed. In addition, JPEG and MPEG4 compression algorithms are used to reduce the transfer overhead. To fulfill security requirements, a security layer is introduced to protect the transmitted data from cyber-attacks. Furthermore, an integrated model of resource allocation, compression, and security is formulated as an integer nonlinear problem with the objective of minimizing the weighted sum of energy under a latency constraint. As this problem is considered as NP-hard, linearization and relaxation approaches are applied to transform the problem into a convex one. Finally, an efficient offloading algorithm is designed with detailed processes to make the computation offloading decision for computation tasks of mobile users. Simulation results show that our model not only saves about 46% of system overhead consumption in comparison with local execution but also scale well for large-scale IoT networks.

With the rapid development of cloud computing, many cloud service providers have been deploying more and more datacenters to provide better reliability and quality of service. The energy optimization problem has become an emerging concern. The current researches focus on how to either reduce the energy consumption of servers or reduce the consumption of inter-datacenters data transmission. However, energy optimization of joint inter-datacenter and servers has not been explored. In this paper, we first introduced the background to the energy consumption problem of geographically distributed datacenters. Then, based on the Service Level Agreement (SLA), this paper proposes an online control framework to minimize the energy consummation cost. The online control framework can dynamically make decisions by adjusting geographically load balancing, capacity right-sizing, server speed scaling, and flow programming. Finally, the simulation verifies the effectiveness of the proposed framework in cost saving.

Mobile edge computing (MEC) has become a promising technique to accommodate demands of resource-constrained mobile devices by offloading the task onto edge clouds nearby. However, most existing works only focus on whether or where a task is offloaded but ignore the motivation of the edge cloud to offer service. To stimulate service provisioning by edge clouds, it is essential to design an incentive mechanism that charges mobile devices and rewards edge clouds. In this paper, we utilize market-based pricing model to establish a relationship between the resources provided by edge clouds and the price paid by the mobile devices in a non-competitive environment. Furthermore, we design a profit maximization multi-round auction (PMMRA) mechanism for the resource trading between edge clouds as sellers and mobile devices as buyers in a competitive environment. The mechanism can effectively determine the price paid by the buyers to use the resources provided by the sellers and make the corresponding match between edge clouds and mobile devices. Finally, numerical results show that proposed mechanism outperforms other existing algorithms in maximizing the profits of resource providers.

Named Data Networking (NDN) is a promising instance of Information-Centric Networking (ICN). With the expansion of the network, unbounded namespace and query of the routing table in NDN can deteriorate routing performance. Since Hyperbolic Routing (HR) does not need to maintain a full routing table, it becomes a potential solution to this problem. Existing works assign coordinate based on betweenness centrality of nodes. The betweenness-based solution can fully embed the network into hyperbolic space; however, it brings a problem that packets are aggregated to high-betweenness nodes. In this paper, by jointly considering the betweenness centrality of nodes and popularity of contents while assigning hyperbolic coordinate, we first propose a content-based hyperbolic routing called Pop-Hyper. As result, packets are sent to nodes with high betweenness and high popularity. Then, a push mechanism based on Pop-Hyper called HyperPush is presented. Finally, we compare our proposals with the existing mechanisms in the 22-node and 100-node topology, respectively. The simulation results show that Pop-Hyper performs well in terms of hop count and packet loss; while HyperPush outperforms others in terms of network load, cache hit ratio and delays.

Edge devices with sensing, storage, and communication resources are penetrating our daily lives. These resources make it possible for edge devices to conduct data transactions (e.g., micro-payments, micro-access control). The blockchain technology can be used to ensure transaction unmodifiable and undeniable. In this paper, we propose a blockchain system that adapts to the limitations of edge devices. The new blockchain system can fairly and efficiently allocate storage resources on edge devices, which makes it scalable. We find the optimal peer nodes for transaction data storage in the blockchain, and propose a recent block storage allocation scheme for quick retrieval of missing blocks. The proposed blockchain system can also reach mining consensus with low energy consumption in edge devices with a new Proof of Stake mechanism. Extensive simulations show that our proposed blockchain system works efficiently in edge environments. On average, the new system uses 15% less time and consumes 64% less battery power when compared with traditional blockchain systems.

We investigate the problem of stochastic network optimization in presence of non-stationarity and estimations of average states in the future. Specifically, we first prove that the widely-used Drift and Penalty Algorithm in the Lyapunov optimization framework works well for non-stationary systems with periodical states. However, when the system is not periodical, non-stationarity may lead to severe performance degradation, which motivates the design of a novel, online algorithm named DPNP that incorporates the estimations of average future states into the stochastic optimization framework for decision making. DPNP is an online algorithm that requires zero a-prior distributional information about estimation errors. DPNP not only has near-optimal theoretical performance guarantees, but also outperforms existing Drift and Penalty Algorithm in numerical simulations. The improvement of DPNP highlights the importance of combining historic and future state estimations in non-stationary stochastic network optimization.

This paper considers how to cache popular contents and load balancing in 5G networks to minimize the total operating cost. Specifically, popular contents requested by mobile users (MUs) are cached in small base stations (SBSs) to serve them with better quality and lower cost because the SBSs are often much closer to MUs than the base station (BS). Due to limited caching capacity and bandwidth of SBSs, the caching policy and load balancing algorithm need to be carefully designed jointly and dynamically over time. In this paper, we formulate the joint content placement and load balancing by an online optimization problem. This problem is challenging because of the integer constraint in content placement and the lack of future information. We tackle the challenges in two progressive steps. First, we propose a primal-dual algorithm to solve the problem efficiently and prove it always achieves the optimal cost assuming all system information is available. Then we integrate promising online optimization algorithms with the proposed primal-dual algorithm so that only limited short-term predictions are needed. Theoretical performance bounds are also derived. We conduct extensive numerical simulations to evaluate the performance of proposed algorithms. Results highlight that the proposed online algorithms can reduce the system cost significantly (by as much as 27%) compared to the existing solutions and perform similarly to the offline optimal solution.

Emerging virtual network functions (VNFs) introduce new flexibility and scalability into traditional middlebox. Specifically, middleboxes are virtualized as software-based platforms running on commodity servers known as network points of presence (N-PoPs). Traditional network services are therefore realized by chained VNFs, i.e., service function chains (SFCs), running on potentially multiple N-PoPs. SFCs can be flexibly placed and routed to reduce operating cost. However, excessively pursuing low cost may incur congestion on some popular N-PoPs and links, which results in performance degradation or even violation of the service level of agreements.

Incentives are explored in the sharing economy to inspire users for better resource allocation. Previous works build a budget-feasible incentive mechanism to learn users' cost distribution. However, they only consider a special case that all tasks are considered as the same. The general problem asks for finding a solution when the cost for different tasks varies. In this paper, we investigate this general problem by considering a system with k levels of difficulty. We present two incentivizing strategies for offline and online implementation, and formally derive the ratio of utility between them in different scenarios. We propose a regret-minimizing mechanism to decide incentives by dynamically adjusting budget assignment and learning from users' cost distributions. Our experiment demonstrates utility improvement about 7 times and time saving of 54% to meet a utility objective compared to the previous works.

Energy supply remains to be a major bottleneck in Wireless Sensor Networks (WSNs). A self-sustainable network operates without battery replacement. Recent efforts employ multi-source energy harvesting to power sensors with ambient energy. Meanwhile, wireless charging is considered in WSNs as a reliable energy source. It motivates us to integrate both fields of research to build a self-sustainable network and guarantee operation under any weather condition. We propose a three-step solution to optimize this new framework. We first solve the Sensor Composition Problem (SCP) to derive the percentage of different types of sensors. Then we enable self-sustainability by bringing energy harvesting storage to the field for charging the Mobile Charger (MC). Next, we propose a 3-factor approximation algorithm to schedule sensor charging and energy replenishment of MC. Our extensive simulation results demonstrate significant improvement of network lifetime and reduction of network cost. The network lifetime can be extended at least three times compared with traditional approaches and the charging capability of MC increases at least 100%.

The trading of social media data has attracted wide research interests over years. Especially the trading for web browsing histories probably produces tremendous economic value for data consumers when being applied to targeted advertising. However, the disclosure of entire browsing histories, even in form of anonymous datasets poses a huge threat to user privacy. Although some existing solutions have investigated privacy-preserving outsourcing of social media data, unfortunately, they neglected the impact on the data consumer's utility. In this paper, we propose PEATSE, a new Privacy-prEserving dAta Trading framework for web browSing historiEs. It takes users' diverse privacy preferences and the utility of their web browsing histories into consideration. PEATSE perturbs users' detailed browsing times on released browsing records to protect user privacy, while balancing the privacy-utility tradeoff. Through real-data based experiments, our analysis and evaluation results demonstrate PEATSE indeed achieves user privacy protection, the data consumer's accuracy requirement, and truthfulness, individual rationality as well as budget balance.

With the popularity of mobile multimedia services, the explosive increase in video traffic not only causes huge load and energy consumption of base station (BS), but also affects the QoS of users. The device to device (D2D) multicast technology can effectively reduce the number of redundant video transmissions and improve energy efficiency of the BS. However, the existing researches about D2D technology assume that there is not unconstrained communication between local users, which is not in line with the actual situation. Moreover they do not take full advantage of attributes of users in mobile social networks. In this paper, we first propose a clustering method and select the cluster head users (CHUs) as relay nodes to distribute videos by considering the user's physical conditions and user's social attributes based on Chinese Restaurant Process (CRP). Then we put forward with a video distribution and sharing mechanism based on scalable video coding (SVC). In this mechanism, edge users collaboratively share videos on the basis of user's mobility, where Zipf distribution combines with SVC to effectively reduce the energy consumption of the BS. Finally, the experimental results show that the proposed strategy can not only reduce the energy consumption of the BS, but also improve the throughput and the stability and flexibility of video distribution.

This talk presents an emerging pervasive edge computing paradigm where heterogeneous mobile edge devices (e.g., smartphones, tablets, IoT and vehicles) can collaborate to sense, process data and create many novel applications at network edge. We propose a data centric design where data become self-sufficient entities that are stored, referenced independently from their producers. This enables us to design efficient and robust data discovery, retrieval and caching mechanisms. The future research agenda including scalable data discovery, cache management, autonomous processing, trust, security and privacy, incentives and semantic data naming) will be discussed.

Smart city as a new paradigm for future city development leads to a large amount of computing workload and high network latency especially with artificial intelligence algorithms. Fog computing, as one of the mobile edge computing paradigms, deploys some servers at the edge of mobile networks to solve these problems. However, it still remains a challenging issue how to obtain the energy-effective cooperation policy among fog nodes (FNs) to enhance the users' quality of experience (QoE) under fairness, where the fairness ensures that FNs are willing to take part in cooperations. Therefore, we first build up a cooperative fog computing system to process offloading workload on the entire fog layer by data forwarding. Then, we formulate a joint optimization problem of QoE and energy in integrated fog computing process with fairness. After that, we prove the convexity of the optimization problem and design a fairness cooperation algorithm (FCA) to obtain the optimal fairness cooperation policy of all FNs. Finally, numerical results show that our FCA can quickly converge to its solution compared with three traditional convex optimization approaches, and FCA can effectively reduce the time overhead and the energy consumption compared to baseline algorithm and distributed optimization algorithm.

Most indoor navigation technologies need to provide structure maps of buildings, but it is difficult to obtain these structure maps in practice. Therefore, we design a geomagnetism-based indoor navigation system without structure map of buildings by applying offloading strategy in narrow band Internet of Things. Why the geomagnetic signal can be used to achieve indoor navigation is due to its stability. We divide the indoor navigation into two parts: 1) the construction of signal fingerprint database and 2) the user navigation. First, the navigator carries out the signal acquisition of navigation route, and transfers the original signals to cloud server so as to construct the fingerprint database. Second, users can choose online navigation or offline navigation according to the actual situation. When choosing offline navigation, the users will employ dynamic time warping algorithm for fingerprint matching. When users would like to obtain better navigation results, they can choose online navigation. In this case, navigation system will offload the users' sampling data to remote cloud, and then the cloud matches the fingerprint of geomagnetic signals by using particle filter algorithm and sends the computation results to the users so as to indicate the users' moving direction. Experiment results demonstrate that our method is effective and the turning error is only 5 cm.

As metropolises develop, air pollution has become a serious problem, especially in developing countries like China. Many governments and researchers have devoted themselves to tackling and solving this problem. With the proliferation of smartphones, mobile crowdsensing is becoming a promising paradigm for monitoring large-scale environmental phenomena. In a practical crowdsensing system, incentives should be provided to encourage the participation of rational smartphone users, because it incurs various costs on users to collect sensing data. However, monitoring fine-grained air pollution in a large urban area based on crowdsensing will lead to high payments, which makes designing an efficient incentive mechanism a challenging problem. Fortunately, compressive sensing (CS) has been proved as an effective technology to reduce the amount of collected data via exploiting the spatial correlations among sensing data. In this article, we employ CS in the air pollution monitoring application, in which only a sampled set of locations are selected to collect data and provide incentives to the participants, and air pollution concentrations in unselected locations are inferred via CS. We propose an active learning scheme, which iteratively selects valuable locations to collect sensing data. Moreover, an expectation maximization-based algorithm is designed to detect the contexts in which sensing data are collected, and an efficient incentive mechanism is provided to encourage users with low costs participating. Comprehensive simulations are conducted to demonstrate the performance of our proposed scheme.

Mobile cloud computing (MCC) as an emerging and prospective computing paradigm, can significantly enhance computation capability and save energy for smart mobile devices (SMDs) by offloading computation-intensive tasks from resource-constrained SMDs onto resource-rich cloud. However, how to achieve energy-efficient computation offloading under hard constraint for application completion time remains a challenge. To address such a challenge, in this paper, we provide an energy-efficient dynamic offloading and resource scheduling (eDors) policy to reduce energy consumption and shorten application completion time. We first formulate the eDors problem into an energy-efficiency cost (EEC) minimization problem while satisfying task-dependency requirement and completion time deadline constraint. We then propose a distributed eDors algorithm consisting of three subalgorithms of computation offloading selection, clock frequency control, and transmission power allocation. Next, we show that computation offloading selection depends on not only the computing workload of a task, but also the maximum completion time of its immediate predecessors and the clock frequency and transmission power of the mobile device. Finally, we provide experimental results in a real testbed and demonstrate that the eDors algorithm can effectively reduce EEC by optimally adjusting CPU clock frequency of SMDs in local computing, and adapting the transmission power for wireless channel conditions in cloud computing.

Information about urban safety, e.g., the safety index of a position, is of great importance to protect humans and support safe walking route planning. Despite some research on urban safety analysis, the accuracy and granularity of safety index inference are both very limited. The problem of analyzing urban safety to predict safety index throughout a city has not been sufficiently studied and remains open. In this paper, we propose U-Safety, an urban safety analysis system to infer safety index by leveraging multiple cross-domain urban location-based data. We first extract spatially-related and temporally-related features from various urban location-based data, including urban map, housing rent and density, population, positions of police stations, point of interests (POIs), crime event records, and taxi GPS trajectories. Then, these features are fed into a novel sparse auto-encoder (SAE) framework with feature correlation constraint to obtain the final discriminative feature representation. Finally, we design a new co-training-based learning method, which consists of two separated classifiers, to calculate safety index accurately. We implement U-Safety and conduct extensive experiments by utilizing various real data sources obtained in New York City. The evaluation results demonstrate the advantages of U-Safety over other methods.

Energy remains a major hurdle in running computation-intensive tasks on wireless sensors. Recent efforts have been made to employ a Mobile Charger (MC) to deliver wireless power to sensors, which provides a promising solution to the energy problem. Most of previous works in this area aim at maintaining perpetual network operation at the expense of high operating cost of MC. In the meanwhile, it is observed that due to the low cost of wireless sensors, they are usually deployed at high density so there is abundant redundancy in their coverage in the network. For such networks, it is possible to take advantage of the redundancy to reduce the energy cost. In this paper, we relax the strictness of perpetual operation by allowing some sensors to temporarily run out of energy while still maintaining target $k$k-coverage in the network at lower cost of MC. We first establish a theoretical model to analyze the performance improvements under this new strategy. Then, we organize sensors into load-balanced clusters for target monitoring by a distributed algorithm. Next, we propose a charging algorithm named $\lambda$λ-GTSP Charging Algorithm to determine the optimal number of sensors to be charged in each cluster to maintain $k$k-coverage in the network and derive the route for MC to charge them. We further generalize the algorithm to encompass mobile targets as well. Our extensive simulation results demonstrate significant improvements of network scalability and cost saving that MC can extend charging capability over 2-3 times with a reduction of 40 percent of moving cost without sacrificing the network performance.

Network-based malware has posed serious threats to the security of host machines. When malware adopts a private TCP/IP stack for communications, personal and network firewalls may fail to identify the malicious traffic. Current firewall policies do not have a convenient update mechanism, which makes the malicious traffic detection difficult.

Localized traffic is ubiquitous in today's data centers. In this context, we propose to fit the topologies of the underlying network into the traffic locality, so that we can improve the efficiency of network resource utilization. We make our network infrastructure to be versatile, in the sense that its topology can be fitted into the profile of the traffic. We describe our network's topological architecture, design its addressing and routing schemes, and validate its adaptively fitting capability. We also evaluate its performance and compare it with fat-tree, a representative Clos-type data center network architecture. The evaluation results demonstrate that the our network can deliver the same throughput as fat-tree, but use significantly reduced network resources.

The development of Virtual Network Functions (VNFs) migrates network functions from dedicated hardware to groups of commodity servers called network points of presence (N-PoPs). Thus, network services are redefined as interconnected VNFs called Service Function Chains (SFCs). SFC has the potential to reduce costs of network services and improve scalability. However, the availability of SFC brings new challenges since a failure of any N-PoP along the SFC affects its availability. Deploying backup SFCs is a practical method to improve the availability of SFCs, but inappropriate deployments of backups may trigger the unnecessary capacity expansion of N-PoPs and thus waste VNF resources. In this paper, we solve this problem by proposing an optimization model called partial service function chain mapping. The model adopts partial SFC rerouting strategy for smaller rerouting delay and minimizes the maximum load on N- PoPs to reduce unnecessary capacity expansion of N- PoPs. We then propose a randomized rounding algorithm to solve the optimization problem, preserving the competitive ratio of O(log n), where n is the number of NPoPs in the network. Our extensive simulation results show that the proposed algorithm can significantly improve the availability of SFCs and limit the capacity expansion of N-PoPs.

This paper considers a mobile data collecting problem in a wireless sensor network with private residual sensor networks for the scenario in which the owners of residual sensor networks may perform dishonest behavior. The interaction between the wireless sensor network operator and the owners of residual sensor networks is modeled by a Stackelberg game which has a unique Stackelberg equilibrium. The influence of the Stackelberg equilibrium caused by the dishonest residual sensor networks owner are analyzed. An algorithm and a theoretical analysis are provided for the corresponding strategies of the operator and owners. Simulations are conducted to illustrate the difference of network performance compared with the game without dishonest residual owners.

In this paper, we study virtual network embedding problem in hybrid data center networks (HDCN), where each top-on-rack switch is equipped with a directional antenna. Those antennas can dynamically construct a wireless network in the on-demand way, regarding to the current traffic flow. Hence, HDCN has a great potential to alleviate the over- subscription problem suffered by traditional data centers. However, how to embed virtual networks in HDCN while fully utilizing the benefits introduced by the wireless links remains as an open topic. To this end, we jointly consider virtual network embedding and the antenna scheduling. In particular, in our model, to some extend, over-subscription in links is acceptable. We first abstract the studied problem into an integer programming problem. Then we provide a heuristic algorithm to find sub- optimal solutions to the problem. Extensive simulation based evaluation has shown the great efficiency of the proposed algorithm, which makes it a promising solution for VNE in HDCN.

In this paper, we propose a data center network architecture, named fitted fat-tree. Fitted fat- tree provisions unique flexibility in the sense that its topology and performance can be tailored with great freedom. This flexibility allows the architecture to closely follow the demands of the traffic. Given that traffic localization is ubiquitous in today's data centers, the fitted fat-tree can find its wide applications because it can be configured to adapt to the localized traffic load. We first propose a simple and efficient way to profile the localized traffic in the data centers, and then fit the architecture into the profile.We design the topology of the fitted fat-tree, propose its addressing and routing schemes, analyze its cost, and evaluate its performance. Because of its fitted nature, the architecture delivers the same performance as the original fat-tree, but incurs significantly reduced cost, because it uses the network resource much more efficiently.

Congestion control is one of the most critical issues in Named Data Networking (NDN). Compared to traditional Internet, NDN has some new features: receiver-driven, in-network caching, hop-by-hop forwarding, etc. These new features pose new challenges for designing congestion control mechanism. Congestion in NDN is mainly caused by Data packets, thus, shaping the transmission rate of Interest packet can regulate the returning rate of Data packet. In this paper, we propose an Interest shaping mechanism to tackle congestion in NDN by controlling Interest packet transmission rate in an optimized way. We formulate the rate allocation problem as a global optimization problem via jointly considering congestion control and traffic management. In order to achieve traffic management objective, we add an extra term in utility function to penalize over-loaded links. By applying partial dual decomposition, we solve the optimization problem with a gradient-based algorithm and we prove that gradient-based algorithm converges to optimality of optimization. Then, we present a practical implementation of this algorithm. Finally, we conduct simulation in ndnSIM to evaluate performance of the proposed mechanism by comparing with other existing methods. Simulation results show that our proposed mechanism can achieve high ratio of satisfied Interest, low delay and packet drop rate. The proposed mechanism can also achieve fairness among flows though the link utilization may not be high.

Software-Defined Networking (SDN) greatly simplifies middlebox policy enforcement. Middleboxes need tag packet headers to avoid forwarding ambiguity on SDN switches. In this paper, we present a new attack, called middlebox-bypass attack, to breach SDN-based middlebox policy enforcement. Such an attack manipulates a compromised switch to locally tag attacking packets without handing them over to the attached middlebox for inspection. Existing SDN security solutions, however, cannot detect the middlebox-bypass attack under practical constraints of efficiency, robustness, and applicability. We design and implement FlowCloak, the first protocol for per-packet real-time detection and prevention of middlebox-bypass attacks. FlowCloak enables middleboxes to generate tags that are probabilistically unknown to an attacker and confines it to only random guessing. We propose a multi-tag verification technique to address the tradeoff between FlowCloak robustness and TCAM usage by tag verification rules on the egress switch. Experiment results show that dozens of verification rules can confine the attacking probability under 0.1 %. FlowCloak imposes only a 0.3 ms packet processing delay on middleboxes and no obvious delay on the egress switch.

Scalable, fine-grained access control for Internet-of-Things is needed in enterprise environments, where thousands of subjects need to access possibly one to two orders of magnitude more objects. Existing solutions offer all-or-nothing access, or require all access to go through a cloud backend, greatly impeding access granularity, robustness and scale. In this paper, we propose Heracles, an IoT access control system that achieves robust, fine-grained access control at enterprise scale. Heracles adopts a capability-based approach using secure, unforgeable tokens that describe the authorizations of subjects, to either individual or collections of objects in single or bulk operations. It has a 3-tier architecture to provide centralized policy and distributed execution desired in enterprise environments, and delegated operations for responsiveness of resource-constrained objects. Extensive security analysis and performance evaluation on a testbed prove that Heracles achieves robust, responsive, fine-Qrained access control in large scale enterprise environments.

Emerging innovative edge devices like drones, self-driving cars, phones/tablets and IoT nodes are revolutionizing our daily lives. Caching data among peer edge devices enables data sharing needed in many applications. In such applications, network scalability and node mobility bring many challenges. They change the topology and the resources in the network and make the network less robust. In this paper, we propose peer data caching strategies that consider the scale and mobility of these increasingly popular edge devices. We propose a grouping method creating a layered design to reduce the number of entities in each layer. We propose inter-group and intra-group optimization problems which proactively cache data onto best places to support robust and fast data access. We develop a 7-approximation algorithm for inter-group optimization and use uncapacitated facility location problems to solve intra-group optimization. We also transform the mobility of nodes into node behaviors to reduce the impact of mobility on the network. Our extensive simulation results show that our proposed strategies can apply to large-size and high-mobility networks, while achieving satisfactory results for data access.

Traffic locality is ubiquitously exploited in today's data centers. It allows network resources to be used more efficiently because traffic in data centers is adapted to the underlying network infrastructures. In this paper, we approach this problem from another direction, which is to adapt network infrastructure to the traffic. Towards this direction, we adopt two approaches to boost the efficiency of network resource utilization. First, we improve the topology of Clos-type data center networks by introducing horizontal connections, which facilitates the routing of local traffic. Second, based on the improved topology, we make the network infrastructure to be versatile, in the sense that it can be fitted into the characteristics of the traffic. We name this design as Versatile Clos-type Networks (VCN). We describe the topological architecture of the VCN, design its addressing and routing schemes, and demonstrate its various properties. We also evaluate its performance and compare it with fat-tree, a representative Clos-type data center network architecture. The evaluation results show that the VCN can deliver the same throughput as fat-tree, but use significantly reduced network resources.

This paper studies a data gathering problem in a wireless sensor network containing multiple private residual subnetworks. The interaction between the wireless sensor network operator and the owners of residual sub-networks is modeled by a Stackelberg game, which forms a novel framework for jointly analyzing the pricing, gathering data, and planning routes. It is shown that the game has a unique Stackelberg equilibrium at which the wireless sensor network operator sets prices to minimize total cost, while owners of residual sub-networks respond accordingly to maximize their utilities subject to their bandwidth constraints. An algorithm and theoretical analyses are provided for the corresponding strategies of the operator and owners, and validated by extensive simulations. It is demonstrated that the algorithm achieves lower network cost compared with existing data gathering strategies.

The recent development of network function virtualization decouples network functions from dedicated hardware. Thus, virtual network functions (VNFs) can be distributed onto shared and virtualized platforms held by multiple data centers in various network locations. The architecture of the distributed VNFs interconnected by virtual links is denoted as the Service Function Chain (SFC). SFC has the potential to significantly reduce the opening and operating cost of the network services while improving the flexibility. However, the availability of SFC on chained up data centers is always inferior to that of network functions running on a single data center because the failure in any data center on the chain may affect its availability. To improve the availabilities of SFCs, in this paper we propose a local rerouting strategy to bypass the failed data centers on SFCs using locally rerouted paths (LRPs). Furthermore, we formulate an optimization model to minimize the maximum load on links while deploying SFCs and LRPs into the network. Thus, we reduce the potential risk of congested links caused by the local rerouting strategy. We then propose a randomized rounding approximation algorithm to solve the optimization problem, preserving the competitive ratio of O(logn) for the model. We also propose a fast heuristic algorithm to improve the efficiency. Our extensive simulation results show that the proposed algorithms can provide highly available SFCs with more balanced link load.

Data-centric networks provide content instead of address (what vs. where) based communication primitives, and have been argued to be the proper candidate for data dissemination in high mobility vehicular networks (e.g., delivering road side accident video clips to affected drivers in both directions). However, current Medium Access Control (MAC) layers filter incoming frames based on destination addresses, not content. The data-centric network community has resorted to MAC broadcast, with high and greatly varying frame loss rates. We propose V-MAC, a data-centric MAC layer that filters frames by content. It supports one to many multicast at MAC level, and ensures a uniform and controllable small frame loss rate across all receivers, despite their varying reception qualities. We have created a V-MAC prototype using Raspberry Pis and WiFi dongles. Experiments under extremely noisy environment show that it reduces frame loss from 50% (broadcast) to less than 10%, and consistently among multiple receivers.

In this paper, we propose a shortest travel route planning scheme that takes into account the spatial characteristics of wireless transmissions for mobile data gathering in wireless sensor networks. We formulate the shortest travel route problem (STRP) as a covering salesman problem (CSP), which is regarded as a mixed integer nonlinear programming and also as a non- convex programming problem. To solve the STRP problem, we propose a heuristic algorithm named decomposition algorithm (DA), which decomposes the STRP problem into two subproblems: access sequence problem and position determining problem. We conduct extensive simulation to verify the effectiveness of the proposed algorithm and show that the DA algorithm can plan the shortest travel route in large scale WSNs other than small scale WSNs by the classical traveling salesman problem (TSP) algorithms.

The emerging software defined networking enables the separation of control plane and data plane and saves the resource consumption of the network. Breakthrough in this area has opened up a new dimension to the design of software defined method in wireless sensor networks (WSNs). However, the limited routing strategy in software defined WSNs (SDWSNs) imposes a great challenge in achieving the minimum traffic load. In this paper, we propose a flow splitting optimization (FSO) algorithm for solving the problem of traffic load minimization (TLM) in SDWSNs by considering the selection of optimal relay sensor node and the transmission of optimal splitting flow. To this end, we first establish the model of different packet types and describe the TLM problem. We then formulate the TLM problem into an optimization problem which is constrained by the load of sensor nodes and the packet similarity between different sensor nodes. Afterwards, we present a Levenberg-Marquardt algorithm for solving the optimization problem of traffic load. We also provide the convergence analysis of the Levenberg-Marquardt algorithm. Finally, we implement the FSO algorithm in the NS-2 simulator and give extensive simulation results to verify the efficiency of FSO algorithm in SDWSNs.

With the development of sensing technology, smartphones can provide various kinds of data, including inertial sensing data, WiFi data, depth data, and images. These data make it possible to construct accurate indoor floor plans that are the critical foundations of flourishing indoor location-based services for smartphone. However, even with the popular crowdsourcing approach, the wide construction of indoor floor plans has not yet to be realized due to the intensive time consumption. In this paper, we utilize deep learning techniques to build PlanSketcher, a system that enables one user to construct fine-grained and facility-labeled indoor floor plans accurately. First, the proposed system extracts novel integrated features to recognize diverse landmarks. Second, traverse-independent hallway topologies are constructed based on the sensing data, depth data, and images through the proposed hallway construction algorithms. Finally, PlanSketcher constructs the room shape and labels recognized facilities in their corresponding positions to generate a complete indoor floor plan. Because PlanSketcher exploits different kinds of data collected from smartphones with new feature extraction method, it can obtain accurate indoor floor plan topology and facility labels. We implement PlanSketcher and conduct extensive experiments in three large indoor settings. The evaluation results show that the 90th percentile accuracy of positions and orientations of facilities are 1 m–2.5 m and 4°–6°, while 85%–95% facilities are recognized and labeled precisely.

With the proliferation of mobile devices, indoor fingerprinting-based localization has caught considerable interest on account of its high precision. Meanwhile, channel state information (CSI), as a promising positioning characteristic, has been gradually adopted as an enhanced channel metric in indoor positioning schemes. In this paper, we propose a CSI amplitude fingerprinting-based localization algorithm in Narrowband Internet of Things system, in which we optimize a centroid algorithm based on CSI propagation model. In particular, in the fingerprint matching, we utilize the method of multidimensional scaling (MDS) analysis to calculate the Euclidean distance and time-reversal resonating strength between the target point and the reference points and then employ the K-nearest neighbor (KNN) algorithm for location estimation. By conjugate gradient method, moreover, we optimize the localization error of triangular centroid algorithm and combine the positioning result with MDS and KNN's estimated position to get the final estimated position. Experiment results show that compared to some existing localization methods, our proposed algorithm can effectively reduce positioning error.

Accurate digital maps play a crucial role in various location-based services and applications. However, store information is usually missing or outdated in current maps. In this paper, we propose CrowdGIS, an automatic store selfupdating system for digital maps that leverages street views and sensing data crowdsourced from mobile users. We first develop a new weighted artificial neural network to learn the underlying relationship between estimated positions and real positions to localize user's shooting positions. Then, a novel text detection method is designed by considering two valuable features, including the color and texture information of letters. In this way, we can recognize complete store name instead of individual letters as in the previous study. Furthermore, we transfer the shooting position to the location of recognized stores in the map. Finally, CrowdGIS considers three updating categories (replacing, adding, and deleting) to update changed stores in the map based on the kernel density estimate model. We implement CrowdGIS and conduct extensive experiments in a real outdoor region for 1 month. The evaluation results demonstrate that CrowdGIS effectively accommodates store variations and updates stores to maintain an up-to-date map with high accuracy.

In mobile wireless sensor networks (MWSNs), scavenging energy from ambient radio frequency (RF) signals is a promising solution to prolonging the lifetime of energy-constrained relay nodes. In this paper, we apply the Simultaneous Wireless Information and Power Transfer (SWIPT) technique to a MWSN where the energy harvested by relay nodes can compensate their energy consumption on data forwarding. In such a network, how to maximize system energy efficiency (bits/Joule delivered to relays) bytrading off energy harvesting and data forwarding is a critical issue. To this end, we design a resource allocation (ResAll) algorithm by considering different power splitting abilities of relays undertwo scenarios. In the first scenario, the power received by relays is split into a continuous set of power streams with arbitrary power splitting ratios. In the second scenario, the received power is only split into a discrete set of power streams with fixed power splitting ratios. For each scenario above, we formulate the ResAll problem in a MWSN with SWIPT as a non-convex energy efficiency maximization problem. By exploiting fractional programming and dual decomposition, we further propose a cross-layer ResAll algorithm consisting of subalgorithms for rate control, power allocation, and power splitting to solve the problem efficiently and optimally. Simulation results reveal that the proposed ResAll algorithm converges within a small number of iterations, and achieves optimal system energy efficiency by balancing energy efficiency, data rate, transmit power, and power splitting ratio.

The application of wireless charging technology in traditional battery-powered wireless sensor networks (WSNs) grows rapidly recently. Although previous studies indicate that the technology can deliver energy reliably, it still faces regulatory mandate to provide high power density without incurring health risks. In particular, in clustered WSNs there exists a mismatch between the high energy demands from cluster heads and the relatively low energy supplies from wireless chargers. Fortunately, solar energy harvesting can provide high power density without health risks. However, its reliability is subject to weather dynamics. In this paper, we propose a hybrid framework that combines the two technologies - cluster heads are equipped with solar panels to scavenge solar energy and the rest of nodes are powered by wireless charging. We divide the network into three hierarchical levels. On the first level, we study a discrete placement problem of how to deploy solar-powered cluster heads that can minimize overall cost and propose a distributed 1:61(1+ϵ)2-approximation algorithm for the placement. Then, we extend the discrete problem into continuous space and develop an iterative algorithm based on the Weiszfeld algorithm. On the second level, we establish an energy balance in the network and explore how to maintain such balance for wireless-powered nodes when sunlight is unavailable. We also propose a distributed cluster head re-selection algorithm. On the third level, we first consider the tour planning problem by combining wireless charging with mobile data gathering in a joint tour. We then propose a polynomial-time scheduling algorithm to find appropriate hitting points on sensors' transmission boundaries for data gathering. For wireless charging, we give the mobile chargers more flexibility by allowing partial recharge when energy demands are high. The problem turns out to be a Linear Program. By exploiting its particular structure, we propose an efficient algorithm that can achieve near-optimal solutions. Our extensive simulation results demonstrate that the hybrid framework can reduce battery depletion by 20 percent and save vehicles' moving cost by 25 percent compared to previous works. By allowing partial recharge, battery depletion can be further reduced at a slightly increased cost. The results also suggest that we can reduce the number of high-cost mobile chargers by deploying more low-cost solar-powered sensors.

Interconnection networks lie in the heart of all types of parallel architectures, because how processors or memory modules are connected to each other has a significant impact on the scalability, reliability, cost and performance. For example, a nonblocking interconnection network delivers guaranteed path availability to any connection requests, without interference to existing connections. Also, an interconnection network with multicast capability can distribute data from a single source to all the destinations in a one-shot manner, eliminating unnecessary duplications and minimizing communication delays. However, implementing nonblocking multicast networks imposes great challenges to designers because both of them demand high hardware cost. To deal with this problem, in this paper we propose a novel interconnection network, named Multicast Capable Low-cost Network (MCL), which is both nonblocking for multicast traffic and cost-efficient. We first design the topologies and routing algorithms for MCL, and then prove its nonblocking multicast properties. Most importantly, we show that MCL achieves the lowest hardware cost in terms of asymptotic number of crosspoints. Specifically, the theoretical upper bound on the crosspoints of an N × N MCL is O(N log3.39N). The explicitly constructed instance of an N × N MCL has a cost of O(N5/4) and constant delay from the input ports to the output ports. These theoretical and practical costs are both the lowest compared to previous designs which deliver the same performance.

Designing a cost-effective network for data centers that can deliver sufficient bandwidth and provide high availability has drawn tremendous attentions recently. In this paper, we propose a novel server-centric network structure called RCube, which is energy efficient and can deploy a redundancy scheme to improve the availability of data centers. Moreover, RCube shares many good properties with BCube, a well known server-centric network structure, yet its network size can be adjusted more conveniently. We also present a routing algorithm to find paths in RCube and an algorithm to find multiple parallel paths between any pair of source and destination servers. In addition, we theoretically analyze the power efficiency of the network and availability of RCube under server failure. Our comprehensive simulations demonstrate that RCube provides higher availability and flexibility to make trade-off among many factors, such as power consumption and aggregate throughput, than BCube, while delivering similar performance to BCube in many critical metrics, such as average path length, path distribution and graceful degradation, which makes RCube a very promising empirical structure for an enterprise data center network product.

As the advanced development of directional antenna, wireless technique has been introduced into data center networks, denoted as hybrid data center networks (HDCN). HDCN shows its great potential to mitigate the over-subscription problem in higher level links in traditional data centers.However, how to implement network virtualization in HDCN such that all the wireless links can be sufficiently utilized remains a challenging problem. In this paper, we study virtual network embedding problem in HDCN, by jointly considering embedding virtual networks and scheduling the directional antennas. We first summarize this problem intoan integer programming problem, then propose a heuristic algorithm to find a near optimal solution for the studied problem. The simulation based evaluation shows the great efficiency for the proposed algorithm deriving a suboptimal solution in HDCN.

Interconnection networks lie at the heart of parallel processing architectures for big data, because the way that machines, processors or memory modules connected to each other has a significant effect on the scalability, reliability, cost and performance. For example, an interconnection network with multicast capability can distribute data from a single source to all the destinations in a one-shot manner, eliminating unnecessary duplications and minimizing communication delays. Also, a nonblocking interconnection network delivers guaranteed path availability to any connection requests, without interference to existing connections. However, implementing multicast nonblocking networks imposes great challenges to designers because both of them demand high hardware cost. To deal with this problem, we propose a novel type of interconnection network, named Multicast Capable Low-cost Network (MCL), which is both nonblocking for multicast traffic and cost efficient. We first design the topologies and routing algorithms for MCL, and then prove its multicast nonblocking properties. Most importantly, we show that MCL achieves outstanding cost efficiency. To be specific, our explicitly constructed MCL has the cost of O(N 5 4 ). This hardware cost achieves a new record low, comparing to previous solutions which deliver the same performance.

Virtual network embedding has been widely studied for decades in backbone network, as it provides a promising way to resolve the conflict between flexibility of higher layer applications and rigidity of lower layer hardware, by allowing multiple heterogeneous virtual networks designed for different big data services to coexist and share the same infrastructure underneath. On the other hand, as the advanced development of directional antenna, wireless technique has also been introduced into data center networks, denoted as hybrid data center networks (HDCN). HDCN shows its great potential to mitigate the over-subscription problem in higher level links in traditional data centers. However, how to implement network virtualization in HDCN such that all the wireless links can be sufficiently utilized remains a challenging problem. In this paper, we study virtual network embedding problem in HDCN environment, by jointly considering embedding virtual networks and scheduling the directional antennas. We first summarize this problem into an integer programming problem, then propose a heuristic algorithm to find solutions to this problem. Extensive simulations reveal that the proposed algorithm efficiently provides a near-optimal solution. These features make it a promising VNE solution to HDCN environment.

With the explosive expansion of data centers, a huge amount of identical or similar data are usually requested repeatedly over networks by users, which causes serious waste of network bandwidth, and further increases network energy consumption remarkably. Existing solutions achieve energy saving by increasing network link capacity as well as eliminating the data redundancy in routers. However, such redundancy elimination (RE) causes the increase of router's energy consumption. To solve this problem, we propose a flow preemption routing scheme with RE called RE-FPR. RE-FPR scheme uses software defined networking (SDN) technology to select different routing paths for flows and control RE function on the corresponding router under two modes, i.e., traffic peak and traffic valley. We then formulate the RE-FPR problem as a power consumption minimization problem. Furthermore, we solve the optimization problem by using the maximum entropy principle and propose the RE-FPR algorithm. The simulation results show that RE-FPR algorithm outperforms the traditional flow scheduling algorithms in terms of flow completion time and number of active RE- routers / links.

Edge devices (e.g., smartphones, tablets, connected vehicles, IoT nodes) with sensing, storage and communication resources are increasingly penetrating our environments. Many novel applications can be created when nearby peer edge devices share data. Caching can greatly improve the data availability, retrieval robustness and latency. In this paper, we study the unique issue of caching fairness in edge environment. Due to distinct ownership of peer devices, caching load balance is critical. We consider fairness metrics and formulate an integer linear programming problem, which is shown as summation of multiple Connected Facility Location (ConFL) problems. We propose an approximation algorithm leveraging an existing ConFL approximation algorithm, and prove that it preserves a 6.55 approximation ratio. We further develop a distributed algorithm where devices exchange data reachability and identify popular candidates as caching nodes. Extensive evaluation shows that compared with existing wireless network caching algorithms, our algorithms significantly improve data caching fairness, while keeping the contention induced latency similar to the best existing algorithms.

In recent years, mobile data gathering in wireless sensor networks has attracted much interests in the research community. However, despite extensive efforts, many of previous work in this area lies only in theory and evaluates network performance with computer simulations, which leaves a large gap from reality. In this paper, we present the design and implementation of a general purpose, flexible platform for mobile data gathering in wireless sensor networks to evaluate network performance and algorithms in a practical setting. Instead of relying on hand-crafted theoretical models, our platform integrates both mobile data collector and sensor nodes to provide realistic performance evaluations. In addition, the platform adopts a modular design in mobile data collector and sensor nodes, and equips the mobile data collector with advanced computing capability, which makes it versatile for evaluating the performance of a wide-range of applications. Finally, as a case study, weimplement a wildlife monitoring system on our platform. Our experimental results demonstrate that real implementations can evaluate many practical performance factors which would have a great impact on the sensing results and are very difficult to fully capture by theoretical models and simulations. We expect that this platform can become a very powerful general tool for more accurate network simulations and facilitate performance optimization in wireless sensor networks.

The proliferation and daily congregation of modern mobile devices have created abundant opportunities for peer edge devices to share valuable data with each other. The short contact durations, relatively small sharing sizes, and uncertain data availability, demand agile, light weight peer based data sharing. In this paper, we propose Peer Data Sharing (PDS) that enables edge devices to discover which data exist in nearby peers, and retrieve interested data robustly and efficiently. PDS uses novel lingering queries, mixedcast and en-route message rewriting techniques to minimize redundant transmissions and maximize opportunistic overhearing thus caching in data discovery and retrieval. Extensive evaluations based on an Android prototype show that PDS discovers and retrieves almost 100% data in tens of seconds, and remains robust despite wireless contention, simultaneous consumer requests and user mobility.

Energy remains a major hurdle in running computation-intensive tasks on wireless sensors. Recent efforts have been made to employ a Mobile Charger (MC) to deliver wireless power to sensors, which provides a promising solution to the energy problem. Most of previous works in this area aim at maintaining perpetual network operation at the expense of high operating cost of MC. In the meanwhile, it is observed that due to low cost of wireless sensors, they are usually deployed at high density so there is abundant redundancy in their coverage in the network. For such networks, it is possible to take advantage of the redundancy to reduce the energy cost. In this paper, we relax the strictness of perpetual operation by allowing some sensors to temporarily run out of energy while still maintaining target k-coverage in the network at lower cost of MC. We first establish a theoretical model to analyze the performance improvements under this new strategy. Then we organize sensors into load-balanced clusters for target monitoring by a distributed algorithm. Next, we propose a charging algorithm named λ-GTSP Charging Algorithm to determine the optimal number of sensors to be charged in each cluster to maintain k-coverage in the network and derive the route for MC to charge them. We further generalize the algorithm to encompass mobile targets as well. Our extensive simulation results demonstrate significant improvements of network scalability and cost saving that MC can extend charging capability over 2-3 times with a reduction of 40% of moving cost without sacrificing the network performance.

Designing a cost-effective network for data centers that can deliver sufficient bandwidth and provide high availability has drawn tremendous attentions recently. In this paper, we propose a novel server-centric network structure called RCube, which is energy efficient and can deploy a redundancy scheme to improve the availability of data centers. Moreover, RCube shares many good properties with BCube, a well known server-centric network structure, yet its network size can be adjusted more conveniently. We also present a routing algorithm to find paths in RCube and an algorithm to build multiple parallel paths between any pair of source and destination servers. In addition, we theoretically analyze the power efficiency of the network and availability of RCube under server failure. Our comprehensive simulations demonstrate that RCube provides higher availability and flexibility to make trade-off among many factors, such as power consumption and aggregate throughput, than BCube, while delivering similar performance to BCube in many critical metrics, such as average path length, path distribution and graceful degradation, which makes RCube a very promising empirical structure for an enterprise data center network product.

In this paper, we propose a novel data center network architecture named FFTree. Compared to widely adopted industrial solutions including fat-tree, this architecture can provide even higher aggregate bandwidth and richer path availability. Most importantly, FFTree provisions unique flexibility so that its topology and performance can be tailored with great freedom before its deployment. The fine granularity and wide dynamic range of its configurations allow FFTree to exactly fit and closely follow the time-variant demands of its applications. Also, this flexibility facilitates the reuse of network devices, so that upgrades could be achieved by rearranging existing switches, avoiding the expenditure on new generations of hardware in each upgrade cycle. Furthermore, this flexibility allows FFTree to be elaborately tuned into cost efficient zones in the sense that it provides higher bandwidth using less network devices, which leads to significant cost reduction. We design the network topologies of FFTree, propose a set of routing algorithms, and demonstrate its aforementioned features. We also analyze the performance and compare it with its predecessors. Technically, this architecture can be seen as a generalization of fat-tree, and is backward-compatible to fat-tree: it consists of commercial off-the-shelf network devices, and the whole system can cooperate with the hosts running Ethernet and IP. We believe FFTree is ready to be deployed in industry, as a perfect replacement of the classic fat-tree.

Multicast can not only shorten task completion time of applications, but also effectively reduce overall bandwidth consumption in data center networks (DCNs). However, load imbalance and sudden link blocking will seriously impact the network performance owing to the fundamental characteristics of huge traffic in DCNs. To address this problem, in this paper, we propose a novel multicast scheduling algorithm in software defined fat-tree DCNs, which can improve network performance by reducing the blocking of multicast traffic. In particular, the multicast scheduling algorithm selects the minimum blocking cost of links as optimal paths. By our scheduling algorithm, multicast flows are evenly distributed over the available links so as to achieve load balance. In addition, the DCNs are controlled globally by the software defined networking (SDN) technology, therefore, the multicast traffic cannot be interfered by the unexpected flow requests. Furthermore, the multicast scheduling algorithm can lead to asymptotically minimum network blocking probability, and has a low time complexity. Simulation results verify the effectiveness of our proposed multicast scheduling algorithm in different network traffic intensities.

The rapid penetration of mobile devices has provided ample opportunities for mobile devices to exchange sensing data on a peer basis without any centralized backend. In this paper, we design a peer based data exchanging model, where relay nodes move to certain locations to connect data providers and consumers to facilitate data delivery. Both relays and data providers can gain rewards from consumers who are willing to pay for the data. We first prove the problem of relay node assignment is NP-hard, and provide a centralized optimal method to decide which relay nodes goes to which location with an approximation ratio. Then we define an autonomous compensation game to allow relays make individual decisions without any central authority. We derive a sufficient and necessary condition for the existence of Nash equilibrium. We analyze and compare this distributed game to the centralized social optimal solution, and show that the game incurs small bounded social costs, and efficient under various network sizes, numbers of providers, consumers, and device mobility.

Multicast can improve network performance by eliminating sending unnecessary duplicated flows in the data center networks (DCNs), thus it can significantly save network bandwidth and improve the network Quality of Service (QoS). However, the network multicast blocking causes the retransmission of a large number of data packets, and seriously influences the traffic efficiency of data center networks, especially for the multicast traffic in the fat-tree DCNs owing to multi-rooted tree structure. In this paper, we propose a novel multicast scheduling strategy to reduce the network multicast blocking. In order to decrease the operation time of the proposed algorithm, therefore, the remaining bandwidth the selected uplink connecting to available core switch should be close to and greater the three times than the bandwidth of multicast requests. Then the blocking probability of downlink at next time-slot is calculated by using markov chain theory. Furthermore, we select the downlink with minimum blocking probability as the optimal path at next time slot. In addition, theoretical analysis shows that the blocking probability of scheduling algorithm is close to zero and has lower time complexity. Simulation results verify the effectiveness of our proposed multicast scheduling algorithm.

With the development of distributed energy generators and storages, the sustainability of a microgrid comprised of multiple electricity users is significantly increased. Maximizing the efficiency of generated renewable energy is vital to running a sustainable microgrid as it indicates reducing the usage of thermal electricity purchased from the macrogrid. To this end, the excessive renewable energy of a user should be shared with others who are short of energy. Unfortunately, coordinating the transfers of renewable energy among the users in a microgrid is particularly difficult, given the rational nature of users, the stochastic nature of renewable energy and the dynamic nature of energy demand of each user. In this paper, we consider the coupled problem of maximizing the renewable energy efficiency of a sustainable microgrid as well as stimulating rational users to share excessive renewable energy. We propose a near-optimal scheduling algorithm, which determines the amounts of renewable energy transferred among users in an online fashion. We also design an efficient pricing mechanism for the trade of energy among users based on double auction. We rigorously prove that our online scheduling algorithm is approximately optimal and the pricing mechanism guarantees the property of individual rationality of users. Comprehensive simulation results demonstrate the efficacy of our online algorithm and incentive mechanism.

Summary Multicast traffic scheduling in data center networks can not only improve network efficiency but also save network resources. However, the existing multicast scheduling algorithms cannot appropriately schedule flows to achieve traffic load balance so that the network may occur heavy blocking. This prevents the full utilization of high degree of link parallelism and causes unpredictable reduction of network performance. To address the problem, in this paper, we propose a blocking cost‐driven multicast scheduling algorithm by using optimization theory in fat‐tree data center networks. In particular, a model of multicast traffic subnetwork is established on the basis of the blocking probability of available paths at next time slot, which can reflect the blocking characteristics of multicast network and predict network state at next time slot. With the multicast blocking model, we derive the minimum blocking probability of multicast subnetworks, denoted as blocking cost. In addition, the algorithm can select the multicast subnetwork with minimum blocking cost to transfer multicast flows. Time complexity analysis and simulation results demonstrate the effectiveness and efficiency of our proposed multicast scheduling algorithm for different network traffic intensities.

Wireless charging has provided a convenient alternative to renew nodes' energy in wireless sensor networks. Due to physical limitations, previous works have only considered recharging a single node at a time, which has limited efficiency and scalability. Recent advances on multi-hop wireless charging is gaining momentum and provides fundamental support to address this problem. However, existing single-node charging designs do not consider and cannot take advantage of such opportunities. In this paper, we propose a new framework to enable multi-hop wireless charging using resonant repeaters. First, we present a realistic model that accounts for detailed physical factors to calculate charging efficiencies. Second, to achieve balance between energy efficiency and data latency, we propose a hybrid data gathering strategy that combines static and mobile data gathering to overcome their respective drawbacks and provide theoretical analysis. Then, we formulate multi-hop recharge schedule into a bi-objective NP-hard optimization problem. We propose a two-step approximation algorithm that first finds the minimum charging cost and then calculates the charging vehicles' moving costs with bounded approximation ratios. Finally, upon discovering more room to reduce the total system cost, we develop a post-optimization algorithm that iteratively adds more stopping locations for charging vehicles to further improve the results while ensuring none of the nodes will deplete battery energy. Our extensive simulations show that the proposed algorithms can handle dynamic energy demands effectively, and can cover at least three times of nodes and reduce service interruption time by an order of magnitude compared to the single-node charging scheme.

Virtualization is an essential step before a bare-metal data center being ready for commercial usage, because it bridges the foreground interface for cloud tenants and the background resource management on underlying infrastructures. A concept at the heart of the foreground is multi-tenancy, which deals with logical isolation of shared virtual computing, storage, and network resources and provides adaptive capability for heterogeneous demands from various tenants. A crucial problem in the background is load balancing, which affects multiple issues including cost, flexibility and availability. In this work, we propose a virtualization framework that consider these two problems simultaneously. Our framework takes advantage of the flourishing application of distributed virtual switch (DVS), and leverages the blooming adoption of OpenFlow protocols. First, the framework accommodates heterogeneous network communication patterns by supporting arbitrary traffic matrices among virtual machines (VMs) in virtual private clouds (VPCs). The only constraint on the network flows is that the bandwidth of a server's network interface. Second, our framework achieves load balancing using an elaborately designed link establishment algorithm. The algorithm takes the configurations of the bare-metal data center and the dynamic network environment as inputs, and adaptively applies a globally bounded oversubscription on every link. Our framework concentrates on the fat-tree architecture, which is widely used in today's data centers.

As air pollution is becoming a serious problem in developing nations, governments try to track and solve this problem by monitoring air pollution. With the proliferation of smartphones, mobile crowdsensing becomes a promising paradigm for monitoring fine-grained air pollution in urban areas. As existing studies have shown that pollutant concentrations have inherent spatiotemporal correlations, compressive sensing is an effective technology to reduce the amount of data collected through crowdsensing. In a practical crowdsensing application, incentives are expected by smartphone users for contributing sensing data. However, how to design incentives to collect high- quality sensing data with low costs is difficult in compressive crowdsensing. In this work, we propose an iterative scheme for the process of crowdsensing-based air pollution monitoring, where incentives are updated online according to the distribution of collected sensing data. Comprehensive simulations have been conducted to demonstrate the efficacy of our proposed scheme.

Despite significant research efforts and great advances on Mobile CrowdSensing (MCS), building MCS applications remains difficult. In this paper, we develop and run Dining Halls on Live (DHOL), a campus dining population density monitoring system over several months. We make a holistic reality examination, discover key technical and practical difficulties, develop effective solutions and share our experiences and insights. We find two main obstacles on data fusion and incentive design: insufficient data quantity/quality and ``irrational'' user behavior. We develop effective methods by combining historical and real time data, and allocating a given budget among users to address them. We also conduct a detailed user survey to identify reasons behind interesting discoveries, important practical difficulties in acquiring sufficient users and location data, and share our experiences dealing with them. Our main insight is that insufficient data quantity/quality and ``irrational'' user behavior demand practical yet effective data fusion and incentive mechanisms, and one must provide values to users to acquire and retain a large user base.

In the simultaneous wireless information and power transfer (SWIPT) system, due to the broadcast nature of wireless radio, the energy receiver may act as a potential eavesdropper to eavesdrop the information sent to the information receiver. To address this issue, in this paper, we propose an optimization framework of target secrecy rate and power allocation ratio based on secrecy outage probability and effective secrecy throughput in the SWIPT system over fading wiretap channel. Firstly, we formulate the effective secrecy throughput maximization problem under the reliability constraint in the on-off and adaptive transmission modes, and provide the optimal target secrecy rate. Furthermore, we formulate the secrecy outage probability minimization problem and the average harvested energy maximization problem, respectively. By solving the two optimization problems, we propose the corresponding optimal power allocation policy. Finally, we provide numerical results to evaluate the performance of the proposed policy in effective secrecy throughput.

Virtualization is an essential step before a bare-metal data center being ready for commercial usage, because it bridges the foreground interface for cloud tenants and the background resource management on underlying infrastructures. A concept at the heart of the foreground is multi-tenancy, which deals with logical isolation of shared virtual computing, storage, and network resources and provides adaptive capability for heterogeneous demands from various tenants. A crucial problem in the background is load balancing, which affects multiple issues including cost, flexibility and availability. In this work, we propose a virtualization framework that considers these two problems simultaneously. Our framework takes advantage of the flourishing application of distribute virtual switch (DVS), and leverages the blooming adoption of OpenFlow protocols. First, the framework accommodates heterogeneous network communication pattern by supporting arbitrary traffic matrices among virtual machines (VMs) in virtual private clouds (VPCs). The only constraint on the network flows is the bandwidth of server's network interface. Second, our framework achieves load balancing using an elaborately designed link establishment algorithm. The algorithm takes the configurations of the bare-metal data center and the dynamic network environments as inputs, and dynamically applies a globally bounded oversubscription on every link. Our framework concentrates on the fat-tree architecture, which is widely used in today's data centers.

Interconnects play a critical role in various networking environments including data center networks, high performance computing systems, networks-on-chip, etc. An important design concern of interconnects is the hardware cost, especially when the scale increases. In order to achieve lower hardware cost, a lot of previous work leverages a tradeoff between the cost and the performance. In this paper, we alternatively propose a new type of recursively constructed multi-stage interconnect which is both cost efficient and performance guaranteed. The proposed interconnect can deliver the same communication pattern support and path availability as previous designs, yet at the same time achieves lower hardware complexity. We first design a prototype (or base case) for the new interconnect, which consists of three stages of switching modules. Then we use this prototype to decompose and replace the switching modules repeatedly and obtain the recursive case of our interconnect. The hardware cost of the recursively constructed interconnect can be significantly reduced, meanwhile the communication pattern support and path availability are perfectly preserved. For both the base case and the recursive case, we study the properties of the network topology, propose routing algorithms, give performance analysis and calculate cost. We show that the interconnect reduces the hardware cost from the previously best known result O(N3/2), where N is the number of input or output nodes of the interconnect, to O(N11/1-2δ log1.585N), where δ is a small value approaching zero when N increases.

Recent years have witnessed a growing interest in localization algorithms for wireless ad hoc networks. In most localization algorithms, increasing the density of anchor nodes is one of the main strategies to improve the localization accuracy in dense networks. In this paper, based on the number of reference nodes, we propose a distributed localization algorithm, i.e., history based multi-node collaborative localization algorithm (HMCL), which provides a potential approach for localization in sparse ad hoc wireless networks. In the proposed HMCL algorithm, we exploit a new motion model to filter the imprecise estimation values based on the historical position information of nodes, which can improve the localization accuracy and reduce the computation overhead and energy consumption. Moreover, we utilize different strategies to achieve the localization of nodes with different priorities measured by the distance information between neighbor nodes. We verify through experiment that the proposed algorithm provides better performance in terms of localization precision and energy consumption. Besides, we also analyze the effect of the number of neighbor nodes, node density and moving speed of nodes on localization precision.

Cooperative cognitive radio (CCR) is a novel paradigm for improving both radio spectrum efficiency and communication quality. However, for the CCR networks with energy harvesting, how to achieve specific relay selection is still an open issue. In this paper, we consider a CCR network with energy harvesting in which multiple secondary transmitters are able to harvest energy from the received signals to serve their own receivers and primary transmitters. Furthermore, we propose two relay selection schemes, i.e., single relay selection and multiple relay selection, by considering harvested energy and analyze the outage probability for both schemes over Nakagami-m fading channels. Simulation results validate our analysis on outage performance and compare the effects of the number of selected relays, energy harvesting ratio and transmission phase division ratios on two schemes in terms of outage probability. different parameters.

Digital garage maps are the basis for future vehicle navigation services such as smart parking management that displays the availability of parking spaces. It can direct drivers to empty ones, avoiding any searching, circulating in large, complex parking structures. However, such maps are not currently available, making it impossible to deploy smart parking management. Conducting manual survey incurs tremendous amount of human efforts, and cannot scale to large numbers of garages. In this paper, we propose three algorithms, Sequential Merging, Points Clustering and Segments Matching that can automatically construct complete and accurate garage maps using data crowdsensed from drivers. Upon entering and leaving the garage, the driver's smartphone collects inertial data, which are used to generate the vehicle's trajectory. Our algorithms fuse together these trajectories to recreate the size, layout of the garage. We compare the performance of the three algorithms using different garages. We find that Points Clustering is robust to trajectory errors, with F-score above 0.95 for trajectory length error up to 2 meters, Segments Matching can handle partial trajectories with arbitrary start/end locations, and it constructs the same map using trajectories much shorter than those needed by the other two algorithms.

With the development of renewable energy generators and electricity storages, microgrids become a promising technology of the smart grid. Maximizing the usage of renewable energy is vital to running a microgrid as it indicates reduction of the usage of thermal electricity purchased from the macrogrid. To this end, the excessive renewable energy of a user should be transferred to other users who need energy. Unfortunately, coordinating the transfers of renewable energy among the users in the microgrid is particularly difficult due to the stochastic nature of renewable energy, and the dynamic energy demand of each user. In this paper, we consider the problem of maximizing the long-term renewable energy usage by exchanging excessive renewable energy among users in a microgrid. We propose an online control algorithm which determines the amounts of renewable energy transferred among users in an online fashion. We rigorously prove that our online control algorithm is approximately optimal. We have conducted comprehensive simulation results that demonstrate the efficacy of our online algorithm.

The redundancy of sensing data in wireless sensor networks (WSNs) gives rise to longer transmission delays and more energy consumption. In this paper, we focus on the energy-efficient data redundancy elimination and compression with the objective of recovering the original data. To balance aggregation load of a large-scale WSN, we propose a novel energy-efficient dynamic clustering algorithm by utilizing spatial correlation, which can achieve a distributed compressive data aggregation in each cluster head. Furthermore, we propose a distributed fast data compression approach based on eliminable lifting wavelet to reduce the amount of raw data. Also, it offers high fidelity recovery for the raw data. Extensive experimental results demonstrate that our clustering method based on data correlation clustering (CDSC) for data aggregation outperforms other methods on prolonging network lifetime and reducing the amount of data transmitted. In particular, our data compression aggregation algorithm can achieve 98.4% recovery accuracy when the compression ratio equals 1.3333.

In wireless sensor networks (WSNs), there usually exist spatial overlap and data correlation among sensors. Reducing data redundancy is crucial for prolonging network lifetime inWSNs. Source coding is an effective method for data aggregation to reduce data redundancy. However, source coding was regarded as an independent problem in previous work. Little work pays attention to optimal coding rate and associates it with underlying protocols. In this paper, we adopt Slepian-Wolf theorem to achieve the boundary of coding rate, and propose a cross-layer optimization framework to give the optimal source coding rate and flow allocation. We seek to establish a structure-free, multipath transmission model. To the best of our knowledge, this is the first work to solve the optimal source coding rate allocation problem in WSNs. Our extensive simulation results demonstrate that the proposed framework can reduce network traffic and extend network lifetime significantly.

Network virtualization is the enabling technology for sharing resources on cloud. The efficiency of virtual network embedding determines the expense and revenue ratio of a data center. In this paper, we consider the virtual network embedding problem in fat-tree data centers. We design various schemes to embed Nonblocking Multicast Virtual Networks (NMVNs) which are dedicated to deliver premium experience to cloud users. In each NMVN, there is a free combination of virtual machines selected from variable sizes. The bottleneck of communications between these virtual machines is removed so that they can always send data at full bandwidth of their network interface, even if data is simultaneously sent to multiple destinations. In addition, the high performance of NMVNs is guaranteed at the wellcontrolled low network hardware cost. We design two embedding schemes for NMVNs, named Static NMVN Embedding (SNE) and Dynamic NMVN Embedding (DNE). Both schemes support the nonblocking properties for multicast. Besides, each of the two schemes has its unique features. The SNE scheme provides an interference-free solution, in the sense that a virtual network is not aware of the existence of other virtual networks during its lifetime. The DNE scheme has lower hardware cost than SNE and provides higher flexibility to cloud users by possible reconfigurations when necessary. Additionally, we show through theoretical analysis and simulations to validate that the overhead of DNE is minimal thus acceptable to most cloud applications.

In this paper, we propose a novel server-centric network for data centers, called RRect. Compared to existing server-centric networks, RRect has a linear diameter to the network order and abundant parallel paths with near-equal lengths, so that traffic in RRect enjoys a short and predictable communication latency. We present an efficient routing algorithm to find paths between any pair of servers in RRect. A complete addressing scheme and recursive RRect construction procedure are also provided in this paper. Meanwhile, to meet today's stringent high availability requirement, unlike existing server-centric network structures, RRect can be configured into redundancy and failover scheme, in which the backup server can fully take the place of the corresponding malfunctioning server without losing topological advantages, such as multiple near-equal parallel paths. Our comprehensive simulations show that RRect gives a better average path lengths and a more balanced path distribution among all pairs of servers. Meanwhile, RRect can maintain the same performance on many critical metrics as BCube, including short diameter and excellent aggregate throughput. All these features make RRect a very empirical structure for enterprise dater center network products.

HyperLogLog Counting is widely used in cardinality estimation. It is the foundation of many algorithms in data analysis, commodity recommendation and database optimization. Facing the large scale internet business like electronic commerce, internet companies have an urgent requirement of distributed real-time cardinality estimation with high accuracy and low time cost. In this paper, we propose a distributed real-time cardinality estimation algorithm named Hermes. Hermes adjusts the estimated cardinality dynamically according to the result of HyperLogLog Counting and also optimizes the data distribution strategy of existing distributed cardinality estimation algorithms. Experiments have been carried out and the results show that Hermes has lower estimation error and time cost compared with existing algorithms.

Mobile cloud computing (MCC) as an emerging and prospective computing paradigm, can significantly enhance computation capability and save energy of smart mobile devices (SMDs) by offloading computation-intensive tasks from resource-constrained SMDs onto the resource-rich cloud. However, how to achieve energy-efficient computation offloading under the hard constraint for application completion time remains a challenge issue. To address such a challenge, in this paper, we provide an energy-efficient dynamic offloading and resource scheduling (eDors) policy to reduce energy consumption and shorten application completion time. We first formulate the eDors problem into the energy-efficiency cost (EEC) minimization problem while satisfying the task-dependency requirements and the completion time deadline constraint. To solve the optimization problem, we then propose a distributed eDors algorithm consisting of three subalgorithms of computation offloading selection, clock frequency control and transmission power allocation. More importantly, we find that the computation offloading selection depends on not only the computing workload of a task, but also the maximum completion time of its immediate predecessors and the clock frequency and transmission power of the mobile device. Finally, our experimental results in a real testbed demonstrate that the eDors algorithm can effectively reduce the EEC by optimally adjusting the CPU clock frequency of SMDs based on the dynamic voltage and frequency scaling (DVFS) technique in local computing, and adapting the transmission power for the wireless channel conditions in cloud computing.

Recently, there have been a growing number of applications that power wireless sensor networks (WSNs) by wireless charging technology. Although previous studies indicate that wireless charging can deliver energy reliably, it still faces regulatory challenges to provide high power density without incurring health risks. In particular, in clustered WSNs there exists a mismatch between the high energy demands from cluster heads and the relatively low energy supplies that wireless charging can provide. Fortunately, solar energy harvesting can provide high power density which is also risk-free. However, it is subject to weather dynamics. Therefore, in this paper, we propose a hybrid framework that combines the two technologies - cluster heads are equipped with solar panels to scavenge solar energy and the rest of nodes are powered by wireless charging. First, we study a placement problem on how to deploy solar-powered cluster heads that can minimize overall cost and propose a distributed 1.61(1 + ϵ)2-approximation algorithm for the placement. Second, we establish an energy balance in the network and explore how to maintain such balance when sunlight is unavailable. Third, we consider combining wireless charging and mobile data gathering in a joint tour in such networks, and propose a polynomial-time scheduling algorithm. Our extensive simulation demonstrates that the hybrid framework can reduce battery depletion by 20% and save system cost by 25% compared to previous results.

In wireless sensor networks (WSNs), numerous sensors can produce a significant portion of the big data. It remains an open issue how to timely gather and transmit such large amount of data while minimizing data latency through wireless sensor networks (WSNs). On the other hand, spatially correlated sensor observations lead to considerable data redundancy in the network. To efficiently eliminate data redundancy and improve energy efficiency, in this paper, based on the fact that the more similar the measure data are, the smaller the amount of data after aggregation is, we first develop a new distributed clustering algorithm which can categorize sensor nodes with high similarity into a cluster for data aggregation, while ensuring uniform energy consumption within the cluster. Then, we propose a data aggregation algorithm based on principal component analysis (PCA) which can be executed in the cluster head (CH). Finally, our experimental results demonstrate that the amount of data transmission can be significantly reduced based on our proposed clustering and data aggregation algorithm.

This paper reveals an intrinsic relationship between secure cloud storage and secure network coding for the first time. Secure cloud storage was proposed only recently while secure network coding has been studied for more than ten years. Although the two areas are quite different in their nature and are studied independently, we show how to construct a secure cloud storage protocol given any secure network coding protocol. This gives rise to a systematic way to construct secure cloud storage protocols. Our construction is secure under a definition which captures the real world usage of the cloud storage. Furthermore, we propose two specific secure cloud storage protocols based on two recent secure network coding protocols. In particular, we obtain the first publicly verifiable secure cloud storage protocol in the standard model. We also enhance the proposed generic construction to support user anonymity and third-party public auditing, which both have received considerable attention recently. Finally, we prototype the newly proposed protocol and evaluate its performance. Experimental results validate the effectiveness of the protocol.

In wireless local area networks (WLANs), link-layer multicast is a promising technology for many multimedia applications, e.g., video streaming, as multicast frames can reach multiple clients simultaneously. However, the efficiency of multicast in WLANs is usually low since multicast frames are transmitted at a basic data rate to reach clients with poor channel quality. Moreover, the reliability of multicast cannot be guaranteed either, as multicast transmissions are not acknowledged. Some recent works have utilized smart antennas to improve multicast performance. However, most of them require customized hardware and are not designed for the latest IEEE 802.11 standard, 802.11n WLANs. More importantly, these works did not consider the impact of AP association strategies on the performance of link-layer multicast. In this paper, we study the problem of link-layer multicast in large-scale 802.11n WLANs where each AP is equipped with a smart antenna that supports multiple antenna patterns. Based on channel gains of various antenna patterns from different APs, we choose the associated AP for multicast clients, partition associated clients of each AP into multiple groups, select an antenna pattern and data rate for each group of client, and transmit multicast frames to each group once. We first examine the limitation of multicast in 802.11n WLANs and the benefits of smart antennas to multicast via experiments. We then introduce the system model and formulate the problem into an optimization problem, and prove its NP-hardness. The objective is to minimize the time to transmit a multicast frame to all clients while guaranteeing high packet reception ratio (PRR) for each client. For generic WLANs where APs are sparsely deployed, we propose an optimal algorithm under the condition that the PRR of antenna patterns and data rates are known for every client. For generic large-scale WLANs, we further propose an on-line algorithm in which the AP association strategy, the partition of clients, the antenna pattern and data rate of each group are adapted dynamically, based on PRR reports from clients. We have implemented the on-line algorithm on off-the-shelf WLAN products, and conducted extensive experiments and simulations to evaluate the performance. The results show that the proposed algorithm can significantly improve multicast performance compared to other schemes, and at the same time guarantee high PRR for all clients.

Several recent works have studied mobile vehicle scheduling to recharge sensor nodes via wireless energy transfer technologies. Unfortunately, most of them overlooked important factors of the vehicles' moving energy consumption and limited recharging capacity, which may lead to problematic schedules or even stranded vehicles. In this paper, we consider the recharge scheduling problem under such important constraints. To balance energy consumption and latency, we employ one dedicated data gathering vehicle and multiple charging vehicles. We first organize sensors into clusters for easy data collection, and obtain theoretical bounds on latency. Then we establish a mathematical model for the relationship between energy consumption and replenishment, and obtain the minimum number of charging vehicles needed. We formulate the scheduling into a Profitable Traveling Salesmen Problem that maximizes profit - the amount of replenished energy less the cost of vehicle movements, and prove it is NP-hard. We devise and compare two algorithms: a greedy one that maximizes the profit at each step; an adaptive one that partitions the network and forms Capacitated Minimum Spanning Trees per partition. Through extensive evaluations, we find that the adaptive algorithm can keep the number of nonfunctional nodes at zero. It also reduces transient energy depletion by 30-50 percent and saves 10-20 percent energy. Comparisons with other common data gathering methods show that we can save 30 percent energy and reduce latency by two orders of magnitude.

Data uploading time constitutes a large portion of mobile data gathering time in wireless sensor networks. By equipping multiple antennas on the mobile collector, data uploading time can be greatly shortened. However, previous works only treated wireless link capacity as a constant and ignored power control on sensors, which would significantly deviate from the real wireless environments. To overcome this problem, in this paper we propose a new data gathering cost minimization framework for mobile data gathering in wireless sensor networks by considering dynamic wireless link capacity and power control jointly. Our new framework not only allows concurrent data uploading from sensors to the mobile collector, but also determines transmission power under elastic link capacities. We study the problem under constraints of flow conservation, energy consumption, elastic link capacity, transmission compatibility, and Sojourn time. We employ the subgradient iteration algorithm to solve the minimization problem. We first relax the problem with Lagrangian dualization, then decompose the original problem into several subproblems, and present distributed algorithms to derive data rate, link flow and routing, power control, and transmission compatibility. For the mobile collector, we also propose a sub-algorithm to determine sojourn time at different stopping locations. Finally, we provide extensive simulation results to demonstrate the convergence and robustness of proposed algorithms. The results reveal 20 percent shorter data collection latency on average with lower energy consumptions compared to previous works as well as lower data gathering cost and robustness in case of node failures.

Recent advances in environmental energy harvesting technologies have provided great potentials for traditional battery powered sensor networks to achieve perpetual operations. Due to dynamics from the temporal profiles of ambient energy sources, most of the studies so far have focused on designing and optimizing energy management schemes on single sensor node, but overlooked the impact of spatial variations of energy distribution when sensors work together at different locations. To design a robust sensor network, in this paper, we use mobility to circumvent communication bottlenecks caused by spatial energy variations. We employ a mobile collector, called SenCar, to collect data from designated sensors and balance energy consumptions in the network. To show spatial-temporal energy variations, we first conduct a case study in a solar-powered network and analyze possible impact on network performance. Next, we present a two-step approach for mobile data collection. First, we adaptively select a subset of sensor locations where the SenCar stops to collect data packets in a multi-hop fashion. We develop an adaptive algorithm to search for nodes based on their energy and guarantee data collection tour length is bounded. Second, we focus on designing distributed algorithms to achieve maximum network utility by adjusting data rates, link scheduling, and flow routing that adapts to the spatial-temporal environmental energy fluctuations. Finally, our numerical results indicate the distributed algorithms can converge to optimality very fast and validate its convergence in case of node failure. We also show advantages of our framework such as it can adapt to spatial-temporal energy variations and demonstrate its superiority compared to the network with static data sink.

Designing a cost-effective network topology for data centers that can deliver sufficient bandwidth and consistent latency performance to a large number of servers has been an important and challenging problem. Many server-centric data center network topologies have been proposed recently due to their significant advantage in cost efficiency and data center agility, such as BCube, FiConn, and Bidimensional Compound Network (BCN). However, existing server-centric topologies are either not expandable or demanding prohibitive expansion cost. As the scale of data centers increases rapidly, the lack of expandability in existing server-centric data center networks imposes a severe obstacle for data center upgrade. In this paper, we present a novel server-centric data center network topology called BCube connected crossbars (BCCCs), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. A significant advantage of BCCC is its good expandability. When there is a need for expansion, we can easily add new servers and switches into the existing BCCC with little alteration of the existing structure. Meanwhile, BCCC can accommodate a large number of servers while keeping a very small network diameter. A desirable property of BCCC is that its diameter increases only linearly to the network order (i.e., the number of dimensions), which is superior to most of the existing server-centric networks, such as FiConn and BCN, whose diameters increase exponentially with network order. In addition, there are a rich set of parallel paths with similar length between any pair of servers in BCCC, which enables BCCC to not only deliver sufficient bandwidth capacity and predictable latency to end hosts, but also provide graceful performance degradation in case of component failure. We conduct comprehensive comparisons between BCCC with other popular server-centric network topologies, such as FiConn and BCN. We also propose an effective addressing scheme and routing algorithms for BCCC. We show that BCCC has significant advantages over the existing server-centric topologies in many important metrics, such as expandability, server port utilization, and network diameter.

Virtualization of servers and networks is a key technique to resolve the conflict between the increasing demands on computing power and the high cost of hardware in data centers. In order to map virtual networks to physical infrastructure efficiently, designers have to make careful decisions on the allocation of limited resources, which makes placement of virtual networks in data centers a critical issue. In this paper, we study the placement of virtual networks in fat-tree data center networks. In order to meet the requirements of instant parallel data transfer between multiple computing units, we propose a model of multicast-capable virtual networks (MVNs). We then design four virtual machine (VM) placement schemes to embed MVNs into fat-tree data center networks, named Most-Vacant-Fit (MVF), Most-Compact-First (MCF), Mixed-Bidirectional-Fill (MBF), and Malleable-Shallow-Fill (MSF). All these VM placement schemes guarantee the nonblocking multicast capability of each MVN while simultaneously achieving significant saving in the cost of network hardware. In addition, each VM placement scheme has its unique features. The MVF scheme has zero interference to existing computing tasks in data centers; the MCF scheme leads to the greatest cost saving; the MBF scheme simultaneously possesses the merits of MVF and MCF, and it provides an adjustable parameter allowing cloud providers to achieve preferred balance between the cost and the overhead; the MSF scheme performs at least as well as MBF, and possesses some additional predictable features. Finally, we compare the performance and overhead of these VM placement schemes, and present simulation results to validate the theoretical results.

A new network structure called BCube Connected Crossbars (BCCC) was recently proposed. Its short diameter, good expandability and low cost make it a very promising topology for data center networks. However, it can utilize only two NIC ports of each server, which is suitable for nowadays technology, even though more NIC ports are available. Due to technology advances, servers with more NIC ports are emerging and they will become low-cost commodities some time later. In this paper, we propose a more general server-centric data center network structure, called GBC3, which can utilize inexpensive commodity off-the-shelf switches and servers with any fixed number of NIC ports and provide good network properties. Like BCCC, GBC3 has good expandability. When doing expansion, there is no need to alter the existing system but only to add new components into it. Thus the expansion cost that BCube suffers from can be significantly reduced in GBC3. We also introduce an addressing scheme and several efficient routing algorithms for one-to-one, one-to-all and one-to-many communications in GBC3 respectively. We make comprehensive comparisons between GBC3 and some popular existing structures in terms of several critical metrics, such as diameter, network size, bisection bandwidth and capital expenditure. We also conduct extensive experiments to evaluate GBC3, which show that GBC3 achieves the best flexibility to make tradeoff among all these critical metrics and it can suit for many different applications by fine tuning its parameters.

This paper considers applying simultaneously wireless information and power transfer (SWIPT) technique to cooperative clustered wireless sensor networks, aiming at prolonging the lifetime of relay nodes and maximizing the energy efficiency of data transmission. To this end, we first formulate the energy-efficient cooperative transmission (eCotrans) problem for SWIPT as a non-convex optimization problem. By exploiting fractional programming and dual decomposition, we design a distributed iteration algorithm for power allocation, power splitting and relay selection to solve the non-convex optimization problem. Our simulation results illustrate that the proposed algorithm can converge within a few iterations and provide practical insights into the effect of the number of relay nodes and the maximum transmission power allowance on energy efficiency.

The indoor location fingerprint technique that infers the location based on the received signal strength (RSS) has been adopted in many localization applications, due to its high accuracy and low cost. However, there still lacks an analytical model that can be used to reduce the amount of fingerprints and improve the design of indoor localization system. In this paper, we propose a Voronoi analytical model based on graph theory, and apply this model to analyze the fingerprint structure, yield proximity information and compute the centroid of the Voronoi vertex in the Voronoi region. Furthermore, we compare the measured location and the actual location. Based on the comparison results, we select the smallest Euclidean distance between the two locations as the approximation of the actual location. In order to validate the performance of the analytical model on efficiency and reliability, we conduct an extensive experiment in an indoor parking lot, where it is convenient to deploy the access points (APs). The simulation results illustrate that the mean distance error decreases with the number of access points and collected samples.

BCube Connected Crossbars (BCCC) is a recently proposed network structure with short diameter and good expandability for cloud-based networks. Its diameter increases linearly to its order (dimension) and it has multiple near-equal parallel paths between any pair of servers. These advantages make BCCC a very promising network structure for next generation cloud-based networks. An efficient routing algorithm for BCCC has also been proposed, in which a permutation is used to determine which order (or dimension) will be routed first. However, there is no discussion yet about how to choose the permutation. In this paper, we mainly focus on permutation generations for routing in BCCC. We analyze the impact of choosing different permutations in both theory and simulation and propose two efficient permutation generation algorithms which take advantage of BCCC structure and give good performance.

Adopting mobile data gathering in wireless sensor networks (WSNs) can reduce the energy consumption on data forwarding thus achieve more uniform energy consumption among sensor nodes. However, the data delivery latency inevitable increases in mobile data gathering due to the travel of the mobile sink. In this paper, we consider a delivery latency minimization problem (DLMP) in a randomly deployed WSN. To solve this problem, we first select the traversed anchor points on the border of the communication range of sensor nodes to shorten the travel route, and then let the mobile sink move and collect data at the same time to reduce the travel time. In addition, we also employ the time division approach to traverse the sensor nodes whose signals cover the same travel segments. We formulate the DLMP as an integer programming problem which subjects to the direct access constraint, the data transmission constraint and the route traverse constraint. We prove that the DLMP is an NP-Complete (NPC) problem. To solve the NPC problem, we propose a substitution heuristic algorithm, a traveling salesman problem (TSP) heuristic algorithm and a random heuristic algorithm. We conduct extensive simulations to evaluate the performance of the proposed algorithms, and the results show that all the three algorithms can shorten the data delivery latency in mobile data gathering, with the substitution heuristic algorithm being the most effective one.

Wireless charging is a game-changing technology to provide reliable energy source for wireless sensor networks. Combining wireless charging with mobile data collection on a single mobile vehicle can mitigate the nonuniform energy distribution problem. However, data latency may be too long for some applications because vehicles have to spend significant time in charging before uploading data to the base station. In this paper, we propose a new framework that employs a dedicated vehicle for data collection and theoretically study the trade-offs between data latency and the number of recharging vehicles needed. We first study how to minimize data latency while ensuring all sensory data are collected and derive a latency bound. Then we establish a mathematical model to calculate the minimum number of recharging vehicles needed. Finally, we conduct simulations to validate the theoretical results and evaluate the efficiency of the framework. The results show that our scheme can reduce the number of nonfunctional nodes by 30-60%, and cut down data collection latency more than an order of magnitude compared to the previous work.

A new network structure called BCube Connected Crossbars (BCCC) was recently proposed. Its short diameter, good expandability and low cost make it a very promising topology for data center networks. However, it can utilize only two NIC ports of each server, which is suitable for nowadays technology, even when more ports are available. Due to technology advances, servers with more NIC ports are emerging and they will become low-cost commodities some time later. In this paper, we propose a more general server-centric data center network structure, called Advanced BCube Connected Crossbars (ABCCC), which can utilize inexpensive commodity off-the-shelf switches and servers with any fixed number of NIC ports and provide good network properties. Like BCCC, ABCCC has good expandability. When doing expansion, there is no need to alter the existing system but only to add new components into it. Thus the expansion cost that BCube suffers from can be significantly reduced in ABCCC. We also introduce an addressing scheme and an efficient routing algorithm for one-to-one communication in ABCCC. We make comprehensive comparisons between ABCCC and some popular existing structures in terms of several critical metrics, such as diameter, network size, bisection bandwidth and capital expenditure. We also conduct extensive simulations to evaluate ABCCC, which show that ABCCC achieves the best trade off among all these critical metrics and it suits for many different applications by fine tuning its parameters.

Wireless charging has provided a convenient alternative to renew sensors' energy in wireless sensor networks. Due to physical limitations, previous works have only considered recharging a single node at a time, which has limited efficiency and scalability. Recent advance on multi-hop wireless charging is gaining momentum to provide fundamental support to address this problem. However, existing single-node charging designs do not consider and cannot take advantage of such opportunities. In this paper, we propose a new framework to enable multi-hop wireless charging using resonant repeaters. First, we present a realistic model that accounts for detailed physical factors to calculate charging efficiencies. Second, to achieve balance between energy efficiency and data latency, we propose a hybrid data gathering strategy that combines static and mobile data gathering to overcome their respective drawbacks and provide theoretical analysis. Then we formulate multi-hop recharge schedule into a bi-objective NP-hard optimization problem. We propose a two-step approximation algorithm that first finds the minimum charging cost and then calculates the charging vehicles' moving costs with bounded approximation ratios. Finally, upon discovering more room to reduce the total system cost, we develop a post-optimization algorithm that iteratively adds more stopping locations for charging vehicles to further improve the results. Our extensive simulations show that the proposed algorithms can handle dynamic energy demands effectively, and can cover at least three times of nodes and reduce service interruption time by an order of magnitude compared to the single-node charging scheme.

This paper addresses the problem of joint relay and power splitting ratio selection along with power allocation for an energy harvesting (EH) cooperative network, where the source and the relays can harvest energy from natural sources (e.g., solar) and radio frequency (RF) signals, respectively. To effectively use the harvested energy from the source, the relays employ the power splitting technique to scavenge energy from RF signals radiated by the source. We formulate this problem into a non-convex constrained optimization problem with the objective of maximizing system payoff, which is defined as the difference between system transmission benefit and system energy cost, and meanwhile minimizing system outage probability in both offline and online settings. In particular, we consider both direct transmission and relay transmission in this paper. Relay transmission is selected dynamically based on network channel conditions and available energy of EH nodes. Our simulation results reveal that considering direct transmission and selecting relay transmission and power splitting ratio dynamically can greatly improve system performance.

Recent studies show that the novel wireless charging technology can extend the lifetime of Wireless Sensor Networks (WSNs) towards perpetual operations. Recharging Vehicles (RVs) can be applied in WSNs to recharge sensors conveniently via wireless charging devices. Most of existing work focused only on energy replenishment whereas ignored sensor activity management. In this paper, we propose a new framework that can jointly schedule sensor activity and recharging to save the traveling energy of RVs. First, we propose two schemes to manage sensor activity: balanced clustering and distributed sensor activation schemes. We further introduce a new metric so that the energy demand in each cluster can be managed. Then we formulate the recharging problem into a Traveling Salesman Problem with Profits, which is NP-hard. For the recharging route schedule, we first study the case of a single RV by coordinating sensor activity and energy replenishment, and then extend it to multiple RVs using two different schemes. The first scheme focuses on reducing traveling distance of RVs by confining their moving scopes and the second one improves the overall system performance by giving RVs a global view over the entire network. Finally, we validate the correctness and evaluate the performance of the sensor activity management schemes along with the recharging algorithms by extensive simulations. Our results indicate that significant reduction on system cost can be achieved. The sensor activity management schemes can save traveling energy of RVs by 16% while maintaining a reliable detection on targets. Compared with a simple greedy algorithm, the first and the second recharging schemes can save 41% and 13% traveling distance of RVs, and reduce nonfunctional nodes by 23% and 52%, respectively.

Cloud storage has gained a remarkable success in recent years with an increasing number of consumers and enterprises outsourcing their data to the cloud. To assure the availability and integrity of the outsourced data, several protocols have been proposed to audit cloud storage. Despite the formally guaranteed security, the constructions employed heavy cryptographic operations as well as advanced concepts (e.g., bilinear maps over elliptic curves and digital signatures), and thus are inefficient to admit wide applicability in practice. In this paper, we design a novel secure cloud storage protocol, which is conceptually and technically simpler and significantly more efficient than previous constructions. Inspired by a classic string equality checking protocol in distributed computing, our protocol uses only basic integer arithmetic (without advanced techniques and concepts). As simple as the protocol is, it supports both randomized and deterministic auditing to fit different applications. We further extend the proposed protocol to support data dynamics, i.e., adding, deleting and modifying data, using a novel technique. As a further contribution, we find a systematic way to design secure cloud storage protocols based on verifiable computation protocols. Theoretical and experimental analyses validate the efficacy of our protocol.

Most of today's data center networks (DCNs) adopt a multi-rooted tree structure called fat-tree, which delivers large bisection bandwidth through rich path multiplicity. In fat-tree DCNs, core switch modules play an important role in providing nonblocking capability, and form a significant part of network cost simultaneously. Reducing core switches while simultaneously guaranteeing performance has been a constant challenge. For example, multicast is an essential communication pattern in cloud services which needs to be supported efficiently. In this paper, we propose virtual network embedding schemes to deal with this problem. In the first scheme, we place the virtual machines (VMs) of a multicast-capable virtual network (MVN) as compact as possible, without any disturbance to existing traffic. In the second scheme, we manage to keep VMs in an even more compact way to reduce cost by allowing a small degree of VM migration. Both schemes are guaranteed to support any multicast communications within MVNs, and simultaneously achieve significant cost saving in terms of core switches, compared to currently best known result. Moreover, we show that our schemes incur only a small overhead in terms of migrations. Finally, we evaluate the performance of proposed schemes and validate the theoretical analysis through extensive simulations.

Wireless sensor networks (WSNs) are often deployed in hostile environments where an adversary may physically capture some of the nodes in WSNs, and replicate them in a large number of clones, easily taking control of networks. A few solutions have been proposed to cope with this problem. However, these solutions cannot adapt to the change of the network size and have low detection efficiency for clone nodes. In order to discover the clone nodes fast, in this paper, we propose an improved LEACH (NI-LEACH) protocol to reduce the scale of the cluster by considering the residual energy of nodes and the optimal number of clusters. Furthermore, we design an intrusion detection algorithm to detect the replication attacks by introducing monitor nodes in the network so as to greatly reduce the occurrence of tampering with the information. Simulation results show that our proposed algorithm is simple yet efficient. An attacker can be detected with high probability while achieving approximately optimal throughput. The network's ability against the attack from clone nodes is greatly improved.

Virtualization of servers and networks is a key technique to resolve the conflict between the increasing demands on computing power and the high cost of hardware in data centers. In order to map virtual networks to physical infrastructure efficiently, designers have to make careful decisions on the allocation of limited resources, which makes network embedding in data centers a very important problem. In this paper, we tackle the network embedding problem in fat-tree data centers. To meet the requirements of instant parallel data transfer between multiple computing units, we propose a model of multicast-capable virtual networks (Mons). We then design three virtual machine (VM) placement schemes with different features for embedding MVNs into fat-tree DCNs, named Most-Vacant-Fit (MVF), Most-Compact-First (MCF) and Mixed-Bidirectional-Fill (MBF). All these VM placement schemes guarantee the no blocking multicast capability of each MVN while simultaneously achieving significant saving on the cost of network hardware. In addition, each VM placement scheme also has its unique features. The MVF scheme has zero interference to existing computing tasks in data centers, the MCF scheme leads to the greatest cost saving, the MBF scheme simultaneously possesses the merits of MVF and MCF, and it provides an adjustable parameter allowing cloud providers to achieve preferred balance between the cost and the overhead. Finally, we compare the performance and overhead of these VM placement schemes, and present simulation results to validate our theoretical results.

Energy harvesting is a promising solution to prolong the lifetime of energy-constrained wireless sensor networks. In particular, scavenging energy from ambient radio frequency (RF) signals has drawn a lot of attention recently. In this paper, we apply simultaneous wireless information and power transfer (SWIPT) to a clustered sensor network such that a cluster head node harvests the wireless energy of received RF signals from its cluster members and then employs the harvested energy to compensate the energy consumed by data aggregating and forwarding. In such a network, how to achieve high energy efficiency through trading off between energy harvesting and information decoding is a critical issue. To this end, we formulate the rate and power resource allocation problem in a clustered WSN with SWIPT as a non-convex constrained energy efficiency maximization problem. By exploiting fractional programming and dual decomposition, we further propose a cross-layer resource allocation (ResAll) algorithm consisting of subalgorithms of rate control, power allocation and power splitting to solve the problem efficiently and optimally. Our simulation results reveal that the proposed ResAll algorithm converges within a small number of iterations, and achieves optimal system energy efficiency by balancing energy efficiency, data rate, transmit power and power splitting ratio.

In this paper, we consider lossy mobile ad hoc networks where the data rate of a given flow becomes lower and lower along its routing path. One of the main challenges in lossy mobile ad hoc networks is how to achieve the conflicting goal of increased network utility and reduced power consumption, while without following the instantaneous state of a fading channel. To address this problem, we propose a cross-layer rate-effective network utility maximization (RENUM) framework by taking into account the lossy nature of wireless links and the constraints of rate outage probability and average delay. In the proposed framework, the utility is associated with the effective rate received at the destination node of each flow instead of the injection rate at the source of the flow. We then present a distributed joint transmission rate, link power and average delay control algorithm, in which explicit broadcast message passing is required for power allocation algorithm. Motivated by the desire of power control devoid of message passing, we give a near-optimal power-allocation scheme that makes use of autonomous SINR measurements at each link and enjoys a fast convergence rate. The proposed algorithm is shown through numerical simulations to outperform other network utility maximization algorithms without rate outage probability/average delay constraints, leading to a higher effective rate, lower power consumption and delay. Furthermore, we conduct extensive network-wide simulations in NS-2 simulator to evaluate the performance of the algorithm in terms of throughput, delay, packet delivery ratio and fairness.

Fat-tree networks have been widely adopted as network topologies in data center networks (DCNs). However, it is costly for fat-tree DCNs to support nonblocking multicast communication, due to the large number of core switches required. Since multicast is an essential communication pattern in many cloud services and nonblocking multicast communication can ensure the high performance of such services, reducing the cost of nonblocking multicast fat-tree DCNs is very important. On the other hand, server redundancy is ubiquitous in today’s data centers to provide high availability of services. In this paper, we explore server redundancy in data centers to reduce the cost of nonblocking multicast fat-tree data center networks (DCNs). First, we present a multirate network model that accurately describes the communication environment of the fat-tree DCNs. We then show that the sufficient condition on the number of core switches required for nonblocking multicast communication under the multirate model can be significantly reduced when the fat-tree DCNs are 2-redundant, i.e., each server in the data center has exactly one redundant backup. We also study the general redundant fat-tree DCNs where servers may have different numbers of redundant backups depending on the availability requirements of services they provide, and show that a higher redundancy level further reduces the cost of nonblocking multicast fat-tree DCNs. Then, to complete our analysis, we consider a practical faulty data center, where one or more active servers may fail at any time. We give a strategy to re-balance the active servers among edge switches after server failures so that the same nonblocking condition still holds. Finally, we give a multicast routing algorithm with linear time complexity to configure multicast connections in fat-tree DCNs.

Clos networks and their variations such as folded-Clos networks (fat-trees) have been widely adopted as network topologies in data center networks. Since multicast is an essential communication pattern in many cloud services, nonblocking multicast communication can ensure the high performance of such services. However, nonblocking multicast Clos networks are costly due to the large number of middle stage switches required. On the other hand, server redundancy is ubiquitous in today's data centers to provide high availability of services. In this paper, we explore such server redundancy in data centers to reduce the cost of nonblocking multicast Clos data center networks (DCNs). To facilitate our analysis, we first consider an ideal fault-free data center with no server failure. We give an algorithm to assign active servers evenly among input stage switches in a multicast Clos DCN where each server has one or more redundant backups depending on the availability requirements of services they provide. We show that the sufficient nonblocking condition on the number of middle stage switches for a multicast Clos DCN can be significantly reduced by exploring server redundancy. Then, to complete our analysis, we consider a practical faulty data center, where one or more active servers may fail at anytime. We give a strategy to re-balance the active servers among input stage switches after server failures so that the same nonblocking condition still holds. Finally, we provide a multicast routing algorithm with linear time complexity to configure multicast connections in Clos DCNs.

This paper considers applying simultaneous wireless information and power transfer (SWIPT) technique to cooperative clustered wireless sensor networks, where energy-constrained relay nodes harvest the ambient radio-frequency (RF) signal and use the harvested energy to forward the packets from sources to destinations. To this end, we first formulate the energy-efficient cooperative transmission (eCotrans) problem for SWIPT in clustered wireless sensor networks as a non-convex constrained optimization problem. Then, by exploiting fractional programming and dual decomposition, we develop a distributed iteration algorithm for power allocation, power splitting and relay selection to solve the non-convex optimization problem. We find that power splitting ratio plays an imperative role in relay selection. Our simulation results illustrate that the proposed algorithm can converge within a few iterations and the numerical analysis provides practical insights into the effect of various system parameters, such as the number of relay nodes, the inter-cluster distance and the maximum transmission power allowance, on energy efficiency and average harvested power.

Recent studies have shown that significant benefit can be achieved in wireless sensor networks (WSNs) by employing mobile collectors for data gathering via short-range communications. A typical scenario for such a scheme is that a mobile collector roams over the sensing field and pauses at some anchor points on its moving tour such that it can traverse the transmission range of all the sensors in the field and directly collect data from each sensor. In this paper, we study the performance optimization of such mobile data gathering by formulating it into a cost minimization problem constrained by channel capacity, required minimum data uploads from each sensor and bound of total sojourn time at all anchor points. In order to provide an efficient and distributed algorithm, we decompose this global optimization problem into two subproblems that can be solved by each sensor and the mobile collector, respectively. We show that such decomposition can be characterized as a pricing mechanism, in which each sensor independently adjusts its payment for the data uploading opportunity based on the shadow prices of different anchor points. Correspondingly, we give an efficient algorithm to jointly solve the two subproblems. Our theoretical analysis demonstrates that the proposed algorithm can achieve the optimal data control for each sensor and the optimal sojourn time allocation for the mobile collector, which minimizes the overall network cost. Finally, extensive simulation results further validate that our algorithm achieves lower cost than the compared data gathering strategy.

In this paper, a three-layer framework is proposed for mobile data collection in wireless sensor networks, which includes the sensor layer, cluster head layer, and mobile collector (called SenCar) layer. The framework employs distributed load balanced clustering and dual data uploading, which is referred to as LBC-DDU. The objective is to achieve good scalability, long network lifetime and low data collection latency. At the sensor layer, a distributed load balanced clustering (LBC) algorithm is proposed for sensors to self-organize themselves into clusters. In contrast to existing clustering methods, our scheme generates multiple cluster heads in each cluster to balance the work load and facilitate dual data uploading. At the cluster head layer, the inter-cluster transmission range is carefully chosen to guarantee the connectivity among the clusters. Multiple cluster heads within a cluster cooperate with each other to perform energy-saving inter-cluster communications. Through inter-cluster transmissions, cluster head information is forwarded to SenCar for its moving trajectory planning. At the mobile collector layer, SenCar is equipped with two antennas, which enables two cluster heads to simultaneously upload data to SenCar in each time by utilizing multi-user multiple-input and multiple-output (MU-MIMO) technique. The trajectory planning for SenCar is optimized to fully utilize dual data uploading capability by properly selecting polling points in each cluster. By visiting each selected polling point, SenCar can efficiently gather data from cluster heads and transport the data to the static data sink. Extensive simulations are conducted to evaluate the effectiveness of the proposed LBC-DDU scheme. The results show that when each cluster has at most two cluster heads, LBC-DDU achieves over 50 percent energy saving per node and 60 percent energy saving on cluster heads comparing with data collection through multi-hop relay to the static data sink, and 20 percent shorter data collection time compared to traditional mobile data gathering.

The recently proposed optical cut-through (OpCut) switch holds a great potential in achieving high energy efficiency, as it allows optical packets to cut through the switch in optical domain whenever possible, which avoids power-hungry O/E/O conversion. In the OpCut switch, to ensure in-order transmission, only optical Head-of-Line (HOL) packet of a switch flow, i.e., the stream of packets sharing the same input and output port, is allowed to cut-through the switch, and optical HOL packets are always prioritized over buffered HOL packets to achieve high cut-through ratio, which is measured by the portion of packets cutting through the switch optically. However, under such priority rule, switch flows with buffered packets are at the risk of starvation, and the OpCut switch fails to achieve 100 percent throughput for all admissible i.i.d. traffics due to the unfairness in packet scheduling. To address this two issues, in this paper we propose a delay threshold rule for packet scheduling, in which buffered packets with delays exceeding a preset delay threshold are prioritized over optical packets. In the meanwhile, the cut-through ratio is very low under heavily congested traffic due to maintaining packet order, whereas the Internet is designed to accommodate a certain degree of packet reorder, which is very common in practice due to path multiplicity. In this paper, we design a bounded-reorder packet scheduling algorithm that significantly increases the cut-through ratio of the OpCut switch while allowing a small degree of out-of-order transmission. Our extensive simulation results show that the energy efficiency of OpCut switch can be significantly improved with only a very small degree of packet reordering, which has little adverse impact on the network application performance.

Many server-centric data center network topologies have been proposed recently due to their significant advantage in cost-efficiency and data center agility, such as BCube, FiConn and BCN. However, existing server-centric topologies are either not expandable or demanding prohibitive expansion cost. As the scale is increasing rapidly, the lack of expandability imposes a severe obstacle for data center upgrade. In this paper, we present a novel server-centric data center network topology called BCube Connected Crossbars (BCCC), which can provide good network performance and expandability using commodity off-the-shelf switches and commodity servers with only two NIC ports. BCCC can accommodate a large number of servers while keeping a very small network diameter, as a particular desirable property of BCCC is that its diameter increases only linearly to the network order, which is superior to most of existing server-centric networks, such as FiConn and BCN, whose diameters increase exponentially with network order. Additionally, we propose an effective addressing scheme and routing algorithms for BCCC. We also conduct comprehensive comparisons between BCCC and other popular server-centric networks. We show that BCCC has significant advantages over existing server-centric topologies in many important metrics, such as expandability, port utilization and network diameter.

The high bandwidth and power efficiency of optical circuit switching (OCS) have motivated the recent development of hybrid packet/circuit switched (Hypac) data center networks (DCNs). However, current Hypac DCNs use a large MEMS optical switch for OCS communication, which offers limited scalability and expandability. In addition, the slow switching speed of MEMS switches imposes considerable network reconfiguration overhead, which results in degraded network performance. In this paper, we first analyze the fundamental challenges in current MEMS-based Hypac DCNs, and show that fast optical network reconfiguration is the key to effectively utilize OCS in data center communication. We then present a Fast Reconfigurable Baseline Optical Network (FARBON), which, by leveraging the ultra-fast optical switching modules and unique topological properties of the baseline multistage network, allows for rapid network configuration. We also design the control plane and a practical low-jitter traffic scheduling algorithm for FARBON. We demonstrate that FARBON has many desirable features, such as good scalability, low traffic jitter, predictable network performance and tolerance to inaccurate traffic information. The performance of FARBON is evaluated via extensive simulations, and the results show that FARBON significantly outperforms MEMS optical switches in terms of average packet delay and jitter, as well as dealing with correlated traffic, thus is a promising candidate for exploiting the potential of OCS in Hypac DCNs.

In this paper, we consider the joint opportunistic routing and channel assignment problem in multi-channel multi-radio (MCMR) cognitive radio networks (CRNs) for improving aggregate throughput of the secondary users. We first present the linear programming optimization model for this joint problem, taking into account the feature of CRNs-channel uncertainty. Then considering the queue state of a node, we propose a new scheme to select proper forwarding candidates for opportunistic routing. Furthermore, a new algorithm for calculating the forwarding probability of any packet at a node is proposed, which is used to calculate how many packets a forwarder should send, so that the duplicate transmission can be reduced compared with MAC-independent opportunistic routing & encoding (MORE) [11]. Our numerical results show that the proposed scheme performs significantly better that traditional routing and opportunistic routing in which channel assignment strategy is employed.

Cognitive radio (CR) is a promising technology to improve spectrum utilization. However, spectrum availability is uncertain which mainly depends on primary user's (PU's) behaviors. This makes it more difficult for most existing CR routing protocols to achieve high throughput in multi-channel cognitive radio networks (CRNs). Inter-session network coding and opportunistic routing can leverage the broadcast nature of the wireless channel to improve the performance for CRNs. In this paper we present a coding aware opportunistic routing protocol for multi-channel CRNs, cognitive radio opportunistic routing (CROR) protocol, which jointly considers the probability of successful spectrum utilization, packet loss rate, and coding opportunities. We evaluate and compare the proposed scheme against three other opportunistic routing protocols with multichannel. It is shown that the CROR, by integrating opportunistic routing with network coding, can obtain much better results, with respect to throughput, the probability of PU-SU packet collision and spectrum utilization efficiency.

Wireless sensor networks adopting static data gathering may suffer from unbalanced energy consumption due to non-uniform packet relay in such networks, especially in large scale networks. On the other hand, although mobile data gathering provides a reasonable approach to solving this problem, it inevitably introduces longer data collection latency due to the use of mobile data collectors. In the meanwhile, energy harvesting has been considered as a promising solution to relieve energy limitation in wireless sensor networks. In this paper, we consider a joint design of these two schemes and propose a novel two layer heterogeneous architecture for wireless sensor networks, which consists of two types of nodes: sensor nodes which are static and powered by solar panels, and cluster heads that have limited mobility and can be wirelessly recharged by power transporters. Based on this network architecture, we present a data gathering scheme, called Mobility Assisted Data Gathering (MADG), where sensor nodes are clustered around cluster heads that change their positions in each data gathering cycle, and the sensing data are forwarded to the data sink by these cluster heads working as data aggregation points. We evaluate the performance of the proposed scheme by extensive simulations and the results show that MADG provides significant improvement in terms of balancing energy consumption and the amount data gathered compared to previous work.

Environmental energy harvesting technologies have provided potential for battery-powered wireless sensor networks to have perpetual network operations. To design a robust network that can adapt to not only temporal but also spatial variations of ambient energy sources, in this paper, we utilize mobility to circumvent communication bottlenecks, by employing a mobile data collector, called SenCar. We propose a two-stage approach for mobile data collection. In the first stage, SenCar makes stops at a subset of selected sensor locations to collect data packets in a multi-hop fashion. We provide a selection algorithm to search for sensor locations with most residual energy while guaranteeing a bounded tour length. Then we design a distributed data gathering algorithm to achieve maximum network utility by adjusting data rates, link scheduling and flow routing that adapts to spatial temporal environmental energy variations. The effectiveness and efficiency of the proposed algorithms are validated by extensive numerical results.

As the scale of data centers and cloud computing applications increases, data center networks play a critical role in meeting the huge communication bandwidth requirement of such applications. The scalability of conventional electronic data center networks is limited by wiring complexity and reaching distance of links under fixed power budget. To overcome this problem, in this paper we propose a nonblocking hybrid switch architecture, called NEO (Nonblocking Electronic and Optical), which is able to provide nonblocking interconnections for as many as 1,000,000 servers in a data center. NEO maintains electronic interconnections for intra-pod networks, while providing interpod interconnections by optical core switches, which not only increases the scalability of the switch architecture, but also lowers the switch cost and power consumption compared to other existing optical switch architectures. We also design a packet scheduler for NEO, which adopts a credit flow control mechanism and a parallel scheduling algorithm to avoid packet loss, and provide low communication latency. Our simulation results demonstrate that NEO achieves very low average packet delay compared to other existing optical switching architectures under various traffic patterns.

This paper investigates the intrinsic relationship between secure cloud storage and secure network coding for the first time. Secure cloud storage was proposed only recently while secure network coding has been studied for more than ten years. We show in general how to construct a secure cloud storage protocol given any secure network coding protocol. Our construction suggests a systematic way to construct various secure cloud storage protocols. We also show that it is secure under a definition which captures the real world uses of the cloud storage. From our general construction, we propose a secure cloud storage protocol based on a recent secure network coding protocol. The protocol is the first publicly verifiable secure cloud storage protocol in the standard model, while the previous work is either not publicly verifiable, or security argument is only argued heuristically in the random oracle model. We also enhance the proposed protocol to support third-party public auditing, which has received considerable attention recently. Finally, we prototype the proposed protocol and evaluate its performance. Experimental results validate the effectiveness of the protocol.

Recently, there has been much effort on introducing optical fiber communication to data center networks (DCNs) because of its significant advantage in bandwidth capacity and power efficiency. However, due to limitations of optical switching technologies, optical networking alone has not yet been able to accommodate the volatile data center traffic. As a result, hybrid packet/circuit (Hypac) switched DCNs, which argument the electrical packet switched (EPS) network with an optical circuit switched (OCS) network, have been proposed to combine the strengths of both types of networks. However, one problem with current Hypac DCNs is that the EPS network is shared in a best effort fashion and is largely oblivious to the accompanying OCS network, which results in severe drawbacks, such as degraded network predictability and deficiency in handling correlated traffic. Since the OCS/EPS networks have unique strengths and weaknesses, and are best suited for different traffic patterns, coordinating and collaborating the configuration of both networks is critical to reach the full potential of Hypac DCNs, which motivates the study in this paper. First, we present a network model that accurately abstracts the essential characteristics of the EPS/OCS networks. Second, considering the recent advances in network control technology, we propose a time-efficient algorithm called Collaborative Bandwidth Allocation (CBA) that configures both networks in a complementary manner. Finally, we conduct comprehensive simulations, which demonstrate that CBA significantly improves the performance of Hypac DCNs in many aspects.

Reliability is a critical metric in the design and development of scale-out data storage clusters. A general multiway replication-based declustering scheme has been widely used in enterprise large-scale storage systems to improve the I/O parallelism. Unfortunately, given an increasing number of node failures, how often a cluster starts losing data when being scaled-out is not well investigated. In this paper, we studied the reliability of multi-way declustering layouts by developing an extended model, more specifically abstracting the Continuous Time Markov chain to an ordinary differentiate equation group, and analyzing their potential parallel recovery possibilities. Our comprehensive simulation results on Mat lab and SHARPE show that the shifted declustering layout outperforms the random declustering layout in a multi-way replication scale-out architecture, in terms of data loss probability and system reliability by up to 63% and 85% respectively. Our study on both 5-year and 10-year system reliability equipped with various recovery bandwidth settings shows that, the shifted declustering layout surpasses the random declustering layout in both cases by consuming up to 5.2% and 11% less recovery bandwidth.

Several recent works have studied the schedule for mobile vehicles to recharge sensor nodes via wireless energy transfer technologies. Unfortunately, most of them overlooked the important factors of the vehicles' moving energy consumption and limited recharging capacity. These oversights may lead to problematic schedules or even stranded vehicles. In this paper, we study the recharging schedule that maximizes the recharging profit - the amount of replenished energy less the cost of vehicle movements - under these important constraints. We first derive the minimum number of vehicles needed for energy neutral condition and discover a set of desired network properties. Then we formulate the recharge schedule optimization into a Profitable Traveling Salesmen Problem with capacity and battery deadline constraints, which we prove to be NP-hard. We propose two algorithms to solve the problem. The first one is a greedy algorithm that maximizes the recharge profit at each step; the second one first adaptively partitions the network based on recharge requests, then forms Capacitated Minimum Spanning Tree in each partition followed by route improvements. Finally, we evaluate and compare the performance of proposed algorithms and validate the correctness of theoretical results through extensive simulations. Given a sufficient number of vehicles, the adaptive algorithm can keep the number of nonfunctional nodes at zero. Compared to the greedy algorithm, it reduces the percentage of transient energy depletion by 30-50% with 10-20% energy saving on vehicles.

Multicast benefits numerous data center applications that require group communication by eliminating sending unnecessary duplicated packets in the network, thus significantly reduces network traffic and improves application throughput. Meanwhile, most data center networks (DCNs) today adopt a multi-rooted tree structure called fat-tree, which utilizes rich path multiplicity to deliver high bisection bandwidth. However, without an efficient flow scheduling algorithm that appropriately routes multicast flows to achieve traffic load balance, heavy congestion may occur throughout the network, which prevents full utilization of such high degree of link parallelism and causes unpredictable network performance. Hence, in this paper we study multicast flow scheduling in fat-tree DCNs, where multicast flow requests arrive one by one without a priori knowledge of future traffic. To address the drastic traffic fluctuation in data centers, we consider a very general traffic model called hose traffic model, where the only assumption is that the total bandwidth demand of traffic that enters (leaves) an ingress (egress) link of each server at any time is bounded by the capacity of its network interface card. We present a low-complexity on-line multicast flow scheduling algorithm for fat-tree DCNs. The algorithm can achieve bounded congestion and efficient bandwidth utilization under any arbitrary sequence of multicast flow requests that satisfy the hose model. We also derive the bound on congestion that the algorithm can achieve in a fat-tree DCN. Finally, we evaluate the algorithm by an event-driven DCN simulator under various types of traffic patterns, and show that the algorithm achieves superior performance in terms of network throughput and evenness of traffic load distribution.

As the latest amendment of IEEE 802.11 standard, 802.11n allows a maximum raw data rate as high as 600 Mbps, making it a desirable candidate for wireless local area network (WLAN) deployment. In typical deployment, the coverage areas of nearby access points (APs) usually overlap with each other to provide satisfactory coverage and seamless mobility support. Clients tend to associate (connect) to the AP with the strongest signal strength, which may lead to poor client throughput and overloaded APs. Although a number of AP association schemes have been proposed for IEEE 802.11 WLANs in the literature, the challenges brought by the new features in 802.11n have not been thoroughly studied nor the impact of legacy 802.11a/b/g clients in 802.11n WLANS on AP association. To fill in this gap, in this paper, we explore AP association for 802.11n with heterogeneous clients (802.11a/b/g/n). We first present a bi-dimensional Markov model to estimate the uplink and downlink throughput of clients and formulate AP association into an optimization problem, aiming at providing each client a bandwidth proportional to its usable data rate. Based on this Markov model, we propose an on-line AP association algorithm under the condition that each client can acquire timely information of all clients associated with nearby APs. Furthermore, for WLANs with densely deployed APs, we provide another on-line AP association algorithm with lower complexity, which takes full advantage of 802.11n transmissions by simply associating different types of clients with different APs. We have conducted extensive simulations and experiments to validate the proposed algorithms. The results show that our algorithms can significantly improve both 802.11n throughput and aggregated network throughput under various network scenarios, compared to previous AP association schemes. Our experiments also confirm the effectiveness of the algorithms in enhancing network throughput, maintaining proportional fairness among clients, and balancing load among APs.

Network coding is a promising enhancement of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. Peer-to-peer networks are a perfect place to apply network coding due to two reasons: the topology of a peer-to-peer network is constructed arbitrarily, thus it is easy to tailor the topology to facilitate network coding; the nodes in a peer-to-peer network are end hosts which can perform more complex operations such as decoding and encoding than simply storing and forwarding messages. In this paper, we propose a scheme to apply network coding to peer-to-peer file sharing which employs a peer-to-peer network to distribute files resided in a web server or a file server. The scheme exploits a special type of network topology called combination network. It was proved that combination networks can achieve unbounded network coding gain measured by the ratio of network throughput with network coding to that without network coding. Our scheme encodes a file into multiple messages and divides peers into multiple groups with each group responsible for relaying one of the messages. The encoding scheme is designed to satisfy the property that any subset of the messages can be used to decode the original file as long as the size of the subset is sufficiently large. To meet this requirement, we first define a deterministic linear network coding scheme which satisfies the desired property, then we connect peers in the same group to flood the corresponding message, and connect peers in different groups to distribute messages for decoding. Moreover, the scheme can be readily extended to support link heterogeneity and topology awareness to further improve system performance in terms of throughput, reliability and link stress. Our simulation results show that the new scheme can achieve 15%–20% higher throughput than another peer-to-peer multicast system, Narada, which does not employ network coding. In addition, it achieves good reliability and robustness to link failure or churn.

The ever increasing intra-chip and inter-chip traffic load in computing systems has been pushing traditional electronic interconnects to their limit in communication bandwidth, latency, and energy consumption. In order to achieve the high bandwidth and low latency required by intra-chip and inter-chip communications and mitigate the high interconnect power dissipation, optical interconnects have been considered as a promising candidate for intra-chip and inter-chip interconnections in next generation computing systems. In addition, packet switching is an efficient switching paradigm to fully utilize the communication bandwidth. However, due to lack of random access optical memory, it is challenging to implement all-optical packet switching in optical interconnects. In this paper, we exploit bufferless routing, a special type of packet-switching, to overcome the problem of lack of random access optical buffer. More specifically, we study bufferless routing in a novel optical multichip system, called Gaussian macrochip, where embedded chips are interconnected by an optical Gaussian network. By taking advantage of the underlying Hamiltonian cycles in the Gaussian network, we design a bufferless routing algorithm for the Gaussian macrochip, which routes packets along the shortest path in the absence of deflection, and guarantees that deflected packets reach their destinations within${{N}}$hops. Our extensive simulation results demonstrate that by adopting the proposed routing algorithm, Gaussian macrochip can support much higher inter-chip communication bandwidth, has much shorter average packet delay, and is more power efficient than the previously proposed architectures for optical multichip systems.

Optical interconnects are considered as a very appealing solution for future high speed interconnections in core networks and parallel computers. In this paper, we study multicast scheduling in all-optical packet interconnects/switches. We first propose a novel optical buffer called multicast-enabled fiber-delay-lines (M-FDLs), which can provide flexible delay for copies of multicast packets using only a small number of FDL segments. We then present a Low Latency Multicast Scheduling (LLMS) Algorithm that considers the schedule of each arriving packet for multiple time slots. We show that LLMS has several desirable features, such as a guaranteed delay upper bound and adaptivity to transmission requirements. To relax the time constraint of LLMS, we further propose a pipeline and parallel architecture for LLMS that distributes the scheduling task to multiple pipelined processing stages, with N processing modules in each stage, where N is the size of the interconnect. Finally, by implementing it with simple combination circuits, we show that each processing module can complete the packet scheduling for a time slot in O(1) time. The performance of LLMS is evaluated extensively against statistical traffic models and real Internet traffic traces, and the results show that the proposed LLMS algorithm can achieve superior performance in terms of average packet delay and packet drop ratio.

Optical switches are widely considered the most promising candidate to provide ultra-high speed interconnections for future communication and computing systems. Due to the difficulty in implementing an all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the optical cut-through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. We studied the packet-scheduling problem in single-wavelength OpCut switches in our previous work. In this paper, we consider the wavelength division multiplexed (WDM) case. While WDM makes much higher bandwidth possible, it also increases the complexity of the switch architecture, as well as packet scheduling. Our goal is to schedule as many as possible packets to the switch output in each time slot and to maintain the packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing the set packing problem to it, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of √(2Nk) with regard to the number of packets transmitted, where N is the switch size, and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing problem. Based on the approximation algorithm, we also give practical schedulers that can be implemented in the fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

The demands for data rate and transmission reliability constantly increase with the explosive use of wireless devices and the advancement of mobile computing techniques. Multiple-input and multiple-output (MIMO) technique is considered as one of the most promising wireless technologies that can significantly improve transmission capacity and reliability. Many emerging mobile wireless applications require peer-to-peer transmissions over an ad hoc network, where the nodes often have a different number of antennas, and the channel condition and network topology vary over time. It is important and challenging to develop efficient schemes to coordinate transmission resource sharing among a heterogeneous group of nodes over an infrastructure-free mobile ad hoc network. In this work, we propose a holistic scheduling algorithm that can adaptively select different transmission strategies based on the node types and channel conditions to effectively relieve the bottleneck effect caused by nodes with smaller antenna arrays, and avoid the transmission failure due to the violation of lower degree of freedom constraint resulted from the channel dependency. The algorithm also takes advantage of channel information to opportunistically schedule cooperative spatial multiplexed transmissions between nodes and provide special transmission support for higher priority nodes with weak channels, so that the data rate of the network can be maximized while user transmission quality requirement is supported. The performance of our algorithm is studied through extensive simulations and the results demonstrate that our algorithm is very effective in handling node heterogeneity and channel constraint, and can significantly increase the throughput while reducing the transmission delay.

The emerging wireless energy transfer technology enables charging sensor batteries in a wireless sensor network (WSN) and maintaining perpetual operation of the network. Recent breakthrough in this area has opened up a new dimension to the design of sensor network protocols. In the meanwhile, mobile data gathering has been considered as an efficient alternative to data relaying in WSNs. However, time variation of recharging rates in wireless rechargeable sensor networks imposes a great challenge in obtaining an optimal data gathering strategy. In this paper, we propose a framework of joint wireless energy replenishment and anchor-point based mobile data gathering (WerMDG) in WSNs by considering various sources of energy consumption and time-varying nature of energy replenishment. To that end, we first determine the anchor point selection strategy and the sequence to visit the anchor points. We then formulate the WerMDG problem into a network utility maximization problem which is constrained by flow, energy balance, link and battery capacity and the bounded sojourn time of the mobile collector. Furthermore, we present a distributed algorithm composed of cross-layer data control, scheduling and routing subalgorithms for each sensor node, and sojourn time allocation subalgorithm for the mobile collector at different anchor points. We also provide the convergence analysis of these subalgorithms. Finally, we implement the WerMDG algorithm in a distributed manner in the NS-2 simulator and give extensive numerical results to verify the convergence of the proposed algorithm and the impact of utility weight, link capacity and recharging rate on network performance.

Using vehicles equipped with wireless energy transmission technology to recharge sensor nodes over the air is a game-changer for traditional wireless sensor networks. The recharging policy regarding when to recharge which sensor nodes critically impacts the network performance. So far only a few works have studied such recharging policy for the case of using a single vehicle. In this paper, we propose NETWRAP, an NDN based Real Time Wireless Recharging Protocol for dynamic wireless recharging in sensor networks. The real-time recharging framework supports single or multiple mobile vehicles. Employing multiple mobile vehicles provides more scalability and robustness. To efficiently deliver sensor energy status information to vehicles in real-time, we leverage concepts and mechanisms from named data networking (NDN) and design energy monitoring and reporting protocols. We derive theoretical results on the energy neutral condition and the minimum number of mobile vehicles required for perpetual network operations. Then we study how to minimize the total traveling cost of vehicles while guaranteeing all the sensor nodes can be recharged before their batteries deplete. We formulate the recharge optimization problem into a Multiple Traveling Salesman Problem with Deadlines (m-TSP with Deadlines), which is NP-hard. To accommodate the dynamic nature of node energy conditions with low overhead, we present an algorithm that selects the node with the minimum weighted sum of traveling time and residual lifetime. Our scheme not only improves network scalability but also ensures the perpetual operation of networks. Extensive simulation results demonstrate the effectiveness and efficiency of the proposed design. The results also validate the correctness of the theoretical analysis and show significant improvements that cut the number of nonfunctional nodes by half compared to the static scheme while maintaining the network overhead at the same level.

Recent years have witnessed the rapid development and proliferation of techniques on improving energy efficiency for wireless s`ensor networks. Although these techniques can relieve the energy constraint on wireless sensors to some extent, the lifetime of wireless sensor networks is still limited by sensor batteries. Recent studies have shown that energy rechargeable sensors have the potential to provide perpetual network operations by capturing renewable energy from external environments. However, the low output of energy capturing devices can only provide intermittent recharging opportunities to support low-rate data services due to spatial-temporal, geographical or environmental factors. To provide steady and high recharging rates and achieve energy efficient data gathering from sensors, in this paper, we propose to utilize mobility for joint energy replenishment and data gathering. In particular, a multi-functional mobile entity, called SenCar in this paper, is employed, which serves not only as a mobile data collector that roams over the field to gather data via short-range communication but also as an energy transporter that charges static sensors on its migration tour via wireless energy transmissions. Taking advantages of SenCar’s controlled mobility, we focus on the joint optimization of effective energy charging and high-performance data collections. We first study this problem in general networks with random topologies. We give a two-step approach for the joint design. In the first step, the locations of a subset of sensors are periodically selected as anchor points, where the SenCar will sequentially visit to charge the sensors at these locations and gather data from nearby sensors in a multi-hop fashion. To achieve a desirable balance between energy replenishment amount and data gathering latency, we provide a selection algorithm to search for a maximum number of anchor points where sensors hold the least battery energy, and meanwhile by visiting them, the tour length of the SenCar is no more than a threshold. In the second step, we consider data gathering performance when the SenCar migrates among these anchor points. We formulate the problem into a network utility maximization problem and propose a distributed algorithm to adjust data rates at which sensors send buffered data to the SenCar, link scheduling and flow routing so as to adapt to the up-to-date energy replenishing status of sensors. Besides general networks, we also study a special scenario where sensors are regularly deployed. For this case we can provide a simplified solution of lower complexity by exploiting the symmetry of the topology. Finally, we validate the effectiveness of our approaches by extensive numerical results, which show that our solutions can achieve perpetual network operations and provide high network utility.

Data gathering is a fundamental operation in various applications of wireless sensor networks (WSNs), where sensor nodes sense information and forward data to a sink node via multi-hop wireless communications. Typically, data in a WSN is relayed over a tree topology to the sink for effective data gathering. A number of tree-based data gathering schemes have been proposed in the literature, most of which aim at maximizing network lifetime. However, the timeliness and reliability of gathered data are also of great importance to many applications in WSNs. To achieve low-latency, high-reliability data gathering in WSNs, in this paper, we construct a data gathering tree based on a reliability model, schedule data transmissions for the links on the tree and assign transmitting power to each link accordingly. Since the reliability of a link is highly related to its signal to interference plus noise ratio (SINR), the SINR of all the currently used links on the data gathering tree should be greater than a threshold to guarantee high reliability. We formulate the joint problem of tree construction, link scheduling and power assignment for data gathering into an optimization problem, with the objective of minimizing data gathering latency. We show the problem is NP-hard and divide the problem into two subproblems: Constructing a low-latency data gathering tree; Jointly link scheduling and power assignment for the data gathering tree. We then propose a polynomial heuristic algorithm for each subproblem and conduct extensive simulations to verify the effectiveness of the proposed algorithms. Our simulation results show that the proposed algorithms achieve much lower data gathering latency than existing data gathering strategies while guaranteeing high reliability. Moreover, the algorithms also have a comparable energy efficiency and network lifetime to other algorithms.

Clustering has been widely used in wireless sensor networks to increase scalability, improve energy efficiency and provide QoS guarantees. In such networks, frequent interactions between the intra-cluster communication and the inter-cluster communication are inevitable, which may severely downgrade the communication efficiency and hence the network performance if not handled properly. This is especially problematic in delaysensitive data gathering applications. Thus, proper synchronization among these two types of communications is required. In this paper, we propose two approaches to schedule the communications in clustered wireless sensor networks aiming at delay-sensitive applications. In the first approach, an efficient cycle-based synchronous scheduling is proposed to achieve low average packet delay and high throughput by optimizing the cycle length and transmission order. In the second approach, a novel clustering structure is introduced to eliminate the necessity of communication synchronization so that packets are transmitted with no synchronization delay, yielding very low end-to-end packet delay. Our extensive experimental results demonstrate the superior performance of both approaches. The distinct behavior of two scheduling approaches enables them to support a wide range of data gathering applications with different performance requirements in clustered wireless sensor networks.

Data gathering is a fundamental operation for various applications of wireless sensor networks (WSNs), where sensor nodes sense information and forward data to a sink node via multihop wireless communications. Typically, data in a WSN is relayed over a tree topology to the sink for effective data gathering. A number of tree-based data gathering schemes have been proposed in the literature, most of which aim at maximizing network lifetime. However, the timeliness and reliability of gathered data are also of great importance to many applications in WSNs. To achieve low-latency, high-reliability data gathering in WSNs, in this paper, we construct a data gathering tree based on a reliability model, schedule data transmissions for the links on the tree and assign transmitting power to each link accordingly. Since the reliability of a link is highly related to its signal to interference plus noise ratio (SINR), the SINR of all the currently used links on the data gathering tree should be greater than a threshold to guarantee high reliability. We formulate the joint problem of tree construction, link scheduling and power assignment for data gathering into an optimization problem, with the objective of minimizing data gathering latency. We show the problem is NP-hard and divide the problem into two subproblems: Construction of a low-latency data gathering tree; Jointly link scheduling and power assignment for the data gathering tree. We then propose a polynomial heuristic algorithm for each subproblem and conduct extensive simulations to verify the effectiveness of the proposed algorithms. Our simulation results show that the proposed algorithms achieve much lower data gathering latency than existing data gathering strategies while guaranteeing high reliability.

The emerging wireless energy transfer technology enables charging sensor batteries in a wireless sensor network (WSN) and maintaining perpetual operation of the network. Recent breakthrough in this area has opened up a new dimension to the design of sensor network protocols. In the meanwhile, mobile data gathering has been considered as an efficient alternative to data relaying in WSNs. However, time variation of recharging rates in wireless rechargeable sensor networks imposes a great challenge in obtaining an optimal data gathering strategy. In this paper, we propose a framework of joint Wireless Energy Replenishment and anchor-point based Mobile Data Gathering (WerMDG) in WSNs by considering various sources of energy consumption and time-varying nature of energy replenishment. To that end, we first determine the anchor point selection and the sequence to visit the anchor points. We then formulate the WerMDG problem into a network utility maximization problem which is constrained by flow conversation, energy balance, link and battery capacity and the bounded sojourn time of the mobile collector. Furthermore, we present a distributed algorithm composed of cross-layer data control, scheduling and routing subalgorithms for each sensor node, and sojourn time allocation subalgorithm for the mobile collector at different anchor points. Finally, we give extensive numerical results to verify the convergence of the proposed algorithm and the impact of utility weight on network performance.

Many data center networks (DCNs) adopt a multirooted tree structure called fat-tree, which has the potential to deliver large bisection bandwidth through rich path multiplicity. However, unbalanced traffic load distribution may prevent efficient utilization of such high degree of parallelism. Meanwhile, high bandwidth multicast communication is critical to many data center services and applications. Hence, in this paper we consider multicast traffic load balance problem in fat-tree DCNs from a novel angle, aiming to find the most cost-effective way to build a multicast fat-tree DCN with bounded link oversubscription ratio. First, we present a multi-rate network model to accurately describe the communication environment in a fat-tree DCN. Then, we derive the minimum number of core switches required to achieve bounded link oversubscription ratio under arbitrary multicast traffic. Finally, we provide a comprehensive comparison on the cost of different approaches to building such a multicast fat-tree DCN.

Energy efficiency of optical packet switches (OPS) is the key to ensure the profitability of backbone network providers. However, due to lack of optical random access buffer, most optical packet switches rely on electronic buffer to resolve output contention, which requires power-hungry O/E/O conversion for all packets. The recently proposed optical cut-through (OpCut) switch holds a great potential in achieving high energy efficiency, as it allows optical packets to cut through the switch in optical domain whenever possible. The energy efficiency of OpCut switch hinges on the cut-through ratio, which is the percentage of packets that cut through the switch optically. On the other hand, it is generally desirable to maintain packet order in a switch. To achieve in-order transmission, an optical packet needs to be converted to electronic form and buffered when an earlier packet from the same flow is still in the buffer, which may lead to a low cut-through ratio. In the meanwhile, the Internet is designed to accommodate a certain degree of packet reorder, which is very common in practice due to path multiplicity. In this paper, we introduce a novel reorder metric, reorder degree, to accurately describe the extent of packet reordering, and propose a flow management scheme to bound the reorder degree of transmitted flows. We then design an efficient packet scheduling algorithm that significantly increases the cutthrough ratio of the OpCut switch while allowing a small degree of out-of-order transmission. Our extensive simulation results show that the cut-through ratio can be drastically increased with only a very small reorder degree.

A wireless mesh network (WMN) is a special type of wireless ad-hoc network, which consists of mesh clients, mesh routers and gateways to the Internet, organized in a mesh topology. The mesh clients are often laptops, cell phones and other wireless devices. Mesh routers forward traffic between mesh clients and gateways. Despite a number of promising features provided by WMNs, such as low deployment cost, self-healing, etc., the throughput of WMNs is often limited by severe congestion and collisions, and thus cannot satisfy the increasing traffic demands of numerous applications. In this paper, we study how to maximize the throughput of IEEE 802.11n WMNs by joint routing and frame aggregation. Frame aggregation is to aggregate multiple frames into a large frame before transmission, to reduce communication overhead and alleviate collisions. We first show that previous frame aggregation strategies cannot achieve optimal network throughput. We then formulate the joint problem into a linear programming (LP) problem by considering traffic in the network as flow. As most previous algorithms for LP are centralized and difficult to deploy in large-scale WMNs, we propose a distributed algorithm to solve the formulated problem, in which each mesh router determines the amount of traffic flow for its adjacent links based on the traffic information of neighbors and interfering links. However, in realistic 802.11n WMNs, traffic is transmitted in frames instead of flow, and the traffic to different routers needs to be distinguished. Thus, we further provide an algorithm to determine the routing and frame aggregation strategy for each mesh router, using the traffic flow derived from the first algorithm. We have conducted extensive simulations to evaluate the proposed algorithms and the results demonstrate that the network throughput can be significantly improved compared with existing schemes.

Multicast benefits numerous data center applications that require group communication by eliminating sending unnecessary duplicated packets in the network, thus significantly reduces network traffic and improves application throughput. Meanwhile, many data center networks (DCNs) adopt a multi-rooted tree structure called fat-tree, which utilizes rich path multiplicity to deliver high bisection bandwidth. However, currently there is no efficient flow scheduling algorithm for the fat-tree that can route multicast flows appropriately to achieve traffic load balance, thus cannot fully take advantage of this high degree of link parallelism. Besides low bandwidth utilization, unbalanced traffic load distribution also leads to unpredictable network performance and degraded data center agility. In this paper, we study multicast traffic load balance problem in fat-tree DCNs. First, we derive a minimum link oversubscription upper bound in multicast fat-tree DCNs based on a network model that accurately describes the DCN communication environment. Then, we present Oversubscription Bounded Multicast Scheduling (OBMS), a low-complexity multicast flow scheduling algorithm that guarantees bounded link oversubscription and efficient network utilization even under the most congested traffic patterns. Finally, we evaluate the performance of OBMS in an event-driven DCN simulator under various types of traffic patterns, and show that OBMS significantly outperforms other load-balance methods in terms of network throughput and evenness of traffic load distribution.

Mobile vehicles equipped with wireless energy transmission technology can recharge sensor nodes over the air. When to recharge which nodes, and in what order, critically impact the network performance. So far only a few works have studied the recharging policy for a single mobile vehicle. In this paper, we study how to coordinate the recharging activities of multiple mobile vehicles, which provide more scalability and robustness than a single vehicle. We leverage concepts and mechanisms from NDN (Named Data Networking) to design energy monitoring protocols that deliver energy status information to mobile vehicles in an efficient manner. Then we study how to minimize the total traveling cost of multiple vehicles while ensuring no node failure. We derive theoretical results on the energy neutral condition and the minimum number of mobile vehicles required for perpetual network operations. We formulate the optimization problem into a Multiple Traveling Salesman Problem with Deadlines (m-TSP with Deadlines), which is NP-hard. To accommodate the dynamic nature of node energy conditions and reduce computational overhead, we present a heuristic algorithm that selects the node with the minimum weighted sum of traveling time and residual lifetime. Our scheme not only improves network scalability but also guarantees the perpetual operation of networks. Finally, we conduct extensive simulations to demonstrate the effectiveness and efficiency of our proposed design, and validate the correctness of theoretical analysis.

Recently, cooperative retransmissions have exhibited great potentials in enhancing the reliability and efficiency of wireless communications by exploring spatial diversity. With cooperative retransmissions, a cooperative node helps retransmit an overheard frame if the frame from a sender fails to reach the destination. Several cooperative retransmission schemes have been proposed for wireless local area networks (WLANs) in the literature. However, most of them require explicit coordination between the sender and the cooperative node before each retransmission, which results in a non-negligible overhead. Moreover, these schemes are not designed for the latest IEEE 802.11n standard, and are incompatible with the frame aggregation and block ACK mechanisms of 802.11n. In this paper, we propose an efficient cooperative retransmission MAC (CAR-MAC) protocol that utilizes new features of 802.11n and is compatible with standard 802.11n transmissions. In CAR-MAC, all nodes periodically broadcast a C-Beacon message to release their retransmitting capability, and each node selects a cooperative node based on received CBeacon messages. If some sub-frames in the aggregated frame from the sender fail to reach the destination, the cooperative node retransmits the failed sub-frames together with its own new sub frames, such that overhead from cooperative retransmissions is amortized by normal frame transmissions. We have theoretically analyzed the improvement on network throughput brought by CAR-MAC protocol. In addition, we have conducted extensive simulations to evaluate CAR-MAC protocol under various channel conditions. Both theoretical and simulation results show that the proposed protocol can greatly improve network throughput and reduce packet delay, compared with the 802.11n standard and existing cooperative retransmission schemes.

In wireless local area networks (WLANs), link-layer multicast is a promising technology for many multimedia applications, e.g., video conference, as multicast frames can reach multiple clients simultaneously. However, the efficiency of multicast in WLANs is unsatisfactory since multicast frames are transmitted at low data rates to reach clients with poor channel quality. Moreover, the reliability of multicast cannot be guaranteed either, as multicast transmissions are not acknowledged. Some recent works have utilized smart antennas to improve multicast performance. But most of them require customized hardware and are not designed for the latest IEEE 802.11 standard, 802.11n WLANs. In this paper, we consider link-layer multicast in 802.11n WLANs with smart antennas. We partition clients into several groups, then select an antenna pattern from smart antennas and a multicast rate for each group, and transmit the same frame to each group. We first examine the gain of smart antennas and reliability of various 802.11n data rates for multicast in indoor WLANs via experiments. We then present the system model for multicast over smart antennas and formulate the problem into a mixed integer program. After that, we propose an optimal algorithm for the mixed integer program, under the condition that the packet reception ratio (PRR) of all antenna patterns and data rates is known for every client. As clients join and leave the network frequently and the wireless channel is time varying, we also propose an on-line algorithm that is able to adapt the partition of clients, antenna pattern and multicast rate for each group dynamically, based on PRR reports from clients. We have implemented the on-line algorithm on off-the-shelf WLAN products and conducted extensive experiments to evaluate the performance. The results show that the proposed algorithm can significantly improve multicast throughput compared to other strategies, and at the same time guarantee high PRR for all clients.

Nonuniform energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. For this problem, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.

A mobile vehicle equipped with wireless energy transmission technology can move around a wireless sensor network and recharge nodes over the air, leading to potentially perpetual operation if nodes can always be recharged before energy depletion. When to recharge which nodes, and in what order, critically impact the outcome. So far only a few works have studied this problem and relatively static recharging policies were proposed. However, dynamic changes such as unpredictable energy consumption variations in nodes, and practical issues like scalable and efficient gathering of energy information, are not yet addressed. In this paper, we propose NETWRAP, an NDN based Real Time Wireless Recharging Protocol for dynamic recharging in wireless sensor networks. We leverage concepts and mechanisms from NDN (Named Data Networking) to design a set of protocols that continuously gather and deliver energy information to the mobile vehicle, including unpredictable emergencies, in a scalable and efficient manner. We derive analytic results on energy neutral conditions that give rise to perpetual operation. We also discover that optimal recharging of multiple emergencies is an Orienteering problem with Knapsack approximation. Our extensive simulations demonstrate the effectiveness and efficiency of the proposed framework and validate the theoretical analysis.

In this paper, we study multicast scheduling in all-optical packet switches. We first propose a novel optical buffer called multicast-enabled Fiber-Delay-Lines (M-FDLs), which can provide flexible delay for copies of multicast packets using only a small number of FDL segments. We then present a Delay-Guaranteed Multicast Scheduling (DGMS) algorithm that considers the schedule of each arriving packet for multiple time slots. We show that DGMS has several desirable features, such as guaranteed delay upper bound and adaptivity to transmission requirements. To relax the time constraint of DGMS, we further propose a parallel and pipeline architecture for DGMS that distributes the scheduling task to multiple pipelined processing stages, with N processors in each stage, where N is the switch size. Finally, by using a simple combination logic circuit, we show that each processor can finish the scheduling for one time slot in O(1) time. The performance of DGMS is tested extensively against statistical traffic models and real Internet traffic, and the results show that the proposed DGMS algorithm can achieve ultra-low average packet delay with minimum packet drop ratio.

As the latest IEEE 802.11 standard, 802.11n allows a maximum physical data rate as high as 600Mbps, making it a desirable candidate for wireless local area network (WLAN) deployment. In WLANs, access points (APs) are often densely deployed, and thus neighboring APs should be assigned with orthogonal channels to avoid performance degradation caused by interference. It is challenging to find the optimal channel assignment strategy, as the number of channels is very limited. Many channel assignment schemes have been proposed for WLANs in the literature. However, most of them were not designed for 802.11n WLANs, and did not consider the challenges from the new channel bonding and frame aggregation mechanisms. Moreover, the impact of multi-rate clients on channel assignment is not fully investigated yet. In this paper, we study channel assignment in multi-rate 802.11n WLANs, aiming at maximizing the network throughput. We first present a network model and an interference model, and estimate the client throughput based on them. We then formulate the channel assignment problem into a throughput optimization problem. As the formulated problem is NP-hard, we propose a distributed channel assignment algorithm to provide practical solutions. We have conducted extensive simulations to evaluate the proposed algorithm and the results show that the network throughput can be significantly improved compared with existing schemes.

In this paper, we consider lossy mobile ad hoc networks where the data rate of a given flow becomes lower and lower along its routing path, and propose a cross-layer rate-effective network utility maximization (RENUM) framework by taking into account the lossy nature of wireless links and the constraints of rate outage probability and average delay. In the proposed framework, the utility is associated with the effective rate received at the destination node of each flow instead of the injection rate at the source of the flow. We then present a distributed joint transmission rate, link power and average delay control algorithm, in which explicit broadcast message passing is required for power allocation algorithm. The proposed algorithm is shown through numerical simulations to outperform other network utility maximization algorithms without rate outage probability/average delay constraints, leading to a higher effective rate, lower power consumption and delay.

Recent studies have shown that environmental energy harvesting technologies have the potential to provide perpetual operation to wireless sensor networks. However, due to the large variations of the ambient energy source, such networks could only support low-rate data services and the performance is affected by many unpredictable environmental factors. To deliver energy to sensor nodes reliably, in this paper, we apply the novel wireless power transmission technology to rechargeable sensor networks by introducing a mobile actuator to replenish sensor energy wirelessly. We first establish an analytical model based on stochastic wireless energy replenishment to obtain a variety of performance metrics. Then based on the theoretical results, we further propose battery-aware mobile energy replenishment scheme and present two heuristic algorithms: (1) linear adaptation sensor activation with prioritized recharge; and (2) battery-aware activation with selective recharge. We validate the theoretical results and evaluate the performance of the proposed algorithms through extensive simulations. The results demonstrate that a good design of sensor activation with effective control of mobile energy replenishment can provide substantial performance improvement.

With the popularity of wireless devices and the increase of computing and storage resources, there are increasing interests in supporting mobile computing techniques. Particularly, ad hoc networks can potentially connect different wireless devices to enable more powerful wireless applications and mobile computing capabilities. To meet the ever increasing communication need, it is important to improve the network throughput while guaranteeing transmission reliability. Multiple-input-multiple-output (MIMO) technology can provide significantly higher data rate in ad hoc networks where nodes are equipped with multiantenna arrays. Although MIMO technique itself can support diversity transmission when channel condition degrades, the use of diversity transmission often compromises the multiplexing gain and is also not enough to deal with extremely weak channel. Instead, in this work, we exploit the use of cooperative relay transmission (which is often used in a single antenna environment to improve reliability) in a MIMO-based ad hoc network to cope with harsh channel condition. We design both centralized and distributed scheduling algorithms to support adaptive use of cooperative relay transmission when the direct transmission cannot be successfully performed. Our algorithm effectively exploits the cooperative multiplexing gain and cooperative diversity gain to achieve higher data rate and higher reliability under various channel conditions. Our scheduling scheme can efficiently invoke relay transmission without introducing significant signaling overhead as conventional relay schemes, and seamlessly integrate relay transmission with multiplexed MIMO transmission. We also design a MAC protocol to implement the distributed algorithm. Our performance results demonstrate that the use of cooperative relay in a MIMO framework could bring in a significant throughput improvement in all the scenarios studied, with the variation of node density, link failure ratio, packet arrival rate, and retransmission threshold.

In this paper, we study multicast scheduling in the OpCut switch, a recently proposed hybrid optical/electronic switching architecture for transmitting high-volume traffic in core networks and parallel computers. First, we present a multicast scheduling algorithm called Guaranteed Latency Multicast Scheduling (GLMS) that considers the schedule of each packet for multiple time slots. We show that GLMS has several desirable features, such as guaranteed latency for all transmitted packets and adaptivity to transmission requirements. To relax the time constraint on computing a schedule, we further propose a parallel and pipeline processing architecture for GLMS that distributes the scheduling task to multiple pipelined processing stages, with N processors in each stage, where N is the switch size. Finally, by implementing it with simple combination logic circuits, we show that each processor can finish the scheduling for one time slot in (O(1)time complexity. We evaluate the performance of GLMS extensively against statistical traffic models and real Internet traffic, and the results show that the proposed GLMS algorithm can achieve very low average packet latency with minimum packet drop ratio.

With the development of multiprocessor system on chips (MPSoCs), it is expected that hundreds of computing cores will be operating on a single chip in the near future. This will require high-performance on-chip networks with very low latency to provide a communication substrate for the increasing number of cores. In this paper, we consider Gaussian on-chip networks that are of significant topological advantages over traditional mesh and torus networks in terms of diameter and average hop distance. Many applications on MPSoCs need global data movement and global control to exchange data and synchronize the execution among cores, which require all-to-all broadcast communication. In this paper, we propose an all-to-all broadcast algorithm suitable for on-chip implementation on the Gaussian network topology. The algorithm utilizes controlled message flooding based on a broadcast pattern, which can be described in a formal, generic way for each node in terms of a few simple operations and can be easily built into router hardware. Furthermore, the generic broadcast pattern also ensures a balanced traffic load in all dimensions in the network so that minimum total latency for all-to-all broadcast can be achieved. The algorithm overlaps message switching time with transmission time in a pipelined fashion to further reduce the total communication latency of all-to-all broadcast. Comparison results demonstrate the topological merits of Gaussian networks and ultralow latency of the proposed all-to-all broadcast algorithm.

In this paper, we present the design and implementation of a general, flexible, hardware-aware network platform that takes hardware processing behavior into consideration to accurately evaluate network performance. The platform adopts a network-hardware co-simulation approach in which the NS-2 network simulator supervises the network-wide traffic flow and the SystemC hardware simulator simulates the underlying hardware processing in network nodes. In addition, as a case study, we implemented wireless all-to-all broadcasting with network coding on the platform. We analyze the hardware processing behavior during the algorithm execution and evaluate the overall performance of the algorithm. Our experimental results demonstrate that hardware processing can have a significant impact on the algorithm performance and hence should be taken into consideration in the algorithm design. We expect that this hardware-aware platform will become a very useful tool for more accurate network simulations and more efficient design space exploration of processing-intensive applications.

Current study on prolonging lifetime for wireless sensor networks (WSNs) mainly focuses on two techniques. The first technique is to reduce energy consumption of sensor nodes, while the second technique is to recharge sensor nodes by harvesting energy from the ambient environment or RF based energy transmission. However, neither of these two techniques are able to guarantee network lifetime and network performance. In order to achieve perpetual operation for WSNs while providing high network utility, in this paper we propose an optimal wireless energy replenishment and mobile data gathering mechanism (OWER-MDG) which charges sensor nodes effectively and collects data from the network using a mobile vehicle (SenCar). We study the application of OWER-MDG in WSNs and provide an efficient algorithm which maximizes network utility. Our numerical results demonstrate the performance advantage of OWER-MDG and provide a guidance on parameter selection for system design.

It is challenging to provide QoS in wireless ad hoc networks. One of the main problems that affects QoS in wireless ad hoc networks is the multi-hop nature of the network which generates high volume of control overhead. Such overhead is necessary to create/maintain network routes. Congested routes further aggravate the existing problem by generating more control packets for performing route maintenance. In addition, established routes are not well-protected and are subject to the changes in traffic load, which further reduces the QoS provided and wastes network resources. Therefore, in this paper, we propose a flow admission control scheme at the routing layer to mitigate the above problem by taking pre-emptive measures through bandwidth and congestion estimation. The scheme can reduce unnecessary control overhead for route maintenance and select a proper route for a flow, thus improve the overall network performance. Moreover, established routes can be protected from any changes in traffic load for the duration of the route lifetime. Our extensive simulation results demonstrate that the proposed scheme achieves good network performance.

As the latest amendment of IEEE 802.11 standard, 802.11n allows a maximum raw data rate as high as 300Mbps, making it a desirable candidate for wireless local area network (WLAN) deployment. In typical deployment, the coverage areas of nearby access points (APs) usually overlap with one another to provide satisfactory coverage and seamless mobility support. Clients tend to associate (connect) to the AP with the strongest signal strength, which might lead to poor client throughput and overloaded APs. Although a number of AP association schemes have been proposed for IEEE 802.11 WLANs in previous studies, none of them have considered the frame aggregation feature in 802.11n. Moreover, the impact of legacy 802.11a/b/g clients in 802.11n WLANS has not been considered in AP association. To fill in this gap, in this paper we explore AP association for 802.11n with heterogeneous clients (802.11a/b/g/n). We first formulate it into an optimization problem based on a bi-dimensional Markov model, aiming at providing clients with the bandwidth proportional to their highest physical data rates, and then propose two heuristic AP association algorithms that can efficiently make online decisions on AP association. We have also conducted extensive simulations and experiments to validate the proposed algorithms. Our simulation results show that under hotspot client distribution, the proposed algorithms can boost the throughput of 802.11n clients and overall throughput by 106% and 89%, respectively, compared to other AP association schemes. Experiments also confirm the effectiveness of the algorithms in enhancing aggregated throughput, maintaining proportional fairness among clients and balancing load among APs.

In this paper, we consider mobile data gathering in wireless sensor networks (WSNs) by using a mobile collector with multiple antennas. By taking into account the elastic nature of wireless link capacity and the power control for each sensor, we first propose a data gathering cost minimization (DaGCM) framework with concurrent data uploading, which is constrained by flow conservation, energy consumption, link capacity, compatibility among sensors and the bound on total sojourn time of the mobile collector at all anchor points. One of the main features of this framework is that it allows concurrent data uploading from sensors to the mobile collector to sharply shorten data gathering latency and significantly reduce energy consumption due to the use of multiple antennas and space-division multiple access technique. We then relax the DaGCM problem with Lagrangian dualization and solve it with the subgradient iteration algorithm. Furthermore, we present a distributed algorithm composed of cross-layer data control, routing, power control and compatibility determination subalgorithms with explicit message passing. We also give the subalgorithm for finding the optimal sojourn time of the mobile collector at different anchor points. Finally, we provide numerical results to show the convergence of the proposed DaGCM algorithm and its advantages over the algorithm without concurrent data uploading and power control in terms of data gathering latency and energy consumption.

Clos networks and their variations such as folded- Clos networks (fat-trees) have been widely adopted as network topologies in data center networks. Since multicast is an essential communication pattern in many cloud services, nonblocking multicast communication can ensure the high performance of such services. However, nonblocking multicast Clos networks are costly due to the large number of middle stage switches required. On the other hand, server redundancy is ubiquitous in today's data centers to provide high availability of services. In this paper, we explore server redundancy in data centers to reduce the cost of nonblocking multicast Clos data center networks (DCNs). First, we show that the sufficient nonblocking condition on the number of middle stage switches for multicast Clos DCNs can be significantly reduced, when the data center is 2-redundant, i.e., each server in the data center has exactly one redundant backup. We then investigate more general cases that the data center is k-redundant (k >; 2), and show that a higher redundancy level further reduces the cost of nonblocking multicast Clos DCNs. We also extend the result to practical data centers where servers may have different number of redundant backups depending on the availability requirement of services provided. Finally, we provide a multicast routing algorithm with linear time complexity to configure multicast connections in Clos DCNs.

Fat-tree networks have been widely adopted as network topologies in data center networks (DCNs). However, it is costly for fat-tree DCNs to support nonblocking multicast communication, due to the large number of core switches required. Since multicast is an essential communication pattern in many cloud services and nonblocking multicast communication can ensure the high performance of such services, reducing the cost of nonblocking multicast fat-tree DCNs is very important. On the other hand, server redundancy is ubiquitous in today's data centers to provide high availability of services. In this paper, we explore server redundancy in data centers to reduce the cost of nonblocking multicast fat-tree data center networks (DCNs). First, we present a multirate network model that accurately describes the communication environment of the fat-tree DCNs. Then, we show that the sufficient number of core switches for nonblocking multicast communication under the multirate model can be significantly reduced in arbitrary 2-redundant fat-tree DCNs, i.e., each server has exactly one redundant backup in the data center. We generalize the result to practical fat-tree DCNs where servers may have different number of redundant backups depending on the availability requirements of services they provide, and show that a higher redundancy level further reduces the cost of nonblocking multicast fat-tree DCNs. Finally, we propose a multicast routing algorithm with linear time complexity to configure multicast connections in fat-tree DCNs.

Compression, as a popular technique to reduce data size by exploiting data redundancy, can be used in delay sensitive wireless sensor networks (WSNs) to reduce end-to-end packet delay as it can reduce packet transmission time and contention on the wireless channel. However, the limited computing resources at sensor nodes make the processing time of compression a nontrivial factor in the total delay a packet experiences and must be carefully examined when adopting compression. In this paper, we first study the effect of compression on data gathering in WSNs under a practical compression algorithm. We observe that compression does not always reduce packet delay in a WSN as commonly perceived, whereas its effect is jointly determined by the network configuration and hardware configuration. Based on this observation, we then design an adaptive algorithm to make online decisions such that compression is only performed when it can benefit the overall performance. We implement the algorithm in a completely distributed manner that utilizes only local information of individual sensor nodes. Our extensive experimental results show that the algorithm demonstrates good adaptiveness to network dynamics and maximizes compression benefit.

Recent study reveals that great benefit can be achieved for data gathering in wireless sensor networks by employing mobile collectors that gather data via short-range communications. To pursue maximum energy saving at sensor nodes, intuitively, a mobile collector should traverse the transmission range of each sensor in the field such that each data packet can be directly transmitted to the mobile collector without any relay. However, this approach may lead to significantly increased data gathering latency due to the low moving velocity of the mobile collector. Fortunately, it is observed that data gathering latency can be effectively shortened by performing proper local aggregation via multihop transmissions and then uploading the aggregated data to the mobile collector. In such a scheme, the number of local transmission hops should not be arbitrarily large as it may increase the energy consumption on packet relays, which would adversely affect the overall efficiency of mobile data gathering. Based on these observations, in this paper, we study the tradeoff between energy saving and data gathering latency in mobile data gathering by exploring a balance between the relay hop count of local data aggregation and the moving tour length of the mobile collector. We first propose a polling-based mobile gathering approach and formulate it into an optimization problem, named bounded relay hop mobile data gathering (BRH-MDG). Specifically, a subset of sensors will be selected as polling points that buffer locally aggregated data and upload the data to the mobile collector when it arrives. In the meanwhile, when sensors are affiliated with these polling points, it is guaranteed that any packet relay is bounded within a given number of hops. We then give two efficient algorithms for selecting polling points among sensors. The effectiveness of our approach is validated through extensive simulations.

Buffered crossbar switches are a special type of crossbar switches with a small buffer at each crosspoint of the crossbar. Existing research results indicate that they can provide port based performance guarantees with speedup of two, but require significant hardware complexity to provide flow based performance guarantees. In this paper, we present scheduling algorithms for buffered crossbar switches to achieve flow based performance guarantees with speedup of two and one buffer per crosspoint. When there is no crosspoint blocking, only simple and distributed input scheduling and output scheduling are needed. Otherwise, a special urgent matching procedure is necessary to guarantee on-time delivery of crosspoint blocked cells. For urgent matching, we present both sequential and parallel matching algorithms. The parallel version significantly reduces the average number of iterations for convergence, which is verified by simulation. With the proposed algorithms, buffered crossbar switches can provide flow based performance guarantees by emulating push-in-first-out output-queued switches, and we use the counting method to prove the perfect emulation. Finally, we discuss an alternative backup-buffer implementation design to the bypass path, and compare our scheme with existing solutions.

Recent advances have shown a great potential of mobile data gathering in wireless sensor networks, where one or more mobile collectors are employed to collect data from sensors via short-range communications. Among a variety of data gathering approaches, one typical scheme is called anchor-based mobile data gathering. In such a scheme, during each periodic data gathering tour, the mobile collector stays at each anchor point for a period of sojourn time, and in the meanwhile the nearby sensors transmit data to the collector in a multihop fashion. In this paper, we focus on such a data gathering scheme and provide distributed algorithms to achieve its optimal performance. We consider two different cases depending on whether the mobile collector has fixed or variable sojourn time at each anchor point. We adopt network utility, which is a properly defined function, to characterize the data gathering performance, and formalize the problems as network utility maximization problems under the constraints of guaranteed network lifetime and data gathering latency. To efficiently solve these problems, we decompose each of them into several subproblems and solve them in a distributed manner, which facilitates the scalable implementation of the optimization algorithms. Finally, we provide extensive numerical results to demonstrate the usage and efficiency of the proposed algorithms and complement our theoretical analysis.

In wireless networks, network coding has been considered as an effective approach that utilizes the broadcast nature of the wireless channel to achieve energy efficiency and improve the network throughput. While network coding can be utilized in different forms of communications, including unicast, multicast and broadcast, the MAC layer transmissions used for network coding are mainly multicast, therefore, such network coding based communications are substantially affected by the performance of the underlying MAC layer multicast. However, the commonly used IEEE 802.11 MAC protocol performs only a basic CSMA/CA mechanism for multicast, making the transmissions and the network coding based communications unreliable and less efficient. In this paper we propose NC-MAC, a novel MAC layer multicast protocol that are specifically designed to support reliable network coding based communications. Compared to existing reliable MAC multicast protocols, NC-MAC takes advantage of the unique characteristics of network coding to expedite the multicast procedure. We evaluate the performance of NCMAC for two typical network coding algorithms through ns-2 simulations. The results demonstrate the superior performance of NC-MAC over other MAC protocols in maintaining both reliability and efficiency.

In wireless local area networks (WLANs), collision-free channel access is desirable for real-time services that require guaranteed bandwidth and bounded delay. In WLANs with a single access point (AP), collision-free access can be achieved by applying the point coordination function (PCF), where the AP polls all associated clients for data transmissions. However, in larger WLANs with multiple APs, if there is no inter-AP coordination mechanism, concurrent transmissions from nearby basic service sets (BSSs) may collide and thus degrade service performance even if all APs operate on the PCF mode. So far only few schemes have been proposed to resolve this problem, and the client throughput in these schemes is quite limited due to the inaccurate modeling of polling conflicts. In this paper, we study client polling in multi-AP WLANs, with the objective of providing high-throughput, collision-free channel access for each client, and maximizing network capacity. We first give a WLAN framework in which the PCF of all APs is coordinated and clients are polled in a time slotted manner.We then formulate client polling into a time slot allocation problem and propose a collision-free polling scheme consisting of three procedures: (1) a basic polling procedure that determines the minimum number of time slots required to poll every client once to obtain the polling frequencies of all clients; (2) a complementary polling procedure that makes extra polls for APs that have idle time slots without causing collisions, to improve spatial reuse of the network; (3) a backup poll selecting procedure that finds backup clients to poll in case the current polled client has no data to transmit, to utilize the otherwise wasted bandwidth. We have conducted extensive simulations and compared it with two existing schemes. The simulation results show that the proposed scheme can provide high throughput and uniform channel access time for all clients, while boosting spatial reuse 2 to 3 times compared to other schemes.

In this paper, we propose a distributed resource allocation framework for cognitive radio networks by using the orthogonal frequency division multiple access (OFDMA) modulation. We jointly consider the constraints of quality of service (QoS), maximum power, and minimum rates in the network to obtain optimal available subcarrier sets and transmission power. The fairness of resource allocation is guaranteed by incorporating the probability that a subcarrier is occupied into the link capacity expression. We present a distributed subcarrier selection and power allocation algorithm and evaluate the algorithm through simulations. Our results confirm that the proposed algorithm outperforms the existing algorithms in terms of throughput, the number of secondary links admitted, and the fairness of resource allocation.

This paper investigates the performance of network coding (NC) in unreliable wireless networks and the integration with TCP protocol. As the wireless nodes have limited processing capacity and energy, it will be difficult for them to deal with complex problems. Coding and decoding with traditional NC will cause a large overhead for wireless nodes. It is necessary to improve the NC scheme for applying to wireless networks. Furthermore, unreliable wireless channels will result in a lot of unnecessary retransmissions in wireless networks. In this paper, we propose a joint generation network coding scheme to improve the performance of NC in wireless networks. We first analyze the impact of the probability of decoding under lossy wireless channels in the traditional NC and joint generation NC. Then, we design a scheme that integrates the proposed network coding scheme with TCP. By adopting the joint generation NC, we could avoid unnecessary retransmissions in wireless networks due to the loss of acknowledgment in TCP protocol. Our simulation results demonstrate that joint generation NC could greatly reduce retransmissions.

All-optical packet switches (OPS) are considered as a good candidate for future ultra-fast communications as they do not require optical-electronic-optical (O/E/O) conversions. However, currently there is still no practical optical random access memory available, which makes it difficult to reduce packet loss to an acceptable level in OPS. Thus, hybrid optical/electronic switch architectures, such as the switch proposed in which we refer to as the OpCut switch in this paper, are promising alternatives due to their potential to achieve ultra-low packet loss and packet delay. Although there has been extensive work on the performance modeling of different types of electronic and all-optical switches, little work has been done for the performance modeling of hybrid switches. In this paper, we present an efficient analytical model called the aggregation model that comprehensively analyzes various performance metrics of the OpCut switch under different types of traffic. By inductively aggregating more queues in the buffer into a block, the aggregation model can achieve a polynomial complexity to the switch size. We develop the aggregation model for the OpCut switch under both Bernoulli traffic and ON-OFF Markovian traffic. The effectiveness of our model is validated by extensive simulations. The results show that the aggregation model is very accurate in all tested scenarios.

Optical switches are widely considered as the most promising candidate to provide ultra-high speed interconnections. Due to the difficulty in implementing all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the Optical Cut-Through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. In this paper, we consider packet scheduling in this switch with wavelength division multiplexing (WDM). Our goal is to maximize throughput and maintain packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing it to the set packing problem, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of √2Nk with regard to the number of packets transmitted, where N is the switch size and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing. Based on the approximation algorithm, we also give practical schedulers that can be implemented in fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

Optical switching architectures with electronic buffers have been proposed to tackle the lack of optical Random Access Memories (RAM). Out of these architectures, the OpCut switch achieves low latency and minimizes optical-electronic-optical (O/E/O) conversions by allowing packets to cut-through the switch. In an OpCut switch, a packet is converted and sent to the electronic buffers only if it cannot be directly routed to the switch output. As the length of a time slot shrinks with the increase of the line card rate in such a high-speed system, it may become too stringent to calculate a schedule in each single time slot. In such a case, pipelining scheduling can be adopted to relax the time constraint. In this paper, we present a novel mechanism to pipeline the packet scheduling in the OpCut switch by adopting multiple “sub-schedulers.” The computation of a complete schedule for each time slot is done under the collaboration of sub-schedulers and spans multiple time slots, while at any time schedules for different time slots are being calculated simultaneously. We present the implementation details when two sub-schedulers are adopted, and show that in this case our pipelining mechanism eliminates duplicate scheduling which is a common problem in a pipelined environment. With an arbitrary number of sub-schedulers, the duplicate scheduling problem becomes very difficult to eliminate due to the increased scheduling complexity. Nevertheless, we propose several approaches to reducing it. Finally, to minimize the extra delay introduced by pipelining as well as the overall average packet delay under all traffic intensities, we further propose an adaptive pipelining scheme. Our simulation results show that the pipelining mechanism effectively reduces scheduler complexity while maintaining good system performance

In this paper, a three-layer framework is proposed for mobile data collection in wireless sensor networks, which includes the sensor layer, cluster head layer, and mobile collector (called SenCar) layer. The framework employs distributed load balanced clustering and MIMO uploading techniques, which is referred to as LBC-MU. The objective is to achieve good scalability, long network lifetime and low data collection latency. At the sensor layer, a distributed load balanced clustering (LBC) algorithm is proposed for sensors to self-organize themselves into clusters. In contrast to existing clustering methods, our scheme generates multiple cluster heads in each cluster to balance the work load and facilitate MIMO data uploading. At the cluster head layer, the inter-cluster transmission range is carefully chosen to guarantee the connectivity among the clusters. Multiple cluster heads within a cluster cooperate with each other to perform energy-saving inter-cluster communications. Through inter-cluster transmissions, cluster head information is forwarded to the SenCar for its moving trajectory planning. At the mobile collector layer, the SenCar is equipped with two antennas, which enables multiple cluster heads to simultaneously upload data to the SenCar. The trajectory planning for the SenCar is optimized to fully utilize MIMO uploading capability by properly selecting polling points in each cluster. By visiting each selected polling point, the SenCar can efficiently gather data from cluster heads and transport the data to the static data sink. Extensive simulations are conducted to evaluate the effectiveness of the proposed LBC-MU scheme. The results show that when each cluster has at most two cluster heads, LBC-MU can reduce the maximum number of transmissions a sensor performs by 90% and the average number of transmissions by 88% compared with the enhanced relay routing scheme. It also results in 25% shorter average data latency compared with the mobile collection scheme with single-head clustering.

Recent years have witnessed a surge of interest in efficient data gathering schemes in wireless sensor networks (WSNs). In this paper, we address this issue by adopting mobility and space-division multiple access (SDMA) technique. Specifically, mobile collectors, called SenCars in this paper, work like mobile base stations and collect data from associated sensors via single-hop transmissions so as to achieve uniform energy consumption. We also apply SDMA technique to data gathering by equipping each SenCar with multiple antennas such that distinct compatible sensors may successfully make concurrent data uploading to a SenCar. To investigate the utility of the joint design of controlled mobility and SDMA technique, we consider two cases, where a single SenCar and multiple SenCars are deployed in a WSN, respectively. For the single SenCar case, we aim to minimize the total data gathering time, which consists of the moving time of the SenCar and the data uploading time of sensors, by exploring the trade-off between the shortest moving tour and the full utilization of SDMA. We refer to this problem as mobile data gathering with SDMA, or MDG-SDMA for short. We formalize it into an integer linear program (ILP) and propose three heuristic algorithms for it. In the multi-SenCar case, the sensing field is divided into several regions, each having a SenCar. We focus on minimizing the maximum data gathering time among different regions and refer to it as mobile data gathering with multiple SenCars and SDMA (MDG-MS) problem. Accordingly, we propose a region-division and tour-planning (RDTP) algorithm in which data gathering time is balanced among different regions. We carry out extensive simulations and the results demonstrate that our proposed algorithms significantly outperform single SenCar and non-SDMA schemes.

Group communications are important in Mobile Ad hoc Networks (MANETs). Multicast is an efficient method for implementing group communications. However, it is challenging to implement efficient and scalable multicast in MANET due to the difficulty in group membership management and multicast packet forwarding over a dynamic topology. We propose a novel Efficient Geographic Multicast Protocol (EGMP). EGMP uses a virtual-zone-based structure to implement scalable and efficient group membership management. A networkwide zone-based bidirectional tree is constructed to achieve more efficient membership management and multicast delivery. The position information is used to guide the zone structure building, multicast tree construction, and multicast packet forwarding, which efficiently reduces the overhead for route searching and tree structure maintenance. Several strategies have been proposed to further improve the efficiency of the protocol, for example, introducing the concept of zone depth for building an optimal tree structure and integrating the location search of group members with the hierarchical group membership management. Finally, we design a scheme to handle empty zone problem faced by most routing protocols using a zone structure. The scalability and the efficiency of EGMP are evaluated through simulations and quantitative analysis. Our simulation results demonstrate that EGMP has high packet delivery ratio, and low control overhead and multicast group joining delay under all test scenarios, and is scalable to both group size and network size. Compared to Scalable Position-Based Multicast (SPBM) [CHECK END OF SENTENCE], EGMP has significantly lower control overhead, data transmission overhead, and multicast group joining delay.

Packet scheduling algorithms that deliver 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. Although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, the optical counterpart of electronic random access memory (RAM) is absent; second, the wavelength conversion capability of WDM interconnects changes the conditions for admissible traffic. To address these issues, in this paper, we first introduce a new fiber-delay-line (FDL)-based input buffering fabric that is able to provide flexible buffering delay, followed by a discussion on the conditions that admissible traffic must satisfy in a WDM interconnect. We then propose a weight-based scheduling algorithm, named Most-Packet Wavelength-Fiber Pair First (MPWFPF), and theoretically prove that given a buffering fabric with flexible delay, MPWFPF delivers 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose the WDM-i SLIP algorithm, a generalized version of the i SLIP algorithm for WDM interconnects, which efficiently finds an approximate optimal schedule with low time complexity. Extensive simulations have been conducted to verify the theoretical results, and test the performance of the proposed scheduling algorithms in input-buffered WDM interconnects.

With the development of Multi-Processor System-on-Chip (MP-SoC) in recent years, the intra-chip communication is becoming the bottleneck of the whole system. Current electronic network-on-chip (NoC) designs face serious challenges, such as bandwidth, latency and power consumption. Optical interconnection networks are a promising technology to overcome these problems. In this paper, we study the routing problem in optical NoCs with arbitrary network topologies. Traditionally, a minimum hop count routing policy is employed for electronic NoCs, as it minimizes both power consumption and latency. However, due to the special architecture of current optical NoC routers , such a minimum-hop path may not be energy-wise optimal. Using a detailed model of optical routers we reduce the energy-aware routing problem into a shortest-path problem, which can then be solved using one of the many well known techniques. By applying our approach to different popular topologies, we show that the energy consumed in data communication in an optical NoC can be significantly reduced. We also propose the use of optical burst switching (OBS) in optical NoCs to reduce control overhead, as well as an adaptive routing mechanism to reduce energy consumption without introducing extra latency. Our simulation results demonstrate the effectiveness of the proposed algorithms.

In this paper, we study packet scheduling in the OpCut switch, a recently proposed optical switching architecture that can be adopted for high-performance parallel computers. The key feature of the OpCut switch is that it allows packets to cut-through the switch whenever possible, such that packets experience minimum delay. Packets that cannot cut-through are received by optical receivers and stored in the electronic buffer, and can be sent to the output ports by the optical transmitters later. Due to its feed-back buffer structure, existing scheduling algorithms cannot be directly applied to the OpCut switch. Keeping packet order also becomesmore challenging in the OpCut switch. In this paper, we propose a scheduling algorithmfor the OpCut switch that achieves overall low packet latency while maintaining packet order. The scheduling algorithmis very simple and can be implemented in hardware. To relax the time constraint on computing a schedule, we further propose a mechanism to pipeline the packet scheduling in the OpCut switch by distributing the scheduling task to multiple “sub-schedulers.” Our simulation results show that the OpCut switch with the proposed scheduling algorithms achieve chose performance to the ideal output-queued (OQ) switch in terms of packet latency, and that the pipelined mechanism effectively reduces scheduler complexity while maintaining satisfactory system performance.

Media streaming is an important Internet application and has received more and more attention in recent years. Traditional media streaming systems are deployed in a server-client mode which scales poorly with the increasing population of the clients. Peer-to-peer media streaming can greatly enhance the scalability of the system by employing the clients to help forward the media content. In this paper, we consider optimizing the overlay construction for peer-to-peer streaming systems with heterogeneous access link bandwidths. Our goal is to maximize the total downloading rate and satisfy the heterogeneous downloading requirements when the uplink bandwidth is limited. We first formalize it into a problem of finding maximum number of edge disjoint trees in a graph which models the peers and their access link bandwidths. Then we give a centralized heuristic algorithm to solve the problem. Based on the centralized algorithm, we further propose a distributed algorithm which constructs an adaptive overlay topology that can adapt itself to the changing peers such that the end-to-end delay and link stress are minimized. We compare our scheme with another recently proposed scheme called MDM through simulations. Our simulation results show that the proposed scheme outperforms MDM by about 30% with respect to the average peer satisfaction. In addition, the proposed scheme achieves less link stress than MDM.

In this paper, we present the design and implementation of a general, flexible hardware-aware network platform which takes hardware processing behavior into consideration to accurately evaluate network performance. The platform adopts a network-hardware co-simulation which the NS-2 network simulator supervises the network-wide traffic flow and the SystemC hardware simulator simulates the underlying hardware processing in network nodes. In addition, as a case study, we implemented wireless all-to-all broadcasting with network coding on the platform. processing behavior during the algorithm execution and evaluate the overall performance of the algorithm. Our experimental results demonstrate that hardware processing has a significant impact on the algorithm performance and hence should be taken into consideration in the algorithm design. We expect that this hardware-aware platform will become a very useful tool for more accurate network simulations and optimal designs of processing-intensive applications.

Recent advances have shown a great potential of anchor based mobile data gathering in wireless sensor networks. In such a scheme, during each periodic data gathering tour, the mobile collector stays at each anchor point for a period of sojourn time and collects data from nearby sensors via multi-hop communications. We provide an optimization based distributed algorithm for such data gathering in this paper. We adopt network utility, which is a properly defined function, to characterize the data gathering performance, and formalize the problem as a network utility maximization problem under the constraint of guaranteed network lifetime. To efficiently solve the problem, we decompose it into two sets of subproblems and solve them in a distributed manner, which facilitates the scalable implementations. Finally, we provide numerical results to demonstrate the convergence of the proposed distributed algorithm.

Compression, as a popular technique to reduce data size by exploiting data redundancy, can be used in delay sensitive wireless sensor networks (WSNs) to reduce end-to-end packet delay as it can reduce packet transmission time and contention on the wireless channel. However, the limited computing resources at sensor nodes make the processing time of compression a nontrivial factor in the total delay a packet experiences and must be carefully examined when adopting compression. In this paper, we first study the effect of compression on data gathering in WSNs under a practical compression algorithm. We observe that that compression does not always reduce the packet delay in a WSN as commonly perceived, whereas its effect is jointly determined by the network configuration and hardware configuration. Based on this observation, we design an adaptive algorithm to make on-line decisions such that compression is only performed when it can benefit the overall performance. We implement the algorithm in a completely distributed manner that utilizes only local information of individual sensor nodes. Our extensive experimental results show that the algorithm demonstrates good adaptiveness to network dynamics and maximizes compression benefit.

Recently, several multi-channel MAC protocols have been proposed for wireless sensor networks (WSNs) to improve network capacity and boost energy efficiency. In addition, cooperative multiple-input multiple-output (MIMO) technique has been shown to be able to significantly enhance the energy efficiency of WSNs if properly configured. However, these two promising techniques have not been jointly utilized in WSNs. In this paper, we explore such a joint design by proposing a novel MAC protocol for WSNs that takes advantage of both multiple channels and cooperative MIMO. Specifically, sensor nodes in a WSN are organized into clusters and each cluster head selects some cooperative nodes to help forward traffic to or receive from other clusters by utilizing cooperative MIMO technique. For intra-cluster communications, different channels are assigned to adjacent clusters to reduce collisions, while for inter-cluster communications, cooperative MIMO links are scheduled to improve energy efficiency and concurrent transmissions are enabled by assigning different channels to them. We carry out extensive simulations and the results demonstrate that the proposed protocol can significantly increase throughput and improve energy efficiency compared to other schemes. For example, for a WSN with 150 nodes in a 250m × 250m field, with five or more available channels, the protocol can achieve over three times saturated throughput while saving up to 17% energy per bit for inter-cluster communications.

Recent studies have shown that significant benefit can be achieved in wireless sensor networks (WSNs) by employing mobile collectors for data gathering via short-range communications. A typical scenario for such a scheme is that a mobile collector roams over the sensing field and pauses at some anchor points on its moving tour such that it can traverse the transmission range of all the sensors in the field and directly collect data from each sensor. In this paper, we study the performance optimization of such mobile data gathering by formulating it into a cost minimization problem constrained by the channel capacity, the minimum amount of data gathered from each sensor and the bound of total sojourn time at all anchor points. We assume that the cost of a sensor for a particular anchor point is a function of the data amount a sensor uploads to the mobile collector during its sojourn time at this anchor point. In order to provide an efficient and distributed algorithm, we decompose this global optimization problem into two subproblems to be solved by each sensor and the mobile collector, respectively. We show that such decomposition can be characterized as a pricing mechanism, in which each sensor independently adjusts its payment for the data uploading opportunity to the mobile collector based on the shadow prices of different anchor points. Correspondingly, we give an efficient algorithm to jointly solve the two subproblems. Our theoretical analysis demonstrates that the proposed algorithm can achieve the optimal data control for each sensor and the optimal sojourn time allocation for the mobile collector, which minimizes the overall network cost. Finally, extensive simulation results further validate that our algorithm achieves lower cost than the compared data gathering strategy.

Recent experimental studies have revealed that a large percentage of wireless links are lossy and unreliable for data delivery in wireless sensor networks (WSNs). Such findings raise new challenges for the design of clustering algorithms in WSNs in terms of data reliability and energy efficiency. In this paper, we propose distributed clustering algorithms for WSNs by taking into account of the lossy nature of wireless links. We first formulate the one-hop clustering problem that maintains reliability as well as saves energy into an integer program and prove its NP-hardness. We then propose a metric-based distributed clustering algorithm to solve the problem. We adopt a metric called selection weight for each sensor node that can indicate both link qualities around the node and its capability of being a cluster head. We further extend the algorithm to multi-hop clustering to achieve better scalability. Extensive simulations have been conducted under a realistic link model and the results demonstrate that the proposed clustering algorithm can reduce the total energy consumption in the network and prolong network lifetime significantly compared to a typical distributed clustering algorithm, HEED, that does not consider lossy links.

In recent years, wireless mesh networks (WMNs) have been widely deployed to provide wireless access to the Internet. However, due to inter-link interference, the aggregated capacity of WMNs is limited, even with multiple channels. As a result, many links in WMNs are suppressed since interfering links cannot be active (i.e., transmitting packets) simultaneously. In this paper, we propose a joint design of channel assignment and space-division multiple access (SDMA) technique with the objective of maximizing the number of active links in WMNs. We assign different channels to transmission links based on their interference relationship to alleviate the interference. We also apply the SDMA technique to link scheduling, which enables two interfering links that share the same destination to communicate simultaneously on the same channel. By utilizing SDMA, more concurrent transmission links can be accommodated such that the network capacity can be greatly improved. We formulate this joint design into an optimization problem, prove its NP-hardness and then provide two heuristic algorithms to give practically good solutions to the problem. Our simulation results demonstrate that performance of the two heuristic algorithm is close to the optimal solution, and when 90% SDMA pairs are compatible, the proposed algorithms can increase the percentage of active links in a WMN by up to 40% as compared to non-SDMA schedules.

In this paper, we consider data gathering in wireless sensor networks (WSNs) by utilizing multiple mobile collectors and spatial-division multiple access (SDMA) technique. In particular, multiple mobile collectors, for convenience, called SenCars in this paper, are deployed in a WSN and work independently and simultaneously to collect data. The sensing field is divided into several non-overlapping regions, each having a SenCar. Each SenCar takes the responsibility of gathering data from sensors in the region while traversing their transmission ranges. Sensors directly send data to their associated SenCars without any relay in order to achieve uniform energy consumption. We also consider exploiting SDMA technique by equipping each SenCar with two antennas. With the support of SDMA, two distinct compatible sensors in the same region can successfully make concurrent data uploading to their associated SenCar. Intuitively, if each SenCar can always simultaneously communicate with two compatible sensors, the data uploading time in each region can be cut into half in the ideal case. We focus on the problem of minimizing the maximum data gathering time among different regions, which consists of two parts: the data uploading time of the sensors in this region and the moving time of the associated SenCar on a tour. We refer to this problem as data gathering with multiple mobile collectors and SDMA, or DG-MS for short, and formalize it into an integer linear program. We then propose a region-division and tour-planning algorithm to provide a practically good solution to the problem. Simulation results demonstrate that the proposed scheme significantly outperforms other non-SDMA or single mobile collector schemes by efficiently shortening and balancing the data gathering time among different regions.

There are increasing interest and big challenges in designing a scalable and robust multicast routing protocol in a mobile ad hoc network (MANET) due to the difficulty in group membership management, multicast packet forwarding, and the maintenance of multicast structure over the dynamic network topology for a large group size or network size. In this paper, we propose a novel Robust and Scalable Geographic Multicast Protocol (RSGM). Several virtual architectures are used in the protocol without need of maintaining state information for more robust and scalable membership management and packet forwarding in the presence of high network dynamics due to unstable wireless channels and node movements. Specifically, scalable and efficient group membership management is performed through a virtual-zone-based structure, and the location service for group members is integrated with the membership management. Both the control messages and data packets are forwarded along efficient tree-like paths, but there is no need to explicitly create and actively maintain a tree structure. The stateless virtual-tree-based structures significantly reduce the tree management overhead, support more efficient transmissions, and make the transmissions much more robust to dynamics. Geographic forwarding is used to achieve further scalability and robustness. To avoid periodic flooding of the source information throughout the network, an efficient source tracking mechanism is designed. Furthermore, we handle the empty-zone problem faced by most zone-based routing protocols. We have studied the protocol performance by performing both quantitative analysis and extensive simulations. Our results demonstrate that RSGM can scale to a large group size and a large network size, and can more efficiently support multiple multicast groups in the network. Compared to existing protocols ODMRP and SPBM, RSGM achieves a significantly higher delivery ratio under all circumstances, with different moving speeds, node densities, group sizes, number of groups, and network sizes. RSGM also has the minimum control overhead and joining delay.

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected by a regular topology, and unstructured peer-to-peer networks in which the topology is arbitrary. Structured peer-to-peer networks usually can provide efficient and accurate services but need to spend a lot of effort in maintaining the regular topology. On the other hand, unstructured peer-to-peer networks are extremely resilient to the frequent peer joining and leaving but this is usually achieved at the expense of efficiency. The objective of this work is to design a hybrid peer-to-peer system for distributed data sharing which combines the advantages of both types of peer-to-peer networks and minimizes their disadvantages. The proposed hybrid peer-to-peer system is composed of two parts: the first part is a structured core network which forms the backbone of the hybrid system; the second part is made of multiple unstructured peer-to-peer networks each of which is attached to a node in the core network. The core structured network can narrow down the data lookup within a certain unstructured network accurately, while the unstructured networks provide a low-cost mechanism for peers to join or leave the system freely. A data lookup operation first checks the local unstructured network, and then, the structured network. This two-tier hierarchy can decouple the flexibility of the system from the efficiency of the system. Our simulation results demonstrate that the hybrid peer-to-peer system can utilize both the efficiency of structured peer-to-peer network and the flexibility of the unstructured peer-to-peer network and achieve a good balance between the two types of networks.

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. A typical scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose an approach to transforming the linear coding problem into a graph theory problem. By utilizing hypergraphs, we model the linear codes by constructing a pseudodual graph of the multicast network. Then, a valid linear code is equivalent to a cover in the pseudodual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, we propose several preprocessing algorithms to further reduce the computation time required by the iterative refinements by reducing the graph size before transformation. An important contribution of this work is that the proposed approach can be readily extended to solve many minimal network coding problems. By assigning different weights to edges, minimal network coding problems are reduced to the shortest path problem in the pseudodual graph. Our simulation results show that the proposed preprocessing algorithms can reduce the computation time by about 40-50 percent in a medium size multicast network compared to the scheme without preprocessing algorithms, and the throughput of the system with network coding is 25 percent higher than that with the traditional approach of multiple multicast trees.

Optical networks with Wavelength Division Multiplexing (WDM), especially Optical Packet Switching (OPS) networks, have attracted much attention in recent years. However, OPS is still not yet ready for deployment, which is mainly because of its high packet loss ratio at the switching nodes. Since it is very difficult to reduce the loss ratio to an acceptable level by only using all-optical methods, in this paper, we propose a new type of optical switching scheme for OPS which combines optical switching with electronic buffering. In the proposed scheme, the arrived packets that do not cause contentions are switched to the output fibers directly; other packets are switched to shared receivers and converted to electronic signals and will be stored in the buffer until being sent out by shared transmitters. We focus on performance analysis of the switch, and with both analytical models and simulations, we show that to dramatically improve the performance of the switch, for example, reducing the packet loss ratio from 10-2to close to 10-6, very few receivers and transmitters are needed to be added to the switch. Therefore, we believe that the proposed switching scheme can greatly improve the practicability of OPS networks.

In this paper we propose a joint design of MIMO technique and network coding (MIMO-NC) and apply it to improve the performance of wireless networks. We consider a system in which the packet exchange among multiple wireless users is forwarded by a relay node. In order to enjoy the benefit of MIMO-NC, all the nodes in the network are mounted with two antennas and the relay node possess the coding capability. For the cross traffic flows among any four users, the relay node not only can receive packets simultaneously from two compatible users in the uplink (users-to-relay node), but also can mix up distinct packets for four destined users into two coded packets and concurrently send them out in the same downlink (relay node-to-users), so that the information content is significantly increased in each transmission. We formalize the problem of finding a schedule to forward the buffered data of all the users in minimum number of transmissions in such a system as a problem of finding a maximum matching in a graph. We also provide an analytical model on maximum throughput and optimal energy efficiency, which explicitly measures the performance gain of the MIMO-NC enhancement. Our analytical and simulation results demonstrate that system performance can be greatly improved by the efficient utilization of MIMO and network coding opportunities.

Recent study reveals that great benefit can be achieved for data gathering in wireless sensor networks by employing mobile collectors that gather the data via short-range communications. To pursue maximum energy saving at sensor nodes, intuitively, a mobile collector should traverse the transmission range of each sensor in the field such that the transmission of each packet can be constrained to a single hop. However, this approach may lead to significantly increased data collection latency due to the low moving velocity of the mobile collector. On the other hand, data collection latency can be effectively shortened by performing local aggregation via multi-hop transmissions and then uploading the packets from relay sensors to the mobile collector. However, local transmission hops should not be arbitrarily increased since it may incur too much energy consumption on packet relays, which would adversely affect the overall efficiency of mobile data collection. Based on these observations, in this paper, we study the tradeoff between energy saving and data collection latency in mobile data gathering by exploring a balance between the relay hop count of local data aggregation and the moving tour length of the mobile collector. We first propose a polling-based mobile collection approach and formulate it into an optimization problem, named bounded relay hop mobile data collection (BRH-MDC). Specifically, a subset of sensors will be selected as polling points that buffer locally aggregated data and upload the data to the mobile collector when it arrives. In the meanwhile, when sensors are affiliated with these polling points, it is guaranteed that any packet relay is bounded within a given number of hops. We then give two efficient algorithms to select polling points among sensors. The effectiveness of our approach is validated through extensive simulations.

In this paper, we propose a scheme to apply network coding to heterogeneous peer-to-peer media streaming systems. As most peers in a peer-to-peer media streaming system are individual computers connected to the Internet through access links with heterogeneous link capacities, it is desirable to design an adaptive scheme to make efficient use of the bandwidth of the access links. We propose an adaptive network coding scheme for heterogeneous peer-to-peer streaming systems. The media content is encoded into multiple stripes. The peers select one or more stripes to subscribe based on their own download bandwidths. For each stripe, a subgraph is constructed such that the coding probability is maximized. In addition, we propose an overlay topology construction algorithm which takes both upload bandwidth and download bandwidth into consideration. We compare our scheme with another recently proposed scheme called LION through simulations. Our simulation results show that the proposed scheme achieves higher satisfaction and better throughput than LION with or without churn.

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input contention is eliminated, and the scheduling process for buffered crossbar switches is greatly simplified. Moreover, since different input ports and output ports work independently, the switch can easily schedule and transmit variable length packets. Compared with fixed length packet scheduling, variable length packet scheduling has some unique advantages: higher throughput, shorter packet latency, and lower hardware cost. In this paper, we present a fast and practical scheduling scheme for buffered crossbar switches called Localized Independent Packet Scheduling (LIPS). With LIPS, an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers, i.e., the crosspoint buffers where the input port sends packets to or the output port retrieves packets from. The localization feature makes LIPS suitable for a distributed implementation and thus highly scalable. Since no comparison operation is required in LIPS, scheduling arbiters can be efficiently implemented using priority encoders, which can make arbitration decisions quickly in hardware. Another advantage of LIPS is that each crosspoint needs only L (the maximum packet length) buffer space, which minimizes the hardware cost of the switches. We theoretically analyze the performance of LIPS and, in particular, prove that LIPS achieves 100 percent throughput for any admissible traffic with speedup of two. We also discuss in detail the implementation architecture of LIPS and analyze the packet transmission timing in different scenarios. Finally, simulations are conducted to verify the analytical results and measure the performance of LIPS.

In this paper, we consider using simultaneous Multiple Packet Transmission (MPT) to improve the downlink performance of wireless networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum matching problem in a graph. Since maximum matching algorithms are relatively complex and may not meet the timing requirements of real-time applications, we give a fast approximation algorithm that is capable of finding a matching at least 3/4 of the size of a maximum matching in O(|E|) time, where |E| is the number of edges in the graph. We also give analytical bounds for maximum allowable arrival rate, which measures the speedup of the downlink after enhanced with MPT, and our results show that the maximum arrival rate increases significantly even with a very small compatibility probability. We also use an approximate analytical model and simulations to study the average packet delay, and our results show that packet delay can be greatly reduced even with a very small compatibility probability.

Network coding is a promising enhancement of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. Peer-to-peer networks are a perfect place to apply network coding due to two reasons: the topology of a peer-to-peer network is constructed arbitrarily, thus it is easy to tailor the topology to facilitate network coding; the nodes in a peer-to-peer network are end hosts which can perform more complex operations such as decoding and encoding than simply storing and forwarding messages. In this paper, we propose a scheme to apply network coding to peer-to-peer file sharing which employs a peer-to-peer network to distribute files resided in a web server or a file server. The scheme exploits a special type of network topology called combination network. It is proved that combination networks can achieve unbounded network coding gain measured by the ratio of network throughput with network coding to that without network coding. The scheme encodes a file into multiple messages and divides peers into multiple groups with each group responsible for relaying one of the messages. The encoding scheme is designed to satisfy the property that any subset of the messages can be used to decode the original file as long as the size of the subset is sufficiently large. To meet this requirement, we first define a deterministic linear network coding scheme which satisfies the desired property, then we connect peers in the same group to flood the corresponding message, and connect peers in different groups to distribute messages for decoding. Moreover, the scheme can be readily extended to support topology awareness to further improve system performance in terms of throughput, reliability and link stress. Our simulation results show that the new scheme can achieve 15%-20% higher throughput than Narada which does not employ network coding. In addition, it achieves good reliability and robustness to link failure or churn.

Recent years have witnessed a surge of interest in efficient data gathering schemes in wireless sensor networks (WSNs). In this paper, we address this important issue in WSNs by adopting mobility and space-division multiple access (SDMA) technique to optimize system performance. Specifically, a mobile data collector, for convenience, called SenCar in this paper, is deployed in a WSN. It works like a mobile base station and polls each sensor while traversing its transmission range. Each sensor directly sends data to the SenCar without any relay so that the lifetime of sensors can be prolonged. We also consider applying SDMA technique to data gathering by equipping the SenCar with two antennas. With SDMA, two distinct compatible sensors may successfully make concurrent data uploading to the SenCar. Intuitively, if the SenCar can always simultaneously communicate with two compatible sensors, data uploading time can be cut into half in the ideal case. We focus on the problem of minimizing the total time of a data gathering tour which consists of two parts: data uploading time and moving time. To better enjoy the benefit of SDMA, the SenCar may have to visit some specific locations where more sensors are compatible, which may adversely prolong the moving path. Hence, an optimum solution should be a tradeoff between the shortest moving path and full utilization of SDMA. We refer to this optimization problem as mobile data gathering problem with SDMA, or MDG-SDMA for short. We formalize the MDG-SDMA problem into an integer program (IP) and then propose three heuristic algorithms that provide practically good solutions to the problem. Our simulation results demonstrate that the proposed algorithms can greatly reduce the total data gathering time compared to the non-SDMA algorithm with only minimum overhead.

All-optical wavelength-division-multiplexing (WDM) interconnects are a promising candidate for future ultra highspeed interconnections due to the huge capacity of optics. Packet scheduling algorithms that can guarantee 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. However, although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, almost all of these algorithms depend on the virtual output queue (VOQ) technique which is currently difficult to implement in WDM optical interconnects due to lack of optical RAM; Second, a packet arriving at the input of a WDM interconnect now have more than one output wavelength channels to choose from due to wavelength conversion capability. The former motivates us to search for a new input buffering fabric that is more practical under the current optical technology and can achieve satisfactory performance, and the latter indicates that a new definition of "admissible traffic" may be needed for WDM optical interconnects. In this paper, we first introduce a new fiber- delay-line (FDL) based input buffering fabric that is able to provide flexible buffering delay in WDM optical interconnects. We then give a new definition of "admissible traffic" for a WDM optical interconnect, and propose the most- packet wavelength-fiber pair first (MPWFPF) scheduling algorithm for WDM interconnects using such buffering fabric. We theoretically prove that with the new buffering fabric, MPWFPF can deliver 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose a faster scheduling algorithm, WDM-iSLIP, that can efficiently determine an approximate optimal schedule with much lower time complexity. Extensive simulations have been conducted to verify the theoretical results, and test the performance of the proposed scheduling algorithms in input-buffered WDM interconnects with the new buffering fabric.

In this paper, we propose a new data gathering mechanism for large scale wireless sensor networks by introducing mobility into the network. A mobile data collector, or for convenience called M-collector in this paper, could be a mobile robot or a vehicle equipped with a powerful transceiver and battery, works like a mobile base station and gathers data while moving through the field. An M-collector starts the data gathering tour periodically from the static data sink, polls each sensor while traversing the transmission range of the sensor, then collects data directly from the sensor without relay (i.e., in a single hop), finally returns and uploads data to the data sink. Since data packets are gathered directly without relay and collision, the lifetime of sensors is expected to be prolonged, and sensors can be made very simple and inexpensive. We focus on the problem of minimizing the length of each data gathering tour and refer to this problem as the single-hop data gathering problem, or SHDGP for short. We first formalize the SHDGP problem into a mixed integer program and prove its NP-hardness. We then present a heuristic tour-planning algorithm for a single M-collector. For the applications with a strict distance/time constraint for each data gathering tour, we also utilize multiple M-collectors to traverse through several shorter sub-tours concurrently to satisfy the distance/time constraint. Our single-hop data gathering scheme will improve the scalability and solve intrinsic problems of large scale homogeneous networks, and can be used in both connected networks and disconnected networks. The simulation results demonstrate that the new data gathering algorithm can greatly reduce the moving distance of the collectors compared to the covering line approximation algorithm, and is close to the optimal algorithm in small networks. In addition, the proposed data gathering scheme can prolong the network lifetime significantly compared to a network which has only a static data collector, or a network in which the mobile collector can only move along straight lines.

Buffered crossbar switches are a special type of combined input-output queued switches with each crosspoint of the crossbar having small on-chip buffers. The introduction of crosspoint buffers greatly simplifies the scheduling process of buffered crossbar switches, and furthermore enables buffered crossbar switches with speedup of two to easily provide port based performance guarantees. However, recent research results have indicated that, in order to provide flow based performance guarantees, buffered crossbar switches have to either increase the speedup of the crossbar to three or greatly increase the total number of crosspoint buffers, both adding significant hardware complexity. In this paper, we present scheduling algorithms for buffered crossbar switches to achieve flow based performance guarantees with speedup of two and with only one or two buffers at each crosspoint. When there is no crosspoint blocking in a specific time slot, only the simple and distributed input scheduling and output scheduling are necessary. Otherwise, the special urgent matching is introduced to guarantee the on-time delivery of crosspoint blocked cells. With the proposed algorithms, buffered crossbar switches can provide flow based performance guarantees by emulating push-in-first-out output queued switches, and we use the counting method to formally prove the perfect emulation. For the special urgent matching, we present sequential and parallel matching algorithms. Both algorithms converge with N iterations in the worst case, and the latter needs less iterations in the average case. Finally, we discuss an alternative backup-buffer implementation scheme to the bypass path, and compare our algorithms with existing algorithms in the literature.

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer- to-peer networks in which peers are connected by a regular topology, and unstructured peer-to-peer networks in which the topology is arbitrary. Structured peer-to-peer networks usually can provide efficient and accurate services but need to spend a lot of efforts in maintaining the regular topology. On the other hand, unstructured peer-to-peer networks are extremely resilient to the frequent peer joining and leaving but this is usually achieved at the expense of efficiency. The objective of this work is to design a hybrid peer-to-peer system for distributed data sharing which combines the advantages of both types of peer-to-peer networks and minimizes their disadvantages. The proposed hybrid peer-to-peer system is composed of two parts: the first part is a structured core network which forms the backbone of the hybrid system; the second part is multiple unstructured peer- to-peer networks each of which is attached to a node in the core network. The core structured network can narrow down the data lookup within a certain unstructured network accurately, while the unstructured networks provide a low cost mechanism for peers to join or leave the system freely. A data lookup operation first checks the local unstructured network and then the structured network. This two-tier hierarchy can decouple the flexibility of the system from the efficiency of the system. Our simulation results demonstrate that the hybrid peer-to-peer system can utilize both the efficiency of structured peer-to-peer network and the flexibility of the unstructured peer-to-peer network and achieve a good balance between the two types of networks.

Network coding is a promising generalization of routing which allows a network node to generate output messages by encoding its received messages to reduce the bandwidth consumption in the network. An important application where network coding offers unique advantages is the multicast network where a source node generates messages and multiple receivers collect the messages. Previous network coding schemes primarily considered encoding the messages in a single multicast session. In this paper, we consider the linear inter-session network coding for multicast. The basic idea is to divide the sessions into different groups and construct a linear network coding scheme for each group. To maximize the performance, we introduce two metrics: overlap ratio and overlap width, to measure the benefit that a system can achieve by inter-session network coding. The overlap ratio mainly characterizes the network bandwidth while the overlap width characterizes the system throughput. Our simulation results show that the proposed inter-session network coding scheme can achieve about 30% higher throughput than intra-session network coding.

In this paper, we study two-layered heterogeneous sensor networks where two types of nodes are deployed: the basic sensor nodes and the cluster head nodes. The basic sensor nodes are simple and have limited power supplies, whereas the cluster head nodes are much more powerful and have many more power supplies, which organize sensors around them into clusters. Such two-layered heterogeneous sensor networks have better scalability and lower overall cost than homogeneous sensor networks. We propose using polling to collect data from sensors to the cluster head since polling can prolong network life by avoiding collisions and reducing the idle listening time of sensors. We focus on finding energy-efficient and collision-free polling schedules in a multihop cluster. To reduce energy consumption in idle listening, a schedule is optimal if it uses the minimum time. We show that the problem of finding an optimal schedule is NP-hard and then give a fast online algorithm to solve it approximately. We also consider dividing a cluster into sectors and using multiple nonoverlapping frequency channels to further reduce the idle listening time of sensors. We conducted simulations on the NS-2 simulator and the results show that our polling scheme can reduce the active time of sensors by a significant amount while sustaining 100 percent throughput.

In this paper, we present a new multicast architecture and the corresponding multicast routing protocol for providing efficient and flexible multicast services over the Internet. Traditional multicast protocols construct and update the multicast tree in a distributed manner, which may cause two problems: first, since each node has only local or partial information on the network topology and group membership, it is difficult to build an efficient multicast tree; second, due to lack of complete information, broadcast is often used for sending control packets and data packets, which consumes a great deal of network bandwidth. In the newly proposed multicast architecture, a few powerful routers, called m-routers, collect multicast-related information and process multicast requests based on the information collected. The m-routers handle most of multicast related tasks, while other routers in the network only need to perform minimum functions for routing. The m-routers are designed to be able to handle simultaneous many-to-many communications efficiently. The new multicast routing protocol, called the Service Centric Multicast Protocol (SCMP), builds a shared multicast tree rooted at the m-router for each group. The multicast tree is computed in the m-router by employing the Delay Constrained Dynamic Multicast (DCDM) algorithm which dynamically builds a delay constrained multicast tree and minimizes the tree cost as well. The physical construction of the multicast tree over the Internet is performed by a special type of self-routing packets in order to minimize the protocol overhead. Our simulation results on NS-2 demonstrate that the new SCMP protocol outperforms other existing protocols and is a promising alternative for providing efficient and flexible multicast services over the Internet.

In this paper, we present a novel contention-based medium access control (MAC) protocol, namely, the Channel Reservation MAC (CR-MAC) protocol. The CR-MAC protocol takes advantage of the overhearing feature of the shared wireless channel to exchange channel reservation information with little extra overhead. Each node can reserve the channel for the next packet waiting in the transmission queue during the current transmission. We theoretically prove that the CR-MAC protocol achieves much higher throughput than the IEEE 802.11 RTS/CTS mode under saturated traffic. The protocol also reduces packet collision, thereby saving the energy for retransmission. We evaluate the protocol by simulations under both saturated traffic and unsaturated traffic. Our simulation results not only validate the theoretical analysis on saturated throughput, but also reveal other good features of the protocol. For example, under saturated traffic, both the saturated throughput and fairness measures of the CR-MAC are very close to the theoretical upper bounds. Moreover, under unsaturated traffic, the protocol also achieves higher throughput and better fairness than IEEE 802.11 RTS/CTS.

All-optical packet switching is a promising candidate for future high-speed switching. However, due to the absence of optical Ran-dom Access Memory, the traditional Virtual Output Queue (VOQ) based input-queued switches are difficult to implement in optical domain. In this paper we consider output-buffered optical packet switches. We focus on packet scheduling in an output-buffered optical packet switch with limited-range wavelength conversion, aiming at maximizing throughput and minimizing average queuing delay simultaneously. We show that it can be converted to a minimum cost maximum network flow problem. To cope with the high complexity of general network flow algorithms, we further present a new algorithm that can determine an optimal scheduling in O (min {W2,BW}) time, where W is the number of wave-length channels in each fiber and B is the length of the output buffer. We also conduct simulations to test the performance of the proposed scheduling algorithm under different traffic models.

Opportunistic medium access (i.e., multiuser diversity) and MIMO techniques (i.e., multiple-antenna techniques) are two effective ways to achieve a substantial throughput gain in a multiuser wireless system. In this paper, we propose a medium access control (MAC) protocol with opportunistic medium access and multiuser MIMO techniques (MAC-OMA/MM) in Multi-channel Multi-radioWireless Local Area Networks (WLANs) to explore the utility of the joint design of these two techniques for the challenging MAC design. Specially, in addition to utilizing multiple channels simultaneously and multiple radio transceivers dynamically, multiuser spatial multiplexing and multiuser diversity are employed in each frequency channel to improve system performance. The key ideas of MAC-OMA/MM can be summarized as follows. By utilizing ATIM (Ad-hoc Traffic Indication Message) windows as in IEEE 802.11 power saving mechanism (PSM) under the distributed coordinate function (DCF) mode, user selection and channel negotiation are conducted between the AP and users via ATIM messages on a common channel. Multiuser diversity are employed to opportunistically schedule among multiple candidate users to optimize data transmission. During data exchange, on each frequency channel, the AP can transmit data to two distinct users simultaneously in the downlink with the help of multiuser spatial multiplexing, and two users can concurrently send data to the AP by uplinkdownlink duality in the uplink, which creates an extra dimension in spatial domain to further leverage the effect of multiuser diversity and multi-channel gains. Another contribution of this paper is to provide an analytical model to characterize the impact of our protocol on the system throughput and energy efficiency performance. Extensive simulations have been conducted and the results demonstrate that our protocol outperforms existing multi-channel MAC protocols with only minimal additional overhead and minor enhancements to the IEEE 802.11 PSM.

Wireless mesh networks recently emerge as a flexible, low- cost and multi-functional networking platform with wired infrastructure connected to the Internet. A critical issue in mesh networks is to maintain long time network coverage. Recent study reveals that batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. To take advantage of the battery recovery property, in this paper we propose a cross-layer client driven battery aware (CDBA) scheme to efficiently schedule mesh network coverage. The key idea of CDBA coverage algorithm is to let neighboring mesh routers collaboratively adjust their transceiver radii driven by mesh clients. In this way routers are able to recover their over-discharged battery power dynamically. This algorithm is a distributed algorithm with O(n) time complexity where n is the maximum number of neighbors of a router in the network. To further jointly improve system performance among layers, we design the CDBA MAC algorithm to provide a seamless and fast service for handoff among mesh routers. We conduct simulations to evaluate the performance of the proposed CDBA scheme. The results show that network lifetime and data throughput can be improved by up to 27.27% and 30.54% in mesh networks, respectively.

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. An important scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose a method to transform the linear coding problem to a graph theory problem. With the help of hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. A valid linear code is equal to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, this method can be readily applied to many minimum network coding problems as well.

Recent years have witnessed a surge of the interest in efficient data gathering schemes in wireless sensor networks (WSNs). In this paper, we address this essential issue in WSNs by introducing the mobility and MIMO capability to the data sink in order to optimize the system performance. Specifically, the mobile sink moves along a pre-determined path and collects data packets at some polling stations. With a proper planning on the moving path, we can reduce the data relaying to the minimum, which effectively improves the energy efficiency and also circumvents the non-uniformity of energy consumption among sensor nodes. We also apply MIMO technique to the mobile sink by mounting multiple antennas on it, which provides a radical way to improve the system capacity. With the support of MIMO technique, the mobile sink can simultaneously collect data from multiple compatible sensors. Finally, we theoretically analyze the performance of mobile data gathering in a WSN enhanced by MIMO support, and also investigate its efficiency by simulation experiments. The results demonstrate that the proposed mechanism can greatly improve the system throughput and energy efficiency with minimum additional overhead.

With the rapid development of broadband applications, the capability of networks to provide quality of service (QoS) has become an important issue. Fair scheduling algorithms are a common approach for switches and routers to support QoS. All fair scheduling algorithms are running based on a bandwidth allocation scheme. The scheme should be feasible in order to be applied in practice, and should be efficient to fully utilize available bandwidth and allocate bandwidth in a fair manner. However, since a single input port or output port of a switch has only the bandwidth information of its local flows (i.e., the flows traversing itself), it is difficult to obtain a globally feasible and efficient bandwidth allocation scheme. In this paper, we show how to fairly allocate bandwidth in packet switches based on the max-min fairness principle. We first formulate the problem, and give the definitions of feasibility and max-min fairness for bandwidth allocation in packet switches. As the first step to solve the problem, we consider the simpler unicast scenarios, and present the max-min fair bandwidth allocation algorithm for unicast traffic. We then extend the analysis to the more general multicast scenarios, and present the max-min fair bandwidth allocation algorithm for multicast traffic. We prove that both algorithms achieve max-min fairness, and analyze their complexity. The proposed algorithms are universally applicable to any type of switches and scheduling algorithms.

In this paper, a contention-free polling protocol and a load-balancing algorithm, for two-layered heterogeneous sensor networks were proposed, based on the energy consumption features of the physical layer, MAC layer and network layer. By introducing some powerful nodes, sensors can be organized into clusters. Each powerful node works as a local data sink and gathers data from sensors in the cluster. The power consumption model of IEEE 802.15.4-based transceivers was first analyzed. Based on physical layer features of such low-power, low-rate transceivers, a contention-free polling protocol for inner-cluster data gathering was designed, so that packet collision can be avoided. By deactivating the transceivers of sensors which do not need to transmit or receive packets, energy consumption on idle listening can be saved. A load-balancing algorithm at network layer was also proposed to maximize the network lifetime by taking into consideration of power consumption features at the physical and MAC layers. Simulation results show that the proposed scheme can achieve more than one order of magnitude improvement compared to the FLOW-CSMA combination and reduce the duration of sensor duty cycle by at least 50% under various offered traffic loads.

Wireless MIMO (multiple input multiple output) mesh networks recently emerge as a flexible, low-cost and multi-functional networking platform with wired infrastructure connected to the Internet. Mesh routers are equipped with multiple radio transceivers that can work simultaneously. This MIMO feature greatly improves data throughput of mesh routers. A critical issue in MIMO mesh networks is to maintain network coverage and routing for a long lifetime with high energy efficiency. As more and more outdoor applications require long-lasting, high energy efficient and continuously-working mesh networks with battery-powered mesh routers, it is important to maximize the performance of mesh networks from a battery aware point of view. Recent study in battery technology reveals that discharging of a battery is nonlinear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. To take advantage of the battery recovery property, in this paper we first study the relationships between various MIMO transceiver parameters and their battery parameters to give an energy model for MIMO transceivers. We then present a multiple current battery model that can accurately describe battery behaviors with multiple current inputs. Based on these two models, we propose a battery aware MIMO mesh network power scheduling scheme. The scheme consists of two algorithms: the coverage algorithm and the backhaul routing algorithm. The key idea of the coverage algorithm is to let neighboring mesh routers collaboratively adjust their transceiver radii to dynamically recover their over-discharged battery power. The backhaul routing algorithm adopts the multiple current battery model to calculate battery discharging loss at routers for scheduling mesh backhaul routing. We conducted simulations to evaluate the performance of the proposed scheme. The results show that network lifetime can be improved by up to 10.3% and 16.1% for homogeneous and heterogeneous mesh networks, respectively.

The combination of multiple input multiple output (MIMO) and orthogonal frequency division multiplexing (OFDM) is regarded as one of the most promising solutions for improving spectrum efficiency and enhancing data rate for next-generation wireless communication systems. However, the applications of these advanced physical-layer techniques also impose great challenges on upper layer protocol designs. In this paper, a cross-layer approach was proposed to exploring the utility of the joint design of multiuser MIMO-OFDM technique and power-saving MAC protocol. Specifically, a novel MIMO-OFDM transceiver architecture and an improved power-saving MAC protocol (namely, PSM-MIMO/OFDM) are proposed. In the proposed downlink transceiver architecture, by processing the data according to the channel state, the access point (AP) makes the data for one user appear as zero at the other user on each subcarrier such that it can send distinct packets to two users simultaneously. In the dual uplink, two users can concurrently transmit data to the AP without co-channel interference by uplink-downlink duality. The key ideas of PSM-MIMO/OFDM can be summarized as follows. A similar timing structure was employed to IEEE 802.11 power-saving mechanism (PSM). By utilizing ATIM (ad-hoc traffic indication message) window, negotiations are conducted between the AP and multiple candidate users via ATIM messages to achieve multiuser diversity gains. At the end of ATIM window, the AP sends an additional beacon to indicate the estimated time duration for data exchange with the measurement result of the number of active links which have been successfully negotiated during ATIM window. The length of a beacon interval is adjustable to satisfy the requirements of active links to the maximum extent. During the data exchange, the AP always communicates with two compatible users simultaneously both in the downlink and uplink, which effectively creates extra dimensions in the spatial domain. Extensive simulations have been conducted and the results demonstrate that the new protocol significantly outperforms other power-saving MAC protocols with only minimum additional overhead and minor modifications to the IEEE 802.11 PSM.

In this paper, we present a novel sensor deployment algorithm, called the adaptive triangular deployment (ATRI) algorithm, for large-scale unattended mobile sensor networks. The ATRI algorithm aims at maximizing coverage area and minimizing coverage gaps and overlaps by adjusting the deployment layout of nodes close to equilateral triangulation, which is proven to be the optimal layout to provide the maximum no-gap coverage. The algorithm only needs the location information of nearby nodes, thereby avoiding communication cost for exchanging global information. By dividing the transmission range into six sectors, each node adjusts the relative distance to its one-hop neighbors in each sector separately. The distance threshold strategy and the movement state diagram strategy are adopted to avoid the oscillation of nodes. The simulation results show that the ATRI algorithm achieves a much larger coverage area and smaller average moving distance of nodes than existing algorithms. We also show that the ATRI algorithm is applicable to practical environments and tasks such as working in both bounded and unbounded areas and avoiding irregularly shaped obstacles. In addition, the density of nodes can be adjusted adaptively to different requirements of tasks.

Image-data transmission from one site to another through public network is usually characterized in term of privacy, authenticity, and integrity. In this paper, we first describe a general scenario about how image is delivered from one site to another through a wide-area network (WAN) with security features of data privacy, integrity, and authenticity. Second, we give the common implementation method of the digital imaging and communication in medicine (DICOM) image communication software library with IPv6/IPv4 for high-speed broadband Internet by using open-source software. Third, we discuss two major security-transmission methods, the IP security (IPSec) and the secure-socket layer (SSL) or transport-layer security (TLS), being used currently in medical-image-data communication with privacy support. Fourth, we describe a test schema of multiple-modality DICOM-image communications through TCP/IPv4 and TCP/IPv6 with different security methods, different security algorithms, and operating systems, and evaluate the test results. We found that there are tradeoff factors between choosing the IPsec and the SSL/TLS-based security implementation of IPv6/IPv4 protocols. If the WAN networks only use IPv6 such as in high-speed broadband Internet, the choice is IPsec-based security. If the networks are IPv4 or the combination of IPv6 and IPv4, it is better to use SSL/TLS security. The Linux platform has more security algorithms implemented than the Windows (XP) platform, and can achieve better performance in most experiments of IPv6 and IPv4-based DICOM-image communications. In teleradiology or enterprise-PACS applications, the Linux operating system may be the better choice as peer security gateways for both the IPsec and the SSL/TLS-based secure DICOM communications cross public networks.

In this paper, we propose a new data gathering mechanism for large-scale multihop sensor networks. A mobile data observer, called SenCar, which could be a mobile robot or a vehicle equipped with a powerful transceiver and battery, works like a mobile base station in the network. SenCar starts the data gathering tour periodically from the static data processing center, traverses the entire sensor network, gathers the data from sensors while moving, returns to the starting point, and, finally, uploads data to the data processing center. Unlike SenCar, sensors in the network are static and can be made very simple and inexpensive. They upload sensed data to SenCar when SenCar moves close to them. Since sensors can only communicate with others within a very limited range, packets from some sensors may need multihop relays to reach SenCar. We first show that the moving path of SenCar can greatly affect network lifetime. We then present heuristic algorithms for planning the moving path/circle of SenCar and balancing traffic load in the network. We show that, by driving SenCar along a better path and balancing the traffic load from sensors to SenCar, network lifetime can be prolonged significantly. Our moving planning algorithm can be used in both connected networks and disconnected networks. In addition, SenCar can avoid obstacles while moving. Our simulation results demonstrate that the proposed data gathering mechanism can prolong network lifetime significantly compared to a network that has only a static observer or a network in which the mobile observer can only move along straight lines.

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input contention is eliminated, and the scheduling process for buffered crossbar switches is greatly simplified. Moreover, crosspoint buffers enable the switch to work in an asynchronous mode and easily schedule and transmit variable length packets. Compared with fixed length packet scheduling or cell scheduling, variable length packet scheduling, or packet scheduling for short, has some unique advantages: higher throughput, shorter packet latency and lower hardware cost. In this paper, we present a fast and practical scheduling scheme for buffered crossbar switches called Localized Asynchronous Packet Scheduling (LAPS). With LAPS, an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers, i.e., the crosspoint buffers where the input port sends packets to or the output port retrieves packets from. The localization property makes LAPS suitable for a distributed implementation and thus highly scalable. Since no comparison operation is required in LAPS, scheduling arbiters can be efficiently implemented using priority encoders, which can make arbitration decisions quickly in hardware. Another advantage of LAPS is that each crosspoint needs only L (the maximum packet length) buffer space, which minimizes the hardware cost of the switches. We also theoretically analyze the performance of LAPS, and in particular we prove that LAPS achieves 100% throughput for any admissible traffic with speedup of two. Finally, simulations are conducted to verify the analytical results and measure the performance of LAPS.

Reliable multicast is critical to multicast based applications as it provides reliability over the unreliable network. Although the primary function of reliable multicast is loss recovery and flow control which are similar to that of reliable unicast, the inherent property of multicast that multiple receivers coexist in one multicast session imposes new challenges such as acknowledge implosion and poor scalability. Among existing reliable multicast protocols, tree based reliable multicast protocols can achieve the reliability in a scalable fashion. They group the receivers into a hierarchy called the ACK tree and the ACK/NACK messages and retransmitted packets are transmitted between adjacent levels. Since current tree based reliable multicast protocols construct the ACK tree based on the multicast tree which is constructed by the multicast routing protocol, the protocol performance greatly depends on the multicast tree. In this paper, we propose a peer-to-peer (P2P) tree based reliable multicast protocol which constructs the ACK tree in a flexible way as the multicast tree is constructed in a P2P system. In our protocol, any two receivers can be adjacent nodes in the ACK tree. The ACK tree construction process is based on a heuristic function which is designed to minimize the retransmission delay. The child node sends ACK/NACK to the parent node and receives retransmitted packets from the parent node. Our protocol uses window based flow control. The window in the parent node will not advance unless the parent node receives all the ACKs from its child nodes. We conducted extensive simulations to evaluate the protocol. The simulation results show that our protocol achieves good scalability with low retransmission delay and high throughput.

In a multiuser wireless system, multiuser diversity for opportunistic scheduling has been extensively studied for high-rate data transmission. In this paper, we propose a novel MAC protocol named medium access diversity with uplink-downlink duality and transmit beamforming (MAD-UDD/TB). In addition to aggressively utilizing multiuser gains, it takes advantage of uplink-downlink duality and transmit beamforming, which are the transmitting and receiving strategies used in a multiple antenna environment for simultaneous packet transmissions to multiple distinct users. These techniques effectively leverage the effect of multiuser diversity and greatly improve network throughput by taking into account the opportunistic scheduling among multiple users to prioritize data transmissions. Extensive simulation results show that the proposed protocol achieves much better performance than other medium access diversity and auto rate schemes with minimal additional overhead.

In wireless environments, the inherent time-varying characteristics of the channel pose great challenges on medium access control design. In recent years, multiuser diversity and opportunistic medium access control schemes have been proposed to deal with the channel variation in order to efficiently improve the network throughput. In this paper, we propose a novel MAC protocol called Contention-Based Prioritized Opportunistic (CBPO) Medium Access Control Protocol. This protocol takes advantage of multiuser diversity, rate adaptation, which utilizes the multi-rate capability offered by IEEE 802.11, and black-burst (BB) contention to access the shared medium in a distributed manner. In particular, rather than simply measuring the channel condition for a node pair in communications each time, with the help of multicast RTS, the candidate users with qualified channel condition are selected and prioritized. Then the qualified receivers contend to send back prioritized clear-to-send message (CTS) with BB, which is a pulse of energy, the duration of which is proportional to the CTS priority. The user with the best channel quality is always selected to send back CTS and receive packets from the sender. Extensive simulation results show that our protocol achieves much better performance than IEEE 802.11 and other auto rate schemes with minimal additional overhead.

In this paper, we present a new multicast architecture and the associated multicast routing protocol for providing efficient and flexible multicast services over the Internet. Traditional multicast architectures construct and update the multicast tree in a distributed manner, which causes two problems: first, since each node has only local or partial information on the network topology and group membership, it is difficult to build an efficient multicast tree; second, due to lack of the complete information, broadcast is often used when transmitting control packets or data packets, which consumes a great deal of network bandwidth. In the newly proposed multicast architecture, a few powerful routers, called m-routers, collect multicast-related information and process multicast requests based on the information collected, m-routers handle most of multicast related tasks, while other routers only need to perform minimum functions for routing, m-routers are designed to be able to handle simultaneous many-to-many communications efficiently. The new multicast routing protocol, called service centric multicast protocol (SCMP), builds a dynamic shared multicast tree rooted at the m-router for each group. The multicast tree can satisfy the QoS constraint on maximum end-to-end delay and minimize tree cost as well. The tree construction is performed by a special type of self-routing packets to minimize protocol overhead. Our simulation results on NS-2 demonstrate that the new SCMP protocol outperforms other existing protocols and is a promising alternative for providing efficient and flexible multicast services over the Internet

Wireless mesh networks emerge as a flexible, low-cost and multipurpose networking platform with wired infrastructure connected to the Internet. A critical issue in mesh networks is to maintain network activities for a long lifetime with high energy efficiency. As more and more outdoor applications require long-lasting, high energy efficient and continuously-working mesh networks with battery-powered mesh routers, it is important to optimize the performance of mesh networks from a battery-aware point of view. Study in battery technology reveals that discharging of a battery is nonlinear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. Intuitively, to optimize network performance, a mesh router should recover its battery periodically to prolong the lifetime. In this paper, we introduce a mathematical model on battery discharging duration and lifetime for wireless mesh networks. We also present a battery lifetime optimization scheduling algorithm (BLOS) to maximize the lifetime of battery-powered mesh routers. Based on the BLOS algorithm, we further consider the problem of using battery powered routers to monitor or cover a few hot spots in the network. We refer to this problem as the spot covering under BLOS policy problem (SCBP). We prove that the SCBP problem is NP-hard and give an approximation algorithm called the spanning tree scheduling (STS) to dynamically schedule mesh routers. The key idea of the STS algorithm is to construct a spanning tree according to the BLOS policy in the mesh network. The time complexity of the STS algorithm is O(r) for a network with r mesh routers. Our simulation results show that the STS algorithm can greatly improve the lifetime, data throughput and power consumption efficiency of a wireless mesh network.

In this paper we consider using simultaneous multiple packet transmission (MPT) to improve the downlink performance of wireless networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum matching problem in a graph. Since maximum matching algorithms are relatively complex and may not meet the timing requirements of real time applications, we give a fast approximation algorithm that is capable of finding a matching at least 3/4 of the size of a maximum matching in O(|E|) time where |E| is the number of edges in the graph. We also give analytical bounds for maximum allowable arrival rate which measures the speedup of the downlink after enhanced with MPT and our results show that the maximum arrival rate increases significantly even with a very small compatibility probability. We also use an approximate analytical model and simulations to study the average packet delay and our results show that packet delay can be greatly reduced even with a very small compatibility probability.

In this paper we study Optical Burst Switching (OBS) networks. Since OBS still suffers high loss ratio due to the lack of buffer at the OBS core routers, we study methods to reduce the loss without using optical buffers. We consider time-slotted OBS called Slotted OBS (SOBS), where routers are synchronized and only send fixed length bursts at the beginning of time slots. Our simulation results show that SOBS reduces the packet loss probability significantly. Moreover, we show that SOBS can be implemented with little or no additional cost and has other advantages such as the better supporting of Quality of Service (QoS).

In this paper, we consider the problem of positioning mobile cluster heads and balancing traffic load in a hybrid sensor network, which consists of two types of nodes: basic static sensor nodes and mobile cluster heads. In such a network, sensor nodes are organized into clusters and form the lower layer of the network. At the higher layer, cluster heads collect sensing data from sensors and forward data to outside observers. Such two-layer hybrid networks are more scalable and energy-efficient than homogeneous sensor networks. We show that the locations of cluster head-s can affect network lifetime significantly. The problem of maximizing network lifetime through dynamically positioning cluster heads in the network (referred to as the CHL problem in this paper) turns out to be NP-hard. We present a heuristic algorithm for positioning cluster heads and balancing traffic load in the network. We show that by moving the cluster head to a better location, the traffic load can be balanced and network lifetime can be prolonged. We conducted simulations on the NS-2 simulator, and the result-s show that our clustering algorithm can increase network lifetime by up to 35% after only three rounds of adjustments, compared to the optimal lifetime of the initial network layout.

All optical networking is a promising candidate for supporting high-speed communications because of the huge bandwidth of optics. In this paper, we study optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability. We formalize the problem of maximizing network throughput and minimizing total delay as a problem of finding an optimal matching in a weighted bipartite graph. We then give a simple algorithm, called the Scan and Swap Algorithm, that finds the optimal matching in O(kB) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to directly adopting other existing algorithms that need at least O(k/sup 2/N/sup 2/ + k/sup 2/BN) time, where N is the number of input fibers.

In this paper, we give a new switching fabric design for the recirculating buffer in optical packet switching networks. We note that since a packet to be buffered can be routed to any delay lines, the switching fabric connecting packets to the delay lines can be simplified. We give a design based on the arrayed waveguide grating router, and give a simple linear time-control algorithm for assigning buffer locations to the packets. To the best of our knowledge, this is the first switching fabric specifically designed for recirculating buffers which takes advantage of the fact that packets can be routed to any delay lines.

All optical communication is attracting more and more attention because of the huge bandwidth of optics. In this paper, we study the performance of bufferless optical wavelength-division multiplexing (WDM) packet switching networks with limited-range wavelength conversion capabilities. We first introduce an optimal scheduling algorithm that maximizes the throughput of the switch. We then derive an analytical model to evaluate the performance of the switch in terms of packet-loss probability. Our model is the first accurate analytical model for a bufferless WDM packet switch with variable conversion distances, and can be used to quantitatively determine the maximum load for a given conversion distance or the minimum conversion distance for a given traffic load. We also conducted simulations to validate the analytical model. Both the analytical and simulation results reveal that limited-range wavelength conversion can achieve almost the same performance as full-range wavelength conversion.

All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk/sup 2/) time, compared to O((N+B)/sup 3/k/sup 3/) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints.

In this paper, we present a novel contention-based medium access control (MAC) protocol, namely, the channel reservation MAC (CR-MAC) protocol. The CR-MAC protocol takes advantage of the overhearing feature of the shared wireless channel to exchange the channel reservation information with little extra overhead. Each node can reserve the channel for the next packet waiting in the transmission queue during the current transmission. We theoretically prove that the CR-MAC protocol achieves much higher throughput than the IEEE 802.11 RTS/CTS mode under saturated traffic. The protocol also reduces the packet collision, thereby saving the energy for retransmission as well. We also evaluate the protocol by simulations under both saturated traffic and unsaturated traffic. Our simulation results not only validate the theoretical analyses on saturated throughput, but also reveal some other good features of the protocol. For example, under saturated traffic, both the saturated throughput and fairness measures of the CR-MAC are very close to the theoretical upper bounds. Moreover, under unsaturated traffic, the protocol also achieves higher throughput and better fairness than IEEE 802.11 RTS/CTS.

Recent technological advances have made it possible to support long lifetime and large volume streaming data transmissions in sensor networks. A major challenge is to maximize the lifetime of battery-powered sensors to support such transmissions. Battery, as the power provider of the sensors, therefore emerges as the key factor for achieving high performance in such applications. Recent study in battery technology reveals that the behavior of battery discharging is more complex than we used to think. Battery powered sensors might waste a huge amount of energy if we do not carefully schedule and budget their discharging. In this paper we study the effect of battery behavior on routing for streaming data transmissions in wireless sensor networks. We first give an on-line computable energy model to mathematically model battery discharge behavior. We show that the model can capture and describe battery behavior accurately at low computational complexity and thus is suitable for on-line battery capacity computation. Based on this battery model we then present a battery-aware routing (BAR) protocol to schedule the routing in wireless sensor networks. The routing protocol is sensitive to the battery status of routing nodes and avoids energy loss. We use the battery data from actual sensors to evaluate the performance of our protocol. The results show that the battery-aware protocol proposed in this paper performs well and can save a significant amount of energy compared to existing routing protocols for streaming data transmissions. The network lifetime is also prolonged with maximum data throughput. As far as we know; this is the first work considering battery-awareness with an accurate analytical on-line computable battery model in sensor network routing. We believe our battery model can be used to explore other energy efficient schemes for wireless networks as well.

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed, they usually consider only short delay and high throughput but not bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the credit based multicast fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit/balance based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, CMF supports multicast scheduling by allowing a multicast packet to send transmission requests to multiple output ports simultaneously. As a result, a multicast packet has more chances to be delivered to all its destinations in the same time slot, and thus shortens its multicast latency. Extensive simulations are conducted to compare the performance of CMF with other existing scheduling algorithms, and the results demonstrate that CMF achieves the two design goals: short multicast latency and fair bandwidth allocation.

In this paper we propose a multi-channel polling algorithm in multi-hop clusters of hybrid sensor networks. The hybrid sensor network consists of two types of nodes: basic sensor nodes and cluster head nodes. Basic sensor nodes have limited communication capacity and mainly focus on sensing the environment, while cluster head nodes are equipped with more powerful transceivers but simpler sensing modules. The cluster head node organizes basic sensor nodes around it into a cluster, and collects sensing data from sensors and forwards data to the outsider observer. This type of network has better energy-efficiency since traffic within cluster is scheduled by cluster head and packet collisions can be avoided. In addition, idle listening time can be shortened by turning off the transceivers of sensor nodes after data has been forwarded to cluster head. We focus on finding energy efficient and collision-free polling schedules in the multi-hop cluster with multiple frequency channels. Due to its energy efficiency and scalability, the proposed algorithm is very suitable for applications such as large scale environment monitoring. We also implement the proposed algorithm on NS-2. Simulation results show that multi-channel polling algorithm shortens the active time of sensor nodes by a significant amount compared to single channel polling. In the case that the total frequency bandwidth allocated to the cluster is fixed, the optimal number of channels can be obtained.

Presents the welcome message from the conference proceedings.

Multicast is an efficient way for group communication over the Internet. The performance of multicast relies greatly on the multicast tree constructed among the group members. Constructing a multicast tree spanning a set of group members with minimum cost is called Steiner tree problem which is a well-known NP-hard problem. Existing heuristic algorithms can build such a Steiner tree statically when the group members are known in advance. However, in many multicast tree dynamically. In addition, QoS is becoming a more important issue in multicast applications, and many applications, pose a tight bound on end-to-end delay. In this paper, we design a heuristic algorithm which can construct a delay constrained minimum cost multicast tree dynamically. Our algorithm can add or remove a group number without rerouting the path between the source and other group members. The algorithm not only avoids packet loss but also saves network bandwidth. Our algorithm guarantees that the end-to-end delay between the source and any group member is bounded with a threshold. Simulation results show that the algorithm achieves a good balance between the cost of a multicast tree and the time of the construction.

In this paper, we present a new position-based routing algorithm for mobile ad hoc networks. The proposed algorithm minimizes the effect of inaccurate location information on routing, which is caused by periodical updates of the node location information in the network. The algorithm achieves low communication complexity of O(/spl radic/n), compared to other existing position-based algorithms with O(n) complexity, where n is the number of nodes in the network. In addition, unlike some existing routing algorithms, the new algorithm is insensitive to the mobility of mobile nodes and consistently performs well for various mobilities.

A critical issue in wireless sensor networks is to construct energy efficient virtual backbones for routing, broadcasting and data propagating. The minimum connected dominating set (MCDS) has been proposed as a backbone to reduce power dissipation and prolong network lifetime. However, we find that an MCDS cannot guarantee maximum network lifetime as it does not consider the battery discharging behavior. Recent study in battery technology reveals that the discharging of a battery is not linear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. In order to optimize network performance and construct an energy efficient virtual backbone in sensor networks, battery-awareness should be considered. In this paper we first study the mathematical battery discharging model and provide a simplified battery model suitable for implementation in sensor networks. We then introduce the concept of battery-aware connected dominating set (BACDS) and show that in general the BACDS can achieve longer lifetime than the MCDS. Then we show that finding a minimum BACDS (MBACDS) is NP-hard and give a distributed approximation algorithm to construct the BACDS. The resulting BACDS constructed by our algorithm is at most (8+/spl Delta/)opt size where /spl Delta/ is the maximum node degree and opt is the size of an optimal BACDS. The time and message complexities of the algorithm are O(n) and O(n(/spl radic/n+logn+/spl Delta/)), respectively, where n is the number of nodes in the network. The simulation results show that the BACDS constructed by our algorithm can save a significant amount of energy and achieve up to 30% longer network lifetime than the MCDS. To the best of our knowledge, this is the first work considering battery-awareness in the construction of connected dominating sets.

We study the problem of determining the minimum number of limited range wavelength converters needed to construct strictly, wide-sense, and rearrangeably nonblocking optical cross-connects for both unicast and multicast traffic patterns. We give the exact formula to compute this number for rearrangeably and wide-sense nonblocking cross-connects under both the unicast and multicast cases. We also give optimal cross-connect constructions with respect to the number of limited-range wavelength converters.

Switches with shared buffer have lower packet loss probabilities than other types of switches when the sizes of the buffers are the same. In the past, the performance analysis for electronic shared buffer switches has been carried out extensively. However, due to the strong dependencies of the output queues in the buffer, it is very difficult to find a good analytical model. Existing models are either accurate but have exponential complexities or not very accurate. In this paper, we propose a novel analytical model called the aggregation model for switches with shared buffer. This model can be used for analyzing both electronic and optical switches, and has perfect accuracies under all tested conditions and has polynomial time complexity. It is based on the idea of induction: first find the behavior of 2 queues, then aggregate them into one block; then find the behavior of 3 queues while regarding 2 of the queues as one block, then aggregate the 3 queues into one block; then aggregate 4 queues and so on. When a sufficient number of queues have been aggregated, the behavior of the entire switch is found. We believe that the new model represents the best analytical model for shared buffer switches so far.

Many networking/computing applications require high speed switching for multicast traffic at the switch/router level to save network bandwidth. However, existing queuing-based packet switches and scheduling algorithms cannot perform well under multicast traffic. While the speedup requirement makes the output queued switch difficult to scale, the single input queued switch suffers from head of line (HOL) blocking, which severely limits the network throughput. An efficient yet simple buffering strategy to remove the HOL blocking is to use the virtual output queued (VOQ) switch structure, which has been shown to perform well under unicast traffic. However, the traditional VOQ switch is impractical for multicast traffic because a VOQ switch for multicast traffic has to maintain an exponential number of queues in each input port (i.e., 2/sup N/-1 queues for a switch with N output ports). In this paper, we give a novel queue structure for the input buffers of a multicast VOQ switch by separately storing the address information and data information of a packet so that an input port only needs to manage a linear number (N) of queues. In conjunction with the multicast VOQ switch, we present a first-in-first-out based multicast scheduling algorithm, FIFO multicast scheduling (FIFOMS), and conduct extensive simulations to compare FIFOMS with other popular scheduling algorithms. Our results fully demonstrate the superiority of FIFOMS in both multicast latency and queue space requirement.

In this paper, we propose a new design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N/spl times/N multicast network, its hardware cost, in terms of the number of crosspoints, is about 2(3+2/spl radic/2)N/sup 3/2/=11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(N/sup 3/2/(logN/loglogN)) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sublinear time complexity, and does not require multicast capability for the switch modules in the input stage.

Multicast involves transmitting information from a single source to multiple destinations, and is an important operation in high-performance networks. A k-fold multicast network was recently proposed as a cost-effective solution to providing better quality-of-service functions in supporting real-world multicast applications. To give a quantitative basis for network designers to determine the suitable value of system parameter k under different traffic loads, in this paper, we propose an analytical model for the performance of k-fold multicast networks under Poisson traffic. We first give the stationary distribution of network states, and then derive the throughput and blocking probability of the network. We also conduct extensive simulations to validate the analytical model, and the results show that the analytical model is very accurate under the assumptions made. The analytical and simulation results reveal that by increasing the fold of the network, network throughput increases very fast when the fanouts of multicast connections are relatively small, compared with the network size.

Optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/communication applications, such as data browsing in the World Wide Web, multimedia conferencing, e-commerce, and video-on-demand services. As optics becomes a major networking media in all communications needs, optical interconnects will inevitably play an important role in interconnecting processors in parallel and distributed computing systems. We consider a cost-effective design of WDM optical interconnects for current and future generation parallel and distributed computing and communication systems. We first categorize WDM optical interconnects into two different connection models based on their target applications: the wavelength-based model and the fiber-link-based model. Most of existing WDM optical interconnects belong to the first category. We then present a minimum cost design for WDM optical interconnects under wavelength-based model by using sparse crossbar switches instead of full crossbar switches in combination with wavelength converters. For applications that use the fiber-link-based model, we show that network cost can be significantly reduced, and present such a minimum cost design for WDM optical interconnects under this model. Finally, we generalize the idea used in the design for the fiber-link-based model to WDM optical interconnects under the wavelength-based model, and obtain another new design that can trade off switch cost with wavelength converter cost in this type of WDM optical interconnect. The results in this paper are applicable to any emerging optical switching technologies, such as SOA-based and MEMS-based technologies.

Permutation is a frequently-used communication pattern in parallel and distributed computing systems and telecommunication networks. Node-disjoint routing has important applications in guided wave optical interconnects where the optical "crosstalk" between messages passing the same switch should be avoided. In this paper, we consider routing arbitrary permutations on an optical baseline network (or reverse baseline network) with node-disjoint paths. We first prove the equivalence between the set of admissible permutations (or semipermutations) of a baseline network and that of its reverse network based on a step-by-step permutation routing. We then show that an arbitrary permutation can be realized in a baseline network (or a reverse baseline network) with node-disjoint paths in four passes, which beats the existing results [M. Vaez et al., (2000)], [G. Maier et al., (2001)] that a permutation can be realized in an n /spl times/ n banyan network with node-disjoint paths in O(n/sup 1/2/) passes. This represents the currently best-known result for the number of passes required for routing an arbitrary permutation with node-disjoint paths in unique-path multistage networks. Unlike other unique path MINs (such as omega networks or banyan networks), only baseline networks have been found to possess such four-pass routing property. We present routing algorithms in both self-routing style and central-controlled style. Different from the recent work in [Y. Yang et al., (2003)], which also gave a four-pass node-disjoint routing algorithm for permutations, the new algorithm is efficient in transmission time for messages of any length, while the algorithm in [Y. Yang et al., (2003)] can work efficiently only for long messages. Comparisons with previous results demonstrate that routing in a baseline network proposed in this paper could be a better choice for routing permutations due to its lowest hardware cost and near-optimal transmission time.

A key challenge in wireless sensor networks is to achieve maximal network lifetime with dynamic power management on sensor nodes. In this paper we investigate the node level power control scheduling on densely deployed sensor networks. We prove that given homogeneous Poisson sensing traffic in a sensor network, the routing traffic is heterogeneous. We then introduce a well defined power control model to adapt to heterogeneous traffic, and propose a data-centric energy efficient scheduling protocol under the power model. The simulation results show that our protocol can reduce about 61.4% of power consumption at the sensor node level and achieve 33.3% to 43.5% energy efficiency at the network level, compared to other existing protocols.

We propose a design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N /spl times/ N multicast network, its hardware cost in terms of number of crosspoints is about 2(3 + 2/spl radic/2)N/sup 3/2/ = 11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(-N3/2log N/loglog N) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sub-linear time complexity, and does not require multicast capability for the switch modules in the input stage.

In this paper we study switching fabric design in WDM optical switching networks with recirculating buffers. The switching network we consider may have arbitrary wavelength conversion capabilities. We focus on limited range wavelength conversion while considering full range wavelength conversion as a special case. We show that by adopting the idea of concentrators the cost of the switching fabric can be substantially reduced. For example, for a typical switching network with 16 input/output fibers, 16 wavelength channels per fiber, 12 delay lines and wavelength conversion degree 7, the new design can yield about 20% savings in network cost. We also give an efficient algorithm to assign the outputs to the inputs in the switching network.

A new class of interconnection networks called group connectors are introduced. A group connector G (N,n) is a switching network that consists of N inputs and N outputs such that (1) its N outputs are divided into N/n groups with n outputs in each group, and (2) it can provide any simultaneous one-to-one connections from the N inputs to the N outputs, possibly without the ability of distinguishing the permutation of the outputs within each group. Note that a group connector is able to distinguish among groups of outputs. Group connectors has applications in the switching matrices in dense wavelength-division multiplexing (DWDM) networks. Clearly, an N /spl times/ N permutation network can be used as an N /spl times/ N group connector. We show that a group connector can be built at a lower hardware cost than that of a permutation network of the same size.

We consider cost-effective designs of wavelength division multiplexing (WDM) optical switching networks for current and future generation communication systems. Based on different target applications: we categorize WDM optical switching networks into two connection models: the wavelength-based model and the fiber-link-based model. Most of existing WDM optical switching networks belong to the first category. We present new designs for WDM optical switching networks under both models by using sparse crossbar switches instead of full crossbar switches in combination with wavelength converters. The newly designed sparse WDM optical switching networks have minimum hardware cost in terms of both the number of crosspoints and the number of wavelength converters. The single stage and multistage implementations of the sparse WDM optical switching networks are considered. An optimal routing algorithm for the proposed sparse WDM optical switching networks is also presented.

Optical networking is a promising candidate for high-speed communication networks because of its huge bandwidth. In this paper we study optimal scheduling in buffered WDM packet switching networks with arbitrary wavelength conversion ability. We focus on limited range wavelength conversion while considering full range wavelength conversion as a special case of it. We formalize the problem of maximizing network throughput and minimizing total delay in such a network as finding an optimal matching in a weighted bipartite graph. We then give a simple and fast algorithm called the scan and swap algorithm that solves the problem in O(kB/sup 2/) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to other existing algorithms that need at least O(k/sup 2/B/sup 2/ + k/sup 2/BN) time where N is the number of input fibers.

Summary form only given. Optical communication, in particular, wavelength division multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. A major challenge in designing WDM optical interconnects is how to provide maximum connectivity while keeping minimum hardware cost. The overall hardware cost of a WDM optical interconnect includes not only the cost of switching elements, but also the cost of wavelength conversion. Previous work mainly focused on minimizing hardware cost without taking into consideration of the type of wavelength converters used. We design WDM optical interconnects with full connectivity by using the low cost limited wavelength converters. We present optimal WDM optical interconnects for both permutation and multicast in single stage and multistage implementations. We also discuss the impact of the relationship between the number of fibers and the number of wavelengths per fiber on the optimal design. As can be seen, the newly designed WDM optical interconnects have minimum hardware cost in terms of the number of crosspoints and wavelength conversion cost.

As optical communication becomes a promising networking choice, the well-known Clos network has regained much attention recently from optical switch designers/manufacturers and cluster computing community. There has been much work on the Clos network in the literature due to its uses as optical crossconnects (OXCs) in optical networks and high-speed interconnects in parallel/distributed computing systems. However, little attention has been paid to its fault tolerance capability, an indispensable requirement for any practical high-performance networks. We analyze the fault tolerance capability of the three-stage rearrangeable Clos network. We first establish a fault model on losing-contact faults in the switches of the network. Then, under this model, we analyze the fault tolerance capability of the Clos network when multiple such faults present in switches in the input stage, middle stage, and/or output stage of the network. Our results show that the rearrangeable condition on the number of middle stage switches for a fault-free rearrangeable Clos network still holds in the presence of a substantial amount of faults, while a more expensive crossbar network cannot tolerate any single such fault. In particular, we obtain that, for an N/spl times/N Clos network C(m,n,r), where N = nr and m/spl ges/n, it can tolerate any m - 1 losing-contact faults arbitrarily located in input/output stage switches, or any m - n losing-contact faults arbitrarily located in middle stage switches, when realizing any permutations. We also demonstrate that, for a given permutation, the network usually can tolerate much more such faults. We then present a necessary and sufficient condition on the losing-contact faults a Clos network can tolerate for any given permutation. We also develop an efficient fault-tolerant routing algorithm for a rearrangeable Clos network based on these results.

Optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. A major challenge in designing WDM optical interconnects is how to provide maximum connectivity while keeping minimum hardware cost. The overall hardware cost of a WDM optical interconnect includes not only the cost of switching elements, but also the cost of wavelength conversion. Previous work mainly focused on minimizing hardware cost without taking into consideration the type of wavelength converters used. In this paper, we design WDM optical interconnects with full connectivity by using the low cost limited wavelength converters. We present optimal WDM optical interconnects for both permutation and multicast in single stage and multistage implementations. We also discuss the impact of the relationship between the number of fibers and the number of wavelengths per fiber on the optimal design. As can be seen, the newly designed WDM optical interconnects have minimum hardware cost in terms of the number of crosspoints and wavelength conversion cost.

Currently, many bandwidth-intensive applications require multicast services for efficiency purposes. In particular, as wavelength division multiplexing (WDM) technique emerges as a promising solution to meet the rapidly growing demands on bandwidth in present communication networks, supporting multicast at the WDM layer becomes an important yet challenging issue. In this paper, we introduce a systematic approach to analyzing the multicast connection capacity of WDM switching networks with limited wavelength conversion. We focus on the practical all-optical limited wavelength conversion with a small conversion degree d (e.g., d=2 or 3), where an incoming wavelength can be switched to one of the d outgoing wavelengths. We then compare the multicast performance of the network with limited wavelength conversion to that of no wavelength conversion and full wavelength conversion. Our results demonstrate that limited wavelength conversion with small conversion degrees provides a considerable fraction of the performance improvement obtained by full wavelength conversion over no wavelength conversion. We also present an economical multistage switching architecture for limited wavelength conversion. Our results indicate that the multistage switching architecture along with limited wavelength conversion of small degrees is a cost-effective design for WDM multicast switching networks.

There is a growing demand for network support for group applications, in which messages from one or more sender(s) are delivered to a large number of receivers. Here, we propose a network architecture for supporting a fundamental type of group communication, conferencing. A conference refers to a group of members in a network who communicate with each other within the group. We consider adopting a class of multistage networks, such as a baseline, an omega, or an indirect binary cube network, composed of switch modules with fan-in and fan-out capability for a conference network which supports multiple disjoint conferences. The key issue in designing a conference network is to determine the multiplicity of routing conflicts, which is the maximum number of conflict parties competing a single interstage link when multiple disjoint conferences simultaneously present in the network. Our results show that, for a network of size n /spl times/ n, the multiplicities of routing conflicts are small constants (between 2 and 4) for an omega network or an indirect binary cube network; while it can be as large as /spl radic/n/q + 1 for a baseline network, where q is the minimum allowable conference size. Thus, our design for conference networks is based on an omega network or an indirect binary cube network. We also develop fast self-routing algorithms for setting up routing paths in the newly designed conference networks. As can be seen, such an n /spl times/ n conference network has O(logn) routing time and communication delay and O(nlogn) hardware cost. The conference networks are superior to existing designs in terms of routing complexity, communication delay and hardware cost. The conference network proposed is rearrangeably nonblocking in general, and is strictly nonblocking under some conference service policy. It can be used in applications that require efficient or real-time group communication.