Event/Emergency APRS Network Brainstorming

APRS is a wireless packet network system used by ham radio operators to transmit position information. Packets are encoded using the AX.25 data link protocol, which occupies the first, second, and third layers of the OSI networking model, and transmitted using half duplex radios usually on VHF or UHF frequencies. The default transfer rate is 1200 or 9600 baud. Packets are transmitted by a station and in general consist of a callsign to identify the sender, an icon/symbol code, a GPS string to show the sender’s exact position, and a short text status. It is also possible to send text messages or other small amounts of data.

Digipeaters are the basic nodes of the network, repeating signals from the stations to propagate them. The exact structure of the network is limited to the geography of the area and hardware available.

A basic representation of an APRS network can be achieved using a graph with the nodes representing the digipeaters and the edges representing which digipeaters can hear each other. In theory this would be an undirected graph, but on occasion phenomena arise which cause one digipeater to hear another, but not vice versa. This is a rare occurrence and will not be considered in most cases. The goal of a general purpose APRS network is to propagate the signal packet through the nodes to a certain depth from it’s original location.

In a general purpose APRS network, collisions between stations can and will occur as congestion increases, due to the almost random nature of transmission times. Collisions between the digipeaters should, however, be minimized.

In Event/Emergency Specific APRS, APRS is often used to track mobile emergency vehicles or event vehicles. The main difference of event specific APRS is that the stations have the ability to use controlled methods such as preasigned time slotting, so that no collisions will occur between stations.

For example, 10 stations transmitting position packets every 60 seconds can be programmed before the event to transmit one after the other every at 6 second intervals, allowing the most time possible for the signal to propagate through the network. Using the station’s GPS receivers to continually synchronize their internal clocks, they can achieve very accurate transmission times.

Beyond this, during an event the coordinators have more control over the content on the network, and can limit it to decrease network congestion. Messages or excess data for example, can be banned from the network, making relatively small standard packet length for all the stations in order to increase the number of time slots that can be assigned.

In a general purpose APRS network collisions and lost packets are considered acceptable. In an event/emergency specific APRS network, it should be engineered to have no collisions or lost packets as long as the station is able to be heard by at least one digipeater.

Generally, event specific networks cover a much smaller area. A general purpose APRS network might cover the entire country, but an event specific network will likely only cover some portion of a state and be perhaps less than 10 nodes.

A somewhat simplified version of the problem can be described as follows for a small event network,

• A station may be heard by any subset of the total digipeaters when it sends a packet
• Only one node or station should be transmitting on the network at a time to avoid any chance of collisions
• Time may be discretized into slots the length of the longest transmission time to send a packet
• It can be assumed that only one mobile station will send a packet at a time, and all other mobile stations will hold off a set amount of time in order to allow for that packet to propagate through the network (in other words, all stations will be time slotted)
• Packets should be retransmitted by all nodes exactly once
• A digipeater can tell if a packet was heard directly or by an adjacent digipeater
• A digipeater can tell if it has digipeated a packet before, either by each station including a timestamp inside the packet, or by the digipeaters just keeping track of anything they transmitted and received during a station’s time slot.

Therefore, the problem is how to propagate the packet through the entire network in the least amount of time slots, and taking into an account a digipeater’s only information is what it’s heard.

Method 1: Simple Algorithm to avoid collisions by use of delays

Even this very simplified and ideal problem, where stations will always transmit inside their time slots, proves to be a challenge to keep the digipeaters from colliding. Suppose you have a chain of digipeaters as shown below,

Even in this almost simplest layout, it’s impossible to get an efficient use of time slots when the number of digipeaters increases. Suppose we have a chain of 4 digipeaters such that, digipeater 1 can hear 2, 2 can hear 1 and 3, 3 can hear 2 and 4, etc.

Here is a simple way to ensure no two transmit at the same time.

If a direct packet hits digipeater 1, it can transmit immediately. However, if 1 hears a packet from 2, it must wait two timeslots to ensure that 3 and 4 are not transmitting (the case 2 hears the packet, but 1 does not).

If a packet is heard direct by 2, it can transmit only after a delay of 1 time slot to ensure 1 did not also hear the packet and repeat. If a packet is heard by 2 from 3, it must wait one timeslot to ensure that 4 does not transmit next (the case when 3 is the only one to hear the packet).

If digipeater 3 hears a packet direct, it must wait two timeslots to ensure that neither digipeater 1 or 2 are going to fill the time slot transmitting the packet. If 3 hears a packet from 4, it can transmit immediately.

If digipeater 4 hears a packet, it must wait three timeslots to transmit.

Now, suppose a packet is heard by digipeater 1. In this case, the path is 1->2->3->4 with no pauses. However, if 4 hears the packet, it must wait 3 timeslots to ensure neither 1, 2, or 3 are transmitting. It can then transmit the packet. After that, 3 can transmit the packet. Now when 2 hears a packet from 3, it’s possible that 3 was the first and only station to hear the packet, so 2 must wait a timeslot in case 4 has to go. The path then looks like,

P->P->P->4->3->P->2->P->P->1

For a line of digipeaters of length 6 the longest path is,

P->P->P->P->P->P->6->5->P->4->P->P->3->P->P->P->2->P->P->P->P->1

For a line of N digipeaters using this method, it takes 2N+[(N-2)+(N-3)+(N-4)+…+2+1]-1 = O(N^2) for the longest possible path. This is due to the fact digipeaters have no idea what’s going on further down the chain.

For a group of digipeaters where they can all hear eachother, a routing algorithm like this can be improved slightly, down to 2N hops worse case, but this is still too many to be useful for any sort of large network. Also, in most cases there will be some mix of digipeaters being able to hear eachother and being chained.

Because time slotting must be assigned to take into account the worse case propagation through the network, a better method is needed than simple logic on the digipeaters to ensure no collisions and higher throughput (such as a high speed back bone between digipeaters, multiple channels, request to send protocols, etc).