Existing text-to-image (T2I) diffusion models face several limitations, including large model sizes, slow runtime, and low-quality generation on mobile devices. This paper aims to address all of these challenges by developing an extremely small and fast T2I model that generates high-resolution and high-quality images on mobile platforms. We propose several techniques to achieve this goal. First, we systematically examine the design choices of the network architecture to reduce model parameters and latency, while ensuring high-quality generation. Second, to further improve generation quality, we employ cross-architecture knowledge distillation from a much larger model, using a multi-level approach to guide the training of our model from scratch. Third, we enable a few-step generation by integrating adversarial guidance with knowledge distillation. For the first time, our model SnapGen, demonstrates the generation of 10242px images on a mobile device around 1.4 seconds. On ImageNet-1K, our model, with only 372M parameters, achieves an FID of 2.06 for 2562px generation. On T2I benchmarks (i.e., GenEval and DPG-Bench), our model with merely 379M parameters, surpasses large-scale models with billions of parameters at a significantly smaller size (e.g., 7× smaller than SDXL, 14× smaller than IF-XL).

Semi-implicit distributions have shown great promise in variational inference and generative modeling. Hierarchical semi-implicit models, which stack multiple semi-implicit layers, enhance the expressiveness of semi-implicit distributions and can be used to accelerate diffusion models given pretrained score networks. However, their sequential training often suffers from slow convergence. In this paper, we introduce CoSIM, a continuous semi-implicit model that extends hierarchical semi-implicit models into a continuous framework. By incorporating a continuous transition kernel, CoSIM enables efficient, simulation-free training. Furthermore, we show that CoSIM achieves consistency with a carefully designed transition kernel, offering a novel approach for multistep distillation of generative models at the distributional level. Extensive experiments on image generation demonstrate that CoSIM performs on par or better than existing diffusion model acceleration methods, achieving superior performance on FD-DINOv2.

Irregular multivariate time series (IMTS) is characterized by the lack of synchronized observations across its different channels.In this paper, we point out that this channel-wise asynchrony can lead to poor channel-wise modeling of existing deep learning methods.To overcome this limitation, we propose MTM, a multi-scale token mixing transformer for the classification of IMTS.We find that the channel-wise asynchrony can be alleviated by down-sampling the time series to coarser timescales, and propose to incorporate a masked concat pooling in MTM that gradually down-samples IMTS to enhance the channel-wise attention modules.Meanwhile, we propose a novel channel-wise token mixing mechanism which proactively chooses important tokens from one channel and mixes them with other channels, to further boost the channel-wise learning of our model.Through extensive experiments on real-world datasets and comparison with state-of-the-art methods, we demonstrate that MTM consistently achieves the best performance on all the benchmarks, with improvements of up to 3.8% in AUPRC for classification.

The delivery of goods to numerous indoor stores poses significant safety risks, with heavy, high-stacked packages on delivery trolleys posing a potential hazard to passersby. This paper reports our experiences of developing and operating DeMo, a practical system for real-time monitoring of indoor delivery. DeMo employs sensors attached to trolleys, utilizing Inertial Measurement Unit (IMU) and Bluetooth Low Energy (BLE) readings to detect delivery violations, such as speeding and the use of non-designated delivery paths, and ensure accurate matching of each delivery to its intended destination store. Unlike typical indoor localization applications, DeMo addresses unique challenges, including sensor placement and the complex electromagnetic characteristics encountered in underground settings. Specifically, DeMo adapts the classical logarithmic radio signal model to facilitate fingerprint-free localization, significantly reducing deployment and maintenance costs. DeMo has been operating since May 2020, covering more than 200 shops with 74,537 deliveries (6193.2 km) across 12 subway stations in Hong Kong. DeMo's 4-year operation witnessed a significant violation rate drop, from 19% (May 2020) to 0.9% (Mar 2024).

Knowing a pedestrian'sconveyor stateof “elevator,” “escalator,” or “neither” is fundamental to many applications such as indoor navigation and people flow management. Previous studies on classifying the conveyor state often rely on specially designed body-worn sensors or make strong assumptions on pedestrian behaviors, which greatly strangles their deployability. To overcome this, we study the classification problem under arbitrary pedestrian behaviors using the inertial navigation system (INS) of the commonly available smartphones (including accelerometer, gyroscope, and magnetometer). This problem is challenging, because the INS signals of the conveyor states are entangled by the arbitrary and diverse pedestrian behaviors. We propose ELESON, a novel and lightweight deep-learning approach that uses phone INS to classify a pedestrian toelevator,escalator,orneither. Using causal decomposition and adversarial learning, ELESON extracts the motion and magnetic features of conveyor state independent of pedestrian behavior, based on which it estimates the state confidence by means of an evidential classifier. We curate a large and diverse dataset with 36,420 instances of pedestrians randomly taking elevators and escalators under arbitrary unknown behaviors. Our extensive experiments show that ELESON is robust against pedestrian behavior, achieving a high accuracy of over 0.9 in F1 score, strong confidence discriminability of 0.81 in AUROC (Area Under the Receiver Operating Characteristics), and low computational and memory requirements fit for common smartphone deployment.

Due to its promising results, density map regression has been widely employed for image-based crowd counting. The approach, however, often suffers from severe performance degradation when tested on data from unseen scenarios, the so-called “domain shift” problem. To address the problem, we investigate in this work single domain generalization (SDG) for crowd counting. The existing SDG approaches are mainly for image classification and segmentation, and can hardly be extended to our case due to its regression nature and label ambiguity (i.e., ambiguous pixel-level ground truths). We propose MPCount, a novel effective SDG approach even for narrow source distribution. MPCount stores diverse density values for density map regression and reconstructs domain-invariant features by means of only one memory bank, a content error mask and attention consistency loss. By partitioning the image into grids, it employs patch-wise classification as an auxiliary task to mitigate label ambiguity. Through extensive experiments on different datasets, MPCount is shown to significantly improve counting accuracy compared to the state of the art under diverse scenarios unobserved in the training data characterized by narrow source distribution. Code is availablex at https://github.com/Shimmer93/MPCount.

Unsupervised domain adaptation (UDA) seeks to bridge the domain gap between the target and source using unlabeled target data. Source-free UDA removes the requirement for labeled source data at the target to preserve data privacy and storage. However, previous works on source-free UDA assume knowledge of domain gap, and hence is limited to either target-aware or classification task. To overcome it, we propose TASFAR, a novel target-agnostic source-free domain adaptation approach for regression tasks. Using prediction confidence, TASFAR estimates a label density map as the target label distribution, which is then used to calibrate the source model on the target domain. We have conducted extensive experiments on four regression tasks with various domain gaps, namely, pedestrian dead reckoning for different users, image-based people counting in different scenes, housing-price prediction at different districts, and taxi-trip duration prediction from different departure points. TASFAR demonstrates significant superiority over state-of-the-art source-free UDA approaches, achieving an average error reduction of 22 % across the four tasks and comparable accuracy to source-based UDA, all without relying on source data.

People with Dementia (PwD) suffer from a high risk of getting lost due to their cognitive deterioration, leading to potential safety hazards and significant search efforts. In this paper, we propose DEmentia Caring System (DECS), an effective crowdsourcing platform to search for missing PwD. Specifically, PwD carry our customized Bluetooth Low Energy (BLE) tags that broadcast BLE packets, which are detected and then uploaded by mobile volunteers via their smartphones. To further enhance search efficiency, DECS deploys BLE gateways as its infrastructure and analyzes PwD's daily spatial-temporal mobility patterns. DECS has been deployed in Hong Kong since 2019, supporting 3,100+ PwD's families with over 45,000 app downloads by volunteers. More importantly, it has successfully served the search for 254 missing cases. This paper reports the unique lessons and experiences learned through our 4-year citywide deployment of DECS.

We study the challenging problem of navigating in an indoor carpark in the absence of global navigation satellite system (GNSS) and cellular signals using an offline smartphone docked at the car dashboard. There is basic radio frequency (RF) infrastructure in the venue but, due to signal attenuation by the car body, the location computed based on the in-car signal is noisy and intermittent. Previous works on carpark navigation often require costly specialized equipment as on-car additional infrastructure (OCAI), or suffer from error propagation stemmed from integrating inertial measurement unit (IMU) signals over time. We propose RICH, a novel, simple, accurate, and cost-effective docked-phone approach to fuse RF and IMU signals for indoor carpark navigation using the hidden Markov model (HMM). RICH uses IMU signals to detect the speed level and turning of the car, which is then fused with the crude RF localization in an HMM framework to estimate the car’s location distribution in real-time. We further present an analysis on the tradeoff between computation and accuracy of RICH. Our extensive experiments on smartphone in real carparks show that, as compared with the state-of-the-art, RICH achieves substantially lower localization error (by 40%) with high-computational efficiency (less than 10 ms per location).

Time series data, including univariate and multivariate ones, are characterized by unique composition and complex multi-scale temporal variations. They often require special consideration of decomposition and multi-scale modeling to analyze. Existing deep learning methods on this best fit to univariate time series only, and have not sufficiently considered sub-series modeling and decomposition completeness. To address these challenges, we propose MSD-Mixer, a M ulti- S cale D ecomposition MLP- Mixer , which learns to explicitly decompose and represent the input time series in its different layers. To handle the multi-scale temporal patterns and multivariate dependencies, we propose a novel temporal patching approach to model the time series as multi-scale patches, and employ MLPs to capture intra- and inter-patch variations and channel-wise correlations. In addition, we propose a novel loss function to constrain both the mean and the autocorrelation of the decomposition residual for better decomposition completeness. Through extensive experiments on various real-world datasets for five common time series analysis tasks, we demonstrate that MSD-Mixer consistently and significantly outperforms other state-of-the-art algorithms with better efficiency.

Existing crowdsourced indoor positioning systems (CIPSs) usually require prior knowledge about the site and a tedious calibration process. Moreover, they may require a large number of landmarks while ignoring the topology information that may be contained in the crowdsourced data. In this paper, we present Leto, a system that useslearnedtopology information from combined user traces to construct a radio map. Leto relies on crowdsourced WiFi and accelerometer signals only without requiring any prior knowledge about the site. Our key idea is that learned topology information can reduce the required number of landmarks, while available landmarks can transform the topology into a map. We propose a novel framework that efficiently learns the map topology by a hybrid multidimensional scaling (HMDS) algorithm and accurately rectifies the map using only a few anchors by an adaptive force-directed (AFD) algorithm. We also provide a theoretical convergence analysis of the HMDS algorithm. Experimental results on real-world datasets show that Leto can capture useful topology information and achieve significant improvements in radio map construction compared to existing systems.

A user's movement path can be precisely and concisely described as a concatenation of straight lines having the user's turns as their end points. Learning such a path description or representation from inertial measurement unit (IMU) sensors enables various mobile and IoT applications, as it allows efficient processing of the movement path data. It is, however, non-trivial to learn a succinct yet accurate path description from IMU sensor readings in the mobile device of a moving useron the flydue to the dynamically changing behaviors and the technical difficulty in detecting the user's turns. We propose PATHLIT, a novel online path description learning system based on IMU signals. PATHLIT learns position vectors of a user from IMU sensor readings by our custom-made self-attention network model. Once each position vector is learned, PATHLIT also decides whether or not to take it as a part of the resulting path description by our efficient online algorithm developed under the minimum description length principle, which essentially detects the user's turns along the path. We conduct extensive experiments on two large datasets. The experiment results show that PATHLIT achieves superior performance over state-of-the-art algorithms by up to 50% in absolute trajectory error using only 15% of trajectory data points.

To design fast neural networks, many works have been focusing on reducing the number of floating-point operations (FLOPs). We observe that such reduction in FLOPs, however, does not necessarily lead to a similar level of re-duction in latency. This mainly stems from inefficiently low floating-point operations per second (FLOPS). To achieve faster networks, we revisit popular operators and demonstrate that such low FLOPS is mainly due to frequent memory access of the operators, especially the depthwise con-volution. We hence propose a novel partial convolution (PConv) that extracts spatial features more efficiently, by cutting down redundant computation and memory access simultaneously. Building upon our PConv, we further propose FasterNet, a new family of neural networks, which attains substantially higher running speed than others on a wide range of devices, without compromising on accuracy for various vision tasks. For example, on ImageNet-lk, our tiny FasterNet-TO is 2.8×, 3.3×, and 2.4× faster than MobileViT-XXS on GPU, CPU, and ARM processors, respectively, while being 2.9% more accurate. Our large FasterNet-L achieves impressive 83.5% top-1 accuracy, on par with the emerging Swin-B, while having 36% higher inference throughput on GPU, as well as saving 37% compute time on CPU. Code is available at https://github.com/JierunChen/FasterNet.

Floor labels of crowdsourced RF signals are crucial for many smart-city applications, such as multi-floor indoor localization, geofencing, and robot surveillance. To build a prediction model to identify the floor number of a new RF signal upon its measurement, conventional approaches using the crowdsourced RF signals assume that at least few labeled signal samples are available on each floor. In this work, we push the envelope further and demonstrate that it is technically feasible to enable such floor identification with only one floor-labeled signal sample on the bottom floor while having the rest of signal samples unlabeled. We propose FIS-ONE, a novel floor identification system with only one labeled sample. FIS-ONE consists of two steps, namely signal clustering and cluster indexing. We first build a bipartite graph to model the RF signal samples and obtain a latent representation of each node (each signal sample) using our attention-based graph neural network model so that the RF signal samples can be clustered more accurately. Then, we tackle the problem of indexing the clusters with proper floor labels, by leveraging the observation that signals from an access point can be detected on different floors, i.e., signal spillover. Specifically, we formulate a cluster indexing problem as a combinatorial optimization problem and show that it is equivalent to solving a traveling salesman problem, whose (near-)optimal solution can be found efficiently. We have implemented FIS-ONE and validated its effectiveness on the Microsoft dataset and in three large shopping malls. Our results show that FIS- ONE outperforms other baseline algorithms significantly, with up to 23 % improvement in adjusted rand index and 25% improvement in normalized mutual information using only one floor-labeled signal sample.

In applications such as elderly care, dementia anti-wandering and pandemic control, it is important to ensure that people are within a predefined area for their safety and well-being. We propose GEM, a practical, semi-supervised Geofencing system with network EMbedding, which is based only on ambient radio frequency (RF) signals. GEM models measured RF signal records as a weighted bipartite graph. With access points on one side and signal records on the other, it is able to precisely capture the relationships between signal records. GEM then learns node embeddings from the graph via a novel bipartite network embedding algorithm called BiSAGE, based on a Bipartite graph neural network with a novel bi-level SAmple and aggreGatE mechanism and non-uniform neighborhood sampling. Using the learned embeddings, GEM finally builds a one-class classification model via an enhanced histogram-based algorithm for in-out detection, i.e., to detect whether the user is inside the area or not. This model also keeps on improving with newly collected signal records. We demonstrate through extensive experiments in diverse environments that GEM shows state-of-the-art performance with up to 34% improvement in F-score. BiSAGE in GEM leads to a 54% improvement in F-score, as compared to the one without BiSAGE.

We consider pervasive localization for a roaming user who may sample widely varying signal modes (GPS, WiFi, geomagnetism, Bluetooth low energy, etc.) and values over time and space. Previous works can only apply to specific (two or three) modes and environment, and cannot accommodate arbitrary signal modes and environmental changes due to signal noise, device heterogeneity, phone carriage states, etc. We propose SiFu, a simple, accurate, and generic multimodal signal fusion platform robust against environmental deviation from its design point. As a generic framework, SiFu treats a single-modal localization algorithm as a black box to embrace any existing, emerging or future signals with only incremental training. It employs Bayesian deep learning and data augmentation to mitigate the location bias of the single-modal localization algorithm and run-time deviation from the training data, respectively. Using a unified multimodal likelihood formulation and particle filter, it fuses with inertial sensor measurements for localization. We conduct extensive experiments in different venues (campus, mall, and subway station), and show that SiFu achieves significantly higher localization accuracy as compared to state-of-the-art (cutting the error by more than 20%). It is also robust against environmental variations (reducing error by 30%), even when the signal values deviate greatly from their original design settings.

We study the forecasting problem for traffic with dynamic, possibly periodical, and joint spatial-temporal dependency between regions. Given the aggregated inflow and outflow traffic of regions in a city from time slots 0 to$t - 1$, we predict the traffic at time$t$for any region. Prior arts in the area often considered the spatial and temporal dependencies in a decoupled manner, or were rather computationally intensive in training with a large number of hyper-parameters which needed tuning. We propose ST-TIS, a novel, lightweight and accurateSpatial-TemporalTransformer withinformation fusion and regionsampling for traffic forecasting. ST-TIS extends the canonical Transformer with information fusion and region sampling. The information fusion module captures the complex spatial-temporal dependency between regions. The region sampling module is to improve the efficiency and prediction accuracy, cutting the computation complexity for dependency learning from$O(n^{2})$to$O(n\sqrt{n})$, where$n$is the number of regions. With far fewer parameters than state-of-the-art deep learning models, ST-TIS's offline training is significantly faster in terms of tuning and computation (with a reduction of up to$90\%$on training time and network parameters). Notwithstanding such training efficiency, extensive experiments show that ST-TIS is substantially more accurate in online prediction than state-of-the-art approaches (with an average improvement of$9.5\%$on RMSE, and$12.4\%$on MAPE compared to STDN and DSAN).

Wi-Fi-on devices such as smartphones search for network availability by periodically broadcasting probe requests which encapsulate MAC addresses as device identifiers. To protect identity privacy, modern devices embed random MAC addresses in probe frames, the so-called MAC address randomization. Such randomization disrupts the frame association, inadvertently frustrating identity-oblivious statistical analytic efforts such as people counting and trajectory inference. To address that, we proposeCappuccino, a novel privacy-preserving approach that captures the association of probe requests under MAC address randomization. Cappuccino first estimates pairwise frame correlation and then associates frames over time. For frame correlation, it employs a self-supervised estimator that jointly considers multiple modalities, i.e., information elements, sequence number, and received signal strength. For multiple frame association, Cappuccino formulates frames as a minimum-cost flow optimization. To the best of our knowledge, this is the first piece of work that leverages self-supervised learning to estimate frame correlation based on multiple modalities and formulates the probe request association problem as the network flow optimization. We have conducted extensive experiments in a leading and crowded shopping mall for more than three months. Cappuccino achieves remarkable performance in terms of V-measure scores ($>0.85$).

In fingerprint-based indoor localization, fusing radio frequency (RF) and geomagnetic signals has been shown to achieve promising results. To efficiently collect fingerprints, implicit crowdsourcing can be used, where signals sampled by pedestrians are automatically labeled with their locations on a map. Previous work on crowdsourced fingerprinting is often based on a single signal, which is susceptible to signal bias and labeling error. We study, for the first time, implicit multimodal crowdsourcing for joint RF and geomagnetic fingerprinting. The scheme, termed UbiFin, exploits the spatial correlation among RF, geomagnetic, and motion signals to mitigate the impact of sensor noise, leading to highly accurate and robust fingerprinting without the need for any explicit manual intervention. Using clustering and dynamic programming, UbiFin correlates spatially different signals and filters effectively mislabeled signals. We conduct extensive experiments on our campus and a large multi-story shopping mall. Efficient and simple to implement, UbiFin outperforms other state-of-the-art crowdsourcing schemes to construct RF and geomagnetic fingerprints in terms of accuracy and robustness (cutting fingerprint error by 40 percent in general).

Live video traffic has been widely observed to vary significantly within short timescale. In order to manage such traffic dynamic of overlay live streaming, the Content Provider (CP) may deploy a set of geo-dispersed auto-scaling servers where the pay-as-you-go deployment cost is charged by the amount of resources used due to server uploading and data transmission between servers. To support geo-distributed user demands, we study a novel multi-origin multi-channel auto-scaling live streaming cloud that pushes each channel stream in the core network overlay as a tree covering the end servers who have local demand for the channel. The Origin-to-End (O2E) delay from an origin to an end server is due to the Server-to-Server (S2S) delays of the overlay links along the path. By optimizing the overlay of the core network, we seek to minimize the deployment cost and O2E delays of the channels (i.e., a bi-criteria problem), which can be equivalently phrased as minimizing the deployment cost while meeting certain given maximum O2E delay constraints. We formulate a realistic problem capturing the major cost and delay components, and show its NP-hardness. We proposeCost-optimized Multi-Origin Multi-ChannelOverlayStreaming (COCOS), a novel, efficient and near-optimal bi-criteria approximation algorithm with proven approximation ratio. Trace-driven extensive experimental results based on real-world live streaming service data validate that COCOS outperforms other state-of-the-art schemes by a wide margin (cutting the cost in general by more than 50%).

Of all indoor localization techniques, vision-based localization emerges as a promising one, mainly due to the ubiquity of rich visual features. Visual landmarks, which present distinguishing textures, play a fundamental role in visual indoor localization. However, few researches focus on visual landmark labeling. Preliminary arts usually designate a surveyor to select and record visual landmarks, which is tedious and time-consuming. Furthermore, due to structural changes (e.g., renovation), the visual landmark database may be outdated, leading to degraded localization accuracy. To overcome these limitations, we propose VILL , a user-friendly, efficient, and accurate approach for visual landmark labeling. VILL asks a user to sweep the camera to take a video clip of his/her surroundings. In the construction stage, VILL identifies unlabeled visual landmarks from videos adaptively according to the graph-based visual correlation representation. Based on the spatial correlations with selected anchor landmarks, VILL estimates locations of unlabeled ones on the floorplan accurately. In the update stage, VILL formulates an alteration identification model based on the judgments from different users to identify altered landmarks accurately. Extensive experimental results in two different trial sites show that VILL reduces the site survey substantially (by at least 65.9%) and achieves comparable accuracy.

As convolution has empowered many smart applications, dynamic convolution further equips it with the ability to adapt to diverse inputs. However, the static and dynamic convolutions are either layout-agnostic or computation-heavy, making it inappropriate for layout-specific applications, e.g., face recognition and medical image segmentation. We observe that these applications naturally exhibit the characteristics of large intra-image (spatial) variance and small cross-image variance. This observation motivates our efficient translation variant convolution (TVConv) for layout-aware visual processing. Technically, TVConv is composed of affinity maps and a weight-generating block. While affinity maps depict pixel-paired relationships gracefully, the weight-generating block can be explicitly over-parameterized for better training while maintaining efficient inference. Although conceptually simple, TVConv significantly improves the efficiency of the convolution and can be readily plugged into various network architectures. Extensive experiments on face recognition show that TVConv reduces the computational cost by up to 3.1 × and improves the corresponding throughput by 2.3× while maintaining a high accuracy compared to the depthwise convolution. Moreover, for the same computation cost, we boost the mean accuracy by up to 4.21%. We also conduct experiments on the optic disc/cup segmentation task and obtain better generalization performance, which helps mitigate the critical data scarcity issue. Code is available at https://github.com/JierunChen/TVConv.

We study the problem of floor identification for radiofrequency (RF) signal samples obtained in a crowdsourced manner, where the signal samples are highly heterogeneous and most samples lack their floor labels. We propose GRAFICS, a graph embedding-based floor identification system. GRAFICS first builds a highly versatile bipartite graph model, having APs on one side and signal samples on the other. GRAFICS then learns the low-dimensional embeddings of signal samples via a novel graph embedding algorithm named E-LINE. GRAFICS finally clusters the node embeddings along with the embeddings of a few labeled samples through a proximity-based hierarchical clustering, which eases the floor identification of every new sample. We validate the effectiveness of GRAFICS based on two large-scale datasets that contain RF signal records from 204 buildings in Hangzhou, China, and five buildings in Hong Kong. Our experiment results show that GRAFICS achieves highly accurate prediction performance with only a few labeled samples (96% in both micro- and macro-F scores) and significantly outperforms several state-of-the-art algorithms (by about 45% improvement in micro-F score and 53% in macro-F score).

Docked bike systems have been widely deployed in many cities around the world. To the service provider, predicting the demand and supply of bikes at any station is crucial to offering the best service quality. The docked bike prediction problem is highly challenging because of the complicated joint spatial-temporal (ST) dependency as bikes are picked up and dropped off, the so-called “flows”, between stations. Prior works often considered the spatial and temporal dependencies separately using sequential network models, and based on locality assumptions. Without sufficiently capturing the joint spatial and temporal features, these approaches are not optimal for attaining the best prediction accuracy. We propose STGNN-DJD, a novel data-driven Spatial-Temporal Graph Neural Network to solve the bike demand and supply prediction problem by unifiedly embedding the Dynamic and Joint ST Dependency in two novel ST graphs. Given station locations and historical rental data on bike flow over the past time slots 0 to$t-1$, we seek to predict online the bike demand and supply at any station at time$t$. To extract joint spatial-temporal dependency, STGNN-DJD employs a graph generator to construct, at the beginning of time$t$, two graphs that embed the flow relationships between stations at various time slots (flow-convoluted graph) and dynamic demand-supply pattern correlation between stations (pattern correlation graph), respectively. Given the two spatial-temporal graphs, STGNN-DJD subsequently employs a graph neural network with novel flow-based and attention-based aggregators to generate embedding of each station for docked bike prediction. We have conducted extensive experiments on two large bike-sharing datasets. Our re-sults confirm the effectiveness of STGNN-DJD as compared with other state-of-the-art approaches, with significant improvement on RMSE and MAE (by 20%-50%). We also provide a case study on dynamic dependencies between stations and demonstrate that the locality assumption does not always hold for a docked bike system.

Proximity detection is to determine whether an IoT receiver is within a certain distance from a signal transmitter. Due to its low cost and high popularity, Bluetooth low energy (BLE) has been used to detect proximity based on the received signal strength indicator (RSSI). To address the fact that RSSI can be markedly influenced by device carriage states, previous works have incorporated RSSI with inertial measurement unit (IMU) using deep learning. However, they have not sufficiently accounted for the impact of multipath. Furthermore, due to the special setup, the IMU data collected in the training process may be biased, which hampers the system’s robustness and generalizability. This issue has not been studied before.We propose PRID, an IMU-assisted BLE proximity detection approach robust against RSSI fluctuation and IMU data bias. PRID histogramizes RSSI to extract multipath features and uses carriage state regularization to mitigate overfitting due to IMU data bias. We further propose PRID-lite based on a binarized neural network to substantially cut memory requirements for resource-constrained devices. We have conducted extensive experiments under different multipath environments, data bias levels, and a crowdsourced dataset. Our results show that PRID significantly reduces false detection cases compared with the existing arts (by over 50%). PRID-lite further reduces over 90% PRID model size and extends 60% battery life, with a minor compromise in accuracy (7%).

Image-to-markup generation aims at translating an image into markup (structured language) that represents both the contents and the structural semantics corresponding to the image. Recent encoder-decoder based approaches typically employ string decoders to model the string representation of the target markup, which cannot effectively capture the rich embedded structural information. In this paper, we propose TSDNet, a novel Tree-based Structure-aware Transformer Decoder NETwork to directly generate the tree representation of the target markup in a structure-aware manner. Specifically, our model learns to sequentially predict the node attributes, edge attributes, and node connectivities by multi-task learning. Meanwhile, we introduce a novel tree-structured attention to our decoder such that it can directly operate on the partial tree generated in each step to fully exploit the structural information. TSDNet doesn't rely on any prior assumptions on the target tree structure, and can be jointly optimized with encoders in an end-to-end fashion. We evaluate the performance of our model on public image-to-markup generation datasets, and demonstrate its ability to learn the complicated correlation from the structural information in the target markup with significant improvement over state-of-the-art methods by up to 5.6% in mathematical expression recognition and up to 35.34% in chemical formula recognition.

Covid-19 is primarily spread through contact with the virus, which may survive on surfaces with a lifespan of hours or even days if not sanitized. To curb its spread, it is hence of vital importance to detect those who have been in contact with the virus for a sustained period of time, the so-calledclose contacts. Most of the existing digital approaches for contact tracing focus only on direct face-to-face contacts. There has been little work on detecting indirect environmental contact, which is to detect people coming into a contaminated area with the live virus, i.e., an area last visited by an infected person within the virus lifespan. In this work, we study automatic Internet of Things (IoT) contact tracing when the virus has a lifespan, which may depend on the disinfection frequency at a location. Leveraging the ubiquity of WiFi signals, we propose vContact, a novel, private, pervasive, and fully distributed WiFi-based IoT contact tracing approach. Users carrying an IoT device (phone, wearable, dongle, etc.) continuously scan WiFi access points (APs) and store their hashed IDs. Given a confirmed case, the signals are then uploaded to a server for other users to match in their local IoT devices for virus exposure notification. vContact is not based on device pairing, and no information of other users is stored locally. The confirmed case does not need to have the device for it to work properly. As WiFi data are sampled sporadically and asynchronously, vContact uses novel and effective signal processing approaches and a similarity metric to align and match signals at any time. We conduct extensive indoor and outdoor experiments to validate vContact performance. Our results demonstrate that vContact is effective and accurate for contact detection. The precision, recall, and F1-score of contact detection are high (up to 90%) for close contact proximity (2 m). Its performance is robust against AP numbers, AP changes, and phone heterogeneity. Having implemented vContact as an Android software development kit and installed it on phones and smart watches, we present a case study to demonstrate the validity and implementability of our design in notifying its users about their exposure to the virus with a specific lifespan.

The geomagnetic field has been wildly advocated as an effective signal for fingerprint-based indoor localization due to its omnipresence and local distinctive features. Prior survey-based approaches to collect magnetic fingerprints often required surveyors to walk at constant speeds or rely on a meticulously calibrated pedometer (step counter) or manual training. This is inconvenient, error-prone, and not highly deployable in practice. To overcome that, we propose Maficon, a novel and efficient pedometer-free approach for geo ma gnetic fi ngerprint database con struction. In Maficon, a surveyor simply walks at casual (arbitrary) speed along the survey path to collect geomagnetic signals. By correlating the features of geomagnetic signals and accelerometer readings (user motions), Maficon adopts a self-learning approach and formulates a quadratic programming to accurately estimate the walking speed in each signal segment and label these segments with their physical locations. To the best of our knowledge, Maficon is the first piece of work on pedometer-free magnetic fingerprinting with casual walking speed. Extensive experiments show that Maficon significantly reduces walking speed estimation error (by more than 20%) and hence fingerprint error (by 35% in general) as compared with traditional and state-of-the-art schemes.

While deep learning demonstrates its strong ability to handle independent and identically distributed (IID) data, it often suffers from out-of-distribution (OoD) generalization, where the test data come from another distribution (w.r.t. the training one). Designing a general OoD generalization framework for a wide range of applications is challenging, mainly due to different kinds of distribution shifts in the real world, such as the shift across domains or the extrapolation of correlation. Most of the previous approaches can only solve one specific distribution shift, leading to unsatisfactory performance when applied to various OoD benchmarks. In this work, we propose DecAug, a novel decomposed feature representation and semantic augmentation approach for OoD generalization. Specifically, DecAug disentangles the category-related and context-related features by orthogonalizing the two gradients (w.r.t. intermediate features) of losses for predicting category and context labels, where category-related features contain causal information of the target object, while context-related features cause distribution shifts between training and test data. Furthermore, we perform gradient-based augmentation on context-related features to improve the robustness of learned representations. Experimental results show that DecAug outperforms other state-of-the-art methods on various OoD datasets, which is among the very few methods that can deal with different types of OoD generalization challenges.

Image demosaicking and denoising are the two key fundamental steps in digital camera pipelines, aiming to reconstruct clean color images from noisy luminance readings. In this paper, we propose and study Wild-JDD, a novel learning framework for joint demosaicking and denoising in the wild. In contrast to previous works which generally assume the ground truth of training data is a perfect reflection of the reality, we consider here the more common imperfect case of ground truth uncertainty in the wild. We first illustrate its manifestation as various kinds of artifacts including zipper effect, color moire and residual noise. Then we formulate a two-stage data degradation process to capture such ground truth uncertainty, where a conjugate prior distribution is imposed upon a base distribution. After that, we derive an evidence lower bound (ELBO) loss to train a neural network that approximates the parameters of the conjugate prior distribution conditioned on the degraded input. Finally, to further enhance the performance for out-of-distribution input, we design a simple but effective fine-tuning strategy by taking the input as a weakly informative prior. Taking into account ground truth uncertainty, Wild-JDD enjoys good interpretability during optimization. Extensive experiments validate that it outperforms state-of-the-art schemes on joint demosaicking and denoising tasks on both synthetic and realistic raw datasets.

Recent advances on Out-of-Distribution (OoD) generalization reveal the robustness of deep learning models against distribution shifts. However, existing works focus on OoD algorithms, such as invariant risk minimization, domain generalization, or stable learning, without considering the influence of deep model architectures on OoD generalization, which may lead to sub-optimal performance. Neural Architecture Search (NAS) methods search for architecture based on its performance on the training data, which may result in poor generalization for OoD tasks. In this work, we propose robust Neural Architecture Search for OoD generalization (NAS-OoD), which optimizes the architecture with respect to its performance on generated OoD data by gradient descent. Specifically, a data generator is learned to synthesize OoD data by maximizing losses computed by different neural architectures, while the goal for architecture search is to find the optimal architecture parameters that minimize the synthetic OoD data losses. The data generator and the neural architecture are jointly optimized in an end-to-end manner, and the minimax training process effectively discovers robust architectures that generalize well for different distribution shifts. Extensive experimental results show that NAS-OoD achieves superior performance on various OoD generalization benchmarks with deep models having a much fewer number of parameters. In addition, on a real industry dataset, the proposed NAS-OoD method reduces the error rate by more than 70% compared with the state-of-the-art method, demonstrating the proposed method’s practicality for real applications.

With the rapid advances and the penetration of the Internet of Things and sensors, a massive amount of trajectory data, given by discrete locations at certain timestamps, have been extracted or collected. Knowing the similarity between trajectories is fundamental to understanding their spatial-temporal correlation, with direct and far-reaching applications in contact tracing, companion detection, personalized marketing, etc. In this work, we consider the general and realistic sensing scenario that the locations of the trajectories may be noisy, and that these trajectories are sporadically sampled with randomness and asynchrony from the underlying continuous paths. Most of the prior work on trajectory similarity has not sufficiently considered the temporal dimension, or the issues of location noise and sporadic sampling, while others have limitations of strong assumptions such as a fixed known speed of users or the availability of a large amount of training data.We propose a novel and effective spatial-temporal measure termed STS (Spatial-Temporal Similarity) to evaluate the spatial-temporal overlap between any two trajectories. In order to account for the location noise and sporadic sampling, STS models each location in a trajectory as an observable outcome drawn from a probability distribution. With that, it efficiently reduces the need for training data by estimating a personalized spatial-temporal probability distribution of the object position from its own trajectory. Based on that, it subsequently computes the co-location probability and hence derives the similarity of any two trajectories. We have conducted extensive experiments to evaluate STS using real large-scale indoor (mall) and outdoor (taxi) datasets. Our results show that STS is substantially more accurate and robust than the state-of-the-art approaches, with an improvement of 63% on precision and 85% on mean rank.

Wi-Fi-enabled devices such as smartphones periodically search for available networks by broadcasting probe requests which encapsulate MAC addresses as the device identifiers. To protect privacy (user identity and location), modern devices embed random MAC addresses in their probe frames, the so-called MAC address randomization. Such randomization greatly hampers statistical analysis such as people counting and trajectory inference. To mitigate its impact while respecting privacy, we propose Espresso, a simple, novel and efficient approach which establishes probe request association under MAC address randomization. Espresso models the frame association as a flow network, with frames as nodes and frame correlation as edge cost. To estimate the correlation between any two frames, it considers the multimodality of request frames, including information elements, sequence numbers and received signal strength. It then associates frames with minimum-cost flow optimization. To the best of our knowledge, this is the first piece of work that formulates the probe request association problem as network flow optimization using frame correlation. We have implemented Espresso and conducted extensive experiments in a leading shopping mall. Our results show that Espresso outperforms the state-of-the-art schemes in terms of discrimination accuracy (> 80%) and V-measure scores (> 0.85).

In a video-on-demand (VoD) service, blockbuster videos have stable and predictable popularity, but the traffic can vary significantly within short timescale. To efficiently serve the user pool in a geographic region, we consider a regional auto-scaling cloud-based data center consisting of multiple servers. For efficient storage, we partition the videos into fixed-size blocks. To respond to dynamic user traffic in a timely and cost-effective manner, we may activate or deactivate each server according to the traffic while keeping at least one replica for each block in the active servers. We maximize the user capacity of the active servers (and hence minimizing the number of active servers at any time) by jointly optimizing block allocation in the servers, server selection at each traffic level, and request dispatching to a server. We believe that this is the first work to study such problem for an auto-scaling cloud-based VoD data center. We first formulate the problem and show its NP-hardness. We then propose AVARDO (Auto-scalingVideoAllocation andRequestDistributionOptimization), a simple but efficient approximation algorithm with proven optimality. AVARDO operates the servers like a stack, with a server being pushed into or popped from the existing active server set according to some optimized traffic thresholds. We prove that AVARDO approaches the theoretical optimum as the block size reduces. Trace-driven experimental results based on large-scale real-world video data further validate that AVARDO is closely optimal. It achieves significantly higher user capacity as compared with other state-of-the-art and traditional schemes, and reduces the optimality gap by multiple times.

In interfering WLANs, clients are usually non-uniformly distributed. Therefore, their throughput can be improved by association control. WLANs adopt DCF (Distributed Coordinating Function) for media access control. The transmit probability of an AP is governed by its CW (Contention Window). Random Access control is to determine the CW size and hence the transmit probability of each AP. Client association control and random access control are coupled. APs associated with more clients require higher channel access opportunities. On the other hand, APs with higher transmit probability should serve more clients. We study the novel problem of maximizing the proportional fairness of client throughput by joint association control and random access control. As the joint problem is non-convex, we first consider that client association is given and propose an optimal policy for random access control. Given the CWs of APs, we propose a factor-2 approximation algorithm, Greedy-Asso to address the client association problem. Inspired by the optimal access control policy and Greedy-Asso, we further propose a distributed algorithm, termed CARA to tackle the joint optimization problem. Extensive simulation and experimental studies show that it outperforms comparison schemes by a wide margin in terms of throughput and fairness.

Locality classification is an important component to enable location-based services. It entails two sequential queries: 1) whether a target is within the site or not, i.e., inside/outside region decision, and 2) if so, which area in the region the target is located, i.e., area classification. Locality classification is hence more coarse-grained and efficient as compared with pinpointing the exact target location in the region. The classification problem is challenging, because fingerprints may not exist outside the region for training. Furthermore, the target may sample an incomplete RSSI vector due to, say, random signal noise, momentary occlusion, or scanning duration. The algorithm also has to be computationally efficient. We propose INOA, a scalable and practical locality classification overcoming the above challenges. INOA may serve as a plug-in before any fingerprint-based localization, and can be incrementally extended to cover new areas or regions for large-scale deployment. Its preprocessor cherry-picks only those discriminating access points, which greatly enhances computational efficiency and accuracy. By formulating a “one-class” classifier using ensemble learning, INOA accurately decides whether the target is within the region or not. Extensive experimental trials in different sites validate the high efficiency and accuracy of INOA, without the need of full RSSI vectors collected at the target.

Fusing mutual distance information with fingerprints can substantially improve indoor localization accuracy. Such distance information may be spatial (e.g., measurement among users or from installed beaconing devices) or temporal (e.g., via dead-reckoning). Previous approaches on distance-fusion often require deterministic distance measurement, consider fingerprints and distances separately, or are narrowly applicable to some specific sensing technology or scenario. Given the fact that fingerprint and distance measurements are intrinsically random, we propose Maxlifd, an accurate indoor localization framework fusing fingerprints and distances of arbitrary distributions via joint maximum likelihood. Maxlifd is a generic statistical/probabilistic framework applicable to a wide range of sensors (peer-assisted, INS, iBeacon, etc.) and fingerprints (Wi-Fi, RFID, etc.). It achieves low localization errors by a novel optimization formulation jointly considering mutual distances and fingerprint signals. Using generic probabilistic formulation, we further derive the lower bound on localization error for comprehensive performance analysis. We have implemented Maxlifd, and conducted extensive simulation and experimental trials in an international airport and our university campus. Our results show that Maxlifd achieves significantly lower errors than other state-of-the-art schemes (often by more than 30 percent). We experimentally verify that its performance does not depend sensitively on the exact knowledge of the underlying distributions beyond simple Gaussian.

Image-based indoor localization has aroused much interest recently because it requires no infrastructure support. Previous approaches on image-based localization, due to their computation and storage requirements, often process queries at servers. This does not scale well, incurs round-trip delay, and requires constant network connectivity. Many also require users to manually confirm the shortlisted matched landmarks, which is inconvenient, slow, and prone to selection error. To overcome these limitations, we propose a h ighly a utomated (in terms of image confirmation after taking images) i mage-based l ocalization algorithm (HAIL), distributed in mobile devices. HAIL achieves resource efficiency (in terms of storage and processing) by keeping only distinguishing visual features for each landmark, and employing the efficient k-d tree to search for features. It further utilizes motion sensors and map constraints to enhance the localization accuracy without user operation. We have implemented HAIL on Android platforms and conducted extensive experiments in a food plaza and a premium shopping mall. Experimental results show that it achieves much higher localization accuracy (reducing the localization error by more than 20%) and computation efficiency (by more than 40% in time) as compared with the state-of-the-art approaches.

Geomagnetism is promising for indoor localization due to its omnipresence, high stability, and availability of magnetometers in smartphones. Previous works often fuse it with pedometer via particles, which are computationally intensive and make strong user behavior assumptions. To overcome that, we propose Magil, an approach leveraging geo mag netism for i ndoor l ocalization. To our best knowledge, this is the first piece of work using geomagnetism for smartphone localization without the need of pedometer or user walking model. Magil is applicable to any open or complex indoor environment. In the offline phase, Magil collects and stores geomagnetic fingerprints while surveyors walk indoors. In the online phase, it employs a fast algorithm to match the geomagnetic variation of the target with the stored fingerprints. Given closely matched segments, Magil constructs user trajectory efficiently with a modified shortest path formulation by selecting and connecting these matched segments. To further improve accuracy and deployability, we propose MagFi, which extends Mag il by fusing it with Wi- Fi . MagFi further collects opportunistic Wi-Fi RSSI for fingerprint construction. We have implemented both Magil and MagFi and conducted extensive experiments in our campus. Results show that our schemes outperform state-of-the-art schemes by a wide margin (often cutting localization error by 30%).

Interference Alignment (IA) has emerged as a promising interference coordination approach for cooperative MIMO systems. Due to heavy CSI feedback overhead, APs (Access Points) need to be partitioned into cooperation groups no larger than a certain size where only APs in the same group are able to cooperate with IA. We consider a general MIMO network using a hybrid interference coordination approach, i.e. intra-group interference is managed with IA, while inter-group interference is overcome with traditional orthogonal multiple access techniques. Users are usually non-uniformly distributed. Their throughput can be improved by association optimization. We study the novel problem of minimizing AP load by joint AP grouping and user association. The problem is shown to be NP-hard. Based on alternating direction optimization, we propose DAGA (Distributed Joint AP Grouping and User Association) to tackle the problem. DAGA is distributed and uses only long-term CSI. Based on current AP grouping, it produces an approximated user association solution which is at most elogm (m is the number of APs) times of the optimum. Based on current user association, it adjusts AP grouping with local search. Extensive simulation results show that it substantially outperforms other comparison schemes.

To improve the accuracy of fingerprint-based localization, one may fuse step counterwith fingerprints. However, the walking step model may vary among people. Such user heterogeneity may lead to measurement error in walking distance. Previous works often require a step counter tediously calibrated offline or through explicit user input. Besides, as device heterogeneity may introduce various signal readings, these studies often need to calibrate the fingerprint RSSI model. Many of them have not addressed how to jointly calibrate the above heterogeneities and locate the user. We propose SLAC, a novel system which simultaneously localizes the user and calibrates the sensors. SLAC works transparently, and is calibration-free with heterogeneous devices and users. Its novel formulation is embedded with sensor calibration, where location estimations, fingerprint signals, and walking motion are jointly optimized with resultant consistent and correct model parameters. To reduce the localization search scope, SLAC first maps the target to a coarse region (say, floor) via stacked denoising autoencoders and then executes the fine-grained localization. Extensive experimental trials at our campus and the international airport further confirm that SLAC accommodates device and user heterogeneity, and outperforms other state-of-the-art fingerprint-based and fusion algorithms by lower localization errors (often by more than 30 percent).

Geomagnetism is promising for indoor localization due to its pervasive presence, high signal stability and unnecessity of extra infrastructure support. It can be fused with a pedometer (step counter) to further improve accuracy. Traditional fusions based on particle filter, however, are computationally complex. Their accuracy is barely satisfactory for large open indoor spaces (such as airports or malls), mainly because particles cannot converge properly in environments with high degree of freedom. They often assume knowledge or explicit user step length input, which is inconvenient or difficult to achieve in reality. We propose Mapel, which efficiently fuses geomagnetism with pedometer based on graphical model without manual user input. Mapel is applicable to any indoor environment. We first discretize indoor map into closely spaced lattice nodes (separated by, say, 0.5~1 meter) in a graph, representing potential target locations. Using conditional random field (CRF), Mapel then conducts geomagnetism-pedometer fusion to estimate user location in the lattice. By jointly considering geomagnetism pattern and step counts, Mapel adaptively self-calibrates a step model for each user without explicit input. Extensive experiments conducted at our campus show that Mapel outperforms state-of-the-art schemes by a wide margin (cutting localization error by more than 40% and reducing computation time by more than 30%).

Site survey cost has become a major deployment challenge for large-scale wireless systems. Some previous approaches require explicit user inputs to label the locations of crowdsourced signals, which is inconvenient in practice. Others may rely on intensively-calibrated specialized sensors. Furthermore, the locations of crowdsourced signals are usually random and sparse, making it difficult to build a complete signal map. To address these, we propose Surecose, a novel signal map construction system by implicit crowdsourcing and interaction of low-cost cooperative sensors. Surecose is initialized with the light-weight sparse signal map collection. Having the background application on, the naive users are implicit surveyors unknowingly uploading crowdsourced signals. Phones may detect each other (mobile sensors), or beacons (fixed sensors). To label their locations, Surecose measures the mutual sensor proximity of the IoT devices. Via joint location labeling and sensor calibration, Surecose transparently locates the users despite devices used. Then Surecose constructs the database with a directionally and environmentally adapted Gaussian process, which scales the labeled locations and RSSIs anywhere into a complete signal map. Extensive experiments in diverse environments, including a campus hall, an international airport and a premium shopping mall, have validated that Surecose can adaptively and accurately construct the Wi-Fi signal map (often more than 20% reduction in RSSI construction error), with low survey cost (around 70% survey reduction) and little human intervention.

Due to its accuracy, trilateration has been widely deployed to locate smartphones outdoors. However, such approach cannot be easily applied indoors due to issues like non-line-of-sight measurement and complex multipath fading. Though fingerprinting overcomes these issues, its accuracy is often hampered by signal noise and the similarity metric comparing signal vectors. We propose INTRI, a novel, simple, accurate, and effective indoor localization framework combining strengths of trilateration and fingerprinting. Given a signal level received from an access point (AP) at target, INTRI first forms a contour given by reference points (RPs) with the same signal level, taking into account signal noise. The target is hence at the juncture of contours formed by all APs. We present selecting RPs for random signal by a width parameter determining the signal contour width (or spread). Then, an LP-based formulation finds the location following spirit of trilateration, which minimizes distance between target position and all contours. A novel particle filter leverages crowdsourced user inputs to adaptively estimate the width parameter. An online algorithm is further used to calibrate heterogeneous smartphones. Our extensive experiments in an airport, a shopping mall, and our campus show INTRI outperforms recent schemes with substantially lower error (often by more than 20 percent).

Wi-Fi fingerprinting has been extensively studied for indoor localization due to its deployability under pervasive indoor WLAN. As the signals from access points (APs) may change due to, for example, AP movement or power adjustment, the traditional approach is to conduct site survey regularly in order to maintain localization accuracy, which is costly and time-consuming. Here, we study how to accurately locate a target and automatically update fingerprints in the presence of altered AP signals (or simply, “altered APs”). We propose Localization with Altered APs and Fingerprint Updating (LAAFU) system, employing implicit crowdsourced signals for fingerprint update and survey reduction. Using novel subset sampling, LAAFU identifies any altered APs and filter them out before a location decision is made, hence maintaining localization accuracy under altered AP signals. With client locations anywhere in the region, fingerprint signals can be adaptively and transparently updated using non-parametric Gaussian process regression. We have conducted extensive experiments in our campus hall, an international airport, and a premium shopping mall. Compared with traditional weighted nearest neighbors and probabilistic algorithms, results show that LAAFU is robust against altered APs, achieving 20 percent localization error reduction with the fingerprints adaptive to environmental signal changes.

In spacious and multi-area buildings, fingerprint-based localization often suffers from expensive location search. Besides, context knowledge like inside/outside-region and floor area is important for complete location service. To address above issues, beyond the algorithms finding the exact location point, we study accurate and efficient indoor area classification for large-scale fingerprint-based system. We first study leveraging the one-class classification to conduct inside/outside-region detection given only the inside fingerprints. Then we discuss different area determination algorithms, and compare their detection accuracy and deployment efficiency. To further enhance accuracy, we also discuss rejecting unclassifiable signals and calibrating heterogeneous devices. We have implemented different algorithms on Android platforms. Experimental trials (totally over 30,000 fingerprints and 15,000 test data) at an international airport, a business building, a premium shopping mall and a university campus have evaluated practicability and deployability of different classification schemes. Our studies can also serve as design guidelines for area classification.

In wireless local area networks (WLANs), association of the access points (APs) is often not uniform due to joining and leaving of wireless users. Such imbalance leads to unsatisfactory user throughput due to congestion at some APs and channel under-utilization at others. As users may be covered by multiple APs in WLAN deployment, their throughput can be improved by AP re-association, i.e., migrating some users from the congested APs to the less loaded neighboring APs. Such reassociation is expected to come with some cost (due to overhead in handshaking, authentication and data flow management). In this paper, we study the novel problem of optimizing AP re-association by maximizing the minimum user throughput (i.e., max-min fairness), subject to a certain total user migration cost constraint. We show that the problem is NP-hard. We then propose an efficient approximation algorithm called CACA (Cost-constrained Association Control Algorithm). CACA has provable performance, achieving an approximation factor of (4+ϵ), for any ϵ > 0. It is simple and implementable. Our extensive simulation results based on NS3 show that it substantially outperforms other comparison schemes with close-to-optimal performance (the case without cost constraint). Our testbed experiments further confirm the effectiveness of CACA.

In a wireless system, a signal map shows the signal strength at different locations termed reference points (RPs). As access points (APs) and their transmission power may change over time, keeping an updated signal map is important for applications such as Wi-Fi optimization and indoor localization. Traditionally, the signal map is obtained by a full site survey, which is time-consuming and costly. We address in this paper how to efficiently update a signal map given sparse samples randomly crowdsourced in the space (e.g., by signal monitors, explicit human input, or implicit user participation).

In indoor localization based on Wi-Fi fingerprinting, a target sends its received signal strength indicator (RSSI) of access points (APs) to a server to estimate its position. Traditionally, the server estimates the target position by matching the RSSI with the fingerprints stored in the database. Due to signal noise in fingerprint collection and target measurement, this often results in a geographically disperse set of reference points (RPs), leading to unsatisfactory estimation accuracy. To mitigate the noise problem, we propose a novel, efficient, and highly accurate localization scheme termed Tilejunction. Based on only the first two moments of the measured signal, Tilejunction maps the target RSSI of each AP to a convex hull termed signal “tile” where the target is likely within. Using a novel comparison metric for random signals, we formulate a linear programming (LP) problem to localize the target at the junction of the tiles. To further improve its computational efficiency, Tilejunction employs an information-theoretic measure to keep only those APs whose signals show sufficient differentiation in the site. It also partitions the site into multiple clusters to substantially reduce the search space in the LP optimization. We have implemented Tilejunction. Our extensive simulation and experimental measurements show that it outperforms other recent state-of-the-art approaches (e.g. RADAR, KL-divergence, etc.) with significantly lower localization error (often by more than 30 percent).

Free viewpoint video (FVV) offers compelling interactive experience by allowing users to switch to any viewing angle at any time. An FVV is composed of a large number of camera-captured anchor views, with virtual views (not captured by any camera) rendered from their nearby anchors using techniques such as depth-image-based rendering (DIBR). We consider a group of wireless users who may interact with an FVV by independently switching views. We study a novel live FVV streaming network where each user pulls a subset of anchors from the server via a primary channel. To enhance anchor availability at each user, a user generates network-coded (NC) packets using some of its anchors and broadcasts them to its direct neighbors via a secondary channel. Given limited primary and secondary channel bandwidths at the devices, we seek to maximize the received video quality (i.e., minimize distortion) by jointly optimizing the set of anchors each device pulls and the anchor combination to generate NC packets. To our best knowledge, this is among the first body of work addressing such joint optimization problem for wireless live FVV streaming with NC-based collaboration. We first formulate the problem and show that it is NP-hard. We then propose a scalable and effective algorithm called PAFV (Peer-Assisted Freeview Video). In PAFV, each node collaboratively and distributedly decides on the anchors to pull and NC packets to share so as to minimize video distortion in its neighborhood. Extensive simulation studies show that PAFV outperforms other algorithms, achieving substantially lower video distortion (often by more than 20-50%) with significantly less redundancy (by as much as 70%). Our Android-based video experiment further confirms the effectiveness of PAFV over comparison schemes.

We consider providing large-scale Netflix-like video-on-demand (VoD) service on a cloud platform, where cloud proxy servers are placed close to user pools. Videos may have heterogeneous popularity at different geo-locations. A repository provides video backup for the network, and the proxy servers collaboratively store and stream videos. To deploy the VoD cloud, the content provider rents resources consisting of link capacities among servers, server storage, and server processing capacity to handle remote requests. We study how to minimize the deployment cost by jointly optimizing video management (in terms of video placement and retrieval at servers) and resource allocation (in terms of link, storage, and processing capacities), subject to a certain user delay requirement on video access. We first formulate the joint optimization problem and show that it is NP-hard. To address it, we propose Resource allocation And Video management Optimization (RAVO), a novel and efficient algorithm based on linear programming with proven optimality gap. For a large video pool, we propose a video clustering algorithm to substantially reduce the run-time computational complexity without compromising performance. Using extensive simulation and trace-driven real data, we show that RAVO achieves close-to-optimal performance, outperforming other advanced schemes significantly (often by multiple times).

editorial Free Access Share on Introduction to Special Issue on Multimedia Big Data: Networking Editors: Mianxiong Dong Muroran Institute of Technology, Japan Muroran Institute of Technology, JapanView Profile , Vincenzo Piuri Università degli Studi di Milano, Italy Università degli Studi di Milano, ItalyView Profile , Shueng-Han Gary Chan The Hong Kong University of Science and Technology, Hong Kong The Hong Kong University of Science and Technology, Hong KongView Profile , Ramesh Jain University of California, Irvine, CA University of California, Irvine, CAView Profile Authors Info & Claims ACM Transactions on Multimedia Computing, Communications, and ApplicationsVolume 12Issue 5sDecember 2016 Article No.: 70pp 1–3https://doi.org/10.1145/2989214Published:21 September 2016Publication History 1citation336DownloadsMetricsTotal Citations1Total Downloads336Last 12 Months17Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In order to improve the accuracy of fingerprint-based localization, one may fuse step counter measurement with location estimation. Previous works on this often require a pre-calibrating the step counter with training sequence or explicit user input, which is inconvenient for practical deployment. Some assume conditional independence on successive sensor readings, which achieves unsatisfactory accuracy in complex and noisy environment. Some other works need a calibration process for RSSI measurement consistency if different devices are used for offline fingerprint collection and online location query.

In order to provide scalable live streaming service, a content provider often deploys an overlay cloud consisting of distributed servers which collaboratively exchange streams with each other. We consider an overlay consisting of multiple live channels originating from multiple sources. Server bandwidth and end-to-end network bandwidth are shared among these channels. The stream of each channel is divided into multiple substreams of a certain bitrate, each of which is pushed via a tree to the servers that subscribe to the channel. The critical and challenging issue is then how to optimize the topology of the substream trees so as to minimize the maximum channel delay (defined as the delay from the source to the subscribing servers). There has been little work on the optimization of such multisource multi-channel live streaming network. We first formulate the problem which comprehensively and realistically captures various delay and bandwidth components, and show that it is NP-hard. We then propose an efficient algorithm called COMMOS (Collaborative Multi-source Multi-channel Streaming Overlay) which achieves low channel delay. Extensive simulation results based on real Internet topologies show that COMMOS outperforms other state-of-the-art schemes by a wide margin (often by more than 40%), due to its better utilization of network resources.

Fusing fingerprints with mutual distance information potentially improves indoor localization accuracy. Such distance information may be spatial (e.g., via inter-node measurement) or temporal (e.g., via dead reckoning). Previous approaches on distance fusion often require exact distance measurement, assume the knowledge of distance distribution, or apply narrowly to some specific sensing technology or scenario. Due to random signal fluctuation, wireless fingerprints are inherently noisy and distance cannot be exactly measured. We hence propose Wi-Dist, a highly accurate indoor localization framework fusing noisy fingerprints with uncertain mutual distances (given by their bounds). Wi-Dist is a generic framework applicable to a wide range of sensors (peer-assisted, INS, etc.) and wireless fingerprints (Wi-Fi, RFID, CSI, etc.). It achieves low errors by a convex-optimization formulation which jointly considers distance bounds and only the first two moments of measured fingerprint signals. We implement Wi-Dist, and conduct extensive simulation and experimental studies based on Wi-Fi in our international airport and university campus. Our results show that Wi-Dist achieves significantly better accuracy than other state-of-the-art schemes (often by more than 40%).

Trilateration has been widely and successfully employed to locate outdoor mobile devices due to its accuracy. However, it cannot be directly applied for indoor localization due to issues such as non-line-of-sight measurement and multipath fading. Though fingerprinting overcomes these issues, its accuracy is often hampered by signal noise and the choice of similarity metric between signal vectors. We propose INTRI, a novel, simple and effective indoor localization technique combining the strengths of trilateration and fingerprinting.

There has recently been growing interest for content providers to provide video-on-demand (VoD) as a cloud service. In such a network, the content provider may rent heterogeneous resources (such as streaming and storage capacities ) from geographically distributed data centers deployed close to user pools. These data centers (or proxy servers) collaboratively share content with each other to serve their local users. A critical challenge is to optimize movie storage and retrieval to minimize the deployment cost consisting of streaming, storage, and network transmission between data centers. We propose a novel and effective movie storage and retrieval using linear source coding. All the movies are source-encoded once at the repository, by taking every q source symbols of movie m to generate n(m)coded symbols. These coded symbols are then distributed to the servers in the cloud. Based on a general and comprehensive cost model, we optimize n(m)and the number of symbols to retrieve from remote servers for a local movie request. The optimal solution can be efficiently computed with a linear programming (LP) formulation . Our solution is proved to asymptotically approach the global minimum cost as q increases. Even when q is low, near optimality can be achieved. To accommodate large movie pool and system parameter changes, we propose algorithms for movie grouping and on-line re-optimization which significantly reduce the computational complexity with little compromise on optimality. Through extensive simulation, our algorithm is shown to achieve the lowest cost, outperforming traditional and state-of-the-art heuristics with a substantially wide margin.

In free viewpoint video, a viewer can choose at will any camera angle or the so-called “virtual view” to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera views via depth-image-based rendering (DIBR). We consider, for the first time, collaborative live streaming of a free viewpoint video, where a group of users may interactively pull and cooperatively share streams of different anchor views. There is a cost to access the anchor views from the live source, a cost to “reconfigure” the peer network due to a change in selected anchors during view switching, and a distortion cost due to the distance of the virtual views to the received anchor views at users. We optimize the anchor views allocated to users so as to minimize the overall streaming cost given by the access cost, reconfiguration cost, and view distortion cost. We first show that, if the reconfiguration cost due to view switching is negligible, the view allocation problem can be optimally and efficiently solved in polynomial time using dynamic programming. For the case of non-negligible reconfiguration cost, the problem becomes NP-hard. We thus present a locally optimal and centralized algorithm inspired by Lloyd's algorithm used in non-uniform scalar quantization. We further propose a distributed algorithm with convergence guarantee, where each peer group independently makes merge-and-split decisions with a well-defined fairness criteria. Simulation results show that our algorithms achieve low streaming cost due to its excellent anchor view allocation.

In Wi-Fi fingerprint localization, a target sends its measured Received Signal Strength Indicator (RSSI) of access points (APs) to a server for its position estimation. Traditionally, the server estimates the target position by matching the RSSI with the fingerprints stored in database. Due to signal measurement uncertainty, this matching process often leads to a geographically dispersed set of reference points, resulting in unsatisfactory estimation accuracy. We propose a novel, efficient and highly accurate localization scheme termed Sectjunction which does not lead to a dispersed set of neighbors. For each selected AP, Sectjunction sectorizes its coverage area according to discrete signal levels, hence achieving robustness against measurement uncertainty. Based on the received AP RSSI, the target can then be mapped to the sector where it is likely to be. To further enhance its computational efficiency, Sectjunction partitions the site into multiple area clusters to narrow the search space. Through convex optimization, the target is localized based on the cluster and the junction of the sectors it is within. We have implemented Sectjunction, and our extensive experiments show that it significantly outperforms recent schemes with much lower estimation error.

A wireless mesh employing directional antenna, termed DMesh in this paper, can greatly extend coverage and improve spatial reuse of wireless channels. As beaming direction of the antennas changes network topology which in turns affects routing and channel decisions, we address in this work how to jointly optimize topology (in terms of beaming directions of antennas), routing and channel assignment so as to maximize network throughput. Specifically, we use a model based on SINR which captures much more realistically network interference than the traditional conflict graph approach. Using the model, we then formulate the NP-hard optimization problem for a general DMesh with multiple gateways, possibly heterogeneous number of antennas in routers, and routers generating traffic to any of the gateways or routers. As the problem is NP-hard, we propose a simple and implementable joint optimization heuristic called TORCA (topology control, routing and channel assignment). TORCA is based on iterative LP rounding guaranteed to converge. Extensive simulation based on NS3 shows that TORCA is closely optimal and highly efficient, performing significantly better than recent approaches by wide margins in terms of loss rate, delay, fairness and throughput.

The performance of multi-channel (MRMC) wireless mesh networks (WMNs) is largely affected by interference, which depends on router placement, traffic routing and channel assignment. This work seeks to jointly optimize the placement, routing and channel assignment for mesh deployment given flow requirements. The problem is complex because router placement changes network topology which in turns impacts routing and channel decisions, while routing and channel assignment algorithms affect router placement decision. We present a novel scheme PRACA (Placement, Routing And Channel Assignment), which seeks to minimize the network-wide interference by considering the three inter-dependent factors. Through extensive simulation, we show that PRACA significantly outperforms other schemes in terms of loss rate, delay, fairness and throughput.

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request any one of many captured views for playback. Moreover, the client can periodically freeze the video in time and switch to neighboring views for a compelling look-around visual effect. We consider distributed content servers to support large-scale interactive multiview video service. These servers collaboratively replicate and access video contents. We study two challenges in this setting: what is an efficient coding structure that supports interactive view switching and, given that, what to replicate in each server in order to minimize the cost incurred by interactive temporal and view switches? We first propose a redundant coding structure that facilitates interactive view-switching, trading off storage with transmission rate. Using the coding structure, we next propose a content replication strategy that takes advantage of indirect hit to lower view-switching cost: in the event that the exact requested view is not available locally, the local server can fetch a different but correlated view from the other servers, so that the remote repository only needs to supply the pre-encoded view differential. We formulate the video content replication problem to minimize the switching cost as an integer linear programming (ILP) problem and show that it is NP-hard. We first propose an LP relaxation and rounding algorithm (termed Minimum Eviction) with bounded approximation error. We then study a more scalable solution based on dynamic programming and Lagrangian optimization (DPLO) with little sacrifice in performance. Simulation results show that our replication algorithms achieve substantially lower switching cost compared to other content replication schemes.

IPTV services deployed nowadays often consist of both live TV and Video-on-Demand (VoD), offered by the same service provider to the same pool of users over the same managed network. Understanding user behaviors in such a setting is hence an important step for system modelling and optimization. Previous studies on user behavior on video services were on either live TV or VoD. For the first time, we conduct an in-depth large-scale behavior study for IPTV users offering simultaneously live TV and VoD choices at the same time. Our data is from the largest IPTV service provider in China, offering hundreds of live channels and hundreds of thousands of VoD files, with traces covering more than 1.9 million users over a period of 5 months. This large dataset provides us a unique opportunity to cross-compare user viewing behaviors for these services on the same platform, and sheds valuable insights on how users interact with such a simultaneous system. Our results lead to new understanding on IPTV user behaviors which have strong implications on system design. For example, we find that the average holding time for VoD is significantly longer than live TV. live TV users tend to surf more. However, if such channel surfing is discounted, the holding times of both services are not much different. While users in VoD tend to view HD longer, channel popularity for live TV is much less dependent on its video quality. In contrast to some popular assumptions on user interactivity, the transitions among live TV, VoD, and offline modes are far from a Markov model.

In order to provide live streaming over the global Internet, a content provider often deploys an overlay network consisting of distributed proxies placed close to user pools. Streaming of multi-Mbps video over such an overlay is challenging because of bandwidth bottlenecks in paths. To effectively overcome these bottlenecks, we consider employing proxy helpers in the overlay to provide rich path diversity. The helpers do not have any attached users, and hence may forward partial video streams (or not at all) if necessary. In this way, the helpers serve as stepping stones to supply full streams to the servers. The issue is how to involve the helpers in the overlay to achieve low streaming delay meeting a certain high streaming bitrate requirement. To address the issue, we first formulate the problem which captures various delay and bandwidth components, and show that it is NP-hard. We then propose an efficient algorithm called Stepping-Stones (SS) which can be efficiently implemented in a controller. Given the encouraging simulation results, we develop a novel streaming testbed for SS and explore, through sets of Internet experiments, the effectiveness of helpers to achieve high bitrate (multi-Mbps) global live streaming. In our experiments, proxies are deployed with a reasonably wide global footprint. We collect more than a hundred hours of streaming traces with bitrate ranging from 500kbps to a few Mbps. Our experimental data validates that helpers indeed play an important role in achieving high bitrate in today's Internet. Global multi-Mbps streaming is possible due to their multihop and multipath advantages. Our experimental trials and data also provide valuable insights on the design of a global push-based streaming network. There are strong benefits of using proxy helpers to achieve high bitrate and low delay.

In order to cost-effectively serve a large number of users, video-on-demand (VoD) content providers often place distributed servers close to user pools. These servers have heterogeneous streaming and storage capacities, and collaboratively share contents with each other. A critical challenge is how to optimize movie storage and retrieval so as to minimize system deployment cost due to server streaming, server storage, and network transmission between servers. Using a general and comprehensive cost model, we propose a novel VoD architecture using linear source coding. All the movies are source-encoded once at the repository, by coding k source symbols of movie m to n(m) source-coded symbols. These coded symbols are then distributed to the servers. We optimize n(m) and the number of symbols to retrieve from each server for a request. Our solution approaches asymptotically to global optimum as k increases. We show that even when k is low (say, 30), near optimality can be achieved. Furthermore, the solutions on n(m), symbol distribution and retrieval can be efficiently computed with a linear program (LP). Through extensive simulation, our algorithm is shown to achieve substantially the lowest cost, outperforming traditional and state-of-the-art heuristics by a significantly wide margin (by multiple times in many cases).

In a distributed large-scale video-on-demand (VoD) streaming network, a content provider often deploys local servers close to their users. A movie is partitioned into k segments which the servers collaboratively replicate and retrieve ( k ≥ 1). A critical but challenging problem is how to minimize overall system deployment cost consisting of server bandwidth, server storage, and network traffic among servers. In this paper, we address this problem through jointly optimizing movie storage and retrieval in the server network. We first formulate the optimization problem and show that it is NP-hard. To address the problem, we propose a novel, effective and implementable heuristic termed LP-SR. LP-SR decomposes the optimization problem into two computationally efficient linear programs (LPs) for segment storage and retrieval, respectively. The strength of LP-SR is that it is asymptotically optimal in terms of k, and k is not high to be closely optimal (around 5 to 10 in our study). For large movie pool, we propose a movie grouping algorithm to further reduce the computational complexity without compromising much on the performance. Through extensive simulation, LP-SR is shown to perform significantly the best as compared with other state-of-the-art and traditional schemes, reducing the deployment cost by a wide margin (by multiple times in many cases). It attains performance very close to the global optimum.

Due to unpredictable peer churns (joins, leaves and failures), it is challenging to offer video continuity in peer-to-peer (P2P) live streaming. In this paper, we study a push-based P2P network formed by unreliable nodes (i.e., nodes which may churn at any time). To achieve high stream continuity, the video is encoded into k MDC (Multiple-Description Coded) streams and t FEC (Forward Error Correction) streams. To achieve low delay and reduce error correlation between streams, the k + t streams are pushed to the nodes in parent-disjoint spanning trees. The issue is how to construct these trees minimizing the worst-case node delay. We address the optimization of the spanning trees through problem analysis and algorithmic design. After presenting a model capturing important system parameters and delay components, we formulate the problem and prove that it is NP-hard. We then propose SUN (Streaming with Unreliable Nodes), a simple, adaptive and distributed algorithm which continuously reduces delay through overlay adaptation. Through extensive simulation on real Internet and Internet-like topologies, we show that stream continuity can be achieved with push-based P2P streaming. SUN is effective, achieving low delay and high continuity in the presence of node churns for P2P live streaming.

Using directional antennas in wireless mesh networks (termed DMesh in this paper) is attractive due to its longer coverage range and spatial separation between transmissions of the same channel. However, the connectivity in a DMesh is much lower than its omni-directional counterpart. This makes topology control (through beaming) a critical problem in DMesh. Because topology control coupled with routing decision, their joint optimization is critical to achieve the best performance. In this paper, we consider a multimedia DMesh with a certain traffic demand at each mesh router. We first formulate the joint topology control and routing assignment as an optimization problem and show that it is NP-hard. To address the problem, we propose a novel and efficient heuristic called TORA (Joint Topology Control and Routing Assignment), an ant-colony optimization algorithm which seeks to jointly optimize topology and routing for DMesh. Simulation results based on NS3 show that TORA performs substantially better in terms of loss rate, delay and throughput as compared with a recent scheme.

In a distributed large-scale video-on-demand (VoD), a content provider often deploys local servers close to their users. A movie is partitioned into k segments which the servers collaboratively store and retrieve (k ≥ 1). A critical but challenging problem is how to minimize overall system deployment cost due to server bandwidth, server storage, and network traffic among servers. In this paper, we address this problem through jointly optimizing movie storage and retrieval in the server network. We first formulate the optimization problem to an integer program. To address its tractability, we propose a novel, effective and implementable heuristic. The heuristic, termed LP-SR, decomposes the problem into two computationally efficient linear programs (LPs) for segment storage and retrieval, respectively. The strength of LP-SR is that it is asymptotically optimal in terms of k, and k does not need to be high to achieve near optimality (around 5 to 10 in our study). Through extensive simulation study, LP-SR is shown to perform significantly the best as compared with other state-of-the-art and traditional schemes, reducing the deployment cost by a wide margin (by multiple times in many cases). It attains performance very close to the global minimum cost.

We study providing large-scale video-on-demand (VoD) service to distributed users. In order to achieve scalability in user capacity and reduce the load of the core network, local servers with heterogeneous storage are deployed. Each server replicates the movie segments depending on their access probabilities. Considering the realistic scenario that underlay delay is a function of the total traffic in the link (including cross-traffic), we address two important problems to achieve low user interactive delay: 1) Which segments should each server replicate under the constraints of their capacities to achieve network-wide good locality effect? This is the so-called content replication (CR) problem; and 2) Given a number of remote servers with the requested segment, which one should serve the user? This is the so-called server selection (SS) problem. CR and SS problems couple with each other. In this paper, we propose a simple and distributed algorithm which seeks to jointly optimize CR and SS. The algorithm, termed CR-SS, achieves good caching locality by adaptively replacing segments and selecting servers with a simple lookup. Simulation results on Internet-like topologies show that CR-SS outperforms existing and state-of-the-art approaches by a wide margin, achieving substantially lower user delay.

Wireless mesh networks (WMNs) have been increasingly used to carry multimedia traffic with flow requirements. The performance of multi-radio multi-channel (MRMC) WMNs largely depends on the routing and channel assignment. Because routing and channel decisions are coupled, they need to be jointly optimized to achieve the best performance. This is the so-called routing and channel assignment (RCA) problem, which is known to be NP-hard. There has not been sufficient consideration on joint RCA optimization which takes into account multimedia traffic demands in the network. In this paper, we propose and study CRAFT (Channel and Routing Assignment with Flow Traffic) for MRMC WMNs. CRAFT is distributed, cooperative, computationally efficient and simple to implement. It jointly optimizes routing and channel assignment by using a properly designed objective function to meet the flow demands of the mesh nodes. Simulation results based on NS3 show that CRAFT performs much better than other state-of-the-art schemes in terms of convergence, delay, loss rate and throughput.

There has been much interest in offering multimedia location-based service (LBS) to indoor users (e.g., sending video/audio streams according to user locations). Offering good LBS largely depends on accurate indoor localization of mobile stations (MSs). To achieve that, in this paper we first model and analyze the error characteristics of important indoor localization schemes, using Radio Frequency Identification (RFID) and Wi-Fi. Our models are simple to use, capturing important system parameters and measurement noises, and quantifying how they affect the accuracies of the localization. Given that there have been many indoor localization techniques deployed, an MS may receive simultaneously multiple co-existing estimations on its location. Equipped with the understanding of location errors, we then investigate how to optimally combine, or fuse, all the co-existing estimations of an MS's location. We present computationally-efficient closed-form expressions to fuse the outputs of the estimators. Simulation and experimental results show that our fusion technique achieves higher location accuracy in spite of location errors in the estimators.

Multiview video refers to the simultaneous capturing of multiple video views with an array of closely spaced cameras. In an interactive multiview video streaming (IMVS) system, a client can play back the content in time in a single view, and may observe a scene of interest by switching to different viewpoints. Users independently choose their own view navigation paths through the high-dimensional multiview data. Distributed servers are deployed to collaboratively replicate video content in order to support user scalability. Such a system typically presents challenges in both coding and content replication. In coding, the multiview video must be encoded in order to support efficient view-switching and distributed replication. In content replication, it is important to decide which data blocks to store at each server to facilitate view-switches at any time. In this paper, we co-design a coding structure and a distributed content replication strategy. First, we propose a coding structure based on redundant P-frames and distributed source coding (DSC) frames to achieve efficiency in coding, view switches and content replication. We then propose a heuristic-based distributed and cooperative replication strategy to take advantage of the correlation between the multiple views for resource-effective content delivery. Simulation results show that our coding and replication co-design is cost-effective in supporting IMVS services.

High-resolution video is defining a new age of peer-assisted video streaming over the public Internet. Streaming over 1-Mbps videos in a scalable and global manner presents a challenging milestone. In this work, we examine the feasibility of 1-Mbps streaming through a global measurement study. In contrast to previous measurement studies that crawl commercial applications, we conduct fine-grain, controlled experiments on a configurable platform. We developed and deployed FastMesh-SIM, a novel peer-assisted streaming system that leverages proxies, scalable streaming trees and IP multicast to achieve 1-Mbps streaming at a global scale. With the configurability-enabled design, we are allowed to conduct controlled experiments by varying design decisions under a wide range of operating conditions, and measuring in-depth, finegrain metrics at a per-hop, per-segment level. We collected hundreds of hours of streaming traces that broadcast live TV channels to more than 120 peers and 30 proxies, with a global geographic footprint over 8 different countries. Data analysis demonstrates how a set of design decisions collectively overcome the 1-Mbps barrier. The various operational issues we uncovered provide insights to service providers that want to deploy a commercial system at a larger scale and a higher streaming rate. By comparing theory and practice, we also confirm theory-inspired architectural decisions, and show that our system indeed achieves throughputs close to theoretical upper-bound calculated under many ideal assumptions.

In order to assess service quality of a networked application (such as a streaming session), distributed monitoring servers need to continuously collect application-specific performance metrics in real time. Much of the previous work to address this is to use distributed aggregation tree (DAT) rooted at each monitor. However, this approach often leads to high monitoring delay and network stress. In this paper, we study a highly scalable monitoring network for distributed applications. In the network, there are distributed monitors collecting application performance in two steps: first, client applications report their performance to some proxies by means of a client overlay, and then the proxies report the performance to the distributed monitors using another proxy overlay. We first formulate the problem to construct overlays minimizing monitoring delay. The problem is shown to be NP-hard. Then, we present a simple, efficient, and scalable monitoring algorithm called SMon, which continuously reduces network diameter in real time in a distributed manner. Through simulations and actual experimental measurements with implementation, we show that SMon achieves low monitoring delay, network stress, and protocol overhead for distributed applications.

To provide live streaming service to mobile users, traditionally each user pulls content from a server over his cellular network. In order to overcome the scalability problem of last-hop bandwidth bottleneck, mobile peer-to-peer (P2P) streaming can be used where mobile devices relay their stream received in a multi-hop manner by means of a secondary channel (such as Wi-Fi or bluetooth). We investigate the design of distributed algorithm termed LocalTree, which minimizes the number of broadcasters while meeting a certain video quality requirement under peer churns. We first formulate the problem and show that it is NP-hard, and hence propose LocalTree which achieves robustness similar to an unstructured mesh and low delay similar to a global tree. Simulation results show that LocalTree outperforms other algorithms substantially in terms of number of broadcasters used (by as much as 50%).

The five papers in this special section present effective solutions to tackle interactive multimedia challenges.

In video streaming over multicast network, user bandwidth requirement is often heterogeneous possibly with orders of magnitude difference (say, from hundreds of kb/s for mobile devices to tens of Mb/s for high-definition TV). Multiple description coding (MDC) can be used to address this bandwidth heterogeneity issue. In MDC, the video source is encoded into multiple independent descriptions. A receiver, depending on its available bandwidth, joins different descriptions to meet their bandwidth requirements. An important but challenging problem for MDC video multicast is how to assign bandwidth to each description in order to maximize overall user satisfaction. In this paper, we investigate this issue by formulating it as an optimization problem, with the objective to maximize user bandwidth experience by taking into account the encoding inefficiency due to MDC. We prove that the optimization problem is NP-hard. However, if the description number is larger than or equal to a certain threshold (e.g., if the minimum and maximum bandwidth requirements are 100 kb/s and 10 Mb/s, respectively, such threshold is seven descriptions), there is an exact and simple solution to achieve maximum user satisfaction, i.e., meeting all the bandwidth requirements. For the case when the description number is smaller, we present an efficient heuristic called simulated annealing for MDC bandwidth assignment (SAMBA) to assign bandwidth to each description given the distribution of user bandwidth requirement. We evaluate our algorithm using simulations. SAMBA achieves virtually the same optimal performance based on exhaustive search. By comparing with other assignment algorithms, SAMBA significantly improves user satisfaction. We also show that, if the coding efficiency decreases with the number of descriptions, there is an optimal description number to achieve maximal user satisfaction.

IEEE 802.11 WLANs are becoming more and more popular in homes and urban areas. As compared to traditional WLAN setups (such as in campuses) where knowledgeable network administrators can make centralized decisions on channel selection, access points (APs) in these networks are often deployed by network nonspecialists in an uncoordinated manner, leading to unplanned topologies, interference, and therefore unsatisfactory throughput performance. We consider in this paper a distributed channel assignment algorithm for uncoordinated WLANs, where APs can self-configure their operating channels to minimize interference with adjacent APs. We first formulate the optimization problem on channel assignment which overcomes some of the weaknesses encountered by uncoordinated WLANs. We show that the problem is NP-hard, and propose an efficient, simple, and distributed algorithm termed CACAO (Client-Assisted Channel Assignment Optimization). In CACAO, the clients feed back traffic information to their APs. This leads to better network condition knowledge and better channel assignment decisions at the APs. We conduct extensive simulation study and comparisons using Network Simulator 2 (NS2). Our results show that CACAO outperforms other traditional and recent schemes in terms of TCP and UDP throughputs with a similar level of fairness. Furthermore, it converges quite fast and reduces cochannel interference significantly.

In peer-to-peer (P2P) live streaming using unstructured mesh, packet scheduling is an important factor on overall playback delay. The hybrid pull-push approach has been recently proposed to reduce delay compared to classical pulling method. In this approach, video are divided into substreams and packets are pushed with low delay. There has been little work addressing the scheduling problem on substream assignment. In this paper, we study the scheduling problem on assigning substreams to minimize packet delay. Given heterogeneous contents, delays and bandwidths of parents, we formulate the substream assignment (SA) problem to assign substreams to parents with minimum delay. The SA problem can be optimally solved in polynomial time by transforming it into a max-weighted bipartite matching problem. Simulation results show that our distributed algorithm achieves substantially lower delay as compared with traditional pull and current hybrid pull-push approaches based on greedy algorithm.

IEEE 802.11 WLANs are becoming more and more popular in homes and urban areas. As opposed to traditional WLANs, the access points (APs) in these networks are often deployed by network non-specialists in an uncoordinated manner, leading to unplanned topology, interference and unsatisfactory throughput performance. We consider in this paper a distributed channel assignment algorithm for uncoordinated WLANs, where APs can selfconfigure their operating channels to minimize interference. We propose an efficient, simple and distributed algorithm termed CACAO (client-assisted channel assignment optimization). In CACAO, an AP makes use of the traffic information fed back by its clients to make channel assignment decision. This leads to better knowledge on network environment and better channel assignment decision at the APs. We conduct extensive simulation study and comparisons using network simulator 2 (NS2). Our results show that CACAO out-performs other traditional and recent schemes in terms of throughput with similar level of fairness. Furthermore, it converges quite fast to reduce interference to a low level.

When a content provider (CP) provides peer-to-peer live streaming service, routing decisions based on the knowledge of underlay traffic could lead to much better performance (such as user delay). On the other hand, if the Internet Service Providers (ISPs) provide underlay traffic information to the CP, their overall network cost due to routing inefficiencies could be reduced. There is hence incentive for ISP-CP collaboration. In this paper, we study protocol design and cost-delay trade-off for such collaboration. We consider two ways of collaboration: one on complete information sharing (the case of ISPs playing the role of CP), and the other one on limited information sharing by means of peer ranking (the case of P4P framework through Oracle/iTracker). We first formulate the problem of minimizing network cost subject to a certain delay target, and show that it is NP-hard. For complete information sharing, we propose a centralized heuristic which achieves low network cost given a delay target. For limited information sharing, we present a simple distributed algorithm called Coppice (Collaborative ISP-CP live streaming service). Simulation results show that indeed there is a strong benefit for ISP-CP collaboration, and substantial performance can be gained if ISPs could share network information with CP.

With the penetration of broadband wireless access network and devices, interactive multimedia streaming to handhelds has become a reality. However, it is still challenging to offer such services to a large number of users in a cost-effective manner. With the increase of battery lifetime, memory capacity and processing capability, and the fact that many mobile devices nowadays are equipped with multiple interfaces (3G, Wi-Fi, bluetooth, etc.), we study wireless peer-to-peer (P2P) streaming for scalable interactive streaming. In the network, videos are divided into segments and collaboratively cached and accessed among mobile devices. The major challenge is then which segment to cache at each mobile to achieve efficient access (in terms of low segment access cost). We first formulate the problem of segment caching to minimize segment access cost. We show that the optimization problem is NP-hard and present OPSEC (Optimized Segment Caching), a distributed algorithm which achieves collaborative and efficient segment caching, given heterogeneous caching capacities of the participating users. Using simulation, we show that OPSEC achieves much lower network access cost as compared with some recent schemes for interactive wireless video streaming.

Although peer-to-peer (P2P) streaming can efficiently deliver live video content to large user populations, existing applications often suffer from limited video quality, periodic hiccups, and high delays. To overcome some of the limitations of today's unstructured (mesh-based) designs, we have developed and deployed FastMesh-SIM, a novel P2P streaming system that leverages proxies, push-mechanism and IP multicast to achieve lower playback delay and better stream continuity. Having control over a real P2P streaming system also gives us a rare opportunity to conduct controlled experiments where we vary major design parameters (e.g., push vs. pull delivery, IP multicast support, streaming rate, and video segment size) under a range of operating conditions (e.g., dynamics of peer churn, and different network configurations), while collecting detailed, fine-granular measurements (e.g., the various components of end-to-end delay). Analysis of the measurement data, consisting of seven trials of streaming several live TV channels for more than 100 hours to 140 peers, sheds light on how design decisions and the operating environment affect important performance metrics. Our experiments show that a push-based, proxy-P2P system can achieve low delay and good video quality, though network bottlenecks on long-haul connections can sometimes cause disruptions in a global deployment. Theory-practice gaps observed from the data are also discussed. Large-scale, global experiments are now being carried out.

In this paper we propose an edge-directed error concealment (EDEC) algorithm, to recover lost slices in video sequences encoded by flexible macroblock ordering. First, the strong edges in a corrupted frame are estimated based on the edges in the neighboring frames and the received area of the current frame. Next, the lost regions along these estimated edges are recovered using both spatial and temporal neighboring pixels. Finally, the remaining parts of the lost regions are estimated. Simulation results show that compared to the existing boundary matching algorithm [1] and the exemplar-based inpainting approach [2] , the proposed EDEC algorithm can reconstruct the corrupted frame with both a better visual quality and a higher decoder peak signal-to-noise ratio.

In peer-to-peer (P2P) live streaming using unstructured mesh, packet scheduling is an important factor in overall playback delay. In this paper, we propose a scheduling algorithm to minimize scheduling delay. To achieve low delay, our scheduling is predominantly push in nature, and the schedule needs to be changed only upon significant change in network states (due to, for examples, bandwidth change or parent churns). Our scheme, termed SPANC (Substream Pushing and Network Coding), pushes video packets in substreams and recovers packet loss using network coding. Given heterogeneous contents, delays, and bandwidths of parents of a peer, we formulate the substream assignment (SA) problem to assign substreams to parents with minimum delay. The SA problem can be optimally solved in polynomial time by transforming it to a max-weighted bipartite matching problem. We then formulate the fast recovery with network coding (FRNC) problem, which is to assign network coded packets to each parent to achieve minimum recovery delay. The FRNC problem can also be solved exactly in polynomial time with dynamic programming. Simulation results show that SPANC achieves substantially lower delay with little cost in bandwidth, as compared with recent approaches based on pull, network coding and hybrid pull-push.

Current peer-to-peer (P2P) streaming systems often assume that nodes cooperate to upload and download data. However, in the open environment of the Internet, this is not necessarily true and there exist malicious nodes in the system. In this article, we study malicious actions of nodes that can be detected through peer-based monitoring. We require each node to monitor the data received and to periodically send monitoring messages about its neighbors to some trustworthy nodes. To efficiently store and search messages among multiple trustworthy nodes, we organize trustworthy nodes into a threaded binary tree. Trustworthy nodes also dynamically redistribute monitoring messages among themselves to achieve load balancing. Our simulation results show that this scheme can efficiently detect malicious nodes with high accuracy, and that the dynamic redistribution method can achieve good load balancing among trustworthy nodes.

Peer-to-peer (P2P) streaming has been widely deployed over the Internet. A streaming system usually has multiple channels, and peers may form multiple groups for content distribution. In this paper, we propose a distributed overlay framework (called SMesh) for dynamic groups where users may frequently hop from one group to another while the total pool of users remain stable. SMesh first builds a relatively stable mesh consisting of all hosts for control messaging. The mesh supports dynamic host joining and leaving, and will guide the construction of delivery trees. Using the Delaunay Triangulation (DT) protocol as an example, we show how to construct an efficient mesh with low maintenance cost. We further study various tree construction mechanisms based on the mesh, including embedded, bypass, and intermediate trees. Through simulations on Internet-like topologies, we show that SMesh achieves low delay and low link stress.

Multiple description coding (MDC) has been widely used in media streaming to address the bandwidth heterogeneity issue. That is, the video source encodes data into multiple descriptions. At the receiver end, the streaming quality is proportional to the number of descriptions received. In this paper, we investigate how to assign bandwidth for descriptions in order to make full use of available network bandwidth. We formulate the problem as an optimization problem. We then decompose the problem and address it by an iterative algorithm. We evaluate the algorithm through simulations. Our results show that arbitrary description rates may severely degrade system performance and an optimal solution can make efficient use of network bandwidth.

In this study, we discuss how to provide low-delay peer-to-peer streaming with high video quality by considering mesh design with backup parents. To achieve robustness against peer churns, each peer has a certain number of streaming parents and backup parents. We have designed a distributed algorithm that constructed a low-delay mesh and at the same time achieved a certain stream continuity for the peers. We have conducted extensive simulations to study the performance of our algorithms. The results show that our distributed algorithm achieves a lower source-to-peer delay as compared with a traditional scheme. Our results have shown that peer-to-peer live streaming can be delivered in short delays while providing a high level of quality, despite peer churns and the lack of a centralized planner.

In peer-to-peer (P2P) on-demand streaming applications, multimedia content is divided into segments and peers can seek any segments for viewing at anytime. Since different segments may be of different popularity, random segment caching would lead to a segment popularity-supply mismatch, and hence an uneven workload distribution among peers. Some popular segments may be far from peers, leading to inefficient search and streaming. In this paper, we study optimal segment caching for P2P on-demand streaming. We first state the segment caching optimization problem, and propose a centralized heuristic to solve it, which serves as a benchmark for other algorithms. We then propose a distributed caching algorithm termed POPCA (POPularitybased Caching Algorithm), in which each peer adaptively and independently replaces segments to minimize the popularitysupply discrepancy and the segment distance from peers. Through simulations, we show that POPCA achieves nearoptimal performance, and lower peer workload and segment distance as compared with other schemes.

In live peer-to-peer (P2P) streaming, each peer (child) has a number of supplying parents whose packets have to be scheduled and delivered in time for continuous playback at the child. It is challenging to develop a scheduling algorithm that achieves low delay given heterogeneous bandwidth, propagation delays and available content in all the parents. This paper proposes a novel, simple and effective scheduling scheme called pattern-push. As compared to the traditional mesh-pull, pattern-push does not require continuous buffermap advertisements from the parents, and operates on the packet level instead of the larger segment level. In pattern-push, each parent pushes its packets according to a pattern as indicated by a starting packet ID and a cycle bitmap. Pattern-push requires only minimal feedback from the child, as the pattern only needs to be changed when the child detects a marked change in network conditions or its parents. Simulation results show that pattern-push achieves a significantly lower delay and overhead as compared with both traditional and recent scheduling algorithms proposed in the literature.

Since the quality of compressed video is vulnerable to errors, video transmission over unreliable Internet is very challenging today. Multi-hypothesis motion-compensated prediction (MHMCP) has been shown to have error resilience capability for video transmission, where each macroblock is predicted by a linear combination of multiple signals (hypotheses). B picture prediction is a special case of MHMCP. In H.264/AVC, the prediction of B pictures is generalized such that both of the two predictions can be selected from the past pictures or from the subsequent pictures. The multiple reference picture framework in H.264/AVC also allows previously decoded B pictures to be used as references for B picture coding. In this paper, we will discuss the error resilience characteristics of the generalized B pictures in H.264/AVC. Three prediction patterns of B pictures are analyzed in terms of their error-suppressing abilities. Both theoretical models (picture level error propagation) and simulation results are given for the comparison.

Traditional overlay protocols use unicast connections to form delivery trees. While it can achieve global multicast across the Internet, it is not as efficient as IP multicast. In this paper, we integrate IP multicast into overlay data distribution to improve delivery efficiency. We investigate island multicast where unicast connections are used to connect multicast domains and IP multicast is used within multicast domains. We first explore a centralized island multicast protocol (termed CIM), which relies on a central server to construct a delivery tree. We then study a distributed protocol (termed DIM), where hosts can distributedly join islands and form a delivery tree. We study the key issues in both protocols. We also discuss how to apply these protocols to media streaming applications. We have evaluated both protocols on Internet-like topologies. We have also implemented a prototype for CIM and tested it on PlanetLab. The results show that our approaches can significantly im prove network performance as compared to pure overlay protocols. Our study shows that it is important to consider local multicast capability when designing overlay protocols.

Peer-to-peer (P2P) technology has emerged as a promising scalable solution for live streaming to a large group. In this paper, we address the design of an overlay mesh which achieves low source-to-peer delay, accommodates asymmetric and diverse uplink bandwidth, and continuously improves delay based on an existing pool of peers. By considering a streaming mesh as an aggregation of data flows along multiple spanning trees, the peer delay in the mesh is then its longest delay (including both propagation and scheduling delay) among all the trees. Clearly, such delay can be very high if the mesh is not designed well. In this paper, we propose and study a mesh protocol called Fast-Mesh, which optimizes such delay while meeting a certain streaming bandwidth requirement. Fast-Mesh is particularly suitable for a mildly dynamic network consisting of proxies, supernodes, or content distribution servers. We first formulate the minimum delay multiple trees (MDMT) problem and show that it is NP-hard. Then we propose a centralized heuristic based on complete knowledge, which may be used when the network is small or managed, and serves as an optimal benchmark for all the other schemes under comparison. We then propose a simple distributed algorithm, Fast-Mesh, where peers select their parents based on the concept of power in networks given by the ratio of throughput and delay. By maximizing the network power, our algorithm achieves low delay. The algorithm makes continuous improvement on delay until some minimum delay is reached. Simulation and PlanetLab experiments show that our distributed algorithm performs very well in terms of delay and source workload, and substantially outperforms traditional and state-of-the-art approaches.

Underlay topology information is important to construct efficient overlay networks. To achieve end-to-end network topology inference among a group of hosts, traceroute-like tools are often used. Previously, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, Max-Delta relies on external tools to estimate host coordinates, which incur considerable deployment overhead. In this paper, we consider novel inference schemes with no coordinate estimation. One choice is to select long paths to traceroute. That is, based on existing traceroute results, each host can estimate the distance between another host and itself. It can then select the host with the largest distance between them as the traceroute target. We call this scheme Longest-Path-First (LPF). Similarly, we can define Shortest-Path-First (SPF) inference. The intuition may indicate that LPF performs better than SPF, as longer paths often contain more underlay links and routers, and hence more undiscovered links or routers. However, our simulation results on Internet-like topologies show that SPF can achieve comparable performance with Max-Delta, while LPF performs even worse than a random inference scheme. To explain the results, we analyze the statistics of all-pairs paths between hosts. Our results show that long paths have serious overlaps on underlay links, showing much higher path stress than short paths. We also find that there exist quite a few links only appearing in short paths and seldom appearing in long paths. Therefore, with the same number of traceroutes, SPF can discover more underlay links and routers than LPF. Furthermore, as SPF prefers short paths, a traceroute in SPF sends less probing packets and consumes less network resource than that in LPF. Therefore, SPF is a highly efficient inference scheme with low deployment overhead and low measurement overhead.

Overlay applications have used various tools to measure path properties in order to construct efficient overlay networks. Typical examples include delay measurement, connectivity measurement and residual bandwidth measurement. While different tools have different measurement targets, it is difficult to design general criterion for selecting paths to measure. In this paper, we study path properties and figure out some simple rules for path selection in measurements. We first examine the relationship between path delay and residual bandwidth. Our measurement results indicate that short paths often have high residual bandwidth. We then impose high preference on short paths in traceroute measurements. The results show that traceroute measurements with path preference achieve comparable inference efficiency and much lower overhead as compared to traditional traceroute measurements. Our study suggests that we can preferentially select short paths to measure. This can fulfill various requirements on path properties.

Peer-to-peer (P2P) technology has emerged as a promising scalable solution for live streaming to large group. In this paper, we address the design of overlay which achieves low source-to-peer delay, is robust to user churn, accommodates of asymmetric and diverse uplink bandwidth, and continuously improves based on existing user pool. A natural choice is the use of mesh, where each peer is served by multiple parents. Since the peer delay in a mesh depends on its longest path through its parents, we study how to optimize such delay while meeting a certain streaming rate requirement. We first formulate the minimum delay mesh problem and show that it is NP-hard. Then we propose a centralized heuristic based on complete knowledge which serves as our benchmark and optimal solution for all the other schemes under comparison. Our heuristic makes use of the concept of power in network given by the ratio of throughput and delay. By maximizing the network power, our heuristic achieves very low delay. We then propose a simple distributed algorithm where peers select their parents based on the power concept. The algorithm makes continuous improvement on delay until some minimum delay is reached. Simulation results show that our distributed protocol performs close to the centralized one, and substantially outperforms traditional and state-of-the-art approaches.

Multiple Description Coding (MDC) can be used as an Error Resilience (ER) technique for video coding. In case of transmission errors, Error Concealment (EC) can be combined with MDC to reconstruct the lost frame, such that the propagated error to the following frames is reduced. In this paper we propose a novel algorithm based on a Multi-hypothesis Decoder (MHD), to improve the reconstructed video quality of MDC over packet loss networks. Both subjective and objective results show that MHD can help to achieve a better video quality than a traditional EC algorithm.

Multiple description coding(MDC) is an effectiveerror resilience(ER) technique for video coding. In case of frame loss,error concealment(EC) techniques can be used in MDC to reconstruct the lost frame, with error, from which subsequent frames can be decoded directly. With such direct decoding, the subsequent decoded frames will gradually recover from the frame loss, though slowly. In this paper we propose a novel algorithm usingmultihypothesis error concealment(MHC) to improve the error recovery rate of any EC in the temporal subsampling MDC. In MHC, the simultaneous temporal-interpolated frame is used as an additional hypothesis to improve the reconstructed video quality after the lost frame. Both subjective and objective results show that MHC can achieve significantly better video quality than direct decoding.

Application layer multicast (ALM) has been proposed to overcome current limitations in IP multicast for large-group multimedia communication. We address offering data confidentiality tailored for ALM. To achieve confidentiality, a node may need to continuously re-encrypt packets before forwarding them downstream. Furthermore, keys have to be changed whenever there is a membership change, leading to rekey processing overhead at the nodes. For a large and dynamic group, these reencryption and rekeying operations incur high processing overhead at the nodes. We propose and analyze a scalable scheme called Secure Overlay Multicast (SOM) which clusters ALM peers so as to localize rekeying within a cluster and to limit re-encryption at cluster boundaries, thereby minimizing the total nodal processing overhead. We describe the operations of SOM and compare its nodal processing overhead with two other basic approaches, namely, host-to-host encryption and whole group encryption. We also present a simplified analytic model for SOM and show that there exists an optimal cluster size to minimize the total nodal processing overhead. By comparing with a recently proposed ALM scheme (DT protocol), SOM achieves a substantial reduction in nodal processing overhead with similar network performance in terms of network stress and delay.

We consider using tools like traceroute to infer the underlay topology among a group of hosts. Traditional Max-Delta inference relies on a central server and is not scalable. In this paper, we investigate a distributed inference scheme to support scalable inference. In our scheme, each host joins an overlay tree before conducting traceroute. A host then independently selects paths to traceroute and exchanges traceroute results with others through the overlay tree. As a result, each host can maintain a partially discovered topology. Furthermore, we propose several techniques to reduce the measurement cost, including (a) integrating the Doubletree algorithm to reduce measurement redundancy; (b) setting up a lookup table for routers to reduce traceroute size, and (c) conducting topology abstraction and reducing the computing frequency to reduce computational overhead. In our scheme, the computation loads for target selection are distributed to all the hosts instead of a single server, and the consumption of edge bandwidth at a host is hence limited. We have done simulations on Internet-like topologies and conducted measurements on PlanetLab. The results show that the constructed tree has a low diameter. Furthermore, the proposed improvements can efficiently reduce measurement redundancy, computational overhead and bandwidth consumption.

To construct an efficient overlay network, the information of underlay is important. However, the inference of an underlay topology is not easy. We consider using end-to-end measurement tools such as traceroute to infer the underlay topology among a group of hosts. Since pair-wise traceroutes among hosts take a long time and generate much network traffic, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, Max-Delta relies on a central server to collect traceroute results and to select paths for hosts to measure. It is hence not scalable to large groups. In this paper, we investigate a distributed version of Max-Delta scheme in order to support scalable inference. In our scheme, each host joins an overlay tree before conducting traceroutes. A host then independently selects paths to traceroute and exchanges traceroute results with others through the overlay tree. As a result, each host can maintain a partially discovered topology. We have studied two key issues in the scheme, i.e., how to construct a low-diameter overlay tree and how to reduce bandwidth consumption in measurements. As compared to Max-Delta, our scheme is fully distributed and scalable. In the scheme, each host computes its own traceroute targets, and the computational loads are distributed to all the hosts instead of a single server. Furthermore, each host only exchanges data with a few other hosts and does not need to set up connections with all the other hosts. Simulation results show that the constructed tree has a low diameter and can support quick data exchange among hosts, and that the use of a lookup table for routers can significantly reduce bandwidth consumption in data exchange.

We consider inferring the underlay topology among a group of hosts by traceroute-like end-to-end measurement tools. Since pair-wise traceroutes among hosts take a long time and generate much network traffic, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, there is still high measurement redundancy in Max-Delta. That is, a router may be repeatedly visited in different traceroutes. In this paper, we integrate a previously proposed Doubletree algorithm into Max-Delta to reduce such redundancy. We study two key issues in the integration, i.e., the selection of h (a parameter of Doubletree) and the distribution of the global stop set of Doubletree. We have conducted extensive simulations on Internet-like topologies to evaluate the proposed scheme. The results show that Doubletree can significantly reduce the measurement redundancy and the bandwidth consumption in Max-Delta while introducing a small penalty in the measurement accuracy.

Wireless digital video broadcasting has experienced much success in years with some industrial systems deployed. We study in this paper how to recover lost packets in video broadcasting by means of a free broadcast-based secondary channel (such as IEEE-802.11 or Bluetooth). In our scheme, termed BOPPER (broadcasting with peer-to-peer error recovery), mobile devices collaboratively help each other to recover packet lost by broadcasting to their neighborhood. BOPPER achieves high scalability, low recovery delay, independence of a backward channel and low bandwidth cost. We study how to minimize the total number of retransmissions while achieving a certain level of recovery capability. We first consider the case with global knowledge (in terms of peer connectivity, loss status and pairwise loss rates of all peers) and formulate the problem as a linear program which can be solved efficiently. The result also serves as the optimum for our distributed protocol. We then propose and study a scalable, adaptive and distributed protocol which makes use of local information and message exchange to achieve efficient packet loss recovery. Simulation results show that our distributed scheme achieves close to the optimum with fast convergence time.

Application-layer multicast (ALM, or overlay multicast) has been proposed to overcome limitations in IP multicast. While much measurement work (such as delay or connectivity measurement) has been conducted to build efficient ALM trees, several interesting questions therein are left unclear: (1) What are the measurement costs of the different measurement methods? (2) What is the major improvement to an ALM tree by using a certain measurement method? (3) To achieve the target tree performance, what is the most cost-efficient measurement method? In this paper, we study three representative measurement methods, i.e., delay measurement, connectivity measurement and available bandwidth measurement. We select six typical ALM protocols each adopting at least one of the measurement methods and evaluate their performance on Internet-like topologies. Our study shows that delay and connectivity measurements can effectively reduce end-to-end delay in overlay trees with low measurement costs. Only using delay measurement may lead to a tree consuming much network resource. The use of connectivity and bandwidth measurements can build a tree with low resource consumption.

Provisioning random access functions in peer-to-peer on-demand video streaming is challenging, due to not only the asynchronous user interactivity but also the unpredictability of group dynamics. In this paper, we propose VMesh, a distributed peer-to-peer video-on-demand (VoD) streaming scheme which efficiently supports random seeking functionality. In VMesh, videos are divided into segments and stored at peers' local storage in a distributed manner. An overlay mesh is built upon peers to support random forward/backward seek, pause and restart during playback. Our scheme takes advantage of the large aggregate storage capacity of peers to improve the segment supply so as to support efficient interactive commands in a scalable manner. Unlike previous work based on "cache-and-relay" mechanism, in our scheme, user interactivity such as random seeking performed by a peer does not break the connections between it and its children, and hence our scheme achieves better playback continuity. Through simulation, we show that our system achieves low startup and seeking latency under random user interactivity and peer join/leave which is a crucial requirement in an interactive VoD system.

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%

In recent years, there has been an increasing interest in peer-to-peer (P2P) multimedia streaming. In this paper, we consider constructing a high-bandwidth overlay tree for streaming services. We observe that underlay information such as link connectivity and link bandwidth is important in tree construction, because two seemingly disjoint overlay paths may share common links on the underlay. We hence study how to construct a high-bandwidth overlay tree given the underlay topology. We formulate the problem as building a Maximum Bandwidth Multicast Tree (MBMT) or a Minimum Stress Multicast Tree (MSMT), depending on whether link bandwidth is available or not. We prove that both problems are NP-hard and are not ap-proximable within a factor of (2/3 + epsiv), for any epsiv > 0, unless P = NP. We then present approximation algorithms to address them and analyze the algorithm performance. Furthermore, we discuss some practical issues (e.g., group dynamics, resilience and scalability) in system implementation. We evaluate our algorithms on Internet-like topologies. The results show that our algorithms can achieve high tree bandwidth and low link stress with low penalty in end-to-end delay. Measurement study based on Plan-etLab further confirms this. Our study shows that the knowledge of underlay is important for constructing efficient overlay trees.

Current peer-to-peer (P2P) streaming systems often assume that nodes are cooperative to upload and download data. However, in the open environment of the Internet, this is not true and there exist malicious nodes in the system. In this paper, we study malicious actions that can be detected through peer- based monitoring. We require each node to monitor the data received and to periodically send out monitoring messages about its neighbors to some trustworthy nodes. To efficiently store and search the messages among multiple trustworthy nodes, we organize the trustworthy nodes into a threaded binary tree. The trustworthy nodes also dynamically redistribute the monitoring messages among them to achieve load balancing. Our simulation results show that this scheme can efficiently detect malicious nodes with high accuracy, and that the dynamic redistribution method can achieve good load balancing among the trustworthy nodes.

A home network is a residential local area network, in which users are networking their PCs, laptops or wireless multimedia appliances to use a single residential access point (AP) or gateway connecting to the Internet. As network-capable appliances continue to gain momentum in the home, home networks are becoming increasingly popular. The problem arising from the increasing number of "wireless home" is the interference introduced from neighbor's home networks which leads to throughput dropped precipitously. This problem is different from the traditional channel assignment problem in WLAN. We are considering how home wireless network can self-configure its operating channel to minimize interference with other networks instead of how network administrator assigns channel to different APs. In this paper, we propose a peer-assisted channel assignment algorithm, termed PACA, for home wireless LAN based on local information. A newly power on AP automatically configures itself to operate on a channel with least interference. Mobile node helps other APs to do channel assignment and switching dynamically by providing traffic load information. Our simulation and experimental measurements show that the algorithm reduces interference among different networks and improves user throughput.

Most existing techniques for keyword search in structured peer-to-peer (P2P) networks only support single-keyword exact-match lookups. In practice, however, users often have fuzzy information for identifying these items and tend to submit broad queries. The support of searching based on multiple keywords is hence desirable. In multiple-keyword search, a data item is associated with multiple keywords for storage. A query may also contain multiple keywords. The search result for a query should include all the data items whose storage keywords contain all the query keywords. Traditional DHT-based approaches achieve this by storing a data item (or its index) multiple times, each time with one of its keywords. A query is processed by searching each of the query keywords once. Therefore, the storage cost and search cost are both linear wit the number of keywords. Clearly, it is not efficient in case of a large number of keywords. In this paper, we propose a hybrid structured network called MKey to address this problem. Its backbone is a structured network. Each node in the backbone is also the leader of a cluster formed by non-backbone nodes. Within a cluster, nodes form an unstructured network and cooperate to store data and answer queries. When inserting a data item, multiple copies of its index are stored in a few different clusters. A query is also mapped to multiple clusters, and a flooding search within these clusters is performed. The union of all the search results are returned to users as the final result.

Providing random access function in peer-to-peer on-demand video streaming is a challenging task, due to not only the asynchronous user interactivity but also the unpredictability of group dynamics. In this paper, we propose VMesh, a distributed peer-to-peer video-on-demand (VoD) streaming scheme which efficiently supports random seeking functionality. In VMesh, videos are divided into segments and stored in peers in a distributed manner. An overlay mesh is built upon peers to support jumping forward/backward, pause and restart during playback. Our scheme utilizes the large total storage capacity of peers to improve the segment supply so as to support interactive commands in a scalable manner. Through simulation, we show that our system outperforms a recent work, P2VoD. VMesh also has low segment missing rate under random member join/leave. In addition, the system achieves low joining and seeking latencies which are crucial requirements in an interactive VoD system.

Rate control is a complicated problem in the H.264/AVC coding standard, extra computation is usually needed for the existing rate control schemes to estimate the complexity of frames or macroblocks (MBs). However, during transcoding, information from preceded video could be used to simplify the rate control. In this paper, we propose a low-complexity rate control scheme for transcoding from H.263 to H.264/AVC. The relationship between the rate of the pre-coded video and both the rate and distortion of the transcoded video are studied. By using only the rate information from the preceded video, we introduce a row-layer bit allocation and perform average rate shaping across a row of MBs. Estimation error diffusion is also introduced. The proposed scheme has sufficiently lower computational complexity than other methods as there is no explicit complexity measurement of MBs and complicated parameters updating. Experimental results show the effectiveness of the proposed scheme.

In traditional overlay multicast network, all peers are treated as equal regardless of their importance and contribution to the network. In this paper, we consider that each user may have different cost function depending on his privilege, delay to source, available bandwidth, etc. We propose a fully distributed and scalable protocol to construct an overlay tree to minimize the overall cost of the users. It uses aggregation to account for the total cost of one's descendants, and reduces tree cost by a continuous improvement process. Through simulation, we show that our protocol converges reasonably fast. By comparing with other schemes, our resultant overlay tree offers differentiated services to users by appropriately taking into account individual user cost functions

We present an efficient implementation of motion estimation (ME) for H.264/AVC using programmable graphics hardware. The cost function for ME in H.264/AVC depends on the motion vector (MV) predictor which is the median MV of three neighboring coded blocks. Previous implementations assume no dependency among adjacent blocks, which is not true for H.264/AVC, they also perform unsatisfactorily because of their low arithmetic intensity, which is defined as operation per word transferred. To overcome the dependency problem, we introduce a new implementation which performs ME on block-by-block basis. Moreover, we can adjust the arithmetic intensity easily to optimize the performance on different graphics cards. Experimental results show that our implementation is substantially faster (by 10 times) than our SIMD optimized CPU implementation

Despite the fact that global multicast is still not possible in today's Internet, many local networks are already multicast-capable (the so-called multicast "islands"). However, most application-layer multicast (ALM) protocols for streaming has not taken advantage of the underlying IP multicast capability. As IP multicast is more efficient, it would be beneficial if ALM can take advantage of such capability in building overlay trees. In this paper, we propose a fully distributed protocol called Scalable Island Multicast (SIM), which effectively integrates IP multicast and ALM. Hosts in SIM first form an overlay tree using a scalable protocol. They then detect IP multicast islands and employ IP multicast whenever possible. Through simulations on Internet-like topologies, we show that SIM achieves much lower end-to-end delay and link stress as compared with traditional ALM protocols

Current peer-to-peer (P2P) streaming systems often assume that hosts are cooperative. However, this may not be true in the open environment of the internet. In this paper, we discuss how to detect malicious hosts (e.g., with attacking actions and abnormal behavior) based on their history performance. In our system, each host monitors the performance of its neighbor(s) and reports this to a server. Based on the reports, the server computes host reputation with hosts of low reputation being malicious. A problem is that hosts may lie by submitting forged reports to the server. We hence formulate the reputation computing problem in the presence of lying hosts as a minimization problem and solve it by the traditional Levenberg-Marquardt algorithm. Simulation results show that our scheme can efficiently detect malicious hosts with high accuracy

In traditional mobile streaming networks such as 3G cellular networks, all users pull streams from a server. Such pull model leads to high streaming cost and problem in system scalability. In this paper, we propose and investigate a scalable and cost-effective protocol to distribute multimedia content to mobiles in a peer-to-peer manner. Our protocol, termed collaborative streaming among mobiles (COSMOS), makes use of multiple description coding (MDC) and data sharing to achieve high performance. In COSMOS, only a few peers pull video descriptions through a telecommunication channel. Using a free broadcast channel (such as Wi-Fi and Bluetooth), they share the descriptions to nearby neighbors in an ad-hoc manner. This way reduces greatly the telecommunication cost and cellular bandwidth requirement. As video descriptions are supplied by multiple peers, COSMOS is robust to peer failure. Since broadcasting is used to distribute video data, the protocol is highly scalable to large number of users. By taking turns to pull descriptions, we show through simulation that peers can effectively share, and hence substantially reduce, streaming cost. As peers can often obtain a number of descriptions from nearby neighbors, they enjoy lower delay as compared to a recent scheme CHUM

An improved refinement search method for transcoding from H.263 to H.264/AVC is proposed in this paper. Many existing motion re-estimation methods refine the input motion vector (MV) with a small search range, which is usually input MV biased. Motion estimation (ME) in H.263 usually does not consider the rate required for coding the MV, and hence, the input MV may incur a large cost in H.264/AVC. To overcome this problem, we introduce a refinement search method, called minimum cost tendency search (MCTS), which takes the difference between the cost functions for ME in H.263 and H.264/AVC into consideration. The input MV and the predictor MV are used as two anchor points. The proposed MCTS starts searching from the anchor point with a higher cost to another. Finally, the best point is chosen as the center for further refinement. The performance of MCTS is evaluated by comparing with full search, FME in JM software and refinement scheme using small diamond pattern around the input MV (RSD). Experimental results show the proposed MCTS performs more stable than FME and RSD over a wide range of output video quality.

Multiple description coding (MDC) can be used as an error resilience (ER) technique for video coding. In case of transmission errors, error concealment can be combined with MDC to reconstruct the lost frame, such that the propagated error to the following frames is reduced. In this paper, we propose a new temporal error concealment method named three-loop temporal interpolation (TLTI). TLTI can be well combined with temporal sub-sampling ER methods, such as MDC and alternative motion-compensated prediction. In the simulation, we compare the performance of TLTI with unidirectional motion compensated temporal interpolation (UMCTI). Both visual and quantitive results show that TLTI can achieve a better video quality than UMCTI.

We consider using traceroute-like end-to-end measurement to infer the underlay topology for a group of hosts. One major issue is the measurement cost. Given N hosts in an asymmetric network without anonymous routers, traditionally full N(N-1) traceroutes are needed to determine the underlay topology. We investigate how to efficiently infer an underlay topology with low measurement cost, and propose a heuristic called Max-Delta. In the heuristic, a server selects appropriate host-pairs to measure in each iteration so as to reveal the most undiscovered information on the underlay. We further observe that the presence of anonymous routers significantly distorts and inflates the inferred topology. Previous research has shown that obtaining both exact and approximate topology in the presence of anonymous routers under certain consistency constraints is intractable. We hence propose fast algorithms on how to practically construct an approximate topology by relaxing some constraints. We investigate and compare two algorithms to merge anonymous routers. The first one uses Isomap to map routers into a multidimensional space and merges anonymous routers according to their interdistances. The second algorithm is based on neighbor router information, which trades off some accuracy with speed. We evaluate our inference algorithms on Internet-like and real Internet topologies. Our results show that almost full measurement is needed to fully discover the underlay topology. However, substantial reduction in measurements can be achieved if a little accuracy, say 5%, can be compromised. Moreover, our merging algorithms in the presence of anonymous routers can efficiently infer an underlay topology with good accuracy

Packet loss is inevitable in video multicast. In this paper, we propose and study an effective feedback-free loss recovery scheme for layered video which combines forward error correction (FEC) and stream replication. In our scheme, the server multicasts the video in parallel with FEC packets and a number of replicated delayed (ReD) version of the stream. Receivers autonomously and dynamically join the FEC and ReD streams to repair their losses. On the server side, we analyze and optimize the number of replicated streams and FEC packets to meet a certain residual loss requirement (i.e., error after correction). On the receiver side, we analyze the optimal combination of FEC and ReD packets to minimize its loss. We also present a fast yet accurate approximation algorithm for receiver to make such decision. We show that FEC combined with merely one or two replicated streams can effectively reduce the residual error rate (by as much as 50%) as compared with pure FEC or replication alone. Both subjective and objective video measures confirm that our recovery scheme achieves much better visual quality.

We consider media streaming using application-level multicast (ALM) where packet loss has to be recovered via retransmission in a timely manner. Since packets may be lost due to congestion, node failures, and join and leave dynamics, traditional "vertical" recovery approach where upstream nodes retransmit the lost packets is no longer effective. We therefore propose lateral error recovery (LER). In LER, hosts are divided into a number of planes, each of which forms an independent ALM tree. Since error correlation across planes is low, a node effectively recovers its error by "laterally" requesting retransmission from nearby nodes in other planes. We present analysis on the complexity and recovery delay on LER. Using Internet-like topologies, we show via simulations that LER is an effective error recovery mechanism. It achieves low overhead in terms of delivery delay (i.e., relative delay penalty) and physical link stress. As compared with traditional recovery schemes, LER attains much lower residual loss rate (i.e., loss rate after retransmission) under a certain deadline constraint. The performance can be substantially improved in the presence of some reliable proxies.

Internet applications such as voice over IP and instant messaging require the support of efficient person search. In these applications, a user often has a list of people whom he/she often calls, the so-called "hot list." Traditional structured peer-to-peer networks for file sharing, despite of their support of unique item search, are not efficient for person search. This is mainly because they do not take into account human communication characteristics such as close social network, user-dependent hot list, and high skewness in access popularity. We show in this paper that person search can be much more efficient by taking into consideration of our communication features. Based on Pastry, our system makes use of hot lists in the routing process and clusters people of the same community together in the search graph, thereof creating a "small-world" effect. Simulation results show that our scheme achieves significantly lower search time than Pastry (by as much as 50%).

In wireless sensor networks, estimating nodal positions is important for routing efficiency and location-based services. Traditional techniques based on precise measurements are often expensive and power-inefficient, while approaches based on landmarks often require bandwidth-inefficient flooding and hence are not scalable for large networks. In this paper, we propose and investigate a cost-effective and distributed algorithm to accurately estimate nodal positions for wireless sensor networks. In our algorithm, a node only needs to identify and exchange information with a certain number of neighbors (around 30) in its proximity in order to estimate its relative nodal position accurately. For location-identification, only a small number of nodes (around 10) are needed to have additional GPS capabilities to accurately estimate the absolute position of every node in the network. Our algorithm is shown to have fast convergence with low estimation error, even for large networks.

Abstract — Wireless networks have been widely deployed in recent years to provide high-speed Internet access to mobile users. In traditional IEEE 802.11 wireless LANs, all users directly connect to an access point (AP) and all packets are forwarded by the AP. As a result, the coverage and capacity of the network is limited. If ad hoc mode is adopted in both the AP and mobile nodes, the one hop connections from AP can be extended to multiple hops. Such arhitecture, termed WIANI (Wireless Infrastructure and Ad-Hoc Network Integration) in this paper, is able to extend the network coverage beyond the coverage of APs. Furthermore, the users may take advantage of the ad hoc connections to forward local data and hence alleviating the traffic load through the AP and increasing the network capacity. In this paper, we propose a dynamic load-balancing protocol for WIANI in which all APs and nodes operate in ad hoc mode. Our protocol consists of two parts: the load-balancing zone forming and weighted x−hop routing algorithms. Using simulation, we show that our protocol improves system throughput and reduce packet delivery delay. Index Terms — Multi-hop wireless LAN, load-balancing routing, infrastructure network, ad hoc network, IEEE 802.11

With the availability and penetration of multicast-capable routers, many local networks in today's Internet are multicast-capable. However, achieving global IP multicast is still hindered by many management and technical difficulties. This is because routers interconnecting these local multicast-capable networks, or so-called "islands," are often either multicast-incapable or multicast-disabled. Traditional application-level multicast (ALM) only makes use of unicast connections to form delivery trees and has not fully taken advantage of the local multicast capability of an island. As a result, these protocols are not very efficient. In order to achieve efficient global multicast, we propose and study island multicast (IM) where unicast connections are used between islands while IP multicast is used within islands. We present the detailed mechanisms of the IM centralized approach. IM is simple to implement and is based on minimum spanning tree, and hence is applicable to many-to-many communication. We have implemented the protocol and done real measurements on PlanetLab. We show that our protocol significantly improves network performance (in terms of stress, delay and nodal degrees) as compared to using ALM alone.

Most of the application-layer multicast protocols use end-to-end delay as their primary metric. However, for applications such as stored video delivery, meeting a certain target bandwidth requirement is of primary importance. In this paper, we present a centralized approach on how to build a fast overlay tree based on efficient end-to-end measurements. We first investigate how to infer underlay topology (in terms of connectivity) with low measurement cost. Given N end-hosts, traditionally full N(N-1)/2 traceroutes are needed to accurately determine the underlay topology. We propose a much faster heuristic (max-delta) where a server selects appropriate host-pairs to probe in parallel so as to reveal the most information on the underlay in each round. Given an inferred network topology, we then present the algorithm of fast application-layer tree (FAT), which builds an overlay tree of a certain target bandwidth by estimating possible load on each underlay link. Stimulation results show that almost full measurements are needed to discover completely underlay topology. However, substantial reduction in measurements (by almost an order of magnitude) can be achieved if some accuracy, say 5%, can be sacrificed. As compared to traditional ALM protocols such as Narada and overcast, FAT achieves high bandwidth, low link stress, and low RDP.

Island multicast (IM) has been recently proposed to achieve efficient global multicast, where IP multicast is used within multicast-capable domains (the so-called islands) while overlay connections are used to bridge islands. In the previously proposed scheme, the number of ping measurement to find good bridge-nodes is at least proportional to island size, and a leader needs to keep track of all its members in the island. In this paper, we improve the system scalability by presenting a bridge-node selection algorithm where both the numbers of ping measurements and members to keep track of are greatly reduced to some constants. We further propose a recovery scheme for packets lost across islands. Our scheme uses a number of recovery meshes formed by overlays of some randomly chosen nodes. Simulation results show that our bridge-node selection is efficient in terms of control overhead and achieves scalability with little cost in network stress and delay. As compared to traditional source and parent recoveries, our loss recovery scheme substantially reduces both the recovery delay and bandwidth overhead to achieve reliability.

Multihypothesis motion-compensated prediction (MHMCP) can be used as an error resilience technique for video coding. Motivated by MHMCP, we propose a new error resilience approach named alternative motion-compensated prediction (AMCP), where two-hypothesis and one-hypothesis predictions are alternatively used with some mechanism. Both theory and simulation results show that in case of one frame loss, the expected converged error using AMCP is smaller than that using two-hypothesis MCP.

Periodic broadcasting (PB) schemes are the most promising solution for building large-scale video streaming services. Existing PB schemes are all built around the traditional client-server model. This paper proposes a radically different architecture where only end-user hosts are used to build the PB system, thereby eliminating the need for a central server or even a service provider. Two unique problems pertaining to this decentralized, peer-to-peer architecture is addressed: transmission scheduling and peer synchronization. A new decentralized synchronization algorithm is proposed and results obtained from simulations confirm the architecture's feasibility and performance.

A common issue in video transcoding for heterogeneous network environment is to efficiently and accurately reduce the bit-rate such that the distortion is minimized under a given rate constraint. To convert the bit-rate of an encoded video to match the channel capacity, in general, re-quantization is done on the DCT coefficients with larger quantization step size. Most existing rate control algorithms for video transcoding in the literature calculate quantization parameters (QPs) of macroblocks (MBs) based on a relationship between certain properties of coded video and bit-rate. They reduce the computational complexity by simplifying the R-D model and reusing the statistics information of input video. In this paper, we propose a zero-residue pre-selection (ZRPS) mechanism to select only a portion of MBs to apply the rate control in video transcoding. TMN-8 is used to evaluate the impact of ZRPS. Experimental results show that, as compared to the original TMN-8 rate control scheme, TMN-8 with ZRPS achieves up to 1.60 dB gain, in term of PSNR, and requires less than 50% of the computational complexity compared to TMN-8, depending on the characteristics of the video content

With the penetration and popularity of mobile devices such as pocket PCs and smart-phones, there is an increasing need of low-delay video streaming over wireless channel. Traditionally, UDP (user datagram protocol) is used for video streaming. However, due to unreliable transmission and fluctuating bandwidth of wireless channel, this requires error concealment and recovery mechanisms which greatly increases the complexity and delay of the system. Furthermore, UDP streams are often more difficult to penetrate firewalls. We hence propose using TCP (transmission control protocol) for video streaming in this paper, due to its ease of use, reliability, and flexibility in selecting frames to transmit. After discussing the wireless system architecture under consideration, we present a multi-worker model as implemented at wireless proxy (or encoder) which handles client requests independently. Our model makes use of a technique (selective packet drop) which selectively drops those unimportant frames so as to maintain video quality and low delay in the presence of congestion and fluctuating bandwidth. We have implemented a cellular and WLAN-based surveillance system using the model, and conduct real network measurement on its performance. Our model is simple and effective for mobile clients of heterogeneous bandwidth and computing power. Our results show that using TCP for streaming leads to good video quality in wireless networks.

The Internet nowadays consists of multicast-capable domains or "islands" interconnected by multicast-incapable routers. In order to achieve efficient global multicast, we propose and study island multicast (IM) where overlay connections are used between islands while IP multicast is used within an island. IM may use any existing application-level multicast protocol to build island overlay. We describe how to elect a representative (or leader) in each island for such a purpose. We also present the mechanisms for electing the bridging nodes for overlay connections. Using Internet-like topologies, we show that IM achieves much higher bandwidth efficiency as compared to using application-level multicast alone, at the cost of a small increase in end-to-end delay.

This paper proposes and investigates a simple self-adaptive contention window adjustment algorithm for 802.11 WLAN. We present simulation and analytical results showing that the new algorithm outperforms the standard 802.11 window-adjustment algorithm. Compared with the standard and previously proposed enhancement algorithms, a salient feature of our algorithm is that it performs well both when the number of active stations is large and small that is, in both heavy and light contention cases. Furthermore, the adaptive window adjustment algorithm is simpler than previously proposed enhancement schemes in that no live measurement of the WLAN traffic activity is needed.

Application layer multicast (ALM) has been proposed to overcome current limitations in IP multicast. We address, for the first time, offering data confidentiality in ALM. To achieve data confidentiality, data encryption keys are shared among the multicast group members. Observe that in this system, a node may need to continuously reencrypt packets before forwarding them downstream. Furthermore, keys have to be changed whenever there is a membership change, leading to rekey processing overhead at the nodes. For a large and dynamic group, these reencryption and rekeying operations incur high processing overhead at the nodes. We introduce a scalable scheme called secure overlay tree (SOT) which clusters ALM peers so as to localize rekeying within a cluster and to limit reencryption at cluster boundaries, thereby minimizing the total nodal processing overhead. We describe the operations of SOT and compare its nodal processing overhead with two other basic approaches, namely, host-to-host encryption and whole group encryption. We show that there exists an optimal cluster size to minimize the total nodal processing overhead. SOT achieves substantial reduction in nodal processing overhead with little cost in network performance in terms of network stress and delay.

We consider the delivery of reliable and streaming services using application-level multicast (ALM) by means of UDP, where packet loss has to be recovered via retransmission in a timely manner in order to offer high level of service. Since packets may be lost due to congestion, tree-reconfiguration or node failure, the traditional "vertical" recovery, whereby upstream nodes retransmit the lost packet is no longer effective. We therefore propose and investigate lateral error recovery (LER). In LER, hosts are divided into a number of planes, each of which forms an independent ALM tree. Since the correlation of error among the planes is likely to be low, a node can effectively recover its error "laterally" from nearby nodes in other planes. We employ the technique of global network positioning (GNP) to map the hosts into a coordinate space and identify a set of close neighbors for error recovery by constructing a Voronoi diagram for each plane. We present centralized and distributed algorithm on how to construct the Voronoi diagrams. Using Internet-like topologies, we show via simulations that our system achieves low overheads in terms of relative delay penalty and physical link stress. For reliable service, lateral recovery greatly reduces the average recovery time as compared with vertical recovery schemes. For streaming applications, LER achieves much lower residual loss rate under a certain deadline constraint.

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.

In the traditional IEEE 802.11 wireless LAN using infrastructure mode, all users share the same channel and all packets are forwarded by an access point (AP). As a result, as the number of users in the cell increases, the throughput for each user degrades substantially. If there are users communicating with each other within the cell (as in conferencing or file exchange applications), such throughput degradation could be relieved by making these users communicate through ad hoc connections without going through the AP. The advantages are multi-fold. First, the traffic load at the AP is reduced, hence relieving the contention. Second, ad hoc connections are single-hop, hence improving the channel efficiency. Moreover, ad hoc connections could use different channels, hence multiplying the system bandwidth. In this paper, we propose to integrate the infrastructure mode and the ad hoc mode in a wireless network so as to achieve these advantages. We present a framework for such mixed-mode wireless LAN (termed M/sup 2/-WLAN). In such a network, a node can dynamically switch between the infrastructure mode and the ad hoc mode according to the instruction of the AP, and hence the switching is transparent to the users. Using simulations, we show that M/sup 2/-WLAN can indeed improve system throughput substantially without user's manual configuration.

In recent years, there has been increasing interest in application-level multicast (ALM), where the multicast related functionalities are moved to end-hosts. One of the promising ALM protocols is Delaunay triangulation (DT), which constructs an overlay mesh using 2-D Delaunay triangulation (DT) and makes use of compass routing to forward packets. However, DT protocol as it is originally proposed suffers from several weaknesses: 1) it requires users to input its geographic location, and assumes that the location correlates well with network distance; 2) it tends to form multiple connections across two domains, and hence has a high usage of long delay (interdomain) links; 3) it does not consider the fanout of a host, therefore some less-powerful hosts may serve too many users, leading to degradation of service. To address these problems, we propose to use global network positioning (GNP) for host location estimation and forward delegation to limit the fanout of a host explicitly and efficiently trade off the network resource usage with latency. Using Internet-like topologies, we show that our scheme, as compared to the original DT protocol, can substantially reduce average relative delay penalty, physical link stresses and network resource usage while meeting the processing capability of the hosts in the network.

Optical packet switched (OPS) network is a strong candidate for the future optical Internet. In this paper, we study packet aggregation and deflection routing a employed in OPS networks on the performance of upper layer Internet protocols represented by TCP and UDP. Regarding packet aggregation schemes, we study no aggregation, mixed-flow aggregation, and per-flow aggregation. Our results show that for both TCP and UDP, mixed-flow aggregation significantly decreases the fairness at large aggregation intervals. Both aggregation schemes increase UDP delay jitter. Regarding deflection routing, we show that deflection routing significantly improves TCP throughput in spit of the out-of-order packet delivery. However, the congestion of the deflection path significantly affects the improvement that can be achieved. UDP throughput does not suffer from out-of-order packet delivery, and hence its throughput improvement by deflection routing can be even more prominent. The larger the deflection cost (delay difference between the deflection path and the shortest path) is, the larger UDP delay jitter results. Deflection cost, however, does not affect the throughput and fairness very much for both TCP and UDP.

In video streaming over multicast networks, error recovery is essential to alleviate the effect of packet loss. In this paper, we study a feedback-free recovery scheme which combines the strength of FEC (namely, a parity packet can repair any lost packet) and pseudo-ARQ (namely, incremental recovery). To account for the receiver heterogeneity, the server multicasts layered video streams for the receivers to join. For each layer, the receivers may join dynamically additional multicast channels of FEC and pseudo-ARQ packets to recover local losses. In order to offer quality video, we address the following issues: 1) "menu creation": given a certain maximum error rate after correction (i.e., residual error rate), what is the combination of FEC and pseudo-ARQ packets for the server to send so as to minimize a target receiver's bandwidth; and 2) "menu selection": given the server's menu, what's the combination of FEC and pseudo-ARQ packets for the receiver to join so as to minimize its residual error rate given its local probability, bandwidth and loss pattern. We present the analysis of the scheme and show that our scheme can substantially reduce a receiver's residual error rate as compared with pure FEC or pure pseudo-ARQ alone (by cutting it as much as half).

There has been an increasing interest in recent years to deliver multimedia services over wireless ad hoc networks. Due to the existence of hidden terminal and absence of central control, the MAC protocol as used in the ad hoc networks may lead to channel capture, where some flows monopolize the channel while others suffer from starvation. This greatly degrades system throughput and fairness. After showing that static power control leads to channel capture, we propose and study a distributed dynamic power control scheme to break the capture. Our power control algorithm offers much higher fairness without compromising system throughput by better spatial reuse.

In recent years, there has been an increasing interest to deliver multimedia services over wireless ad hoc networks. Due to the existence of hidden terminal and absence of central control, the medium access control protocol as used in the ad hoc networks may lead to channel capture, where some flows monopolize the channel while others suffer from starvation. As a consequence, the system throughput and fairness are greatly degraded. After showing that static power control leads to channel capture, we propose and study a distributed dynamic power control scheme termed "power adaptation for starvation avoidance" (PASA), which dynamically adjusts the transmission power of a node so as to avoid starvation. PASA is shown to be effective in breaking channel captures, hence improving short-term fairness among contending flows. It is simple, fully autonomous and requires no communication overhead. Via extensive simulations, we show that our power control algorithm achieves much better fairness without compromising system throughput through better spatial reuse. Our experiments with video sequences transmitting over different network topologies show that PASA achieves much better video quality with lower start-up delay and buffer requirement.

In order to cost-effectively accommodate a large number of titles in a video system, a hierarchical storage system can be used. In this system, not-so-popular video files are stored in a tertiary level such as a disk/tape library. These files are transferred, or "staged," to a secondary level composed of magnetic disks before being streamed to the users. This system overcomes the current limitations in using disk/tape libraries to stream videos and resolves the bandwidth difference between staging and streaming. We present, via analysis, a model of the system and determine the minimum storage and bandwidth required, at each level, to meet a given user delay goal. We also analyze a number of system operations pertaining to whether or not a file is played while it is being staged (i.e., stage-streaming) and whether or not the displayed segments are deleted (i.e., trail-deletion). We show that stage-streaming and trail-deletion can achieve substantially lower bandwidth and storage requirements. In order to further increase the streaming and storage scalability, a distributed storage system can be used where multiple local servers are put close to user pools and get their files from one of the libraries through a network. We extend the models developed to such a system and specify the resource requirements to meet a given delay goal.

The use of interactive media has already gained considerable popularity. Interactivity gives viewers VCR controls like slow-motion, pause, fast-forward, and instant replay. However, traditional server-based or client-based approaches for supporting interactivity either consume too much network bandwidth or require large client buffering; and hence they are economically unattractive. We propose the architecture and design of an interactive media proxy (IMP) server that transforms noninteractive broadcast or multicast streams into interactive ones for servicing a large number of end users. For IMP to work cost-effectively, it must carefully manage its storage devices, which are needed for caching voluminous media data. In this regard, we propose a fine-grained device management strategy consisting of three complementary components: disk profiler, data placement, and IO scheduler. Through quantitative analysis and experiments, we show that these fine-grained strategies considerably improve device throughput under various workload scenarios.

In order to offer backward and forward secrecy for multicast applications (i.e., a new member cannot decrypt the multicast data sent before its joining and a former member cannot decrypt the data sent after its leaving), the data encryption key has to be changed whenever a user joins or leaves the system. Such a change has to be made known to all the current users. The bandwidth used for such re-key messaging can be high when the user pool is large. We propose a distributed servers approach to minimize the overall system bandwidth (and complexity) by splitting the user pool into multiple groups each served by a (logical) server. After presenting an analytic model for the system based on a hierarchical key tree, we show that there is an optimal number of servers to achieve minimum system bandwidth. As the underlying user traffic fluctuates, we propose a simple dynamic scheme with low overhead where a physical server adaptively splits and merges its traffic into multiple groups each served by a logical server so as to minimize its total bandwidth. Our results show that a distributed servers approach is able to substantially reduce the total bandwidth required as compared with the traditional single-server approach, especially for those applications with a large user pool, short holding time, and relatively low bandwidth of a data stream, as in the Internet stock quote applications.

Layered multicast is an efficient technique to deliver video to heterogeneous receivers over wired and wireless networks. We consider such a multicast system in which the server adapts the bandwidth and forward-error correction code (FEC) of each layer so as to maximize the overall video quality, given the heterogeneous client characteristics in terms of their end-to-end bandwidth, packet drop rate over the wired network, and bit-error rate in the wireless hop. In terms of FECs, we also study the value of a gateway which "transcodes" packet-level FECs to byte-level FECs before forwarding packets from the wired network to the wireless clients. We present an analysis of the system, propose an efficient algorithm on FEC allocation for the base layer, and formulate a dynamic program with a fast and accurate approximation for the joint bandwidth and FEC allocation of the enhancement layers. Our results show that a transcoding gateway performs only slightly better than the nontranscoding one in terms of end-to-end loss rate, and our allocation is effective in terms of FEC parity and bandwidth served to each user.

Multicast is an efficient technique for delivering data to a large group of users. For some applications, offering multicast security is an important issue. In such a system, a new member should not be able to decrypt the multicast data sent before its joining and a former member should not be able to decrypt the multicast data sent after its leaving. Traditional approaches generally focus on reducing the re-key messages for a single server. However, these approaches still lead to large exchange overhead when the group is large. We consider a distributed server network in which the user pool is split into multiple groups and served by multiple servers. Given the user traffic, there is a trade-off between the amount of re-key messaging and the total data bandwidth needed. We present a simple model for the system and study how the total bandwidth (including the re-key messaging and data traffic) can be minimized by optimizing the number of servers in the network. As the underlying user traffic is dynamic, a server should be able to split and merge user groups to minimize its total bandwidth. We propose a scheme for such a purpose. We show that a distributed server network is able to reduce substantively the total bandwidth required in the system as compared to the traditional scheme.

Video applications, such as video-on-demand systems, in general have bandwidth and delay constraints. Such QoS requirements can no longer be guaranteed when video is transmitted with the traditional shortest-path routing over a bandwidth-limited network such as the Internet. We propose multipath routing algorithms for video unicast so as to meet a certain bandwidth requirement with minimum start-up delay (and hence low user buffer requirement). We first formulate the problem which in its most general form is difficult to solve. However, for the special case where the network links are of unit capacity, we present an exact solution using a k-shortest-disjoint paths algorithm with video rescheduling in the source. For the most general case, we propose an efficient heuristic based on max-flow and shortest path algorithms. The complexity of such an algorithm is only O(|V|/sup 3/), where |V| is the number of nodes in the network. Extensive simulation results show that the multipath approach meets the bandwidth requirement with a delay close to that of shortest-path routing.

The multicast routing and wavelength assignment (MC-RWA) problem is generally studied with the objective of maximizing the number of multicast groups admitted, or equivalently, to minimize the call (or session) blocking probability given a certain number of wavelengths. While this approach is sound, a better objective is to maximize the total number of users served (i.e., minimizing the user blocking probability) by allowing part of a multicast group to be admitted. We present for the first time a formulation of the MC-RWA problem with such an objective. The formulation is a nonlinear integer program, which in general is complex to solve. We therefore propose a heuristic algorithm based on linear programming (LP). We further develop a simpler MAX-FIRST algorithm, which achieves almost the same performance as the LP algorithm. These algorithms are for static MC-RWA, where the multicast trees are predetermined and cannot be changed during the wavelength assignment. We extend the algorithms to dynamic MC-RWA, where new multicast trees can be built for unserved groups. We finally present upper and lower bounds on the user blocking probability for the static MC-RWA.

Multicast is an efficient technique to deliver video content over a network. We consider such a multicast system to serve both wireless and wireline users when there are errors over the wired network and the wireless hop. Since packets are likely to be dropped in the wired networks while bit errors are more likely over the wireless hop, a combination of both packet-level and byte-level FEC is required to recover these errors. Given the estimated error and bandwidth characteristics reported by end users, the server needs to allocate optimally the packet-level and byte-level FEC to achieve maximum video quality. We study two schemes pertaining to whether or not the wireless gateway is able to transcode the video packets from the wired network before forwarding them to the wireless users. We first develop a model to analyze the system; and then propose an efficient algorithm for the FEC computation. We finally compare the schemes in terms of the optimal parameters used in the FEC, and the video quality achieved.

True-VOD provides an interactive on-demand (i.e., virtually zero start-up delay) video service by allocating each user a dedicated stream. Such a streaming technique, however, cannot scale up to accommodate a large number of users. A more scalable solution is to use multicasting and client buffering. In this paper, we propose a client-initiated (client-pull) on-demand scheme in which short unicast streams are used to "merge" users onto the existing multicast streams by means of pre-buffering. The scheme is observed to trade-off some bandwidth with lower buffer requirement as compared with a previously proposed scheme. We then propose and analyze a server-initiated (server-push) scheme for on-demand interactive applications. The scheme is shown to offer a service level similar to true-VOD with substantially (many times) lower bandwidth, even with high user interactivity (e.g., averaged ten VCR commands/viewing).

In near video-on-demand (near-VoD), requests for a video title are grouped together (i.e. batched) and are served with a single multicast stream, thereby increasing the number of concurrent users which can be supported by the system. Since users may not be able to tolerate the delay incurred by batching and hence cancel their requests, a batching policy should be designed so as to achieve low user loss and high revenue (given by the total pay-per-view collected over a long period of time across all movies). We propose an adaptive batching policy which offers users low delay at low arrival rate, and gates the allocation of the channels at high rate. Such adaptivity is achieved by the use of a simple "token-tray" (TT) scheme which governs when a stream may be allocated to a movie. In assigning a movie to a stream, we propose a weight function which depends on the user queuing-time and its pay-per-view (hence the term "weighted queuing-time") (WQT). By comparing our batching policy (TT/WQT) with a number of traditional ones (FCFS, forced-wait, batch-size-based scheme, etc.), our scheme is shown to achieve the highest revenue and lowest loss rate even when the arrival rate changes, with the user loss rate across the movies being fairly uniform, and the user delay being fairly low even at high arrival rate.

In a near video-on-demand (near-VOD) system, requests for a movie arriving in a period of time are grouped (or "batched") together and served with a single multicast stream. We consider providing near-VOD services when there is a cost associated with using a network multicast channel. We address the tradeoff between system profit, given by the total pay-per-view collected minus the total channel cost, and user delay or user loss (due to reneging). We first analyze and compare the tradeoff of two traditional "basic" schemes, namely, the window-based schemes in which a maximum user delay can be guaranteed, and the batch-size based scheme in which system profit can be guaranteed. By combining these basic schemes, we present a scheme which can adaptively balance system profit and user delay when the underlying request rate fluctuates. We then consider the case in which delayed users may renege and determine how system profit can be maximized by sizing the batching period given user's reneging behavior. We show that maximizing profit can lead to excessively high user loss rate, especially when the channel cost is high and users are not very patient. Therefore, a shorter suboptimal batching period should be used for this case in reality. We finally introduce schemes which are able to offer high profit or low user loss when the underlying arrival rate fluctuates.

In an on-demand video system, the video repository generally has limited streaming capacities and may be far from the users. In order to achieve higher user capacity and lower network transmission cost, distributed servers architecture can be used, in which multiple local servers are placed close to user pools and, according to their local demands, dynamically cache the contents streamed from the repository. We study a number of caching schemes as applied in the local servers depending on whether the repository is able to multicast movie contents to the local servers or not, and whether the local servers can exchange their cached contents among themselves or not. Our caching schemes keep a circular buffer of data for the movie requested, and hence movies are partially cached. By adjusting the size of the buffer, such caching is able to achieve better tradeoff between network channels and local storage as compared to the traditional caching in which a movie is treated as an entity. For each caching scheme, we study the tradeoff between the local storage and the network channels, and address how the total cost of the system can be minimized by appropriately sizing the buffer. As compared to a number of traditional operations (request batching and multicasting, true-VOD, etc.), we show that distributed servers architecture is able to achieve much lower system cost to offer on-demand video services.

In a cellular network, a fixed number of channels is normally assigned to each cell. However, under this scheme, the channel usage may not be efficient because of the variability in the offered traffic. Different approaches such as channel borrowing (CB) and dynamic channel allocation (DCA) have been proposed to accommodate variable traffic. In this paper, we expand on the CB scheme and propose a new channel allocation scheme-mobile-assisted connection-admission (MACA) algorithm-to achieve load balancing in a cellular network. In this scheme, some special channels are used to connect mobile units from different cells; thus, a mobile unit, which is unable to connect to its own base station because it is in a heavily-loaded "hot" cell, may be able to get connected to its neighboring cold cell's base station through a two-hop link. We find that MACA can greatly improve the performance of a cellular network.

Layered video is a video compression technique to encode video data in multiple layers. It typically consists of a base layer and additional layers that provide enhanced video quality. The multicasting operation of a layered video may need to satisfy: (i) bounded end-to-end delay from a source to each receiver, (ii) minimum total cost, and (iii) minimum delay jitter between the various video streams received by the receivers. Because different nodes may request different video quality and because of limited bandwidth on the network's links, different layers of video data may reach their destinations over different distribution trees, and not all receivers may receive all of their requested layers. The problem of computing such data distribution paths is NP-complete, which means that no optimal solution method is available. This paper presents a new heuristic algorithm called LVMSR. With O(Rn/sup 2/) time complexity and O(R/sup 2/) message complexity, where n is the number of nodes in the network and R is the receiver group size. Our simulation results show that the multicast data paths computed by our algorithm can always satisfy the delay constraint with reasonably small total cost.

A packet scheduling scheme is an important component of a network node. The choice of a scheme dictates the allocation of network resources among contending flows of the network. In this paper we study packet scheduling in the context of active networks. In an active network, intermediate nodes, called active nodes, can perform customized computations on every packet. Programmability in active networks is achieved by having active packets carry either programs or references to programs that are injected into the active nodes offline. As each packet arrives at an active node, the node executes the program associated with the packet and then routes the packet to the next node. Traditionally, packet scheduling schemes are used to allocate a single resource fairly. This cannot be directly applied to active nodes because active nodes contain multiple resources, such as CPU and bandwidth. Moreover, these resources are inter-dependent. Hence, allocating one resource fairly does not entail allocating the other resources fairly. We describe a simple packet scheduling algorithm to allocate multiple resources fairly in an active node. Using simulations, we show that the algorithm effectively allocates both CPU and bandwidth resources fairly among the contending flows.

In a cellular system, if there are too many data users in a cell, which we refer to as a hot cell, data may suffer large delay, and system's quality of service (QoS) may degrade. A dynamic channel-allocation scheme assigns more channels to those hot cells under centralized control (CC). In mobile-assisted data forwarding (MADF), we add an ad-hoc overlay to the fixed cellular infrastructure and special channels-called forwarding channels-are used to connect users in a hot and its surrounding cold cells without going through the hot cell's base station. The forwarding-channel management in MADF is done by the mobile units themselves to relieve the load on the CC. We find that, using MADF, under a certain delay requirement, the system performance can be greatly improved.

In near video-on-demand, requests for the same movie arriving within a period of time are grouped together (i.e., batched) and served with a single multicast stream; thereby reducing the bandwidth requirement compared with the unbatched case. We consider here that the use of a multicast channel comes with a cost. Since delayed users may cancel their requests while being batched, this uncollected revenue has to be appropriately balanced with the channel usage cost in order to achieve maximum profit. We address profit issues for a number of batching schemes. In the window-based schemes, users are batched for a fixed period of time before they are served; in the batch-size based scheme, users are served once a certain number of them are collected. We study the system profit in terms of user reneging behavior, movie popularity, and multicast channel cost. By combining the advantages of the window-based and the batch-size based schemes, we introduce a scheme which adapts to the fluctuating request rate to achieve high profit.

In an on-demand video system, the repository servers storing all the video contents generally have limited streaming capacities and may not be co-located with the users. To achieve higher user capacity and lower network transmission cost, the distributed servers architecture can be used. In such a system, multiple local servers are placed close to the user pools and, according to their local demands, the servers dynamically cache the contents streamed from the repository. We study in this paper a number of caching schemes by considering whether the local servers can exchange their cached contents among themselves or not. All the caching schemes keep a sliding window worth of data for each video being displayed; hence a video can be partially stored. We study the trade-off between the storage capacity required and the network channel used in each scheme, and address how the system cost can be minimised by appropriately sizing the window. We also show the cost advantage in using such a system over a system of request batching and multicasting in providing distributed video services.

In an on-demand video system, requests for a video file arriving within a period of time can be batched together and served with a single multicast stream; thereby reducing the bandwidth requirement compared with the unbatched case. We study various batching schemes to meet delay and profitability requirements-in the window-size based and moving-average schemes, maximum and average user delay respectively are guaranteed; in the batch-size based scheme, minimal profitability is maintained; in the adaptive scheme, both the delay and profitability can be balanced. We analyse and compare these schemes in terms of the delay experienced by the users, and their profitability (the number of users in a batch, the number of concurrent streams, etc.).