Method of transmitting data with minimum energy consumption in a wireless sensor network

• US 20060178150A1
• Filed: 02/06/2006
• Published: 08/10/2006
• Est. Priority Date: 02/04/2005
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Hyung-Seok
• Application Number:
  US11/348,497
• Publication Number:
  US 20060178150A1
• Time in Patent Office: Days
• US Class Current: 455/445
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Disclosed is a method of configuring a tree when a new sink is added in a wireless sensor network. The method includes selecting a first sensor node via which a path can run to a new sink with the smallest delay cost, if the new sink requesting the sensed information as a sink within an existing tree is added; thereafter determining whether a path connecting the first sensor node directly(direct path) to the new sink has minimal energy consumption, after selecting the first sensor node. A second sensor node via which a path can run to the new sink with the minimal energy consumption, if the direct path does not have the minimal energy consumption. Therefore, an optimal tree having the minimal energy consumption can be configured.

Claims

1. A method of configuring a tree when a new sink is added in a wireless sensor network, comprising the steps of:

selecting a first sensor node via which a path can run to the new sink with a smallest delay cost, if the new sink requesting the sensed information as a sink within an existing tree is added;

determining whether a path connecting the first sensor node directly to the new sink has minimal energy consumption, after selecting the first sensor node; and

selecting a second sensor node via which a path can run to the new sink with the minimal energy consumption, if the direct path does not have the minimal energy consumption,

whereby an optimal tree having the minimal energy consumption is configured.

2. The method of claim 1, wherein the first sensor node is one of sensor nodes serving as branch nodes or leaf nodes in the existing tree.

3. The method of claim 1, wherein the first sensor node selecting step comprises the steps of:

selecting a set of child nodes satisfying a predetermined condition, upon receipt of a message for tree connection;

selecting a child node via which a path can run to the new sink with the smallest delay cost from the set of child nodes;

comparing the delay cost from the selected child node to the new sink with the delay cost from the sensor node currently having the message for tree connection to the new sink; and

connecting the new sink to the sensor node receiving the message, if the delay cost from the selected child node to the new sink is equal to or greater than the delay cost from the sensor node currently having the message for tree connection to the new sink.

4. The method of claim 3, wherein the message for tree connection includes the address of the new sink and a sum of delay costs between a source sensor node which generated the sensed information to the sensor node currently having the message for tree connection.

5. The method of claim 3, wherein delay cost is calculated using a distance between sensor nodes to estimate delay between the sensor nodes.

6. The method of claim 3, wherein the predetermined condition is defined by

S_i+q{d(r[i],h)+d(h,a_m)}<

Q_m

wherein a_m is the new sink, r[i] is the sensor node currently having the message for tree connection, S_i is a sum of delay costs from the source sensor node to the sensor node r[i] along the tree, Q_m is a maximum delay limit between the source sensor node and the new sink a_m, q is an average delay per unit distance (sec/m), h is the selected child node, d(r[i], h) is the distance between the sensor node r[i] and the child node h, and. d(h, a_m) is the distance between the child node h and the new sink a_m.

7. The method of claim 3, further comprising:

calculating a sum of delay costs from the source sensor node to the selected child node, if the delay cost from the child node to the new sink is less than the delay cost from the sensor node currently having the message to the new sink;

updating the delay cost sum in the message for tree connection with the calculated delay cost sum; and

sending the updated message for tree connection to the child node.

8. The method of claim 7, wherein the delay cost sum is computed by

S_i+1=S_i+qd(r[i],r[i+1])

wherein r[i] is the sensor node currently having the message for tree connection, r[i+1] is the selected child node, S_i is a sum of delay costs from the source sensor node to the sensor node r[i] along the tree, S_i+1 is the sum of delay costs from the source sensor node to the selected child node r[i+1] along the tree, and qd(r[i],r[i+1]) is a delay cost from the sensor node r[i] to the selected child node r[i+1].

9. The method of claim 1, wherein the step of determining whether a path connecting the first sensor node directly to the new sink has minimal energy consumption is determined by

U₁>

U₂, where U₁=d(g,m)+d(g,c),U₂=U(k,c)=d(g,k)+d(k,m)+d(k,c), and

g is the first sensor node, m is the new sink, c is a child node of the first sensor node, k is any neighbor sensor node of the first sensor node g, d(g,m)+d(g,c) is a sum of the distance from the first sensor node g to the new sink m and a distance from the first sensor node g to the child node c, and d(g,k)+d(k,m)+d(k,c) is a sum of the distance from the first sensor node g to the child node c via the neighbor sensor node k and a distance from the first sensor node g to the child node c via the neighbor sensor node k.

10. The method of claim 9, further comprising determining the path connecting the first sensor node directly to the new sink is an optimal path, if U₁ is less that or equal to U₂ is not satisfied.

11. The method of claim 1, wherein the second sensor node selecting step comprises the steps of:

selecting a set of neighbor sensor nodes satisfying a predetermined condition, upon receipt of a message for tree connection;

selecting a neighbor sensor node via which a path can run to the new sink and to an existing sink connected to the first sensor node with the smallest delay cost from the set of neighbor sensor nodes;

comparing the energy cost of the selected neighbor sensor node with the energy cost of paths between the sensor node receiving the message for tree connection and the new sink and between the sensor node receiving the message for tree connection and the existing sink; and

selecting the sensor node receiving the message for tree connection as the second sensor node if the energy cost of the sensor node receiving the message for tree connection is less than the energy cost of the selected neighbor sensor node.

12. The method of claim 11, wherein the predetermined condition is satisfied if the sensed information can be routed from the source sensor node to the new sink via the neighbor sensor node, and a new path is available from the first sensor node to the existing sink via the neighbor sensor node.

13. The method of claim 12, wherein it is determined whether the sensed information can be routed from the source sensor node to the new sink via the neighbor sensor node by

$S_g+d$

( g , k ) + d ⁡

( k , m ) ≤

Q m q ⁡

[ ri ]

where S_g is a sum of energy costs from the source sensor node to the first sensor node g along the tree, d(g,k)+d(k,m) is the energy cost from the first sensor node g to the new sink m via the neighbor sensor node k, and

$\frac{Q_m}{q}$

is a maximum energy limit between the source sensor node and the new sink m, q is an average delay per unit distance (sec/m).

14. The method of claim 12, wherein it is determined whether a new path is available from the first sensor node to the existing sink via the neighbor sensor node by

$d$

( g , k ) + d ⁡

( k , c ) - d ⁡

( g , c ) ≤

w c q ,

where d(g,k)+d(k,c) is the energy cost from the first sensor node g to a child node c of the first sensor node via the neighbor sensor node k, d(g,c) is the energy cost from the first sensor node g to the child node c, and

$\frac{w_c}{q}$

is the difference between a maximum energy limit and the energy cost from the child node c to a sink connected to the child node c, q is an average delay per unit distance (sec/m)

15. The method of claim 11, wherein the energy cost of the selected neighbor sensor node is computed by

U₂=U(k,c)=d(g,k)+d(k,m)+d(k,c),

where g is the first sensor node, k is the selected neighbor sensor node, m is the new sink, c is a child of the first sensor node, U₂ is the energy cost of the selected neighbor sensor node, d(g,k) is an energy cost from the first sensor node g to the neighbor sensor node k, d(k,m) is an energy cost from the neighbor sensor node k to the new sink m, and d(k,c) is an energy cost from the neighbor sensor node k to the child node c.

16. The method of claim 11, further comprising setting the selected neighbor sensor node as a sensor node to receive the message and sending the message to the selected neighbor sensor node, if the energy cost of the selected neighbor sensor node is less than the energy cost of the sensor node receiving the message.

17. The method of claim 11, wherein the message for tree connection includes an address of the new sink.

18. The method of claim 1, further comprising connecting the new sink directly to the first sensor node, if the direct path has the minimal energy consumption.