SCI论文（www.lunwensci.com）:
摘 要：由于邻居发现是移动自组网的常规工作，对路由和组网具有基础支撑作用，且由于能耗的限制，移动自组网必须 以低功耗的方式实现邻居发现工作，因此邻居发现一直是学术界研究的热点问题。本文通过研究大量关于邻居发现的研究论文 分析了邻居发现协议的分类。目前主流的邻居发现协议是基于全向天线的单信道邻居发现算法，包括单信道概率性邻居发现算 法、单信道确定性邻居发现算法。此外也有基于定向天线的单信道邻居发现算法等。
关键词：Ad Hoc；邻居发现；邻居发现协议
Research on Neighbor Discovery Protocol Algorithm Status and Types in Ad Hoc Network
GAO Fei, ZHAO Na
（Beijing Polytechnic, Beijing 100176）
【Abstract】： Because neighbor discovery is a routine work of mobile Ad Hoc networks, it provides basic support for routing and networking. Moreover, due to the limitation of energy consumption, mobile Ad Hoc networks must realize neighbor discovery with low power consumption. Therefore, neighbor discovery has always been a hot issue in academic research.This paper analyzes the classification of neighbor discovery protocols by studying a large number of research papers on neighbor discovery. At present, the mainstream neighbor discovery protocols are single-channel neighbor discovery algorithms based on omnidirectional antenna, including single-channel probabilistic neighbor discovery algorithm and single-channel deterministic neighbor discovery algorithm. In addition, there are also single-channel neighbor discovery algorithms based on directional antennas.
【Key words】： Ad Hoc;neighbor discovery;neighbor discovery protocol
0 引言
邻居发现是 Ad Hoc 移动自组网的常规工作，对路 由和组网具有基础支撑作用，且由于能耗的限制，移动 自组网必须以低功耗的方式实现邻居发现工作，因此邻 居发现一直是学术界研究的热点问题。截至目前，研究 者们主要研究了基于全向天线的单信道邻居发现算法， 包括单信道概率性邻居发现算法、单信道确定性邻居发现算法。虽然也有基于定向天线的单信道邻居发现算法 方面的研究，但研究者们基本都沿袭了全向天线的研究 思路， 未有突破性思维， 所获性能提升有限。另外， 为 了解决邻居发现中的冲突问题，从而缩短邻居发现时延，也有少量关于多信道邻居发现算法的研究论文。但 多信道的引入又增加了邻居发现的难度，因为在单信道 场景中只需要苏醒时隙重叠，而多信道场景中除了要求 苏醒时隙重叠，还要求两个节点处于同一信道才能保证发现。
1 基于全向天线的单信道邻居发现算法
1.1 算法分类和特点
基于全向天线的单信道邻居发现算法有分为两类： 分别是基于全向天线的单信道概率性邻居发现算法和基 于全向天线的单信道确定性邻居发现算法。
基于全向天线的单信道概率性邻居发现算法只能以一定的概率 ( 或比例 ) 实现两个物理邻居节点之间的相 互发现，它的主要缺点是不能给出两个物理邻居节点间 的发现延时的上限。主要包括基于生日悖论的 Birthday Protocols 算法 [1] 及其衍生算法 [2] ，和基于素数集合的 概率性算法 [3] 等。这类算法研究的核心问题是： 如何 进一步减少平均发现延时，如何减少发现延时拖尾。最 早的概率性邻居发现算法 Birthday Protocols 按照占 空比的要求，随机设置节点在每个时隙的苏醒或睡眠状态，实现了较高的邻居发现比例，但由于节点苏醒和睡 眠设置的随意性注定了其发现延时具有较长的拖尾。而 基于素数集合的概率性邻居发现算法首先依据占空比要 求构建一个素数集合，节点工作时随机从素数集合中选 择一个素数作为自己的工作周期 ( 即在该素数工作周期 的首个时隙苏醒，其余时隙睡眠 )，并工作确定个工作 周期。这就既获得了基于中国剩余定理 [4] 的确定性优 势，同时又利用了随机选择素数的概率性优势，取得了 更好的平均发现延时，同时拖尾还很小。该算法是目前 效果最好的概率性邻居发现算法。
基于全向天线的单信道确定性邻居发现算法能够保 证在给定时限内百分之百实现两个物理邻居节点之间的 相互发现。它们的主要优点是能够给出两个物理邻居 之间的发现延时的上限，主要包括： 基于 Quorum 的 Grid[5]、Block Design[6]、Cqs-Pair 和 Gqs-Pair[7] 等算 法、基于中国剩余定理的 Disco 算法 [8] 和混合型算法 U-connect、Searchlight、C-Torus[9]、Non-Integer 算法 [10] 等。确定性邻居发现算法通过两物理邻居节点 之间在给定时限内必有重叠或部分重叠的苏醒时隙来确 保发现延时的上限，它研究的核心问题是：在能量有限 情况下，如何尽可能缩短发现延时的上限，缩短平均发 现延时，并设计占空比和发现延时可以在很宽范围内变 化的邻居发现方法。目前取得最好性能的确定性邻居发 现算法 Non-Integer 算法。先前的算法是基于等时隙 的，即所有时隙无论是苏醒时隙还是休眠时隙都要求等 大小，这一类型的算法在 Non-Integer 算法中统称为 Integer 策 略。Non-Integer 算 法 提 出 将 任 何 Integer 策略转化为 Non-Integer 算法的方法。Non-Integer 算 法 由 于 可 将 Nostriped Searchlight 算 法（Nostriped Searchlight 算 法 仍 属 于 Integer 策 略） 转 化 为 Non- Integer 策略， 从而比以往最好的 Striped Searchlight 提升性能大约 40.5%。
1.2 主要缺点
基于全向天线的单信道邻居发现算法，包括单信道概率性邻居发现算法、单信道确定性邻居发现算法，都 存在两个主要缺点：（1）一旦该通信信道环境不理想， 将严重影响网络的可靠性；（2）对于移动场景，由于邻 居关系动态变化，邻居发现工作变成了常规工作，在邻 居发现和数据传输任务较重或节点较密集时，常常因冲 突频发导致邻居发现延迟明显增大。因此，移动自组网 使用多信道进行邻居发现和通信越来越成为一种趋势。
2 基于全向天线的多信道邻居发现算法
近年来，多信道邻居发现算法研究已经取得了一 些成果，比如： 基于彩票收集理论和泛洪方式的算法， EasiND 算法和 McDisc 算法等。基于彩票收集理论和 泛洪方式的算法将邻居划分为多个组，组内节点随机选 择一个信道工作，当到达某一期望时间 ( 这一时间根据 彩票收集理论得出 )，就认为组内节点间已经相互发现； 组内节点相互发现后，每个组选出一个 Leader，然后进 行组间发现，组间发现时，所有 Leader 工作于同一信 道，组间发现后，每个 Leader 向组内节点广播自己的 信息以完成最终的相互发现。该研究有利于各信道的充 分利用，但由于它属于概率性邻居发现算法，其发现延 迟有长尾。EasiND 也是基于分组的多信道邻居发现算 法，但其分组算法实现复杂，开销较大，且性能提升有 限。McDisc 是基于中间件的多信道邻居发现算法，它利 用中间件获得时钟同步， 然后让每个节点都依据全局时钟 设置自己的工作信道，确保了任意两个物理邻居节点在有 重叠苏醒时隙时必定工作在同一信道， 从而实现邻居发现 且发现延迟保持与单信道模式一致。但该方法要求所有节 点同步，在邻居发现前取得网络上所有节点间的同步非 常艰难，或者至少其开销很难承受，因此实用性不足。
另外，所有多信道串行邻居发现算法都存在其他两 个共同缺点：（1）它们都旨在解决数据包冲突问题和通 信质量不可靠的问题，但引入多信道后由于发现难度的 增大而增加的发现延时是否能够抵消引入多信道后由于 冲突减少而减少的发现延时？关于这两者之间如何寻求 平衡的系统的定量理论分析的研究未见报道；（2）尚未 发现对多信道并行邻居发现理论机制的探索，包括没有 推导出多信道邻居发现算法中发现延迟与能量消耗乘 积的理论最优值。上述这些缺陷说明现有多信道邻居发现研究工作还不够深入。因此，课题组认为依然缺乏比 较深入的多信道邻居发现机制研究，尤其是理论层面的研究。
3 基于定向天线的邻居发现算法
定向天线就是将发射能量集中起来向特定方向发射的天线。它能提高信噪比，有利于提高通信质量。定向 天线在无线传感网中的应用越来越多。但是定向天线的 引入却增加了邻居发现的难度，原因在于：基于定向天 线的邻居发现算法由于节点定向天线的水平辐射主瓣宽 度不足以覆盖 360 度水平方向，故它有可能需要在不 同方向上重复执行以覆盖所有方位。为了应对这样的挑 战，研究者们主要提出了三类基于定向天线的邻居发现 算法，包括：第一类是利用全向天线来辅助进行邻居发现，这增加了额外开销；第二类需要时间同步，但众所 周知，在分布式无线网络中，尤其在邻居发现前，要获 得时间同步是非常艰难的，这类算法实用性不足； 第 三类是随机算法，即每个节点随机选择不同方向发送 “Hello”包，然后再随机选择一个方向进行侦听，这 类方案虽然比较简单，但存在发现延迟有较长拖尾的问 题。上述算法未能充分利用好定向天线的辐射范围更宽 的优势，而且它们并未注意到定向天线还具有天然的单 向连接性这一特点。
4 研究发展动态分析
虽然基于全向天线的邻居发现算法 ( 包括概率性邻 居发现算法、确定性邻居发现算法和合作邻居发现算 法 ) 研究取得了很大的进展。但依然需要努力提高其性 能，当前，该方向的研究发展动态主要包括。
（1）在能量有限情况下，如何进一步降低单信道确 定性邻居发现的最差发现延时，并提高占空比配置的灵 活性；
（2）在能量有限情况下，如何进一步降低单信道概 率性邻居发现的平均发现延时；
（3）在能量有限情况下，如何进一步挖掘单信道合 作邻居发现在组内和组间合作方面的潜力。
此外，使用定向天线除能够增大天线增益、减少干 扰、提高信噪比，从而有效提高数据传输速率和稳定性 外，还可在相同辐射能量情况下，获得比采用全向天线 更大的信号辐射范围。换句话说，在辐射范围相同的条 件下，定向天线比全向天线消耗更少的能量。并且注 意，由于辐射范围与能量消耗成二次方的关系，并非线 性关系，这样可以大幅提高能效。当前，在定向天线研 究方面，尚未发现结合定向天线的单向连接特性和辐射范围更宽的特点，研究如何发现更多的邻居、进一步缩 短邻居发现延时、提高邻居发现能效的报道。
参考文献
[1] McGlynn M J,Borbash S A.Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[C].In:Proc.of the 2nd ACM Intl Symp.on Mobile Ad Hoc Networking & Computing (MobiHoc).Long Beach:ACM Press,2001:137-145.
[ 2 ] Borbash S A,Ephremides A,McGlynn M J.An asynchronous neighbor discovery algorithm for wireless
sensornetworks[J].In:Ad Hoc Networks,2007,5(7):998-1016. [3] Chen LY,Li YC,Chen YR,Liu K,Zhang JY,Cheng YH,You HY,and Luo Qian.Prime-set-based Neighbor Discovery Algorithm for Low Duty-cycle Dynamic WSNs[C].In: ELECTRONICS LETTERS,19th March 2015,51(6).
[4] Niven I M,Zuckerman H S,Montgomery H L.An introduction to the theory of numbers[M].New York: John Wiley & Sons Inc.,1991.
[5] Tseng Y C,Hsu C S,Hsieh T Y.Power-saving protocols for IEEE 802.11-based multi-hop ad hoc networks[C]. In:Proc.of the 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM).New York: IEEE CS Press,2002(1):200-209.
[6] Zheng R,Hou J C,Sha L.Asynchronous wakeup for ad hoc networks[C].In:Proc.of the 4th ACM Intl Symp.on Mobile AD Hoc Networking & Computing (MobiHoc). Annapolis:ACM Press,2003:35-45.
[7] Lai S,Ravindran B,Cho H.Heterogenous quorum-based wake-up scheduling in wireless sensor networks[J].IEEE Trans.on Computers(TC),2010,59(11):1562-1575.
[8] Dutta P,Culler D.Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications [C].In:Proc. of the 6th ACM Conf.on Embedded Network Sensor Systems(SenSys).Raleigh:ACM Press,2008:71-84.
[9] 陈良银,颜秉姝,张靖宇,等.移动低占空比传感网邻居发现算 法研究[J].软件学报,2014,25(6):1352-1368.
[10] Sxia Chen,Alexander Russell,Ruofan Jin,Yanyuan Qin,BingWang,and Sudarshan Vasudevan.Asynchronous neighbor discovery on duty-cycled mobile devices:Integer and non-integer schedules[C].MobiHoc15 Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing,2015:47-56.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/34711.html
