Predictive routing technique in the ad hoc wireless network

• US 7,944,899 B2
• Filed: 03/28/2008
• Issued: 05/17/2011
• Est. Priority Date: 08/15/2007
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Nordmark, Erik, Chakrabarti, Samita
• Primary Examiner(s): Phan; Man
• Assistant Examiner(s): Mansoury; Nourali
• Application Number:
  US12/058,509
• Publication Number:
  US 20090046712A1
• Time in Patent Office: 1,145 Days
• Field of Search: 370/389, 370/338, 370/254, 370/351, 370/310, 370/392, 370/238
• US Class Current: 370/338
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In a particular embodiment of the present invention, a forwarding node in an ad hoc network collects sets of node information pertaining to its neighbor nodes. An example of a type of node information is history information that indicates previous time periods during which a neighbor node has been available for communication. Other types of node information may include proximity information that indicates how far a neighbor node is from the forwarding node. In selecting a routing path, the forwarding node takes into account information collected in the sets of node information. A routing path can be selected to include a neighbor node having the highest probability to be available for communication. Additionally or alternatively, a routing path may be selected to minimize the power transmission level required for the forwarding node to forward data packets.

Claims

1. A method implemented by a forwarding node in an ad hoc network, comprising:

collecting a first set of node information pertaining to a first neighbor node, wherein the first set of node information comprises;

first power information comprising a first power level required to transmit information to the first neighbor node and a first energy source weight factor corresponding to a type of energy source of the first neighbor node, and

first history information indicating previous time periods during which the first neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of a day and a day of a week;

calculating a first availability probability for the first neighbor node, using the first history information and a current time period;

calculating a first overall availability probability for the first neighbor node using the first availability probability and the first power information;

collecting a second set of node information pertaining to a second neighbor node, wherein the second set of node information comprises;

second power information comprising a second power level required to transmit information to the second neighbor node and a second energy source weight factor corresponding to a type of energy source of the second neighbor node, and

second history information indicating previous time periods during which the second neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of the day and a day of the week;

calculating a second availability probability for the second neighbor node, using the second history information and the current time period;

calculating a second overall availability probability for the second neighbor node using the second availability probability and the second power information;

selecting a first routing path to a destination node that includes the first neighbor node as a hop when the first overall availability probability is greater than the second overall availability probability; and

upon selecting the first routing path, forwarding a packet to the destination node via the first routing path.

2. The method of claim 1, further comprising:

when the first overall availability probability is not greater than the second availability probability, selecting a second routing path to the destination node that includes the second neighbor node as the hop.

3. The method of claim 1, wherein the first set of node information further comprises proximity information indicating a physical distance between the first neighbor node and the forwarding node, and wherein the proximity information is taken into account in selecting the first routing path to the destination node.

4. The method of claim 1, wherein the first set of node information further comprises mobility information indicating whether the first neighbor node is one selected from a group consisting of mobile and stationary relative to the forwarding node, and wherein the mobility information is taken into account in calculating the first overall availability probability.

5. The method of claim 1, wherein the first history information in the first set of node information comprises longevity information indicating how long the first neighbor node remains available for the at least one prior communication when it is available for a potential communication, and wherein the longevity information is taken into account in calculating the first overall availability probability.

6. A non-transitory, tangible machine readable storage medium, comprising:

instructions for collecting a first set of node information pertaining to a first neighbor node, wherein the first set of node information comprises;

first power information comprising a first power level required to transmit information to the first neighbor node and a first energy source weight factor corresponding to a type of energy source of the first neighbor node, and

first history information indicating previous time periods during which the first neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of a day and a day of a week;

instructions for calculating a first availability probability of the first neighbor node, using the first history information and a current time period;

instructions for calculating a first overall availability probability of the first neighbor node using the first availability probability and the first power information;

instructions for collecting a second set of node information pertaining to a second neighbor node, wherein the second set of node information comprises;

second power information comprising a second power level required to transmit information to the second neighbor node and a second energy source weight factor corresponding to a type of energy source of the second neighbor node, and

second history information indicating previous time periods during which the second neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of the day and a day of the week;

instructions for calculating a second availability probability for the second neighbor node, using the second history information and a current time period;

instructions for calculating a second overall availability probability for the second neighbor node using the second availability probability and the first power information;

instructions for selecting a first routing path to a destination node that includes the neighbor node as a hop when the first overall availability probability is greater than the second overall availability probability; and

instructions for forwarding a packet to the destination node via the first routing path upon selecting the first routing path.

7. The machine readable storage medium of claim 6, further comprising:

instructions for selecting a second routing path to the destination node that includes the second neighbor node as the hop when the first overall availability probability is not greater than the second availability probability.

8. The machine readable storage medium of claim 6, wherein the first set of node information further comprises proximity information indicating a physical distance between the first neighbor node and a forwarding node, and wherein the proximity information is taken into account in selecting the first routing path to the destination node.

9. The machine readable storage medium of claim 6, wherein the first set of node information further comprises mobility information indicating whether the first neighbor node is one selected from a group consisting of mobile and stationary relative to a forwarding node, and wherein the mobility information is taken into account in calculating the first overall availability probability.

10. The machine readable storage medium of claim 6, wherein the first history information in the first set of node information comprises longevity information indicating how long the first neighbor node remains available for the at least one prior communication when it is available for a potential communication, and wherein the longevity information is taken into account in calculating the first overall availability probability.

11. A forwarding node in an ad hoc network, wherein the forwarding node is configured to:

collect, by a processor, a first set of node information pertaining to a first neighbor node, wherein the first set of node information comprises;

first power information comprising a first power level required to transmit information to the first neighbor node and a first energy source weight factor corresponding to a type of energy source of the first neighbor node, and

first history information indicating previous time periods during which the first neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of a day and a day of a week;

calculate, by the processor, a first availability probability for the first neighbor node, using the first history information and a current time period;

calculate, by the processor, a first overall availability probability for the first neighbor node using the first availability probability and the first power information;

collect, by the processor, a second set of node information pertaining to a second neighbor node, wherein the second set of node information comprises;

second power information comprising a second power level required to transmit information to the second neighbor node and a second energy source weight factor corresponding to a type of energy source of the second neighbor node, and

second history information indicating previous time periods during which the second neighbor node has been available for at least one prior communication, wherein the time periods are one selected from a group consisting of a time of the day and a day of the week;

calculate, by the processor, a second availability probability for the second neighbor node, using the second history information and the current time period;

calculate, by the processor, a second overall availability probability for the second neighbor node using the second availability probability and the second power information;

select, by the processor, a first routing path to a destination node that includes the first neighbor node as a hop when the first overall availability probability is greater than the second overall availability probability; and

forward, by the processor, a packet to the destination node via the first routing path upon selecting the first routing path.

12. The forwarding node of claim 11, further configured to:

when the first overall availability probability is not greater than the second availability probability, select, by the processor, a second routing path to the destination node that includes the second neighbor node as the hop.

13. The forwarding node of claim 11, wherein the first set of node information further comprises mobility information indicating whether the first neighbor node is one selected from a group consisting of mobile and stationary relative to the forwarding node, and wherein the mobility information is taken into account in calculating the first overall availability probability.

14. The forwarding node of claim 11, wherein the first history information in the first set of node information comprises longevity information indicating how long the first neighbor node remains available for the at least one prior communication when it is available for potential communication, and wherein the longevity information is taken into account in calculating the first overall availability probability.