Patent ID: 12244517

DETAILED DESCRIPTION

In the drawings, like reference numerals designate identical or corresponding parts throughout the several views. Further, as used herein, the words “a,” “an” and the like generally carry a meaning of “one or more,” unless stated otherwise.

Aspects of this disclosure are directed to a system and method for computational resource management in fog-based Internet of Things networks. The method uses three different components in the network including IoT nodes, Fog node controllers and Fog nodes. The IoT node generates tasks and assigns a priority to each task. The fog node controller maintains a signal strength table for each IoT node to fog node transmission. The fog node controller runs a matching technique to associate IoT nodes with the fog nodes. Further, the fog nodes also run a 0/1 Knapsack algorithm to assign tasks in its fog node queue to the current computational cycle. The developed method reduces the computational delay of tasks.

The disclosed system and method provide a solution to IoT environments that involve execution of urgent tasks among a large number of tasks.

FIG.2is a diagram of software modules for computational resource management in a Fog-based IoT network. There are three major modules in the network. The first module is the IoT node204that generates different application-related tasks. The second module is the fog nodes202that have provided their computing resources to the IoT nodes204and compute tasks on behalf of the IoT nodes204. The third module is the Fog node controller212which is a central server placed in the network. The role of the fog node controller212is the attachment of tasks to the fog computing nodes202.

At first, the IoT nodes204generate their tasks each of which has different sizes (in terms of bytes) and has different computing requirements (in terms of number of cycles). Each IoT node204also assigns a priority to its tasks. This priority is based on how urgent the task computation is. For example, in an industrial IoT network, machine failure-related tasks are urgent whereas tasks related to regular machine status are not of high urgency. In one embodiment, the tasks are divided into three levels of priority namely, low, medium, and high. It is understood that the levels of priority can be more than these three levels, such as low, medium-low, medium, medium-high, and high. The levels of priority can include an Emergency level as well. These two functionalities of IoT nodes are depicted inFIG.2.

The fog controller node212is the second component in the network. It maintains a table of signal strengths of all IoT-fog node pairs. This signal strength is initially calculated based on the distance between two nodes and a received power formula in wireless communications. The position information of IoT nodes is transmitted as part of task generation request to the fog controller. Once the network is set up, the actual signal strengths when data is shared between IoT devices and fog servers are determined and average signal strength is maintained. The second responsibility of the fog node controller212is to use the matching technique to associate IoT devices with the best fog servers. This is done by using a stable matching algorithm.

The third component of the network is the fog server node202. The fog server node212has two major responsibilities. The first is that it applies a Knapsack algorithm using received (offloaded) tasks and finds the order of tasks that will be executed in the current cycle duration. In other words, the size of the knapsack is the number of cycles that a fog server202can use to compute tasks. Each fog server202only has a certain number of cycles that can be used to compute tasks in parallel. The remaining tasks are moved for execution in the next cycle. The second functionality of the fog server202is that it executes the tasks and sends back the results to the IoT nodes204.

The steps of the task computing algorithm are shown in the flowchart ofFIG.3. In the task computing algorithm, tasks are allocated to minimize the transmission delay while keeping in view task priority. The task computing algorithm uses stable matching with preference profiling to reduce transmission delay. A preference profile is developed for both IoT nodes and fog nodes. At IoT nodes, signal strength and fog node available computational capacity are used to generate a IoT preference profile. Similarly, at the fog nodes, task priority and task generation time are used to assign preference order. The preference profile reduces task computation delay.

In performing the offloading, a single atomic task is offloaded to a single fog node. The Fog Node Controller212has a resource allocation algorithm embedded in its hardware.

Referring toFIG.3, the task computing algorithm is described as follows:

Step S302: Task Generation Executed in Each IoT Node

This step is performed by the IoT nodes204. Different application-related tasks are generated by IoT nodes204, and they require computation.

Step S304: Signal Strength Table Generation

This step is executed on the Fog Node Controller212. The signal strength is evaluated for each IoT-Fog node pair. The signal strength (SS) can be evaluated by

SS=Transmit⁢Power×Antenna⁢gains×λ2(4⁢π⁢D)2(1)
Here, transmit power is of the wireless transceiver of IoT Antenna gains are the product of transmitter side and receiving side antenna gains.Δ is the wavelength of the signal.D is the distance between the IoT devices and fog servers.
Step S306: IoT Fog Node Associating Using a Stable Matching Algorithm, Executed on Fog Node Controller212.

In this step, the IoT nodes204are associated with fog servers202utilizing the stable matching algorithm as shown in the flowchart ofFIG.4. The algorithm used for stable matching is utilized to assign several IoT nodes204per single fog node202. Here the preference profiles are calculated as follows:

Preference Profile of IoT Nodes

IoT nodes204use signal strength as a measure of their preference order towards the fog node202. This is because IoT nodes want to select fog nodes that have the highest signal strength and data rate so that the transmission time of the task is reduced.

Preference Profile of Fog Nodes

Fog nodes202use signal strength divided by the task size (in bytes) as a measure of their preference order towards the IoT nodes204. This is because fog nodes202have a preference to select tasks with the highest signal strengths and also tasks that are smaller in size to conserve their computational power.

Finally, IoT tasks are assigned to the fog servers202with the help of a matching algorithm and tasks are offloaded for computation. IoT nodes transmit their task to the allocated fog node using 5G wireless communication technology.

Step S308: Task Computation Order Using 0/1 Knapsack Algorithm

In this step, the task computation order at each fog node202is established using the0/1Knapsack algorithm as shown inFIGS.5A,5B. The knapsack algorithm is performed on each Fog node202.

Step S310: Task Execution

In this step, fog nodes202execute the selected tasks from step S308in the current cycle set.

FIG.4is a flowchart of the IoT-Fog Node association algorithm using a stable matching algorithm, herein referred to as the stable matching algorithm. The stable matching algorithm is executed in the Fog node controller212and begins with preference generation steps. Step S402generates a preference list of all IoT tasks for each fog node using signal strength. Step S404generates a preference list of all fog nodes for each IoT task using a ratio of signal strength and task size (bytes).

The Fog node controller212can initialize each IoT task I in set T and fog node resource f in set F to be free. In S406, a decision is checked as to whether any IoT task in set T is free. While true in S406, in S410, a decision is made as to whether f is not engaged with any other node (where in S408, f is a top fog node in the preference list of I whom it has not proposed). If true in S410, in S416, allocate I to be matched with f.

Otherwise, in step S412, a decision is made as to whether f has i at a higher preference order than its current allocation i′. If true at S412, in step S420, allocate i to be matched with f, and in step S422, assign i′ to be not engaged to any node. If not true at step S412, in step S414, f does not accept the proposal of i.

At a point, where the decision at step S406is no longer true, in step S418, the algorithm performed on the Fog node controller212returns the resulting IoT-Fog node association.

FIGS.5A and5Bis a flowchart of task computation order selection executed on a Fog node for each IoT device. A Knapsack algorithm is used to find the task computation order. In the Knapsack algorithm, task size, task priority and task generation time are considered to allocate computation cycles of fog nodes to the IoT tasks. The task computation order algorithm is based on a 0/1 Knapsack algorithm. The knapsack algorithm is a resource allocation algorithm where a choice is made from a set of tasks under a time constraint, in particular number of processing cycles of a fog node. In the0/1Knapsack algorithm, the number of copies of each kind of task is restricted to zero or one. The algorithm fills the knapsack so that the sum of the values of tasks is less than or equal to the knapsack's capacity.

The flowchart is drawn to simplify the amount of information in each block. In the flowchart, C represents the current processing cycle, t represents the task number, T represents the maximum number of tasks, FP represents the processing cycles of a fog node, TP represents the task priority, xt, c represents the cell value of task t and cycle c, Pt represents the total processing cycles required by task t.

FIG.5Ais a flowchart of a knapsack table filing method. In step S502, the cell value of task t and the processing cycles of the fog node FP are initialized to 0.

In S504, a decision is made to determine if the task number t has exceeded the maximum number of tasks T.

While the task number t is less than of equal to the maximum number of tasks T (No in S504), in step S506, a decision is made as to whether the current processing cycle C is greater than the processing cycles of the fog node FP.

While the current processing cycle C is less than or equal to the processing cycles of the fog node FP (NO in S506), in S508, a decision is made as to whether Q is greater than the current processing cycle C. If true (YES at S508), in step S510, the value of the current cell will be filled with the same value of its upper cell value. In step S516, the current processing cycle is incremented, and the process goes back to step S506.

In step S508, when Q becomes less than or equal to the current processing cycle C (NO in S508), in step S512, a decision is made as to whether the task priority TP+cell value of task t and cycle c is greater than a cell value a cycle c.

If true (YES at S512), in step S514, fill the cell with the combined value of task priority and the specific cell value placed in the upper row. In step S516, the current processing cycle is incremented, and the process goes back to step S506.

If the decision at step S512is false (NO at step S512), in step S518, fill the cell with the same as mentioned in the upper row with same column (Xt−1,C), the process goes to step S516, to increment the current processing cycle, and repeat S506.

The process is repeated until the current processing cycle C is greater than processing cycles of frog node FP (YES at S506). In step S520, the task number is incremented, and the decision step S504checks whether the task number exceeds the maximum number of tasks T.

When step S504determines that the task t is greater than the maximum number of tasks T (YES at S504), in S522, the knapsack table has been filled.

FIG.5Bis a flowchart of a method of task selection from the knapsack table.

In step S532, the task number t and current processing cycle C are initialized.

In step S534, the cell value at t, C are set to maximum task number T and processing cycles of frog node FP.

In step S536, a decision is made as to whether the cell value at t, C is greater than the cell value at t−1, C. If the decision is true (YES at S536), in step S538, a task is selected.

Otherwise (NO in S536), in S540, task number t is incremented. In step S544, task number t is set to task number t*1l[t−1] and current processing cycle C is set to C*Ct.

In step S542, a decision is made as to whether task number has reached 0 or current processing cycle has reached zero. If not (NO at S542), the process returns to step S536.

Otherwise (YES in S542), in S546, all tasks have been selected, and the task computation order is established.

Task offloading pertains to moving compute tasks to an external computing device to be performed on that device. IoT devices may include microprocessor-based controllers with limited storage, for storing a program of a size, and sub-optimal processing speed, in cycles per unit time. Subsequently, processing for large tasks has tended to be offloaded for processing in the cloud. However, offloading to the cloud suffers from latency and sometimes communication reliability issues. Fog computing brings an external computing resource closer to the IoT environment which greatly reduces latency, but is not without its own resource allocation issues. The disclosed Fog computing solution involves offloading tasks from disparate types of IoT devices to Fog servers, which themselves have limited resources.

The disclosed Fog computing approach to offloading IoT tasks to Fog servers is applicable to various types of IoT systems, ranging from smart homes to smart cities, smart power grids, and specialized systems such as video surveillance and healthcare. The disclosed Fog computing approach can facilitate storage and computational services in future 6G networks.

A smart home may consist of a technology-controlled ventilation and heating system such as the Nest Learning Thermostat, smart lighting, programmable shades and sprinklers, smart intercom systems to communicate with people indoors as well as those at the door, and an intelligent alarm system. The disclosed Fog computing approach can be used to create a personalized alarm system. It can also be used to automate certain events, such as turning on water sprinklers based on time and temperature.

Smart power grids are being implemented to help control power routing and monitor power usage. Smart power grids typically rely on the Internet for control and data communication. The disclosed Fog computing approach can be used to offload control functions and data storage to Fog nodes to enable localized power usage monitoring and control.

Smart cities are being considered to automate various services, from garbage collection to traffic management. The disclosed Fog computing approach is particularly applicable when it comes to traffic regulation. Sensors can be set up at traffic signals and road barriers for detecting pedestrians, cyclists, and vehicles. Speedometers can measure how fast vehicles are traveling and other motion and proximity sensors can serve to warn of potential dangerous conditions. These various sensors can use wireless and cellular technology to collate data. The disclosed Fog computing approach can be used to operate traffic signals to automatically turn red or stay green for a longer time based on the information processed from these sensors.

The disclosed Fog computing approach can be used in video surveillance, as video is complex to handle at the video camera device and continuous streams of videos are large and cumbersome to transfer across networks to the cloud. The nature of the involved data results in latency problems and network challenges. Costs also tend to be high for storing media content. Video surveillance is used in shopping areas and other large public areas and has also been implemented in the streets of numerous communities. Using the Fog computing approach, computing offloaded to Fog nodes can detect anomalies in crowd patterns and automatically alert authorities if they detect certain actions in the video footage.

The healthcare industry is one of the most governed industries, with regulations such as HIPAA being mandatory for hospitals and healthcare providers. The healthcare industry is always looking to innovate and address emergencies in real-time. Emergencies can arise in a hospital facility, such as a drop in vitals, or can occur at a patient's home. Data from wearables, blood glucose monitors, and other health apps can be monitored in the IoT devices to look for signs of bodily distress.

However, these monitoring functions may require complex processing in order to identify a potentially critical situation. The disclosed Fog computing approach can be applied to offload the complex processing task to Fog nodes without latency issues that may be critical in a situation, such as a stroke. As an example, in one embodiment, wherein the IoT environment is a healthcare environment, a wireless device includes an associated a heart monitor. The heart monitor monitors heart condition and when the condition indicates a potential critical condition, the wireless device associated with the heart monitor will assign a priority of urgent to a heart condition identification task to be offloaded to a Fog server. The invention enables all health-related tasks to be computed in a timely manner while maximizing the utilization of the fog node computing resources. The invention will allow computing load at the fog nodes to be efficiently managed and hence, fog nodes will enhance quality of service in terms of low task computing time.

In an industrial IoT application, machine health monitoring is critical for timely maintenance of machines. Machines can be wireless devices and their fault diagnosis related tasks can be offloaded to fog nodes. Fog servers can be placed to timely compute fault diagnosis tasks and provide maintenance related feedback about the machines.

FIG.6illustrates details of the hardware description of a computing environment according to exemplary embodiments. InFIG.6, a controller700is described is representative of the system in which the controller is a computing device which includes a CPU701which performs the processes described above. The process data and instructions may be stored in memory702. These processes and instructions may also be stored on a storage medium disk704such as a hard drive (HDD) or portable storage medium or may be stored remotely.

Further, the present disclosure is not limited by the form of the computer-readable media on which the instructions of the inventive process are stored. For example, the instructions may be stored on CDs, DVDs, in FLASH memory, RAM, ROM, PROM, EPROM, EEPROM, hard disk or any other information processing device with which the computing device communicates, such as a server or computer.

Further, the present disclosure may be provided as a utility application, background daemon, or component of an operating system, or combination thereof, executing in conjunction with CPU701,703and an operating system such as Microsoft Windows 7, Microsoft Windows 10, UNIX, Solaris, LINUX, Apple MAC-OS and other systems known to those skilled in the art.

The hardware elements in order to achieve the computing device may be realized by various circuitry elements, known to those skilled in the art. For example, CPU701or CPU703may be a Xenon or Core processor from Intel of America or an Opteron processor from AMD of America, or may be other processor types that would be recognized by one of ordinary skill in the art. Alternatively, the CPU701,703may be implemented on an FPGA, ASIC, PLD or using discrete logic circuits, as one of ordinary skill in the art would recognize. Further, CPU701,703may be implemented as multiple processors cooperatively working in parallel to perform the instructions of the inventive processes described above.

The computing device inFIG.6also includes a network controller706, such as an Intel Ethernet PRO network interface card from Intel Corporation of America, for interfacing with network760. As can be appreciated, the network760can be a public network, such as the Internet, or a private network such as an LAN or WAN network, or any combination thereof and can also include PSTN or ISDN sub-networks. The network760can also be wired, such as an Ethernet network, or can be wireless such as a cellular network including EDGE, 3G, 4G, 5G, or 6G wireless cellular systems. The wireless network can also be WiFi, Bluetooth, or any other wireless form of communication that is known.

The computing device further includes a display controller708, such as a NVIDIA GeForce GTX or Quadro graphics adaptor from NVIDIA Corporation of America for interfacing with display710, such as a Hewlett Packard HPL2445w LCD monitor. A general purpose I/O interface712interfaces with a keyboard and/or mouse714as well as a touch screen panel716on or separate from display710. General purpose I/O interface also connects to a variety of peripherals718including printers and scanners, such as an OfficeJet or DeskJet from Hewlett Packard.

A sound controller720is also provided in the computing device such as Sound Blaster X-Fi Titanium from Creative, to interface with speakers/microphone722thereby providing sounds and/or music.

The general purpose storage controller724connects the storage medium disk704with communication bus726, which may be an ISA, EISA, VESA, PCI, or similar, for interconnecting all of the components of the computing device. A description of the general features and functionality of the display710, keyboard and/or mouse714, as well as the display controller708, storage controller724, network controller706, sound controller720, and general purpose I/O interface712is omitted herein for brevity as these features are known.

The exemplary circuit elements described in the context of the present disclosure may be replaced with other elements and structured differently than the examples provided herein. Moreover, circuitry configured to perform features described herein may be implemented in multiple circuit units (e.g., chips), or the features may be combined in circuitry on a single chipset, as shown onFIG.7.

FIG.7shows a schematic diagram of a data processing system, according to certain embodiments, for performing the functions of the exemplary embodiments. The data processing system is an example of a computer in which code or instructions implementing the processes of the illustrative embodiments may be located.

InFIG.7, data processing system800employs a hub architecture including a north bridge and memory controller hub (NB/MCH)825and a south bridge and input/output (I/O) controller hub (SB/ICH)820. The central processing unit (CPU)830is connected to NB/MCH825. The NB/MCH825also connects to the memory845via a memory bus, and connects to the graphics processor850via an accelerated graphics port (AGP). The NB/MCH825also connects to the SB/ICH820via an internal bus (e.g., a unified media interface or a direct media interface). The CPU Processing unit830may contain one or more processors and even may be implemented using one or more heterogeneous processor systems.

For example,FIG.8shows one implementation of CPU830. In one implementation, the instruction register938retrieves instructions from the fast memory940. At least part of these instructions are fetched from the instruction register938by the control logic936and interpreted according to the instruction set architecture of the CPU830. Part of the instructions can also be directed to the register932. In one implementation the instructions are decoded according to a hardwired method, and in another implementation the instructions are decoded according a microprogram that translates instructions into sets of CPU configuration signals that are applied sequentially over multiple clock pulses. After fetching and decoding the instructions, the instructions are executed using the arithmetic logic unit (ALU)934that loads values from the register932and performs logical and mathematical operations on the loaded values according to the instructions. The results from these operations can be feedback into the register and/or stored in the fast memory940. According to certain implementations, the instruction set architecture of the CPU830can use a reduced instruction set architecture, a complex instruction set architecture, a vector processor architecture, a very large instruction word architecture. Furthermore, the CPU830can be based on the Von Neuman model or the Harvard model. The CPU830can be a digital signal processor, an FPGA, an ASIC, a PLA, a PLD, or a CPLD. Further, the CPU830can be an x86 processor by Intel or by AMD; an ARM processor, a Power architecture processor by, e.g., IBM; a SPARC architecture processor by Sun Microsystems or by Oracle; or other known CPU architecture.

Referring again toFIG.7, the data processing system800can include that the SB/ICH820is coupled through a system bus to an I/O Bus, a read only memory (ROM)856, universal serial bus (USB) port864, a flash binary input/output system (BIOS)868, and a graphics controller858. PCI/PCIe devices can also be coupled to SB/ICH888through a PCI bus862.

The PCI devices may include, for example, Ethernet adapters, add-in cards, and PC cards for notebook computers. The Hard disk drive860and CD-ROM866can use, for example, an integrated drive electronics (IDE) or serial advanced technology attachment (SATA) interface. In one implementation the I/O bus can include a super I/O (SIO) device.

Further, the hard disk drive (HDD)860and optical drive866can also be coupled to the SB/ICH820through a system bus. In one implementation, a keyboard870, a mouse872, a parallel port878, and a serial port876can be connected to the system bus through the I/O bus. Other peripherals and devices that can be connected to the SB/ICH820using a mass storage controller such as SATA or PATA, an Ethernet port, an ISA bus, a LPC bridge, SMBus, a DMA controller, and an Audio Codec.

Moreover, the present disclosure is not limited to the specific circuit elements described herein, nor is the present disclosure limited to the specific sizing and classification of these elements. For example, the skilled artisan will appreciate that the circuitry described herein may be adapted based on changes on battery sizing and chemistry, or based on the requirements of the intended back-up load to be powered.

The above-described hardware description is a non-limiting example of corresponding structure for performing the functionality described herein.

Numerous modifications and variations of the present disclosure are possible in light of the above teachings. It is therefore to be understood that the invention may be practiced otherwise than as specifically described herein.