Method and system for locating sensor node in sensor network using distance determining algorithm

• US 7,855,684 B2
• Filed: 11/14/2008
• Issued: 12/21/2010
• Est. Priority Date: 11/15/2007
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ahn, Sae Young, Kim, Bum Jin, Ryu, Jehyok, Choi, Hyo Hyun, Kim, Sun Gi, An, Sun Shin
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Galt; Cassi
• Application Number:
  US12/270,912
• Publication Number:
  US 20090128412A1
• Time in Patent Office: 767 Days
• Field of Search: 342/451, 342/464
• US Class Current: 342/464
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

For a sensor network having reference nodes and sensor nodes, A method and apparatus using a distance determining algorithm for a sensor network having reference nodes and sensor nodes. A distance determining algorithm is executed to determine an adequate distance between reference nodes within a preset error range, and a position location table is created. A sensor node sends a location information request to reference nodes, receives the position location table and location information from the reference nodes, and computes the coordinates of its position. Alternatively, without requesting transmission of the position location table, the sensor node may receive calculated coordinates of its position directly from a reference node.

Claims

1. A position locating system for a sensor network, comprising:

a plurality of reference nodes, each reference node of said plurality of reference nodes having self-positional information regarding a respective position thereof; and

a sensor node having a position location table,

wherein each reference node comprises;

a control unit for generating, in response to a location information request signal, a location information; and

a radio frequency (RF) communication unit for receiving a location information request signal and for forwarding the received location information request signal to the control unit, controlling transmission power, and sending the generated location information in return,

wherein the sensor node comprises;

a control unit for generating a coordinate request signal, analyzing transmit power levels extracted from location information from reference nodes, and for calculating coordinates of a position of the sensor node using the position location table; and

an RF communication unit for transmitting the coordinate request signal, and for receiving location information and forwarding the location information to the control unit,

wherein the position location table is formed by providing a grid of a preset number of vertical and horizontal lines corresponding to a square area defined by an arrangement of the plurality of reference nodes;

wherein measured distances from each intersection point in the grid to each of the reference nodes, respectively correspond to transmit power levels;

wherein intersection points sorted according to transmit power level patterns are arranged into sorted groups in which each particular group has a middle point of those intersection points belonging to the particular group; and

error calculating means for calculating errors for all groups to determine whether a largest group error is within a desired error boundary.

2. The position locating system of claim 1, wherein when the largest group error is not within the desired error boundary, a distance between reference nodes is increased for repeated execution.

3. The position locating system of claim 1, wherein the reference nodes are arranged to form a square.

4. The position locating system of claim 1, wherein the error of a particular group is equal to a longest one of distances between the middle point of the group and intersection points belonging to the particular group.

5. The position locating system of claim 1, wherein the location information comprises:

a node distance from each reference node to the sensor node and maximum transmission distances by transmit power levels; and

reference node data including transmit power data and absolute coordinate data.

6. The position locating system of claim 1, wherein the control unit of the sensor node finds four nearest reference nodes forming a square on the basis of location information from multiple reference nodes.

7. The position locating system of claim 6, wherein the control unit of the sensor node is configured for finding a group in the position location table that corresponds to transmit power levels of a four nearest reference nodes, and said sensor node is configured for obtaining its own coordinates by adding together coordinates of a sensor position corresponding to the group found in the position location table and absolute coordinates of one of the four nearest reference nodes having a smallest absolute coordinate value (x, y).

8. The position locating system of claim 7, wherein the control unit of a reference node controls a transmission operation to send information regarding a node distance from each reference node to the sensor node and maximum transmission distances by transmit power levels and reference node information when a random backoff time expires after reception of a location information request signal.

9. The position locating system of claim 1, wherein said sensor node receives the position location table from a particular reference node of the plurality of reference nodes.

10. A position locating method for a sensor network having reference nodes and at least one sensor node, comprising:

transmitting, by the sensor node, a location information request signal;

transmitting, by each of neighbor reference nodes in response to reception of the location information request signal, a position location table, information on a node distance from each reference node to the sensor node and maximum transmission distances by transmit power levels, and transmitting transmit power data and absolute coordinate data while valving transmission power; and

calculating, by the sensor node, a location of the sensor node using the position location table and transmit power levels of the reference nodes,

wherein the position location table is created using a procedure comprising;

forming a grid of a preset number of vertical and horizontal lines corresponding to a square area defined by plural reference nodes;

measuring distances from each intersection point in the grid to the reference nodes, and finding transmit power levels corresponding to the measured distances;

sorting intersection points according to transmit power level patterns into groups, and finding, for each group, a middle point of those intersection points belonging to the group; and

calculating errors for all groups, and checking whether the largest group error is within a desired error bound.

11. The position locating method according to claim 10, wherein the procedure further comprises increasing, when the largest group error is not within the desired error bound, a distance between reference nodes for repeated execution of the procedure.

12. The position locating method of claim 10, wherein calculating, by the sensor node, a location of the sensor node comprises:

finding a group in the position location table corresponding to transmit power levels of the reference nodes; and

adding coordinates of a sensor position corresponding to the found group and absolute coordinates of one of the reference nodes having the smallest absolute coordinates (x, y) together.

13. The position locating method of claim 12, wherein the reference nodes are arranged to form a square.

14. A position locating system for a sensor network, comprising:

a plurality of reference nodes, each reference node including self-positional information of a position thereof and having a position location table; and

a sensor node,

wherein each reference node comprises;

a control unit for generating, in response to a location information request signal from the sensor node, location information, and for calculating, in response to a coordinate request signal from the sensor node, coordinates of a position of the sensor node; and

a radio frequency (RF) communication unit for receiving a location information request signal or a coordinate request signal from the sensor node and forwarding the received signal to the control unit, controlling transmission power, for sending the generated location information in return for the location information request signal, and for sending the coordinates of the position of the sensor node in return for the coordinate request signal,

wherein the sensor node comprises;

a control unit for generating a location information signal or a coordinate request signal; and

an RF communication unit for transmitting the location information signal or coordinate request signal, and for receiving location information and forwarding the location information to the control unit,

wherein the position location table is formed by providing a grid of a preset number of vertical and horizontal lines corresponding to a square area defined by an arrangement of plural reference nodes;

wherein measured distances from each intersection point in the grid to each of the reference nodes, respectively correspond to transmit power levels;

wherein intersection points are sorted according to transmit power level patterns and are arranged into groups, in which each particular group has a middle point of those intersection points belonging to the particular group; and

error calculating means for calculating errors for all groups to determine whether a largest group error is within a desired error boundary.

15. The position locating system of claim 14, when the largest group error is not within the desired error boundary, a distance between reference nodes is increased for repeated execution.

16. The position locating system of claim 14 wherein the reference nodes are arranged to form a square.

17. The position locating system of claim 14, wherein the error of a group is equal to the longest one of distances between the middle point of the group and intersection points belonging to the group.

18. The position locating system of claim 14, wherein the location information comprises:

a node distance from each reference node to the sensor node and maximum transmission distances by transmit power levels; and

reference node information including transmit power data and absolute coordinate data.

19. The position locating system of claim 18, wherein the control unit of each reference node finds four nearest reference nodes forming a square on the basis of location information from multiple reference nodes.

20. The position locating system of claim 19, wherein the control unit of each reference node finds a group in the position location table corresponding to transmit power levels of the four nearest reference nodes, and obtains its own coordinates by adding coordinates of a sensor position corresponding to the found group and absolute coordinates of one of the four reference nodes having the smallest absolute coordinates (x, y) together.

21. A position locating method for a sensor network having reference nodes and at least one sensor node, comprising:

transmitting, by the sensor nod;

a location information request signal;

transmitting, by each of neighbor reference nodes in response to reception of the location information request signal, information on a node distance from each reference node to the sensor node and maximum transmission distances by transmit power levels, and transmitting transmit power data and absolute coordinate data while varying transmission power

transmitting, by the sensor node, a coordinate request signal carrying information on transmit power levels of the reference nodes; and

calculating, by a reference node receiving the coordinate request signal, a location of the sensor node using the transmit power levels of the reference nodes and a position location table, and sending coordinates of the calculated location,

wherein the position location table is created using a procedure comprising;

forming a grid of a preset number of vertical and horizontal lines corresponding to a square area defined by plural reference nodes;

measuring distances from each intersection point in the grid to the reference nodes, and finding transmit power levels corresponding to the measured distances;

sorting intersection points by according to transmit power level patterns into groups, and finding, for each group, a middle point of those intersection points belonging to the group; and

calculating errors for all groups, and checking whether the largest error is within a desired error bound.

22. The position locating method of claim 21, wherein calculating, by a reference node, a location of the sensor node comprises:

finding a group in the position location table corresponding to transmit power levels of the reference nodes; and

adding coordinates of a sensor position corresponding to the found group and absolute coordinates of one of the reference nodes having the smallest absolute coordinates (x, y) together.

23. The position locating method of claim 21, wherein the reference nodes are arranged to form a square.