Thursday, October 2, 2014

What's The Channel Capacity Of The ADS-B System

If you've seen my twitter feed lately you may have noticed I've been playing around with ADS-B, the system used by commercial planes to report their position and other details.  I find it an interesting topic and a great way to get into software defined radio.  For just $20 you can start to play around with a TV tuner dongle and map air traffic in your local area.  As usual I wanted to get down into the nitty-gritty and find out more about how the protocol works, particularly how many planes it can support at once.

First of all we'll take a quick overview of how the system works.  The ADS-B traffic I'm interested in occurs at a frequency of 1090 MHz and consists of frames/packets that are 112 microseconds long with a 8 microsecond preamble, a total of 120 microseconds.  All of the data a plane transmits can't fit into a single frame, so there are different types transmitted, some are initiated by the plane, some are initiated by ground radar systems, some are required twice a second, some are required every 5 seconds.  We'll get to this later, but for now I want to look at the pure throughput of the channel.  It may seem simple, but as the number of planes/stations transmitting increases, the probability that they'll "talk" over each other increases, and frames start to collide.  If we take this example to an absurd extent and assume there are infinite planes, the throughput of the channel will be zero because the planes will always be talking over the top of each other.  There's a sweet spot that can be found.

Grey frames are ones that have collided

If messages are 120 microseconds long, it should be easy to determine the probability of collisions at certain data rates.  First though, a few assumptions need to be made.  Planes transmit their ADS-B frames whenever they want.  There are communication systems that only transmit at certain time periods (slotted systems), and some listen to the channel and wait for it to be clear before sending (carrier sense multiple access), these methods reduce collisions, increasing the throughput of the channel.  In the case of ADS-B, it's hard to find information on how it's actually done, so I'm going to assume the random transmit method, which is the basis for ALOHAnet, the first public demonstration of a wireless packet data network.  So most of the analysis has been done for us.  In fact the images (with attribution) in this blog have come from the Wikipedia article for ALOHAnet.  This article is going to apply the theory of the ALOHAnet to ADS-B.

Another assumption that needs to be made is the signal strength coming from different stations/planes.  We'll assume that all the signals are received at the same level, and will therefore collide.  In reality a plane transmitting 150 km away, will get lost in the signal of a plane transmitting 500 m away and will not be seen as a collision.

The final assumption to make is that the simple CRC checks in some of the ADS-B messages aren't used to correct the signal.  If that were the case small collisions would be OK, but let's keep things simple.

Frames transmitted between t0-T and t0+T will collide with the yellow test frame

Firstly define the time taken to transmit a frame as T, and also define G as the average number of transmission attempts per frame in Erlangs.  In the above image it can seen that any frames transmitted in the period from t0-T to t0 will collide with the start of the yellow test frame, and any frames transmitted in the period from t0 to t0+T will collide with the end of the yellow frame.  From this we can see the probability of a successful transmission of the yellow test frame is equal to the probability that no other frames are transmitted during the period between t0-T to t0+T.  A period of 2T.

If the arrival distribution is modelled as a poisson process the probability that k frames are sent in a time period of 2T is equal to


By setting k to zero we can see the probability of no other frames sent in this time frame.


This gives a throughput in frames per frame period of


The maximum value of S can be easily found.


So, the maximum throughout is 0.184 frames per frame period, and this occurs at a channel load of 0.5 Erlangs.  This is demonstrated in the graph below for the Pure Aloha system.
Throughput vs load for slotted and pure Aloha
Now to bring this all back to ADS-B is rather simple.  T is simply the 120 microseconds mentioned earlier.  We know the maximum throughput is 0.184 frames per frame period, which in this case is 0.184 frames per 120 microseconds which is equal to 1533 frames per second.

1533 is the number of frames per second supported in this instance, but it's not the number of planes.  Each plane is required to transmit location and velocity frames twice a second.  They are also required to transmit a flight ID frame every 5 seconds.  This means at a bare minimum the plane is transmitting 4.2 frames per second.  I'm unsure if the plane is required to transmit it's position twice a second or position frames twice a second (there is a difference).  ADS-B uses a strange compression method called compact position reporting to transmit the latitude and longitude of a plane.  Two frames are required for a full latitude and longitude position.  I'm going to stick with 4.2 frames a second but it could be 6.2 frames per second.

Taking the number of 4.2 frames per second per plane as a minimum means that there can't be more than 1533/4.2 = 365 planes visible to a receiver at any one time.  Even that's an unlikely scenario, because at that point there are quiet a few frame collisions occurring. Having said that there will always be some collisions.  At maximum capacity of G equal to 0.5, the probability of no collisions in two frame periods is equal to e^(-1) = 0.368, if the load were reduced by a factor of 10 this becomes e^(-0.1) = 0.905, so although the probability of a collision is reduced.  It's still around 10% which is not insignificant.  This load represents a more realistic number of planes, 36 (365/10) , detected by an ADS-B station.  So obviously there's somewhere in the specification for ADS-B that defines an acceptable level of frame collisions, but because it seems to be a propriety standard, we can only guess what that number is.

The point of this article was to get a feel for the capacity of ADS-B.  My numbers are a ballpark figure.  I'm doing some coding and I need to figure out if I can handle the incoming data using the method I plan to use.  I'm pretty sure I can.

Further Reading
http://defenseelectronicsmag.com/site-files/defenseelectronicsmag.com/files/archive/rfdesign.com/mag/512RFDSF3.pdf
http://www.homepages.mcb.net/bones/SBS/Article/Barebones42_Socket_Data.htm

References
http://users.ecs.soton.ac.uk/sqc/EL336/CNL-7.pdf
http://en.wikipedia.org/wiki/ALOHAnet

2 comments:

  1. Grant, this is interesting information. My system maximizes at some 250 live aircraft at 1200 frames/s (as reported by dump1090) received on a collinear antenna. It's my belief that the total number of observed aircraft would be higher when using directional antennas thus limiting the collisions.
    Your article shows that in my area the theoretical boundary's of ADSB do become an issue.
    paul

    ReplyDelete
    Replies
    1. It's good to see some real world numbers for an ADS-B situation. I live in Brisbane Australia and it would be rare to see more than 50 aircraft at a time, so the capacity of the channel isn't really an issue. I didn't consider directional antennas, but yes you're right, it would limits collisions and pick up more aircraft in a specific direction.

      Delete