摘 要

近年来，随着具有无线通信能力的移动智能设备逐渐普及，具有延迟容忍可间歇性的机会网络逐渐成为研究的热点。机会网络是一种利用节点移动带来的相遇机会实现通信的网络，具有无中心、大规模、高度动态的特点。机会网络常用于困难条件下的通信，例如灾后紧急通信、偏远地区通信等场景。对于这种高度不稳定的网络，Gossip算法具有简单、高效、可扩展的特点，使其逐渐成为一种的普遍用于机会网络研究的重要工具。本文使用Gossip算法解决机会网络中的一致性问题。本文做的第一件事，就是提出了一种基于Gossip算法的路由协议，可用于实现消息在机会网络的高效扩散。本文做的第二件事是在ONE模拟器中提出来一种解决广播问题的方法，使得消息扩散的机制更加灵活。

关键词： Gossip，机会网络，高效扩散，ONE

Abstract

In recent years, with the mobile intelligence equipment with wireless communication capabilities gradually popular, intermittent opportunity network which is delay-tolerant and intermittent has gradually become a hot research.Opportunities networks are often used for communication in difficult conditions, such as post-disaster emergency communications, remote area communications, and so on.Opportunity network is a network that uses the node‘s meeting caused by node moving to achieve the communication, with no center, large scale, high dynamic characteristics. For such highly unstable network, Gossip algorithm is simple, efficient and scalable, and gradually become an important tool for the network of opportunities. This paper uses the Gossip algorithm to solve the problem of consistency problem in the opportunistic network. The first thing to do in this paper is to propose a routing protocol based on the Gossip algorithm to achieve the efficient diffusion of the message in the opportunistic network. The second thing to do in this article is to present a solution to the broadcast problem in the ONE simulator,making the mechanism of message diffusion more flexible.

Key Words： Gossip, Opportunity network, efficient diffusion, ONE

第一章 绪 论

1.1本文的研究背景及意义

近年来，随着具有无线通信能力的移动智能设备逐渐普及，具有延迟容忍可间歇性的机会网络逐渐成为研究的热点。机会网络是一种不需要源目节点之间有完整通信路径的，利用节点移动带来的相遇机会实现通信的网络。机会网络常常用来在困难环境下实现通信，比如灾后紧急通信、偏远条件下的困难通信，也可以用于野生动物追踪、车载网络等多种情况。Gossip算法本质上是一个泛洪的过程，具有简单高效的特点。本文将利用Gossip算法解决机会网络中的均值问题，希望提出一套合理的方案，求出机会网络下节点值的平均值、最大值、最小值。

1.2 机会网络概述

1.2.1机会网络定义

机会网络还没有一个统一的定义，通过对机会网络特点的分析，本文给出一个描述性的定义：机会网络是一种不需要源目节点存在稳定路径，利用节点移动带来的相遇机会实现通信的自组织网络。在无线网络中，无线自组织网络和无线传感器网络一直是研究和应用的热点。由于这两者没有考虑节点的稀疏分布和节点的快速移动的情况，导致其在很多情况下无法正常使用，比如高速移动的动车上、偏远无基站地区等。由于节点移动、节点稀疏、射频关闭或由于障碍物造成的信号衰弱等原因，导致网络拓扑被划分成多个不连通的子域。通信中的源节点和目的节点之间只有不连续或者根本就不存在连通的路径，传统无线网络无法使用。机会网络就是来解决这种困难条件下的通信问题，机会网络利用节点的相遇机会，源节点将消息转发给中间节点，当中间节点移动到合适位置时，再把消息转发给目的节点，从而实现源目节点之间的消息交换。

1.2.2机会网络特点

机会网络不要求源目节点之间有完整的通路，仅仅利用节点移动过程中产生的相遇机会，逐跳转发进行通信。机会网络是在传统无线自组织网络的基础上改进而来的，因此也具有自组织、无中心、多跳等特点。但由于机会网络考虑了节点的稀疏性和节点的移动性，不要求通信节点之间连通，因此还具有以下特点：

（1）传输延迟较高。由于机会网络中，节点分布十分稀疏，节点快速移动，导致网络拓扑变化复杂，通信链路具有间歇性。端到端之间没有完整可靠的路径，数据往往要经历很多次转发，很长时间后才能发送到目的节点，因此，高延迟是机会网络的重要特点。

（2）间歇性。机会网络中的节点具有移动性，在通信链路中断之后，不会丢弃已经接受的数据，而是继续将数据存储，等待合适的机会转发。因此，间歇也是机会网络中常有的现象。

（3）对节点的缓存大小和电池容量要求较高。由于机会网络在转发的过程中会一直将数据存储在本地缓存中，当网络规模变大之后，对节点的缓存大小提出了较高的要求。另外，由于节点的移动，网络中的节点需要重复进行邻居发现，对设备的电池容量也会有不小的压力。

1.2.3机会网络原理

机会网络利用中继节点进行转发，扩展了网络空间范围，提高了网络容量。研究表明，在传统无线自组织网络中，节点对之间的吞吐量会随着节点数量的增加而降低，节点数量增加，网络中的干扰增加，造成了网络容量的瓶颈。近来Crossglauser等人研究^[1]证明，在允许节点移动的情况下，提高数据的延时可以增大网络容量。基于此理论，它们提出通过中继节点缓存消息来提高网络容量的方法。这是机会网络的理论基础。

机会网络的路由模式与传统自组织网络不同，采用“存储-携带-转发”的工作模式。源节点产生数据之后，如果和目的节点在同一个通信域之内，可以直接将消息转发到目的节点；如果不在同一通信域，则需要将消息转发到合适的中间节点。中间节点存储该数据，进行移动，并重复该过程，直到遇到目的节点，完成消息的投递。和传统路由方式不同的是，机会网络中没有路由表，而是选择合适的转发节点，这一过程叫做机会转发。因此，在机会网络中，路由协议的关键是如何选择合适的转发节点并选择合适的转发时机。

图1.1 机会网络中消息发送过程

如上图1.1，机会网络中某节点A要给节点C发送数据，但是此时两个节点A和C处在不同的通信域，也就是说它们之间没有直接的链路可以通信。此时，节点A先将数据转发给通信域内的节点B，节点B将数据缓存在本地。随着节点B的移动，节点B进入了节点C的通信域，节点B再将消息转发给节点C，完成了数据从节点A向节点C的转发。

1.2.4机会网络应用

机会网络对数据传输时延和网络的间歇中断具有一定容忍度，利用节点的移动带来的相遇机会来携带数据，通过“存储-携带-转发”的机制进行通信。在很多场景下，这种特点使得机会网络具有传统自组织网络不具有的优势。例如在受灾或偏远地区网络传输、车载网络、节假日交通枢纽、野生动物追踪、海洋通信区域等场景下，蜂窝移动通信网络和无线局域通信网的负荷过重^[2]，甚至处于瘫痪状态，而这些场景也无法提供稳定的全连通网络，此时利用机会 网络仍然能够实现节点间的有效通信。机会网络的通信方式考虑了实际的通信条件和需求，在很多场景下能发挥巨大作用。

1.3本文的主要工作

机会网络中节点的移动性造成拓扑时刻变化，端到端之间很难有一条完整的通信路径，使得机会网络下路由方式不同于传统网络。机会网络中的一致性问题还是要通过消息的交换来实现，解决机会网络下的路由问题是其关键。机会网络模拟器ONE本身也不支持消息的广播，采用一种合理的方式将消息扩散到每一个节点，也是本文的问题。在解决机会网络一致性问题的过程中，本文主要做了以下工作：

（1）首先介绍了机会网络的定义，机会网络的特点，机会网络原理，以及机会网络的应用。

（2）本文对Gossip算法有关的论文做了大量的阅读，了解了Gossip算法相关的研究历史，算法有关的基本概念，算法的交互模式，算法的应用。

（3）机会网络模拟器是本文主要用到的工具，因此，本文对机会网络也做了有关研究，对ONE模拟器的软件结构，移动模型，路由模型，事件模型和报告框架做了说明。

（4）本文大量阅读了机会网络的各种路由协议，对机会网络下经典的直接路由算法和Epidemic路由算法做了介绍，并在其基础上设计了Gossip路由算法。

（5）为了满足在机会网络中扩散value值消息的要求，本文对机会网络模拟器进行了修改，为消息类型添加了value属性，在结点DTNHost类型中添加了求平均值、最大值、最小值的方法。

（6）机会网络模拟器ONE不支持消息的广播，也就是说，在ONE模拟器中，一个消息只能从一个节点发给一个节点接受。为了将各个节点的value快速扩散到网络中的所有节点，本文提出一种利用OneToEach消息事件发生器和设立孤立节点，实现消息广播的巧妙方案。

1.4本文的组织架构

本论文主要包含五个部分，各部分的主要内容如下安排：

第1章 绪论

本章主要介绍机会网络的定义、特点、原理以及应用，本文的研究背景和意义，以及本文的组织结构。

第2章 Gossip算法综述

本章对Gossip算法的相关概念进行了综述，介绍了Gossip算法的概念、特点以及应用。

第3章 机会网络模拟器ONE概述

本章对本文使用的主要工具THE ONE机会网络模拟器做了研究和说明，分别对ONE模拟器的软件结构、移动模型、路由模型、事件模型和报告模型以及配置方法做了介绍。

第4章 Gossip路由算法

本章首先对机会网络的两种经典路由算法，直接路由算法和Epidemic路由算法做了介绍，然后在其基础上，提出来Gossip路由算法。

第5章 广播解决方案

本章首先对机会网络模拟器进行了修改，使其消息类型支持携带value值，使其DTNHost类型支持对平均值的求取。本章还介绍了ONE模拟器中消息事件发生器，提出了种利用OneToEach消息事件发生器和设立孤立节点，实现消息广播的方案。

第6章 仿真配置

采用第4章提出的Gossip路由协议和第5章的广播方案，本章对机会网络中的均值问题进行仿真求解。首先介绍了仿真的配置情况，然后对仿真的结果进行了简单的分析。

结论与展望

总结全文的工作，指出本文所做的主要工作，同时对本文在求解均值问题时的部分缺陷进行说明。

第二章 Gossip算法综述

在将Gossip算法运用到机会网络路由之前，本文对Gossip算法做了大量的学习，详细阅读了文献[3]。

1972年Hajnal等人^[4]第一次提出了Gossip问题：有n个妇女，每个人都知道唯一的一条谣言，他们之间可以通过电话联系。任意两个妇女通过一次电话联系之后，互相交流彼此知道的所有流言，求最少多少次电话之后，每个妇女都知道所有的谣言？1988年Hedetniem等人^[5]对计算机网络环境下的Gossip问题作了数学定义：假设Ａ是由网络中所有节点组成的集合，每个节点都有自己特有的信息，需将其传播到网络中其它所有节点，用有序的节点对 ∈A序列表示信息的传播过程，每个节点对表示两者之间存在信息交换，当序列的最后一个节点对完成交互后，所有节点都知道所有信息，称为Gossip过程结束？需要多少次信息交换Gossip过程能够结束,需要多长时间？

Gossip算法被提出后，马上得到了研究者的关注。自上世纪50年代到70年代，有关Gossip算法的研究层出不穷，人们关注的热点是寻找一种合理的模型来描述Gossip算法的运行过程。1972年Galton Waston提出了简单分支处理模型^[6]，使得对Gossip问题的研究有了基础的理论工具；在此基础之上，1975年Bailey对Gossip算法作了深入详细的研究^[7]；之后，马尔科夫链成了研究Gossip算法的新工具。之后的10年里，有关Gossip算法的研究热度下降。随着网络技术飞速发展和复杂网络深入研究，Gossip算法得到了新的研究，近20年在P2P网络构造及维护、数据库复制、分布式环境下的聚集计算等领域，涌现了大量关于Gossip的研究成果。