Sisäpaikannusjärjestelmän tukiasemien sijaintien optimointi geneettisellä algoritmilla

Abstract

Sisäpaikannusjärjestelmä on tekninen ratkaisu, jonka avulla voidaan paikantaa ihmisiä, esineitä tai laitteita rakennusten sisällä. Sisäpaikannus perustuu rakennukseen asennettujen tukiasemien ja kohteiden mukana liikkuvien paikantimien väliseen signaaliliikenteeseen. Sisäpaikannusjärjestelmien yleistyessä sisäpaikannuksen suunnittelun automatisointi, erityisesti tukiasemien sijoittelun osalta, on noussut merkittäväksi ja ajankohtaiseksi tutkimuskohteeksi. Tukiasemien optimaalisella sijoittelulla vaikutetaan merkittävästi sisäpaikannusjärjestelmän paikannustarkkuuteen ja kustannuksiin.

Tässä tutkimuksessa kehitettiin geneettinen algoritmi tukiasemien sijoittelun optimointiin rakennuksen pohjapiirrokseen. Algoritmin toteutuksessa vertailtiin eri valinta-, risteytys- ja mutaatiomenetelmien yhdistelmiä. Tukiasemien sijoitteluratkaisujen arviointi perustui yksinkertaisiin rajoitteisiin pohjautuvaan kustannusfunktioon. Geneettisellä algoritmilla pyrittiin löytämään kustannusfunktion globaalia minimiarvoa lähestyvä sijoitteluratkaisu.

Tulokset osoittavat, että kehitetty algoritmi kykeni tehokkaasti ja johdonmukaisesti tuottamaan sijoitteluratkaisuja, jotka lähestyvät kustannusfunktion globaalia minimiä. Erityisesti elitismiä, kaksipisteristeytystä ja ei-tasajakoista mutaatiota hyödyntävä geneettinen algoritmi tuotti manuaaliseen sijoitteluun verrattuna kilpailukykyisiä tuloksia. Kehitetty algoritmi löysi luotettavasti satunnaisesta alkupopulaatiosta huolimatta lähellä globaalia minimiä olevan ratkaisun keskimäärin kuudessa minuutissa. Geneettinen algoritmi todettiin tehokkaaksi ja joustavaksi menetelmäksi tukiasemien sijoittelun optimointiin. Kehitetyn algoritmin kyky tutkia ratkaisuavaruutta kattavasti luo vahvan pohjan jatkokehitykselle ja laajemmalle soveltamiselle.

An indoor positioning system is a technical solution for locating people, objects, or devices within buildings. It relies on signal exchanges between stationary base stations and positioning units carried by the targets. As these systems become more common, automating the design process, especially base station placement, has become a timely research focus. Optimal base station placement significantly affects both positioning accuracy and system cost.

This study developed a genetic algorithm to optimize base station placement using a building floor plan. Different combinations of selection, crossover, and mutation methods were compared. Placement solutions were evaluated using a cost function based on simple constraints. The goal of the algorithm was to find a placement solution that approaches the global minimum of this cost function.

Results show that the algorithm consistently and efficiently produced solutions near the global minimum. In particular, the version using elitism, two-point crossover, and non-uniform mutation produced competitive results when compared to manual placement. Despite starting from a random initial population, the algorithm reliably found near-optimal solutions in an average of six minutes. Overall, the genetic algorithm proved to be an effective and flexible method for optimizing base station placement. Its ability to thoroughly explore the solution space provides a strong foundation for further development and broader application.