System and method for determining location of a device in a wireless communication network

• US 7,215,966 B2
• Filed: 06/07/2004
• Issued: 05/08/2007
• Est. Priority Date: 06/05/2003
• Status: Active Grant

• Current Assignee: Strong Force IoT Portfolio 2016, LLC (Strong Force Intellectual Capital, LLC)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Joshi, Avinash
• Primary Examiner(s): Feild, Joseph
• Assistant Examiner(s): DESIR, PIERRE LOUIS
• Application Number:
  US10/863,871
• Publication Number:
  US 20040259571A1
• Time in Patent Office: 1,065 Days
• Field of Search: 455/456.1, 455/456.2, 455/456.5, 455/452.1, 455/435.1, 455/436, 455/408, 455/450, 370/352, 370/466, 370/218, 709/239, 709/242
• US Class Current: 455/456.1
• 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 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method for message exchanges in a wireless communication network which minimize network overhead and offers fast determination of Coordinates of a device. A system and method controls a node to exchange small, structured messages with one or more reference nodes requesting the Coordinates of the reference node, which are then used in a periodic evaluation of time of flight messages from that reference node for determination of Coordinates of the node.

Claims

1. A method for enabling a node in a wireless communication network to determine its location coordinates, based on the location coordinates of at least one other node, the method comprising:

controlling the node to request at least one other node to provide location coordinates either periodically or upon the node receiving at least one of a hello message, routing message, neighbor advertisement and short hello message from the said at least one other node and, in reply, controlling said at least one other node to provide the location coordinates;

controlling the node to periodically evaluate time of flight messages received at the node from the at least one other node;

controlling the node to estimate its own location coordinates based on the information pertaining to the location coordinates of the said at least one other node and the evaluation of the time of flight messages;

assigning a respective sequence number to each respective other node;

changing the sequence number of an other node when the location coordinates of that other node change; and

controlling the node to check the sequence number of the other node when the node receives a time of flight message from that other node, and controlling the node to send a request to that other node to provide updated location coordinates if the sequence number is different from a sequence number for that other node that was previously received by the node.

2. A method as claimed in claim 1, wherein:

the request is at least one of a location request message, routing message and MAC message; and

the reply is at least one of a location reply message, routing message and MAC message.

3. A method as claimed in claim 1, wherein:

the node is a mobile node.

4. A method as claimed in claim 1, wherein:

the node stores the respective location coordinates of an other node at a location in a neighbor table corresponding to that other node.

5. A method as claimed in claim 1, wherein:

the three controlling steps are performed for each of a plurality of other nodes.

6. A method as claimed in claim 5, wherein:

at least one of the other nodes is mobile.

7. A method as claimed in claim 1, wherein:

the rate of periodicity depends on the rate of change of the coordinates of the at least one other node.

8. A method as claimed in claim 1, wherein:

the hello message, routing message, neighbor advertisement and short hello message each include information identifying a characteristic of the other node from which the message was sent.

9. A method as claimed in claim 1, wherein:

the wireless network includes an ad-hoc multi-hopping peer-to-peer wireless network.

10. A node in a wireless communication network that is adapted to determine its location coordinates, based on the location coordinates of at least one other node, the node comprising:

a controller, adapted to control the node to request at least one other node to provide location coordinates either periodically or upon the node receiving at least one of a hello message, routing message, neighbor advertisement and short hello message from the said at least one other node and, in reply, controlling said at least one other node to provide the location coordinates; and

the controller is further adapted to control the node to periodically evaluate time of flight messages received at the node from the at least one other node, and to control the node to estimate its own location coordinates based on the information pertaining to the location coordinates of the said at least one other node and the evaluation of the time of flight messages,

a respective sequence number to each respective other node, and the sequence number of an other node change when the location coordinates of that other node change; and

the controller of the node is further adapted to control the node to check the sequence number of the other node when the node receives a time of flight message from that other node, and to control the node to send a request to that other node to provide updated location coordinates if the sequence number is different from a sequence number for that other node that was previously received by the node.

11. A node as claimed in claim 10, wherein:

the request is at least one of a location request message, routing message and MAC message; and

the reply is at least one of a location reply message, routing message and MAC message.

12. A node as claimed in claim 10, wherein:

the node is a mobile node.

13. A node as claimed in claim 10, wherein:

the controller is further adapted to control the node to store the respective location coordinates of an other node at a location in a neighbor table corresponding to that other node.

14. A node as claimed in claim 10, wherein:

the controller is further adapted to perform the controlling operations for each of a plurality of other nodes.

15. A node as claimed in claim 14, wherein:

at least one of the other nodes is mobile.

16. A node as claimed in claim 10, wherein:

the rate of periodicity depends on the rate of change of the coordinates of the at least one other node.

17. A node as claimed in claim 10, wherein:

the hello message, routing message, neighbor advertisement and short hello message each include information identifying a characteristic of the other node from which the message was sent.

18. A node as claimed in claim 10, wherein:

the wireless network includes an ad-hoc multi-hopping peer-to-peer wireless network.

19. A method of operation of a communication device within a wireless communication network comprising:

transmitting a location request message to a reference node, wherein the location request message comprises a message type, a source address of the communication device, and a destination address of the reference node;

receiving a location reply message from the reference node, wherein the location reply message comprises a message type, the source address, the destination address, and a device coordinates of the at reference node;

storing the device coordinates associated with the reference node in a neighbor table;

repeating the transmitting, receiving, and storing steps for one or more other reference nodes; and

only repeating the transmitting, receiving, storing, and repeating steps when the communication device enters a new neighborhood with one or more new neighbor reference nodes,

wherein at least one of the reference nodes is a mobile reference node, the method further comprising;

storing a reference type associated with the mobile reference node in the neighbor table, wherein the reference type comprises a frequency of change of coordinates received from the mobile reference node; and

periodically repeating at a time period the transmitting, receiving, and storing steps for the mobile reference node, wherein the time period is associated with the reference type of the mobile reference node.

20. A method of operation of a communication device as claimed in claim 19 wherein the time period increases as the frequency of change of coordinates decreases;

and further wherein the time period decreases as the frequency of change of coordinates increases.

21. A method of operation of a communication device as claimed in claim 19, further comprising prior to the repeating step:

periodically checking the neighbor tables to identify one or more reference nodes without stored coordinates,

wherein the repeating step comprises repeating the transmitting, receiving, and storing steps for the one or more reference nodes without stored coordinates.

22. A method of operation of a communication device as claimed in claim 19, further comprising prior to the repeating step:

receiving a Hello Message from a new reference node,

wherein the repeating step comprises repeating the transmitting, receiving, and storing steps for the new reference node.

23. A method of operation of a communication device as claimed in claim 19 further comprising:

determining a location of the communication device by using the stored coordinates to calculate a time of flight from each of the reference nodes.

24. A method of operation of a wireless communication network comprising a plurality of nodes comprising:

at each of the plurality of nodes;

maintaining a location sequence number;

detecting a change in location coordinates; and

increasing the location sequence number;

transmitting a time of flight message from a node to a neighbor node of the plurality of nodes;

communicating a time of flight reply from the neighbor node to the node, wherein the time of flight reply includes a current location sequence number for the neighbor node;

comparing by the node the current location sequence number with a stored location sequence number for the neighbor node;

transmitting a location request message from the node to the neighbor node when the current location sequence number is different from the stored location sequence number for the neighbor node, wherein the location request message comprises a message type, a source address of the node, and a destination address of the neighbor node;

receiving a location reply message by the node from the neighbor node, wherein the location reply message comprises a message type, the source address, the destination address, and a device coordinates of the neighbor node; and

storing the device coordinates associated with the neighbor node in a neighbor table of the node.

25. A method of operation of a wireless communication network as claimed in claim 24, the method further comprising:

storing a reference type associated with the neighbor node in the neighbor table; and

periodically repeating at a time period the transmitting, receiving, and storing steps for the mobile reference node, wherein the time period is associated with the reference type of the neighbor node.

26. A method of operation of a wireless communication network as claimed in claim 25, wherein the reference type comprises a frequency of change of the location sequence number of the neighbor node.

27. A method of operation of a communication device as claimed in claim 26 wherein the time period increases as the frequency of change of the location sequence number decreases;

and further wherein the time period decreases as the frequency of change of the location sequence number increases.