System, medium, and method for estimating distance in communication system having nodes

• US 20050271057A1
• Filed: 06/06/2005
• Published: 12/08/2005
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Bui, Duy-bach, Kim, Ji-tae, Kim, Dae-young
• Granted Patent: US 7,623,512 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method, medium, and system estimating a location of a node, whose location is unknown, in a communication system including both nodes having known locations and nodes having unknown locations. A first packet is transmitted and received between nodes having known locations, via a node having an unknown location to be estimated. A second packet, which contains a distance function coefficient acquired using first information and second information included in the received first packet, is transferred to the node having the unknown location to be estimated. The unknown location is then estimated using the received distance function coefficient.

Claims

1. A method for estimating an unknown location of a first node in a communication system including nodes having known locations and nodes having unknown locations, comprising:

transmitting and receiving first packets between nodes having known locations via the first node;

sending a second packet to the first node, the second packet containing a distance function coefficient acquired using first information and second information included in at least one of the first packets; and

estimating the unknown location of the first node using the distance function coefficient.

2. The method of claim 1, wherein the first information is a sum of transmission distances of a first packet and the second information is a hop counter.

3. The method of claim 2, wherein the initial transmission of a first packet is performed by a node knowing its location.

4. The method of claim 3, wherein the initial setting of the first information is zero and the initial setting of the second information is zero.

5. The method of claim 1, wherein an initiating sending of the second packet is performed only by a node knowing its location.

6. The method of claim 1, wherein the first node calculates and stores distances to one-hop nodes.

7. The method of claim 1, wherein the one first packet contains location information of a node that transmitted the one first packet.

8. The method of claim 7, wherein the first information is a packet transfer distance and the second information is a hop counter with respect the packet transfer.

9. The method of claim 8, wherein a node relaying the one first packet updates the first information and the second information of the one first packet, and transfers the updated first packet with the updated first and second information.

10. The method of claim 9, wherein, if at least three first packets are received, distance function coefficients are calculated in accordance with the following equation:

$\left[\begin{array}{c}{d}_1\\ d_2\\ \mathrm{\dots <br><br>}\\ d_n\end{array}\right]=\left(\begin{array}{ccc}{\mathrm{sd}}_1& h_1& 1\\ {\mathrm{sd}}_2& h_2& 1\\ \mathrm{\dots <br><br>}& \mathrm{\dots <br><br>}& \mathrm{\dots <br><br>}\\ {\mathrm{sd}}_n& h_n& 1\end{array}\right)<br><br>\left[\begin{array}{c}{\mathrm{\alpha <br><br>}}_0\\ {\mathrm{\alpha <br><br>}}_1\\ {\mathrm{\alpha <br><br>}}_2\end{array}\right],$

wherein n is a natural number equal to or greater than 3, d is an actual distance between a node transmitting the one of the three first packets and a node receiving the one of the three first packets and calculated using location information, sd is a corresponding first information, h is corresponding second information, and α

₀, α

₁, α

₂ are distance function coefficients.

11. The method of claim 10, wherein the estimating of the unknown location further comprises:

receiving at least three second packets;

calculating distances to nodes transmitting the second packets by use of distance function coefficients contained in the received second packets and first and second information with respect to the nodes transmitting the second packets; and

estimating the unknown location using the unknown locations of and the distances to the nodes transmitting the second packet.

19. A medium comprising computer readable code implementing the method of claim 1.

12. A system estimating an unknown location of a second node using a known location of a first node, both in a communication system, comprising:

the first node generating a second packet containing a distance function coefficient calculated using first information and second information contained in a first packet received via the second node; and

the second node estimating its location using the distance function coefficient, as received by the second node in the second packet.

13. The system of claim 12, wherein the second node calculates and stores distances to one-hop nodes.

14. The system of claim 12, wherein the first node transfers the first packet, containing location information of the first node, to another node having a known location.

15. The system of claim 14, wherein the first information is a packet transfer distance and the second information is a hop counter with respect to the packet transfer.

16. The system of claim 15, wherein a node relaying the first packet updates the first information and the second information of the first packet, and transfers the updated first packet with the updated first and second information.

17. The system of claim 16, wherein the first node calculates distance function coefficients if at least three first packets are received in accordance with the following equation:

$\left[\begin{array}{c}{d}_1\\ d_2\\ \mathrm{\dots <br><br>}\\ d_n\end{array}\right]=\left(\begin{array}{ccc}{\mathrm{sd}}_1& h_1& 1\\ {\mathrm{sd}}_2& h_2& 1\\ \mathrm{\dots <br><br>}& \mathrm{\dots <br><br>}& \mathrm{\dots <br><br>}\\ {\mathrm{sd}}_n& h_n& 1\end{array}\right)<br><br>\left[\begin{array}{c}{\mathrm{\alpha <br><br>}}_0\\ {\mathrm{\alpha <br><br>}}_1\\ {\mathrm{\alpha <br><br>}}_2\end{array}\right],$

wherein n is a natural number equal to or greater than 3, d is an actual distance between a node transmitting one of the three first packets and a node receiving the one of the three first packets and calculated using location information, sd is a corresponding first information, h is a corresponding second information, and α

₀, α

₁, α

₂ are distance function coefficients.

18. The system of claim 17, wherein the second node, when at least three second packets are received by the second node, calculates distances to nodes transmitting the second packets by use of distance function coefficients contained in the received second packets and stored first and second information with respect to the nodes transmitting the second packets, and

the second node estimates the unknown location using locations of and the distances to the nodes transmitting the second packets.

20. A sensor network, comprising:

a base node; and

a plurality of nodes communicating sensory data to the base nodes based on locations of each of the plurality of nodes, using the system of estimating an unknown location of claim 12 for nodes whose location is unknown.