基于概率优化的定向自组织网络邻节点发现方法

摘要

本发明提出了一种基于概率优化的定向自组织网络邻节点发现方法，用于解决现有技术中存在的邻节点发现效率低的技术问题，实现步骤为：设置节点的波束选择概率向量；修改各波束方向的波束选择概率值；修改各波束方向执行邻节点查找的次数以及发送信息和接收信息的时隙长度比值；选择执行邻节点查找的波束方向；选择邻节点查找模式；根据接收到的信息更新邻节点表和查找到的邻节点数量。本发明根据节点每个周期在各波束方向查找到的邻节点数量指导下一周期在各波束方向的邻节点发现的执行，通过优化各波束方向执行邻节点发现的波束选择概率，并修改各波束方向的执行次数和发送信息和接收信息的时隙长度，提高了邻节点发现效率。

说明书

技术领域

本发明属于无线通信技术领域，涉及一种无线自组织网络邻节点的快速发现方法，具体涉及一种基于概率优化的定向自组织网络邻节点发现方法，可用于纯定向无线网络的数据链路层和网络层通信协议设计。

背景技术

无线自组织网络是一个能够动态组网的多跳对等网络，可以不利用任何网络基础设施实现节点间的相互通信，无线自组织网络的终端设备形式多样，可以是普通用户电脑、笔记本电脑、智能手机、平板电脑等等，在探险救灾、军事通信、海上通信、实时信息传输等方面有着广泛的应用。定向天线通过将能量集中在理想的方向，可以提供长传输距离、降低时延、提高空间复用，同时降低网络中节点间的干扰，在各种无线网络中应用极为广泛。通过在无线自组织网络中使用定向天线进行信息传输，能够利用定向天线的优势，提高网络容量，增强网络的传输性能，但是无线自组织网络中的节点在通信之前，需要首先执行邻节点发现，这就需要快速准确的邻节点发现方法。

目前，对定向天线的无线自组织网络邻节点发现的研究，主要分为两种：带有全向天线辅助的定向邻节点发现和不带全向天线辅助的纯定向邻节点发现。

带有全向天线辅助的定向邻节点发现可以快速的实现邻节点发现，高效的进行信息传输，但其要求增加全向天线，其天线设备复杂，不方便携带，不符合无线自组织网络移动方便组织方便的特点。

不带全向天线辅助的纯定向邻节点发现，天线结构简单，方便携带，目前的研究更多集中在纯定向信息传输的方面。例如，上海交通大学的研究团队在论文＂Neighbordiscovery algorithms in wireless networks using directional antennas＂(published in Communications(ICC),2012 IEEE International Conference on,vol.,no.,pp.767-772,10-15 June 2012)中提出的I-SBA算法，是一种应用于小规模网络的不带全向天线辅助的纯定向邻节点发现方法。该算法针对邻节点发现过程中的冲突和空闲问题进行研究，通过增加一个Idle状态大大降低冲突概率。该算法在执行时，节点在每个邻节点发现执行周期之前，以一定概率从传输、接收、Idle这三个状态中选择一个状态首先执行，处于Idle状态的节点在相应方向的传输和接收过程中都处于休眠，既不接收信息也不传输信息，以降低接收节点接收hello信息的冲突。这种方式能在一定程度上提高查找效率。但这种方法只是简单地随时间变化扫描各方向进行邻节点发现，没有利用节点在邻节点发现过程中产生的已经发现的邻节点个数和剩余未发现邻节点个数等数据信息，所以对于降低邻节点发现时间的效果不很明显。

再如，Mir,Z.H等人在论文"Continuous Neighbor Discovery Protocol inWireless Ad Hoc Networks with Sectored-Antennas,"(published in AdvancedInformation Networking and Applications(AINA),2015 IEEE 29th InternationalConference on,Gwangiu,2015,pp.54-61.)中提出NDSA算法，是一种采用事件驱动节点执行的不带全向天线辅助的纯定向邻节点发现。该方法在执行时，根据信道信息和查找到的邻节点的反馈信息，改变节点在邻节点发现过程中处于发送状态、接收状态、IDLE状态的持续时间，从而提高邻节点发现的收敛速度。但是该方法的反馈信息只针对整个空间方向发现的邻节点数量，没有深入节点每个方向的邻节点数量信息，反馈不全面，所以不能有效的降低节点完成邻节点发现的时间。

发明内容

本发明的目的在于克服上述现有技术存在的不足，提出了一种基于概率优化的定向自组织网络邻节点发现方法，通过为定向自组织网络的各节点的各波束方向设置波束选择概率，并在执行邻节点发现的过程中不断调整该波束选择概率，旨在改变各波束方向被选择执行邻节点查找的概率，用于解决现有定向自组织网络中不带全向天线辅助的定向邻节点发现方法存在的效率低的技术问题。

本发明的技术思路是：对于定向自组织网络中的每个节点，在其执行邻节点发现之前，先检测节点在各波束方向已经发现的邻节点数量，根据检测结果调整各波束方向的波束选择概率值；根据调整后的各波束方向的波束选择概率值修改各波束方向执行邻节点发现的次数以及各波束方向发送信息和接收信息的时隙长度；每个节点根据调整后的各波束方向的波束选择概率值选择相应的波束方向执行邻节点查找。

根据上述技术思路，实现本发明目的采取的技术方案，通过如下步骤实现：

步骤1：向定向自组织网络中的每个节点导入网络节点数量N、网络范围S和定向天线的波束角度θ，其中，N≥2，θ∈(0°，180°]；

步骤2：每个节点根据定向天线的波束角度θ计算定向天线的波束个数k，同时根据网络节点数量N和网络范围S，计算每个节点在各波束方向上可能的邻节点数量n₀；

步骤3：每个节点对其在各波束方向的邻节点表和查找到的邻节点数量n进行初始化，且n＝0，同时利用可能的邻节点数量n₀将每个节点在各波束方向上执行邻节点查找的时隙数设置为2·n₀；

步骤4：每个节点判断各波束方向查找到的邻节点数量n是否全部等于0，若是，则执行步骤5，否则执行步骤6；

步骤5：每个节点设置波束选择概率向量P中各元素的值为0，其中P＝[p_i,0,p_i,1,…,p_i,j,…,p_i,k-1]，i为节点号，k为定向天线的波束个数，p_i,j为节点i的第j个波束方向被选择执行邻节点查找的波束选择概率，同时每个节点利用rand函数产生k个(0.5,0.8)的随机数，并利用这些随机数对各波束选择概率p_i,j的值进行初始化，其中0.5为波束选择概率p_i,j的最小门限值p_min；

步骤6：每个节点根据其各波束方向上查找到的邻节点数量n，对波束选择概率向量P中的各波束选择概率值进行调整，得到优化的波束选择概率值，按如下步骤实现：

步骤6a：判断任一波束方向上邻节点数量n和该波束方向上可能的邻节点数量n₀是否满足n≥n₀，若是，则将该波束方向的波束选择概率值调整为0.5，并执行步骤7，否则执行步骤6b；

步骤6b：判断该波束方向上邻节点数量n是否满足n＝0，且该波束方向的波束选择概率值是否等于1，若是，则将该波束方向的波束选择概率值调整为0.5，并执行步骤7，否则执行步骤6c；

步骤6c：将该波束方向的波束选择概率值增加0.1，得到新的波束选择概率值，且增大后的波束选择概率值不超过1；

步骤7：每个节点判断步骤6调整后的波束选择概率向量P中的各波束选择概率值是否全都等于p_min，若是，执行步骤12；否则执行步骤8；

步骤8：每个节点根据步骤6调整后的波束选择概率向量P，设置其在各波束方向执行邻节点查找的次数向量M和各波束方向发送时隙与接收时隙的比值向量ψ，其中M＝[m₀,m₁,…,m_j,…,m_k-1]，j为每个节点的第j个波束方向，k为定向天线的波束个数，m_j为每个节点的第j个波束方向被选择执行邻节点查找的次数，为每个节点的第j个波束方向执行邻节点查找时发送时隙和接收时隙的比值；

步骤9：每个节点根据步骤6调整后的波束选择概率向量P的值，选择一个波束方向执行邻节点查找，其中查找的次数为该节点的次数向量M中该波束方向的数值m_j；

步骤10：每个节点在其所选择的波束方向上随机选择一种邻节点查找模式，其中邻节点查找模式为：

查找模式1：每个节点首先在其所选择的波束方向上的个时隙发送hello信息，再在个时隙接收hello信息，并执行步骤11；

查找模式2：每个节点首先在其所选择的波束方向上的个时隙接收hello信息，再在个时隙发送hello信息，并执行步骤11；

步骤11：每个节点根据其所选择的波束方向上接收到的hello信息，对各波束方向的邻节点表和查找到的邻节点数量n进行更新，并执行步骤4；

步骤12：每个节点完成本次邻节点发现过程。

本发明与现有技术相比，具有如下优点：

第一，本发明由于在每个节点选择执行邻节点查找的波束方向时，增加了设置波束选择概率向量的步骤，并根据各波束方向查找到的邻节点数量调整各波束方向的波束选择概率值，避免选择不必要执行邻节点查找的波束方向，降低了邻节点发现时间，与现有技术采用的各节点随机选择波束方向执行邻节点查找的方法相比，有效地提高了邻节点的发现效率。

第二，本发明由于每个节点在其所选择的波束方向执行邻节点查找时，根据该波束方向的波束选择概率值，修改节点在该波束方向执行邻节点查找的次数，改变了各周期执行邻节点查找的总时隙长度，节点间的异步特性更加明显，减少了信息冲突的概率，同时，修改节点当前周期在各方向执行邻节点查找时发送hello信息和接收hello信息的时隙长度，进一步减少了信息冲突的概率，降低了邻节点发现的时间，与现有技术采用的节点在每个邻节点发现周期执行固定的邻节点查找时隙长度和在固定的时隙长度发送和接收hello信息的方法相比，进一步提高了邻节点的发现效率。

附图说明

图1是本发明的实现流程框图；

图2是本发明的帧结构示意图；

图3是本发明的时隙变化示意图。

具体实施方式

以下结合附图和具体实施例，对本发明的目的、技术方案和技术效果作进一步详细描述。

参照图1：

步骤1：向定向自组织网络中的每个节点导入网络节点数量N、网络范围S和定向天线的波束角度θ，其中，N≥2，θ∈{30°,45°,60°,90°,120°}。

步骤2：每个节点根据定向天线的波束角度θ计算定向天线的波束个数k，同时根据网络节点数量N和网络范围S，计算每个节点在各波束方向上可能的邻节点数量n₀。

此处利用步骤1中向无线自组织网络中的每个节点输入的波束角度θ值，计算出每个节点的波束个数k。计算方法为：

同时利用N和S计算各波束方向上可能的邻节点数量n₀。计算方法为：

其中，节点通信范围是定向自组织网络中节点的通信属性，表示节点能够传输信息的范围。

步骤3：每个节点对其在各波束方向的邻节点表和查找到的邻节点数量n进行初始化，且n＝0，同时利用邻节点数量n₀将每个节点在各波束方向上执行邻节点查找的时隙数设置为2·n₀。

每个节点将各波束方向的邻节点表初始化为0，表示在开始执行邻节点发现时，节点在各波束方向没有发现任何邻节点。每个节点将其各波束方向上可执行邻节点发现的时隙个数设置为2·n₀，表示节点在各波束方向执行邻节点查找的时隙个数与本波束方向可能的邻节点数量相关，等于n₀的两倍。

步骤4：每个节点判断各波束方向查找到的邻节点数量n是否全部等于0，若是，则执行步骤5，否则执行步骤6。

节点在每个波束方向查找到的邻节点数量全部等于0，说明节点第一次执行邻节点查找，故执行步骤5进行设置波束选择概率向量。

步骤5：每个节点设置波束选择概率向量P中各元素的值为0，其中P＝[p_i,0,p_i,1,…,p_i,j,…,p_i,k-1]，i为节点号，k为定向天线的波束个数，p_i,j为节点i的第j个波束方向被选择执行邻节点查找的波束选择概率，同时每个节点利用rand函数产生k个(0.5,0.8)的随机数，并利用这些随机数对各波束选择概率p_i,j的值进行初始化，其中0.5为波束选择概率p_i,j的最小门限值p_min。

本方法使用波束选择概率向量P＝[p_i,0,p_i,1,…,p_i,j,…,p_i,k-1]表示节点在各波束方向执行邻节点查找的概率，概率值p_i,j越大则节点i选择波束方向j执行邻节点查找的可能性越大。设置概率值p_i,j的范围在0.5到0.8之间，能够保证每次执行邻节点查找时都有相应的波束方向被选择执行邻节点发现。

步骤6：每个节点根据其各波束方向上查找到的邻节点数量n，对波束选择概率向量P中的各波束选择概率值进行调整，得到优化的波束选择概率值，按如下步骤实现：

步骤6a：判断任一波束方向上邻节点数量n和该波束方向上可能的邻节点数量n₀是否满足n≥n₀，若是，则将该波束方向的波束选择概率值调整为0.5，并执行步骤7，否则执行步骤6b。

某一波束方向已查找到的邻节点数量大于等于可能的邻节点数量，说明节点已经发现了该波束方向上所有的邻节点，则设置本周期的邻节点发现过程不再在该波束方向执行，可以节约邻节点发现时间。

步骤6b：判断该波束方向上邻节点数量n是否满足n＝0，且该波束方向的波束选择概率值是否等于1，若是，则将该波束方向的波束选择概率值调整为0.5，并执行步骤7，否则执行步骤6c。

某一波束方向已查找到的邻节点数量等于0且其对应的波束选择概率值已经等于最大值1，则说明在实际网络中该波束方向上可能不存在邻节点，所以设置该波束方向的波束选择概率值等于0.5，使得本周期的邻节点发现过程不再在该波束方向执行，能够节约邻节点发现时间。

步骤6c：将该波束方向的波束选择概率值增加0.1，得到新的波束选择概率值，且增加后的波束选择概率值不超过1。

某波束方向的波束选择概率值没有达到最大值，且该波束方向上已查找到的邻节点数量没有达到n₀，则本周期的邻节点发现过程需继续在该波束方向执行，以便在该波束方向发现更多的邻节点。

步骤7：每个节点判断步骤6调整后的波束选择概率向量P中的各波束选择概率值是否全都等于p_min，若是，执行步骤12，否则执行步骤8。

p_min表示节点的一个波束方向能够被选择执行邻节点查找的最小值，根据网络规模和通信需求设置为0.5。当某波束方向的波束选择概率值等于p_min时，节点认为该方向的邻节点已经被全部查找到或者该方向没有邻节点，则节点不再选择该波束方向执行邻节点查找。当所有波束方向的波束选择概率值都等于p_min时，表示节点查找到所有邻节点，完成邻节点发现过程。

步骤8：每个节点根据步骤6调整后的波束选择概率向量P，设置其在各波束方向执行邻节点查找的次数向量M和各波束方向发送时隙与接收时隙的比值向量ψ，其中M＝[m₀,m₁,…,m_j,…,m_k-1]，j为每个节点的第j个波束方向，k为定向天线的波束个数，m_j为每个节点的第j个波束方向被选择执行邻节点查找的次数，为每个节点的第j个波束方向执行邻节点查找时发送时隙和接收时隙的比值。

定向自组织网络中的每个节点根据波束选择概率向量中各波束方向的波束选择概率值，设定相应波束方向执行邻节点查找的次数值和该波束方向发送时隙与接收时隙的比值，即，根据p_i,j设定m_j和的值。

设定方式为：当p_i,j＝0.5时，设置m_j＝0，表示节点本周期在该波束方向不执行邻节点查找；当0.5<p_i,j≤0.7时，设置m_j＝1，表示节点本周期在该波束方向执行一次邻节点查找，且该波束方向上发送时隙和接收时隙数相同；当0.7<p_i,j≤0.85时，设置m_j＝2，表示节点本周期在该波束方向执行两次邻节点查找，且该波束方向上接收时隙的长度是发送时隙长度的两倍，这样做能够保证节点在更多的时隙上接收hello信息，以便更快的发现邻节点；当0.85<p_i,j≤1时，设置m_j＝1，当波束选择概率值增大到0.85时，说明在前面的周期中该波束方向已经执行过一定次数的邻节点查找，所以设置节点本周期在该波束方向只执行一次邻节点查找，同时设置该波束方向上接收时隙的长度是发送时隙长度的两倍，保证节点在更多的时隙上接收hello信息，减少了hello信息的冲突，以便更快的发现邻节点。

步骤9：每个节点根据步骤6调整后的波束选择概率向量P的值，选择一个波束方向执行邻节点查找，其中查找的次数为该节点的次数向量M中该波束方向的数值m_j。

节点根据波束选择概率向量中各波束方向的波束选择概率值选择一个波束方向执行查找邻节点的过程，并在该方向查找m_j次。

步骤10：每个节点在其所选择的波束方向上随机选择一种邻节点查找模式，其中邻节点查找模式为：

查找模式1：每个节点首先在其所选择的波束方向上的个时隙发送hello信息，再在个时隙接收hello信息，并执行步骤11。

查找模式2：每个节点首先在其所选择的波束方向上的个时隙接收hello信息，再在个时隙发送hello信息，并执行步骤11。

设置两种查找模式能够减少hello信息的冲突，增加了节点间执行邻节点查找的异步特性。

步骤11：每个节点根据其所选择的波束方向上接收到的hello信息，对各波束方向的邻节点表和查找到的邻节点数量n进行更新，并执行步骤4。

节点接收到hello信息后，根据hello信息中的内容，记录相应的邻节点的ID号和波束方向号等信息，同时将查找到的邻节点数量加1。

步骤12：每个节点完成本次邻节点发现过程。

参照图2：

图2描述的是每个节点执行邻节点发现过程的帧结构示意图。

参照图3：

图3(a)描述的是每个节点在各波束方向发送hello信息和接收hello信息的时隙比例变化示意图。

图3(b)描述的是每个节点各周期执行邻节点发现的总时隙长度变化示意图。

本发明说明书中未详细描述的内容属本领域技术人员的公知技术。基于本发明思想的修正和改变仍在本发明的权利要求保护范围之内。