Adaptive wireless sensor network and method of routing data in a wireless sensor network

• US 8,514,760 B2
• Filed: 04/27/2010
• Issued: 08/20/2013
• Est. Priority Date: 04/27/2010
• Status: Active Grant

• Current Assignee: HCL Technologies Limited
• Original Assignee: International Business Machines Corporation
• Inventors: Mukherjee, Amitava
• Primary Examiner(s): Nguyen, Hanh N
• Application Number:
  US12/767,850
• Publication Number:
  US 20110261738A1
• Time in Patent Office: 1,211 Days
• Field of Search: 370/241, 370/242, 370/252, 370/328, 370/329, 370/238, 370/237, 370/351, 370/310, 370/311, 370/389, 370/390, 370/392, 370/338, 370/352, 370230-235, 370/236
• US Class Current: 370/311
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method of routing data in a wireless sensor network, a program product and a wireless sensor network. The method, includes: (a) detecting a temporal event by a source sensor node of a wireless sensor network comprising a multiplicity of sensor nodes; (b) identifying multiple paths from the source sensor node to a sink of the wireless sensor network, the multiple paths consisting of sensor node to sensor node hops; and after (b), (c) using a processor of the source sensor node, optimizing a distribution of data packets to each path of the multiple paths by simultaneously reducing (i) power consumed by sensor nodes in each path of the multiple paths and (ii) a time to transmit the data packets from the source sensor node to the sink.

Claims

1. A method, comprising:

(a) detecting a temporal event by a source sensor node of a wireless sensor network comprising a multiplicity of sensor nodes;

(b) in response to said source sensor detecting said temporal event, said source sensor identifying multiple paths from said source sensor node to a sink of said wireless sensor network, said multiple paths consisting of sensor node to sensor node hops;

after (b), (c) using a processor of said source sensor node, said source node optimizing a distribution of data packets to each path of said multiple paths by simultaneously reducing (i) power consumed by sensor nodes in each path of said multiple paths and (ii) a time to transmit said data packets from said source sensor node to said sink; and

where said optimizing a distribution of data packets includes;

determining power consumption for each sensor node in each path of said multiple paths;

determining power consumed for transmission and reception of data packets over each path of said multiple paths;

determining a time delay for each hop of each path of said multiple paths;

determining a maximum allowable amount of time for transmission of data packets from said source sensor node to said sink;

determining lifespans for each path of said multiple paths based on an amount of power of a sensor node of each path having a least amount of power remaining; and

determining a most stable path based on said lifespans of each path of said multiple paths.

2. The method of claim 1, further including:

after (c), (d) simultaneously transmitting different data packets of said data packets over each path of said multiple paths from said source sensor node to said sink.

3. The method of claim 2, further including:

between (a) and (b), determining if an amount of data to be transmitted from said source sensor node to said sink exceeds a predetermined limit;

if said amount of data exceeds said predetermined limit performing (b), (c) and (d); and

if said amount of data is at or below said predetermined limit determining a single path from said source sensor node to said sink, and transmitting data packets containing said data over said single path from said source sensor node to said sink.

4. The method of claim 1, wherein (c) includes:

initialing an optimization equation and a set of constraints for solutions to said optimization equation;

performing a Lagrangian function to relax said optimization equation using said constraints; and

solving said Lagrangian function for data packet distribution for each path of said multiple paths.

5. The method of claim 4, further including:

using sequential quadratic programming to solve said Lagrangian function.

6. The method of claim 1, wherein said processor optimizes said distribution of data packets using the following algorithm:

Z=Σ

_j(2*Δ

_j*tp_j*H_j*p_j)

with the constraints

Σ

_jΔ

_j=D;

max[(Δ

_j*τ

_j*H_j*p_j]≦

{[D*τ

_stab*H_stab*p_j]+[max[(D/n_j*Δ

_j*H_j*p_j)]}/2; and

2*Δ

_j*tp_j+K_r*max(Δ

_j*τ

_j*H_j*p_j)<

P_jmin; and

where

Z is the objective function;

D is the total data volume to be transmitted;

K_r=n_j*t_j;

K_r is the effective rate of power loss from a node due to processing and sensing (joule/second);

n_j is the number of sensor nodes in the j^th path;

t_j is the time the path is in use for transmitting data packets;

τ

_j=q_j+1/B₁;

τ

_j is the average delay/packet/hop for j^th path (seconds/packet/hop);

q_j is the average queuing delay in j^th path;

B_j is the bit rate of the j^th path (in packets/seconds);

p_j=2*Δ

_j*tp_j*H_j;

p_j is the power consumed in the j^th path;

tp_j is the transmission power/packet/hop for j^th path (joules/packet/hop);

Δ

_j is the number of data packets transmitted over the j^th path;

H_j is the number of hops in the j^th path;

P_jmin is the power remaining to the sensor node with the least amount of remaining power in the j^th path;

τ

_stab is the average delay/packet/hop for the maximum life span path (seconds/packet/hop); and

H_stab is the number of hop counts for the maximum life-span path.

7. The method of claim 1, wherein each sensor node of said set of sensor nodes includes means for charging an onboard battery.

8. The method of claim 7, wherein said means for charging said onboard battery is a solar cell.

9. The method of claim 1, wherein said sinks includes means for charging an onboard battery.

10. The method of claim 9, wherein said means for charging said onboard battery is a solar cell.

29. The method of claim 1, wherein further including:

executing a route discovery algorithm for determining one or more data packet paths from said source sensor node through intervening sensor nodes to said sink on said processor of said source sensor node; and

executing a data packet path optimization algorithm for determining which data packets of said data packets are routed to each of said data packet paths on said processor of said source sensor node.

11. A computer program product, comprising:

a computer useable storage medium having a computer readable program therein, wherein the computer readable program when executed on a computer causes the computer to;

(a) collect information relative to a temporal event detected by a source sensor node of a wireless sensor network comprising a multiplicity of sensor nodes;

(b) in response to said source sensor detecting said temporal event, instruct said source sensor to identify multiple paths from said source sensor node to a sink of said wireless sensor network, said multiple paths consisting of sensor node to sensor node hops;

after (b), (c) after said source sensor detects said temporal event, instruct said source sensor to optimize a distribution of data packets to each path of said multiple paths by simultaneously reducing (i) power consumed by sensor nodes in each path of said multiple paths and (ii) a time to transmit said data packets from said source sensor node to said sink; and

wherein the method step (c) includes;

determining power consumption for each sensor node in each path of said multiple paths;

determining power consumed for transmission and reception of data packets over each path of said multiple paths;

determining a time delay for each hop of each path of said multiple paths;

determining a maximum allowable amount of time for transmission of data packets from said source sensor node to said sink;

determining lifespans for each path of said multiple paths based on an amount of power of a sensor node of each path having a least amount of power remaining; and

determining a most stable path based on said lifespans of each path of said multiple paths.

12. The computer program product of claim 11, the method further including:

after (c), (d) simultaneously transmitting different data packets of said data packets over each path of said multiple paths from said source sensor node to said sink.

13. The computer program product of claim 12, the method further including:

between (a) and (b), determining if an amount of data to be transmitted from said source sensor node to said sink exceeds a predetermined limit;

if said amount of data exceeds said predetermined limit performing (b), (c) and (d); and

if said amount of data is at or below said predetermined limit determining a single path from said source sensor node to said sink, and transmitting data packets containing said data over said single path from said source sensor node to said sink.

14. The computer program product of claim 11, wherein the method step (c) includes:

initialing an optimization equation and a set of constraints for solutions to said optimization equation;

performing a Lagrangian function to relax said optimization equation using said constraints; and

solving said Lagrangian function for data packet distribution for each path of said multiple paths.

15. The computer program product of claim 14, the method further including:

using sequential quadratic programming to solve said Lagrangian function.

16. The computer program product of claim 11, wherein said processor optimizes said distribution of data packets using the following algorithm:

Z=Σ

_j(2*Δ

_j*tp_j*H_j*p_j)

with the constraints

Σ

_jΔ

_j=D;

max[(Δ

_j*τ

_j*H_j*p_j]≦

{[D*τ

_stab*H_stab*p_j]+[max[(D/n_j*Δ

_j*H_j*p_j)]}/2; and

2*Δ

_j*tp_j+K_r*max(Δ

_j*τ

_j*H_j*p_j)<

P_jmin; and

where

Z is the objective function;

D is the total data volume to be transmitted;

K_r=n_j*t_j;

K_r is the effective rate of power loss from a node due to processing and sensing (joule/second);

n_j is the number of sensor nodes in the j^th path;

t_j is the time the path is in use for transmitting data packets;

τ

_j=q_j+1/B_j;

τ

_j is the average delay/packet/hop for j^th path (seconds/packet/hop);

q_j is the average queuing delay in j^th path;

B_j is the bit rate of the j^th path (in packets/seconds);

p_j=2*Δ

_j*tp_j*H_j;

p_j is the power consumed in the j^th path;

tp_j is the transmission power/packet/hop for j^th path (joules/packet/hop);

Δ

_j is the number of data packets transmitted over the j^th path;

H_j is the number of hops in the j^th path;

P_jmin is the power remaining to the sensor node with the least amount of remaining power in the j^th path;

T_stab is the average delay/packet/hop for the maximum life span path (seconds/packet/hop); and

H_stab is the number of hop counts for the maximum life-span path.

17. The computer program product of claim 11, wherein in response to said source sensor detecting said temporal event, instruct said source sensor to:

execute a route discovery algorithm for determining one or more data packet paths from said source sensor node through intervening sensor nodes to said sink on said processor of said source sensor node; and

execute a data packet path optimization algorithm for determining which data packets of said data packets are routed to each of said data packet paths on said processor of said source sensor node.

18. A wireless sensor network, comprising:

a set of sensor nodes, each sensor node of said set of sensor nodes including a sensor, a processor, a memory unit, a battery and a transceiver;

each sensor node of said set of sensor nodes configured to identify multiple paths from said sensor node to a sink of said wireless sensor network in response to detecting a temporal event, each path of said multiple paths comprising sensor node to sensor node hops; and

each sensor node of said set of sensor nodes configured to optimize a distribution of data packets to each path of said multiple paths by simultaneously reducing (i) power consumed by sensor nodes in each path of said multiple paths and (ii) a time to transmit said data packets from said sensor node to said sink;

wherein each sensor node of said sensor nodes is configured to;

determine power consumption for each sensor node in each path of said multiple paths;

determine power consumed for transmission and reception of data packets over each path of said multiple paths;

determine a time delay for each hop of each path of said multiple paths;

determine a maximum allowable amount of time for transmission of data packets from said source sensor node to said sink;

determine lifespans for each path of said multiple paths based on an amount of power of a sensor node of each path having a least amount of power remaining; and

determine a most stable path based on said lifespans of each path of said multiple paths.

19. The wireless sensor network of claim 18, each sensor node of said set of sensor nodes further including:

a processor for determining if an amount of data to be transmitted from said source sensor node to said sink exceeds a predetermined limit and if said amount of data is at or below said predetermined limit means for determining a single path from said source sensor node to said sink; and

a transceiver for transmitting data packets containing said data over said single path from said source sensor node to said sink.

20. The wireless sensor network of claim 18, each sensor node of said set of sensor nodes further including:

a multipath routing algorithm for finding multiple paths from said sensor node to said sink; and

an optimization algorithm for optimizing said distribution of data packets stored as code executable in each memory of each sensor node of said set of sensor nodes, said optimization algorithm describing an optimization equation and constraints on said optimization equation.

21. The wireless sensor network of claim 20, each sensor node of said set of sensor nodes further including:

a processor for performing a Lagrangian function to relax said optimization equation using said constraints and for solving said Lagrangian function for data packet distribution for each path of said multiple paths using sequential quadratic programming.

22. The wireless sensor network of claim 18, wherein each sensor node of said set of sensor nodes includes a processor for determining:

power consumption for each sensor node in each path of said multiple paths;

power consumed for transmission and reception of data packets over each path of said multiple paths;

a time delay for each hop of each path of said multiple paths;

a maximum allowable amount of time for transmission of data packets from said source sensor node to said sink;

a lifespan for each path of said multiple paths based on an amount of power a sensor node with a least amount of power remaining; and

a most stable path based on said lifespans of each path of said multiple paths.

23. The wireless sensor network of claim 18, further including:

a base station wirelessly connected to one or more of said set of sensor nodes;

or

a gateway node wirelessly connected to one or more of said set of sensor nodes, said gateway node wire connected to said base station; and

wherein said base station is a general purpose computer and said gateway node has greater power reserves, greater transmit range or both greater power reserves and greater transmit range than each sensor node of said set of sensor nodes.

24. The wireless sensor network of claim 18, wherein each sensor node of said set of sensor nodes includes means for charging an onboard battery.

25. The wireless sensor network of claim 24, wherein said means for charging said onboard battery is a solar cell.

26. The wireless sensor network of claim 18, wherein said sinks includes means for charging an onboard battery.

27. The wireless sensor network of claim 26, wherein said means for charging said onboard battery is a solar cell.

28. The wireless sensor network of claim 18, wherein each sensor node of said set of sensor nodes includes:

a route discovery algorithm stored in said memory unit, said route discovery algorithm for determining data packet paths from said sensor node through intervening sensor nodes to said sink; and

a data packet path optimization algorithm stored in said memory unit, said data packet path optimization algorithm for determining which data packets of said data packets are routed to each of said data packet paths.