A web application and a few digital elevation models can significantly ease the pain of building wireless networks in remote areas.
If you're trying to build wireless community networks out in the hills, like the NoCat Network has done in Sonoma County, California, the first thing you discover is that hills eat Wi-Fi signals for lunch. Wireless networking technologies such as 802.11b/g need line-of-sight to establish a connection, and any significant amount of intervening terrain, trees, or buildings between two points will quickly ruin your chances of setting up a long-distance, point-to-point wireless connection. In places where DSL and cable are unavailable, however, point-to-point community wireless links are often the only way that local residents can get high speed Internet connectivity, so there's a lot of motivation to find ways to work with the surrounding terrain.
Naturally, the first question a newbie asks when they show up at a community network meeting is, "Can I get on the network?" The answer is, inevitably, "That depends. Where do you live?" Armed with the GPS coordinates of the newbie's house, you can do a certain amount of terrain analysis using digital elevation models (DEMs) in commercial software such as TopoUSA [Hack #96] or free software such as GRASS (http://grass.ibiblio.org). The downside to this is that, if you have 50 would-be participants in a community network, the total number of possible links to evaluate is, apropos of nothing else, 50 x 492 = 1225. That's a lot of work to do by hand!
7.2.1. NoCat Maps
We knew there had to be a better way. My ambition was to create a tool that would allow a community member to get their house on the NoCat Network with nothing more than a compass and a Wi-Fi card with a high-gain antenna. Rich Gibson demonstrated that, using GRASS, he could extract elevations from 10-meter resolution USGS DEMs along the line connecting two locations, and use that to plot a contour profile with Perl and the GD:: Graph module from CPAN (http://www.cpan.org).
If the elevation of the straight line in three dimensions between those two points is less than or equal to the elevation at any point along that line, it means there's a hill in the way, and a link probably won't be feasible. If the elevation of the line-of-sight is above ground elevation along the whole distance, a wireless connection might be possible (but see "The Caveats" later in this hack, for some exceptions).
We took the contour profiler from GRASS and combined it with a web-based network node database, so that any new locations would be automatically tested against all existing locations for link viability. Finally, we added a rudimentary address geocoder based on TIGER/Line data for users who didn't know their GPS coordinates already. The result was NoCat Maps, which now lives at http://maps.nocat.net.
Now, when people come to NoCat Network meetings and ask how they can get on the network, they're told to go to the web site and add themselves to the database. If they know their GPS coordinates, they can enter them there; otherwise, their address is looked up in the TIGER/Line database of Sonoma County. The application analyzes the elevation profile along the line-of-sight to every other possible node and then presents the user with a list of possible connections, as shown in Figure 7-1.
Figure 7-1. Viewing likely point-to-point links at a glance
The listing of possible links comes sorted by clearance: approximately how much room a link has to spare, given the intervening terrain, ignoring Fresnel zones and other potential radio problems. Antennas are assumed to be at least 5 meters off the ground, so the maximum possible clearance is about 16 feet. A negative clearance indicates the presence of a hill at least that high in the way.
Additionally, since we know the latitude and longitude of both points, we can calculate the straight-line distance and true bearing for each possible link. This means that, if you know that there's a live antenna at a given node, and NoCat Maps suggests that a link might be possible, you can go outside with a Wi-Fi card and your own high-gain antenna and a compass and give it a shot before you ever show up at a meeting.
Rich's original contour profiler has been preserved, as well. If you click the View link next to any pair of nodes in the node listing, you get a detailed view of the prospective link, with a Google Map depicting the line-of-sight and a graph showing the elevation profile between them. Figure 7-2 shows a potentially successful link, while Figure 7-3 shows one doomed to failure.
This view offers some other features as well. First, likely lines-of-sight are listed at the bottom of the page. Second, clicking on the graph opens a full-page version of the same. Finally, the Google Map can be used to get a sense of what's in between points A and B, by zooming in and perhaps by switching the map to Satellite Mode. This will give you a much better idea of potential buildings and trees, which the line-of-sight data will not include.
Figure 7-2. A possible point-to-point link
Figure 7-3. This is not the link you are looking for; move along
7.2.2. Installing Your Own Profile Analyzer
If you don't happen to live in Sonoma County, you can set up a copy of NoCat Maps on your own web server. First, you'll need to install the requisite C libraries:
Next, you'll want to install all of the Perl modules. Your best bet is to use the CPAN shell to get all of the code at once, by running the following command:
# perl -MCPAN -e 'install NoCat::Profile'
This command will go out to the Comprehensive Perl Archive Network (CPAN), download the Perl libraries for NoCat Maps, and then install them, along with all of their Perl module prerequisites.
If this is the first time you've run the CPAN shell, you might have to walk through configuring it first, but the configuration process takes only a few minutes and comes with mostly sensible defaults. The CPAN shell should then install the following Perl modules, which are listed here for completeness's sake:
For building the actual profile analyzer.
The Template Toolkit, for generating HTML pages.
For converting lat/long coordinates to UTM. This prerequisite may be removed at some point, since the GDAL library is capable of doing cartographic transformations, as well.
For looking up the lat/long of street addresses via http://geocoder.us.
For storing nodes and links in a database.
Optional, for generating elevation graphs.
Optional, for using the SQLite standalone database.
Next, you'll need to get the source distribution of NoCat Maps, in order to install the other components. You can download the code from http://maps.nocat.net. The tarball will be called something like NoCat-Profile-x.xx.tar.gz. Untar it in a convenient place. If you chose not to install the libraries using the CPAN shell, you can build and install the NoCat Maps libraries as follows (assuming you have all the other prerequisites from the CPAN):
$ ./configure $ make # make install
Finally, copy the following directories to somewhere on the filesystem where your Apache web server can see them:
Contains the actual profile analysis script
Contains the CGI scripts that form the application UI
Contains the Template Toolkit templates for the web interface
7.2.3. Getting the Elevation Data
In the United States, you can obtain elevation data for your area from http://seamless.usgs.gov. You'll want to get the 1/3 arc-second National Elevation Data (NED), which comes at about 10m resolution. The data comes in a Zip file named with a long string of digits. Inside the Zip, the data is in ArcInfo Grid format, which you'll want to unpack and convert to GeoTIFF as follows, using the gdalwarp tool from GDAL:
$ unzip 01234567.zip $ gdalwarp -t_srs "+proj=utm +zone=10" -co "TILED=YES" 01234567/01234567 elevation.tif
Universal Transverse Mercator (UTM) projection and is a useful cartographic projection for doing this type of geospatial analysis. You will need to find out what UTM zone you're in and fix the zone=10 portion above to match. Zone 10 is the west coast of the US, where this software was originally written. You can find a map of UTM zones at http://www.dmap.co.uk/utmworld.html.
Since the maximum download size from http://seamless.usgs.gov is about 60 MB, and your area of interest is of any significant size, you'll wind up having to download multiple files and merge them together as follows:
$ eg/gdal_merge.py -o merged.tif 01234567/01234567 0987654/0987654 … $ gdalwarp -t_srs "+proj=utm +zone=10" -co "TILED=YES" merged.tif elevation.tif
The gdal_merge.py script comes from the GDAL distribution but is also included with the NoCat Maps distribution for convenience. You will definitely need the Python bindings for GDAL installed in order for the data merging to work.
If you're outside the United States, you won't be able to use the USGS NED dataset, but you can get WRS2 tiles of NASA's Shuttle Radar Topography Mission (SRTM) data at 90m resolution from http://www.landcover.org. Since these tiles will already be in UTM format for your zone, you should simply tile them internally for efficient lookups:
$ gdal_translate -co "TILED=YES" p201r24.tif elevation.tif
If you have access to other, better elevation data sets, by all means use them, but do make sure they're in the UTM projection for your particular area. If they're not, use gdalwarp (as shown in the previous example) to convert them.
Now that you've created your elevation model, you'll want to copy it some place that your Apache web server can access it from.
7.2.4. Setting Up the Application
Having installed the code and assembled the elevation data, we're ready to configure the application. Create a newSQL database somewhere, and load the appropriate schema for your database server from the eg/ directory in the distribution. You can use SQLite, a lightweight standalone database, but if you decide to do so, you'll need to install the sqlite3 executable for your OS. You can get the source code for SQLite 3 from http://www.sqlite.org. Then, load the database schema as follows:
$ sqlite3 node.db < eg/nodedb.sqlite $ chown apache node.db (or whatever user your webserver runs as)
You'll want to put the node database somewhere convenient. Note that both the database file itself and the directory that contains the database file must be writable by your Apache server. Of course, if you want to use a real database, you can just as easily load the supplied MySQL schema or, with a bit of editing, use the same schema for PostgreSQL.
Next, install and configure Apache, if you haven't already. The configuration in your httpd.conf for the VirtualHost on which the profiler will run will probably look something like this:
ServerName maps.nocat.net DocumentRoot /home/www/maps.nocat.net/docs ScriptAlias /cgi-bin/ /home/www/maps.nocat.net/src/cgi-bin/ SetEnv MAP_CONF /home/www/maps.nocat.net/db/map.conf
The SetEnv parameter in your httpd.conf tells the application where to find its configuration file. An example copy of this map.conf file can be found in the eg/ directory in the distribution. Place a copy of it in the location you specified for the MAP_CONF environment variable in the previous step. If you don't specify a value for MAP_CONF, the CGI scripts default to looking for map.conf in the directory above the one they're running in.
Wherever you put your map.conf file, you will want to customize it accordingly, of course. Here's what the default map.conf configuration looks like:
Database dbi:SQLite:/www/maps.nocat.net/node.db DB_User map DB_Password censored Template_Path /www/maps.nocat.net/src/tt2 Script_Path /www/maps.nocat.net/src/bin Elevation_File sonoma_ned_utm.tif Node_Height 5 Geocoder_URI http://rpc.geocoder.us/service/xmlrpc Contact_Email firstname.lastname@example.org GMaps_API_Key [Add Your Google Maps API Key Here]
The Database parameter specifies the Perl DBI connect string for your database. The string is case sensitive and always starts with dbi:, followed by SQLite, mysql, or Pg for PostgreSQL. You might need to refer to the appropriate Perl DBD:: module documentation for details. The DB_User and DB_ Password options are what you'd expect, and are unused if the database runs in SQLite. The Template_Path and Script_Path parameters should point to wherever you put the tt2/ and bin/ directories earlier.
The Elevation_File parameter should point to the GeoTIFF you made earlier, while the Node_Height parameter specifies how far above ground level (in meters) we assume antennas to be situated, on average. The default value is five meters. The Geocoder_URI parameter specifies the address of an XML-RPC service for looking up the coordinates of street addresses. The default behavior is to use the geocoder.us service, which is free for non-profit use, so you probably won't want to change this. See http://www.geocoder.us for more details.
The Contact_Email address is used in various places in the application's templates. Finally, the GMaps_API_Key parameter specifies your Google Maps API key, which you will need in order to be able to show Google Maps on your site. You can sign up for an API key at http://www.google.com/apis/maps/signup.html, and cut and paste the long alphanumeric string into the map.conf file. Be sure not to leave a line break in the middle of the key.
7.2.5. Starting Your Elevation Profiler for the First Time
Now that everything's set up, visit the URL you configured in Apache for the service. Try the add_node.cgi script, and add a couple of newnodes. If all goes well, the elevation profile between the two nodes should be plotted when you add the second node, and you should be able to view the profile graph to verify that everything is working.
Unfortunately, much of the facility for editing and removing nodes themselves is absent from the UI itself, so keep your command-line database client handy. Much of this will be addressed in an upcoming release of the code.
7.2.6. The Caveats
What are the caveats of using such an application? First, the mapping data takes no account whatsoever of ground clutter (e.g., buildings, trees, and such). Realistically, it's difficult to do so, because these things change a bit from month to month and year to year. One approach, suggested by Jerritt Collord, might be to integrate the 30-meter resolution SRTM data, which could be compared against a matching DEM to infer the presence of ground clutter.
However, even correlating against SRTM data would suffer from the other general caveat of NoCat Maps, which is that the resolution of the DEMs isn't perfect for the task. Experience shows that 10 meters in one direction or another can easily be make-or-break for a wireless link, much less 30 meters. As a result, NoCat Maps rates some proven, working wireless links as being impossible, and rates some other links as possible which later turned out not to be. The practical upshot is that NoCat Maps is intended to provide a rule of thumb, a starting point for planning community networks, rather than a definitive resource. If a link looks marginal, it's often worth trying anyway!
Creating an application like NoCat Maps has become much easier in the last three years. For starters, you no longer need to create your own custom geocoder to get the latitude and longitude of a particular street address; instead, you can use http://geocoder.us. You can also lighten the load of the application quite a bit by using the Geo::GDAL Perl module from the CPAN to directly access DEM files, instead of having to integrate with GRASS.
There are plans afoot to improve NoCat Maps and to generalize the tool so that anyone can download and implement a NoCat Map database for their own community network. Stay tuned to http://maps.nocat.net for more details.
Bluetooth, Mobile Phones, and GPS
Network Discovery and Monitoring
Wireless Network Design
Appendix A. Wireless Standards
Appendix B. Wireless Hardware Guide