Research And Application Of Semantic Cache Technology For Mobile Computing Environments

Mobile computing is a combination of computing technology and wirelesscommunication technology. The core objective of mobile computing is shielding wirelesscommunication and mobile environments, then let computers or other smart terminalsachieve resource access and resource share. Now, in mobile computing environment,however, there are many unsolved problems so far, such as weak connection, limited energy,hand-off and limited wireless bandwidth etc. So the methods used in conventional distributedsystems and wired systems are not appropriate in mobile computing systems. The relatedresearch in mobile computing field is becoming the hot spot and focus in current computerscience research.In this thesis, we study semantic cache technology for mobile computing environments,including semantic cache consistency maintenance, organization structure of cache invalidreport, cooperative semantic cache mechanism, mobile agent technology, approximate queryalgorithm during disconnection, KNN query in road networks, etc. We hope to providetheoretical references and technology roadmap for semantic cache by the research of theseproblems.The main contents and contributions of this thesis are summarized as follows:1. Research on semantic cache consistency judge and granularity clipping method.Firstly, the thought of using MSS to store mobile client’s semantic cache backups is proposed.And then the extended semantic cache structure SMC-Architecture, cache organizationstructure in MSS and mobile terminal, as well as the broadcast cache invalidate reportorganization structure are presented. Secondly, we consider three kinds of update operations,the procedure of each update from server is trimmed into tuple level and then the trimmedupdate sequences are stored into queue is discussed in detail. The results of simulationexperiments show that the proposed algorithm can reduce invalidation report size and savedata communication cost effectively.2. A semantic cache maintenance scheme using mobile agent is proposed, which couldadapt to frequent mobility, hand-off network environments. The scheme based on SMC-Architecture, and we design two mobile agents: MSSAg and MTAg, running in MSS tomaintain cache consistency effectively and autonomously. The processing of maintain cacheconsistency using mobile agents is discussed in two cases: without hand-off and withhand-off. In this work we use random walking model to analysis and emulate the behavior ofmobile terminals. We also design the next cell location predict algorithm decision table,which could compute mobile terminal’s future location quickly. The results of simulationexperiments show that the proposed algorithm can reduce invalidation report size and savedata communication cost effectively. And the proposed cache consistency recovery methodkeeps small data communication cost and time cost which adapt to frequent mobility,hand-off and disconnect network environments.3. A new approach to answer queries using cooperative semantic cache mechanism inmobile computing environments is proposed. Firstly, we analyzes and point out that bothcentralized and distributed CoopSC architectures don’t fully fit for mobile computingenvironment and cellular network. And then the cooperative semantic cache architecture ispresented. Secondly, procedure of cooperation is introduced in detail. Before sending aquery to original database server, mobile terminal will connect to MSS and ask for a queryresult cached by other mobile terminals that subsume or overlap the original query. Inadition, we discuss the methods used in cache consistence maintenance, which focus onconfirm receiver of the periodic cache invalidation report and the process of validate client’slocal cache. The results of simulation experiments show that cooperative semantic cachemethod could improve cache hit ratio, reduce network delay time, save bandwidth and shareserver burden in development.4. A simple query processing algorithm SQPID based on semantic cache is proposed,which could reply queries in disconnection. Firstly, related definitions are given, and theprocedure of building integrated related semantic cache item is presented. The main idea ofSQPID is to build the integrated related semantic cache item about current query throughcombine and clip operations. Secondly, theoretic analysis proves that query result exportfrom integrated related semantic cache item is correct, when cache validity is satisfied.Thirdly, analyses the approximate result export procedure in two aspects: completeness queryand incompleteness query. In order to simplify the procedure, SQPID’s combine does not involve indirect relativity estimate, thus speed up the program of extracting query resultsfrom semantic cache during disconnection. Then the pseudo code of SQPID is presented, andthe time complexity is analyzed. The results of simulation experiments show that based onSQPID, query response time and degree of accuracy are better meet client’s requirementsthan QPID.5. A novel mobile continuous KNN query algorithm (CQ-KNN) is proposed, which isapplied in road networks. Firstly, we design a structure to store cell data objects namedGrid-Object to describe road networks graph model, related information saved into vertex list,object list and edge list. Secondly, describe CQ-KNN query algorithm in detail. In order tosupport mobile terminals continuous query, using local cache memory strategy andfurthermore, cache consistent maintain procedure based server broadcast invalid locationreport is given. The results of simulation experiments show that KNN and CQ-KNNalgorithms can reduce CPU time and network response delay, also can support approximateK nearest neighbor query when the terminal off-line a period of time.