Network traffic classification is crucial for cybersecurity, as it helps detect abnormal traffic and potential attack patterns, enabling timely protective measures. With the widespread adoption of remote work, video conferencing, and VPN services, the rapid growth of network traffic has increased the complexity of traffic classification. Traditional methods, such as port-based classification, Deep Packet Inspection, and Machine Learning (ML), face limitations in handling complex and encrypted traffic. In this study, we propose a novel network traffic classification system that combines 1D-CNN and Transformer, utilizing different activation functions to extract both local and long-range features. These complementary features are fused together to improve classification capability. The experimental results on the ISCX VPN-nonVPN dataset indicate that our proposed system outperforms baseline methods in most categories with respect to Precision, Recall, and F1-score.

Gesture recognition is a key component in developing intuitive and efficient human-computer interaction systems, enabling machines to interpret human intentions through body movement analysis. A common approach employs the Dynamic Time Warping (DTW) algorithm to compute similarity between keypoint sequences extracted via pose estimation from both reference and live video streams. While effective and flexible, DTW has limitations, including high space complexity and sensitivity to keypoint misidentification often seen in pose estimation. To address these issues, we propose two enhancements to the DTWbased gesture recognition pipeline. First, we apply a space compression technique to reduce memory usage without sacrificing performance. Second, we introduce a frame-skip mechanism to mitigate the impact of incorrectly detected keypoints on recognition results. To evaluate our method, we construct a dataset of traffic gestures commonly used in Taiwan. Experimental results show that the proposed enhancements improve the efficiency, scalability, and accuracy of gesture recognition, making the approach more suitable for real-time use in constrained environments.

In the current era of micro-services, containerized applications face unprecedented security challenges due to shared kernels and limited isolation. This research proposes a container security framework based on monitoring system call sequences to detect anomalies in micro-service containers. We introduce a custom dataset named XXXX, which capture container captures system call sequences behavior in micro-services containers and simulated attacks. The framework includes real-time system call monitors, parsers, dashboards, and an unsupervised anomaly detection model using unsupervised learning with autoencoders to enhance the detection capability of unknown vulnerabilities. It leverages containerization benefits-simplicity, scalability, and automation. Our evaluation emphasizes false alarm rate and average detection time. Results show that the attack detection performance of most containers meets expectations, though the detection time of one subset had slightly longer detection time due to the intrinsic complexity of vulnerabilities. This work offers valuable insights for improving container security in microservice systems.

Privacy-preserving k-nearest neighbor (PPkNN) classification for multiple clouds enables categorizing queried data into a class in keeping with data privacy, where the database and key servers jointly perform cryptographic operations. The existing solutions, unfortunately, take a long time and incur a large amount of traffic between the database and key servers. Therefore, in this paper, we propose a fast and secure kNN classification protocol, namely FSkNN, over distributed databases deployed in multiple clouds under the semi-honest model. Particularly, we focus on optimizing the network-related operations during kNN classification. That is, the proposed cryptographic protocol reduces the number of interactions between the servers by using a fully homomorphic encryption scheme and eliminates unnecessary traffic by applying mathematical techniques. In addition, the indistinguishability-based security of FSkNN is proven. We implemented FSkNN with C++ and the testbed experiments demonstrate that the proposed scheme significantly facilitates the query response time and reduces the communication cost.

Urbanization, characterized by the continuous growth of population and density in urban areas, has led to the expansion and increased complexity of transportation networks, exacerbating traffic congestion. Accurate traffic speed prediction is crucial for effective traffic network management and planning. As the complexity of real-world road networks increases, integrating spatial and temporal information for accurate traffic speed prediction has become a challenging research task. This paper proposes a novel approach by introducing a spatial-temporal graph neural network (STGNN)-based model to enhance the accuracy of traffic speed prediction. By employing an attention-based STGNN, we effectively capture the complex relationships among road segments in real-world scenarios. We utilize the Huber loss as the training objective to improve prediction accuracy. Furthermore, we present an architecture that incorporates Root Mean Square Layer Normalization into the Transformer and integrates the Spatial-Temporal Attention Wavenet (STAWnet) into the model backbone, enabling faster training while maintaining model stability. We evaluate the proposed model using five real-world traffic speed benchmark datasets. The experimental results demonstrate that our method achieves superior performance compared to state-of-the-art traffic speed prediction approaches.

In the dynamic and evolving field of computer vision, action recognition has become a key focus, especially with the advent of sophisticated methodologies like Convolutional Neural Networks (CNNs), Convolutional 3D, Transformer and spatial-temporal feature fusion. These technologies have shown promising results on well-established benchmarks but face unique challenges in real-world applications, particularly in sports analysis, where the precise decomposition of activities and the distinction of subtly different actions are crucial. Existing datasets like UCF101, HMDB51, and Kinetics have offered a diverse range of video data for various scenarios. However, there’s an increasing need for fine-grained video datasets that capture detailed categorizations and nuances within broader action categories. In this paper, we introduce the VideoBadminton dataset, which is derived from high-quality badminton footage. Through an exhaustive evaluation of leading methodologies on this dataset, this study aims to advance the field of action recognition, particularly in badminton sports. The introduction of VideoBadminton could not only serve for badminton action recognition but also provide a dataset for recognizing fine-grained actions. The insights gained from these evaluations are expected to catalyze further research in action comprehension, especially within sports contexts.

Multi-armed bandits (MABs) are widely used for decision making processes, in which an agent tries to maximize a long-term reward by balancing exploiting and exploring actions. In this paper, we are particularly interested in federated MABs for mobile social networks (MSNs), where a collection of agents learn action values by locally observing rewards and exchanging estimated action values with other agents. Our research differs from the existing federated MABs in the underlying network setting, such that agents can communicate with each other only at opportunistic contact events. To this end, we first design the weighted-connectivity (WC) centrality to quantify the importance of agents in an MSN, and then, we propose the weighted-connectivity upper confidence bound (WC-UCB) algorithm for the MSN contexts. The key idea to reduce biases at each agent and to utilize limited opportunities of federated updates is to prioritize the estimates of action-value functions computed by the agents with a high WC centrality. In addition, the performance bound in terms of the cumulative regret is analyzed. The performance of the proposed algorithm is evaluated by simulations using real mobility traces and the results demonstrate that our WC-UCB outperforms the state-of-the-art algorithms in terms of the average reward and the cumulative regret.

In recent years, there has been a growing interest among researchers and scholars in the analysis of sports activities, driven by the advancements of machine learning and the increased availability of public data. However, there remains a scarcity of comprehensive sports video datasets that possess the necessary attributes to address various research tasks effectively. We present the “Badminton Benchmark” (BMT-BENCH) to facilitate reproducible machine learning research in the sports domain. This dataset comprises high-quality, high-speed video clips collected from official badminton tournaments involving two team players. The dataset is labeled and unlabeled, catering to different research problems such as video generation and real-time object detection. we feature a baseline system mainly for video generation tasks and provide a thorough evaluation of the challenges posed by the dataset’s unique nature. The dataset is publicly accessible at https://drive.google.com/drive/folders/1moYDb8tp5K-VDxPJU3sTorfY E7NnwVpf?usp=sharing and the baseline system is available at https://github.com/ziangshi/BMT_BENCH_baseline_repo.

Cyber Threat Intelligence (CTI) significantly enhances organizational cybersecurity defenses by providing actionable insights from diverse data sources. This research studies the correlation between CTI analysis and the MITRE ATT&CK framework, focusing on their alignment to strengthen threat detection and response capabilities. A pivotal aspect of this study involves developing a classifier using a fine-tuned BERT-based model to map CTI reports to specific ATT&CK techniques. Our model demonstrated substantial improvements over the baseline SecBERT, achieving a 2.6% higher F1-score and a 4.2% improvement in Top-3 Accuracy. By integrating CTI with the MITRE ATT&CK framework, researchers can shift from reactive to proactive cybersecurity strategies. This integration enables swift detection of emerging threats, enhances incident response effectiveness, and fortifies defensive measures against evolving cyber threats. Ultimately, the synergy between CTI and ATT&CK fosters a comprehensive approach to cybersecurity management in today’s dynamic threat landscape.

The topic of study, Intelligent Transportation System (ITS), focuses on using vehicle-to-environment communication to address severe traffic problems, such as safety and congestion difficulties. Pedestrians remain the most Vulnerable Road Users (VRUs). Moreover, pedestrian movements are more challenging to predict because humans can quickly change their direction and status (e.g., walking or stopping). In this research, we build a system called PedCross, which uses human image semantic information to predict the behavior of pedestrians (i.e., crossing or not crossing). In PedCross, images of pedestrians are first used to detect skeletons. The features in the detected skeletons are then extracted for model training. Two types of models, Random Forest and LSTM, are considered for pedestrian crossing prediction. To further improve the efficiency and accuracy of PedCross, Skip Frame, Head Orientation, and Warning/Dangerous Zones are integrated. PedCross is tested with the collected ITRI dataset and deployed on the auto-driving bus for a road test. The road test indicates that PedCross achieves all the requirements set forth by ITRI and outperforms Free Space, a baseline system developed by ITRI.

We consider a potential communication problem in national security, where wireless spy sensors with eavesdropping capability are strategically deployed around an area of interest. For counterintelligence, achieving secure communication by penetrating such a spy barrier is of great importance. In this paper, we first formulate the problem of barrier penetration routing against spy barriers consisting of strategically deployed wireless sensors. We point out that existing multi-path avoidance routing protocols cannot efficiently counteract collusion attacks, where connected adversaries collaborate with each other to compromise data packets. We propose a barrier penetration routing (BPR) protocol to securely penetrate the barrier of adversaries. In the protocol, a set of physically distanced paths are identified based on distance vectors as well as network-wide flooding. Then, each data packet encoded by XOR coding is routed via a different path. Unlike existing avoidance routing, the proposed scheme does not rely on the assumption that the adversary's locations are known. The simulation results demonstrate that the proposed BPR outperforms the baseline protocol as well as existing routing protocols in terms of secure delivery rate.

Opportunistic network-based mobile crowdsourcing (MCS) outsources location-based human tasks to a crowd of workers, where workers with mobile devices opportunistically have contact with the server. While a number of task assignment algorithms have been proposed for different objectives, real-timeness is not considered. In this article, we are interested in real-time MCS (RT-MCS), in which tasks can be generated at any time step, and task assignment is performed in real-time. We first model an abstract RT-MCS and then instantiate the real-time task assignment problem for opportunistic network-based RT-MCS. A generic real-time task assignment (RTA) algorithm is designed based on the principle of the greedy approach, where each task is assigned to the best worker with the highest expected completion probability. To understand the fundamental performance issues, we formulate closed-form solutions for task completion probability as well as delay. In addition, we identify the critical condition that illuminates the busy state and the not-busy state of an RT-MCS. Furthermore, the analytical and simulation results demonstrate that our analysis yields close approximation of simulation results.

With the growing consumption of online visual contents, there is an urgent need for video translation in order to reach a wider audience from around the world. However, the materials after direct translation and dubbing are unable to create a natural audio-visual experience since the translated speech and lip movement are often out of sync. To improve the viewing experience, an accurate automatic lip-movement synchronization generation system is necessary. To improve the accuracy and visual quality of speech to lip generation, this research proposes two techniques: Embedding Attention Mechanisms in Convolution Layers and Deploying SSIM as Loss Function in Visual Quality Discriminator. The proposed system as well as several other ones are tested on three audiovisual datasets. The results show that our proposed methods achieve superior performance over the state-of-the-art speech to lip synthesis on not only the accuracy but also the visual quality of audio-lip synchronization generation.

Protecting the privacy of users is one of the most important issues in recommender systems, where new items, e.g., books, movies, and friends in online social networking service/sites, are recommended to target users. To identify recommended items, encryption-based privacy-preserving collaborative filtering is widely used to generate recommendations. However, existing solutions are either slow or not scalable. To tackle this issue, in this paper, we first propose a privacy-preserving user-based CF protocol using the BGV fully homomorphic encryption scheme, which is named BGV-CF. By reducing interactions and the amount of communication traffic among users and recommendation servers, the proposed BGV-CF protocol significantly facilitates the recommendation process. Then, we propose an optimized BGV-CF (OBGV-CF) protocol where some computations are offloaded to users during the recommendation process. The security of the proposed schemes is qualitatively analyzed and quantitative analyses of the computation and communication costs are performed. In addition, provable security analysis using random oracles is provided. The BGV-CF and OBGV-CF protocols are implemented using C++, and testbeds using the MovieLens dataset are conducted. Experimental results demonstrate that the proposed BGV-CF and OBGV-CF successfully achieve their design goals.

AI cameras are edge devices that can execute lightweight deep learning models with embedded GPU devices. In traffic management applications, traffic flow and traffic incidents can be detected from roadside images by AI cameras, and only the detected high-level information needs to be sent back to the server to avoid network bandwidth consumption and spare server resources. However, due to limited hardware resources at edge devices, the models should be optimized for specific AI cameras before they are deployed. In addition, the environment-related parameters need to be configured properly after model deployment. These tasks call for an AI camera management system. In this research, we design a management and deployment traffic monitoring system which can accomplish model optimization and parameter configuration with ease. Except for the camera hardware installation, other main functions can be called remotely from the management system, including 1) Automatic modeling and code transfer generation; 2) Remote deep learning model deployment; 3) Remote application configuration; 4) Analysis result presentation with a graphical user interface. To validate our proposed system, the embedded GPU devices, including NVIDIA Jetson TX2 and AGX Xavier combined with roadside cameras, are used as the prototype of the AI cameras, and the deployment of intersection flow analysis models and the visualized analysis results are conducted by the proposed system. The experiments validate that the proposed management system achieves all the design goals.

Graph Neural Networks (GNNs) have shown promising performance in many applications, yet remain extremely difficult to train over large-scale graph datasets. Existing weight pruning techniques can prune out the layer weights; however, they cannot fully address the high computation complexity of GNN inference, caused by large graph size and complicated node connections. In this paper, we propose an Iterative Gradient Rank Pruning (IGRP) algorithm to find graph lottery tickets (GLT) of GNNs where each GLT includes a pruned adjacency matrix and a sub-network. Our IGRP can avoid layer collapse and the winning ticket achieves Maximal critical compression. We evaluate the proposed method on small-scale (Cora and Citeseer), medium-scale (PubMed and Wiki-CS), and large-scale (Ogbn-ArXiv and Ogbn-Products) graph datasets. We demonstrate that both Single-shot and Multi-shot of IGRP outperform the state-of-the-art unified GNN sparsification (UGS) framework on node classification. The source code can be found in https://github.com/poweiharn/IGRP_GNN.

The location-based alert system plays a primary factor on determining who is at risk during an emergency, such as a war zone in Ukraine. While users are willing to reveal their locations in exchange for timely alert in those situations, there is no guarantee that their private information does not fall into the wrong hands. For example, a soldier may be killed if his movement pattern is known by the enemy. One resolution to this issue is to encrypt the location information by trusted authority public key before it is transmitted. This approach provides location privacy and allows decryption only when the recipient’s location satisfies a certain predicate. However, the encryption itself may still be compromised if the location encoding is leaked. In this paper, we propose a Hilbert Curve Encoding which encrypts the user’s message along with her locations for private processing with the trusted authority. We further propose a hybrid HNGM−NEncoding which combines the Hilbert Curve Encoding and Gray Encoding. HNGM−Nhas the proprieties of a Hilbert Curve Encoding in its identifier and a Hamming distance of 1 between neighboring cells in a subgrid. As a consequence, the proposed HNGM−Nis less likely to leak neighboring cell identifier than Gray Encoding under random guessing attacks. Extensive experiment results show that our encoding methods are better than Hierarchical Encoding and comparable to Gray Encoding in terms of user response time, token remaining percentage, and execution time.

In this paper, we propose privacy-preserving user-based CF protocols using the BGV fully homomorphic encryption scheme, named BGV-CF and optimized BGV-CF (OBGV-CF), in order to protect privacy of users in recommender systems. The proposed schemes are implemented by C++, and testbeds using the MovieLens dataset demonstrate that the proposed protocols successfully achieve their design goals.

By predicting the air pollutant concentration, people can take precautions to avoid overexposure to air pollutants. Consequently, accurate$\mathbf{PM}_{2.5}$prediction becomes more important. In this paper, we propose a$\mathbf{PM}_{2.5}$prediction system, which utilizes the dataset from EdiGreen Airbox and Taiwan EPA. Our$\mathbf{PM}_{2.5}$prediction system is composed of four parts: data collection, data preprocessing, prediction model construction, and Line platform. To assess the performance of the model prediction, the daily average error and the hourly average accuracy for the duration of a week are calculated. The experimental results show that LSTM based on K- means has the best performance among all methods. Therefore, LSTM based on K-means is chosen to provide real-time$\mathbf{PM}_{2.5}$prediction through the Linebot.

An RFID system is a contactless automatic identification technology and a solution to many business and personal applications. However, the privacy threats to RFID systems cause significant concerns in real RFID applications. Among the privacy issues in RFID systems, we are particularly interested in designing an RFID authentication protocol that achieves strong indistinguishability-based privacy (ind-privacy) and possesses the zero-knowledge property for active tags. In this article, a zero-knowledge authentication protocol (ZKAP) using quadratic residues is proposed. Then, an indistinguishability-based experiment using random oracles is modeled to prove that the proposed scheme achieves strong ind-privacy against active eavesdroppers. The zero-knowledge property is defined with respect to the tags’ private information against dishonest readers, and that property of our ZKAP is proven by constructing a polynomial time simulator that generates a transcript with the same distribution as that of ZKAP. Finally, the proposed protocol is implemented in a Raspberry Pi and a PC, and the performance is evaluated in terms of authentication time. The experimental results demonstrate that our ZKAP achieves its design goals.

The progress of industrial development naturally leads to the demand for more electrical power. Unfortunately, due to the fear of the safety of nuclear power plants, many countries have relied on thermal power plants, which will cause more air pollutants during the process of coal burning. This phenomenon as well as increased vehicle emissions around us, have constituted the primary factors of serious air pollution. Inhaling too much particulate air pollution may lead to respiratory diseases and even death, especially PM$_{2.5}$. By predicting the air pollutant concentration, people can take precautions to avoid overexposure to air pollutants. Consequently, accurate PM$_{2.5}$prediction becomes more important. In this study, we propose a PM$_{2.5}$prediction system, which utilizes the dataset from EdiGreen Airbox and Taiwan EPA. Autoencoder and Linear interpolation are adopted for solving the missing value problem. Spearman’s correlation coefficient is used to identify the most relevant features for PM$_{2.5}$. Two prediction models (i.e., LSTM and LSTM based on K-means) are implemented which predict PM$_{2.5}$value for each Airbox device. To assess the performance of the model prediction, the daily average error and the hourly average accuracy for the duration of a week are calculated. The experimental results show that LSTM based on K-means has the best performance among all methods. Therefore, LSTM based on K-means is chosen to provide real-time PM$_{2.5}$prediction through the Linebot.

The development of road transportation makes it easier for people to drive their vehicles. Unfortunately, it also causes the increasing number of traffic accidents. Advanced driver assistance systems, which in many ways is based on the future trajectory prediction of the vehicle, are developed to alert the driver for potential dangers. Road conditions, including road geometry and the distance between lead vehicle and host vehicle, are important factors in improving accuracy of future trajectory prediction. The road conditions can be obtained by the camera affixed in the vehicle. In this paper, we propose an image processing system, which includes a curve detection algorithm (CDA) and a distance conversion (DC) algorithm, to obtain these road conditions from the image. First, CDA detects the lane stripes and calculates the vanishing point. The road trend can then be identified according to the location of the vanishing point. DC is used to convert the distance between the lead and host vehicles in the image to the real distance. Through analyses and experiments, it is shown that the proposed system achieves a higher precision than the baseline algorithms.

Mobile users and wireless devices are now the sources of a large volume of data. In such data-intensive mobile and wireless computing systems, delay-tolerant network (DTN) routing plays a critical role in data routing, dissemination, and collection. In this paper, we first introduce a new routing problem in DTNs - data-intensive routing - where data transmitted from one node to another is very large with respect to the size of data which can be transmitted in a single contact and available buffer size at relay nodes. In the proposed opportunistic path model, the contact frequency, contact duration, and buffer constraint are all integrated into a single routing metric. Then, we design the data-intensive routing (DIR) protocol where the path with the highest bottleneck link capacity is defined as the path weight. In addition, we propose the advanced DIR (A-DIR) protocol which focuses on the probability that the last message block will be delivered to its destination within the time constraint. Both the DIR and A-DIR protocols forward messages to better relays or to their destinations based on a greedy strategy with the proposed path metric. Simulations using real mobility traces demonstrate that the proposed DIR and A-DIR protocols achieve their design goals.

This paper presents an exact solution and a heuristic solution to a UAV-assisted parcel delivery problem, in which UAVs can only be operated in Visual-Line-Of-Sight (VLOS) areas. In our proposed problem, we assume that trucks travel on road networks, and UAVs move in Euclidean spaces and can launch at any locations on roads. We first demonstrate the overview of our exact solution that iterates all permutations of destinations for an optimal delivery route. Given a specific delivery order, an intuitive approach needs to check all possible locations on roads in the VLOS areas and find a globally optimal location for every destination if UAVs are used for delivery. To avoid high computational cost of searching the optimal location at runtime, we propose an advanced index-based alternative, which computes optimal delivery routes in a pre-processing stage. Due to the nature of NP-hard problems, we also propose a heuristic approach that utilizes delivery groups for the proposed problem of practical size. All proposed solutions are evaluated through extensive experiments.

Designing fast and secure RFID private authentication with structured key management is one of the most essential components for RFID-enabled large-scale object management. Since group keys are shared by some tags in structured key-based authentication, physical tampering of tags, so called the compromise attack, may enable the adversary to obtain group keys stored in the compromised tags, which in turn can be used to distinguish other tags. All existing structured key-based protocols try to reduce the common group key effect to preserve high privacy. However, the theoretical bound of weak privacy achievable by structured key-based authentication remains unknown. In this paper, we investigate weak privacy in RFID authentication. To this end, we first formulate a mathematical model which identifies the probability of two tags being linked with respect to the number of group keys. Our model shows that the existing solutions are far from the ultimate goal in weak privacy. Then, we propose a k-neighbor graph-based RFID authentication (KNGA) protocol, where random walk over a k-neighbor graph is performed. In addition, we show that KNGA achieves the performance bound, and we then quantify the degree of privacy by anonymity. Finally, the extensive simulations demonstrate that the proposed protocol successfully achieves its design goals.

Due to instability of links in the network, the model of delaytolerant networks (DTNs) is often adopted in many emerging mobile applications. To organizations and individuals using these mobile applications, security and privacy are considered to be two of the most significant concerns. This research seeks to address anonymous communications in DTNs. While many different anonymous routing protocols have been proposed for ad hoc networks, to the best of our knowledge, only variants of onion-based routing have been tailored for DTNs. Since each type of anonymous routing protocol has its pros and cons, there is no single anonymous routing protocol for DTNs that can adapt to the different levels of security requirements. In this paper, we first design a set of anonymous routing protocols for DTNs, called anonymous Epidemic and zone-based anonymous routing, based on the original anonymous routing protocols for ad hoc networks. Then, we propose a framework of anonymous routing (FAR) for DTNs, which subsumes all the aforementioned protocols. By tuning its parameters, the proposed FAR is able to outperform onion-based, anonymous Epidemic, and zone-based routing. In addition, numerical analyses for the traceable rate, node anonymity, and path anonymity models are built. Extensive simulations using randomly generated graphs as well as real traces demonstrate that the proposed framework for DTNs successfully achieves its design goals.

Due to software implementation failure and misuse of cryptography, data encryption can no longer be considered a safeguard from security attacks. As a result, adversaries with eavesdropping capability along a routing path can compromise data privacy. In addition, should an adversary be one of the intermediate relay nodes in a path, she can deny data forwarding to disconnect the end-to-end communications. One solution is to avoid message routing through certain insecure areas, such as malicious countries or likely-compromised nodes. To this end, an avoidance routing based on the single path has been proposed. However, this single-path-based protocol relies on the availability of a safe path, i.e., no adversary is in the proximity of the whole path, which is difficult to achieve and therefore limits the routing opportunity. To tackle this issue, we propose an avoidance routing framework, namely timer-based multi-path avoidance routing (TMPAR). In our approach, a source node first encodes a message into k different pieces, and each piece is sent via a different path. During its path discovery phase, a timer is used to efficiently discover a better set of paths. The destination can assemble the original message easily. Under the condition that no adversary obtains all the k pieces of the message, the proposed TMPAR can securely deliver a message to its destination in spite of eavesdropping. The extensive ns-2 simulation results demonstrate that our TMPAR achieves its design goals.

Many fatal car accidents are rear-ended collisions. To help alleviate this issue, a lightweight vehicle turn prediction system is developed, which identifies the forthcoming turn event at the early stage so that the neighboring vehicles can be notified in advance to prevent traffic accidents. The system uses smartphone sensors and digital maps. The smartphone sensors (a.k.a Inertial measurement unit) collect position information of the vehicle and predict the future position using particle filters. These positions are used to compute the curvature of the vehicle trace. From digital maps, the curvature of the road that the vehicle is currently traveling is also computed. By examining the difference of these two curvatures as well as the speed of the vehicle, the system determines if the vehicle is making a turn at the early stage. The experimental results show that the proposed system can correctly identify all the turns on the road. In addition, the proposed system does not require extra hardware, which allows it for inexpensive large-scale deployment.

Cloud storage system provides storage to enterprises and end users, and it helps to reduce the cost of server maintenance. Unfortunately, this new type of data storage service also brings new security challenges as data owners do not have full control of their data. The existing research works cannot completely resolve these security issues efficiently or may cause other security problems. In this paper, a framework with the third party auditor is first proposed. Based on our system model, a key management scheme and an authentication process are proposed which can ensure the security of cloud storage. In addition, two types of key loading methods are proposed to improve the performance of key management. In order to create a system with balanced load, AES encryption algorithm is adopted to reduce the computation load on the user side. Through analyses and simulations, we have shown that the proposed system achieves both security and good overall performance.

In this paper, we seek to address anonymous communications in delay tolerant networks (DTNs). While many different approaches for the internet and ad hoc networks, to the best of our knowledge, only variants of onion-based routing have been tailored for DTNs. Since each type of anonymous routing protocol has its advantages and drawbacks, there is no single anonymous routing protocol for DTNs that can adapt to the different levels of security requirements. In this paper, we first design a set of anonymous routing protocols for DTNs, called anonymous epidemic and zone-based anonymous routing, based on the original anonymous routing protocols for ad hoc networks. Then, we propose a framework of anonymous routing (FAR) for DTNs, which subsumes all the aforementioned protocols. By tuning its parameters, the proposed FAR is able to outperform onion-based, anonymous Epidemic, and zone-based routing.

Security and privacy issues are considered to be two of the most significant concerns to organizations and individuals using mobile applications. In this paper, we seek to address anonymous communications in delay tolerant networks (DTNs). While many different anonymous routing protocols have been proposed for ad hoc networks, to the best of our knowledge, only variants of onion-based routing have been tailored for DTNs. Since each type of anonymous routing protocol has its advantages and drawbacks, there is no single anonymous routing protocol for DTNs that can adapt to the different levels of security requirements. In this paper, we first design a set of anonymous routing protocols for DTNs, called anonymous Epidemic and zone-based anonymous routing, based on the original anonymous routing protocols for ad hoc networks. Then, we propose a framework of anonymous routing (FAR) for DTNs, which subsumes all the aforementioned protocols. By tuning its parameters, the proposed FAR is able to outperform onion-based, anonymous Epidemic, and zone-based routing. In addition, numerical analyses for the traceable rate and node anonymity models are built. Extensive simulations using randomly generated graphs as well as real traces are conducted to demonstrate that given appropriate parameter settings, our FAR outperforms all the existing anonymous routing protocols for DTNs.

Link prediction is a fundamental problem in social network analysis. Although the link prediction problem is not new, the challenge of how to exploit various existing network information, such as network structure data and node attribute data, to enable AI-style knowledge inference for large social networks still remains unsolved. In this paper, we design and implement a scalable framework that treats link prediction as knowledge reasoning using Markov Logic Networks (MLNs). Differing from other probabilistic graphical models, MLNs allow undirected relationships with cycles and long-range (non-adjacent) dependency, which are essential and abound in social networks. In our framework, the prior knowledge is captured as the structure dependency (such as friendship) and the attribute dependency (such as social communities) in terms of inference rules, associated with uncertainty represented as probabilities. Next, we employ the random walk to discover the inference subgraph, on which probabilistic inference is performed, so that the required computation and storage cost can be significantly reduced without much sacrifice of the inference accuracy. Our extensive experiments with real-world datasets verify the superiority of our proposed approaches over two baseline methods and show that our approaches are able to provide a tunable tradeoff between inference accuracy and efficiency.

Delay tolerant network (DTN) routing provides a communication primitive in intermittently disconnected networks, such as battlefield communications and human-contact networks. In these applications, the anonymity preserving mechanism, which hides the identities of communicating parties, plays an important role as a defense against cyber and physical attacks. While anonymous routing protocols for DTNs have been proposed in the past, to the best of our knowledge, there is no work that emphasizes analysis of the performance of these protocols. In this paper, we first design an abstract of anonymous routing protocols for DTNs and augment the existing solution with multi-copy message forwarding. Then, we construct simplified mathematical models, which can be used to understand the fundamental performance and security guarantees of onion-based anonymous routing in DTNs. To be specific, the delivery rate, message forwarding cost, traceable rate, and path and node anonymity are defined and analyzed. The numerical and simulation results using randomly generated contact graphs and the real traces demonstrate that our models provide very close approximations to the performance of the anonymous DTN routing protocol.

Due to the fluctuation of the bandwidth consumption of mobile users, the availability of a more flexible bandwidth pricing structure becomes important. Unfortunately, most mobile service providers only offer long-term contracts. Hence, wireless bandwidth sharing has a potential to become a niche market. In this paper, we propose the pay-per-second model, in which the price is based on the mobile net speed. Our analysis also takes into account the buffet plan, which is available from service providers in several countries to offer mobile users unlimited bandwidth. First, a survey is conducted to collect the data from mobile users. The data are then used to obtain the parameters in our pricing model. The model is verified to be appropriate by Bayesian data analysis. In the experiments, our model is compared against the pay-per-byte model, and the results indicate that our model generates more profit for bandwidth sharing.

A variety of optimal location problems have been extensively studied in the literature. However, limited visualization systems have been developed for illustrating optimal location selection process. In this demonstration, we present a system that visualizes an advanced solution that can efficiently answer multi-criteria optimal location updating query by incrementally updating the Minimum Overlapping Voronoi Diagram (MOVD) model. Not only does our system display an example as a practical multi-criteria optimal location updating query, but also visualizes the process of the query evaluation in a more intuitive manner. With the object insertion and deletion operations defined over the MOVD model, any object changes in an MOVD can be represented by removing the objects from initial datasets and adding them back with updated attributes. Moreover, Haxe toolkit is used to provide friendly and flexible user interfaces in our system.

Delay tolerant network (DTN) routing provides a communication primitive in intermittently disconnected networks, such as battlefield communications and human-contact networks. In these applications, the anonymity preserving mechanism, which hides the identities of communicating parties, plays an important role as a defense against cyber and physical attacks. While anonymous routing protocols for DTNs have been proposed in the past, to the best of our knowledge, there is no work that emphasizes the theoretical aspects. In this paper, we first design an abstract of anonymous routing protocols for DTNs and augment the existing solution with multi-copy message forwarding. Then, we construct simplified mathematical models, which can be used to understand the fundamental performance and security guarantees of onion-based anonymous routing in DTNs. The numerical and simulation results using randomly generated contact graphs and the real traces demonstrate that our models provide very close approximations to the performance of the anonymous DTN routing protocol.

Privacy protection is the primary concern when RFID applications are deployed in our daily lives. Due to the computational power constraints of passive tags, non-encryption-based singulation protocols have been recently developed, in which wireless jamming is used. However, the existing private tag access protocols without shared secrets rely on impractical physical layer assumptions, and thus they are difficult to deploy. To tackle this issue, we first redesign the architecture of RFID system by dividing an RF reader into two different devices, an RF activator and a trusted shield device (TSD). Then, we propose a novel coding scheme, namely Random Flipping Random Jamming (RFRJ), to protect tags' content. Unlike the past work, the proposed singulation protocol utilizes only the physical layer techniques that are already implemented. Analyses and simulation results validate our distributed architecture with the RFRJ coding scheme, which defends tags' privacy against various adversaries including the random guessing attack, correlation attack, ghost-and-leech attack, and eavesdropping.

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to a large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named randomized skip lists-based authentication (RSLA). Without sacrificing the authentication performance, RSLA provides a high privacy preserving mechanism. While RSLA provides the same level of unpredictability-based-privacy and indistinguishability-based privacy compared with other structured key management approaches, our scheme achieves the highest system anonymity with good performance in key look up and update. In addition, the simulation results match our analyses closely.

In this demonstration, we present a visualization system offering two advanced solutions that can efficiently address a novel multi-criteria optimal location query by using Overlapping Voronoi Diagrams (OVDs). Our system not only displays an example that applies the advanced solutions to a practical optimal location query, but also visualizes the process of query evaluation by using the solutions, which can help users better understand the two solutions in a more intuitive way. The Real Region as Boundary (RRB) approach calculates real regions of overlapped Voronoi cells, while the Minimum Bounding Rectangle as Boundary (MBRB) approach approximates the cells by their MBRs to simplify region overlapping calculation. For efficient query evaluation and better demonstration, global and local datasets are managed separately and only the local dataset is displayed in a limited visualization area. User interactions are provided in diverse manners in our system by using the Standard Widget Toolkit (SWT) and Open Graphics Library (OpenGL).

The speedy advancement in computer hardware has caused data encryption to no longer be a 100% safe solution for secure communications. To battle with adversaries, a countermeasure is to avoid message routing through certain insecure areas, e.g., Malicious countries and nodes. To this end, avoidance routing has been proposed over the past few years. However, the existing avoidance protocols are single-path-based, which means that there must be a safe path such that no adversary is in the proximity of the whole path. This condition is difficult to satisfy. As a result, routing opportunities based on the existing avoidance schemes are limited. To tackle this issue, we propose an avoidance routing framework, namely Multi-Path Avoidance Routing (MPAR). In our approach, a source node first encodes a message into k different pieces, and each piece is sent via k different paths. The destination can assemble the original message easily, while an adversary cannot recover the original message unless she obtains all the pieces. We prove that the coding scheme achieves perfect secrecy against eavesdropping under the condition that an adversary has incomplete information regarding the message. The simulation results validate that the proposed MPAR protocol achieves its design goals.

This paper presents a novel optimal location selection problem, which can be applied to a wide range of applications.After providing a formal definition of the novel query type, we explore an intuitive approach that sequentially scans all possible object combinations in the search space.Then, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs, and construct an algebraic structure under an OVD overlap operation.Based on the OVD model, we design an advanced approach to answer the query.Due to the high complexity of Voronoi diagram overlap computation, we improve the overlap operation by replacing the real boundaries of Voronoi diagrams with their Minimum Bounding Rectangles (MBR).We also propose a cost-bound iterative approach that efficiently processes a large number of Fermat-Weber problems.Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.

In this paper, we propose two parameterized frameworks, namely the Uniform Watchtower (UW) framework and the Hot zone-based Watchtower (HW) framework, for the evaluation of spatial queries on large road networks. The motivation of this research is twofold: (1) how to answer spatial queries efficiently on large road networks with massive POI data and (2) how to take advantage of social data in spatial query processing. In UW, the network traversal terminates once it acquires the Point of Interest (POI) distance information stored in watchtowers. In HW, by observing that users' movements often exhibit strong spatial patterns, we employ probabilistic clustering to model mobile user check-in data as a mixture of 2-dimensional Gaussian distributions to identify hot zones so that watchtowers can be deployed discriminatorily. Our analyses verify the superiority of HW over UW in terms of query response time.

People spend a significant amount of time in indoor spaces (e.g., office buildings, subway systems, etc.) in their daily lives. Therefore, it is important to develop efficient indoor spatial query algorithms for supporting various location-based applications. However, indoor spaces differ from outdoor spaces because users have to follow the indoor floor plan for their movements. In addition, positioning in indoor environments is mainly based on sensing devices (e.g., RFID readers) rather than GPS devices. Consequently, we cannot apply existing spatial query evaluation techniques devised for outdoor environments for this new challenge. Because particle filters can be employed to estimate the state of a system that changes over time using a sequence of noisy measurements made on the system, in this research, we propose the particle filter-based location inference method as the basis for evaluating indoor spatial queries with noisy RFID raw data. Furthermore, two novel models, indoor walking graph model and anchor point indexing model, are created for tracking object locations in indoor environments. Based on the inference method and tracking models, we develop innovative indoor range and k nearest neighbor (kNN) query algorithms. We validate our solution through extensive simulations with real-world parameters. Our experimental results show that the proposed algorithms can evaluate indoor spatial queries effectively and efficiently.

As one of the most important Semantic Web applications, social network analysis has attracted more and more interest from researchers due to the rapidly increasing availability of massive social network data. A desired solution for social network analysis should address the following issues. First, in many real world applications, inference rules are partially correct. An ideal solution should be able to handle partially correct rules. Second, applications in practice often involve large amounts of data. The inference mechanism should scale up towards large-scale data. Third, inference methods should take into account probabilistic evidence data because these are domains abounding with uncertainty. Various solutions for social network analysis have existed for quite a few years; however, none of them support all the aforementioned features. In this paper, we design and implement LinkProbe, a prototype to quantitatively predict the existence of links among nodes in large-scale social networks, which are empowered by Markov Logic Networks (MLNs). MLN has been proved to be an effective inference model which can handle complex dependencies and partially correct rules. More importantly, although MLN has shown acceptable performance in prior works, it is also reported as impractical in handling large-scale data due to its highly demanding nature in terms of inference time and memory consumption. In order to overcome these limitations, LinkProbe retrieves the k-backbone graphs and conducts the MLN inference on both the most globally influencing nodes and most locally related nodes. Our extensive experiments show that LinkProbe manages to provide a tunable balance between MLN inference accuracy and inference efficiency.

Indoor localization has become a popular topic in recent years. While self-contained pedestrian dead reckoning (PDR) systems can be conveniently implemented on a smartphone with built-in inertial sensors for indoor localization, the error of the estimated position for a PDR system can accumulate quickly and results in an unacceptable position accuracy. To address this issue, we propose the collaborative pedestrian dead reckoning (CPDR) system. The main idea of the CPDR system is when users are near to each other, we can leverage the proximity information to improve their estimated positions by means of the opportunistic Kalman filter. In addition, the backward correction scheme is used to improve the accuracy of user's trajectory. To evaluate the CPDR system, a prototype is implemented on Apple's iPhone 5. The experiment results show that the CPDR system achieves a better position accuracy than the raw PDR system.

As mobile ad hoc networks are generally applied for the resource access and sharing, enormous amount of resource query may occur in a short period of time, which will easily lead to heavy traffic load in the network. Therefore, the traffic reduction for queries is an important issue. Most of the researches in this area focus on the optimal resources placement strategy under static query traffic and overlook the dynamic nature of the traffic. In this paper, we propose the Dynamic Content Grid Adjustment Strategy (DCGAS) to balance the dynamic traffic load in a network. The main feature behind DCGAS is to adjust the number of resources in a network when the query traffic exceeds or falls behind some critical thresholds. The simulation results demonstrate that our strategy outperforms the state-of-the-art data replication schemes.

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to the large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named Randomized Skip Lists-based Authentication. Without sacrificing the authentication performance, our scheme provides a strong privacy preserving mechanism.

Today Radio Frequency Identification (RFID) technologies are applied in many fields for a variety of applications. Though bringing great productivity gains, RFID systems may cause new security and privacy threats to individuals or organizations. Therefore, it is important to protect the security of RFID systems and the privacy of RFID tag owners. Unfortunately, none of the existing solutions provide a complete defense against eavesdroppers who could monitor the communication between RFID readers and tags and recover the contents of tags. Based on our research, we propose two novel RFID backward channel protection protocols, namely dynamic bit encoding and optimized dynamic bit encoding. Our schemes are able to achieve high anonymity with limited communication overhead. Our extensive simulations show that both proposed schemes provide much stronger backward channel protection than existing techniques. In addition, analytical models were created and validated through comparisons with simulation results.

The past few years have witnessed the emergence of an increasing number of applications for tracking and tracing based on radio frequency identification (RFID) technologies. However, raw RFID readings are usually of low quality and may contain numerous anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the environment may help improve data quality, and a desired solution must be able to take into account such knowledge. Third, the solution should take advantage of physical constraints in target applications to elevate the accuracy of data cleansing. There are several existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper, we propose a Bayesian inference-based framework for cleaning RFID raw data. We first design an n-state detection model and formally prove that the three-state model can maximize the system performance. Then, we extend the n-state model to support two-dimensional RFID reader arrays and compute the likelihood efficiently. In addition, we devise a Metropolis-Hastings sampler with constraints, which incorporates constraint management to clean RFID data with high efficiency and accuracy. Moreover, to support real-time object monitoring, we present the streaming Bayesian inference method to cope with realtime RFID data streams. Finally, we evaluate the performance of our solutions through extensive experiments.

At present, mobile devices are prevalent with end users and continuous media streaming services in mobile ad-hoc networks (MANETs) support popular applications. It is required for applications that stream isochronous media that the network link be continuously available. In this study, we introduce two group-server scheduling schemes to improve link continuity: static group-server scheduling and dynamic group-server scheduling . With our solution, if one of the current links between a client and a server instance breaks, the client can still download the multimedia content from another scheduled server peer. In addition, we incorporate the data link layer constraints as well as privacy concerns into our protocol design. The simulation results show that the proposed schemes significantly improve the effective link duration, overall system performance, and degree of privacy in MANETs.

The connected dominating set (CDS) has been extensively used for routing and broadcast in wireless ad hoc networks. While existing CDS protocols are successful in constructing CDS of small size, they either require localized information beyond immediate neighbors, lack the mechanism to properly handle nodal mobility, or involve lengthy recovery procedure when CDS becomes corrupted. In this paper, we introduce the timer-based CDS protocols, which first elect a number of initiators distributively and then utilize timers to construct a CDS from initiators with the minimum localized information. We demonstrate that our CDS protocols are capable of maintaining CDS in the presence of changes of network topology. Depending on the number of initiators, there are two versions of our timer-based CDS protocols. The Single-Initiator (SI) generates the smallest CDS among protocols with mobility handling capability. Built on top of SI, the Multi-Initiator (MI) version removes the single point of failure at single-initiator and possesses most advantages of SI. We evaluate our protocols by both the ns-2 simulation and an analytical model. Compared with the other known CDS protocols, the simulation results demonstrate that both SI and MI produce and maintain CDS of very competitive size. The analytical model shows the expected convergence time and the number of messages required by SI and MI in the construction of CDS, which match closely to our simulation results. This helps to establish the validity of our simulation.

Radio Frequency Identification (RFID) technologies are used in many applications for data collection. However, raw RFID readings are usually of low quality and may contain many anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings (by multiple readers simultaneously or by a single reader over a period of time) of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the readers and the environment (e.g., prior data distribution, false negative rates of readers) may help improve data quality and remove data anomalies, and a desired solution must be able to quantify the degree of uncertainty based on such knowledge. Third, the solution should take advantage of given constraints in target applications (e.g., the number of objects in a same location cannot exceed a given value) to elevate the accuracy of data cleansing. There are a number of existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper we propose a Bayesian inference based approach for cleaning RFID raw data. Our approach takes full advantage of data redundancy. To capture the likelihood, we design an n-state detection model and formally prove that the 3-state model can maximize the system performance. Moreover, in order to sample from the posterior, we devise a Metropolis-Hastings sampler with Constraints (MH-C), which incorporates constraint management to clean RFID raw data with high efficiency and accuracy. We validate our solution with a common RFID application and demonstrate the advantages of our approach through extensive simulations.

In multi-hop wireless networks, the use of virtual backbone can greatly simplify routing, broadcasting, as well as energy/bandwidth saving. However, constructing a virtual backbone is costly and time-consuming because of the inevitable transmission interference during the process of the construction. In the literature, most of virtual backbone construction algorithms did not take the interference issue into consideration. To the best of our knowledge, our proposed algorithm is the first fully-distributed, interference-aware virtual backbone construction algorithm that has a proven bound on the construction latency. Besides, our proposed algorithm can be applied to the leader election problem, and such application results in a fully-distributed and interference-aware leader election algorithm of time complexity O(n \log n) (where n is the number of nodes). This new leader election algorithm is practical in wireless networks because interference has already been dealt with; is also results in the fastest interference-aware leader election algorithm to the best of our knowledge.

The connected dominating set (CDS) has been commonly used for routing and broadcast in mobile ad hoc networks (MANETs). Considering the applications of MANETs, it is generally preferred that the CDS protocol not only creates CDS of small size, incurs less communication and computational overheads, adapts to the nodal mobility, but also generates CDS as quickly as possible. Unfortunately, none of the existing CDS protocols possesses all of these desirable properties. In this paper, we propose an algorithm to rapidly grow a CDS tree from an initiator. By incorporating this algorithm with the Multi-Initiator CDS protocol, we have created the CDS protocol for MANETs which enjoys all the aforementioned desirable properties. The simulation results validate that our proposed protocol achieves its design goals. In addition, an analytical model is provided that can accurately estimate the convergence time required by our proposed CDS protocol.

In cluster-based sensor networks, part of the sensor nodes can be switched into a sleep state in order to conserve energy if their neighbors can provide the same or almost the same sensing coverage. However, as the number of nodes in the sleep state increases, coverage for the cluster is degraded. It is crucial to maintain high coverage of clusters in order to preserve performance. In this paper, we propose a coverage- aware sleep scheduling (CS) algorithm to improve the coverage of each cluster. Compared with two previous schemes: the randomized scheduling (RS) scheme and the distance-based scheduling (DS) scheme, the CS algorithm maintains higher coverage, while guaranteeing the same lifetime for the cluster. The CS algorithm thus improves the overall performance of the cluster-based sensor networks.

Trip planning search (TPS) represents an important class of queries in Geographic Information Systems (GIS). In many real-world applications, TPS requests are issued with a number of constraints. Unfortunately, most of these constrained TPS cannot be directly answered by any of the existing algorithms. By formulating each restriction into rules, we propose a novel form of route query, namely the multi-rule partial sequenced route (MRPSR) query. Our work provides a unified framework that also subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. In this paper, we first prove that MRPSR is NP-hard and then present three heuristic algorithms to search for near-optimal solutions for the MRPSR query. Our extensive simulations show that all of the proposed algorithms can answer the MRPSR query effectively and efficiently. Using both real and synthetic datasets, we investigate the performance of our algorithms with the metrics of the route distance and the response time in terms of the percentage of the constrained points of interest (POI) categories. Compared to the LORD-based brute-force solution, the response times of our algorithms are remarkably reduced while the resulting route length is only slightly longer than the shortest route.

The connected dominating set (CDS) has been extensively used for routing and broadcast in mobile ad hoc networks. While existing CDS protocols are successful in constructing CDS of competitive size with localized information, they either lack the mechanism to properly handle nodal mobility or require lengthy period of time to recover when CDS becomes corrupted. In this paper, a novel protocol, namely Multi-Initiator Connected Dominating Set protocol (MI-CDS), is proposed that constructs and maintains CDS of competitive size efficiently without introducing much communication overhead. The simulation results demonstrate that MI-CDS permits CDS to be available for the highest percentage of time in the mobile network scenario compared with the other CDS protocols.

Tree routing is one of the detouring strategies employed in geographic routing to help find a detour for a packet to leave a local minimum. The effectiveness of tree routing depends on the quality of the pre-constructed routing trees. Existing tree construction methods build trees in a top-down and centralized fashion and do not consider the traffic load in the network, and therefore is likely to create trees with poor routing performance. In this paper, we propose a novel routing tree, namely traffic-aware routing tree, which is constructed completely in a bottom-up fashion and with the traffic load in mind. Simulation results show that such traffic-aware routing trees have very few conflicting hulls and much higher path throughput than other routing trees, leading to a better routing performance.

Load balancing is an important issue in sensor networks especially when geographic routing is employed since in this case, a node often forwards its packet to a certain neighbor. As a result, nodes located at the intersection of multiple routes to the base station tend to be placed under great stress and drain its energy quickly. This can potentially lead to disconnection of the network. Current solutions to this problem fail to take the traffic load at nodes into account and can potentially forward packets toward the heavy trafficked region and create collisions and network congestion. In this paper, we propose a load balancing scheme, namely traffic adaptive routing (TAR), which works with any geographic routing protocols. TAR relieves the aforementioned issues by having a node evaluate the level of traffic at its neighbors and decide where to forward the packet based on the distance to the base station and the traffic load. Through simulations, we have shown that when compared against the existing load balancing techniques, TAR is able to deliver 10% more packets to the base station using approximately the same amount of energy due to the reduction of the collisions and congestion.

Energy efficiency is one of the most critical issues in wireless sensor networks, because sensor nodes are usually powered by batteries and their energy is extremely limited. To reduce the energy consumption, anchor-based geographic routing aims at finding a small number of intermediate nodes acting as anchors so that the path length (i.e., number of hops) between the source and destination can be reduced. However, some nodes (e.g., nodes near the boundary of the network) tend to be used as anchors repeatedly by multiple flows. As a result, their energy drains quickly and the lifetime of the network is reduced. Moreover, the intermediate nodes between source and destination change very little once the anchor list is set. This also contributes to the quick depletion of the energy for some nodes. In this paper, we propose to introduce a random shift to the location of anchors. Doing so, more nodes in the network are likely to become anchors and the energy consumption for packet routing can be better distributed among nodes in the network. We show analytically that our strategy improves the network lifetime. Simulation results show that this energy-aware strategy is effective in increasing the number of packets delivered in the lifetime of sensor networks.

Geographical routing protocols are promising in wireless sensor networks because of their ability to discover a sub-optimal route without the help of a global state. Existing geographical routing protocols can guarantee packet delivery if the network topology after planarization remains connected. However, face routing used in non-flooding geographical routing algorithms usually results in a large number of hops, which not only reduces network efficiency, but may also decrease delivery rate when packets are subject to the constraint of time to live (TTL). In this paper, we present a path shortening algorithm that reduces the number of hops of geographical routing by exploiting the channel listening capability of wireless nodes. We investigate the impact of the algorithm on the delivery rate under the constraint of TTL. Simulation results show that in average the path shortening algorithm can reduce as much as 80% hops on the routes obtained by existing geographical protocols such as GPSR and GOAFR+in a critical network density region, and the improvement of packet delivery rate is up to 50% with a maximum of three retransmissions without increasing TTL.

Geographical routing is powerful for its ability to discover route to the destination without the help of global state. However, detours usually occur when the packet reaches a local minimum. In this case, the network topology has to be reduced to a planar graph and recovery schemes such as face routing are needed. However, face routing may create a large number of hops on a planar graph. When multiple packets are generated for the same destination, such a large number of hops tends to consume more energy. In this paper, a simple yet effective path pruning strategy is proposed to reduce the excessive number of hops caused by the detouring mode of geographical routing protocols. The path pruning algorithm finds routing shortcuts by exploiting the channel listening capability of wireless nodes, and is able to reduce a large number of hops with the help of little state information passively maintained by a subset of nodes on the route. The average hop count of the proposed algorithm is compared to those of existing geographical routing algorithms and the benchmark shortest path algorithm. Simulation results show that in average the path pruning algorithm can reduce as much as 80% of hops on the routes obtained by greedy perimeter stateless routing (GPSR) and greedy other adaptive face routing+(GOAFR+) in a critical network density range

Connected dominating set (CDS) has been used widely in mobile ad hoc networks by numerous routing, broadcast, and time synchronization protocols. Although computing minimum CDS is known to be NP-hard, many distributed protocols have been proposed to construct a small CDS. However, these protocols are either too complicated, need non-local information, are not adaptive to topology changes, or fail to consider the difference in energy consumption for nodes within and outside the CDS. In this paper, we present two timer-based energy-aware connected dominating set protocols. Our protocols extend the MAC-layer timer-based connected dominating set protocol (MTCDS) so that the energy level at each node is taken into account when constructing the CDS. Simulation results have shown that our protocols effectively construct an energy-aware CDS with a very competitive size and prolong the network operation under different levels of nodal mobility.

Abstract Multicast/broadcast is an important service primitive in networks. It is supported by all IEEE 802.x standards, including 802.11. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced owing to the increased probability of lost frames resulting from interference or collisions. Recently, a few MAC protocols have been proposed to enhance the reliability and the efficiency of the 802.11 multicast/broadcast protocol. In this paper, we observe that these protocols are still unreliable or inefficient. To redress the problems of reliability and efficiency, we propose a reliable Batch Mode Multicast MAC protocol (BMMM), which in most cases reduces the number of contention phases fromnto 1, wherenis the number of intended receivers in the multicast/broadcast. This considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol (LAMM), which uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. Copyright © 2003 John Wiley & Sons, Ltd.

Bluetooth utilizes fast frequency hopping to mitigate interference from other wireless devices and other Bluetooth piconets that share the same frequency range. However, it still can not avoid the interference between piconets entirely. In our simulation, we observed that the inter-piconet interference can significantly degrade the system throughput by more than 30%. The system throughput within a piconet can be improved by a proper arrangement of the segmentation/reassembling (SAR) policy and a good selection of MAC scheduling protocols. Many SAR policies and MAC scheduling protocols were proposed, but none of them takes the inter-piconet interference into consideration. In this paper, we study the impact of the interference on the performance of TCP traffic over a Bluetooth scatternet with multiple overlapping piconets. To alleviate the impact, we propose interference-aware SAR policies as well as the interference-aware MAC scheduling protocols. The simulation results show that our schemes help reduce the impact of the inter-piconet interference by more than 50%.

Broadcast service is fundamental in ad hoc networks for different applications and dynamic source routing protocols. One problem that makes the traditional broadcast protocol inefficient is the broadcast storm problem. To alleviate the broadcast storm problem, the number of re-transmissions for a broadcast needs to be reduced. One possible solution is to use the node's geometric location information to obtain a smaller subset of neighbors (called local cover set) for re-transmissions. In this paper, we investigate the unique existence of the optimal local cover set. Based on the proof, we construct a location-based algorithm to compute the local cover set. We prove the correctness of our algorithm and discuss the time complexity of the algorithm. The simulation shows that the local cover set generated by our algorithm is significantly smaller than the graph-based broadcast protocol of Wu and Li (see Proc. DIAL M, Aug. 1999, p.7-14).

Multicast/broadcast is an important service primitive in networks. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced due to the increased probability of lost frames resulting from interference or collisions. In this paper, we propose a reliable Batch Mode Multicast MAC protocol, BMMM, which substentially reduces the number of contention phases, thus considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol, LAMM, that uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. 1

Ad hoc networks in wireless communications is a challenging field due to the constant change of network topology. Broadcast service in ad hoc networks is critical in supporting various important applications and message routing. We examine the problem of the traditional broadcast protocol (i.e., flooding) in mobile wireless ad hoc networks, also known as "broadcast storm problem". We introduce a location aided algorithm to compute the optimal local cover set without delay and without much communication overhead. Based on the algorithm, we propose three new location-aided broadcast protocols for ad hoc networks that compute the optimal local cover set for retransmissions on-the-fly. We compare and analyze the simulation results of our protocols and others. The results show that our new protocols save a significant amount of wireless bandwidth and consume less overhead.

Building efficient ad hoc networks for wireless communications is challenging due to the dynamic nature of the hosts. Broadcast service in ad hoc networks is critical in supporting various applications and protocols. However, excessive redundant retransmissions of traditional broadcast protocols in mobile wireless ad hoc networks have caused the infamous "broadcast storm problem." Various broadcast protocols have been proposed to alleviate the broadcast storm problem. We identify two primary design issues, namely defer time generation and redundant message classification, for all these protocols. We propose a distance-based defer time scheme for the first issue and an angle-based scheme for the second issue. The two schemes together result in a broadcast protocol that enjoys flooding's high reachability and non-flooding schemes' bandwidth efficiency.

Intelligent Transportation Systems (ITS) have become a focus for many countries. To achieve ITS, Inter Vehicle Communication (IVC) is required for the exchange and distribution of data such as congestion or emergency information. If this communication can be done without fixed infrastructure, the systems can be deployed quickly and on a larger scale. Ad hoc networking technologies are one such technology to achieve IVC. However, if generic ad hoc network solutions are applied directly to IVC, performance can degrade quickly as the system scales particularly for broadcast type messages. In this paper we propose two new broadcast protocols that reduce bandwidth required for broadcast communication by taking advantage of a vehicle's highly directional movement and Global Positioning Information. To show the performance of our new protocols, we compare our approach with generic ad hoc broadcasting techniques. Our results show that it is possible to achieve several hundred percent improvement of bandwidth utilization with very slight sacrifice of reachability.