论文部分内容阅读
随着各种技术的发展，人们能随时随地访问和处理网络中的数据，因而数据查询算法的研究已成为一个重点研究问题。然而，Multi-Radio MANET的网络特性给数据查询和收集带来了很多问题，比如增大了数据查询时延和能量消耗等。因此，本文针对Multi-Radio MANET的网络特点，重点研究了基于数据缓存的数据查询问题，其主要研究成果有：1.针对MANET环境中带宽有限、能量有限、存储有限和链路频繁断接性等特点，提出了基于缓存的移动数据查询问题，证明该问题是NP-完全问题，并给出一个多项式时间的算法，即最大节点新覆盖数据算法。该算法采用贪心策略，查询新覆盖数据量最大的节点，减少了查询次数，并最大限度地减少了网络中的传输时延。随后在该算法的基础上，同时考虑了节点新覆盖数据量和链路服务质量问题，提出了一种改进的高效的算法，即基于最大节点传输时延与新覆盖数据比值的数据查询算法，有效地减少了能量消耗，最小化数据传输时延，提高了网络的吞吐量。理论分析及实验结果表明提出的数据查询算法能够充分利用缓存节点的数据信息，较好地完成数据查询工作，有效地减少数据收集时延，提高查询效率。2.针对Multi-Radio MANET中链路服务质量和信道冲突等问题，提出并证明了基于缓存和信道切换的数据查询问题是一个NP-完全问题。根据数据流守恒和链路-信道等约束条件，建立线性规划方程，得到该问题的最优解模型，并提出了一个多项式时间的贪心近似算法。该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延，再贪心选择其具有最小路径时延的缓存节点，收集其新覆盖数据。理论分析和实验结果表明，提出的方案能有效地减少数据收集时延，提高数据查询效率。3.在MANET中采用TOP-K数据查询来获得仅需要的数据是一种有效方法。针对Multi-Radio MANET的网络特点，研究了基于缓存的TOP-K数据查询问题。同时提出了两种处理算法，一种为基于f-邻近缓存节点的TOP-K数据查询算法，另一种为基于f-随机缓存节点的TOP-K数据查询算法。这两种算法有效的权衡了数据查询时延和查询结果准确率这两者，确保了较高的查询结果准确率和较少的数据查询时延。