泛在末梢环境中的节点选择方法

摘要

本发明涉及一种泛在末梢环境中的节点选择方法，包括：计算源节点和服务节点间基于能量的可靠性水平R

说明书

技术领域

本发明涉及通信技术领域，具体而言，涉及一种泛在末梢环境中 的节点选择方法。

背景技术

泛在网络，能够使用户在任何时间任何地点可以享有所需服务， 随着泛在网络的不断发展，越来越多的智能终端、传感器设备、便 携式设备等可以进行通信为用户提供服务，各种能提供不同业务的 终端设备分布于用户周边形成了智能空间即泛在末梢环境(例如:智 能家居、协同办公、智慧校园)。在泛在末梢环境中，节点间可通过 无线通信组成无中心MANET网络，通过协作提供丰富的泛在业务， 因此节点需查找到其他节点所能提供的服务，查找到多个匹配的服 务后，需选择其中之一协作完成服务。因此在泛在末梢网络中协作 完成服务需要服务发现与选择方法。

泛在末梢环境中若每个节点都存储整个网络的服务，节点存储 的信息将过于巨大，若节点只在需要协作完成服务时广播查找匹配 服务，则会在短暂时间内造成网络拥塞，若选择特定节点来存储小 区域内的节点服务，形成基于簇的服务发现结构，则服务发现能快 速有效的实现，因此在服务发现方法中，构建簇结构能有效提高发 现成功率，降低网络拥塞。服务发现的可靠性高低是指查找到匹配 服务的概率大小，若能在较短时间内查找到匹配的服务，则用户等 待时间短，用户体验好。服务选择的可靠性高低是指服务执行时中 断的难易程度，中间路由节点的移动性和能量有限性会造成路径失 效，从而造成服务中断，服务提供节点的失效更会造成服务中断。 若能预测节点及路径的可靠性水平，并选择可靠性高的节点及路径， 则可有效减少服务中断次数，增强用户体验。因此泛在末梢环境下 基于可靠性预测的服务发现与选择方法具有重要的研究价值。

现有技术中主要存在以下几种方式实现节点或路径的选取来进 行通信：

1、通过广播服务发现请求的方式查找匹配的服务，但是限制广 播服务请求信息的跳数，从而达到减少服务发现负载的目的。但只 在有限跳数内寻找服务，可能出现匹配的服务全在查找范围外的情 况，其服务发现成功率并不高，同时广播服务发现请求的方式可能 会造成短时间内网络拥塞的发生；

2、跨层以及分簇的思路，但是簇头节点的选择方案并不能保证 该簇的稳定性，同时没有提出查找到多个匹配的服务时如何选择服 务提供节点的问题；

3、选择能使网络生命周期最长的服务提供节点，但网络中提供 服务或转发消息消耗的能量并不是减小其网络生命周期的最重要因 素，同时，用户体验到的服务质量高低比网络生命周期长短更重要， 同时，该方式中还订了Cost函数：Cost＝∑i∈pathnumService(Ni) ×Et+numService(SPselected)×Eexe其中，Ni是从服务发起节点到服 务执行节点路径上的中间节点，Et是服务中继节点传递服务请求所 需要的能量，Eexe是服务执行节点执行该服务所需要的能量， SPselected是选取来执行服务的节点，服务发起节点依据Cost函数 的定义计算每个节点的Cost值，选取Cost最小的节点作为服务执行 节点，但对于每个不同的请求服务而言，服务提供节点和中间路由 节点需消耗的能量都具有差异性，该方案并不能精确估算具体的能 量消耗值。

发明内容

本发明所要解决的技术问题是本发明的目的在于如何构建泛在 末梢环境下基于可靠性预测的服务发现与选择方法，通过预测节点的 移动性及节点有效时间，建立可靠性高的簇结构以完成服务发现，同 时计算服务提供节点及路径的可靠性，选取可靠性最高的服务提供节 点及路径，采用双路径机制增强路径可靠性，从而完成服务选择。

为此目的，本发明提出了一种泛在末梢环境中的节点选择方法， 包括：S4，计算所述源节点的速度在水平方向和垂直方向上的分解量 v_x0和v_y0，以及当前时刻的与服务节点的距离d，根据当前时刻的距离 d与T时间后两节点之间距离的比值计算两节点间基于移动性的可靠 性水平R_SM，

其中，T为完成服务所需时间，获取所述源节点剩余能量所能持 续的时间t_N，计算两节点间基于能量的可靠性水平R_SE，

$R_{\mathrm{SE}}=\left(\begin{array}{cc}{t}_N/T& t_N<T\\ 1& t_N>=T\end{array}\right),$

计算所述服务节点的可靠性R_S＝R_SM*R_SE，则所述服务节点的选择 权重值R＝w*R_S/delay，其中，delay两节点间传输数据的时间延迟量， w为调节因子；S5，每个服务节点向所述源节点回复消息包Reply (u_j,m_i,s,R_S,Path)，其中，u_j为服务请求的源节点标识，s为请求服务 名称，m_i为服务节点的标识，Path为列表，用于记录服务节点m_i到所 述源节点的通信链路上每个节点的速度和剩余能量所能持续的时间， 所述源节点计算每个服务节点的R，并选取R最大的服务节点为目标 服务节点；S6，针对位于所述源节点和所述目标服务节点通信链路上 的第一节点和第二节点，获取两节点当前时刻的距离d₀和两节点中通 信半径较小的节点的通信半径r，设两节点间链路的可维持时间t_L，则 在经过在t_L时长后，两节点的距离由d₀变为r，计算所述第二节点相对 于所述第一节点的速度在水平方向和垂直方向上的分量v_x和v_y，则根 据方程组

计算t_L，计算第一节点和第二节点的通信链路基于移动性的可靠性水 平M，

$M=\left(\begin{array}{cc}1& t_L>=T\\ t_L/T& t_L<T\end{array}\right),$

获取所述源节点和目标服务节点通信链路上的节点数量pn，节点 i的剩余能量所能持续的时间为t_i，则所述源节点和目标服务节点间通 信链路基于能量的可靠性水平为R_RE，

R_RE＝min(t₁/T,t₂/T…t_pn/T)*[(t₁/T+t₂/T+…+t_pn/T)/pn]，

所述源节点和目标服务节点间通信链路基于移动性的可靠性水 平为R_RM，

R_RM＝min(M₁,M₂…M_pn-1)*[(M₁+M₂+…+M_pn-1)/(pn-1)]，

所述源节点和目标服务节点间通信链路的可靠性水平为R_R，

R_R＝R_RE*R_RM；

选取所述源节点和目标服务节点间通信链路中R_R最大的通信链 路进行数据传输。

优选地，在所述步骤S4之前还包括：S1，预测计算节点在n时刻 的移动速度$v_n={\mathrm{av}}_{n-1}+(1-a)\bar{v}+\sqrt{1-a^2}{v}_{\mathrm{Xn}-1},$其中，a为随机性 调节因子，v_n-1为所述节点在第n-1时刻的移动速度，v_Xn-1为节点的 移动速度符合高斯分布的随机速度变量，为节点的历史平均速度。

优选地，在所述步骤S1之后还包括：S2，检测所述目标节点u的 剩余能量所能持续的时间u.st，邻节点数u.d和计算能力u.cc，计算所 述目标节点在泛在末梢环境中作为簇头节点的可能性值 u.W＝w₁*u.st+w₂*u.d+w₃*u.cc-w₄*u.v，其中，u.v根据所述目标节点所处的时刻和v_n确定，所述目标节点向其邻节点 发送u.W，并接收每个邻节点作为簇头节点的可能性值 z₁.W,z₂.W,…,z_i.W，其中，z_i为所述目标节点第i个邻节点的标识，比 较u.W与z_i.W，在u.W大于每个z_i.W时将所述目标节点设置为簇头节 点。

优选地，在所述步骤S2之后还包括：S3，在以所述目标节点为簇 头节点的簇中，当簇成员节点u_j接到服务请求时，建立消息包Request (u_j,s,D,v_s)发送至簇头节点，其中，v_s为所述源节点的速度，D为请 求服务的细节列表，簇头节点所在簇中查询能够提供该请求服务的服 务节点，若存在，则进入步骤S4，若不存在，则将消息包Request转 发至与所述目标节点存在通信路径的相邻簇头节点，在相邻簇头节点 所在簇中查询能够提供该请求服务的服务节点，并进入步骤S4。

优选地，所述步骤S4还包括：服务节点根据消息包Request中 的D获取完成服务所需时间T和源节点剩余能量所能持续的时间t_N， 并计算R_SE和R_S。

优选地，所述步骤S2还包括：若u.W小于z_m.W，则将所述目标 节点的第m个邻节点设置为簇头，所述目标节点加入z_i.W最大的邻 节点为簇头的簇。

优选地，所述步骤S2还包括：检测所述目标节点的邻节点z_i的 邻节点中是否存在相邻簇头节点，若存在，则建立所述目标节点与相 邻簇头节点之间的通信路径，若不存在，则检测邻节点z_i的邻节点的 邻节点中是否存在相邻簇头节点，直至检测到相邻簇头节点，并建立 所述目标节点与相邻簇头节点之间的通信链路。

优选地，所述步骤S2还包括：所述目标节点周期性向其所在簇 中的成员节点发送验证信息，以验证成员节点是否有效，若验证存在 失效的成员节点，则在服务列表中删除失效成员节点的对应项，以及， 在所有成员节点都失效的情况下，重新选择簇头节点，在部分成员节 点失效的情况下，则为失效的成员节点查询中间节点，以使失效的成 员节点重新加入簇。

优选地，还包括：选取所述源节点和目标服务节点间通信链路中 R_R第二大的通信链路作为备用链路，在R_R最大的通信链路失效的情 况下选取所述备用链路进行数据传输。

优选地，还包括：所述源节点周期性判断所述目标服务节点是否 失效，若失效，则重新发起服务。

根据上述技术方案，通过预测节点的移动性及节点有效时间，建 立可靠性高的簇结构以完成服务发现，同时计算服务提供节点及路径 的可靠性，选取可靠性最高的服务提供节点及路径提供和传输服务， 从而保证服务传输的高可靠性，并采用双路径机制增强路径可靠性， 从而完成服务选择。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示 意性的而不应理解为对本发明进行任何限制，在附图中：

图1示出了根据本发明一个实施例的泛在末梢环境中的节点选择 方法的示意流程图；

图2示出了根据本发明一个实施例的簇构建过程示意图；

图3示出了根据本发明一个实施例的簇维护过程示意图；

图4示出了根据本发明一个实施例的路径选择的示意流程图。

具体实施方式

了能够更清楚地理解本发明的上述目的、特征和优点，下面结合 附图和具体实施方式对本发明进行进一步的详细描述。需要说明的 是，在不冲突的情况下，本申请的实施例及实施例中的特征可以相互 组合。

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但 是，本发明还可以采用其他不同于在此描述的其他方式来实施，因此， 本发明的保护范围并不受下面公开的具体实施例的限制。

如图1所示，本发明提出了一种泛在末梢环境中的节点选择方法， 包括：S4，计算源节点的速度在水平方向和垂直方向上的分解量v_x0和v_y0，以及当前时刻的与服务节点的距离d，根据当前时刻的距离d 与T时间后两节点之间距离的比值计算两节点间基于移动性的可靠性 水平R_SM，

其中，T为完成服务所需时间，获取源节点剩余能量所能持续的 时间t_N，计算两节点间基于能量的可靠性水平R_SE，

$R_{\mathrm{SE}}=\left(\begin{array}{cc}{t}_N/T& t_N<T\\ 1& t_N>=T\end{array}\right),$

计算服务节点的可靠性R_S＝R_SM*R_SE，则服务节点的选择权重值 R＝w*R_S/delay，其中，delay两节点间传输数据的时间延迟量，w为调 节因子；S5，每个服务节点向源节点回复消息包Reply(u_j,m_i,s, R_S,Path)，其中，u_j为服务请求的源节点标识，s为请求服务名称，m_i为服务节点的标识，Path为列表，用于记录服务节点m_i到源节点的通 信链路上每个节点的速度和剩余能量所能持续的时间，源节点计算每 个服务节点的R，并选取R最大的服务节点为目标服务节点；S6，针 对位于源节点和目标服务节点通信链路上的第一节点和第二节点，获 取两节点当前时刻的距离d₀和两节点中通信半径较小的节点的通信 半径r，设两节点间链路的可维持时间t_L，则在经过在t_L时长后，两节 点的距离由d₀变为r，计算第二节点相对于第一节点的速度在水平方向 和垂直方向上的分量v_x和v_y，则根据方程组

计算t_L，计算第一节点和第二节点的通信链路基于移动性的可靠性水 平M，

$M=\left(\begin{array}{cc}1& t_L>=T\\ t_L/T& t_L<T\end{array}\right),$

获取源节点和目标服务节点通信链路上的节点数量pn，节点i的 剩余能量所能持续的时间为t_i，则源节点和目标服务节点间通信链路 基于能量的可靠性水平为R_RE，

R_RE＝min(t₁/T,t₂/T…t_pn/T)*[(t₁/T+t₂/T+…+t_pn/T)/pn]，

源节点和目标服务节点间通信链路基于移动性的可靠性水平为 R_RM，

R_RM＝min(M₁,M₂…M_pn-1)*[(M₁+M₂+…+M_pn-1)/(pn-1)]，

源节点和目标服务节点间通信链路的可靠性水平为R_R，

R_R＝R_RE*R_RM；

选取源节点和目标服务节点间通信链路中R_R最大的通信链路进 行数据传输。

泛在末梢环境的不同场景模型下，用户具有不同的行为特征，由 于不同场景模型可以类推，因此可以设置场景模型为道路上无基站移 动节点协作完成服务，通过建立节点移动模型，预测节点的移动性及 节点有效时间，建立可靠性高的簇结构以完成服务发现，同时计算服 务提供节点及路径的可靠性，选取可靠性最高的服务提供节点及路 径，采用双路径机制增强路径可靠性，从而完成服务选择。需要说明 的是，步骤S5可以发生于步骤S4之中，其仅用于解释和说明S4中 的部分参量的来源和获取方式，而并不一定发生于步骤S4之后。

由于泛在末梢网络中节点具有移动性和电池能量有限性，为保证 服务执行中断次数少，要求通过协作完成服务时，服务提供节点的可 靠性越高。服务提供节点有效概率由服务提供节点与请求源节点的相 对移动性及服务提供节点的剩余能量支持时间决定。

通过根据服务节点的可靠性R_S＝R_SM*R_SE计算服务节点的选择权 重值R＝w*R_S/delay，并根据R来选取目标服务节点，可以选取可靠 性最高的节点提供服务，从而在运算能力、服务的相符性以及可提供 服务时长等方面得到最优保障。并且进一步根据源节点和目标服务节 点间通信链路的可靠性水平为R_R选取通信链路(在源节点和目标服 务节点之间存在多条链路的情况下)，可以保证选取两节点之间的最 优链路进行数据通信，从而保证数据通信最高的稳定性和最快的速 度。

优选地，在步骤S4之前还包括：S1，预测计算节点在n时刻的移 动速度$v_n={\mathrm{av}}_{n-1}+(1-a)\bar{v}+\sqrt{1-a^2}{v}_{\mathrm{Xn}-1},$其中，a为随机性调节 因子，v_n-1为节点在第n-1时刻的移动速度，v_Xn-1为节点的移动速度 符合高斯分布的随机速度变量，为节点的历史平均速度。

在具有道路的场景模型中，节点的运动均有一定的规律性，可以 通过预测节点的移动速度矢量建立节点的移动模型。设节点均在道路 上行走，则预测用户的移动速度矢量可分为两种情况：节点此时位置 在道路中以及节点此时位置在道路交叉点上。

当节点此时在道路中时，节点的移动速度与其较近时间内的速 度、历史速度具有相关性，因此可使用高斯-马尔可夫模型预测用户 在区域内运动的速度矢量，第n时刻的速度大小v_n不仅和第n-1时刻的 速度大小v_n-1有关，也和历史平均速度相关。而当节点到达某道路交 叉点时，需选取一条新道路继续运动，设r_i为空间内某交叉点的第i 个方向的道路，根据高斯-马尔科夫思想，基于其历史经过此交叉点 选择的道路次数预测其速度方向，节点选择道路的概率为

$p\left(r_i\right)=N\left(r_i\right)/\underset{j=1}{\overset{j=m}{\Sigma }}N\left(r_j\right)$

所示，其中p(r_i)表示选择r_i这条道路的概率，N(r_i)表示历史经过 此交叉点选择r_i这条道路的次数。节点基于预测的速度方向取沿着道 路的方向，速度大小不变。

优选地，在步骤S1之后还包括：S2，检测目标节点u的剩余能量 所能持续的时间u.st，邻节点数u.d和计算能力u.cc，计算目标节点在 泛在末梢环境中作为簇头节点的可能性值 u.W＝w₁*u.st+w₂*u.d+w₃*u.cc-w₄*u.v，其中，u.v根据目标节点所处的时刻和v_n确定，目标节点向其邻节点发送 u.W，并接收每个邻节点作为簇头节点的可能性值z₁.W,z₂.W,…,z_i.W， 其中，z_i为目标节点第i个邻节点的标识，比较u.W与z_i.W，在u.W大于 每个z_i.W时将目标节点设置为簇头节点。

泛在末梢环境中节点具有能量有限性、处理能力有限性、移动性 等问题，基于此提出在簇的初始化过程中构建最大可靠性的簇算法， 综合考虑节点剩余能量能支持的时间、CPU处理能力、节点连接度和 节点的速度，使用加权法计算四者综合加权值，选取值最大的节点作 为簇头节点。

优选地，在步骤S2之后还包括：S3，在以目标节点为簇头节点的 簇中，当簇成员节点u_j接到服务请求时，建立消息包Request(u_j,s,D,v_s) 发送至簇头节点，其中，v_s为源节点的速度，D为请求服务的细节列 表，簇头节点所在簇中查询能够提供该请求服务的服务节点，若存在， 则进入步骤S4，若不存在，则将消息包Request转发至与目标节点存 在通信路径的相邻簇头节点，在相邻簇头节点所在簇中查询能够提供 该请求服务的服务节点，并进入步骤S4。

优选地，仅在相邻簇头中选择服务节点，在簇结构中服务发现请 求能到达所有簇头节点，且只在簇头上匹配服务，因此可以减少通信 量、改善发现效率、提高发现成功率。

相邻簇头收到服务发现与选择请求后，检查是否重复收到此消 息，若已收到，则丢弃不作处理；若未收到，则重复检查与转发。

优选地，步骤S4还包括：服务节点根据消息包Request中的D 获取完成服务所需时间T和源节点剩余能量所能持续的时间t_N，并计 算R_SE和R_S。由服务节点来获取T和t_N等参数，可以保证源节点的 计算能力，使得用户可以继续使用源节点进行其他操作。

优选地，步骤S2还包括：若u.W小于z_m.W，则将目标节点的第 m个邻节点设置为簇头，目标节点加入z_i.W最大的邻节点为簇头的 簇。

优选地，步骤S2还包括：检测目标节点的邻节点z_i的邻节点中 是否存在相邻簇头节点，若存在，则建立目标节点与相邻簇头节点之 间的通信路径，若不存在，则检测邻节点z_i的邻节点的邻节点中是否 存在相邻簇头节点，直至检测到相邻簇头节点，并建立目标节点与相 邻簇头节点之间的通信链路。可以保证泛在末梢环境中的每个节点都 能够加入到簇中，从而将在整个泛在末梢环境中构件一个完整的通信 网络。

优选地，步骤S2还包括：目标节点周期性向其所在簇中的成员 节点发送验证信息，以验证成员节点是否有效，若验证存在失效的成 员节点，则在服务列表中删除失效成员节点的对应项，以及，在所有 成员节点都失效的情况下，重新选择簇头节点，在部分成员节点失效 的情况下，则为失效的成员节点查询中间节点，以使失效的成员节点 重新加入簇。

优选地，还包括：选取源节点和目标服务节点间通信链路中R_R第二大的通信链路作为备用链路，在R_R最大的通信链路失效的情况 下选取备用链路进行数据传输。

优选地，还包括：源节点周期性判断目标服务节点是否失效，若 失效，则重新发起服务。

上述方法针对如何查找并选择服务提供节点，使得协作完成服务 时查找到匹配服务成功率高、执行服务中断率低的问题，提出在泛在 末梢环境下基于可靠性预测的服务发现与选择协议，首先预测节点的 移动速度矢量，其次，构造并维护簇结构，在簇结构中请求相应的服 务；再次，定义选择服务提供节点及路径的模型；最后，根据模型选 择服务提供节点及路径，服务发现与选择协议完成。基于可靠性预测 的服务发现与选择方法能有效降低服务查找失败率及服务执行中断 率，提高服务的可靠性和用户体验。

在本发明中，术语“第一”、“第二”仅用于描述目的，而不能理 解为指示或暗示相对重要性。术语“多个”指两个或两个以上，除非 另有明确的限定。

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