Pada bagian ini, berbagai algoritma routing disurvei untuk kesesuaian mereka dalam penemuan sumber daya di berbagai lingkunga.
2.3.1 Algoritma Routing untuk Jaringan tidak terstruktur.
Bagian ini membahas beberapa protokol routing yang ada untuk jaringan ad hoc. menuntun pemilihan lapisan routing untuk sumber daya yang tidak terstruktur dan Karakteristik lingkungan jaringan sebagai berikut :
1. Mobilitas tingkat tinggi, termasuk kedatangan dan keberangkatan node
2. target node (s) tidak diketahui - konten lebih relevan daripada alamat node
3. perangkat ringan.
Diskusi
Flooding adalah teknik pencarian yang sering digunakan dalam jaringan tidak terstruktur. Misalnya, Teknik ini digunakan oleh Gnutella [34] pada rute untuk permintaan file melalui jaringan overlay dibentuk oleh rekan-rekan Gnutella. Sebuah isu pada node mereka menyebarkan ke daerah masing masing, dan mengembalikan kepada node itu tersebut di dalam ruang lingkup jaringan mereka. Pada setiap hop, hop counter dalam pesan query adalah decremented. Saat counter mencapai nol, pesan query tidak disebarkan lebih lanjut. Secara umum, hits query yang diarahkan sepanjang reverse path dengan yang query. Pengambilan atau pemanfaatan sumber daya yang cocok biasanya terjadi melalui mekanisme terpisah. Dalam Gnutella, misalnya, ketika querier menerima pesan hit query, itu membuat koneksi TCP / IP langsung ke node yang berisi dan untuk mencocokkan file. Masalah utama dengan flooding adalah ketidakmampuannya untuk skala jaringan besar. Dalam flooding berbasis query routing, setiap query menghasilkan pesan untuk setiap tetangga dari setiap node yang melewati, sehingga sering menghasilkan pesan berlebihan.
DSR menggunakan routing, dimana rute yang harus diambil oleh sebuah paket dimasukkan kedalam header paket. Dalam jaringan ad hoc, rute dari satu node ke node lain dapat beubah terus-menerus. Oleh karena itu, ide penemuan rute diperkenalkan. Ketika node ingin mengirimkan paket ke tujuan tertentu, ia memeriksa cache rute untuk melihat apakah sudah tahu rute tujuan yang telah diketahui. Jika tidak ada yang cocok rute ditemukan dan disimpan dalam cache, pengirim melakukan penemuan rute, yang melibatkan menyiarkan paket permintaan rute ke tetangga masing-masing. Jika kesalahan rute ditemui, rute kesalahan yang berisi dua node yang terlibat dalam hop rusak akan dikembalikan ke pengirim, dan pengirim harus mengembalikan semua rute cache yang melibatkan hop itu.
AODV banyak memiliki kesamaan dengan DSR. Namun,jika DSR memasukkan rute sementara yang harus diambil dalam setiap header paket menjadi penuh, maka AODV akan menjadi sumber dan tujuan pointer pada setiap node. Dalam AODV, rute antara node sumber dan tujuan dibuat secara dinamis. Rute dibentuk melalui penggunaan paket permintaan rute (RREQ) dan paket reply rute (RREP). Ketika sebuah node ingin membangun rute ke tujuan, itu akan di laporkan sebagai paket RREQ. AODV meningkatkan kinerja pada DSR dan akan mengurangi overhead, meskipun masih memerlukan paket untuk dilaporkan selama penemuan rute.
GPSR meneruskan paket berdasarkan lokasi geografis (apakah lokasi dan informasi yang dikumpulkan dari Global Positioning System berada di latar luar ruangan, dari beacon ultra-sonik dalam pengaturan ruangan, atau dari beberapa cara lain). Secara umum, paket akan diteruskan ke tetangga yang jarak tujuan adalah terpendek (membuat algoritma greedy, karena hanya informasi lokal yang digunakan dalam keputusan kedepannya).
Masalah routing paket ke node tertentu dalam jaringan ad hoc adalah yang paling penting. Namun, itu bukan paket hanya masalah routing. Beberapa kelas aplikasi mengharuskan paket diteruskan ke node tertentu berdasarkan isi yang terkandung di dalamnya. Penyebaran data adalah bentuk paling umum konten berbasis routing dalam penyebaran ad hoc seperti sensornets dan kendaraan jaringan. Secara umum, data yang dihasilkan oleh setiap node sudah bernama atau ditentukan.
Ringkasan
Pendekatan routing disurvei dan dirancang untuk jenis tertentu pada jaringan dan aplikasi. Permintaan yang memandu sepanjang rute yang query sebarkan. Namun, pendekatan berbasis konten yang telah dijelaskan di atas tidak berlaku secara luas cukup untuk beroperasi di komputasimeresap lingkungan. Sutradara difusi menggunakan flooding dan penguat, yang tidak tertentu untuk jaringan yang lebih besar (terutama jaringan besar yang berjenis sangat dinamis), dan penyimpanan data-sentris tentu saja tidak cocok untuk jaringan yang terdiri dari mobile node. Dynamic lingkungan komputasi pervasif, yang mencakup sensor jaringan dan mobile jaringan ad hoc, membutuhkan penemuan sumber daya protocol yang routing query mekanisme dapat beradaptasi terhadap perubahan tanpa membebani jaringan dengan protokol overhead, flooding layanan berbasis protocol seperti Rubi [90] yang mungkin untuk dilakukan. Protokol tersebut tidak akan berusaha untuk menemukan jalur terpendek ke sumber daya, karena jalan terpendek adalah pendek-hidup, dan biaya berasal dari jalur terpendek.
2.3.2 Algoritma Routing untuk Jaringan Terstruktur
Algoritma untuk alamat jaringan tradisional berbasis routing sangat terkenal [91 - 93]. Mereka tidak dibahas di sini karena penemuan sumber daya adalah berbasis konten prosedur, seperti diuraikan dalam Bagian 2.3.1. Bagian ini membahas routing protokol yang digunakan dalam jaringankonten-addressable dan berbagi sumber daya jaringan peer-to-peer. Diskusi Protokol routing Konten berbasis seperti Elvin [94] dan Gryphon [95] memiliki aplikasi dalam jaringan IP tradisional. Protokol ini menggunakan mempublikasikan /berlangganan paradigma ke konten peta untuk satu atau lebih konsumen. Elvin dijelaskan di sini untuk contoh kelas ini protokol. Elvin router mungkin federasi ke kelompok untuk meningkatkan kinerja dan ketahanan. Klaster atau router individu mungkin dihubungkan dengan router lain dan kelompok router untuk membentuk daerah-pesan luas jaringan. Sebuah router Elvin biasanya memiliki sebuah alamat yang terkenal dan harus dicapaioleh semua konsumen dan produsen.
Distributed Hash Tabel (DHT) algoritma telah datang untuk menonjol dalam penelitian sastra akhir-akhir ini. Namun, mereka masih akan digunakan dalam penyebaran utama di luar lingkup penelitian. Protokol routing di kelas ini meliputi BISA [96], Pastry [97], Tapis [98] dan Kademlia [99]. Tapi mungkin yang paling terkenal Protokol DHT adalah Chord [40]. Chord kunci peta node. Kunci m bit panjang dihasilkan oleh fungsi hash yang input data atau nama data untuk disimpan. Setiap node Chord memiliki ID yang diambil dari keyspace sama kunci yang dihasilkan dari data. Kunci peta ke node pertama yang lebih besar ID dari kunci (keyspace yang melingkar). Setiap node memiliki sebuah tabel ukuran jari m (panjang sama seperti tombol) yang berisi ID dan alamat subset yang lain node dalam DHT. Tabel ini dibuat sedemikian rupa sehingga setiap entrimencakup sebagian berturut-turut lebih besar dari keyspace. Secara khusus, jika ID node adalahn, i entri dalam tabel berisi node pertama yang berhasil n ID oleh sedikitnya 2i-1. Setelah menerima lookup pesan untuk k tombol, berkonsultasi node menerima jari tabel untuk menemukan r node yang paling dekat ID mendahului k dan mengacu pada querier ke node ini.
Ringkasan
Dari algoritma yang dijelaskan di atas, tabel hash didistribusikan paling dekatdicocokkan dengan tujuan protokol penemuan sumber daya untuk lingkungan terstruktur. Mereka bekerja dengan baik dalam jaringan tetap, dan mereka menyebar data merata atasnode dalam DHT (dengan asumsi penggunaan fungsi hash yang sesuai). Namun, untuk DHTs untuk berguna dalam penemuan sumber daya, deskripsi sumber daya, yang mungkinmengandung banyak atribut dan nilai-nilai, harus dipetakan ke kunci atau set kunci. Sebuah query, yangdapat juga berisi beberapa atribut dan nilai-nilai, serta ekspresi, juga harus dipetakan ke kunci atau set kunci. INS / Benang membuktikan bahwa ini dapat dicapai,meskipun query tidak dapat berisi ekspresi.
