Method and apparatus for sensor network routing

• US 7,466,681 B2
• Filed: 03/19/2004
• Issued: 12/16/2008
• Est. Priority Date: 03/19/2004
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Fedyk, Donald, Ashwood-Smith, Peter
• Primary Examiner(s): Beamer, Temica M.
• Application Number:
  US10/804,740
• Publication Number:
  US 20050207376A1
• Time in Patent Office: 1,733 Days
• Field of Search: 455/41.2, 370/395.31, 370/408, 370/409
• 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;

wherein the distance message contains key information indicative of sensors on the network that have broadcast the distance message prior to reception by the sensor.

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 1, further comprising the step of extracting the key information from the distance message.

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

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

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

7. 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.

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

9. 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.

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 not rebroadcasting the updated distance message.

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

17. 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.

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

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

12. 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;

using the message distance information to set a current sensor distance of the sensor from the sensor to the collector node;

receiving a data message by the sensor from another sensor on the sensor network; and

selectively rebroadcasting the data message if a distance value in the data message is equal to or less than the current sensor distance.

20. The method of claim 12, wherein the step of selectively rebroadcasting the data message comprises comparing key information in the data message with key information associated with the sensor, and only rebroadcasting the data message if the data message contains matching key information.

21. The method of claim 20, wherein the key information associated with the sensor is not unique on the network.

13. 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;

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

comparing the message distance information with a drop value.

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

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

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