Моделі та алгоритми маршрутизації інформаційних потоків в самоорганізованих мережах - Пиріг, Юлія Володимирівна (Національний університет "Львівська політехніка", 2018)
Дисертація присвячена удосконаленню методів маршрутизації інформаційних потоків у безпровідних самоорганізованих мережах шляхом покращення часових параметрів маршрутизації та передавання інформації в умовах різкого зростання динаміки потоків та нестабільності рівня шумів у радіоканалах. Встановлено, що важливим завданням при передаванні даних по безпровідних сенсорних мережах залишається забезпечення ефективності маршрутизації, яка безпосередньо впливає на збалансованість та рівномірність використання ресурсів радіоканалу, а також сумісне використання ліцензованих частотних смуг без впливу на процеси передавання користувачів. Для розв’язання окреслених завдань у роботі вперше запропоновано комплексний метод маршрутизації на основі знаходження глобального екстремуму функції впорядкованого випадкового пошуку з додаванням/видаленням вузла для утворення множини маршрутів та їх послідовного упорядкування за критерієм максимізації рівня QoS з урахуванням неоднорідностей у мережі. Удосконалено метод локалізації вузлів сенсорної мережі на основі алгоритмічного підходу Терстона з використанням діаграми потужності Вороного, що дало змогу підвищити точність визначення віртуальних координат при застосуванні диску Пуанкаре. Удосконалено метод кластеризації множини сенсорних вузлів для зменшення тривалості пошуку маршруту між довільною їх парою на основі визначення центроїда кластера із урахуванням моделі поширення сигналу в радіоканалі. Набула подальшого розвитку модель зони перекриття кластерів у самоорганізованих мережах, яка дала змогу застосувати схему перепризначення логічних адрес мережним вузлам, що функціонують у цих кластерах, і забезпечувати необхідний рівень якості обслуговування у разі програмних чи апаратних збоїв. Доведено ефективність запропонованих в роботі рішень з використанням розроблених математичних і імітаційних моделей. Диссертация посвящена усовершенствованию методов маршрутизации информационных потоков в беспроводных самоорганизующихся сетях путем улучшения временных параметров маршрутизации и передачи информации в условиях резкого роста динамики потоков и нестабильности уровня шумов в радиоканалах. Показано, что важной задачей при передаче данных по беспроводным сенсорным сетям остается обеспечение эффективности маршрутизации, которая непосредственно влияет на сбалансированность и равномерность использования ресурсов радиоканала, а также совместное использование лицензированных частотных полос без влияния на процессы передачи пользователей. Для решения определенных задач в работе впервые предложен комплексный метод маршрутизации на основе нахождения глобального экстремума путем упорядоченного случайного поиска с добавлением / удалением узла для образования множества маршрутов и их последовательного упорядочения по критерию максимизации уровня QoS с учетом неоднородностей в сети. Усовершенствован метод локализации узлов сенсорной сети на основе алгоритмического подхода Терстона с использованием диаграммы мощности Вороного, что позволило повысить точность определения виртуальных координат при применении модели диска Пуанкаре. Усовершенствован метод кластеризации множества сенсорных узлов для уменьшения продолжительности поиска маршрута между произвольной их парой на основе определения центроида кластера с учетом модели распространения сигнала в радиоканале. Получила дальнейшее развитие модель зоны перекрытия кластеров в самоорганизующихся сетях, которая позволила применить схему переназначения логических адресов сетевым узлам, функционирующим в этих кластерах, и обеспечивать необходимый уровень качества обслуживания в случае программных или аппаратных сбоев. Доказана эффективность предложенных в работе решений с использованием разработанных математических и имитационных моделей. The thesis is devoted to solving the actual scientific task of the data flows routing methods enhancement in self-organized networks by improvement of the data transmission latency in conditions of the dynamic traffic intensity and noise fluctuations in modern wireless sensor networks in order to satisfy user requirements in real-time applications. The principles and features of the wireless self-organizing networks design have been analysed to determine the key tasks, which should be solved to improve the balance and fairness of radio resource utilization such as improvement of the routing efficiency and spectrum sharing in licensed bands without jeopardizing the user experience. In order to solve the given tasks this thesis propose new complex routing method based on the global extremum determination for the function of sorted random search by adding/removing of the nodes. Proposed method allows creating and arranging of the set of routes by using the QoS maximization and taking into account the network heterogeneity. The nodes localization method has been improved based on the Thurston's algorithm using the Voronoi power diagram with correct adjacent connections, which allows to increase the precision of virtual coordinates by using canonical unit Poincare disk to improve the quality of routing in Euclidian space. The clustering method of sensor nodes has been improved by the determination of centroid taking into account the wireless channel propagation model to reduce the time for route searching between the arbitrary pair of nodes. The model of clusters overlapping in self-organized wireless networks has been further developed by using the logical nodes addresses reassignment within the given cluster to ensure the target QoS level in case of hardware or software failures. The simulations have been conducted based on the developed analytical and empirical models in conditions of noise fluctuations in wireless channels to prove the efficiency of the proposed solutions. Simulation results show that by using the proposed complex routing method we can ensure the high reliability of the wireless sensor network and maintain the required QoS level for end users. Simulations on the efficiency of proposed clustering method show that bit error rate has been reduced by 7% comparing to existing solutions. Simulations of the transmission time between source node and destination node using the shortest path selection by the proposed complex routing method show that the transmission latency has been reduced two times comparing to conventional routing methods for the same configuration of the wireless sensor network.
Модели и алгоритмы маршрутизации информационных потоков в самоорганизующихся сетях
Models and algorithms for data flows routing in self-organized networks
Keywords: самоорганізовані мережі; якість обслуговування; маршрутизація; кластеризація; самоорганизующиеся сети; качество обслуживания; маршрутизация; кластеризация; self-organized networks; quality of service; routing; clustering; 621.391