摘要:针对使用定向天线的无线网络邻居发现问题，为提高邻居发现效率，提出了一种忙音辅助算法。通过全向发送序列化忙音预约信道，有效缓解了无线网络通信过程中普遍存在的数据冲突问题和空闲问题，提高了信道的利用率。根据感知的忙音方向调整定向天线的波束指向，有效解决了基于定向天线的无线网络中波束方向的协调问题，提高了通信效率。实验结果表明，相对传统算法及基于反馈机制的邻居发现算法，忙音辅助算法具有更高的邻居发现效率。
关键词:无线网络；定向天线；邻居发现；忙音；信道竞争
中图分类号: TP393.04 文献标志码:A
Algorithms of neighbor discovery in wireless networks with directional antennas
LIU Zhen*, LI Ying
School of Computer Science and Technology, Soochow University, Suzhou Jiangsu 215006, ChinaAbstract:
To improve the efficiency of neighbor discovery in wireless networks with directional antennas, a busy-tone aided algorithm was proposed. With the help of omni-directional busy-tones, the problems of collision and idleness in wireless communication were effectively relieved, as a result, the channel utilization ratio was increased. The direction of antenna beam was adjusted according to the Direction of Arrival (DOA) of busy-tones. Through this strategy, communication efficiency was improved. Numerical results show that, compared with the conventional Aloha-like algorithm and a latest improved algorithm, the proposed algorithm has a better performance.
To improve the efficiency of neighbor discovery in wireless networks with directional antennas, a busy.tone aided algorithm was proposed. With the help of omni.directional busy.tones, the problems of collision and idleness in wireless communication were effectively resolved; as a result, the channel utilization ratio was increased. The direction of antenna beam was adjusted according to the Direction of Arrival (DOA) of busy.tones. Through this strategy, communication efficiency was improved. The experimental results show that, compared with the conventional ALOHA.like algorithm and the neighbor discovery algorithm based on the feedback mechanism, the proposed algorithm has a better performance.Key words:
wireless network; directional antenna; neighbor discovery; busy.tone; channel competition
0引言
邻居发现是无线网络初始化过程中的关键步骤之一，有效的邻居发现算法对于大部分基于无线网络的MAC协议［1］、路由算法［2］和拓扑控制算法［3］是必不可少的。邻居发现效率的高低直接影响着网络的性能。邻居发现算法可以分为随机性邻居发现算法［4-7］和确定性邻居发现算法［8］两大类。当前国内外对于邻居发现的研究多集中于全向天线模式，对于基于定向天线的邻居发现算法的研究相对较少。文献［4］基于ALOHA协议提出了随机性邻居发现算法，文献［5］在此基础上进一步提出了应用于定向天线的邻居发现算法，但二者都仅通过调整发送概率提高发现信息成功发送的概率，未能有效解决冲突和空闲问题。文献［6-7］提出了具有反馈机制的邻居发现算法，节点可以通过邻居节点的反馈信息获知发现信息是否被正确接收，可以避免发现信息的重复发送。但基于反馈机制的邻居发现算法很难应用于多跳网络模式下，亦不能解决使用定向天线的无线网络邻居发现问题。文献［8］提出了一种确定性邻居算法，即节点按照既定的收发顺序发送和接收发现信息，对于分布式的无线网络，确定性算法难以实施。
针对基于定向天线的无线网络，本文提出一种忙音辅助邻居发现算法，能够同时缓解冲突和空闲问题，并且可以有效协调定向天线的波束方向。主要的工作内容包括：
1)归纳影响邻居发现效率的主要问题并提出解决方法;
2)提出能够同时实现冲突避免和降低空闲时隙出现概率的忙音辅助的信道竞争机制;
3)针对基于定向天线的静态无线网络提出忙音辅助邻居发现算法;
4)通过分析和实验验证忙音辅助邻居发现算法的可行性和效率;
5)验证忙音辅助邻居发现算法适用于基于全向天线的无线网络。
1模型和条件假设
1.1网络模型
假定无线网络是静态自组织网络。为方便分析讨论，假定每一个节点都位于其他任何节点的单跳通信范围之内。在本文最后将提出一种针对多跳无线网络邻居发现问题的解决方案。
1.2天线模型
每个节点配备一个具有波束切换机制的定向天线，假定每个节点的波束宽度相同。每个节点拥有一个独立的忙音收发装置，能够全向发送和检测忙音。在一个时刻，一个节点只有一个波束处于活动状态。节点通过处于活动状态的波束进行数据的定向的发送或接收，但不能同时发送和接收。假定忙音的全向干扰距离和定向天线的有效通信距离相同。天线的各个扇区的相对位置保持不变，这个功能通过简单指向设备可以实现。
1.3条件假设
1)独立的ID。每个节点拥有一个独立的标识符，例如MAC地址。
2)同步。假定时间被分成相等的时隙，每个时隙由多个子时隙组成。每个时隙的长度和一次发现信息发送时间相同。网络的邻居发现过程与时间帧同步。一个时间帧定义 为节点完成一次成功发送需要的时隙个数。
3)冲突。如果一个节点在某一个时刻从两个以上的节点接收邻居发现信息，则视为冲突产生。
4)邻居节点数目。本文假定节点可以预先估算出自己的邻居节点的数目。
5)物理信道传输不会产生错误，传播时延忽略不计。
2算法设计
2.1基于ALOHA协议的邻居发现算法
针对使用定向天线的无线网络，文献［5］提出了基于ALOHA协议的邻居发现算法。在每个时隙的开始，节点以概率pt定向发送发现信息，即自己的标识信息，以概率1－pt进行定向接收。在每个时隙，节点的波束方向是随机的。在一个时隙中，节点i发现节点j的概率为:
pi,j=θ24π2 pt(1－θ24π2 pt)n－2(1－pt)其中：θ是波束宽度，n是网络节点个数。
随机性邻居发现的方式有三方面的问题制约邻居发现的效率。首先，在同一个时隙内发送节点和接收节点需要将波束方向彼此指向对方，这是成功发送发现信息的基本前提。假定网络中只有i和j两个位于彼此通信范围内的节点，在一个时隙内节点i发现节点j的概率为:
pi,j=θ24π2 pt(1－pt)
假定波束宽度为θ=π/2，当pt=1/2时，在这个时隙内，节点i接收到节点j的发现信息概率最大为pi,j=1/64，随着波束宽度的减小，在同一个时隙内，节点i和节点j波束方向指向对方的概率θ24π2减小，pi,j也随之减小。第4期
刘桢等：基于定向天线的无线网络邻居发现算法
计算机应用 第32卷
随机性邻居发现算法中存在另一个重要问题，即赠券收集问题［6］：在邻居发现过程结束之前，发送节点发送信息后，由于冲突的可能性，不能确保邻居节点成功接收。需要重复地发送发现信息，在指定时间内以较大概率保证发现信息被所有邻居节点所接收。赠券收集问题降低了邻居发现算法的效率。解决此问题也是提高邻居发现效率的一个有效途径。
第三个制约邻居发现效率的问题是空闲时隙和冲突，这将导致信道利用率的下降。由于节点基于概率随机地进行邻居信息的发送和接收，可能在某个时隙内所有的节点均处于接收状态，这样就产生了空闲时隙。还有一种可能是在一个时隙内，同时有多个节点发送发现信息，这会在接收节点引起冲突。文献［4］指出，在全向天线模式下，当pt=1/n的时候，邻居发现的效率最高。在这种情况下，当n→+∞时，在一个时隙中，成功发送邻居信息的概率为:
ps=npt(1－pt)n－1=1�e(1)
与此同时，空闲时隙的概率:
pidle=(1－pt)n=(1－1�n)n=1�e (2)
由式(1)、(2)易知在这个时隙中由于多个节点同时发送信息而产生冲突的概率:
pc=1－pidle－ps=1－2�e(3)
空闲和冲突问题的存在降低了信道的利用率，从而制约
了邻居发现的效率。有效地解决这两个问题，可以提高邻居发现的效率。上述假设前提是n→+∞，容易证明n比较小的情况下，空闲和冲突问题同样在很大程度上制约着邻居发现的效率。
对于使用定向天线的无线网络，传统的邻居发现算法效率很低,可以通过解决以上三个问题来提高邻居发现的效率。2.2基于忙音的邻居发现算法
忙音是一种有着某个特定单频的正弦信号，可以是通过能量检测的方法来识别，不需要编码和解码。节点通过忙音竞争信道，通知邻居节点进入接收状态并且调整波束方向指向发送节点，并通过忙音序列来筛选出能够发送发现信息的节点。
2.2.1算法描述
忙音辅助邻居发现算法包含两个阶段。第一阶段，包含一个时隙，称为竞争时隙(Competition Slot, CS)。在这个时隙中节点通过发送忙音竞争信道。第二阶段，包含的时隙个数和扇区的个数相同，称为信息发送时隙(Message Slot, MS)竞争到信道的节点在每个时隙扫描一个扇区，发送发现信息。每个节点维持两个本地变量s和t，初始化为0。其中s用于记录发送节点已扫描的扇区个数，t用来记录已经接收到的邻居信息数目。显然，s的最大值等于扇区总数2π/θ，用S表示。一个时间帧包含一个竞争时隙和S个信息发送时隙。
第一阶段在竞争时隙，节点以概率pt全向发送忙音进行信道预约。为了最大限度地降低空闲时隙出现的概率，引入了参数η(η∈(0，n))。令每个节点以概率pt=η/n进行信道的竞争，根据式(2)，相对较小的η可以使空闲概率得到有效降低。易知pidle=(1－pt)n≈e－η。当η≥7的时候，空闲时隙出现的概率将小于0.001。通过上述方法选择合适的常数η，能有效地降低空闲时隙出现的概率。然而这种方法会增加冲突概率。为了在降低空闲时隙概率的同时避免冲突，可以采取这样一种机制：把竞争时隙分成m个子时隙，在每个时间帧的开始阶段，竞争信道的节点随机生成长度为m的二进制序列，每个序列值对应一个子时隙。在竞争时隙中，根据生成的二进制序列，当二进制值等于1时，对应的子时隙全向发送忙音，否则进行忙音检测。如果在一个子时隙中，节点检测到忙音，则在余下的子时隙中不再按照二进制序列的值进行发送，它将转换为接收节点，一直处于监听状态直到整个竞争时隙的结束。每个接收节点根据在竞争时隙中最后一次接收到忙音的方位切换自己的波束指向对应的方向，进入邻居发现的第二个阶段。如图1所示，在竞争时隙中，如果有节点i(二进制序列：01111)和节点j(二进制序列：10100)同时竞争信道。节点i随机选择了子时隙2、3、4、5，节点j选择了子时隙1、3来发送忙音。在第一个时隙内，i检测到忙音，表明有其他节点竞争信道，i此时转换为接收节点，取消接下来的忙音的发送，保持监听状态直到竞争时隙的结束。这样节点j抢占到信道。在竞争时隙结束后，节点i和所有其他接收节点，根据最后一次接收到的忙音的方位（下文将证明其唯一性），把波束切换到对应方向，准备进行发现信息的接收。
忙音不必充塞整个子时隙，可以在子时隙中发送单脉冲。在仅有两个节点同时竞争信道的情况下，只有两个节点随机生成的二进制序列完全相同才会发生冲突。通过这种机制，节点冲突的概率可以有效降低。假如在一个时隙内有r个节点竞争信道，产生相同二进制序列的概率:
p(m,r)=1－2m(2m－1)…(2m－(r－1))2rm=
1－2m!2rm(2m－r)!(4)二进制序列的数量随m的增长呈指数增长，随着m的增大，式(4)快速趋近于0。 选择m=16，当r=7时，式(4)约等于0.0003。对于多于两个节点同时竞争信道的情况，产生冲突的条件可描述为：将二进制序列按数值大小排列，只有两个或以上节点的二进制序列具有最大数值时才能产生冲突。容易证明实际冲突的概率为:
pc∈(p(m,r)r－1,p(m,r))其中两个以上节点产生相同序列的概率相对较低，因此实际冲突概率pc≈p(m,r)r－1。再者由于节点发送概率pt=η/n，根据中心极限定理：
p(r>η+Δ)=1－Φ(η+Δ－nptnpt(1－pt))(5)其中Δ=0,1,2,3,…。在竞争时隙中，竞争信道的节点数的期望值为η，当Δ=0时，式(5)的值为0.5，随着Δ的值增大，式(5)快速趋近于0。因此在每个时隙中竞争信道的节点数有限，并且趋近于η。综上所述，选择合适的m值，冲突的概率可以忽略。
第二阶段即信息发送阶段。当网络中的一个节点j成功竞争到信道，从一个随机方向开始，逐个扇区发送发现信息，当发送结束以后，节点在接下来的邻居发现过程中处于接收状态，不再竞争信道。通过这种方式，可以解决因赠券收集问题而引起的邻居信息的重复发送。处于接收状态的节点每接收到一个邻居信息后把t的值加1，每经过一个时隙，s的值加1，如果接收到邻居发现信息后，s的值小于扇区数目S，则在余下的S-s个时隙中，节点可以处于休眠状态以节省能量。在一次发现信息发送和接收过程完成以后，s的值清零。由于每次成功的邻居发现以后发送节点退出信道的竞争，因此在接下来的空闲时隙中，如果n－t>η,那么未退出信道竞争的节点以η/(n－t)的概率竞争信道；否则，以概率1竞争信道。2.2.2算法验证
本节验证忙音辅助算法的有效性，将忙音辅助邻居发现算法和传统的基于ALOHA协议的邻居发现算法作对比，通过Matlab 7.0进行仿真测试。在实验中，设定η=7，m=16。规定每个节点维持一个邻居信息表，发现信息的内容包括：发送节点标识和发送波束编号。如图2所示的三个节点的情况，以4个扇区的定向天线为例。在邻居发现过程结束后，i节点的邻居信息表如表1所示。
3相关讨论
3.1未知邻居节点数目情况
在忙音辅助算法中，可以根据网络规模选取适当的参数m，可以将忙音发送扩充到多个时隙内，保证足够多的子时隙达到冲突避免。每个节点以概率1竞争信道，这样发送概率不依赖于邻居节点数目，可以实现在未知邻居数目情况下的邻居发现过程。
3.2多跳场景扩展
在多跳场景下，隐终端问题制约网络性能。如图6所示，实线表示节点发现信息的通信范围。当A向B发送数据的时候，C可能同时向B发送，这样在B处就产生了冲突。在使用定向天线的情况下，当A和C同时竞争到信道，如果根据忙音辅助发现算法，节点B的波束指向A，那么B收不到节点C的信息。