基于素数集合的传感网邻居发现中的素数集合配置的方法

摘要

本发明公开了一种基于素数集合的传感网邻居发现中素数集合配置的方法。首先选择与节点需求占空比的倒数作为集合开始配置的起点，然后沿数值增大和减小的方向依次不断增加素数加入集合，直到素数集合中的素数个数等于约定值。计算配置出来的素数集合的期望占空比值，并判断配置的素数集合是否需要优化，如果期望占空比与需求占空比一致，则不需要优化。否则，对素数集合中的素数从数值增大和减小的方向进行调换，再次进行期望占空比的计算和判断，直到达到符合要求的场景需要的占空比值。本发明可选择不同的素数集合进行占空比调节，尽可能使节点需要的占空比与期望占空比接近，极大地降低邻居发现的平均延迟和能耗。

说明书

一、技术领域

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

二、背景技术

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

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

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

在基于素数集合的低占空比传感网邻居发现的方法中素数集合配置是非常 重要的环节。素数集合的配置直接关系到邻居发现的平均发现延迟。本发明在基 于素数集合的低占空比传感网邻居发现的方法基础上，进一步发展和优化素数集 合的配置，突破邻居发现的平均发现延迟，提高邻居发现比率，提高网络通信质 量。

三、发明内容

本发明的目的是提供一种有效的素数集合配置的方法，该方法从素数集合的 优化中达到最佳素数集合配置效果。

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

在无线传感网中，节点按照自己的占空比，从事先根据素数集合配置方法配 置好的素数集合中选取自己的素数集合，该素数集合P中的素数将作为节点的工 作周期，素数集合P的配置方法是：首先选择节点需求占空比的倒数作为集合开 始配置的起点，然后沿数值增大和减小的方向依次不断增加素数到素数集合P， 直到素数集合中的素数个数大于约定值k为止；计算配置出来的素数集合的期望 占空比值并判断配置的素数集合是否需要优化，如果期望占空比与需求占空 比一致，则不需要优化。否则，对素数集合中的素数从数值增大和减小的方向进 行调换，再次进行期望占空比的计算和判断，直到达到符合要求的场景需要的 占空比值d。

期望占空比公式为：

上式中k为素数集合中元素的个数。

对于素数集合P，设定的表达式为

P＝{p₁,p₂,p₃,...,p_k},k≥2,k∈N⁺式中，N⁺为自然数，k为素数的个数，

p₁,p_2,…,p_k为素数集合中的单个素数；

式中，k为约定的素数个数，p_i为素数集合中的某个素数。

所述判断配置的素数集合是否需要优化，直到达到符合要求的期望占空比 值，其步骤是：计算期望占空比符合场景需要的占空比值，直接使用；若不 符合场景需要的占空比值，判断配置出来的素数集合的期望占空比值是否大于 场景需要的占空比d，判断配置出来的素数集合的期望占空比值是否 小于场景需要的占空比d，

若将配置出来的素数集合中的最小的素数删除，并在素数集合中数 值增大的方向加入一个素数，该素数应为大于当前素数集合中最大值的最小素 数；再计算当前素数集合的重复该步骤直到为止；在此过程中得到一 个素数集合的序列，记为{P₁,P₂,...P_n}；记P_n的期望占空比为P_n-1的期望占空 比为若则选择P_n为最终素数集合，否则选择P_n-1为最终的 素数集合；

若将配置出来的素数集合中的最大的素数删除，并在素数集合中数 值减小的方向加入一个素数，该素数应为小于当前素数集合最小值的最大素数， 再计算当前素数集合的重复该步骤直到为止；在此过程中得到一个素 数集合的序列，记为{P₁,P₂,...P_n}；记P_n的期望占空比为P_n-1的期望占空比为 若则选择P_n为最终素数集合，否则选择P_n-1为最终的素数 集合。

设场景需求占空比d的可接受范围ε，素数集合中的素数满足如下公式：

$|d-\hat{d}|=|d-\frac{\underset{i=1}{\overset{k}{\Sigma }}{c}_i}{\underset{i=1}{\overset{k}{\Sigma }}{p}_i{c}_i}|<ϵ$

其中d为场景需求的节点占空比，为节点期望占空比，ε为场景节点可以 接受的节点需求占空比与节点实际期望占空比最大误差，c_i是工作周期数集合C 中与素数集合P中p_i相对应的工作周期次数。

本发明的积极效果是：

1、采用素数集合优化的方法，可以将素数集合配置后的期望占空比与传感 网中场景需要的占空比无限接近，能更好的迎合用户的需求，极大降低邻居发现 的平均延迟，降低节点邻居发现能耗。并让发现延迟拖尾变短、变细。

2、特别适合移动场景下的邻居发现：由于本发明可以根据不同的场景选择 不同的素数集合来进行占空比调节，针对性强，适应性好，效果显著，极大提高 了给定时间内邻居发现概率。

3、操作简单可靠，应用前景广阔。

四、附图说明

图1是本发明的素数集合优化流程图。

图2是优化的素数集合中素数个数约定数与邻居发现概率的曲线图。

五、具体实施方式

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

素数集合P的配置方法是：首先选择节点需求占空比的倒数作为集合开始配 置的起点，然后沿数值增大和减小的方向依次不断增加素数到素数集合P，直到 素数集合中的素数个数大于约定值k为止；计算配置出来的素数集合的期望占空 比值并判断配置的素数集合是否需要优化，如果期望占空比与场景需要的占 空比一致，则不需要优化。否则，对素数集合中的素数从数值增大和减小的方向 进行调换，再次进行期望占空比的计算和判断，直到达到符合要求的场景需要 的占空比值d。

期望占空比公式为：

上式中k为素数集合中元素的个数。p_i为某个素数。

对于素数集合P，设定的表达式为

P＝{p₁,p₂,p₃,...,p_k},k≥2,k∈N⁺式中，N⁺为自然数，k为素数的个数， p₁,p_2,…,p_k为素数集合中的单个素数。

进行优化的步骤参见图1：

计算期望占空比符合场景需要的占空比值，直接使用；若不符合场景需 要的占空比值，判断配置出来的素数集合的期望占空比值是否大于场景需要的 占空比d，判断配置出来的素数集合的期望占空比值是否小于场景需 要的占空比d，

若将配置出来的素数集合中的最小的素数删除，并在素数集合中加 入一个素数，该素数应为大于当前素数集合中最大值的最小素数；再计算当前素 数集合的重复该步骤直到为止；在此过程中得到一个素数集合的序列， 记为{P₁,P₂,...P_n}；记P_n的期望占空比为P_n-1的期望占空比为若 则选择P_n为最终素数集合，否则选择P_n-1为最终的素数集合；

若将配置出来的素数集合中的最大的素数删除，并在素数集合中加 入一个素数，该素数应为小于当前素数集合最小值的最大素数，再计算当前素数 集合的重复该步骤直到为止；在此过程中得到一个素数集合的序列， 记为{P₁,P₂,...P_n}；记P_n的期望占空比为P_n-1的期望占空比为若 则选择P_n为最终素数集合，否则选择P_n-1为最终的素数集合。

在实际操作中，素数集合的配置不能够全部与场景所需要的占空比精确匹 配。场景需要的占空比d有一个可接受范围ε。根据这个范围ε最大限度满 足用户需求的占空比。

设场景需求占空比d的可接受范围ε，素数集合中的素数满足如下公式：

$|d-\hat{d}|=|d-\frac{\underset{i=1}{\overset{k}{\Sigma }}{c}_i}{\underset{i=1}{\overset{k}{\Sigma }}{p}_i{c}_i}|<ϵ$

其中d为场景需求的节点占空比，为节点期望占空比，ε为场景节点可以 接受的节点需求占空比与节点实际期望占空比最大误差，c_i是工作周期数集合C 中与素数集合P中p_i相对应的工作周期次数。

其伪代码可描述如下：

//配置素数集合

forcount＝0tok

{

if(count是2的倍数)

从大于起始值的方向选素数加入P

else

从小于起始值的方向选素数加入P

count＝count+1

}

//优化素数集合

if(P的期望占空比等于需求的占空比)

{

返回P

}

if(P的期望占空比大于需求的占空比)

{

while(P的期望占空比大于需求的占空比){

删除P中最小的素数，并加入一个素数，此素数刚好大于P中最大的素 数。

}

if(P的期望占空比更接近需求占空比){

返回P

}

else{

将P中最大素数删除，并增加一个素数，该素数刚好小于P中最小的素 数。返回P

}

}

if(P的期望占空比小于需求的占空比)

{

while(P的期望占空比小于需求的占空比){

删除P中最大的素数，并加入一个素数，此素数刚好小于P中最小的素 数。

}

if(P的期望占空比更接近需求占空比){

返回P

}

else{

将P中最小素数删除，并增加一个素数，该素数刚好大于于P中最大的素数。 返回P

}

}

应用本发明的素数集合配置，配置出来的各个占空比下的素数集合表1，其中， ε<5％。

表1

以配置1％占空比的素数集合为例，假设k＝15。我们选取1％的倒数即100 作为起点，然后按素数增加和减少的两个方向依次加入素数。于是我们依次将 101,97,103,89,107,83,109,79,113,73,127,71,131,67,137加入该素数集合。 由于此时集合中的素数个数已经达到15个，此阶段的工作结束。

由此素数集合的期望占空比计算公式我们可知，我们所配的1％占空比的素 数集合的期望占空比为即于是我们依据第二种情况，从素 数集合中将67删除并加入139。此时经计算得此时已经达 到终止条件。我们经比较得：|0.01009-0.01|<|0.01-0.00960|所以我们选择 {67,71,73,79,83,89,97,101,103,107,109,113,127,131,137} 作为1％占空比的素数集合。

参见图2。在更进一步的研究中我们发现，素数集合中素数个数对本发明的 邻居发现方法性能影响很大。具体体现在：当素数集合中素数个数较多时，本发 明的性能更好。反之亦然。其实从直观上也是很好理解的：影响节点发现其邻居 性能的主要因素是：该节点是否和邻居节点选择了同一个素数。任意两个节点， 如果从同一个素数集合中选素数作为其工作周期，那么其选择相同素数的概率可 表示为：1/k，即当k变大时，两个节点选择相同素数的概率会变小，从而邻居 发现性能会变好。如仿真结果所示，在1％占空比的情况下，我们分别将其素数 集合的素数个数取1,2,4,6,8,10。并且得出他们在相同一段时间内对周围邻居 的发现率。明显的可以看到，当k增大时，对周围邻居的发现率也在随之上升， 即性能变好。

实验数据表明，当k增大时，对周围邻居的发现率也在随之上升，如表2。

表2

素数数目 相同时间内节点发现率 1 0.01 2 0.495 4 0.733385 6 0.81384 8 0.85409 10 0.87971

但是在实际应用中，较大的占空比往往影响了我们素数集合的规模。例如配 置5％占空比的素数集合的话，其素数集合规模必定小于20，因为小于20的素数 一共才8个。因此本方法更适合占空比较低的无线网节点。