如何暂时间隔相邻无线传输？

Question

我有一个相当有趣的问题，之前可能已经解决了，但我不太确定该去哪里。

情况

我正在开发一个系统，其中包括：

• 四处移动的移动无线节点
• 节点每 1000 毫秒广播一个信标
• 节点可以听到来自其他此类节点的信标
• 信标包含有关发送者的信息（这是唯一的，如 MAC 地址）
• 信标可以包含一定限度的其他信息（例如有关其他邻居的信息）

要求

我正在尝试开发一种算法和实现：

• 让相邻节点在 1000 毫秒内在“虚拟槽”上对齐（给出 +/- 10 毫秒的容差）
• 在彼此的无线电范围内最多允许 4 个相邻节点（即时隙数为 4，即 250ms +/-10ms）
• 可以仅通过观察来工作（即完全去中心化）
• 可以容忍已经对齐的邻居组进入彼此的范围内（即2 + 2 = 4）
• 通过将信标周期分别延长或缩短至1001/999ms，使节点逐渐汇聚到时隙上
• 不对无线电链路的双向性做出任何假设

例如一些应该有效的示例拓扑是：

• 4 个节点都可以互相看到

   A-B
   |X|
   C-D
  

• 排长队最多只能看到4个邻居

   A-B-C-D-E-F-G-H-I
           | 
           X-Y-Z
  

算法如何工作的示例

示例 1 -A 和 B 彼此靠近，算法决定 B 应该向右移动

                  1000                2000                3000                4000
0   250  500  750   0   250  500  750   0   250  500  750   0   250  500  750   0
|    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
A                   A                   A                   A                   A
                     >>                  >>>>                                  
 B                     B                     B                   B              
Time ------------------------------------------------------------------------------>

示例 2 - A 和 B 对齐，算法决定 C 应该向左移动

                  1000                2000                3000                4000
0   250  500  750   0   250  500  750   0   250  500  750   0   250  500  750   0
|    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | 
A    B              A    B              A    B              A    B              A
                                      <<                <<<<                 
                   C                 C                 C                   C
Time ------------------------------------------------------------------------------> 

当前的想法/指南

无线电通信是未确认/广播信标，因此无法确认 RF 链路。然而，如果节点在自己的信标中包含邻居的标识符，那么它们就可以共享足够的信息。

例如在上面的示例 2 中，如果 A 可以听到 B，则 A 的信标可以包括“B 比我晚 250 毫秒”。同样，如果 B 可以听到 A，那么 B 的信标可能会包含“A 比我晚 750 毫秒”。

有了这种类型的信息，这个问题开始看起来很像网络图问题，其中每个节点都可以根据它可以听到的节点以及它们依次可以听到的节点从自身向外构建。我研究过诸如生成树协议之类的东西来寻求灵感，但还没有太多运气。

问题

虽然它看起来像一个网络图问题，但问题实际上是如何改变信标的时间。

本质上，该算法回答了“我应该移动自己的信标吗？如果是，朝哪个方向移动？”的问题，但它考虑到了：

• 邻居搬家有多难（即如果他们已经拥有一个优化良好的社区）？
• 我的邻居将如何搬家（即我们会分开搬家，还是应该只有我们一个人搬家）？

实际问题

Sooooo，在写了很多文字之后，我的问题确实是：

1. 有任何人知道这种行为的例子吗？
2. 您认为创建图表是好还是坏主意？
3. 你认为图表会妨碍我真正想做的事情——时间空间吗？
4. 逐渐收敛是个好主意吗？
5. 虚拟老虎机的想法好吗？
6. 这与 STP 是否有相似之处，但我们可以有多个根节点？

顺便说一句：我对无线电/MAC 层解决方案不感兴趣，这确实是一个应用程序问题！

编辑：最终结果

我从来没有抽出时间来解决这个“插槽”的想法。相反，我们的节点只是远离了任何冲突。 IE。我们没有尝试开发槽算法的解决方案，而是做了一些尝试均匀间隔的东西，但这可能会导致振荡。

Answer 1

我建议你将其分成两个分布式算法，你可以找到书面的。

1）分布式时钟同步。使用 NTP 等算法，让所有节点都同意一个共同的时间基准。此时，也许在一段时间内，可能还没有一个共同的协议来及时分隔不同的传输，但是您可以使用 http://en.wikipedia.org/wiki/ALOHAnet#The_ALOHA_protocol 虽然这是一个问题.

2）分布式图形着色。一个起点是http://en.wikipedia.org/wiki/Graph_coloring#Parallel_and_distributed_algorithms。我什至不认识那里命名的算法，但至少看起来有你可以参考的工作。在“分散算法”下，他们还引用了无线信道分配的应用程序，因此其中一些可能非常接近您想要的。