## pISSN: 2252-9128  eISSN: 2252-9128

## Vol 1 No 1 January 2015, 45 - 50

## OPTIMASI PEMILIHAN CLUSTER HEAD DENGAN BIRD-BEHAVIOR PADA LINGKUNGAN MANET
Desy Intan Permatasari 1 , Waskitho Wibisono 2
1,2 Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Kampus ITS Keputih Sukolilo, Surabaya, Jawa Timur desyintan@yahoo.com

## Abstrak
Pergerakan node secara dinamis di dalam lingkungan MANET ( mobile ad-hoc network) merupakan  tantangan utama hingga saat ini. Pemilihan metode yang paling sesuai untuk mengirimkan pesan pada layer routing harus diterapkan untuk  mengurangi service  discovery  delay . Service  discovery di  lingkungan  jaringan mobile  ad-hoc  network merupakan isu yang masih diteliti hingga saat ini, karena pada lingkungan mobile ad-hoc network tidak terdapat titik pusat administrasi yang mengatur node di jaringan. Untuk mengurangi service discovery delay , mekanisme cluster diterapkan pada lingkungan mobile ad-hoc network . Node dibagi dalam beberapa daerah yang disebut cluster , dimana setiap cluster memiliki cluster head yang bertugas mengkoordinasikan  pergerakan node dalam cluster tersebut.  Permasalahan  yang  muncul  adalah  bagaimana menentukan cluster  head yang  tepat.  Pemilihan cluster  head yang  tidak  tepat  dapat  menyebabkan  menurunnya performa efisiensi di jaringan.
Pada penelitian  ini,  penulis  mengemukakan  usulan  untuk  melakukan  optimasi  pada  pemilihan cluster  head dengan mengadopsi  perilaku  burung  dalam  melakukan  migrasi  dari  suatu  tempat  ke  tempat  lain.  Parameter  yang  dapat digunakan untuk pemilihan cluster head berdasarkan bird behavior ini adalah jumlah node tetangga dan jumlah energy yang tersimpan pada setiap node.
Hasil  penelitian  menunjukkan  bahwa  metode  pemilihan cluster  head dengan  mengadaptasi  perilaku  semut  untuk service  discovery mampu  mengurangi service  discovery  delay hingga  sebesar  33,22  ms  dan  meningkatkan service success rate sebesar 8,57%. Kata Kunci: Service Discovery, Cluster Formation, Cluster Head Selection, JiST/SWANS

## Abstract
The movement of nodes dynamically in MANET environments (mobile ad-hoc network) is a major challenge today. Selection of the most appropriate method to send a message to the routing layer should be applied to reduce service discovery delay. Service discovery in the mobile ad-hoc network is a network issue that is still studied today, because the mobile ad-hoc environment network there is no central point of administration that set of nodes in the network.
To reduce service discovery delay, the cluster mechanism applied to mobile ad-hoc environment network. Nodes are divided  into  several  areas,  called  clusters,  where  each  cluster  has  a  cluster  head  in  charge  of  coordinating  the movement of the nodes in the cluster. The problem that arises is how to determine the appropriate cluster head. The selection of cluster head which may cause the decrease in the efficiency of network performance.
In this study, the authors put forward a proposal for optimizing the cluster head election by adopting the behavior of birds in migrating from one place to another. Parameters that can be used for the selection of cluster head based on the behavior of bird this is the number of neighboring nodes and the amount of energy that is stored on each node.
The results showed that the method of election of cluster head by adapting the behavior of ants to service discovery service discovery delay can reduce up to 33.22 ms and improve service success rate of 8.57%.
Keywords: Service Discovery, Cluster Formation, Cluster Head Selection, jist / SWANS

## I. PENDAHULUAN
Service  discovery di  lingkungan  jaringan MANET merupakan isu yang masih diteliti hingga saat ini,  karena  pada  lingkungan  jaringan ad-hoc tidak terdapat titik pusat administrasi yang mengatur node di jaringan. Dynamic service discovery and advertisement (SDA)  telah  membawa  perubahan  isu yang signifikan pada teknologi jaringan.
Definisi  protokol service  discovery adalah protokol  jaringan  yang  memberikan  akses  proses pencarian  layanan  yang  terdapat  pada  suatu device . Untuk  melakukan  pencarian  layanandi  jaringan, pengguna  memanfaatkan  proses  pencarian  dengan
metode
active  pull. Server  melakukan  proses advertisement secara periodik untuk
menginformasikan service yang dimiliki ke node lain. Mekanisme advertisement ini  termasuk  metode passive pull [8] .
Penelitian  yang  dilakukan  oleh  Konark  [10] mengusulkan mekanisme push dan pull yang bertujuan memudahkan  klien  dan  server  melakukan  pencarian dan menginformasikan eksistensi layanan berdasarkan kebutuhan.  Proses  pencarian service terdiri  dari  dua tahap  yaitu  pengguna  mengirimkan request pesan pencarian service secara multicast ke grup jaringan dan selanjutnya  server  yang  memiliki service sesuai dengan  yang  dibutuhkan  klienakan  memberikan

## Melek IT
respon  pesan  ke client. Untuk  memenuhi  tahap pertama  proses  pencarian service, klien  membuat pesan request pencarian  yang berisi path dari service tree atau keyword. Path tersebut akan digunakan ketika klien meminta semua service yang terdapat di jaringan yang  telah  didefinisikan  oleh  beberapa  jenis service yang  generic.  Untuk    pencarian service tertentu  yang bersifat  spesifik, keyword harus  digunakan. Request pesan harus memiliki port tertentu, dimana klien dapat memperoleh reply message dari server secara unicast.
Pada  penelitian  ini,  penulis  mengusulkan mekanisme clustering pada  proses service  discovery. Dengan diterapkannya cluster pada service discovery, diharapkan dapat mengurangi service discovery delay dan meningkatkan service success rate. Permasalahan yang  akan  diteliti  lebih  dalam  adalah  menentukan cluster  head dengan  metode bird  behavior. Metode bird  behavior mengadaptasi  perilaku  burung  saat melakukan migrasi dengan cara membagi beban secara merata  pada  sekumpulan  burung  yang  melakukan migrasi.  Pembagian  beban  secara  merata  tersebut dilakukan  oleh bird  head. Parameter  yang  digunakan untuk  memilih cluster  head dengan  metode bird behavior adalah  jumlah  tetangga  yang  dimiliki  oleh node dan jumlah energi yang dimiliki oleh node.

## II. METODE  BIRD  BEHAVIOR  UNTUK

## PEMILIHAN CLUSTER HEAD
Metode  pemilihan cluster  head dengan bird behavior akan dijelaskan sebagai berikut:
1.1 Pemilihan cluster head dengan bird behavior
Bird  flocking adalah  perilaku  perpindahan fauna  burung  dari  satu  tempat  ke  tempat  lain  pada kurun  waktu  tertentu.  Formasi  perpindahan  fauna burung  membentuk  huruf  “V”  yang  memiliki  makna pembagian  tugas  dari bird  head ke  anggota  burung lainnya secara hierarkhi. Bentuk “V Shaped” ini juga bermanfaat  untuk  meminimalkan  jumlah  energi  yang dikeluarkan  saat  migrasi  fauna  burung.  Pembagian energi  dilakukan  oleh bird  head, dimana bird  head bertanggung  jawab  untuk  mengatur  beban  energi antara  satu  anggota  burung  dengan  anggota  burung lainnya.
Tahapan  pemilihan cluster  head berdasarkan bird behavior adalah node dibagi dalam tiga tier model ( cluster head, gateway node,member node). Pembentukan  formasi cluster dilakukan  oleh  setiap node di MANET secara periodik dengan mengirimkan hello message. Setiap node pada awalnya akan berada pada undecided_status. Pemilihan cluster head didasarkan pada jumlah energi yang dimiliki oleh suatu node. Inisialisasi  awal,  setiap  node  berfungsi sebagai cluster  head dan  secara  periodic node akan mengirimkan Hello  Message ke  node  tetangga  yang berada  dalam  radius  ketetanggaan.  Ketika  node menerima jawaban Hello Packets dari node tetangga, maka node akan berubah status menjadi member node.
Ketika  node  menerima  Hello  Packets  dari node tetangga,  maka  nilai  prioritas  dalam node akan bertambah.  Semakin  tinggi  nilai  prioritas  yang dimiliki, maka kemungkinan suatu node untuk menjadi cluster  head juga  semakin  tinggi.  Perhitungan  nilai prioritas  ditentukan  dari  dua  faktor  parameter  yaitu
jumlah  node  tetangga  dan  jumlah  energi.  Rumus perhitungan peluang terpilihnya node menjadi cluster head adalah:
𝑃𝐵𝑖𝑟𝑑 (n i , 𝑡) = (δ x E)  +  (ω x 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟 𝑖 )
Rumus 1
Keterangan:
ni = node ke-i
𝑃𝐵𝑖𝑟𝑑 (n i , 𝑡) = bobot terpilihnya node ke-i menjadi cluster head  pada iterasi ke t berdasarkan algoritma burung
E = jumlah energi pada node 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟 𝑖 = jumlah node tetangga yang dapat di cover
δ , ω
= konstanta
Dari  rumus bird  behavior, dapat  disimpulkan bahwa  parameter  utama  yang  mempengaruhi  dalam pemilihan cluster  head adalah  jumlah  node  tetangga yang dimiliki oleh suatu node dan jumlah energi yang tersimpan pada node.
Pada komunitas burung ini terdapat bird sphere head yang  bertugas  mengatur  anggota  burung  dalam komunitasnya dalam hal pembagian beban. Pembagian beban oleh bird sphere head inilah yang akan diadopsi dalam  penelitian  ini.  Struktur  hierarki  yang  akan digunakan  terdiri  dari  tiga  hierarkhi  yaitu network, cluster  head dan normal  node. Struktur  hierarki  ini digambarkan pada Gambar 1.
Gambar 1 Hierarki bird behavior

## 1.2 Tahap Service Discovery
Setelah cluster terbentuk  dan cluster  head telah  terpilih,  maka service  discovery baru  dapat dilakukan. Skema hirarki service yang akan digunakan adalah sebagai berikut:

## Gambar 2 Hirarki Service Discovery

## III. DESAIN SISTEM
Pada  penelitian  ini  protokol  yang  akan dikembangkan  diberi  nama Bird  Service  Discovery yang  merupakan  adopsi  dari  perilaku  burung  dalam melakukan  migrasi  dari  suatu  tempat  ke  tempat  lain,

## pISSN: 2252-9128  eISSN: 2252-9128

## Vol 1 No 1 January 2015, 47 - 50
perilaku migrasi burung ini digunakan untuk memilih cluster head dalam proses service discovery di jaringan MANET. Protokol yang akan dikembangkan ini juga akan menurunkan sifat protokol routing Cluster Based Routing  Protocol dalam    mengelompokkan node  – node yang  ada  dalam  jaringan  MANET.  Setiap node yang terdapat pada jaringan MANET akan dikelompokkan  menjadi  suatu cluster ,  dimana  setiap cluster nantinya  akan  memiliki cluster  head. Diharapkan dengan pembagian node ke dalam cluster, dapat  mengurangi service  discovery  delay dan meningkatkan service  success  rate .  Desain  sistem yang akan dibangun dapat dilihat pada Gambar berikut
Gambar 3 BirdBehavior CBRPServiceDiscovery

## IV. PERANCANGAN SIMULASI SISTEM
Sesuai  dengan  tujuan  penelitian  ini  yaitu mengurangi service discovery delay dan meningkatkan service success rate, maka perlu dilakukan pengujian. Tahap pengujian dalam penelitian ini bertujuan untuk membandingkan  kinerja  protokol  CBRP  yang  telah dioptimasi  pada  bagian  pemilihan cluster  head dan protokol  ZRP  untuk  setiap  skenario  yang  telah dipaparkan pada Bab 3. Kinerja dari kedua protokol ini dinilai dari parameter pengujiannya.
Langkah – langkah pengujian pada penelitian ini  adalah  membuat  skenario  pengujian,  menentukan parameter pengujian, dan menganalisa hasil pengujian yang telah dilakukan.

## 1.3 Pembuatan Skrip Pengujian
Sebelum  pengujian  dilakukan,  penentuan parameter  simulasi  perlu  dilakukan  terlebih  dahulu. Parameter  simulasi  ini  tetap  untuk  setiap  skenario pengujian, sehingga setiap skrip pengujian yang akan dijalankan  pada  network  simulator  JiST/SWANS dibangun berdasarkan parameter simulasi ini.

## 1.3.1 Skenario Luas Area
Skrip pengujian skenario 1 adalah memvariasikan luas wilayah yaitu 1000x1000 s/d 3000x3000. Variasi nilai luas wilayah ini yang dimasukkan kedalam skrip variasi  skenario  pengujian.  Pada  Gambar  4.9,  nilai yang dirubah adalah nilai yang ditandai dengan warna merah  yang  merupakan  nilai  dari  luas  wilayah. Sedangkan  nilai  yang  lain  disetting  sama  dengan variasi luas wilayah yang lain.

## 1.3.2 Skenario Bordercast Transmission
Skrip pengujian skenario 3 adalah memvariasikan  waktu  tunggu  node  yaitu  10ms  s/d 90ms.  Variasi  nilai  waktu  tunggu  node  ini  yang dimasukkan kedalam skrip variasi skenario pengujian. Pada  Gambar  4.11,  nilai  yang  dirubah  adalah  nilai yang  ditandai  dengan  warna  merah  yang  merupakan nilai  dari  waktu  tunggu  node.  Sedangkan  nilai  yang lain disetting sama dengan variasi waktu tunggu yang lain.

## V. HASIL DAN PEMBAHASAN
Hasil  pengujian  pada  sub  bab  ini  diperoleh dengan  melakukan  analisis  terhadap  file  teks  yang dihasilkan  saat  pengujian Bird  Service  Discovery Protocol. Dari hasil pengujian penelitian ini, parameter yang  akan  dianalisis  adalah message  overhead dan service discovery delay.
1.4 Hasil Uji Coba Parameter Message Overhead
Parameter message  overhead digunakan untuk  mengukur  jumlah message  service  discovery yang  digunakan  saat  proses service  discovery dilakukan.
Tabel 1 Pause Time vs Message Overhead
Dari  hasil  pengujian,  dapat  disimpulkan bahwa  nilai message  overhead yang  dihasilkan  oleh CBRP Service  Discovery lebih  rendah  dibandingkan dengan ZRP Service Discovery. Dimana ketika pause time semakin  meningkat,  maka message  overhead yang  dihasilkan  juga  semakin  menurun.  Pada pause time ke  90,  nilai message  overhead yang  dihasilkan oleh CBRP Service Discovery adalah 18,45 % dan nilai message  overhead yang  dihasilkan  oleh  ZRP Service Discovery adalah  21,621%.    Dari  hasil  pengujian secara  keseluruhan,  nilai message  overhead CBRP Service Discovery berbeda sedikit dengan ZRP Service Discovery, dimana  nilai message  overhead CBRP Service  Discovery lebih  tinggi  daripada  ZRP Service Discovery.

## Melek IT
Information Technology Journal. Vol 1 No 1 January 2015, 48 - 50
Gambar 4 Pause Time vs message overhead

## 1.5 Hasil Uji Coba Parameter Service Discovery

## Delay
Pada sub bab ini akan dibahas mengenai pengaruh kecepatan  mobilitas  pada  node  terhadap  service discovery  delay.  Pergerakan  mobilitas  node  yang semakin cepat, maka akan menyebabkan nilai service discovery delay semakin menurun.
Terlihat  dari  hasil  pengujian  pada  kecepatan mobilitas  10  m/s,  nilai service  discovery  delay yang dihasilkan  oleh Bird  Discovery  Protocol adalah 1607,1428  ms.  Sedangkan  nilai  yang  dihasilkan  oleh ZRP Service Discovery adalah 1500 ms. Nilai service delay semakin menurun pada kecepatan mobilitas node 50  m/s. Bird  Service  Discovery menghasilkan  nilai 666,66  ms,  sedangkan  ZRP Service  Discovery menghasilkan nilai 703,125 ms.
Nilai service discovery delay pada kecepatan mobilitas node yang rendah lebih tinggi dibandingkan dengan kecepatan mobilitas node yang tinggi. Hal ini disebabkan oleh adanya mekanisme pencarian service antara node satu  dan  lainnya.  Semakin  rendah kecepatan mobilitas node, semakin tinggi nilai service discovery delay yang dihasilkan dan dapat disimpulkan bahwa proses pencarian service yang terbaik dilakukan adalah pada kecepatan mobilitas yang rendah.
Gambar 5 Kecepatan mobilitas vs service discovery delay

## VI. KESIMPULAN
Kontribusi yang diberikan pada penelitian ini adalah  mengkombinasikan  metode Bird  Behavior untuk  pemilihan cluster  head dan  digunakan  dalam proses service  discovery yang  bertujuan  untuk mengurangi message  overhead dan  mengurangi service discovery delay dalam lingkungan Mobile Ad Hoc  Network (MANET).  Kontribusi  yang  dilakukan dalam  penelitian  ini  terbukti  mampu  menghasilkan
service  discovery  delay yang  lebih  rendah  jika dibandingkan dengan protokol Zona Routing Protocol (ZRP). Selain  itu,  nilai service  discovery  delay yang dihasilkan  oleh Bird  Discovery  Protocol juga  lebih rendah dibandingkan dengan ZRP Discovery Protocol. Hal ini terlihat dari hasil pengujian pada skenario luas area 3000x3000m, nilai service discovery delay yang dihasilkan oleh Bird  Discovery  Protocol adalah 666.666  ms.Nilai service  discovery  delay yang dihasilkan  oleh  ZRP Discovery  Protocol adalah 703.125 ms.

## VII. DAFTAR PUSTAKA
[1] A.  Boukerche,  Simulation-based  performance comparison  of  routing  protocols  for  mobile  ad hoc networks, Simulation 78 (2002) 401–407.
[2] Amin,  Seyen.  Budiarto,  Rahmat.,  Wan,  Tat- Chee. A routing layer-based hierarchical service advertisement  and  discovery  for  MANETs, Sciencedirect, Adhoc Network Journal . 2011.
[3] Abolhasan, Mehran.,Wysocki, Tadeusz., Dutkiewicz, Eryk. A review of routing protocols for  mobile  ad  hoc  networks,  Sciencedirect, Adhoc Network Journal. 2010.
[4] Barr,  R.,  J.Haas,  Z.  &  Renesse,  R.v.,  (2005). Scalable Wireless  Ad Hoc Network Simulation. CRC Press, Volume 19, hal. 297-311.
[5] Chlamtac,  I.,  M.  Conti,  and  J.J  Liu  (2003). Mobile  Ad  Hoc  Networking:  imperatives  and challenges. Ad Hoc Networks, 1(1):13-64.
[6] C.N.  Ververidis,  C.G.  Polyzos,  A  routing  layer based  approach  for  energy  efficient  service discovery  in  mobile  ad  hoc  networks,Wireless Communications  and  Mobile  Computing  9 (2008) 655–672.
[7] C.N.  Ververidis,  G.C.  Polyzos,  Routing  layer support  for  service  discovery  in  mobile  ad  hoc networks, in: Third IEEE International Conference  on  Pervasive  Computing  and Communications  Workshops  (PERCOMW’05), Kauai Island, Hawaii, 2005, pp. 258–262.
[8] C. Perkins, E. Belding-Royer, S. Das, RFC 3561: Ad  hoc  On-Demand  Distance  Vector  (AODV)- draft-ietf-manet-aodv  Routing,  University  of California, Santa Barbara, University of Cincinnati, Nokia Research Center, 2003.
[9] C.N. Ververidis, G.C. Polyzos, Extended ZRP: a routing layer based service discovery protocol for mobile ad hoc networks, in: The Second Annual International  Conference on  Mobile  and Ubiquitous  Systems:  Networking  and  Services (MobiQuitous  2005),  IEEE,  San  Diego,  CA, 2005, pp. 65–72.
[10] Helal,  Sumi.,Desai,  Nitin.,  Verma,  Varun. Choonhwa,  Lee.2003.  “Konark  –  A  service discovery  and  delivery  protocol  for  ad  hoc networks”, IEEE.
[11] M.  Abolhasan,  T.  Wysocki,  E.  Dutkiewicz,  C. Liu, J. Kaiser, A review of routing protocols for mobile  ad  hoc  networks,  Ad  Hoc  Networks  2 (2004) 1–22..

## pISSN: 2252-9128  eISSN: 2252-9128

## Vol 1 No 1 January 2015, 49 - 50
[12] N. Moghim, F. Hendessi, N. Movehhedinia, T.A. Gulliver,  Ad-hoc  wireless  network  routing protocols  and  improved  AODV,  The  Arabian Journal  for  Science  and  Engineering  28  (2003)
99–114.
[13] R.  Koodli,  C.E.  Perkins,  Service  Discovery  in On-Demand  Ad  Hoc  Networks,  draft-koodli- manet-servicediscovery-00.txt,  IETF,  Internet Draft, 2002.
[14] Salunkhe.  A.S,  Sankpal.  Dr.S.V,Performance Evaluation Using Cluster Based Routing Protocol for MANET, International Journal of Application or  Innovation  in  Engineering  &  Management (IJAIEM), January 2013.
[15] Sampath,  Amritha.,Tripti.  C,  M.Thampi.Sabu. “An ACO Algorithm for Effective Cluster Head Selection”,  Journal  of  Advances  in  Information Technology, Vol 2, No.1, February 2011.
[16] Tonnesen,  Andreas.  Mobile  Ad-Hoc  Networks, Unik Organization, Everaldo.com, 2004.
[17] Verdous. Raihana, GMuthukkumarasamy. Vallipuram,Sithirasenan.Elankayer,  Trust-based Cluster head Selection Algorithm for Mobile Ad hoc Networks, IEEE Journal.S
[18] Z. Fan, E.G. Ho, Service discovery in mobile ad hoc  networks,  in:  Sixth  IEEE  International Symposium on a World of Wireless Mobile and Multimedia
Networks
(WoWMoM05), Taormina-Giardini Naxos, Italy, 2005, pp. 457– 459.

## Melek IT
Halaman ini kosong Redaksi Melek IT