1 一个简单分布式算法

物联网通常具有网络不稳定，速率低，分散较广的特点。

没有毫无用处的算法，那是没有遇到合适的场景。

1.1 需要解决的问题：

1，高速网络 与 延迟缓慢的网络， 需要 确保所有进程 使用相同的频率 与高速网络通信。

2，如果当前使用的频率出现问题，需要切换频率。

1.2 问题特点：

1，信息是幂等的，

如果高速网络切换到不同的频率，新的频率不依赖于旧的频率。

接受新频率的进程 可 只更新频率。而不管旧频率是否更新。

2，信息量小

可用在小数据包中轻松跨节点传播。 例如 频率可用编码为 64位的整数。

1.3 解决思路：

算法的基本思想是 跨进程 存在人工时间 概念，
用于对事件或信息进行排序，而无需求助于进程的 系统时间，这在它们之间很难同步。

这个人工时间误差称为 “纪元”。 每个进程都有 currentEpoch的概念，即在启动时 初始化 为0
每当一个进程看到一个大于 其当前 epoch 的 epoch时，它就会更新它的 epoch 以匹配观察到 epoch。

每个进程也有 frequencyEpoch概念，即当前使用的频率的版本。

每个进程定期向其他进程发送更新消息。 以传播信息。例如，每5秒每个进程选择一个随机进程，并向它发送一个更新消息，其中包含：当前使用频率，使用频率的纪元 以及发送 更新消息的进程 currentEpoch

第一次创建进程时，其频率设置为 -1 ， 这表示 从给定进程的角度看，当前没有使用频率，必须选择另一个频率。

1.4 更新操作：

当一个进程接收到 来自另一个进程的更新消息，其中包含一个 频率 Epoch 大于其本地 frequencyEpoch的频率，它将其频率更新为接收值，并将 frequencyEpoch设置为 接收值

当currentEpoch 或 frequency 和 frequencyEpoch被修改时，进程将此变化写入磁盘或其他永久存储，以便进程重新启动时 使用最新的已知信息。

1.5 选择频率

一个流程需要在 两种不同的场景选择频率

		1，检测到当前 频率有噪声
		2，当前频率设置为 -1 时（启动时）

1.6 工作原理

1， 进程增加自己的 currentEpoch，并将其写入永久存储。还选择 合适的新频率。

2， 该进程向所有其他进程 发送一个 ELECT_ME 数据包以获得其他进程的投票。ELECT_ME数据包包含 发送进程的 currentEpoch

3， 只有当它们的 currentEpoch 与请求投票的进程之一相比不大时，其他进程才回复YOU_HAVE_MY_VOTE 数据包（包含投票过程 currentEpoch）。

接收ELECT_ME数据包将导致更新旧的 currentEpoch匹配传入的数据包之一。

4，给定进程在 给定的 epoch内只 投票一次，所有它需要一个名为 lastVoteEpoch的变量。

只有在投票请求中 currentEpoch大于 lastVoreEpoch时 才会提供它的投票。当投票被提供时，lastVoteEpoch 被更新。（投票前存储在 磁盘，这样崩溃和重启不会导致 再次投票）。

5，YOU_HAVE_MY_VOTE 消息的currentEpoch小于请求投票进程的currentEpoch将被丢弃。

6，如果进程被选中，它将更新它的 frequencyEpoch和频率变量，将使用的 grequencyEpoch是 进程请求投票的 纪元，即它发送 ELECT_ME数据包时currentEpoch，就在增量之后。

一个进程需要被选举 来改变频率，并且每个进程在给定的 epoch中投票一次，在给定的epoch中必须只有一个获胜者。

如果给定的进程无法获得大多数未达成的过程，则会在随机延迟之后再试一次。

与用于交换这些消息的慢速网络延迟相比，此延迟必须更大。 每个进程都会在小于重试的一段时间后 认为选举中止。

1.7 新信息的 传播

当一个进程 赢得选举时，它将其频率值和频率更新为新的，因此通过发送更新消息，最终所有其他进程都将获得更新，并切换到新频率。

如果某进程被分区， 它将在 分区回复后立即收到更新。

然而一旦进程改变频率，就尽快向所有进程广播UPDATE消息 是一个好主意，这样所有其他节点将尽快切换。

1.8 算法改进

通过添加 frepuencyEpoch 值来改进 ELECT_ME 数据包，这样如果进程有 陈旧的信息，其他进程将拒绝投票。

例如，这可能发生在过程被分割一段时间的旧频率时，该频率由于噪声太多而无法正常工作。

大多数 进程 已经切换到 新的频率。

当分区恢复时，进程可能会被 选举 并在 有机会接收 更新的频率之前 将频率更改为其他频率，从而导致无用的频率切换。

通过在 ELECT_ME 数据包添加 grequencyEpoch并让其他进程提供投票之前检测信息是否更新，可用避免无用的切换。

2 小结：

仅在当前频率 确实 嘈杂时 才提供投票。
这避免了在高带宽无线电中 出现硬件问题的单个节点将能够连续切换到 新频率。

因为每个频率都会被检测为 有噪声，这样只有当大多数节点检测到当前频率有问题时，才发生频率切换。