1 Pendahuluan
Ad hoc jaringan nirkabel merupakan suatu jenis jaringan nirkabel khusus yang memilih suatu kumpulan mobile host dengan membentuk jaringan sementara tanpa tambahan infrastruktur yang terpusat. Jika dua host berdekatan dan berada pada jangkauan masing-masing, maka tidak perlu ada protokol routing atau pemilihan yang dibutuhkan, keduanya dapat melakukan komunikasi secara langsung. Sedangkan jika keduanya terpisah di luar jangkauan transmisi Wi-Finya maka keduanya hanya dapat berkomunikasi jika ada perantara di antaranya yang dapat/mengizinkan pengiriman data melalui perantara tersebut.
Pada laptop khususnya jaringan ad hoc dapat dilakukan dengan aktivasi menggunakan command prompt. Hal tersebut dilakukan dengan melakukan 2 tahap yaitu:
- a. Pendefinisian: untuk membangun identitas seperti nama node dan password (sebagai perizinan) jika diinginkan terhubung, maka ditulis perintah tanpa kutip "netsh wlan set hostednetwork mode=allow ssid=node key=12341234"
- b. Aktivasi: dilakukan setelah pendefinisian telah dilakukan "netsh wlan start hostednetwork"
Untuk pendefinisian yang perlu diperhatikan adalah value ssid dan key, ssid digunakan sebagai nama dari node sedangkan key merupakan password untuk dapat terhubung ke dalam jaringannya. Untuk aktivasi node, dilakukan dengan melakukan tahap b, dan untuk mematikan fungsi ini cukup dengan melakukan seperti tahap b namun mengganti kata start menjadi stop di dalamnya.
Untuk merepresentasikan ad hoc ini dapat direpresentasikan oleh suatu diagram G=(V , E). Dalam hal ini, V merupakan set dari host dan E merupakan set dari edges. Edge antar pasangan host {v ,u } yang menyatakan v dan u berada pada jangkauan transmisinya. Untuk memudahkan, berdasarkan Wu dan Li, asumsikan semua host bersifat homogen sehingga jarak transmisi sama.
Routing pada ad hoc jaringan nirkabel memiliki beberapa tantangan. Protokol tradisional pada jaringan kabel biasanya menggunakan link state [1],[2] atau vektor posisi [3],[4] tidak cocok diaplikasikan pada ad hoc jaringan nirkabel.
Gateway routing [5] merupakan konsep dari teori dominating set in graph [6]. Suatu sub set dari suatu simpul pada diagram merupakan gateway jika terdapat titik yang tidak terhubung dengan titik lainnya secara langsung namun dapat terhubung jika melewati sub set tersebut. Tujuan dari pendekatan ini adalah mengurangi routing dan proses pencarian pada set gateway. Kelebihan pendekatan ini adalah melakukan simplifikasi terhadap proses routing ke sub jaringan yang lebih kecil yang dibangkitkan dari jaringan yang terhubung.
Sehingga hanya gateway yang dibutuhkan untuk menyimpan informasi routing. Sepanjang perubahan topologi jaringan tidak mengubah sub jaringan tersebut, maka tidak diperlukan perhitungan ulang pada routing. Pada Gambar 1, v dan w adalah gateway yang terkoneksi pada u, x, dan y.
Gambar 1. Contoh ad hoc jaringan nirkabel
Garis lingkaran putus-putus menyatakan jangkauan transmisi pada host, sehingga garis penghubung suatu host berdasarkan daftar host lain pada jangkauannya. Dengan jelas bahwa efisiensi untuk menemukan gateway dan jumlahnya berdasarkan seberapa besar jaringan tersebut. Namun untuk menemukan jumlah minimum gateway biasanya menggunakan NPcomplete (Non-deterministic Polynomial Time). Wu dan Li [5] memberikan suatu algoritma yang mampu secara cepat untuk menentukan gateway dan jumlahnya berdasarkan diagram jaringan yang diberikan yang merepresentasikan ad hoc jaringan nirkabel. Secara umum, suatu titik disebut gateway jika dua tetangga di dalam jangkauannya tidak terhubung satu sama lain. Penelitian ini disusun dengan: Bagian 2 rangkuman yang memiliki hubungan dengan pembahasan ini. Bagian 3 penjelasan singkat algoritma Wu dan Li. Bagian 4 perancangan model berdasarkan algoritma Wu dan Li serta hasilnya. Lalu terakhir bagian 5 merupakan kesimpulan paper ini.
2 Pembahasan Terkait
Skema konservasi energi jaringan seharusnya diaplikasikan pada lapisan berbeda yaitu physical layer, data link layer, dan network layer. Pada network layer efisiensi energi dapat dipilih antara minimum total transmission power routing (MTPR) atau minimum battery cost routing (MBCR) [8]. MTPR meminimalkan total energi yang dibutuhkan untuk mengirimkan paket data pada jaringan. Sedangkan MBCR memaksimalkan usia semua node. Untuk mencapai MTPR, dipilih algoritma yang memilih jarak terpendek [9]. MBCR fokus langsung kepada usia setiap host. Selain itu conditional max-min battery capacity (CMMBCR) [10] membuat penggunaan yang lebih baik untuk keduanya MTPR dan MBCR.
Proses penentuan gateway sangat penting untuk melakukan perhitungan efisiensi. Salah satu metode yang diberikan adalah oleh grup MIT [11]. Suatu node akan diatur sebagai gateway jika dua dari tetangganya gagal untuk kondisi:
- a. Terhubung langsung
- b. Terhubung oleh salah satu atau lebih gateway
Contoh routing diberikan oleh Wu dan Li seperti pada Gambar 2. Di dalam gambar dicontohkan node 8. Node 8 merupakan gateway yang memiliki anggota non-gateway yaitu 3, 10, dan 11. Kemudian jika dari node 8 pengiriman dilakukan menuju node 9, maka jaraknya dihitung 1 hop. Begitu juga dengan 7. Lalu jika dilakukan ke node 4, maka pengiriman dapat dilakukan dengan melewati 7 atau 9. Namun dalam memilih, dipilih jarak yang terdekat yaitu ke 7 kemudian ke 4. Berarti dalam hop jaraknya adalah 2 hop.
Gambar 2. Contoh routing Wu dan Li [5]
Dari gambar 2, pembuatan gateway dilakukan berdasarkan cara sederhana seperti syarat yang sudah dipaparkan. Namun kemudian Wu dan Li memberikan aturan lebih spesifik sehingga efisiensi dapat ditingkatkan.
3 Algoritma Wu dan Li
Pada bagian ini, dibahas proses penentuan gateway yang diberikan oleh Wu dan Li [5] yang kemudian disempurnakan Wu beserta rekan-rekannya [7] berdasarkan diagram node yang diberikan.
3.1 Aturan berdasarkan ID
Wu dan Li [5] memberikan suatu algoritma untuk penentuan gateway pada ad hoc jaringan nirkabel. Algoritma ini berdasarkan proses penandaan yang menandai setiap titik pada diagram G=(V , E). Kemudian m (v ) merupakan variabel penanda dari titik v∈V yang bernilai T (ditandai sebagai gateway) dan F (ditandai non-gateway).
Gambar 3. Contoh diagram jaringan
Asumsikan pada mula semua penanda bernilai F, kemudian N (v )={u∨{v ,u}∈E} merupakan notasi untuk daftar tetangga (open, jadi dirinya v tidak termasuk) dari titik v. Proses penandaan mengikuti aturan berikut:
- a. Mula-mula atur semua node memiliki nilai F pada variabel penandanya
- b. Setiap v diatur memiliki nilai T jika terdapat 2 tetangganya yang tidak berhubungan Berdasarkan gambar 3 sebagai contoh diagram yang digunakan untuk mengaplikasikan aturan di atas, maka menghasilkan bentuk seperti Gambar 4 berikut:
Gambar 4. Diagram setelah aturan awal diberikan
Pada gambar di atas, diperoleh bahwa node 9, 14, 15, 18, dan 19 memiliki nilai tanda F sedangkan yang lainnya bernilai T.
Kemudian Wu dan Li memberikan aturan berdasarkan node ID sehingga dapat mengurangi jumlah gateway dari proses penandaan. Pertama tentukan ID, id (v ), yang diberikan kepada tiap titik seperti penomoran pada node Gambar 3. Definisikan N [ v ]=N (v ) ⋃{v } maka lakukan aturan berikut:
a. Tinjau 2 node v dan u, jika N ¿ dan id (v )<id (u ), tanda m (v )=F jika sebelumnya T
b. Tinjau node v dan w. Jika N ¿ dan id (v ) yang terkecil di antaranya, maka tanda m (v )=F jika sebelumnya T
Sehingga jika aturan di atas diaplikasikan kepada Gambar 4, maka menghasilkan Gambar 5 berikut:
Dari Gambar 5 di atas, dapat dilihat node 8 dikeluarkan dari grup gateway yang semula memiliki tanda T kemudian dikenakan aturan ID sehingga tanda dikembalikan ke F.
3.2 Aturan Node Degree
Kemudian Wu dan rekannya [7] mengajukan algoritma baru yaitu berdasarkan node degree (ND) (disebut algoritma Wu-Li Extended) untuk mengurangi kembali jumlah gateway dari proses penandaan. Pertama didefinisikan tambahan notasi yaitu nd ( v ) yang menyatakan node degree dari v. Aturan yang diberikan adalah:
- 1. Tanda m (v )=F berubah dari T jika memenuhi salah satu syarat:
- a. N ¿ dan nd (v )<nd (u)
- b. N ¿ dan id (v )<id (u ) jika nd (v )=nd (u)
- 2. Tanda m (v )=F berubah dari T jika memenuhi salah satu syarat:
- a. N ¿ tapi N (u) ⊈N(v )∪ N (w) dan N (w)⊈ N(u)∪ N ( v )
- b. N ¿ dan N ¿ tapi N (w)⊈ N(u)∪ N (v ) serta mengikuti salah satu kondisi:
- i. nd ( v )<nd (u)
- ii. nd ( v )=nd (u ) dan id (v )<id (u )
- c. Tanda m (v )=F berubah dari T jika N ¿ dan N (u) ⊆N (v )∪ N (w) dan N (w)⊆ N(u)∪N (v ) serta mengikuti salah satu kondisi:
- i. nd ( v ) paling kecil di antaranya
- ii. nd ( v )=nd (u)<nd(w) dan id (v ) paling kecil
Sehingga dengan aturan tersebut dapat diaplikasikan kepada Gambar 4 sehingga menghasilkan Gambar 6 berikut:
Dari Gambar 6 di atas, selain node 8, node 6 dan node 11 juga dikembalikan menjadi tanda F. Hal ini membuat jumlah gateway semakin berkurang tanpa merusak sistem komunikasi jaringannya.
4 Perancangan Model
Permodelan dibuat dengan melakukan simulasi dengan menggunakan 1000x1000 2-D space dengan memberikan pilihan dapat membentuk jaringan dengan jumlah node antara 20 hingga 100. Radius transmisi diatur 250 unit, namun semua parameter nantinya ditulis 25 saha (di dalam sistem dilakukan perkalian 10). Hal tersebut dibuat menggunakan Processing 3 dengan menggunakan Jawa. Kemudian ikuti beberapa prosedur seperti berikut:
- a. Membangkitkan node
- i. Buat sebuah node posisi acak pada 2-D space, lalu berikan id=1
- ii. Untuk node selanjutnya yaitu id=2 diposisikan acak namun hanya boleh di dalam area transmisi id=1.
- iii. Kemudian node id=3, seperti point 2, namun area acak mencakup transmisi 2 dan 3. Begitu seterusnya hingga node id=n.
- b. Membangkitkan garis penghubung. Garis penghubung hanya menghubungkan node yang berada di dalam area transmisinya saja.
- c. Atur semua node m (v )=F
- d. Buat daftar properti masing-masing node yaitu id, jenis node (gateway atau bukan), jumlah tetangga yang berada di dalam jangkauan transmisinya, daftar id tetangga tersebut
- e. Dibuat pilihan aturan yang diaplikasikan pada node yaitu: No Rule (NR), ID atau ND
- f. Buat properti sistem yang meliputi aturan yang diaplikasikan, jumlah gateway dan jumlah node
Kemudian dari langkah tersebut dihasilkan:
Gambar 7. Tampilan awal pemodelan
Saat dilakukan simulasi, pointer dapat di-hover kepada tiap node sehingga menghasilkan gambaran berikut:
Gambar 8. Tampilan lengkap pemodelan
Dari Gambar 7 dan Gambar 8 dapat dilihat beberapa tombol yang dapat digunakan yaitu:
a. Roll graph: untuk melakukan randomisasi kembali bentuk diagram b. Base: melakukan reset kepada aturan yang diberikan c. NR: mengaplikasikan penentuan gateway tanpa menggunakan aturan khusus
d. Rule ID: mengaplikasikan
aturan ID kepada diagram e. Rule ND: mengaplikasikan
aturan ND kepada diagram f. Edit Node: untuk memilih
jumlah node yang digunakan pada diagram (20 hingga 100)
Khusus Gambar 8, saat pointer dilakukan pada node 3, maka akan muncul garis hijau penghubung dengan dirinya yang menyatakan node yang terkoneksi langsung dengan dirinya. Lalu lingkaran besar hijau merupakan jangkauan transmisinya.
Saat hal tersebut dilakukan, maka akan muncul informasi (dapat dilihat perbandingan informasi pada gambar 7 dan 8), yaitu bagian Properties. Untuk gambar 8, dapat dilihat:
a. Id: 3
b. Node type: Gateway c. Energy level: 1000 d. Number Neighbor: 8 e. Radius detection: 25
f. List neighbor id: 1, 5, 6, 12, 1, 32, 37, 40
Khusus untuk Energi level nanti digunakan untuk keperluan pengembangan terkait terutama dalam sistem dinamis.
Dari simulasi dilakukan pencatatan terhadap jumlah gateway relatif jumlah nodenya. Lalu didapat rata-rata jumlah gateway berbagai model (dilakukan 20 model diagram berbeda dengan mengambil rata-ratanya yang nilainya dikenakan fungsi integer):
| Aturan yang digunakan | Gateway untuk node=20 | Gateway untuk node=60 | Gateway untuk node=100 |
|---|---|---|---|
| NR | 16 | 58 | 97 |
| ID | 14 | 31 | 35 |
| ND | 13 | 23 | 25 |
Tabel 1. Hasil rata-rata jumlah gateway untuk jumlah node 20, 60, dan 100
5 Kesimpulan
Pada penelitian ini, dimodelkan algoritma Wu dan Li serta versi tambahannya. Gateway dipilih berdasarkan ID dan node degree. Objektif penggunaan algoritma tersebut adalah untuk memperoleh jumlah gateway seminimal mungkin sehingga dapat mengurangi pemakaian energi pada struktur jaringan nirkabel. Dari permodelan tersebut dapat dilihat hasil bahwa algoritma Node Degree dapat menekan jumlah gateway tanpa merusak sistem pengiriman data.