Andijon davlar universiteti fizika- matematika fakulteti axborot texnologiyalari kafedrasi

Simsiz tarmoqlarda algoritmlar
bluetooth simsiz tarmoq
Ushbu maqola optimallashtirilgan variantni taklif qiladi - mavjud echimlar asosida ishlab chiqilgan muqobil marshrutlash algoritmi. Dijkstri va Bellman-Ford algoritmlarida qo'llaniladigan eng qisqa yo'llarning qurilish tamoyillari va paketli o'tish tarmoqlari uchun an'anaviy o'rtacha kechikishlarni aniqlash usullari qo'llaniladi.
Repitorlar uchun ishlab chiqilgan alternativ marshrutizatsiya algoritmi barcha qisqa muddatlarda o'rtacha kechikishni minimallashtirishga va bo'limlardagi kechikishlarni aniqlashda statik tarmoq xususiyatlarini (aloqa kanallarining topologiyasi va tarmoqli kengligi) va o'tkaziladigan transportning xarakatini (turli turdagi transportlar uchun optimal kechikishlar hisobga olingan holda) tahlil qilishni o'z ichiga oladi.
Algoritm aloqa kanallarining tarmoqli kengligi qobiliyatlarini optimallashtirish, bu ma'lumotlarga asoslanadigan optimal og'irlik yo'llarini hisoblash va kechikishning ayrim turdagi yo'llarning umumiy qabul qilingan uzatish xususiyatlariga mos kelishi mumkin bo'lgan marshrutlar bo'ylab oqim tahliliga asoslangan tarmoqni kechiktirish funktsiyasini minimallashtirish nuqtai nazaridan tahlil qilish mexanizmlarini taqdim etadi.
Algoritm Dijkstra va Bellman-Ford algoritmlarida qo'llaniladigan eng qisqa yo'llarni qurish printsiplarini va paketli tarmoqlar uchun an'anaviy bo'lgan o'rtacha kechikishlarni aniqlash usullarini qo'llaydi. Algoritmning funktsional blok diagrammasi rasmda ko'rsatilgan va quyidagi komponentlarni o'z ichiga oladi:
1. Optimal tarmoqli kengligini aniqlash uchun blok - asosiy tarmoq topologiyasini tahlil qiladi va optimal tarmoqli kengligini aniqlaydi. Olingan ma'lumotlarga asoslanib, kelgusida tahlil qilish uchun tarmoqli kanallar kanalining og'irligini hisoblab chiqadi.
2. O'rtacha kechikish vaqtini tahlil qilish - tarmoqdagi optimal tarmoqli kengligi va dastlabki oqimlarga asoslangan tarmoqdagi o'rtacha kechikish vaqtini hisoblash uchun javob beradi.
3. To'siqlarni aniqlashning blokirovkasi - barcha tarmoq tugunlari orasidagi eng qisqa marshrutlarni yaratish uchun javobgardir.
4. Blokning ruxsat etilgan oqimi - eng qisqa yo'llarda oqimlarning taqsimlanishini ta'minlaydi.
5. O'rtacha kechikishni minimallashtirish bloki - tarmoqdagi o'rtacha kechikishning minimal darajadagi funktsiyasi asosida oqimning sapmasını hisoblashni ta'minlaydi.
6. Algoritm tanasi - har bir blokning ishini birlashtiradi va algoritmning izchil ishlashini ta'minlaydi.
Shakl - oqim sxemasi
Biz yaratilgan algoritm yordamida hal qilinishi kerak bo'lgan vazifalarni quyidagicha ifodalaymiz:
muammoni hal qilish uchun kanallardan eng maqbul foydalanish quyidagilar:
a) tarmoqdagi tarmoqli chastotali aloqa kanallarini tahlil qilish va optimal yorliqlarni hisoblash;
b) muqobil marshrutlardan foydalanish;
c) jami marshrut metrikalari nisbati emas, balki ushbu marshrutning maksimal kanal metrikalari nisbati bo'yicha alternativ marshrutlar orasidagi trafikni taqsimlash;
d) faqat maksimal uzatish vaqtining mezoniga ko'ra foydalanish uchun mavjud bo'lgan muqobil yo'nalishlarni tanlash (marshrutni marshrutni uzatish vaqti ushbu turdagi yo'l uchun ruxsat etilgan maksimaldan oshmasa foydalanish uchun qabul qilinishi mumkin).
2) tarmoq uzatish parametrlariga bo'lgan talablarga rioya qilish.
a) murakkab topologiyalar tarmoqlarida xabarlarni uzatishda kechikishni minimallashtirish;
b) SCRni kechiktirishni kamaytirish.
Algoritm asosida ishlashning optimalligini taxmin qilaylik.
Biz quyidagilarni bildiramiz:
bu erda maqsad tugunining juftligi - qabul qiluvchi tugun; Birinchi formula - i-kanalga boradigan paketlarning oqimi; ikkinchisi - tugunni tarmoqqa keladigan paketlar oqimi.
Biz i-th kanali yuklarini paketlar sifatida quyidagi formula bo'yicha ko'rib chiqamiz:
birinchi omil o'rtacha paket uzunligi, Di esa tarmoqli kengligi
i-th kanali.
I-kanalidagi o'rtacha paketlar soni:
Tarmoqdagi tugunlar umumiy sonini hisobga olgan holda, tarmoq uchun umumiy paketlar soni o'rtacha:
Littlening formulasiga ko'ra
bu erda T - o'rtacha tarmoq uzilishidir. Shunday qilib, biz formulani qo'lga kiritamiz
Kleinrock o'rtacha tarmoq latentligini tahlil qilish uchun:
Kechiktirilgan vaqtni baholash uchun olingan formulalar turli optimallash muammolarini hal qilishda samarali qo'llaniladi. Bunday vazifalar tarmoqli kengligi optimallashtirish va xabarlarni uzatish yo'nalishlarini tanlashni o'z ichiga oladi.