【摘要】 精确性是网络测量的一个关键问题 .一个测量节点对测量任务的并发执行通常会影响测量结果的精确性 ,测量任务的互斥执行可以降低或消除这种影响 .同时 ,单向测量需要两个节点协作进行 ,因此随机产生的测量任务可能会产生冲突 ,从而导致进程死锁、测量效率低下等一系列问题 .我们称该类问题为测量协同问题 (MCP) .MCP是一类特殊的分布式资源分配问题 ,它的特殊性主要在于 :(1)资源之间协商该被哪个进程 (任务 )使用 ;(2 )如果任务的资源需求得不到满足 ,则该任务将被放弃执行 .作者提出了测量协同问题完全分布式的算法———CDA ,证明了CDA的存活性和正确性 ,并分析了消息复杂度、空间复杂度和收敛时间 .模拟实验表明 ,CDA具有良好的处理冲突任务的能力 ,使得CDA在任务并发性较强时仍然具有较好的任务执行能力 .更多还原

【Abstract】 Measurement Collaboration Problem (MCP) is a kind of distributed collaboration problem with tasks having confliction, which is a class of particular resource distribution problem. Its particularity lies in that: (1)resources negotiate about which process (or task) should be triggered; (2)if the resource demand of a task can’t be satisfied, the task should be given up. After having studied the arbitrator-based solution, authors present a Completely Distributed Algorithm (CDA) in this paper. They also prove the aliveness and correctness of CDA, and finally analyze the message complexity, space complexity and convergence time. Compared with the arbitrator-based algorithm, CDA can be used in the system with larger scale. To validate the efficiency of CDA, authors put forward Single Wait State Algorithm (SWSA) and a simulation experiment. The experiment indicates that, in the course of a large scale of measurement, when the concurrent number of measurement tasks created randomly is small, CDA has no better efficiency than SWSA. But with the increase of concurrent number, CDA gradually has higher efficiency. It also shows that CDA has much better ability of dealing with conflict tasks than SWSA. With the portion of conflicted tasks increasing, the efficiency of CDA even slightly increases. CDA can also be utilized in many aspects, such as disaster rescue, distributed agent collaboration, object position and so on.更多还原