BROADCAST PADA KANAL WIRELESS DENGAN NETWORK CODING Trisian Hendra Putra

BROADCAST PADA KANAL WIRELESS DENGAN NETWORK CODING Trisian Hendra Putra – 2205100046 Email : [email protected] Bidang Studi Telekomunikasi Multimedia Jurusan Teknik Elektro-FTI, Institut Teknologi Sepuluh Nopember (ITS) Kampus ITS, Keputih – Sukolilo, Surabaya 60111 Berkembangnya teknologi jaringan komputer saat ini, kecepatan akses data sangat dibutuhkan dalam distribusi content. Network coding menawarkan paradigma baru untuk jaringan komunikasi. Dengan menggunakan network coding, maka masalah kecepatan download file, penyimpanan, pesan, komunikasi interaktif, efisiensi dalam distribusi content dan masalah tentang packet loss dapat diselesaikan, sehingga pengguna internet lebih mudah dalam melakukan akses download file dalam jumlah besar dengan kata lain network coding akan meningkatkan performance sistem pada jaringan internet. Pada tugas akhir ini dirancang broadcast pada jaringan wireless dengan menggabungkan berbagai paket yang hilang dari berbagai paket receivers sehingga beberapa transmisi receivers dapat mengembalikan satu paket yang hilang dengan satu transmisi oleh pengirimnya, serta Merancang broadcast pada jaringan wireless dengan menggunakan network coding dan bertujuan untuk simulasikan serta membandingkan antara dua skema broadcast yang berbeda dengan tolak ukur network coding sebagai pembanding. Dengan skema broadcast network coding akan dapat ditentukan metode yang tepat untuk pengiriman paket yang handal. Dan hasilnya dapat dijadikan untuk mengetahui perbandingan antara metode broadcast dengan menggunakan network coding dan non-network coding yang baik untuk jaringan wireless. Kata kunci : network coding, broadcast, wireless I.

PENDAHULUAN Broadcast adalah suatu mekanisme untuk menyebarkan informasi yang sama dari suatu pengirim ke banyak penerima. Ini digunakan dalam banyak aplikasi, yang berkisar dari komunikasi satelit sampai network WiFi. Dalam sesi penyiaran yang dapat diandalkan, setiap penerima harus menerima informasi dengan benar yang dikirimkan oleh pengirim Permasalahan yang timbul adalah bagaimana mendistribusikan content secara bersama-sama bisa diatasi menggunakan network coding. Batasan masalah yaitu pada pembatasan node yang digunakan yaitu 5 node dalam sistem. Sistem yang bekerja dalam network coding meliputi routing Broadcast menggunakan algoritma djikstra dan menggunakan max flow min cut dan pengkodean Reed solomon. Pada tugas akhir ini akan dibandingkan skema network coding dengan skema non-network coding yang telah ada. Skema baru ini digunakan untuk permasalahan broadcast pada network. Dari perbandingan ini akan diketahui apakah skema baru network coding ini lebih handal dari skema non-network coding. Penelitian pada tugas akhir ini bertujuan membuat simulasi skema network coding untuk distribusi content pada

Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS

peningkatkan performance network komputer atau pada akses pengiriman data. Membandingkan network coding dengan skema non-network menggunakan algoritma djikstra atau max flow min pengkodean Reed solomon.

internet kinerja coding cut dan

II. TEORI PENUNJANG 2.1 Broadcast Broadcast adalah suatu mekanisme untuk mensosialisasikan informasi dari pengirim ke beberapa penerima,

Gambar 1 skema broadcast.

dimana pesan awal dimiliki oleh node sumber harus disebarluaskan ke seluruh node lain dalam network. Broadcast disini adalah sebagai Istilah untuk network komunikasi yang pengiriman datanya dari sebuah terminal dilakukan secara menyebar[1]. Untuk menggambarkan skema yang dikemukakan, maka asumsi dari skema broadcast adalah sebagai berikut : 1. Ada satu pengirim dan lebih dari 1 penerima (M>1). 2. Data dikirim dalam paket – paket, dan setiap paket dikirim dalam satu slot waktu dengan durasi tetap[1]. 2.2 Network coding Network coding adalah sebuah mekanisme terbaru yang diusulkan dalam beberapa tahun terakhir untuk meningkatkan pemanfaatan throughput dari suatu topologi network. Dibandingkan pendekatan dengan cara tradisional lain (misal building multicast tree), network coding mengoptimalkan penggunaan resource network yang tersedia dan skema penjadwalan komputasi yang mencapai tingkat computationally yang mudah. network coding memperbaiki suatu perkembangan informasi tanpa ada penjadwalan yang dikoordinasi secara umum dengan beberapa pertimbangan sederhana. gambar 2 menjelaskan tentang pertukaran paket yang dilakukan antar node. Gambar 2a adalah non-network coding dan gambar 2b adalah network coding.

Gambar 2 (a) non-network coding (b) network coding[1]

Proses non-network coding memerlukan langkah yang lebih banyak dibandingkan dengan proses network coding. Dari gambar terlihat bahwa proses yang dilakukan nonnetwork coding sebesar 4 langkah, sedangkan proses yang dilakukan network coding . 2.3 Algoritma Djikstra Algoritma Dijkstra, (dinamai menurut penemu, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah dengan sisi yang bernilai tak-negatif. Masalah penentuan jalur terpendek di dalam graph merupakan permasalahan optimasi klasik. Graph yang digunakan adalah graph berarah dan memiliki suatu bobot. Bobot pada sisi graph dapat merepresentasikan jarak antar kota, waktu pengiriman, ongkos pembangunan[3]. B 3 1

4

A 2

4

E

3

8

5

D

C 2

7

6

4

8

F

Gambar 3 Representasi Graph G(V,E).[3]

2.4 Max Flow Min Cut Max-flow min-cut adalah metode untuk mencari maximum flow dan minimum cut. Metode ini digunakan untuk menentukan besar kapasitas kanal untuk jalur transmisi data. Selain itu metode ini juga akan menghilangkan beberapa node yang nilai kapasitas kanal bernilai kecil dan tidak dipakai untuk melewatkan data [6]. Metode Ford-Fulkerson mempunyai algoritma sebagai berikut : dimulai dari flow atau jalur kosong pada setiap sisi dan kemudian meningkatkan flow selama masih terdapat augmenting path dari source ke sink dimana tidak terdapat kapasitas yang melebihi batas dikarenakan bahwa kapasitas dan flow dari setiap sisi adalah bilangan bulat dan kapasitas merupakan bilangan positif, dalam setiap langkah kita mendapatkan sebuah flow baru yang mendekati maksimum. Tapi, algoritma ini tidak dijamin berhasil jika kapasitas adalah bilangan rasional. Bagaimana membuktikan kebenaran dari algoritma ini, terlihat jelas bahwa dalam network telah ditentukan maksimum flow, jika tidak kita akan dapat meningkatkan nilai maksimum dari flow,ini merupakan kebalikan dari asumsi awal. Pernyataan ini benar jika dibandingkan dengan pernyataan, maka tidak akan terdapat lagi augmenting path, nilai dari flow telah mencapai maksimum. Teori ini dikenal dengan nama Max-flow min-cut theorema[4]. 2.5 Reed Solomon Code Sebuah kode Reed solomon (RS) dengan symbol 2 kode nonbinary cyclic codes dengan simbol-simbol yang terdiri dari m-bit berurutan, dimana m adalah bilangan bulat positif yang memiliki nilai lebih besar dari 2. RS (n, k) kode pada m-bit simbol ada untuk semua n dan k dimana 0 < k < n < 2m + 2. Parameter-parameter sebagai berikut [5] :


dimana

2

: adalah jumlah simbol data yang dikodekan : adalah jumlah total kode : adalah simbolkemampuan koreksi kesalahan : adalah jumlah parity symbol

2.5.1 Extension Field GF(23) Mendefinisikan dan mempertimbangan suatu polinomial primitif dan finite fields. Tabel 1 berisi daftar beberapa primitif polinomial. Pillihan yang pertama menampilkan, f(X) = 1 + X + X 3, yang mendefinisikan sebuah finite fields GF (2m), di mana derajat polinom adalah m = 3. Dengan demikian, ada 2m = 23 = 8 elemen dalam fields didefinisikan oleh f (X). Penyelesaian untuk akar dari f (X) yang berarti bahwa nilai-nilai dari X yang sesuai dengan f (X) = 0 harus dapat ditemukan. Elemen biner yang dikenal yaitu, 1 dan 0, tidak memenuhi polinom f(X ) = 1 + X + X 3, karena f (1) = 1 dan f (0) = 1 (menggunakan Modulo – 2 aritmatika). Namun, sebuah teorema dasar aljabar menyatakan bahwa besar polinom m harus memiliki pangkat m yang tepat. Oleh karena itu untuk contoh ini, f (X) = 0 harus menghasilkan tiga akar. Jelas sebuah dilema muncul, karena pangkat tiga tidak terletak pada finite field yang sama sebagai koefisien dari f (X). Maka, harus digunakan pangkat yang terletak pada extention fields, GF (23). Dengan α, adalah sebuah elemen dari extention field, dapat didefinisikan sebagai pangkat dari polinomial f (X) dan dapat ditulis sebagai berikut [6] : f(α) = 0 1 + α + α3 = 0 α3 = –1 – α (1) karena binary field +1 = −1, α3 dapat didefinisikan α3 = 1 + α (2) 3 Dengan demikian, α dinyatakan sebagai jumlah α lebih rendah. didapat (3) α7 = α α6 = α (1 + α2) = α + α3 = 1 = α0 Perhatikan bahwa α7 = α0, dan karena itu delapan finite field GF (23) adalah [6]: (4) {0, α0, α1, α2, α3, α4, α5, α6} Tabel 1 Beberapa Primitif Polinomial

Gambar 4 Pemetaaan Elemen Fields Dalam Basis Elemen GF(23) Dengan F(X) = X3+ X+1[6]

codeword yang diterima mengalami error, sehingga akan dilakukan langkah berikutnya, yaitu: 1. Mencari lokasi error mempunyai persamaan polynomial error locator pada persamaan (6) 1 di mana v menunjukkan error yang terjadi sampai Nilai-nilai dari , , …, pada lokasi ke dapat dicari menggunakan matrik seperti yang terlihat pada persamaan 5, di mana syndrom pertama dilakukan untuk memprediksi syndrom berikutnya.

Tabel 2 Addition Table dan Multiple Table

2.

, Pada Additional table penjumlahan menunjukkan kolom. Pada menunjukkan baris sedangkan . menunjukkan , Multiplication table perkalian menunjukkan kolom. baris sedangkan 2.5.2 Reed-Solomon Encoding Pada dasarnya terdapat tiga tahap pada proses pegkodean RS secara sistematik, yaitu : Menentukan Mengalikan data informasi dengan pariti p(x) yang didapat melalui Operasi (1) dimana adalah generator polinomial untuk RS dengan , yaitu simbol dari GF (2 ) dengan panjang kode 2 (2) Menggabungkan hasil proses a dan b sehingga diperoleh codeword yang dapat ditulis sebagai (3) 2.5.3 Reed-Solomon Decoding Pada RS dekoder, codeword mempunyai persamaan:

yang

(7) Setelah nilai-nilai σ pada persamaan 6 sudah dapat ditentukan maka terbentuklah persamaan untuk σ(x). Lokasi error dapat diketahui dengan cara mensubstitusikan akar-akar generator polinomial ke dalam variabel x. Lokasi error (β) terjadi pada saat σ(x)=0. Nilai error Setelah lokasi error diketahui, maka nilai error dapat ditentukan dengan menggunakan persamaan

(8) III. PEMODELAN DAN SIMULASI SISTEM 3.1 Pemodelan Sistem Model sistem network coding yang digunakan pada simulasi Tugas Akhir ini dapat dilihat seperti Gambar 5. Simulasi pada tugas akhir ini dibuat untuk menganalisa distorsi pada pengiriman media dengan memggunakan skema network coding pada sistem network komputer.

diterima (4)

di mana : = codeword yang diterima = codeword yang dikirimkan = error akan bernilai sama dengan pada saat codeword yang diterima tidak mengalami error ( 0. Langkah pertama yang dilakukan dekoder RS untuk mendekodekan data yang diterima, yaitu menghitung sindrom (S). Sindrom didapatkan dengan cara memasukkan akar-akar generator polinomialnya ke dalam codeword yang diterima. (5) 1, … , | Jika sindrom yang dihasilkan sama dengan nol maka codeword yang diterima tidak mengalami error, sedangkan apabila tidak sama dengan nol, maka dapat diartikan bahwa


Gambar 5 Diagram Alir Proses Simulasi

Gambar 6 Diagram Alir Skema Broadcast

Langkah-langkah yang dilakukan berdasarkan gambar 5 adalah sebagai berikut: a. Memodelkan network komputer dengan graf. b. Menentukan jumlah node yang akan digunakan. Node berjumlah 5 buah, 1 source node, 2 node tengah, dan dengan 2 node penerima. c. Merepresentasikan dengan graf. d. Memilih inputan. e. Dalam network yang akan disimulasikan digunakan skema broadcast, penentuan panjang lintasan sesuai dengan algoritma dijkstra untuk menentukan jalur terpendek. f. Algoritma max flow min cut untuk menentukan maximum flow dalam network. Algoritma ini digunakan untuk menentukan besar lintasan. g. Menentukan GF yang akan digunakan. h. Menkombinasi data dan mengkodekan menggunakan pengkodean Reed solomon untuk dikirim ke node tujuan. i. Data dikoreksi dan didekodekan pada penerima untuk mengetahui data asli. Langkah-langkah yang dilakukan berdasarkan gambar 6 adalah sebagai berikut: 1. Membandingkan skema broadcast yang akan disimulasikan, Skema yang akan dibandingkan yaitu skema A (penerima tanpa memori), skema B (skema ARQ khusus), skema C (retransmisi berbasis waktu), dan skema D (pengembangan retransmisi berbasis waktu). 2. Menentukan gain dari skema broadcast dengan menggunakan network coding skema C (retransmisi berbasis waktu) dengan gain dari skema broadcast dengan menggunakan network coding skema D (pengembangan retransmisi berbasis waktu). IV. ANALISA DATA DAN PEMBAHASAN 4.1 Analisa Hasil Simulasi

Gambar 8 Max Flow Min Cut dari source node ke node 4

Gambar 9 Max Flow Min Cut dari source node ke node 5

Analisa hasil sistem perencanaan dengan menggunakan matriks adjacent pada graf dengan 5 node. Pengiriman data menggunakan sistem broadcast dimana node 4 dan node 5 sebagai penerima atau sink dan node 1 adalah sebagai source node. Node 1 akan mengirim data menuju node 4 dan node 5. Berikut adalah gambar 7 adalah konfigurasi 5 node yang akan digunakan. Pada gambar 7 adalah menggambarkan graf secara umum pada network komputer dengan 5 node. Dengan menggunakan algoritma djikstra dapat diketahui bahwa jarak lintasan terpendek dari pengirim node 1 menuju node 4 dan node 5 dapat ditentukan. Dari hasil program simulasi didapatkan bahwa untuk pengiriman data secara broadcast dari node sumber 1 menuju node 4 dibutuhkan jarak sebesar 4. Jarak 4 merupakan jarak terpendek yang melewati node 2, jadi node yang dilewati adalah node 1, 2, 4. dan dari node sumber 1 menuju node 5 dibutuhkan jarak sebesar 4. Jarak 4 adalah jarak terpendek dari node 1 ke node 5 yang melewati node 3, sehingga node yang dilewati adalah node 1, 3, 5. Pada simulasi akan dihitung besar max flow yang akan dilewatkan. Berikut akan dihitung besar kapasitas kanal yng bisa dilewatkan menggunakan max flow min cut. 4.2 Analisa network coding Dari Gambar 10 akan dilakukan perhitungan dengan network coding. Persamaan dari gambar 10 adalah sebagai berikut :

Gambar 7 Konfigurasi Graf 5 Node Gambar 10 Analisa network coding


0 Membuat matrix dari syndrome sesuai dengan persamaan 7 0 0 0 0 Kita ambil matrix 2 x 2

, , , , , ,

Paket yang dikirim adalah 2,4,6 dengan bit 010,100,110.

Untuk mencari nilai

.

,

kita gunakan persamaan 6

det

Untuk mengetahui data yang dikirim dari node 1, kita ambil contoh paket yang diterima di yaitu

.

0 dan

det

. .

. 0 Menghitung nilai error

4.3 Analisa Pengkodean Reed Solomon Setelah melakukan pencarian jarak lintasan terpendek menggunakan algoritma djikstra dan nilai maksimum flow dan minimum cut maka data akan dikodekan untuk dikirim menggunakan kode Reed Solomon. Data yang dikirim menggunakan GF(7,3) Reed Solomon code dengan menggunakan GF(8), Paket = 2,4,6 6 2 4 Nilai kita konversikan ke berdasarkan Tabel 1 . Polinomial didapatkan dari persamaan 1 . Nilai

̂ ̂ ̂

dilihat dari persamaan 2

Kode yang dihasilkan dari persamaan 3 adalah ((110) Diberikan error 000

+(100)

+(010)

+(101)

+(100)

)

100 111 000 000 000 000 Dari persamaan 4 dapat ditentukan kode paket yang diterima pada sink

Untuk menemukan syndrome digunakan persamaan 5 1, … , |


̂

Setelah decoding dengan RS didapatkan paket 010 2 100 4 110 6 4.4 Analisa Perbandingan Error Pada Skema Network coding dengan Skema Non-network coding Error dihitung setelah mengirim 15 paket pada masing-masing skema, lalu dibandingkan. Pada skema network coding didapatkan rata-rata paket error setelah pengiriman 300 paket adalah 38 paket error dan rata-rata error tiap 15 paket adalah 2. Pada skema non-network coding rata-rata paket error setelah pengiriman 300 paket adalah 82 paket error dan rata-rata paket error tiap 15 paket adalah 5 paket error. Pada tahap ini skema network coding lebih baik daripada skema non-network coding.

10 e 8 r 6 r 4 o 2 r 0

Network Coding

15

45

75 105 135 165 195 225 255 285

jumlah paket Gambar 11 Perbandingan error network coding dengan non-network coding

4.5 Analisa Perbandingan skema Network coding dengan skema non-network coding 1.4 PERBANDINGAN 1.35 1.3 BANDWIDTH 1.25 1.2 1.15 1.1 Skema A skema B 1.05 1 skema C skema D 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 Gambar 12 Perbandingan Skema Non-network coding dengan Skema Network coding

Dalam pengukuran ditentukan probabilitas error dari receiver (p1) adalah 0.2 , 0.4 , 0.6 , 0.8 , 1.0 , 1.2 , 1.4 , 1.6 , 1.8 , dan 2.0, sedangkan probabilitas error dari receiver (p2) adalah 0.1. untuk perhitungan dari beberapa skema antara skema Network coding dan skema non-network coding ditunjukkan pada gambar 12 dibawah ini. 4.6

Analisa Perbandingan Gain pada Skema Network coding dan Skema Non-network coding Perbandingan gain yang didapat dari pembagian 2 skema antara skema B dan skema C serta skema B dan skema D dapat dilihat pada gambar 13. gain dari skema D lebih kecil daripada gain dari skema C.

PERBANDINGAN GAIN

3) Error yang terjadi disebabkan oleh penjumlahan antara paket dan alfa yg bernilai sama. 4) Throughput dari skema network coding lebih tinggi daripada skema non-network coding. 5) Gain network coding dari skema C (retransmisi berbasis waktu) lebih tinggi daripada skema D (pengembangan retransmisi berbasis waktu). 6) Perbedaan nilai Gf berpengaruh pada kapasitas jumlah bit dalam satu paket. 5.2 1) 2)

3)

4)

Saran Pemanfaatan Broadcast pada Kanal Wireless dengan Network Coding untuk peningkatan Untuk penelitian lebih lanjut tentang Broadcast pada Kanal Wireless dengan Network Coding diharapkan menghitung, menganalisa proses penyimpanan paket di dalam memori sebelum dan sesudah di injeksikan paket. Mengitung delay dan efisiensi daya untuk membandingkan skema non-netwok coding dengan network coding. Melakukan perhitungan nilai Gf(16), Gf(32) dan membandingkan hasil perhitungan throughput dari pengiriman paket antar node.

DAFTAR PUSTAKA [1] Dong nguyen, Tuan Tran, Thinh Nguyen, and Bella Bose, “Wireless broadcast using network coding”, IEEE Transactions On Information, feb 2009. [2] Gkantsidis, C., Rodriguez, P., Mar. 2005, “Network Coding for Large Scale Content Distribution”, IEEE INFOCOM, no. MSRTR- 2004-80, pp. 12. [3] Aris Puji Widodo, ” Simulasi Lintasan Jalur Terpendek Algoritma Dijkstra Berbasis Extensible Markup Language (Xml)’, April 2007 [4] Kevin Wayne, “Max Flow, Min Cut”, 2004, http://www.cs.princeton.edu/~wayne/teaching/maxflowmincut.pdf Bernard Sklar, “Digital Communications: Fundamentals [5] and Applications, Second Edition”, Prentice-Hall, 2001. Petrus Mursanto, “Generic Reed Solomon Encoder”, [6] Makara, Sains, Vol. 10, No. 2, November 2006: 58-62. BIODATA PENULIS

Gambar 13 Gain dari skema C dan skema D atas skema B V. PENUTUP 5.1 Kesimpulan Berdasarkan hasil simulasi dan analisa, dapat diambil beberapa kesimpulan sebagai berikut: 1) Skema network coding memiliki transmisi bandwidth yang lebih kecil dalam transmisi data dibandingkan dengan skema non-network coding. 2) Skema network coding dalam Broadcast pada Kanal Wireless dengan Network Coding terletak di error yang lebih sedikit daripada skema non-netwok coding.


Trisian Hendra Putra, lahir di Sibolga 14 Desember 1987, merupakan anak pertama dari tiga bersaudara pasangan Sumadi dan Siti Afrida. Memulai pendidikan Sekolah Dasar di SDN Pabean III Sedati-Sidoarjo, kemudian meneruskan pendidikan di SLTP Negeri 1 Sedati-Sidoarjo dan SMA Negeri 1 Waru - Sidoarjo. Pendidikan terakhir di Teknik Elektro ITS bidang studi Telekomunikasi Multimedia. Sekarang sedang mengerjakan tugas akhir di Bidang Studi Telekomunikasi Multimedia, Jurusan Teknik Elektro ITS Surabaya. Email: [email protected]

BROADCAST PADA KANAL WIRELESS DENGAN NETWORK CODING Trisian Hendra Putra

Recommend Documents