【발명의 설명】

【발명의명칭】

수중 무선 이동 네트워크를 위한 스케줄링 방법

【기술분야】

본 발명은 수중 무선 이동 네트워크를 위한 스케줄링 방법에 관한 것으로， 특히 시간 영역에서 충돌이 발생하지 않는 스케쥴링 방법을 고려하되 특정 순간에 전송 시간이 겹치지 않도톡 작교화하기 보다는 음파의 전달 속도 및 패¾ 길이를 고려하여 싱크 노드에서 패킷이 패킷 트레인 형태로 연속적으로 수신되도록 하여 네트워크 효율을 향상시킬 수 있는， 수중 무선 이동 펴ᅵ트워크를 위한 스케즐링 방 법에 관한 것이다ᅳ 또한, 본 발명은 수중음향 무선 이동 네트워크 등과 같이 왕복시간지연이 크 고 물리 계층의 전송 속도가 낮은 네트워크 환경에서 다수의 노드들이 싱크 노드로 데이터 패킷을 시분할 다중접속 방식으로 전송하고자 할 때 노드의 이동성에 따른 왕복시간지연을 사이클 단위로 추적하여 싱크 노드가 노드들로부터 데이터 패¾을 수신함에 있어 유휴 시간을 최소화함으로써 채널 사용 효율 향상을 통한 네트워크 효율이 크게 향상될 수 있는， 수중 무선 이동 네트워크를 위한 스케쥴링 방법에 관 한 것이다. 또한， 본 발명은 수중음향 무선 이동 네트워크 등과 같이 왕복시간지연이 크 고 물리 계층의 전송 속도가 낮은 네트워크 환경에서, 다수의 노드들이 성크 노드

1

대체용지 (규칙 제 26조) 로 데이터 패킷을 시분할 다중접속 방식으로 전송하고자 할 때, 노드의 이동성에 따른 왕복시간지연을 사이클 단위로 추적하여 싱크 노드가 노드들로부터 데이터 패 킷을 수신함에 있어 유휴 시간을 최소화함으로써 채널 사용 효율 향상을 통한 네트 워크 효율이 크게 향상될 수 있는, 수중 무선 이동 네트워크를 위한 스케줄링 방법 에 관한 것이다.

【배경기술】

통상적으로， 수중 무선 네트워크는 음파를 이 하며， 이렇게 음파를 사용하 는 수중 무선 네트워크에서는 전자파에 비해서 상대적으로 전달 속도가 매우 느린 음파의 전달 속도에서 기인하는 매우 긴 전파 지연， 그리고 수중음향 모템의 협소 한 대역폭에 기인하는 물리 계층의 느린 데이터 전달 속도에 의해서 길어지는 패킷 길이로 인해 발생하는 네트워크 효율성 저하를 극복하는 것이 가장 중요하다.

수중 무선 네트워크 토폴로지는 하나 또는 다수의 싱크 노드로 다수의 노드 들이 정보를 전달하는 것을 주 트래픽으로 하는 중앙 집중 방식과， 분산형의 다중 흡 방식이 있는데， 네트워크 효율 측면에서 중앙 집중 방식이 유리하다. 현재 상용 으로 운용되고 있는 모든 네트워크 방식 또한 중앙 집중식이다. 중앙 집중 방식은 공간 /시간 /주파수 /부호 둥의 자원을 직교화하여 사용하는 것이 일반적이다.

전파 지연 시간이 "0"에 가까운 공기중에서의 전자파를 이용하는 통신 네트 워크 시스템에서는， 같은 충돌 영역에 있는 두 노드가 동시에 패킷 송신을 하면 서 로 충돌을 일으키지만， 수중에서는 느린 음파의 전달 속도로 인하여 충돌을 일으키 지 않을 수도 있다. 예를 들면， 음파의 전달 속도를 1 , 500 m/s 로 가정하고， 서로 1.5 km 떨어져 있는 두 노드가 1초 길이의 데이터 패¾을 동시에 전송하면， 송신-

2

대체용지 (규칙 제 26조) 수신간 스위칭에 필요한 시간을 무시하면， 각 노드에서 송신이 끝나자마자 다른 노 드의 패킷 수신이 시작된다. 구체적으로는 0초에 두 노드가 1초 길이의 패킷을 동 시에 전송하면 1초 시점에서 두 노드는 송신이 종료되고， 바로 상대 노드의 데이터 를 수신하기 시작하므로 자신의 패킷 송신이 상대 노드의 패킷을 수신하는데 문제 를 야기하지 않게 되고， 2초 시점에는 두 노드 모두 패킷 수신이 완료된다. 만약 순차적으로 데이터를 전송한다면 총 4초의 시간이 소요되므로, 이 경우에는 네트워 크 효율이 2배 향상되는 효과를 가진다. 하지만， 이런 경우에도 두 노드가 서로 가 까워지는 방향으로 움직이는 경우에는 충돌이 발생하는데， 기존 대부분의 수중 무 선 매체접속제어 프로토콜은 이와 같은 노드의 이동성을 고려하고 있지 않다. 국내 특허 등록 제 1522279호 공보 (발명의 명칭: 수중 음향 네트워크의 정밀 시간 -경계 시분할 다중 접근 방법， 이하 특허 문헌이라 함)는 노드의 이동성을 고 려하고 있으나， 각 노드의 초기 위치를 알아야 하고 초기화 과정에서 노드가 고정 되어 있어야 하며, 각 노드의 이동 속도 정보가 매 사이클 지속적으로 갱신되어야 하며， 시간 동기화가 반드시 필요하다는 단점이 있다. 더욱이 상기 특허 문헌은 각 노드의 속도 정보를 이용하여 위치 추정을 하고 이를 기반으로 왕복 시간 지연을 추정하는 방법을 제시하고 있으나， 이는 시간이 지날수록 수중 노드의 속도 정보의 누적에 따른 오차가 커지는 환경에서 적용하는데 한계가 있었다. 또한， 상기 특허 문헌은 시간 동기화를 위한 구체적인 방안이 제시되지 않았고， 동기화 오차에 대한 대응방안이 없기 때문에 각 노드의 초기 위치 정보 S는 속도를 알 수 없거나, 시 간 동기화가 불가능한 경우에는 활용이 불가하다는 문제점이 있었다.

【발명의 내용】

3

대체용지 (규칙 제 26조) [기술적 과제】

따라서 본 발명은 상기와 같은 점에 착안하여 이루어진 것으로서 , 본 발명의 목적은 수중에서 이동 노드의 항법 정보와 무관하게 동작핥과 아울러 , 시간 동기화 가 불필요하므로 시간 동기화를 위한 별도의 패킷 교환이 필요 없으므로 네트워크 수율을 향상시킬 수 있는， 수중 무선 이동 네트워크 # 위한 스케즐링 방법을 제공 하는 데에 있다. 본 발명의 다른 목적은 수중음향 무선 이동 네트워크와 같이 왕복시간지연이 크고 물리 계층의 전송 속도가 낮은 네트워크 환경에서， 채널 사용 효율 향상을 통 한 네트워크 효율을 향상시킬 수 있고， 시간 동가화가 필요 없으므로 시간 동기화 가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 웅용 분야에서도 활 용이 가능하며， 오차가 누적되지 않고 주기적인 재초기화가 필요 없는， 수증 무선 이동 네트워크를 위한 스케쥴링 방법을 제공하는 데에 있다ᅳ 본 발명의 또 다른 목적은 수중음향 무선 이동 네트워크와 같이 왕복시간지 연이 크고 물리 계층의 전송 속도가 낮은 네트워크 환경에서, 채널 사용 효율 향상 을 통한 네트워크 효율을 향상시킬 수 있고， 시간 동기화가 필요 없으므로 시간 동 기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 응용 분야에서도 활용이 가능하며, 오차가 누적되지 않고 주기적인 재초가화가 필요 없는， 수중 무 선 이동 네트워크를 위한 스케줄링 방법을 제공하는 데에 있다.

【기술적 해결방법】

4

대체용지 (규칙 제 26조) 상기의 목적을 달성하기 위해 본 발명의 일실시형태에 의한， 수증 무선 이동 네트워크를 위한 스케줄링 방법은 싱크 노드로부터 다수의 노드들로 초기화 패킷을 방송하는 제 1 단계; 상기 싱크 노드가 다수의 노드들로부터 제 1 설정시간 ( ⁷ O 동안 초기화 응답 패킷을 수신하는 제 2 단계; 상기 싱크 노드가상기 제 2 단계에 서 수신한 초기화 응답 패킷으로부터 상기 싱크 노드와 다수의 노드들 간 왕복 시 간 지연 )을 계산하는 제 3 단계; 상기 싱크 노드에 의해 초기화 웅답 패 킷 수신에 층돌이 존재하는 지의 여부를 결정하는 제 4 단계; 상기 제 4 단계에서 초기화 응답 패킷 수신에 충돌이 존재하지 않으면, 상기 싱크 노드가 상기 제 3 단 계에서 계산된 왕복 시간 지연 을 이용하여 왕복 시간 지연이 작은 순으 로 노드들을 정렬하는 제 5 단계; 상기 싱크 노드에 의해 변수 0 가 1로 설정되고

1-번째 노드의 대기 시간 (^ ¹ , ¹ )이 "0' '으로 설정되는 제 6 단계; 상기 싱크 노드에 의해 1-번째 노드의 데이터 패킷이 상기 싱크 노드에 수신되기 시작하는 시각의 최

대값 ( 1, 1 )이 계산되는 제 7 단계; 상기 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하는 제 8 단계 ; 상기 제 8 단계에서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면 상기 변수 (k)를 k+1로 설정하는 제 9 단계; 상기 싱크 노드에 의해 k-번째 노드의 데이터 패킷이 상기 싱크 노드에 도착하는 시각의 최소 严 in

값(쬬 i )이 계산되는 제 10 단계; 상기 싱크 노드에 의해 상기 k-번째 노드의 대기 시간 이 계산되는 제 11 단계; 상기 싱크 노드에 의해 상기 k-번째 노

5

대체용지 (규칙 제 26조) 드의 데이터 패킷이 상기 싱크 노드에 도착하는 시각의 최대값 ( ^{' '} )을 계산한 후 상기 제 8 단계로 진행되는 제 12 단계; 상기 제 8 단계에서 상기 변수 (k)가 마 지막 -번째 (K—번째) 보다 작지 않으면， 상기 싱크 노드에 의해 1-번째 비콘 패킷이 제 3 설정 시각 ( 0, 1 )에 다수의 노드들에 방송되는 제 13 단계; 상기 성크 노드가 마지막—번째 (K-번째) 노드 데이터 패킷을 수신한 후 또는 상기 제 13 단계에 의한 闕 襲^

1-번째 비콘 패킷 방송후 제 4 설정 시간 (찌 1)을 대기하는 ^ 14 단계 ; 상기 싱크 노드에 의해 상기 싱크 노드와 상기 k-번째 노드 간 왕복 시간 지 연 (<5 _k , _{n )} 이 계산되는 제 15 단계; 상기 싱크 노드가 상기 제 15 단계에서 계산된 왕복 시간 지연 ( ^6k , ⁿ )을 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬하 는 제 16 단계 ; 상기 싱크 노드에 의해 1 사이클 동안 변화할 수 있는 노드의 왕복 시간 지연 변동폭 (^max )이 계산되는 제 17 단계; 상기 변수 (k)를 1로 설정하고， 상기 싱크 노드가 n-번째 사이클에서 1—번째 노드에게 부여되는 시간 지연 을 "0"으로 설정하고， n-번째 사이클에서 1-번째 노드의 데이터 패킷이 수신되기 擁

시작되는 시각의 최대값 ( ^ )을 계산하는 제 18 단계; 상기 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하는 제 19 단계; 상기 제 19 단계에서 상기 변수 00가 마지막 -번째 (K-번째) 보다 작으면 상기 변수 (k)를 k+1로 설정하는 제 20 단계; 상기 싱크 노드가 n-번째 사이클에서 k-번째 노드의 데이터 패킷이 수

6

대체용지 (규칙 제 26조) 신되기 시작되는 시각의 최소값 ( 을 계산하는 제 21 단계; 상기 싱크 노드 가 n—번째 사이클에서 k-번째 노드에게 부여되는 시 지연 ( ^W «,rt )을 계산하는 제 22 단계; 상기 싱크 노드가 n-번째 사이클에서 k-번째 1 노드의 데이터 패킷이 수신 되기 시작되는 시각의 최대값 ( )을 계산한 후 상기 제 19 단계로 진행되는 제 23 단계; 상기 제 19 단계예서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작지 않으면， 상기 싱크 노드에 의해 비콘 패킷 방송이 되는 지의 여부가 결정되는 제 24 단계; 및 상기 제 24 단계에서 비콘 패킷 방송이 되지 않으면 종료하는 제 25 단계를 포함하는 것을 특징으로 한다.

상기 일실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법은 상기 제 24 단계에서 싱크 노드에 의해 비콘 패킷 방专이 결정 되면， 상기 싱크 노 드에 의해 n—번째 사이클의 비콘 패킷이 방송되는 시각 )에 비콘 패킷이 노드 들에 방송되는 제 26 단계; 상기 싱크 노드가 마지막 -번째 (K-번째) 노드 데이터 패 킷을 수신한 후 또는 상기 n-번째 사이클에서 마지막 -번째 노드의 데이터 패¾이 수신되기 시작되는 시각의 최대값 ( ^ )을 대기하는 제 27 단계; 및 상기 싱크 노드에 의해 사이클이 1만큼 증가된 후 상기 제 15 .단계로 진행되는 제 28 단계가 수행될 수 있다.

상기 일실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법은 상기 제 4 단계에서 초기화 웅답 패킷 수신에 충돌이 존재하면， 상기 싱크 노드에

대체용지 (규칙 제 26조) 의해 재초기화 패킷이 노드들에 방송되는 제 29 단계; 상기 싱크 노드에 의해 제 2 설정 시간 ( rein ) 만큼 재초기화 응답 패킷이 수신되는 제 30 단계; 상기 싱크 노 드가 상기 제 30 단계에서 수신한 재초기화 웅답 패킷으로부터 상기 싱크 노드와 노드들 간 왕복 시간 지연 ( ^ ^ )을 계산하는 제 31 단계 ; 및 상기 싱크 노드에 의해 재초기화 응답 패¾ 수신에 층돌이 존재하는 지의 여부를 결정하는 제 32 단 계가 수행되며: 상기 제 32 단계에서 재초기화 웅답 패킷 수신에 층돌이 존재하면 상기 제 29 단계로 진행될 수 있다.

상기 일실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법은 상기 제 32 단계에서 재초기화 응답 패킷 수신에 충들이 존재하지 않으면 상기 제 5 단계로 진행될 수 있다.

상기 일실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 1 설정시간 은 다음 수학식 1이에 의해 결정될 수 있다.

[수학식 101]

[여기서， ^；구^^는 싱크 노드와 노드 간 왕복시간 지연의 최대값으로 서 다음 수학식 102에 의해 결정되고， 는 초기화 패킷 길이의 시간 환산 값이며, ^¾« >는 초기화 웅답 패킷 길이의 시간 환산값이며， 는 노드가

8

대체용지 (규칙 제 26조) 초기화 패킷 수신 완료후에 초기화 웅답 패킷을 송신하기까지 소요되는 시간임

[수학식 102]

(I"은 모템의 최대 통신반경, C는 음파 속도)] 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 싱크 노드와 다수의 노드들 간 왕복 시간 지연 )은 다음의 수학식 103에 의해 결정될 수 있다. [수학식 Κ)3]

[여기서 , t _rRP H)는 노드 (H)로부터 수신된 초기화 웅답 패킷의 수신 시각이 고， i 는 초기화 패킷 방송 시간임] 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케쥴링 방법에 있어서， 상기 1-번째 노드의 데이터 패킷이 상기 싱크 노드에 수신되기 시작하는

9

대체용지 (규칙 제 26조) 雞

시각의 최대값 ( )은 다음의 수학식 1 ₀₈ 에 의해 결정될 수 있다ᅳ

[수학식 108]

[여기서, 0, 1은 싱크 노드에 의한 최초의 비 패킷 방송 시각이며， 는 비콘 패킷 길이의 시간 환산값이며， ^ ¹ , ¹ 은 1-번째 노프의 왕복시간 지연이며, ^r i은

1-번째 노드의 싱크 노 H와의 왕복시간 지연이 획득된 시점이며 , V은 싱크 노드와 노드 간의 최대 상대 속력임] 상기 일실시형태에 의한， 수증 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 k-번째 노드의 데이터 패킷이 상기 싱 3 노드에 도착하는 시각의 최 소값 (화 )은 다음의 수학식 113에 의해 결정될 수 있다.

[수학식 113]

[여기세 은 k-번째 노드의 왕복 시간 지연이고, ^는 ^！가 획득된 시 각임]

10

대체용지 (규칙 제 26조) 상기 일실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 k-번째 노드의 대기 시간 은 다음의 수학식 114에 의해 결정될 수 있다.

[수학식 114]

[여기서, max{A,B}는 A, B 둘 중에서 큰 값을 선택하는 함수이고， k-i-번째 노드의 데이터 패¾이 싱크 노드에 도착하는 시 각의 최대값으로서 아래의 수학식 112에 의해 결정되며, 씨ᅳ ^" : 은 k-1-번째 노드의 데이터 패킷 길이의 시간환산 값임

[수학식 112]

1- ₀ .1 + + 1,1 — ^

은 k-i-번째 노드의 왕복시간 지연이: a, feᅳ ι,ι은 k-i-번째 노 ᅳ의 대기시간이며， 은 1，1이 획득된 시간임)] 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에

11

대체용지 (규칙 제 26조) 있어서， 상기 싱크 노드와 상기 k-번째 노드 간 왕복 시간 지연 ( ⁵ k.n)은 다음의 수 학식 115에 의해 결정될 수 있다.

[수학식 115]

[여기서， 은 n-번째 사이클의 비콘 패킷이 방송되는 시각이고， 은 _n -번째 사이클에서 _k -번째 노드의 데이터 패킷의 수신이 시작되는 시각이며,

，"은 _n -번째 사이클에서 _k -번째 노드에게 부여되는 시간 지연이며， n은 _n - 번째 사이클에서의 비콘 길이 시간 환산값임]

상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서, 상기 1 사이클 동안 변화할 수 있는 노드의 왕복 시간 지연 변동 폭 ( _max) 은 다음의 수학식 1 ₁₆ 에 의해 결정될 수 있다.

[수학식 116]

[여기서， n- l은 ( _n -l)-번째 사이클에서의 데이터 패킷의 수신 시작 시각

12

대체용지 (규칙 제 26조) oil

J 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어세 각 노드의 (n-1)-번째 사이클에서 데이터 패¾의 수신 시각 (^, ^η ᅳ 1)과 _η - 번째 사이클에서 데이터 패킷의 수신 시각 ( ， η)의 차이는 다음의 수학식 ₁₁₇ 과 같 이 근사할 수 있다.

[수학식 117] 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 2 설정 시간 (쭈 ein )은 다음의 수학식 105에 의해 결정될 수 있 다.

[수학식 105]

¾ft ^{: == '} ¾； ax + ^^m^^ ^:': ^mRP^ ^'''' ^

[여기서， ^DRIR Q는 재초기화 패킷 길이의 시간 환산값이고, 는 재초 기화 웅답 패킷 길이의 시간 환산값임]

13

대체용지 (규칙 제 26조) 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서, 상기 n-번째 사이클에서 1-번째 노드의 데이터 패킷이 수신되기 시작되는 시각의 최대값 ( 피 )은 다음의 수학식 118에 의해 결정될 수 있다.

[수학식 118]

[여기서, ^di ,«- i은 n-1-번째 사이클에서의 1-번째 노드의 왕복 시간 지연이 며， 찌 ^, «은 n-번째 사이클에서 1-번째 노드의 데이터 패킷 길이의 시간 환산값임] 상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서, 상기 싱크 노드가 n-번째 사이클에서 k-번째 노드의 데이터 패킷이 수신되 기 시작되는 시각의 다음의 수학식 119에 의해 계산될 수 있다.

[수학식 119]

14

대체용지 (규칙 제 26조) [여기서， * , ^η - ι은 η-1-번째 사이클에서의 번째 노드의 왕복 시간 지연 임]

상기 일실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 싱크 노드가 n-번째 사이클에서 k-번째 노드에게 부여되는 시간 지 연 (Wk^ )은 다음의 수학식 o에 의해 계산될 수 있다ᅳ

[수학식 120]

^^ 铺聽雜 辆， ,

[여기서， 은 n-번째 사이클에서 k-1-번째 노드의 데이터 패킷 이 수신되기 시작되는 시각의 최대값임]

상기 일실시형태에 의한, 수증 무선 이동 네트워크를 위한 스케쥴링 방법에 있어서, 상기 싱크 노드가 n-번째 사이클에서 k-번째 노드의 데이터 패¾이 수신되

.M

t ^{' '} ： ^' ■

기 시작되는 시각의 최대값 ( ^K , ⁿ )은 다음의 수학식 121에 의해 계산될 수 있 다.

15

대체용지 (규칙 제 26조) [수학식 121]

은 n—번째 사이클에서 k-번째 노드의 데이터 패킷 길이의 시간 환산값 임] 상기의 다른 목적을 달성하기 위해 본 발명의 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법은 전송 스케줄을 포함하고 있는 비콘 패 킷올 방송하는 하나의 싱크 노드와, 상기 싱크 노드의 비콘 패킷을 수신하여 전송 스케쥴에 따라서 데이터 패킷을 상기 싱크 노드로 전송하는 다수의 노드들로 구성 된 네트워크 토폴로지에서 시분할 다중접속을 하는, 수중 무선 이동 네트워크를 위 한 스케줄링 방법으로서 : 상기 싱크 노드가 초기화 과정을 수행하는 제 1 ' 단계; 상기 싱크 노드가 데이터 패킷 수신 순서를 결정한 후 n-번째 사이클에서 1-번째 노드에게 부여되는 시간 지연 ( ^ ¹ '" )을 0으로 설정하는 제 2 ' 단계; 상기 싱크 노 드가 n-번째 사이클에서 1-번째 노드의 왕복시간지연 ( 'ᅳ" )을 추정하고, 1-번째 노 드의 데이터 패킷 수신 완료 시점 을 계산하는 제 3 ' 단계; 상기 싱크 노드에 의해 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하는 제 4 ' 단계; 상기 제 4 ' 단계에서 상기 변수 (k)가 마지막 -번째 (K—변째) 보다 작으면， 상기 싱크 노드가 상기 변수 (k)를 k+1로 설정하는 제 5 ' 단계; 상기 싱크 노드가 n-번째 사이 클에서 k-번째 노드의 왕복시간지연 을 추정하는 제 6 ' 단계; 상기 싱크 노드

16

대체용지 (규칙 제 26조) 가 상기 제 6' 단계에서 추정된 k-번째 노드의 왕복시간지연 을 이용하여， k- 번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할 때, k-번째 노드의 데이 터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 (^ )을 계산하는 제 T 단계; 상기 싱크 노드가 상기 제 T 단계에서 계산된 }ί-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 을 이용하여 k—번째 노드의 대 기 시간 ( ^ " )을 계산하는 제 8' 단계; 및 상기 싱크 노드가 상기 제 T 단계에서 계산된 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정 값 과 상기 제 8' 단계에서 계산된 k—번째 노드의 대기 시간 (^ " )을 이용하 여 k-번째 노드의 데이터 패킷이 수신 완료되는 시각의 추정값 (^ 을 계산한 후 상기 제 4' 단계로 진행되는 제 9' 단계를 포함하는 것을 특징으로 한다.

상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법 에 있어서， 상기 제 4' 단계에서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작지 않으면, 상기 싱크 노드가 비콘 패킷의 방송 유무를 판단하는 제 10' 단계를 더 포 함하고; 상기 제 10' 단계에서 비콘 패킷이 방송되지 않으면 모든 절차를 종료할 수 있다.

상기 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법 에 있어서， 상기 제 10' 단계에서 비콘 패킷이 방송되면, 상기 싱크 노드는 n-번째 사이클에서 싱크 노드가 비콘 패킷을 방송하기 시작하는 시각 에 비콘 패킷을 방송하는 제 11' 단계; K-번째 노드의 데이터 패킷 수신이 완료되었거나 K-번째 노 드의 데이터 패킷이 수신 완료되는 시각의 추정값 이 초과되는 제 12' 단계;

17

대체용지 (규칙 제 26조) 상기 싱크 노드는 n-번째 사아클에서 k-번째 노드의 왕복시간지연 (^.")을 계산하 고， 왕복 시간 지연 획득 유효성 값( ^Ui ' ^k 및 ^U2 ' ^k ) 및 가장 최근에 획득된 왕 복 시간 지연 관련 정보 )를 갱신하는 제 13' 단계; 및 상기 싱크 노드가 η 을 1만큼 증가시킨 후 상기 제 2' 단계로 진행되는 제 14' 단계를 포함할 수 있다. 상기 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법 에 있어서， 상기 제 Γ 단계에서 상기 싱크 노드는 다음의 [수학식 201]과 같이 초 기화 과정을 수행할 수 있다.

[수학식 201] ri- 1, fci, _f c = 1， ¾ = = ¾ ο, <¾ = C _D

["υ는 η-번째 사이클에서 , (η-1)-번째 사이責에서의 k-번째 ^; 노드의 왕복 ^' 시간지연 획득의 유효성을 나타내는 변수이며; ^U 2, k는 _n -번째 사이클에세 (n-2)- 번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의 유효성을 나타내는 변수이 며 ^' ; ^α 는 가장 최근에 획득된 k-번째 노드의 왕복시간지연이며; 는 "^가 얻어진 사이클이며 ; ^S *. ⁰ 는 싱크 노드와 각 노드간의 최초 왕복시간지연이며 ; ^Co 는 1—번째 사이클 이전의 지속시간이며; 는 다음의 수학식 202와 같이 추정되어 정해짐 ]

18

대체용지 (규칙 제 26조) [수학식 202]

[ ^D k, i은 1-번째 사이클에서 k-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임] 상기 다른 실시형태에 의한, 수중 무선 이동 네트쒀크를 위한 스케즐링 방법 에 있어서， 상기 제 3 ' 단계는 최근 두 사이클 동안 1-번째 노드의 왕복시간지연이 성공적으로 획득된 경우에는 다음의 [수학식 203]과 같이 n-번째 사이클에서 1-번 째 노드의 왕복시간지연 을 추정하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 을 계산할 수 있다.

[수학식 203]

[ ^는 가드 시간이고, 1은 n-1-번째 사이클에서 획득된 1-번째 노드의 왕복시간지연이며， ^Α "은 η-번째 사이클에서 비콘 패킷 길이를 시간으로 환산한

19

대체용지 (규칙 제 26조) 값이며, ， _^ 은 n-i-번째 사이클에서 1-번째 노드의 데이터 패킷 수신되기 시작하는 시각이며， 긔은 다음의 수학식 204와 같음]

[수학식 204]

[ ,„— ² 은 _n _2_번째 사이클에서 획득된 1-번째 노드의 왕복시간지연이며， ，" - 2은 n-2-번째 사이클에서 1-번째 노드의 데이터 패킷이 싱크 노드에 수신되 기 시작하는 시각임]

상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법 에 있어서， 상기 [수학식 203]은 다음과 같은 연립 방정식인 [수학식 206]을 풀어 서 얻어질 수 있다.

[수학식 206]

20

대체용지 (규칙 제 26조) Γ ·"은 η-번째 사이클에서 1—번째 노드의 데이터 패킷 수신 시각 에 대한 추정값임] 상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케쥴링 방법 에 있어서， 상기 제 3 ' 단계는 최근 두 사이클 동안 1" "번째 노드의 왕복시간지연이 1번 이상 성공적으로 획득되지 못한 경우에는 다음의 [수학식 205]와 같이 η-번째 사이클에서 1-번째 노드의 왕복시간지연 을 추정하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 ( ^ei )을 계산할 수 있다.

[수학식 205]

[S _{m ax} 는 왕복시간지연의 최대값이고， ^α 1은 가장 최근에 획득된 1-번째 노 드의 왕복시간지연이며， "m ax는 싱크 노드와 _k -번째 노드간의 최대 상대속도이며， ^一工은 n-1-번째 사이클의 지속시간이며， 은 1-번째 노드의 왕복시간지연이 획득 된 가장 최근 사이클이며， ^C m in은 수중에서의 최소 음파 전달 속도임 ] 상기 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법

21

대체용지 (규칙 제 26조) 에 있어서， 상기 제 6 ' 단계는 최근 두 사이클 동안 번째 노드의 왕복시간지연이 성공적으로 획득된 경우에는， 다음의 [수학식 20 과 같이 n-번째 사이클에서 k-번 째 노드의 왕복시간지연 위을 추정할 수 있다.

[수학식 207]

⁼ ¾rt- I + ， 1ᅳ¾ — 1 ) 은 n-1-번째 사이클에서 획득된 k-번째 노드의 왕복시간지연이며, →은 k-1-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정 값이며, 스은 n-i-번째 사이클에서 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각이며， ^X 은 다음의 수학식 211과 같음] [수학식 211]

X ^. ― ¾^--1： ~ ¾, ᅳ

— ² 는 η-2-번째 사이클에서 획득된 k-번째 노드의 왕복시간지연이며， ,„- ₂ 는 _n — 2-번째 사이클에서 k—번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각임]

22

대체용지 (규칙 제 26조) 상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법 에 있어서， 상기 제 6 ' 단계는 최근 두 사이클 동안 k-번째 노드의 왕복시간지연이 1번 이상 성공적으로 획득되지 못한 경우에는 다음의 [수학식 212]와 같이 n-번째 사이클에서 k—번째 노드의 왕복시간지연 을 추정할 수 있다. [수학식 212]

는 *^ ^가 얻어진 사이클임] 상기 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법 에 있어서， 상기 제 7 ' 단계에서， 상기 k-번째 노드의 1 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 )은 다음의 [수학식 213]과 같이 계산될 수 있다.

[수학식 213]

23

대체용지 (규칙 제 26조) 상기 다른 실시형태에 의한， 수중 무선 이동 네트쒀크를 위한 스케즐링 방법 에 있어서， 상기 제 8 ' 단계에서， 상기 k-번째 노드의 대기 시간 ( "^. " )은 다음의 [수학식 214]와 같이 계산될 수 있다.

[수학식 214]

상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법 에 있어서, 상기 제 9 ' 단계에서, 최근 두 사이클 동안 k-번째 노드의 왕복시간지 연이 성공적으로 획득된 경우쎄는 k-번째 노드의 데이터 패킷이 싱크 노드에서 수 신 완료되는 시각의 추정값 ( ^e * )은 다음의 [수학식 215]와 같이 계산될 수 있다 _; . [수학식 215]

[ ,η은 _η -번째 사이클에서 _k -번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임] 상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케쥴링 방법

24

대체용지 (규칙 제 26조) 에 있어서, 상기 제 9 ' 단계에서， 최근 두 사이클 동안 k-번째 노드의 왕복시간지 연이 1번 이상 성공적으로 획득되지 못한 경우에는 k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정값 은 다음의 [수학식 216]과 같이 계산될 수 있다.

[수학식 216]

상기 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법 에 있어서， 상기 제 13 ' 단계에서， 상기 왕복 시간 지연 획득 유효성 값 ( "ι· 및

" ² . * )을 갱신하기 위해서， 다음의 [수학식 21기과 같이 모든 노드들에 대하여 상 기 왕복 시간 지연 획득 유효성 값 ( " ² . )을 갱신하고, n-번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하였으면, 다을의 [수학식 218]과 같이 하 며, n-번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하지 못한 경 우에는 다음의 [수학식 219]와 같이 하며, 상기 가장 최근에 획득된 왕복 시간 지 연 관련 정보 는 다음의 [수학식 220]와 같이 같이 갱신하몌 또한, 상기 왕복 시간 지연 획득 유효성 값 ( ^{U l} ^ )이 1인 경우에는， 다음의 [수학식 221]과 같이 n- 번째 사이클에서 k-번째 노드의 왕복시간지연 을 계산하고, 최근에 획득된 왕 복 시간 지연 관련 정보 ( ^α )를 갱신할 수 있다.

25

대체용지 (규칙 제 26조) [수학식 217]

u2,k ~ ^U l c ,

[수학식 218]

[수학식 219]

[수학식 220]

[수학식 221]

¾n

상기 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법서， k-번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신하여 왕복시간

26

대체용지 (규칙 제 26조) 지연 ( ⁶ ")을 가지면서 싱크 노드에 k-번째 노드의 데이터 패킷이 수신되기 시작하 는 시각 (P^ )는 다음의 [수학식 208]과 같이 계산되며， 이때， ^p ^ ^e ' ^{~ i} 인 경우에 는 다음과 같이 [수학식 209]를 풀어서， 다음의 [수학식 210]과 같이 k-번째 노드 의 왕복시간지연을 추정하며， 상기 [수학식 210]에서 *·"은 상기 [수학식 211]과 같을 수 있다.

[수학식 208]

[수학식 209]

^k,n ~ ¾,n - 1： + J¾ _i¾ (i _A¾n .― ί¾. _η - ι )

[수학식 210] 二 ― ψ ~~ ^" &k - l ^" 卜瑪, ― i

상기의 목적을 달성하기 위해 본 발명의 또 다른 실시형태에 의한, 수중 무 선 이동 네트워크를 위한 스케줄링 방법은 전송 스케줄을 포함하고 있는 비콘 패킷

27

대체용지 (규칙 제 26조) 을 방송하는 하나의 싱크 노드와， 상기 싱크 노드의 비콘 패킷을 수신하여 전송 스 케쥴에 따라서 데이터 패킷을 상기 싱크 노드로 전송하는 다수의 노드들로 구성된 네트워크 토폴로지에서 시분할 다중접속을 하는, 다항식 보간법을 이용한 수중 네 트워크 스케줄링 방법으로서: 상기 싱크 노드가 초기화 과정을 수행하는 제 1" 단 계; 상기 싱크 노드가 데이터 패킷 수신 순서를 결정함 후 n-번째 사이클에서 1-번 째 노드에게 부여되는 시간 지연 을 0으로 설정하는 제 2" 단계; 상기 싱크 노드가 n-번째 사이클에서 1-번째 노드의 왕복시간지연 ( ^,„. )을 추정하고， 1-번째 노드의 데이터 패킷 수신 완료 시점 을 계산하는 제 3" 단계; 상기 싱크 노드에 의해 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하는 제 4" 단계; 상기 제 4" 단계에서 상기 변수 (k)가 마지막—번째 (K-번째) 보다 작으면， 상기 싱크 노드가 상기 변수 (k)를 k+1로 설정하는 제 5" 단계; 상기 싱크 노드가 n-번째 사이 클에서 k-번째 노드의 왕복시간지연 을 추정하는 제 6" 단계; 상기 싱크 노드 가 상기 제 6" 단계에서 추정된 k-번째 노드의 왕복시간지연 (^," )을 이용하여, k- 번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할 때, k-번째 노드의 데이 터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 ( ^^ᅵ을 계산하는 제 7" 단계; 상기 싱크 노드가 상기 제 7" 단계에서 계산된 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 을 이용하여 k-번째 노드의 대 기 시간 ( ^ ' " )을 계산하는 제 8" 단계; 및 상기 싱크 노드가 상기 제 7" 단계에서 계산된 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정

28

대체용지 (규칙 제 26조) 값 과 상기 제 8" 단계에서 계산된 k-번째 노드의 대기 시간 ( ^^ "；！을 이용하 여 k-번째 노드의 데이터 패킷이 수신 완료되는 시각의 추정값 을 계산한 후 상기 제 4" 단계로 진행되는 제 9" 단계를 포함하는 것을 특징으로 한다. 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케쥴링 방법은 상기 제 4" 단계에서 상기 변수 (k)가 마지막—번째 (K-번째) 보다 작지 않으 면， 상기 성크 노드가 비콘 패킷의 방송 유무를 판단하는 제 10" 단계를 더 포함하 고; 상기 제 10" 단계에서 비콘 패킷이 방송되지 않으면 모든 절차를 종료할 수 있 다. 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법은 상기 제 10" 단계에서 비콘 패킷이 방송되면, 상기 싱크 노드는 n-번째 사 이클에서 싱크 노드가 비콘 패킷을 방송하기 시작하는 시각 에 비콘 패킷을 방송하는 거 1 11" 단계; K-번째 노드의 데이터 패킷 수—신이 완료되었거나 K-번째 노 드의 데이터 패킷이 수신 완료되는 시각의 추정값 어 초과되는 제 12" 단계; 상기 싱크 노드는 n-번째 사아클에서 k-번째 노드의 왕복시간지연 을 계산하 고， 왕복 시간 지연 획득 유효성 값( , ^¾ ) 및 가장 최근에 획득된 왕복 시간 지 연 관련 정보 ， )를 갱신하는 제 13" 단계 ; 및 상기 성크 노드가 η을 1만큼 증가시킨 후 상기 제 2" 단계로 진행되는 제 14" 단계를 포함할 수 있다.

29

대체용지 (규칙 제 26조) 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 1" 단계에서 상기 싱크 노드는 다음의 [수학식 301]과 같 이 초기화 과정을 수행할 수 있다.

[수학식 301]

n = 1， u _k = 1, l _k = 0, a _k = 6 _kt0 , C ₀ = C _D

[^는 ^보다 작거나 같은 자연수이고; m = ² ' ³ '- 'A 이며 ; "L*는 ^번 째 사이클에서, (η-1)-번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의 유효 성을 나타내는 변수이며; ^{U n} ' ^k ^ n-번째 사이클에서, (n-m)-번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의 유효성을 나타내 변수이며 ; ^α 는 가장 최 근에 획득된 k-번째 노드의 왕복시간지연이며; 는 α ^가 얻어잔 사이클이며; δ . ₀ 는 싱크 노드와 각 노드간의 최초 왕복시간지연이며; ^는 1-번째 사이클 이전 의 지속시간이며 ; 는 다음의 수학식 302와 같이 추정되어 정해짐]

[수학식 302]

κ

C _D = min{ii, ₀ , ^■■ ·, ½, ₀ }+∑D _k ,i

k= 1

[ ^D k, ⁱ 은 1-번째 사이클에서 k-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임]

30

대체용지 (규칙 제 26조) 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 3" 단계는 최근 M 사이클 동안 1-번째 노드의 왕복시간지 연이 성공적으로 획득된 경우가 ^/ο (2 이상인 자연수라 함)회 이상인 경우에는 다음 의 [수학식 303]과 같이 η-번째 사이클에서 1-번째 노드의 왕복시간지연 (^," )을 추정하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 ( ^ei )을 [수학식 305]와 같이 계산할 수 있다.

[수학식 303]

지나는 최소 차수의 다항식이며; ^, 은 η—번째 사이 #에서 1-번째 노드의 데이터 패킷 수신 시각 ( ^ " )에 대한 추정값이며; ^. "은 _η -번째 사이클에서 싱크 노드가 비콘 패킷을 방송하기 시작하는 시각이며; ^Db ' n-번째 사이클에서 비콘 패킷 길 이홑 시간으로 환산한 값이며; 히"은 다음 수학식 304와 같이 값을 제한함]

31

대체용지 (규칙 제 26조) [수학식 304]

, _n = min{ _max ,ᅳ^， J [ _max 는 왕복시간지연의 최대값임]

[수학식 305]

은 _η -번째 사이클에서 1-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값이며; ^" ^는 가드 시간임 ] 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 [수학식 303]은 다음과 같이 반복적으로 해가 구해질 수 있 다.

1) ^,"의 초기값을 ^,η ⁼ ο, _η + Α,η + «ι 또는 ϊΐ,η ⁼ ^Ο, ^{+ D} b,n + ^max 과 같이 정하고，

2) 상기 초기값 ^έ ι,"을 이용하여 [수학식 303]으로부터 ."을

= < ( i,J과 같이 계산하며 ,

3) 상기 2)에서 계산된 ᅳ"을 이용하여 "을 ^{== ί} ο,η +

과 같이 계산하고，

32

대체용지 (규칙 제 26조) 4) 상기 3)에서 계산된 ^ι,"으로부터 을 ^, „ = < (U과 같이 계산 하며，

5) 상기 4)에서 계산된 을 이용하여 을 1，" = n+ " + ^ᅳ ^η 과 같이 계산하고,

6) 상기 5)에서 계산된 으로부터 ^ι,η을 ^- dd'J과 갈이 계산 하는 과정을 설정된 횟수만큼 반복한 후에， 최종적으로 계산되는 값을 ，"과 으로 확정함 (이때， 반복 횟수를 정하지 않고， 이전에 계산된 ，"과 현재 계산 된 1，™의 차이가 일정값 이하인 경우에 반복과정을 층단하는 방법이나 또는 이전 에 계산된 1，"과 현재 계산된 "의 차이가 일정값 이하인 경우에 반복과정을 증 단함) 상기 또 다른 실시형태에 의한， 수중 무선 이통 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 3" 단계는 최근 사이클 동안 1-번째 노드의 왕복시간 지연이 성공적으로 획득된 경우가 ^Jo 회 미만인 경우에는, 다음의 [수학식 306]과 같이 n-번째 사이클에서 1—번째 노드의 왕복시간지연 (^'"j을 추정하고， 1-번째 노 드의 데이터 패킷 수신 완료 시점 )을 계산할 수 있다，

33

대체용지 (규칙 제 26조) [수학식 306] ,η = min{5 _max , ₁ +2v _mAX C _n - ₁ {n-l _l )/c _min }

ei + D _b , _n 十 δ _ι>η

[ ^α 1은 가장 최근에 획득된 1-번째 노드의 왕복시간지연이며, 는 싱크 노드와 k-번째 노드간의 최대 상대속도이며 , C„— 은 _n _L -번째 사이클의 지속시간 이며， 은 1-번째 노드의 왕복시간지연이 획득된 가잠 최근 사이클이며, ^C min은 수증에서의 음파 전달 속도의 최소값임] 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 6" 단계는 최근 사이클 동안 k-번째 노드의 왕복시간 지연이 성공작으로 획득된 경우가 。회 이상인 경우에는， 다음의 [수학식 30기과 같이 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정할 수 있다.

[수학식 307]

나는 최소 차수의 다항식이고; — 는 ("ᅳ 사이클에서 k-번째 노드의 유효 한 왕복시간지연 값이며; - ¹ 은 (k-l)-번째 노드의 데이터 패킷이 싱크 노드에서

34

대체용지 (규칙 제 26조) 수신 완료되는 시각의 추정값임 ] 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 6" 단계에서 k—번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신하여 왕복시간지연 을 가지면서 싱크 노드에 k-번째 노드의 데이 터 패킷이 수신되기 시작하는 시각 ( ^ )은 다음 [수학식 308]과 같이 계산될 수 있 다.

[수학식 308]

Pk ~ Ο, η + ^b, n + ^k, n 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 6" 단계는 ^{P > e} k→ 인 경우에는 다음의 [수학식 309]와 같이 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정활 수 있다. [수학식 309]

35

대체용지 (규칙 제 26조) 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 있어서， 상기 [수학식 ^' 309]는 다음과 같이 반복적으로 해가 구해질 수 있

1' ) 의 초기값을 A a ^ 0,n + + fc 또는 ^t k,n ― *0,η + ·« + ax과 같이 정하고，

2') 상기 초기값 을 이용하여 [수학식 309]로부터 ^^을

^fe, ⁼ QkHk,n)과 같이 계산하며 ,

3') 계산된 을 이용하여 ^,η을 * Α·,η = t ⁽⁾ , _n + Α,η + ^k,n jZ). 갈이 계산 하고,

4') 상기 3')에서 계산된 으로부터 ^ 을 , _n = ^Q _' 과 같이 계 산하며，

5') 상기 4')에서 계산된 을 이용하여 을 ik,n ― *0,n + ,» + ^k,n,과 같이 계산하고,

6') 상기 5')에서 계산된 으로부터 을 ⁼ 과 같이 계산하는 과정을 설정된 횟수만큼 반복한 후에， 최종적으로 계산되는 값을 ^, 과 으로 확정함 (이때 , 반복 횟수를 정하지 않고 , 이전에 계산된 ^^과 현재 계산

36

대체용지 (규칙 제 26조) 된 ^^의 차이가 일정값 이하인 경우에 반복과정을 충단하는 방법이나 또는 이전 에 계산된 "과 현재 계산된 ^"의 차이가 일정값 이하인 경우에 반복과정을 증 단함) 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서, 상기 ^ 은 다음의 [수학식 310]과 같이 값을 제한할 수 있다. [수학식 310]

, n 二 mirr _{m ax} , S _ki 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 6" 단계는 최근 ^M 사이클 동안 k-번째 노드의 왕복시간 지연이 성공적으로 획득된 경우가 ^회 미만인 경우에는， 다음의 [수학식 311]과 같아 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정할 수 있다. [수학식 311]

, _n = max{ 0, _k - 2v _{m ax} C _n _ _! ( - l _k )/ c _{m in} } 상기 또 다른 실시형태에 의한， 수증 무선 이동 네트워크를 위한 스케즐링

37

대체용지 (규칙 제 26조) 방법에 있어서， 상기 제 7" 단계에서 상기 k—번째 노 H의 데이터 패킷이 싱크 노드 에 수신되기 시작하는 시각의 추정값 ( ^ 은 다음의 [수학식 308]에 의해 계산될 수 있다.

[수학식 308]

Pk ⁼ ^Ο, η + ^b, n + ^k, n 상기 또 다른 실시형태에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 있어서， 상기 제 8" 단계에서 상기 k-번째 노드의 대기 시간 ( ^ " )은 다음 의 [수학식 312]에 의해 계산될 수 있다.

[수학식 312]

w _{k> n} = max{0, e _k - p _k }

상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 9" 단계에서， 최근 사이클 동안 k-번째 노드의 왕복시 간지연이 성공적으로 획득된 경우가 ^o 회 이상인 경우에는 k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정값 은 다음의 [수학식 313]과 같이 계산될 수 있다.

38

대체용지 (규칙 제 26조) [수학식 313]

[ ^D ^"^ n-번째 사이클에서 k-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임] 상기 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 9" 단계에서， 최근 ^M 사이클 동안 1-번째 노드의 왕복시 간지연이 성공적으로 획득된 경우가 °회 미만인 경우에는 k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정값 은 다음의 [수학식 314]와 같이 계산될 수 있다.

[수학식 314]

ek = n + ^D b.n + w _k ,n + min{ ⁽ 5 _max , _k + 2t _max C _n _ i (n - l _k )/c _m[n } + D _k , _n

상기 또 다른 실시형태에 의한, 수중 무선 이통 네트워크를 위한 스케줄링 방법에 있어서， 상기 제 13" 단계에서， 상기 왕복 시간 지연 획득 유효성 값 ₍ ^m,fc)을 갱신하기 위해서 , 다음의 [수학식 315]과 같이 모든 노드들에 대하여 상기 왕복 시간 지연 획득 유효성 값( ^¾ ， )을 갱신하고, n-번째 사이클에서 k-번

39

대체용지 (규칙 제 26조) 째 노드의 데이터 패킷을 성공적으로 수신하였으면， 다음의 [수학식 316]과 같이 하며, n-번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하지 못한 경우에는 다음의 [수학식 31기과 같이 하며， 상기 가장 최근에 획득된 왕복 시간 지연 관련 정보 (^)는 다음의 [수학식 318]과 같이 갱신하며， 또한， 상기 왕복 시 간 지연 획득 유효성 값이 )이 1인 경우에는, 다음의 [수학식 319]와 같이 n-번 째 사이클에서 k-번째 노드의 왕복시간지연 (^.")을 계산하고， 가장 최근에 획득된 왕복 시간 지연 관련 정보 ( ^α )를 갱신할 수 있다.

[수학식 315]

+ l,k ᅳ , k

[수학식 316] Ul,k ⁼ 1

[수학식 317]

u _lik = 0

[수학식 318]

h二 max{l _k ,nui _;k },

40

대체용지 (규칙 제 26조) [수학식 319]

^k, n ⁼ tfc, _n ~ (t _Q , _n + D _{h n} + W _{k n} ) ,

[유리한 효과]

본 발명의 일실시형태에 의한, 수중 무선 이동 네트워크를 위한스케즐링 방 법에 의하면, 싱크 노드로부터 다수의 노드들로 초기화 패킷을 방송하고， 싱크 노 드가 다수의 노드들로부터 제 1 설정시간 동안 초기화 웅답 패킷을 수신하 몌 상기 싱크 노드가 수신한 초기화 응답 패킷으로부터 싱크 노드와 다수의 노드 들 간 왕복 시간 지연 (^ ⁷ ^^ )을 계산하며， 싱크 노드에 의해 초기화 웅답 패킷 수신에 충돌이 존재하는 지의 여부를 결정하고， 초기화 응답 패킷 수신에 충돌이 존재하지 않으면 싱크 노드가 계산된 왕복 시간 지연 ( ^ 을 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬하며, 싱크 ¾드예 의해 변수 (k)가 1로 설 정되고 1-번째 노드의 대기 시간 (^ ¹ ， ¹ )이 'Ό"으로 설정되며， 싱크 노드에 의해 1- 번째 노드의 데이터 패킷이 싱크 노드에 수신되 ί기 시작하는 시각의 최대 계산되며, 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하고, 변수 0 가 마지막 -번째 (K-번째) 보다 작으면 변수 (k)를 k+1로 설정하고， 싱크 노드에 의해 k-번째 노드의 데이터 패킷이 상기 싱크 노드에 도착하는 시각의

41

대체용지 (규칙 제 26조) 최소값 ( 1 )이 계산되며， 싱크 노드에 의해 k-번째 노드의 대기 시간 ( ^, ¹ ) 이 계산되며, 싱크 노드에 의해 k-번째 노드의 데이터 패킷이 싱크 노드에 도착하

는 시각의 최대값 ( )을 계산한 후 변수 (k)가 마지막 -번째 (K-번째) 보다 작지 않으면, 싱크 노드에 의해 1-번째 비콘 패킷이 제 3 설정 시각 fu )에 다수의 노드 들에 방송되고， 싱크 노드가 마지막 -번째 (K-번째) 노드 떼이터 패킷을 수신한 후

또는 1-번째 비콘 패킷 방송후 제 4 설정 시간 ( ， ¹ )을 대기하며， 싱크 노드에 의해 싱크 노드와 k-번째 노드 간 왕복 시간 지연 ( ⁵ k. _n )이 계산되며， 싱크 노드가 계산된 왕복 시간 지연 (6^ 을 이용하여 왕복 시간 지연이 작은 순으 로 노드들을 정렬하며， 싱크 노드에 의해 1 사이클 동안 변화할 수 있는 노드의 왕 복 시간 지연 변동폭 ( _max )이 계산되며, 변수 (k)를 1로 설정하고, 싱크 노드가 n-번째 사이클에서 1—번째 노드에게 부여되는 시간 지연 ( ¹ )을 "0"으로 설정하 고， n-번째 사이클에서 1-번째 노드의 데이터 패킷이 수신되기 시작되는 시각의 최 顯^

대값 ( )을 계산하며, 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하여 변수 (k)가 마지막 -번째 (K—번째) 보다 작으면 변수 (k)를 k+1로 설정하고, 싱크 노드가 n-번째 사이클에서 k—번째 노드의 데이터 패킷이 수신되기 시작되는

시각의 최소값 ( 을 계산하며， 싱크 노드가 n-번째 사이클에서 k-번째 노드

42

대체용지 (규칙 제 26조) 에게 부여되는 시간 지연 ( ^W k.rt )을 계산하며， 싱크 노드가 n-번째 사이클에서 k-번 째 노드의 데이터 패킷이 수신되기 시작되는 시각의 최대값 ( )을 계산한 후 변수 (k)가 마지막 -번째 (κ—번째) 보다 작지 않으면, 싱 a 노드에 의해 비콘 패킷 방 송이 되는 지의 여부가 결정되며， 비콘 패킷 방송이 되지 않으면 종료하도록 구성 됨으로써，

첫째， 수중에서 이동 노드의 항법 정보와 무관하게 동작하며，

둘째， 시간 동기화가 불필요하므로 시간 동기화를 위한 별도의 패킷 교환이 필요 없으므로 네트워크 수율을 향상시킬 수 있으며,

셋째， 스케쥴 정보가 절대 시간 기준이 아니라 시간 차이에 해당하는 정보에 의해서 결정되므로 각 노드들의 로컬 시각 정보가 서로 상이하더라도 정확하게 동 작하며,

넷째， 매 사이클 종료 시점에 싱크 노드와 노드간 왕복 시간 지연 정보에 대 한 정확한 값이 측정되므로 스케즐 정보는 시간이 지남에 따라서 오차가 누적되지 않아서 주기적인 재초기화가 팔요 없다는 뛰어난 효과가 있다. 또한, 본 발명의 다른 실시형태에 의한， 수중 부선 이동 네트워크를 위한 스 케줄링 방법에 의하면， 싱크 노드가 초기화 과정을 수행하고; 싱크 노드가 데이터 패¾ 수신 순서를 결정한 후 n-번째 사이클에서 1-번째 노드에게 부여되는 시간 지 연 ( ^ι, ^η )을 0으로 설정하며; 싱크 노드가 _η -번째 사이클에서 1-번째 노드의 왕복

43

대체용지 (규칙 제 26조) 시간지연 (^. " )을 추정하고， 1-번째 노드의 데이터 패킷 수신 완료 시점 ( ^ei )을 계 산하며; 싱크 노드에 의해 변수 (k)가 마지막 -번째 α-번째)보다 작은 지의 여부를 판단하며; 상기 판단에서 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면， 싱크 노드 가 상기 변수 (k)를 k+1로 설정하며; 싱크 노드가 n-번째 사이클에서 k—번째 노드의 왕복시간지연 을 추정하며; 싱크 노드가상기 추정된 k-번째 노드의 왕복시간 지연 ( " )을 이용하여， k-번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신 할 때， k—번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정 값 을 계산하며; 싱크 노드가 상기 계산된 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 ( ^ )을 이용하여 k—번째 노드의 대기 시 간 을 계산하며; 그리고 싱크 노드가 상기 계산된 _k -번째 노드의 데이터 패 킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 ( )과 상기 계산된 k-번째 노 드의 대기 시간 ( ^ " )을 이용하여 k-번째 노드의 데이터 패킷이 수신 완료되는 시 각의 추정값 ( ^e * )을 계산한 후 상기 판단 과정으로 진행되도록 구성됨으로써:

즉， 수중음향 무선 이동 네트워크 등과 같이 왕복시간지연이 크고 물리 계층 의 전송 속도가 낮은 네트워크 환경에서， 다수의 노 들이 싱크 노드로 데이터 패 킷을 시분할 다중접속 방식으로 전송하고자 할 때, 노드의 이동성에 따른 왕복시간 지연을 사이클 단위로 추적하여 싱크 노드가 노드 #로부터 데이터 패킷을 수신함에 있어 유휴 시간을 최소화함으로써 채널 사용 효율 향상을 통한 네트워크 효율이 크 게 향상될 수 있다는 뛰어난 효과가 있다. 특히, 노드 수가 증가할수록 네트워크 효율 향상 정도는 더욱 증가한다. 본 발명에 따른 수증 무선 이동 네트워크를 위한-

44

대체용지 (규칙 제 26조) 스케즐링 방법은 절대 시간 기준이 아니라, 시간 차이에 해당하는 정보에 의해서 결정되므로 , 각 노드들의 로컬 시각 정보가 서로 상이하더라도 정확하게 동작한다 . 따라서 시간 동기화가 필요 없으므로 시간 동기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 옹용 분야에서도 활용이 가능하다는 장점이 있다. 또한， 왕복 시간지연 정보에 대한 정확한 값이 매 사이클마다 얻어지므로， 오차가 누적되지 않고 주기적인 재초기화가 필요 없다는 뛰어난 효과가 있다. 본 발명의 또 다른 실시형태에 의한， 수중 무선 이동 네트워크를 위한 스케 즐링 방법에 의하면， 싱크 노드가 초기화 과정을 수행하고 ; 상기 싱크 노드가 데이 터 패킷 수신 순서를 결정한 후 n-번째 사이클에서 1-번째 노드에게 부여되는 시간 지연 ( i , n )을 0으로 설정하며; 싱크 노드가 n—번째 사이클에서 1-번째 노드의 왕 복시간지연 (^,« )을 추정하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 을 계산하며; 싱크 노드에 의해 변수 (k)가 마지막—번째 0 번째)보다 작은 지의 여부를 판단하며; 상기 판단에서 변수 0 가 마지막 -번째 (K-번째) 보다 작으면, 싱크 노드 가 변수 (k)를 k+1로 설정하며; 싱크 노드가 n-번째 사이클에서 k-번째 노드의 왕복 시간지연 을 추정하며; 싱크 노드가 상기 추정 ¾ k-번째 노드의 왕복시간지 연 을 이용하여, k-번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할 때, k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정 값 을 계산하며; 싱크 노드가 계산된 k-번째 노도의 데이터 패¾이 싱크 노드 에 수신되기 시작하는 시각의 추정값 ( ^ )을 이용하여 k-번째 노드의 대기 _: 시

45

대체용지 (규칙 제 26조) 간 을 계산하며; 상기 싱크 노드가 상기 계산된 _k _번째 노드의 데이터 패킷 이 싱크 노드에 수신되기 시작하는 시각의 추정값 ( ^Ρί 과 상기 계산된 k-번째 노드 의 대기 시간 ( ^ " )을 이용하여 k-번째 노드의 데이터 패킷이 수신 완료되는 시각 의 추정값 을 계산한 후 상기 판단 과정으로 진행되도록 구성됨으로써:

즉， 수중음향 무선 이동 네트워크와 같이 왕복시간지연이 크고 물리 계층의 전송 속도가 낮은 네트워크 환경에서， 채널 사용 효율 향상을 통한 네트워크 효율 을 향상시킬 수 있고， 시간 동기화가 필요 없으므로 시간 동기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 웅용 분야에서도 활용이 가능하며, 오 차가 누적되지 않고 주기적인 재초기화가 필요 없다는 뛰어난 효과가 있다. 특히, 노드 수가 증가할수록 네트워크 효율 향상 정도는 더욱 증가한다. 본 발명에 따른 수증 무선 이동 네트워크를 위한 스케줄링 방법은 절대 시간 기준이 아니라， 시간 차이에 해당하는 정보에 의해서 결정되므로， 각 노드들의 로컬 시각 정보가 서로 상이하더라도 정확하게 동작한다. 따라서 시간 동기화가 필요 없으므로 시간 동기 화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 응용 분야에서도 활용이 가능하다는 장점이 있다.

또한, 왕복 시간지연 정보에 대한 정확한 값이 매 사이클마다 얻어지므로, 오차가 누적되지 않고 주기적인 재초기화가 필요 없다는 뛰어난 효과가 있다.

【도면의 간단한 설명】

도 1은 본 발명의 제 1 실시예에 의한 수중 무선 여동 네트워크를 위한 스케 즐링 방법이 적용되는 네트워크 토폴로지를 나타내는 도면이다.

46

대체용지 (규칙 제 26조) 도 2a 내지 도 2f는 본 발명의 제 1 실시예에 의한 수중 무선 이동 네트워크 를 위한 스케줄링 방법을 설명하기 위한 동작 플로우차트이다.

도 3은 본 발명의 제 1 실시예에 의한 사이클 단위의 스케즐링 개념도이다. 도 4는 본 발명의 제 1 실시예에 의한 n-번째 사이클에서 각 노드의 대기 시 간 도출 원리에 대한 개념도이다.

도 5는 본 발명의 제 2 실시예에 의한, 수중 무선 이동 네트워크를 위한 스 케쥴링 방법이 적용되는 네트워크 토폴로지를 나타내는 도면이다.

도 6은 본 발명의 제 2 실시예에 의한， 수중 부선 이동 네트워크를 위한 스 케즐링 방법의 사이클 개념도아다.

도 7a 내지 도 7b는 본 발명의 제 2 실시예에 의한, 수증 무선 이동 네트워 크를 위한스케쥴링 방법을 설명하기 위한 동작 플로우챠트이다.

도 8은 본 발명의 제 3 실시예에 의한, 수중 무선 이동 네트워크를 위한 스 케즐링 방법이 적용되는 네트워크 토폴로지를 나타내는도면이다.

도 9는 본 발명의 제 3 실시예에 의한, 수중 무선 이동 네트워크를 위한 스 케줄링 방법의 사이클 개념도아다.

도 10a 내지 도 10c는 본 발명의 제 3 실시예에 의한， 수증 무선 이동 네트 워크를 위한 스케쥴링 방법을 설명하기 위한 동작 플로우차트이다.

【발명의 실시를 위한 형태】

이하， 본 발명의 실시예를 도면을 참조하여 상세히 설명하기로 한다.

[제 1 실시예]

47

대체용지 (규칙 제 26조) 도 1은 본 발명의 제 1 실시예에 의한 수증 무선 이ᅵ동 네트워크를 위한 스케 즐링 방법이 적용되는 네트워크 토폴로지를 나타내는 도면으로서， 네트워크 토폴로 지는 하나의 싱크 노드와 다수의 노드들로 이루어져 있다. 수중에서 음파를 이용하 여 다수의 노드가 하나의 싱크 노드로 데이터 패킷을 보내는 중앙 집중식 네트워크 토폴로지에서의 스케즐링 방법이다. 싱크 노드 이외의 노드는 간략하게 노드로 부 르기로 한다. 싱크 노드는 노드들의 전송 스케쥴을 ¾함하고 있는 비콘 패킷을 방 송하고， 비콘 패킷을 수신한 노드들은 비콘 패킷에 지시되어 있는 각 노드들의 전 송 스케즐에 따라서 데이터 패¾을 싱크 노드로 전송한다. 싱크 노드와 노드 간의 최대 상대 속도를 알고 있다고 가정하고， V로 표시한다.

이하， 위와 같이 구성된 네트워크 토폴로지에서 이루어지는， 본 발명의 제 1 실시예에 의한 수중 무선 이동 네트워크를 위한 스케출링 방법에 대해서 설명하기 로 한다.

도 2a 내지 도 2f는 본 발명의 제 1 실시예에 의한 수중 무선 이동 네트워크 를 위한 스케즐링 방법을 설명하기 위한 동작 플로우챠트로서, 여기서 S는 스 템 (Step)을 의미한다.

본 발명의 스케줄링 방법은 싱크 노드와 다수의 노드들 간의 왕복 시간 지 연 (RTT: Round Tr ip Time)을 구하여 이를 기반으로 최초의 층돌 희피 스케즐을 도 출하는 초기화 과정과， 초기화 과정에서 싱크 노드가 비콘 패킷 방송하여 모든 노 드들로부터 데이터 패키 수신이 완료되는 1-번째 사이클 후에 이루어지는 정규 과 정을 포함한다.

48

대체용지 (규칙 제 26조) 초기화 과정 먼저, 싱크 노드로부터 다수의 노드들로 초기화 ( IRQ) 패킷을 방송하 고 (S1010) , 성크 노드가 다수의 노드들로부터 제 1 설정시간 (^"O 동안 초기화 웅 답 (IRP) 패킷을 수신한다 (S1020) .

초기화 패킷은 노드가 초기화 패킷을 수신했을 때 초기화 패킷임을 알 수 있 는 패킷 종류 식별 정보만을 포함하고 있으면 되므로 그 길이가 매우 짧다. 초기화 응답 패킷은 해당 초기화 응답 패킷을 송신하는 노드의 주소 정보와 초기화 응답 패킷임을 나타내는 패킷 종류 식별 정보를 포함한다. 모뎀의 최대 통신 반경을 r이 라고 하고， 음파의 속도를 c라고 하면, 싱크 노드는 초기화 패킷 방송 후에 아래와 같이 제 1 설정시간 ( ^n" ) 이내에 모든 노드들로부터 초기화 웅답 패¾ 수신이 완 료된다. 제 1 설정시간 (^^ )은다음 수학식 101에 의해 결정된다.

[수학식 101]

[여기서, 쫘 ^ m ax는 싱크 노드와 노드 간 왕복시간 지연의 최대값으로 서 아래의 수학식 102에 의해 결정되고， 는 초기화 패킷 길이의 시간 환산

49

대체용지 (규칙 제 26조) 값이며， 는 초기화 응답 패킷 길이의 시간 환산값이며, 는 노드가 초기화 패킷 수신 완료 후에 초기화 응답 패킷을 송신하기까지 소요되는 시간임 ]

[수학식 102] ^¾ = ^{: '}

[여기서, r은 모뎀의 최대 통신 반경이고, c는 음파의 속도임] 이어서， 싱크 노드가 상기 스텝 (S1020)에서 수신한 초기화 웅답 패킷으로부 터 싱크 노드와 다수의 노드들 간 왕복 시간 지연 ( H )을 계산한다 (S1030). 구체적으로는， 싱크 노드는 초기화 패킷 송신 시간 ( 을 싱크 노드 자신의 로 컬 클럭으로부터 알 수 있고， 노드 (H)로부터 수신된 초기화 응답 패킷의 수신 시 각 (i^^ay)) 또한 싱크 노드 자신의 로컬 클럭으로부터 알 수 있다. 따라서 싱크 노드는 시간 동기화 없이 싱크 노드와 노드 (H) 사이의 왕복 시간 지연 정 보 ( T )를 초기화 웅답 패깃 수신 시각과 초기화 패킷 송신 시각의 차이로서 획득할 수 있다.

싱크 노드와 다수의 노드들 간 왕복 시간 지연 은 다음의 수학식 103에 의해 결정된다.

50

대체용지 (규칙 제 26조) [수학식 103] 이후, 싱크 노드에 의해 초기화 웅답 패킷 수신에 충돌이 존재하는 지의 여 부를 결정한다 (S1040) .

싱크 노드가 노드들로부터 초기화 웅답 ( IRP) 패킷을 수신할 때 여러 노드들 로부터 초기화 응답 패킷을 수신하게 되는데, 싱크 노드와 각 노드간 왕복 시간 지 연 차이가 초기화 응답 패킷 길이보다 크기만 하면 충돌이 발생하지 않는다. 예컨 대, 물리 계층의 전송 속도가 100 kbps 이고 음파의 전달 속도가 1 , 500 m/s 인 경 우를 생각하면， 한 개의 비트가 차지하는 길이는 0.01 ms 이고, 초기화 웅답 패킷 은 노드의 주소와 패킷타입 정보만을 포함하면 되므로 30-bi t 라고 가정하면 이때 초기화 응답 패킷 길이는 0.3 ms 이고， 0.3 ms 동안 음파가 이동하는 거리는 0.45 m 이므로， 임의의 두 개의 노드에 대해서 싱크 노드와 노드간 거리에 대한 상대적 인 차이가 0.5 m 이상이면 층돌이 발생하지 않으므로, 충돌 확률이 매우 작아지게 된다. 이것은 음파의 느린 전달 속도가 만들어내는 자연적인 랜덤 백오프 (random backof f ) 효과를 활용하는 것을 의미한다. 일반적으로 공기중에서 전자파를 이용하 는 무선 네트워크에서는 패킷 수신 충돌을 방지하기 위하여 랜덤한 시간 지연을 부 여하게 되는데, 수증에서 음파를 이용하는 무선 통신 네트워크에서는 음파의 느린 전달 속도가 자연스럽게 랜덤 시간 지연을 유발하게 되는 원리를 이용하는 것이다. 그럼에도 불구하고， 싱크 노드에서 초기화 응답 패킷에 대한 수신 충돌이 발생할

51

대체용지 (규칙 제 26조) 수 있는데, 이러한 초기화 응답 패킷 수신 층돌이 발생한 노드들에게만 선택적으로 초기화 웅답 패킷의 수신 층돌 회피를 적용하는 것이 본 발명쎄 대한 초기화 과정 의 가장 중요한 특징이다.

맨 처음 이루어지는 초기화 패킷 방송 및 이에 대한 노드들의 초기화 웅답 패킷 수신 과정을 거치면서 , 싱크 노드는 물리 계층에서 신호 수신은 이루어졌으나 정보가 제대로 복원되지 않은 경우의 발생 유무로서 초기화 응답 패킷 수신 충돌 발생 유무를 알 수 있다. 상기 스텝 (S1040)에서 초기화 웅답 패킷 수신에 충돌이 존재하지 않으면 (N) , 초기 스케즐링 절차로 진입하여 아래의 스텝 (S1050)으로 진행되는 한편, 초기화 웅 답 패킷 수신에 충돌이 발생한 경우에는 (Y) , 싱크 노드에 의해 재초기화 (RIRP) 패 킷이 다수의 노드들에 방송되어 층돌 회피를 통한 왕복 시간 지연 획득 절차에 진 입한다 (S1260) .

재초기화 (RIRP) 패킷은 싱크 노드와노드간 왕복 시간 지연 획득이 이루어진 노드들에 대한 목록을 포함하도록 하여, 재초기화 패킷을 수신한 노드들은 자신이 재초기화 패킷의 목록에 없는 경우에만 랜덤 백오프 (backoff)를 통하여 재초기화 응답 패킷을 싱크 노드에게 송신하도록 한다. 여기에서 랜덤 백오프란 재초기화 패 킷을 수산한 노드가 재초기화 패킷을 수신하자마자 바로 재초기화 웅답 패킷을 송 신하는 것이 아니라, 재초기화 응답 패킷의 송신을 길이를 갖는 시간 술롯의 임의의 정수배만큼 재초기화 응답 패킷의 송신을 미루는 것을 의미한다. 즉， 재초

52

대체용지 (규칙 제 26조) 기화 패킷을 수신한 노드는 재초기화 패킷 수신이 완료된 후에 아래의 수학식 104 와 같이 주어지는 시간 동안 대기한 후에 재¾기화 웅답 패킷을 싱크 노드 로 송신하도록 한다.

[수학식 104]

[여기서， m은 사용자가 지정하는 최대값 (M) 보다 작은 정수 중에서 랜덤하게 선택되는 음수가 아닌 정수이고， 은 바람직하게는 초기화 옹답 패킷 길이의

2배 이상이 되도록 함]

이어서, 스텝 (S1270)에서는 싱크 노드에 의해 제 2 설정 시간 만큼 재초기화 응답 패킷이 수신된다. 재초기화 옹답 패킷은 초기화 웅답 패킷이 포함하 고 있는 정보에다가 추가적으로 m 값이 포함되도록 한다.

즉, 싱크 노드는 처음 초기화 웅답 패킷 수신의 경우와 유사하게 재초기화 패킷 방송 후에 아래의 수학식 105에 의해 결정된 바와 같은 제 2 설정 시 간 ( _e ii ) 이내에 모든 노들들로부터 재초기화 웅 _ᅵ 답 패킷 수신이 완료된다.

53

대체용지 (규칙 제 26조) [수학식 105]

[여기서， ^D 丽 Q는 재초기화 패킷 길이의 시간 환산값이고， 는 재초 기화 웅답 패킷 길이의 시간 환산값임] 이어서， 싱크 노드가 상기 스텝 (S1270)에서 수신한 재초기화 웅답 패킷으로 부터 싱크 노드와 다수의 노드들 간 왕복 시간 지연 을 계산한다 (S12S0) . 구체적으로， 싱크 노드는 재초기화 패킷 송신 서간 을 싱크 노드 자신 의 로컬 클럭으로부터 알 수 있고, 노드 (Η)로부터 수신된 재초기화 응답 패킷의 수 신 시각 ) ] 또한 싱크 노드 자신의 로컬 클럭으로부터 알 수 있다. 따라서 싱크 노드는 시간 동기화 없이 싱크 노드와 노드 00 사。의 왕복 시간 지연 정보 을 재초기화 웅답 패킷 수신 시각과 재초기화 패¾ 송신 시각의 차이로 서 다음의 수학식 106과 같이 획득할 수 있다. [수학식 106]

[여기서， t _Rmp 는 노드 (H)로부터 수신된 재초기화 웅답 패킷의 수신 시

54

대체용지 (규칙 제 26조) 각이며， 는 재초기화 패킷 송신 시각임]

이후， 싱크 노드에 의해 재초기화 응답 패킷 수신쎄 층돌이 존재하는 지의 여부를 결정한다 (S1290) . 상기 스텝 (S1290)에서 재초기화 웅답 패킷 수신에 층돌이 존재하면 (Υ) 상기 스텝 (S1260)으로 진행되는 한편 상기 스텝 (S1290)에서 재초기화 응답 패킷 수신에 충돌이 존재하지 않으면 (Ν) 상기 스텝 (S1050)으로 진행된다.

즉， 재초기화 웅답 패킷 수신 충돌이 발생하지 않을 때까지 재초기화 패킷 방송을 반복하여 모든 노드들에 대해서 싱크 노드와 노드간 왕복 시간 지연을 획득 하도톡 한다. 단， 모든 노드들에 대해서 싱크 노드와 노드간 왕복 시간 지연 획득 이 반드시 필요하지 않은 경우에는 상기 반복 횟수에 제한을 둘 수 있다.

상기와 같이 초기화 과정에서 싱크 노드가 왕복 시간 지연 정보 획득을 완료 하면 싱크 노드는 이와 같이 획득된 왕복 시간 지연 정보를 이용하여 싱크 노드에 서 노드들의 데이터 패킷 수신 충돌이 발생하지 않도록 초기 스케쥴을 계산하고, 싱크 노드는 이 스케즐 정보를 비콘 패킷에 포함하도록 비콘 패킷을 생성하여 이 비콘 패킷을모든 노드들에게 방송한다. 이를 위해서， 싱크 노드가 상기 스텝 (S1030)에서 계산된 왕복 시간 지 연 ^RTT H ) ^ 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬한

55

대체용지 (규칙 제 26조) 다 (S1050) .

총 K개의 노드가 있다면， 왕복 시간 지연이 k-번째로 작은 노드를 "k-번째 노드"로 명명한다. k—번째 노드의 왕복 시간 지연을 ^S 1라고 표시한다. ^δ 는 수학식 103 및 수학식 106을 통해서 획득된 왕복 시간 지연을 작은 순서대로 정렬 하여 얻어지는 값이다. ^δ *ᅳ1가 획득된 시각을 ^τ 라고 표시한다. ^τ Α·는 ^s i에 상응하는 tiRP 또는 t^RP 값이다. 싱크 노드가 최초로 비콘 패킷을 방송하는 시 각을 i로 표시한다. ^0 , 1은 싱크 노드의 로컬 클럭으로부터 당연히 알 수 있는 값 이다. 이후， 싱크 노드는 왕복 시간 지연이 작은 순서대로 다음과 같이 각 노드의 스케즐링을 한다. 스케줄링이라 함은, 노드가 비콘 패킷을 수신한 후에 데이터 패 킷을 송신하기까지 대기하는 시간으로서， k—번째 노드의 대기 시간을 ^W ^ 으로 표시한다.

먼저, 싱크 노드에 의해 변수 (k)가 1로 설정되고 1-번째 노드의 대기 시 간 (^ι, ι ).이 다음의 수학식 1 ₀₇ 과 같이 "0"으로 설정된다 (S1060) . 즉， 1-번째 노드 는 비콘 패킷을 수신하자마자 대기 시간 없이 바로 데이터 패킷을 송신한다.

[수학식 107]

56

대체용지 (규칙 제 26조) 그러면， 싱크 노드에 의해 1-번째 노드의 데이터 패킷이 싱크 노드에 수신되 기 시작하는 시각의 아래의 수학식 108과 같이 계산된 다 (S1070) .

[수학식 108]

[여기서， c 은 싱크 노드에 의한 최초의 비콘 패¾ 방송 시각이며， ^D b는 비콘 패킷 길이의 시간 환산값이며， ^ ¹ ， ¹ 은 1-번째 노프의 왕복시간 지연이며, 은

1-번째 노드의 싱크 노드와의 왕복시간 지연이 획득된 시젊이며, V은 싱크 노드와 노드 간의 최대 상대 속력임] 수학식 108은 1-번째 노드의 RTT 획득 시점부터, 1-번째 노드가 비콘 패킷 수신 후에 데이터 패킷을 송신할 때까지 1-번째 노드의 이동성으로 인해서 발생하 는 1-번째 노드의 왕복 시간 지연의 최대 변동폭을 고려하는 방법이다. 1 번째 노 드의 RTT가 획득된 시점은 ^τ 1이므로 1-번째 노드의 RTT가 결정된 시점은 ^τ 1 ^{_ δ} 1. ΐ ² 이고， 1-번째 노드는 l + ^^^max / ² 시각 이전에는 비콘 메시지를 반드시 수신한다. 따라서 1-번째 노 H의 결정 시점부터 1-번째 노드가 데이터

57

대체용지 (규칙 제 26조) 패킷을 전송하기 시작하는 시점까지 1-번째 노드가 싱크 노드와 최대 상대 속력 V 로 멀어질 때 왕복 시간 지연은 최대로 증가하게 되 ¾데， 이것은 수학식 108에서， {t ₀ _ ₁ + RTT _max /2 + T _pro + D _b - (τ ₁ - δ _1,1 /2)} ^χ 2 ^χ /c으로 표현되고 있다ᅳ

따라서 1-번째 노드의 데이터 패킷이 싱크 노≤에 수신 완료되는 시각의 최 대값은 다음 수학식 109와 같다. 즉， 상기 시각의 최대값에 수신이 종료된다.

[수학식 109]

[여기에서 ^ ¹ . ¹ 는 1번째 노드의 데이터 패킷 길이를 시간으로 환산한 값임] .max

/•mm

ι Λ 이후에 2-번째 노드의 데이터 패킷 수신이 시작된다.

[수학식 110]

^min

[여기서， 2，1은 2-번째 노드의 데이터 패¾이 싱크 노드에 도착하는 시

58

대체용지 (규칙 제 26조) 각의 최소값임] 따라서, 다음의 수학식 Hi과 같이 2-번째 노드에게 시간 지연을 부여하면 싱크 노드에서 1-번째 노드의 데이터 패킷과의 수신 충돌을 피할 수가 있다.

[수학식 111]

[여기에서 , max }는 A, B 둘 중에서 큰 값을 선택하는 함수임] 같은 방법으로, K-번째 노드의 시간 지연이 계산될 때까지 회귀적으로 각 노 드의 시간 지연을 계산할 수가 있는데， 구체적으로， (k-1)-번째 노드의 데이터 패 킷이 싱크 노드에 도착하는 시각의 1)은 다음의 수학식 1 ₁₂ 와 같이 계산된다.

[수학식 112]

스템 (S1080)에서는 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판

59

대체용지 (규칙 제 26조) 단한다. 상기 스텝 (S1080)에서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면 (Y), 상기 변수 (k)를 k+1로 설정한다<51090). 스텝 (S1100)에서는 k-번째 노드의 데이터 패킷이 싱크 노드에 도착하는 시각 의 )이 다음의 수학식 113과 같이 계산된다. [수학식 113]

[여기서, 은 _k -번째 노드의 왕복 시간 지연이고， ¾는 ι가 획득된 시 각임]

스텝 (S1110)에서는 싱크 노드에 의해 k-번째 ¾드의 대기 시간 (^씨)이 다 음의 수학식 114와 같이 계산돤다.

[수학식 114] =max{0. t^-i _tl + — i,r¾ ¾

60

대체용지 (규칙 제 26조) 이와 같이， k-번째 노드에게 대기 시간 을 부여하면 (k-1)-번째 노드 의 데이터 패킷과 k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 층돌이 발생하 는 것을 회피할 수 있다. 스텝 (S1120)에서는 싱크 노드가 k-번째 노드의 데이터 패킷이 싱크 노드에 도착하는 시각의 최대값 ( ^， )을 상기 수학식 112와 같이 계산한 후 상기 스 텝 (S1080)으로 진행된다. 한편， 상기 스텝 (S1080)에서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작 지 않으면 (N) , 즉， 모든 K개의 노드에 대해서 스케줄 계산이 완료되면， 스 텝 (S1130)으로 진행된다. 스텝 (S1130)에서는 싱크 노드에 의해 1-번째 비콘 패킷이 제 3 설정, 각 ( ，1 )에 노드들에 방송된다. 스텝 (S1140)에서는 싱크 노드가 마지막 -번째 (K-번째) 노드 데이터 패킷을 수 신한 후 또는 상기 스텝 (S1130)에 의한 1-번째 비콘 패킷 방송 후 제 4 설정 시 )을 대기하고, 다음의 정규 과정!에 진입한다.

61

대체용지 (규칙 제 26조) 정규 과정

도 3은 본 발명의 제 1 실시예에 의한 사이클 단위의 스케즐링 개념도이다. 초기화 과정에서 싱크 노드가 비콘 패킷을 방송하고, 모든 노드들로부터 데이터 패 킷 수신이 완료되는 순간까지를 1-번째 사이클이라고 정의하면, 정규 과정은 2-번 째 사이클부터이다. 여기에서 n-번째 사이클이란， 도 3에 도시된 바와 같이, 싱크 노드가 n一번째 비콘 패킷을 방송하고, 모든 노드들로부터 데이터 패킷 수신이 완료 되는 순간까지를 의미한다. n-번째 사이클의 비콘 패¾이 방송되는 시각을 ^to ^ 라 고 표기한다. n—번째 사이클에서 k-번째 노드의 데이터 패킷이 수신 시작되는 시각 을 ^, ^η 라고 표기한다. _n -번째 사이클에서 k—번째 노드에게 부여되는 시간 지연을 ^w 라고 표기한다. n-번째 사이클이 종료되면 싱크 노드에 의해 싱크 노드와 k-번째 노드 간 왕 복 시간 지연 ( ^Sk . ⁿ )이 다음의 수학식 115와 같이 계산된다 (S1150) .

[수학식 115]

[여기서， ,"은 n-번째 사이클의 비콘 패킷이 방송되는 시각이고， ， 은 n-번째 사이클에서 k-번째 노드의 데이터 패킷의 수신이 시작되는 시각이며，

62

대체용지 (규칙 제 26조) «¾，«은 _n -번째 사이클에서 k-번째 노드에게 부여되는 시간 지연이며, ^， 은 _n - 번째 사이클에서의 비콘 길이 시간 환산값임] 스텝 (S1152)에서는 싱크 노드가 상기 스텝 (S1150)예서 계산된 왕복 시간 지 연 ( ^δ . ^η )을 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬한다. 스텝 (S1154)에서는 싱크 노드에 의해 1 사이클 동안 변화할 수 있는 노드의 왕복 시간 지연 변동폭 (^max )이 다음의 수학식 116에 의해 계산된다.

[수학식 116]

[여기서， ½ 1은 (n l)-번째 사이클에서의 데이터 패킷의 수신 시작 시각 임] 싱크 노드는 (n-1)-번째 사이클의 비콘 패킷 송신 시각 및 각 노드들로부터 의 데이터 패킷 수신 시각을 이용하여 싱크 노드와 각 노드간 왕복 시간 지연 값을 얻을 수 있지만, η-번째 사이클에서 각 노드가 gl†fᅵ터 패킷을 송신하는 시점에서의 싱크 노드와 각 노드간 왕복 시간 지연은 노드의 이동성으로 인하여 정확하게 알기 가 어렵다. 본 발명에서는, 각 노드의 (n-1)-번째 사이클에서 데이터 패킷의 수신

63

대체용지 (규칙 제 26조) 시작 시각과 _n -번째 사이클에서 데이터 패킷의 수신 시각의 차이를 다음의 수학식 117과 같이 근사하고，

[수학식 117] ,nᅳ ,n- l ~ Ο,η― 1, 1≤ k≤ Κ 한 사이클동안 변화할 수 있는 싱크 노드와 각 노드간 왕복 시간 지연의 변 동폭을 상기 수학식 116과 같이 계산한다. 수학식 117에서， n-번째 스케즐 정보는 _n -번째 사이클에서 비콘 패킷에 포함하여 방송하므로 _n -번째 스케즐을 계산하여 도출하는 순간에는 ^ 값은 알 수 없는 값임에 유의해야 한다. 도 4는본 발명의 제 1 실시예에 의한 n-번째 사이클에서 각 노드의 대기 시 간 도출 원리에 대한 개념도이다. n-번째 사이클에서 (k-1)-번째 노드의 데이터 패 킷은 n-번째 비콘 패킷 방송 시각을 기준으로 ^s -i,"-i_X _max 에서 δ^— ι, _Λ - 1 + λ. _max + w _k _ _1ιί7 + D _k _ _{1 η} 사이에 수신 완료된다. 따라서 본 발명 에서는 ⁵ "一 1—入 max 이 ⁵ *一丄 _, „— 1 + λ _max + W _k _ _1-n + D _k _ _x _„ 보다 크도 록 하여， n-번째 사이클에서 (k-1)-번째 노드의 데이터 패킷과 k-번째 노드의 데이 터 패킷이 싱크 노드에서 수신 층돌이 발생하지 않도록 해야 한다. 스텝 (S1160)에서는 싱크 노드가 변수 (k)를 1로 설정하고， n-번째 사이클에서

64

대체용지 (규칙 제 26조) 1-번째 노드에게 부여되는 시간지연 ( ^을 "0' '으로 설정하고， n-번째 사이클에 서 1-번째 노드의 데이터 패킷이 수신되기 시작되는 시각의 최대값 ( ， )을 다 음의 수학식 118과 같이 계산한다. [수학식 118]

；壞 ᅳ 細

스텝 (S1170)에서는 싱크 노드가 변수 ( )가 보다 작은 지의 여부를 결정 하고， 변수 가 보다 작으면 (Y) , k를 " 1"만큼 증개"시키고 (S1180) , 다음 스 템 (S1190)을수행하는 한편, ：가 이상이면 (N) 하기의 스템 (S1220)을 수행한다. 스텝 (S1190)에서는 싱크 노드가 η-번째 사이클에서 노드들의 데이터 패킷이 수신되기 시작되는 시각의 다음의 수학식 119와 같이 계산한다. [수학식 119]

-

스텝 (S1200)에서는 싱크 노드가 n—번째 사이클에서 노드들에게 부여되는 시

65

대체용지 (규칙 제 26조) 간 지연 (V¾ _{rt )} 을 다음의 수학식 과 같이 계산한다ᅳ

[수학식 120] 스템 (S1210)에서는 싱크 노드가 n-번째 사이클에서 노드의 데이터 패킷이 수 신되기 시작되는 시각의 최대값 ( )을 다음의 수학식 121과 같이 계산한 후 상기 스텝 (S1170)으로 진행된다.

[수학식 121] 스텝 (S1220)에서는 싱크 노드에 의해 비콘 패킷 방송이 되는 지의 여부가 결 정된다.

상기 스텝 (S1220)에서 비콘 패킷 방송이 되지 않으면 (N) 스케즐링 과정을 종 료한다. 한편, 상기 스템 (S1220)에서 싱크 노드에 의해 비콘 패킷 방송이 결정되 면 (Y) , 싱크 노드에 의해 n—번째 사이클의 비콘 패킷이 방송되는 시각 (to," )에 비

66

대체용지 (규칙 제 26조) 콘 패킷이 다수의 노드들에게 방송된다 ( _S12 30) .

이어서, 싱크 노드가마지막 -번째 (K-번째) 노드 데이터 패킷을 수신한 牟 또 는 상기 n-번째 사이클에서 마지막 -번째 노드의 데이터 패킷이 수신되기 시작되는 max

시각의 최대값 ( ≠ )을 대기하고 (S1240) , 싱크 노 ^에 의해 사이클이 1만큼 증 가된 후 (S1250) , 상기 스텝 (S1150)으로 진행된다.

상기와 같이 구성된 본 발명의 제 1 실시예에 의한, 수중 무선 이동 네트워 크를 위한 스케즐링 방법에 의하면, 싱크 노드로부터 다수의 노드들로 초기화 패¾ 을 방송하고， 싱크 노드가 다수의 노드들로부터 제 1 설정시간 동안 초기화 웅답 패킷을 수신하며, 상기 싱크 노드가 수신한 초기화 웅답 패킷으로부터 싱크 노드와 다수의 노드들 간 왕복 시간 지연 (^ ^ )을 계산하며， 싱크 노드에 의해 초기화 응답 패킷 수신에 층돌이 존재하는 지의 여부를 결정하고， 초기화 웅답 패 킷 수신에 충돌이 존재하지 않으면 싱크 노드가 계산된 왕복 시간 지연 (^^ ⁷ ^ ) 을 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬하며， 싱크 노드에 의해 변수 (k)가 1로 설정되고 1-번째 노드의 대기 시간 (^Ι, ι )이 "0"으로 설정되며, 싱 크 노드에 의해 1-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각 雞 ； ^■

의 최대값 ( )이 계산되며， 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의

67

대체용지 (규칙 제 26조) 여부를 판단하고， 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면 변수 (k)를 k+1로 설 정하고， 싱크 노드에 의해 k—번째 노드의 데이터 패¾이 상기 싱크 노드에 도착하

는 시각의 이 계산되며， 싱크 노드에 의해 k-번째 노드의 대기 시 간 (^ 이 계산되며， 싱크 노드에 의해 k—번째 노 의 데이터 패킷이 싱크 노드

에 도착하는 시각의 최대값 ( ^' )을 계산한 후 변수 (k)가 마지막 -번째 (K-번째) 보다 작지 않으면， 싱크 노드에 의해 1-번째 비콘 패킷이 제 3 설정 시각 (Vi )에 다수의 노드들에 방송되고， 싱크 노드가 마지막 -번째 (K-번째) 노드 데이터 패¾을 扉 脚 ^:

수신한 후 또는 1-번째 비콘 패킷 방송후 제 4 설정 시간 ( » ^Α 을 대기하며， 싱크 노드에 의해 싱크 노드와 k-번째 노드 간 왕복 시간 지연 ( ⁶ k.n )이 계산되며, 싱크 노드가 계산된 왕복 시간 지연 ( ⁶ ><，이을 이용하여 왕복 시간 지연이 작은 순으로 노드들을 정렬하며， 싱크 노드에 의해 1 사이클 동안 변화할 수 있는 노드의 왕복 시간 지연 변동폭 ( _{max )} 이 계산되며, 변수 (k)를 1로 설정하고， 싱크 노드가 _n -번째 사이클에서 1-번째 노드에게 부여되는 시간 지연 (^ ¹ ，« )을 "0"으로 설정하고, n-번째 사이클에서 1-번째 노드의 데이터 패킷이 수신되기 시작돠는 시

각의 최대값 (주 )을 계산하며， 변수 (k)가 마지막 번째 (K-번째)보다 작은 지의 여부를 판단하여 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면 변수 (k)를 k+1로 설 정하고, 성크 노드가 n-번째 사이클에서 k-번째 노드의 데이터 패킷이 수신되기 시

68

대체용지 (규칙 제 26조) 작되는 시각의 최소값 ( > )을 계산하며 싱크 노드가 η-번째 사이클에서 k-번 째 노드에게 부여되는 시간 지연 ( ^W ft )을 계산하며， 싱크 노드가 n-번째 사이클에 서 k—번째 노드의 데이터 패킷이 수신되기 시작되는 시각의 최대값 ( )을 계 산한 후 변수 (k)가 마지막 -번째 (K-번째) 보다 작지 않으면, 싱크 노드에 의해 비콘 패킷 방송이 되는 지의 여부가 결정되며, 비콘 패킷 방송이 되지 않으면 종료하도 록 구성됨으로써， 수중에서 이동 노드의 항법 정보와 무관하게 동작하며， 시간 동 기화가 불필요하므로 시간 동기화를 위한 별도의 패킷 교환이 필요 없으므로 네트 워크 수율을 향상시킬 수 있으며, 스케즐 정보가 절대 시간 기준이 아니라 시간 차 이에 해당하는 정보에 의해서 결정되므로 각 노드들의 로컬 시각 정보가 서로 상이 하더라도 정확하게 동작하며， 매 사이클 종료 시점에 싱크 노드와 노드간 왕복 시 간 지연 정보에 대한 정확한 값이 측정되므로 스케줄 정보는 시간이 지남에 따라서 오차가 누적되지 않아서 주기적인 재초기화가 필요 없다

[제 2 실시예]

도 5은 본 발명의 제 2 실시예에 의한， 수증 부선 이동 네트워크를 위한 스 케즐링 방법이 적용되는 네트워크 토폴로지를 나타내는 도면으로서， 싱크 노드가 노드들의 전송 스케즐을 포함하고 있는 비콘 패킷을 방송하고, 싱크 노드의 비콘 패킷을 수신한 싱크 노드 이외의 노드들이 비콘 패킷에 포함되어 있는 각 노드들의 전송 스케즐에 따라서 데이터 패킷을 싱크 노드로 전송한다. 싱크 노드 이외의 노

69

대체용지 (규칙 제 26조) 드는 간략하게 노드로 부르기로 한다. 본 발명에서는 수증에서 음파를 이용하여 통 신이 이루어지는 경우를 고려하고， 싱크 노드와 k-번째 노드 간의 최대 상대 속 도 (" ^{m ax} >, 수중에서의 최소 음파 전달 속도 ( ^{Cm in} ) , 싱크 노드를 제외한 노드의 총 수 ( ^ )는 알고 있다고 가정한다. 도 6은 본 발명의 제 2 실시예에 의한， 수증 부선 이동 네트워크를 위한 스 케즐링 방법의 사이클 개념도이다.

본 발명에서 n-번째 사이클이란， 도 6에 도시된! 바와 같이， 싱크 노드가 n- 번째 비콘 패킷을 방송하는 시각부터, 모든 노드들로부터 데이터 패킷 수신이 완료 된 후에 (n+1) 번째 비콘 패킷을 방송하기 시작하는 시각까지의 구간을 의미한다. η-번째 사이클의 비콘 패킷이 방송되는 시각을 ，" 이라고 표기한다. 그러 면, _{+ 1} — _ίο · "이다 [여기서 ^은 ^번째 사이클의 지속시간임] . _η -번째 사이 클에서 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각을 라고 표기하자.

본 발명의 제 2 실시예에 의한， 수중 무선 이동 네트워크를 위한 스케즐링 방법은 각 노드들이 비콘 패킷 수신 시각으로부터 얼맡 큼의 시간 지연 후에 데이 터 패킷을 ^' 송신해야 하는지에 대한 정보를 싱크 노드가 비콘 패킷에 포함하여 보낸 다.

n-번째 사이클에서 k-번째 노드의 비콘 수신 후 데이터 패킷 송신시까지의 대기 시간을 ^Wk ' ⁿ 라고 표기하자. ^ "에서 n-번째 사이클임을 명시할 필요는

70

대체용지 (규칙 제 26조) 없지만， 본 발명을 설명함에 있어서 명확성을 위하여 "에 n-번째 사이클을 명 시하는 첨!자를 사용한다. 노드의 이동성으로 인하여 노드들의 왕복시간지연은 매 사이클마다 변화하는데, 본 발명에서는 이렇게 변화하는 왕복시간지연을 과거 두 사이클의 왕복시간지연 정보를 이용하여 추정하고， 싱크 노드에서 노드들의 데이터 패킷 수신 층돌이 발생하지 않도록 "을 정한다.

본 발명에서는 싱크 노드와 각 노드간의 최초 왕복시간지연 및 싱크 노드와 각 노드간의 최초 왕복시간지연 ( s o )이 획득된 시간 ( . ⁰ )은 알고 있다고 가정한다. ^{5 k} ' ° 및 를 획득할 수 있는 다양한 방법이 존재하며， 어떤 방법을 사용하더라도 본 발명의 제 2 실시예에 의한， 수증 무선 이동 네트워크를 위한 스 케즐링 방법은 사이클 수가 증가할수록 및 와 무관하게 정상 상태에 이르 게 되므로， 및 . 0를 획득하기 위해서 사용하는 방법에 따른 본 발명의 시분 할 다중접속 방법의 성능 변화는 매우 작다. 이하, 위와 같이 구성된 네트워크 토폴로지에서 이루어지는 본 발명의 제 2 실시예에 의한, 수중 무선 이동 네트워크를 위한 스케즐링 방법에 대해서 설명하기 로 한다.

도 7a 내지 도 7b는 본 발명의 제 2 실시예에 의한, 수증 무선 이동 네트워 크를 위한 스케줄링 방법을 설명하기 위한 동작 플로우챠트로서， 여기서 S는 스 텝 (Step)을 의미한다.

71

대체용지 (규칙 제 26조) 먼제 싱크 노드는 및 를 이용하여 1—번째 사이클의 스케즐인 을 정하기 위해서는 가장 먼저 다음의 [수학식 ₂₀₁ ]과 같이 초기화 과정을 수 행한다 (S2010).

[수학식 201] r¾ == 1, _{l Jt} . = lr it _2f ¾ = Q == ¾샵， ¾ — C _D

[여기서， 는 ^보다 작거나 같은 자연수이다. 는 n-번째 사이클에 서， (n-1)-번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의 유효성을 나타내 는 변수이며, ^δ ^·° 값을 알고 있으므로 모두 1로 설정한다. ^U 2, k는 _n _번째 사이 클에서， (n— 2)-번째 사이클에서의 k-번째 노드와 왕복시간지연 획득의 유효성을 나 타내는 변수이며， 보다 과거에 획득된 왕복시간지연 정보는 최초에 존재하지 않으므로 0으로 한다. ^α *는 가장 최근에 획득된 k-번째 노드의 왕복시간지연이며， 현 상태에서 ^^가 가장 최근께 획득된 왕복시간지연 (즉， 싱크 노드와 각 노드간 의 최초 왕복시간지연)이므로 ^{1 =} S*. ₀ 로 설정한다. 는 가 얻어진 사이클이 며， 0으로 설정한다. ^c "은 n-번째 사이클의 지속 시간이며， 1-번째 사이클 이전의 사이클 지속 시간은 알 수 없으므로사용자가 적정한 ^Co 값을 정해야 하는데, 여기 에서는 그 값을 로 표시하였다. ^는 경험적으로 알고 있는 평균적인 값으

72

대체용지 (규칙 제 26조) 로 하거나, 사이클 지속 시간은 전체 데이터 패킷 길이의 합과 노드들의 왕복시간 지연의 최소값의 합보다는크므로 다음의 수학식 202와 같이 추정되어 정해짐] [수학식 202]

[ ^D ^은 1-번째 사이클에서 k-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임] 이어서， 싱크 노드는 다음과 같은 절차로 n-번째 사이클에서 k-번째 노드의 비콘 수신후 데이터 패킷 송시시까지의 대기시간( ^* )을 계산하여 사이클 단위로 각 노드들의 데이터 패킷을 수신한다 (S2020 ~ S2140) .

[스텝 S2020]

싱크 노드가 데이터 패킷 수신 순서를 결정한 후 n-번째 사이클에서 1—번째 노드에게 부여되는 시간 지연 (삐 )을 0으로 설정한다. 좀 더 상세하게 설명하면， ¹ 으로 하고，

^ ^• " ^{= 0} 으로 한다. k-번째 노드라 함은 ^α *가 k-번째로 작은 노드를 의미한다. n- 번째 사이클에서 k-번째 노드의 데이터 패킷은 싱크 노드에 k-번째로 수신된다.

73

대체용지 (규칙 제 26조) 즉， 여기에서 정렬된 순서는 성크 노드에 데이터 패킷이 도착하는 순서이다. 정렬 하는 방법으로서 추가적으로 고려될 수 있는 방법은 ^{U l} ' ^k 값이 1인 노드들을 ^α 가 작은 순서대로 정렬하고, 다음으로 "나 값이 0인 노드들 증에서 ^u ' ^k 값이 1인 노드들을 ^α *가 작은 순서대로 정렬하고， 다음으로 ^{u \} ' ^k 및 ^u u 값이 모두 0인 노드들을 ⁰ ^가 작은 순서대로 정렬하도록 함으로써， 최근에 왕복시간지연이 획득 된 노드들에게 우선 순위를 부여하는 방법을 사용할 수도 있다. 이외에도 응용 분 야에 따라서 우선 순위 기반의 다양한 정렬 방법이 존재할 수 있다.

[스텝 S2030]

싱크 노드가 n 번째 사이클에서 1-번째 노드의 왕복시간지연 을 추정하 고, 1-번째 노드의 데이터 패킷 수신 완료 시점 을 계산한다.

좀 더 상세하게는， 만약 "u + u ^ ² 이면， 즉, 최근 두 사이클 동안 丄—번째 노드의 왕복시간지연이 성공적으로 획득된 경우에는 다음의 [수학식 203]과 같이 n-번째 사이클에서 1-번째 노드의 왕복시간지연 ( ^ " )을 추정하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 을 계산한다.

[수학식 203]

Λ 1

丄 Α'Ι

74

대체용지 (규칙 제 26조) ^는 가드 시간이고 ^- 은 n-1-번째 사이클에서 획득된 1-번째 노드의 왕복시간지연이며， ^Db ' n-번째 사이클에서 비콘 패킷 길이를 시간으로 환산한 값이며， ^- 은 n-i-번째 사이클에서 ;L -번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각이며, 은 다음의 수학식 204와 같음]

[수학식 204]

_ ― 1 2

^Λ ¾ ^· — ~

Ll,n- 1 ^ν 1.,η-2

[ 1， 2은 η-2-번째 사이클에서 획득된 1-번째 노드의 왕복시간지연이며,

2은 η-2-번째 사이클에서 1—번째 노드의 데이터 패킷이 싱크 노드에 수신되 기 시작하는 시각임]

만약， " + ^ 값이 ₂ 보다 작으면， 즉 최근 두 사이클 동안 i—번째 노드의 왕복시간지연이 1번 이상 성공적으로 획득되지 못한 경우에는 다음의 [수학식 205] 와 같이 n-번째 사이클에서 1-번째 노드의 왕복시간지연 을 추정하고 1-번째 노드의 데이터 패킷 수신 완료 시점 ( ^e ' )을 계산한다.

75

대체용지 (규칙 제 26조) [수학식 205]

[ _max 는 왕복시간지연의 최대값이고, ^α 1은 가장 최근에 획득된 1-번째 노 드의 왕복시간지연이며 , "max는 싱크 노드와 _k -번째 노드간의 최대 상대속도이며 , C^-i은 —번째 사이클의 지속시간이며, A은 -번째 노드의 왕복시간지연이 획득 된 가장 최근 사이클이며， ^C min은 수중에서의 최소 음파전달 속도임] 상기 [수학식 203]은 다음과 같은 연립 방정식인 [수학식 206]을 풀어서 얻 어진다.

[수학식 206]

은 n-번째 사이클예서 1-번째 노드의 데이터 패킷 수신 시각 (^")에 대한 추정값임]

76

대체용지 (규칙 제 26조) 상기 [수학식 206]에서 첫 번째 식은 두 점 ( "— ² ' ^{sy 2} )과

( "- ¹ ' ⁶¹ ."- ¹ )을 지나는 직선으로 1—번째 노드의 데이터 패킷 수신 시각과 왕복 시간 지연의 관계를 근사하고, ^."에서 왕복시간지연 ^"을 계산한 것이다. 한편，

^"은 n-번째 사이클의 스케쥴 정보를 계산하는 시점에서 정확하게 알 수 없는데， 1-번째 노드의 왕복지연시간과 데이터 패킷 수신 시각은 상기 [수학식 206]에서 두 번째 식과 같은 관계를 가지므로, 상기 [수학식 206]윷 풀면 [수학식 203]와 같이 ·"을 계산할 수 있다. [수학식 203]는 ^ ¹ 이면 계산이 불가능한데， 이 경우 는 1-번째 노드와 싱크 노드의 상대 속도가 음파의 속도와 같은 경우에 해당하므로 현실적으로 발생하지 않는다ᅳ

(n-1)-번째 사이클 및 (η-2)-번째 사이클 중에서 적어도 한 사이클 이상에서 1-번째 노드의 왕복시간지연이 획득되지 못하면 [수학식 206]과 같이 1—번째 노드 의 왕복시간지연을 구할 수 없으므로, [수학식 205]과 같이 1-번째 노드의 왕복시 간지연이 획득된 가장 최근 시점으로부터 가능한 최대 변동폭을 이용하여 왕복시간 지연을 추정하도록하여 충돌을 회피한다. [수학식 205]에서 ^ι 은 1—번째 노드의 왕 복시간지연이 획득된 가장 최근 사이클이므로 — ⁷ ι)은 왕복시간지연 획득 후에 소요된 시간을 의미하고， 이때 평균적인 사이클 지속시간을 가장 최근 사이클인 (n-1)-번째 사이클 지속시간으로 근사하면 ² 교 ^-^"ᅳ AVc-은 가장 최근에 왕 복시간지연이 획득된 후에 n-번째 사이클에서의 왕복시간지연이 가질 수 있는 최대 변동폭이 된다. 따라서 + ² ^ ₃ ^„— — ^/ ^은 _η _번째 사이클에서. ^번째 노드 의 최대 왕복시간지연이 되고， 이 값이 를 초과할 수 없으므로 [수학식 205]와

77

대체용지 (규칙 제 26조) 같이 1-번 ί째 노드의 왕복시간지연을 계산한다. (η-ΐ;卜번째 사이클 및 (n-2)-번째 사이클 중에서 적어도 한사이클 이상에서 1-번째 노 H의 왕복시간지연이 획득되지 못했다는 것은 물리계층이 완벽하다면 1-번째 노드의 이동성이 갑작스럽게 변하여 다른 노드들의 패킷과의 층돌을 발생한 것으로 인지할수 있고， 따라서 과거 왕복 시간지연 정보로부터 n-번째 사이클에서의 왕복시간지연을 추정하는 것은 바람직하 지 않음에 유의하여야 한다. 또한， 이와 같이 계산된 ^ "은 S ⁱ . "이 가질 수 있는 자장 큰 값이므로， ^ei 을 계산함에 있어 [수학식 205]에서는 E수학식 203]와 달리， 가드 시간을포함하지 않는다ᅳ

[스텝 S2040]

싱크 노드에 의해 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판 단한다.

[스텝 S2050]

상기 스템 (S2040)에서 상기 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면 (Y) , 싱크 노드가상기 변수 (k)를 k+1로 설정한다.

[스텝 S2060]

싱크 노드가 n-번째 사이클에서 k-번째 노드의 왕복시간지연 (그" )을 추정 한다.

78

대체용지 (규칙 제 26조) 좀 더 상세하게는, 만약 이면， 즉 최근 두 사이클 동안 k-번 째 노드의 왕복시간지연이 성공적으로 획득된 경우에는， 다음의 [수학식 20기과 같 이 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정한다.

[수학식 207]

은 n-1-번째 사이클에서 획득된 k-번째 노드의 왕복시간지연이며，

^ᅳ ¹ 은 k-1-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정 값이며 , *에은 n-1-번째 사이클에서 k-번째 노드의 데이테 패킷이 싱크 노드에 수신되기 시작하는 시각이며, 그은 다음의 수학식 211과 같음]

[수학식 211]

— ² 는 n-2-번째 사이클에서 획득된 k-번째 노드의 왕복시간지연이며 ,

^즈는 _n -2-번째 사이클에서 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각임]

79

대체용지 (규칙 제 26조) 상기 [수학식 20기은 두 점 ( 지， ⁶ 으 ² )과 ( "ᅳ！， ^ - ^을 지나는 직선으로 k-번째 노드의 데이터 패킷 수신 시각과 왕복 시간 지연의 관계를 근사하 고， 바로 직전 데이터 패킷인 (k-1)-번째 노드의 데이터 패킷의 수신이 완료되는 시각인 ¹ 시각에 k-번째 데이터 패킷이 수신될 때 왕복시간지연 을 계산 한 것이다. 따라서 k-번째 노드가 비콘 패킷을 받자마자 데이터패킷을 송신하여 왕 복시간지연 을 가지면서 싱크 노드에 k-번째 노 H의 데이터 패킷이 수신되기 시작하는 시각 는 다음의 [수학식 208]과 같이 계산된다.

[수학식 208]

이때, 만약 ^{Pk> ek} → 이면， k-번째 노드가 비 ¾ 패킷을 받자마자 데이터 패 킷을 송신해도 (k-1)-번째 노드의 데이터 패킷 수신이 완료되고 나서， ^ᅳ _ ι 만큼의 시간이 지난 후에： k-번째 노드의 데이터 패킷 수신이 시작되므로, 상기 [수 학식 20기에 의해서 추정한 ^ek ᅳ ¹ 시각에서의 k-번째 노드의 왕복시간지연은 실제 k一번째 노드의 데이터 패킷이 도착하는 시점에서의 왕복시간지연 추정치로서 적절 하지 않다. 따라서 상기 [수학식 206]을 풀어서 상기 [수학식 203]과 같이 1-번째 노드의 욍복시간지연을 추정한 방식으로 k-번째 노드의 왕복시간지연을 추정해야

80

대체용지 (규칙 제 26조) 한다. 따라서 에 _λ 인 경우에는 다음과 같이 [수학식 ₂₀₉ ]를 풀어서 다음의

[수학식 2:1이과 같이 k-번째 노드의 왕복시간지연을 추장한다. 상기 [수학식 210] 에서 그은상기 [수학식 ₂₁₁ ]과 같다ᅳ

[수학식 209]

tk,h― *0,n + ¾ + "¾ _;

[수학식 210]

만약， ^ᅳ세 값이 2보다 작으면， 즉 최근 두 사이클 동안 k—번째 노드 의 왕복시 ! ^' 간지연이 1번 이상 성공적으로 획득되지 못한 경우에는 다음의 [수학식 212]과 같이 η-번째 사이클에서 k-번째 노드의 왕복시간지연 ( ^*. " )을 추정한다.

[수학식 212]

81

대체용지 (규칙 제 26조) [ 는 ⁽ ^가 얻어진 사이클임]

상기 [수학식 212]는 [수학식 205]와는 다른데, 이것은 연속되는 데이터 패 킷의 충돌을 회피하기 위해서는 이전 데이터 패¾의 종료 시각은 늦게 추정되는 방 향으로 해 i야 하고， 다음의 데이터 패킷의 수신 시각은 빠르게 추정되는 방향으로 해야 하기 때문이다.

[스텝 S2070]

싱크 노드가 상기 스텝 (S2060)에서 추정된 k-번째 노드의 왕복시간지 연 을 이용하여， k—번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할 때， k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정 값 을 다음의 [수학식 213]과 같이 계산한다. [수학식 213]

^ft + + ¾n

[스텝 S2080]

싱크 노드가 상기 스텝 (S2070)에서 계산된 k-번째 노드의 데이터 패킷이 싱 크 노드에 수신되기 시작하는 시각의 추정값 을 이용하여 k-번째 노드의 대기 시간 ( " )을 다음의 [수학식 _214] 와 같이 계산한다.

82

대체용지 (규칙 제 26조) [수학식 214]

[스텝 S2090]

싱크 노드가 상기 스템 (S2070)에서 계산된 k -번째 노드의 데이터 패킷이 싱 크 노드에 수신되기 시작하는 시각의 추정값 ( ^^ )과 상기 스텝 (S2080)에서 계산된 k-번째 노드의 대기 시간 을 이용하여 k-번째 노드의 데이터 패킷이 수신 완 료되는 시각의 추정값 ( ^e 을 계산한 후， 상기 스템 (S 040)으로 진행된다.

좀 더 상세하게는, 만약 이면， 즉 최근 두 사이클 동안 k-번째 노드의 왕복시간지연이 성공적으로 획득된 경우에는 —번째 노드의 데이터 패킷이 싱크 노드쎄서 수신 완료되는 시각의 추정값 ( ^e * )은 다음의 [수학식 215]와 같이 계산된다.

[수학식 215]

¾ + ¾^ + ¾

[ . 은 _n _번째 사이클에서 _k _번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임]

83

대체용지 (규칙 제 26조) 만약， " ⁺ " ² . * 값이 2보다 작으면, 즉 최근 두 사이클 동안 k-번째 노드 의 왕복시간지연이 1번 이상 성공적으로 획득되지 못한 경우에는 k-번째 노드의 데 이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정값 ( ^e * )은 다음의 [수학식 216]과 같이 계산된다.

[수학식 216]

k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정 값 의! 계산이 완료되면， 상기 스텝 (S2040)으로 진행된다.

[스텝 S2100]

상기 스텝 (S2040)에서 변수 (k)가 마지막—번째 (K-번째) 보다 작지 않으면 (N) , 싱크 노드가 비콘 패킷의 방송 유무를 판단하여 사이클 진행 여부를 결정한다. 본 스텝 (S2100)에서 비콘 패킷이 방송되지 않아 사이클이 진행되지 않는 경 우에는 (N) , 모든 절차를 종료한다.

[스텝 S2110]

상기 스텝 (S2100)에서 비콘 패킷이 방송되어 사이클이 계속해서 진행되는 경

84

대체용지 (규칙 제 26조) 우에는 (Y) , 싱크 노드는 ^η -번째 사이클에서 싱크 노 가 비콘 패킷을 방송하기 시 작하는 시각 에 비콘 패킷을 방송한다.

[스템 S2120]

Κ-번째 노드의 데이터 패킷 수신이 완료되었거나 Κ-번째 노드의 데이터 패 킷이 수신 완료되는 시각의 추정값 이 초과된다.

[스텝 S2130]

상기 스텝 (S2120)이 진행된 후, 싱크 노드는 n-번째 사이클에서 k—번째 노드 의 왕복시간지연 을 계산하고， 왕복 시간 지연 획득 유효성 값 ( "L *및

^U ^- ^k ) 및 가장 최근에 획득된 왕복 시간 지연 관련 정보 를 갱신한다. 좀 더 상세하게는， 왕복 시간 지연 획득 유효성 값 ("u및 " ² ᅳ ^을 갱신하 기 위해서, 다음의 [수학식 21기과 같이 모든 노드들에 대하여 왕복 시간 지연 획 득 유효성 값 ( " ² ， )을 갱신하고， 만약， ^η -번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하였으면， 다음의 [수학식 218]과 같이 한다.

[수학식 217]

85

대체용지 (규칙 제 26조) [수학식 218]

만약， n-번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하지 못한 경우에는 다음의 [수학식 219]와 같이 한다.

[수학식 219]

= 0 가장 최근에 획득된 왕복 시간 지연 관련 정보 ( ^ )는 다음의 [수학식 220]과 같이 갱신한다.

[수학식 220]

또한, 왕복 시간 지연 획득 유효성 값 )이 1인 경우에는， 다음의 [수 학식 221]i과 같이 n-번째 사이클에서 k—번째 노드의 왕복시간지연 을 계산하 고, 최근에 획득된 왕복 시간 지연 관련 정보 를 ¾신한다.

86

대체용지 (규칙 제 26조) [수학식 221]

¾ 二 ¾¾ᅳ ¾w + + ¾ ，

[스텝 S2140]

싱크 노드가 n을 1만큼 증가시킨 후 (n+1)-번째 사이클을 위한 " ⁺ ι 계 산을 위하여 상기 스텝 (S2020)으로 진행된다. 상기와 같이 구성된 본 발명의 제 2 실시예에 의한, 수중 무선 이동 네트워 크를 위한 스케쥴링 방법에 의하면， 싱크 노드가 초기화 과정을 수행하고; 싱크 노 드가 데이터 패킷 수신 순서를 결정한 후 _η -번째 사이클에서 1-번째 노드에게 부여 되는 시간 지연 ( ^ ¹ ， )을 0으로 설정하며; 싱크 노드가 η-번째 사이클에서 1-번째 노드의 왕복시간지연 을 추정하고， 1-번째 노드의 데이터 패킷 수신 완료 시 점 ( ^ei )을 계산하며 ; 싱크 노드에 의해 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지 의 여부롤 판단하며; 상기 판단에서 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면， 싱크 노드가 상기 변수 (k)를 k+1로 설정하며; 싱크 노드가 n-번째 사이클에서 k-번 째 노드의 왕복시간지연 ( ^ )을 추정하며; 싱크 노¾가상기 I 추정된 k—번째 노드 의 왕복시!간지연 을 이용하여， k-번째 노드가 비콘 패킷을 받자마자 데이터

87

대체용지 (규칙 제 26조) 패킷을 송신할 때， k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 을 계산하며; 싱크 노드가 상기 계산된 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 을 이용하여 k—번째 노 드의 대기 시간 ( "；)을 계산하며 ; 그리고 싱크 노 H가 상기 계산된 k-번째 노드 의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정값 과 상기 계산 된 k-번째 노드의 대기 시간 ( ^^ " )을 이용하여 k-번째 노드의 데이터 패킷이 수신 완료되는 시각의 추정값 ( ^e * )을 계산한 후 상기 판단 과정으로 진행되도록 구성됨 으로써：

즉， 수중음향 무선 이동 네트워크 둥과 같이 왕복시간지연이 크고 물리 계층 의 전송 속도가 낮은 네트워크 환경에서， 다수의 노드들이 싱크 노드로 데이터 패 킷을 시분할 다중접속 방식으로 전송하고자 할 때 , 노드의 이동성에 따른 왕복시간 지연을 사이클 단위로 추적하여 싱크 노드가 노드들로부터 데이터 패킷을 수신함에 있어 유휴 시간을 최소화함으로써 채널 사용 효율 향샅을 통한 네트워크 효율이 크 게 향상될 수 있다. 특히, 노드 수가 증가할수록 네 B워크 효율 향상 정도는 더욱 증가한다ᅳ 본 발명에 따른 수중 무선 이동 네트워크를 위한 스케줄링 방법은 절대 시간 기준미 아니라， 시간 차이에 해당하는 정보에 의 1해서 결정되므로, 각 노드들 의 로컬 시각 정보가 서로 상이하더라도 정확하게 동작한다. 따라서 시간 동기화가 필요 없으므로 시간 동기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소 모되는 응용 분야에서도 활용이 가능하다.

또한， 왕복 시간지연 정보에 대한 정확한 값이 매 사이클마다 얻어지므로,

88

대체용지 (규칙 제 26조) 오차가 누적되지 않고 주기적인 재초기화가 필요 없다.

[제 3실시예]

도 8은 본 발명의 제 3 실시예에 의한， 수중 부선 이동 네트워크를 위한 스 케즐링 방법이 적용되는 네트워크 토폴로지를 나타내는 도면으로서， 싱크 노드가 노드들의 전송 스케즐을 포함하고 있는 비콘 패킷을 방송하고， 싱크 노드의 비콘 패킷을 수신한 싱크 노드 이외의 노드들이 비콘 패킷에 포함되어 있는 각 노드들의 전송 스케즐에 따라서 데이터 패킷을 싱크 노드로 전송한다. 싱크 노드 이외의 노 드는 간략하게 노드로 부르기로 한다. 본 발명에서는 수중에서 음파를 이용하여 통 신이 이루어지는 경우를 고려하고, 싱크 노드와 k-번째 노드 간의 최대 상대 속 도 ("max), 수중에서의 음파 전달 속도의 최소값 (e _{min )} , 싱크 노드를 제외한 노드 의 총 수 (^)는 알고 있다고 가정한다. 도 9는 본 발명의 제 3 실시예에 의한， 수중 부선 이동 네트워크를 위한 스 케즐링 방법의 사이클 개념도이다.

본 발명에서 n-번째 사이클이란， 도 9에 도시 바와 같이， 싱크 노드가 n- 번째 비콘 패킷을 방송하는 시각부터， 모든 노드들로부터 데이터 패¾ 수신이 완료 된 후에 (n+1)-번째 비콘 패킷을 방송하기 시작하는 시각까지의 구간을 의미한다. η-번째 사이클의 비콘 패킷이 방송되는 시각을 ^." 이라고 표기한다. 그러 면， <^= ₀ .„ _{+ 1 0} . "이다 [여기서 (^은 _η _번째 사이클의 지속시간임]. _η -번째

89

대체용지 (규칙 제 26조) 사이클에서 k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각을 tk. n 라고 표기하자 .

본 발명의 제 3 실시예에 의한, 수중 무선 이동 네트워크를 위한 스케줄링 방법은 각 노드들이 비콘 패킷 수신 시각으로부터 얼만 큼의 시간 지연 후에 데이 터 패킷을 송신해야 하는지에 대한 정보를 싱크 노드가 비콘 패¾에 포함하여 보낸 다.

n一번째 사이클에서 k-번째 노드의 비콘 수신 후 데이터 패킷 송신시까지의 대기 시간을 라고 표기하자. "에서 n-번째 사이클임을 명시할 필요는 없지만, 본 발명을 설명함에 있어서 명확성을 위하여 "에 n-번째 사이클을 명 시하는 첨 ί자를 사용한다. 노드의 이동성으로 인하여 노드들의 왕복시간지연은 매 사이클마다 변화하는데， 본 발명에서는 이렇게 변화하는 왕복시간지연을 과거 Μ-개 사이클의 왕복시간지연 정보를 이용하여 추정하고, 싱크노드에서 노드들의 데이터 패킷 수신 층돌이 발생하지 않도록 "을 정한다 .

본 발명에서는 싱크 노드와 각 노드간의 최초 왕복시간지연 및 싱크 노드와 각 노드간의 최초 왕복시간지연 ( ^S . o )이 획득된 시간 은 알고 있다고 가정한다. ^δ ^ ⁰ 및 ⁰ 를 획득할 수 있는 다양한 방법이 존재하며， 어떤 방법을 사 용하더라도 본 발명의 제 3 실시예에 의한 다항식 보간법을 이용한 수증 네트워크 스케줄링 방법은 사이클 수가 증가할수록 ᅳ ⁰ 및 ⁰ 와 무관하게 정상 상태에 이 르게 되므로， ⁶ *.ᄋ 및 ^Q 를 획득하기 위해서 사용하는 방법에 따른 본 발명의 스

90

대체용지 (규칙 제 26조) 케즐링 방법의 성능 변화는 매우 작다.

이하, 위와 같이 구성된 네트워크 토폴로지에서 이루어지는 본 발명의 제 3 실시예에 의한， 수증 무선 이동 네트워크를 위한 스케줄링 방법에 대해서 설명하기 로 한다. 도 10a 내지 도 10c는 본 발명의 제 3 실시예에 의한, 수중 무선 이동 네트 워크를 위한 스케줄링 방법을 설명하기 위한 동작 플로우챠트로서， 여기서 S는 스 텝 (Step)을 의미한다.

먼저， 싱크 노드는 ^5k 'o 및 ᅳ°를 이용하여 1-번째 사이클의 스케즐인 찌， 1을 정하기 위해서는 가장 먼저 다음의 [수학식 301 ]과 같이 초기화 과정을 수행한다 (S3010).

[수학식 301 ] n=l, u _k = 1, l _k = 0, a _k = ¾, ₀ , C ₀ = C _D

u _m , _k = 0.

[ f는 보다 작거나 같은 자연수이고， ¾=2，3,ᅳ게이다. 는 _n _ 번째 사이클에서， (n-1)-번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의 유 효성을 나타내는 변수이며, s . ⁰ 값을 알고 있으므로 모두 1로 설정한다. ^Um ' ^k ^ _n -번째 사이클에서, (n-m)-번째 사이클에서의 k-번째 노드의 왕복시간지연 획득의

91

대체용지 (규칙 제 26조) 유효성을 나타내는 변수이며， 보다 과거에 획득된 왕복시간지연 정보는 최초에 존재하지 않으므로 rn이 1보다 큰 경우에는 0으로 한다. ^α *는 가장 최근에 획득 된 k-번째 노드의 왕복시간지연이며, 현 상태에서 ^S/i . ⁰ 가 가장 최근에 획득된 왕복 시간지연이 ¾로 "fc = ¾,o로 설정한다. ^는 ° 가 ¾어진 사이클이며, 0으로 설 정한다. ^C "은 n-번째 사이클의 지속 시간이며， 1-번째 사이클 아전의 사이클 지속 시간은 알 수 없으므로 사용자가 적정한 ^Co 값을 정해야 하는데, 수학식 301 에서 는 그 값을 로 표시하였다. 는 경험적으로 알고 있는 평균적인 c _n 값으로 하 거나， 사이클 지속 시간은 전체 데이터 패킷 길이의 합과 노드들의 왕복시간지연의 최소값의 합보다는크므로 다음의 수학식 302와 같이 추정되어 정해짐] [수학식 302]

κ

C _D = min{5 _li0 , ···, ½. +∑D _k ,i

k= 1

[ ^D 'k, ⁱ 은 1-번째 사이클에서 k-번째 노드의 데이터 패 길이를 시간으로 환 산한 값임] 이어서, 싱크 노드는 다음과 같은 절차로 n-번째 사이클에서 k-번째 노드의 비콘 수신후 데이터 패킷 송신시까지의 대기시간 (^^" 을 계산하여 사이클 단위로 각 노드들의 데이터 패킷을 수신한다 (S3020 ~ S3140).

92

대체용지 (규칙 제 26조) [스텝 S3020]

싱크 노드가 데이터 패킷 수신 순서를 결정한 후 n-번째 사이클에서 1-번째 노드에게 부여되는 시간 지연 을 0으로 설정한다.

좀 더 상세하게 설명하면 , ^α Α·가 작은 순서대로 정렬한 후， ⁼ 1으로 하 고， ^." = 0 으로 한다ᅳ _k 번째 노드라 함은 가 _k _번째로 작은 노드를 의미한 다. n-번째 사이클에서 k-번째 노드의 데이터 패킷은 싱크 노드에 k-번째로 수신된 다. 즉， 여기에서 정렬된 순서는 싱크 노드에 데이터 패킷이 도착하는 순서이다. 정렬하는 방법으로서 추가적으로 고려될 수 있는 방법은 ^Ul ' ^k 값이 1인 노드들을 ^α 가 작은 순서대로 정렬하고， 다음으로 " 값이 0인 노드들 중에서 ^U2 ' ^k 값 이 1인 노드들을 ^<1 가 작은 순서대로 정렬하고， 다음으로 ^u u 및 ^u ^ ^k 값이 모두 0인 노드들을 ^α 가 작은 순서대로 정렬하고, 이하 반복으로서 , 다음으로

^Ul , ^k , ^{' "} ' ^Um , ^k 값이 모두 0인 노드들을 ^α 가 작은 순서대로 정렬 하는 방식!으로 함으로써， 최근에 왕복시간지연이 획득된 노드들에게 우선 순위를 부여하는 방법을 사용할 수도 있다. 이외에도 웅용 분야에 따라서 우선 순위 기반 의 다양한 정렬 방법이 존재할 수 있다.

[스템 S3030] 싱크 노드가 η-번째 사이클에서 1-번째 노드의 왕복시간지연 ( ， 을 추정하 고, 1-번째 노드의 데이터 패킷 수신 완료 시점 ( ^ei )을 계산한다.

93

대체용지 (규칙 제 26조) 좀 더 상세하게는, ""'- _" """'라고 정의하자. Λ는 2 이상인 자연수라고 하 자. °는 사용자가 정하는 값이다. 만약 ^≥ o이면， 즉, 최근 ^M 사이클 동안 1-번째 노드의 왕복시간지연이 성공적으로 획득된 경우가 ^회 이상인 경우에는 n- 번째 사이클에서 1-번째 노드의 왕복시간지연 ^，"을 다음 [수학식 303]과 같이 연 립 방정식을 풀어서 추정한다.

[수학식 303]

t Ι,η ⁼ to, _n + D _b , _n + ⁽ 5 _ljfl

나는 최소 차수의 다항식이다. 여기에서 , ( ᅳ " ) 사이클에서 1—번째 노드의 유효 한 왕복시간지연이 획득되었고, 그 때 1-번째 노드의 왕복시간지연 값은 一 이다. )는 (·Λᅳ 1)-차의 다항식으로서， 다항식 보간법을 이용하여 쉽게 구할 수 있다. 예를 들면， 분할된 차이 (divided difference) 방법을 이용할 수 있다. [수학식 303]은 ( ^< λ一 1)차 다항식과 1차 다항식의 연립 방정식으로서 , [수학식 303]의 2-번째 1차 다항식을 [수학식 303]의 1-번째 ᅳ ¹ )차 다항식에 대입하면 결과적으로 ( ― 1)차 다항식의 해를 구하는 문제로 귀결된다. [수학식 303]은 해 가 유일하게 존재하거나, 해가 존재하지 않거나， 해가 다수 존재하거나， 해가무수

94

대체용지 (규칙 제 26조) 히 많이 존재할 수도 있다. [수학식 303]의 해가 존재하지 않으려면， [수학식 303] 의 1-번째 ('Λᅳ 1 )차 다항식이 [수학식 303]의 2-번째 I 1차 다항식 위에 있거나 아 래에 있는 경우이다. 본 발명에서 ^{0 ≤ ≤ 5} -ax 이므로, 즉， 값은 범위가 제한되어 있으므로， [수학식 3Θ3]의 1-번째 (^― D차 다항식은 히，" 변화에 따라 서 일정한 범위 내에서 축과 평행에 가까운 형태로 그래프가 표현된다. 반면 에 [수학식 303]의 2-번째 1차 다항식은 기울기가 " 1" ^' 이다. 따라서 해가 존재하지 않는 경우는 발생하지 않는다. 또한, ^J i이 2인 경우에는 [수학식 303]의 1-번째

(Λᅳ 1 )치 I 다항식이 1차 다항식이 되는데 , 상기와 같은 이유로 [수학식 303]을 구 성하는 두 개의 1차 다항식의 기울기가 서로 달라져서， [수학식 303]의 실수 해가 유일하게 존재한다. ^이 3 이상인 경우에는 복소수 해를 포함하여 다수의 해가 존 재할 수 있으며， 실수 해도 여러 개 존재할 수 있다. 실수 해가 여러 개 존재하려 면 [수학식 303]의 1-번째 ( 一 차 다항식이 기울기 "1" 이상의 급격한 변화를 보여야 하며， 이것은 ^{0 ≤} ^ ¹ ^ ^≤ ^ax 임을 고려하면 ι ^, " 값의 히스토리가 양 끝 값인 "0" 또는 " m _ax " 값을 가지는 것을 뜻하므로, 이 경우에도 역시 실수 해는 1 개를 가질 확률이 매우 높다. 다르게 해석하면， 이와 같이 급격한 토폴로지 변화를 보이는 환경은 과거의 왕복 시간 지연 정보를 이용해서 현재의 왕복 시간 지연 정 보를 추정하는 것이 어려운 경우에 해당한다. 이때에도 본 발명은 왕복 시간 지연 정보를 보수적으로 적용하도록 설계되어 안정적으로 동작할 수 있다. 앞서, [수학 식 303]을 푸는 것은 ( ^« Λᅳ ¹ )차 다항식의 해를 구하는 것과 같다고 언급하였는데，

95

대체용지 (규칙 제 26조) 일반적으로 (^ᅳ D차 다항식은 ("Λ一 1) 개의 해를 가지몌 여기에는 복소 해와 실수 해가 혼합되어 있다. 본 발명에서는 [수학식 303]을 해석적으로 직접 푸는 것 보다는 다음과 같이 인터택티브 (iterative)하게 구한다. 먼저， ^"의 초기값을 정 한다. 예를 들면, ^{= ί} ο, _η + Α," +«ι ^로 한다. 이외에도，

*1, ^η = n + . + ^max 등과 같이 초기값을 정하는 방법은 다양하게 있으며, ^."에 근접하는 값이 되도록 설정하는 것이 좋다. 이제, 초기값 을 이용하여

[수학식 303]으로부터 i ^, "을 ，' ' = ¹ (^，")과 갈이 계산한다. 그리고 이와 같 이 계산된 ^' 을 이용하여 "을 ^," ⁼ ". + Α,". + ^,"과 같이 계산하고, 이 때 계산된 ^， 으로부터 "을 ^^ ^{= <} d,n)과 같이 계산한다. ^'".을 이용하 여 ^^을 ^,η ⁼ Ο,™ + + 과 같이 계산하고 ' 계산된 ^Ι,η으로부터 ^,^을 = 과 같이 계산하는 과정을 정해진 횟수만큼 반복한 후에 최종적으 로 계산되는 값을 "과 으로 확정한다. 이때， 반복 횟수를 정하지 않고， 이전 에 계산된 ^"과 현재 계산된 ^"의 차이가 일정값 이하인 경우에 반복과정을 중 단하는 방법이 있다. 마찬가지로， 이전에 계산된 ^，"과 현재 계산된 ^"의 차이가 일정값 이하인 경우에 반복과정을 중단하는 방법도 있다. ，"은 ⁵ n^x보다는 작으 므로， 다음 수학식 304와 같이 값을 제한함]

96

대체용지 (규칙 제 26조) [수학식 304]

, _n = min{5 _{m ax} , ^， J

[ _ax 는 왕복시간지연의 최대값임] 그리고, 1-번째 노드의 데이터 패킷 수신 완료 시점 ^ei 을 다음 [수학식 305]와 같이 계산한다.

[수학식 305] e i = *0 + Α ^Ι + Α

[ ^은 _n -번째 사이클에서 번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값이며; ^T 는 가드 시간임 ] 만약 «Λ < 이면, 즉, 최근 M 사이클 동안 i -번째 노드의 왕복시간지연 이 성공적으로 획득된 경우가 ^회 미만인 경우에는， 과거에 획득된 시간지연으로 부터 현재 ί의 시간지연을 추정하는 것이 타당하지 않다고 판단한다. 이때는, 다음

[수학식 306]과 같이 η-번째 사이클에서 1-번째 노드의 왕복시간지연 ^,™을 추정 하고, 1-번째 노드의 데이터 패킷 수신 완료 시점 ^ei 을 계산한다.

97

대체용지 (규칙 제 26조) [수학식 306]

Κ = min{<5 _max , « ₁ + 2¾ _{m ax} C _n _ _x ( - l _x )/ c _{m in} }

[이은 가장 최근에 획득된 —번째 노드의 왕복시간지연이며， ^U max는 싱크 노드와 k-번째 노드간의 최대 상대속도이며， C ^ᅳ 은 -번째 사이클의 지속시간 이며, ¹ 은 1-번째 노드의 왕복시간지연이 획득된 가장 최근 사이클이며， ^C min은 수중에서의 최소 음파 전달 속도임 ]

[수학식 306]과 같이 1-번째 노드의 왕복시간지 I연이 획득된 가장 최근 시점 으로부터 가능한 최대 변동폭을 이용하여 왕복시간지연을 추정하면， 층돌을 원천적 으로 회피할 수 있다. [수학식 306]에서 ⁷ ι은 1-번째 노드의 왕복시간지연이 획득된 가장 최근 사이클이므로 ( ᅳ 은 왕복시간지연 획득 후에 소요된 시간을 의미하 고, 이때 평균적인 사이클 지속시간을 가장 최근 사이클인 (n-1)-번째 사이클 지속 시간으로 근사하면 S max^— l( ^{n _ Z} l)/ ^c mi _n 은 가장 최근에 왕복시간지연이 획 득된 후에 n-번째 사이클에서의 왕복시간지연이 가질 수 있는 최대 변동폭이 된다. 따라서 + ^ ^-^/^ 은 ^번째 사이클에서 번째 노드의 최대 왕 복시간지연이 되고, 이 값이 ⁵ ma _X 를 초과할 수 없으므로 [수학식 306]과 같이 1- 번째 노드의 왕복시간지연을 계산한다. 가장 최근 개의 사이클 중에서 개 미만의 사이클에서만 1-번째 노드의 왕복시간지연이 획득되었다는 것은, 물리계층

98

대체용지 (규칙 제 26조) 이 완벽하다면 1-번째 노드의 이동성이 갑작스럽게 변하여 다른 노드들의 패킷과의 충돌을 발생한 것으로 인지할 수 있고, 따라서 과거 왕복시간지연 정보로부터 n-번 째 사이클에서의 왕복시간지연을 추정하는 것은 바람직하지 않음에 유의하여야 한 다ᅳ 또한， 이와 같이 계산된 ，„은 ， n이 가질 수 있는 가장 큰 값이므로, ^e i을 계산함에 있어 [수학식 306]에서는， [수학식 305]와는 달리， 가드 시간을 포함하지 않는다.

[스텝 S3040]

싱크 노드에 의해 변수 (k)가 마지막—번째 (K-번째)보다 작은 지의 여부를 판 단한다.

[스템 S3050]

상기 스텝 (S3040)에서 상기 변수 (k)가마지막 -번째 (K-번째) 보다 작으면 (Y) , 싱크 노드가상기 변수 (k)를 k+1로 설정한다.

[스텝 S3060] 싱크 노드가 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정한 다. 좀 더 상세하게는, '라고 정의하자. 만약 이면， 즉, 최근

^M 사이클 동안 k-번째 노드의 왕복시간지연이 성공적으로 획득된 경우가 ^회 이

99

대체용지 (규칙 제 26조) 상인 경우에는, 다음 [수학식 30기과 같이 η-번째 사이클에서 k—번째 ^' 노드의 왕복 시간지연 ^ 을 추정한다.

[수학식 307] . _' n = Qki ^e k- \)

나는 최소 차수의 다항식이다. 여기에서， ―" 사이클에서 k-번째 노드의 유효 한 왕복시간지연이 획득되었고， 그 때 k-번째 노드의 왕복시간지연 값은 네 이다. ¾( 는 (^ᅳ 1)-차의 다항식으로서， 다항식 보간법을 이용하여 쉽게 구할 수 있다. 수학식 307은 과거에 획득된 왕복시간지연 정보를 수치해석적 보간법으로 근사하고, 바로 직전 데이터 패킷인 (k-1)-번째 노드의 데이터 패킷의 수신이 종료 되는 시각인 ^e n 시각에 k-번째 데이터 패킷이 수신될 때 왕복시간지연 ( ， ")을 계산한 것임]

따라서 k-번째 노드가 비콘 패킷을 받자마자 데이터패킷을 송신하여 왕복시 간지연 (^^)을 가지면서 싱크 노드에 k-번째 노드의 데이터 패킷이 수신되기 시작 하는 시각 (^ 는 다음 [수학식 308]과 같이 계산된다，

100

대체용지 (규칙 제 26조) [수학식 308]

P'k ⁼ Ο, η + D _b , _n + S _k , _n

이때, 만약 ^{Pk> Gk} → 아면， k-번째 노드가 비콘 패킷을 받자마자 데이터 패 킷을 송신해도 (k-1)-번째 노드의 데이터 패킷 수신이 완료되고 나서 Pk― ^e k - 1 만큼의 시간이 지난 후에 _k -번째 노드꾀 데이터 패킷 수신이 시작 되므로， [수학식 30기에 의해서 추정한 시각에서의 k-번째 노드의 왕복시간 지연은 실제 k-번째 노드의 데이터 패킷이 도착하는 시점에서의 왕복시간지연 추정 치로서 적 ί절하지 않다. 따라서 [수학식 303]을 반복적인 방법으로 풀어서 1-번째 노드의 ^복시간지연을 추정한 방식으로 k-번째 노드의 왕복시간지연을 추정해야 한다. 따라서 P^ ^ek → 인 경우에는 다음과 같이 연립방정식인 [수학식 309]를 풀 어서 k-번째 노드의 왕복시간자연 을 추정한다. [수학식 309]

t k,n ⁼

[수학식 303]에서와 마찬가지로, [수학식 309]는 ᅳ 1 )차 다항식의 해를 구하는 문제로서, 가 2인 경우에는 실수 해가 유일하게 존재하므로 해석적 해를

101

대체용지 (규칙 제 26조) 이용하고， 가 3 이상인 경우에는 다음과 같이 반복적인 방법을 이용하여 해를 구 한다. 먼저， ^，"의 초기값을 정한다. 예를 들면 = ^ί ₀ ,η + fc으로 한 다. 이외에도, ^ᅳ" + A, _n + _max 등과 같이 초기값을 정하는 방법은 다양 하게 있으며， 에 근접하는 값이 되도록 설정하는 것이 좋다. 이제, 초기 값 을 이용하여 [수학식 309]로부터 을 ^ = ' ( )과 같이 계산한 다. 그리고 이와 같이 계산된 을 이용하여 ^,"을 ^4* 과 같이 계산하고， 이때 계산된 ，"으로부터 ^,"을 ^'η = Q/c U과 같이 계산한 다. „을 이용하여 ,n을 fc'n = Ο,η + + ·,ή.과 같이 계산하고， 계산된

^，"으로부터 ^^을 ， n = fc /cJ과 같이 계산하는 과정을 정해진 횟수만큼 반 복한 후에 최종적으로 계산되는 값을 과 ，"으로 확정한다. 이때, 반복 횟수를 정하지 않고, 이전에 계산된 과 현재 계산된 ᅳ"의 차이가 일정값 이하인 경우 에 반복과정을 중단하는 방법이 있다. 마찬가지로， 이전에 계산된 ^， 과 현재 계 산된 ^ 의 차이가 일정값 이하인 경우에 반복과정을 중단하는 방법도 있다. m _ax 보다는 작으므로, 다음 [수학식 310]과 같이 값을 제한한다.

102

대체용지 (규칙 제 26조) [수학식 310] 만약 Λ' < ^이면, 즉， 최근 M 사이클 동안 _k -번째 노드의 왕복시간지연 이 성공적으로 획득된 경우가 ^Q 회 미만인 경우에는, 과거에 획득된 시간지연으로 부터 현재의 시간지연을 추정하는 것이 타당하지 않다고 판단한다. 이때에는 다음

[수학식 311]과 같이 n-번째 사이클에서 k-번째 노드의 왕복시간지연 을 추정 한다.

[수학식 311]

¾, = max{0, a _k ᅳ 2v _{m ax} C 一 ι ( ^η ᅳ )/'c _{m in} } 상기 [수학식 311]은 [수학식 306]과는 다른데 이것은 연속되는 데이터 패 킷의 충돌을 회피하기 위해서는 이전 데이터 패킷의 종료 시각은 늦게 추정되는 방 향으로 해야 하고， 다음 데이터 패깃의 수신 시각은 빠르게 추정되는 방향으로 해 야 하기 때문이다.

[스텝 S3070]

싱크 노드가 상기 스텝 (S3060)에서 추정된 k-번째 노드의 왕복시간지

103

대체용지 (규칙 제 26조) 연 을 이용하여， k-번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할 때， k-번째 노드의 데이터 패¾이 싱크 노드에 수신되기 시작하는 시각의 추정 값 ( ^ )을 상기 [수학식 308]과 같이 계산한다.

[스텝 S3080]

싱크 노드가 상기 스텝 (S3070)에서 계산된 k-번째 노드의 데이터 패킷이 싱 크 노드에 수신되기 시작하는 시각의 추정값 을 이용하여 k-번째 노드의 대기 시간 을 다음의 [수학식 _{312 ]} 와 같이 계산한다ᅳ

[수학식 312] 'k, _n = max{0, e _k - p _k }

이와 같이, n-번째 사이클에서 k-번째 노드가 비콘 패킷을 수신한 후에

^Wk - " 시간만큼 대기한 후에 데이터 패킷을 송신하면 (k— 1)-번째 노드의 데이터 패 킷이 수신 완료된 후에 k-번째 노드의 데이터 패킷이 수신되어， 싱크 노드에서 데 이터 패킷 수신 충볼이 발생하지 않는다.

[스텝 S3090]

싱크 노드가 상기 스텝 (S3070)에서 계산된 k-번'째 노드의 데이터 패킷이 싱 크 노드에 수신되기 시작하는 시각의 추정값 과 상기 스템 (S3080)에서 계산된

104

대체용지 (규칙 제 26조) k-번째 노드의 대기 시간 ( ^ ^" . " )을 이용하여 k-번째 노드의 데이터 패킷이 수신 완 료되는 시각의 추정값 을 계산한 후 상기 스텝 (S3040)으로 진행된다. 좀 더 상세하게는， 만약 Λ≥ o이면 (즉， 최근 M 사이클 동안 _k _번째 노 드의 왕복시간지연이 성공적으로 획득된 경우가 ^회 이상인 경우에는) k-번째 노 드의 데이터 패킷이 수신 종료되는 시각 은 다음 [수학식 ₃₁₃ ]과 같이 계산된 다.

[수학식 313]

6 fc = Pfc + A, _n + ^w k,n +

[ '"은 n-번째 사이클에서 k-번째 노드의 데이터 패킷 길이를 시간으로 환 산한 값임] 한편， 만약 ^fc < ^이면 (즉, 최근 M 사이클 동안 1-번째 노드의 왕복시 간지연이 성공적으로 획득된 경우가 ^/o 회 미만인 경우에는) k-번째 노드의 데이터 패킷이 싱크 노드에서 수신 완료되는 시각의 추정값 은 다음의 [수학식 314]와 같이 계산된다.

105

대체용지 (규칙 제 26조) [수학식 314] e¾ = o,n + ^D b.n + ^k,n + min{5 _max , a _k + 2v _max C _n _ ₁ (n- l _k )/c _m{n ] + D _k , _n e _k

[스텝 S3100]

상기 스텝 (S3040)에서 변수 (k)가 마지막 -번째 (K 번째) 보다 작지 않으면 (N), 싱크 노드가 비콘 패킷의 방송 유무를 판단한다.

즉 K-번째 노드의 스케즐 계산이 완료되면， 성크 노드가 비콘 패킷의 방송 유무를 판단하여 사이클 진행 여부를 결정한다. 한편， 스템 (S3040)에서 비콘 패킷이 방송되지 않으면 (N) (즉, 사이클을 진행 하지 않는 경우에는) 모든 절차를 종료한다.

[스텝 S3110]

상기 스텝 (S3100)에서 비콘 패킷이 방송되어 사이클이 계속해서 진행되는 경 우에는 (Y), 싱크 노드는 n—번째 사이클에서 싱크 노¾가 비콘 패킷을 방송하기 시 작하는 시각 (^ᅳ")에 비콘 패킷을 방송한다.

[스템 S3120]

106

대체용지 (규칙 제 26조) K-번째 노드의 데이터 패킷 수신이 완료되었거나 Κ—번째 노드의 데이터 패 킷이 수신 완료되는 시각의 추정값 이 초과된다.

[스템 S3130]

상기 스텝 (S3120)이 진행된 후， 싱크 노드는 n-번째 사이클에서 k-번째 노드 의 왕복시간지연 을 계산하고， 왕복 시간 지연 획!득 유효성 값 및 가 장 최근에 획득된 왕복 시간 지연 관련 정보 ( ^α , 4)를 갱신한다.

좀 더 상세하게는， 시각에 비콘 패킷을 방송한 후에, Κ-번째 노드의 데 이터 패킷 수신이 완료되었거나 ^ek 시각을 초과하면， 싱크 노드는 n—번째 사이클 에서의 각 노드들로부터 데이터 패킷의 성공적인 수신 여부를 알 수 있다. 먼저,

^Um ' ^k 값을 갱신하기 위해서, 다음 [수학식 315]와 같이 모든 ⁼ 1,2,··· K 및 = 1,2,···,Λ/ᅳ 1에 대하여 노드들에 대해서 ^u m,k 값을 다음 [수학식

315]와 같이 갱신한다.

[수학식 315]

+ 1 , ¾ , k n-번째 사이클에서 k-번째 노드의 데이터 패킷을 성공적으로 수신하였으면, 다음의 [수학식 316]과 같이 한다.

107

대체용지 (규칙 제 26조) [수학식 316] n-번째 사이클에서 _k -번째 노드의 데이터 패킷을 성공적으로 수신하지 못한 경우에는 다음의 [수학식 31기과 같이 한다.

[수학식 317] , ui , k = 0 그리고， 가장 최근에 확득된 왕복 시간 지연 관련 정보 (4)는 다음의 [수학 식 318]과 같이 갱신한다. [수학식 318]

&한, 왕복 시간 지연 획득 유효성 값 )이 1인 경우에는， 다음의 [수 학식 319]1와 같이 n-번째 사이클에서 k-번째 노드의 왕복시간지연 ( ^. " )을 계산하 고， 가장 최근에 획득된 왕복 시간 지연 관련 정보 ( ^α )를 갱신한다.

108

대체용지 (규칙 제 26조) [수학식 319]

^k, n 二 ^k, nᅳ (^Ο , η + ^b,n + ^W k, n ->

ak ⁼ ^k, n

[스텝 S3140]

싱크 노드가 n을 1만큼 증가시킨 후 (n+1)-번째 사이클을 위한 ^ " ⁺ ι 계 산을 위하여 상기 스텝 (S3020)으로 진행된다. 본 발명의 제 3 실시예에 의한 수중 무선 이동 네트워크를 위한 스케즐링 방 법에 의하면， 싱크 노드가 초기화 과정을 수행하고; 상기 싱크 노드가 데이터 패킷 수신 순서를 결정한 후 η-번째 사이클에서 1-번째 노드에게 부여되는 시간 지 연 ( ^ι, ^η )을 0으로 설정하며; 싱크 노드가 η-번째 사이클에세 1-번째 노드의 왕복 시간지연 을 추정하고， 1-번째 노드의 데이터 패¾ 수신 완료 시점 을 계 산하며; 싱크 노드에 의해 변수 (k)가 마지막 -번째 (K-번째)보다 작은 지의 여부를 판단하며; 상기 판단에서 변수 (k)가 마지막 -번째 (K-번째) 보다 작으면, 싱크 노드 가 변수 (k)를 k+1로 설정하며; 싱크 노드가 n-번째 사이클에서 k-번째 노드의 왕복 시간지연 을 추정하며; 싱크 노드가 상기 추정된 k-번째 노드의 왕복시간지 연 을 이용하여， k-번째 노드가 비콘 패킷을 받자마자 데이터 패킷을 송신할

109

대체용지 (규칙 제 26조) 때, k-번째 노드의 데이터 패킷이 싱크 노드에 수신되기 시작하는 시각의 추정 값 을. 계산하며; 싱크 노드가 계산된 k-번째 노드의 데이터 패킷이 싱크 노드 에 수신되기 시작하는 시각의 추정값 을 이용하여 k-번째 노드의 대기 시 간 ( ^ " )을 계산하며; 상기 싱크 노드가 상기 계산된 k-번째 노드의 데이터 패킷 이 싱크 노드에 수신되기 시작하는 시각의 추정값 ( ^p ^ 과 상기 계산된 k-번째 노드 의 대기 시간 ( ^ " )을 이용하여 k-번째 노드의 데이터 패킷이 수신 완료되는 시각 의 추정값 ( 을 계산한 후 상기 판단 과정으로 진행되도록 구성됨으로써 :

즉， 수증음향 무선 이동 네트워크와 같이 왕복시간지연이 크고 물리 계층의 전송 속도가 낮은 네트워크 환경에서, 채널 사용 효율 향상을 통한 네트워크 효율 을 향상새킬 수 있고， 시간 동기화가 필요 없으므로 시간 동기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 웅용 분야에서도 활용이 가능하며, 오 차가 누적되지 않고 주기적인 재초기화가 필요 없다는 뛰어난 효과가 있다. 특히, 노드 수가 증가할수톡 네트워크 효율 향상 정도는 더욱 증가한다. 본 발명에 따른 다항식 보간법을 이용한 수중 네트워크 스케즐링 방법은 절대 시간 기준이 아니라， 시간 차이!에 해당하는 정보에 의해서 결정되므로， 각 노드들의 로컬 시각 정보가 서로 상이하더라도 정확하게 동작한다. 따라서 시간 동기화가 필요 없으므로 시간 동기화가 불가능하거나 시간 동기화를 위해서 많은 자원이 소모되는 웅용 분야에서 도 활용이 가능하다.

또한， 왕복 시간지연 정보에 대한 정확한 값이 매 사이클마다 얻어지므로, 오차가 누적되지 않고 추기적인 재초기화가 필요 없다.

110

대체용지 (규칙 제 26조) 도면과 명세서에는 최적꾀 실시예가 개시되었으며， 특정한 용어들이 사용되 었으나 이는 단지 본 발명의 실시형태를 설명하기 위한 목적으로 사용된 것이지 의 미를 한정하거나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다. 그러므로， 본 기술 분야의 통상의 지식을 가진자라면 이로부터 다양 한 변형 및 균등한 타 실시예가 가능하다는 점을 이해 I할 수 있을 것이다. 따라서, 본 발명의 ί 진정한 기술적 보호범위는 첨부된 특허청구범위의 기술적 사상에 의해 정해져야 할 것이다.

111

대체용지 (규칙 제 26조)