Енергоефективний кворумний протокол MAC для бездротових мереж датчиків

1. 1. Передбачення та припущення Припущення, зроблені в запропонованому алгоритмі, такі: (а) всі датчикові...
2. 3. Планування Wake-Up
3. Рис.
4. 2.
5. Рис.
6. 4.
7. Рис.

1. Передбачення та припущення

Припущення, зроблені в запропонованому алгоритмі, такі: (а) всі датчикові вузли є статичними; отже, не приймається до уваги динамічний контроль топології сенсорних вузлів внаслідок мобільності, і (b) всі датчикові вузли мають однаковий діапазон передачі і передають дані на загальну мийку; це складається з двох фаз; а саме, побудова CDT і планування будильника з використанням протоколу HQMAC.

Перша фаза полягає в конструюванні CDT, що складається з домінуючих, домінаторів, з'єднувачів і вузла датчика раковини або вузла датчика ініціатора. На другому етапі розроблено енергоефективний протокол MAC, який називається HQMAC, щоб дозволити тільки домінуючі сенсорні вузли переходити в стан сну і пробудження на основі власного трафіку. Цей протокол використовує нову систему сіток під назвою BiQuorum, яка допомагає протоколу бути більш ефективним з точки зору енергії та пропускної здатності. Всі домінатори агрегують дані від своїх домінуючих і направляють їх до вузла датчика раковини через роз'єми.

2. Побудова CDT

Бездротова мережа представлена ​​у вигляді графіка G ( V , E ), де вершини позначені V і ребра позначені E. Підмножина S з V називається домінуючою множиною (DS), якщо кожен сенсорний вузол у V G є або доступним у підмножині S, або є суміжним з щонайменше одним датчиком у S. CDS, яку ми позначимо як C , G є одночасно пов'язаним підграфом G і DS. Тому всі вузли датчика в графі G можуть зв'язуватися з щонайменше одним датчиком вузла в С з однією відстанню переходу. Незалежний набір (IS) є підмножиною, яку ми позначимо через D , графа G, якщо для будь-яких двох вершин D не існує краю між ними. Коли будь-який доданий вузол датчика до D порушує властивість IS графа, ідентифікується як максимальний незалежний набір (MIS), який є одночасно IS і DS.

Побудова CDT включає початкову фазу, за допомогою якої створюється MIS для визначення домінаторів. Далі йде друга фаза, в якій розпізнаються роз'єми і домінуючі пристрої з'єднуються з раковиною.

А. Створення МІС

Датчикові вузли в межах MIS, або домінатори, є вузлами датчиків, які діють як головка кластера конкретного кластера. Зона покриття голови кластера фіксована. Будь-які два вузли датчика в зоні покриття будуть розглядатися як вузли сусідніх датчиків. Наступний алгоритм, Алгоритм 1, створює MIS і ідентифікує домінуючі.

• Алгоритм 1. Створення MIS ( G ( V , E )).

• 1: // n : вузол датчика, N : сусід, E res: залишкова енергія, i : датчик вузла датчика

• 2: Ініціалізація MISBlack, NMISGrey = {ϕ}

• 3: initiatorNode = i

• 4: MISBlack = MISBlack U { i }

• 5: для всіх n ∈ N ( i )

• 6: NMISGrey = NMISGrey U { n }

• 7: endfor

• 8: виконайте наступне, доки весь V ∈ (MISBlack || NMISGrey)

• 9: для всіх x ∈ N ( i ) роблять

• 10: для всіх y ∈ N ( x )

• 11: MaxRes ( Y ) = Макс ( E res ( y ))

• 12: якщо E res ( x )> MaxRes ( Y )

• 13: MISBlack = MISBlack U { x } // Домінатори

• 14: NMISGrey = NMISGrey U { N ( x )} // Домінанти

• 15: endif

• 16: endfor

• 17: endfor

Спочатку всі суміжні сенсорні вузли раковини кольорові сірі. Серед сусідів сірих вузлів датчика, вузол датчика з найвищою енергією приймається як домінатор, доданий до набору, а потім змінюється на чорний; потім всі сусіди вибраного домінатора пофарбовані в сірий колір. Тому, як цей процес продовжується, ми в кінцевому підсумку прийдемо до ситуації, коли всі домінатори пофарбовані в чорний колір, і всі домінанти пофарбовані в сірий колір. Енергетична оцінка ідентифікації домінатора проводиться під час кожного раунду, і домінант буде обраний у кожному раунді. Залишкова енергія домінатора, ідентифікована в даному раунді j , обчислюється шляхом віднімання споживання енергії домінатора, ідентифікованого під час попереднього раунду, j - 1, з залишкової енергії цього ( j - 1) th-round домінатора.

де Xi ( j - 1) - споживання енергії домінатора Xi під час раунду j - 1 і Yi ( j - 1) - споживання енергії члена кластера Yi під час раунду j - 1. З (1) і (2) , обчислюється залишкова енергія датчика вузла i під час кругового j , E r i ( j ). Під час кожного раунду датчик вузла з найбільшою залишковою енергією; тобто, max ( E r i ( j )), буде обрано як домінатор для цього раунду.

B. Створення з'єднувачів

З'єднувачі вибираються особливим чином, за допомогою яких часто не використовуються надлишкові домінатори. Після вибору dominator під час кожного раунду, односпрямовані сусідні датчикові вузли раковини, що з'єднує максимальну кількість домінаторів, виявляються роз'ємами і забарвлені в червоний колір. Раковина, роз'єми та домінатори разом утворюють CDS. Наступний алгоритм, Алгоритм 2, розпізнає датчики ретрансляційних вузлів або роз'єми, необхідні для підключення домінаторів до вузла датчика раковини.

• Алгоритм 2. Створення з'єднувачів ( G ( V , E )).

• 1: initiatorNode = i ;

• 2: Ініціалізація ConnectorRed, CDT = {ϕ}

• 3: для всіх n ∈ N ( i )

• 4: знайдемо n, яке має максимальне число N ( n ) ∈ MISBlack

• 5: ConnectorRed = ConnectorRed U { n } // З'єднувачі

• 6: endfor

• 7: для всіх n ∈ MISBlack

• 8: CDT = {CDT} U { n } U {Коннектор Red} U {NMISGrey}

• 9: endfor

• 10: endwhile

Якщо будь-який член кластера або домінант в CDT повинен виконати передачу даних в раковину, то домінатор або відповідна голова кластера кластера передає дані через з'єднувач до вузла датчика раковини.

3. Планування Wake-Up

Після того, як CDT побудований, моделі сну і пробудження будуть обрані кожним вузлом датчика. Інтервали часу радіомаяка, які представляють стан сну і пробудження вузлів датчиків, класифікуються на часові інтервали кворуму або не кворуму. Інтервали часу кворуму означають час пробудження, а тимчасові інтервали без кворуму означають час сну на вузлах датчика. Часові інтервали датчиків вузлів поділяються на 16 часових інтервалів.

A. BiQuorum

Система кворуму є набором непустових підмножин елементів; кожна підмножина називається кворумом, що досягає властивості перетину. У системі кворуму інтервали часу пробудження організовуються в перекриваються кворумах, так що кожен кворум перекривається з кожним іншим кворумом. Тут ми пропонуємо систему BiQuorum - систему, яка ґрунтується на концепції кворуму і яка забезпечує як адаптивне, так і низьке співвідношення кворумів, що перевершує існуючі системи кворумів. Термін "Intersect" використовується в наступних визначеннях для позначення запропонованої системи кворуму.

З урахуванням універсального множини Z = {0, 1, ..., n - 1}, де n - ціле число, позначимо X як безліч непорожніх підмножин Z , і це називається перетином, якщо для всіх A , A ' ∈ X , A' A ' ≠ {ϕ}. Наприклад, для множини Z = {0, 1, 2, 3, 4} X називається перетинанням, якщо X = {{1, 2}, {2, 3, 4}, {2, 4} }. Тут будь-які дві підмножини X ; {1, 2} ... {2, 3, 4} буде мати перетин, який дозволить вузлам датчиків зустрічатися один з одним, де елементи X - інтервали часу пробудження вузлів датчика.

З урахуванням універсальної множини Z = {0, 1, ..., n - 1}, де n - ціле число, позначимо A і B двома непорожніми підмножинами Z. Пара ( A , B ) називається “BiIntersect”, якщо для всіх X ∈ A , Y ∈ B , X ≠ Y ≠ {ϕ}. Наприклад, для множини Z = {0, 1, 2, 3, 4} пара ( A , B ) називається BiIntersect, якщо A = {{0, 1}, {3, 4}, { 0, 1, 4}} і B = {{0, 3}, {0, 4}}.

Визначення 3.1: C-Intersect ( Y ). Враховуючи універсальну множину Z = {0, 1, ..., n - 1}, де n - натуральне число, Y позначає ціле число, значення якого дорівнює одиниці. "C-Intersect (1)", позначений як CI (1), визначається як

Наприклад, у Рис , коли n = 16, і якщо n показано як сітка, CI (1) = {0, 4, 8, 12}.

Рис.

C-Intersect (1).

Визначення 3.2: R-Intersect ( X ). З урахуванням універсальної множини Z = {0, 1, ..., n - 1}, де n додатне ціле число, позначимо X як ціле число, 1 ≤ X ≤. "R-Intersect ( X )", позначений як RI ( X ), визначається як

де, i = 1, ..., X і

Наприклад, якщо n = 16, і якщо n показано як сітка, коли i = 1, j = 1, 2, 3, 4, то RI (4) = {0, 5, 10, 15}; а коли i = 2, j = 5, 6, 7, то RI (4) = {4, 9, 14}; а коли i = 3, j = 9, 10, то RI (4) = {8, 13}; а коли i = 4, j = 13, то RI (4) = {12}. Тому, RI (4) = {0, 4, 5, 8, 9, 10, 12, 13, 14, 15}, оскільки X = 4. Аналогічно для RI (1) = {0, 5, 10, 15} , RI (2) = {0, 4, 5, 9, 10, 14, 15}, а RI (3) = {0, 4, 5, 8, 9, 10, 13, 14, 15}; результати показані в 2 .

2.

R-Перехрестя (X): (a) RI (1), (b) RI (2), (c) RI (3), і (d) RI (4).

Задавши ціле число X , 1 ≤ X ≤, нехай C і D - множини непорожніх підмножин Z , де Z = {0, 1, 2, 3, ..., n - 1}. Пара ( C , D ) називається ( X , 1) BiQuorum тоді і тільки тоді, коли наступне утримання: (i) C є RI ( X ) і D є CI (1) або D є RI ( X ) і C являє собою CI (1); і (ii) пара ( C , D ) є BiIntersect. Наприклад, для n = 16, a (4, 1) BiQuorum показано в Рис .

Рис.

(4, 1) BiQuorum.

Перехрестя між RI і CI гарантоване. Кількість перетинів буде варіюватися від 1 до залежно від значення X. Перевага цієї системи полягає в тому, що розмір РІ істотно менший порівняно з розміром системи кворуму дигір. Наприклад, RI (4) і CI (1), які утворюють (4, 1) BiQuorum, мають чотири перетину, як показано в 4 . Аналогічно, (1) BiQuorum має перехрестя.

4.

Перекриття інтервалів часу пробудження датчика.

B. Асинхронне планування Wake-Up

У плані асинхронного пробудження немає необхідності в синхронізації часу. У протоколі HQMAC, хоча вузли датчиків слідують за власним графіком пробудження, перекриття між інтервалами пробудження гарантовано, навіть якщо є дрейф годинника.

Визначення 3.4. Для будь-якого заданого натурального числа ( a ) і кворуму ( Y ) в системі кворуму Q під Z = {0, ..., n - 1} визначаємо RC ( Y , a ) = {( a + b ) mod n | b ∈ Y }.

Визначення 3.5: Властивість закриття. Система кворуму Q за Z = {0, ..., n - 1} має замикання обертання, якщо для всіх X , Y ∈ Q , a ∈ {0, ..., n - 1}: X RC ( Y , a ) ≠ {ϕ}.

Визначення 3.6. Система BiQuorum виконує властивість закриття обертання.

Доказ. Нехай Q - BiQuorum розміру. Нехай A ∈ Q , який містить ліві діагональні елементи сітки; а саме, {(0, +1, 2 + 2, ..., n - 1) mod n }. Звідси випливає, що A (RC ( B , a ) ≠ {ϕ}, де B ∈ CI (1). Таким чином, вузли датчика можуть переносити дрейф часового інтервалу, оскільки система BiQuorum виконує замикання обертання. ■

Теорема 1. Будь-які вузли A та B, які виконують систему BiQuorum, мають максимум X перетинів для кожного n інтервалу циклу. Нехай A ∈ RI ( X ) і B ∈ CI (1). Тоді для будь-яких двох заданих чисел, наприклад a та b , ми маємо RC ( A , a ) (RC ( B , b ) ≤ X.

Доказ. Для RC ( A , a ), B максимальне число перетинів при X = 1 дорівнює 1, а максимальне число перетинів при X = 2 дорівнює 2, і так далі. Таким чином, загальна кількість перетинів ідентифікується

Аналогічно, для A (RC ( B , b ) максимальна кількість перетинів дорівнює 1 при X = 1, а максимальне число перетинів - 2, коли X = 2, і так далі. Таким чином, загальна кількість перетинів ідентифікується

Отже, за формулами (5) і (6)

Як можна бачити в (7), цілком очевидно, що два сусідніх вузла датчика, які приймають ( X , 1) BiQuorum, будуть зустрічатися один з одним протягом X часових інтервалів на n часових інтервалів, навіть якщо є дрейф годинника.

Якщо вузли датчиків A і B приймають RI (2) і CI (1), щоб сформувати (2, 1) BiQuorum як їхній зразок циклу, і якщо є дрейф часового інтервалу, що дорівнює двом, то вищезазначена теорема Доводить, що інтервали часу пробудження як A ', так і B будуть перетинатися принаймні двічі протягом циклу 16. Рисунок 5 показаний перекриття часових інтервалів, незважаючи на два дрейфу часу у часовому інтервалі у вузлі датчика А. У RC ( A , 2) (RC ( B , 0) (2, 1) BiQuorum є два перетину. ■

Рис.

Після двох проміжків часу-слота в вузлі А.

C. Протокол HQMAC

Протокол HQMAC використовує BiQuorum, чиї важливі особливості, такі як мінімальний коефіцієнт кворуму, призводять до високого енергозбереження та мінімального NS; і максимальна кількість точок рандеву призводить до максимальної пропускної здатності і меншої затримки передачі даних. Час пробудження домінаторів визначається HQMAC, заснованим на навантаженні трафіку вузла датчика. Крім того, він також вказує на всі залишилися вузли датчика, що немає необхідності в тому, щоб регулювати свої інтервали часу пробудження, за винятком випадків домінаторів. Наступний алгоритм, Алгоритм 3, описує алгоритм планування HQMAC.

• Алгоритм 3. HQMAC.

• 1: // i : вузол датчика раковини, TD : трафік навантаження

• 2: для всіх V ∈G ( V , E )

• 3: якщо ( V == i ), то прокидатися = RI (4)

• 4: elseif ( V ∈NMISGrey || ConnectorRed)

• 5: прокидання = CI (1)

• 6: endif

• 7: endif

• 8: while ( V ∈ MISBlack)

• 9: якщо ( TD > TH2), то прокидатися = RI (4)

• 10: elseif (TH3 < TD ≤ TH2), потім прокидаються = RI (3)

• 11: elseif (TH4 < TD ≤ TH3), потім прокидаються = RI (2)

• 12: elseif ( TD <TH4), потім прокидатися = RI (1)

• 13: endif

• 14: endif

• 15: endif

• 16: endif

• 17: endwhile

• 18: endfor

Навантаження трафіку датчикового вузла відноситься до середньої кількості переданих пакетів даних протягом однієї одиниці часу. Під час кожного раунду вибору голови кластера буде оцінено навантаження на рух. Час затримки різко збільшується, коли час приходу пакета кожного датчика перевищує 300 кбіт / с. Отже, поріг транспортного навантаження (TH1) приймається рівним 300 кбіт / с. Оскільки домінуючими є вузли датчиків, які знаходяться на відстані від раковини, тільки вперед, і не є повноцінним завантаженням, час пробудження цих сірих сенсорних вузлів приймається як CI (1). Оскільки вузол датчика раковин сильно завантажується даними з його роз'ємів і сусідніх вузлів датчика, час пробудження цього вузла датчика приймається як RI (4), що є найбільшим інтервалом пробудження RI. Оскільки домінуючі вузли датчика передбачаються для пробудження в CI (1), то вузли датчика з'єднувача також встановлюються в тому ж самому стані пробудження, як і у доменних вузлів датчика, щоб отримати перетин з часовими інтервалами обох вузол датчика раковини і вузли датчика домінатора. Таким чином, вузли датчика домінатора є вузлами датчиків, які вирішують пересічні інтервали часу як домінуючих, так і роз'ємів. Вони або збільшують, або зменшують інтервали пересікання часу як доменних, так і з'єднувальних вузлів датчика. Хоча використовується вибір домінаторів на основі енергії, планування будильника домінатора переважно базується на навантаженні трафіку вузла датчика. Це призводить до мінімального виснаження енергії, що, у свою чергу, призводить до нечастої зміни домінаторів.

Оскільки RI (4) випливає 10 інтервалів часу пробудження з 16, Threshold2 (TH2) обчислюється як 300 × (10/16) = 187.5 kbps. Аналогічно, значення TH3 і TH4 обчислюються як 168,7 кбіт / с і 131,2 кбіт / с відповідно [18] . Тому, коли навантаження трафіку (TD) знаходиться між TH3 і TH2, RI (3) буде призначено як графік домінатора. Будь-який вузол датчика, що має TD більше, ніж TH2, буде присвоєно стану пробудження RI (4), і якщо TD менше, ніж TH4, то стан RI (1) пробудження буде підтримуватися вузлами датчика. Після того, як CDT побудовано, дані з домінанта передаються в інтервалах пробудження, що перетинаються, з домінаторами; пересилається через домінант; потім направляються в роз'єм; поки, нарешті, не досягне вузла датчика раковини. Рисунок 6 показує, що коли домінатор приймає RI (3), число пересічних часових інтервалів домінатора з доминирующим і домінатором з роз'ємом становить три; тобто нуль, чотири і вісім. Таким чином, HQMAC вказує, що тільки домінатори змінюють свої інтервали часу пробудження, в той час як всі інші вузли датчика повинні залишатися в попередньо визначених інтервалах часу пробудження, що значно зменшує накладні витрати. HQMAC завжди дозволяє домінантним вузлам датчиків перебувати в мінімальному стані пробудження CI (1) = {0, 4, 8, 12}. Під час інших станів сну функціональні умови низького енергоспоживання підтримуються вузлами датчиків для визначення середовища; згодом це не дозволяє їм виснажувати свою енергію. Домінатори приймають змінне стан пробудження на основі навантаження трафіку вузла датчика; таким чином, оптимальне виснаження енергії досягається, коли вузли датчиків займають як запропонований спосіб планування енергії, так і спосіб планування, що враховує трафік.

6.

Домінатор кількість точок зустрічі.