algorithm - 如何在时间上间隔相邻的无线传输？

Question

我有一个很有趣的问题，以前可能已经解决了，但我不确定该去哪里找。
形势
我正在开发一个系统，包括：
移动无线节点
节点每1000毫秒广播一个信标
节点可以从其他这样的节点听到信标
信标包括关于发送者的信息（这是唯一的，比如mac地址）
信标可以在一定范围内包含其他信息（例如关于其他邻居的信息）
要求
我正在尝试开发一种算法和实现：
获取相邻节点在1000毫秒（给定的正负10毫秒公差）内在“虚拟插槽”上对齐。
在彼此的无线电范围内最多可容纳4个相邻节点（即时隙数为4，即250毫秒+/-10毫秒）
可以通过观察单独工作（即完全分散）
可以容忍已对齐的邻居集彼此进入范围（即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 ------------------------------------------------------------------------------> 

当前想法/指南
无线电通信为未确认/广播信标，因此无法确认射频链路然而，如果节点包含在自己的信标中，那么它们可以共享足够的信息。
例如，在上面的例子2中，如果A能听到B，那么A的信标可以包括“B在我之后250毫秒”同样，如果B能听到A，那么B的信标可能包括“A在我之后750ms”。
有了这种类型的信息，这个问题开始看起来很像一个网络图问题，每个节点可以根据它能听到的节点和它们依次能听到的节点从自身向外构建。我曾研究过诸如生成树协议之类的东西来获得灵感，但还没有太多的运气。
问题
虽然这看起来像是一个网络图问题，但真正的问题是如何改变信标的定时。
实际上，算法回答了“我应该移动自己的信标吗？”如果是，是哪个方向？”，但它考虑了：
邻居们搬家有多难（也就是说，如果他们已经有了一个很好的社区）？
我的邻居将如何搬家（即我们两个搬家，还是只有一个人搬家）？
实际问题
Soooo，在发了很多短信之后，我的问题是：
有谁知道这种行为的例子吗？
你认为创建图形是个好主意还是坏主意？
你认为这张图会妨碍我真正想做的事情吗-暂时的空间？
逐步趋同是个好主意吗？
虚拟老虎机是个好主意吗？
这是否与stp并行，但我们可以有多个根节点？
顺便说一句：我对无线/MAC层的解决方案不感兴趣，这确实是一个应用程序问题！
编辑：最终结果
我从没想过要解决这个“插班”的问题。相反，我们的节点只是远离了任何冲突。也就是说，我们并没有试图为开槽算法制定一个解决方案，而只是做了一些尝试空间均等但可能导致振荡的事情。

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。我甚至不认识那里命名的算法，但至少看起来有一些工作可以参考。在“分散算法”中，它们还将应用程序引用到无线信道分配，因此其中一些可能与您想要的非常接近。