## Routing Protocol berbasis Cluster Segitiga

## Nurhayati
Dosen Program Studi Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta
e-mail : nurhayatibuslim@gmail.com

## Abstract
Wireless sensor networks users are increasing drastically in communication and technology. They consist of small battery powered devices  with  limited  energy  resources.  Once  deployed,  the  small  sensor  nodes  are  usually inaccessible to the user, and thus replacement of the energy source is not feasible. However, the smaller of a device the better it is. The development of device should be user friendly. Hence, energy efficiency is a key design issue that needs to be enhanced in order to improve the life span of the network. In BCDCP, all sensors send data from CH (Cluster Head) and then to BS (Base Station).    BCDCP works well in small-scale network but in large scale network it is not appropriated since it uses much energy for long distance wireless communication. We propose a routing  protocol  -  Triangular  Clustering  Routing  Protocol  (TCRP)  -  to  prolong  network  life  time  through  the balanced  energy  consumption.  RPTC  selects  cluster  head  of  triangular  shape.  The  sensor  field  is  divided  into energy level and in every level we choose one node as a gate node. This gate node collects data and sends it to the leader  node.  Finally  the  leader  node  sends  the  aggregated  data  to  the  BS.  We  show  TCRP outperforms  BCDCP with several experiments.
Key words : Wireless Sensor Network, Routing Protocol, Clustering

## 1. PENDAHULUAN
Kemajuan  terbaru  dalam  komunikasi  nirkabel  dan elektronik telah memungkinkan pengembangan biaya rendah, daya  rendah,  sensor  node  berukuran  kecil.  Dalam  WSN, sensor node dapat digunakan untuk mengumpulkan informasi yang  berguna  dari  lapangan.  Banyak  routing  protokol  baru yang  diusulkan  untuk  jaringan  sensor  nirkabel.  Efisiensi energi adalah faktor yang paling penting untuk memperpanjang  jaringan  seumur  hidup  dan  keseimbangan konsumsi  energi.  Meskipun  dalam  skala  kecil  jaringan, BCDCP  bekerja  dengan  baik  untuk  rute  data  energi  secara efisien; topologi jaringan mereka menghambat mereka ketika diterapkan  untuk  jaringan  skala  besar.  Karena  topologi  klub di  cluster  adalah  suatu  skema  rute  satu-hop,  tidak dialokasikan  untuk  komunikasi  nirkabel  jarak  jauh. Selanjutnya,  ketika  ada  banyak  node,  sensor  node  ke  base station  terdekat  akan  mati  cepat,  karena  beban  data  yang dikirim pada base station.
Ini  adalah  kelemahan  dari  BCDCP,  karena  itu  kami mengusulkan  Clustering  Routing  Protokol  berdasarkan metode  seleksi  Segitiga  di  Jaringan  Wireless  Sensor  untuk menyeimbangkan  konsumsi  energi  dan  memperpanjang waktu hidup jaringan. Metode ini didasarkan pada konsentris dan  BCDCP,  tapi  dengan  menambahkan  beberapa  level  dan membuat  cluster  node  dalam  bentuk  segitiga  untuk memperpanjang  waktu  hidup  jaringan  dan  konsumsi keseimbangan  energi.  Sensor  node  di  sebarkan  secara random  dalam  jaringan  dan  jaringan  dibagi  ke  dalam  level
yang  kemudian  dikelompokkan  ke  dalam  sensor  node  atau kelompok dalam bentuk segitiga di setiap tingkat. Satu node dalam  setiap  bentuk  segitiga  dipilih  sebagai  kepala  cluster dan  kepala  klaster  mengirimkan  data  ke  yang  lain  kepala cluster  segitiga.  Setiap  Kepala  Cluster  Gerbang  memilih salah satu Kepala Cluster untuk mengumpulkan data dari CH di  setiap  tingkat.  Node  dengan  energi  tinggi  dan  yang  lebih dekat  dengan  base  station  yang  dipilih  sebagai  pemimpin kepala  cluster.  Kepala  Cluster  Gerbang  di  setiap  tingkatan mengirimkan  data  ke  kepala  cluster  gerbang  di  tingkat  lain dan  lagi  itu  dikirim  kepada  pemimpin  kepala  cluster berikutnya dan akhirnya ke base station.
Struktur makalah ini adalah sebagai berikut: bagian kedua menjelaskan  penelitian-penelitian  terkait,  yang  ketiga menggambarkan  pengelompokan  routing  protokol  dalam jaringan  segitiga  sensor  nirkabel,  keempat  menjelaskan simulasi dan analisis dan akhirnya kelima adalah kesimpulan.

## 2. PENELITIAN YANG BERELASI
Metode  clustering  pada  LEACH  adalah  dibuat  dengan mengelompokkan node-node ke dalam cluster dan kelompok, dimana  kelompok  tersebut  terdiri  dari  kepala  cluster  dan anggota  cluster.   Informasi  adalah  menyatukan  menjadi Kepala  Cluster  (CH)  sebelum  dikirim  ke  base  station. Informasi    ini  dibagi  kedalam  beberapa  putaran;  setiap putaran  terdiri  dari  tahap  set-up  phase  and  steady  set  phase. Set up phase  didefinisikan sebagai pengorganisasian cluster- cluster  ketika  steady  set  phase  mendefinisikan  proses  di
mana  kepala  cluster  menerima  data  dari  semua  cluster  dan mengirimkannya  ke  base  station.  Untuk  menyeimbangkan beban energi, LEACH dimasukkan random rotasi dari posisi energi  yang  tinggi  di  kepala  cluster  di  antara  sensor-sensor. Tetapi  metode  di  mana  kepala  klaster  secara  langsung mengirimkan  data  ke  sink  mengkonsumsi  lebih  banyak energi pada kepala cluster.
Pada  BCDCP  setiap  node  memiliki  pengelompokan  yang similar (serupa) seperti LEACH. Pertama, satu kepala cluster adalah  dipilih  secara  acak  untuk  meneruskan  data  ke  base station.  Karena  kepala  cluster  di  setiap  cluster  akan mengirimkan  data  ke  kepala  cluster  yang  paling  dekat dengannya  didasarkan  pada  minimum  spanning  tree,  ini membebani  routing  untuk  ke  base  station  (BS).  Cluster Kepala  mengirim  data  ke  kepala  cluster  yang  terpilih  dan akhirnya  CH  mengirim  data  ke  base  station  (BS).  Jadi, BCDCP  adalah  memiliki  kelemahan  ketika  ada  sejumlah besar  sensor  node  dan  kepala  cluster.  Karena  jumlah  besar, node  sensor  membutuhkan  lebih  banyak  energi  untuk transmisi  data  intra  dan  antar  cluster.  Hal  ini  menciptakan ketidakseimbangan  dalam  konsumsi  energi  dan  menurunkan umur hidup jaringan.
Kita dapat melihat bahwa BCDCP [6] adalah lebih efisien daripada  LEACH  dalam  dua  aspek,  pertama  dengan memperkenalkan  Minimal  Spanning  Tree  (MST)[2]  untuk menghubungkan ke CH yang secara random memilih Leader untuk  mengirim  data  ke  sink.  Kedua,  BCDCP  membuat penggunaan  terbaik  dari  BS  energi  yang  tinggi  untuk memilih  CHs  dan  bentuk  cluster  yang  interaktif  dengan mensplit algoritma. Jadi BCDCP mengurangi energi dissipasi jaringan  jauh lebih dari  LEACH,  namun  keduanya  memiliki kelemahan dalam jaringan skala kecil.  LEACH dan BCDCP bekerja  dengan  baik  untuk  energi  efisien  pada  putaran  data, namun topologi jaringan mereka menghambat mereka dalam jaringan  skala  besar.  Karena  topologi  klub  di  cluster  adalah suatu  skema  ruting  satu-hop,  tidak  dialokasikan  untuk komunikasi jarak jauh pada nirkabel.

## Gambar. 1. BCDCP pada WSN
Jadi  makalah  ini  mengusulkan  Routing  Protocol  Cluster Segitiga (RPCT) pada Jaringan Sensor Nirkabel untuk daerah jaringan  besar.  Gagasan  utama  adalah:  untuk  intra-cluster- cluster  dan  antar  transmisi  data  kami  dibagi  ke  dalam  level area  jaringan.  Setiap  level  memiliki  satu  cluster  kepala gerbang  yang  berfungsi  untuk  menerima  data  dari  kepala
cluster  setiap  tingkat.  Hasil  simulasi  menunjukkan  seumur hidup  jaringan  dan  keseimbangan  konsumsi  energi  BCDCP dibandingkan dengan CTRP di area jaringan yang besar.

## 3. TRIANGULAR
CLUSTERING ROUTING PROTOCOL PADA WIRELESS SENSOR

## NETWORK
Model  untuk  sistem  routing  protokol  didasarkan  pada asumsi sebagai berikut:
1. Base station terletak jauh dari bidang sensor. Sensor node dan  base  station  menjadi  statis  setelah  menyebarkan  secara acak di area jaringan
2.  Sensor  adalah  homogen  dan  memiliki  kemampuan  yang sama; setiap node diberikan sebuah pengenal yang unik (ID). 3.  Sensor  mampu  beroperasi  di  node  aktif  atau  mode  tidur berdaya rendah.
4.  Sensor  dapat  menggunakan  kontrol  daya  untuk memvariasikan  kekuatan  daya  transmisi  sesuai  dengan  jarak penerima yang diinginkan

## A. Radio Model
Model  radio  terdiri  dari  tiga  bagian:  pemancar,  power amplifier  dan  penerima.  Ada  dua  model  propagasi:  model ruang  bebas  dan  dua  model  propagasi  abu-abu  [7].  Model ruang  bebas  (daya  yang  hilang  d 2 )  dan  (dua  penyebarkan abu-abu) yang multipath fading (daya yang hilang d 4 ) model saluran  yang  digunakan  tergantung  pada  jarak  antara pemancar dan penerima. Dalam makalah ini penelitian energi yang  dihabiskan  untuk  transmisi  dari  sebuah  paket  l-bit  dari pemancar ke penerima pada jarak d didefinisikan sebagai:
ET x (l,d) = lE elec + lεd α = lE elec + lεfsd 2 , d < d 0 or = lE elec +l ε tgd 4 , d ≥ d 0 (1) ET x is  energy  terdisipasi  dalam  pemancar  dari  node sumber  dan  energi  elektronik E elec energi  disipasi  bit  per untuk  menjalankan  sirkuit  transceiver.  Berikut  energi amplifier, εfsd 2 or εtgd 4 , tergantung pada jarak transmisi dan bit  error  rate  yang  diterima.  Persilangan  jarak  d 0 dapat  di peroleh dari:
d 0 = √ ( ε fs/ ε tg)                                                              (2)
Energi yang dikeluarkan untuk menerima pesan adalah:
ER x (l)=lE elec (3)
B. Routing Protocol Cluster Segitiga pada Wireless Sensor Network
Protokol  routing  ini  memberikan  kontribusi  untuk menyeimbangkan konsumsi energi dan memperpanjang umur jaringan  sensor  node.  Jadi  untuk  alasan  ini  kami mengusulkan  Routing  Protocol  Cluster  Segitiga  untuk routing  yang  pendek.  Metode  bentuk  segitiga,  mirip  dengan metode pohon biner mengurangi jumlah transmisi oleh setiap node karena setiap node tidak mengirimkan data langsung ke base  station.  Metode  segitiga,  mirip  dengan  pohon  biner adalah  sebuah  struktur  data  pohon  di  mana  setiap  node
memiliki  paling  banyak  dua  anak.  Biasanya  node  pertama dikenal  sebagai  orangtua  dan  node  anak  disebut  node  node dan  kanan  kiri.  Dalam  teori,  sebuah  pohon  biner  dengan simpul tipe A didefinisikan sebagai induktif TA = µα. 1 + A × α  ×  α.  Pohon  biner  biasanya  digunakan  untuk mengimplementasikan  pencarian  biner.  Kami  membuat routing dengan asumsi:
 Node  disebarkan  secara  random  di  area  jaringan  dan tiap node menjadi statis setelah di sebarkan.
 Bidang jaringan dibagi ke dalam partisi level dan node- node  di  group  ke  dalam    cluster  segitiga  kecil  pada tiap partisi level.
 Setiap tingkat memilih satu node sebagai pintu gerbang, sehingga  setiap  kepala  cluster  di  setiap  tingkat  partisi mengirimkan  data  ke  gerbang  node  yang  selanjutnya dikirim ke base station.
 Rotasi  kepala  klaster  membuat  keseimbangan  energi konsumsi.
 Jika  energi  dari  kepala  cluster  yang  mengering  karena dekat  dengan  base  station,  kepala  cluster  lain  dapat mengirim data langsung ke base station.
 Memiliki  3  fase:  konstruksi  awal  atau  pembentukan cluster, cluster konstruksi, cluster rekonstruksi segitiga
Fase  awal  atau  pembentukan  cluster:  Bidang  jaringan dibagi  menjadi  tingkat  partisi  yang  sama.  Setelah menyebarkan  node  secara  acak  dalam  area  jaringan,  sensor menjadi  statis.  Ini  terdiri  dari  semua  informasi  tentang  ID, energi  residual  node  dan  jarak  dari  node  ke  base  station. Node  memilih  kepala cluster  dan anggota cluster. Pemilihan kepala cluster adalah didasarkan pada energi dan jarak antara node ke base station. Node dengan energi tertinggi dan dekat dengan  base  station  akan  dipilih  sebagai  kepala  cluster  di setiap  tingkat.  Dan  kepala  cluster  dengan  energi  tertinggi serta  paling  dekat  dengan  base  station  di  setiap  tingkatan akan dipilih sebagai gerbang kepala cluster.
Konstruksi dari cluster: simpul tersebut dikelompokkan ke dalam  kelompok  segitiga  kecil  mirip  dengan  pembentukan pohon. Satu node dipilih sebagai kepala cluster dan dua node sebagai  anggota  cluster.  Setiap  tingkat  memiliki  gerbang kepala cluster. Node dengan energi tertinggi dan paling dekat dengan  base  station  dipilih  sebagai  gerbang  kepala  cluster. Setiap  node  mengirim  data  ke  kepala  cluster  dalam  cluster yang  segitiga  kecil  dan  kemudian  kepala  cluster  yang mengirimkan data ke kepala cluster yang berdekatan dengan energi yang lebih tinggi. Selanjutnya kepala cluster mengirim data ke gerbang, Dan gerbang kepala cluster mengirimkannya  ke  pemimpin  kepala  cluster,  kepala  cluster akhirnya pemimpin kirim ke base station. Setelah pengiriman data ke base station energi dari node atau kepala cluster yang menurun  Oleh  karena  itu,  setiap  node  dan  kepala  cluster dapat berotasi untuk menyeimbangkan konsumsi energi.
Fase  rekonstruksi  segitiga:  Fase  ini  adalah  untuk pemeliharaan.  Setelah  pengiriman  data  ke  base  station  jika energi  gerbang  kepala  klaster  menjadi  lebih  rendah  dari energi  di  node  tetangga,  dapat  memilih  lain  kepala  cluster sebagai  pemimpin  untuk  mengirimkan  data  ke  base  station. Kepala  cluster  dapat  berotasi  untuk  menyeimbangkan konsumsi energi dan memperpanjang umur jaringan.
Algoritma cluster segitiga routing protokol dijelaskan dan ditunjukkan dengan gambar di bawah ini:
1. Pada awalnya kita dikerahkan sensor secara acak di daerah jaringan;
2. Sensor node menjadi statis setelah menyebarkan;
3. Bagi    area jaringan ke tingkat partisi yang sama;
4. Setiap sensor node mengirimkan informasi (ID, level, Sisa energi, Jarak) ke BS;
5.  BS  menghitung  dan  menyimpan  semua  informasi  dalam tabel informasi (ID, Level, Energi Residual, jarak);
6.  Setiap  node  memilih  simpul  tetangga  terdekat  untuk membuat cluster segitiga di setiap tingkatan;
7.  Diperiksa  untuk  node  dengan  informasi  yang  sesuai dengan    informasi pada tabel(ID, Level, RE, d) dalam BS; 8.  Setiap  node  mengirim  data  ke  Kepala  Cluster  (CH),  di setiap  tingkat,  dan  algoritma  memilih  satu  CH  sebagai Gerbang Kepala Cluster untuk mengumpulkan data; 9. CH gerbang di setiap tingkat mengirim agregat data untuk CH Pemimpin dan akhirnya CH Pemimpin mengirimkannya ke base station
Gambar. 2. C luster segitiga di  wireless  sensor  network
Gambar. 3.    Routing di cluster segitiga

## 4. ANALYSIS AND SIMULATION RESULTS
Dalam  bagian  ini  kami  mengevaluasi  kinerja  Routing Protocol  Cluster  Segitiga  (CTRP)  melalui  simulasi  dan dibandingkan  dengan  BCDCP.  Pertama  kita  mempelajari karakteristik  dari  clustering  dan  algoritma  routing  segitiga, maka  kita  menyelidiki  pengaturan  parameter  dan  efisiensi energi  CTRP  dalam  hal  waktu  hidup  jaringan,  karena
makalah  ini  berfokus  pada  menyeimbangkan  energi konsumsi dan efisiensi waktu hidup Jaringan
Dalam  makalah  ini  waktu  hidup  jaringan  ditentukan  oleh jumlah  putaran  yang  dibuat  oleh  node  sampai  node  pertama mati.  Simpul  pertama  mati  berarti  node  pertama  kehabisan energi dalam jaringan. Satu putaran didefinisikan operasi dari awal  pembentukan  cluster  sampai  akhirnya  base  station menerima semua data dari pimpinan kepala klaster.
Parameter  yang  digunakan  diasumsikan  dalam  simulasi kami diringkas dalam tabel 1.

## < Tabel 1> Parameter-parameter Simulasi
Parameter Nilai Network field (0, 0)–(100,100) m Base station location (150, 50) m N 100 Initial energy 1 J E elec 50 nJ/bit ε fs 10 pJ/bit/m2 ε mp 0.0013 pJ/bit/m4 d o 87 m EDA 5 nJ/bit/signal Data packet size 4000 bits Hasil simulasi seperti berikut ini:
a. Perbandingan  TCRP's  dengan  rata-rata  energy  yang menghilang dengan BCDCP.
Gambar  4.  Perbandingan  TCRP's  dengan    rata-rata  energy  dissipation dengan BCDCP.
Gambar  4  menunjukkan  rata-rata  energi  yang  digunakan atas jumlah putaran ketika kita digunakan CTRP dan BCDCP sebagai  protokol  yang  ada.  CTRP  mengurangi  konsumsi energi  yang  signifikan  atas  BCDCP,  karena  bentuk  metode segitiga  untuk  memilih  kepala  cluster  dan  gerbang  kepala cluster  di  setiap  tingkat  dalam  CTRP  lebih  efisien  dalam mengkonsumsi  energi  lebih  sedikit  untuk  baik  intra  dan cluster  transmisi  data  antar  di  setiap  tingkat.  Pengurangan 30%  dalam  rata-rata  energi  yang  dipakai  energi  dapat menunjukan  BCDCP  melebihi  CTRP  itu  berarti  CTRP mengkonsumsi  energi  sekitar  30%  kurang  dari  BCDCP. Selanjutnya kita bisa lihat di grafik kurva BCDCP yang lebih tinggi dari CTRP dan disipasi bervariasi antara putaran. Jadi CTRP  memiliki  kinerja  lebih  baik  daripada  BCDCP  dalam hal  efisiensi  energi  dan  dapat  memperpanjang  masa  pakai
jaringan dari sensor node.
b. Masa hidup dari sensor nodes sampai node pertama kali mati
Gambar  5.    Perbandingan  masa  hidup  system  pada  RPCT  dengan BCDCP
Dalam gambar 5. Jumlah masa hidup node adalah seumur hidup (jumlah node sensor hidup sampai node pertama mati) untuk CTRP lebih BCDCP terlihat jelas. Dalam kasus waktu kehidupan  BCDCP  dimulai  berkurang  di  putaran  60  dan dalam  hal  CTRP  itu  dimulai  berkurang  pada  lebih  dari  90 putaran. Kami menghitung bahwa dalam kasus BCDCP node mati 36% lebih cepat dari CTRP. Itu berarti rata-rata jumlah node  sensor  tinggal  di  CTRP  adalah  36%  lebih  tinggi  dari BCDCP.  Jadi  CTRP  memperpanjang  waktu  hidup  jaringan dan  keseimbangan  konsumsi  energi  daripada  BCDCP.  Juga grafik CTRP lebih licin dari BCDCP.

## 5. CONCLUSION
Dalam  tulisan  ini  kami  mengusulkan  Clustering  Segitiga Routing Protocol (CTRP), yang  memanfaatkan energi tinggi pada base station untuk  melakukan tugas energi  yang paling efisien.  Dengan  menggunakan  base  station  sensor  node terbebas  dari  menjalankan  tugas  energi  komputasi  intensif seperti  setup  cluster,  pemilihan  kepala  klaster,  routing formasi.  Node  sensor  dibuat  menjadi  simpul  cluster  dan dibagi  ke  dalam  tingkatan  yang  berbeda.  Setiap  tingkat memiliki satu gerbang kepala cluster untuk menerima semua data  dari  kepala  klaster  yang  kemudian  dikirim  ke  tingkat lain  dan  akhirnya  ke  base  station.  Segitiga  ini  Clustering Routing  Protocol  rotasi  dan  pemilihan  kepala  cluster  adalah berdasarkan energi sisa  yang lebih tinggi dalam sensor node dan  node  jarak  ke  stasiun  pangkalan,  node  dengan  energi yang lebih tinggi dan dekat dengan base station akan dipilih sebagai kepala cluster dalam setiap putaran. Kami berasumsi bahwa  base  station  memiliki  semua  informasi  dari  node sensor, dan energi sisa dan jarak dari node telah didefinisikan. Semua hasil yang ditunjukkan dalam simulasi untuk jaringan seumur  hidup  dan  keseimbangan  konsumsi  energi  BCDCP itu  miskin  bila  dibandingkan  dengan  CTRP  dalam  jaringan area  yang  luas.  Hasil  untuk  CTRP  lebih  baik  dari  hasil
BCDCP. Ini membuktikan bahwa CTRP dapat memperpanjang  jaringan  seumur  hidup  dan  konsumsi keseimbangan energi.

## REFERENSI
[1] Guangyan  Huang,  Xiawei  Li,  Jing  He,  “Dynamic Minimal  Spanning  Tree  Routing  Protocol  for  Large Wireless Sensor Networks", ICIEA, 2006.
[2] H. Shen, “Finding the k Most Vital Edges with Respect to Minimum Spanning Tree,” in Proceedings of IEEE Nat’l. Aerospace and Elect. Conf., vol. 1, pp.255-262, 1997.
[3] Jung-Eun Lee, kieechon Kim, “Diamond-Shaped Routing Method  for  Reliable    Data  Transmision  in  Wireless Sensor  Networks”,  International  Symposium  on  Parallel Distributed  Processing  with  applications.(ISPA),      pp. 799-801, 2008 IEEE.
[4] Stephanie  Lindsey,  Cauligi  S.  Raghavendra,  "Power- Efficient  GAthering  in  Sensor  Information  Systems", IEEE, 2002, Volume: 3, On page(s): 3-1125- 3-1130 vol.3.
[5] Sung-Min Jung, Young-Ju Han, Tai-Myoung Chung,”The Concentric  Clustering  Scheme  for  Efficient  Energy consumption in the PEGASIS”, International Conference on  Advanced  Communication  Technology  (ICACT), Vol.1, pp.260-265, Feb.2007.
[6] S. D. Muruganathan, D. C. F Ma., R. I. Bhasin, and A. O. Fapojuwo,  “A  Centralized  Energy-Efficient  Routing Protocol  for  Wireless  Sensor  Networks,”  IEEE Communications Magazine, vol.43, pp. 8-13, 2005.
[7] W.  Heinzelman,  A.  Chandrakasan  and  H.  Balakrishnan, An application-specific protocol architecture for wireless micro  sensor  networks,  IEEE  Transactions  on  Wireless Communications 1(4) (2005) 660–670.