1HanyangHanyang Univ. CASP lab.Univ. CASP lab.

다운링크 라우팅 알고리즘Down link routing algorithm

Hanyang UniversityCASP LAB

02-2296-0390Http://casp.hanyang.ac.kr

2HanyangHanyang Univ. CASP lab.Univ. CASP lab.

목차

알고리즘

Message formatUp link 알고리즘

Down link 알고리즘

에러 상황 처리

3HanyangHanyang Univ. CASP lab.Univ. CASP lab.

주요특징

본 알고리즘의 핵심은 up link와 down link를 하나의 노드가 아닌 sink노드(down link)와 주변 노드(up link)로 분리하여 생각 하는 것이며 기본적인down link 알고리즘은 connected source routing 이다.

Sink node: 센서노드에 비해서 에너지와 메모리의 사용량이 거의 제한이 없다.up link되어 들어오는 토플로지 정보 저장 및 down link pass결정에유리함.

Sensor node:실제 필드에서 활동을 하므로 주변 상황에 따라서 up link 라우팅패스의 결정에 유리함.

4HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Message format

Up link message

Sensing data

Sequence number

Origine address

Source address

Parent address

Direction flag

Mac header

Down link message

Parent address3

Parent address2

Parent address1

Dest address

Origine address

Direction flag

Mac header

Up link message

Command or dataSequence number

Dest address

Origine address

Direction flag

Mac header

Direction flage

0= up link1=down link2=down link lock3=down link free5=peer to peer6=reply message

5HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Up link

Base

7

6

5

3

2

4

1

Node idsequence

costhop

Node idsequence

costhop

Node idsequence

costhop

Node idsequence

costhop

Node idsequence

costhop

Node idsequence

costhop Node id

sequencecosthop

Node idsequence

costhop

node5Node id

sequencecosthop

node7

Node4 table

6HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Up link

Base

1

5

432

6 987

parent

source

parent

source

parent

source

origine

Dest Source origine parent

3 4 4 3

2 3 4 2

1 2 4 1

base 1 4 base

7HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Down link Sequence 1

8HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Down link Sequence 2

parent

source

parent

source

parent

source

origine

source

Mac header Direction flage=1

Source message

Origineaddress

Parentaddress1

Parentaddress2

Parentaddress3

Dest address

Mac header Direction flage=2 base 1 2 3Dest address

12

Sequence 2

Direction flage

0= up link1=down link2=down link lock3=down link free5=peer to peer6=reply message

9HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Down link Sequence 3

Base

1

5

432

6 987

parent

source

parent

source

parent

source

origine

source

121110

Mac header Direction flage=2 base 5 10 11Dest address

12

Sequence 3

Mac header Direction flage=1

Source message

Origineaddress

Parentaddress1

Parentaddress2

Parentaddress3

Dest address

Direction flage

0= up link1=down link2=down link lock3=down link free5=peer to peer6=reply message

10HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Down link Sequence 4

11HanyangHanyang Univ. CASP lab.Univ. CASP lab.

Down link Sequence 5

Base

1

5

432

6 987

parent

source

parent

source

parent

source

origine

source

121110

Mac header Direction flage=5 base Command or dataDest address

12

Sequence 5

Direction flage0= forward1=inverse 2=inverse lock3=inverse free5=bidirection

Mac header Direction flage=1

Source message

Origineaddress

Parentaddress1

Parentaddress2

Parentaddress3

Dest address

12HanyangHanyang Univ. CASP lab.Univ. CASP lab.

0

1

3

6

2 4

95 8

parent : 8

Data

7

parent : 5

Data

parent : 2

Data

parent : 0

Data

Up Link

98

85

52

2sink

Dest Source origin parent

9 8

9 5

9 2

9 sink

13HanyangHanyang Univ. CASP lab.Univ. CASP lab.

0

13 6

2 4 7

5 8 9

Parent: 2Parent: 5

Parent: 5

Parent: 8Parent: 9

Parent: 8Parent: 9

Parent: 8Parent: 9 Parent: 9

address: 9

data address: 9

dataaddress: 9

data

address: 9

data

Down Link

14HanyangHanyang Univ. CASP lab.Univ. CASP lab.

에러상황처리

Down link connection error센서 네트워크의 토플로지는 센서 노드의 주변 상황에 따라서 변하기때문에 down link 시에 connection 에러

Peer to peer errorconnection 이후에 통신 할때 packet이 loss 되는 에러

해결방법센서 노드로 부터 up link되어오는 우회 경로와 reply message, sequence

message이용

15HanyangHanyang Univ. CASP lab.Univ. CASP lab.

MAC Performance Test

Motivation노드 간 무선 통신에 있어서 최악의 경우에 네트워크 성능 검증 요구

MAC protocolCSMA (Carrier Sense Multiple Access) 방식

네트워크 망이 현재 사용 중인지를 감지하고 만약 사용중이라면 일정시간을 기다렸다가 다시 전송을 시도하는 방식

CSMA 방식의 문제점

Node가 많아 질수록 delay, packet loss rate가 커짐

16HanyangHanyang Univ. CASP lab.Univ. CASP lab.

MAC Performance Test

1. Base node는 모든 node들에게 전송을 허용함으로써 각 node는 서로 경쟁함

2. 각 node들은 CSMA방식으로 서로 경쟁하다가 충돌이 일어남

collision

3. 충돌한 node는 일정시간을 기다렸다가 다시 전송 함

17HanyangHanyang Univ. CASP lab.Univ. CASP lab.

MAC Performance Test

0

5

10

15

20

25

30

2 4 6 8 10 12 14 16 18

node (EA)

Backoff

Tim

e(m

s

0

20

40

60

80

100

2 4 6 8 10 12 14 16 18

node (EA)

Loss o

f packet(

%

Back off Time Packet Loss Rate

900Mhz 대역

18HanyangHanyang Univ. CASP lab.Univ. CASP lab.

MAC Performance Test

Back off Time Packet Loss Rate

2.4Ghz 대역

0

5

10

15

20

25

30

2 3 4 5

node (EA)

Backo

ff T

ime(m

s

0

20

40

60

80

100

2 3 4 5

node (EA)

Lo

ss o

f p

acket(

%