K-CLOSE: algorithm for finding the close regions in wireless sensor networks based uncertain graph mining technology

Due to the instability of wireless links and the complexity of geographical environment where wireless sensor networks are deployed, sensor nodes can not guarantee communication with their neighboring nodes with high probabilities. Resolving the problem of finding the sensor nodes that communicate well in practical settings can play an important role in node clustering and the optimization of routing protocols. It is important to note the discovery which nodes in a region are more close to each other in actual movement. A new algorithm called K-CLOSE is proposed in this paper to solve the problem which finding the most k close regions. First, K-CLOSE abstracts wireless sensor networks into uncertain graphs in a distributed manner. Then, the closeness threshold is determined by an approximation algorithm proposed in this paper, which has approximate rate 2. Finally, the k close regions where sensor nodes communicate with high probabilities are discovered using tree searching and branch-and-bound methods. Moreover, the experimental results show that the proposed algorithm is efficient in practice.