SISTEM PENENTUAN POSISI DI DALAM RUANGAN DENGAN METODE FINGERPRINT (KNN) BERBASIS KUAT SINYAL WLAN

Seminar Nasional Teknologi Informasi dan Multimedia 2015

ISSN : 2302-3805

STMIK AMIKOM Yogyakarta, 6-8 Februari 2015

SISTEM PENENTUAN POSISI DI DALAM RUANGAN DENGAN METODE FINGERPRINT (KNN) BERBASIS KUAT SINYAL WLAN Eko Suripto Pasinggi1), Selo Sulistyo2), Bimo Sunarfri Hantono3) e-Systems Lab, Jurusan Teknik Elektro dan Teknologi Informasi Universitas Gadjah Mada Jalan Grafika No 2, Kampus UGM Yogyakarta 55281 Email : [email protected]), [email protected]), [email protected]) Abstrak Context-aware system merupakan sistem yang bekerja berdasarkan lokasi. Teknologi GPS sebagai teknologi yang paling luas digunakan tidak dapat bekerja secara maksimal di dalam ruangan. Oleh sebab itu dibutuhkan sistem penentuan posisi yang berkerja untuk kebutuhan di dalam ruangan. Teknologi WLAN dapat dimanfaatkan untuk kebutuhan tersebut. Dalam paper ini akan dibahas mengenai pemanfaatan WLAN dengan metode fingerprint (KNN) untuk melakukan penentuan posisi. Selain itu dilakukan beberapa percobaan untuk meningkatkan kemampuan metode tersebut. Pengujian yang dilakukan menunjukkan hasil berupa tingkat akurasi sistem yang dapat mencapai 1,45 m dan presisi 84 % untuk tingkat akurasi 2 meter. Percobaan penerapan algoritme WKNN mempu meningkatkan akurasi namum kecil, sedangkan clustering mempu menurunkan beban komputasi. Kata kunci: Ubiquious, Context-aware, Location-aware, kNN, Fingerprint, Euclidean. 1. Pendahuluan Ubiquitous computing merupakan sebuah konsep teknologi masa depan yang saat ini sedang dikembangkan melalui berbagai penelitian. Salah satu komponen ubiquitous computing adalah context-aware system, yaitu sistem bekerja berdasarkan context. Context merupakan informasi yang digunakan untuk menyatakan karakteristik suatu entitas dan bersifat relevan terhadap interaksi penguna dan aplikasi [1]. Posisi merupakan salah satu aspek Context yang penting dan sering digunakan [2]. Ubiquitous sistem harus memperoleh informasi context dengan tepat untuk menydiakan layanan yang sesuai [3]. Konsep location-aware telah diimplementasikan untuk berbagai kebutuhan seperti aplikasi untuk menunjukkan boarding gate kepada penumpang pesawat, membantu seorang siswa menemukan ruang kelas, membantu menemukan suatu produk saat berbelanja di supermarket, pemandu perjalanan, pendeteksian posisi produk pada gudang, pelacakan peralatan medis dirumah sakit, dan

pendeteksian posisi petugas pemadam kebakaran dalam gedung yang terbakar [4], [5]. Teknologi Global Positioning System (GPS) adalah teknologi penentuan posisi yang paling luas digunakan saat ini dan menjadi teknologi standar untuk penentuan posisi. GPS mampu memberikan tingkat akurasi yang tinggi untuk penggunaan di luar ruangan, namun akan menemukan tantangan yang signifikan untuk penggunaan di dalam ruangan [6], [7]. GPS tidak dirancang untuk penggunaan di dalam ruangan karena kondisi tersebut tidak memungkinkan terjadinya transmisi yang tidak terhalang (Line of Sigh) antar perangkat dan satelit [8]. Beberapa penelitian menunjukkan bahwa penentuan posisi di dalam ruangan memungkinkan untuk dilakukan dengan menggunakan teknologi wireless lainnya, misalnya WLAN, Infrared, dan RFID [6], [9], [10]. Teknologi WLAN sangat cocok digunakan untuk membuat sistem ini karena saat ini teknologi ini telah banyak terpasang diberbagai bangunan sehingga dapat meminimalkan biaya. Selain itu, teknologi WLAN juga didukung oleh perangkat-perangkat mobile sebagai fitur standar. Algoritme KNN, yang merupakan salah satu algoritme dasar dalam data mining (klasifikasi), dapat dimanfaatkan dalam metode fingerprint. Metode fingerprint bekerja dengan dengan cara melakukan pencocokan suatu masukan dengan data yang telah dimiliki. Paper ini terdiri dari 5 bab. Bab 2 menjelaskan mengenai parameter yang akan digunakan untuk melakukan evaluasi pada percobaan. Metode yang akan diterapkan pada sistem akan dijelaskan pada Bab 3 dan akan dievaluasi pada Bab 4. Kesimpulan dari hasil evaluasi akan disajikan pada Bab 5. 2. Parameter evaluasi Untuk melakukan evaluasi terhadap suatu sistem penentuan posisi dibutuhkan beberapa parameter sebagai pembanding. Menurut [5], [8] dan [11] evaluasi dapat menggunakan parameter akurasi, presisi, dan waktu komputasi.

4.4-93

ISSN : 2302-3805

Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015

a. Akurasi Sebagai sistem yang memberikan informasi berupa posisi, kriteria yang paling dibutuhkan adalah tingkat ketepatan atau akurasi penentuan posisi. Akurasi merujuk pada tingkat kesalahan yang dapat ditentukan dengan membandingkan antara posisi perkiraan dan posisi sesungguhnya. Akurasi dinyatakan dalam satuan jarak, misalnya tingkat akurasi 1 meter, yang berarti rata-rata perbedaan antar posisi perkiraan dengan posisi sesungguhnya adalah 1 meter. b. Presisi Presisi menyatakan tingkat kemungkinan suksesnya perkiraan yang berdasar pada tingkat akurasi yang ditentukan. Presisi menggambarkan konsistensi kerja sebuah sistem. presisi dapat dinyatakan dalam bentuk persentase, misalnya akurasi 1 meter dan presisi 90 % berarti sistem dapat melakukan perkiraan posisi dengan akurasi 1 meter sebanyak 90% dari total percobaan. c. Waktu komputasi Waktu komputasi merupakan biaya (cost) yang menjadi konsekuensi terhadap proses yang dilakukan. Biaya diharapkan sekecil mungkin, dan dalam kasus ini diharapkan waktu yang digunakan dalam menjalankan tiap proses sesingkat mungkin.

bertindak sebagai testing data. Data masukan tersebut akan dibandingkan dengan data yang telah diperoleh pada fase offline. Hasil perbandingan ini adalah posisi yang ingin diketahui. Algoritme KNN bekerja dengan menghitung jarak (distance) antar nilai pada fase online dengan titik referensi (TR) pada radio map. Jarak menggambarkan tingkat kemiripan antara dua titik. Semakin kecil jaraknya, semakin tinggi kemiripannya, dan sebaliknya. Penghitungan jarak ini menggunakan persamaan Euclidean Distance (1). Setelah itu akan diambil subset RP sebanyak k berdasarkan nilai jarak yang terkecil.

=

(

,

−

)

(1)

Selanjutnya koordinat posisi tersebut dapat ditentukan dengan menghitung nilai rata-rata koordinat sejumlah k nilai yang diambil tersebut dengan persamaan (2). ( , )=

3. Metode Fingerprint

1

( ,

)

(2)

Metode Fingerprint mengacu pada metode yang mencocokkan fingerprint/fitur sinyal pada suatu lokasi dengan data hasil pengukuran. Metode ini terdiri dari 2 bagian seperti yang ditunjukkan pada Gambar 1, yaitu pengumpulan data fingerprint,yang biasa disebut fase offline dan penentuan posisi, yang disebut fase online.

Gambar 2 Algoritme KNN

Dalam KNN, setiap titik yang terpilih memiliki kontribusi yang sama dalam penentuan koordinat. Namun k titik yang terpilih tersebut memiliki jarak yang berbeda terhadap nilai pengukuran pada fase online. Untuk itu diperlukan pembobotan kontribusi tiap titik tersebut berdasarkan besar jarak masing-masing. Algoritme ini disebut dengan Weighted KNN (WKNN). Persamaan yang digunakan sedikit diubah menjadi persamaan (3), dimana penghitungan bobot tiap titik menggunakan persamaan (4).

Gambar 1 Metode fingerprint

Pada fase offline dilakukan pengumpulan data berupa kuat sinyal pada titik-titik koordinat yang ditentukan. Setiap data yang diperoleh dimasukkan ke dalam sebuah basisdata yang disebut radio map. Data tersebut bertindak sebagai training data dalam proses selanjutnya. Fase online merupakan tahapan menentukan posisi berdasarkan sebuah data masukan. Data tersebut 4.4-94

( , )=

=

1

( ,

)

1

(3) (4)

Seminar Nasional Teknologi Informasi dan Multimedia 2015

ISSN : 2302-3805

STMIK AMIKOM Yogyakarta, 6-8 Februari 2015

Penggunaan algoritme WKNN dimaksudkan untuk meningkatkan akurasi dan presisi perhitungan. Sedangkan untuk menurunkan beban komputasi yang berefek langsung pada waktu eksekusi dilakukan pengelompokan-pengelompokan (clustering) TR. Pengelompokan dilakukan antar titik yang berdekatan, misalnya dikelompokkan setiap 12 sampai 20 titik, atau berdasarkan pemisah berupa dinding. Setiap kelompok memiliki sebuah nilai yang mewakili anggotanya, misalnya digunakan nilai rata-rata kuat sinyal.

dipasang 5 buah Access point (AP). Lokasi pemasangan ditunjukkan pada Gambar 5. Pengambilan data dilakukan dengan menggunakan perangkat smartphone Samsung Galaxy mini 2 (800 MHz Cortex-A5, 512 MB RAM, Android 2.3). Pengambilan data dilakukan pada tiap jarak 1 x 1 meter, yaitu pada titiktitik yang merupakan perpotongan garis pada Gambar 5. Jumlah titik yang ada sebanyak 216 titik. Pada tiap titik diambil sebanyak 20 sampel data, yaitu setiap 3 detik selama 1 menit, kemudian diambil nilai rata-ratanya. Titik referensi tersebut dikelompokkan menjadi 13 kelompok/cluster.

Gambar 3 Algoritme WKNN

Dalam KNN, perhitungan jarak dilakukan pada setiap titik referensi. Beban komputasi sebanding dengan jumlah titik referensi yang digunakan. Pengelompokan yang dilakukan dapat mengurangi itu karena perhitungan jarak tidak dilakukan pada setiap titik referensi melainkan hanya pada kelompok yang mewakili anggotanya. Hanya anggota dari kelompok yang terpilihlah yang kemudian akan digunakan. Proses pemilihan cluster ini dilakukan sebelum masuk ke dalam algoritme KNN, seperti yang ditunjukkan pada Gambar 4.

Gambar 5 Tempat pengujian b. Skenario pengujian Untuk menguji pengaruh beberapa faktor, pengujian dibuat dalam beberapa skenario berikut.  Pengujian menggunakan KNN dan WKNN dengan variasi nilai k = 1 – 9.  Pengujian dengan variasi jumlah data titik referensi: 4320 data (20 data pada tiap titik), 216 data (menggunakan nilai rata-rata) dan 88 data (jumlah titik dikurangi).  Pengujian efek clustering.

Gambar 4 Langkah penggunaan cluster

4. Pengujian dan pembahasan a. Lingkungan pengujian Untuk melakukan pengujian, digunakan sebuah bangunan dengan ukuran 11 x 19 meter. Pada bangunan tersebut

c. Hasil pengujian Pengujian menggunakan masukan 100 data dari 20 titik uji (5 data pertitik) yang tersebar dalam bangunan dengan

4.4-95

Seminar Nasional Teknologi Informasi dan Multimedia 2015

ISSN : 2302-3805

STMIK AMIKOM Yogyakarta, 6-8 Februari 2015

skenario yang telah disampaikan di atas. Data diambil dengan perangkat yang sama dan komputasi dilakukan pada perangkat komputer (AMD A8-4500M 1.9 GHz, 4 GB RAM). Hasil pengujian yang pertama mengenai tingkat akurasi dapat dilihat pada Tabel 1. Nilai yang diperoleh merupakan nilai rata-rata dari pengujian 100 data. Hasil pengujian tersebut memperlihatkan perbedaan tingkat akurasi yang dipengaruhi oleh beberapa faktor yaitu metode yang digunakan, nilai k, jumlah titik referensi (TR), dan jumlah cluster. Hasil yang kedua pada Tabel 2 berupa perbedaan waktu eksekusi masing-masing keadaan. Nilai waktu yang dihasilkan merupakan rata-rata dari perhitungan 100 data sebanyak 100 kali. Tabel 1 Nilai akurasi hasil pengujian (unit dalam meter) kNN

wkNN

Cluster

216 TR 88 TR 4320 TR 216 TR 88 TR 4320 TR knn, 1 cluster knn, 2 cluster wknn, 2 cluster

1 2.18 2.41 2.41 2.18 2.41 2.41 8.31 2.18 2.18

2 1.69 2.08 2.15 1.72 1.99 2.16 8.31 1.69 1.72

3 1.54 1.98 2.07 1.56 1.90 2.08 8.45 1.54 1.56

4 1.45 1.81 1.95 1.45 1.75 1.97 8.46 1.45 1.45

k 5 1.45 1.77 1.89 1.42 1.70 1.93 8.48 1.45 1.42

6 1.50 1.71 1.87 1.43 1.66 1.89 8.47 1.50 1.43

7 1.51 1.70 1.84 1.45 1.63 1.86 8.50 1.51 1.45

8 1.49 1.61 1.83 1.44 1.57 1.85 8.45 1.49 1.44

9 1.50 1.62 1.84 1.43 1.55 1.87 8.48 1.50 1.43

8 123 52 1339 125 49 1300 64 106 169

9 123 51 1310 127 49 1314 64 106 168

Tabel 2 Waktu eksekusi (unit dalam milidetik) kNN

wkNN

Cluster

216 TR 88 TR 4320 TR 216 TR 88 TR 4320 TR knn, 1 cluster knn, 2 cluster wknn, 2 cluster

1 126 49 1315 130 58 1314 67 114 159

2 127 51 1305 125 50 1424 64 113 157

3 124 51 1407 124 49 1328 64 107 157

4 122 51 1367 125 50 1396 64 106 158

k 5 122 51 1303 125 49 1311 64 105 158

6 123 51 1399 124 49 1339 64 105 158

7 123 51 1372 125 48 1312 65 105 158

Pengaruh nilai k dapat terlihat perubahan nilai akurasi. Secara umum tingkat akurasi meningkat pada nilai k dari 1 sampai 3, dan cenderung stabil pada nilai k > 4. Dari sisi waktu, peningkatan nilai k tidak memberikan peningkatan terhadap waktu eksekusi. Hal tersebut terjadi karena peningkatan nilai k tidak menambah baris komputasi. Nilai k hanya berpengaruh terhadap jumlah yang terlibat dalam menghitung rata-rata (x,y), sedangkan porsi waktu yang besar terdapat pada perhitungan jarak (D). Pengaruh faktor jumlah titik referensi dapat dibagi 2 perbandingan, pengunaan 20 data per titik-penggunaan nilai rata-rata dan pengurangan jumlah titik dari 216 menjadi 88. Perbandingan pertama memperlihatkan bahwa akurasi akan lebih baik jika mengunakan nilai ratarata sinyal. Hal tersebut terjadi karena dari k titik yang akan terpilih terdapat sejumlah titik yang memiliki koordinat yang sama. Dalam parameter waktu eksekusi,

Perbandingan kedua, yaitu pengurangan jumlah titik referensi menjadi 88 titik dilakukan dengan mengambil titik dengan jarak 2 x 2 meter. Dari pengujian ini dapat terlihat pengaruh kerapatan titik referensi. Semakin banyak dan semakin rapat jarak antar titik maka akurasi yang diperoleh semakin baik. Dari segi waktu, pengurangan jumlah titik mengurangi beban komputasi yang cukup besar yang berefek pada pengurangan waktu yang dibutuhkan. Penerapan WKNN juga memberikan pengaruh terhadap akurasi. Secara umum, nilai yang diperoleh menunjukkan akurasi yang sedikit lebih baik dibandingkan dengan KNN. Penerapan clustering mampu menurunkan waktu eksekusi. Percobaan ini menggunakan jumlah titik referensi sebanyak 216. Penggunaan 1 cluster mampu memberikan penurunan waktu hingga 50 %, namun akurasi yang dihasilkan jauh menurun. Hal tersebut terjadi karena proses yang berjalan belum memilih cluster yang tepat. Sebagian besar cluster yang harusnya terpilih bukan merupakan cluster yang memiliki jarak paling kecil. Kesalahan tersebut disebabkan oleh penentuan nilai cluster yang kurang tepat menggunakan nilai rata-rata anggotanya. Berbeda halnya dengan penggunaan 2 cluster yang memberikan penurunan hanya sebesar 15 % namun tetap mempertahankan akurasi. Tingkat presisi yang dihasilkan dalam percobaan ditampilkan pada Gambar 6. Pada tingkat akurasi 2 meter, KNN (216 TR) memberikan presisi 84 % dan WKNN (216) memberikan presisi 82%. 5. Kesimpulan Pengujian yang telah dilakukan menunjukkan bahwa teknologi WLAN dengan metode fingerprint dapat dimanfaatkan untuk melakukan penentuan posisi di dalam ruangan. Beberapa variasi keadaan yang telah dilakukan dapat menjadi acuan dalam mengembangkan sistem lebih lanjut. Misalnya, pengurangan beban komputasi dapat dilakukan dengan mengurangi jumlah titik referensi atau dengan clustering. Penelitian selanjutnya diharapkan dapat menemukan metode clustering yang lebih baik untuk membantu mengurangi beban komputasi, khususnya jika sistem diimplementasikan pada tempat yang luas.

4.4-96

Seminar Nasional Teknologi Informasi dan Multimedia 2015

ISSN : 2302-3805

STMIK AMIKOM Yogyakarta, 6-8 Februari 2015

Gambar 6. Grafik Presensi Biodata Penulis

Daftar Pustaka [1]

P. Prekop and M. Burnett, “Activities, context and ubiquitous computing,” Comput. Commun., vol. 26, no. 11, pp. 1168–1176, 2003. [2] B. Schilit, N. Adams, and R. Want, “Context-aware computing applications,” in Mobile Computing Systems and Applications, 1994. WMCSA 1994. First Workshop on, 1994, pp. 85–90. [3] E. Kim and J. Choi, “A Context Management System for Supporting Context-Aware Applications,” in IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, 2008. EUC ’08, 2008, vol. 2, pp. 577–582. [4] N. Le Dortz, F. Gain, and P. Zetterberg, “WiFi fingerprint indoor positioning system using probability distribution comparison,” in Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on, 2012, pp. 2301–2304. [5] H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of wireless indoor positioning techniques and systems,” Syst. Man Cybern. Part C Appl. Rev. IEEE Trans. On, vol. 37, no. 6, pp. 1067–1080, 2007. [6] A. M. Ladd, K. E. Bekris, A. P. Rudys, D. S. Wallach, and L. E. Kavraki, “On the feasibility of using wireless ethernet for indoor localization,” IEEE Trans. Robot. Autom., vol. 20, no. 3, pp. 555– 559, 2004. [7] J. Xiao, Z. Liu, Y. Yang, D. Liu, and X. Han, “Comparison and analysis of indoor wireless positioning techniques,” in 2011 International Conference on Computer Science and Service System (CSSS), 2011, pp. 293–296. [8] Y. Gu, A. Lo, and I. Niemegeers, “A survey of indoor positioning systems for wireless personal networks,” Commun. Surv. Tutor. IEEE, vol. 11, no. 1, pp. 13–32, 2009. [9] Y. Wang, X. Jia, H. K. Lee, and G. Y. Li, “An indoors wireless positioning system based on wireless local area network infrastructure,” in 6th Int. Symp. on Satellite Navigation Technology Including Mobile Positioning & Location Services, 2003. [10] H. Koyuncu and S. H. Yang, “A survey of indoor positioning and object locating systems,” IJCSNS Int. J. Comput. Sci. Netw. Secur., vol. 10, no. 5, pp. 121–128, 2010. [11] J. Hightower and G. Borriello, “A survey and taxonomy of location systems for ubiquitous computing,” IEEE Comput., vol. 34, no. 8, pp. 57–66, 2001.

Eko Suripto Pasinggi, memperoleh gelar Sarjana Teknik (S.T.), Jurusan Teknik Elektro dan Teknologi Informasi, UGM pada tahun 2012. Saat ini sedang menempuh pendidikan S2 pada jurusan yang sama. Selo Sulistyo, memperoleh gelar Ph.D. di bidang Information and Communication Technology dari University of Agder, Norway, lulus tahun 2012. Saat ini menjadi kepala e-Systems Lab dan dosen di Jurusan Teknik Elektro dan Teknologi Informasi UGM. Bidangbidang penelitian yang diminati meliputi Model-driven Software Engineering, Software Development, serta Mobile and Embedded Programming in the Internet of Services. Bimo Sunarfri Hantono, memperoleh gelar M.Eng. dari Nanyang Technological University, lulus tahun 2005. Saat ini menjadi kepala grup riset eMuseum di e- Systems Lab dan dosen di Jurusan Teknik Elektro dan Teknologi Informasi UGM. Bidang-bidang penelitian yang diminati meliputi Multimedia, Software Engineering, dan Information System.

4.4-97