Location system

[0001] The present invention claims priority to U.S. Provisional Patent Application, Ser. No. 60/512,897, filed Oct. 20, 2003, entitled Location System, the content of which is herein incorporated by reference.

[0002] The present invention relates to determining a location of one or more objects.

[0003] It is useful to know the location of people or objects for several reasons. The location in-and-of itself is important because it allows another party to find something that is lost, such as a child or a piece of expensive equipment. Location can also be valuable as a piece of data used in conjunction with other information. For example, knowledge about the location of a portable laptop computer combined with knowledge about the location of all the printers in a building allows a system to automatically route a print job from the laptop to the nearest printer, thus saving time and aggravation. The knowledge of who is in a particular room allows a system to adjust the temperature or lighting of that room to the individual's preferences or route that person's telephone calls to the phone in that room. These applications are presented here as examples illustrating the utility of a system that allows the location of a person or object to be known.

[0004] Existing systems are generally based on one of two principles. In the first method they measure the amount of time it takes a signal to travel from point A to point B then calculate the distance between the two points. Given three different distance calculations, a precise location can be determined. These types of systems typically require very precise timing. For example, since d=rt and r=3×10⁸ meters/second, in order to locate something to within 1 meter, there is a requirement for 3.3×10⁻⁹ (3 nanoseconds) of temporal accuracy for each distance calculation. This means that the timing between the remote transmitter to be located and each of three receivers, as well as the timing between all of the receivers, must be known within 3 nSec. Various techniques have been used with varying degrees of success to overcome this timing requirement but all require fairly complex systems. Some use a centralized time base and remote receiving antennas that must be connected with special coaxial cables. Others use calibration transmitters whose location is precisely known to help compensate for timing jitter. All of these solutions require complex, expensive infrastructure.

[0005] In the second technique, existing systems attempt to calculate the distance between a transmitter and receiver based on a received signal strength indication (RSSI). While this is conceptually simpler then estimating location based on time-of-arrival (TOA) it is plagued by the issue of multipath, especially in indoor spaces. The RSSI is a function of distance and a path-loss factor: RSSI=1/d^−f, where d is distance and f is the factor. However, the same radio wave travels over many paths between the transmitter and receiver. Some times these multiple waves arrive at the receiver in-phase (constructively) and some times they arrive out-of-phase (destructively). This means that the RSSI can be 3 dB higher than the actual value or as much as 30 dB lower than the true value.

[0006] This multipath fading makes it extremely difficult to determine the RSSI value accurately. The second challenge is determining the path-loss factor, f. Various techniques have been suggested to both compensate for multipath as well as the calculation of f. These typically involve calibration signals, averages of RSSI over time or diversity receiver systems. The trade-off is that these techniques, while typically simpler than the TOA calibration, lead to accuracies that are not as good as TOA based systems. It should also be noted here that “simple” is a relative term and even RSSI based systems must be quite complex in order to have acceptable accuracy.

[0007] In summary, existing solutions attempt to accurately locate the distance a transmitter is from a receiver. The accuracy of the determination of the location of a transmitter is driven by how accurately the distances can be calculated (d₃, d₂ and d₃) between the transmitter and the various receivers (R₁, R₂ and R₃).

[0008] Therefore, there is a need for a location system that can accurately and simply locate a transmitter. Ideally, this system does not require precisely calculating the distances between the receivers and transmitter. The present invention allows the location of transmitter to be determined (approximated) without requiring its distance from a receiver to be precisely known. This means that the overall system can be much simpler and hence less expensive.

[0009] The present invention provides a location system which allows location to be determined without requiring precise calculations of distance and allows differing degrees of precision to be provided in the same system.

[0010] In accordance with a first aspect, a method for determining location of an object comprises the steps of: for a receiver, estimating a first zone within which a first transmitter is located; for remaining receivers that can detect a given transmitter, each estimating a second zone within which a first transmitter is located; and determining if there are overlaps in any of the zones.

[0011] In accordance with another aspect, a method for determining location of an object comprises the steps of: determining a potential target area, and estimating a target location within the potential target area. In certain embodiments, the step of determining a potential target area comprises the steps of: identifying receivers that received a signal from a transmitter, generating one or more line segments connecting the identified receivers, determining zones around identified receivers, generating lines through intersections of zones and the one ore more lines; and designating the area defined by secants as the potential target area. In some embodiments the step of generating lines comprises generating secants through the intersections between the line segments and the zones for each zone. In other embodiments, the step of generating lines comprises generating tangents at the intersections between the line segments and the zones for each zone. The step of estimating a target location within the potential target area may comprise finding the center of the potential target area.

[0012] In accordance with another aspect, a method for determining location of an object comprises the steps of: identifying receivers that received a signal from a transmitter, generating one or more lines segments connecting the identified receivers, determining zones around the identified receivers, generating lines through intersections of zones and the one ore more line segments, designating the area defined by the lines as the potential target area; and determining center of potential target area.

[0013] In accordance with another aspect, in a computing device, a method for determining location of an object, comprises the steps of for a receiver, estimating a first zone a first transmitter is in; for remaining receivers that can receive a given transmitter, each estimating a second zone a first transmitter is in; and determining if there are overlaps in any of the zones.

[0014] In accordance with another aspect, in a computing device, a method for determining location of an object, comprises the steps of: identifying receivers that received a signal from a transmitter, generating one or more line segments connecting the identified receivers, determining zones around the identified receivers, generating lines through intersections of zones and the one ore more line segments, designating the area defined by lines as the potential target area; and determining the center of the potential target area.

[0015] In accordance with another aspect, in a location system comprising at least one transmitter and at least two receivers, a method comprises: determining which receivers can receive a signal from the transmitter, estimating the zones of the receivers the transmitter is in, determining if there are overlaps in any of the zones.

[0016] In accordance with another aspect, a computer program product holds instructions executable in a computer for determining location of an object. The instructions comprise the steps of for a receiver, estimating a first zone within which a first transmitter is located; for remaining receivers that can receive a given transmitter, each estimating a second zone within which a first transmitter is located; and determining if there are overlaps in any of the zones.

[0017] In accordance with another aspect, a computer program product holds instructions executable in a computer for determining location of an object. The instructions comprise the steps of identifying receivers that received a signal from a transmitter, generating one or more line segments connecting the identified receivers, determining zones around the identified receivers, generating lines through intersections of zones and the one ore more line segments, designating the area defined by lines as the potential target area, and determining the center of the potential target area.

[0018] In accordance with another aspect, a location system for determining location of an object comprises a location determination module for determining a potential target area encompassing the object and estimating the location of the object within the potential target area.

[0036] Various embodiments of the present invention provide apparatus and methods for the determination of location information. Various embodiments of the invention allow for location information to communicated over a network or over the Internet. Various embodiments of the invention may be configured to minimize installation efforts by the use of various techniques such as using wireless components to provide location information to fixed locations and by an ability in some embodiments of the invention to utilize existing wiring, already in place in many environments.

[0037] A location system 10 is provided by way of example in FIG. 1A. The illustrated location system 10 includes an object identifier 800 and a location determining module 14. The object identifier 800 may be coupled to an object such that a location of that object corresponds to the location of the object identifier 800. The object identifier 800 may be any device capable of identifying a location of an object. According to an embodiment of the invention, an example includes an electronic device. Examples of electronic devices may be in many forms and include, by way of example, a processor, a computer, a personal digital assistant, a communications device, such as a cell phone, a network appliance, a web server, a network, any device capable of manipulating information, a receiver, a transmitter, an interface or any combination of these devices. A network may be a local area network (LAN), a wide area network (WAN), the Internet, an intranet, or a metropolitan network. The network may be a wireless network such as a Bluetooth network, a cellular network, a GSM based network, a hard-wired network, or some other type of network.

[0038] According to various embodiments of the invention, the object identifier 10 transmits two identifiers, one identifier corresponding to the object identifier 10 and a second identifier which is a group designator. While the identifiers may be in many forms, some examples, according to various embodiments of the invention, include numbers, letters, URLs, MAC addresses and IP addresses.

[0039] According to an embodiment of the invention, the location determining module 14 may include any structure suitable for determining location. Examples include any device with intelligence to determine the location of one or more object identifiers. According to various embodiments of the invention, the location determining module 14 may include one or more of each of the following, including combinations of the following: a network connection element, an object identifier, a fixed location identifier, a location resolver, a database, topology data, an electronic device, a web interface, a network interface, a specialized network interface, an implementation interface, a database interface, a network and/or a specialized network, a receiver and/or a transmitter. According to various embodiments of the invention, the location determining module 14 may have only a receiver, only a transmitter or both a receiver and a transmitter. It will be apparent to one of ordinary skill in the art that one or more components may be distributed in a wide variety of configurations.

[0040] According to various embodiments of the invention, the present invention may be used to determine a location of a location determining module. In such an embodiment, the location determining module may be a mobile module, capable of determining its own location relative to one or more object identifiers. In such an embodiment, the object identifiers may be fixed. Optionally, the object identifiers may be moving. One example of the use of a mobile location determining module involves a location system configured to determine locations within a large area. If such a large area is populated by a small number of objects, the components of such a location system may be more efficiently configured by providing functionality of a location determining module with each object. In such a case, object identifiers could be distributed throughout the large area. The location determining module could then be adapted to receive location signals from the object identifiers and thereby determine a location of the location determining module. In this embodiment, the location of the objects is determined relative to the location of the one or more object identifiers, although the locations of the object identifiers may be known, allowing locations of objects to be determined relative to other references or by name, such as a location on a map or a specific room.

[0041] The configuration above is contrasted with another embodiment of the invention, better suited to environments with a greater number of objects in a smaller area. In such an embodiment, each object may be provided with an object identifier. One or more location determining modules may then be located within the area to receive location signals transmitted by the object identifiers. In this embodiment, the location of the objects is determined by determining the location of the object identifiers.

[0042] According to various embodiments of the invention, the location determining module 14 may be capable of performing additional functionality, such as receiving requests for information, providing information, storing information, commanding actions in response to location information, associating objects with other objects or with locations, establishing privacy conditions regarding availability of location information, interfacing directly with various network types, and the like. According to further embodiments of the invention, the location determining module 14 includes multiple, distributed receivers, some of which may be connected to a network, and others not connected to a network. According to various embodiments of the invention, the object identifier 10 and location determining module 14 utilize both RF signals and IR signals for the determination of location.

[0043] According to an embodiment of the invention, the location determining module 14 may include one or more databases. The databases may store information relating to current location of object identifiers, fixed location identifiers and network connection elements.

[0044] According to various embodiments of the invention, the invention may be used only within an enclosed structure. Enclosed structures include buildings, such as office buildings, exhibition halls, health care institutions, homes or other structures. According to other embodiments, the invention may be used outside of enclosed structures or may be used both within and outside enclosed structures.

[0045] According to an embodiment of the invention, a location system 100 is provided. As illustrated by way of example in FIG. 1B, the location system 100 is provided with a transmitter 200 and a receiver 300. Optionally, additional transmitters 200 (shown in phantom) may be provided. The transmitter 200, for example, can form part of the object identifier 800, and the receiver 300, for example, can form part of the location determining module 14. A transmitter 200 communicates with the receiver 300 in order to provide a signal for receipt by the receiver 300. According to one embodiment of the invention, the transmitter 200 transmits a signal using only a radio frequency (RF) transmitter 210. In such an embodiment, the receiver 300 is provided with an RF receiver 310. According to a further embodiment of the invention, the transmitter 200 may be provided only with an infra red (IR) transmitter 220 to transmit an IR signal. In such an embodiment the receiver 300 is provided with an IR receiver 320. According to a further embodiment of the invention the transmitter 200 is provided with both an RF transmitter 210 and an IR transmitter 220 while the receiver 300 is correspondingly provided with both an RF receiver 310 and an IR receiver 320. According to this embodiment, both the RF signal and the IR signal are used for the determination of the location of the transmitter 200. According to one practice, the RF signal can include information unique to the object identifier or the object to which it is attached. The IR signal can be non-unique and not include any specific information.

[0046] According to a further embodiment of the invention, the receiver 300 may be provided with a network interface 330. An example of the network interface 330 includes an interface for a local area network (LAN) or another interface to allow direct coupling of the receiver 300 to a network 400. According to one embodiment of the invention the network interface 330 is comprised of an interface capable of direct coupling of the receiver to a UTP-based, Ethernet network interface. The Ethernet network may be a wired or wireless network or a combination thereof.

[0047] According to another embodiment of the invention the receiver 300 is provided with a web server 340. The web server 340 may be configured to provide location information directly to the network 400 and/or the Internet 500. The web server 340 may also be configured to allow for control or configuration of the receiver 300 through the network 400 and/or the Internet 500.

[0048] According to one practice, the receiver 300 can be configured to convey signals to the network 400 in a periodic or intermittent manner. By way of example, the receiver 300 can convey information in any appropriate format, such as a data packet, to the network 300 every selected time period. The time period can preferably be between 1 second and 10 minutes, more preferably between 5 seconds and 1 minute, and most preferably every 10 seconds. The signals generated by the receiver are independent of receipt of signals from an object identifier. That is, the generation of signals by the receiver is periodic and not in response to receipt of a signal by the receiver.

[0049] As shown by way of example, a location determining module 14, according to an embodiment of the invention, is illustrated, by way of example, as including the network 400.

[0050] A further embodiment of the invention is illustrated in FIG. 2. A location system 700 is illustrated by way of example having an object identifier 800 in communication with a network connection element 900. According to an embodiment of the invention, the object identifier 800 is physically coupled to an object so that the location of the object identifier 800 is considered to be the location of the object. According to another embodiment of the invention, the location of the object may be determined by locating one or more object identifiers 800 in an area and coupling a network connection element 900 to an object. In such an embodiment, the location of the network connection element 900, and hence the object, is determined relative to the one or more object identifiers 800. The network connection element 900 is configured to be coupled to a network 400. According to an optional embodiment of the invention, the network may be a wireless network. As illustrated in FIG. 2, one or more object identifiers 800 communicate to the network connection element 900. According to another embodiment of the invention, the network connection element 900 may communicate back to the object identifier 800.

[0051] According to a further embodiment of the invention a fixed location identifier 1000 is provided. The fixed location identifier 1000 is configured to receive signals from one or more object identifiers 800 and retransmit that information. The retransmitted information may be received by the network connection element 900. According to one embodiment of the invention the retransmitted information includes the information provided by the object identifier 800, coupled with additional information to identify the fixed location identifier 1000 that is re-transmitting the information. According to an embodiment of the invention, plurality of network connection elements 900, fixed location identifiers 1000 and object identifiers 800 may be provided in the location system 700. In such a case, the network 400 may provide communication among the network connection elements 900 in order to determine the location of one or more object identifiers 800 by one or more network connection elements 900 or by the use of other devices coupled to the network 400.

[0052] As shown by way of example, a location determining module 14, according to an embodiment of the invention, is illustrated, by way of example, as including the network connection element 900, the fixed location identifier 1000 and the network 400.

[0053] According to an embodiment of the invention, the object identifier 800 and/or fixed location identifier 1000 transmits various information. According to an embodiment of the invention, this information is transmitted over both RF and IR signals. Optionally, the information may be transmitted over only one signal. According to an embodiment of the invention, examples of the information transmitted may include one or all of the following: RF power level; IR power level; battery level; input device status; transmission frequency, e.g. repetition rate, for any or all types of transmissions, such as IR and/or RF; an identifier corresponding to the transmitting device; an identifier corresponding to a group to which the transmitting device is associated; any information received from another system component; status or condition information; or the like. According to an embodiment of the invention, some information may be repeated over multiple signal transmissions. Examples include transmitting input device status over ten transmissions to increase the likelihood of receipt by other components of the location system.

[0054] The object identifier 800 according to an embodiment of the invention is illustrated by way of example in FIG. 3. The object identifier 800 is provided with a controller 810 and controller support 820. The controller support 820 may include various items such as a power supply, such as a battery or other apparatus to provide electrical power, memory and/or various time keeping circuitry such as an oscillator. Controller support 820 may optionally include non-volatile memory. Various components of the controller support 820 may optionally be incorporated into the controller 810 or may be provided from an external source, outside the object identifier 800.

[0055] According to an embodiment of the invention, the object identifier 800 may be provided with an RF transmitter 830. According to a further embodiment of the invention the object identifier 800 may be provided with an IR transmitter 840. According to an further embodiment of the invention the object identifier 800 is provided with both an RF transmitter 830 and an IR transmitter 840.

[0056] According to another embodiment of the invention, the object identifier 800 is provided with an RF receiver 850. According to another embodiment of the invention the object identifier may be provided with an IR receiver 860.

[0057] The object identifier 800 may also be provided with an input device 870. Examples of input devices include buttons, switches, keypads, ports for electrical or optical communication with other devices, sensors, such as photo cells cameras or microphones. Other types of input devices 870 may be apparent to one of ordinary skill in the art upon reading this disclosure and are to be considered within the scope of the invention. One or more input devices 870 are configured to provide input to the controller 810 in order to allow the controller 810 to take an action, not take an action, or to forward information outside the object identifier 800 by way of an RF transmitter 830 and/or an IR transmitter 840.

[0058] According to a further embodiment of the invention an indicator 880 may be provided to enable the controller 810 to output information in the proximity of the object identifier 800. Examples of indicators 880 include visual, audio and vibrational devices. Examples of these include buzzers, bells, horns, LEDs, other forms of lights and/or displays. The indicator 880 may be configured to display or output information determined by the controller 810 or received by the controller 810 through the input device 870, RF receiver 850 and/or the IR receiver 860.

[0059] An object identifier 800 is illustrated by way of example according an embodiment of the invention, in FIG. 4. The object identifier 800 is illustrated with two indicators 880 in the form of two LEDs. Three input devices 870 are also illustrated in the form of switches. Two switches are illustrated so as to correspond to the two indicators 880, while the third switch 870 is illustrated on an opposing surface of the object identifier 800. According to this illustrative embodiment, the input device 870 on the lower surface of the object identifier 800 is normally pushed in when the object identifier 800 is attached to an object. Upon removal from the object, the input device 870 extends, resulting in a change of position of the input device 870. This embodiment allows the controller 810 to be alerted when the object identifier 800 is removed from an object. Each of the indicators 880 may be configured to illuminate upon the activation of the corresponding switches, input devices 870, so as to allow visual confirmation of the activation of one of the switches. Various uses of these switches will become apparent to one of ordinary skill in the art. Several examples, by way of illustration, include panic alerts, causing the processor 810 to emit a specialized signal through at least one of the RF transmitter 830 and the IR transmitter 840. A further example may involve an ability to configure a portion of the location system 700 remotely by the activation of the input devices 870.

[0060] FIGS. 5A, 5B and 5C illustrate, according to various embodiments of the invention, various examples of a transmission of signals from the object identifier 800. A first method 802 is illustrated in FIG. 5A according to an embodiment of the invention. An RF power level is set to PN, step 804. An IR signal is transmitted, step 806. The delay of m seconds then occurs, step 808. An RF signal is transmitted, step 812. A further delay of x seconds occurs, step 814. Pn is then incremented, step 816. This method 802 provides a substantially consistent IR power level, while varying an RF power level. Varying the RF power level may assist in determining a location of the object identifier 800 by enabling the network connection element 900, location determining module 14, or receiver 300, to receive less than all of the RF signals. According to an embodiment of the invention, one or both of the IR and RF signals are also transmitting information. Examples of this information may include the signal strength being transmitted, the period between transmissions, the length of time of the transmissions, various identifiers, corresponding to the object identifier 800, information received from one or more input devices 870 and/or various status information, such as those pertaining to the controller 810 controller sport 820 or other components of the object identifier 800. According to one embodiment of the invention the RF signal is transmitted every ten seconds and the IR signal is transmitted every twenty seconds.

[0061] Determination of the frequency and length of the transmissions involves considerations including battery life precision of location, frequency of updates to location, interference among signal transmissions and network traffic.

[0062] A further method 822 of an embodiment of the invention is illustrated in FIG. 5B. According to this embodiment, an RF signal is transmitted, step 824 and a delay, step 826 occurs before the next transmission of an RF signal, step 824. Independently of the RF transmission, an IR signal is transmitted, step 828. The IR transmission, step 828 may occur simultaneously with the transmission of the RF signal, step 824 but this embodiment of the invention is not so limited. The transmission of the RF signal, step 828 may occur at any time relative to the transmission of the RF signal step 824. A delay of c seconds step 832, occurs before the next transmission of the RF signal, 828.

[0063] According to a further embodiment of the invention, a further method 842 is illustrated by way of example in FIG. 5C. According to this embodiment, an RF signal is transmitted, step 844 and an IR signal is transmitted, step 846. According to an alternative embodiment, a transmission in another medium may also occur, step 848. Examples of other mediums include ultra-sonic (US), visual light, or audible sound. According to the method 842 of FIG. 5C, transmissions may be continuous, variable or occur at regular intervals. The transmissions among various mediums may be synchronized or random relative to transmissions in other mediums.

[0064] An example of a network connection element 900 according to an embodiment of the invention is illustrated in FIG. 6. A network connection element 900 includes many component similar to those of the object identifier 800 illustrated by way of example in FIG. 3. A network connection element 900 is provided with a controller 910 and a controller support 920. Controller support 920 may optionally include non-volatile memory. Optionally, various embodiments of the invention may include one or more of the following in the network connection element 900: an RF receiver 930, an IR receiver 940, an RF transmitter 950, an IR transmitter 960, an input device 970 and/or an indicator 980.

[0065] The network connection element 900 is adapted to receive signals from the object identifier 800. According to an embodiment of the invention, the network connection element 900 contains hardware and software capable of receiving signals from other components of the location system, such as object identifiers 900, other network connection elements 900. According to an embodiment of the invention, the network connection element 900 may have network connectivity software, a local web server, object identifier analysis software, software to transmit the results of an object identifier analysis to a remote server, DHCP software and local permanent storage. According to an embodiment of the invention, the network connection element 900 may also include configuration, service and debug applets to be used in the maintenance and configuration of the object identifier 900.

[0066] The network connection element 900, according to an embodiment of the invention, may further be provided with a web server 990. As with the web server 340 of the receiver 300 of location system 100, web server 990 of network connection element 900 is able to provide or receive information or commands. In various embodiments of the invention, the web server 990 may allow for control and configuration of any component of the location system.

[0067] According to a further embodiment of the invention, the network connection element 900 may be provided with a network interface 992. The network interface 992, as with the network interface 330 of location system 100, is configured to couple the controller to a network 400. According to an embodiment of the invention, the network interface 992 is adapted to packetize buffered information received and send this information as a group, thereby providing more efficient network usage in some applications.

[0068] A further embodiment of the invention provides a database 996 in communication with then controller 910 of the network connection element 900. The database 996 may be provided within the network connection element 900 or may be provided on a network 400. According to alternative embodiment of the invention, the database 996 may be provided within the network connection element 900 and also in direct communication with the network 400.

[0069] According to a further embodiment of the invention, a location system 710 is illustrated by way of example in FIG. 7. According to this embodiment, a location resolver 1100 is provided for communication with the network connection element 900. In this embodiment, the location resolver 1100 communicates with one or more network connection elements 900 to obtain information pertaining to the location of one or more object identifiers 800 and one or more optional fixed location identifiers 1000. The location resolver 1100 may be provided in the form of software or hardware or a combination of both. The location resolver 1100 may communicate with one or more network connection elements 900 over a network 400.

[0070] As shown by way of example, a location determining module 14, according to an embodiment of the invention, is illustrated, by way of example, as including the network connection element 900, the location resolver 1100 and the fixed location identifier 1000. In this embodiment, the network 400 is not included in the location determining module 14, but optionally communicates with the location determining module 14.

[0071] The location resolver 1100, according to an embodiment of the invention, is further illustrated by way of example in FIG. 8. As shown in FIG. 8, a controller 1110 is provided in communication with a network interface 1120. The network interface 1120 is adapted to be coupled to the network 400. Controller support may also be optionally provided. A web server 1130 is provided in communication with a controller 1110. The web server 1130 of the location resolver 1100 is similar to the web server 990 of the network connection element 900, discussed herein.

[0072] According to an embodiment of the invention, the location resolver 1100 may be provided with a configuration capability to configure other components of the location system. For example, an embodiment of the location resolver 1100 may perform some or all of the following functions: reset system time; reset communications; disable all or selected input devices of all or selected components, such as object identifiers, fixed location identifiers, network connection elements; establish and/or cancel associations between all or selected components; establish and/or cancel privacy settings for specific location information; configure network communication protocols; configure receiver and/or transmitter configurations, altering or eliminating signals, signal types, such as RF, IR, ultrasonic, or the like, or transmission frequencies and the frequencies at which transmissions are expected.

[0073] An implementation interface 1140 is also provided in communication with controller 1110. The implementation interface 1140 is provided to communicate with other devices in order to allow for the communication of location information and/or initiation or response to commands as described herein. Various examples of implementation interfaces 1140 include XML and SMTP protocols, other examples may be apparent to those of ordinary skill in the art.

[0074] A database 1150 is also provided either within the location resolver 1100 or external the location resolver 1100. The database 1150 is adapted to store information relating to the location of one or more object identifiers 800 and/or optional fixed location identifiers 1000 and/or network connection elements 900. According to various embodiments of the invention, the database 1150 may store current and/or previous location and status information of location system components, associations of location system components with each other or locations, privacy protocols and status, topology data indicating locations of some or all location system components relative to each other, or in other descriptive terms, such as room or location names or by a coordinate system.

[0075] A database interface 1155 may be provided in another embodiment of the invention in order to facilitate interaction between the database 1150 and the controller 1110. The database interface 1155 may be a network or other hardware or software to controller 1110 to enable the controller 1110 to access the database 1150. Various examples of database interfaces 1155 include JDBC and ODBC, other examples may be apparent to those of ordinary skill in the art.

[0076] A method 1102 of operation of the location resolver 1100, according to an embodiment of the invention is illustrated in FIG. 9. The location resolver 1100 initially waits for input from a receiver, such as the network connection element 900, step 1104. The location resolver 1100 then determines whether an IR signal was received, step 1106. If an IR signal was received, data received from the transmitter and receivers location is made available, step 1108. If an IR signal is not received the location resolver 1100 checks to see if an RF signal was received, step 1112. Location resolver 1100 also checks to see if an RF signal was received after making any data available from the reception of an IR signal available, step 1108. If an RF signal was not received, the location resolver 1100 according to an embodiment of the invention returns again to wait for further input from the network connection element 900. If an RF signal was received, the location resolver 1100 determines whether the RF power was high, step 1114. If so, data received from the transmitter is made available with message indicating that the object identifier is within a large radius of the network connection element 900, step 1116. If the RF signal power was not high the location resolver 1100 determines whether the RF power was medium, step 118. If so, data received from the object identifier is made available with a message that the object identifier is within a smaller radius of the network connection element 900, step 1122. If the RF signal power was not medium the location resolver 1100 determines whether the RF signal power was low, step 1124. If so data from the object identifier 800 is made available with an indication that the object identifier is within a smaller radius of the network connection element 900, step 1126. The location resolver 1100 then returns to await further input from one or more of the network connection elements 900, step 1104.

[0077] It is understood that the method of FIG. 9 may be accomplished by using transmitters that vary in output power or by constant power output transmitters. In using constant power output transmitters, received signal strength is categorized according to signal strength, such as by the use of a histogram. According to an embodiment of the invention, the network connection element 900 classifies signal strength within specific ranges and may pass an indication of the appropriate range to other location system components. According to another embodiment of the invention, the network connection element 900 provides a signal strength value that may be passed to other location system components, such the location resolver 1100, allowing more precise analysis of received signal strength information.

[0078] According to one embodiment of the invention, RF and IR signal strength are adjusted to a range of approximately 20 feet. Other embodiments of the invention may involve adjusting signal strength of RF and/or IR and/or other signal types, such as ultrasonic, ranges to a few inches, feet, thousands of feet, or miles. Another embodiment of the invention involves varying signal strength among various types of object identifiers.

[0079] A method of operation of the location resolver 1100 involves multilateration. Multilateration determines location by the use of determining range from a relative location. Multilateration can be performed by a single receiver, but is best accomplished by multiple receivers. An object can infer the location of another object by calculating its range from one or more beacons with known locations using some type of signal measurement. According to an embodiment of the invention RF signal strength is used to determine location. According to a further embodiment both RF and IR are used to determine location. It is understood that an absence of a signal that is expected is considered a signal for purposes of determining location. An example, for purposes of illustration, is the receipt of an RF signal but not an IR signal may indicate a transmitter out of IR range but within RF range, or just out of line-of-sight if required for lower-powered IR transmissions. The receiver may be configured to expect both RF and IR transmissions at specific intervals generally or for a specific transmitter. This is one example of the use of both RF and IR for determination of location.

[0080] In addition to current signal information, other information may be used in determining location. Previous location information may also be used in determining current location. Locations of other location system components may also be used in determining location. For example, locations of one or more network connection elements 900, one or more fixed location identifiers 1000 and other object identifiers 800 may be used in determining location of a particular location system component. According to one embodiment, establishing relative distances between additional nearby components and the component for which location information is desired assist in establishing a location with greater particularity.

[0081] According to an embodiment of the invention, transmission rates may vary among different types of object identifiers. Transmission rates may be adjusted in relation to the type of object for which location information is desired. Examples include low transmission rates for objects typically stationary, such as equipment typically found in a particular room. Whereas people, or mobile equipment may be better tracked by more frequent signal transmissions.

[0082] Another method of determining location involves at least one Bayesian network. A further method of determining location involves triangulation. An example of one or more of the foregoing methodologies are described, for example, in U.S. Pat. No. 5,774,876, which is incorporated herein by reference. Bayesian networks are also described in Castro, Paul et al. “A Probabilistic Room Location Service for Wireless Networked Environments” In: Ubicomp 2001: Ubiquitous Computing, Third International Conference, Atlanta, Ga., USA, Sep. 30–Oct. 2, 2001 Proceedings. Edited by G. D. Abowd, et al. Heidelberg, Germany: Springer-Verlag, 2001, LNCS 2201, p. 18 ff. This publication is incorporated herein by reference. Combinations of these methods or other methods of location determination may be apparent to one of ordinary skill in the art and are included within the scope of the invention.

[0083] Another technique determines a location of a transmitter without requiring the distance from the object identifier to one or more receivers to be precisely known. This means that the overall system can be much simpler and hence less expensive. This technique involves determining a potential target area and then estimating a target location within the potential target area. Two methodologies for accomplishing this are provided below. The first methodology looks for overlaps between zones of receivers to define the potential target area and is illustrated in FIGS. 10–10F. The second methodology determines a potential target area without requiring overlapping zones and is illustrated in FIGS. 10G–10K. It should be noted that the two methodologies discussed below, or any the other methods discussed in this disclosure, are not mutually exclusive. Techniques from any of these methods may be combined.

[0084] In the first methodology, an example illustration 1002 of which is shown in FIG. 10, there are two receivers, R₁ 1004 and R₂ 1006, and three transmitters T₁ 1008, T₂ 1012 and T₃ 1014. There are three rings (zones) around each receiver: Zn-m where n is the designator for the receiver and m is the designator for the zone. Although three zones are illustrated in FIG. 10, those of ordinary skill will readily recognize that any number of zones can be used. More zones lead to higher precision but more complex calculations. In the example embodiment, the zones are actually three dimensional, but can also be two dimensional.

[0085] According to the illustrated embodiment of FIG. 10A, the steps to locate a transmitter are set forth. First, for a given receiver, the system estimates the zone where a given transmitter is located 1016. This may be accomplished according to any suitable technique, including, but limited to RSSI, TOA. The system continues to estimate zones until all the receivers that can receive a signal from a given transmitter have their zones determined. This yields a vector (Zn-m)₁, (Zn-m)₂, (Zn-m)₃ . . . (Zn-m)_P where P is the number of receivers that can hear a given transmitter 1018. The system then determines or calculates if there are overlaps in any of the determined zones 1022.

[0086] So, in the above example, T₃ can be located quite precisely because it is located in the potential target area defined by the overlapping region of zones Z_1-2 and Z_2-1, which is relatively small. Transmitter T₁ can also be located quite precisely because it is in the potential target area defined by the overlap of zones Z_1-1 and Z_2-1, which also have a small overlapping area. The system meanwhile locates transmitter T₂ somewhere within zone Z_2-1.

[0087] Note that the above example is a fairly simple case. A more general example is described below. Assume that there are N spheres and that the position (x, y, z), outer radius (R) and wall thickness (t) are known. The goal of the calculation is to find the area of intersection between each sphere. Then, the total area of intersection between all of the spheres can be obtained by adding the intersection areas for the individual spheres.

[0088] The approach in this example is to determine if spheres are intersecting by calculating the distance between the centers of the spheres and comparing that distance to the radius of the spheres. For any two spheres (j and k), the distance equation is:
d_jk=√{square root over ((x_j−x_k)²+(y_j−y_k)²+(z_j−z_k)²)}{square root over ((x_j−x_k)²+(y_j−y_k)²+(z_j−z_k)²)}{square root over ((x_j−x_k)²+(y_j−y_k)²+(z_j−z_k)²)}

[0089] The two spheres are interacting only if d_jk≦(R_j+R_k). Similarly, three spheres (j, k, m) are mutually intersecting if d_jk≦(R_j+R_k), d_jm≦(R_j+R_m), and d_km≦(R_k+R_m). This can be continued for four (or more) spheres, but it is unlikely that more than four spheres mutually intersect, unless the size range is very large and a sphere can be enveloped by another sphere. For convenience, each of these types of mutual interactions can be classified separately, as:

• • [0090] Case 0: no interaction
  • [0091] Case 1: interaction between two spheres
  • [0092] Case 2: mutual interaction between three spheres
  • [0093] Case 3: mutual interaction between four spheres.

[0094] Case 0 is trivial since the area is zero. A solution for the intersection area for case 1 is below. Cases 2 and 3 become more complicated, particularly when the radii of the spheres are different. Until those cases are solved, a good first approximation is to assume that the correction for the mutual interaction between more than two spheres is negligible. This is a good assumption if d_jk is only slightly less than (R_j+R_k).

[0095] For Case 1, consider the geometry of 10B. The intersection area 1024 is taken at the interface between the two spheres 1024 and 1026, and is in a plane perpendicular to the line 1028 connecting the centers of the spheres. This area A 1024 has a circular shape of radius a and can be calculated from the geometry as

[0096] $A=\frac{\pi }{4d_{\mathrm{jk}}^2}\left[4R_j^2{R}_k^2-{\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2\right]$

[0097] This equation even applies for larger interactions, as shown in FIG. 10C, where both walls are effectively penetrated but the center of either sphere has not yet reached the plane of the interface area. FIG. 10D shows the center region of the smaller sphere reaching the plane of the intersection area, while FIG. 10E shows the center region of a larger sphere reaching the plane of the intersection area. In either case, the intersection area will be reduced by the area of the gap of the center region of the sphere that breaks the interface plane, or it will be increased because of the curved spherical surface area. Similarly, FIG. 10F shows that the common wall between the two spheres has disappeared. The interface area can include the common plane between the two spheres (dashed) but may also include the curved inner surface of the smaller sphere. Whether or not these-situations need to be considered is optional.

[0098] In the present example, for an initial treatment, only the planar area of intersection will be treated. These areas can then be expressed as:

[0099] $A=\{\begin{array}{c}\pi \left[R_k^2-{\left(R_k-t_k\right)}^2\right]R_j>R_k;\sqrt{\begin{array}{c}{R}_k^2-\frac{1}{4d_{\mathrm{jk}}^2}[4R_j^2{R}_k^2-\\ {\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2]\end{array}}<\left(R_k-t_k\right)\\ \pi \left[R_j^2-{\left(R_j-t_j\right)}^2\right]R_j>R_k;\sqrt{\begin{array}{c}{R}_j^2-\frac{1}{4d_{\mathrm{jk}}^2}[4R_j^2{R}_k^2-\\ {\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2]\end{array}}<\left(R_j-t_j\right)\end{array}$

[0100] These assume that the j sphere has a larger radius than the k sphere. The upper case applies when c≦(R_k−t_k) while the lower case applies when b≦(R_j−t_j). These equations are valid as long as the smaller sphere is outside the bigger sphere or d_jk≦R_j. However, this constraint can be relaxed slightly so that c>0.

[0101] For completeness, the expressions for a, b, and c are:

[0102] $a=\frac{1}{2d_{\mathrm{jk}}}\sqrt{4R_j^2{R}_k^2-{\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2}$ $b=\sqrt{R_j^2-a^2}=\sqrt{R_j^2-\frac{1}{4d_{\mathrm{jk}}^2}\left[4R_j^2{R}_k^2-{\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2\right]}$ $c=\sqrt{R_k^2-a^2}=\sqrt{R_k^2-\frac{1}{4d_{\mathrm{jk}}^2}\left[4R_j^2{R}_k^2-{\left(d_{\mathrm{jk}}^2-R_j^2-R_k^2\right)}^2\right]}$

[0103] As a special case, the sphere can be assumed to have an equal diameter. This provides much simpler expressions but may not be applicable.

[0104] Another method of determining (approximating) the location of a transmitter can be seen in FIG. 10G. This method 1032 comprises the steps of determining a potential target area (PTA) 1034 and then estimating a target location within the PTA 1036. This method is particularly useful in the situation mentioned above wherein there is no overlap between zones. Zones may not overlap due to interference in the transmitter signal but an approximation can still be made.

[0105] A more detailed flow chart of this method is shown in FIG. 10H. The step of determining the PTA 1034 further comprises the steps of identifying the receivers that have received a signal from a transmitter 1038, generating one or more line segments connecting the receivers 1042, determining zones around the receivers 1044, generating lines through the points where the lines intersect the zones 1046. The area contained by the lines defines the PTA. In this example, estimating the target location within the PTA 1036 is accomplished by finding the center of the PTA. On skilled in the art will recognize there are several method for finding the center of the PTA

[0106] An example where there are two receivers with zones that do not overlap can be seen in FIG. 10I. First, the two receivers 1048 are identified as receiving a signal. Then a line segment 1054 is generated between the receivers. Then the zones 1056 of the receivers are determined. Then lines (here tangents because there is only one intersection on each zone) are generated at the intersection of the line and the zones 1062. The area bounded by the tangents , in this case the line connecting the receivers, is the PTA. The center of the PTA, here found along the line connecting receivers provides a good approximation of the target location of the transmitter 1064.

[0107] An example with three receivers with non-overlapping zones is shown in FIG. 10J. First the receivers receiving a signal are identified 1058. Then line segments are generated between the receivers 1064. Then the zones 1066 are determined. Next, lines, here secants, are generated through the intersections of the line segments and the zones 1068. The area bounded by the secants defines the PTA 1072. Determining or estimating the approximate or exact center of the PTA provides a good approximation of the target location of the transmitter 1074.

[0108] This method also works when the zones overlap. An example of such a situation is shown in FIG. 10K. Here, the same method is applied and the PTA 1076 and approximation of the target location of the transmitter 1078 are found within the area of overlap as discussed above. This method may also be used when there is a combination of overlapping and not overlapping zones.

[0109] Privacy conditions may be established regarding location information for one or more location system components. Privacy may be accomplished in a variety of ways. For example, privacy may be accomplished by not making location information available or by not determining location information. Privacy may be managed by an opt-out protocol, requiring an action to establish privacy. Privacy may be managed by an opt-in protocol, requiring an action to cancel privacy. A not-opt-out protocol may also be used, preventing action from establishing privacy. Various protocols may be used in combination within a location system. Different location system components may subject to different protocols. Examples include various groups of object identifiers being subject to different protocols, such as some people able to select a privacy protocol or a privacy status, such as privacy or no privacy, while object identifiers used to locate equipment may be subject to a not-opt-out protocol. According to an embodiment of the invention, protocols or privacy status may be assigned through a batch-processing capability in a user interface. According to another embodiment, privacy status for opt-in or opt-out protocols may be accomplished by an input device incorporated in the location system component. Optionally, privacy status may be confirmed by an indicator incorporated in the location system component.

[0110] Associations associating objects with other objects or with locations may be established. Examples of the use of associations include: determining procedure times, room utilization, proximity alerts that may be used to alert a fall of a person, regulatory compliance, person & equipment associations; location & equipment associations; friend & foe associations, and automatic billing. According to an embodiment of the invention, association information may be stored in a database. Associations may be performed through a batch-processing capability in a user interface. According to another embodiment, associations may be accomplished by an input device incorporated in the location system component. Optionally, association status may be confirmed by an indicator incorporated in the location system component. One example involves activating an input device on an object identifier, fixed location identifier or network connection element. An indicator indicates, such as by an LED or sound, that association can be performed. An input device may then be activated within a limited time on another location system component, such as an object identifier, to establish an association between the components.

[0111] Events or actions may be initiated based on location information association information or input device status, or changes in any of these. One example involves sending information in response to an object identifier being within a range of locations or a specific location. An example includes paging a doctor when a specific patient enters a treatment area. Other examples of actions include entering information in a database, sending XML data containing the current location data and status of a location system component onto the network. An example is the use of a cardiac monitoring application typically used in a health care institution for receiving a report of a cardiac arrest. The term health care institution, as used herein, includes a wide variety of facilities associated with providing health care or services. Examples include hospitals, managed care facilities, assisted care facilities and clinics. The location system according to an embodiment of the invention may be configured to receive a request for the location of a particular patient, or the cardiac monitoring equipment sounding the alarm. The location system can then automatically reply with location information to assist health care institution staff in locating the patient in need. A similar example could use the activation of an input device on an object identifier as a distress call by a patient, with the alert and location information forwarded to a health care institution communication system for prompt attention by health care institution staff. One embodiment of the invention may interface with a Winegard interface to unlock a door, or activate other security equipment, in response to location information or input device status. Other examples include pages, WAP messages, sending e-mails and activating or canceling alarms.

[0112] According to an embodiment of the invention, the components of the location system do not retransmit signals if they are not received. By waiting until the next scheduled transmission, transmissions throughout the location system area are reduced and interference difficulties are reduced.

[0113] The fixed location identifier 1000, according to an embodiment of the invention is illustrated by way of example in FIG. 11. The fixed location identifier 1000 is similar to the object identifier 800 illustrated and described in relation to FIG. 3. A controller 1010 is provided in communication with controller support 1020. RF and IR transmitters and receivers 1030, 1040, 1050, 1060 may be provided individually or in combination according to various embodiments of the invention. An input device 1070 and indicator 1080 may also each or both be included in various embodiments of the invention. The fixed location identifier 1000 is configured to receive signals from one or more object identifiers 800, and/or other fixed location identifiers 1000, and retransmit these signals to a network connection element 900 along with identifying information to designate which of the fixed location identifiers 1000 is retransmitting the information. Additional information relating to the retransmitting fixed location identifier 1000 may also be appended, such as battery information or other status information allowing remote monitoring of the fixed location identifier 1000.

[0114] According to various embodiments of the invention, the fixed location identifier 1000 may be provided with input devices 1070 or indicators 1080 to enable input information or various signaling functionality. Fixed location identifiers 1000 do not need to be coupled to other components by the use of wiring or other infrastructure. Therefore, the use of fixed location identifiers 1000 enable a location system to be implemented with fewer network connection elements, as fixed location identifiers can provide additional information as to the location of object identifiers 800. Furthermore, fixed location identifiers 1000, can extend the range of network connection elements 900 by providing an optional higher power transmission signal to reach network connection elements 900 at ranges that object identifiers 800 may be incapable of reaching.

[0115] The network connection element 900 is adapted to receive signals from the fixed location identifier 1000 as described above in relation to signals from the object identifier 800. According to an embodiment of the invention, the network connection element 900 contains hardware and software capable of receiving signals from the fixed location identifier 1000. According to an embodiment of the invention, the network connection element 900 may have network connectivity software, a local web server, fixed location identifier software, software to transmit the results of a fixed location identifier analysis to a remote server, DHCP software and local permanent storage. According to an embodiment of the invention, the network connection element 900 may also include configuration, service and debug applets to be used in the maintenance and configuration of the fixed location identifier 1000.

[0116] A location system 720, according to a further embodiment of the invention, is illustrated by way of example in FIG. 12. The location system 720 includes various object identifiers 800, network connection elements 900 and fixed location identifiers 1000. A network 400 is illustrated along with a database 1150 and location resolver 1100. According to the present embodiment, a topology database 1152 is separately provided from the database 1150. The topology database 1152 may be provided with information pertaining to the locations of network connection elements 900 and fixed location elements 900 and fixed location identifiers 1000. Such topology information allows for more descriptive data to be provided regarding the location of object identifiers 800. For example, the location of a fixed location identifier 1000 or network connection element 900 may be specified as a particular office, hallway or area. Therefore, if an object identifier 800 is identified as within a small radius of a fixed location identifier 1000 or network connection element 900, the object identifier 800 may be identified as being within specific room, office or area.

[0117] An electronic device 1101 is provided to host the location resolver 1100. According to this embodiment the location resolver 1100 is in the form of software operating on the electronic device 1101. Examples of electronic devices 1101 include computers, processors or other devices capable of implementing the functionality of the location resolver 1100.

[0118] As shown by way of example, a location determining module 14, according to an embodiment of the invention, is illustrated, by way of example, as including one of the fixed location identifiers 1000, the network 400, the electronic device 1101, the location resolver 1100, the database 1150 and topology database 1152.

[0119] An example of a location system in use in a health care institution setting is illustrated in FIG. 13. As shown by way of example in FIG. 13, a network 400 is provided to allow for communication among multiple network connection elements 900. A location resolver 1100 is also provided in communication is also provided in communication with the network 400. It is noted that the network is not limited to a wired network, as the network may be a wireless network. A fixed location identifier 1000 is illustrated and is in communication with the network connection elements 900. Various object identifiers 800 are illustrated as a fixed to various pieces of equipment within the health care institution setting. The object identifiers 800 may be in communication with one or more of each of the network connection elements 900 and the fixed location identifier 1000.

[0120] As illustrated in FIG. 14, a network interface 992, 1120 is shown by way of example according to an embodiment of the invention. The network interface 992, 1120 may be used in one or more of the network connection elements 900 and/or location resolver 1100 or other components adapted for communication with a network. A network interface 992, 1120 is adapted to be directly coupled to a network. The network interface 992, 1120 may be configured with one or more of the appropriate configurations for the corresponding networks. For example, it is illustrated by way of example in FIG. 14, the network interface 992, 1120 may be configured to be directly to an Ethernet network by way of Ethernet circuitry 994. According to a further embodiment, the network interface 992, 1120 may be coupled to a telephone system to a modem 996. According to another embodiment of the invention, the network interface 992, 1120 may be provided with one or more of a cable television modulator 998 to allow communication with a cable T.V. network, a UTP network card 1122, to allow communication with a UTP network, or a universal serial bus (USB) card 1124 and/or a medical telemetry transmitter 1126 for communication with a medical telemetry network.

[0121] The present invention has been described by way of example, and modifications and variations of the described embodiments will suggest themselves to skilled artisans in this field without departing from the spirit of the invention. Aspects and characteristics of the above-described embodiments may be used in combination. The described embodiments are merely illustrative and should not be considered restrictive in any way. The scope of the invention is to be measured by the appended claims, rather than the preceding description, and all variations and equivalents that fall within the range of the claims are intended to be embraced therein.