Dynamic task allocation and node reconfiguration in mesh network

Patent metadata

Field	Value
Publication number	US-11119825-B2
Application number	US-201715847052-A
Country	US
Kind code	B2
Filing date	Dec 19, 2017
Priority date	Dec 19, 2017
Publication date	Sep 14, 2021
Grant date	Sep 14, 2021

Abstract

A system for allocating tasks within a moving multi-hop mesh network includes a processor operatively coupled to memory. The processor is configured to implement the steps of: sending a bid request from a first network node to two or more other network nodes for computing a task, wherein the first network node has a first geographical location relative to a first geographical location of the two or more other network nodes; in response to the first network node receiving a bid from at least two of the two or more other network nodes for computing the task; predicting a second geographical location for each of the at least two of the two or more other network nodes relative to a second geographical location of the first network node based on the time when the task will be completed; predicting a total task completion time for the at least two of the two or more other network nodes; comparing the total task completion time predicted for the at least two of the two or more other network nodes to generate a winning bid; and allocating the task to the winning bid.

First claim

What is claimed is:

1. A method for allocating tasks to network resources within a moving multi-hop mesh network comprising:
sending a task-compute request from a first network node to two or more other network nodes for computing a task, wherein the first network node and the two or more other network nodes are mobile nodes, wherein the first network node has a first geographical location relative to a first geographical location of the two or more other network nodes, and wherein the first network node and the two or more other network nodes are configured for communication with each other via a communication mesh network;
in response to the first network node receiving a task-compute offer from at least two of the two or more other network nodes for computing the task, predicting a second geographical location for each of the at least two of the two or more other network nodes relative to a second geographical location of the first network node based on a time when the task will be completed;
predicting a total task completion time for the predicted second geographical location of the at least two of the two or more other network nodes comprising:
a time taken for the first network node to send data to the at least two of the two or more other network nodes for computing the task based on the first geographical location;
a computation time for the at least two of the two or more other network nodes to compute the task; and
a time taken for the at least two of the two or more other network nodes to send the output data for the completed task to the first network node from the second geographical location;

comparing the total task completion time predicted for the at least two of the two or more other network nodes to generate an acceptance of the task-compute offer from a given one of the two or more other network nodes; and
allocating the task to network resources to the accepted task-compute offer;
wherein predicting the second geographical location of the at least two of the two or more other network nodes relative to the second geographical location of the first network node is determined according to node mobility information associated with each node in the network, the node mobility information comprising one or more of node trajectory and node speed; and
wherein the steps of the method are performed in accordance with a processor and a memory.

2. The method of claim 1 , wherein each of the first network node and the two or more other network nodes are independently one of a cellular phone, tablet, laptop, desktop computer, drones and robots.

3. The method of claim 1 , wherein each of the first network node and the two or more other network nodes are independently a cellular phone.

4. The method of claim 1 , wherein the step of sending the task-compute request from the first network node to the two or more other network nodes for computing the task comprises receiving location information of the two or more other nodes.

5. The method of claim 1 , wherein the step of sending the task-compute request from the first network node to the two or more other network nodes for computing the task comprises sending communicated messages by one or more of a text message, voice message, audio message, video, data and encrypted message.

6. The method of claim 1 , wherein the step of sending the task-compute request from the at least two of the two or more other network nodes to the first network node comprises sending communicated messages by one or more of a text message, voice message, audio message, video, data and encrypted message.

7. The method of claim 1 , wherein the first geographical location of the first network node and the first geographical location of the two or more other network nodes is determined by a unique identification of the first network node and the two or more other network nodes.

8. The method of claim 1 , further comprising sending a notification that a node's task-compute offer is the accepted task-compute offer, and wherein the notification provides the node with further instruction to proceed with the computed task.

9. The method of claim 1 , further comprising generating a rating system of the two or more other nodes.

10. An article of manufacture to provide optimal aggregation of small-scale energy storage capacity comprising a non-transitory computer-readable storage medium for storing computer-readable program code which, when executed, causes a computer to carry out the steps according to claim 1 .

11. A method for allocating tasks to network resources within a moving multi-hop mesh network comprising:
in response to receiving a task-compute request from a first network node to two or more other network nodes for computing a task, wherein the first network node and the two or more other network nodes are mobile nodes, wherein the first network node has a first geographical location relative to a first geographical location of the two or more other network nodes, and wherein the first network node and the two or more other network nodes are configured for communication with each other via a communication mesh network, sending a task-compute offer from at least two of the two or more other network nodes to the first network node for computing the task;
predicting a second geographical location for each of the at least two of the two or more other network nodes relative to a second geographical location of the first network node based on a time when the task will be completed;
predicting a total task completion time for the predicted second geographical location of the at least two of the two or more other network nodes comprising:
a time taken for the first network node to send data to the at least two of the two or more other network nodes for computing the task based on the first geographical location;
a computation time for the at least two of the two or more other network nodes to compute the task; and
a time taken for the at least two of the two or more other network nodes to send the output data for the completed task to the first network node from the second geographical location;

comparing the total task completion time predicted for the at least two of the two or more other network nodes to generate an acceptance of the task-compute offer from a given one of the two or more other network nodes; and
allocating the task to network resources to the accepted task-compute offer;
wherein predicting the second geographical location of the at least two of the two or more other network nodes relative to the second geographical location of the first network node is determined according to node mobility information associated with each node in the network, the node mobility information comprising one or more of node trajectory and node speed; and
wherein the steps of the method are performed in accordance with a processor and a memory.

12. The method of claim 11 , wherein each of the first network node and the two or more other network nodes are independently one of a cellular phone, tablet, laptop, desktop computer, drone and robot.

13. The method of claim 11 , wherein the step of sending the task- compute offer from the at least two of the two or more other network nodes to the first network node comprises sending communicated messages by one or more of a text message, voice message, audio message, video, data and encrypted message.

14. The method of claim 11 , wherein the first geographical location of the first network node and the first geographical location of the two or more other network nodes is determined by a unique identification of the first network node and the two or more other netw

Assignees

• IBM

Inventors

• Jalali Fatemeh
• Lynar Timothy M
• Suits Frank
• Kolluri Ramachandra Rao

Classifications

• H04L45/00

  Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) · CPC title

• G06F9/5044 Primary

  considering hardware capabilities · CPC title

• G06F9/4875 Primary

  with migration policy, e.g. auction, contract negotiation · CPC title

• H04W40/18

  based on predicted events · CPC title

• H04W40/20

  based on geographic position or location · CPC title