A distributed sensing algorithm is proposed which considers the nodes’ contention relation and the sensing cost. The algorithm is based on the distributed minimum clique partition, which can classify nodes into several cliques. Then, the optimal spectrum sensing scheme for each node is calculated on the foundation of cliques. The computation complexity is O(N²+M×N), N is the node number of the network, and M is the number of channels. By a detailed simulation, the results demonstrate that the network performance is improved efficiently with the use of the algorithm.