Pengolahan Isyarat pada Graf

Ayu Oktaviani Dewi, Dr. Dyonisius Dony Ariananda, S.T., M.Sc.; Ir. Sigit Basuki Wibowo, S.T., M.Eng., Ph.D., IPM.

2024 | Skripsi | TEKNIK ELEKTRO

Isyarat yang dievaluasi dalam pengolahan isyarat klasik umumnya merupakan isyarat satu dimensi, seperti isyarat yang merupakan fungsi waktu. Sementara itu, isyarat-isyarat yang ditemui di dunia nyata seringkali merupakan isyarat multi-dimensi atau isyarat yang berada pada suatu struktur yang kompleks dan tidak teratur. Struktur yang kompleks dan tidak teratur ini dapat dimodelkan sebagai graf, yang terdiri atas simpul-simpul (node) dan link-link (edges) yang menghubungkan simpul-simpul tersebut. Untuk isyarat-isyarat yang berada pada struktur graf, analisis dalam domain waktu seringkali tidak memadai karena struktur graf cenderung kompleks dan tidak teratur. Oleh karena itu, perlu mekanisme tersendiri dalam mengolah isyarat graf. Pertanyaan yang perlu dijawab adalah bagaimana mengembangkan mekanisme pengolahan isyarat graf (graph signal processing (GSP)) dari teori-teori pengolahan isyarat klasik yang sudah ada.

Salah satu tujuan penelitian ini adalah memahami konsep frekuensi tinggi dan frekuensi rendah dalam isyarat pada graf. Tujuan ini dapat dicapai melalui proses perhitungan variansi total (total variation (TV)) pada isyarat-isyarat graf. Akan tetapi, perhitungan TV ini tidak menjabarkan secara mendetail besar kontribusi dari komponen frekuensi yang berbeda-beda. Untuk mengatasi permasalahan tersebut, proses dekomposisi isyarat graf dengan menggunakan graph Fourier transform (GFT) dapat dilakukan. Proses dekomposisi tersebut pada dasarnya melibatkan eigenvector-eigenvector matriks penyusun graf yang diperoleh dengan melakukan proses dekomposisi eigenvalue pada matriks penyusun graf. Eigenvector-eigenvector ini berperan sebagai fungsi basis bagi seluruh isyarat graf. Proses GFT sendiri dilakukan dengan mengalikan inverse dari matriks eigenvector dari matriks penyusun graf dan isyarat graf. Pemahaman akan konsep-konsep tersebut di atas menjadi basis penelitian ini untuk mengevaluasi implementasi GSP dalam aplikasi penginderaan spektrum pada jaringan radio kognitif (cognitive radio (CR)). Dalam aplikasi penginderaan spektrum di atas, GSP dapat digunakan untuk mendeteksi adanya anomali pada hasil penginderaan spektrum. Anomali ini bisa disebabkan oleh perbedaan statistik fading pada lokasi yang berbeda dan keberadaan serangan Byzantine. 

 Hasil penelitian menunjukkan bahwa nilai TV tertinggi dicapai saat jumlah zero crossing pada isyarat graf maksimal. Proses evaluasi GFT pada isyarat graf melibatkan matriks eigenvector dari matriks random-walk Laplacian dari graf yang akan dievaluasi. Saat isyarat pada seluruh node bernilai sama, hasil GFT akan memiliki nilai tertinggi pada elemen dengan indeks yang bersesuaian dengan indeks kolom eigenvector yang berperan sebagai basis komponen frekuensi rendah. Sebaliknya, saat isyarat graf memiliki tingkat fluktuasi yang paling tinggi (jumlah zero crossing yang terbanyak), hasil GFT akan memiliki nilai tertinggi pada elemen dengan indeks yang bersesuaian dengan indeks kolom eigenvector yang berperan sebagai basis komponen frekuensi tinggi. Dalam aplikasi penginderaan spektrum pada jaringan CR, kemampuan GSP yang cukup baik dalam mendeteksi keberadaan anomali statistik fading diperoleh saat daya derau kecil dan jumlah sampel yang diproses banyak. Sementara itu, kemampuan GSP yang cukup baik dalam mendeteksi keberadaan serangan Byzantine diperoleh saat dampak fading minimal dan pelaku serangan Byzantine senantiasa melakukan falsifikasi terhadap informasi hasil penginderaan spektrum.

The signals evaluated in classical signal processing are generally one-dimensional signals, such as time-domain signals. In reality, however, most of signals are often multi-dimensional and they could be located on a complex and irregular structure. These complex and irregular structures can be modeled as graphs, consisting of nodes and links (edges) that connect these nodes. Due to these complex and irregular structures, signal processing tools for time-domain signals cannot be directly applied on signals located on the graph (labeled as graph signals). Of particular interest is how to develop a graph signal processing (GSP) tools from the existing classical signal processing theories. 

One of the purposes of this research is to understand the concepts of high frequency and low frequency in signals on graphs. This goal can be achieved by evaluating total variance (TV) of the graph signals. However, TV does not provide detailed information about the contribution of different frequency components in graph signals. To solve this issue, the decomposition of graph signals using the graph Fourier transform (GFT) into some basis functions can be performed. The decomposition process basically involves the eigenvectors of some common matrix representations for graph, obtained by performing the eigenvalue decomposition on these matrix representations. These eigenvectors play a role as the basis function for the entire graph signals. The GFT process performed by applying the inverse of the eigenvector matrix of the matrix representations on the graph signals. The aforementioned concepts forms basis of this research to evaluate the implementation of GSP in spectrum sensing application for cognitive radio (CR) networks. In this application, GSP can be used to detect anomalies in the spectrum sensing result. These anomalies can be caused by differences in fading statistic at different locations and the existence of Byzantine attacks.

The results of the aforementioned investigation show that the highest value of TV is achieved when the number of zero crossings in the graph signal is at its maximum. The GFT evaluation process on the graph signals involves the eigenvector matrix of the random-walk Laplacian matrix of the examined graph. When the signals on all nodes are equal, the GFT result will have the highest value on the element with an index corresponding to the index of the eigenvector column that play a role as the basis of the low-frequency component. Meanwhile, when a graph signal has the highest rate of fluctuation (the highest number of zero crossings), the GFT result will have the highest value on an element with an index associated with the index of the eigenvector column that serves as the basis of the high-frequency component. In the experiments related to spectrum sensing for CR networks, a good performance in the detection of fading statistics anomalies using GSP is obtained for a sufficiently small noise power and a sufficiently large number of processed samples. In addition, a good performance in the detection of Byzantine attacks using GSP is acquired when the impact of fading is minimal and the perpetrator of the Byzantine attack continuously falsifies the spectrum sensing information. 

Kata Kunci : graph signal processing, graph Fourier transform, isyarat graf, variansi total, penginderaan spektrum