Position determination of mobile stations in a wireless network

• US 9,736,637 B2
• Filed: 09/13/2006
• Issued: 08/15/2017
• Est. Priority Date: 09/13/2005
• Status: Active Grant

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Inventors: Larsen, James David
• Primary Examiner(s): SCHWARTZ, JOSHUA L
• Application Number:
  US12/066,745
• Publication Number:
  US 20080280625A1
• Time in Patent Office: 3,989 Days
• Field of Search: 370338, 4554561
• CPC Class Codes: G01S 5/0226 Transmitters
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination
• CPC Class Codes: H04W 8/14 between corresponding nodes

Abstract

A network, and a method of operating a network. The network includes a plurality of stations each able to transmit and receive data so that the network can transmit data between stations via at least one selected intermediate station. Each station transmits probe signals in broadcast fashion to other stations to gather a list of neighbor stations. The stations transmit position data and/or position determining data in at least some of the probe signals. Each station maintains position data and/or position determining data received from selected probing stations, and utilizes the data to determine the absolute or relative position of itself and/or other stations. The stations can determine the relative or absolute position of other stations in direct communication with themselves, and also of other stations not in direct communication with themselves.

Claims

1. A method of operating a network comprising a plurality of stations each able to transmit and receive data so that the network can transmit data between stations via at least one selected intermediate station, the method comprising:

determining locations of stations within the network, comprising;

monitoring at each station, the activity of other stations on the network to establish an availability of neighbor stations having connectivity with the monitoring station;

transmitting probe signals from each station to other stations which receive the probe signals from a probing station responding directly or indirectly via another station, to the probing station to thereby indicate their availability as neighbor stations able to receive or relay data, wherein the probing signals are transmitted at a first power level until a predetermined number of other stations have replied at which point the probing signals are transmitted at a second power level greater than the first power level;

transmitting position data and/or position determining data in at least some of the probe signals and/or in responses to the probe signals, the position data including data indicative of an absolute or relative position of a station transmitting a probe signal or a response signal, and the position determining data including data usable by a station receiving a probe signal or a response signal to determine the absolute or relative position of the station and/or other stations;

maintaining, at stations which receive probe signals from one or more probing stations and/or response signals from one or more responding stations, position data and/or position determining data received from selected ones of the probing and/or responding stations;

at one or more of said stations maintaining said position data and/or position determining data, utilizing the position data and/or position determining data to determine the absolute or relative position of said each station and/or other stations, thereby enabling any station to determine its own position or the position of another station in the network either as an absolute position or relative to other stations;

after determining the locations of stations within the network, selecting a receiving station to which to send a communication;

determining an optimized route along which to send the communication to the receiving station, the optimized route based on a determined location of the receiving station, determined relative locations of one or more intermediate stations within the network, and the minimum power requirement for sending the communication to the receiving stations through the one or more intermediate stations; and

sending the communication on the optimized route.

2. A method according to claim 1 wherein the position data and/or position determining data in the probe signals includes data indicating the absolute position or relative position of nearby stations selected by the station transmitting the probe signals.

3. A method according to claim 1 wherein the position data and/or position determining data is used to determine the relative or absolute position of other stations in direct communication with said each station, and also other stations not in direct communication with said each station.

4. A method according to claim 1 which is operated in a communication network in which the stations can transmit a message from an originating station to a destination station via at least one opportunistically selected intermediate station.

5. A method according to claim 1 which is operated in a network provided primarily for purposes of tracking or locating stations in the network.

6. A method according to claim 1 including selecting, at each station, a channel for transmission of probe signals to other stations, other stations which receive the probe signals from a probing station responding directly, or indirectly via other stations, on the selected channel.

7. A method according to claim 1 wherein stations include data in their probe signals relating to a length of time they have remained static, other stations receiving the probe signals utilizing position data and/or position determining data preferentially from stations that have remained static for the longest periods.

8. A method according to claim 1 wherein stations include auxiliary data in their probe signals relating to one or more of the following:

a number and/or quality of transmission hops between stations identified in the probe signals;

age data indicating an age of timing data or position data and/or position determining data included in the probe signals;

the stated or determined level of accuracy of position information relating to one or more stations identified in the probe signals; and

quality data indicating whether the probe signals have been sent at peaks of opportunity, other stations receiving the probe signals utilizing position data and/or position determining data therein selectively depending on the nature of the auxiliary data included in the received probe signals.

9. A method according to claim 1 wherein stations maintain historical position data of other stations for a predetermined time after such other stations have lost connectivity with one another, the historical position data being retrievable to determine the last known position of a station with which connectivity has been lost.

10. A method according to claim 1 wherein stations utilise variations in data in probe signals or other characteristics of the probe signals, arising out of relative movement between stations, to resolve ambiguities in relative position data and/or position determining data in the probe signals.

11. A method according to claim 1 wherein the nature or quality of a service available from a station in the network is adjusted according to the determined absolute or relative position of said station and/or other nearby stations.

12. A method according to claim 11 including providing information to a user of a station relating to facilities, objects or persons, or other stations near to the determined position of said station.

13. A method according to claim 1 wherein position information relating to a station is determined by transmitting gradient gathering probe signals between stations, directly or via one or more intermediate stations.

14. A method according to claim 13 wherein the gradient gathering probe signals are transmitted at an increased rate selected to provide enhanced resolution of the position information.

15. A method according to claim 14 wherein the gradient gathering probe signals are transmitted at an increased rate only while the position information is required.

16. A method according to claim 1 wherein a first station requiring position information relating to another station in the network transmits a position request message addressed to a central authority maintaining position data and/or position determining data of stations in the network;

to one or more neighbors of the first, requesting station for onward transmission to the other station;

or directly to the other station.

17. A method according to claim 16 wherein the station whose position is required transmits a reply message to the first station via the network with the required position information.

18. A method according to claim 16 wherein the first station transmits a gradient gathering probe signal addressed to the other station via one or more intermediate stations, said other station transmitting a response via one or more Intermediate stations to thereby create a gradient through the intermediate stations, the gradient providing information enabling a relative or absolute direction vector to be established between the first station and said other station.

19. A method according to claim 1 wherein the position data comprises position information indicating the position of one or more stations to a predetermined degree of accuracy.

20. A method according to claim 19 wherein the position data comprises absolute position information obtained from a station equipped with a station based positioning system, or a station with a known fixed location.

21. A method according to claim 20 comprising utilizing a combination of absolute and relative position information to determine the absolute position of further stations by determining their position relative to other stations that have previously determined their own absolute positions, so that such further stations that are unable to communicate directly with other stations that have absolute position information can nevertheless determine their own absolute position indirectly.

22. A method according to claim 20 including providing a number of seed stations, each of which is able to determine, or is provided with absolute position data defining, its own absolute position with relatively high accuracy, other stations transmitting probe signals to and receiving probe signals from the seed stations thus obtaining absolute position information from the seed stations to determine their own absolute positions, and further stations transmitting probe signals to and receiving probe signals from said other stations thus obtaining absolute position information from said other stations to determine their own absolute positions.

23. A method according to claim 1 wherein the position data comprises relative position information indicating the position of one or more stations relative to other stations.

24. A method according to claim 23 wherein the relative position information is obtained by stations determining an approximate distance between themselves utilizing transmission power and/or path loss data in probe signals transmitted between such stations.

25. A method according to claim 23 including obtaining position information indicating the position of one or more stations by triangulation.

26. A method according to claim 23 wherein the relative position information is obtained by stations determining a distance between themselves utilizing timing data extracted from probe signals transmitted between the stations.

27. A method according to claim 26 wherein the timing data includes processing delay data inserted into reply probe signals by stations responding to received probe signals, the processing delay data indicating a time taken at a station responding to a received probe signal to process the received probe signal.

28. A method according to claim 1 including transmitting clock data in the probe signals, and utilizing the clock data to determine a time taken for the probe signals to propagate between stations and hence a distance between said stations.

29. A method according to claim 28 including synchronizing clocks at the stations of the network, with updated timing data for this purpose being transmitted from a central timing authority to the other stations.

30. A method according to claim 29 wherein an acceptance or rejection of said updated timing data at any station is determined in response to a cumulative error function calculated in respect of transmission of such data, relative to other prior or simultaneous transmissions of such data received at said station, thereby maintaining a high level of accuracy in respect of the synchronization of clocks at each station of the network.

31. A method according to claim 29 wherein each station selects received probe signals from which to extract position or timing data according to the extent to which such received probe signals are determined to contain position or timing data of a high quality in terms of distance measurement capability or clock synchronization.

32. A method according to claim 31 comprising analyzing received probe signals to determine whether or not they are transmitted during optimum peaks of opportunity.

33. A method according to claim 31 comprising measuring path loss and/or multi-path distortion in such received probe signals, and selecting probe signals having low path Joss and/or low multi-path distortion for extraction of position or timing data therefrom.

34. A method of operating a network comprising a plurality of stations, the method comprising:

transmitting, with a transmitting station, a probe signal to one or more neighbor stations, the probe signal including position data of the transmitting station and identification data from the transmitting station, the probing signal being transmitted at a first power level;

transmitting, with the one or more neighbor stations, a response signal including position data of the one or more neighbor stations and the identification data in response to the probe signal;

transmitting, with the transmitting station, probe signals at increasing power levels higher than the first power level until a predetermined number of neighbor stations transmit response signals to the transmitting station, wherein the probe signals are transmitted on probe channels defined by a central authority, thereby reducing interference and preventing jamming or interception of the signals;

monitoring, at the transmitting station, the response signals to establish an availability of the one or neighbor stations and a determined position of the one or more neighbor stations that are available;

updating the determined position of one or more available neighbor stations based on differences in position data of the one or more available neighbor stations;

determining an available neighbor station to which to send a communication;

determining an optimized route along which to send the communication to the available neighbor station, the optimized route based on the determined location of the available neighbor station and the minimum power requirement for sending the communication to the available neighbor station through one or more other intermediate available neighbor stations; and

sending the communication on the optimized route.

35. A network comprising a plurality of stations each able to transmit and receive data so that the network can transmit data between stations via at least one selected intermediate station, wherein each station in the network comprises a transmitter, a receiver and data processing means and is operable to:

monitor the activity of other stations on the network to establish an availability of neighbor stations having connectivity with the monitoring station;

transmit probe signals to other stations and receive probe signals from other stations so that other stations which receive the probe signals from a probing station can respond directly, or indirectly via another station to the probing station to thereby indicate their availability as neighbor stations able to receive or relay data which probing signals begin at low power then increase in power until a predetermined number of other stations have replied;

transmit position data and/or position determining data in at least some of the probe signals and/or in responses to probe signals, the position data including data indicative of the absolute or relative position of a station transmitting a probe signal or a response signal and the position determining data including data usable by a station receiving a probe signal or a response signal to determine the absolute or relative position of the station and/or other stations;

maintain at stations which receive probe signals from one or more probing stations and/or response signals from one or more responding stations position data and/or position determining data received from selected ones of the probing stations and/or responding stations;

utilize the maintained position data and/or position determining data to determine the absolute or relative position of said station and/or other stations thereby enabling any station to determine its own position or the position of another station in the network either as an absolute position or relative to other stations;

after determining the locations of stations within the network, select a receiving station to which to send a communication;

determine an optimized route along which to send the communication to the receiving station, the optimized route based on a location of the receiving station, relative locations of one or more intermediate stations within the network, and the minimum power requirement for sending the communication to the receiving stations through the one or more intermediate stations; and

send the communication on the optimized route.

36. A network according to claim 35 wherein each station is operable to determine the absolute or relative position of other stations in direct communication with said station, and also other stations not in direct communication with said station.

37. A network according to claim 35 wherein at least some stations comprise a station based positioning system or are programmed with position data corresponding to a known fixed location.

38. A network according to claim 35 including a number of seed stations each able to determine its own absolute position with relatively high accuracy, so that other stations transmitting probe signals to and receiving probe signals from the seed stations can obtain absolute position information from the seed stations to determine their own absolute positions, and further stations transmitting probe signals to and receiving probe signals from said other stations can obtain absolute position information from said other stations to determine their own absolute positions.

39. A network according to claim 35 including a central authority to define probe channels for transmission of the probe signals, to reduce interference and prevent jamming or interception of the signals.

40. A network according to claim 35 wherein each station is adapted to determine an approximate distance between itself and other stations utilizing transmission power and/or path loss data in probe signals transmitted between the stations.

41. A network according to claim 40 wherein each station is adapted to obtain position information indicating the position of one or more other stations by triangulation.

42. A network according to claim 35 wherein the data processing means of each station is operable to analyze received probe signals to determine whether or not they are transmitted during optimum peaks of opportunity.

43. A network according to claim 42 wherein the data processing means is operable to analyze received probe signals by measuring path loss and/or multi-path distortion in received probe signals, and to select probe signals having low path loss and/or low multi-path distortion for extraction of position or timing data therefrom.

44. A network according to claim 35 wherein each station includes a clock and is arranged to transmit clock data in the probe signals, and to utilize the clock data to determine a time taken for the probe signals to propagate between stations and hence a distance between said stations.

45. A network according to claim 44 including a central timing authority for transmitting updated timing data to the stations of the network, and wherein each station is arranged to synchronize its clock with clocks of other stations of the network utilizing the updated timing data.

46. A network according to claim 45 wherein each station is arranged to accept or reject said updated timing data according to a cumulative error function calculated in respect of transmission of such data, relative to other prior or simultaneous transmissions of such data received at said station, thereby maintaining a high level of accuracy in respect of the synchronization of clocks at each station of the network.