gossip协议：一种减少自组织网络路由开销的新方法

需积分: 9 158 浏览量更新于2024-09-07 收藏 199KB PDF 举报

"Gossip-Based Ad-Hoc Routing是Zygmunt Haas、Joseph Y. Halpern和Li Li在Cornell University提出的一种基于 gossip 的自组织网络路由协议。该协议旨在通过节点以一定概率转发消息来减少路由协议的开销，从而优化传统洪水泛洪(flooding)方式中的不必要的消息传播。 gossiping 在网络规模足够大时表现出双模态行为：在某些执行中，消息迅速消失，只有少量节点收到；而在其他执行中，大部分节点都能接收到消息。节点接收到消息的比例取决于 gossiping 的概率和网络拓扑结构。在研究的网络中，使用0.6到0.8之间的 gossiping 概率可以确保几乎在所有执行中，几乎每个节点都能接收到消息。对于大型网络，这种简单的 gossiping 协议可以减少高达35%的消息数量。" 本文探讨了在自组织网络(ad-hoc network)中，如何通过 gossiping（八卦）策略来改进路由协议，以降低网络开销。传统的 ad-hoc 路由协议常采用洪水泛洪策略，即每个节点接收到消息后都会向其所有邻居广播，这导致了大量的冗余消息传输，增加了网络负担。Gossip-Based Ad-Hoc Routing 提出了一种新的思路，即节点随机地以一定的概率转发消息，而不是无差别地广播。 gossiping 策略在大规模网络中呈现出两种不同的运行模式。一种情况是消息传播迅速消亡，只有一小部分节点能接收到，这是由于节点随机性转发的概率导致的。另一种情况是大多数节点都能接收到消息，这是因为尽管每次转发都是随机的，但随着消息在网络中传播，最终会覆盖大部分节点。这种现象的出现与 gossiping 的概率和网络的拓扑结构密切相关。通过调整 gossiping 概率，可以在保证消息传递效率的同时，显著减少不必要的消息传输。在实际应用中，作者发现 gossiping 概率设置在0.6至0.8之间，能够有效地保证几乎每个节点在大多数情况下都能接收到消息，同时显著减少了网络中消息的数量。这一结果对于大型网络尤其有利，可以将消息传输的开销降低35%，从而提高了网络资源的利用率和路由协议的效率。 Gossip-Based Ad-Hoc Routing 是一种创新的自组织网络路由策略，它利用 gossiping 的随机性来减少网络负担，同时保证消息的广泛传播。这种方法对于优化 ad-hoc 网络的性能，尤其是在资源有限的环境中，具有重要的理论和实践意义。

of the inﬁnite random graphs G constructed as above, if

GOSSIP1(p,0) is used by every node to spread a message,

then there is a probability θ

(p) < 1 such that the mes-

sage reaches inﬁnitely many nodes is θ

(p). Moreover,

the probability that a node receives the message and for-

wards it in an execution where the message reaches in-

ﬁnitely many nodes is also θ

(p).

Note that the probability of a message dying out (i.e.,

not spreading to inﬁnitely many nodes) is taken over the

executions of the algorithm. That is, the theorem says that

if we execute the algorithm repeatedly, the probability that

a message does not die out in any given execution is θ

(p).

On the other hand, the second θ

(p) talks about the prob-

ability that a node receives and forwards the message in a

given execution of the algorithm. The intuition behind the

equality of the above two probabilities is easy to explain.

A gossip initiated by a source n

dies out if there is a set

of nodes N that disconnects n

from the rest of the graph;

that is, every inﬁnite path starting at n

must go through

a node in N . Thus, θ

(p) is the probability that there is

no disconnecting set N such that none of the nodes in N

forward the message. (Note that N could consist of the

singleton node n

itself.) Similarly, the probability that a

random node n does not receive and forward the message

is precisely the probability that there is a set N

′

such that

′

disconnects n from n

and none of the nodes in N

′

for-

wards the message. In a regular graph or a random graph

of the type considered here, these probabilities are clearly

the same.

It follows from these results that, in an execution where

the message does not die out, the probability that a random

node receives the message is θ

(p)/p, since receiving the

message is independent of forwarding it. Thus, in terms of

the notation used in the introduction, θ

(p) = θ

(p) and

(p) = θ

(p)/p.

Let θ

(p) be the probability that a message reaches

inﬁnitely many nodes if GOSSIP1(p, k) is used. It is

easy to see that θ

(p) = θ

(p)/p, since the probabil-

ity that the message reaches inﬁnitely many nodes using

GOSSIP1(p, 1) is precisely the probability that a message

reaches inﬁnitely many nodes using GOSSIP1(p, 0) given

that the source actually gossips. However, note that the

probability that a node receives and forwards a message

if GOSSIP1(p, k) is used, given that the message does not

die out, is still θ

(p). That is, the probability that a node

receives the message is independent of the choice of k. On

the other hand, it is not hard to see that if each node learns

the network topology in a zone of radius k (so that it can

route a message directly to any node in its zone), then the

probability that a node receives and forwards a message

given that the message does not die out is θ

(p).

All these results are for inﬁnite graphs. It is not hard

to show that essentially the same results hold for ﬁnite

graphs, except possibly near the boundary. In sufﬁciently

large ﬁnite graphs, there will be two types of executions:

those where hardly any node gets the message, and those

where the message makes it all the way to the boundary.

It follows easily from the Central Limit Theorem that, in

sufﬁciently large graphs, in almost all executions where

the gossip does not die out, a fraction θ

(p)/p nodes will

get the message. That is, we expect the bimodal behav-

ior: either hardly any nodes get the message, or a fraction

(p)/p receive the message. As we shall see, in cases of

interest, θ

(p) is quite close to p. Thus, in almost all exe-

cutions of the algorithm in sufﬁciently large graphs, either

hardly any nodes receive the message, or most do.

This leads to a number of obvious questions:

• How large is “sufﬁciently large”?

• What is the behavior of θ

(p) for different graphs of in-

terest?

• What can be done to improve the performance of gos-

siping in realistic settings?

We investigate these questions in the next two sections.

III. GOSSIPING IN FINITE NETWORKS

We did a number of experiments to investigate the be-

havior of gossiping. We summarize some of the more in-

teresting results here. We assumed an ideal MAC layer for

these experiments because we wanted to decouple the ef-

fect of the MAC layer from the effect of gossiping. (When

we consider more realistic scenarios in Section V, we use

the IEEE 802.11 MAC layer.) We ﬁrst study regular net-

works, since they allow us to easily analyze how GOSSIP1

behaves with respect to different parameters, such as the

gossip probability, network size, and node degree, without

other complicating factors. As we shall see, the behavior

in regular graphs seems quite indicative of the behavior

of gossiping in general. We then study random networks

constructed as follows: Nodes are placed at random on a

two-dimensional area; an edge is placed between any pair

of nodes less than a ﬁxed distance d apart. This type of

random graph seems appropriate for modeling a number

of applications involving ad hoc networks. Nodes have a

limited amount of power, and so can communicate only

with reasonably close nodes. The random placement can

be viewed as modeling features such as the random mo-

bility of nodes and the random placement of sensors in a

large region.

Our ﬁrst set of experiments involves “medium-sized”

networks, with 1000 nodes. We start by considering a

20×50 grid (i.e., a regular graph of degree 4). We focus on

GOSSIP1(p, 4), since taking k = 4 produces a reasonable

剩余11页未读，继续阅读

gu1013

粉丝: 0
资源: 3

gossip协议：一种减少自组织网络路由开销的新方法

A.Gossip-Based.Energy.Conservation.Protocol.for.Wireless.Ad.Hoc.and.Sensor.Networks

PyPI 官网下载 | gossip-2.4.0.tar.gz

Gossip-based gradient-free method for multi-agent optimization: constant step size analysis

the-gossip-project-bdd-models

Gossip-闲言碎语

gossip-summer-school-2018:Let's GOSSIP暑期学校2018的源代码回购

ssb-gossip-sim:模拟八卦网络算法

draft-linus-trans-gossip-ct:停产的存储库-转到https

贝岭的matlab的代码-the-gossip-project:八卦项目

gossip-girl:网络创建练习

最新资源