# Influence of Crowd Participation Features on Mobile Edge Computing
## 2 Opportunistic Caching
### Cache Size: How Big Is the Buffer Space? Since the connection between nodes in MEC cannot be guaranteed, the edge nodes must store part of the content in advance and cache some copies of the content temporarily in the buffer space. A fundamental question hence arises: how much buffer space should each node reserve? We think that an upper bound exists for the node buffer size, which is the smallest value that can guarantee the desired performance such as the caching hit ratio and transmission delay. In our study, the transmission process and the intermittently connected links are modeled by an edge-Markovian dynamic graph [16], and we analyze the buffer limitation from the percolation theory perspective. The inter-contact time  
Figure 1: Illustration of mobile edge computing (MEC). series reproduced by this model show a similar power law and exponential tail distribution as those observed in many real data traces. In the model, each edge has two states: active and inactive, which are distributed with an arbitrary initial probability. Based on a two-state Markovian process, one edge changes its state with an active probability \(p\) and an inactive one \(q\) between two sequent slots. Specifically, if an edge is active at slot \(t\), it switches to the inactive state at slot \(t+1\) with a probability \(q\). On the other hand, if it is inactive at slot \(t\), it becomes active at the next slot with a probability \(p\). Based on the percolation theory, there is a special state for the network, called the supercritical case, in which there exists a connected giant group at any moment when the density of nodes goes to infinity. The precondition for the supercritical case is \(p>p_{c}\) (i.e., in an ultra-dense environment such as the cell networks we discussed), where \(p_{c}=c\frac{\log n}{n}\), \(n\) is the number of nodes and \(c\) is a constant. We find that, in the supercritical case, there exits an upper bound on the node's buffer size, which is independent of the inactive probability \(q\)[17]. Upper Bound Analysis  
In the supercritical case, depending on whether the nodes belong to the giant cluster or not, they can be classified into two types: connected nodes and disconnected nodes. The former belongs to the giant cluster, while the latter does not. The connected nodes constitute a connected group, where packets are forwarded fast. On the contrary, buffer sizes of disconnected nodes are larger than those of the connected nodes, because packets in the disconnected nodes need to wait a longer time until the edges turn active. The worst case is that both the source node \(s\) and destination node \(d\) are separated by the giant cluster. This leads to the maximum time and buffer space being required to store the packets, as shown in Figure 3. There are three phases in the transmission process in this case: the source flooding phase, the shortest path phase and the destination flooding phase [18]. (1) Source flooding phase: In general, the flooding strategy has the lowest transmission delay and highest packet delivery ratio; at the same time, it results in the largest buffer space, which is necessary for this paper, since we focus on the fundamental bounds on node buffer size, especially in the worst case. In the flooding scheme, if both the source \(s\) and its neighbors belong to disconnected nodes, packets must be flooded to each other when the link between them is active. That is, if there is a packet  
Figure 2: System architecture. MBS, macro base station; SBS, small base station; UT, user terminal; RUT, requesting user terminal; D2D, device-to-device. at node \(u\) at time slot \(t-1\), node \(u\) will send the packet to all its neighbors at time slot \(t\). We use an infectious-disease-diffusion algorithm to characterize the flooding process [19] and classify nodes into a susceptible state and an infected state. A node is called infected if it carries a packet; otherwise, we call it susceptible.