PRAKTEK 2

   Routing Probabilistik di Jaringan Terhubung

abstrac

Kami mempertimbangkan masalah perutean dalam jaringan yang terhubung secara terputus-putus. Di jaringan seperti itu ada

tidak ada jaminan bahwa jalur yang sepenuhnya terhubung antara sumber dan tujuan tersedia kapan saja, rendering

protokol perutean tradisional tidak dapat mengirimkan pesan antar host. Kami mengusulkan probabilistik

protokol routing untuk jaringan tersebut.

I. Pendahuluan

Biasanya, salah satu persyaratan paling dasar untuk memungkinkan dua node berkomunikasi melalui jaringan adalah itu

ada jalur yang sepenuhnya terhubung di antara mereka. Namun, ada skenario di mana hal ini tidak terjadi, tetapi

di mana masih akan diinginkan untuk memungkinkan komunikasi antar node. Skenario tersebut termasuk komunikasi antara desa-desa populasi Saami penggembala rusa kutub di utara Swedia [4], dan populasi dan populasi aborigin lainnya di daerah miskin [6], tetapi

juga komunikasi satelit [7], jaringan sensor [1], dan

area lain di mana Delay Tolerant Networking (DTN)

arsitektur [2] menarik. Dalam jaringan seperti itu, mobilitas node dapat digunakan untuk memungkinkan pengiriman pesan

- misalnya, meskipun tidak pernah ada jalur antar node

A dan C, A mungkin bertemu dengan node B dan memberikan pesan padanya,

dan B mungkin nanti akan menemukan C, mengirimkan pesan ke

tujuan akhirnya. Di bagian selanjutnya, beberapa mungkin

pendekatan untuk perutean dalam jaringan tempat konektivitas berada

intermiten dibahas, dan protokol routing probabilistik untuk jaringan tersebut diuraikan.

II. Pekerjaan yang berhubungan

Vahdat dan Becker menyajikan protokol untuk rute epidemi

dalam jaringan yang terhubung sebentar-sebentar [8]. Saat dua node

bertemu satu sama lain, mereka bertukar pesan yang dibawa (tunduk pada ruang buffer), sehingga menyebabkan pesan menjadi

menyebar melalui jaringan seperti wabah penyakit.

Pendekatan ini memastikan bahwa pesan mencapai tujuannya secepat mungkin, tetapi juga menghabiskan banyak sumber daya

melalui transfer pesan yang tidak perlu.

Karena ambiguitas dalam memutuskan apa lompatan terbaik berikutnya

adalah jaringan yang dibahas di sini, Chen dan Murphy mengusulkan

bahwa aplikasi harus dapat memengaruhinya melalui

pengenalan fungsi utilitas [3], memungkinkan aplikasi

untuk menentukan bobot dari beberapa faktor yang mempengaruhi fungsi. Dalam solusi yang diusulkan, yang disebut Komunikasi Transitif Terputus, protokol penemuan digunakan untuk menemukan

hop terbaik berikutnya dalam cluster yang saat ini terhubung

node.

Grossglauser dan Tse mendekati jenis perutean ini dari

sudut pandang yang sedikit berbeda [5]. Satu masalah besar

dengan jaringan ad hoc adalah bahwa karena gangguan transmisi bersamaan antara node, skala mereka buruk. Oleh

hanya melakukan komunikasi lokal antara tetangga dan

Alih-alih mengandalkan pergerakan node untuk membawa pesan ke tujuannya, ternyata masalah ini bisa jadi

III. Perutean probabilistik

Sebagian besar pengguna biasanya tidak bergerak sepenuhnya secara acak, sehingga pola pergerakan cenderung dapat diprediksi, seperti jika suatu lokasi sering dikunjungi

di masa lalu, kemungkinan akan dikunjungi lagi di masa mendatang. Kami ingin menggunakan pengamatan ini untuk meningkatkan kinerja perutean dengan melakukan perutean probabilistik.

Metrik probabilistik yang disebut prediktabilitas pengiriman, dibuat di setiap node untuk setiap tujuan yang diketahui yang menunjukkan peluang prediksi node tersebut untuk menyampaikan pesan

ke tujuan itu. Ketika sebuah node bertemu dengan node lain,

mereka bertukar informasi tentang prediksi pengiriman yang mereka miliki dan memperbarui informasi mereka sendiri. Berdasarkan prediksi pengiriman, keputusan adalah

kemudian dibuat tentang apakah akan meneruskan pesan tertentu atau tidak

ke node ini.

III.A. Perhitungan prediktabilitas pengiriman

Protokol mengandalkan metrik prediktabilitas pengiriman,

P ∈ [0, 1], yang mencerminkan kemungkinan bertemu dengan node tertentu. Metrik itu harus digunakan untuk mendukung

keputusan apakah akan meneruskan pesan ke a

node tertentu.

Setiap kali node ditemukan, metriknya harus

diperbarui menurut (1), di mana P (a, b) adalah pengiriman prediktabilitas node a memiliki untuk node b, dan Pinit ∈ [0, 1] adalah an

konstanta inisialisasi. Ini memastikan bahwa node yang sering ditemui memiliki prediktabilitas pengiriman yang tinggi.

Jika sepasang node tidak bertemu satu sama lain dalam beberapa saat,

mereka cenderung menjadi penerus pesan yang baik

satu sama lain, sehingga nilai prediktabilitas pengiriman harus menua,

dikurangi dalam prosesnya. Persamaan penuaan ditampilkan

di (2), di mana γ ∈ [0, 1) adalah konstanta penuaan, dan k adalah

jumlah unit waktu yang telah berlalu sejak terakhir kali

metrik sudah tua. Satuan waktu yang digunakan bisa berbeda, dan

Ulasan Komputasi dan Komunikasi Seluler, Volume 7, Nomor 3 19

harus didefinisikan berdasarkan aplikasi dan yang diharapkan

penundaan di jaringan yang ditargetkan.

P (a, b) = P (a, b) old × γk (2)

Prediksi pengiriman juga memiliki sifat transitif, yaitu berdasarkan pengamatan bahwa jika node A sering bertemu dengan node B, dan node B sering bertemu dengan node C, maka node C mungkin merupakan node yang baik untuk diteruskan

pesan yang ditujukan untuk node A ke. Persamaan 3 menunjukkan bagaimana

transitivitas ini mempengaruhi prediktabilitas pengiriman, di mana

β ∈ [0, 1] adalah konstanta penskalaan yang memutuskan seberapa besar dampak transitivitas seharusnya pada prediktabilitas pengiriman.

III.B. Pengambilan keputusan

Dalam protokol perutean tradisional, memilih kemana akan diteruskan

sebuah pesan biasanya merupakan tugas sederhana; pesan sudah terkirim

ke tetangga dengan jalur biaya terendah ke tujuan (biasanya berarti jumlah lompatan paling sedikit). Biasanya

pesan juga hanya dikirim ke satu node karena keandalan jalur relatif tinggi. Namun, dalam pengaturan

kami membayangkan di sini, semuanya sama sekali berbeda. Ketika sebuah

pesan tiba mungkin tidak ada jalur ke tujuan

jadi node harus menyimpan pesan untuk sementara dan masing-masing

saat bertemu node lain itu harus membuat keputusan jika

itu harus meneruskan pesan ke node itu atau tidak. Itu mungkin

juga bijaksana untuk meneruskan pesan ke beberapa node ke

meningkatkan kemungkinan pesan benar-benar terkirim

ke tujuannya.

Sayangnya, keputusan ini tidak mudah dibuat. Di

dalam beberapa kasus mungkin masuk akal untuk memilih ambang tetap dan hanya memberikan pesan ke node yang memiliki pengiriman

prediktabilitas di atas ambang itu untuk tujuan

pesan. Di sisi lain, saat menemui node

dengan prediktabilitas penyampaian yang rendah, belum tentu a

node dengan metrik yang lebih tinggi akan ditemui dalam waktu yang wajar, jadi ada juga situasi di mana kita

mungkin ingin tidak terlalu ketat dalam memutuskan kepada siapa akan memberi pesan. Lebih jauh, ada masalah dalam memutuskan caranya

banyak node untuk memberikan pesan tertentu. Mendistribusikan a

pesan ke sejumlah besar node meningkatkan kemungkinan pengiriman pesan ke tujuannya, tetapi lebih

sumber daya terbuang percuma. Di sisi lain, memberikan pesan hanya ke beberapa node (mungkin hanya satu node) akan digunakan

sedikit sumber daya, tetapi kemungkinan menyampaikan pesan

mungkin lebih rendah, dan penundaan yang ditimbulkan tinggi. Sejumlah

trade-off harus dipertimbangkan saat membuat keputusan.

Jadi, menurut kami strategi yang diadopsi untuk pesan tertentu harus dipilih berdasarkan per pesan untuk memungkinkan aplikasi memenuhi kebutuhan khusus datanya. Satu

Situasi yang harus dihadapi adalah kasus dimana suatu sistem

baru saja dimulai sedemikian rupa sehingga tidak ada prediksi pengiriman

informasi tersedia (atau jika mobilitas sedemikian rupa sehingga prediksi itu sulit). Dalam kasus seperti itu, protokolnya harus jatuh

kembali ke beberapa varian epidemi (mungkin secara acak)

rute.

IV. Pekerjaan masa depan

Penggunaan ucapan terima kasih untuk menghapus pesan

jaringan setelah pengiriman ke tujuan mereka akan diselidiki. Mengabaikan melakukan ini akan mengakibatkan hal yang tidak perlu

transfer pesan, membuang sumber daya sistem yang berharga.

Simulasi ekstensif dari protokol yang diusulkan akan dijalankan

untuk mengevaluasi protokol, dan untuk menyelidiki dampak

pengaturan parameter yang berbeda dan strategi pengambilan keputusan.

Lebih lanjut, akan baik juga untuk mengevaluasi secara analitis

protokol untuk menentukan kesesuaian persamaan yang dipilih untuk perhitungan prediksi pengiriman