Method and apparatus for sensor network routing

• US 20050207376A1
• Filed: 03/19/2004
• Published: 09/22/2005
• Est. Priority Date: 03/19/2004
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Fedyk, Donald, Ashwood-Smith, Peter
• Granted Patent: US 7,466,681 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Sensor network routing uses distance information of sensors relative to a collector node, optionally along with non-unique key information, to route broadcasts from addressless sensors to a selected addressless collector. Distance calculation messages (DCMs) are used to set distance values on sensors relative to collectors. The distance values enable messages to propagate toward collectors to reduce the number of broadcasts. Self-assigned key information may be added to DCMs propagating in the network to enable routes to be determined through the network without assigning addresses to the participants. By storing the key information associated with the route, and causing sensors to only rebroadcast a message if the message contains a matching key at the matching distance position, broadcast paths may be created on the network. Optionally, diverse collectors and paths may be selected on the network by exchanging traffic condition indications and preferentially selecting paths with better traffic conditions.

Claims

1. A method of routing on a sensor network, the method comprising the steps of:

receiving by a sensor a distance calculation message containing message distance information indicative of a number of hops to a collector node; and

comparing the message distance information with current sensor distance information to obtain a distance result.

2. The method of claim 1, wherein if the distance result indicates that the current sensor distance is farther than the message distance information, the method further comprising the step of updating the current sensor distance information with the message distance information.

3. The method of claim 2, wherein the distance message contains key information indicative of sensors on the network that have broadcast the message prior to reception by the sensor.

4. The method of claim 3, further comprising the step of extracting the key information from the distance message.

5. The method of claim 3, wherein the key information is a non-unique value associated with the sensors on the network.

6. The method of claim 3, wherein the distance message contains traffic condition information indicative of traffic conditions at the sensors on the network.

7. The method of claim 6, wherein the traffic conditions at the sensors may be used to select a preferential path through the network.

8. The method of claim 2, further comprising the steps of creating an updated distance message containing increased message distance information;

and broadcasting the updated distance message.

9. The method of claim 8, further comprising establishing sensor key information associated with the sensor and including the sensor key information in the updated distance message.

10. The method of claim 1, wherein if the distance result indicates that the current sensor distance is the same as the message distance information, the method further comprising the steps of creating an updated distance message containing increased message distance information;

and broadcasting the updated distance message.

11. The method of claim 1, wherein if the distance result indicates that the current sensor distance is the same as the message distance information, the method further comprising the steps of not rebroadcasting the updated distance message.

12. The method of claim 1, further comprising the step of periodically increasing the current sensor distance information.

13. The method of claim 1, further comprising the steps of receiving a data message and selectively rebroadcasting the data message if a distance value in the data message is equal to or less than the current sensor distance.

14. The method of claim 1, further comprising the steps of comparing the message distance information with a drop value.

15. The method of claim 14, wherein the drop value is independent of the current sensor distance and the distance value in the data message.

16. The method of claim 14, wherein the distance calculation message further comprises reflection prevention information.

17. The method of claim 16, wherein the reflection prevention information is a message identifier.

18. The method of claim 1, wherein the distance calculation message further contains collector identification information associated with an identity of a collector associated with the distance calculation message.

19. The method of claim 18, wherein the collector identification information is a key information that is not unique on the network.

20. The method of claim 18, wherein the distance calculation message further contains a collector load indicator.

21. A method of establishing routing information on a sensor network, the method comprising the steps of:

generating a distance calculation message containing a distance information parameter indicative of a number of hops to a collector node, the distance information parameter being updateable by sensors on the sensor network; and

broadcasting the distance calculation message to the sensor network.

22. The method of claim 21, further comprising receiving data messages from sensors on the sensor network.

23. The method of claim 22, wherein the data messages comprise key information associated with a series of sensors on the network that broadcasted the message to enable the message to propagate from an originating sensor to be received.

24. A sensor network, comprising:

collector nodes; and

sensor nodes;

wherein said sensor nodes are configured to use distance information relative to the collector node and key information to selectively transmit data messages on the sensor network.

25. The sensor network of claim 24, wherein the sensor nodes are further configured to use traffic condition information to selectively transmit data messages on the sensor network.