Optimasi Multi-Objective Penempatan Relai Pada Perancangan Wireless Sensor Network Menggunakan Genetic Algorithm Dan Particle Swarm Optimization

Amron, Kasyful and Dr. Dra. Wuryansari Muharini Kusumawinahyu, M.Si. and Syaiful Anam, S.Si., M.T., Ph.D. and Prof. Ir. Wayan Firdaus Mahmudy, S.Si., M.T., Ph.D. (2024) Optimasi Multi-Objective Penempatan Relai Pada Perancangan Wireless Sensor Network Menggunakan Genetic Algorithm Dan Particle Swarm Optimization. Doktor thesis, Universitas Brawijaya.

Abstract

Wireless Sensor Network (WSN) dapat diartikan sebagai kumpulan node yang terhubung secara nirkabel dan digunakan untuk mengumpulkan, mengirimkan, dan memproses data. Sebuah WSN yang besar terbentuk dari ratusan bahkan ribuan node heterogen, mencakup area yang luas dengan topologi multi-tier. Sebagai akibatnya, permasalahan yang harus diselesaikan semakin kompleks. Metode penempatan node tidak hanya memastikan cakupan dan konektivitas, tetapi juga pembentukan jalur komunikasi. Metode penempatan node harus memastikan cakupan, konektivitas, dan keandalan jalur komunikasi. Permasalahan penempatan node sering dipresentasikan sebagai masalah optimasi heuristik. Namun, optimasi heuristik dengan pendekatan single-objective tidak selalu menghasilkan solusi optimal. Oleh karena itu, pendekatan Multi-Objective Optimization (MOO) muncul sebagai alternatif untuk meningkatkan hasil optimasi. Disertasi ini membahas metode optimasi untuk merancang topologi WSN dengan pendekatan MOO. Penelitian ini bertujuan untuk meminimalkan jumlah relai dan biaya komunikasi WSN dengan memanfaatkan Genetic Algorithm (GA) yang dimodifikasi. Modifikasi yang dilakukan berupa pengembangan kromosom dengan meniru pergerakan acak partikel pada Particle Swarm Optimization (PSO). Kedua algoritma ini dipilih karena merupakan varian dari algoritma berbasis populasi yang paling banyak diusulkan untuk menyelesaikan optimasi WSN dengan skala besar dan mewakili dua metode optimasi berbeda, yaitu metode eksplorasi dan eksploitasi. Pencarian eksploratif yang luas dari GA diharapkan dapat ditingkatkan dengan pencarian eksploitasi sistematis dari PSO. Penelitian ini mengusulkan metode optimasi penempatan relai menggunakan GA yang dimodifikasi untuk merancang WSN dengan topologi multi-path. Topologi multi-path memungkinkan sensor untuk memanfaatkan beberapa jalur komunikasi berbeda, sehingga meningkatkan kemampuan fault tolerance dan mengurangi delay pengiriman data. Fitur fault tolerance memastikan ketahanan sistem pada kegagalan relai atau masalah komunikasi lainnya dengan memanfaatkan jalur alternatif. Pengaturan jarak antar relai dan pembatasan jumlah hop maksimum berguna untuk memastikan bahwa delay transmisi tetap terkontrol. Pendekatan ini bertujuan untuk membangun topologi WSN yang andal untuk pengiriman data. Pembatasan jumlah hop memunculkan konsekuensi luas area implementasi menjadi terbatas. Untuk mengatasi hal ini, area dibagi menjadi beberapa sub area dengan sink sebagai node tujuan ditempatkan di tengah-tengah sub area. Dengan demikian, perancangan WSN tetap dapat dilakukan pada area yang lebih luas dengan melakukan optimasi per sub area.x Penelitian ini menangani tiga permasalahan yaitu pemodelan area implementasi, pola penempatan dan pemilihan lokasi relai, serta evaluasi metode optimasi dari sudut pandang teknologi WSN secara teoritis dan praktis. Tujuan utama penelitian ini adalah merancang topologi WSN multi-path yang andal dengan mengoptimalkan posisi dan jumlah relai serta biaya komunikasi minimum. Pada penelitian ini, area simulasi berbentuk persegi dengan ukuran 10 kali radius komunikasi. Penempatan relai diatur dengan pola grid segitiga dengan ukuran yang disesuaikan dengan radius komunikasi. Radius komunikasi diasumsikan sama untuk seluruh tipe node, baik sensor, relai, ataupun sink. Penempatan relai diatur hanya pada titik-titik grid segitiga. Pola penempatan ini memungkinkan setiap relai untuk terhubung dengan enam relai terdekat. Sensor ditempatkan secara acak mendekati posisi target untuk memastikan bahwa semua target dapat dipantau melalui sensor. Pada setiap area simulasi, hanya terdapat satu sink, dengan posisi yang ditentukan berada pada titik tengah area simulasi. Melalui serangkaian simulasi, hasil penelitian menunjukkan bahwa metode optimasi yang diusulkan mengurangi jumlah relai dan biaya komunikasi pada WSN dan secara efektif meningkatkan keandalan dengan topologi multi-path. Pada pengujian dengan 20 sensor, rasio GP095 menghasilkan dua topologi dengan jumlah relai terendah sebanyak 62 node dan biaya komunikasi terendah sebesar 183,2. Kedua hasil simulasi ini menggunakan relai yang lebih sedikit dan biaya komunikasi yang lebih rendah jika dibandingkan dengan algoritma lain seperti Dijkstra dan A-star. Selain itu, metode optimasi yang diusulkan juga memberikan fleksibilitas dalam menyesuaikan jumlah relai dan biaya komunikasi secara bersamaan, yang merupakan keunggulan tambahan dalam perancangan topologi WSN. Rekomendasi untuk pengembangan metode optimasi lebih lanjut dalam penelitian ini mencakup beberapa aspek penting. Pertama, pengembangan model matematika yang lebih lengkap untuk menggambarkan karakteristik WSN secara akurat, misalnya dengan mempertimbangkan faktor eksternal seperti gangguan sinyal dan kondisi area implementasi. Kedua, pengembangan algoritma fokus pada pemilihan dan penerapan fitur optimasi yang lebih baik dengan mengeksplorasi berbagai fitur yang disediakan oleh GA, PSO, atau algoritma optimasi lainnya. Terakhir, implementasi lapangan terkontrol berdasarkan hasil simulasi sebagai validasi perlu dilakukan untuk memastikan bahwa rancangan topologi yang dihasilkan merupakan solusi yang benarbenar dapat diterapkan secara nyata.

English Abstract

Wireless Sensor Network (WSN) can be interpreted as a collection of nodes that are connected wirelessly and are used to collect, transmit, and process data. A large WSN is formed from hundreds or even thousands of heterogeneous nodes, covering a large area with a multi-tier topology. As a result, the problems that must be solved are increasingly complex. The method of placing nodes ensures not only coverage and connectivity but also the establishment of communication lines. The node placement method must ensure the coverage, connectivity, and reliability of the communication line. The problem of node placement is often presented as a problem of heuristic optimization. However, heuristic optimization with a single-objective approach does not always result in optimal solutions. Therefore, the Multi-Objective Optimization (MOO) approach emerged as an alternative to improve optimization results. This dissertation discusses optimization methods for designing WSN topologies with MOO approach. This study aims to minimize the number of relays and WSN communication costs by utilizing a modified Genetic Algorithm (GA). The modification carried out is in the form of chromosome development by imitating the random movement of particles in Particle Swarm Optimization (PSO). These two algorithms were chosen because they are variants of the most widely proposed population-based algorithms to solve WSN optimization at scale and represent two different optimization methods, namely exploration and exploitation methods. The extensive exploratory search of GA is expected to be enhanced by the systematic exploitation search of PSOs.This study proposes a relay placement method using GA to design WSNs with a multipath topology. Multipath topology allows sensors to utilize multiple different communication paths, thereby increasing fault tolerance capabilities and reducing data transmission delays. The fault tolerance feature ensures system resilience to relay failures or other communication problems by utilizing alternative paths. Setting the distance between relays and limiting the maximum number of hops is useful to ensure that transmission delay remains controlled. This approach aims to build a reliable and efficient WSN topology for data delivery. Limiting the number of hops has the consequence that the area of implementation is also limited. To overcome this, the sink as a data storage node is placed in the middle of the sub-area. Thus, WSN design can still be done in a wider area by optimizing per sub-area. This research addresses three problems, namely modeling the implementation area, placement and selection patterns of relays, and evaluating optimization methods from the point of view of WSN technology theoretically and practically. The main objective of this study is to design a reliable and fault-tolerant multipath WSN topology by optimizing the position and number of relays and minimizing communication costs.x

Item Type:	Thesis (Doktor)
Identification Number:	0624090012
Uncontrolled Keywords:	Wireless sensor network; penempatan relai; topologi jaringan; multi-path; biaya komunikasi minimum; optimasi multi-objective; genetic algorithm; particle swarm optimization
Divisions:	S2/S3 > Doktor Matematika, Fakultas MIPA
Depositing User:	Unnamed user with username nova
Date Deposited:	10 Oct 2024 04:07
Last Modified:	10 Oct 2024 04:07
URI:	http://repository.ub.ac.id/id/eprint/228817

Text (DALAM MASA EMBARGO) Kasyful Amron.pdf Restricted to Registered users only Download (5MB)

Actions (login required)

View Item