1 |
1
삭제
|
2 |
2
삭제
|
3 |
3
삭제
|
4 |
4
삭제
|
5 |
5
삭제
|
6 |
6
삭제
|
7 |
7
삭제
|
8 |
8
삭제
|
9 |
9
삭제
|
10 |
10
삭제
|
11 |
11
그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법에 있어서, 브로드캐스트 통신을 수행하는 노드들의 연결 형태를 나타내는 연결 매트릭스 및 상기 연결 매트릭스를 기초로 상기 노드들에 동일한 타임슬롯을 할당할 수 있는지 여부를 나타내는 공존 가능 매트릭스를 생성하는 단계; 상기 노드들에 할당되는 타임슬롯들의 개수 및 상기 타임슬롯들의 사용률에 따라 정의되는 목적 함수를 계산하는 단계; 상기 계산된 목적 함수에 기초하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯과 관련된 가능한 해들 중 프로듀서 해, 스크라운저 해들 및 레인저 해들을 설정하고, 업데이트하는 단계; 적어도 하나의 세대 동안에 상기 목적 함수에 대응하는 평가값이 최소화되도록 상기 공존 가능 매트릭스를 참조하여, 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 중 최적의 해를 획득하는 단계; 및 상기 최적의 해를 참조하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯을 결정하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
12 |
12
제11항에 있어서,상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들을 설정하고, 업데이트하는 단계는 상기 계산된 평가값에 기초하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯과 관련된 가능한 해들 중 최적화된 상기 프로듀서 해를 선택하는 단계; 상기 프로듀서 해를 제외한 상기 가능한 해들 중 미리 설정된 확률에 따라 상기 스크라운저 해들을 획득하는 단계; 상기 가능한 해들 중 상기 프로듀서 해 및 상기 스크라운저 해들을 제외한 나머지 해들을 상기 레인저 해들로 설정하는 단계;상기 스크라운저 해들 및 상기 레인저 해들 각각을 업데이트하는 단계; 및 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 각각에 대응하는 평가값을 계산하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
13 |
13
제12항에 있어서,상기 프로듀서 해를 선택하는 단계는 상기 가능한 해들 중 상기 프로듀서 해를 제외한 이웃해들을 탐색하는 단계; 상기 이웃해들 각각의 확률 난수를 생성하는 단계; 상기 생성된 확률 난수가 미리 설정된 기준 확률 난수의 범위 내에 있는 경우, 상기 공존 가능 매트릭스를 참조하여 상기 이웃해들을 변경하는 단계; 상기 변경된 이웃해들 각각에 대응하는 평가값을 계산하는 단계; 및 상기 계산된 평가값에 기초하여 상기 프로듀서 해 및 상기 변경된 이웃해들로부터 상기 프로듀서 해를 업데이트하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
14 |
14
제12항에 있어서,상기 스크라운저 해들 및 상기 레인저 해들 각각을 업데이트하는 단계는 상기 스크라운저 해들 각각의 확률 난수를 생성하는 단계; 및 상기 생성된 확률 난수가 미리 설정된 기준 확률 난수의 범위 내에 있는 경우, 상기 프로듀서 해를 참조하여 상기 스크라운저 해들 각각을 변경하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
15 |
15
제12항에 있어서,상기 스크라운저 해들 및 상기 레인저 해들 각각을 업데이트하는 단계는 상기 레인저 해들 각각의 확률 난수를 생성하는 단계; 및 상기 생성된 확률 난수가 미리 설정된 기준 확률 난수의 범위 내에 있는 경우, 상기 레인저 해들을 변경하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
16 |
16
제11항에 있어서,상기 최적의 해를 획득하는 단계는 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 중 상기 노드들에 할당되는 타임슬롯들의 개수 및 상기 타임슬롯들의 사용률 사이의 차가 가장 작은 상기 최적의 해를 추출하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
17 |
17
제11항에 있어서,상기 연결 매트릭스에 포함되는 원소들 각각은 상기 노드들이 서로 인접해 있는지 여부에 따라 제1 논리값 또는 제2 논리값 중 어느 하나로 결정되는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
18 |
18
제11항에 있어서,상기 공존 가능 매트릭스에 포함되는 원소들 각각은 특정 노드에 할당된 타임슬롯이 동일하게 다른 노드에 할당되었는지 여부에 따라 제1 논리값 또는 제2 논리값 중 어느 하나로 결정되는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
19 |
19
제11항에 있어서,상기 목적 함수를 계산하는 단계는 특정 타임슬롯이 특정 노드에게 할당되었는지 여부에 따라 제1 논리값 또는 제2 논리값 중 어느 하나로 결정되는 이진 정수 의사 결정 변수를 이용하여 상기 타임슬롯들의 사용률을 계산하는 단계를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 방법
|
20 |
20
제11항 내지 제19항 중 어느 한 항의 방법을 수행하기 위한 프로그램이 기록된 컴퓨터로 판독 가능한 기록 매체
|
21 |
21
그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 장치에 있어서, 브로드캐스트 통신을 수행하는 노드들의 연결 형태를 나타내는 연결 매트릭스 및 상기 연결 매트릭스를 기초로 상기 노드들에 동일한 타임슬롯을 할당할 수 있는지 여부를 나타내는 공존 가능 매트릭스를 생성하는 매트릭스 생성부; 상기 노드들에 할당되는 타임슬롯들의 개수 및 상기 타임슬롯들의 사용률에 따라 정의되는 목적 함수를 계산하는 목적 함수 계산부; 상기 계산된 목적 함수에 기초하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯과 관련된 가능한 해들 중 프로듀서 해, 스크라운저 해들 및 레인저 해들을 설정하고, 업데이트하는 해 설정부; 적어도 하나의 세대 동안에 상기 목적 함수에 대응하는 평가값이 최소화되도록 상기 공존 가능 매트릭스를 참조하여, 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 중 최적의 해를 획득하는 최적해 획득부; 및 상기 최적의 해를 참조하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯을 결정하는 결정부를 포함하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 장치
|
22 |
22
제21항에 있어서,상기 해 설정부는 상기 계산된 평가값에 기초하여 상기 노드들 각각에 할당되는 적어도 하나의 타임슬롯과 관련된 가능한 해들 중 최적화된 상기 프로듀서 해를 선택하고, 상기 프로듀서 해를 제외한 상기 가능한 해들 중 미리 설정된 확률에 따라 상기 스크라운저 해들을 획득하며, 상기 가능한 해들 중 상기 프로듀서 해 및 상기 스크라운저 해들을 제외한 나머지 해들을 상기 레인저 해들로 설정하고, 상기 스크라운저 해들 및 상기 레인저 해들 각각을 업데이트하며, 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 각각에 대응하는 평가값을 계산하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 장치
|
23 |
23
제21항에 있어서,상기 최적해 획득부는 상기 프로듀서 해, 상기 스크라운저 해들 및 상기 레인저 해들 중 상기 노드들에 할당되는 타임슬롯들의 개수 및 상기 타임슬롯들의 사용률 사이의 차가 가장 작은 상기 최적의 해를 추출하는 그룹 탐색 최적화 기법을 적용한 브로드캐스트 스케줄링 장치
|