NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCAN PADA ESTIMASI ARAH KEDATANGAN SINYAL BERBASIS REKONSTRUKSI SPARSE
LAPORAN KEMAJUAN 2
Oleh
KOREDIANTO USMAN NIM: 33213002 (Program Studi Teknik Elektro dan Informatika)
INSTITUT TEKNOLOGI BANDUNG Mei 2015
NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCAN PADA ESTIMASI ARAH KEDATANGAN SINYAL BERBASIS REKONSTRUKSI SPARSE
Oleh Koredianto Usman NIM: 33213002 (Program Studi Teknik Elektro dan Informatika) Institut Teknologi Bandung
Menyetujui Tim Pembimbing Tanggal : 21 Mei 2015
Ketua,
(Prof. Andriyan Bayu Suksmono, Ph.D)
Anggota,
(Prof. Hendra Gunawan, Ph.D)
i
ABSTRAK
Setelah berhasil diterapkan pada berbagai bidang, saat ini aplikasi dari Compressive Sensing (CS) ini juga digunakan untuk estimasi arah kedatangan sinyal. Estimasi arah kedatangan sinyal adalah teknik estimasi sudut kedatangan objek yang dideteksi dengan peralatan radar atau sonar. Teknik klasik untuk estimasi arah kedatangan antara lain adalah MVDR, MUSIC, dan ESPRIT. Peran dari CS adalah pengurangan jumlah sampel akuisisi pada sisi penerima. Pengurangan ini memberi dampak pada kecilnya data rate, sehingga dimungkinkan membangun sistem radar terdistribusi untuk memantau daerah yang luas. Teknik terkini dalam estimasi arah kedatangan sinyal dengan compressive sensing adalah dengan metoda sparsitas sudut. Teknik ini mengasumsikan sinyal datang berasal dari beberapa sumber berbeda yang berjumlah terbatas. Teknik yang telah dikembangkan peneliti untuk skema ini adalah dengan menggunakan sensing matrix A yang tersusun atas steering vector yang berasal dari semua sudut yang dipindai (-900 sampai 900 ). Teknik pindai pada semua sudut ini disebut sebagai exhaustive search. Teknik exhaustive search ini memiliki permasalahan pada besarnya matrik sensing A, sehingga proses rekonstruksi CS menjadi berat. Kemungkinan pemindaian pada rentang sudut yang lebih kecil (non-exhaustive search), yaitu pada sudut-sudut yang diduga mengandung sumber sinyal diusulkan pada penelitian ini. Pengujian yang dilakukan pada penelitian ini menunjukkan bahwa teknik ini memiliki tingkat keberhasilan yang baik. Masih terdapat masalah tambahan yang harus diselesaikan pada teknik non-exhaustive search yaitu rekonstruksi CS tidak konvergen jika rentang sudut pindai terlalu sempit. Penambahan pemindaian di luar area pemindaian utama (tail-scan) untuk mengatasi masalah ini juga dilakukan pada laporan ini. Landasan matematis untuk teknik tail-scan ini direncanakan pada tahap kemajuan berikutnya. Kata kunci : compressive sensing, estimasi arah kedatangan sinyal, sparsitas, exhaustive search, non-exhaustive search, tail scan.
ii
DAFTAR ISI ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BAB I Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 State of The Art . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3 Premis dan Hipotesis . . . . . . . . . . . . . . . . . . . . . . . . BAB II Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II.1 Model matematis sistem . . . . . . . . . . . . . . . . . . . . . . . II.2 Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . . . . II.3 Compressive sensing pada estimasi DoA . . . . . . . . . . . . . . BAB III Metode yang diusulkan . . . . . . . . . . . . . . . . . . . . . . . . . . III.1 Exhaustive Search . . . . . . . . . . . . . . . . . . . . . . . . . . III.2 Non-exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . III.3 Tail scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.4 CS solver dengan CVX Programming . . . . . . . . . . . . . . . BAB IV Hasil kemajuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.1 Hal yang telah dilakukan pada semester berjalan . . . . . . . . . IV.1.1 Simulasi teknik exhaustive dan non-exhaustive search . . IV.1.2 Mengusulkan teknik tail-scan (uniform dan random tail scan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.1.3 Mempublikasikan hasil-hasil yang diperoleh . . . . . . . . IV.2 Perbandingan Kemajuan II dan Kemajuan I . . . . . . . . . . . . BAB V Penutup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ii iii iv v 1 1 3 4 6 6 7 9 13 13 13 15 18 20 20 20 21 22 23 25 26
DAFTAR GAMBAR
II.1 Antennas arrangement in ULA with distance d between element . . . . II.2 Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steering vector sudut-sudut yang dipindai . . . . . . . . . . . . . . . . . . . . . III.1 Ilustrasi exhaustive search. Algoritma memindai pada semua arah untuk memperoleh arah sumber sinyal . . . . . . . . . . . . . . . . . . . . . . III.2 Blok diagram skema non-exhaustive search dengan fungsi pemindaian kasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3 Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudut dalam koordinat polar (b). dalam koordinat kartesian . . . . . . . . . . III.4 Ilustrasi tracking object dengan teknik non-exhaustive search serta update scanning window pada setiap waktu. (a),(b), dan (c) pergerakan objek beserta update scanning window yang bersesuaian. (d). ilustrasi pergeseran scanning window pada setiap waktu; W1, W2, W3 adalah scanning window berturut-turut pada t1, t2 dan t3 . . . . . . . . . . . III.5 Ilustrasi detail tentang proses update scanning window dengan menggunakan median dari posisi objek. (a) hasil scanning kasar dengan algoritma klasik pada semua sudut,(b) penerapan scanning window pada sudut yang dianggap memiliki objek, (c) objek bergerak sehingga puncak scanning bergeser menuju batas window. (d). update scanning window, sehingga puncak scanning berada di tengah scanning window . III.6 Hasil simulasi: perbandingan skema exhaustive search terhadap . . . . III.7 Non exhaustive search dengan tail scanning . . . . . . . . . . . . . . . III.8 Non exhaustive search dengan tail scan. (a) uniform tail scan, (b) random tail scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.1 Hasil simulasi non-exhaustive search dengan uniform dan random tail scan. Sudut aktual objek diberikan sebagai pembanding . . . . . . . . IV.2 Hasil simulasi non-exhaustive search dengan uniform dan random tail scan dengan sudut pindai utama dipersempit ke 300 sampai 600 . Sudut aktual objek diberikan sebagai pembanding, estimasi yang menyimpang diganti dengan interpolasi dari nilai yang mengapitnya . . . . . . . . . IV.3 Hasil simulasi non-exhaustive search dengan uniform dan random tail scan dengan sudut pindai utama dipersempit ke 300 sampai 600 . Sudut aktual objek diberikan sebagai pembanding, estimasi yang menyimpang diganti dengan interpolasi dari nilai yang mengapitnya . . . . . . . . .
iv
6 11 13 14 15
16
17 18 18 19 22
23
24
DAFTAR TABEL
I.1 I.2
Perbandingan Referensi State of The Art . . . . . . . . . . . . . . . . . Premis dan Hipotesis yang dirumuskan dalam penelitian . . . . . . . .
4 5
IV.1 Parameter simulasi exhaustive dan non exhaustive search . . . . . . . . IV.2 Perbandingan Kemajuan I dan Kemajuan II . . . . . . . . . . . . . . .
20 24
v
BAB I Pendahuluan I.1 Latar Belakang Teknik compressive sensing untuk estimasi arah kedatangan sinyal memperoleh perhatian yang besar pada dekade saat ini. Meski pun CS mulai dianggap sebagai bidang ilmu yang cukup matang pada pertengahan tahun 2000an (Donoho (2006), Candes dan Wakin (2006), Baraniuk (2007)), teknik yang mendasarinya telah berkembang lebih dahulu, seperti matching pursuit (Mallat dan Zhang (1993)), basis pursuit Chen dkk. (2001), algoritma greedy (Tropp (2004)) maupun wavelet. Penerapan teknik CS telah dilakukan pada berbagai bidang, antara lain: kompresi data (Candes dan Wakin (2006), Wahidah dan Suksmono (2010)), channel coding (Candes dan Wakin (2006)), MRI imaging (Swastika dan Haneishi (2012)), wireless channel estimation (Hayasi dkk. (2013)). Saat ini, teknik CS telah pula diterapkan pada bidang radar. Secara umum radar memiliki tiga fungsi, yaitu: estimasi arah kedatangan, estimasi jarak, dan estimasi kecepatan. Pada bidang estimasi arah kedatangan sinyal, teknik Compressive Sening ditujukan untuk mengurangi jumlah sampel yang harus diakuisisi oleh penerima. Jumlah sampel yang sedikit akan memberikan keuntungan pada kebutuhan bandwidth telekomunikasi yang rendah. Dengan demikian, skema distributed radar system dapat diimplementasikan lebih mudah untuk menjangkau wilayah yang luas. Secara perkembangan, teknik estimasi arah kedatangan sinyal sendiri telah berkembang sejak era analog, sampai dengan era digital. Pada era digital, teknik estimasi arah kedatangan sinyal dipelopori antara lain oleh algoritma Capon atau MVDR (Dmochowski dkk. (2007)). Dengan memanfaatkan kovariansi matrik sinyal penerima, serta steering vector pada arayh yang dipindai, algoritma ini berhasil memperoleh estimasi arah kedatangan sinyal dengan spektrum puncak yang cukup tajam. Schmidt melakukan terobosan pada bidang estimasi DoA ini dengan mengusulkan algoritma MUSIC (Multiple Signal Classification, Schmidt (1986)). Algoritma ini membuka dimensi baru dengan penggunaan teknik sub-space yang berasal dari dekomposisi nilai eigen dari matrik kovariansi. Roy dkk. (1986) juga menggunakan teknik sub-space untuk melakukan estimasi arah kedatangan sinyal. Teknik ini berbeda dengan MUSIC karena teknik ini tidak melakukan estimasi arah kedatangan sinyal dengan memindai semua arah, namun ia memanfaatkan struktur dari susunan antena penerima. Estimasi arah kedatangan diperoleh dengan manipulasi matematis dari susunan ini. Teknik ini populer dengan istilah ESPRIT (Estimation
1
of Signal Parameters via Rotational Invariant Techniques). Veen dan Buckley (1988) mengajukan skema yang sederhana dibandingkan dengan MUSIC dan ESPRIT, yaitu skema delay and sum (DAS). Skema ini memiliki prinsip estimasi arah kedatangan dengan mendelay fasa dengan suatu mekanisme pada setiap elemen antena. Pada nilai fasa tertentu, diperoleh sinyal terima terkuat. Sudut yang berkorespondensi dengan delay tersebut diambil sebagai estimasi arah kedatangan sinyal. Teknik klasik pada umumnya bersandar pada teorema sampling klasik Shannon-Nyquist dalam mengakuisisi data. Akuisisi data dilakukan dengan kecepatan sampling sekurang-kurangnya dua kali frekuensi tertinggi sinyal informasi. Akibat dari adanya skema akuisisi ini, data yang diolah oleh algoritma klasik adalah sangat besar. Teknik distributed radar system yang bersandar pada komunikasi antar unit (seperti wireless sensor network) akan memiliki masalah jika harus mentransmisikan data besar setiap saat. Oleh karena itu teknik CS untuk DoA sangat diperlukan pada kondisi tersebut. Secara umum, terdapat tiga kategori besar dalam pemanfaatan compressive sensing untuk estimasi arah kedatangan sinyal: skema sparsitas waktu, skema sparsitas ruang, dan skema sparsitas sudut. Sparsitas waktu mengambil asumsi bahwa sinyal yang diterima sensor bersifat sparse secara sampel per sampel. Mengambil asumsi ini, maka pengurangan sampel dilakukan dalam ranah waktu. Penelitian yang memanfaatkan skema ini antara lain adalah Wang dkk. (2009). Di sisi lain, skema sparsitas ruang mengambil asumsi bahwa sinyal yang diterima suatu sensor adalah sama dengan sinyal yang diterima oleh sensor yang lain dengan perbedaan pada fasa. Dengan asumsi ini, maka jumlah sensor dapat dikurangi sampai menjadi sebanyak sinyal yang diterima. Pengurangan jumlah sensor berarti juga mengurangi jumlah sampel yang diterima. Penelitian yang memanfaatkan skema ini antara lain adalah Gurbuz dan McClellan (2008), dan Jouny (2011). Skema sparsitas sudut mengambil asumsi bahwa sinyal yang datang hanya pada sudut-sudut tertentu. Dengan asumsi ini, maka algoritma estimasi arah kedatangan dilakukan dengan mencari spektral tak nol pada matrik sinyal penerima yang disusun terdiri dari semua sudut arah kedatangan yang dipindai. Penelitian yang menggunakan skema ini antara lain adalah Gorodnitsky dan Rao (1997) dan Stoica dkk. (2011). Skema sparsitas sudut memiliki keuntungan utama dari pada skema sparsitas waktu dan sparsitas sensor yaitu pada jumlah sampel yang sedikit. Penelitian Gorodnitsky dan Rao (1997) mengusulkan penggunaan satu sampel untuk estimasi arah kedatangan. Untuk keperluan rekonstruksi, Gorodnitsky dan Rao menggunakan algoritma Focal Underdetermined System Solver (FOCUSS). Dalam lingkungan dengan derau yang rendah, hasil estimasi arah kedatangan yang dilaporkan oleh Gorodnitsky dan Rao tersebut memiliki resolusi yang tajam. Meski keuntungan ini, algoritma FOCUSS
2
yang ditawarkan mengalami masalah pada lingkungan dengan derau tinggi (Usman dkk. (2014)). Teknik multi sampel yang dilakukan oleh Stoica dkk. (2011) memperbaiki performa yang lebih baik, namun proses komputasi yang lebih tinggi. Proses komputasi yang lebih tinggi ini disebabkan antara lain oleh jumlah sampel yang lebih banyak dan basis perhitungan pada bilangan kompleks. Permasalahan yang juga perlu diatasi pada skema sparsitas sudut adalah pemindaian yang dilakukan pada semua arah menyebabkan sensing matrix A memiliki dimensi yang sangat besar. Hal ini menyebabkan proses rekonstruksi CS berjalan lambat. Penelitian yang dilakukan ini adalah untuk menjawab permasalahan tersebut.
I.2 State of The Art Pada bagian ini, dipilih tiga referensi yang dijadikan sebagai state of the art. Pemilihan tiga referensi ini dikarenakan karena ketiga referensi ini adalah referensi langsung yang terkait pada upaya penyelesaian masalah yang diusulkan. Ketiga referensi ini adalah Gorodnitsky dan Rao (1997), Stoica dkk. (2011), dan Dai dkk. (2013). Detail dari ketiga referensi tersebut adalah sebagai berikut : 1. Gorodnitsky dan Rao (1997): Sparse Signal Reconstruction form Limited data Using FOCUSS: a re-weighted minimum norm algorithm, Publikasi : IEEE Transaction on Signal Processing, Vol. 45, No.3 (Referensi #1) 2. Stoica, Babu, dan Li (2011): SPICE: A sparse covariance-based estimation method for array processing, Publikasi : IEEE Transaction of Signal Processing, Vol.59, No.2 (Referensi #2) 3. Dai, Xu, dan Zhao (2013): Direction-of-Arrival Estimation Via Real-Valued Sparse Representation, Publikasi : IEEE Antennas and Wireless Propagation Letters (Referensi #3) Referensi #1 menjadi referensi utama dari skema sparsitas sudut. Sejauh yang penulis teliti, Referensi #1 dapat dianggap sebagai karya seminal dari teknik sparsitas sudut. Hal yang menarik dikaji adalah bahwa teknik ini dapat bekerja dengan menggunakan satu sampel sinyal saja. Referensi #2 membahas tentang teknik rekonstruksi dengan metode covariance-based. Teknik ini memperbaiki hasil dari Referensi #1 dalam hal ketahanan dalam lingkungan derau tinggi. Teknik ini mengakomodasi penggunaan multi sampel. Referensi #3 membahas tentang teknik penyederhaan perhitungan rekonstruksi compressive sensing dengan cara mengubah nilai-nilai kompleks menjadi nilai-nilai riil. Pengubahan ini diklaim oleh para penulisnya dapat mempercepat komputasi menjadi 4 kali. Dalam kerangka tiga
3
referensi ini penelitian ini dilakukan dan dikembangkan. Tabel I.1 memperlihatkan perbandingan tekniks dari ketiga referensi ini. Tabel I.1. Perbandingan Referensi State of The Art Perihal Aplikasi
Tujuan
Skema
Referensi #1 Estimasi arah kedatangan sinyal dengan algoritma FOCUSS Menunjukkan bahwa teknik CS dengan satu sampel dapat menghasilkan estimasi arah yang baik dan resolusi tinggi Jumlah sumber : 3 (pada sudut -44, -33, 56); Jumlah sensor : 8; Jumlah sampel 1 ; Algoritma Inisialisasi MVDR
Kekurangan Tidak robust pada lingkungan dengan derau tinggi
Kelebihan
Hanya menggunakan satu sampel, sangat efisien bandwidth jika ditransmisikan
Referensi #2 Estimasi arah kedatangan sinyal dengan algoritma SPICE Teknik estimasi arah kedatangan beberapa sampel sekaligus
Jumlah sumber : 3 (pada sudut 10, 40 dan 55 derajat); Jumlah sensor : 10 ; Jumlah sample : 200 ; Algoritma inisialisasi SPICE Kompleksitas tinggi karena melakukan exhaustive search pada semua arah
Mengakomodasi multi-sample sehingga lebih robust pada lingkungan dengan derau tinggi
Referensi #3 Estimasi arah kedatangan dengan compressive sensing dengan nilai riil Mempercepat perhitungan compressive sensing dengan transformasi unitary untuk memperoleh nilai matrik riil 2 sumber (pada sudut -2.5 dan 3.5 derajat) ; Jumlah sensor : 10 ; Jumlah sampel : 100 ; Algoritma inisialisasi : MUSIC kompleksitas tinggi: teknik Singular Value Decomposition (SVD) diterapkan pada matrik besar serta perhitungan dekomposisi memerlukan waktu yang besar komputasi yang lebih ringan dibandingkan
I.3 Premis dan Hipotesis Pada Kemajuan I telah disampaikan premis yang mendasari penelitian ini, yaitu : 1). Skema sparsitas sudut memiliki kelemahan pada lingkungan dengan derau tinggi, 2). Skema sparsitas sudut memiliki kompleksitas rekonstruksi yang tinggi. Kedua premis tersebut telah dibuktikan dengan simulasi komputer yang dilakukan. Hasil pembuktian tersebut telah dipublikasikan sebagai publikasi awal dari penelitian ini (Usman dkk. (2014)).
4
Pada Kemajuan II ini, dilakukan simulasi lanjutan yaitu perbaikan skema yang ada dengan teknik non-exhaustive search. Dari percobaan-percobaan yang dilakukan, maka diperoleh premis-premis lanjutan, yaitu: 3). Skema sparsitas sudut dapat bekerja dengan sudut pindai yang lebih sempit (non-exhaustive search). Ada pun hipotesis yang diajukan sebagai jawaban dari premis tersebut adalah: 1). Kelemahan teknik sparsitas sudut dapat diatasi dengan teknik yang mengakomodasi pengolahan beberapa sampel sekaligus, 2). Pengurangan kompleksitas (yang berimplikasi pada peningkatan kecepatan komputasi) dapat dilakukan dengan pra-pemindaian dan penyederhanaan perhitungan dalam matrik riil. Hasil pembuktian dari dua hipotesis ini diharapkan dapat diformulasikan ke dalam suatu skema atau model. Skema atau model dapat menjadi kontribusi pengetahuan pada bidang aplikasi compressive sensing untuk estimasi arah kedatangan sinyal. Susunan premis dan hipotesis ini dirangkum dalam Tabel I.2. Tabel I.2. Premis dan Hipotesis yang dirumuskan dalam penelitian Premis Skema sparsitas sudut memiliki akurasi yang buruk pada lingkungan derau tinggi Skema sparsitas sudut memiliki kompleksitas rekonstruksi yang tinggi
Hipotesis Akurasi pada lingkungan derau tinggi dapat ditingkatkan dengan teknik yang mengolah beberapa sampel sekaligus Pengurangan kompleksitas dapat dilakukan dengan pra-pemindaian dan pemindaian pada arah tertentu saja non-exhaustive search
5
BAB II Landasan Teori
II.1 Model matematis sistem Untuk keperluan simulasi, maka model matematis dari sistem yang ditinjau perlu dijabarkan terlebih dahulu. Tinjau susunan antena (antenna array) yang terdiri dari M buah elemen antena. Elemen antena ini disusun sehingga terletak pada satu garis, dengan jarak antar antena konstan. Susunan ini disebut sebagai uniform linear array / ULA. Misalkan bahwa sumber sinyal datang pada jarak yang jauh dengan sudut kedatangan sebesar θ relatif terhadap garis normal susunan antena (Gbr. II.1). Jika jarak sistem antena ke sumber jauh lebih besar dari pada dimensi susunan antena, maka berkas yang sampai ke masing-masing antena dapat dianggap sejajar. l1 θ
x1 (t) x2 (t)
d d
x3 (t)
∆
R
2∆
l2 l3
lM
(M − 1)∆
xM (t)
Gambar II.1. Antennas arrangement in ULA with distance d between element Dengan menggunakan antena paling atas sebagai referensi, serta jarak antar elemen antena adalah d, maka perbedaan jarak tempuh pada masing-masing antena (∆) dapat ditulis sebagai ∆ = d · sin(θ).
(II.1)
Perbedaan jarak ini berkorespondensi dengan delay fasa sebesar : 2π · d · sin(θ) (II.2) λ Dengan mengumpulkan sinyal yang diterima oleh masing-masing antena pada suatu vektor x, maka persamaan sinyal terima pada keluaran array adalah : φ=
6
x = a·s+n
(II.3)
Pada pers.II.3, s adalah sinyal pada masukan antena (dengan dimensi p kali N snaps; p adalah jumlah objek), x menotasikan sinyal pada keluaran antena (dengan dimensi M kali N snaps), n dalah white gaussian noise, dan a adalah array steering vector atau array manifold. Steering vector a dapat dinyatakan sebagai : h
a = 1 e−jψ e−j(M −1)ψ
iT
(II.4)
Sebagai penerima, steering vector menyatakan bobot pada antena yang berkorespondensi dengan arah penerimaan maksimum dari sinyal datang (main beam).
II.2 Compressive Sensing Compressive Sampling/Sensing (CS), adalah pendekatan baru yang menyatukan antara proses sampling dan kompresi. Dengan kekhususan bahwa sinyal yang disampling bersifat sparse (mayoritas sinyal adalah nol dan sedikit sisanya tak nol). Dengan asumsi ini, maka teknik CS dapat digunakan untuk mensampling sinyal dengan rate yang jauh lebih kecil dari pada sampling rate klasik Nyquist. Pada sampling rate yang rendah ini, CS tetap masih mampu untuk merekonstruksi sinyal semula. Kemampuan ini membuka peluang CS dapat menggantikan peralatan yang ada saat ini dengan peralatan yang bekerja berdasarkan prinsip CS yang efisien. Secara prinsip, pensamplingan dengan CS dilakukan dengan mengumpulkan secara random dari sampel lengkap. Pada teknik sampling klasik Nyquist, proses sampling dan rekonstruksi secara prinsip adalah sederhana dibandingkan dengan sampling dan rekonstruksi pada CS. Proses sampling pada teknik sampling klasik dilakukan dengan melakukan pencuplikan pada sinyal analog dengan jarak antar sampel yang sama/konstan. Pada bagian rekonstruksi, sinyal hasil sampling difilter dengan filter Nyquist untuk memperoleh kembali sinyal semula. Pada teknik CS, sebelum proses sampling dapat dilaksanakan, pertama harus ditentukan terlebih dahulu basis dua basis, yaitu basis sparsitas Ψ dan basis projeksi Φ. Keberhasilan teknik CS tergantung pada keberhasilan menentukan kedua basis tersebut. Dengan demikian proses modifikasi dari sinyal pada sisi penerima perlu dilakukan. Ini berarti bahwa perangkat CS akan lebih kompleks dibandingkan dengan peralatan sampling klasik. Pada sisi rekonstruksi, solusi dari teknik CS tidaklah unik/tunggal. Dengan kata lain, setelah set solusi ditemukan, maka diperlukan optimasi dengan suatu kriteria (biasanya adalah norm orde-n) dari set solusi yang ada untuk memperoleh satu solusi terbaik sesuai kriteria tersebut. Solusi terbaik
7
diharapkan (secara statistik) sama atau mendekati sinyal asal. Beberapa peralatan telah dikembangkan dengan prinsip CS ini. Antara lain adalah kamera-satu-piksel (Baraniuk (2007)), sparse MRI (Swastika dan Haneishi (2012)), spectra-denoising (Mingxia dkk. (2013)) dan sebagainya. Formulasi matematika dari compressive sensing. Ada banyak cara untuk menjelaskan prinsip kerja dari compressive sensing. Tapi yang akan dibahas di sini adalah dengan menggunakan prinsip ketidakpastian (uncertainty principle atau UP). Prinsip ini menyatakan bahwa suatu sinyal tidak mungkin secara bersamaan dapat dilokalisasi dengan baik pada ranah waktu dan frekuensi. Dengan kata lain, jika suatu sinyal terlokalisasi pada ranah waktu, maka sinyal tersebut tidak terlokalisasi pada ranah frekuensi. Sebaliknya jika suatu sinyal terlokalisasi pada ranah frekuensi, maka ia tidak terlokalisasi pada ranah waktu. Jika suatu sinyal f tidak terlokalisasi pada suatu ranah, maka akan selalu dapat dicari suatu transformasi Ψ pada f untuk menghasilkan suatu sinyal textbfF yang bersifat sparse. Dengan kata lain: F = Ψf
(II.5)
Pada sinyal sparse F tersebut, CS dapat dilakukan dengan mengalikan di awal (pre-multiplying) dengan suatu pencuplik Φ yang merupakan suatu matrik CS. g = ΦF = ΦΨf
(II.6)
Jika sinyal asal, f dan hasil transformasinya, F memiliki panjang N , maka sinyal f, dapat direkonstruksi kembali dari sinyal g dengan panjang M (M<
(II.7)
dimana K menyatakan tingkat sparsitas dari sinyal f, C adalah suatu konstanta (sekitar 2), dan µ(Φ, P si) menyatakan fungsi pengukur tingkat koherensi dari Φ dan Ψ. Tingkat koherensi ini diberikan oleh µ(Φ, Ψ) = max |hφ, ψi| φ3Φ,ψ3Ψ
(II.8)
Perkalian antara fungsi sparsitas Ψ dan fungsi sampling Φ dalam bentuk matrik tersebut dapat dinyatakan sebagai matrik sensing A : A = ΨΦ
8
(II.9)
Dengan demikian g = ΨΦf = Af
(II.10)
Proses rekonstruksi secara matematis dilakukan menyelesaikan II.10 dalam f. Namun, oleh karena f memiliki N nilai yang tidak diketahui, sedangkan II.10 memiliki M buah persamaan (M << N ), maka penyelesaian II.10 membelikan banyak alternatif solusi bagi f. Kondisi ini disebut sebagai ill-posed problem. Agar solusi menjadi unik dan sama atau mendekati dari sinyal semula, maka dilakukan optimasi dari solusi yang diperoleh. Optimasi yang umum dilakukan adalah dengan menggunakan optimisasi norm orde-n. Orde yang lazim dipakai dengan asumsi sinyal f bersifat sparse adalah norm- orde 1. Proses rekonstruksi CS ini secara umum dapat dituliskan sebagai min |f |1 s.t. A · f = g
(II.11)
Minimisasi |f |1 berarti mencari solusi f yang paling sparse. Pada lingkungan yang memiliki derau atau noise, maka sinyal terima akan memasukkan faktor derau ini, sehingga permasalahan CS seperti pada II.10 menjadi : g = Af + n
(II.12)
Proses rekonstruksi CS dengan demikian dimodifikasi menjadi: min |f |1 s.t. A · f − g ≤
(II.13)
Dengan adalah suatu bilangan kecil.
II.3 Compressive sensing pada estimasi DoA Pada bidang radar yang ditinjau, khususnya pada algoritma estimasi arah kedatangan sinyal (Direction of Arrival Estimation - DoA), terdapat beberapa skema CS yang telah dilakukan pada penelitian terdahulu. Penerapan CS pada estimasi DoA secara umum terbagi ke dalam tiga skema : sparsitas waktu (Gurbuz dan McClellan (2008), Kim dkk. (2012)), sparsitas ruang (Wang dkk. (2009), Wang dkk. (2010)), and sparsitas sudut (Gorodnitsky dan Rao (1997), Stoica dkk. (2011), Usman dkk. (2014)). Sparsitas waktu mengambil asumsi bahwa sinyal yang dikirim adalah sinusoidal, oleh karena itu, sinyal terima bersifat sparse dalam waktu (atau frekuensi). Sinyal terima x yang dikumpulkan oleh M buah antena N dilakukan sampling pada ranah waktu dengan teknik sampling klasik sebanyak N buah sampel untuk menghasilkan blok sinyal terima sebesar M kali N sinyal masukan. Dengan menggunakan pemrosesan blok,
9
setial blok sinyal terima ini dikalikan-sebelum (pre-multiplied) dengan sensing matrix A (berukuran M kali k, dengan k << N) untuk memperoleh sinyal keluaran y yang berdimensi M kali k, jauh lebih kecil dari pada ukuran sinyal masukkan semula x. Untuk proses estimasi arah kedatangan, sinyal yang telah dikompres ini kemudian dikembalikan ke sinyal semula sebelum algoritma DoA diterapkan. Sparsitas ruang memiliki prinsip kerja yang mirip dengan sparsitas waktu. Jika sparsitas waktu mengasumsikan bahwa sinyal tersebut sparse dalam waktu, maka sparsitas ruang mengasumsikan bahwa masing-masing antena pada susunan antena penerima sebenarnya menerima sinyal yang sama dengan perbedaan hanya pada waktu kedatangan (delay). Dengan demikian, sinyal terima diasumsikan bersifat sparse pada arah antena, atau ruang. Sinyal yang dikumpulkan oleh M buah antena, seperti halnya pada sparsitas waktu, memiliki dimensi M kali N . Proses sensing dilakukan dengan dengan mengalikan sinyal terima dengan sensing matrix A yang berdimensi k kali N . Seperti halnya sparsitas waktu, sinyal semula perlu direkonstruksi ulang dengan sebelum estimasi arah kedatangan dapat dilakukan. Dibandingkan dengan sparsitas waktu, skema sparsitas ruang memiliki kekurangan yaitu tingkat kompresi yang rendah, sedangkan kelebihannya adalah ketahanan sinyal terhadap derau lebih baik, serta lebih mudah direalisasikan dalam bentuk perangkat keras, karena matrik sensing A telah secara langsung memberikan arah panduan pada pembuatan perangkat kerasnya. Skema sistem penerima dengan sparsitas ruang dapat dilihat pada Wang dkk. (2009) dan Wang dkk. (2010). Sparsitas sudut memiliki pendekatan yang berbeda dibandingkan dengan sparsitas waktu dan sparsitas ruang sebelumnya. Skema sparsitas sudut tidak melakukan kompresi pada arah waktu dan ruang. Skema ini mengasumsikan bahwa sinyal yang diterima berasal dari sejumlah sumber sinyal yang terbatas. Beberapa sumber sinyal ini datang pada sudut-sudut yang berbeda. Berdasarkan pada anggapan ini, maka konstruksi permasalahan CS dilakukan dengan menggunakan sensing matrik A yang tersusun atas steering vector dari sinyal datang. Deskripsi matematis yang lebih rinci diberikan pada sub-bab berikutnya. CS formulasi dilakukan dengan menggabungkan sensing matrix A, sparse vektor s, dan snapshot dari sinyal terima x. Rekonstruksi CS tersebut dituliskan sebagai A·s = x (II.14) Jika terdapat derau AWGN, maka Rekonstruksi CS tersebut dimodifikasi menjadi (analogi dengan Persamaan II.12): A · s = x + n.
(II.15)
Dengan menggunakan pendekatan ini, maka sparsitas sudut memiliki keuntungan
10
signifikan dibandingkan dengan skema sparsitas waktu dan sparsitas ruang, karena skema ini memerlukan sangat sedikit sinyal terima, serta proses estimasi DoA dilakukan bersamaan dengan rekonstruksi CS. Dengan kata lain, penyelesaian CS pada sparse matrik s sekaligus juga adalah penyelesaian masalah estimasi arah kedatangan. Estimasi arah kedatangan sinyal diperoleh berdasarkan posisi element tak nol dari dari matrik solusi sparse s (Gorodnitsky dan Rao (1997)). Gambar II.2 mengilustrasikan proses penyusunan konstruksi CS teknik sparsitas sudut.
A a11
a12
a1p
a21
a22
a2p
aM 1
aM 2
aM p
a(θ1 ) a(θ2 )
s s1
x x1i
s2
x2i
s3
x3i
sp
xM i
a(θM )
steering vector at angle θi Gambar II.2. Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steering vector sudut-sudut yang dipindai Meski pun memiliki keuntungan ini, skema sparsitas sudut memiliki kelemahan, yaitu kurang tahan terhadap derau lingkungan. Hal ini diverifikasi oleh Usman dkk. (2014). Pada penelitian tersebut, Usman dkk. (2014) mengusulkan peningkatan performa sinyal dengan menggunakan teknik multi-snaps CS. Skema multi-snaps CS ini dilakukan dengan memperluas vektor sinyal terima x menjadi beberapa snap-shots. Solusi sparse s dengan demikian akan mengikuti perluasan ini. Dengan kata lain, vektor s terdiri dari beberapa kolom, yang masing-masing kolom berkorespondensi dengan hasil estimasi arah kedatangan pada setiap snap-shots. Estimasi DoA dilakukan dengan merata-ratakan nilai estimasi pada setiap snap-shots. Dengan demikian estimasi yang diperoleh menjadi lebih robust dibandingkan dengan hanya menggunakan satu snap-shot. Upaya untuk melakukan perbaikan skema sparsitas sudut dilakukan pula oleh Stoica dkk. (2011) secara terpisah. Skema yang diusulkan oleh Stoica dkk. (2011) diistilahkan dengan independently covariance-based estimation technique (SPICE). Skema Stoica dkk. (2011) juga mengakomodasi kemampuan multi-snaps untuk meningkatkan ketahanan terhadap noise.
11
Permasalahan lainnya dari sparsitas sudut adalah besarnya sensing matrix A. Sebagaimana yang telah dibahas sebelumnya, sensing matrix A disusun berdasarkan steering vector dari arah kedatangan yang dipindai. Pemindaian yang dilakukan pada semua arah kedatangan sinyal (dari −900 sampai 900 ) disebut dengan exhaustive search. Bab selanjutnya membahas dengan terperinci tentang exhaustive search tersebut serta skema peningkatan yang diusulkan.
12
BAB III Metode yang diusulkan
III.1 Exhaustive Search Exhaustive search adalah upaya untuk menemukan arah kedatangan sinyal dengan melakukan pemindaian pada semua arah kedatangan sinyal yang mungkin. Peneliti sebelumnya melakukan pemindaian secara exhaustive ini. Pada makalahnya, objek Gorodnitsky dan Rao (1997) melakukan pemindaian pada semua sudut antara −900 sampai 900 . Stoica dkk. (2011) melakukan pemindaian dari −900 sampai 900 dengan resolusi 0.10 , dengan demikian terdapat 1800 arah pindai yang berkorespondensi dengan matriks sensing A yang berdimensi M kali 1800. Hal yang sama dilakukan oleh Usman dkk. (2014). Gambar III.1 menunjukkan ilustrasi pemindaian dengan teknik exhaustive search. 00
objek
arah pemindaian -900
900
Gambar III.1. Ilustrasi exhaustive search. Algoritma memindai pada semua arah untuk memperoleh arah sumber sinyal Permasalahan yang dihadapi oleh teknik exhaustive search, seperti yang telah dikemukakan sebelumnya, adalah besarnya sensing matrix A. Sensing matriks yang besar memerlukan proses komputasi rekonstruksi CS yang besar, sumber daya yang tinggi, serta waktu yang lama. Penyelesaian permasalahan ini diusulkan pada sub-bab berikutnya yang membahas tentang pemindaian non-exhaustive search.
III.2 Non-exhaustive search Kemajuan yang dicapai pada penelitian ini berkisar pada eksplorasi teknik non-exhaustive search. Teknik ini adalah perbaikan dari teknik exhaustive search berupa pengurangan rentang pemindaian dari semua sudut yang mungkin (tipikal
13
pada −900 sampai 900 ), ke dalam rentang yang lebih sempit. Tentu pemindaian pada rentang yang lebih sempit ini dimungkinkan jika telah ada gambaran tentang arah sumber sinyal. Untuk keperluan memperoleh gambaran tentang arah sumber sinyal tersebut, maka diperlukan suatu pemindaian kasar, misalnya dengan menggunakan estimasi DoA klasik (DAS, MVDR, MUSIC, atau ESPRIT). Setelah gambaran kasar arah kedatangan sinyal ini diperoleh, maka proses DoA selanjutnya dilanjutkan dengan teknik CS dengan rentang sudut sempit, yang diperbarui setiap saat, sesuai dengan arah gerakan objek. Skema pemindaian kasar sebelum teknik CS disebut dengan istilah pra-pemindaian. Skema non-exhaustive search dengan pra-pemindaian selengkapnya diberikan pada Gambar III.2.
Pengaturan Jendela Pemindaian
Pemindaian Kasar
Sinyal terima
Akuisisi
Snapshot
Konstruksi CS
DoA
CS Solver
Gambar III.2. Blok diagram skema non-exhaustive search dengan fungsi pemindaian kasar Pada Gambar III.2 tersebut, sinyal mula-mula diakuisisi oleh sistem antena penerima. Pada awal operasi, sinyal dimasukkan ke blok pemindaian kasar. Proses pada blok pemindaian kasar ini bertujuan untuk memperoleh gambaran umum tentang posisi sinyal. Blok pemindaian kasar ini dapat menggunakan salah satu algoritma klasik, seperti DAS, MVDR, MUSIC, dan ESPRIT. Pada proses kemajuan ini II ini, digunakan teknik MVDR. Teknik ini sederhana serta memiliki resolusi yang tinggi. Skema MUSIC dan ESPRIT memerlukan komputasi yang lebih tinggi, sedangkan DAS memiliki resolusi yang rendah. Gambar III.3 menunjukkan ilustrasi skema non-exhaustive search. Pada gambar tersebut, rentang sudut pemindaian dinyatakan sebagai jendela pindai (scanning window). Tracking objek pada skema CS-DoA. Keuntungan utama pada skema yang ditawarkan ini adalah penambahan kemampuan tracking terhadap gerakan objek
14
objek Objek Scanning Window θ2
θ1
θ
Scanning Window
(b)
(a)
Gambar III.3. Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudut dalam koordinat polar (b). dalam koordinat kartesian mudah untuk dilaksanakan. Hal ini dikarenakan sampling objek dapat dilakukan pada interval tertentu, dan pengambilan sampel sinyal yang sedikit setiap kali pengambilan. Jendela pemindaian (scanning window) dapat digeser-geser pada setiap iterasi menyesuaikan dengan dengan posisi objek. Untuk melakukan update scanning window ini, maka diperlukan suatu skema update. Pada penelitian ini, skema update dilakukan dengan terlebih dahulu menetapkan lebar scanning window (konstan). Pada setiap scanning, titik tengah dari scanning window diupdate sehingga berimpit atau mendekati lokasi dari posisi objek (Gbr III.5). Proses update dengan menjadikan lokasi objek sebagai median dari jendela pindai dapat dinyatakan dengan : θPmax = med([θmin , θmax ])
(III.1)
Pada Pers.III.1, θPmax menyatakan sudut estimasi objek, θmin dan θmax berturut-turut menyatakan batas kiri dan batas kanan dari jendela pindai.
III.3 Tail scanning Skema non-exhaustive search dilakukan dengan pembatasan wilayah sudut pindai hanya pada arah-arah tertentu saja. Namun pembatasan ini ternyata memberikan masalah baru pada proses rekonstruksi CS, yaitu CS Solver yang dalam hal ini adalah cvx-programming, tidak berhasil memperoleh solusi yang konvergen. Fenomena ini tidak diperkirakan sebelumnya, karena dengan asumsi bahwa titik optimal dari CS solver terletak pada lokasi sudut keberadaan sinyal, sedangkan sudut ini sendiri berada pada cakupan sudut yang dipindai. Namun ternyata, cvx-programming tidak berhasil memperoleh solusi yang konvergen.
15
objek objek objek
(a)
(b)
P
t1
t2
objek
objek
(c)
t3 objek
W1
θ
W2 W3
(d)
Gambar III.4. Ilustrasi tracking object dengan teknik non-exhaustive search serta update scanning window pada setiap waktu. (a),(b), dan (c) pergerakan objek beserta update scanning window yang bersesuaian. (d). ilustrasi pergeseran scanning window pada setiap waktu; W1, W2, W3 adalah scanning window berturut-turut pada t1, t2 dan t3 Gambar III.6 mengilustrasikan permasalahan ini. Pada gambar III.6 tersebut, terdapat tiga macam skema yang digunakan. Skema tersebut adalah skema exhaustive search (lebar jendela pindai adalah −900 sampai 900 ), skema non-exhaustive search dengan lebar jendela −300 sampai dengan 900 , dan skema terakhir adalah non-exhaustive search dengan lebar jendela 00 sampai dengan 900 . Sebagai pembanding, posisi aktual dari objek diberikan. Objek tersebut bergerak dari sudut 300 sampai dengan 900 dengan kecepatan 1, 40 per detik. Sumbu datar adalah waktu (dalam detik), dan sumbu tegak adalah sudut (dalam derajat). Pada gambar III.6 tersebut skema exhaustive search dan skema non-exhaustive search dengan sudut pindai lebar (−300 sampai dengan 900 ) berhasil mengikuti pergerakan objek dengan baik. Namun untuk lebar jendela pindai yang terlalu kecil (00 sampai dengan 900 ), cvx-programming gagal memberikan hasil konvergen. Hasil yang diperoleh, iterasi cvx-programming terjebak pada solusi semu di 50 dan 650 . Untuk mengatasi permasalahan ini, maka area pemindaian diperluas mencakup pada arah selain dari arah utama. Arah tambahan ini disebut dengan tail scanning. Gambar III.7 memperlihatkan ilustrasi tail-scanning. Sifat dari tail scan adalah :
16
P
θx1
(a)
θ
P
θx1
θ
(b) P
θx2
θ
(c) P
θx2
(d)
θ
Gambar III.5. Ilustrasi detail tentang proses update scanning window dengan menggunakan median dari posisi objek. (a) hasil scanning kasar dengan algoritma klasik pada semua sudut,(b) penerapan scanning window pada sudut yang dianggap memiliki objek, (c) objek bergerak sehingga puncak scanning bergeser menuju batas window. (d). update scanning window, sehingga puncak scanning berada di tengah scanning window 1. jumlahnya lebih sedikit dibandingkan dengan pemindaian pada arah utama (main-scan) 2. mengarah pada sudut yang tidak terdapat objek 3. berfungsi mencegah algoritma cvx-programming tidak konvergen atau terjebak pada solusi semu Pada penelitian ini, diusulkan dua macam tipe tail scan yaitu uniform tail scan dan random tail scan. Uniform tail scan adalah tail scan yang terpisah pada jarak yang seragam, sedangkan random tail scan adalah tail scan yang jarak antar pemindaian satu dan lainnya terpisah. Gambar ?? menunjukkan ilustrasi uniform tail scan dan random tail scan.
17
70
60
angle (degree)
50
40 w 0 to 90 w -30 to 90 30
w -90 to 90 Actual
20
10
0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 time(second)
Gambar III.6. Hasil simulasi: perbandingan skema exhaustive search terhadap
III.4 CS solver dengan CVX Programming Ada beberapa CS solver yang dapat digunakan untuk menyelesaikan permasalahan estimasi sudut dengan rekonstruksi sparse. Dua solver yang umum dipakai adalah CVX-programming dan l1 -magic. CVX-programming dikembangkan oleh Boyd (2014), sedangkan l1 -magic dikembangkan oleh oleh Romberg (2005). CVX-programming bersifat umum dengan kemampuan melakukan optimasi pada berbagai permasalahan pemrograman linier (Linear Programming - LP). CVX-programming juga dapat mengoptimasi pilihan solusi dengan konstrain norm. Dengan demikian, 00
objek
-900
900
Tail scan Gambar III.7. Non exhaustive search dengan tail scanning
18
00
00
objek
-900
900
objek
-900
900
Tail scan
Tail scan (b)
(a)
Gambar III.8. Non exhaustive search dengan tail scan. (a) uniform tail scan, (b) random tail scan CVX-programming bersifat sangat fleksibel. Engine solver yang digunakan pada CVX-programming antara lain adalah SDPT3 and SeDumi. Terdapat pula solver lain yang berlisensi yang dapat digunakan pada cvx seperti Gurobi dan MOSEK (Boyd (2014)). Untuk menyelesaikan persamaan CS seperti yang terdapat pada persamaan ??, pada CVX-programming, dapat kita tuliskan seperti contoh berikut: begin cvx variable s(n) complex; minimize(norm(s,1)); subject to norm(A*s-x,2) < epsilon; end cvx.
19
BAB IV Hasil kemajuan IV.1 Hal yang telah dilakukan pada semester berjalan Pada Kemajuan II ini, hal-hal yang telah dilakukan adalah: 1. Simulasi dan pembandingan teknik exhaustive dan non-exhaustive search untuk tracking objek yang bergerak. 2. Mengusulkan teknik tail scanning (uniform dan random tail scan) 3. Mensimulasikan teknik non-exhaustive search dengan membandingkannya dengan teknik exhaustive search
tail
scan,
dan
4. mempublikasikan hasil-hasil yang diperoleh
IV.1.1 Simulasi teknik exhaustive dan non-exhaustive search Simulasi komputer dilakukan untuk memverifikasi efektifitas skema non-exhaustive search yang diusulkan. Skema dari teknik non-exhaustive search ini adalah seperti pada Gambar III.2. Lingkungan simulasi diberikan pada Tabel IV.1 Tabel IV.1. Parameter simulasi exhaustive dan non exhaustive search No Skema Parameter Nilai 1 Exhaustive Search Susunan Antena ULA 12 element SNR 10 dB Kecepatan Objek 1,40 /s 0 Sudut jelajah objek 30 sampai 600 Resolusi pindai 10 Jumlah objek 1 2 Non Exhaustive Search Parameter dasar sama dengan (Jumlah antena, dll.) exhaustive search Skema pra-pemindaian MVDR Lebar jendela pindai −300 sampai 900 dan 00 sampai 900 CS Solver CVX-programming Hasil simulasi diperlihatkan pada Gambar III.6. Pada gambar tersebut, terlihat bahwa skema non-exhaustive search dengan lebar jendela pindai yang cukup lebar (-300 sampai dengan 900 ) memiliki performa yang baik dalam melakukan tracking
20
pada gerakan objek. Performanya tidak jauh berbeda dengan performa exhaustive search. Permasalahan muncul ketika lebar jendela pindai dipersempit pada sudut 00 sampai 900 . Pada rentang sudut pindai ini, rekonstruksi dengan cvx-programming tidak berhasil memperoleh solusi yang konvergen. Iterasi cvx-programming terjebak pada dua nilai sudut estimasi salah yaitu 50 dan 650 . Oleh karena skema exhaustive search berhasil sedangkan teknik non-exhaustive search gagal untuk rentang sudut pindai yang sempit, maka kenyataan ini memberikan inspirasi untuk menambahkan pemindaian pada sudut-sudut tambahan di luar dari arah pindai utama. Pemindaian pada sudut-sudut tambahan ini diistilahkan dengan tail scan.
IV.1.2 Mengusulkan teknik tail-scan (uniform dan random tail scan) Teknik tail scan muncul sebagai upaya untuk mengatasi permasalahan ketidakkonvergen pada rekonstruksi CS untuk sudut pindai yang terlalu sempit. Sudut pindai yang terlalu sempit, berdasarkan simulasi yang dilakukan adalah sudut pindai kurang dari 900 (00 sampai 900 ). Teknik tail-scan menambahkan pemindaian pada arah yang berada di luar dari sudut pindai utama. Sebagai mana yang telah dipaparkan pada Bab III, teknik tail scan diusulkan dua macam, yaitu tail scan uniform dan tail scan random. Efektifitas tail scan ini diujicobakan pada simulasi komputer. Pada simulasi ini, parameter simulasi adalah sama dengan parameter simulasi sebelumnya, dengan detil parameter simulasi adalah seperti pada Tabel IV.1. Lebar jendela pindai arah utama adalah 00 sampai dengan 900 . Sedangkan tail scan dilakukan secara random dan uniform pada 20 arah pindai yang berbeda. Hasil simulasi adalah seperti yang ditunjukkan pada Gambar IV.1. Pada Gambar IV.1 tersebut, terlihat bahwa performa non-exhaustive search meningkat dibandingkan dengan tanpa tail scan. Teknik non-exhaustive search dapat men-tracking objek dengan baik. Rekonstruksi CS tidak lagi terjebak pada solusi semu. Kelemahan yang masih terlihat adalah masih terjadi kesalahan deteksi sudut pada iterasi tertentu (pada t=11 untuk uniform tail scan, dan t=15 pada random tail scan). Namun kesalahan ini dapat diperbaiki dengan membuang nilai yang menyimpang ini dengan interpolasi nilai pada titik-titik di antaranya. Setelah berhasil memperbaiki performansi non-exhaustive search dengan teknik tail scan, percobaan berikutnya adalah mempersempit lebih lanjut lebar dari jendela pindai utama. Pada percobaan sebelumnya, jendela pindai utama adalah dari 00 sampai dengan 900 . Selanjutnya, lebar jendela pindai utama ini dipersempit dari 300 sampai
21
80 60 40
UniTail RNDTail Actual
angle (degree)
20 0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22
-20 -40 -60 -80 -100
time
Gambar IV.1. Hasil simulasi non-exhaustive search dengan uniform dan random tail scan. Sudut aktual objek diberikan sebagai pembanding dengan 900 . Tail scan dilakukan dengan cara yang sama yaitu secara uniform dan random dengan 20 arah berbeda. Nilai-nilai yang menyimpang dibuang dan diganti dengan interpolasi dari nilai yang mengapitnya. Hasil simulasi dapat dilihat pada Gambar IV.2. Untuk mengetahui lebih lanjut dampak dari tail scan, pada percobaan berikutnya dilakukan simulasi dengan mengubah jumlah dari tail scan yang ada. Hasil simulasi
IV.1.3 Mempublikasikan hasil-hasil yang diperoleh Pada semester dengan Kemajuan II ini, hasil-hasil simulasi yang diperoleh dipublikasikan pada konfrensi internasional. Konfrensi yang dipilih adalah APWIMob2015 (IEEE Asia Pacific Conference on Wireless and Mobile 2015). Judul dari publikasi ini adalah : Uniform Non Exhaustive Sparse Reconstruction for Direction of Arrival Estimation. Publikasi ini telah dikirimkan kepada panitia seminar pada ddd Mei 2015, dan saat ini sedang melalui proses review. Pemberitahuan penerimaan pada 27 Juni 2015. Isi publikasi selengkapnya diberikan pada Lampiran A, dan informasi selengkapnya
22
70
60
50
angle (degree)
exhaustive search Actual
40
random tail scan uniform tail scan 30
20
10
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 time(second)
Gambar IV.2. Hasil simulasi non-exhaustive search dengan uniform dan random tail scan dengan sudut pindai utama dipersempit ke 300 sampai 600 . Sudut aktual objek diberikan sebagai pembanding, estimasi yang menyimpang diganti dengan interpolasi dari nilai yang mengapitnya tentang konfrensi tersebut pada Lampiran B.
IV.2 Perbandingan Kemajuan II dan Kemajuan I Pada semester sebelumnya (Kemajuan I), telah ditetapkan bahwa teknik Compressive Sensing dengan sparsitas sudut sebagai fokus dari penelitian. Transformasi unitary yang mengubah matrik kovariansi dari kompleks menjadi riil diusulkan sebagai bagian dari proses untuk mempercepat komputasi. Pada Kemajuan I juga muncul ide untuk mempercepat proses rekonstruksi CS dengan memanfaatkan teknik non-exhaustive search. Ide tersebut direncanakan dilaksanakan pada Kemajuan II ini. Pada Kemajuan II ini, skema non-exhaustive search tersebut disimulasikan dan diteliti secara lebih mendalam. Hasil yang diperoleh adalah skema non-exhaustive search tersebut bekerja baik jika lebar jendela pindai cukup lebar, dan tidak berhasil jika lebar jendela pindai sempit. Pada Kemajuan II ini juga diusulkan teknik baru yaitu tail scan untuk mengatasi masalah itu. Teknik ini juga disimulasikan dan memberikan hasil yang baik. Tabel IV.2 memperlihatkan perbandingan antara Kemajuan I dan Kemajuan II.
23
50 45 40 35 30 uniform tail
25
random tail without tail
20 15 10 5 0 3
6
9
12
15
18
21
24
27
30
Gambar IV.3. Hasil simulasi non-exhaustive search dengan uniform dan random tail scan dengan sudut pindai utama dipersempit ke 300 sampai 600 . Sudut aktual objek diberikan sebagai pembanding, estimasi yang menyimpang diganti dengan interpolasi dari nilai yang mengapitnya
Tabel IV.2. Perbandingan Kemajuan I dan Kemajuan II No Kemajuan Hasil Keterangan 1 Kemajuan I Fokus Penelitian CS-DoA dengan sparsitas sudut Usulan Penggunaan Unitary Transform untuk konversi matriks kovariansi kompleks ke riil Publikasi Poster pada ICODSE2014 Usulan selanjutnya Teknik non-exhaustive search 2 Kemajuan II Fokus Penelitian CS-DoA dengan sparsitas sudut Usulan dan simulasi non-exhaustive search random dan uniform tail scan tracking objek dengan CS-DoA Publikasi IEEE APWIMob2015 conference Usulan selanjutnya memperdalam tail-scan basis matematis tail-scan
24
BAB V Penutup
Pada Kemajuan II ini, telah dilaporkan mengenai penjelasan tentang topik penelitian serta hasil-hasil yang dicapai sampai sejauh ini. Beberapa hasil simulasi dan ide baru yang dicapai pada Kemajuan II membuka peluang untuk suatu kontribusi nyata dalam algoritma CS-DoA berbasis sparsitas sudut dengan teknik non-exhaustive search dengan tail-scan. Teknik ini, sejauh yang telah diteliti pada literatur, belum pernah dilakukan oleh peneliti lain sebelumnya. Rencana ke depan adalah memperdalam teknik tail scan ini baik secara simulasi mau pun secara teori. Penjelasan matematik dari teknik tail scan ini memerlukan pemahaman mendalam tentang prinsip kerja CVX Programming. Oleh karena itu, studi literatur tentang CVX programming akan diprioritaskan pada kemajuan berikutnya. Keberhasilan pemahaman landasan matematik serta simulasi CVX programming diharapkan memberikan kontribusi signifikan pada keilmuan CS-DoA yang diteliti ini.
25
Daftar Pustaka
Baraniuk, R. (2007): Compressive Sensing, IEEE Signal Processing Magazine, 24. Boyd, S. (2014): CVX: Matlab Software for Disciplined Convex Programming, URL http://cvxr.com/cvx/. Candes, E. dan Wakin, M. B. (2006): Compressive Sampling, Proceedings of the International Congress of Mathematicians, Madrid, Spain. Capon, J. (1969): High-resolution frequency-wavenumber spectrum analysis, Proceedings of the IEEE, 57(8), 1408–1418. Chen, S. S., Donoho, D. L., dan Saunders, M. A. (2001): Atomic Decomposition by Basis Pursuit, SIAM Review, Society for Industrial and Applied Mathematics, 43(1), 129 to 159. Dai, J., Xu, X., dan Zhao, D. (2013): Direction-of-Arrival Estimation Via Real-Valued Sparse Representation, Antennas and Wireless Propagation Letters, IEEE, 12, 376–379. Dmochowski, J., Benesty, J., dan Affes, S. (2007): Direction of Arrival Estimation Using the Parameterized Spatial Correlation Matrix, Audio, Speech, and Language Processing, IEEE Transactions on, 15(4), 1327–1339. Donoho, D. L. (2006): Compressed Sensing, IEEE Transactions on Information Theory, 52(4). Gorodnitsky, I. F. dan Rao, B. D. (1997): Sparse Signal Reconstruction from Limited Data Using FOCUSS: A Re-weighted Minimum Norm Algorithm, IEEE Transactions on Signal Processing, 45(3). Gurbuz, A. C. dan McClellan, J. H. (2008): A Compressive Beamforming Method, Proceeding of the IEEE International Conference on Acoustics, Speech and Signal Processing. Hayasi, K., Nagahara, M., dan Tanaka, T. (2013): A UserŠs Guide to Compressive Sensing for Communications Systems, In IEICE Transaction on Communication, E96-B(3), 685–712.
26
Jouny, I. (2011): Music DOA estimation with compressive sensing and/or compressive arrays, Antennas and Propagation (APSURSI), 2011 IEEE International Symposium on, 2016–2019. Kim, J. M., Lee, O. K., dan Ye, J. C. (2012): Compressive MUSIC: Revisiting the Link Between Compressive Sensing and Array Signal Processing, IEEE Transctions on Information Theory, Vol. 58, No. 1, January 2012. Mallat, S. dan Zhang, Z. (1993): Matching Pursuits With Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, 41(12). Mingxia, X., Changhua, L., Xing, M., dan Weiwei, J. (2013): The Application of Compressive Sensing on Spectra De-noising, TELKOMNIKA, 11(10), 6151–6157. Telkomnika Ahmad Dahlan. Romberg, J. (2005): l1-Magic, URL http://users.ece.gatech.edu/ justin/l1magic/. Roy, R., Paulraj, A., dan Kailath, T. (1986): Estimation of Signal Parameters via Rotational Invariance Techniques Ű ESPRIT., Proceeding of IEEE Military Communications (MILCOM) Conference - Communications, 3. Schmidt, R. (1986): Multiple emitter location and signal parameter estimation, IEEE Transactions on Antennas and Propagation, 34(3), 276–280. Stoica, P., Babu, P., dan Li, J. (2011): SPICE: A Sparse Covariance-Based Estimation Method for Array Processing, Signal Processing, IEEE Transactions on, 59(2), 629–638. Swastika, W. dan Haneishi, H. (2012): Compressed Sensing for Thoracic MRI with Partial Random Circulant Matrices, TELKOMNIKA, Vol.10, No.1, March 2012, pp. 147 154 e-ISSN: 2087-278X (p-ISSN: 1693-6930), 10(1), 147 154. TELKOMNIKA AHMAD DAHLAN. Tropp, J. A. (2004): Greed is Good : Algorithmic Results for Sparse Approximation, IEEE Transactions on Information Theory, 50(10). Usman, K., Suksmono, A. B., dan Gunawan, H. (2014): Peningkatan Kinerja Skema Estimasi Arah Kedatangan Sinyal dengan Compressive Sensing Sparsitas Sudut dan Sampel Multisnap, Inkom Journal, 8(1), 21–27. Veen, B. V. dan Buckley, K. M. (1988): Beamforming: A Versatile Approach to Spatial Filtering, IEEE ASSP Magazine.
27
Wahidah, I. dan Suksmono, A. B. (2010): RECONSTRUCTION ALGORITHMS FOR COMPRESSIVE VIDEO SENSING USING BASIS PURSUIT, Proceeding of the 6th International Conference on Information & Communication Technology and Systems. Wang, Y., Leus, G., dan Pandharipande, A. (2009): Direction Estimation Using Compressive Sampling Array Processing, Proceeding of IEEE SSP. Wang, Y., Pandharipande, A., dan Leus, G. (2010): Compressive sampling based MVDR spectrum sensing, Proceeding of IAPR.
28
