任意网络中的可分数据处理研究

项目名称： 任意网络中的可分数据处理研究

项目编号： No.61502403

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 张哲民

作者单位： 厦门大学

项目金额： 20万元

中文摘要： 在传统用于分析可分数据处理的等效节点法中，为了建立求解数据分配方式所需的线性方程，网络中的节点最多只能从一个邻居节点接收数据。这极大的降低了网络链路资源的利用率，从而导致了数据传送时间长，数据处理速度的提升受到了限制。为了提高网络链路资源的利用率以进一步提升数据处理速度，我们拟在三个方面展开研究工作：1）在允许节点从多个邻居节点接收数据的情况下，为任意给定网络中的可分数据处理优化建立模型；2）运用新的分析方法找到所建模型的最优解；3）在最优算法的基础上设计低时间复杂度且性能优异的经验算法。项目解除了等效节点法中对节点接收数据的限制，进而为可分数据处理速度的进一步提升奠定了基础。为了对新建模型进行求解，我们提出了一整套的分析方法，不仅找到了模型的最优解，还为设计有效的经验算法提供了思路。本项目的研究具有重要的理论创新和广泛的应用前景。

中文关键词： 可分数据；并行与分布式处理；最大完成时间最小化问题；任意网络；线性规划

英文摘要： In order to establish the linear equations, which are required to calculate the divisible load distribution pattern, the traditional equivalent processing node method restricts that any node in the network can receive load from no more than one of its neighbors. Such restriction drastically lowers the utilization of network link resource, which leads to long load transmission time, and limits the further improvement of load processing speedup. We plan to conduct our research in the following 3 aspects, such that the load processing speedup can be further increased by better utilizing the network link resource: 1) we allow node receive load from multiple neighbors, and establish new optimization model for divisible load scheduling in an arbitrary network; 2) we apply a novel analysis method to solve the optimization model; 3) we propose a heuristic algorithm with low time complexity but good performance. The project eliminates the restriction in the equivalent processing node method, therefore, further improvement of load processing speedup becomes possible. We develop a set of analysis method to find out the optimal solution of the new model, and provide the idea of designing an effective heuristic algorithm. Hence, the project is of great novelty and wide applicability.

英文关键词： Divisible load;Parallel and distributed processing;MFTM problem;Arbitrary network;Linear programming