Minimizing CO2 emissions in a practical daily carpooling problem

Governments, as well as companies and individuals, are increasingly aware of the damages to the environment caused by human activities. In this sense, the reduction of CO₂ emissions is an important topic that is pursued through a range of practices. A relevant example is carpooling, which is defined as the act of individuals sharing a single car. In this paper we approach a practical case found in an Italian service company. Our objective is to develop an integrated web application to be used by the employees of this company to organize carpooling crews on a daily basis, so as to reach a common destination. We look for possible crews by the use of mathematical formulations and heuristic algorithms. The heuristic algorithms are then embedded into the web application to provide users with carpooling solutions. Experimental results attest for a great potential in CO₂ savings by the use of carpooling in the real-world scenario as well as in newly generated instances.     

Virtual indexing based methods for estimating node connection degrees

It is difficult to accurately measure node connection degrees for a high speed network, since there is a massive amount of traffic to be processed. In this paper, we present a new virtual indexing method for estimating node connection degrees for high speed links. It is based on the virtual connection degree sketch (VCDS) where a compact sketch of network traffic is built by generating multiple virtual bitmaps for each network node. Each virtual bitmap consists of a fixed number of bits selected randomly from a shared bit array by a new method for recording the traffic flows of the corresponding node. The shared bit array is efficiently utilized by all nodes since every bit is shared by the virtual bitmaps of multiple nodes. To reduce the “noise” contaminated in a node’s virtual bitmaps due to sharing, we propose a new method to generate the “filtered” bitmap used to estimate node connection degree. Furthermore, we apply VCDS to detect super nodes often associated with traffic anomalies. Since VCDS need a large amount of extra memory to store node addresses, we also propose a new data structure, the reversible virtual connection degree sketch, which identifies super node addresses analytically without the need of extra memory space but at a small increase in estimation error. Furthermore we combine the VCDS and RVCDS based methods with a uniform flow sampling technique to reduce memory complexities. Experiments are performed based on the actual network traffic and testing results show that the new methods are more memory efficient and more accurate than existing methods.     

A lightweight soft-state tracking framework for dense mobile ad hoc networks

In a mobile ad hoc network, tracking protocols need to deal with–in addition to the mobility of the target–the mobility of the intermediate nodes that maintain a track toward the target. To address this problem, we propose the MDQT (Mobility-enhanced Distributed QuadTree) tracking framework. MDQT employs a static cell abstraction to mask the mobility of the nodes and provide the illusion of a logical static network overlaid on the mobile network. MDQT implements this virtual static network layer in a lightweight/communication-free manner by exploiting the soft-state principle and the snooping feature of wireless communication.Through simulation, we study the impacts of the mobile node percentage and target mobility speed on the system performance. Simulation results show that the success rate of tracking is mostly unaffected by the speed of mobile nodes, but degrades slightly with the increases in mobile node percentage. On the other hand, the cost measurements (latency, average hops, and retry rate) are more sensitive to the mobility speed, and remain unaffected by the increase of mobile node percentage—owing to our soft-state design approach. We find that even at very high mobility speeds (50 m/s), low update rates (1 update per second), and 100% node mobility, the success rate of MDQT tracking is above 85% and the latency is comparable with that of static networks.     

Utilizing correlated node mobility for efficient DTN routing

In a delay tolerant network (DTN), nodes are connected intermittently and the future node connections are mostly not known. Therefore, effective forwarding based on limited knowledge of contact behavior of nodes is challenging. Most of the previous studies assumed that mobility of a node is independent from mobility of other nodes and looked at only the pairwise node relations to decide routing. In contrast, in this paper, we analyze the temporal correlation between the meetings of each node with other nodes and utilize this correlation for efficient routing. We introduce a new metric called conditional intermeeting time (CIT), which computes the average intermeeting time between two nodes relative to a meeting with a third node. Then, we modify existing DTN routing protocols using the proposed metric to improve their performance. Extensive simulations based on real and synthetic DTN traces show that the modified algorithms perform better than the original ones.     

Minimum disruption service composition and recovery in mobile ad hoc networks

The dynamic nature of mobile ad hoc networks poses fundamental challenges to the design of service composition schemes that can satisfy the end-to-end quality of service requirements and minimize the effect of service disruptions caused by dynamic link and node failures. Although existing research on mobile ad hoc networks has focused on improving reliability, little existing work has considered service deliveries spanning multiple components. Moreover, service composition strategies proposed for wireline networks (such as the Internet) are poorly suited for highly dynamic wireless ad hoc networks.This paper proposes a new service composition and recovery framework designed to achieve minimum service disruptions for mobile ad hoc networks. The framework consists of two tiers: service routing, which selects the service components that support the service path, and network routing, which finds the optimal network path that connects these service components. Our framework is based on the disruption index, which is a novel concept that characterizes different service disruption aspects, such as frequency and duration, that are not captured adequately by conventional metrics, such as reliability and availability.Using the definition of disruption index, we formulate the problem of minimum-disruption service composition and recovery (MDSCR) as a dynamic programming problem and analyze the properties of its optimal solution for ad hoc networks with known mobility plan. Based on the derived analytical insights, we present our MDSCR heuristic algorithm for ad hoc networks with uncertain node mobility. This heuristic algorithm approximates the optimal solution with one-step lookahead prediction, where service link lifetime is predicted based on node location and velocity using linear regression. We use simulations to evaluate the results of our algorithm in various network environments. The results validate that our algorithm can achieve better performance than conventional methods.     

Viral marketing for dedicated customers

Viral marketing has attracted considerable concerns in recent years due to its novel idea of leveraging the social network to propagate the awareness of products. Specifically, viral marketing first targets a limited number of users (seeds) in the social network by providing incentives, and these targeted users would then initiate the process of awareness spread by propagating the information to their friends via their social relationships. Extensive studies have been conducted for maximizing the awareness spread given the number of seeds (the Influence Maximization problem). However, all of them fail to consider the common scenario of viral marketing where companies hope to use as few seeds as possible yet influencing at least a certain number of users. In this paper, we propose a new problem, called J-MIN-Seed, whose objective is to minimize the number of seeds while at least J users are influenced. J-MIN-Seed, unfortunately, is NP-hard. Therefore, we develop an approximate algorithm which can provide error guarantees for J-MIN-Seed. We also observe that all existing studies on viral marketing assume that all users in the social network are of interest for the product being promoted (i.e., all users are potential consumers of the product), which, however, is not always true. Motivated by this phenomenon, we propose a new paradigm of viral marketing where the company can specify which types of users in the social network are of interest when promoting a specific product. Under this new paradigm, we re-define our J-MIN-Seed problem as well as the Influence Maximization problem and design some algorithms with provable error guarantees for the new problems. We conducted extensive experiments on real social networks which verified the effectiveness of our algorithms.     

Fast distributed dominating set based routing in large scale MANETs

Hierarchical routing techniques have long been known to increase network scalability by constructing a virtual backbone. Even though MANETs have no physical backbone, a virtual backbone can be constructed by finding a connected dominating set (CDS) in the network graph. Many centralized as well as distributed algorithms have been designed to find a CDS in a graph (network). Theoretically, any centralized algorithm can be implemented in a distributed fashion, with the tradeoff of higher protocol overhead. Because centralized approaches do not scale well and because distributed approaches are more practical especially in MANETs, we propose a fast distributed connected dominating set (FDDS) construction in MANETs. FDDS has message and time complexity of O(n) and O(Δ²), where n is the number of nodes in the network and Δ is the maximum node degree. According to our knowledge, FDDS achieves the best message and time complexity combinations among the previously suggested approaches. Moreover, FDDS constructs a reliable virtual backbone that takes into account (1) node’s limited energy, (2) node’s mobility, and (3) node’s traffic pattern. Our simulation study shows that FDDS achieves a very low network stretch. Also, when the network size is large, FDDS constructs a backbone with size smaller than other well known schemes found in the literature.     

长期车辆合乘问题的复合变邻域搜索算法

针对于长期车辆合乘问题（LTCPP）,提出一种复合变邻域搜索算法（HVNSA）,将具有相同目的地的用户进行合乘匹配从而减少车辆出行数量。首先,构建一个全面准确的长期车辆合乘问题的数学模型,将所有用户按复合距离优先算法分配到合乘小组中,对时间窗口和车容量约束验证,得到初始合乘方案;然后利用变邻域搜索算法对初始合乘方案进行优化迭代,得到最终的优化合乘方案。实验结果表明,该算法在处理100人和200人的规模问题上可以在1 s内得到高质量的优化合乘方案,对于400人和1000人的较大规模问题,该算法仍然可以在2~4 s内得到较高质量的优化合乘方案。     

Detecting Communities in <Emphasis Type="Italic">K</Emphasis>-Partite <Emphasis Type="Italic">K</Emphasis>-Uniform (Hyper)Networks

In social tagging systems such as Delicious and Flickr,users collaboratively manage tags to annotate resources.Naturally,a social tagging system can be modeled as a (user,tag,resource) hypernetwork,where there are three different types of nodes,namely users,resources and tags,and each hyperedge has three end nodes,connecting a user,a resource and a tag that the user employs to annotate the resource.Then how can we automatically cluster related users,resources and tags,respectively? This is a problem of community detection in a 3-partite,3-uniform hypernetwork.More generally,given a K-partite K-uniform (hyper)network,where each (hyper)edge is a K-tuple composed of nodes of K different types,how can we automatically detect communities for nodes of different types? In this paper,by turning this problem into a problem of finding an efficient compression of the (hyper)network’s structure,we propose a quality function for measuring the goodness of partitions of a K-partite K-uniform (hyper)network into communities,and develop a fast community detection method based on optimization.Our method overcomes the limitations of state of the art techniques and has several desired properties such as comprehensive,parameter-free,and scalable.We compare our method with existing methods in both synthetic and real-world datasets.     

Cored-Based Tree with Forwarding Regions (CBT-FR); A Protocol for Reliable Multicasting in Mobile Ad Hoc Networks

In this paper we propose a new protocol for reliable multicast in a multihop mobile radio network. The protocol is reliable, i.e., it guarantees message delivery to all multicast nodes even when the topology of the network changes during multicasting. The proposed protocol uses a core-based shared tree. The multicast tree may get fragmented due to node movements. The notion of a forwarding region is introduced which is used to glue together fragments of multicast trees. The gluing process involves flooding the forwarding region of only those nodes that witness topology change due to node mobility. Delivery of multicast messages to mobile nodes is expedited through (i) pushing the message by witness nodes in their forwarding regions and (ii) pulling messages by a mobile node during (re)joining process. Hence, the protocol conserves network bandwidth by using a combination of the push–pull approach and by restricting flooding only to the essential parts of the network that are affected by topology change.  We develop a theoretical model to compute the probability of packet loss (as a function of the mobility rate) for our proposed scheme compared to the the core-based tree protocol (CBT); we also evaluate the effectiveness of forwarding regions as compared to traditional flooding. Our analysis shows that the proposed scheme significantly outperforms CBT.     

Understanding Skout users’ mobility patterns on a global scale: a data-driven study

Location-based social apps, such as Skout, have been widely used by millions of users for sharing their location information. In this work, we collected all the location information published by over 1.2 million Skout users during December 2012 and June 2016. Based on the collected information, we model the inter-city mobility of Skout users with a global city network, and analyze the evolution of the network based on its structural characteristics. Moreover, we look into Skout users’ mobility patterns by discovering the most popular inter-city routes, destinations, and tightly connected city groups, and analyze the impact on the mobility patterns from geographical distances, languages and cultures. Finally, we leverage machine learning techniques to build a model for identifying the most influential cities in the world according to the Skout data. The results are able to assist individuals, governors and business leaders in making better decisions regarding traveling, immigrating, measuring city improvements and cooperation with cities.

     

基于行车位置数据挖掘的拼车方法研究

拼车是一种环保节能的出行方式,合理的拼车策略可以缓解交通压力,优化乘客体验,减少碳排放等。针对拼车问题,提出了两阶段的拼车匹配策略。第一阶段匹配过程是利用基于改进Hausdorff距离的乘客分配算法,将拼车需求分配到具体车辆,从而将多车辆问题转化为单车辆问题;第二阶段匹配过程,采用基于匹配度的聚类筛选出与车辆最为匹配的拼车需求。实验结果表明该算法和流程能分别应用于单车次、多车次接力换乘的拼车方案推荐,匹配简单准确。     

Ad hoc node connectivity improvement analysis – Why not through mesh clients?

A mobile ad-hoc network (MANET) is a complex distributed system with unpredictable node movements, which results in frequent node disconnectivity. In a MANET, each node works independently, using the resources based on individual need. The main problem with this arises during the movement of the nodes and random utilization of network resources. This work attempts to solve the mobility maintenance issues using three mesh structures; (i) mesh tree (M_T), (ii) mesh backbone (M_B) and (iii) mesh cluster (M_C). The mobility maintenance architectures are formed based on a localized connectivity analysis and the node degree as a key parameter for network construction. The performance of the proposed work is analysed through mathematical models and simulation results.     

A web personalizing technique using adaptive data structures: The case of bursts in web visits

The explosive growth in the size and use of the World Wide Web continuously creates new great challenges and needs. The need for predicting the users’ preferences in order to expedite and improve the browsing though a site can be achieved through personalizing of the Websites. Recommendation and personalization algorithms aim at suggesting WebPages to users based on their current visit and past users’ navigational patterns. The problem that we address is the case where few WebPages become very popular for short periods of time and are accessed very frequently in a limited temporal space. Our aim is to deal with these bursts of visits and suggest these highly accessed pages to the future users that have common interests. Hence, in this paper, we propose a new web personalization technique, based on advanced data structures.The data structures that are used are the Splay tree (1) and Binary heaps (2). We describe the architecture of the technique, analyze the time and space complexity and prove its performance. In addition, we compare both theoretically and experimentally the proposed technique to another approach to verify its efficiency. Our solution achieves O(P²) space complexity and runs in k log P time, where k is the number of pages and P the number of categories of WebPages.     

Beyond the separation of identifier and locator: Building an identity-based overlay network architecture for the Future Internet

The Internet is continuously evolving from a static, host-based, uniquely attached node model to a mobile, host-free node model with the possibility of multiple attachment points to the network. However, the current Internet was not designed to support this type of workload because of its strict addressing mechanism. Thus, the Future Internet promotes the introduction of new architectures that provide the decoupling of identification and location. Moreover, new technologies, like cloud computing and Internet of Things, raise the necessity for a finer granularity of network nodes. Furthermore, the huge number of devices connected to the Internet and their finer granularity impose the necessity of flexible naming and, thus, integrated discovery mechanisms. In this paper we present an architecture that decouples the identification and location by using identities to identify the network nodes and moving from a host-to-host to a fine-grained process-to-process view of the network. Together with the mobility and multi-homing support, it also provides integrated discovery, flexible naming, and integrated security features. Finally, we analyze the architecture to discuss its performance and compare it with other (existing) approaches.     

How do we encourage an egoist to act socially in an ad hoc mobile network?

We consider a flow-based model for an ad hoc mobile network where users may need to use transit nodes in order to be able to communicate. Under the assumption that every node is willing to cooperate, we derive the set of Karush–Kuhn–Tucker equations that define the socially-optimal flows on each of the routes. We then look at the problem from an ‘egoist’ point of view, in which the user at node i cares only about maximising his/her utility under the constraint that the flows on routes which do not use node i are fixed at the socially-optimal value.This leads us to a consideration of extra constraints that could be introduced to induce the egoist user at node i to behave in a socially-optimal way. We show how to derive the parameters of such constraints, and give them interpretations in terms of schemes in which nodes’ transmission rates are constrained by the rates at which they accumulate ‘credit’.     

Who to follow recommendation in large-scale online development communities

ContextOpen source development allows a large number of people to reuse and contribute source code to the community. Social networking features open opportunities for information discovery, social collaborations, and improved recommendations of potential collaborators.ObjectiveOnline community and development platforms rely on social network features to increase awareness and attention among community members for improved collaborations. The objective of this work is to introduce an approach for recommending relevant users to follow. Follower networks provide means for informal information propagation. The efficiency and effectiveness of such information flows is impacted by the network structure. Here, we aim to understand the resilience of networks against random or strategic node removal.MethodSocial network features of online software development communities present a new opportunity to enhance online collaboration. Our approach is based on the automatic analysis of user behavior and network structure. The proposed ‘who to follow’ recommendation algorithm can be parametrized for specific contexts. Link-analysis techniques such as PageRank/HITS provide the basis for a novel ‘who to follow’ recommendation model.ResultsWe tested the approach using a GitHub-based dataset. Currently, users follow popular community members to get updates regarding their activities instead of maintaining personal relations. Thus, social network features require further improvements to increase reciprocity. The application of our ‘who to follow’ recommendation model using the GitHub dataset shows excellent results with respect to context-sensitive following recommendations. The sensitivity of GitHub’s follower network to random node removal is comparable with other social networks but more sensitive to follower authority based node removal.ConclusionLink-based algorithm can be used for context-sensitive ‘who to follow’ recommendations. GitHub is highly sensitive to authority based node removal. Information flow established through follower relations will be strongly impacted if many authorities are removed from the network. This underpins the importance of ‘central’ users and the validity of focusing the ‘who to follow’ recommendations on those users.     

Epidemic-based reliable and adaptive multicast for mobile ad hoc networks

An emerging approach to distributed systems exploits the self-organization, autonomy and robustness of biological epidemics. In this article, we propose a novel bio-inspired protocol: EraMobile (Epidemic-based Reliable and Adaptive Multicast for Mobile ad hoc networks). We also present extensive performance analysis results for it. EraMobile supports group applications that require high reliability. The protocol aims to deliver multicast data reliably with minimal network overhead, even under adverse network conditions. With an epidemic-based multicast method, it copes with dynamic and unpredictable topology changes due to mobility. Our epidemic mechanism does not require maintaining any tree- or mesh-like structure for multicasting. It requires neither a global nor a partial view of the network, nor does it require information about neighboring nodes and group members. In addition, it substantially lowers overhead by eliminating redundant data transmissions. Another distinguishing feature is its ability to adapt to varying node densities. This lets it deliver data reliably in both sparse networks (where network connectivity is prone to interruptions) and dense networks (where congestion is likely). We describe the working principles of the protocol and study its performance through comparative and extensive simulations in the ns-2 network simulator.     

An overview of anonymity technology usage

Anonymity technologies enable Internet users to maintain a level of privacy that prevents the collection of identifying information such as the IP address. Understanding the deployment of anonymity technologies on the Internet is important to analyze the current and future trends. In this paper, we provide a tutorial survey and a measurement study to understand the anonymity technology usage on the Internet from multiple perspectives and platforms. First, we review currently utilized anonymity technologies and assess their usage levels. For this, we cover deployed contemporary anonymity technologies including proxy servers, remailers, JAP, I2P, and Tor with the geo-location of deployed servers. Among these systems, proxy servers, Tor and I2P are actively used, while remailers and JAP have minimal usage. Then, we analyze application-level protocol usage and anonymity technology usage with different applications. For this, we preform a measurement study by collecting data from a Tor exit node, a P2P client, a large campus network, a departmental email server, and publicly available data on spam sources to assess the utilization of anonymizer technologies from various perspectives. Our results confirm previous findings regarding application usage and server geo-location distribution where certain countries utilize anonymity networks significantly more than others. Moreover, our application analysis reveals that Tor and proxy servers are used more than other anonymity techniques.     

Energy Optimization under Informed Mobility

Energy optimization is important in wireless ad hoc networks, where node battery power is usually limited. Research results show that such a network can exploit controlled node mobility to reduce communication-related energy consumption. However, node movement itself usually consumes energy. In this paper we study the energy optimization problem that accounts for energy costs associated with both communication and physical node movement. We refer to this model as informed mobility. We first review the theoretical foundations on how to reduce total communication energy consumption, as well as increase system lifetime, by combining node movement and transmission power adaptation. Next, we describe and analyze the informed mobility optimization problem. Based on this analysis, we introduce localized algorithms and protocols for informed mobility. We propose iMobif, a flow-based informed mobility framework that collects network information for mobility decision making. We demonstrate how to use iMobif to minimize total communication energy consumption as well as to maximize system lifetime. We compare the performance of iMobif to that of systems with no mobility or only cost-unaware mobility. Simulation results show iMobif is effective in reducing energy consumption relative to such systems.