Patent ID: 7633882

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