The remarkable success of contrastive-learning-based multimodal models has been greatly driven by training on ever-larger datasets with expensive compute consumption. Sample selection as an alternative efficient paradigm plays an important direction to accelerate the training process. However, recent advances on sample selection either mostly rely on an oracle model to offline select a high-quality coreset, which is limited in the cold-start scenarios, or focus on online selection based on real-time model predictions, which has not sufficiently or efficiently considered the noisy correspondence. To address this dilemma, we propose a novel Differential-Informed Sample Selection (DISSect) method, which accurately and efficiently discriminates the noisy correspondence for training acceleration. Specifically, we rethink the impact of noisy correspondence on contrastive learning and propose that the differential between the predicted correlation of the current model and that of a historical model is more informative to characterize sample quality. Based on this, we construct a robust differential-based sample selection and analyze its theoretical insights. Extensive experiments on three benchmark datasets and various downstream tasks demonstrate the consistent superiority of DISSect over current state-of-the-art methods. Source code is available at: https://github.com/MediaBrain-SJTU/DISSect.

Ultrasound imaging plays a significant role in the early diagnosis of thyroid nodules. However, ambiguous nodule boundaries and their similarity to surrounding tissue cause challenges. These cause high false positive rates, reducing the diagnostic efficiency of ultrasound imaging. Although recent advancements in deep learning such as Faster R-CNN and YOLO, have shown progress, they still have limitations in handling imbalanced datasets and noise during real-time detection. To solve these challenges, our team proposes a novel deep learning framework integrating mixup data augmentation and negative sample utilization. This approach reduces false positives while maintaining a stable true positive detection rate. The method employs a one-stage-based object detection model as the baseline. The proposed framework based on that can improve the model’s robustness against background noise and optimize mixup parameters to enhance generalization. The experimental results demonstrate our approach significantly reduces false positive rates by 40% (from 50% to below 10%). In the meantime, it can stabilize high true positive rates above 80% in thyroid nodule detection during testing. This improvement highlights the framework can balance diagnostic sensitivity and specificity. The framework provides an efficient solution for detecting nodules in thyroid ultrasound imaging and has great potential to enhance diagnostic accuracy.

Accurate assessment of intestinal cleanliness is essential for effective colonoscopy, but manual scoring with the Boston Bowel Preparation Scale (BBPS) remains subjective and labor-intensive. In this study, we propose a novel, fully automated multi-stage pipeline for objective BBPS-based bowel preparation assessment in colonoscopy videos. Our approach utilizes deep image classifiers, enhanced by a hierarchical sequence of binary classification tasks, to assign precise frame-level BBPS scores. From the resulting sequence of scores, we extract statistical and temporal features to train machine learning regression models for video-level BBPS prediction. Extensive experiments demonstrate that our pipeline achieves robust, reproducible, and granular video-level bowel cleanliness assessment, outperforming standard multi-class models at the frame level and offering a scalable tool for large-scale endoscopic quality analysis.

Accurate sizing of colorectal polyps is essential for malignancy risk assessment and surveillance planning. However, both visual estimation and current instrument-based aids often suffer from variability or workflow disruption. Recent AI-based approaches typically rely on reference objects, camera calibration, or depth networks with suboptimal accuracy in endoscopic imagery. We present a calibration-free pipeline that segments the polyp and then couples ViTCAN-Depth, a monocular metric-depth model that fuses parallel CNN and Vision-Transformer encoders via channel-attention gating, with Depth–Pixel Linear (DPL), a lightweight module that converts pixel diameter and depth into real-world diameter using a learned scalar, eliminating camera calibration and reference objects. ViTCAN-Depth outperforms state-of-the-art CNN- or ViT-based metric-depth networks on the C3VD synthetic benchmark, and yields higher-fidelity depth maps on real colonoscopy images. Across 78 polyps from five independent cohorts, the system achieves a mean absolute error of 0.67mm (RMSE=0.88mm), suggesting its potential for integration into clinical workflows.

In colonoscopy, wireless capsule endoscopy (WCE) is widely used since it is more physically friendly for patients than standard endoscopy. WCE is a low-risk and effective clinical operation for the small intestine endoscopy, which is less accessible to standard endoscopy. However, reviewing WCE videos can be challenging as it is time-consuming and requires considerable expertise. WCE videos are usually captured at a low resolution and partial frames are filtered out due to hardware limitations. Additional challenges arise from the diversity and complexity of gastrointestinal (GI) diseases. Moreover, inadequate clinic attention can cause clinical errors. Consequently, physicians are often overburdened with work. This paper presents a convolutional neutral networks (CNN) based framework to assist clinicians to review the WCE videos. The framework combines both image classification and object detection results to provide comprehensive results for disease detection in WCE videos. For disease classification, ResNet-50 was selected when experiments were conducted on the dataset. For disease detection, YOLO-X is employed on the images labelled with bonding boxes. Enhanced with an offline hard example mining (offline-HEM) procedure and fine-tuning on hyper-parameters, this framework can achieve high sensitivity for disease instances while maintaining acceptable specificity for false positives in video tests.

Dental caries, the most prevalent oral disease, poses a significant healthcare challenge. Deep Neural Network (DNN)-based object detection techniques offer promising solutions to improve the efficiency of dental caries diagnosis. It is widely acknowledged that the performance of DNN models heavily relies on the availability of sufficient and accurately labeled data. The collection and annotation of dental X-ray images encounter obstacles due to privacy concerns and the requirement for specialized expertise. Consequently, the limited access to labeled dental image datasets restricts the potential of DNNs in supporting oral and dental healthcare. Self-Training (ST) is a semi-supervised machine leaning approach that addresses this problem to a large extent. It repeats the procedures of training a model on the labeled dataset, and then applying it to generate pseudo labels on the unlabeled dataset, and further using the combined data with the original and pseudo labels to train new models. However, the latent errors of the pseudo labels can arise and even be amplified throughout the ST pipeline, which leads to a significant performance decline for DNN models. In this paper, we propose a Greedy algorithm-based Self-Training (Greedy-ST) pipeline to address this problem. At each iteration, the Greedy-ST selects an optimal confidence threshold to generate predictions as pseudo labels, and uses static fine-tuning (SFT) and dynamic fine-tuning (DFT) to refine them. Experimental results demonstrate that by utilizing the pseudo labels generated by the Greedy-ST pipeline, the selected baseline model achieves improved performance compared to using the pseudo labels generated by the vanilla ST approach.

The advancement of deep learning techniques has significantly improved abnormality detection in gastrointestinal (GI) endoscopy. However, this imaging process comes with challenges due to the complex nature of GI abnormalities. The wide variety of abnormalities in terms of type, color, texture, shape, and scale of lesions makes it difficult to accurately detect them in different scenarios. Furthermore, the presence of multiple types of lesions within the same region create complex scenarios that complicate abnormality detection. Additionally, differentiating early-stage cancers from non-cancerous lesions is a significant challenge even for experienced professionals. The simultaneous identification of cancers, particularly early-stage ones, and non-cancerous lesions within the same region remains a challenging issue in GI endoscopy imaging. In this study, we discover that multiple types of lesions exhibit a scale-sensitive characteristic that can be leveraged by multi-level feature-based deep learning models. Hence, we propose the use of a multi-level and multi-scale attention (MLMSA) neck module in a deep learning network. The MLMSA module utilizes multiple levels of features extracted from the backbone network to generate processed multi-level features that assist the detection head. By integrating the MLMSA module into the deep learning framework, our goal is to enhance the detection and differentiation of lesions, particularly the early-stage cancer, thereby advancing the capabilities of GI endoscopy imaging. Our experiment results show that integrating the MLMSA module leads to a significant improvement in the detection of GI abnormalities, providing compelling evidence for the enhanced performance achieved through the utilization of the MLMSA module in our approach.

A gastroscopy involves examining the upper digestive system using a flexible tube equipped with a small camera. Generally, it is performed to determine the cause of digestive symptoms, such as vomiting blood, stomach pains, and difficulty swallowing. Though this procedure has been performed since the mid-19th century, and various measures have been implemented to make it easier and less invasive, it is still not risk-free. One of the major complications is esophagus perforation, and most of them happen during the insertion of the gastroscopy. Therefore, it is necessary to develop an effective method for evaluating the performance of the operator. One appropriate metric is the time interval between the mouth and esophagus during the intubation. In this paper, we propose a gastroscopy video processing system based on deep learning to automatically evaluate the mouth-esophagus passage time. In this system, a Convolutional Neural Network (CNN) based model is adopted to detect the mouth and esophagus, track the timestamps of the last appearance of the mouth and the first appearance of the esophagus, and calculate the interval between those appearances. Our system is capable of dealing with abnormal circumstances that can occur during a procedure, as well as reporting accurate results. Experiment results show that our best model achieves an accuracy of 88.92% on image dataset, and an accuracy of 99.86% on videos for the mouth-esophagus passage time.

Chest radiography (X-ray) is a critical imaging modality for the diagnosis of thorax diseases. Automated classification of chest X-rays has enormous potential to benefit diagnostic decision making. Most existing models are designed to consider a single-view chest X-ray image, mostly the frontal view, failing to utilize the complementary information provided by the lateral view when available. In clinical practice, radiologists often examine both frontal and lateral views to gather more information for diagnosis. Thus, a well-designed model should take advantage of the paired views to enhance the classification results. To this end, we present a novel dual-view deep learning framework to enhance the classification that uses an intermediate bi-directional fusion architecture to exploit the intrinsic spatial correlation registered between the two views. In particular, we design two different modules, a vertical alignment fusion and a 3D reconstruction fusion, that can effectively extract and fuse important features from both input streams to generate a pair of recalibrating signals, which are then used to amplify the pertinent parts while suppressing the irrelevant segments of the feature map in each stream. We evaluate our proposed methods extensively on two large public chest X-ray datasets, CheXpert and MIMIC-CXR-JPG. Experiment results show that our methods can effectively improve the classification results over fine-tuned baselines and other state-of-the-art methods, demonstrating the benefit of exploiting the spatial correlation between the paired views in the model. We also find that our fusion methods significantly outperform the early fusion and late fusion models, highlighting the need to capture the spatial correlation across different intermediate feature layers.

Colorectal cancer (CRC) is a common and lethal disease. Globally, CRC is the third most commonly diagnosed cancer in males and the second in females. The most effective way to prevent CRC is through using colonoscopy to identify and remove precancerous growths at an early stage. The detection and removal of colorectal polyps have been found to be associated with a reduction in mortality from colorectal cancer. However, the false negative rate of polyp detection during colonoscopy is often high even for experienced physicians. With recent advances in deep learning based object detection techniques, automated polyp detection shows great potential in helping physicians reduce false positive rate during colonoscopy. In this paper, we propose a novel anchor-free instance segmentation framework that can localize polyps and produce the corresponding instance level masks without using predefined anchor boxes. Our framework consists of two branches: (a) an object detection branch that performs classification and localization, (b) a mask generation branch that produces instance level masks. Instead of predicting a two-dimensional mask directly, we encode it into a compact representation vector, which allows us to incorporate instance segmentation with one-stage bounding-box detectors in a simple yet effective way. Moreover, our proposed encoding method can be trained jointly with object detector. Our experiment results show that our framework achieves a precision of 99.36% and a recall of 96.44% on public datasets, outperforming existing anchor-free instance segmentation methods by at least 2.8% in mIoU on our private dataset.

Cracks are important indicators of pavement structural and operational conditions. Early pavement crack detection and treatments can help extend pavement service life, reduce fuel consumption, and improve safety and ride quality. Pavement distress surveys have traditionally been performed manually by visually inspecting the roads, which is labor-intensive and time-consuming. Therefore, computer-vision-based automated crack detection has great practical significance in pavement maintenance and traffic safety. Traditional image processing techniques are sensitive to noise in images and are thus likely to miss detecting some cracks due to the crack texture variety, complex lighting conditions, and various similar but irrelevant objects on the road. This paper adopts and enhances DeepLabv3+, a popular deep learning framework for semantic image segmentation, for road pavement crack detection. We propose a multi-scale attention module in the decoder of DeepLabv3+ to generate an attention mask and dynamically assign weights between high-level and low-level feature maps. Compared with fixed weights across different features, the dynamic weights strategy can assign more reasonable weights to different feature maps. Ablation experiments show that the attention mask can effectively help the model better combine multi-scale features and generate more accurate pavement crack segmentation results. The proposed method achieves state-of-the-art results on three benchmarks, including Crack500, DeepCrack, and FMA (Fitchburg Municipal Airport) datasets. We further test it on pavement crack images captured by smartphones, and the results show that it provides a viable approach to road pavement crack segmentation in practice with excellent performance.

Esophagogastroduodenoscopy (EGD) is a common procedure that visualizes the esophagus, stomach, and the duodenum by inserting a camera, attached to a long flexible tube, into the patient's mouth and down the stomach. A comprehensive EGD needs to examine all gastric locations, but since the camera is controlled manually, it is easy to miss some surface area and create diagnostic blind spots, which often result in life-costing oversights of early gastric cancer and other serious illnesses. In order to address this problem, we train a convolutional neural network to classify gastric locations based on the camera feed during an EGD, and based on the classifier and a triggering algorithm we propose, we build a video processing system that checks off each location as visited, allowing human operators to keep track of which locations they have visited and which they have not. Based on collected clinical patient reports, we consider six gastric locations, and we add a background class to our classifier to accomodate for the frames in EGD videos that do not resemble the six defined classes (including when the camera is outside of the patient body). Our best classifier achieves 98 % accuracy within the six gastric locations and 88 % accuracy including the background class, and our video processing system clearly checks off gastric locations in an expected order when being tested on recorded EGD videos. Lastly, we use class activation mapping to provide human-readable insight into how our trained classifier works.

A colonoscopy is an endoscopic examination that visualizes the colon by inserting a camera, attached to a long, flexible tube, into the patient’s anus and up the rectum. One significant landmark of a colonoscopy is when the endoscope begins to withdraw after reaching the farthest point in its path, the cecum. In this paper, we demonstrate that the withdrawal point is closely related to the sighting of local anatomical features in the cecum, specifically the ileocecal valve. The withdrawal point allows us to determine the amount of time the endoscope spends withdrawing, which is an important indicator of the quality of a colonoscopy. In this paper, we present a colonoscopy video processing system that detects the withdrawal point in real time by using a convolutional neural network to classify between ileocecal valves and other images. The system then processes the raw classifier output to determine the withdrawal point. We collect a novel dataset of colonoscopy images and videos to train and evaluate the classifier, as well as to evaluate the video processing system. We explore a range of state-of-the-art classifier architectures, and our best model achieves 99.6% accuracy on the image-level dataset. Then, we provide human-readable insight into our classifier using class activation mapping and principle component analysis. Using this classifier and optimized parameters, our video processing system achieves 70.5% accuracy (± 10s) on the video-level dataset.

It is a challenging task to predict financial markets. The complexity of this task is mainly due to the interaction between financial markets and market participants, who are not able to keep rational all the time, and often affected by emotions such as fear and ecstasy. Based on the state-of-the-art approach particularly for financial market predictions, a hybrid convolutional LSTM Based variational sequence-to-sequence model with attention (CLVSA), we propose a novel deep learning approach, named dual-CLVSA, to predict financial market movement with both trading data and the corresponding social sentiment measurements, each through a separate sequence-to-sequence channel. We evaluate the performance of our approach with backtesting on historical trading data of SPDR SP 500 Trust ETF over eight years. The experiment results show that dual-CLVSA can effectively fuse the two types of data, and verify that sentiment measurements are not only informative for financial market predictions, but they also contain extra profitable features to boost the performance of our predicting system.

In Vitro Fertilization (IVF) is the most widely used Assisted Reproductive Technology (ART). IVF usually involves controlled ovarian stimulation, oocyte retrieval, fertilization in the laboratory with subsequent embryo transfer. The first two steps correspond with females' follicular phase and ovulation in their menstrual cycle. Therefore, we refer to it as the treatment cycle in our paper. The treatment cycle is crucial because the stimulation medications in IVF treatment are applied directly on patients. In order to optimize the stimulation effects and lower the side effects of the stimulation medications, prompt treatment adjustments are in need. In addition, the quality and quantity of the retrieved oocytes have a significant effect on the outcome of the following procedures. To improve the IVF success rate, we propose a knowledge-based decision support system that can provide medical advice on the treatment protocol and medication adjustment for each patient visit during IVF treatment cycle. Our system is efficient in data processing and light-weighted which can be easily embedded into electronic medical record systems. Moreover, an oocyte retrieval oriented evaluation demonstrates that our system performs well in terms of accuracy of advice for the protocols and medications.

Colorectal polyps are abnormal tissues growing on the intima of the colon or rectum with a high risk of developing into colorectal cancer, the third leading cause of cancer death worldwide. Early detection and removal of colon polyps via colonoscopy have proved to be an effective approach to prevent colorectal cancer. Recently, various CNN-based computer-aided systems have been developed to help physicians detect polyps. However, these systems do not perform well in real-world colonoscopy operations due to the significant difference between images in a real colonoscopy and those in the public datasets. Unlike the well-chosen clear images with obvious polyps in the public datasets, images from a colonoscopy are often blurry and contain various artifacts such as fluid, debris, bubbles, reflection, specularity, contrast, saturation, and medical instruments, with a wide variety of polyps of different sizes, shapes, and textures. All these factors pose a significant challenge to effective polyp detection in a colonoscopy. To this end, we collect a private dataset that contains 7,313 images from 224 complete colonoscopy procedures. This dataset represents realistic operation scenarios and thus can be used to better train the models and evaluate a system's performance in practice. We propose an integrated system architecture to address the unique challenges for polyp detection. Extensive experiments results show that our system can effectively detect polyps in a colonoscopy with excellent performance in real time.

Diabetic retinopathy (DR) is a primary cause of blindness in working-age people worldwide. About 3 to 4 million people with diabetes become blind because of DR every year. Diagnosis of DR through color fundus images is a common approach to mitigate such problem. However, DR diagnosis is a difficult and time consuming task, which requires experienced clinicians to identify the presence and significance of many small features on high resolution images. Convolutional Neural Network (CNN) has proved to be a promising approach for automatic biomedical image analysis recently. In this work, we investigate lesion detection on DR fundus images with CNN-based object detection methods. Lesion detection on fundus images faces two unique challenges. The first one is that our dataset is not fully labeled, i.e., only a subset of all lesion instances are marked. Not only will these unlabeled lesion instances not contribute to the training of the model, but also they will be mistakenly counted as false negatives, leading the model move to the opposite direction. The second challenge is that the lesion instances are usually very small, making them difficult to be found by normal object detectors. To address the first challenge, we introduce an iterative training algorithm for the semi-supervised method of pseudo-labeling, in which a considerable number of unlabeled lesion instances can be discovered to boost the performance of the lesion detector. For the small size targets problem, we extend both the input size and the depth of feature pyramid network (FPN) to produce a large CNN feature map, which can preserve the detail of small lesions and thus enhance the effectiveness of the lesion detector. The experimental results show that our proposed methods significantly outperform the baselines.

Retinopathy of Prematurity (ROP) is an eye disorder primarily affecting premature infants with lower weights. It causes proliferation of vessels in the retina and could result in vision loss and, eventually, retinal detachment, leading to blindness. While human experts can easily identify severe stages of ROP, the diagnosis of earlier stages, which are the most relevant to determining treatment choice, are much more affected by variability in subjective interpretations of human experts. In recent years, there has been a significant effort to automate the diagnosis using deep learning. This paper builds upon the success of previous models and develops a novel architecture, which combines object segmentation and convolutional neural networks (CNN) to construct an effective classifier of ROP stages 1-3 based on neonatal retinal images. Motivated by the fact that the formation and shape of a demarcation line in the retina is the distinguishing feature between earlier ROP stages, our proposed system first trains an object segmentation model to identify the demarcation line at a pixel level and adds the resulting mask as an additional "color" channel in the original image. Then, the system trains a CNN classifier based on the processed images to leverage information from both the original image and the mask, which helps direct the model's attention to the demarcation line. In a number of careful experiments comparing its performance to previous object segmentation systems and CNN-only systems trained on our dataset, our novel architecture significantly outperforms previous systems in accuracy, demonstrating the effectiveness of our proposed pipeline.

In this paper, we design, develop and evaluate an in-home lower body rehabilitation system based on a novel lightweight human pose estimation model. To achieve that, we first create a lower body rehabilitation dataset of 500,000 images with each image annotated with the ground truth joint point locations. The dataset consists of 31 different types of lower body rehabilitation activities from twenty volunteers. After that, we design a lightweight but powerful neural network model, which runs on a smartphone, to estimate human pose. Furthermore, we develop a series of principles for evaluating in-home rehabilitation activities of patients in terms of the range of motion and duration of activities. For the concern of privacy, all the data collected from patients are encrypted, stored and processed locally on patients' own smartphones. Only the sanitized evaluation reports are uploaded and shared with the patients' primary doctors. Our model achieves 70.8 in AP score on the COCO val2017 set with only 4.7M parameters and 1.0 GFLOPs. Using our system, patients can perform lower body rehabilitation activities at home and obtain evaluation report without the presence of physical therapists. We believe our system can greatly facilitate in-home rehabilitation and reduce the cost for patients.

As data-parallel applications process more complex data, the dependencies between computation jobs in a multi-stage job also become more complicated. However, most of the existing scheduling solutions primarily rely on total bytes sent (job size) to differentiate jobs where jobs with fewer? bytes sent are prioritized over the larger ones. This approach overlooks the fact that jobs may consist of multiple computation stages, and that the completion of a computation job stage depends on the completion of other jobs' stage. In this paper, we present a coflow scheduler of multi-stage jobs that minimizes the average job completion time. Our solution prioritizes jobs based on the multi-faceted characteristics of multi-stage job structure per stage, instead of total bytes sent. Our experiments show that our approach provides twice the performance of existing solutions on average and by four times in bursty traffic scenario.

People re-identification is a retrieval problem to find a person of interest among a gallery of person images from different cameras in various poses or view angles. How to get a strong feature representation for a person image plays an important role in performing people re-identification. In this paper, we present a novel end-to-end framework that extracts both global and local features with multiple scales to generate more discriminative representations. The model we design is a multi-branch network consisting of one global branch to obtain features of the whole input image from different convolutional layers and several local branches to obtain features from horizontal partitions in different granularities. Our method achieves state-of-the-art results on three challenging datasets (Market-1501, CUHK03 and DukeMTMC-reid).

We present a 3D Convolutional Neural Networks (CNNs) based single shot detector for spatial-temporal action detection tasks. Our model includes: (i) two short-term appearance and motion streams, with single RGB and optical flow image input separately, in order to capture the spatial and temporal information for the current frame; (ii) two long-term 3D ConvNet based stream, working on sequences of continuous RGB and optical flow images to capture the context from past frames. Our model achieves strong performance for action detection in video and can be easily integrated into any current two-stream action detection methods. We report a frame-mAP of 71.30% on the challenging UCF101-24 [1] actions dataset, achieving the state-of-the-art result of the one-stage methods. To the best of our knowledge, our work is the first system that combined 3D CNN and SSD in action detection tasks.

In self-service supermarket and retail industry, efforts to reduce customer wait time using automatic grocery item identification are challenged by low recognition accuracy, long response time and substantial requirement for equipment. In this paper, we propose a novel edge computing system named EdgeVegfru for vegetable and fruit image classification. While existing work on Vegfru dataset shows excellent performance, few of them have been deployed in real-world applications. We adopt an edge computing paradigm, design, implement and evaluate the whole system on the Android devices. The proposed deep learning model and quantization algorithm reduce the model size and inference time significantly. Our system has shown out-standing accuracy within limited time and computation resources, compared with other machine learning methods(such as Support Vector Machine(SVM), Random Forest(RF)), thus providing the potential path for automatic recognition and pricing in self-service retail stores.

Diabetic retinopathy (DR) is a vision-threatening complication among the diabetic population and a leading cause of blindness for working-age adults. Early detection and timely treatment can reduce the occurrence of blindness due to DR. Computer-aided diagnosis have great potential to significantly improve the accuracy and speed in DR detection over the traditional manual diagnosis process. In this paper, we present a deep convolutional neural network for DR stage classification, trained and evaluated on a large dataset. Our model uses high-resolution retinal fundus images of both the left and right eyes as inputs to take advantage of more detailed retinal lesion information in images and strong correlation between both eyes. Selective data sampling (SeS) is applied in the training process to mitigate the data imbalance problem. Experiments show that our model outperforms the fine-tuned Inception-v3 model by every measure, achieving an accuracy of 87.2% and a Kappa score of 0.806 on the Kaggle dataset.

Recently there have been many efforts to study the predictability of financial market trend using various machine learning approaches. In this paper we explore the idea of using deep neural networks to analyze and predict futures market movements. Our approach adopts deep long short term memory (LSTM) as the main model architecture and predicts futures market movement using augmented market trading data. Training and testing of our model is performed in a rolling fashion to ensure the validity and reliability of the prediction. We discuss the design trade-off of several configurations and variations of our model, and evaluate the impact of various parameter choices as well as how model and backtesting perform under different parameter settings. We further design and implement a complete trading platform to evaluate our approach. Backtesting and live paper trading of our model on this platform achieves promising returns. Moreover, a total return of 58.69% is obtained with live paper trading for a twelve-month period when taking into account of slippage and commissions, which demonstrates the effectiveness of our proposed approach.

Colorectal cancer (CRC) is one of the most commonly diagnosed cancers and a leading cause of cancer deaths in the United States. Colorectal polyps that grow on the intima of the colon or rectum is an important precursor for CRC. Currently, the most common way for colorectal polyp detection and precancerous pathology is the colonoscopy. Therefore, accurate colorectal polyp segmentation during the colonoscopy procedure has great clinical significance in CRC early detection and prevention. In this paper, we propose a novel end-to-end deep learning framework for the colorectal polyp segmentation. The model we design consists of an encoder to extract multi-scale semantic features and a decoder to expand the feature maps to a polyp segmentation map. We improve the feature representation ability of the encoder by introducing the dilated convolution to learn high-level semantic features without resolution reduction. We further design a simplified decoder which combines multi-scale semantic features with fewer parameters than the traditional architecture. Furthermore, we apply three post processing techniques on the output segmentation map to improve colorectal polyp detection performance. Our method achieves state-of-the-art results on CVC-ClinicDB and ETIS-Larib Polyp DB.

Diabetic retinopathy (DR) is a diabetes complication that affects eyes. DR is a primary cause of blindness in working-age people and it is estimated that 3 to 4 million people with diabetes are blinded by DR every year worldwide. Early diagnosis have been considered an effective way to mitigate such problem. The ultimate goal of our research is to develop novel machine learning techniques to analyze the DR images generated by the fundus camera for automatically DR diagnosis. In this paper, we focus on identifying small lesions on DR fundus images. The results from our analysis, which include the lesion category and their exact locations in the image, can be used to facilitate the determination of DR severity (indicated by DR stages). Different from traditional object detection for natural images, lesion detection for fundus images have unique challenges. Specifically, the size of a lesion instance is usually very small, compared with the original resolution of the fundus images, making them diffcult to be detected. We analyze the lesion-vs-image scale carefully and propose a large-size feature pyramid network (LFPN) to preserve more image details for mini lesion instance detection. Our method includes an effective region proposal strategy to increase the sensitivity. The experimental results show that our proposed method is superior to the original feature pyramid network (FPN) method and Faster RCNN.

Colorectal cancer (CRC) is a common and lethal disease. Globally, CRC is the third most commonly diagnosed cancer in males and the second in females. For colorectal cancer, the best screening test available is the colonoscopy. During a colonoscopic procedure, a tiny camera at the tip of the endoscope generates a video of the internal mucosa of the colon. The video data are displayed on a monitor for the physician to examine the lining of the entire colon and check for colorectal polyps. Detection and removal of colorectal polyps are associated with a reduction in mortality from colorectal cancer. However, the miss rate of polyp detection during colonoscopy procedure is often high even for very experienced physicians. The reason lies in the high variation of polyp in terms of shape, size, textural, color and illumination. Though challenging, with the great advances in object detection techniques, automated polyp detection still demonstrates a great potential in reducing the false negative rate while maintaining a high precision. In this paper, we propose a novel anchor free polyp detector that can localize polyps without using predefined anchor boxes. To further strengthen the model, we leverage a Context Enhancement Module and Cosine Ground truth Projection. Our approach can respond in real time while achieving state-of-the-art performance with 99.36% precision and 96.44% recall.

Recent computer-aided polyp detection systems showed its effectiveness to decrease the polyp miss rate in colonoscopy operations, which is helpful to reduce colorectal cancer mortality. However, traditional polyp detection approaches suffer from the following drawbacks: low precision and sensitivity caused by the variance of polyp's appearance, and the system may not be able to detect polyps in real time due to the high computation complexity of the detection algorithms. To alleviate those problems, we introduce a real-time detection framework that incorporates spatial and temporal information extracted from colonoscopy videos. Our framework consists of the following three components: 1) we adopt Single Shot MultiBox Detector (SSD) to generate the proposal bounding boxes in each video frame. 2) Simultaneously, we compute optical flow from neighboring frames to extract temporal information and generate another group of polyp proposals with the temporal detection network. 3) At last, the final result is generated by a fusion module that connects the end of both streams. Experimental results on ETIS-LARIB dataset demonstrate that our proposed approach reaches the state-of-the-art performance on polyp localization with real-time performance.

Financial markets are a complex dynamical system. The complexity comes from the interaction between a market and its participants, in other words, the integrated outcome of activities of the entire participants determines the markets trend, while the markets trend affects activities of participants. These interwoven interactions make financial markets keep evolving. Inspired by stochastic recurrent models that successfully capture variability observed in natural sequential data such as speech and video, we propose CLVSA, a hybrid model that consists of stochastic recurrent networks, the sequence-to-sequence architecture, the self- and inter-attention mechanism, and convolutional LSTM units to capture variationally underlying features in raw financial trading data. Our model outperforms basic models, such as convolutional neural network, vanilla LSTM network, and sequence-to-sequence model with attention, based on backtesting results of six futures from January 2010 to December 2017. Our experimental results show that, by introducing an approximate posterior, CLVSA takes advantage of an extra regularizer based on the Kullback-Leibler divergence to prevent itself from overfitting traps.

The following topics are dealt with: learning (artificial intelligence); mobile computing; wireless sensor networks; feature extraction; Internet of Things; optimisation; graph theory; social networking (online); telecommunication network topology; pattern clustering.

In response to poor quality of experience (QoE), users self-regulating, i.e. they immediately release bandwidth and abandon network. However, there are studies that show users are willing to tolerate poor QoE for some time to evaluate if network performance will improve before abandoning the network. In this paper, we investigate how users willingness to wait for improved QoE may influence network activities, such as network pricing, bandwidth allocation, network revenue, and performance. We develop and employ a self-regulation model that includes user evaluation of QoE before deciding to abandon or stay in the network. This model considers these two factors: user tolerance of low QoE and the price per unit a user is willing to pay. Our investigation uncovers a double edged problem - network may be populated with lower paying users, who are also dissatisfied. These lower paying users drive the price higher than the price produced by conventional solution for network congestion. This leads to our proposal for a market informed congestion control scheme, where network resolves congestion based on user profile that is defined by their ability to pay and demand for bandwidth.

Financial markets are difficult to predict due to its complex systems dynamics. Although there have been some recent studies that use machine learning techniques for financial markets prediction, they do not offer satisfactory performance on financial returns. We propose a novel one-dimensional convolutional neural networks (CNN) model to predict financial market movement. The customized one-dimensional convolutional layers scan financial trading data through time, while different types of data, such as prices and volume, share parameters (kernels) with each other. Our model automatically extracts features instead of using traditional technical indicators and thus can avoid biases caused by selection of technical indicators and pre-defined coefficients in technical indicators. We evaluate the performance of our prediction model with strictly backtesting on historical trading data of six futures from January 2010 to October 2017. The experiment results show that our CNN model can effectively extract more generalized and informative features than traditional technical indicators, and achieves more robust and profitable financial performance than previous machine learning approaches.

We investigate the design of a Mobile Edge Computing (MEC) system in which self-interested users minimize their own costs and a MEC service provider attempts to maximize its revenue. We introduce a third-party platform that works as an intermediary to facilitate the service transaction between the users and the provider. The platform collects MEC server information and discloses that to users; users rely on their user agent apps to place their application jobs on edge computing servers during their stay in the system. We propose a dynamic programming algorithm for a user to minimize his/her own cost and an efficient heuristic algorithm for the platform to minimize the cost of all users by optimally scheduling the admission of users' jobs and still allowing users to make independent optimal decisions. We have demonstrated the effectiveness of these algorithms via extensive simulations based on an empirical Google cloud dataset and a Web file dataset. Furthermore we model the interaction between users and a provider as a game, referred to as User-Provider Game. We find that when the provider always attempts to maximize its own revenue by adjusting the prices of edge servers, the interaction will lead to an unstable system with severe oscillation and degraded performance. To address the issue, we propose a better response algorithm for the provider which stabilizes the system and results in high performance. This paper sheds light on this important area of MEC, and points a promising direction to further investigate and design an effective MEC system of independent self-optimizing mobile users.

We introduce a game-theoretic framework to explore revenue sharing in an Edge-Cloud computing system, in which computing service providers at the edge of the Internet (edge providers) and computing service providers at the cloud (cloud providers) collectively provide computing resources to clients (e.g., end users or applications) at the edge. Different from traditional cloud computing, the providers in an Edge-Cloud system are independent and self-interested. To achieve high system-level efficiency, the manager of the system adopts a task distribution mechanism to maximize the total revenue received from clients and also adopts a revenue sharing mechanism to split the received revenue among computing servers (and hence service providers). Under those system-level mechanisms, service providers attempt to game with the system in order to maximize their own utilities, by strategically allocating their resources (e.g., computing servers). Our framework models the competition among the providers in an Edge-Cloud system as a non-cooperative game. We have shown the existence of Nash equilibrium in the game both theoretically and practically through simulations and experiments on an emulation system that we have developed. We find that revenue sharing mechanisms have a significant impact on the system-level efficiency at Nash equilibria, and surprisingly the revenue sharing mechanism based directly on actual contributions can result in significantly worse system performance than Shapley value sharing mechanism and Ortmann proportional sharing mechanism. Our framework provides an effective economics approach to the understanding and designing of efficient Edge-Cloud computing systems.

Advances in smartphone technologies enable mobile data subscribers to resell their data allowance to other users, creating a secondary data market. The trading environment of this secondary data market is dynamic and ad-hoc: buyers and sellers join and leave the market at all times, changing the trading landscape constantly. The amount of data demanded and offered at any point in time also vary. These conditions make determining a fair transaction price, and matching buyers to sellers difficult in practice. Prior schemes utilize global description of the network and market forces to achieve good performance, but the implementation requires a high overhead cost. In this paper, we present DataMart, a data pricing and user matching platform for trading in this dynamic, ad-hoc and heterogeneous market that works in distributed manner without needing global information. Using insights from real world traces, we demonstrate via simulation that our pricing scheme is converging and consistent with the law of demand and supply. Further, our user matching scheme achieves comparable performance to the optimal solution. We implement a prototype on Android platform, and the experiment results confirm the effectiveness of DataMart.

In Low and Middle-Income Countries (LMICs), efforts to eliminate the Tuberculosis (TB) epidemic are challenged by the persistent social inequalities in health, the limited number of local healthcare professionals, and the weak healthcare infrastructure found in resource-poor settings. The modern development of computer techniques has accelerated the TB diagnosis process. In this paper, we propose a novel method using Convolutional Neural Network(CNN) to deal with unbalanced, less-category X-ray images. Our method improves the accuracy for classifying multiple TB manifestations by a large margin. We explore the effectiveness and efficiency of shuffle sampling with cross-validation in training the network and find its outstanding effect in medical images classification. We achieve an 85.68% classification accuracy in a large TB image dataset, surpassing any state-of-art classification accuracy in this area. Our methods and results show a promising path for more accurate and faster TB diagnosis in LMICs healthcare facilities.

Multimodal Deep Boltzmann Machines (DBMs) have demonstrated huge successes in multimodal representation learning tasks. During inference, DBMs function as Recurrent Neural Nets (RNNs) because of the intractable distributions. To learn the parameters, optimizations can alternatively be operated on these surrogate RNNs with "truncated message passing". As a consequence, the gradient will propagate through a long chain without any local guidance which can potentially affects the optimization procedure. In this paper, we address this problem by adding skip connections during back-propagation while keeping the forward propagation (inference) untouched. With skip connections, we implicitly assign local "targets" for the states of intermediate inference loops to approach. Applied to different training criteria on different data sets, we demonstrate the proposed algorithms can consistently help to train better models while at a lower cost of training time. Experimental results show that our algorithms can achieve state-of-the-art performance on the Multimedia Information Retrieval (MIR) Flickr data set.

Crowdsourcing is often used to solicit contributions from an online community for ideas, evaluation and opinions. However, spamming can pollute such a system and manipulate the results of crowdsourcing. For detection of those spammers, the training data used in previous studies is often derived by experts labeling collected data and manually identifying spammers. The reliability of such training data is questionable. In this paper, we utilize two web based service providers Zhubajie (ZBJ) and Sandaha (SDH) and obtain reliable data about the spammers. We use such data to investigate the crowd-retweeting spam in Sina Weibo. We analyze profile features, social relationship and retweeting behavior of such spammers. We find that although these spammers are likely to connect more closely than legitimate users, the underlying social tie is different from the social relationship in other spam campaigns because of the unique retweeting features with the information cascade effect. Based on these findings, we propose retweeting-aware link based ranking algorithms to detect suspect spam accounts using seeds of identified spammers. Our evaluation shows that our algorithm is more effective than other link-based methods.

We investigate emerging proximity-based Mobile Crowd Service or pMCS systems, in which services are provided and consumed by users carrying smart mobile devices (e.g., smartphones) and in proximity of each other (e.g., within Bluetooth range). Due to limited resources on smartphones, it is crucial to provide a mechanism to incentivize users' participation and ensure fair trading in a pMCS system. In this paper, we design a multi-market dynamic double auction mechanism for a pMCS system, referred to as MobiAuc, and we show that it is truthful, feasible, individual-rational, no-deficit, and computationally efficient. The novelty and significance of MobiAuc is that it addresses and solves the fair trading problem in a multi-market dynamic double auction setting which naturally occurs in a mobile wireless environment. We demonstrate its efficiency via simulations based on generated user patterns (stochastic arrivals and random market clustering of users) and real-world traces. Our preliminary implementation of MobiAuc and experiments on Android platform have demonstrated the feasibility of MobiAuc mechanism in practice.

Online dating sites have become popular platforms for people to look for potential romantic partners. Different from traditional user-item recommendations where the goal is to match items (e.g., books, videos, etc) with a user's interests, a recommendation system for online dating aims to match people who are mutually interested in and likely to communicate with each other. We introduce similarity measures that capture the unique features and characteristics of the online dating network, for example, the interest similarity between two users if they send messages to same users, and attractiveness similarity if they receive messages from same users. A reciprocal score that measures the compatibility between a user and each potential dating candidate is computed and the recommendation list is generated to include users with top scores. The performance of our proposed recommendation system is evaluated on a real-world dataset from a major online dating site in China. The results show that our recommendation algorithms significantly outperform previously proposed approaches, and the collaborative filtering-based algorithms achieve much better performance than content-based algorithms in both precision and recall. Our results also reveal interesting behavioral difference between male and female users when it comes to looking for potential dates. In particular, males tend to be focused on their own interest and oblivious towards their attractiveness to potential dates, while females are more conscientious to their own attractiveness to the other side of the line.

When natural disasters strike, network infrastructure is often completely destroyed, disabling communication; this significantly hampers rescue and relief efforts. Therefore, emergency communication network infrastructure must be deployed to provide communication at ground zero to rescue and relief agencies. The deployment strategy has to consider these humanitarian agencies' varying degrees of responsibilities which correspond to their levels of communication needs. In this paper, we propose a more precise deployment of emergency communication network based on our field study of how relief organizations collaborated at ground zero in Aceh, Indonesia, post Tsunami 2004. Building on our field findings, the emergency communication deployment is formulated to a k-Weighted Deployment problem, achieving a more customized delivery of communication network services to organizations according to their varying level of responsibilities and communication needs, including resource provisioning strategy. Finally, we devise a two-stage implementation protocol to achieve the objective of a more effective and targeted deployment to areas affected by natural disasters.

The growing popularity for video based applications has put an enormous strain on the network and causes the network to be more prone to congestion. The study of congestion control and bandwidth allocation problems is often formulated into Network Utility Maximization (NUM) framework, and the existing solutions for NUM generally focus on single-layered applications. However, today's quality of video is divided into several layers, where each layer provides different level of enhancement of quality. In this paper, we study how multi-layered video based applications impact network performance and pricing through NUM formulation, in particularly traffic from video streaming. In our investigation, we design and implement a new multi-layered user utility model that leverages on studies of human visual perception. Then, using this new utility model to examine network activities, we demonstrate that solving NUM with multi-layered utility is intractable, and that rate allocation and network pricing may oscillate due to user behavior specific to multi-layered applications. To address this, we propose a new approach for admission control to ensure quality of service and experience.

There is a fast growing number of public spaces offering Wi-Fi access to meet the rising demands for Internet access. It is common for such service to be offered to users at no charge or for a flat fee. Both situations provide very little incentive for Wi-Fi providers to offer better service to the users. Similarly, Wi-Fi providers pay a monthly flat rate to ISP for Internet access and, this too does not incentivize ISP to offer better service to Wi-Fi users. As a result, Wi-Fi users may experience poor connection when network becomes congested during peak hours. In this paper we propose a dynamic pricing scheme for Internet access and a revenue sharing mechanism that provides incentives for both ISP and Wi-Fi providers to offer better service to their users. We build our revenue sharing model based on Shapley value mechanism. Importantly, our proposed revenue sharing mechanism captures the power negotiation between ISP and Wi-Fi providers, and how shifts in power influences revenue division. Specifically, the model assures that the party who contributes more receives a higher portion of the revenue. In addition, our simulation demonstrates that our model captures the bargaining power shifts between Wi-Fi providers and ISP, and shows that the division of revenue asymptotically converges to a percentage value.

There is a fast growing number of public spaces offering Wi-Fi access to meet the rising demands for the Internet. It is common for such service to be offered to users at no charge or for a flat fee. Both situations provide very little incentive for Wi-Fi providers to offer better service to the users. Similarly, Wi-Fi providers pay a monthly flat-rate to ISP for Internet access, which does not incentivize ISP to offer better service to Wi-Fi users. As a result, Wi-Fi users may experience poor Internet connection when network becomes congested during peak hours. In this paper, we propose a dynamic pricing mechanism for both ISP and Wi-Fi providers in order to give mobile Wi-Fi users better service, while providing economic incentive for both ISP and Wi-Fi provider.

Concomitant to the growing popularity of Internet enabled mobile devices such as smartphones, tablets, PDAs, portable media players etc., however, are the concerns about availability of Internet access points for these devices. Mobile users often either overpay for service availability such as (3G or LTE) or suffer incapability of accessing Internet services due to limited hardware resources (3G or LTE) or exhaustion of carrier enforced data plans. In this paper we introduce Collab Assure, an auction based, ad-hoc market model assuring service for users with no Internet access capability. Collab Assure framework provides service assurance through opportunistic ad-hoc networks formed by spatio-temporally co-existing mobile users. The system allows users to "sublet" their surplus data plans to the users without Internet access. We discuss the design and implementation of Collab Assure technology in Android framework. Our simulation results advocate the success of this approach on real world traces, where mobile users need to participate in auctions for achieving on-demand and low-cost data service.

In this paper, we introduce a novel computer vision based attack that automatically discloses inputs on a touch-enabled device while the attacker cannot see any text or popup in a video of the victim tapping on the touch screen. We carefully analyze the shadow formation around the fingertip, apply the optical flow, deformable part-based model (DPM), k-means clustering and other computer vision techniques to automatically locate the touched points. Planar homography is then applied to map the estimated touched points to a reference image of software keyboard keys. Recognition of passwords is extremely challenging given that no language model can be applied to correct estimated touched keys. Our threat model is that a webcam, smartphone or Google Glass is used for stealthy attack in scenarios such as conferences and similar gathering places. We address both cases of tapping with one finger and tapping with multiple fingers and two hands. Extensive experiments were performed to demonstrate the impact of this attack. The per-character (or per-digit) success rate is over 97% while the success rate of recognizing 4-character passcodes is more than 90%. Our work is the first to automatically and blindly recognize random passwords (or passcodes) typed on the touch screen of mobile devices with a very high success rate.

Cellular Network Providers (CNP) provide users with wireless data access to meet the growing ubiquitous demand for the Internet. As users subscribe to a fixed data plan for a monthly flat fee, some users may exhaust their data allowance before the end of the billing cycle, while others underutilize their monthly quota. To take advantage of such underutilization, Khausik et. al. propose a mechanism for ad hoc bandwidth redistribution that allows subscribers to sell their unused bandwidth to users needing Internet access in exchange for some financial compensation as and when opportunities arise. There exists a popular belief that allowing such on-demand ad hoc service is not beneficial to CNP. This paper seeks to address and counter this opinion by proposing a pricing scheme and a revenue sharing mechanism that makes the provision of ad hoc connection advantageous to CNP. Our revenue sharing mechanism provides economic incentives to CNP. The simulation results show that our revenue sharing model ensures that CNP receives the majority portion of the revenue gained, regardless of the amount. Secondly, our pricing model ensures traffic from ad hoc users has minimal impact on the connection quality of current subscribers. In this model, we use Shapley value as the basis for deriving the revenue sharing.

While wireless ad hoc networks have a wide range of applications in environment monitoring, military operations, and disaster recovery, etc, the full potential of such networks is inherently hindered by their diminishing capacity as the network size scales up. Content caching has been previously proposed to improve the availability of contents in a network and thus helps to alleviate the load on content custodians, reduce access latency, and improve the network capacity. This paper studies the scaling laws of the capacity of cache-enabled content distribution wireless ad hoc networks. We consider two basic content access schemes, namely, the Nearest Caching Node scheme where a request is satisfied by the nearest node to the requestor that has the content in its cache, and the Transparent Enroute Caching scheme where a content request is routed towards the content custodian and is satisfied by an intermediate node (or custodian) along the path that has the content in its cache. We first establish the capacity of content distribution wireless ad hoc networks without content caching as a baseline for investigating the benefit of caching. We then obtain the scaling laws of the capacity for the above two content access schemes with content caching. Based on the results we further explore their design and performance implications. Our results show that the capacity exhibits distinct scaling behaviors under different scaling regimes of the network parameters. Under certain conditions increasing the cache size of the nodes can effectively improve the capacity while under other conditions the improvement can be negligible. The characterizations of the capacity allows us to identify the bottleneck of the content access capacity for given network scenarios and choose effective approaches to improve the capacity.

This paper presents a fully functional and highly portable mini Unmanned Aerial Vehicle (UAV) system, HAWK, for conducting aerial localization. HAWK is a programmable mini helicopter Draganflyer X6 armed with a wireless sniffer Nokia N900. We developed custom PI-Control laws to implement a robust waypoint algorithm for the mini helicopter to fly a planned route. A Moore space filling curve is designed as a flight route for HAWK to survey a specific area. A set of theorems were derived to calculate the minimum Moore curve level for sensing all targets in the area with minimum flight distance. With such a flight strategy, we can confine the location of a target of interest to a small hot area. We can recursively apply the Moore curve-based flight route to the hot area for a fine-grained localization of a target of interest. We have conducted extensive experiments to validate the feasibility of HAWK and our theory. A demo of HAWK in autonomous fly is available at http://www.youtube.com/watch?v=ju86xnHbEq0.

Online dating sites have become popular platforms for people to look for potential romantic partners. It is important to understand users' dating preferences in order to make better recommendations on potential dates. The message sending and replying actions of a user are strong indicators for what he/she is looking for in a potential date and reflect the user's actual dating preferences. We study how users' online dating behaviors correlate with various user attributes using a real-world dateset from a major online dating site in China. Our study provides a firsthand account of the user online dating behaviors in China, a country with a large population and unique culture. The results can provide valuable guidelines to the design of recommendation engine for potential dates.

Telehealth and wearable equipment can deliver personal healthcare and necessary treatment remotely. One major challenge is transmitting large amount of biosignals through wireless networks. The limited battery life calls for low-power data compressors. Compressive Sensing (CS) has proved to be a low-power compressor. In this study, we apply CS on the compression of multichannel biosignals. We firstly develop an efficient CS algorithm from the Block Sparse Bayesian Learning (BSBL) framework. It is based on a combination of the block sparse model and multiple measurement vector model. Experiments on real-life Fetal ECGs showed that the proposed algorithm has high fidelity and efficiency. Implemented in hardware, the proposed algorithm was compared to a Discrete Wavelet Transform (DWT) based algorithm, verifying the proposed one has low power consumption and occupies less computational resources.

In many wireless localization applications, we rotate a directional antenna to derive the angle of arrival (AOA) of wireless signals transmitted from a target mobile device. The AOA corresponds to the direction in which the maximum received signal strength (RSS) is sensed. However, an unanswered question is how to make sure the directional antenna picks up packets producing the maximum RSS while rotating. We propose a set of novel RSS sampling theory to answer this question. We recognize the process that a directional antenna measures RSS of wireless packets while rotating as the process that the radiation pattern of the directional antenna is sampled. Therefore, if RSS samples can reconstruct the antenna's radiation pattern, the direction corresponding to the peak of the radiation pattern is the AOA of the target. We derive mathematical models to determine the RSS sampling rate given the target's packet transmission rate. Our RSS sampling theory is applicable to various types of directional antennas. To validate our RSS sampling theory, we developed BotLoc, which is a programmable and self-coordinated robot armed with a wireless sniffer. We conducted extensive real-world experiments and the experimental results match the theory very well. A video of BotLoc is at www.youtube.com/watch?v=WtUt0IqhXRU&feature=youtu.be.

Path planning is a critical task for search and rescue mission in Mobile Ad-hoc Rescue Network in natural or unnatural catastrophes. However, most existing path planning schemes fail to cope with the challenges in post-disaster map environment due to its increased complexity and uncertainty. To address these issues, we propose a Hierarchical Random Walk based path Planner (HRWP). In HRWP, Regular Grid and Voronoi Diagram are used to model the map, and uncertain map segments are assigned uncertain cost using random variables. The hierarchical random walk is then designed to generate the optimal path using probabilistic accept-reject. In this way, results of HRWP can significantly reduce the risk of uncertainty and converge to the optimal path. Using a combination of analytical modeling and extensive simulations we show that HRWP outperforms existing path planer and mobility schemes, and performs well in complicated environments.

We study the dynamic aspects of the coverage of a mobile sensor network resulting from continuous movement of sensors. As sensors move around, initially uncovered locations may be covered at a later time, and intruders that might never be detected in a stationary sensor network can now be detected by moving sensors. However, this improvement in coverage is achieved at the cost that a location is covered only part of the time, alternating between covered and not covered. We characterize area coverage at specific time instants and during time intervals, as well as the time durations that a location is covered and uncovered. We further consider the time it takes to detect a randomly located intruder and prove that the detection time is exponentially distributed with parameter 2\lambda r \bar{v}_s where \lambda represents the sensor density, r represents the sensor's sensing range, and \bar{v}_s denotes the average sensor speed. For mobile intruders, we take a game theoretic approach and derive optimal mobility strategies for both sensors and intruders. We prove that the optimal sensor strategy is to choose their directions uniformly at random between [0, 2\pi ). The optimal intruder strategy is to remain stationary. This solution represents a mixed strategy which is a Nash equilibrium of the zero-sum game between mobile sensors and intruders.

Read-Optimized databases are well suited for read intensive Data Warehouse applications. In addition, data in these applications grow rapidly and hence need a dynamically scalable environment like Cloud. Cloud provides a flexible environment where user can load data, execute queries and scale resources on demand. However, cloud has its own challenges. To reduce the inter-node communication during the execution of query, tables are horizontally partitioned on join attribute and then related partitions are stored on the same physical system. In cloud environment it is not possible to ensure that these related partitions are always stored on the same physical system. As the resources are scaled up, the number of nodes involved increases, resulting in the increased inter-node communication. This becomes critical when we have huge data (in Tera or Peta bytes) stored across a large number of nodes. So with the increase in number of nodes and data size, the communication message size increases. All these factors result in increased bandwidth usage and performance degradation. When the number of joins in a query increases, the performance will further degrade. These problems emphasize a need for good storage structure and query execution plan. In this paper we propose a storage structure PK-map and a query processing algorithm. We show, through experiments, that this approach not only decreases the inter-node communication overhead but also decreases the work load of joins.

Admission control (AC) is an effective mechanism for providing bandwidth assurance in wireless mesh networks. Early AC schemes over multirate WMNs typically use a pre-chosen rate or a MAC-layer adapted rate for each link, denying data sessions that could have been admitted should a better multirate AC be available. Taking full advantage of multirate WMNs, we present a rate-adaptive admission control protocol (RaAC) for IEEE 802.11-based WMNs. RaAC consists of three major components: (1) a rate adaption algorithm to meet the bandwidth requirement of the data session and satisfy the channel condition of the PHY layer; (2) a new path-selection metric to balance between hop counts, bandwidth, rates, and other network parameters; and (3) a routing-coupled, distributed, rate-adaptive admission control algorithm to admit data sessions with bandwidth assurance. Through simulations, we show that RaAC is efficient and effective in meeting bandwidth requirements.

We investigate whether friend relationship in online social networks (OSNs) can help to improve the performance of Peer-to-Peer (P2P) data swarming systems. Due to the importance and popularity of OSNs and P2P swarming (the two major applications on the Internet), the research community shows increasing interest in leveraging OSNs for data swarming system design. In this paper, we present our initial findings about some of the basic issues in this emerging area, which are largely missing from existing work. Specifically, we conduct a measurement study of a popular online social network - Douban [1], and our analysis of this OSN provides strong empirical evidence of the association between users' content interests and their online social friend relationship. Then we introduce a simple public social streaming scheme that lets peers simultaneously join multiple swarms of the same data content with the help from their online social friends. Our simulation studies demonstrate that this social scheme can lead to significant performance improvement in vanilla P2P streaming systems. Furthermore we explore the impact of various social graphs on the performance improvement brought about by the social scheme. Our findings indicate that our proposed social scheme consistently achieves greater performance improvement on Erdos-Renyi's random graphs than on other graphs such as Barabasi-Albert's scale-free graphs and the empirical Facebook and Douban social graphs. This result points to an important research direction of leveraging OSNs in data swarming system design.

We present achievable scaling results on the per-node secure throughput that can be realized in a large random wireless network of n legitimate nodes in the presence of m eavesdroppers of unknown location. We consider both one-dimensional and two-dimensional networks. In the one-dimensional case, we show that a per-node secure throughput of order 1/n is achievable if the number of eavesdroppers satisfies m = o(n/log n). We obtain similar results for the two-dimensional case, where a secure throughput of order 1/(√n log n) is achievable under the same condition. The number of eavesdroppers that can be tolerated is significantly higher than previous works that address the case of unknown eavesdropper locations. The key technique introduced in our construction to handle unknown eavesdropper locations forces adversaries to intercept a number of packets to be able to decode a single message. The whole network is divided into regions, where a certain subset of packets is protected from adversaries located in each region. In the one-dimensional case, our construction makes use of artificial noise generation by legitimate nodes to degrade the signal quality at the potential locations of eavesdroppers. In the two-dimensional case, the availability of many paths to reach a destination is utilized to handle collaborating eavesdroppers of unknown location.

This paper presents a fully functional and highly portable mini Unmanned Aerial Vehicle (UAV) system, HAWK, for conducting aerial localization. HAWK is a programmable mini helicopter - Draganflyer X6 - armed with a wireless sniffer - Nokia N900. We developed custom PI-Control laws to implement a robust waypoint algorithm for the mini helicopter to fly a planned route. A Moore space filling curve is designed as a flight route for HAWK to survey a specific area. A set of theorems were derived to calculate the minimum Moore curve level for sensing all targets in the area with minimum flight distance. With such a flight strategy, we can confine the location of a target of interest to a small hot area. We can recursively apply the Moore curve based flight route to the hot area for a fine-grained localization of a target of interest. Therefore, HAWK does not rely on a positioning infrastructure for localization. We have conducted extensive experiments to validate the feasibility of HAWK and our theory. A demo of HAWK in autonomous fly is available at http://www.youtube.com/watch?v=ju86xnHbEq0.

Opportunistic routing (OR) is a viable approach for improving performance of wireless communications. Previous studies on OR have focused on cost minimization, performance of multiple rates, congestion control, and other issues. Bandwidth assurance over OR, however, has not been adequately investigated. To bridge this gap, we present a bandwidth-aware opportunistic routing (BOR) with admission control (AC) protocol named BOR/AC. In particular, by analyzing the expected available bandwidth (EAB) and the expected transmission cost (ETC) in OR, we first devise a new metric called BCR (bandwidth-cost ratio) to determine the priority of relays in the forwarding candidates set. Admission control is then applied to admit or reject traffic flows based on estimated expected available bandwidth. Extensive simulation results show that BOR/AC consistently achieves much better performance than existing opportunistic routing protocols.

Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveillance and environmental monitoring. An important performance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal processing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are conducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sensing. In this paper, we attempt to bridge this gap by exploring the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multiple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors when several physical properties of the target signal are known. In particular, for signal path loss exponent of (typically between 2.0 and 5.0), ρf= O(ρd1-1/k, where ρfand ρdare the densities of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Moreover, data fusion can also reduce network density for regularly deployed networks and mobile networks where mobile sensors can relocate to fill coverage holes. Our results help understand the limitations of the previous analytical results based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.

Intersection collision warning system has been widely studied with the progress in wireless communication technology and positioning devices, which are now increasingly available on smart phones. In this paper, we present an Intersection Collision Warning (ICW) system using Wi-Fi smart phones with built-in GPS receivers for vehicular ad-hoc networks. In the system, smart phones first retrieve safety-related information, i.e., location, moving direction and velocity, via onboard GPS receivers and then periodically exchange the information using standard wireless communication between vehicles to compute the probability of potential collision and issue warnings when necessary. Simulation results show that our ICW system can significantly reduce the probability of collisions.

The network address translation technique (NAT) is widely used in wireless routers. It is a low cost solution to IPv4 address space limitations. However, cyber criminals may abuse NAT and hide behind wireless routers to use mobile devices and conduct crimes. To identify a suspect mobile device, we should be able to map the suspect public traffic on the Internet to the private traffic behind the wireless router in WLAN. In this paper, we propose a suite of novel packet size based traffic marking techniques to identify suspect mobiles in encrypted wireless networks as well as open wireless networks. To cope with severe packet loss during wireless sniffing, we proposed to use error correcting codes to improve detection rate. We conducted extensive analysis and experiments to demonstrate the efficiency and accuracy of our schemes, which achieve high detection rate and very small false positive rate. The proposed strategies can be used for law enforcement for combatting cyber crimes in wireless network crime scene investigations.

Real-time detection is an important requirement of many mission-critical wireless sensor network applications such as battlefield monitoring and security surveillance. Due to the high network deployment cost, it is crucial to understand and predict the real-time detection capability of a sensor network. However, most existing real-time analyses are based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of detection. In practice, data fusion has been adopted in a number of sensor systems to deal with sensing uncertainty and enable efficient collaboration among resource-limited sensors. However, real-time performance analysis of sensor networks designed based on data fusion has received little attention. In this paper, we bridge this gap by investigating the fundamental real-time detection performance of large-scale sensor networks under stochastic sensing models. In particular, we consider two basic data fusion schemes, i.e., value fusion and decision fusion. Our results show that data fusion is effective in achieving stringent performance requirements such as short detection delay and low false alarm rates. Moreover, value fusion and decision fusion are suitable for low and high signal-to-noise ratio scenarios, respectively. Our results help understand the impact of data fusion and provide important guidelines for the design of real-time wireless sensor networks for intrusion detection. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection. The results show that data fusion can reduce the network density by about 60 percent compared with the disc model while detecting any intruder within one detection period at a false alarm rate lower than five percent.

Constructing sensing barriers using wireless sensor networks has important applications in military operations and homeland security. The goal of forming a sensing barrier is to detect intruders attempting to cross the network. Early studies often assume that sensors remain static once deployed. We note that barrier gaps may occur at deployment if sensors are deployed at random. Barrier gaps may also occur in an existing barrier if some sensors used to form the barrier start malfunctioning or run out of power. We present an efficient solution to solve this problem. In particular, we devise an efficient algorithm to find sensing gaps and relocate mobile sensors to form a new barrier while balancing the energy consumption among mobile sensors. We also investigate the related design issues and performance tradeoffs. Simulation results show that our algorithms can effectively improve the barrier coverage of a wireless sensor network under a wide range of deployment parameters. These results provide insights and guidelines to the deployment, design, and performance of mobile wireless sensor networks for barrier coverage.

Barrier coverage is a critical issue in wireless sensor networks for various battlefield and homeland security applications. The goal is to effectively detect intruders that attempt to penetrate the region of interest. A sensor barrier is formed by a connected sensor cluster across the entire deployed region, acting as a "trip wire" to detect any crossing intruders. In this paper we study how to efficiently improve barrier coverage using mobile sensors with limited mobility. After the initial deployment, mobile sensors can move to desired locations and connect with other sensors in order to create new barriers. However, simply moving sensors to form a large local cluster does not necessarily yield a global barrier. This global nature of barrier coverage makes it a challenging task to devise effective sensor mobility schemes. Moreover, a good sensor mobility scheme should efficiently improve barrier coverage under the constraints of available mobile sensors and their moving range. We first explore the fundamental limits of sensor mobility on barrier coverage and present a sensor mobility scheme that constructs the maximum number of barriers with minimum sensor moving distance. We then present an efficient algorithm to compute the existence of barrier coverage with sensors of limited mobility, and examine the effects of the number of mobile sensors and their moving ranges on the barrier coverage improvement. Both the analytical results and performance of the algorithms are evaluated via extensive simulations.

With current technologies submarines can thwart active or passive sonar detection. A viable alternative to detect submissible vessels is to use magnetic or acoustic sensors in close proximity to possible underwater pathways of them. This approach may require deploying large-scale underwater sensor networks to form barriers. We show new results for construction barriers in 3D sensor networks. First, we prove that barriers are unlikely to exist in a large 3D fixed emplacement sensor field where sensor locations follow a Poisson point process. We then derive the notion of 3D stealth distance to measure how far a submarine can travel in a sensor network without detection. Finally, we describe energy conserving approaches for constructing a 3D barrier using mobile nodes to detect intruders. We focus on developing an energy efficient matching of mobile sensors that move to cover gridpoints using auction algorithms. We compare our results of the auction approach to an optimal approach using simulations and show that the auction algorithm produces similar results to the optimal approach at a reduced computational expense. This provides a fruitful new approach to constructing barriers in 3D sensor networks.

Barrier coverage of wireless sensor networks has been studied intensively in recent years under the assumption that sensors are deployed uniformly at random in a large area (Poisson point process model). However, when sensors are deployed along a line (e.g., sensors are dropped from an aircraft along a given path), they would be distributed along the line with random offsets due to wind and other environmental factors. It is important to study the barrier coverage of such line- based deployment strategy as it represents a more realistic sensor placement model than the Poisson point process model. This paper presents the first set of results in this direction. In particular, we establish a tight lower-bound for the existence of barrier coverage under line-based deployments. Our results show that the barrier coverage of the line-based deployments significantly outperforms that of the Poisson model when the random offsets are relatively small compared to the sensor's sensing range. We then study sensor deployments along multiple lines and show how barrier coverage is affected by the distance between adjacent lines and the random offsets of sensors. These results demonstrate that sensor deployment strategies have direct impact on the barrier coverage of wireless sensor networks. Different deployment strategies may result in significantly different barrier coverage. Therefore, in the planning and deployment of wireless sensor networks, the coverage goal and possible sensor deployment strategies must be carefully and jointly considered. The results obtained in this paper will provide important guidelines to the deployment and performance of wireless sensor networks for barrier coverage.

Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveil-lance and environmental monitoring. An important per-formance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal process-ing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are con-ducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sens-ing. In this paper, we attempt to bridge this gap by explor-ing the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multi-ple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors. In particu-lar, for signal path loss exponent of k (typically between 2.0 and 5.0), ρf = O(ρ1−1/kd), where ρf and ρd are the densi-ties of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Our results help understand the limitations of the previous analytical re-sults based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.

Real-time detection is an important requirement of many mission-critical wireless sensor network applications such as battlefield monitoring and security surveillance. Due to the high network deployment cost, it is crucial to understand and predict the real-time detection capability of a sensor network. However, most existing real-time analyses are based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of detection. In practice, data fusion has been adopted in a number of sensor systems to deal with sensing uncertainty and enable the collaboration among sensors. However, real-time performance analysis of sensor networks designed based on data fusion has received little attention. In this paper, we bridge this gap by investigating the fundamental real-time detection performance of large-scale sensor networks under stochastic sensing models. Our results show that data fusion is effective in achieving stringent performance requirements such as short detection delay and low false alarm rates, especially in the scenarios with low signal-to-noise ratios (SNRs). Data fusion can reduce the network density by about 60% compared with the disc model while detecting any intruder within one detection period at a false alarm rate lower than 2%. In contrast, the disc model is only suitable when the SNR is sufficiently high. Our results help understand the impact of data fusion and provide important guidelines for the design of real-time wireless sensor networks for intrusion detection.

Extensive research has demonstrated the potential improvement in physical layer performance when multiple radios transmit concurrently in the same radio channel. We consider how such cooperation affects the requirements for full connectivity and percolation in large wireless ad hoc networks. Both noncoherent and coherent cooperative transmission are considered. For one-dimensional (1-D) extended networks, in contrast to noncooperative networks, for any path loss exponent less than or equal to one, full connectivity occurs under the noncoherent cooperation model with probability one for any node density. Conversely, there is no full connectivity with probability one when the path loss exponent exceeds one, and the network does not percolate for any node density if the path loss exponent exceeds two. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any path loss exponent less than or equal to two, full connectivity is achieved for any node density. Conversely, there is no full connectivity when the path loss exponent exceeds two, but the cooperative network percolates for node densities above a threshold which is strictly less than that of the noncooperative network. A less conclusive set of results is presented for the coherent case. Hence, even relatively simple noncoherent cooperation improves the connectivity of large ad hoc networks.

This paper studies the scaling laws of the data gathering capacity of large scale multihop wireless networks. Unlike the data communication paradigms studied in previous research, for example, the many-to-many, many-to-one, broadcast, and multicast paradigms, the data gathering capacity concerns the per source node throughput in a network where a subset of nodes send data to some designated destinations while other nodes serve as relays. This some-to-some communication paradigm is commonplace in many wireless networks, for example, wireless mesh networks and wireless sensor networks, and in some cases perhaps more prevalent than the other paradigms. We first derive the upper and constructive lower bounds for the data gathering capacity, and then examine their design and performance implications. Our results show that the data gathering capacity is constrained by different factors in several different scaling regimes of the number of source and destination nodes, exhibiting distinct scaling laws in those regimes. This work fills a gap in our understanding of the capacity of various communication paradigms, and can lead to better network planning and performance for data gathering wireless network applications.

Constructing sensor barriers to detect intruders crossing a randomly-deployed sensor network is an important problem. Early results have shown how to construct sensor barriers to detect intruders moving along restricted crossing paths in rectangular areas. We present a complete solution to this problem for sensors that are distributed according to a Poisson point process. In particular, we present an efficient distributed algorithm to construct sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. Our approach is as follows: We first show that in a rectangular area of width w and length l with w = Ω(log l), if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the other hand, if w = o(log l), then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. We then devise, based on this result, an efficient distributed algorithm to construct multiple disjoint barriers in a large sensor network to cover a long boundary area of an irregular shape. Our algorithm approximates the area by dividing it into horizontal rectangular segments interleaved by vertical thin strips. Each segment and vertical strip independently computes the barriers in its own area. Constructing "horizontal" barriers in each segment connected by "vertical" barriers in neighboring vertical strips, we achieve continuous barrier coverage for the whole region. Our approach significantly reduces delay, communication overhead, and computation costs compared to centralized approaches. Finally, we implement our algorithm and carry out a number of experiments to demonstrate the effectiveness of constructing barrier coverage.

Connectivity and capacity are two measures for the performance of mobile ad hoc networks that have been studied extensively under standard point-to-point physical layer assumptions. However, extensive recent research at the physical layer has demonstrated the improvement in performance possible when multiple radios concurrently transmit in the same radio channel. In this paper, we consider how such physical layer cooperation improves the connectivity in wireless ad hoc networks. In particular, with noncoherent cooperation at the physical layer, we consider conditions on the node density λ (or, equivalently, the transmit power) for full connectivity and percolation for large networks in various dimensions and with various path loss exponents α. For one-dimensional (1-D) extended networks, in sharp contrast to noncooperative networks, we demonstrate that full connectivity can be realized under certain conditions. In particular, for any node density with path loss exponent α < 1, or for node density λ > 2 when α = 1, full connectivity occurs with probability one. Conversely, we demonstrate that, under noncoherent cooperation, there is no full connectivity with probability one when α < 1. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any node density with α < 2, or for node density λ Ū 5 when α = 2, full connectivity is achieved. Conversely, there is no full connectivity with probability one when α > 2, but we prove that, for α ≥ 4, the percolation threshold of the noncoherent cooperative network is strictly less than that of the noncooperative network. Analogous results are presented for dense networks. Hence, the main conclusion is that even relatively simple physical layer cooperation in the form of noncoherent power summing can substantially improve the connectivity of large ad hoc networks.

In this paper we study the capacity of wireless ad hoc networks with infrastructure support of an overlay of wired base stations. Such a network architecture is often referred to as hybrid wireless network or multihop cellular network. Previous studies on this topic are all focused on the twodimensional disk model proposed by Gupta and Kumar in their original work on the capacity of wireless ad hoc networks. We further consider a one-dimensional network model and a two-dimensional strip model to investigate the impact of network dimensionality and geometry on the capacity of such networks. Our results show that different network dimensions lead to significantly different capacity scaling laws. Specifically, for a one-dimensional network of n nodes and b base stations, even with a small number of base stations, the gain in capacity is substantial, increasing linearly with the number of base stations as long as b log b ≤ n. However, a two-dimensional square (or disk) network requires a large number of base stations b = Ω ( √ n) before we see such a capacity increase. For a 2-dimensional strip network, if the width of the strip is at least on the order of the logarithmic of its length, the capacity follows the same scaling law as in the 2-dimensional square case. Otherwise the capacity exhibits the same scaling behavior as in the 1-dimensional network. We find that the different capacity scaling behaviors are attributed to the percolation properties of the respective network models.

Abstract — There is an inherent well-known conflict between fairness and throughput that arises in many networking scenarios. A number of researchers have studied this problem in the context of (single-hop) wireless local area networks (WLANs), where clients directly exchange traffic with access points (APs). More recently, researchers have proposed multi-hop extensions to WLANs where client traffic is forwarded via a series of client-client links. In this paper, we show that the objective of improving throughput without sacrificing fairness can be much better met in multi-hop WLANs. We decouple this objective into two separate but related problems. First, we need an algorithm to organize clients into a multi-hop structure such that fair bandwidth allocation within this structure leads to improved throughput. Second, we need algorithms for performing fair bandwidth allocation within the determined multi-hop structure. In this paper, we first design optimal fair bandwidth allocation algorithms for both max-min throughput fairness and max-min time fairness in multi-hop WLANs. Subsequently, design an efficient algorithm to find desirable multi-hop structures. With slight modification, our results in this paper can be generalized to other multi-hop wireless networks, such as the emerging wireless backhaul networks and wireless mesh networks. Our proposed solutions seamlessly integrate with legacy devices and hence are incrementally deployable. Simulation results demonstrate that our solutions can effectively improve throughput (by up to 114% or more) as well as network coverage while preserving fairness. I.

A number of mobility models have been proposed for the purpose of either analyzing or simulating the movement of users in a mobile wireless network. Two of the more popular are the random waypoint and the random direction models. The random waypoint model is physically appealing but difficult to understand. Although the random direction model is less appealing physically, it is much easier to understand. User speeds are easily calculated, unlike for the waypoint model, and, as we observe, user positions and directions are uniformly distributed. The contribution of this paper is to establish this last property for a rich class of random direction models that allow future movements to depend on past movements. To this end, we consider finite oneand two-dimensional spaces. We consider two variations, the random direction model with wrap around and with reflection. We establish a simple relationship between these two models and, for both, show that positions and directions are uniformly distributed for a class of Markov movement models regardless of initial position. In addition, we establish a sample path property for both models, namely that any piecewise linear movement applied to a user preserves the uniform distribution of position and direction provided that users were initially uniformly throughout the space with equal likelihood of being pointed in any direction.

Previous work on the coverage of mobile sensor networks focuses on algorithms to reposition sensors in order to achieve a static configuration with an enlarged covered area. In this paper, we study the dynamic aspects of the coverage of a mobile sensor network that depend on the process of sensor movement. As time goes by, a position is more likely to be covered; targets that might never be detected in a stationary sensor network can now be detected by moving sensors. We characterize the area coverage at specific time instants and during time intervals, as well as the time it takes to detect a randomly located stationary target. Our results show that sensor mobility can be exploited to compensate for the lack of sensors and improve network coverage. For mobile targets, we take a game theoretic approach and derive optimal mobility strategies for sensors and targets from their own perspectives.

In this paper, we take the sample-path approach in analyzing the asymptotic behavior of single-hop bandwidth estimation under bursty cross-traffic and show that these results are provably different from those observed under fluid models of prior work. This difference, which we call the probing bias, is one of the previously unknown factors that can cause measurement inaccuracies in available bandwidth estimation. We present an analytical formulation of "packet probing," based on which we derive several major properties of the probing bias. We then experimentally observe the probing bias and investigate its quantitative relationship to several deciding factors such as probing packet size, probing train length, and cross-traffic burstiness. Both our analytical and experimental results show that the probing bias vanishes as the packet-train length or packet size increases. The vanishing rate is decided by the burstiness of cross-traffic.

We study the coverage properties of large-scale sensor networks. Three coverage measures are defined to characterize the fraction of the area covered by sensors (area coverage), the fraction of sensors that can be removed without reducing the covered area (node coverage), and the capability of the sensor network to detect objects moving in the network (detectability), respectively. We approach the coverage problem from a theoretical perspective and explore the fundamental limits of the coverage of a large-scale sensor network. We characterize the asymptotic behavior of the coverage measures for a variety of sensor network scenarios. We find that the coverage of a sensor network exhibits different behaviors for different network configuration and parameters. Based on the analytical characterizations of the network coverage, we further discuss the implications to network planning and protocol performance of sensor networks.

This paper involves the study of the throughput capacity of hybrid wireless networks. A hybrid network is formed by placing a sparse network of base stations in an ad hoc network. These base stations are assumed to be connected by a high-bandwidth wired network and act as relays for wireless nodes. They are not data sources nor data receivers. Hybrid networks present a tradeoff between traditional cellular networks and pure ad hoc networks in that data may be forwarded in a multihop fashion or through the infrastructure. It has been shown that the capacity of a random ad hoc network does not scale well with the number of nodes in the system. In this work, we consider two different routing strategies and study the scaling behavior of the throughput capacity of a hybrid network. Analytical expressions of the throughput capacity are obtained. For a hybrid network of n nodes and m base stations, the results show that if m grows asymptotically slower than √n, the benefit of adding base stations on capacity is insignificant. However, if m grows faster than √n, the throughput capacity increases linearly with the number of base stations, providing an effective improvement over a pure ad hoc network. Therefore, in order to achieve nonnegligible capacity gain, the investment in the wired infrastructure should be high enough.

We compare four different approaches towards modeling frame-level errors in GSM channels. One of these, the Markov-based trace analysis (MTA) model, was developed for the purpose of modeling a GSM channel. The next two, k/sup th/-order Markov models and hidden Markov models (HMMs) have been widely used to model loss in wired networks. All three of these have difficulty modeling empirical GSM frame-level error traces. The MTA model and HMM predict frame error rates substantially different from that measured from the trace, and all three models have difficulty capturing the long term temporal correlation structure. We propose a fourth model, the extended ON/OFF model, which alternates between an ON (error-free) and an OFF (error-filled) state. The state holding times are taken from mixtures of geometric distributions. We show that this model, with mixtures of three or four geometric distributions, captures first order and second order statistics significantly better than the preceding three approaches.

Wireless links are characterized by high bit error rates and intermittent connectivity. This can result in significant degradation in the performance (goodput) of TCP over wireless networks since non-congestion related packet losses can be misinterpreted by TCP as indications of network congestion, resulting in unnecessary congestion control. In this paper, we propose a technique, TCP with adaptive forward error correction (TCP-AFEC), to improve TCP performance over wireless networks. TCP-AFEC combines the well-established performance characterization of TCP with an understanding of the link layer error control scheme to dynamically select the forward error correction (FEC) that maximizes TCP goodput according to the current channel condition. The benefit of coupling a characterization of TCP performance with link layer FEC to improve TCP goodput is demonstrated by comparing the performance of TCP-AFEC against those of TCP-SACK and Snoop. Simulation results show that TCP-AFEC outperforms TCP-SACK and Snoop for a wide range of wireless channel conditions.

Network performance evaluation through traditional packet-level simulation is becoming increasingly difficult as today's networks grow in scale along many dimensions. As a consequence, fluid simulation has been proposed to cope with the size and complexity of such systems. This study focuses on analyzing and comparing the relative efficiencies of fluid simulation and packet-level simulation for several network scenarios. We use the "simulation event" rate to measure the computational effort of the simulators and show that this measure is both adequate and accurate. For some scenarios, we derive analytical results for the simulation event rate and identify the major factors that contribute to the simulation event rate. Among these factors, the "ripple effect" is very important since it can significantly increase the fluid simulation event rate. For a tandem queueing system, we identify the boundary condition to establish regions where one simulation paradigm is more efficient than the other. Flow aggregation is considered as a technique to reduce the impact of the "ripple effect" in fluid simulation. We also show that WFQ scheduling discipline can limit the "ripple effect", making fluid simulation particularly well suited for WFQ models. Our results show that tradeoffs between parameters of a network model determines the most efficient simulation approach.