Centrum Wiskunde & Informatica Amsterdam
PERSBERICHT
15 juni 2009 / 09
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. 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.
--
Centrum voor Wiskunde en Informatica