Method and wireless terminal for generating and maintaining a relative positioning system

• US 20040203380A1
• Filed: 12/31/2002
• Published: 10/14/2004
• Est. Priority Date: 07/03/2000
• Status: Abandoned Application

• Current Assignee: Ecole polytechnique fãdãrale de lausanne epfl (Schweizerische Eidgenossenschaft)
• Original Assignee: Ecole polytechnique fãdãrale de lausanne epfl (Schweizerische Eidgenossenschaft)
• Inventors: Capkun, Srdan, Hamdi, Maher, Vetterli, Martin, Hubaux, Jean-Pierre
• Application Number:
  US10/334,110
• Publication Number:
  US 20040203380A1
• Time in Patent Office: Days
• US Class Current: 455/41.2
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

A method for determining the relative position of wireless terminals (1) in an ad hoc network, wherein at least some of said wireless terminals can communicate over wireless links (2) in one or several hops with at least some of the other wireless terminals. The following steps are performed in the wireless terminals: (1) measuring in a plurality of said wireless terminals the distances (d_ij) to one-hop neighbors, and (2) using the distances measured in at least two wireless terminals to compute the location (x, y) of at least one other wireless terminals. One advantage of the invention is GPS-less positioning in ad hoc networks.

Claims

1. A method for determining the relative position of wireless terminals in an ad hoc network in which at least some of said wireless terminals can communicate over wireless links in one or several hops with at least some of the other wireless terminals and the location of at least one wireless terminal is determined by measuring the distances between at least two terminals, the method comprising:

measuring in a plurality of said wireless terminals the distances to one-hop neighbors,

sending measured distances to other wireless terminals, and

using the distances measured in at least two terminals to compute in at least one said wireless terminal the position of at least one other wireless terminal.

2. The method of claim 1, wherein said distances between said wireless terminals and their one-hop neighbors are measured from at least one characteristic of one signal transmitted between said wireless terminal and said neighbor.

3. The method of claim 2, wherein said characteristic is the time of arrival of said signal.

4. The method of claim 2, wherein said characteristic is the attenuation of said signal.

5. The method of claim 3, wherein the number of distances measured is greater than the minimum required in order to compute said locations, this redundancy being used for improving the precision with which the location can be determined.

6. The method of claim 1, wherein a history of positions of at least one wireless terminal is stored, said history being used for improving the precision with which the location can be determined.

7. The method of claim 3, wherein each wireless terminal computes the location of a different set of wireless terminals in the network.

8. The method of claim 7, wherein each wireless terminal uses a different local coordinate system in which it computes the location of said set of wireless terminals.

9. The method of claim 8, further comprising a step of choosing a global coordinate system and communicating said global coordinate system to all wireless terminals over said wireless links.

10. The method of claim 8, wherein said local coordinate system is computed in at least some of said wireless terminals by:

detecting all one-hop neighbors of said wireless terminal,

measuring the distance to said one-hop neighbors,

receiving the distance between at least some pairs of said one-hop neighbors,

choosing two neighbors such that the distance between said neighbors is known and larger than zero, and

using said two neighbors to define the local coordinate system of said wireless terminal.

11. The method of claim 9, further comprising a step of translating said location into said global coordinate system.

12. The method of claim 11, wherein the local coordinate system of one of said wireless terminals is elected as global coordinate system and communicated to the other wireless terminals.

13. The method of claim 12, wherein the wireless terminal whose local coordinate system is elected is a fixed wireless terminal.

14. The method of claim 9, wherein the wireless terminal having the lowest speed is determined, the local coordinate system of said wireless terminal being elected as a global coordinate system.

15. The method of claim 9, further comprising:

selecting a reference group of N wireless terminals, wherein the number N of wireless terminals in the group is lower than the total number of wireless terminals in the network,

defining a global coordinate system depending on the position of said wireless terminals within said reference group, and

communicating said global coordinate system to wireless terminals outside said reference group.

16. The method of claim 15, wherein said reference group is selected such that the density of wireless terminals is the highest in the network.

17. The method of claim 9, further comprising a step of recomputing said global coordinate system to adapt it to changes in the topology of the network.

18. The method of claim 2, said method comprising indicating the absolute position of at least three wireless terminals in said network, in order to be able to compute the absolute position of at least one other wireless terminal.

19. The method of claim 2, wherein said wireless terminals communicate with each other over a short range radio protocol, for example Bluetooth, HomeRF or 802.11.

20. The method of claim 1, further comprising a step of routing packets in at least one of said wireless terminals based on its knowledge of its own location and one of that of other wireless terminals.

21. The method of claim 1, wherein said wireless terminals are mobile personal communication devices, said method further comprising a step of exchanging data or voice data with a cellular mobile phone network.

22. The method of claim 1, wherein at least some of said wireless terminals are incorporated in cars, said method further comprising a step of displaying to a driver the distance to another car.

23. The method of claim 1, wherein at least some of said wireless terminals are made of interconnected sensors, said method further comprising a step of detecting the sensors'"'"' displacements.

24. A wireless terminal comprising:

electronic circuit means for directly communicating over a wireless interface with similar wireless terminals and for relaying communications on behalf of other wireless terminals,

distance measuring means for measuring the distance to other wireless terminals, and

computing means for computing the position of at least one other wireless terminal, said location being computed based on said distances and on distance information received from other wireless terminals.

25. The wireless terminal of claim 24, wherein said distances are measured by measuring at least one characteristic of one signal exchanged with said other wireless terminal.

26. The wireless terminal of claim 25, wherein said characteristic is the time of arrival of said signal.

27. The wireless terminal of claim 24, wherein said characteristic is the attenuation of said signal.

28. The wireless terminal of claim 24, further comprising:

means for detecting all one-hop neighbors of said wireless terminal,

receiving means for receiving the distances between at least some pairs of said one-hop neighbors,

means for choosing two neighbors such that the distance between said neighbors is known and larger than zero, and

means for using said two neighbors to define the local coordinate system of said wireless terminal.

29. The wireless terminal of claim 28, further comprising means for translating the position of a wireless terminal in said local coordinate system into a global coordinate system used by other wireless terminals.

30. The wireless terminal of claim 24, further comprising location based routing means for routing packets to another wireless terminal based on the knowledge of said location of other wireless terminals.

31. The wireless terminal of claim 24, comprising a mobile phone part.

32. The wireless terminal of claim 24, wherein said wireless terminals are made of sensors for sensing a physical parameter and sending the value measured to other wireless terminals.

33. The wireless terminal of claim 24, wherein said wireless interface uses a non proprietary short range radio communication protocol, for example Bluetooth, HomeRF or 802.11.