출처:  " A Review of Current Routing Protocols for Ad-hoc Mobile Wireless Networks' Elizabeth M. Royer, C-K Toh  한글 번역

 

 Mobile Ad Hoc Network

     1970년대 무선통신이 처음 등장한 후, 무선 통신은 컴퓨터 관련 산업에서 점점 더 많이 사용되어 왔다. 특히 지난 10여년 간, 무선 통신에 이동성이 추가되면서, 이러한 추세는 더욱 심화되었다. 현재 두 가지 형태의 무선 이동 통신이 사용되고 있다. 하나는 infrastructured network로서, 고정되고 유선으로 연결된 gateway 내에서 사용되는 형태이다. 이러한 network를 위한 bridge들을 base station이라 한다. 이러한 network 내의 이동 단말기들은 통신 반경내의 가장 가까운 base station에 연결되어 통신하게 된다. 단말기가 이전의 base station의 영역을 벗어나 다른 base station의 영역으로 들어가게 되면, 이전의 base station으로부터 새 base station으로의 'handoff'가 일어나게 된다. 그리고 이 과정에서 단말기는 network로의 접속을 유지한 채 계속 통신을 할 수 있다. 이러한 application의 예로서는 사무 무선 LAN (WLAN)이 있다.


    
무선 이동 통신 network의 두 번째 형태로 일반적으로 ad hoc network라 불리는, infrastructureless moblie network가 있다. infrastructureless network는 고정된 router가 없다. 모든 node들은 이동할 수 있어며, 임의의 방법으로 동적으로 접속할 수 있다. 이러한 networknode들은 router로서 network 내의 다른 node로의 routing 경로를 찾아내고 유지한는 기능을 한다. ad hoc network의 예로 긴급 구난 구조 작전, 긴급한 정보 공유가 필요한 회의, 군사 network, wearable computing & communications 등에 사용된다.

    1970년대 DARPA에서 packet radio network를 개발한 이후, ad hoc mobile network를 위한 다양한 프로토콜들이 개발되어 왔다. 그러한 프로토콜들은 이러한 network가 가지는 특징적인 제한들, 즉 높은 전력소비, 낮은 대역폭, 높은 에러율을 다룰 수 있어야 한다. 그림 1에서 보듯이, routing 프로토콜은 일반적으로 table-driven 방식과 source-initiated(demand driven) 방식으로 나누어 볼 수 있다. 그림에서의 실선은 직접 포함되는 범주의 계열이며, 점선은 논리적으로 포함되는 계열이다.

    table-driven routing 프로토콜

    table-driven routing 프로토콜은 각 node로부터 network 내의 다른 모든 node로의 일관되고 갱신되는 routing 정보를 유지한다. 이러한 프로토콜들은 routing 정보를 저장하기 위하여 하나 또는 그 이상의 table을 필요로 하며, network 정보를 전파하여 모든 node들이 일관된 network topology에 대한 정보를 갖도록 table을 갱신한다. 이 프로토콜은 routing에 관련된 어떠한 table을 유지하는가에 따라 다시 분류될 수 있다. 다음은 table-driven ad hoc routing 프로토콜들이다.

    destination-sequence distance-vector routing

    destination-sequence distance-vector(DSDV) routing 프로토콜은 Bellman-Ford 알고리즘에 기반한 table-driven 알고리즘이다.
네트워크 내의 모든 이동 node들은 연결 가능한 다른 모든 node들에 대한 경로의 정보를 가지고 있다. 각 항목에는 목적지
sequence number가 있다. sequence number는 이동 node들이 routing loop를 방지하기 위하여 사용된다. routing table에서 갱신
된 내용은 일관성을 위하여 정기적으로 네트워크를 통하여 전송된다. 이러한 갱신을 위하여 전송되는 네트워크 traffic
을 경감하기 위하여 두 가지 형태의 packet을 사용한다. 첫 번째는 full dump이다. 이 packet은 모든 routing 정보를 전송하며
자주 사용되지 않는다. 작은 incremental packet이 마지막 full dump로부터 갱신된 정보를 전송하는 데 사용된다.
새로운 route broadcast는 목적지의 주소, 목적지까지의 hop 수, 목적지로부터의 정보에 대한 sequence number, broadcast에 대한
sequence number를 가지고 있다. routing 경로를 위하여 가장 최근의 sequence number를 찾는다. 또한 이동 단말기들은 경로에 대한 settling time 또는 weighted average time을 기록해 둔다. settling time의 길이를 이용하여 갱신된 routing 정보에 대한 broadcast를 지연시킴으로써, 이동 단말기들은 네트워크 traffic을 감소시키고, 보다 최적의 경로를 찾은 후 broadcast함으로써 경로를 최적화할 수 있다.


[
그림 1] ad hoc routing 프로토콜의 계열

    clusterhead gateway switch routing

    clusterhead gateway switch routing(CGSR) 프로토콜은 주소할당 방식과 네트워크 구성에서 앞의 DSDV 방식과 다르다. CGSRheuristic routing 방법을 사용하는 군집된 multihop 무선 이동 네트워크이다. ad hoc node 그룹에 cluster head 제어를 둠으로써 code 분리, channel 접근, routing, 대역폭 할당의 위한 framework가 가능하여 진다. cluster head 선택 알고리즘은 cluster 내의 node들 중 cluster head의 선택하는 데 사용된다. cluster head를 사용함으로써 단점은 cluster head가 자주 바뀌면 이에 대한 부하로 성능이 저하될 수 있다는 것이다. 이를 보안하기 위하여 least cluster change(LCC)가 사용된다. LCC를 이용하면, cluster head가 합하여 지거나, node가 다른 모든 cluster head로부터 분리될 경우에만 cluster head의 변화가 일어난다.
CGSR
DSDV를 기본 골격으로 하며 DSDV와 같이 많은 overhead가 있다. 그러나, sourcedestination 사이가 아닌, 계층적인 cluster headgateway간의 routing을 사용한다. packet은 우선 cluster head로부터 gateway로 전송되고, 다시 cluster head, 그러한 방식을 반복하여 목적지로 전송된다. 그림 2는 이러한 방식의 예를 보여준다. 이 방법에서 각 nodecluster member table을 유지하여야 한다. cluster member tableDSDV를 이용하여 정기적으로 이웃 nodebroadcast된다. node들은 cluster member table 외에, 목적지에 도달하기 위한 routing table도 유지한다.


[
그림 2] CGSR: node 1에서 node 8로의 routing

    wireless routing 프로토콜

    wireless routing 프로토콜(WRP)는 네트워크 내의 모든 routing 정보를 유지하려는 table-based 프로토콜이다. 각 node들은 distance table, routing table, link-cost table, messge retransmission list(MRL) table을 유지한다. MRL은 갱신 메시지의 sequence number, 재전송 counter, acknowledgement-required flag vector, 전송된 update list를 가지고 있다.
이동 단말기들은 갱신 메시지를 이용하여 서로에게 link의 변화를 알려준다. 갱신 메시지는 이웃 node 간에만 전송되며, 목적지와 목적지까지의 거리 및 ACK 응답까지 포함한다.
WRP는 이웃 node들로부터 전송되어온 정보들의 이전 node들에 대한 일관성을 검사함으로써 'count-to-infinity'의 문제를 해력한다. 따라서 looping이 발생하는 것을 막고, line failure에서 신속한 복구를 가능하게 한다.

    source-initiated on-demand routing

    table-driven routing과 다른 접근 방식으로 source-initiated on-demand routing 방법이 있다. 이러한 방식의 경우, source의 필요에 따라 경로가 설정된다. 목적지로의 경로가 필요하면, 네트워크 내의 경로 탐색 프로세스를 작동시킨다. 이 프로세스는 경로가 탐색되거나, 모든 가능한 경로 가능성에 대한 검사가 끝난 후에 완료된다. 이 경로는 목적지로 접근 불가능하게 되거나, 경로가 더 이상 필요 없을 때까지 유지된다.

    ad hoc on-demand distance vector routing

    ad hoc on-demand distance vector(AODV) routing 프로토콜은 DSDV 알고리즘을 사용한다. DSVP가 전체 경로에 대한 routing 정보를 유지하는데 비하여 AODV는 필요한 경로에 대한 routing 정보를 유지한다는 점에서 향상되었다고 할 수 있다. 선택되지 않은 node들은 routing table에 포함되지 않고 그에 대한 정보가 전송되지 않는다.
source node
에서 destination node로의 경로가 미리 만들어져 있지 않다면, 경로 탐색 프로세스를 사용한다. route request(RREQ)를 이웃 node들에 broadcast하고, 이웃 node들은 다시 그 이웃들에 broadcast하는 방식으로 경로를 찾아간다. 그림 3aRREQ가 네트워크를 통하여 전파되는 것을 보여준다. AODVdestination sequence number를 이용하여 loop-free하고 최신 routing 정보를 갖도록 한다.
RREQ
를 전송하는 동안, 중간 node들은 packetbroadcast한 이웃 node의 주소를 routing table에 기록하여 둠으로써 역경로를 만든다. 이후에 받게되는 동일한 RREQ packet들은 버린다. RREQ가 목적지에 도달하게되면, 목적지와 중간 node들은 RREQ 전송중에 만들어진 역경로로 route reply(RREP) packet을 보낸다. (그림 3b) RREP packet이 전송되는 과정에서 node들은 routing table에 전송 경로를 기록하게된다.


[
그림 3] AODV 경로 탐색

    dynamic source routing

    dynamic source routing(DSR)source routing에 기반한 on-demand routing 프로토콜이다. 이동 단말기들은 source route를 가진 route cache를 유지해야 한다. 새 경로가 입력될 때마다 지속적으로 cache를 갱신하여야 한다.
    
이 프로토콜은 경로 탐색과 경로 유지에 관한 부분으로 이루어진다. 이동 단말기가 전송하여야 할 packet이 있으면, route cache를 우선 확인 후, 유효기간이 지나지 않았다면 이 경로를 이용한다. 만약 cache에 없다면 route request packetbroadcast한다. packet을 받은 node들은 자신의 cache를 확인하고, 없다면 계속 전파한다.
    route request가 목적지에 도달하거나 그에 대한 cache를 가진 중간 node에 도달하면, route reply가 만들어진다. 그림 4aroute request가 네트워크를 통하여 전파되는 과정에서의 route record의 형식을 보여준다. route reply를 만든 곳이 목적지이면, route request에 포함된 route recordroute reply에 넣는다. 중간 node인 경우에는 cacherouteroute record에 덧붙여 route reply를 만든다. route reply를 반송하기 위하여, 응답하는 node에서 source node로의 경로가 있어야 한다. 응답 node에 이에 대한 경로가 cache에 없다면, symmetric link를 사용하여 route record의 경로를 역으로 만들거나, 경로 탐색과 새로운 route requestroute reply에 대한 piggyback을 만든다. 그림 4bsource node로의 route reply를 보여준다.


[그림 4] DSR에서의 route record의 생성

    temporally ordered routing algorithm

    temporally ordered routing algorithm(TORA)는 loop-free 분산 routing 알고리즘에 적합하다. 특히 매우 동적인 이동 통신 환경에 적합하다. 이는 source/destination 간의 source에 의하여 생성되는 다중 경로를 제공한다. TORA의 핵심은 topology 변화가 일어나는 작은 node의 집합 안에서만 제어 메시지가 사용되는 것이다. 이를 위하여 node들은 이웃 node들에 대한 routing 정보를 유지한다. 이 프로토콜은 경로의 생성, 유지, 삭제의 기능을 가진다.

    associativity-based routing

    associativity-based routing(ABR)은 loop, deadlock, packet의 중복을 제거하고 ad hoc mobile 네트워크에 대한 새로운 routing metric을 제공한다. 이 metric은 degree of association stability로 알려져 있다. ABR에서 각 이동 단말기의 경로는 이 metric으로 선택된다. 각 node는 정기적으로 자신의 존재를 알리는 신호를 만든다. 이를 이웃 node에서 받으면 관련된 table이 갱신된다. ABR의 기본적인 목적은 ad hoc mobile 네트워크에서 오래 지속되는 경로를 사용하는 것이다.
이는 경로 탐색, 경로 재설정(RRC), 경로 삭제의 과정으로 이루어진다. 경로 탐색은 broadcast query와 await-reply (BQ-REPLY) 과정이다. source가 이동하면, 새로운 BQ-REPLY 과정이 필요하며, 그림 5a와 같다. destination이 이동하는 경우, upstream node에서 경로를 삭제하고 localized query(LQ[H]) 과정을 통해 연결가능한지를 결정한다. H는 upstream node로부터 destination까지의 hop 수이다. destination이 LQ packet을 받으면 최상 부분 경로로 응답한다. 그렇지 않으면, node는 time out과 함께 다음 upstream node로 backtrack된다. 여기에서 RN[0] 메시지가 다음 upstream node로 전송되어, LQ[H] 프로세스를 수행하도록 한다.

contact mailto:monitor@dcs.chonbuk.ac.kr for more information.  
Copyright (c) 2003. Designed by DCS lab. All right reserved