单跳广播控制波束指向方法
技术领域
本发明涉及一种适用于定向网络的快速单跳广播控制波束指向的方法。
背景技术
天线对空间不同方向具有不同的辐射或接收能力，这就是天线的方向性。根据方向性的不同，无线网络采用的通信天线一般分为全向天线与定向天线两大类。全向天线指的是无方向性，在方向图上表现为全范围均匀辐射。定向天线指的具有方向性，在方向图上表现为一定角度范围内辐射。相比于全向天线，定向天线具有增益高、传输距离远、速率高、抗干扰性能好等诸多优点，在无线通信网络中的应用越来越广泛。
定向网络是所有网络节点均采用定向天线相互进行通信的无线网络。图5所示的典型的定向网络，如网络包含A、B、C、D、E、F六个节点，每个节点配置可向任意方向赋形特定宽度通信波束的定向天线，波束宽度为，如图6所示。节点是随机均匀分布在场地上,定向天线没有相互对准的节点之间不能参与信息传递，只有通信双方均在对方的通信波束覆盖范围之内时，才可以实现稳定可靠的定向通信。
广播传输是最常见的一种传播方式，分为全网广播与单跳广播。全网广播指的是广播节点发送消息时，需要传输至所有的网络其它节点；根据网络拓扑的不同，可能需要中继节点转发多次，才可能实现全网广播。而单跳广播指的是广播节点发送消息时，需要传输至单跳覆盖范围内的所有网络其它节点，单跳广播不需要任何节点的中继就可以完成。全网广播与单跳广播的示意图如图7所示。
单跳广播通常是紧急警告消息传播的基本机制，广泛应用于车联网等分布式无线局域网中。单跳广播是分发车用安全信息的基本方法，车载环境下的单跳信息广播机制是保证车辆行驶中人员安全的关键。周期性的信标消息广播能够帮助车辆节点相互感知,使得车辆节点间相互协作。此外,突发性的紧急消息和安全单跳广播能够帮助故障车辆有效地提醒周围邻居节点,从而避免发生更加严重的二次事故。然而,车联网单跳广播存在着严重的可靠性问题,难以保证邻居节点都能成功接收到广播节点所广播的MAC帧。首先,传统的广播机制中接收到广播帧的所有邻居节点不会返回ACK确认帧,因而广播节点不可能多次重传丢失的帧；其次,由于面向缓解隐藏终端问题的RTS/CTS机制也不适用于广播,因此广播节点不能够预约无线信道,广播帧很可能会被隐藏节点所干扰；最后,由于帧不能多次重传,传统的最小竞争窗口也将不能动态指数地自适应增长,因此造成竞争窗口随机取值较小,使得信道拥塞环境下的碰撞概率较高。
全向网络由于采用全向天线，辐射无方向性，广播节点只需要发送一次，周围的邻居节点就可以全部收到，正因为全向天线的开放性，节点的广播容易造成相互冲突，全向网络的单跳广播的难点在于如何提高广播的可靠性。通常的做法根据广播节点对实时接收的数据帧进行统计分析,从邻居节点中选择一个合适的节点作为虚拟目的节点,然后广播节点将与这个虚拟目的节点进行单播传输,同时其他邻居节点仍然将单播帧视作传统的广播帧接收。这种机制使得广播传输能够利用单播中的RTS/CTS、ACK、重传和竞争窗口调整等多种修复和自适应机制,有效地提高了单跳广播的可靠性。由于定向天线辐射的方向性，广播节点的每次发送，仅能使位于天线辐射方向覆盖区域内的邻居节点接收到，而覆盖范围外的邻居需要调整波束指向再次发送才可能接收到。因此，全向网络的单跳广播方法完全不适用于定向网络，相比全向网络，定向网络的单跳广播变得非常复杂。定向网络的单跳广播的核心在于波束指向的控制，如何控制广播节点定向天线的辐射方向，使广播节点的信息能够及时、高效、可靠地传递到所有周围邻居节点，是定向网络单跳广播中面临的难题。
现有的主要技术方案有：邻居节点遍历的方式和多波束并行发送的方式。邻居节点遍历的方式针对每个邻居节点进行分时传输，即先将一跳范围内的所有邻居进行排列，依次调用单个波束资源对每个邻居节点进行发送同一条广播消息，直到所有邻居节点均接收到该广播消息为止。该方式实现简单，单波束就可以操作，网络扩展性好，缺点是每个邻居均需要顺序发送一次，广播效率较低，广播时延较大，假定单次发送时间为t秒，对于N个邻居节点，则需要N*t秒才能广播完毕，这对于时效性要求较高的广播消息是无法忍受的。邻居节点遍历的方式对网络拓扑要求高，只适合节点稀疏且分布均匀的定向组网场景，对于节点数目较多且分布不均匀的定向组网场景，在某个方向上聚集多个网络节点，该方式会造成在某个方向上重复发送多次数据包，一方面大量发送重复数据包浪费了通信带宽，另一方面大量重复包的接收容易造成邻居节点接收过程的拥塞。
多波束并行发送的方式采用多个定向波束，针对每个邻居赋形一个定向波束，所有波束分同时指向所有邻居节点，广播节点通过所有波束一次并行发送同一条广播消息，所有邻居节点全部接收到。该方式实现单跳广播非常快捷，但这种转发机制，需要耗费非常多的天线或波束资源，软硬件代价非常大，并且在并行发送过程中，往往多个波束需要均分广播节点的功率资源，分摊到单个波束的功率大幅减小，而且各波束之间通常存在相互干扰，邻居节点的接收信噪比明显降低，从而很大程度降低了单跳广播的可靠性。由于天线或波束资源非常有限，该方式只适合于节点数很少的小型网络，而对于密集型的定向网络，邻居节点数较多时，对于N个邻居节点，则需要N个定向波束资源需要的波束资源均无法承受。另外，由于受硬件限制，节点的波束资源受限，该方式下的网络扩展性差，不具备网络拓扑适应能力。
综上所述，现有的技术方案要么依靠软硬件资源堆砌，要么依靠延长时间来进行定向网络的单跳广播，具有各自的局限性，无法满足大型密集定向网络中快速可靠的广播需求。
发明内容
本发明的目的是针对现有技术存在的不足之处，提供一种广播效率高，广播时延低，能够提供更可靠的单跳广播通信性能，适用于定向网络的快速单跳广播控制波束指向的方法。
本发明的上述目的可以通过以下措施来得到，一种单跳广播控制波束指向方法，具有如下技术特征：在定向网络中，广播节点通过GPS获得自身及各邻居节点的地理位置信息，在快速广播中采用单波束发送数据，通知所有邻居节点设置波束指向并尝试接收，所有其余节点调度波束资源指向广播节点接收数据；然后，广播节点利用所有的地理位置信息，计算广播发送所需要的波束指向集合，计算出所有两两链路之间的夹角，创建逻辑图G，并找出逻辑图G中的最大完全子图计算波束指向，用最大完全子图确定此次波束指向Pi；在单次波束赋形发送过程中，根据波束指向集合逐一发送广播消息，直到波束集合中所有的波束指向处理完毕。
从上述技术方案可以看出，本发明提出的适用于定向网络的快速广播控制方法，相比于现有技术，具有如下有益效果。
具有最低的软硬件资源需求，单跳广播可靠。本发明在定向网络中，广播节点通过GPS与邻居交互等手段，获得的自身的地理位置信息，收集所有邻居节点的地理位置信息，并在快速广播中采用单波束进行发送，同一时刻仅在某单个波束方向上发送数据；这种在快速广播中采用单波束进行发送，同一时刻仅在某单个波束方向上发送数据的单跳广播机制和基于节点分团的单跳广播波束控制机制，以比较多波束多天线的并行发送方式，具有最低的软硬件资源需求，很明显地降低了波束、天线通道、功率等资源，大大增加了网络的可扩展性，很好地适应密集型大型网络，并且采用单波束发送可以利用广播节点的全部功率资源提高接收信噪比，且不存在多波束并发的相互干扰，大幅提高了单跳广播的可靠性；
广播效率高，广播时延低。本发明广播节点通过GPS与邻居交互等手段，收集所有邻居节点的地理位置信息，根据广播节点获得的自身及邻居节点的地理位置信息，广播节点通知所有邻居节点设置波束指向尝试接收，计算广播发送需要的波束指向集合，计算出以广播节点为中心的所有链路两两之间的夹角，根据链路夹角创建逻辑图G，并找出逻辑图G中的最大完全子图，基于完全子图的节点分团的方法计算波束指向，用最大完全子图确定此次波束指向Pi，具有较高的广播效率与较低的广播时延；广播节点在单次波束赋形发送过程中，覆盖尽可能多的邻居节点，排除波束指向Pi覆盖的所有邻居节点，并将这些节点对应的链路在逻辑图G对应的顶点删除，更新逻辑图G，不是针对每个邻居节点单独波束赋形发送，而是利用基于完全子图的节点分团的方法计算波束指向，在单次波束赋形发送过程中，覆盖尽可能多的邻居节点，避免了对聚集在一团的邻居节点的多次发送，从而大大降低了广播发送次数，提高了广播效率，有效降低了广播时延。一般情况下，本发明的广播发送次数仅为邻居节点遍历方式下的1/3左右，即广播效率提高3倍左右。
拓扑适应能力强。本发明广播节点首先通过GPS获得自身地理位置信息，通过邻居交互获得各邻居节点的地理位置信息。其次，广播节点通知所有邻居节点设置波束指向，让它们的通信波束均指向广播节点并尝试接收。然后，广播节点利用所有的地理位置信息，计算广播发送所需要的波束指向集合。将节点对应的链路在逻辑图G对应的顶点删除，更新逻辑图G，重复操作，直至逻辑图G为空，广播节点当逻辑图G为空时，输出所有的波束指向集合{Pi}，最后，广播节点根据波束指向集合并按照波束指向集合，逐一发送广播消息。逐一进行波束赋形，当该波束上发送完毕后，再切换至下一个波束进行赋形并发送广播消息，直到波束集合中所有的波束指向处理完毕。使得广播传输能够适应任意网络拓扑，网络节点可以任意分布，无论是稀疏网络还是密集网络，无论是节点均匀分布网络还是分布不均匀网络，均可采用本发明的波束指向控制方法，全面提供高效的单跳广播通信能力。
附图说明
图1是本发明单跳广播控制波束指向的总体流程图；
图2是波束指向计算的坐标定义示意图；
图3是本发明广播节点计算广播发送需要的波束指向处理流程图；
图4是本发明广播节点根据波束指向集合逐一发送广播消息的处理流程图；
图5是典型的定向网络构成示意图；
图6是图5节点采用定向天线赋形通信波束示意图；
图7是图5单跳广播与全网广播的示意图。
具体实施方式
参见图1。根据本发明，一种单跳广播控制波束指向的方法，具有如下技术特征：在定向网络中，在定向网络中，广播节点通过GPS获得自身及各邻居节点的地理位置信息，在快速广播中采用单波束发送数据，通知所有邻居节点设置波束指向并尝试接收，所有其余节点调度波束资源指向广播节点接收数据；然后，广播节点利用所有的地理位置信息，计算广播发送所需要的波束指向集合，计算出所有两两链路之间的夹角，创建逻辑图G，并找出逻辑图G中的最大完全子图计算波束指向，用最大完全子图确定此次波束指向Pi；在单次波束赋形发送过程中，根据波束指向集合逐一发送广播消息，直到波束集合中所有的波束指向处理完毕。
广播节点在单次波束赋形发送过程中，覆盖尽可能多的邻居节点，排除波束指向P覆盖的所有邻居节点，并将这些节点对应的链路在逻辑图G对应的顶点删除，更新逻辑图G，重复操作，直至逻辑图G为空，当逻辑图G为空时，输出所有的波束指向集合{P}，并按照波束指向集合逐一进行波束赋形并发送广播消息，当该波束上发送完毕后，再切换至下一个波束进行赋形并发送广播消息，直到波束集合中所有的波束指向处理完毕。
参见图2。以广播节点位置为坐标原点(0,0,0)，原点所在的水平面作为xy平面的右手XYZ坐标系，在XYZ坐标系中用表示每个邻居节点的坐标，用(xpoint,ypoint,zpoint)表示波束指向矢量，建立计算波束指向矢量的三维直角坐标系。
参见图3。图中给出了广播节点计算广播发送需要的波束指向处理流程；广播节点计算广播发送需要的波束指向包括如下步骤：
步骤201，本节点根据广播节点的地理位置与所有邻居节点的地理位置，计算所有以广播节点为本端、邻居节点为对端的链路两两之间的夹角，然后转入步骤202创建逻辑图G初始化循环控制变量i＝1；
步骤202，广播节点按照以下方法创建逻辑图G，并初始化循环控制变量＝1，然后转入步骤203获得逻辑图G的最大完全子图的顶点集合Si；
广播节点将所有一跳邻居节点建模作为G中的顶点，然后遍历所有以广播节点为本端、一跳邻居节点为对端的链路，若某两条链路的夹角小于波束宽度γ，则将逻辑图G中该两条链路对端节点对应的两个顶点相连构成边，遍历完毕后得到逻辑图G；
步骤203，广播节点利用图论学中的最大完全子图求解算法，获得逻辑图G的最大完全子图的顶点集合Si，并将其顶点集合抽取出来作为Si，记录初始顶点集合S'i＝Si，然后转入步骤204确定顶点集合Si对应的波束指向矢量Pi；
步骤204，广播节点按照以下方法确定顶点集合Si对应的波束指向矢量Pi，然后转入步骤205删除顶点集合Si中未被波束指向矢量Pi覆盖的顶点；首先，广播节点计算集合Si中所有顶点对应的邻居节点与广播节点之间的距离d，并令其最大值为dmax，构造以广播节点为球心、dmax为半径的球体Sph，然后，针对顶点集合Si中每个顶点对应的邻居节点j，计算广播节点到该邻居节点j的射线与球体Sph的交点的坐标(xj，yj，zj)，令
步骤205，广播节点检查顶点集合Si中的每个顶点，若广播节点与该顶点对应的邻居节点之间的连线与波束指向Pi之间的夹角大于γ/2，则认为该顶点无法被波束指向矢量Pi覆盖，直接将该顶点从顶点集合Si中剔除，然后转入步骤206判断顶点集合Si是否为空；
步骤206，若广播节点判定顶点集合Si为空，则转入步骤207获取未剔除前的初始顶点集合S'i，重新生成顶点集合Si的子集，否则转入步骤208在逻辑图G中删除顶点集合Si中的顶点及相关联的边；
步骤207，广播节点按照以下方法获取未剔除前的初始顶点集合S'i的子集，作为新的顶点.集合Si：令集合XL＝{(x,y,z)∈S'i|x≤xpoint}，集合XR＝{(x,y,z)∈S'i|x＞xpoint}，若集合XL的元素数目不小于集合XR的元素数目，则Si＝XL，否则Si＝XR，然后转回步骤204重新确定顶点集合Si对应的波束指向矢量Pi；其中，XL和XR各表示1个集合，L和R无特殊含义，仅作为下标来区分两个集合；
步骤208，广播节点在逻辑图G中删除集合Si中的顶点及所有相关联的边，形成新的逻辑图G，然后转入步骤209判断逻辑图G的顶点集合是否为空；
步骤209，若为空则转入步骤211输出所有波束指向的集合P＝{P1,…，Pi，...}，否则转入步骤210更新循环控制变量i＝i+1。
步骤210，广播节点更新循环控制变量i＝i+1，然后转回步骤203获得逻辑图G的最大完全子图的顶点集合Si；
步骤211，广播节点输出所有波束指向的集合P＝{P1,…，Pi，...}。
参见图4。图中给出了广播节点根据波束指向集合逐一发送广播消息的处理流程。
步骤301，广播节点从波束指向集合P中移除一个指向Pi，然后转入步骤302设置定向天线的波束指向为Pi；
步骤302，广播节点设置定向天线的波束指向为Pi，然后转入步骤303发送广播消息。
步骤303，广播节点采用定向天线在Pi方向上发送广播消息，发送完毕后转入步骤304判断波束指向集合P是否为空；
步骤304，广播节点判断波束指向集合P是否为空，若为空则直接结束，否则转回步骤301从波束指向集合P中移除一个指向，直至结束。
以上所述为本发明较佳实施例，应该注意的是上述实施例对本发明进行说明，然而本发明并不局限于此，并且本领域技术人员在脱离所附权利要求的范围情况下可设计出替换实施例。对于本领域内的普通技术人员而言，在不脱离本发明的精神和实质的情况下，可以做出各种变型和改进，这些变型和改进也视为本发明的保护范围。
