Study On Multi-Radio MANET Data Caching And Data Query Processing Algorithms

With the development of various technologies, people can access and process dataanywhere in the network, so the research of data query algorithms has become a keyresearch question. However, the network characteristics of Multi-Radio MANET bring alot of problems when we query and collect datas, such as increasing data query latencyand energy consumption. Therefore, this paper focuses on researching the problem ofdata query based on data caching. The main contributions of this thesis are as follows:1. Aiming at the nature of mobile ad-hoc networks, such as self-organization,limited communication bandwidth, multi-hop communication, limited energy, limitedstorage and the frequent disconnection of the links, etc., it formulates a problem ofmobile data query based on caching, and it is proved to be a NP-complete problem.Then a polynomial algorithm is given to solve the problem. This algorithm uses greedystrategy to query cache nodes which store the largest amount of new data packets, sothat reduce the number of query and minimize the network transmission delay.According to this algorithm for mobile data query, it proposes another algorithm basedon the max ratio of new data packets and unit communicate delay of cache nodes, whichnot only takes the number of new data packets into account, but also considers thequality-of-service of the links. This algorithm can improve the efficiency of query,minimize network data transmission delay, reduce energy consumption and improvenetwork throughput. Theoretical analysis and experimental results indicate that theproposed algorithms can make full use of the data of cache nodes, complete data querybetter, reduce data transmission delay, as well as improve the efficiency of queryefficiently.2. Due to the nature of multi-Radio multi-channel MANET networks, such as thequality-of-service of the links, channel confliction etc., we investigated a problem ofdata query based on data cache and channel switch, and proved it to be an NP-completeproblem. Firstly, we constructed a LP equation based on the data flow conservation andlink-channel constraint etc. to formulate the problem, then designed a polynomialapproximate algorithm. The algorithm used dynamic programming strategy to minimize the delay of unit data packet transmission from cache nodes to the query node, greedilychose a cache node with the smallest delay of unit data packet transmission, andcollected the new covered data packets. Theoretical analyzes and experimental resultsindicate that the proposed algorithm can reduce the communicate delay and improve theefficiency of query efficiently.3. In MANETs, to acquire only necessary data items, it is effsctive that each noderetriseves data items using a top-k query. Aiming at network features for Multi-RadioMANET, we study the top-k data query based on cache. Meanwhile we propose twoprocessing algorithms, one is a top-k query algorithm based on f-near cache nodes, andthe other one is a top-k query algorithm based on f-random cache nodes. Bothalgorithms effectively weigh the data query latency and accuracy of query results andensure higher accuracy of query results and less data query latency.