Smart homes, medical devices, and education systems, among other emerging cyber-physical systems, hold immense promise for sensing-based user interfaces, especially for using fingers and hand gestures as system input. However, vision approaches compatible with time-consuming image processing adopt low 60 Hz location sampling rate (frame rate) for real-time hand gesture recognition. Furthermore, they are not suitable for low-light environment and long detection range. In this paper, we propose RoFin, which first exploits 6 temporal-spatial 2D rolling fingertips for real-time 3D reconstructing of 20-joint hand pose. RoFin designs active optical labeling for finger identification and enhances inside-frame 3D location tracking via high rolling shutter rate (5-8 kHz). These features enable great potentials for enhanced multi-user HCI, virtual writing for Parkinson suffers, etc. We implement RoFin prototypes with wearable gloves attached with low-power single-colored LED nodes and commercial cameras. The experiment results show that (1) In flexible sensing distances up to 2.5 m, RoFin achieves an average labeling parsing accuracy of 85%, (2) In comparison to vision-based techniques, RoFin improves the tracking grain with 4× more sampled points each frame, (3) RoFin reconstructs a hand pose in real time with 16 mm mean deviation error compared with Leap Motion under flexible distance, and (4) we further investigated real-world applications of RoFin, such as air writing with smoothed trajectories and mobile-based letter/number recognition in our developedXameraapp.

Many computer vision based mobile applications, ranging from simple children's games to complex, safety-critical applications use convolutional neural networks (CNNs) to provide accurate image recognition of both still images and live video streams. Current state-of-the-art CNNs, however, are very computationally complex and not well suited to real-time mobile computation, where computing resources are severely limited. Current work to improve the latency of CNNs on mobile devices include model compression, caching, as well as CNNs designed specifically for mobile use (e.g. MobileNet). All of these approaches, however, suffer from significantly reduced accuracy. In this paper we introduce a class-aware caching scheme for CNNs that provides fast, high-quality image recognition while not sacrificing accuracy. During offline computation, our system learns the most valuable filters for each class of a dataset through our proposed innovative filter ranking algorithm. At inference time we quickly determine the top-5 most likely classifications of an input image using an LSH, which is very fast but not as accurate as a CNN. Then, using the filter rankings we compute the valuable filters for the top-5 predicted classes while re-using previous computations for any others. This allows the CNN to maintain flexibility, and robustness which are often lost with model compression or mobile-based CNNs, while still providing significant latency reduction. Our evaluation shows that we can achieve latency reduction of up to 30 % while providing a similar level of accuracy.

The deployment of satellite constellations for internet access has garnered significant interest in recent years. Current research trends focus on optimizing parameters of uniformly distributed symmetric constellations such as Starlink and Kuiper to better suit evaluation metrics like land coverage or ground station revisit time. These studies largely do not take into account the real distribution of people around the world, nor do they explore the field of Asymmetric Constellations. This work presents a novel optimization algorithm that uniquely designs asymmetric satellite constellations to focus on maximizing population coverage. Through our system evaluation with a fitness function and extensive simulations, our optimized constellations reduce redundancy and enhance efficiency. Results demonstrate that our asymmetrically designed constellations outperform standard uniform constellations in several use cases representing the United States, Europe, and a global scale, highlighting the potential for high-impact satellite deployment.

Self-driving platooning trucks are becoming increasingly common due to the economic gains for companies that utilize them. However, high throughput, long range communication between truck platoons can be very difficult if they are not in areas with pre-built cellular infrastructures. To combat this problem, we propose PlaCoB (Platoon Collaborative Beamforming), which enables multiple platooning trucks to collaboratively beamform to maintain communication over long distances. We conduct extensive simulations under various settings to evaluate PlaCoB’s performance compared to single-truck methods. By leveraging multi-truck platoons, collaborative beamforming, and frequency shifting, (1) PlaCoB can transmit 1.23x more data compared to single vehicle transmission methods, and (2) PlaCoB can transmit data 2.44x further than single vehicle transmission methods. These results demonstrate the effectiveness of our proposed PlaCoB’s approach.

With the proliferation of Internet-of-Things and the advancements in deep learning and Artificial Intelligence, there is an increased need for task-specific mobile devices that can efficiently utilize the wireless spectrum while operating in a wide variety of environments and channel conditions. This work proposes a novel end-to-end Visual-Inertial Odometry architecture that utilizes Semantic Communication-enhanced modulation constellation design for pose estimation of mobile devices. Our proposed model occupies less wireless spectrum bandwidth and does not require complex forward error-correction mechanisms. Yet, it is able to infer the pose information of a remote mobile device with comparable accuracy to a standard wireless Visual-Inertial Odometry system. We propose utilizing a Vision Transformer-based Image-IMU encoder for a network-constrained remote mobile device that transmits wireless encoded data to an Edge receiver. The receiver automatically detects the modulation scheme and decodes the received data for pose estimation. We propose a novel modulation constellation coding design scheme that can transmit data in multiple Modulation and Coding Schemes (MCS) within the same burst, without the need to embed an MCS symbol within the burst. Our proposed receiver can automatically detect the MCS as well. We illustrate how our proposed architecture can transmit encoded Image-IMU data over a wide range of distances and Signal-to-Noise Ratio (SNR) channel conditions and have a decoded pose accuracy comparable to a standard wireless Visual-Inertial Odometry system, with significantly less wireless bandwidth consumption and computational complexity.

Optical wireless communication (OWC) has inherent location aware and spatial reuse advantages over RF-based technologies due to the Line-of-Sight (LoS) propagation of optical signals. Hence, OWC presents a fresh opportunity for effective and secure IoT connectivity and data transmission. However, most OWC systems design transmitter as a point source without considering its spatial diversity in data delivery in 3D space, which is not suitable for real-world mobile IoT connections among devices and users. In this paper, we design and implement HoloCube, which provides 3D optical IoT connections via software defined optical camera communication and Pepper's ghost effect. At the heart of the HoloCube design is multiple virtual 3D hollowed-out cubes with adaptive Spatial-Color Shift Keying (SCSK) modulation. Specifically, the virtual cube seen from various directions has constant structure but embeds different data over time. The cube's positioning elements provide double reference for both 3D reconstruction (spatial) and robust color decoding (spectral). Our comprehensive experiments demonstrate that HoloCube achieves practical 3D omnidirectional IoT connections with 70 Kbps goodput at 4 m in real-world indoor setting.

Computer vision on smartphones is commonly achieved through the use of convolutional neural networks (CNNs). CNNs offer accurate image recognition, but struggle with latency when run with resource constraints. Current work in mobile CNNs aim to improve the latency on mobile devices through techniques such as quantization, model compression, early-exit, caching, etc. While these methods can improve the overall latency of image recognition, they also sacrifice significant accuracy. This problem is compounded by the wide range of pre-trained CNNs that have been released over the past decade. Many of these useful CNNs were developed before innovations that improved the efficiency of CNNs. Anyone attempting to use a CNN trained many years ago may be out of luck.In this paper, we introduce a computation caching scheme paired with early-exit strategies to improve the latency of CNNs on smartphones. Our system has both offline and online components. The offline system is used to find patterns in CNN execution, which are stored on the device. The online component reviews the current state of a CNN execution, determines if it matches a saved pattern, and can choose to forgo the full CNN execution and return a classification immediately. This system improves the speed of image recognition on any smartphone. It also requires no modification to the CNN, and no CNN training, meaning that it can be applied to any CNN that you can find, including many developed years ago. Our system achieves an average latency reduction of 17% while maintaining strong accuracy.

In this paper, we propose WavePurifier, an audio purification framework to defend against audio adversarial attacks. Audio adversarial attacks craft adversarial examples or perturbations to attack the automated speech recognition (ASR) models. Although existing defense mechanisms can detect such attacks and raise alarms, they fail to recover or maintain benign commands. Consequently, this leads to the denial of users' benign commands. Different than existing defenses, WavePurifier aims to purify adversarial examples, thereby rectifying the user's benign commands. We find that the forward diffusion process of the diffusion model effectively eliminates perturbations, whereas the reverse diffusion process restores benign speech. Based on this, we develop a hierarchical diffusion model to defend against audio adversarial examples. This model is capable of purifying different spectrogram bands to varying degrees. To validate the performance of WavePurifier, we purify the adversarial examples from 3 different adversarial attacks in 140 distinct settings. In total, we collect 78,864 diffused spectrograms and 21,000 purified audios. Then, we evaluate WavePurifier on 2 different ASR models, 4 commercial speech-to-text APIs, 2 real-world attack scenarios, and compare them against 7 existing defense approaches. Our result shows that WavePurifier is a universal framework, demonstrating adaptability across diverse attacks with the same hyperparameters. Notably, WavePurifier outperforms existing methods with the lowest character error rate (CER), word error rate (WER), and a high purification success rate against different attacks.

Cellular networks provide the most accessible emergency services with ubiquitous coverage, yet their emergency-specific designs remain largely unexplored. To systematically explore potential design defects that lead to failures or delays in emergency services, we introduce M911-Verifier, an emergency-specific model checking tool. It reveals many counterintuitive findings regarding the ubiquitous access support for cellular emergency services. Our study shows that, despite sufficient wireless signal coverage, users may still experience prolonged emergency call setup times, call initiation failures, or call drops due to flaws in the design of cellular emergency services. These design defects arise from three major causes: problematic network selection for initiating emergency calls, emergency-unaware call operation, and network escalation forbidden during emergency calls. The impacts of these defects have been experimentally validated across three U.S. carriers and two Taiwan carriers using commodity smartphones. Finally, we propose solutions and evaluate their effectiveness.

Beam selection is a fundamental problem in millimeter-wave (mmWave) communication systems. Yet, most existing beam selection techniques focus on the exploitation of spatial channel features to reduce their airtime overhead in stationary mmWave networks. In this article, we exploit the temporal correlation of wireless channels to facilitate beam selection in mobile mmWave networks. Specifically, we present a temporal beam prediction (TBP) scheme for a mobile mmWave device to predict its future beam direction based on its history beam selection profile. TBP has two challenges in its design: 1) nonuniform history data samples due to the bursty nature of data traffic and 2) nonsmooth beam angles over time due to the multipath effect of channels and the imperfect radiation pattern of phased-array antennas. TBP addresses these two challenges by employing a new mobility-aware LSTM model that takes data timestamp for its training, together with an adversarial learning model to exploit user-independent features for beam steering. We have evaluated TBP through over-the-air (OTA) experiments on a 60-GHz mmWave testbed. Experimental results show that the average prediction error of TBP is less than 7° and that TBP improves the throughput by 60% in representative mmWave networks.

Cellular networks, vital for delivering emergency services, enable mobile users to dial emergency calls (e.g., 9–1-1 in the U.S.), which are forwarded to public safety answer points (PSAPs). Regulatory requirements allow anonymous user equipment (UE) without a SIM card or valid mobile subscription to access these services. However, supporting emergency services for anonymous UEs introduces different operations, expanding the attack surface of cellular infrastructure. In this study, we explore the insecurity of cellular emergency services, identifying six security vulnerabilities. These vulnerabilities can be exploited for free data service attacks against carriers and data DoS/overcharge and denial of cellular emergency service (DoCES) attacks against mobile users. Experimental validation in networks of three major U.S. carriers and two major Taiwan carriers demonstrates the global impact of our findings. Finally, we propose and prototype standard-compliant remedies to mitigate these vulnerabilities.

More than 150 cellular networks worldwide have rolled out LTE-M (LTE-Machine Type Communication) and/or NB-IoT (Narrow Band Internet of Things) technologies to support massive IoT services such as smart metering and environmental monitoring. Such cellular IoT services share the existing cellular network architecture with non-IoT (e.g., smartphone) ones. When they are newly integrated into the cellular network, new security vulnerabilities may happen from imprudent integration. In this work, we explore the security vulnerabilities of the cellular IoT from both system-integrated and service-integrated aspects. We discover several vulnerabilities spanning cellular standard design defects, network operation slips, and IoT device implementation flaws. Threateningly, they allow an adversary to remotely identify IP addresses and phone numbers assigned to cellular IoT devices, interrupt their power saving services, and launch various attacks, including data/text spamming, battery draining, device hibernation against them. We validate these vulnerabilities over five major cellular IoT carriers in the U.S. and Taiwan using their certified cellular IoT devices. The attack evaluation result shows that the adversary can raise an IoT data bill by up to${\$}226$with less than 120 MB spam traffic, increase an IoT text bill at a rate of${\$}5$per second, and prevent an IoT device from entering/leaving power saving mode; moreover, cellular IoT devices may suffer from denial of IoT services. We finally propose, prototype, and evaluate recommended solutions.

Optical wireless communication (OWC) shows great potential due to its broad spectrum and the exceptional intensity switching speed of LEDs. Under poor conditions, most OWC systems switch from complex and more error prone high-order modulation schemes to more robust On-Off Keying (OOK) modulation defined in the IEEE OWC standard. This paper presents LiFOD, a high-speed indoor OOK-based OWC system with fine-grained dimming support. While ensuring fine-grained dimming, LiFOD remarkably achieves robust communication at up to 400 Kbps at a distance of 6 meters. This is the first time that the data rate has improved via OWC dimming in comparison to the previous approaches that consider trading off dimming and communication. LiFOD makes two key technical contributions. First, LiFOD utilizes Compensation Symbols (CS) as a reliable side-channel to represent bit patterns dynamically and improve throughput. We firstly design greedy-based bit pattern mining. Then we propose 2D feature enhancement via YOLO model for real-time bit pattern mining. Second, LiFOD synchronously redesigns optical symbols and CS relocation schemes for fine-grained dimming and robust decoding. Experiments on low-cost Beaglebone prototypes with commercial LED lamps and the photodiode (PD) demonstrate that LiFOD significantly outperforms the state-of-the-art system with 2.1× throughput on the SIGCOMM17 data-trace.

Optical Camera Communication (OCC) appears as a promising technology to provide secure and pervasive wireless services with users' daily smart devices. Rolling shutter based modulations can improve the frequency response of the camera. This paper introduces a 2D Rolling Block (2DRB) based OCC modulation to use un-exploited spatial diversity to improve OCC's data rate for real-world applications. 2DRB outperforms traditional 1D strip based modulations. Using our 2DRB prototype with commercial devices, we show a significant data rate enhancement. We also discuss one promising real-world use case: indoor office integrated lighting and communication.

Speaker Verification (SV) is widely deployed in mobile systems to authenticate legitimate users by using their voice traits. In this work, we propose a backdoor attack MasterKey, to compromise the SV models. Different from previous attacks, we focus on a real-world practical setting where the attacker possesses no knowledge of the intended victim. To design MasterKey, we investigate the limitation of existing poisoning attacks against unseen targets. Then, we optimize a universal backdoor that is capable of attacking arbitrary targets. Next, we embed the speaker's characteristics and semantics information into the backdoor, making it imperceptible. Finally, we estimate the channel distortion and integrate it into the backdoor. We validate our attack on 6 popular SV models. Specifically, we poison a total of 53 models and use our trigger to attack 16,430 enrolled speakers, composed of 310 target speakers enrolled in 53 poisoned models. Our attack achieves 100% attack success rate with a 15% poison rate. By decreasing the poison rate to 3%, the attack success rate remains around 50%. We validate our attack in 3 real-world scenarios, and successfully demonstrate the attack through both over-the-air and over-the-telephony-line scenarios.

Smart homes, medical devices, and education systems, among other emerging cyber-physical systems, hold immense promise for sensing-based user interfaces, especially for using fingers and hand gestures as system input. However, vision approaches compatible with time-consuming image processing adopt low 60 Hz location sampling rate (frame rate) for real-time hand gesture recognition. Furthermore, they are not suitable for low-light environment and long detection range. In this paper, we propose RoFin, which first exploits 6 temporal-spatial 2D rolling fingertips for real-time 3D reconstructing of 20-joint hand pose. RoFin designs active optical labeling for finger identification and enhances inside-frame 3D location tracking via high rolling shutter rate (5--8 KHz). These features enable great potentials for enhanced multi-user HCI, virtual writing for Parkinson suffers, etc. We implement RoFin prototypes with wearable gloves attached with low-power single-colored LED nodes and commercial cameras. The experiment results show that (1) In flexible sensing distances up to 2.5 m, RoFin achieves an average labeling parsing accuracy of 85%. (2) In comparison to vision-based techniques, RoFin improves the tracking grain with 4× more sampled points each frame. (3) RoFin reconstructs a hand pose in real time with 16 mm mean deviation error compared with Leap Motion under flexible distance.

In this paper, we propose PhantomSound, a query-efficient black-box attack toward voice assistants. Existing black-box adversarial attacks on voice assistants either apply substitution models or leverage the intermediate model output to estimate the gradients for crafting adversarial audio samples. However, these attack approaches require a significant amount of queries with a lengthy training stage. PhantomSound leverages the decision-based attack to produce effective adversarial audios, and reduces the number of queries by optimizing the gradient estimation. In the experiments, we perform our attack against 4 different speech-to-text APIs under 3 real-world scenarios to demonstrate the real-time attack impact. The results show that PhantomSound is practical and robust in attacking 5 popular commercial voice controllable devices over the air, and is able to bypass 3 liveness detection mechanisms with success rate. The benchmark result shows that PhantomSound can generate adversarial examples and launch the attack in a few minutes. We significantly enhance the query efficiency and reduce the cost of a successful untargeted and targeted adversarial attack by 93.1% and 65.5% compared with the state-of-the-art black-box attacks, using merely ∼ 300 queries (∼ 5 minutes) and ∼ 1,500 queries (∼ 25 minutes), respectively.

Drones are gaining more interest thanks to their advantages and great potential for applications. However, present swarming drones’ stand-alone centralized radio frequency control mode from a base station has non-trivial drawbacks such as severe interference, latency caused localization error, etc. Differently, optical camera communication (OCC) is promising as an alternative for integrated communication and sensing for swarming drones. We propose PoseFly, the first 4-in-1 OCC approach for swarming drones. With exploited rolling shutter effect and the already installed camera and LED nodes, PoseFly provides (1) massive drone indication and identification, (2) multilevel on-site localization, (3) quick-link channel among drones, and (4) basic lighting. The design methodology of PoseFly gives a valuable example for the low-cost integrated sensing and communication for swarming drones.

Drones are gaining more interest from the industry and the research community as a result of their many advantages, including low cost, small size, adaptability, and ease of use, as well as their potential applications. However, current control of swarming drones relies on stand-alone modes and centralized radio frequency control from a base station on the ground which is devoid of drone-to-drone communication. This method has drawbacks, including a crowded RF spectrum with mutual interference, high latency, and a lack of on-site drone-to-drone interactions. Because of its high spatial multiplexing capability, Line of Sight (LoS) security capabilities, broader bandwidth, and intuitive vision manner, Optical Camera Communication (OCC) is considered to be a potential alternative for sensing and communication in drone clusters. In this paper, we first utilize the rolling shutter effect in drone sensing and communication and propose PoseFly, a 4-in-1 AI-assisted OCC with drone identification, on-site localization, quick-link communication and lighting. We implement PoseFly prototypes on commercial drones, cameras and LEDs. Our experiments show our PoseFly achieves nearly 100% accuracy for distance estimation (20m), drone identification (12m), angle and speed estimation (4m) and 5 Kbps average quick-link throughput at up to 4 m on current prototypes.

One of the leading enabling technologies of 5G wireless networks is to use the millimeter wave spectrum band. Despite its large and wide frequency bandwidth, the obtained data rate can be diminished due to link blockage in this frequency band. In this paper, we formulate a bi-objective optimization problem to optimize user association in cellular networks with millimeter wave enabled base stations. The two objectives to minimize are maximum base station utility and blockage score (to indicate the chance of a link getting blocked). We simulate three different scalarization methods to turn a bi-objective vector into a scalar. Since the combinatorial bi-objective problem is NP-Hard, we conduct Lagrangian dual analysis on all of the scalarization methods. Solving the dual problem decreases the time complexity of the solver algorithm, but the solution has a distance from the optimal point created by solving the primal. We also solve the primal optimization problem with a single objective optimization tool. Compared to the time complexity of the primal problem of scalarization methods, the time complexities of solutions to the dual problems are lower. The results show that our solution to the bi-objective optimization problem has a better outcome in terms of the number of link blockage and the maximum base station utility compared to optimizing each objective alone.

Voice-activated systems are integrated into a variety of desktop, mobile, and Internet-of-Things (IoT) devices. However, voice spoofing attacks, such as impersonation and replay attacks, in which malicious attackers synthesize the voice of a victim or simply replay it, have brought growing security concerns. Existing speaker verification techniques distinguish individual speakers via the spectrographic features extracted from an audible frequency range of voice commands. However, they often have high error rates and/or long delays. In this paper, we explore a new direction of human voice research by scrutinizing the unique characteristics of human speech at the ultrasound frequency band. Our research indicates that the high-frequency ultrasound components (e.g. speech fricatives) from 20 to 48 kHz can significantly enhance the security and accuracy of speaker verification. We propose a speaker verification system, SUPERVOICE that uses a two-stream DNN architecture with a feature fusion mechanism to generate distinctive speaker models. To test the system, we create a speech dataset with 12 hours of audio (8,950 voice samples) from 127 participants. In addition, we create a second spoofed voice dataset to evaluate its security. In order to balance between controlled recordings and real-world applications, the audio recordings are collected from two quiet rooms by 8 different recording devices, including 7 smartphones and an ultrasound microphone. Our evaluation shows that SUPERVOICE achieves 0.58% equal error rate in the speaker verification task, which reduces the best equal error rate of the existing systems by 86.1%. SUPERVOICE only takes 120 ms for testing an incoming utterance, outperforming all existing speaker verification systems. Moreover, within 91 ms processing time, SUPERVOICE achieves 0% equal error rate in detecting replay attacks launched by 5 different loudspeakers. Finally, we demonstrate that SUPERVOICE can be used in retail smartphones by integrating an off-the-shelf ultrasound microphone.

In this paper, we propose SpecPatch, a human-in-the loop adversarial audio attack on automated speech recognition (ASR) systems. Existing audio adversarial attacker assumes that the users cannot notice the adversarial audios, and hence allows the successful delivery of the crafted adversarial examples or perturbations. However, in a practical attack scenario, the users of intelligent voice-controlled systems (e.g., smartwatches, smart speakers, smartphones) have constant vigilance for suspicious voice, especially when they are delivering their voice commands. Once the user is alerted by a suspicious audio, they intend to correct the falsely-recognized commands by interrupting the adversarial audios and giving more powerful voice commands to overshadow the malicious voice. This makes the existing attacks ineffective in the typical scenario when the user's interaction and the delivery of adversarial audio coincide. To truly enable the imperceptible and robust adversarial attack and handle the possible arrival of user interruption, we design SpecPatch, a practical voice attack that uses a sub-second audio patch signal to deliver an attack command and utilize periodical noises to break down the communication between the user and ASR systems. We analyze the CTC (Connectionist Temporal Classification) loss forwarding and backwarding process and exploit the weakness of CTC to achieve our attack goal. Compared with the existing attacks, we extend the attack impact length (i.e., the length of attack target command) by 287%. Furthermore, we show that our attack achieves 100% success rate in both over-the-line and over-the-air scenarios amid user intervention.

In this paper, we propose NEC (Neural Enhanced Cancellation), a defense mechanism, which prevents unautho-rized microphones from capturing a target speaker’s voice. Compared with the existing scrambling-based audio cancellation approaches, NEC can selectively remove a target speaker’s voice from a mixed speech without causing interference to others. Specifically, for a target speaker, we design a Deep Neural Network (DNN) model to extract high-level speaker-specific but utterance-independent vocal features from his/her reference audios. When the microphone is recording, the DNN generates a shadow sound to cancel the target voice in real-time. Moreover, we modulate the audible shadow sound onto an ultrasound frequency, making it inaudible for humans. By leveraging the non-linearity of the microphone circuit, the microphone can accurately decode the shadow sound for target voice cancellation. We implement and evaluate NEC comprehensively with 8 smartphone microphones in different settings. The results show that NEC effectively mutes the target speaker at a microphone without interfering with other users’ normal conversations.

Long Range Wide Area Network (LoRaWAN), using the linear chirp for data modulation, is known for its low-power and long-distance communication to connect massive Internet-of-Things devices at a low cost. However, LoRaWAN throughput is far behind the demand for the dense and large-scale IoT deployments, due to the frequent collisions with the by-default random channel access (i.e., ALOHA). Recently, some works enable an effective LoRa carrier-sense for collision avoidance. However, the continuous back-off makes the network throughput easily saturated and degrades the energy efficiency at LoRa end nodes. In this paper, we propose CurveALOHA, a brand-new media access control scheme to enhance the throughput of random channel access by embracing non-linear chirps enabled quasi-orthogonal logical channels. First, we empirically show that non-linear chirps can achieve similar noise tolerance ability as the linear one does. Then, we observe that multiple nonlinear chirps can create new logical channels which are quasi-orthogonal with the linear one and each other. Finally, given a set of non-linear chirps, we design two random chirp selection methods to guarantee an end node can access a channel with less collision probability. We implement CurveALOHA with the software-defined radios and conduct extensive experiments in both indoor and outdoor environments. The results show that CurveALOHA’s network throughput is 59.6% higher than the state-of-the-art carrier-sense MAC.

Cellular networks that offer ubiquitous connectivity have been the major medium for delivering emergency services. In the U.S., mobile users can dial an emergency call with 911 for emergency uses in cellular networks, and the call can be forwarded to public safety answer points (PSAPs), which deal with emergency service requests. According to regulatory authority requirements for the cellular emergency services, anonymous user equipment (UE), which does not have a SIM (Subscriber Identity Module) card or a valid mobile subscription, is allowed to access them. Such support of emergency services for anonymous UEs requires different operations from conventional cellular services, and can therefore increase the attack surface of the cellular infrastructure. In this work, we are thus motivated to study the insecurity of the cellular emergency services and then discover four security vulnerabilities from them. Threateningly, they can be exploited to launch not only free data service attacks against cellular carriers, but also data DoS/overcharge and denial of cellular emergency service (DoCES) attacks against mobile users. All vulnerabilities and attacks have been validated experimentally as practical security issues in the networks of three major U.S. carriers. We finally propose and prototype standard-compliant remedies to mitigate the vulnerabilities.

Underwater optical wireless communication techniques are promising due to a broad bandwidth with a long communication range compared with existing expensive acoustic and RF-based underwater communication techniques. For underwater navigation assistance during dive and rescue, it is more practical to adopt passive optical tags for objects/human identification and location-based services. However, existing optical tags (bar/QR codes) employ one/two dimensional designs, which lack significant element/symbol distance for robust decoding and full-directional localization capabilities for underwater navigation tasks. This paper investigates opportunities to increase the element distance in passive low-order optical tags by exploiting 3D spatial diversity. Specifically, we design U-Star, a system that consists of Underwater Optical Identification (UOID) tags and commercial camera-based tag readers for underwater navigation. Our UOID tags embed rich location and guidance information. Additionally, because our UOID tags employ a three-dimensional design, they can also determine the relative location of a user in real-time based on the perspective principles. We design AI based mobile algorithms for underwater denoising, relative positioning, and robust data parsing for tag readers. Finally, we evaluate U-Star on real UOID tag prototypes under different underwater scenarios. Results show that our 3-order UOID tag can embed 21 bits with a BER of 0.003 at 1m and less than 0.05 at up to 3m, which is sufficient for underwater navigation guidance with backup database.

Many emerging multimedia mobile applications rely heavily upon image recognition of both static images and live video streams. Image recognition is commonly achieved using deep neural networks (DNNs) which can achieve high accuracy but also incur significant computation latency and energy con-sumption on resource-constrained smartphones. Recent efforts addressing these issues include cloud offloading and reducing the complexity of the DNNs, which, however, introduce increased network latency or reduced accuracy. In-memory caching has also been explored to assess the similarity of images as opposed to exact matching. However, such approximate caching systems often treat devices as static nodes, and do not fully utilize the mobile and collaborative nature of smartphones without outside infrastructure. Another consequence of treating nodes as static is the necessity of cache sizes larger than what is feasible for individual mobile applications. In this paper we introduce Co-Cache, a in-memory caching paradigm that supports infrastructure-less collaborative compu-tation reuse in smartphone image recognition. Co-Cache utilizes the inertial movement of smartphones, the locality inherent in video streams, as well as information from nearby, peer-to-peer devices to maximize the computation reuse opportunities in mobile image recognition. Compared to other caching systems, our extensive evaluation shows that Co-Cache can reduce the required number of cache entries by 50–70 % while lowering the average latency of standard image recognition applications by up to 94 % with minimal loss of recognition accuracy.

Optical wireless communication (OWC) shows great potential for high-speed communication due to its broad spectrum and the exceptional intensity switching speed of LEDs. Under poor conditions, most OWC systems switch from complex and more error prone high-order modulation schemes to the more robust On-Off Keying (OOK) modulation defined in the IEEE OWC standard. This paper presents LiFOD, a high-speed indoor OOK-based OWC system with fine-grained dimming support. While ensuring fine-grained dimming, LiFOD remark-ably achieves robust communication at up to 400 Kbps at a distance of 6 meters. This is the first time that the data rate has improved via OWC dimming in comparison to the previous approaches that consider trading off dimming and communication. LiFOD makes two key technical contributions. First, LiFOD utilizes Compensation Symbols (CS) as a reliable side-channel to represent bit patterns dynamically and improve throughput. Second, LiFOD synchronously redesigns optical symbols and CS relocation schemes for fine-grained dimming and robust decoding. Experiments on low-cost Beaglebone prototypes with commercial LED lamps and the photodiode (PD) demonstrate that LiFOD significantly outperforms the state-of-art system with at least 2.1x throughput on the SIGCOMM17 data-trace.

Sensing-based user interfaces hold enormous potential for smart homes, medical equipment, educational systems, AR/VR/MR, etc. However existing hand and body gesture recognition systems are mostly based on frame-level computer vision approaches, which have limitations such as the inability to operate in the environment with low brightness, short detection distance, without the objective identification ability, and coarse-grained tracking when the objectives are in high-speed motion. Therefore, in this paper, we propose to attach active LED elements on objectives and utilize rolling shutter effect to enhance the gesture recognition and achieve the fine-grained motion tracking with objective identification.

Nowadays, Bitcoin is the most popular cryptocurrency. With the proliferation of smartphones and the high-speed mobile Internet, more and more users have started accessing their Bitcoin wallets on their smartphones. Users can download and install a variety of Bitcoin wallet applications (e.g., Coinbase, Luno, Bitcoin Wallet) on their smartphones and access their Bitcoin wallets anytime and anywhere. However, it is still unknown whether these Bitcoin wallet smartphone applications are secure or if they are new attack surfaces for adversaries to attack these application users. In this work, we explored the insecurity of the 10 most popular Bitcoin wallet smartphone applications and discovered three security vulnerabilities. By exploiting them, adversaries can launch various attacks including Bitcoin deanonymization, reflection and amplification spamming, and wallet fraud attacks. To address the identified security vulnerabilities, we developed a phone-side Bitcoin Security Rectifier to secure Bitcoin wallet smartphone application users. The developed rectifier does not require any modifications to current wallet applications and is compliant with Bitcoin standards.

Many emerging mobile applications rely heavily upon image recognition of both static images and live video streams. Image recognition is commonly achieved using deep neural networks (DNNs) which can achieve high accuracy but also incur significant computation latency and energy consumption on resource-constrained smartphones. We introduce an in-memory caching paradigm that supports infrastructure-less collaborative computation reuse in smartphone image recognition. We propose using the inertial movement of smartphones, the locality inherent in video streams, as well as information from nearby, peer-to-peer devices to maximize the computation reuse opportunities in mobile image recognition. Experimental results show that our system lowers the average latency of standard mobile neural network image recognition applications by up to 94% with minimal loss of recognition accuracy.

More than 150 cellular networks worldwide have rolled out massive IoT services such as smart metering and environmental monitoring. Such cellular IoT services share the existing cellular network architecture with non-IoT (e.g., smartphone) ones. When they are newly integrated into the cellular network, new security vulnerabilities may happen from imprudent integration. In this work, we explore the security vulnerabilities of the cellular IoT from both system-integrated and service-integrated aspects. We discover five vulnerabilities spanning cellular standard design defects, network operation slips, and IoT device implementation flaws. Threateningly, they allow an adversary to remotely identify IP addresses and phone numbers assigned to cellular IoT devices and launch data/text spamming attacks against them. We experimentally validate these vulnerabilities and attacks with three major U.S. IoT carriers. The attack evaluation result shows that the adversary can raise an IoT data bill by up to $226 with less than 120 MB spam traffic and increase an IoT text bill at a rate of $5 per second; moreover, cellular IoT devices may suffer from denial of IoT services. We finally propose, prototype, and evaluate recommended solutions.

Low-Power Wide-Area Networks (LPWANs) are an emerging Internet-of-Things (IoT) paradigm marked by low-power and long-distance communication. Among them, LoRa is widely deployed for its unique characteristics and open-source technology. By adopting the Chirp Spread Spectrum (CSS) modulation, LoRa enables low signal-to-noise ratio (SNR) communication. However, the standard demodulation method does not fully exploit the properties of chirp signals, thus yields a sub-optimal SNR threshold under which the decoding fails. Consequently, the communication range and energy consumption have to be compromised for robust transmission. This paper presents NELoRa, a neural-enhanced LoRa demodulation method, exploiting the feature abstraction ability of deep learning to support ultra-low SNR LoRa communication. Taking the spectrogram of both amplitude and phase as input, we first design a mask-enabled Deep Neural Network (DNN) filter that extracts multi-dimension features to capture clean chirp symbols. Second, we develop a spectrogram-based DNN decoder to decode these chirp symbols accurately. Finally, we propose a generic packet demodulation system by incorporating a method that generates high-quality chirp symbols from received signals. We implement and evaluate NELoRa on both indoor and campus-scale outdoor testbeds. The results show that NELoRa achieves 1.84-2.35 dB SNR gains and extends the battery life up to 272% (~0.38-1.51 years) in average for various LoRa configurations.

Thanks to the popularity of smartphones, optical camera communication (OCC) gains more and more attention from markets and research as one of the new internetworking architectures in the future. However, existing OCC modulations treat the signal from the transmitter as a single point light source, which sacrifices the spatial diversity and limits the data rate improvement. In this paper, we investigate the spatial diversity, a natural feature of camera imaging, and propose to combine spatial diversity with amplitude and spectrum diversities to boost the data rate of OCC to support high-speed applications. Based on preliminary experiments, we design and implement RainbowRow, a high-speed and robust OCC system. RainbowRow comprises a LED-based transmitter and a camera-based receiver, which is low-cost (i.e., under $100), with a flexible communication range (i.e., within 2 m), and high speed (i.e., up to 40 Kbps). To validate the RainbowRow performance, we conduct experiments on LabVIEW based platforms in different scenarios. Results show that RainbowRow can robustly recognize the optical symbols with a symbol error rate (SER) less than 0.05 and approach 40 Kbps data rate in the range of 1 m, significant improvement from less than 10 Kbps in OCC state of the art.

Millimeter-wave technology has proved to be one of the enabling technologies of the fifth generation of wireless networks. Despite the merits of the millimeter-wave spectrum, its directionality imposes more overhead on communication systems than the non-millimeter wave spectrum. In this paper, we propose using signaling in another frequency band to discover the paths surrounding a receiver working in the millimeter-wave spectrum. In this way, the receiver does not have to do an expensive beam scan in the millimeter wave band and repair the interrupted ongoing millimeter communication much faster by choosing the beam covering the best path discovered by another frequency band. Our experiments in various environments by millimeterwave hardware platforms show that a non-millimeter wave frequency band's paths can be used to align the beams in millimeterwave frequency. Existing out-of-band path discovery methods typically need a specially designed hardware for scanning and can only find the single line-of-sight path. Our proposed method uses commercial off-the-shelf products to perform out-of-band scanning and discover both line-of-sight path and non-line-of-sight paths for millimeter wave communication.

The emerging 5G adopts OFDM modulation and deploys small-cell amplify and forward (AF) relays for in-cell capacity enhancement and energy efficiency. However, hybrid delivery services for multiple users where broadcast and unicast coexist are inefficient and unfair due to their different QoS requirements. Most existing work considering hybrid broadcast and unicast traffic focuses on different scheduling schemes in onehop scenarios. For dual-hop relay networks, subcarrier mapping or pairing has been studied, but none considers hybrid traffic with both broadcast and unicast. In this paper, we propose an effective subcarrier pairing (ESP) protocol, which exploits the performance diversity in subcarrier pairing at relays to improve the overall performance of hybrid broadcast and unicast traffic. ESP exquisitely pairs subcarriers of two hops into two kinds of subcarrier pairs separately. ESP then allocates subcarrier pairs with low outage probability for broadcast and subcarrier pairs with high capacity for unicast. In ESP design, we study several important metrics such as end-to-end outage probability, capacity, and bit-error-rate (BER) in AF assisted OFDM-CDMA relay networks. We conduct Monte Carlo simulations to verify the effectiveness and fairness of our approach in hybrid transmission. Results show that ESP is efficient in hybrid delivery for relay networks and improves the performance of broadcast services significantly without sacrificing unicast services.

OFDMA femtocell is a promising technology to improve indoor cellular network coverage cost-effectively. Large-scale deployment of femtocells in the urban area is expected to be realized in the near future. However, inter-femtocell interference significantly limits the achievable throughput of an OFDMA femtocell system, which calls for interference management tailored for femtocell networks. A typical approach to mitigate inter-femtocell interference is known as resource isolation, which aims at assigning non-overlapping resources to interfering femtocells. One of the main challenges for interference mitigation in femtocell networks is that end consumers often install the femtocells. Very limited information about the femtocells is available, making it hard to decipher the inter-femtocell interference. Previous studies either take time to resolve collisions online or adopt a conservative approach to identify interferers. Although the latter approach avoids wasting time on resolving collisions, it may result in resource underutilization. In this paper, we propose an efficient method to identify inter-femtocell interference by analyzing the received patterns observed by mobile stations. We conducted experiments on GNU Radio/USRP to demonstrate that the proposed interference identification method can successfully identify real interferers while excluding non-interfering femtocells from suspect femtocells. Based on the proposed interference identification, we propose a weighted vertex-coloring based resource assignment algorithm to allocate resources with better fairness and higher throughput.

To employ millimeter wave technology in the 5G standard, two inherent challenges need to be addressed in dynamic outdoor environments. Firstly, different types of obstacles can easily block the links. Secondly, the link quality can drop significantly in a mobile environment. It is critical to discriminate between the two different situations to take appropriate actions. The existing work to make the distinction is based on RSSI variation measured in a time window, which is very time-consuming leading to large volume of data loss in order to achieve high accuracy. In this paper, we propose a learning-based prediction framework to classify link blockage and link movement efficiently and quickly. A classifier is trained with data blockage instances using different learning methods and is used to make a prediction based on diffraction values on different multipath components formed around a receiver. The simulations show that the prediction framework can predict blockage with close to 90% accuracy. The prediction framework will eliminate the need for having time-consuming methods to discriminate between link movement and link blockage. Experiments show that our framework does not need large amount of training data to get to the desired prediction accuracy.

Cooperative relaying in cognitive radio networks offers time and space diversity and thereby, provides an effective technique to improve spectrum utilization. Most of the existing research has been focused on adopting this technique in single hop communication which may not fully exploit the benefits of cooperative transmissions. Recently, multi-hop cooperative relaying has been explored in routing path formation between primary transmitter-receiver pairs. In this approach, each user handles one cooperation request at a time and takes part in at most one routing path, which makes the model unscalable and limits the benefits of cooperation. Also, primary users dictate the cooperation terms with no or limited involvement from the participating secondary users. This model, therefore, cannot capture the dynamics when both the primary and secondary users require to make cooperation decisions considering the tradeoffs of multiple offers. As a result, the essence of multi-hop cooperative relaying cannot be realized from the existing approach and calls for further investigation. In this work, we consider a network of coexisting primary and secondary users in which their intention to improve throughput via mutual cooperation is formulated as an overlapping coalition formation game. Based on the analysis of the game, we devise mcRoute, a distributed multi-hop coalition based cooperative routing and scheduling algorithm that forms stable coalitions satisfying users' mutual interest. A primary user constructs its routing path in the form of a coalition with secondary users relaying its packet. A secondary user takes part in one or more coalitions by relaying corresponding primary packets and accessing their channels for its own transmission. Finally, we analyze the performance of the algorithm through extensive numerical simulations.

In recent years mobile computing has been rapidly expanding to the point that there are now more devices than there are people. While once it was common for every household to have one PC, it is now common for every person to have a mobile device. With the increased use of smartphone devices, there has also been an increase in the need for mobile ad hoc networks, in which phones connect directly to each other without the need for an intermediate router. Most modern smart phones are equipped with both Bluetooth and Wifi Direct, where Wifi Direct has a better transmission range and rate and Bluetooth is more energy efficient. However only one or the other is used in a smartphone ad hoc network. We propose HSNet, a framework to enable the automatic switching between Wifi Direct and Bluetooth to emphasize minimizing energy consumption while still maintaining an efficient network. We develop an application to evaluate the HSNet framework which shows significant energy savings when utilizing our switching algorithm to send messages by a less energy intensive technology in situations where energy conservation is desired. We discuss additional features of HSNet such as load balancing to help increase the lifetime of the network by more evenly distributing slave nodes among connected master nodes. Finally, we show that the throughput of our system is not affected due to technology switching for most scenarios.

mmWave bands have large chunks of spectrum and are promising for satisfying the unprecedented cellular traffic demands of future cellular networks. Unfortunately, the characteristic that mmWaves have high attenuation against physical objects and even atmosphere hinder its feasibility. High gain directional antennas are required to combat the attenuation. However, user mobility might change the signal direction, introduce physical objects in the line-of-sight of the signal and might block the directional signal. Additionally, user mobility might also make two directional signals to interfere with one another. The blockage and interference incidents must be handled with care. In this paper, the mmWave-enabled HetNet cells record the fingerprints of the incidents and the cells' transmission parameters. When a user is moving, and the serving cell's transmission parameters are approaching a fingerprint, the HetNet takes necessary actions to mitigate interference or avoid disconnection before it happens. Our results show that for typical indoor scenarios, most of the blockage and interference can be predicted so that countermeasures can be applied in advance.

In cognitive radio networks (CRNs), the established communication sessions between secondary users (SUs) may be affected or even get interrupted because the SUs need to relinquish the spectrum when the licensed users (PUs) appear and reclaim the spectrum/channel. On detecting PU activities, the SUs on the affected links either switch to another available idle spectrum using the same link or the SUs seek for an alternative path/link. In either approach, the ongoing session is destined to experience delay or even gets interrupted, which is intolerable to quality of service-sensitive applications such as multimedia streaming or audio/video conferencing. In this paper, we study the problem of establishing k-protected routes in CRNs. A k-protected route consists of a set of main links with preassigned backup spectrum and backup paths and is guaranteed to sustain from k PU appearances without being interrupted. For a CRN, we find a k-protected route for each session request and maximize the number of sessions that can be supported. We propose both centralized and distributed k-protected routing algorithms for this problem. Simulation results show that our k-protected routing protocol outperforms existing opportunistic spectrum switching approaches in terms of delay and interruption rate.

mm-Wave is a promising technology to meet the enormous bandwidth demands of the future generation cellular networks. This technology has vast amount of unused bandwidth, but has problem of human blockage. Blockage mitigation methods for indoor environments cannot be applied to outdoor scenarios effectively. In this paper, we mitigate human blockage of the mm-Wave technology by proposing an algorithm that provides intelligent user association in mm-Wave networks. The proposed algorithm collects the history blockage incidents throughout the network and exploits the history incidents to associate user equipment to the base station with lower blockage possibility. The blockage incidents happened at different locations in the network. When user equipment attempts to find a base station to associate to, the algorithm examines the history blockage incidents near the location of the user equipment. In this way, the user equipment is associated to a base station that has smaller chance of being blocked. The simulation results show that our proposed algorithm is performing better in terms of improving SINR, rate of the links and blockage rate in the network compared to another state-of-the-art user association algorithm designed for mm-Wave networks and common user association algorithms of associating user to closest base station and base station with maximum SINR.

The allocation of underutilized spectrum from primary users to secondary users in real time is likely the most promising avenue for advancing efficiency of spectrum use given the ever-increasing demand for transmission. Research in this area has focused on auctions to facilitate the distribution of spectrum, inducing truthful reporting by participants. However, most research has assumed a static or partially dynamic setting. These approaches are unable to capture that spectrum becomes available at random intervals as primary users' needs vary across time; and, similarly, secondary users' needs vary over time. Moreover, frequently there is flexibility regarding the time of transmission - with some transmissions being more urgent and time-sensitive than others. Therefore, existing research cannot be directly applied to such auction environments involving users with variable transmission deadlines, while preserving efficiency and truthfulness. In this work, we design SOADE, a strategyproof online auction mechanism in dynamic environments that considers dynamic arrival of bidders with varying transmission deadlines and dynamic availability of spectrum. SOADE builds on a priority function that determines the rank of a bidder of winning spectrum at an auction considering its valuation, deadline, and uncertainty associated with dynamic arrival of bidders and spectrum availability. We analytically prove that SOADE is truthful and ex ante and ex post individually rational. Finally, we perform numerical simulation to demonstrate the efficiency of SOADE and show that it improves auction revenue compared to prior work.

Online spectrum auctions will play a pivotal role in restructuring the existing spectrum allocation system given growing spectrum demand from users with diverse requirements. The research in this field mainly concentrates on designing truthful mechanisms in a static or partially dynamic setting. This setting, however, does not capture the fact that spectrum becomes available according to primary users' activities, and the reserve price for this unused spectrum differs from one primary user to another. The number of secondary users with spectrum demand, their transmission deadlines, and their valuations for their transmissions also vary in time and space. Existing research cannot ensure truthful reporting of participants in presence of such diversity in demand and supply. In this work, we consider such a dynamic secondary market and present two spectrum allocation and pricing algorithms. The first algorithm requires distribution knowledge of bidders and sellers, and assesses the winning probability and payment amount of participants based on a priority function. The second algorithm determines the payment amount by exploring the interference relationships between bidders, their transmission deadlines and valuations without any distribution knowledge. We analytically prove that both these algorithms satisfy three desired auction properties - truthfulness, individual rationality, and budget balance. Finally, we present simulation results to analyze the performance of these two algorithms under different auction settings.

Cooperative relaying in cognitive radio networks offers time and space diversity and thereby, provides a useful technique to improve spectrum utilization. Most of the existing research has adopted this technique in single hop communication which may not fully exploit the benefits of cooperative transmissions. So, the essence of multi-hop cooperative relaying cannot be realized from the existing research and needs further investigation. In this work, we consider a network of coexisting primary and secondary users in which their intention to improve throughput via mutual cooperation is formulated as an overlapping coalition formation game. Based on the analysis of the game, we devise mcRoute, a distributed multi-hop coalition based cooperative routing and scheduling algorithm that forms stable coalitions satisfying users' mutual interest. A primary user constructs its routing path in the form of a coalition with secondary users relaying its packet. A secondary user takes part in one or more coalitions by relaying corresponding primary packets and accessing their channels for its own transmission. Finally, we analyze the performance of the algorithm through extensive numerical simulations.

Network densification by installing more cellular stations (cells) with smaller coverage is a promising technique to improve wireless capacity to meet the overwhelming demands for mobile data usage. These smaller cells with different coverage and the macrocellular base station form heterogeneous cellular networks (HetNet). However, the dense deployment of HetNet cells might result in unexpected inter-cell interference. In cellular networks, the data to all cells and to the mobile stations (MSs) are originated from the core cellular network. We take advantage of this characteristic and propose a technique called interference precancellation. If the interferer to an MS is identified, the victim cell that serves the victim MS transmits the interference precanceled signal, which is the signal intended for the victim MS subtracts the interference signal. The interference precanceled signal and the interference signal scramble at the victim MS and become the intended signal. With interference precancellation, the interferer and the victim cell can utilize the same wireless resources and thus the capacity is further improved. However, some MSs are interference-free and for MSs whose exact interferers cannot be determined, the MSs still require isolated resources. We propose an algorithm for resource management with interference precancellation (RMIP) that jointly considers MSs experiencing different level of interference. Through experiments on GNURadio/USRP, we show that the known interference signal can be precanceled and the combination of the interference signal and the precanceled signal becomes the intended signal. Through simulation, we evaluate the performance in larger HetNets.

In cognitive radio (CR) networks, control channels are needed for secondary users (SUs) to perform certain handshaking procedures to negotiate communication parameters and to exchange control messages. The process of SUs attempting to meet on a channel is known as rendezvous. Previous studies either use a dedicated control channel or adopt channel-hopping schemes to rendezvous. However, it is not realistic to designate a preselected control channel in licensed spectrum bands and the time consumption for channel hopping grows drastically. Moreover, a requirement of previous studies is that a common channel must be available across the whole network at all SUs. Such a channel might not exist and the SUs cannot form an effective CR network. This paper proposes an efficient approach for guaranteed NC-OFDM-based Control Channel (NCCC) establishment by utilizing subcarrier pulses. Simulation results show that the time needed for establishing control channel is lower than that of channel hopping schemes. Additionally, the proposed approach is able to establish NCCC even if there is no common channel in the CR network. NC-OFDM-based control interfaces improve the control channel establishment rate even when the interface can only access the spectrum bandwidth that is equal to one channel.

The pursuit of high speed wireless communication is pushing wireless networks toward wider channels. Narrowband interference and frequency- selective fading significantly impact the performance of broadband wireless communication. To cope with the harsh channel conditions, orthogonal frequency division multiplexing (OFDM), which divides a band of spectrum into numerous subcarriers that carry data in parallel, is widely adopted. Because subcarriers experience different channel qualities in a wide band of spectrum, different modulation schemes may be used for different subcarriers. This paper exploits the modulation scheme diversity as rich information to assist data transmission. In this paper, we propose encoding each modulation scheme with a bit pattern that occurs frequently when allocating data bits to subcarriers. If the bits to be allocated on a subcarrier match the bit pattern defined on the subcarrier, the receiver is informed by the transmitter through subcarrier nulling. Because the bit pattern usually consists of more bits than that can be represented by a modulation symbol in low-density modulation schemes, the total transmission time is shortened. Further, detecting a null subcarrier is more reliable than decoding a modulation symbol. Therefore, the known bits represented by the selected bit patterns help improve decoding performance. Through experiments on USRP1 we show that the throughput is increased due to shortened transmission time and reduced bit error rates.

To support applications that demand high-speed wireless communication, the fifth generation (5G) Wi-Fi increases the channel bonding from 40 MHz in 802.11n to 80, and even 160 MHz under certain conditions in 802.11ac. However, inefficiency and unfairness issues arise when devices that use different channel widths coexist in a contention domain. In this paper, we propose a dynamic channel bonding (DyB) protocol in which a node is allowed to start a transmission as long as there are some idle narrow channels and it gradually increases the channel width during transmission whenever new narrow channels become available. To enable communication over uncertain channels, a convolution method is introduced to achieve fast spectrum agreement between the transmitter and the receiver. In addition, DyB considers the severe contention in a wide band of spectrum. A compound preamble is designed to make collisions detectable in the frequency domain and a parallel bitwise arbitration is designed to quickly resolve the collisions in the time domain. We implement and evaluate the DyB through both the GNU Radio/USRP platform and ns-2 simulations. Experimental results and simulations show that DyB well addresses the inefficiency and unfairness issues caused by heterogeneous radio coexistence.

Duty cycling improves energy efficiency but limits throughput and introduces significant end-to-end delay in wireless sensor networks. In this article, we present a traffic-adaptive synchronous MAC protocol (TAS-MAC), which is a high-throughput, low-delay MAC protocol tailored for low power consumption. It achieves high throughput by adapting time division multiple access (TDMA) to a novel traffic-adaptive allocation mechanism that assigns time slots only to nodes located on active routes. TAS-MAC reduces the end-to-end delay by notifying all nodes on active routes of incoming traffic in advance. These nodes will claim time slots for data transmission and forward a packet through multiple hops in a cycle. The desirable traffic-adaptive feature is achieved by decomposing traffic notification and data-transmission scheduling into two phases, specializing their duties and improving their efficiency, respectively. Simulation results and experiments on TelosB motes demonstrate that the two-phase design significantly improves the throughput of current synchronous MAC protocols and achieves the similar low delay of slot-stealing-assisted TDMA with much lower power consumption.

To improve spectrum utilization, cognitive radio (CR) is introduced to detect and exploit available spectrum resources autonomously. The flexible spectrum use imposes special challenges on broadcast because different CR devices may detect different available spectrum fragments at different locations. The sender and the receivers have to agree on spectrum fragments that will be used for broadcast. There may not exist a common spectrum fragment that is available to all receivers. Most existing work assumes that a device works only in a single channel and thus the sender has to broadcast multiple times in different channels to reach all receivers. The broadcast problem is studied as a channel rendezvous and minimum latency scheduling problem. Recent spectrum-agile designs have enabled a device to utilize partially occupied spectrum. We thus view a wideband channel as an aggregation of multiple narrow channels that can be evaluated independently. A Spectrum Fragment Agile Broadcast (SFAB) scheme is introduced in this paper to support efficient broadcast on fragmented spectrum. It aims at achieving spectrum agreement between the transmitter and the receivers efficiently and maximizing the channel width used for broadcast regardless of the spectrum availability differences at receivers. We validate the effectiveness of SFAB through implementation on the GNU Radio / USRP platform and use ns-2 simulations to evaluate the performance in large deployments.

In this paper, we study the cooperation model to design and develop a system that improves the reception rate of delay sensitive packets in realtime applications. While making a cooperation decision, a user with real-time traffic must consider the queue size, packet deadline, the traffic rate, channel condition. Existing cooperation models do not take these factor into consideration and therefore, are not applicable to the improvement of reliability of real-time traffic. We formulate the cooperation model using a Markov decision process (MDP) which is NP-Hard. The MDP-based optimization problem of a single pair of primary and secondary user is analyzed to find the optimum transmission decision in different states of the network. Based on the findings of a single pair case, we develop a distributed cooperation algorithm where a user (primary or secondary) quantifies the immediate and future impact of cooperation and takes its decision accordingly. Extensive simulation is performed to evaluate the performance of the proposed cooperation algorithm which reveals its efficacy compared to the non-cooperative scheme.

Event-driven wireless sensor networks (WSNs) usually operate under light traffic load. However, when an event is detected, a large number of packets may be generated. A MAC protocol designed for this kind of WSNs should be able to swiftly adapt to the two conditions. Most WSN MAC protocols are optimized for light traffic for the energy efficiency consideration. In this paper, we propose a novel receiver-centric MAC protocol called RC-MAC that seamlessly integrates duty cycling and receiver-centric scheduling, providing high throughput without sacrificing the energy efficiency. To handle bursty traffic triggered by an event, RC-MAC takes advantage of the underlying data gathering tree structure of WSNs and the multichannel technique supported by current IEEE 802.15.4 RF transceivers to assist scheduling of medium access. The throughput is improved in two phases with receiver-centric medium access scheduling and distributed channel assignment. First, on a data gathering tree, a receiver is able to coordinate the medium access of multiple senders so as to reduce collisions and achieve high throughput. Second, different receivers coordinate their senders in different channels and the throughput is further improved by allowing parallel data gathering. Observing packet processing time on low cost sensor nodes, we design a scheduling pattern that ensures fairness between source nodes without sacrificing the throughput. We evaluate the performance of our RC-MAC through measurements of an implementation in TinyOS on TelosB motes and extensive ns-2 simulations. Compared with contention-based and scheduling-based MAC protocols, we show that the throughput and the fairness under heavy traffic load are significantly improved by the receiver-centric scheduling. Due to the high throughput, the energy efficiency is also improved.

In this paper, we present the design and development of a miniature robot that is able to run and jump. This robot can use wheeled locomotion to travel on the flat ground. When it encounters a large obstacle compared to its size, it can stand up and leap over the obstacle. The robot has a mass of 25 grams and a maximum size of 9 centimeters. Experimental results show that with a take-off angle 80°, the robot can jump up to 1.44 meter in height and 0.59 meter in distance. Moreover, it has on-board energy, control, and communication abilities, which enables tetherless or autonomous operation. With the multi-modal locomotion abilities, the robot is expected to have many applications ranging from environmental monitoring, search and rescue, to military surveillance.

In mobile ad-hoc cognitive radio networks (CRMANET), accurately identifying primary user spectrum occupancy is an important requirement in successful utilization of the spectrum by the secondary user. This is made difficult by malicious mobile secondary users launching spectrum sensing data falsification (SSDF) attacks, byzantine failures of devices, primary user signal fading, and hidden terminal problems. Another ability of these malicious users is to use their mobility to hide under the changing neighborhood. Existing state of the art techniques either consider a centralized approach in decision making or when considering an ad-hoc network, do not take into account the mobility of the devices which adds unique limitations. We present a light weight multi-fusion based distributed spectrum sensing scheme (MFDSS) in a mobile ad-hoc secondary user network to overcome the aforementioned problems. MFDSS allows each secondary user to collect semi-global information to make decisions in a distributed manner. It uses outlier detection and data fusion to remove incorrect sensing data generated by byzantine failures. Reputation information of the devices is used to suppress a SSDF attack. MFDSS incorporates a reputation propagation and fusion scheme to prevent malicious devices from hiding behind changing topology and to maintain the freshness of the reputation information. Additionally, MFDSS includes an incubation period to discourage devices from changing identity to perform a Sybil attack or to mask a bad reputation. Detailed analysis is presented and the results show significant improvement in correct primary user spectrum occupancy identification. We also show that without the reputation propagation of MFDSS, a malicious device is able to move its position and hide its malicious intentions in the new neighborhood.

Inter-femtocell interference significantly limits the achievable throughput of an OFDMA femtocell system, which calls for interference management tailored for femtocell net-works. A typical approach to mitigate inter-femtocell interference is known as resource isolation, which aims at assigning nonoverlapping resources to interfering femtocells. One of the main challenges for interference mitigation in femtocell networks is that the femtocells are often installed by end-consumers without any pre-planning. Very limited information about the femtocells is available, making it hard to decipher the inter-femtocell interference. In this paper, we propose an efficient method to identify inter-femtocell interference by analyzing the received patterns observed by mobile stations. We conducted experiments to demonstrate that the proposed interference identification method can successfully identify real interferers while excluding non-interfering femtocells from suspicious interferers. Based on the proposed interference identification, we propose a weighted vertex-coloring based resource assignment algorithm to allocate resources with better fairness and achieve higher throughput.

IEEE 802.22 is the first standard based on the concept of cognitive radio. It recommends collaborative spectrum sensing to avoid the unreliability of individual spectrum sensing while detecting primary user signals. However, it opens an opportunity for attackers to exploit the decision making process by sending false reports. In this paper, we address security issues regarding distributed node sensing in the 802.22 standard and discuss how attackers can modify or manipulate their sensing result independently or collaboratively. This problem is commonly known as spectrum sensing data falsification (SSDF) attack or Byzantine attack. To counter the different attacking strategies, we propose a reputation based clustering algorithm that does not require prior knowledge of attacker distribution or complete identification of malicious users. We provide an extensive probabilistic analysis of the performance of the algorithm. We compare the performance of our algorithm against existing approaches across a wide range of attacking scenarios. Our proposed algorithm displays a significantly reduced error rate in decision making in comparison to current methods. It also identifies a large portion of the attacking nodes and greatly minimizes the false detection rate of honest nodes.

Cognitive radio appears as a promising technology to allocate wireless spectrum between licensed and unlicensed users in an efficient way. When unlicensed users opportunistically utilize spectrum holes, prediction models that infer the availability of spectrum holes can help to improve the spectrum extraction rate and reduce the collision rate. In this paper, a spectrum occupancy prediction model based on Partial Periodic Pattern Mining (PPPM) is introduced. The mining aims at identifying frequent spectrum occupancy patterns that are hidden in the spectrum usage of a channel. The mined frequent patterns are then used to predict future channel states (i.e., busy or idle). Based on the prediction, unlicensed users are able to utilize spectrum holes aggressively without introducing significant interference to licensed users. PPPM outperforms traditional Frequent Pattern Mining (FPM) by considering real patterns that do not repeat perfectly due to noise, sensing errors, and irregular behaviors. Using real-world Wi-Fi and personal communication service (PCS) activities, we show a significant reduction on miss rate in channel state prediction. With the proposed prediction mechanism, the performance of Dynamic Spectrum Access (DSA) is substantially improved. Further, we extend the three-state PPPM to an N-state PPPM to predict the duration of high/low utilization in a channel. The frequent patterns of channel utilization duration are critical in optimizing channel switch strategies. The high prediction accuracy is validated with data collected in the paging bands.

To support applications that demand high-speed wireless communication, the ongoing standardization of the next generation Wi-Fi increases the channel bonding from 40 MHz in 802.11n to 80, and even 160 MHz under certain conditions in 802.11ac. However, inefficiency and unfairness issues arise when devices that use different channel widths coexist in a contention domain. In this paper, we propose a dynamic channel bonding (DyB) protocol in which a node is allowed to start a transmission as long as there are some idle narrow channels and it gradually increases channel width during transmission whenever new narrow channels become available. A challenge is the communication over uncertain channels. To enable fast spectrum agreement between transmitter and receiver, a partial spectrum correlation method is introduced. In addition, DyB considers the severe contention in a wide band of spectrum. A compound preamble is designed to make collisions detectable in the frequency domain and a parallel bitwise arbitration is used to quickly resolve the collisions in the time domain. We implemented and evaluated the DyB through both the GNU Radio/USRP platform and ns-2 simulations. Experimental results and simulations show that DyB can well address the inefficiency and unfairness issues caused by heterogeneous radio coexistence.

Advancements in wireless communication techniques have increased the wireless physical layer (PHY) data rates by hundreds of times in a dozen years. The high PHY data rates, however, have not been translated to commensurate throughput gains due to overheads incurred by medium access control (MAC) and PHY convergence procedure. At high PHY data rates, the time used for collision avoidance (CA) at MAC layer and the time used for PHY convergence procedure can easily exceed the time used for transmission of an actual data frame. Recent work intends to reduce the CA overhead by reducing the backoff time slot size. However, the method introduces more collisions in presence of hidden terminals because the tiny backoff slots can no longer de-synchronize hidden terminals, leading to persistent collisions among hidden terminals. As collision detection (CD) in wireless communication became feasible recently, some protocols migrate random backoff from the time domain to the frequency domain, but they fail to address the introduced high collision probability. We investigate the practical issues of CD in the frequency domain and introduce a binary mapping scheme to reduce the collision probability. Based on the binary mapping, a bitwise arbitration (BA) mechanism is devised to grant only one transmitter the permission to initiate data transmission in a contention. With the low collision probability achieved in a short bounded arbitration phase, the throughput is significantly improved by our proposed WiFi-BA. Because collisions are unlikely to happen, unfairness caused by capture effect of radios is also reduced. The bitwise arbitration mechanism can further be set to let high priority messages get through unimpeded, making WiFi-BA suitable for real time prioritized communication. We validate the effectiveness of WiFi-BA through implementation on FPGA of USRP E110. Performance evaluation demonstrates that WiFi-BA is more efficient than current Wi-Fi solutions.

In this paper, we present the design and experimentation of a miniature robot that can jump, run, and perform aerial maneuvering. Specifically, this robot can use wheeled locomotion to run on the ground. Encountering an obstacle, it can jump up to overcome the obstacle. After leaping into the air, the robot can control its body angle using its tail for aerial maneuvering. To the best of our knowledge, this is the first miniature (maximum size 6.5 centimeters) and lightweight (28.0 grams) robot that having all the three capabilities. Furthermore, this robot is equipped with on-board energy, sensing, control, and wireless communication capabilities, which enables the tetherless operation. It can be potentially employed for mobile sensor networks in environments with obstacles.

To support high data rate applications such as multimedia streaming, the ongoing standardization of the next generation Wi-Fi increases the channel bonding from 40 MHz in 802.11n to 80, and even 160 MHz under certain conditions in 802.11ac. However, inefficiency and unfairness issues arise when devices that use different channel widths coexist in a contention domain. A device with channel bonding has to wait until all bonded channels to be idle to commence a transmission while narrow channel interferers have more channel access opportunities. To address the inefficiency and unfairness issues in channel bonding, we propose an adaptive channel bonding (ACB) protocol in which a node is allowed to initiate a transmission as long as a narrow channel is available and gradually increase channel width during transmission whenever a new narrow channel becomes available. ACB aggregates all available narrow channels as one wide channel, removing the need of setting guard bands between contiguous narrow channels. A challenge in the design is the communication over uncertain channels. To enable fast spectrum agreement between transmitter and receiver, a partial spectrum correlation method is introduced. ACB also considers the severe contention in a wide band of spectrum. When new channels become available, multiple nodes may contend for them. A compound preamble is designed to make collisions detectable in the frequency domain and a parallel bitwise arbitration mechanism is introduced to quickly resolve the collisions in the time domain. We implemented and evaluated the ACB through the GNU Radio/USRP platform. Experimental results show that ACB can well address the inefficiency and unfairness issues caused by heterogeneous radio coexistence.

Duty cycling improves energy efficiency but limits throughput and introduces significant end-to-end delay in wireless sensor networks. In this paper, we present a traffic-adaptive synchronous MAC protocol (TAS-MAC), which is a high throughput low delay MAC protocol tailored for low power consumption. It achieves high throughput by using Time Division Multiple Access (TDMA) with a novel traffic-adaptive allocation mechanism that assigns time slots only to nodes located on active routes. TAS-MAC reduces the end-to-end delay by notifying all nodes on active routes of incoming traffic in advance. These nodes will claim time slots for data transmission and forward a packet through multiple hops in a cycle. The desirable traffic-adaptive feature is achieved by decomposing traffic notification and data transmission scheduling into two phases, specializing their duties and improving their efficiency respectively. Simulation results and tests on TelosB motes demonstrate that the two-phase design significantly improves the throughput of current synchronous MAC protocols and achieves the similar low delay of slot stealing assisted TDMA with much lower power consumption.

In cognitive radio networks, secondary users need to accurately identify primary user spectrum occupancy in order to use it. Accurate spectrum sensing is hindered by signal fading, hidden terminal problems, byzantine failures, etc. Centralized cooperative spectrum sensing works well if the secondary user network is infrastructure based and there is a centralized basestation making network wide decisions. When the secondary users network is a cognitive radio mobile ad-hoc network (CR-MANET), then decisions need to be made in a distributed manner and cooperative spectrum sensing introduces additional problems due to the presence of malicious users. These malicious secondary users encourage other secondary users to make a wrong spectrum occupancy decision by feeding inaccurate measurements. We study this problem and present a solution to improve primary user spectrum occupancy identification accuracy in the presence of malicious users. A virtual neighbor cluster is created in which the mobile device forms an evolving cluster of past neighbor devices that aids in validating the input gathered from the current neighboring devices. Next, a recursive partitioning around medoids based clustering is performed to identify a tightly bound set of valid inputs. The validated inputs from both the methods form a decision cluster and the data is fused to get the decision on primary user occupancy. Two data fusion strategies are presented and their use depends on the amount of dynamism in the CR-MANET. The analysis and results show the accuracy of primary user occupancy detection even in the presence of large number of malicious users and signal measurement errors.

Many efforts have been devoted to maximizing network throughput in a multichannel multiradio wireless mesh network. Most current solutions are based on either purely static or purely dynamic channel allocation approaches. In this paper, we propose a hybrid multichannel multiradio wireless mesh networking architecture, where each mesh node has both static and dynamic interfaces. We first present an Adaptive Dynamic Channel Allocation protocol (ADCA), which considers optimization for both throughput and delay in the channel assignment. In addition, we also propose an Interference and Congestion Aware Routing protocol (ICAR) in the hybrid network with both static and dynamic links, which balances the channel usage in the network. Our simulation results show that compared to previous works, ADCA reduces the packet delay considerably without degrading the network throughput. The hybrid architecture shows much better adaptivity to changing traffic than purely static architecture without dramatic increase in overhead, and achieves lower delay than existing approaches for hybrid networks.

Cognitive radio (CR), which enables dynamic access of underutilized licensed spectrums, is a promising technology for more efficient spectrum utilization. Since cognitive radio enables the access of larger amount of spectrum, it can be used to build wireless mesh networks with higher network capacity, and thus provide better quality of services for high bit-rate applications. In this paper, we study the multisource video on-demand application in multi-interface cognitive wireless mesh networks. Given a video request, we find a joint multipath routing and spectrum allocation for the session to minimize its total bandwidth cost in the network, and therefore maximize the number of sessions the network can support. We propose both distributed and centralized routing and channel allocation algorithms to solve the problem. Simulation results show that our algorithms increase the maximum number of concurrent sessions that can be supported in the network, and also improve each session's performance with regard to spectrum mobility.

Securing a sensor network poses a variety of problems. Of those, an important one is of providing privacy to the event-detecting sensor node and integrity to the data gathered by the node. Compromised source privacy can inadvertently leak event location. Safeguarding the privacy of the source node is important, as sensor networks hold critical roles in military application, tracking endangered species, etc. Existing techniques in sensor networks use either random walk path or generate fake event packets to make it hard for an adversary to trace back to the source, since encryption alone may not help prevent a traffic analysis attack. In this work, without using traditional overhead-intensive methods, we present a scheme for hiding source information using cryptographic techniques incurring lower overhead. The packet is modified en route by dynamically selected nodes to make it difficult for a malicious entity to trace back the packet to a source node and also to prevent packet spoofing. This is important because the adversary model considers a super-local eavesdropper having the ability to compromise sensor nodes. Additionally, we provide a method for the base station to recover corrupted packets and identify the location of the compromised node. We analyze the ability of our proposed scheme to withstand different attacks and demonstrate its efficiency in terms of overhead and functionality when compared to existing work.

This paper together with the accompanied video presents our improved single motor actuated miniature jumping robot. The robot has a maximum size 6.5 centimeter and a mass 23.5 gram. It can jump towards a desired direction and jump continuously. With a take-off angle 75°, the average jumping height is 0.9 meter. In the video, the detailed robot design is illustrated, and experiments in various situations are presented. These scenarios suggest potential applications of such miniature jumping robots such as surveillance, environmental monitoring, or locomotion in environments with obstacles.

Cognitive radio appears as a promising technology to allocate wireless spectrum between licensed and unlicensed users. Predictive methods for inferring the availability of spectrum holes can help to reduce collision and improve spectrum extraction. This paper introduces a Partial Periodic Pattern Mining (PPPM) algorithm to identify frequent spectrum occupancy patterns that are hidden in the spectrum usage of a channel. The mined frequent patterns are then used to predict future channel states (i.e., busy or idle). PPPM outperforms traditional Frequent Pattern Mining (FPM) by considering real patterns that do not repeat perfectly. Using real life network activities, we show a significant reduction on miss rate in channel state prediction.

Cognitive radio appears as a promising technology to allocate wireless spectrum between licensed and unlicensed users in an efficient way. The availability of spectrum holes vastly affects the throughput and delay of unlicensed users. Predictive methods for inferring the availability of spectrum holes can help to improve spectrum extraction rate and reduce collision rate. In this paper, a spectrum occupancy prediction model based on Partial Periodic Pattern Mining (PPPM) is introduced. The mining aims to identify frequent spectrum occupancy patterns that are hidden in the spectrum usage of a channel. The mined frequent patterns are then used to predict future channel states (i.e., busy or idle). Based on the prediction, unlicensed users will be able to make use of spectrum holes efficiently without introducing significant interference to licensed users. PPPM outperforms traditional Frequent Pattern Mining (FPM) by considering real patterns that do not repeat perfectly due to noise, sensing errors, and irregular behaviors. Using real life network activities we show a significant reduction on miss rate in channel state prediction. With the proposed prediction mechanism, the performance of Dynamic Spectrum Access (DSA) is substantially improved.

In this paper, we exploit mutual cooperation between primary and secondary users to reduce delay in packet transmission in a cognitive network. More formally, we present a delay optimization problem based on the cooperation model and show that the problem is NP-Hard. The mutual benefit through cooperation is analyzed using a time dependent priority queueing system. Analytical simulation results are presented to validate the proposed cooperation model.

In this paper, we study the distributed channel selection problem in a cognitive network. We consider a time varying channel environment where secondary users do not have any prior knowledge of primary transmission and independently learn about existing channels without any explicit communication with other users. To solve this problem, we address the impact of switching between channels during the learning process that is mostly ignored in literature. We propose a scalable distributed block learning algorithm that minimizes the switching cost, adapts to time varying channel conditions, and achieves logarithmic regret. Simulation results show that our algorithm performs significantly better than the existing ones.

A cut vertex is defined as a network node whose removal increases the number of network components. Failure of a cut vertex disconnects a network component and downgrades the network performance. Overlay networks are resilient to the failure of random nodes, but cut vertices that have been observed in real-world overlay traces make the network very vulnerable to well-constructed and targeted attacks. Traditional methods of detecting cut vertices are centralized and are very difficult, if not impossible, to be applied to large-scale and highly dynamic overlay networks. We aim to provide a practical solution by proposing a distributed mechanism that detects the cut vertices and neutralizes them to noncut vertices before they fail. The proposed mechanism not only minimizes the possibility of network decomposition on the cut vertex failure but also offloads the traffic that is handled by the cut vertices. We prove that our proposed method can correctly identify the cut vertices. We evaluate the performance of our design through trace-driven simulations. The results show that our method can successfully locate all cut vertices in the network and greatly offload the traffic processed by cut vertices.

Wireless mesh networks have attracted great interest in the research community recently. Much effort has been devoted to maximizing the network performance using limited channel resources in a multichannel multiradio wireless mesh network. It is believed that the limited spectrum resource can be fully exploited by utilizing partially overlapping channels in addition to nonoverlapping channels in 802.11b/g networks. However, there are only few studies of channel assignment algorithms for partially overlapping channels. In this paper, we first formulate the optimal channel assignment problem with the goal of maximizing the overall network throughput or maximizing the throughput of a multicast application. For both cases, we present a greedy algorithm for partially overlapping channel assignment, and then propose a novel genetic algorithm, which has the potential to obtain better solutions. Through evaluation, we demonstrate that the overall network throughput can be dramatically improved by properly utilizing the partially overlapping channels. The genetic algorithm outperforms the greedy algorithm in mitigating the network interference, and therefore leads to higher network throughput. In addition, the multicast throughput can also be dramatically improved by using our algorithms compared to previous work.

We study the multisource video on-demand (VoD) application in multichannel multiradio wireless mesh networks. When a user initiates a new video request, the application can stream the video not only from the media servers, but also from the peers that have buffered the video. The multipath multisource video on-demand streaming has been applied in wired networks with great success. However, it remains a challenging task in wireless networks due to wireless interference. In this paper, we first focus on the problem of finding the maximum number of high-quality and independent paths from the user to the servers or peers for each VoD request by considering the effect of wireless interference. We formulate it as a constrained maximum independent paths problem and propose two efficient heuristic path discovery algorithms. Based on the multiple paths discovered, we further propose a joint routing and rate allocation algorithm, which minimizes the network congestion caused by the new VoD session. The algorithm is aware of the optimization for both existing and potential VoD sessions in the wireless mesh network. We evaluate our algorithms with real video traces. Simulation results demonstrate that our algorithm not only improves the average video streaming performance over all the coexisting VoD sessions in the network, but also increases the network's capacity of satisfying more subsequent VoD requests.

Greedy forwarding is a simple yet efficient technique employed by many routing protocols. It is ideal to realize point-to-point routing in wireless sensor networks because packets can be delivered by only maintaining a small set of neighbors' information regardless of network size. It has been successfully employed by geographic routing, which assumes that a packet can be moved closer to the destination in the network topology if it is forwarded geographically closer to the destination in the physical space. This assumption, however, may lead packets to the local minimum where no neighbors of the sender are closer to the destination or low-quality routes that comprise long distance hops of low packet reception ratio. To address the local minimum problem, we propose a topology aware routing (TAR) protocol that efficiently encodes a network topology into a low-dimensional virtual coordinate space where hop distances between pairwise nodes are preserved. Based on precise hop distance comparison, TAR can assist greedy forwarding to find the right neighbor that is one hop closer to the destination and achieve high success ratio of packet delivery without location information. Further, we improve the routing quality by embedding a network topology based on the metric of expected transmission count (ETX). ETX embedding accurately encodes both a network's topological structure and channel quality to nodes' small size virtual coordinates, which helps greedy forwarding to guide a packet along the optimal path that has the fewest number of transmissions. We evaluate our approaches through both simulations and experiments, showing that routing performance are improved in terms of routing success ratio and routing cost.

With respect to ground level, wireless communication signal strength increases with the elevation of communicating wireless sensor network devices, within practical bounds. Jumping sensors are mobile sensors that provide relocation capabilities and a temporary increase in elevation can be utilized for improving communication. This paper provides a comprehensive multidimensional analysis for jumping sensors. It studies the main factors that impact the Received Signal Strength (RSS) in sensor communication, and performs a comparative analysis between theoretical and experimental results. Sensor elevation from ground level is a key factor, which is often neglected, and plays an important role for successful wireless communication. The impact of jump height manipulation on a jumping sensor to the packet transmission goodput is presented. An airborne two-way communication scheme is defined and studied with experiments. The results indicate the effectiveness of utilizing the change in elevation of a jumping sensor to increase communication range. Since energy is at premium in sensor nodes, the operational energy cost of a jumping sensor prototype is studied in detail. A jumping sensor network is simulated with the parameters learned from the experimental results and the jumping sensor prototype analysis. Simulation results show the enhancement in connectivity and the feasibility of a jumping sensor network.

A miniature robot with continuous jumping ability is presented in this paper. The robot has a dimension about 6cm×8cm×2cm and weighs 20 grams. To achieve continuous jumping, various mechanisms are needed including the jumping mechanism, energy store and release mechanism, self-righting mechanism, and jumping direction changing mechanism. The design and analysis for those mechanisms are elaborated in this paper. Moreover, implementation and experimental results are also presented. It is shown that the robot can jump higher than 55cm with a 75° takeoff angle. The robot can be used as mobile sensors and deployed in the areas of rugged terrain and natural obstacles which are not suitable for sensors with wheels.

We study the multi-source video on-demand application in multi-channel multi-radio wireless mesh networks. When a user initiates a new video request, the application can stream the video not only from the media servers, but also from the peers that have buffered the video. The multi-path multi-source video on-demand streaming has been applied in wired networks with great success. However, it remains a challenging task in wireless networks due to wireless interference. In this paper, we first focus on the problem of finding the maximum number of high-quality and independent paths from the user to the servers or peers for each VoD request by considering the effect of wireless interference. We formulate it as a constrained maximum independent paths problem, and propose two efficient heuristic path discovery algorithms. Based on the multiple paths discovered, we further propose a joint routing and rate allocation algorithm, which minimizes the network congestion caused by the new VoD session. The algorithm is aware of the optimization for both existing and potential VoD sessions in the wireless mesh network. We evaluate our algorithms with real video traces. Simulation results demonstrate that our algorithm not only improves the average video streaming performance over all the coexisting VoD sessions in the network, but also increases the network's capacity of satisfying more subsequent VoD requests.

In a sensor network, an important problem is to provide privacy to the event detecting sensor node and integrity to the data gathered by the node. Compromised source privacy can inadvertently leak event location. Existing techniques use either random walk path or generate fake event packets to make it hard for the adversary to traceback to the source, since encryption alone may not help prevent a traffic analysis attack. In this work, without using the traditional overhead intensive methods, we present a scheme to hide source information using cryptographic techniques incurring lower overhead. The packet is modified en route by dynamically selected nodes to make it difficult for a malicious entity to traceback the packet to a source node and also prevent packet spoofing. This is important because the adversary model considers a super-local eavesdropper having the ability to compromise sensor nodes. We analyze the ability of our proposed scheme to withstand different attacks and demonstrate its efficiency in terms of overhead and functionality when compared to existing work.

In this paper, we address the channel selection problem with switching cost and propose a distributed learning approach that minimizes the sum regret while ensuring quick convergence to an optimal solution and logarithmic regret. Our algorithm is adaptive in the sense that it adapts to the changing idle status of channels and achieves logarithmic regret even in a dynamic environment. The experimental result shows that our algorithm outperforms the existing algorithm in terms of regret, scalability and channel switching cost.

In this paper, we propose a new opportunistic multicast protocol to improve multicast throughput in Wireless Mesh Networks (WMN). It builds upon opportunistic routing (OR) strategies that have been designed to improve unicast throughput in wireless networks. The key concept in our multicast protocol is a tree backbone. Our tree backbone protocol represents a tradeoff between traditional structured multicast protocols where a complete multicast tree is constructed and unstructured protocols where multicast is treated as a collection of unicasts. Tree backbone selects multiple nodes as intermediate nodes. Each pair of upstream and downstream nodes may be multiple hops away, and packet delivery between them takes advantage of OR. For single-rate WMNs, we show that constructing an efficient tree backbone that minimizes the number of transmissions is NP-hard, and we devise one effective heuristic algorithm for it. For multi-rate WMNs, we investigate the inherent rate-distance tradeoff and propose a Euclidean opportunistic multicast protocol by devising a Euclidean tree backbone as well as an efficient rate selection scheme to minimize the number of transmissions. In our simulations, our tree backbone multicast protocols outperform both the completely structured traditional multicast protocols and the completely unstructured unicast-based protocols augmented with OR in both throughput and delay.

Mobile sensors with jumping ability provide several advantages compared with the traditional wheeled sensors such as ability to move in rugged terrain. A controllable jumping robot for this purpose is described in this paper. The robot has dimension about 9.5cm × 9cm × 3cm and weighs 54.1 grams. It can perform the jumping process continuously. This paper focuses on the mechanisms to achieve such a continuous jumping ability, including the jumping mechanism, energy store and release mechanism, and self-righting mechanism. Detail implementation and experimental results are also given in this paper. It is shown that with a 75° takeoff angle, the robot can jump about 20cm in height.

Wireless sensor networks usually operate under light traffic loads. However, when an event is detected, a large volume of data may be generated and delivered to the sink. The demand for simultaneous data transmission may cause severe channel collision and thus decrease communication throughput in contention-based medium access control (MAC) protocols. In this paper, we introduce a novel receiver-centric data transmission paradigm, which takes advantage of the tree structure that is naturally formed in data collection of a sensor network to assist scheduling of channel access. On the tree structure, a receiver is able to coordinate its multiple senders' channel access so as to reduce channel contention and consequently improve communication throughput. The protocol seamlessly integrates scheduling with contention-based medium access control. In addition, to ensure reliable data transmission, we propose a sequence-based lost packet recovery scheme in a hop-by-hop recovery pattern, which could further improve communication throughput by reducing control overhead. We present the performance of our receiver-centric MAC protocol through measurements of an implementation in TinyOS on TelosB motes and extend the evaluation through ns-2 simulations. Compared with B-MAC and RI-MAC, we show the benefits of improving throughput and fairness through receiver-centric scheduling under heavy traffic loads.

Cognitive radio, which enables dynamic access of under-utilized licensed spectrums, is a promising technology for more efficient spectrum utilization. Since cognitive radio enables the access of larger amount of spectrum, it can be used to build wireless mesh networks with higher network capacity, and thus provide better quality of services for high bit-rate applications. In this paper, we study the multi-source video on-demand application in multiinterface cognitive wireless mesh networks. Given a video request, we find a joint multi-path routing and spectrum allocation for the session to minimize its total bandwidth cost in the network, and therefore maximize the number of sessions the network can support. We propose both distributed and centralized routing and channel allocation algorithms to solve the problem. Our algorithms not only increase the maximum number of concurrent sessions that can be supported in the network, but also improve each session's adaptivity to spectrum mobility.

In TDMA based wireless mesh networks, routing and scheduling algorithms are essential to provide QoS support for mesh clients. In order to maximize the network throughput and minimize session delay, the routing and scheduling algorithms should produce a minimum length schedule. A linear programming formulation enables an optimal solution, however has very high computational cost. In this paper, we consider network scenarios where multiple orthogonal channels are available. With a channel assignment algorithm to eliminate secondary interference, we are able to use a scheduling algorithm that yields the minimum length schedule given a specific routing tree. We then propose a heuristic routing algorithm that aims to build the routing tree that results in the minimum length schedule. Our routing algorithm performs significantly better than simple routing algorithms, which are based on Breadth First Search or Dijkstra algorithms.

Multihoming load balancing improves network performance and makes better use of network resource by leveraging the traffic among the access links in a multihomed network. Currently, no effective load balancing system is available to handle the inbound traffic in a multihomed stub network, where the traffic volume is unknown to the network and the route of the traffic is hard to control. In this paper, we propose ILBO, an inbound traffic load balancing mechanism to effectively balance the inbound traffic in a multihomed stub network. ILBO predicts and schedules the inbound traffic based on outbound traffic. It adopts a two-step traffic predictor to increase the prediction accuracy and also provides an inbound traffic control scheme that can guarantee the successful execution of the traffic scheduling. We have evaluated the effectiveness of ILBO in a trace driven simulation with real world traffic traces collected from multihomed stub networks.

The wireless mesh network is an emerging technology that provides high quality service to end users as the "last milerdquo of the Internet. Furthermore, multicast communication is a key technology for wireless mesh networks. Multicast provides efficient data distribution among a group of nodes. However, unlike other wireless networks, such as sensor networks and MANETs, where multicast algorithms are designed to be energy efficient and to achieve optimal route discovery among mobile nodes, wireless mesh networks need to maximize throughput. This paper proposes two multicast algorithms: the level channel assignment (LCA) algorithm and the multichannel multicast (MCM) to improve the throughput for multichannel and multi-interface mesh networks. The algorithms build efficient multicast trees by minimizing the number of relay nodes and total hop count distances of the trees. The algorithms use dedicated channel assignment strategies to reduce the interference to improve the network capacity. We also demonstrate that using partially overlapping channels can further diminish the interference. Furthermore, additional interfaces help to increase the bandwidth, and multiple gateways can further shorten the total hop count distance. Simulations show that those algorithms greatly outperform the single-channel multicast algorithm. We also observe that MCM achieves better throughput and shorter delay while LCA can be realized in distributed manner.

In wireless sensor networks, communication signal strength weakens as the distance between sensors increases, which increases the tendency for transmitted packets to be lost. This paper provides a novel method of incorporating the hopping capability of a sensor to increase its communication range, which results in increased connectivity and sensed coverage area. Furthermore, jump heights can be manipulated to enhance packet transmissions. Since energy is at premium within sensor nodes, we present a Hopping Sensor Network Model (HSNM) and an energy conserving Hopping Sensor Routing Protocol (HSRP), which aims to optimize communication paths while balancing energy depletion in the network. Results from practical in-field experiments and simulations demonstrate the effectiveness of the approach when employed over a wireless hopping sensor network by showing increased network connectivity and the total area covered. HSRP simulations demonstrated 20% energy saving while increasing the packet delivery. The HSRP results in far less number of dead nodes, especially the high traffic nodes that are closer to the base station.

Wireless mesh networks (WMN) have emerged as an economical means for delivering last-mile Internet access. Multicast is a fundamental service in WMNs because it efficiently distributes data among a group of nodes. Multicast algorithms in WMNs are designed to maximize system throughput and minimize delay. Previous work has unrealistically assumed that the underlying WMN is link-homogeneous. We consider one important form of link heterogeneity: different link loss ratios, or equivalently different ETX. We model different link loss ratios by defining a new graph theory problem, HW-SCDS, on an edge-weighted directed graph, where the edge weights model ETX, the reciprocal of link loss ratios. We minimize transmissions in a multicast by computing a minimum HW-SCDS in the edge-weighted graph. We prove HW-SCDS is NP-hard and devise a greedy algorithm for it. Simulations show that our algorithm significantly outperforms the current best WMN multicast algorithm by both increasing throughput and reducing delay.

We present the design and implementation of a new jumping robot for mobile sensor network. Unlike other jumping robots, the robot is based on a simple two-mass-spring model. After we throw it on ground, it can stabilize itself and then jump once. The detailed mechanism design including the load holding and self-stabilization are presented. Jumping heights and distances with different robot weights are measured and compared with calculated values from the two-mass-spring model.

Many efforts have been devoted to maximizing network throughput in a multi-channel multi-radio wireless mesh network. Current solutions are based on either pure static or pure dynamic channel allocation approaches. In this paper, we propose a hybrid multi-channel multi-radio wireless mesh networking architecture, where each mesh node has both static and dynamic interfaces. We first present an Adaptive Dynamic Channel Allocation protocol (ADCA), which considers optimization for both throughput and delay in the channel assignment. In addition, we also propose an Interference and Congestion Aware Routing protocol (ICAR) in the hybrid network with both static and dynamic links, which balances the channel usage in the network. Compared to previous work, our simulation results show that ADCA reduces the packet delay considerably without degrading the network throughput. Moreover, the hybrid architecture shows much better adaptivity to changing traffic than pure static architecture without dramatic increase in overhead.

Compromised sensor nodes may collude to segregate a specific region of the sensor network preventing event reporting packets in this region from reaching the basestation. Additionally, they can cause skepticism over all data collected. Identifying and segregating such compromised nodes while identifying the type of attack with a certain confidence is critical to the smooth functioning of a sensor network. Existing work specializes in preventing or identifying specific type of attack and lacks a unified architecture to identify multiple attack types. Camouflage Event Based Malicious Node Detection Architecture (CENDA) is a proactive architecture that uses camouflage events generated by mobile-nodes to detect malicious nodes while identifying the type of attack. We exploit the spatial and temporal information of camouflage event while analyzing the packets to identify malicious activity. We simulated CENDA to compare its performance with other techniques that provide protection against individual attack types and the results show marked improvement in malicious node detection while having significantly less false positives. Moreover, CENDA is able to identify the type of malicious activity and is flexible to be configured to include other attack types in future.

This paper presents an adaptive partitioning scheme of sensor networks for node scheduling and topology control with the aim of reducing energy consumption. Our scheme partitions sensors into groups such that a connected backbone network can be maintained by keeping only one arbitrary node from each group in active status while putting others to sleep. Unlike previous approaches that partition nodes geographically, our scheme is based on the measured connectivity between pairwise nodes and does not depend on nodes' locations. In this paper, we formulate node scheduling with topology control as a constrained optimal graph partition problem, which is NP-hard, and propose a Connectivity-based Partition Approach (CPA), which is a distributed heuristic algorithm, to approximate a good solution. We also propose a probability-based CPA algorithm to further save energy. CPA can ensure K-vertex connectivity of the backbone network, which achieves the trade-off between saving energy and preserving network quality. Moreover, simulation results show that CPA outperforms other approaches in complex environments where the ideal radio propagation model does not hold.

Multihoming load balancing improves network performance by leveraging the traffic among the access links in a multi-homed network. Currently, no effective load balancing system is available to handle the inbound traffic in a BGP multi-homed stub network, where the traffic volume is unknown to the network and the route of the traffic is hard to control. In this paper, we propose ILBO, an inbound traffic load balancing mechanism to effectively balance the inbound traffic in a BGP multi-homed stub network. ILBO predicts and schedules the inbound traffic based on outbound traffic. It also provides an inbound traffic control scheme that can guarantee the successful execution of the traffic scheduling.

In sensor network localization, multihop based approaches have been proposed to approximate the shortest paths to Euclidean distances between pairwise sensors. A good approximation can be achieved when sensors are densely deployed in a convex area, where the shortest paths are close to straight lines connecting pairwise sensors. However, in a concave network, the shortest paths may deviate far away from straight lines, which leads to erroneous distance estimation and inaccurate localization results. To solve this problem, we propose an improved multihop algorithm that can recognize and filter out the erroneous distance estimation, and therefore achieve accurate localization results even in a concave network.

Multicast is a key technology that provides efficient data communication among a set of nodes for wireless multi-hop networks. In sensor networks and MANETs, multicast algorithms are designed to be energy efficient and to achieve optimal route discovery among mobile nodes, respectively. However, in wireless mesh networks, which are required to provide high quality service to end users as the "last-mile" of the Internet, throughput maximization conflicting with scarce bandwidth has the paramount priority. We propose a Level Channel Assignment (LCA) algorithm and a Multi-Channel Multicast (MCM) algorithm to optimize throughput for multi-channel and multi-interface mesh networks. The algorithms first build a multicast structure by minimizing the number of relay nodes and hop count distances between the source and destinations, and use dedicated channel assignment strategies to improve the network capacity by reducing interference. We also illustrate that the use of partially overlapping channels can further improve the throughput. Simulations show that our algorithms greatly out-perform the single-channel multicast algorithm. We observe that MCM achieves better throughput and shorter delay while LCA can be realized in distributed manner.

A flooding-based search mechanism is often used in unstructured P2P systems. Although a flooding-based search mechanism is simple and easy to implement, it is vulnerable to overlay distributed denial-of-service (DDoS) attacks. Most previous security techniques protect networks from network-layer DDoS attacks, but cannot be applied to overlay DDoS attacks. Overlay flooding-based DDoS attacks can be more damaging in that a small number of messages are inherently propagated to consume a large amount of bandwidth and computation resources. We propose a distributed and scalable method, DD-POLICE, to detect malicious nodes in order to defend P2P systems from overlay flooding-based DDoS attacks. We show the effectiveness of DD-POLICE by comprehensive simulation studies. We believe that deploying DD-POLICE will make P2P systems more scalable and robust.

In this paper, we reveal the inherent tradeoff between the quality of routing performance and the size of routing states in wireless networks. We suggest that the key approach to an optimal routing design is how toefficientlyencode a network topology into small dimensional coordinates from which hop count distances between pairwise sensors can beaccuratelyrecovered. Based on the precisely hop count distance comparison, our proposed topology aware routing can assist the greedy forwarding to find the right neighbor that is one hop closer to the destination, and therefore achieve high success rate of packet delivery. The intensive performance evaluation shows that the topology aware routing can achieve routing performance comparable to the shortest path routing while preserving the routing states as small as location aware routing. Particularly, high routing success rate can be achieved in both concave environments where voids are presented and dynamic environments where nodes crash frequently.

The peer-to-peer (P2P) model, being widely adopted in today's Internet computing, suffers from the problem of topology mismatch between the overlay networks and the underlying physical network. Traditional topology optimization techniques identify physically closer nodes to connect as overlay neighbors, but could significantly shrink the search scope. Efforts have been made to address the mismatch problem without sacrificing the search scope, but they either need time synchronization among peers or have a low convergent speed. In this paper, we propose a scalable bipartite overlay (SBO) scheme to optimize the overlay topology by identifying and replacing the mismatched connections. In SBO, we employ an efficient strategy for distributing optimization tasks in peers with different colors. We conducted comprehensive simulations to evaluate this design. The results show that SBO achieves approximately 85 percent of reduction on traffic cost and about 60 percent of reduction on query response time. Our comparisons with previous approaches to address the topology mismatch problem have shown that SBO can achieve a fast convergent speed, without the need of time synchronization among peers.

Although the original intent of the peer-to-peer (P2P) concept is to treat each participant equally, heterogeneity widely exists in deployed P2P networks. Peers are different from each other in many aspects, such as bandwidth, CPU power, and storage capacity. Some approaches have been proposed to take advantage of the query forwarding heterogeneity such that the high bandwidth of powerful nodes can be fully utilized to maximize the system capacity. In this paper, we suggest using the query answering heterogeneity to directly improve the search efficiency of P2P networks. In our proposed differentiated search (DiffSearch) algorithm, the peers with high query answering capabilities will have higher priority to be queried. Because the query answering capabilities are extremely unbalanced among peers, a high query success rate can be achieved by querying only a small portion of a network. The search traffic is significantly reduced due to the shrunken search space. Our trace analysis and simulation show that the DiffSearch algorithm can save up to 60 percent of search traffic

Unstructured peer-to-peer networks have become a very popular method for content distribution in the past few years. By not enforcing strict rules on the network's topology or content location, such networks can be created quickly and easily. Unfortunately, because of the unstructured nature of these networks, in order to find content, query messages are flooded to nodes in the network, which results in a large amount of traffic. This work borrows the technique of association analysis from the data mining community and extends it to intelligently forward queries through the network. Because only a small subset of a node's neighbors are forwarded queries, the number of times those queries are propagated is also reduced, which results in considerably less network traffic. These savings enable the networks to scale to much larger sizes, which allows for more content to be shared and more redundancy to be added to the system, as well as allowing more users to take advantage of such networks

The open feature of peer-to-peer systems invites the spread of the malfunctioning data. Additional reputation systems are constructed to guarantee the data authenticity. One challenge in these systems is how to store and spread trust value securely and efficiently. Devoid of a central control system, most of the recently proposed P2P reputation systems adopt flooding based polling mechanisms, which need to inquire into every node in the system. The polling mechanisms create heavy traffic, do not guarantee voter anonymity, and make it hard for peers to filter out the fake trust values. In this paper, we propose a reputation management system - hiREP to address these problems. A peer in hiREP system only needs to contact a small group of reputation agents to obtain the trust values. hiREP guarantees data authenticity and voter anonymity, and also makes it easier for peers to filter out fake trust values

Abstract — In sensor network localization, multihop based approaches were proposed to approximate the shortest paths to Euclidean distances between pairwise sensors. A good approximation can be achieved when sensors are densely deployed in a convex area, where the shortest paths are close to straight lines connecting pairwise sensors. However, in a concave network, the shortest paths may deviate far away from straight lines, which leads to erroneous distance estimation and inaccurate localization results. In this paper, we propose an improved multihop algorithm which can recognize and filter out the erroneous distance estimation, and therefore achieve accurate localization results even in a concave network. I.

Multicast services are demanded by a variety of applications. Many applications require anonymity during their communication. However, there has been very little work on anonymous multicasting and such services are not available yet. Since there are fundamental differences between multicast and unicast, the solutions proposed for anonymity in unicast communications cannot be directly applied to multicast applications. In this paper, we define the anonymous multicast system, and propose a mutual anonymous multicast (MAM) protocol including the design of a unicast mutual anonymity protocol and construction and optimization of an anonymous multicast tree. MAM is self organizing and completely distributed. We define the attack model in an anonymous multicast system and analyze the anonymity degree. We also evaluate the performance of MAM by simulations.

In sensor localization, ultrasound based distance measurements will have large errors if line-of-sight paths are blocked between pairwise sensors. Because these outliers, once mixed together with other correct distance measurements, are difficult for localization algorithms to identify, we propose to exclude the outliers in the first step of distance measurement. Although the distance between pairwise sensors measured by ultrasound can have multiple values due to the multipath effect, our experiments find that a sensor's incorrect position, estimated from the distance measurement along a reflected path instead of a straight line, is always mirrored to the sensor's correct position. Based on this phenomena, we propose to use mobile beacons to measure the distance between pairwise sensors from multiple perspectives and filter incorrect values through a statistical approach. Our performance evaluation shows that the proposed algorithm can achieve better localization results than previous approaches in an indoor environment where multipath effects cannot be avoided

Overlay networks provide base infrastructures for many areas including multimedia streaming and content distributions. Since most overlay networks are highly decentralized and self-organized, cut vertices may exist in such systems due to the lack of centralized management. A cut vertex is defined as a network node whose removal increases the number of network components. Failure of these nodes can break an overlay into a large number of disconnected components and greatly downgrade the upper layer services like media streaming. We propose here a distributed mechanism, CAM, which efficiently detects the cut vertices before they fail and neutralizes them into normal overlay nodes with slight overhead so that the possibility of network decomposition is minimized after they fail. We prove the correctness of this algorithm and evaluate the performance of our design through trace driven simulations.

Unstructured peer-to-peer (P2P) system is the prevalent model in today's P2P systems. In such systems, a response is sent along the same path that carried the incoming query message. To guarantee the anonymity of the requestor, no requestor information is included in the response message, and each node in the query's incoming path only knows its direct neighbors who sent the query request to it. This mechanism introduces response loss when any one node or connection in the path fails, which is a common occurrence in the P2P system due to its dynamic feature. In this paper, we address the response loss problem and show that peers' oscillation can cause up to a 35 percent response loss in an unstructured P2P system. We also present three techniques to alleviate this problem: the redundant response delivery (RRD) scheme as a proactive approach, the adaptive response delivery (ARD) scheme as a reactive approach, and the extended adaptive response delivery scheme to render ARD to function in an unstructured P2P system with limited or no flooding-based search mechanism. We have evaluated our techniques in a large-scale network simulation. With limited traffic overhead, all three techniques reduce response loss rate by more than 65 percent and are fully distributed. We have designed our techniques to be simple to develop and implement in existing P2P systems.

Large scientific parallel applications demand large amounts of memory space. Current parallel computing platforms schedule jobs without fully knowing their memory requirements. This leads to uneven memory allocation in which some nodes are overloaded. This, in turn, leads to disk paging, which is extremely expensive in the context of scientific parallel computing. To solve this problem, we propose a new peer-to-peer solution called parallel network RAM. This approach avoids the use of disk, better utilizes available RAM resources, and will allow larger problems to be solved while reducing the computational, communication, and synchronization overhead typically involved in parallel applications. We proposed several different parallel network RAM designs and evaluated the performance of each under different conditions. We discovered that different designs are appropriate in different situations.

Peer-to-peer networks are widely criticized for their inefficient flooding search mechanism. Distributed hash table (DHT) algorithms have been proposed to improve the search efficiency by mapping the index of a file to a unique peer based on predefined hash functions. However, the tight coupling between indices and hosting peers incurs high maintenance cost in a highly dynamic network. To properly balance the tradeoff between the costs of indexing and searching, we propose the distributed caching and adaptive search (DiCAS) algorithm, where indices are passively cached in a group of peers based on a predefined hash function. Guided by the same function, adaptive search selectively forwards queries to "matched" peers with a high probability of caching the desired indices. The search cost is reduced due to shrunk searching space. Different from the DHT solutions, distributed caching loosely maps the index of a file to a group of peers in a passive fashion, which saves the cost of updating indices. Our simulation study shows that the DiCAS protocol can significantly reduce the network search traffic with the help of small cache space contributed by each individual peer

Although the original intent of the peer-to-peer (P2P) concept is to treat each participant equally, heterogeneity widely exists in deployed P2P networks. In this paper, we suggest to improve the search efficiency of P2P network by utilizing the query answering heterogeneity. Our proposed differentiated search (DiffSearch) algorithm can evolve an unstructured P2P network to a two-tier hierarchical structure, where peers with high query answering capabilities are grouped in the first tier, which has higher priority to be queried than the second tier. Because the query answering capability is extremely unbalanced among peers, a high query success ratio can be achieved by querying only a small portion of the network. The search traffic is dramatically reduced due to the shrunken search space. Our trace analysis and simulation show that the DiffSearch algorithm can save up to 60% of search traffic.

In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.

Implementing multicast in MANETs is a challenging task. A typical multicast network consists of a single tree, in which only a few internal nodes contribute most resources and are involved in performing the multicast functionality. This leads to an un-even utilization of network resources. This problem is more prominent in MANETs where network resources are limited. A possible solution to the problem is to split the multicast content over a number of trees. Multiple trees provide several paths for the multicast content and get more nodes involved in implementing the multicast functionality. However, in such a setup, not all the trees get to use the best weight edges, thus the overall multicast latency increases. This paper presents MEST, a distributed algorithm to construct multiple edge-sharing trees for small group multicast. MEST balances the resource allocation and delay constraints by choosing to overlap certain edges that have low weights. Our simulation results show that MEST is scalable and can generate multicast networks that have low delay and fair resource utilization.

Security is one of the top concerns when sensors are deployed in hostile environments for military applications. Attacks on sensor nodes can be categorized into two types: attacks through radio signals to alter the functionalities of sensors and physical attacks; which may completely damage sensors. We show that the former is easier to launch and more disguised, thus more hazardous. The layered framework proposed in this paper is specially designed to defend against the first type of attacks. Different from precious reputation-based approaches or data mining technologies which usually incur large communication and computation overhead, our solution only involves localized computation which is less intensive, thus can be implemented on-board with little burden on current MICA2 platforms. Besides identifying malicious nodes, our solution can also recover the normal functionalities of sensors, which have been altered by malicious radio signals

It may be costly for mobile pervasive computing device users to download content from the Internet using their 3G connections if the 3G connection cost is a function of the amount of data downloaded. This paper introduces an approach in which mobile pervasive computing devices form an ad hoc network and share downloaded content with each other. In order to improve privacy when sharing content, this paper describes an anonymous connection between the sending peer and the receiving peer. Simulation results show that the transmission overhead of the anonymous connection may increase 50% or less as the number of peers increase or the peers are scattered over the larger area.

In unstructured peer-to-peer (P2P) systems, the mechanism of a peer randomly joining and leaving a P2P network causes a topology mismatch between the P2P logical overlay network and the physical underlying network, incurring a large volume of redundant traffic in the Internet. In order to alleviate the topology mismatch problem, we propose adaptive connection establishment (ACE), an algorithm for building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer and further optimizing the neighbor connections that are not on the tree while retaining the search scope. Our simulation study shows that this approach can effectively solve the mismatch problem and significantly reduce P2P traffic. We further study the trade-offs between the topology optimization rate and the information exchange overhead by changing the diameter used to build the tree.

Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies.

Superpeer unstructured P2P systems have been found to be very effective by dividing the peers into two layers, superlayer and leaf-layer, in which message flooding is only conducted among superlayer and all leaf-peers are represented by corresponding superpeers. However, current superpeer systems do not employ any effective layer management schemes, so the transient and low-capacity peers are allowed to act as superpeers. Moreover, the lack of an appropriate size ratio maintenance mechanism on superlayer to leaf-layer makes the system's search performance far from being optimal. We present one workload model aimed at reducing the weighted overhead of a network. Using our proposed workload model, a network can determine an optimal layer size ratio between leaf-layer and superlayer. We then propose a dynamic layer management algorithm, DLM, which can maintain an optimal layer size ratio and adaptively elect and adjust peers between superlayer and leaf-layer. DLM is completely distributed in the sense that each peer decides to be a superpeer or a leaf-peer independently without global knowledge. DLM could effectively help a superpeer P2P system maintain the optimal layer size ratio and designate peers with relatively long lifetime and large capacities as superpeers, and the peers with short lifetime and low capacities as leaf-peers under highly dynamic network situations. We demonstrate that the quality of a superpeer system is significantly improved under the DLM scheme by comprehensive simulations.

In unstructured peer-to-peer (P2P) systems, the mechanism of a peer randomly joining and leaving a P2P network causes topology mismatching between the P2P logical overlay network and the physical underlying network, causing a large volume of redundant traffic in the Internet. In order to alleviate the mismatching problem, we propose adaptive connection establishment (ACE), an algorithm of building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer, and further optimizing the neighbor connections that are not on the tree, while retaining the search scope. Our simulation study shows that this approach can effectively solve the mismatching problem and significantly reduce P2P traffic. We further study the tradeoffs between the topology optimization rate and the information exchange overhead by changing the diameter used to build the tree.

To improve the scalability of Gnutella-like unstructured peer-to-peer (P2P) networks, a uniform index caching (UIC) mechanism was suggested in some earlier work. In UIC, query results are cached in all peers along the inverse query path such that the same query of other peers can be replied from their nearby-cached results. However, our experiments show that the UIC method causes a large amount of duplicated and unnecessary caching of items among neighboring peers. Aiming at improving the search efficiency, we propose a distributed caching mechanism, which distributes the cache results among neighboring peers. Furthermore, based on the distributed caching mechanism, an adaptive search approach is built which selectively forwards the query to the peers with a high probability of providing the desired cache results. All the enhancements above are defined in a protocol called distributed caching and adaptive search (DiCAS). In the DiCAS enhanced Gnutella network, all the peers are logically divided into multiple layers, with the character that all the peers in the same layer have the same group ID. The query flooding is restricted in one layer with the matched group ID. Our simulation study shows that, with the help of the index caching and search space division, the DiCAS protocol can significantly reduce the network search traffic in unstructured P2P systems without degrading query success rate.

Large scientific parallel applications demand large amounts of memory space. Current parallel computing platforms schedule jobs without fully knowing their memory requirements. This leads to uneven memory allocation in which some nodes are overloaded. This, in turn, leads to disk paging, which is extremely expensive in the context of scientific parallel computing. To solve this problem, we propose a new peer-to-peer solution called parallel network RAM. This approach avoids the use of disk and better utilizes available RAM resources. This approach will allow larger problems to be solved while reducing the computational, communication and synchronization overhead typically involved in parallel applications.

The emerging peer-to-peer (P2P) model has recently gained a significant attention due to its high potential of sharing various resources among networked users. Super-peer unstructured P2P systems have been found very effective by dividing the peers into two layers, super-layer and leaf-layer, in which message flooding is only conducted among super-layer. However, current super-peer systems do not employ any effective layer management schemes, which means the transient and low-capacity peers are allowed to act as super-peers. Moreover, the lack of an appropriate size ratio maintenance mechanism on super-layer to leaf-layer makes the system's search performance far from being optimal. We propose a dynamic layer management algorithm, DLM, which can maintain the optimal layer size ratio, and adoptively adjust peers between super-layer and leaf-layer. DLM is completely distributed in the sense that each peer decides to be a super-peer or a leaf peer independently without the global knowledge. DLM could effectively help a super-peer P2P system maintain the optimal layer size ratio, and designate peers with relatively long lifetime and large capacities as super-peers, and the peers with short lifetime and low capacities as leaf-peers under highly dynamic network situations. We demonstrate that the quality of a super-peer system is significantly improved under DLM scheme by comprehensive simulations.

Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources, complementing the available client-server services. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatching between the P2P overlay network and the physical underlying network. The topology mismatching problem brings a great stress in the Internet infrastructure and greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique, an algorithm of building an efficient overlay by disconnecting low productive connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network when each node is optimizing the organization of its logical neighbors. The effectiveness of LTM is demonstrated through simulation studies.

Summary form only given. In unstructured peer-to-peer (P2P) systems, the stochastic peer connection and peers' randomly joining and leaving a P2P network without any knowledge about underlying physical topology can cause serious topology mismatching between the P2P overlay network and the physical underlying network. Some existing techniques have been proposed to address topology mismatching problem without shrink search scope. However, these techniques involve considerable amount of overhead, and have other disadvantages, such as slow convergence speed and synchronization requirement. To address the limits of existing solutions, we propose a scalable bipartite overlay (SBO) among peers in Gnutella-like systems or among the super-peers in KaZaA-like systems. SBO employs an efficient strategy to reduce optimization overhead by intelligently distributing optimization tasks in different peers. Our evaluations show that the total traffic and response time of the queries can be significantly reduced by optimized SBO without shrinking the search scope.

Overlay networks have made it easy to implement multicast functionality in wireless ad hoc networks. Their flexibility to adapt to different environments has helped in their steady growth. In MANET, the position of nodes constantly changes; as a result, overlay multicast trees that are built using location information to account for node movement would certainly have a low latency. However, the performance gains of such a tree are offset by the overhead involved in maintaining precise location information. As the degree of (location) accuracy increases, the performance improves but the overhead required to store and broadcast this information also increases. In this paper, we present SOLONet, a design to build a sub-optimal location aided overlay multicast tree, where location updates of each member node are event based. Our simulation results indicate that such a sub-optimal tree does not compromise the performance gains of a location aided overlay multicast tree.

Without assuming any knowledge of the underlying physical topology, the conventional P2P mechanisms are designed to randomly choose logical neighbors, causing a serious topology mismatch problem between the P2P overlay network and the underlying physical network. This mismatch problem incurs a great stress in the Internet infrastructure and adversely restraints the performance gains from the various search or routing techniques. In order to alleviate the mismatch problem, reduce the unnecessary traffic and response time, we propose two schemes, namely, location-aware topology matching (LTM) and scalable bipartite overlay (SBO) techniques. Both LTM and SBO achieve the above goals without bringing any noticeable extra overheads. More-over, both techniques are scalable because the P2P over-lay networks are constructed in a fully distributed manner where global knowledge of the network is not necessary. This paper demonstrates the effectiveness of LTM and SBO, and compares the performance of these two approaches through simulation studies. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Proxy hit ratios tend to decrease as the demand and supply of Web contents are becoming more diverse. By case studies, we quantitatively confirm this trend and observe significant document duplications among a proxy and its client browsers' caches. One reason behind this trend is that the client/server Web caching model does not support direct resource sharing among clients, causing the Web contents and the network bandwidths among clients to be relatively underutilized. To address these limits and improve Web caching performance, we have extensively enhanced and deployed our browsers-aware framework, a peer-to-peer Web caching management scheme. We make the browsers and their proxy share the contents to exploit the neglected but rich data locality in browsers and reduce document duplications among the proxy and browsers' caches to effectively utilize the Web contents and network bandwidth among clients. The objective of our scheme is to improve the scalability of proxy-based caching both in the number of connected clients and in the diversity of Web documents. We show that building such a caching system with considerations of sharing contents among clients, minimizing document duplications, and achieving data integrity and communication anonymity is not only feasible but also highly effective.

In a cluster system with dynamic load sharing support, a job submission or migration to a workstation is determined by the availability of CPU and memory resources of the workstation at the time (L. Xiao et al., 2002). In such a system, a small number of running jobs with unexpectedly large memory allocation requirements may significantly increase the queuing delay times of the rest of jobs with normal memory requirements, slowing down execution of each individual job and decreasing the system throughput. We call this phenomenon the job blocking problem because the big jobs block the execution pace of majority jobs in the cluster. Since the memory demand of jobs may not be known in advance and may change dynamically, the possibility of unsuitable job submissions/migrations to cause the blocking problem is high, and existing load sharing schemes are unable to effectively handle this problem. We propose two schemes to address this problem. The first scheme, network RAM supported load sharing, combines job migrations with network RAM, which uses remote execution to initially allocate a job to the most lightly loaded workstation and, if necessary, network RAM to provide a global memory space for the job larger than it would be available otherwise. This scheme has the merits of both job migrations and network RAM. Our experiments show its effectiveness and scalability. However, this scheme requires a network RAM facility in the cluster, which may cause additional overhead and increase cluster network traffic. In order to address this limit, we propose a second scheme, memory reservation, incorporated with dynamic load sharing, which adaptively reserves a small set of workstations to provide special services to the jobs demanding large memory allocations. As soon as the blocking problem is resolved by the memory reservation scheme, the system will adaptively switch back to the normal load sharing state. Both schemes target on handling large data-intensive jobs in clusters, and are mutually complementary. The network RAM supported load sharing scheme can fully utilize the cluster global memory space, while the memory reservation scheme has the advantage of simple implementations and low overhead. Thus, they both can be effective alternatives, and practically deployed in cluster computing under different system conditions.

Computational fluid dynamics (CFD) applications are highly demanding for parallel computing. Many such applications have been shifted from expensive MPP boxes to cost-effective clusters. Auto-CFD is a pre-compiler which transforms Fortran CFD sequential programs to efficient message-passing parallel programs running on clusters. Our work has the following three unique contributions. First, this pre-compiler is highly automatic, requiring a minimum number of user directives for parallelization. Second, we have applied a dependency analysis technique for the CFD applications, called analysis after partitioning. We propose a mirror-image decomposition technique to parallelize self-dependent field loops that are hard to parallelize by existing methods. Finally, traditional optimizations of communication focus on eliminating redundant synchronizations. We have developed an optimization scheme which combines all the non-redundant synchronizations in CFD programs to further reduce the communication overhead. The auto-CFD has been implemented on clusters and has been successfully used for automatically parallelizing structured CFD application programs. Our experiments show its effectiveness and scalability for parallelizing large CFD applications.

Peer-to-peer (P2P) systems are self-organized and decentralized. However, the mechanism of a peer randomly joining and leaving a P2P network causes topology mismatching between the P2P logical overlay network and the physical underlying network. The topology mismatching problem brings great stress on the Internet infrastructure and seriously limits the performance gain from various search or routing techniques. We propose the adaptive overlay topology optimization (AOTO) technique, an algorithm for building an overlay multicast tree between each source node and its direct logical neighbors so as to alleviate the mismatching problem by choosing closer nodes as logical neighbors, while providing a larger query coverage range. AOTO is scalable and completely distributed in the sense that it does not require global knowledge of the whole overlay network when each node is optimizing the organization of its logical neighbors. The simulation shows that AOTO can effectively solve the mismatching problem and reduce more than 55% of the traffic generated by the P2P system itself.

In a hybrid peer-to-peer (P2P) system, some operations are intentionally centralized, such as indexing of peers' files. We present several protocols to achieve mutual communication anonymity between an information requester and a provider in a hybrid P2P information-sharing environment with trusted index servers such that neither the requester, nor the provider can identify each other and no other peers can identify the two communicating parties with certainty. Some existing protocols provide solutions to achieve mutual anonymity in pure P2P systems without any trusted central controls. Compared with two representative protocols, our proposed mutual anonymity protocols improve efficiency by utilizing trusted third parties and aiming at both reliability and low-cost. We show that with some limited central support, our protocols can accomplish the goals of anonymity, efficiency, and reliability. We have evaluated our techniques in a browser-sharing environment. We show that the average increase in response time caused by our protocols is trivial, and these protocols show advantages over existing protocols in a hybrid P2P system.

Blind flooding is a popular search mechanism used in current commercial P2P systems because of its simplicity. However, blind flooding among peers or super-peers causes large volume of unnecessary traffic although the response time is short. Some improved statistics-based search mechanisms can reduce the traffic volume but also significantly shrink the query coverage range. In some search mechanisms, not all peers may be reachable creating the so-called partial coverage problem. Aiming at alleviating the partial coverage problem and reducing the unnecessary traffic, we propose an efficient and adaptive search mechanism, hybrid periodical flooding (HPF). HPF retains the advantages of statistics-based search mechanisms, alleviates the partial coverage problem, and provides the flexibility to adaptively adjust different parameters to meet different performance requirements. The effectiveness of HPF is demonstrated through simulation studies

We present several protocols to achieve mutual communication anonymity between an information requester and a provider in a P2P information-sharing environment, such that neither the requester nor the provider can identify each other, and no other peers can identify the two communicating parties with certainty. Most existing solutions achieve mutual anonymity in pure P2P systems without any trusted central controls. Compared with two such representative ones, our protocols improve efficiency in two different ways. First, utilizing trusted third parties and aiming at both reliability and low-cost, we propose a group of mutual anonymity protocols. We show that with some limited central support, our protocols can accomplish the goals of anonymity, efficiency, and reliability. Second, we propose a mutual anonymity protocol which relies solely on self-organizations among peers without any trusted central controls. In this protocol, the returning path can be shorter than the requesting path. This protocol does not need to broadcast the requested file back to the requester so that the bandwidth is saved and efficiency is improved. In addition, this protocol does not need special nodes to keep indices of sharing files, thus eliminating the index maintenance overhead and the potential for inconsistency between index records and peer file contents. We have evaluated our techniques in a browser-sharing environment. We show that the average increase in response time caused by our protocols is negligible, and these protocols show advantages over existing protocols in a P2P system.

In a cluster system with dynamic load sharing support, a job submission or migration to a workstation is determined by the availability of CPU and memory resources of the workstation at the time. In such a system, a small number of running jobs with unexpectedly large memory allocation requirements may significantly increase the queuing delay times of the rest of jobs with normal memory requirements, slowing down executions of individual jobs and decreasing the system throughput. We call this phenomenon as the job blocking problem because the big jobs block the execution pace of majority jobs in the cluster. We propose a software method incorporating with dynamic load sharing, which adaptively reserves a small set of workstations through virtual cluster reconfiguration to provide special services to the jobs demanding large memory allocations. This policy implies the principle of shortest-remaining-processing-time policy. As soon as the blocking problem is resolved by the reconfiguration, the system will adaptively switch back to the normal load sharing state. We present three contributions in this study. (1) the conditions to cause the job blocking problem; (2) the adaptive software method in a dynamic load sharing system; and (3) trace-driven simulations. We show that our method can effectively improve the cluster computing performance by quickly resolving the job blocking problem. The effectiveness and performance insights are also analytically verified.

The cluster system we consider for load sharing is a compute farm which is a pool of networked server nodes providing high-performance computing for CPU-intensive, memory-intensive, and I/O active jobs in a batch mode. Existing resource management systems mainly target at balancing the usage of CPU loads among server nodes. With the rapid advancement of CPU chips, memory and disk access speed improvements significantly lag behind advancement of CPU speed, increasing the penalty for data movement, such as page faults and I/O operations, relative to normal CPU operations. Aiming at reducing the memory resource contention caused by page faults and I/O activities, we have developed and examined load sharing policies by considering effective usage of global memory in addition to CPU load balancing in clusters. We study two types of application workloads: 1) Memory demands are known in advance or are predictable and 2) memory demands are unknown and dynamically changed during execution. Besides using workload traces with known memory demands, we have also made kernel instrumentation to collect different types of workload execution traces to capture dynamic memory access patterns. Conducting different groups of trace-driven simulations, we show that our proposed policies can effectively improve overall job execution performance by well utilizing both CPU and memory resources with known and unknown memory demands.

A compute farm is a pool of clustered workstations to provide high performance computing services for CPU-intensive, memory-intensive, and I/O active jobs in a batch mode. Existing load sharing schemes with memory considerations assume jobs' memory demand sizes are known in advance or predictable based on users' hints. This assumption can greatly simplify the designs and implementations of load sharing schemes, but is not desirable in practice. In order to address this concern, we present three new results and contributions in this study. Conducting Linux kernel instrumentation, we have collected different types of workload execution traces to quantitatively characterize job interactions, and modeled page fault behavior as a function of the overloaded memory sizes and the amount of jobs' I/O activities. Based on experimental results and collected dynamic system information, we have built a simulation model which accurately emulates the memory system operations and job migrations with virtual memory considerations. We have proposed a memory-centric load sharing scheme and its variations to effectively process dynamic memory, allocation demands, aiming at minimizing execution time of each individual job by dynamically migrating and remotely submitting jobs to eliminate or reduce page faults and to reduce the queuing time for CPU services. Conducting trace-driven simulations, we have examined these load sharing policies to show their effectiveness.

Job migrations and network RAM are two approaches for effectively using global memory resources in a workstation cluster, aimed at reducing page faults in each local workstation and improving the overall performance of cluster computing. Using either remote executions or pre-emptive migrations, a load-sharing system is able to migrate a job from a workstation without sufficient memory space to a lightly loaded workstation with a large idle memory space for the migrated job. In a network RAM system, if a job cannot find sufficient memory space for its working sets, it utilizes idle memory space from other workstations in the cluster through remote paging. Conducting trace-driven simulations, we have compared the performance and tradeoffs of the two approaches and their impacts on job execution time and cluster scalability. Job migration-based load-sharing schemes are able to balance executions of jobs in a cluster well, while network RAM is able to satisfy data-intensive jobs which may not be migratable by sharing all the idle memory resources in a cluster. A network RAM cluster of workstations is scalable only if the network is sufficiently fast. We propose an improved load-sharing scheme by combining job migrations with network RAM for cluster computing. This scheme uses remote execution to initially allocate a job to the most lightly loaded workstation and, if necessary, network RAM to provide a larger memory space for the job than would be available otherwise. The improved scheme has the merits of both job migrations and network RAM. Our experiments show its effectiveness and scalability for cluster computing.

We develop and examine job migration policies by considering effective usage of global memory in addition to CPU load sharing in distributed systems. When a node is identified for lacking sufficient memory space to serve jobs, one or more jobs of the node will be migrated to remote nodes with low memory allocations. If the memory space is sufficiently large the jobs will be scheduled by a CPU-based load sharing policy. Following the principle of sharing both CPU and memory resources, we present several load sharing alternatives. Out objective is to reduce the number of page faults caused by unbalanced memory allocations for jobs among distributed nodes, so that overall performance of a distributed system can be significantly improved. We have conducted trace-driven simulations to compare CPU-based load sharing policies with our policies. We show that our load sharing policies not only improve performance of memory bound jobs, but also maintain the same load sharing quality as the CPU-based policies for CPU-bound jobs. Regarding remote execution and preemptive migration strategies, our experiments indicate that a strategy selection in load sharing is dependent on the amount of memory demand of jobs-remote execution is more effective for memory-bound jobs, and preemptive migration is more effective for CPU-bound jobs. Our CPU memory-based policy using either high performance or high throughput approach and using the remote execution strategy performs the best for both CPU-bound and memory-bound jobs.

We consider networks of workstations which are not only time-sharing, but also heterogeneous with a large variation in the computing power and memory capacities of different workstations. Many load sharing schemes mainly target sharing CPU resources, and have been intensively evaluated in homogeneous distributed environments. However the penalties of data accesses and movement in modern computer systems, such as page faults, have grown to the point where the overall performance of distributed systems cannot be further improved without serious considerations concerning memory resources in the design of load sharing policies. Considering both system heterogeneity and effective usage of memory resources, we design and evaluate load sharing policies in order to minimize both CPU idle times and the number of page faults in heterogeneous distributed systems. Conducting trace-driven simulations, we show that load sharing policies considering both CPU and memory resources are robust and effective in heterogeneous systems. We also show that the functionality and the nature of load sharing policies are quite independent on several memory demand distributions of workloads.