Routing (Sun SPOT)

Fra DAMNWiki
Version fra 24. apr. 2008, 12:45 af David (diskussion | bidrag) David (diskussion | bidrag) (→‎Algoritmevalg)
(forskel) ←Ældre version | Nuværende version (forskel) | Nyere version → (forskel)
Spring til navigationSpring til søgning

Denne artikel omhandler overvejelser, design og implementeringer omkring Sensor Network Protocol routing'en skal foregå.

Den generelle protokol kan findes under Programdesign (Sun SPOT) og under Implementering (Sun SPOT) er der mere konkret om den egentlige implementering af det hele.

Mål

At forbinde alle sensorer i et sensor netværk, således at kommunikationsafstand bliver mindst mulig mellem sensorerne.

Metode

Sensor netværket opbygges som en vægtet, ikke-orienteret og cyklisk graf, hvor hver enkelt sensor er en node, og kanterne i grafen er kommunikationsforbindelsen imellem dem. Vægtningen er repræsenteret ved radiostyrken af forbindelsen mellem de enkelte sensorer.

Der skal på baggrund af grafen konstrueres et kommunikationstræ for sensornetværket. Der skal lægges vægt på:

  • Pålidelighed:
    Pålidelighed opbygges ved primært at vælge kanter, som har en lav vægt og dermed høj radiostyrke. Dette øger sandsynligheden for, at pakker ikke går tabt undervejs.
  • Afstand:
    Der skal foretages færrest mulige kommunikationshop mellem sensorerne i sensornetværket og basisstationen.

Algoritmevalg

Vi vil benytte en korteste sti algoritme til at opbygge et kommunikationtræ for sensornetværket. Der er her flere muligheder:

  • Breddeførstsøgning:
    Fordele:
    • Nem at implementere og forstå
    • Komplethed
    Ulemper:
    • Ikke optimal til vægtede grafer
  • Dijkstras algoritme
    Fordele:
    • God til rutebestemmelse
    • Er som udgangspunkt designet til vægtede grafer
    Ulemper:
    • Større maksimal køretid end breddeførst

Sensornetværket, som vi beskæftiger os med, er ikke specielt stort. Der vil højst være tale om 100 sensorer, og det er derfor overflødigt at implementere en alt for avanceret algoritme, da grafen ikke er så stor.

Algoritme valg er ikke endeligt afgjort, men valget falder nok på Dijkstras algoritme.