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

• US 20070177511A1
• Filed: 02/02/2006
• Published: 08/02/2007
• Est. Priority Date: 02/02/2006
• Status: Active Grant

• Current Assignee: Eaton Corp. (Wisconsin) (Eaton Corporation PLC.)
• Original Assignee: Eaton Corp. (Wisconsin) (Eaton Corporation PLC.)
• Inventors: Das, Sujit, Pereira, Luis
• Granted Patent: US 7,633,882 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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 said first processor cooperates with at least some of said ad-hoc network devices to globally optimize a route based on a plurality of link costs 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 said ad-hoc network devices are structured to build and maintain a plurality of local graphs to manage packet routing locally for the corresponding one of said ad-hoc network devices;

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

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

5. The ad-hoc network of claim 3 wherein said local graphs comprise a set of vertices corresponding to some of said ad-hoc network devices, a set of edges connecting said vertices, and a set of link costs associated with said edges.

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

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

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

employing a plurality of link costs 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 based on said link costs; 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.

9. The method of claim 8 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.

10. The method of claim 9 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.

11. The method of claim 9 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.

12. The method of claim 8 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.

13. The method of claim 8 further comprising

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

and

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

14. The method of claim 13 further comprising

for 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 one of said local graphs;

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 one of said local graphs 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.

15. The method of claim 14 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.

16. The method of claim 15 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.

17. The method of claim 16 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.

18. The method of claim 12 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.

19. The method of claim 18 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.

20. The method of claim 8 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.

21. The method of claim 20 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.

22. The method of claim 8 further comprising

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

23. The method of claim 22 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.

24. The method of claim 23 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.

25. The method of claim 24 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.

26. The method of claim 22 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.