KR100856178B1

KR100856178B1 - 멀티-홉 무선 네트워크에서 비상주 링크를 검출하기 위한시스템 및 방법

Info

Publication number: KR100856178B1
Application number: KR1020077002092A
Authority: KR
Inventors: 세브넴 제트. 오저; 스롱 젱
Original assignee: 메시네트웍스, 인코포레이티드
Priority date: 2004-07-27
Filing date: 2005-07-26
Publication date: 2008-09-03
Anticipated expiration: 2025-07-26
Also published as: US20060023632A1; KR20070030301A; WO2006015007A2; DE112005001799T5; WO2006015007A3

Abstract

본 발명은 시의적절하고 신뢰할 수 있는 방식으로 비상주 링크를 검출하는 시스템 및 방법을 제공한다. 본 발명은 수신기 노드(102,106,107)에서의 유니캐스트 데이터 타임아웃 측정에 따르는 메트릭을 도입한다. 이 메트릭은 기존의 해결책과 조합하여 노드(102,106,107) 간의 링크 품질을 평가할 수 있다. 더욱이, 본 발명은 송수신기(108)가 패킷 완료율에 기초하여 링크 품질을 업데이트할 때 패킷 크기를 고려하여 비상주 링크 품질을 더욱 정밀하게 정량화한다.

비상주 링크, 유니캐스트 데이터, 타임아웃, 링크 품질, 패킷 완료율,

Description

멀티-홉 무선 네트워크에서 비상주 링크를 검출하기 위한 시스템 및 방법{SYSTEM AND METHOD FOR DETECTING TRANSIENT LINKS IN MULTI-HOP WIRELESS NETWORKS}

본 출원은 2004년 7월 27일에 출원한 미국특허 가출원번호 제60/591,305호의 우선권을 주장하고, 그 전반적인 내용은 본 명세서에 참조로서 포함한다.

본 발명은 무선 네트워크에서 노드 사이의 비상주 링크를 검출하기 위한 시스템 및 방법에 관한 것이다. 특히, 본 발명은, 패킷 크기 및 패킷 고장률을 고려하여 노드 사이에 있는 링크의 품질을 알아내고, 그 링크 품질에 기초하여 비상주 링크를 더욱 정밀하게 식별하는 시스템 및 방법에 관한 것이다.

최근, "애드-혹(ad-hoc)" 네트워크로 알려진 이동 통신 네트워크 타입이 개발되어왔다. 본 기술분야의 숙련자가 인식할 수 있는 바와 같이, 네트워크 노드는 데이터 패킷 통신을 다중화 포맷, 예컨대 시분할 다중 액세스(TDMA) 포맷, 코드분할 다중 액세스(CDMA) 포맷, 또는 주파수분할 다중 액세스(FDMA) 포맷으로 전송 및 수신한다.

종래의 애드-혹 네트워크에서처럼 이동 노드가 서로 통신할 수 있게 하는 것 외에, 이동 노드가 고정된 네트워크를 액세스하게 하여 다른 이동 노드, 예컨대 공중전화망(PSTN)의 노드 및 인터넷과 같은 다른 네트워크의 노드와 통신할 수 있게 하는 더욱 정교한 애드-혹 네트워크가 또한 개발되고 있다. 이와 같은 진보된 타입의 애드-혹 네트워크에 대한 상세한 내용은 "Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks"의 명칭으로 2001년 6월 29일에 출원한 미국특허출원번호 제09/897,790호(미국특허번호 제7,072,650호, 2006년 7월 4일 발행됨), "Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel"의 명칭으로 2001년 3월 22일에 출원한 미국특허 출원번호 제09/815,157호(미국특허번호 제6,807,165호, 2004년 10월 19일 발행됨) 및 "Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System"의 명칭으로 2001년 3월 22일에 출원한 미국특허 출원번호 제09/815,164호(미국특허번호 제6,873,839호, 2005년 3월 29일 발행됨)에서 기술하고, 그 각각의 전반적인 내용은 본 명세서에 참조로서 포함한다.

무선 송수신기 능력 및 노드의 인지된 간섭 레벨에서의 차이로 인하여 이동 애드-혹 네트워크에서는 단방향 링크가 통용된다. 또한, "비상주 링크" (Chin K-W., Judge J., Williams A. and Kermode R., "Implementation Experience with MANET Routing Protocols." ACM Sigcomm Computer Communications Review, Vol. 32, No 5, November 2002) 또는 "통신 그레이 존" (Lundgren H., Nordstrom E., Tschudin C., "Coping with Communication Gray Zones in IEEE 802.11b based Ad hoc Networks", WoWMoM 2002)으로 불리는 링크가 존재하는데, 이러한 문헌 둘 다는 본 명세서에 참조로서 포함한다. 그러한 존에서, 데이터 손실은 심하지만, 작은 메시지(예를 들어, 송신 요구(RTS)를 포함하는 제어 및 예약 메시지, 송신 허 가(CTS) 및 헬로(Hello) 메시지)는 여전히 성공적으로 교환할 수 있다. 그 주요 원인은 데이터 및 제어 메시지는 일반적으로 상이한 속도, 크기 및 변조로 전송된다는 데 있다. 더욱이, 다중 채널 네트워크에서 그러한 메시지는 상이한 주파수 범위에서 송신된다. 또한, 브로드캐스트 메시지는 응답하지 않고, 송신기는 성공률을 측정할 수 없다. 이동성이 증가함에 따라, 전송 경계선에서의 유동 링크의 수가 증가한다. 이러한 링크의 충돌은 제어 메시지 또는 작은 패킷 크기를 갖는 적은 수의 데이터 메시지를 이용하는 라우팅 프로토콜에서 심각해질 수도 있다. 이러한 문제점을 극복하려고 개발된 해결책으로는 라우팅 방식에 따라 여러 가지 해결책이 존재한다.

예를 들어, 단방향 링크에 대한 연구에서는 더 높은 지연 및 오버헤드를 도입할 수 있다(Marina M. K. and Das S. R., "Routing Performance in the Presence of Unidirectional Links in Multihop Wireless Networks," Mobihoc 2002, 본 명세서에 참조로서 포함). 애드 혹 주문형 거리 벡터(AODV: Ad Hoc On-Demand Distance Vector) 타입의 라우팅 프로토콜을 위한 해결책 중 하나는 블랙리스팅이다(Charles E. Perkins, Elizabeth M. Belding-Royer, Samir R. Das, "Ad hoc On-Demand Distance Vector(AODV) Routing", ietf draft Jan. 2002, 본 명세서에 참조로서 포함). 즉, 노드가 경로 응답(RREP: Route Reply) 전송 실패를 검출할 때마다, 노드는 실패한 RREP의 그 다음 홉을 블랙리스트 세트에 삽입한다. 수많은 단방향 링크가 존재하는 경우, 이 접근법은 비효율적이다(Marina M. K. and Das S. R., "Routing Performance in the Presence of Unidirectional Links in Multihop Wireless Networks," Mobihoc 2002, 본 명세서에 참조로서 포함). 더욱이, 그 기법은 노드가 블랙리스트에서 유지되는 기간을 지정하는 특정 타임아웃 값에 좌우된다.

또 다른 방법은 송신기가 헬로를 경청할 수 있는 모든 노드가 포함되는 주기적인 원-홉 헬로 메시지를 이용하는 것이다. 노드가 그 노드의 노드 id가 포함되지 않은 헬로 메시지를 경청하면, 노드는 대응하는 링크를 단방향으로서 표기한다. 본 명세서에 참조로서 포함하는 "Coping with Communication Gray Zones in IEEE 802.11b based Ad hoc Networks" by Lundgren H., Nordstrom E., and Tschudin C., WoWMoM 2002 문헌은 n개의 연속적인 헬로를 송신하는 것을 제안한다. 그러나 크고 빈번한 헬로 패킷은 오버헤드를 상당히 증가시킨다. 본 명세서에 참조로서 포함하는 "Routing Performance in the Presence of Unidirectional Links in Multihop Wireless Networks," by Marina M. K. and Das S. R., Mobihoc 2002 문헌에서 제안한 또 다른 해결책은 복수의 RREP가 단방향 경로를 탐색하는 분산형 검색 절차를 이용한다. RREP가 노드에서 실패하는 경우, 그 대응하는 역 경로는 소거하고, 이용가능하다면, RREP는 다른 역 경로를 따라 재시도한다. 일반적으로, 경로 요청(RREQ: Route Request)(대부분 브로드캐스트형) 및 RREP 타입의 메시지는 MTU 크기보다 작아 오버헤드를 감소시킨다. 다른 접근법도 존재한다. 본 명세서에 참조로서 포함하는 "Providing a Bidirectional Abstraction for Unidirectional Ad Hoc Networks," by Ramasubramanian V., Chandra R. and Mosse D., IEEE Infocom 2002 및 "A Tunneling Approach to Routing with Unidirectional Links in Mobile Ad-Hoc Networks," by Nesargi S. and Prakash R., IC3N 2000 문헌은 라우팅 프로토콜에서 단방향 링크를 이용하는 서브-라우팅 계층 및 링크-계층 터널링을 제안한다. 그러나 이러한 해결책은 제어 메시지가 상술한 바와 같은 데이터 메시지보다 더 높은 확률로 교환될 수 있는 비상주 링크 문제점을 해결하지는 않는다. 더욱이, 경로가 확립되면, 그러한 해결책은 경로가 고장이 난 후에야 링크 품질 저하를 검출한다.

따라서, 무선 네트워크, 특히 멀티-홉 네트워크에서 비상주 링크를 시의적절하고 정확한 방식으로 검출하여 최적의 링크를 선택할 수 있게 하는 대칭 링크 품질 평가를 제공하기 위한 시스템 및 방법이 필요하다.

각 도면에 걸쳐 비슷한 참조번호가 동일하거나 기능적으로 유사한 엘리먼트를 의미하는 첨부한 도면 및 이하의 상세한 설명은 본 명세서에 포함되고, 본 명세서의 일부분을 형성하며, 다양한 실시예를 설명하며, 본 발명에 따른 모든 다양한 원리 및 장점을 설명한다.

도 1은 본 발명의 실시예에 따른 시스템 및 방법에서 사용하는 복수의 노드를 포함한 예시적인 애드-혹 무선 통신 네트워크의 블록도이다.

도 2는 도 1에 도시한 네트워크에서 사용하는 이동 노드의 예를 나타내는 블록도이다.

도 3은 본 발명의 실시예에 따른 예시적인 네트워크를 나타내는 블록도이다.

본 기술분야의 숙련자는, 도면에서 엘리먼트는 간단하고 명확하게 예시하고, 반드시 크기 조절을 할 필요는 없다는 점을 인식한다. 예를 들어, 도면에서 일부 엘리먼트의 크기를 다른 엘리먼트에 관하여 확대해서 본 발명의 실시예에 대한 이해를 도울 수도 있다.

본 발명에 따른 상세한 실시예를 설명하기 전에, 실시예는 무선 멀티-홉 네트워크에서 비상주 링크를 검출하는 것에 관한 방법 스텝 및 장치 컴포넌트의 조합에 우선적으로 존재한다는 점을 알아야 한다. 따라서, 장치 컴포넌트 및 방법 스텝은 본 발명의 실시예를 이해하기 위한 특정 내용만을 도시하여 본 명세서의 내용에 관한 기술분야의 당업자에게 명백한 내용을 불명료하게 공개하지 않도록 도면에 종래의 심벌로 적절하게 표현한다.

본 명세서에서, 예컨대 제1 및 제2, 상 및 하 등의 관련 용어는 하나의 엔티티 또는 액션을 또 다른 엔티티 또는 액션과 단지 구별하는 데 사용할 수도 있고, 그러한 엔티티 또는 액션 간의 어떤 실제 관계 또는 순서를 반드시 요구 또는 포함하지는 않는다. 용어 "포함하다", "포함하는" 또는 그 용어의 다른 변종은 한정적이지 않게 포함하는 의도이고, 엘리먼트의 리스트를 포함하는 프로세스, 방법, 물품 또는 장치는 그러한 엘리먼트만을 포함하는 것이 아니라 그러한 프로세스, 방법, 물품 또는 장치에 대하여 명백하게 열거되거나 내재하는 다른 엘리먼트를 포함할 수도 있다. "…를 포함하는"으로 시작하는 엘리먼트는 제약이 없고, 그 엘리먼트를 포함하는 프로세스, 방법, 물품 또는 장치에 추가하는 동일한 엘리먼트의 존재를 배제하지 않는다.

본 명세서에서 기술하는 본 발명의 실시예는 하나 이상의 종래의 프로세서와, 어떤 비프로세서 회로와 함께 그 하나 이상의 프로세서를 제어하여 본 명세서에 기술한 멀티-홉 네트워크에서 비상주 링크를 검출하기 위한 시스템 및 방법의 기능 중 일부, 대부분 또는 전부를 구현하는 특유의 저장된 프로그램 명령으로 구성할 수도 있음을 인식하게 된다. 비프로세서 회로는 무선 수신기, 무선 전송기, 신호 드라이버, 클록 회로, 전원 회로 및 사용자 입력 디바이스를 포함할 수도 있지만, 이에 한정하지 않는다. 그와 같이, 이러한 기능은 멀티-홉 네트워크에서 비상주 링크를 검출하는 방법의 스텝으로서 해석할 수도 있다. 대안으로, 기능의 일부 또는 전부는 저장된 프로그램 명령이 없는 상태 머신에 의해, 또는 각 기능 또는 그 기능의 어떤 조합이 주문형 로직으로서 구현되는 하나 이상의 주문형 반도체(ASIC)에서 구현될 수 있다. 물론, 2가지 접근법의 조합을 사용할 수 있다. 그래서 이러한 기능을 위한 방법 및 수단을 본 명세서에 기술한다. 또한, 예를 들어 이용가능한 시간, 현재의 기술 및 경제적 사항에 의해 동기부여된 어떤 상당한 노력 및 많은 설계 선택임에도, 당업자가 본 명세서에 기술한 개념 및 원리에 따라 그러한 소프트웨어 명령 및 프로그램 그리고 IC를 최소한의 실험으로 용이하게 생성할 수 있다고 예상한다.

이제, 상세하게 설명하는 바와 같이, 본 발명은 시의적절하고 신뢰할 수 있는 방식으로 비상주 링크를 검출하는 시스템 및 방법을 제공한다. 구체적으로, 본 발명은 수신 측에서의 유니캐스트 데이터 타임아웃 측정에 따르는 메트릭을 도입한다. 이 메트릭은 노드 간의 링크 품질을 평가하는 기존의 해결책과 조합할 수 있 다. 더욱이, 본 발명은 송수신기가 패킷 완료율에 기초하여 링크 품질을 업데이트하여 비상주 링크 품질을 더욱 정밀하게 정량화할 때 패킷 크기를 고려한다.

이하에서, 본 명세서에 기술한 본 발명의 실시예에 따른 시스템 및 방법은 시의적절하고 정확한 방식으로 비상주 링크를 검출하여 대칭 링크 품질 평가를 제공할 수 있음을 인식하게 된다. 그 기법은, 본 명세서에 참조로서 포함하고, Avinash Joshi가 "System and Method For Achieving Continuous Connectivity to an Access Point or Gateway in a Wireless Network Following an On-demand Routing Protocol and to Perform Smooth Handoff of Mobile Terminals between Fixed Terminals in the Network"의 명칭으로 2004년 1월 13일에 출원한 미국특허 출원번호 제10/755,346호 및 공개번호 제2004/0143842호에 기술한 최적의 이웃 및 경로 선택을 위한 링크 품질 평가를 이용하는 해결책을 보완한다. 본 발명의 실시예는 전송기 위치에서의 계층 2(L2) 피드백(예를 들어, 응답 패킷으로부터 평가된 패킷 손실)과 함께 이용가능할 때 제어 및 데이터 패킷의 신호 세기를 이용한다. 원하는 신호 품질보다 낮은 제어 패킷을 거절하기 위한 기법의 예는, 본 명세서에 참조로서 포함하고, Lundgren H., Nordstrom E., 및 Tschudin C.가 "Coping with Communication Gray Zones in IEEE 802.11b based Ad hoc Networks"의 명칭으로 WoWMoM 2002에 공개한 문헌에서 기술한다. 그러나 그 기법은 이용가능한 경로만을 거절할 수 있기 때문에 연결성 문제가 있을 수 있다.

다중 액세스 충돌 회피(MACA: Multiple Access Collision Avoidance) 기법으로 알려진 또 다른 기법은, 본 명세서에서 참조로서 포함하고, Karn P.가 "MACA-a new channel access method for packet radio"의 명칭으로 ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL 1990에 공개한 문헌에서 기술한다. 그 문헌에서 기술한 기법은 이동 멀티-홉 네트워크용으로 이용하는 공통적인 기법이다. 그 기법은 송신 요구(RTS) 및 송신 허가(CTS) 메시지를 이용함으로써 패킷 충돌을 예방하는 예약 메시지를 이용한다. 송신기와 수신기 간의 전송은 RTS-CTS-DATA 메시지로 구성한다. MACAW(Multiple Access Collision Avoidance for Wireless)로 알려진 또 다른 기법은, 본 명세서에서 참조로서 포함하고, Bharghavan, V., Demers, A., Shenker, S., Zhang, L이 "MACAW: A media access protocol for wireless LAN's"의 명칭으로 Computer Communication Review, vol. 24, (no.4), (ACM SIGCOMM '94 Conference on Communications Architectures, Protocols and Applications, London, UK, 31 Aug. - 2 Sept. 1994) Oct. 1994. p.212-25에 공개한 문헌에서 기술한다. MACAW 기법은 데이터-송신(DS) 및 응답(ACK) 메시지를 도입하여 MACA를 확장함으로써 RTS-CTS-DS-DATA-ACK 메시지 교환 및 새로운 백오프 알고리즘을 형성한다. IEEE 802.11 MAC는 응답 메시지로 캐리어 감지 및 가상 (RTS-CTS 교환) 캐리어 감지 둘 다를 구현하여 신뢰성을 개선하는 CSMA/CA 프로토콜의 변종이다. 본 명세서에 기술한 본 발명의 실시예에 따른 기법은 모든 이러한 MAC 방식, 예를 들어 MACA, MACAW 및 802.11 MAC 프로토콜과 그 변종에 대하여 적용할 수 있다.

이제, 도면을 참조하면, 도 1은 본 발명의 실시예를 이용하는 애드-혹 패킷-스위치형 무선 통신 네트워크(100)의 예를 나타내는 블록도이다. 구체적으로, 네 트워크(100)는 복수의 이동 무선 사용자 단말기(102-1 내지 102-n)(일반적으로 노드(102) 또는 이동 노드(102)로서 간주함)를 포함하고, 노드(102)가 고정된 네트워크(104)에 액세스할 수 있게 하는 복수의 액세스 포인트(106-1, 106-2, 106-n)(일반적으로 노드(106) 또는 액세스 포인트(106)로서 간주함)를 구비한 고정된 네트워크(104)를 포함할 수 있지만, 이는 필수적이지 않다. 고정된 네트워크(104)는, 예를 들어 코어 LAN과, 네트워크 노드를 다른 네트워크, 예컨대 애드-혹 네트워크, 공중전화망 및 인터넷에 액세스할 수 있게 하는 복수의 서버 및 게이트웨이 라우터를 포함할 수 있다. 네트워크(100)는 복수의 고정된 라우터(107-1 내지 107-n)(일반적으로 노드(107) 또는 고정된 라우터(107)로서 간주함)를 더 포함하여 데이터 패킷을 다른 노드 102, 106 또는 107 사이에서 라우팅할 수 있다. 논의를 위하여, 상술한 노드는 집합적으로 "노드 102, 106 및 107" 또는 간단하게 "노드"로서 간주할 수 있음을 알아야 한다.

본 기술분야의 숙련자가 인식할 수 있는 바와 같이, 노드 102, 106 및 107은 서로 직접 통신할 수 있거나, 참조한 미국특허 출원번호 제09/897,790호, 제09/815,157호 및 제09/815,164호(미국특허번호 제7,072,650호, 제6,807,165호,제 6,873,839호)에서 기술한 바와 같이, 노드 사이에서 패킷을 송신하기 위한 라우터 또는 라우터들로서 작동하는 하나 이상의 다른 노드 102, 106 또는 107을 통해 통신할 수 있다.

도 2에 도시한 바와 같이, 각 노드 102, 106 및 107은, 안테나(110)에 연결하고, 패킷화된 신호와 같은 신호를 컨트롤러(112)의 제어하에 노드 102, 106 또는 107로부터/에 수신 및 전송할 수 있는 송수신기 또는 모뎀(108)을 포함한다. 패킷 화된 데이터 신호는, 예를 들어 음성, 데이터 또는 멀티미디어 정보, 그리고 노드 업데이트 정보를 포함한 패킷화된 제어 신호를 포함할 수 있다.

각 노드 102, 106 및 107은 다른 정보 중에서 네트워크(100)에 있는 그 자체 노드 및 다른 노드에 속한 라우팅 정보를 저장할 수 있는 RAM과 같은 메모리(114)를 더 포함한다. 도 2에 도시한 바와 같이, 노드, 특히 이동 노드(102)는 복수의 디바이스, 예컨대 노트북 컴퓨터 터미널, 이동 전화 유닛, 이동 데이터 유닛 또는 다른 적당한 디바이스로 구성할 수도 있는 호스트(116)를 포함할 수 있다. 각 노드 102, 106 및 107은 본 기술분야의 숙련자가 용이하게 인식할 수 있게 하기 위하여 인터넷 프로토콜(IP) 및 주소 결정 프로토콜(ARP)를 실행하는 적당한 하드웨어 및 소프트웨어를 또한 포함한다. 전송 제어 프로토콜(TCP) 및 사용자 데이터그램 프로토콜(UDP)을 실행하는 적당한 하드웨어 및 소프트웨어를 또한 포함할 수도 있다.

본 명세서에 기술한 접근법은 수신기에서의 L2 피드백(예컨대 CTS 송신 후의 데이터 타임아웃)을 이용하여, 오버헤드 및 지연을 도입하지 않으면서 비상주 링크를 검출하기 위한 평균 링크 품질 메트릭을 계산한다.

본 발명의 실시예를 설명하기 위하여 MACA 타입의 시스템을 사용한다. 송신기는 송신 요구(RTS) 메시지를 송신하여 전송 매체를 예약한다. 수신기는 송신 허가(CTS) 메시지로써 응답한다. RTS 및 CTS 메시지는 예약 채널(또는 다른 적합한 채널, 예컨대 데이터 채널)을 통해 전송하는 반면, 데이터 및 응답(ACK) 메시지는 동일한 채널 또는 상이한 데이터 채널을 통해 전송할 수도 있다. RTS 및/또는 CTS 를 경청하는 모든 노드는 대응하는 주소 및 채널을 전송에 요구되는 시간에 대하여 사용중인 것으로서 설정한다. 라우팅 프로토콜은 복수의 작은 크기의 브로드캐스트 및 유니캐스트 시스템 메시지를 이용하여 경로를 확립하는 리액티브, 프로액티브 또는 하이브리드 타입일 수 있다. 프로토콜은 경로를 확립하는 빠르고 큰 시스템 패킷을 전송해서는 안 되는데, 이는 효과적인 라우팅 방식을 위하여 중요하다. 그러나 이러한 타입의 라우팅 프로토콜은 비상주 링크에 의해 상당히 영향을 받아 데이터 손실은 심각하지만, 작은 메시지(예를 들어 송신 요구(RTS), 송신 허가(CTS) 및 헬로 메시지를 포함하는 제어 및 예약 메시지)는 여전히 성공적으로 교환할 수 있다.

본 발명의 시스템 및 방법은 CTS를 송신한 후 데이터 타임아웃을 카운트한다. 비상주 링크에서, RTS 및 CTS 완료율은 높을 수도 있지만, 데이터 완료율은 매우 낮을 수도 있다. 그러므로 경로가 확립된 후, 수신기는 많은 양의 데이터 타임아웃을 경험한다. 이 메트릭을 다른 신호 품질 측정에 통합하면, 수신기는 링크가 비상주 링크라는 점을 검출할 수 있다. 이 메트릭이 없으면, 수신기는 작은 제어 및 시스템 메시지 완료율이 낮지 않으므로, 그 링크를 양호한 링크로서 인지한다. 전송기가 인지된 링크 품질을 본 명세서에 참조로서 그 내용을 포함하고 있는 Avinash Josh 및 Guenael Strutt가 "System and Method for Characterizing the Quality of a Link in a Wireless Network"의 명칭으로 2004년 6월 7일에 출원한 미국특허 출원일련번호 제10/863,534호(미국특허출원공개번호 US20040246935A1, 2004년 12월 9일에 공개됨)에 기술된 바와 같이 전송하지 않으면, 수신기는 전송기 위치로부터의 유니캐스트 데이터 완료율을 평가할 수 없다. 그러나 이러한 정보의 전송은 오버헤드를 증가시킬 수도 있다. 더욱이, 이 정보를 전송하는 메시지 타입에 따라 이 패킷이 성공적으로 수신될 확률은 낮아질 수도 있다.

도 3에서, 본 발명의 장점을 설명하는 예시적인 시나리오를 나타낸다. N_1 내지 N_7은 도 1 및 2에 관하여 상술한 노드를 나타낸다. 이 예에서, N_1과 N_2 간의 링크는 비상주 링크 특성이 있다. N_2 및 N_1은 제어 메시지와 헬로 메시지를 높은 성공 확률로 수신할 수 있는 반면, 유니캐스트 데이터 전송은 심각한 패킷 손실이 있다. 예를 들어, N_1은 소스이고, N_4는 트래픽 세션을 위한 수신지이면, N_2 및 N_3 둘 다는 중간 중계 노드의 역할을 하는 양호한 후보이다. N_2로의 경로를 확립한 후, N_1은 L2 피드백(예컨대 No ACK)을 이용하여 링크 품질 메트릭을 감소시키고, 약간의 패킷 손실 후, N_3을 지나가는 또 다른 경로를 선택할 수 있다.

상술한 상황에 대한 기존의 해결책에서는 N_1에서 평가된 링크 품질 메트릭을 N_2에 송신한다. 그러나 N_1과 N_2 사이에서 대부분의 유니캐스트 데이터 전송이 성공적이지 않으므로, 이 메트릭이 데이터 메시지를 통해 송신되지 않으면, N_2가 업데이트된 링크 품질 메트릭을 갖게 될 확률은 낮다. 이 정보가 제어 메시지를 통해 송신되면, 802.11과 같은 표준과는 호환성이 없고, 오버헤드를 증가시킨다. N_2가 평가된 링크 품질 메트릭을 N_1에 대하여 시의적절하게 변경하면, 경로 변경은 더 빨라진다.

N_5가 N_6에 대한 경로를 설정하려고 할 때 N_2가 N_1을 그 다음 홉으로서 선택할 수 있으므로 또 다른 문제가 발생하는데, 이는 N_2가 N_2와 N_1 사이의 링 크에 대하여 여전히 양호한 뷰(view)를 갖기 때문이다(성공적인 제어 메시지에 기인함). 다시, N_1이 N_2에 데이터를 송신하기 시작할 때, N_2가 평가된 링크 품질 메트릭을 N_1을 위하여 변경하면, 최적 경로의 확립은 더 빨라진다. 본 발명으로 노드는 대칭 링크 품질 평가를 갖는 더 빠르고 신뢰할 수 있는 방식을 제공함으로써 비상주 링크 문제를 극복할 수 있다. 보완적인 기법으로서 다른 기존의 해결책과 조합할 수 있다.

이 메트릭의 통계는 노드, 채널 및 트래픽 특성의 다이내믹한 행동에 좌우된다. 그러므로 중요한 특징은 비상주 링크의 시간 범위를 반영하는 메트릭을 갖는다는 점이다. 그러므로 각 링크에 대한 마지막으로 업데이트된 시간은 본 명세서에 참조로서 포함하고 있는 P. Gupta 및 P. Kumar가 "A system and traffic dependent adaptive routing algorithm for ad hoc networks"의 명칭으로 IEEE Conference on Decision and Control 1997 문헌에서 제안한 바와 같이 이동 평균에 사용하기 위하여 유지할 수도 있다.

기존의 링크 품질 평가에 관한 다른 포인트는 상술한 내용으로부터 발견할 수 있다. 작은 패킷은 일반적으로 큰 패킷보다 더 높은 완료율을 갖는다. 그러나 송수신기는 다양한 패킷 크기를 구별하지 않으면서 패킷 완료율에 기초하여 링크 품질을 업데이트한다. 그러므로 본 발명에 따른 기법은 본 명세서에 참조로서 포함하고 있는 "System and method for providing adaptive control of transmit power and data rate in an ad-hoc communication network"라는 명칭의 미국 공개 특허 제2003/0189906호에서 제안한 현재의 링크 품질 평가를 확장하여 패킷 크기를 고려한다. 송신기 노드가 작은 패킷 전송의 성공을 검출할 때, 송신기 노드는 링크 품질을 작은 스텝만큼 증가시켜야 한다. 작은 패킷은 제어 메시지, 예약 메시지 또는 짧은 라우팅 패킷, 예컨대 RREQ, RREP 등일 수 있다. 예로서, 작은 패킷(제1 패킷)은 100 바이트보다 짧은 메시지일 수 있고, 큰 패킷(제2 패킷)은 100 바이트보다 큰 메시지일 수 있다. 그러나 작은 패킷(제1 패킷)의 크기는 100 바이트보다 작게만 한정하지 않고, 본 기술분야의 숙련자가 인식할 수 있을 때 큰 패킷(제2 패킷)으로서 생각할 수 있는 것과 비교하여 적합한 크기일 수 있다. 작은 스텝은 본 기술분야의 숙련자가 인식할 수 있을 때 큰 스텝으로서 간주하는 크기보다 작은 크기로서 간주할 수 있다. 전송기가 큰 전송(제2 전송)의 성공을 검출할 때, 전송기는 링크 품질을 큰 스텝(제2 량)만큼 증가시켜야 하는데, 큰 스텝은 본 기술분야의 숙련자가 인식할 수 있는 작은 스텝(제1 량)으로서 생각할 수 있는 것보다 큰 크기를 갖는 적합한 값일 수 있다. 이 업데이트는 각 노드의 전송기 및 수신기 둘 다에서 이루어진다.

유사하게, 전송의 실패가 검출될 때, 전송기 노드는 패킷 크기가 작을 때 링크 품질을 더욱 적극적으로 떨어뜨려야 한다. 수신기 측에서는, RTS가 패킷 크기를 전송하기 때문에, 수신기 노드는 패킷 크기 정보를 또한 얻을 수 있다. 데이터 패킷 타임아웃이 작은 패킷(제3 패킷)에 대하여 발생하면, 수신기 노드는 링크 품질에 더욱 적극적으로 패널티를 부과할 수 있다. 그러나 데이터 패킷 타임아웃이 큰 패킷(제4 패킷)에 대하여 발생하면, 수신기 노드는 링크 품질을 작은 스텝(제4 량)만큼 감소시키는데, 작은 스텝은 본 기술분야의 숙련자가 알 수 있는 큰 스텝(제3 량)으로서 생각할 수 있는 값보다 작은 적합한 값일 수 있다. 패킷 성공 및 실패에 대하여 링크 품질을 조절하는 스텝 크기의 값은 패킷 크기에 비례할 수 있다는 점을 또한 알게 된다. 예를 들어, 작은 패킷(예컨대, 100 바이트보다 작음)이 실패하면, 링크 품질은 X%만큼 떨어질 수 있다. 큰 패킷(예컨대, 500 바이트)이 실패하면, 링크 품질은 Y%만큼 떨어질 수 있고, 더 큰 패킷(예컨대, 1000 바이트)이 실패하면, 링크 품질은 Z%만큼 떨어질 수 있는데, 여기서 X＞Y＞Z이다. 즉, 링크 품질은 실패한 패킷 크기가 작을수록 더 큰 양만큼 떨어진다. 마찬가지로, 작은 패킷(예컨대, 100 바이트보다 작음)이 성공적으로 수신되면, 링크 품질은 A%만큼 업그레이드될 수 있다. 큰 패킷(예컨대, 500 바이트)이 성공하면, 링크 품질은 B%만큼 업그레이드할 수 있고, 더 큰 패킷(예컨대, 1000 바이트)이 성공하면, 링크 품질은 C%만큼 업그레이드할 수 있는데, 여기서 C＞B＞A이다. 즉, 링크 품질은 수신한 패킷 크기가 클수록 더 큰 양만큼 업그레이드한다. 그러므로 패킷 크기 요소는 비상주 링크가 얼마나 중요한지, 즉 링크의 비신뢰성 레벨을 반영하고, 링크 품질 평가를 더 빠르게 수렴할 수 있게 한다. 그래서 본 발명은 패킷 크기를 링크 품질 평가에 대한 패킷 완료율에 따른 피드백으로서 이용하여 실제의 링크 품질을 더 빠르게 평가한다. 상술한 작동, 예컨대 데이터 패킷 전송의 성공 또는 실패 검출, 링크 품질의 업데이트 및 링크가 비상주 링크인지 여부에 관한 판정은 전송 또는 수신 노드, 또는 둘 다의 컨트롤러(112)에서 실행할 수 있고, 또는 다른 적합한 조합으로 실행할 수 있다. 전송 노드, 수신 노드 또는 둘 다에 존재하는 컨트롤러(112) 또는 다른 적합한 컴포넌트는 그러한 작동을 실행하기 위한 "컨트롤러"로서 집합적으로 간주하고, 용어 "컨트롤러"는 전송 및 수신 노드의 컨트롤러(112) 또는 다른 적합한 컴포넌트를 의미하고, 전송 및 수신 노드 각각의 개별 컨트롤러(112) 또는 다른 컴포넌트는 전송 노드 컨트롤러 및 수신 노드 컨트롤러로서 간주할 수 있다.

수신기 기반의 링크 품질 메트릭 평가는 적응 전송 프로토콜의 성능을 향상시킨다. 예컨대, 상이한 패킷 크기에 대한 수신 성공률을 시의적절하게 평가한 수신기는 그 비율, 단편화 및 파워 레벨을 조절하는 전송기에 알려준다.

상술한 명세서에서는 본 발명의 특정 실시예를 기술한다. 그러나 본 기술분야의 숙련자는 본 발명의 범위를 벗어나지 않으면서 이하의 청구범위에서 설명하는 바와 같이 다양한 수정 및 변경이 이루어질 수 있다는 점을 이해한다. 따라서, 명세서 및 도면은 제한적이기보다는 예시적이고, 모든 그와 같은 수정은 본 발명의 범위 내에서 이루어진다. 이점, 장점, 문제점에 대한 해결책 그리고 이점, 장점 또는 해결책을 야기하거나 더욱 명백하게 할 수도 있는 구성요소는 청구범위의 중요하고, 필수적이거나 본질적인 특징 또는 구성요소로서 해석하지는 않는다. 본 발명은 본 출원이 계류중인 동안 이루어지는 보정을 포함하는 청구범위 및 등록된 청구범위의 모든 동등물에 의해서만 정의한다.

Claims

무선 네트워크에서 비상주 링크(a transient link)를 검출하기 위한 방법으로서,

요구(request)를 성공적으로 통신하여 전송 노드로부터 수신 노드로 메시지를 송신하고 클리어(clear)를 성공적으로 통신하여 수신 노드로부터 전송 노드로 메시지를 보내는 것에 의해, 전송 노드와 수신 노드 사이에서 링크 및 루트를 확립하는 단계,

루트 상의 전송 노드와 수신 노드 사이에서 데이터를 전송하는 단계,

성공 및 실패 데이터 전송들을 카운트하고 수신 노드에서 발생하는 데이터 타임아웃들을 카운트하여 데이터 완료율을 결정하는 것을 포함하여 제어 및 시스템 메시지들에 대한 루트 상에서의 완료율을 결정하는 단계, 및

데이터 완료율이 적어도 특정 값만큼 제어 및 시스템 메시지들에 대한 완료율보다 낮을 때 루트를 비상주 링크로 판정하는 단계

를 포함하는 방법.
제1항에 있어서,

상기 카운트하는 것은, 데이터 타임아웃들을 카운트하기 위해 전송 노드 및 수신 노드 중 적어도 하나를 제어하는 것을 포함하는 방법.
제2항에 있어서,

상기 제어하는 것은, 데이터 타임아웃들을 카운트하기 위해 전송 노드 및 수신 노드를 제어하는 것을 포함하는 방법.
제1항에 있어서,

데이터 타임아웃들의 카운트된 수에 적어도 부분적으로 기초하여 링크의 품질을 평가하는 단계, 및

링크의 품질을 데이터 완료율을 결정하는 데에 포함시키는 단계

를 더 포함하는 방법.
제4항에 있어서,

링크의 품질 값에 적어도 부분적으로 기초하여 비상주 링크의 비신뢰성 레벨(a level of unreliability)을 결정하는 단계

를 더 포함하는 방법.
제4항에 있어서,

데이터 타임아웃들의 카운트된 수 및 타임아웃이 발생하는 데이터 패킷들의 개별 크기들에 적어도 부분적으로 기초하여 링크의 품질을 나타내는 품질 값을 조절하는 단계

를 더 포함하는 방법.
제6항에 있어서,

각각의 데이터 전송 성공에 대해서,

상기 조절 단계는, 제1 데이터 패킷에 대하여 품질 값을 제1 량만큼 조절하고, 제1 데이터 패킷보다 크기가 큰 제2 데이터 패킷에 대하여 제1 량보다 큰 제2 량만큼 조절하고,

각각의 데이터 전송 실패에 대해서,

상기 조절 단계는, 제3 데이터 패킷에 대하여 품질 값을 제3 량만큼 조절하고, 제3 데이터 패킷보다 크기가 큰 제4 데이터 패킷에 대하여 제3 량보다 작은 제4 량만큼 조절하는

방법.
제6항에 있어서,

상기 조절 단계는 전송 노드에 의해 송신되는 송신 요구(RTS) 메시지에 포함된 정보에 적어도 부분적으로 기초하여 개별 데이터 패킷의 개별 크기를 결정하는 것을 더 포함하는

방법.
무선 네트워크에서 비상주 링크를 검출하기 위한 시스템으로서,

전송 노드 및 수신 노드 - 전송 노드는 수신 노드에 데이터를 전송함 -,

요구를 성공적으로 통신하여 전송 노드로부터 수신 노드로 메시지를 송신하고 클리어를 성공적으로 통신하여 수신 노드로부터 전송 노드로 메시지를 보내는 것에 의해 확립된, 전송 노드와 수신 노드 사이의 링크와 루트, 및

성공 및 실패 데이터 전송들을 카운트하고 수신 노드에서 발생하는 데이터 타임아웃들을 카운트하여 데이터 완료율을 결정하는 것을 포함하여 제어 및 시스템 메시지들에 대한 루트 상에서의 완료율을 결정하며, 데이터 완료율이 적어도 특정 값만큼 제어 및 시스템 메시지들에 대한 완료율보다 낮을 때 루트를 비상주 링크로 판정하기 위한 컨트롤러

를 포함하는 시스템.
제9항에 있어서,

컨트롤러는 전송 노드에 배치된 전송 노드 컨트롤러 및 수신 노드에 배치된 수신 노드 컨트롤러 중 적어도 하나를 포함하여 데이터 타임아웃들을 카운트하는

시스템.
제10항에 있어서,

컨트롤러는,

전송 노드에 배치된 전송 노드 컨트롤러, 및

수신 노드에 배치된 수신 노드 컨트롤러

를 포함하고,

전송 노드 컨트롤러 및 수신 노드 컨트롤러의 각각은 데이터 타임아웃들을 카운트하는

시스템.
제9항에 있어서,

컨트롤러는, 데이터 타임아웃의 카운트된 수에 적어도 부분적으로 기초하여 링크의 품질을 평가하고, 링크의 품질을 데이터 완료율을 결정하는 데에 포함시키는

시스템.
제12항에 있어서,

컨트롤러는 링크의 품질 값에 적어도 부분적으로 기초하여 비상주 링크의 비신뢰성 레벨을 결정하는

시스템.
제12항에 있어서,

컨트롤러는 데이터 타임아웃들의 카운트된 수 및 타임아웃이 발생하는 데이터 패킷들의 개별 크기들에 적어도 부분적으로 기초하여 링크의 품질을 나타내는 품질 값을 조절하는

시스템.
제14항에 있어서,

각각의 데이터 전송 성공에 대해서,

컨트롤러는, 제1 데이터 패킷에 대하여 품질 값을 제1 량만큼 조절하고, 제1 데이터 패킷보다 크기가 큰 제2 데이터 패킷에 대하여 제1 량보다 큰 제2 량만큼 조절하고,

각각의 데이터 전송 실패에 대해서,

컨트롤러는, 제3 데이터 패킷에 대하여 품질 값을 제3 량만큼 조절하고, 제3 데이터 패킷보다 크기가 큰 제4 데이터 패킷에 대하여 제3 량보다 작은 제4 량만큼 조절하는

시스템.
제14항에 있어서,

컨트롤러는 전송 노드에 의해 송신되는 송신 요구(RTS) 메시지에 포함된 정보에 적어도 부분적으로 기초하여 개별 데이터 패킷의 개별 크기를 결정하는

시스템.
무선 네트워크 내에서 동작하는 노드로서,

요구를 성공적으로 전송하여 다른 노드로 메시지를 송신하고,

클리어를 성공적으로 수신하여 다른 노드로부터 메시지를 송신하여 확립된 루트를 따라 무선 네트워크에서 다른 노드에 데이터를 전송하는 송수신기, 및

성공 및 실패 데이터 전송들을 카운트하고 다른 노드에서 발생하는 데이터 타임아웃들을 카운트하여 데이터 완료율을 결정하는 것을 포함하여 제어 및 시스템 메시지들에 대한 루트 상에서의 완료율을 결정하며, 데이터 완료율이 적어도 특정 값만큼 제어 및 시스템 메시지들에 대한 완료율보다 낮을 때 루트를 비상주 링크로 판정하는 컨트롤러

를 포함하는 노드.
제17항에 있어서,

컨트롤러는, 데이터 타임아웃들의 카운트된 수에 적어도 부분적으로 기초하여 링크의 품질을 평가하고, 링크의 품질을 데이터 완료율을 결정하는 데에 포함시키는

노드.
제17항에 있어서,

컨트롤러는 데이터 타임아웃들의 카운트된 수 및 타임아웃이 발생하는 데이터 패킷의 개별 크기에 적어도 부분적으로 기초하여 링크의 품질을 나타내는 품질 값을 조절하는

노드.
제19항에 있어서,

각각의 데이터 전송 성공에 대해서,

컨트롤러는, 제1 데이터 패킷에 대하여 품질 값을 제1 량만큼 조절하고, 제1 데이터 패킷보다 크기가 큰 제2 데이터 패킷에 대하여 제1 량보다 큰 제2 량만큼 조절하고,

각각의 데이터 전송 실패에 대해서,

컨트롤러는, 제3 데이터 패킷에 대하여 품질 값을 제3 량만큼 조절하고, 제3 데이터 패킷보다 크기가 큰 제4 데이터 패킷에 대하여 제3 량보다 작은 제4 량만큼 조절하는

노드.