ANALISA KINERJA RESOURCE-AWARE FRAMEWORK PADA ALGORITMA LIGHT-WEIGHT FREQUENT ITEM (LWF) 1
2
Jumadi M. Parenreng , Supeno Djanali , Ary M. Shiddiqi
3
Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
[email protected] 2 Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia 3 Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
1
Abstrak Online Data Stream saat ini menjadi trend komunikasi data, ini tidak terlepas dari kemampuan transfer data yang semakin cepat, sehingga memungkinkan untuk transfer live data stream. Pemanfaatan teknologi ini salah satunya dimanfaatkan oleh perangkat Wireless Sensor Network (WSN). Kendalanya adalah sumber daya (resource) yang dimiliki oleh setiap perangkat wireless berupa bateri, memory dan CPU sangat terbatas. Karena keterbatasan sumber daya maka dibutuhkan efesiensi sumber daya dengan menerapkan konsep resource-aware (RA) dan data yang didapatkan oleh perangkat wireless tidak mesti dikirimkan seluruhnya ke server pengelohan data, karena hanya akan menghabiskan sumber daya, tetapi data yang dikirim adalah data yang telah mengalami proses mining dan data yang benar-benar dibutuhkan saja. Fokus penelitian tesis ini adalah pembuktian dan analisa algoritma LW-Class dan LWF yang bekerja dengan memanfaatkan ketersediaan sumber daya yang dimiliki, banyaknya data, class dan counter yang terus berubah sesuai dengan ketersediaan memory pada waktu yang telah dispesifikasikan. Percobaan ini menggunakan data Iris dan data Vehicle yang disimulasikan pada program Java. Pada percobaan didapatkan hasil bahwa dengan menerapkan Resource-Aware membuat hasil mining data lebih baik, pemanfaatan memory dan CPU lebih efisien serta daya tahan (live time) bateri +30% lebih lama jika menerapkan konsep Resource-Aware. Adapun efesiensi LW-Class dan LWF yakni penggunaan memory lebih baik pada LWF dibanding LW-Class, tetapi daya tahan bateri, pada LW-Class +15% lebih baik dari LWF. Kata Kunci : Data Stream, Algoritma Granularity, Resource-Aware
1. Pendahuluan Perangkat jaringan terbaru dan aplikasinya, saat ini telah banyak memanfaatkan streaming data online sehingga sistem jaringan dituntut untuk selalu beroperasi secara stabil. Resource-aware framework pada konsep Online Data Mining merupakan bagian yang sangat penting untuk Wireless Sensor Network (WSN). Resource-Aware framework dapat diterapkan pada banyak teknik mining pada data yang membutuhkan monitoring secara berkelanjutan, agregasi data dan inter network processing (Datta, 2006). Sumber energi berupa Memori, CPU dan Bateri adalah bagian yang menjadikan Wireless Sensor Network dapat bekerja secara terus-menerus dalam jangka waktu lama. Tren terbaru dalam lingkup jaringan wireless yakni online data stream dimana pemrosesan data dilakukan pada perangkat wireless sensor network yang mengandalkan stream input data dengan kecepatan tinggi, kemudian pada waktu yang bersamaan pengiriman data secara update harus dilakukan dengan energi yang dimiliki. Karenanya efesiensi energi dan manajemen sumber daya (resource) adalah bagian yang sangat penting untuk teknik pemrosesan data pada jaringan ini. Gaber memperkenalkan model pengolahan data yang didasarkan pada teknik mining dengan nama Algoritma-Granularity (Gaber et al, 2004a) yakni : Light Weight Clustering (LWC), Light Weight Classification (LWClass) dan Light Weight
Frequent Item (LWF) dengan memanfaatkan ketersediaan resource berupa Memory, CPU dan Bateri. 2. Mining Pada Data Stream Data Stream didasarkan pada urutan besarnya data yang dihasilkan secara kontinyu dengan kecepatan tinggi. Salah satu karakteristik data stream adalah memungkinkan untuk selalu terupdate secara real time dengan data yang hampir tiba pada waktu yang bersamaan. Karakteristik lain data stream adalah mengalirkan item data dengan kecepatan tinggi. Hal ini bisa jadi kecepatan data lebih tinggi dibandingkan dengan kemampuan komputasi. Untuk menangani kecepatan data yang tidak seimbang ini, maka kecepatan stream data harus disesuaikan dengan kemampuan komputasi. Hal ini dapat dilakukan dengan mengurangi jumlah aliran data yang dilewatkan ke algoritma data mining (Shiddiqi, 2009a).
Gambar 1. Proses Stream Mining pada Data (Gaber et al, 2003)
Beberapa strategi mining terhadap data yang dikembangkan : pertama, adaptasi data rate pendekatan ini menggunakan sampling, filtering, aggregation dan load shedding. Kedua, konsep level output dilakukan pencocokan berdasarkan kategori output, bisa berupa penetapan ukuran tapi proses ini membuat CPU bekerja terus-menerus. Ketiga, algoritma perkiraan konsepnya berdasarkan perkiraan hasil dengan memberikan beberapa batasan error yang dapat diterima. Keempat, analisa on-board yaitu pada proses data miningnya dilakukan pada lokasi data sumber dengan maksud menghindari transfer data dalam jumlah besar. Kelima yang dikembangkan dalam penelitian ini adalah algoritma output granularity konsep ini memiliki parameter kontrol output rate dari algoritma berdasarkan ketersediaan resource komputasi. 3. Kerangka Resource-Aware Penelitian (Gaber et al, 2006) menemukan sebuah metode penyelesaian untuk setting ketersediaan resource untuk algoritma stream mining yang disebut Algoritma Granularity Setting (AGS). Metode ini terdiri dari tiga setting yang pertama, Algoritma Input Setting disebut Algoritma Input Granularity (AIG) yang mengontrol ketersediaan resource berupa Bateri. Adaptasinya dilakukan dengan Interval sampling (IS), Jika source bateri 100% maka data stream dicek secara keseluruhan tetapi jika drop sampai pada level kritis maka pada data dilakukan dengan interval data berdasarkan ketersediaan bateri yang dihitung menggunakan rumus (Shiddiqi, 2009a) : ub − lb ...............(1) SI = ub − battery batt _ crit _ Threshold Keterangan : SI = Interval Sampling ub = Upper Bound lb = Lower Bound battery = Total sisa resource bateri batt_crit_threshold = Batas kritis bateri Kedua, Algoritma Output Setting yang disebut Algoritma Output Granularity (AOG) mengontrol ketersediaan resource berupa Memory. Adaptasinya didasarkan pada Setting Radius Threshold (RT), jika ketersediaan memory berkurang di bawah batas kritis maka sistemnya akan mengurangi pemanfaatan memory dengan membatasi jumlah cluster atau counter yang terbentuk, sehingga menyisakan space memory lebih banyak. Dihitung dengan menggunakan rumus : ….(2) UB − LB RT = UB − (100 − Memory)
(100 − Mem _ Crit _ Threshold )
Keterangan : Radius Threshold = Jarak maksimum threshold UB = Upper Bound LB = Lower Bound Memory = Total memory yang terpakai Mem_Crit_Threshold = Batas kritis memory 100 = Utilitas maksimum memory (%) Ketiga, proses setting yang disebut Algoritma Process Granularity (APG) yang mengontrol ketersediaan resource berupa processor (CPU).
Adaptasinya dilakukan dengan setting Factor Random (FR), Jika CPU 100% maka stream data dicek secara keseluruhan untuk menentukan kedekatan antara data tetapi jika CPU sampai pada level kritis maka stream data diseleksi secara random. Nilai-nilainya dihitung menggunakan rumus : UB − LB .....(4) RF = (100 − CPU )
(100 − CPU _ Crit _ Threshold )
Keterangan : RF = Faktor Random Cpu_Crit_Thresh= Ambang kritis CPU LB = Lower Bound CPU = Total sisa resource CPU 100 = Utilitas maksimum CPU (%)
Gambar 2. Resource-Aware Framework
Adapun komponen utama dari Resource-Aware framework, yang pertama, Komponen Resource Monitor yang memonitor level resource. Secara umum resource yang perlu untuk dimonitor adalah level bateri, memory yang tersedia, penggunaan CPU dan Buffer komunikasi atau Bandwidth. Resource monitor menghasilkan laporan resource yang digunakan oleh AGS dalam membuat keputusan untuk parameter mining pada data jika dibutuhkan. Kedua, algoritma mining pada data yang diproses pada data stream dilakukan secara real time. Ketiga, algoritma granularity setting berfungsi untuk memutuskan parameter algoritma mining berdasarkan ketersediaan resource. 3.1 Light-Weight Classification (LWClass) LW-Class dan AGS adalah kombinasi untuk membangun teknik Resource-Aware Classification yang disebut RA-Class. Pada teknik ini, AGS memonitor secara berkala ketersediaan resource. Namun, jika ada perubahan signifikan terhadap ketersediaan sumber daya, maka AGS akan bereaksi terhadap perubahan secara langsung, untuk mencegah penurunan kinerja dan yang lebih penting lagi yakni kehilangan hasil klasifikasi terbaru. Algoritma dimulai dengan memeriksa setiap entry yang masuk dengan menggunakan algoritma LW-Class. Algoritma akan menentukan apakah entry yang masuk akan ditandai sebagai spesifik entry yang disimpan, atau akan disimpan sebagai entry baru. Fungsi algoritma update memberikan informasi jika dibutuhkan untuk mengubah setting dari algoritma LW-Class. Pada RA-Class yang diusulkan, ada tiga setting yang dapat
disesuaikan: interval sampling, factor random dan nilai radius threshold. Sampling interval berhubungan dengan level ketersediaan bateri, factor random berhubungan dengan penggunaan CPU dan nilai radius threshold berhubungan dengan sisa memory. Jika ada perubahan signifikan terhadap ketersediaan resource, maka AGS akan menghitung variable algoritma LWClass (interval sampling, faktor random, dan nilai radius threshold). Jika level bateri turun di bawah level tertentu, interval sampling akan dinaikkan. Ini akan mengurangi energi yang dihabiskan untuk memproses data stream. Jika penggunaan CPU mencapai level kritis, maka factor random akan dikurangi. Sehingga, ketika menetapkan entry masuk, maka LWClass tidak akan menguji semua entry yang tersimpan untuk mendapatkan jarak minimum. Sebaliknya, pemeriksaan secara random, berdasarkan perhitungan AGS. Terakhir, jika memory yang tersisa berkurang secara signifikan, maka nilai radius threshold akan ditingkatkan untuk mencegah pembuatan (creation) entry baru. Ini akan memperlambat penggunaan memory untuk menyimpan entri yang dipilih. Hasil resource-aware classification (RAClass) adalah daftar entry yang dapat digunakan untuk menentukan label kelas entry. Algoritmanya dituliskan seperti pada gambar 3. (Shiddiqi, 2010).
Gambar 3. Algoritma Resource-Aware Class
3.2 Light Weight Frequent Itme (LWF) Light-Weight Frequent Item (LWF) atau disebut dengan Resource-Aware Frequent Item (RAFrequent Item). (Gaber et al, 2004b) menjelaskan bahwa algoritma ini melakukan setting sejumlah frequent item yakni banyaknya data dan counter yang terus berubah berdasarkan pada kalkulasi memori yang tersedia dan nilai data rate yang selalu berubah. Algoritma diawali dengan menentukan frequent item yang akan dihitung berdasarkan ketersediaan memori. Nilai ini berubah seiring waktu untuk mengatasi data rate yang tinggi. Ide utama di balik algoritma ini adalah algoritma output granularity (AOG). AG ini mewakili banyaknya frequent item yang mana algoritmanya dapat menghitung seperti halnya pada sejumlah counter yang akan ter-reset setelah batas waktu (time threshold) yang tujuannya untuk mengatasi sifat alami data yang mengalir secara continue dari data stream. Algoritmanya menerima elemen data satu demi satu dan mencoba untuk menemukan counter untuk setiap item baru dan menambah item untuk jenis item yang telah terdaftar. Jika semua counter telah ditempati, beberapa item baru akan diabaikan dan counter akan berkurang satu (satu demi satu) sampai algoritmanya mencapai nilai ambang batas,
jumlah frequent item yang paling sedikit akan diabaikan dan counternya akan kembali direset menjadi nol. Jika item baru mirip dengan salah satu item dalam memory berdasarkan batasbatas kesamaan (similarity threshold), nilai ratarata kedua item akan dialokasikan dan counter akan bertambah satu. Parameter utama yang dapat mempengaruhi akurasi algoritma adalah batas waktu (time threshold), banyaknya frequent item akan diperhitungkan dan banyaknya item yang akan di abaikan dan counternya akan direset setelah batas waktu habis (time threshold) (Gaber et al, 2003).
Gambar 4. Algoritma LWF
4. Implementasi Algoritma RA 4.1 Arsitektur Sistem RA Dengan melakukan modifikasi arsitektur Resource-Aware Ubiquitous Data Mining (RAUDM) (Gaber et al, 2003). Algoritma ini nantinya akan menerima dan mengolah data yang diterima berdasarkan ketersediaan resource yang dimiliki. Informasi resource diperoleh dari resource aware komponen yang melakukan pengecekan dan menghitung ketersediaan sumber daya yang masih tersisa. Berdasarkan informasi ini maka mobile light weight data analisis agent melakukan proses data yang telah diterima dari data stream process dengan memanfaatkan algoritma LightWeight Classification LW-Class dan Light-weight frequent item (LWF).
Gambar 5. Arsitektur Sistem RA
4.2 Diagram Alur Sistem
Gambar 8. Grafik resource memory dengan adaptasi RA melalui radius threshold saat rilis hasil counter pada LW-Class
Gambar 6. Diagram sistem LW-Class
Gambar 8 memperlihatkan kinerja RT dalam melakukan adaptasi terhadap ketersediaan memory. Level kritis memory 70% ketika memory yang terpakai melebihi 70% maka RT secara bertahap melakukan adaptasi sesuai dengan ketersediaan memory. Semakin kecil ketersediaan memory maka adaptasi RT semakin besar. Terlihat ketika memory terpakai 83% maka besarnya nilai adaptasi RT sebesar 0.933. b. Grafik CPU dan adaptasi Factor Random (FR) pada LW-Class
Gambar 9. Grafik ketersediaan resource CPU ketika benar-benar sibuk dengan adaptasi RA melalui factor random pada LW-Class
Gambar 9 memperlihatkan adaptasi FR. Besarnya adaptasi FR berada pada 100 s.d 0, level kritis 60% yakni ketika penggunaan CPU melampaui 60% maka FR akan melakukan adaptasi untuk mengimbangi kondisi kritis CPU. Gambar 4.16 ketika CPU benar-benar sibuk dan FR berusaha mengimbangi kesibukan CPU. c. Grafik Bateri dan adaptasi Interval Sampling (IS) pada LW-Class Gambar 7. Diagram sistem LWF
5. Pengujian dan Analisa Hasil 5.1 Pengujian Skenario pengujian dirancang sedemikian rupa dan dilakukan dalam 12 kali pengujian, menggunakan Data Iris dan Data Vehicle dengan menerapkan algoritma LW-Class dan LWF. 5.2 Analisa Hasil 5.2.1 Algoritma LW-Class dengan Data Iris a. Grafik Memory dan adaptasi Radius Threshold (RT) pada LW-Class
Gambar 10. Grafik ketersediaan resource bateri ketika melampaui level kritis dengan adaptasi RA melalui interval sampling pada LW-Class
c. Grafik Bateri dan adaptasi Interval Sampling (IS) pada LWF
Gambar 10 memperlihatkan level kritis bateri yang disetting sebesar 40% ketika ketersediaan bateri sisa 40% maka secara bertahap IS akan melakukan adaptasi yang persentase kenaikannya berdasarkan ketersediaan bateri. Level adaptasi IS dimulai 1000 s.d 2500 ms yakni pada data dilakukan pengecekan dengan interval waktu antara 1 detik sampai 2.5 detik ketika bateri benarbenar kritis. Pada percobaan dengan adaptasi RA, bateri dapat bertahan lebih lama 245 detik jika dibandingkan dengan tanpa adaptasi RA. 5.2.2 Algoritma LWF dengan Data Iris a. Grafik Memory dan adaptasi Radius Threshold (RT) pada LWF
Gambar 13. Grafik ketersediaan resource bateri ketika melampaui level kritis dengan adaptasi RA melalui interval sampling pada LWF
Gambar 13 memperlihatkan kondisi ketika bateri memasuki masa kritis. Dengan adaptasi RA, IS secara bertahap melakukan adaptasi yang dimulai dari 1000 s.d 2500 ms. Pada percobaan terlihat jelas dengan adaptasi RA melalui IS daya tahan bateri (live time) dapat beratahan sampai 155 detik lebih lama dari percobaan tanpa adaptasi RA.
Gambar 11. Grafik resource memory dengan adaptasi RA melalui radius threshold saat rilis hasil counter pada LWF
Pada Gambar 11 pengujian dengan Level kritis memory 70% dan adaptasi RT 0.5 s.d 1.5. Nampak pada hasil percobaan tanpa RA penggunaan memory pada LWF lebih stabil terlihat dengan hasil percobaan rata-rata konsumsi memory tidak melebihi 80%. Ketika penggunaan memory 75%, maka secara bertahap RT melakukan adaptasi sebesar 0.666 b. Grafik CPU dan adaptasi Factor Random (FR) pada LWF
Gambar 12. Grafik ketersediaan resource CPU ketika sibuk dengan adaptasi RA melalui factor random pada LWF
Gambar 12 memperlihatkan grafik ketika CPU mulai memasuki masa kritis saat prosesnya melebihi level kritis 60% adaptasi RF dengan interval adaptasi antara 100 s.d 0 berusaha mengimbangi tingkat kesibukan CPU, sehingga dengan adaptasi FR membuat proses CPU lebih stabil jika dibandingkan dengan tanpa adaptasi RA.
6. Kesimpulan Beberapa hal yang menarik dijadikan sebagai kesimpulan, setelah melakukan percobaan di atas dengan beberapa variasi pengujian, yaitu : • Adaptasi resource-aware terbukti lebih efisien dalam memanfaatkan resource baik untuk penerapan algoritma Light-Weight Classification (LW-Class) juga untuk algoritma Light-Weight Frequent Item (LWF). • Efesiensi waktu dengan adaptasi resourceaware (RA) rata-rata 30% s.d 40% lebih efisien. • Efesiensi penggunaan memory, LWF lebih irit dan stabil dibanding LW-Class tetapi untuk efesiensi waktu LW-Class lebih baik dibandingkan dengan LWF. • Untuk inplementasi ke perangkat untuk area dengan fariasi data terlalu banyak, maka pemanfaatan LW-Class kurang baik karena kerja memory akan berat dan hanya akan melaporkan data yang betul-betul dominant saja. Semenatara pada LWF pemanfaatan memory lebih stabil dan hasilnya lebih merata. Daftar Pustaka Akkaya, Kemal., and Newell, Andrew. (2009), Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks, Department of Computer Science, Southern Illinois University Carbondale, Carbondale, IL 62901, United States Burl M., Fowlkes C., Roden J., Stechert A., and Mukhtar S. (1999), Diamond Eye: A distributed architecture for image data mining. In SPIE DMKD, Orlando, April (1999)
Charu C. Aggarwal. (2007), Data Stream : Model and Algorithms IBM T. J. Watson Research Center, Hawthorne, NY 10532 Datta, Souptik., Bhaduri, Kanishka., Giannella, Chris., Wolff, Ran., Kargupta, Hillol. (2006), Distributed Data Mining in Peerto-Peer Networks, Dept. of Computer Science & Electrical Engineering, University of Maryland Baltimore County Baltimore, MD, USA Gaber, Mohamed Medhat., Krishnaswamy, Shonali., Zaslavsky Arkady. (2003), Adaptive Mining Techniques for Data Streams using Algorithm Output Granularity, School of Computer Science and Software Engineering, Monash University, 900 Dandenong Rd, Caulfield East, VIC3145, Australia Gaber, Mohamed Medhat., Krishnaswamy, S., and Zaslavsky, A. (2004a), Cost-Efficient Mining Techniques for Data Streams. First Australasian Workshop on Data Mining and Web Intelligence (DMWI 2004). Held in conjunction with the Australasian Computer Science Week (ACSW 2004), Dunedin, New Zealand, 2004 Gaber, Mohamed Medhat., Yu, P. S. (2006), A framework for resource-aware knowledge discovery in data streams: a holistic approach with its application to clustering. Proceedings of the 2006 ACM Symposium on Applied Computing (SAC '06), April 23 - 27, 2006, Dijon, France, ACM, New York, NY; p. 649-56. Gaber, Mohamed Medhat., Krishnaswamy, Shonali., and Zaslavsky, Arkady. 2004b), A Wireless Data Stream Mining Model, 1 School of Computer Science and Software Engineering, Monash University, 900 Dandenong Rd, Caulfield East, VIC3145, Australia Kargupta. H. (2003), VEhicle DAta Stream Mining (VEDAS) Project. Entry from http://www.cs.umbc.edu /% 7Ehillol/vedas.html. IOS., Euclidean Distance Metric and Manhattan Distance Entry from http://www.improvedoutcomes.com/docs/ WebSiteDocs/Clustering/Clustering_Para meters/Manhattan_Distance_Metric.htm Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., Anderson, J. (2002), Wireless sensor networks for habitat monitoring. In st Proceedings of the 1 ACM International Workshop on Wireless Sensor Networks and Applications (Atlanta, Georgia, USA, September 28 - 28, 2002). WSNA '02. ACM, New York, NY, p. 88-97 McConnell S., Skillicorn D. (2005), A Distributed Approach for Prediction in Sensor Networks. In Proceedings of 1st International Workshop on Data Mining in Sensor Networks as part of the ISAM International Conference on Data Mining, 2005, p. 28-37
Mowforth, Pete., and Shepherd, Barry., Statlog (Vehicle Silhouettes) Data Set Entry from http://archive.ics.uci.edu/ml/datasets/St atlog+(Vehicle+ Silhouettes) Phung, N. D., Gaber, M. M., Röhm, U. (2007), Resource-aware Distributed Online Data Mining for Wireless Sensor Networks, Computational Intelligence and Data Mining 2007 (CIDM 2007), March 1, 2007-April 5, 2007, p.139 – 146 Röhm U, Gaber M, M., Tse, Q. (2008), “Enabling resource-awareness for in-network data processing in wireless sensor networks”, Proceedings of the Nineteenth Conference on Australasian Database - Volume 75; December 03 04, 2007; Gold Coast, Australia: Australian Computer Society, Darlinghurst, Australia; p. 107-14 Shiddiqi, Ary Mazharuddin. (2009a), “ResourceAware data stream classification in wireless sensor network”, faculty of Information Technology, Monash University, july 2009 Shiddiqi, Ary Mazharuddin. (2009b), Performance Measurement of Resource-aware Framework in Online Data Stream Mining, Informatics Department, Faculty of Information Technology, Sepuluh Nopember Institute of Technology Shiddiqi, Ary Mazharuddin., Gaber, Mohamed Medhat. (2010), Light Weight Resource-Aware Data Stream Classification, Sepuluh Nopember Institute of Technology, Surabaya, Indonesia, Monash University, Melbourne, Australia, IEEE Magnetics Letters, Volume 1 (2010). Tanner S., Alshayeb M., Criswell E., Iyer M., McDowell A., McEniry M., Regner K. (2002), EVE: On-Board Process Planning and Execution, Earth Science Technology Conference, Pasadena, CA, Jun. 11 - 14, (2002) Travis, Greg. (1997), Create BitInputStream and BitOutputStream Classes, Entry from http://www.devx.com/java/free/articles/g t052002/gt052002-1.asp Wales, Jimmy., and Snow, Michael. (2009), Ordinal Data Type, Entry from http://en.wikipedia.org/wiki/Ordinal_dat a_type Werner-Allen, G., Lorincz, K., Ruiz, M., Marcillo, O., Johnson, J., Lees, J., Welsh, M. (2006), Deploying a wireless sensor network on an active volcano, Internet Computing, IEEE, Volume 10, Issue 2, March-April, 2006, p.18 – 25
