Method and system for managing energy in sensor network environment using spanning tree

• US 7,961,651 B2
• Filed: 12/27/2007
• Issued: 06/14/2011
• Est. Priority Date: 01/11/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Kyung Mi, Hwang, Seong Taek, Shin, Ji Soo, Suh, Chang Jin, Cho, Jae Hun, Kim, Hoon
• Primary Examiner(s): Moore, Jr.; Michael J
• Application Number:
  US11/964,763
• Publication Number:
  US 20080172191A1
• Time in Patent Office: 1,265 Days
• Field of Search: 370/338, 370/408, 370/352, 370/256, 370/221, 370/401, 370/337, 370/351, 370/328, 370/310, 370/400, 709/224, 709/248
• US Class Current: 370/256
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

A method for managing energy in a sensor network environment using a spanning tree includes the steps of collecting amount of remaining energy of nodes at a predetermined cycle by a base station in a region having a number of clusters a number of nodes forming a spanning tree in each cluster; assigning a number of links for connecting the nodes to each cluster; determining a maximum number of allowable links of the nodes; and updating the spanning tree based on the maximum number of allowable links.

Claims

1. A method of managing energy in a sensor network environment using a spanning tree, the method comprising:

collecting an amount of remaining energy of each of a plurality of nodes in the sensor network at a predetermined cycle by a base station in a region having a number of clusters, a number of nodes forming a spanning tree in each cluster;

assigning a number of links for connecting the nodes to each cluster;

determining a maximum number of allowable links of the nodes according to the amount of remaining energy of each node; and

updating the spanning tree based on the maximum number of allowable links;

wherein the maximum number of allowable links is a predetermined percentage of free links; and

wherein the percentage of free links is determined based on a standard deviation of distribution of the amount of remaining energy of the nodes.

2. The method as claimed in claim 1, further comprising:

setting up the predetermined cycle for updating the spanning tree; and

calculating amount of energy necessary to add a node to a different node during the predetermined cycle.

3. The method as claimed in claim 2, wherein the predetermined cycle is at least one of, a round cycle, the node transmitting data to the base station at the round cycle, and a cycle obtained by dividing entire sensor network life at a predetermined ratio.

4. The method as claimed in claim 1, wherein the cluster has a size corresponding to ⅕

- 1/10 of a size of the region.

5. The method as claimed in claim 1, wherein the assigning a number of links comprises:

determining a percentage of free links in the cluster by the base station; and

determining a link number by adding a number of nodes located at the cluster and a percentage of free nodes located at the cluster together.

6. The method as claimed in claim 5, which further comprises:

determining the link number by rounding down a total when the total has a decimal value.

7. The method as claimed in claim 1, wherein the percentage of free links corresponds to 10%-20% of a total number of allowable links of all, nodes arranged in the cluster.

8. The method as claimed in claim 1, wherein the step of determining a maximum number of allowable links of the nodes comprises:

sorting nodes located at the cluster according to a relative rank of amount of remaining energy of the nodes;

calculating a standard decimal number based on the relative rank; and

determining the maximum number of allowable links based on the standard decimal number and the percentage of free links.

9. The method as claimed in claim 8, wherein the standard decimal number P[i] of the node is (relative rank-0.5)/node number of cluster where i refers to node number.

10. The method as claimed in claim 9, wherein the maximum number of allowable links is determined based on a table for determining the maximum number of allowable links, the table having been prepared based on the standard decimal number and the percentage of free links.

11. The method as claimed in claim 1, wherein the determining a maximum number of allowable links of the nodes comprises:

calculating the maximum number of allowable links D[i] by as

min(4, max(1, integer((E1[i]−

m[j])/(T_c×

E_r)))),

wherein D[i] refers to the maximum number of allowable link,

min(x) outputs x value when equal to or smaller than the x value,

max(y) outputs y value when equal to or larger than the y value,

E[i] refers to amount of remaining energy of i^th node,

m[j] refers to a variable,

T_c refers to a cycle,

E_r refers to energy necessary to add a node to a different node,

L[j] refers to a link number assigned to the cluster, \ integer(k) rounds off k so as to obtain an integer, and

i_k(j) refers to a number of a node belonging to a cluster;

calculating second value as \Σ

_k=1,2,N[j]D[i_k(j)]−

2×

L[j];

increasing the m[j] by a predetermined amount when the second calculated value is larger than 0 and repeating the calculation of the maximum value; and

decreasing the m[j] by a predetermined amount when the second calculated value is smaller than 0 and repeating the calculation of the maximum value.

12. The method as claimed in claim 1, wherein the spanning tree is updated by constructing a tree based on, consideration of the amount of remaining energy and location of nodes distributed in the cluster.

13. The method as claimed in claim 1, wherein the updated spanning tree has a link number equal to or smaller than the maximum number of allowable links in a previous spanning tree.

14. A system for managing energy in a sensor network environment using a spanning tree, the system comprising:

a plurality of nodes forming a spanning tree in each region based on link connection, the nodes updating the spanning tree at a predetermined cycle; and

a base station for;

setting up the predetermined cycle,

collecting amount of remaining energy of the nodes and distributed location of the nodes at the predetermined cycle so as to determine a maximum number of allowable links of the nodes,

calculating the spanning tree based on the determined maximum number of allowable links according to the amount of remaining energy of each node, and

transmitting a calculation result to the nodes;

wherein the maximum number of allowable links is determined by sorting nodes located at a cluster according to a relative rank of amount of remaining energy of the nodes and referring to a predetermined percentage of free links determined based on standard deviation of distribution of amount of remaining energy of the nodes and a standard decimal number calculated based on the relative rank.

15. The system as claimed in claim 14, wherein the base station comprises a processor executing code stored on a machine readable storage medium for:

determining the maximum number of allowable links as

min(4, max(1, integer((E1[i]−

m[j])/(T_c×

E_r)))),

wherein D[i] refers to the maximum number of allowable link,

min(x) outputs x value when equal to or smaller than the x value,

max(y) outputs y value when equal to or larger than the y value,

E[i] refers to amount of remaining energy of i^th node,

m[j] refers to a variable, T_c refers to a cycle,

E_r refers to energy necessary to add a node to a different node,

L[j] refers to a link number assigned to the cluster,

integer(k) rounds off k so as to obtain an integer, and

i_k(j) refers to a number of a node belonging to a cluster;

calculation of the calculated values by using equation

Σ

<sub>k×

1,2,N[j]</sub>D[i_k(j)]−

2×

L[j];

increase of the m[j] by a predetermined amount when the secondarily calculated value is larger than 0 and repetition of the primary calculation; and

decrease of the m[j] by a predetermined amount when the secondarily calculated value is smaller than 0 and repetition of the primary calculation.

16. A base station for managing energy in a sensor network environment, said base station comprising:

a processor in communication with a memory, the processor executing code stored on a machine readable storage medium for;

collecting information regarding an amount of remaining energy in each of a plurality of nodes and their respective location in said network at a predetermined cycle so as to determine a maximum number of allowable links of the nodes,

calculating a spanning tree based on the determined maximum number of allowable links according to the amount of remaining energy of each node, and

transmitting a calculation result to each of the nodes;

wherein said maximum number of allowable links is determined as;

min(4, max(1, integer((E1[i]−

m[j])/(T_c×

E_r)))),

wherein D[j] refers to the maximum number of allowable link,

min(x) outputs x value when equal to or smaller than the x value,

max(y) outputs y value when equal to or larger than the y value,

E[i] refers to amount of remaining energy of i^th node,

m[i] refers to a variable T_c refers to a cycle,

E_r refers to energy necessary to add a node to a different node,

L[j] refers to a link number assigned to the cluster,

integer(k) rounds off k so as to obtain an integer, and

i_k(j) refers to a number of a node belonging to a cluster;

calculation of the calculated values by using equation

Σ

<sub>k×

1,2 N[j]</sub>D[i_k(j)]−

2×

L[j];

increase of the m[j] by a predetermined amount when the secondarily calculated value larger than 0 and repetition of the primary calculation; and

decrease of the m[j] by a predetermined amount when the secondarily calculated value is smaller than 0 and repetition of the primary calculation.