Alzheimer’s Disease (AD) affects over 55 million people globally, yet the key genetic contributors remain poorly understood. Leveraging recent advancements in genomic foundation models, we present the innovative Reverse-Gene-Finder technology, a ground-breaking neuron-to-gene-token backtracking approach in a neural network architecture to elucidate the novel causal genetic biomarkers driving AD onset. Reverse-Gene-Finder comprises three key innovations. Firstly, we exploit the observation that genes with the highest probability of causing AD, defined as the most causal genes (MCGs), must have the highest probability of activating those neurons with the highest probability of causing AD, defined as the most causal neurons (MCNs). Secondly, we utilize a gene token representation at the input layer to allow each gene (known or novel to AD) to be represented as a discrete and unique entity in the input space. Lastly, in contrast to the existing neural network architectures, which track neuron activations from the input layer to the output layer in a feed-forward manner, we develop an innovative backtracking method to track backwards from the MCNs to the input layer, identifying the Most Causal Tokens (MCTs) and the corresponding MCGs. Reverse-Gene-Finder is highly interpretable, generalizable, and adaptable, providing a promising avenue for application in other disease scenarios.

Alzheimer’s Disease (AD) is an irreversible neurodegenerative disease affecting 50 million people worldwide. Low-cost, accurate identification of key markers of AD is crucial for timely diagnosis and intervention. Language impairment is one of the earliest signs of cognitive decline, which can be used to discriminate AD patients from normal control (NC) individuals. Patient-interviewer dialogues may be used to detect such impairments, but they are often mixed with ambiguous, noisy, and irrelevant information, making the AD detection task difficult. Moreover, the limited availability of AD speech samples and variability in their speech styles pose significant challenges in developing robust speech-based AD detection models. To address these challenges, we propose DECT, a novel speech-based domain-specific approach leveraging large language models (LLMs) for fine-grained linguistic analysis and label-switched label-preserved (LSLP) data generation. Our study presents four novelties: (1) We harness the summarizing capabilities of LLMs to identify and distill key Cognitive-Linguistic (CL) information (atoms) from noisy speech transcripts, effectively filtering irrelevant information. (2) We leverage the inherent linguistic knowledge of LLMs to extract linguistic markers from unstructured and heterogeneous audio transcripts. (3) We exploit the compositional ability of LLMs to generate LSLP AD speech transcripts consisting of diverse linguistic patterns to overcome the speech data scarcity challenge and enhance the robustness of AD detection models. (4) We use the augmented AD textual speech transcript dataset and a more fine-grained representation of AD textual speech transcript data to fine-tune the AD detection model. The results have shown that DECT, an integrated, LLM-assisted, speech-based AD detection model demonstrates superior model performance with an 11% improvement in AD detection accuracy on the datasets from DementiaBank compared to the baselines.

Accurate and comprehensive air pollution data is essential for understanding and addressing environmental challenges. Missing data can impair accurate analysis and decision-making. This study presents a novel approach, named CNN-Transformer-based Spatial-Temporal Data Imputation (CTDI), for imputing missing air pollution data. Data pre-processing incorporates observed air pollution data and related urban data to produce 24-hour period tensors as input samples. 1-by-1 CNN layers capture the interaction between different types of input data. Deep learning transformer architecture is employed in a spatial-temporal (S-T) transformer module to capture long-range dependencies and extract complex relationships in both spatial and temporal dimensions. Hong Kong air pollution data is statistically analyzed and used to evaluate CTDI in its recovery of generated and actual patterns of missing data. Experimental results show that CTDI consistently outperforms existing imputation methods across all evaluated scenarios, including cases with higher rates of missing data, thereby demonstrating its robustness and effectiveness in enhancing air quality monitoring. Additionally, ablation experiments reveal that each component significantly contributes to the model's performance, with the temporal transformer proving particularly crucial under varying rates of missing data.

Timely and high-density air quality monitoring is essential for the development of future smart cities. The images captured from widely deployed stationary-cameras can be transferred quickly via the Internet of Things (IoT) to facilitate ambient pollution estimation anytime anywhere. Image-based air pollution estimation is normally formulated as a supervised learning problem, relying on an extended number of image samples. However, individual stationary-cameras can offer only very limited samples and scenes, while locally trained estimation models can easily overfit. A global method was proposed to address this challenge. The global model was trained via images captured from different cameras. However, such a model is less effective in extracting local features from scenes. A personalized method is therefore proposed to improve not only the generalization of the estimation model but also to preserve the local characteristics of individual cameras. Our personalized method consists of a two-stage architecture: 1) images from different cameras are used to train the global estimation model to avoid overfitting due to fixed scenes and small sample size and 2) the global model is further refined by images captured from individual cameras separately for adapting local characteristics. To evaluate our proposed personalized method, a large data set was constructed, based on stationary-camera-taken images captured in Hong Kong, consisting of different pollution measurements, including PM2.5, PM10, NO2, and O3. As compared to the local model, our proposed personalized model has reduced average MAE by 5.68% and average SMAPE by 6.82%, and improved average$r$by 4.69%.

Facial emotions are expressed through a combination of facial muscle movements, namely, the Facial Action Units (FAUs). FAU intensity estimation aims to estimate the intensity of a set of structurally dependent FAUs. Contrary to the existing works that focus on improving FAU intensity estimation performance, this study investigates how knowledge distillation (KD) incorporated into a training model can improve FAU intensity estimation efficiency while achieving the comparable level of performance. Given the intrinsic structural characteristics of FAU, it is desirable to distill deep structural relationships, namely, DSR-FAU, using heatmap regression. Our methodology is as follows: First, a feature map-level distillation loss is applied to ensure that the student network and the teacher network share similar feature distributions. Second, the region-wise and channel-wise relationship distillation loss functions are introduced to penalize the difference in structural relationships. Specifically, the region-wise relationship can be represented by the structural correlations across the facial features, whereas the channel-wise relationship is represented by the implicit FAU co-occurrence dependencies. Third, we compare the model performance of DSR-FAU with the state-of-the-art models, based on two benchmarking datasets. It is shown that our model achieves comparable performance, with a lower number of model parameters and lower computation complexities.

Due to equipment and transmission failures, data loss presents a key challenge to air quality monitoring. This paper attempts to recover missing air quality data from an air quality database. Leveraging adaptive updating convolutional neural networks (CNNs), we propose a novel Long-short term context encoder (ILSCE) model, which can simultaneously capture any temporal-spatial correlation and periodic variation identified from an air quality dataset. In addition, our model applies a new mechanism to automatically update both the air quality data and their corresponding masks in every single layer of CNN. Our proposed method presents three novelties. First, it hierarchically recovers any missing air quality values. Second, domain specific weekday/weekend and seasonal information are incorporated into the training model. Third, model performance is enhanced by an additional regularization term that captures the correlation between different air pollutants, thereby considering both background ambient pollution and local emissions. Our experimental study shows these three newly proposed features allow the ILSCE model to significantly outperform existing state-of-the-art imputation methods in air pollution data recovery. Furthermore, as data loss becomes more severe, with more missing data and more consecutively missing data, the superior recovery performance and greater robustness of our model become more prominent.

Missing data pattern identification and recovery (MDIR) is vital for accurate air pollution monitoring. To recover the missing air pollution data, GCN-ST-MDIR, a Graph Convolutional Network (GCN)-based MDIR framework, is proposed to identify daily missing data patterns and automatically select the best recovery method. GCN-ST-MDIR presents four novelties: (1) A new graph construction is developed to improve GCN data representation for MDIR using S-T similarity matrix and domain-specific knowledge (e.g., weekend/weekday). (2) A TL component is used to pre-train LSCE and ILSCE models. (3) A GCN structure outputs a selection indicator to determine the dominant missing pattern for daily input. The pre-trained data recovery model's accuracy is incorporated into the GCN loss function to penalize the wrong indicator. (4) The output of the GCN structure is used as a score to combine LSCE and ILSCE. Results show that the domain-specific S-T regularity and irregularity can be used as the prior information for both GCN and ILSCE/LSCE to enhance feature extraction. Our model considerably improves the recovery performance as compared to the baselines. GCN-ST-MDIR has achieved an accuracy of 88.48% for general missing data recovery with consecutively and sporadically missing data. GCN-ST-MDIR can be extended to many other S-T MDIR challenges.

Intersections are prone to congestion in urban areas and making competent speed plans for vehicles to efficiently utilize green time resources is significant for congestion alleviation and driving experience improvement. The key is to increase the chance of going through green lights and avoid idling at red lights. Existing works for velocity planning fail to fully consider various realistic traffic conditions, such as interfering traffic, free lane switch, and group efficiency, thus compromising effectiveness and limiting feasibility. To address all the aforementioned issues, we propose a novel method DeepGAL for vehicle control by dividing vehicles into groups, assigning a leader in each group and delivering intelligent control on leaders with deep reinforcement learning. Extensive experiments are conducted based on two real-world datasets with distinct traffic flow rates in Hangzhou, China, and the results demonstrate that DeepGAL achieves outstanding improvement over various performance metrics applied in five classic car following models considering realistic traffic conditions. Moreover, DeepGAL outperforms four state-of-the-art baseline methods over various metrics under both light and heavy real-world traffic flows. The test of DeepGAL with indeterministic traffic-signal phase and timing (SPAT) information under an adaptive traffic signal control indicates its effectiveness even with partial SPAT information. In addition, considering the practical issue that only some of the vehicles can be controlled by our scheme, we conduct simulations on different penetration levels of controlled leader vehicles, which demonstrate that even with only 10% penetration, DeepGAL can notably alleviate congestion and enhance driving experience at intersections, validating its great feasibility.

Facial expression recognition (FER) is crucial for social communication. However, current studies present limitations when addressing facial expression difference due to demographic variation, such as race, gender, and age, etc. In this article, we first propose a deeply-supervised attention network (DSAN) to recognize human emotions based on facial images automatically. Based on DSAN, a two-stage training scheme is designed, taking full advantage of the race/gender/age-related information. In our DSAN framework, multi-scale features are leveraged to capture more discriminative information from the deep layers to the shallow layers. Furthermore, we adopt the attention block to highlight the essential local facial characteristics; it performs well when it is incorporated into the deeply-supervised framework. Finally, we combine the complementary characteristics of multiple convolutional layers in deeply-supervised manner and ensemble the intermediate predicted scores. Our experimental results have shown that our proposed framework can (i) effectively integrate demographic information in improving the performance of a variety of FER tasks, (ii) learn informative feature representations with a visual explanation by capturing the regions of interests (ROI), (iii) achieve superior performance for both the posed and the spontaneous FER databases, each containing pictures of human facial expressions varied in gender, age or race.

Predicting air pollution concentration is crucial and beneficial for public health. This study proposes a domain-specific Bayesian deep-learning model for long-term air pollution forecast in China and the United Kingdom. Our proposed model carries three novelties: First, a domain-specific knowledge is integrated to take into account the strong statistical relationship between PM$_{2.5}$and PM$_{10}$as a regularization term; Second, an attention layer is included to capture the influential historical feature and the recursive temporal correlation of air quality data; Third, results generated from different multi-step forecast strategies are combined based on corresponding uncertainty measures to improve our model’s performance. Our model outperforms other baseline models. Results show that incorporating Bayesian and domain-specific knowledge into the deep learning model can reduce the prediction errors by a maximum of 3.7% and 12.4%, for Beijing and London, respectively. Specifically, incorporating domain-specific knowledge into the Bayesian deep-learning model reduces prediction errors whilst the integration of Bayesian techniques allows the fusion of different forecast strategies to improve prediction accuracy. In future, additional influential domain-specific features can be added to further improve our deep-learning model’s prediction accuracy and interpretability.

Air pollution has become a global challenge, and obtaining real-time air quality information is urgently needed. Although the governments have been trying their best in delivering accurate air quality reports, missing air pollution data remains a key challenge. Based on the temporal-spatial correlation of the data, we propose a novel long-short term context encoder (LSCE) structure for recovering missing air pollution data. The original context encoder approach based on image completion focuses on reconstructing rectangular missing regions. Differing from traditional methods, our fully convolutional neural network architecture enjoys the following novelties. First, LSCE can recover irregular missing data patterns. Second, we devise two data pre-processing strategies to produce two types of context encoders, namely, the long-short term cutting context encoder (LSCCE) and the long-short term sliding context encoder (LSSCE). Compared with LSCCE, LSSCE increases the number of training data matrixes. Finally, we investigate the significance of adaptive training in addressing different types of missing data. Our simulation results have demonstrated that our approach, especially, LSSCE, can outperform existing missing data recovery methods. Besides, our techniques can be widely applicable for recovering other temporally and spatially correlated missing data, such as vehicular traffic or meteorology data.

For the emergency response, every second counts. Intersections are prone to congestion, which greatly hinders the fast response of emergency vehicles. Although emergency vehicles possess the privilege to run a red light, it can be unsafe, and a congested intersection will prevent the exercise of this privilege. When an emergency vehicle arrives, the greedy preemption scheme offers a green signal promptly until it leaves the intersection. This guarantees a fast emergency response in most cases. However, this scheme will lead to an adverse impact on vehicles of conflicting directions and may not work when there are other emergency vehicles traveling from conflicting directions simultaneously. Employing deep reinforcement learning techniques, recent studies have shown promising results for traffic signal control. In this work, we deliver an early attempt to control the traffic signal for emergency vehicles through deep reinforcement learning, which ensures an expeditious emergency response in various scenarios and alleviates the negative influence on the traffic efficiency of conflicting directions. We conduct realistic simulations using traffic data in a real-world network with multiple intersections on different testing parameters. The results verify the feasibility and effectiveness of our model and indicate that our method notably outperforms the other five baseline methods in terms of various performance metrics.

An Autonomous Vehicle (AV) is believed to be the next generation transport that can enhance safety and efficiency for smart mobility. In an AV-based public transportation system, the full autonomy of AVs enables high-efficiency transport services and the potential ride-sharing feature of AV system enhances the utilization. The system manages a fleet of AVs, determines their assignments to transport requests, sends instructions concerning the optimized plans, and recommends the parking locations for the unoccupied AVs. The parking location of an empty AV is crucial in the sense that rebalancing AVs to areas with high potential service demand can curtail the unnecessary waiting time for passengers. As AVs are generally electric, proper parking locations can also facilitate vehicle-to-grid (V2G) support. In this paper, we propose a joint rebalancing and V2G coordination strategy for AV-based public transportation system. We formulate the problem as an integer linear program and propose a heuristic based on Genetic Algorithm and Model Predictive Control to solve the problem in low time complexity. Extensive experiments are performed with the real taxi service data from New York City. The formulated integer linear program is solved dynamically where each problem instance contains 3 to 5 AVs and 3 to 8 requests in 30s time interval. Compared with the transport system without rebalancing, the results show that the coordination strategy is efficient and effective in reducing unnecessary waiting time for passengers while satisfying V2G support. Compared to computational time with the standard solver, the proposed heuristic dramatically reduces the computational time.

An efficient transportation system can substantially benefit our society, but road intersections have always been among the major traffic bottlenecks leading to traffic congestion. Appropriate traffic signal timing adapted to real-time traffic may help mitigate such traffic congestion. However, most existing traffic signal control methods require a huge amount of road information, such as vehicle positions. In this paper, we focus on a particular road intersection and aim to minimize the average waiting time. We propose a traffic signal control (TSC) system based on an end-to-end off-policy deep reinforcement learning (deep RL) agent with background removal residual networks. The agent takes real-time images at the road intersection as input. Upon sufficient training, the agent can perform (near-) optimal traffic signaling based on real-time traffic conditions. We conduct experiments on different intersection scenarios and compare various TSC methods. The experimental results show that our end-to-end deep RL approach can adapt to the dynamic traffic based on the traffic images and outperforms other TSC methods.

Lexically constrained sentence generation allows the incorporation of prior knowledge such as lexical constraints into the output. This technique has been applied to machine translation, and dialog response generation. Previous work usually used Markov Chain Monte Carlo (MCMC) sampling to generate lexically constrained sentences, but they randomly determined the position to be edited and the action to be taken, resulting in many invalid refinements. To overcome this challenge, we used a classifier to instruct the MCMC-based models where and how to refine the candidate sentences. First, we developed two methods to create synthetic data on which the pre-trained model is fine-tuned to obtain a reliable classifier. Next, we proposed a two-step approach, “Predict and Revise”, for constrained sentence generation. During the predict step, we leveraged the classifier to compute the learned prior for the candidate sentence. During the revise step, we resorted to MCMC sampling to revise the candidate sentence by conducting a sampled action at a sampled position drawn from the learned prior. We compared our proposed models with many strong baselines on two tasks, generating sentences with lexical constraints and text infilling. Experimental results have demonstrated that our proposed model performs much better than the previous work in terms of sentence fluency and diversity. Our code, pre-trained models and Appendix are available at https://github.com/NLPCode/MCMCXLNet.

Lexically constrained neural machine translation (NMT), which leverages pre-specified translation to constrain NMT, has practical significance in interactive translation and NMT domain adaption. Previous work either modify the decoding algorithm or train the model on augmented dataset. These methods suffer from either high computational overheads or low copying success rates. In this paper, we investigate Att-Input and Att-Output, two alignment-based constrained decoding methods. These two methods revise the target tokens during decoding based on word alignments derived from encoder-decoder attention weights. Our study shows that Att-Input translates better while Att-Output is more computationally efficient. Capitalizing on both strengths, we further propose EAM-Output by introducing an explicit alignment module (EAM) to a pretrained Transformer. It decodes similarly as EAM-Output, except using alignments derived from the EAM. We leverage the word alignments induced from Att-Input as labels and train the EAM while keeping the parameters of the Transformer frozen. Experiments on WMT16 De-En and WMT16 Ro-En show the effectiveness of our approaches on constrained NMT. In particular, the proposed EAM-Output method consistently outperforms previous approaches in translation quality, with light computational overheads over unconstrained baseline.

Disturbance, which is generally unknown to the controller, is unavoidable in real-world systems and it may affect the expected system state and output. Existing control methods, like robust model predictive control, can produce robust solutions to maintain the system stability. However, these robust methods trade the solution optimality for stability. In this article, a method called generative adversarial control networks (GACNs) is proposed to train a controller via demonstrations of the optimal controller. By formulating the optimal control problem in the presence of disturbance, the controller trained by GACNs obtains neuro-optimal solutions without knowing the future disturbance and determines the objective function explicitly. A joint loss, composed of the adversarial loss and the least square loss, is designed to be used in the training of the generator. Experimental results on simulated systems with disturbance show that GACNs outperform other compared control methods.

The intensity estimation of facial action units (AUs) is challenging due to subtle changes in the person's facial appearance. Previous approaches mainly rely on probabilistic models or predefined rules for modeling co-occurrence relationships among AUs, leading to limited generalization. In contrast, we present a new learning framework that automatically learns the latent relationships of AUs via establishing semantic correspondences between feature maps. In the heatmap regression-based network, feature maps preserve rich semantic information associated with AU intensities and locations. Moreover, the AU co-occurring pattern can be reflected by activating a set of feature channels, where each channel encodes a specific visual pattern of AU. This motivates us to model the correlation among feature channels, which implicitly represents the co-occurrence relationship of AU intensity levels. Specifically, we introduce a semantic correspondence convolution (SCC) module to dynamically compute the correspondences from deep and low resolution feature maps, and thus enhancing the discriminability of features. The experimental results demonstrate the effectiveness and the superior performance of our method on two benchmark datasets.

The key challenge of multi-domain translation lies in simultaneously encoding both the general knowledge shared across domains and the particular knowledge distinctive to each domain in a unified model. Previous work shows that the standard neural machine translation (NMT) model, trained on mixed-domain data, generally captures the general knowledge, but misses the domain-specific knowledge. In response to this problem, we augment NMT model with additional domain transformation networks to transform the general representations to domain-specific representations, which are subsequently fed to the NMT decoder. To guarantee the knowledge transformation, we also propose two complementary supervision signals by leveraging the power of knowledge distillation and adversarial learning. Experimental results on several language pairs, covering both balanced and unbalanced multi-domain translation, demonstrate the effectiveness and universality of the proposed approach. Encouragingly, the proposed unified model achieves comparable results with the fine-tuning approach that requires multiple models to preserve the particular knowledge. Further analyses reveal that the domain transformation networks successfully capture the domain-specific knowledge as expected.1

Modern neural machine translation (NMT) models employ a large number of parameters, which leads to serious over-parameterization and typically causes the underutilization of computational resources.In response to this problem, we empirically investigate whether the redundant parameters can be reused to achieve better performance.Experiments and analyses are systematically conducted on different datasets and NMT architectures.We show that: 1) the pruned parameters can be rejuvenated to improve the baseline model by up to +0.8 BLEU points; 2) the rejuvenated parameters are reallocated to enhance the ability of modeling low-level lexical information.

Leveraging lexical constraint is extremely significant in domain-specific machine translation and interactive machine translation. Previous studies mainly focus on extending beam search algorithm or augmenting the training corpus by replacing source phrases with the corresponding target translation. These methods either suffer from the heavy computation cost during inference or depend on the quality of the bilingual dictionary pre-specified by user or constructed with statistical machine translation. In response to these problems, we present a conceptually simple and empirically effective data augmentation approach in lexical constrained neural machine translation. Specifically, we make constraint-aware training data by first randomly sampling the phrases of the reference as constraints, and then packing them together into the source sentence with a separation symbol. Extensive experiments on several language pairs demonstrate that our approach achieves superior translation results over the existing systems, improving translation of constrained sentences without hurting the unconstrained ones.

Increasingly serious traffic congestion requires an accurate and timely traffic speed prediction, which will significantly benefit both individual drivers and decision makers in travel planning and traffic management. However, traffic speed prediction is a long-standing and challenging topic. Due to the availability of traffic datasets and powerful computation resources, deep learning becomes a promising solution to this problem. In this paper, based on Convolutional Neural Networks (CNN) and Long Short-Term Memory (LSTM) models, we propose a model named CLM, which is the first to make use of CNN to extract the features of daily and weekly periodicity of traffic speed at the target area and also extract the spatiotemporal features together with the output of CNN by LSTM layers. We conduct comprehensive simulations to assess the performance of our proposed method based on the real-world dataset of Hong Kong. The results indicate that our proposed CLM model can better predict traffic speed in different forecast time periods than the other five competing methods, including SVR, MLP, Lasso, Random forest, and LSTM.

Abstract Infinite population models are important tools for studying population dynamics of evolutionary algorithms. They describe how the distributions of populations change between consecutive generations. In general, infinite population models are derived from Markov chains by exploiting symmetries between individuals in the population and analyzing the limit as the population size goes to infinity. In this article, we study the theoretical foundations of infinite population models of evolutionary algorithms on continuous optimization problems. First, we show that the convergence proofs in a widely cited study were in fact problematic and incomplete. We further show that the modeling assumption of exchangeability of individuals cannot yield the transition equation. Then, in order to analyze infinite population models, we build an analytical framework based on convergence in distribution of random elements which take values in the metric space of infinite sequences. The framework is concise and mathematically rigorous. It also provides an infrastructure for studying the convergence of the stacking of operators and of iterating the algorithm which previous studies failed to address. Finally, we use the framework to prove the convergence of infinite population models for the mutation operator and the k-ary recombination operator. We show that these operators can provide accurate predictions for real population dynamics as the population size goes to infinity, provided that the initial population is identically and independently distributed.

An effective intelligent transportation system is a core part of modern smart city. The Internet of Things and vehicular communication technologies facilitate rapid development of connected and autonomous vehicles (CAVs). While most studies focus on standalone CAV technologies, collective CAV control has much potential. With the connectivity and automation of CAVs, we can employ dynamic lane reversal (DLR) to optimize the travel schedules of CAVs for performance enhancement. In this paper, we propose the dynamic lane reversal-traffic scheduling management (DLR-TSM) scheme for CAVs. The system collects the travel requests from CAVs and determines their optimal schedules and routes over dynamically reversible lanes. We formulate the routing and scheduling problem on DLR as an integer linear program. To address the scaling effect, an algorithm based on alternating direction method of multipliers is designed to solve the problem in a distributed manner. We extensively evaluate the DLR-TSM and the distributed algorithm with real-world transportation data. The simulation results show that the DLR-TSM can significantly improve the travel times of CAVs and the distributed algorithm can dramatically reduce the required computational time.

Advancements in sensing and the Internet of Things (IoT) technologies generate a huge amount of data. Mobility on demand (MoD) service benefits from the availability of big data in the intelligent transportation system. Given the future travel demand or origin-destination (OD) flows prediction, service providers can pre-allocate unoccupied vehicles to the customers' origins of service to reduce waiting time. Traditional approaches on future travel demand and the OD flows predictions rely on statistical or machine learning methods. Inspired by deep learning techniques for image and video processing, through regarding localized travel demands as image pixels, a novel deep learning model called multi-scale convolutional long short-term memory network (MultiConvLSTM) is developed in this paper. Rather than using the traditional OD matrix which may lead to loss of geographical information, we propose a new data structure, called OD tensor to represent OD flows, and a manipulation method, called OD tensor permutation and matricization, is introduced to handle the high dimensionality features of OD tensor. MultiConvLSTM considers both temporal and spatial correlations to predict the future travel demand and OD flows. Experiments on real-world New York taxi data of around 400 million records are performed. Our results show that the MultiConvLSTM achieves the highest accuracy in both one-step and multiple-step predictions and it outperforms the existing methods for travel demand and OD flow predictions.

Cooperative Rate-Splitting (CRS) strategy, relying on linearly precoded rate-splitting at the transmitter and opportunistic transmission of the common message by the relaying user, has recently been shown to outperform typical Non-cooperative Rate-Splitting (NRS), Cooperative Non-Orthogonal Multiple Access (C-NOMA) and Space Division Multiple Access (SDMA) in a two-user Multiple Input Single Output (MISO) Broadcast Channel (BC) with user relaying. In this work, the existing twouser CRS transmission strategy is generalized to the K-user case. We study the problem of jointly optimizing the precoders, message split, time slot allocation, and relaying user scheduling with the objective of maximizing the minimum rate among users subject to a transmit power constraint at the base station. As the user scheduling problem is discrete and the entire problem is non-convex, we propose a two-stage low-complexity algorithm to solve the problem. Both centralized and decentralized relaying protocols based on selecting K1(K1<; K) strongest users are first proposed followed by a Successive Convex Approximation (SCA)-based algorithm to jointly optimize the time slot, precoders and message split. Numerical results show that by applying the proposed two-stage algorithm, the worst-case achievable rate achieved by CRS is significantly increased over that of NRS and SDMA in a wide range of network loads (underloaded and overloaded regimes) and user deployments (with a diversity of channel strengths). Importantly, the proposed SCA-based algorithm dramatically reduces the computational complexity without any rate loss compared with the conventional algorithm in the literature of CRS. Therefore, we conclude that the proposed K-user CRS combined with the two-stage algorithm is more powerful than the existing transmission schemes.

Zero-shot translation, translating between language pairs on which a Neural Machine Translation (NMT) system has never been trained, is an emergent property when training the system in multilingual settings.However, naïve training for zero-shot NMT easily fails, and is sensitive to hyper-parameter setting.The performance typically lags far behind the more conventional pivot-based approach which translates twice using a third language as a pivot.In this work, we address the degeneracy problem due to capturing spurious correlations by quantitatively analyzing the mutual information between language IDs of the source and decoded sentences.Inspired by this analysis, we propose to use two simple but effective approaches: (1) decoder pre-training; (2) backtranslation.These methods show significant improvement (4 ∼ 22 BLEU points) over the vanilla zero-shot translation on three challenging multilingual datasets, and achieve similar or better results than the pivot-based approach.

Millimeter wave (mm-wave) communication technology promises to provide higher data rates as the spectrum is highly under-utilized and more amount of spectrum can be allocated. However, mm-wave cannot travel longer distances and it is sensitive to blockages. The former issue can be dealt with via the small cell technology. Small cell technology can increase the spectral efficiency of the system if the resources are efficiently utilized. The transmission distance between the mobile user and the small cell access point is reduced and it makes an ideal candidate for the use of mm-wave. However, the latter issue of blockages still needs to be handled in order to exploit the full benefits of mm-wave in small cell network. In this paper, a blockage-aware allocation of resources for a mm-wave small cell network is investigated. Our objective is to maximize the downlink sum-rate of all users such that the quality of service (QoS) and power constraints are satisfied. The formulated problem takes into consideration the presence of blockages and the best link (both LOS and relay, only LOS, only relay) possible. We propose a blockage-aware relay selection and power allocation algorithm (BARSPAA) for mm-wave in small cells. The BARSPAA algorithm is compared with exhaustive and bounded exhaustive search algorithms. Numerical results show that the proposed BARSPAA achieves a significantly close performance while the algorithm complexity is much reduced.

Data integrity of power system states is critical to modern power grid operation and control due to communication latency, state measurements are not immediately available at the control center, rendering slow responses of time-sensitive applications. In this paper, a new graph-based deep learning approach is proposed to recover and predict the states ahead of time utilizing the power network topology and existing measurements. A graph-convolutional recurrent adversarial network is devised to process available information and extract graphical and temporal data correlations. This approach overcomes drawbacks of the existing synchrophasor recovery and prediction implementation to improve the overall system performance. Additionally, the approach offers an adaptive data processing method to handle power grids of various sizes. Case studies demonstrate the outstanding recovery and prediction accuracy of the proposed approach, and investigations are conducted to illustrate its robustness against bad communication conditions, measurement noise, and system topology changes.

In a Non-Orthogonal Unicast and Multicast (NOUM) transmission system, a multicast stream intended to all the receivers is superimposed in the power domain on the unicast streams. One layer of Successive Interference Cancellation (SIC) is required at each receiver to remove the multicast stream before decoding its intended unicast stream. In this paper, we first show that a linearly-precoded 1-layer Rate-Splitting (RS) strategy at the transmitter can efficiently exploit this existing SIC receiver architecture. By splitting the unicast messages into common and private parts and encoding the common parts along with the multicast message into a super-common stream decoded by all users, the SIC is better reused for the dual purpose of separating the unicast and multicast streams as well as better managing the multi-user interference among the unicast streams. We further propose multi-layer transmission strategies based on the generalized RS and power-domain Non-Orthogonal Multiple Access (NOMA). Two different objectives are studied for the design of the precoders, namely, maximizing the Weighted Sum Rate (WSR) of the unicast messages and maximizing the system Energy Efficiency (EE), both subject to Quality of Service (QoS) rate requirements of all messages and a sum power constraint. A Weighted Minimum Mean Square Error (WMMSE)-based algorithm and a Successive Convex Approximation (SCA)-based algorithm are proposed to solve the WSR and EE problems, respectively. Numerical results show that the proposed RS-assisted NOUM transmission strategies are more spectrally and energy efficient than the conventional Multi-User Linear-Precoding (MU-LP), Orthogonal Multiple Access (OMA) and power-domain NOMA in a wide range of user deployments (with a diversity of channel directions, channel strengths and qualities of channel state information at the transmitter) and network loads (underloaded and overloaded regimes). It is superior for the downlink multi-antenna NOUM transmission.

The data transmission performance of a network protocol is closely related to the amount of available information about the network state. In general, more network state information results in better data transmission performance. However, acquiring such state information expends network bandwidth resource. Thus, a trade-off exists between the amount of network state information collected, and the improved protocol performance due to this information. A framework has been developed in the previous efforts to study the optimal trade-off between the amount of collected information and network performance. However, the effect of information delay is not considered in the previous analysis. In this paper, we extend the framework to study the relationship between the amount of collected state information and the achievable network performance under the assumption that information is subject to delay. Based on the relationship we could then obtain the optimal resource allocation between the data transmission and network state information acquisition in a time-varying network. We have considered both memoryless and memory-exploited scenarios in our framework. Structures of the Pareto optimal information collection and decision-making strategies are discussed. Examples of multiuser scheduling and multi-hop routing are used to demonstrate the framework's application to practical network protocols.

While end-to-end neural machine translation (NMT) has achieved notable success in the past years in translating a handful of resource-rich language pairs, it still suffers from the data scarcity problem for low-resource language pairs and domains. To tackle this problem, we propose an interactive multimodal framework for zero-resource neural machine translation. Instead of being passively exposed to large amounts of parallel corpora, our learners (implemented as encoder-decoder architecture) engage in cooperative image description games, and thus develop their own image captioning or neural machine translation model from the need to communicate in order to succeed at the game. Experimental results on the IAPR-TC12 and Multi30K datasets show that the proposed learning mechanism significantly improves over the state-of-the-art methods.

Previous neural machine translation models used some heuristic search algorithms (e.g., beam search) in order to avoid solving the maximum a posteriori problem over translation sentences at test phase. In this paper, we propose the \textit{Gumbel-Greedy Decoding} which trains a generative network to predict translation under a trained model. We solve such a problem using the Gumbel-Softmax reparameterization, which makes our generative network differentiable and trainable through standard stochastic gradient methods. We empirically demonstrate that our proposed model is effective for generating sequences of discrete words.

In this paper, we extend an attention-based neural machine translation (NMT) model by allowing it to access an entire training set of parallel sentence pairs even after training. The proposed approach consists of two stages. In the first stage –retrieval stage–, an off-the-shelf, black-box search engine is used to retrieve a small subset of sentence pairs from a training set given a source sentence. These pairs are further filtered based on a fuzzy matching score based on edit distance. In the second stage–translation stage–, a novel translation model, called search engine guided NMT (SEG-NMT), seamlessly uses both the source sentence and a set of retrieved sentence pairs to perform the translation. Empirical evaluation on three language pairs (En-Fr, En-De, and En-Es) shows that the proposed approach significantly outperforms the baseline approach and the improvement is more significant when more relevant sentence pairs were retrieved.

Cross-dataset facial emotion recognition (FER) aims to reduce the discrepancy between the source and the target facial database. The topic is very challenging in FER, where facial features differ across different domains, such as ethnicity, age, gender and environmental condition. In practice, the labels of target facial expression database may be unavailable, making it impossible to fine-tune a pre-trained model via supervised transfer learning. To address this issue, we propose an unsupervised domain adaptation framework with adversarial learning for cross-dataset FER. We perform cross-dataset FER on three well-known publicly available facial expression databases, viz. CK+, Oulu-CASIA, and RAF-DB, showcasing the efficiency of our proposed approach.

Rapid socio-economic development and urbanization have resulted in serious deterioration in air-quality in many world cities, including Beijing, China. This preliminary study is the first attempt to examine the effectiveness of air pollution control regulations implemented in Beijing during 2013 - 2017 through a data-driven regulatory intervention analysis. Our proposed machine-learning model utilizes proxy data including Aerosol Optical Depth (AOD) and meteorology; it can explain 80% of the PM2.5variability. Our preliminary results show that air pollution control regulatory measures introduced in China and Beijing have reduced PM2.5pollution in Beijing by 23% on average.

This study examines the statistical relationship between people's international movements and air quality. Utilizing randomized geo-tagged tweets obtained from Twitter Streaming API, we extract international movements that Twitter users have actually made. Coupling these movements with the air quality data across the world, we verify that Twitter users tend to move to countries of better air qualities. We also find that in most countries, the out-movement rate tends to be positively associated with the monthly air pollution concentration, and the number of movements to destination countries is negatively associated with the decrease in air pollution concentration in the origin countries.

As the main energy source is coal burning, district heating in Northern China is an important driver of air pollution. Optimization of the performance of District Heating Network (DHN) carries both social and economic benefits. This study proposes an approach for optimizing urban heating network design based on Genetic Algorithm. Our case study shows that DHN can meet the users' requirements and achieve minimum cost in parallel.

Beam search is a widely used approximate search strategy for neural network decoders, and it generally outperforms simple greedy decoding on tasks like machine translation.However, this improvement comes at substantial computational cost.In this paper, we propose a flexible new method that allows us to reap nearly the full benefits of beam search with nearly no additional computational cost.The method revolves around a small neural network actor that is trained to observe and manipulate the hidden state of a previouslytrained decoder.To train this actor network, we introduce the use of a pseudo-parallel corpus built using the output of beam search on a base model, ranked by a target quality metric like BLEU.Our method is inspired by earlier work on this problem, but requires no reinforcement learning, and can be trained reliably on a range of models.Experiments on three parallel corpora and three architectures show that the method yields substantial improvements in translation quality and speed over each base system.

In this paper, we propose to extend the recently introduced model-agnostic meta-learning algorithm (MAML, Finn et al., 2017) for lowresource neural machine translation (NMT).We frame low-resource translation as a metalearning problem, and we learn to adapt to low-resource languages based on multilingual high-resource language tasks.We use the universal lexical representation (Gu et al., 2018b) to overcome the input-output mismatch across different languages.We evaluate the proposed meta-learning strategy using eighteen European languages (Bg, Cs, Da, De, El, Es, Et, Fr, Hu, It, Lt, Nl, Pl, Pt, Sk, Sl, Sv and Ru) as source tasks and five diverse languages (Ro, Lv, Fi, Tr and Ko) as target tasks.We show that the proposed approach significantly outperforms the multilingual, transfer learning based approach (Zoph et al., 2016) and enables us to train a competitive NMT system with only a fraction of training examples.For instance, the proposed approach can achieve as high as 22.04 BLEU on Romanian-English WMT'16 by seeing only 16,000 translated words (⇠ 600 parallel sentences).

In smart cities, with large numbers of vehicles on roads, including autonomous and manned ones, congestion is still a significant issue and hence smart traffic signal control is indispensable. Nowadays, navigation apps have become increasingly popular and path information is widely available. Due to the development of various vehicular communication technologies, V2X communications become increasingly stable and efficient. Accurate knowledge of traffic flow is key to effective traffic signal control. Most of the existing adaptive strategies rely on video cameras, radars, or other wireless sensors, which involve a huge investment for measuring or estimating real-time flow. In this paper, based on V2I communications, we propose to make use of navigation information of vehicles to obtain real-time traffic flow around each intersection, thus achieving effective traffic signal control. In undersaturated and oversaturated traffic conditions, we analyze the performance of navigation- based strategy to control traffic signal, study how to obtain optimal cycle duration and compare it with the even-distributed fixed-time strategy. Our results can also provide significant insights on other strategies. We conduct extensive simulations to validate our analysis and evaluate the performance of the navigation-based strategy. The results show that the navigation-based strategy is effective and practical, and can further relieve congestion compared with the even-distributed fixed-time strategy.

Replication and coding are two popular approaches to combat failures in large-scale distributed storage systems. Access latency in such systems greatly impacts user experience. Compared with redundant scheduling, random scheduling can reduce the system load, resulting in lower latency, especially when the request arrival rate is high. Besides, random scheduling can achieve near optimal load balancing at a reduced communication cost. A latency comparison of replication and coding is of great importance. Although it has been much argued that coding can achieve lower latency than replication, the latency comparison under random scheduling is still lacking. In this work, based on random scheduling, we analyze the latency of replication and coding and find that, when each request desires all data in a codeword, they have the same average latency. Additionally, we study a general case that users only request a subset of the erasure-coded content, and propose flexible random scheduling for coding, which can lower latency and realize load balancing. Our analysis demonstrates that, in this case, replication achieves lower latency when the system load is low and suffers higher latency when the system load becomes high. With real service time traces from Amazon S3, we conduct trace-driven simulations to validate our analysis.

Emotion recognition (ER) based on natural facial images/videos has been studied for some years and considered a comparatively hot topic in the field of affective computing. However, it remains a challenge to perform ER in the wild, given the noises generated from head pose, face deformation, and illumination variation. To address this challenge, motivated by recent progress in Convolutional Neural Network (CNN), we develop a novel deeply supervised CNN (DSN) architecture, taking the multi-level and multi-scale features extracted from different convolutional layers to provide a more advanced representation of ER. By embedding a series of side-output layers, our DSN model provides class-wise supervision and integrates predictions from multiple layers. Finally, our team ranked 3rd at the EmotiW 2018 challenge with our model achieving an accuracy of 61.1%.

Bufferbloat is a phenomenon where router buffers are constantly being filled, resulting in high queueing delay and delay variation. Larger buffer size and more delay-sensitive applications on the Internet have made this phenomenon a pressing issue. Active queue management (AQM) algorithms, which play an important role in combating bufferbloat, have not been widely deployed due to complicated manual parameter tuning. Moreover, AQM algorithms are often designed and analyzed based on models with a single bottleneck link, rendering their performance and stability unclear in multi-bottleneck networks. In this paper, we propose a general framework to combat bufferbloat in multi-bottleneck networks. We first conduct an equilibrium analysis for a general multi-bottleneck TCP/ AQM system and develop an algorithm to compute the equilibrium point. We then decompose the system into single-bottleneck subsystems and derive sufficient conditions for the local asymptotic stability of the subsystems. Using the proposed framework, we present a case study to analyze the stability of the recently proposed Controlled Delay (CoDel) in multi-bottleneck networks and devise Self-tuning CoDel to improve the system stability and performance. Extensive simulation results show that Self-tuning CoDel effectively stabilizes queueing delay in multi-bottleneck scenarios, and thus contributes to combating bufferbloat.

Jiatao Gu, Hany Hassan, Jacob Devlin, Victor O.K. Li. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

Online social networks provide a platform for customers to share their experience and make viral marketing possible. Through online social networks, sellers can apply marketing strategies to reach more potential buyers and thus gain more revenue. Previous studies on social network marketing based on the influence maximization problem focus on how to propagate information widely and neglect that price is a key factor that influences information diffusion. In this paper, we study the problem of how to design pricing strategies in order to maximize the revenue when the product usage or promotion time is limited. Different from the existing study of optimal pricing scheme over online social networks, we consider how the price may influence the diffusion. In addition, with limited promotion time, the prices assigned in the different promotion stages of the pricing sequence can be increasing. To better understand the problem, we propose a framework which incorporates the influence maximization problem and a multi-state diffusion model. In the diffusion model, users are divided into different groups by their purchasing behavior and have different influence power, which informs how pricing strategies can influence the potential buyers. We design several pricing strategies under our framework with different pricing sequence order and different promotion time. Simulations are performed to illustrate the concepts in our framework and compare different pricing strategies. With our framework, we can provide some guidelines for the seller when designing the pricing strategy.

Spatial crowdsourcing (SC) is an emerging paradigm of crowdsourcing, which commits workers to move to some particular locations to perform spatio-temporal-relevant tasks (e.g., sensing and activity organization). Task allocation or worker selection is a significant problem that may impact the quality of completion of SC tasks. Based on a conceptual model and generic framework of SC task allocation, this paper first gives a review of the current state of research in this field, including single task allocation, multiple task allocation, low-cost task allocation, and quality-enhanced task allocation. We further investigate the future trends and open issues of SC task allocation, including skill-based task allocation, group recommendation and collaboration, task composition and decomposition, and privacypreserving task allocation. Finally, we discuss the practical issues on real-world deployment as well as the challenges for large-scale user study in SC task allocation.

This paper proposes CrowdTracker, a novel object tracking system based on mobile crowd sensing (MCS). Different from traditional video-based object tracking approaches, CrowdTracker recruits people to collaboratively take photographs of the object to achieve object movement prediction and tracking. The optimization objective of CrowdTracker is to effectively track the moving object in real time and minimize the cost on user incentives. Specifically, the incentive is determined by the number of workers assigned and the total distance that workers move to complete the task. In order to achieve the objective, we propose the movement prediction (MPRE) model for object movement prediction and two other algorithms for task allocation, namely, T-centric and P-centric. T-centric selects workers in a task-centric way, while P-centric allocates tasks in a peoplecentric manner. By analyzing a large number of historical vehicle trajectories, MPRE builds a model to predict the object's next position. In the predicted regions, CrowdTracker selects workers by utilizing T-centric or P-centric. We evaluate the algorithms over a large-scale real-world dataset. Experimental results indicate that CrowdTracker can effectively track the object with a low incentive cost.

The Internet of Things forms the backbone of connectivity for the smart city, which revolutionizes the transportation and energy sectors and drives the development of vehicular energy network (VEN). VEN is a vehicular network which can transport energy over a large geographical area by means of electric vehicles (EVs). In the near future, an abundance of EVs, plentiful generation of renewables, and mature wireless energy transfer and vehicular communication technologies will expedite the realization of VEN. To transmit energy from a source to a destination, we need to establish energy paths, which are composed of segments of vehicular routes, while satisfying various design objectives. In this paper, we develop a method to construct all energy paths for a particular energy source-destination pair, followed by some analytical results of the method. We describe how to utilize the energy paths to develop optimization models for different design goals and propose two solutions. We also develop a heuristic for the power loss minimization problem. We compare the performance of the three solution methods with artificial and real-world traffic networks and provide a comprehensive comparison in terms of solution quality, computation time, solvable problem size, and applicability. This paper lays the foundations of VEN routing.

Many countries are suffering from severe air pollution. Understanding how different air pollutants accumulate and propagate is critical to making relevant public policies. In this paper, we use urban big data (air quality data and meteorological data) to identify the spatiotemporal (ST) causal pathways for air pollutants. This problem is challenging because: (1) there are numerous noisy and low-pollution periods in the raw air quality data, which may lead to unreliable causality analysis; (2) for large-scale data in the ST space, the computational complexity of constructing a causal structure is very high; and (3) the ST causal pathways are complex due to the interactions of multiple pollutants and the influence of environmental factors. Therefore, we present pg-Causality, a novel pattern-aided graphical causality analysis approach that combines the strengths of pattern mining and Bayesian learning to efficiently identify the ST causal pathways. First, pattern mining helps suppress the noise by capturing frequent evolving patterns (FEPs) of each monitoring sensor, and greatly reduce the complexity by selecting the pattern-matched sensors as “causers”. Then, Bayesian learning carefully encodes the local and ST causal relations with a Gaussian Bayesian Network (GBN)-based graphical model, which also integrates environmental influences to minimize biases in the final results. We evaluate our approach with three real-world data sets containing 982 air quality sensors in 128 cities, in three regions of China from 01-Jun-2013 to 31-Dec-2016. Results show that our approach outperforms the traditional causal structure learning methods in time efficiency, inference accuracy and interpretability.

In online social networks, celebrities are usually paid to promote products via posting or forwarding ads or related information. Imagine that one day when everyone is allowed to register as a spreader and participate in the campaign to sell influence, how much money should be claimed? Two factors play vital roles in deciding the price. One is how influence is valued by buyers (advertisers). The other is how one's price is affected by that of others. In this paper, we consider that the influence is valued as the number of final “activations” under some existing information diffusion processes, and focus on the latter, namely, the price competition. We model the scenario as a pricing game where spreaders compete with each other under selection policies of the advertiser, who is trying to maximize its profit. We draw conclusions for three cases of the advertiser. First, an omniscient advertiser always selects the optimal set of spreaders. We show that the competition is so fierce that each spreader can only claim its unique influence in the Nash equilibrium (NE), and the equilibrium is also unique. Second, the greedy advertiser selects spreaders using the simple greedy algorithm. We deduce that the unique NE exists when the number of spreaders is less than four; however, the existence of NE cannot be guaranteed when there are at least four spreaders. Third, the advertiser adopts a “double-greedy” method that greedily selects spreaders one by one in accordance with their registration order. We conclude that the unique NE exists and the utility of the platform is at least 1/2 to the optimal and also bounded by 1/2 to the influence of all spreaders.

State estimation is critical to the operation and control of modern power systems. However, many cyber-attacks, such as false data injection attacks, can circumvent conventional detection methods and interfere the normal operation of grids. While there exists research focusing on detecting such attacks in dc state estimation, attack detection in ac systems is also critical, since ac state estimation is more widely employed in power utilities. In this paper, we propose a new false data injection attack detection mechanism for ac state estimation. When malicious data are injected in the state vectors, their spatial and temporal data correlations may deviate from those in normal operating conditions. The proposed mechanism can effectively capture such inconsistency by analyzing temporally consecutive estimated system states using wavelet transform and deep neural network techniques. We assess the performance of the proposed mechanism with comprehensive case studies on IEEE 118- and 300-bus power systems. The results indicate that the mechanism can achieve a satisfactory attack detection accuracy. Furthermore, we conduct a preliminary sensitivity test on the control parameters of the proposed mechanism.

While end-to-end neural machine translation (NMT) has made remarkable progress recently, it still suffers from the data scarcity problem for low-resource language pairs and domains.In this paper, we propose a method for zero-resource NMT by assuming that parallel sentences have close probabilities of generating a sentence in a third language.Based on the assumption, our method is able to train a source-to-target NMT model ("student") without parallel corpora available guided by an existing pivot-to-target NMT model ("teacher") on a source-pivot parallel corpus.Experimental results show that the proposed method significantly improves over a baseline pivot-based model by +3.0 BLEU points across various language pairs.

With the increasing awareness of the harmful impacts of urban air pollution, air quality monitoring stations have been deployed in many metropolitan areas. These stations provide air quality data to the public. However, due to sampling device failures and data processing errors, missing data in air quality measurements is common. Data integrity becomes a critical challenge when such data are employed for public services. In this paper, we investigate the mathematical property of air quality measurements, and attempt to recover the missing data. First, we empirically study the low rank property of these measurements. Second, we formulate the low rank matrix completion (LRMC) optimization problem to reconstruct the missing air quality data. The problem is transformed using duality theory, and singular value thresholding (SVT) is employed to develop sub-optimal solutions. Third, to evaluate the performance of our methodology, we conduct a series of case studies including different types of missing data patterns. The simulation results demonstrate that the proposed SVT methodology can effectively recover missing air quality data, and outperform the existing Interpolation. Finally, we investigate the parameter sensitivity of SVT. Our study can serve as a guideline for missing data recovery in the real world.

Translating in real-time, a.k.a.simultaneous translation, outputs translation words before the input sentence ends, which is a challenging problem for conventional machine translation methods.We propose a neural machine translation (NMT) framework for simultaneous translation in which an agent learns to make decisions on when to translate from the interaction with a pre-trained NMT environment.To trade off quality and delay, we extensively explore various targets for delay and design a method for beam-search applicable in the simultaneous MT setting.Experiments against state-of-the-art baselines on two language pairs demonstrate the efficacy of the proposed framework both quantitatively and qualitatively. 1

Recent research in neural machine translation has largely focused on two aspects; neural network architectures and end-toend learning algorithms.The problem of decoding, however, has received relatively little attention from the research community.In this paper, we solely focus on the problem of decoding given a trained neural machine translation model.Instead of trying to build a new decoding algorithm for any specific decoding objective, we propose the idea of trainable decoding algorithm in which we train a decoding algorithm to find a translation that maximizes an arbitrary decoding objective.More specifically, we design an actor that observes and manipulates the hidden state of the neural machine translation decoder and propose to train it using a variant of deterministic policy gradient.We extensively evaluate the proposed algorithm using four language pairs and two decoding objectives, and show that we can indeed train a trainable greedy decoder that generates a better translation (in terms of a target decoding objective) with minimal computational overhead.

Air quality has deteriorated rapidly in Hong Kong and China in the past two decades, with NO2and PM2.5levels frequently exceeding WHO safety guidelines. While poor air quality has clear public health impacts, there are very limited air quality monitoring (AQM) stations, severely constraining evidence-based air quality decision-making, leading to severe criticisms about the utility of the current official Air Quality Health Index to the public. Since air pollution is highly location-dependent, a city-wide deployment of traditional, highly sophisticated air quality monitors would be prohibitively expensive. In this paper, we propose a deep learning model to estimate air pollution throughout the city, utilizing the readily available urban data as proxy data. As with many big data driven approaches, the proxy data may be sparse/missing. We propose the M-BP algorithm to recover/fill in such missing data. Our results show that the proposed model gives better estimates compared with existing big data approaches.

Selecting k seed users in online social networks (OSNs) as spreaders to publish advertisements so that the final information spread is maximized, is the well-studied influence maximization problem. Studies have been focusing on a static pool of potential spreaders and ignoring their autonomy. In fact, as influential users in OSN, spreaders may act at their own discretion. Their availabilities are affected by both their logging in time and their willingness to participate in a marketing campaign. From the perspective of the advertiser, spreaders arrive stochastically. Instead of selecting spreaders on their own, advertisers usually delegate the task to a professional advertising platform and simply buy impressions. Comparing to the short time that spreaders spend on publishing advertisements, multiple advertisers exist simultaneously and are relatively static with much longer durations. Therefore, it is the platform's responsibility to properly distribute advertisements to stochastically arriving spreaders, or equivalently, allocate spreaders to sponsors. The goal is to maximize the sum utilities of all parties, i.e. the social welfare. In this paper, we propose the online simple-greedy algorithm for such allocation problem. We prove the algorithm is guaranteed to achieve an expected welfare of at least 1-1/e to the expected offline optimum, and further show it is the best that a polynomial-time algorithm can achieve. Moreover, we discussed extensions with different diffusion models and also conduct experiments on real datasets to show the performance of the greedy algorithm.

Access latency is the bottle-neck of various web services, and can greatly impact user experience, especially for the data retrieval applications, such as Google search. Many large-scale distributed storage systems are moving to the use of erasure codes to provide low storage overhead and high failure tolerance. Most previous work about coding latency focuses on the case when users desire all the data in a codeword. However, we find that in practical MDS- coded storage systems, the size of a codeword is usually so big that users only desire part of the files in a codeword. Hence, it is significant to analyze the latency in coding systems when users only desire part of a codeword. In this paper, we propose Flexible Redundant Scheme (FRedS) that can deal with the general case in which users only require part of the files from a codeword. In the case of no queueing delay, we give a general and closed-form expression of the coding latency with FRedS. Considering queueing delay, we extend the popular latency bound to analyze the latency performance of FRedS under the general service time distribution. Through extensive simulations using real service time traces from Amazon S3, we validate our latency analysis, demonstrate the tightness of the bounds derived in this work and show the latency comparison of FRedS and the direct read scheme.

A large-scale distributed storage system is the foundation for big data operations and applications, and replication and coding are the main methods to combat failures. Access latency is a key performance metric in such systems due to its great impact on user experience. Sending redundant requests is a popular and effective approach to reduce latency. It is therefore significant to present a fair latency comparison between replication and coding with the redundant scheduling. We analyze the latency of replication in the general case in which each request desires more than one data block. In the low arrival rate scenario, we give the exact latency analysis of replication, which is a novel generalization of the order statistic analysis of coding, and prove that coding achieves lower latency in this case. In the high arrival rate scenario, we point out the shortcomings of the latency comparison based on some popular latency bounds with redundant scheduling. In addition, this work is an earlier attempt to demonstrate the early cancellation advantage of replication and shows that, with redundant requests, coding can better reduce latency only in the low system load case while replication can achieve lower latency when the system load becomes high. We validate our analysis through extensive simulations using real latency traces from Amazon S3.

Caching popular contents at base stations (BSs) of a heterogeneous cellular network (HCN) reduces latency in content delivery and alleviates congestion in backhaul networks. Despite the existence of many sub-optimal strategies for content placement, the optimal ones for HCNs remain largely unknown and are investigated in this paper. To this end, we adopt the popular HCN model where BSs are modeled as K tiers of independent Poisson point processes (PPPs). Further, the random caching scheme is considered where each of a database of M files with corresponding popularity measures is placed at each BS of a particular tier with a corresponding probability, called placement probability. The probabilities are identical for all BSs in the same tier but vary over tiers, giving the name tier- level content placement. The network performance is measured by hit probability, defined as the probability that a file requested by the typical user is delivered successfully to the user. Consider the case of a uniform received signal-to- interference (SIR) threshold for successful transmissions. The optimal policy is derived in a simple form allowing sequential computation of the optimal placement probabilities. The result shows that the probability for a particular file-and-tier combination is a monotone increasing function of the file's popularity and the tier's density, transmis- sion power and storage capacity. Furthermore, for the general case of non-uniform SIR threshold, the optimization problem is non-convex and a sub-optimal placement policy is designed by approximation. The close- to-optimal policy has a similar structure as that in the previous case.

This paper deals with city-wide air quality estimation with limited air quality monitoring stations which are geographically sparse. Since air pollution is influenced by urban dynamics (e.g., meteorology and traffic) which are available throughout the city, we can infer the air quality in regions without monitoring stations based on such spatial-temporal (ST) heterogeneous urban big data. However, big data-enabled estimation poses three challenges. The first challenge is data diversity, i.e., there are many different categories of urban data, some of which may be useless for the estimation. To overcome this, we extend Granger causality to the ST space to analyze all the causality relations in a consistent manner. The second challenge is the computational complexity due to processing the massive volume of data. To overcome this, we introduce the non-causality test to rule out urban dynamics that do not “Granger” cause air pollution, and the region of influence (ROI), which enables us to only analyze data with the highest causality levels. The third challenge is to adapt our grid-based algorithm to non-grid-based applications. By developing a flexible grid-based estimation algorithm, we can decrease the inaccuracies due to grid-based algorithm while maintaining computation efficiency.

In this paper, we present the first detailed analysis of influence maximization in noncooperative social networks under the Independent Cascade Model (ICM). We propose a new influence model based on the ICM and prove the approximation guarantees for influence maximization in noncooperative settings. We structure the influence diffusion into two stages, namely, seed node selection and influence diffusion. In the former, we introduce a modified hierarchy-based seed node selection strategy, which can take node noncooperation into consideration. In the latter, we propose a game-theoretic model to characterize the behavior of noncooperative nodes and design a Vickrey- Clarke-Groves (VCG)-like scheme to incentivise cooperation. Then, we study the budget allocation problem between the two stages, and show that a marketer can utilize the two proposed strategies to tackle noncooperation intelligently. We evaluate our proposed schemes on large coauthorship networks, and the results show that our seed node selection scheme is very robust to noncooperation and the VCG-like scheme can effectively stimulate a node to become cooperative.

Caching popular contents at base stations (BSs) of a heterogeneous cellular network (HCN) avoids frequent information passage from content providers to the network edge, thereby reducing latency and alleviating traffic congestion in backhaul links. The potential of caching at the network edge for tackling 5G challenges has motivated recent studies on optimal content placement in large-scale HCNs. However, due to the complexity of the network performance analysis, the existing strategies were mostly based on approximation, heuristics, and intuition. In general, optimal strategies for content placement in HCNs remain largely unknown and deriving them forms the theme of this paper. To this end, we adopt the popular random HCN model, where K tiers of BSs are modeled as independent Poisson point processes distributed in the plane with different densities. Furthermore, the random caching scheme is considered, where each of a given set of M files with corresponding popularity measures is placed at each BS of a particular tier with a corresponding probability, called placement probability. The probabilities are identical for all BSs in the same tier but vary over tiers, giving the name tier-level content placement. We consider the network performance metric, hit probability, defined as the probability that a file requested by the typical user is delivered successfully to the user. Leveraging existing results on HCN performance, we maximize the hit probability over content placement probabilities, which yields the optimal tierlevel placement policies. For the case of uniform received signalto-interference (SIR) thresholds for successful transmissions for BSs in different tiers, the policy is in closed-form, where the placement probability for a particular file is proportional to the square-root of the corresponding popularity measure with an offset depending on BS caching capacities. For the general case of non-uniform SIR thresholds, the optimization problem is non-convex and a sub-optimal placement policy is designed by approximation, which has a similar structure as in the case of uniform SIR thresholds and shown by simulation to be close-tooptimal.

We address an important problem in sequence-to-sequence (Seq2Seq) learning referred to as copying, in which certain segments in the input sequence are selectively replicated in the output sequence. A similar phenomenon is observable in human language communication. For example, humans tend to repeat entity names or even long phrases in conversation. The challenge with regard to copying in Seq2Seq is that new machinery is needed to decide when to perform the operation. In this paper, we incorporate copying into neural network-based Seq2Seq learning and propose a new model called CopyNet with encoder-decoder structure. CopyNet can nicely integrate the regular way of word generation in the decoder with the new copying mechanism which can choose sub-sequences in the input sequence and put them at proper places in the output sequence. Our empirical study on both synthetic data sets and real world data sets demonstrates the efficacy of CopyNet. For example, CopyNet can outperform regular RNN-based model with remarkable margins on text summarization tasks.

Initialization will affect the performance of Evolutionary Algorithm (EA), especially under computationally expensive environments. To investigate the optimal resource allocation between the initialization and optimization stages, we studied the Computational Resource Optimization Problem (CROP) in our previous work. In this paper, we extend our resource allocation model by separating “initial solutions” into two sets, namely, Generated Initial Solutions (GIS) and Used Initial Solutions (UIS). Such separation in the model allows us to conduct a more comprehensive analysis and reveal more insights into how initial solutions can affect the performance of EAs under computationally expensive environments. Simulations are conducted on the BBOB'09 benchmark functions with the standard settings to mimic the expensive environment. We have shown that proper computational resource allocation can improve the solution quality. Our analysis allows us to find the best allocation scheme for a particular EA on a specific problem and also demonstrates the importance of initialization.

Download delay is a crucial performance metric in distributed storage systems as it greatly impacts user experience. Recently, plenty of research has pointed out that coding can reduce delay compared with replication. However, almost all previous studies only focus on the case in which all of the users require the same size of files and hence must download all files of a codeword and ignore the case in which some users only need some of the files in the codeword. Moreover, they do not consider the advantage of codes with original data nodes, such as systematic codes. In this paper, based on a more general and practical case in which download requests may desire different sizes of files and hence only some of the files of a codeword in a systematic (n, k) MDS-coded storage system, we propose the compound read method, characterize its mean download delay in low arrival rate scenario and derive upper and lower bounds on its mean download delay in high arrival rate scenario. We also compare the delay performance of compound and k-access reads and propose a scheme C & K to dynamically take advantage of them according to users' required size of files to reduce the mean download delay. In addition, with real service time traces from Amazon S3, we conduct trace-driven simulations to verify our theoretical analyses and the effectiveness of the C & K scheme.

Online social search such as Quora and Zhihu brings new ways to obtain answers to questions in social networks. However, personal and other sensitive information may be exposed to others when the question spreads via the social network. People obtain utility when they obtain answers to their questions but may suffer privacy cost when their personal information is known by others. Researchers are seeking methods and tools to help users get utility and protect their privacy at the same time. In this paper, we study this problem by proposing a framework to quantitatively evaluate the utility and privacy cost in online social search. Besides, we design an algorithm under our framework to help users trade off their utility and privacy cost. Simulations are performed to illustrate the concepts in our framework and demonstrate the advantages of our algorithm.

While the influence maximization problem (IMP) which studies how to trigger a large cascade in Online Social Networks (OSNs) by properly selecting seed nodes has been extensively studied in the past decade, one important and practical issue on how these seed nodes or celebrities will get paid for promoting cascades is seldom addressed. In order to get selected by the advertising platform and to maximize his/her own utility, it is natural for each celebrity to determine his/her price of promoting cascades based on other celebrities' decisions and his/her power of influence. In this paper, we formulate the problem of determining prices by celebrities as a pricing game, with celebrities as players. We show that celebrity selection by the advertising platform is NP-hard, and assume that the advertising platform will adopt the simple greedy algorithm that is widely used in IMP. Under this assumption, we study the pure Nash equilibrium of the pricing game among celebrities. In particular, we prove that while equilibrium exists and is unique when there are only two or three players, the equilibrium is not guaranteed to exist in cases of four or more players.

Download time is a key performance metric in distributed storage systems since it greatly impacts user experience, especially for latency-sensitive applications such as Google Search and so on. Recently, plenty of research has pointed out that coding can reduce download time. Till now, almost all previous studies analyze download time when a user requires all the information in a codeword. However, in practical storage systems such as the Windows Azure Storage System (WAS), only when files reach a certain size (e.g., 1GB), will it be a candidate for erasure coding [1]. That is, in practice, files stored in a codeword are usually very large and users' requests may only desire part of these files. Therefore, it is significant to analyze the latency performance when users only request a subset of the erasure-coded content.

Directional antennas have received much attention recently in multihop ad hoc networks, due to such benefits as increased transmission range, reduced co-channel interference, improved spatial reuse, and reduced susceptibility to jamming. However, existing random access scheduling schemes with directional antennas suffer from the issues of deafness and high probability of collisions. Moreover, such schemes cannot provide throughput and delay guarantees. In this paper, we propose a topology-transparent scheduling algorithm in mobile multihop ad hoc networks with directional antennas, to overcome these deficiencies. The proposed algorithm fully exploits the benefits of directional antennas and utilizes both assigned and unassigned time slots efficiently. We study the performance of our algorithm analytically and by simulation. The results show that the performance of the proposed algorithm, in certain cases, can be comparable to that of some topology-dependent algorithms designed for static networks. Yet, the proposed algorithm also performs well even when the network topology is dynamic, as in mobile networks.

Mobile users in public vehicles (train, buses, etc.) suffer from low signal quality due to the enclosed nature of the vehicles. Small cells may be used to provide good signal quality in enclosed regions. Therefore, deployment of small cells in public vehicles can be a promising solution to the quality-of-service issue. However, deploying such moving small cells makes the resource allocation in the network a challenging problem, due to the time-varying interference experienced and created by them. In this paper, we solve the joint resource allocation (resource blocks and power) problem in a cellular network with moving small cells, with the objective of enhancing the quality-of-service in the network. To capture the effect of mobility on the conflict relationship of the users in the moving small cell network, we propose representing the interference relationship as a time interval dependent interference (TIDI) graph. We formulated a joint resource allocation problem, which is decomposed into the subproblems of resource block (RB) allocation for a fixed power allocation and transmission power allocation for a fixed RB allocation to make the problem tractable. We propose an iterative resource allocation algorithm (IRAA) to solve the joint resource allocation problem.

Initialization techniques are normally considered as “resource-free” and their computational complexities are seldom addressed. Since many techniques require objective function evaluations to generate initial solutions, this “resource-free” assumption is invalid under computational expensive environment. In this paper, we propose an Computational Resource Optimization Problem (CROP) between initialization and optimization under such environment. We provide a comparison metric among different initialization techniques. Four popular initialization techniques, namely, Pseudo Random Number Generator (PRNG), Opposition-based Learning (OBL), Quasi-Opposition-based Learning (QOBL) and Quadratic Interpolation (QI) are studied. Differential Evolution (DE) is used as the underlying optimization technique, while Chemical Reaction Optimization (CRO) is used to solve CROP. The CEC2014 computational expensive problem set is used as test cases. Our results show the importance of considering resource allocation between initialization and optimization in computational expensive environment.

Social Spider Algorithm (SSA) is a recently proposed general-purpose real-parameter metaheuristic designed to solve global numerical optimization problems. This work systematically benchmarks SSA on a suite of 11 functions with different control parameters. We conduct parameter sensitivity analysis of SSA using advanced non-parametric statistical tests to generate statistically significant conclusion on the best performing parameter settings. The conclusion can be adopted in future work to reduce the effort in parameter tuning. In addition, we perform a success rate test to reveal the impact of the control parameters on the convergence speed of the algorithm.

A newly proposed chemical-reaction-inspired metaheurisic, Chemical Reaction Optimization (CRO), has been applied to many optimization problems in both discrete and continuous domains. To alleviate the effort in tuning parameters, this paper reduces the number of optimization parameters in canonical CRO and develops an adaptive scheme to evolve them. Our proposed Adaptive CRO (ACRO) adapts better to different optimization problems. We perform simulations with ACRO on a widely-used benchmark of continuous problems. The simulation results show that ACRO has superior performance over canonical CRO.

Both video viewing and sharing behaviors in online social networks are of great importance for optimizing traffic engineering and understanding the information diffusion mechanism. However, few models have been proposed to characterize these two behaviors together. In this paper, we first collect the sitewide viewing and sharing statistics of videos in a popular OSN in China, and propose a new model, VSM, to capture the temporal dynamics of video viewing and sharing behaviors during the diffusion process. Specifically, our model can handle the external influence and periodicity properly. The experiments based on the collected dataset demonstrate our VSM can outperform other alternative models in terms of explanatory power and prediction accuracy.

Full-duplex transmission can be easily implemented on a visible light communication (VLC) link. In this paper, we investigate the performance of a VLC network with full-duplex optical links. We propose two contention protocols, named U-ALOHA and FD-CSMA, to utilize the full-duplex capability effectively. Their performances in terms of channel utilization and network throughput are analyzed and simulated and compared with a protocol with half-duplex links. The results show that the proposed protocols can effectively exploit the full-duplex capability. U-ALOHA achieves high channel utilization on the downlink channel while FD-CSMA has good performance on both downlink and uplink channels. Both of them outperform the protocol with half-duplex links when the traffic load is sufficiently high.

The minimum amount of information that should be supplied to transmitters to resolve traffic conflicts in a multiple access system is investigated in this paper. The arriving packets are modeled as the random points of a homogeneous Poisson point process distributed within a unit interval. The minimum information required is equal to the minimum entropy of a random partition that separates the points of the Poisson point process. Only a lower bound of this minimum is known in previous work. We provide an upper bound of this minimum entropy, and the gap with the existing lower bound is shown to be smaller than log2e bits. The upper bound asymptotically achieves the minimum entropy required to resolve per unit traffic. We then analyze the control information used to resolve the traffic conflicts in the splitting algorithm and in the slotted-ALOHA protocol, and identify their gaps with the theoretic bound.

Network protocol performance is closely related to the available information about the network state. However, acquiring such information expends network bandwidth resource. Thus a trade-off exists between the amount of information collected about the network state, and the improved protocol performance due to this information. A framework has been developed to study the optimal trade-off between the amount of collected information and network performance. However, the effect of information delay is not considered. In this paper, we extend the framework to study the impact of information delay on the value of network state information to network protocols, based on which optimal periodic information update policies could be obtained. The framework is illustrated by an example of multiuser scheduling, and observations about the impact of information delay on network protocols are obtained.

With the growth of mobile data and the increasing density of base stations, mobility management in future cellular networks will face great challenges. One such challenge is the high frequency of handovers. With high-frequency handovers, packet delay caused by forwarding in handovers cannot be ignored any more. In this paper, we propose a novel data prefetching strategy to reduce handover delays in cellular networks. The strategy is deployed on software-defined cellular networks, taking advantage of centralized computing capability and packet path control. According to the prediction of a user's next location, we prefetch data packets to possible target base stations, so that the delay caused by packet forwarding in handovers can be reduced. The numerical results show that the data prefetching strategy performs very well. The average delay of the whole user group has a dramatic decrease. We also study the impacts of different parameters on system performance in this paper.

Relaying is a promising technique in cellular networks for improving system capacity and coverage. To facilitate the deployment of relays in remote areas without ready access to the electrical grid, energy-harvesting relays may be deployed. Energy-harvesting has been studied extensively for sensor networks, but it is still an open problem for cellular networks. In this paper, we study the problem of the joint allocation of orthogonal frequency division multiplexing access resource blocks and transmission power to users in a cellular network with energy-harvesting relays. The energy-harvesting process is stochastically described by a time-varying Poisson process. We propose a new metric called survival probability as the selection criteria for an energy-harvesting relay to support data transmissions. We propose a survival probability-based resource allocation (SPRA) algorithm. The algorithm solves the joint problem of resource block allocation, power control, and associating relays to users in a cellular network. We show the achievable data rates of SPRA for different energy harvesting rates.

The performance of networks is greatly affected by the available network state information, such as network topology, channel state, and traffic information. Previous research on network performance analysis is based on the assumption that complete and precise network state information is available. However, in reality, precise information is difficult to obtain, and it requires a large amount of bandwidth resource to maintain accurate information. In this paper, we study networks with memoryless states and address the following question: Given the true network state and a performance measure, what is the minimum information required to achieve a given network performance? We propose a general information-theoretic framework, which can be applied to memoryless network and network protocol, to study the effect of information on network performance. We find that the minimum required information is equal to the mutual information between the true network state and the decision of the controller. To illustrate our approach, we use the framework to determine the lower bound on the channel state information in wireless networks, and then find the coding rate to achieve optimal net data rate. We also study the lower bound on the traffic information required in a distributed network, propose an encoding scheme for exchanging the state information, and then study the gap between the performance of the proposed scheme and the theoretical bound.

Smart grid network facilitates reliable and efficient power generation and transmission. The power system can adjust the amount of electricity generated based on power usage information submitted by end users. Sender authentication and user privacy preservation are two important security issues on this information flow. In this paper, we propose a scheme such that even the control center (power operator) does not know which user makes the requests of using more power or agreements of using less power until the power is actually used. At the end of each billing period (i.e., after electricity usage), the end user can prove to the power operator that it has really requested to use more power or agreed to use less power earlier. To reduce the total traffic volume in the communications network, our scheme allows gateway smart meters to help aggregate power usage information, and the power generators to determine the total amount of power that needs to be generated at different times. To reduce the impact of attacking traffic, our scheme allows gateway smart meters to help filter messages before they reach the control center. Through analysis and experiments, we show that our scheme is both effective and efficient.

Powering radio access networks using renewables, such as wind and solar power, promises dramatic reduction in the network operation cost and the network carbon footprints. However, the spatial variation of the energy field can lead to fluctuations in power supplied to the network and thereby affects its coverage. This warrants research on quantifying the aforementioned negative effect and designing countermeasure techniques, motivating the current work. First, a novel energy field model is presented, in which fixed maximum energy intensity γ occurs at Poisson distributed locations, called energy centers. The intensities fall off from the centers following an exponential decay function of squared distance and the energy intensity at an arbitrary location is given by the decayed intensity from the nearest energy center. The product between the energy center density and the exponential rate of the decay function, denoted as ψ, is shown to determine the energy field distribution. Next, the paper considers a cellular downlink network powered by harvesting energy from the energy field and analyzes its network coverage. For the case of harvesters deployed at the same sites as base stations (BSs), as γ increases, the mobile outage probability is shown to scale as (cγ-πψ+ p), where p is the outage probability corresponding to a flat energy field and c is a constant. Subsequently, a simple scheme is proposed for counteracting the energy randomness by spatial averaging. Specifically, distributed harvesters are deployed in clusters and the generated energy from the same cluster is aggregated and then redistributed to BSs. As the cluster size increases, the power supplied to each BS is shown to converge to a constant proportional to the number of harvesters per BS. Several additional issues are investigated in this paper, including regulation of the power transmission loss in energy aggregation and extensions of the energy field model.

With the recent explosion in mobile data, the energy consumption and carbon footprint of the mobile communications industry is rapidly increasing. It is critical to develop more energy-efficient systems in order to reduce the potential harmful effects to the environment. One potential strategy is to switch off some of the under-utilized base stations during off-peak hours. In this paper, we propose a binary Social Spider Algorithm to give guidelines for selecting base stations to switch off. In our implementation, we use a penalty function to formulate the problem and manage to bypass the large number of constraints in the original optimization problem. We adopt several randomly generated cellular networks for simulation and the results indicate that our algorithm can generate superior performance.

The set covering problem (SCP) is one of the representative combinatorial optimization problems, having many practical applications. This paper investigates the development of an algorithm to solve SCP by employing chemical reaction optimization (CRO), a general-purpose metaheuristic. It is tested on a wide range of benchmark instances of SCP. The simulation results indicate that this algorithm gives outstanding performance compared with other heuristics and metaheuristics in solving SCP.

Optimization techniques are frequently applied in science and engineering research and development. Evolutionary algorithms, as a kind of general-purpose metaheuristic, have been shown to be very effective in solving a wide range of optimization problems. A recently proposed chemical-reaction-inspired metaheuristic, Chemical Reaction Optimization (CRO), has been applied to solve many global optimization problems. However, the functionality of the inter-molecular ineffective collision operator in the canonical CRO design overlaps that of the on-wall ineffective collision operator, which can potential impair the overall performance. In this paper we propose a new inter-molecular ineffective collision operator for CRO for global optimization. To fully utilize our newly proposed operator, we also design a scheme to adapt the algorithm to optimization problems with different search space characteristics. We analyze the performance of our proposed algorithm with a number of widely used benchmark functions. The simulation results indicate that the new algorithm has superior performance over the canonical CRO.

This paper proposes a novel finite Gaussian mixture model to study the population dynamics of evolutionary algorithms on continuous optimization problems. While previous research taking on a dynamical system view has established the transition equation between the density functions of consecutive populations, the equation usually does not have closed-form solutions and can only be applied to very few optimization problems. In this paper, we address this issue by approximating both the population density function of each generation and the objective function by finite Gaussian mixtures. We show that by making such approximations the transition equation can be solved exactly and key statistics, such as the expected mean and the variance of fitness values of the population, can be calculated easily. We also prove that by choosing appropriate values of the parameters, the $L^1$-norm error between our model and the actual population density function can be made arbitrarily small, up until a predefined generation. We present experimental results to show that our model is useful in simulating and examining the dynamics of evolutionary algorithms.

We investigate bandwidth allocation and scheduling in non-cooperative wireless networks as a mixed integer programming problem. Fast Vickrey-Clarke-Groves (VCG) auction-based bandwidth allocation (FABA), incorporating relaxation-based greedy algorithm (RGA) and split-flow-based algorithm (SFA), is proposed by modifying the traditional VCG auction to make it computationally feasible. With incentives provided by FABA, the dominant strategy of any selfish node in the network is to be cooperative so that the system cost is minimized. We implement FABA via a batching-based mechanism which allocates bandwidth for all call routing requests arriving in a certain batching period simultaneously. Our simulation evaluates the performance in terms of system cost, payment-cost ratio, and setup time.

This paper presents a heuristic approach to generate initial feasible solutions for the Unit Commitment (UC) problem in electric power generation. The Chemical Reaction Optimization (CRO) algorithm is implemented to solve this problem. Multiple generator constraints and system constraints are considered. We also program the binary PSO and the Elite PSO (EPSO) for comparison. The proposed heuristic approach is combined with the three optimization algorithms to form H-CRO, H-PSO and H-EPSO. We test the performance of all algorithms on the standard 10-unit system. Simulation results show that the heuristic can improve the performance and CRO provides better convergence than the two PSO algorithms. H-CRO is also tested on a 20-unit and 100-unit system to show its capability. The results provided in this paper suggest that the proposed heuristic approach is a better alternative for solving the UC problem. CRO also has its advantage in optimizing UC problems.

Indoor localization has greatly leveraged applications regarding to location based service (LBS), which witnessed ever-increasing impact on human life. Among the existing localization solutions, WIFI-based received signal strength index (RSSI) fingerprinting is widely used due to desirable features such as universal availability, privacy protection, and low deployment cost. However, to build a robust, accurate RSSI fingerprinting localization system regardless of application occasions confronts two challenges. The first challenge is to construct a fine-grained and up-to-date RSSI map with reasonable labor cost in the training phase, and the second challenge is to deploy effective algorithm in the localization phase. This article illustrates the design and deployment of our indoor localization system targeting at the above mentioned problems. The overall solution is based on five spatio-temporal (S-T) metrics, to improve localization accuracy. Localization performance is evaluated in three indoor scenes at different scales, which show good accuracy with a median error of 1-2m under office environment, and 3-4m accuracy with no less than 70% probability when the environment is extremely crowded and noisy.

WIFI-based received signal strength indicator (RSSI) fingerprinting is widely used for indoor localization due to desirable features such as universal availability, privacy protection, and low deployment cost. The key of RSSI fingerprinting is to construct a trustworthy RSSI map, which contains the measurements of received access point (AP) signal strengths at different calibration points. Location can be estimated by matching live RSSIs with the RSSI map. However, a fine-grained map requires much labor and time. This calls for developing efficient interpolation and approximation methods. Besides, due to environmental changes, the RSSI map requires periodical updates to guarantee localization accuracy. In this paper, we propose a spatio-temporal (S-T) similarity model which uses the S-T correlation to construct a fine-grained and up-to-date RSSI map. Five S-T correlation metrics are proposed, i.e., the spatial distance, signal similarity, similarity likelihood, RSSI vector distance, and the S-T reliability. This model is evaluated based on experiments in our indoor WIFI positioning system test bed. Results show improvements in both the interpolation accuracy (up to 7%) and localization accuracy (up to 32%), compared to four commonly used RSSI map construction methods, namely, linear interpolation, cubic interpolation, nearest neighbor interpolation, and compressive sensing.

Multihop communication has attracted a lot of attention as an effective transmission strategy for future cellular networks. It can be an effective technique to increase data rate and enhance coverage. However, multihop relaying with a single Radio Access Technology (RAT) may not be able to provide the flexibility required for wireless cellular network which has moved towards heterogeneity. Therefore, multihop cellular network needs to be integrated with multi-RAT to provide the required flexibility in the cellular architecture. When multihop cellular network is provided with multi-RAT capability, RAT selection for a certain transmission session becomes part of its resource management. RAT selection decision depends on the characteristics of the radio links and the availability of resources in the different RATs. A careful control of power between user and relay is required to exploit multi-RAT and multihop capabilities to their maximum potential. In this paper, we formulated a RAT selection and a transmission power control for a mobile user and relay using an indifference curve. We selected the RAT and allocated the power for a single users transmission such that the interference created by the mobile user and the relay is minimized and the achievable data rate is satisfied.

Passengers in city buses are possibly one of the main contributors to the increase in mobile traffic in cellular networks. Instead of each passenger accessing the cellular base station, we may deploy a small cell on the bus to serve these passengers. To reap the benefits of this deployment in the cellular network, resource allocation of the network needs to be addressed carefully. We call the small cells deployed in city buses as moving small cells. In this paper, we propose a probabilistic graph based resource allocation (PGRA) algorithm in a cellular network with moving small cells. We exploit the headway characteristics of city buses to study the interference relationship between different moving small cells. Our performance metric is the number of resource blocks used. Our performance evaluation shows an average decrease of 19.84% in the number of RBs used with moving small cells in the network as compared to a scenario without moving small cells, requiring each passenger to access the base station.

The combination of loss-based TCP and drop-tail routers often results in full buffers, creating large queueing delays. The challenge with parameter tuning and the drastic consequence of improper tuning have discouraged network administrators from enabling AQM even when routers support it. To address this problem, we propose a novel design principle for AQM, called the pricing-link-by-time (PLT) principle. PLT increases the link price as the backlog stays above a threshold β, and resets the price once the backlog goes below β. We prove that such a system exhibits cyclic behavior that is robust against changes in network environment and protocol parameters. While β approximately controls the level of backlog, the backlog dynamics are invariant for β across a wide range of values. Therefore, β can be chosen to reduce delay without undermining system performance. We validate these analytical results using packet-level simulation.

Topology-transparent scheduling algorithms can work well in mobile ad hoc networks, since they are oblivious to the network topology changes and can provide throughput and delay guarantees. Recently, it has been shown that topology-transparent algorithms can provide comparable or even better performance, compared to topology-dependent algorithms. However, most existing topology-transparent scheduling algorithms are designed for single channel networks and few work have been done in multi-channel (MC) networks. In this paper, we focus on broadcasting and propose a distributed multi-channel topology-transparent broadcast scheduling algorithm. In our algorithm, each node randomly selects one or several subchannels to transmit and utilizes both assigned and unassigned slots efficiently. We study the performance of our algorithm analytically and obtain the optimal number of selected subchannels that maximizes the throughput. The simulation results show that our proposed algorithm outperforms existing multi-channel topology-transparent broadcast scheduling algorithms dramatically. More importantly, our work answers the question “Will dividing the spectrum into subchannels lead to a better network performance?” under different network configurations.

In a vehicle-to-grid (V2G) system, aggregators coordinate the charging/discharging schedules of electric vehicle (EV) batteries so that they can collectively form a massive energy storage system to provide ancillary services, such as frequency regulation, to the power grid. In this paper, the optimal charging/discharging scheduling between one aggregator and its coordinated EVs for the provision of the regulation service is studied. We propose a scheduling method that assures adequate charging of EVs and the quality of the regulation service at the same time. First, the scheduling problem is formulated as a convex optimization problem relying on accurate forecasts of the regulation demand. By exploiting the zero-energy nature of the regulation service, the forecast-based scheduling in turn degenerates to an online scheduling problem to cope with the high uncertainty in the forecasts. Decentralized algorithms based on the gradient projection method are designed to solve the optimization problems, enabling each EV to solve its local problem and to obtain its own schedule. Our simulation study of 1000 EVs shows that the proposed online scheduling can perform nearly as well as the forecast-based scheduling, and it is able to smooth out the real-time power fluctuations of the grid, demonstrating the potential of V2G in providing the regulation service.

In this paper, we propose a navigation scheme that utilizes the online road information collected by a vehicular ad hoc network (VANET) to guide the drivers to desired destinations in a real-time and distributed manner. The proposed scheme has the advantage of using real-time road conditions to compute a better route and at the same time, the information source can be properly authenticated. To protect the privacy of the drivers, the query (destination) and the driver who issues the query are guaranteed to be unlinkable to any party including the trusted authority. We make use of the idea of anonymous credential to achieve this goal. In addition to authentication and privacy preserving, our scheme fulfills all other necessary security requirements. Using the real maps of New York and California, we conducted a simulation study on our scheme showing that it is effective in terms of processing delay and providing routes of much shorter traveling time.

Deflection routing is a feasible approach to resolve the output contention problem in packet-switched networks when buffering of packets is not practical. In this paper, we investigate the performance of multichannel deflection-routed networks with no packet injection control, strict packet injection control, and a simple token-bucket-based packet injection control. The analytical performance models of multichannel deflection-routed networks with strict packet injection control are derived. Simulation results show that the analytical models can accurately predict the performance regardless of the network topology, number of channels, and packet injection control methods. We observed that the end-to-end throughput-delay and the packet re-transmission performance at sources can be largely improved by using simple packet injection control mechanisms such as the proposed token-bucket-based method.

Characterizing the video diffusion in online social networks (OSNs) is not only instructive for network traffic engineering, but also provides insights into the information diffusion process. A number of continuous-time diffusion models have been proposed to describe video diffusion under the assumption that the activation latency along social links follows a single parametric distribution. However, such assumption has not been empirically verified. Moreover, a user usually has multiple activated neighbors with different activation times, and it is hard to distinguish the different contributions of these multiple potential sources. To fill this gap, we study the multiple-source-driven asynchronous information diffusion problem based on substantial video diffusion traces. Specifically, we first investigate the latency of information propagation along social links and define the single-source (SS) activation latency for an OSN user. We find that the SS activation latency follows the exponential mixture model. Then we develop an analytical framework which incorporates the temporal factor and the influence of multiple sources to describe the influence propagation process. We show that one's activation probability decreases exponentially with time. We also show that the time shift of the exponential function is only determined by the most recent source (MRS) active user, but the total activation probability is the combination of influence exerted by all active neighbors. Based on these discoveries, we develop a multi-source-driven asynchronous diffusion model (MADM). Using maximum likelihood techniques, we develop an algorithm based on expectation maximization (EM) to learn model parameters, and validate our proposed model with real data. The experimental results show that the MADM obtains better prediction accuracy under various evaluation metrics.

Recent advances in the physical layer have enabled wireless devices to have multiple packet reception (MPR) capability, which is the capability of decoding more than one packet, simultaneously, when concurrent transmissions occur. In this paper, we focus on the interaction between the MPR physical layer and the medium access control (MAC) layer. Some random access MAC protocols have been proposed to improve the network performance by exploiting the powerful MPR capability. However, there are very few investigations on the schedule-based MAC protocols. We propose a novel m-MPR-l-code topology-transparent scheduling ((m, l)-TTS) algorithm for mobile ad hoc networks with MPR, where m indicates the maximum number of concurrent transmissions being decoded, and l is the number of codes assigned to each user. Our algorithm can take full advantage of the MPR capability to improve the network performance. The minimum guaranteed throughput and average throughput of our algorithm are studied analytically. The improvement of our (m, l)-TTS algorithm over the conventional topology-transparent scheduling algorithms with the collision-based reception model is linear with m. The simulation results show that our proposed algorithm performs better than slotted ALOHA as well.

An electric vehicle (EV) may be used as energy storage which allows the bi-directional electricity flow between the vehicle's battery and the electric power grid. In order to flatten the load profile of the electricity system, EV scheduling has become a hot research topic in recent years. In this paper, we propose a new formulation of the joint scheduling of EV and Unit Commitment (UC), called EVUC. Our formulation considers the characteristics of EVs while optimizing the system total running cost. We employ Chemical Reaction Optimization (CRO), a general-purpose optimization algorithm to solve this problem and the simulation results on a widely used set of instances indicate that CRO can effectively optimize this problem.

The rapid development of online social networks (OSN) makes viral marketing through the word-of-mouth effect possible. Designing effective marketing strategy is critical in monetizing the social networks. However, most existing studies focus on conducting effective influence maximization analysis to propagate information widely instead of explicitly incorporating the pricing factor to design intelligent marketing strategies. In this paper, we study the sequential pricing models in which a monopoly seller iteratively posts a sequence of public unique prices for a product in stages, and any interested buyer can buy the product at the posted price at a particular stage if his valuation is above the posted price. Specifically, our model is built on the multi-state diffusion scheme where an active user may be in the “AWARE” and “ADOPT” states. Users in “ADOPT” state could influence their neighbors' valuation for the given product. To realize the goal of revenue maximization, we develop a Dynamic Programming Based Heuristic (DPBH) to obtain the optimal pricing sequence. Application of the DPBH in the revenue maximization problem shows that it performs well in both the expected revenue achieved and in running time. This leads to fundamental ramifications to many related OSN marketing applications.

As one of the core components in wide-area monitoring systems (WAMS), phasor measurement units (PMUs) acquire highly accurate and time-synchronized phasor data at high frequency for smart grid monitoring, protection, and control. Despite the advantages of PMUs, they do generate much data and create a heavy burden on the communication network. One way of alleviating such burden is to install phasor data concentrators (PDC) across the power system to concentrate data generated by the PMUs. Although PDCs are expensive as well, this may still be a much cheaper and more practical option than building a high bandwidth network for WAMS. Therefore, it is very important to solve the optimal PDC installation problem so as to achieve a desired level of traffic reduction. This paper is the first to address this problem and we give solutions for the IEEE 14-bus, 30-bus, and 57-bus systems.

In this paper we consider the influence maximization problem in social networks, and propose an Int-Div heuristic to solve it. Motivated by the concepts of intensification and diversification in optimization problems, Int-Div accounts for both of these two concepts to estimate the social influence, and selects nodes based on marginal influence increment. It is applicable to the two widely used diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model. The proposed strategy is evaluated through experiments on a collaboration network and a who-trust-whom online social network, respectively, and compared with several existing heuristics, namely, the pure greedy algorithm, the centrality-based scheme, the single discount and the degree discount heuristics. We find that our proposed strategy offers better performance than the centrality-based scheme, the single discount and the degree discount heuristics, while achieving approximately the same performance as the greedy algorithm. The computational load is dramatically lower than the greedy heuristic.

The congestion control mechanisms in the standardized Transmission Control Protocol (TCP) may misinterpret packet reordering as congestive loss, leading to spurious congestion response and under-utilization of network capacity. Therefore, many TCP enhancements have been proposed to better differentiate between packet reordering and congestive loss, in order to enhance the reordering robustness (RR) of TCP. Since such enhancements are incrementally deployed, it is important to study the interactions of TCP flows with heterogeneous RR. This paper presents the first systematic study of such interactions by exploring how changing RR of TCP flows influences the bandwidth sharing among these flows. We define the quantified RR (QRR) of a TCP flow as the probability that packet reordering causes congestion response. We analyze the variation of bandwidth sharing as QRR changes. This leads to the discovery of several interesting properties. Most notably, we discover the counter-intuitive result that changing one flow's QRR does not affect its competing flows in certain network topologies. We further characterize the deviation, from the ideal case of bandwidth sharing, as RR changes. We find that enhancing RR of a flow may increase, rather than decrease, the deviation in some typical network scenarios.

Network protocol performance is closely related to knowledge about the network state. However, acquiring such knowledge expends network bandwidth resource. Thus a trade off exists between the amount of bandwidth resource expended in acquiring knowledge about network state, and the improved protocol performance due to such knowledge. Previous work used rate distortion theory to calculate the minimum information required for certain network performance. However, this limit is asymptotic and might not be achievable due to the introduced infinite delay. This work develops a non-asymptotic framework to find a practical bound of the required information for certain network performance, and the strategies for implementing network information collection. The framework is illustrated by a wireless scheduling problem to show the quantitative relationship between collected traffic information and network throughput. Furthermore, we calculate the effective data rate by considering the overhead of network information collection, and determine the optimal resource allocation between information collection and data transmission.

Improvement in signal quality and service quality by femtocells offers a natural opportunity for them to be deployed in vehicles. However, resource allocation with mobile femtocells becomes challenging due to the dynamic interference patterns as the mobile femtocells move. In this paper, we introduce the problem of allocating resources in a cellular network with mobile femtocells. We consider two types of femtocells in the scenario, a) fixed femtocells (deployed in stationary location e.g train stations); and b) mobile femtocell with deterministic mobility (e.g deployed on trains). We use the speed and path information of the mobile femtocells to determine the interference relationships between different femtocells at different time instants and represent it as a time interval dependent interference graph. Finally using the interference graph, we proposed a cluster-based resource allocation algorithm. Performance analysis shows that the allocated resources with mobile femtocell in the scenario are close to the ones without mobile femtocells and much less than a random allocation.

The class of additive-increase/multiplicative-decrease (AIMD) algorithms constitutes a key mechanism for congestion control in modern communication networks, like the current Internet. The algorithmic behaviour may, however, be distorted when wireless links are present. Specifically, spurious window reductions may be triggered due to packet reordering and non-congestive loss. In this paper, we develop a framework for AIMD in TCP to analyze the aforementioned problem. The framework enables a systematic analysis of the existing AIMD-based TCP variants and assists in the design of new TCP variants. It classifies the existing AIMD-based TCP variants into two main streams, known as compensators and differentiators, and develops a generic expression that covers the rate adaptation processes of both approaches. It further identifies a new approach in enhancing the performance of TCP, known as the compensation scheme. A tax-rebate approach is proposed as an approximation of the compensation scheme, and used to enhance the AIMD-based TCP variants to offer unified solutions for effective congestion control, sequencing control, and error control. In traditional wired networks, the new family of TCP variants with the proposed enhancements automatically preserves the same inter-flow fairness and TCP friendliness. We have conducted a series of simulations to examine their performance under various network scenarios. In most scenarios, significant performance gains are attained.

We study multi path routing with traffic assignment in selfish networks. Based on the Vickrey-Clarke-Groves (VCG) auction, an optimal and strategy-proof scheme, known as optimal auction-based multipath routing (OAMR), is developed. However, OAMR is computationally expensive and cannot run in real time when the network size is large. Therefore, we propose sequential auction-based multi path routing (SAMR). SAMR handles routing requests sequentially using some greedy strategies. In particular, with reference to the Ausubel auction, we develop a water-draining algorithm to assign the traffic of a request among its available paths and determine the payment of the transmission in approximately constant time. Our simulation results show that SAMR can rapidly compute the allocations and payments of requests with small sacrifice on the system cost. Moreover, various sequencing strategies for sequential auction are also investigated.

Studying the propagation of social influence is critical in the analysis of online social networks. While most existing work focuses on the expected number of users influenced, the detailed probability distribution of users influenced is also significant. However, determining the probability distribution of the final influence propagation state is difficult. Monte-Carlo simulations may be used, but are computationally expensive. In this paper, we develop an analytical model for the influence propagation process in online social networks based on discrete-time Markov chains, and deduce a closed-form equation for the n-step transition probability matrix. We show that given any initial state, the probability distribution of the final influence propagation state may be easily obtained from a matrix product. This provides a powerful tool to further understand social influence propagation.

In this paper we analyze influence maximization for noncooperative social networks under the Independent Cascade Model. We propose a model of noncooperative nodes and prove some interesting properties of this model. Based on this, we further develop a game-theoretic model to characterize the behavior of noncooperative nodes, and design a Vickrey-Clarke-Groves-like scheme to incentivise cooperation. An advertiser can resolve the negative effect of noncooperation with our proposed solution. Evaluation on large social networks demonstrates the importance of cooperation and the effectiveness of our proposed incentive scheme in maximizing influence. We also discuss the budget allocation between seed nodes activation and incentives to non-seed nodes.

Although the techniques of cooperative transmission have been developed for terrestrial sensor networks in recent years to improve the bit‐error‐rate (BER) performance, the unique characteristics of the underwater acoustic communication channel, such as large and variable propagation delay and the three‐dimensional network topology, make it necessary to reconsider the implementation and analysis of cooperative transmission in underwater acoustic networks. In this study, two asynchronous forwarding schemes, namely underwater amplify‐and‐forward (UAF) and underwater decode‐and‐forward (UDF), are proposed. Although the fading model for underwater channel is complex and there is still no consensus in the research community on a model which is applicable for all underwater channels, the authors simulation results show that both UDF and UAF have better performance than direct transmission under different underwater channel configurations, and there is a breathing effect for BER performance improvement caused by underwater multi‐path fading. Finally, some insights on choosing the proper parameters to improve performance of underwater cooperative transmission are provided.

A novel general-purpose optimization method, chemical reaction optimization (CRO), is a population-based metaheuristic inspired by the phenomenon of interactions between molecules in a chemical reaction process. CRO has demonstrated its competitive edge over existing methods in solving many real-world problems. However, all studies concerning CRO have been empirical in nature and no theoretical analysis has been conducted to study its convergence properties. In this paper, we present some convergence results for several generic versions of CRO, each of which adopts different combinations of elementary reactions. We investigate the limiting behavior of CRO. By modeling CRO as a finite absorbing Markov chain, we show that CRO converges to a global optimum solution with a probability arbitrarily close to one when time tends to infinity. Our results also show that the convergence of CRO is determined by both the elementary reactions and the total energy of the system. Moreover, we also study and discuss the finite time behavior of CRO.

Cognitive radio is a promising technology for increasing the system capacity by using the radio spectrum more effectively. It has been widely studied recently and one important problem in this new paradigm is the allocation of radio spectrum to secondary users effectively in the presence of primary users. We call it the cognitive radio spectrum allocation problem (CRSAP) in this paper. In the conventional problem formulation, a secondary user can be either on or off and its interference range becomes maximum or zero, respectively. We first develop a solution to CRSAP based on the newly proposed chemical reaction-inspired metaheuristic called Chemical Reaction Optimization (CRO). We study different utility functions, accounting for utilization and fairness, with the consideration of the hardware constraint, and compare the performance of our proposed CRO-based algorithm with existing ones. Simulation results show that the CRO-based algorithm always outperforms the others dramatically. Next, by allowing adjustable transmission power, we propose power-controlled CRSAP (PC-CRSAP), a new formulation to the problem with the consideration of spatial diversity. We design a two-phase algorithm to solve PC-CRSAP, and again simulation results show excellent performance.

In this paper, we utilize Chemical Reaction Optimization (CRO), a newly proposed metaheuristic for global optimization, to design Fuzzy Rule-Based Systems (FRBSs). CRO imitates the interactions of molecules in a chemical reaction. The molecular structure corresponds to a solution, and the potential energy is analogous to the objective function value. Molecules are driven toward the lowest energy stable state, which corresponds to the global optimum of the problem. In the realm of modeling with fuzzy rule-based systems, automatic derivation of fuzzy rules from numerical data plays a critical role. We propose to use CRO with Cooperative Rules (COR) to solve the fuzzy rule learning problem in FRBS. We formulate the learning process of FRBS in the form of a combinatorial optimization problem. Our proposed method COR-CRO is evaluated by two fuzzy modeling benchmarks and compared with other learning algorithms. Simulation results demonstrate that COR-CRO is highly competitive and outperforms many other existing optimization methods.

This paper presents an implementation of the Chemical Reaction Optimization (CRO) algorithm to solve the optimal power flow (OPF) problem in power systems with the objective of minimizing generation costs. Multiple constraints, such as the balance of the power, bus voltage magnitude limits, transmission line flow limits, transformer tap settings, etc., are considered. We adapt the CRO framework to the OPF problem by redesigning the elementary reaction operators. We perform simulations on the standard IEEE-14, -30, and -57 bus benchmark systems. We compare the perform of CRO with other reported evolutionary algorithms in the IEEE-30 test case. Simulation results show that CRO can obtain a solution with the lowest cost, when compared with other algorithms. To be more complete, we also give the average result for the IEEE-30 case, and the best and average results for the IEEE-14 and -57 test cases. The results given in this paper suggest that CRO is a better alternative for solving the OPF problem, as well as its variants for the future smart grid.

The analysis of short tandem repeats (STRs) in DNA sequences has become an attractive method for determining the genetic profile of an individual. Here we focus on a more general and practical issue named short adjacent repeats identification problem (SARIP), which is extended from STR by allowing short gaps between neighboring units. Presently, the best available solution to SARIP is BASARD, which uses Markov chain Monte Carlo algorithms to determine the posterior estimate. However, the computational complexity and the tendency to get stuck in a local mode lower the efficiency of BASARD and impede its wide application. In this paper, we prove that SARIP is NP-hard, and we also solve it with Chemical Reaction Optimization (CRO), a recently developed metaheuristic approach. CRO mimics the interactions of molecules in a chemical reaction and it can explore the solution space efficiently to find the optimal or near optimal solution(s). We test the CRO algorithm with both synthetic and real data, and compare its performance in mode searching with BASARD. Simulation results show that CRO enjoys dozens of times, or even a hundred times shorter computational time compared with BASARD. It is also demonstrated that CRO can obtain the global optima most of the time. Moreover, CRO is more stable in different runs, which is of great importance in practical use. Thus, CRO is by far the best method on SARIP.

Chemical Reaction Optimization (CRO) is a powerful metaheuristic which mimics the interactions of molecules in chemical reactions to search for the global optimum. The perturbation function greatly influences the performance of CRO on solving different continuous problems. In this paper, we study four different probability distributions, namely, the Gaussian distribution, the Cauchy distribution, the exponential distribution, and a modified Rayleigh distribution, for the perturbation function of CRO. Different distributions have different impacts on the solutions. The distributions are tested by a set of wellknown benchmark functions and simulation results show that problems with different characteristics have different preference on the distribution function. Our study gives guidelines to design CRO for different types of optimization problems.

Air pollution monitoring is a very popular research topic and many monitoring systems have been developed. In this paper, we formulate the Bus Sensor Deployment Problem (BSDP) to select the bus routes on which sensors are deployed, and we use Chemical Reaction Optimization (CRO) to solve BSDP. CRO is a recently proposed metaheuristic designed to solve a wide range of optimization problems. Using the real world data, namely Hong Kong Island bus route data, we perform a series of simulations and the results show that CRO is capable of solving this optimization problem efficiently.

The Max-Cut problem is a classical NP-hard combinatorial optimization problem. It consists of dividing the vertices of a weighted graph into two subsets, such that the sum of the weights of the edges connecting the two subsets is maximized. Although semidefinite relaxation algorithms for Max-Cut have been proved to be of high quality and offer performance guarantees, in practice, metaheuristic algorithms are still the first option to solve large Max-Cut instances. In this paper, we present the first effort at combining semidefinite programming (SDP) with metaheuristic algorithm (Memetic Algorithm) to solve the Max-Cut problem. Based on the solution of semidefinite relaxation, we use Goemans-Williamson Algorithm to seed high quality solutions to the initial population for the memetic algorithm. Experimental results on well-known benchmark problems show that our new hybrid algorithm is capable of obtaining better solutions in the initial population generation stage than previous algorithms, and the overall performance of our algorithm is better than one of the best existing algorithms. Besides, new best solutions for 14 benchmark problems were found by our algorithm.

The rapid development of online social networks (OSN) renders them a popular mechanism for information diffusion. Studying the temporal characteristics is critical in understanding the diffusion process. However, due to the lack of well-defined propagation data, hardly any study addresses the temporal feature of information diffusion in OSN. In this paper, we present a measurement study on information diffusion in the Renren social network. We investigate the latency of information propagation along social links and define the “activation time” for an OSN user, and find that the activation time follows the lognormal distribution. Based on this, we develop two new information diffusion models incorporating asynchronous activation times. Application of the models in the influence maximization problem shows that they capture the temporal diffusion behavior very well. This leads to fundamental ramifications to many related OSN applications.

In this paper, we consider the problem of maximizing information propagation with noncooperative nodes in social networks. We generalize the linear threshold model to take node noncooperation into consideration and provide a provable approximation guarantees for the noncooperative influence maximization problem. We propose an analytical model based on the generalized maximum flow problem to characterize the noncooperative behavior of an individual node in maximizing influence. Based on this, we develop a new seed node selection strategy, under the linear threshold model, to account for user noncooperativeness. Extensive simulations on large collaboration networks show that our proposed flow-based strategy outperforms the weighted degree scheme under various noncooperative scenarios. The evaluation also validates the importance of cooperation and incentives in maximizing influence.

In order to maintain a small, stable backlog at the router buffer, active queue management (AQM) algorithms drop packets probabilistically at the onset of congestion, leading to backoffs by Transmission Control Protocol (TCP) flows. However, wireless losses may be misinterpreted as congestive losses and induce spurious backoffs. In this paper, we raise the basic question: Can AQM maintain a stable, small backlog under wireless losses? We find that the representative AQM, random early detection (RED), fails to maintain a stable backlog under time-varying wireless losses. We find that the key to resolving the problem is to robustly track the backlog to a preset reference level, and apply the control-theoretic vehicle, internal model principle, to realize such tracking. We further devise the integral controller (IC) as an embodiment of the principle. Our simulation results show that IC is robust against time-varying wireless losses under various network scenarios.

Transmission scheduling is a key problem in mobile ad hoc networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple-access (TDMA) frame length in mobile ad hoc networks. Most algorithms are dependent on the exact network topology and cannot adapt to the dynamic topology in a mobile wireless network. To overcome this limitation, several topology-transparent scheduling algorithms have been proposed. The slots are assigned to guarantee that there is at least one collision-free time slot in each frame. In this paper, we consider multicast and broadcast, and propose a novel topology-transparent distributed scheduling algorithm. Instead of guaranteeing at least one collision-free transmission, the proposed algorithm guarantees one successful transmission exceeding a given probability, and achieves a much better average throughput. The simulation results show that the performance of our proposed algorithm is much better than the conventional TDMA and other existing algorithms in most cases.

Optimization problems can generally be classified as continuous and discrete, based on the nature of the solution space. A recently developed chemical-reaction-inspired metaheuristic, called chemical reaction optimization (CRO), has been shown to perform well in many optimization problems in the discrete domain. This paper is dedicated to proposing a real-coded version of CRO, namely, RCCRO, to solve continuous optimization problems. We compare the performance of RCCRO with a large number of optimization techniques on a large set of standard continuous benchmark functions. We find that RCCRO outperforms all the others on the average. We also propose an adaptive scheme for RCCRO which can improve the performance effectively. This shows that CRO is suitable for solving problems in the continuous domain.

Social-based forwarding algorithms provide a new perspective on the study of routing in opportunistic mobile networks, and all of these schemes assume a uniform pattern for message generating rule. However, this is unconvincing due to the heterogeneity of contact rates in human communication patterns. In this paper we propose three social-based communication pattern models and utilize them to evaluate the network performance of different social-based routing protocols based on several human mobility traces. We find that communication patterns could significantly affect the network performance and the influence degree largely depends on the social metrics which these communication patterns are based on. We contend that considering communication pattern is quite important for designing a practical routing algorithm in opportunistic mobile networks.

In this paper, we study the problem of discovering multiple resource holders and how to evaluate a node's satisfaction in query incentive networks. Utilizing an acyclic tree, we show that query propagation has a nature of exponential start, polynomial growth, and eventually becoming a constant. We model the query propagation as an extensive game, obtain nodes' greedy behaviors from Nash equilibrium analysis, and show the impairment of greedy behaviors via a repeated Prisoner's Dilemma. We demonstrate that cooperation enforcement is required to achieve the optimal state of resource discovery.

The vehicular ad hoc network (VANET) is an emerging type of network which enables vehicles on roads to inter-communicate for driving safety. The basic idea is to allow arbitrary vehicles to broadcast ad hoc messages (e.g. traffic accidents) to other vehicles. However, this raises the concern of security and privacy. Messages should be signed and verified before they are trusted while the real identity of vehicles should not be revealed, but traceable by authorized party. Existing solutions either rely too heavily on a tamper-proof hardware device, or do not have an effective message verification scheme. In this paper, we propose a multiple level authentication scheme which still makes use of tamper-proof devices but the strong assumption that a long-term system master secret is preloaded into all tamper-proof devices is removed. Instead the master secret can be updated if needed to increase the security level. On the other hand, messages sent by vehicles are classified into two types - regular messages and urgent messages. Regular messages can be verified by neighboring vehicles by means of Hash-based Message Authentication Code (HMAC) while urgent messages can only be verified with the aid of RSUs nearby by means of a conditional privacy-preserving authentication scheme.

Evolutionary algorithms (EAs) are very popular tools to design and evolve artificial neural networks (ANNs), especially to train them. These methods have advantages over the conventional backpropagation (BP) method because of their low computational requirement when searching in a large solution space. In this paper, we employ Chemical Reaction Optimization (CRO), a newly developed global optimization method, to replace BP in training neural networks. CRO is a population-based metaheuristics mimicking the transition of molecules and their interactions in a chemical reaction. Simulation results show that CRO outperforms many EA strategies commonly used to train neural networks.

A smart grid network adjusts power allocation by collecting information about the power usage of the customers in real-time. Authentication and user privacy preservation are the two major concerns on smart grid security. Authentication schemes that preserve users' privacy from third parties, but not from the power operator, have been proposed. In this paper, we propose a scheme that preserves users' privacy information, including their daily electricity usage pattern from third parties as well as from the power operator. At the same time, the scheme ensures that authentication can be properly done. These two properties are achieved by using anonymous credential under the principle of blind signature. Basically, a customer generates a set of credentials by himself and asks the control center to blindly sign them. When the customer needs to request more power later on, he presents the signed credential to the control center as proof of his identity. Implementation and analysis show that our scheme is feasible in terms of a number of performance measures such as the signing time and the credential collision rate.

In this paper we consider the problem of maximizing information propagation in social networks. To solve it, we introduce a probabilistic maximum coverage problem, and further purpose a cluster-based heuristic and a neighborhood-removal heuristic for two basic diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model, respectively. Our proposed strategies are compared with the pure greedy algorithm and centrality-based schemes via experiments on large collaboration networks. We find that our proposed algorithms perform better than centrality-based schemes and achieve approximately the same performance as the greedy algorithm. Moreover, the computational load is significantly reduced compared with the greedy heuristic.

Network coding may improve network efficiency. However, it is not necessary to code every link to meet a given transmission rate. In this paper, we consider the NP-hard problem of minimizing the number of coding links of a network for a given target transmission rate. Chemical Reaction Optimization (CRO) is a general purpose metaheuristic, which have been demonstrated to be effective in many optimization problems. We adopt the CRO framework to develop an algorithm to solve this NP-hard problem. Simulation results show that CRO outperforms existing algorithms with two sets of test network topologies.

In this paper, we develop a new scheme to effectively detect the primary signal in a cognitive radio (CR) network. We propose a packet transmission scheme with random censoring. The proposed scheme, known as Censored with Probability Fusion Method~(CPFM), controls the information exchange in cooperative spectrum sensing so as to improve the detection performance and reduce the cooperation overheads. In CPFM, each participating CR device independently senses the spectrum. Based on the energy level received, it may transmit, not transmit, or randomly transmit its observation packet to the fusion centre. The fusion centre then determines the spectrum condition based on all packets received. The simulation results show that CPFM outperforms other detection schemes in terms of improved detection probability and smaller control overheads.

Online social search (OSS) brings forth a new way to harness the Internet for answers. In this paper, we study the non-cooperation problem in OSS. We propose an analytical model that captures the behavior of OSS nodes, and, from a gaming-strategy point of view, analyze various strategies an individual node can utilize to allocate its awareness capacity. Based on this we derive the Pareto inefficiency in terms of the system cost. We also propose an incentive scheme under which the optimal state of individual nodes is also optimal for the whole system. Extensive simulations show that the strategy under our proposed incentive mechanism outperforms other strategies in terms of the system cost and the search success rate. To the best of our knowledge, this is the first study of the tragedy-of-the-commons problem in OSS.

Cellular networks are currently facing the challenges of mobile data explosion. High-end mobile phones and laptops double their mobile data traffic every year and this trend is expected to continue given the rapid development of mobile social applications. It is imperative that novel architectures be developed to handle such voluminous mobile data. In this paper, we propose and evaluate an integrated architecture exploiting the opportunistic networking paradigm to migrate data traffic from cellular networks to metropolitan WiFi access points (APs). To quantify the benefits of deploying such an architecture, we consider the case of bulk file transfer and video streaming over 3G networks and simulate data delivery using real mobility data set of 500 taxis in an urban area. We are the first to quantitatively evaluate the gains of city-wide WiFi offloading using large scale real traces. Our results give the numbers of APs needed for different requirements of quality of service for data delivery in large metropolitan area. We show that even with a sparse WiFi network the delivery performance can be significantly improved. This effort serves as an important feasibility study and provides guidelines for operators to evaluate the possibility and cost of this solution.

Most replication-based packet forwarding algorithms in opportunistic networks neglect the fairness issue on the success rate distribution among all participants. In this paper we discuss the fairness evaluation on success rate, and propose a new fair packet forwarding strategy which operates as a plugin for traditional utility-based routing protocols. We compare the performance of our strategy with several well-known routing schemes via both a synthetic contact model and real human mobility traces. We find that our strategy improves the balance of success rates among users while maintaining approximately the same system throughput. In addition, our scheme reduces the cost of traditional utility-based routing protocols.

We consider the querying service (e.g., location-based query service) in vehicular ad hoc networks (VANETs). Querying service has been studied in various kinds of networks such as traditional mobile phone networks and other mobile ad hoc networks. However, existing schemes are either not suitable for VANETs due to their highly dynamic environment or do not provide a privacy-preserving solution. In this paper, we first discuss the security concerns of providing a querying service that ensures that a query will not be linkable to the querier. Then, we briefly highlight the characteristics of VANETs, which make the problem different from other types of networks. Finally, we propose a solution for solving the problem by using techniques of pseudoidentity, indistinguishable credentials, and oblivious transfer. We show that, although all infrastructure units collude, it is still impossible to link the real identity of the user to a query. Based on our simulation study, we show that our scheme is effective in terms of processing delay, message overhead, and success rate.

For the low-cost hardware-based intrusion detection systems, this paper proposes a memory-efficient parallel string matching scheme. In order to reduce the number of state transitions, the finite state machine tiles in a string matcher adopt bit-level input symbols. Long target patterns are divided into subpatterns with a fixed length; deterministic finite automata are built with the subpatterns. Using the pattern dividing, the variety of target pattern lengths can be mitigated, so that memory usage in homogeneous string matchers can be efficient. In order to identify each original long pattern being divided, a two-stage sequential matching scheme is proposed for the successive matches with subpatterns. Experimental results show that total memory requirements decrease on average by 47.8 percent and 62.8 percent for Snort and ClamAV rule sets, in comparison with several existing bit-split string matching methods.

Evolutionary Monte Carlo (EMC) algorithm is an effective and powerful method to sample complicated distributions. Short adjacent repeats identification problem (SARIP), i.e., searching for the common sequence pattern in multiple DNA sequences, is considered as one of the key challenges in the field of bioinformatics. A recently proposed Markov chain Monte Carlo (MCMC) algorithm has demonstrated its effectiveness in solving SARIP. However, high computation time and inevitable local optima hinder its wide application. In this paper, we apply EMC to parallelize the MCMC algorithm to solve SARIP. Our proposed EMC scheme is implemented on a parallel platform and the simulation results show that, compared with the conventional MCMC algorithm, EMC not only improves the quality of final solution but also reduces the computation time.

In this paper, we propose a novel concept for a social TV application targeting the demographic of viewers enjoying live sports events, such as road bicycle racing. We intend to enhance the viewing experiences of spectators with sensor-fitted bikes tied to an interactive biking environment on television. The system enables a new form of personalized, physical, and virtual-reality interaction between viewers and a TV program, as well as interactions within or between communities of friends. We also describe a prototype we have implemented to demonstrate the feasibility of our idea. The prototype, my second bike, uses a 3D mirrored world environment (Google Earth) to visually represent participating spectators, competing athletes and outdoor bikers. We contend that the system has the potential to attract and support a large user base on account of its scalability, ease of deployment and ability to promote audience participation in live sports events on TV.

Peer-to-peer (P2P) live streaming applications are very popular in recent years and a Markov open queueing network model was developed to study the population dynamics in P2P live streaming. Based on the model, we deduce an optimization problem, called population transition problem, with the objective of maximizing the probability of universal streaming by manipulating population transition probability matrix. We employ a chemical reaction-inspired metaheuristic, Chemical Reaction Optimization (CRO), to solve the problem. Simulation results show that CRO outperforms many commonly used strategies for controlling population transition in many practical P2P live streaming systems. This work also shows that CRO also demonstrates the usability of CRO to solve optimization problems.

In this paper, we study the performance of opportunistic scheduling in wireless networks from the perspective of information and entropy. In opportunistic scheduling, we allocate a limited number of channels to a certain number of nodes so as to maximize the network performance. Due to the inherent uncertainty of the system input represented by random variables with certain probability distributions, even under the optimal scheduling strategy, we may not achieve the best network performance. In our proposed model, we mathematically formulate the relationship between system uncertainty characterized by entropy and network performance, i.e., we give the lower and upper bounds of network performance with given entropy of the uncertain input. Based on this result, we can determine quantitatively the impact of system uncertainty on the performance of of opportunistic scheduling in wireless networks.

Cognitive radio can help increase the capacity of wireless networks by allowing unlicensed users to use the licensed bands, provided that the occupancy do not affect the prioritized licensed users. One of the fundamental problems in cognitive radio is how to allocate the available channels to the unlicensed users in order to maximize the utility. In this work, we develop an allocation algorithm based on the newly proposed chemical reaction-inspired metaheuristic called Chemical Reaction Optimization (CRO). We study three utility functions for utilization and fairness, with the consideration of the hardware constraint. No matter which utility function is used, simulation results show that the CRO-based algorithm always outperforms the others dramatically.

Online social search brings forth a new way to harness the Internet for answers. However, the personal and often sensitive information is unwittingly exposed to others when a person looks for an expert via the underlying social network. In this paper, we propose a model in which a node's behavior of looking for an expert is adjusted by his awareness of the potential expertise of his contacts. We derive the optimal distribution of nodes' awareness level that minimizes the system's privacy exposure, and prove that it corresponds to the unique Nash equilibrium. Our analysis shows that the optimal distribution over a posed question is inversely proportional to the square root of the corresponding expertise density.

Online social search (OSS) brings forth a new way to harness the Internet for answers. In this paper, we study the balancing between OSS users' capabilities and responsibilities. Targeting a practical system design, we propose an analytical model that captures the heterogeneity of different referral sessions in OSS, and a distributed socio-aware referral strategy that can achieve the desired balance when the system reaches steady state. We show that configuring the strategy enables the system operator to control the flow of all posed questions in the system. We also discuss the implications of configuring the strategy from a gaming-strategy point of view.

Information theory has made great impact on research and development of communication systems. However, research in networking, a system built on communication components, has not benefited much from information theory and a theoretical framework to guide the analysis and design of networks is still lacking. Therefore, in this paper, we propose an information-theoretical framework to explore the quantitative relationship between information and network performance. Another attribute of information, namely information quality (IQ), is proposed to reflect the degree of importance of information to the target performance metric. IQ can be utilized to identify important information, so that network resource can first be allocated to such information, and hence to improve the network performance. Moreover, information efficiency (IE) is proposed as a metric to measure the information efficiency of network protocols and it can be used to analyze and compare the performance of different network protocols. Opportunistic scheduling is used to illustrate our proposed framework.

Many wireless network protocols have to deal with inaccurate information due to the lack of sufficient knowledge of the scenario or other limitations. Therefore, in this paper, we study information accuracy and investigate its quantitative impact on wireless network performance. First, we introduce an entropy-performance framework to model the relationship between wireless network performance and entropy, which characterizes the uncertainty of the input. Under this framework, we quantify the performance variations due to the availability of side information and find that the system performance improvement has a positive linear relationship with the amount of mutual information between input and side information. Subsequently, information accuracy is proposed to reflect the reliability of information. We show that information accuracy has a natural relationship with mutual information and we quantify the impact of information accuracy on wireless network performance.

The capacity of wireless networks is greatly affected by the available information on network states, such as network topology, channel state, and traffic information. Previous research has estimated the capacity of wireless networks by assuming that each node in the network can obtain precise network information. However, in reality, precise network information may not be readily available, and it may require a large amount of bandwidth resource to maintain accurate network information, thus reducing the net data rate. In this paper, we study the tradeoff between network performance improvement and the communication overhead of transmitting network information. To do so, we first determine the resource required to transmit network information reliably. A channel model is presented for the transmission of network information packets, and the network protocols are modeled as coding schemes. An information-theoretic method is used to obtain the lower bound on the resource required to maintain accurate network information. We use the result to find the optimal allocation of resource between network information transmission and data transmission so as to maximize the net data rate. The model can also be used to derive the upper bound on wireless network performance for topology-transparent algorithms.

Transmission scheduling is a key design problem in wireless multi-hop networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length. Most of the scheduling algorithms are topology-dependent. They are generally graph-based and depend on the exact network topology information. Thus, they cannot adapt well to the dynamic wireless environment. In contrast, topology-transparent TDMA scheduling algorithms do not need detailed topology information. However, these algorithms offer very low minimum throughput. The objective of this work is to propose an adaptive topology-transparent scheduling algorithm to offer better throughput performance. With our algorithm, each node finds a transmission schedule so as to reduce the transmission conflicts and adapt better to the changing network environment. The simulation results show that the performance of our algorithm is better than the existing topology-transparent algorithms.

Grid computing collects geographically dispersed resources ranging from laptops to supercomputers to compute tasks requested by clients. Grid scheduling, i.e., assigning tasks to resources, is an NP-hard problem, and thus, metaheuristic methods are employed to find the optimal solutions. In this paper, we propose a Chemical Reaction Optimization (CRO) algorithm for the grid scheduling problem. CRO is a population-based metaheuristics mimicking the interactions between molecules in a chemical reaction. We compare the CRO approach with four generally acknowledged metaheuristics, and show that CRO performs the best.

Online social networking systems provide indirect access to a large number of people connected by multi-step chains of acquaintances, and plays an important role in the referrals for human information flow. In this paper, from a networking point of view, we study the problem of locating experts for relevant information via online social networks. We model the action of forwarding a question with random walk, adjusted by a node's awareness of the potential expertise of his immediate neighbours. Using the model we derive analytical expressions of the performance metrics of a referral session in terms of the nodes' awareness level of their neighbours and the percentage of nodes that may have answers to the posed question. We also utilize several real online social networks to study the modeled question-forwarding strategy, and find that the simulation results validate our analyses.

A Vehicular Sensor Network (VSN) may be used for urban environment surveillance utilizing vehicle- based sensors to provide an affordable yet good coverage for the urban area. The sensors in VSN enjoy the vehicle's steady power supply and strong computational capacity not available in traditional Wireless Sensor Network (WSN). However, the mobility of the vehicles results in highly dynamic and unpredictable network topology, leading to packet losses and distorted surveillance results. To resolve these problems, we propose a cooperative data sensing and compression approach with zero inter-sensor collaboration overhead based on sparse random projections. The algorithm provides excellent reconstruction accuracy for the sensed field, and by taking advantage of the spatial correlation of the data, enjoys much smaller communication traffic load compared to traditional sampling algorithms in wireless sensor networks. Real urban environment data sets are used in the experiments to test the reconstruction accuracy and energy efficiency under different vehicular mobility models. The results show that our approach is superior to the conventional sampling and interpolation strategy which propagates data in an uncompressed form, with 4-5dB gain in reconstruction quality and 21-55% savings in communication cost for the same sampling times.

In wireless networks, TCP performs unsatisfactorily since packet reordering and random losses may be falsely interpreted as congestive losses. This causes TCP to trigger fast retransmission and fast recovery spuriously, leading to under-utilization of available network resources. In this paper, we propose a novel TCP variant, known as TCP for non-congestive loss (TCP-NCL), to adapt TCP to wireless networks by using more reliable signals of packet loss and network overload for activating packet retransmission and congestion response, separately. TCP-NCL can thus serve as a unified solution for effective congestion control, sequencing control, and loss recovery. Different from the existing unified solutions, the modifications involved in the proposed variant are limited to sender-side TCP only, thereby facilitating possible future wide deployment. The two signals employed are the expirations of two serialized timers. A smart TCP sender model has been developed for optimizing the timer expiration periods. Our simulation studies reveal that TCP-NCL is robust against packet reordering as well as random packet loss while maintaining responsiveness against situations with purely congestive loss.

In this paper, we study the performance of resource-constrained systems from the perspective of information theory. Such a system consists of many components which may contribute to the performance, but resource can only be allocated to some of them. We desire to allocate the limited resources effectively so as to maximize the system performance. Usually, we have incomplete information about the system or the system has inherent randomness. Even with the optimal allocation strategy according to the available (uncertain) information, we may not achieve the best system performance. We propose a model for the generic resource-constrained system and mathematically formulate the relationship between system uncertainty, characterized by entropy, and performance. Based on this result, we can determine how the system uncertainty quantitatively influences the performance. Examples of applications of the model to data storage and peer-to-peer file sharing are also given.

A key issue impacting wireless network performance is network information. In wireless networks, a significant amount of bandwidth and power resource is consumed to disseminate and maintain routing information. Previous work has presented different methods to broadcast and store such routing information so as to reduce the overhead. However, the amount of information required for a routing algorithm to be effective is not studied theoretically. In this paper, we consider two kinds of routing information, i.e., location information and link state information, and study the quantitative relationship between the available routing information and network performance. It is assumed that each node in the network can only obtain information of its k-hop neighbors, and for each packet, a distance vector based algorithm is employed to minimize the number of hops for the packet to reach its destination with the limited information. We then present a methodology to derive the analytical result on the quantitative relationship between routing performance and the information available for each node. The analysis in this paper can be a valuable tool on designing routing algorithms in wireless networks.

Transmission scheduling is a key design problem in wireless multi-hop networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length. There exists some interesting scheduling algorithms called topology-transparent TDMA scheduling algorithms, which do not require the detailed topology information, and are suitable for the wireless environment. However, a framework to compare the performance of these algorithms properly and fairly is still lacking. The objective of this work is to propose a uniform framework for topology-transparent scheduling algorithms. Under some fundamental constraints, an optimal solution is provided to the scheduling problem of topology-transparent algorithms. Furthermore, under the proposed framework, we analyze the relationship among all existing topology-transparent algorithms. We then develop an adaptive topology-transparent algorithm, which can always give an optimal solution under a set of the system design parameters.

In this paper, we propose a hybrid cargo-level tracking system for logistics. We highlight the special system requirements, discuss the design issues and identify the design principles. Then we propose an innovative hybrid system. As far as we know, this is the first system that exploits both infrastructure-based and infrastructure-less positioning schemes for practical cargo-level tracking. Compared with existing systems, the proposed system provides a ubiquitous cargo-level tracking solution with enhanced availability, reliability, and lower total costs.

In opportunistic networks, centrality characterizes a node's capability to act as a communication hub. In this paper, we provide an in-depth study of choosing effective centrality metrics for message forwarding in bandwidth-limited opportunistic networks. Based on this study, we propose a destination-unaware forwarding algorithm that accounts for the popularity of a node and the contact durations between nodes. We evaluate the algorithm on two experimental human mobility traces. The simulation results show that the proposed algorithm achieves higher system throughput while maintaining a lower forwarding cost compared with several known destination-unaware forwarding schemes.

In this paper, we present a model to analyze the performance of three transmission strategies with smart antennas, i.e. directional antennas with adjustable transmission power. Generally, a larger transmission radius contributes a greater progress if a transmission is successful. However, it has a higher probability of collision with other concurrent transmissions. Smart antennas mitigate collisions with sectorized transmission ranges. They also extend the transmission radii. By modelling three transmission strategies, namely, Nearest with Forward Progress (NFP), Most Forward with Fixed Radius (MFR), and Most Forward with Variable Radius (MVR), our analysis illustrates that the use of smart antennas can greatly reduce the possibility of conflicts. The model considers the interference range and computes the interference probability for each transmission strategy. We have analyzed two Medium Access Control (MAC) protocols using our interference model, namely, the slotted ALOHA protocol and the slotted CSMA/CA-like protocol. The result shows that, for slotted ALOHA, NFP yields the best one-hop throughput, whereas MVR provides the best average forward progress. The overall performance is substantially improved with the slotted CSMA/CA-like protocol, and the network becomes more resilient.

We encounter optimization problems in our daily lives and in various research domains. Some of them are so hard that we can, at best, approximate the best solutions with (meta-) heuristic methods. However, the huge number of optimization problems and the small number of generally acknowledged methods mean that more metaheuristics are needed to fill the gap. We propose a new metaheuristic, called chemical reaction optimization (CRO), to solve optimization problems. It mimics the interactions of molecules in a chemical reaction to reach a low energy stable state. We tested the performance of CRO with three nondeterministic polynomial-time hard combinatorial optimization problems. Two of them were traditional benchmark problems and the other was a real-world problem. Simulation results showed that CRO is very competitive with the few existing successful metaheuristics, having outperformed them in some cases, and CRO achieved the best performance in the real-world problem. Moreover, with the No-Free-Lunch theorem, CRO must have equal performance as the others on average, but it can outperform all other metaheuristics when matched to the right problem type. Therefore, it provides a new approach for solving optimization problems. CRO may potentially solve those problems which may not be solvable with the few generally acknowledged approaches.

Previous research has estimated the performance of wireless networks by assuming that nodes in the network can obtain precise network information. However, in reality, available network information is mostly imprecise and incomplete. In this paper, we study the relationship between wireless network performance and available network information. It is assumed that each node in the network can obtain the information about other nodes within its information collection range, and a distributed graph coloring algorithm is employed to perform scheduling with the available information. The analytical result on the quantitative relationship between the information collection range and the network throughput is derived. We also consider the communication overhead of collecting information, and analyze the tradeoff between network capacity improvement and information collection overhead. Based on the derived result, an optimal information collection range which maximizes the net data rate can be found. Since wireless networks are typically mobile, and the collected information may be inaccurate due to the dynamics of the networks, we analyze the effect of information for mobile wireless networks by considering the information updating rate, and the result can be used to determine the information collection range as well as the information updating period.

Motivated by the highly dynamic topology in wireless sensor networks with asynchronous duty cycle, and its impact on reliable data delivery, we propose a light-weight opportunistic forwarding (LWOF) scheme. Differing from other recently proposed schemes, LWOF neither employs historical network information nor a contention process to select a forwarder prior to data transmission. It takes advantage of the preamble in low power listening (LPL) media access control (MAC) protocols and dual-channel communication to remove the overhead of making a forwarding decision. Along with LWOF, we propose an energy efficient MAC protocol (LWMAC) with a shortened preamble, to exploit the non-deterministic characteristics of opportunistic forwarding. The preamble length in LWMAC is a function of the node density and sleep duration. Simulation results show that LWOF, along with LWMAC, can provide reliable service of data delivery with less energy consumption.

Available network information is an important factor in determining network performance. In this paper, we study the basic limits on the amount of network information that should be transmitted in the network to achieve a given level of network performance. From the perspective of information theory, network information is an information source, and the lower bound on network information is the minimum code letters required to encode the source. We propose a general information-theoretic framework, which can be applied to any network, to study the effect of network information on the performance of any network protocol. We also analyze the tradeoff between network performance improvement and network information collection overhead. To illustrate our approach, we use the framework to determine the lower bound on the traffic information for a simple scheduling protocol in wireless networks. The results in this paper may be used to analyze and evaluate network protocols and guide future designs.

Data streaming (DS) over peer-to-peer (P2P) networks has been intensively studied in recent years and there have been various schemes proposed already. To evaluate these schemes, either measurement in experimental implementations, or simulation and theoretical analysis have been used. The former is inadequate as data are collected from different experiments, while the latter lacks a proper theoretical dynamics model. Our research aims at providing a general theoretical model to evaluate DS over P2P systems and analyze their dynamic behaviors. In this paper, with the analysis and abstraction of the characteristics of peers and their organization in DS over P2P, we propose a general population dynamics model for DS over P2P with fixed population. The model depicts the dynamic distribution of peers as a closed Markov queuing network. In particular, the model is scheme-independent and can be used with various schemes. Through theoretical analysis, we prove the model has equilibrium and only one closed-form solution. Besides, we verify the model through simulations, and show that it is a helpful analytical tool with a case study.

The problems of TCP packet reordering and random loss over wireless networks have motivated the development of a number of TCP variants. However, most of these variants focus on resolving only one of the aforementioned two problems. A few unified solutions for both problems generally extend beyond the scope of the transport layer. In this paper, we propose a new TCP variant, known as TCP for non-congestion loss (TCP-NCL), to tackle both problems under one compact framework. Different from previous unified solutions, the modifications are limited to sender-side TCP only, thereby facilitating possible future wide deployment. A retransmission decision timer and a congestion response decision timer have been installed to trigger packet retransmission and congestion response, respectively. Our simulation studies reveal that TCP-NCL is robust against packet reordering as well as random packet loss while maintaining responsiveness against situations with purely congestive loss.

The No-Free-Lunch (NFL) Theorem provides a fundamental limit governing all optimization/search algorithms and has successfully drawn attention to theoretical foundation of optimization and search. However, we find several limitations in the original NFL paper. In this work, using results from the nature of search algorithms, we enhance several aspects of the original NFL Theorem. We have identified the properties of deterministic and probabilistic algorithms. We also provide an enumeration proof of the theorem. In addition, we show that the NFL Theorem is still valid for more general performance measures. This work serves as an application of the nature of search algorithms.

This special issue includes a collection of 19 outstanding research papers which cover a diversity of topics on the application of network coding in wireless communication networks.

Based on the Hungarian algorithm, the Kuhn-Munkres algorithm can provide the maximum weight bipartite matching for assignment problems. However, it can only solve the single objective optimization problem. In this paper, we formulate the multi-objective optimization (MO) problem for bipartite matching, and propose a modified bipartite matching (MBM) algorithm to approach the Pareto set with a low computational complexity and to dynamically select proper solutions with given constraints among the reduced matching set. In addition, our MBM algorithm is extended to the case of asymmetric bipartite graphs. Finally, we illustrate the application of MBM to antenna assignments in wireless multiple-input multiple-output (MIMO) systems for both symmetric and asymmetric scenarios, where we consider the multi-objective optimization problem with the maximization of the system capacity, total traffic priority, and long-term fairness among all mobile users. The simulation results show that MBM can effectively reduce the matching set and dynamically provide the optimized performance with different quality of service (QoS) requirements.

In this paper, we present a model to analyze the performance of wireless ad hoc networks with smart antennas, i.e. directional antennas with adjustable transmission power. Our results show that smart antennas can improve the network performance by mitigating the effects of interference. We illustrate our model with the NFP (Nearest with Forward Progress) transmission strategy. Our analytical and simulation results show that, for ad hoc networks with smart antennas, NFP yields good throughput and remains stable as the node density varies.

With the recently proposed multi-slot batch-transfer (MSBT) architecture, we can build optical packet switches using slow switching fabrics with reconfiguration time larger than the guard time between packets. Since MSBT switches can provide multichannel capability with no additional hardware, we propose to combine the multichannel and deflection routing approaches for packet contention resolution in MSBT networks. As there is no analytical performance model available, we derive the required model in this paper. Simulations show that the model is very accurate.

Transmission scheduling is a key design problem in wireless multi-hop networks and many scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple- access (TDMA) frame length. Most of scheduling algorithms are graph-based, dependent on the exact network topology information and cannot adapt to the dynamic wireless environment. Some topology-independent TDMA scheduling algorithms have been proposed, and do not need accurate topology information. Our proposed algorithm follows a similar approach but with a different design strategy. Instead of minimizing the TDMA frame length, we maximize the minimum expected throughput, and we consider multicasting and broadcasting. The simulation result shows that the performance of our algorithm is better than the conventional TDMA and other existing algorithms in most cases.

In optical burst switching (OBS) system, the throughput decreases rapidly with increase in control packet processing time Tcp. The negative impact of Tcpwill become significant as the optical fiber transmission rate increases. By analyzing the relationship between the throughput and Tcp, we attempt to improve the throughput. Different possible solutions are discussed. We found that using extra random offset time can significantly improve the throughput at the expense of increase in data burst delay.

In this paper, we introduce a framework for distributed opportunistic scheduling in multihop wireless ad hoc networks. With the proposed framework, one can take a scheduling algorithm originally designed for infrastructure-based wireless networks and adapt it to multihop ad hoc networks. The framework includes a wireless link state estimation mechanism, a medium access control (MAC) protocols and a MAC load control mechanism. The proposed link state estimation mechanism accounts for the latest results of packet transmissions on each wireless link. To improve robustness and provide service isolation during channel errors, the MAC protocol should not make any packet retransmissions but only report the transmission result to the scheduler. We modify IEEE 802.11 to fulfill these requirements. The MAC load control mechanism improves the system robustness. With link state information and the modified IEEE 802.11 MAC, we use BGFS-EBA, an opportunistic scheduling algorithm for infrastructured wireless networks, as an example to demonstrate how such an algorithm is converted into its distributed version within the proposed framework. The simulation results show that our proposed method can provide robust outcome fairness in the presence of channel errors.

Previous research has estimated the capacity of wireless networks by assuming that each node in the network can obtain precise network information. However, in reality, available network information is mostly imprecise and incomplete. In this paper, we study the relationship between the information obtained by each node and the capacity of the wireless network. We also consider the communication overhead of collecting network information, and analyze the tradeoff between the network capacity improvement and the network information collection overhead. The analysis in this paper can be a valuable tool on determining information collection parameters in wireless networks.

In this paper, we investigate the problem of providing QoS to end-to-end flows in multihop ad hoc networks with channel errors through packet scheduling. Each flow is associated with some QoS requirement, which is requested and granted in the form of a desired service rate. The achieved rate is estimated at the destination and fed back to the source periodically. Both the desired rate and achieved rate of a multihop flow are piggybacked on the packets of the flow and propagated from the source node to all its downstream relaying nodes. With such information, a compensation-capable scheduling algorithm originally designed for infrastructured wireless networks can be adapted to each ad hoc node for compensating a lagging flow, i.e., a flow with the achieved rate smaller than the desired rate. We propose the feedback and propagation mechanism as an end-to-end compensation framework, which is the key contribution of this work. We use BGFS-EBA, a scheduling algorithm for infrastructured wireless networks, as an example to demonstrate how such an algorithm is adapted to ad hoc networks within the proposed framework. Our simulation results show that the proposed mechanism maintains outcome fairness and compensate flows that suffer sporadic bursty channel errors effectively.

With the development of wireless communication technologies and the popularity of the P2P applications, an important problem is to determine how to distribute data efficiently in wireless P2P networks. However, data distribution in wireless P2P networks faces many challenges compared with that in th

Data streaming by swarming over peer-to-peer overlay networks has attracted much attention in recent years and initially the swarming solution is based on data-driven schemes. This paper presents a new request-driven swarming scheme. The scheme offers several advantages: high efficiency in data deli

Traffic scheduling is key to the provision of quality of service (QoS) differentiation and guarantees in wireless networks. Unlike its wireline counterpart, wireless communications pose special channel-specific problems such as time-varying link capacities and location-dependent errors. These problems make designing efficient and effective traffic scheduling algorithms for wireless networks very challenging. Although many wireless packet scheduling algorithms have been proposed in recent years, issues such as how to improve bandwidth efficiency and maintain goodput fairness with various link qualities for power-constrained mobile hosts remain unresolved. In this paper, we devise a simple wireless packet scheduling algorithm called bandwidth-guaranteed fair scheduling with effective excess bandwidth allocation (BGFS-EBA), which addresses these issues. Our studies reveal that BGFS-EBA effectively distributes excess bandwidth, strikes a balance between effort-fair and outcome- fair, and provides a delay bound for error-free flows and transmission effort guarantees for error-prone flows.

This paper investigates optimal transmission of space-time block codes (STBCs) in distributed multiple-input multiple-output (D-MIMO) Rayleigh fading channels. The optimal diversity performance is achieved through transmit power allocation implemented at the receiver based on transmit and receive correlations to minimize the average symbol error rate (SER). Evaluation of SER performance of uncoded STBCs over a generalized distributed antenna (DA) topology is first presented, with exact analytical SER expressions derived for MQAM and MPSK symbols. SER upper bounds are also derived, based on which two criteria for complexity reduced antenna subset selection with sub-optimal power allocation are further proposed, whose performance approaches optimal over correlated D-MIMO channels. Moreover, a novel simplified but close SER approximation scheme is devised to significantly facilitate optimal SER calculation. We continue to thoroughly analyze how the optimal diversity is affected by large scale fading, targeted data rate, antenna correlations and transmit power. Finally, we develop a surprisingly close and useful analogy between open loop STBCs in co-located MIMO and optimal STBCs in D-MIMO with minimum feedback (i.e., n bits for n DAs in Criterion 2 with power allocation scheme 2 which equally allocates power to the selected DAs). Extensive simulation results have been presented to demonstrate the effectiveness of our analysis.

In optical packet switching, the reconfiguration time of optical switches should only be a small fraction of the packet transmission time for efficient utilization of the bandwidth. This constraint puts a very stringent demand on the switch reconfiguration time as the transmission rate of optical fiber increases. By using batch transfer of packets, we propose an optical switch architecture that can significantly relax the requirement on switch reconfiguration time. The utilization of the transmission links is greatly improved because the guard time between packets is no longer related to the switch reconfiguration time. We have also demonstrated analytically that the proposed switch architecture can significantly reduce the packet loss probability, at the expense of an increase in the delay variations, if the packets are not restricted to their original time slots at the switch output.

In this paper, a dynamic resource allocation algorithm to satisfy the packet delay requirements for real-time services, while maximizing the system capacity in multiuser orthogonal frequency division multiplexing (OFDM) systems is discussed. Our proposed cross-layer algorithm, called Joint Dynamic Subcarrier Allocation and Flow Control (DSA-FC) algorithm, consists of two interactive components. In the medium access control (MAC) layer, the users' expected transmission rates in terms of the number of subcarriers per symbol and their corresponding transmission priorities are evaluated. With the subcarrier gain information of each user, the physical (PHY) layer subcarrier allocation is optimally designed to satisfy the users' requirements under the system signal-to-noise ratio (SNR) and power constraints. In a system where the number of active users changes dynamically, the MAC-layer congestion control and removal schemes can guarantee the quality of service (QoS) of the existing users in the system and fully utilize the bandwidth resource. The proposed algorithm combines these two components, and the numerical results show that it significantly improves the system performance in terms of the bandwidth efficiency and delay performance for real-time services.

In this paper, we evaluate the performance of New- reno analytically by explicitly modeling its slow-start, congestion avoidance, fast retransmit, fast recovery and retransmission timeout mechanisms. Two packet loss models, bursty and independent, are adopted in our study. The accuracy of our proposed New-reno model is verified by simulations. The performance of New-reno is then compared with Sack using the derived analytical models. We show that New-reno outperforms Sack when the round trip time is short and the bursty loss event probability is low.

When implementing public key security services in mobile ad hoc networks (MANETs), multiple certificate authority (CA) servers are usually adopted to increase the security of the system, with each CA node holding only one share of the private key. To prevent an adversary from collecting a large enough number of shares over a long period of time to compromise the system, the shares will be periodically updated. However, it is not trivial how this update procedure can be done efficiently in a MANET. In this paper, we devise an efficient distributed secret key share update scheme for MANETs based on the cluster architecture. In our scheme, the secret shares are updated first by a small group of server nodes. With the assistance of the cluster head in each cluster, the updated servers then refresh the shares in the remaining servers. We evaluate our scheme by simulation and show that our scheme can expedite the share update process.

In this paper, we develop contention-based medium access control (MAC) schemes for both best-effort data transmissions and delay-sensitive multimedia transmissions over WLANs. A user detection module and a multi-rate adaptation module are proposed in the physical layer to assist in link differentiation. With these two modules, for best-effort data transmissions, a new distributed queuing MAC protocol (PALD-DQMP) is proposed. Based on different users' channel states, PALD-DQMP makes use of a distributed queuing system to schedule the transmissions. To support delay-sensitive multimedia transmissions, an enhanced PALD-DQMP (E-PALD-DQMP) is designed by providing two-level optimized transmission scheduling for four access categories, thus eliminating both external and internal collisions among mobile stations. Simulation results show that our proposed protocols outperform the standard MAC protocols for both delay-sensitive and best-effort traffics. All these improvements are mainly contributed by the availability of cross-layer channel state information, and the consequent multi-rate adaptation scheme.

A novel adaptive resource-based probabilistic search algorithm (ARPS) for P2P networks is proposed in this paper. ARPS introduces weighted probabilistic forwarding for query messages according to the node degree distribution and the popularity of the resource being searched. A mechanism is introduced to estimate the popularity and adjust the forwarding probability accordingly such that a tradeoff between search performance and cost can be made. Using computer simulations, we compare the performance of ARPS with several other search algorithms. It is shown that ARPS performs well under various P2P scenarios. ARPS guarantees a success rate above a certain level under all circumstances, and enjoys high and popularity-invariant search success rate.

An adaptive framework is proposed for multi-user video transmission over orthogonal frequency division multiple access (OFDMA) systems. Utilizing the channel knowledge, a two-step heuristic sub-carrier assignment algorithm is proposed to achieve unequal error protection for the video data. The approach also solves the fairness issue among different users that may be caused by varying channel quality on different sub-carriers. Meanwhile, multi-user channel gain is also achieved. The proposed framework significantly improves the video transmission quality with little extra computational complexity and system overhead.

TFRC is a TCP-friendly rate control protocol based on TCP Reno's throughput equation. It is designed to provide optimal service for unicast multimedia flow operating in the wired Internet environment. However, in wireless networks, TFRC, same as TCP Reno, suffers significant performance degradation. In this paper, we propose to make use of a more advanced equation to enhance TFRC over wireless networks. This new equation is directly derived from the modeling of the wireless TCP rather than the wired TCP. After incorporating this equation into TFRC, two achievements are obtained: 1) this enhanced TFRC has a significant throughput improvement; it is shown that in wireless networks with 10% loss rate, it can obtain 300% improvement over the original TFRC; 2) this enhanced TFRC inherits the desirable features of TFRC, namely good fairness, nice TCP-friendliness and smoothness of sending rate. The extensive experiments, including simulation and live Internet measurements, validate our proposed scheme. Moreover, our scheme only needs to modify the sender-side protocol of TFRC while the receiver-side or intermediate node protocol stack remains intact.

In this paper, we investigate the integration of passive optical networks (PONs) with optical burst switched (OBS) networks. Owing to the decomposition of the operations between the PONs and OBS nodes, serious problems have been observed. One of them is data burst assembly problem. In some situations, burst assembly delay exceeding tens seconds may be required if the general purpose PON access schemes are used. To solve this problem, we propose to have the optical network units (ONUs) take over the burst assembly function from the OBS nodes. Large reduction of the burst assembly delay is obtained. Four ONU data burst scheduling schemes have also been investigated. We observe that a simple scheduling scheme is itself adequate in most situations.

Many secure protocols in mobile ad hoc networks rely on the public key infrastructure. Due to the vulnerability of nodes in MANETs, multiple certificate authorities (CAs) distributed over the network, each with a periodically updated share of the private key, is usually adopted. Existing approaches either assume that all nodes are CAs which is not realistic or assign each cluster head to be a CA based on the cluster architecture which may not be efficient since CA service may involve nodes in many clusters. In a previous work, we enhance the latter approach by allowing other nodes to be CAs. All these schemes do not allow the number of CAs to be changed adaptively due to the changes in the size of the network which is common in MANETs. In this paper, we propose a new framework to provide distributed authority services in cluster-based MANETs. In each cluster, a set of nodes are chosen as CAs. The size of the CA set is adaptive to network changes. We further require the shares in different clusters to be independent, and periodically updated.

This paper develops a multipolling MAC protocol which exploits cross-layer information to support delay-sensitive multimedia services over WLANs. A user detection module and a multi-rate adaptation module are proposed in the physical layer to assist in link differentiation. With these two modules, our new multi-polling MAC protocol, named PALD-MPMP not only reduces the polling overhead, but also provides an effective polling scheduler by allocating transmission priorities to users according to their delay requirements or levels and channel gains. Simulation results show that our proposed protocol outperforms the standard point coordination function (PCF) for delay-sensitive services. All the performance improvements are mainly contributed by the awareness of cross-layer channel state information, and the consequent multi-rate adaptation schemes.

The objective of this paper is two-fold. First, we compare the performance, through computer simulations, of some solutions for TCP packet reordering in wireless networks. Second, we present an alternative method to improve the connection goodput in wireless networks through link-layer retransmissions and applying the solutions to TCP packet reordering. Some link-layer retransmission approaches do not attempt to maintain in-order packet delivery. This leads to some segments, which belong to the same TCP flow, to arrive at their destination out of order. Thus, the problem of high channel error rates in wireless networks becomes the problem of packet reordering due to link-layer retransmissions. We performed a simulation study to evaluate the performance of four solutions for TCP packet reordering, namely, RR-TCP, TCP-DCR, TCP-DOOR, and TCP-PR, under the scenarios of an infrastructure-based wireless network and a multi-hop wireless network. We also compared them with SACK TCP and TCPW. Our simulation study reveals that TCP-PR outperforms all of the other five algorithms, enjoying a greater connection goodput and fewer false fast retransmissions.

This paper addresses the issue of transmission scheduling in multi-channel wireless ad hoc networks. The authors propose a multi-channel time division multiple access (TDMA) scheduling based on edge coloring and algebraic coding theory, called CC-TDMA. The authors categorized the conflicts suffered by wireless links into two types: explicit conflicts and implicit conflicts, and CC-TDMA utilize two different strategies to deal with them. Explicit conflicts are avoided completely by a simple distributed edge-coloring algorithm mu-M, and implicit conflicts are minimized by using coding theory to assign channels to links. The authors evaluate CC-TDMA analytically and numerically, and find that it exhibits a better performance than previous work in terms of throughput and delay.

Peer-to-Peer file sharing applications in the Internet, such as BitTorrent, Gnutella, etc., have been immensely popular. Prior research mainly focuses on peer and content discovery, overlay topology formation, fairness and incentive issues, etc. However, little attention has been paid to investigate the data distribution problem which is also a core component of any file sharing application. In this paper, we present the first effort in addressing this collaborative file distribution problem and formally define the scheduling problem in a simplified context. We develop several algorithms to solve the problem and study their performance. We deduce a theoretical bound on the minimum download time experienced by users and also perform simulations to evaluate our algorithms. Simulation results show that our graph-based dynamically weighted maximum-flow algorithm outperforms all other algorithms. Therefore, we believe our algorithm is a promising solution to be employed as the core scheduling module in P2P file sharing applications.

This letter investigates optimal transmission of orthogonal space-time block codes (OSTBCs) over distributed antennas (DAs) in non-ergodic flat Rayleigh fading channels with transmit antenna correlations. A generalized DA topology is considered, where the DAs are grouped into some geographically dispersed ports within each of which the DAs are co-located. Assuming equal power allocation within each port, the outage probability is derived. We find that minimizing the outage probability only requires the feedback of the eigenvalues of the transmit correlation matrix at the transmitter. Since it is computationally intensive to minimize the outage probability, an antenna subset selection with suboptimal power allocation scheme is proposed, whose effectiveness has been demonstrated by numerical results

Recent advances in multicast video streaming algorithms have opened up new ways to provision video-on-demand services to potentially millions of users. However, the spectacular efficiency of multicast streaming algorithms can only be realized by restricting or even prohibiting interactive playback control. Experiments reveal that the performance of current state-of-the-art multicast streaming algorithms will degrade significantly even at very low levels of interactivity (e.g., one control per five users). This study tackles this challenge by investigating the fundamental limitations of multicast streaming algorithms in supporting interactive playback control and presents a general solution-static full stream scheduling (SFSS)-which can be applied to many of the existing multicast streaming algorithms to substantially improve their performance when interactive playback control is to be supported. Moreover, to solve the problem of optimizing the algorithm for the often unknown client access patterns (e.g., arrival rates and interactivity rates), we present a novel just-in-time simulation (JTS) scheme to dynamically and automatically tune operating parameters of the SFSS algorithm while the system is online. This JTS scheme not only eliminates the need for a priori knowledge of the often unknown system parameters, but also can adapt to changes in the client access pattern over time. Extensive simulation results show that the proposed adaptive algorithm can reduce the admission and interactive control latencies by as much as 90%

Transmission control protocol (TCP) is the most popular transport layer protocol for the Internet. Due to various reasons, such as multipath routing, route fluttering, and retransmissions, packets belonging to the same flow may arrive out of order at a destination. Such packet reordering violates the design principles of some traffic control mechanisms in TCP and, thus, poses performance problems. In this paper, we provide a comprehensive and in-depth survey on recent research on packet reordering in TCP. The causes and problems for packet reordering are discussed. Various representative algorithms are examined and compared by computer simulations. The ported program codes and simulation scripts are available for download. Some open questions are discussed to stimulate further research in this area

Multicast is very efficient in distributing a large volume of data to multiple receivers over the Internet. Layered multicast helps solve the heterogeneity problem in multicast delivery. Extensive work has been done in the area of layered multicast, for both congestion control and error control. In this paper, we focus on network-supported protocols for streaming media. Most of the existing work solves the congestion control and error control problems separately and does not give an integrated efficient solution. In this paper, after reviewing related work, we introduce our proposed protocols, namely, router-assisted layered multicast (RALM) and router-assisted layered FEC (RALF). The former is a congestion control protocol, whereas the latter is an error control protocol. They work under the same framework and provide an integrated solution. We also extend RALM to RALM-II, which is compatible with transmission control protocol (TCP) traffic. We analyze the complexity of the proposed protocols in the network and investigate their performance through simulations. We show that our solution achieves significant performance gains with reasonable additional complexity.

The goal of handoffs in a 4G wireless network is not only to keep the data traffic from being disrupted due to user mobility, but also to switch the connection to the network which best satisfies users' requirements. In this work, we propose a scheme which dynamically switches a mobile user's connection between different access networks. In each handoff, a user will adjust its bandwidth requirement according to the utilization of the current access network. A profitability function is established to evaluate the profits gained from a handoff and to select the target network accordingly. Through vertical handoffs, traffic load will be balanced among the access networks and radio resources will be efficiently utilized. Our simulation result shows that the scheme will effectively decrease call blocking and dropping rate. System throughput and users' experience will also be improved.

The binary exponential backoff (BEB) algorithm used in IEEE 802.11 DCF suffers from the unfairness problem and yields low throughput under heavy load. With physical layer assisted loss differentiation, this paper proposes a new distributed queuing medium access control (MAC) protocol (PALD-DQMP). In this protocol, utilizing the user detection module in the physical layer, losses due to collisions are distinguished from those due to link errors, and such information is made available to the MAC layer. Based on different users' channel states, PALD-DQMP schedules their transmissions. Simulation results show that the proposed scheme outperforms the standard MAC protocol in terms of network throughput and fairness. This improvement is mainly due to the availability of cross-layer channel information, and the elimination of collisions and backoff periods.

In this paper, we propose an adaptive video transmission scheme to achieve unequal error protection in multichannel ad hoc networks. In our scheme, video data is divided into high priority (HP) and low priority (LP) portions, and mobile nodes have two channels for video transmission. A channel quality metric, busy time ratio (BTR), is employed to characterize the channel quality. The channel with better BTR metric is used for HP data, and the other for LP. Further, adaptive load control and delay-constrained queue management schemes are proposed to improve performance. Simulation results demonstrate the performance of video streaming is greatly enhanced in multichannel multi-hop ad hoc networks.

The optical burst switching (OBS) schemes to date assume that the switching overhead at intermediate nodes is either negligible or can be considered as part of the processing delay of the control packet. In this paper, we will show that the switching overhead can have a significant impact on the performance of OBS. We have also proposed methods to alleviate the problem.

Opportunistic transmission scheduling schemes improve system capacity by taking advantage of independent time varying channels in wireless networks. In the design of such scheduling schemes, the fairness criterion plays an important role in the tradeoff of total system capacity and the achievable throughput of individual users. To meet different fairness demands with a unified opportunistic scheduling scheme, in this paper, we have extended the well known opportunistic scheduling scheme PFS into αPFS, which satisfies arbitrary fairness demands, varying from proportional fairness to maxmin fairness, through adjusting the parameter α. To further improve the achievable diversity gains of αPFS, we extend the αPFS scheme into an αPFS-P scheme. Performances of αPFS and αPFS-P are studied and compared. As demonstrated in the simulation results, both αPFS and αPFS-P can achieve adjustable fairness criteria, varying from proportional fairness to max-min fairness. Compared with αPFS, αPFS-P achieves higher diversity gains with degraded short term performance, which is still better than the performance of PFS.

Proper channel selection is essential to exploit the benefits of multi-channel systems by distributing conflicting transmissions across non-interfering channels. Critical to channel selection is the channel quality metric. We propose a busy time ratio (BTR) metric that captures channel contention and user traffic load under a variety of network dynamics. We also propose a distributed collaborative sensing scheme to reduce sensing overhead and energy consumptions. The proposed algorithms can be implemented using conventional 802.11 hardware with single radio interface. The proposed metric can be integrated with routing and channel selection. Experimental results show that the proposed scheme significantly outperforms the existing channel selection methods.

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

Traditional traffic descriptor-based and measurement-based admission control schemes are typically combined with a node by node resource reservation scheme, rendering them unscalable. Although some Endpoint Admission Control schemes can resolve this problem, they impose significant signaling overhead. To cope with these two problems, this paper proposes a statistical connection admission control framework which can easily and efficiently estimate the network resource for a pair of ingress-egress nodes and make admission decision based on this estimated result. In this framework, the network is considered as a "black box." For a certain ingress-egress node pair, the egress node measures the QoS constraint violation ratio and feeds this information back to the ingress node periodically. With this information and the measured statistical characteristics of the existing aggregated traffic, the ingress node estimates the achievable capacity between the ingress-egress node pair, and makes the admission decision for a new traffic connection request. The signaling overhead of this framework is very small. Simulation results show the effective throughput is relatively high.

We propose a hybrid multiple-input-multiple-output (MIMO) architecture to implement unequal error protection (UEP) for video delivery in MIMO systems. On the transmitter side, some of the transmit antennas are used to implement transmit diversity for delivering video data with high priority, while others are employed for spatial multiplexing to transmit video data with low priority. On the receiver side, a hybrid signal detection mechanism is adopted to separate and decode the mixed data. The goal is to exploit the diversity gain to provide better protection to the high priority data, while transmitting the low priority data with spatial multiplexing to achieve high data rate. Analysis and simulation results demonstrate that the proposed UEP mechanism significantly enhances the quality of video reception with high spectrum efficiency.

Coexistence of heterogeneous networks such as cellular, wireless local area network (WLAN), ultra-wideband (UWB) etc. brings new challenges. It is perceived that current radio resource management mechanism cannot meet the requirements of multi-radio access technologies (multi-RATs). This paper proposes a novel intelligent multi-agent radio resource management system, which is self-organized and distributed to ensure the coexistence of multi-RATs. Radio resource is managed by a macro control and management system using control factors and validation mechanism, instead of micro control for individual users. The goal is to increase radio resource utilization efficiency, maximize system capacity and meet the QoS requirements of different services

For optimal radio resource utilization in heterogeneous wireless networks, joint radio resource management (JRRM) is required. In distributed JRRM, each radio each access network (RAN) adjusts network parameters to affect user's RAN selection, thereby indirectly implementing joint radio resource allocation. The mathematical method for instructing such adjustment is lacking. In this article, the relationship between different RANs is mapped into the competition between species in the well-known L-V model developed by ecologists. Based on this model, an adjustment algorithm of distributed joint radio resource allocation is proposed. The simulation results show that compared with no adjustment or over adjustment, our adjustment algorithm can: 1) obtain proper resource allocation; 2) guarantee network coexistence

In recent years, a number of sophisticated architectures have been proposed to provide video-on-demand (VoD) service using multicast transmissions. Compared to their unicast counterparts, these multicast VoD systems are highly scalable and can potentially serve millions of concurrent users. Nevertheless, these systems are designed for streaming constant-bit rate (CBR) encoded videos and thus cannot benefit from the improved visual quality obtainable from variable-bit rate (VBR) encoding techniques. To tackle this challenge, this paper presents a turbo-slice-and-patch (TSP) algorithm to support VBR video streaming in a multicast VoD system. Results obtained from trace-driven simulation of 300 VBR videos show that serving VBR videos with the TSP algorithm increases the average latency by only 9% compared to the CBR case with the same average video bit rate. Moreover, in 165 out of the 300 video titles, the TSP algorithm actually outperforms the CBR equivalent by shortening the latency by 0.04%-99%. Given that we can achieve similar visual quality by encoding VBR video at half the average rate of CBR video, this TSP algorithm can potentially serve VBR videos with more consistent visual quality and with less resource compare to CBR-based video streaming systems.

In this paper, we develop a model to study how to effectively download a document from a set of replicated servers. We propose a generalized application-layer anycasting protocol, known as paracasting, to advocate concurrent access of a subset of replicated servers to cooperatively satisfy a client's request. Each participating server satisfies the request in part by transmitting a subset of the requested file to the client. The client can recover the complete file when different parts of the file sent from the participating servers are received. This model allows us to estimate the average time to download a file from the set of homogeneous replicated servers, and the request blocking probability when each server can accept and serve a finite number of concurrent requests. Our results show that the file download time drops when a request is served concurrently by a larger number of homogeneous replicated servers, although the performance improvement quickly saturates when the number of servers increases. If the total number of requests that a server can handle simultaneously is finite, the request blocking probability increases with the number of replicated servers used to serve a request concurrently. Therefore, paracasting is effective when a small number of servers, say, up to four, are used to serve a request concurrently.

In this paper, we propose a framework to study how to effectively perform load sharing in multipath communication networks. A generalized load sharing (GLS) model has been developed to conceptualize how traffic is split ideally on a set of active paths. A simple traffic splitting algorithm, called packet-by-packet weighted fair routing (PWFR), has been developed to approximate GLS with the given routing weight vector by transmitting each packet as a whole. We have developed some performance bounds for PWFR and found that PWFR is a deterministically fair traffic splitting algorithm. This attractive property is useful in the provision of service with guaranteed performance when multiple paths can be used simultaneously to transmit packets which belong to the same flow. Our simulation studies, based on a collection of Internet backbone traces, reveal that PWFR outperforms two other traffic splitting algorithms, namely, packet-by-packet generalized round robin routing (PGRR), and packet-by-packet probabilistic routing (PPRR).

For pt.1 see ibid., p.694-702 (2006). In this paper, we extend the load sharing framework to study how to effectively perform flow-based traffic splitting in multipath communication networks. The generalized load sharing (GLS) model is employed to conceptualize how traffic is split ideally on a set of active paths. A simple flow-based weighted fair routing (WFR) algorithm, called call-by-call WFR (CWFR), has been developed to imitate GLS so that all packets belonging to a single flow are sent on the same path. We have investigated how to couple the proposed basic packet-by-packet WFR (PWFR) and CWFR algorithms so as to permit a traffic splitter to handle both connection-oriented and connectionless traffic simultaneously. Our simulation studies, based on a collection of Internet backbone traces, reveal that WFR outperforms two other traffic splitting algorithms, namely, generalized round robin routing (GRR), and probabilistic routing (PRR). These promising results form a basis for designing future adaptive constraint-based multipath routing protocols.

In this paper, we propose a new scheduler for orthogonal frequency-division multiplexing (OFDM) wireless communication systems, called channel-condition and packet-length dependent packet generalized processor sharing (CPLD-PGPS) scheduler. Based on PGPS, the CPLD scheduler considers both the physical channel condition and the length of packets, and optimally allocates the sub-carriers to different users. The total transmit power is adoptively allocated to each subcarrier. With this scheduler, the system can achieve better system BER performance, and correspondingly superior PER performance. The system throughput is improved, the required bandwidth is guaranteed, and long term fairness for all traffic in the system is provided. In order to reduce the complexity, a simplified algorithm is proposed, which maintains the system throughput as in the original scheduler, and guarantees the system performance with properly set system parameters. The superior performance of the proposed schedulers is demonstrated by simulation with multimedia traffic

Peer-to-peer file sharing applications on the Internet, such as BitTorrent, Gnutella, etc., have been immensely popular prior research mainly focuses on peer and content discovery, overlay topology formation, fairness and incentive issues, etc, but seldom investigates the data distribution problem which is also a core component of any file sharing application. In this paper, we present the first effort in addressing this collaborative file distribution problem and formally define the scheduling problem in a simplified context. We suggest several types of algorithms, including a novel bipartite matching algorithm, for solving the problem. Simulation results show that our weighted bipartite algorithm finds an optimal solution for all cases tested. Therefore, we believe our algorithm is a promising solution to be employed as the core scheduling module in P2P file sharing applications, shortening the total download time experienced by users.

An optical packet switch (OPS) is called performance guaranteed if it can achieve 100% throughput with bounded packet delay. Presently, high speedup requirement and large packet delay are two main disadvantages in designing performance guaranteed OPS. Survivability is another important issue that must be considered for real OPS implementations. In this paper, we propose a two-layer parallel OPS architecture together with an efficient scheduling scheme to address all the above issues. The tradeoff between speedup and packet delay under this new parallel architecture is also formulated to provide more design flexibility. Compared to the single-layer OPS, our proposed solution can simultaneously reduce both speedup and packet delay. For example, a delay of 4/spl delta/N slots can be achieved with a speedup of 2 in our solution (where N is the switch size and /spl delta/ is the switch reconfiguration overhead), whereas the single-layer OPS needs a speedup of 6 for a delay of 7/spl delta/N slots. We show that this significant improvement benefits from a careful overall design rather than simply adding an extra switching layer.

Despite the rich literature on modeling TCP, we find two common deficiencies with the existing approaches. First, none of the work gives sufficient treatment to slow-start, although almost all of them show that retransmission timeout events are common. Second, the probability that retransmission timeout occurs has been underestimated, because retransmission timeout is coupled with fast recovery but fast recovery has not been properly modeled in the previous work. In this paper, new analytical models for predicting the steady state throughput of TCP flows are proposed. All major TCP mechanisms, including slow-start, congestion avoidance, fast retransmit, and fast recovery, are jointly considered under both bursty and independent loss models. We show that our proposed throughput models capture TCP performance more accurately.

In this paper, we present an accurate frequency offset estimation method for frequency-selective channels. Through the iterative use of the chirp z-transform (CZT) algorithm, an accurate frequency offset estimator is proposed, approaching the Cramer-Rao bound (CRB) even at low signal-to-noise ratio (SNR). Further, the estimation can he achieved within one block of training sequence, thus avoiding the transmission of repetitive known blocks as is usually required in many conventional methods. Meanwhile, the overall complexity is acceptable. More importantly, the CZT operation can utilize the fast Fourier transform (FFT) structure that is favourable for digital signal processor (DSP) implementation. Simulation results show that two or at most three iterations of the CZT computation are sufficient for an accurate frequency offset estimation in the SNR range from 0 dB to 30 dB.

We propose to improve the throughput performance of optical burst switching by using regional controller nodes and window-based reservation. Both methods increase the information available to the intermediate nodes during scheduling decisions. Simulations show that the proposed reservation schemes provide significant improvement in the throughput performance compared with the original optical burst switching when the network is heavily loaded.

A novel receiver-initiated soft-state probabilistic multicasting protocol (RISP) for mobile ad hoc network is proposed in this paper. RISP introduces probabilistic forwarding and soft-state for making relay decisions. Multicast members periodically initiate control packets, through which intermediate nodes adjust the forwarding probability. With a probability decay function (soft-state), routes traversed by more control packets are reinforced, while the less utilized paths are gradually relinquished. In this way, RISP can adapt to node mobility; at low mobility, RISP performs similar to a tree-based protocol; at high mobility, it produces a multicast mesh in the network. Simulation results show RISP has lower delivery redundancy than mesh-based protocols, while achieving higher delivery ratio. Further, the control overhead is lower than other compared protocols.

QoS routing, which satisfies diverse application requirements and optimizes network resource utilization, needs accurate link states to compute paths. Suitable link state update (LSU) algorithms which ensure timely propagation of link state information are thus critical. Since traffic fluctuation is one of the key reasons for link state uncertainty and existing approaches cannot effectively describe its statistical characteristics, we propose a novel stability-based (SB) LSU mechanism which consists of a second-moment-based triggering policy and a corresponding stability-based routing algorithm. They incorporate knowledge of link state stability in computing a stability measure for link metrics. With extensive simulations, we investigate the performance of the SB LSU mechanism and evaluate its effectiveness compared with existing approaches. Simulation results show that SB LSU can achieve good performance in terms of traffic rejection ratio, successful transmission ratio, efficient throughput and link state stability while maintaining a moderate volume of update traffic.

To maximize system throughput and guarantee the quality of service (QoS) of multimedia traffic in orthogonal frequency division multiplexing (OFDM) systems with smart antennas, a new packet scheduler is introduced to consider QoS requirements, packet location in the frame, and modulation scheme. In OFDM, several consecutive subcarriers are grouped as a frequency subband. Each subband in a frame can be reused by several users with smart antennas. In this paper, based on the best-fit algorithm proposed for TDMA and the physical features of OFDM, a new packet scheduler is proposed to allocate different BER-classified traffics into the frame. Adaptive modulation is also applied in the scheduler. When compared with existing schedulers, our scheduler achieves higher system capacity with much reduced complexity. The use of adaptive modulation further enhances the system capacity. Simulation results demonstrate that as the traffic load increases, the new scheduler has much better performance in system throughput, average delay, and packet loss rate.

The original power controlled multiple access (PCMA) protocol does not support service differentiation. In this paper, we extend PCMA to form a new media access control protocol supporting service differentiation in mobile ad hoc networks. To support QoS, we first introduce the in-station access category concept in 802.11e to PCMA. For service differentiation between access categories, our major contribution is to propose a sender-initiated busy tone based mechanism that allows a user to gain quick channel access. This quick access mechanism is only performed when the number of access failures exceeds a threshold. An access category with higher priority is assigned a lower threshold for easier channel access, and vice versa. Through analysis and simulation, we demonstrate that our protocol can provide better quality of service than 802.11e in terms of throughput, delay, loss, and fairness.

Transmission control protocol (TCP) performs well in traditional wired networks where the packet loss rate is low. However, in heterogeneous wired/wireless networks, the high packet loss rate over wireless links may result in excessive invocation of the congestion control algorithm, thus deteriorating the performance of TCP. In this paper, a novel localized link layer retransmission protocol, called clustered-loss retransmission protocol (CLRP), is proposed. CLRP consists of three protocol components, namely, TCP-FH deployed on a fixed host, TCP-MH deployed on a mobile host and CLRP-BS deployed on a base station. CLRP can provide not only explicit distinction between congestion and packet corruption losses, and effective multiple wireless loss information for retransmissions, but also better retransmission control for wireless losses. Thus it is well suited to wireless networks, in which packet loss and bursty packet corruption is a serious problem. Moreover, CLRP does not require any modifications to TCP deployed on fixed hosts.

In this paper, we propose an architecture for providing distributed Certificate Authority (CA) service in Mobile Ad Hoc Networks (MANET), based on threshold cryptography. We have two major contributions: 1) we make use of the cluster structure to provide CA service, and design a scheme for locating CA server nodes in MANET; 2) we provide a proactive secret share update protocol, which periodically updates CA secret shares with low system overhead. Compared with existing approaches, our CA architecture provides faster CA services to user nodes at reduced system overhead.

Multicasting protocols deliver data packets from a source node to multiple receivers, and serve a very important function in mobile ad-hoc networks (MANETs). In this paper, a novel receiver-initiated soft-state probabilistic multicasting protocol (RISP) for MANETs is proposed. RISP is inspired by the ant colony's route-seeking mechanism, in which an individual ant chooses the optimal path to its destination through cooperation with others in a totally distributed manner. Imitating the behaviour of ants in nature, RISP introduces probabilistic forwarding and soft-state for making relay decisions that are automatically adaptive to node mobility in MANETs. Compared with other protocols, we show by computer simulations that RISP has lower delivery redundancy, while achieving higher delivery ratio at all mobility scenarios. Furthermore, RISP has lower control overhead.

In this paper, we propose a new approach to establishing application layer conference trees for multimedia multipoint conferences on the Internet using the Megaco/H.248 protocol, a Voice over IP (VoIP) media gateway control protocol. In existing VoIP protocols (and also legacy telephone networks), a multipoint conference takes place through an MCU, and forms a star topology centered at the MCU. This paper suggests to establishing shared, cost effective conference trees for VoIP conferences. Each tree is rooted at the conference initiator, who initiates the conference, and spans over all the conference members. Tree branches grow or are trimmed dynamically and adaptively, in a way to avoid the growth of a skewed tree. We develop a simplified analytical model and conduct simulations to evaluate the performance of the proposed approach. The results show that our approach enjoys the advantage of lower join latency and better bandwidth efficiency compared to the traditional MCU approach, and is cost effective compared to a near optimal Steiner tree.

In this paper, we propose a new scheduler for orthogonal frequency-division multiplexing (OFDM) wireless communication systems, called channel-condition and packet-length dependent packet generalized processor sharing (CPLD-PGPS) scheduler. The CPLD scheduler considers the condition of the physical channel and the length of packets at the same time, and optimally allocates the subcarriers in a frame. With this scheduler the system can achieve better system BER performance, and correspondingly superior PER performance. The system throughput is improved, at the same time the required bandwidth is guaranteed, and long term fairness for all the traffic in the system is provided. In order to reduce the algorithm complexity, a simplified CPLD is proposed, which maintains the system throughput as in the original scheduler, and guarantees the system performance with properly set system parameters. The superior performance of the proposed scheduler is demonstrated by simulation results.

Explicit control protocol (XCP) is a promising transport layer protocol for satellite IP networks. Nevertheless, two problems of XCP can be identified: low throughput under high link error rate conditions; output link underutilization in the presence of rate-limited connections. To address the first problem, we propose to maintain the transmission rate of an XCP sender when triple duplicate ACK is detected. To solve the second problem, we propose to adjust the aggregated feedback based on the ratio of the number of rate-limited connections to the total number of connections sharing the link. We then combine our proposed solutions to form a new protocol, called P-XCP. Simulation results show that P-XCP overcomes the two problems of XCP. When packet error rate is over 0.1, P-XCP is shown to enjoy a throughput almost double that of XCP.

This paper proposes an integrated routing and grooming algorithm for IP over WDM networks. Assuming a peer model in GMPLS-Based optical networks, we take into account the combined topology and resource usage information on both IP and WDM layers. Based on a clustering technique called blocking island paradigm, we propose an enhanced blocking island graph (BIG) network model with blocking island hierarchy (BIH) to abstract network resources. The main idea of the algorithm is to keep the integrity and load balance of related blocking islands. We also combine a cost function in the routing algorithm to groom traffic flows into active lightpaths. The complexity of the algorithm is analyzed to show its efficiency. In the simulation, we compare the algorithm with three other integrated routing algorithms in terms of blocking probability. The three algorithms are: the integrated min-hop (IMH) routing algorithm, the maximum open capacity (MOCA) routing algorithm and the IP-WDM grooming (IWG) algorithm. Simulation results show our algorithm has the best performance.

Optical time division multiplexing (OTDM) is an effective approach to improve the performance of wavelength-routed (WR) networks. Implementation of all-optical time-slot routing in OTDM-WR networks is difficult owing to the lack of practical optical buffer and sophisticated optical processing devices. In this paper, a wavelength-switched time-slot routing scheme that can be implemented with fast wavelength converters only is proposed. Simulation results demonstrate that the performance of the proposed scheme is much better than that of WR networks and is comparable to OTDM-WR networks with time-shared space switching.

Shared channel contention-based MAC protocols, such as IEEE 802.11, are popular in ad hoc networks because of their ease of implementation. However, these contention-based MAC protocols do not coordinate between nodes at different hops within a multi-hop flow. This results in channel resource and node transmission power wastage and overall system throughput degradation. In this paper we present a novel distributed flow-based scheduling (DFBS) scheme that coordinates between neighbor links of a multi-hop flow. As demonstrated by the simulation results, DFBS achieves higher throughput and improves the transmission efficiency when traffic load is relatively high.

We analyze the maximum throughputs of slotted-ALOHA-based multihop ad hoc networks with and without capture, by considering the degree (number of neighbors) of each node, and, different from prior research, allowing each node to have a different transmission probability. We propose a novel enhanced slotted ALOHA scheme, in which each station adaptively transmits packets according to the degrees of the stations' neighbors. The analytical and simulation results show that the enhanced scheme can improve the network performance greatly.

We provide a sub-channel partitioning based unequal error protection (UEP) scheme for a space-time block coded orthogonal frequency division multiplexing (STBC-OFDM) system. In such a scheme, video data is partitioned into high-priority (HP) and low-priority (LP) layers according to the importance of the data. At the receiver side, OFDM sub-channels are partitioned into high-quality (HQ) and low-quality (LQ) groups according to the estimated channel qualities. Based on the feedback of sub-channel partitioning results, the transmitter assigns HP and LP video data to the corresponding HQ and LQ sub-channels. Through theoretical analysis, we show there is indeed a significant BER difference between the HQ and LQ sub-channels, which can be exploited by UEP. Based on the analysis, we provide a criterion for determining the appropriate transmission power. Through computer simulations, we show that the proposed scheme offers significant performance gain compared to conventional methods. We also demonstrate that the scheme is the least sensitive to channel estimation errors among all compared schemes, and is hardly influenced by the Doppler spread. The feedback overhead can also be reduced with almost no performance penalty by bundling several neighboring sub-channels together and assigning them to the same group.

Voice-over-IP (VoIP) is.an important application on the Internet. With the emergence of WLAN technology and its various advantages compared with the traditional wired LAN, it is fast becoming the "last-mile" of choice for the overall Internet infrastructure. This work considers the support of VoIP over 802.11b WLAN. We show that although the raw WLAN capacity can potentially support more than 500 VoIP sessions, various overheads bring this down to only 12 VoIP sessions when using GSM 6.10 codec. We propose a novel multiplexing scheme for VoIP which exploits multicasting over WLAN for the downlink VoIP traffic. This scheme can achieve nearly 100% improvement in system capacity. In addition, we present results showing that the delay and delay jitter introduced by the proposed scheme are small. We believe that the scheme can reduce the blocking probability of VoIP sessions in an enterprise WLAN significantly.

Service discovery protocols allow clients to discover services without actual knowledge of the locations or characteristics of the services. Jini and Bluetooth SDP are two common service discovery protocols. They may meet each other in many environments. But there is still no general architecture to bring them together. We introduce an architecture for Bluetooth client to discover Jini services. We introduce the Jini/sup TM/ profile for Bluetooth, which runs in three modes of operations, namely, surrogate, bridge, and client. We describe the implementation of a Jini/Bluetooth surrogate as well as the bridge which acts as a proxy and allows a multihop connection to a Jini network. To enable reliable end to end connection, we also incorporate session management into our design.

Many space-time codes (STC) have been proposed to enhance the performance of wireless communications in flat fading channels. All of them rely on the knowledge of the channel, and are hence affected by the channel estimation errors. In this paper, we investigate STC robustness under imperfect channel knowledge. We first define the concept of "closeness" by comparing the BER under channel estimation errors with that under perfect channel knowledge, aiming to characterize STC performance degradation due to imperfect channel knowledge. Then the robustness of STC can be compared by their "closeness" to perfect results. We find that for systems with two and three transmit antennas, the space time block codes (STBC) are always more robust to channel estimation errors than space time trellis codes (STTC). With the increase of receive diversity, all STC become more robust to the channel estimation errors. For STTC, as the number of trellis states increases, the codes become less robust to the channel estimation errors. We also compare the BER performance of STC in the presence of channel estimation errors. For the two-transmit-antenna system, the performance of STBC is always better than that of the 4-state STTC, but is always worse than 16-state STTC. For systems with three transmit antennas, the BER performance of STTC is much better than that of STBC.

An ad hoc network is composed of geographically dispersed nodes that may move arbitrarily and communicate with each other without the support of a stationary infrastructure. Compared with a wireless network with a stationary infrastructure, such as a cellular network, an ad hoc network is inherently less efficient. Therefore, a number of proposals have been made to develop a quasi-stationary infrastructure for ad hoc networks. However, the dynamic nature of ad hoc networks makes it very costly to maintain such an infrastructure. The article proposes a vertex-linked infrastructure (VLI) for ad hoc networks. This novel approach uses an easily deployable, survivable, wired infrastructure as a backbone of the ad hoc network, thus realizing the advantages of an infrastructure in wireless communications, but without the overhead due to maintaining such an infrastructure.

In this work, we introduce the idea of adaptive sub-channel allocation based unequal error protection (ASCA-UEP) to a space-time block coded orthogonal frequency division multiplexing (STBC-OFDM) system. In such a system, UEP is realized by adaptively allocating and transmitting high-priority and low-priority video data over high-quality and low-quality sub-channels, respectively. Further, we propose two ASCA-UEP schemes in a time division duplex (TDD) system: a receiver-based scheme and a transmitter-based scheme. Analysis and simulation results demonstrate that ASCA-UEP greatly enhances the quality of video reception, and the transmitter-based scheme is more robust to uplink channel noise than the receiver-based scheme, and is thus preferred when the receiver is power-constrained and the transmitter has sufficient power.

The problem of super-resolution time delay estimation in multipath environments is addressed in this paper. Two cases, active and passive systems, are considered. The time delay estimation is first converted into a sinusoidal parameter estimation problem. Then the sinusoidal parameters are estimated by generalizing the multiple signal classification (MUSIC) algorithm for single-experiment data. The proposed method, referred to as the MUSIC-type algorithm, approximates the Cramer-Rao bound (CRB) in terms of the mean square errors (MSKs) for different signal-to-noise ratios (SNRs) and separations of multipath components. Simulation results show that the MUSIC-type algorithm performs better than the classical correlation approach and the conventional MUSIC method for the closely spaced components in multipath environments.

TCP is the most widely adopted transport layer communication protocol. In heterogeneous wired/wireless networks, however, the high packet loss rate over wireless links can trigger unnecessary execution of TCP congestion control algorithms, resulting in performance degradation. TCP performs poorly on wireless links with bursty losses, when it is forced to rely on limited information available from batched acknowledgements, (i.e., multiple packets are acknowledged with one acknowledgment packet). In this paper, a selective negative acknowledgement (SNACK) mechanism is designed to overcome the limitation of batched acknowledgments. A new link layer retransmission protocol, called, SNACK-NS (new snoop), is proposed. Through the detection and retransmission functions that are provided by the two protocol components of SNACK-NS, namely, SNACK-snoop and SNACK-TCP, the transmission performance of TCP over wireless network is greatly enhanced in both fixed host (FH) to mobile host (MH) and MH to FH transmissions.

The delivery of quality video service often requires high bandwidth with low delay or cost in network transmission. Current routing protocols such as those used in the Internet are mainly based on the single-path approach (e.g., the shortest-path routing). This approach cannot meet the end-to-end bandwidth requirement when the video is streamed over bandwidth-limited networks. In order to overcome this limitation, we propose multipath routing, where the video takes multiple paths to reach its destination(s), thereby increasing the aggregate throughput. We consider both unicast (point-to-point) and multicast scenarios. For unicast, we present an efficient multipath heuristic (of complexity O(|V|/sup 3/)), which achieves high bandwidth with low delay. Given a set of path lengths, we then present and prove a simple data scheduling algorithm as implemented at the server, which achieves the theoretical minimum end-to-end delay. For a network with unit-capacity links, the algorithm, when combined with disjoint-path routing, offers an exact and efficient solution to meet a bandwidth requirement with minimum delay. For multicast, we study the construction of multiple trees for layered video to satisfy the user bandwidth requirements. We propose two efficient heuristics on how such trees can be constructed so as to minimize the cost of their aggregation subject to a delay constraint.

A deflection routing scheme for small to medium size future all-optical networks with arbitrary topologies is proposed. The proposed scheme assumes only single-bit all-optical processing and no buffers. The primary output selection and the alternate output choices by a packet at each node are encoded in the packet header in order to reduce the signal processing requirement. Additional features such as priority and time-to-live fields have also been defined. The performance of the deflection routing scheme is studied using the AT&T North America OC-48 optical fiber network topology.

Two general-purpose decomposition methods to calculate the blocking probabilities of connection-oriented networks are presented. The methods are based on either the call status or the link status of the networks, and can significantly reduce the required computational times. A heuristic is presented to simplify the application of the proposed decomposition methods on networks with irregular topologies. Numerical examples are given to demonstrate the applications of the proposed methods.

MEMS optical switch technology is one of the key technologies in wavelength division multiplexing (WDM) optical networks. Although the 2-D MEMS optical switch technology is mature, the commonly used crossbar architecture is not amenable to building large switches. In this paper, we propose a design of 2x2 switching modules, and use it to build large 2-D MEMS optical switches with architectures such as Spanke-Benes and Benes networks.

Data exchange within a Bluetooth piconet is master-driven. The channel/slot utilization thus depends on the efficiency of the scheduling algorithm adopted by the master. In this paper, a novel MAC layer scheduling algorithm, called floating threshold (FT), is proposed. Unlike existing approaches, FT allows the master to estimate the backlog queue status at each slave accurately based only on a single feedback bit and a floating threshold. The master can then derive an optimized packet transmission schedule. Using simulations, we show that FT outperforms existing algorithms in terms of channel utilization, packet delay and packet dropping probability.

This paper examines the impact of RED on two versions of TCP - traditional TCP Reno and a newly proposed variant, TCP Veno - over 802.11b WLAN. TCP Reno was originally designed for wired networks where packet losses are primarily due to network congestion. This assumption is not always true in wireless networks, in which packet losses can be due to transmission errors on the noisy wireless link. TCP Veno refines the algorithms in Reno by distinguishing between noncongestive and congestive states, and avoids the unnecessary reduction of TCP congestion window when packet losses are not due to congestion. Our results show that TCP Veno can achieve up to 30% more throughput than TCP Reno when link quality is poor. Our results also show that TCP Veno is compatible with RED. In addition, although RED does not help to further improve the throughput in Veno, it can improve fairness among co-existing TCP flows.

In this paper we propose a novel wireless scheduling algorithm for delay-sensitive (DS) and best-effort (BE) traffics. Unlike the majority of the previous wireless scheduling, where the wireless links are modeled as having only two states, our algorithm is applicable to links with multiple states. For DS flows, the algorithm is capable of providing statistical delay violation bounds. Such bounds are derived, analytically, using the idea of the statistical service envelope. For BE flows, we propose a new notion of fairness, called long-term link-quality weighted outcome-fair, which we believe is more suited to wireless networks than pure outcome-fair or effort-fair. The algorithm achieves a balance between bandwidth efficiency requirement and fairness requirement, and guarantees minimal goodput levels for BE flows.

In this paper, we study the uplink performance of an orthogonal frequency division multiplexing (OFDM) wireless system where multiple antennas are utilized at the base station (BS). Further, capacity can be greatly enhanced through spatial division multiple access (SDMA), so that several users can transmit packets simultaneously to the BS. The system performance is determined by various transmission techniques, including methods for channel estimation, modulation, as well as channel coding. Conventional parameters such as packet error rate (PER) and bit error rate (BER) are unable to reflect the actual system performance because no consideration is given to the overheads incurred by the transmission techniques. Therefore, we are motivated to propose a novel concept called effective throughput to characterize the capacity available to users by incorporating all these factors. The effective throughput for a user can be viewed as the average number of successfully received data bits in an OFDM symbol after excluding erroneously received packets and the overheads due to channel estimation and coding. It also directly relates to the transmission delay of a user packet. The system effective throughput is the aggregated effective throughput of all users. Simulation results demonstrate that effective throughput can serve as a useful and more meaningful benchmark parameter in optimizing system performance.

Nonbinary type-II hybrid ARQ (HARQ), which combines shortened Reed-Solomon (RS) code with ARQ, is proposed. Its throughput is obtained by extending Lin and Yu's analysis of binary type-Il HARQ. Analytical results show that nonbinary HARQ outperforms its binary counterpart in throughput over Rayleigh fading channels when the modulation scheme and the FEC subsystem are selected properly.

We study the slotted ALOHA with multiple random access channels, the so called multi-channel ALOHA (MC-ALOHA). It is well known that single-channel ALOHA (SC-ALOHA) is unstable. Not surprisingly, MC ALOHA is also unstable. A stabilization algorithm for MC-ALOHA has been proposed in [D. Shen and V.O.K. Li, 2002], in which the pseudo-Bayesian algorithm in SC-ALOHA was extended to achieve stabilized MC-ALOHA. The idea is to estimate the number of attempting users so that user transmission probability can be adjusted accordingly. In this paper, we give a theoretical analysis on the algorithm performance for cases with limited and unlimited number of users by assuming perfect estimate. The theoretical results are validated by simulation, which shows the stabilization algorithm performs close to a system with perfect estimate. The simulation results also show that the performance of the stabilized algorithm is much better than the non-stabilized algorithm. With the stabilized algorithm, the system is always stable when the new packet arrival rate is less than system capacity. Even when the arrival rate is higher than capacity, system throughput can still be guaranteed.

This paper investigates the performance of coded orthogonal frequency division multiplexing (OFDM) systems with receiving adaptive array through which multiple users with single-element transmitting antenna are supported simultaneously in spatial division multiple access (SDMA). We characterized the performance of an OFDM/SDMA systems by effective throughput, which is essentially the average number of data bits in an OFDM symbol after considering the erroneous packet transmissions and modulation scheme by excluding the overhead from coding and pilots for channel estimation. Optimization of system operating parameters can be achieved through the maximization of effective throughput. The focus of the performance of coded OFDM/SDMA systems. Through extensive computer simulation, we show that using more pilots always improves bit error rate (BER) performance, but may reduce effective throughput. The optimal number of pilots together with the modulation scheme can be determined by maximizing the effective throughput for given operating signal-to-noise ratio (SNR). It is also shown that the system performance degrades gradually with the increase of users. For a system with a six-element adaptive array, the effective throughput with 5 users is lower than that with 4 users for a certain range of SNR. This indicates that the maximal number of users supportable by the system should consider the effective throughput.

Current efforts on ad hoc wireless network research are focused more on routing and multicasting protocols. However, there is an increasing need to understand what sort of media could be transported over wireless ad hoc networks other than data. Existing research on multimedia wireless communications often addresses broadband wireless networks with a connection-oriented backbone. In this paper, we address the possibility of transporting audio traffic over wireless ad hoc networks. We examine the impact of wireless multi-hop links on audio data relay and how the audio quality at the receiver is affected. In particular, we examine communication parameters such as latency, jitter, packet loss, and their impact on perceived audio quality.

Cross layer design is a promising approach in mobile ad hoc networks (MANET) to combat the fast time-varying characteristics of wireless links, network topology, and application traffic. In this paper, we employ cross layer design to develop a novel-scheduling scheme with two optimisations aimed at service differentiation. The scheduling scheme is executed at the network layer of every station according to the channel conditions estimated by the MAC layer. The optimizations are based on traffic property sharing and packet timeout period interaction to reduce the packet collisions and improve network performance. We evaluate the proposed scheme under different network loads in terms of packet delivery ratio, average end-to-end delay and delay jitter. The simulation results show that our scheme can provide different service differentiations for time-bounded and best effort traffics. In particular, we can guarantee the delay and delay jitter requirements of time-bounded traffic.

An adaptive packet scheduling algorithm for cellular CDMA systems is proposed. The algorithm guarantees packet deadline and average data rate under the assumption of perfect power control. Channel condition is also considered to reduce the transmission power.

An important, yet difficult, problem in the design of a packet radio network is the determination of a conflict-free broadcast schedule at a minimum cycle length. We first formulate the problem via a within-two-hop connectivity matrix and then, by assuming a known cycle length, determine a conflict-free scheduling pattern using a centralized approach that exploits the structure of the problem via a modified genetic algorithm. This algorithm, called genetic-fix, generates and manipulates individuals with fixed size (i.e., in binary representation, the number of ones is fixed) and therefore, can reduce the search space substantially. We also propose a method to find a reasonable cycle length and shorten it gradually to obtain a near-optimal one. Simulations on three benchmark problems showed that our approach could achieve 100% convergence to solutions with optimal cycle length within reasonable time.

Packet scheduling is key to the provision of quality of service (QoS) differentiation and guarantees in a wireless network. Unlike its wireline counterpart, wireless communication poses special problems such as time-varying link capacity and location-dependent errors. These special problems make designing efficient and effective scheduling algorithms for wireless networks very challenging. Although many wireless scheduling algorithms have been proposed in recent years, some issues remain unresolved. This paper introduces a new wireless scheduling algorithm called BGFS-EBA (bandwidth-guaranteed fair scheduling with effective excess bandwidth allocation), which addresses these issues. It is shown that BGFS-EBA distributes excess bandwidth effectively, strikes a balance between effort-fair and outcome-fair, and provides delay bound for error-free flows and transmission effort guarantees for error-prone flows. The new algorithm is compared with some recent wireless scheduling algorithms.

A new routing method, known as active routing, has been emerging. This involves using active packets to configure customized network paths. Based on a Markov decision model, this paper presents an active routing service for active networks in general and the next generation network, called ISDN3, in particular. Our aim is to determine the active routing policy so as to minimize the network cost. Theoretical analysis is presented to show the advantages of our proposal as compared with three other approaches.

Two multicast protocols are proposed for deflection-routed all-optical packet-switched networks. One scheme sends a deflected multicast packet back to the root node while the other sends it back to the deflection point. Both schemes can be implemented using demonstrated optical signal processing technology. The performance of the two proposed multicast schemes are compared using Manhattan street networks. We found that the back-to-the-root-node scheme performed better than the back-to-the-deflection-node scheme. A hybrid approach can further improve the system performance.

Multiple access based on orthogonal frequency division multiplexing (OFDM), or OFDMA, enables multiple users to simultaneously access the media by using different subcarriers. This leads to the convenient realization of multi-channel ALOHA, in which each user transmits with a group of subcarriers. In this paper, we first introduce the multi-channel slotted ALOHA algorithm to OFDM, which is called OFDMA-based multi-channel ALOHA (OMC-ALOHA). Since ALOHA is an unstable algorithm, we show OMC-ALOHA is also unstable. To solve this stability problem, we extend the pseudo-Bayesian algorithm to achieve stabilized OMC-ALOHA.

In this paper, we propose RALF, a new FEC-based error control protocol for layered multicast video. RALF embodies two design principles: decoupling transport layer error control from upper layer mechanisms and decoupling error control and congestion control at the transport layer. RALF works with our previously proposed protocol RALM - a layered multicast congestion control protocol with router assistance. RALF provides tunable error control services for upper layers. It requires no additional complexities in the network beyond those for RALM. Its performance is evaluated through simulations in NS2.

The differentiated services (DiffServ) architecture has been proposed as a scalable solution for delivering end-to-end quality of service (QoS) guarantees over the Internet. While the scalability of the data plane emerges from the definition of only a small number of different service classes, the issue of a scalable control plane is still an open research problem. The initial proposal was to use a centralized agent, called bandwidth broker (BB), to manage the resources within each DiffServ domain and make local admission control decisions. We propose an alternative distributed approach, where the local admission decisions are made independently at the edge routers of each domain. We show, through simulation results, that this distributed approach can manage the network resources very efficiently, leading to lower bandwidth blocking rates when compared to traditional shortest path admission control. Moreover, its simplicity and distributed implementation make it a very scalable solution for resource management in DiffServ networks.

In this paper we propose a general utility-oriented adaptive quality of service (QoS) model for wireless networks and establish a framework for formulating the bandwidth allocation problem for users with time-varying links. For slow link variations, it is inadequate to only employ low-level adaptive mechanisms at the symbol or packet level, such as error correction coding or swapping packet transmission opportunities. To improve bandwidth utilization and satisfy users' QoS requirements, high-level adaptive mechanisms working at larger time scale are needed. We propose an adaptive bandwidth allocation scheme, which is capable of providing QoS guarantees, ensuring long-term fairness, and achieving high bandwidth utilization. A finite-state Markov channel model (FSMC) is used to model wireless links.

The Internet is organized as an interconnection of separate administrative domains called autonomous systems (ASs). The border gateway protocol (BGP) is the de facto standard for controlling the routing of traffic across different ASs. It supports scalable distribution of reachability and routing policy information among different ASs. In this paper, we study a network design problem which determines (1) the optimal placement of border router(s) within a domain and (2) the corresponding inter- and intra-domain traffic patterns within an AS. Practical constraints imposed by BGP and other standard shortest-path-based intra-domain routing protocols are considered. The problem is formulated as a variant of the uncapacitated network design problem (UNDP). While it is feasible to use a brute-force, integer-programming-based approach for tackling small instances of this problem, we have resorted to a dual-ascent approximation approach for mid/large-scale instances. The quality of the approximation approach is evaluated in terms of its computational efficiency and network cost sub-optimality. Sensitivity analysis w.r.t. various network/traffic parameters are also conducted. We then describe how one can apply our optimization results to better configure BGP as well as other intra-domain routing protocols. This serves as a first-step towards the auto-configuration of Internet routing protocols, BGP in particular, which is "well-known" for its tedious and error-prone configuration needs.

A deflection routing algorithm that can be applied to a novel self-routing address scheme for networks with arbitrary topology is proposed. The proposed deflection routing algorithm can be implemented all-optically using bitwise optical logic gates. Besides the primary output link selection, alternate output link choices by a packet at each node in case of deflection are also encoded in the address header. Priority classes can also be defined in the proposed address scheme. The performance of the deflection routing algorithm is studied using the AT&T North America OC-48 optical fiber network topology.

Several layered multicast protocols have been proposed for congestion control in real-time multicast applications. Most of them are pure end-to-end protocols, thus having difficulty in coordinating receivers and coping with traffic variations. We propose RALM, a new receiver-driven router-assisted layered multicast protocol. RALM achieves much better performance at the expense of moderate additional complexity in the network. RALM is incrementally deployable. We evaluate RALM through simulations, and compare its performance with RLM, the well known layered multicast protocol.

Burst transmission protocols have been proposed in the next generation CDMA cellular systems to support short-time high-speed data communications. The existing burst admission algorithm considers only the current interference condition in the system. The burst transmission request will be rejected if the interference in the system exceeds the acceptable level with the burst admitted. In this paper we propose a new burst admission algorithm where a currently unacceptable burst request can be assigned to start at a later time when the system interference level is lower. The interference prediction is based on the establishing, updating, and exchanging of the load and burst scheduling tables among the neighboring cells. Simulations show that our method can reduce the burst blocking probability and improve the system resource utilization.

Short BCH codes for multimedia communication are examined in a typical fast fading channel. In adverse fading channel, burst errors degrade the quality of transmission badly. Generally, long BCH codes and large interleaving degree are adopted to improve the performance of system, thus causing inevitable long delay, which sometimes is fatal to multimedia data. We propose to employ short BCH codes (n<32) with medium interleaving depth on static images compressed by discrete-cosine-transformation (DCT), a widely used compression method in multimedia data. The structure of coding meets the rigorous delay request of multimedia communication. Simulation results amply demonstrate the validity of the proposed scheme in fading environment. The aspects of delay and reliability are both satisfied.

Multicasting is a mechanism to send data to multiple receivers in an efficient way. We give a comprehensive survey on network and transport layer issues of Internet multicast. We begin with an introduction to the current Internet protocol multicast model-the "host group" model and the current Internet multicast architecture, then discuss in depth the following three research areas: (1) scalable multicast routing; (2) reliable multicast; and (3) multicast flow and congestion control. Our goal is to summarize the state of the art in Internet multicast and to stimulate further research in this area.

The capacity of the forward link in multiservice DS-CDMA systems is analyzed. Capacity constraints are derived with respect to the number of users in each service class. Shadowing, hard/soft handoffs, and data rate variations are considered in the analysis. Solutions of the capacity constraints are used to compare the forward link capacity with hard and soft handoffs. The accuracy of the solutions is verified by simulations.

During the past few years, new types of Internet applications which require performance beyond the best-effort service that is provided by the current Internet have emerged. These applications include the transmission of voice and video, which require a fixed end-to-end delay bound in order for the end-user to perceive an acceptable level of service quality. The differentiated services (DiffServ) model has been proposed to enhance the traditional best-effort service, and provide certain quality of service (QoS) guarantees to these applications. Its current definition, however, does not allow for a high level of flexibility or assurance and, therefore, it can not be widely deployed. We introduce a new protocol for a DiffServ architecture which provides a simple and efficient solution to the above problem. It is a complete protocol, in the sense that it deals with the issues of packet scheduling, admission control, and congestion control. We show, through experimental results, that our proposed protocol can improve the flexibility and assurance provided by current solutions, while maintaining a high level of network utilization.

Self-similar traffic is distinguished by positive correlation, which can be exploited for better traffic management. Inspired by measurement-based admission control schemes, a measurement-based congestion alarm is proposed. The aggregate traffic at an output port of a switch or router in a high-speed network is modeled by a fractional Gaussian noise process. Traffic measurements are performed in regular time intervals to determine the current traffic loading. This information is then used to predict the loading situation in the near future. If congestion is likely to occur, a congestion alarm is set off and appropriate network management functions taken to alleviate the possible congestion. The above constitutes a closed loop feedback control mechanism that maintains high resource utilization. Simulation results show that the proposed scheme, when used with dynamic bandwidth allocation, reduces bandwidth requirements by more than 20%.

Satellite communication is distinguished by global coverage and the ability to support a wide range of applications. LEO (low Earth orbit) satellite systems employing inter-satellite links offer rich connectivity in space and provide direct broadband access and personal communication services. One of the technical challenges for LEO systems is the design of efficient routing strategies tailored to their highly dynamic nature. In this paper, we present a new routing method which solves the routing problem efficiently by overlaying a static logical topology over the physical constellation. The algorithm generates near-optimal shortest paths. The performance of our proposed scheme is evaluated through theoretical analysis and simulations.

Due to limited available photonic devices, optical networks in the near future will likely employ routing schemes that do not require sophisticated processing of optical packets. In this paper, we propose a novel self-routing scheme for all-optical packet networks that can be applied to networks with arbitrary topology. The proposed routing scheme requires only single bit processing and can be implemented with existing technologies.

Scheduling algorithms that support quality of service (QoS) differentiation and guarantees for wireless data networks are crucial to the development of broadband wireless networks. Wireless communication poses special problems that do not exist in wireline networks, such as time-varying channel capacity and location-dependent errors. Although many mature scheduling algorithms are available for wireline networks, they are not directly applicable in wireless networks because of these special problems. This paper provides a comprehensive and in-depth survey on recent research in wireless scheduling. The problems and difficulties in wireless scheduling are discussed. Various representative algorithms are examined. Their themes of thoughts and pros and cons are compared and analyzed. At the end of the paper, some open questions and future research directions are addressed.

Wideband code division multiples access (CDMA) is one of the major options for the next generation mobile cellular system. However, there is only limited research on the admission control for CDMA systems containing multiple service classes. In this paper the multi-service CDMA admission control problem is addressed by an approach which is conceptually simple, and yet produces satisfactory results. In our approach the limit on the acceptable interference level in a cell is translated into a constraint on the number of users of each service class in the local and neighboring cells. The randomness of user locations, shadowing and imperfect power control is captured as a whole by a log-normal distribution. Simulation results show that this approach is quite accurate over a wide range of required system outage probabilities.

We propose a framework to study how to effectively perform load sharing in multipath communication networks. A generalized load sharing (GLS) model has been developed to conceptualize how traffic is split ideally, on a set of active paths. A simple traffic splitting algorithm, called weighted fair routing (WFR), has been developed at two different granularity levels, namely, the packet level, and the call level, to approximate GLS with the given routing weight vector. The packet-by-packet WFR (PWFR) mimics GLS by transmitting each packet as a whole whereas the call-by-call WFR (CWFR) imitates GLS so that all packets belonging to a single flow are sent on the same path. We have developed some performance bounds for PWFR and formed that PWFR is a deterministically fair traffic splitting algorithm. This attractive property is useful in the provision of service with guaranteed performance when multiple paths can be used simultaneously to transmit packets which belong to the same flow. Our simulation studies, based on a collection of Internet backbone traces, reveal that WFR outperforms two other traffic splitting algorithms, namely, generalized round robin routing (GRR), and probabilistic routing (PRR). These promising results form a basis for designing future adaptive constraint-based multipoint path routing protocols.

In the future deployment of wideband DS-CDMA mobile communication systems, spectrum overlay among subbands with different bandwidths is probably inevitable. In this paper we present an approach to estimate the reverse-link capacity of overlaid multiband DS-CDMA systems in terms of the maximum number of users in each sub-band. We will derive the general capacity formula, and present a decomposition method for the capacity analysis to reduce the computational complexity. Based on this decomposition method the conditions for maximum bandwidth utilization are obtained. These results are then extended to account for imperfect power control cases.

In this paper, we propose a framework to study the resequencing mechanism in high speed networks. This framework allows us to estimate the packet resequencing delay, the total packet delay, and the resequencing buffer occupancy distributions when data traffic is dispersed on multiple disjoint paths. In contrast to most of the existing work, the estimation of the end-to-end path delay distribution is decoupled from the queueing model for resequencing. This leads to a simple yet general model, which can be used with other measurement-based tools for estimating the end-to-end path delay distribution to find an optimal split of traffic. We consider a multiple-node M/M/1 tandem network as a path model. When end-to-end path delays are Gaussian distributed, our results show that the packet resequencing delay, the total packet delay, and the resequencing buffer occupancy drop when the traffic is spread over a larger number of homogeneous paths, although the network performance improvement quickly saturates when the number of paths used increases. We find that the number of paths used in multipath routing should be small, say up to three. Besides, an optimal split of traffic occurs at paths with equal loads.

Video prefetching has been proposed previously for the transmission of variable-bit-rate (VBR) video over a packet-switched network. The objective of these protocols is to prefetch future frames to be stored at the customer's set-top box (STB) in periods of low link utilization. Experimental results have shown that video prefetching is very effective and it achieves much higher network utilization (i.e. larger number of simultaneous connections) than the traditional video smoothing schemes. Video prefetching, however can only be efficiently implemented when there is one centralized server that serves the different customers over a common link. In a distributed environment there is a large degradation in its performance. In this paper we introduce a new scheme that utilizes smoothing along with prefetching, to overcome the problem of distributed prefetching. We show that our scheme performs almost as well as the centralized prefetching protocol even though it is implemented in a distributed environment.

Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. This algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of our algorithm, and examine the topology-transparent characteristics and the sensitivity on design parameters by simulation.

Many transmission scheduling algorithms have been proposed to maximize spatial reuse and minimize the time division multiple access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. The proposed algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of this algorithm and examine the topology-transparent characteristics and the sensitivity on design parameters by analytical and simulation techniques.

Personal communications services (PCS) promise to provide a variety of information exchanges among users with any type of mobility, at any time, in any place, through any available device. To achieve this ambitious goal, two of the major challenges in the system design are: (i) to provide a high-speed wireless subsystem with large capacity and acceptable quality-of-service (QoS) and (ii) to design a network architecture capable of supporting multimedia traffic and various kinds of user mobility. A time-hopping spread-spectrum wireless communication system called ultra-wide bandwidth (UWB) radio is used to provide communications that are low power, high data rate, fade resistant, and relatively shadow free in a dense multipath environment. Receiver-signal processing of UWB radio is described, and performance of such communications systems, in terms of multiple-access capability, is estimated under ideal multiple-access channel conditions. A UWB-signal propagation experiment is performed using the bandwidth in excess of 1 GHz in a typical modern office building in order to characterize the UWB-signal propagation channel. The experimental results demonstrate the feasibility of the UWB radio and its robustness in a dense multipath environment. A ATM network is used as the backbone network due to its high bandwidth, fast switching capability, flexibility, and well-developed infrastructure. To minimize the impact caused by user mobility on the system performance, a hierarchical network-control architecture is postulated. A wireless virtual circuit (WVC) concept is proposed to improve the transmission efficiency and simplify the network control in the wireless subsystem. The key advantage of this network architecture and WVC concept is that the handoff can be done locally most of the time, due to the localized behavior of PCS users.

With the affluence that comes with economic developments and technological advances, citizens around the world will require personalized, on-demand, high-quality information services, which the author calls personal information service (PIS). He foresees that by 2012 A.D., a variety of communication services, and in particular PIS, will be much more widely available around the world. To make such services available to the masses, a number of challenges have to be overcome. In this paper, the author addresses the challenges. He believes that by working together solutions can be obtained by 2012 A.D.

Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple-access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and do not adapt to different traffic requirements. Chlamtac and Farago (1994) proposed a topology-transparent algorithm. Following their approach, but with a different design strategy, we propose another algorithm which is optimal in that it maximizes the minimum throughput. We compare our algorithm with that of Chlamtac and Farago's and with the TDMA algorithm, and find that it gives better performance in terms of minimum throughput and minimum and maximum delay times. Our algorithm requires estimated values of the number of nodes and the maximum nodal degree in the network. However, we show that the performance of our algorithm is insensitive to these design parameters.

MPEG, in addition to being an international standard, is currently the most popular coding scheme for stored video. For several applications that require stored video, such as video-on-demand, it is advantageous to group MPEG frames into segments. Retrieving segments instead of individual frames can result in a more efficient use of disk retrieval resources and consequently, in the support of a larger number of users and in a more cost-effective system. Depending on the value of parameters such as desired user quality of service, size and cost of required buffers, number of disks to stripe a segment across, etc., a certain segment length (defined as the number of frames per segment) may be preferred over others. In this paper, we propose a generalized grouping scheme that may be used to achieve any desired segment length. Properties of such a grouping scheme and formulae that may be used to achieve such a grouping have been provided. Since a segment is an atomic unit of video retrieval, retrieval of some segments is skipped during fast playback. Some frames belonging to retrieved segments may be discarded due to the unavailability of other frames necessary for their decoding. Tradeoffs between different kinds of fast playback (i.e., the choice of skipped segments) and the number of discarded frames is discussed.

A true video-on-demand (VOD) system provides the ultimate flexibility in video services by allowing users to select any video programs, at any time, and to perform any VCR-like user interactions. To allow true VOD, one approach is to have a dedicated video stream for each customer. This is expensive, especially when multiple identical video streams are sent to multiple customers accessing the same video. To be commercially viable, VOD service must be priced competitively with existing video rental services. Batching may be used to reduce this cost. It allows multiple users accessing the same video to share the same video stream. The batching approach, however, complicates the provision of user interactions. Existing batching schemes only allow near VOD services. This paper describes a new protocol, called split and merge (SAM), which offers true VOD services while allowing multiple users to share the same video stream. This sharing is transparent to the users and it appears as if each has a dedicated video stream. Our approach is to split an interactive user from the batch and to serve him with a dedicated video stream. We develop an innovative way to merge these individuals back to the batching streams when they resume normal play mode. The SAM protocol therefore significantly improves the system resource utilization and the number of simultaneous users, and more importantly, allows true VOD services.

Video-on-demand (VOD) servers need to be efficiently designed in order to support a large number of users viewing the same or different videos at different rates. While considering a disk-array based VOD server, use of a shared buffer at the server end may be more economical than the sole use of dedicated buffers at each user's end. In this paper we propose a simple buffer sharing architecture that may be used when disk-array based video servers are used. Our aim is to support the maximum number of users for a given number of video server disks while employing a simple scheme requiring less buffer space. The number of video segment retrievals that can occur within a certain time (the service round) is maximum when the scan disk scheduling algorithm is used. Consequently, we shall assume use of the scan algorithm for disk retrieval. The VOD server has a buffer manager that directs retrieved segments to appropriate buffer locations depending on their release and deadlines. The release and deadlines of segments are such that buffer requirement at the user's set-top box is minimized to two video segments while avoiding video starvation and buffer overflow at the user's end. We propose a novel scheme for the operation of the shared buffer that aims at increasing buffer utilization and decreasing cell loss due to buffer overflow. An ATM based broadband network is assumed and all segments are stored in buffers as fixed length ATM cells.

A distributed multimedia system (DMS) is an integrated communication, computing, and information system that enables the processing, management, delivery, and presentation of synchronized multimedia information with quality-of-service guarantees. Multimedia information may include discrete media data, such as text, data, and images, and continuous media data, such as video and audio. Such a system enhances human communications by exploiting both visual and aural senses and provides the ultimate flexibility in work and entertainment, allowing one to collaborate with remote participants, view movies on demand, access on-line digital libraries from the desktop, and so forth. In this paper, we present a technical survey of a DMS. We give an overview of distributed multimedia systems, examine the fundamental concept of digital media, identify the applications, and survey the important enabling technologies.

This paper examines code-division multiple-access (CDMA) techniques used in slotted fiber-optic packet networks. Since the inherent properties and signal processing of the conventional communication channels are different from those of the fiber-optic channels, new code sequences must be constructed for fiber-optic applications. The goal of our research is to analyze the performance of fiber-optic CDMA packet networks using code sequences with given orthogonality properties.

This paper examines code-division multiple-access (CDMA) techniques used in unslotted fiber-optic packet networks. Since the inherent properties and signal processing of the conventional communication channels are different from those of the fiber-optic channels, new code sequences must be constructed for fiber-optic applications. In unslotted systems, the exact solution is very difficult to obtain. Therefore, two approximation methods are presented to analyze the performance of such systems. Simulation is performed to verify the accuracy of the results.

An interactive video-on-demand (VoD) system allows users to access video services, such as movies, electronic encyclopedia, interactive games, and educational videos from video servers on a broadband network. This paper develops a performance evaluation tool for the system design. In particular, a user activity model is developed to describe the usage of system resources, i.e., network bandwidth and video server usage, by a user as it interacts with the service. In addition, we allow batching of user requests, and the effect of such batching is captured in a batching model. Our proposed queueing model integrates both the user activity and the batching model. This model can be used to determine the requirements of network bandwidth and video server and, hence, the trade-off in communication and storage costs for different system resource configurations.

A queueing model is developed for the database system which supports mobility management in personal communication systems (PCS). The end-to-end service delay is defined as the performance metric. The accuracy of the analytical model is validated by simulation. It is found that the analytical results show a close agreement to those from simulation over a significant range of system parameters. Three database system architectures proposed for PCS are studied, namely, the flat database system in GSM, the two-level hierarchical architecture, and the three-level hierarchical architecture. Based on the queueing model, the delay performance of these three architectures are compared. It is observed that the hierarchical architecture provides the best system performance and supports the highest user density. This is because the service arrival rate to the higher level large database is significantly reduced, due to the localized nature of calls and users in PCS.

Personal communication systems (PCS) represent a rapidly growing and increasingly important segment of the telecommunication industry. The goal of PCS is to provide truly personal, cost-efficient communication services to users through portable handsets. In this paper, we present a survey on the research and development in PCS, emphasizing several important aspects such as the PCS concept, service requirements, system architecture, operation, and management. Some ongoing field trials are described as well. We focus on the wireless and the mobility-related features of PCS, discuss their impact on the system design and performance, and provide an overview of different technology choices.>

In wavelength-division multiplexed wide-area optical networks, erbium-doped fiber amplifiers (EDFAs) are usually employed to boost lightwave power. However, EDFAs can only cover 35 nm of the 200 nm fiber bandwidth at 1.55 /spl mu/m, and therefore messages transmitted on the remaining fiber bandwidth cannot be amplified. The authors propose to use wavelengths outside the EDFA bandwidth for sending messages over short distances in which amplification is not necessary. Routing determines which wavelength and links a message is routed on, and hence whether or not a message needs amplification. The authors design static and dynamic routing algorithms in circuit-switched networks and analyze the performance using simulation. The results show that use of wavelengths outside the EDFA bandwidth can decrease blocking and increase the network capacity.>

Rerouting for a circuit-switched wavelength-division-multiplexed all-optical network is considered in the paper. Due to the wavelength continuity constraint, a new connection may be blocked even if bandwidth is available between the origin and the destination. Rerouting can make the available bandwidth wavelength-continuous by changing the routes of certain existing connections to accommodate the new connection. To avoid disruptions of existing connections, move-to-vacant wavelength-retuning (MTV WR) is proposed as the basic operation of circuit migration, in which a circuit is moved to a vacant wavelength on the same path, and the parallel MTV WR rerouting scheme is considered to reroute multiple circuits on disjoint sets of links. The authors design the optimal algorithm which minimizes the weighted number of rerouted circuits with the parallel MTV WR rerouting scheme. Numerical results using simulation show that rerouting can effectively reduce the blocking probability due to the wavelength continuity constraint while minimizing the incurred disruptions.>

The future telecommunication networks are expected to support a wide variety of multimedia services with very different bit-rate and performance requirements. Under these circumstances, it has been recognized that the conventional simple source modeling, namely, the Poisson arrival process, is no longer adequate to describe various kinds of traffic sources accurately. Other source modelings, which give more accurate results but greatly complicate the performance analyses, have been proposed. However, all these models share a common property, that is, they can be decomposed into a superposition of independent identical interrupted Poisson processes (IPP). In order to obtain a balance between the accuracy and the complexity of analysis, the authors propose to approximate an IPP, a basic component of various models, by a Poisson distribution and use the Chen-Stein (1975, 1972) method to find an upper bound of this approximation error.>

A multilevel priority scheme for fiber-optic CDMA is proposed. Users are divided into groups with different transmission power levels. Since the inherent properties and signal processing of the conventional communication channels are different from those of the fiber-optic channels, new code sequences must be constructed for fiber-optic applications. Furthermore, fiber-optic systems can be modeled as positive systems. Therefore, the packets from higher power groups can transmit successfully with higher probability than those from lower power groups. This implies that packets with higher power levels have higher priority than those packets with lower power levels. The goal of this research is to analyze the performance of fiber-optic CDMA packet networks using code sequences with given orthogonality properties.>

A wavelength-convertible switch architecture and routing algorithm for circuit-switched wavelength-division-multiplexing optical networks is studied. Wavelength converters are used to resolve wavelength conflicts and to reuse wavelengths. These converters are not dedicated to individual channels, but are shared by the channels of a node or those of an outbound link in the share-per-node or the share-per-link wavelength-convertible switch, respectively. A routing algorithm is developed to converse wavelength converters while maintaining performance close to that of a network with abundant converters. It is found that converters can improve the network performance, such as the blocking probability and fairness, considerably.>

The issues involved in developing a distributed database system (DDBS) in a high-speed environment are discussed. The inadequacy of existing database protocols in utilizing the gigabit network is described. A concurrency control protocol that performs better than traditional DDBSs in high-speed networks is developed. Both analytical and simulation results are presented. The focus is on the concurrency control aspect of DDBS since this protocol is at the heart of the overall functioning of the distributed system.>

Regular two-dimensional architectures are being considered as alternatives to the linear topology metropolitan area networks (MANs) that are popular today. Deflection routing is an adaptive routing strategy that performs well on such architectures. A general analytic model has been developed to study the performance of buffered deflection routing in regular networks. The Manhattan street network, the ShuffleNet, and the shuffle exchange network have been studied as candidate two-connected networks with different topological characteristics. The results show that deflection routing performs well on both the Manhattan street network and the ShuffleNet, even under heavy loads, while on the shuffle exchange network it does not perform as well. The introduction of just a few buffers provides significant improvement in the delay-throughput performance over unbuffered deflection routing, especially in networks with large propagation delays. The analytic results are found to match the simulations very closely in most cases.>

The authors derive an upper bound of the minimum time division multiple access (TDMA) frame length of any collision-free node assignment protocol in a packet radio network in which a node has multiple reception capacity. They also derive the optimum TDMA frame length for any fully connected network with large reception capacity. When the total number of nodes in the network is unknown, a heuristics to generate a TDMA protocol with frame length within some upper bound is presented for any network with large reception capacity.>

The analysis of the data accessing mechanism is of importance to the analytical performance evaluation of any data processing system. So far, most such analyses have been done under the assumption of a uniform data access model. This is not true in the real world and some attempts at modeling nonuniform data access have been made. The authors develop a new, improved model, which is believed to be capable of describing the real-world scenario fairly accurately. They also develop the general formula and properties of an important performance parameter, namely, the probability of conflict.>

A novel semijoin execution strategy is proposed which allows parallelism and processes multiple semijoins simultaneously. In practice most of the parameters needed for query optimization, such as relation cardinality and selectivity, are of fixed-precision. Imposing this fixed-precision constraint, an efficient distributed query processing algorithm is developed. For situations where the fixed-precision constraint does not apply, a method to truncate the parameters and to use the same algorithm to find near-optimal solutions is proposed. By analyzing the truncation errors, a quantitative comparison between the near-optimal solutions and the optimal ones is provided.>

The issues of fairness are considered in designing time division multiple access (TDMA) channel access protocols for multihop radio networks. It is shown that there is a limitation as to how fair one can design a channel access protocol for a static multihop radio network. Several fairness measures which are functions of the channel access protocol and the network topology are proposed. It is shown that to find the optimal protocol with respect to any defined fairness measure is NP-hard. Criteria for designing a fair protocol which are independent of the network topology are introduced and their properties are proved. A lower upper bound of one of the measures is found. Two heuristic protocols are developed based on these criteria. Performance comparisons with existing protocols are given.>

The delays analysis of multihop packet radio networks using busy-tone type protocols is presented. An interrupted link queue model is proposed to resolve the difficulties of dependency and interference between different users and an embedded Markov chain for the queue is formulated. The steady state behavior of the system is studied and the delay-throughput performance is given. Numerical results are compared for the network performance under receiver-initiated busy-tone multiple access (RI-BTMA) and conservative BTMA (C-BTMA). It is found that RI-BTMA performs better because of better utilization of the spatial reuse property of multihop packet radio networks.>

In replicated database systems, a replication control protocol is needed to ensure one-copy serializability. The author incorporates the concept of a regeneration into the missing-partition dynamic voting scheme to design a replication control protocol. Like the original missing-partition dynamic voting scheme, this protocol supports an inexpensive read operation which accesses one copy, rather than all copies, of each data item read. By incorporating the concept of regeneration and keeping multiple versions for each data item in the database, higher data availability is maintained. To support data regeneration, a replicated directory architecture for the proposed replication control protocol is designed, and it not only supports regeneration of replicated data items, but also provides inexpensive, high-availability directory services, which help maintain database availability.>

A distributed deadlock detection/resolution algorithm is proposed. In this algorithm, when a deadlock cycle is detected, it is resolved by reordering the wait-for relations between pairs of transactions. Therefore, no transaction abortions are necessary to resolve deadlock cycles. This results in fewer messages and smaller transaction response time. The correctness of this abortion-free algorithm is proved. The abortion-free algorithm can be extended to handle read/write lock requests and to distinguish between transaction classes.>

Two local access algorithms are presented for a hierarchical mobile packet radio network where each user transmits with a fixed or an adjustable transmission radius, respectively. A model is developed for analyzing the two access schemes, and it is shown that the network can achieve better performance if each node uses an adjustable transmission radius. Previous research assumed a static two-dimensional Poisson model to describe the distribution of users and cannot fully characterize the effect of user mobility. The proposed model accounts for this effect. Numerical examples are presented.>

An improved reliability approximation method is presented which reduces the number of states to be considered by exploiting the path structure of the network. The method does not impose restriction on the reliability criterion; criteria more general than those based on connectivity can be used. The reduction of the number of states is usually substantial, sometimes dramatic. The approach is applicable for all communication networks. Furthermore, very general reliability criteria can be used.>

The capacity of a distributed, self-organizing, mobile, multihop broadcast packet-radio network using virtual circuit switching and time division multiple access policies is studied. The study develops a tool which provides for the optimization of network capacity by trading off among the network area, the transmission range, and the number of packet-radio units. Since these results are not in closed form, numerical results provide further insight into these parameters.>

The performance analysis of unslotted spread-spectrum packet radio network is very difficult because the received signal-to-noise ratio (SNR) fluctuates during the packet transmission. Past analyses are either based on complete enumeration or restricted to performance bounds. Here, a technique based on ballot theory is developed to analyze the performance of unslotted ALOHA spread-spectrum packet radio networks. This technique is also used to analyze the channel load sensing access protocol. An L-channel model is assumed.>

A queueing model is used to approximate static locking in distributed database systems without deadlocks. Then a random graph model to find the deadlock probability of each transaction is proposed. Finally, the above two models are integrated, so that given the transaction arrival rate, the response time and the effective throughput can be calculated.>

A replication control protocol utilizing dynamic voting is presented for ensuring database correctness so that the system behaves like a one-copy database to the users. The protocol dynamically adjusts vote assignment of data items in response to failures and recoveries, thus maintaining higher data availability than static voting schemes in the event of network partitioning. Unlike existing dynamic voting schemes, it supports inexpensive read operations which access one copy, rather than all copies, of each data item read. Since read operations outnumber write operations in most applications, this protocol enjoys better performance. With this protocol, transactions run in one of three modes: normal mode, missing-partition mode, or pseudo-normal mode. Because a partition number and a last current copy cardinality are associated with each copy, read operations only require one copy of a data item when run in the normal mode.>

A model is proposed for analyzing the performance of a mobile packet radio network. In this network, a node is allowed to move around with a random velocity. Hence, the distribution of the number of nodes in one's transmission circle is dependent on the mobility of the nodes. A queuing model is developed to evaluate this distribution and the effects of node mobility on system performance. This effect cannot be obtained by classical two-dimensional Poisson model. It is found that an optimal power radius is dependent on the node mobility.>

A model is presented for the reliability and performance analysis of systems where components can go through degraded states in a statistically dependent manner. The model, called the cause-based multimode model (CBMM), is based on the idea that deviations of components from the 'up' state have underlying physical causes which can be explicitly identified and are statistically independent. The effects of several causes can be combined in a flexible manner. System reliability/performance measures can be computed by an approximation method, based on the consideration of the most probable states. Such states can be efficiently generated by using algorithms developed for an earlier multimode, independent-failure model by S.N. Chiou and V.O.K. Li (see IEEE J. Selected Areas in Commun., vol.SAC-4, no.7, p.1156-61 (1986)).>

A multiple-access protocol for local area networks is described. It is basically a hybrid of carrier-sense multiple access with collision detection (CSMA/CD) and the broadcast recognizing access method (BRAM). CSMA/CD, which is contention-based, works well under light traffic, but message collisions degrade system performance when the channel becomes heavily loaded. BRAM, which is collision-free, has no longer delays at low load, but its efficiency improves as the load increases. Performance models are developed for the hybrid protocol and for the Ethernet protocol, a proven commercial implementation of CSMA/CD-type protocols. It is found that the hybrid protocol gives better performance for a wide range of scenarios.>

A multibeam satellite communications network serving multiple zones with S-ALOHA random access uplinks and dynamically switched transponders in the downlinks is studied. The overhead of switching transponders between zones may degrade the performance of the system significantly. Two different strategies are introduced and studied. In the guard time strategy, each slot time is equal to the packet transmission time plus the transponder switching time, allowing the transponder to be pointed to a new zone at the beginning of each slot. In the idle waiting strategy, each slot time is equal to the packet transmission time. If a transponder is switched to a new zone, it will take k slot time where k is the smallest integer greater than the switching time divided by the slot time. The throughputs of these two strategies are analyzed and compared.>

The problem of optimizing joins between two fragmented relations on a broadcast local network is analyzed. Data redundancy is considered. Semantic information associated with fragments are used to eliminate necessary processing. More than one physical copies of a fragment is allowed to be used in a strategy to achieve more parallelism. Join-analysis graphs are introduced to represent joins on two fragmented relations. The problem of optimizing a join is mapped into an equivalent problem of finding a minimum-weight vertex cover for the corresponding join-analysis graph. This problem is proved to be NP-hard. A four-phase approach for processing joins is proposed.>

A quorum-based commit and termination protocol is designed with the goal of maintaining high data availability in case of failures. The protocol proposed is resilient to arbitrary concurrent site failures, lost messages, and network partitioning. The major difference between this protocol and existing ones is that the voting partition processing strategy is taken into consideration in the design. As a result, the protocol is expected to maintain higher data availability.>

The authors present a unified concurrency control algorithm for distributed database systems in which each transaction may choose its own concurrency control protocol. Specifically, they integrate two-phase locking, timestamp ordering, and precedence agreement into one unified concurrency control scheme. They show the correctness of the scheme and study the problem of selecting the best protocol for each transaction to optimize system performance.>

The authors consider a static routing problem in a network with failure-prone links. Two copies of each externally generated message are sent from the source to the destination along two disjoint paths with the objective of reducing the delay resulting from retransmissions of unsuccessful packets. They formulate an optimal-routing problem using a suitable delay function. This results in a nonlinear programming problem of minimizing the delay over routing assignment under certain constraints. Specifically, they impose a disjoint-path constraint on the route assignment. This nonlinear program is solved by an iteration method incorporating a combinatorial algorithm. The solution converges to the global minimum for a convex objective function over a convex feasible region.>

A multibeam satellite communications network serving multiple zones with S-Aloha random-access uplinks and dynamically switched transponders in the downlinks is studied. The overhead of switching transponders between zones may degrade the performance of the system significantly. Two different strategies are introduced and studied. In the Guard Time strategy, each slot time is equal to the packet transmission time plus the transponder switching time, allowing the transponder to be pointed to a new zone at the beginning of each slot. In the Idle Waiting strategy, each slot time is equal to the packet transmission time. If a transponder is switched to a new zone, it will take k slot time, where k is the smallest integer greater than the switching time divided by the slot time. The throughputs of these two strategies are analyzed and compared.>

Resilient commit protocols for multisite simple network partitioning are studied in this paper. The necessity of termination protocols to make commit protocols resilient in multisite simple network partitioning is presented. A termination protocol that makes the three-phase commit protocol resilient is designed. This protocol is valid even for transient network partitioning. The method can be generalized to design termination protocols for other commit protocols in multisite simple network partitioning.

We have developed a unified model, called the precedence-assignment model (PAM), of concurrency control algorithms in distributed database. It is shown that two-phase locking timestamp-ordering and other existing concurrency control algorithms may be modeled by PAM. We have also developed a new concurrency control algorithm under the PAM modeling framework, which is free from deadlocks and transaction restarts. Finally, a unified concurrency control subsystem for precedence-assignment algorithms is developed. By using this subsystem, different transactions may be executed under different concurrency control algorithms simultaneously.

An overview is given of communications networks in which multiple terminals share the same channel in their attempt to communicate. The author briefly surveys the following multiaccess schemes and protocols: the ALOHA protocol, splitting algorithms, carrier-sense multiaccess (CSMA), time-division multiaccess (TDMA), frequency-division multiacess (FDMA), and reservation-based protocols. Protocols used in satellite networks, local area networks, and packet radio networks are briefly reviewed.

This paper describes and analyzes a pipeline protocol for the data message communications of MSAT-X, a proposed experimental satellite-based mobile communications network. A demand-assigned multiple access protocol using pure ALOHA for making reservation requests has been developed for MSAT-X under error-free assumptions. Preliminary propagation studies indicate that the shortterm bit error rate of satellite channels in a mobile environment can be as high as 10-3. Therefore, error-control schemes must be developed to ensure reliable transmissions. In this paper, we propose a retransmission scheme using selective repeat to minimize the end-to-end delay. We also use slotted ALOHA for making reservation requests to increase the overall system throughput. Since the number of channels available for reservation and data channels is essentially fixed for a given voice call blocking probability and a fixed call arrival rate, the analysis presented in this paper is also applicable to the integrated voice and data services of MSAT-X. Various operational scenarios have been investigated.

A distributed database (DDB) consists of copies of data files (usually redundant) geographically distributed and managed on a computer network. One important problem in DDB research is that of concurrency control. This paper develops a performance model of timestamp-ordering concurrency control algorithms in a DDB. The performance model consists of five components: input data collection, transaction processing model, communication subnetwork model, conflict model, and performance measures estimation. In this paper we describe the conflict model in detail. We first determine the probability of transaction restarts, the probability of transaction blocking, and the delay due to blocking for the basic timestamp-ordering algorithm. We then develop conflict models for variations of the basic algorithm. These conflict models are illustrated by numerical examples.

In a distributed database system, query processing involves considerable amount of data transmission among different computer sites. Since communication delay is substantial, minimizing inter-site data transmissions becomes an important issue. In this paper, we propose an abstract relation-partitioning approach to the distributed query processing problem. This approach transforms a query processing problem into a pseudo query processing problem, solves the query processing problem in the pseudo space, and then transforms the solution back to the original solution space. We then apply this method to derive optimal algorithms for star queries.

This paper presents a model to calculate the reliability of communication networks with multimode components. Previous research on network reliability has focused on models in which each component may be in one of two modes, namely, operative or failed. In reality, a component may undergo degradations in performance before a complete outage, and will therefore operate in more than two modes. Traditional network reliability measures, such as the probability that a pair of nodes is connected, are not meaningful in a multimode model. Therefore, the mean message delay of the network is defined as the performance measure. An exact calculation of this reliability measure is not feasible due to the large number of network states, corresponding to network components being in different modes. We have developed an approximation method to calculate this reliability measure. This method requires us to work with the states of the network in order of decreasing probability. An algorithm ORDER-Mis developed to generate these states in the proper order.

This paper presents a new model to study the reliability of communication networks in which link failures are statistically dependent. The approach tries to identify and model explicitly the events that cause communication link failures. No conditional probabilities are needed, and so two major difficulties inherent to them, namely, an exponential number of conditional probabilities to deal with and a consistency requirement to satisfy, are avoided. For reliability computations, some existing algorithms for finding network reliability can be used with minor modifications and no significant increase in computational complexity.

A new approach for analyzing the performance of communication networks with unreliable components was given in a recent paper [2]. An algorithm was developed to generate the most probable states of a network, and an analysis of those states gave a good approximation of the network performance. In this paper, we present a new algorithm for generating the most probable states. This new algorithm is a major improvement over the previous one in terms of efficiency and flexibility.

The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. Semijoin tactics are applied for query processing. An execution graph is introduced to represent the semijoin programs associated with the distributed processing of the queries. We then identify optimality properties of semijoin programs for star queries, and use these properties to derive the optimal semijoin program. We have shown that the optimal semijoin program can be found from serial semijoin strategies, defined as serial semijoin programs which include each semijoin associated with the query exactly once. By making certain assumptions on the file sizes and the semijoin selectivities, we can obtain the optimal semijoin program from these strategies in polynomial time. Our assumption on selectivites is consistent in the sense that we consider the selectivity of a semijoin based on the current database state, i.e., we take into consideration the reduction effects of all prior semijoins.

This paper describes a feasibility study of the adaptive mobile access protocol (AMAP) for MSAT-X, a proposed experimental mobile satellite communication network. The mobiles are dispersed over a wide geographical area and the channel data rate is limited due to the size and cost limitations of mobile antennas. AMAP is a reservation based multiple-access scheme. The available bandwidth is divided into subchannels, which are divided into reservation and message channels. The ALOHA multiple-access scheme is employed in the reservation channels, while the message channels are demand assigned. AMAP adaptively reallocates the reservation and message channels to optimize system performance. It has been shown that if messages are generated at a rate of one message per hour, AMAP can support approximately 2000 active users per 2400 bit/s channel with an average delay of 1.4 s.

The problem of optimal query processing in distributed database systems was shown to be NP-hard. This means that heuristic algorithms are necessary to solve the query processing problem. In this paper, we describe algorithms to improve the solutions generated by heuristics. We have identified four properties which optimal semijoin programs for processing tree queries have to satisfy. A semijoin program is represented by an execution graph which specifies the order and the identities of the semijoins to be executed. Given a semijoin program, we can therefore apply these properties to check its optimality. If it does not satisfy these optimality properties, the associated improvement algorithms can be applied to improve this program. No assumptions have been made about the relation size and the selectivity of the semijoins.

In evaluating the performance of a communication network with unreliable components, researchers have traditionally approached the problem by enumerating all possible states of the system. Since the number of states of a communication network withnfailure-prone components is 2nthese methods are restricted to small systems. We present a new solution technique that is not doomed by the "statespace explosion" problem. Instead of enumerating all possible fail states, we consider only the most probable states. Since the network operates in these states most of the time, we can get upper and lower bounds and, hence, a good approximation of the network performance without having to analyze all possible states. We illustrate our solution technique by analyzing network reliability, the expected number of communicating pairs, and network average delay for some particular networks.

In a recent paper, a generalization of the slotted ALOHA random access scheme is considered in which a user transmits multiple copies of the same packet. In frequency diversity ALOHA, multiple copies of the same packet are simultaneously transmitted on different channels. We found the analysis for one of the proposed schemes, namely, channel selection without replacement, to be incorrect. These comments contain a counterexample to the published results and a corrected version of the analysis.

Abstract Given a set of origin‐destination points in the plane and a set of polygonal barriers to travel, this paper develops an efficient algorithm for finding minimal distance feasible paths between the points, assuming that all travel occurs according to the rectilinear distance metric. By geometrical arguments the problem is reduced to a finite network problem. The nodes are the origin‐destination points and the barrier vertices. The links designate those node pairs that “communicate” in a simple way, where communication implies the existence of a node‐to‐node rectilinear path that is not made longer by the barriers. The weight of each link is the rectilinear distance between its two corresponding nodes. Solution of the minimal distance path problem on the network procedes in two steps. First, for a given origin or root node, a tree is generated containing a minimal distance path to each node that communicates with the root node. Second, a modified Dijkstra‐type iteration is utilized, starting with the nodes of the tree, sequentially adding nodes according to minimum “penalty distance,” where the penalty is the extra travel distance caused by the barriers. The paper concludes with a discussion of the computational complexity of the procedure, followed by a numerical example.