wireless ad hoc network - 3 (OLSR,GPSR)

proactive방식

초기 딜레이가 적다는 장점이 있지만 컨트롤 트래픽이 많이 발생할수 있다는 단점

distance vector방식을 사용하는 DSDV에서는 어떤 한 노드가 라우팅 계산을 잘못하는경우 네트워크 전체적으로 영향을 미칠수 있다.

Link state프로토콜은 상대적으로 한 노드의 잘못된 계산에 의한 영향이 적다.

Link state알고리즘은 한 노드가 네트워크를 구성하는 다른 모든 노드에게 라우팅 정보를 전송한다. 각각의 노드들은 네트워크의 모든 노드들까지의 루트 경로를 가지고 있다.

네트워크에 N개의 노드가 있을때,

어떤 한 노드가 다른 모든 노드들에게 자신의 링크 정보를 전송 해야 하므로 N회의 전송 횟수가 필요하며

네트워크에 N개의 노드가 존재하므로 N제곱만큼의 전송 횟수가 Link State 프로토콜에서 라우팅 정보를 교환하기 위해서 필요한 횟수이다.

상태 한번 업데이트 하는데, N^2만큼의 라우팅 테이블을 전송해야 한다.

flooding -> 특정 정보를 단 한번만 모든 노드가 re-broadcast하는것

어떤 노드가 자신이 엣지에 있다고 판단하면 그 노드는 재 브로드캐스팅 하지 않을수 있는데, 그걸 알기가 쉽지 않다.

그래서 N^2만큼의 전송 횟수는 피할수 없다. 이것은 상당히 큰 오버헤드이다.

위의 그림은 각 노드가 flooding에 의해서 중복해서 같은 데이터를 수신한다는것을 의미하는 그림이다.

각 노드가 받는 동일한 패킷의 개수는 이웃 노드의 개수와 동일하다.

위의 프로토콜은 유선에서 사용되는 Link state 알고리즘인 OSPF 프로토콜이다.

ad - hock network 에서는 특정 노드까지 가는 경로가 굉장히 다양하다. 

무선 환경에서 중복된 패킷을 수신하는것을 막기 위해서 OSPF를 개선한것이 OLSR이다.

재전송 횟수를 줄이고, advertisement하는 link state의 양도 줄어들게끔 하는 2가지 목적을 가지고 있다.

link state는 d.v에 비해 안정적인 프로토콜이다. 또한 proactive하다는 장점이 있다.

중앙 컨트롤 노드가 따로 있는게 아니라 각 노드가 알아서 라우팅 테이블을 계산 하는것이, ad hoc network routing protocol들의 장점이다.

위의 그림에서 파란색인 노드가 MPR SET이라고 한다. (Multipoint Relay)

1개의 노드를 거쳐가야 도달할수 있는것을 1 hop neighbours라고 한다.

위의 그림에서 MPR만이 retransmission하게 하면 11회의 재전송만 하면 된다.

distance vector의 경우에는 전체 네트워크에 대한 경로를 각 노드들이 분산적으로 계산해서 완성 되지만,

link state의 경우에는 전체 네트워크에 대한 경로를 각 노드들이 알아서 계산한다.

MPR - 원홉 네이버의 일부 이며, 모든 투홉네이버들을 커버하는 노드의 집합이다.

MPR SELECTOR -> 자신을 MPR로 지정한 노드

위의 그림에서 주황색 노드들의 MPR 셀렉터는 s이다.

mpr지정하는 방법 - 원홉 네이버들 중에서 가장 많은 투홉네이버를 커버하는 원홉 네이버를 mpr로 선택함.

그 mpr에 의해 지정된 투홉네이버를 제외한 다른 투홉 네이버들 중에서 또다시 위의 과정을 반복해서 또다른 mpr을 선택한다.

위의 그림에서 B의 원홉 네이버들은 A,C,G인데 C와 F가 가장 많은 투홉네이버를 커버하므로 C를 mpr로 선택하게 하면 모든 투홉네이버가 커버 되므로 mpr을 선택하는 알고리즘이 종료되고 최종적으로 C만 mpr로 지정되게 된다. 

mpr select 알고리즘을 돌리기 위해서는 원홉네이버 뿐만 아니라 투홉네이버에 대한 정보까지 알아야 한다.

그걸 위해서 노드들이 헬로 메세지를 주기적으로 주고 받는다.(자기가 존재한다는것을 알리는 역할)

헬로 메세지 수신을 통해서 알게된 네이버들을 다음 헬로메시지에 집어넣는다. 이렇게 하다보면 노드들은 완전한 네이버 리스트들을 가지고 있을 것이다.

D와 E로부터 헬로 메세지를 받은 C는 그 정보들을 다시 헬로 패킷에 담아서 B에게 전송하게 되면 B는 투홉네이버까지의 정보들을 가지고 있다.

Topology Control Message(TC)

노드의 링크 정보를 담은 메시지.

주기적으로 flooded 되어야 함(모든 노드들에게 데이터를 전달한다는 의미)

tc메세지를 보낼때 mpr을 지정해서 보내기 때문에 그 mpr을 수신한 노드들 중에서 mpr 패킷에 자신이라고 표시되었으면, 그것을 다시 재전송한다. 그 노드가 재전송을할때 다시 mpr을 지정해서 똑같은 과정을 반복한다.

TC에는 MPR SELECTOR SET에 대한 정보가 들어가있다. 또한, 정보의 최신성을 나타내기 위해서 시퀀스 넘버도 존재한다.

또한 TC는 MPR에 의해서만 재전송 된다.

이 그림에서 S->M->Y->A로 tc가 전달 될때, 선택되는 mpr들은 M,Y,A이다. 이 정보들이 MPR selector set이라고도 할수 있으므로, tc에 이 경로를 적어 놓아야 a가 이 tc를 수신 했을때 s에 대한 경로를 알수 있게 된다.

Topology Informaint Base라는것이 라우팅 테이블과 비슷한 개념인데 OLSR프로토콜에서 사용되는 라우팅 테이블이라고 생각하면 될것 같다.

TC를 수신한 노드들은 TIB에 경로 정보와 시퀀스 넘버를 기록하게 된다.

link state 알고리즘 에서 높은 오버헤드 문제를 해결하기 위해서 나온게 OLSR프로토콜이다.

GPSR

노드들의 정보를 GPS정보로 인식한다. geographical

GPSR - Greedy Perimeter Stateless Routing algorithm

Stateless -> 주변 노드 정보는 저장하지만 라우팅 테이블이 존재 하지 않음.

Greedy,perimeter->경로찾기 문제를 해결하기 위한 2개의 알고리즘 이름.

경로 정보를 위치 정보로 저장한다. (노드의 주소로 경로를 결정하지 않는다)

노드의 주소랑 상관없이 홍대가 위도 경도 몇에 위치해 있다 라는 정보가 중요하다.

각 노드들은 원홉 네이버들의 정보와 최종 데스티네이션의 위치 정보를 알고 있어야 한다.

양방향 통신이 가능하며 2차원적인 구조를 네트워크가 구성하고 있어야 한다.

GPSR의 동작 과정

Neighbor Discovery - 주변 노드를 찾는 과정

Planarized Graphs - 부적합한 주변 노드 일부를 걸러내는 과정

Greedy Forwarding - 일단은 이 알고리즘을 돌림

Perimeter Routing - 그리디 알고리즘이 안통하면 이 알고리즘 사용해서 경로찾음.

Greedy forwarding - 목적지에 가장 가까운 next hop에게 패킷을 포워딩한다.

항상 최적의 해를 내지 않아서, 그런 경우 perimeter 라우팅 적용.

Neighbor Discovery 

주변 노드들과 주기적으로 heartbeat packet을 주고 받는다.(나의 존재를 주변 노드들에게 알림 hello packet과 비슷)

주변 노드가 나에게 데이터를 보내지 않으면 (일정 주기가 지나면) 존재 하지 않다고 판단.

일부 네이버들을 걸러내는 작업이 planarization 이라고 한다.

planar graph란 평면에서 서로 교차해서 지나가는 엣지가 없는 그래프를 지칭한다.

Relative Neighborhood Graph

Gabriel Graph

회색 지점에 포함되는 노드들을 지워버린다. 노드를 지우면 링크도 줄어든다.

RNG가 GG보다 더 많은 네이버들을 제거한다.

위의 두 방식을 사용하면 planar graph를 만들수 있다.

perimeter routing은 planar graph에서만 동작한다.

planar graph가 아닌데 이 알고리즘을 돌리면 루프가 발생할 가능성이 있다.

그리디 알고리즘을 돌리기 위해서는 목적지의 위치정보만 있으면 되지만 perimeter 알고리즘을 돌리기 위해서는 여러가지 정보들이 필요하다.

x가 D에게 보내려고 하는데, w와 y보다 x 자기 자신이 오히려 D보다 가까우므로 누구에게 패킷을 전달해야 하는지 그리디 알고리즘으로는 결정이 불가능 하다. 이런상황을 void라고 한다.

따라서 perimeter알고리즘을 사용해야 한다. 그래서 일단은 Right Hand Rule을 통해서 (void에서 빠져 나오기 위해서) w에게 패킷을 전달하고 그 이후부터는 다시 그리디 알고리즘을 돌린다.

perimeter모드로 동작 시키기 위해서는 perimeter 모드로 동작을 처음 시작한 노드의 위치를 기억해 놓아야 한다.(Lp)

왜냐하면, perimeter에서 다시 그리디 알고리즘으로 돌아가는 방법이,

처음 perimeter로 진입을 시작한 노드의 위치에서 Destination까지의 거리가

현재 노드의 위치와 D까지의 거리보다 긴경우 다시 그리디 알고리즘으로 돌아가게끔 설계되어 있기 때문이다. 

다시말해서 다시 그리디 알고리즘으로 돌아가게 하기 위해서 처음 perimeter로 동작을 시작한 노드의 위치정보를 헤더에 기록하는것이다.

x는 w와 y중 그리디알고리즘으로 패킷을 전송할수 없어서 perimeter모드로 동작하고,

right hand rule에 의해서 w에게 패킷을 전송한다. w도 마찬가지로 v에게 패킷을 전달하고 v는 드디어 x보다 자신이 D보다 가까워 졌으므로

다시 그리디 알고리즘을 통해서 D에 도착한다.

위의 그림은 만약 planarization이 되지 않은 그래프에 perimeter알고리즘을 돌릴때 나타나는 그림이다.

그림에서 처럼 루프가 생겼다. right hand rule방식으로 동작하는데 이 방식은 반시계방향으로 돌리다가 처음 만나는 엣지가 다음 엣지가 된다는 규칙이다. x->D에 오른손을 올려놓으면 처음 반시계방향인 u가 선택 되고, 그다음 u->x에 오른쪽 손날을 올리면 u->z엣지가 선택되고 z->u에 오른쪽 손날을 올리고 반시계방향으로 돌리면 z->u가 선택되며 마찬가지로 선택을 했을때 루프가 생긴다.