【摘要】 考虑在总资源量和节点容量的限制下,如何为任务找到一棵最小代价汇聚树。该问题是一个NP难问题,分别提出问题的线性整数规划模型和启发式算法GCAT。仿真结果显示,相比于其他的启发式算法,GCAT算法生成的汇聚树代价更小,同时有更高的资源利用率,小规模网络下性能接近于最优解。更多还原

【Abstract】 In-network computation can greatly reduce the traffic generated during many-to-one transmission by establishing aggregation trees to merge data streams at the aggregation nodes. In this paper, we consider finding the minimum-cost aggregation tree under the constraints of a given amount of resources and the capacity of switch nodes. Since this problem is an NP-hard problem, a linear integer programming model and a heuristic algorithm called greedy cost aggregation tree(GCAT) are given to solve it. Simulation results show that the GCAT algorithm can generate a tree with less cost and utilize the resource more efficiently than other heuristics, and the performance is close to the optimal solution for small-scale networks.更多还原