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