## 3 Problem Statement  
Previous works for task offloading focus on whether to offload corresponding tasks to a cloud server in order to optimize a certain parameter. They regard the cloud resource as a whole and make decisions for task offloading according to resource availability, energy consumption etc. They do not consider improving the utilization rate of cloud resource, which may lead to a waste of cloud resources. A dedicated cloud resource manager is in charge of optimal resource allocation following its optimization objects, such as saving energy, decreasing the waste of computing resource etc. It does not consider the impact on mobile devices in mobile cloud computing environment. In our paper, we intend to improve the utilization rate of cloud resource and reduce the latency when the cloud resource is applied to augment mobile devices, which is seldom considered by other studies on the issue of task offloading. Moreover, the selection of physical machines that an offloaded task runs in can affect the delay of offloaded tasks. Therefore, it is necessary to make sure a high utilization rate of PM and a low delay for offloaded tasks when offloading tasks to the cloud. We will mainly study the tradeoff between the optimal utilization of cloud resource and the delay for offloaded tasks in our paper. We consider the real cloud environment where all tasks run on the virtual machines and a physical machine could deploy several virtual machines. The proximity cloud may reduce data transmission time between the mobile device and cloud. In our paper, we consider the bandwidth between mobile devices and the PMs. As shown in Figure 1, \(PM_{i}\) represents the \(i\)th physical machine (PM) in cloud center that is used to run VMs. We can see that the number of VMs running in each PM are different. The \(PM_{4}\) is not in a running state that there are no VMs running in. The bandwidth between mobile devices and the \(i\)th PM is denoted as \(BW_{i}\) correspondingly. Suppose that the number of current running PMs is \(N_{CP}\) and the max number of VMs that \(N_{CP}\) PMs could run is \(N_{TV}\). The number of current running VMs on these \(N_{CP}\) PMs is \(N_{CV}\) and the max number of VMs each PM can run is \(N_{V}\). We defined utilization rate of PM as follow  
\[UR=N_{CV}/N_{TV}*100\% \tag{1}\]  
\[N_{TV}=N_{V}*N_{CP} \tag{2}\]  
We can see that proposed algorithm should decrease the \(N_{CP}\) and increase the \(N_{CV}\) in order to get larger \(UR\) when offloading tasks to cloud server. Therefore, offloaded tasks should be assigned to those PMs that have run VMs preferentially than being assigned to a new PM. However, it may lead to a higher delay than offloading tasks to a new PM. We define the delay caused by an offloading task as follow:  
\[TD=T_{c}+T_{W}+S/BW \tag{3}\]  
where \(T_{c}\) is the execution time of offloaded tasks in cloud server, and \(S\) is the amount of data to be transferred between the mobile device and the cloud server. \(T_{W}\) is the waiting time when an offloaded task is assigned to the VM that existing another task is running in. As shown in Figure 2, the Task1 is running on \(VM_{1}\) in the time among 0 and \(t_{1}\), and only one VM is running in current PM during that period time. The \(T_{c}\) of Task1 is \(t_{1}\). If an offloaded task Task2 arrives at \(t_{0}\), then there are two  
Figure 1: Allocation of physical machine. ways to choose for running the offloaded task Task2. One way is that the Task2 is assigned to \(VM_{1}\), it will be executed at \(t_{1}\) when the Task1 is completed. Therefore the waiting time caused by this way is \(T_{W}=t_{1}-t_{0}\). Another way is that the Task2 is offloaded to a new running VM \(VM_{2}\) that no task is running on. The Task2 can be executed in \(VM_{2}\) at \(t_{0}\) and there is no need to wait, \(T_{W}=0\). Moreover, the VMs from different PMs are in different running states, which could lead to different waiting time for offloaded tasks. Meanwhile, the bandwidths between mobile devices and the PMs are also different.