Traffic-oblivious load balancing protocol for sensor networks

• US 8,085,792 B1
• Filed: 10/19/2007
• Issued: 12/27/2011
• Est. Priority Date: 06/29/2007
• Status: Expired due to Fees

• 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:
  US11/875,531
• Time in Patent Office: 1,530 Days
• Field of Search: None
• US Class Current: 370/400
• 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 method of routing packets in a wireless network, the method comprising:

selecting an intermediate destination sensor in a network to which to route a packet, wherein;

the intermediate destination sensor is selected independently of energy status of sensors included in the network, and

the intermediate destination sensor is selected by a source sensor randomly or pseudo-randomly from among sensors included in the network; and

routing the packet from the source sensor toward a destination sensor, the routing comprising;

forwarding the packet from the source sensor to one or more intermediate sensors, and

having each of the one or more intermediate sensors (i) determine whether the intermediate sensor is closer to the intermediate destination sensor than any neighbor sensors of the intermediate sensor, (ii) forward the packet toward the intermediate destination sensor if the intermediate sensor is not closer than the neighbor sensors, and (iii) forward the packet toward the destination sensor if the intermediate sensor is closer than the neighbor sensors.

2. The method of claim 1, wherein selecting the intermediate destination sensor independently of the energy status of the sensors included in the network comprises selecting the intermediate destination sensor without determining whether the intermediate destination sensor has been previously selected.

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

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

5. The method of claim 1, wherein routing the packet from the source sensor toward the destination sensor comprises routing the packet toward the selected intermediate destination sensor without enumeration of a path from the source sensor to the selected intermediate destination sensor.

6. The method of claim 1, further comprising routing the packet from the selected intermediate destination sensor toward the destination sensor.

7. The method of claim 1 further comprising, at each of the one or more intermediate sensors:

determining a value of an indicator configured to indicate whether to route the packet to the selected intermediate destination sensor or to the destination sensor;

determining whether to route the packet to the destination sensor based on distances to the intermediate destination sensor from the intermediate sensor and neighbor sensors of the intermediate sensor; and

changing the value of the indicator to indicate that the packet is to be routed to the destination sensor based on the determination of whether to route the packet to the destination sensor.