ALGORITMA LEAST RECENTLY USED UNTUK PEMBENTUKAN CACHE DALAM PENGAKSESAN WEB SERVICE STUDI KASUS TRANSJOGJA

ALGORITMA LEAST RECENTLY USED UNTUK PEMBENTUKAN CACHE DALAM PENGAKSESAN WEB SERVICE STUDI KASUS TRANSJOGJA Kristian Adi Nugraha(1) [email protected]

Budi Susanto(2) [email protected]

Antonius Rachmat Chrismanto(3) [email protected]

Abstract Transjogja, a busway transportation system, is widely used by people for traveling in Yogyakarta. Because of increasing number of Transjogja shelters, using Transjogja becomes more and more complicated for people. Therefore, the authors propose a solution by designing a location-based mobile application, which can provide information about Transjogja. The system is built using a Web Service in order to support a large number of outstanding mobile platforms. For the optimization of Web Service access, the authors implement a cache in the client application in order to speedup Web Service access time. Keywords: cache, LRU, mobile, web service Abstrak Transjogja merupakan sarana transportasi busway yang banyak digunakan oleh masyarakat Yogyakarta untuk bepergian. Namun semakin lama jumlah shelter dan jalur Transjogja semakin bertambah, sehingga hal ini akan menyulitkan masyarakat ketika akan pergi dengan menggunakan Transjogja. Karenanya, penulis mencoba membuat sebuah solusi dengan merancang sebuah aplikasi mobile berbasis lokasi yang dapat memberikan layanan informasi mengenai Transjogja. Sistem ini dibangun dengan menggunakan basis Web Service agar dapat mendukung banyaknya jumlah platform mobile yang beredar. Kemudian untuk optimalisasi pengaksesan Web Service, maka penulis mengimplementasikan penggunaan cache didalam aplikasi client agar dapat meningkatkan waktu untuk pengaksesan Web Service. Keywords: cache, LRU, mobile, web service

1. Pendahuluan Dewasa ini masyarakat Yogyakarta banyak menggunakan Transjogja dibanding dengan sarana transportasi yang lainnya. Hal ini disebabkan karena Transjogja dapat menjangkau hampir seluruh daerah serta tarifnya yang cukup terjangkau. Namun seiring dengan pengembangan Transjogja itu sendiri, semakin bertambah pula jumlah 1

Prodi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Kristen Duta Wacana Dosen, Prodi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Kristen Duta Wacana 3 Dosen, Prodi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Kristen Duta Wacana 2

93

shelter dan jalur Transjogja yang berdampak pada semakin rumitnya sistem penjaluran Transjogja. Melihat permasalahan diatas, penulis mencoba memberikan solusi dengan merancang sebuah aplikasi mobile berbasis lokasi yang dapat membantu memberikan layanan informasi mengenai Transjogja kepada para penggunanya. Dengan adanya aplikasi ini, diharapkan pengguna tidak akan kesulitan lagi dalam mencari shelter dan jalur yang harus ditempuh dalam menggunakan jasa Transjogja. Penelitian ini bertujuan untuk mengimplementasikan teknik caching untuk pengaksesan Web Service dalam menyediakan layanan informasi terhadap aplikasi LBS yang digunakan ketika pengguna hendak pergi ke suatu lokasi dengan menggunakan Transjogja. Sehingga dengan adanya aplikasi ini, pengguna tidak perlu kesulitan dalam mencari shelter dan rute Transjogja yang tepat ketika hendak pergi ke suatu tempat Berdasarkan latar belakang yang telah dikemukakan pada bagian sebelumnya, maka permasalahan yang akan diteliti oleh penulis adalah sebagai berikut : 1. Bagaimana cara membangun komunikasi yang reliable antara aplikasi LBS dengan Web Service dengan menggunakan teknik caching? 2. Bagaimana cara menentukan rute terpendek dari shelter keberangkatan pengguna menuju ke shelter tujuan pengguna? Ruang lingkup pembahasan makalah ini adalah implementasi algoritma Least Recently Used (LRU) pada cache aplikasi mobile dalam pengaksesan Web Service. Permasalahan yang dibahas dalam makalah ini adalah mengenai layanan informasi Transjogja.

2. Batasan Masalah Permasalahan yang akan dibahas dalam penelitian ini dibatasi sebagai berikut : 1. Penelitian ini hanya membahas mengenai jarak tempuh dan rute yang ditempuh. 2. Aplikasi client yang dibangun dalam penelitian ini berbasis Android. 3. Informasi yang disimpan dalam cache hanya informasi rute terpendek.

3. Landasan Teori 3.1. Location Based Service (LBS) Pada penelitian yang dilakukan oleh Deidda, Pala, dan Vacca (2010), menyatakan bahwa Location Based Service (LBS) adalah “... salah satu kategori layanan yang bisa diakses melalui perangkat bergerak dan berbasiskan kondisi lokasi geografis dari perangkat tersebut pada saat itu ....” (hal 1). Informasi yang diberikan oleh LBS sangat bergantung terhadap posisi yang dikirimkan oleh penggunanya, sehingga setiap lokasi memiliki informasi masing-masing yang bersifat unik. 3.2. Web Service Menurut glosari W3C, definisi Web Service adalah “... sebuah sistem perangkat lunak yang didesain untuk mendukung interoperabilitas interaksi antara mesin dengan mesin melalui jaringan. Web Service memiliki sebuah antarmuka yang dideskripsikan dalam sebuah format yang dapat diproses oleh sebuah mesin. Sistem lain berinteraksi dengan Web Service menggunakan SOAP melalui prosedur yang telah dideskripsikan,

94

biasanya menggunakan HTTP dengan serialisasi Extensible Markup Language (XML) dalam hubungannya dengan standar web terkait yang lain.” Dengan menggunakan XML dalam standar pengiriman pesan membuat Web Service mendukung komunikasi cross-platform, sehingga sistem yang memiliki platform berbeda tetap dapat saling berkomunikasi. 3.3. Simple Object Access Protocol (SOAP) Menurut Newcomer definisi Simple Object Access Protocol (SOAP) adalah “... penyedia layanan komunikasi pada antarmuka sebuah Web Service untuk dapat berkomunikasi dengan sistem lain melalui internet atau jaringan yang lain.” (2002, hlm. 4). SOAP digunakan sebagai sarana untuk mengirim request dari client kepada Web Service serta mengirimkan respon dari Web Service kepada client dengan menggunakan pesan berbentuk XML. 3.4. Cache Teknik caching memungkinkan sebuah sistem untuk menggunakan ulang informasi yang dibutuhkan dengan cara mengambil informasi disimpan dalam sebuah media penyimpanan khusus apabila informasi tersebut pernah digunakan sebelumnya. Dengan demikian secara otomatis waktu yang dibutuhkan oleh sebuah sistem dalam menampilkan informasi akan lebih cepat dibandingkan dengan apabila memproses ulang untuk mendapatkan informasi tersebut. Dalam penelitian ini, pembentukan cache dilakukan pada database yang terdapat pada aplikasi client. 3.5. Least Recently Used (LRU) LRU merupakan salah satu algoritma yang cukup baik dalam page replacement. Menurut Laplante (2004), LRU menganut sebuah prinsip yang cukup sederhana, yaitu membuang proses yang paling jarang digunakan dari sekumpulan proses-proses yang ada. Karena algoritma ini mengasumsikan bahwa proses yang baru saja dijalankan kemungkinan besar akan dijalankan kembali dalam waktu dekat.

Gambar 1. Skema Algoritma LRU (Osvaldo G. & Marina G (Eds). (2007). Computational Science and Its Applications - ICCSA 2007: International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007, hlm. 203.)

Pada gambar diatas, terdapat delapan proses yang diurutkan berdasarkan proses yang paling terakhir diakses (p1) hingga proses yang pertama kali diakses (p8) dari kiri kanan. Apabila pada kasus tersebut terdapat sebuah proses baru p9 yang akan diproses oleh sistem, maka proses p9 akan ditempatkan di sebelah kiri proses p1 dan proses p8 akan dibuang dari daftar antrian proses. 3.6. Algoritma A* (A Star)

95

A* merupakan salah satu algoritma yang digunakan untuk menyelesaikan permasalahan jarak pada sebuah graf yang terdiri dari node/verteks dan edge. Dalam penelitian ini, A* digunakan dalam mencari rute terbaik dari posisi pengguna menuju ke lokasi tujuan. Menurut Russel dan Norvig (2003) Algoritma A* merupakan “bentuk yang paling dikenal dari metode best-first search. Algoritma A* bekerja dengan cara menjumlahkan biaya yang dikeluarkan dari posisi saat ini untuk mencapai ke node n yaitu g(n) dengan biaya yang diperlukan dari node n menuju ke node tujuan, yaitu h(n) ”. Dengan demikian, maka perhitungan dari Algoritma A* dapat dirumuskan sebagai berikut : [1] f(n) = biaya total yang dikeluarkan untuk mencapai node n g(n) = biaya yang dikeluarkan dari node keberangkatan menuju node n h(n) = biaya yang dikeluarkan dari node n menuju goal (nilai heuristik) Biaya pada nilai g(n) dan h(n) merupakan segala sesuatu yang harus dikeluarkan atau dibayarkan ketika hendak pergi menuju node n dari node saat ini. Representasi bentuk dari biaya tersebut dapat berupa waktu, jarak tempuh, jumlah langkah, dan sebagainya. Node yang dipilih sebagai node tujuan berikutnya adalah node dengan nilai f(n) yang paling rendah. Semakin kecil nilai dari f(n), maka semakin kecil biaya yang dikeluarkan untuk menuju ke node n. Pada penelitian ini, nilai heuristik yang digunakan adalah jarak dari node n menuju ke node goal dalam satuan meter. Hal tersebut akan menunjukkan bahwa semakin kecil nilai heuristik, maka semakin dekat jarak dari node n menuju ke node goal.

4. Hasil dan Pembahasan 4.1 Perancangan Pada Gambar 2 dijelaskan bahwa aplikasi yang akan dibangun dibagi menjadi dua bagian besar yaitu aplikasi client yang berupa aplikasi berbasis mobile dan aplikasi server yang berbentuk Web Service, dimana keduanya terhubung melalui sebuah jaringan internet. Web Service terhubung langsung ke sebuah database yang menyimpan seluruh informasi mengenai lokasi shelter dan rute Transjogja. Aplikasi client dapat mengakses fungsi-fungsi yang telah disediakan pada Web Service untuk mendapatkan informasi yang diinginkan.

96

Gambar 2. Gambar Rancangan Arsitektur Sistem Cara kerja sistem dimulai dari aplikasi client yang melakukan request dengan cara memanggil fungsi pada Web Service dengan nilai parameter yang telah ditentukan. Web Service yang menerima permintaan tersebut kemudian mengolah nilai parameter yang diterima melalui fungsi yang dipanggil oleh client, kemudian informasi dari hasil pengolahan data tersebut dikirimkan kepada client. Client dapat langsung menampilkan informasi hasil kembalian dari Web Service, dan jika memungkinkan client dapat menyajikan informasi tersebut dalam bentuk peta dengan bantuan Google Maps API. 4.2 Antarmuka Aplikasi mobile yang dibangun pada platform Android memiliki tampilan awal sebagai berikut.

Gambar 3. Tampilan Menu Utama Aplikasi Client

97

Pada tampilan tersebut terdapat tiga buah menu utama, yaitu menu untuk memilih lokasi tujuan, menu untuk melihat rute yang disarankan, dan menu untuk melihat peta. Pada menu untuk memilih lokasi tujuan, tersedia sebuah kolom untuk memasukkan nama lokasi yang ingin dituju.

Gambar 4. Tampilan Menu ‘Destination’ Aplikasi Client Sedangkan menu untuk melihat rute yang disarankan akan menampilkan informasi rute terbaik yang diproses dengan menggunakan Algoritma A*.

Gambar 5. Tampilan Menu ‘Directions’ Aplikasi Client Informasi pada menu ini diperoleh melalui Web Service. Namun apabila pada cache aplikasi client terdapat request serupa, maka informasi diambil dari cache tersebut. Kemudian menu peta digunakan untuk melihat peta informasi pengguna saat itu.

98

Gambar 6. Tampilan Menu ‘Map’ Aplikasi Client 4.3 Analisis dan Pengujian Algoritma A* membutuhkan nilai heuristik untuk proses perhitungannya. Nilai tersebut didapat dari jarak garis lurus antara shelter yang dikunjungi dengan shelter tujuan dalam satuan meter. Pengujian algoritma A* dilakukan dengan cara melakukan request dari satu shelter ke shelter lain. Setiap iterasi proses pada sebuah request disimpan pada sebuah file log. Kemudian dilakukan pengamatan terhadap file log tersebut agar dapat terlihat proses-proses di dalamnya. Salah satu contoh isi dari file log tersebut adalah sebagai berikut ini.

99

17-11-2011 04:26:42 :: Fungsi countFinalDistance 17-11-2011 04:26:42 :: id_shelter_asal = 1, nama_shelter 17-11-2011 04:26:42 :: id_shelter_tujuan = 10, nama_shelter 17-11-2011 04:26:42 :: --- TREE 1 --Array Sudirman 2 (1A),f = 1516.1996280701 Cik Di Tiro 2 (2A),f = 1680.645856908

= Sudirman 1 = Mangkubumi 2

17-11-2011 04:26:42 :: Lowest Cost : Sudirman 2 (1A),f = 1516.1996280701

17-11-2011 04:26:42 :: --- TREE 2 --Array Array Mangkubumi 1 (1A),f = 1683.462403096 Cik Di Tiro 2 (2A),f = 1680.645856908 17-11-2011 04:26:42 :: Lowest Cost : Cik Di Tiro 2 (2A),f = 1680.645856908

17-11-2011 04:26:42 :: --- TREE 3 --Array Array Mangkubumi 1 (1A),f = 1683.462403096 Array Jl. Colombo (Kosud Gama) (1B),f = 3289.031940843 Jl. Colombo (Kosud Gama) (2A),f = 3289.031940843 17-11-2011 04:26:42 :: Lowest Cost : Mangkubumi 1 (1A),f = 1683.462403096 17-11-2011 04:26:42 :: --- TREE 4 --Array Array Array Mangkubumi 2 (1A),f = 1700.0949307305 Mangkubumi 2 (2A),f = 1700.0949307305 Array Jl. Colombo (Kosud Gama) (1B),f = 3289.031940843 Jl. Colombo (Kosud Gama) (2A),f = 3289.031940843 17-11-2011 04:26:42 :: Lowest Cost : Mangkubumi 2 (1A),f = 1700.0949307305 17-11-2011 04:26:42 :: Detail Shelter Sudirman 1 (1A)#Sudirman 2 (1A)#Mangkubumi 1 (1A)#Mangkubumi 2 17 11 2011 04:26:42 :: End of countFinalDistance

Gambar 7. Isi File ‘log.txt’ untuk Tracking Penentuan Rute Terpendek Pengujian pada cache dilakukan dengan cara melakukan permintaan rute sebanyak 30 kali secara acak, dimana besar kapasitas cache yang diuji adalah 9 dan total nama lokasi tujuan yang digunakan dalam permintaan rute adalah 13 nama. Dari pengujian tersebut, didapatkan hasil sebagai berikut (dihitung dalam satuan milisecond). Tabel 1. Pengujian LinkedHashMap Cache No 1. 2. 3. 4. 5. 6. 7.

Nama Lokasi Rumah Sakit Bethesda Candi Prambanan Stasiun Tugu Jogjakarta Jalan Malioboro Terminal Prambanan Malioboro Mall Universitas Negeri Yogyakarta (UNY)

100

1 299 463 401 328 407 254 481

2 0,34 264 0,55 0,37 0,40

3 292 0,34 0,40

4

5

0,31

0,34

8.

SGM

9. 10. 11. 12.

Bundaran SAMSAT Benteng Vredeburg Kraton Kantor Kedaulatan Rakyat Taman Makam Kusumanegara

13.

Pahlawan

2014 6 325 434

0,15 0,34

1195

0,37

0,31

0,31

554

0,46

0,34

0,37

Hasil pengujian pada tabel 1 menunjukkan bahwa selisih waktu yang ditunjukkan antara pengambilan data melalui cache dan melalui Web Service cukup signifikan, dimana untuk menyimpan sebuah data pada cache diperlukan kapasitas sebesar 108 bytes. Secara keseluruhan, rata-rata waktu pengaksesan adalah 1887,6 milisecond. Rata-rata waktu yang dibutuhkan untuk memperoleh informasi dari Web Service adalah sekitar 375 milisecond, sedangkan rata-rata waktu yang dibutuhkan untuk mengambil kembali informasi-informasi tersebut pada cache adalah sekitar 0,35 milisecond. Bahkan untuk data dari Web Service yang diambil dalam waktu cukup lama, yaitu data nomor 12 dengan lokasi tujuan “Kantor Kedaulatan Rakyat”, memakan waktu 1159 milisecond. Namun ketika data tersebut diambil kembali pada cache, waktu yang dibutuhkan tidak jauh berbeda dari nilai rata-rata waktu pengaksesan pada cache, yaitu sekitar 0,31 milisecond dan 0,37 milisecond. Hal ini menunjukkan bahwa lama atau tidaknya sebuah data diambil pada Web Service, tidak akan berpengaruh terhadap lama waktu yang dibutuhkan ketika mengakses kembali data tersebut pada cache. Karenanya, semakin lama waktu yang dibutuhkan untuk mengambil data pada Web Service, maka akan semakin terasa pula manfaat dari keberadaan cache.

5. Kesimpulan dan Saran 1. Penggunaan cache memberikan dampak yang cukup signifikan karena dapat meningkatkan waktu pengaksesan hingga seribu kali lebih cepat. Cache juga berfungsi untuk mengurangi beban kerja server, karena dengan adanya cache maka akan semakin sedikit permintaan yang dikerjakan oleh server. Terlebih apabila Web Service telah dikembangkan untuk banyak platform, maka dengan adanya cache pada client akan terasa dampaknya. 2. Nilai heuristik yang digunakan dalam perhitungan algoritma A* dinilai sudah tepat karena dapat membantu memberikan saran rute terbaik dengan tingkat keberhasilan sebesar 100%. 3. Aplikasi yang dibangun dengan basis Web Service dapat mendukung bermacammacam platform sekaligus. Namun karena keterbatasan waktu, penulis hanya mengembangkan aplikasi untuk platform Android. Sehingga untuk pengembangan berikutnya aplikasi client dapat dikembangkan agar dapat mendukung platform ponsel yang lain seperti iOS, Symbian, Windows Phone, dan Blackberry. 4. Sistem dapat dikembangkan agar dapat mendukung perhitungan waktu tempuh berdasarkan tingkat kepadatan jalan raya pada jam-jam tertentu. Sehingga selain memperhitungkan jarak terpendek sistem juga dapat menggunakan waktu tempuh yang paling singkat sebagai pertimbangan dalam pengambilan keputusan.

101

Daftar Pustaka Budiawan, T., Santoso, I., & Zahra, A.A. (2011). Mobile Tracking GPS (Global Positioning System) Melalui Media SMS (Short Message Service). Undergraduate Thesis. Diakses pada tanggal 18 Agustus 2011 dari http://eprints.undip.ac.id/25228/1/ML2F004518.pdf Definisi Android & Android SDK. Diakses pada tanggal 19 Agustus 2011 dari http://developer.android.com/guide/basics/what-is-android.html Haas, H., & Brown, A. (2004). Web Services Glossary. Diakses pada tanggal 23 Agustus 2011 dari http://www.w3.org/TR/ws-gloss/ Deidda, M., Pala, A., & Vacca, G. (2010). A Tourist Location Based Service (LBS) for The Cagliari City. Dalam M.A. Brovelli, S. Dragicevic, S. Li, & B. Veenendaal (Eds), International Society for Photogrametry and Remote Sensing (ISPRS) Volume XXXVIII-4/W13. Diakses pada tanggal 18 Agustus 2011 dari http://www.isprs.org/proceedings/XXXVIII/4-W13/ID_06.pdf Deitel, H. M., Deitel, P. J., & Nieto, T.R. (2001). Internet & World Wide Web How to Program (2nd Edition). United-States : Prentince Hall. Gallaugher, J., & Ramanathan, S. (1996). The Critical Choice of Client Server Architecture: A Comparison of Two and Three Tier Systems. Dalam Warren, Gorham, & Lamont (Eds), Information Systems Management (New York, Auerbach Publications). Diakses pada 18 Agustus 2011 dari https://www2.bc.edu/~gallaugh/research/ism95/cccsa.html Laplante, P. A. (2004). Real-Time Systems Design and Analysis. United States : Wiley-IEEE Press. Newcomer, E. (2002). Understanding Web Services : XML, WSDL, SOAP, and UDDI. Canada : AddisonWesley Professional. Panggabean, T. B. I., Suryadharma, Y., & Nugroho, P. (2006). Penyelesaian Permasalahan 8 Puzzle dengan Menggunakan Algoritma A* (A Star). Dalam Makalah Mahasiswa Tahun 2006. Bandung : ITB. Diakses pada 14 Oktober 2011 dari http://www.informatika.org/~rinaldi/Stmik/20052006/Makalah2006/MakalahStmik2006-01.pdf. Parsons, D., & Newnham, J. (2006). A Web Services Architecture for Rich Content Mobile Learning Client. Diakses pada 19 Oktober 2011 dari http://www.massey.ac.nz/~dpparson/acis%202006.pdf Priyambodo, T.K. (2005). Implementasi Web-Service untuk Pengembangan Sistem Layanan Pariwisata Terpadu. Dalam SNATI Tahun 2005. Diakses pada 13 Oktober 2011 dari http://journal.uii.ac.id/index.php/Snati/article/viewFile/1311/1071 Russel, S.J., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, New Jersey : Prentice Hall. Wessels, D. (2001). Web Caching. Canada : O’Reilly. Yoo, Y.S., Lee, H., Ryu, Y., & Bahn, H. (2007). Page Replacement Algorithm for NAND Flash Memory Storages. Dalam Osvaldo G. & Marina G (Eds), Computational Science and Its Applications - ICCSA 2007: International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Kuala Lumpur : Springe

102