分组无线网分群后的隐藏终端问题分析

  一、 引言
  现代空军作为海陆空联合作战的重要组成部分,不仅要求战机装备多种先进电子设备,将各种功能高度综合,提高单机战斗和生存能力,还要求机群之间、飞机与地面部队、舰队以及地面指控中心在战时能迅速建立无线战术信息网络,保证各种军事信息高度共享和互通,提高整个作战体系的统一指挥和协同作战能力。这对于空中飞机组网提出了严格的要求。飞机机动性强,高速移动,通过机载电台联成空中移动通信网。这是一种分组无线网[1~3](PRN,即Packet Radio Network),与确定性连接网络比较,PRN网络具有2个显著特性:广播媒介和动态拓扑。广播媒介使节点能与其所有一跳节点直接通信,但为避免冲突必须限制同时发送的节点数;无线信道支持节点自由移动,但节点移动导致网络拓扑动态变化,从而带来很多新问题。因此,PRN网络必须建立稳健有效的网络管理方法,来解决冲突和动态拓扑问题。
  对于无线网络,隐藏终端[4~7]也是一个严重影响通信性能的问题。隐藏终端问题发生在相距两跳的2个节点同时发送报文的情况下,这时2个节点的公共接收节点处将产生冲突,导致网络吞吐量和延时性能急剧下降。文献[4]分析了无线局域网中隐藏终端的影响,提出了单信道下无线局域网的完整解决方案;文献[5]提出了一种新的基于FAMA (Floor AcquisitionMultiple Access)协议来分析PRN中的隐藏终端的方法。文献[6]提出一种基于捎带帧来解决VHF数据链中藏终端问题的方案;文献[7]对于CDMA体制下分组无线网隐藏终端问题开展研究,提出了一种基于RTS/CTS调度的多址方式来解决隐藏终端问题。对于采用分群算法分群后的PRN,隐藏终端问题更加错综复杂,对于此类问题尚未检索到相关研究文献。
  
  二、概述
  1基本定义和假设
  为论述方便首先介绍采用的几个定义和假设。
  (1)假设网络中各节点发射功率相同,不考虑功率控制,显然各节点通信覆盖半径相等,记为r。
  (2)k跳节点:考察节点i和j。若j在i的通信覆盖范围内,可直接接收i的报文和向i发报,则称j为i的一跳节点。显然i和j互为一跳节点。若i至少通过1个节点转发报文才能和j建立通信连接,称i和j互为两跳节点。依此类推,如果i和j至少通过(k-1)(k=2,3…)个节点转发报文才能建立通信连接,称i和j互为k跳节点。定义k跳节点之间相距跳数为k跳,记为H(i,j)=k,i≠j,并定义H(i,j)=0,i=j。
  (3)一跳邻节点集:对于节点i,其所有一跳节点的集合称为一跳邻节点集,记为N1(i),依次类推可定义i的k跳邻节点集Nk(i)(k=2,3,…)。
  (4)网络状态模型:PRN网络拓扑动态变化,但考察足够短的任一时间段,该时间段内各节点位移微小,这时可认为网络拓扑基本不变,呈现静止状态,称为瞬时静态。瞬时静态时,网络执行分群算法,节点进行分群管理和通信。瞬时静态会持续一段时间,直到网络拓扑变化量增大到一定程度,瞬时静态被完全打破,原有网络秩序彻底失效,网络进入短暂的混沌状态,然后迅速达到另一瞬时静态,网络重新分群,重建网络秩序。网络状态在瞬时静态和混沌状态之间不断交替,呈现一种动态平衡。本文基于以上网络状态模型,重点研究当PRN网络处于瞬时静态时的隐藏终端问题。一些未列出的定义和假设,将在叙述时给出。
  2.基于自组织分群算法的网络管理方法
  PRN的路由和管理是一个非常复杂的问题。若采用全分布算法,网络中每个节点都需维持一张全网拓扑的路由表来维护网络。路由表的长度随节点数线性增长,因此路由总开销随节点数呈平方增长。借鉴中心控制网络的思想,若只在少量主要节点维持路由表,这样既可充分发挥分布式网络的优点,又可大大减少路由总开销。但是单纯减少PRN网络中保存路由表的节点数并不能显著减少开销。由于PRN拓扑频繁变化,路由信息的更新开销占总开销的主要部分,因此应采取措施降低更新频率和每次的更新开销。
  一种有效的方法是将网络分成多个小区,各小区自组织管理,即由小区内所有节点对小区进行管理。这种小区称为分群(Cluster)或群,将网络划分为小区的算法称为分群算法[3,8,9]。
  当网络处于瞬时静态时,采用分群算法将网络划分为若干群,每个群自组织管理。只有当节点的位移导致大部分群严重失败时才使整个网络分群失败,从而导致瞬时静态失效。因此分群算法能有效适应节点的移动特性,群的生存能力强,抗毁性高,从而能够有效降低网络拓扑的更新频率。同时,当网络拓扑变化时,若少量维护路由表的节点只更新受影响的局部路由信息,在确保网络运行稳定的前提下又可大幅减少每次更新的开销。
  自组织分群算法规定分群后各群内节点通过约定方法选择一个”主控节点”,称为群首。群首负责群的初始化管理和路由管理等任务,群内节点在群首的协调下对群进行自组织管理。当网络拓扑变化时,群首只处理本群内节点进出群、链路失败等少量操作,更新少量局部路由变化信息。当群首失效(重新分群、群首故障等)时,群内节点探测到后快速重选群首,可立即恢复网络秩序。因此这种化整为零式的自组织网络管理方式具有优良的抗毁性和稳健性,充分体现了自组织的优点,还可节约大量更新开销。本文假设所研究的PRN网络也采用自组织分群算法进行网络管理。
  分群算法有多种,按群内有无群首,可分为带群首和无群首两类;按分群后群之间有无重叠区域,可分为重叠和不重叠两类。本文主要研究带群首、重叠的分群算法,并假设群内所有节点都在以群首为中心,以为半径的圆形区域内。
  3.隐藏终端问题
  隐藏终端问题如图1所示。图中R为接收终端,S1和S2为两个发送终端,S1和S2相距两跳。R同时处于S1和S2的通信覆盖范围内,当S1和S2同时向R发送报文时,造成R无法接收任何终端的报文,发生冲突,称S1和S2相对R互为隐藏终端。
  图1中H区(阴影区)称为S1相对R的隐藏终端区,区域内任何发送终端都是S1相对R的隐藏终端。S1向R发送报文时H区内任一终端同时发送都将产生冲突,因此隐藏终端的存在严重影响无线网络的通信性能。
  

 

  
  三、分群后隐藏终端问题分析
  1.群内隐藏终端问题分析
  群首是各节点的一跳节点,群内可能存在相距两跳的节点,因此可能存在隐藏终端问题。
  2.群内隐藏终端问题分析
  分群后群首在群的边缘节点中选择网关(网关选择算法见后),网关负责路由寻址和转发进出群的报文。群之间的通信只能由网关中转,因此不同群的节点不会直接冲突。
  图2中S1和S2分群前相对R互为隐藏终端,分群后S1和R属于群C1,S2属于群C2。S2只能通过网关节点g1与R间接通信,因此S1与S2相对R不再互为隐藏终端。但是S1和S2可能同时向g1发报,造成g1发生冲突,故S1和S2相对g1互为隐藏终端,隐藏终端问题转而出现在网关节点g1上。
  
 

  
  四、隐藏终端问题解决方案
  对于PRN网络,TDMA体制允许不同区域的多个节点同时发送而保证有效接收,并能大大减小冲突概率,高效复用带宽资源。为简化分析,本文拟在TDMA体制下开展分析。但TDMA规定必须有主控节点分配时隙,当主控节点失效时整个网络将陷入瘫痪,这显然不适用于空中飞机组网。
  自组织TDMA[10,11]是一种无主控节点的TDMA体制,所有节点都自行计算计划预约的空闲时隙,然后广播包含预约信息(预约的时隙、目标节点等)的时隙预约广播报。如未发生冲突则该节点预约成功,否则重新预约。以后该节点就可在预约的时隙里发报,在其他时隙里则监听信道并准备接收。因此自组织TDMA具有抗毁性高、生存能力强、支持分布式网络等优点。为此,下文将针对自组织TDMA体制的PRN网络开展研究。
  1.群内隐藏终端问题解决方案
  在自组织TDMA体制下,群内两跳节点如果在同一时隙发送报文则可能发生冲突。图3中S1和S2相距两跳,互为隐藏终端,为避免冲突必须禁止两者预约同一时隙。由于两者都无法直接知道对方时隙预约情况,因此需要中间节点(网格区中节点)仲裁。由于群首一定在网格区内,因此本文提出一种基于群首干预解决群内隐藏终端问题的方案。
  本方案规定群首接收群中所有节点的预约广播报,一旦发现如下预约冲突:2个一跳节点预约同一时隙;两跳节点预约同一时隙,且至少有一个接收节点位于通信覆盖的重叠区内(图3中网格区),则群首立即实施干预。群首(h)根据优先级或其他准则判决一个节点(S1)为优胜者,其他节点(S2)为失败者,然后群首给失败者发送一个预约失败报(RFP,即Reservation Failure Packet),失败者根据RFP中提示信息重新预约。因此本方案有效地消除了群内的预约冲突,从而解决了群内可能存在的隐藏终端问题。
  
 

  2群间隐藏终端问题解决方案
  由第三部分分析可知,群间隐藏终端问题只发生在网关节点上。由于网关的位置特殊性,以下展开详细分析。
  (1)网关选择算法和两种网关模型
  为简化分析,只对2个相邻群进行分析(多相邻群的情况类似分析)。根据两群是否重叠存在以下2种网关模型:
  1)两个群有重叠区域,且重叠区域内有节点:
  ①重叠区域有一个节点:该节点当然选作2个群的网关,例如图2中节点g1;
  ②重叠区域有多个节点:选择具有最多一跳节点的节点作为网关,其他节点可作为备用网关;
  2)2个群没有重叠区域或重叠区内无节点,但是2个群内必定至少各有一个节点相距一跳(否则2个群无法直接通信),则这2个节点组成网关节点对(GNP,即Gateway Node Pair),如图4中(g1,g2)组成一对GNP,记为G(g1,g2)。
  ①若只有一对GNP,当然选作网关;