Ad-hoc network and method employing globally optimized routes for packets

• US 7,633,882 B2
• Filed: 02/02/2006
• Issued: 12/15/2009
• Est. Priority Date: 02/02/2006
• Status: Expired due to Fees

• Current Assignee: Eaton Corp. (Wisconsin) (Eaton Corporation PLC.)
• Original Assignee: Eaton Corp. (Wisconsin) (Eaton Corporation PLC.)
• Inventors: Pereira, Luis R., Das, Sujit R.
• Primary Examiner(s): Moore, Jr.; Michael J
• Assistant Examiner(s): Duong; Duc T
• Application Number:
  US11/347,077
• Publication Number:
  US 20070177511A1
• Time in Patent Office: 1,412 Days
• Field of Search: 370/400, 370/338, 370/238, 370/252, 370/480, 370/339, 370/248, 370/254, 370/328, 370/401, 709220-223, 709/252
• US Class Current: 370/252
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

An ad-hoc network includes an ad-hoc network coordinator (NC) having a first processor, a first memory, and a first communication interface; and a plurality of ad-hoc network devices (NDs). Each of the NDs includes a second processor, a second memory, and a second communication interface structured to communicate with the first communication interface of the NC or with the second communication interface of at least another one of the NDs. The first processor cooperates with at least some of the NDs to globally optimize a route based on a plurality of link costs for: (i) pairs of the NDs, or (ii) pairs of the NDs and at least one pair including one of the NDs and the NC, in order to minimize cost along the route that: (a) one of the NDs or the NC employs to send a packet to: (b) another one of the NDs or the NC.

Claims

1. An ad-hoc network comprising:

an ad-hoc network coordinator comprising;

a first processor,

a first memory, and

a first communication interface; and

a plurality of ad-hoc network devices, each of said ad-hoc network devices comprising;

a second processor,

a second memory, and

a second communication interface structured to communicate with the first communication interface of said ad-hoc network coordinator or with the second communication interface of at least another one of said ad-hoc network devices,

wherein the second processor of each of said ad-hoc network devices is structured to determine a local graph,

wherein said local graph of a corresponding ad-hoc network device comprises;

a set of vertices corresponding to all of said ad-hoc network devices that the corresponding ad-hoc network device can communicate with,

a set of edges connecting said vertices, and

a set of link costs associated with said edges,

wherein each vertex of said vertices corresponds to one of said ad-hoc network devices that the corresponding ad-hoc network device can communicate with, and

wherein each edge of said edges links the corresponding ad-hoc network device to one vertex of said vertices,

wherein the second processor of each of said ad-hoc network devices is further structured to send the local graph to said ad-hoc network coordinator,

wherein the first processor of said ad-hoc network coordinator is structured to determine a global graph from the union of the local graph of each of said ad-hoc network devices, and

wherein said first processor employs said global graph and cooperates with at least some of said ad-hoc network devices to globally optimize a route in said ad-hoc network for;

(i) pairs of said ad-hoc network devices, or (ii) pairs of said ad-hoc network devices and at least one pair including one of said ad-hoc network devices and said ad-hoc network coordinator, in order to minimize cost along said route that;

(a) one of said ad-hoc network devices or said ad-hoc network coordinator employs to send a packet to;

(b) another one of said ad-hoc network devices or said ad-hoc network coordinator.

2. The ad-hoc network of claim 1 wherein said route includes at least one of said ad-hoc network devices other than said one of said ad-hoc network devices and said other one of said ad-hoc network devices.

3. The ad-hoc network of claim 1 wherein the corresponding ad-hoc network device is structured to build and maintain said local graph to manage packet routing locally for the corresponding ad-hoc network device;

and wherein said ad-hoc network coordinator is structured to build and maintain said global graph to manage packet routing globally for said ad-hoc network.

4. The ad-hoc network of claim 3 wherein said local graph is a smaller subset of said global graph.

5. The ad-hoc network of claim 1 wherein said ad-hoc network is a wireless sensor network.

6. The ad-hoc network of claim 1 wherein said ad-hoc network is a low rate wireless personal area network.

7. The ad-hoc network of claim 1 wherein the second processor of each of said ad-hoc network devices is further structured to update said link costs associated with said edges, and to intermittently send said local graph with said updated link costs to said ad-hoc network coordinator.

8. The ad-hoc network of claim 1 wherein the second processor of each of said ad-hoc network devices is further structured to update one of said link costs associated with a corresponding one of said edges, and to send said local graph with said updated one of said link costs to said ad-hoc network coordinator.

9. A method for determining routing of packets of an ad-hoc network comprising an ad-hoc network coordinator and a plurality of ad-hoc network devices, said ad-hoc network devices communicating with said ad-hoc network coordinator or with at least another one of said ad-hoc network devices, said method comprising:

determining a local graph for each of said ad-hoc network devices, wherein said local graph of a corresponding ad-hoc network device comprises;

a set of vertices corresponding to all of said ad-hoc network devices that the corresponding ad-hoc network device can communicate with,

a set of edges connecting said vertices, and

a set of link costs associated with said edges,

wherein each vertex of said vertices corresponds to one of said ad-hoc network devices that the corresponding ad-hoc network device can communicate with, and

wherein each edge of said edges links the corresponding ad-hoc network device to one vertex of said vertices;

sending the local graph from each of said ad-hoc network devices to said ad-hoc network coordinator;

determining a global graph from the union of the local graph of each of said ad-hoc network devices;

for;

(i) pairs of said ad-hoc network devices, or (ii) pairs of said ad-hoc network devices and at least one pair including one of said ad-hoc network devices and said ad-hoc network coordinator globally optimizing a route in said ad-hoc network based on said global graph; and

minimizing cost along said route that;

(a) one of said ad-hoc network devices or said ad-hoc network coordinator employs to send a packet to;

(b) another one of said ad-hoc network devices or said ad-hoc network coordinator.

10. The method of claim 9 further comprising

employing said one of said ad-hoc network devices as a source node;

employing said other one of said ad-hoc network devices as a destination node;

employing as said route a global minimum cost route, which includes at least one of said ad-hoc network devices other than said one of said ad-hoc network devices and said other one of said ad-hoc network devices; and

employing as a first element of said global minimum cost route a first global minimum cost neighbor of said source node.

11. The method of claim 10 further comprising

employing a single source minimum cost route function for said source node;

determining a plurality of global minimum cost routes from said source node to each of the other ones of said ad-hoc network devices;

employing said global minimum cost routes as a set of routes;

determining a plurality of global minimum cost neighbors corresponding to said global minimum cost routes; and

determining for each of said global minimum cost routes a set including at least one minimum cost neighbor for said source node.

12. The method of claim 10 further comprising

employing as a second element of said global minimum cost route a second global minimum cost neighbor of said first global minimum cost neighbor;

and

employing at least one successive global minimum cost neighbor terminating at said destination node.

13. The method of claim 9 further comprising

for at least one of said ad-hoc network devices:

discovering a route when powered up, reset or when isolated from said ad-hoc network;

learning about some of said ad-hoc network devices as being neighbor ad-hoc network devices;

informing said ad-hoc network coordinator about said neighbor ad-hoc network devices; and

receiving from said ad-hoc network coordinator a recommendation about which one of said neighbor ad-hoc network devices to use for sending upstream packets toward said ad-hoc network coordinator, in order to maximize routing efficiency or minimize routing cost.

14. The method of claim 13 further comprising

for said one of said ad-hoc network devices, completing said discovering a route for said neighbor ad-hoc network devices;

informing said ad-hoc network coordinator of said neighbor ad-hoc network devices;

discarding any prior global minimum cost neighbor;

selecting the upstream local minimum cost neighbor from the corresponding one of said local graphs;

sending a first update message to said upstream local minimum cost neighbor including said corresponding one of said local graphs; and

receiving a second update message from said ad-hoc network coordinator.

15. The method of claim 14 further comprising

receiving said first update message at said upstream local minimum cost neighbor;

for said upstream local minimum cost neighbor, selecting a corresponding upstream local minimum cost neighbor from the corresponding one of said local graphs;

forwarding said first update message to the last said corresponding upstream local minimum cost neighbor including the corresponding one of said local graphs of said one of said ad-hoc network devices; and

forwarding said first update message to said ad-hoc network coordinator.

16. The method of claim 9 further comprising

for each of said ad-hoc network devices, building and maintaining a corresponding said local graph to manage routing locally for a corresponding one of said ad-hoc network devices;

and

for said ad-hoc network coordinator, building and maintaining said global graph to manage routing globally for said ad-hoc network.

17. The method of claim 16 further comprising

for the corresponding one of said ad-hoc network devices, discovering some of said ad-hoc network devices as being neighbor ad-hoc network devices;

discarding the corresponding said local graph;

broadcasting a request message to at least one of said neighbor ad-hoc network devices;

responsively receiving a response message from at least one of said neighbor ad-hoc network devices; and

updating the corresponding said local graph with two vertices, an edge and a link cost associated with said response message from a corresponding one of said at least one of said neighbor ad-hoc network devices to said one of said ad-hoc network devices.

18. The method of claim 17 further comprising

for the corresponding one of said at least one of said neighbor ad-hoc network devices, receiving said request message;

employing said link cost as a first link cost;

determining a second link cost from said one of said ad-hoc network devices to said corresponding one of said at least one of said neighbor ad-hoc network devices; and

broadcasting said response message including the second link cost.

19. The method of claim 18 further comprising

for said one of said ad-hoc network devices, receiving said response message including the second link cost;

determining the first link cost from said corresponding one of said at least one of said neighbor ad-hoc network devices to said one of said ad-hoc network devices;

adding said corresponding one of said at least one of said neighbor ad-hoc network devices as an upstream vertex in the corresponding one of said local graphs; and

adding an edge from said corresponding one of said at least one of said neighbor ad-hoc network devices to said one of said ad-hoc network devices.

20. The method of claim 19 further comprising

sending a confirm message to said corresponding one of said at least one of said neighbor ad-hoc network devices indicating acceptance as a downstream neighbor;

and

receiving another response message from another one of said at least one of said neighbor ad-hoc network devices.

21. The method of claim 9 further comprising

employing upstream routing if the ad-hoc network coordinator is the final destination of a packet sent by one of said ad-hoc network devices;

and

employing a global minimum cost neighbor defined by said ad-hoc network coordinator as an initial destination of said packet sent by one of said ad-hoc network devices.

22. The method of claim 21 further comprising

for another one of said ad-hoc network devices, joining said ad-hoc network;

receiving a global minimum cost neighbor for said other one of said ad-hoc network devices as defined by said ad-hoc network coordinator;

employing upstream routing if the ad-hoc network coordinator is the final destination of another packet sent by said other one of said ad-hoc network devices; and

employing the last said global minimum cost neighbor as an initial destination of said other packet sent by said other one of said ad-hoc network devices.

23. The method of claim 9 further comprising

employing downstream routing when said ad-hoc network coordinator sends a packet to one of said ad-hoc network devices.

24. The method of claim 23 further comprising

for said ad-hoc network coordinator, updating one of said ad-hoc network devices with a set of global minimum cost neighbors for each possible destination of packets to each of the other ones of said ad-hoc network devices.

25. The method of claim 24 further comprising

receiving said packet to one of said ad-hoc network devices at another one of said ad-hoc network devices;

for said other one of said ad-hoc network devices, determining the corresponding global minimum cost neighbor; and

forwarding said received packet to said determined corresponding global minimum cost neighbor.

26. The method of claim 25 further comprising

including the address of said determined corresponding global minimum cost neighbor in said forwarded packet;

and

employing no routing specification in said forwarded packet.

27. The method of claim 23 further comprising

for said ad-hoc network coordinator, updating on demand selected ones of said ad-hoc network devices with corresponding global minimum cost neighbors for a particular downstream destination on demand;

establishing a route to a downstream destination after one of said ad-hoc network devices needs to initially send a packet to said particular downstream destination; and

after said establishing a route, each intermediate one of said ad-hoc network devices maintaining a corresponding global minimum cost neighbor for said particular downstream destination.