Schneller gefunden im Ernstfall: Neue Algorithmen optimieren die Positionierung der Sensoren in Ortungssystemen

Für die Ortung von Personen in Innenräumen setzen viele Systeme auf Bluetooth-Low-Energy-Beacons (BLE), kleine Funksender, die es mobilen Geräten erlauben, ihre Position zu bestimmen, ohne dass Kameras oder eine dauerhafte persönliche Überwachung nötig sind. Damit die Ortung per Trilateration funktioniert, muss jeder Punkt im Gebäude gleichzeitig von mindestens drei Beacons erfasst werden. Zu wenige Beacons bedeuten Ortungslücken, zu viele treiben Anschaffungs- und Wartungskosten unnötig in die Höhe. Bislang wird diese Platzierung meist von Hand vorgenommen – ein aufwendiger, fehleranfälliger Prozess, der weder vollständige Abdeckung noch eine kosteneffiziente Lösung garantieren kann.

Die Lösung: Drei Methoden im Zusammenspiel

Das Team um Sven Löffler, Viktoria Abbenhaus, George Assaf und Petra Hofstedt von der Brandenburgischen Technischen Universität Cottbus-Senftenberg (BTU) löst dieses Problem algorithmisch. In dem nun in der Fachzeitschrift SN Computer Science (Springer Nature) veröffentlichten Forschungsartikel kombinieren die Wissenschaftler drei unterschiedliche Optimierungsansätze:

• Constraint Programming (CP): ein deklarativer Ansatz, der mathematisch exakte, global optimale Lösungen berechnen kann – allerdings mit hohem Rechenaufwand.
• Large Neighborhood Search (LNS): eine Metaheuristik, die bestehende Lösungen gezielt "zerstört" und wieder "repariert", um sie Schritt für Schritt zu verbessern.
• Evolutionäre Algorithmen (EA): ein an die biologische Evolution angelehntes Verfahren, das mit einer Population von Lösungsvorschlägen arbeitet und diese durch Rekombination und Mutation weiterentwickelt.

Die zentrale Neuerung der aktuellen Arbeit liegt in der Realisierung der Anwendbarkeit und der Weiterentwicklung dieser Methoden für dreidimensionale Gebäudemodelle mit mehreren Stockwerken. Das Team hat die Berechnung der von einem Beacon abgedeckten Fläche erheblich beschleunigt, die einzelnen Verfahren feiner parametrisiert und mehrere Hybridstrategien entwickelt, die die Stärken der drei Methoden kombinieren.

Die Ergebnisse: Weniger Beacons, höhere Erfolgsquote

Anhand von 29 synthetisch generierten, dreistöckigen Gebäudemodellen mit unterschiedlichen Wandmaterialien und -stärken hat das Team die verschiedenen Verfahren systematisch verglichen. Das Ergebnis: Während frühere Ansätze teils nur für rund ein Viertel bis knapp drei Viertel der Testgebäude überhaupt eine gültige Lösung fanden, liefern die neuen Methoden für alle getesteten Gebäude eine funktionierende Beacon-Platzierung. Gleichzeitig kommt das beste der neu entwickelten Verfahren – eine Kombination aus stockwerksweiser Constraint-Optimierung und Reparaturstrategie – im Schnitt mit deutlich weniger Beacons aus als der ursprüngliche, rein constraint-basierte Ansatz, der teils über 800 Beacons pro Gebäude benötigte.

Bemerkenswert ist zudem, dass die algorithmischen Verbesserungen einen größeren Effekt hatten als der Umstieg auf leistungsfähigere Computer-Hardware. Für die Praxis bedeutet das: Klügere Verfahren bringen mehr als reine Rechenleistung.

Praxisrelevanz: Von der Pflegeeinrichtung bis zur Industriehalle

Getestet wurde das Verfahren unter anderem an den realen Grundrissen eines dreistöckigen BTU-Gebäudes in Cottbus. Die Ergebnisse zeigen, dass sich die Methode auch auf reale, architektonisch komplexe Bauwerke übertragen lässt. Für Betreiber von Pflegeeinrichtungen, Industrieanlagen oder großen Verwaltungsgebäuden eröffnet das die Möglichkeit, Indoor-Ortungssysteme künftig automatisiert, kosteneffizient und mit belastbaren Abdeckungsgarantien zu planen – ein Beitrag zu mehr Sicherheit, etwa bei der schnellen Lokalisierung hilfsbedürftiger Personen im Notfall.

Über die Publikation

Der Fachartikel Advanced Algorithms for the Three-Dimensional Beacon Placement Problem Based on Constraint Programming, Large Neighborhood Search, and Evolutionary Methods" von Sven Löffler, Viktoria Abbenhaus, George Assaf und Petra Hofstedt (Fachgebiet Programmiersprachen und Compilerbau, MINT, BTU Cottbus–Senftenberg) ist am 8. August 2026 als Open-Access-Beitrag in der Zeitschrift SN Computer Science (Springer Nature) erschienen und für jedermann frei zugänglich.