Data center networks (DCNs) are the essential backbone connecting servers, storage, and networking devices, enabling vast data processing and seamless transmission. Among these competing platforms, BCube stands out due to its exceptional scalability and fault tolerance. For a graphGas the underlying topology of a network, the neighbor connectivity (resp. edge-neighbor connectivity) refers to the minimum number of vertices (resp. edges) that the removal of their closed neighborhoods (which is called subversion) results in becoming disconnected, complete, or empty (resp. trivial). These two connectivities provide more precise evaluations of network reliability and fault tolerance. In this paper, we explore these two specific connectivities of BCube and conduct a series of experiments to evaluate the effects of subversion across various scales. Specifically, we compare the experimental outcomes of random failures with those of cascade failures at varying failure rates. Additionally, we conduct a comparative analysis of the average path length (APL) of BCube and other networks, including thek-aryn-cube and DCell, in residual networks after subversion. These experiments enhance our understanding of the complexities of neighbor connectivity and subversion behaviors within BCube, demonstrating its superior fault tolerance.

With the rapid advancement of robotics technologies, a group of robots are able to communicate with one another by wireless transmissions and form a robot swarm. Robot swarm has many applications and a typical one is target search in which swarm robots are sent to places that might be dangerous for human workers, and they coordinate with one another to search for targets such as survivors in a disaster. However, motion coordination of swarm robots for target search has received little attention especially when the targets are mobile. In this work, we develop a motion coordination algorithm for swarm robots to search for targets in an unknown area. Our basic idea is to divide the search area into grids and build a gray-scale map in which each grid is associated with a gray scale indicating the efficiency of searching targets in this grid. The Voronoi diagram is adopted to coordinate swarm robots to search different portions of the search area for maximizing search efficiency. By theoretical analysis, our motion coordination algorithm is validated to ensure that all static targets are guaranteed to be found. We derive an upper-bound on the total time for robots to traverse all the grids in the search area. Extensive simulations are conducted and the results show that the proposed motion coordination algorithm outperforms the state-of-the-art and achieves a success rate of over 90% in finding all mobile targets with low search latency.

Rising concerns about data privacy and volume have driven the development of encrypted and compressed key-value (KV) storage systems. To defend against pattern-analysis attacks, the length and access frequency distributions of packs should appear uniform to adversaries. The design of the packing algorithm is crucial because it determines both pack length and frequency distributions, thereby impacting the overhead for hiding pack pattern information. Existing algorithms focus on minimizing length differences, leading to large variations in pack frequency and thus causing large bandwidth overhead. In this paper, we study the optimal packing problem for encrypted and compressed KV stores, aiming to minimize the overheads for protecting both pack length and frequency information. We propose DualPacking, a two-dimensional packing algorithm with an approximation ratio that depends on the length and frequency distributions of KV pairs. We further develop an encrypted and compressed KV storage system that adapts well to dynamic updates of outsourced stores. Finally, we formally analyze the security of our design and implement it on Redis and RocksDB. Experimental results indicate that, compared to existing packing algorithms, our design reduces the bandwidth overhead by up to 25% and the storage overhead for pack length protection by 33%, confirming its superior efficiency.

It is widely known that parallel and distributed systems are crucial technologies and platforms necessary to support supercomputing and cloud computing. The network architecture forms the foundational support for the stable operation of these systems, directly influencing their reliability, scalability, and robustness. As the network scale expands, the probability of processor/server and communication link failures increases. Therefore, it is imminent to consider how to build up the fault tolerance and reliability of the network. The circulant-based recursive networks (CRNs) are a novel type of network with several desirable properties such as regularity, recursiveness, vertex (edge) transitivity and so on. CRNs contain not only interconnection networks hypercubes and$k$-ary$n$-cubes, but also data center network BCube, as well as some future networks. Connectivity and diagnosability of networks have garnered significant attention, as they suffice for analyzing and measuring networks' fault tolerance. This article focuses primarily on conditional connectivity and diagnosability under the good neighbor fault pattern. In this work, we explore the conditional connectivity and diagnosability (built on$g$-good neighbor fault pattern) of the$f$-dimensional$r$-order CRN under the PMC model and MM* model, respectively. These values are nearly$g$times greater than the traditional connectivity and diagnosability of CRNs, respectively, implying that they can further improve fault tolerance of CRNs. Furthermore, it is worth noting that the results can be effectively utilized in BCube and other future networks given that they are both subclasses of CRNs.

Multi-modal federated learning (MFL) offers the advantage of aggregating models from diverse data modalities to obtain a more powerful fused model while preserving data privacy. However, MFL faces three key challenges: 1) Communication overhead - only a limited number of clients can participate in training due to communication budget constraints; 2) Modality heterogeneity - different modalities contribute unequally to the fused model; 3) Client heterogeneity - clients exhibit variations in data quantity and quality across modalities. To address these challenges, we formulate a joint client-modality selection problem under communication budget constraints. The goal is to determine the participating clients and their uploaded modalities in each communication round, maximizing the performance of the fused model given a limited communication budget. We propose a dynamic many-to-many matching algorithm with two quota budgeting strategies: 1) Round-aware Modality Budgeting (RMB) determines the total number of uploaded modality models per round based on the current training process (i.e., how close the model is to convergence). 2) Modality-aware Client Allocation (MCB) adaptively allocates client quota for each modality by balancing the modality’s contribution to the fusion model against its model size. After quota budgeting, we construct preference lists for clients and modalities to find a stable many-to-many matching of (client, modality) pairs. Experiments demonstrate that our algorithm achieves better model performance than baselines under the same communication budget, validating the benefits of dynamic budget allocation and client scheduling.

Robots are widely used for target search in applications such as search and rescue, environmental monitoring, and surveillance. Existing search algorithms typically rely on target signals or predictable movement patterns, which might not be available in real applications. In this paper, we address the practical challenge of a target search problem where targets do not emit signals and have unpredictable movement patterns. The problem is formulated as an area coverage problem: how to maximize the coverage of the robots’ detection areas within a limited time. We propose an algorithm that divides the search area into multiple partitions and assigns specific partitions to robots for maximizing their coverage and the success rate of target detection. Within each partition, the random walk technique is adopted by the robots to handle robot failures and unknown obstacles. Through theoretical analysis and experiments, we explore the optimal number of partitions as well as the optimal partition shape to facilitate searching. Extensive simulations across different dynamic environments validate the effectiveness and adaptability of our proposed algorithm.

This paper studies information freshness in collaborative surveillance scenarios operated with non-orthogonal multiple access (NOMA), where each monitoring device observes a portion of a common target and reports its latest status on the target to a common access point (AP) to recover the complete observation. We use age of collection (AoC) as a metric of information freshness. Unlike the conventional age of information (AoI) metric, the instantaneous AoC decreases only when the AP receives all partial updates from different devices (i.e., successfully receives a “joint” update). Conventional NOMA schemes typically use multiuser decoding (MUD) techniques to decode update messages from different devices. However, MUD does not work well when the signal-to-noise ratios (SNRs) of different NOMA users are (nearly) balanced. Therefore, we consider network-coded multiple access (NCMA), an advanced NOMA scheme that integrates MUD with physical-layer network coding (PNC). PNC is a technique that turns wireless interferences into useful network-coded information, which works well even when the SNRs of different users do not differ much. Experimental results on software-defined radios indicate that NCMA is a practical solution for achieving low average AoC under different channel conditions. This is the first study to show that NCMA, thanks to the combination of MUD and PNC, can receive joint update messages in a shorter period of time, thus significantly reducing the average AoC of the system.

This paper investigates the information freshness of joint status updates, quantified by the age of collection (AoC), in uplink coordinated direct and relay transmission (CDRT). In an uplink CDRT setup, a direct sensor communicates directly with the destination, while a relay-aided sensor relies on a decode-and-forward relay. The update packet of each sensor contains partial information about a common observation target. The AoC measures the time elapsed since the generation of the latest set of update packets received at the destination. Hence, unlike the age of information (AoI) metric, the AoC decreases only when all update packets from multiple sources for a common observation are collected (i.e., a successful joint update). When simultaneous transmissions from the direct and relay-aided sensors cause packet collisions at the relay, conventional multiuser decoding (MUD) is usually used to decode native packets explicitly from the superimposed signals. Nevertheless, MUD does not work well when the signal-to-noise ratios (SNRs) of different sensors are (nearly) equal. To this end, this paper puts forth a physical-layer network coding (PNC)-aided CDRT scheme for joint information updating, utilizing both MUD and PNC decoders. The PNC decoder decodes superimposed signals into network-coded packets, particularly effective when the SNRs of different sensors are close. We design an automatic repeat request (ARQ) protocol tailored to low AoC and study how network-coded packets can be utilized to reduce the AoC of uplink CDRT, where the closed-form peak AoC formula is derived. We evaluate the PNC-aided CDRT scheme using software-defined radios. Experimental results show that our PNC-aided CDRT scheme significantly reduces the average peak AoC under various SNR conditions.

Connected-dominating-set (CDS) is a representative technique for constructing virtual backbones of wireless networks and thus facilitates implementation of many tasks including broadcasting, routing, etc. Most of existing works on CDS aim at constructing the minimum CDS (MCDS), so as to reduce the communication overhead over the CDS. However, MCDS may not work well in cognitive radio networks (CRNs) where communication links are prone to failure due to stochastic activities of primary users (PUs). A MCDS without consideration of the stochastic activities of PUs easily becomes invalid when the PUs become active. This study addresses a new CDS construction problem by considering the PUs’ activities. Our problem is to maximize the lifetime of the CDS while minimizing the size of the CDS, where the lifetime of a CDS is defined as the expected duration that the CDS is maintained valid. We show that the problem is NP-hard and propose a three-phase centralized algorithm. Given a CRN, the centralized algorithm can compute a CDS such that the lifetime of the CDS is maximized (optimal), and the size of the CDS is upper-bounded. We further present a two-phase localized algorithm which requires 2-hop information. Extensive simulations are conducted to evaluate the proposed algorithms.

The multi-channel blind rendezvous problem in distributed cognitive radio networks (DCRNs) refers to how users can hop to the same channel at the same time slot without any prior knowledge (i.e., each user is unaware of other users' information). The channel hopping (CH) technique is a typical solution to this blind rendezvous problem. In this paper, we propose a quinary coding and matrix structure-based CH algorithm called QCMS-CH. It can guarantee the rendezvous of users using only one cognitive radio in the scenario of the asynchronous clock (i.e., arbitrary time drift between users), heterogeneous channels (i.e., the available channel sets of users are distinct), and symmetric role (i.e., all users play a same role). The QCMS-CH algorithm first represents a randomly selected channel (denoted by R) as a fixed-length quaternary number. Then it encodes the quaternary number into a quinary bootstrapping sequence according to a carefully designed quaternary-quinary coding table with the prefix “R00”. Finally, it builds a CH matrix column by column according to the bootstrapping sequence and six different types of elaborately generated subsequences. The user can access the CH matrix row by row and accordingly perform its channel hopping to attempt to rendezvous with other users. We derive an upper bound on its Maximum Time-To-Rendezvous (MTTR). Simulation results show that QCMS-CH algorithm outperforms the state-of-the-art in terms of the MTTR and the Expected Time-To-Rendezvous (ETTR).

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish communication links. Most of existing works were devoted to shortening the time-to-rendezvous (TTR) but paid little attention to qualities of the channels on which rendezvous is achieved. In fact, qualities of channels, such as resistance to primary users' activities, have a great effect on the rendezvous operation. If users achieve a rendezvous on a low-quality channel, the communication link is unstable and the communication performance is poor. In this case, re- rendezvous is required which results in considerable communication overhead and a large latency. In this paper, we first show that actual TTRs of existing rendezvous solutions increase by 65.40-104.38% if qualities of channels are not perfect. Then we propose a Quality-Aware Rendezvous Framework (QARF) that can be applied to any existing ren-dezvous algorithms to achieve rendezvous on high-quality channels. The basic idea of QARF is to expand the set of available channels by selectively duplicating high-quality channels. We prove that QARF can reduce the expected TTR of any rendezvous algorithm when the expanded ratio$\lambda$is smaller than the threshold$(-3+\sqrt{1+4(\frac{\sigma}{\mu})^{2}}) / 2$, where$\mu$and$\sigma$, respectively, are the mean and the standard deviation of qualities of channels. We further prove that QARF can always reduce the expected TTR of Random algorithm by a factor of$1+(\frac{\sigma}{\mu})^{2}$. Extensive experiments are conducted and the results show that QARF can significantly reduce the TTRs of the existing rendezvous algorithms by 10.50-51.05 % when qualities of channels are taken into account.

Energy conservation of large data centers for high performance computing workloads, such as deep learning with Big Data, is of critical significance, where cutting down a few percent of electricity translates into million-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a batch of offline tasks or a sequence of real-time tasks under deadline constraints. We derive a fast and accurate analytical model to compute the appropriate voltage/frequency setting for each task, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 36% of energy can be saved, we record 33-35% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters.

Minimizing energy consumption of data centers is important to reduce carbon emissions. Virtual machines (VMs) consolidation is a typical technique to utilize the available data center resources and thus improve energy efficiency. The cooling systems consume up to 50% of the total data center electricity. In this work, we investigate the joint energy optimization of cooling systems and VM consolidations in cloud data centers. We propose a cooling-aware VM consolidation (CAVC for short) algorithm to the problem. The CAVC algorithm is a two-stage solution: 1) we first relax the constraints of the problem and determine an optimal number of physical machines (PMs) and an optimal CPU utilization of the PMs that yields the minimum cooling power; and 2) based on the initial solution of the first stage, we consolidate the VMs into the predetermined PMs with the predetermined CPU utilization ratio as much as possible. To the best of authors’ knowledge, this is the first work that jointly considers the VM consolidation and the cooling systems in minimizing energy consumption of cloud data centers. We derive an approximation ratio of CAVC over the optimal solution. The real-world data set (i.e., Google cluster data) is adopted in the simulations and the results show that the CAVC algorithm yields very close energy consumption to the theoretical lower bound.

Erasure codes have been used extensively in large-scale storage systems to reduce the storage overhead of triplication-based storage systems. One key performance issue introduced by erasure codes is the long time needed to recover from a single failure, which occurs constantly in large-scale storage systems. We present ESetStore, a prototype erasure-coded storage system that aims to achieve fast recovery from failures. ESetStore is novel in the following aspects. We proposed a data placement algorithm named ESet for our ESetStore that can aggregate adequate I/O resources from available storage servers to recover from each single failure. We designed and implemented efficient read and write operations on our erasure-coded storage system via effective use of available I/O and computation resources. We evaluated the performance of ESetStore with extensive experiments on a cluster with 50 storage servers. The evaluation results demonstrate that our recovery performance can obtain linear performance growth by harvesting available I/O resources. With our defined parameter recovery I/O parallelism under some mild conditions, we can achieve optimal recovery performance, in which ESet enables minimal recovery time. Rather than being an alternative to improve recovery performance, our work can be an enhancement for existing solutions, such as Partial-parallel-repair (PPR), to further improve recovery performance.

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish a communication link on a commonly-available channel for communications. Most of existing rendezvous algorithms provide guaranteed rendezvous (i.e., rendezvous can be achieved within finite time) by generating channel-hopping (CH) sequences based on the whole channel set. These algorithms are inefficient when available channels account for a small proportion of the whole channel set. Some recent algorithms generate CH sequences based on the available channel set. However, these algorithms normally require additional information such as unique IDs and predefined roles of cognitive users. In this study, we design a new algorithm called ZOS based on the set of available channels without any additional requirements. ZOS uses three types of elementary sequences (namely, Zero-type, One-type, and S-type) to generate CH sequences and provides guaranteed rendezvous. The maximum time-to-rendezvous of ZOS is upper-bounded by O(m1×m2×log2M) where M is the number of all channels and m1 and m2 are the numbers of available channels of two users. Simulation results show superior performance of ZOS.

In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish communication links. Most of existing works consider rendezvous of a pair of users. When multiple pairs of users are doing rendezvous, collisions are caused by the multiple user-pairs which significantly degrade the rendezvous performance, e.g., resulting in a long time-to-rendezvous. To address this problem, we propose a new protocol called Cooperative Rendezvous Protocol which exploits cooperation in the multiple user-pairs environment to speed up the rendezvous operation. Using this protocol, multiple user-pairs cooperate with each other to relay their channel availability information, so that they could avoid attempting rendezvous in unavailable channels. The proposed protocol serves as a general framework that can be applied in conjunction with any existing rendezvous algorithm for faster rendezvous. We theoretically derive an upper bound on the time-to-rendezvous when the proposed protocol is applied in conjunction with any rendezvous algorithm which generates channel hopping sequence based on the available channel set. In addition, we conduct extensive simulation and the results show that the proposed protocol can significantly reduce the time-to-rendezvous of the existing rendezvous algorithms by up to 80.86% in multiple user-pairs environment.

Collective motion is a fundamental operation of robot swarms by which a group of robots move from a source to a destination in a cohesive way (i.e., connectivity is preserved during these movements). However, the collective motion of robot swarms along preplanned paths has not been well studied. In this paper, we propose self-adaptive collective motion algorithms for swarm robots in 3-D space. Using the proposed collective motion algorithms, robots are able to move along a preplanned path from a source to a destination while satisfying the following requirements: 1) the robots use only one-hop neighbor information; 2) the robots maintain connectivity of the network topology for information exchange; 3) the robots maintain a desired neighboring distance; and 4) the robots are capable of bypassing obstacles without partitioning the robot swarm (i.e., member loss). Our basic idea is to introduce a guidance force and a topology force into the system. The guidance force is used to guide the robots to their destination along the preplanned path. It ensures that the robots continue to move until they reach their destination. The topology force is used to maintain a “good” topology of the robot swarm, such as maintaining connectivity of the network topology and the desired distance between neighboring robots. The resultant of the guidance and topology forces determines the movement of a robot. We develop collective motion algorithms for three cases: 1) no obstacles or leaders; 2) no obstacles with a leader; and 3) with obstacles (with and without a leader). Extensive simulations are conducted to evaluate performance of the proposed algorithms. The simulation results show that: 1) our algorithms meet all the requirements; 2) our algorithms are resistant to GPS errors and robot failures; and 3) self-adaptive control of our algorithms makes network topologies more stable and significantly saves travel time of swarm robots. Note to Practitioners-We propose self-adaptive collective motion algorithms that enable swarm robots to move along a preplanned path from a source to a destination in 3-D space. Our algorithms use only one-hop neighbor information and operate without central controllers. The algorithms are designed to be self-adaptive in the sense that robots are able to dynamically determine proper moving parameters, based on their environments and statuses. With the proposed algorithms, swarm robots are able to: 1) maintain connectivity and a desired neighboring distance during movement; 2) bypass obstacles without member loss (i.e., the robot swarm is partitioned); and 3) be resistant to GPS errors and robot failures. We address both cases of with a leader and without a leader. Simulation results show effectiveness of our algorithms which can be applied in applications of surveillance, search and rescue, mining, agricultural foraging, autonomous military units, and distributed sensing in micromachinery or human bodies.

Cloud federation paradigm can improve cloud service providers' (CSPs) profits by renting their idle resource to other federation members. However, these CSPs have the risk that they cannot fulfill their scalability commitment when some of their customers have large short-term resource demand. To reduce this risk, we design a reinsurance-emulated collaboration mechanism in a broker-based cloud federation. Reinsurance is an insurance policy which transfers all or part of insurance business in order to scatter the risk to other insurers. Similar to insurance companies, in our proposed model, each CSP determines its resource retention for its future demand. We design an exact method to determine each CSP's retention, with the aim of maximizing its expected profit. Once the CSP's retention cannot meet its future demand, it reduces the risk by outsourcing part of the requests to others. After every CSP determines its retention, the broker will make an assignment to maximize the resource utilization so as to reduce the risk of the CSPs. We designed an algorithm to maximize the resource utilization, with a guarantee of not worse than half of the optimal solution. Simulation results show that our proposed algorithm is efficient.

Conserving the energy consumption of large data centers is of critical significance, where a few percent in consumption reduction translates into millions-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a sequence of real-time tasks under deadline constraints. We compute the appropriate voltage/frequency setting for each task through mathematical optimization, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 38% of energy can be saved, we record 30-36% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption.

Compared to general vehicular systems, bus systems have advantages including wide coverage, fixed routes, and regular service. Inspired by these unique features of the bus systems, we propose to use the bus systems as routing backbones of VANETs. In this work, we present a Community-based Bus System (CBS) which consists of two components: a community-based backbone and a routing scheme over the backbone. The backbone construction is a one-off operation which is done offline while the routing is done online in individual buses. We build a community-based backbone by applying community detection techniques and propose a twolevel routing scheme which operates over the backbone. The proposed routing scheme performs sequentially in the inter-community level and the intra-community level, and is able to support message delivery to both buses and specific locations/areas. We develop a probabilistic model to analyze the message delivery latency of CBS. The average error of the analytically-derived latency is shown to be 8.9 percent of the latency derived from the real traces. Extensive experiments are conducted on real-world traces from the Beijing bus system and the Dublin bus system and the results show that CBS can significantly lower the delivery latency and improve the delivery ratio, compared to the existing solutions. CBS is a general solution which is applicable to any bus-based VANETs.

Virtual machine (VM) consolidation and switch/path consolidation are two typical techniques for improving energy efficiency in data centers (DCs). Most of existing work separately optimize VM consolidation and switch consolidation which results in inferiority of the optimization performance. Moreover, these work usually handle a user application as a VM flow (i.e., a source VM is connected to a destination VM). In practice, however, relation of VMs could be much more complex than the single flow and multiple VMs are connected via a network. In this work, we address a general DC energy optimization problem that enables tenants to express their applications by a general resource request graph (i.e., computation requests of VMs, bandwidth requests of VM communications, and time requests of VM execution). We propose a joint VM-switch consolidation (JVSC for short) algorithm to this problem. JVSC jointly optimizes the energy consumption of DCs in three steps: (i) it decreases the number of active PMs by VM consolidation; (ii) it decreases the number of active switches by switch consolidation at the tor tier, the aggregation tier and the core tier of the network, respectively; and (iii) it minimizes energy consumption of VM migration via an energy-aware migration strategy. Extensive experiments are conducted on both simulated applications and real Google cluster usage traces. Experimental results demonstrate that JVSC can save 60% around energy of DCs, compared to the state-of-the-art.

Mobile crowdsensing (MCS) is a promising paradigm that utilizes the mobility of people and the sensing capabilities of their mobile devices to accomplish a variety of sensing tasks. In this paper, we adopt the Signaling System No.7 (SS7) as the MCS platform since SS7 can well capture trajectories and mobility patterns of the mobile users. We collect a real-world SS7 data of 1.18 million mobile users at 3512 cell towers/sites in Xiamen, China. We first analyze this dataset and reveal important characteristics of user mobility. Then, we address a Mobile User Recruitment (MUR) problem which is crucial to all MCS systems. Given SS7 data of mobile users, a set of target cells to be sensed/covered, and recruitment cost functions of the mobile users, the MUR problem is to recruit a set of mobile users such that all the target cells are covered and the total recruitment cost is minimized. Our MUR problem is general and includes the existing problems as its special cases. We prove NP-hardness of the problem. We propose an approximation algorithm to this problem and derive the approximation ratio. Extensive experiments are conducted on the real-world SS7 dataset and results show that the proposed solution outperforms two baseline algorithms by saving 22.6% and 62.9% recruitment costs, respectively, on average.

Bus networks in cities have distinctive features such as wide coverage and fixed bus routes so that they show the potential of forming the communication backbone in vehicular ad hoc networks (VANETs). This paper focuses on the geocast in bus-based VANETs and presents a geocast routing mechanism named Vela. Specifically, Vela analyzes and mines historical bus trajectories and characterizes spatial–temporal patterns (i.e., bus travel-time patterns and bus spatial encounter patterns) in a moderate granularity of road segments, which makes the mined patterns both accurate and steady. Furthermore, Vela exploits these acquired patterns to build a probabilistic spatial–temporal graph model and provides the available routing paths with the best possible quality-of-service levels for data delivery requests. Moreover, Vela also employs a two-hop aware strategy that utilizes the real-time spatial–temporal relationships between buses to increase the chances of forwarding the data. The results of the experiments on the real and synthetic trajectories show that Vela performs much better in terms of delivery ratio and delay and has stronger scalability than the other solutions.

Rendezvous is a fundamental operation for cognitive users to establish communication links so as to realize data communications and network management. Most of existing rendezvous algorithms implicitly assume that each cognitive user is equipped with one radio, i.e., one wireless transceiver. As the cost of wireless transceivers is dropping, it becomes economically feasible to utilize multiple radios to significantly improve the rendezvous performance. In this paper, we propose an Adjustable Multi-Radio Rendezvous (AMRR) algorithm which exploits multiple radios for fast rendezvous based on available channels only. Suppose that a cognitive user is equipped with m radios. Our basic idea is to partition the radios into two groups: k stay radios and (m - k) hopping radios. The user stays on specific channels in the stay radios while hops on its available channels parallelly in the hopping radios. We prove that the maximum time-to-rendezvous (MTTR) of AMRR is upper-bounded by O(|C1||C2|/m1m2), where |C1| and |C2| are the numbers of available channels of two users and m1and m2are the numbers of radios of the two users. This bound meets the lower bound of MTTR of any deterministic rendezvous algorithm when two users are equipped with the same number of radios (i.e., m1= m2). AMRR is adjustable in giving its best performance on either MTTR or E(TTR) by adjusting value of k. Simulation results show that AMRR performs better than the state-of-the-art.

Abstract—In recent years, erasure coding has been adopted by large-scale cloud storage systems to replace data replication. With the increase of disk I/O throughput and network bandwidth, the speed of erasure coding becomes one of the key system bot-tlenecks. In this paper, we propose to offload the task of erasure coding to Graphics Processing Units (GPUs). Specifically, we have designed and implemented PErasure, a parallel Cauchy Reed-Solomon (CRS) coding library. We compare the performance of PErasure with that of two state-of-the-art libraries: Jerasure (for CPUs) and Gibraltar (for GPUs). Our experiments show that the raw coding speed of PErasure on a $500 Nvidia GTX780 card is about 10 times faster than that of multithreaded Jerasure on a quad-core modern CPU, and 2-4 times faster than Gibraltar on the same GPU. PErasure can achieve up to 10GB/s of overall encoding speed using just a single GPU for a large storage system that can withstand up to 8 disk failures. I.

Low delivery latency and high delivery ratio are two key goals in the design of routing schemes in Vehicular Ad Hoc Networks (VANETs). The existing routing schemes utilize real-time information (e.g., Geographical position and vehicle density) and historical information (e.g., Contacts of vehicles), which usually suffer from a long delivery latency and a low delivery ratio. Inspired by the unique features of bus systems such as wide coverage, fixed routes and regular service, we propose to use the bus systems as routing backbones of VANETs. In this work, we present a Community-based Bus System (CBS) which consists of two components: a community-based backbone and a routing scheme over the backbone. We collect real traces of 2515 buses in Beijing and build a community-based backbone by applying community detection techniques in the Beijing bus system. A two-level routing scheme is proposed to operate over the backbone. The proposed routing scheme performs sequentially in the inter-community level and the intra-community level, and is able to support message delivery to both mobile vehicles and specific locations/areas. Extensive experiments are conducted on the real trace data of the Beijing bus system and the results show that CBS can significantly lower the delivery latency and improve the delivery ratio. CBS is applicable to any bus-based VANETs.

Latest developments in cloud computing technologies have enabled a plethora of cloud based data storage services. Cloud storage service providers are facing significant bandwidth cost as the user population scales. Such bandwidth cost can be substantially slashed by exploring a hybrid cloud storage architecture that takes advantage of under-utilized storage and network resources at storage clients. A critical component in the new hybrid cloud storage architecture is an economic mechanism that incentivizes clients to contribute their local resources, while at the same time minimizes the provider's cost for pooling those resources. This work studies online procurement auction mechanisms towards these goals. The online nature of the auction is in line with asynchronous user request arrivals in practice. After carefully characterizing truthfulness conditions under the online procurement auction paradigm, we prove that truthfulness can be guaranteed by a price-based allocation rule and payment rule. Our truthfulness characterization actually converts the mechanism design problem into an online algorithm design problem, with a marginal pricing function for resources as variables set by cloud storage service providers for online procurement auction. We derive the marginal pricing function for the online algorithm. We also prove the competitive ratio of the social cost of our algorithm against that of the offline VCG mechanism and of the resource pooling cost of our algorithm against that of the offline optimal auction. Simulation studies driven by real-world traces are conducted to show the efficacy of our online auction mechanism.

Rendezvous is a fundamental operation in cognitive radio networks (CRNs) for establishing a communication link on a commonly-available channel between cognitive users. The existing work on rendezvous implicitly assumes that each cognitive user is equipped with one radio (i.e., one wireless transceiver). As the cost of wireless transceivers is dropping, this feature can be exploited to significantly improve the rendezvous performance at low cost. In this study, we investigate the rendezvous problem in CRNs where cognitive users are equipped with multiple radios and different users may have different numbers of radios. We first study how the existing rendezvous algorithms can be generalized to use multiple radios for faster rendezvous. We then propose a new rendezvous algorithm, called role-based parallel sequence (RPS), which specifically exploits multiple radios for more efficient rendezvous. Our basic idea is to let the cognitive users stay in a specific channel in one dedicated radio and hop on the available channels with parallel sequences in the remaining general radios. We prove that our algorithm provides guaranteed rendezvous (i.e., rendezvous can be completed within a finite time) and derive the upper bounds on the maximum time-to-rendezvous (TTR) and the expected TTR. The simulation results show that i) multiple radios can cost-effectively improve the rendezvous performance, and ii) the proposed RPS algorithm performs better than the ones generalized from the existing algorithms.

Server selection is an important problem of cloud computing in which cloud service providers direct user demands to servers in one of the multiple data centers located in different geographical locations. The existing solutions usually assume homogeneity of cloud services (i.e., all users request the same type of service) and handle user demands in an individual basis which incurs high computational overhead. In this study, we propose a new and effective server selection scheme in which diversities of cloud services are taken into account. We focus on a specific cloud service, i.e., online video service, and assume that different videos have different bandwidth requirements. We group users into clusters and handle user demands on a cluster basis for faster and more efficient process. Given user demands and bandwidth capacities of servers in the data centers, our problem is to assign the user demands to the servers under the bandwidth constraint, such that the overall latency (measured by the network distance) between the user clusters and the selected servers is minimized. We design a server selection system and formulate this problem as a linear programming formulation which can be solved by existing techniques. The system periodically executes our scheme and computes an optimal solution for server selection. User demands are assigned to the servers according to the optimal solution and the minimum overall latency can be achieved. The simulation results show that our scheme is significantly better than the random algorithm and the YouTube server selection strategy.

Rendezvous is a necessary operation for cognitive users to establish communication links in cognitive radio networks (CRNs). To guarantee the rendezvous in finite time, all existing rendezvous algorithms generate CH (channel-hopping) sequences using the whole channel set and attempt rendezvous on each of the channels (i.e., both available channels and unavailable channels). In practice, the available channel set is usually a small portion of the whole channel set due to dynamics of channel availabilities and limited sensing capabilities of cognitive users. Thus, the CH sequences using the whole channel set may attempt unnecessary rendezvous in uncertain channels (e.g., unavailable channels or randomly-selected channels) which greatly degrades the performance. In this study, we propose a new rendezvous algorithm that generates channel-hopping sequences based on available channel set (CSAC) for more efficient rendezvous. We prove that CSAC gives guaranteed rendezvous and derive its upper-bound on maximum time-to-rendezvous (MTTR) which is an expression of the number of available channels instead of the number of all potential channels. To the best of our knowledge, CSAC is the first one in the literature that exploits the only available channels in designing CH sequences while providing guaranteed rendezvous. Experimental results show that CSAC can significantly improve the MTTR compared to state-of-the-art.

Rendezvous is a fundamental operation in cognitive radio networks (CRNs) for establishing a communication link on a commonly-available channel between cognitive users. The existing works on rendezvous implicitly assume that each cognitive user is equipped with one radio (i.e., one wireless transceiver). As the cost of wireless transceivers is dropping, this feature can be exploited to significantly improve the rendezvous performance at low cost. In this study, we investigate the rendezvous problem in CRNs where cognitive users are equipped with multiple radios and different users may have different number of radios. We first study how the existing rendezvous algorithms can be generalized to use multiple radios for faster rendezvous. We then propose a new rendezvous algorithm, called role-based parallel sequence (RPS), which specifically exploits multiple radios for more efficient rendezvous. Our basic idea is to let the cognitive users stay in a specific channel in one dedicated radio and hop on the available channels with parallel sequences in the remaining general radios. We prove that our algorithm provides guaranteed rendezvous and derive the maximum time-to-rendezvous (TTR) and upper-bounds on the expected TTR. Extensive experiments are conducted to evaluate the proposed solutions.

In sensor-target surveillance networks, sensors are typically powered by batteries with limited energy and hence it is important to manage the energy usage. In the literature, several methods have been proposed to maximize the lifetime of these networks. We observe that some surveillance applications have lifetime requirements. For example, a surveillance network is used to monitor the precious items in an exhibition and its lifetime must be at least equal to the duration of exhibition. For these surveillance applications, it is desirable to minimize the network cost while fulfilling the given lifetime requirement. In this paper, we address a new problem in which the network cost is minimized while the resulting lifetime is at least equal to a given value L. To minimize the network cost, we place the minimum number of sensors such that all the given targets can be monitored for a duration of at least L and all the sensed data can be forwarded to a given base station. We prove that this problem is NP-hard and derive a lower bound on the minimum number of sensors required. We design an efficient approximation algorithm for this problem. Theoretically, we prove that this approximation algorithm has an approximation ratio of max {2l - m + 2, 3}, where m is the number of targets and l is the number of targets in a small disk centered at the base station with a constant radius. Experimentally, we conduct computer simulation to demonstrate that this approximation algorithm gives close-to-optimal solutions.

Power-aware routing and controlled mobility schemes are two commonly used mechanisms for improving communications in a wireless sensor network. While the former actively consider the transmission costs when selecting the next hop on the route, the latter instruct mobile relay nodes (either sensors or actuators) to pursue more promising locations so as to optimize end-to-end transmission power. Rarely, if ever, the two methodologies are exploited together for achieving relevant energy savings and prolonging network lifetime. In this paper, we introduce a hybrid routing-mobility model for the optimization of network communications. First, we find a multi-hop path between a source and its destination in an energy-efficient fashion and then we move all hop nodes in an uninterrupted, straight manner to some predefined spots with optimal energy-saving properties, fully preserving the path connectivity as they move. Such synergetic approach allowed us to: (1) seamlessly guarantee message delivery regardless of the network density (average number of neighbors per node), (2) easily incorporate any power-related optimization criterion to the routing protocol and (3) even target scenarios where both end nodes are actually disconnected from each other. Results gathered from extensive simulations argue for the introduction of the proposed hybrid framework.

Bi-connectivity is a basic requirement for designing fault tolerant topologies in wireless networks. In cognitive radio networks (CRNs), available channels of cognitive users dynamically change since a channel becomes unavailable whenever the channel is reclaimed by primary users. Therefore, fault tolerance of CRNs highly depends on the status of channel availability. However, traditional definition of bi-connectivity concerns only node/link failure and thus is not suitable to CRNs. In this study, we introduce a new definition of generalized-bi-connectivity (g-bi-connectivity) where a CRN is said to be g-bi-connected if the remaining network is still connected when any one of the two events occurs: i) any node fails; ii) any channel becomes unavailable. Based on this definition, our problem is to build a g-bi-connected network by assigning power and channels to the cognitive users. Our objective is to minimize the maximum transmission power of users and the number of channels required. We propose a two-stage approach which consists of the power assignment stage and the channel assignment stage. In the power assignment, we integrate a novel degree-control process which prepares a good topology for minimizing the number of channels in the next stage. We prove that the maximum transmission power of cognitive users is optimized and derive an upper- bound on the number of channels required. We present distributed topology recovery algorithms which give guaranteed g-bi-connectivity in case of node-join and node-leave. Extensive simulations are conducted to evaluate performance of our solution.

Cognitive radio networks (CRNs) have emerged as advanced and promising paradigm to exploit the existing wireless spectrum opportunistically. It is crucial for users in CRNs to search for neighbors via rendezvous process and thereby establish the communication links to exchange the information necessary for spectrum management and channel contention, etc. This paper focuses on the design of algorithms for blind rendezvous, i.e., rendezvous without using any centralized controller and common control channel (CCC). We propose a jump-stay channel-hopping (CH) algorithm for blind rendezvous. The basic idea is to generate CH sequence in rounds and each round consists of a jump-pattern and a stay-pattern. Users “jump” on available channels in the jump-pattern while “stay” on a specific channel in the stay-pattern. We prove that two users can achieve rendezvous in one of four possible pattern combinations: jump-stay, stay-jump, jump-jump, and stay-stay. Compared with the existing CH algorithms, our algorithm has the overall best performance in various scenarios and is applicable to rendezvous of multiuser and multihop scenarios. We derive upper bounds on the maximum time-to-rendezvous (TTR) and the expected TTR of our algorithm for both 2-user and multiuser scenarios (shown in Table 1). Extensive simulations are conducted to evaluate the performance of our algorithm.

Cognitive radio networks (CRNs) have emerged as advanced and promising paradigm to exploit the existing wireless spectrum opportunistically. It is crucial for users in CRNs to search for neighbors via rendezvous process and thereby establish the communication links to exchange the information necessary for spectrum management and channel contention etc. This paper focuses on the design of algorithms for blind rendezvous, i.e., rendezvous without using any central controller and common control channel (CCC). We propose a jump-stay based channel-hopping (CH) algorithm for blind rendezvous. The basic idea is to generate CH sequence in rounds and each round consists of a jump-pattern and a stay-pattern. Users “jump” on available channels in the jump-pattern while “stay” on a specific channel in the stay-pattern. Compared with the existing CH algorithms, our algorithm achieves the following advances: i) guaranteed rendezvous without the need of time-synchronization; ii) applicability to rendezvous of multi-user and multi-hop scenarios. We derive the maximum time-to-rendezvous (TTR) and the upper-bound of expected TTR of our algorithm for both 2-user and multi-user scenarios (shown in Table I). Extensive simulations are further conducted to evaluate performance of our algorithm.

We address a new and general maximal lifetime problem in sensor-target surveillance. We assume that each sensor can watch at most k targets (k ≥ 1) and each target should be watched by h sensors (h ≥ 1) at any time. The problem is to schedule sensors to watch targets and forward the sensed data to a base station such that the lifetime of the surveillance network is maximized. This general problem includes the existing ones as its special cases (k = 1 and h = 1 in and k = 1 and h ≥ 2 in). It is also important in practice because some sensors can monitor multiple or all targets within their surveillance ranges and multisensor fusion (i.e., watching a target by multiple sensors) gives better surveillance results. The problem involves several subproblems and one of them is a new matching problem called (k, h)-matching. The (k, h)-matching problem is a generalized version of the classic bipartite matching problem (when k = h = 1, (k, h)-matching becomes bipartite matching). We design an efficient (k, h)-matching algorithm to solve the (k, h)-matching problem and then solve the general maximal lifetime problem. As a byproduct of this study, the (k, h)-matching problem and the proposed (k, h)-matching algorithm can potentially be applied to other problems in computer science and operations research.

Robotic sensor networks are more powerful than sensor networks because the sensors can be moved by the robots to adjust their sensing coverage. In robotic sensor networks, an important problem is movement control: how the robots can autonomously move to the desired locations for sensing and data collection. In this paper, we study a new movement control problem with the following essential requirements: i) an initial and possibly disconnected network is self-organized into a bi-connected network, ii) only 1-hop information is used for movement control, iii) the coverage of the network is maximized while the total moving distance in the movement process is minimized. We propose a simple movement control algorithm for this problem. This algorithm emulates the attractive force (such as the force in a stretched spring) and the repulsive force (such as the electrostatic force between electric charges) in nature, such that each robot simply follows the resultant virtual force to move. We theoretically prove that this algorithm guarantees bi-connected networks under a mild condition and derive bounds on the maximum coverage and the minimum moving distance. We conduct extensive simulation experiments to demonstrate that the proposed algorithm is effective.

The paper addresses the maximal lifetime problem in sensor-target surveillance networks. Given a set of sensors and targets in an Euclidean plane, each sensor can watch all targets within its surveillance range and each target should be watched by at least one sensor at any time. The problem is to schedule the sensors to watch the targets and forward the sensed data to the base station, such that the lifetime of the surveillance network is maximized, where the lifetime is the duration that all targets are watched and all active sensors are connected to the base station. We propose an optimal solution to achieve the maximal lifetime. Our solution consists of three steps: 1) compute the maximal lifetime of the surveillance network and find a workload matrix and data flows by using the linear programming technique; 2) decompose the workload matrix into a sequence of schedule matrices by using the perfect matching technique; 3) determine the sensor-target surveillance trees based on the above obtained schedule matrices and data flows, which specify the active sensors and the routes to pass sensed data to the base station. The proposed optimal solution is illustrated by a numeric example.

Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm

Abstract—Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference to the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions, or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100% deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is the minimal; 2) the time complexity for computing forwarding nodes is the lowest,

This paper addresses the maximal lifetime scheduling for sensor surveillance systems with K sensors to 1 target. Given a set of sensors and targets in an Euclidean plane, a sensor can watch only one target at a time and a target should be watched by k, k \geq 1, sensors at any time. Our task is to schedule sensors to watch targets and pass data to the base station, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration up to the time when there exists one target that cannot be watched by k sensors or data cannot be forwarded to the base station due to the depletion of energy of the sensor nodes. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques, 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime, and 3) determining the sensor surveillance trees based on the above obtained schedule matrices, which specify the active sensors and the routes to pass sensed data to the base station. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. We illustrate our optimal method by a numeric example and experiments in the end.

This paper addresses the maximal lifetime scheduling problem in sensor surveillance networks. Given a set of sensors and targets in a Euclidean plane, a sensor can watch only one target at a time, our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime; 3) obtaining a target watching timetable for each sensor based on the schedule matrices. Simulations have been conducted to study the complexity of our proposed method and to compare with the performance of a greedy method.

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.