摘 要

随着移动智能终端的普及，人们对移动网络的需求也逐步扩大。本文就Android系统下蓝牙网络的小范围大规模通信进行试探性研究。蓝牙网络通信技术自爱立信公司于1994年提出以来出色的解决了很多短距离通信问题，然而由于最初的设计理念，在规模稍大的网络中暴露了低效、短距的等一些列问题。Gossip算法基于其设计理念，在大规模网络中能够保持快速收敛、高效传输、稳定、可容错，而且有很好的可扩展性的优点。同时，在Gossip算法的结构下，节点数据的同步机制和数据分布策略，能够出色的完成无中心，大规模，动态分布的网络环境任务。基于Gossip算法的种种优势，本文将在蓝牙网络通信中，主要对数据的简单数的的求平均值、最大值、最小值和普通数据的同步以及一致性计算进行实验性探索。最终所得结果对于在小范围内大规模数据通信和数据同步有重要意义。研究结果表明：Android系统蓝牙通信的Gossip算法实现。在小范围内对于多节点的数据通信和数据同步有着较好的效果。

关键词：Android系统；蓝牙通信；Gossip算法

Abstract

With the popularity of mobile smart terminals, people's demand for mobile networks has gradually expanded. This article on the Android system under the Bluetooth network of small-scale large-scale communication for tentative research. Bluetooth network communication technology since the Ericsson company in 1994 since the outstanding solution to a lot of short-range communication problems, but because of the initial design concept, in a slightly larger network exposed inefficient, short distance and some other issues. Gossip algorithm is based on its design concept, in large-scale network to maintain fast convergence, efficient transmission, stable, fault tolerant, and there is a good scalability advantages. At the same time, under the structure of Gossip algorithm, the synchronization mechanism and data distribution strategy of node data can accomplish the network environment task without center, large scale and dynamic distribution. Based on the advantages of Gossip algorithm, this paper will try to find out the average, maximum, minimum and normal data synchronization and consistency calculation of the simple number of data in Bluetooth network communication. The final result is important for large-scale data communications and data synchronization in a small area.

Key Words：Android system; Bluetooth communication; Gossip algorithm

目录

摘 要 1

Abstract 2

第1章 绪论 1

1.1 研究背景以及研究目的与意义 1

1.1.1 Gossip算法简介 1

1.1.2 Gossip算法的发展历史 1

1.1.3 Gossip算法在蓝牙通信中的意义 2

1.2 国内外研究现状 2

1.3 蓝牙通信网络中Gossip算法的难点 3

1.4 本文的主要内容 4

1.5本文结构安排 4

第2章 Gossip算法的论述 6

2.1 Gossip算法介绍 6

2.1.1 网络结构模型 6

2.1.2 时间模型 6

2.1.3 Gossip优劣的考量标准 7

2.2 Gossip算法的常用交互方式及其收敛速度分析 8

2.2.1通信条件 8

2.2.1 通信协议 9

2.3 Gossip算法的数据结构及讨论 10

2.3.1 在有限网络负载下Gossip算法的协调机制 10

2.3.2 Gossip算法的数据结构 11

2.4 本章小结 12

第3章 基于安卓蓝牙的APP交互实现 13

3.1 安卓系统蓝牙通信的Gossip算法的交互过程 13

3.2相关技术介绍 14

3.3 系统设计 14

3.4 概要设计 15

3.5 详细设计 15

3.5.1界面设计 15

3.6开发工具 16

3.7 安卓蓝牙通信的Gossip算法的优势 16

3.8 本章小结 17

第4章 基于安卓蓝牙Gossip的一致性计算的实现 18

4.1 平均值与求和 18

4.2 最大值与最小值 19

4.3 测试 19

4.3.1 测试环境 20

4.3.2 测试方法和测试用例 20

4.4 本章小结 20

第5章 总结与展望 21

5.1 总结 21

5.2 展望 21

参考文献 22

致谢 23

第1章 绪论

本章主要论述了Gossip算法的研究背景、研究目的和研究意义，简单介绍了Gossip问题的提出、Gossip算法的概念、Gossip算法的发展历程、Gossip算法在国内外的研究现状。

1.1 研究背景以及研究目的与意义

1.1.1 Gossip算法简介

Gossip算法来源如其名，灵感来自办公室绯闻传播，只要绯闻传播一下，在有限的时间内，办公室内的所有人都将会知道该绯闻的信息，因此Gossip又被称为“闲话算法”、“谣言传播算法”、“疫情传播算法”、“病毒感染算法”。但是Gossip并不是一种新型算法，如泛洪查找、路由算法都属于“感染算法”范畴，与之不同的是Gossip算法有着明确的语义、具体实施方法和收敛性证明。因为在一个网络中，Gossip算法不需要节点知道所有其他节点，所以Gossip算法具有去中心化的特点，故节点之间事完全对等的，因此Gossip算法不需要中心节点。更多的是，Gossip算法是一个最终一致性算法，虽然无法确保在某时刻全部的节点都状态一致，但是可以保证在“最终”状态时网络中的所有节点状态一致，“最终”是一个现实中存在，但理论上无法确定所以也无法证明的时刻。在实际的场景应用里，Gossip算法可以许多能接受“最终一致性”的领域派上用场，例如：路由同步、动态负载均衡等。

1.1.2 Gossip算法的发展历史

1972年，Hajnal等一群学者第一次给出了Gossip问题的描述,具体如下：有n个人，每个人都知道一条与其他人不同的的谣言，他们之间通过电话进行谣言信息的分享；任意两人互通电话之后，互相分享自己当前知道的所有谣言信息并记住听到的新的谣言；那么，他们之间最少需要进行多少次联系，才能确保使得每个人都知道全部的谣言？此次事件让很多学者们对谣言问题正式展开了研究^[1]。

经过长期的总结，在1988年，Hedetniem等人对计算机网络环境的Gossip问题做出了详细的规范的描述，其具体描述如下：A是由计算机网络环境中所有节点组成的节点集合，每个节点都有自己独有的信息，并且每个节点都需要将自己的信息传给当前的计算机网络中的其他节点；令节点对(i,j)i,j∈A来表示信息的传播过程，每组节点对表示该节点对内的两个节点之间存在信息交换；当全部的节点对中的最后一个节点对完成同步后，全部的节点对就完成了通信，此时，该网络环境中的全部节点都将会得到各个节点的信息，此阶段称为Gossip过程结束^[2]。那么，到底需要进行多少次的节点信息交互，才能确保Gossip过程结束，这是Gossip问题研究的重中之重。