定向Ad Hoc网络隐藏与暴露终端问题的研究

摘　要：介绍基于定向天线的MAC协议，阐述使用定向天线所面临的隐藏终端、暴露终端以及聋结点问题。重点分析定向天线的MAC协议造成隐藏终端和暴露终端的原因以及解决这些问题相应的策略，在此基础上提出了新的改进CSMA协议。通过仿真表明，改进CSMA协议能提高基于定向天线Ad Hoc网路的整体性能。

关键词：Ad Hoc网路 定向天线 改进CSMA协议

引言
　　Ad Hoc 网络是一种特殊的无线移动网络。网络中所有节点的地位平等，无需设置任何的中心控制结点。网络中的结点不仅具有普通移动终端所需的功能，而且具有报文转发能力。与普通的移动网络和固定网络相比，它具有无中心、自组织、多跳路由、动态拓扑的特点。
　　Ad Hoc 网络的无线通道是多跳共享的多点信道。在Ad Hoc 网络中，可能会有多个无线设备同时接入信道，导致分组之间相互冲突，使接收端无法分辨出接收到的数据，导致信道资源浪费，吞吐量显著下降。为了解决这些问题，就需要MAC协议。所谓MAC协议，就是通过一组规则和过程来更有效、有序、和公平地使用共享媒体。因此MAC协议可以说是Ad Hoc?网络的关键技术之一。
1.无线MAC协议面临的关键问题
　　目前关于Ad Hoc 网络的研究重点大多为节点配备的是全向天线。
　　建议基于竞争的MAC协议：
　　（1）ALOHA协议：
　　ALOHA是最早提出的MAC接入协议，其工作原理是：所有结点均可以自由的通信，发起握手的结点不需要监听信道，结点直接用频率F0进行三次握手，发送方如果超过一定时限未收到应答，则认为发生了冲突，等待一定间隔后重试，直到重发成功为止。等待时间间隔是随机的，假定，各个结点通信是发送数据帧，发送数据帧所需时间是T，发送成功的条件是这个帧与该帧前后发送的两个帧到达的时间间隔均大于T。但是在这个时间内有其他帧传送，就可能产生冲突。ALOHA协议中没有考虑如何避免数据发送发生冲突，因此，发生冲突的几率较大。
　　（2）CSMA协议：
　　CSMA中，发起握手的结点用频率F0进行连接建立前首先需监听，确定是否听得到有其它结点用频率F0进行握手（由于采用定向天线的Ad Hoc网络天线波束的方向性，未听到并不意味着不存在冲突和隐终端问题），如果未监听到则以频率F0发送握手信息，否则等待一定间隔后重试；如果超过一定 时限未收到应答，则认为发生了冲突，等待一定间隔后重试。由于采用了信道监听，这样就避免了一定的发送冲突。
3.2“无冲突”的MAC协议
　　目前“无冲突”的MAC协议越来越受到学者们的青睐。但是基于结点轮询或令牌环的网络的时延性能较差，而且没有采用同频道复用技术，不利于多跳网络系统效率的提高；传统的FDMA或TDMA协议 不适用于相互之间信息位置未知的建网过程。
　　因此在采用定向天线的Ad Hoc网络中，为了克服这些不足，建网阶段的MAC协议采用预先分配应答时隙的动态STDMA协议。其特点是：
　　信道分时隙，时隙组成帧；结点必须粗同步，应答限制于时隙范围内；结点按照一个分布式、动态产生的时隙来接入信道；S指的空分复用，由于物理层使用定向天线。各结点的应答可在各自规定的时隙内实现并行操作，获取更好的复用度。总的来说，对于突然有大量握手操作的建网过程，动态时隙分配STDMA是更优的选择。
4.定向天线对MAC协议的影响（内容补充）
　　虽然采用定向天线的网络天线波束具有方向性，但其信号覆盖范围仍为一个椎体，有可能发生冲突与隐藏终端问题。
　　1.纯ALOHA协议
　　结点用频率F0发出握手请求，若没有先验扫描方向信息，则全向扫描，若有先验扫描方向信息，则其波束覆盖范围为自身为顶点、α为半顶角的锥形区域，信号作用距离取决与距离和功控算法的精度。如图4.1所示。

　　图4 .1 ALOHA协议中冲突与隐藏终端
　　假设V6正与V7定向通信，没有收到V5和V2间的握手信息。当V6向V2发送RTS，由于V2正与V5通信，从而在V2处发生冲突，当V2向V5发送全向CTS时，由于V1在V2全向发送范围之外，收不到V2的全向CTS。如果V1在V5和V2通信期间向V2发送定向RTS，则在V2处发生冲突。V6和V1即为V2的隐藏终端。
　　协议
　　结点首先需监听信道，确定是否听得到有其它结点用频率F0进行握手，若无则用频率F0发出握手请求，否则等待一定间隔后重试。若没有先验扫描方向信息，则全向扫描，若有先验扫描方向信息，则其波束覆盖范围为以自身为顶点、α为半顶角的锥形区域，信号作用距离取决与距离和功控算法的精度。参与握手的结点用频率F0进行连接建立前首先监听的机制能够避免部分可能产生的冲突与隐藏终端问题，但由于波束信号覆盖范围为一个半顶角为α的椎体，任何结点必然存在监听盲区，冲突与隐终端问题仍可能存在。监听机制部分解决了冲突与隐终端问题，但也带来了暴露终端问题，如图4.2所示。

　　图4.2  CSMA协议的暴露终端现象
　　假设首先由V1用频率F0向V2发出握手请求，该握手请求信号既能被结点V2收到也能被结点V4收到，如果此时V4需要建立至V3的连接，依据CSMA协议，V4不能以频率F0发起与V3握手过程。事实上由于V1没有位于V4为结点、V4V3间连线为轴、α为半顶角的锥形区域，不会产生F0频率冲突，V4“可说但不能说”，形成暴露终端现象。
　　3.改进的CSMA协议（）
　　基于CSMA协议的讨论，CSMA协议未充分利用定向天线网络的天线信号方向性特征解决频率冲突和隐终端现象，可能会形成严重的暴露终端现象。我们提出改进的CSMA协议，进一步解决暴露终端现象。改进规则（）如下：
　　（1）空闲结点记录△t时间内监听到的最后一次（或前两次）用频率F0进行握手的结点，比如结点V0，称为可能冲突结点。
　　（2）任何结点用频率F0发出握手信息时（请求、应答及确认），首先解算自身的可能冲突结点是否会落入波束信号的椎体内。若是，则退避，否则用频率F0发出握手信息。协议规定仅在可能冲突结点确实发生冲突时退避。如图4.3所示。
　　
　　图4.3 改进CSMA协议暴露终端解决方案
　　假设结点V1首先用频率F0向V2发起握手请求，该握手请求信号同时被结点V4收到，因此在△t时间内结点V1成为结点V4的可能冲突结点。如果在△t时间内结点V4需要建立至V5的连接，V1落入以V4为顶点、V4V5间连线为轴、α为半顶角的锥形区域，此时可能冲突结点V1成为V4的必然冲突结点，V4必须退避；如果在△t时间内结点V4需要建立至V3的连接，V1没有位于以V4为顶点、V4V3间连线为轴、α为半顶角的锥形区域，此时可能冲突结点V1不是V4的必然冲突结点，V4完全可以用频率F0向V3发出握手信号。
　　改进CSMA协议较好解决了频率冲突、隐藏终端和暴露终端现象。但增加了协议复杂性和结点工作负担：
　　（1）空闲结点必须记录△t时间内监听到的最近一次（或前两次）用频率F0进行握手的结点信息，即可能冲突结点的信息，增加了结点需存储信息量，但信息仅属于结点局部信息而非全局信息，未增加需要全网广播的信息量。
（2）结点以频率表F0发送握手信息前要解算可能冲突结点是否为必然冲突结点，加重了结点运算负担。
5.三种协议性能的理论分析
　　分析MAC协议的性能，一般用吞吐量S和网络流量G两个参数来衡量。吞吐量S：在帧的发送时间T内成功发送的平均帧数；网络流量G：在T内总共发送的平均帧数（包括发送成功的帧和因冲突未发送的帧）。
　　它们之间的关系为：
　　  
而：
　　  
假设网络中结点的数量很大，数据包发送成功概率服从泊松分布，即，为平均帧的发送率，。
所以有：
　　  
　　在纯ALOHA协议中，吞吐量，当G=0.5时，S有极大值，S≈0.184。
　　在CSMA协议中，吞吐量，为信道延迟；若忽略信道延迟时，则，当G=1时，网络的吞吐量达到最大S≈0.538。
　　在改进CSMA协议中，引入了“可能冲突点”和“必然冲突点”两个概念，只有当一个结点是另一结点的“必然冲突点”时，则必须退避。
　　在解算“可能冲突点”与“必然冲突点”中，各结点相同频率的天线波束为顶角是的近似椎体。则：
　　  
　　可知结点有效传输半径为。则，表示在半径内平均结点数，为单位面积内平均结点数。表示一个结点在一个时隙内平均成功传输的分组数，其中是定向天线波束的顶角。
　　根据结点成功发送需要同时满足的3个条件：本结点发送且成功，其次至少在本结点传输区域内有一个结点。则：
　　  
　　在想定和的情况下，使最大的值为
　　  
6.仿真结果及分析
　　采用OPNET仿真软件进行仿真分析[8][10]，ALOHA、CSMA和改进CSMA是应用于定向天线信道网络中的接入协议，为了仿真定向天线信道，建立起基于Ad Hoc通信的网络模型。将网络模型设定为由5个结点， 2个发射结点，3个接收结点组成。发射结点以指数时间间隙发送数据包，接收结点接收未发生冲突的数据包， 并在仿真结束后，通过网络吞吐量以及信道利用率统计量记录下仿真的结果。分析仿真数据，比较ALOHA、CSMA、改进CSMA协议在网络负载、吞吐量、冲突概率等方面的性能差异。
　　由于ALOHA协议发起通信的结点不需要监听信道，发送结点如果超过一定时限未收到应答，则认为发生了冲突，等待一定间隔重试，直到发送成功为止。没有采取任何冲突避免的策略，而CSMA协议和改进CSMA协议采用了信道监听和引入判断冲突点机制来避免冲突，所以从表6.1可以看出改进CSMA协议和CSMA协议与ALOHA协议相比每秒冲突数目明显减少，延时明显降低。
表6.1 三种协议各性能平均值比较

　　利用归一化的吞吐量S和网络负载G作吞吐量特性图. Internetwork Research Department BBN Technologies,2002.