A few recent works attempt to train an adversarially robust Unsupervised Domain Adaptation (UDA) model, transferring the robustness from a robust source model or other robust pre-trained models to an unlabeled target domain. However, it is usually impractical to assume the availability of robust source models or robust pre-training, and meanwhile, source data are not always accessible or efficient for adaptation training in many real-world scenarios. In this paper, we dive into a more practical and challenging problem of robust source-free domain adaptation: can we train a robust model on an unlabeled target domain given only a non-robust source model (without source data)? Empirically, we find that applying adversarial training (AT) to the self-supervised adaptation process leads to severe model degradation, as it tends to amplify the inevitable errors of UDA models. To tackle this issue, we propose a novel approach called Source-Free Alternating Optimization (SFAO), which employs a non-robust target model to provide better guidance for the AT of the desired robust target model. The two models are trained in an alternating manner to minimize the discrepancy between the clean source domain and the adversarial target domain. Moreover, we propose Softly-Constrained Adversarial Training (SCAT) to further mitigate the adverse effects of incorrect pseudo-labels in AT. Extensive experimental results demonstrate that the proposed method significantly improves the model performance on both clean and adversarial data. Source code is available at: https://github.com/Coxy7/robust-SFDA.

We focus on the problem of fusing two or more heterogeneous large language models (LLMs) to leverage their complementary strengths.One of the challenges of model fusion is high computational load, specifically in fine-tuning or aligning vocabularies.To address this, we propose Cool-Fusion, a simple yet effective approach that fuses the knowledge of source LLMs, which does not require training.Unlike ensemble methods, Cool-Fusion is applicable to any set of source LLMs that have different vocabularies.To overcome the vocabulary discrepancies among LLMs, we ensemble LLMs on text level, allowing them to rerank the generated texts by each other with different granularities.Extensive experiments have been conducted across a variety of benchmark datasets.On GSM8K, Cool-Fusion increases accuracy from three strong source LLMs by a significant margin of 17.4%.

Deep hashing is an appealing approach for large-scale image retrieval. Most existing supervised deep hashing methods learn hash functions using pairwise or triple image similarities in randomly sampled mini-batches. They suffer from low training efficiency, insufficient coverage of data distribution, and pair imbalance problems. Recently, central similarity quantization (CSQ) attacks the above problems by using “hash centers” as a global similarity metric, which encourages the hash codes of similar images to approach their common hash center and distance themselves from other hash centers. Although achieving SOTA retrieval performance, CSQ falls short of a worst-case guarantee on the minimal distance between its constructed hash centers, i.e. the hash centers can be arbitrarily close. This paper presents an optimization method that finds hash centers with a constraint on the minimal distance between any pair of hash centers, which is non-trivial due to the non-convex nature of the problem. More importantly, we adopt the Gilbert-Varshamov bound from coding theory, which helps us to obtain a large minimal distance while ensuring the empirical feasibility of our optimization approach. With these clearly-separated hash centers, each is assigned to one image class, we propose several effective loss functions to train deep hashing networks. Extensive experiments on three datasets for image retrieval demonstrate that the proposed method achieves superior retrieval performance over the state-of-the-art deep hashing methods.

Deep learning models are challenged by the distribution shift between the training data and test data. Recently, the large models pre-trained on diverse data have demonstrated unprecedented robustness to various distribution shifts. However, fine-tuning these models can lead to a trade-off between in-distribution (ID) performance and out-of-distribution (OOD) robustness. Existing methods for tackling this trade-off do not explicitly address the OOD robustness problem. In this paper, based on causal analysis of the aforementioned problems, we propose a novel fine-tuning method, which uses masked images as counterfactual samples that help improve the robustness of the fine-tuning model. Specifically, we mask either the semantics-related or semantics-unrelated patches of the images based on class activation map to break the spurious correlation, and refill the masked patches with patches from other images. The resulting counterfactual samples are used in feature-based distillation with the pre-trained model. Extensive experiments verify that regularizing the fine-tuning with the proposed masked images can achieve a better trade-off between ID and OOD performance, surpassing previous methods on the OOD performance. Our code is available at https://github.com/Coxy7/robust-finetuning.

Unsupervised Domain Adaptation (UDA) learns a model for an unlabeled target domain, utilizing a labeled source domain. Most existing works on UDA assume the availability of source data and neglect the adversarial robustness of the models, hindering security-sensitive real-world applications. In this paper, we study adversarially robust source-free UDA, aiming to train a robust target model by adapting a non-robust source model without using source data. A basic approach is to train a non-robust teacher model via conventional source-free UDA to predict pseudo-labels for target data, and then train a robust student model via adversarial training (AT). However, AT tends to magnify the errors of the teacher model, reducing the accuracy. Hence, we propose Relaxed Adversarial Training (RAT) that relieves the constraints on the confidence of predictions in AT to balance the robustness and accuracy. Extensive experiments validate that RAT can improve the accuracy on clean and adversarial samples, and is superior to related methods. Our code is available at https://github.com/Coxy7/RAT.

We propose a novel algorithm that improves on the previous neural span-based CKY decoder for constituency parsing. In contrast to the traditional span-based decoding, where spans are combined only based on the sum of their scores, we introduce an order-sensitive strategy, where the span combination scores are more carefully derived from an order-sensitive basis. Our decoder can be regarded as a generalization over existing span-based decoder in determining a finer-grain scoring scheme for the combination of lower-level spans into higher-level spans, where we emphasize on the order of the lower-level spans and use order-sensitive span scores as well as order-sensitive combination grammar rule scores to enhance prediction accuracy. We implement the proposed decoding strategy harnessing GPU parallelism and achieve a decoding speed on par with state-of-the-art span-based parsers. Using the previous state-of-the-art model without additional data as our baseline, we outperform it and improve the F1 score on the Penn Treebank Dataset by 0.26% and on the Chinese Treebank Dataset by 0.35%.

Existing lexically constrained machine translation employs data augmentation and incorporates lexical constraints during decoding period, which requires a bilingual dictionary or costs much decoding time. In this paper, we propose a simple but effective method to leverage lexical constraints. We use separate encoders to encode source sentence and lexical constraints, with self-attention layer mask to disentangle the two encoding subtasks. Our method does not require bilingual dictionaries or modify decoding process. Experiments on WMT 2016 English-German (En-De) and IWSLT 2017 English-Chinese (En-Zh) datasets show that our method gains improvement compared to baseline models.

Mobility-assisted opportunistic routing in mobile social network is an interesting research topic with real world applications. It allows users to exchange large chunks of data without relying on stationary network infrastructures. This paper proposes a scalability and privacy preserving routing algorithm. The core of a multi-hop routing scheme is the prediction of the next relay router, which ideally is the next hop on the shortest path to the destination of the message. The proposed routing algorithm contains a machine learning based prediction model that is trained on a trace of nodes connection events collected during a warm up period in a network where the mobility is assumed to exhibit a certain degree of regularity as in general human social networks. The algorithm is scalable since the prediction model, i.e. the control plane of the algorithm, only needs to maintain and broadcast the trained model that implicitly encodes the possible mobility locations and patterns within the mobility area, which is a constant to the number of nodes in the network. The algorithm is privacy preserving because that it does not require the nodes to disclose to other nodes any explicit information about its previous mobility or its personal preferences. Privacy preserving is achieved by using distributed node representations that jointly encode the mobility pattern of the node together with the prediction model, instead of using explicit statistical information to represent previous connectivity patterns as in prior work. This on one hand make attacker hard to find out any exact information about any particular node, and on the other hand enables the routing algorithm to extrapolate to the prediction of nodes of unseen mobility pattern, which is difficult if hand designed statistical mobility information is used. To perform large scale experiments, we collect very large synthetic mobility trace from university course registration information, this trace contain a total of about 35,000 nodes and 300 million message forwarding links. Experiments are conduct to examine several prediction accuracies of our algorithm.

We describe an attentive encoder that combines tree-structured recursive neural networks and sequential recurrent neural networks for modelling sentence pairs. Since existing attentive models exert attention on the sequential structure, we propose a way to incorporate attention into the tree topology. Specially, given a pair of sentences, our attentive encoder uses the representation of one sentence, which generated via an RNN, to guide the structural encoding of the other sentence on the dependency parse tree. We evaluate the proposed attentive encoder on three tasks: semantic similarity, paraphrase identification and true-false question selection. Experimental results show that our encoder outperforms all baselines and achieves state-of-the-art results on two tasks.

Mobile crowdsensing is a new paradigm in which a crowd of mobile users exploit their carried smart devices to conduct complex computation and sensing tasks in mobile social networks (MSNs). In this paper, we focus on the task assignment problem in mobile crowdsensing. Unlike traditional task scheduling problems, the task assignment in mobile crowdsensing must follow the mobility model of users in MSNs. To solve this problem, we propose an oFfline Task Assignment (FTA) algorithm and an oNline Task Assignment (NTA) algorithm. Both FTA and NTA adopt a greedy task assignment strategy. Moreover, we prove that the FTA algorithm is an optimal offline task assignment algorithm, and give a competitive ratio of the NTA algorithm. In addition, we demonstrate the significant performance of our algorithms through extensive simulations, based on four real MSN traces and a synthetic MSN trace.

Hashing is a popular approximate nearest neighbor search approach for large-scale image retrieval. Supervised hashing, which incorporates similarity/dissimilarity information on entity pairs to improve the quality of hashing function learning, has recently received increasing attention. However, in the existing supervised hashing methods for images, an input image is usually encoded by a vector of hand-crafted visual features. Such hand-crafted feature vectors do not necessarily preserve the accurate semantic similarities of images pairs, which may often degrade the performance of hashing function learning. In this paper, we propose a supervised hashing method for image retrieval, in which we automatically learn a good image representation tailored to hashing as well as a set of hash functions. The proposed method has two stages. In the first stage, given the pairwise similarity matrix $S$ over training images, we propose a scalable coordinate descent method to decompose $S$ into a product of $HH^T$ where $H$ is a matrix with each of its rows being the approximate hash code associated to a training image. In the second stage, we propose to simultaneously learn a good feature representation for the input images as well as a set of hash functions, via a deep convolutional network tailored to the learned hash codes in $H$ and optionally the discrete class labels of the images. Extensive empirical evaluations on three benchmark datasets with different kinds of images show that the proposed method has superior performance gains over several state-of-the-art supervised and unsupervised hashing methods.

This paper proposes an efficient opportunistic forwarding algorithm in Delay Tolerant Networks (DTNs) using only local information: inter-meeting times collected locally. It tries to minimize delay with a controlled energy consumption through placing a limitation on the number of total copies per message. The proposed forwarding algorithm makes forwarding decisions based only on local information, which means that no information is needed to be exchanged among the nodes, except for the data to be transferred. The removal of information propagation is particularly important in large-scale DTNs with limited communication opportunities like vehicular communication networks. On the contrary, most existing algorithms either forward messages randomly without facilitating any information, or require the exchange of certain information to make wise forwarding decision. Extensive real trace-driven simulations are conducted, and the proposed algorithm significantly outperforms all of the comvehicular communication networks. Onpared localized algorithms in every simulation.

In cognitive radio (CR) networks, a pair of CR nodes have to ``rendezvous'' on a common channel for link establishment. Channel hopping (CH) protocols have been proposed for creating rendezvous over multiple channels to reduce the possibility of rendezvous failures caused by the detection of primary user signals. Rendezvous within a minimal bounded time over multiple channels is a challenging problem in heterogeneous CR networks where two CR nodes may have asynchronous clocks, different sensing capabilities, no common universal channel set, and heterogeneous channel index systems. In this paper, we present a systematic approach using group theory for designing CH protocols that guarantee the maximum number of rendezvous channels and the minimal time-to-rendezvous (TTR) in heterogeneous environments. We derive the minimum upper bound of TTR, and propose two types of rendezvous protocols that are independent of environmental heterogeneity. Analytical and simulation results show that these protocols are resistant to rendezvous failures under various network conditions.

Due to intermittent connectivity and uncertain node mobility, opportunistic message forwarding algorithms have been widely adopted in delay tolerant networks (DTNs). While existing work proposes practical forwarding algorithms in terms of increasing the delivery rate and decreasing data overhead, little attention has been drawn to the control overhead induced by the algorithms. The control overhead could, however, make the forwarding algorithms infeasible when the network size scales. In this paper, we are interested in increasing scalability by reducing control overhead, while retaining the state-of-the-art forwarding performances. The basic idea is to use locality-sensitive hashing to map each node as a hash-code, and use these hash-codes to compute the pair-wise similarity that guides the forwarding decisions. The proposed SOFA algorithms have reduced control overhead and competitive forwarding performance, which are verified by extensive real trace-driven simulations.

Deep packet inspection (DPI), based on regular expressions, is expressive, compact, and efficient in specifying attack signatures. We focus on their implementations based on general-purpose processors that are cost-effective and flexible to update. In this paper, we propose a novel solution, called deterministic finite automata with extended character-set (DFA/EC), which can significantly decrease the number of states through doubling the size of the character-set. Unlike existing state reduction algorithms, our solution requires only a single main memory access for each byte in the traffic payload, which is the minimum. We perform experiments with several Snort rule-sets. Results show that, compared to DFAs, DFA/ECs are very compact and are over four orders of magnitude smaller in the best cases; DFA/ECs also have smaller memory bandwidth and run faster. We believe that DFA/EC will lay a groundwork for a new type of state compression technique in fast packet inspection.

Rank aggregation, which combines multiple individual rank lists toobtain a better one, is a fundamental technique in various applications such as meta-search and recommendation systems. Most existing rank aggregation methods blindly combine multiple rank lists with possibly considerable noises, which often degrades their performances. In this paper, we propose a new model for robust rank aggregation (RRA) via matrix learning, which recovers a latent rank list from the possibly incomplete and noisy input rank lists. In our model, we construct a pairwise comparison matrix to encode the order information in each input rank list. Based on our observations, each comparison matrix can be naturally decomposed into a shared low-rank matrix, combined with a deviation error matrix which is the sum of a column-sparse matrix and a row-sparse one. The latent rank list can be easily extracted from the learned low-rank matrix. The optimization formulation of RRA has an element-wise multiplication operator to handle missing values, a symmetric constraint on the noise structure, and a factorization trick to restrict the maximum rank of the low-rank matrix. To solve this challenging optimization problem, we propose a novel procedure based on the Augmented Lagrangian Multiplier scheme. We conduct extensive experiments on meta-search and collaborative filtering benchmark datasets. The results show that the proposed RRA has superior performance gain over several state-of-the-art algorithms for rank aggregation.

Data fusion, which effectively fuses multiple prediction lists from different kinds of features to obtain an accurate model, is a crucial component in various computer vision applications. Robust late fusion (RLF) is a recent proposed method that fuses multiple output score lists from different models via pursuing a shared low-rank latent matrix. Despite showing promising performance, the repeated full Singular Value Decomposition operations in RLF's optimization algorithm limits its scalability in real world vision datasets which usually have large number of test examples. To address this issue, we provide a scalable solution for large-scale low-rank latent matrix pursuit by a divide-and-conquer method. The proposed method divides the original low-rank latent matrix learning problem into two size-reduced sub problems, which may be solved via any base algorithm, and combines the results from the sub problems to obtain the final solution. Our theoretical analysis shows that with fixed probability, the proposed divide-and-conquer method has recovery guarantees comparable to those of its base algorithm. Moreover, we develop an efficient base algorithm for the corresponding sub problems by factorizing a large matrix into the product of two size-reduced matrices. We also provide high probability recovery guarantees of the base algorithm. The proposed method is evaluated on various fusion problems in object categorization and video event detection. Under comparable accuracy, the proposed method performs more than $180$ times faster than the state-of-the-art baselines on the CCV dataset with about 4,500 test examples for video event detection.

In this paper, we propose a time-sensitive utility model for delay tolerant networks (DTNs), in which each message has an attached time-sensitive benefit that decays over time. The utility of a message is the benefit minus the transmission cost incurred by delivering the message. This model is analogous to the postal service in the real world, which inherently provides a good balance between delay and cost. Under this model, we propose a Time-sensitive Opportunistic Utility-based Routing (TOUR) algorithm. TOUR is a single-copy opportunistic routing algorithm, in which a time-sensitive forwarding set is maintained for each node by considering the probabilistic contacts in DTNs. By forwarding messages via nodes in these sets, TOUR can achieve the optimal expected utilities. We show the outstanding performance of TOUR through extensive simulations with several real DTN traces. To the best of our knowledge, TOUR is the first utility-based routing algorithm in DTNs.

The Internet has become a platform for delivering and consuming content. Additionally, mobile devices consume a significant chunk of content, which poses a unique challenge for provisioning efficient content delivery and is not addressed in contemporary infrastructures. In this paper, we present a naming system that provides Internet-scale content distribution service with a particular emphasis on content delivery across mobile devices. The basis of the system is a highly flexible and expressive content naming scheme. It is flexible in expressing diverse application requirements. To achieve fast name resolution, we design a two-level indexing network using Distributed Hash Table (DHT). This architecture is open and scalable. It utilizes a key-value storage system built on DHT. Our content delivery protocol relies on content routers to balance the load of delivering content and to throttle denial-of-service attacks. The feasibility of the system is analyzed based on a realistic modeling of the Internet. Simulation studies are performed to verify its usefulness and performance.

Learning-to-rank for information retrieval has gained increasing interest in recent years. Inspired by the success of sparse models, we consider the problem of sparse learning-to-rank, where the learned ranking models are constrained to be with only a few nonzero coefficients. We begin by formulating the sparse learning-to-rank problem as a convex optimization problem with a sparse-inducing ℓ1constraint. Since the ℓ1constraint is nondifferentiable, the critical issue arising here is how to efficiently solve the optimization problem. To address this issue, we propose a learning algorithm from the primal dual perspective. Furthermore, we prove that, after at most O(1/ε) iterations, the proposed algorithm can guarantee the obtainment of an ε-accurate solution. This convergence rate is better than that of the popular subgradient descent algorithm. i.e., O(1/ε2). Empirical evaluation on several public benchmark data sets demonstrates the effectiveness of the proposed algorithm: 1) Compared to the methods that learn dense models, learning a ranking model with sparsity constraints significantly improves the ranking accuracies. 2) Compared to other methods for sparse learning-to-rank, the proposed algorithm tends to obtain sparser models and has superior performance gain on both ranking accuracies and training time. 3) Compared to several state-of-the-art algorithms, the ranking accuracies of the proposed algorithm are very competitive and stable.

Deep packet inspection, in which packet payloads are matched against a large set of patterns, is an important algorithm in many networking applications. Nondeterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) are the basis of existing algorithms. However, both NFA and DFA are not ideal for real-world rule sets: NFA has the minimum storage, but the maximum memory bandwidth; while DFA has the minimum memory bandwidth, but the maximum storage. Specifically, NFA and DFA cannot handle the presence of character sets, wildcards, and repetitions of character sets or wildcards in real-world rule sets. In this paper, we propose and evaluate a dual Finite Automaton (dual FA) to address these shortcomings. The dual FA consists of a linear finite automaton (LFA) and an extended deterministic finite automaton (EDFA). The LFA is simple to implement, and it provides an alternative approach to handle the repetition of character sets and wildcards (which could otherwise cause the state explosion problem in a DFA) without increasing memory bandwidth. We evaluate the automaton in real-world rule sets using different synthetic payload streams. The results show that dual FA can reduce the number of states up to five orders of magnitude while their memory bandwidth is close to minimum.

Delay Tolerant Networks (DTNs) are characterized by nondeterministic mobility and connectivity. Message routing in DTNs usually employs a multicopy forwarding scheme. To avoid the cost associated with flooding, much effort has been focused on opportunistic forwarding, which aims to reduce the cost of forwarding while retaining high routing performance by forwarding messages only to nodes that have high delivery probabilities. This paper presents two multicopy forwarding protocols, called optimal opportunistic forwarding (OOF) and OOF-, which maximize the expected delivery rate and minimize the expected delay, respectively, while requiring that the number of forwardings per message does not exceed a certain threshold. Our contributions in this paper are summarized as follows: We apply the optimal stopping rule in the multicopy opportunistic forwarding protocol. Specifically, we propose two optimal opportunistic forwarding metrics to maximize delivery probability and minimize delay, respectively, with a fixed number of copies and within a given time-to-live. We implement and evaluate OOF and OOF- as well as several other representative forwarding protocols, i.e., Epidemic, Spray-and-wait, MaxProp* and Delegation. We perform trace-driven simulations using both real and synthetic traces. Simulation results show that, in the traces where nodes have regular intermeeting times, the delivery rates of OOF and OOF- can be 30 percent greater than the compared routing protocols.

In sparse mobile social networks, the moving activity of nodes always happen in a specific area, which corresponds to some specific community. How to guarantee the higher packet delivery ratio while reducing forwarding delay in such networks, is a challenging issue and has not been widely investigated yet. Recently, additional super-node was introduced to ferry packets between the isolated areas. However, most existing solutions assume the super-node is always moving according to the fixed trajectory. In this paper, we put some special mobile nodes in the networks, they are called postmen, and their responsibility is to carry packets for normal nodes which belong to specific communities. Our work focus on the optimization of the moving trajectory by considering the minimum transmission delay. We formulate the optimal issue into semi-Markov Decision Process model. The decision process includes two parts: Packets-choosing strategy and trajectory of packet-ferrying-determination strategy. By maximizing the individual reward of a postman, its optimal trajectory will be found. Furthermore, the proposed solution guarantees the packet delivery ratio and delay for isolated communities. Simulation results show that the proposed packet-ferrying solution outperforms two existing ferrying solutions in terms of packet delivery ratio.

In traditional delay tolerant networks (DTNs), there exists a potential assumption that the nodes are willing to help others for packet forwarding. However, in the real application scenarios, such as civilian DTNs, selfish behaviors always widely exist. Therefore, the assumption that nodes are cooperative is not realistic in all applications. Currently, most of the existing incentive mechanism focuses on individual selfish behaviors. Few research work is proposed on social selfish behavior in DTNs. In this paper, we stimulate the nodes to cooperate with others by using a virtual bank mechanism. This incentive mechanism can effectively avoid individual selfish behaviors. Meanwhile, we observe that under this individual selfish incentive mechanism, the social distribution is unfair. That means the poverty nodes would appear in the networks, and become the internal threats for the social DTNs. To avoid this, we introduce the Gini coefficient to measure the inequality of the social distribution. Furthermore, by using the taxation strategy, we avoid the internal threats caused by social selfishness. To demonstrate the selfish behavior, we introduce the forwarding protocol which is based on social relations of nodes. We verify the proposed methods using simulation evaluations.

Deep packet inspection (DPI), based on regular expressions, is expressive, compact, and efficient in specifying attack signatures. We focus on their implementations based on general-purpose processors that are cost-effective and flexible to update. In this paper, we propose a novel solution, called deterministic finite automata with extended character-set (DFA/EC), which can significantly decrease the number of states through slightly extending the character-set. Different from existing state reduction algorithms, our solution requires only a single memory access for each byte in the traffic payload, which is the minimum. We perform experiments with the Snort rule-sets. Results show that, compared to DFA, a DFA/EC can be over four orders of magnitude smaller, has smaller memory bandwidth, and runs faster. We believe that DFA/EC will lay a groundwork for a new type of state compression technique in fast packet inspection.

One of the extensively studied coverage models in wireless sensor networks is barrier coverage, which guarantees that any movement crossing the given belt must be detected, while the direction of the movement is not required. For some intrusion detection applications, it may be the case that only one direction of crossing (the belt) is illegal such as border guarding. Therefore, we introduce a new coverage model called one-way barrier coverage, which requires that the network reports illegal intruders while ignores legal intruders. We propose an appropriate definition for one-way barrier coverage. We deeply investigate one-way barrier coverage with binary sensors. Our research illustrates that it is not straightforward to provide oneway barrier coverage even though there is only one intruder. When there are multiple intruders, we introduce the concept of neighboring barriers and design different protocols to provide one-way barrier coverage for different sensor models based on neighboring barriers.

A key challenge of routing in delay-tolerant networks (DTNs) is finding routes that have high delivery rates and low end-to-end delays. When future connectivity information is not available, opportunistic routing is preferred in DTNs, in which messages are forwarded to nodes with higher delivery probabilities. We observe that real objects have repetitive motions, whereas no prior research work has investigated the time-varying delivery probabilities of messages between nodes at different times during a repetition of motion of the nodes. We propose to use the expected minimum delay (EMD) as a new delivery probability metric in DTNs with repetitive but nondeterministic mobility. First, we model the network as a probabilistic time-space graph with historical contact information or prior knowledge about the network. We then translate it into a probabilistic state-space graph, in which the time dimension is removed. With the state-space graph, we apply the Markov decision process to derive the EMDs of the messages. We propose an EMD-based probabilistic routing protocol, called routing in cyclic MobiSpace (RCM). To make RCM more practical, we show a simple extension that reduces routing information exchanged among nodes. We perform simulations with real and synthetic traces. Simulation results show that RCM outperforms several existing opportunistic routing protocols.

Conventional routing algorithms in mobile ad hoc networks (MANETs), i.e., multi-hop forwarding, assume the existence of contemporaneous source-destination paths and are not scalable to large networks. On the other hand, in delay tolerant networks (DTNs), routing protocols use the mobility- assisted, store-carry-forward paradigm which allows delivery among disconnected network components. Adaptive routing, which combines multi-hop and mobility-assisted routing protocols, is of practical value: it allows efficient multi-hop forwarding while providing the flexibility to deliver messages among disconnected network components. However, existing adaptive routing protocols use mobility-assisted routing protocols as an alternative only when the former fails. In this paper, we propose to improve the performance of adaptive routing from a resource allocation point of view, in situations where bandwidth is a critical and limited resource affecting routing performance. We propose an adaptive routing protocol, named efficient adaptive routing (EAR), which allocates bandwidth (or forwarding opportunities) between its multi-hop forwarding component and its mobility-assisted routing component dynamically to improve bandwidth utility. Simulations are conducted to evaluate the routing performance of EAR under different network parameters.

Efficient geometric routing algorithms have been studied extensively in two-dimensional ad hoc networks, or simply 2D networks. These algorithms are efficient and they have been proven to be the worst-case optimal, localized routing algorithms. However, few prior works have focused on efficient geometric routing in 3D networks due to the lack of an efficient method to limit the search once the greedy routing algorithm encounters a local-minimum, like face routing in 2D networks. In this paper, we tackle the problem of efficient geometric routing in 3D networks. We propose routing on hulls, a 3D analogue to face routing, and present the first 3D partial unit Delaunay triangulation (PUDT) algorithm to divide the entire network space into a number of closed subspaces. The proposed greedy- hull-greedy (GHG) routing is efficient because it bounds the local- minimum recovery process from the whole network to the surface structure (hull) of only one of the subspaces.

A key challenge of message forwarding in delay tolerant networks (DTNs) is to increase delivery rate and decrease delay and cost. When information for future connectivity is not available, opportunistic routing is preferred in DTNs in which messages are forwarded opportunistic (non-deterministically) to nodes with higher delivery probabilities. Many real objects have non-deterministic but cyclic motions; however, few prior research work has investigated a multi-copy opportunistic message forwarding algorithm for DTNs with cyclic mobility patterns. Cyclic MobiSpace is a generalization of DTNs with cyclic mobility patterns. In this paper, we propose an optimal opportunistic multi-copy message forwarding algorithm in Cyclic MobiSpace. Specifically, we model a Cyclic MobiSpace as a state-space graph, and apply the optimal stopping rule to derive a delivery metric for each message state using the state-space graph. We perform simulations to compare our protocol, called Multi-copy Forwarding in Cyclic MobiSpace (MFC), against existing forwarding protocols using UMassDieselNet trace. Simulation results show that MFC delivers up to 100% more messages than the compared forwarding protocols under the same delay and forwarding cost.

Due to uncertainty in nodal mobility, DTN routing usually employs multi-copy forwarding schemes. To avoid the cost associated with flooding, much effort has been focused on probabilistic forwarding, which aims to reduce the cost of forwarding while retaining a high performance rate by forwarding messages only to nodes that have high delivery probabilities. This paper aims to provide an optimal forwarding protocol which maximizes the expected delivery rate while satisfying a certain constant on the number of forwardings per message. In our proposed optimal probabilistic forwarding (OPF) protocol, we use an optimal probabilistic forwarding metric derived by modeling each forwarding as an optimal stopping rule problem. We also present several extensions to allow OPF to use only partial routing information and work with other probabilistic forwarding schemes such as ticket-based forwarding. We implement OPF and several other protocols and perform trace-driven simulations. Simulation results show that the delivery rate of OPF is only 5% lower than epidemic, and 20% greater than the state-of-the-art delegation forwarding while generating 5% more copies and 5% longer delay.

Routing is the foremost issue in mobile ad hoc networks (MANETs). To guarantee delivery and improve performance, most position-based routing protocols, e.g., greedy-face-greedy (GFG), forward a message in greedy routing mode until the message is forwarded to a local minimum where greedy forwarding is impossible. They then switch to a less efficient mode known as face routing. Face routing requires the underlying network to be a planar graph which makes geometric routing only theoretically feasible. To remove this constraint, this paper tackles the local minimum problem with two new methods. First, we construct a virtual small-world network by adding virtual long links to the network to reduce the number of local minima. Second, we use the virtual force method to recover from local minima without relying on face routing. Combining these two methods, we propose a purely greedy routing protocol, the small-world iterative navigation greedy (SWING+) routing protocol. Simulations are conducted to evaluate SWING+ against existing geometric routing protocols. Simulation results show that SWING+ guarantees delivery, and that its performance is comparable to that of the state-of-the-art greedy other adaptive face routing (GOAFR+) routing protocol.

The nonexistence of an end-to-end path poses a challenge in adapting traditional routing algorithms to delay-tolerant networks (DTNs). Previous works have covered centralized routing approaches based on deterministic mobility, ferry-based routing with deterministic or semideterministic mobility, flooding-based approaches for networks with general mobility, and probability-based routing for semideterministic mobility models. Unfortunately, none of these methods can guarantee both scalability and delivery. In this paper, we extend the investigation of scalable deterministic routing in DTNs with repetitive mobility based on our previous works. Instead of routing with global contact knowledge, we propose a routing algorithm that routes on contact information compressed by three combined methods. We address the challenge of efficient information aggregation and compression in the time-space domain while maintaining critical information for efficient routing. Then, we extend it to handle a moderate level of uncertainty in contact prediction. Analytical studies and simulation results show that the performance of our proposed routing algorithm, DTN hierarchical routing (DHR), is comparable to that of the optimal time-space Dijkstra algorithm in terms of delay and hop count. At the same time, the per-node storage overhead is substantially reduced and becomes scalable.

A key challenge of routing in delay tolerant networks (DTNs) is finding routes that have high delivery rates and low end-to-end delays. When oracles are not available for future connectivity, opportunistic routing is preferred in DTNs, in which messages are forwarded to nodes with higher delivery probabilities. We observe that real objects have repetitive motions, but no prior research work has investigated the cyclic delivery probability of messages between nodes. In this paper, we propose to use the expected minimum delay (EMD) as a new delivery probability metric in DTNs with repetitive but non-deterministic mobility. Specifically, we model the network as a probabilistic time-space graph with historical contact information or prior knowledge about the network. We then translate it into a probabilistic state-space graph in which the time dimension is removed. Finally, we apply the Markov decision process to derive the EMDs of the messages at particular times. Our proposed EMD-based routing protocol, called routing in cyclic MobiSpace (RCM), outperforms several existing opportunistic routing protocols when simulated using both real and synthetic traces.

Routing is the foremost issue in mobile ad hoc networks (MANETs) and sensor networks. To guarantee delivery and improve performance, most position-based routing protocols are based on face routing, which requires the underlying network to be a planar graph. Localized planar graph construction requires the radio model to be a unit disk graph and it is only applicable to two-dimensional networks. This paper presents an efficient force-based geometric routing algorithm which is applicable to general network models and has a worst-case bound for arbitrary three-dimensional networks.

Dynamic ad hoc networks are mobile ad hoc networks (MANETs) where network characteristics, such as network density and node mobility, change significantly over time and space. Sometimes, dynamic ad hoc networks resemble a dense ad hoc network. At other times, they resemble a delay tolerant network. Many real networks follow the paradigm of dynamic ad hoc networks. Military networks, wildlife tracking sensor networks, and vehicle networks are some of these examples. In dynamic ad hoc networks, conventional routing schemes fail when the network characteristics do not fall into their applicable scenarios. Previous research has proposed a variety of routing schemes for each specific network scenario. For instance, distributed routing tables are built for efficient multi-hop, single- copy routing in static and dense networks. Mobility assisted, multi-copy routings are proposed in sparse networks where contemporary paths might not exist. With the advantages of the existing schemes in mind, we introduce a new routing scheme, Adaptive ROuting in Dynamic ad hoc networks (AROD), which is a seamless integration of several existing schemes. Simulation results show that AROD is highly scalable and is adaptive to different network scenarios.

Geometric routing in mobile ad-hoc networks (MANETs) is comprised of two forwarding modes: greedy forwarding and face forwarding. It is known that face forwarding is inefficient and fails frequently in practical situations. A previous work, NEAR [2], avoids switching to face forwarding by predicting local minima and not forwarding messages to them. However, NEAR predicts excessive local minima, which results in subop- timal routing performance. Also, it is not fully localized due to its bridge detection scheme. Aiming to further improve the performance, we propose a destination- region-based Local minimum AwaRe GEometric Routing (LARGER) algorithm which improves the accuracy of the local minima prediction by dividing the network into a number of regions and predicting local minima based on the region where the destination is located. Simulation results show that LARGER substantially improves the prediction accuracy and the routing performance of NEAR and that of the other state-of-the-art geometric routing algorithms in terms of route length.

The non-existence of an end-to-end path poses a challenge inadapting the traditional routing algorithms to delay tolerantnetworks (DTNs). Previous works include centralized rout-ing approaches based on deterministic mobility, ferry-basedrouting with deterministic or semi-deterministic mobility, flooding-based approaches for networks with general mobility, and probability-based routing for semi-deterministicmobility models. Unfortunately, none of these methods canguarantee both scalability and delivery. In this work, we investigate scalable deterministic routing in DTNs. Instead of routing with global contact knowledge, we propose a simplified DTN model and a routing algorithm which routes on contact information compressed by three combined methods. Analytical studies and simulation results show that the performance of our proposed routing algorithm, DTN Hierarchical Routing (DHR), approximates that of the optimal time-space Dijkstra's algorithm in terms of delay and hop-count. At the same time, the per node storage overhead is substantially reduced and becomes scalable. Although our work is based on a simplified DTN model, we believe this approach will lay a groundwork for the understanding of scalable routing in DTNs.

Routing is the foremost issue in mobile ad hoc networks (MANETs). In a wireless environment characterized by small bandwidth and limited computation resources, position- based routing is attractive because it requires little communication and storage overhead. To guarantee delivery and improve performance, most position-based routing protocols, e.g. GFG, forward a message in greedy mode until the message is forwarded to a node that has no neighbor closer to the destination. They then switch to a less efficient mode. Face routing, where the message is forwarded along the perimeter of the void, is one example. This paper tackles the void problem from a different angle. We construct a virtual small world network by adding virtual long links to reduce the chance of a protocol encountering local minima in greedy mode, and thus decrease the chance to invoke inefficient methods. Experiments show that this method effectively improves the performance of the greedy-face combinations in terms of average hop count.

Routing is the foremost issue in mobile ad hoc networks (MANETs). In a wireless environment characterized by small bandwidth and limited computational resources, position-based routing is attractive because it requires little communication and storage overhead. To guarantee delivery and improve performance, most position-based routing protocols, e.g. GFG, forward a message in greedy mode until the message is forwarded to a node that has no neighbor closer to the destination, which is called a local minimum. They then switch to a less efficient mode. Face routing, where the message is forwarded along the perimeter of the void, is one example. This paper tackles the void problem with two new methods. First, we construct a virtual small world network by adding virtual long links to the network to reduce the chance of a protocol encountering local minima in greedy mode, and thus decrease the chance to invoke inefficient methods. Second, we use the virtual force method to recover from local minima without relying on face routing. We combine these two methods to be our new purely greedy routing protocol SWING. Simulation shows that SWING finds shorter routes than the state of art geometric routing protocol GOAFR, though with a longer route establishment time. More importantly, SWING is purely greedy which works even if position information is inaccurate, also it can be directly applied to the 3D MANET models. A theoretical proof that it guarantees delivery is given.