Optymalizacja wielokryterialna rozmieszczania heterogenicznych WSN w 3D z użyciem ulepszonego algorytmu Genghis Khan shark

Inteligentniejsze czujniki w trójwymiarowym świecie

Od monitorowania koron drzew po zarządzanie inteligentnymi budynkami i zakładami przemysłowymi — bezprzewodowe sieci sensorowe stają się niewidomym układem nerwowym nowoczesnej infrastruktury. Jednak decyzja, gdzie umieścić setki czujników w złożonej przestrzeni trójwymiarowej — przy zachowaniu łączności i ograniczeń budżetowych — wcale nie jest trywialna. W artykule przedstawiono nowy algorytm, który pomaga inżynierom automatycznie projektować takie sieci tak, by obserwowały każdy zakątek, niezawodnie się komunikowały i nie marnowały środków.

Dlaczego rozmieszczanie czujników jest trudniejsze, niż się wydaje

W wielu rzeczywistych warunkach czujniki nie są rozłożone na płaskiej powierzchni. Montuje się je na sufitach i ścianach, wplata w maszyny lub zawiesza w powietrzu czy wodzie. Każdy typ czujnika ma inną odległość wykrywania i komunikacji oraz inną cenę. Lista życzeń projektantów jest prosta do sformułowania, ale trudna do spełnienia: każdy istotny punkt w objętości powinien być obserwowany przez kilka czujników (dla niezawodności), każdy czujnik musi móc przekazać dane do stacji bazowej przez łańcuch sąsiadów, a całkowity koszt powinien mieścić się w budżecie. Próba jednoczesnego spełnienia tych trzech celów zamienia projekt w labirynt sprzecznych wyborów, którego nie da się rozwiązać dokładnie dla dużych systemów.

Równoważenie obserwacji, komunikacji i wydatków

Autorzy opisują wyzwanie projektowe jako problem „wielokryterialny”: chcą jednocześnie maksymalizować pokrycie (ile czujników widzi każdy punkt docelowy), maksymalizować łączność (ile sąsiadów osiąga każdy czujnik) i minimalizować całkowity koszt. Modelują monitorowaną objętość jako zbiór możliwych miejsc instalacji czujników oraz punktów docelowych rozrzuconych w trzech wymiarach. Niektóre miejsca są droższe w instalacji, na przykład ze względu na trudny dostęp. Czujniki należą do kilku klas, z własnym promieniem detekcji, zasięgiem komunikacji i ceną. Kandidat projektu to wybór tak/nie, który typ czujnika, jeśli w ogóle, umieścić w danym miejscu. Projekt musi przestrzegać ścisłych reguł: każdy punkt docelowy musi być obserwowany przez co najmniej określoną liczbę czujników, a każdy zainstalowany czujnik musi mieć wystarczającą liczbę sąsiadów, by sieć była odporna.

Party poszukiwawcze inspirowane naturą

Aby zbadać ogromną przestrzeń możliwych projektów, artykuł opiera się na metodzie poszukiwania opartej na roju, inspirowanej zachowaniem drapieżnym, zwanej optymalizatorem Genghis Khan shark. Ulepszona wersja, EnMOGKSO, traktuje każdy możliwy projekt sieci jako osobnika w populacji przemieszczającej się po przestrzeni poszukiwań. Osobniki te najpierw szeroko wędrują, a potem stopniowo koncentrują się wokół obiecujących regionów, naśladując eksplorację i polowanie. Kluczowe jest to, że metoda utrzymuje dwa banki pamięci: jeden przechowuje najlepsze dotąd znalezione projekty, a drugi zachowuje nietypowe lub słabo zbadane rozwiązania. Ta podwójna pamięć pomaga uniknąć utknięcia przy jednej wąskiej rodzinie rozwiązań i zamiast tego dostarcza szerokiego wachlarza kompromisów między pokryciem, łącznością i kosztem.

Od gładkich liczb do konkretnych układów

Ponieważ rzeczywiste decyzje — zainstalować dany typ czujnika tutaj czy nie — są wyborami tak/nie, trudno je łagodnie korygować. EnMOGKSO omija ten problem, pracując najpierw z gładkimi wartościami liczbowymi „ocen”, które wyrażają, jak bardzo dany typ czujnika jest preferowany w konkretnym miejscu. Na każdym etapie oceny te oceny są przekształcane w rzeczywisty układ poprzez wybór co najwyżej jednego typu czujnika na lokalizację i ewentualne pozostawienie niektórych miejsc pustych. Powstały projekt jest następnie testowany: algorytm oblicza, ile czujników widzi każdy punkt docelowy, tworzy graf komunikacyjny pokazujący, które czujniki mogą się ze sobą komunikować, i sumuje koszty instalacji. Projekty łamiące reguły pokrycia lub łączności nie są odrzucane bezpośrednio; zamiast tego klasyfikuje się je według stopnia naruszenia, co pozwala wyszukiwaniu stopniowo piąć się w kierunku w pełni poprawnych rozwiązań.

Testowanie metody

Aby wykazać, że ich podejście nie jest dopasowane do jednego przykładu, autorzy najpierw oceniają EnMOGKSO na standardowym zestawie trudnych problemów matematycznych używanych do benchmarków algorytmów wielokryterialnych. Poprzez pomiar, jak blisko wyniki algorytmu odpowiadają idealnym krzywym kompromisu, odkrywają, że EnMOGKSO zwykle osiąga lepszy rozrzut i dokładność niż kilka dobrze znanych alternatyw, w tym popularne metody ewolucyjne i rojowe. Następnie przechodzą do realistycznych scenariuszy rozmieszczania czujników w trzech wymiarach. W wielu ustawieniach, które różnicują wymaganą redundancję pokrycia i rygor łączności, EnMOGKSO konsekwentnie znajduje projekty, które obejmują więcej punktów docelowych i utrzymują gęstsze połączenia komunikacyjne niż metody konkurencyjne, przy koszcie nieco wyższym, lecz stosunkowo stabilnym.

Co to oznacza dla rzeczywistych sieci sensorowych

Dla praktyków kluczowym wynikiem nie jest pojedynczy „najlepszy” układ, lecz zbiór wysokiej jakości opcji ujawniających kompromis między wydajnością a wydatkami. Nowy algorytm ma tendencję do bardziej kompletnego wypełniania tej powierzchni kompromisów, co ułatwia inżynierom wybór projektu odpowiadającego ich tolerancji ryzyka i budżetowi. Praca sugeruje, że starannie zaprojektowane metody rojowe, które uwzględniają zarówno fizykę wykrywania, jak i logikę połączeń sieciowych, mogą przekształcić inaczej nierozwiązywalną łamigłówkę projektową w wykonalne ćwiczenie planistyczne dla zadań monitoringu trójwymiarowego w budynkach, fabrykach i środowisku.

Cytowanie: Houssein, E.H., Ibrahim, I.E., Wazery, Y.M. et al. Multi-objective optimization for 3D heterogeneous WSN deployment using an enhanced Genghis Khan shark algorithm. Sci Rep 16, 12075 (2026). https://doi.org/10.1038/s41598-026-45399-z

Słowa kluczowe: bezprzewodowe sieci sensorowe, rozmieszczenie 3D, optymalizacja wielokryterialna, inteligencja rojowa, pokrycie i łączność sieci