updated 21 jan 2023
new dec 2015
Flock and Peep protocols for Arduino-style MCUs.
Flock is a non-hierarchical, self-negotiating radio messaging protocol. Flock (and Peep) protocols are entirely timer-based. It is designed to carry message payloads, which consist of keyword::number pairs, with a heavy emphasis event signaling.
The code is contained in a single (library) object that contains the Flock/Peep protocol logic, which in turn loads the NRF24L01+ driver module. This code requires an event-loop style coding scheme. All of the code is non-blocking. It's fairly lightweight, and runs fine on an Uno (Atmega328).
This description of the Flock and Peep protocols accompanies the state diagrams and code. This glosses over some of the details in the interests of getting the big picture across.
Birds are physically distributed over a geographical area, ideally within radio range of each other, or at least overlapping ranges.
The Flock protocol's purpose is to get a number of individual birds on the same channel so that they can inter-communicate, and communicate with a Flock Nest if one exists. Flock is straightforward: any bird can communicate at any time, asynchronously. If maximum power-saving is not required Flock is a fine end state. Peep protocol synchronizes all birds and offers packet queuing to allow powering the radio off 80&percent; of the time for substantial power saving. Peep requires no protocol awareness in the application program.
The application program needs no knowledge of protocol operation. The API is simple:
Flock.begin (CEpin, CSNpin); ... byte * p= Flock.getRxBuff(); ... int r= read(); // read() is non-blocking if (r > 0) { // r is packet length, data in rxBuff ... int r= Flock.write (byte * p, int len); // r= bytes written else -1 ... void nextChannel (bool markBad); void setChannel (unsigned ch); void setMinChannel (unsigned n); void setMaxChannel (unsigned n); unsigned getChannel(); void dynamicChannel (bool d); void setFlockLoopRate (unsigned n); void setNestID (char id); void setIdentity (char id); char getIdentity (void); void debug (bool n); void setPALevel (byte n); void promiscuous (bool f); char * getRxBuff(); unsigned getRxPower(); byte * getChanErrorMap ();
Additional methods exist for setting identity, upper and lower channel limits, transmitter power, promiscuous reception, etc. The only mandatory configuration is identity (bird name).
read() returns special packet types that identify Peep phases
and if promiscuous is true, any and all packets received instead
of just those addressed to this bird/broadcasts.
In my current Solar Bird application there is a loose userland protocol that causes ICMP-ping-like message propagation through all birds in the network, and these will traverse non-direct bird to bird connections.
At power-up/reset, a bird has no knowledge of neighbors, if any exist. Seek phase consists of selecting a random channel, and for a set period sending queries and listening for responses. If an acceptable response is received Seek ends, otherwise the process repeats with a new random channel.
On-channel phase begins when Seek hears a valid packet on the current channel. The channel, in the logical sense, is considered usable as long as any valid packet, payload or protocol, is heard on the channel. If the channel goes quiet for an extended period birds issue query packets to elicit response. If the channel times out, Seek phase is restarted. Otherwise, and normally, in on-channel phase birds may exchange payload packets.
The NRF24L01+ radio supports 125 channels of 1 MHz bandwidth each. Flock uses channels 60 to 80 (configurable); my experience is that high and low channels are less reliable.
Flock maintains a "bad channel" list. If, during on-channel phase, a bird fails to receive a packet for sufficient time, that channel is marked as "bad" and a new channel selection.
New channel selection is made by selecting a random channel that is not in the bad-channel list, and is different from the previous channel. To prevent the unlikely occurrence of running out of channels due to "bad" marking, 5% of the time one previously bad channel is un-marked. This also allows re-trying previously-bad channels where interference may have been severe, but short lived.
Bad-channel marking occurs only in on-channel phase, specifically not in Seek phase.
Each bird has a tick clock, started at power on. Its interval currently two seconds. While on-channel, birds issue a TICK packet containing a one-way negotiation token each time the timer fires. Other birds receiving this TICK may choose to synchronize their tick timer with this senders'. This results in on-channel birds eventually having synchronized TICK timers.
A given bird cannot know if it is the only bird, or if other extant birds have discovered neighbor(s) of their own, or not. Since each bird does it's own channel discovery (Seek), birds may form disjoint "island" flocks, on different channels.
An on-channel phase sub-protocol gathers disparate islands of birds into one flock by sporadically issuing GOTO packets on random channels not the current on-channel. GOTO packets contain this-on-channel and a one-way negotiation token. GOTO suggests that an un-seen "other" flock join the current one. With the same goal, that other flock may later suggest that "this" flock join theirs. The one-way negotiation is biased in favor of the initiating bird, and by the number of birds doing so (flock size); see TOKEN section for details.
Given that birds power-on/reset independently, may go silent due to run-down batteries or other reasons, Flock packet transmission and reception is stochastic. Both Flock and bird user code sends messages both scheduled and event-driven, but there is no coordination of scheduling timers (not the purpose of TICK). Bird events sent often elicit response from receiving birds, and cause cascades of relatively intense radio activity, then fall back to sparse and sporadic activity. Therefore for Flock radios are on 100% of the time, and a power drain on batteries.
Peep protocol synchronizes birds to send and receive within a narrow time window, on a negotiated schedule. This allows Peep birds to power radios off for 80&percent; of the time, to conserve power.
Peep relies on the fact that birds using Flock protocol will receive Peep transmissions by simply waiting long enough for the Peep window to open.
Peep can begin as soon as the tick timer is synchronized. Peep reverts to Flock if N seconds goes without a TICK or data activity in TX phase; TICK is Peep's "keep-alive". Peep does all of it's protocol-overhead communication within the window. User payload that would be sent immediately and asynchronously by Flock is queued and dequeued on-schedule by Peep.
Once synchronized, Peep protocol steps through three phases each timer tick interval (2 seconds).
RX phase begins when the tick timer fires. It is here that TICK synchronization occurs. Given the inherent timing jitter it is not possible to know which birds are yet listening, hence this phase is receive-driven.
For each valid packet received from a given bird, if there exists a packet addressed to that bird in the transmit queue, it is dequeued and transmitted to that bird.
Birds respond to protocol packets in this and TX phase, such as those sent by birds still in Flock protocol. The responses generally are to direct the sender to in-sync with the recipient bird's flock.
RX phase lasts a generous 200 milliseconds.
TX phase begins after RX phase. Any packets remaining to any recipient are dequeued and transmitted, with variable and random timing. Protocol packets received are responded to. TX phase is currently 300 milliseconds, though the transmit queues are generally empty in a dozen milliseconds.
At this time birds turn their radios off and nothing happens. This is lower-power phase. However nest leaves it's radio on, will respond to all received protocol packets and any payload packets.
Quiescent phase ends when the tick timer fires to begin RX phase.
Peep uses a software timer and a TICK packet type to synchronize all reachable birds in the flock. When a bird's tick timer fires, the radio is turned on and a TICK packet sent. Birds which had previously turned their radios on may receive this TICK packet. If the tick arrives within TICKWINDOW milliseconds (currently 10) no action is taken. If the timing error is larger than that, rock-paper-scissors logic decides if the synchronization offer is accepted or ignored.
Of course only birds whose tick timers fired earlier will have their radios on to receive a TICK packet; and the TICK packet these earlier bird(s) sent may not have been received. If a bird somehow drifts very late and misses all TICKs issued by earlier birds, the protocol will timeout, revert to SEEK phase, and resync with the first TICK received in Flock.
Therefore birds only receive "late" TICK packets, never early ones. Considering all possible pairs of birds, only one will have received the others' TICK packet, maximum. However a nest, which has it's radio on all the time, will receive late TICK sync and will use rock-paper-scissors to decide to honor it.
Bird-to-bird timing jitter is approximately 10 milliseconds. When the tick timer fires a TICK packet is issued.
(A known but narrow limitation to TICK synchronization is that it is possible, however improbable, to have "time islands"; birds on the same channel but in disparate TICK sync. The solution, not yet implemented, is the sporadic issuance of a "WHEN" packet off-schedule but on channel, analogous to GOTO channel packets. I'll get around to this when I have a larger number of birds to work with.)
An additional mechanism biases bird tick synchronization to favor TICK packets that are received close to it's own tick timer. This mechanism has little effect on small flocks.
When a bird's tick timer fires, it clears a "tick bias" counter, that increments with every TICK packet reception. When this bias exceeds a threshold (TICKTHRESH) each additional tick count over that threshold lowers the rock-paper-scissors token received from the TICK initiator; this reduces the probability of accepting the sync offer.
There is a special node (bird) type called the nest, or base. It creates a loose hierarchy with some advantageous features. It is identified by having a unique address, @.
The nest/base state machine differs slightly: nest radio is on full-time. In Seek phase GOTO packets are ignored. Nest also broadcasts GOTO packets on all non-selected channels with token IWIN. See the code for details.
It is assumed that nest/base is attached to a desktop computer for gathering flock data and managing the flock.
Packets are simply the 32-byte maximum fixed packet size native to the NRF23L01+. Payloads are SRMessage text strings containing name::value pairs, and described elsewhere, except protocol packets which are a mixture of ASCII and binary (yes, a design misteak).
All packets contain one-byte destination and source addresses, an ASCII letter [A-Za-z]. Nest gets a special name, @ rarely is there a second nest, mostly for protocol-stressing and testing. For this I use #.
Protocol packet types are one of the reserved "ASCII graphic" characters; packets are discerned by switch() of type, and default case is payload. The particular byte arrangement to the right of type ie type-dependent.
The Flock and Peep is stateless and cooperative. One-way negotiation is used to solve organizational problems and indicate the severity/importance of a requested function.
Given that all birds are peers, negotiation between two birds is done with rock-paper-scissors; modular arithmetic. One change has been made to the typical method: in the case of a tie, a win is given to the initiator of the negotiation. This builds in a convenient and tunable bias. Two tokens provide additional options; IWIN and ILOSE pre-destine the outcome.
The intent of negotiation is to coalesce birds into a single flock. If each negotiation had equal A vs. B odds, two island flocks might oscillate instead of converge. Negotiation bias and automatic conciliation resolve this.
Tokens are numbers in a small space, 0..TOKENSPAN. The values at each extreme, 0 and TOKENSPAN-1, are reserved as magic values, namely ILOSE and IWIN. Tokens created for negotiation are always inside these boundary values. A larger space, move values, moves the odds closer to 1:1; lower span values favor the initiator because the test is "greater than or equal to", the "equal to" providing a +1 advantage to the initiator for the tie. (In classic rock-paper-scissors a tie is resolved by selecting again.) Tokens are numbers pulled from a Margolis pseudorandom generator, modulo TOKENSPAN-2, plus one. TOKENSPAN is currently 9 (14% advantage for initiator).
To attempt a timer-tick synchronization, the initiator creates a new token, A, and sends a packet of type TICK containing this token. Upon reception, the receiver creates token, B using a Margolis PRNG and does a simple arithmetic comparison, (A ≥ B). If the result is true ("initiator wins") the recipient's tick timer is synchronized to the initiators, plus radio overhead time. If the initiator loses, nothing happens.
On-channel birds sporadically issue GOTO packet broadcast ("go to [my] channel nn") to random off channels, any channel not on-channel, where there may be other birds (or an entire flock). A new token is created and sent each time.
There may or may not be a bird to receive this packet; an existing bird may be in seek phase or on-channel. A Seek phase recipient accepts the GOTO packet as-is, no negotiation, switches to that channel, and enters on-channel phase. An on-channel recipient creates it's own token, B, performs the (A ≥ B) test as above, and if A wins, two things happen: the bird broadcasts it's own GOTO packet containing the new channel and an IWIN token, then immediately switches to the new channel. On-channel means it has at least one peer; the GOTO nn IWIN packet will cause it's peers to accept the proposal (IWIN), re-send GOTO nn IWIN, and switch channels. This would runaway into infinite resends if it were not for the fact that each bird then leaves the channel. If the initiator loses (recipient wins), no action is taken.
Since senders/protocol initiators tend to win due to the comparison bias, the flock with the largest number of member birds will win over time, as they in turn send out more off-channel GOTO packets than smaller flocks.
The bias in comparison is A ≥ B, combined with the statistical bias of more biased requests.
These are state diagrams that look like 60's flowcharts because that's what Monodraw can do.
