Спосіб збору інформації в бездротовій сенсорній мережі

Реферат: Спосіб збору інформації в бездротовій сенсорній мережі (БСМ) побудований на основі теорії    графів. БСМ являє собою гіперграф - G N,I  , де N - множина вершин гіперграфу, кожна     вершина гіперграфу є об'єднанням вузлів БСМ тобто пікомережею, таким чином гіпергаф      складається з р-пікомереж, утворених в БСМ N  N1,N2 ,...,Np  , де p - показує кількість   пікомереж в БСМ, в свою чергу ребра гіпергафу - І, приставляють собою множину I інформаційних потоків, які виникають між вершинами гіперграфу, тобто I  1,I2 ,...,I j , де j кількість інформаційних потоків в БСМ, інформаційні потоки між вершинами гіперграфу об'єднують дві або більше вершин гіперграфу, в свою чергу пікомережа представляє собою об'єднання кластерів. UA 100463 U (54) СПОСІБ ЗБОРУ ІНФОРМАЦІЇ В БЕЗДРОТОВІЙ СЕНСОРНІЙ МЕРЕЖІ UA 100463 U UA 100463 U 5 10 15 20 25 Запропонована корисна модель належить до способів збору інформації з вузлів бездротової сенсорної мережі (БСМ) і може бути використана в мережах моніторингу та контролю для збору інформації з вузлів бездротової сенсорної мережі. Відомий спосіб розгортання сенсорної мережі (патент РФ № 2439812, МПК Н04Н 60/79, H04W 36/00, G06F 15/173 опубл. 10.01.2012 Бюл. № 1), що полягає в наступному: спрощення маршрутизації переданих повідомлень і зниження енергоспоживання в мережі відбувається за рахунок спільної роботи декількох сенсорних мереж. Побудова сенсорної мережі включає центральний пристрій обробки даних, сукупність базових станцій, вузлів і каналів зв'язку. В ході розгортання роботи сенсорної мережі виконують щонайменше один обмін значеннями власних координат і значеннями коефіцієнтів довіри між вузлами сенсорної мережі та/або базовими станціями мережі, з якими було встановлено зв'язок, з наступним визначенням вузлами мережі розрахункового значення власних координат. До недоліків цього способу належить той факт, що обробка даних проходить на центральному пристрої обробки даних (координаторі мережі), що приводить до зменшення часу роботи вузлів БСМ, а також збільшення енергоспоживання вузлів за рахунок необхідності обробки даних через координатор мережі. Найбільш близьким до запропонованої корисної моделі за суттю технічного рішення є спосіб (патент РФ № 2528415, H04W 40/04, H04W 72/12 20.09.2014 р. Бюл. № 26), в якому запропоновано спосіб і систему розподіленого балансування трафіку в бездротовій сенсорній мережі на основі алгоритму маршрутизації від вузла джерела до вузла призначення, де бездротова сенсорна мережа представляється як граф G (N, M) де N - вузли мережі, а М - грані. Мається K маршрутів, а інформація генерується зі швидкістю Qc і передається по каналу зв'язку С зі швидкістю qc, причому і-й вузол має запас енергії Еi, а кожна грань ij має вагу / ціну еi,j, яка відповідає енергії для передачі одного пакета даних від вузла і до j, а час життя T i кожного вузла визначається як: Ei Ti  c  qc  eij jM 30 35 40 45 50 jC На кожному вузлі визначається таблиця маршрутизації і вистроюється вектор передачі повідомлення, проводиться аналіз варіантів маршрутів по найбільш оптимальних сумарних векторах, які розраховуються за таблицею маршрутизації. Для цього визначається час життя всієї мережі. З метою досягнення максимального часу життя всієї мережі розподіляють маршрути, де вибір маршруту в мережі заснований на використанні найменш затратних передач на кожному вузлі, а найбільш затратні виключаються. До недоліків цього способу належить відсутність кластеризації мережі, який може бути використаний також як спосіб економії електроенергії в мережі. Технічною задачею запропонованої корисної моделі є збільшення часу роботи вузлів БСМ та зменшення їх енергоспоживання за рахунок розробки моделі БСМ із застосуванням теорії множин і графів (гіпергафів та мультиграфів) та використанням кластеризації мережі. Поставлена задача вирішується наступним чином. У способі збору інформації в бездротовій сенсорній мережі який побудований на основі теорії графів, згідно із запропонованою корисною   моделлю, БСМ являє собою гіперграф - G N,I  , де - N множина вершин гіперграфу, кожна       вершина гіперграфу є об'єднанням вузлів БСМ тобто пікомережею, таким чином гіпергаф     складається з р-пікомереж, утворених в БСМ N  N1,N2 ,...,Np  , де p - показує кількість     пікомереж в БСМ, в свою чергу ребра гіпергафу - І, приставляють собою множину інформаційних потоків, які виникають між вершинами гіперграфа, тобто I  1,I2 ,...,I j , де j I кількість інформаційних потоків в БСМ, інформаційні потоки між вершинами гіперграфу об'єднують дві або більше вершин гіперграфу, в свою чергу пікомережа представляє собою об'єднання кластерів. Технічним результатом є те, що при підході до побудови способу збору інформації в БСМ, що реалізується на основі гіперграфової моделі, спосіб враховує, що кожне ребро гіперграфу з'єднує не два вузли мережі БСМ, а дві та більше пікомережі, за рахунок чого зменшується надлишковий інформаційний потік, та відповідно збільшується час роботи вузлів БСМ та зменшується їх енергоспоживання, а використання пікомереж, як об'єднання кластерів дозволяє додатково зменшити енергоспоживання в мережі. 1 UA 100463 U На фіг. 1 зображено кластер БСМ, що складається з звичайних вузлів БСМ, а також маршрутизатора кластера (головного вузла кластеру).  5 10 На фіг. 2 показано пікомережу N1 та чотири кластери з яких вона складається. На фіг. 3 представлений гіперграф, як модель бездротової сенсорної мережі. Гіпергаф складається з вершин та ребер. Вершини гіперграфу - пікомережі. Ребра гіперграфу інформаційні потоки, що виникають між пікомережами. На фіг. 4 показаний мультиграф, як окремий випадок, коли інформаційні потоки з'єднують тільки дві вершини. Бездротову сенсорну мережу, згідно з корисною моделлю, представимо у вигляді множини вузлів: N  n1,n2 ,...,nN , (1)  як: all  де Nall - загальна кількість вузлів БСС без урахування типу пристроїв, яку можна визначити n Nall   Ni (2) i1 15 20 де Ni - і-й вузол БСМ. Такий підхід при виключенні маршрутизаторів характерний для однорангової мережі, де кожен пристрій може взаємодіяти з будь-яким іншим пристроєм, що знаходиться в межах його радіусу дії. Беручи до уваги, що БСМ складається з кінцевих пристроїв, роутерів і координатора, множина вузлів розбивається на три підмножини, які об'єднують всі три типи пристроїв в БСМ: N  K , N  R , N  E (3) де K - підмножина координаторів в мережі, R - підмножина роутерів в мережі, E підмножина кінцевих пристроїв в мережі. Відповідно, загальну кількість вузлів в мережі можна визначити як: 30 35 40 n k r e i1 25 j1 l1 s 1 Nall   Ni   N j   Nl   Ns (4) де k - кількість координаторів в мережі, згідно специфікації IEЕЕ 802.15.4 (IEЕЕ Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs) [Електронний ресурс] IEЕЕ Std. 802.15.4-2009 - Режим доступа: www/URL: http://standards.ieee.org/getieee802/download/802.15.4d-2009.pdf - 11.06.2014 г. - Загл. з екрану.), k = 1 - константа; r - кількість роутерів в мережі; e - кількість кінцевих пристроїв в мережі; Nj - j-й координатор в бездротової сенсорної мережі; Nl - l-й роутер в мережі; Ns - S-й кінцевий вузол в мережі. Використовуючи багаторівневий підхід при декомпозиції мережі, можна виділити три рівня ієрархії її структури: рівень координатора, рівень маршрутизатора, рівень кінцевих пристроїв. Що відповідає наведеним множинам у виразі (3). Об'єднання вузлів БСМ в кластер утворюється простий граф в двомірному просторі, як показано на фіг. 1. На фіг. 1 зображено кластер БСМ, що складається з звичайного вузла із підмножини Е, а також маршрутизатора кластера (головного вузла кластеру), що входить до підмножини R. Вся бездротова сенсорна мережа розбивається на підмножини вузлів, які назвемо пікомережами:  45 50 N  Nq , (5) де індекс  показує, що ця множина є пікомережею, q - номер пікомережі і приймає значення від 1 до p, p - кількість пікомереж в БСМ. Пікомережі являє собою об'єднання кластерів, як показано на фіг. 2. Кластерізація дозволяє збільшити час автономної роботи вузлів. Далі відповідно до способу збору інформації в БСМ пікомережі виступають вершинами гіперграфу, фіг. 3. Пікомережу взято за основу побудови моделі БСМ. З вищевикладеного випливає, що модель БСМ являє собою гіперграф:   G N,I  , (6)     2 UA 100463 U  де - N множина вершин гіперграфу, яка є множиною пікомереж (спеціально об'єднаних підмножин вузлів БСМ), I - множина інформаційних потоків. Безліч вершин гіперграфу складається з р-пікомереж, утворених в БСМ: 5 10 15 20      N  N1,N2 ,...,Np  , (7)   де p - кількість пікомереж в БСМ. Множина ребер гіперграфу є безліччю інформаційних потоків, що виникають між пікомережами: I  1,I2 ,...,I j , (8) I де j - кількість інформаційних потоків в БСМ. У гіперграфі кожним ребром можуть з'єднуватися не тільки дві вершини, але і будь-які підмножини вершин. Множина ребер гіперграфу є безліччю інформаційних потоків, що виникають між пікомережами. На фіг. 3 представлений гіперграф, як модель БСМ. Гіпергаф складається з вершин та ребер. Вершини гіперграфу - пікомережі. Ребра гіперграфу - інформаційні потоки, що виникають між пікомережами. На фіг. 4 показаний окремий випадок, коли інформаційні потоки І з'єднують тільки дві вершини, що є по суті мультиграфом, коли ребро графу може з'єднувати тільки дві вершини. Таким чином, авторами запропонований спосіб збору інформації в бездротовій сенсорній мережі, який дозволяє зменшити надлишковий інформаційний потік, та відповідно збільшити час роботи вузлів БСМ та зменшити їх енергоспоживання, а використання пікомереж, як об'єднання кластерів, дозволяє також додатково зменшити енергоспоживання в мережі і як наслідок збільшити час автономної роботи всієї мережі. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 25 30 Спосіб збору інформації в бездротовій сенсорній мережі (БСМ), який побудований на основі    теорії графів, який відрізняється тим, що БСМ являє собою гіперграф - G N,I  , де N     множина вершин гіперграфу, кожна вершина гіперграфу є об'єднанням вузлів БСМ тобто пікомережею, таким чином гіпергаф складається з р-пікомереж, утворених в БСМ      N  N1,N2 ,...,Np  , де p - показує кількість пікомереж в БСМ, в свою чергу ребра гіпергафу - І,   приставляють собою множину інформаційних потоків, які виникають між вершинами гіперграфу, I тобто I  1,I2 ,...,I j , де j - кількість інформаційних потоків в БСМ, інформаційні потоки між вершинами гіперграфу об'єднують дві або більше вершин гіперграфу, в свою чергу пікомережа представляє собою об'єднання кластерів. 3 UA 100463 U 4 UA 100463 U Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5