Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$28,000.00

Theoretical aspects and algorithms for architectural design and communication in current networks

FY 2016-17

Summary
The mathematical structure inherent in problems originated in design and administration of sensor networks has made them central to the theoretical computer science community as they utilize different techniques from areas like graph theory, computational geometry, design theory, and algebraic combinatorics. My goal is to build on my expertise and to answer some of the emerging questions in the area of ad-hoc and sensor networks: I propose to study and better understand the potential of geometric information in computation. The classical theory of graph algorithms was developed for offline models and is not sufficient for many modern applications where we are dealing with huge networks and we have only access to some local part of it at a time. It is more and more apparent that geometric information is useful to handle these settings.High connectivity is a fundamental criteria on communication network and it has been attacked in several research works where a planar subgraph of UDG with higher connectivity was build by adding/deleting edges to/from planar graph/UDG. However, existing results do not give complete understanding of tradeoffs here. Central question, which I would like to attack, is whether for some class of UDGs a similar technique as Gabriel Test or Relative Neighborhood Graph can result in a planar subgraph with higher (2-4) connectivity (vertex or edge). Today we know that for higher than 1-connectivity this cannot be the whole class of UDGs without extra conditions, and perhaps some topological requirements are necessary.Directional antennae are widely being used in wireless networks not only for reducing energy consumption and interference, but also for improving routing efficiency and security. The tradeoffs are studied between number of antennae and transmission range necessary to establish connected network. Existing results only partially address the issue of stretch factor. Also the effect of various technology limiting requirements such as allowed number of antennae at each node or allowed total number of antennae have to be better understood. I plan to attack some of these problems.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
261542-2012
Name nom
Stacho, Ladislav
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
28000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
5
Nb partie
5
Application title
Theoretical aspects and algorithms for architectural design and communication in current networks
Keyword
NSERC
Application summary
The mathematical structure inherent in problems originated in design and administration of sensor networks has made them central to the theoretical computer science community as they utilize different techniques from areas like graph theory, computational geometry, design theory, and algebraic combinatorics. My goal is to build on my expertise and to answer some of the emerging questions in the area of ad-hoc and sensor networks: I propose to study and better understand the potential of geometric information in computation. The classical theory of graph algorithms was developed for offline models and is not sufficient for many modern applications where we are dealing with huge networks and we have only access to some local part of it at a time. It is more and more apparent that geometric information is useful to handle these settings.High connectivity is a fundamental criteria on communication network and it has been attacked in several research works where a planar subgraph of UDG with higher connectivity was build by adding/deleting edges to/from planar graph/UDG. However, existing results do not give complete understanding of tradeoffs here. Central question, which I would like to attack, is whether for some class of UDGs a similar technique as Gabriel Test or Relative Neighborhood Graph can result in a planar subgraph with higher (2-4) connectivity (vertex or edge). Today we know that for higher than 1-connectivity this cannot be the whole class of UDGs without extra conditions, and perhaps some topological requirements are necessary.Directional antennae are widely being used in wireless networks not only for reducing energy consumption and interference, but also for improving routing efficiency and security. The tradeoffs are studied between number of antennae and transmission range necessary to establish connected network. Existing results only partially address the issue of stretch factor. Also the effect of various technology limiting requirements such as allowed number of antennae at each node or allowed total number of antennae have to be better understood. I plan to attack some of these problems.