We consider information dissemination in a large n -user wireless network in which k users wish to share a unique message with all other users. Each of the n users only has knowledge of its own contents and state information; this corresponds to a one-sided push-only scenario. The goal is to disseminate all messages efficiently, hopefully achieving an order-optimal spreading rate over unicast wireless random networks. First, we show that a random-push strategy-where a user sends its own or a received packet at random-is order-wise suboptimal in a random geometric graph: specifically, Ω(√n) times slower than optimal spreading. It is known that this gap can be closed if each user has “full” mobility, since this effectively creates a complete graph. We instead consider velocity-constrained mobility where at each time slot the user moves locally using a discrete random walk with velocity v(n) that is much lower than full mobility. We propose a simple two-stage dissemination strategy that alternates between individual message flooding (“self promotion”) and random gossiping. We prove that this scheme achieves a close to optimal spreading rate (within only a logarithmic gap) as long as the velocity is at least v(n)=ω(√(logn k)). The key insight is that the mixing property introduced by the partial mobility helps users to spread in space within a relatively short period compared to the optimal spreading time, which macroscopically mimics message dissemination over a complete graph.
Another line of work has studied spreading scaling laws using more sophisticated non-gossip schemes over static wireless networks, e.g. @cite_1 @cite_8 . Recently, Resta @cite_25 began investigating broadcast schemes for mobile networks with a source constantly propagating new data, while we focus on a different problem with multiple mobile sources each sharing distinct message. Besides, @cite_25 analyzed how to combat the adverse effect of mobility to ensure the same pipelined broadcasting as in static networks, whereas we are interested in how to take advantage of mobility to overcome the geometric constraints. In fact, with the help of mobility, simply performing random gossiping -- which is simpler than most non-gossip schemes and does not require additional overhead -- is sufficient to achieve optimality.
@cite_1 @cite_25 @cite_8
2118323697 2022453146 2060660772
We study gossip algorithms for the rumor spreading problem which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple and robust solutions to the rumor spreading problem. Recently, non-uniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-, STOC'12] gave an O(log^3 n) algorithm to solve the 1-local broadcast problem in which each node wants to exchange rumors locally with its 1-neighborhood. By repeatedly applying this protocol one can solve the global rumor spreading quickly for all networks with small diameter, independently of the conductance. This and all prior gossip algorithms for the rumor spreading problem have been inherently randomized in their design and analysis. This resulted in a parallel research direction trying to reduce and determine the amount of randomness needed for efficient rumor spreading. This has been done via lower bounds for restricted models and by designing gossip algorithms with a reduced need for randomness. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors. In this paper we improves over this state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem in 2(k+log n)log n rounds. Besides being the first efficient deterministic solution to the rumor spreading problem this algorithm is interesting in many aspects: It is simpler, more natural, more robust and faster than its randomized pendant and guarantees success with certainty instead of with high probability. Its analysis is furthermore simple, self-contained and fundamentally different from prior works. In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good "Quality of Delivery," i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal. Broadcasting and gossiping are fundamental tasks in network communication. In broadcasting, or one-to-all communication, information originally held in one node of the network (called the source) must be transmitted to all other nodes. In gossiping, or all-to-all communication, every node holds a message which has to be transmitted to all other nodes. As communication networks grow in size, they become increasingly vulnerable to component failures. Thus, capabilities for fault-tolerant broadcasting and gossiping gain importance. The present paper is a survey of the fast-growing area of research investigating these capabilities. We focus on two most important efficiency measures of broadcasting and gossiping algorithms: running time and number of elementary transmissions required by the communication process. We emphasize the unifying thread in most results from the research in fault-tolerant communication: the trade-offs between efficiency of communication schemes and their fault-tolerance. © 1996 John Wiley & Sons, Inc. Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Theta(1 radic(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=Theta(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Theta(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Theta(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of Oscr(1 radic(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=Theta(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Theta(nlogn), which is the delay for throughput of Theta(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay. In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate k distinct messages to all n nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of O((k + log n + D)Δ) rounds with high probability, where D and Δ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of k this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is Θ(k + D). To eliminate the factor of Δ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol S. The stopping time of TAG is O(k+ log n + d(S) + t(S)), where t(S) is the stopping time of the spanning tree protocol, and d(S) is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for k=Ω(n), where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after Θ(n) rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for k=Ω(polylog(n)). The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis. We present a method for using real world mobility traces to identify tractable theoretical models for the study of distributed algorithms in mobile networks. We validate the method by deriving a vehicular ad hoc network model from a large corpus of position data generated by Boston-area taxicabs. Unlike previous work, our model does not assume global connectivity or eventual stability; it instead assumes only that some subset of processes are connected through transient paths (e.g., paths that exist over time). We use this model to study the problem of prioritized gossip, in which processes attempt to disseminate messages of different priority. Specifically, we present CabChat, a distributed prioritized gossip algorithm that leverages an interesting connection to the classic Tower of Hanoi problem to schedule the broadcast of packets of different priorities. Whereas previous studies of gossip leverage strong connectivity or stabilization assumptions to prove the time complexity of global termination, in our model, with its weak assumptions, we instead analyze CabChat with respect to its ability to deliver a high proportion of high priority messages over the transient paths that happen to exist in a given execution. Broadcast or flooding is a dissemination technique of paramount importance in wireless ad hoc networks. The broadcast scheme is widely used within routing protocols by a wide range of wireless ad hoc networks such as mobile ad hoc networks, vehicular ad hoc networks, and wireless sensor networks, and used to spread emergency messages in critical scenarios after a disaster scenario and or an accidents. As the type broadcast scheme used plays an important role in the performance of the network, it has to be selected carefully. Though several types of broadcast schemes have been proposed, probabilistic broadcast schemes have been demonstrated to be suitable schemes for wireless ad hoc networks due to a range of benefits offered by them such as low overhead, balanced energy consumption, and robustness against failures and mobility of nodes. In the last decade, many probabilistic broadcast schemes have been proposed by researchers. In addition to reviewing the main features of the probabilistic schemes found in the literature, we also present a classification of the probabilistic schemes, an exhaustive review of the evaluation methodology including their performance metrics, types of network simulators, their comparisons, and present some examples of real implementations, in this paper. We present a deterministic broadcast algorithm for the class of mobile ad hoc networks where the mobile nodes possess collision detection capabilities. The algorithm is based on a breadth-first traversal of the network, allows multiple transmissions in the same time slot and completes broadcast in O(n log n) time in the worst case. It is mobility resilient even for networks where topology changes are very frequent. The idea of this broadcast algorithm is then extended to develop a gossiping algorithm having O((n+D)Dlog n) worst case run time, where D is the diameter of the network graph, which is an improvement over the existing algorithms. In this paper, we investigate the fundamental properties of broadcasting in mobile wireless networks. In particular, we characterize broadcast capacity and latency of a mobile network, subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform. We first study the intrinsic properties of broadcasting, and present a broadcasting scheme that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on the maximum node velocity. We then investigate the broadcasting problem when the burden related to selecting relay nodes is taken into account, and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a poly-logarithmic factor from optimal. Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in a wireless network when the nodes are fixed, and showed that the throughput per source-destination pair is spl otimes (1 spl radic nlogn). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant or spl otimes (1) throughput scaling per source-destination pair. The focus of this paper is on characterizing the delay and determining the throughput-delay trade-off in such fixed and mobile ad hoc networks. For the Gupta-Kumar fixed network model, we show that the optimal throughput-delay trade-off is given by D(n) = spl otimes (nT(n)), where T(n) and D(n) are the throughput and delay respectively. For the Grossglauser-Tse mobile network model, we show that the delay scales as spl otimes (n sup 1 2 v(n)), where v(n) is the velocity of the mobile nodes. We then describe a scheme that achieves the optimal order of delay for any given throughput. The scheme varies (i) the number of hops, (ii) the transmission range and (iii) the degree of node mobility to achieve the optimal throughput-delay trade-off. The scheme produces a range of models that capture the Gupta-Kumar model at one extreme and the Grossglauser-Tse model at the other. In the course of our work, we recover previous results of Gupta and Kumar, and Grossglauser and Tse using simpler techniques, which might be of a separate interest. Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding (O(n2) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a √n factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional √n factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high probability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies. Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and for computing in an arbitrarily connected network of nodes. Specifically, we propose a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithms almost surely converge to a consensus. In addition, the random consensus value is, in expectation, equal to the desired value, i.e., the average of initial node measurements. However, the broadcast gossip algorithms do not converge to the initial average in absolute sense because of the fact that the sum is not preserved at every iteration. We provide theoretical results on the mean square error performance of the broadcast gossip algorithms. The results indicate that the mean square error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithms required to achieve a given distance to consensus through numerical simulations. Several multihop applications developed for vehicular ad hoc networks use broadcast as a means to either discover nearby neighbors or propagate useful traffic information to other vehicles located within a certain geographical area. However, the conventional broadcast mechanism may lead to the so-called broadcast storm problem, a scenario in which there is a high level of contention and collisions at the link layer due to an excessive number of broadcast packets. While this is a well-known problem in mobile ad hoc wireless networks, only a few studies have addressed this issue in the VANET context, where mobile hosts move along the roads in a certain limited set of directions as opposed to randomly moving in arbitrary directions within a bounded area. Unlike other existing works, we quantify the impact of broadcast storms in VANETs in terms of message delay and packet loss rate in addition to conventional metrics such as message reachability and overhead. Given that VANET applications are currently confined to using the DSRC protocol at the data link layer, we propose three probabilistic and timer-based broadcast suppression techniques: weighted p-persistence, slotted 1-persistence, and slotted p-persistence schemes, to be used at the network layer. Our simulation results show that the proposed schemes can significantly reduce contention at the MAC layer by achieving up to 70 percent reduction in packet loss rate while keeping end-to-end delay at acceptable levels for most VANET applications. Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy 1 n sup a using O(n sup 1.5 spl radic (logn)) radio transmissions, which reduces the energy consumption by a spl radic (n logn) factor over standard gossip algorithms. Broadcast in mobile ad-hoc networks is a challenging and resource demanding task, due to the effects of dynamic network topology and channel randomness. In this paper, we consider 2D wireless ad-hoc networks where nodes are randomly distributed and move following a random direction mobility model. A piece of information is broadcast from an arbitrary node. Based on an in-depth analysis into the popular Susceptible-Infectious-Recovered (SIR) epidemic routing algorithm for mobile ad-hoc networks, an energy and spectrum efficient broadcast scheme is proposed, which is able to adapt to fast-changing network topology and channel randomness. Analytical results are provided to characterize the performance of the proposed scheme, including the fraction of nodes that can receive the information and the delay of information propagation. The accuracy of analytical results is verified using simulations. We consider Mobile Ad-hoc NETworks (MANETs) formed by n nodes that move independently at random over a finite square region of the plane. Nodes exchange data if they are at distance at most r within each other, where r > 0 is the node transmission radius . The flooding time is the number of time steps required to broadcast a message from a source node to every node of the network. Flooding time is an important measure of the speed of information spreading in dynamic networks. We derive a nearly-tight upper bound on the flooding time which is a decreasing function of the maximal velocity of the nodes. It turns out that, when the node velocity is "sufficiently" high, even if the node transmission radius r is far below the connectivity threshold , the flooding time does not asymptotically depend on r . So, flooding can be very fast even though every snapshot (i.e. the static random geometric graph at any fixed time) of the MANET is fully disconnected. Our result is the first analytical evidence of the fact that high, random node mobility strongly speed-up information spreading and, at the same time, let nodes save energy . Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point---which may be either fixed or moving---is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network. Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we have recently proposed a broadcasting-based gossiping protocol to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. The class of broadcast gossip algorithms achieve consensus almost surely at a value that is in the neighborhood of the initial node measurements? average. In this paper, we further study the broadcast gossip algorithms: we derive and analyze the optimal mixing parameter of the algorithm when approached from worst-case convergence rate, present theoretical results on limiting mean square error performance of the algorithm, and find the convergence rate order of the proposed protocol. TV is regarded as a key service for mobile devices. In the past, Mobile TV was often associated with broadcast transmission. However, unicast technology is sufficient in many cases, especially since mobile users prefer to access content on-demand, rather than following a fixed schedule. In this paper we will focus on 3G mobile networks, which have been primarily optimized for unicast services. Based on a traffic model we will discuss the capacity limits of 3G networks for unicast distribution of Mobile TV. From the results it can be concluded that the capacity is sufficient for many scenarios. In order to address scenarios in which broadcast is a more appropriate technology, 3GPP has defined a broadcast extension, called Multimedia Broadcast Multicast Service (MBMS). MBMS introduces shared radio broadcast bearers and has thus the capabilities of a real broadcasting technology. We will give a short overview about MBMS including a discussion on MBMS capacity. Since MBMS is primarily a new transport technology, additional application and service layer technologies are required, like electronic service guide and service protection. These mechanisms are standardized by the Open Mobile Alliance (OMA) and are favorably combined with MBMS or 3G unicast distribution in order to create complete end-to-end solutions. In order to optimize a system for delivery of broadcast services over 3G networks, the advantages of broadcast and unicast should be combined. We argue that hybrid unicast-broadcast delivery offers the best system resource usage and also the best user experience, and is thus favorable not only for broadcast delivery in 3G networks, but actually also for non-cellular broadcast systems like DVB-H or DMB Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.