In Ad-hoc 2-tier Network, only part of hosts are used as routers that participate in management and routing, therefore 2-tier network can reduce scalability and energy consumption. And virtual backbone is the set of hosts used as routers in this 2-tier network. To minimize the number of hosts participating in virtual backbone, Minimum Connected Dominating Set (MCDS) or Minimum Dominating set (MDS) is used. However, these theories consider only topology of network and decide minimum hosts participating in virtual backbone. But this is not efficient when consider characteristic of radio environment and characteristic of traffics.
Energy Efficient Connected Dominating set is the virtual backbone for multicast. It has two object that are to minimize the number of hosts participating in virtual backbone and to minimize the number of transmission to supporting multicast. For addressing this EECDS in this paper, Facility Location Problem and Linear Integer Problem are proposed.
임시 비상망은 어떤 기반 시설 없이 단말사이의 통신을 지원한다. 임시 비상망에서 각 단말은 데이터 교환의 시작과 목적지의 역할을 함은 물론 서로간의 통신을 위한 데이터를 전달해주는 라우터의 역할을 수행한다.
임시 비상 2계층 망에서는 단말의 오직 일부만이 관리와 라우팅을 위한 라우터로 사용되는데 이를 통해 망의 크기와 전력소비를 줄일 수 있다. 그리고 2계층 망에서 라우터로 사용되는 단말들의 집합을 가상 백본이라고 한다.
최소의 연결된 지배 집합은 가상 백본을 구성하기 위해 사용된다. 그러나 이런 이론은 오직 망의 지리적 특성만을 고려하여 가상 백본에 참여하는 최소의 노드를 결정하는 것이다. 하지만 이것은 무선환경의 특징과 트래픽의 성격을 고려할 경우 효율적이지 못하다. 무선 환경은 한번의 전송으로 동시에 여러 노드가 데이터를 받을 수 있는 강점을 가지고 있고, 따라서 같은 멀티캐스트 세션과 같은 경우 가까운 위치에 있는 단말들은 최소한의 데이터 전송으로 만족시키는 것이 더 효율적이다.
이와 같이 백본에 속하는 노드의 수를 최소화 하면서 멀티캐스트를 효율적으로 지원하고자 하는 에너지 효율이 높은 연결된 지배 집합을 이 논문에서 연구하고자 한다.
그리고 이를 위해 백본에 속하는 노드의 수를 최소화 하는 문제를 설비 배치 문제 (Facility Location Problem)를 이용하여 풀고 이를 에너지 효율이 높은 연결된 지배 집합을 구하는 데 확장하여 선형 정수 계획법으로 문제를 해결하였다.
