Optimal algorithms for dissemination of information in some interconnection networks

The problems of gossiping and broadcasting in one-way communication mode are considered for some prominent families of graphs. The complexity is measured as the number of communication rounds in the gossip and broadcast algorithms. The main result of the paper is the precise estimation of the gossip-problem complexity in cycles. To obtain this result a new combinatorial analysis of gossiping in cycles is developed. This analysis leads to an optimal lower bound on the number of rounds, and also to the design of an optimal algorithm for gossiping in cycles. The optimal algorithm for gossiping is later used to design new, effective algorithms for gossiping in important families of interconnection networks (cube connected cycles, butterfly networks). Furthermore, a new, effective algorithm for broadcasting in shuffle-exchange networks is developed.On leave from Comenius University, Bratislava, Czechoslovakia.     

An application-level framework for information dissemination and collection in vehicular networks

Mobility of wireless network nodes is increasingly regarded as a fundamental resource for future pervasive communication systems. In this paper, we leverage the movement of communication-enabled vehicles to implement an original Application-level Role Mobility (ARM) framework. ARM allows nodes to share a generic assignment, by handing each other the associated application-level role. The handover of the role is performed according to the mobility patterns of the vehicles, following rules that are specific to the objective of the application. We employ the ARM framework for two different tasks: dissemination of information to traveling cars, and data collection from road-side sensors. For each application, we provide dedicated role handover rules and show, via simulation, that ARM can successfully perform the required operations in a lightweight, fully distributed way.     

Efficient techniques for time-constrained information dissemination using location-based social networks

Social networks have undergone an explosive growth in recent years. They constitute a central part of users׳ everyday lives as they are used as major tools for the spread of information, ideas and notifications among the members of the network. In this work we investigate the use of location-based social networks as a medium of emergency notification, for efficient dissemination of emergency information among members of the social network under time constraints. Our objective is the following: given a location-based social network comprising a number of mobile users, the social relationships among the users, the set of recipients, and the corresponding timeliness requirements, our goal is to select an appropriate subset of users so that the spread of information is maximized, time constraints are satisfied and costs are considered. We propose LATITuDE, our system that investigates the interactions among the members of the social network to infer their social relationships, and develop scalable dissemination mechanisms that select the most efficient set of users to initiate the dissemination process in order to maximize the information reach among the appropriate receivers within a time window. Our detailed experimental results illustrate that our approach is practical, effectively addresses the problem of informing the appropriate set of users within a deadline when an emergency event occurs, uses a small number of messages, and consistently outperforms its competitors.     

An adaptive epidemic information dissemination model for wireless sensor networks

We propose an adaptive bio-inspired information dissemination model that exploits the specific characteristics of the sampled/generated data stream (DS) in a wireless sensor network. Our model extends the basic epidemic algorithm by adapting key operational parameters (i.e., the forwarding probability and validity period) of the data dissemination process. The main idea is that the forwarding probability is tuned according to the variability of the involved DS. Our findings from the introduction of this adaptive epidemic are quite promising. Our scheme supersedes conventional probabilistic information dissemination algorithms in terms of efficiency and reliability.     

MEK: Using spatial-temporal information to improve social networks and knowledge dissemination

Most of the projects which envision knowledge dissemination create and use a unique knowledge base, where all items acquired are organized according to a simple classification. This kind of ‘centralized’ approach shows some inconsistencies in relation to many of the theories about the creation of knowledge and its dissemination. Due to them, distribution and sociability are essential characteristics for the creation and sharing of knowledge. This incoherence partially explains the reason which leads many users into abandoning this kind of system because they have to adapt themselves to a classification and a rigid structure to represent pieces of knowledge. On the other hand, a lot of tacit knowledge and interaction possibilities are lost in this centralized vision. So, based on the advantages of a distributed approach for knowledge dissemination and the improvement of interaction, we designed and constructed the Mobile Exchange of Knowledge (MEK). This approach involves, in a mobile way, the exchanging of knowledge among people who share the same interests. Some issues like ad-hoc networks, social networks, location prediction and distributed knowledge management are also related to the MEK concept. However, to verify how effective our idea is, we conducted an experiment in the geographical space of a university in Brazil where we analyzed the movements of students and also their interest and willingness to share knowledge items.     

Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony

The topic of this paper is the study of information dissemination in mobile ad-hoc networks by means of deterministic protocols. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the mobile ad-hoc networks considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit the assumptions in previous papers. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocol-classes are observed. These results show that the gap in time complexity between oblivious and quasi-oblivious (hence, adaptive) protocols is almost linear. This gap is what we call the profit of global synchrony since it represents the gain the network obtains from global synchrony with respect to not having it. We note that the global synchrony required by the efficient quasi-oblivious protocol proposed is simply achieved by piggybacking in the messages sent the time at the source node, as a global reference.     

An information dissemination model of product quality and safety based on scale-free networks

In the small-world model, information nodes’ positions are relatively ordered. However, information dissemination between nodes is unordered on the Internet. In this study, a product quality and safety information dissemination model on the Internet is proposed in terms of the characteristics of the scale-free model in the complex network. Using the simulation tests, we found that the information diffusion rate will speed up and the time needed for the system to reach the equilibrium will shorten when the spontaneous dissemination coefficient increases. Additionally, the scope of information coverage also increases as the system’s size increases. However, the time of information diffusion needed to cover the maximum area does not change with the system’s size. The media’s influence has also been found to have an effect on the information dissemination.     

GoDisco++: A gossip algorithm for information dissemination in multi-dimensional community networks

In this paper we propose GoDisco++, a gossip based approach for information dissemination in online social community networks. GoDiscoo++ uses local information available to nodes—that is information associated with a node and its neighbors. The algorithm exploits multiple relations which may exist between nodes, and applies social principles and behavior inspired decentralized mechanisms for targeted dissemination. The dissemination process works with the dual aims of (i) maximizing the spread among relevant nodes (high recall) and (ii) minimizing spamming among non-relevant nodes (high precision). Such a designed dissemination scheme can have interesting applications like probabilistic publish/subscribe, decentralized recommendation and contextual advertisement systems, to name a few. We validate the proposed approach with simulation experiments performed using real and synthetic datasets.     

Epidemic information dissemination in distributed systems

Easy to deploy, robust, and highly resilient to failures, epidemic algorithms are a potentially effective mechanism for propagating information in large peer-to-peer systems deployed on Internet or ad hoc networks. It is possible to adjust the parameters of epidemic algorithm to achieve high reliability despite process crashes and disconnections, packet losses, and a dynamic network topology. Although researchers have used epidemic algorithms in applications such as failure detection, data aggregation, resource discovery and monitoring, and database replication, their general applicability to practical, Internet-wide systems remains open to question. We describe four key problems: membership maintenance, network awareness, buffer management, and message filtering, and suggest some preliminary approaches to address them.     

Fast message dissemination in random geometric networks

We analyze information dissemination in random geometric networks, which consist of n nodes placed uniformly at random in the square ${[0,\sqrt{n}]^{2}}$ . In the corresponding graph two nodes u and v are connected by a (directed) edge, i.e., u is an (incoming) neighbor of v, if and only if the distance between u and v is smaller than the transmission radius assigned to u. In order to study the performance of distributed communication algorithms in such networks, we adopt here the ad-hoc radio communication model with no collision detection mechanism available. In this model the topology of network connections is not known in advance. Also a node v is capable of receiving a message from its neighbor u if u is the only (incoming) neighbor transmitting in a given step. Otherwise a collision occurs prompting interference that is not distinguishable from the background noise in the network. First, we consider networks modeled by random geometric graphs in which all nodes have the same radius ${r > \delta \sqrt{\log n}}$ , where δ is a sufficiently large constant. In such networks, we provide a rigorous study of the classical communication problem of distributed gossiping (all-to-all communication). We examine various scenarios depending on initial local knowledge and capabilities of network nodes. We show that in many cases an asymptotically optimal distributed O(D)-time gossiping is feasible, where D stands for the diameter of the network. Later, we consider networks in which the transmission radii of the nodes vary according to a power law distribution, i.e., any node is assigned a transmission radius r > r _min according to probability density function ρ(r) ~ r ^?α . More precisely, ${\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}}$ , where ${\alpha \in (1, 3)}$ and ${r_{\min} > \delta \sqrt{\log n}}$ with δ being a large constant. In this case, we develop a simple broadcasting algorithm that runs in time O(log log n) (i.e., O(D)) always surely, and we show that this result is asymptotically optimal. Finally, we consider networks in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) =  (α?1)c ^α-1 r ^?α , where α is a constant from the same range as before and c is a constant. In this model the graph is usually not strongly connected, however, there is one giant component with Ω(n) nodes, and there is a directed path from each node of this giant component to every other node in the graph. We assume that the message which has to be disseminated is placed initially in one of the nodes of the giant component, and every node is aware of its own position in ${[0,\sqrt{n}] \times [0,\sqrt{n}]}$ . Then, we show that there exists a randomized algorithm which delivers the broadcast message to all nodes in the network in time O(D . (log log n)²), almost always surely, where D stands for the diameter of the giant component of the graph. One can conclude from our studies that setting the transmission radii of the nodes according to a power law distribution brings clear advantages. In particular, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the uniform low transmission power.     

Noninfluentials and information dissemination in the microblogging community

Firms are increasingly focusing on understanding and managing their social media strategies in order to create discussions and optimize the spread of news in their communities. Most prior studies on information dissemination have mainly focused on the roles of influentials but ignored the essential for noninfluentials. To fill this gap, this paper takes a holistic view of the information dissemination process and investigates how the participation of both influentials and noninfluentials plays a role in affecting the volume and sentiment of microblogs, which are precursors to raise awareness and attraction for brands. To test our hypotheses, we build a novel econometric model and apply it to a dataset collected from the popular microblogging site Twitter. We have the following main results: (1) back-and-forth-type discussions and retweets are effective in generating awareness and positive attractiveness; (2) influentials or mavens (who have many followers but seldom follow others) help generate initial sparks toward microblogging, but during the cascading periods, the noninfluentials play an important role in driving the conversations; and (3) new users who gradually join the discussions also help increase awareness, although they may not generate a positive sentiment. Our results provide important implications for mediating consumer interactions and firms’ marketing strategies.     

Optimal scheduling of peer-to-peer file dissemination

Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are increasingly used for disseminating potentially large files from a server to many end users via the Internet. The key idea is to divide the file into many equally-sized parts and then let users download each part (or, for network coding based systems such as Avalanche, linear combinations of the parts) either from the server or from another user who has already downloaded it. However, their performance evaluation has typically been limited to comparing one system relative to another and has typically been realized by means of simulation and measurements. By contrast, we provide an analytic performance analysis that is based on a new uplink-sharing version of the well-known broadcasting problem. Assuming equal upload capacities, we show that the minimal time to disseminate the file is the same as for the simultaneous send/receive version of the broadcasting problem. For general upload capacities, we provide a mixed integer linear program (MILP) solution and a complementary fluid limit solution. We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system. We also investigate the performance of a decentralized strategy, providing evidence that the performance of necessarily decentralized P2P file dissemination systems should be close to this bound and, therefore, that it is useful in practice. Research of G. Weiss is supported in part by Israel Science Foundation Grants 249/02 and 454/05. Collaboration of the authors was supported in part by European Network of Excellence Euro-NGI.     

Matching preclusion and conditional matching preclusion for pancake and burnt pancake graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion destroys all perfect matchings in the graph. The optimal matching preclusion sets are often precisely those which are induced by a single vertex of minimum degree. To look for obstruction sets beyond these, the conditional matching preclusion number was introduced, which is defined similarly with the additional restriction that the resulting graph has no isolated vertices. In this paper we find the matching preclusion and conditional matching preclusion numbers and classify all optimal sets for the pancake graphs and burnt pancake graphs.     

Finding a robust configuration for the AEDB information dissemination protocol for mobile ad hoc networks

The Adaptive Enhanced Distance Based Broadcasting Protocol, AEDB hereinafter, is an advanced adaptive protocol for information dissemination in mobile ad hoc networks (MANETs). It is based on the Distance Based broadcasting protocol, and it acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. As most of the existing communication protocols, AEDB relies on different thresholds for adapting its behavior to the environment. We propose in this work to look for configurations that induce a stable performance of the protocol in different networks by automatically fine tuning these thresholds thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. Finding robust solutions for this problem is important because MANETs have a highly unpredictable and dynamic topology, features that have a strong influence on the performance of the protocol. Consequently, robust solutions that show a good performance under any circumstances are required. In this work, we define different fitness functions that measure robustness of solutions for better guiding the algorithm towards more robust solutions. They are: median, constrained, worst coverage, and worst hypervolume. Results show, that the two worst-case approaches perform better, not only in case of robustness but also in terms of accuracy of the reported AEDB configurations on a large set of networks.     

Optimal broadcasting on the star graph

The star graph has been show to be an attractive alternative to the widely used n-cube. Like the n-cube, the star graph possesses rich structure and symmetry as well as fault tolerant capabilities, but has a smaller diameter and degree. However, very few algorithms exists to show its potential as a multiprocessor interconnection network. Many fast and efficient parallel algorithms require broadcasting as a basic step. An optimal algorithm for one-to-all broadcasting in the star graph is proposed. The algorithm can broadcast a message to N processors in O(log₂ N) time. The algorithm exploits the rich structure of the star graph and works by recursively partitioning the original star graph into smaller star graphs. In addition, an optimal all-to-all broadcasting algorithm is developed     

Hierarchical role-based data dissemination in wireless sensor networks

Data dissemination from multiple sources to mobile sinks is fundamental and challenging in WSN applications due to limited energy supply of sensor nodes and sink mobility. Previous data dissemination protocols either rely on an energy-consuming coordinate system or build an inefficient backbone. In this paper, we propose a hierarchical role-based data dissemination (HRDD) protocol in wireless sensor networks. In HRDD, a small number of sensor nodes are assigned to serve as cluster heads and agents to form the data dissemination backbone and mitigate unnecessary query forwarding. In addition, HRDD designs an efficient data delivery mechanism that provides shorter paths to accelerate data delivery as well as reduce the number of data transmissions. An adaptive backbone maintenance mechanism is also introduced for low-energy cluster heads and agents to reduce their load, thereby prolonging the network lifetime. The experimental results show that HRDD achieves the longer network lifetime, the shorter delay, and the high success ratio compared to the prior work.     

车辆网络中一种有效的警告消息散布协议

针对车辆网络的警告消息散布问题进行研究,提出一种有效的警告消息散布协议WMD.在WMD中,时间被分成一个个带时间槽的时间帧,每个时槽被分成两个子时槽,第一个时槽用来实时获取邻居位置,第二个时槽用来散布警告消息.为了实时获取邻居位置,WMD采取自适应的发送策略.通过理论分析,对每个时间帧的发送次数以及每个时间帧的长度进行优化.基于真实车辆行驶数据进行仿真实验.实验结果表明,相比其他方法,WMD实现了较快的散布速率和较高的接收率.     

Nearly optimal one-to-many parallel routing in star networks

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n²). More specifically, given a node s and n-1 other nodes {t₁, t₂ , …, t_n-1} in the n-star network, our algorithm constructs n-1 node-disjoint paths P₁, P₂, …, P_n-1, where P_i is a path from s to t_j of length at most dist(s, t_j)+6 and dist(s, t _j) is the distance, i.e., the length of a shortest path, from s to t_j, for i=1, 2, …, n-1.The best bound on the path length by previously known algorithms for the same problem is 5(n-2)≈10Δ_n/3, where Δ_n=max{dist(s, t)} is the diameter of the n-star network