Спосіб мережного кодування даних на основі системи залишкових класів

Реферат: UA 96835 U UA 96835 U 5 10 15 20 25 30 35 40 45 50 Корисна модель належить до систем передачі інформації, які можуть бути використані для передавання та приймання дискретних інформаційних повідомлень. Відомий спосіб мережного кодування, що ґрунтується на тому, що проміжний вузол створює лінійні комбінації декількох прийнятих пакетів з коефіцієнтами із кінцевого поля Галуа і передає їх далі по мережі, замість того, щоб передавати кожний пакет окремо [1]. Основним недоліком такого способу є значне збільшення службових даних в пакеті протоколу і реалізація способу потребує значних обчислювальних ресурсів для кодування/декодування повідомлень, відповідно не може бути використане в сенсорних мережах, які характеризуються малими розмірами пакетів і мають обмежену пропускну здатність каналів зв'язку. Найбільш близьким за технічною суттю до винаходу, що заявляється, є спосіб мережного кодування в системі залишкових класів, при якому здійснюється кодуванні з використанням прямого перетворення системи залишкових класів та декодуванням на основі китайської теореми про залишки [2]. Суть способу полягає в тому, що здійснюється розділення повідомлення на взаємно прості модулі і отримані залишки ретранслюються в наступні вузли мережі. В проміжних вузлах отримані залишки об'єднуються в пакети на основі китайської теореми про залишки і передаються в наступний вузол мережі. Проте такий спосіб передбачає передавання одних і тих же повідомлень різними маршрутами, тобто відбувається дублювання повідомлень, що в результаті призводить до зниження корисної пропускної здатності мережі. В основу корисної моделі поставлена задача розробки нового способу передавання інформації шляхом використання мережного кодування в системі залишкових класів, який для розділення повідомлення на частини в системі залишкових класів використовує модулі різної розрядності, що забезпечує підвищення загальної пропускної здатності мережі та зменшення обчислювальної складності алгоритмів кодування/декодування. Поставлена задача вирішується завдяки тому, що спосіб мережного кодування на основі системи залишкових класів, при якому повідомлення в вихідному вузлі розділяється на дві і більше частини (залишки b i ), отримані залишки передаються наступним вузлам, згідно з корисною моделлю, взаємно прості модулі вибираються різної розрядності, а розподіл частин повідомлення між доступними маршрутами відбувається за умовою, щоб обсяг повідомлень, які передаються по незалежних маршрутах і які передаються по спільних маршрутах повинні були однакові, що забезпечить ефективне використання пропускної здатності каналів передачі даних мережі. Корисна модель пояснюється кресленнями, де на фіг. 1 зображено топологію мережі, яка складається з восьми вузлів (А, В, С, D, Е, F, G, S) і використовує мережне кодування в системі залишкових класів для передавання повідомлень. На фіг. 2 зображена блок схема алгоритму мережного кодування: в (фіг. 2, бл. 1) відбувається вибір взаємно простих модулів та їх розподіл для всіх вузлів мережі. На наступному кроці з отриманого повідомлення обчислюються залишки по вибраних модулях (фіг. 2, бл. 2), які передаються по знайдених маршрутах (фіг. 2, бл. 3). При умові, що наступний вузол мережі є незалежним (вузол, який ретранслює дані тільки від одного джерела) (фіг. 2, бл. 4) по даному маршруту передаються залишки більшої розрядності, в іншому випадку дані обробляються на проміжному вузлі (фіг. 2, бл. 6) і передаються наступним вузлам в маршруті. Таким чином дані (залишки) поступають на кінцевий вузол (фіг. 2, бл. 8) (базову станцію), де відбувається їх відновлення (фіг. 2, бл. 9) в позиційну систему числення. Спосіб здійснюють таким чином. Для передавання повідомлень X1 і X2 вузлу S (фіг. 1) вибираємо взаємопрості модулі p1, p2 , p3 , p4 . У вузлі A розділяємо повідомлення X1 на модулі p1, p2 : отримаємо b1  X1 mod p1 , b2  X1 mod p2 . У вузлі B розділяємо повідомлення X2 на модулі p3 , p4 : b3  X2 mod p3 , b4  X2 mod p4 . Отримані залишки передаємо відповідними маршрутами (фіг. 1). У проміжному вузлі D відбувається об'єднання залишків b1, b2 , b3 , b4 за формулою [3]: n X   B i  b i mod R  , (1) i 1 UA 96835 U n R   p i , n - кількість модулів, B i - базисні числа, B i   i  mi ,  i  де i1 5  i  mi  1mod p i  , m i - коефіцієнт, який знаходиться в межах 0  mi  p i , і формування нових залишків по модулях p2 , p3 : b5  X mod p2 , b6  X mod p3 , R , pi або b5  X mod p5 , де p5  p2  p3 . 10 Для передачі повідомлень X1, X2 в мережі необхідно передати сім пакетів даних (фіг. 1). Пакет даних складається із залишків та значень взаємопростих модулів і має вигляд: b , b ,...b ...b 1 2 i n pi , pi1. В вузлі 15 20 S відбувається об'єднання залишків за формулою (1) та обчислення значень X1  X mod p1 p2 і X2  X mod p3  p4 . Для розділення даних у вихідних вузлах A і B вибираються взаємопрості модулі різної розрядності, при цьому залишки більшої розрядності b1, b4 передаються по незалежних маршрутах C  F  S, E  G  S а залишки меншої розрядності b2 , b3 по спільному маршруту D  S . Джерела інформації: 1. Fragouli С, Le Boudec J. Υ., Widmer J. Network coding: an instant primer // ACM SIGCOMM Computer Communication Review. - 2006. - T. 36. - №. 1. С. 63-68. 2. Zhang Zhifang. Network Coding Based on Chinese Remainder Theorem. arXiv preprint arXiv: 1208.3966, 2012. 3. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. Радио. - 1968. - 460 с. 25 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб мережного кодування даних на основі системи залишкових класів, при якому повідомлення у вузлі відправнику розділяють на частини з використанням двох і більше взаємопростих модулів і отримані залишки передають різними маршрутами, які в приймальному вузлі об'єднують на основі китайської теореми про залишки, який відрізняється тим, що в вихідних вузлах при розділенні повідомлень використовують взаємопрості модулі різної розрядності, а передачу отриманих залишків здійснюють різними маршрутами, залишки більшої розрядності передають по незалежних маршрутах, а меншої розрядності по спільних маршрутах. 2 UA 96835 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3