Research On Group Neighbor Discovery Algorithms In Next- Generation Wireless Networks

The 21st century has witnessed great success of wireless networks. Centralized cellular networks and WiFi networks have made their way into our life. Meanwhile, wireless ad-hoc networks have received tremendous attentions in recent years because of their self-organization and self-maintenance. The popularization of various applications powerfully impels the development of low energy-cost and high capacity-approaching technologies, and the development of wireless networks. Duty-cycle wireless sensor networks and wireless ad-hoc networks with multi-packet reception (MPR) capability are two typical examples of next-generation wireless networks.In this work, we study group neighbor discovery problem in next-generation wire-less ad-hoc networks. Neighbor discovery is an essential step for the initialization of large-scale ad-hoc networks. In particular, we are interested two kinds of ad-hoc model: duty-cycle and channel-based multi-packet reception. To conserve energy, wireless sta-tions alternate between active and dormant states in duty-cycle mode. In MPR mode, wireless stations could decode more than one packet from multiple concurrent trans-missions. Both modes pose challenges and opportunities to neighbor discovery. One successful transmission does not reach all neighbors in duty-cycle scenario, and several parallel discoveries can happen in MPR scenario.We present several randomized algorithms, and exploit asymptotic analysis and probability analysis tools to study their performance. In duty-cycle networks, we prove that the discovery time is O(n In n In In n) with high probability, O(ln In n) higher than all-awake ad-hoc networks. In MPR networks, we prove that the tight lower bound for all algorithms is θ(n/κ), and present two algorithms that achieve bound Θ(n lnn/κ) and Θ(n/k) with high probability. These results broaden the understanding of neighbor discovery in duty-cycle and MPR wireless networks. The proposed methods can be applied to analyze other kinds of wireless networks.