Neighbor Discovery in Wireless Networks with Multipacket Reception
Neighbor Discovery in Wireless Networks with Multipacket Reception
复制标题
DOI：
10.1109/tpds.2014.2321157
复制
发表时间：
2015-07
影响因子：
5.3
通讯作者：
Alexander Russell;Sudarshan Vasudevan;B. Wang;Wei-ni Zeng;Xian Chen;Wei Wei-Wei
中科院分区：
文献类型：
--
作者：
Alexander Russell;Sudarshan Vasudevan;B. Wang;Wei-ni Zeng;Xian Chen;Wei Wei-Wei
邻居发现是配置和管理无线网络的第一步。现有的邻居发现研究大多采用单包接收模型，即一个接收端只能成功接收一个包。在本文中，受多包接收（MPR）技术（如CDMA和MIMO）日益普及的激励，我们研究了MPR网络中的邻居发现，该网络允许多个同时发送的数据包在一个接收器上成功接收。从n个节点的团开始，我们首先分析了一个简单的类似aloha的算法，并表明在允许多达k个同时传输时，以高概率发现所有邻居需要Θ（(n ln n)/k）时间。然后，我们设计了两种自适应邻居发现算法，动态调整每个节点的传输概率。我们表明，自适应算法对具有n个节点的团产生Θ（ln n）改进，因此是顺序最优的。最后，我们在一般的多跳网络环境下分析了我们的算法。当最大节点度为Δ时，Aloha-like算法的上界为O（（Δ ln n）/k），最多比最优算法差一个ln n因子。此外，当Δ较大时，我们证明自适应算法是有序最优的，即运行时间为O（Δ/k），与问题的下界匹配。
Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Θ((n ln n)/k) time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then design two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms yield a Θ(ln n) improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal. Finally, we analyze our algorithms in a general multi-hop network setting. We show an upper bound of O((Δ ln n)/k) for the Aloha-like algorithm when the maximum node degree is Δ, which is at most a factor ln n worse than the optimal. In addition, when Δ is large, we show that the adaptive algorithms are orderoptimal, i.e., have a running time of O(Δ/k) which matches the lower bound for the problem.