UAV-aided WPSNs (Unmanned Aerial Vehicle aided Wireless Powered Sensor Networks) are promising for the emerging IoT (Internet of Things) applications. In the literature, one UAV is commonly adopted for one WPSN and it wirelessly charges the sensor nodes and collects data from them. In this paper, we address two new issues in UAV-aided WPSN. First, we adopt multiple UAVs for a WPSN in order to support many sensor nodes over a large service area. With multiple UAVs, it is necessary to optimize the locations of the UAVs and the UAV-to-node associations. Second, we utilize the UAVs for three joint functions: (i) wirelessly charging the sensor nodes, (ii) data collection from the sensor nodes, and (iii) data dissemination to the sensor nodes. We formulate an optimization problem to address the above two new issues, where the objective is to maximize the throughput. We prove that this problem is NP-hard and design a heuristic algorithm to tackle it. This algorithm iteratively executes two inter-dependent operations. The first operation optimizes the UAV-to-node associations via load balancing among the UAVs, reducing the data transmission time. The second operation optimizes the UAV locations via Particle Swarm Optimization, reducing the charging time. The simulation results show that: (i) when more UAVs are used, the throughput is significantly increased, and (ii) the proposed algorithm efficiently determines the locations of the UAVs and the UAV-to-node associations for joint charging, data collection and data dissemination.

In cognitive radio networks, when a primary user reclaims his/her frequency band, the secondary users of this band must stop using the channels of this band and attempt to use the other free channels. This process is known as spectrum handoff. The existing studies on spectrum handoff implicitly assume that each channel is assigned to one secondary user at a time. This implicit assumption results in an all-or-none outcome: if a secondary user is assigned a channel in spectrum handoff, he/she could exclusively use this channel; otherwise, he/she must terminate his/her ongoing communication and this phenomenon is known as forced termination. In this paper, we study an alternative approach to avoid forced termination in spectrum handoff. When there are not sufficient channels for the secondary users involved in spectrum handoff, multiple secondary users may be assigned to each available channel and they share this channel via multiple access. As a result, the secondary users would not suffer from forced termination but the per-user data rate is lower. This is a desirable tradeoff because forced termination is more inconvenient and troublesome than lower per-user data rate. We formulate a new spectrum handoff problem in which forced termination is avoided and the objective is to balance the traffic loads in the channels in spectrum handoff. We prove that this problem is NP-hard and design an efficient heuristic algorithm to tackle this problem. We present numerical results to demonstrate that the proposed algorithm is fast and effective.

A dense WiFi uses numerous access points (APs) to provide Internet access to many users in an indoor site (such as concert hall or stadium). To deploy dense WiFi, the existing approach adopts two separate QoS requirements: (i) ensuring a minimum throughput for each station, and (ii) ensuring fault tolerance by withstanding the failure of at most$N$APs where$N$is a given value. We observe that these separate requirements lead to costly dense WiFi because the number of required APs increases by about$N$times. To address this issue, we propose a joint throughput and fault tolerance requirement (or joint requirement) to construct cost-effective dense WiFi. This joint requirement ensures that the throughput of each station is at least$\rho_{i}$when any$i$APs fail, where$\rho_{i}$is a given value and$i=0,1,2,\ldots$. For example, when no AP fails, the per-station throughput is at least$\rho_0 = 5$Mbps; when anyone AP fails, the per-station throughput is at least$l$Mbps; when any two APs fail, the per-station throughput is at least$\rho_{2}=1$Mbps. To realize this joint requirement, we formulate and solve an optimization problem for AP placement and resource allocation. The objective is to minimize the number of APs required while fulfilling the joint requirement. Simulation results demonstrate that the joint requirement offers desirable tradeoff between cost and performance, making dense WiFi more cost-effective.

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.

IEEE 802.11ax is the standard for the new generation WiFi networks. In this paper, we formulate the problem of joint access point (AP) placement and power-channel-resource unit assignment for 802.11ax-based dense WiFi. The objective is to minimize the number of APs. Two quality-of-service (QoS) requirements are to be fulfilled: (1) a two-tier throughput requirement which ensures that the throughput of each station is good enough, and (2) a fault tolerance requirement which ensures that the stations could still use WiFi even when some APs fail. We prove that this problem is NP-hard. To tackle this problem, we first develop an analytic model to derive the throughput of each station under the OFDMA mechanism and a widely used interference model. We then design a heuristic algorithm to find high-quality solutions with polynomial time complexity. Simulation results under both fixed-user and mobile-user cases show that: (1) when the area is small (50 × 50$\rm m^2$), our algorithm gives the optimal solutions; when the area is larger (80 × 60$\rm m^2$), our algorithm can reduce the number of APs by 34.9-87.7% as compared to the Random and Greedy algorithms. (2) Our algorithm can always get feasible solutions that fulfill the QoS requirements.

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.

Fingerprint is one of the representative methods for wireless indoor localization. It uses a fingerprint database (measured in the offline phase) and the current received signal strengths (RSSs) (measured by the user's device in the online phase) to determine the location of this device. However, the RSSs and hence the localization accuracy would be affected by time-varying environmental factors (e.g., number of people in a shopping mall). In this paper, we propose a new method for wireless localization in time-varying indoor environments. In the offline phase, the proposed method measures extra information: it measures E fingerprint databases for E respective environmental conditions, where E is a design parameter (e.g., E=2 for the peak period and the non-peak period in a shopping mall). In the online phase, it leverages the extra information for better localization in time-varying indoor environment, even when the current environmental condition is different from the ones considered in the offline phase. The proposed method is particularly suitable for the indoor venues for which their primary concern is to provide good quality localization services while they could afford a moderate amount of extra resources for one-off measurement in the offline phase (e.g., exhibition centers, airports, shopping malls, etc.). We conduct a simulation experiment and a real-world experiment to demonstrate that the proposed method gives accurate localization.

IEEE 802.11ax is a promising standard for the next-generation WiFi network, which uses orthogonal frequency division multiple access (OFDMA) to segregate the wireless spectrum into time-frequency resource units (RUs). In this paper, we aim at designing an 802.11ax-based dense WiFi network to provide WiFi services to a large number of users within a given area with the following objectives: (1) to minimize the number of access points (APs); (2) to fulfil the users' throughput requirement; and (3) to be resistant to AP failures. We formulate the above into a joint AP placement and power-channel-RU assignment optimization problem, which is NP-hard. To tackle this problem, we first derive an analytical model to estimate each user's throughput under the mechanism of OFDMA and a widely used interference model. We then design a heuristic algorithm to find high-quality solutions with polynomial time complexity. Simulation results show that our algorithm can achieve the optimal performance for a small area of 50×50 m2. For a larger area of 100×80 m2where we cannot find the optimal solution through an exhaustive search, our algorithm can reduce the number of APs by 32 ~ 55% as compared to the random and Greedy solutions.

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.

An N×M lightpath concentrator is an optical component for concentrating lightpaths from N incoming fibers to M outgoing fibers where N>M. In this paper, we propose a novel design of lightpath concentrators that gives significantly better performance-complexity tradeoff than the existing design. The proposed design uses 2×2 switch elements to form rings which connect the inputs to the outputs. The incoming lightpaths are circulated along these rings in order to reach the available outputs. We demonstrate that: i) the proposed design gives significantly smaller blocking probability than the existing design when both designs have about the same complexity, and ii) the proposed design has significantly smaller complexity than the existing design when both designs have about the same blocking probability.

Calibrators and sniffers have been used in the literature to proactively update the functional relationship between the received signal strength and the distance for wireless localization in time-varying indoor venue, where calibrators and sniffers are Wi-Fi transmitters and Wi-Fi receivers respectively. To be effective, these devices should be suitably placed in the indoor venue. Let there be N calibrators and M sniffers, di,jbe the distance between calibrator i and sniffer j, and RSSi,jbe the received signal strength measured by sniffer j from calibrator i. The points (d1,1, RSS1,1), (d1,2, RSS1,2), ..., (dN,M, RSSN,M) are used to estimate the functional relationship between the received signal strength and the distance. It is desirable that d1,1, d1,2, ..., dN,Mare uniformly scattered so that the estimated functional relationship is more accurate for better localization. In this paper, we propose to minimize the discrepancy of d1,1, d1,2, ..., dN,Min order to determine the optimal locations of the N calibrators and the M sniffers. We formulate this new problem (named minimal discrepancy placement problem) and design an efficient optimization method to solve it. We conduct simulation and real-world experiments to demonstrate that minimal discrepancy placement can effectively improve localization accuracy.

Many indoor localization systems rely on a set of reference anchors with known positions. A target's location is estimated from a set of distances between the target and its surrounding anchors, and hence the selection of anchors affects the localization accuracy. However, it remains a challenge to select the best set of anchors. In this paper, we study how to appropriately make use of the surrounding anchors for localizing a target. We first construct different candidate anchor clusters by selecting different number of anchors with the strongest received signals. Then for each candidate cluster, we propose a weighted min-max algorithm to provide a location estimation. Finally, we introduce a weighted geometric dilution of precision (w-GDOP) algorithm that combines the estimations from multiple clusters by quantifying their estimation accuracy. We evaluate the performance of our solution through simulations and real-world experiments. Our results show that the proposed anchor selection scheme and localization algorithm significantly improve the localization accuracy in large indoor environments.

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.

Recently, erasure coding has been extensively deployed in large-scale storage systems to replace data replication. With the increase in disk I/O throughput and network bandwidth, the performance of erasure coding becomes a major bottleneck of erasure-coded storage systems. In this paper, we propose a graphics processing unit (GPU)-based implementation of erasure coding named G-CRS, which employs the Cauchy Reed-Solomon (CRS) code, to overcome the aforementioned bottleneck. To maximize the coding performance of G-CRS, we designed and implemented a set of optimization strategies, such as a compact structure to store thebitmatrixin GPU constant memory, efficient data access through shared memory, and decoding parallelism, to fully utilize the GPU resources. In addition, we derived a simple yet accurate performance model to demonstrate the maximum coding performance of G-CRS on GPU. We evaluated the performance of G-CRS through extensive experiments on modern GPU architectures such as Maxwell and Pascal, and compared with other state-of-the-art coding libraries. The evaluation results revealed that the throughput of G-CRS was 10 times faster than most of the other coding libraries. Moreover, G-CRS outperformed PErasure (a recently developed, well optimized CRS coding library on the GPU) by up to 3 times in the same architecture.

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.

Technology of autonomous vehicles (AVs) is becoming mature, and many AVs will appear on roads in the near future. AVs become connected with the support of various vehicular communication technologies, and they possess a high degree of control to respond to instantaneous situations cooperatively with high efficiency and flexibility. In this paper, we propose a new public transportation system based on AVs. It manages a fleet of AVs to accommodate transportation requests, offering point-to-point services with ride sharing. We focus on the two major problems of the system: scheduling and admission control. The former is to configure the most economical schedules and routes for the AVs to satisfy the admissible requests, whereas the latter is to determine the set of admissible requests among all requests to produce maximum profit. The scheduling problem is formulated as a mixed-integer linear program, and the admission control problem is cast as a bilevel optimization, which embeds the scheduling problem as the major constraint. By utilizing the analytical properties of the problem, we develop an effective genetic-algorithm-based method to tackle the admission control problem. We validate the performance of the algorithm with real-world transportation service data.

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.

Many shopping malls provide free parking service to attract customers because car owners usually have high spending power. Typically a customer is entitled to free parking after spending a certain amount in the shopping mall and he redeems free parking by presenting the sales receipts to a staff in a service counter. The staff manually processes these sales receipts (e.g., checks the date and calculates the total amount of spending) and redeems the corresponding number of free parking hours to the customer. In this project, we apply QR code and digital signature to automate the process of redeeming free parking in shopping malls. This brings convenience to the customers and cost saving to the shopping malls.

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.

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.

We consider an Internet telephony system in which the service provider operates a telephone gateway in each servicing city to serve the general public. We propose a packet loss recovery system, called lightweight piggybacking, for this system. This scheme applies two stages of erasure coding and fragmentation, such that only a small redundancy is piggybacked to each voice packet while this redundancy can be shared by multiple voice streams to a large extent for effective packet loss recovery. Compared with the conventional piggybacking scheme, the lightweight piggybacking scheme can effectively: (i) increase the probability of recovering the lost packets using the same or smaller amount of redundancy, and (ii) recover the loss of multiple and consecutive packets.

A video-on-demand (VOD) system provides an electronic video rental service to geographically distributed users. It can adopt multiple servers to serve many users concurrently. As a VOD system is being used and evolved, its servers probably become heterogeneous. For example, if a new server is added to expand the VOD system or replace a failed server, the new server may be faster with a larger storage size. This paper investigates how to assign movies to heterogeneous servers in order to minimize the blocking probability. It is proven that this assignment problem is NP-hard, and a lower bound is derived on the minimal blocking probability. The following approach is proposed for assignment: 1) problem relaxation-a relaxed assignment problem is formulated and solved to determine the ideal load that each server should handle, and 2) goal programming-an assignment and reassignment are performed iteratively while fulfilling all the constraints so that the load handled by each server is close to the ideal one. This approach is generic and applicable to many assignment problems. This approach is adopted to design two specific algorithms for movie assignment with and without replication. It is demonstrated that these algorithms can find optimal or close-to-optimal assignments.

Cable TV service providers must manage encryption/decryption keys to ensure that only authorized set-top boxes can decrypt pay-TV channels; ITU have recommended a key management scheme for this purpose. Nevertheless, some crackers crack and reproduce set-top boxes for profit, and many people use the pirated set-top boxes to decrypt and watch pay-TV channels without paying a subscription fee. We enhance the key management scheme to protect the service provider's revenue against piracy. Using the enhanced scheme, even if a cracker could crack and reproduce set-top boxes, the pirated set-top boxes are only applicable in a small geographical region (i.e., they have limited spatial applicability) and they cannot function within one charging period (i.e., they have limited temporal applicability).

A possibilistic approach was proposed in a previous paper for C-means clustering, and two algorithms realizing this approach were reported in two previous papers. Although the possibilistic approach is sound, these two algorithms tend to find identical clusters. In this paper, we modify and improve these algorithms to overcome their shortcoming. The numerical results demonstrate that the improved algorithms can determine proper clusters and they can realize the advantages of the possibilistic approach.

We design an interactive video-on-demand (VOD) system using both the client-server paradigm and broadcast delivery paradigm. Between the VOD warehouse and customers, we adopt a client-server paradigm to provide an interactive service. Within the VOD warehouse, we adopt a broadcast delivery paradigm to support many concurrent customers. In particular, we exploit the enormous bandwidth of optical fibers for broadcast delivery, so that the system can provide many video programs and maintain a small access delay. In addition, we design and adopt an interleaved broadcast delivery scheme, so that every video stream only requires a small buffer size for temporary storage. A simple proxy is allocated to each ongoing customer, and it retrieves video from optical channels and delivers video to the customer through an information network. The proposed VOD system is suitable for large scale applications with many customers, and has several desirable features: 1) it can be scaled up to serve more concurrent customers and provide more video programs, 2) it provides interactive operations, 3) it only requires point-to-point communication between the VOD warehouse and the customer and involves no network control, 4) it has a small access delay, and 5) it requires a small buffer size for each video stream.

A multiobjective programming algorithm may find multiple nondominated solutions. If these solutions are scattered more uniformly over the Pareto frontier in the objective space, they are more different choices and so their quality is better. In this paper, we propose a quality measure called U-measure to measure the uniformity of a given set of nondominated solutions over the Pareto frontier. This frontier is a nonlinear hyper-surface. We measure the uniformity over this hyper-surface in three main steps: 1) determine the domains of the Pareto frontier over which uniformity is measured, 2) determine the nearest neighbors of each solution in the objective space, and 3) compute the discrepancy among the distances between nearest neighbors. The U-measure is equal to this discrepancy where a smaller discrepancy indicates a better uniformity. We can apply the U-measure to complement the other quality measures so that we can evaluate and compare multiobjective programming algorithms from different perspectives.

In many applications of C-means clustering, the given data set often contains noisy points. These noisy points will affect the resulting clusters, especially if they are far away from the data points. In this paper, we develop a pruning approach for robust C-means clustering. This approach identifies and prunes the outliers based on the sizes and shapes of the clusters so that the resulting clusters are least affected by the outliers. The pruning approach is general, and it can improve the robustness of many existing C-means clustering methods. In particular, we apply the pruning approach to improve the robustness of hard C-means clustering, fuzzy C-means clustering, and deterministic-annealing C-means clustering. As a result, we obtain three clustering algorithms that are the robust versions of the existing ones. In addition, we integrate the pruning approach with the fuzzy approach and the possibilistic approach to design two new algorithms for robust C-means clustering. The numerical results demonstrate that the pruning approach can achieve good robustness.

It is cost-effective to install multiple fibers in each link of an all-optical network, because the cost of fibers is relatively low compared with the installation cost. The resulting network can provide a large capacity for good quality of service, future growth, and fault tolerance. If a node has more incoming/outgoing fibers, it requires larger optical switches. Using the current photonic technology, it is difficult to realize large optical switches. Even if they can be realized, they are expensive. To overcome this problem, we design a node configuration for all-optical networks. We exploit the flexibility that, to establish a lightpath across a node, we can select any one of the available channels in the incoming link and any one of the available channels in the outgoing link. As a result, the proposed node configuration requires significantly smaller optical switches while it can result in nearly the same blocking probability as the existing one. We demonstrate that a good network design is to adopt the proposed node configuration and slightly more fibers in each link, so that the network requires small optical switches while it has a small blocking probability.

We design and optimize the physical topology of all-optical networks. This problem is more challenging than the traditional one for electronic communication networks, because of the wavelength-continuous constraint and it involves routing and wavelength assignment. In this problem, we are given the number of lightpaths required by every node pair and a cost specification, and our objective is to determine a physical topology of minimal cost. We formulate the problem, prove that it is NP-hard, and design an efficient algorithm called two-stage cut saturation algorithm for it. In the first stage, we relax the wavelength-continuous constraint and apply the main idea of the cut saturation method to determine a good initial network. In the second stage, we impose the wavelength-continuous constraint and perform routing and wavelength assignment to establish the specified lightpaths on the initial network. When some lightpaths cannot be established, we apply the main idea of the cut saturation method to optimize the insertion of additional links into the network. Simulation results show the following: (1) the proposed algorithm can efficiently design networks with low costs and high utilization and (2) if wavelength converters are available to support full wavelength conversion, the total cost of the links can be significantly reduced.

We design a genetic algorithm called the orthogonal genetic algorithm with quantization for global numerical optimization with continuous variables. Our objective is to apply methods of experimental design to enhance the genetic algorithm, so that the resulting algorithm can be more robust and statistically sound. A quantization technique is proposed to complement an experimental design method called orthogonal design. We apply the resulting methodology to generate an initial population of points that are scattered uniformly over the feasible solution space, so that the algorithm can evenly scan the feasible solution space once to locate good points for further exploration in subsequent iterations. In addition, we apply the quantization technique and orthogonal design to tailor a new crossover operator, such that this crossover operator can generate a small, but representative sample of points as the potential offspring. We execute the proposed algorithm to solve 15 benchmark problems with 30 or 100 dimensions and very large numbers of local minima. The results show that the proposed algorithm can find optimal or close-to-optimal solutions.

Multipoint videoconference service allows multiple and far-away conferees to conduct a meeting without leaving their offices. Variable-bit-rate video compression is attractive for videoconferencing, because it can provide a constant image quality and it can effectively utilize the communication bandwidth via statistical multiplexing. When some conferences temporarily generate heavy traffic to a link, congestion occurs and some video packets have to be discarded. Since the packets of different conferences are multicast to different number of conferees, the loss of different packet will affect different number of people. If we discard the packets sent to the smallest number of conferees, we can minimize the number of affected conferees to give the best mean quality of service, but the conference having a smaller number of conferees will suffer from a poorer quality of service. Therefore, we must consider both the mean quality of service and fairness in congestion control. We propose a congestion-control strategy for multipoint videoconferencing. This strategy has a control parameter which we can tune to make a tradeoff between the mean quality of service and fairness. In addition, the strategy only involves some simple arithmetic and logic operations, and hence, it can be executed quickly for real-time congestion control.

Principal component analysis (PCA) and minor component analysis (MCA) are a powerful methodology for a wide variety of applications such as pattern recognition and signal processing. In this paper, we first propose a differential equation for the generalized eigenvalue problem.We prove that the stable points of this differential equation are the eigenvectors corresponding to the largest eigenvalue. Based on this generalized differential equation, a class of PCA and MCA learning algorithms can be obtained. We demonstrate that many existing PCA and MCA learning algorithms are special cases of this class, and this class includes some new and simpler MCA learning algorithms. Our results show that all the learning algorithms of this class have the same order of convergence speed, and they are robust to implementation error.

Principal component analysis (PCA) and minor component analysis (MCA) are a powerful methodology for a wide variety of applications such as pattern recognition and signal processing. In this paper, we first propose a differential equation for the generalized eigenvalue problem. We prove that the stable points of this differential equation are the eigenvectors corresponding to the largest eigenvalue. Based on this generalized differential equation, a class of PCA and MCA learning algorithms can be obtained. We demonstrate that many existing PCA and MCA learning algorithms are special cases of this class, and this class includes some new and simpler MCA learning algorithms. Our results show that all the learning algorithms of this class have the same order of convergence speed, and they are robust to implementation error.

The notion of Pareto-optimality is one of the major approaches to multiobjective programming. While it is desirable to find more Pareto-optimal solutions, it is also desirable to find the ones scattered uniformly over the Pareto frontier in order to provide a variety of compromise solutions to the decision maker. We design a genetic algorithm for this purpose. We compose multiple fitness functions to guide the search, where each fitness function is equal to a weighted sum of the normalized objective functions and we apply an experimental design method called uniform design to select the weights. As a result, the search directions guided by these fitness functions are scattered uniformly toward the Pareto frontier in the objective space. With multiple fitness functions, we design a selection scheme to maintain a good and diverse population. In addition, we apply the uniform design to generate a good initial population and design a new crossover operator for searching the Pareto-optimal solutions. The numerical results demonstrate that the proposed algorithm can find the Pareto-optimal solutions scattered uniformly over the Pareto frontier.

Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near optimal solutions within moderate numbers of generations.

In an all-optical wide area network, some network nodes may handle heavier volumes of traffic. It is desirable to allocate more full-range wavelength converters (FWCs) to these nodes, so that the FWCs can be fully utilized to resolve wavelength conflict. We propose a set of algorithms for allocating FWCs in all-optical networks. We adopt the simulation-based optimization approach, in which we collect utilization statistics of FWCs from computer simulations and then perform optimization to allocate the FWCs. Therefore, our algorithms are widely applicable and they are not restricted to any particular model or assumption. We have conducted extensive computer simulations on regular and irregular networks under both uniform and nonuniform traffic. Compared with the best existing allocation, the results show that our algorithms can significantly reduce: (1) the overall blocking probability (i.e., better mean quality of service) and (2) the maximum of the blocking probabilities experienced at all the source nodes (i.e., better fairness). Equivalently, for a given performance requirement on blocking probability, our algorithms can significantly reduce the number of FWCs required.

We consider an online string matching problem in which we find all the occurrences of a pattern of m characters in a text of n characters, where all the characters of the pattern are available before processing, while the characters of the text are input one after the other. We propose a space-time optimal parallel algorithm for this problem using a neural network approach, This algorithm uses m McCulloch-Pitts neurons connected as a linear array. It processes every input character of the text in one step and hence it requires at most n iteration steps.

Consider the problem of assigning N software versions of a multiversion software to M processors for execution. When a processor completes executing a software version, it sends the output to a voter immediately. The voter executes a voting strategy to estimate the correct output. When it has made a sufficiently reliable estimation (e.g., it has received [(N/2)] identical outputs under majority voting), it accepts this estimated output and terminates the execution of all the unfinished versions. Therefore, some software versions may not be executed to completion. In this paper, we analyze the mean time to reach correct consensus for four voting strategies. To minimize the mean time to reach correct consensus, we show that the processor assignment problem is NP-hard and we propose a heuristic to find suboptimal assignments. When two or more versions are assigned to a processor, these versions are executed one after the other and we derive the optimal execution sequence for them.

In wireless networks, portable terminals are usually powered by battery, and they communicate through the free-space spectrum. Therefore, both the transmission power and bandwidth are scarce resources. Artificial power capture is a simple and effective method to exploit the transmission bandwidth to give a higher throughput, but it may consume a larger mean transmission power because some packets are transmitted at higher power. In this paper, we analyze the mean power consumption of artificial power capture, and formulate two capture control problems which regulate the mean power consumption and the throughput. The analysis reveals that, although some packets are transmitted at higher power, artificial power capture has a smaller mean power consumption than the case without capture when the traffic is sufficiently heavy. This is because artificial power capture can significantly increase the probability of successful transmission at heavy traffic, and hence the mean power consumed for successfully transmitting a packet is smaller.

A new packet switch architecture using two sets of time-division multiplexed buses is proposed. The horizontal buses collect packets from the input links, while the vertical buses distribute the packets to the output links. The two sets of buses are connected by a set of switching elements which coordinate the connections between the horizontal buses and the vertical buses so that each vertical bus is connected to only one horizontal bus at a time. The switch has the advantages of: (1) adding input and output links without increasing the bus and I/O adaptor speed; (2) being internally unbuffered; (3) having a very simple control circuit; and (4) having 100% throughput under uniform traffic. A combined analytical-simulation method is used to obtain the packet delay and packet loss probability. Numerical results show that for satisfactory performance, the buses need to run about 30% faster than the input line rate. With this speedup, even at a utilization factor of 0.9, each input adaptor requires only 31 buffers for a packet loss rate of 10/sup -6/. The output queue behaves essentially as an M/D/1 queue.

A distributed power control algorithm for cellular networks is proposed. This algorithm includes the distributive balancing (DB) algorithm (Zander 1992) and the distributed power control (DPC) algorithm (Grandhi et al. 1994) as special cases. We show that this algorithm converges much faster than the DB and DPC algorithms, is less sensitive to measurement error than the DPC algorithm, and its convergence rate and sensitivity to measurement error can be tuned by varying a design parameter.

The throughput of a time-multiplex switch can be maximized by resolving transmission conflict such that the maximum number of packets are switched in each slot. We propose an upper-bound and a lower-bound for the maximum throughput of time-multiplex switches. These bounds are given in closed-form expressions, they are very tight, and they are significantly tighter than the bounds proposed by Mehmet-Ali, Youssefi and Nguyen (see ibid., vol.42, no.12, p.3189, 1994).

When a Banyan switch is used to switch variable bit rate (VBR) video, some video packets may not be switched before their deadlines because the VBR video sources may temporarily generate heavy traffic or they only generate moderate traffic but some video packets encounter internal blocking in the switch. Therefore, some video packets may be discarded. We determine the condition of packet loss and then derive the packet loss probability. Based on this result, we perform admission control to determine whether a given video session can be admitted while the resulting packet loss probability is still small enough to guarantee a good image quality.

To ensure the quality of a multimedia teleconference, it is essential that sufficient bandwidth be allocated for its use. In this paper a conference traffic model is formulated and link level and conference level congestion measures are derived. Motivated by the advantages of sharing transmission resources in TASI related voice communication systems, an analogous transmission policy for conference videos is proposed. The quantification of conference traffic also enables us to set an admission policy so that the network can accommodate as many conferences as possible without violating conference quality constraints.>

The one-unit Oja algorithm plays a very important role in the study of principal component analysis neural networks. In this paper, we propose an energy function whose steepest descent direction (i.e., negative gradient direction) is the same as the average evolution direction of the one-unit Oja algorithm, and the energy function has two global minimal points corresponding to the two converged points of the one-unit Oja algorithm and it has no other local minimal points.

In an N/spl times/N time-multiplex switch, transmission conflict arises when two or more input adaptors transmit packets to the same output adaptor simultaneously. To resolve transmission conflict, we propose two neural-based scheduling algorithms which use a large number of simple processing elements to perform scheduling in parallel. The first algorithm uses N/sup 2/ hysteresis McCulloch-Pitts (1943) neurons to determine conflict-free transmission schedules with maximum throughput. The second algorithm resolves transmission conflict among the first M packets in each input queue. It determines suboptimal transmission schedules using only NM neurons (M>

A modular architecture is proposed for distributing broadcast and switched video. The architecture consists of a set of concentration buses (or input buses), a TDM-based bus matrix and a set of distribution buses (or output buses). The transmission time in each output bus is divided into fixed size frames. Dedicated time slots in a frame are reserved for broadcast video. The remaining time slots are allocated to switched video on a first-come-first-served basis. Videos are switched via time slot assignments which determine the connections within the bus matrix. Two slot assignment algorithms are designed, one for point-to-point transmissions and the other for point-to-multipoint transmissions. The advantages of this architecture include: (1) accommodation of multirate video, (2) support of video broadcasting and multicasting, and (3) modular growth at distributed locations.>

ShuffleNet is one of the many architectures proposed for multihop lightwave networks. Its advantages include low mean-internodal distance and simple routing. Modular growth of ShuffleNets, however, is generally difficult and requires many hardware and software reconfigurations. The authors consider a multistar implementation of ShuffleNet and discuss how a (p,k) ShuffleNet can be expanded to a (p,k+1) ShuffleNet in modular phases, where each phase increases the number of nodes by only a small fraction and requires only minor hardware and software reconfigurations.>

A novel packet switch architecture using two sets of time division multiplexed (TDM) buses is proposed. The horizontal buses collect packets from the input ports while the vertical buses distribute the packets to the output ports. The two sets of buses are connected by a set of switching elements which coordinate the connections between the horizontal buses and the vertical buses so that each vertical bus is connected to only one horizontal bus at a time. The switch has the advantages of: (1) it adds input and output ports without increasing the bus and I/O adaptor speed; (2) it is internally unbuffered; (3) it has a very simple control circuit; and (4) it has 100% potential throughput under uniform traffic. A combined analytical-simulation method is used to obtain the packet delay and packet loss probability. Numerical results show that for satisfactory performance the buses need to run about 30% faster than the input line rate. With this speedup, even at a utilization factor of 0.9, the input queue can give a packet loss of 10/sup -6/ with only 31 buffers per input adaptor. The output queue behaves essentially as an M/D/1 queue.>