Position Determination of Mobile Stations in a Wireless Network

• US 20080280625A1
• Filed: 09/13/2006
• Published: 11/13/2008
• 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
• Granted Patent: US 9,736,637 B2
• Time in Patent Office: Days
• US Class Current: 455/456.1
• 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 neighbour 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-46. -46. (canceled)

47. 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:

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

transmitting probe signals from each station, 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;

transmitting 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;

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; and

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.

48. A method according to claim 47 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.

49. A method according to claim 47 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.

50. A method according to claim 47 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.

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

52. A method according to claim 47 including selecting, at each station, a channel for the 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.

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

54. A method according to claim 53 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.

55. A method according to claim 54 wherein the acceptance or rejection of said updated timing data at any station is determined in response to a cumulative error function calculated in respect of the 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.

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

57. A method according to claim 56 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.

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

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

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

61. A method according to claim 60 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 the time taken at a station responding to a received probe signal to process the received probe signal.

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

63. A method according to claim 57 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.

64. A method according to claim 57 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.

65. A method according to claim 54 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.

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

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

68. A method according to claim 47 wherein stations include data in their probe signals relating to the 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.

69. A method according to claim 47 wherein stations include auxiliary data in their probe signals relating to one or more of the following the number and/or quality of transmission hops between stations identified in the probe signals;

age data indicating the 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.

70. A method according to claim 47 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.

71. A method according to claim 47 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.

72. A method according to claim 47 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.

73. A method according to claim 47 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.

74. A method according to claim 73 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.

75. A method according to claim 47 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.

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

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

78. A method according to claim 47 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.

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

80. A method according to claim 78 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.

81. 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 the 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;

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; and

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.

82. A network according to claim 81 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.

83. A network according to claim 81 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 the time taken for the probe signals to propagate between stations and hence the distance between said stations.

84. A network according to claim 83 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 the clocks of other stations of the network utilizing the updated timing data.

85. A network according to claim 84 wherein each station is arranged to accept or reject said updated timing data according to a cumulative error function calculated in respect of the 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.

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

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

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

89. A network according to claim 81 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.

90. A network according to claim 81 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.

91. A network according to claim 90 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.

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