基于协同素数的非对称低轮值周期邻居发现方法

摘要

本发明公开一种基于协同素数的非对称低轮值周期邻居发现方法，其包括如下步骤：根据移动节点的能量需求和时延要求选择相应的轮值周期。根据所述轮值周期，选择不同参数安排锚时隙、探针时隙和素数时隙的位置，建立邻居发现调度表。移动节点根据所述邻居发现调度表，完成邻居发现。本发明使用单个协作的素数，保证在有界的发现时延内完成快速的异步邻居发现，并且增加了可选轮值周期的数量，能量分配更加灵活。在非对称低轮值周期情况下，不仅能够保证移动节点较低的能量开销，而且减小了最坏发现时延。

说明书

技术领域

本发明涉及移动社交网络技术领域，尤其涉及一种基于协同素数的非对称 低轮值周期邻居发现方法。

背景技术

近年来，移动传感器和智能手机等移动设备在各个方面得到了广泛而深入 的应用。大多数基于应用的移动设备有机会互相遇见彼此。例如，两个移动设 备偶然相遇，进而互相通信；某个移动设备需要进入一个已经建立的群组和多 个移动设备形成一个群组的场景。在这些应用场景中，都需要移动设备快速发 现处于自己通信范围内的邻居用户。

在新兴的物联网和移动社交网络中，移动设备完成邻居发现主要面临三个 方面的挑战。一、移动设备的能量受到限制。为了延长持续工作的时间，移动 设备需要在极低的轮值周期下运行，异构的硬件平台也需要非对称的轮值周期 （即不同的轮值周期）。二、移动设备的工作不同步，在低轮值周期的网络中将 导致更大的发现时延。三、大部分运行在移动设备上的应用对时延非常敏感， 在邻居发现过程中要求更小的发现时延。

针对异步非对称的邻居发现问题，之前的研究提出了几个解决方法，例如 Disco、U-Connect以及Searchlight协议。Disco协议选取一对素数，轮值周 期为两个素数的倒数之和，如果节点时隙计数器的值能被任一素数整除，此时 隙就为活跃时隙，活跃时隙的交迭可以完成邻居发现；U-Connect协议只选择一 个素数p，每隔p-1个时隙为一个活跃时隙，同时每p²个时隙中有(p+1)/2个活 跃时隙；而Searchlight协议利用任意两个节点活跃时隙之间的常偏移，相比 Disco和U-Connect协议，在对称轮值周期情况下减小了约50%最坏发现时延。， 上述三种协议在应对能量效率和发现时延带来的挑战上显示了其优越性，但是， 在非对称低轮值周期的情况下，性能相对较差。

发明内容

针对上述技术问题，本发明的目的在于提供一种基于协同素数的非对称低 轮值周期邻居发现方法，其可以在极低的能量开销下保证有界且较小的发现时 延，从而完成低功耗的邻居发现。

为达此目的，本发明采用以下技术方案：

一种基于协同素数的非对称低轮值周期邻居发现方法，其包括如下步骤：

A、根据移动节点的能量需求和时延要求选择相应的轮值周期；

B、根据所述轮值周期，选择不同参数安排锚时隙、探针时隙和素数时隙的 位置，建立邻居发现调度表；

C、移动节点根据所述邻居发现调度表，完成邻居发现。

特别地，所述步骤B还包括：

采用基于时分机制的周期性睡眠调度方法，将移动节点在一个周期内的时 隙划分为睡眠时隙和活跃时隙，其中，活跃时隙分为锚时隙、探针时隙及素数 时隙三种类型。

特别地，所述步骤B中在定义和选择素数时隙时，选取单个素数。

特别地，所述步骤B中选择不同参数安排锚时隙、探针时隙和素数时隙的 位置，具体包括：

选择不同的参数t和p安排锚时隙、探针时隙和素数时隙的位置,其中，t 为移动节点一个周期的时隙数，p是[2,t-1]内的素数。

特别地，所述步骤B中安排锚时隙、探针时隙和素数时隙的位置，具体包 括：

锚时隙的位置固定，安排在每个周期的第一个时隙；探针时隙可以系统地 搜索其它节点的锚时隙，其位置从时隙计数值1开始，每个周期增加1，结束于 然后重复此过程；所选素数限定在[2,t-1]，对应的素数时隙安排在时隙 计数值模p等于零的位置。

特别地，所述邻居发现调度表由预定义的固定长度的时隙组成。

特别地，所述步骤C具体包括：

移动节点根据所述邻居发现调度表，在活跃时隙的开头和结尾均发送信标 消息，当锚时隙、探针时隙和素数时隙这三种活跃时隙的任意两个时隙相互交 迭时，即可收到消息并记录其邻居，完成邻居发现。

本发明提出的基于协同素数的非对称低轮值周期邻居发现方法具有如下优 点：一、素数时隙使用单个协作的素数，保证了在有界的发现时延内完成快速 的异步邻居发现，并且增加了可选轮值周期的数量，能量分配更加灵活。二、 在非对称低轮值周期情况下，不仅能够保证移动节点较低的能量开销，而且减 小了最坏发现时延。

附图说明

图1为本发明实施例提供的基于协同素数的非对称低轮值周期邻居发现方 法流程图；

图2为本发明实施例提供的传统基于时分机制的邻居发现调度表示意图；

图3为本发明实施例提供的利用本发明建立的邻居发现调度表示意图；

图4为本发明实施例提供的非对称轮值周期的邻居发现示意图；

图5为本发明实施例提供的非对称轮值周期为1%-10%时发现时延累积分布 函数曲线图；

图6为本发明实施例提供的非对称轮值周期为1%-10%和1%-5%时不同邻居 发现方法的平均发现时延对比图；

图7为本发明实施例提供的非对称轮值周期为1%-5%且选取不同调节因子α 时发现时延累积分布函数曲线图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明。可以理解的是，此处所描 述的具体实施例仅仅用于解释本发明，而非对本发明的限定。另外还需要说明 的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部内容。

请参照图1所示，本实施例中基于协同素数的非对称低轮值周期邻居发现 方法包括如下步骤：

步骤S101、根据移动节点的能量需求和时延要求选择相应的轮值周期。

轮值周期表示节点活跃和睡眠时间比。节点的能量越少需要的轮值周期越 小。同时，由于移动设备的异构性，不同节点可能选择非对称的轮值周期。

步骤S102、根据所述轮值周期，选择不同参数安排锚(anchor)时隙、探针 (probe)时隙和素数(prime)时隙的位置，建立邻居发现调度表。

采用基于时分机制的周期性睡眠调度方法，将移动节点在一个周期内的大 部分时隙定义为睡眠时隙，部分时隙定义为活跃时隙，从而建立邻居发现调度 表，这样一来，移动节点在大部分时隙睡眠，小部分时隙活跃，有利于节省能 量，延长生命周期。如图2所示，图中A、B代表两个移动节点，黑色区域为活 跃时隙，白色区域为睡眠时隙，移动节点A、B将在每个周期的一个或多个时隙 醒来，而在剩余的大部分时隙睡眠。在醒来的时隙，也即活跃时隙，节点可以 根据应用程序发送或接收消息。当两个活跃时隙相互交迭，互为邻居的移动节 点A、B就可以成功发现对方。

仅通过将移动节点在一个周期内的大部分时隙定义为睡眠时隙，部分时隙 定义为活跃时隙，建立邻居发现调度表，并不能在极低的能量开销下保证有界 且较小的发现时延，从而完成低功耗的邻居发现。因此本发明将活跃时隙分为 三种类型：锚时隙、探针时隙及素数时隙。根据步骤S101所选的轮值周期，选 择不同的参数t和p安排锚时隙、探针时隙和素数时隙的位置,建立邻居发现 调度表，t为移动节点一个周期的时隙数，p是[2,t-1]内的素数。锚时隙的位 置固定，安排在每个周期的第一个时隙；探针时隙可以系统地搜索其它节点的 锚时隙，其位置从时隙计数值1开始，每个周期增加1，结束于然后重复 此过程；同时，由中国剩余定理获得启发，本发明引入第三种活跃时隙，即素 数时隙，在定义和选择素数时隙时，选取单个素数，所选素数限定在[2,t-1]， 对应的素数时隙安排在时隙计数值模p等于零的位置。需要说明的是，邻居发 现调度表由预定义的固定长度的时隙组成。

如图3所示，用A，P，p分别代表锚时隙、探针时隙和素数时隙，通过安 排(A,P,p)建立一种新的邻居发现调度表。本发明设定一个时隙计数器，A位 于时隙0；P从时隙1开始，每个周期增加1，结束于然后重复此过程；p 处在时隙计数值模p等于零的位置，例如，选取素数p=5，若时隙计数t的初值 为0,当tmodp＝0时该时隙（即时隙0,5,15,20…）为活跃的素数时隙。举个例 子，对于某一移动节点，选择周期t=8、素数p=5，探针时隙周期性的按照 {1,2,3,4}选取，可以建立一个邻居发现调度表，即图3所示。

在非对称情况下，不同移动节点选取不同参数t和p，建立不同的邻居发现 调度表。图4是一个非对称情况下邻居发现的例子，其中，A（p）或P（p）分 别表示锚时隙和素数时隙、探针时隙和素数时隙的选取重叠，两个移动节点u 和v分别选取t_u＝6,p_u＝3和t_u＝8,p_u＝5，可以在时隙6、9、21进行发现。

步骤S103、移动节点根据所述邻居发现调度表，完成邻居发现。

实际上，移动节点总是独立运行，也没有设定一个全局时间，时钟漂移就 会导致时隙非对齐。本发明不会假设或者依靠不同节点之间的时隙边界对齐。 为了解决时隙非对齐的问题，移动节点根据所述邻居发现调度表，在活跃时隙 的开头和结尾均发送信标（beacon）消息，而在时隙的剩余时间进行通信。当 锚时隙、探针时隙和素数时隙这三种活跃时隙的任意两个时隙相互交迭时，即 可收到消息并记录其邻居，完成邻居发现。一般情况下，节点可以将每个时隙 设为几毫秒，甚至几微秒，而配有Wi-Fi的智能手机需要设为几秒。为了节省 能量，节点需要使用尽量少的时隙进行邻居发现。

下面对本发明在对称轮值周期和非对称轮值周期下的性能进行说明。

首先讨论对称情况，也就是所有的移动节点具有相同的邻居发现调度表。 本发明在对称情况下的最坏发现时延，也即完成邻居发现所需的最小时隙数量 为由此可知，本发明在发现时延和能量消耗之间折中，虽然引入素数时 隙增加了轮值周期，但是降低了发现时延。

其次，在非对称情况下，不同移动节点选取不同参数t和p，建立不同的发 现调度表。假设两个移动节点的轮值周期分别为1/x₁和1/x₂，且x₁＞x₂。给定参数 (t₁,p₁),(t₂,p₂)，p₁,p₂为所选素数，α为调节因子，则本发明的最坏发 现时延小于等于与Searchlight协议相比，即只需α＞4， 本发明的最坏发现时延小于Searchlight协议，更小于Disco和U-Connect协 议。不仅如此，本发明中不同移动节点的锚时隙、探针时隙和素数时隙交迭的 机会更多，所以相比其他邻居发现协议其最坏发现时延会更小。同时，本发明 增加了可选轮值周期的数量，能量分配更加灵活。

另外，之所以在定义和选择素数时隙时，选取单个素数，其机理如下：

如果按照任意非负整数选取活跃时隙不能保证时隙交迭，同时只选取互素 的非负整数也不能保证发现，所以应该使用纯素数来决定活跃时隙。但是，选 取多个素数将导致冗余且带来更大的能量消耗，所以本发明选取单个素数协同 地与参数t共同决定活跃时隙。

假设两个移动节点的轮值周期分别为1/x₁和1/x₂，且x₁＞x₂。两个节点各自选 取n个素数，即p₁₁,p₁₂,...,p_1n和p₂₁,p₂₂,...,p_2n，令及 且α₁＞α₂＞...＞α_n，则p₁₁＜p₁₂＜...＜p_1n及p₂₁＜p₂₂＜...＜p_2n。 两个节点的轮值周期为：和 $\frac{2}{t_2}+\frac{1}{p_{21}}+...+\frac{1}{p_{2n}}\approx \frac{2+{\alpha }_1+{\alpha }_2+...+{\alpha }_n}{t_2}=\frac{1}{x_2}.$所以，最坏发现时延为：

$\min \{p_{11},p_{12,...}{p}_{1n}\}·\min \{p_{21},p_{22},...p_{2n}\}$

$=p_{11}·p_{21}$

$=\frac{x_1{x}_2{(2+{\alpha }_1+{\alpha }_2+...+{\alpha }_n)}^2}{{\alpha }_1^2}$

显然，由此可得，选取单个素数时，本发明在非 对称情况下的最坏发现时延最小。换句话说，选取单个协同地素数时，本发明 的性能最优。

以下为仿真分析状况：1)仿真设置与说明。本分析重点关注的是非对称情 况下不同协议花费相同能量时，需要多长时间发现邻居。不失一般性，能量可 以由轮值周期表示。发现时延指的是从两个节点进入各自通信范围到互相发现 对方的延迟时间，现在用时隙的个数表示发现时延。每个协议以不同的种子运 行1000次，通过观察发现时延的累积分布函数曲线，可以分析不同协议的性能。 本发明对所提出的pSearch协议与Disco、U-Connect及Searchlight协议进行 比较。本分析也评估了调整因子α对协议性能的影响。2）发现时延分析。重点 分析和比较了不同邻居发现协议在节点选择非对称轮值周期时的发现时延。不 失一般性，设置非对称低轮值周期1%-10%对于pSearch协议，令调整因子α等 于8。当两个移动节点的轮值周期分别为1%和10%时，Disco协议选取的素数对 为（17,23）和（191,211），U-Connect选取的素数为17和151，Searchlight 协议选取的参数为20和200，而pSearch协议选取的参数为（100,13）和 （1000,123）。如图5所示，相比Searchlight协议，pSearch减小了约30%发 现时延，在几种发现协议中性能最优。从图5也可以看出，确定性的邻居发现 协议不会导致发现时延累积分布函数的拖尾。图6更清晰地分析和比较了不同 邻居发现协议的平均发现时延，1、2、3、4分别表示Searchlight、pSearch、 U-Connect、Disco协议的发现时延条形图。在非对称低轮值周期1%-10%和1%-5% 时，pSearch协议的平均发现时延略大于Searchlight协议，但是小于其它协议。

非对称情况下，pSearch协议的最坏发现时延为为了分析调整因子 α对pSearch协议性能的影响，分别选取α等于2、6和8。如图7所示，当轮值 周期分别为1%和5%时，pSearch协议的发现时延随着α的增大而减小，α大于4 时，即为6和8时，pSearch协议的最坏发现时延小于Searchlight协议。但是， 随着α增大，发现时延的减小幅度在变小，最终将近似等于x₁x₂。

本发明的技术方案在非对称低轮值周期情况下，不仅能够保证移动节点较 低的能量开销，而且减小了最坏发现时延。

以上所述仅为本发明的优选实施例，并不用于限制本发明，对于本领域技 术人员而言，本发明可以有各种改动和变化。凡在本发明的精神和原理之内所 作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。