무선 센서 네트워크에서 자율 이동 로봇의 최단 경로 라우팅 알고리즘

Abstract

In wireless sensor networks with robots, the path for robots can be provided through wireless communication between robots and wireless sensor nodes. The network can also inform robots of events or information that sensors detect. In WSN, robots can perform high-level missions, such as human rescue, exploration in dangerous areas, maintenance and repair of unmanned networks in cooperation with surrounding sensor nodes. When sensors detect specific events and inform robots in remote areas, robots should move to the place in which events occur. They should move there as soon as possible in order to deal with the events quickly. This dissertation proposes an algorithm that guides robots to move to the destination via a short path that sensor nodes provide. Considering that low-cost sensor nodes with low resource can have no GPS and robots cannot use GPS indoors, the proposed algorithm can guide robots to the destination without location infrastructures like GPS. This dissertation proposes Distance-Aware Routing (DAR) for robot path planning, which modifies an existing packet routing algorithm for the robot path determination in sensor networks. DAR acquires the shortest physical distance using packets and received signal strength during the process of delivering information on the event from the sensor to the robots. Existing packet routing algorithms in communication networks focus on the hop count that is related to the number of passed nodes, not physical distance between nodes. DAR is a novel approach in which the packet routing algorithm is applied to the movement of robots. According to the computer simulation, DAR, when compared to DSR, has a shorter moving course in each case. In particular, when the straight-line distance between the node of the source and the node of the destination is 300m and the number of the distributed nodes is 70, the distance of moving courses of DAR is 58m shorter than that of DSR. In general, when DAR is used, the moving course distance is more reduced as the nodes are more distributed, but when DRS is used, the total distance of the moving course is random even when the distributed nodes are more. This phenomenon may be caused because the course selection of DSR is not based on actual distance. This dissertation showed through simulation that packet routing algorithms could be used for robot path planning in sensor networks and the performance of DAR are suitable for robot path planning.|무선 센서 네트워크는 이동형 로봇과 결합되어 로봇과 조밀하게 배치된 무선 센서노드 간의 무선통신에 의하여 로봇 경로가 가이드 되며, 로봇에게 특정한 사건을 알리거나 정보를 전달하는 등의 기능을 할 수 있다. 로봇은 센서네트워크 내에서 인명 구조, 위험지역 탐사, 주변 센서 노드와 협력하여 무인 네트워크에서의 유지 보수와 같은 고수준의 미션을 수행할 수 있다. 센서가 특정한 사건을 감지하여 이를 무선네트워크에 의해 원격지에 위치한 로봇에게 알리면, 로봇은 가능한 빨리 해당 사건 발생 지역으로 이동해야 한다. 이 때 가능한 빨리 해당지역에 도착해야 위급한 사건을 좀 더 빨리 처리할 수 있다. 본 논문에서는 위와 같은 상황을 배경으로 하여 로봇이 센서네트워크 내에서 목표지로 짧은 경로를 이동할 수 있도록 센서노드가 경로를 로봇에 제공하여 가이드 하는 알고리즘을 제안한다. 일반적으로 저가, 저자원인 센서노드에 GPS를 탑재할 수 없고, 로봇이 실내에 있는 경우처럼 로봇 또한 GPS를 사용할 수 없는 상황을 가정하여, GPS와 같은 위치정보 인프라 없이 목적지로 로봇을 안내할 수 있는 알고리즘이다. 기존에 패킷 라우팅 알고리즘을 로봇 센서네트워크에서 로봇 경로를 위해서 응용하여 로봇 경로 안내를 위한 Distance aware routing (DAR)을 제안하며, 이 라우팅 알고리즘은 사건이 발생한 센서노드가 사건정보를 로봇에게 전달하는 과정에서 가장 짧은 물리적 거리의 경로를 통신 패킷과 수신신호세기를 이용해서 조사하여 이후 로봇이 그 경로로 이동할 수 있도록 센서와 무선 노드 간의 통신으로 정보를 제공한다. 기존 통신망 라우팅 알고리즘에서는 홉 카운트를 중요시하여 노드 간의 물리적 거리가 아닌 거쳐가는 노드 수를 통신 성능으로 중시하여 응용하는데, 본 논문의 DAR은 이를 로봇의 이동과 관련시킨 새로운 연구이다. 시뮬레이션을 통해서, 각각의 경우에 대비하여 DAR은 DSR에 비해 짧은 이동경로를 선택한다는 걸 알 수 있다. 특히, 출발지 노드와 목적지 노드간 직선거리가 300m 이고 배치된 노드의 수가 70개 일 때, DSR을 사용할 때와 비교하여 58m나 짧은 이동경로거리 획득할 수 있었다. 전체적으로 볼 때, DAR은 노드가 많이 배치 될수록 전체적으로 이동경로 거리가 감소되는 모습을 보이는 반면, DSR을 사용하는 경우, 배치된 노드의 수가 늘어난다 할 지라도, 이동경로의 총 길이는 이와 관계 없이 무분별하게 나타난다. 이는 DSR의 경우 경로 선택에 있어 실제 거리를 기반으로 하지 않기 때문에 나타나는 현상으로 볼 수 있다. 본 논문에서는 무선통신망 라우팅 알고리즘들이 로봇 센서네트워크에서 로봇 이동 경로를 위해서 사용될 수 있음을 보여주었고 시뮬레이션을 통해서 DAR의 성능이 로봇이동경로에 적합함을 보여주었다.; In wireless sensor networks with robots, the path for robots can be provided through wireless communication between robots and wireless sensor nodes. The network can also inform robots of events or information that sensors detect. In WSN, robots can perform high-level missions, such as human rescue, exploration in dangerous areas, maintenance and repair of unmanned networks in cooperation with surrounding sensor nodes. When sensors detect specific events and inform robots in remote areas, robots should move to the place in which events occur. They should move there as soon as possible in order to deal with the events quickly. This dissertation proposes an algorithm that guides robots to move to the destination via a short path that sensor nodes provide. Considering that low-cost sensor nodes with low resource can have no GPS and robots cannot use GPS indoors, the proposed algorithm can guide robots to the destination without location infrastructures like GPS. This dissertation proposes Distance-Aware Routing (DAR) for robot path planning, which modifies an existing packet routing algorithm for the robot path determination in sensor networks. DAR acquires the shortest physical distance using packets and received signal strength during the process of delivering information on the event from the sensor to the robots. Existing packet routing algorithms in communication networks focus on the hop count that is related to the number of passed nodes, not physical distance between nodes. DAR is a novel approach in which the packet routing algorithm is applied to the movement of robots. According to the computer simulation, DAR, when compared to DSR, has a shorter moving course in each case. In particular, when the straight-line distance between the node of the source and the node of the destination is 300m and the number of the distributed nodes is 70, the distance of moving courses of DAR is 58m shorter than that of DSR. In general, when DAR is used, the moving course distance is more reduced as the nodes are more distributed, but when DRS is used, the total distance of the moving course is random even when the distributed nodes are more. This phenomenon may be caused because the course selection of DSR is not based on actual distance. This dissertation showed through simulation that packet routing algorithms could be used for robot path planning in sensor networks and the performance of DAR are suitable for robot path planning.