Traffic-oblivious load balancing protocol for sensor networks

• US 8,625,575 B1
• Filed: 12/08/2011
• Issued: 01/07/2014
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Aly, Mohamed
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US13/314,645
• Time in Patent Office: 761 Days
• Field of Search: None
• US Class Current: 370/351
• 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 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04W 28/08 Load balancing or load distribution transferring a connection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A sensor in a network to which to route a packet is selected, where the sensor is selected independently of energy status of the sensors included in the network, and the sensor is selected by a source sensor. The packet is routed from the source sensor toward the destination sensor.

Claims

1. A device comprising:

at least one processor; and

a storage device, the storage device storing instructions for causing the at least one processing device to;

track numbers of packets forwarded from a sensing device to a plurality of neighbor sensors in a network of the sensing device;

select two or more sensors from the plurality of neighbor sensors in the network to which to potentially route a packet, the two or more sensing devices being randomly selected and being intermediate sensing devices in the network between the sensing device and a destination sensor in the network;

determine, based on the tracked numbers of packets forwarded to the plurality of neighbor sensors, whether a number of packets routed in a direction toward one of the two or more selected sensors does not exceed a number of packets routed in a direction of another one of the two or more selected sensors; and

route the packet from the sensing device toward one of the two or more selected sensors while not routing the packet from the sensing device toward another one of the two or more selected sensors, the routing being conditioned upon a determination that the number of packets routed in the direction toward the one of the two or more selected sensors does not exceed the number of packets routed in the direction of the another one of the two or more selected sensors such that two packets that arrive in sequence at the sensing device are not both routed on a shortest path to the destination sensor.

2. The sensing device of claim 1, wherein the numbers of packets routed in the direction of the two or more selected sensors are equal and the storage device stores instructions for causing the at least one processing device to:

determine to which of the two or more selected sensors a packet was least recently routed toward; and

select a sensor least recently routed toward as the one of the two or more selected sensors.

3. The sensing device of claim 1, wherein the determining whether the number of packets routed in the direction toward the one of the two or more selected sensors comprises determining the number of packets routed in the direction toward a neighbor of the sensing device.

4. The sensing device of claim 1, wherein routing the packet comprises routing the packet using an underlying routing protocol of the network.

5. The sensing device of claim 4, wherein the underlying routing protocol of the network is a point-to-point routing protocol.

6. A method of routing packets in a wireless network, the method comprising:

identifying a packet for routing through a network of sensors from a source sensor to a destination sensor associated with the network;

at the source sensor, randomly selecting from all of the sensors in the network a plurality of intermediate sensors between the source sensor and the destination sensor in the network;

tracking a number of packets that have been routed to each of the randomly selected plurality of intermediate sensors;

determining a load associated with each of the randomly selected plurality of intermediate sensors based on the tracked number of packets; and

routing the packet to a sensor selected from the randomly selected plurality of intermediate sensors that has the lightest load rather than directly to the destination sensor, wherein the selected sensor having the lightest load is the sensor selected from the randomly selected plurality of intermediate sensors to which the fewest packets have been routed such that two packets that arrive in sequence at the source sensor are not both routed on a shortest path to the destination sensor.

7. The method of claim 6, wherein when two sensors have the lightest load then the method further including determining to which of the two sensors a packet was least recently routed toward;

and

select a sensor least recently routed toward as the sensor for routing the packet.

8. The method of claim 6 further comprising determining whether the number of packets routed in the direction toward one of the randomly selected plurality of intermediate sensors comprises determining the number of packets routed in the direction toward a neighbor of a respective selected sensor.

9. The method of claim 6, wherein routing the packet comprises routing the packet using an underlying routing protocol of the network.

10. The method of claim 9, wherein the underlying routing protocol of the network is a point-to-point routing protocol.

11. A method of routing packets in a wireless network, the method comprising:

selecting a sensor in a network to which to route a packet from a source sensor in a path toward a destination sensor, wherein;

the sensor is selected randomly by the source sensor without communicating with the selected sensor or any neighbor sensors, and

sensors in the network have a non-uniform spatial distribution;

tracking a number of packets that have been routed to the selected sensor and one or more neighbor sensors of the source sensor, the one or more neighbor sensors being selected randomly and being intermediate sensors between the source sensor and the destination sensor;

determining, based on the tracking, whether a number of packets routed in the direction toward the selected sensor does not exceed a number of packets routed in the direction of the one or more selected neighbor sensors of the source sensor; and

routing the packet from the source sensor toward the selected sensor while not routing the packet from the source sensor to the one or more selected neighbor sensors, the routing being conditioned upon a determination that the number of packets routed in the direction toward the selected sensor does not exceed the number of packets routed in the direction of the one or more selected neighbor sensors such that two packets that arrive in sequence at the source sensor are not both routed on a shortest path to the destination sensor.

12. The method of claim 11, wherein the routing being conditioned upon a determination that the number of packets routed in the direction toward the selected sensor does not exceed the number of packets routed in the direction toward the one or more selected neighbor sensors comprises routing the packet conditioned upon a determination that the number of packets routed in the direction toward the selected sensor is less than the number of packets routed in the direction of each of the one or more selected neighbor sensors.

13. The method of claim 11, wherein the routing is conditioned upon a determination that the number of packets routed in the direction toward the selected sensor does not exceed the number of packets routed in the direction of the one or more selected neighbor sensors, and further comprising:

selecting a second sensor in the network to which to route the packet before the packet is routed to the destination sensor, the second sensor being selected randomly; and

routing the packet from the source sensor toward the selected second sensor without enumeration of a path from the source sensor to the selected second sensor, the routing being conditioned upon a determination that a number of packets routed in the direction toward the selected second sensor is less than a number of packets routed toward one or more randomly selected neighbor sensors of the second sensor.

14. The method of claim 11, wherein tracking a number of packets comprises maintaining a counter on the source sensor in response to a packet being routed from the source sensor to the selected sensor, the method further comprising:

determining the number of packets routed to the selected sensor based on the counter.

15. The method of claim 11, wherein determining that the number of packets routed in the direction toward the selected sensor does not exceed the number of packets routed in the direction toward the one or more selected neighbor sensors is determined based on a comparison, to a threshold value, of a ratio of a counter representing a direction of the selected sensor and a sum of counters representing directions of the one or more selected neighbor sensors and further comprising forwarding the packet in a direction other than the direction toward the selected sensor when the threshold value is exceeded.

16. A computer program product comprising instructions stored in a non-transitory memory that when executed by a processor, cause the processor to:

track numbers of packets forwarded from a first sensing device to a plurality of neighbor sensors in a network of the first sensing device;

select two or more sensors from the plurality of neighbor sensors in the network to which to potentially route a packet, the two or more sensing devices being randomly selected and being intermediate sensing devices in the network between the first sensing device and a destination sensor for the packet in the network;

determine, based on the tracked numbers of packets forwarded to the plurality of neighbor sensors, whether a number of packets routed in a direction toward one of the two or more selected sensors does not exceed a number of packets routed in a direction of another one of the two or more selected sensors; and

route the packet from the first sensing device toward one of the two or more selected sensors while not routing the packet from the first sensing device toward another one of the two or more selected sensors, the routing being conditioned upon a determination that the number of packets routed in the direction toward the one of the two or more selected sensors does not exceed the number of packets routed in the direction of the another one of the two or more selected sensors such that two packets that arrive in sequence at the first sensing device are not both routed on a shortest path to the destination sensor.

17. A computer program product comprising instructions stored in a non-transitory memory that when executed by a processor, cause the processor to:

identify a packet for routing through a network of sensors from a source sensor to a destination sensor associated with the network;

at the source sensor, randomly select from all of the sensors in the network a plurality of intermediate sensors between the source sensor and the destination sensor in the network;

track a number of packets that have been routed to each of the randomly selected plurality of intermediate sensors;

determine a load associated with each of the randomly selected plurality of intermediate sensors based on the tracked number of packets; and

route the packet to a sensor selected from the randomly selected plurality of intermediate sensors that has the lightest load rather than directly to the destination sensor, wherein the selected sensor having the lightest load is the sensor selected from the randomly selected plurality of intermediate sensors to which the fewest packets have been routed such that two packets that arrive in sequence at the source sensor are not both routed on a shortest path to the destination sensor.

18. A computer program product comprising instructions stored in a non-transitory memory that when executed by a processor, cause the processor to:

select a sensor in a network to which to route a packet from a source sensor in a path toward a destination sensor, wherein;

the sensor is selected randomly by the source sensor without communicating with the selected sensor or any neighbor sensors, and

sensors in the network have a non-uniform spatial distribution;

track a number of packets that have been routed to the selected sensor and one or more neighbor sensors of the source sensor, the one or more neighbor sensors being selected randomly and being intermediate sensors between the source sensor and the destination sensor;

determine, based on the tracking, whether a number of packets routed in the direction toward the selected sensor does not exceed a number of packets routed in the direction of the one or more selected neighbor sensors of the source sensor; and

route the packet from the source sensor toward the selected sensor while not routing the packet from the source sensor to the one or more selected neighbor sensors, the routing being conditioned upon a determination that the number of packets routed in the direction toward the selected sensor does not exceed the number of packets routed in the direction of the one or more selected neighbor sensors such that two packets that arrive in sequence at the source sensor are not both routed on a shortest path to the destination sensor.