Abstract: We have designed and implemented an algorithm for discovering neighborhood and estimating the timeliness link quality between neighbors using active probing， passive overhearing and WMEWMA(Window Mean Exponentially Weighted Moving Average Estimator). The link layer relay service presented in this paper mitigates the effect of asymmetric links so as to discover more neighbors. We have evaluated the algorithm using both static analysis and simulation through the TOSSIM simulator. Results show that the algorithm is effective, that more than 40% of nodes identify more outbound neighbors and that the percentage of increased outbound neighbors is between 14% and 100%.

Key words: wireless sensor network, neighborhood discovery, link quality estimation, link layer relay service