Wiskunde maakt ontwerp draadloze netwerken veel efficiënter

Hoeveel GSM-masten moeten er minimaal geplaatst worden om iedereen bereik te geven? Als er tien extra bassisstations gefinancierd kunnen worden, waar kunnen die dan het beste geplaatst worden? Promovendus Erik Jan van Leeuwen van het Centrum Wiskunde & Informatica (CWI) in Amsterdam beschreef deze problemen met meetkundige rekenmodellen.

Publication date: 15-06-2009

Hoeveel GSM-masten moeten er minimaal geplaatst worden om iedereen bereik te geven? Als er tien extra bassisstations gefinancierd kunnen worden, waar kunnen die dan het beste geplaatst worden? Promovendus Erik Jan van Leeuwen van het Centrum Wiskunde & Informatica (CWI) in Amsterdam beschreef deze problemen met meetkundige rekenmodellen.

Met de technieken die hij ontwikkelde is het mogelijk om veel efficiënter de best mogelijke oplossingen te vinden: soms tienduizenden keren zo snel als eerdere methodes. In 2008 ontving hij hiervoor de Philips Wiskunde Prijs voor promovendi. Op 16 juni promoveert hij aan de Universiteit van Amsterdam op zijn proefschrift 'Optimization and Approximation on Systems of Geometric Objects'.

Veel praktische problemen hebben een meetkundige component. "Niet alleen de plaatsing van GSM-masten of het bouwen van een 'backbone' in sensornetwerken, maar bijvoorbeeld ook het plaatsen van plaatsnamen op een landkaart zonder dat de namen overlappen valt onder deze categorie," aldus Van Leeuwen. "Met de computer kunnen de optimale oplossingen niet snel exact berekend worden." De problemen die de wiskundige onderzocht behoren namelijk tot de zeer ingewikkelde NP-moeilijke problemen, waar onder  andere het bekende handelsreizigersprobleem toe gerekend wordt. "Het  lastige is dat het aantal mogelijke oplossingen dat onderzocht moet worden explosief groeit met bijvoorbeeld het aantal zendmasten", zegt van Leeuwen.

De onderzoeker liet echter zien dat computers wel snel oplossingen kunnen  vinden die bijna optimaal zijn. Hiervoor gebruikte hij onder andere  shifting-technieken. Daarmee leverde hij significante verbeteringen op eerdere resultaten. Zijn methode staat een zeer kleine foutmarge toe die instelbaar is. Daarbij is de benodigde rekentijd tienduizenden keren korter dan bij eerdere methoden. In enkele gevallen kon zelfs worden aangetoond dat geen snellere methode bestaat om binnen deze foutmarges te komen. Het onderzoek is gefinancierd door het Bsik-programma BRICKS.