Ad Hoc Network에서 라우팅 성능 향상을 위한 이웃 노드 정보를 이용한 적응성 경로 구성 전송 방식

(Adaptive Query Flooding using Neighbor Information for Routing Performance Enhancement in Ad Hoc Networks)

이학후†      강상욱‡      안순신§

(Hakhu Lee)     (Sangwook Kang)      (Sunshin An)

요  약  무선 이동통신이 실생활에 널리 보편화되면서, 무선 이동 기술은 휴대 무선 통신 장비에 대한 폭발적인 수요와 함께 통신 영역에서 중요한 역할을 담당할 것으로 보인다. 무선 이동통신 기술 중 특히 기존의 통신 인프라의 도움없이 임시적으로 무선 이동 노드들끼리 네트워크를 구성하는 mobile ad hoc network (MANET)이 최근에 주목을 받고 있다. 더욱이, ad hoc network의 특성을 고려할 때 효율적인 라우팅 프로토콜의 설계가 중요하다고 할 수 있다. 최근에는, 라우팅 프로토콜 중에서 on-demand 프로토콜이 낮은 라우팅 부하로 주목을 받고 있다. 그러나, on-demand 프로토콜은 경로 구성을 위해 경로 구성 패킷(query packet)을 broadcasting 하는 방식, 즉 flooding 방식, 을 사용하여 많은 수의 경로 구성 패킷을 발생시키는 문제점이 있다. 이러한 flooding 방식은 매우 비 효율적이며 또한 broadcast storm문제를 발생시킨다. 본 논문에서는 broadcast storm 문제를 해결하기 위해 Dynamic Adaptation Query flooding Using Neighbor Topology(NT-DAQ) 방식을 제안한다. 경로 구성 과정에서, 각 이동 노드들은 이웃 노드들의 정보를 기초로 하여 경로 구성에 참여 여부를 결정하게 된다. 이러한 제안 방식은 경로 구성 패킷의 수를 최소화 하여 네트워크 성능을 향상 시킬 수 있으며, 또한 시험을 통해 제안한 방식의 효율성을 입증하였다.

키워드 : mobile ad hoc network, flooding, 적응성 경로 구성

Abstract  As the wireless mobile communication is being widespread, mobile technologies will have important roles in the communication with the explosive growth of demanding for wireless portable devices. Among the mobile technologies, a great deal of interest has been taken in mobile ad hoc network (MANET), which is a collection of wireless mobile nodes forming a temporary network without the aid of stationary infrastructure in recent. Furthermore, considering characteristic of ad hoc networks, the design of efficient routing protocols is an important issue. In recent years, on-demand protocols among routing protocols have noticed because of the low routing overhead. However, on-demand protocols suffer from production of the enormous query packets by broadcasting in order to setup routes, that is, a flooding scheme. The flooding scheme is very costly and results in serious problem, which we refer as the broadcast storm problem. In this paper, we propose a Dynamic Adaptation Query flooding Using Neighbor Topology (NT-DAQ) scheme, in order to resolve the broadcast storm problem. When a route discovery is in progress, each mobile node decides on the basis of neighbor topology information whether discovery process participates or not. Therefore, our proposed scheme enables to improve network performance in which minimize the number of query packets. We evaluate the efficiency of our proposed scheme through simulation.

Key words : mobile ad hoc network, flooding, dynamic adaptation query flooding

Ad Hoc Network에서 라우팅 성능 향상을 위한 이웃 노드 정보를 이용한 적응성 경로 구성 전송 방식

정보과학회논문지 : 정보통신 제 31 권 제 6 호(2004.12)

†	비 회 원	:	고려대학교 전자공학과		CopyrightⒸ2004 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작물의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지: 정보통신 제31권 제6호(2004.12)
			hhlee@dsys.korea.ac.kr
‡	비 회 원	:	고려대학교 전자공학과
			klogic@dsys.korea.ac.kr
§	종신회원	:	고려대학교 전자공학과 교수
			sunshin@dsys.korea.ac.kr
	논문접수	:	2004년 06월 04일
	심사완료	:	2004년 08월 12일

1. Introduction

With the explosive growth of the demanding for the mobile computing, wireless networks have become increasingly popular in the mobile com-puting industry. In particular, a mobile ad hoc network [1,2,3] has recently attracted a lot of attentions, which is a collection of wireless mobile nodes forming a temporary network without the aid of any established infrastructure. In ad hoc net-works, adjacent nodes directly communicate bet-ween one another over wireless channels. However, since the transmission range of nodes is limited, the nodes that are not neighboring must commu-nicate with the support of one or more intermediate nodes acting as routers. Due to the mobility of nodes, the topology of connections between com-mu-ni-cating nodes may be quite adaptive. Thus, routing protocols must be adaptive and enable to maintain routes in spite of the changing network connectivity and design of efficient routing is a central challenging issue in such mobile ad hoc networks. Routing protocols of ad hoc networks can generally be categorized as table-driven and on-demand.

Table-driven protocols [3,4] attempt to maintain consistency, up-to-date routing information from each node to every other node in the network. Hence, these protocols require periodic routing messages regardless of whether it is needed or not and this feature is wasted both bandwidth and battery power in mobile nodes. On the other hand, on-demand protocols [3,4] set up and maintain routes from a source to a destination on a demand basis. To discover routes, it uses flooding technique, where the source floods the entire network with a query packet in search of a route to the destination. After receiving the query, each node checks whether it has destination information or not and propagates to neighbors via a wireless broadcast. This technique guarantees that the query reaches all nodes in network. In this paper, we call such flooding as network-wide flooding. Some of these protocols are TORA [4], SSR [4], DSR [6], AODV [7], and ABR [8]. According to recent performance papers, on-demand protocols have shown low routing overhead in comparison with table-driven protocols.

However, flooding scheme [5,9,10] incurs a numerous number of query packets and results in increasing of network overhead consequently. So, we focused on a solution of the flooding problem that incurs considerable network overhead, which increases end-to-end delay and decreases routing performance. To resolve flooding problem, we pro-pose a new scheme, Dynamic Adaptation Query flooding Using Neighbor Topology (NT-DAQ) employing topology information of neighbor nodes within a radio transmission range of a node. The design principle of NT-DAQ scheme establishes neighbor node table using periodic beacon hello messages for link breakage detection and its exis-tence signification. Using metric information of its table, each of nodes composes query flooding threshold range. When a source node needs a route to some destination, it broadcasts a query message to its neighbors, including query flooding threshold range information. Each node that receives query message checks query flooding threshold range information in receiving message and determines whether its message rebroadcasts or not. In case of a rebroadcast, it exchanges a receiving threshold for a self-threshold and broadcasts to neighbor nodes. In this way, it can reduce forwar-ding of unnecessary query message and contribute to im-prove network performance in consequence.

The remainder of the paper is organized as follows. In Section 2, we introduce a brief back-ground on the on-demand routing protocols, AODV and ABR, and review flooding mechanism using on-demand protocols. Section 3 describes our new scheme, Dynamic Adaptation Query flooding Using Neighbor Topology (NT-DAQ) architecture in detail. Section 4 shows simulation result with their ex-pla-nation. Finally, Section 5 provides our con-clusions.

2. Background

2.1 Ad hoc On-demand Distance Vector protocol (AODV)

AODV [7] is an on-demand variation of dis-tance vector protocols. AODV uses the basic on-demand mechanism of Route Discovery and Route Maintenance, which include the use of hop-by-hop routing and sequence numbers and periodic beacons. Routes are discovered on an as-needed basis and are maintained only as long as they are necessary. When a source node desires to send a message to some destination and does not already have a valid route to that destination, it initiates a path discovery process. It broadcasts a route request packet to its neighbors via flooding, until either the destination or an intermediate node with a “fresh enough” route to the destination is located. Once the request packet reaches the destination or an intermediate node with a fresh route, the destination or intermediate node responds by unicasting a route reply packet back to the neighbor. In order to maintain routes, AODV normally requires that each node periodically transmit a beacon hello message. In this way, each node maintains routing table, including route information. According to each node dynamically moving, if the link breaks, a Route Error message is sent to the source node and each node over link updates their route table. However, as mentioned above, AODV like on-demand routing protocols has serious problem such as increasing of routing overhead, using flooding mechanism.

References

[ 1 ]	C.K Toh, "Ad Hoc Mobile Wireless Networks: Protocols and Systems," Prentice Hall PTR, New Jersey, 2002.

이 학 후

1996년 동아대학교 전기공학과 졸업 1996년～현재 삼성전자㈜ 네트웍 사업부 책임 연구원. 2003년～현재 고려대학교 대학원 전자․컴퓨터공학과 석사과정. 관심분야는 Mobile Network, W-CDMA CDMA2000, QoS Multicast Routing