Cross-layer Design for Mission-Critical IoT in Mobile Edge Computing Systems
Changyang She Yifan Duan Guodong Zhao Tony Q. S. Quek Yonghui Li Branka Vucetic




Cross-layer Design for Mission-Critical IoT in Mobile Edge Computing Systems
    Changyang She, Yifan Duan, Guodong Zhao, Tony Q. S. Quek, Yonghui Li, and Branka Vucetic,







Part of this paper was presented at the International Conference on
Wireless Communications and Signal Processing 2018 <cit.>.

C. She, Y. Li and B. Vucetic are with the School of Electrical and Information Engineering, University of Sydney, Sydney, NSW 2006, Australia (email:shechangyang@gmail.com, {yonghui.li,branka.vucetic}@sydney.edu.au).

Y. Duan is with the School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China (e-mail: duanyifan23@outlook.com).

G. Zhao is with School of Engineering, University of Glasgow, Glasgow, G12 8LT, UK. (e-mail: Guodong.Zhao@glasgow.ac.uk).

T. Q. S. Quek is with the Information Systems Technology and Design Pillar, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372 (e-mail: tonyquek@sutd.edu.sg). 

    Accepted ???. Received ???; in original form ???
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================








	













Cross-layer Design for Mission-Critical IoT in Mobile Edge Computing Systems
    Changyang She, Yifan Duan, Guodong Zhao, Tony Q. S. Quek, Yonghui Li, and Branka Vucetic,







Part of this paper was presented at the International Conference on
Wireless Communications and Signal Processing 2018 <cit.>.

C. She, Y. Li and B. Vucetic are with the School of Electrical and Information Engineering, University of Sydney, Sydney, NSW 2006, Australia (email:shechangyang@gmail.com, {yonghui.li,branka.vucetic}@sydney.edu.au).

Y. Duan is with the School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China (e-mail: duanyifan23@outlook.com).

G. Zhao is with School of Engineering, University of Glasgow, Glasgow, G12 8LT, UK. (e-mail: Guodong.Zhao@glasgow.ac.uk).

T. Q. S. Quek is with the Information Systems Technology and Design Pillar, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372 (e-mail: tonyquek@sutd.edu.sg). 

    Accepted ???. Received ???; in original form ???
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


In this work, we propose a cross-layer framework for optimizing user association, packet offloading rates, and bandwidth allocation for Mission-Critical Internet-of-Things (MC-IoT) services with short packets in Mobile Edge Computing (MEC) systems, where enhanced Mobile BroadBand (eMBB) services with long packets are considered as background services. To reduce communication delay, the 5th generation new radio is adopted in radio access networks. To avoid long queueing delay for short packets from MC-IoT, Processor-Sharing (PS) servers are deployed at MEC systems, where the service rate of the server is equally allocated to all the packets in the buffer. We derive the distribution of latency experienced by short packets in closed-form, and minimize the overall packet loss probability subject to the end-to-end delay requirement. To solve the non-convex optimization problem, we propose an algorithm that converges to a near optimal solution when the throughput of eMBB services is much higher than MC-IoT services, and extend it into more general scenarios. Furthermore, we derive the optimal solutions in two asymptotic cases: communication or computing is the bottleneck of reliability. Simulation and numerical results validate our analysis and show that the PS server outperforms first-come-first-serve servers.



Mission-critical internet-of-things, mobile edge computing, 5G new radio, processor-sharing server, cross-layer optimization





§ INTRODUCTION

Mission-Critical Internet-of-Things (MC-IoT) will be widely deployed in future wireless networks for remote health monitoring, haptic interaction, and factory automation <cit.>. Achieving ultra-reliable and low-latency communications (URLLC) (e.g., 10^-7 packet loss probability and 1 ms End-to-End (E2E) delay) for MC-IoT has been considered as one of the major goals in 5th Generation (5G) cellular networks <cit.>. Most existing technologies mainly focus on one of the seven layers of the open systems interconnection model, and cannot guarantee the E2E delay <cit.>. To satisfy the requirements of MC-IoT, we need to re-design the physical-layer resource management, the link-layer scheduling policy, and the network-layer user association from a cross-layer perspective.

One of the major differences between MC-IoT and enhanced Mobile BroadBand (eMBB) services lies in the sizes of packets. With high data rate, the packet size in eMBB services is relatively large, e.g., thousands of bytes in each packet. However, the packets generated by MC-IoT are very small, e.g., 20 or 32 bytes in each packet <cit.>. To achieve low latency for short packet transmissions, a short frame structure is adopted in 5G New Radio (NR) <cit.>. When transmitting a short packet in a short frame, the blocklength of channel codes is very limited. As a result, the decoding error probability cannot be ignored when analyzing reliability <cit.>.

On the other hand, the computing ability at each MC-IoT device is limited. To reduce processing delay, MC-IoT devices will offload some of the packets to the Mobile Edge Computing (MEC) systems for processing <cit.>. Considering that MC-IoT services will co-exist with eMBB services, a short packet arriving at the MEC after long packets has to wait in a queue if the packets are processed with a First-Come-First-Serve (FCFS) order. To avoid long queueing delay, other scheduling orders at MEC systems should be considered.

Furthermore, the reliability and delay not only depend on the resource management and scheduling order but also depend on the traffic load. Considering that the radio resources and computing capacity at each Access Point (AP) are limited, the user association and offloading policy should be optimized to balance traffic loads. The problems for optimizing user association and offloading policy are NP-hard in general <cit.>. Low-complexity solutions to the NP-hard problems are in urgent need for MC-IoT since complicated searching algorithms will lead to long computation delay <cit.>.



 §.§ Related Works

To transmit short packets with low latency, the blocklength of channel codes is short. In the short blocklength regime, Shannon's capacity is not applicable since it cannot characterize the decoding error probability <cit.>. Recently, the maximal achievable rate with given decoding error probability in the short blocklength regime was obtained in multi-antenna quasi-static channel <cit.>. How to design transmission schemes and resource allocation in the short blocklength regime has been studied in existing literature <cit.>. The throughput achieved in cognitive radio channels and relay systems was studied in <cit.> and <cit.>, respectively. The studies in <cit.> optimized the scheduling of short packets to maximize energy efficiency. The authors of <cit.> optimized packet losses caused by decoding errors, queueing delay violation, and packet dropping over deep fading channel subject to the ultra-high reliability. Considering that the feedback of Channel State Information (CSI) leads to extra delay, the studies in <cit.> jointly optimized Uplink (UL) and Downlink (DL) resource configurations without CSI at the transmitters. More recently, how to optimize resource allocation among multiple users with different packet arrival processes was studied in <cit.>.

Scheduling policies in computing systems have significant impacts on the Quality-of-Service (QoS) of MC-IoT. A near-optimal policy to minimize the average latency of short packet is the Shortest Remaining Processing Time (SRPT) first scheduler. Such a scheduler is hard to implement in practice since the remaining processing time is not available at the server, and it requires too many priority levels<cit.>. To reduce the latency of short packets without introducing priority levels, the Processor-Sharing (PS) server is a possible solution, where the total service rate is equally allocated to all the packets in the server<cit.>. Although the distribution of latency was derived in the large delay regime in the PS server <cit.>, the latency experienced by short packets remains unclear. To derive the delay bound violation probability of URLLC services, martingales-based analysis, effective capacity, and network calculus were used in <cit.>, <cit.>, and <cit.>, respectively. But all the results were obtained in the FCFS servers. Note that it is very challenging to derive the closed-form expression of the distribution of delay, how to formulate the constraints on delay and reliability of MC-IoT is still unclear.

Promising network architectures for MC-IoT were studied in <cit.>. A comprehensive overview on MC-IoT of industrial scenarios was carried out in <cit.>, where the issues related to architecture design were discussed, such as extensibility, scalability, and modularity. To reduce the routing delay, an adaptive transmission architecture with software-defined networks and edge computing was proposed in <cit.>. Considering that energy consumption of IoT devices is an important issue, an energy-aware real-time routing scheme was proposed in <cit.> to reduce energy consumption and E2E delay in large-scale IoT networks. More recently, a fog computing architecture was proposed for 5G tactile IoT <cit.>, where the quality-of-experience-aware model was formulated. By combining stochastic geometry and queueing theory, different QoS requirements were analyzed in ultra-dense networks <cit.>. The studies in <cit.> shed light upon network architecture designs for MC-IoT, but decoding errors in the physical-layer were not considered.

Computing offloading has been exhaustively studied in various MEC systems, such as wireless powered MEC <cit.>, ultra-dense IoT networks <cit.>, and fiber-wireless networks <cit.>. Although these works did not consider MC-IoT, they developed useful methodologies for optimizing computing offloading in MEC systems. How to improve the QoS in MEC systems by optimizing task offloading has been addressed in <cit.>. In <cit.>, the average delay was minimized by optimizing task offloading/scheduling in MEC systems. Considering that the average delay is not suitable for URLLC services, the authors of <cit.> optimized task offloading and resource allocation under the constraint on a queue length violation probability. The offloading schemes for URLLC in MEC systems were optimized in <cit.>, where a weighted sum of E2E delay and the offloading failure probability was minimized in a single-user scenario. How to analyze latency in large-scale MEC networks was studied in <cit.>, where the average communication and computing latencies were derived.

Most of the existing studies on resource management in MEC systems only analyzed UL transmission and processing delay, and assumed DL transmission can be finished with high transmit power at the APs <cit.>. Besides, they did not take the decoding errors in the short blocklength regime into account, which is crucial for MC-IoT. Although the block error probability was considered in the optimization problem in <cit.>, the radio resource management was not optimized and the packet losses due to the delay bound violation were not considered.



 §.§ Our Contributions

To the best of the authors' knowledge, there is no resource allocation scheme or offloading scheme that can achieve the target E2E delay and overall packet loss probability for MC-IoT in MEC systems. Moreover, how to design scheduling policy and whether the FCFS server is suitable for MC-IoT were not addressed. In order to achieve ultra-high reliability and ultra-low E2E delay for MC-IoT in MEC systems, the following three issues will be addressed in this work: 1) How to design scheduling and queueing policies in MEC servers and local servers to achieve ultra-high reliability and ultra-low E2E delay for short packets? 2) How to characterize the statistical QoS of short packets when there are both short and long packets in MEC systems? 3) How to improve the fundamental tradeoff between delay and reliability by optimizing user association, packets offloading, and bandwidth allocation in MEC systems? Our major contributions are summarized as follows,


  * We establish a framework for minimizing overall packet loss probability subject to E2E delay requirement in MEC systems, where processing delay and UL and DL transmission delays are taken into account. PS servers are equipped at MEC systems, where the total service rate is equally allocated to all the packets in each server, and every packet receives service at all times. As such, short packets can bypass long packets and achieve low latency.


  * We derive a closed-form approximation of the Complementary Cumulative Distribution Function (CCDF) of the latency experienced by short packets in the PS server. The approximation is accurate when the number of Central Processing Unit (CPU) cycles needed to process a long packet is much larger than that needed to process a short packet.


  * We optimize the user association scheme, packet offloading rates, and bandwidth allocation for short packets in MEC systems. We propose an algorithm to solve a mixed integer problem and analyze the convergence and the complexity of it. Our analysis shows that the difference between the obtained solution and the global optimal solution only results from searching numbers of subcarriers in a continuous domain.


Furthermore, our simulation results validate the accuracy of the closed-form approximation. Numerical results indicate that when increasing the number of antennas at the AP with a fixed processing capacity, communication is the bottleneck of the reliability when the number of antennas is small, and computing is the bottleneck when the number of antennas is large. Only in a very small region (e.g., from 16 to 18 antennas), the packet loss probability in communications is comparable to the processing delay violation probability. This implies our algorithm converges to a near optimal solution in most of the cases.

The rest of the paper is organized as follows. Section II describes the system model. Section III analyzes delay and reliability. Section IV studies how to optimize the association scheme, packet offloading rates and bandwidth allocation. Section V extends the algorithm into more general scenarios. Section VI provides simulation and numerical results. Section VII concludes the paper.



§ SYSTEM MODEL



 §.§ The MEC System


As illustrated in Fig. <ref>, we consider a MEC system with single-antenna devices and multi-antenna APs, where the data collected by each MC-IoT device and the computation intensive tasks generated by eMBB services can be offloaded to one of the APs for processing. To provide better services in radio access networks and to avoid high backhaul overhead, the partially centralized Control Plane (CP) in <cit.> is considered. The whole network is decomposed into multiple clusters, each of which includes K closely located APs and one CP that optimizes user association scheme, packet offloading rates, and bandwidth allocation for M devices in the cluster. To achieve ultra-low latency and ultra-high reliability, strong co-channel interference should be avoided. To this end, orthogonal channels are allocated to different devices in each cluster, and the frequency reuse factor is less than one such that adjacent clusters use different bandwidth. In this work, we focus on one cluster of APs, and our solution is applicable for low mobility scenarios like factory automation and VR/AR applications. For high mobility scenarios, where devices travel across clusters frequently, how to reserve resources in different clusters deserves further study.



 §.§ Traffic Models

In vehicle networks and factory automation, there are two kinds of packets, i.e., periodic packets with deterministic arrivals and sporadic packets that are driven by some random events <cit.>. Since analyzing the delay and the reliability of random packet arrival processes is more challenging than deterministic arrivals, we focus on sporadic packets in this work. The experiment in <cit.> indicates that the packet arrival processes of MC-IoT are very bursty, i.e., there is a high traffic state and a low traffic state. For each of the traffic states, the arrival process can be modeled as a Bernoulli process. According to 5G NR, time is discretized into slots with duration T_ s. In each slot, a device either has a packet to transmit or stays silent. We assume the traffic state is obtained with the traffic state classification methods in <cit.>. When a device switches between the high and low traffic states, we only need to change the average arrival rate in our analysis. The aggregation of multiple independent Bernoulli processes at a MEC server can be accurately approximated by a Poisson process <cit.>.



  §.§.§ Short packets
 The data collected by each MC-IoT device is contained in short packets for transmission and processing. A packet with the following three features is considered as “short",


  * The number of bits in the packet is small. According to <cit.>, the packet size in MC-IoT services is around 20 or 32 bytes. In contrast, the packets in eMBB services may include hundreds or thousands of bytes, such as video streaming.


  * The blocklength of channel codes of the packet is short. For example, if quadrature phase-shift keying is used in modulation, the number of symbols required by a packet with 32 bytes (256 bits) is 128, which is the blocklength of the packet. To achieve low-latency, the blocklength of channel codes is short in MC-IoT <cit.>.


  * The number of CPU cycles required to process the packet is small. The number of CPU cycles required to process the packet depends on the number of bits in the packet and the processing algorithms. Since a packet in MC-IoT services only contains a few bits, the number of required CPU cycles is small.

Let c_ S be the number of CPU cycles required to process a short packet.  The service rate of the local server at the kth device and that of the mth MEC server are denoted as C_k and S_m (CPU cycles/slot), respectively.



  §.§.§ Long packets
 There are some devices requesting eMBB services in each cluster. The tasks generated by the eMBB services are packetized into long packets. How to optimize resource allocation and computing offloading for eMBB services has been studied in the existing literature, such as <cit.>. In our work, we focus on MC-IoT services, where eMBB services are considered as background services.

The sum of average packet arrival rates of eMBB services at the mth AP is denoted as λ^ L_m (packets/slot). The number of CPU cycles required to process a long packet is denoted as c_ L, which is a random variable with mean value c̅_ L. In this work, we do not specify the distribution of c_ L. The only assumption on c_ L is that c_ L≫ c_ S, which is reasonable since the packet size of eMBB services is much larger than that of MC-IoT services and the algorithm for processing long packets (e.g., high definition pictures) is more complex than that for processing short packets (e.g., the location and velocity of a device). For example, c_ L may follow the Pareto distribution with a heavy tail <cit.>, i.e.,

    {c_ L/c_ S > x} = p_ A x^-v,

where 1<v<2, p_ A = (c_0/c_ S)^v, and c_0 is the minimum of c_ L. As shown in <cit.> and the references therein, Pareto distributions have been observed in different application scenarios, such as the service time of UNIX jobs.



 §.§ User Association and Packet Offloading



  §.§.§ User association
 Each device can associate with one of the APs. We leverage indicators x_k,m, k=1,...,K, m=1,...,M, to represent the user association scheme,

    x_k,m = {[ 1, if device k is associated with AP m,;                           0, otherwise. ].

The association scheme of the kth device is denoted as x_k = [x_k,1,...,x_k,M]^T.



  §.§.§ Packet offloading
 When a short packet is generated by the kth device, the device either processes the packet with the local server or uploads the packet to an AP. The average packet rate from the kth device to the mth MEC server is denoted as λ_k,m (packets/slot), where k=1,2,...,K, and m=0,1,...,M. m=0 means that the packets are processed at the local server. If x_k,m'=1, then λ_k,0 + λ_k,m' = λ_k^ U, where λ^ U_k is the average packet arrival rate of the kth device. If x_k,m=0 for all m=1,...,M, then λ_k,0 = λ^ U_k.




 §.§ Queueing Models and Scheduling Policies




As shown in Fig. <ref>(a), to guarantee the QoS requirements of different devices, packets from different devices are waiting in different queues at a MEC server, and are served according to the FCFS order. In the mth MEC server, the service rate allocated to the kth device is denoted as S_k,m. Once the computing resource is allocated to one device, it cannot be shared with the other devices. Such a scheduling scheme is widely used, but is not optimal in terms of minimizing the delay.

The second server in Fig. <ref>(b) is referred to as a statistical multiplexing FCFS server <cit.>. Due to statistical multiplexing gain, the average delay in the second server is much shorter than the first server when S_m =∑_k S_k,m. Furthermore, as proved in <cit.>, if the sizes of all the packets are identical, to achieve the same delay bound and delay bound violation probability, the required service rate in the statistical multiplexing server is less than the sum of the service rates in the individual server. However, when the distribution of the number of CPU cycles required to process the packets has a heavy-tail, some short packets arriving at the MEC server after a long packet need to wait for a long time. As a result, the delay requirement of MC-IoT services can hardly be satisfied.

The key to low latency is letting short packets bypass queued long packets. One possible solution is the PS server. As shown in Fig. <ref>(c), every packet in the server receives service at all times. When there are i packets in the mth MEC server, each packet is processed at rate S_m/i.


In practice, a server can be implemented in a time-sharing way, i.e., the service time in each slot is equally allocated to all the packets in the server. In this way, the processing delay of packets in the server is the same as that in the ideal PS server <cit.>. It's worth noting that there are some other possible scheduling policies if the server is aware of the diverse QoS requirements of different packets. In this work, we do not assume the computing system is aware of the types of packets in the communication systems. We will study more sophisticated scheduling policies for different types of packets in our future work.




We consider the scheduling policies at MEC servers and local servers in Fig. <ref>, where PS servers are deployed at APs and FCFS servers are deployed at devices. To avoid queueing delay, the UL and DL transmission durations of a short packet equal to one slot.[Since the packet arrival rate of each device is less than one packet per slot, there is no queue before UL and DL transmissions.]  On the other hand, if the required CPU cycles to process different packets are identical, which is the case in the local server of each device, the FCFS server outperforms the PS server <cit.>. Therefore, FCFS servers are equipped at MC-IoT devices.



§ ANALYSIS OF DELAY AND RELIABILITY

In this section, we study how to characterize E2E delay and overall packet loss probability. We first derive the CCDF of the processing delay of short packets in the PS server. Then, we show how to characterize the transmission delay and decoding error probability of short packets.



 §.§ Processing Delay and Delay Violation Probability

A short packet can be processed either at the device or at the AP. The packet arrival process at the local server of the kth device is a Bernoulli process with average arrival rate λ_k,0. Denote the service time of a packet at the kth local server as D_k^ loc = c_ S/C_k. With the constant service rate at each local server, the queueing model is a Geo/D/1/FCFS model, where “Geo" means that the inter-arrival time between packets is geometric distributed, and “D" represents deterministic service processes. The CCDF of queueing delay in Geo/D/1/FCFS model has been obtained in <cit.>. If i ≤ D_k^ loc - 1, then

    {D_k^ q > i}=1-( 1 - λ _k,0)^ - i-1(1-λ _k,0D_k^ loc).

If i ≥ D_k^ loc, the expression of {D_k^ q > i} can be found in <cit.>.
Due to the low-latency requirement, we are interested in the case i ≤ D_k^loc - 1.

Each AP may serve multiple devices. The aggregation of multiple Bernoulli processes can be modeled as a Poisson process <cit.>. Thus, the MEC server can be characterized by an M/G/1/PS model, where “M" means the packet arrival process is Poisson process and “G" means that the number of CPU cycles required to process the packets can follow any distributions. To derive a closed-form CCDF of the processing delay of short packets in the M/G/1/PS model, we introduce an accurate approximation. Since the short packets are much smaller than the long packets, i.e., c_ S≪ c_ L, the processing delay of a short packet is much shorter than a long packet. As a result, the number of long packets in the server is nearly constant from the arrival to the departure of a short packet. When a short packet arrives at the server, the number of packets in the server is denoted as Q_m. Considering that the value of Q_m does not change significantly during the short service time of a short packet, then the service rate allocated to the short packet can be approximated by S_m/(q+1) if Q_m = q. In this case, the processing delay of the short packet is approximated by

    W^ S_m|_Q_m = q≈c_ S(q+1)/S_m  (slots).


According to <cit.>, the distribution of Q_m can be expressed as follows,

    {Q_m = q} = ρ_m^q(1-ρ_m),

which is the distribution of the number of packets in the M/G/1/PS model. The workload of the server is

    ρ_m = ∑_k=1^Kλ_k,mc_ S + λ^ L_m c̅_ L/S_m.

From (<ref>) and (<ref>), we can further obtain that

    {W^ S_m = c_ S(q+1)/S_m}≈{Q_m = q} = ρ_m^q(1-ρ_m),

where q=0,1,.... Based on the above expression, the CCDF of the processing delay of short packets in the PS server can be derived as follows,

    {W^ S_m > c_ S(q+1)/S_m}   ≈{Q_m > q} = ρ_m^q.

The approximation in (<ref>) is accurate when c_ S≪ c_ L. We will validate the accuracy of the approximation via simulation.

The processing delay of short packets in the mth MEC server can be characterized by a delay bound and a delay bound violation probability, D^ mec_m and ε^ mec_m. From the CCDF in (<ref>), the relationship between ε^ mec_m and D_ m^ mec can be expressed as follows,

    ε _m^mec = ρ_m^( S_mD_m^mec/c_S - 1).






 §.§ Transmission Delay and Decoding Error Probability

If a packet is processed at the MEC server, the device first uploads the packet to the AP. After the MEC server finishes the processing, the result is sent back to the device. We introduce a superscript of parameters X^ξ, where ξ∈{u,d}. If ξ = u, X is a parameter in UL transmissions. Otherwise, it is a parameter in DL transmissions. We consider Orthogonal Frequency Division Multiple Access (OFDMA) systems, which will be used to support MC-IoT services in 5G NR <cit.>. The total bandwidth is equally allocated to N_max subcarriers, each with a bandwidth of W_0. Denote the number of subcarriers allocated to the kth device for UL and DL transmissions as N^ξ_k, ξ∈{u,d}, respectively. Since the packet size is small, it is reasonable to assume that N^ξ_kW_0 is smaller than the coherence bandwidth. As mentioned in the previous section, to avoid queueing delay before UL and DL transmissions, the transmission duration of each packet is one slot, which is smaller than channel coherence time. Thus, each packet is transmitted over a flat fading quasi-static channel. Considering that feedback from receivers to transmitters may cause large overhead and extra delay, CSI is not available at the transmitters. According to <cit.>, the achievable rate in the short blocklength regime over quasi-static flat fading channel can be accurately approximated by

    R^ξ_k,m≈N^ξ_kW_0/ln 2   [ ln( 1 + α_k,mg^ξ_k,mP^ξ_ s/N_0W_0) 
       - √(V_k,m^ξ/T_ sN^ξ_kW_0) f_Q^ - 1( e^ξ_k,m) ] bits/s,

where α_k,m is the large-scale channel gain from the kth device to the mth AP, g^ξ_k,m is the UL or DL small-scale channel fading between the kth device and the mth AP, P_ s^ξ is the UL or DL transmit power of one antenna on each subcarrier, N_0 is the single-side noise spectral density, f_Q^-1(.) is the inverse of Q-function, e^ξ_k is the decoding error probability, and V_k,m^ξ = 1 - 1/( 1 + α_k,mg^ξ_k,mP^ξ_ s/N_0W_0)^2.


Due to the following two reasons, we only consider the flat fading channel, and do not consider frequency-selective channels. First, the maximal achievable rate over a frequency-selective channel in the short blocklength regime has not been derived in existing studies. Although the upper and lower bounds were obtained in <cit.>, there is no closed-form expression. Second, as shown in <cit.>, when the number of antennas is large (e.g., 16 antennas), frequency diversity is not necessary for URLLC. Therefore, we focus on the multi-antenna flat fading channel. 


Let b^ξ_k be the number of bits in a short packet of the kth device. When sending a packet of b^ξ_k bits within one slot, the decoding error probability can be obtained from (<ref>) by setting T_ sR^ξ_k,m = b^ξ_k. According to the law of total probability, the packet loss probability due to decoding errors can be expressed as follows <cit.>,

    ε_k,m^ξ   ≈𝔼_g^ξ_k,m{e^ξ_k,m}=𝔼_g^ξ_k,m{f_ Q( √(T_ sN^ξ_kW_0/V_k^ξ)
       ×[ ln( 1 + α_k,mg^ξ_k,mP^ξ_ s/N_0W_0) - b^ξ_kln 2/T_ sN^ξ_kW_0] )},

where the distribution of small-scale channel gain depends on the number of antennas at each AP, which is denoted as N_ t. To compute (<ref>), we need to calculate the integral for a given distribution of g^ξ_k,m. For Rayleigh fading, we can apply the closed-form result in <cit.>.



 §.§ E2E Delay and Overall Packet Loss Probability



  §.§.§ Delay and Reliability at Local Servers
 If a packet is processed at the device, then the E2E delay is equal to the sum of the service time and the queueing delay at the local server of the device. Given the E2E delay requirement D_max, the delay violation probability at local servers, ε_k^ loc, can be obtained by substituting i = D_max- D_k^loc into (<ref>). When D_max- D_k^loc≤ D_k^loc - 1,

    ε_k^ loc = 1-( 1 - λ _k,0)^ - (D_max- D_k^loc)-1(1-λ _k,0D_k^ loc).




  §.§.§ Delay and Reliability at the MEC server
 If a packet is processed at a MEC server, then the UL and DL transmission delays and the processing delay in the server should be considered. The E2E delay can be satisfied under the following constraint,

    2 + D^ mec_m≤ D_max,

where two slots are occupied by the UL and DL transmissions.

Due to decoding errors and processing delay violation, the overall packet loss probability can be expressed as follows,

    ε^ A_k,m   = 1-(1- ε_k,m^ u)(1- ε_k,m^ d)(1- ε _m^mec)
       ≈ε_k,m^ u + ε_k,m^ d + ε _m^mec,

where the approximation is very accurate since ε_k,m^ u, ε_k,m^ d, and ε _m^mec are extremely small in MC-IoT. Upon substituting (<ref>) and (<ref>) into (<ref>), we can get the expression of ε_m^mec, i.e.,

    ε_m^mec = (∑_k=1^Kλ_k,mc_ S + λ^ L_m c̅_ L/S_m)^S_m (D_max-2) /c_S - 1.



The factors that lead to packet losses or errors depend on network architectures <cit.>. For the considered MEC system, reliability only includes queueing delay violations in computing systems and packet losses in radio access networks.





§ CROSS-LAYER OPTIMIZATION

In this section, we study how to optimize the association scheme, packet offloading rates, and UL and DL bandwidth allocation to minimize the overall packet loss probability subject to the E2E delay requirement.



 §.§ Problem Formulation

Note that the packet loss probabilities at the local server and the MEC can be different, the reliability is determined by the worse one. Thus, the packet loss probability of the kth device is characterized by

    f_k(x_k,λ_k,m,N^ u_k,N^ d_k)
       =max[ε_k^ loc,x_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec), ∀ m].

The problem that minimizes the maximal packet loss probability experienced by the K devices can be formulated as follows,

    min_x_k,λ _k,m,N_k^u,N_k^d_k = 1,...,K max_k = 1,...,Kf_k(x_k,λ _k,m,N_k^u,N_k^d)
    s.t.     ∑_m=1^M x_k,m≤1, x_k,m∈{0,1}, a
         0≤λ_k,m≤ x_k,m,  b
        ∑_m=1^Mλ_k,m + λ_k,0 = λ_k^ U,  c
        ∑_k=1^KN_k^u + ∑_k=1^KN_k^d≤ N_max, N_k^u, N_k^d∈{1,2,...,N_ c},  d
        max{ε_k^loc, x_k,m(ε_k,m^ u+ ε_k,m^ d+ ε_m^mec), ∀ m}≤ 1,  e

where k = 1,...,K, m =1,...,M, N_ c is the maximum number of subcarriers that can be allocated to a device without exceeding the coherence bandwidth, and the expressions of ε_k,m^ξ, ε_k^ loc, and ε_m^mec can be found in (<ref>), (<ref>), and (<ref>), respectively. Constraint (<ref>) guarantees that a device can only associate with one AP. If ∑_m=1^M x_k,m = 0, then all the packets are processed at the local server.

With constraint (<ref>), each device cannot be served by two or more APs. Constraint (<ref>) ensures that the packet offloading rate λ_k,m is zero if the kth device is not served by the mth AP. Constraint (<ref>) guarantees that the sum of the packet offloading rates at the APs and the packet arrival rate at the local server is equal to the total packet arrival rate of a device. The constraint on the maximal number of subcarriers of the system is given in (<ref>), where the UL and DL bandwidth allocated to each device does not exceed the coherence bandwidth. When constraint (<ref>) is satisfied, ε_k^loc and ε_m^mec are smaller than 1, and hence the local and MEC servers are stable. By minimizing the objective function, we can check whether constraint (<ref>) can be satisfied or not. If it cannot be satisfied, the problem is infeasible.

Since CSI is not available at the transmitters, the transmit power on each subcarrier is fixed. In UL transmission, the maximal transmit power of a device, P^ U_max, is equally allocated to N_ c subcarriers, P_ s^ u = P^ U_max/N_ c. In DL transmission, the maximal transmit power of an AP, P^ A_max, is equally allocated to N_ t antennas. Considering that the number of subcarriers for DL transmission can be up to N_max, to satisfy maximal transmit power constraint, the transmit power on each subcarrier is fixed as P^ A_max/N_max. Thus, we have P_ s^ d = P^ A_max/N_maxN_ t.

Problem (<ref>) is a mixed integer optimization problem, which is non-convex. In typical scenarios, the throughput of eMBB services is much higher than the throughput of MC-IoT services, and hence the number of CPU cycles required to process long packets are much larger than that required to process short packets. In the rest part of this section, we first consider the scenario that (∑_k=1^Kλ^ U_kc_ S) / (λ^ L_m c̅_ L)  → 0, and then extend our algorithm into more general scenarios.



 §.§ Solution in the Typical Scenario



  §.§.§ Simplified Optimization Problem
 According to (<ref>), λ_k,m≤λ^ U_k. Thus, we have

    ρ_m = ∑_k=1^Kλ_k,mc_ S + λ^ L_m c̅_ L/S_m≤∑_k=1^Kλ^ U_kc_ S + λ^ L_m c̅_ L/S_m≜ρ^ ub_m.

When (∑_k=1^Kλ^ U_kc_ S) / (λ^ L_m c̅_ L) → 0, the equality in (<ref>) holds, and ε_m^mec in (<ref>) is a constant that does not depend on packet offloading rates. Moreover, the packet loss probabilities due to decoding errors in UL and DL transmissions, ε_k,n^ u and ε_k,n^ d, do not change with packet offloading rates. Thus, the second term in max[ε_k^ loc,x_k,m(ε_k,n^ u + ε_k,n^ d + ε_m^mec), ∀ m] does not depend on packet offloading rates. By setting λ_k,m = λ^ U_k, all the packets are offloaded to the MEC servers. Then, ε_k^ loc = 0 and

    f_k(x_k,λ_k,m,N^ u_k,N^ d_k) = max_m=1,...,Mx_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec).

With (<ref>), problem (<ref>) can be simplified as follows,

    min_x_k,N_k^u,N_k^d_k = 1,...,K max_k = 1,...,K_m = 1,...,M   x_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec)
    s.t.     (<ref>), (<ref>),  and (<ref>).




  §.§.§ Packet Loss Balance Algorithm
 Denote the optimal solution and the minimal packet loss probability of problem (<ref>) as (x̃_k,Ñ_k^u,Ñ_k^d) and ε̃^ A, respectively. In the following, we propose a binary search algorithm to find the optimal solution. The basic idea of the algorithm is to keep ε_k,m^ u + ε_k,m^ d + ε_m^mec, k=1,...,K,m=1,...,M, below a threshold ε_ th, and search the minimal ε_ th in the regime (0,ε_ in], where ε_ in≤ 1 is an initial upper bound of the overall packet loss probability. We refer to the algorithm as the Packet Loss Balance (PLB) Algorithm.

For a given threshold of overall packet loss probability ε_ th, we search for the optimal association scheme and subcarrier allocation that minimize the total number of subcarriers. If the minimum number of subcarriers exceeds N_max, then ε̃^ A > ε_ th. Otherwise, ε̃^ A≤ε_ th.

The problem that minimizes the total number of subcarriers can be expressed as follows,

    min_x_k,N_k^u,N_k^d_k = 1,...,K    ∑_k=1^KN_k^u + ∑_k=1^KN_k^d
    s.t.     x_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec)≤ε_ th, a
        N_k^u, N_k^d∈{1,2,...,N_ c},  and (<ref>),

where constraint (<ref>) is removed since ε_ th<1. The above problem can be decoupled into K problems since the association schemes and bandwidth allocation of different devices are independent.

Given that the kth device is served by the m'th MEC server, x_k,m' = 1, the required number of subcarriers can be found from the following problem,[By solving problem (<ref>) with different m' = 1,...,M, we can obtain the optimal user association scheme and related bandwidth allocation that minimize N_k^u+N_k^d.]

    min_N_k^u,N_k^d    N_k^u+N_k^d
    s.t.     ε_k,m'^ u + ε_k,m'^ d +ε_m'^mec≤ε_ th, a
        N_k^u, N_k^d∈{1,2,...,N_ c}.

To solve the inter programming problem, we first relax N_k^u and N_k^d as continuous variables, and find the optimal subcarrier allocation. Then, we discretize the number of subcarriers used in UL and DL transmissions. Note that only the discretization
step will cause performance loss, which is minor as shown in <cit.>.

To solve problem (<ref>), we need the following property of (<ref>).

The packet loss probabilities ε_k,m'^ u and ε_k,m'^ d in (<ref>) are convex in N_k^ξ.

See proof in Appendix <ref>.



Further considering that ε_m'^mec in (<ref>) does not change with N_k^ξ, constraint (<ref>) is convex. Therefore, problem (<ref>) is a convex problem, and can be solved by techniques such as the interior-point method <cit.>. The algorithm for solving problem (<ref>) is provided in Table <ref>, where ⌈ x ⌉ is the minimum integer that is equal to or higher than x.





Note that problem (<ref>) could be infeasible if ε_ th is too small. In this case, the minimal overall packet loss probability is higher than ε_ th. Based on the algorithm in Table <ref>, the PLB algorithm for solving problem (<ref>) is shown in Table <ref>.







  §.§.§ Convergence of the PLB Algorithm

To prove that the PLB algorithm converges to the minimal packet loss probability of problem (<ref>), we first prove the following proposition,


The minimal packet loss probability ε^ A* lies in the region (ε^ LB(i), ε^ UB(i)], ∀ i∈{1,2,3,...}.

See proof in Appendix <ref>.


According to Proposition <ref>, the minimal packet loss probability lies in the region (ε^ LB(i), ε^ UB(i)]. After i steps of searching, the gap between ε^ A* and the output of the PLB algorithm, ε̃^ A, is smaller than 0.5[ε^ UB(i)-ε^ LB(i)]. In addition, with the binary search algorithm (i.e. from Line 1 to Line 11 in Table <ref>), the range of (ε^ LB(i),ε^ UB(i)] decreases according to the following expression, ε^ UB(i)-ε^ LB(i) = ε_ in/2^i. When i is large enough, ε̃^ A approaches to ε^ A*.

The above proof holds when the performance loss caused by the discretization step in Line 7 of Table <ref> is negligible. Since the discretization step inevitably causes some performance loss, the related association scheme and bandwidth allocation are near optimal.



  §.§.§ Complexity of the PLB Algorithm

With the PLB algorithm, we need to solve problem (<ref>) around log_2(ε_ in/Δ_ε) times. Problem (<ref>) is decoupled into K single-device problem in (<ref>). With the algorithm in Table <ref>, the convex optimization problem in (<ref>) is solved KM times for K devices with M possible APs. The complexity of solving the convex optimization problem is denoted as Ω_0, which is not high. Therefore, the complexity of the PLB algorithm is 𝒪(log_2(ε_ in/Δ_ε)KMΩ_0). Considering that a device will not associate with an AP that is very far from it, M will not be very large. For example, a device can only be connected to one of the three or four APs with the highest large-scale channel gains. As a result, the complexity of the PLB algorithm increases linearly with the number of devices.





§ SOLUTION IN GENERAL SCENARIOS

To solve problem (<ref>), we extend the PLB algorithm into general scenarios without the assumption (∑_k=1^Kλ^ U_kc_ S) / (λ^ L_m c̅_ L)  → 0.



 §.§ Extended PLB Algorithm

Although problem (<ref>) cannot be simplified as problem (<ref>), we can still use the algorithm in Table <ref>. The difference between the general scenarios and the scenario with the assumption (∑_k=1^Kλ^ U_kc_ S) / (λ^ L_m c̅_ L)  → 0 lies in Line 3 of the algorithm, where problem (<ref>) is obtained from (<ref>). In general scenarios, given the threshold of overall packet loss probability, ε_ th, the optimization problem that minimizes the total number of subcarriers can be expressed as follows,

    min_x_k,λ_k,m,N_k^u,N_k^d_k = 1,...,K ∑_k=1^KN_k^u + ∑_k=1^KN_k^d
    s.t.     max[ε_k^ loc, x_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec), ∀ m ]≤ε_ th, a
        N_k^u, N_k^d∈{1,2,...,N_ c}, (<ref>), (<ref>),   and (<ref>).


From the expression of ε_m^mec in (<ref>), we can see that ε_m^mec increases with the packet offloading rate λ_k,m. Besides, the expressions of ε_k,m^ u and ε_k,m^ d in (<ref>) show that the required number of subcarriers increases as ε_k,m^ξ decreases. Therefore, to satisfy constraint (<ref>), the number of subcarriers increases with the packet offloading rate λ_k,m. To minimize the total number of subcarriers, the first step is minimizing packet offloading rates.

Step 1: Optimize offloading rates. To minimize packet offloading rates, we find the maximal packets arrival rate at the local server, denoted as λ̃_k,0(i). Note that the delay violation probability at each local server should satisfy ε_k^ loc≤ε_ th, by substituting the expression of ε_k^ loc in (<ref>) into the constraint, λ̃_k,0(i) can be obtained via binary search. If λ̃_k,0(i) > λ_k^ U, all the packets are processed at the local server, λ_k,m(i)=0, x_k,m(i) = 0, m=1,...,M and N_k^ u=N_k^ d=0. Otherwise, the packet offloading rate of the kth device is ∑_m=1^Mλ_k,m(i) = λ_k^ U-λ̃_k,0(i). As such, the constraint on the packet offloading rate in (<ref>) can be expressed as follows,

    ∑_m=1^Mλ_k,m  = max[0,λ_k^ U-λ̃_k,0(i)], k = 1,...,K.

According to (<ref>) and (<ref>), each device only offload it's packets to one AP. Thus, the value of λ_k,m is determined by x_k,m. If x_k,m=1, λ_k,m = max[0,λ_k^ U-λ̃_k,0(i)]. Otherwise, λ_k,m = 0.

With the minimal packet offloading rates, problem (<ref>) can be simplified as follows,

    min_x_k,N_k^u,N_k^d_k = 1,...,K    ∑_k=1^KN_k^u + ∑_k=1^KN_k^d
    s.t.      x_k,m(ε_k,m^ u + ε_k,m^ d + ε_m^mec) ≤ε_ th,  a
        λ_k,m = x_k,mmax[0,λ_k^ U-λ̃_k,0(i)]  a
        N_k^u, N_k^d∈{1,2,...,N_ c},  and (<ref>).

where k=1,...,K, and m=1,...,M.
Different from problem (<ref>), problem (<ref>) cannot be decoupled into K subproblems. This is because the workloads of the APs depend on association schemes of all the devices. As a result, ε_m^mec changes with x_k,m. Changing the association scheme of one device will lead to different overall packet loss probabilities of all the other devices.

Based on this fact that the throughput of eMBB services is higher than MC-IoT services in most of the scenarios, we optimize the association scheme given the optimal bandwidth allocation obtained from problem (<ref>), and then update bandwidth allocation according to the association scheme and related workloads at MEC servers.

Step 2: Optimize the association scheme x_k(i). We set N_k^ u and N_k^ d as the values that are obtained under the assumption (∑_k=1^Kλ^ U_kc_ S) / (λ^ L_m c̅_ L)  → 0, and compute ε^ u_k,m+ε^ d_k,m, k=1,...,K, m = 1,...,M. The initial workloads of the MEC servers are ρ̂_m = λ^ L_m c̅_ L/S_m, m=1,...,M. From (<ref>) we can obtain the initial delay bound violation probability ε̂_m^mec. Then, from the 1st device to the Kth device, each device selects one AP that can minimize ε^ u_k,m+ε^ d_k,m+ε̂_m^mec. Denote m̂_k as the AP that minimizes ε _k,m^u + ε _k,m^d + ε̂_m^mec. The m̂_kth element of x_k(i) equals to one and λ_k,m̂_k = max[0,λ_k^ U-λ̃_k,0(i)], λ_k,m = 0, ∀ m m̂_k. After the kth device is associated with the m̂_kth AP, the workload is updated according to ρ̂_m = (λ_1,mc_ S+λ_2,mc_ S+...+λ_k,mc_ S+λ^ L_m c̅_ L)/S_m.

Step 3: Update bandwidth allocation N_k^ u and N_k^ d. Given x_k(i), we solve problem (<ref>) for each device, and obtain the bandwidth allocation.


The packet offloading rates obtained in Step 1 and the bandwidth allocation obtained in Step 3 are optimal with given x_k(i). If we can obtain the optimal association scheme in Step 2, then we can obtain the optimal solution of problem (<ref>). However, the final workloads of the APs are not exactly the same as the initial values. Thus, x_k(i) obtained in Step 2 is not optimal. However, x_k(i) is near optimal if the association scheme of MC-IoT services has little impacts on the workloads of the APs. To provide more insights, we will prove that x_k(i) is optimal in two asymptotic cases in the sequel.




 §.§ Optimal Access Schemes in Two Asymptotic Cases

In this subsection, we derive the optimal association scheme of problem (<ref>) in the two asymptotic cases: communication or computing is the bottleneck of the overall packet loss probability. Whether communication or computing is the bottleneck depends on the number of antennas at each AP and the processing ability of the MEC server. In the next section, we will show the assumption that either communication or computing is the bottleneck is reasonable for various system parameters.



  §.§.§ Communication is the Bottleneck

When the MEC servers have enough computing resources, the processing delay bound violation probability is much smaller than packet loss due to decoding errors, i.e., ε_m^ mec≪ε_k,m^ξ. In this case, communication is the bottleneck of reliability. Denote x^ comm_k, k =1,...,K, as the association scheme that the kth device is served by the m_k^*th AP, which has the highest large-scale channel gain among all the APs, i.e., α_k,m_k^* > α_k,m'_k, ∀m'_k≠ m^*_k. The following proposition indicates that x^ comm_k is the optimal association scheme if ∑_m=1^Mx_k,m = 1.


 If ∑_m=1^Mx_k,m = 1, then for any solution of problem (<ref>), (x_k,m'_k=1, λ_k,m,N_k^u,N_k^d), we can always find another solution, (x_k,m^*_k=1, λ_k,m,N_k^u,N_k^d), that can achieve smaller packet loss probability.

Since α_k,m^*_k≥α_k,m'_k and the decoding error probability in (<ref>) decreases with the large-scale channel gain, we have ε^ξ_k,m^*_k≤ε^ξ_k,m'_k. Therefore,

    max_k=1,...,Kmax[ε_k^ loc,x_k,m'_k(ε_k,m'_k^ u + ε_k,m'_k^ d), ∀ m] 
       ≤max_k=1,...,Kmax[ε_k^ loc,x_k,m^*_k(ε_k,m^*_k^ u + ε_k,m^*_k^ d)].

This completes the proof.



When all the packets of the kth device are processed at the local server, λ_k,0 = λ_k^ U, if ε_k^ loc≤ε_k,m^*^ u+ε_k,m^*^ d,  then x_k,m = 0, ∀ m, and N_k^ u=N_k^ d=0. Otherwise, the device uploads some packets to the MEC servers to achieve better reliability, and hence ∑_m=1^Mx_k,m = 1.




  §.§.§ Computing is the Bottleneck

When there are very limited computing resources at the APs and no processing unit at devices, the packet loss probability due to decoding errors is much smaller than the processing delay violation probability, i.e., ε_k,m^ξ≪ε^ mec_m. In this case, all the packets are processed at the MEC servers, and the objective function of problem (<ref>) can be simplified as follows,

    max_k = 1,...,K x_k,mε_m^ mec.

Let x^ comp_k, k =1,...,K, be the optimal association scheme when computing is the bottleneck, respectively. To find the optimal solution, we denote the average packet arrival rate at the mth MEC server as λ_m^ A. Then, λ_m^ A = ∑_k=1^Kλ_k,m and

    ∑_m=1^Mλ_m^ A=∑_m=1^M∑_k=1^Kλ_k,m.

Given the average arrival rate of each MEC server, the processing delay bound violation probability can be expressed as ε_m^ mec = ρ_m^S_m(D_max-2)/c_ S-1, where ρ_m = λ^ A_mc_ S+λ_m^ Lc̅_ L/S_m.

Let ε^ A* and ρ^* be the minimal value of (<ref>) and the workload achieved by the optimal association scheme, respectively. If λ_m^ Lc̅_ L/S_m≥ρ^*, then x_k,m = 0, ∀ k, and λ_m^ A^* = 0. Let ℳ be the set of MEC servers with λ_m^ Lc̅_ L/S_m < ρ^*. From ρ^* = λ^ A^*c_ S+λ_m^ Lc̅_ L/S_m, we can derive

    λ_m^ A^* = ρ^*S_m-λ_m^ Lc̅_ L/c_ S, ∀ m ∈ℳ.

Substituting λ_m^ A^* into (<ref>), we can derive that

    ρ^* = ∑_m=1^M∑_k=1^Kλ_k,mc_S  + ∑_m ∈ℳλ _m^Lc̅_L/∑_m ∈ℳS_m.

To obtain ρ^* and the related λ_m^ A^*, we need to obtain ℳ. Without loss of generality, we assume λ_1^ Lc̅_ L/S_1≤λ_2^ Lc̅_ L/S_2≤...≤λ_M^ Lc̅_ L/S_M. Then, ℳ can be expressed as ℳ = {m=1,..., M_ th}. Then, we can use the binary search algorithm to find the maximal M_ th that satisfies λ_m^ A^* > 0, ∀ m ≤ M_ th. As illustrated in Fig. <ref>, the basic idea of the optimal solution is offloading packets to the MEC servers with lower workloads.



On the one hand, since the association scheme is discretized, perhaps there is no association scheme that can keep the workloads of the M_ th MEC servers exactly the same. On the other hand, if it is possible to satisfy ρ_m = ρ^* in all the M_ th servers, x_k^ comp may not be unique. For example, if λ^ U_1 = λ_2^ U, exchanging x^ comp_1 and x^ comp_2 does not change the workloads of the servers. Any association schemes that satisfy ρ_m = ρ^*, ∀ m ≤ M_ th, are optimal.



 §.§ Convergence of the Extended PLB Algorithm

When communication is the bottleneck, ε _k,m^u + ε _k,m^d + ε̂_m^mec≈ε _k,m^u + ε _k,m^d. Since the decoding error probability in (<ref>) decreases with the large-scale channel gain, each device is associated with the MEC server with the largest large-scale channel gain. Thus, the association scheme obtained in Step 2 of the extended PLB algorithm is the same as the optimal association scheme when communication is the bottleneck, x_k^ comm.

When computing is the bottleneck of reliability,  ε _k,m^u + ε _k,m^d +  ε _m^mec≈ε _m^mec. In the second step of the extended PLB algorithm, each device connected to the MEC server with the lowest workload. Then, the association scheme is the same as the optimal association scheme in Fig. <ref>, x_k^ comp.




 §.§ Complexity of the Extended PLB Algorithm
 In the first step, we can use the binary search algorithm to find each λ_k,0(i) with low complexity Ω_1. In the second step, we find m̂_k from M MEC servers for each of the K devices. Denote the complexity for computing ε _k,m^u + ε _k,m^d + ε̂_m^mec as Ω_2. Then, the complexity of the second step is around MKΩ_2. In the third step, we need to solve problem (<ref>) K times. Thus, the complexity is KΩ_0. Therefore, the complexity of the extended PLB algorithm is 𝒪((KΩ_0+KΩ_1 + MKΩ_2)log_2(ε_ in/Δ_ε)), which is linear with the number of devices.



§ SIMULATION AND NUMERICAL RESULTS

In this section, we validate the approximation of the CCDF of the processing delay of short packets in the PS server. To show the performance gain of our proposed framework, we compare the distributions of delay with PS servers and that with FCFS servers.[Although there are some related works, none of them took both uplink and downlink transmissions of short packets into account, and few of them optimized offloading policy from multiple devices to multiple APs with random packets arrival processes.] Besides, we illustrate the near optimal association scheme obtained with the extended PLB algorithm, and compared it with the optimal solution in the asymptotic cases. Finally, the reliability achieved by the extended PLB algorithm is illustrated in the scenarios with different communication and computing resources.



 §.§ Simulation Setup




The simulation scenario is shown in Fig. <ref>, where 4 APs serve multiple MC-IoT and eMBB devices. The distance between two APs is d_ ap = 500 m. The path loss model is 35.3+37.6 log_10{d (m)}, where d is the distance between an AP and a device served by it <cit.>. The shadowing is lognormal distributed with 8 dB standard deviation. Half of the devices need D_k^s = 5 slots to process a packet at their local servers, and the other half of the devices need D_k^s = 6 slots. The packet arrival rate of each device, λ_k^ U, is uniformly distributed between 0.05 and 0.1 packets/slot <cit.>.

The required CPU cycles for processing a long packet, c_ L, follows the distribution in (<ref>).  Denote the processing delay of long packets at the mth MEC server as W_m^ L. According to the result in <cit.>, we have

    {W_m^ L > x}∼ p_ A(S_m/c_ S)^-v(1-ρ_m)^-vx^-v,

where f(x)∼ h(x) means that lim_x →∞f(x)/h(x) = 1. In our simulation, v=1.5.
Other parameters are listed in Table <ref>, unless otherwise specified.





 §.§ CCDFs of Processing Delay



The CCDFs of processing delay in the FCFS servers and the PS server at the mth AP are illustrated in Fig. <ref>. In the simulation, 20 devices are served by the AP, where the first 10 of them send short packets and the other 10 send long packets. The average packet rate from each device is λ_k,m = 0.01 packets/slot. The individual and statistical multiplexing servers are illustrated in Fig. <ref>(a) and Fig. <ref>(b), respectively. In the individual server, the service rate of the MEC server is allocated to the devices according to their packet arrival rate, i.e., ∑_k=1^20S_k,m= S_m, λ_k,mc_ S/S_k,m = ρ_m, k=1,...,10, and λ_k,mc̅_ L/S_k,m = ρ_m, k=11,...,20. The simulation results are obtained by generating 10^8 packets and computing their processing delay. The numerical results in Fig. <ref> and Fig. <ref> are obtained from (<ref>) and (<ref>), respectively.

The results in Fig. <ref> indicate that to achieve the same delay bound for long packets, the delay bound violation probability of PS server is much smaller than that of the FCFS servers. The results in Fig. <ref> indicate that the approximation in (<ref>) is very accurate for short packets, and the PS server outperforms the FCFS servers in the short delay regime. Besides, we can see that compared with the statistical multiplexing FCFS server, the individual FCFS server achieves better QoS for short packets by sacrificing the QoS of long packets. However, the PS server can achieve better QoS than the FCFS servers for both long and short packets when the distribution of the number of CPU cycles required to process the packets has a heavy tail.



 §.§ Overall Packet Loss Probabilities



The overall packet loss probabilities achieved by the optimized association scheme, packet offloading rates, and bandwidth allocation are illustrated in Fig. <ref>, where the solution and the minimal overall packet loss probability are obtained with the extended PLB algorithm. As shown in Fig. <ref>, better reliability can be achieved with more antennas or with higher service rate at the MEC servers. To show when communication or computing is the bottleneck of reliability, we consider the case S_m/c_ S = 6. When N_ t≤ 16, increasing the service rate of the MEC servers does not help improving reliability, and hence communication is the bottleneck. When N_ t≥ 18, overall packet loss probability does not decrease with N_ t, and hence computing is the bottleneck. As a result, only when N_ t∈ [16,18], the packet loss in UL and DL transmissions are comparable to the processing delay violation. In the cases that S_m/c_ S > 6, communication is always the bottleneck, because the processing delay violation probability is much smaller than the packet loss due to decoding errors. These results imply that the extended PLB algorithm converges to the optimal solutions in most of the scenarios.

According to 5G NR in <cit.>, the bandwidth of each subcarrier, W_0, and the duration of each slot, T_ s, can be adjusted according to the requirements of services. In Fig. <ref>, we illustrated the impact of W_0 and T_ s on the reliability, where T_ sW_0 is fixed as a constant such that there are 14 symbols transmitted in each slot with one subcarrier. The results in Fig. <ref> indicate that when N_ t is small (i.e., communication is the bottleneck), increasing T_ s is helpful for increasing reliability. The total bandwidth allocated to each device does not exceed coherence bandwidth 1.2 MHz, which does not change with W_0. By increasing T_ s, the maximal blocklength of each packet increases. As a result, the packet loss probability due to decoding errors decreases with T_ s. However, when computing is the bottleneck, increasing T_ s leads to higher overall packet loss probability.


The differences between the association scheme obtained with the extended PLB algorithm and the optimal association schemes ( i.e., ||x^ PLB_k-x_k^ comm|| with the legend “Commun. is the bottleneck" and ||x^ PLB_k-x_k^ comp|| with the legend “Comp. is the bottleneck") are shown in Fig. <ref>. When N_ t=8, communication is the bottleneck and x^ PLB_k and x_k^ comm are the same. When N_ t is large, x^ PLB_k approaches to x_k^ comp. The results in Fig. <ref> are consistent with our analysis in Section V.C that the extended PLB algorithm converges to the optimal solutions in the two asymptotic cases.



The relation between the overall packet loss probability and the density of devices is illustrated in Fig. <ref>. The curves are not smooth, because problem (<ref>) is a mixed integer optimization problem. The results in Fig. <ref> indicate that there is a tradeoff between the overall packet loss probability and the density of devices. When the number of occupied subcarriers is less than the maximal number of subcarriers, i.e., ∑_k=1^K(N_k^ u+N_k^ d) < N_max, the overall packet loss probability increases slowly as K increases. When ∑_k=1^K(N_k^ u+N_k^ d) = N_max, the overall packet loss probability increases extremely fast as K increases. By increasing N_ t and S_m, the density of devices can be improved (i.e., the number of devices with overall packet loss probability less than 10^-7), but the performance gain in Fig. <ref> is only around 25%.























§ CONCLUSION

In this work, we analyzed the processing delay of short packets in the M/G/1/PS server. By introducing an accurate approximation, the CCDF of the processing delay of short packets was derived in closed-form. We then formulated an optimization problem that minimizes the overall packet loss probability under the constraints on ultra-low E2E delay in the MEC system, where the association scheme, packet offloading rates, and bandwidth allocation for MC-IoT services are optimized. The problem is a mixed integer problem and is non-convex. To solve the problem, we proposed a PLB algorithm in the scenario that the data rates of eMBB services are much higher than that of MC-IoT services. We further extended the algorithm into more general scenarios, where we can obtain a near optimal solution with low complexity, i.e., the complexity increases linearly with the number of devices. To analyze the performance of the extended PLB algorithm, we derived the optimal solutions of the problem in two asymptotic cases: communication or computing is the bottleneck of reliability, and proved that the extended PLB algorithm converges to the optimal solution in these two asymptotic cases. Simulation and numerical results validated our analysis and showed that the PS server outperforms FCFS servers.





§ PROOF OF PROPERTY <REF>





Denote f_N(N_k^ξ) = √(T_ sN^ξ_kW_0/V_k^ξ)[ ln( 1 + α_k,mg^ξ_k,mP^ξ_ s/N_0W_0) - b^ξ_kln 2/T_ sN^ξ_kW_0]. The second order derivative of f_N(N_k^ξ) can be derived as follows,

    f”_N(N_k^ξ)=    - 1/4( N_k^ξ)^ - 3/2√(T_sW_0/V_k^ξ)ln( 1 + α _k,mg_k,m^ξ P_s^ξ/N_0W_0) 
       - 3/4( N_k^ξ)^ - 5/2b_k^ξln 2/√(T_sW_0V_k^ξ)  < 0 .

Thus, f_N(N_k^ξ) is concave in N_k^ξ. Moreover, Q function f_ Q(x) is a convex and decreasing function when f_ Q(x) < 0.5, which is the case in MC-IoT. According to <cit.>, the composite function f_ Q(f_N(N_k^ξ)) is convex in N_k^ξ. This completes the proof.




§ PROOF OF PROPOSITION <REF>





We apply the mathematical induction to prove Proposition <ref>.
When i=1, ε^ LB(1)=0 and ε^ UB(1) = ε_ in, we have ε̃^ A∈ (ε^ LB(1), ε^ UB(1)]. We assume that when i=j, ε̃^ A∈ (ε^ LB(j), ε^ UB(j)], and prove ε̃^ A∈ (ε^ LB(j+1), ε^ UB(j+1)].

In the case that ∑_k=1^K[N_k^u(i) + N_k^d(i)] ≤ N_max, ε_ th(i) can be achieved by a solution that lies in the feasible region of problem (<ref>). Thus, ε̃^ A≤ε_ th(i). According to the algorithm in Table <ref>, we have ε^ UB(j+1) = ε_ th(j) and ε^ LB(j+1) = ε^ LB(j). Further considering that ε̃^ A > ε^ LB(j) with the assumption in the case i=j, we have ε̃^ A∈ (ε^ LB(j+1), ε^ UB(j+1)].

In the case that ∑_k=1^K[N_k^u(i) + N_k^d(i)] > N_max, ε_ th(i) cannot be achieved with N_max subcarriers. Thus, ε̃^ A > ε_ th(i). According to the algorithm in Table <ref>, we have ε^ LB(j+1) = ε_ th(j) and ε^ UB(j+1) = ε^ UB(j). Further considering that ε̃^ A≤ε^ UB(j) with the assumption in the case i=j, we have ε̃^ A∈ (ε^ LB(j+1), ε^ UB(j+1)]. The proof ends here.


IEEEtran


