Abstract:
Disclosed is an indoor location system that uses an electrical power line, power line signal injection devices, and portable position receivers (tags) to generate location data relating to positions of the tags in a structure such as a residence or business. The indoor location system fingerprinting of multiple signals transmitted along the power line to achieve sub-room-level localization of the positioning receivers. Details regarding power line positioning are described along with how it compares favorably to other fingerprinting techniques.

Description:
BACKGROUND  
       [0001]     The present invention relates generally to indoor location systems, and more particularly, to indoor location systems that employ radio signals transduced via power lines.  
         [0002]     Recent advances in indoor location systems leverage existing wireless communication infrastructure (e.g., 802.11 and GSM) to provide a value-added location service. The major advantage of these approaches is that a user does not have to purchase any specialized equipment and can still benefit from location-aware computing. Leveraging public infrastructure has many advantages, but one major drawback is that users have very little control of the infrastructure itself. Service providers adjust the operational parameters of WiFi access points and cellular towers with little or no warning. These changes require recalibration of the location system and may result in inaccurate location data until the changes are discovered. An alternative is to introduce new infrastructure in the home by distributing many low-cost, short-range beacons. The time required for installation and the possible impact to home aesthetics, however, may limit adoption.  
         [0003]     Indoor positioning has been very active in the ubiquitous computing research community in the subsequent half decade. Several characteristics distinguish different solutions, such as the underlying signaling technology (e.g., IR, RF, load sensing, computer vision or audition), line-of-sight requirements, accuracy, and cost of scaling the solution over space and over number of items. Although we do not intend to provide a complete survey of this topic, we highlight those projects with characteristics most relevant to the motivation for power line positioning, namely the requirements for additional infrastructure and algorithmic approach.  
         [0004]     The earliest indoor positioning solutions introduced new infrastructure to support localization. See, for example, “Active Bat.” The BAT Ultrasonic Location System, 2006; O&#39;Connell, T., Jensen, P., Dey, A. K., and Abowd, G. D., “Location in the Aware Home,” Position paper for Workshop on Location Modeling for Ubiquitous Computing at Ubicomp 2001 Sep. 30, Atlanta, Ga., 2001; Priyantha, N. B., Chakraborty, A., and Balakrishnan, H., “The Cricket Location-Support System,” Proceedings of  The International Conference on Mobile Computing and Networking  ( Mobicom  2000), Boston, Mass., August, 2000; and Want, R., Hopper, A., Falcao, V., and Gibbons, J., “The active badge location system,” “ ACM Transactions on Information Systems, ” Volume 10, pp. 91-102, January, 1992.  
         [0005]     Despite some success, as indicated by some commercialized products, the cost and effort of installation are a major drawback to wide-scale deployment, particularly in domestic settings. Thus, many new projects in location-based systems research reuse existing infrastructure to ease the burden of deployment and lower the cost. The earliest demonstrations leveraged 802.11 access points (see, for example, Bahl, P. and Padmanabhan, “V. RADAR: An In-Building RF-Based User Location and Tracking System,” Proceedings of  IEEE Infocom,  Los Alamitos, pp. 775-784, 2000; Castro, P., Chiu, et al., “A Probabilistic Room Location Service for Wireless Networked Environments,” Proceedings of  Ubicomp  2001, pp. 18-34, 2001; and LaMarca, A., et al., “Place Lab: Device Positioning Using Radio Beacons in the Wild,” Proceedings of  Pervasive  2005, Munich, Germany, pp. 116-133, 2005. More recent examples explore Bluetooth (see, for example, Madhavapeddy, A. and Tse, T., “Study of Bluetooth Propagation Using Accurate Indoor Location Mapping,”  The Seventh International Conference on Ubiquitous Computing  ( UbiComp  2005), Tokyo, Japan, pp 105-122, September 2005, and wireless telephony infrastructure, such as GSM (see, for example, V. Otsason et al., “Accurate GSM Indoor Localization,” Proceedings of  The Seventh International Conference on Ubiquitous Computing  ( UbiComp  2005), Tokyo, Japan, September, 2005), or FM transmission towers (see, for example, Krumm, J., Cermak, G., and Horvitz, E., “RightSPOT: A Novel Sense of Location for a Smart Personal Object,” Proceedings of  Ubicomp  2003, Seattle, Wash., pp. 36-43, 2003. Concerns about system resolution eliminate the FM solution for domestic use.  
         [0006]     Another concern we highlighted in the introduction is that individuals and households may not be able to control the characteristics of this infrastructure, resulting in the need to recalibrate if parameters change. The desire to control the infrastructure and to scale inexpensively to track a large number of objects inspired the search for a solution like the power line system presented here.  
         [0007]     Traditional wireless signal triangulation, such as 802.11 access point triangulation, uses Received Signal Strength Indicator (RSSI) information to estimate distance and determine a location based on geometric calculations employing the RSSI data. Other techniques include the use of Time of Arrival, as in the case of ultrasound, or Angle of Arrival, such as with Ultra-wideband positioning (see the Ubisense website, for example). Ultrasonic solutions, such as Cricket (see Priyantha, N. B., et al., “The Cricket Location-Support System,” Proceedings of  The International Conference on Mobile Computing and Networking  ( Mobicom  2000), Boston, Mass., August, 2000, and Active Bat, the BAT Ultrasonic Location System, provide precise centimeter resolution, but require line-of-sight operation indoors. Therefore, they require extensive sensor installations for full coverage. Some radio frequency technologies, such as 802.11 triangulation, employ overdetermination of transmitting sites (e.g., wireless access points) to avoid issues of occlusion induced by multipath propagation caused by reflections in the environment.  
         [0008]     Fingerprinting of the received signals can help overcome the multipath problem. Fingerprinting improves on other means of estimation by taking into account the effects that buildings, solid objects, or people may have on a wireless or RF signal, such as reflection and attenuation. Fingerprinting works by recording the characteristics of wireless signals at a given position and later inferring that position when the same signature is seen again. A survey of signals over a surveyed space allow for the creation of a map that can be used to relate a signal fingerprint to a location.  
         [0009]     Power lines are already in place in most buildings and the power network reaches more homes than either cable systems or telephone lines. Thus, for many years, people have been using power lines in buildings (especially homes) to deliver more than just electricity. Several home automation technologies leverage the power line for communications and control. The most popular example is the X10 control protocol for home automation, a standard that is more than 30 years old and is a very popular, low-cost alternative for homeowners. Over the past decade, there have been a number of efforts to produce power line communications capabilities, driven by industrial consortia such as the HomePlug Powerline Alliance, and efforts such as Broadband over Powerline (BPL). Because electricity used for power is sent over power lines at a lower frequency (e.g., 60 Hz) than Internet data signals modulated on high frequency carriers, power and data can coexist on the same power line without interference.  
         [0010]     It would be desirable to have an indoor location system that takes advantage of existing infrastructure, such as electrical power lines, and the like, and which does not require additional infrastructure. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0011]     The various features and advantages of the present invention may be more readily understood with reference to the following detailed description taken in conjunction with the accompanying drawings, wherein like reference numerals designate like structural elements, and in which:  
         [0012]      FIG. 1  illustrates an exemplary indoor location system installed in an exemplary building, in this case a residence;  
         [0013]      FIG. 2   a  illustrates an exemplary user interface employed to map and localize the position of a connected receiver;  
         [0014]      FIG. 2   b  illustrates a photograph of a reduced-to-practice user interface;  
         [0015]      FIGS. 3   a  and  3   b  illustrate exemplary signal maps of a bedroom and kitchen of a home;  
         [0016]      FIG. 4  illustrates an exemplary tagging implementation that may be used in the indoor location system;  
         [0017]      FIG. 5  illustrates the percentage of incorrect room predictions identifying a room that is adjacent to the correct room;  
         [0018]      FIG. 6  is a graph that illustrates the effect of number of modules on room-level and sub-room-level classification accuracies; and  
         [0019]      FIGS. 7   a - 7   d  illustrate temporal signal stability in a kitchen area of Home  2 . 
     
    
     DETAILED DESCRIPTION  
       [0020]     Disclosed is an exemplary indoor location system that uses an electrical power line as a signaling infrastructure to simultaneously track multiple objects, and which may be used in buildings or structures, such as homes and business buildings, and the like. An affordable, whole-building indoor localization system is described below, that works in a vast majority of households, scales cost-effectively to support tracking of multiple objects simultaneously and does not require the installation of additional new infrastructure. The solution requires installation of at least two transmission modules that are connected to or plugged-into a building&#39;s electrical system at different locations within the building. These modules inject a low-frequency, attenuated signal throughout the electrical system of the building. Simple receivers, or positioning tags, listen for these signals and wirelessly transmit their positioning readings back to a base station. The base station is used to process the transmitted signals to produce a location map containing spatial locations of the positioning tags. The base station may use a two-phase localization algorithm based on signal fingerprinting to provide position location. Alternatively, in other embodiments, the processing sometimes performed in the base station may be incorporated into the positioning tag.  
         [0021]     This solution, referred to as power line positioning (PLP) is capable of providing sub-room-level positioning for multiple regions of a building and has the ability to track multiple tags simultaneously. Power line positioning has a localization accuracy of 87-95% for classifying regions at 3-4 meters resolution. An embodiment of this system has been reduced to practice, installed and tested in several buildings, and its performance has been compared against existing 802.11 and GSM solutions.  
         [0022]     Referring to the drawing figures,  FIG. 1  illustrates an exemplary indoor location system  10 , comprising a power line positioning system  10 . The indoor location system  10  uses an electrical power line  12  (or wiring of an electrical system  12 ) as a signaling infrastructure to simultaneously track multiple objects (positioning tags  14 ) located in a home  11 , for example. The indoor location system  10  may be used in any structures  11 , including homes  11  and businesses  11 , for example.  
         [0023]      FIG. 1  shows placement of at least two signal-generating modules  13  at extreme ends of a house  11 . It is to be understood, however, that many such signal-generating modules  13  may be employed throughout the home  11 . The number of signal-generating modules  13  generally determines the resolution of the system  10 . Signal-generating modules  13  may comprise off-the-shelf, plug-in tone generator modules. The positioning tag  14 , which comprises a receiver  15  and antenna  16  is wirelessly coupled to a computer  17  comprising a receiver  18  and an antenna  19 , that is used for processing signals to determine position location of the tags  14 . In this embodiment, the computer  17  performs the functions of the base station processing, although in other embodiments the base station processing is performed by a processor collocated with the positioning tag.  
         [0024]     Theory of Operation  
         [0025]     The power line positioning system  10  is loosely related to a wire-finding technique employed by many electricians and utility workers to locate or trace hidden wires behind a wall or underground. In the wire-finding technique an electrician connects an exposed end of a wire to a tone generator, whose signal can range from 10-500 kHz, and locates the hidden wire using a handheld, inductive tone detector. Some detectors use LEDs to indicate the tone strength and others play an audible sound. In either case, the electrician scans the area for the loudest tone, indicating the approximate location of the wire. Following the presence of the tone reveals the path of the wire.  
         [0026]     The following properties of the wire-finding technique are leveraged and extended to produce a viable solution for the location system  10 . (1) It is easy and inexpensive to propagate a signal or tone throughout the entire electrical system  12  in the home  11  without any electrical interference. (2) It is possible to set the power of the signal so that it attenuates as it reaches the periphery of the home  11 , and the electrical wiring appears in varying densities throughout the home  11 , creating a time-independent spatial variation of the signal throughout the home  11 . (3) The tone detectors or receivers (position tags  14 ) are fairly simple, inexpensive to construct, and have low power requirements. It should be appreciated that it is anticipated that a system may consist of more than one position tag  14 .  
         [0027]     In the power line positioning system  10 , and as is illustrated in  FIG. 1 , the wire-finding technique is extended to include at least two plug-in signal generator modules  13 . The modules  13  are connected directly into electrical outlets of the electrical system  12 , and their respective signals emanate from those outlets to the rest of the home  11 . One of the at least two modules  13  is installed in an outlet close to a main electrical panel or circuit breaker, for example, and the other module  13  is plugged into an outlet which is placed along the power line infrastructure furthest from the first module  13 . In most cases, physical distance is a good estimate of electrical distance.  
         [0028]     In the case of a two-story house  11  with a basement, for example, one module  13  may be placed at a west end of the house  11  in the basement (where the main panel is located), for example, and the other in the east end on the second floor, for example. Each module  13  emits a different frequency signal throughout the power line of the electrical system  12 . As part of the installation, the signal strength is adjusted so that significant attenuation occurs and the signal still reaches the opposite end of the home  11 . Both modules  13  continually emit their respective signals over the power line and portable tag(s)  14  equipped with specially-tuned tone detectors (receivers  15 ) sense these signals in the home  11  and relay them wirelessly to the base station  17 . Depending on the location of the portable tag(s)  14 , the detected signal levels provide a distinctive signature, or fingerprint, resulting from the density of electrical wiring present at the given location. The base station  17  (e.g., wireless receiver  18  and antenna  18  connected to a PC) analyzes the fingerprint and maps the signal signature to its associated location based on a site survey. More than one tag  14  may be present in the building and each tag  14  may independently receive power line transduced signals for the purpose of computing the position of each tag  14 .  
         [0029]     Phase difference between signals is another signal feature that may be leveraged for localization. A pair or group of signals generated in relative synchrony at harmonically or sub-harmonically related frequencies will exhibit a phase difference due to radio propagation in the building&#39;s wiring as well as due to differences in radio propagation delay through the interior of the building. This phase difference can be employed as another feature in the fingerprinting localization algorithm presented herein.  
         [0030]     When the modules  13  are active, the tone detector or positioning tag(s)  14  picks up the presence and amplitude of the power line transduced signals throughout the home  11 . Because electrical wiring typically branches inside the walls, ceiling, and floors, signal will be present throughout much of the main living areas of the home  11 . Three factors contribute to the amplitude of the signal received by the tag(s)  14  at any given location: (1) the distance between the tag(s)  14  and electrical wiring; (2) the density of electrical wiring in an area; and (3) the distance from the transmitting modules  13  to the tag(s)  14 .  
         [0031]      FIG. 2   a  illustrates an exemplary user interface implemented in the computer  17  that may be used to map and localize the position of a connected receiver.  FIG. 2   b  illustrates a photograph of a reduced-to-practice user interface. The computer  17  has a display screen on which a layout of the home  11  is presented. The spatial position of the positioning tag(s)  14  is determined using software implemented on the computer  17 .  
         [0032]      FIG. 3   a  shows an exemplary signal map of a bedroom of the home  11  and  FIG. 3   b  shows an exemplary signal map of a kitchen of the home  11 . In each cell, the left-hand number corresponds to signal strength from one transmitting module or device  13  and the right-hand number corresponds to the signal strength of the other transmitting module or device  13 . In the bedroom, the strength of both signals increases near the walls where there is the greatest concentration of electrical wiring and outlets. The strength of signal A (left value in each cell shown in  FIGS. 3   a  and  3   b ) is weaker than the strength of signal B (right value in each cell) in the kitchen, and the opposite is true for the bedroom. Because the two rooms are on different floors and at opposing ends of the house  11 , each room is closer to a different module  13 .  
         [0033]     Most residential homes and apartments in North America and many parts of Asia have a single phase or a split single phase electrical system, which enables any signal generated on a given outlet to reach the entire electrical system. Larger buildings and some homes in Europe have two and three phase electrical systems, in which the electrical system may split into separate legs for lower voltage applications. For multi-phase electrical systems, the signal can be coupled between the phases using a capacitor. In a home, this would typically be plugged-in in a 240 V outlet, such as that used for clothes dryer. The present description focuses on common residential single or split single phase electrical systems operating at 60 Hz. However, the system may be readily adapted for use in other electrical systems.  
         [0034]     Power Line Positioning Localization Algorithm  
         [0035]     The power line positioning system  10  relies on a fingerprinting technique for position localization. This technique requires generation of a signal topology map via a site survey which may be performed either manually or automatically, for example by a robotic device that automatically visits multiple locations in the building to perform the site survey. The granularity of the survey influences the final accuracy of the positioning system  10 . For power line positioning in the home  11 , the site survey is a one-time task provided the transmitting modules  13  emit a consistent power level, stay fixed in place, and the electrical characteristics of the home  11  remain substantially the same.  
         [0036]     Effective application of fingerprinting requires the signals to have low temporal variations, but high spatial variation and relatively low correlation from one location to another. As discussed above, the propagation of signals transmitted via the power line  12  exhibits both of these properties, because the detected signals vary little unless the modules  13  are moved or the electrical system  12  has been significantly remodeled. The use of two different signals and the variability in the electrical wire density throughout the home  11  provides this spatial variation.  
         [0037]     An exemplary localization algorithm that may be used in the power line positioning system  10  proceeds in two steps. The first step predicts the location of a positioning tag  14  in terms of which room it is located within, and the second predicts the location of a positioning tag  14  in terms of sub-regions within that room. Both may use k-nearest neighbor (KNN) classification.  
         [0038]     k-Nearest Neighbor (KNN) Classification  
         [0039]     The room and sub-room localizers (positioning tag(s)  14 ) may use k-nearest neighbor (KNN) classification to determine the receiver&#39;s room location. KNN is discussed by T. Mitchell, in  Machine Learning,  McGraw Hill, ISBN 0070428077, 1997. KNN is a memory-based model defined by a set of objects known as learned points, or samples, for which the outcomes are known. Each sample consists of a data case having a set of independent values labeled by a set of dependent outcomes. Given a new case of dependent values (the query point or unknown value), we estimate the outcome based on the KNN instances. KNN achieves this by finding k examples that are closest in distance to the query point. For KNN classification problems, as discussed herein, a majority vote determines the query point&#39;s class. For this task, given an unlabeled sample, the k closest labeled room samples in the surveyed data are found and assigned to the room that appears most frequently within the k-subset. For our distance measure d, the Euclidean distance,  
           d   ⁡     (     x   ,   y     )       =       (       ∑     i   =   1     2     ⁢       (       x   i     -     y   i       )     2       )         ,       
 
 in which tuples x=&lt;Signal A x1 , Signal B x2 &gt; and y=&lt;Signal A y1 , Signal B y2 &gt;. The tuple x refers to a labeled signal point and triple y refers to the unlabeled query point sensed by the positioning tag  14 . For more modules  13 , the dimension is increases to match the number of modules  13 . 
 
         [0040]     Room and Sub-Room Localization  
         [0041]     One difference between the room and sub-room classifiers are the labels assigned to the data points and the value for k used in the localization. For room level classification, room labels are assigned to samples from the site survey. In the sub-room classification, the same samples are subdivided and sub-room labels are assigned to them. For each home  11 , there is an optimal and initially unknown value of k for the room level localizer. Within the same home  11  there is an optimal value for the sub-room level localizer for each room. Thus, for localization, the KNN classification is first executed using the room labeled samples and its optimal k value. After determining the room, KNN is executed on the sub-room labeled samples from that room and its optimal k value to determine the sub-room.  
         [0042]     Training the System and Determining k in KNN  
         [0043]     The choice of k is essential in building the KNN model and strongly influences the quality of predictions, for both room-level and sub-room-level localization. For any given problem, a small value of k will lead to a large variance in predictions. Alternatively, setting k to a large value may lead to a skewed model. Thus, k should be set to a value large enough to minimize the probability of misclassification and small enough (with respect to the number of cases in the example sample) so that the k nearest points are close enough to the query point. Thus, an optimal value for k that achieves the tight balance between the bias and the variance of the model. KNN can provide an estimate of k using a cross-validation technique discussed in the Machine Learning reference previously cited.  
         [0044]     Splitting the localization into two steps can help control the cluster sizes. In classifying the room, a larger value of k is used so that a larger region is considered when trying to find where the unknown signal potentially maps. To localize within a room, smaller values of k are used so that finer clusters are match and because of the smaller data sets within a room than the whole home  11 .  
         [0045]     The training interface allows end users to build a signal map of the home  11  (see  FIGS. 2   a  and  2   b ). The user loads a pre-made or hand-drawn floor plan of the home  11  into the application. The interface displays the floor plan, and one physically travels to different locations in the home  11  and chooses the approximate location on the floor plan. When a location is selected, the application stores the fingerprint for that location, which is a one-second average of the amplitude of the at least two detected signals from the at least two transmitting modules. The same process continues throughout the home  11 . Surveying at a granularity of approximately 2-3 meters in each room produces more than sufficient accuracy for the test cases presented below. The interface allows the user to assign meaningful labels to different room and sub-room areas, such as “kitchen” and “center of master bedroom.” 
         [0046]     For optimal performance in sub-room level localization, each room may be segmented into five regions: the center of the room and areas near the four walls of the room. The user is free to select the location granularity (assuming sufficient training sets) of their choice for important regions. However, the desired segmentation may not reflect the actual segmentation the underlying set of signals can provide. For example, a user may want to segment the middle part of a bedroom into four regions, but there might not be enough signal disparity among those regions for the KNN classifier to work well. Some assistance may be provided in overcoming those limitations by automatically clustering the room into potential sub-regions that are likely to be accurately classified based on the room&#39;s signal map. A k-means clustering algorithm may be employed to provide graphical suggestions on where to segment for a desired number of sub-regions.  
         [0047]     After construction of the signal map and all data has been labeled, the algorithm cross-validates model data to find suitable k values for the room and sub-room classifiers. Cross-validation involves the division of the data samples into a number of v folds (randomly drawn, disjoint sub-samples or segments). For a fixed value of k, the KNN model is applied on each fold and the average error is evaluated. The algorithm repeats these steps for various k values. The algorithm selects the value for k achieving the lowest error (or the highest classification accuracy) as the optimal value for k. This value for k depends on the home  11  and the number of sample points. Generally, optimal k values are seen near  10  for the room localizer and k values near 3-5 for the sub-room localizer.  
         [0048]     Module Design  
         [0049]     For rapid development and investigation, commercially available tone generators (modules  13 ) and tone detectors (tags  14 ) used by electricians were modified for use as part of the tags  14 . In particular, a Textron Tempo 508S tone generator module and a Pasar Amprobe 2000 were used in one embodiment. These modules  13  produce a 447 kHz and 33 kHz tone, respectively, on an energized 120 VAC power line  12  without causing any interference to household appliances. In addition, the modules  13  are powerful enough to transmit a tone up to 500 meters over the electrical wire  12  (both hot and ground). The modules  13  are tuned to emit at a lower signal to control propagation through the electrical system  12 . For one prototype that has been reduced to practice as part of a power line positioning system  10  discussed herein, the signal strength was manually adjusted depending on the size of the home  11 . Samples were collected with the tag  14  near the module  13  and samples near the opposite side of the home  11  where the second module is located. The signal strength was tuned so that a large signal difference between the two locations was produced without turning it down so much that the signal did not reach the far end. In most cases, approximately a 2.5 dB loss was produced from end to end.  
         [0050]     Although the steps described above were manually performed, it is anticipated to build the modules  13  to self-calibrate during the installation and surveying steps. It is also anticipated to perform a manual or robotic check step wherein the calibration is confirmed over time at specific location(s).  
         [0051]     Tag Design  
         [0052]     A Textron Tempo 508R passive wideband tone detector was modified to act as a prototype tag  14  that would send sensed signals to a portable computer  17  for analysis and position location determination. The tone detector has a built in frequency divider that maps a range of high frequency tones to audible sounds while still preserving the amplitude of the original signal. The tone detector&#39;s internal frequency divider translated a 447 kHz signal to about 1000 Hz and 33 kHz signal to about 80 Hz. The tone detector was altered to interface with the audio line-in jack of a portable computer to capture the signals.  
         [0053]     A rather large prototype tag  14  was used that was easy to build. There are a variety of ways to construct a small and inexpensive version of this tag  14 . One way is to feed the radio transducer or antenna  16  through a series of operational-amplifiers and into a DsPIC microcontroller. A low-power radio transmitter, such as those manufactured by Ming or Linx, or a WiFi (IEEE 802.11), Bluetooth radio, Zigbee radio, or any other wireless communication device may be used to transmit the readings back to the base station computer  18 . Alternatively the need for a microcontroller may be bypassed by using multiple tone decoder ICs, similar to the NE567 IC, which supports signal power output. Powered by a small lithium cell, the tag  14  may easily be the size of a small key fob and run for a significant period of time using a motion switch to enable the circuitry when the positioning tag  14  is moved.  
         [0054]     Software  
         [0055]     In the experimental set-up, an application was written in C++ using a Microsoft Windows Win32 application programming interface (API) to sample the signal from the sound card&#39;s line-in jack where the prototype receiver tag is connected. The application acquires 16-bit samples from the receiver of the positioning tag  14  at a rate of up to 44 kHz and performs a Fast Fourier Transform (FFT) on the incoming signal to separate component frequencies for analysis. The application performs this analysis in very close to real-time and makes the raw signal strengths for the two frequencies of interest (447 kHz and 33 kHz) available through a TCP connection for other parts of the power line positioning system  10  to access (see  FIG. 4 ).  FIG. 4  illustrates an exemplary tagging implementation that may be used in the indoor location system  10 .  
         [0056]     The experimental prototype used for empirical validation consisted of a Sony Vaio-U handheld computer with all software applications (signal receiver, learner, and the user interfaces) loaded and the receiver hardware connected (see  FIGS. 1 and 4 ).  FIG. 4  illustrates an exemplary user interface used for mapping and localizing the position of the tag  14 . Using this small but powerful device provides an easy way to survey homes  11 .  
         [0057]     Performance Evaluation  
         [0058]     The performance of the power line positioning system  10  was evaluated in 8 different homes  11  of varying styles, age, sizes, and locations, all in the same metropolitan city. Both older homes  11  with and without remodeled and updated electrical systems were chosen (see Table 1 for specifications of the homes). In addition to evaluating the system  10 , infrastructure tests of WiFi and GSM availability was simultaneously conducted to provide some comparison with other indoor localization results. The infrastructure tests only involved logging the availability of wireless 802.11 access points and multiple GSM towers in the home. A WiFi spotter application running on the Sony Vaio-U computer logged the wireless access points, and an application written on the Audiovox SMT-5600 GSM mobile phone logged available cellular telephone base stations.  
         [0059]     In each home  11  that was analyzed, the power line positioning system  10  was installed, the two transmitting devices or modules  13  were calibrated and a signal map was created by surveying the home  11 . When creating the signal map, multiple signal readings were taken every 2-3 meters throughout the home  11  to ensure enough training and test data was gathered for cross-validation. After creating the signal map, the interface on the handheld computer  17  was used to assign the appropriate room and sub-room labels to the data.  
         [0060]     The classification accuracy of the room and sub-room predictors is presented below. The sub-room accuracy was calculated independent of the room-level predictor. Thirty-four (34) meter regions were used for the sub-room-level tests. To obtain the room-level accuracy, a 10-fold cross-validation on the room localizer was conducted using the collected data samples. This test was repeated for various k values to find the best accuracy measure. To determine the sub-room level accuracy, the data samples for each room were taken and a 10-fold cross-validation was performed using the sub-room localizer, again for different values of k. Similar to the room-level tests, the k value that provided the highest accuracy for predicting regions in a room were searched for. After testing each room, we average all the sub-room localization accuracies to produce an overall accuracy value.  
         [0061]     Table 1 shows details of the homes where the power line positioning system  10  was deployed and evaluated.  
                                       TABLE 1                                   Floors/                           Electrical   Total Size       Bedrooms/           Year   Remodel   (Sq Ft)/       Bathrooms/   Population       Home   Built   Year   (Sq M)   Style   Total Rms.   Density                   1   2003   2003   3/4000/371   1 Family House   4/4/13   Suburb       2   2001   2001   3/5000/464   1 Family House   5/5/17   Suburb       3   1992   1992   1/1300/120   Apartment   2/2/6   Downtown       4   2002   2002   3/2600/241   1 Family House   3/3/12   Suburb       5   1967   2001   2/2600/241   1 Family House   3/3/11   Suburb       6   1950   1970   1/1000/93   1 Family House   2/2/5   Suburb       7   1926   1990   1/800/74   1 Bedroom Loft   1/1/5   Downtown       8   1935   1991   1/1100/102   1 Family House   2/1/7   Suburb                  
 
         [0062]     Power Line Positioning Accuracy  
         [0063]     Between Homes Comparison  
         [0064]     In Table 2, the results of room-level and sub-room level accuracies of the power line positioning system  10  are reported for various homes  11 . Room accuracy ranged between 78-100% and sub-room accuracy ranged between 87-95%. The modern homes  11  and the older homes  11  with updated electrical infrastructure resulted in similar performance results. The updated electrical systems  12  in these homes  11  were accompanied with an overall remodel of the home  11  which tends to include the addition of electrical outlets and lighting. The single family home  11  that exhibited a significantly lower accuracy (Home  8 ) was an older home  11  with an updated electrical system  12 . However, that home  11  had a two phase electrical system,  12  which we only learned after installing the power line positioning system. Because it is a small home  11  and electrical phase one drives a small number of outlets, we simply placed the modules  13  on electrical phase two to produce acceptable (though not optimal) coverage throughout the home  11 . However, it is anticipated that installing a simple phase coupler to couple some of the positioning signal from electrical phase one to electrical phase two would have improved its performance.  
         [0065]     Condominium and apartment test cases also produced promising results. The condominium was converted from an office building, but the electrical system  12  was completely remodeled to a residential style system. Although one wall of the condominium used a metal conduit to run its electrical wire, the power line positioning system still worked because the room with the conduit was small and the receiver was never too far from the wall. The apartment also featured a similar residential style electrical system. Because of the small size of the living spaces, we had to turn down the power of the modules significantly in the two cases, unlike the larger homes  11  that were tested.  
         [0066]     Older homes  11  without an updated electrical system  12  exhibited lower results for two reasons. First, these homes  11  lack a proper electrical ground, resulting in one less path for the signal to propagate, because the signal was sent both on the hot and ground wires. Homes  11  with an updated electrical system  12  have an extra electrical ground wire running through the home  11 , which is usually grounded to the copper water pipes. This grounding enables additional signal propagations to certain areas of the home. Second, these homes  11  tended to have fewer electrical outlets than the modern or remodeled ones, resulting in poor detection in some areas.  
         [0067]     Table 2 shows accuracy results for each home  11 . For each home  11 , the accuracy of room-level prediction and the average sub-room-level prediction across all rooms are reported. The sub-room-level regions where defined to be approximately a 34 meters square. The WiFi and GSM measurements indicate the maximum number of access points or towers seen at all times during the surveying and the total number of unique access points or towers seen during the whole surveying period.  
                                                                             TABLE 2                           Size           Room   Sub-   WiFi   GSM           Sq Ft/   Sample   Rooms   Accuracy   Room   Always/   Always/       Home   Sq M   points   surveyed   at 3-4 m   Accuracy   Max   Max                                1   4000/371   194   13   89%   92%    3/12   3/5       2   5000/464   206   15   95%   93%   1/3   2/4       3   1300/120   95   6   90%   90%   3/7    4/12       4   2600/241   183   11   88%   87%   1/3   3/5       5   2600/241   192   10   92%   93%   2/4   3/6       6   1000/93   76   5   100%   94%   0/2   4/6       7    800/74   65   5   93%   95%    2/11   3/9       8   1100/102   80   7   78%   88%   2/6   3/7                  
 
         [0068]     Classification Errors  
         [0069]     To understand the types of classification errors encountered by the power line positioning system  10 , the confusion matrices for each home  11  were analyzed. For some homes  11 , most of the classification errors resulted from misclassifying rooms as one of the adjacent rooms. The adjacency errors appeared when trying to localize very near the boundary or the wall of a room. These errors were more prevalent in larger homes  11  near common walls between two adjacent rooms of similar size. Open spaces that were divided into multiple rooms also resulted in errors. Other homes  11 , however, exhibited more random classification errors possibly due to errors in the survey map, sparse sampling, or in error readings coming from the receiver at that time. One possible solution to guard against miss classifications is to use hysteretic data to compare against certain classifications and see if those classifications follow a valid trail. Some homes  11  could benefit from hysterics, especially those with significant random error (see  FIG. 5 ).  FIG. 5  is a graph that shows the percentage of incorrect room predictions identifying a room that is adjacent to the correct room.  
         [0070]     Number of Modules and Performance  
         [0071]     Accuracy tests were conducted using a varying number of modules  13 . Although the goal was to minimize the additional hardware the user must install in a home  11 , there might be cases in which higher accuracy is more desirable. Adding additional modules  13  is a primary way to increase overall accuracy.  FIG. 6  shows temporal signal stability in the kitchen area of Home  2 . The graphs show the signal values for the two transmitting modules  13  (combined using the Euclidean distance) over various intervals during four days of continuous recording. The average signal values and the standard deviations are shown above each graph.  
         [0072]      FIG. 6  shows both room-level and sub-room level accuracies for an increasing number of modules  13  for a particular home as an example. Additional modules  13  do increase the accuracy for both predictions, but there is a point of diminishing returns. For this home  11  (Home  1 ) two or three modules  13  are the best number. Similar trends were observed in other homes  11  that were tested and generally, two modules  13  were sufficient.  
         [0073]     Resolution  
         [0074]     In the initial evaluation, rooms were sub-divided into approximately 34 meter regions. This subdivision yielded high classification accuracies typically around 90%. Higher resolution, or smaller subdivisions of each room, is possible, but at the cost of classification accuracy. In addition, higher resolution also requires a more dense mapping of an area. To investigate the specific accuracy to resolution tradeoff, a fine-grain survey (sampling down to every 0.5 meter for a total of 96 samples) of a room (6 m×6 m) in Home  1  was performed. With the current implementation, the best obtainable practical resolution is 1 meter. The accuracy falls below 70% for 1 meter regions (see Table 3), because there is a theoretical limit to the detectable differences between small movements in the space and the signal. From observation, the maximum signal differential is about 20 units when moved 1 meter for a modern home  11 .  
         [0075]     Table 3 shows the sub-room-level accuracies for smaller sub-regions for a particular room in home  1 . A total of 96 points were surveyed.  
                                                                               TABLE 3                                       Sub-room region size                4 m   3 m   2 m   1 m   0.5 m                            % Accuracy   94%   91%   74%   67%   42%                      
 
         [0076]     Temporal Signal Stability  
         [0077]     Fingerprinting works best with a signal that is time-independent but spatially diverse. The data presented so far only considered results over relatively short periods of time, usually around an hour&#39;s worth of data collected at a particular home  11 . To test the stability of the signals over time, two separate tests were conducted. First, in Home  1 , we conducted separate surveys over the course of several weeks. The system  10  was trained on data from one survey and checked its accuracy against data collected from different surveys. Room prediction was correct 88% of the time (compared with the value of 89% for Home  1  in Table 3) and sub-room level prediction was correct 89% of the time (compared with the value of 90% in Table 3). Second, in Home  2 , 45 hours of data was collected over a three-day period (Saturday through Monday) in a single location (the kitchen). The kitchen is interesting because it contains a large number of features that could affect the transmitted signals (plentiful overhead lighting, appliances being turned on and off throughout the day, talking on a cordless phone, and people gathering around the tag).  FIGS. 7   a - 7   d  depict the stability of the signal for four different 3-hour intervals. The results suggest there is deviation (17 units on average), but it is not significant enough to cause major classification errors.  
         [0078]     Modifications to the electrical infrastructure can contribute to accuracy errors and require recalibration, a problem we noted for other infrastructure solutions (802.11 and GSM). However, most situations such as turning on a light only energize a portion of the electrical line and do not affect significantly the accuracy in our experience. Construction of a “day” and “night” map using a richer data set can allay some of these concerns. The addition of an extension cord may impact the accuracy, depending on location and length. The power line positioning system  10  may be designed to recognize potential changes in the infrastructure from hysteretic data to notify the user that re-surveying of a particular area is necessary.  
         [0079]     Although no problems were observed regarding electrical interference with continuous logging, electrical interference caused by home electronics and appliances was observed, such as from computers, televisions, and stereos. When the receiver was held next to some of these electronic devices, its broadband electrical noise often overwhelmed the receiver and caused spurious readings. This problem only existed when the receiver was very close (within a few centimeters) of such devices. To guard against learning or localizing incorrect fingerprints, one solution is to look for these signal interferences and filter out those readings, indicated by a clear broadband signature, before using the data in analysis.  
         [0080]     The power line positioning system  10  is very promising as an inexpensive and reliable sub-room-level indoor positioning service. In this section, we investigate the viability of this system and offer some comparison to previous solutions.  
         [0081]     Infrastructure and Cost Comparison Against WiFi and GSM  
         [0082]     The cost of infrastructure for WiFi is distributed across a community and assuming dense enough living conditions, it is a reasonable expectation a single residence will be able to leverage other access points nearby. This is less likely in sparser housing, in which case users would be required to purchase multiple WiFi access points. The cost of the infrastructure for GSM is covered by various cellular telephony service providers. The coverage is fairly dense in most metropolitan areas and will only get better over time. However, coverage is still fairly sparse in rural settings and many homes do not get very good cellular service in some rooms (see Table 2). Almost every home in the U.S. has electrical power and it is an assumed cost of the homeowner to maintain this infrastructure over the lifetime of the home. Thus, the infrastructure is already available and usually well maintained.  
         [0083]     One key advantage of leveraging the power line infrastructure  12  is user control of the infrastructure  12 . Users have very little control of the parameters of GSM cellular towers or a neighbor&#39;s WiFi access point, thus changes can happen unexpectedly . In contrast, users have control of the power line infrastructure  12 . Furthermore, there is stability in signal propagation over this infrastructure  12 .  
         [0084]     The cost and power requirements of the location tags  14  favors that of the power line positioning system  10  because of its simple sensing requirements, whereas as opposed to the more sophisticated chipset associated with GSM and WiFi reception. In addition, the cost of the transmitting module or device  13  would also be less expensive than buying additional access points if one were investing in a location system for the home  11 .  
         [0085]     The Power Line Infrastructure  
         [0086]     In the United States, modem homes  11  follow a strict electrical code called the National Electronic Code (NEC). Electrical codes only became widely enforced in the 1980s, although many homes before that already followed similar guidelines. Although the specific regulations may change depending on state and city ordinances, each follows the same general requirements. These regulations ensure the electrical systems are consistent across homes  11  of different sizes and styles. Specifically, the requirements outlined in the NEC favor the infrastructure requirements needed for the power line positioning system  10  to work in modern homes  11 . These requirements include regulations for certain “home run” circuits through the home  11 , a minimum number of outlets in a given space, and minimum lighting requirements throughout the home. Although the power line positioning system already performed reasonably well in older homes  11 , it consistently achieved very good results in the new or remodeled homes  11  that follow these requirements (see Table 3).  
         [0087]     The power line positioning system  10  was developed to provide an affordable location system for home environments. However, commercial buildings must comply with strict electrical codes for which the power line positioning system  10  must be altered to support. First, commercial wiring typically uses a two or three phase electrical system which prevents the signals from propagating throughout the entire electrical system. This problem is solved by installing an inexpensive phase coupler to couple transmitted signals back and forth among electrical phases. Second, most commercial electrical wiring runs through a metal conduit, which blocks significant portions of the tune emanating from the wire. One solution to this problem is to greatly increase the signal strength and the other is to send the signal both through electrical wiring and the metallic conduit itself. This problem also applies to homes  11  that have been converted from commercial buildings without remodeling the electrical system  12 .  
         [0088]     General Comparison of the Power Line Positioning System with 802.11 and GSM  
         [0089]     The significant advantage of PLP when compared against two popular fingerprinting techniques using WiFi/802.11 and GSM lies in the better resolution, control of the infrastructure and power requirements (see Table 4). Table 4 shows an overall comparison of PLP against two popular location systems that also use fingerprinting.  
                                                 TABLE 4                                   PLP   GSM   WiFi                                    Output Type   symbolic   symbolic   symbolic(geometric                   Using triangulation       Resolution and   3-4 m - 90%   20 m - 90%   6 m - 90%       Accuracy   1 m - 67%   2-5 m - 50%   2-3 m - 50%       Infrastructure   2 plug-in signal   Located within GSM   3-4 WiFi access points       Requirements.   modules   cellular service range       Infrastructure   Full   No   Partial (dependent on       Control           ownership of access                   points)       Spectral   10 kHz-500 kHz   900 MHz and 1800 MHz   2.4 GHz       Requirements       Update Rate   &gt;20 Hz   &gt;20 Hz   &gt;20 Hz       Tag power Req.   −50 mA (Pie + op-   −200 mA (GSM   −100 mA (μcontroller)           amp + antenna)   receiver module   operated will detector       Simultaneous   Theoretically no limit   Theoretically no limit   Theoretically no limit       tracking                  
 
         [0090]     The power line positioning system  10  is an indoor positing system for the home  11  or business that leverages its power line infrastructure  12  and requires only the addition of two plug-in modules  13  to the electrical infrastructure  12  and using simple location tags  14 . The system  10  is capable of localizing to sub-room level precision using a fingerprinting technique on the amplitude of signals produced by the two modules  13  installed in extreme locations of the home  11 . The density of electrical wiring at different locations throughout the home  11  provides a time-independent spatial variation of signal propagation.  
         [0091]     The experimental validation in eight different homes  11  identified the following advantages of the power line positioning system  10  over current indoor location solutions. (1) The power line positioning system  10  leverages a truly ubiquitous resource, the power line infrastructure  12 , available in almost all homes  11 . (2) The power line positioning system  10  requires minimal additions to the infrastructure  12  (two plug-in modules  13 ). (3) The power line positioning system  10  achieves superior sub-room-level classification, with an accuracy of 93% on average at a resolution of 34 meters. (4) The power line positioning system  10  does not detract from the appearance of the home  11 .  
         [0092]     In addition, other spatially varying signal features may be incorporated into the power line positioning system  10 , such as phase differences between the signals in addition to the amplitude to increase the accuracy of the power line positioning system in the fingerprinting process.  
         [0093]     Thus, indoor location systems that employ power line positioning techniques have been disclosed. It is to be understood that the above-described embodiments are merely illustrative of some of the many specific embodiments that represent applications of the principles discussed above. Clearly, numerous and other arrangements can be readily devised by those skilled in the art without departing from the scope of the invention.