A Spectral Clustering Approach to Identifying Cuts in Wireless Sensor Networks

Wireless sensor networks (WSNs) often suffer from the disrupted connectivity due to unpredictable wireless channels, early depletion of node energy, and physical tampering by hostile users. The existence of a disconnected segment of the network referred to as network cut, leads to data loss, wasted power consumption, and congestion in the WSN. However, existing approaches to network cut detection in the WSN rely on the assumption that a node or a link either works normally or fails, without considering the uncertain and random features of wireless links in the WSN. In this paper, we extend the notion of the network cut based on the realistic wireless channel model. Furthermore, we formulate the problem of minimizing the normalized cut (Ncut) with critical nodes, considering the quality of wireless links, degree weights, and different priorities of sensor nodes. Then, we propose a network cut identification algorithm and dominant eigenvector computation algorithm that efficiently identify multiple network cuts by computing multiple eigenvalues and eigenvectors according to a given parameter of eigenvalue gap. Extensive simulations are conducted to examine the effectiveness and robustness of the proposed approach. The results show that the proposed method strikes a balance between minimizing the Ncut objective and the degree of disconnection of critical nodes and achieves a better performance than existing algorithms.