PDF

Otsikkokuva

Matkapuhelinverkon solujen geometria

Robert Piché
Professori
Matematiikan laitos, Tampereen teknillinen yliopisto

Tukiasemien solut

Kun soitat matkapuhelimella bussista, puhelusi välittyy verkkoon lähimmän tukiaseman kautta (kuva 1). Vaikka bussi kulkee ja vie sinut kauas siitä ensimmäisestä tukiasemasta, puhelu ei katkea, koska järjestelmä siirtää sen käsittelyn tukiasemasta toiseen. Tukiaseman ''hoitoaluetta'' kutsutaan soluksi; matkapuhelin onkin englanniksi cellular phone. Tässä artikkelissa tutkitaan tukiasemien solujen geometriaa.


Kuva 1: Minkä muotoinen on tämän tukiaseman solu?

Aloitetaan sillä, että asemat ovat $n$ eri pistettä tasossa. Määritellään jokaisen aseman $p_i\;(i=1,2,\ldots,n)$ ympärille sellainen alue, että alueen jokaisen pisteen lähin asema on $p_i$. Aseman $p_i$ aluetta kutsutaan soluksi ja merkitään $V(p_i)$. Jos kahden paikan välistä etäisyyttä merkitään $d(p,q)$:lla, niin solu on pistejoukko

\begin{displaymath} V(p_i)=\{q \;\vert\; d(q,p_i)<d(q,p_j), 1\leq j\leq n, i\neq j\}. \end{displaymath}

Solujen reunalla ollaan yhtä lähellä kahta tai useampaa asemaa. Nämä raja-alueet eivät kuulu mihinkään soluun. Solujen kokoelmaa kutsutaan solukaavioksi.

Miltä näyttää solu? Tarkastellaan ensin kahden aseman tapausta.


Kuva 2: Kahden aseman solukaavio

Solut $V(p_1)$ ja $V(p_2)$ ovat silloin puolitasoja (kuva 2). Solujen yhteinen raja on suora, joka puolittaa asemat yhdistävän janan (katkoviiva kuvassa 2). Jokaisen suoran pisteen etäisyys asemaan $p_1$ on sama kuin sen etäisyys asemaan $p_2$.

Jos merkitään symbolilla $h(p_1,p_2)$ asemalle $p_1$ kuuluvaa puolitasoa aseman $p_2$ suhteen, eli

\begin{displaymath} h(p_1,p_2)=\{q \;\vert\; d(q,p_1)<d(q,p_2)\}, \end{displaymath}

niin kahden aseman tapauksessa voidaan todeta, että $V(p_1)=h(p_1,p_2)$ ja $V(p_2)=h(p_2,p_1)$.

Lisätään kolmas asema. Silloin huomataan, että solu $V(p_1)$ (kuva 3)


Kuva 3: Aseman $p_1$ solu, kun tasossa on kolme asemaa, on kahden puolitason leikkaus.

on leikkaus kahdesta asemalle $p_1$ kuuluvasta puolitasosta: sen puolitasosta aseman $p_2$ suhteen sekä puolitasosta aseman $p_3$ suhteen. Kaava on siis

\begin{displaymath} V(p_1)=h(p_1,p_2)\cap h(p_1,p_3). \end{displaymath} (1)

Kahden puolitason leikkaus on suorien rajaama alue, eli monikulmio. Puolitasot ovat kuperia alueita, joten niiden leikkaus on kupera. Kun muodostamme vastaavalla tavalla solut $V(p_2)$ ja $V(p_3)$, saadaan kaavio, jonka muodostaa kolme kuperaa monikulmiota (kuva 4).


Kuva 4: Kolmen aseman solukaavio

Reunat ovat tässä tapauksessa kaikki puolisuoria.

Kun lisätään asemia, voimme todeta, että solu $V(p_1)$ on leikkaus kaikista puolitasoista, joita se hallitsee muiden asemien suhteen. Näin kaavasta ([*]) tulee

\begin{eqnarray*} \nonumber V(p_1)&=&h(p_1,p_2)\cap h(p_1,p_3)\cap \cdots\cap h(p_1,p_n)\\ &=& \bigcap\{h(p_1,p_j) \vert 2\leq j \leq n\}. \end{eqnarray*}



Muut solut muodostetaan samalla tavalla, eli puolitasojen leikkauksena:

\begin{displaymath} V(p_i)=\bigcap\{h(p_i,p_j) \vert 1\leq j \leq n, j\neq i\}, \quad 1\leq i \leq n. \end{displaymath}

Tästä kaavasta seuraa, että solut ovat kaikki kuperia monikulmioita.

Koska puolitasojen lukumäärä on $n-1$, niin monikulmion särmien ja kärkien lukumäärä on korkeintaan $n-1$. Tämä maksimiarvo saavutetaan solussa, jonka asema on muiden asemien piirittämä (kuva 5).


Kuva 5: Kuuden aseman solukaavio.

Jos asemat ovat suorassa rivissä, niin solukaavion särmät ovat yhdensuuntaisia suoria (kuva 6).


Kuva 6: Rivissa olevien asemien solukaavio.

Tämä on erikoistapaus. Jos asemat eivät ole rivissä, niin solukaavion särmät ovat janoja tai puolisuoria, eikä kaaviossa ole yhtäkään (täys-)suoraa. Tämä väite voidaan todistaa seuraavasti. Olkoon suora $e$ solujen $V(p_i)$ ja $V(p_j)$ yhteinen reunaviiva. Koska suoran $e$ pisteet ovat solun $V(p_j)$ reunalla, niin ei ole olemassa muuta asemaa, joka olisi niitä lähempänä. Oletetaan nyt, että on olemassa sellainen asema $p_k$, että asemat $p_i, p_j, p_k$ eivät ole rivissä. Tällöin puolitason $h(p_k,p_j)$ reunaviiva ei ole yhdensuuntainen suoran $e$ kanssa, joten se leikkaa $e$:n (kuva 7).


Kuva 7: Todistuksen geometria.

Ne suoran $e$ pisteet, jotka ovat puolitason $h(p_k,p_j)$ sisällä, ovat lähempänä asemaa $p_k$ kuin asemaa $p_j$. Tämä on ristiriidassa sen kanssa, että $e$ on suora, ja todistus päättyy tähän.

Tason pisteille $q$, jotka eivät ole asemia, voidaan määritellä suurin tyhjä ympyrä, joka on suurin $q$-keskinen ympyrä, joka ei sisällä asemaa. Suurimman tyhjän ympyrän avulla voidaan luokitella tason pisteet:

ei asemassa oleva piste on ... jos ja vain jos sen suurimman tyhjän ympyrän reunalla on ...
solun sisällä yksi asema
särmässä kaksi asemaa
kärjessä kolme tai useampi asemaa (kuva 8).
Neljän tai useamman aseman läpi kulkevä ympyrä vaatii asemien erikoista asettelua. Siksi solukaavion kärjessä on melkein aina kolme särmää.


Kuva 8: Kärjen suurin tyhjä ympyrä.

Pohdittavaa

Solu voidaan myös määritellä vastaanotettujen signaalien mukaan. Matkapuhelimen tietoliikenteen hoitaisi se tukiasema, jonka signaali on voimakkain. Jos asemilla on eri lähetysteho ja signaalin voimakkuus vähenee etäisyyden neliön mukaan, niin minkä näköisiä ovat solut?

Viitteet

1
A. Okabe et al., Spatial Tesselations: Concepts and Applications of Voronoi Diagrams, 2nd edition, Wiley, 2000.

2
J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1994.

3