양자 컴퓨팅을 이용한 무선 센서 네트워크에서의 클러스터링 알고리즘 구현

Abstract

Clustering is an effective topology control approach in wireless sensor networks. The majority of the classical clustering algorithm in wireless sensor network requires N steps to select cluster head in an array of N elements. So, CH selection is generally recognized as an NP hard optimization problem which is time consuming and incurs huge computational and data processing times. In this thesis, we design an optimization strategy that emphasizes adjusting the transmission range according to node density and utilizing a quantum search algorithm to reduce the time complexity associated with selecting the cluster head. For designing the new clustering topology, we proposed a new classical algorithm that combines necessary parameters such as number of neighbor node, node to node average distance and residual energy with certain weighting factors chosen according to the network system. This thesis considers a fully connected network with a minimum node degree of 1 (i.e., 1-connectivity) to achieve minimum energy consumption and also considered optimum number of clusters by controlling the transmission power . For comparison, we investigated the existing transmission power control topologies such as EECS and HEED. These methods do not address the optimization of transmission power in the whole connected network. Both EECS and HEED use residual energy as a rudimentary factor, as well as intra-cluster communication cost as a secondary factor. However, EECS and HEED show some drawbacks, increases the network overhead and time complexity. By controlling transmission power, the proposed CH selection mechanism is energy efficient compared to the classical method such as EECS and HEED. Furthermore, the quantum search algorithm used in the method offers a quadratic speedup advantage. It minimizes the time complexity to O (√N) compared to classical search algorithm O(N). In our work, an energy-efficient cluster head selection approach is illustrated through a classical weighted clustering algorithm, and its implementation is also extended through a quantum weighted search algorithm which is demonstrated by the IBM Quantum Qiskit simulation results.