I have a rather interesting problem that has probably been solved before, but I'm not really sure where to look.

The situation

I am developing a system that consists of:

• mobile wireless nodes that move around
• the nodes broadcast a beacon every 1000 milliseconds
• the nodes can hear the beacons from other such nodes
• the beacon includes information about the sender (that is unique, like a MAC address)
• the beacon can include other information to a limit (such as info about other neighbours)

The requirements

I am trying to develop an algorithm & implementation that:

• gets neighbouring nodes to align themselves on 'virtual slots' in the 1000ms (given +/- 10ms tolerance)
• tolerates up to 4 neighbouring nodes within radio range of each other (i.e. the number of slots would be 4, i.e. 250ms +/-10ms)
• can work through observation alone (i.e. is fully decentralised)
• can tolerate sets of already aligned neighbours coming in range of each other (i.e. 2 + 2 = 4)
• gets nodes to converge on the slots gradually by lengthening or shortening beacon period to 1001/999ms respectively
• makes no assumptions about the bidirectionality of the radio link

E.g. some example topologies that should work are:

• 4 nodes that can all see each other

   A-B
   |X|
   C-D
  

• long lines that can see at most 4 neighbours

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

Examples of how the algorithm COULD work

Example 1 -A & B close to each other, algorithm decides B should move towards the right

                  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 ------------------------------------------------------------------------------>

Example 2 - A & B aligned, algorithm decides C should move towards the left

                  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 ------------------------------------------------------------------------------> 

Current ideas / guides

The radio communications are unacknowledged/broadcast beacons, so confirmation of the RF link is impossible. However, if the nodes included in their own beacon the identifiers of their neighbours they can kind of share enough information.

e.g. In example 2 above, if A can hear B, then A's beacon could include "B is 250ms after me". Likewise, if B can hear A, then B's beacon could include "A is 750ms after me".

With this style of information this problem starts to look a lot like a network graph problem, where each node can build outwards from itself based on the nodes it can hear and the nodes they can hear in turn. I have looked into things like Spanning Tree Protocol for inspiration but haven't had much luck yet.

The problem

Although it looks like a network graph problem, the issue is really how to shift the timing of the beacons.

In essence, the algorithm answers the question "Should I move my own beacon? If yes, which direction?", but it takes into account:

• How hard it is for neighbours to move (i.e. if they already have a well optimised neighbourhood)?
• How will my neighbours be moving (i.e. will we both move apart, or should just one of us move)?

Actual questions

Sooooo, after quite a lot of text, my questions really are:

1. Are there any examples of this behaviour anyone knows about?
2. Do you think that the graph creation is a good/bad idea?
3. Do you think the graph will just get in the way of what I'm really trying to do - space temporally?
4. Is gradual convergence a good idea?
5. Is the virtual slot idea a good one?
6. Does this have parallels to STP, but that we could have multiple root nodes?

BTW: I'm not interested in Radio/MAC layer solutions to this, it really is an application issue!

EDIT: The End Result

I never got around to solving this "slotting" idea. Instead our nodes just moved away from any conflicts. I.e. instead of trying to develop a solution to the slotting algorithm we just made something that would attempt to space equally but that could result in oscillations.

I suggest that you break this up into two distributed algorithms that you can find written up.

1) Distributed clock synchronization. Have all nodes agree on a common time base, using algorithms such as those used by NTP. At this point, and maybe for some time, there may not be a common agreement in time to separate different transmissions, but you can use http://en.wikipedia.org/wiki/ALOHAnet#The_ALOHA_protocol while this is a problem.

2) Distributed graph colouring. One starting point is http://en.wikipedia.org/wiki/Graph_coloring#Parallel_and_distributed_algorithms. I don't even recognise the algorithms named there, but it at least looks like there is work you can refer to. Under "Decentralized algorithms" they also reference applications to Wireless Channel Allocation, so some of this might be quite close to what you want.