Herecast: An Open Infrastructure for



Herecast: An Open Infrastructure for

Location-Based Services using Wi-Fi

University of Western Ontario

Department of Computer Science

Mark Paciga

Supervisor: Hanan Lutfiyya

April 2004

Table of Contents

1. Introduction 3

2. Existing Solutions and Previous Research 3

2.1. The problems with GPS 3

2.2. Specialized Indoor Positioning Systems 4

2.3. Wi-Fi Positioning Systems 4

3. Design Tradeoffs 5

3.1. Wide-Area vs. Local 5

3.2. Server-Oriented vs. Client-Oriented 5

3.3. Resolution of Location-Detection Algorithms: Fine vs. Coarse 7

3.4. Coordinate-Based vs. Symbolic Positioning Systems 8

4. Design Concepts 9

4.1. Community-Built Database 9

4.2. Respecting Privacy 9

4.3. Open for Developers 11

5. Implementation Details 12

5.1. Database Design 12

5.2. Client-Side Data Cache 13

5.3. Client-Server Synchronization 15

5.4. Downloading From Server 16

5.5. Uploading To Server 16

5.6. Developing Location-Aware Services 17

5.7. Client Software 20

5.8. Software Tour 22

5.9. Finding Access Points 26

6. Applications 27

6.1. Area Maps 27

6.2. Friend Finder 28

6.3. Heresay 29

6.4. Finding Rogue Access Points 29

6.5. Bandwidth Advisor 29

6.6. Software as a Network Scanner 30

7. Future Work 31

7.1. Future Applications 31

7.2. Database Integrity and Privacy Issues 31

7.3. GPS Integration 32

7.4. Offline Services 33

7.5. Autonomous Map Generation 33

Appendix A – Database Schema 35

References 37

Introduction

It has long been imagined that one day, our computers would be able to use information about the environment in order to enhance the user experience. For example, a device or service could customise its response depending on where the user is located. This is known as location-awareness. Once your mobile device knows where it is, it can use this information in many different ways—you could bring up a map of your location with a single click, access web sites relevant to your location, publish presence information to your friends, or play new types of games where you progress as you hunt around the city.

Researchers have begun to explore the possibility of leveraging existing 802.11 wireless networks in order to determine a user’s location. We have designed and implemented one such system, taking into consideration some of the main issues that are frequently raised with respect to location-sensing infrastructures. The system must respect user privacy. It needs to work indoors as well as out. It must be inexpensive, easy to set up, easy to use, and work in any building, anywhere.

We want to significantly reduce the barriers to entry in this field, giving all developers the ability to create their own location-aware services. The stereotypical “restaurant finder” type of ideas have already been thrown around for years. The real innovation happens when we get the tools into the hands of the people who are passionate about the technology in and of itself. That is what this project is about.

Existing Solutions and Previous Research

1 The problems with GPS

The most obvious way to capture location information is to use an embedded Global Positioning System (GPS) receiver. Unfortunately, because of the small number of compelling applications available, there does not exist a strong market demand for GPS devices, and they thus remain surprisingly expensive. (Although “Assisted GPS” is integrated in some modern mobile phones, it is usually impossible for outside developers to access this information.) Perhaps most importantly, the radio waves used by GPS have difficulty penetrating building walls, making the devices unreliable when used indoors. Even the tall buildings of dense urban environments are known to cause significant trouble in city streets.

It is easy to see that these weaknesses are of great significance when attempting to use these devices with our everyday computers. After all, we do most of our interaction with computers while we are indoors—often in large steel and concrete structures—

exactly the places where GPS is the least reliable.

2 Specialized Indoor Positioning Systems

Most previous location-sensing infrastructures used specialized hardware installed in the environment. Modern versions of such systems can locate mobile devices with an incredible level of resolution, and are able to support unique applications such as “clickable” posters [[i]]. Unfortunately, because of the hardware investment required, these systems can be expensive to deploy. Although they function well in specialized environments, they are not suitable for use on a global scale.

3 Wi-Fi Positioning Systems

More recently, there has been interest in taking advantage of the existing wireless network infrastructure to support location-aware services [[ii]]. With many organizations now deploying 802.11 wireless networks on a large scale, one can imagine that these networks will become essentially ubiquitous in a few years. (In fact, one can barely take a drive down an average city street without discovering a number of wireless access points.) Since the networks are already deployed, there is no additional hardware investment required. Wi-Fi networks are thus well suited to become the basis for a cost-effective wide-area location-aware infrastructure.

Note that while GPS has difficulty coping with indoor and urban environments, Wi-Fi networks are most concentrated in exactly these areas. The two systems therefore complement each other well. GPS works well when you are on the road in an open area, but once you get on your feet in the city, that’s where Wi-Fi positioning is best.

Design Tradeoffs

This section will deal with some of the tradeoffs that are specific to a Wi-Fi positioning system.

1 Wide-Area vs. Local

In this project, we aim to create a system that is applicable to a wide area, rather than one that is heavily customised for a specific area. The location-sensing infrastructure itself should be generic. Customisation takes place at a higher level—by offering unique services that are specific to an area.

2 Server-Oriented vs. Client-Oriented

There are two ways to determine a user’s location. The difference is in what part of the network has the task of performing the location calculation.

Server-Oriented Method

The server-oriented method places the task of locating users in the network infrastructure. Users simply access a web page, and instantly see information tailored to their location. An implementation of this method was created by Purdue University [[iii],[iv]]. In that system, accessing a web site would give users a map of their current area, indicating the location of nearby resources such as printers and vending machines. In addition, a “print to closest printer” service was created. By implementing the locating mechanism as a web service, other applications would be able to make use of the location information as well.

This approach requires a method of mapping a client IP address to a physical location. This is done in several steps. First, the IP address must be mapped to a MAC address. This information can be obtained by examining the DHCP server log, or by querying the ARP table on the client’s default gateway. Knowing the MAC address, the system examines a Radius log file to determine which access point that device is currently using. (An alternate approach is to examine the bridge learning tables of all access points using SNMP; however, this method has more overhead and is thus not as scalable.) Once the client’s current access point is known, the web service can deliver information appropriate to that location.

Obviously, this method requires collaboration with the administrators of the wireless network. The IP-to-MAC mapping requires SNMP access to the gateways, and the MAC-to-access point mapping requires access to the Radius log file, or SNMP access to the access points.

Client-Oriented Method

An alternative strategy is to let the device itself figure out where it is. Every wireless access point transmits a unique MAC address, which allows a mobile device to distinguish one access point from another. To determine its location, the client only needs a database associating each access point address with a real-world location. This has a clear privacy advantage, as the client does not need to reveal its location unless desired.

This method leverages the entire existing deployment of Wi-Fi equipment. Note that we can use a Wi-Fi access point as a landmark whether or not that access point provides public internet access. We thus take advantage not only of the growing number of public Wi-Fi “hotspots”, but also any private networks that exist as well.

Comparison

With the server-oriented method, the infrastructure itself handles the locating mechanism, so individual clients are not required to install special software on their devices. All wireless users can instantly take advantage of location-aware services. However, because this method requires the involvement of the network administrators, the services will not work when accessed from networks outside of their administrative control.

Privacy is always an issue whenever network-based locating services are mentioned. The Purdue system addresses this issue by only calculating a user’s location in response to a direct query—it does not continually monitor individuals. However, with a client-oriented system, the preservation of privacy is guaranteed by the design, and thus may be perceived to be more trustworthy.

The choice of server- vs. client-oriented depends on the type of services that one wishes to provide. The server-oriented method is best for services that are specific to one network and need to be available to the greatest number of users. The client-oriented method is best for services that work anywhere, or that require the client to be able to determine its own location.

3 Resolution of Location-Detection Algorithms: Fine vs. Coarse

Numerous methods have been proposed to pinpoint a user’s location on an 802.11 network. These algorithms involve using the signal strength information from multiple access points in order to triangulate the user’s location [[v]]. Discussion of such algorithms is outside the scope of this research; however, we believe that for most practical applications, it is good enough to employ a simple algorithm based on the single closest access point.

The downside of using more complex algorithms is that they require more initial calibration in order to obtain accurate results. It is typically necessary for an administrator to walk around the environment, recording signal strengths at every possible location—a time-intensive process that is usually dependant on first creating a graphical map of the environment. Clients then require more storage space to hold the larger database, and more processing power to compute the location—two critical issues when dealing with resource-constrained mobile devices. In addition, complex algorithms are more sensitive to changes in the environment, such as movement of people and furniture.

The performance of these algorithms is also influenced by the positioning of the access points. Although it may be possible to arrange access points to improve their usefulness as reference points for triangulation, real-world networks are arranged only to provide optimal network coverage. In our on-campus testing with commercially available location-sensing software, we were not able achieve the results advertised.

Using the single closest access point, we can locate a user down to a reasonable level—an area the size of a large room, or several rooms. This is not as detailed as something like GPS, but it’s good enough for many practical purposes. Even if this is not enough to determine, for example, which office cubicle the user is in, it is good enough to at least narrow down the list of possibilities.

4 Coordinate-Based vs. Symbolic Positioning Systems

There are two ways to express a location: using numeric coordinates, or using a symbolic description. GPS is an example of a coordinate-based system—it expresses location as latitude and longitude (and sometimes altitude.) Other systems use a proprietary coordinate system in a limited area. Symbolic representation expresses location in terms a human would use—for example, the name of a building, or the name of a room.

Coordinate-based positioning makes it easy to draw a map of a location, but additional metadata is required to describe that location in textual terms, such as specifying the name of the building. Conversely, symbolic representation is natural and immediately understandable to the user, but requires additional metadata in order to create a map showing where that location is.

With a coordinate-based system, there are two ways to enter data. We could use a GPS device to automatically record the location of each access point. Alternatively, we could obtain a graphical map of the environment, and click on the map to specify the location of the access point. If we want the system to be usable over a wide area, it is problematic to expect individuals to obtain maps of every building. Therefore, the best way to implement a coordinate-based system is to use GPS. However, given GPS’s problems coping with indoor and urban environments, this could be equally problematic.

With a symbolic positioning scheme, we don’t have to require maps or GPS devices, and maps are not required to display the data in a meaningful format. It seemed most appropriate to use a different approach from the existing solutions, as this could open up different possibilities for services. Symbolic positioning is designed the way people see the world—names of places instead of numbers.

One disadvantage of using a symbolic positioning system is that it is more difficult to calculate the distance between two points. There may be ways to address this issue. These will be discussed in the “future work” section.

Design Concepts

1 Community-Built Database

We will create an access point location database that can cover an entire campus, city, or even the world. The first time an access point is discovered by a user, that user can enter information describing the location of the access point. This information may then be uploaded to the global database, making it available to everyone else who happens across that access point in the future. The advantage of a community-built database is that it does not require as much administrative involvement, as all users of the system work together to contribute to the usefulness of the community as a whole.

For each access point, the database should know the physical location of the access point: country, province, city, street and number, building, floor, and room. For environments such as university and business campuses, we would want to include this information as well, to allow buildings to be grouped similarly to how people do it. In addition to this geographic information, we should also include information about the organization that controls the access point, and thus the group of users that has permission to use the access point. The network information will be useful for providing services such as the “bandwidth advisor”, which will be discussed in section 6.5.

For efficiency and privacy purposes, a portion of the database will be downloaded and cached by the client when it enters a new area. This way, the user will be able to move around in an area without having to download new information as each new access point is encountered. (In the current implementation, we download data for an entire city at once. A PDA should easily be able to handle a database of this size, as it takes only approximately 5 KB of memory storage to hold information about 150 access points.)

2 Respecting Privacy

Whenever people outside of research circles hear about location-based services, some of them will inevitably raise doubts over their willingness to be tracked by a third party. One strength of the client-oriented method is that all of the calculations are done on the client device. The device knows where it is, but isn't being tracked by some central server. This means the user is always in control of how much information is revealed about their location.

Imagine a scenario where you are in a workplace that is equipped with a Wi-Fi network. Your device knows where all the access points are, and is thus able to describe your location without having to contact a third party. When you enter the workplace, you are presented with a list of services that the network offers. Say one of these services is a meeting room reservation tool, which allows you to locate the closest unoccupied meeting room for a given time period. The device tells the service where you are, allowing the service to return a list of available meeting rooms nearby. That is a simple case, because the service only needs to know your location at the moment you access it. The user has a reasonable expectation that such information will be required, and the location-awareness is used simply to skip manual data entry.

There is another type of service, one that always needs to know where you are. This is the type of service that can raise privacy concerns. In the workplace, it might be a service that allows you to locate your co-workers; in a mall, it might be stores wanting to send promotional messages when you walk past. Since you don’t want people tracking you unless you get some sort of benefit from it, you would probably demand that all such services to be opt-in. With Herecast, since the device is the only thing that knows where it is, you are never being tracked—you only reveal information voluntarily. To support a tracking service, you would “subscribe” to it, instructing your device to automatically contact the service periodically to give it an updated location. Since the subscription is managed by the device rather than a third party, you can “unsubscribe” at any time by telling the device to stop sending updates to the service.

To improve privacy, it is possible to limit a subscription to a specific building or area, so the device only advertises its location when it is in that building or area. In the coworker locator example, you may not mind letting people find out where you are when you are at work, but you don’t want those people also seeing where you are when you go home. Since Herecast uses a symbolic location description—names of buildings rather than GPS coordinates—that is easy to do. You can configure it to track you in one building, but nowhere else.

3 Open for Developers

One of the major design goals of this project is to ensure that any developer is able to create a location-based service without having to invest a significant amount of time into understanding the theory behind location-based services or the infrastructure used to support them.

Because of the considerable infrastructure requirements needed to deploy location-based services, the ability to develop such services currently rests primarily in the hands of large corporations such as mobile phone providers. In North America, these companies have been slow to offer innovative location-aware services to their customers. At the same time, we frequently read about the innovative ideas for location-aware games coming from places such as Japan and Hong Kong, where people are running around the streets hunting terrorists and collecting treasure, and wonder why North America is lagging behind.

The solution we envision is to put the tools in the hands of the general population, tapping into the vast numbers of developers who might have great ideas but simply don’t have the infrastructure to carry them out. If we enable the people who do development just because it’s fun, then we might see some more interesting things happening—not maps or restaurant finders: ideas which have been thrown around for years already—but ideas that are so far out there, nobody has even thought of them yet. Since it simply hasn’t been feasible to create location-aware services until recently, a relatively small amount of thought has gone into exploring the possibilities so far. We believe that many of the best ideas have yet to be discovered. It is largely unexplored territory—and that is where the real potential lies.

To simplify the development of location-aware services, we will allow them to be presented as ordinary web pages. The simplest type of service will be an ordinary URL that is tied to a particular location. More advanced services can receive location information in the URL query string in order to customise their content to the current location. This mechanism will be discussed in more detail in section 5.6.

Implementation Details

1 Database Design

Location Information

The database is arranged in a hierarchical fashion, with a country and the top level, and an access point at the bottom. Here are the different levels in the hierarchy:

• Country

• Province/State

• City

• Area

• Building (name and street address)

• Access Point (specifying floor and location within the building)

An area is a part of a city; for example, a neighbourhood, borough, district, or perhaps a university or business campus. This is optional, but is useful for grouping several related buildings together.

The floor and location fields are also optional. These are used if the building has more than one access point. The “location” doesn't have to be precise—if the access point covers a large area, it is best to give the name the general area.

In addition to the physical location, each access point can also be assigned to a network.

The full database schema is shown in appendix A.

Services

A separate table exists for the list of services. These are simply URLs that are associated with one of the location objects described in the previous section. (For example, a service can be associated with a city, area, building, or network.)

Note that associating services with real-world objects such as buildings and cities is only possible because we use symbolic positioning rather than GPS coordinates—the software already knows the location by a name. With a coordinate-based system, we would need to separately record the boundaries of each building and city.

User Management

A community-maintained database requires a user management system so that additions and modifications can be traced to individuals who made them.

Our system accommodates differing user levels. New users will be placed at the starting level. After a time of good behaviour, they may be promoted to a higher level that gives additional privileges. Regular users can only modify items in a limited number of cities, to contain the amount of damage a malicious user would be able to do.

Changes to the database are stored in a change log, which will allow any inappropriate changes to be rolled back at a later date. Certain changes, such as deletions, cannot be performed immediately, and are placed in a queue of change requests to be examined by a higher-ranking user later. In the future, we would like to enhance this moderation system so that all users may “vote” to accept or reject changes.

Distributed Database?

Since the database is arranged as a hierarchical fashion, it would seem that it would lend itself well to being geographically distributed. (For example, there could be one server handling the database for Canada, one for the United States, and so on.) Unfortunately, the manner in which the database is accessed makes this difficult to accomplish. Clients request information by specifying the “MAC address” of the closest access point—the lowest level in the hierarchy. Essentially, each server would still need an entire copy of the database.

2 Client-Side Data Cache

The client stores part of the database locally in simple text files. This format was chosen in part to keep the storage format compact, making it suitable for a mobile device with limited memory. There is essentially one text file for each table of the database. Data fields are separated by tabs; each line of the file represents a row.

As an example, here is the format of the countries data file:

20 Canada

21 United States

22 ...

Each line contains two fields: a unique numeric identifier for the country, and the name of the country. The networks file has the same format.

For objects further down in the hierarchy, we must add an additional field as a reference to the parent object. For example, each item in the provinces file has a reference to the country that contains it:

30 20 Ontario

31 20 Quebec

32 21 Washington

The data files for cities and areas are the same as the above, each using (id, parent-id, name) triples.

Buildings have two additional fields. First, each building has a street address. Also, while buildings may belong to an area, this is optional. Some buildings may not have an area, but all belong to a city.

id area city building-name street-address

60 50 40 Middlesex Middlesex Dr

61 50 40 NatSci Middlesex Dr

62 0 40 Cherryhill Mall 301 Oxford St

(Note that the header showing column names is for illustration purposes only, and is not actually included in the file.)

The file listing access points uses the BSSID (MAC address) as the primary key. Each access point belongs to a building, and may also belong to a network. The final two fields are the floor (usually a number) and location:

BSSID bldg netwk floor location

00a0f8a5292f 60 10 3 Labs

00a0f8a52937 60 10 1 Room 110

00a0f8a45f4a 61 10 2 ITS North

There is also a file containing a list of services. A service can be associated with any of the different types of objects (for example, a country, city, or network.) Therefore, instead of only using an ID, we must also specify what type of object the ID refers to. (IDs are not guaranteed to be unique across all object types.)

id pid type url service-name

91 10 1 Wireless Help

90 50 5 UWO

The object type may be one of the following:

0. Global (parent ID is ignored)

1. Network

2. Country

3. Province

4. City

5. Area

6. Building

Additionally, each line of each of the files mentioned above has a final field that was not shown in the preceding examples. That field represents the status of the record, and is used by the client to flag whether that record needs to be uploaded to the server. This field can be one of the following values:

0. Normal. (The item has not been modified on the client.)

3. New. (The item was created on the client.)

6. Modified. (The item was downloaded, but was later modified on the client.)

3 Client-Server Synchronization

The client-server synchronization mechanism was designed around the storage format in order to simplify implementation. (Initially, an XML-RPC transfer mechanism had been proposed; however, it was decided that this would provide significant overhead with little or no gain. More robust transfer protocols could be devised at a later time, if necessary.) Transfer takes place over a standard HTTP connection, and the data files are uploaded and downloaded in the same format in which they are stored on the client.

4 Downloading From Server

To download information from the database, the client makes an GET request to , where “00123456789a” is the BSSID that the client wants to download information for. The server then sends its reply a format similar to what is used in the client’s local database, as follows:

- countries

20 Canada

- provinces

30 20 Ontario

- cities

40 30 London

- areas

50 40 UWO

- buildings

60 50 40 Middlesex Middlesex Dr

61 50 40 NatSci Middlesex Dr

62 0 40 Cherryhill Mall 301 Oxford St

- aps

00a0f8a5292f 60 10 3 Labs

00a0f8a52937 60 10 1 110

00a0f8a45f4a 61 10 2 ITS North & Taylor S4-6

- networks

10 UWO Wireless

- services

91 10 1 Wireless Help

90 50 5 UWO

- end

If no data is found for the access point, it returns only “- No data for this BSSID”. Note that the server may send the data for more access points than the one that was requested; this is used as a pre-caching mechanism. When the client requests information for one access point, it is likely that the client will later need to know about other nearby access points. The server thus transmits more information than necessary to avoid future requests.

5 Uploading To Server

When the client wants to upload data, it does so by sending a HTTP POST to . The content of the post is the identical to the contents of the local database, with each file separated the same way that is shown in the previous section. Also, the data submitted is prefixed with user login information:

- login

username

password (plaintext or MD5-encoded)

- countries

2000000 Canada 3

...

- end

The client should only send rows that have been added or changed.

Note that while the database uses unique numeric IDs for each object, the client will often have to create a new object before knowing what its final ID will be. (The actual ID will be assigned by the server after the item is uploaded.) The client can thus pick an arbitrary ID (a high integer is preferred to avoid collisions), and it will be translated automatically and transparently by the server. (The server matches objects by name, not by ID.)

6 Developing Location-Aware Services

As stated earlier, one of the primary design goals was to make it easy for any developer to create their own location-based services. The different possibilities are described in this section.

Normal Links

When the user clicks on their location in the software, they will receive a list of links to services at that location, as shown in the diagram to the right. This is the most basic way to provide a location-aware service. A URL can be associated with a country, province, city, area, building, network, or globally.

Enhanced Links

The next level is to provide a service that operates on a wider scale, but receives as input the user’s location. For example, the “area map” service (described in section 6.1) was created to show a map of the University of Western Ontario campus. It is available to anyone while they are in the UWO area. However, this service also receives the user’s location as input, and is thus able to pinpoint the actual building in which the user is located.

The location is sent as parameters in the URL query string. For example, one could use the url: {building}. When the user requests the service, {building} will be replaced by the actual building name.

The following URL parameters are supported: {country}, {province}, {city}, {streetaddr}, {building}, {buildingid}, {area}, {location}, and {bssid}.

As shown in the previous screen shot, these types of services are shown in italics.

Subscriptions

The most advanced type of service is one that continually receives updates as the user moves around. The URL itself uses the same parameters as described above. When a user subscribes to the service, the client will automatically access the URL specified every time the user enters a new location.

To allow a user to subscribe to a service, the web site would provide a web link of the form: herecast://url. For example, herecast://svc?building={building}. When the user clicks on this URL from the device, the Herecast software will be activated, and the user will be prompted to confirm their intention to subscribe to the service. The user can also specify further privacy settings at that time.

Services can pop up alerts to the user. To do this, the web page would include the following command on a line by itself:

- Herecast MSG Message here.

Any other data returned by the service is discarded. Of course, services developers should be careful not to send excessive alerts to the user.

XML-RPC Interface

If a service needs to request information directly from the Herecast database, it can do so using a simple XML-RPC interface. (XML-RPC implementations are available for many common programming languages [[vi]].) XML-RPC requests should be sent to

Only one method is currently provided; more may be implemented as required by service developers.

Method: location.lookupBssid

Purpose: Retrieves information about one access point.

Parameter: a string containing the BSSID of the access point to look up. The string should be in hex format. Octets can be separated by spaces, dashes, colons, or not at all.

Returns: a struct containing information about the BSSID. The members of the struct are:

• int network_id

• string network_name

• int country_id

• string country_name

• int province_id

• string province_name

• int city_id

• string city_name

• int area_id

• string area_name

• int building_id

• string building_name

• string building_streetaddr

• string ap_bssid

• string location

• string floor

7 Client Software

The application is written in C++. The Pocket PC version uses eMbedded Visual C++, which is available as a free download from Microsoft. The source code is available via CVS from , and is covered under the GNU General Public License (GPL.) The source code distribution is divided into four main projects:

• HerecastLib – The main body of the source code.

• TodayItem – The standard version of the application.

• Scanner – A standalone version of the WiFi scanner.

• Subscribe – A tiny application that handles the herecast:// subscription protocol.

The Herecast library (HerecastLib) contains most of the code for the applications; the TodayItem and Scanner projects are essentially front-ends that invoke different dialogs within the library. The library includes all of the dialog box resources, icons, and so on. It has several modules, which are described in the following sections.

Utils

Contains utility functions for creating windows, accessing the Windows registry, and so on.

WiFi

This module contains mechanisms for interfacing with the 802.11 network card, and working with the information that is retrieved.

• WiFi – an object that handles communication with the 802.11 card. For maximum compatibility, it uses NDIS, a standard interface that should be common between all wireless network cards. NDIS 802.11 was introduced in Pocket PC 2003, and also exists on Windows XP.

• AccessPoint – an object that represents a single currently-visible access point. The object provides convenient storage for metadata about the access point, including the average RSSI.

• AccessPointList – maintains a list of AccessPoint objects. Includes a method to find out which one has the highest signal strength. Alternatively, the entire list can be enumerated for presentation in a network scanner.

APDB

This large module contains objects for using the Herecast access point database. The module is further divided into several general types of objects.

• Items – These are the basic objects such as Country, City, Ap, and Service. The virtual class GenericItem contains an interface shared by all of these. The Ap (access point) class inherits directly from GenericItem. Most other objects inherit from HItem (hierarchy item), which shares the base interface of GenericItem, but adds additional fields for the item name and references to the parent item. (For example, a City object’s parent is a Province.)

[pic]

• Lists – Each Item class has a corresponding List class, which represents a set of those items. GenericList the superclass; ApList and ItemList are inherited from it. All other lists (CountryList, ServiceList, etc) are inherited from ItemList. The factory pattern is used extensively, so most List objects contain no real code. Each of the List objects has an associated file on disk (for example, countries.txt), which serves as a local cache. (See section 5.2 for details.) There is also an in-memory cache for recently used items.

[pic]

• WebAgents – UploadAgent and DownloadAgent handle sending information to and retrieving it from the online database. SubscriptionAgent manages the subscription list, scanning it and sending updates to subscribed services. All three make use of the generic WebAgent, which handles a queue of pending requests, reporting back with the progress of the request. WebAgent uses WebRequest objects to take care of the details of performing a single HTTP request.

• Dialogs – The user interface. This should port reasonably well to Windows XP, with the exception that references to CE-specific widgets such as the soft input panel will have to be disabled in that build.

8 Software Tour

This section shows a quick tour of features of the Pocket PC software.

The Herecast today item displays the user’s current location on the Pocket PC’s main screen:

[pic]

When the user clicks on the today item, it brings up a screen that shows more information about where they are. This screen includes links to web sites and services that are relevant to this location.

[pic]

Wi-Fi Scanner

By clicking on the globe icon on the today screen, the user can bring up a scanner that shows all access points that are detected in the area, along with their location and signal strength.

[pic] [pic]

The lock icon indicates that WEP is enabled on the access point, while the notebook icon represents an ad-hoc access point. The access point highlighted in red is the one with which the device is currently associated. Advanced users may wish to view additional information—for example, the screen shot on the right also shows the 802.11 channels used by each access point.

When the user discovers an access point that does not have a known location (for example, "00 a0 f8 5c a2 00" in the screen shot above), they can fill in the details by clicking on that entry. The information may then be uploaded to the global database for other people to use. The following screen shots show the data entry forms:

[pic] [pic]

[pic]

To make data entry as easy as possible, the program initially selects the most recently seen city, area, and building. Recently used items are available in dropdown listboxes, for quick selection.

9 Finding Access Points

In testing the application, we surveyed approximately 140 access points in 12 buildings. This represents most of the wireless network currently deployed on the main campus of the University of Western Ontario. We found that in a fully covered building containing approximately 20 access points, it is possible to accurately locate and describe all access points in about an hour. This section describes some of the issues involved in locating access points.

Signal Travel Distance

It was observed that wireless signals could travel a surprising distance, often reaching from one building to another. We would want to avoid situations where the user enters incorrect information because they weren’t aware that they were sensing a signal from a great distance. Ideally, we would want the user to locate the physical access point. It may be desirable to add a warning message when the user attempts to enter information for a weakly-detected access point.

Crowded Buildings

Often, a building will have many access points in a small area, making the process of matching signals to access points more challenging. We have discovered some tricks that can be used for accurately locating access points.

• Increase distance. Imagine that you see two access points quite close to each other. Standing near them, you detect the two strong signals—it is impossible to tell which is which. Realise that each access point is probably intended to cover a slightly different area. Instead of getting close, try going farther away. Walk around them on all sides, closer to the edge of each coverage area.

• Reduce interference. Sometimes there are 5 access points with reasonably strong signals all at once. Try covering the antenna to obstruct the signal. Signals from more distant access points will be blocked more easily, narrowing the list of possibilities.

• View the channels, and think like the network engineer. Two access points on the same channel interfere with each other. Say you’ve found three access points in a straight line. Two are on channel 6, and the other is on channel 11. Chances are very good that the two access points that share channel 6 are not next to each other. This helps tremendously in figuring out which is which.

• If in doubt, say so. Put a question mark at the end of the location to indicate that further investigation is needed. Perhaps use a notation such as, “Lobby? candidate 1 of 2.” You can go back and edit it later.

Complicating matters is the fact that a single access point can broadcast more than one BSSID. For example, say an organization has a WEP network and a non-WEP network. Each access point will broadcast both. It can broadcast the two networks using the same BSSID, or with two different BSSIDs. Our campus network uses both methods, depending on what hardware is being used.

Applications

The success of a location-aware computing platform lies in its ability to support a variety of useful applications. This section describes some of the sample applications that have been developed for the Herecast platform. It is expected that more elaborate applications will be developed in the future.

1 Area Maps

Mapping services such as MapQuest work well for navigating city streets by car, but when you get down to a certain level of detail, it would be better to have a more customised map showing the detailed features of the area. For example, a university campus could show a map that includes building names and local amenities, while a shopping area would display the names of stores. The Area Map service allows you to produce detailed maps for a specific area.

Maps are optimised to fit on a Pocket PC screen, and can be navigated by clicking on the image. Here is an example map showing the UWO campus.

[pic] [pic]

To create a map, we need an image, and a database table giving the image coordinates of each access point in the area.

The Area Map service initially took only about an hour to implement. This shows just how easy it is to create a useful service on top of the Herecast infrastructure. It would be equally easy to create detailed maps of individual buildings rather than an entire area. A future enhancement to this service would allow maps to be zoomed to different levels of detail.

2 Friend Finder

The friend finder service is one of the most frequently discussed applications for a location-aware infrastructure, so it seemed logical to attempt to implement such a service on Herecast. As a demo service, it is not meant to be especially fancy, nor does it care much about privacy. When a user subscribes to the service, the device automatically publishes its location to a web page as they move from place to place. The web site displays the most recently seen location of each individual; for example:

Mark was last seen at NatSci, ITS Front counter on Friday at 7:00 pm.

3 Heresay

Another frequently discussed location-

aware service is a location-based message board. We have implemented a simple version of this service, called Heresay. Users can leave a message at their current location, and see messages that have been left by other people in the same building. Although the version shown here is incredibly simple, this can be used as the starting point for a more elaborate community-building service.

4 Finding Rogue Access Points

Many organizations are concerned about “rogue access points”—wireless access points installed by individual users and departments without the authorization of the network administrators. These rogue devices pose a security risk, because they may allow any outside user to access the private network, bypassing whatever authentication mechanism is in place. In addition, rogue access points can disrupt the existing wireless network infrastructure by broadcasting on an interfering RF channel.

With the database of access points described earlier, network administrators could perform a search for “access points located within the UWO campus, but not belonging to the UWO Wireless network.” The system could even email individuals when new access points appear in an area of interest. This not only allows ordinary users to discover where service has been expanded, it also allows network administrators to be alerted quickly when new (possibly unauthorized) access points appear. Since the database is built by the entire user community, this essentially lets all of the users do the work of monitoring the network.

5 Bandwidth Advisor

A slightly more advanced application would be a wireless bandwidth advisor. Users experiencing a lack of connectivity could bring up a list of access points in the area, along with an indication of the load on each. Additionally, if the device notices that the network is currently slow and congested, it could proactively advise the user to move to a location that has lower usage. The bandwidth advisor application not only helps users by suggesting areas where they may obtain optimal service, it also helps the network by balancing network traffic.

[pic]

Implementing this service requires collecting usage statistics from access points using SNMP. For demonstration purposes, we chose to measure the number of users associated with each access point. Since the access points are behind a firewall that prevents direct SNMP access, we do this in two steps. Behind the firewall, a simple Perl script periodically polls each access point, recording the information in a log file. (Although our network environment uses several different types of wireless equipment, the Perl script records the information in a standardized format.) The log file is then made available to our service through a secure web server.

We can display a graphical representation of this information on a web site, as shown in the diagram above. It is also possible for users to “subscribe” to this service to be alerted when they enter an area that may be experiencing congestion. This application is currently operating as a proof of concept, but is not in production use.

6 Software as a Network Scanner

The software also works well as an ordinary Wi-Fi network scanner. For network administrators who are trying to deal with hundreds of access points in a confined area, it might be useful to figure out where those stray signals are coming from. The Wi-Fi scanner included as part of Herecast is one of the only scanners that functions with Pocket PC 2003.

Future Work

This section describes some of the future development that we would like to see occur with the Herecast system.

1 Future Applications

Community-building applications would benefit from location-awareness. This would be a logical extension of the Heresay service discussed earlier. For example, imagine an instant messaging application that allow users to broadcast messages to other people in the geographic area. This not only could be used to discover people you didn’t previously know are nearby (“does anyone want to go for lunch?”, “is anyone out there studying for the computer science exam?”), but also for facilitating communication between people you are already meeting with (sending documents, sending questions to the professor in the middle of a large lecture.) The ActiveCampus project at the University of California San Diego is an example of a location-aware application that is designed to foster campus communities and encourage participation in large classes [[vii]].

The “friend finder” type of application may also be used in a more limited sense to allow a user to locate their own computer, should it be lost or stolen. Since it is likely that the deployment of a wireless network on campus will lead to increased usage of notebook computers and PDAs, we might expect to see thefts increase. Indeed, earlier this year, the university police department issued an advisory regarding an increase in computer theft. Although this sort of service would work better if it were implemented in the network infrastructure itself, it may also be possible to implement it in the client. Of course, this would only work if the thief attempts to access the wireless network with the stolen equipment. Since many notebooks now include 802.11 networking as a standard feature, it is non-trivial to disable the wireless networking adapter. We may at least be able to protect users against the more opportunistic computer thief.

Getting away from the topic of work, games are an area of great potential for location-based services. A course in video development might be able to look into developing games in which players run around campus picking up objects, leaving things for other players, and so on. In Tokyo, one such “massively multiplayer role-playing game” exists today [[viii]]. Hong Kong is host to another location-based game, this one involving the search for terrorists [[ix]].

2 Database Management, Data Integrity and Privacy Issues

Access points, especially those owned by private individuals, might move. Currently, the only way to resolve this is to manually delete the access point from the database and re-create it somewhere else. In the meantime, it may cause the client to mistakenly download information for other cities. We have not fully dealt with this issue at this time.

There are some other database management features that need to be more fully implemented. For example, when a database is being created by large number of different users, it is inevitable that some people will spell the names of places differently from other people. There needs to be a facility to merge different spellings of the same item into a single object.

The lifetime of the data cache should also be addressed. Currently, downloaded data is cached indefinitely, and can only be cleared manually. This means that if new services are added via the web site, they will not appear clients until the client next has to download information.

It may also be desirable to limit the amount of information that can be obtained about private access points, such as those within a company. Although it is unclear whether the information about what building or room an access point is in could be perceived as a security risk, we will want to account for the possibility that someone will believe it to be so. Other papers have discussed these issues in similar systems [[x]].

Special consideration may need to be made for privately owned access points. What a user may refer to his own access point as “Home” or “Bob’s House,” this designation will not make sense to someone else. The database should not store such private information.

3 GPS Integration

Although not a core requirement of the system, it would be possible to add GPS information (latitude and longitude) to complement the existing symbolic representation. This would make it possible to gather a large amount of information quickly, using the “war-driving” method—driving around a city, letting the device automatically gather and record the coordinates of many access points.

This would open up additional possibilities for services, as coordinates are well suited for generating maps and calculating the relative distance between two points. Gathering this information raises its own issues in topics such as how to average location information from multiple sightings, how to determine when an access point has moved, and so on.

4 PlaceLab

PlaceLab is another Wi-Fi Positioning project underway at the University of Washington, University of California at Berkeley, and Intel Corporation [[xi]]. Although PlaceLab takes a slightly different approach in some areas, many of the key goals and motivations are the same. (The main difference is in their use of GPS as the primary positioning mechanism.) We would like to more fully explore the differences and similarities between the two projects, and see how we might be able to work together.

5 Offline Services

An organization that provides a directory of Wi-Fi “hotspots” would like to make their information available using Herecast, allowing users to locate the nearest free wireless internet access. The usefulness of such a service is severely limited by the fact that in order to access this hotspot directory, the user must already have a working internet connection.

In order to solve this problem, we would like to provide a way for services to pre-cache information on the mobile device, allowing it to be searched while offline. This would require a great deal of thought in order to ensure that the facility would be useful to a variety of services. In addition to the “hotspot locator” example, many other lookup services would be enhanced if an internet connection were not required.

6 Autonomous Map Generation

One advantage of a coordinate-based position system over a symbolic system is that the coordinate system makes it easy to calculate the distance between two points. We would like to be able to compare distances between access points without knowing the absolute coordinates of those access points. To do this, we would need to automatically generate a logical map of the environment by observing user movements. Several techniques might be used to generate such a map. First, if users are frequently seen moving directly from access point A to access point B, the system could infer that those two access points are likely neighbours. Another idea is to record the minimum travel time between pairs of access points. Some of the techniques for environment mapping in more fine-grained location-based systems may apply to this coarse-grained system as well [[xii]].

Once this information is available, additional applications become possible. For example, knowing the travel time between two locations would make it possible to enhance the reminder feature of a personal information manager. Instead of always displaying an reminder 10 minutes before an appointment, the calendar should be take into account how long it will take the user to get to the building or room the appointment is in. If the user in a distant building, the calendar will warn the user earlier. Alternatively, if the user has already moved to the room where the meeting is to occur, the calendar does not need to remind the user at all.

This “logical map” would be independent of the existing database. It should be possible for a device to automatically determine where a recurring meeting is and guess the travel time to that location without needing to know anything further about the location. Names of places serve only to assist human readability.

Appendix A – Database Schema

CREATE TABLE apdb_network (

network_id int(10) unsigned NOT NULL auto_increment,

network_name varchar(31) NOT NULL,

network_description varchar(50) NOT NULL,

PRIMARY KEY (network_id),

UNIQUE KEY (network_name)

);

CREATE TABLE apdb_country (

country_id int(10) unsigned NOT NULL auto_increment,

country_name varchar(31) NOT NULL,

PRIMARY KEY (country_id),

UNIQUE KEY (country_name)

);

CREATE TABLE apdb_province (

province_id int(10) unsigned NOT NULL auto_increment,

country_id int(10) unsigned NOT NULL,

province_name varchar(31) NOT NULL,

PRIMARY KEY (province_id),

UNIQUE KEY (country_id, province_name)

);

CREATE TABLE apdb_city (

city_id int(10) unsigned NOT NULL auto_increment,

province_id int(10) unsigned NOT NULL,

city_name varchar(31) NOT NULL,

PRIMARY KEY (city_id),

UNIQUE KEY (province_id, city_name)

);

CREATE TABLE apdb_area (

area_id int(10) unsigned NOT NULL auto_increment,

city_id int(10) unsigned NOT NULL,

area_name varchar(31) NOT NULL,

PRIMARY KEY (area_id),

UNIQUE KEY (city_id, area_name)

);

CREATE TABLE apdb_building (

building_id int(10) unsigned NOT NULL auto_increment,

city_id int(10) unsigned NOT NULL,

building_name varchar(31) NOT NULL,

building_streetaddr varchar(31) NOT NULL,

PRIMARY KEY (building_id)

);

CREATE TABLE apdb_areabuilding (

building_id int(10) unsigned NOT NULL,

area_id int(10) unsigned NOT NULL,

PRIMARY KEY (building_id)

);

CREATE TABLE apdb_ap (

ap_id int(10) unsigned NOT NULL auto_increment,

ap_bssid varchar(12) NOT NULL,

building_id int(10) unsigned NOT NULL,

network_id int(10) unsigned NOT NULL,

ap_floor varchar(31) NOT NULL,

ap_name varchar(31) NOT NULL,

PRIMARY KEY (ap_id),

UNIQUE KEY (ap_bssid)

);

CREATE TABLE apdb_service (

service_id int(10) unsigned NOT NULL auto_increment,

parent_type tinyint(4) NOT NULL,

parent_id int(10) unsigned NOT NULL,

service_name varchar(31) NOT NULL,

service_url varchar(100) NOT NULL,

PRIMARY KEY (service_id)

);

CREATE TABLE apdb_user (

user_id int(10) unsigned NOT NULL auto_increment,

user_name varchar(31) NOT NULL default '',

user_password_md5 varchar(32) NOT NULL default '',

user_email varchar(50) NOT NULL default '',

user_enabled tinyint(1) NOT NULL default '0',

user_created date NOT NULL default '0000-00-00',

user_lastseen date NOT NULL default '0000-00-00',

user_lastip varchar(15) NOT NULL default '',

user_badlogins tinyint(4) NOT NULL default '0',

user_uploads smallint(5) unsigned NOT NULL default '0',

user_ap_found mediumint(8) unsigned NOT NULL default '0',

user_ap_updated mediumint(9) unsigned NOT NULL default '0',

user_ap_ignored mediumint(9) unsigned NOT NULL default '0',

user_points mediumint(9) NOT NULL default '0',

group_id tinyint(4) NOT NULL default '5',

PRIMARY KEY (user_id),

UNIQUE KEY user_name (user_name)

);

CREATE TABLE apdb_user_access (

user_id int(10) unsigned NOT NULL default '0',

item_type tinyint(3) unsigned NOT NULL default '6',

item_id int(10) unsigned NOT NULL default '0',

KEY user_id (user_id)

);

CREATE TABLE apdb_user_accessreq (

user_id int(10) unsigned NOT NULL default '0',

item_type tinyint(3) unsigned NOT NULL default '6',

item_id int(10) unsigned NOT NULL default '0',

req_date datetime NOT NULL default '0000-00-00 00:00:00',

req_votes smallint(6) NOT NULL default '0',

KEY user_id (user_id)

);

CREATE TABLE apdb_user_group (

group_id smallint(5) unsigned NOT NULL auto_increment,

group_name varchar(31) NOT NULL default '',

max_access_type tinyint(4) NOT NULL default '4',

max_access_entries tinyint(4) NOT NULL default '2',

max_access_entries_network tinyint(4) NOT NULL default '2',

wait_hours_access tinyint(3) unsigned NOT NULL default '240',

wait_hours_change tinyint(3) unsigned NOT NULL default '240',

PRIMARY KEY (group_id)

);

CREATE TABLE apdb_changelog (

change_id int(10) unsigned NOT NULL auto_increment,

item_type tinyint(4) NOT NULL default '0',

item_id int(10) unsigned NOT NULL default '0',

user_id int(10) unsigned NOT NULL default '0',

change_date datetime NOT NULL default '0000-00-00 00:00:00',

change_desc varchar(255) default NULL,

change_undo_sql varchar(255) default NULL,

PRIMARY KEY (change_id),

KEY user_id (user_id),

KEY item (item_id,item_type)

);

CREATE TABLE apdb_changereq (

req_id int(10) unsigned NOT NULL auto_increment,

item_type tinyint(4) NOT NULL default '0',

item_id int(10) unsigned NOT NULL default '0',

user_id int(10) unsigned NOT NULL default '0',

req_date datetime NOT NULL default '0000-00-00 00:00:00',

req_desc varchar(255) default NULL,

req_sql varchar(255) default NULL,

req_undo_sql varchar(255) NOT NULL default '',

req_votes smallint(6) NOT NULL default '0',

PRIMARY KEY (req_id),

KEY user_id (user_id),

KEY item (item_id,item_type)

);

References

-----------------------

[[i]] M. Addlesee, R. Curwen, S. Hodges, J. Newman, P. Steggles, A. Ward, and A. Hoppe, “Implementing a Sentient Computing System,” Computer, IEEE, August 2001, pp. 50-56.

[[ii]] J. Hightower, G. Borriello, “Location Systems for Ubiquitous Computing”, Computer, IEEE, August 2001, pp. 57-66.

[[iii]] S. G. M. Koo, C. Rosenberg, H. Chan, and Y. C. Lee, “Location Discovery in Enterprise-Based Wireless Networks: Case Studies and Applications,” Annals of Telecommunications, 2003.

[[iv]] S. G. M. Koo, C. Rosenberg, H. Chan, and Y. C. Lee, “Location-based E-Campus Web Services,” Adjunct Proceedings of UbiComp 2003.

[[v]] P. Bahl, V. N. Padmanabhan, “RADAR: An in-building RF-based user location and tracking system,” Proceedings of IEEE INFOCOM 2000, pp. 775-784, Mar 2000.

[[vi]] XML-RPC web site,

[[vii]] W. G. Griswold, R. Boyer, S. W. Brown, T. M. Truong, E. Bhasker, G. R. Jay, and R. B. Shapiro, “Using Mobile Technology to Create Opportunitistic Interactions on a University Campus”, UbiComp 2002 Workshop on Supporting Spontaneous Interaction in Ubiquitous Computing Settings, Sept 2002.

[[viii]] J. Hall, “Mogi: Second-Generation Location-Based Gaming,” The Feature, Apr 2001.

[[ix]] YDreams, “Undercover,”

[[x]] J. Hong, G. Borriello, J. Landay, D. McDonald, B. Schilit, and D. Tygar, “Privacy and Security in the Location-enhanced World Wide Web”, Proceedings of Ubicomp 2003, October 2003.

[[xi]] B. Schilit, A. LaMarca, G. Borriello, W. Griswold, D. McDonald, E. Lazowska, A. Balachandran, J. Hong and V. Iverson, “Challenge: Ubiquitous Location-Aware Computing and the Place Lab Initiative,” in Proceedings of The First ACM International Workshop on Wireless Mobile Applications and Services on WLAN (WMASH 2003), September 2003.

[[xii]] R. K. Harle, A. Hopper, “Using Personnel Movements for Indoor Autonomous Environment Discovery,” Proceedings of the First IEEE International Conference on Pervasive Computing and Communication, 2003, p. 125.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download