ANALISA PENJADWALAN PAKET PADA CDMA xEV-DO

Prosiding SENTIA 2009 – Politeknik Negeri Malang

ANALISA PENJADWALAN PAKET PADA CDMA 2000 1xEV-DO Annisa Fauziah1, Sofia Naning2, Arief Rudiana3 Departemen Teknik Elektro – Institut Teknologi Telkom 1) [email protected],2)[email protected] ABSTRAK 1xEV-DO merupakan sistem hybrid CDMA/TDM generasi ke tiga yang yang menyediakan layanan data dengan kecepatan tinggi. Menggunakan bandwidth 1.25 Mhz, 1xEV-DO bisa mensupport data rate sampai 2.4576 Mbps pada forward link. Untuk mencapai datarate yang maksimal, terdapat beberapa teknik yang dilakukan pada forward link, salah satunya dengan mekanisme scheduling. Scheduler dibutuhkan untuk mengoptimalkan dan mengefisienkan proses sharing resource sistem, dimana bandwidth secara konstan berubah sesuai dengan fluktuasi kanal wireless. Oleh karena itu dibutuhkan suatu algoritma untuk menyeimbangkan proses penjadwalan user. Dalam Penelitian ini, diskenariokan suatu sistem wireless yang menggunakan Proportional Fair Scheduler sebagai alternatif solusi. Algoritma PF scheduler merupakan mekanisme scheduling yang berusaha untuk menambah performansi throughput sistem dengan menjadwalkan pengiriman data kepada user ketika kondisi kanal user dalam keadaan optimal. Dari hasil simulasi diperoleh bahwa pada tipe vehicular, mekanisme penjadwalan menggunakan PF scheduler dapat meningkatkan throughput system, throughput sistem dengan PF scheduler lebih tinggi yaitu 2,11 Mbps dibandingkan dengan FIFO scheduler yang bernilai 830 Kbps. Sedangkan pada kondisi pedestrian, penggunaan PF scheduler tidak terlalu memberikan pengaruh yang signifikan terhadap penambahan throughput sistem. Throughput yang dicapai sistem saat menggunakan FIFO scheduler sama dengan saat menggunakan PF scheduler yaitu bernilai 2,11 Mbps.Pada kondisi pedestrian, Latency sistem dengan PF scheduler mencapai 0,8 second, lebih tinggi dibandingkan dengan latency sistem dengan FIFO yaitu 0,5 second, sedangkan pada tipe vehicular, latency sistem dengan FIFO scheduler mencapai 2.9243 second, sedangkan latency sistem dengan PF scheduler lebih rendah yaitu bernilai 0.80747 second. Kata kunci : CDMA 2000 1X EV-DO, Proportional Fair Scheduling, Throughput dan Latency Sistem menentukan bagaimana melakukan alokasi resource secara adaptive untuk mencapai throughput yang optimal pada sistem paket data. CDMA 1x-EV DO tidak mempunyai spesifikasi khusus untuk penjadwalan data, masing-masing vendor diperbolehkan menggunakan algoritma penjadwalan paket yang dianggap efisien. Pada penelitian ini diusulkan mekanisme penjadwalan paket dengan menggunakan algoritma proportional fair (PF) scheduler. Alasan pemilihan algoritma proporitonal fair scheduler karena algoritma ini menggabungkan dua hal penting dari suatu scheduler, yaitu fairness dan peningkatan throughput sistem. Algoritma ini bekerja dengan cara melayani setiap user pada kondisi kanal yang maksimal dan secara adil (fair) berusaha meningkatkan throughput user pada sektor tersebut tanpa mengurangi throughput user lainnya. Dengan penggunaan proportional fair (PF) scheduler, diharapkan fairness dapat dicapai sekaligus meningkatkan throughput sistem sehingga user mendapatkan pelayanan yang optimal.

1. PENDAHULUAN Teknologi CDMA 2000 1xEV-DO atau IS-856 merupakan pengembangan dari CDMA 2000 1x yang menyediakan layanan data untuk menghasilkan throughput yang optimal. Untuk mendukung jaringan CDMA2000 1xEV-DO perlu adanya tambahan komponen yang mendukung fungsi-fungsi baru dan meningkatkan kemampuan sistem. Gambar 1 merupakan jaringan 1xEV-DO yang dibangun dengan memanfaatkan jaringan eksisting CDMA2000 1X dengan menambahkan beberapa modul di BSC dan BTS serta software yang mendukung.

Gambar 1: Arsitektur Jaringan CDMA 2000 1xEV-DO

2. CDMA 2000 1X EV-DO 1xEV-DO merupakan sistem hybrid CDMA/TDM generasi ke tiga yang yang menyediakan layanan data dengan kecepatan tinggi.

Untuk meningkatkan performansi sistem, CDMA 1x-EV DO mengimplementasikan algoritma penjadwalan paket. Scheduler J-1


Seperti namanya, 1x Evolution for Data Optimized, 1xEV-DO mendukung aplikasi data dengan menggunakan bandwidth 1.25 Mhz. 1xEV-DO bisa mendukung data rate sampai 2.4576 Mbps pada forward link dan hingga 153.6 Kbps pada reverse link [13]. Jaringan CDMA1xEV-DO dibangun dengan memanfaatkan jaringan eksisting CDMA2000 1X. Hardware tambahan berupa beberapa modul di BSC dan BTS serta software yang mendukung dibutuhkan untuk membentuk jaringan 1xEV-DO.

dibandingkan dengan algoritma First In First Out (FIFO). Akan dianalisa pengaruh penggunaan kedua mekanisme terhadap performansi sistem (average forward link throughput). Proportional Fair Scheduler Pada sebuah sistem wireless dengan multi user yang melewati kanal fading, setidaknya terdapat satu user yang memiliki kondisi kanal terbaik pada satu waktu tertentu. Secara kontinu dan konstan, sistem akan mengamati kondisi kanal user dan membuat keputusan untuk melayani user dengan kondisi kanal yang terbaik, prinsip inilah yang diadaptasi oleh Proportional Fair Scheduler. Algoritma PF scheduler berusaha untuk menambah kapasitas sel dengan memanfaatkan variasi kanal yaitu dengan menjadwalkan pengiriman kepada AT selama periode dimana AT memperoleh level sinyal yang kuat [5]. Disamping itu, scheduler juga memberikan jaminan fairness kepada user yang berbeda. Selama ini, usaha penambahan throughput kepada user-i sebesar x%, akan menimbulkan pengurangan throughput pada user yang lain lebih dari x %. Karena itu, Proportional Fair scheduler berusaha menambah throughput untuk user-i sebesar x %, dengan jaminan tidak akan terjadi pengurangan throughput pada user yang lain didalam sistem lebih dari x % [9]. Pada algoritma Proportional Fair, pengalokasian time slot kepada user i diprioritaskan kepada user dengan nilai fs terbesar. Nilai fs didefinisikan dengan persamaan [7,9,10]: DRC i (t ) fs Ri (t ) fs merupakan rasio antara datarate yang direquest oleh user i pada time slot t dengan nilai average rate user i pada time slot t. Cara kerja PF scheduler adalah sebagai berikut: 1. Inisialisasi: pada time slot t= 0, diset Ri (0 )= 0 untuk seluruh user 2. Untuk user 1≤i≤K, Ri (t) secara eksponensial dirata-ratakan disetiap time slot. Rata-rata time constant ditentukan oleh tc. 3. Updating: untuk i=1:K, nilai Ri (t) diupdate pada masing-masing time slot sesuai dengan persamaan [7,9,10]:

Scheduler Scheduler atau penjadwal merupakan suatu mekanisme pada sistem operasi yang berkenaan dengan urutan kerja yang dilakukan pada suatu sistem [4].. Pada sistem wireless penjadwalan paket dilakukan di RNC (Radio Network Controller) Parameter yang digunakan untuk mengukur dan mengoptimasi kinerja scheduler antara lain [4] 1. Adil (fairness). 2. Latency. 3. Throuhgput Terdapat dua strategi penjadwalan dalam sistem yaitu mekanisme penjadwalan preempative dan penjadwalan nonpreempative. Scheduler dibutuhkan untuk mengoptimalkan dan mengefisienkan proses sharing resource sistem, dimana bandwidth secara konstan berubah sesuai dengan fluktuasi kanal wireless. Oleh karena itu dibutuhkan suatu algoritma untuk menyeimbangkan proses penjadwalan user. 3.

Pemodelan Sistem Simulasi dilakukan pada satu sektor dimana terdapat 16 user (AT) per sektor yang bergerak dengan kecepatan terdistribusi random dimana setiap AT mempunyai kemungkinan kecepatan yang acak (random). Klasifikasi pergerakan user dimodelkan dalam beberapa kecepatan konstan sebagai berikut: 1. pedestrian (pejalan kaki) = 0-5 Km/Jam 2. vehicular = 35-90 Km/Jam. Sistem dimodelkan menjadi tiga blok utama, yaitu blok access network (AN), access terminal (AT), dan blok kanal propagasi. Scheduler terdapat pada AN Scheduler pada AN membuat keputusan untuk mengalokasikan time slot kepada user kemudian menentukan user mana yang terlebih dahulu yang akan diproses untuk dikirimi data. Keputusan dibuat berdasarkan informasi datarate (DRC indeks) yang dikirimkan user melalui datarate channel (DRC) pada reverse link. Algoritma scheduling yang akan digunakan pada simulasi ini adalah algoritma Proportional Fair Scheduling yang akan

Ri(t

1)

(1

1 ) * Ri(t ) tc

(

1 ) * Yi(t ) * DRCi(t ) tc

Yi(t) bernilai 0-1, merupakan variabel yang mengindikasikan ada atau tidaknya user i yang dipilih pada time slot t. User yang tidak mempunyai data untuk dikirimkan juga mendapatkan update ratenya tetapi dapat diabaikan dalam proses perhitungan, dengan kata lain Yi(t) bernilai sama dengan 0. Diasumsikan tc=1000 slot atau sama dengan 1,66 second [7,9]. Konstanta waktu tc merepresentasikan panjang interval yang digunakan untuk mengupdate Ri (t). Nilai parameter J-2


Gambar 3 Nilai SNR pada Single User Sebagai Fungsi dari Kecepatan

tc juga merupakan waktu maksimum user mengalami starvasi (tidak menerima service).

Dari gambar 3 tampak bahwa user dengan kecepatan 0 Km/Jam mendapatkan nilai SNR hampir mencapai 20 dB, namun semakin cepat pergerakan user maka SNR yang diterima user semakin menurun. Kecepatan pergerakan user mempengaruhi fluktuasi kanal pada link forward sehingga berdampak pada SNR yang diterima oleh user. Pada kecepatan rendah fluktuasi kanal menjadi lambat sehingga SNR yang diterima user tinggi, tetapi saat kecepatan user bertambah maka SNR yang diterima user semakin berkurang.

FIFO Scheduler FIFO scheduler memprioritaskan user yang datang terlebih dahulu kedalam antrian. Algoritma FIFO dapat dilihat pada gambar 3.6. User yang akan dijadwalkan pada time slot ke-t adalah user dengan nilai j terbesar. j dihitung dengan persamaan [8]:

j 4.

max i li (t )

Analisa Performansi Sistem

Kecepatan User Terhadap Distribusi Data Rate Data rate pada kanal DRC merupakan representasi dari kondisi kanal yang dialami oleh user. Pada gambar 4 berikut diperlihatkan distribusi data rate pada kanal DRC sesuai dengan kecepatan user:

Kecepatan User Terhadap Variasi Kanal Pada mobile wireless, kondisi kanal mengalami perubahan terhadap waktu secara signifikan. Pada gambar 2 diperlihatkan fluktuasi selubung kanal suatu user yang diamati selama 20 second. User berada pada kondisi pedestrian dan kondisi vehicular.

2000

Vehicular Pedestrian

Rate (kbps)

0

Selubung Fluktuasi Kanal (dB)

-2 -4

1000

-6 -8 500

-10 -12 0

-14

-18 -20

10

20

30

40 50 v (km/jam)

60

70

80

90

Gambar 4. Distribusi Data Rate pada Single User sebagai Fungsi dari Kecepatan User

-16

0

0.2

0.4

0.6

0.8

1 t (ms)

1.2

1.4

1.6

1.8

2

Data rate yang diminta user melalui DRC kanal lebih tinggi ketika user bergerak pada kecepatan rendah dibandingkan pada saat user bergerak pada kecepatan tinggi, user bisa menerima sinyal dari BS dengan lebih baik pada kecepatan rendah. Saat kecepatan rendah, datarate yang mendukung user akan tinggi karena pada kecepatan rendah kondisi kanal yang dialami user cukup baik untuk proses pengiriman data dengan data rate yang tinggi. Namun jika kecepatan user semakin tinggi maka datarate yang dapat mendukung proses pengiriman data juga rendah, karena pada kecepatan tinggi kondisi kanal menjadi buruk dan tidak memungkinkan untuk dilakukan proses pengiriman data menggunakan data rate yang tinggi.

4

x 10

Gambar 2. Fluktuasi Kanal User pada Kondisi Pedestrian dan Vehicular

Dari gambar 2 terlihat bahwa kanal user pada kondisi vehicular berfluktuasi lebih cepat dibandingkan dengan kondisi pedestrian. Pergerakan relatif antara transmitter dan receiver menimbulkan pelebaran spektrum dari sinyal terkirim (Doppler spread) yang disebabkan oleh laju perubahan waktu terhadap kanal (time varying). Semakin cepat pergerakan user, maka semakin tinggi frekuensi Doppler maksimal dan semakin cepat perubahan kondisi fluktuasi kanal. Pada gambar 3 berikut dapat dilihat grafik SNR yang diterima suatu user sebagai fungsi dari kecepatan:

Pengaruh Kecepatan User Terhadap Throughput dan Latency Sistem Menggunakan FIFO dan PF Scheduler Pada simulasi ini, terdapat 16 user (AT) yang terletak pada satu sektor. AT bergerak pada beberapa tipe kecepatan konstan, yaitu pedestrian dengan dan vehicular. Analisa ini dimaksudkan untuk mengetahui pengaruh kecepatan user terhadap performansi sistem yang dilihat dari parameter

20 15 10 5

SNR (dB)

1500

0 -5 -10 -15 -20

0

10

20

30

40 50 v (km/jam)

60

70

80

90

J-3


throughput dan latency, dengan mekanisme penjadwalan user mengggunakan algoritma Proportional Fair (PF) scheduler dan First In First Out (FIFO). Gambar 5 dan 6 berikut menunjukkan pengaruh kecepatan user terhadap throughput yang dapat dicapai oleh user menggunakan algoritma First In First Out (FIFO) dan Proportional Fair (PF) scheduling: 6

2.5

1 user 2 user 4 user 8 user 16 user

7 6

Latency (s)

5 4 3 2 1

Performansi Pada FIFO

x 10

0 1 user 2 user 4 user 8 user 16 user

2

Throughput (bps)

Latency pada FIFO 8

0

10

20

30

40 50 60 Kecepatan (km/jam)

70

80

90

Gambar 7 Grafik Pengaruh Kecepatan User Terhadap Latency Sistem Menggunakan FIFO Scheduler

1.5 Latency pada PF 8

1


7 6

0.5

0

0

10

20

30


70

80

Latency (s)

5

90

4 3

Gambar 5 Grafik Pengaruh Kecepatan User Terhadap Throughput Sistem Menggunakan FIFO Scheduler.

2 1 0

6

2.5

Performansi Pada PF

x 10


Throughput (bps)

2

0.5

10

20

30


70

80

20

30


70

80

90

Pada gambar 7 dan 8 dapat dilihat bahwa semakin bertambahnya kecepatan suatu user maka latency yang dialami juga semakin bertambah. Kecepatan suatu user berpengaruh terhadap kondisi kanalnya, semakin cepat pergerakan user menyebabkan kondisi kanal memburuk, ini menyebabkan proses pengiriman data kepada user tersebut semakin lama sehingga latency yang dialami meningkat.

1

0

10

Gambar 8. Grafik Pengaruh Kecepatan User Terhadap Latency Sistem Menggunakan PF Scheduler

1.5

0

0

90

Gambar 6 .Grafik Pengaruh Kecepatan User Terhadap Throughput Sistem Menggunakan PF Scheduler

Pada gambar 5 dan 6 dapat dilihat bahwa kecepatan user sangat mempengaruhi throughput yang dapat dicapai oleh tiap user. Bertambahnya kecepatan suatu user, throughput yang dapat dicapai semakin menurun. Dapat dilihat juga bahwa pada kecepatan yang sama, throughput yang dapat dicapai oleh sistem dengan 16 user lebih tinggi dibandingkan throughput dengan jumlah user kurang dari 16. Pada kondisi diam (kecepatan 0 Km/Jam), throughput sistem dengan 16 user hampir mencapai 2,5 Mbps, lebih tinggi dibandingkan throughput sistem dengan 1 user, 2 user, 4 user, dan 8 user. Begitu juga pada kecepatan yang lain, throughput sistem dengan 16 user selalu bernilai lebih tinggi. Gambar 7 dan 8 berikut menunjukkan pengaruh kecepatan user terhadap latency user, algoritma First In First Out (FIFO) dan Proportional Fair (PF) scheduling digunakan sebagai mekanisme penjadwalannya:

Analisa Throughput Sistem Pada bagian ini akan dianalisa throughput sistem yang dapat dicapai ketika digunakan PF scheduler dan FIFO scheduler pada tipe kecepatan user yang berbeda. Grafik 9 berikut menunjukkan throughput sistem yang dapat dicapai dengan menggunakan PF scheduler dan FIFO scheduler pada kondisi pedestrian (dengan kecepatan 0-5 Km/Jam): 6

2.5

Performansi Pada kondisi pedestrian

x 10

FIFO PF

Throughput (bps)

2

1.5

1

0.5

0

0

2

Gambar 9.

4

6

8 Jumlah User

10

12

14

16

Throughput Sistem Pada Kondisi Pedestrian

Grafik 9 menunjukkan bahwa throughput sistem dengan FIFO scheduler sama dengan PF J-4


scheduler yaitu mencapai 2,11 Mbps. Pada kondisi pedestrian, kondisi kanal keseluruhan user dalam keadaan baik, sehingga tidak terjadi fluktuasi kanal yang cepat yang menyebabkan tingginya variansi noise. Penggunaan scheduler tidak terlalu memberikan pengaruh yang signifikan terhadap penambahan throughput sistem. Throughput sistem saat menggunakan PF scheduler dan FIFO pada kondisi vehicular (dengan kecepatan 35-90 Km/Jam) dapat dilihat pada grafik 10 berikut: 5

FIFO PF

Latency (s)

2

0

2

4

6

8 Jumlah User

10

12

14

16

Latency Sistem Pada Kondisi Vehicular

Dari gambar 12 dapat dilihat bahwa latency sistem menggunakan FIFO scheduler lebih tinggi dibandingkan dengan PF scheduler. Latency sistem dengan FIFO scheduler mencapai 2.9243 second, sedangkan latency sistem dengan PF scheduler bernilai 0.80747 second. Pada FIFO scheduler, penjadwalan user hanya didasarkan pada user yang pertama kali datang tanpa melihat kondisi kanalnya. Secara umum layanan pada sistem CDMA 1xEV DO dapat mentolerir latency. Terjadi tradeoff pada pencapaian performansi sistem (throughput sistem) dengan latency.

6

Throughput (bps)

0

Gambar 12

7

5 4 3 2 1

0

2

4

6

Gambar 10

8 Jumlah User

10

12

14

16

Throughput Sistem Pada Kondisi Vehicular

Dari grafik gambar 10 dapat dilihat bahwa throughput sistem dengan PF scheduler lebih tinggi (2,11 Mbps) dibandingkan dengan FIFO scheduler (830 Kbps). Pada tipe kecepatan vehicular, mekanisme penjadwalan menggunakan PF scheduler dapat meningkatkan throughput sistem.

5. Kesimpulan Berdasarkan hasil simulasi yang telah dilakukan, dapat diambil kesimpulan sebagai berikut:

Analisa Latency Sistem Grafik 11 berikut menunjukkan latency sistem dengan menggunakan PF dan FIFO scheduler yang dilakukan pada daerah pedestrian:

1. Kecepatan

pergerakan user mempengaruhi throughput yang dapat dicapai oleh sistem. Pada kecepatan 0 Km/Jam, throughput sistem dengan 16 user hampir mencapai 2,5 Mbps, lebih tinggi dibandingkan throughput pada kecepatan 30 Km/Jam sebesar 1,35 Mbps, kecepatan 60 Km/Jam sebesar 0,8 Mbps, dan pada kecepatan 90 Km/Jam sebesar 0,6 Mbps. 2. Dengan bertambahnya kecepatan dan jumlah user pada suatu sistem, proses pengiriman data kepada user semakin lama sehingga latency yang dialami meningkat. Latency sistem pada kecepatan 90 Km/Jam dengan 16 user aktif mencapai 8 second, nilai tersebut lebih tinggi dibandingkan latency sistem dengan 1 user, 2 user, 4 user, dan 8 user pada kecepatan kurang dari 90 Km/Jam.

Performansi Pada kondisi pedestrian 0.9 FIFO PF

0.8 0.7 0.6

Latency (s)

1

FIFO PF

8

0

1.5

0.5

Performansi Pada kondisi vehicular

x 10

9

Performansi Pada kondisi vehicular 2.5

0.5 0.4 0.3 0.2 0.1 0

0

Gambar 11.

2

4

6

8 Jumlah User

10

12

14

16

Latency Sistem Pada Kondisi Pedestrian

3. Pada kondisi pedestrian, penggunaan PF scheduler tidak terlalu memberikan pengaruh yang signifikan terhadap penambahan throughput sistem. Throughput yang dicapai sistem saat menggunakan FIFO scheduler sama dengan saat menggunakan PF scheduler yaitu bernilai 2,11 Mbps. Pada tipe kecepatan vehicular, mekanisme penjadwalan menggunakan PF scheduler dapat meningkatkan throughput system. Throughput sistem dengan PF scheduler lebih tinggi yaitu 2,11 Mbps dibandingkan dengan FIFO scheduler yang bernilai 830 Kbps.

Dari gambar 11dapat dilihat bahwa latency PF scheduler lebih tinggi dibandingkan dengan latency FIFO scheduler. Latency sistem dengan PF scheduler mencapai 0,8 second, lebih tinggi dibandingkan dengan latency sistem dengan FIFO yaitu 0,5 second. Grafik 12 berikut menunjukkan latency sistem dengan menggunakan PF dan FIFO scheduler yang dilakukan dilakukan pada daerah vehicular:

J-5


4. Pada kondisi pedestrian, Latency sistem dengan PF scheduler mencapai 0,8 second, lebih tinggi dibandingkan dengan latency sistem dengan FIFO yaitu 0,5 second. Pada tipe kecepatan vehicular, latency sistem menggunakan FIFO scheduler lebih tinggi dibandingkan dengan PF scheduler. Latency sistem dengan FIFO scheduler mencapai 2.9243 second, sedangkan latency system dengan PF scheduler bernilai 0.80747 second. Daftar Pustaka [1 ] 3GPP2 Technical Specification Group C, [2 ]

[3 ]

[4 ]

[5 ]

[6 ]

[7 ]

“1xEV-DV Evaluation Methodology,” 3GPP2/TSGC, 2003. 3rd Generation Partnership Project 2, “CDMA2000 High Rate Packet Data Air Interface Specification,” TIA/EIA/IS-856, Version 2.0, C.S0024, Oct. 27, 2000. Budiman, Gelar., “Konfigurasi MIMO MCCDMA Pada Kanal Rayleigh Fading,” Sekolah Tinggi Teknologi Telkom, Bandung, 2005. Cao Y, Li VOK. “Scheduling Algorithms in Broad-band Wireless Networks.” Proceedings of the IEEE 2001. D. Piazza and L. Milstein, “Multiuser Diversity-Mobility Tradeoff: Modeling, and Performance Analysis of a Proportional Fair scheduling,” in Proc. IEEE Global Telecommunication, Taipei, Taiwan, November 2002. Eduardo Esteves and Qiang Wu, “The cdma2000 High Rate Packet Data System,”in QUALCOMM Incorporated 80-H05931Revision A, San Diego, U.S, March 2002. Eksim A, Sunay MO. “On scheduling for Delay Tolerant Data in HDR.” Proceedings of the IEEE International Conference on Advances in Wireless Communications, Victoria, BC, Canada, 2002

J-6

ANALISA PENJADWALAN PAKET PADA CDMA xEV-DO

Recommend Documents