KR20020012264A

KR20020012264A - 메시형 무선 네트워크의 패킷 데이터용 통신 프로토콜

Info

Publication number: KR20020012264A
Application number: KR1020017015785A
Authority: KR
Inventors: 아론손이타이; 워포크패트릭에이
Original assignee: 추후보정; 칼리 코포레이션
Priority date: 1999-06-08
Filing date: 2000-06-05
Publication date: 2002-02-15
Anticipated expiration: 2020-06-05
Also published as: EP1059773A2; US6363062B1; CN1354924A; DE60039004D1; CA2376183A1; EP1059773B1; ATE397341T1; CN1145278C; IL146722A; WO2000076088A1; KR100447302B1; TW484277B; IL146722A0; EP1059773A3; JP2003501941A

Abstract

프로토콜의 일부는 네트워크(11)의 모든 상호 통신 노드(12∼19)에서 유지되는 제어 채널의 세션의 스케줄을 사용하여 동기화되고 프로토콜의 일부는 요청된 데이터의 전송을 위해 제어 채널 세션 사이의 갭에 응답하여 비동기화된다. 유휴 상태로부터, 노드(A)는 노드 스케줄 내의 프리 타임에 대한 정보를 포함하는 RTS(ready to send) 메시지를 노드(B)에 전송한다. 인접 노드(B)는 일부의 상호 동의될 수 있는 시간에 전송을 허용하는 CTS(clear to send) 메시지를 노드(A)에 전송한다. 인접 노드(B)는 인접 노드의 스케줄되지 않은 시간에 대한 정보를 포함하는 RTS 메시지를 노드(A)에 전송한다. 노드(A)는 일부의 상호 동의될 수 있는 시간에서 전송을 허용하는 CTS 메시지를 인접 노드(B)에 전송한다. 데이터 전송을 위한 포텐셜 스케줄은 공지의 제어 채널 세션 사이의 이용 가능한 갭의 개수를 포함한다.

Description

메시형 무선 네트워크의 패킷 데이터용 통신 프로토콜{COMMUNICATIONS PROTOCOL FOR PACKET DATA PARTICULARLY IN MESH TOPOLOGY WIRELESS NETWORKS}

복수의 기가헤르쯔(GHz) 스펙트럼에서 동작하는 광대역 무선 네트워크는 다양한 위치에 있는 고객에게 다양한 서비스를 전달할 능력을 갖고 있다. 고주파수 스펙트럼에 의해 네트워크의 공간 영역마다 광대역폭을 사용하여 높은 수용 능력을 갖는 무선 네트워크의 배치가 가능하다. 이전에는, 텔레비젼 대역, 아마튜어 무선 대역, 항공 대역 등과 같은 개별적인 서비스 또는 사용을 위해 무선 스펙트럼이 허용되었다. 각각의 대역 내에서, 대역 내의 모든 사용자가 허용되도록 개별적인 사용자들이 링크 베이시스로 허용되었다. 1998 년에, FCC(Federal Communication Commission)는 이러한 방법으로부터 벗어나서 LMDS(Local Multipoint Distribution Systems)(지역 다지점 분배 시스템)에 사용하기 위해 27 GHz∼31 GHz 대역의 대규모 무선 스펙트럼을 제공하였다. 이와 유사한 스펙트럼 대역이 캐나다, 오스트레일리아, 뉴질랜드 및 아르헨티나에서 사용되도록 개설되었다. 유럽에서는 24.5∼26.5 GHz의 무선 스펙트럼이 또한 다지점 사용을 위해 할당되었다. 많은 국가들이 링크베이시스 보다는 영토 베이시스로 사용하기 위해 10 GHz∼40 GHz 사이의 고주파수 스펙트럼의 다양한 대역을 개설하는 과정에 있다. 무선 스펙트럼을 허용하는 해결책(영토 VS 링크)의 이러한 주요한 차이로 광대한 지역적 영역을 망라하고 이러한 영역에서 가시선(line of sight) 관계에 있는 고객에게 접속 서비스를 제공하는 네트워크를 네트워크 운영자가 구성할 수 있다. 이것은 밀리미터파 전송은 통신하는 송신기와 수신기 사이의 가시선에 달려있기 때문이다.

1988년 이후 새로운 관리 제도가 지점 대 다지점의 무선 시스템의 개발에 의해 유도되었다. 이러한 시스템은 고객의 송수신기가 기지국의 영역 안테나를 향하는 고객을 포함하는 영역으로 분할된 셀을 포함하는 영역 전송기 및 수신기를 갖는 기지국을 기초로 한다. 이러한 고객들은 정보 방송 다운스트림을 기지국으로부터 수신하여 그들에게 전달된 정보를 선택한다. 업스트림 측에서, TDMA(시분할 다중 액세스) 모드로, 기지국은 시간 슬롯, 또는 FDMA(주파수 분할 다중 액세스) 모드로 주파수 슬롯을 원거리 고객의 각각의 송수신기에 할당하여 고객에게 전달될 필요가 있는 정보의 양을 기초로 하여 정보의 폴링을 허용한다.

데이터 통신 프로토콜은 '계층'으로 알려져 있는데, 왜냐하면 각각의 계층이 통신 시스템의 레벨이기 때문이고, 이러한 통신 시스템은 자체적인 규칙과, 때때로 유일한 관심이 상기 레벨의 동작에 관한 것인 사람을 갖고 있다. '계층' 이라는 개념은 많은 데이터 통신 텍스트에서 설명되고 다음과 같이 요약될 수 있다. 하드웨어로 시작되고, 가장 낮은 계층으로 고려되는 무선 통신을 가능하게 하는 장치는 "물리적 계층"으로 알려져 있고, 반면에 소비자에 의해 운영되는 어플리케이션인 가장 높은 계층은 "응용 계층"으로 알려져 있다. 물리적 계층 바로 위는 에러없이 데이터 전송을 관리하는 "링크 계층"이다. 그 다음은, 경로 설정 기능을 수행하여 네트워크를 결합시키는 "네트워크 계층" 이다. 그 다음은, 네트워크 계층에 어드레스를 제공하고 데이터가 전송되는 유닛의 크기를 결정하는 "전송 계층" 이다. 다음에는, 단자들 사이의 "개시" 및 "종료" 등과 같은 명령을 배열하는 "세션 계층" 이다. 어플리케이션 계층 바로 아래이고 세션 계층 위에는 "프리젠테이션 계층"으로 표현되는 데이터의 포맷을 정의하고, 다양한 단자들의 요구 사항의 차이를 극복할 수 있다. 무선 네트워크에서는 부가적인 계층인 "매체 접근 제어 계층", 즉 MAC 계층이 존재하여, 네트워크 상의 상호 결합된 노드의 송수신기 사이의 데이터 통신을 위한 프로토콜로서 네트워크 형태 내에서 사용된다. 전술된 계층 체계에서, MAC 계층은 물리적 계층과 링크 계층 사이에 존재하여, 2 개의 계층 사이의 인터페이스로서 작용한다. 과거에는, 지점 대 다지점(PMP) 셀룰러 시스템을 위한 매체 접근 제어(MAC) 계층은 비교적 간소했고 그라운드에서 셀룰러 이동 시스템 및 광대역 시스템 뿐만 아니라 위성에서 그라운드(VSAT) 시스템 같은 많은 무선 시스템에서 사용되었다.

MAC 계층을 갖는 지점 대 다지점(PMP) 네트워크의 장점은 간소성이다. PMP 시스템의 제1의 단점은 다운스트림 링크의 방송 특성 및 업스트림 링크의 폴링 때문에 발생한다. 기지국이 특정 주파수 및 타임 슬롯(TDMA)으로 전송할 때, 정보를 수신하는 사람을 제외한 영역 내의 모든 고객들은 임의의 정보 수신으로부터 차단된다. 업스트림 방향으로, 단지 한명의 고객이 특정 시간에 특정 주파수로 전송할수 있다. 이와 같이, 영역 내의 고객의 수가 증가할 때, 고객 마다 이용가능한 평균 데이터율은 감소한다.

PMP 시스템의 제2의 단점은 모든 고객에게 뛰어난 가시선을 제공할 수 있는 높은 위치에 값 비싼 기지국을 설치할 필요성이 있다는 점이다. 이러한 시스템은 선행 투자를 필요로 한다.

PMP 시스템의 제3의 단점은 PMP MAC 계층의 셀룰러 특성으로부터 발생된다. 노드는 이러한 노드의 기지국 영역의 송수신기와 통신만을 할 수 있어서, 반복 또는 경로 설정의 다양성이 발생할 수 없다. 만약 가시선이 기지국으로부터 가입자 유닛에 존재하지 않는다면, 모든 고객이 접속될 수 있도록 새로운 기지국이 건설되어야 할 것이다.

G. Flammer에 의한 미국 특허 공보 5,903,566호에는 블록으로 대량의 데이터 파일을 전송하기 위한 멀티 노드 메시형의 무선 네트워크가 개시되어 있다. 전송 프로토콜은 요청된 코드 블록의 유효성의 확인을 수반한다. 무효 블록에 대해, 소스 노드는 패킷 전송 버퍼를 프리 상태로 하고 프로세스는 종료된다. 유효 블록에 대해, 소스 노드는 블록을 수신지 노드에 전송한 후, 패킷 전송 버퍼를 프리 상태로 하고 프로세스는 종료된다. 블록 전송의 통신 프로토콜은 지정되지 않는다.

본 발명은 무선 통신 방법(wireless radio communications method)에 관한 것으로, 특히 네트워크 노드 사이의 패킷 데이터 통신 방법에 관한 것이다.

도 1은 본 발명을 이용하는 완전히 접속된 메시형 네트워크의 도면.

도 2는 단일 제어 채널의 마이크로슬롯 내의 본 발명에 따른 데이터 통신 프로토콜을 도시하는 2 개의 노드 사이의 신호 세션도.

도 3은 도 2에 도시된 제어 채널의 로직에 대한 상태 머신도.

도 4a 및 도 4b는 2 개의 노드 사이에 존재하는 도 2에 도시된 종류의 복수의 마이크로슬롯의 관계를 도시하는 2 개의 노드 사이의 신호 전송도.

도 5는 평균 지연 시간 VS 갭의 그래프.

도 6은 본 발명을 이용하는 트리 구조 네트워크의 도면.

케이블 어플리케이션에서, 메시형의 네트워크는 n 개의 노드 때문에, 모든 노드를 결합시키는 데에 n(n-1)/2 개의 회로가 필요하여 회피된다. 그러나, 특히, 데이터 패킷이 IP(인터넷 프로토콜) 네크워크에서와 같은 데이터 전송을 위해 사용될 때, 메시형의 네트워크가 광대역 무선 어플리케이션에 이상적이다. 본 발명은 특히, 메시형 네트워크 또는 다른 형태의 네트워크에서 패킷 베이시스로 효율적인 데이터 전송이 가능하도록 설계된 새로운 형태의 공간 및 시간으로 스위칭된 MAC 계층 프로토콜에 관한 것이다.

메시형 네크워크의 장점은 다음과 같다: (1) 메시형 네트워크는 노드 사이의 정보 반복을 허용하여 가시선(LOS) 통신이 확립될 수 있는 영역 내의 다른 노드를 통해 고객과 백본 접속점(BAP)(backbone access point) 사이의 신뢰할 수 있는 접속이 가능하여, 관련된 영역의 보다 높은 커버리지를 달성할 수 있다. (2) 메시형 네트워크는 고객들을 중심으로 구성된다. 네트워크에 결합되는 노드(고객)의 수가 증가할 때, 데이터 흐름을 위한 다수의 병렬 경로의 생성으로 인하여 이러한 메시형 네트워크의 대역폭의 용량은 증가한다. (3) 노드에서 다른 노드로의 다수 경로의 이용성으로, 경로의 다양성과 로드의 균형이 가능하다.

이러한 시스템을 구현하는 어려움으로 이용 가능한 가시 거리 및 이용 가능한 링크 뿐만 아니라 다른 노드에서 개시되고 종료되는 버스트 데이터 트래픽으로부터의 가능성 있는 간섭을 갖는 관련된 위치를 기초로 하여, 노드 사이의 데이터 전송을 제어하고 동기화하기 위한 알고리즘을 가질 필요성이 있다는 점이다. IP 형태의 네트워크에서, 데이터 패킷은 랜덤한 발신지 및 수신지 셀로 랜덤하게 생성된다. 이와 같이, 최적의 트래픽 조정이 패킷 베이시스로 패킷 상에서 조절되어야 할 것이다. 이에 부가하여, 물리적으로 결합된 섬유 네트워크 또는 동선 네트워크와는 대조적으로, 무선 메시형 네트워크는 다수의 빔을 갖는 송수신기 및 지향성 안테나를 갖고 그것들 사이에 스위칭 할 능력을 갖고 있다. 이와 같이, 공간 및 시간으로 스위칭되는 MAC 알고리즘은 상이한 노드 사이의 전파 지연과, 각각의 노드에서 다양한 어드레스를 갖는 데이터의 대기 행렬과, 다수의 노드로부터의 전송 시간의 동기화와, 수신지 노드의 위치를 기초로 하여 상이한 지연을 갖는 다수의 다양한 노드에서의 수신 시간을 고려해야 할 것이다.

본 발명은 피어 투 피어(peer-to-peer) 통신 뿐만 아니라 노드-to-BAP 통신 및 BAP-to-노드 통신의 네트워크 노드 사이의 IP 형태의 데이터 패킷 흐름을 갖는 메시형 네트워크의 구현을 효율적으로 허용하도록 적합한 공간 및 시간으로 스위칭된(STS) MAC 프로토콜을 설계하는 것을 특징으로 한다. 메시형 네크워크는 동일한 주파수로 동작하는 TDD(시분할 이중화) 방식으로 동작될 수 있고 상이한 링크에서 동시에 다양한 주파수로 동작될 수 있다. STS MAC 프로토콜은 트래픽 로드를 기초하여 용량을 배당한다.

본 발명에 따른 STS MAC 프로토콜의 기본 원리는 노드 사이의 제어 채널로서 동기식 스케줄 정보를 사용하여, 스케줄 정보 시간 슬롯 사이에 비동기식 가변 길이 데이터 패킷을 배당한다. 이용 가능한 데이터 슬롯은 개시자에 의한 요구 시간 슬롯과 수신자의 이용 가능한 시간 슬롯을 기초하여 각각의 수신자 노드에 의해 데이터 개시자 노드에 적합하게 배당된다.

본 발명의 적합한 STS MAC 프로토콜은 다음과 같은 구조를 갖는 네트워크에서의 고대역폭의 통신을 효율적으로 지원하도록 설계된다: (1) 부분적으로(또는 완전하게) 접속된 메시형을 형성하는 어느 정도의 무선 접속성을 갖는 노드. (2) 무선 메시형 네트워크를 IP 백본(backbone)에 접속시키는 백본 접근점(BAP)으로 공지된 한개 또는 그 이상의 특별 노드.

네크워크 내의 노드는 다음과 같은 능력을 갖고 있다: (1) 각각의 노드는 수신 및 전송 방향의 빔 안테나를 0 개 또는 1 개 또는 그 이상의 고정된 수의 영역으로 돌릴 수 있다. (2) 상이한 영역에 도달한 신호는 서로 간섭하지 않는다. (3) 통신은 반이중 통신이고 노드는 한번에 하나의 영역에서만 통신할 수 있다.

본 발명의 적합한 STS MAC 알고리즘은 다수의 네트워크 노드에서 개시되는 순간적인 버스트 패킷 트래픽 로드를 기초하고 다수의 가변 수신지 어드레스를 갖는 네트워크 내의 서브 그룹과 동등한 노드 사이에 다수의 동시 전송 링크를 생성할 수 있어, 공간으로 커버되는 소정의 영역에서의 스펙트럼의 효율적인 사용, 경로 다양성 및 패킷으로 운송되는 정보에 대한 로드 균형의 급격한 증가를 허용한다.

도 1을 참조하면, 무선 메시형의 네트워크(11)는 완전히 상호 결합된 가시선 노드(12∼19)를 갖고 있다. 본 발명에서, 동일한 베이시스로 네트워크의 나머지 노드와 가시거리 내 통신을 하는 적어도 하나의 인접 노드와 노드가 가시거리 내 통신을 하는 한 모든 노드가 상호 접속될 필요는 없다. 노드 사이의 통신은 본 발명의 STS MAC 프로토콜 방법을 사용하는 패킷에 의한다. 프로토콜의 기본적인 특징은 다음과 같다. 시간은 공지된 길이의 프레임으로 분할된다. 각각의 프레임에서, 모든 노드는 각각의 인접 노드와 제어 정보를 교환하기 위한 스케줄링된 슬롯, 즉 제어 채널을 갖고 있다. 노드가 제어 채널의 전송 또는 수신에 관여하지 않을때에는 데이터 패킷의 전송 또는 수신을 스케줄링하지 않을 것이다. 제어 채널의 일부로서, 비트를 전송하기 위한 요청이 이루어진다. 요청의 일부로서, 요청 노드의 데이터 채널내의 스케줄링되지 않은 기간, 즉 이용 가능한 시간에 대한 정보가 전송된다. 전송 요청(RTS)을 수신하는 노드는 전송을 허용하거나 또는 부인한다. 허용의 일부는 데이터를 전송할 때 요구자의 스케줄로부터 선택된 스케줄을 포함한다.

STS MAC 계층의 개략

MAC 계층은 페이로드 데이터 유닛(PDU)을 생성하고 소비하는 링크 계층과, 실제적인 전송을 담당하는 물리적 계층 사이의 인터페이스이다. MAC 프로토콜의 일반적인 원리는 데이터 전송을 스케줄링하기 위해 각 쌍의 인접 노드가 규칙적인 베이시스로 제어 정보를 전달해야 한다는 것이다. 이와 같이, 우리는 프레임의 개념을 갖는다. 모든 프레임 중에, 노드는 각각의 인접 노드와 통신하여 전송 요청(RTS)하고 전송 소거(CTS)(clear to send)를 허용한다. 이러한 제어 정보를 전송하고 수신하는데 소비된 시간은 제어 채널로 불린다. 데이터 전송은 프레임에 걸쳐 뒤섞여 제어 채널을 회피한다. MAC 스케줄링의 성능은 다음과 같은 요인에 달려있다: (1) 프레임의 길이. (2) 제어 채널에 의해 차지되는 프레임의 퍼센트. (3) 제어 채널 주변의 데이터 스케줄링의 효율성. (4) 인접 노드 사이의 데이터 전송 스케줄링의 효율성.

제어 채널

각각의 프레임 내에서, 각각의 노드는 각각의 인접 노드와 통신해야 한다. 기본적인 아이디어는 전송이 이루어질 수 있을 때에 대한 몇몇의 정보를 수반하여, 전송 요청이 이루어진다는 것이다. 그후, 포텐셜 수신기는 모든 요청 또는 일부의 요청을 허용하거나 또는 어떠한 요청도 허용하지 않아야 한다. 각각의 인접 노드와 발생될 필요가 있는 기본적인 통신은 다음과 같다:

노드의 스케줄에서의 프리 타임에 대한 정보를 갖는, 인접 노드에 대한 RTS 메시지.

일부의 상호 동의될 수 있는 시간에 전송을 허용하는 인접 노드로부터의 CTS 메시지.

인접 노드의 스케줄링되지 않은 시간에 대한 정보를 갖는 인접 노드로부터의 RTS 메시지.

일부의 상호 일치될 수 있는 시간에 전송을 허용하는 인접 노드에 대한 CTS메시지.

이러한 교환은 세션으로 불리고 도 2에 도시되어 있다.

도 2를 참조하면, 세션의 길이는 화살표(L)에 의해 표시되고 수평선에 의해 표시된 노드 A 및 B와 동일하지만, 대각선의 화살표(D,E,F)에 의해 나타낸 전파 지연에 의해 오프셋된다. 제1의 RTS를 B 노드에 전송하는 것을 보여주기 위해 화살표 D로 나타낸, A 노드는 개시자이고 데이터에 이용 가능한 시간에 대한 A 노드의 스케줄을 운송한다. 그 다음, 동의된 시간으로 B 노드로부터 A 노드로 CTS 전송이 잇따른다. 그후, B 노드는 A 노드에 데이터에 이용 가능한 시간의 스케줄과 함께 RTS를 전송한다. 화살표 F는 요청된 데이터의 전송에 대한 동의된 시간으로 A 노드에 의한 승인을 나타낸다.

도 3에서, 제어 채널의 로직에 대한 기본적인 상태 머신은 유휴 상태(27)에 대한 2 개의 루프(23,25)를 갖고 있다. 유휴 상태로부터, CTS 메시지를 갖는 B 노드에 의해 A 노드로 전송된 동의된 전송 시간으로 승인을 위해 RTS 스케줄이 판독되는 대기 상태(22)에 의해 나타내었듯이, A 노드는 RTS 메시지를 B 노드에 전송한다. 그후, 전송은 상태(24)에 의해 나타낸 바와 같이, A 노드에 의해 스케줄링된다. 또한, 노드 B는 노드 A에 대한 요청으로 이용 가능한 스케줄링되지 않은 갭을 리스트하고, 상태(26)에 의해 나타낸 바와 같이 노드 A는 스케줄링 알고리즘을 개시하고, 스케줄을 디벨로프하고 상태(28)에 의해 나타낸 바와 같이 CTS 메시지를 노드 B에 전송한다. 이러한 시퀀스는 모든 인접 노드 사이에서 실행된다. 노드 A와 노드 B 사이의 세션의 길이는 다음 항목의 합이다:

1. 개시자인 A 노드로부터 수신자인 인접의 B 노드로의 RTS 메시지의 전파 지연.

2. 전체의 RTS 패킷이 도달하는데 발생하는 전송 지연.

3. 인접 노드가 RTS를 스케줄링하는데 걸리는 프로세싱 시간.

4. 인접의 B 노드로부터 개시자인 A 노드로 되돌아가는 CTS 메시지의 전파 지연.

5. 전체의 CTS 메시지가 도달하는데 발생하는 전송 지연.

6. 전체의 RTS 메시지가 도달하는데 발생하는 전송 지연.

7. 개시자가 인접의 B 노드의 RTS를 스케줄링하는데 걸리는 프로세싱 시간.

8. 전체의 CTS 패킷 전송의 전송 지연.

RTS 및 CTS 메시지가 동일한 길이를 갖는다면, 세션의 길이는:

4 제어 패킷(메시지) 길이 + 2 전파 지연 + 2 처리 시간.

모든 노드는 프레임마다 각각의 인접 노드와 적어도 하나의 세션을 가져야하고 어떠한 세션도 오버래핑 될 수는 없다. 세션은 고정된 스케줄에서 발생한다. 글로벌 스케줄링 알고리즘에 의해 전체의 네트워크에 대한 이러한 스케줄이 결정된다. 이러한 알고리즘에서, 다음과 같이 가정된다: 네트워크의 형태가 공지된다. 인접 노드 사이의 전파 지연이 공지된다. 프로세싱 시간이 일정하다. 네트워크 내의 각각의 노드의 세션에 대한 스케줄이 컴퓨팅되어 각각의 노드에 분배된다. 노드의 형태가 변화할 때, 예를 들어 노드의 승인 또는 이탈로 인하여 새로운 세션 스케줄이 컴퓨팅되어, 메시형 네트워크의 모든 노드에 전파되어 지정된 미래의 시간에 실행될 필요가 있다.

모든 노드는 자체적인 제어 채널 스케줄에 부가하여, 인접 노드의 제어 채널스케줄을 알고 있다. 이것은 가시 거리내 통신이 존재하는 모든 인접 노드에 해당한다. 그것은 또한 통신이 존재할 수 없는 다른 기지국에 대한 제어 채널 스케줄을 알 수 있지만, 이러한 제어 채널의 마이크로슬롯은 무시될 수 있다. 인접 노드로의 데이터 전송 중에, 노드는 자체적인 제어 채널의 전송 및 수신을 유지하기 위해 전송을 중지해야만 한다. 이와 유사하게, 인접 노드가 제어 채널을 유지하도록 하기 위해 전송을 중지해야 한다. 브로드캐스팅 노드는 인접 노드의 제어 채널을 정지할 때 전파 지연을 고려해야 한다. 제어 채널에 사용되는 작은 시간 슬롯은 마이크로슬롯으로 칭한다. 노드 및 인접 노드의 RTS 및 CTS는 계속해서 교환될 것을 필요로하지는 않지만, 이것은 제어 채널을 스케줄링하는 효율적인 방법이다.

도 4A에서, 수평선(A,B)은 메시형 네트워크에서의 2 개의 인접 노드를 나타낸다. 도 4A를 참조하면, 노드에 대한 제어 채널 또는 마이크로슬롯이 도시되어 있다. 채널의 타이밍은 다른 노드에 공지되어 브로드캐스트된다. 노드 B로의 전송시, 노드 A는 이러한 노드 A의 마이크로슬롯 아래에, 그러나 동일한 시간 스케줄 상에 있는 노드 B의 마이크로슬롯에 관련된다. 아래로 향하는 화살표(G)는 RTS 상의 노드 A 전송기에 비교되는 노드 B 수신기의 전파 지연을 나타낸다. 이와 유사하게, 위로 향하는 화살표(H)는 RTS 상의 노드 B 전송기에 비교되는 노드 A 수신기의 전파 지연을 나타낸다.

도 4B에서, 노드 B의 마이크로슬롯은 노드 A가 인접 노드의 마이크로슬롯 스케줄을 알아야만 하기 때문에, 전파 지연을 고려하여 노드 A에 매핑된다. A 노드선 상의 어두운 사각형은 B 노드의 제어 채널이다. A 노드선 내의 결합된 마이크로슬롯 사이에 갭이 존재한다는 것을 주시해라. 이러한 갭은 A 노드에서 B 노드로의 전송을 위한 데이터 채널에 의해 사용 가능하다.

이제 인접 노드에 전송 요청(RTS) 하기 위한 프로토콜을 고려한다. 각각의 노드는 프레임마다 특정한 인접 노드에 RTS 요청을 할 기회를 갖는다. 제1 단계는 얼마나 많은 비트가 아직 스케줄링되지 않는 인접 노드에 전송되도록 대기 행렬내에 있는 지를 결정하는 것이다. 완전한 비트수가 요청된다. 선택적으로, 요청은 보다 작은 수의 비트로 제한될 수 있다. 노드는 데이터를 수신하거나 또는 전송하기 위해 이미 스케줄링된 시간을 트래킹한다. 이러한 시간 사이에, 갭이 존재하고, 스케줄 시간의 끝이 존재한다. 노드는 CTS를 인접 노드로부터 수신할 가능한 한 가장 이른 시간을 알 것이다. 그후, 이러한 시간 후에 최초의 3 개의 갭과, RTS로 패키지되는 스케줄 시간의 끝을 선택한다. CTS에 관련된 갭의 개시 및 정지 시간은 RTS로 패키지되는 것이다. 더욱 많은 또는 더욱 적은 갭이 선택적으로 선택될 수 있다. 다른 기준이 브로드캐스트 할 갭을 선택하기 위해 사용될 수 있다. RTS 신호가 수신(0비트 이상)된 후에, 스케줄링을 하는 것은 수신 노드의 책임이다. 제1 단계는 수신 노드의 스케줄 내의 요청 노드 및 갭으로부터 스케줄 정보의 갭 및 끝의 교차 부분을 결정하는 것이다. 첫번째 3 개의 갭은 유지되고 나머지는 폐기된다. 가능한 한 많은 전송이 이러한 갭에 스케줄링되고, 제1의 갭으로 개시된다. 여분의 공간이 존재한다면, 그후 마지막 갭은 짧아지거나 또는 폐기된다. 만약 갭이 충분히 길지 않다면, 잔여 비트는 스케줄의 끝에서 스케줄링된다. 이로서 많아야 4 개의 세그먼트(각각의 세그먼트는 제어 채널 주변에서 뒤섞일 것이고, 아마도 더욱세그먼트화될 것이다)로 스케줄링 전송된다. 갭에 전송될 수 있는 비트수는 2 개의 노드의 제어 채널 스케줄에 달려있다는 것을 유의해라. 갭은 RTS 및 CTS 필드 내에서 식별되어야 한다. 아래의 표 1 및 표 2의 패킷 포맷의 예에서, 갭으로 식별된 비트는 데이터가 동일한 프레임 내에서 발견되는 제어 채널의 외부 갭의 어드레스 또는 위치 정보를 위한 것이다.

제어 채널 패킷 포맷의 예

RTS 메시지(패킷내에서)	비트
512 비트 증가내의 비트의 요청 개수(0-1024*512, 즉 128Mbps에서의0-3.9 msec)	10
갭 1:[개시, 정지] CTS 도달의 종료로부터 오프셋(1/8의 마이크로초의 세분성과 함께 0.-4.096 msec)	30
갭 2: [개시, 정지] CTS 도달의 종료로부터 오프셋	30
갭 3: [개시, 정지] CTS 도달의 종료로부터 오프셋	30
스케줄 종료	15
합계	115

CTS 메시지(패킷내에서)	비트
갭 1:[개시, 정지] CTS 도달의 종료로부터 오프셋(1/8의 마이크로초의 세분성과 함께 0.-4.096 msec)	30
갭 2: [개시, 정지] CTS 도달의 종료로부터 오프셋	30
갭 3: [개시, 정지] CTS 도달의 종료로부터 오프셋	30
갭 4: [개시, 정지] CTS 도달의 종료로부터 오프셋	30
합계	120

RTS 및 CTS 패킷은 0 비트가 요청되거나 또는 스케줄링될 때 조차도 전송될 수 있다. 이로서 인접 노드의 상태의 모뎀 동기화 및 규칙적인 모니터링을 허용한다.

세션 스케줄링

제어 채널은 각각의 인접 노드와 프레임마다 적어도 하나의 세션을 갖도록스케줄링되고 임의의 경우에도 시간안에 하나의 세션에 관여한다. 다수의 갭을 식별하는 것이 필요한 프레임마다의 다수의 세션이 사용될 수 있다. 프레임의 길이는 노드가 전송을 요청하고 전송을 허용하는 기회를 갖는 주파수에서 최소의 주파수를 결정한다. 이와 같이, 프레임 길이는 네트워크의 응답과 네트워크의 지연에 영향을 준다. 보다 짧은 프레임은 보다 빠른 응답과 보다 짧은 지연이 되지만, 데이터 밴드폭을 감소시키게 된다. 최적의 짧은 프레임으로의 스케줄링은 일반적으로 복잡한 문제이다. 그러나, 제어 채널에 대한 최적의 스케줄은 일반적으로 필요하지 않거나 또는 반드시 필요하지도 않다. 스케줄링을 구현하는 단순한 알고리즘은 다음과 같다:

1. 스케줄링될 필요가 있는 모든 세션을 리스트.

2. 세션을 선택하고 그것을 가능한 한 일찍 스케줄링(어떠한 노드도 개시자일 수 있음).

3. 모든 세션이 스케줄링 될 때까지 단계 2를 반복. 그러한 스케줄의 적합성은 네트워크 및 네트워크의 바람직한 성능에 달려있다. 보다 짧은 스케줄이 상기 알고리즘에 대한 변경 또는 다양한 대안의 알고리즘을 통해 생성될 수 있다.

실시예

다음의 네트워크의 시뮬레이션은 수행된다: 도 1에 도시된 바와 같이, 직경 3km의 원에 랜덤하게 위치되고 완전히 결합된 노드이고, 128Mbps 대역폭을 사용하고, 모든 패킷이 완전한 트래픽 로드에서 1024 비트를 갖는 8 개의 노드로 구성된 메시형 네트워크. 각각의 노드는 64*1024 패킷/초 를 발생시키고 각각의 패킷의 수신지는 1 마이크로초 길이의 마이크로슬롯과 10 마이크로초의 스케줄링된 처리 시간을 갖는 노드의 인접 노드와, 378 마이크로초(제어 채널은 7.4%이다)의 프레임 길이로부터 랜덤하게 선택된다. 최소의 전송 시간은 1 마이크로초이고. 스케줄의 4 개의 갭의 플러스 엔드는 RTS 내에 통과되고, 5 개의 갭은 CTS로 복귀된다. 이러한 시뮬레이션은 갭의 경계 상에서 임의의 정확성을 취하고 갭이 얼마나 멀리 앞서는 가에 대한 제한은 없다. 또한 대기 행렬의 길이는 제한되지 않는다.

도 5는 70%의 로드로 RTS 신호로 통과되는 정보의 기능으로서의 지연과 비교되는 RTS 신호에서 식별되는 갭의 개수를 변경시키는 효과를 도시하고 있다. RTS 내에 적어도 3 개의 갭을 이용함으로써, 평균 지연이 최소화된다. 이것이 리던던씨(redundancy) 또는 다른 이유로 실행될 지라도, 갭의 수를 증가시키는데에 최소의 이득이 있다. RTS 신호보다는 CTS 신호로 제공된 하나 이상의 갭이 항상 존재한다.

전술된 바와 같이, 완전히 결합된 메시형 네트워크가 설명되었지만, 이것이 요구 사항은 아니다. 본 발명은 완전히 결합된 메시형으로 제한되지 않는다. 도 6은 완전히 결합된 메시형, 즉 트리 구조의 보조 세트를 도시하고 있다. 이것은 중심 노드(33)가 가지 노드(35,37)와 통신하는 체계적인 구조이다. 노드(33)는 링크(39)를 따라 백본 접속점과 통신할 수 있다. 전술된 바와 동일한 방식으로, 가지 노드는 보조 가지 노드(41, 43)와 각각 통신한다. 본 발명의 목적을 위해, 트리 구조와 유사한 노드 배열이 메시형 네트워크로 정의된다는 점이 강조된다.

Claims

통신 노드 사이의 가시선 장치를 갖는 복수의 상호 결합 노드를 갖는 형태의 무선 패킷의 무선 메시형 통신 시스템에 있어서, 상기 복수의 상호 결합 노드들 사이의 통신 방법은,

시간을 공지의 길이의 동기식 프레임으로 분할하는 단계와;

각각의 프레임 내에서, 제어 정보에 대해 시간 슬롯을 제공하여, 동기식 제어 채널을 제공하는 단계와;

통신 노드 사이에서, 각각의 통신 노드에서의 제어 정보를 사용하고, 제어 채널의 시간 슬롯 사이에 데이터의 비동기식 전송 또는 수신을 스케줄링하여, 데이터 채널을 제공하는 단계를 포함하는 것을 특징으로 하는 통신 방법.
제1항에 있어서, 각각의 노드가 스케줄을 갖고, 2 개의 노드, 즉 개시자 노드 및 수신자 노드 사이의 제어 채널에서, 상기 제어 채널은 상기 수신자에게 RTS 메시지를 전송하기 위한 요청과, 스케줄 내의 개시자의 스케줄되지 않은 시간에 대하여 수신자에게 전달하는 부가적인 데이터를 제공하는 개시자와, 상기 개시자에게 제공된 CTS(clear to send) 메시지 내의 스케줄되지 않은 시간의 개시자의 제공을 기초하여 상호 동의될 수 있는 시간의 전송 스케줄을 개시자에게 허용하는 수신자를 포함하는 통신 프로토콜을 더 갖는 것인 통신 방법.
제2항에 있어서, RTS(request to send) 메시지 내의 스케줄되지 않은 시간의 스케줄을 상기 개시자에게 제공된 수신자의 CTS(clear to send) 메시지에 첨부하는 단계와; 상기 개시자에 의해 상기 CTS 메시지를 사용하는 스케줄되지 않은 시간과 일치하는 시간에 대한 전송 스케줄을 수신자에게 허용하는 단계를 더 포함하는 것인 통신 방법.
제1항에 있어서, 각각의 노드가 이용 가능한 시간을 예고하여 데이터 패킷을 전송하는 단계를 더 포함하는 것인 통신 방법.
제1항에 있어서, 각각의 노드가 시간을 미리 할당하여 상기 인접 노드로부터 데이터 패킷을 수신하는 단계를 더 포함하는 것인 통신 방법.
제1항에 있어서, 각각의 프레임에서 상기 제어 채널을 주기적으로 반복함으로써 정의되는 것인 통신 방법.
제1항에 있어서, 제어 정보용 상기 제공된 시간 슬롯과 스케줄링하기 위해 각각의 통신 노드에서의 상기 사용된 제어 정보는 상기 통신 노드 사이의 반 이중 무선 통신을 제공하는 단계와, 각각의 노드로부터 데이터 채널 가운데의 제어 채널 마이크로슬롯의 스케줄을 전달하여, 각각의 노드가 통신하는 모든 노드의 마이크로슬롯의 스케줄을 갖는 단계와, 제1의 노드에서, 요청 노드에 의한 요청을 나타내는이용 가능한 갭의 스케줄을 포함하는 RTS 메시지를 기다리는 각각의 마이크로슬롯내의 제어 채널의 데이터를 판독하는 단계와, 제2 노드에서, 제1 노드와 가시선의 관계에서, 제1 노드의 RTS 메시지를 판독하고, 스케줄에 동의한 이용 가능한 갭의스케줄을 포함하는 CTS 메시지로 응답하여, 제1 노드의 요청에 수신하고 또한 요청된 데이터를 제공하기 위해 이용 가능한 갭의 스케줄을 갖는 RTS 메시지를 제1 노드에 전송하는 단계와, 상기 제1 노드에서, 상기 요청된 데이터를 수신하기 위해 이용 가능한 갭의 스케줄에 동의하는 CTS 메시지를 갖는 제2 노드의 RTS 메시지에 응답하는 단계를 포함하는 것인 통신 방법.
제7항에 있어서, 제1 노드와 제2 노드 사이에 방향성의 스위칭 가능한 안테나를 사용하는 것을 더 포함하는 것인 통신 방법.
제7항에 있어서, 제3의 노드에서, 요청 노드에 의해 요청되는 데이터를 나타내는 마이크로슬롯 사이의 이용 가능한 갭의 스케줄을 포함하는 RTS 메시지를 대기하는 각각의 마이크로슬롯 내의 제어 채널의 데이터를 판독하는 단계와, 제2 노드에서 제3의 노드에 가시선의 관계로, 제3 노드의 RTS 메시지를 판독하고 스케줄에 동의된 마이크로슬롯 사이의 이용 가능한 갭의 스케줄을 포함하는 CTS 메시지로 응답하여, 요청된 데이터의 요청을 수신하고 또한 상기 요청된 데이터를 제공하기 위해 이용 가능한 갭의 스케줄을 갖는 RTS 메시지를 제3 노드에 전송하는 단계와, 제3 노드에서, 상기 요청된 데이터를 수신하기 위해 이용 가능한 갭의 스케줄에 동의하는 CTS 메시지를 제2 노드의 RTS 메시지에 응답하는 단계를 더 포함하는 것인 통신 방법.
제7항에 있어서, 상기 RTS 메시지 내의 갭의 개수는 적어도 2 개인 것인 통신 방법.
제7항에 있어서, 제어 채널 마이크로슬롯의 프레시 스케줄은 상호간에 통신하는 노드의 승인 또는 이탈 시에 각각의 노드로부터 통신하는 것인 통신 방법.
제7항에 있어서, 상기 갭의 구간이 최소로 지정된 구간보다 작다면, 그 갭은 무시되는 것인 통신 방법.