Take your ThinkPad out for a walk to create wireless site surveys

Document options Document options requiring JavaScript are not displayed Sample code Rate this page Help us improve this content

Level: Intermediate

Nathan Harrington (harrington.nathan@gmail.com), Programmer, IBM　

12 Feb 2008

Use the accelerometer embedded in a ThinkPad to record your movements while monitoring your network connectivity. Use custom algorithms to extract footstep features from the recorded data, then automatically plot signal strengths on a floor-plan map to determine the best areas of coverage.

Wireless site surveys are indispensable for developing accurate data models of network coverage in a variety of environments. Current options for creating a signal-strength map of a large area require time-consuming manual operations to designate points and record signal strengths. ThinkPads with the Hard Disk Active Protection System (HDAPS) accelerometers allow for the automation of much of this work through computed distance traveled and signal-strength measurements. This article uses sample code to extract the step features from a stream of accelerometer data and presents rendering algorithms for mapping a wireless network's signal strength over a broad area.

Requirements

Hardware

Many ThinkPads manufactured in 2003 and later sport HDAPS hardware. If you are unsure whether your ThinkPad supports HDAPS, review its technical specifications on the Lenovo Web site. A functional 802.11 network card or built-in WiFi hardware is required.

Software

You need a Linux® distribution with kernel support for HDAPS. The HDAPS driver must be included in the kernel to enable access to the accelerometers. Newer kernel distributions, including Red Hat, Debian, Gentoo, and Ubuntu include HDAPS drivers. Check out the HDAPS-related articles in the Resources section for more information on how to get started with HDAPS kernel drivers.

You'll also need the Time::HiRes module from the Perl file archive, CPAN, to provide subsecond timing control when recording data. ImageMagick is also required, as the rendering program uses the convert and composite commands to generate the final signal-strength maps. See Resources for links to these tools.

Note that the techniques and algorithms described in this article should work with any notebook computer that has on-board accelerometers. Those with MacBooks or ThinkPads running an operating system other than Linux should be able to adapt the code presented here without difficulty.

Back to top

Collecting data with recordData.pl

recordData.pl program description

Listing 1 shows the recordData.pl program. The first 12 lines define the program's global variables, including where to find the HDAPS sensor data and the wireless network connection information. Subroutines readPosition and readSignal simply extract the (x,y) accelerometer and the signal-strength values from the appropriate files. In this example, the main program loop prints out this information and sleeps for one-twentieth of a second. Depending on your data collection context, you may desire more samples per second or the addition of a separate parameter, such as ESSID. For the purposes of this article, 20 samples per second is sufficient resolution to record an average user's walking characteristics.

                
#!/usr/bin/perl -w  
# recordData.pl - record accelerometer readings and wireless signal strength
# usage: recordData.pl | tee logFile
use strict;
use Time::HiRes qw( usleep );

$|=1; # non-buffered output

my $hdapsFN = "/sys/devices/platform/hdaps/position"; # hdaps data
my $netwkFN = "/proc/net/wireless";                   # network data
my ($restX, $restY ) = ""; # default position of hdaps sensors
my $SLEEP_INTERVAL = 50000; # microseconds to pause between data reads

# setup the default position of the hdaps sensor values
($restX, $restY ) = readPosition();

while(1)
{
  my ($currX, $currY) = readPosition();
  $currX -= $restX;  # adjust for rest data state
  $currY -= $restY;

  print Time::HiRes::time(), " ", readSignal(), " $currX $currY \n";
  usleep($SLEEP_INTERVAL);
}#end main loop

# begin subroutines

sub readPosition
{
  my ($posX, $posY) = "";
  open(FH," $hdapsFN") or die "can't open hdaps file";
    while(my $hdapsLine = <FH> )
    { 
      $hdapsLine =~ s/(\(|\))//g; # remove parens
      ($posX, $posY) = split ",", $hdapsLine;
    }# while hdaps line read
  close(FH);
  return( $posX, $posY );
}#readPosition

sub readSignal
{ 
  my $sigLev = 0;
  open(FH," $netwkFN") or die "can't open wireless network file";
    while( my $networkLine = <FH> )
    { 
      next unless( /eth/ );
      (undef, undef, undef, $sigLev ) = split " ", $networkLine;
    }# while read
  close(FH);
  return( $sigLev );
}#readSignal

recordData.pl usage for logging data

Associate your network card with an access point and start the recordData.pl program with the command perl recordData.pl | tee logFileN. Further processing of the output in logFile is dependent on the user holding the ThinkPad in a specific manner. For example, walk to the desired data collection start point, close the ThinkPad, and hold it at your side like a book or briefcase. Pause in this position for at least two seconds, then begin to walk down the row or hallway toward the data collection end point. Remember to pause at the end of the data-collection run for at least two seconds, then open the ThinkPad and stop the recordData.pl program with Ctrl+C.

Remember to walk normally. Let your ThinkPad-holding arm swing freely. These characteristic oscillations will be detected later as features indicating a step. Record a different log file for each row and give them a sequential name or numbering scheme for ease of processing later. Isolating the walking motion from the associate translations and rotations is accomplished by listening for the two-second pause before and after a data run. Make sure your data runs are punctuated by standing still to ensure that the post-processing is successful. Listing 2 shows an example output of the recordData.pl program with time, signal strength, and X and Y accelerometer readings during a typical walking session.

                
...
1199973721.01845 179.  -15 -140 
1199973721.06944 181.  -11 -141 
1199973721.12043 181.  -8 -139 
1199973721.22242 183.  -4 -139 
...

Back to top

Extracting steps from recorded data

Visualizing the output of a typical data-collection run is a task best suited for kst — a KDE application for plotting data. Although not required for this article, kst is indispensable for analyzing live and recorded data. If you have kst installed, you can generate a graph like that shown below with the command kst -y 2 -y 3 -y 4 logFile.

Annotations and indicators of the vital points are shown in Figure 1. The required sequence of events is demonstrated, showing the start of the data logging, then the moving of the ThinkPad to the vertical "walking" position. The initial "rest" state is recorded, followed by the "walking" section. The rest period is then shown again, followed by movement back to a "standard" configuration to manually stop the program.

Extracting relevant data portions

The first step in creating a signal-strength plot from the recordData log files is to isolate only the relevant data portions. Listing 3 shows the detectEnds.pl program, which is designed to print only the rest/walking/rest portions of the data log files.

detectEnds.pl reads each line of the logFile input from the recordData.pl program. If there are more than two seconds (40 samples based on a 50,000-microsecond delay) worth of data with a Y accelerometer reading less than -100, a primitive average-deviation check is performed. If the average deviation is near zero, a rest state is set. Following the initial rest state, the walking condition is expected based on a high deviation for a group of points. When the walking condition is set, the second rest detected will terminate the detectEnds.pl program, leaving an endFile with the same format as the initial logFile, but with substantially more useful data.

                
#!/usr/bin/perl -w
# detectEnds.pl - find rest/walking/rest section of recordData.pl output
# usage: cat logFile |  detectEnds.pl > endFile
use strict;
my @dataArr = ();
my $maxDeviation = 1;
my $minimumData = 40; # 2 seconds at 20 samples/sec
my $lastMode = "start";

while(my $line = <STDIN> )
{ 
  my( $time, $signal, $x, $y ) = split " ", $line;

  # only process entries where unit is rotated properly
  next if( $y > -100 );

  push @dataArr, $y;  # add to the data sample

  # if at least N seconds or data has been recorded
  next if( @dataArr <= $minimumData );

  # zero deviation is near zero movement (rest), deviation 4 or more is walking
  my $deviation = avgCheck(9) + avgCheck(19) + avgCheck(29) + avgCheck(39);

  if( $deviation == 0 )
  { 
    # first rest, before any other state
    $lastMode = "rest" if( $lastMode eq "start" );

    # terminate if post-walking rest detected
    exit(0) if ( $lastMode eq "walking" );

  }elsif( $deviation >= 4 )
  { 
    # set walking mode on first rest detection
    $lastMode = "walking" if( $lastMode eq "rest" );

  }#check deviation

  shift @dataArr;  # maintain a minimumData size sample
  print $line if( $lastMode eq "rest"  || $lastMode eq "walking" );
}#while line in 

# begin subroutines 

sub avgCheck
{ 
  # build and average of two seconds worth of data, return an integer of it's
  # deviation from the center point
  my $avgIndex = $_[0];
  my $avgArr = 0;
  for my $eachArr ( @dataArr ){ $avgArr += $eachArr };
  $avgArr = $avgArr / ($minimumData+1);

  return(1) if(  abs( $dataArr[$avgIndex] - $avgArr ) > $maxDeviation );
  return(0);
}# avgCheck

Create an isolated walking file with the command cat logFileN | perl detectEnds.pl > endFileN. An endFile will now contain only the relevant portions of accelerometers and signal strength, without the extraneous translation and rotation associated with the start and stop of the program.

Note that the row data needs to be kept separate for effective rendering. If you have three rows, for example, consider the following one-liner to help automate the processing of multiple files:

perl -e 'while($c<3){`cat logFile$c | perl detectEnds.pl > endFile$c`;$c++}'

Back to top

Identifying footsteps with findStep.pl

With the relevant data portion now available in the endFile, processing for indicating footsteps is much more straightforward. Consider Figure 2, which shows a kst program output of endFile processing with footsteps indicated. Listing 4 describes the findStep.pl program, which will produce a data file used in building the image in Figure 2.

                
#!/usr/bin/perl -w 
# findStep.pl - indicate peaks and nadirs (left and right steps) in an endFile
use strict;
die "usage: cat endFile | findStep.pl dataSz lowOrder > steps" unless @ARGV==2;

my $dataSz   = $ARGV[0]; # number of samples to process for a wave
my $lowOrder = $ARGV[1]; # level of modulation that indicates a low order wave
my @lineArr = ();

# read the whole file in to set defaults and compute total data size
while( my $line = <STDIN> )
{
  chomp($line);
  push @lineArr, "default $line -60 -240 ";
}#while stdin

die "specify dataSz at most (totalSampleSize/2)-1" if ( (@lineArr/2)+1 < $dataSz );

my $lineNum = $dataSz; # skip the first N samples (known 'resting' mode)

for( $lineNum = $dataSz; $lineNum < (@lineArr-$dataSz); $lineNum++ )
{
  my ( undef, $time, $signal, $x, $y ) = split " ", $lineArr[$lineNum];

  # require a coffee bender before twitch=step
  next unless ( highOrderWave($lineNum, $y) == 1);

  if( findModulation( "peak", $lineNum, $y ) == (($dataSz*2)+1) )
  {
    $lineArr[$lineNum] =~ s/default/peak   /i;
    $lineArr[$lineNum] = "peak $time $signal $x $y $y -240";
  }elsif( findModulation( "nadir", $lineNum, $y ) == (($dataSz*2)+1) )
  {
    $lineArr[$lineNum] =~ s/default/nadir  /i;
    $lineArr[$lineNum] = "nadir $time $signal $x $y -60 $y";
  }#if peak or nadir detected

}#for each linearr

for my $lineItem( @lineArr ){ print "$lineItem\n" }

findStep.pl requires two parameters:

• dataSz' — Minimum number of data points to consider for a wave
• lowOrder' — Minimum threshold that must be reached for a modulation to be considered a "step"

Experimentation with these variables may be required, depending on the characteristics of the data collector's gait or method of holding the ThinkPad. Modification of the sample size in recordData and detectEnds may also require changes for these variables. After reading in the contents of the file to determine the full data size, as well as setting default values, each data point in the walking section is processed. Two checks are performed — one to determine a modulation of sufficient amplitude, another to detect the type of modulation. If a peak or nadir is detected, that particular entry is set using a string identifier, and all the entries are printed out after processing.

                
sub highOrderWave
{   
  my(  $startVal, $currY ) = @_;
  my $avgSize = 0;
  
  # for selected sample size before and after current position, build average
  for( my $pos = ($startVal-$dataSz); $pos <= ($startVal+$dataSz); $pos++ )
  { 
    my ( undef, undef, undef, undef, $checkY ) = split " ", $lineArr[$pos];
    $avgSize += $checkY;
  }#for each position dataSz before and after
  
  $avgSize = $avgSize / (($dataSz*2)+1);
  $avgSize = abs($avgSize - $currY);
  
  return(0) if( $avgSize <  $lowOrder );
  return(1);

}#highOrderWave

Listing 5 shows the modulation-amplitude check in highOrderWave in detail. Implementing another primitive average-check algorithm, highOrderWave simply computes the deviation of all items in the data sample from the current item. If the deviation is greater than the lowOrder parameter, the function returns true and further processing for a peak or nadir modulation is performed in the main program logic. Low-order modulations are common during the resting state among hyper-caffeinated programmer types, as well as during the weight-shifting motions prior to the beginning of a walking motion. Increase the lowOrder variable as described above to isolate only the most pronounced modulations to be detected by the findModulation subroutine, as shown below.

                
sub findModulation
{ 
  my( $peakType, $startVal, $currY ) = @_;
  my $totalMatch = 0;

  # for selected sample size before and after current position
  for( my $pos = ($startVal-$dataSz); $pos <= ($startVal+$dataSz); $pos++ )
  { 
    # stop checking if a previous modulation found nearby
    return(0) if( $lineArr[$pos] =~ /$peakType/ );

    my ( undef, undef, undef, undef, $checkY ) = split " ", $lineArr[$pos];

    if( $peakType eq "peak" ){     $totalMatch++ if( $checkY <= $currY ); }
    elsif( $peakType eq "nadir" ){ $totalMatch++ if( $checkY >= $currY ); }

  }#for each position dataSz before and after

  return( $totalMatch );

}#findModulation

Given a collection of data points that show an oscillating pattern of peaks and nadirs, it is relatively easy to extract the high and low points by simply measuring nearby values. For each data point in the current sample size, findModulation first checks for previously defined modulation events within the same sample range. This check prevents clustering of modulation points on plateaus and hiccups of nearby point detections. When a "peak" check is specified, the findModulation counts the number of points at or below the current data point. The inverse is performed for a nadir check, with the total number of points at or above the current data point returned by the findModulation subroutine. Recall from Listing 4 that the return value from findModulation is compared to the total sample size. If the count of less than or equal to is the same as the sample size, a peak is indicated. Inversely, if the count of greater than or equal to sample size, a nadir is set.

Generate a file with peak and nadir step information with the command cat endFileN | perl findStep.pl 3 5 > stepFileN. Values 3 for dataSz and 5 for lowOrder work well with the author's data collection files. stepFileN will contain the final information necessary to begin the image-rendering process.

Back to top

Rendering signal strength from recorded data

Blueprint selection, identify row starting points

Data files containing isolated steps with the corresponding wireless-signal information are now prepared. A building floor-plan diagram is ideal for representing this data on a set of useful reference points. Although any image from a blueprint to a hand-drawn diagram will work well, the rendering program requires the dimensions to be regular. The diagrams used for this example are all rectangular, with equal-shaped portions of the building throughout the image. If you have an irregularly shaped building (an L-shaped floor plan, for example), you may need to divide the diagrammable portions into regular sections corresponding to the appropriate row data collections.

Consult the first part of Figure 3 below for an example diagram. Note the white background and border around the image. These characteristics make rendering and compositing much more efficient. You'll need to identify the row starting points in this image to feed the rendering program. For example, if you open the blueprint image file in The Gimp and place your cursor over the beginning of a row data collection point, you can see that the row starts at position 44,30. Prepare a list of the starting points for each row of data that has been collected.

rowRender.pl program and design decisions

Before we continue with a description of the rowRender.pl program and further examples, some words are required about the rendering approach chosen for this implementation. There appears to be some limitation with the C and Perl APIs to the gd package. No matter the options selected or the parameters specified, drawing an alpha-blended circle does not appear to be possible. The simplest method of removing this limitation is to draw all the geographic primitives on the command line using ImageMagick's convert command. The rowRender.pl program simply builds a long chain of ImageMagick convert commands to be executed and runs the commands in chunks to produce the desired output.

                
#!/usr/bin/perl -w
# rowRender.pl - draw alpha blended signal strength circles at each step
use strict;
die "usage: cat steps | rowRender.pl inImg outImg stX stY size" unless @ARGV==5;
my $alpha = 220;      # alpha color blending for signal circles
my @steps = ();       # signal measurements
my $cmd = "convert "; # beginning of ImageMagick command
my ($inFile, $outFile, $startX, $startY, $dotSize) = @ARGV; # input, output files

# pre-compute the number of steps
while(my $line = <STDIN>)
{
  my( undef, undef, $signal, undef, undef) = split " ", $line;
  push @steps, $signal  if( $line =~ /(peak|nadir)/ );
}#while stdin

# assumes consistent width through entire image
my( undef, undef, $width ) = split " ", `identify $inFile`;
$width = substr($width, 0, index($width,"x"));
$width = $width - ($startX * 2);   # right image border compensation

# set stepSize manually for blueprint images with irregular borders, an 'L'
# shaped building for example
my $stepSize = $width / @steps;

for( my $lineNum = 0; $lineNum < @steps; $lineNum++ )
{
  $cmd .= qq{ -fill "rgba(} . computeColor($steps[$lineNum]) . qq{,$alpha)" };
  $cmd .= qq( -draw 'circle $startX,$startY, );
  $cmd .= ($startX + $dotSize) . "," . ($startY + $dotSize) . qq(' \\\n);

  runCommand() if( $lineNum % 50 == 0 );
  $startX += $stepSize;

}#for each step

runCommand();

rowRender.pl expects an input image such as a blueprint or other diagram and an output image name. The startX and startY parameters are coordinates of the beginning of the row (all rendering is left to right), and the dotSize parameter is the diameter of the alpha-blended circle to draw at each step.

The total number of steps is computed, and the ImageMagick identify program is used to determine the width of the image to be rendered. rowRender assumes that each row is traversed in full and that the footsteps are distributed evenly across the entire image. For each of these evenly spaced steps, the alpha-blended circle drawing command is built based on the signal strength. computeColor shown in Listing 8 determines what level of color to display, while runCommand simply executes commands as built.

                
sub computeColor
{ 
  # simplistic computation of custom color range based on signal levels
  my $signal = $_[0];

  my $color = qq(255,140,10); # default orange
  if( $signal >= 197 && $signal < 207  )
  {
    $color = abs( $signal - 207 );
    $color = $color * 8;           # intervals of 10
    $color = $color + 175;         # starting at green 175
    $color = qq(59,$color,10);

  }elsif( $signal >= 189 && $signal < 197 )
  {
    $color = abs( $signal - 197 );
    $color = $color * 18;          # 10 intervals
    $color = $color + 75;          # starting at red 75
    $color = qq($color,234,39);

  }elsif( $signal >= 181 && $signal < 189 )
  {
    $color = abs( $signal - 189 );
    $color = $color * 15;          # 10 intervals
    $color = $color + 124;         # starting at green 124
    $color = qq(255,$color,10);
  }
  return($color);
}#computeColor

sub runCommand
{
  $cmd = `$cmd $inFile $outFile`;
  $inFile = "$outFile"; # use output as input for multi-pass image writing
  $cmd = qq( convert );
}#runCommand

As shown above, four arbitrary buckets of signal strength were chosen corresponding to red (<181), orange (181-188), yellow (189-196), and green (197-207). Color values are chosen based on where the signal level falls in its color classification bucket. These values will almost certainly need to be changed based on the signal-strength data collected during the first step. The color-choosing algorithms here represent a straightforward example for rendering differentiation.

Rendering the final image

Build a diagram with a single row of data rendered with the command cat steps | perl rowRender.pl bluePrint.png out.png 44 20 30. Recall that the start X,Y coordinates are determined from The Gimp image editor and represent the starting point of data collection for that particular row. For multiple rows of data, consider building a file with the associated row start X,Y coordinates like that shown below.

                
cat steps0 |perl rowRender1.pl bluePrint.png out.png 20 44 30
cat steps1 |perl rowRender1.pl out.png out.png       20 74 30
cat steps2 |perl rowRender1.pl out.png out.png       20 99 30
..
cat stepsN |perl rowRender1.pl out.png done.png      X  Y  dotSize

You may also want to try changing the alpha-blending amount to more easily see the background diagram. If you have created a blueprint file with a white background, the final overlay is easily accomplished with ImageMagick. Listing 10 shows how to use convert and composite to easily overlay just the visible portions of the blueprint onto the signal-strength rendering.

                
convert -transparent "#FFFFFF" bluePrint.png transparent.png
composite -compose over transparent.png done.png finalImg.png

Figure 3 shows an example output of the rendering steps listed above.

Back to top

Conclusion and further examples

The techniques and code in this article allow you to measure wireless-signal strength much more efficiently than existing stop-and-click methods. Mapping multiple floors of a building or vast open spaces, such as warehouses and manufacturing facilities, can be done nearly as quickly as you can walk. With this signal-strength information, you'll be able to more efficiently distribute site access points to improve the speed and coverage of your wireless network.

For further research, consider integrating the footfall detection code with gpsd and kismet to enhance the resolution of your broad area network-mapping setups. Make full use of your wireless card's functionality and map the signal strength from multiple access points simultaneously.

Share this... Digg this story Post to del.icio.us Slashdot it!

Back to top

Download

	Information about download methods

Resources

• For more information about interesting things to do with HDAPS sensors in ThinkPads, read "Knock-based commands for your Linux laptop."
  
  
• Check out the HDAPS development information on SourceForge.
  
  
• Plot scientific and other data using kst.
  
  
• See "Enable C++ applications for Web services using XML-RPC" for a step-by-step guide to exposing C++ methods as services.
  
  
• To listen to interesting interviews and discussions for software developers, check out developerWorks podcasts.
  
  
• Stay current with developerWorks' Technical events and webcasts.
  
  
• Check out upcoming conferences, trade shows, webcasts, and other Events around the world that are of interest to IBM open source developers.
  
  
• Visit the developerWorks Open source zone for extensive how-to information, tools, and project updates to help you develop with open source technologies and use them with IBM's products.
  
  
• Watch and learn about IBM and open source technologies and product functions with the no-cost developerWorks On demand demos.
  
  

• Grab the Time::HiRes module from CPAN.
  
  
• Learn more about Linux kernel download mirrors for acquiring HDAPS.
  
  
• Learn more about and download The Gimp image manipulation software. Available for download for Windows®, Mac OS X, and many flavors of UNIX®.
  
  
• ImageMagick is a software suite to create, edit, and compose bitmap images, available for Windows, Mac OS X, and many flavors of UNIX.
  
  
• Grab Perl from Perl.org.
  
  
• Innovate your next open source development project with IBM trial software, available for download or on DVD.
  
  
• Download IBM product evaluation versions, and get your hands on application development tools and middleware products from DB2®, Lotus®, Rational®, Tivoli®, and WebSphere®.

• Participate in developerWorks blogs and get involved in the developerWorks community.
  
  

About the author

		Nathan Harrington is a programmer at IBM currently working with Linux and resource-locating technologies.

Rate this page

Please take a moment to complete this form to help us better serve you. Did the information help you to achieve your goal? Yes No Don't know   Please provide us with comments to help improve this page:   How useful is the information? 1 2 3 4 5 Not useful Extremely useful

Back to top