Decentralized wireless communication network and method having a plurality of devices

A wireless communication system and method for determination of the location of a location-incapable device of a decentralized wireless communication network. Upon receipt of location determination information, relevant to the location of the location-incapable device in the network and sufficient to perform a calculation of the location of the location-incapable device, a location-capable device of the network may calculate the location of the location-incapable device and make this information available to one or more devices of the network.

FIELD OF THE INVENTION

The present invention relates generally to communication networks and more specifically to the use of location determination methods and structures in wireless communication networks.

BACKGROUND

Peer-to-peer network location resolution is an emerging market within the wireless communication arena. New systems are being developed to find people and/or objects, in various environments. For outdoor environments, there are many solutions such as GPS that can provide reliable location estimates. In building location solutions, however, techniques are still being researched and developed. Many indoor location determination solutions operate on radio frequency signals and require a dense installation of receivers capable of measuring characteristics of the received waveforms that are used to determine the transmitter's location.

Wireless location determination or radiolocalization in Wireless Personal Area Networks (WPANs) is an area receiving increasing attention. Accurate and cost-effective localization is a key application enabler for wireless sensor networks in a variety of applications such as warehousing and manufacturing logistics. Another typical application may be inventory management: An office has a collection of computers, printers, lab equipment, etc. and the office manager would like to know the location of this office equipment at all times. To date, this has been done with portal systems. Examples of wireless network technology that shows promise in addressing many of the shortcomings of current wireless PANs in terms of cost, throughput, and scalability include the 802.15.4/ZigBee standard, Bluetooth, such as Bluetooth 1.0B, and radiotransceivers and wireless sensor devices operable in these technologies.

Wireless sensor devices may often be highly resource constrained, however. Thus, while some devices of the network may have the ability to perform device location determination this may not be the case for a number of the devices of the wireless network. One of the shortcomings of the current wireless PAN solutions is their inability to provide low cost, transparent location determination for devices within the network. Ideally, each device within the network should have the ability to determine its connectivity status and physical location within the network without the use of specialized and expensive hardware and software. Ideally, location determination calculations could be performed without a corresponding reduction in data throughput between devices within the network.

DETAILED DESCRIPTION

Radiolocalization in wireless sensor networks can be performed in a centralized manner where all devices send their range-related waveform measurements to a location server which calculates the location using a location algorithm. A known drawback of a centralized localization approach is the traffic load that data upstream data communication places on the network throughput. Another one is the delay associated with communication with the server. Alternatively, localization can employ another approach in which location determination is performed on-chip using a built-in location solver. In wireless sensor networks, a hardware approach may be preferred to a software solution due to the complexity associated with localization solutions. An example of this approach is the Chipcon CC2431 which incorporates an on-chip location engine core on the device that enables the device to automatically calculate its location. Such a device having on-chip or on-board location determination capability at the device may be referred to as a location-capable device.

In accordance with the present invention, a source-constrained node may outsource or delegate determination of its location to a peer node that has location determination capabilities, such as the built-in on-chip location engine core referenced above. By enabling a resource-constrained node or device to outsource their location calculation functions to a peer node, a more efficient, distributed localization in the wireless network may be realized.

Therefore, in a wireless network, the present invention enables resource-constrained nodes, referred to herein as location-incapable nodes or devices, to delegate the task of determining their location to other peer devices, referred to as location-capable devices or nodes, within the network that are capable of performing location determination calculations. Location determination for resource-constrained or location-incapable nodes or devices by location-capable devices tapped to perform this function allows the network to operate much more quickly and efficiently since it is no longer a requirement that location determination information needed to perform such device location determinations be forwarded to a centralized location server or application.

It is understood that location-incapable devices may encompass devices or nodes incapable of determining their own location as well as devices or nodes of the network that, while capable of determining their location or the location of another device within communication range, decline to do so, for whatever reason. For instance, a device capable of performing location determination calculations may elect to not do so because at the time it is requested to perform the location determination, it needs to behave as a location-incapable device. Such may be the case where it is desirable for the device to offload computational load to save battery, upon detecting a failure of the location calculation block of the device, or other device conditions. Network conditions that might indicate the device wishes to not assume location determination responsibilities could include traffic volume and/or latencies within the network.

It is further understood that the location determination information collected by the location-incapable device and sent to the location-capable device for use in the location determination calculations is relevant to the location of the location-incapable device. The location determination information includes measurements of one or more parameters related to distance received by the location-incapable device as well as location information of location-aware devices communicatively coupled to the location-incapable device, such as within multi-hop range or otherwise within communication range.

There are many measurements that may be made to yield parameters related to distance measurements of the location-incapable node vis-à-vis other devices to which it is communicatively coupled. As an example, consider that the location-incapable node may measure received signal strength (RSS) or time of arrival (TOA); both of these are parameters related to distance of the location-incapable device to one or more location-aware devices to which it may be within communication range (communicatively coupled). Location information of location-aware devices communicatively coupled to the location-incapable device may include the location coordinates of these devices. It should be noted that location-aware nodes or devices encompass any device or node aware of its position in the network. Thus, a reference node given its location coordinates during network commissioning or formation, a location-capable node aware of its position, or even a location-incapable node with knowledge of its location (remember that location-incapable nodes include any device or node either incapable of, unwilling or unable to calculate location determination at a given point in time) are all examples of location-aware devices or nodes.

The location-capable device, then, has a location determination capability, such as a radiolocation hardware engine core, that enables efficient on-chip self-positioning in wireless PANs without the need to consult a central location function, such as a central location server or application capable of determining location for many of the devices of the network. This location determination capability of a location-capable device is utilized as needed by other nodes or devices of the network that either cannot or choose to not calculate their own locations. A resource-constrained node, referred to as a location-incapable node as explained above, will send its measurements along with supplementary information need to calculate location, together referred to as location determination information, to a nearby location-capable device which can then calculate the position of the location-incapable node and report that information. The information is reported back to the location-incapable device so that it then becomes a location-aware node and the location may also be reported to other nodes in the network as well as to a central location function of the network, such as a location server or location application.

Decentralized location calculation is attractive as it reduces the traffic load and the delay incurred by nodes sending their range-related measurements upstream to the centralized location server. All devices or nodes of the network, whether or not they themselves have location-determination capabilities, can easily and efficiently determine their location in the network.

Referring toFIG. 1, an exemplary network100containing various devices is illustrated. Device102is illustrated as a “blindfolded” or location-incapable node, unaware of its location in the network, and is designated as a white node. Communicatively coupled to device102are devices104,106,108,110, illustrated as black; device112is not communicatively coupled to location-incapable device102. Also in the network100is a location function element120, which may be a location server or a location application. The location element120may operate in the network to collect the location information of various devices of the network and/or have location calculation capabilities, such as might be useful in the centralized approach not necessary in accordance with the present invention.FIG. 1serves to illustrate the location and communication relationships between various devices of the network. It further illustrates the occasion of location-incapable device102sending a communication to other devices with which it is communicatively coupled. In an exemplary embodiment, device102is sending out a request to devices within its communication range for information about their locations (such as location information and other information relevant for ranging function) as well as requests for messages from these other devices; it is from these messages sent back to it (as shown inFIG. 2) that the location-incapable device102may make measurements of parameters related to distance between device102and its neighbors, i.e. range-related measurements. Again, as mentioned above, device102may be making measurements related to RSS or TOA, for example. AOA (Angle of Arrival) combined with TOA or combinations of TOA, RSS can also be done. Moreover, electromagnetic field measurements may be used as ell. Measurements can be made by listening to beacon messages transmitted by the location-aware devices104,106,108,110,115for the case of RSS or by two-way packet exchanges for the case of TOA measurements. Either type of information gleaned from the return waveforms ofFIG. 2, together with the location information of the neighboring devices, may be used by a location determination function to determine the location of location-incapable device102.

Location-incapable device102performs range-related measurements and receives location information from devices104,106,108,110and115. Receipt of such information may occur in various ways, including by means of a passive scan or an active scan. Referring now toFIG. 3, transmission of beacon or packet information by devices104,106,108,110,115may occur as a result of a passive scan in which device102listens for regular message transmissions. Alternately,FIG. 4illustrates an active scan by device102in which device102sends a request for message transmissions from neighboring nodes, such as illustrated byFIG. 1in which device102transmits a location data request command, which may be by broadcast or polling, to devices104,106,108,110.

FIG. 2also illustrates that another device, device115is communicatively coupled to device102and indeed is also transmitting its location coordinates as well as waveforms to device102. Device115is a location-capable device in this example and is thus distinguished from other devices communicatively coupled to102by its gray-scale appearance.

Referring now toFIG. 5, the location-incapable device102may now forward its location determination information received from waveform measurements and location data of devices with which it has communicated to location-capable device115. It is not required that location-capable device115be located in the immediate neighborhood of the location-incapable device. Location-capable device115uses the location determination information to calculate the location of device102, or alternately, if device115does not wish to or cannot perform this service, it may transmit the location determination information to another location-capable device of the network. AtFIG. 6, the calculated location of device102is communicated. The location is communicated back to device102, but may also optionally be communicated to another device of the network, such as device110or a location function120as shown by the dashed lines.

The above description is further illustrated by the flowcharts ofFIGS. 7-9. Referring now toFIG. 7, flow700illustrates an exemplary flow from the perspective of a location-incapable device. At Block710, the location-incapable device receives message transmissions from location-aware devices to which it is communicatively coupled. There may be location information embedded in these message that the location-incapable device gets from the message(s). The location-incapable device can then make measurements of the waveforms received from its location-aware neighbors to obtain measurements related to distance at Block720; again, these measurements may be RSS or TOA directed; TOA and RSS could also be done if desired. At Block730, the location-incapable device transmits location determination information, relevant to the location of the location-incapable device in the network and sufficient to perform a calculation of the location of the location-incapable device, to the location-capable device.

It has been described that the location-incapable device may receive its location calculated by a location-capable device from the location determination information; this is shown inFIG. 6for example. Moreover, the received waveforms from the location-aware neighbor devices may be the result of active or passive scanning, as described above. In the case of passive scanning, the location-incapable device listens for message transmissions from the one or more location-aware devices, receives message transmissions from them, and then measures waveforms of the received message transmissions from the one or more location-aware devices to obtain the measurements from the location-incapable device to the one or more location-aware devices. In the case of active scanning, the location-incapable device transmits a request for message transmissions from the one or more location-aware devices, receives the requested message transmissions from the location-aware devices, and measures the waveforms of the received message transmissions. Also, it is noted that the location-incapable device may select to transmit the location determination information to the location-capable device on the basis of one or more criteria. Moreover, the location-incapable device may or may not also be a location-aware device of the network. Additionally, the location-capable device may not necessarily be in one hop range of the location-incapable device.

InFIG. 8, a flow800from the perspective of a location-capable device is provided. At Block810, the location-capable device receives location determination information relevant to the location of the location-incapable device in the network. At Decision Block820, a decision as to whether the location-capable device will undertake the location determination task request is made. If no, then it may transmit the location determination information to another, second location-capable device to determine location of the requesting device at Block830. Again, conditions under which the location-capable device may decline to undertake the location determination request may include a need for the location-capable device to offload computational load to save its battery life, upon detecting a failure of its location calculation block of the device, or other device condition. Network conditions that might indicate the device wishes to not assume location determination responsibilities could include traffic volume and/or latencies within the network. If yes, then at Block840, the location-capable device performs the location calculation and has a location determination element or function for this task. At Block850, the determined location may be communicated. Again, the location will most likely be transmitted back to the requesting, location-incapable device but could also be transmitted to a location function or another device in the network. The location-capable device may or may not also be a location-aware device of the network.

Referring now toFIG. 9, an overall network approach for determining a location of a location-incapable device of a decentralized wireless communication network also having location-aware devices communicatively coupled to the location-incapable device and a location-capable device communicatively coupled to the location-incapable device. At Block910, the location-incapable device transmits its location determination information to the location-capable device. At Block920, a location-capable device, which may or may not be the location-capable device to which the location-incapable device directly made its calculation request, receives the location determination information and calculating the location of the location-incapable device in the network. Lastly, at Block930, the location of the location-incapable device is communicated. The location may be communicated to the location-incapable device, a device of the network, and/or a location function of the network. The location-capable device may or may not be also a location-aware device of the network.

FIG. 10illustrates a block diagram1000of an exemplary device, which in at least some instances will correspond to the devices described above. To facilitate wireless communications, the device can include a transceiver1002and an antenna1004. One skilled in the art will recognize that such a block structure and arrangement will support various different types of wireless communications, which could be implemented without departing from the spirit and scope of the present invention.

In at least the illustrated embodiment, the exemplary unit1000, additionally includes a range measurement module1006, which allows for a measured range determination between other units within communication range; module1006may be integrated into the transceiver. As noted previously, several different methods could be incorporated for determining range, at least a couple of examples include a range measurement based upon a received signal strength indication, time of arrival estimate, angle of arrival estimate, and/or a time difference of arrival estimate. For purposes of supporting the determination of a received signal strength indication, the range measurement module1006could include a signal strength measurement module1008. Alternatively or additionally, the range measurement module1006could include a timer1010, which could be used in connection with determining a time of arrival estimate or a time difference of arrival estimate. The measured range information, is then used to determine a location estimate after the information is gathered in the device.

In at least some instances, the range measurement module1006may be implemented as one or more sets of prestored instructions, which are executed in a microprocessor. In other instances, the modules may be implemented using various electronic circuit elements. The block diagram illustrated inFIG. 10may similarly correspond in some instances to one or more of the devices of the network, where it may be desirable for the units to similarly be able to obtain information necessary to determine their location or range between nearby units.

Each device within the network may contain a similar set of functionality for interacting with other wireless devices within the network. Referring now to block diagram300ofFIG. 11, a functional view1100of a representative wireless device1101is shown. Device1101receives incoming messages1110, through message receiver1130, and processes the messages with processor1140under the control of controller1150. Device timing is provided in block1160, while storage for the device is located in block1170. Outgoing messages1120are transmitted by message transmitter1180. Timing block1160provides the clocking and synchronization for the channel assignments selected by the processor1140. The timing block1160may also provide the reference clock for range determination. Storage block1170stores location determination information1176. It will be recognized by one skilled in the art that the functionality represented inFIG. 11is only representative of an external view of wireless device1101, and additional functionality may be added, or the described functionality may be combined, without departing from the spirit and scope of the present invention.

Generally, the method and system for determining a location for a plurality of units can be used in connection with the location of any number of individual items among a group of items, one such example including the detection of items in a storage location or in a warehouse environment. However, the method and system for determining a location has additional applicability in other networks, wherein the determination of the location of individual elements is desired and a corresponding set of reference units and other non-reference units are available throughout the area to assist in determining a location estimate. At least one such example includes the location of devices such as one or more cellular telephones or other wireless communication devices located within a network.

Still further, the location determination module could be incorporated as part of the equipment for one or more groups of personnel operating in concert within a given area or environment. One such example includes emergency personnel. In this instance the circuitry and/or modules associated with each of the units could be located in one or more of a fire fighter's helmet, jacket, or other piece of equipment.

Further yet, the method and system for determining a location could be made to function with many different forms of wireless communications including communications systems, which use a cellular telephone radio transceiver, a cordless telephone radio transceiver, a wireless LAN connection, a short range radio transceiver, such as a Bluetooth transceiver, an infra-red communication transceiver, or other similar communication device. Still further there is no requirement that the units be completely physically detached from one another, for example, the method and system for determining a location could interact with an installed sprinkler system, which might include wireless transceivers, and/or which might be communicatively coupled to one another, via one or more common communication busses, which traverse the area containing the network.