We construct reliable connected dominating set in wireless ad hoc networks. Unlike previous techniques, the choice of dominators in these schemes, are based not on node characteristics but on the link characteristics. We define the link reliability as the association of link stability and packet error rate. We propose different distributed heuristic algorithms, enhanced marking, high-reliability and recommendation algorithm. To compare with distributed algorithms, we also propose a centralized algorithm, minimum energy tree-growing algorithm. Through performance evaluation, we show that high-reliability scheme is the best results in the distributed algorithm. Our simulations show the proposed algorithms increase few CDS sizes of existing algorithm and decrease the energy cost that means packet retransmissions.
무선 애드혹 네트워크는 이동 단말기들이 기지국 같은 고정된 기간망이 없이 각 단말기들 사이에서 통신이 이루어지는 것으로, 각 단말기가 라우터의 역할까지 수행하여 데이터 트래픽을 주위 노드들에게 전달해주는 일을 수행한다. 이 때 다양한 트래픽들이 발생하면서 이들이 목적지까지 패킷을 전달할 수 있는 경로를 찾는 많은 메시지들을 주고 받게 되면서 네트워크가 복잡해지게 된다. 따라서 임의의 가상 백본을 구성하여 네트워크를 간단하고 효율적으로 운영할 수 있는 다양한 연구들이 진행되고 있다. 기존의 연구들에서는 주로 각 단말기들의 주소번호나 에너지 양 등의 기준을 통해 백본을 형성하는 연구들이 많았으나, 우리는 단말기 중심이 아닌 단말과 단말 사이의 링크 특성을 고려하여 백본을 형성하고자 하였다. 무선 환경은 단말기들이 이동하고 전송 오류가 많아 패킷 전송에 실패하여 재전송이 요구되는 경우가 많다. 따라서 이런 재전송이 적게 일어날 수 있는 링크들을 통해 백본을 형성하고자 하는 것이 논문의 목적이었다. 이를 위해 실제 무선 애드혹 환경에서 적용 가능한 분산된 각 단말기에서 백본을 구성할 수 있는 다양한 알고리즘들을 제안하였다. 그 결과 각 단말기가 자신과 연결된 링크들의 신뢰도 합을 계산하여, 이 값이 주변에서 가장 큰 경우에 백본에 속하게 되는 알고리즘의 성능이 가장 좋음을 볼 수 있었다. 이 알고리즘은 백본을 형성하는 단말기의 수를 줄이면서 또한 백본을 형성하는 노드 사이의 링크의 에너지 비용 값도 같이 줄일 수 있는 결과를 보였다.
