Coded grouping-based inspection algorithms to detect malicious meters in neighborhood area smart grid

When modern hardware and software technologies are integrated into smart grid, numerous vulnerabilities are introduced at the same time. The vulnerabilities are now leveraged by malicious users for the purpose of electricity theft. Many approaches are proposed to identify malicious users. However, some of them have low detection rates; the others suffer from either low inspection speed or huge cost of deploying monitoring devices. In this paper, to accurately locate malicious users stealing electricity in a fast and economic way, we propose three novel inspection algorithms. First, Binary-Coded Grouping-based Inspection (BCGI) algorithm is proposed. Under some assumptions, it can locate malicious users with only one inspection step. Given n users, the BCGI algorithm requires Θ(log2(n)) inspectors. Unfortunately, in some cases we do not have enough inspectors for the BCGI algorithm to work. To deal with these cases, we further propose two algorithms: M-ary Coded Grouping-based Inspection (MCGI) and Generalized BCGI (G-BCGI). In the MCGI algorithm, users' identification (ID) numbers are encoded into (l+1)-nary notations, where l is adaptively determined by the number of users and the number of available inspectors. It can locate malicious users within l inspection steps. In G-BCGI algorithm, users' IDs are encoded into binary notations, similar to the BCGI algorithm, and multiple rounds may be needed to locate malicious users. Experiment results show that the proposed algorithms can locate malicious users accurately and efficiently.