Abstract: Owing to the better security, dynamic and extensibility, Exclusion Basis Systems (EBS) based key management applies to security of heterogeneous sensor networks, but it suffers from the collusion. This paper introduces a Minimum Spanning Tree (MST) based optimization scheme of key collusion restraining, which uses Prim algorithm to create MST from undirected graph constituted by nodes in cluster. Traversing the tree gets a sequence of nodes. The sequence is used to design and distribute keys in the scheme. It improves the repeated degrees of keys in adjacent nodes and reduces the possibility of key collusion. The experimental results show that the optimization scheme effectively improves the resistant of networks capture, comparing with SHELL and random distribution method.