KR101060821B1 - Ｃｓｍａ/ｉｃ를 위한 ｉｄ 할당 방법 - Google Patents

Abstract

본 발명에 따른 CSMA/IC 기반 노드에서 ID를 할당하는 방법은 매체 접근시에 자신의 ID를 할당하는 단계와, ID를 사용해야 하는 지를 판단하는 단계와, ID를 사용해야 한다면, ID 순환 법칙에 따라 자신의 ID를 변환하는 단계를 포함한다. 본 발명에 따라 CSMA/IC를 사용하는 네트워크에서 순환 ID를 활용함으로써 모든 노드들이 공평한 매체 접근 기회를 잡게 하고 메시지 교환 없이 ID를 할당함으로써 네트워크의 효율성을 높이는 효과를 가진다.

CSMA/IC

Description

ＣＳＭＡ/ＩＣ를 위한 ＩＤ 할당 방법{Method for assigning IDs for CSMA/IC}

본 발명은 충돌 없는 무선 MAC 프로토콜인 CSMA/IC(Carrier Sense Multiple Access / ID Countdown)에 사용할 수 있는 ID 할당 방법에 관한 것이다.

가장 널리 쓰이는 무선 MAC 프로토콜인 CSMA/CA 는 매체가 비어 있을 경우 모든 노드가 임의의 시간을 대기한 후 매체에 접근함으로써 충돌을 회피하는 프로토콜이다. 이 프로토콜은 노드가 많을 경우 접근 충돌이 잦아 성능이 낮아진다.

반면 CSMA/IC(Carrier Sense Multiple Access / ID Countdown)는 매체 접근 충돌이 없는 MAC 프로토콜이다.

CSMA/IC는 각 무선 노드마다 유일한 숫자 ID를 가지고 있고, 이 ID의 이진 형태에 따라 신호를 발생시켜 경쟁함으로써 노드간의 매체 접근 충돌을 배제한다. 구체적으로, CSMA/IC의 전체 동작을 CSMA/IC 프로토콜의 프레임 포맷을 참고하여 설명한다.

도 1은 CSMA/IC 프로토콜의 프레임 포맷을 나타낸 도면이다.

도 1을 참조하면, CSMA/IC 프로토콜의 프레임 포맷은 그 역할이 매우 간단한 4 부분으로 구성된다. 매체 접근 경쟁 이전에 모든 노드는 매체가 현재 아이들 상태인지를 확인하기 위해 "매체 감지 슬롯(Medium sensing slot)" 동안 매체를 감지한다. 그런 다음. 노드들은 "SB 신호 전송 기간(SB signal sending period)" 동안 "동기 비컨(Synchronizing Beacon)" 신호를 전송함으로써 로컬 동기 프로세서를 수행한다. 그런다음, 동기 노드들은 이진 경쟁 슬롯(Binary competing slots)의 미리 결정된 길이 동안 매체 접근을 위해 경쟁한다.

구체적으로 설명하면, 경쟁 기간 동안, 각 노드는 비컨 신호를 전송하거나 그 고유 ID의 이진 형태로부터 도출된 스케줄에 따라 매체를 감지한다. 이 스케줄은 다음 법칙에 따라 결정된다. 최상위 비트로부터, 비트들은 1비트씩 해석된다. 비트 "1"은 "비컨 신호 전송"으로서 해석되고 비트 "0"은 "매체 감지(sense media)"로서 해석된다. 만약 노드가 "sense media" 타임 슬롯에서 비컨 신호를 감지한다면, 경쟁을 중지한다. 이 경쟁 프로세스를 반복함으로써 끝까지 남아있는 노드는 경쟁의 승자가 된다. 모든 ID는 고유하기 때문에, 스케줄은 똑같을 수 없다. 그러므로, 매체 접근 충돌은 CSMA/IC에서는 일어날 수 없다. 최종적으로 경쟁의 승자는 "데이터 전송 기간(Data sending period)" 동안 데이터를 전송한다.

CSMA/IC의 가장 중요한 이점은 충돌 없는 소유이다. 고유의 ID들은 고유의 비컨 신호 스케줄을 발생시키며, 오직 하나의 승자만이 선택된다. 충돌은 대역 낭비의 주요한 원인이므로, CSMA/IC는 네트워크 스루풋 성능을 매우 개선한다. 또한, CSMA/IC는 interference range에서 노드들에 의해 유발된 "히든 단말"의 문제점을 해결한다. CSMA/IC는 경쟁자(contender)를 제거하기 위해 비컨 신호를 사용한다. 왜냐하면, 비컨 신호는 interference range에서 노드들에 의해 감지될 수 있기 때문에, interference range에서의 히든 단말은 경쟁 기간 동안 또한 제거되며, 그에 따라 "히든 단말" 문제는 해결된다.

이들 매력적인 점들에도 불구하고, CAMS/IC는 2개의 치명적인 단점으로 인해 널리 사용되지 않고 있다. 그 하나는 가장 큰 ID를 갖는 노드가 항상 매체 접근 기회를 획득한다. 이는 불공평한 매체 접근 문제는 심각한 기아 문제를 발생시킨다. 다시 말해, 그에 따라, CSMA/IC에서는 항상 큰 ID를 갖는 노드가 매체 접근 기회를 획득하여 다른 노드들이 매체에 접근할 수 없는 문제점이 있다. 다른 문제점은 고유의 ID를 할당하는 것이 그 불확실성으로 인해 ad hoc 네트워크 환경에서 매우 어렵다.

따라서, 본 발명의 목적은 종래 기술의 문제점을 해결하기 위해 순환 ID를 사용하며 순환 ID를 사용할 때 각 노드에 지역적으로 유일한 ID를 부여하는 방법을 제공한다.

상기 목적을 달성하기 위한 본 발명의 일 측면에 따른, CSMA/IC 기반 노드에서 ID를 할당하는 방법은 매체 접근시에 자신의 ID를 할당하는 단계와, ID를 사용해야 하는지를 판단하는 단계와, ID를 사용해야 한다면, ID 순환 법칙에 따라 자신의 ID를 변환하는 단계를 포함한다.

여기에서, 상기 ID 순환 법칙은 상기 ID에서 최상위 비트로부터 첫번째 '0' 비트를 '1'로 설정하는 제1 법칙, 상기'0'으로 설정된 비트의 앞자리 비트들을 모두 '0'비트로 변환하는 제2 법칙 및 모든 비트가 '1'인 경우는 모두 '0'으로 변환하는 제3 법칙을 포함한다.

여기에서, 상기 ID 할당 단계는 매체가 아이들 상태인지를 판단하는 단계와, 상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와, 경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하고 상기 변환된 ID보다 큰 랜덤 ID를 자신의 ID로서 할당하는 단계를 포함한다.

여기에서, 상기 ID 할당 단계는 매체가 아이들 상태인지를 판단하는 단계와, 상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와, 경쟁 노드의 비컨 신호를 감지하지 않았으면, 0보다 큰 랜덤 ID를 자신의 ID로 할당하는 단계를 포함한다.

여기에서, 상기 ID 할당 단계는 매체가 아이들 상태인지를 판단하는 단계와, 상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와, 경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하는 단계와, 상기 변환된 ID가 사용가능한 ID들 중 가장 큰 ID이면 ID 할당 시도 횟수가 임계값을 초과하는 지를 판단하고, 초과하면 노드가 매체 접근 경쟁에서 승자가 될 수 있도록 하는 인터셉트 비트를 1로 설정하는 단계와, 랜덤 ID를 자신의 ID로 할당하는 단계를 포함한다.

여기에서, 상기 ID를 사용해야 하는지를 판단하는 단계는 전송할 데이터가 있는 지 판단하는 단계를 포함한다.

본 발명의 다른 측면에 따른, CSMA/IC 기반 노드에서 ID를 할당하는 방법은 매체가 아이들 상태인지를 판단하는 단계와, 상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와, 경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하고 상기 변환된 ID보다 큰 랜덤 ID를 자신의 ID로서 할당하는 단계와, 경쟁 노드의 비컨 신호를 감지하지 않았으면, 0보다 큰 랜덤 ID를 자신의 ID로 할당하는 단계를 포함한다.

본 발명의 또 다른 측면에 따른, CSMA/IC 기반 노드에서 ID를 할당하는 방법은 매체가 아이들 상태인지를 판단하는 단계와, 상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와, 경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하는 단계와, 상기 변환된 ID가 사용가능한 ID들 중 가장 큰 ID이면 ID 할당 시도 횟수가 임계값을 초과하는 지를 판단하고 초과하면 노드가 매체 접근 경쟁에서 승자가 될 수 있도록 하는 인터셉트 비트를 1로 설정하는 단계와, 랜덤 ID를 자신의 ID로 할당하는 단계를 포함한다.

여기에서, 상기 ID 할당 방법은 상기 경쟁 노드의 비컨 신호를 감지하지 않았으면, 0보다 큰 랜덤 ID를 자신의 ID로 할당하는 단계를 더 포함한다.

여기에서, 상기 ID 할당 방법은 상기 변환된 ID가 사용가능한 ID들 중 가장 큰 ID가 아니면, 상기 변환된 ID보다 큰 랜덤 ID를 자신의 ID로서 할당하는 단계를 더 포함한다.

상기와 같은 본 발명은 순환 ID 시스템과 ID 시스템에서 지역적으로 유일한 ID를 부여하는 기법으로 구성되어 있다. 순환 ID 시스템은 매체 접근 경쟁 마다 ID를 순환하여 큰 ID를 공평하게 가지게 함으로써 매체 접근 기회를 공평하게 부여하게 한다. 유일한 ID 부여하는 기법은 항상 가장 큰 ID가 매체 접근 경쟁에서 승리한다는 CSMA/IC의 특성을 바탕으로 노드간의 ID 정보에 대한 교환 없이 노드 자체적으로 판단하여 ID를 스스로 부여함으로써 네트워크의 효율성을 높인다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 각 도면을 설명하면서 유사한 참조부호를 유사한 구성요소에 대해 사용하였다.

제1, 제2, A, B 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의 조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.

어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다.

본 출원에서 사용한 용어는 단지 특정한 실시예를 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함하다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥 상 가지는 의미와 일치하는 의미를 가지는 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.

이하, 본 발명에 따른 실시예들을 첨부된 도면을 참조하여 상세하게 설명한 다.

본 발명을 설명하기 앞서, CSMA/IC에서의 ID 스크린 효과(ID Screeen Effect)를 설명한다.

도 2은 CSMA/IC에서의 ID 스크린 효과를 설명하기 위한 도면이다.

CSMA/IC에서 다른 노드들의 비컨 신호를 감지한 노드는 경쟁을 포기한다. 그러므로, 승자만이 비컨 스케줄을 완전히 수행할 수 있다. 예컨대, 도 2에서 노드 A(10)의 ID가 "0110"이고 노드 B(20)의 ID가 "1001"이고 노드 C(30)의 ID가 "1010"이며, 노드들 A, B 및 C는 서로 결합되어 있다. 도 2에서 "1010"의 비컨 스케줄 만이 완전하게 수행된다. 첫번째 경쟁 슬롯에서, 노드 A910)는 노드 B (20)및 노드 C(30)의 비컨 신호으로 인해 경쟁을 포기한다. 이어서, 노드 B(20)는 세번째 경쟁 슬롯에서 경쟁을 포기한다. 도 2에 도시된 바와 같이, 다른 비컨 스케줄들은 승자의 비콘 스케줄에 의해 완전히 차단된다. 두번째 경쟁 슬롯에서의 노드 A(10)의 비컨 및 네번째 경쟁 슬롯에서의 노드 B(20)의 비컨은 차단된다. 이러한 현상을 "ID 스크린 효과(ID Screeen Effect)"라고 한다. 이러한 ID 스크린 효과는 이웃노드들 중 검출된 ID(observed ID)보다 큰 ID가 없다는 사실을 제공한다. 즉, 노드가 검출된 ID보다 큰 ID를 할당한다면, 해당 ID는 로컬 영역에서 유일한 것은 확실하다. 본 발명은 이러한 ID 스크린 효과를 이용한다.

도 3은 본 발명의 일실시예에 따른 ID 할당 방법을 나타낸 도면이다.

도 3을 참조하면, 노드는 단계 210에서 매체가 아이들 상태인지를 판단한다. 구체적으로 매체 접근 경쟁(medium access competition)에 참가하고자 하는 노드는 다른 노드들의 전송을 방해하지 않기 위해 매체가 아이들 상태가 될 때까지 대기한다. 매체가 아이들 상태가 되면 노드는 매체가 실제로 아이들 상태인지를 확인하기 위해 일정 기간(certain duration) 동안 추가적인 시간을 더 대기할 수도 있다.

이어서, 노드는 단계 220에서 경쟁 시작점(contention starting point)을 동기화하기 위해 동기 비컨(synch Beacon)을 전송한다. 동기 후에, 노드는 단계 230에서 미리 결정된 "이진 경쟁 슬롯(Binary competing slots)" 구간 동안 경쟁 노드들의 비컨을 감지한다. 만약 노드가 이진 경쟁 슬롯 구간 동안 어떠한 비컨 신호도 감지하지 않는다면, 노드는 단계 260으로 진행하여 자신의 ID로서 0보다 큰 임의의 램덤 ID를 할당한다. 즉, 모든 이웃들은 아이들 상태 이거나 그 이웃 노느들의 ID는 0이기 때문이다. 그러나, 만약 노드가 비컨 신호를 감지하였으면, 단계 240으로 진행하여 감지된 비컨 신호를 ID로 변환한다. 즉, 노드는 감지된 비컨 신호로부터 ID를 획득한다. "ID 스크린 효과"로 인해 감지된 비컨 신호는 승자의 비컨 신호이다. 따라서, 비컨 신호로부터 획득된 ID는 이웃들 중 가장 큰 ID가 된다.

비컨 신호를 ID로 변환한 후 노드는 단계 250에서 비컨 신호로부터 획득된 ID보다 큰 임의의 랜덤 ID를 자신의 ID로서 할당한다.

그런데, 비컨 신호로부터 획득된 ID가 ID 풀에서 가장 큰 ID일 수 있으며, 그에 따라 노드는 다음 경쟁 슬롯에서 ID를 다시 할당해야 한다. 또한, 거의 모든 ID가 사용되고 있다면 노드는 긴 시간을 대기하거나 ID를 할당하지 못할 수 있다.

이러한 문제를 해결하기 위해 이하 본 발명의 제2 실시예에서는 "인터셉트 비트(Intercept bit)를 사용한다.

도 4는 본 발명의 제2 실시예에 따른 ID 할당 방법을 나타낸 도면이다. 도 4의 단계 310 내지 단계 330은 도 3의 단계 210 내지 230과 유사하므로, 도 3에 관련된 설명을 참조한다.

도 4를 참조하면, 노드는 단계 310에서 매체가 아이들 상태인지를 판단한다. 노드는 매체가 아이들 상태일 때까지 대기하다가 아이들 상태가 되면 단계 320에서 경쟁 시작점(contention starting point)을 동기화하기 위해 동기 비컨(synch Beacon)을 전송한다. 동기 후에, 노드는 단계 330에서 미리 결정된 "이진 경쟁 슬롯(Binary competing slots)" 구간 동안 경쟁 노드들의 비컨을 감지한다.

만약 노드가 이진 경쟁 슬롯 구간 동안 어떠한 비컨 신호도 감지하지 않는다면, 노드는 단계 370으로 진행하여 자신의 ID를 할당한다. 이 경우, 노드는 자신의 ID로서 0보다 큰 임의의 램덤 ID를 할당하면 된다.

만약 노드가 이진 경쟁 슬롯 구간 동안 비컨 신호를 감지하였으면 단계 340으로 진행하여 감지된 비컨 신호를 ID로 변환한다. 즉, 노드는 감지된 비컨 신호로부터 ID를 획득한다. "ID 스크린 효과"로 인해 감지된 비컨 신호는 승자의 비컨 신호이다. 따라서, 비컨 신호로부터 획득된 ID는 이웃들 중 가장 큰 ID가 된다.

이어서, 노드는 단계 350으로 진행하여 변환된 ID가 사용가능한 ID들(available IDs) 중 가장 큰 ID인지를 판단한다. 만약 변환된ID가 사용 가능한 ID들 중 가장 큰 ID가 아니면 노드는 단계 370으로 진행하여 자신의 ID를 할당한다. 이 경우, 노드는 비컨 신호로부터 획득된 ID보다 큰 임의의 랜덤 ID를 자신의 ID로서 할당한다.

그리고, 변환된 ID가 사용 가능한 ID들 중 가장 큰 ID이면, 노드는 단계 360으로 진행하여 ID 할당 시도 횟수가 임계값을 초과하였는 지를 판단한다. ID 할당 시도 횟수가 임계값을 초과하였으면, 노드는 단계 380으로 진행하여 인터셉트 비트(Intercept bit)를 1로 설정한다. 인터셉트 비트는 매체 접근 경쟁에서 노드가 승자가 될 수 있게 한다.

그리고, 노드는 도 4에 도시하지 않았지만, 랜덤 ID를 할당한다. 이 경우에, 그 이웃 노드들 중 하나가 자신의 ID를 감지한다면, 그 노드는 자신의 ID를 해제한다(release). 인터셉트 비트를 1로 설정하는 경우, 할당된 ID가 다른 노드에 의해 점유되었는 지에 상관없이 사용될 수 있다.

즉, 노드는 자신의 ID를 할당하기 위한 시도를 여러 번 수행하고 여러 번 ID를 할당하려고 시도해도 ID 할당에 실패한 경우 인터셉트 비트를 1로 설정하는 것이다.

이에 따라 노드는 인터셉트 비트와 랜덤하게 할당된 ID에 의해 노드는 매체 접근 경쟁에 참여한다. 왜냐하면, "인터셉트 비트"는 ID 부분 이전에 위치하기 때문에 노드는 승자가 될 수 있으며, 다른 모든 이웃 노드들이 비컨 신호를 감지한다.

도 5는 본 발명의 제2 실시예에 따른 "이진 경쟁 슬롯"의 포맷을 나타낸다.

도 5를 참조하면, 이진 경쟁 구간의 포맷에서 인터셉트 비트가 첫번째 경쟁 슬롯에 위치하기 때문에, 인터셉트 비트"가 1로 설정되면, 노드는 매체 접근 경쟁에서 승자가 된다.

한편, 본 발명에 따라 ID 할당 프로세스 후에, 새로 진입하는 노드는 순환되는 ID(rotated ID)를 이용하여 그 이웃 노드들과 경쟁한다. 모든 노드들은 매 경쟁에서 그들의 ID들을 순환하며, 그에 따라 새로 진입하는 노드는 또한 ID 충돌을 피하도록 그 할당된 ID를 순한해야 한다. 본 발명에 따른ID 순환의 법칙은 이하 설명된다.

도 6은 본 발명의 제3 실시예에 따른 ID 할당 방법을 나타낸 도면이다. 도 6에서 단계 410 내지 단계 460은 도 3 및 관련 설명의 단계 210 내지 260과 동일하므로 그 상세한 설명을 생략한다.

도 6을 참조하면, 노드는 단계 410에서 매체가 아이들 상태인지를 판단한다. 매체가 아이들 상태가 아니면, 노드는 단계 420에서 경쟁 시작점(contention starting point)을 동기화하기 위해 동기 비컨(synch Beacon)을 전송한다. 동기 후에, 노드는 단계 430에서 미리 결정된 "이진 경쟁 슬롯(Binary competing slots)" 구간 동안 경쟁 노드들의 비컨을 감지한다. 만약 노드가 이진 경쟁 슬롯 구간 동안 어떠한 비컨 신호도 감지하지 않는다면, 노드는 단계 440으로 진행하여 자신의 ID로서 0보다 큰 임의의 램덤 ID를 할당한다. 만약 노드가 비컨 신호를 감지하였으면, 단계 450으로 진행하여 감지된 비컨 신호를 ID로 변환한다. 즉, 노드는 감지된 비컨 신호로부터 ID를 획득한다. 비컨 신호를 ID로 변환한 후 노드는 단계 460에서 비컨 신호로부터 획득된 ID보다 큰 임의의 랜덤 ID를 자신의 ID로서 할당한다.

이어서, 노드는 단계 470에서 ID를 사용해야 하는 지를 판단한다. 노드는 할당한 ID를 이용하여 매체 접근 경쟁에 참여하였다. 노드는 매체 접근 경쟁에서 승 자가 될 수도 있고 아닐 수도 있다. 노드는 매체 접근 경쟁에서 승자가 되면 데이터를 매체로 송신할 수 있다. 노드가 매체 접근 경쟁에서 승자가 되어 데이터를 매체로 송부하였더라도 전송할 데이터가 더 존재할 수 있다. 노드는 전송할 데이터가 더 있으면 ID를 사용해야 한다.

또한, 노드는 매체 접근 경쟁에서 승자가 되지 못하면 데이터를 전송하지 못한다. 그에 따라 노드는 매체 접근 경쟁에서 승자가 되지 못한 경우 데이터를 전송하기 위해 ID를 사용해야 한다.

그에 따라 노드는 단계 470에서 ID를 사용해야 하는 지를 판단한다. ID를 사용해야 하는 경우 노드는 단계 480에서 본 발명에 따른 ID 순환 법칙에 따라 자신의 ID를 변환한다. 이하 구체적으로 설명한다.

노드가 매체 접근 경쟁에서 접근 권한을 획득하였다면, 노드는 자신을 포함하여 이웃 노드들 중에 가장 큰 ID를 가졌을 수 있다. 이 경우 노드가 계속적으로 자신의 ID를 유지한다면 다른 노드들이 매체 접근 경쟁에서 접근 권한을 획득하기가 어렵다. 따라서, 이 경우에 노드는 자신의 ID를 낮은 값의 ID로 변환하는 것이 바람직하다.

다르게는, 노드가 매체 접근 경쟁에서 접근 권한의 획득에 실패하였다면, 노드는 자신을 포함하여 이웃 노드들 중에 적은 값의 ID를 가졌을 수 있다. 이 경우 노드가 계속적으로 자신의 ID를 유지한다면 매체 접근 경쟁에서 접근 권한을 획득하기가 어렵다. 따라서, 이 경우에 노드는 자신의 ID를 높은 값의 ID로 변환하는 것이 바람직하다.

이러한 위의 상황들을 고려하여 본 발명은 노드가 매체 접근 경쟁 주기가 종료할 때마다, 즉, 매체 접근 경쟁 주기마다 ID를 변환한다. 이 때, ID는 다음과 같은 법칙에 따라 변환된다.

1. 이진 형태의 ID에서 최상위 비트로부터 첫번째 '0' 비트를 '1'로 설정한다.

2. '0'으로 설정된 비트의 앞자리 비트들을 모두 '0'비트로 변환한다.

3. 모든 비트가 '1'인 경우는 모두 '0'으로 변환한다.

그에 따라 ID의 이진 형태가 "11001"이면, 상기 ID 순환 법칙에 따라 "00101"이 된다. 왜냐하면, 세번째 비트가 첫번째 "0" 비트이기 때문에, 제1 및 제2 비트들은 '0'으로 설정되고, 세번째 비트는 '1'로 설정된다.

도 7은 본 발명에 따른 ID 순환 예를 나타낸 도면이다. 노드들은 매 매체 접근 경쟁에 참여한 후에 자신의 ID를 도 7에 도시된 바와 같은 순서로 변환한다.

이와 같이, CSMA/IC를 사용하는 네트워크에서 순환 ID를 활용함으로써 모든 노드들이 공평한 매체 접근 기회를 잡게 하고 메시지 교환 없이 ID를 할당함으로써 네트워크의 효율성을 높이는 효과를 가진다.

상기에서는 본 발명의 바람직한 실시예를 참조하여 설명하였지만, 해당 기술 분야의 숙련된 당업자는 하기의 특허 청구의 범위에 기재된 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 및 변경시킬 수 있음을 이해할 수 있을 것이다.

도 1은 CSMA/IC 프로토콜의 프레임 포맷을 나타낸 도면이다.

도 2은 CSMA/IC에서의 ID 스크린 효과를 설명하기 위한 도면이다.

도 3은 본 발명의 일실시예에 따른 ID 할당 방법을 나타낸 도면이다.

도 4는 본 발명의 제2 실시예에 따른 ID 할당 방법을 나타낸 도면이다.

도 5는 본 발명의 제2 실시예에 따른 "이진 경쟁 슬롯"의 포맷을 나타낸다.

도 6은 본 발명의 제3 실시예에 따른 ID 할당 방법을 나타낸 도면이다.

도 7은 본 발명에 따른 ID 순환 예를 나타낸 도면이다.

Claims (10)

1. CSMA/IC 기반 노드의 ID관리 방법에 있어서,

   데이터의 전송을 원하는 노드가 다른 전송 노드들의 매체 접근 경쟁 비콘 신호를 관찰하는 단계;

   상기 관찰을 통해서 비콘 신호가 감지된 경우 매체 접근 경쟁에 참여한 경쟁 노드들의 ID 중 가장 큰 ID를 추출하고, 상기 추출한 경쟁 노드들의 ID중 가장 큰 ID보다 크고 미리 결정된 최대 ID보다 작거나 같은 ID중 하나를 랜덤하게 선택하여 자신의 초기 ID로 설정하는 단계; 및

   연속된 데이터의 전송이 종료되어 더 이상 전송할 데이터가 존재하지 않을 때 까지, 노드가 상기 초기 ID로 부터, 매 매체 접근 경쟁이 시작될 때 마다 미리 결정된 ID 순환 규칙을 이용하여 ID를 변환시키는 단계를 포함하는 것을 특징으로 하는 ID 관리 방법.
2. 제 1 항에 있어서, 상기 초기 ID로 설정하는 단계는,

   상기 관찰을 통해서 비콘 신호가 감지되지 않은 경우, 0보다 크고 상기 미리 결정된 최대 ID보다 작거나 같은 ID중 하나를 랜덤하게 선택하여 자신의 초기 ID로 설정하는 것을 특징으로 하는 ID 관리 방법.
3. 제 1 항에 있어서, 상기 초기 ID로 설정하는 단계는,

   상기 관찰을 통해서 비콘 신호가 감지된 경우, 매체 접근 경쟁에 참여한 경쟁 노드들의 ID중 가장 큰 ID를 자신의 초기 ID로 설정하는 것을 특징으로 하는 ID 관리 방법.
4. 제 3 항에 있어서, 상기 초기 ID로 설정하는 단계는,

   상기 경쟁 노드들의 ID중 가장 큰 ID가 상기 미리 결정된 최대 ID와 같아 초기 ID를 설정할 수 없는 횟수가 임계값을 초과하는지 판단하고, 상기 판단 결과 임계값을 초과하는 경우 노드가 매체 접근 경쟁에서 승자가 될 수 있도록 하는 인터셉트 비트를 1로 설정하고, 0부터 상기 미리 결정된 가장 큰 ID보다 작거나 같은 ID 중 하나를 랜덤하게 선택하여 자신의 초기 ID로 설정하는 것을 특징으로 하는 ID 관리 방법.
5. 제 4 항에 있어서, 상기 초기 ID로 설정하는 단계는,

   상기 인터셉트 비트를 1로 설정하여 ID를 초기화한 노드와 동일한 ID를 가진 노드는 가지고 있던 ID를 포기하는 ID 관리 방법.
6. 제 1 항에 있어서, 상기 미리 결정된 ID 순환 규칙은,

   상기 ID에서 최상위 비트로부터 첫번째 '0' 비트를 '1'로 설정하는 제1 법칙, 상기'0'으로 설정된 비트의 앞자리 비트들을 모두 '0'비트로 변환하는 제2 법칙 및 모든 비트가 '1'인 경우는 모두 '0'으로 변환하는 제3 법칙 중 적어도 하나임을 특징으로 하는 ID 관리 방법.
7. CSMA/IC 기반 노드에서 ID를 할당하는 방법에 있어서,

   매체가 아이들 상태인지를 판단하는 단계와,

   상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와,

   경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하고 상기 변환된 ID보다 큰 랜덤 ID를 자신의 ID로서 할당하는 단계와,

   경쟁 노드의 비컨 신호를 감지하지 않았으면, 0보다 큰 랜덤 ID를 자신의 ID로 할당하는 단계를 포함하는 것을 특징으로 하는 ID 할당 방법.
8. CSMA/IC 기반 노드에서 ID를 할당하는 방법에 있어서,

   매체가 아이들 상태인지를 판단하는 단계와,

   상기 매체가 아이들 상태이면 동기 비컨 신호를 전송하는 단계와,

   경쟁 노드의 비컨 신호를 감지하였으면 감지된 비컨 신호를 ID로 변환하는 단계와,

   상기 변환된 ID가 사용가능한 ID들 중 가장 큰 ID이면 ID 할당 시도 횟수가 임계값을 초과하는 지를 판단하고 초과하면 노드가 매체 접근 경쟁에서 승자가 될 수 있도록 하는 인터셉트 비트를 1로 설정하는 단계와,

   랜덤 ID를 자신의 ID로 할당하는 단계를 포함하는 것을 특징으로 하는 ID 할당 방법.
9. 제8항에 있어서,

   상기 경쟁 노드의 비컨 신호를 감지하지 않았으면, 0보다 큰 랜덤 ID를 자신의 ID로 할당하는 단계를 더 포함하는 것을 특징으로 하는 ID 할당 방법.
10. 제8항에 있어서,

    상기 변환된 ID가 사용가능한 ID들 중 가장 큰 ID가 아니면, 상기 변환된 ID보다 큰 랜덤 ID를 자신의 ID로서 할당하는 단계를 더 포함하는 것을 특징으로 하는 ID 할당 방법.

Images