[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR101243244B1 - 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법 - Google Patents

애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법 Download PDF

Info

Publication number
KR101243244B1
KR101243244B1 KR1020100130047A KR20100130047A KR101243244B1 KR 101243244 B1 KR101243244 B1 KR 101243244B1 KR 1020100130047 A KR1020100130047 A KR 1020100130047A KR 20100130047 A KR20100130047 A KR 20100130047A KR 101243244 B1 KR101243244 B1 KR 101243244B1
Authority
KR
South Korea
Prior art keywords
node
energy consumption
request message
route
path
Prior art date
Application number
KR1020100130047A
Other languages
English (en)
Other versions
KR20120068427A (ko
Inventor
안순신
남흥우
신현재
Original Assignee
강릉원주대학교산학협력단
고려대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 강릉원주대학교산학협력단, 고려대학교 산학협력단 filed Critical 강릉원주대학교산학협력단
Priority to KR1020100130047A priority Critical patent/KR101243244B1/ko
Publication of KR20120068427A publication Critical patent/KR20120068427A/ko
Application granted granted Critical
Publication of KR101243244B1 publication Critical patent/KR101243244B1/ko

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/04—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources
    • H04W40/10—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources based on available power or energy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W52/00—Power management, e.g. TPC [Transmission Power Control], power saving or power classes
    • H04W52/02—Power saving arrangements
    • H04W52/0209—Power saving arrangements in terminal devices
    • H04W52/0212—Power saving arrangements in terminal devices managed by the network, e.g. network or access point is master and terminal is slave
    • H04W52/0219—Power saving arrangements in terminal devices managed by the network, e.g. network or access point is master and terminal is slave where the power saving management affects multiple terminals
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W84/00—Network topologies
    • H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D30/00—Reducing energy consumption in communication networks
    • Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

본 발명은 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치, 방법 및 그 방법을 기록한 기록매체에 관한 것으로, 본 발명에 따른 경로 탐색 방법에서 현재 노드는 이웃 노드로부터 경로 요청 메시지를 수신하고, 이웃 노드의 위치 정보와 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 산출된 수신 거리를 이용하여 출발지 노드로부터 현재 노드까지의 누적 에너지 소모량을 산출하며, 현재 노드의 위치 정보와 산출된 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트한다.

Description

애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법{Routing apparatus and method for minimizing the energy consumption in ad-hoc network}
본 발명은 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치 및 방법에 관한 것으로, 특히 기반 구조나 네트워크 구성에 대한 특정 규칙없이 임의의 노드들이 자율적으로 네트워크를 구성하는 애드혹 네트워크 상에서 무선 인터페이스를 사용하여 하나의 노드에서 다른 노드에 경로 요청 메시지를 전달하여 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치, 방법 및 그 방법을 기록한 기록매체에 관한 것이다.
최근 무선 통신이 빠르게 발전함에 따라, 보다 적은 전력을 소모하고, 보다 적은 비용으로 생산이 가능하며, 그 크기도 작은 스마트 센서 노드(smart sensor node)가 실현되고 있다. 이러한 센서 노드들은 주위로부터 온도, 습도 및 조도와 같은 환경 요소들을 측정하는데 활용되고 있다. 또한, 센서 노드들은 측정된 데이터를 처리하고, 센서 노드들 상호 간의 통신을 통해 데이터를 주고 받을 수 있다.
이러한 센서 노드들이 복수 개 모이면 인간의 지원 없이 자기-구성 능력(self-organizing ability)을 가지는 무선 센서 네트워크(wireless sensor network, WSN)를 구축할 수 있다. 따라서, 다수의 센서 노드들은 임의로(randomly) 비행기 또는 헬리콥터로부터 투척되어 배치되더라도 각각이 보유한 무선 통신 수단을 이용하여 무선 센서 네트워크를 구축할 수 있다. 이러한 무선 센서 네트워크는 과학, 의학, 군사 및 자연 재해 예방과 같은 다양한 영역에서 각각의 목적에 따른 모니터링 어플리케이션에 폭넓게 활용될 수 있다.
한편, 무선 센서 네트워크는 각각의 센서 노드들 간의 통신을 위해 노드(node)들에 의해 자율적으로 구성되는 애드혹 네트워크(ad-hoc network)를 사용할 수 있다. 애드혹 네트워크는 네트워크의 구성 및 유지를 위해 기지국이나 액세스 포인트와 같은 기반 네트워크 장치나 특정 네트워크 연결 규칙을 필요로 하지 않는다. 애드혹 노드들은 무선 인터페이스를 사용하여 서로 통신하고, 멀티 홉 라우팅(multi hop routing) 기능에 의해 무선 인터페이스가 가지는 통신 거리상의 제약을 극복하며, 노드들의 이동이 자유롭기 때문에 네트워크 위상(topology)이 동적으로 변화되는 특징이 있다.
본 발명이 해결하고자 하는 기술적 과제는 무선 센서 네트워크를 구성하는 센서 노드들이 작은 배터리를 가짐으로 인해 무선 센서 네트워크 상에서의 경로 탐색 및 네트워크의 유지를 위한 전력 공급이 제한되는 한계를 극복하고, 그로 인해 네트워크의 지속 시간이 단축될 수 밖에 없는 문제점을 해결하고자 한다. 나아가 경로 탐색에 특정 센서 노드가 빈번하게 활용됨으로써 해당 센서 노드의 잔여 전력이 빠르게 소진되고, 그 결과 네트워크의 지속 시간이 단축되는 문제점을 해결하고자 한다.
상기 기술적 과제를 해결하기 위하여, 본 발명에 따른 애드혹 네트워크에서 출발지 노드(node)로부터 목적지 노드까지의 경로를 탐색하는 방법은 현재 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하는 단계; 상기 이웃 노드의 위치 정보와 상기 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하는 단계; 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 단계; 및 상기 현재 노드가 상기 현재 노드의 위치 정보와 상기 산출된 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트(broadcast)하는 단계를 포함한다.
또한, 상기 기술적 과제를 해결하기 위하여, 본 발명에 따른 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 방법은 상기 목적지 노드가 적어도 하나 이상의 경유 노드로부터 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하는 단계; 상기 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출하는 단계; 및 상기 추출된 전송 경로를 따라 경로 응답 메시지를 유니캐스트(unicast)하는 단계를 포함하고, 상기 누적 에너지 소모량은 상기 경유 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 상기 경유 노드가 상기 이웃 노드의 위치 정보와 상기 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하며, 상기 경유 노드가 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 산출하여 브로드캐스트함으로써 상기 목적지 노드에 전달된다.
또한, 상기 기술적 과제를 해결하기 위하여, 본 발명에 따른 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 방법은 상기 출발지 노드가 자신의 위치 정보 및 0의 값을 갖는 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트하는 단계; 및 상기 출발지 노드가 상기 목적지 노드로부터 탐색된 경로에 대한 응답 메시지를 수신하는 단계를 포함하고, 상기 탐색된 경로는 경유 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 상기 경로 요청 메시지를 수신하고, 상기 이웃 노드의 위치 정보와 상기 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 산출하여 상기 목적지 노드에 전달하고, 상기 목적지 노드가 적어도 하나 이상의 경유 노드로부터 상기 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 상기 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출함으로써 획득된다.
한편, 상기 다른 기술적 과제를 해결하기 위하여, 상기된 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 방법은 상기 경로 요청 메시지가 잔여 에너지 임계값을 더 포함하고, 상기 현재 노드가 자신의 잔여 에너지와 상기 잔여 에너지 임계값을 비교하는 단계를 더 포함하며, 상기 현재 노드가 경로 요청 메시지를 브로드캐스트하는 단계는 상기 비교 결과에 따라 선택적으로 수행된다.
나아가, 이하에서는 상기 기재된 터치 감지 수단을 구비하는 사용자 식별 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공한다.
상기 기술적 과제를 해결하기 위하여, 본 발명에 따른 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치는 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 현재 노드의 위치 정보와 상기 현재 노드의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트하는 통신부; 및 상기 이웃 노드의 위치 정보와 상기 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 처리부를 포함한다.
한편, 상기 다른 기술적 과제를 해결하기 위하여, 상기된 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치는 상기 경로 요청 메시지가 잔여 에너지 임계값을 더 포함하고, 상기 처리부는 상기 현재 노드가 자신의 잔여 에너지와 상기 잔여 에너지 임계값을 비교하며, 상기 통신부는 비교 결과에 따라 상기 경로 요청 메시지를 선택적으로 브로드캐스트한다.
본 발명은 무선 센서 네트워크 내에서 누적 에너지 소모량을 최소화하는 경로를 발견함으로써 제한된 전력 공급 환경 하에서도 효율적인 전력 소모를 꾀할 수 있으며, 그로 인해 네트워크의 지속 시간(lifetime)을 최대화할 수 있다. 나아가 노드들의 잔여 에너지를 검사하여 적은 잔여 에너지를 갖는 노드를 전송 경로로부터 배제함으로써 특정 노드가 지나치게 빈번하게 활용되는 것을 방지하고, 그 결과 네트워크의 지속 시간을 향상시킬 수 있다.
도 1은 본 발명의 일 실시예에 따른 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하기 위해 사용하는 경로 요청 메시지의 구조를 예시한 도면이다.
도 2는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 경유 노드가 경로를 탐색하는 방법을 도시한 흐름도이다.
도 3은 본 발명의 다른 실시예에 따른 애드혹 네트워크에서 경유 노드가 긴급 메시지를 이용하여 경로를 탐색하는 방법과 잔여 에너지를 고려하여 경로를 탐색하는 방법을 설명하기 위한 흐름도이다.
도 4는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 목적지 노드가 경로를 탐색하는 방법을 도시한 흐름도이다.
도 5a 및 도 5b는 애드혹 네트워크에서 다양한 방법을 활용하여 출발지 노드로부터 목적지 노드까지의 경로를 탐색하고 각각의 방법에서 소모한 에너지를 비교하여 설명하기 위한 도면이다.
도 6는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 출발지 노드가 경로를 탐색하는 방법을 도시한 흐름도이다.
도 7은 본 발명의 일 실시예에 따른 애드혹 네트워크에서 경로를 탐색하는 개별 장치인 센서 노드를 도시한 블록도이다.
본 발명의 실시예들을 설명하기에 앞서 실시예들이 구현되는 환경에 대해 개괄적으로 소개하고, 실시예들이 공통적으로 채용하고 있는 기본 아이디어를 제시하고자 한다.
앞서 소개한 바와 같이 센서 노드는 작은 폼-팩터(form-factor)를 가지므로 작은 크기의 배터리만을 가질 수 있으며, 그 결과 센서 노드들은 에너지 공급이 제한된다. 따라서, 많은 센서 노드들로 구성된 네트워크의 지속 시간을 증가시키기 위해서는 필연적으로 제한된 에너지 자원을 효율적으로 사용하여야만 한다. 즉, 보다 긴 네트워크의 지속 시간을 달성하기 위해 데이터 전송 프로토콜은 전체 네트워크를 통해 에너지 소모를 최소화하도록 설계될 필요가 있다.
AODV(ad-hoc on-demand distance vector) 라우팅 프로토콜(routing protocol)은 무선 센서 네트워크 환경에서 사용하는 대표적인 라우팅 방법으로, 애드혹 모바일 네트워크에서 동적 소스 라우팅(dynamic source routing, DSR) 프로토콜의 문제점 해결을 위해 제안되었다. AODV는 좀 더 적은 메모리로 라우팅이 가능하도록 하기 위해서 데이터 전달 시에만 사용되는 주문형 라우팅 프로토콜이며, 데이터를 전달하지 않는 경우에는 사용되지 않으므로 라우팅에 의한 오버헤드가 적다는 특징이 있다.
AODV 라우팅 방법은 애드혹 네트워크에 참여하는 무선 노드가 데이터를 전달하기 위해서 라우팅 경로를 요구하는 경우에 라우팅 경로를 찾기 위해서 사용된다. 이를 위해 출발지 노드(source node)는 라우팅 경로를 찾기 위한 경로 요청(route request, RREQ) 메시지를 네트워크에 플러딩(flooding)한다. 경로 요청 메시지를 수신한 노드들은 이웃 노드들에게 다시 경로 요청 메시지를 플러딩하고, 목적지 노드(destination node)가 경로 요청 메시지를 수신하였을 경우, 경로 응답(route reply, RREP) 메시지를 출발지 노드로 전송한다. 이 때, 전송 경로는 경로 요청 메시지가 전송된 경로의 역방향이다. 이제, 경로 응답 메시지를 수신한 출발지 노드는 경로 응답 메시지가 전달된 경로를 통해 데이터를 목적지 노드에 전송한다.
그러나, AODV 라우팅 방법은 경로를 탐색함에 있어서 단지 이웃 노드에만 브로드캐스트(broadcast)하여 경로 요청 메시지를 전달하므로 각 노드의 에너지 소모의 관점에서 최적화된 경로를 제시하지는 못한다. 또한, AODV 라우팅 방법은 각 노드들의 잔여 에너지를 고려하지 않기 때문에 특정 노드의 빠른 에너지 고갈을 야기할 수 있다. 따라서, 이후에 설명할 본 발명의 실시예들에서는 전체 네트워크의 수명을 극대화시키는 것에 집중하여 경로 탐색 방법을 제안하고자 한다.
이하의 실시예들이 채택하는 라우팅 프로토콜에 따르면 하나의 노드가 다른 노드로 패킷(packet)을 전송할 때 에너지 소모를 최소화하도록 경로를 탐색한다. 이를 위해 상기 라우팅 프로토콜은 노드들 간의 에너지 소모 및 각각의 노드들의 잔여 에너지를 이용하여 에너지 소모가 최소화되는 경로를 선택하는 방법을 제안한다. 또한, 네트워크 내에서 특정 노드가 집중적으로 사용되어 잔여 에너지가 일정 수준 이하로 소진될 경우, 해당 노드를 경로로부터 배제시킴으로써 네트워크 분리(network partition) 현상을 차단함과 동시에 네트워크 내의 균형있는 에너지 소모를 달성하고자 한다. 즉, 상기 라우팅 프로토콜은 소모되는 에너지를 전체 네트워크상에서 분산시킴으로써 네트워크의 지속 시간(lifetime)을 증가시킨다.
요약하건대, 본 발명의 실시예들의 한 측면은 에너지 소모를 최소화하는 경로 탐색 알고리즘을 제안하는 것이고, 다른 한 측면은 네트워크 상에서 에너지 소모를 분산시키는 유도 알고리즘을 제안하는 것이다. 이하에서는 도면을 참조하여 본 발명의 실시예들을 구체적으로 설명한다.
도 1은 본 발명의 일 실시예에 따른 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하기 위해 사용하는 경로 요청 메시지의 구조를 예시한 도면이다. 이하의 실시예들에서 네트워크 내의 각각의 노드는 GPS(global positioning system) 수신기를 구비함으로써 자신의 위치 정보를 알고 있다고 가정한다.
본 실시예를 통해 소개될 라우팅 프로토콜을 이용하기 위해서는 두 가지 정보가 필요하다. 첫째는 각 노드의 위치 정보이고, 둘째는 잔여 에너지이다. 이들 정보를 얻기 위해 통상적인 경로 요청(RREQ) 메시지 양식 내에 도 1에 도시된 바와 같은 3가지 파라메터(parameter)를 추가하였다. LI(location information)(110)은 해당 노드의 위치 정보를 나타내고, AEC(accumulated energy consumption)(120)는 생성되고 있는 경로 상에서 사용된 에너지 소비량의 합(출발지 노드로부터 해당 노드까지의 누적 에너지 소모량을 말한다.)을 의미하며, MRE(minimum residual energy)(130)는 최소 잔여 에너지를 의미한다. 두 노드 사이에서 데이터 전송시 사용되는 에너지는 무선 환경에서의 에너지 소비 모델(energy consumption model)을 통해 산출된다. 이러한 연산 과정에는 두 노드 사이의 거리 값이 필요한데, 이는 GPS를 통해 얻은 위치 정보(LI)(110)를 이용한다.
한편, 또 다른 추가 파라메터인 Emergency(140)는 전송하고자 하는 메시지가 긴급 메시지인지 여부를 나타내는 일종의 플래그(flag)이다. 긴급 메시지를 수신한 경유 노드들은 자신이 수신한 경로 요청 메시지를 다음의 이웃 노드로 바로 전달한다. 반면, 긴급하지 않은 경유 노드들(예를 들어, Emergency 파라메터가 'false'로 설정된 경우가 해당된다.)은 첫 경로 요청 메시지를 받은 후 일정 시간 동안 그 이후에 발생하는 경로 요청 메시지를 수신하여, 일련의 연산(상기된 에너지 소비 모델에 따라 누적 에너지 소모량을 산출하는 처리 과정을 의미한다.)을 수행한다. 이러한 Emergency(140)는 선택적으로 채택될 수 있는데, 그 구체적인 활용 방법은 이후의 도 3을 통해 설명하도록 하겠다.
도 1에 도시된 여타의 파라메터들은 통상적인 경로 요청 메시지에서 활용되는 것으로서, 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 용이하게 파악될 수 있으므로 구체적인 설명을 생략한다.
이제, 보다 구체적으로 애드혹 네크워크에서 에너지 소모를 최소화하는 경로 탐색 방법을 제시하고자 한다. 애드혹 네트워크를 구성하는 노드들은 경유 노드, 목적지 노드 및 출발지 노드로 구분될 수 있으며, 각각 그 수행 동작이 다소 상이하다. 이들 노드들의 수행 동작은 각각 도 2, 도 4 및 도 6에 도시되어 있는바, 이하에서 순서대로 설명하겠다.
도 2는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 경유 노드가 경로를 탐색하는 방법을 도시한 흐름도로서, 다음과 같은 단계들을 포함한다. 애드혹 네트워크에서 출발지 노드는 최초에 경로 요청 메시지를 생성한 후에, 이를 출발지 노드의 전송 범위 내에 있는 이웃 노드들에 브로드캐스트한다. 이렇게 브로드캐스트된 경로 요청 메시지가 현재의 경유 노드에 도착하는 상황을 가정한다.
210 단계에서 현재 노드는 이웃 노드로부터 이웃 노드의 위치 정보 및 출발지 노드로부터 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신한다. 이 때, 경로 요청 메시지는 앞서 소개한 도 1의 요청 메시지 양식이 활용될 수 있다. 즉, 이웃 노드로부터 수신된 경로 요청 메시지의 위치 정보(LI)는 이웃 노드가 구비하고 있는 GPS를 통해 획득된 이웃 노드의 현재 위치를 나타내고, 역시 경로 요청 메시지에 포함된 누적 에너지 소모량(AEC)은 출발지 노드로부터 이웃 노드까지 현재 발견된 경로 상에서 소모된 에너지의 총량을 의미한다.
220 단계에서는 210 단계를 통해 수신된 경로 요청 메시지에 포함된 이웃 노드의 위치 정보와 현재 노드의 위치 정보를 이용하여 수신 거리를 산출한다. 이러한 수신 거리는 다음의 수학식 1과 같은 유클리드 거리법(Euclidean distance method)을 이용하여 산출될 수 있다.
Figure 112010083521509-pat00001
수학식 1에서 X1, Y1, Z1은 이웃 노드의 위치를 나타내는 좌표값이고, X2, Y2, Z2은 현재 노드의 위치를 나타내는 좌표값이다. Z1 및 Z2 값은 3차원 좌표계를 사용할 경우 필요한 값이며, 2차원 좌표계를 사용할 경우에는 불필요할 것이다.
230 단계에서는 220 단계를 통해 산출된 수신 거리를 이용하여 출발지 노드로부터 현재 노드까지의 누적 에너지 소모량을 산출한다.
보다 구체적으로 누적 에너지 소모량을 산출하는 방법을 설명하기에 앞서 우선 2개의 노드들이 상호 데이터를 전송하고 수신할 때 발생하는 에너지 소모에 대해 설명하고자 한다. 2개의 노드들 간의 거리에 따른 에너지 소모는 다음의 수학식 2와 같이 정리된다.
Figure 112010083521509-pat00002
수학식 2에서 k는 패킷 사이즈(packet size)이고, d는 두 개의 노드들 간의 거리를 나타낸다. 전송자 노드(transmitter node)에서 에너지 소모는
Figure 112010083521509-pat00003
(Transmitter Electronics)과
Figure 112010083521509-pat00004
(Transmit Amplifier)를 포함한다. 수신자 노드(receiver node)에서, 에너지 소모는 오직
Figure 112010083521509-pat00005
(Receiver Electronics)만을 포함한다. 본 실시예에서는
Figure 112010083521509-pat00006
와
Figure 112010083521509-pat00007
가 같다고 가정하였다. 따라서, n개의 노드들 간의 전체 에너지 소모량은 다음의 수학식 3과 같이 정리된다.
Figure 112010083521509-pat00008
궁극적으로 n개의 노드들 간의 전체 에너지 소모량은 전송 거리(d) 및 전송 및 수신 동작에 관련된 노드들의 수(n)에 의해 영향을 받는다. 본 실시예에서는
Figure 112010083521509-pat00009
,
Figure 112010083521509-pat00010
이라고 가정하였으며, 이후 도 5b의 예를 통해 직접 에너지 소모량을 산출하는데 활용할 것이다.
다시 도 2로 돌아와서, 앞서 220 단계를 통해 수신 거리를 산출하였으므로, 이제 230 단계에서는 상기된 수학식 3을 사용하여 이웃 노드로부터 현재 노드까자의 에너지 소모량을 산출할 수 있다. 이어서, 산출된 에너지 소모량과 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 가산함으로써 전체 누적 에너지 소모량을 획득할 수 있다. 이 때, 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량은 앞서 소개한 도 1의 경로 요청 메시지 내에 포함된 값(AEC)임을 알 수 있다.
240 단계에서 현재 노드는 현재 노드의 위치 정보와 230 단계를 통해 산출된 누적 에너지 소모량을 포함하는 경로 요청 메시지를 자신의 이웃 노드에 브로드캐스트(broadcast)한다. 이렇게 브로드캐스트된 경로 요청 메시지는 적어도 하나 이상의 경유 노드(현재 노드를 포함한다.)를 거쳐 최종적으로 목적지 노드에 도달하게 되고, 목적지 노드는 최소의 누석 에너지 소모량(AEC)을 갖는 경로 요청 메시지에 따라 경로를 선택하게 된다.
도 3은 본 발명의 다른 실시예에 따른 애드혹 네트워크에서 경유 노드가 긴급 메시지를 이용하여 경로를 탐색하는 방법과 잔여 에너지를 고려하여 경로를 탐색하는 방법을 설명하기 위한 흐름도로서, 크게 2가지 측면에서 도 2의 흐름도와는 차이점이 있다.
첫째, 경로 요청 메시지 내에 긴급 메시지를 나타내는 파라메터가 포함되며, 파라메터의 설정 여부에 따라 통상의 브로드캐스트 방법(현재 노드의 이웃 노드에 단순히 경로 요청 메시지를 브로드캐스트하는 방법을 의미한다.)을 사용하거나 에너지 소모를 최소화하는 브로드캐스트 방법을 사용한다.
즉, 무선 센서 네트워크에서 출발지 노드는 목적지 노드를 찾기 위해 경로 탐색 메시지를 브로드캐스트하는데, 이러한 경로 탐색이 긴급할 경우에는 에너지 소모가 최소화되는 경로를 찾는 과정에 다소 시간이 소요됨을 고려하여 이러한 경로 탐색 과정없이 통상의 브로드캐스트 방법을 활용하게 된다. 반면, 긴급한 상황이 아닐 경우 경로 요청 메시지를 받은 경유 노드는 일정 시간 동안 자신이 받은 경로 요청 메시지, GPS를 통한 위치 정보와 앞서 소개한 에너지 소비 모델을 이용해 에너지 소비량을 산출한 후, 최소의 에너지 소비 경로를 갖는 경로 요청 메시지를 다음의 이웃 노드에 브로드캐스트한다.
도 3에서 310 단계는 경유 노드가 경로 요청 메시지를 수신하는 과정을 나타내고 있는데, 이러한 경로 요청 메시지는 데이터 전송의 긴급 여부를 나타내는 긴급도 정보를 더 포함한다. 320 단계에서는 경로 요청 메시지 내에 포함된 긴급도 여부 파라메터를 검사하고, 긴급도 정보에 따라 수신 거리를 산출하는 과정과 누적 에너지 소모량을 산출하는 과정을 선택적으로 수행한다. 만약 긴급하지 않은 경우(긴급도 파라메터가 '거짓(false)'으로 설정된 경우가 될 수 있다.)에는 다음의 330 단계로 진행하게 되는 반면, 긴급한 경우(긴급도 파라메터가 '참(true)'으로 설정된 경우가 될 수 있다.)에는 일련의 연산을 생략하고 곧바로 360 단계를 통해 경로 요청 메시지를 이웃 노드에 브로드캐스트한다.
둘째, 현재 노드의 잔여 에너지가 특정 임계치(threshold)보다 큰지 여부를 검사하고, 검사 결과에 따라 다른 연산을 수행한다. 즉, 경로 요청 메시지를 수신한 경유 노드가 임계치 이하의 잔여 에너지(residual energy, RE)를 가진다면, 확률적 과정을 통해서 다음의 이웃 노드에게 경로 요청 메시지를 전달할지 여부를 결정하게 된다.
만약 본 발명의 실시예들에서 상기된 첫 번째 알고리즘(에너지 소모를 최소화하는 알고리즘을 지칭한다.)만을 사용한다면, 에너지 소모가 특정 센서 노드에 집중될 우려가 있다. 에너지 소모가 특정 센서 노드에 집중되면, 네트워크의 지속 시간을 더욱 단축시키게 될 수 있다. 왜냐하면, 비록 현재의 경유 노드를 경로에 포함시키는 것이 전체 에너지 소모를 최소화시킬 수 있다고 할지라도, 해당 경유 노드를 반복적으로 사용할 경우 에너지 고갈로 인해 네트워크가 단절될 우려가 있기 때문이다.
따라서, 전체 네트워크 내에서 에너지 소모를 분산시키는 방법을 제안하고자 '임계치' 개념을 소개한다. 최초에는 모든 노드들이 잔여 에너지(RE)에 대해 동일한 임계치를 가진다고 가정한다. 경로 요청 메시지를 받은 하나의 노드는 자신의 잔여 에너지(RE)와 임계치를 비교한다. 즉, 현재의 경유 노드의 잔여 에너지를 검사함으로써 네트워크 내에 포함된 센서 노드들의 전력이 기준치(임계치를 의미한다.)보다 지나치게 낮아지는 것을 방지할 수 있으며, 결과적으로 네트워크의 지속 시간을 향상시키게 된다.
도 3에서 310 단계를 통해 수신된 경로 요청 메시지는 잔여 에너지 임계값(최소 잔여 에너지(MRE)를 의미한다.)을 더 포함하는데, 현재 노드가 가지고 있는 자신의 잔여 에너지(RE)와 비교를 위해 사용된다.
330 단계에서 현재 노드는 자신의 잔여 에너지(RE)와 잔여 에너지 임계값(threshold)을 비교한다. 비교 결과 자신의 잔여 에너지가 임계값보다 큰 경우에는 350 단계로 진행하여 누적 에너지 소모량을 갱신한다. 즉, 현재 노드는 자신의 위치 정보(LI)를 이용하여 이웃 노드와 현재 노드 간의 소비 에너지를 산출하고, 누적 에너지 소모량(AEC)을 갱신한 후, 360 단계를 통해 경로 요청 메시지를 다음의 이웃 노드들에게 브로드캐스트한다.
반면, 잔여 에너지가 임계값보다 크지 않다면 340 단계로 진행하여 특정 규칙에 따라 확률 처리를 수행하게 된다. 이러한 확률 처리는 다음의 수학식 4를 이용하여 처리될 수 있다.
Figure 112010083521509-pat00011
수학식 4에서 Pi 의 번위는 0~1 사이의 변수이고, N은 소정의 상수를 나타낸다. 즉, 잔여 에너지가 임계값보다 작은 경우에는 수학식 4와 같은 특정 규칙을 활용하여 현재 노드를 경로 설정에 포함시킬지 여부를 결정하게 된다. 수학식 4에 따르면 Pi 는 0~1 사이의 값이 되므로 일정한 확률의 빈도에 따라 경로 요청 메시지를 브로드캐스트하는 단계(360 단계)를 선택적으로 수행하게 된다. 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 상기된 확률 처리를 위한 수학식 4 뿐만 아니라 그 본질의 동일, 유사성이 인정되는 한 다양한 확률 처리 방법이 활용될 수 있음을 알 수 있다.
한편, 잔여 에너지(RE)가 임계값보다 크거나 확률 처리(340 단계)에 의해 경로로서 선택된 경우 350 단계를 통해 누적 에너지 소모량을 갱신한다. 이 과정은 현재 노드가 자신의 잔여 에너지(RE)와 잔여 에너지 임계값(MRE) 중 더 작은 값으로 잔여 에너지 임계값(MRE)을 갱신함으로써 수행될 수 있다. 마지막으로 360 단계에서는 갱신된 잔여 에너지 임계값을 경로 요청 메시지에 포함시켜 이웃 노드에 브로드캐스트한다.
도 4는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 목적지 노드가 경로를 탐색하는 방법을 도시한 흐름도로서, 다음과 같은 단계들을 포함한다.
410 단계에서 목적지 노드는 적어도 하나 이상의 경유 노드로부터 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신한다. 최종 목적지 노드는 첫 경로 요청 메시지를 수신한 후 일정 시간 동안만 또 다른 경로 요청 메시지를 수신한다.
420 단계에서는 410 단계를 통해 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 430 단계에서 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출한다. 예를 들어, 최초로 수신한 경로 요청 메시지와 두 번째로 수신한 경로 요청 메시지의 누적 에너지 소모량(AEC)을 비교한 후, 저 작은 누적 에너지 소모량에 해당하는 경로 요청 메시지만을 남기고, 다른 것은 폐기한다. 이러한 과정을 통해 목적지 노드는 출발지 노드로부터 에너지 소모량이 최소화되는 경로를 선택할 수 있게 된다.
한편, 누적 에너지 소모량은 앞서 도 2 내지 도 3을 통해 설명한 일련의 절차에 따라 산출된다. 즉, 경유 노드가 이웃 노드로부터 이웃 노드의 위치 정보 및 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 이웃 노드의 위치 정보와 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하며, 산출된 수신 거리를 이용하여 출발지 노드로부터 경유 노드까지의 누적 에너지 소모량을 산출하여 브로드캐스트함으로써 최종적으로 목적지 노드에 누적 에너지 소모량이 전달되게 된다.
440 단계에서 목적지 노드는 430 단계를 통해 추출된 전송 경로를 따라 경로 응답 메시지를 유니캐스트(unicast)한다. 즉, 최종적으로 목적지 노드에 남은 경로 요청 메시지의 역방향으로 경로 응답 메시지를 전송하고, 경로 응답 메시지를 수신한 출발지 노드는 설정된 경로를 통해 필요한 데이터를 전송한다. 경로 응답 메시지를 전송함에 있어서 이미 전송 경로가 확정되었기 때문에 불필요한 노드들의 시스템 자원을 낭비할 필요없이 유니캐스트 방식에 따라 통신하는 것이 유리하다.
도 5a 및 도 5b는 애드혹 네트워크에서 다양한 방법을 활용하여 출발지 노드로부터 목적지 노드까지의 경로를 탐색하고 각각의 방법에서 소모한 에너지를 비교하여 설명하기 위한 도면이다. 도 5a는 3가지 경로를 통해 A 노드로부터 D 노드로 임의의 패킷을 전송하는 절차를 보여준다. 도 5a에서 각 노드를 연결하는 에지(edge)에 표시된 값은 노드 간의 거리를 의미한다. 또한, 모든 가능한 경로와 에너지 소모는 도 5b에 주어진 값에 따른다.
첫째, [Route 1]은 통상적인 AODV에 따라 전송 경로를 설정하는 방법을 보여주고 있다. [Route 1]에서는 다른 경로보다 더 적은 수의 홉 카운트(hop count)를 갖는 A→D의 경로가 선택된다.
그러나, 본 발명의 실시예들을 통해 제안하고 있는 에너지 소모를 최소화하는 경로 탐색 방법에 따르면 [Route 1]의 선택은 바람직하지 못하다. 왜냐하면, [Route 1]의 총 소모 에너지가 1100의 값을 갖는 반면, 다른 경로 [Route 2] 내지 [Route 3]은 더 적은 총 소모 에너지 값을 갖기 때문이다.
에너지 소모의 관점에서 볼 때 가장 효율적인 경로는 총 700의 에너지를 소모하는 [Route 2]에 따른 A→C→D의 경로가 될 것이며, 이상에서 소개한 본 발명의 실시예들은 통상적인 경우 [Route 2]를 전송 경로로서 선택할 것이다.
한편, C 노드의 잔여 에너지가 임계치보다 작아진 경우를 가정하자. 이 경우, 이상에서 소개한 본 발명의 실시예들은 네트워크 절단을 막기 위해 해당 노드를 경로에서 배제하게 된다. 즉, 확률적인 방법을 통해 노드 C는 전송 경로로서 포함되지 않을 것이며, 차선으로 총 920의 에너지를 소모하는 [Route 3]에 따른 A→B→D 경로가 선택된다. [Route 3]은 전체 네트워크 내에서 에너지 소모를 분산시킴으로써 네트워크의 지속 시간을 극대화할 수 있다.
도 6는 본 발명의 일 실시예에 따른 애드혹 네트워크에서 출발지 노드가 경로를 탐색하는 방법을 도시한 흐름도로서, 다음과 같은 단계들을 포함한다.
610 단계에서 출발지 노드는 자신의 위치 정보 및 0의 값을 갖는 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트한다. 출발지 노드의 경우 이웃 노드로부터 경로 요청 메시지를 수신받지 않으므로 누적 에너지 소모량(AEC)은 0이 될 것이다. 또한, 최소 잔여 에너지(MRE)는 기본값(default)으로 설정될 수 있다.
이렇게 브로드캐스트된 경로 요청 메시지가 최종적으로 목적지 노드에 도착하면, 목적지 노드에 의해 에너지 소모량이 최소화되는 경로가 선택된다. 그러면, 620 단계에서 출발지 노드는 목적지 노드로부터 탐색된 경로에 대한 응답 메시지를 수신하게 된다.
이 때, 탐색된 경로는 이상의 도면들을 통해 설명된 방법에 따라 선택된다. 즉, 경유 노드가 이웃 노드로부터 이웃 노드의 위치 정보 및 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 이웃 노드의 위치 정보와 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 산출된 수신 거리를 이용하여 출발지 노드로부터 경유 노드까지의 누적 에너지 소모량을 산출하여 목적지 노드에 전달한다. 그러면, 목적지 노드는 적어도 하나 이상의 경유 노드로부터 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하여 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출한다.
도 7은 본 발명의 일 실시예에 따른 애드혹 네트워크에서 경로를 탐색하는 개별 장치인 센서 노드(700)를 도시한 블록도로서, 통신부(10), 제어부(20), 처리부(30), GPS(40) 및 센서(50)를 포함한다.
통신부(10)는 통상적으로 이웃 노드로부터 이웃 노드의 위치 정보 및 출발지 노드로부터 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 현재 노드의 위치 정보와 현재 노드의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트한다.
이러한 통신부(10)는 센서 노드에서 활용될 수 있는 무선 통신 수단을 통해 구현될 수 있으며, 그 통신 프로토콜 역시 센서 노드 간의 애드혹 통신 내지 범용 네트워크와의 연결에 활용되는 통신 프로토콜이 모두 활용 가능하다.
제어부(20)는 통신부(10), 처리부(30), GPS(40) 및 센서(50)에 전기적으로 연결되어 각각의 하드웨어를 제어한다. 따라서, 제어부(20)는 작은 용량의 명령어 셋(set)을 저장할 수 있으며, 이러한 명령에 따라 각각의 하드웨어를 동작시키고, 그 수행 결과를 수신하여 타 장치로 전달한다.
처리부(30)는 통상적으로 이웃 노드의 위치 정보와 상기 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 산출된 수신 거리를 이용하여 출발지 노드로부터 현재 노드까지의 누적 에너지 소모량을 산출한다. 보다 구체적으로, 처리부(30)는 산출된 수신 거리를 이용하여 이웃 노드와 현재 노드까지의 에너지 소모량을 산출하고, 산출된 에너지 소모량과 출발지 노드로부터 이웃 노드까지의 누적 에너지 소모량을 가산함으로써 출발지 노드로부터 현재 노드까지의 누적 에너지 소모량을 산출한다.
이러한 처리부(30)는 상기된 일련의 연산을 수행하기 위해 필요한 처리기(processor) 및 기억공간(memory)을 통해 구현될 수 있다. 이러한 처리기 내지 기억공간은 본 발명이 속하는 기술분야의 활용 환경이나 동작 환경을 고려하여 통상의 지식을 갖는 기술자에 의해 적절하게 선택될 수 있을 것이다. 나아가, 이러한 구성 요소들을 구현함에 있어서 이상에서 예시된 하드웨어들을 제어하기 위한 부가적인 소프트웨어 코드(code)도 활용될 수 있을 것이다.
한편, 통신부(10)를 통해 수신되는 경로 요청 메시지는 잔여 에너지 임계값을 더 포함할 수 있으며, 이 경우 처리부(30)는 현재 노드의 잔여 에너지와 잔여 에너지 임계값을 비교하여 해당 현재 노드를 전송 경로에 포함시킬지 여부를 결정한다. 따라서, 통신부(10)는 이러한 비교 결과에 따라 경로 요청 메시지를 이웃 노드에 선택적으로 브로드캐스트한다.
또한, 만약 현재 노드가 목적지 노드인 경우, 처리부(30)는 수신된 적어도 하나 이상의 요청 메시지에 포함된 누적 에너지 소모량 중에서 최소의 값을 선택하여 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출한다. 이어서, 통신부(10)는 처리부(30)를 통해 추출된 전송 경로를 따라 경로 응답 메시지를 유니캐스트하게 된다.
또한, 만약 현재 노드가 출발지 노드인 경우, 통신부(10)는 누적 에너지 소모량을 0으로 설정하여 요청 메시지를 브로드캐스트하고, 목적지 노드로부터 탐색된 경로에 대한 응답 메시지를 수신한다. 이 때, 탐색된 경로는 목적지 노드가 적어도 하나 이상의 경유 노드로부터 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하여 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출함으로써 획득된다.
한편, 센서 노드(700)들이 획득하는 위치 정보들은 각각의 노드들이 구비한 GPS(global positioning system) 수신기(40)를 통해 획득된 노드 자신의 현재 위치를 나타낸다. 이러한 위치 정보는 이웃 노드와 현재 노드와의 거리를 산출하는데 이용되며, 이를 위해 유클리드 거리법이 활용될 수 있음은 이미 설명한 바 있다.
센서(50)는 센서 노드(700)의 주위로부터 다양한 환경 인자들을 측정하기 위한 수단으로서, 본 실시예가 활용되는 환경에 따라서 다양한 스마트 센서가 활용될 수 있다. 상기된 실시예들에서 전송 경로를 탐색하는 것은 결국 센서(50)를 통해 수집된 정보를 원하는 목적지까지 보다 효과적으로 전송하기 위함이다.
상기된 실시예들에 따르면, 무선 센서 네트워크 내에서 누적 에너지 소모량을 최소화하는 경로를 발견함으로써 제한된 전력 공급 환경 하에서도 효율적인 전력 소모를 꾀할 수 있으며, 그로 인해 네트워크의 지속 시간을 최대화할 수 있다. 나아가, 노드들의 잔여 에너지를 검사하여 임계치보다 작은 잔여 에너지를 갖는 노드를 전송 경로로부터 배제함으로써 특정 노드가 빈번하게 활용되는 것을 방지하고, 그 결과 네트워크의 지속 시간을 향상시킬 수 있다.
한편, 본 발명은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수 있는 코드로 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록 매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록 장치를 포함한다.
컴퓨터가 읽을 수 있는 기록 매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광 데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현하는 것을 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산 방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다. 그리고 본 발명을 구현하기 위한 기능적인(functional) 프로그램, 코드 및 코드 세그먼트들은 본 발명이 속하는 기술 분야의 프로그래머들에 의하여 용이하게 추론될 수 있다.
이상에서 본 발명에 대하여 그 다양한 실시예들을 중심으로 살펴보았다. 본 발명에 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다.
700 : 에드혹 네트워크에서 경로를 탐색하는 장치(센서 노드)
10 : 통신부 20 : 제어부
30 : 처리부 40 : GPS
50 : 센서

Claims (18)

  1. 애드혹 네트워크(ad-hoc network)에서 출발지 노드(node)로부터 목적지 노드까지의 경로를 탐색하는 방법에 있어서,
    현재 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량 및 잔여 에너지 임계값을 포함하는 경로 요청 메시지를 수신하는 단계;
    상기 현재 노드가 자신의 잔여 에너지와 상기 잔여 에너지 임계값을 비교하는 단계;
    상기 이웃 노드의 위치 정보와 상기 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하는 단계;
    상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 단계; 및
    상기 비교 결과에 따라 상기 현재 노드가 상기 현재 노드의 위치 정보와 상기 산출된 누적 에너지 소모량을 포함하는 경로 요청 메시지를 선택적으로 브로드캐스트(broadcast)하는 단계를 포함하는 방법.
  2. 제 1 항에 있어서,
    상기 누적 에너지 소모량을 산출하는 단계는,
    상기 산출된 수신 거리를 이용하여 상기 이웃 노드와 상기 현재 노드까지의 에너지 소모량을 산출하는 단계; 및
    상기 산출된 에너지 소모량과 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 가산함으로써 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 단계를 포함하는 방법.
  3. 제 1 항에 있어서,
    상기 수신 거리를 산출하는 단계는 유클리드 거리법(Euclidean distance method)을 이용하여 상기 이웃 노드로부터 상기 현재 노드까지의 수신 거리를 산출하는 것을 특징으로 하는 방법.
  4. 삭제
  5. 제 1 항에 있어서,
    상기 비교 결과 상기 현재 노드의 잔여 에너지가 상기 잔여 에너지 임계값보다 작은 경우, 소정 확률의 빈도에 따라 경로 요청 메시지를 브로드캐스트하는 것을 특징으로 하는 방법.
  6. 제 1 항에 있어서,
    상기 현재 노드가 상기 자신의 잔여 에너지와 상기 잔여 에너지 임계값 중 더 작은 값으로 상기 잔여 에너지 임계값을 갱신하는 단계를 더 포함하고,
    상기 경로 요청 메시지를 브로드캐스트하는 단계는 상기 갱신된 잔여 에너지 임계값을 경로 요청 메시지에 포함시키는 것을 특징으로 하는 방법.
  7. 제 1 항에 있어서,
    상기 경로 요청 메시지는 데이터 전송의 긴급 여부를 나타내는 긴급도 정보를 더 포함하고,
    상기 긴급도 정보에 따라 상기 수신 거리를 산출하는 단계 및 상기 누적 에너지 소모량을 산출하는 단계를 선택적으로 수행하는 것을 특징으로 하는 방법.
  8. 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 방법에 있어서,
    상기 목적지 노드가 적어도 하나 이상의 경유 노드로부터 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하는 단계;
    상기 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출하는 단계; 및
    상기 목적지 노드가 상기 추출된 전송 경로를 따라 경로 응답 메시지를 유니캐스트(unicast)하는 단계를 포함하고,
    상기 누적 에너지 소모량은,
    상기 경유 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고,
    상기 경유 노드가 상기 이웃 노드의 위치 정보와 상기 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하며,
    상기 경유 노드가 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 산출하여 브로드캐스트함으로써 상기 목적지 노드에 전달되는 것을 특징으로 하는 방법.
  9. 제 8 항에 있어서,
    상기 누적 에너지 소모량은,
    상기 산출된 수신 거리를 이용하여 상기 이웃 노드와 상기 경유 노드까지의 에너지 소모량을 산출하고,
    상기 산출된 에너지 소모량과 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 가산함으로써 획득되는 것을 특징으로 하는 방법.
  10. 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 방법에 있어서,
    상기 출발지 노드가 자신의 위치 정보 및 0의 값을 갖는 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트하는 단계; 및
    상기 출발지 노드가 상기 목적지 노드로부터 탐색된 경로에 대한 응답 메시지를 수신하는 단계를 포함하고,
    상기 탐색된 경로는,
    경유 노드가 이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 포함하는 상기 경로 요청 메시지를 수신하고, 상기 이웃 노드의 위치 정보와 상기 경유 노드의 위치 정보를 이용하여 수신 거리를 산출하고, 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 산출하여 상기 목적지 노드에 전달하고,
    상기 목적지 노드가 적어도 하나 이상의 경유 노드로부터 상기 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 상기 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출함으로써 획득되는 것을 특징으로 하는 방법.
  11. 제 10 항에 있어서,
    상기 누적 에너지 소모량은,
    상기 산출된 수신 거리를 이용하여 상기 이웃 노드와 상기 경유 노드까지의 에너지 소모량을 산출하고,
    상기 산출된 에너지 소모량과 상기 출발지 노드로부터 상기 경유 노드까지의 누적 에너지 소모량을 가산함으로써 획득되는 것을 특징으로 하는 방법.
  12. 제 1 항 내지 제 3 항, 제 5 항 내지 제 11 항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
  13. 애드혹 네트워크에서 출발지 노드로부터 목적지 노드까지의 경로를 탐색하는 장치에 있어서,
    이웃 노드로부터 상기 이웃 노드의 위치 정보 및 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량 및 잔여 에너지 임계값을 포함하는 경로 요청 메시지를 수신하고, 현재 노드의 위치 정보와 상기 현재 노드의 누적 에너지 소모량을 포함하는 경로 요청 메시지를 브로드캐스트하는 통신부; 및
    상기 현재 노드의 잔여 에너지와 상기 잔여 에너지 임계값을 비교하고, 상기 이웃 노드의 위치 정보와 상기 현재 노드의 위치 정보를 이용하여 수신 거리를 산출하며, 상기 산출된 수신 거리를 이용하여 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 처리부를 포함하되,
    상기 통신부는 상기 비교 결과에 따라 상기 경로 요청 메시지를 선택적으로 브로드캐스트하는 것을 특징으로 하는 장치.
  14. 제 13 항에 있어서,
    상기 처리부는 상기 산출된 수신 거리를 이용하여 상기 이웃 노드와 상기 현재 노드까지의 에너지 소모량을 산출하고, 상기 산출된 에너지 소모량과 상기 출발지 노드로부터 상기 이웃 노드까지의 누적 에너지 소모량을 가산함으로써 상기 출발지 노드로부터 상기 현재 노드까지의 누적 에너지 소모량을 산출하는 것을 특징으로 하는 장치.
  15. 삭제
  16. 제 13 항에 있어서,
    상기 현재 노드가 목적지 노드인 경우,
    상기 처리부는 상기 수신된 적어도 하나 이상의 요청 메시지에 포함된 누적 에너지 소모량 중에서 최소의 값을 선택하여 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출하고,
    상기 통신부는 상기 추출된 전송 경로를 따라 경로 응답 메시지를 유니캐스트하는 것을 특징으로 하는 장치.
  17. 제 13 항에 있어서,
    상기 현재 노드가 출발지 노드인 경우,
    상기 통신부는 상기 누적 에너지 소모량을 0으로 설정하여 상기 요청 메시지를 브로드캐스트하고, 상기 목적지 노드로부터 탐색된 경로에 대한 응답 메시지를 수신하고,
    상기 탐색된 경로는 상기 목적지 노드가 적어도 하나 이상의 경유 노드로부터 상기 누적 에너지 소모량을 포함하는 경로 요청 메시지를 수신하고, 상기 수신된 하나 이상의 누적 에너지 소모량 중에서 최소의 값을 선택하고, 상기 선택된 값에 해당하는 경로 요청 메시지로부터 전송 경로를 추출함으로써 획득되는 것을 특징으로 하는 장치.
  18. 제 13 항에 있어서,
    상기 위치 정보들은 각각의 노드들이 구비한 GPS(global positioning system) 수신기를 통해 획득된 노드 자신의 현재 위치인 것을 특징으로 하는 장치.
KR1020100130047A 2010-12-17 2010-12-17 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법 KR101243244B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020100130047A KR101243244B1 (ko) 2010-12-17 2010-12-17 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020100130047A KR101243244B1 (ko) 2010-12-17 2010-12-17 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법

Publications (2)

Publication Number Publication Date
KR20120068427A KR20120068427A (ko) 2012-06-27
KR101243244B1 true KR101243244B1 (ko) 2013-03-13

Family

ID=46687111

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020100130047A KR101243244B1 (ko) 2010-12-17 2010-12-17 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법

Country Status (1)

Country Link
KR (1) KR101243244B1 (ko)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104768200A (zh) * 2015-03-26 2015-07-08 重庆邮电大学 一种基于多径转发策略的稳定性wsn路由方法
US20220237712A1 (en) * 2017-08-14 2022-07-28 LO3 Energy Inc. Exergy token

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014104454A1 (ko) * 2012-12-31 2014-07-03 인텔렉추얼디스커버리 주식회사 지리적 정보를 이용한 라우팅 시스템 및 방법
WO2015090348A1 (en) 2013-12-16 2015-06-25 Telefonaktiebolaget L M Ericsson (Publ) Method and apparatus for data packet transmission

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
Sungsoon Cho. "Power-Aware Link Maintenance (PALM) for Mobile Ad Hoc Networks." Local Computer Networks, 2007. LCN 2007. 32nd IEEE Conference on, 403 - 410. 2007.10.15. *
유남규 외 2명. "이동 애드혹 네트워크에서 단말의 최대 소모 에너지를 최적화하는 라우팅 방안," 정보과학회논문지 : 정보통신, [2008] pp.158~165 (8pages). 2008년 4월. *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104768200A (zh) * 2015-03-26 2015-07-08 重庆邮电大学 一种基于多径转发策略的稳定性wsn路由方法
CN104768200B (zh) * 2015-03-26 2018-06-15 重庆邮电大学 一种基于多径转发策略的稳定性wsn路由方法
US20220237712A1 (en) * 2017-08-14 2022-07-28 LO3 Energy Inc. Exergy token
US12118628B2 (en) * 2017-08-14 2024-10-15 LO3 Energy Inc. Exergy token

Also Published As

Publication number Publication date
KR20120068427A (ko) 2012-06-27

Similar Documents

Publication Publication Date Title
Arafat et al. Routing protocols for unmanned aerial vehicle networks: A survey
Sharma et al. Rendezvous based routing protocol for wireless sensor networks with mobile sink
Faheem et al. MQRP: Mobile sinks-based QoS-aware data gathering protocol for wireless sensor networks-based smart grid applications in the context of industry 4.0-based on internet of things
KR101634585B1 (ko) 드론 네트워크에서 드론의 지리적 위치 정보를 기반으로 한 데이터 전달 방법
Tunca et al. Ring routing: An energy-efficient routing protocol for wireless sensor networks with a mobile sink
Pozza et al. Neighbor discovery for opportunistic networking in internet of things scenarios: A survey
Rahman et al. Totally opportunistic routing algorithm (TORA) for underwater wireless sensor network
US7486633B2 (en) Network system, radio communication device, radio communication method, and computer program for the same
Sahoo et al. Target tracking and boundary node selection algorithms of wireless sensor networks for internet services
Lima et al. Geographic routing and hole bypass using long range sinks for wireless sensor networks
Khedr et al. Minimum connected cover of a query region in heterogeneous wireless sensor networks
de Oliveira et al. An enhanced location-free Greedy Forward algorithm with hole bypass capability in wireless sensor networks
Ali et al. A performance‐aware routing mechanism for flying ad hoc networks
Benzerbadj et al. Cross-layer greedy position-based routing for multihop wireless sensor networks in a real environment
KR101243244B1 (ko) 애드혹 네트워크에서 에너지 소모를 최소화하는 경로 탐색 장치 및 방법
JV et al. Exploring data collection on Bluetooth Mesh networks
Sengul et al. A survey of adaptive services to cope with dynamics in wireless self-organizing networks
Sheu et al. Efficient path planning and data gathering protocols for the wireless sensor network
Biswas Redundancy-based Approaches in Wireless Multihop Network Design
Zhong et al. Oodt: obstacle aware opportunistic data transmission for cognitive radio ad hoc networks
Sammut et al. A location-based routing algorithm for wireless sensor networks
Pappas et al. A circulatory system approach for wireless sensor networks
Bonifácio et al. SMAC multi-hop mesh routing protocol using IEEE 802.15. 4
Shahid et al. Proactive multipath data dissemination for Multimedia Sensor Networks
Jain et al. Energy aware beaconless geographical routing in three dimensional wireless sensor networks

Legal Events

Date Code Title Description
A201 Request for examination
E902 Notification of reason for refusal
E701 Decision to grant or registration of patent right
GRNT Written decision to grant
FPAY Annual fee payment

Payment date: 20170109

Year of fee payment: 5

LAPS Lapse due to unpaid annual fee