FINAL YEAR PROJECTS: June 2011

IEEE TRANSACTIONS PROJECTS
* IEEE Transactions on Mobile Computing * IEEE Transactions on Network Computing * IEEE Transactions on Network Security * IEEE Transactions on Parallel and Distributed Systems * IEEE Transactions on Cloud Computing * IEEE Transactions on Knowledge and Data Engineering * IEEE Transactions on Dependable and Secure Computing * IEEE Transactions on Services Computing * IEEE Transactions on Image Processing * IEEE Transactions on Distributed Computing System * IEEE Transactions on Pattern Analysis & Machine Intelligence * IEEE Transactions on Software Engineering * IEEE Transactions on Web Application and Web Service * IEEE Transactions on Data Mining * IEEE Transactions on Learning Technologies * IEEE Transactions on Information Forensics and Security * IEEE Transactions on Internet Computing * IEEE Transactions on Signal Processing * IEEE Transactions on Multimedia Computing * IEEE Transactions on Vehicular Technology * IEEE Transactions on Visualization and Computer Graphics * IEEE Transactions on Wireless Communication * IEEE Transactions on Wireless Sensor Networks * IEEE Transactions on Fuzzy systems * IEEE Transactions on Neural Networks * IEEE Transactions on Communication * IEEE Transactions on Computers

Sunday, June 26, 2011

IEEE 2011 Project Titles List - JAVA AND DOT NET

IEEE TRANSACTION - IEEE 2011 PROJECTS
MOBILE COMPUTING PROJECTS - 2011
· A Control Theoretic Approach to Distributed Optimal Configuration of 80211 WLANs
· A Cooperative Clustering Protocol for Energy Saving of Mobile Devices with WLAN and Bluetooth Interfaces
· A Distributed and Scalable Time Slot Allocation Protocol for Wireless Sensor Networks
· Adaptive Location Oriented Content Delivery in Delay Sensitive Pervasive Applications
· Autonomous Deployment of Heterogeneous Mobile Sensors
· Cross Layer Optimization for Multimedia Transport over Multicode CDMA Networks
· Design and Performance Analysis of Mobility Management Schemes Based on Pointer Forwarding
· Design and Performance of an Optimal Inertial Power Harvester for Human-Powered Devices
· Dynamic Time Slot Partitioning for Multimedia Transmission in Two Hop Cellular Networks
· Effective Scheduling in Infrastructure Based Cognitive Radio Networks
· Efficient Location Training Protocols for Heterogeneous Sensor and Actor Networks
· Endpoint Based Call Admission Control and Resource Management for VoWLAN
· Fast Detection of Mobile Replica Node Attacks in Wireless Sensor Networks Using Sequential Hypothesis Testing
· Interference Aware Routing in Wireless Multihop Networks
· MAC Layer Throughput Estimation in Impulse-Radio UWB Networks
· Minimum Bandwidth Reservations for Periodic Streams in Wireless Real-Time Systems
· Mobile Sampling of Sensor Field Data Using Controlled Broadcast
· Multicast Throughput for Hybrid Wireless Networks under Gaussian Channel Model
· On the Design of Opportunistic MAC Protocols for Multihop Wireless Networks with Beamforming Antennas
· On the Information Flow Required for Tracking Control in Networks of Mobile Sensing Agents
· Optimal Stochastic Location Updates in Mobile Ad Hoc Networks
· Processing Continuous Range Queries with Spatiotemporal Tolerance
· QoS Aware Routing and Admission Control in Shadow Fading Environments for Multirate MANETs
· Scalable Localization with Mobility Prediction for Underwater Sensor Networks
· Secure High-Throughput Multicast Routing in Wireless Mesh Networks
· Spatial Temporal Coverage Optimization in Wireless Sensor Networks
· Supporting Efficient and Scalable Multicasting over Mobile Ad Hoc Networks
· The HIDENETS Holistic Approach for the Analysis of Large Critical Mobile Systems
· Throughput Optimization in Mobile Backbone Networks
· Traffic Differentiation Based Modular QoS Localized Routing for Wireless Sensor Networks

NETWORKING PROJECTS - 2011
· A Novel Approach for Failure Localization in All-Optical Mesh Networks
· A Simple Model for Chunk-Scheduling Strategies in P2P Streaming
· A Unifed Approach to Optimizing Performance in Networks Serving Heterogeneous Flows
· Coloring Spatial Point Processes With Applications to Peer Discovery in Large Wireless Networks
· Component Based Localization in Sparse Wireless Networks
· Continuous Neighbor Discovery in Asynchronous Sensor Networks
· Cross Layer Jamming Detection and Mitigationin Wireless Broadcast Networks
· Crosstalk Preventing Scheduling in Single and Two Stage AWG Based Cell Switches
· Delay Analysis and Optimality of Scheduling Policies for Multihop Wireless Networks
· Efficient Multipath Communication for Time Critical Applications in Underwater Acoustic Sensor Networks
· Energy Efficient Protocol for Cooperative Networks
· Fast Simulation of Service Availability in Mesh Networks With Dynamic Path Restoration
· Forward Correction and Fountain Codes in Delay-Tolerant Networks
· Jamming Aware Traffic Allocation for Multiple Path Routing Using Portfolio Selection
· Licklider Transmission Protocol (LTP) Based DTN for Cislunar Communications
· Live Streaming With Receiver Based Peer-Division Multiplexing
· Mobile Sampling of Sensor Field Data Using Controlled Broadcast
· Model Based Identification of Dominant Congested Links
· Network Coding Multicast Networks With QoS Guarantees
· On the Complexity of the Regenerator Placement Problem in Optical Networks
· On the Price of Security in Large-Scale Wireless Ad Hoc Networks
· Optimal Anycast Technique for Delay-Sensitive Energy-Constrained Asynchronous Sensor Networks
· Parametric Methods for Anomaly Detection in Aggregate Traffic
· Practical Computation of Optimal Schedules in Multihop Wireless Networks
· Primary User Activity Modeling Using First-Difference Filter Clustering and Correlation in Cognitive Radio Networks
· ProgME - Towards Programmable Network MEasurement
· Scalable and Cost-Effective Interconnection of Data-Center Servers Using Dual Server Ports
· Scheduling Algorithms for Multicarrier Wireless Data Systems
· Self Reconfigurable Wireless Mesh Networks
· SPAF - Stateless FSA-Based Packet Filters
· Star Block Design in Two-Level Survivable Optical Networks
· Stochastic Model and Connectivity Dynamics for VANETs in Signalized Road Systems
· TOFU Semi Truthful Online Frequency Allocation Mechanism for Wireless Networks
· Topological Transformation Approaches to TCAM-Based Packet Classification

CLOUD COMPUTING PROJECTS 2011
· Performance Analysis of Cloud Computing Services for Many-Tasks Scientific Computing
· Exploiting Dynamic Resource Allocation for Efficient Parallel Data Processing in the Cloud
· Enabling Public Auditability and Data Dynamics for Storage Security in Cloud Computing
· Heuristics Based Query Processing for Large RDF Graphs Using Cloud Computing
· Optimization of Resource Provisioning Cost in Cloud Computing
· Towards Secure and Dependable Storage Services in Cloud Computing
· Performance Analysis of Cloud Computing Services for MTC-Based Scientific Computing
· CloudTPS: Scalable Transactions for Web Applications in the Cloud

DEPENDABLE AND SECURE COMPUTING PROJECTS 2011
· Anomaly Detection in Network Traffic Based on Statistical Inference and alpha-Stable Modeling
· ELMO: Energy Aware Local Monitoring in Sensor Networks
· Efficient Fault Detection and Diagnosis in Complex Software Systems with Information-Theoretic Monitoring
· Privacy-Preserving Updates to Anonymous and Confidential Databases
· Dynamics of Malware Spread in Decentralized Peer-to-Peer Networks
· Low-Energy Symmetric Key Distribution in Wireless Sensor Networks
· Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables
· Robust Correlation of Encrypted Attack Traffic through Stepping Stones by Flow Watermarking

NETWORK AND SERVICE MANAGEMENT 2011
· Low-Overhead End-to-End Performance Measurement for Next Generation Networks
· On the Impact of Security Protocols on the Performance of SNMP
· Locating Equivalent Servants over P2P Networks

IMAGE PROCESSING PROJECTS 2011
· Nonlocal PDEs-Based Morphology on Weighted Graphs for Image and Data Processing
· Image Segmentation Using Fuzzy Region Competition and Spatial/Frequency Information
· Perceptual Segmentation: Combining Image Segmentation With Object Tagging
· ViBe: A Universal Background Subtraction Algorithm for Video Sequences
· Contextual Kernel and Spectral Methods for Learning the Semantics of Images
· Distributed Multiple Description Video Coding on Packet Loss Channels
· Graph Regularized Sparse Coding for Image Representation
· Geometrically Induced Force Interaction for Three-Dimensional Deformable Models
· JPEG2000-Based Scalable Interactive Video (JSIV)

KNOWLEDGE AND DATA ENGINEERING PROJECTS 2011
· Mining Cluster-Based Temporal Mobile Sequential Patterns in Location-Based Service Environments
· Cosdes: A Collaborative Spam Detection System with a Novel E-Mail Abstraction Scheme
· A Link Analysis Extension of Correspondence Analysis for Mining Relational Databases
· A Personalized Ontology Model for Web Information Gathering
· A Machine Learning Approach for Identifying Disease-Treatment Relations in Short Texts
· Design and Implementation of an Intrusion Response System for Relational Databases
· Classification and Novel Class Detection in Concept-Drifting Data Streams under Time Constraints

PARALLEL AND DISTRIBUTED SYSTEM PROJECTS 2011
· Cooperative Channelization in Wireless Networks with Network Coding
· Video Streaming Distribution in VANETs
· Throughput Optimization in Multihop Wireless Networks with Multipacket Reception and Directional Antennas
· Attribute-Based Access Control with Efficient Revocation in Data Outsourcing Systems
· Network Immunization with Distributed Autonomy-Oriented Entities
· Optimization of Rate Allocation with Distortion Guarantee in Sensor Networks
· A Data Throughput Prediction and Optimization Service for Widely Distributed Many-Task Computing
· Multicloud Deployment of Computing Clusters for Loosely Coupled MTC Applications
· Toward Efficient and Simplified Distributed Data Intensive Computing

IEEE 2011 Project Titles List - JAVA AND DOT NET

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

DYNAMIC TIME SLOT PARTITIONING FOR MULTIMEDIA TRANSMISSION IN TWO-HOP CELLULAR NETWORKS

Abstract
In recent years, there has been an exponential increase in the number of mobile phone users. In addition, a significant growth in the demand for high-rate multimedia services over wireless networks, such as video conferencing, multimedia streaming, etc., was noted.
Different solutions were proposed to support high-quality high data rate delivery to mobile users, including resource allocation techniques for packet-radio-based next generation cellular networks.
In this paper, an efficient time slot allocation method—Dynamic Time Slot Partitioning (DTSP) algorithm based on statistical multiplexing is proposed for a two-hop cellular architecture. In DTSP, the available bandwidth resources are increased by partitioning each time slot into several minislots wherein different numbers of minislots are allocated to different users.
The DTSP algorithm is based on asynchronous time-division multiplexing, wherein users with variable number of packets in their buffers can transmit data sequentially without any loss in the overall available resources.
The key advantage of DTSP is that it can flexibly adapt to different quality of service requirements, especially when combined with adaptive modulation. It has been observed that the system capacity achieved by the DTSP algorithm in the downlink mode using adaptive modulation is up to 41 percent higher than when existing solutions are employed.
In addition, DTSP results in significantly lower time for data transmission than the state-of-the-art region and time partitioning techniques.

Index Terms
Adaptive modulation, cluster-based design, dynamic time slot partitioning, statistical multiplexing, time-division multiple access, two-hop.

--------------------------------------------------------------------------
IEEE TRANSACTIONS ON MOBILE COMPUTING,
VOL. 10, NO. 3, MARCH 2011

EFFICIENT LOCATION TRAINING PROTOCOLS FOR HETEROGENEOUS SENSOR AND ACTOR NETWORKS

Abstract
In this work, we consider a large-scale geographic area populated by tiny sensors and some more powerful devices called actors, authorized to organize the sensors in their vicinity into short-lived, actor-centric sensor networks. The tiny sensors run on miniature nonrechargeable batteries, are anonymous, and are unaware of their location.
The sensors differ in their ability to dynamically alter their sleep times. Indeed, the periodic sensors have sleep periods of predefined lengths, established at fabrication time; by contrast, the free sensors can dynamically alter their sleep periods, under program control.
The main contribution of this work is to propose an energy-efficient location training protocol for heterogeneous actor-centric sensor networks where the sensors acquire coarse-grain location awareness with respect to the actor in their vicinity.
Our theoretical analysis, confirmed by experimental evaluation, shows that the proposed protocol outperforms the best previously known location training protocols in terms of the number of sleep/awake transitions, overall sensor awake time, and energy consumption.

Index Terms
Sensor and actor networks, heterogeneous sensors, coarse-grain localization, location training protocols, localization protocols.

--------------------------------------------------------------------------
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

CROSS-LAYER OPTIMIZATION FOR MULTIMEDIA TRANSPORT OVER MULTICODE CDMA NETWORKS

Abstract
Most previous work on code division multiple access (CDMA) considers the bit error ratio (BER) at the physical layer and the frame drop ratio (FDR) at the medium access control layer separately. However, a better system performance, e.g., in terms of a lower overall frame loss ratio (FLR), can be achieved if BER and FDR are jointly optimized.
In this paper, we propose a cross-layer optimization scheme called traffic-adaptive scheme for multicode CDMA operating over a time division multiple access (TDMA) channel.
Based on the traffic condition and buffer status, this scheme employs a Markov Decision Process (MDP) to determine the optimal value of the maximum number of simultaneous data frames that can be transmitted in each time slot of a TDMA frame so as to minimize the overall FLR of the system.
To facilitate implementation, we also propose an approximation scheme named the rate adaptive scheme to reduce the computation cost. Simulation and analytical results show that both the traffic-adaptive scheme and rate-adaptive scheme can significantly reduce FLR, increase the system throughput, and optimize the packet access delay of the system.
Furthermore, the rate-adaptive scheme can achieve a performance close to the traffic-adaptive scheme when the traffic load in the system is high.

Index Terms
Multimedia communication, wireless, multicode code division multiple access.

--------------------------------------------------------------------------
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

EFFECTIVE SCHEDULING IN INFRASTRUCTURE-BASED COGNITIVE RADIO NETWORKS

Abstract
In this paper, we investigate a joint scheduling and power control for an infrastructure-based cognitive radio network (CRN) in coexistence with a cellular primary radio network (PRN). The PRN uses a set of licensed nonoverlapping orthogonal frequency channels for transmission.
This set of channels is also accessed in an opportunistic manner by a set of cognitive radio base stations (CR-BSs) to support secondary users (SUs). The problem is formulated to maximize the spectrum utilization of SUs without causing excessive interference to active primary users (PUs) of the PRN. In addition, all the serviced SUs must meet a certain Quality of Service (QoS), such as satisfying a predefined signal to interference noise ratio (SINR).
A centralized solution for joint scheduling and power control is derived to make the global accessing decision for all unserved SUs. With the assumption that the knowledge of all subscribers is available, a coordinator of the CRN can use the joint scheduling and power control algorithm to maximize the spectrum utilization of serviced SUs by solving a mixed-integer linear programming (MILP) with an NP-hard complexity.
To avoid the NP-hard complexity, we propose a suboptimal heuristic greedy algorithm that can be obtained at a much lower complexity based on the coloring interference graph among unserved SUs effected by serviced SUs and active PUs. Its superior performance over the existing algorithms is demonstrated through simulations.

Index Terms
Cognitive radio, opportunistic spectrum allocation, scheduling, power control, interference graph.

--------------------------------------------------------------------------
IEEE TRANSACTIONS ON MOBILE COMPUTING,
VOL. 10, NO. 3, MARCH 2011

DESIGN AND PERFORMANCE ANALYSIS OF MOBILITY MANAGEMENT SCHEMES BASED ON POINTER FORWARDING FOR WIRELESS MESH NETWORKS

Abstract
We propose efficient mobility management schemes based on pointer forwarding for wireless mesh networks (WMNs) with the objective to reduce the overall network traffic incurred by mobility management and packet delivery.
The proposed schemes are per-user-based, i.e., the optimal threshold of the forwarding chain length that minimizes the overall network traffic is dynamically determined for each individual mobile user, based on the user’s specific mobility and service patterns.
We develop analytical models based on stochastic Petri nets to evaluate the performance of the proposed schemes. We demonstrate that there exists an optimal threshold of the forwarding chain length, given a set of parameters characterizing the specific mobility and service patterns of a mobile user.
We also demonstrate that our schemes yield significantly better performance than schemes that apply a static threshold to all mobile users. A comparative analysis shows that our pointer forwarding schemes outperform routing-based mobility management protocols for WMNs, especially for mobile Internet applications characterized by large traffic asymmetry for which the downlink packet arrival rate is much higher than the uplink packet arrival rate.

Index Terms
Mobility management, pointer forwarding, wireless mesh networks, performance analysis, stochastic Petri net.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

A COOPERATIVE CLUSTERING PROTOCOL FOR ENERGY SAVING OF MOBILE DEVICES WITH WLAN AND BLUETOOTH INTERFACES

Abstract
One of the most widely used wireless communication standards is a Wireless Local Area Network (WLAN) (IEEE 802.11). However, WLAN has a serious power consumption problem. In this paper, we propose a novel energy saving approach that exploits the multiradio feature of recent mobile devices equipped with WLAN and Bluetooth interfaces.
Unlike previous approaches, our work is based on clustering. In our work, a cluster is a Bluetooth Personal Area Network (PAN), which consists of one cluster head and several regular nodes. The cluster head acts as a gateway between the PAN and the WLAN, enabling the regular nodes to access the WLAN infrastructure via low-power Bluetooth.
We present a distributed clustering protocol, Cooperative Networking protocol (CONET), which dynamically reforms clusters according to each node’s bandwidth requirement, energy use, and application type. CONET does not require modifications of existing wireless infrastructures because clustering is performed independently of WLAN access points.
We implemented the CONET prototype with four wearable computing devices to evaluate the performance on real hardware. We also simulated CONET for large networks of more than 100 mobile nodes. Both results demonstrate that our approach is effective in reducing the power consumption of WLAN.

Index Terms
Wireless communication, protocol architecture, multiradio, energy efficiency, clustering.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

AUTONOMOUS DEPLOYMENT OF HETEROGENEOUS MOBILE SENSORS

Abstract
In this paper, we address the problem of deploying heterogeneous mobile sensors over a target area. Traditional approaches to mobile sensor deployment are specifically designed for homogeneous networks. Nevertheless, network and device homogeneity is an unrealistic assumption in most practical scenarios, and previous approaches fail when adopted in heterogeneous operative settings.
For this reason, we introduce VorLag, a generalization of the Voronoi-based approach which exploits the Laguerre geometry. We theoretically prove the appropriateness of our proposal to the management of heterogeneous networks.
In addition, we demonstrate that VorLag can be extended to deal with dynamically generated events or uneven energy depletion due to communications.
Finally, by means of simulations, we show that VorLag provides a very stable sensor behavior, with fast and guaranteed termination and moderate energy consumption. We also show that VorLag performs better than its traditional counterpart and other methods based on virtual forces.

Index Terms
Device heterogeneity, self-deployment, Voronoi-Laguerre diagrams.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

A CONTROL-THEORETIC APPROACH TO DISTRIBUTED OPTIMAL CONFIGURATION OF 802.11 WLANS

Abstract
The optimal configuration of the contention parameters of a WLAN depends on the network conditions in terms of number of stations and the traffic they generate. Following this observation, a considerable effort in the literature has been devoted to the design of distributed algorithms that optimally configure the WLAN parameters based on current conditions.
In this paper, we propose a novel algorithm that, in contrast to previous proposals which are mostly based on heuristics, is sustained by mathematical foundations from multivariable control theory. A key advantage of the algorithm over existing approaches is that it is compliant with the 802.11 standard and can be implemented with current wireless cards without introducing any changes into the hardware or firmware.
We study the performance of our proposal by means of theoretical analysis, simulations, and a real implementation. Results show that the algorithm substantially outperforms previous approaches in terms of throughput and delay.

Index Terms
Wireless LAN, IEEE 802.11, DCF, adaptive MAC, distributed algorithm, multivariable control theory.

IEEE TRANSACTIONS ON MOBILE COMPUTING
VOL. 10, NO. 3, MARCH 2011

ADAPTIVE LOCATION-ORIENTED CONTENT DELIVERY IN DELAY-SENSITIVE PERVASIVE APPLICATIONS

Abstract
In this paper, we introduce a delay-sensitive service that involves transmitting large amounts of location-based data to nodes at multiple locations. Given a limited amount of access points (APs) and an abundance of service requests that result from the nodes moving around, a typical content delivery service would inevitably introduce considerable delay.
To solve this problem, we analyze the movement pattern of mobile nodes and approximate it as a semi-Markov process. Based on this model, we explore different components of the underlying service delay and propose that APs should use a multicast strategy to minimize the queuing delay component.
Furthermore, we demonstrate the feasibility of employing nodes, which already have their own local copies of location-relevant data, to relay such data to other nodes by employing one or multiple communication channels.
Lastly, we examine the resulting algorithms and study their performance relative to baseline content-delivery schemes through simulations.

Index Terms
Location-dependent and sensitive, pervasive computing, wireless sensor networks.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

A DISTRIBUTED AND SCALABLE TIME SLOT ALLOCATION PROTOCOL FOR WIRELESS SENSOR NETWORKS

Abstract
There are performance deficiencies that hamper the deployment of Wireless Sensor Networks (WSNs) in critical monitoring applications. Such applications are characterized by considerable network load generated as a result of sensing some characteristics of the monitored system.
Excessive packet collisions lead to packet losses and retransmissions, resulting in significant overhead costs and latency. In order to address this issue, we introduce a distributed and scalable scheduling access scheme that mitigates high data loss in data-intensive sensor networks and can also handle some mobility.
Our approach alleviates transmission collisions by employing virtual grids that adopt Latin Squares characteristics to time slot assignments. We show that our algorithm derives conflictfree time slot allocation schedules without incurring global overhead in scheduling.
Furthermore, we verify the effectiveness of our protocol by simulation experiments. The results demonstrate that our technique can efficiently handle sensor mobility with acceptable data loss, low packet delay, and low overhead.

Index Terms
Access scheduling, wireless sensor networks, data-intensive applications, topology changes.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

DESIGN AND PERFORMANCE OF AN OPTIMAL INERTIAL POWER HARVESTER FOR HUMAN-POWERED DEVICES

Abstract
We present an empirical study of the long-term practicality of using human motion to generate operating power for bodymounted consumer electronics and health sensors. We have collected a large continuous acceleration data set from eight experimental subjects going about their normal daily routine for three days each.
Each subject is instrumented with a data collection apparatus that simultaneously logs 3-axis, 80 Hz acceleration data from six body locations. We use this data set to optimize a firstprinciples physical model of the commonly used velocity damped resonant generator (VDRG) by selecting physical parameters such as resonant frequency and damping coefficient to maximize the harvested power.
Our results show that with reasonable assumptions on size, mass, placement, and efficiency of VDRG harvesters, most body-mounted wireless sensors and even some consumer electronics devices can be powered continuously and indefinitely from everyday motion.
We have optimized the power harvesters for each individual and for each body location. In addition, we present the potential of designing a damping- and frequency-tunable power harvester that could mitigate the power reduction of a generator generalized for “average” subjects.
We present the full details on the collection of the acceleration data sets, the development of the VDRG model, and a numerical simulator, and discuss some of the future challenges that remain in this promising field of research.

Index Terms
Human power harvesting, inertial generator, optimal design, tunable generator, human-powered device.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

ENDPOINT-BASED CALL ADMISSION CONTROL AND RESOURCE MANAGEMENT FOR VOWLAN

Abstract
This paper examines two specific aspects of resource management in Wireless Local Area Networks (WLANs)—Call Admission Control (CAC) and handling of Link Adaptation (LA) events. A self-consistent system to manage these for Voice over Internet Protocol (VoIP) over an IEEE 802.11 WLAN is presented.
The proposed CAC scheme is based on the Endpoint Admission Control (EAC) paradigm, where the endpoints probe the network to determine if the call can be supported with acceptable Quality of Service (QoS).
The proposed scheme was evaluated on an experimental testbed and test results show that correct admission decisions were made under various network configurations. The scheme also determines if LA has resulted in the system becoming congested and, if so, the voice codec of the handset which has undergone LA is adapted so as to restore the system to its earlier state, thereby alleviating the congestion.
The proposed scheme was evaluated on the experimental testbed and test results show that the codec adaptation scheme was very effective at overcoming the effects of LA for VoIP over WLAN.

Index Terms
Call admission control, IEEE 802.11, link adaptation, VoIP

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

OPTIMAL STOCHASTIC LOCATION UPDATES IN MOBILE AD HOC NETWORKS

Abstract
We consider the location service in a mobile ad-hoc network (MANET), where each node needs to maintain its location information by 1) frequently updating its location information within its neighboring region, which is called neighborhood update (NU), and 2) occasionally updating its location information to certain distributed location server in the network, which is called location server update (LSU).
The trade off between the operation costs in location updates and the performance losses of the target application due to location inaccuracies (i.e., application costs) imposes a crucial question for nodes to decide the optimal strategy to update their location information, where the optimality is in the sense of minimizing the overall costs. In this paper, we develop a stochastic sequential decision framework to analyze this problem.
Under a Markovian mobility model, the location update decision problem is modeled as a Markov Decision Process (MDP). We first investigate the monotonicity properties of optimal NU and LSU operations with respect to location inaccuracies under a general cost setting.
Then, given a separable cost structure, we show that the location update decisions of NU and LSU can be independently carried out without loss of optimality, i.e., a separation property.
From the discovered separation property of the problem structure and the monotonicity properties of optimal actions, we find that 1) there always exists a simple optimal threshold-based update rule for LSU operations; 2) for NU operations, an optimal threshold-based update rule exists in a low-mobility scenario.
In the case that no a priori knowledge of the MDP model is available, we also introduce a practical model-free learning approach to find a near-optimal solution for the problem.

Index Terms
Location update, mobile ad hoc networks, Markov decision processes, least-squares policy iteration

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

MOBILE SAMPLING OF SENSOR FIELD DATA USING CONTROLLED BROADCAST

Abstract
Mobile objects can be used to gather samples from a sensor field. Civilian vehicles or even human beings equipped with proper wireless communication devices can be used as mobile sinks that retrieve sensor-data from sampling points within a large sensor field.
A key challenge is how to gather the sensor data in a manner that is energy efficient with respect to the sensor nodes that serve as sources of the sensor data. In this paper, an algorithmic technique called Band-based Directional Broadcast is introduced to control the direction of broadcasts that originate from sensor nodes.
The goal is to direct each broadcast of sensor data toward the mobile sink, thus reducing costly forwarding of sensor data packets. The technique is studied by simulations that consider energy consumption and data deliverability.

Index Terms
Sensor data sampling, mobile object, directional broadcast, sensor networks.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

FAST DETECTION OF MOBILE REPLICA NODE ATTACKS IN WIRELESS SENSOR NETWORKS USING SEQUENTIAL HYPOTHESIS TESTING

Abstract
Due to the unattended nature of wireless sensor networks, an adversary can capture and compromise sensor nodes, make replicas of them, and then mount a variety of attacks with these replicas. These replica node attacks are dangerous because they allow the attacker to leverage the compromise of a few nodes to exert control over much of the network.
Several replica node detection schemes have been proposed in the literature to defend against such attacks in static sensor networks. However, these schemes rely on fixed sensor locations and hence do not work in mobile sensor networks, where sensors are expected to move.
In this work, we propose a fast and effective mobile replica node detection scheme using the Sequential Probability Ratio Test. To the best of our knowledge, this is the first work to tackle the problem of replica node attacks in mobile sensor networks.
We show analytically and through simulation experiments that our scheme detects mobile replicas in an efficient and robust manner at the cost of reasonable overheads.

Index Terms
Replica detection, sequential analysis, mobile sensor networks, security.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

MINIMUM BANDWIDTH RESERVATIONS FOR PERIODIC STREAMS IN WIRELESS REAL-TIME SYSTEMS

Reservation-based (as opposed to contention-based) channel access in WLANs provides predictable and deterministic transmission and is therefore able to provide timeliness guarantees for wireless and embedded real-time applications.
Also, reservation-based channel access is energy-efficient since a wireless adaptor is powered on only during its exclusive channel access times. While scheduling for Quality of Service at the central authority (e.g., base station) has received extensive attention, the problem of determining the actual resource requirements of an individual node in a wireless real-time system has been largely ignored.
This work aims at finding the minimum channel bandwidth reservation that meets the real-time constraints of all periodic streams of a given node. Keeping the bandwidth reservation of a node to a minimum leads to reduced energy and resource requirements and leaves more bandwidth for future reservations by other nodes.
To obtain a solution to the minimum bandwidth reservation problem, we transform it to a generic uniprocessor task schedulability problem, which is then addressed using a generic algorithm. This algorithm works for a subclass of priority-driven packet scheduling policies, including three common ones: fixed-priority, EDF, and FIFO.
Moreover, we then specialize the generic algorithm to these three policies according to their specific characteristics. Their computation complexities and bandwidth reservation efficiencies are evaluated and guidelines for choosing scheduling policies and stream parameters are presented.

Index Terms
Bandwidth reservation, schedulability test, earliest deadline first, fixed-priority, first-in-first-out, medium access control, real time, wireless.

IEEE TRANSACTIONS ON MOBILE COMPUTING
VOL. 10, NO. 5, APRIL 2011

ON THE INFORMATION FLOW REQUIRED
FOR TRACKING CONTROL IN
NETWORKS OF MOBILE SENSING AGENTS

Abstract
We design controllers that permit mobile agents with distributed or networked sensing capabilities to track (follow) desired trajectories, identify what trajectory information must be distributed to each agent for tracking, and develop methods to minimize the communication needed for the trajectory information distribution.

Index Terms
Cooperative control, dynamical networks, tracking

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

MULTICAST THROUGHPUT FOR HYBRID WIRELESS NETWORKS UNDER GAUSSIAN CHANNEL MODEL

Abstract
We study the multicast capacity for hybrid wireless networks consisting of ordinary ad hoc nodes and base stations under Gaussian Channel model, which generalizes both the unicast and broadcast capacities for hybrid wireless networks.
Assume that all ordinary ad hoc nodes transmit at a constant power P, and the power decays along the path, with attenuation exponent > 2. The data rate of a transmission is determined by the Signal to Interference plus Noise Ratio (SINR) at the receiver as Blogð1 þ SINRÞ.
The ordinary ad hoc nodes are placed in the square region AðaÞ of area a according to a Poisson point process of intensity n=a. Then, m additional base stations (BSs) acting as the relaying communication gateways are placed regularly in the region AðaÞ, and are connected by a high-bandwidth wired network. Let a ¼ n and a ¼ 1, we construct the hybrid extended network (HEN) and hybrid dense network (HDN), respectively. We choose randomly and independently ns ordinary ad hoc nodes to be the sources of multicast sessions.
We assume that each multicast session has nd randomly chosen terminals. Three broad categories of multicast strategies are proposed. The first one is the hybrid strategy, i.e., the multihop scheme with BS-supported, which further consists of two types of strategies called connectivity strategy and percolation strategy, respectively.
The second one is the ordinary ad hoc strategy, i.e., the multihop scheme without any BS-supported. The third one is the classical BS-based strategy under which any communication between two ordinary ad hoc nodes is relayed by some specific BSs. According to the different scenarios in terms of m, n, and nd, we select the optimal scheme from the three categories of strategies, and derive the achievable multicast throughput based on the optimal decision.

Index Terms
Wireless hybrid networks, wireless ad hoc networks, multicast throughput, random networks, multicast capacity, Gaussian channel mode

IEEE TRANSACTIONS ON MOBILE COMPUTING
VOL. 10, NO. 3, MARCH 2011

ON THE DESIGN OF OPPORTUNISTIC MAC PROTOCOLS FOR MULTIHOP WIRELESS NETWORKS WITH BEAMFORMING ANTENNAS

Abstract
Beamforming antennas promise a significant increase in the spatial reuse of the wireless medium when deployed in multihop wireless networks. However, existing directional Medium Access Control (MAC) protocols with the default binary exponential backoff mechanism are not capable of fully exploiting the offered potential.
In this paper, we discuss various issues involved in the design of MAC protocols specific for beamforming antennas. Based on our discussion, we argue that the traditional binary exponential backoff mechanism limits the possible spatial reuse and aggravates some beamforming-related problems such as deafness and headof- line blocking.
To grasp the transmission opportunities offered by beamforming antennas, we design an Opportunistic Directional MAC (OPDMAC) protocol for multihop wireless networks. The OPDMAC protocol employs a novel backoff mechanism in which the node is not forced to undergo idle backoff after a transmission failure but can rather take the opportunity of transmitting other outstanding packets in other directions.
This mechanism minimizes the idle waiting time and increases the channel utilization significantly and thereby enables OPDMAC to enhance the spatial reusability of the wireless medium and reduce the impact of the deafness problem without additional overhead. Through extensive simulations, we demonstrate that OPDMAC enhances the performance in terms of throughput, delay, packet delivery ratio, and fairness.
To further improve its performance, we discuss and evaluate the benefits of carefully choosing some protocol parameters instead of using the default values commonly used by other directional MAC protocols.

Index Terms
Beamforming antennas, medium access control, multihop wireless networks, spatial reuse.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

INTERFERENCE-AWARE ROUTING IN WIRELESS MULTIHOP NETWORKS

Abstract
Interference is an inherent characteristic of wireless (multihop) communications. Adding interference-awareness to important control functions, e.g., routing, could significantly enhance the overall network performance. Despite some initial efforts, it is not yet clearly understood how to best capture the effects of interference in routing protocol design.
Most existing proposals aim at inferring its effect by actively probing the link. However, active probe measurements impose an overhead and may often misrepresent the link quality due to their interaction with other networking functions. Therefore, in this paper we follow a different approach and:
1) propose a simple yet accurate analytical model for the effect of interference on data reception probability, based only on passive measurements and information locally available at the node;
2) use this model to design an efficient interference-aware routing protocol that performs as well as probing-based protocols, yet avoids all pitfalls related to active probe measurements.
To validate our proposal, we have performed experiments in a real testbed, setup in our indoor office environment. We show that the analytical predictions of our interference model exhibit good match with both experimental results as well as more complicated analytical models proposed in related literature.
Furthermore, we demonstrate that a simple probeless routing protocol based on our model performs at least as good as well-known probe-based routing protocols in a large set of experiments including both intraflow and interflow interference.

Index Terms
Wireless networks, interference model, interference-aware routing, routing metric.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

MAC LAYER THROUGHPUT ESTIMATION IN IMPULSE-RADIO UWB NETWORKS

Abstract
The inherent channel characteristics of impulse-based UWB networks affect the MAC layer performance significantly. Most previous studies on evaluating MAC protocols are based on prolonged simulations and do not account for the multiple access interference due to multipath delay spread.
In this work, we develop CTU, an analytical framework for Capturing the Throughput dependencies in UWB networks, while taking into account the PHY layer effects.
The key attributes of CTU are:
1) It is modular; it can be easily modified to provide a basis for evaluating a wide range of MAC protocols for impulse-based UWB networks. The only requirements are that the MAC protocol under study be based on time-hopping and the modulation scheme be pulse position modulation; these are common design decisions in UWB networks.
2) It considers the channel characteristics in addition to MAC layer effects; CTU correlates probabilistically the multipath delay profile of the channel with the packet error rate. We employ CTU to evaluate the performance of different generic medium access procedure.
We compare the results with those from extensive simulations and show the high accuracy of CTU. We use CTU to assess the impact of various system parameters on the MAC layer performance; we make several interesting observations that are discussed in depth.

Index Terms
Ultrawide band (UWB), wireless communications, multipath delay spread, modulation.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

TRAFFIC-DIFFERENTIATION-BASED MODULAR QOS LOCALIZED ROUTING FOR WIRELESS SENSOR NETWORKS

Abstract
A new localized quality of service (QoS) routing protocol for wireless sensor networks (WSN) is proposed in this paper. The proposed protocol targets WSN’s applications having different types of data traffic. It is based on differentiating QoS requirements according to the data type, which enables to provide several and customized QoS metrics for each traffic category.
With each packet, the protocol attempts to fulfill the required data-related QoS metric(s) while considering power efficiency. It is modular and uses geographical information, which eliminates the need of propagating routing information. For link quality estimation, the protocol employs distributed, memory and computation efficient mechanisms.
It uses a multisink single-path approach to increase reliability. To our knowledge, this protocol is the first that makes use of the diversity in data traffic while considering latency, reliability, residual energy in sensor nodes, and transmission power between nodes to cast QoS metrics as a multiobjective problem.
The proposed protocol can operate with any medium access control (MAC) protocol, provided that it employs an acknowledgment (ACK) mechanism.
Extensive simulation study with scenarios of 900 nodes shows the proposed protocol outperforms all comparable state-of-the-art QoS and localized routing protocols. Moreover, the protocol has been implemented on sensor motes and tested in a sensor network testbed.

Index Terms
Wireless sensor networks, quality of service, geographical routing, distributed protocols.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

QOS-AWARE ROUTING AND ADMISSION CONTROL IN SHADOW-FADING ENVIRONMENTS FOR MULTIRATE MANETS

Abstract
Providing quality of service (QoS) assurances in a mobile ad hoc network (MANET) is difficult due to node mobility, contention for channel access, a lack of centralized co-ordination, and the unreliable nature of the wireless channel.
A QoS-aware routing (QAR) protocol and an admission control (AC) protocol are two of the most important components of a system attempting to provide QoS guarantees in the face of the above mentioned difficulties faced. Many QAR and AC-based solutions have been proposed, but such network layer solutions are often designed and studied with idealized lower layer models in mind.
This means that existing solutions are not designed for dealing with practical phenomena such as shadow fading and the link quality-dependent fluctuation of link transmission rates. This paper proposes and evaluates new solutions for improving the performance of QAR and AC protocols in the face of mobility, shadowing, and varying link SINR.
It is found that proactively maintaining backup routes for active sessions, adapting transmission rates, and routing around temporarily low-SINR links can noticeably improve the reliability of assured throughput services.

Index Terms
Multirate mobile ad hoc networks, quality of service aware routing, admission control, shadowing/shadow fading, guaranteed throughput.

IEEE TRANSACTIONS ON MOBILE COMPUTING
VOL. 10, NO. 3, MARCH 2011

PROCESSING CONTINUOUS RANGE QUERIES WITH SPATIOTEMPORAL TOLERANCE

Abstract
Continuous queries are often employed to monitor the locations of mobile objects (MOs), which are determined by sensing devices like GPS receivers.
In this paper, we tackle two challenges in processing continuous range queries (CRQs): coping with data uncertainty inherently associated with location data, and reducing the energy consumption of battery-powered MOs. We propose the concept of spatiotemporal tolerance for CRQ to relax a query’s accuracy requirements in terms of a maximal acceptable error. Unlike previous works, our definition considers tolerance in both the spatial and temporal dimensions, which offers applications more flexibility in specifying their individual accuracy requirements.
As we will show, these tolerance bounds can provide well-defined query semantics in spite of different sources of data uncertainty. In addition, we present efficient algorithms that carefully control when an MO should sense or report a location, while satisfying these tolerances.
Thereby, we particularly reduce the number of position sensing operations substantially, which constitute a considerable source of energy consumption. Extensive simulations confirm that the proposed algorithms result in large energy savings compared to nontolerant query processing.

Index Terms
Tracking mobile objects, continuous queries, distributed processing, data uncertainty, energy consumption.

IEEE TRANSACTIONS ON MOBILE COMPUTING
VOL. 10, NO. 3, MARCH 2011

SCALABLE LOCALIZATION WITH MOBILITY PREDICTION FOR UNDERWATER SENSOR NETWORKS

Abstract
Due to harsh aqueous environments, non-negligible node mobility and large network scale, localization for large-scale mobile underwater sensor networks is very challenging. In this paper, by utilizing the predictable mobility patterns of underwater objects, we propose a scheme, called Scalable Localization scheme with Mobility Prediction (SLMP), for underwater sensor networks.
In SLMP, localization is performed in a hierarchical way, and the whole localization process is divided into two parts: anchor node localization and ordinary node localization. During the localization process, every node predicts its future mobility pattern according to its past known location information, and it can estimate its future location based on the predicted mobility pattern.
Anchor nodes with known locations in the network will control the localization process in order to balance the trade-off between localization accuracy, localization coverage, and communication cost.
We conduct extensive simulations, and our results show that SLMP can greatly reduce localization communication cost while maintaining relatively high localization coverage and localization accuracy.

Index Terms
Network architecture and design, network communications, network protocols, applications, miscellaneous, localization, underwater sensor networks.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011

SECURE HIGH-THROUGHPUT MULTICAST ROUTING IN WIRELESS MESH NETWORKS

Abstract
Recent work in multicast routing for wireless mesh networks has focused on metrics that estimate link quality to maximize throughput. Nodes must collaborate in order to compute the path metric and forward data. The assumption that all nodes are honest and behave correctly during metric computation, propagation, and aggregation, as well as during data forwarding, leads to unexpected consequences in adversarial networks where compromised nodes act maliciously.
In this work, we identify novel attacks against high throughput multicast protocols in wireless mesh networks. The attacks exploit the local estimation and global aggregation of the metric to allow attackers to attract a large amount of traffic. We show that these attacks are very effective against multicast protocols based on high-throughput metrics.
We conclude that aggressive path selection is a double-edged sword: While it maximizes throughput, it also increases attack effectiveness in the absence of defense mechanisms. Our approach to defend against the identified attacks combines measurement-based detection and accusation-based reaction techniques. The solution accommodates transient network variations and is resilient against attempts to exploit the defense mechanism itself.
A detailed security analysis of our defense scheme establishes bounds on the impact of attacks. We demonstrate both the attacks and our defense using ODMRP, a representative multicast protocol for wireless mesh networks, and SPP, an adaptation of the well-known ETX unicast metric to the multicast setting.

Index Terms
Wireless mesh networks, high-throughput metrics, secure multicast routing, metric manipulation attacks, Byzantine attacks.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

THROUGHPUT OPTIMIZATION IN MOBILE BACKBONE NETWORKS

Abstract
This paper describes new algorithms for throughput optimization in a mobile backbone network. This hierarchical communication framework combines mobile backbone nodes, which have superior mobility and communication capability, with regular nodes, which are constrained in mobility and communication capability.
An important quantity of interest in mobile backbone networks is the number of regular nodes that can be successfully assigned to mobile backbone nodes at a given throughput level. This paper develops a novel technique for maximizing this quantity in networks of fixed regular nodes using mixed-integer linear programming (MILP).
The MILP-based algorithm provides a significant reduction in computation time compared to existing methods and is computationally tractable for problems of moderate size. An approximation algorithm is also developed that is appropriate for largescale problems.
This paper presents a theoretical performance guarantee for the approximation algorithm and also demonstrates its empirical performance. Finally, the mobile backbone network problem is extended to include mobile regular nodes, and exact and approximate solution algorithms are presented for this extension.

Index Terms
Wireless sensor networks, mobile communication systems.

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

SUPPORTING EFFICIENT AND SCALABLE MULTICASTING OVER MOBILE AD HOC NETWORKS

Abstract
Group communications are important in Mobile Ad hoc Networks (MANETs). Multicast is an efficient method for implementing group communications. However, it is challenging to implement efficient and scalable multicast in MANET due to the difficulty in group membership management and multicast packet forwarding over a dynamic topology.
We propose a novel Efficient Geographic Multicast Protocol (EGMP). EGMP uses a virtual-zone-based structure to implement scalable and efficient group membership management. A networkwide zone-based bidirectional tree is constructed to achieve more efficient membership management and multicast delivery.
The position information is used to guide the zone structure building, multicast tree construction, and multicast packet forwarding, which efficiently reduces the overhead for route searching and tree structure maintenance. Several strategies have been proposed to further improve the efficiency of the protocol, for example, introducing the concept of zone depth for building an optimal tree structure and integrating the location search of group members with the hierarchical group membership management.
Finally, we design a scheme to handle empty zone problem faced by most routing protocols using a zone structure. The scalability and the efficiency of EGMP are evaluated through simulations and quantitative analysis.
Our simulation results demonstrate that EGMP has high packet delivery ratio, and low control overhead and multicast group joining delay under all test scenarios, and is scalable to both group size and network size. Compared to Scalable Position-Based Multicast (SPBM) [20], EGMP has significantly lower control overhead, data transmission overhead, and multicast group joining delay.

Index Terms
Routing, wireless networks, mobile ad hoc networks, multicast, protocol

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, APRIL 2011

SPATIAL-TEMPORAL COVERAGE OPTIMIZATION IN WIRELESS SENSOR NETWORKS

Abstract
Mission-driven sensor networks usually have special lifetime requirements. However, the density of the sensors may not be large enough to satisfy the coverage requirement while meeting the lifetime constraint at the same time. Sometimes, coverage has to be traded for network lifetime. In this paper, we study how to schedule sensors to maximize their coverage during a specified network lifetime.
Unlike sensor deployment, where the goal is to maximize the spatial coverage, our objective is to maximize the spatialtemporal coverage by scheduling sensors’ activity after they have been deployed. Since the optimization problem is NP-hard, we first present a centralized heuristic whose approximation factor is proved to be 1 2 , and then, propose a distributed parallel optimization protocol (POP). In POP, nodes optimize their schedules on their own but converge to local optimality without conflict with one another.
Theoretical and simulation results show that POP substantially outperforms other schemes in terms of network lifetime, coverage redundancy, convergence time, and event detection probability.

Index Terms
Wireless sensor network, coverage, sensor scheduling, distributed protocol, parallel algorithm

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 6, JUNE 2011

THE HIDENETS HOLISTIC APPROACH FOR THE ANALYSIS OF LARGE CRITICAL MOBILE SYSTEMS

Abstract
Dealing with large, critical mobile systems and infrastructures where ongoing changes and resilience are paramount leads to very complex and difficult challenges for system evaluation.
These challenges call for approaches that are able to integrate several evaluation methods for the quantitative assessment of QoS indicators which have been applied so far only to a limited extent. In this paper, we propose the holistic evaluation framework developed during the recently concluded FP6-HIDENETS project.
It is based on Abstraction and decomposition, and it exploits the interactions among different evaluation techniques including analytical, simulative, and experimental measurement approaches, to manage system complexity.
The feasibility of the holistic approach for the analysis of a complete end-to-end scenario is first illustrated presenting two examples where mobility simulation is used in combination with stochastic analytical modeling, and then through the development and implementation of an evaluation workflow integrating several tools and model transformation steps.

Index Terms
Computer systems organization, communication/networking and information technology, mobile computing, mobile communication systems, computing methodologies, simulation, modeling, and visualization, model development, modeling methodologies, computer applications, mobile applications, pervasive computing.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011

LICKLIDER TRANSMISSION PROTOCOL (LTP)-BASED DTN FOR CISLUNAR COMMUNICATIONS

Abstract
Delay/disruption-tolerant networking (DTN) technology offers a new solution to highly stressed communications in space environments, especially those with long link delay and frequent link disruptions in deep-space missions. To date, little work has been done in evaluating the performance of the available “convergence layer” protocols of DTN, especially the Licklider Transmission Protocol (LTP), when they are applied to an interplanetary Internet (IPN).
In this paper, we present an experimental evaluation of the Bundle Protocol (BP) running over various “convergence layer” protocols in a simulated cislunar communications environment characterized by varying degrees of signal propagation delay and data loss.
We focus on the LTP convergence layer (LTPCL) adapter running on top ofUDP/IP (i.e.,BP/LTPCL/UDP/IP). The performance of BP/LTPCL/UDP/IP in realistic ?le transfers over a PC-based network test bed is compared to that of two other DTN protocol stack options, BP/TCPCL/TCP/IP and BP/UDPCL/UDP/IP. A statistical method of -test is also used for analysis of the experimental results.
The experiment results show that LTPCL has a significant performance advantage over Transmission Control Protocol convergence layer (TCPCL) for link delays longer than 4000 ms regardless of the bit error rate (BER). For a very lossy channel with a BER of around 10, LTPCL has a significant good put advantage over TCPCL at all the link delay levels studied, with an advantage of around 3000 B/s for delays longer than 1500 ms. LTPCL has a consistently significant goodput advantage over UDPCL, around 2500–3000 B/s, at all levels of link delays and BERs.

Index Terms—Bundle Protocol (BP), delay-tolerant networking (DTN), interplanetary Internet (IPN), Licklider Transmission Protocol convergence layer (LTPCL), satellite communications, Transmission Control Protocol convergence layer (TCPCL).

IEEE/ACM TRANSACTIONS ON NETWORKING
VOL. 19, NO. 1, FEBRUARY 2011

FORWARD CORRECTION AND FOUNTAIN CODES IN DELAY-TOLERANT NETWORKS

Abstract
Delay-tolerant ad hoc networks leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other.
To decrease delivery delay, the information to be delivered is replicated in the network. Our objective in this paper is to study a class of replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit.
We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on ?uid approximations, are compared to simulations that validate the model.

Index Terms
Delay-tolerant networks (DTNs), forward correction, fountain codes, mobile ad hoc networks.

IEEE/ACM TRANSACTIONS ON NETWORKING
VOL. 19, NO. 1, FEBRUARY 2011

FAST SIMULATION OF SERVICE AVAILABILITY IN MESH NETWORKS WITH DYNAMIC PATH RESTORATION

Abstract
A fast simulation technique based on importance sampling is developed for the analysis of path service availability in mesh networks with dynamic path restoration. The method combines the simulation of the path rerouting algorithm with a “dynamic path failure importance sampling” (DPFS) scheme to estimate path availabilities efficiently.
In DPFS, the failure rates of network elements are biased at increased rates until path failures are observed under rerouting. The simulated model uses “failure equivalence groups,” with finite/infinite sources of failure events and finite/infinite pools of repair personnel, to facilitate the modeling of bi-directional link failures, multiple in-series link cuts, optical amplifier failures along links, node failures, and more general geographically distributed failure scenarios.
The analysis of a large mesh network example demonstrates the practicality of the technique.

Index Terms
Availability, biasing, failure, importance, mesh, model, network, path, restoration, risk, sampling, simulation.

IEEE/ACM TRANSACTIONS ON NETWORKING
VOL. 19, NO. 1, FEBRUARY 2011

EFFICIENT MULTIPATH COMMUNICATION FOR
TIME-CRITICAL APPLICATIONS IN
UNDERWATER ACOUSTIC SENSOR NETWORKS

Abstract
Due to the long propagation delay and high error rate of acoustic channels, it is very challenging to provide reliable data transfer for time-critical applications in an energy-efficient way. On the one hand, traditional retransmission upon failure usually introduces very large end-to-end delay and is thus not proper for time-critical services.
On the other hand, common approaches without retransmission consume lots of energy. In this paper, we propose a new multipath power-control transmission (MPT) scheme, which can guarantee certain end-to-end packet error rate while achieving a good balance between the overall energy efficiency and the end-to-end packet delay.
MPT smartly combines power control with multipath routing and packet combining at the destination. With carefully designed power-control strategies, MPT consumes much less energy than the conventional one-path transmission scheme without retransmission.
Besides, since no hop-by-hop retransmission is allowed, MPT introduces much shorter delays than the traditional one-path scheme with retransmission. We conduct extensive simulations to evaluate the performance of MPT. Our results show that MPT is highly energy-efficient with low end-to-end packet delays.

Index Terms
Applications, energy efficiency, network communications, underwater sensor networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011 561
Energy-Efficient Protocol for Cooperative Networks
Abstract—In cooperative networks, transmitting and receiving nodes recruit neighboring nodes to assist in communication. We model a cooperative transmission link in wireless networks as a transmitter cluster and a receiver cluster. We then propose a cooperative communication protocol for establishment of these clusters and for cooperative transmission of data. We derive the upper bound of the capacity of the protocol, and we analyze the end-to-end robustness of the protocol to data-packet loss, along with the tradeoff between energy consumption and error rate. The analysis results are used to compare the energy savings and the end-to-end robustness of our protocol with two non-cooperative
schemes, as well as to another cooperative protocol published in the technical literature. The comparison results show that, when nodes are positioned on a grid, there is a reduction in the probability of packet delivery failure by two orders of magnitude for the values of parameters considered. Up to 80% in energy savings can be achieved for a grid topology, while for random node placement our cooperative protocol can save up to 40% in energy consumption relative to the other protocols. The reduction in error rate and the energy savings translate into increased lifetime of cooperative sensor networks.

Index Terms—Clustering, cooperative networks energy-efficient protocols, cooperative transmission, sensor networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011 129
Delay Analysis and Optimality of Scheduling Policies for Multihop Wireless Networks
Abstract—We analyze the delay performance of a multihop wireless network with a ?xed route between each source–destination pair. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multihop nature of the ?ows. A general set-based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample-path delay-optimal. For the tandem queue network, where the delay-optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. We conduct extensive numerical studies to suggest that the average delay of the back-pressure scheduling policy can be made close to the lower bound by using appropriate functions of queue length.

Index Terms—Delay, dynamic control, ?ow control, Lyapunov analysis, Markov chains, optimization, queueing analysis, scheduling, wireless mesh network.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Crosstalk-Preventing Scheduling in Single-and Two-Stage AWG-Based Cell Switches
Abstract—Array waveguide grating (AWG)-based optical switching fabrics are receiving increasing attention due to their simplicity and good performance. However, AWGs are affected by coherent crosstalk that can signi?cantly impair system operation when the same wavelength is used simultaneously on several input ports. To permit large port counts in a AWG, a possible solution is to schedule data transmissions across the AWG preventing switch con?gurations that generate large crosstalk. We study the properties and the existence conditions of switch con?gurations able to control coherent crosstalk. The presented results show that, by running a properly constrained scheduling algorithm to avoid or minimize crosstalk, it is possible to operate an AWG-based switch with large port counts without signi?cant performance degradation.

Index Terms—Arrayed waveguide grating (AWG), coherent crosstalk, input-queued switches, optical switchings, scheduling algorithms.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Jamming-Aware Traf?c Allocation for Multiple-Path Routing Using Portfolio Selection

Abstract—Multiple-path source routing protocols allow a data source node to distribute the total traf?c among available paths. In this paper, we consider the problem of jamming-aware source routing in which the source node performs traf?c allocation based on empirical jamming statistics at individual network nodes. We formulate this traf?c allocation as a lossy network ?ow optimization problem using portfolio selection theory from ?nancial statistics. We show that in multisource networks, this centralized optimization problem can be solved using a distributed algorithm based on decomposition in network utility maximization (NUM). We demonstrate the network’s ability to estimate the impact of jamming and incorporate these estimates into the traf?c allocation problem. Finally, we simulate the achievable throughput using our proposed traf?c allocation method in several scenarios.

Index Terms—Jamming, multiple-path routing, network utility maximization (NUM), optimization, portfolio selection theory.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Continuous Neighbor Discovery in Asynchronous Sensor Networks

Abstract—In most sensor networks, the nodes are static. Nevertheless, node connectivity is subject to changes because of disruptions in wireless communication, transmission power changes, or loss of synchronization between neighboring nodes. Hence, even after a sensor is aware of its immediate neighbors, it must continuously maintain its view, a process we call continuous neighbor discovery. In this work, we distinguish between neighbor discovery during sensor network initialization and continuous neighbor discovery. We focus on the latter and view it as a joint task of all the nodes in every connected segment. Each sensor employs a simple protocol in a coordinate effort to reduce power consumption without increasing the time required to detect hidden sensors.

Index Terms— Neighbor discovery, sensor networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Component-Based Localization in Sparse Wireless Networks

Abstract—Localization is crucial for wireless ad hoc and sensor networks. As the distance-measurement ranges are often less than the communication ranges for many ranging systems, most communication-dense wireless networks are localization-sparse. Consequently, existing algorithms fail to provide accurate localization supports. In order to address this issue, by introducing the concept of component, we group nodes into components so that nodes are able to better share ranging and anchor knowledge. Operating on the granularity of components, our design, CALL, relaxes two essential restrictions in localization: the node ordering and the anchor distribution. Compared to previous designs, CALL is proven to be able to locate the same number of nodes using the least information. We evaluate the effectiveness of CALL through extensive simulations. The results show that CALL locates 90% nodes in a network with average degree 7.5 and 5% anchors, which outperforms the state-of-the-art design Sweeps by about 40%.

Index Terms—Component-based, ?nite mergence, localization, node-based, ranging-model-based estimation (RMBE).

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Cross-Layer Jamming Detection and Mitigation in Wireless Broadcast Networks

Abstract—Wireless communication systems are often susceptible to the jamming attack where adversaries attempt to overpower transmitted signals by injecting a high level of noise. Jamming is dif?cult to mitigate in broadcast networks because transmitting and receiving are inherently symmetric operations: A user that possesses the key to decode a transmission can also use that key to jam the transmission.We describe a code tree system that provides input to the physical layer and helps the physical layer circumvent jammers. In our system, the transmitter has more information than any proper subset of receivers. Each receiver cooperates with the transmitter to detect any jamming that affects that receiver. In the resulting system, each benign user is guaranteed to eliminate the impact of the attacker after some ?nite number of losses with arbitrarily high probability. We show that any system that relies on only using spreading code, and no other physical factors, to mitigate jamming must use at least codes, where is the number of jammers. We then propose an optimized scheme that is power-ef?cient: Each transmission is sent on atmost codes simultaneously. Finally, we demonstrate that our scheme approaches the best possible performance by performing an extensive analysis of the system using both event-driven ns-2 and chip-accurate MATLAB simulations.

Index Terms—Broadcast networks, jamming mitigation, spread spectrum.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011 5
Coloring Spatial Point Processes With Applications to Peer Discovery in Large Wireless Networks

Abstract—In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in adhoc wireless networks.We model channel assignment as a coloring
problem for spatial point processes in which nodes are located in a unit cube uniformly at random and each node is assigned one of colors,where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color.
In general, it is hard to derive the optimal coloring algorithm, and we therefore consider a natural online greedy coloring algorithm ?rst proposed by Ko and Rubenstein in 2005.We prove two key re-
sults: 1) with just colors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility.

Index Terms—Channel assignment, coloring algorithms, peer discovery, spatial point processes, wireless networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
A Uni?ed Approach to Optimizing Performance in Networks Serving Heterogeneous Flows
Abstract—We study the optimal control of communication networks in the presence of heterogeneous traf?c require- ments. Speci?cally, we distinguish the ?ows into two crucial classes: inelastic for modeling high-priority, delay-sensitive, and ?xed-throughput applications; and elastic for modeling low-pri- ority, delay-tolerant, and throughput-greedy applications.We note that the coexistence of such diverse ?ows creates complex interac- tions at multiple levels (e.g., ?ow and packet levels), which prevent the use of earlier design approaches that dominantly assume homogeneous traf?c. In this work, we develop the mathematical framework and novel design methodologies needed to support such heterogeneous requirements and propose provably optimal network algorithms that account for the multilevel interactions between the ?ows. To that end, we ?rst formulate a network optimization problem that incorporates the above throughput and service prioritization requirements of the two traf?c types. We, then develop a distributed joint load-balancing and congestion control algorithm that achieves the dual goal of maximizing the aggregate utility gained by the elastic ?ows while satisfying the ?xed throughput and prioritization requirements of the inelastic ?ows. Next, we extend our joint algorithm in two ways to fur-ther improve its performance: in delay through a virtual queue implementation with minimal throughput degradation and in utilization by allowing for dynamic multipath routing for elastic ?ows. A unique characteristic of our proposed dynamic routing solution is the novel two-stage queueing architecture it introduces to satisfy the service prioritization requirement.

Index Terms—Cross-layer optimization, dynamic load bal-ancing, ?ow rate control, heterogeneous traf?c, routing, sched-uling, utility maximization.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
A Simple Model for Chunk-Scheduling Strategies in P2P Streaming
Abstract—Peer-to-peer (P2P) streaming tries to achieve scal- ability (like P2P ?le distribution) and at the same time meet real-time playback requirements. It is a challenging problem still not well understood. In this paper, we describe a simple stochastic model that can be used to compare different downloading strate- gies to random peer selection. Based on this model, we study the tradeoffs between supported peer population, buffer size, and playback continuity. We ?rst study two simple strategies: Rarest First (RF) and Greedy. The former is a well-known strategy for P2P ?le sharing that gives good scalability by trying to propagate the chunks of a ?le to as many peers as quickly as possible. The latter is an intuitively reasonable strategy to get urgent chunks ?rst to maximize playback continuity from a peer’s local perspective. Yet in reality, both scalability and urgency should be taken care of. With this insight, we propose a Mixed strategy that achieves the best of both worlds. Furthermore, the Mixed strategy comes with an adaptive algorithm that can adapt its buffer setting to dynamic peer population. We validate our analytical model with simulation. Finally, we also discuss the modeling assumptions and the model’s sensitivity to different parameters and show that our model is robust.

Index Terms— Marginal probability model, peer-to-peer (P2P), performance analysis, streaming, video.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
A Novel Approach for Failure Localization
in All-Optical Mesh Networks
Abstract—Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. Monitoring trail (m-trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localiza-tion (UFL) of any single link failure while effectively reducing the amount of alarm signals ?ooding the networks. However, it is crit- ical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the total bandwidth consumed, which ubiquitously determines the length of the alarm code and bandwidth overhead for the m-trail deployment, respec-tively. In this paper, the m-trail design problem is investigated. To gain a deeper understanding of the problem, we ?rst conduct a bound analysis on the minimum length of alarm code of each link required for UFL on the most sparse (i.e., ring) and dense (i.e., fully meshed) topologies. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm is veri?ed by comparison to an integer linear program (ILP) approach, and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consump-tion while achieving signi?cant reduction in computation time. Toinvestigate the impact of topology diversity, extensive simulationis conducted on thousands of random network topologies with systematically increased network density.
Index Terms—Combinatorial group testing, failure localization, monitoring trails.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Stochastic Model and Connectivity Dynamics
for VANETs in Signalized Road Systems
Abstract—The space and time dynamics ofmoving vehicles regulated by traf?c signals governs the node connectivity and communi-cation capability of vehicular ad hoc networks (VANETs) in urban environments. However, none of the previous studies on node con- nectivity has considered such dynamics with the presence of traf?c lights and vehicle interactions. In fact, most of them assume that vehicles are distributed homogeneously throughout the geographic area, which is unrealistic. We introduce in this paper a stochastic traf?c model for VANETs in signalized urban road systems. The proposed model is a composite of the ?uid model and stochastic model. The former characterizes the general ?ow and evolution of the traf?c stream so that the average density of vehicles is readily computable, while the latter takes into account the random be-havior of individual vehicles. As the key contribution of this paper, we attempt to approximate vehicle interactions and capture pla- toon formations and dissipations at traf?c signals through a den- sity-dependent velocity pro?le. The stochastic traf?c model with approximation of vehicle interactions is evaluated with extensive simulations, and the distributional result of the model is validated against real-world empirical data in London. In general, we show that the ?uid model can adequately describe the mean behavior of the traf?c stream, while the stochastic model can approximate the probability distribution well even when vehicles interact with each other as their movement is controlled by traf?c lights. With the knowledge of the mean vehicular density dynamics and its proba- bility distribution from the stochastic traf?c model, we determine the degree of connectivity in the communication network and illus- trate that system engineering and planning for optimizing both the transport (in terms of congestion) and communication networks (in terms of connectivity) can be carried out with the proposed model.

Index Terms—Connectivity, signalized road system, stochastic traffic model, vehicle interaction, vehicular ad hoc network (VANET).

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011 433
TOFU: Semi-Truthful Online Frequency Allocation Mechanism for Wireless Networks
Abstract—In wireless networks, we need to allocate spectrum efficiently. One challenge is that the spectrum usage requests often come in an online fashion. The second challenge is that the secondary users in a cognitive radio network are often sel?sh and prefer to maximize their own bene?ts. In this paper, we address these two challenges by proposing TOFU, a semi-truthful online frequency allocation method for wireless networks when primary users can sublease the spectrums to secondary users. In our protocol, secondary users are required to submit the spectrum bid time slots before its usage. Upon receiving an online spectrum request, our protocol will decide whether to grant its exclusive usage or not, within at least time slots of requests’ arrival. We assume that existing spectrum usage can be preempted with some compensation. For various possible known information,we analytically prove that the competitive ratios of our methods are within small constant factors of the optimum online method. Furthermore, in our mechanisms, no sel?sh users will gain bene?ts by bidding lower than their willing payment. Our extensive simulation results show that they perform almost optimum: Our methods get a total pro?t that is more than 95% of the of?ine optimum when is about the duration of spectrum usage .
Index Terms—Competitive ratio, online allocation, penalty, preemption, spectrum, wireless networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Star-Block Design in Two-Level Survivable Optical Networks

Abstract—An ef?cient fault restoration framework is proposed for accomplishing loopback recovery in optical networks. The pro-posed -cycle-based framework achieves both a minimal spare ca-pacity requirement and a rapid restoration time. In the proposed approach, an algorithm designated as Star-Block is used to sim-plify the original topology to a 2-connected graph and to parti-tion the graph into multiple blocks, where each block contains a center node and the minimum number of neighboring nodes that collectively form a complete cycle. The simpli?ed graph is then restored to the original topology using conventional graph rules. The Block Selection algorithm is then used to assign the edges be-longing to multiple blocks to an appropriate block for fault recovery purposes.Within each block, the working ?ows are restored in real-time via local -cycles on the on-cycle and spoke ?bers. The performance of the proposed protection framework is evaluated numerically in terms of the spare capacity to working capacity ratio and the length of the restoration path. The framework has a better spare capacity ef?ciency than existing loopback recovery schemes or the conventional -cycles approach. In addition, the Star-Block decomposition algorithm shortens the average length of the restoration path and therefore reduces the restoration time. Finally, the protection scheme not only provides a differentiated recovery service for traf?c with different QoS requirements in the event of single-link failures within a single block, but also supports multiple-fault restoration for the case in whichmultiple single-link failures occur simultaneously.

Index Terms—Block Selection algorithm, multiple-fault restoration, restoration path, spare capacity ef?ciency, Star-Block algorithm, survivable optical networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
SPAF: Stateless FSA-Based Packet Filters

Abstract—We propose a stateless packet ?altering technique based on ?nite-state automata (FSA). FSAs provide a comprehensive framework with well-de?ned composition operations that enable the generation of stateless ?lters from high-level speci?cations and their compilation into ef?cient executable code without resorting to various opportunistic optimization algorithms. In contrast with most traditional approaches, memory safety and termination can be enforced with minimal run-time overhead even in cyclic ?lters, thus enabling full parsing of complex protocols and supporting recursive encapsulation relationships. Experimental evidence shows that this approach is viable and improves the state of the art in terms of ?lter ?exibility, performance, and scalability without incurring in the most common FSA de?ciencies, such as state-space explosion.

Index Terms—Algorithms, ?ltering algorithms, ?nite-state automata (FSA), mathematics, packet ?lters, packet processing, predicate optimization, protocol description languages (PDLs), run-time safety.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Scheduling Algorithms for Multicarrier Wireless Data Systems
Abstract—We consider the problem of scheduling multicarrier wireless data in systems such as IEEE 802.16 (WiMAX). Each scheduling decision involves assigning carriers to users for each time slot, subject to the constraint that each carrier is assigned to at most one user, but multiple carriers can potentially be assigned to the same user. One important aspect of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision ismade. This “global” information may give a potential for enhancing performance via an optimized allocation of carriers to users. We analyze this problem in a situation where ?nite queues are fed by a data arrival process. The well-known MaxWeight algorithm for the single-carrier setting maximizes the product of queue size and service rate.We focus on how to adapt MaxWeight to the multicarrier setting. If the same objective is pursued, more service than needed may be assigned to drain a queue, thereby creating wastage. While a simple variant in the objective forbids this wastage, it turns an easy-to-compute old objective into an intractable new objective. We state the hardness of the new optimization problems and propose several extremely simple algorithms with provable performance bounds. We conclude with supporting simulation examples.

Index Terms—Communication systems, communications tech-nology, max weight, multicarrier, scheduling, stability, wireless communication, wireless networks, wireless systems.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Self-Reconfigurable Wireless Mesh Networks

Abstract—During their lifetime, multihop wireless mesh networks (WMNs) experience frequent link failures caused by channel interference, dynamic obstacles, and/or applications’ bandwidth demands. These failures cause severe performance degradation in WMNs or require expensive manual network
management for their real-time recovery. This paper presents an autonomous network reconfiguration system (ARS) that enables a multiradio WMN to autonomously recover from local link failures to preserve network performance. By using channel and radio diversities in WMNs, ARS generates necessary changes in local radio and channel assignments in order to recover from failures. Next, based on the thus-generated configuration changes, the system cooperatively reconfigures network settings among local mesh routers. ARS has been implemented and evaluated extensively on our IEEE 802.11-based WMN test-bed as well as through ns2-based simulation. Our evaluation results show that ARS outperforms existing failure-recovery schemes in improving channel-ef?ciency by more than 90%and in the ability of meeting the applications’ bandwidth demands by an average of 200%.

Index Terms—IEEE 802.11, multiradio wireless mesh networks (mr-WMNs), self-reconfigurable networks, wireless link failures.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
ProgME: Towards Programmable Network MEasurement
Abstract—Traf?c measurements provide critical input for a wide range of network management applications, including traf?c engineering, accounting, and security analysis. Existing measurement tools collect traf?c statistics based on some predetermined, inflexible concept of “?ows.” They do not have sufficient ,built-in intelligence to understand the application requirements or adapt to the traffic conditions. Consequently, they have limited scalability with respect to the number of ?ows and the heterogeneity of monitoring applications. We present ProgME, a Programmable MEasurement architecture based on a novel concept of ?owset—an arbitrary set of ?ows de?ned according to application requirements and/or traffic conditions. Through a simple ?owset composition language, ProgME can incorporate application requirements, adapt itself to circumvent the scalability challenges posed by the large number of ?ows, and achieve a better application-perceived accuracy. The modular design of ProgME enables it to exploit the surging popularity of multicore processors to cope with 7-Gb/s line rate. ProgME can analyze and adapt to traffic statistics in real time. Using sequential hypothesis test, ProgME can achieve fast and scalable heavy hitter identification.

Index Terms—Flowset, Flowset Composition Language (FCL), Multi-Resolution Tiling (MRT), network traf?c measurement, programmable measurement.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Scalable and Cost-Effective Interconnection of Data-Center Servers Using Dual Server Ports

Abstract—The goal of data-center networking is to interconnect a large number of server machines with low equipment cost while providing high network capacity and high bisection width. It is well understood that the current practice where servers are connected by a tree hierarchy of network switches cannot meet these requirements. In this paper, we explore a new server-in-terconnection structure. We observe that the commodity server machines used in today’s data centers usually come with two built-in Ethernet ports, one for network connection and the other left for backup purposes.We believe that if both ports are actively used in network connections, we can build a scalable, cost-effective interconnection structure without either the expensive higher-level large switches or any additional hardware on servers. We design such a networking structure called FiConn. Although the server node degree is only 2 in this structure, we have proven that FiConn is highly scalable to encompass hundreds of thousands of servers with low diameter and high bisection width. We have developed a low-overhead traf?c-aware routing mechanism to improve effective link utilization based on dynamic traf?c state. We have also proposed how to incrementally deploy FiConn.
Index Terms—Computer networks, computers and information processing, Internet.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Primary User Activity Modeling Using First-Difference Filter Clustering and Correlation in Cognitive Radio Networks

Abstract—In many recent studies on cognitive radio (CR) networks, the primary user activity is assumed to follow the Poisson traf?c model with exponentially distributed interarrivals. The Poisson modeling may lead to cases where primary user activities are modeled as smooth and burst-free traf?c. As a result, this may cause the cognitive radio users to miss some available but unuti- lized spectrum, leading to lower throughput and high false-alarm probabilities. The main contribution of this paper is to propose a novel model to parametrize the primary user traf?c in a more ef?cient and accurate way in order to overcome the drawbacks of the Poisson modeling. The proposed model makes this possible
by arranging the ?rst-difference ?ltered and correlated primary user data into clusters. In this paper, a new metric called the Primary User Activity Index, , is introduced, which accounts for the relation between the cluster ?lter output and correlation statistics. The performance of the proposed model is evaluated by means of traf?c estimation accuracy, false-alarm probabilities while keeping the detection probability of primary users at a constant value. Simulation results show that the appropriate selection of the Primary User Activity Index, higher primary-user detection accuracy, reduced false-alarm probabilities, and higher throughput can be achieved by the proposed model.
Index Terms—Clustering, cognitive radio (CR) networks, pri-mary user activity modeling.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Practical Computation of Optimal Schedules in Multihop Wireless Networks

Abstract—Interference and collisions greatly limit the throughput of mesh networks that use contention-based MAC protocols such as IEEE 802.11. Signi?cantly higher throughput is achievable if transmissions are scheduled. However, traditional methods to compute optimal schedules are computationally in-tractable (unless co-channel interference is neglected). This paper presents a practical technique to compute optimal schedules. The resulting algorithm searches for a low-dimensional optimization problem that has the same solution as the full problem. Such a low-dimensional problem is shown to always exist. The resulting algorithm converges arithmetically fast or geometrically fast, de- pending on whether the objective is to maximize the proportional fair throughput or to maximize the minimum throughput, where the minimum is over all ?ows in the network. At each iteration of the algorithm, a graph-theoretic optimization known as the maximum weighted independent set (MWIS) problem must be solved. While the general MWIS problem is NP-hard in the worst case, we ?nd that the MWIS can be solved ef?ciently. Speci?cally, computational experiments on over 17 000 topologies indicate that the ratio of the time to solve the MWIS and the mean degree of the con?ict graph grows polynomially with the number of nodes.
Index Terms— Mesh networks, optimal scheduling.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Parametric Methods for Anomaly Detection in Aggregate Traf?c

Abstract—This paper develops parametric methods to detect network anomalies using only aggregate traf?c statistics, in contrast to other works requiring ?ow separation, even when the anomaly is a small fraction of the total traf?c. By adopting simple statistical models for anomalous and background traf?c in the time domain, one can estimate model parameters in real time, thus obviating the need for a long training phase or manual parameter tuning. The proposed bivariate parametric detection mechanism (bPDM) uses a sequential probability ratio test, allowing for control over the false positive rate while examining the tradeoff between detection time and the strength of an anomaly. Additionally, it uses both traf?c-rate and packet-size statistics, yielding a bivariate model that eliminates most false positives. The method is analyzed using the bit-rate signal-to-noise ratio (SNR) metric, which is shown to be an effective metric for anomaly detection. The performance of the bPDM is evaluated in three ways. First, synthetically generated traf?c provides for a controlled comparison of detection time as a function of the anomalous level of traf?c. Second, the approach is shown to be able to detect controlled arti?cial attacks over the University of Southern California (USC), Los Angeles, campus network in varying real traf?c mixes. Third, the proposed algorithm achieves rapid detection of real denial-of-service attacks as determined by the replay of previously captured network traces. The method developed in this paper is able to detect all attacks in these scenarios in a few seconds or less.
Index Terms—Aggregate traf?c, anomaly detection, distributed denial of service (DDoS), parametric models.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Optimal Anycast Technique for Delay-Sensitive Energy-Constrained Asynchronous Sensor Networks
Abstract—In wireless sensor networks (WSNs), asynchronous sleep–wake scheduling protocols can be used to signi?cantly reduce energy consumption without incurring the communica- tion overhead for clock synchronization needed for synchronous sleep–wake scheduling protocols. However, these savings could come at a signi?cant cost in delay performance. Recently, re- searchers have attempted to exploit the inherent broadcast nature of the wireless medium to reduce this delay with virtually no additional energy cost. These schemes are called “anycasting,” where each sensor node forwards the packet to the ?rst node that wakes up among a set of candidate next-hop nodes. In this paper, we develop a delay-optimal anycasting scheme under periodic sleep–wake patterns. Our solution is computationally simple and fully distributed. Furthermore, we show that periodic sleep–wake patterns result in the smallest delay among all wake-up patterns under given energy constraints. Simulation results illustrate the bene?t of our proposed schemes over the state of the art.

Index Terms—Anycast, delay, energy ef?ciency, periodic wake-up process, sensor network, sleep–wake scheduling.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
On the Price of Security in Large-Scale Wireless Ad Hoc Networks
Abstract—Security always comes with a price in terms of per- formance degradation, which should be carefully quanti?ed. This is especially the case for wireless ad hoc networks (WANETs), which offer communications over a shared wireless channel without any preexisting infrastructure. Forming end-to-end secure paths in such WANETs is more challenging than in con-ventional networks due to the lack of central authorities, and its impact on network performance is largely untouched in the literature. In this paper, based on a general random network model, the asymptotic behaviors of secure throughput and delay with the common transmission range and the probability of neighboring nodes having a primary security association are quanti?ed when the network size is suf?ciently large. The costs and bene?ts of secure-link-augmentation operations on the secure throughput and delay are also analyzed. In general, security has a cost: Since we require all the communications operate on secure links, there is a degradation in the network performance. This implies that even when the goes to zero as the network size becomes arbi-trarily large, it is still possible to build throughput-order-optimal secure WANETs, which is of practical interest since is very small in many practical large-scale WANETs.
Index Terms—Ad hoc networks, network performance, network security, wireless networks.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
On the Complexity of the Regenerator Placement Problem in Optical Networks
Abstract—Placement of regenerators in optical networks has attracted the attention of recent research works in optical net-works. In this problem, we are given a network with an underlying topology of a graph and with a set of requests that correspond to paths in . There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this paper, we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results
regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include poly-nomial time algorithms, NP-completeness results, approximation algorithms, and inapproximability results.
Index Terms—Approximation algorithms, complexity, optical networks, regenerators, wavelength divisionmultiplexing (WDM).

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Network-Coding Multicast Networks With QoS Guarantees
Abstract—It is well known that without admission control, net-work congestion is bound to occur. However, to implement admis-sion control is dif?cult in IP-based networks,which are constructed out of the end-to-end principle, and semantics of most major sig-naling protocols can only be interpreted at the edge of the net-work. Even if routers can perform admission control internally, the path computation and the state updating activities required for setting up and tearing down each ?ow will overwhelmthe network. A new QoS architecture, called a nonblocking network, has been proposed recently, and it requires no internal admission control and can still offer hard QoS guarantees. In this architecture, as long as each edge node admits not more than a speci?ed amount of traf?c, the network will never experience link congestion. For multicast networks, the main problem with this approach is low throughput. Conventional tree-based multicast routing algorithms lead to a throughput so low that the nonblocking concept is ren-dered impractical. In this paper, we show how network coding can solve this problem. We demonstrate that a nonblocking unicast network and a multicast network share the same optimal paths, and that a nonblockingmulticast networkwith network coding can admit the same amount of traf?c as a nonblocking unicast network. The above conclusions apply to explicit-routing (MPLS-like) and shortest-path routing (IP-like) networks.
Index Terms—Multicast, network coding, nonblocking.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Model-Based Identi?cation of Dominant Congested Links

Abstract—In this paper, we propose a model-based approach that uses periodic end–end probes to identify whether a “domi-nant congested link” exists along an end–end path. Informally, a dominant congested link refers to a link that incurs the most losses and signi?cant queuing delays along the path. We begin by providing a formal yet intuitive de?nition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present a novel model-based approach for dominant congested link identi?cation that is based on inter-preting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for hiddenMarkovmodel (HMM) and Markov model with a hidden dimension (MMHD) to infer this virtual delay. Our validation using ns simulation and Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further provide an upper bound on the maximum queuing delay of the dominant congested link once we identify that such a link exists.
Index Terms—Bottleneck link, dominant congested link, end–end inference, hiddenMarkov model (HMM),Markov model with a hidden dimension (MMHD), network inference, network management, path characteristics.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 2, APRIL 2011
Delay-Optimal Opportunistic Scheduling and Approximations: The Log Rule
Abstract—This paper considers the design of multiuser op-portunistic packet schedulers for users sharing a time-varying wireless channel from performance and robustness points of view. For a simpli?ed model falling in the classical Markov decision process framework, we numerically compute and characterize mean-delay-optimal scheduling policies. The computed policies ex-hibit radial sum-rate monotonicity: As users’ queues grow linearly, the scheduler allocates service in a manner that deemphasizes the balancing of unequal queues in favor of maximizing current system throughput (being opportunistic). This is in sharp contrast to previously proposed throughput-optimal policies, e.g., Exp rule and MaxWeight (with any positive exponent of queue length). In order to meet performance and robustness objectives, we propose a new class of policies, called the Log rule, that are radial sum-rate monotone (RSM) and provably throughput-optimal. In fact, it can also be shown that an RSM policy minimizes the asymptotic probability of sum-queue over?ow. We use extensive simulations to explore various possible design objectives for opportunistic schedulers. When users see heterogenous channels, we ?nd that emphasizing queue balancing, e.g., Exp rule and MaxWeight, may excessively compromise the overall delay. Finally, we discuss approaches to implement the proposed policies for scheduling and resource allocation in OFDMA-based multichannel systems.
Index Terms—Delay/throughput optimality, Markov decision process, OFDMA resource allocation, opportunistic scheduling,
radial sum-rate monotonicity (RSM).

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Live Streaming With Receiver-Based Peer-Division Multiplexing
Abstract—A number of commercial peer-to-peer (P2P) systems for live streaming have been introduced in recent years. The behavior of these popular systems has been extensively studied in several measurement papers. Due to the proprietary nature of these commercial systems, however, these studies have to rely on a “black-box” approach, where packet traces are collected from a single or a limited number of measurement points, to infer various properties of traf?c on the control and data planes. Although such studies are useful to compare different systems from the end-user’s perspective, it is dif?cult to intuitively understand the observed properties without fully reverse-engineering the under-lying systems. In this paper, we describe the network architecture of Zattoo, one of the largest production live streaming providers in Europe at the time of writing, and present a large-scale mea- surement study of Zattoo using data collected by the provider. To highlight, we found that even when the Zattoo system was heavily loaded with as high as 20 000 concurrent users on a single overlay, the median channel join delay remained less than 2–5 s, and that, for a majority of users, the streamed signal lags over-the-air broadcast signal by no more than 3 s.
Index Terms—Live streaming, network architecture, peer-to-peer (P2P) system.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEBRUARY 2011
Topological Transformation Approaches to TCAM-Based Packet Classi?cation

Abstract—Several range reencoding schemes have been pro-posed to mitigate the effect of range expansion and the limitations of small capacity, large power consumption, and high heat gen-eration of ternary content addressable memory (TCAM)-based packet classi?cation systems. However, they all disregard the se- mantics of classi?ers and therefore miss signi?cant opportunities for space compression. In this paper, we propose new approaches to range reencoding by taking into account classi?er semantics. Fundamentally different from prior work, we view reencoding as a topological transformation process from one colored hyperrect- angle to another, where the color is the decision associated with a given packet. Stated another way, we reencode the entire classi?er by considering the classi?er’s decisions rather than reencode only ranges in the classi?er ignoring the classi?er’s decisions as prior work does. We present two orthogonal, yet composable, reen- coding approaches: domain compression and pre?x alignment. Our techniques signi?cantly outperform all previous reencoding techniques. In comparison to prior art, our experimental results show that our techniques achieve at least ?ve times more space reduction in terms of TCAM space for an encoded classi?er and at least three times more space reduction in terms of TCAM space for a reencoded classi?er and its transformers. This, in turn, leads to improved throughput and decreased power consumption.

Index Terms—Hardware-based packet classi?cation, range en-coding, ternary content addressable memory (TCAM).

Cloud Computing
Performance Analysis of Cloud Computing Services for Many-Tasks Scientific Computing
Parallel and Distributed Systems, IEEE Transactions on Issue Date: June 2011

Abstract
Cloud computing is an emerging commercial infrastructure paradigm that promises to eliminate the need for maintaining expensive computing facilities by companies and institutes alike. Through the use of virtualization and resource time sharing, clouds serve with a single set of physical resources a large user base with different needs. Thus, clouds have the potential to provide to their owners the benefits of an economy of scale and, at the same time, become an alternative for scientists to clusters, grids, and parallel production environments. However, the current commercial clouds have been built to support web and small database workloads, which are very different from typical scientific computing workloads. Moreover, the use of virtualization and resource time sharing may introduce significant performance penalties for the demanding scientific computing workloads. In this work, we analyze the performance of cloud computing services for scientific computing workloads. We quantify the presence in real scientific computing workloads of Many-Task Computing (MTC) users, that is, of users who employ loosely coupled applications comprising many tasks to achieve their scientific goals. Then, we perform an empirical evaluation of the performance of four commercial cloud computing services including Amazon EC2, which is currently the largest commercial cloud. Last, we
compare through trace-based simulation the performance characteristics and cost models of clouds and other scientific computing platforms, for general and MTC-based scientific computing workloads. Our results indicate that the current clouds need an order of magnitude in performance improvement to be useful to the scientific community, and show which improvements should be considered first to address this discrepancy between offer and demand.

Cloud Computing
Exploiting Dynamic Resource Allocation for Efficient Parallel Data Processing in the Cloud
Parallel and Distributed Systems, IEEE Transactions on Issue Date: June 2011
In recent years ad hoc parallel data processing has emerged to be one of the killer applications for Infrastructure-as-a-Service (IaaS) clouds. Major Cloud computing companies have started to integrate frameworks for parallel data processing in their product portfolio, making it easy for customers to access these services and to deploy their programs. However, the processing frameworks which are currently used have been designed for static, homogeneous cluster setups and disregard the particular nature of a cloud. Consequently, the allocated compute resources may be inadequate for big parts of the submitted job and unnecessarily increase processing time and cost. In this paper, we discuss the opportunities and challenges for efficient parallel data processing in clouds and present our research project Nephele. Nephele is the first data processing framework to explicitly exploit the dynamic resource allocation offered by today's IaaS clouds for both, task scheduling and execution. Particular tasks of a processing job can be assigned to different types of virtual machines which are automatically instantiated and terminated during the job execution. Based on this new framework, we perform extended evaluations of MapReduce-inspired processing jobs on an IaaS cloud system and compare the results to the popular data processing framework Hadoop.

Cloud Computing
Enabling Public Auditability and Data Dynamics for Storage Security in Cloud Computing
Parallel and Distributed Systems, IEEE Transactions on Issue Date: May 2011
Abstract

Cloud Computing has been envisioned as the next-generation architecture of IT Enterprise. It moves the application software and databases to the centralized large data centers, where the management of the data and services may not be fully trustworthy. This unique paradigm brings about many new security challenges, which have not been well understood. This work studies the problem of ensuring the integrity of data storage in Cloud Computing. In particular, we consider the task of allowing a third party auditor (TPA), on behalf of the cloud client, to verify the integrity of the dynamic data stored in the cloud. The introduction of TPA eliminates the involvement of the client through the auditing of whether his data stored in the cloud are indeed intact, which can be important in achieving economies of scale for Cloud Computing. The support for data dynamics via the most general forms of data operation, such as block modification, insertion, and deletion, is also a significant step toward practicality, since services in Cloud Computing are not limited to archive or backup data only. While prior works on ensuring remote data integrity often lacks the support of either public auditability or dynamic data operations, this paper achieves both. We first identify the difficulties and potential security problems of direct extensions with fully dynamic data updates from prior works and then show how to construct an elegant verification scheme for the seamless integration of these two salient features in our protocol design. In particular, to achieve efficient data dynamics, we improve the existing proof of storage models by manipulating the classic Merkle Hash Tree construction for block tag authentication. To support efficient handling of multiple auditing tasks, we further explore the technique of bilinear aggregate signature to extend our main result into a multiuser setting, where TPA can perform multiple auditing tasks simultaneously. Extensive security and performance analysis show that the proposed schemes are highly efficient and provably secure.

Cloud Computing
Heuristics Based Query Processing for Large RDF Graphs Using Cloud Computing
Knowledge and Data Engineering, IEEE Transactions on

Abstract
Semantic Web is an emerging area to augment human reasoning for which various technologies are being developed. These technologies have been standardized by W3C. One such standard is the RDF. With the explosion of semantic web technologies, large RDF graphs are common place. Current frameworks do not scale for large RDF graphs and as a result does not address these challenges. In this paper, we describe a framework that we built using Hadoop to store and retrieve large numbers of RDF triples by exploiting the cloud computing paradigm. We describe a scheme to store RDF data in Hadoop Distributed File System. More than one Hadoop job may be needed to answer a query because a triple pattern in a query cannot take part in more than one join in a Hadoop job. To determine the jobs, we present an algorithm to generate query plan, whose worst case cost is bounded, based on a greedy approach to answer a SPARQL query. We use Hadoop's MapReduce framework to answer the queries. Our results show that we can store large RDF graphs in Hadoop clusters built with cheap commodity class hardware. Furthermore, we show that our framework is scalable and efficient and can handle large amounts of RDF data, unlike traditional approaches.

Cloud Computing
Optimization of Resource Provisioning Cost in Cloud Computing
IEEE Transactions on Services Computing
Abstract
In cloud computing, cloud providers can offer cloud consumers two provisioning plans for computing resources, namely reservation and on-demand plans. In general, cost of utilizing computing resources provisioned by reservation plan is cheaper than that provisioned by on-demand plan, since cloud consumer has to pay to provider in advance. With the reservation plan, the consumer can reduce the total resource provisioning cost. However, the best advance reservation of resources is difficult to be achieved due to uncertainty of consumer’s future demand and providers’ resource prices. To address this problem, an optimal cloud resource provisioning (OCRP) algorithm is proposed by formulating a stochastic programming model. The OCRP algorithm can provision computing resources for being used in multiple provisioning stages as well as a long-term plan, e.g., four stages in a quarter plan and twelve stages in a yearly plan. The demand and price uncertainty is considered in OCRP. In this paper, different approaches to obtain the solution of OCRP algorithm are considered including deterministic equivalent formulation, sample-average approximation, and Benders decomposition. Numerical studies are extensively performed in which the results clearly show that with the OCRP algorithm, cloud consumer can successfully minimize total cost of resource provisioning in cloud computing environments.

Cloud Computing
Towards Secure and Dependable Storage Services in Cloud Computing
Services Computing, IEEE Transactions on

Abstract
As one of the emerging services in cloud paradigm, cloud storage enables users to remotely store their data into the cloud so as to enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources. While cloud storage relieves users from the burden of local storage management and maintenance, it is also relinquishing users’ ultimate control over the fate of their data, which may put the correctness of outsourced data into risks. In order to regain the assurances of cloud data integrity and availability and enforce the quality of cloud storage service for users, we propose a highly efficient and flexible distributed storage verification scheme with two salient features, opposing to its predecessors. By utilizing the homomorphic token with distributed erasure-coded data, our scheme achieves the integration of storage correctness insurance and data error localization, i.e., the identification of misbehaving server(s). Unlike most prior works, the new scheme further supports secure and efficient dynamic operations on outsourced data, including: block modification, deletion and append. Extensive security and performance analysis shows the proposed scheme is highly efficient and resilient against Byzantine failure, malicious data modification attack, and even server colluding attacks.

Cloud Computing
CloudTPS: Scalable Transactions for Web Applications in the Cloud
Services Computing, IEEE Transactions on

Abstract
NoSQL Cloud data stores provide scalability and high availability properties for web applications, but at the same time they sacrifice data consistency. However, many applications cannot afford any data inconsistency. CloudTPS is a scalable transaction manager which guarantees full ACID properties for multi-item transactions issued by Web applications, even in the presence of server failures and network partitions. We implement this approach on top of the two main families of scalable data layers: Bigtable and SimpleDB. Performance evaluation on top of HBase (an open-source version of Bigtable) in our local cluster and Amazon SimpleDB in the Amazon cloud shows that our system scales linearly at least up to 40 nodes in our local cluster and 80 nodes in the Amazon cloud.

Mining Cluster-Based Temporal Mobile Sequential Patterns in Location-Based Service Environments
Knowledge and Data Engineering, IEEE Transactions on Issue Date: June 2011

Abstract
Researches on Location-Based Service (LBS) have been emerging in recent years due to a wide range of potential applications. One of the active topics is the mining and prediction of mobile movements and associated transactions. Most of existing studies focus on discovering mobile patterns from the whole logs. However, this kind of patterns may not be precise enough for predictions since the differentiated mobile behaviors among users and temporal periods are not considered. In this paper, we propose a novel algorithm, namely, Cluster-based Temporal Mobile Sequential Pattern Mine (CTMSP-Mine), to discover the Cluster-based Temporal Mobile Sequential Patterns (CTMSPs). Moreover, a prediction strategy is proposed to predict the subsequent mobile behaviors. In CTMSP-Mine, user clusters are constructed by a novel algorithm named Cluster-Object-based Smart Cluster Affinity Search Technique (CO-Smart-CAST) and similarities between users are evaluated by the proposed measure, Location-Based Service Alignment (LBS-Alignment). Meanwhile, a time segmentation approach is presented to find segmenting time intervals where similar mobile characteristics exist. To our best knowledge, this is the first work on mining and prediction of mobile behaviors with considerations of user relations and temporal property simultaneously. Through experimental evaluation under various simulated conditions, the proposed methods are shown to deliver excellent performance.

Cosdes: A Collaborative Spam Detection System with a Novel E-Mail Abstraction Scheme
Knowledge and Data Engineering, IEEE Transactions on Issue Date: May 2011
Abstract
E-mail communication is indispensable nowadays, but the e-mail spam problem continues growing drastically. In recent years, the notion of collaborative spam filtering with near-duplicate similarity matching scheme has been widely discussed. The primary idea of the similarity matching scheme for spam detection is to maintain a known spam database, formed by user feedback, to block subsequent near-duplicate spams. On purpose of achieving efficient similarity matching and reducing storage utilization, prior works mainly represent each e-mail by a succinct Abstraction derived from e-mail content text. However, these Abstractions of e-mails cannot fully catch the evolving nature of spams, and are thus not effective enough in near-duplicate detection. In this paper, we propose a novel e-mail Abstraction scheme, which considers e-mail layout structure to represent e-mails. We present a procedure to generate the e-mail Abstraction using HTML content in e-mail, and this newly devised Abstraction can more effectively capture the near-duplicate phenomenon of spams. Moreover, we design a complete spam detection system Cosdes (standing for COllaborative Spam DEtection System), which possesses an efficient near-duplicate matching scheme and a progressive update scheme. The progressive update scheme enables system Cosdes to keep the most up-to-date information for near-duplicate detection. We evaluate Cosdes on a live data set collected from a real e-mail server and show that our system outperforms the prior approaches in detection results and is applicable to the real world.

A Link Analysis Extension of Correspondence Analysis for Mining Relational Databases
Knowledge and Data Engineering, IEEE Transactions on Issue Date: April 2011
Abstract
This work introduces a link analysis procedure for discovering relationships in a relational database or a graph, generalizing both simple and multiple correspondence analysis. It is based on a random walk model through the database defining a Markov chain having as many states as elements in the database. Suppose we are interested in analyzing the relationships between some elements (or records) contained in two different tables of the relational database. To this end, in a first step, a reduced, much smaller, Markov chain containing only the elements of interest and preserving the main characteristics of the initial chain, is extracted by stochastic complementation. This reduced chain is then analyzed by projecting jointly the elements of interest in the diffusion map subspace and visualizing the results. This two-step procedure reduces to simple correspondence analysis when only two tables are defined, and to multiple correspondence analysis when the database takes the form of a simple star-schema. On the other hand, a kernel version of the diffusion map distance, generalizing the basic diffusion map distance to directed graphs, is also introduced and the links with spectral clustering are discussed. Several data sets are analyzed by using the proposed methodology, showing the usefulness of the technique for extracting relationships in relational databases or graphs.

A Personalized Ontology Model for Web Information Gathering

Knowledge and Data Engineering, IEEE Transactions on
Issue Date: April 2011
Abstract
As a model for knowledge description and formalization, ontologies are widely used to represent user profiles in personalized web information gathering. However, when representing user profiles, many models have utilized only knowledge from either a global knowledge base or a user local information. In this paper, a personalized ontology model is proposed for knowledge representation and reasoning over user profiles. This model learns ontological user profiles from both a world knowledge base and user local instance repositories. The ontology model is evaluated by comparing it against benchmark models in web information gathering. The results show that this ontology model is successful.

A Machine Learning Approach for Identifying Disease-Treatment Relations in Short Texts
Knowledge and Data Engineering, IEEE Transactions on Issue Date: June 2011

Abstract
The Machine Learning (ML) field has gained its momentum in almost any domain of research and just recently has become a reliable tool in the medical domain. The empirical domain of automatic learning is used in tasks such as medical decision support, medical imaging, protein-protein interaction, extraction of medical knowledge, and for overall patient management care. ML is envisioned as a tool by which computer-based systems can be integrated in the healthcare field in order to get a better, more efficient medical care. This paper describes a ML-based methodology for building an application that is capable of identifying and disseminating healthcare information. It extracts sentences from published medical papers that mention diseases and treatments, and identifies semantic relations that exist between diseases and treatments. Our evaluation results for these tasks show that the proposed methodology obtains reliable outcomes that could be integrated in an application to be used in the medical care domain. The potential value of this paper stands in the ML settings that we propose and in the fact that we outperform previous results on the same data set.

Design and Implementation of an Intrusion Response System for Relational Databases
Knowledge and Data Engineering, IEEE Transactions on Issue Date: June 2011
Abstract
The intrusion response component of an overall intrusion detection system is responsible for issuing a suitable response to an anomalous request. We propose the notion of database response policies to support our intrusion response system tailored for a DBMS. Our interactive response policy language makes it very easy for the database administrators to specify appropriate response actions for different circumstances depending upon the nature of the anomalous request. The two main issues that we address in context of such response policies are that of policy matching, and policy administration. For the policy matching problem, we propose two algorithms that efficiently search the policy database for policies that match an anomalous request. We also extend the PostgreSQL DBMS with our policy matching mechanism, and report experimental results. The experimental evaluation shows that our techniques are very efficient. The other issue that we address is that of administration of response policies to prevent malicious modifications to policy objects from legitimate users. We propose a novel Joint Threshold Administration Model (JTAM) that is based on the principle of separation of duty. The key idea in JTAM is that a policy object is jointly administered by at least k database administrator (DBAs), that is, any modification made to a policy object will be invalid unless it has been authorized by at least k DBAs. We present design details of JTAM which is based on a cryptographic threshold signature scheme, and show how JTAM prevents malicious modifications to policy objects from authorized users. We also implement JTAM in the PostgreSQL DBMS, and report experimental results on the efficiency of our techniques.

Classification and Novel Class Detection in Concept-Drifting Data Streams under Time Constraints
Knowledge and Data Engineering, IEEE Transactions on Issue Date: June 2011
Abstract
Most existing data stream classification techniques ignore one important aspect of stream data: arrival of a novel class. We address this issue and propose a data stream classification technique that integrates a novel class detection mechanism into traditional classifiers, enabling automatic detection of novel classes before the true labels of the novel class instances arrive. Novel class detection problem becomes more challenging in the presence of concept-drift, when the underlying data distributions evolve in streams. In order to determine whether an instance belongs to a novel class, the classification model sometimes needs to wait for more test instances to discover similarities among those instances. A maximum allowable wait time Tc is imposed as a time constraint to classify a test instance. Furthermore, most existing stream classification approaches assume that the true label of a data point can be accessed immediately after the data point is classified. In reality, a time delay Tl is involved in obtaining the true label of a data point since manual labeling is time consuming. We show how to make fast and correct classification decisions under these constraints and apply them to real benchmark data. Comparison with state-of-the-art stream classification techniques prove the superiority of our approach.

Anomaly Detection in Network Traffic Based on Statistical Inference and alpha-Stable Modeling
Dependable and Secure Computing, IEEE Transactions on Issue Date: July-Aug. 2011
Abstract
This paper proposes a novel method to detect anomalies in network traffic, based on a nonrestricted α-stable first-order model and statistical hypothesis testing. To this end, we give statistical evidence that the marginal distribution of real traffic is adequately modeled with α-stable functions and classify traffic patterns by means of a Generalized Likelihood Ratio Test (GLRT). The method automatically chooses traffic windows used as a reference, which the traffic window under test is compared with, with no expert intervention needed to that end. We focus on detecting two anomaly types, namely floods and flash-crowds, which have been frequently studied in the literature. Performance of our detection method has been measured through Receiver Operating Characteristic (ROC) curves and results indicate that our method outperforms the closely-related state-of-the-art contribution described in. All experiments use traffic data collected from two routers at our university-a 25,000 students institution-which provide two different levels of traffic aggregation for our tests (traffic at a particular school and the whole university). In addition, the traffic model is tested with publicly available traffic traces. Due to the complexity of α-stable distributions, care has been taken in designing appropriate numerical algorithms to deal with the model.

ELMO: Energy Aware Local Monitoring in Sensor Networks
Dependable and Secure Computing, IEEE Transactions on Issue Date: July-Aug. 2011

Abstract
Over the past decade, local monitoring has been shown to be a powerful technique for improving security in multihop wireless sensor networks (WSNs). Indeed, local monitoring-based security algorithms are becoming the most popular tool for providing security in WSNs. However, local monitoring as it is currently practiced is costly in terms of energy consumption, a major drawback for energy-constrained systems such as WSNs. In WSN environments, the scarce power resources are typically addressed through sleep-wake scheduling of the nodes. However, sleep-wake scheduling techniques in WSNs are vulnerable even to simple attacks. In this paper, a new technique is proposed that promises to allow operation of WSNs in a manner that is both energy-efficient and secure. The proposed technique combines local monitoring with a novel, more secure form of sleep-wake scheduling. The latter is a new methodology dubbed Elmo (Energy Aware Local MOnitoring in Sensor Networks), which enables sleep-wake management in a secure manner even in the face of adversarial nodes that choose not to awaken nodes responsible for monitoring their traffic. An analytical proof is given showing that security coverage is not weakened under Elmo. Moreover, ns-2 simulation results show that the performance of local monitoring is practically unchanged, while energy savings of 20 to 100 times are achieved, depending on the scenario.

Efficient Fault Detection and Diagnosis in Complex Software Systems with Information-Theoretic Monitoring
Dependable and Secure Computing, IEEE Transactions on

Abstract
Management metrics of complex software systems exhibit stable correlations which can enable fault detection and diagnosis. Current approaches use specific analytic forms, typically linear, for modeling correlations. In practice, more complex nonlinear relationships exist between metrics. Moreover, most intermetric correlations form clusters rather than simple pairwise correlations. These clusters provide additional information and offer the possibility for optimization. In this paper, we address these issues by using Normalized Mutual Information (NMI) as a similarity measure to identify clusters of correlated metrics, without assuming any specific form for the metric relationships. We show how to apply the Wilcoxon Rank-Sum test on the entropy measures to detect errors in the system. We also present three diagnosis algorithms to locate faulty components: RatioScore, based on the Jaccard coefficient, SigScore, which incorporates knowledge of component dependencies, and BayesianScore, which uses Bayesian inference to assign a fault probability to each component. We evaluate our approach in the context of a complex enterprise application, and show that 1) stable, nonlinear correlations exist and can be captured with our approach; 2) we can detect a large fraction of faults with a low false positive rate (we detect up to 18 of the 22 faults we injected); and 3) we improve the diagnosis with our new diagnosis algorithms.

Privacy-Preserving Updates to Anonymous and Confidential Databases
Dependable and Secure Computing, IEEE Transactions on
Issue Date: July-Aug. 2011
Abstract
Suppose Alice owns a k-anonymous database and needs to determine whether her database, when inserted with a tuple owned by Bob, is still k-anonymous. Also, suppose that access to the database is strictly controlled, because for example data are used for certain experiments that need to be maintained confidential. Clearly, allowing Alice to directly read the contents of the tuple breaks the privacy of Bob (e.g., a patient's medical record); on the other hand, the confidentiality of the database managed by Alice is violated once Bob has access to the contents of the database. Thus, the problem is to check whether the database inserted with the tuple is still k-anonymous, without letting Alice and Bob know the contents of the tuple and the database, respectively. In this paper, we propose two protocols solving this problem on suppression-based and generalization-based k-anonymous and confidential databases. The protocols rely on well-known cryptographic assumptions, and we provide theoretical analyses to proof their soundness and experimental results to illustrate their efficiency.

Dynamics of Malware Spread in Decentralized Peer-to-Peer Networks
Dependable and Secure Computing, IEEE Transactions on Issue Date: July-Aug. 2011
Abstract
In this paper, we formulate an analytical model to characterize the spread of malware in decentralized, Gnutella type peer-to-peer (P2P) networks and study the dynamics associated with the spread of malware. Using a compartmental model, we derive the system parameters or network conditions under which the P2P network may reach a malware free equilibrium. The model also evaluates the effect of control strategies like node quarantine on stifling the spread of malware. The model is then extended to consider the impact of P2P networks on the malware spread in networks of smart cell phones.

Low-Energy Symmetric Key Distribution in Wireless Sensor Networks
Dependable and Secure Computing, IEEE Transactions on Issue Date: May-June 2011

Abstract
In this work, a scheme for key distribution and network access in a Wireless Sensor Network (WSN) that utilizes Identity-Based Cryptography (IBC) is presented. The scheme is analyzed on the ARM920T processor and measurements were taken for the runtime and energy of its components. It was found that the Tate pairing component of the scheme consumes significant amounts of energy, and so should be ported to hardware. An accelerator was implemented in 65 nm Complementary Metal Oxide Silicon (CMOS) technology and area, timing, and energy figures have been obtained for the design. Results indicate that a hardware implementation of IBC would meet the strict energy constraint required of a wireless sensor network node.

Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables
Dependable and Secure Computing, IEEE Transactions on Issue Date: May-June 2011

Abstract
Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We address both of these problems through replica placement. We characterize tree-based routing DHTs and define MaxDisjoint, a replica placement that creates route diversity for these DHTs. We prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a tree-based routing DHT), we evaluate the impact of MaxDisjoint on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run. Furthermore, we consider another route diversity mechanism that we call neighbor set routing and show that, when used with our replica placement, it can successfully route messages to a correct replica even with a quarter of the nodes in the system compromised at random. Finally, we demonstrate a family of replica query strategies that can trade off response time and system load. We present a hybrid query strategy that keeps response time low without producing too high a load.

Robust Correlation of Encrypted Attack Traffic through Stepping Stones by Flow Watermarking
Dependable and Secure Computing, IEEE Transactions on Issue Date: May-June 2011

Abstract
Network-based intruders seldom attack their victims directly from their own computer. Often, they stage their attacks through intermediate “stepping stones” in order to conceal their identity and origin. To identify the source of the attack behind the stepping stone(s), it is necessary to correlate the incoming and outgoing flows or connections of a stepping stone. To resist attempts at correlation, the attacker may encrypt or otherwise manipulate the connection traffic. Timing-based correlation approaches have been shown to be quite effective in correlating encrypted connections. However, timing-based correlation approaches are subject to timing perturbations that may be deliberately introduced by the attacker at stepping stones. In this paper, we propose a novel watermark-based-correlation scheme that is designed specifically to be robust against timing perturbations. Unlike most previous timing-based correlation approaches, our watermark-based approach is “active” in that it embeds a unique watermark into the encrypted flows by slightly adjusting the timing of selected packets. The unique watermark that is embedded in the encrypted flow gives us a number of advantages over passive timing-based correlation in resisting timing perturbations by the attacker. In contrast to the existing passive correlation approaches, our active watermark-based correlation does not make any limiting assumptions about the distribution or random process of the original interpacket timing of the packet flow. In theory, our watermark-based correlation can achieve arbitrarily close to 100 percent correlation true positive rate (TPR), and arbitrarily close to 0 percent false positive rate (FPR) at the same time for sufficiently long flows, despite arbitrarily large (but bounded) timing perturbations of any distribution by the attacker.
Our paper is the first that identifies 1) accurate quantitative tradeoffs between the achievable correlation effectiveness a- - nd the defining characteristics of the timing perturbation; and 2) a provable upper bound on the number of packets needed to achieve a desired correlation effectiveness, given the amount of timing perturbation. Experimental results show that our active watermark-based correlation performs better and requires fewer packets than existing, passive timing-based correlation methods in the presence of random timing perturbations.

Low-Overhead End-to-End Performance Measurement for Next Generation Networks
Network and Service Management, IEEE Transactions on
Issue Date: March 2011

Abstract
Internet performance measurement is commonly perceived as a high-cost control-plane activity and until now it has tended to be implemented on top of the network's forwarding operation. Consequently, measurement mechanisms have often had to trade relevance and accuracy over non-intrusiveness and cost effectiveness. In this paper, we present the software implementation of an in-line measurement mechanism that uses native structures of the Internet Protocol version 6 (IPv6) stack to piggyback measurement information on data-carrying traffic as this is routed between two points in the network. We carefully examine the overhead associated with both the measurement process and the measurement data, and we demonstrate that direct two-point measurement has minimal impact on throughput and on system processing load. The results of this paper show that adequately engineered measurement mechanisms that exploit selective processing do not compromise the network's forwarding efficiency, and can be deployed in an always-on manner to reveal the true performance of network traffic over small timescales.

On the Impact of Security Protocols on the Performance of SNMP
Network and Service Management, IEEE Transactions on Issue Date: March 2011

Abstract
Since the early 1990s, there have been several attempts to secure the Simple Network Management Protocol (SNMP). The third version of the protocol, published as full standard in 2002, introduced the User-based Security Model (USM), which comes with its own user and key-management infrastructure. Since then, network operators have reported that deploying another user and key management infrastructure to secure SNMP is expensive and a reason to not deploy SNMPv3. This paper describes how existing security protocols operating above the transport layer and below application protocols can be used to secure SNMP. These protocols can take advantage of already deployed key management infrastructures that are used for other network management interfaces and hence their use can reduce the operational costs associated with securing SNMP. Our main contribution is a detailed performance analysis of a prototype implementation, comparing the performance of SNMPv3 over SSH, TLS, and DTLS with other versions of SNMP. We also discuss the differences between the various options to secure SNMP and provide guidelines for choosing solutions to implement or deploy.

Locating Equivalent Servants over P2P Networks
Network and Service Management, IEEE Transactions on Issue Date: March 2011

Abstract
While peer-to-peer networks are mainly used to locate unique resources across the Internet, new interesting deployment scenarios are emerging. Particularly, some applications (e.g., VoIP) are proposing the creation of overlays for the localization of services based on equivalent servants (e.g., voice relays). This paper explores the possible overlay architectures that can be adopted to provide such services, showing how an unstructured solution based on a scale-free overlay topology is an effective option to deploy in this context. Consequently, we propose EQUATOR (EQUivalent servAnt locaTOR), an unstructured overlay implementing the above mentioned operating principles, based on an overlay construction algorithm that well approximates an ideal scale-free construction model. We present both analytical and simulation results which support our overlay topology selection and validate the proposed architecture.

Cooperative Channelization in Wireless Networks with Network Coding
Parallel and Distributed Systems, IEEE Transactions on Issue Date: July 2011
Abstract
In this paper, we address congestion of multicast traffic in multihop wireless networks through a combination of network coding and resource reservation. Network coding reduces the number of transmissions required in multicast flows, thus allowing a network to approach its multicast capacity. In addition, it efficiently repairs errors in multicast flows by combining packets lost at different destinations. However, under conditions of extremely high congestion the repair capability of network coding is seriously degraded. In this paper, we propose cooperative channelization, in which portions of the transmission media are allocated to links that are congested at the point where network coding cannot efficiently repair loss. A health metric is proposed to allow comparison of need for channelization of different multicast links. Cooperative channelization considers the impact of channelization on overall network performance before resource reservation is triggered. Our results show that cooperative channelization improves overall network performance while being well suited for wireless networks using network coding.

Throughput Optimization in Multihop Wireless Networks with Multipacket Reception and Directional Antennas
Parallel and Distributed Systems, IEEE Transactions on Issue Date: July 2011

Abstract
Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. We address the throughput optimization problem in wireless networks that support multipacket reception (MPR) capability. The problem is modeled as a joint routing and scheduling problem, which is known to be NP-hard. The scheduling subproblem deals with finding the optimal schedulable sets, which are defined as subsets of links that can be scheduled or activated simultaneously. We demonstrate that any solution of the scheduling subproblem can be built with |E| + 1 or fewer schedulable sets, where |E| is the number of links of the network. This result is in contrast with previous works that stated that a solution of the scheduling subproblem is composed of an exponential number of schedulable sets. Due to the hardness of the problem, we propose a polynomial time scheme based on a combination of linear programming and approximation algorithm paradigms. We illustrate the use of the scheme to study the impact of design parameters on the performance of MPR-capable networks, including the number of transmit interfaces, the beamwidth, and the receiver range of the antennas.

Attribute-Based Access Control with Efficient Revocation in Data Outsourcing Systems
Parallel and Distributed Systems, IEEE Transactions on
Abstract
Some of the most challenging issues in data outsourcing scenario are the enforcement of authorization policies and the support of policy updates. Ciphertext-policy attribute-based encryption is a promising cryptographic solution to these issues for enforcing access control policies defined by a data owner on outsourced data. However, the problem of applying the attribute-based encryption in an outsourced architecture introduces several challenges with regard to the attribute and user revocation. In this paper, we propose an access control mechanism using ciphertext-policy attribute-based encryption to enforce access control policies with efficient attribute and user revocation capability. The fine-grained access control can be achieved by dual encryption mechanism which takes advantage of the attribute-based encryption and selective group key distribution in each attribute group. We demonstrate how to apply the proposed mechanism to securely manage the outsourced data. The analysis results indicate that the proposed scheme is efficient and secure in the data outsourcing systems.

Network Immunization with Distributed Autonomy-Oriented Entities
Parallel and Distributed Systems, IEEE Transactions on Issue Date: July 2011

Abstract
Many communication systems, e.g., internet, can be modeled as complex networks. For such networks, immunization strategies are necessary for preventing malicious attacks or viruses being percolated from a node to its neighboring nodes following their connectivities. In recent years, various immunization strategies have been proposed and demonstrated, most of which rest on the assumptions that the strategies can be executed in a centralized manner and/or that the complex network at hand is reasonably stable (its topology will not change overtime). In other words, it would be difficult to apply them in a decentralized network environment, as often found in the real world. In this paper, we propose a decentralized and scalable immunization strategy based on a self-organized computing approach called autonomy-oriented computing (AOC) [1], [2]. In this strategy, autonomous behavior-based entities are deployed in a decentralized network, and are capable of collectively finding those nodes with high degrees of conductivities (i.e., those that can readily spread viruses). Through experiments involving both synthetic and real-world networks, we demonstrate that this strategy can effectively and efficiently locate highly-connected nodes in decentralized complex network environments of various topologies, and it is also scalable in handling large-scale decentralized networks. We have compared our strategy with some of the well-known strategies, including acquaintance and covering strategies on both synthetic and real-world networks.

Optimization of Rate Allocation with Distortion Guarantee in Sensor Networks
Parallel and Distributed Systems, IEEE Transactions on
Issue Date: July 2011

Abstract

Lossy compression techniques are commonly used by long-term data-gathering applications that attempt to identify trends or other interesting patterns in an entire system since a data packet need not always be completely and immediately transmitted to the sink. In these applications, a nonterminal sensor node jointly encodes its own sensed data and the data received from its nearby nodes. The tendency for these nodes to have a high spatial correlation means that these data packets can be efficiently compressed together using a rate-distortion strategy. This paper addresses the optimal rate-distortion allocation problem, which determines an optimal bit rate of each sensor based on the target overall distortion to minimize the network transmission cost. We propose an analytically optimal rate-distortion allocation scheme, and we also extend it to a distributed version. Based on the presented allocation schemes, a greedy heuristic algorithm is proposed to build the most efficient data transmission structure to further reduce the transmission cost. The proposed methods were evaluated using simulations with real-world data sets. The simulation results indicate that the optimal allocation strategy can reduce the transmission cost to 6~15% of that for the uniform allocation scheme.

A Data Throughput Prediction and Optimization Service for Widely Distributed Many-Task Computing
Parallel and Distributed Systems, IEEE Transactions on Issue Date: June 2011
Abstract
In this paper, we present the design and implementation of an application-layer data throughput prediction and optimization service for many-task computing in widely distributed environments. This service uses multiple parallel TCP streams to improve the end-to-end throughput of data transfers. A novel mathematical model is developed to determine the number of parallel streams, required to achieve the best network performance. This model can predict the optimal number of parallel streams with as few as three prediction points. We implement this new service in the Stork Data Scheduler, where the prediction points can be obtained using Iperf and GridFTP samplings. Our results show that the prediction cost plus the optimized transfer time is much less than the nonoptimized transfer time in most cases. As a result, Stork data transfer jobs with optimization service can be completed much earlier, compared to nonoptimized data transfer jobs.

Toward Efficient and Simplified Distributed Data Intensive Computing
Parallel and Distributed Systems, IEEE Transactions on Issue Date: June 2011

Abstract
While the capability of computing systems has been increasing at Moore's Law, the amount of digital data has been increasing even faster. There is a growing need for systems that can manage and analyze very large data sets, preferably on shared-nothing commodity systems due to their low expense. In this paper, we describe the design and implementation of a distributed file system called Sector and an associated programming framework called Sphere that processes the data managed by Sector in parallel. Sphere is designed so that the processing of data can be done in place over the data whenever possible. Sometimes, this is called data locality. We describe the directives Sphere supports to improve data locality. In our experimental studies, the Sector/Sphere system has consistently performed about 2-4 times faster than Hadoop, the most popular system for processing very large data sets.

Nonlocal PDEs-Based Morphology on Weighted Graphs for Image and Data Processing
Image Processing, IEEE Transactions on Issue Date: June 2011

Abstract
Mathematical morphology (MM) offers a wide range of operators to address various image processing problems. These operators can be defined in terms of algebraic (discrete) sets or as partial differential equations (PDEs). In this paper, we introduce a nonlocal PDEs-based morphological framework defined on weighted graphs. We present and analyze a set of operators that leads to a family of discretized morphological PDEs on weighted graphs. Our formulation introduces nonlocal patch-based configurations for image processing and extends PDEs-based approach to the processing of arbitrary data such as nonuniform high dimensional data. Finally, we show the potentialities of our methodology in order to process, segment and classify images and arbitrary data.

Image Segmentation Using Fuzzy Region Competition and Spatial/Frequency Information
This paper appears in: Image Processing, IEEE Transactions on Issue Date: June 2011
Abstract
This paper presents a multiphase fuzzy region competition model that takes into account spatial and frequency information for image segmentation. In the proposed energy functional, each region is represented by a fuzzy membership function and a data fidelity term that measures the conformity of spatial and frequency data within each region to (generalized) Gaussian densities whose parameters are determined jointly with the segmentation process. Compared with the classical region competition model, our approach gives soft segmentation results via the fuzzy membership functions, and moreover, the use of frequency data provides additional region information that can improve the overall segmentation result. To efficiently solve the minimization of the energy functional, we adopt an alternate minimization procedure and make use of Chambolle's fast duality projection algorithm. We apply the proposed method to synthetic and natural textures as well as real-world natural images. Experimental results show that our proposed method has very promising segmentation performance compared with the current state-of-the-art approaches.

Perceptual Segmentation: Combining Image Segmentation With Object Tagging
Image Processing, IEEE Transactions on Issue Date: June 2011

Abstract
Human observers understand the content of an image intuitively. Based upon image content, they perform many image-related tasks, such as creating slide shows and photo albums, and organizing their image archives. For example, to select photos for an album, people assess image quality based upon the main objects in the image. They modify colors in an image based upon the color of important objects, such as sky, grass or skin. Serious photographers might modify each object separately. Photo applications, in contrast, use low-level descriptors to guide similar tasks. Typical descriptors, such as color histograms, noise level, JPEG artifacts and overall sharpness, can guide an imaging application and safeguard against blunders. However, there is a gap between the outcome of such operations and the same task performed by a person. We believe that the gap can be bridged by automatically understanding the content of the image. This paper presents algorithms for automatic tagging of perceptual objects in images, including sky, skin, and foliage, which constitutes an important step toward this goal.

ViBe: A Universal Background Subtraction Algorithm for Video Sequences

Image Processing, IEEE Transactions on Issue Date : June 2011

Abstract
This paper presents a technique for motion detection that incorporates several innovative mechanisms. For example, our proposed technique stores, for each pixel, a set of values taken in the past at the same location or in the neighborhood. It then compares this set to the current pixel value in order to determine whether that pixel belongs to the background, and adapts the model by choosing randomly which values to substitute from the background model. This approach differs from those based upon the classical belief that the oldest values should be replaced first. Finally, when the pixel is found to be part of the background, its value is propagated into the background model of a neighboring pixel. We describe our method in full details (including pseudo-code and the parameter values used) and compare it to other background subtraction techniques. Efficiency figures show that our method outperforms recent and proven state-of-the-art methods in terms of both computation speed and detection rate. We also analyze the performance of a downscaled version of our algorithm to the absolute minimum of one comparison and one byte of memory per pixel. It appears that even such a simplified version of our algorithm performs better than mainstream techniques.

Contextual Kernel and Spectral Methods for Learning the Semantics of Images
Image Processing, IEEE Transactions on Issue Date: June 2011

Abstract
This paper presents contextual kernel and spectral methods for learning the semantics of images that allow us to automatically annotate an image with keywords. First, to exploit the context of visual words within images for automatic image annotation, we define a novel spatial string kernel to quantify the similarity between images. Specifically, we represent each image as a 2-D sequence of visual words and measure the similarity between two 2-D sequences using the shared occurrences of s -length 1-D subsequences by decomposing each 2-D sequence into two orthogonal 1-D sequences. Based on our proposed spatial string kernel, we further formulate automatic image annotation as a contextual keyword propagation problem, which can be solved very efficiently by linear programming. Unlike the traditional relevance models that treat each keyword independently, the proposed contextual kernel method for keyword propagation takes into account the semantic context of annotation keywords and propagates multiple keywords simultaneously. Significantly, this type of semantic context can also be incorporated into spectral embedding for refining the annotations of images predicted by keyword propagation. Experiments on three standard image datasets demonstrate that our contextual kernel and spectral methods can achieve significantly better results than the state of the art.

Distributed Multiple Description Video Coding on Packet Loss Channels
Image Processing, IEEE Transactions on Issue Date: June 2011

Abstract
In this paper, we are to solve the drift problem of multiple description video coding on packet loss channels by using state-of-the-art distributed techniques. We first present an asymptotically optimal code design of multiple descriptions in the Wyner-Ziv (MDWZ) setting. Then we propose a distributed multiple description video coding (DMDVC) scheme, which performs MDWZ coding on each nonintra coded frame. Instead of the prediction loops used in traditional multiple description video coding, Slepian-Wolf based coding is used to exploit interframe correlations. A bitplane extraction scheme is proposed to improve the balance between two descriptions, so that side informations can be interchanged between the side decoders of DMDVC with negligible quality degradation, which is crucial to robust transmission over packet loss channels. Experiment results demonstrate the robustness of our scheme, especially at high packet loss rates.

Size-Controllable Region-of-Interest in Scalable Image Representation
Image Processing, IEEE Transactions on Issue Date: May 2011

Abstract
Differentiating region-of-interest (ROI) from non-ROI in an image in terms of relative size as well as fidelity becomes an important functionality for future visual communication environment with a variety of display devices. In this paper, we propose a scalable image representation with the ROI functionality in the spatial domain, which allows us to generate a hierarchy of images with arbitrary sizes. The ROI functionality of our scalable representation is a result of a nonuniform grid transformation in the spatial domain, where only the center of ROI and an expansion parameter are to be known. Our grid transformation guarantees no loss of information within the area of ROI.

Graph Regularized Sparse Coding for Image Representation
Image Processing, IEEE Transactions on Issue Date: May 2011

Abstract
Sparse coding has received an increasing amount of interest in recent years. It is an unsupervised learning algorithm, which finds a basis set capturing high-level semantics in the data and learns sparse coordinates in terms of the basis set. Originally applied to modeling the human visual cortex, sparse coding has been shown useful for many applications. However, most of the existing approaches to sparse coding fail to consider the geometrical structure of the data space. In many real applications, the data is more likely to reside on a low-dimensional submanifold embedded in the high-dimensional ambient space. It has been shown that the geometrical information of the data is important for discrimination. In this paper, we propose a graph based algorithm, called graph regularized sparse coding, to learn the sparse representations that explicitly take into account the local manifold structure of the data. By using graph Laplacian as a smooth operator, the obtained sparse representations vary smoothly along the geodesics of the data manifold. The extensive experimental results on image classification and clustering have demonstrated the effectiveness of our proposed algorithm.

Dynamic Conflict-Free Transmission Scheduling for Sensor Network Queries
Mobile Computing, IEEE Transactions on Issue Date : May 2011
Abstract
With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose workloads, DCQS is specifically designed for query services in wireless sensor networks. DCQS has several unique features. First, it optimizes the query performance through conflict-free transmission scheduling based on the temporal properties of queries in wireless sensor networks. Second, it can adapt to workload changes without explicitly reconstructing the transmission schedule. Furthermore, DCQS also provides predictable performance in terms of the maximum achievable query rate. We provide an analytical capacity bound for DCQS that enables DCQS to handle overload through rate control. NS2 simulations demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and 802.11b in terms of query latency and throughput.

Cooperating with Smartness: Using Heterogeneous Smart Antennas in Multi-hop Wireless Networks
Mobile Computing, IEEE Transactions on Date of Publication : 10 February 2011
The use of smart antennas in multi-hop wireless networks (MWNs) has garnered significant attention over the last few years. While homogeneous MWNs with all nodes having the same antenna capabilities will have certain applications, we argue that MWNs with nodes having heterogeneous antenna capabilities are more likely to be the norm due to a variety of motivating factors. In the context of such heterogeneous smart antenna networks (HSANs), we investigate and motivate the need for a simple form of node cooperation called retransmit diversity. We show that while such a simple form of node cooperation cannot bring significant benefits to homogeneous omni-directional antenna networks, they can bring great gains to heterogeneous smart antenna networks. We then present several key properties pertaining to node cooperation in HSANs along with analytical reasoning. In the process, we identify a fundamental trade-off between exploiting smart antenna gain and cooperation gain, that undermines the ability of HSANs to leverage node cooperation to their maximum potential. To address this tradeoff, we then present an adaptive cooperation mechanism and incorporate this mechanism through the design of a simple but efficient MAC protocol. The performance of the MAC protocol is evaluated through ns2 simulations along with a realistic physical layer channel model for smart antenna environments.

CACAO: Distributed Client-Assisted Channel Assignment Optimization for Uncoordinated WLANs
Parallel and Distributed Systems, IEEE Transactions on Date of Publication : 10 February 2011
Abstract

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

Schedulability Analysis for Hard Network Lifetime Wireless Sensor Networks With High Energy First Clustering
Reliability, IEEE Transactions on, Date of Publication : 21 April 2011

Abstract
Network lifetime predictability is an essential system requirement for the type of wireless sensor network (WSN) used in safety-critical and highly-reliable applications. All sensor nodes in these time-critical WSNs should meet the lifetime constraint at any time instance, else it may cause severe consequences that involve economic losses, or even fatalities. In the literature, clustering sensors into groups is a popular strategy to maximize the network lifetime, but none of the clustering algorithms address the predictability issue for time-critical WSNs. In this paper, the High Energy First (HEF) clustering algorithm is chosen as a design reference model, which is proved in this paper to be an optimal clustering policy under certain ideal conditions. To address network lifetime predictability in practice, the network lifetime bounds and feasibility test for the HEF are developed via the worst case energy consumption analysis. The network simulator 2 (NS2) is used to verify the proposed network lifetime predictability model, and the results show that the derived bounds of the predictability provide accurate estimations of the system lifetime.