基于素数集合的传感网邻居发现中的工作周期选择的方法

摘要

本发明公开了基于素数集合的传感网邻居发现中的工作周期选择的方法。在基于素数集合的传感网邻居发现中，当一个节点根据自己的占空比需求选定了一个素数集合和其相对应的工作周期数集合以后，节点就开始从素数集合中选择一个素数作为其工作周期来工作。选择方法是：随机选择的等概率素数选择方法和二分等概率素数选择方法。二分等概率素数选择方法将素数集合从中间分开成两个子集合，节点随机选取一个子集合用等概率素数选择方法来工作；另一个子集合作为该子集合的补集；定长的时间以后，节点选择该子集合的补集来工作，以此重复。采用本发明可以使节点的期望占空比无限接近实际需求占空比，降低平均发现延时，适合移动通信场景。

说明书

一、技术领域

本发明涉及传感网中的邻居发现，特别涉及基于素数集合的低占空比传感网 邻居发现，具体是一种基于素数集合的传感网邻居发现中的工作周期选择的方 法。

二、背景技术

在无线传感网的不同应用场合都需要组网的过程，而邻居发现是组网的必经 步骤。无线传感网多以分布式和自组织的方式，通过无线通信形成一个多跳的自 组织网络。为了延长网络的寿命，传感器节点必须以低功耗的方式通信。而快速 完成邻居发现，加快组网的速度是降低功耗、实现无线传感网组网的基本和现实 要求。更是移动场景中实现高效数据传输(低平均延迟)的迫切需要。

在无线传感网中，低占空比操作降低了传感器节点工作的功耗，即延长了无 线传感网节点的寿命，进而延长了网络的生命周期。现有低占空比无线传感网邻 居发现方法有同步和异步之分。其中，异步邻居发现方法因为不需要使用额外的 硬件，不需要为维持时钟同步而执行专门的同步操作而受到青睐。

在基于素数集合的低占空比传感网邻居发现的方法中，传感器节点每次只挑 选单个素数作为自己的当前工作周期，大大降低了邻居发现的能耗，从而在相同 能耗情况下，大大降低了邻居发现的平均发现延迟，并让发现延迟拖尾变短、变 细，提高网络通信质量。相对于Birthday、Disco和Searchlight等经典的基于 节点对的异步邻居发现方法，基于素数集合的传感网邻居发现的平均发现延迟更 小。同时，基于素数集合的低占空比传感网邻居发现的方法，可以根据不同的场 景选择不同的素数集合来进行占空比调节，特别适用于移动场景的有效降低能耗、 降低平均发现延迟。

然而，在传感网节点工作过程中如何挑选素数作为当前的工作周期是一个很 重要的问题，从我们的研究过程中发现这对邻居发现算法的性能影响非常大。在 基于素数集合的低占空比传感网邻居发现的方法中，如何挑选素数作为节点的工 作周期是非常重要的环节。它直接关系到邻居发现的时间延迟。本发明在基于素 数集合的低占空比传感网邻居发现的方法基础上，进一步发展和优化节点选择素 数作为自己工作周期的方式，突破邻居发现的平均发现延迟，提高邻居发现比率， 提高网络通信质量。

本发明的基本思路是基于：工作周期的选择应该达到以下两种要求：

1、宏观上使得一个节点的期望占空比接近实际需求的占空比。

2、尽可能的使平均发现延迟降低，即尽可能快的发现周围的邻居。

三、发明内容

本发明的目的是这样达到的：

在无线传感网中，按照不同占空比的需求，首先为每个节点配置一个素数集 合P和相应的工作周期次数集合C；节点将选择该素数集合P中的素数作为自己 的工作周期，并工作确定次数个工作周期；节点以该工作周期工作的次数由集合 C中与节点所选中的素数相对应的工作周期次数决定；最后，传感器节点从素数 集合P中选取一个素数p_i，以该素数p_i作为自己的工作周期并工作c_i个工作周 期，即节点以该素数工作c_ip_i个时隙；在工作完c_i个工作周期之后，传感器节点 再次从P中挑选一个素数作为自己的工作周期并工作相应个工作周期，如此重 复。当一个节点根据自己的占空比需求选定了一个素数集合和其相对应的工作周 期数集合以后，节点就开始从素数集合中选择一个素数作为其工作周期来工作， 该素数的选择即工作周期的选择，选择方法是：

等概率素数选择方法：当一个节点需要更换工作周期时，随机的从素数集合 中选择一个素数来作为其工作周期。

二分等概率素数选择方法：将素数集合从中间分开成两个子集合，当一个节 点开始工作时随机的选取一个子集合来工作；选定某一个子集合以后，另一个子 集合作为该子集合的补集；节点以选取的子集合用等概率素数选择方法开始工 作，定长的时间以后，该节点选择以前一个工作的子集合的补集来工作，选定该 补集后开始以该子集合用等概率素数选择方法开始工作，以此重复。

在二分等概率素数选择方法中，记元素较小的子集合为P_s，元素较大的子集 合为P_b；节点若开始选择P_s作为工作子集合，则子集合P_b为P_s的补集，反之亦然。 节点工作周期选择的方法在设定的条件下进行的，其中，d为场景需求 的节点占空比，为节点期望占空比，ε为场景节点可以接受的节点需求占空比 与节点实际期望占空比最大误差。

本发明的积极效果是：

1、所有的节点在工作时可以更加灵活的挑选素数作为其工作周期。采用等 概率素数选择方法，简单方便；采用二分等概率素数选择方法，更能达到需要达 到的效果。

2、特别适应移动场景，解决了现有技术中移动场景的邻居发现的技术难题， 特别符合无线传感技术的飞速发展的要求。

3、传感器节点每次灵活的挑选单工作周期数作为自己的当前工作周期，大 大降低邻居发现的能耗，从而在相同能耗情况下，降低了邻居发现的平均发现延 迟，并让发现延迟拖尾变短、变细，提高网络通信质量。

四、附图说明

图1是等概率素数选择方法所对应的流程图。

图2是等概率素数选择方法与其他经典邻居发现方法所对应的发现延迟的累积 分布图。图中：

1代表本发明的基于素数集合的低占空比传感网邻居发现方法的曲线，

2代表的是在传感网中，节点以SearchLight方法进行邻居发现的曲线，

3代表的是在传感网中，节点以Birthday方法进行邻居发现的曲线，

4代表的是在传感网中，节点以Disco方法进行邻居发现的曲线。

五、具体实施方式

本发明是基于素数集合的无线传感器网络邻居发现的。

在无线传感网中，按照节点不同占空比的需求，首先为传感网中的各个节点 确定一个素数集合P，该素数集合P中的素数将作为节点的工作周期，然后为P 中的每一个素数都确定一个对应的工作周期次数(即节点选中该素数作为工作周 期后，节点将以该工作周期工作的工作周期次数)，从而得到与素数集合P对应 的工作周期次数集合C。最后，传感器节点从素数集合中选取一个素数p_i，以该 素数作为工作周期并工作c_i个周期(即以该素数工作c_ip_i个时隙)；在工作完c_i个 周期之后，传感器节点将再次挑选新的素数作为工作周期并工作对应个周期，如 此重复。

当一个节点根据自己的占空比需求选定了一个素数集合和其相对应的工作周 期数集合以后，节点就开始从素数集合中按照素数选择方法来选择一个素数作为 其工作周期来工作。该素数选择方法满足以下条件：

1、宏观上以使得一个节点的期望占空比接近实际需求的占空比。

2、尽可能的是平均发现延迟降低，即尽可能快的发现周围的邻居。

根据以上两个需求我们在实际实验中采用了本发明的两种素数选择方法：

A、等概率素数选择方法：顾名思义，当一个节点需要更换素数时，即需要 更换工作周期时，随机的从素数集合中选择一个素数来作为其工作周期。这种方 法的好处是可以充分发挥概率性事件的优势，选择到相同素数的概率很小，为1/k (k为素数集合中素数的个数)，概率性算法的特质使得使用此种素数选择方法 的节点平均发现延迟降低。

如果将工作周期集合C集合和素数集合P集合看做是两个行向量。我们记A 为k阶的元素全为1的行向量。在使用此种素数选择方法时，节点占空比的期望 为:

其中，C^T为自然数，k素数集合中的素数的个数。

由于我们在确定工作周期集合C的时候已经让因此已经足够的接近 需求占空比。另外，通过我们的仿真结果可以发现，此种情况下多素数算法的平 均发现延迟相较于以前提出来的算法已经低了很多。

假如某一个节点要以1％的占空比，它根据自己的需求占空比从素数集合配 置方法中配置出来的素数集合中选择自己占空比所对应的素数集合，为 {67,71,73,79,83,89,97,101,103,107,109,113,127,131,137}。节点选中此集合 后开始工作时，随机的从该集合中选择一个素数作为自己的工作周期。换句话说， 每个素数被选中的概率是相等的，即1/15。当以该工作周期工作完相应次数后， 节点又随机的从集合中选取素数作为自己的工作周期。由于节点的选择仍然是随 机的，所以，此次选择的素数可能跟前一个选择一样，也可能不同。

B、二分等概率素数选择方法：

在介绍此方法前我们先要引入一个数学上的定理。如果a+b＝α，a×b＝β，其 中α为一个定值，如果我们想让β取最大值，那么a＝b＝α/2时β取得最大值。 这个定理是可以通过一些简单的数学常识证明出来的，证明如下：

a+b＝α(1)

a×b＝β(2)

若我们要取β的最大值，可将(1)式变换为：

a＝α-b(3)

将(3)式带入(2)式得：

β＝-b²+bα(4)

我们对(4)式对b求导得：

β'＝-2b+α(5)

令β'＝0可求得最大值点为当a＝b＝α/2时。

对应到二分等概率素数选择方法中：素数集合中的元素按照数值由小到大排 序。其实我们可以看到p₁+p_n≈p₂+p_n-1....≈p_k/2+p_(k/2)+1。基于中国剩余定理， 假如A,B两个节点分别选择x,y素数作为其工作周期来工作，我们可以确定他们 在x×y个时隙内相互发现，那么为了减小发现延时就应该是让x×y取得尽量小。

根据前面提出的定理，为了让x×y的值尽量的小，应该使两个节点在物理 相遇时他们各自的工作周期差异尽可能的大，即尽可能的往素数集合的两头选。

基于以上考虑我们提出了二分等概率素数选择算法。其工作步骤如下：

将素数集合从中间分开成两个子集合，记元素较小的子集合为P_s，较大的子 集合为P_b，当一个节点开始工作时它随机的选取自己是以P_s或P_b来工作。当它 选定某一个子集合以后，就开始以该子集合用等概率素数选择算法开始工作。

过一个定长的时间以后，该节点选择以前一个工作的集合的补集来工作。前 一个如果选的是P_s作为其子素数集合，那么现在就选择P_b。反之亦然。选定该 子集合后开始以该子集合用等概率素数选择方法开始工作。以此重复。

假如某一个节点要以1％的占空比，它根据自己的需求占空比从素数集合配 置方法中配置出来的素数集合中选择自己占空比所对应的素数集合，为 {67,71,73,79,83,89,97,101,103,107,109,113,127,131,137}。我们先将该集合 从中间分为两个子集合，假设为P_s＝{67,71,73,79,83,89,97,101}，

P_b＝{103,107,109,113,127,131,137}。当节点开始工作时，随机的选择一个 子集合作为自己的素数集合，假设此节点选择了P_s子集合作为自己的素数集合。 当选定素数集合后，该节点将使用P_s以等概率素数选择方法工作。

这种工作模式下我们可以让两个节点在物理相遇时选择的素数差异尽可能 的大，从而来降低其平均发现时延。

我们从素数选择方法应满足的条件来看，其实宏观上，一个节点的期望占空 比是和等概率素数选择方法是一样的。非常接近节点的需求占空比。并且在发现 延时上相较于以前提出来的算法，有了很大的降低。

附图2给出了等概率素数选择方法所对应的邻居发现百分数与时延累积分 布图。从图中可以明显的看到本发明方法的发现比率增加得更快，短时间内相互 发现的节点数更多，邻居发现的速度更快。