NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCANPADA ESTIMASI ARAH KEDATANGAN SINYAL

BERBASIS REKONSTRUKSI SPARSE

LAPORAN KEMAJUAN 2

OlehKOREDIANTO USMAN

NIM: 33213002(Program Studi Teknik Elektro dan Informatika)

INSTITUT TEKNOLOGI BANDUNGMei 2015

NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCAN PADAESTIMASI ARAH KEDATANGAN SINYAL BERBASIS

REKONSTRUKSI SPARSE

OlehKoredianto Usman

NIM: 33213002(Program Studi Teknik Elektro dan Informatika)

Institut Teknologi Bandung

MenyetujuiTim 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 CompressiveSensing (CS) ini juga digunakan untuk estimasi arah kedatangan sinyal. Estimasiarah kedatangan sinyal adalah teknik estimasi sudut kedatangan objek yang dideteksidengan peralatan radar atau sonar. Teknik klasik untuk estimasi arah kedatanganantara lain adalah MVDR, MUSIC, dan ESPRIT. Peran dari CS adalah penguranganjumlah sampel akuisisi pada sisi penerima. Pengurangan ini memberi dampak padakecilnya data rate, sehingga dimungkinkan membangun sistem radar terdistribusiuntuk memantau daerah yang luas. Teknik terkini dalam estimasi arah kedatangansinyal dengan compressive sensing adalah dengan metoda sparsitas sudut. Teknik inimengasumsikan sinyal datang berasal dari beberapa sumber berbeda yang berjumlahterbatas. Teknik yang telah dikembangkan peneliti untuk skema ini adalah denganmenggunakan sensing matrix A yang tersusun atas steering vector yang berasal darisemua sudut yang dipindai (-900 sampai 900). Teknik pindai pada semua sudut inidisebut sebagai exhaustive search. Teknik exhaustive search ini memiliki permasalahanpada 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 padapenelitian ini. Pengujian yang dilakukan pada penelitian ini menunjukkan bahwateknik ini memiliki tingkat keberhasilan yang baik. Masih terdapat masalah tambahanyang harus diselesaikan pada teknik non-exhaustive search yaitu rekonstruksi CS tidakkonvergen jika rentang sudut pindai terlalu sempit. Penambahan pemindaian di luararea pemindaian utama (tail-scan) untuk mengatasi masalah ini juga dilakukan padalaporan ini. Landasan matematis untuk teknik tail-scan ini direncanakan pada tahapkemajuan berikutnya.

Kata kunci : compressive sensing, estimasi arah kedatangan sinyal, sparsitas,exhaustive search, non-exhaustive search, tail scan.

ii

DAFTAR ISI

ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiDAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiDAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivDAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vBAB I Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

I.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1I.2 State of The Art . . . . . . . . . . . . . . . . . . . . . . . . . . . 3I.3 Premis dan Hipotesis . . . . . . . . . . . . . . . . . . . . . . . . 4

BAB II Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6II.1 Model matematis sistem . . . . . . . . . . . . . . . . . . . . . . . 6II.2 Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . . . . 7II.3 Compressive sensing pada estimasi DoA . . . . . . . . . . . . . . 9

BAB III Metode yang diusulkan . . . . . . . . . . . . . . . . . . . . . . . . . . 13III.1 Exhaustive Search . . . . . . . . . . . . . . . . . . . . . . . . . . 13III.2 Non-exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . 13III.3 Tail scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15III.4 CS solver dengan CVX Programming . . . . . . . . . . . . . . . 18

BAB IV Hasil kemajuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20IV.1 Hal yang telah dilakukan pada semester berjalan . . . . . . . . . 20

IV.1.1 Simulasi teknik exhaustive dan non-exhaustive search . . 20IV.1.2 Mengusulkan teknik tail-scan (uniform dan random tail

scan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21IV.1.3 Mempublikasikan hasil-hasil yang diperoleh . . . . . . . . 22

IV.2 Perbandingan Kemajuan II dan Kemajuan I . . . . . . . . . . . . 23BAB V Penutup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

iii

DAFTAR GAMBAR

II.1 Antennas arrangement in ULA with distance d between element . . . . 6II.2 Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steering

vector sudut-sudut yang dipindai . . . . . . . . . . . . . . . . . . . . . 11

III.1 Ilustrasi exhaustive search. Algoritma memindai pada semua arah untukmemperoleh arah sumber sinyal . . . . . . . . . . . . . . . . . . . . . . 13

III.2 Blok diagram skema non-exhaustive search dengan fungsi pemindaiankasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

III.3 Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudutdalam koordinat polar (b). dalam koordinat kartesian . . . . . . . . . . 15

III.4 Ilustrasi tracking object dengan teknik non-exhaustive search sertaupdate scanning window pada setiap waktu. (a),(b), dan (c) pergerakanobjek beserta update scanning window yang bersesuaian. (d). ilustrasipergeseran scanning window pada setiap waktu; W1, W2, W3 adalahscanning window berturut-turut pada t1, t2 dan t3 . . . . . . . . . . . 16

III.5 Ilustrasi detail tentang proses update scanning window denganmenggunakan median dari posisi objek. (a) hasil scanning kasar denganalgoritma klasik pada semua sudut,(b) penerapan scanning windowpada sudut yang dianggap memiliki objek, (c) objek bergerak sehinggapuncak scanning bergeser menuju batas window. (d). update scanningwindow, sehingga puncak scanning berada di tengah scanning window . 17

III.6 Hasil simulasi: perbandingan skema exhaustive search terhadap . . . . 18III.7 Non exhaustive search dengan tail scanning . . . . . . . . . . . . . . . 18III.8 Non exhaustive search dengan tail scan. (a) uniform tail scan, (b)

random tail scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

IV.1 Hasil simulasi non-exhaustive search dengan uniform dan random tailscan. Sudut aktual objek diberikan sebagai pembanding . . . . . . . . 22

IV.2 Hasil simulasi non-exhaustive search dengan uniform dan random tailscan dengan sudut pindai utama dipersempit ke 300 sampai 600. Sudutaktual objek diberikan sebagai pembanding, estimasi yang menyimpangdiganti dengan interpolasi dari nilai yang mengapitnya . . . . . . . . . 23

IV.3 Hasil simulasi non-exhaustive search dengan uniform dan random tailscan dengan sudut pindai utama dipersempit ke 300 sampai 600. Sudutaktual objek diberikan sebagai pembanding, estimasi yang menyimpangdiganti dengan interpolasi dari nilai yang mengapitnya . . . . . . . . . 24

iv

DAFTAR TABEL

I.1 Perbandingan Referensi State of The Art . . . . . . . . . . . . . . . . . 4I.2 Premis dan Hipotesis yang dirumuskan dalam penelitian . . . . . . . . 5

IV.1 Parameter simulasi exhaustive dan non exhaustive search . . . . . . . . 20IV.2 Perbandingan Kemajuan I dan Kemajuan II . . . . . . . . . . . . . . . 24

v

BAB I Pendahuluan

I.1 Latar Belakang

Teknik compressive sensing untuk estimasi arah kedatangan sinyal memperolehperhatian yang besar pada dekade saat ini. Meski pun CS mulai dianggap sebagaibidang ilmu yang cukup matang pada pertengahan tahun 2000an (Donoho (2006),Candes dan Wakin (2006), Baraniuk (2007)), teknik yang mendasarinya telahberkembang lebih dahulu, seperti matching pursuit (Mallat dan Zhang (1993)), basispursuit Chen dkk. (2001), algoritma greedy (Tropp (2004)) maupun wavelet. Penerapanteknik CS telah dilakukan pada berbagai bidang, antara lain: kompresi data (Candesdan 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 radarmemiliki tiga fungsi, yaitu: estimasi arah kedatangan, estimasi jarak, dan estimasikecepatan. Pada bidang estimasi arah kedatangan sinyal, teknik Compressive Seningditujukan untuk mengurangi jumlah sampel yang harus diakuisisi oleh penerima.Jumlah sampel yang sedikit akan memberikan keuntungan pada kebutuhan bandwidthtelekomunikasi yang rendah. Dengan demikian, skema distributed radar system dapatdiimplementasikan lebih mudah untuk menjangkau wilayah yang luas.

Secara perkembangan, teknik estimasi arah kedatangan sinyal sendiri telahberkembang sejak era analog, sampai dengan era digital. Pada era digital, teknikestimasi arah kedatangan sinyal dipelopori antara lain oleh algoritma Capon atauMVDR (Dmochowski dkk. (2007)). Dengan memanfaatkan kovariansi matrik sinyalpenerima, serta steering vector pada arayh yang dipindai, algoritma ini berhasilmemperoleh estimasi arah kedatangan sinyal dengan spektrum puncak yang cukuptajam. Schmidt melakukan terobosan pada bidang estimasi DoA ini denganmengusulkan algoritma MUSIC (Multiple Signal Classification, Schmidt (1986)).Algoritma ini membuka dimensi baru dengan penggunaan teknik sub-space yangberasal dari dekomposisi nilai eigen dari matrik kovariansi. Roy dkk. (1986) jugamenggunakan teknik sub-space untuk melakukan estimasi arah kedatangan sinyal.Teknik ini berbeda dengan MUSIC karena teknik ini tidak melakukan estimasi arahkedatangan sinyal dengan memindai semua arah, namun ia memanfaatkan strukturdari susunan antena penerima. Estimasi arah kedatangan diperoleh dengan manipulasimatematis 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, yaituskema delay and sum (DAS). Skema ini memiliki prinsip estimasi arah kedatangandengan mendelay fasa dengan suatu mekanisme pada setiap elemen antena. Pada nilaifasa tertentu, diperoleh sinyal terima terkuat. Sudut yang berkorespondensi dengandelay tersebut diambil sebagai estimasi arah kedatangan sinyal.

Teknik klasik pada umumnya bersandar pada teorema sampling klasikShannon-Nyquist dalam mengakuisisi data. Akuisisi data dilakukan dengan kecepatansampling sekurang-kurangnya dua kali frekuensi tertinggi sinyal informasi. Akibatdari adanya skema akuisisi ini, data yang diolah oleh algoritma klasik adalah sangatbesar. Teknik distributed radar system yang bersandar pada komunikasi antar unit(seperti wireless sensor network) akan memiliki masalah jika harus mentransmisikandata besar setiap saat. Oleh karena itu teknik CS untuk DoA sangat diperlukan padakondisi tersebut.

Secara umum, terdapat tiga kategori besar dalam pemanfaatan compressive sensinguntuk estimasi arah kedatangan sinyal: skema sparsitas waktu, skema sparsitas ruang,dan skema sparsitas sudut. Sparsitas waktu mengambil asumsi bahwa sinyal yangditerima sensor bersifat sparse secara sampel per sampel. Mengambil asumsi ini, makapengurangan sampel dilakukan dalam ranah waktu. Penelitian yang memanfaatkanskema ini antara lain adalah Wang dkk. (2009). Di sisi lain, skema sparsitas ruangmengambil asumsi bahwa sinyal yang diterima suatu sensor adalah sama dengan sinyalyang 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 sinyalyang datang hanya pada sudut-sudut tertentu. Dengan asumsi ini, maka algoritmaestimasi arah kedatangan dilakukan dengan mencari spektral tak nol pada matriksinyal 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 waktudan sparsitas sensor yaitu pada jumlah sampel yang sedikit. Penelitian Gorodnitskydan Rao (1997) mengusulkan penggunaan satu sampel untuk estimasi arah kedatangan.Untuk keperluan rekonstruksi, Gorodnitsky dan Rao menggunakan algoritma FocalUnderdetermined System Solver (FOCUSS). Dalam lingkungan dengan derau yangrendah, hasil estimasi arah kedatangan yang dilaporkan oleh Gorodnitsky dan Raotersebut memiliki resolusi yang tajam. Meski keuntungan ini, algoritma FOCUSS

2

yang ditawarkan mengalami masalah pada lingkungan dengan derau tinggi (Usmandkk. (2014)). Teknik multi sampel yang dilakukan oleh Stoica dkk. (2011) memperbaikiperforma yang lebih baik, namun proses komputasi yang lebih tinggi. Proses komputasiyang lebih tinggi ini disebabkan antara lain oleh jumlah sampel yang lebih banyakdan basis perhitungan pada bilangan kompleks. Permasalahan yang juga perludiatasi pada skema sparsitas sudut adalah pemindaian yang dilakukan pada semuaarah menyebabkan sensing matrix A memiliki dimensi yang sangat besar. Hal inimenyebabkan proses rekonstruksi CS berjalan lambat. Penelitian yang dilakukan iniadalah untuk menjawab permasalahan tersebut.

I.2 State of The Art

Pada bagian ini, dipilih tiga referensi yang dijadikan sebagai state of the art. Pemilihantiga referensi ini dikarenakan karena ketiga referensi ini adalah referensi langsung yangterkait pada upaya penyelesaian masalah yang diusulkan. Ketiga referensi ini adalahGorodnitsky dan Rao (1997), Stoica dkk. (2011), dan Dai dkk. (2013). Detail dariketiga referensi tersebut adalah sebagai berikut :

1. Gorodnitsky dan Rao (1997): Sparse Signal Reconstruction form Limited dataUsing FOCUSS: a re-weighted minimum norm algorithm, Publikasi : IEEETransaction on Signal Processing, Vol. 45, No.3 (Referensi #1)

2. Stoica, Babu, dan Li (2011): SPICE: A sparse covariance-based estimationmethod 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-ValuedSparse Representation, Publikasi : IEEE Antennas and Wireless PropagationLetters (Referensi #3)

Referensi #1 menjadi referensi utama dari skema sparsitas sudut. Sejauh yangpenulis teliti, Referensi #1 dapat dianggap sebagai karya seminal dari teknik sparsitassudut. Hal yang menarik dikaji adalah bahwa teknik ini dapat bekerja denganmenggunakan satu sampel sinyal saja. Referensi #2 membahas tentang teknikrekonstruksi dengan metode covariance-based. Teknik ini memperbaiki hasil dariReferensi #1 dalam hal ketahanan dalam lingkungan derau tinggi. Teknik inimengakomodasi penggunaan multi sampel. Referensi #3 membahas tentang teknikpenyederhaan perhitungan rekonstruksi compressive sensing dengan cara mengubahnilai-nilai kompleks menjadi nilai-nilai riil. Pengubahan ini diklaim oleh parapenulisnya dapat mempercepat komputasi menjadi 4 kali. Dalam kerangka tiga

3

referensi ini penelitian ini dilakukan dan dikembangkan. Tabel I.1 memperlihatkanperbandingan tekniks dari ketiga referensi ini.

Tabel I.1. Perbandingan Referensi State of The Art

Perihal Referensi #1 Referensi #2 Referensi #3Aplikasi Estimasi arah

kedatangan sinyaldengan algoritmaFOCUSS

Estimasi arahkedatangan sinyaldengan algoritmaSPICE

Estimasi arahkedatangan dengancompressive sensingdengan nilai riil

Tujuan Menunjukkan bahwateknik CS dengansatu sampel dapatmenghasilkan estimasiarah yang baik danresolusi tinggi

Teknik estimasi arahkedatangan beberapasampel sekaligus

Mempercepatperhitungan compressivesensing dengantransformasi unitaryuntuk memperoleh nilaimatrik riil

Skema Jumlah sumber : 3(pada sudut -44, -33,56); Jumlah sensor :8; Jumlah sampel 1; Algoritma InisialisasiMVDR

Jumlah sumber :3 (pada sudut 10,40 dan 55 derajat);Jumlah sensor : 10 ;Jumlah sample : 200; Algoritma inisialisasiSPICE

2 sumber (pada sudut-2.5 dan 3.5 derajat) ;Jumlah sensor : 10 ;Jumlah sampel : 100; Algoritma inisialisasi :MUSIC

Kekurangan Tidak robust padalingkungan denganderau tinggi

Kompleksitas tinggikarena melakukanexhaustive search padasemua arah

kompleksitas tinggi:teknik Singular ValueDecomposition (SVD)diterapkan pada matrikbesar serta perhitungandekomposisi memerlukanwaktu yang besar

Kelebihan Hanya menggunakansatu sampel, sangatefisien bandwidth jikaditransmisikan

Mengakomodasimulti-sample sehinggalebih robust padalingkungan denganderau tinggi

komputasi yang lebihringan 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 premistersebut telah dibuktikan dengan simulasi komputer yang dilakukan. Hasil pembuktiantersebut telah dipublikasikan sebagai publikasi awal dari penelitian ini (Usman dkk.(2014)).

4

Pada Kemajuan II ini, dilakukan simulasi lanjutan yaitu perbaikan skema yangada dengan teknik non-exhaustive search. Dari percobaan-percobaan yang dilakukan,maka diperoleh premis-premis lanjutan, yaitu: 3). Skema sparsitas sudut dapat bekerjadengan 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 mengakomodasipengolahan beberapa sampel sekaligus, 2). Pengurangan kompleksitas (yangberimplikasi pada peningkatan kecepatan komputasi) dapat dilakukan denganpra-pemindaian dan penyederhanaan perhitungan dalam matrik riil.

Hasil pembuktian dari dua hipotesis ini diharapkan dapat diformulasikan ke dalamsuatu skema atau model. Skema atau model dapat menjadi kontribusi pengetahuanpada 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 HipotesisSkema sparsitas sudut memilikiakurasi yang buruk padalingkungan derau tinggi

Akurasi pada lingkungan derau tinggidapat ditingkatkan dengan teknik yangmengolah beberapa sampel sekaligus

Skema sparsitas sudut memilikikompleksitas rekonstruksi yangtinggi

Pengurangan kompleksitas dapatdilakukan dengan pra-pemindaian danpemindaian pada arah tertentu sajanon-exhaustive search

5

BAB II Landasan Teori

II.1 Model matematis sistem

Untuk keperluan simulasi, maka model matematis dari sistem yang ditinjau perludijabarkan terlebih dahulu. Tinjau susunan antena (antenna array) yang terdiri dariM 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 sudutkedatangan sebesar θ relatif terhadap garis normal susunan antena (Gbr. II.1). Jikajarak sistem antena ke sumber jauh lebih besar dari pada dimensi susunan antena,maka berkas yang sampai ke masing-masing antena dapat dianggap sejajar.

d

d

θ

l1

l2

l3

lM

∆

2∆

(M − 1)∆

R

x1(t)

x2(t)

x3(t)

xM(t)

Gambar II.1. Antennas arrangement in ULA with distance d between element

Dengan menggunakan antena paling atas sebagai referensi, serta jarak antar elemenantena adalah d, maka perbedaan jarak tempuh pada masing-masing antena (∆) dapatditulis 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 suatuvektor 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 Nsnaps;p adalah jumlah objek), x menotasikan sinyal pada keluaran antena (dengan dimensiM kali Nsnaps), n dalah white gaussian noise, dan a adalah array steering vectoratau array manifold. Steering vector a dapat dinyatakan sebagai :

a=[1 e−jψ e−j(M−1)ψ

]T(II.4)

Sebagai penerima, steering vector menyatakan bobot pada antena yangberkorespondensi dengan arah penerimaan maksimum dari sinyal datang (main beam).

II.2 Compressive Sensing

Compressive Sampling/Sensing (CS), adalah pendekatan baru yang menyatukanantara proses sampling dan kompresi. Dengan kekhususan bahwa sinyal yangdisampling bersifat sparse (mayoritas sinyal adalah nol dan sedikit sisanya tak nol).Dengan asumsi ini, maka teknik CS dapat digunakan untuk mensampling sinyaldengan rate yang jauh lebih kecil dari pada sampling rate klasik Nyquist. Padasampling rate yang rendah ini, CS tetap masih mampu untuk merekonstruksi sinyalsemula. Kemampuan ini membuka peluang CS dapat menggantikan peralatan yangada saat ini dengan peralatan yang bekerja berdasarkan prinsip CS yang efisien. Secaraprinsip, pensamplingan dengan CS dilakukan dengan mengumpulkan secara randomdari sampel lengkap.

Pada teknik sampling klasik Nyquist, proses sampling dan rekonstruksi secaraprinsip adalah sederhana dibandingkan dengan sampling dan rekonstruksi pada CS.Proses sampling pada teknik sampling klasik dilakukan dengan melakukan pencuplikanpada sinyal analog dengan jarak antar sampel yang sama/konstan. Pada bagianrekonstruksi, sinyal hasil sampling difilter dengan filter Nyquist untuk memperolehkembali sinyal semula.

Pada teknik CS, sebelum proses sampling dapat dilaksanakan, pertama harusditentukan terlebih dahulu basis dua basis, yaitu basis sparsitas Ψ dan basis projeksiΦ. Keberhasilan teknik CS tergantung pada keberhasilan menentukan kedua basistersebut. Dengan demikian proses modifikasi dari sinyal pada sisi penerima perludilakukan. Ini berarti bahwa perangkat CS akan lebih kompleks dibandingkan denganperalatan sampling klasik. Pada sisi rekonstruksi, solusi dari teknik CS tidaklahunik/tunggal. Dengan kata lain, setelah set solusi ditemukan, maka diperlukanoptimasi dengan suatu kriteria (biasanya adalah norm orde-n) dari set solusi yangada 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 untukmenjelaskan prinsip kerja dari compressive sensing. Tapi yang akan dibahas di siniadalah dengan menggunakan prinsip ketidakpastian (uncertainty principle atau UP).Prinsip ini menyatakan bahwa suatu sinyal tidak mungkin secara bersamaan dapatdilokalisasi dengan baik pada ranah waktu dan frekuensi. Dengan kata lain, jika suatusinyal terlokalisasi pada ranah waktu, maka sinyal tersebut tidak terlokalisasi padaranah frekuensi. Sebaliknya jika suatu sinyal terlokalisasi pada ranah frekuensi, makaia tidak terlokalisasi pada ranah waktu.

Jika suatu sinyal f tidak terlokalisasi pada suatu ranah, maka akan selalu dapatdicari suatu transformasi Ψ pada f untuk menghasilkan suatu sinyal textbfF yangbersifat 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<<N), dengan syaratM lebih besar dari suatu nilai yang diberikan oleh persamaan

M ≥ C ·µ2(Φ,Ψ) ·K · log(N) (II.7)

dimana K menyatakan tingkat sparsitas dari sinyal f, C adalah suatu konstanta(sekitar 2), dan µ(Φ,Psi) menyatakan fungsi pengukur tingkat koherensi dari Φ danΨ. Tingkat koherensi ini diberikan oleh

µ(Φ,Ψ) = maxφ3Φ,ψ3Ψ

|〈φ,ψ〉| (II.8)

Perkalian antara fungsi sparsitas Ψ dan fungsi sampling Φ dalam bentuk matriktersebut dapat dinyatakan sebagai matrik sensing A :

A= ΨΦ (II.9)

8

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 memilikiM buah persamaan (M <<N), maka penyelesaian II.10 membelikan banyak alternatifsolusi bagi f. Kondisi ini disebut sebagai ill-posed problem.

Agar solusi menjadi unik dan sama atau mendekati dari sinyal semula, makadilakukan optimasi dari solusi yang diperoleh. Optimasi yang umum dilakukan adalahdengan menggunakan optimisasi norm orde-n. Orde yang lazim dipakai dengan asumsisinyal 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 kedatangansinyal (Direction of Arrival Estimation - DoA), terdapat beberapa skema CS yang telahdilakukan pada penelitian terdahulu. Penerapan CS pada estimasi DoA secara umumterbagi ke dalam tiga skema : sparsitas waktu (Gurbuz dan McClellan (2008), Kimdkk. (2012)), sparsitas ruang (Wang dkk. (2009), Wang dkk. (2010)), and sparsitassudut (Gorodnitsky dan Rao (1997), Stoica dkk. (2011), Usman dkk. (2014)).

Sparsitas waktu mengambil asumsi bahwa sinyal yang dikirim adalah sinusoidal, olehkarena itu, sinyal terima bersifat sparse dalam waktu (atau frekuensi). Sinyal terimax yang dikumpulkan oleh M buah antena N dilakukan sampling pada ranah waktudengan teknik sampling klasik sebanyak N buah sampel untuk menghasilkan blok sinyalterima sebesar M kali N sinyal masukan. Dengan menggunakan pemrosesan blok,

9

setial blok sinyal terima ini dikalikan-sebelum (pre-multiplied) dengan sensing matrixA (berukuran M kali k, dengan k << N) untuk memperoleh sinyal keluaran y yangberdimensi M kali k, jauh lebih kecil dari pada ukuran sinyal masukkan semula x.Untuk proses estimasi arah kedatangan, sinyal yang telah dikompres ini kemudiandikembalikan ke sinyal semula sebelum algoritma DoA diterapkan.

Sparsitas ruang memiliki prinsip kerja yang mirip dengan sparsitas waktu. Jikasparsitas waktu mengasumsikan bahwa sinyal tersebut sparse dalam waktu, makasparsitas ruang mengasumsikan bahwa masing-masing antena pada susunan antenapenerima sebenarnya menerima sinyal yang sama dengan perbedaan hanya pada waktukedatangan (delay). Dengan demikian, sinyal terima diasumsikan bersifat sparse padaarah antena, atau ruang. Sinyal yang dikumpulkan oleh M buah antena, sepertihalnya pada sparsitas waktu, memiliki dimensi M kali N . Proses sensing dilakukandengan dengan mengalikan sinyal terima dengan sensing matrix A yang berdimensik kali N . Seperti halnya sparsitas waktu, sinyal semula perlu direkonstruksi ulangdengan sebelum estimasi arah kedatangan dapat dilakukan. Dibandingkan dengansparsitas waktu, skema sparsitas ruang memiliki kekurangan yaitu tingkat kompresiyang rendah, sedangkan kelebihannya adalah ketahanan sinyal terhadap derau lebihbaik, serta lebih mudah direalisasikan dalam bentuk perangkat keras, karena matriksensing A telah secara langsung memberikan arah panduan pada pembuatan perangkatkerasnya. Skema sistem penerima dengan sparsitas ruang dapat dilihat pada Wang dkk.(2009) dan Wang dkk. (2010).

Sparsitas sudut memiliki pendekatan yang berbeda dibandingkan dengan sparsitaswaktu dan sparsitas ruang sebelumnya. Skema sparsitas sudut tidak melakukankompresi pada arah waktu dan ruang. Skema ini mengasumsikan bahwa sinyal yangditerima berasal dari sejumlah sumber sinyal yang terbatas. Beberapa sumber sinyalini datang pada sudut-sudut yang berbeda. Berdasarkan pada anggapan ini, makakonstruksi permasalahan CS dilakukan dengan menggunakan sensing matrik A yangtersusun atas steering vector dari sinyal datang. Deskripsi matematis yang lebih rincidiberikan pada sub-bab berikutnya. CS formulasi dilakukan dengan menggabungkansensing matrix A, sparse vektor s, dan snapshot dari sinyal terima x. RekonstruksiCS 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, karenaskema ini memerlukan sangat sedikit sinyal terima, serta proses estimasi DoA dilakukanbersamaan dengan rekonstruksi CS. Dengan kata lain, penyelesaian CS pada sparsematrik s sekaligus juga adalah penyelesaian masalah estimasi arah kedatangan.Estimasi arah kedatangan sinyal diperoleh berdasarkan posisi element tak nol daridari matrik solusi sparse s (Gorodnitsky dan Rao (1997)).

Gambar II.2 mengilustrasikan proses penyusunan konstruksi CS teknik sparsitassudut.

a11

a21

aM1

a12

a22

aM2

a1p

a2p

aMp

As1

s2

s3

sp

x1i

x2i

x3i

xMi

s x

a(θ1) a(θ2) a(θM)

steering vectorat angle θi

Gambar II.2. Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steeringvector sudut-sudut yang dipindai

Meski pun memiliki keuntungan ini, skema sparsitas sudut memiliki kelemahan,yaitu kurang tahan terhadap derau lingkungan. Hal ini diverifikasi oleh Usmandkk. (2014). Pada penelitian tersebut, Usman dkk. (2014) mengusulkan peningkatanperforma sinyal dengan menggunakan teknik multi-snaps CS. Skema multi-snaps CSini 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 berkorespondensidengan hasil estimasi arah kedatangan pada setiap snap-shots. Estimasi DoAdilakukan dengan merata-ratakan nilai estimasi pada setiap snap-shots. Dengandemikian estimasi yang diperoleh menjadi lebih robust dibandingkan dengan hanyamenggunakan satu snap-shot.

Upaya untuk melakukan perbaikan skema sparsitas sudut dilakukan pula oleh Stoicadkk. (2011) secara terpisah. Skema yang diusulkan oleh Stoica dkk. (2011) diistilahkandengan independently covariance-based estimation technique (SPICE). Skema Stoicadkk. (2011) juga mengakomodasi kemampuan multi-snaps untuk meningkatkanketahanan terhadap noise.

11

Permasalahan lainnya dari sparsitas sudut adalah besarnya sensing matrix A.Sebagaimana yang telah dibahas sebelumnya, sensing matrix A disusun berdasarkansteering vector dari arah kedatangan yang dipindai. Pemindaian yang dilakukan padasemua arah kedatangan sinyal (dari−900 sampai 900) disebut dengan exhaustive search.Bab selanjutnya membahas dengan terperinci tentang exhaustive search tersebut sertaskema peningkatan yang diusulkan.

12

BAB III Metode yang diusulkan

III.1 Exhaustive Search

Exhaustive search adalah upaya untuk menemukan arah kedatangan sinyal denganmelakukan pemindaian pada semua arah kedatangan sinyal yang mungkin. Penelitisebelumnya melakukan pemindaian secara exhaustive ini. Pada makalahnya,Gorodnitsky dan Rao (1997) melakukan pemindaian pada semua sudut antara −900

sampai 900. Stoica dkk. (2011) melakukan pemindaian dari −900 sampai 900 denganresolusi 0.10, dengan demikian terdapat 1800 arah pindai yang berkorespondensidengan matriks sensing A yang berdimensi M kali 1800. Hal yang sama dilakukanoleh Usman dkk. (2014).

Gambar III.1 menunjukkan ilustrasi pemindaian dengan teknik exhaustive search.

objek

arahpemindaian

objek

-900900

00

Gambar III.1. Ilustrasi exhaustive search. Algoritma memindai pada semua arah untukmemperoleh arah sumber sinyal

Permasalahan yang dihadapi oleh teknik exhaustive search, seperti yang telahdikemukakan sebelumnya, adalah besarnya sensing matrix A. Sensing matriks yangbesar memerlukan proses komputasi rekonstruksi CS yang besar, sumber daya yangtinggi, serta waktu yang lama. Penyelesaian permasalahan ini diusulkan pada sub-babberikutnya yang membahas tentang pemindaian non-exhaustive search.

III.2 Non-exhaustive search

Kemajuan yang dicapai pada penelitian ini berkisar pada eksplorasi tekniknon-exhaustive search. Teknik ini adalah perbaikan dari teknik exhaustive searchberupa pengurangan rentang pemindaian dari semua sudut yang mungkin (tipikal

13

pada −900 sampai 900), ke dalam rentang yang lebih sempit. Tentu pemindaian padarentang yang lebih sempit ini dimungkinkan jika telah ada gambaran tentang arahsumber sinyal.

Untuk keperluan memperoleh gambaran tentang arah sumber sinyal tersebut,maka diperlukan suatu pemindaian kasar, misalnya dengan menggunakan estimasiDoA klasik (DAS, MVDR, MUSIC, atau ESPRIT). Setelah gambaran kasar arahkedatangan sinyal ini diperoleh, maka proses DoA selanjutnya dilanjutkan denganteknik CS dengan rentang sudut sempit, yang diperbarui setiap saat, sesuai denganarah gerakan objek. Skema pemindaian kasar sebelum teknik CS disebut dengan istilahpra-pemindaian.

Skema non-exhaustive search dengan pra-pemindaian selengkapnya diberikan padaGambar III.2.

Akuisisi

Pemindaian KasarPengaturan

CS

CS Solver

Snapshot Konstruksi

DoA

Sinyal

terima

JendelaPemindaian

Gambar III.2. Blok diagram skema non-exhaustive search dengan fungsi pemindaiankasar

Pada Gambar III.2 tersebut, sinyal mula-mula diakuisisi oleh sistem antenapenerima. Pada awal operasi, sinyal dimasukkan ke blok pemindaian kasar. Prosespada blok pemindaian kasar ini bertujuan untuk memperoleh gambaran umum tentangposisi sinyal. Blok pemindaian kasar ini dapat menggunakan salah satu algoritmaklasik, 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 DASmemiliki resolusi yang rendah.

Gambar III.3 menunjukkan ilustrasi skema non-exhaustive search. Pada gambartersebut, rentang sudut pemindaian dinyatakan sebagai jendela pindai (scanningwindow).

Tracking objek pada skema CS-DoA. Keuntungan utama pada skema yangditawarkan ini adalah penambahan kemampuan tracking terhadap gerakan objek

14

objek

objek

Scanning Window

θ1 θ2

Scanning Window

θ

Objek

(a) (b)

Gambar III.3. Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudutdalam koordinat polar (b). dalam koordinat kartesian

mudah untuk dilaksanakan. Hal ini dikarenakan sampling objek dapat dilakukanpada interval tertentu, dan pengambilan sampel sinyal yang sedikit setiap kalipengambilan. Jendela pemindaian (scanning window) dapat digeser-geser pada setiapiterasi menyesuaikan dengan dengan posisi objek.

Untuk melakukan update scanning window ini, maka diperlukan suatu skemaupdate. Pada penelitian ini, skema update dilakukan dengan terlebih dahulumenetapkan lebar scanning window (konstan). Pada setiap scanning, titik tengahdari scanning window diupdate sehingga berimpit atau mendekati lokasi dari posisiobjek (Gbr III.5).

Proses update dengan menjadikan lokasi objek sebagai median dari jendela pindaidapat 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 pindaihanya pada arah-arah tertentu saja. Namun pembatasan ini ternyata memberikanmasalah baru pada proses rekonstruksi CS, yaitu CS Solver yang dalam hal ini adalahcvx-programming, tidak berhasil memperoleh solusi yang konvergen. Fenomena initidak diperkirakan sebelumnya, karena dengan asumsi bahwa titik optimal dari CSsolver terletak pada lokasi sudut keberadaan sinyal, sedangkan sudut ini sendiri beradapada cakupan sudut yang dipindai. Namun ternyata, cvx-programming tidak berhasilmemperoleh solusi yang konvergen.

15

(b)

objek

(a)

objek

(c)

objek

W1W2

W3

θ

t1 t2 t3

(d)

objek objek objekP

Gambar III.4. Ilustrasi tracking object dengan teknik non-exhaustive search sertaupdate scanning window pada setiap waktu. (a),(b), dan (c) pergerakanobjek beserta update scanning window yang bersesuaian. (d). ilustrasipergeseran scanning window pada setiap waktu; W1, W2, W3 adalahscanning 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 skematerakhir adalah non-exhaustive search dengan lebar jendela 00 sampai dengan 900.Sebagai pembanding, posisi aktual dari objek diberikan. Objek tersebut bergerak darisudut 300 sampai dengan 900 dengan kecepatan 1,40 per detik. Sumbu datar adalahwaktu (dalam detik), dan sumbu tegak adalah sudut (dalam derajat). Pada gambarIII.6 tersebut skema exhaustive search dan skema non-exhaustive search dengan sudutpindai lebar (−300 sampai dengan 900) berhasil mengikuti pergerakan objek denganbaik. Namun untuk lebar jendela pindai yang terlalu kecil (00 sampai dengan 900),cvx-programming gagal memberikan hasil konvergen. Hasil yang diperoleh, iterasicvx-programming terjebak pada solusi semu di 50 dan 650.

Untuk mengatasi permasalahan ini, maka area pemindaian diperluas mencakup padaarah selain dari arah utama. Arah tambahan ini disebut dengan tail scanning. GambarIII.7 memperlihatkan ilustrasi tail-scanning.

Sifat dari tail scan adalah :

16

P

θθx1

P

θθx1

P

θθx2

P

θθx2

(a)

(b)

(c)

(d)

Gambar III.5. Ilustrasi detail tentang proses update scanning window denganmenggunakan median dari posisi objek. (a) hasil scanning kasar denganalgoritma klasik pada semua sudut,(b) penerapan scanning windowpada sudut yang dianggap memiliki objek, (c) objek bergerak sehinggapuncak scanning bergeser menuju batas window. (d). update scanningwindow, 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 terjebakpada solusi semu

Pada penelitian ini, diusulkan dua macam tipe tail scan yaitu uniform tail scan danrandom tail scan. Uniform tail scan adalah tail scan yang terpisah pada jarak yangseragam, sedangkan random tail scan adalah tail scan yang jarak antar pemindaiansatu dan lainnya terpisah. Gambar ?? menunjukkan ilustrasi uniform tail scan danrandom tail scan.

17

0

10

20

30

40

50

60

70

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

angl

e (

de

gre

e)

time(second)

w 0 to 90

w -30 to 90

w -90 to 90

Actual

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 permasalahanestimasi sudut dengan rekonstruksi sparse. Dua solver yang umum dipakai adalahCVX-programming dan l1-magic. CVX-programming dikembangkan oleh Boyd (2014),sedangkan l1-magic dikembangkan oleh oleh Romberg (2005). CVX-programmingbersifat umum dengan kemampuan melakukan optimasi pada berbagai permasalahanpemrograman linier (Linear Programming - LP). CVX-programming juga dapatmengoptimasi pilihan solusi dengan konstrain norm. Dengan demikian,

objek

-900900

00

Tail scan

Gambar III.7. Non exhaustive search dengan tail scanning

18

objek

-900900

00

Tail scan

objek

-900900

00

Tail scan

(a) (b)

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 padaCVX-programming antara lain adalah SDPT3 and SeDumi. Terdapat pula solver lainyang 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 cvxvariable 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 untuktracking objek yang bergerak.

2. Mengusulkan teknik tail scanning (uniform dan random tail scan)

3. Mensimulasikan teknik non-exhaustive search dengan tail scan, danmembandingkannya dengan teknik exhaustive search

4. mempublikasikan hasil-hasil yang diperoleh

IV.1.1 Simulasi teknik exhaustive dan non-exhaustive search

Simulasi komputer dilakukan untuk memverifikasi efektifitas skema non-exhaustivesearch yang diusulkan. Skema dari teknik non-exhaustive search ini adalah sepertipada Gambar III.2. Lingkungan simulasi diberikan pada Tabel IV.1

Tabel IV.1. Parameter simulasi exhaustive dan non exhaustive searchNo Skema Parameter Nilai1 Exhaustive Search Susunan Antena ULA 12 element

SNR 10 dBKecepatan Objek 1,40/s

Sudut jelajah objek 300 sampai 600

Resolusi pindai 10

Jumlah objek 12 Non Exhaustive Search Parameter dasar sama dengan

(Jumlah antena, dll.) exhaustive searchSkema pra-pemindaian MVDRLebar jendela pindai −300 sampai 900 dan

00 sampai 900

CS Solver CVX-programming

Hasil simulasi diperlihatkan pada Gambar III.6. Pada gambar tersebut, terlihatbahwa 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 exhaustivesearch. Permasalahan muncul ketika lebar jendela pindai dipersempit pada sudut 00

sampai 900. Pada rentang sudut pindai ini, rekonstruksi dengan cvx-programmingtidak berhasil memperoleh solusi yang konvergen. Iterasi cvx-programming terjebakpada dua nilai sudut estimasi salah yaitu 50 dan 650.

Oleh karena skema exhaustive search berhasil sedangkan teknik non-exhaustivesearch gagal untuk rentang sudut pindai yang sempit, maka kenyataan ini memberikaninspirasi untuk menambahkan pemindaian pada sudut-sudut tambahan di luar dariarah pindai utama. Pemindaian pada sudut-sudut tambahan ini diistilahkan dengantail scan.

IV.1.2 Mengusulkan teknik tail-scan (uniform dan randomtail scan)

Teknik tail scan muncul sebagai upaya untuk mengatasi permasalahanketidakkonvergen pada rekonstruksi CS untuk sudut pindai yang terlalu sempit.Sudut pindai yang terlalu sempit, berdasarkan simulasi yang dilakukan adalah sudutpindai kurang dari 900 (00 sampai 900).

Teknik tail-scan menambahkan pemindaian pada arah yang berada di luar dari sudutpindai utama. Sebagai mana yang telah dipaparkan pada Bab III, teknik tail scandiusulkan 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 detilparameter simulasi adalah seperti pada Tabel IV.1. Lebar jendela pindai arah utamaadalah 00 sampai dengan 900. Sedangkan tail scan dilakukan secara random danuniform pada 20 arah pindai yang berbeda. Hasil simulasi adalah seperti yangditunjukkan pada Gambar IV.1.

Pada Gambar IV.1 tersebut, terlihat bahwa performa non-exhaustive searchmeningkat dibandingkan dengan tanpa tail scan. Teknik non-exhaustive search dapatmen-tracking objek dengan baik. Rekonstruksi CS tidak lagi terjebak pada solusi semu.Kelemahan yang masih terlihat adalah masih terjadi kesalahan deteksi sudut padaiterasi 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 inidengan interpolasi nilai pada titik-titik di antaranya.

Setelah berhasil memperbaiki performansi non-exhaustive search dengan teknik tailscan, percobaan berikutnya adalah mempersempit lebih lanjut lebar dari jendela pindaiutama. Pada percobaan sebelumnya, jendela pindai utama adalah dari 00 sampaidengan 900. Selanjutnya, lebar jendela pindai utama ini dipersempit dari 300 sampai

21

-100

-80

-60

-40

-20

0

20

40

60

80

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

angl

e (

de

gre

e)

time

UniTail

RNDTail

Actual

Gambar IV.1. Hasil simulasi non-exhaustive search dengan uniform dan random tailscan. Sudut aktual objek diberikan sebagai pembanding

dengan 900. Tail scan dilakukan dengan cara yang sama yaitu secara uniform danrandom dengan 20 arah berbeda. Nilai-nilai yang menyimpang dibuang dan digantidengan interpolasi dari nilai yang mengapitnya. Hasil simulasi dapat dilihat padaGambar IV.2.

Untuk mengetahui lebih lanjut dampak dari tail scan, pada percobaan berikutnyadilakukan 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 diperolehdipublikasikan pada konfrensi internasional. Konfrensi yang dipilih adalahAPWIMob2015 (IEEE Asia Pacific Conference on Wireless and Mobile 2015). Juduldari publikasi ini adalah : Uniform Non Exhaustive Sparse Reconstruction for Directionof Arrival Estimation. Publikasi ini telah dikirimkan kepada panitia seminar pada dddMei 2015, dan saat ini sedang melalui proses review. Pemberitahuan penerimaan pada27 Juni 2015.

Isi publikasi selengkapnya diberikan pada Lampiran A, dan informasi selengkapnya

22

0

10

20

30

40

50

60

70

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

angl

e (

de

gre

e)

time(second)

exhaustive search

Actual

random tail scan

uniform tail scan

Gambar IV.2. Hasil simulasi non-exhaustive search dengan uniform dan random tailscan dengan sudut pindai utama dipersempit ke 300 sampai 600. Sudutaktual objek diberikan sebagai pembanding, estimasi yang menyimpangdiganti 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 CompressiveSensing dengan sparsitas sudut sebagai fokus dari penelitian. Transformasi unitaryyang mengubah matrik kovariansi dari kompleks menjadi riil diusulkan sebagai bagiandari proses untuk mempercepat komputasi. Pada Kemajuan I juga muncul ide untukmempercepat proses rekonstruksi CS dengan memanfaatkan teknik non-exhaustivesearch. Ide tersebut direncanakan dilaksanakan pada Kemajuan II ini. Pada KemajuanII ini, skema non-exhaustive search tersebut disimulasikan dan diteliti secara lebihmendalam. Hasil yang diperoleh adalah skema non-exhaustive search tersebut bekerjabaik jika lebar jendela pindai cukup lebar, dan tidak berhasil jika lebar jendela pindaisempit. Pada Kemajuan II ini juga diusulkan teknik baru yaitu tail scan untukmengatasi masalah itu. Teknik ini juga disimulasikan dan memberikan hasil yangbaik. Tabel IV.2 memperlihatkan perbandingan antara Kemajuan I dan Kemajuan II.

23

0

5

10

15

20

25

30

35

40

45

50

3 6 9 12 15 18 21 24 27 30

uniform tail

random tail

without tail

Gambar IV.3. Hasil simulasi non-exhaustive search dengan uniform dan random tailscan dengan sudut pindai utama dipersempit ke 300 sampai 600. Sudutaktual objek diberikan sebagai pembanding, estimasi yang menyimpangdiganti dengan interpolasi dari nilai yang mengapitnya

Tabel IV.2. Perbandingan Kemajuan I dan Kemajuan IINo Kemajuan Hasil Keterangan1 Kemajuan I Fokus Penelitian CS-DoA dengan sparsitas sudut

Usulan Penggunaan Unitary Transformuntuk konversi matrikskovariansi kompleks ke riil

Publikasi Poster pada ICODSE2014Usulan selanjutnya Teknik non-exhaustive search

2 Kemajuan II Fokus Penelitian CS-DoA dengan sparsitas sudutUsulan dan simulasi non-exhaustive search

random dan uniform tail scantracking objek dengan CS-DoA

Publikasi IEEE APWIMob2015 conferenceUsulan selanjutnya memperdalam tail-scan

basis matematis tail-scan

24

BAB V Penutup

Pada Kemajuan II ini, telah dilaporkan mengenai penjelasan tentang topik penelitianserta hasil-hasil yang dicapai sampai sejauh ini. Beberapa hasil simulasi dan idebaru yang dicapai pada Kemajuan II membuka peluang untuk suatu kontribusi nyatadalam algoritma CS-DoA berbasis sparsitas sudut dengan teknik non-exhaustive searchdengan tail-scan. Teknik ini, sejauh yang telah diteliti pada literatur, belum pernahdilakukan oleh peneliti lain sebelumnya. Rencana ke depan adalah memperdalamteknik tail scan ini baik secara simulasi mau pun secara teori. Penjelasan matematikdari teknik tail scan ini memerlukan pemahaman mendalam tentang prinsip kerjaCVX Programming. Oleh karena itu, studi literatur tentang CVX programmingakan diprioritaskan pada kemajuan berikutnya. Keberhasilan pemahaman landasanmatematik serta simulasi CVX programming diharapkan memberikan kontribusisignifikan 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, URLhttp://cvxr.com/cvx/.

Candes, E. dan Wakin, M. B. (2006): Compressive Sampling, Proceedings of theInternational 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 byBasis 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-ValuedSparse Representation, Antennas and Wireless Propagation Letters, IEEE, 12,376–379.

Dmochowski, J., Benesty, J., dan Affes, S. (2007): Direction of Arrival EstimationUsing the Parameterized Spatial Correlation Matrix, Audio, Speech, andLanguage Processing, IEEE Transactions on, 15(4), 1327–1339.

Donoho, D. L. (2006): Compressed Sensing, IEEE Transactions on InformationTheory, 52(4).

Gorodnitsky, I. F. dan Rao, B. D. (1997): Sparse Signal Reconstruction fromLimited Data Using FOCUSS: A Re-weighted Minimum Norm Algorithm, IEEETransactions 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 SignalProcessing.

Hayasi, K., Nagahara, M., dan Tanaka, T. (2013): A UserŠs Guide to CompressiveSensing 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 compressivearrays, Antennas and Propagation (APSURSI), 2011 IEEE InternationalSymposium on, 2016–2019.

Kim, J. M., Lee, O. K., dan Ye, J. C. (2012): Compressive MUSIC: Revisiting the LinkBetween Compressive Sensing and Array Signal Processing, IEEE Transctions onInformation 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 ofCompressive 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 viaRotational Invariance Techniques Ű ESPRIT., Proceeding of IEEE MilitaryCommunications (MILCOM) Conference - Communications, 3.

Schmidt, R. (1986): Multiple emitter location and signal parameter estimation, IEEETransactions on Antennas and Propagation, 34(3), 276–280.

Stoica, P., Babu, P., dan Li, J. (2011): SPICE: A Sparse Covariance-Based EstimationMethod for Array Processing, Signal Processing, IEEE Transactions on, 59(2),629–638.

Swastika, W. dan Haneishi, H. (2012): Compressed Sensing for Thoracic MRIwith Partial Random Circulant Matrices, TELKOMNIKA, Vol.10, No.1, March2012, 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 SkemaEstimasi Arah Kedatangan Sinyal dengan Compressive Sensing Sparsitas Sudutdan Sampel Multisnap, Inkom Journal, 8(1), 21–27.

Veen, B. V. dan Buckley, K. M. (1988): Beamforming: A Versatile Approach to SpatialFiltering, IEEE ASSP Magazine.

27

Wahidah, I. dan Suksmono, A. B. (2010): RECONSTRUCTION ALGORITHMS FORCOMPRESSIVE VIDEO SENSING USING BASIS PURSUIT, Proceeding of the6th International Conference on Information & Communication Technology andSystems.

Wang, Y., Leus, G., dan Pandharipande, A. (2009): Direction Estimation UsingCompressive Sampling Array Processing, Proceeding of IEEE SSP.

Wang, Y., Pandharipande, A., dan Leus, G. (2010): Compressive sampling basedMVDR spectrum sensing, Proceeding of IAPR.

28