无线移动网络中基于数据访问分布的合作缓存研究

With the rapid development of mobile internet and cloud computing, mobile users can access the Internet by a wireless multi-hop network. However, due to the limited bandwidth of wireless network and the small storage on mobile devices, it is not possible for a lot of mobile users to access data simultaneously. Moreover, the frequently disconnection of a wireless network also results in network partitions so that part of the data cannot be accessed by mobile users. These problems can be dealt with by cooperative caching. A typical strategy in cooperative caching works as follows. Data sources transfer some data copies to some nodes called cache nodes. Other nodes may access data items from the cache nodes nearby, instead of data sources. Consequently, total access cost can be reduced because of the service provided by these cache nodes. However, due to the limited cache space, not all the data items can be cached locally. It is required to consider what data items should be selected at which mobile node to minimize total access cost. The cache placement problem is the key problem in cooperative caching and its complexity is proved NP-hard. It is referred to as to let each mobile node select a subset of data items to cache cooperatively in its limited cache so that total access cost is minimized. In this project, we consider the shared media of wireless communication in practice and the data access distribution for the new requirements in mobile internet. We consider the tradeoff between the selfishness and the altruism of mobile nodes with respect to their limited cache storage. We propose to divide the cache space of each node into two components: altruistic and selfish. We also consider the inherent relations among data items and provide new metrics for new applications in mobile internet, such as video sharing among mobile users. We believe the breakthrough of these key technologies can improve the performance of data access dramatically in mobile wireless networks, and provide important support for the services in cloud computing in the future.

随着移动互联网和云计算的兴起，移动用户通过无线多跳网络可以随时随地的访问Internet。但是，无线网络在带宽和移动设备在存储空间等方面的资源有限，无法满足大量用户同时访问数据的需求，也不可能在本地缓存大量的数据。移动用户的移动性也会导致无线链接的经常性断开，网络分裂后部分数据无法访问。这些问题都可以通过合作缓存的技术得到解决，利用移动结点之间的合作将数据分散的放置在缓存结点上，在有限的存储空间上实现数据访问总开销的最小化（即缓存放置问题，NP-hard难度）。本项目考虑到无线通信共享介质的特点，从实用性角度考虑了无线信道竞争对于缓存放置问题的影响，同时从新颖性的角度考虑了移动结点的自私性和利他性，通过对数据访问分布和数据内在关系的分析，将提出合理分配缓存空间以达到数据访问总开销的最小化。本项目关键技术的突破，将会带来移动互联网中用户访问数据质的提升，为云服务的普及提供关键技术支撑。

本项目围绕无线移动网络中合作缓存的关键问题——缓存放置问题，在三年期间从两个层次上开展了科学研究。.首先，在无线移动网络的无线通信MAC层上，研究了无线信道竞争对合作缓存的缓存放置问题带来的影响，通过分析每跳延迟数学建模并以此建立每跳延迟和总体数据访问开销之间的数学关系，然后通过分析缓存结点和缓存内部数据选择对数据传输流量的影响，建立在有限缓存空间的限制下最小化总体数据访问开销的目标函数，提出了基于对冲数据流的缓存放置策略，把增加的数据流和减少的数据流视为影响缓存开销的关键因素，在访问数据流、应答数据流和更新数据流之间建立了对冲数据流的平衡原则，通过数学分析和仿真实验，和目前最好的算法相比较，新算法可以减少平均数据访问延迟50%以上，同时减少缓存系统消息开销20%以上，取得了较好的成果。.其次，在无线移动网络的应用层，课题组分别从两点研究数据访问和缓存放置问题之间的关系。第一，在用户访问数据的规律方面，研究了基于Zipf-like分布的文本数据和基于SE分布的媒体数据访问规律，定义了平均访问跳数，作为合理评估无线移动自组网中移动节点访问数据的开销的标准，以解决无线移动自组网中网络拓扑多变的问题。提出分治的方法将每个移动节点的缓存空间划分为两个部分，第一个部分为自私性空间，主要缓存该节点自身访问量较高的数据，第二个部分是利他性空间，主要用来缓存其他节点感兴趣的数据。评估平均访问跳数首次引入了随机二部图的理论分析方法，通过将移动节点集合和数据集合作为随机二部图的两个部分，建立了移动节点和数据之间的访问关系图，从而可以减少移动网络拓扑变化对于访问关系的影响，新的算法和目前已发表的论文中最好的结果对比，可以缩短平均数据访问延迟10%左右，减少通讯消息开销20%左右。第二，在数据内在关系上，课题组研究了数据内在的时间和空间关系对合作缓存带来的影响，在流媒体方面，数据块之间本身就存在时间上的连续性，随着越来越多的视频文件的出现，课题组提出了基于闲聊的合作缓存方法，通过用户访问数据的次序来分析数据缓存之间的关系，从而提高数据访问的性能到一个新的数量级。.本项目在国内外期刊发表学术论文6篇，其中国际期刊发表论文3篇（JCR1区1篇和JCR2区2篇），国际会议论文3篇，申请专利7项，获得授权1项；基于合作缓存算法实现了一个基于海量小文件访问服务器软件，获得软件著作权1项。