Skip to main content

more options


Introduction    top

"A GPS tracking devices capable of telling the user his/her approximate distance to buildings and attractions on a map downloaded from a remote station"

-Project Soundbyte

For our final project in ECE4760, we designed an GPS tracking device that has a capability of downloading maps from a remote server, and then calculating distances from buildings and attractions on that map. For our project, we mapped out the Cornell Engineering quad. Using a pushbutton, a user will choose which building/attraction to travel to. An LCD will indicate how far in what direction he/she is from each building and attraction on the quad. If there are multiple attractions of the same type (i.e., computer labs), the device will direct the user to the closest attraction.

The goal of our project was to design and fabricate an accurate positioning system using low cost, off-the-shelf measurement devices. Readings were made from one central device: a GPS unit that interfaced with our microcontroller. Using coordinates given by the GPS satellite, a position will be synthesized to present a real-time picture of the location of the target. Although the intended target of our positioning system is a human, the same system could be deployed on virtually any type of mobile object that does not experience significant yaw, e.g. a fixed-wing aircraft or a car.

Commercial GPS units are relatively straightforward devices; the complicated signal processing involved is handled by their integrated circuitry, and the user is sent position data over serial in a human-readable or binary format. Our task involves parsing this data for use in our algorithm. Our device is potentially useful especially for those unfamiliar with the engineering quad. Navigating to a building of choice is very easy do to the fact that we also display the target's relative direction to the desired building. The distance from the building is also calculated and displayed in real time, so a user can walk in any arbitrary direction, notice the trend, and quickly correct him/herself. Aside from buildings, our device also tracks two major attractions on a college campus: computer labs and food vendors. As they are distributed throughout the quad, our GPS tracking device is capable of locating the attraction that is currently closest to the target. The physical representation of our prototype map, Cornell Engineering Quad, is shown below:

Map of Engineering Quad

Physical map of Cornell Engineering Quad

The discrete points on the map are translated into something that the microcontroller can understand. Each building/attraction has its own distinct character. In convention with increasing longtitude and latitude, the map starts from the bottom right corner, traverses to the left, and returns to the next row on the the rightmost side and repeats. The first 40 lines are the actual map, the 41st line contains the boundaries of the map (maximum and minimum longitude and latitudes formatted by East, West, North South), and the subsequent lines indicate the key and label for the points on the map. The corresponding digital map for the microcontroller is shown below (note that only the entrances and exits are labeled for the builings:

0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0008880000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000999000000000000000000000000
7700000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
000000000000000000000000000000000000000:
000000000000000000000000000000000000000:
00000000000000;0000000000000000000000000
00;00000000111;0000000000000000000000000
00;0000000000000000000===000000000000000
0000004000000000<<0000000000>00000000000
0000004000000000000000000000000000000000
0000000204000000000000000000000000?00000
0000000204000000000000000000000000?00000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000010000000000000000000000000000000000
0000010000000000000000000501111100000000
0000010000000000000000000501111100000000
0000000000000400000000000005550000000000
0000004440000400000000000000000000000000
0000330000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000660000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
19787340,19788222,11049265,10980892,0000
none000000000000000000000000000000000000
Computer Lab0000000000000000000000000000
Food vendor00000000000000000000000000000
Phillips Hall000000000000000000000000000
Duffield Hall000000000000000000000000000
Carpenter Hall00000000000000000000000000
Olin Hall0000000000000000000000000000000
Rhodes Hall00000000000000000000000000000
Grumann Hall0000000000000000000000000000
Ward Hall0000000000000000000000000000000
Snee Hall0000000000000000000000000000000
Upson Hall000000000000000000000000000000
Kimball Hall0000000000000000000000000000
Thurston Hall000000000000000000000000000
Bard Hall0000000000000000000000000000000
Hollister Hall00000000000000000000000000
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

What is useful about our implementation is the ease and flexibility to create and send maps to our microcontroller. Virtually anything on the world can be mapped, and anyone can create a map, given the knowledge of the location of attractions relative to the latitude and longitude boundaries. This can be useful not only for students lost on a college campus, but for outdoor conventions, carnivals, festivals, and etc.

Logical Structure

High Level Diagram

High Level Diagram

The project consists of two modules. The remote module is composed of a microcontroller, a wireless unit, the onboard eeprom, a button, an LCD, and a GPS. The LCD provides updates to the user about nearby attractions, and the button serves to allow the user to select different attractions. The user’s position from the selected attraction is calculated on the microcontroller, and position data is relayed to the base station using the wireless unit. From the base station, the wireless unit receives maps containing annotated GPS coordinates. This data is stored in the EEPROM so we are limited to the size of the maps we can store. As shown above, our map of the engineering quad is broken down into 1600 discrete points, allowing sufficient resolution for each building and attraction on the quad.

Mathematical Background

[Insert Mathematical Background Here]

Hardware/Software Tradeoffs

GPS Chip

GPS Chip

GPS units return a position measurement uniformly distributed around the actual position. This will cause the GPS to appear to appear to ”jump” when standing in one place or moving at slow speeds. But because we update our position on the LCD in real time, a user can compensate for these unpredictable jumps by noticing the trends in increasing or decreasing distance. Also, because each of our discrete points are separated by a certain distance, we are inherently allowed a certain "jump radius" in which small deviations in the GPS signal would not greatly affect our calculated position on our device. Each point on our map is seperated by approximately 23 feet, specifically because this is the resolution that equally split our map into discrete 40x40 points. Because we are only using the onboard EEPROM, relatively large maps cannot be stored, because the resolution would be too large. Use of this EEPROM, however, allows us to save maps through power cycles, so that when the user enters a recognized position, the corresponding map can be used.

Standards Discussion

The GPS and wireless unit will communicate with our microcontroller via the USART interface, which uses EIA communication standards such as RS-232, RS-422, and RS-485. Specifically, this will be implemented on two RX pins and two TX pins, where the standard defines the data format and speed of communication between the pins. In order to interface with the GPS receiver, we will be using the NMEA 0183 standard, which uses an ASCII, serial communications protocol that defines how the GPS receiver will format and send messages to our microcontroller. Moreover, the operation of the GPS receiver is governed by the IS-GPS-200D specification. This interface specification defines the requirements, operations, and limitations of the use of the global positioning system. Since our GPS receiver will inherently follow this specification, the fulfillment of its requirements is already done for us.

The hardware for our project was fairly straightforward to set up. The GPS was connected to one serial port and the wireless module to the other. The LCD will be connected to PORTA, and the button is connected to PORTC. The same power source (3 AA batteries) will be connected to the GPS, the microcontroller, and the wireless unit. Because the wireless unit runs at 3.3 volts, a linear regulator will be included in series between the batteries and the GPS.

[Insert Hardware Diagram Here]

Things we tried that did not work

Our initial goal for this project, as stated in our proposal, was an indoor GPS device implemented using a 6 degree of freedom inertial measurement unit. We mapped out the first floor Atrium of Duffield Hall, and had specific attractions mapped on this atrium. The goal was to use positioning using the GPS until the fix was lost inside the building, and then measure distance traveled using the IMU. Although they both the GPS and the IMU measure position, they exhibit completely different classes of errors. The IMU displays a high level of precision, but is somewhat lacking in terms of accuracy. Each new measurement is estimated from the previous position using a technique known as dead reckoning. This causes the estimated location to ”drift” over time, as each subsequent reading compounds the error. However, over short distances, dead reckoning is a reasonable way to determine position. GPS units, on the other hand, return a position measurement uniformly distributed around the actual position. This will cause the GPS to appear to appear to ”jump” when standing in one place or moving at slow speeds. There are clear advantages to combiningthese two different measurements. The GPS can bring the IMU back on course when it begins to drift, and the IMU can discard bogus GPS readings.

We spent a great deal of time setting up the hardware for the IMU. Since it is also a 3.3V device, providing it 3.3V power was not an issue due to our level shifters. What was very problematic, however, was interfacing using the I2C bus. This was because we needed a bi-directional logic shifter from 3.3 to 5 and vice versa, in order to interface with our ATMega644p that needed to run at 5V, in order to use the 20MHz crystal like we wanted as well as power the LCD. We tried to solve our problem by using online documentation to build our own bi-directional logic shifter using mosfets in lab. This seemingly got the job done, because the I2C variables were returning success values. Also, after observing the SDA and SCL lines on the oscilliscope, they seemed to be properly pulsing. However, the values we were getting from the IMU were not what we expected. A closer look at the oscilloscope allowed us to discover that the logic was switching very slowly, likely due to the switching speeds of the mosfets. So we ordered new mosfets, capable of switching at high speeds at the low voltages we were giving it, and this allowed us to get good values out of the microcontroller.

After successfully interfacing with the IMU, we ran into another issue in calculating distance traveled. Using the IMU values, we integrated acceleration twice in order to get distance. What we discovered, however, was that this was not a very reliable way to calculate distance because it relied on the fact that the accelerations and distances are continuously changed. This was not the case, since we were updating IMU data only 10 times a second. This was not fast enough to capture the deccelerations that the IMU was actually experencing, and thus our code would maintain a velocity and quickly drift off of the grid. After consulting with Bruce, he told us that measuring distances with an IMU has widely been a tricky problem, especially with off the shelf devices that we were using. Therefore, we chose to forgo this part of our project and use the reliable portion, the GPS, and map out buildings and attractions to the engineering quad.

Our software revolves around a pseudo real-time scheduler in main.c The peripherals are polled at tunable intervals, and position data is relayed to functions responsible for updating location and displaying information. The general flow of execution is as follows: 1. The software starts and initializes the relevant registers to communicate with the peripherals and maintain the system clock. 2. The while(1) loop is entered. This checks the individual task timers, and executes the tasks when appropriate. It also handles the asynchronous loading of wireless data, which happens whenever new data is received. 3. A message indicating that a GPS fix is required is displayed until a GPS fix is acquired. The user is not able to perform any actions until a GPS fix is found. A GPS fix is detected by task2. 4. Immediately after acquiring a GPS fix in task2, the program will attempt to locate a map for the current location. The first place that is checked is the microcontroller's own EEPROM. If the data there is valid and the current location falls within the stored boundaries, then the stored map is adopted. The boundaries and number of attractions are loaded into main memory for fast access, but the rest of the information is left in the EEPROM to converve SRAM. If the data is either invalid or for a different area, the program will attempt to query a base station for a local grid. 5. The process of querying a base station for a grid begins with the unit sending a request for the first line of the grid. Once the first line is received, the unit requests another line. This process repeats until the entire grid is loaded. Then the microcontroller requests the boundaries, which are four integers representing the absolute eastern, western, northern, and southern points on the grid. These are used to contextualize the relative points on the grid and to identify whether or not this grid contains the current location derived from the GPS. Finally, the names of the attractions on the grid are loaded. Up to 20 attractions can be handled at the same time, and each one can have a label up to 16 characters. The flexible nature of the lables and points on the grid allows the designer of the map a large degree of freedom in describing his or her venue to the user. The map is also described using a human-readable ascii format in which each character has a one-to-one correspondence with a point on the grid, which makes it easy for any user with a text editor to update or create a map. 6. The bounds received via the wireless are checked against the current location to make sure that the grid is still relevant for the current location. If not, a new grid is requested. If the grid is relevant, it is saved to EEPROM so that it can be loaded after power-off without any need to query the base station again. 7. Armed with a grid and a GPS fix, the program can begin its normal sequence of execution. The scheduler checks the button, looks for new GPS data, and updates the display with the current distance to the user's selected destination. 8. The simplest task is checking the button. The button is debounced. Each new legitimate press selects the next attraction in the sequence. The user is displayed a temporary "calculating" message while the distance to the new destination is calculated. 9. Checking the GPS involves asynchronously filling a buffer with characters received over uart. Periodically the main loop checks to see if the buffer has been filled. If it has, it iterates over the buffer to extract the current position and to check the quality of the GPS data. The quality of the GPS fix is reported to the main loop which determines whether or not to ignore the data. 10. The most involved task is calculating the distance to the selected attraction. This is broken into a number of sub-tasks: a. First the current point is checked to make sure that it still falls within the grid's boundaries. If not, the main loop is immediately notified so that a new grid can be requested. b. Next, the program determines the nearest instance of the selected attraction. This involves a relatively naive search over all of the nodes in the grid, starting with the current position and increasing the radius by one point once all of the points within the current radius have been checked. c. Finally, the distance between the current position and the attraction is calculated and reported to the user. The most challenging parts to write were the distance calculation, data persistence, and interrupt-drive uart. The distance calculation was difficult because we had to convert from longitude to feet, find the nearest instance of the selected attraction, and calculate the distance to that point in a reasonable amount of time. Especially interesting was the conversion, because the number of feet per degree of longitude changes with latitude. Ultimately we decided to use an estimate; a constant factor that is approximately correct throughout the United States. A number of different alternatives were considered for the distance-calculating algorithm: breadth-first search, depth-first search, and a variety of logarithmic tree-based algorithms. Quickly, we determined that it was not possible to use a complicated data structure in order to represent a point on the map. In fact, to fit a map of any sort with reasonable resolution in the limits of the onboard EEPROM or SRAM, we could only use a single character for each point. This immediately eliminated any sort tree datastructure. Limited to an array of points, the most reasonable approach seemed to be the most simple; breadth-first search starting from the user's current location. To offset the inefficiency of this approach, it is performed only once each time the user selects a new attraction. After that the location of the attraction is cached and a new distance can be calculated using the new GPS location. Persisting data was a challenge not because of the complexity of the code involved - it was fairly simple to implement - but rather because of the challenge of deciding which data to persist. In the end we used 95.6% of the microcontroller's onboard EEPROM; there was very little space to add additional data. One location in memory was chosen to act as a flag indicating whether or not the other data was valid. This location is set with a hard-coded value after data has been fully loaded. It was necessary to store not only the label for each attraction, but also the number of attractions. Naturally the boundaries and grid were stored as well. Finally, we wrote our own interrupt-based serial routines in order to enable the use of two uarts in parallel. Blocking on the uart would render us unable to process GPS data while calculating distances, receving grid data from the base station, or even while checking the button. The GPS data and grid data arrive from the GPS unit and base station at their own pace, and failure to detect incoming data can result in serious delays. Furthermore, a 38400 baud rate results in only 4800 bytes a second and 3333 clock cycles per incoming byte with a 16 MHz clock; the processor is left idle for a significant portion of time. Fortunately, we separated the code into blocks based on peripherals, and each block received its own c file and header file. By using the header files to interface between blocks, we were able to make small tweaks to c files without affecting the rest of the code. This kept the number of lines of code in each file reasonable, greatly reducing the time required to track down a specific line of code. We were also able to specify the header files ahead of time, and then work independently to implement the actual c code.

The effectiveness and accuracy of our device was tested by actually taking it out to the map in use, the Engineering Quad. Short of actually taking a tape measure and measuring distance from the specific targets, a visual approximation can be made as to whether or not the the device was correct. As can be seen below, we are pleased with the accuracy of our device because it gives us 'ballpark values' of our distance from the buildings, consdering the 23 foot resolution and the variability of the GPS readings.

Duffield Test

Duffield Hall: 37 Feet South

Phillips Test

Phillips Hall: 135 Feet Southeast

Snee Test

Snee Hall: 462 Feet Southwest

Carpenter Test

Carpenter Hall: 249 Feet Northwest

In terms of the outdoor GPS tracking functionality, our results met our expectations. Even though there is significant room for error do the the resolution (which was limited by the size of the EEPROM) and GPS accuracy, our device seems very useable by anyone. While the distances may not be as accurate as a consumer GPS system which implement more filtering algorithms, the increasing and decreasing trends in distance allow the user sufficient knowledge of approximately where the their target is. We believe that this kind of device is useful for a new or visiting student that needs to find buildings or computer labs quickly. On a broader scale, the whole project can be useful for trade shows, conventions, festivals, and etc. that are held outdoors because maps can be easily customized for any given area.

In terms of our long term goals of implementing an indoor GPS, we were unsuccessful. We learned about the extreme difficulties of dead reckoning the hard way, which forced us to switch gears on our project very last minute. If given the chance, we would have better assessed the plausibility of our project. A possibility would be to collaborate with Aaron Ho's pedometer project, which we discussed in the very late stages. His group's project could approximate the distance traveled in a straight line. So coupled with a magnometer, we could have measured direction and possibly implement the indoor GPS functionality.

Intellectual Property Considerations

In terms of our final design project, we did not reuse any code, aside from the debouncing button code provided for us by Bruce. In the process of the design, while we were still attempting to use the IMU for an indoor GPS, we utilized I2C libraries made to interface with AVR processors that we obtained from Ryan Owens, whose github page was linked to the Sparkfun website. Moreover, we used libraries to interface with our accelerometer (ADXL345) and gyroscope (ITG-3200), written by Ninoshka Signh which were adapted from FreeIMU C libraries. As mentioned however, this code did not make it to our final design because we did not end up utilizing the IMU.

Our project is very similar to consumer handheld GPS devices available today through companies such as Garmin, TomTom, and etc. Our device is most similar to those that are typically used by hikers and those who need GPS devices on foot as opposed to the custumary use inside a vehicle. The ability to download and store maps is also a feature in these consumer devices. The difference in our device is the fact that it is catered not just to specific addresses, but specific buildings and attractions within those buildings. This just requires more detailed maps to be used by our device. What is interesting about our device is the ease and flexibility of creating a map. While consumer GPS devices today posses the ability to download maps from a remote server, these maps are restricted to the ones made by the specific company. Our device allows anyone to create a map of virtually anything with little time/training. While the possibility of purchasing an indepdenent device for these purposes may have been useful in the past, nowadays a smartphone is a much more convenient way to do so.

Ethical Considerations

In terms of a GPS tracking device, the obvious issue of user privacy comes into play. In light of the recent controversies associated with Apple and Google in relation to location data logging of their customers, we had to take these events into consideration. Our device records your immediate result for distance and direction calculation, but it does not store this location in some sort of data structure. In this sense, our device is memoryless so we do not track the locations of the user.

On a different note, since our device has the capability to locate attractions at a certain location, the question of logging these chosen attractions comes to light. Therefore, one can theoretically make implications about a user's personal life, interests, and habits, depending on which attractions they are most drawn to. Once again, this issue is mitigated by the fact that our device does not do any data logging of the user. However, the only thing we do store is the map of the location on the EEPROM of the device in order to maintain location awareness through power cycles. So by checking the EEPROM, we are able to tell at which specific location the user was, but this location is not stored or transmitted anywhere else.

FCC Regulations

Since we utilized two RF transmitters (for the remote and the base, both of which are FCC approved), we needed to consider the FCC regulations that we must operate by. Firstly, we must consider the frequency ranges that our transceivers operate in (902 - 928 MHz). In this operating range, our RF device does not violate any of the constraints set out by the FCC radio spectrum allocation. Moreover, we must consider our device in terms of the maximum exposure limits to RF radiation as laid out by the FCC. Our device falls under the 300 - 1500 MHz category, so we must ensure that the power density is within the allowed limited, f/300 mW/cm2. After examination of the data sheet, we discover the maximum power output of our transceiver as seen in the figure below. Therefore, the maximum power that our transceiver can emit is under DTS mode at +12 dBm = 15.85 mW. Considering that our device will be about 606 cm2, our expected maximum power density is 15.85 mW/606 cm2 = 0.26155 mW/cm2. Since our device is operating at 902 MHz, our threshold power density is 902/300= 3.007 mW/cm2, much lower than our expected maximum power density.

Radio Specifications

Power output of our radio tranceivers.

Hardware Schematic

Hardware Schematic

Cost Details

ITEM QUANTITY FULL NAME TOTAL PRICE SOURCE
-- -- -- 38.3 --
LCD SCREEN 1 LCD 8 Lab
AA Batteries 8 AA Batteries 0 Project Team
Battery Holder 2 Battery Holder 0 Lab
Microcontroller Board 1 Custom PC Board 4 Lab
Max233CP 1 Max233CP 7 Lab
RS232 Connector 1 RS232 Connector 1 Lab
Microcontroller 1 ATMEGA644P 8 Project Team
Wireless Module 2 Wi.232DTS-EVM-R 0 Project Team
Header Sockets 70/td> Header Sockets 3.5 Lab
Button 1 Button 0 Project Team
Wire (feet) 2 Wire 0 Lab
DIP Socket 2 DIP Socket 1 Lab
Power Supply 1 Power Supply 5 Project Team
RS232 Dongle 1 RS232 Dongle 0 Lab
6DOF IMU 1 IMU Digital Combo 0 Project Team
GPS 1 LS20031 0 Project Team
3V Linear Regulator 1 3V Linear Regulator 0 Project Team
Resistors 4 Resistors 0 Lab
NAND gate 1 PK41AA 0 Lab
Mosfets 2 DMN26DO 0.8 Digikey

Task Breakdown

Edgar Roque:
- Interface with IMU using the I2C bus
- Extract and filter IMU values
- Create graphical and character maps
- Create programs used to simulate GPS strings for testing
- Convert GPS coordinates to feet
Brian Toth:
- Interface with the GPS chip using the serial bus
- Interface with base station via radio tranceivers
- Parse GPS string for useful information
- Implement distance algorithm to calculate distance from target

Datasheets

GPS Datasheet
Accelerometer Datasheet
Gyroscope Datasheet

Source Code

Our source code can be found here:
uart0.c
main.h
ADXL345.h
defs.h
main.c
locate.c
gps.c
display.c
definitions.h
gps.h
i2c.h
imu.c
imu.h
ITG3200.h
lcd_lib.c
lcd_lib.h
uart0.h
uart1.c
uart1.h