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.

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.

Abstract—With fast-growing consumer demands and rapidly-developing mobile technologies, portable mobile devices are becoming a necessity of our daily lives. However, existing mobile devices rely on the wireless infrastructure to access Internet services provided by central application providers. This architecture is inefficient in many situations and also does not utilize abundant inter-device communication opportunities in many scenarios. This paper proposes the human network (HUNET), a network architecture that enables information sharing between mobile devices through direct inter-device communication. We design B-SUB, an interest-driven information sharing system for HUNETs. In B-SUB, content and user interests are described by tags, which are human-readable strings that are designated by users. An experiment is performed to demonstrate the effectiveness of this tag-based content description method. To facilitate efficient data dissemination, we invent the Temporal Counting Bloom filter (TCBF) to encode tags, which also reduces the overhead of content routing. Comprehensive theoretical analyses on the parameter tuning of B-SUB are presented and verify B-SUB’s ability to work efficiently under various network conditions. We then extend B-SUB’s routing scheme to provide a stronger privacy guarantee. Extensive real-world trace-driven simulations are performed to evaluate the performance of B-SUB, and the results demonstrate its efficiency and usefulness. Index Terms—Content based publish/subscribe, interest-driven information sharing, human network, Bloom filter. 1

The buzz-word big-data (application) refers to the large-scale distributed applications that work on unprecedentedly large data sets. Google's MapReduce framework and Apache's Hadoop, its open-source implementation, are the defacto software system for big-data applications. An observation regarding these applications is that they generate a large amount of intermediate data, and these abundant information is thrown away after the processing finish. Motivated by this observation, we propose a data-aware cache framework for big-data applications, which is called Dache. In Dache, tasks submit their intermediate results to the cache manager. A task, before initiating its execution, queries the cache manager for potential matched processing results, which could accelerate its execution or even completely saves the execution. A novel cache description scheme and a cache request and reply protocol are designed. We implement Dache by extending the relevant components of the Hadoop project. Testbed experiment results demonstrate that Dache significantly improves the completion time of MapReduce jobs and saves a significant chunk of CPU execution time.

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.

Wireless Sensor Networks (WSNs) are key for various applications that involve long-term and low-cost monitoring and actuating. In these applications, sensor nodes use batteries as the sole energy source. Therefore, energy efficiency becomes critical. We observe that many WSN applications require redundant sensor nodes to achieve fault tolerance and Quality of Service (QoS) of the sensing. However, the same redundancy may not be necessary for multihop communication because of the light traffic load and the stable wireless links. In this paper, we present a novel sleep-scheduling technique called Virtual Backbone Scheduling (VBS). VBS is designed for WSNs has redundant sensor nodes. VBS forms multiple overlapped backbones which work alternatively to prolong the network lifetime. In VBS, traffic is only forwarded by backbone sensor nodes, and the rest of the sensor nodes turn off their radios to save energy. The rotation of multiple backbones makes sure that the energy consumption of all sensor nodes is balanced, which fully utilizes the energy and achieves a longer network lifetime compared to the existing techniques. The scheduling problem of VBS is formulated as the Maximum Lifetime Backbone Scheduling (MLBS) problem. Since the MLBS problem is NP-hard, we propose approximation algorithms based on the Schedule Transition Graph (STG) and Virtual Scheduling Graph (VSG). We also present an Iterative Local Replacement (ILR) scheme as a distributed implementation. Theoretical analyses and simulation studies verify that VBS is superior to the existing techniques.

The wide use of mobile devices gives rise to many novel network applications, which require an efficient communication substrate. These networks, which are comprised solely of human-carried mobile devices, are called human networks (HUNETs). In this paper, we present ZigZag, a content-based publish/subscribe (CBPS) architecture for HUNETs. We deem that CBPS is a natural fit for HUNETs for its inherent anonymity, scalability, and flexibility. However, existing CBPS systems are designed for the Internet, consuming resources beyond the capacity of mobile devices. Additionally, they do not consider user mobility. To address these restrictions, ZigZag employs a transformation-based subscription representation and processing technique, and a Bloom-filter-based message routing and forwarding scheme. The advantages of ZigZag are its low subscription storage consumption and matching complexity. Analytic and simulation results prove that our proposed methods are flexible and more efficient than existing techniques.

Event matching is a critical component of large-scale content-based publish/subscribe systems. However, most existing methods suffer from a dramatic performance degradation when the system scales up. In this paper, we present TAMA (Table Match), a highly efficient content-based event matching and forwarding engine. We consider range-based attribute constraints that are widely used in real-world applications. TAMA employs approximate matching to provide fast event matching against an enormous amount of subscriptions. To this end, TAMA uses a hierarchical indexing table to store subscriptions. Event matching in TAMA becomes the query to this table, which is substantially faster than traditional methods. In addition, the false positive rate of matching events in TAMA can be adjusted by tuning the size of the matching table, which makes TAMA favorable in practice. We implement TAMA as a forwarding component in Siena and conduct extensive experiments with realistic settings. The results demonstrate that TAMA has a significantly faster event matching speed compared to existing methods, and only incurs a small fraction of false positives.

Content-based publish/subscribe overlay is gaining popularity in large-scale content distribution applications for its flexibility and anonymity. Since such overlays are built on top of diverse infrastructures, minimizing the cost of using bandwidth in the overlays is a complicated task. In this paper, we tackle this task using a combinatorial optimization approach. We assume that each user can simultaneously be publisher and subscriber, and brokers are dedicated servers. We first formulate a two-stage optimization problem, which captures the cost of routing traffic in different parts of the overlay. Our solution is obtained by separately approximating the problem of each stage and then combining the results of sub-problems. In order to achieve better results, we further propose a novel formulation based on sub-channeling and Steiner tree/star problem, which simplifies the analysis of content-based routing and facilitate an intuitive randomized approximation algorithm. This algorithm is then translated into a decentralized one that dynamically adjusts the overlay connections when the network undergoes dynamisms. Simulation results demonstrate that our algorithms substantially reduce the cost of constructing content-based publish/subscribe overlay.

This paper studies the sleep scheduling problem for large scale wireless sensor networks (WSNs), which have hundreds to thousands of sensors. Sensors are extremely sensitive to energy consumption because they are powered by batteries. In this paper, we propose stochastic sleep scheduling, a generic duty- cycling scheduling method based on stochastic theory. It lets each sensor fall asleep based on certain stochastic processes. This strategy requires no clock synchronization, and a little coordination amongst sensors. In order to characterize this design, we analyze its end-to-end communication delay and energy consumption using stochastic methods. According to the analysis, this method actually has a reasonably small delay due to the redundancy in WSNs. Simulation studies are used to verify the analytical results. We also apply stochastic sleep scheduling to S-MAC, a state-of- the-art duty-cycled sensor MAC protocol. Simulation results verify the energy consumption of the new MAC protocol.

The adoption of portable wireless devices is rapidly rising. The demand for efficient communication protocols amongst these devices is pressing. In this paper, we present a content-based publish-subscribe system, called B-SUB Bloom filter-based pub-SUB system), for the networks formed by human-carried wireless devices, which are called human networks (HUNETs). A novel data structure, called Temporal Counting Bloom Filter (TCBF), is proposed to perform content based networking tasks. The TCBF's novelty is that it is able to handle temporal operations, which are not supported in the classic Bloom filter (BF) and are crucial to the success of forwarding messages in HUNETs. B-SUB uses TCBFs to encode users' interests and embed routing information. Using the TCBF, B-SUB can propagate interests by transmitting at most two TCBFs of dozens of bytes, which makes B-SUB space efficient. B-SUB makes forwarding decisions through querying the TCBFs, which is simple and fast. These designs make B-SUB pretty suitable for resource-constrained HUNETs. However, the TCBF has false positives, which will potentially cause useless messages to be injected into the network. The issue that arises here is how to handle its false positives in queries, and at the same time maintain its spatial efficiency as well. So, we analyze several methods for controlling the TCBF's false positive rate. B-SUB's viability and usefulness are verified through extensive simulation studies using real-world human contact traces.

Wireless sensor network (WSN) applications require redundant sensors to guarantee fault tolerance. However, the same degree of redundancy is not necessary for multi-hop communication. In this paper, we present a new scheduling method called virtual backbone scheduling (VBS). VBS employs heterogeneous scheduling, where backbone nodes work with duty-cycling to preserve network connectivity, and non-backbone nodes turn off radios to save energy. We formulate a maximum lifetime backbone scheduling (MLBS) problem to maximize the network lifetime using this scheduling model. Because the MLBS problem is NP-hard, two approximation solutions based on the schedule transition graph (STG) and virtual scheduling graph (VSG) are proposed.We also present an iterative local replacement (ILR) scheme as an distributed implementation of VBS. The path stretch problem is analyzed in order to explore the impact of VBS on the network structure. We show, through simulations, that VBS significantly prolongs the network lifetime under extensive conditions.

The development of modern communication technologies fosters human networks (HUNETs)-an information dissemination platform comprised of human-carried wireless-enabled devices. These networks are promising applications of delay tolerant networks (DTNs). However, existing DTN routing protocols do not address unique problems in HUNETs and are unable to utilize the benefits of human mobility. In this paper, we present a publish/subscribe system for HUNETs. In our system, brokers are responsible for collecting subscriptions and dispatching messages, which provide better flexibility and scalability. The core component of our system is a socially-aware broker allocation algorithm called, social election. Social election trades off between the efficiency and overhead, by dynamically controlling the number of brokers in the network. A replication scheme and a buffer management method based on utility are also proposed to facilitate efficient message forwarding. We demonstrate, through simulations, that our system performs well in realistic networks under extensive conditions.

Position-based routing protocols use location information to refine the traditional packet flooding method in mobile ad hoc networks. They mainly focus on densely and evenly distributed network scenarios, but their performances degrade quickly as networks become sparse. To overcome these shortcomings, we introduce the network density concept in the routing process, and propose a density adaptive routing protocol (DAR) to optimize the packet forwarding process. DAR algorithm utilizes the local network density to determine the packet forwarding zone; in dense areas, it narrows the forwarding range to reduce the total number of participants in flooding; in sparse area, it enlarges the forwarding scope to enclose enough nodes for packet relaying. Compared to the existing protocols, DAR yields lower flooding overhead and higher route discovery rate. Theoretical analysis proves that it works well in both densely and sparsely distributed network scenarios, and is more scalable than traditional routing protocols. Simulation results are presented in this paper to demonstrate the effectiveness of the proposed protocol.