Neighbor discovery is of paramount importance in initialization of wireless ad hoc networks. In this paper, we deal with a variety of neighbor discovery algorithms. Vasudevan, Sudarshan, et al. (2013) designed non-feedback/feedback based neighbor discovery algorithms in single-hop networks having n nodes. They considered two cases where all nodes initially know the network size or not. They argue that the order of running time of feedback based algorithm is O(n) and that of non-feedback algorithm is O(n log n) regardless of the fact that initial network size is known to all nodes or not. However, we find that the order of running time of feedback-based algorithm when the initial network size is unknown to all nodes is indeed $(2^{\lceil \log_2 n \rceil} - n)O(ln n)$ + O(n). We propose two neighbor discovery algorithms for this case. The first algorithm uses maximum likelihood estimation and the other uses adaptive transmission probability. We simulated these algorithms and the simulation results showed great performance enhancement compared to the previous algorithms not using maximum likelihood estimation and adaptive transmission probability. In addition, we assume a simple packet error case and find that the order of running time of a feedback based neighbor discovery algorithm with initial network size n is $O(n(\log_{1/Pe} n+1))$ when the network has a positive packet error probability $P_e$. The order of running time of non-feedback neighbor discovery algorithm when the initial network size is known to all nodes in a packet error case is multiplied by a factor of $O(\log_{1/Pe}n+1)$ compared to no packet error case.
최근에 에드혹 네트워크가 주목받으면서 에드혹 네트워크에서 가장 초기에 시작되는 이웃 발견 알고리듬에 대한 연구가 활발히 진행되었다. 에드혹 네트워크에서 노드 수를 초기에 모든 노드들이 알고 있을 때와 모를 때 어떤 알고리듬을 사용해야 하며, 그 성능은 얼마인지에 대해서도 연구되었다. 그런데 기존 연구에서 초기 노드 수를 모르고, 피드백을 사용하는 알고리듬에 대한 분석에서 수학적 오류가 있음이 발견되었다. 이에 본 논문에서는 기존 알고리듬의 성능을 올바르게 수학적으로 밝혔다. 또한, 초기에 노드 수를 추정하는 방법과 주변 환경에 맞게 전송 확률을 변화시키는 방법을 사용하는, 기존 알고리듬보다 개선된 알고리듬들을 제안하였다.
다음으로는 채널에서 패킷 전송 에러가 존재하는 경우를 수학적으로 모델링하여 예상되는 성능을 분석하였다. 이 경우에 사용될 수 있는 알고리듬을 제안하고 그 성능을 분석하였다. 그리고 이러한 알고리듬들의 성능을 시뮬레이션을 통해 보였다.
