DEKODE BERBASIS KONSENSUS PENGKODEAN KANAL YANG TERDISTRIBUSI PADA JARINGAN SENSOR NIRKABEL CITRA DEVI MURDANINGTYAS 2209 203 003 BIDANG STUDI TELEKOMUNIKASI MULTIMEDIA JURUSAN TEKNIK ELEKTRO FTI –ITS SURABAYA SURABAYA 2010
Dosen Pembimbing : Dr. Ir. Wirawan, DEA 1
Latar Belakang • Jaringan sensor nirkabel berkembang sangat pesat aplikasi di bidang militer, kesehatan, perumahan, industri, transportasi dan lingkungan. • Karakteristik jaringan sensor nirkabel – Jarak yang sempit – energi yang terbatas – sensor yang disebar perlu banyak. • Sensor yang banyak konsensus pada sensor agar menghasilkan keputusan bersama
2
Algoritma Konsensus Terdistribusi • Algoritma konsensus terdistribusi suatu algoritma dimana data yang diperoleh oleh setiap sensor akan diperbaharui setiap waktu oleh sensor tetangganya. • Sensor tetangga semua sensor yang terkoneksi dengan sensor tersebut. • Tujuan untuk mendapatkan nilai kesepakatan global antar node. untuk mengurangi kesalahan yang terjadi pada proses pengkodean
3
Cont... Algoritma konsensus terdistribusi terdiri dari : Algoritma Consensus Averaging-Single Iteration (CASI) Algoritma Consensus Averaging-Method of Multiplier (CA-MoM)
4
Permasalahan 1 Bagaimanakah pemodelan sistem pengkodean kanal yang terdistribusi pada jaringan sensor nirkabel? Node pada sistem ini akan disebar dan node akan mendekodekan sebuah pesan. o Pada setiap node(sensor), informasi yang diperoleh tidak selalu sama. o Dengan demikian, untuk mengurangi keterbatasan jaringan sensor nirkabel dibutuhkan kerjasama antar node (sensor). o Salah satu metode yang digunakan adalah dengan algoritma pendekatan konsensus 5
Permasalahan 2 o Bagaimana pengaruh penggunaan beberapa sensor dalam mendekodekan suatu informasi pada jaringan sensor nirkabel? Sistem pengkodean kanal terdistribusi yang diaplikasikan pada jaringan sensor nirkabel apakah layak?
6
Batasan Masalah Luas area yang digunakan adalah 100m x 100m Model penyebaran sensor yang digunakan adalah menggunakan distribusi uniform Model deteksi sensor menggunakan model deteksi biner Topologi yang digunakan pada jaringan sensor network merupakan topologi serial Parameter simulasi yang digunakan mengacu pada spesifikasi dari MTS420 dan MICA2 Algoritma yang digunakan adalah algoritma Centralized dan algoritma konsensus terdistribusi khususnya algoritma CA-SI dan CA-MoM 7
Tujuan Penelitian Memperoleh model sistem pengkodean kanal terdistribusi yang tepat untuk diaplikasikan pada jaringan sensor nirkabel. Memperoleh performansi kerja yang handal dari kerjasama beberapa sensor pada jaringan sensor nirkabel. Memperoleh jaringan sensor nirkabel yang layak dengan keterbatasan memori, daya dan kompleksitas.
8
Teori Graph GRAPH kumpulan dari simpul (node)/vertex yang dihubungkan dengan satu sama lain melalui sisi/busur (edge) G=(V,E)
9
Model Deteksi Biner • Model deteksi biner sederhana • Jangkauan sensing tersebut sering disebut dengan range sensor (rs). • Untuk mengetahui jarak antar sensor dapat menggunakan rumus jarak Euclidean
• di • xi,yi • xt,yt
= jarak target dengan sensor ke i (m) = koordinat dari sensor (m) = koordinat dari target (m)
10
Pendekodean Kode Konvolusional adalah kode dimana urutan bit informasi tidak dikelompokkan ke dalam blok-blok yang berbeda. Proses pendekodean dengan viterbi dimana Deret bit yang memiliki Hamming distance minimum merupakan deretan bit yang paling dekat dengan bit yang diterima Kode Hamming dilengkapi dengan koreksi kesalahan Proses pendekodean dengan mengetahui parity check matrix untuk menentukan pola error dan error syndrome
11
Model Sistem Bit informasi pada sumber AP terlebih dahulu dikodekan dengan kode Hamming (7,4) dan kode Konvolusional (1,2) Data dari AP dikirimkan ke sensor melalui kanal AWGN Jaringan sensor nirkabel dimodelkan sebagai graph 𝒢 := {ℰ,𝒥} Blok yang diterima sensor : y = Es (2 x − 1) + ε j
Pesan/informasi Encoder
Sumber
XЄC
12
Algoritma Centralized • • • • • •
Pembangkitan Sumber Sensor disebar dengan distribusi uniform Pencarian node yang aktif Pengambilan data oleh sensor aktif Pencarian konektifitas antar sensor aktif Proses deteksi data sensor dengan metode Likelihood Ratio J
N
xˆ ML = arg min ∑∑ γ jn x n = arg min γ x x∈C
j =1 n =1
T
x∈C
• Proses pendekodean
13
Algoritma CA-SI • • • • • •
Pembangkitan Sumber Sensor disebar dengan distribusi uniform Pencarian node yang aktif Pengambilan data oleh sensor aktif Pencarian konektifitas antar sensor aktif Proses pembaharuan data oleh sensor tetangga, pengecekan konektifitas γ jn (k ) = γ jn (k − 1) + α (k ) ∑ W ji [γ jn (k − 1) − (γ jn (k − 1) + η jin (k ))] i∈N j
•
Proses deteksi data sensor dengan metode Likelihood Ratio xˆ = arg min ∑ ∑ γ x = arg min γ x • Proses pendekodean J
ML
x∈C
N
j =1 n =1
T
jn
n
x∈C
14
Algoritma CA-MoM • • • • • •
Pembangkitan Sumber Sensor disebar dengan distribusi uniform Pencarian node yang aktif Pengambilan data oleh sensor aktif Pencarian konektifitas antar sensor aktif Proses penentuan variabel Multiplier c v jin ( k ) = v jin ( k − 1) + (γ 2
jn
(k ) − γ
in
( k )),
• Proses pembaharuan data oleh sensor tetangga
[
]
1 γ jn (k + 1) = γ jn − ∑ v jin (k ) − vijn (k ) − c(γ jn (k ) + γ in (k ) , 1 + 2c | N j | 15
Algoritma CA-MoM • Proses deteksi data sensor dengan metode Likelihood Ratio J N xˆ ML = arg min ∑ ∑ γ x∈C
j =1 n =1
T
jn
x n = arg min γ x x∈C
• Proses pendekodean
16
Metode Penelitian START
Distribusi Sensor Encoding
Data Hasil Algoritma Centralized
Decoding
Data Hasil Algoritma CASI
Decoding
Data Hasil Algoritma CAMoM
Decoding
Perbandingan BER
STOP
17
Parameter Simulasi PARAMETER
NILAI
Luas Area
100m x 100m
Jumlah Node yang disebar
10
Range Sensor
25m
Range Komunikasi
50m
18
Plot Distribusi Sensor dan Sumber Range Sensor
Estimasi Distribusi Sensor 100
Sumber Sinyal
2
90
7
9
80
Sensor aktif
5
Lebar Daerah (m)
70
Sensor tidak aktif
60 50 4
10
40 1
3
30
6
20 8
sensor sumber sinyal sensor aktif
10 0
0
10
20
30
50 60 40 Panjang Daerah (m)
70
80
90
100 19
Algoritma Centralized dengan menggunakan Kode Hamming BER for BPSK in AWGN with Hamming (7,4) code
0
10
Centralized Decoder Localized Decoder -1
Bit Error Rate
10
-2
10
-3
10
-4
10
-12
-10
-8
-6
-4
0 -2 Eb/No, dB
2
4
6
8
10
20
Algoritma Centralized dengan menggunakan Kode Konvolusional BER for BCC with Viterbi decoding for BPSK in AWGN
0
10
Centralized Decoder Localized Decoder -1
Bit Error Rate
10
-2
10
-3
10
-4
10
-10
-8
-6
-4
-2
0 2 Eb/No, dB
4
6
8
10
21
Algoritma CA-SI dengan menggunakan Kode Hamming BER for BPSK in AWGN with Hamming (7,4) code
0
10
Centralized Decoder Localized Decoder CA-SI
-1
Bit Error Rate
10
-2
10
-3
10
-4
10
-12
-10
-8
-6
-4
0 -2 Eb/No, dB
2
4
6
8
10
22
Algoritma CA-SI dengan menggunakan Kode Konvolusional BER for BCC with Viterbi decoding for BPSK in AWGN
0
10
Centralized Decoder Localized Decoder CA-SI
-1
Bit Error Rate
10
-2
10
-3
10
-4
10
-10
-8
-6
-4
-2
0 Eb/No, dB
2
4
6
8
10
23
Algoritma CA-MoM dengan menggunakan Kode Hamming BER for BPSK in AWGN with Hamming (7,4) code
0
10
Centralized Decoder Localized Decoder CA-SI CA-MoM
-1
Bit Error Rate
10
-2
10
-3
10
-4
10
-12
-10
-8
-6
-4
-2 0 Eb/No, dB
2
4
6
8
10
24
Algoritma CA-MoM dengan menggunakan Kode Konvolusional BER for BCC with Viterbi Decoding for BPSK in AWGN
0
10
Centralized Decoder Localized Decoder CA-SI CA-MoM
-1
Bit Error Rate
10
-2
10
-3
10
-4
10
-12
-10
-8
-6
-4
0 -2 Eb/No, dB
2
4
6
8
10
25
Kesimpulan 1 Dengan menggunakan algoritma Centralized dapat meminimalkan kesalahan yang terjadi pada proses pengkodean kanal yang terdistribusi baik pada Kode Hamming (7,4) maupun Kode Konvolusional (2,1). Dengan menggunakan algoritma Konsensus Terdistribusi baik algoritma CA-SI dan CA-MoM dapat menjadikan data yang berbeda menjadi konvergen Dari data konvergen yang dihasilkan algoritma CA-SI dan CA-MoM dapat meminimalkan kesalahan pendekodean. 26
Kesimpulan 2 Variabel Multiplier yang digunakan pada algoritma CA-MoM dapat memperbaiki kinerja dari algoritma CA-SI. Semakin benyak iterasi maka kesalah dalam proses pendekodean semakin kecil. Berdasarkan hasil simulasi, nilai BER dari algoritma CA-MoM lebih bagus daripada nilai BER dari algoritma CA-SI.
27
DaftarPustaka • • • • • • •
Akyldiz, I.F, Ismail H. Kasimoglu, (2004), Wireless Sensor and Actor Networks: Research Challenges’, Ad Hoc Networks vol 2, hal 351-367. Akyldiz, I.F, Sankarasubramaniam, Y, dan Cayirci, E. (2002),’’A Survey on Sensor Network”, IEEE Commun Mag, hal. 102-114. Chakrabarty.K, Iyengar, S.S, (2005) “Scalable infrastructure for distributed sensor Networks”, Springer-Verlag London Limited, London. H. Karl and A. Willig, (2005), “Protocols and Architecture for Wireless Sensor Network”, John Wiley. H. Zhu, G. B. Giannakis, dan A. Cano, (2009), “Distributed In-Network Channel Decoding”, IEEE Transaction on Signal Procesing, hal 57. J. G. Proakis, (1989), “Digital Communication”, International Edition. McGraw-Hill: NewYork. S. Haykin, (1988), “ Digital Communications”, John Wiley & Sons, hal 393. 28
DaftarPustaka •
S. Kar and J. M. F. Moura,(2009), “Distributed Consensus Algorithm in Sensor Network With Imperfect Communication: Link Failures and Channel Noise,” IEEE Transactions On Signal Processing, vol 57, No.1. • Swami, A. Zhao, Hong, YW, (2007),”Wireless Sensors Network Signal Processing and Communications Prespectives, John Wiley & Sons Inc. • Wardihani. E D,(2008),” Sistem Deteksi Terdistribusi Pada Jaringan Sensor Nirkabel”, Tesis Jurusan Teknik Elektro, ITS, Surabaya. • Wicker.B Stephen, (1995), “Error Control Systems for Digital Comunication and Storage”, Prentice Hall International Edition, Hal 265.
29
SEKIAN DAN TERIMA KASIH
30
Konvergensi Data CA-SI 51.8
51.7
51.6
51.5
51.4
51.3
51.2
51.1
0
10
20
30
40
50
60
70
80
90
100 31
Konvergensi Data CA-MoM 20 15 10 5 0 -5 -10 -15 -20
0
10
20
30
40
50
60
70
80
90
100
32
Cont... Terdapat beberapa asumsi dari sistem model diatas : A1. Jaringan WSN terhubung, kemungkinan jalur yang terhubung lebih dari 2 (hop jamak) A2. Komunikasi antar sensor dengan hop tunggal yang berdekatan melalui saluran simetri sbb : A2.1 Per blok bersifat ideal dan time-invariant A2.2 Time-invariant digagalkan oleh additive zero-mean sensor i ϵ Ɲ, tidak noise dengan varians σi2 pada berhubungan j dan i A2.3 Time variying antara saluran sensor yang berdekatan j adan i gagal dengan probabilitas 1- Pji , dimana 0< Pji<1 33
Cont... A3. Memasukkan Xn dari X adalah biner {0,1} dimana codebook C merupakan bagian dari X A4. Kanal sensor AP diskrit, tanpa memori, simetri dan sensor bersifat independen, dan sensor j diketahui sebagai pdf bersyarat P(yj|x) yang merupakan karakteristik dari kanal AP
34
