Self-organization of sensor networks using ant colony optimization

• US 20060092913A1
• Filed: 10/29/2004
• Published: 05/04/2006
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Ademco Inc. (Resideo Technologies, Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Joseph, Sindhu, Kumar, Ashwin
• Granted Patent: US 7,693,049 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and a method for organizing optimal paths in a sensor network. Optimal paths are determined based on an objective function that balances the performance and energy consumption of sensor nodes. Each sensor node stores and updates pheromone values and aging factors associated with each of its neighbor nodes. The pheromone values provide an indication of the speed of a given path, while the aging factor represents the use. Paths are compared using these variables and an optimal path is selected on each transfer so that the load is spread across a variety of sensor nodes, increasing network life.

Claims

1. A method comprising:

receiving a message;

updating a pheromone value and an aging factor associated with the message; and

transmitting the message.

2. The method of claim 1 wherein the message includes a request for sensor data.

3. The method of claim 1 wherein the message includes sensor data.

4. The method of claim 1 wherein the pheromone value is updated by the function P_i=(1+ρ

)P_i;

P_i is the pheromone value; and

ρ

is a constant.

5. The method of claim 1 wherein updating includes initializing the pheromone value and the aging factor and associating them with a source of the message.

6. The method of claim 1 wherein the pheromone value and the aging factor are associated with a source of the message.

7. The method of claim 1 wherein the pheromone value and the aging factor are associated with a source of the message in a tuple containing the source of the message, the pheromone value and the aging factor.

8. The method of claim 7 wherein the tuple is contained in a list of at least one tuple associated with an interest.

9. The method of claim 1 further comprising:

decreasing the pheromone value at periodic intervals.

10. The method of claim 9 wherein the pheromone value is decreased by the function P_i=(1−

ρ

)P_if(t);

P_i is the pheromone value;

ρ

is a constant; and

f(t) is a function of time.

11. The method of claim 1 wherein transmitting includes determining a destination to transmit the message.

12. The method of claim 1 wherein transmitting includes determining a destination to transmit the message using an objective function.

13. The method of claim 12 wherein the objective function is

$\alpha$

⁢

 

⁢

f ⁡

( P ) + β

⁢

1 A ;

α and

β

are constants;

f(P) is a function of the pheromone value; and

A is the aging factor.

14. The method of claim 1 further comprising:

updating at least one additional pheromone value and at least one additional aging factor after transmitting the message.

15. The method of claim 14 wherein the at least one additional pheromone value and the at least one additional aging factor are associated with at least one destination of the message.

16. The method of claim 1 further comprising:

modifying the message before transmitting the message.

17. The method of claim 16 further comprising:

obtaining sensor data before modifying the message; and

modifying the message includes adding the sensor data to the message.

18. A method implemented by a node in a network of nodes for organizing the network, the method comprising:

scanning for at least one neighbor node; and

updating at least one pheromone value and at least one aging factor associated with the scanned at least one neighbor node.

19. A node comprising:

means for storing at least one pheromone value and at least one aging factor;

means for receiving a message; and

means for transmitting the message.

20. The node of claim 19 wherein the message includes a request for sensor data.

21. The node of claim 19 wherein the message includes sensor data.

22. The node of claim 19 further comprising:

means for sensing at least one event; and

means for modifying the message to include the at least one sensed event.

23. The node of claim 19 wherein the means for storing the at least one pheromone value and at least one aging factor includes a node data structure having a list of at least one interest;

each of the at least one interests is associated with a list of tuples, the list of tuples either being empty or containing at least one tuple; and

each of the at least one tuples contains a neighbor node, one of the at least one pheromone values and one of the at least one aging factors.

24. The node of claim 19 further comprising:

means for determining a destination to transmit the message.

25. The node of claim 24 wherein determining the destination includes selecting the destination based on the at least one pheromone value and the at least one aging factor.

26. The node of claim 24 wherein determining the destination includes selecting the destination based on the at least one pheromone value and the at least one aging factor using an objective function.

27. The node of claim 26 wherein the objective function is

$\alpha$

⁢

 

⁢

f ⁡

( P ) + β

⁢

1 A ;

α and

β

are constants;

f(P) is a function of the at least one pheromone value; and

A is the at least one aging factor.

28. The node of claim 19 further comprising:

means for scanning for at least one neighbor node at periodic intervals; and

means for updating the at least one pheromone value and the at least one aging factor based on the at least one neighbor node.

29. The node of claim 19 further comprising:

means for updating the at least one pheromone value and the at least one aging factor.

30. The node of claim 29 wherein updating the at least one pheromone value includes updating each of the at least one pheromone value according to the function P_i=(1+ρ

)P_i;

P_i is the at least one pheromone value; and

ρ

is a constant.

31. The node of claim 19 further comprising:

means for decreasing the at least one pheromone value at periodic intervals.

32. The node of claim 31 wherein decreasing the at least one pheromone value includes decreasing each of the at least one pheromone values according to the function P_i=(1−

ρ

)P_if(t);

P_i is the at least one pheromone value;

ρ

is a constant; and

f(t) is a function of time.

33. A node comprising:

a computer-readable storage device for storing at least one pheromone value and at least one aging factor;

a first port for receiving a message; and

a second port for transmitting the message.

34. The node of claim 33 wherein the message includes a request for sensor data.

35. The node of claim 33 wherein the message includes sensor data.

36. The node of claim 33 further comprising:

a sensor for detecting an event.

37. The node of claim 36 further comprising:

a processor coupled to the sensor, input port and output port, such that the processor can modify the message to include the detected event.

38. The node of claim 33 wherein the at least one pheromone value and the at least one aging factor are stored in a node data structure within the computer-readable storage device having a list of at least one interest;

each of the at least one interests is associated with a list of tuples, the list of tuples either being empty or containing at least one tuple; and

each of the at least one tuples contains a neighbor node, one of the at least one pheromone values and one of the at least one aging factors.

39. The node of claim 33 further comprising:

a processor connected to the computer-readable storage device, the first port and the second port, such that the processor can determine a destination for the transmitted message based on the at least one pheromone value and the at least one aging factor.

40. The node of claim 39 wherein the processor can determine the destination using an objective function.

41. The node of claim 40 wherein the objective function is

$\alpha$

⁢

 

⁢

f ⁡

( P ) + β

⁢

1 A ;

α and

β

are constants;

f(P) is a function of the at least one pheromone value; and

A is the at least one aging factor.

42. The node of claim 39 wherein the processor can update the at least one pheromone value and the at least one aging factor.

43. The node of claim 42 wherein updating the at least one pheromone value includes applying the function P_i=(1+ρ

)P_i;

P_i is at least one pheromone value; and

ρ

is a constant.

44. The node of claim 39 wherein the processor can decrease the at least one pheromone value at periodic intervals.

45. The node of claim 44 wherein decreasing includes applying the function P_i=(1−

ρ

)P_if(t);

P_i is the at least one pheromone value;

ρ

is a constant; and

f(t) is a function of time.

46. The node of claim 39 wherein the transmitted message is formatted by the processor to include a scan for at least one neighbor node at periodic intervals.

47. A sensor node for use in a self-organizing node network that is organized to balance speed and efficiency of data transfer with network life, the sensor node comprising:

an input port;

an output port;

a processor;

at least one sensor;

a computer-readable storage device;

a node data structure contained in the computer-readable storage device;

the processor coupled to the input port and the computer-readable storage device, such that the processor can analyze a message received through the input port and update at least one pheromone value and at least one aging factor stored in the node data structure based on the message;

the processor coupled to the output port, such that the processor can transmit the message on to at least one neighbor node in the node network and update at least one pheromone value and at least one aging factor stored in the node data structure based on the at least one neighbor node; and

the processor coupled to the at least one sensor, such that the processor can modify the message with sensor data collected from the at least one sensor.