Testbed results of an opportunistic routing for multi-robot wireless networks

Opportunistic routing is a candidate for multihop wireless routing where the network topology and radio channels vary rapidly. However, there are not many opportunistic routing algorithms that can be implemented in a real multihop wireless network while exploiting the node mobility. It motivates us to implement an opportunistic routing, random basketball routing (BR), in a real multi-robot network to see if it can enhance the capacity of the multihop network as mobility increases. For implementation purposes, we added some features, such as destination RSSI measuring, a loop-free procedure and distributed relay probability updating, to the original BR. We carried out the experiments on a real multi-robot network and compared BR with AODV combined with CSMA/CA (routing + MAC protocol). We considered both static and dynamic scenarios. Our experiments are encouraging in that BR outperforms AODV + CSMA/CA, particularly in dynamic cases; the throughput of BR is 6.6 times higher than that of AODV + CSMA/CA. BR with dynamic networks shows 1.4 times higher throughput performance than BR with static networks. We investigate the performance of BR in the large-scale network using NS-2 simulation. We verify the effect of node density, speed, destination beacon signal and loop-free procedure. According to the large-scale simulation, the end-to-end throughput grows with the node speed.     

A dynamic multicast tree based routing scheme without replication in delay tolerant networks

Delay tolerant networks (DTNs) are a special type of wireless mobile networks which may lack continuous network connectivity. Multicast is an important routing function that supports the distribution of data to a group of users: a service needed for many potential DTN applications. While multicasting in the Internet and in mobile ad hoc networks has been studied extensively, efficient multicasting in DTNs is a considerably different and challenging problem due to the probabilistic nature of contact among nodes. This paper aims to provide a non-replication multicasting scheme in DTNs while keeping the number of forwardings low. The address of each destination is not replicated, but is assigned to a particular node based on its contact rate level and active level. Our scheme is based on a dynamic multicast tree where each leaf node corresponds to a destination. Each tree branch is generated at a contact based on the compare–split rule proposed in this paper. The compare part determines when a new search branch is needed, and the split part decides how the destination set should be partitioned. When only one destination is left in the destination set, we use either wait (no further relay) or focus (with further relay) to reach the final destination. The effectiveness of our approach is verified through extensive simulations. Ratio-based-split performs best in the compare–split step, both in synthetic and real traces. Using the wait scheme can reduce the number of forwardings, while using the focus scheme can reduce the latency.     

ML-SOR: Message routing using multi-layer social networks in opportunistic communications

Opportunistic networks are a generalization of DTNs in which disconnections are frequent and encounter patterns between mobile devices are unpredictable. In such scenarios, message routing is a fundamental issue. Social-based routing protocols usually exploit the social information extracted from the history of encounters between mobile devices to find an appropriate message relay. Protocols based on encounter history, however, take time to build up a knowledge database from which to take routing decisions. While contact information changes constantly and it takes time to identify strong social ties, other types of ties remain rather stable and could be exploited to augment available partial contact information. In this paper, we start defining a multi-layer social network model combining the social network detected through encounters with other social networks and investigate the relationship between these social network layers in terms of node centrality, community structure, tie strength and link prediction. The purpose of this analysis is to better understand user behavior in a multi-layered complex network combining online and offline social relationships. Then, we propose a novel opportunistic routing approach ML-SOR (Multi-layer Social Network based Routing) which extracts social network information from such a model to perform routing decisions. To select an effective forwarding node, ML-SOR measures the forwarding capability of a node when compared to an encountered node in terms of node centrality, tie strength and link prediction. Trace driven simulations show that a routing metric combining social information extracted from multiple social network layers allows users to achieve good routing performance with low overhead cost.     

一种基于可变半衰期的机会网络社团兴趣值更新策略

为了掌握节点移动的历史信息,提出了MDIR (Mass-group Detected by Interest-value )算法。该算法引入了社团的概念,将节点的移动规律与其它节点的关系进行关联。理论上,在社会网络中节点的移动可以归结为在不同社团中移动的过程。因此在该算法中,消息更倾向于向包含目标节点的社团转发。此外,考虑到社会关系的动态性,算法还引入兴趣值概念来更新网络拓扑中的社团结构。实验测试数据表明,在不同的节点密集度和网络资源有限的情况下,相较于Epidemic、BDCR以及SREP算法,MDIR算法可通过计算效用值进行路由转发来产生较低的转发能耗以及稳定的送达率。     

基于模糊身份密码学的机会网络身份认证方案

针对机会网络的自组织性、开放性、连通性差等特点以及现有的基于上下文的路由协议中可能存在的隐私泄露等安全问题,提出了一种基于模糊身份密码学的身份认证方案F-ONIAS(Identity Authentication Scheme in Opportunistic Network Based on Fuzzy-IBE)。该方案通过一个无需实时在线的PKG为用户颁发私钥来解决机会网络中因节点无法实时连通而导致的传统非对称密码学方案不适用的问题。同时,将节点的生物信息作为身份标识,避免了传统身份密码学中身份信息可能被伪造而带来的安全隐患。仿真实验表明,在存在恶意节点的网络环境下,本方案比现有的经典路由协议方案拥有更高的报文投递率和更低的路由开销率,并且未对报文平均时延造成明显影响。     

Energy-efficient forwarding in wireless sensor networks

For maximizing the energy efficiency in a wireless network, we propose two forwarding schemes termed single-link and multi-link energy-efficient forwarding that tradeoff delivery ratios against energy costs. Multi-link forwarding improves the network performance substantially by addressing multiple receivers at once during the packet forwarding process. If the first forwarding node does not receive a packet correctly, other nodes may act as backup nodes and perform the forwarding instead. By means of mathematical analyses, we derive how the energy efficiency of a forwarding path can be computed and how a forwarding tree is established. Routing cycles are explicitly taken into account and prevented by means of sequence numbers. Simulations and real-world experiments provide a comparison to other reference strategies, showing a superior performance of our forwarding scheme in terms of energy efficiency.     

A framework for exploring organizational structure in dynamic social networks

Recent research has provided promising results relating to discovering communities within a social network. We find that further representing the organizational structure of a social network is an interesting issue that helps gain better understandings of the social network. In this paper, we define a data structure, named Community Tree, to depict the organizational structure and provide a framework for exploring the organizational structure in a social network. In this framework, an algorithm, which combines a modified PageRank and Random Walk on graph, is developed to derive the community tree from the social network. In the real world, a social network is constantly evolving. In order to explore the organizational structure in a dynamic social network, we develop a tree learning algorithm, which employs tree edit distance as the scoring function, to derive an evolving community tree that enables a smooth transition between two community trees. We also propose an approach to threading communities in community trees to obtain an evolution graph of the organizational structure, by which we can reach new insights from the dynamic social network. The experiments conducted on synthetic and real dataset demonstrate the feasibility and applicability of the framework. Based on the theoretical outcomes, we further apply the proposed framework to explore the evolution of organizational structure with the 2001 Enron dataset, and obtain several interesting findings that match the context of Enron.     

Online social networks in economics

This paper describes how economists study social networks. While economists borrow from other fields like sociology or computer science, their approach of modeling of social networks is distinguished by the emphasis on the role of choices under constraints. Economists investigate how socioeconomic background and economic incentives affect the structure and composition of social networks. The characteristics of social networks are important for economic outcomes like the matching of workers to jobs and educational attainment. I review the theoretical and empirical literature that investigates these relationships and discuss possible implications of new, Internet based, forms of social interactions.     

Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery

The network structure exhibits a variety of changes over time. Fusing this structure and the development of communities in dynamic networks plays an important role in analyzing the evolution and development of the entire network. How to ensure the division of the community structure in social network big data, as well as ensure the continuity of the community between the current time and previous time period, are issues that need to be explored. This problem can be solved by fusing the three characteristics of temporal variability, stability, and continuity in dynamic social network communities, and by adopting the multi-objective optimization method to detect community structures in dynamic networks. The probability fusion method is added to the initial step of the algorithm to generate suitable network partitions and ensure fast convergence and high accuracy. Two neighboring fusion strategies are proposed that are suitable for communities: the neighbor diversity strategy and the neighbor crowd strategy. These two strategies make different changes to the candidate network partitions. A continuity metric for dynamic community evolution is formulated to compare the similarity of the dynamic network communities of two consecutive time steps. Experiments on synthetic datasets and actual datasets prove that the proposed method in this paper provides better performance than existing methods.     

Ambient awareness: From random noise to digital closeness in online social networks

Ambient awareness refers to the awareness social media users develop of their online network in result of being constantly exposed to social information, such as microblogging updates. Although each individual bit of information can seem like random noise, their incessant reception can amass to a coherent representation of social others. Despite its growing popularity and important implications for social media research, ambient awareness on public social media has not been studied empirically. We provide evidence for the occurrence of ambient awareness and examine key questions related to its content and functions. A diverse sample of participants reported experiencing awareness, both as a general feeling towards their network as a whole, and as knowledge of individual members of the network, whom they had not met in real life. Our results indicate that ambient awareness can develop peripherally, from fragmented information and in the relative absence of extensive one-to-one communication. We report the effects of demographics, media use, and network variables and discuss the implications of ambient awareness for relational and informational processes online.     

Modelling opinion formation driven communities in social networks

In a previous paper we proposed a model to study the dynamics of opinion formation in human societies by a co-evolution process involving two distinct time scales of fast transaction and slower network evolution dynamics. In the transaction dynamics we take into account short range interactions as discussions between individuals and long range interactions to describe the attitude to the overall mood of society. The latter is handled by a uniformly distributed parameter α, assigned randomly to each individual, as quenched personal bias. The network evolution dynamics is realised by rewiring the societal network due to state variable changes as a result of transaction dynamics. The main consequence of this complex dynamics is that communities emerge in the social network for a range of values in the ratio between time scales. In this paper we focus our attention on the attitude parameter α and its influence on the conformation of opinion and the size of the resulting communities. We present numerical studies and extract interesting features of the model that can be interpreted in terms of social behaviour.     

Flink: Semantic Web technology for the extraction and analysis of social networks

We present the Flink system for the extraction, aggregation and visualization of online social networks. Flink employs semantic technology for reasoning with personal information extracted from a number of electronic information sources including web pages, emails, publication archives and FOAF profiles. The acquired knowledge is used for the purposes of social network analysis and for generating a web-based presentation of the community. We demonstrate our novel method to social science based on electronic data using the example of the Semantic Web research community.     

基于MCMC技术的社会网络搜索

实验和理论表明社会网络中存在着短路径,即人们可以在较少的步数内找到目标。研究了社会网络中的贪婪搜索现象,给出了将长程连接图嵌入底层一维和二维网格的马尔科夫链蒙特卡罗方法。该方法更符合现实情况,坐标体系只是用于网上距离的计算。将算法用于模拟数据（根据一维和二维理想模型产生的图）和真实的社会网络数据均有很好的查询效率,查询成功率高,成功查询平均步长短。     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

MOEME: Real-time Mobility and Orientation Estimation for Mobile Environments

Knowledge of user movement in mobile environments paves the way for intelligent resource allocation and event scheduling for a variety of applications. Existing schemes for estimating user mobility are limited in their scope as they rely on repetitive patterns of user movement. Such patterns neither exist not easy to recognize in soft-real time, in open environments such as parks, malls, or streets. We propose a novel scheme for Real-time Mobility and Orientation Estimation for Mobile Environments (MOEME). MOEME employs the concept of temporal distances and uses logistic regression to make real time estimations about user movement. MOEME is also used to make predictions about the absolute orientation of users. MOEME relies only on opportunistic message exchange and is fully distributed, scalable, and requires neither a central infrastructure nor Global Positioning System. MOEME has been tested on real world and synthetic mobility traces—makes predictions about direction and count of users with up to 90% accuracy, enhances successful video downloads in shared environments.     

The dynamic team forming problem: Throughput and delay for unbiased policies

The dynamic team forming problem (DTFP) for a heterogeneous group of robots is described as follows. Each robot is capable of providing a specific service. Tasks arrive sequentially over time, assume random locations in the environment, and require several different services. A task is completed when a team of robots travels to the task location and provides the required services. The goal is to minimize the expected delay between a task’s arrival and its completion. We restrict our attention to unbiased policies for the DTFP, i.e., policies for which the expected delay is the same for all tasks. We introduce three intuitive policies, and in certain asymptotic regimes we analyze their delay as a function of the arrival rate of tasks (or throughput). For each policy we show that there is a broad class of system parameters for which the policy’s performance is within a constant factor of the optimal.     

一种应用于社交网络中的时延容忍路由协议*

基于传染方式的时延容忍路由并不适合直接应用于社交网络中,不可控的冗余数据包不但极大增加了网络的负载,同时也使得节点极易受到DoS攻击。通过分析社交网络的小世界特性,构建了基于社会关系的网络拓扑模型,并基于该模型提出了一种安全高效的时延容忍路由协议。通过实验,证明了基于节点的社会关系特性,该路由协议可以有效地保证重要数据包的成功转发,并降低节点被DoS攻击的风险。     

无线传感器网络动态重传算法

无线传感器网络路由协议通过点到点的重传来提高数据传输的可靠性,其重传机制没有考虑不同业务数据的可靠性需求差异,统一设定一个静态的最大重传次数。本文提出了一种动态重传算法,为每种业务分别根据其可靠性需求动态设定最大重传次数。对于较低可靠性需求的业务,相比于传统重传机制减少了重传次数。仿真表明动态重传算法能有效降低网络能耗。     

Social relationships and information dissemination in virtual social network systems: An attachment theory perspective

Web-based communication via social networking sites has become an integral method of communication, raising the question of whether the well-established Attachment Theory remains applicable to modern relationships. This communication shift is also likely to affect the information dissemination dynamic; i.e., how internal attachment working models relate to virtual modes of communication. Three studies (354 participants in total, median age 27) examined the applicability of Attachment Theory to web-based social network communications. Using self- report measures (Study 1) and an experimental simulation (Study 2), the results indicate that attachment security level predicts an individual’s number of social ties and willingness to initiate web-based relationships. Secure individuals emerged as best situated to become social hubs. Study 3 reveals that a decrease in avoidance scores predicts an increased willingness to deliver information to others. Anxious participants exhibited less willingness to deliver highly threatening information but more willingness to deliver neutral information to others.These findings support the applicability of attachment internal working models to predicting web-based social network communication, and suggest that Attachment Theory can be a predictor of the dynamics of web-based dissemination of information.