A new resource allocation method in fog computing via non-cooperative game theory

2.1 Cloud computing

Although the emergence of cloud computing is rooted in the scientist’s primary ideas in the scientist in the 60’s, such a name was not proposed for it in those years [6]. The primary view was that all the world people could access in applied programs and their data via a wide communicating network. The first new definition of cloud computing was raised by Prof. Ramanath Chellappa in 1997. In 1999, Salesforce.Com was succeeded in providing applied programs services via a simple website as a pioneer. The 2000’s is the peak of prosperity for cloud computing. In 2009, Amazon provided an Elastic Compute Cloud (EC2) [7]. Afterward, Google and IBM started many research projects on cloud computing in 2007. In 2016, the costs in public commerce of infrastructure based on cloud computing reached more than 100 Billion Pounds, which has been increased by 20% in comparison to 2013 [8]. It is predicted that by the near future, most of the internet services will be accessible via cloud computing services.

2.2 Internet of things (IoT)

Kevin Ashton first raised Internet of Things in 1999. Although the main idea of this technology probably goes back to 70’s [9], this idea, with all its attractiveness, was neglected for about ten years. In 2010, it was realized with Google Street Service. In that year, China announces the strategy of using such technology in his country for up to ten years. Such a concept was considered in 2011 by Gartner as a research company on the market. In 2013, IDC predicted that the share of the Internet of things in the global market would reach 8.9 Trillion Dollars in future [10].

2.3 Fog computing

Fog Computing was first introduced by CISCO, while IBM has raised such technology as edge computing. Anyhow, in Nov. 2015, a consortium named Open Fog [11] was created to make the raised theory in this area real as standard. This consortium was created by Arm, Cisco, Dell, Intel, and Microsoft cooperated with Princeton University, and other members and partners cooperate with it too. According to the definition provided by this consortium, fog computing is a horizontal architecture at the system level which distributes cloud services and resources to compute, save, control, and also network connection in each part of the world among the objects. As regards the expansion of IoT data, which are processed and saved upon cloud computing [12], the fog will be able to do the sensitive computations to the lag near the sensors, which will lead to better efficiency in using the bandwidth of the network and applied and more efficient approaches of IoT [13]. Fog computing increases business agility by using more and more insight; it also increases safety and reduces operational costs. In other words, the following challenges are always raised in realizing IoT applications via cloud computing and communicating models before introducing fog computing.

2.4 Related works

Roy and Bhaumik in [14] discussed matrix games with payoffs as triangular type-2 intuitionistic fuzzy numbers as a modern idea. They argued some policy handling into the free and fair accession of water versus its finite resources.

Bahaumik et al. in [15] focussed on attended a matrix game whose payoffs are triangular intuitionistic fuzzy numbers. The authors also focus on applying a sturdy ranking method to rank fuzzy numbers to solve the matrix game.

Bahaumik et al. in [16] discussed that Uncertainty provides an important in decision-making problems like game theory. The authors’ main aim was to validate and authorize the proposed contemplations by applying them to illuminating real-life problems in the neutrosophic realm through bi-matrix game theory.

Bhaumik et al. in [17] studied the Prisoners’ dilemma game to solve human trafficking that is one of the most rising problems of today’s society. With the use of Nash equilibrium in the non-zero-sum game, the authors can earn results that were Ideal Solution.

Bhaumik and Roy in [18] discussed enhance many problems in doubt and ambiguity in nature; then, the authors proposed a matrix game to solve.

Bhaumik et al. in [19] discussed on expand and analyzing a matrix game with multiple objectives. The authors solve the problem under a single-valued neutrosophic environment in a linguistic approach.

Brikama et al. in [20] proposed the intuitionistic fuzzy set practically in different decision-making; the primary goal of this paper is to extend an approach for solving multi-criteria matrix games. Finally, these matrix games’ results are compared with the existing algorithms to show the advantages of this algorithm.

Ammar et al. in [21] discussed solving the zero-sum two-person continuous differential games using a rough programming approach. At last, with a numeral instance affirm the theoretical outcome.

Brikama et al. in [22] proposed a robust fuzzy multi-objective programming algorithm to solve curb matrix games with payoffs of fuzzy rough numbers. A significant benefaction of this paper is that it deals with restriction matrix games using two types of uncertainties, and so the operation of decision-making is more pliable.

Zhang et al. in [23] proposed a three-layer hierarchical game framework to solve the challenges of the developed fog computing networks. This paper’s proposed framework uses the Stackelberg game for the interaction between DSO and DSS and the ethical risk model for the interaction between DSO and FN, and the resource allocation for the interaction between FN and DSS.

Cao et al. in [24] proposed a FAST system, a distributed analytical system via Fog computing to monitor the fall detection system. The authors developed a set of fall detection algorithms, including algorithms based on measuring acceleration, analytical methods of temporal series, and filter-ing methods to assist fall detection. They designed a real-time fall detection system based on Fog computing, which divided the fall detection duty among edges and cloud. The proposed system has reached higher features and sensitivity in real-time data. However, the response time and energy consumption were near to available efficient approaches.

The other use of fog computing in health care was proposed by Stantchev et al. in [25]. They provided a three-level architecture for smart healthcare infrastructure. The approach is based on a service-oriented architecture and extends established architecture to provide an efficient architecture for applied health care and eldercare programs.

Augmented reality applied programs are compassionate to delay, and even minimal delays can damage the user’s experience. Zao et al. in [26] made an interactive computer game of augmented brain based on fog computing and combined data. When the person played this game, the natural flows of gathered data by EEG sensors will be produced and classified and help detect the player’s brain states.

Zhu et al. in [27] discussed the use of edge servers to improve websites’ performance, and users were connected to the Internet through fog nodes. Any user-generated HTTP request then had to go through the fog. The fog tool performed several optimizations that reduced the user waiting time to load the requested website.

Botta et al. in [28] studied the aggregation of cloud computing and the Internet of Things services. Their paper focused on integrating cloud and Internet of things, which is called Cloud loT pattern. They wrote many works separately on the Internet of things and cloud, which summarized their main features, properties, infrastructural technologies, and open issues on these two areas precisely.

The need for fog computing to create distributed intelligence on the Internet through various topics were reviewed by Byers and Wetterwald in [29]. This article discusses why distributed information is necessary. Various reasons such as scalability, protection of network resources, closest control circle, traction mode, and clustering were suggested as distributed intelligence reasons. And then, the role of real-time data analysis was discussed.

Datta et al. in [30] activated customer-centric Internet services in a fog-based model. This article stated that due to fog computing’s proximity to end-users, resistance to geographical distribution, and high mobility support, fog computing could provide services with reduced latency and improved quality service. Therefore, fog computing is becoming one of the most critical capabilities for the Internet of Things.

Aazam and Huh in [31] pointed out that the novelty, inclusiveness, and being present everywhere of the computing services were considered by the researchers and developers of these services. They pointed that since different tools produce different types of data with different frequencies and since some of the data services like emergency, health and care services, and other similar services are real-time, the response time will be very vital. Meanwhile, decision-making is necessary on the type of data that should be loaded inside the cloud with no trouble to the network and cloud. Therefore, fog computing plays a vital role in this regard.

Aazam and Huh in [32] provided a model that covered the issues related to predicting resources, type of consumer-based on estimating and reserving resource, advanced reserving and pricing for IoT consumers based on their details.

Agarwal et al. in [33] claimed that cloud computing’s primary motivation is optimizing resource consumption, maximizing efficiency, and minimizing the response time. Meanwhile, they stated that regarding the availability of some limitations in cloud computing and to overcome this limitation, fog computing was raised. In this paper, the authors studied the virtualization methods, identifying different problems, probable threats, and attacks for virtualization, and they proposed architecture based on cloud-fog to allocate stretchable resources.

Do et al. in [34] considered the evolving problem of allocating common resources and minimizing the problem of carbon trace for mainstreaming video service in fog computing. They created a distributed algorithm based on a proximal algorithm and alternate multiplication method to solve a big scale.

Sun and Zhang in [35] proposed a fog computing structure and a public budget algorithm to integrate additional resources into the network. Also, to encourage more resource holders to share their resources with the resource pool and monitor resource sponsors while actively performing their tasks, they proposed an incentive mechanism in this algorithm.

3.1 Proposed method

The data centers or clouds in big scales are usually made in far distant regions or regions away from DSS. It leads to high transferring cost, transfer density, and delay in service, which could be non-acceptable for instant interaction programs. In this regard, the closest cloud to the users is essential and useful. Therefore, in fog computations, several low-cost computing devices are put in network edges to load data computing services from the cloud, usually known as fog nodes (FNs). Regarding the supporting property on a small scale, low support, and FNs construction cost, these FNs could be used a lot in the network. FNs are generally located very close to DSSs and therefore can provide low-delay and quick-response services to the requests, while the most crucial challenge in this regard is allocating FN-limited computational resources to all DSSs to reach desired and sustainable function. An algorithm based on a non-cooperative game algorithm based on combining two auction algorithms and the Nash equilibrium was used to solve this challenge. In this regard, this section is composed of descriptive parts of game theory, its detailed investigation in the research, presenting proposed approach, stating the problem based on the optimal allocation of resource, formulating the problem to do the computation, and describing the non-cooperative game theory algo-rithm and combining algorithm of Nash equilibrium and auction algorithm.

3.2 Suggested solution

In this research, a special fog computing network composed of a set of Data Service Operators (DSOs) has been considered, and each controls a set of fog nodes to provide essential data services to the Data Service Subscribers (DSSs). The most crucial challenge in this regard is the manner of allocating FN-limited computational resources to all DSSs to reach the desired and sustainable function. Therefore, this research presents a common optimization framework for all FNs, DSOs; having used DSSs based on non-cooperative game algorithms and basing on combined auction algorithm and Nash equilibrium, an optimal resource allocation algorithm was presented.

The proposed method could be expressed as four following parts:

Statement of the problem: this part will be dealt with describing the problem based on DSS, DSO, and FN.

Formulating the problem based on the presented relationship: this part will be dealt with formulating and studying the mathematical relationship in this regard.

Non-cooperative game algorithm to allocate resources: this part will study the non-cooperative game algorithm and the Nash equilibrium to reach the best strategy.

Auction algorithm for allocating resources: the final part will study the auction algorithm for optimizing the responses obtained from the Nash equilibrium algorithm if it is possible.

3.3 Statement of the problem

In fog computations, several low-cost computing devices are considered FN, which are put in a network edge to load data computing services from the cloud. FNs are generally located very near to DSSs.

Since many of the FNs and their computational resources are invisible for DSSs. DSSs could only contact DSO and purchase the data services and could not directly request from FNs. Therefore, there is a virtual network between DSO and DSS. In receiving the request of services from all DSSs, each DSO can collect the computational resources from FNs and provide virtual data services for DSSs. Regarding the networks requirement, each DSO can allocate a different amount of computation resources from different FNs to different DSSs. Therefore, computation resources could be used effectively by neighbor DSSs.

Fog computing networks could be many FNs that are put in different locations by different DSOs to provide services to DSSs. When DSSs could choose their DSO and related FNs to increase their quality, allocating fog node resources in DSSs is a significant challenge. This research focuses on choosing resources and allocating resources among FNS, DSOs, and DSSs.

In this architecture, DSOs prioritize the price of their services, and DSSs purchase an optimal number of Computational Resource Blocks (CRB). When the price of DSOs and purchased resource of DSSs were obtained, each DSS will know how many CRB is required and then can compete with CRBs belonged to neighbor FNs. In this regard:

The proposed algorithm should choose the proper DSO for DSS.

At the next stage, DSO should choose proper FNs.

Moreover, at the final stage, FN will choose optimal CRB.

3.4 Formulating problem and studying mathematical relationships

This part will be deal with mathematical relationships. In the first equation, the obtained income of DSO is computed based on chosen DSSs, which have received their services from DSO. It is displayed in Equation (1) [1]. This equation computes the income when DSSs are directly connected to DSOs and is computes the income when DSS uses DSO directly. w j s = ∑ i = 1 M τ ij ( α i λ i - β j q j r i - γ j t j )(1)

Where M is the number of DSSs and if τ _ij chooses DSS _i , DSO _j , it will be one, and otherwise, it will be zero. α _i λ _i shows the income obtained from sent works by DSS _i in λ _i sent rate. q _j r _i is the whole cost of using DSS _i from DSO _j . β _j shows the proportional coefficient for the effectiveness of using DSS _i from DSO _j . t shows the delay cost for DSS _i by DSO _j . γ _j is the proportional coefficient for the effectiveness of delay cost. If DSSs receive their services from FNs related to DSO, the obtained gain is computed as the difference of the income obtained for each DSO from DSSs with FNs costs and consumed energy and therefore, the income equation will be as Equation (2) [1]. w i d = ∑ j = 1 N τ ij ( r i q j ) - ∑ k = 1 K p k q ik fd - e i q i 0(2)

Where ∑ i = 1 M τ ij ( r i q j ) is the receiving cost of DSO _j from DSS _i and ∑ k = 1 K p k q ik fd is the paid cost of all FNs that choose DSO _j . e i q i 0 is the energy cost of DSO _j . In this equation, the gain is computed upon being influenced by FNs. In fact, Equation (1) computes the DSO income based on using DSS from DSO as directly, and Equation (2) computes the DSO income based on using DSSs from FN, and according to Equation (2), r _i is computed as Equation (3). r i = γ j β j ( μ t th - λ i λ i ) 2(3)

Where μ is the data transfer rate from CRBs as processing unit of FNs to DSOs, in Equation (4) [1], the final gain is computed upon considering the reward obtained from the relationship between DSS and FNs, and this reward is in fact the reduction cost of DSO upon using FNs subtracted from the relationship cost between DSS and FN. w k f = ∑ k = 1 M η ki f ( p k - c kj ) q kj fs(4)

According to Equation (4), ∑ i = 1 M η ki f p k q kj fs is the reduced cost of DSO _k upon using FN _f . ∑ i = 1 M η ki f c kj q kj fs is data transfer cost from DSS _j to FN _k node. In fact, this equation computes the final gain of DSS of a DSO while using related FNs.

In this regard, this problem is composed of three target functions, and all three functions should have the most value. All three W should have the most value so that the DSO could reach the highest income and DSS could receive the best services from the chosen DSO. In continuing, we will describe the non-cooperative game algorithm to increase the value of Ws.

In this part, the most basic concept of the logical game that is the dominant strategy and eliminating defeated strategy is considered for the non-cooperative game; in this work, the dominant strategies are allocating optimal DSS, FN, and DSOs. The dominant strategies show optimal allocation with the highest W value, and the defeated strategy is the strategies that obtained the lowest W value. Each strategy in this research is as the Table 1.

Table 1 shows a sample of a strategy based on seven DSO, nine FN, and eight DSS. When a DSS chooses a DSO, it can receive its services from FNs of that DSO or the DSO itself.

Each game, like any other problem, includes a work area in optimization. In this article, game dimensions are for the numbers of DSS, DSO, FN, and Nash equilibrium, which is the primary goal of optimization based on game theory is computed based on this number. Therefore, each chosen strategy is a combination of allocating DSSs to DSOs and FNs to DSOs, which is displayed as a non-cooperative game, and each player improves its strategy according to the Nash equilibrium and finds optimal responses for the raised problem.

In fact, Nash equilibrium is a profile of strategies where each player could not increase his utility upon individual changing of his strategy. The other point of Nash equilibrium is that at such point, each user gives a better response to a set of strategies of his competitors. In this regard, Equation (5) [36] is used.

B i ( a - i ) = { a i ∈ A i : u i ( a i , a - i ) ⩾ u i ( a i ′ , a - i ) , ∀ a i ′ ∈ A i }(5)

According to Equation (5) a_-i is the strategy of the opponent i players, a _i i’th player strategy. a i ′ is Another strategy of i’th player or the same strategy of i’th player. A _i is the i’th player strategy set. B _i  (a_-i) represents the set of all strategies for player i’th best response.

In this paper, the Nash equilibrium is created upon combining the competitor strategies and creating new strategies. In this regard, the random matrix of zero and one is created, and two strategies are chosen randomly and create a new strategy for the players. Tables 2–4 create new strategy (Mask: 0100100).

This algorithm is based on the best optimal function value. According to this algorithm, when a new resource is allocated for being chosen, the function related to FN, DSS, and DSO are computed. If the obtained function values based on the optimal system is better than other strategies, it eliminates all the previous strategies as the dominant strategy; therefore, the system will have less memory and low computational load and having chosen the list of strategies by the Nash equilibrium algorithm, only the dominant strategy will be remained in the list which will optimize the system and it could be assured that the best resource allocation will be done.