a multifrequency mac specially designed for wireless sensor web viewcontoh aplikasi terakhir yang...

ESTIMASI ARAH KEDATANGAN: DARI DELAY AND SUM SAMPAI COMPRESSIVE SENSING

KOREDIANTO USMAN, INSTITUT TEKNOLOGI BANDUNGANDRIYAN BAYU SUKSMONO, INSTITUT TEKNOLOGI BANDUNG

Penentuan arah kedatangan sinyal adalah salah satu aplikasi yang penting pada bidang radar dan sonar. Contoh aplikasi terakhir yang dari teknik ini adalah pada bidang behind the wall radar dan ground penetrating radar. Algoritma penentuan arah sinyal ini secara umum terdiri dari dua skema besar yaitu skema yang berbasis maximum likelihood (Delay and Sum dan Capon) dan skema berbasis sub-space (MUSIC dan ESPRIT). Pada perkembangannya, algoritma yang berbasis sub-space memperoleh perhatian yang besar di kalangan peneliti karena memiliki kemampuan mendeteksi beberapa sumber sekaligus dengan resolusi pemisahan yang tinggi. Meski ada keunggulan ini, algoritma estimasi arah kedatangan berbasis sub-space memiliki permasalahan komputasi berat yang antara lain disebabkan karena proses perhitungan matriks kovariansi dan analisis nilai eigen dan vektor eigen. Evolusi dan modifikasi pada algoritma berbasis sub-space umumnya berupa modifikasi pada penyederhanaan komputasi untuk menghitung nilai eigen dan vektor eigen ini. Modifikasi ini kemudian menjadi algoritma varian seperti Root-MUSIC, Unitary-MUSIC, Beamspace-MUSIC, Unitary-ESPRIT, dan Beamspace-ESPRIT. Di sisi lain, perkembangan pada bidang compressive sensing membuka arah baru pada penyederhanaan yaitu dengan cara pengurangan sampel. Beberapa algoritma compressive sensing populer saat ini antara lain adalah l1 optimization, Greedy, dan Pseudo Inverse. Paper ini bertujuan untuk memaparkan perkembangan algoritma estimasi sudut kedatangan mulai dari algoritma klasik, modifikasinya, sampai dengan peran compressive sensing untuk pengurangan sampel. Ada pun kontribusi penulis pada paper ini disamping pemaparan evolusi teknik estimasi arah kedatangan sinyal juga menunjukkan dengan simulasi permasalahan yang masih ada pada teknik compressive sensing untuk bidang ini.

Categories and Subject Descriptors: Antenna Array Signal ProcessingGeneral Terms: Direction of Arrival Estimation, Signal Resolution, Delay and Sum, Minimum Variance Distortionless Response, MUSIC, Root-MUSIC, ESPRIT, Unitary ESPRIT.Additional Key Words and Phrases: Angle Scanning, Subspace Method, Covariance Matrix, Eigen-Value Decomposition

1. PENDAHULUANTeknik estimasi arah kedatangan sinyal merupakan salah satu tugas yang dikerjakan radar disamping dua tugas lainnya yaitu estimasi jarak dan kecepatan objek. Dengan demikian teknik estimasi arah kedatangan memiliki usia setua usia radar. Pada perkembangannya, radar mula-mula dikembangkan pada kapal laut untuk keperluan mendeteksi objek penghalang di depan kapal termasuk keberadaan kapal lain yang ada di sekitar. Pada masa perang dunia I dan II, radar berkembang sangat pesat untuk kebutuhan pertahanan. Setelah perang dunia II, perkembangan radar diarahkan untuk memenuhi kebutuhan sipil seperti kelengkapan sistim monitor udara di bandara.Memasuki era digital, teknik pengolahan sinyal berubah dari analog menjadi digital. Pada masa ini berkembang teknik estimasi arah kedatangan yang Alamat Penulis: Koredianto Usman and Andriyan B. Suksmono, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung, Laboratorium Telematika Radio dan Gelombang Mikro, Jl. Ganesha No.10 Bandung, Indonesia 40132.

Survey Paper : Maret 2014

2 K. Usman and A.B. Suksmono

maju yang membuka jalan bagi berbagai perkembangan teknologi radar canggih pada masa kini. Paper ini berupaya untuk memberikan gambaran umum tentang perkembangan algoritma estimasi arah kedatangan berikut permasalahannya serta potensi peran compressive sensing pada bidang ini.Sistematika penulisan paper ini adalah sebagai berikut: Bagian 2 me-review tentang algoritma-algoritma klasik estimasi arah kedatangan sinyal beserta permasalahannya. Bagian 3 me-review tentang teori compressive sensing. Bagian 4 adalah pembahasan pada skema-skema penerapan compressive sensing pada estimasi arah kedatangan yang telah dilakukan. Bagian 5 mengilustrasikan permasalahan yang masih terdapat pada penggunaan compressive sensing pada estimasi arah kedatangan. Bagian 6 adalah proyeksi arah penelitian ke depan sekaligus menutup paparan pada paper ini.

NotasiUntuk kepentingan keseragaman notasi, maka disepanjang tulisan ini, digunakan notasi-notasi berikut:A* : menyatakan kompleks konjugate dari matriks AAT : menyatakan transpose dari matriks A.AH : menyatakan transpose hermition dari matriks A (operasi transpose kemudian dilakukan operasi kompleks conjugate)A-1 : Menyatakan inverse dari matriks AA+ : menyatakan pseudo inverse dari matriks A.sup(A) : menyatakan support dari matriks A (indeks pada posisi tak nol)diag(A) : vektor yang berisi elemen diagonal dari matriks persegi A

2. ESTIMASI ARAH KEDATANGAN SINYAL2.1Deskripsi permasalahan estimasi arah kedatangan sinyalPermasalahan pada estimasi arah kedatangan sinyal adalah: diberikan sinyal terima yang berasal dari satu atau lebih sinyal datang, bagaimana cara agar arah kedatangan sinyal dapat diketahui. Untuk memulai deskripsi penyelesaikan masalah ini, maka terlebih dahulu kita modelkan situasi estimasi arah kedatangan dalam model matematika.

2.2Model MatematikaAlgoritma estimasi arah kedatangan sinyal diturunkan dari model

matematik dilanjutkan dengan penyederhanaan-penyederhaannya. Untuk keperluan pemodelan ini, ditinjau skema susunan array antena yang tersusun secara linier dengan jarak konstan seperti pada Gambar 1. Susunan antena ini disebut dengan Uniform Linear Array (ULA).

Dengan asumsi bahwa sinyal datang pada jarak yang yang relatif jauh maka berkas sinyal yang datang pada susunan antena tersebut dapat dianggap sejajar. Dengan menganggap sinyal paling atas sebagai referensi, maka perbedaan jarak tempuh gelombang dari antena yang atas dengan antena tengah dan antara antena yang tengah dengan yang bawah adalah sebesar:

Estimasi Arah Kedatangan Sinyal : dari Capon’s sampai Compressive Sensing 3

Δ=d⋅sin (θ ) (1)

Gambar. 1. Susunan Antena ULA dengan 3 elemen antena

Perbedaan jarak ini menyebabkan keterlambatan fasa dari antena yang bawah dibandingkan dengan antena atas sebesar:

ψ= Δλ⋅2π=

d⋅sin (θ )λ

⋅2 π=2 πλ

⋅d⋅sin (θ ) (2)

Dengan menotasikan sinyal sumber sebagai s(n) dan sinyal yang datang pada antena berturut-turut sebagai x1(n), x2(n) dan x3(n) , maka persamaan vektor sinyal datang x(n) dapat ditulis dalam vektor menjadi:

x (n)=[ x1(n )x2(n )x3(n )]=[ s (n)⋅1

s(n )⋅e− jΔ

s (n)⋅e− j2 Δ]=[ 1

e− j 2 π

λ⋅d⋅sin (θ )

e− j 2⋅2 π

λ⋅d⋅sin ( θ )]⋅s(n )

(3)

Persamaan di atas disingkat menjadi:

x (n)=a (θ )⋅s (n) (4)

Dengan a() disebut sebagai steering-vector. Jika jumlah antena digeneralisasi menjadi M, maka steering-vector a() dapat ditulis sebagai:

d

d


a (θ )=[1

e− j⋅2π

λ⋅d⋅sin (θ )

e− j⋅2⋅2 π

λ⋅d⋅sin ( θ )

⋮

e− j ( M−1 )⋅2π

λ⋅d⋅sin (θ )]

(5)Pada kondisi terdapat beberapa sumber yang datang (k), maka persamaan sinyal sumber juga dapat digeneralisasi menjadi:

s(n )=[ s1(n) s2(n ) … sk(n ) ]T (6)

2.3 Algoritma Klasik Estimasi arah Kedatangan

2.3.1 Algoritma Delay-and-SumAlgoritma estimasi arah kedatangan dengan metode delay-and-sum ini termasuk algoritma klasik dan menjadi acuan bagi perkembangan skema estimasi arah kedatangan. Metode ini dimodelkan pertama kali oleh Sidney P. Applebaum [Applebaum 1976]. Van Veen [Van Veen 1988] memformulasikan kembali skema delay-and-sum ini dalam kajiannya tentang versatile adaptive beamformer.

Struktur dari algoritma Delay and sum dapat dilihat pada Gambar 2.

Gambar. 2. Skema delay-and-sum. Pada gambar di atas terdapat tiga tap delay dengan bobot w1, w2, dan w3. Pada N-tap delay, terdapat N buat tap dengan N buah bobot.

Untuk skema sum-and-delay, estimasi arah kedatangan dilakukan dengan scanning semua bobot yang mungkin pada rentang sudut tertentu, tipikalnya adalah dari -180 sampai 180 derajat.

Spektrum amplitudo sebagai fungsi sudut scanning dapat dituliskan sebagai:

V(n)

+

w3

w2

w1


P(w )=∑n=1

L

wi⋅xi (n)

(7)

Arah kedatangan sinyal adalah pada i pada nilai w yang menyebabkan P(w)

bernilai maksimum.

arg (θ )⃗max (P(w )) P(w )=∑n=1

L

wi⋅xi (n)

(8)

Nilai x(n) adalah vektor sinyal terima yang dinyatakan pada Persamaan 4.

Skema Delay and Sum ini memiliki keuntungan dalam hal kesederhanaan. Karena kesederhanaan ini, skema Delay and Sum sering menjadi pilihan implementasi untuk berbagai aplikasi, baik radio [Peng Chen, 2008] maupun audio [Yuan Zeng, 2014]. Walau pun memiliki keuntungan pada sisi kesederhanaannya, algoritma ini memiliki beberapa kelemahan. Kelemahan ini antara lain adalah rendahnya kemampuan resolusi sinyal, dengan kata lain algoritma tidak dapat mendeteksi adanya dua sinyal yang memiliki arah kedatangan yang berdekatan. Kelemahan lainnya adalah sensitifitas sinyal terhadap noise dan interferensi [Cox, 1987]

2.3.2 Algoritma CaponCapon menawarkan skema estimasi arah kedatangan yang berbeda

dibandingkan dengan skema Delay and Sum [Capon, 1969]. Perbedaan ini antara lain pada sisi pengolahan sinyal yang diterima dan dari segi persamaan spektrum sinyal. Algoritma Capon disebut juga dengan algoritma Minimum Variance Distortionless Response (MVDR). Kemampuan resolusi yang lebih baik dari pada algoritma Delay and Sum disebabkan karena spektrum sinyal diperoleh dari inverse dari covariance matrix.

Algoritma Capon dapat dituliskan sebagai berikut:s1 : hitung matriks estimasi kovariansi Rxx dari vektor sinyal datang x(n)

Rxx=E (x (n )⋅x (n )H )= 1N

⋅x (n)⋅x( n)H

(9)s2 : hitung matriks invers dari covariance matrix Rxx s3 : bangkitkan steering vektor a() seperti Persamaan 5.s4 :Hitung spektrum sinyal P() untuk setiap nilai dari 0 sampai 360 derajat

dengan persamaan


P(θ )= 1a(θ )H⋅Rxx

−1⋅a (θ)

(10)s5 : Tentukan arah kedatangan dengan menentukan nilai pada saat P()

bernilai maksimal (atau lokal maksimal jika terdapat beberapa sumber sinyal sekaligus).

Dari sisi performa, para peneliti menemukan dua kekurangan utama dari algoritma Capon yaitu:

1. komputasi yang berat2. rentan terhadap interferensi dari jammer yang berkorelasi dengan

sinyal.Komputasi yang berat terkait dengan proses perhitungan matriks kovariansi kompleks dengan kompleksitisnya adalah pangkat tiga (O(n3)). Kompleksitas lainnya disumbang oleh proses inversi dari matriks kovariansi [Golub, 1990].Ada pun pengaruh interferensi terhadap algoritma Capon diteliti oleh Michael Zoltowski [Zoltowski, 1988]. Pada paper tersebut, Zoltowski menunjukkan sensitifitas dari algoritma MVDR Beamforming pada kasus multiple interference. Performa sistem menurun dengan drastis pada kondisi interferensi tersebut.Upaya lain untuk penyederhanaan perhitungan adalah pengelompokan array antena ke dalam sub-array [Bezanson 2013]. Peningkatan performa algoritma Capon dilakukan juga oleh Zoltowski pada papernya tahun 1988 di atas. Ia menemukan bahwa penambahkan algoritma Total Least Square (TLS) menurunkan permasalahan sensitifitas algoritma ini terhadap terhadap interference walau pun hal tersebut harus dibayar dengan tambahan kompleksitas dan komputasi ekstra.

2.3.3 Algoritma MUSICAlgoritma MUSIC diusulkan oleh Ralph O. Schmidt [Schmidt, 1986]. Walau pun diterbitkan di IEEE transactions tahun 1986, skema dasarnya ini telah dipublikasikan oleh Schmidt pada beberapa lebih awal (1977-1979) di beberapa publikasi. Algoritma MUSIC adalah salah satu algoritma breakthrough di bidang beamforming. Algoritma ini termasuk yang paling banyak diteliti dan dikembangkan oleh para peneliti selama beberapa dekade. Keberhasilan algoritma ini dalam mendeteksi beberapa sumber sekaligus dengan resolusi yang sangat tinggi menjadi daya tarik utama dari algoritma ini. Algoritma MUSIC termasuk pelopor dalam penggunaan eigen-analysis sehingga sering disebut eigen-assisted based algorithm.Berikut ini adalah tahapan-tahapan pada algoritma MUSIC.

s1 : hitung matriks estimasi kovariansi Rxx dari vektor sinyal datang x(n)

s2 : Hitung dekomposisi Eigen dari Rxx

Rxx=U⋅Σ⋅U H

(11)


U menyatakan matriks eigen vektor dari Rxx dan menyatakan matriks diagonal dengan elemen diagonal adalah eigen-value dari matrix Rxx.

s3 : Identifikasi nilai eigen dominal pada (k buah) dan nilai eigen tak dominan (L-k buah), L adalah jumlah antena dalam array. Selanjutnya matriks eigen vektor U dipartisi menjadi dua bagian k kolom dan L-k kolom sesuai dengan pembagian nilai eigen domin dan tak dominan. Eigen-vektor bagian k kolom disebut signal sub-space Us dan kolom L-k disebut noise sub-space Un. Dengan demikian dapat vektor eigen U dapat ditulis menjadi:

U = [Us Un] (12)

s4 : bangkitkan steering vektor a() seperti Persamaan 5 untuk suatu sudut .

s5 : hitung spektrum sinyal P() untuk setiap nilai dari 0 sampai 360 derajat dengan persamaan

P(θ )= 1a(θ )H⋅U n⋅a(θ )

(13)S6 : Tentukan arah kedatangan arah kedatangan sinyal diperoleh pada saat

nilai P() bernilai maksimal (atau lokal maksimal jika terdapat beberapa sumber).

Spektrum sinyal pada algoritma MUSIC seperti pada persamaan (13) akan bernilai maksimum ketika penyebutnya bernilai nol atau mendekati nol. Kondisi ini tercapai jika steering vector a() tegak lurus dengan noise subspace Us. Kondisi ini tercapai jika steering vector adalah kombinasi linier dari signal subspace.Analisis performa algoritma MUSIC telah banyak dilakukan oleh para peneliti [Kaveh 1986, Stoica, 1989]. Mostofa Kaveh melakukan pengujian performa algoritma MUSIC dengan parameter kemampuan resolusi MUSIC dengan dua sinyal datang pada lingkungan yang ber-noise. Hasil simulasinya menunjukkan bahwa algoritma MUSIC memiliki performa yang sangat baik pada SNR yang lebih dari 10 dB. Pada SNR kurang dari 0 dB, performa sistem buruk karena kegagalan sistem dalam membedakan sinyal dan noise. Petre Stoica melakukan pengujian performansi algoritma MUSIC dengan menghitung jaraknya dengan batas minimum yang dapat dicapai dari suatu nilai estimasi yaitu Cramer-Rao Bound (CRB). Penelitiannya menunjukkan bahwa Algoritma MUSIC memiliki performa yang hampir berimpit dengan untuk SNR yang tinggi.Kekurangannya utama dari algoritma MUSIC adalah proses perhitungan yang berat. Kompleksitas perhitungan ini disebabkan oleh tiga proses pada algoritma MUSIC yaitu perhitungan matriks kovariansi, eigen-analysis, dan exhaustive search. Keterbatasan ini menyebabkan algoritma MUSIC sangat jarang diterapkan pada aplikasi realtime [Golub 1990, Van Veen 1989, dan Xu 1994]. Algoritma turunan MUSIC pada umumnya ditujukan untuk mengurangi perhitungan eigen-analysis. Algoritma turunan ini antara lain adalah Root-MUSIC [Barabell 1983], Beamspace Root-MUSIC [Zoltowski 1992] dan Unitary Root MUSIC [Pasevento 2000].


2.3.4 Algoritma ESPRITSkema ESPRIT diperkenalkan oleh Roy, Paulraj, dan Kailath [Roy et al. 1986]. Skema ini mengambil pendekatan berbeda jika dibandingkan dengan tiga algoritma sebelumnya. Jika algoritma sebelumnya arah kedatangan dihitung secara exhaustive search pada semua kemungkinan sudut datang maka algoritma ESPRIT tidak melakukan scanning sudut, melainkan memanfaatkan sifat rotational invariant dari susunan antena. Sifat rotational invariant memerlukan susunan array antena yang dapat dibagi menjadi 2 sub-array yang salah satu sub-array adalah versi tergeser spasial dari sub-array lainnya. Gambar 3 memperlihatkan contoh susunan array dan pengelompokannya ke dalam dua sub-array yang memenuhi sifat sifat ini.

Gambar 3 : Struktur array antena yang dapat dibagi menjadi 2 sub-array dengan salah satu sub-array adalah versi tergeser linier dari sub-array lainnya.

Pergesaran linier secara spasial ini menghasilkan persamaan sinyal terima antara sub-array pertama dan sub-array kedua terhubung secara matematis melalui persamaan eksponensial kompleks yang berasosiasi dengan rotasi pada lingkaran satuan.

Dengan memanfaatkan sifat ini, estimasi arah kedatangan sinyal dapat dihitung secara rumus tanpa perlu menggunakan scanning sudut. Urutan estimasi arah kedatangan sinyal dengan algoritma ESPRIT dapat dirangkum dalam langkah-langkah berikut (langkah s1 sampai s3 adalah sama dengan langkah pada algoritma MUSIC):


s2 : Hitung dekomposisi Eigen dari Rxx : Rxx=U⋅Σ⋅U H

s3 : Partisi vektor eigen U menjadi sinyal sub-space Us dan noise sub-space Un. s4 : Hitung sinyal subspace dari sub-array-1 dan sub-array-2 masing-masing

dengan selection vector J1 dan J2. U s1=J 1⋅U s

(14.a)

U s2=J 2⋅U s(14.a)

s5 : hitung matrix rotational invariant :

4

3

2

1

(b)

J2

J1

4

3

2

1

J2

J1

(a)


Ψ =U s 1+ ⋅U s2=(U s 1

H⋅U s1 )−1⋅U s 1

H⋅U s2 (15)

s6 : Hitung nilai Eigen dari matriks rotational invariant s7 : Sudut kedatangan dihitung dengan persamaan:

θi= tan−1( im( λi )re ( λi ) )

(16)

Variabel i menyatakan nilai eigen dominan ke-i dari matrik , sedangkan operator im(.) dan re(.) berturut-turut menyatakan bagian imaginer dan real dari bilang kompleks.

Permasalahan pada algoritma ESPRIT adalah penambahan langkah perhitungan inverse matriks dan perhitungan nilai eigen menyebabkan pada bagian ini algoritma ESPRIT bekerja lebih berat dari pada algoritma MUSIC. Namun ketiadaan perhitungan exhaustive search untuk semua arah kedatangan menyebabkan algoritma ESPRIT secara keseluruhan lebih cepat dari pada algoritma MUSIC.

Perbaikan algoritma ESPRIT banyak dilakukan oleh para peneliti. Sebagian besar modifikasi tersebut ditujukan untuk mengurangi atau menghindari perhitungan eigen-analysis yang biasanya melibatkan perhitungan bilangan kompleks dalam dimensi yang besar. Upaya perbaikan ini antara lain dimunculkan dalam skema Beamspace ESPRIT [Xu 1994] dan Unitary ESPRIT [Haardt 1995].

2.4. Perbandingan Algoritma Klasik

Dari algoritma yang disebutkan sebelumnya, terdapat kekurangan dan kelebihan dari masing-masing algoritma utama dari DoA. Tabel 1 merangkum perbandingan dari algoritma-algoritma yang dibicarakan sejauh ini.

Table I. Perbandingan Algoritma utama DoA Parameter Komparasi

AlgoritmaDelay and Sum Capon MUSIC ESPRIT

Metode Exhaustive Search

Exhaustive Search

Exhaustive Search

Rotational Invariant

Perhitungan penjumlahan dan perkalian

Covariance Matrix dan Inversi Matrix

Covariance Matrix, Eigen-analysis

Covariance Matrix, Inversi, dan Eigen Analysis,

Tipe Hasil perhitungan

estimasi Spektrum Sinyal



estimasi Sudut Kedatangan

Kompleksitas rendah sedang-tinggi tinggi sedangJumlah Elemen Antena

N N N 2N

Jumlah Sinyal yang dapat dideteksi

variabel, tergantung tingkat korelasi

N-1 N-1 N-1


sinyalResolusi Rendah Sedang-Tinggi Tinggi Sedang

Tabel II memperlihatkan modifikasi dari algoritma klasik untuk mempercepat perhitungan.

Table II. Modifikasi dan Variasi AlgoritmaAlgoritma

Delay and Sum

Capon MUSIC ESPRIT

Variasi Algoritma

- iterative-MVDR Root-MUSIC, Unitary MUSIC, Beamspace MUSIC

Unitary-ESPRIT, Beamspace ESPRIT

3. COMPRESSIVE SENSINGTeori sampling klasik dikembangkan oleh Harry Nyquist [Nyquist

1928], yang kemudian dikembangkan oleh Claude Shannon dalam paper klasiknya [Shannon 1948]. Berkat analisis Nyquist di bidang transmisi sinyal telegraph serta penurunan matematis oleh Shannon, ditemukan teorema sampling yang dipakai hingga saat ini yang menyatakan bahwa untuk dapat dilakukan rekonstruksi sempurna, maka proses digitalisasi sinyal memerlukan frekuensi sampling minimal sebesar dua kali dari frekuensi tertinggi dari sinyal informasi yang disampling.

FSM = 2 x fmax (17)

Dengan FSM adalah frekuensi sampling minimum, dan fmax adalah frekuensi sinyal informasi. Persamaan (17) dikenal dengan persamaan Nyquist-Shannon. Persamaan ini dipatuhi oleh berbagai sistem digital saat ini seperti frekuensi sampling sinyal suara adalah 8.000 Hz (dengan frekuensi suara manusia tertinggi adalah 3.400 Hz).

Compressive sensing adalah salah satu cabang ilmu baru yang dikembangkan oleh para peneliti bidang matematika khususnya statistik. Publikasi awal di bidang ini antara lain adalah David L Donoho [Donoho 2006] dan Emmanuel Candes [Candes 2007]. Aspek teknis dan aplikasinya banyak diteliti dan dikembangkan oleh Richard Baraniuk [Baraniuk 2007]. Mengingat penelitian compressive sensing tersebar di berbagai bidang, beberapa peneliti merangkum perkembangan dan potensi compressive sensing dalam survey paper, antara lain oleh Thomas Stromer [Stromer 2012] dan pada bidang sistem komunikasi oleh Kashunori Hayashi [Hayashi et. al 2013].

3.1.Model Matematik dan AsumsiPemodelan matematik dari compressive sensing memerlukan beberapa asumsi dan pra-syarat terminologi antara lain adalah norm dan sparsity. 3.1.1 Norm lp

Estimasi Arah Kedatangan Sinyal : dari Capon’s sampai Compressive Sensing 11 Jika x(n) menyatakan sinyal pengamatan pada waktu n dari 1 sampai N dengan interval bilangan bulat, x(n) = [x1, x2, ..., xN]T, maka norm orde-p dengan p non-negatif dari x(n) dinyatakan dengan:

‖x (n )‖p=(∑i=1

N

|x i|p)

1/ p

(18)

Simbol |.| menyatakan nilai absolut dari nilai yang terletak di dalam simbol tersebut. Khusus untuk p bernilai 1 dan 2, maka normnya menjadi:

(19.a)

(19.b)

Persamaan (19.a) menyatakan norm orde satu atau dikenal dengan istilah Manhattan Distance, sedangkan norm orde dua dikenal dengan istilah Euclidean Distance. Untuk p bernilai 0, maka norm dari x(n) menyatakan jumlah elemen tak nol dari x(n), dan disebut juga sebagai support dari vektor x(n).

(19.c)

(20)

3.1.2 SparsitySuatu sinyal x(n) dikatakan sparse jika sebagian besar dari elemen pada x(n)

bernilai nol. Dengan kata lain ‖x (n )‖0<< N . Tingkat ke-sparse-an dari sinyal (sparsity) dinyatakan dalam nilai k yaitu banyaknya elemen yang tidak nol dalam sinyal x(n).Dalam banyak sinyal, sparsity dari sinyal tidak langsung kelihatan dengan melihat nilai nol dari sinyal tersebut, namun sinyal tersebut sparse dalam basis tertentu. Dalam persamaan matematika, hal ini dapat dinyatakan dengan:

x (n)=F⋅s (n) (21)

‖x (n )‖1=∑i=1

N

|x i|=|x1|+|x2|+.. .+|xN|

‖x (n )‖2=√∑i=1

N

|xi|2=√|x1|

2+|x2|2+ .. .+|xN|

2

‖x (n )‖0=|sup ( x (n) )|

sup (x )={i , x i≠0}


Pada persamaan (21), sinyal x(n) dikatakan sparse dalam basis F jika s(n) adalah sparse dengan hanya k elemen yang tak nol. Sinyal sinusoidal adalah contoh untuk kondisi ini. Dengan mengambil contoh basis Fourier, maka persamaan (21) dapat diinterpretasikan bahwa sinyal sinusoidal x(n) adalah sparse dalam sinyal frekuensi s(n) berbasis F.

3.1.3. Model MatematikTujuan dari compressive sensing adalah melakukan sampling dari sinyal sparse x(n) sehingga diperoleh sinyal hasil sampling atau sinyal pengamatan y(n) yang memiliki jumlah sampel yang lebih sedikit dari x(n). Proses sampling ini dapat dinyatakan dengan persamaan:

y (n )=A⋅x(n ) (22)

untuk suatu matriks compressive sampling A.

Permasalahan yang harus dipecahkan adalah, jika y(n) adalah hasil compressive sampling dari x(n), bagaimana memperoleh kembali sinyal x(n) ini, diberikan sinyal pengamatan y(n).Permasalahan compressive sensing dengan demikian terdiri dari dua permasalahan, yaitu permasalahan compressive sampling yaitu mencari skema sampling yang mengurangi jumlah sampel dan bagian rekonstruksi yaitu menyusun kembali sinyal semula dari sinyal pengamatan.

Gambar 4 memperlihatkan proses dan permasalahan pada compressive sensing.

Gambar.4. Dua tahap dalam compressive sensing: sampling dan rekonstruksi.

Untuk dapat dikembalikan ke bentuk semula, maka matriks A harus memiliki sifat Restricted Isometry Property (RIP) [Candes dan Tao 2005]. Sifat Restricted Isometric Property ini dinyatakan dengan persamaan:

(1−δ s)⋅‖x (n )‖2≤‖A⋅x (n)‖2≤(1−δ s )⋅‖x (n )‖2 (23)

Secara fisis, sifat RIP ini menyatakan bahwa matrik transformasi A tidak mengubah norm dari sinyal x(n).

3.1.4 Algorima Penyelesaian Compressive Sensing.Seperti yang telah dibahas pada bagian sebelumnya, permasalahan compressive sensing terbagi dalam dua bagian yaitu bagian compressive sampling dan rekonstruksi. Permasalahan compressive sensing dapat disederhanakan pada menjadi permasalahan pemilihan matriks sensing A. Secara umum, matriks biner random dengan elemen 0 lebih banyak dari

Ax(n)

vektor N x 1

y(n)vektor k x 1

matrik k x N

rekonstruksiy(n) x(n)

vektor k x 1 vektor N x 1

Estimasi Arah Kedatangan Sinyal : dari Capon’s sampai Compressive Sensing 13 elemen 1 memenuhi keperluan kompresif sensing ini. Penyelesaian permasalahan Compressive Sensing oleh karena ini banyak tertuju pada masalah rekonstruksi.Terdapat 3 metode utama dalam menyelesaikan masalah rekonstruksi seperti yang dibahas pada bagian berikut.

3.1.4.1 Optimisasi l1Permasalahan Compressive Sensing seperti yang tertulis pada persamaan (23) dapat diselesaikan dengan program linier (Linear Programming - LP). Permasalahan linear programming telah di-embedded-kan pada software komputasi yang ada saat ini, seperti Optimization Toolbox di Matlab atau pun CVX.

3.1.4.2 Algoritma GreedyAlgoritma Greedy dilakukan dengan dengan cara mencari basis dari sinyal x(n) secara bertahap. Pembangunan basis ini dilakukan dengan cara memilih set terbaik yang meminimalisasi sparsity dari sinyal x(n) dalam norm yang dipilih. Beberapa algoritma yang termasuk kelas ini adalah antara lain adalah basis pursuit dan orthogonal matching pursuit (OMP) serta variannya.

3.1.4.3 Algoritma Pseudo Inverse dan variasinyaPenyelesaian permasalahan compressive sensing dengan pseudo inverse dan variasinya termasuk penyeleseian permasalahan compressive sensing yang paling langsung. Permasalahan compressive sensing seperti yang dirumuskan pada persamaan (22) dapat diselesaikan dengan menghitung inverse dari matriks A (A-1). Dengan demikian sinyal x(n) semula adalah:

x (n)=A−1⋅y (n)(24)

Jika matriks A bukan matriks persegi, maka inverse dari matriks A berubah menjadi pseudo

inverse [Hayashi 2013].

x (n)=A+⋅y (n )=( AH⋅A )−1⋅AH⋅y ( n)(25)

Modifikasi lain dari pseudo inverse ini dilakukan oleh Irina Goronitski untuk memperoleh solusi paling sparse dari x(n) [Goronitski dan Rao 1997]. Skema ini diistilahkan oleh penulisnya dengan nama FOCUSS (FOCal Underdetermined System Solver). Algoritma ini terdiri dari proses iterasi yang langkah demi langkahnya dapat dituliskan sebagai:

s1 : lakukan inisialisasi nilai x(n) tak nol sebarang.s2 : set Wk = diag(x(n))s3 : hitung qk = (A.Wk)+.y(n)s4 : update nilai x(n) dengan nilai Wk.y(n)s5 : ulangi langkah s2 sampai x(n) sparse.


Algoritma FOCUSS ini sederhana dalam implementasinya diaplikasikan cukup luas antara lain di bidang biomedis [Zou W et. al 2007] mau pun di bidang array synthesis [Zhang 2003]

4. COMPRESSIVE SENSING PADA ESTIMASI ARAH KEDATANGAN

Pada Sub-bagian 2, telah dibahas upaya penyederhanaan yang terdapat pada Algoritma estimasi arah kedatangan, yaitu kompleksitas perhitungan. Para peneliti melakukan modifikasi-modifikasi serta manipulasi matematik antara lain untuk menghidari perhitungan eigen-analysis mau pun transformasi unitary untuk memetakan nilai kompleks ke dalam nilai real. Pada bagian ini akan dibahas upaya lain untuk mengurangi kompleksitas perhitungan yaitu dengan cara pengurangan jumlah sampel sesuai prinsip dari compressive sensing. Para peneliti telah melakukan penggabungan teknik compressive sensing dengan estimasi arah kedatangan [13, 14, 15, 16]. Untuk keperluan pemahaman lebih lanjut dari algoritma Compressive sensing ini, maka penulis melakukan simulasi algoritma CS berbasis FOCUSS yang dikembangkan oleh Irina dan Ra0.

4. Compressive Sensing Pada Estimasi Arah Kedatangan

Pada Sub-bagian 2, telah dibahas upaya penyederhanaan yang terdapat pada Algoritma estimasi arah kedatangan, yaitu kompleksitas perhitungan. Para peneliti melakukan modifikasi-modifikasi serta manipulasi matematik antara lain untuk menghidari perhitungan eigen-analysis mau pun transformasi unitary untuk memetakan nilai kompleks ke dalam nilai real. Pada bagian ini akan dibahas upaya lain untuk mengurangi kompleksitas perhitungan yaitu dengan cara pengurangan jumlah sampel sesuai prinsip dari compressive sensing. Para peneliti telah melakukan penggabungan teknik compressive sensing dengan estimasi arah kedatangan [Wing Yang 2009, Yong Min 2010]. Untuk keperluan pemahaman lebih lanjut dari algoritma Compressive sensing ini, maka penulis melakukan simulasi algoritma CS berbasis FOCUSS yang dikembangkan oleh Irina dan Rao [16].Algoritma fokus ini berbasiskan pseudo inverse dan dapat dituliskan pada skema berikut.Algoritma FOCUSS:


s2 : Hitung dekomposisi Eigen dari Rxx : Rxx=U⋅Σ⋅U H

s3 : Partisi vektor eigen U menjadi sinyal sub-space Us dan noise sub-space Un.

Gambar berikut memperlihatkan contoh simulasi yang di buat untuk mengestimasi arah kedatangan dengan algoritma klasik dan compressive Sensing (algoritma FOCUSS).


Gambar 5. Estimasi arah kedatangan pada tiga algoritma estimasi arah kedatangan : Algoritma Capon, Algoritma MUSIC dan Algoritma CS-FOCUSS. Sumbu datar : sudut kedatangan. Sumbu

tegak : spektrum sinyal

5. Permasalahan Pada Algoritma Compressive Sensing Pada Estimasi Arah Kedatangan.

Permasalahan yang terdapat pada algoritma compressive sensing untuk keperluan estimasi arah kedatangan adalah sensitifitas algoritma terhadap pengaruh noise khususnya untuk algoritma FOCUSS [Kay 1993]. Untuk mengetahui lebih lanjut permasalahan yang timbul, dilakukan simulasi dengan menggunakan tiga skema, dua skema klasik (MVDR dan satu skema CS (CS-FOCUSS).Simulasi dilakukan untuk berbagai SNR dari -10 sampai dengan 15 dengan arah sudut kedatangan pada 30 derajat

Hasil simulasi menunjukkan bahwa skema CS-FOCUSS memiliki kesalahan estimasi yang paling besar dibandingkan dengan skema konvensional.


-10 -5 0 5 10 15-20

0

20

40

60

80

100

120

140

160

Delay and SumCAPONMUSICCOMPRESSIVE SENSING

Gambar 6. Skema perbandingan performansi algoritma MVDR, MUSIC dan CS-Fokus sebagai fungsi dari SNR. Sumbu datar menyatakan SNR dalam dB dan sumbu Tegak menyatakan error estimasi sudut rata-rata dari algoritma.

6. PENUTUP

Perkembangan algoritma estimasi arah kedatangan telah dibahas pada paper ini, mulai dari skema klasik. Varian dari skema klasik dikembangkan untuk menyederhanakan proses komputasi antara lain dengan modifikasi pada analysis eigen-analysis sampai dengan skema alternatif untuk menghindari exhaustive search.

Penggunaan teknik compressive sensing pada estimasi arah kedatangan sinyal tampak menjanjikan dengan adanya pengurangan sampel yang signifikan. Di sisi lain, pengurangan jumlah sampel ini menyebabkan permasalahan ketahanan terhadap noise, karena sistem harus mendeteksi sinyal ber-noise dalam jumlah sampel yang sedikit. Pada penelitian ke depan diperlukan upaya untuk mengatasi kekurangan inherent. Upaya ini dapat berupa pemilihan matriks sampling tertentu, atau skema rekonstruksi yang cocok. Pemanfaatan sifat sparse dari sinyal radar yang biasanya berupa sinyal sinusoidal dapat menjadi panduan yang efektif dari upaya ini.

REFERENSI[1] J. Capon. 1969. High-Resolution Frequency-Wavenumber Spectrum Analysis. In Proceedings of

the IEEE, Vol. 57, No. 8, August 1969.[2] Sidney P. Applebaum. 1976. Adaptive Array. In IEEE Transactions on Antennas and

Propagation, Vol. Ap-24, No. 5, September 1976[3] Ralph o. Schmidt. 1986. Multiple emitter location and signal parameter estimation. In IEEE

Transactions on Antennas and Propagation, vol. Ap-34, No. 3, March 1986[4] Arthur J. Barabell. 1983. Improving the Resolution Performance of Eigenstructure-Based

Direction-Finding Algorithms. In IEEE Conference on Acoustics, Speech, and Signal Processing, 1983

[5] Anna Lee. 1980. Centrohermitian and Skew-Centrohermitian Matrices. Journal of Linear Algebra And its Applications 29:205-210(1980)

[6] Keh-Chiarng Huarng, Chien-Chung Yeh. A Unitary Transformation Method for Angle-of-Arrival Estimation. IEEE Transactions on Signal Processing, Vol. 39, no.4, April 1991

Estimasi Arah Kedatangan Sinyal : dari Capon’s sampai Compressive Sensing 17 [7] R. Roy, A. Paulraj, T. Kailath. 1986. Estimation of Signal Parameters via Rotational Invariance

Techniques – ESPRIT. In IEEE Military Communications (MILCOM) Conference - Communications-Computers. 1986.

[8] Martin Haardt, Joseph Nossek. 1995. Unitary ESPRIT: How to Obtain Increased Estimation Accuracy with a Reduced Computational Burden. In IEEE Transactions on Signal Processing, vol. 43, no. 5, may 1995

[9] G. Xu, S. D. Silverstein, R. H. Roy, and T. Kailath. 1994. Beamspace ESPRIT. In IEEE Transactions on Signal Processing. Vol. 42, no. 2, pp. 349–356, Feb.1994.

[10] Van Veen, Kevin M Buckley. 1988. Beamforming: A Versatile Approach to Spatial Filtering. In IEEE ASSP Magazine April 1988.

[11] Henry Cox, Robert M. Zeskind, Mark M. Owen. 1987. Robust Adaptive Beamforming. In IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. Assp-35, No. 10, October 1987

[12] Peng Chen, Xiang Tian, Yaowu Chen, Xiaofan Yang. 2008. Delay and Sum of Beamforming on FPGA. In ICSP Proceeding 2008.

[13] Yuan Zeng, Richard C. Hendriks. 2014. Distributed Delay and Sum Beamformer for Speech Enhancement via Randomized Gossip. In IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 22, No. 1, January 2014

[14] G. H. Golub and C. F. V. Loan. 1990. Matrix Computation. Baltimore, MD: Johns Hopkins Univ. Press, 1996.

[15] Michael Zoltowski. 1988. On the Performance Analysis of the MVDR Beamformer in the Presence of Correlated Interference. In IEEE Transactions on Acoustics, Speech, and Signal Processing IEEE Vol. 36, No. 6, June 1988

[16] Leverett Bezanson, Kevin D. LePage, Robert Been.The Subarray MVDR Beamformer for Active Littoral Sonar Systems. In Proceeding of Oceans - San Diego, 2013

[17]Mostofa Kaveh, Arthur J. Barabell. 1986. The Statistical Performance of the MUSIC and the Minimum-Norm Algorithms in Resolving Plane Waves in Noise. In IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-34, No. 2, April 1986.

[18] Petre Stoica, Arye Nehorai.1989. MUSIC, Maximum Likelihood, and Cramer-Rao Bound, In IEEE Transactions on Acoustics. Speech. and Signal Processing. Vol 37. No 5.May 1989

[19] Arthur J. Barabell. 1983. Improving the Resolution Performance of Eigenstructure-Based Direction-Finding Algorithms. In IEEE Conference on Acoustics, Speech, and Signal Processing, 1983

[20] Michael Zoltowski, Cherian Mathews. 1992. Direction Finding with Uniform Circular Array Via Phase Mode Excitation and Beamspace Root-MUSIC. In IEEE Proceeding 1992, pp. V245-248

[21] Barry Van Veen and Bruce Williams. 1988. Structured Covariance Matrices and Dimensionality Reduction in Array Processing. In Fourth Annual ASSP Workshop on Spectrum Estimation and Modeling, 1988

[22] G. Xu, S. D. Silverstein, R. H. Roy, and T. Kailath. 1994. Beamspace ESPRIT. In IEEE Transactions on Signal Processing. Vol. 42, no. 2, pp. 349–356, Feb.1994.

[23] Marius Pesavento, Alex B. Gershman, Martin Haardt. 2000. Unitary Root-MUSIC with a Real-Valued Eigendecomposition: A Theoretical and Experimental Performance Study. In IEEE Transactions on Signal Processing, Vol. 48, No. 5, May 2000

[23] P. Comon and G. H. Golub. 1990. Tracking a few extreme singular values and vectors in signal processing. In Proceeding IEEE, vol. 78, pp. 1327–1343, Aug. 1990.

[24] R. Roy, A. Paulraj, T. Kailath. 1986. Estimation of Signal Parameters via Rotational Invariance Techniques – ESPRIT. In IEEE Military Communications (MILCOM) Conference - Communications-Computers. 1986.

[25] Martin Haardt, Joseph Nossek. 1995. Unitary ESPRIT: How to Obtain Increased Estimation Accuracy with a Reduced Computational Burden. In IEEE Transactions on Signal Processing, vol. 43, no. 5, may 1995

[26] Harry Nyquist. 1928. Certain Topics in Telegraph Transmission Theory. In Transaction of AIEE, Vol. 47, pp. 617–644, Apr. 1928

[27] C. E. Shannon. 1949. Communication in the Presence of Noise. In Proceeding of Institute of Radio Engineers, Vol. 37, No. 1, Jan. 1949

[28] David L. Donoho. 2006. Compressed Sensing. In IEEE Transactions on Information Theory, Vol. 52, No. 4, April 2006

[29] Emmanuel Candes. 2006. Compressive Sampling. In Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006

[30] Richard Baraniuk. 2007. Compressive Sensing. In IEEE Signal Processing Magazine. Volume 24. July 2007

[31] Thomas Strohmer. 2012. Measure what should be measured: progress and Challenges in compressive sensing. In IEEE Signal Processing Letters, vol. 19, no. 12, december 2012 [32] Kashunori Hayasi, Masaaki Nagahara, Toshiyuki Tanaka. 2013. A User’s Guide to

Compressive Sensing for Communications Systems. In IEICE Transaction on Communication. Vol.E86-B. No.3. March 2013.

http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=764






[33] Emmanuel Candes, Terrence Tao. 2005. Decoding by Linear Programming. In IEEE Transaction on Information Theory. Vol.51. No.12. December 2005.

[34] Emmanuel Cand`es and Justin Romberg. L1-magic : Recovery of Sparse Signals via Convex Programming. http://users.ece.gatech.edu/~justin/l1magic/. Accessed at March 14 2014.

[35] Irina F. Gorodnitsky, Bhaskar D. Rao. 1997. Sparse Signal Reconstruction from Limited Data Using FOCUSS: A Re-weighted Minimum Norm Algorithm. In IEEE Transactions on Signal Processing, Vol. 45, No. 3, March 1997

[36] Zouch, W. ; et. al. 2007. Combining WMN and FOCUSS recursive approach to estimating the current density distribution in the brain. Engineering in Medicine and Biology Society, 2007. EMBS 2007. 29th Annual International Conference of the IEEE

[37] Jiawei Zhang Nan Hu ; Ming Bao ; Xiaodong Li ; Wei He 2013 Wideband DOA estimation based on block FOCUSS with limited samples . Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE

[38] V. Krishnaveni, T. Kesavamurthy, Aparna B. 2013. Beamforming for Direction-of-Arrival (DOA) Estimation-A Survey. In International Journal of Computer Applications (0975 – 8887) Volume 61– No.11, January 2013

[39] Ying Wang, Geert Leus, Ashish Pandharipande, Direction Estimation Using Compressive Sampling Array Processing, IEEE SSP 2009

[40] Ali Cafer Gurbuz, James H. McClellan, A Compressive Beamforming Method [41] Ying Wang, Ashish Pandharipande, Geert Leus, Compressive sampling based MVDR spectrum

sensing, IAPR 2010[42] Jong Min Kim, Compressive MUSIC: A Missing Link between Compressive Sensing and Array

Signal Processing, SIAM 2010[43] Steven M. Kay. 1993. Fundamental of Statistical Signal Processing – Estimation Theory.

Prentice Hall International Editions. Englewood Cliffs, New Jersey. 1993

http://ieeexplore.ieee.org/search/searchresult.jsp?searchWithin=p_Authors:.QT.Wei%20He.QT.&newsearch=true

a multifrequency mac specially designed for wireless sensor web viewcontoh aplikasi terakhir yang...

Documents