Computation Partitioning For Stateful Data Stream Application In Edge Computing

The popularization of mobile devices and development of edge computing enable many new computing-intensive and latency-sensitive mobile applications such as augmented reality,object tracking and so on.In the context of edge computing,compared with traditional cloud computing,edge computing has the advantages of low latency,high reliability,and strong scalability.Computation partitioning improves the performance of applications by offloading complex computation from mobile device to nearby edge cloud resources.Existing works consider the computation partitioning research of stateless applications in edge cloud environments.While in a dynamic environment in which the network bandwidth to the edge cloud may change frequently,the computation partitioning decision needs to be updated accordingly.The frequent updating of partitioning leads to high state migration cost between the mobile side and the edge cloud server,which may cause significant network congestion and increase overall completion time tremendously.Therefore,this thesis will firstly study the computation partitioning problem of stateful data stream applications,which aims to effectively partition stateful data stream application in dynamic edge cloud environments to minimize the total completion time(make-span).Considering that the edge cloud server has the possibility of downtime during the execution process,and the data stream also has the possibility of transmission failure during the transmission process,this thesis further study the computation partitioning problem of stateful data stream applications with reliability constraint,which aims to minimize the make-span while ensuring the reliability requirement.Above all,the main research works of this thesis are as follows:(1)This thesis firstly define the computation partitioning problem of stateful data stream application,which aims to minimize the total completion time through considering the state migration cost,selectively adjusting modules and migrating state.(2)A heuristic algorithm,namely Score Matrix-based Heuristic(SM-H)algorithm,is proposed to solve the one-shot problem.The experimental results show that SM-H algorithm can obtain a smaller total completion time than traditional List Scheduling,Sequential Adjustment,and Genetic Algorithm.We propose a Repeated Score Matrix-based Heuristic(RSM-H)algorithm to solve multi-step look ahead online problem.Through extensive experimental evaluations,we found that the performance of RSM-H is better than benchmark methods.(3)This thesis proposes the computation partitioning problem.We adopt the strategies of module redundancy(MR)and cross edge retransmission(CR)to meet the reliability requirement,and establish a complete calculation model.We propose the RL-based computation partitioning algorithm and solutions to the offline problem and the online problem,which could minimize the total completion time while satisfying the reliability requirement.