RESOURCE MANAGEMENT FOR AD HOC WIRELESS NETWORKS WITH CLUSTER ORGANIZATIONS

• US 20080279167A1
• Filed: 06/18/2004
• Published: 11/13/2008
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Pavan, Allalaghatta, Varadarajan, Srivatsan, Graba, Lee B., Cardei, Ionut E.
• Granted Patent: US 7,460,549 B1
• Time in Patent Office: Days
• US Class Current: 370/342
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

An initiator node in a local cluster included in a wireless network receives an admission request to execute an application comprising a set of tasks. If the initiator node is unable to map the set of tasks to nodes included in the local cluster, the local cluster head node forwards the admission request to the cluster head node of successive clusters in the wireless network in order to have at least one node in each of the successive clusters send resource availability information to the initiator node. The initiator node attempts to map the set of tasks to a subset of the nodes from which resource availability information has been received. This is repeated until the initiator node is able to map the set of tasks to a subset of the nodes in the wireless network or until there are no additional clusters to forward the admission request to.

Claims

1. A system comprising:

a wireless network comprising a plurality of clusters;

wherein each cluster comprises a set of nodes including a cluster head node;

wherein each node includes at least one resource;

wherein when an initiator node in a local cluster included in the wireless network receives an admission request to execute an application comprising a set of tasks, the initiator node forwards the admission request to a local cluster head node for the local cluster;

wherein when the admission request is forwarded to the local cluster head node, the local cluster head node requests that at least one of the set of nodes included in the local cluster provide resource availability information to the initiator node;

wherein the initiator node attempts to map the set of tasks to a subset of the nodes included in the local cluster using the resource availability information received from nodes in the local cluster; and

wherein, if the initiator node is unable to map the set of tasks to the subset of nodes included in the local cluster;

the local cluster head node forwards the admission request to the cluster head node of successive clusters in the wireless network in order to have at least one node in each of the successive clusters send resource availability information to the initiator node until the initiator node is able to map the set of tasks to a subset of the nodes in the wireless network or until there are no additional clusters to forward the admission request to; and

the initiator node attempts to map the set of tasks to a subset of the nodes from which resource availability information has been received based on the received resource availability information.

2. The system of claim 1, wherein each cluster head node that receives the admission request requests that the nodes within the same cluster as that cluster head node send resource availability information to the initiator node.

3. The system of claim 2, wherein each node that receives a request to send resource availability information to the initiator node:

determines resource availability information for that node;

sends the resource availability information to the initiator node; and

reserves resources for the admission request from available resources;

when the node receives a commit message sent from the initiator node to that node when the initiator node maps at least one of the tasks to that node, commits the reserved resources for the at least one of tasks mapped to that node and execute the at least one of the tasks mapped to that node; and

when a predetermined amount of time elapses after reserving the reserved resources without receiving the commit message;

release the reserved resources.

4. The system of claim 3, the predetermined amount of time is determined using a timer.

5. A method comprising:

in a wireless ad hoc network having a plurality of clusters, each cluster comprising at least one of a plurality of nodes;

attempting to map a set of tasks to at least one node within a first cluster of the wireless network based on adaptability resource availability of the nodes within the first cluster, wherein the adaptability resource availability of a node comprises an amount of a resource available for use based on a reduced utilization of the resource by the task; and

if unable to map the set of tasks to said at least one node in the first cluster, attempting to map the set of tasks to at least one node in at least one of the first cluster and at least one of the other clusters in the wireless network based on resource availability of the nodes within the first cluster and the at least one of the other clusters in the wireless network.

6. The method of claim 5, further comprising receiving a request to admit an application for execution on at least one node in the network, the application comprising the set of tasks.

7. The method of claim 6, wherein the admission request is received at a first node.

8. The method of claim 7, wherein the request is received from a client executing on the first node.

9. The method of claim 7, further comprising forwarding the request to a head node of the first cluster and receiving, at the first node in the first cluster, first resource availability information from at least one node in the first cluster.

10. The method of claim 9, wherein the request is forwarded to the first head node based on a routing protocol.

11. The method of claim 9, further comprising, if unable to map the set of tasks to said at least one node in the first cluster, requesting that the head node of the first cluster communicate the request to a head node of the at least one of the other clusters in the wireless network and receiving, at the first node in the first cluster, resource availability information from at least one node in the at least one of the other clusters in the wireless network.

12. A system comprising:

a wireless network comprising a plurality of clusters;

wherein each cluster comprises a set of nodes including a cluster head node;

wherein each node includes at least one resource;

wherein when an initiator node in a local cluster included in the wireless network receives an admission request to execute an application comprising a set of tasks, the initiator node forwards the admission request to a local cluster head node for the local cluster;

wherein when the admission request is forwarded to the local cluster head node, the local cluster head node requests that at least one of the set of nodes included in the local cluster provide resource availability information to the initiator node;

wherein the initiator node attempts to map the set of tasks to a subset of the nodes included in the local cluster using the resource availability received from nodes in the local cluster; and

wherein, if the initiator node is unable to map the set of tasks to the subset of nodes included in the local cluster;

the initiator node requests that the local cluster head node forward the admission request to at least one remote cluster head node of at least one remote cluster included in the wireless network;

when the admission request is forwarded to the at least one remote cluster head node, the at least one remote cluster head node requests that at least one of the set of nodes included in the at least one remote cluster provide resource availability information to the initiator node; and

the initiator node attempts to map the set of tasks to a subset of the nodes included in at least one of the local cluster and the at least one remote cluster using the resource availability received from nodes in the local cluster and the at least one remote cluster.

13. The system of claim 12, wherein at least one node that provides resource availability information to the initiator node reserves at least a portion of the resources available on that node for at least one of the set of tasks.

14. The system of claim 13, wherein when the initiator node maps at least one of the set of tasks to at least one node that provides resource availability information to the initiator node, the initiator node sends a commit message to that node.

15. The system of claim 12, wherein an adapted application comprises a set of executing tasks and wherein at least one node in the network to which a task is mapped reduces an amount of at least one resource that is utilized by at least one of the set of executing tasks of the adapted application in order to execute the task mapped to that node.

16. The system of claim 15, wherein the initiator node sends an adapt message to at least one node in the wireless network on which at least one of the set of executing tasks of the adapted application executes.

17. A first node comprising:

a wireless transceiver to send and receive data over a wireless network;

a processor in communication with the wireless transceiver; and

a tangible medium, in communication with the processor, in which program instructions are embodied, wherein the program instructions, when executed by the processor, cause the first node to;

receive an admission request from a client, the admission request requesting that a set of tasks be executed;

forward the admission request to a local cluster head node for a local cluster in order to have at least one node in the local cluster send resource availability information to the first node, wherein the first node is a member of the local cluster;

receive resource availability information from the at least one node in the local cluster;

attempt to map the set of tasks to at least a subset of the nodes included in the local cluster using the resource availability information received from the at least one node in the local cluster; and

if unable to map the set of tasks to the subset of nodes included in the local cluster;

request that the local cluster head node of the local cluster forward the admission request to at least one remote cluster head node of at least one remote cluster included in the wireless network in order to have at least one node in the at least one remote cluster send resource availability information to the first node; and

attempt to map the set of tasks to at least a subset of the nodes included in at least one of the local cluster and the at least one remote cluster using the resource availability received from the at least one node in at least one of the local cluster and the at least one remote cluster.

18. The first node of claim 17, wherein the program instructions, when executed by the processor, cause the first node to attempt to map the set of tasks to the subset of the nodes included in the local cluster using the resource availability information received from the at least one node in the local cluster by attempting to map all of the tasks in the set of tasks to a single node in the local cluster.

19. The first node of claim 17, wherein the program instructions, when executed by the processor, cause the first node to attempt to map the set of tasks to the subset of the nodes included in at least one of the local cluster and the at least one remote cluster using the resource availability received from the at least one node in at least one of the local cluster and the at least one remote cluster by attempting to map all of the tasks in the set of tasks to a single node in at least one of the local cluster and the at least one remote cluster.

20. The first node of claim 17, wherein the resource availability information from the at least one node in the local cluster includes information about the availability of at least one of unused resources available on the at least node within the local cluster and resources that would be available if resources utilized by tasks executing on the at least one node within the local cluster were reduced.

21. The first node of claim 17, wherein the resource availability information from the at least one node in the at least one remote cluster includes information about the availability of at least one of unused resources available on the at least node within the at least one remote cluster and resources that would be available if resources utilized by tasks executing on the at least one node within the at least one remote cluster were reduced.

22. The first node of claim 17, wherein the wireless transceiver comprises a radio frequency transceiver.

23. Software embodied on a tangible medium readable by a programmable processor included in a first node of a wireless network comprising a plurality of clusters, the software comprising program instructions executable on at least one programmable processor included in the first node, the program instructions operable to cause the first node to:

receive an admission request from a client, the admission request requesting that a set of tasks be executed;

forward the admission request to a local cluster head node for the local cluster in order to have at least one node in the local cluster send resource availability information to the first node, wherein the first node is a member of the local cluster;

receive resource availability information from the at least one node in the local cluster;

attempt to map the set of tasks to at least a subset of the nodes included in the local cluster using the resource availability information received from the at least one node in the local cluster; and

if unable to map the set of tasks to the subset of nodes included in the local cluster;

request that the local cluster head node of the local cluster forward the admission request to at least one remote cluster head node of at least one remote cluster included in the wireless network in order to have at least one node in the at least one remote cluster send resource availability information to the first node; and

attempt to map the set of tasks to at least a subset of the nodes included in at least one of the first cluster and the at least one remote cluster using the resource availability received from received from the at least one node in at least one of the first cluster and the at least one remote cluster.

24. The software of claim 23, wherein the program instructions are operable to cause the first node to send a commit message to each of the nodes in the wireless network to which at least one of the tasks is mapped.

25. The software of claim 23, wherein the wireless network comprises an ad hoc wireless network.

26. The software of claim 25, wherein the ad hoc wireless network comprises a mobile ad hoc wireless network.

27. The software of claim 23, wherein the plurality of clusters are defined by the topology of the wireless network.

28. The software of claim 23, wherein the plurality of clusters are defined according to a routing protocol.

29. The software of claim 23, wherein each cluster head node is defined by the topology of the wireless network.

30. The software of claim 23, wherein each cluster head node is defined according to a routing protocol.

31. A first node comprising:

means for sending and receiving data over a wireless network;

means for receiving an admission request from a client, the admission request requesting that a set of tasks be executed;

means for forwarding the admission request to a local cluster head node for a local cluster in order to have at least one node in the local cluster send resource availability information to the first node, wherein the first node is a member of the local cluster;

means for receiving resource availability information from the at least one node in the local cluster;

means for attempting to map the set of tasks to at least a subset of the nodes included in the local cluster using the resource availability information received from the at least one node in the local cluster; and

means for requesting that the local cluster head node of the local cluster forward the admission request to at least one remote cluster head node of at least one remote cluster included in the wireless network in order to have at least one node in the at least one remote cluster send resource availability information to the first node, if unable to map the set of tasks to the subset of nodes included in the local cluster; and

means for attempting to map the set of tasks to at least a subset of the nodes included in at least one of the local cluster and the at least one remote cluster using the resource availability received from the at least one node in at least one of the local cluster and the at least one remote cluster, if unable to map the set of tasks to the subset of nodes included in the local cluster.