Abstract:
A method and apparatus are disclosed for estimating the location of a wireless terminal across multiple building floors. The illustrative embodiment determines the floor where the wireless terminal is presently located by using a majority logic-based heuristic. A plurality of signal monitors measure signals from the wireless terminal and provide those signal strength measurements to a location estimation server. Alternatively, the wireless terminal measures signals that are transmitted by a plurality of transmitting signal devices and provides those signal strength measurements to a location estimation server. The location estimation server determines the floor of the wireless terminal in accordance with the illustrative embodiment of the present invention.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to telecommunications in general, and, more particularly, to estimating the location of a wireless terminal.  
       BACKGROUND OF THE INVENTION  
       [0002]      FIG. 1  depicts a schematic diagram of wireless network  100  in the prior art, which comprises wireless telecommunication terminal  101  and access points  102 - 1  through  102 -L, interconnected as shown. Wireless terminal  101  uses access points  102 - 1  through  102 -L to exchange blocks of data, or “packets,” with computer servers that are external to wireless network  100 . At any given time, wireless terminal  101  is associated with one of access points  102 - 1  through  102 -L for the purpose of communicating with the external servers.  
         [0003]     It is important in some operating scenarios to know the location of wireless terminal  101  within wireless network  100 . Knowing the location enables, for instance, services that use end-user location information. Such services include location-aware content delivery, emergency location, services based on the notion of “closest resource,” and location-based access control.  
         [0004]     Various techniques for estimating location exist in the prior art. Although some prior art techniques perform well in some operating environments, there are other operating environments in which prior art techniques do not perform adequately. The example that follows highlights a shortcoming in prior art techniques.  FIG. 2  depicts a schematic diagram of a cross-section of a building (e.g., an office complex, etc.). Access points  102 - 1  and  102 - 2  are situated on the first floor, access points  102 - 3  and  102 - 4  are situated on the second floor, and access points  102 - 5  and  102 - 6  are situated on the third floor.  
         [0005]     In determining the location of wireless terminal  101  in  FIG. 2 , the problem is first determining the floor on which wireless terminal  101  is presently located. It has often been assumed in the prior art that determining the floor at which wireless terminal  101  is located should be straightforward, since a typical building floor in a multi-story environment significantly attenuates the signal from wireless terminal  101 . Often, however, the signal from wireless terminal  101  can be received on more than one floor, as is the case in  FIG. 2 . The access points on multiple floors can receive a wireless terminal&#39;s signal in a variety of situations, such as where a building layout includes an atrium; where elevator shafts, stairwells, large ductwork, or escalators are present; etc. In these operating environments, it is sometimes the case that the floor receiving the strongest signal or the most signals is not the floor in which the wireless terminal is located.  
         [0006]     What is needed is a technique to improve estimating the location of a wireless terminals across multiple building floors without some of the disadvantages of the prior art.  
       SUMMARY OF THE INVENTION  
       [0007]     The present invention provides a technique to improve estimating the location of a wireless terminal across multiple building floors. The illustrative embodiment determines the floor where the wireless terminal is presently located by using a majority logic-based heuristic.  
         [0008]     In some embodiments of the present invention, signal monitors receive, detect, and measure transmitted signals from the wireless terminal. The receivers are present on all floors. The illustrative embodiment of the present invention applies the signal strength measurements made by the receivers to a Majority Rule and a Stability Rule. In the Majority Rule, a majority of the receivers from which the m strongest signals can be detected are in the same floor F. In the Stability Rule, adding a value K to the m+1st signal strength measurement does not change the decision. The value for m is the minimum value for which both the Majority and Stability Rules hold. The wireless terminal is identified as being on floor F, in accordance with the illustrative embodiment of the present invention.  
         [0009]     In some other embodiments of the present invention, transmitting signal devices that are present on all floors transmit signals that are received by a wireless terminal. The signal measurements made by the wireless terminal are applied by the illustrative embodiment to the Majority and Stability Rules previously described, with the exception that a majority of transmitting signal devices, rather than a majority of receivers, is considered in the heuristic.  
         [0010]     An illustrative embodiment of the present invention comprises: acquiring signal strength measurements made at a plurality of receivers across a plurality of zones, wherein the signal strength measurements correspond to a signal transmitted from a wireless terminal; and determining the location of the wireless terminal to be within a candidate zone within the plurality of zones, wherein determining the location is based on: (i) the majority of receivers of a first m-receiver subset being located in the candidate zone, wherein the first m-receiver subset corresponds to the m strongest of the signal strength measurements; and (ii) the majority of receivers of a second m-receiver subset being located in the candidate zone, wherein the second m-receiver subset corresponds to the m strongest of the signal strength measurements after adding a value K to the m+1st strongest of the signal strength measurements; wherein m is a positive integer. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0011]      FIG. 1  depicts a schematic diagram of wireless network  100  in the prior art.  
         [0012]      FIG. 2  depicts a schematic diagram of wireless network  100  in the prior art distributed across multiple floors of a building.  
         [0013]      FIG. 3  depicts a schematic diagram of network  300  comprising the components of the illustrative embodiment of the present invention.  
         [0014]      FIG. 4  depicts a block diagram of the salient components of signal monitor  302 -i in accordance with the illustrative embodiment of the present invention.  
         [0015]      FIG. 5  depicts a block diagram of the salient components of location estimation server  303  in accordance with the illustrative embodiment of the present invention.  
         [0016]      FIG. 6  depicts a schematic diagram of wireless network  600  distributed across multiple floors of a building, in accordance with the illustrative embodiment of the present invention.  
         [0017]      FIG. 7  depicts a flowchart of the salient tasks performed by the illustrative embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0018]      FIG. 3  depicts a schematic diagram of network  300  comprising the components of the illustrative embodiment of the present invention. Network  300  operates in accordance with a set of air interface protocols (e.g., IEEE 802.11, etc.) and comprises wireless terminal  301 ; signal monitors  302 - 1  through  302 -N, wherein N is a positive integer; and location estimation server  303 , interconnected as shown.  
         [0019]     Wireless terminal  301  is capable of transmitting packets of data over a wireless medium in well-known fashion. The packets of data can comprise information that identifies wireless terminal  301 . Wireless terminal  301  can be a communications station, a locating device, a handheld computer, a laptop with wireless capability, a telephone, etc. It will be clear to those skilled in the art how to make and use wireless terminal  301 .  
         [0020]     In some embodiments, wireless terminal  301  exchanges packets with an access point (not shown). In some other embodiments, wireless terminal  301  transmits packets specifically for the purpose of determining the location of wireless terminal  301 . In some other embodiments still, wireless terminal  301  is capable of performing signal measurements and transmitting those measurements in well-known fashion.  
         [0021]     Signal monitor  302 -i, for i=1 through N, measures (i.e., “sniffs”) signals transmitted by wireless terminal  301  over the wireless medium. Such signals include packets of data transmitted to the access point, packets transmitted specifically for measurement purposes, etc. Signal monitor  302 -i determines the received signal strength (RSS) of those signals. Signal monitor  302 -i sends the signal strength measurements to location estimation server  303 . In some embodiments, signal monitor  302 -i receives the identifying information transmitted by wireless terminal  301  and sends it to location estimation server  303 . In some embodiments, signal monitor  302 -i sends its location (e.g., actual coordinates, identifier, etc.) to location estimation server  303 . The salient details of signal monitor  302 -i, also referred to as a type of “signal device,” are described below and with respect to  FIG. 4 .  
         [0022]      FIG. 3  depicts a wired interface between signal monitors  302 - 1  through  302 -N and location estimation server  303 . Signal monitors  302 - 1  through  302 -N, however, can communicate with location estimation server  303  via a wired interface, the wireless medium, or both in well-known fashion.  
         [0023]     Location estimation server  303  acquires the received signal strength measurements from signal monitors  302 - 1  through  302 -N. Location estimation server  303  processes the received signal strength measurements corresponding to wireless terminal  301  in accordance with the illustrative embodiment of the present invention. The salient details of location estimation server  303  are described below and with respect to  FIG. 5 .  
         [0024]      FIG. 4  depicts a block diagram of the salient components of signal monitor  302 -i in accordance with the illustrative embodiment of the present invention. Signal monitor  302 -i comprises receiver  401 , processor  402 , and memory  403 , interconnected as shown.  
         [0025]     Receiver  401  is a circuit that is capable of receiving packets from the wireless medium, in well-known fashion, and of forwarding them to processor  402 . It will be clear to those skilled in the art how to make and use receiver  401 .  
         [0026]     Processor  402  is a general-purpose processor that is capable of performing the tasks described below and with respect to  FIGS. 6 and 7 . It will be clear to those skilled in the art, after reading this specification, how to make and use processor  402 .  
         [0027]     Memory  403  is capable of storing programs and data used by processor  402 . It will be clear to those skilled in the art how to make and use memory  403 .  
         [0028]      FIG. 5  depicts a block diagram of the salient components of location estimation server  303  in accordance with the illustrative embodiment of the present invention. Location estimation server  303  comprises network interface  501 , processor  502 , and memory  503 , interconnected as shown.  
         [0029]     Network interface  501  is a circuit that is capable of receiving, in well-known fashion, received signal strength measurements from signal monitors  302 - 1  through  302 -N. In some embodiments, network interface  501  receives information from signal monitors  302 - 1  through  302 -N with which the location of the signal monitor can be determined. Network interface  501  is also capable of forwarding the information received to processor  502 . It will be clear to those skilled in the art, after reading this specification, how to make and use network interface  501 .  
         [0030]     In some other embodiments, network interface  501  receives signal strength measurements made by wireless terminal  301  (i.e., through an intermediate device such as an access point). In this case, the signal strength measurements are representative of signals that are transmitted by transmitting signal devices distributed across the network.  
         [0031]     Processor  502  is a general-purpose processor that is capable of performing the tasks described below and with respect to  FIGS. 6 and 7 . It will be clear to those skilled in the art, after reading this specification, how to make and use processor  502 .  
         [0032]     Memory  503  is capable of storing programs and data used by processor  502 . It will be clear to those skilled in the art how to make and use memory  503 .  
         [0033]      FIG. 6  depicts an example of the illustrative embodiment of the present invention. In wireless network  600 , signal devices  602 - 1  through  602 - 15  are distributed across a multi-story office building. In the example, signal devices  602 - 1  through  602 - 3  are on the lowest floor depicted, while signal devices  602 - 13  through  602 - 15  are on the highest floor depicted.  
         [0034]     Signal devices  602 - 1  through  602 - 15  in the example are signal monitors that are capable of receiving signals and making signal measurements.  
         [0035]     It will be clear to those skilled in the art, after reading this specification, how to make and use embodiments of the present invention with a different number of signal devices on a different number of floors and with multiple wireless terminals present.  
         [0036]     Each floor is considered to be a “zone” within a larger space (i.e., the building). It will be clear, however, to those skilled in the art, after reading this specification, how to make and use embodiments of the present invention that applies the concept of zones to signify something other than the floors of a building.  
         [0037]     Wireless terminal  601  transmits packets of data in well-known fashion. One or more of signal devices  602 - 1  through  602 - 15  detect the signal corresponding to the packets of data transmitted by wireless terminal  601 . In the example depicted in  FIG. 6 , signal devices  602 - 3 ,  602 - 4 ,  602 - 5 ,  602 - 6 ,  602 - 7 ,  602 - 8 ,  602 - 9 ,  602 - 11 , and  602 - 12  are receiving and measuring the signal transmitted by wireless terminal  601 . Note that the signal paths of the signal that is transmitted by wireless terminal  601  traverse a plurality of zones (i.e., floors).  
         [0038]     In some other embodiments of the present invention, signal devices  602 - 1  through  602 - 15  transmit signals. At least some of the signals are received by wireless terminal  601 . Wireless terminal  601  makes signal measurements on the received signals and transmits the signal measurements, in well-known fashion, to location estimation server  603  (e.g., through an intermediary access point, etc.).  
         [0039]     Location estimation server  603  acquires the signal strength measurements made by one or more of signal devices  602 - 1  through  602 - 15  in accordance with the illustrative embodiment of the present invention.  
         [0040]      FIG. 7  depicts a flowchart of the salient tasks performed by the illustrative embodiment, continuing with the example depicted in  FIG. 6 . It will be clear to those skilled in the art which tasks depicted in  FIG. 7  can be performed simultaneously or in a different order than that depicted.  
         [0041]     At task  701 , each of signal devices  602 - 1  through  602 - 15  makes a signal strength measurement of a signal transmitted by wireless terminal  601 . Location estimation server  603  acquires the signal strength measurements obtained by some or all of signal devices  602 - 1  through  602 - 15 .  
         [0042]     At task  702 , the quantity m is initialized to 1. The quantity m is significant in that the illustrative embodiment finds the minimum value for m such that a Majority Rule holds and a Stability Rule holds. These rules are described below in detail.  
         [0043]     At task  703 , location estimation server  603  determines the m strongest-ranked signals of the received signal strength measurements (as opposed to signal strength measurements adjusted by a value K that is described below).  
         [0044]     At task  704 , location estimation server  603  determines whether or not the majority of the receivers that correspond to the m strongest-ranked signals of the received signal strength measurements are located on a particular floor (i.e., a candidate zone) within the building. This is referred to in the illustrative embodiment as the “Majority Rule.” If so, control proceeds to task  706 . If not, control proceeds to task  705 .  
         [0045]     At task  705 , the quantity m is incremented by one. Control then proceeds to task  703 .  
         [0046]     At task  706 , location estimation server  603  adds a value K to the m+1st strongest of the received signal strength measurements. In some embodiments, the value K is between 4 dB and 6 dB, inclusive. In other embodiments, the value K is dependent on the value of m. It will be clear to those skilled in the art, after reading this specification, how to assign a value for K.  
         [0047]     At task  707 , location estimation server  603  determines the m strongest-ranked signals of the signal strength measurements that now include the measurement that has been adjusted by the value K. Note that the action performed at task  706  might have affected the makeup of the m strongest-ranked signals.  
         [0048]     At task  708 , location estimation server  603  determines whether or not the majority of the receivers that correspond to the m strongest signals that have been re-ranked at task  707  are still located on the same floor as before (i.e., the candidate zone) within the building. This is referred to in the illustrative embodiment as the “Stability Rule.” If so, control proceeds to task  709 . If not, control proceeds to task  705 .  
         [0049]     At task  709 , location estimation server  603  identifies wireless terminal  601  as being on the particular floor (i.e., the candidate zone) determined by applying the Majority Rule and Stability Rule.  
         [0050]     The tasks depicted in  FIG. 7  use a plurality of signal monitors and a location estimation server to determine the floor in which a wireless terminal is located. It will be clear, however, to those skilled in the art, after reading this specification, how to make and use embodiments of the present invention with other devices, such as access points to make measurements and a general-purpose server to apply the Majority Rule and Stability Rule to those measurements.  
         [0051]     It is to be understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. For example, in this Specification, numerous specific details are provided in order provide a thorough description and understanding of the illustrative embodiments of the present invention. Those skilled in the art will recognize, however, that the invention can be practiced without one or more of those details, or with other methods, materials, components, etc.  
         [0052]     Furthermore, in some instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the illustrative embodiments. It is understood that the various embodiments shown in the Figures are illustrative, and are not necessarily drawn to scale. Reference throughout the specification to “one embodiment” or “an embodiment” or “some embodiments” means that a particular feature, structure, material, or characteristic described in connection with the embodiment(s) is included in at least one embodiment of the present invention, but not necessarily all embodiments. Consequently, the appearances of the phrase “in one embodiment,” “in an embodiment,” or “in some embodiments” in various places throughout the Specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, materials, or characteristics can be combined in any suitable manner in one or more embodiments. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.