and high-reliability, in a highly dynamic scenario [1], [2]. Fog/edge computing, which enables computing anywhere along the cloud-to-thing continuum, is seen as the way forward to meet these stringent requirements [3], [4]. In [31], fog learning is proposed to distribute machine learning (ML) model training from devices to cloud servers and compensate the limitations of centralized ML for battery-limited devices, and latency-sensitive and privacy sensitive applications. These use cases need reliable communication links that have low probability of failure to achieve low latency. Many works [32] have analyzed the performance in terms of reliability but without specific solutions to improve it. Akbar et al. [6] estimate the reliability level of links using a k-nearest neighbor algorithm and an adaptive decision mechanism to select the best path for different types of applications. However, the dynamic nature of fog/edge architectures with services hosted within smartphones, gateways, and user-provided access points results in uncertain link availability, which must be considered when selecting a reliable path. Furthermore, with the rapidly increasing connectivity demands, spectrum resources are becoming scarce and thus, solutions to enhance the reliability must account for spectrum availability as well.

The incorporation of cognitive radio capabilities into fog/edge architectures has attracted much attention recently due to its ability to increase spectrum efficiency and throughput by unleashing multiple access opportunities at the network edge [3], [7]- [8]. In our previous works [3], [5], [7] we presented a self-organized data and spectrum trading algorithm to harvest available resources at the network edge, improving significantly the revenue of the operator. Si et al. [8] studied proactive caching of popular video contents over harvested bands to maximize the spectrum utilization. By a proper design, the multiple access opportunities can be used to increase the robustness of the network defined as the probability that the network remains connected under traffic dynamics. Achieving a high network robustness is crucial to reconfigure the connections on time by jointly allocating available channels and fog nodes to meet high reliability and low latency requirements at the network edge.

Resource allocation and service provisioning under fog/edge architectures have been studied in several works [9]- [12]. Gu et al. [9] investigated the joint radio and computational resource allocation to satisfy user QoS and proposed a matching game framework to solve the problem. Wang et al. [10] studied joint computation offloading and content caching as a convex problem, and solved it with the alternating direction method of multipliers (ADMM). These problems are solved either in static environments or by adapting static algorithms to the network dynamics and developing heuristic algorithms. Recently, ML has emerged as a powerful tool to make fog/edge computing highly adaptable and enable fast-reconfiguration [13]- [16]. Abdulkareem et al. [13] addressed the use of ML for autonomous intelligent management and operation in fog-aided IoT. Chen et al. [14] studied proactive network association and anticipatory mobility management through ML. In [15], a traffic-flow prediction algorithm based on a long short-term memory (LSTM) was presented to predict and control the mobile-traffic flow of the entire network. Sun et al. [16] presented a task offloading algorithm for vehicular edge computing systems based on Multi-Armed Bandits (MAB) that enabled vehicles to learn the offloading delay performance of their neighboring vehicles. However, none of the above papers provided solutions to improve the connection reliability in cognitive fog/edge networks given the network dynamics nor to reduce the impact of the latter on the latency. Predicting the connectivity availability will reduce the number of reconfigurations needed and improve the resource utilization since fewer resources will be wasted due to link failures. Besides, we can reinforce the connections by keeping channels and fog nodes with high availability probability as backups to meet the most stringent requirements.

In this paper, we contribute to the reinforcement of fog/edge networks by presenting a robustness control framework to access dynamically varying resources at the network edge using fog nodes, and serve applications with low-latency and high-reliability requirements. In particular, the main contributions of this work are the following: a) We design distributed fog probing schemes to search for the availability of mobile edge devices to act as fog nodes, and the availability of spectrum and computing resources. First, an agnostic fog probing scheme is developed that assumes no prior knowledge on the outage probability of the connection, which may result into temporal recapturing of the channels used by SNs and/or fog nodes due to PNs' traffic. The process is modelled as a two dimensional absorbing Markov chain. The probability of successful transmission, which depends on the activity of PNs and fog nodes, is quantified. This scheme is used as a benchmark for comparison with the autonomous schemes developed later. b) Fog reinforcement strategies are presented to enhance the robustness to the uncertain availability of channels and fog nodes by probing multiple connections with high probability of success as backups. A comprehensive framework to model and analyze these strategies is elaborated. The robustness optimization problem is formulated as a stochastic optimization problem. The aim is to maximize the expected long-term network performance in terms of reliability defined as the probability of transmitting successfully within a latency bound. However, solving this optimization is complex since it is a combinatorial problem and its complexity increases exponentially with the network size. c) Restless Multi-Armed Bandits (RMAB) provide an efficient way to derive an index-based robustness control algorithm with low computational complexity. However, investigating the problem structure to cast it as an RMAB is challenging [28]. By reducing our original Markov connectiv-ity state model, we reformulate the robustness control problem in the form of a RMAB, which enables an autonomous implementation. Without loss of generality, the reduced model allows direct implementation of the Whittle index policy with significantly low complexity. The problem is solved by an online robustness control (ORC) algorithm that integrates online fog probing and index-based connectivity activation policy. We prove the indexability of the connectivity activation policy theoretically and obtain the Whittle index in closedform. By relaxing the constraint of the number of connections activated per slot, the Whittle index is the optimal solution to our RMAB. d) We evaluate our algorithms through numerous simulations. First, the evaluation is conducted in small-sized networks to compare the performance with the original problem formulation that requires high computational time for large-sized networks. Then we evaluate the index-based scheduling algorithm for large-sized networks. We compare the performance with some typical scheduling algorithms. The results demonstrate that our approach significantly outperforms existing solutions.

The remainder of this paper is organized as follows. Section II describes the related work. The system model is elaborated in Section III. In Section IV, the fog reinforcement framework and the agnostic fog probing scheme are described. The robustness control optimization is formulated in Section V and it is solved in Section VI using our proposed ORC algorithm. Section VII evaluates the proposed algorithms through simulations. Concluding remarks are provided in Section VIII.

Several works have investigated computing resource failures in cloud and fog computing services. Yao and Ansari [17] studied the reliability of virtual machines as their probability of failures in fog nodes when processing computing tasks. They formulated a multi-objective optimization problem to assign computing tasks to virtual machines (VMs) in a fog node. Dantu et al. [18] utilized smartphones as fog nodes and designed a software architecture to provide reliability and adaptability. Yao and Ansari [19] addressed the joint optimization of power control and fog resource provisioning in terms of the number of VMs to guarantee task completion time requirements. Liao et al. [34] propose a scheme to balance computing resources in edge IoT by monitoring computing demand.

Some works have studied channel assignments in cognitive networks through spectrum leasing [35], channel switching and rerouting [36]- [37] but without reliability and latency guarantees and with fixed access points. Recently, a few works have addressed fog resource provisioning under network dynamics in fog networks. Zhao et al. [20] presented a multi-tier operations scheduler to optimize node assignments at the control tier and resource allocation at the access tier under dynamic constraints. They solved the problem using Lyapunov optimization techniques and developed an online scheduling algorithm that achieved at least half of the optimal value. Omoniwa et al. [21] utilized fog nodes as relays and proposed a relay scheme to minimize the transmission outage that jointly optimizes mobility and power consumption. Yang et al. [22] considered fog nodes equipped with cognitive capabilities and studied the joint optimization of spectrum utilization and energy efficiency in collaborative task offloading. In our previous work [5], we presented a Robust Dynamic Network Architecture (RDNA) together with a holistic cross-layer approach to improve network robustness. In this paper, our focus is on optimizing robustness under resource uncertainty to meet latency and reliability requirements. A comprehensive analytical framework is developed to model and analyze robustness enhancement, which encompasses fog probing and fog reinforcement strategies.

In this section, we describe our proposed network architecture, and the related communication and computing models. The most important notations used in the paper are summarized in Table I.

We consider a cognitive, dynamic fog/edge network architecture, as illustrated in Fig. 1. A set of primary nodes (PNs) M = {1, 2, …, M }, such as smartphones, tablets, etc., with data storage, computation and packet forwarding capabilities share their connectivities and act as primary fog nodes (PFNs). The PFNs serve a set of secondary nodes (SNs) N = {1, 2, …, N } with limited capabilities, such as smart sensor nodes that collect data for machines, objects, etc. The PFNs will collect the data from SNs, perform necessary computation and distribute it throughout the network. We assume that SNs are equipped with cognitive capabilities to harvest available frequency channels in the set B = {1, 2, …, B}. The network is operated by a primary operator (PO) that incentivizes its users, whenever their terminals are idle, to act as PFNs. The high density of user terminals provides many connectivity alternatives and opportunities to establish backup connections to improve the robustness of the network against traffic dynamics.

We assume that SNs are equipped with one radio that can be tuned into any available frequency channel for message delivery. The availability of frequency channels varies in time and space as these channels may be occupied by PNs' transmissions. Thus, PNs activity will affect the performance of SNs' transmissions. We assume slotted transmissions in the primary and secondary networks with different arrival/departure times in each network. Let a b ij , i ∈ N , j ∈ M, denote the probability that channel b at link i → j is available for SN i transmission to PFN j and (1a b ij ) the probability that channel b at link i → j is occupied by a PN transmission, and thus, unavailable for SN i transmission. In addition, we denote the availability of PFN j, j ∈ M to act as an access point by α j . PFN j is available to act as an access point and share its resources when it is not transmitting/processing its own traffic.

To characterize the transmission/interference in the physical layer, we adopt the widely accepted protocol model [23]. The power propagation gain from SN i to PFN j is

where β is an antenna-related parameter, χ is the path loss factor, and d ij is the distance between the two nodes. According to the Shannon-Hartley theorem, if SN i, i ∈ N transmits data to PFN j, j ∈ M, using available channel b, the link capacity will be

where W b = W is the bandwidth of channel b, P i is the transmission power at SN i and γ is the Gaussian noise power at PFN j. In the following section, we will address the transmission constraints to avoid interference. If Q i is the amount of data required for the task of SN i, the transmission time needed to transmit its traffic is τ t ij = Q i /C ij and the energy consumption is e t ij = P i τ t ij .

Suppose f j is the computation capacity of PFN j in CPU cycles per unit of time. Denote by w j its current workloadthe portion of processing capacity currently occupied by PFN Authorized licensed use limited to: CLEMSON UNIVERSITY. Downloaded on August 04,2021 at 20:23:57 UTC from IEEE Xplore. Restrictions apply. j's own tasks. Then the available processing capacity to share with SNs is Γ j = f j (1w j ). In addition, we denote by δ i the amount of computing resource required by the task of SN i in CPU cycles. Accordingly, the execution time for computing the task of SN i at PFN j is τ c ij = δ i /Γ j , and the energy consumption at PFN j is e c ij = ε j τ c ij , where ε j is the energy cost per CPU cycle [24]. Given the limitation of mobile terminals in computational capacity, we assume that at most one task is executed at a time.

IV. FOG REINFORCEMENT FRAMEWORK By taking advantage of the high density of user terminals, in the subsequent development we present the methods to identify possible backup connectivities (and their constraints) that could be used to reinforce the connections of SNs with the fog under uncertainty of available channels and PFNs.

We consider scheduling of SNs transmissions in the frequency domain, i.e., channel assignments for transmission and receptions to ensure that there is no interference at the same node and among adjacent nodes.

Denote by B i ⊆ B the set of available channels at SN i ∈ N . Suppose that channel b is available at SN i and PFN j, i.e., B ij = B i ∩ B j . Define

For an SN i ∈ N and a channel b ∈ B, the set of PFNs that can use channel b and are within the transmission range

Note that a PFN j ∈ M cannot receive from multiple SNs on the same channel,

Likewise, if SN i uses channel b for transmitting data to PFN j ∈ T b i , then any other SN that can interfere with PFN j should not use this channel,

where

∅} is the set of SNs that can interfere with the reception of PFN j on channel b, B nj is the set of the licensed channels available to SN n and PFN j, and T b n = ∅ indicates that SN n has a PFN to which it can transmit by interfering with reception at PFN j.

A feasible scheduling of SNs transmissions in frequency channels must satisfy the previous interference constraints. The scheduling of PNs transmissions is out of the scope of this paper. Nevertheless, since the availability of channels for SNs transmissions and the availability of PFNs depend on the traffic in the primary network, we model PNs' traffic as well for completeness of the model.

Denote the set of PNs whose transmission on channel b will interrupt SN i transmission to PFN j as PN z and PFN j. By slightly abusing the notation T b z = ∅ indicates that z has a destination to which it can transmit by interrupting the transmission between SN i and PFN j.

At the beginning of slot t, each SN probes the availability of channels and fog nodes that satisfy its connectivity requirements. Let us elaborate the availability probability of channel b for SN transmission. For analytical tractability of the model, we assume that traffic arrivals follow a Poisson process [3]. The probability of having Z arrivals from PNs' in the set

Then, the availability of channel b for SN i transmission at slot t is obtained as the probability that channel b ∈ B ij has not been recently allocated (i.e., in the previous ∆t) to any arrivals from PN z ∈ C b j ,

where ∆t -refers to the previous ∆t and Z/ |B ij | is the probability that Z arrivals are allocated to a particular channel (i.e., channel b) out of |B ij | . Here, we assume PNs can access any channel with the same probability. Equation ( 5) can be modified to capture other PN channel access policies. The scheduling process after a PN return is illustrated in Fig. 2. At the beginning of slot 1, SN 1 has a set B 1j of available channels to transmit to PFN j (found by probing), and selects to transmit in channel b 1 . After the transmission is initiated, PN 3 returns to channel b 1 interrupting the transmission. At the beginning of the next slot, SN 1 finds the new set of available channels and transmits in channel b 2 . It continues transmitting in this channel until the transmission is interrupted by PN 4 in slot 3. Finally, in slot 4 SN 1 finds the new set of channels and transmits in channel b 5 . A similar behavior is followed by SN2. For simplicity, we illustrate only the impact of PNs' activity on channel availability but its extension to the fog availability is straightforward. A PN j is available as a PFN and performs computing tasks for SNs if it is not transmitting/processing its own traffic. We denote by p J (∆t) = e -λP j ∆t (λ Pj ∆t) J /J! the probability that PN j receives J new requests from its own traffic with arrival rate λ Pj within ∆t. Thus, the probability that PN j is available to serve as a fog node in slot t is the probability of not receiving any new request

Since the availability of fog nodes (and channels) changes in time, a SN may transmit to different fog nodes and channels in subsequent time slots. If a SN transmission is interrupted, it will be repeated it in the next slot using the same or different fog nodes depending on the availability.

Hence, the probability that the link between SN i and PFN j on channel b is available at time t is

The connection will be successful if the link remains available for the entire duration of the slot ∆t. Denote the outage O b ij as the probability that the connection is interrupted due to either a return of a PN to the currently allocated channel b (as illustrated in Fig. 2) and/or a new request from PFN j's own traffic in ∆t. Thus, the transmission between SN i and PFN j on channel b at time t will be successful with probability

Strategies to reinforce the connectivity with the fog and increase the robustness of the network connections will be presented. Robustness is the property of the end devices to remain connected to the fog and providing service under dynamically varying traffic. Dynamic traffic induces uncertainty to the availability of connectivity (i.e., channels and PFNs) which impacts on latency and reliability, as well as on overall network performance.

Definition 1: The latency τ refers to the time elapsed since the data is transmitted until it is received by the destination. The latency τ b ij between i and j on channel b includes the access delay τ b,a ij of SN i to PFN j and it will be elaborated in Section V depending on the reinforcement strategy used, the transmission time τ t ij , and the computational time τ c ij . Downlink time is negligible compared to uplink data offloading time and computation, hence, it has not been considered in the calculus [25],

Definition 2: Reliability ξ refers to the probability of successful transmission within a latency bound τ max . Therefore, the reliability of the connection of SN i is

where τ b ij is the latency. In the following, we present our strategies to reinforce the connectivity with the fog. We represent a reinforcement strategy as the pair (n c , n a ) where the first element indicates the number of backup channels and the second one is the number of backup fog nodes. The selection of the specific backup connections is explained in Section V. We define the following four strategies:

reinforcement, reinforcement through n c backup channels, reinforcement through n a backup PFNs, and reinforcement through both n c backup channels and n a backup fog nodes, respectively. For simplicity in the sequel, we remove the time dependency t in the link availability probability (7). a) No reinforcement (r = 0): It describes the conventional connectivity option where an SN i ∈ N probes the availability of a PFN j ∈ T b i on one channel b at a time. This is illustrated in Fig. 1a. The probability that the link between i and j is available on channel b under this strategy is obtained by (7) as

b) Backup channels (r = 1): An SN i ∈ N probes a set of backup channels B ij ⊂ B ij to increase the probability that there is a link available for transmission to a PFN j ∈ T b i . This is illustrated in Fig. 1b. The probability that the link between i and j is available either on channel b or on any backup

The first term is the link availability probability between i and j on channel b with no reinforcement as in expression (11a). The second term indicates the probability that channel b is not available and the probability that the link between i and j is available on a backup channel k where s is the index of the backup trial.

The first term denotes the link availability probability with no reinforcement as expressed in (11a), and the second term is the probability that PFN j is not available and the probability that there is a backup PFN m available to serve SN i on channel b. Index q indicates the backup trial.

d) 2-level backup (r = 3): This strategy combines backup channels and fog nodes as illustrated in Fig. 1d. Thus, an SN i ∈ N probes 1 + n c channels to transmit to any of its 1 + n a PFNs. The probability that there is a link available between i and j ∪ (T b i ) on channel b ∪ B ij under this strategy is given in (11d). The first term is the probability of link availability under reinforcement strategy r = 1 given in (11b). The second term is the probability of link availability under reinforcement strategy r = 3 as expressed in (11c). The third term is the link availability under no reinforcement as in (11a). Finally, the fourth term is the probability that the channel b and PFN j are not available for SN i's transmission multiplied by the probability that SN i has a connection available on a backup channel k to a backup PFN m. The indexes s and q are the indexes of the channel and PFN backup trails, respectively.

For simplicity, we have limited our previous discussion to obtaining the link availability probability l b,r ij (t) under different reinforcement strategies. Its extension to obtaining the probability of successful transmission l b,r ij (t+∆t) for each strategy r is straightforward from (8).

Definition 3: The robustness of the network is defined as the probability that the network remains connected under dynamically varying traffic, which is given as the average probability that users have at least one connection available to transmit reliably,

where r is the reinforcement strategy used, j ∈ T b i , and l b,r ij (t + ∆t) is the probability of successful connectivity (8) under strategy r. Section V describes how SNs learn to probe the set of connections that have high probability of successful transmission.

We model SNs access to the fog network by using a fog probing mechanism used to check the availability of channels and adjacent fog nodes at the beginning of each slot. Initially, we assume SNs do not have any preliminary knowledge about whether the probed connections are successful. This scheme is referred to as agnostic fog probing, which will be used as a benchmark for comparison with fog probing schemes that incorporate learning in Section V. The probing process is represented by an absorbing Markov chain with MB transient states, where M is the number of fog nodes and B the number of channels, and the two absorbing states "A" and "NA" indicating access and non-access to the fog, respectively. The fog network access state transition diagram is shown in Fig. 3 where each transition state is given by the pair (j, b) denoting the indexes of the PFN and the channel, respectively.

The agnostic fog probing protocol works as follows. At the beginning of a slot, each SN i checks the availability of its adjacent PFNs, starting with its most preferable one, and the availability of each channel randomly. Let us assume that SN i starts checking the availability in state (1,1). If PFN j = 1 is not available, the process moves rightward with probability (1α 1 )a 1 i1 , whereas if channel b = 1 is not available, the process moves upward with probability (1a 1 i1 )α 1 . Similarly, if neither PFN j = 1 nor channel b = 1 are available, the process will move up along the diagonal with probability (1a 1 i1 )(1α 1 ). If a PFN and a channel are available in state S a = (j a , b a ), the process will move to the "A" state with probability a 1 i1 α 1 . Based on the reinforcement strategy, this process may be repeated, starting from the next state S a +1 until the SN finds all available PFNs and channels. The process will finish when all PFNs and channels are checked and there are no more available, finishing in the "NA" state. If a PN returns to a channel currently allocated to a SN or the allocated PFN receives a new task from its own traffic, the connection will be interrupted, and the process will be repeated to find a new connection at the beginning of the next slot, as shown in Fig. 3.

To obtain the access delay τ b,a ij under the agnostic fog probing scheme, we define the transition probability matrix of fog network access states S = S(j, b; j , b ) = S(m, m ) with indexes m = j + M (b -1) and m = j + M (b -1), m, m = 1, 2, …, MB denoting the current and next state, respectively. Following the theory of absorbing Markov chains [26], [27], we arrange matrix S in a canonical form as

with size N S × N S , where N S is the number of states (i.e, N S = N A + MB), I is a N A × N A unity matrix corresponding to N A absorbing states, 0 is a N A × MB all-zero matrix, R is an MB ×N A matrix of transition probabilities from transient states to absorbing states, and S is an MB × MB matrix of transition probabilities between transient states. These matrices are outlined in the Appendix. We define the fundamental matrix as N = (I -S) -1 with dimensions MB × MB. The mean access time for the process to reach an absorbing state starting from transient state m is the mth entry of the vector [26] (τ a 1 , . . . , τ a MB ) t = T N1 (14) when the dwell time for any state m is the same, T = T m and 1 is an MB × 1 column vector of all ones. The generalization to any dwell time is straightforward. The variance of each τ a m can be expressed as [26] var

where T is an MB × MB diagonal matrix with elements T m , e is a column vector of the same elements, and || || sq is the square of each component of || ||. The access delay τ b,a ij is obtained as in ( 14) with T = 1 and the inverse mapping (j, b) ← m.

The probability that transient state m is absorbed to the absorbing state n = {"A", "NA"} is the (m, n)-entry of the matrix B = [b mn ] = NR (15) which provides the probability of available transmission in state (j, b) ← m or equivalently from SN i to PFN j on channel b.

In the agnostic fog probing, SNs will probe all connections until they find an available one. This process is costly since it consumes time and network resources, especially if connectivity reinforcement strategies are used. Therefore, as a next step we will incorporate learning in the fog probing process to reduce the number of probed connections to those with the highest probability of transmission success.

In this section, we formulate the robustness control optimization problem to maximize the long-term reliability of SNs' transmissions. The problem is solved in two steps. First, each SN i probes a set of connections P i (t) at time t based on its reinforcement strategy. After the fog probing is completed, each SN notifies the secondary operator (SO) on the availability of the probed connections. Let us recall that SNs' transmissions use the channels and PFNs from the primary network whenever available. Once all notifications are received, the SO decides which connections to activate in each slot and receives a reward R i for each successful connection of SN i, which depends on the reliability. The objective for the SO is to activate the connections to maximize the long-term total discounted reward.

By using the agnostic fog probing scheme described in Section IV.C, SNs check the availability of the connections in the current instant but they are unaware of the probability of transmitting successfully (i.e., there is no outage in the transmission) by using these connections. To improve the selection of the connections, we present an automatized fog probing scheme based on RMABs model [28], [29] that builds a belief, based on previous experience, that the connection will be successful. In the automatized fog probing, at the beginning of time slot t, each SN i chooses a set P i (t) ⊂ {1, 2, . . . , K} of connections to probe (1 ≤ K < MB) and receives a reward if the probed connections remain available. The objective is to probe the links with the highest probability of being available for the slot duration. We model the availability of each connection (j, b) → k ∈ P i (t) as a Markov process with four possible states, depending on the availability "1" or unavailability "0" of PFN j and channel b: S j,b (t) = (S j (t), S b (t)) = (0,0), (0,1), (1,0), or (1,1). The first index indicates the state of PFN S j (t) and the second one the state of channel S b (t). The state of each connection evolves from slot to slot as a Markov chain with transition matrix P org = [p S j,b ;S j,b ] as illustrated in Fig. 4a.

For tractability of the model and to cast our problem as a RMAB and obtain the Whittle index, we elaborate an equivalent reduced Markov model, as shown in Fig. 4b, with two states, S k (t) = 1 and S k (t) = 0, depending on the availability or unavailability of the connection k, respectively. The state of the probed connection is now obtained as S k (t) = S j (t) • S b (t), where S j (t) is the state of the PFN and S b (t) is the state of the channel. The transition matrix of the reduced Markov model is

where the transition probabilities of connection k during slot t are

)

where k is the index of the connection of SN i to PFN j on channel b. The probability of connection outage O b ij is defined in Section IV.A. The transition probability p k 00 (t + ∆t) from S k (t) = 0 to S k (t+∆t) = 0 is obtained as the probability that the connection remains unavailable. The connection transition IEEE/ACM TRANSACTIONS ON NETWORKING probability p k 01 (t + ∆t) from state S k (t) = 0 to state S k (t + ∆t) = 1 is equal to the probability of successful transmission. The connection transition probability p k 10 (t + ∆t) from state S k (t) = 1 to state S k (t + ∆t) = 0 is equal to the connection outage. Finally, the connection transition probability p k 11 (t + ∆t) from state S k (t) = 1 to state S k (t + ∆t) = 1 is equal to the probability of no connection outage.

Since the connection state S k (t) is not observable until when the availability of the connection is checked, we define a belief matrix Ω(t) = [ω 1 (t), . . . , ω K (t)], where ω k (t) is the conditional probability that S k (t) = 1. It has been shown that the conditional probability that each connection is in state 1 given all past decisions and observations is a sufficient statistic for optimal decision making [28]. Given the fog probing selection P i (t) and the observation at time t, the belief state in time t + 1 can be obtained recursively as

where

01 is the belief operator when connection k has not been probed in the current slot. If there is no prior information on the initial system state, the kth entry of the initial belief vector Ω(1) can be set to the steady state probability that the reduced system is in state 1,

1 , next we analyze the relation between the steady-state probabilities of the original system, shown in Fig. 4a, and the reduced system, shown in Fig. 4b.

Denote by π org = (π org 00 , π org 01 , π org 10 , π org 11 ) the steady state distribution for the Markov chain with transition matrix P org = [p S j,b ; S j,b ] satisfying π org = π org P org (21) and by π red = (π red 0 , π red 1 ) the steady state distribution for the reduced Markov chain with transition matrix P red = [p S k S k ] satisfying π red = π red P red (22) The equivalence between the original system and the reduced system is described as

where π red 0 + π red 1 = 1 and π org 00 + π org 01 + π org 10 + π org 11 = 1. Since the values of the transition matrix P org can be obtained from the traffic arrival and departure distributions, π org is calculated by solving the system (21). Then, π red is obtained by solving (23). Finally, by solving system (22) the steady-state probabilities of the reduced system are calculated

By formulating the fog probing as an RMAB, each connection k represents an arm and the belief state ω k (t) is the state of the arm at time t. Each SN will choose a number of arms K to probe at each slot while the other arms are unobserved.

The belief state shows the states of both probed and unprobed arms.

Each SN i receives a reward at time t when a connection that has probed successfully (i.e., available connection) is activated by the SO minus the cost of probing the connections. Based on the reinforcement strategy, each SN will probe K = (1 + n c )(1 + n a ) connections to increase the chances of finding one with a high belief and, thus, increase the probability that it will be selected by the SO and receive a reward,

where y k (t) ∈ {0, 1}: y k (t) = 1, if the connection has been selected by the SO, or y k (t) = 0, otherwise, and c k is the cost of probing the connection. If SN i has a reinforcement strategy r = 0, then it will probe only K = 1 connections since the number of backup channels n c and backup fog nodes n a will be zero. In our fog probing problem, arms are stochastically identical (i.e., all arms have the same Markovian dynamics and reward structure). Thus, we focus on deriving the optimal policy at an individual slot since it would remain the same for different slots [28]. We define an online fog probing policy obtained by probing K arms with the highest belief in each slot. The online fog probing policy Pi (t) is then given by

Once the fog probing is completed, each SN sends the information about the availability of the probed connections to the SO. Given that all SNs share any available channels and PFNs to transmit, the SO will activate the SNs' connections to maximize the reward subject to the interference constraints (3) and ( 4). The indicator y b ij (t) = 1 is used to denote that connection (j, b) → k ∈ P i (t) has been allocated for SN i transmission, and y b ij (t) = 0 otherwise. If the activated connection k results in a successful transmission the SO receives a reward r k . Otherwise, it receives a penalty c k .

The problem is to determine which connections to activate at each time slot to maximize the expected total discounted reward for the SO, max

where

) is the reward of the SO that will be elaborated in the next section, and y b ij (t) ∈ {0, 1} denotes the association between SN i ∈ N and PFN j ∈ M on channel b ∈ B for data transmission and task computation in time t. Since the available channels are shared among multiple SUs (B < N), to avoid interference, the number of connections activated simultaneously are constrained to a fraction γ of the available channels B. The fraction γ can be obtained using an interference graph [30] and considering the interference constraints defined in ( 4) and ( 5) with

Solving the previous optimization is complex since it is a combinatorial problem [11]. To make it tractable, in the next section we formulate (26) as a RMAB problem and derive a connectivity activation index policy based on Whittle Index [28], [29], [38].

By modelling the SO connectivity activation policy as a RMAB problem, we view each connection as an arm. When an arm is activated, the corresponding SN can transmit. To formulate the RMAB, we define the decision epoch, state space, state transition probability, and reward.

1) Decision Epochs: Time is divided into discrete time slots and decisions are made each time t, t ∈ {1, 2, . . . , ∞}.

2) State Space: Recall that each SN i wants to transmit an amount of data Q i in τ max,i slots. We define the state of the SN i transmission s i (t) = (Q r,i (t), τ r,i (t)), indicating that SN i has a remaining amount of data Q r,i (t) to transmit and τ r,i (t) remaining slots to complete it. The system state at decision t consists of the states of all SNs s = (s 1 (t), . . . , s N (t)). At each time t, there are N SNs waiting to transmit in one of their available probed connections. Note that the state s i of the SN i is different from the state of the connection S k in the previous section.

3) Action: At each decision epoch, the action y b ij (t) taken by the SO determines which SNs can transmit. If SO takes action

Since there are B < N channels, the action taken at any time t should satisfy the constraint i y b ij (t) ≤ γB. 4) State Transition Probability: For each SN i, the state s i (t) will transfer to different states with probability Pr{s i (t+ 1)|s i (t), y b ij (t)} depending on the action of the SO and the uncertain availability of the links. When τ r = 1, assuming that SN i have packets to transmit periodically, Pr{s i (t + 1)|s i (t), y b ij (t)} = 1 independently of the action y b ij (t) taken and the state will transfer to s i (t+1) = (Q i , τ max,i ). Similarly, τ r > 1 and Q r = 0, independently of the action we have Pr{s i (t + 1)|s i (t), y b ij (t)} = 1 with s i (t + 1) = (0, τ r -1). However, if τ r > 1 and Q r > 0 and the connection is activated the state will transfer to

The probability that the connection will be successful or belief ω b ij is obtained as in (20). If the connection is not activated, Pr{s i (t+1)|s i (t), y b ij (t)} = 1 with s i (t+1) = (Q r,i (t), τ r,i (t)-1). 5) Reward: The reward of SN i at time t depends on the current state and the action taken,

where ω b ij ← ω k is the belief state as in (20), c b ij (t) ← c k is the penalty incurred when the connection is not available or it has not been activated, and r b ij (t) ← r k is the reward of connection k obtained when the connection is successful.

To obtain the reward r b ij (t) per slot t, we can rewrite the reliability, defined in (10), as

where

the ratio of the amount of data transmitted in time t with respect to the overall amount of data Q i that SN i aims to transmit.

Whittle index policy is the optimal solution to a Lagrangian relaxation of RMABs [28]. In our problem, this is achieved by relaxing the constraint in (26) in which the number of activated arms can vary over time given that their discounted average over the infinite horizon equals γB,

Based on the Lagrangian multiplier theorem, the RMAB can be decomposed into a single-arm activation problem and so, it suffices to consider a single arm (i.e., connection),

The aim is to decide whether to activate the arm at each slot based on the concept of subsidy for passivity [28]. Let us construct a single-bandit process identical to the one previously described except for a constant subsidy ν that is obtained when the arm is passive. The ν-subsidy reward is formally given by R ν i (s i (t), y(t)) = R i (s i (t), y(t)) + ν1(y(t) = 0) (29) where 1(•) equals 1 if the expression in the bracket is true, and 0 otherwise. The SO decides whether to activate an arm or not at each time t to maximize the total discounted ν-subsidy reward

with initial state s. To simplify the notation, we drop the subscripts i and t without loss of generality. Let V (s) denote the value function that represents the maximum expected total discounted reward that can be accrued from a single-arm bandit process when the initial state is s and two actions, y = 0 and y = 1, are possible:

where V (s; y) is the expected total discounted reward when action y is taken at the first slot followed by the optimal policy in future slots as

V (s, y = 1) = R(s, 1) +

The term p(s |s, y) denotes the probability that SN i changes from state s to next state s when decision y is taken and V ν (s ) is the total discounted future reward. In (32), V (s, y = 0) is given by the sum of the ν-subsidy reward in the first slot under action y = 0 and the total discounted future reward. Likewise, V (s, y = 1) is obtained.

Definition 4: The Whittle index ν i (s) of an arm i in state s is the infimum subsidy ν that makes the two decisions (activating arm i or not) equally rewarding:

where V (s; y) is the expected reward when action y is taken at state s. Definition 5: An arm is indexable if the passive set Z(ν) = {ν : V (s, y = 0) ≥ V (s, y = 1)} of the single-armed bandit process with subsidy ν monotonically increases as ν increases from -∞ to +∞. An RMAB is indexable if every arm is indexable.

To establish the indexability and derive the closed-form expression of the Whittle index, we distinguish the following cases in calculating the expected total discounted reward:

1) When τ r = 1, assuming that SNs have packets to transmit periodically, p(s |s, y) = 1 independently of the action y taken and the SN will change to s = (Q, τ max ). The remaining time to complete the transmission is initialized to τ max and the SN can start a new transmission in the next slot.

-If Q r = 0 and y = 0 we have V ((0, 1), 0) = ν + βV (Q, τ max ), whereas if y = 1 we obtain V ((0, 1), 1) = βV (Q, τ max ). Therefore, by (34) the Whitte index is ν(0, 1) = 0.

-If Q r > 0 and y = 0, we have that V ((Q r , 1), 0) = νc + βV (Q, τ max ), whereas if y = 1 we have V ((Q r , 1), 1) = ωr -(1ω)c + βV (Q, τ max ). Then, the Whittle index is ν(Q r , 1) = ωr + ωc.

The previous derivations establish the indexability of the problem when τ r = 1.

2) When τ r > 1, -If Q r = 0 independently of the action y taken, p(s |s, y) = 1 with s = (0, τ r -1). If y = 0, V ((0, τ r ), 0) = ν+βV (0, τ r -1) is obtained, whereas if y = 1, we have V ((0, τ r ), 1) = βV (0, τ r -1) and the Whittle index is ν(0, τ r ) = 0.

-If Q r > 0 and y = 0, we have p(s |s, y) = 1 with s = (Q r , τ r -1). In this case, the expected reward is V ((Q r , τ r ), 0) = νc + βV (Q r , τ r -1). On the other hand, if y = 1, the user will change to state s = (Q r -Q , τ r -1) with probability ω or to state s = (Q r , τ r -1) with probability 1-ω. Therefore, we obtain

Next, we analyze the indexability when τ r > 1. Let us define

Differentiating h(Q r , τ r ) with respect to ν, we obtain ∂h(Q r , τ r )/∂ν = 1 + βω∂f (τ r -1)/∂ν. Assuming that ∂f (τ r )/∂ν ≥ -1/βω, we find that ∂h(Q r , τ r )/∂ν ≥ 0. By definition 5, this implies indexability under state (Q r , τ r ) with Q r > 0 and τ r > 1. Next, we prove that ∂f (τ r )/∂ν ≥ -1/βω is true by induction. The expression of f (τ r ) is

Since 0 < β ≤ 1 and 0 ≤ β(1ω) < 1, it is easy to see that ∂f (τ r -1)/∂ν ≥ -1/βω for all three cases, which demonstrates the indexability of the connectivity activation problem.

Theorem 1: The connectivity activation problem formulated as a RMAB is indexable.

Proof: See discussion above. Theorem 2: The closed-form Whittle index ν(s) of an arm under state s = (Q r , τ r ) is

Proof: By definition of the Whittle index, for a given state s, we can obtain the Whittle index by solving (34). From the closed-formed expressions of V (s, y = 0) and V (s, y = 1) previously obtained, and ( 35)- (36), we have solved (34) and obtained the Whittle index (37).

We define an Online Robustness Control (ORC) algorithm, as described in Algorithm 1, that combines the online fog probing algorithm (25) and the index-based connectivity activation policy (37). At each time slot, the SO calculates the indices of all connections probed by every SN and activates the γB connections with the highest indices. The complexity of calculating all indices is O(NK) and sorting them has a complexity of O(NKlog(NK)), with

where n c is the number of backup channels and n a is the number of backup fog nodes. Therefore, the computational complexity of the Whittle index-based activation policy is O(NKlog(NK)).

In this section, we present numerical results to illustrate the performance of our schemes. The simulations are conducted in Matlab. We simulate a wireless edge/fog network with N SNs, M PFNs, and B channels as described in Section III. The rest of the simulation parameters are summarized in Table II. We simulate three fog probing schemes: online, agnostic and genie. The online fog probing is defined in (25) and builds a belief on the connection availability. The agnostic fog probing is described in Section IV.C and assumes no prior knowledge on the connection availability. Finally, the genie fog probing assumes perfect prediction of connectivity availability and is used for comparison purposes. We simulate the performance of the robustness control framework by using these fog probing schemes and the connectivity activation policy based on Whittle Index and solving the original formulation in (26) with relaxed constraint. First, we evaluate the performance for small-sized networks to compare the results with the original problem formulation (26) that has increasingly exponential complexity with network size and, thus, requires long computational time in large-sized networks. Then, we evaluate the online robustness control algorithm for large-sized networks and show its log-linear scalability. In addition, the results are compared with the least laxity first (LLF) algorithm [33] often used as a benchmark for comparison in scheduling algorithms.

In Fig. 5 we show the robustness of the network ρ r as in (12) and the average probability of successful transmission (averaged with respect to (8)) for different reinforcement strategies r. We set N = 20, M = 10 and B = 5 (i.e., up to M x B = 10 x 5 possible connections per SN). An improvement between 20% to 30% in the robustness was obtained with 1 backup channel and 1 backup PFN compared with no reinforcement, leading to ρ r = 0.93 to 0.995, respectively. Similarly, an improvement of up to 25% was obtained in the average probability of successful transmission under the same scenario. By increasing the number of backup channels to 2, a robustness ρ r = 1 was obtained and by further increasing the backup PFNs to 3, the average probability of successful transmission equaled to 1.

Next, we conducted Monte Carlo simulations over 10000 realizations of the network to calculate the number of completed transmissions and the reward of the SO. We set N = 5, B = 5, 2 PNs with λ = 0.5 and varied M from 1 to 9. Figure 6 shows the average number of completed transmissions (without reinforcement) using the original robustness control formulation (26) with relaxed constraint and the Whittle index for each of the three fog probing schemes, online, agnostic, and genie. In the legend, the first term denotes the fog probing and the second the robustness control algorithm. The genie-aided fog probing corresponds to the case when the SNs can predict with complete certainty the connectivity availability, and thus its performance is the best. The performance of our online fog probing scheme is very close to that of the genie scheme which emphasizes the relevance of our scheme in which the SNs select the connection with the highest belief of availability at the current slot. In the agnostic scheme, the probing starts from a random connection and without prior information on the probability of transmission success. We can see that the online fog probing scheme completed 30% more transmissions than the agnostic scheme. We also compare the SO activation policy solving the original formulation in (26) with the Whittle index policy and a priority policy based on the LLF algorithm [33] in which SNs with more remaining data and fewer slots left had higher priority to transmit. For clarity of presentation, we show the results using the online fog probing. As expected, we observe that the Whittle index policy achieved the same performance as solving (26) while the performance under the priority policy is significantly worse. In the latter, the decision is made in each slot without considering the future performance and thus, fewer overall number of transmissions are completed. Similar results were obtained with the other fog probing schemes.

In Fig. 7, the utility of the SO defined as the expected total long-term reliability was obtained for a scenario of N = M = B = 5 and 2 PNs for different values of the PNs' traffic arrival rate λ. By increasing λ, the availability of channels and fog nodes decreases. It is worth noting that even for high values of λ (i.e., λ ∈ [0.6, 0.8]), the highest deviation of the online fog probing scheme from the genie scheme was about 3%. This demonstrates that our online fog probing algorithm can estimate the belief even when there are many interruptions and so, less past experience available in probing these connections. When λ > 0.8, there were rarely any available connections, so SNs always chose the same connections. As before, the Whittle index activation policy provides the optimum solution to the original problem (26) with relaxed constraint. In the agnostic scheme, under the optimum selection policy, a higher amount of data was scheduled compared with the online-priority scheme. Let us recall that the latter is based on the LLF algorithm [33], which solves the optimization per slot without considering future performance.

Next, we study the performance of the online robustness control algorithm when online fog probing is used together with the Whittle index policy under different reinforcement strategies. In Fig. 8 and Fig. 9, the expected total long-term reliability and the average number of completed transmissions are presented versus N for three scenarios: M = B = 20; M = B = 10; and M = 10, B = 5. With the optimum reinforcement strategy r * , we achieved up to 10% improvement in terms of reliability and completed 15% more transmissions compared to no reinforcement. The optimum number of probed connections K * to obtain this improvement is shown in Fig. 10. In the first scenario, a total reliability of 0.998 was obtained for K * < 6 probed connections and N ≤ 20. Since this scenario has the highest number of options for connectivity and backup (M = B = 20), the reliability and the number of completed transmissions is significantly higher than in the other two scenarios, especially when N > 20.

In the second scenario, a total reliability of 0.995 was obtained for 4 probed connections and N < 10. In the third scenario, by probing 2.5 connections on average, an expected total reliability of 0.992 was achieved for N < 7. By increasing N to 50, the expected total reliability was maximized for 12 and 6 probed connections in the first scenario, and in the second and third scenarios, respectively, achieving a value of 0.987, 0.882 and 0.77. The numbers of completed transmissions in this case, as shown in Fig. 9, were 47, 33 and 20, respectively. Because of interference, fewer SNs could transmit packets simultaneously and, thus, the number of completed transmissions decreased with N . Nevertheless, the improvement with reinforcement strategies was significant in this case as well.

In this paper we have presented an online robustness control scheme to maximize the total long-term reliability of the connections in a cognitive, dynamic fog/edge-aided wireless network. The scheme consists of two steps. First, a fog probing process is developed to check the availability of the users to act as fog nodes, and the availability of channels and computing resources. An online fog probing algorithm has been presented to maximize the probability that the probed connections are successful (i.e., no transmission outage) during the transmission period. Then, an index-based connectivity activation policy based on RMABs has been proposed. By activating the connections with highest indexes, the total long-term reliability optimization problem is solved with low complexity. Extensive simulations have been conducted to show that our robustness control scheme achieves an expected total reliability very close to the optimum. In addition, it significantly increases the number of completed transmissions compared to an agnostic scheme and a scheme with fixed transmission priorities. Besides, by probing only one additional backup connection, an improvement between 20% to 30% is obtained in terms of network robustness compared with no reinforcement.

In our future work, we will investigate a probable competitive performance ratio by analyzing which of the probed connections the SO activates with a higher probability to reduce the probing cost. Furthermore, we will extend our scenario with heterogeneous IoT devices (SNs) and fog nodes equipped with multiple wireless protocols in different or the same wireless spectrum bands, such as cellular/LoRa (Sub 1GHz), WiFi, Bluetooth, and ZigBee, to collect heterogeneous IoT data. We will study network robustness solutions under heterogeneous traffic patterns and analyze how the traffic changes would affect overall performance.

State transition probability matrix S re defined in (13) consist of the matrixes, S and R as shown at the top of the page.