为提高服务查找成功率以及降低服务中断率, 提出了在泛在末梢环境下基于可靠性预测的服务发现与选择协议(RPD & S).通过建立节点移动模型, 预测节点的移动性及节点有效时间, 计算服务提供节点及路径的可靠性, 选取可靠性最高的服务提供节点及路径, 同时采用双路径机制增强路径可靠性.仿真结果表明, RPD & S的服务查找失败率比跨层的服务发现协议低, 服务执行中断率比基于时延的服务选择协议低. RPD & S能有效解决服务发现与选择中的问题, 提高用户体验.
In order to raise the rate of service searching success and reduce the rate of service executing interruption, the reliability-predicted service discovery & selection protocol (RPD & S) was proposed. A new mobile model of nodes could predict the mobility and available time of nodes, calculate the reliability of service provider nodes and the path, and then select the service provider node and the path with high reliability. Meantime, a double path was built between service request nodes and provider nodes. Simulation shows RPD & S can reduce failure rate of searching service and interrupt rate of execution. It also proves that RPD & S can solve the problems in service discovery and selection and improves the user experience.
在泛在末梢环境下服务发现是指需要协作完成业务时查找能提供匹配服务节点的过程[1]，其目标是提高查找成功率；服务选择是指在返回结果中选择最终提供服务节点及路径的过程[2]，其目标是降低服务执行中断率.可靠性水平高低由服务执行时中断难易程度决定，中间路由节点的移动性和能量有限性会造成路径失效[3]，从而造成服务中断，服务提供节点的失效更会造成服务中断.若能预测节点及路径的可靠性水平，并选择可靠性高的节点及路径，则可有效减少服务中断次数，增强用户体验.泛在末梢环境的不同场景模型下，用户具有不同的行为特征，由于不同场景模型可以类推，所以设置场景模型为道路上无基站移动节点协作完成服务，针对如何查找并选择服务提供节点的问题，提出在泛在末梢环境下基于可靠性预测的服务发现与选择协议.
1 节点移动预测模型1.1 节点在道路上的移动预测模型当节点此时在道路中时，节点第n时刻的速度大小vn不仅和第n-1时刻的速度大小vn-1有关，也和历史平均速度相关，其定义式如(1) 所示，其中v为节点的平均速度，vxn-1为符合Gaussian分布的随机变量，a为随机性调节因子.速度方向为沿着道路方向，在n-1时刻到n时刻保持不变.
|
(1) |
设ri为空间内某交叉点第i个方向的道路.节点选择道路的概率如式(2) 所示，其中p (ri)表示选择ri这条道路的概率，N (ri)表示历史经过此交叉点选择ri这条道路的次数.节点基于预测的速度方向取沿着道路的方向，速度大小不变.
|
(2) |
泛在末梢环境中的节点具有能量有限性、处理能力有限性、移动性等问题，节点当选簇头的可能性由其综合加权值W决定，W值的计算公式如式(3) 所示，其中u.st、u.d、u.cc、u.v分别为节点u剩余电池能量所能支持时间、邻节点数、CPU计算能力、相对邻节点的速度.
|
(3) |
阶段1 构造簇结构
步骤1 W值的计算
1) 检测节点u的u.st、u.d、u.cc，预测u.v.
2) 根据式(1) 计算出节点u的综合加权值u.W.
步骤2 簇头节点的选取
1) 节点u向其邻节点发送u.W消息.
2) 节点u收到其某一邻节点v.W，比较u.W与v.W，若u.W>v.W重复步骤2)，直至所有邻节点比较完毕，跳至3)；若u.W＜v.W，自动跳出阶段2.
3) 节点u自选为簇头节点, 节点u构造簇成员列表及服务列表.
步骤3 节点加入簇
1) 簇头节点u在一跳范围内广播簇消息.
2) 若未加入到任何簇的节点v收到多个簇消息，则加入W值最大的簇头节点所在的簇.若v未收到簇消息但其邻节点存在簇成员节点，则通过邻节点加入到簇.
3) 簇成员节点在簇头节点的服务列表中注册服务.
步骤4 建立簇头节点间路径
1) 簇头节点u向邻节点v发送建立路径消息.
2) v的邻节点中若存在簇头节点，则转发建立路径消息，簇头节点间路径成立；若无，则向其邻节点转发消息.
3) 重复1) 和2) 直至簇头节点间均连通，即任一簇头节点均可通过一个或多个中间节点与其他簇头节点通信.
阶段2 维护簇结构
步骤1 修复簇结构
1) 簇头节点周期性地和簇成员节点通信，验证对方是否有效.
2) 若簇头节点发现某簇成员节点失效，则在服务列表中删除相应表项.若簇头节点对部分节点失效，则节点通过中间节点重新加入簇.若簇头节点对所有节点失效，则重新选择簇头节点.
阶段3 在簇结构中的服务发现
步骤1 节点u请求服务
1) 节点u请求某一服务s, u设置服务s的细节列表D，如下载多少字节的内容、打印多少页内容.
2) u建立服务请求消息包Request(u，s，D，vs)，其中u，s，D，vs为源节点、请求服务名、此服务的细节列表及源节点速度矢量.
3) u向所在簇的簇头节点发送服务请求消息.
步骤2 簇头查找匹配服务
1) 簇头节点收到服务请求消息后，检查本簇服务列表中是否存在匹配的服务.若存在，则向相应服务提供节点v转发服务请求包.
2) 簇头节点向其连通的簇头节点转发Request消息.
3) 其他簇头节点收到服务发现与选择请求后，检查是否重复收到此消息，若已收到，则丢弃不作处理；若未收到，则重复上述的1)、2) 和3).
3 RPS描述3.1 预测单跳链路基于移动性的稳定水平单跳链路的可靠性由链路2个端节点在相互通信范围内的可持续时间决定，依节点的速度预测单跳链路可维持时间t, t与服务需持续的时间T的比值代表此链路在服务需通信期间保持连通的概率，因此可用于预测链路基于移动性的稳定水平.设节点1与节点2基于预测的移动速度矢量分别为v1、v2，节点1、节点2间距离为d，通信半径为r.将v1、v2按节点连线的水平和垂直方向分别分解；按相对移动性原理合并同方向速度，节点1相对不动，节点2相对节点1的速度为vx和vy.
设节点1与节点2间链路持续时间为t，则在t时刻节点1与节点2间距离为r，式(4) 中vx与d同向，下式为vx与d异向.
|
(4) |
根据t值计算单跳链路基于移动性可靠性水平M：
|
(5) |
路径基于能量的可靠性水平受限于该条路径上节点剩余能量所能支持时间与服务所需持续时间比值，还受限于最小时间，整条路径基于能量的可靠性水平RRE量化式如(6) 式所示，设一条路径上节点数量为pn，节点u的剩余能量所能支持时间为ti.
|
(6) |
同理，一条路径基于移动性的可靠性水平受限于该路径上所有单跳链路的平均水平，及该路径上的最小水平，因此整条路径基于移动性的可靠性水平RRM量化公式.
|
(7) |
整条路径的可靠性水平RR由RRM及RRE可由二者乘积得到.
|
(8) |
通过协作完成服务时，服务提供节点的可靠性越高，服务中断次数越少.服务提供节点有效概率由服务提供节点与请求源节点的相对移动性及服务提供节点的剩余能量支持时间决定.
通过两节点间相对速度及速度分解vx与vy求得节点间基于移动性的可靠性水平RSM，计算现有距离d与T时间后两节点距离之间的大小比值. d的方向为两节点连线向外的方向.
|
(9) |
预测的节点能量所能支持时间t，得出服务提供节点基于能量的可靠性水平RSE:
|
(10) |
分析影响服务提供节点可靠性RS的因素，若节点基于移动性的可靠性水平RSM与基于能量的可靠性水平RSE越高，则可靠性越高，可得可靠性计算式.
|
(11) |
定义服务提供节点选择计算式如式(12) 所示.其中d为节点间传递消息的时延，单位为s，w为调节因子.
|
(12) |
阶段1 构造服务回复包并收集路径信息
1) v预测本节点的速度矢量，取Request消息中的vs，并根据式(9) 计算RSM.根据本节点的处理能力，取Request消息中的D，预测完成此服务需要的时间T及节点能量所能支持时间t，根据式(10) 计算RSE，根据式(11) 计算RS，并回复消息Reply(u，v，s，RS，Path)，v为服务提供节点的标识.
2) v向源节点传递Reply(u，v，s，RS，Path)消息，并采集所经过路径上节点的速度矢量与剩余能量所能支持时间，记录到Path列表中.
阶段2 选择服务提供节点及路径
1) 若节点u收到多个回复消息，则计算消息传递时延、取Reply中的RS字段，选择服务提供节点.
2) 若服务请求源节点与提供节点间存在多条路径，则取Path列表中数据，计算各路径的RR，选择可靠水平最高的两条路径作为主路径和备选路径，按主路径与服务提供节点通信.若主路径失效，则使用备选路径，若两条都失效，则重新构造路径.
3) 若在服务执行过程中服务提供节点失效或路径失效，则跳至RPD，重新请求该服务.
4 实验结果及分析4.1 实验环境采集实际场景模型中设备的移动情况，让20台移动设备持有者在校园道路上移动，采集其移动轨迹和移动速度.使用仿真软件OPNET模拟有20个移动设备的环境，将环境抽象成200 m×200 m的矩形，将道路抽象成线段，设备的通信范围是20 m，仿真变量为用户的移动速度V及服务数量N，其中0.5 m/s≤V≤5 m/s，5≤N≤17.
将服务查找时失败次数与总数的比值定义为服务查找失败率(FR，search failure rate)，基于AODV协议跨层的服务发现协议(CSD, cross-layer service discovery)[4]是服务发现协议，不包含簇结构，将CSD作为RPD的比较对象，验证RPD的可靠性及实时性.
将服务执行时中断次数与服务执行总数的比值定义为服务执行中断率(IR, interrupt rate)，基于时延的服务选择协议(DSS, delay-based service selection)[5]是常用的服务选择协议，不包含可靠性预测，选取DSS作为RPS的比较对象，验证RPD的可靠性及高效性.
4.2 实验结果及分析如图 1、图 2所示，RPD的FR小于CSD，因为RPD相当于人为地构造了用于存储服务和匹配服务的分散式基站，同时基站间通过中间路由相互通信，因此这种方式能保证服务查找的可靠性.而CSD通过广播服务请求信息的方式查找服务，不能保证所有节点都能收到服务请求信息，因此RPD的服务查找失败率更低.
|
图 1 FR随SN的变化 |
|
图 2 FR随MV的变化 |
如图 3、图 4所示，RPS的IR小于DSS，因为RPS通过预测节点的移动速度及方向，选取运动方向相对一致的服务提供节点，减少了因服务提供节点距离请求节点距离加大而造成的服务中断，因此服务执行中断率较低.同时通过预测路径的可靠性，选取可靠性高的双路径，进一步降低因路径失效导致的服务失败，因此RPS能有效地降低服务中断率. DSS基于时延选择服务提供节点，在一段时间内服务提供节点会移出请求节点及中间路由节点可感知的有效范围，因此RPS比DSS有更优的IR表现.
|
图 3 IR随SN的变化 |
|
图 4 IR随MV的变化 |
针对泛在末梢网络中节点的移动性和能量有限性，提出基于可靠性预测的服务发现与选择协议RPD & S.建立预测节点的移动速度矢量模型.通过仿真实验模拟表明，RPD & S能有效降低服务查找失败率及服务执行中断率，提高服务的可靠性和用户体验.在以后的研究中，将研究用户移动模型，使得可靠性预测更精准，RPD & S更完善.
| [1] | Wang Yun, Chu Xiaoyu, Wang Xinbing. Optimal multicast capacity and delay tradeoffs in MANETs[C]//A Global Perspective INFOCOM, 2011 Proceedings. Shanghai: IEEE, 2011: 640-648. |
| [2] | Sun Yan, Phillips C, Wang S. An improved QoS awareness scheduling scheme for CR Mobile ad hoc networks[C]//Wireless Telecommunications Symposium (WTS). Phoenix: [s. n. ], 2013: 1-6. |
| [3] | Kidston D, Li Li, Al Mamun W. Cross-layer cluster-based data dissemination for failure detection in MANETs[C]// Network and Service Management (CNSM). Paris: International Conference, 2011: 290-293. |
| [4] | Fathy C, El-Hadidi M T, El-Nasr M A. Fuzzy-based adaptive cross layer routing protocol for delay sensitive applications in MANET[C]//Communications (ICC). Ottawa: IEEE International Conference, 2012: 248-253. |
| [5] | Liu Wang, Lu Kejie, Wang Jianping, et al. On the throughput-delay trade-off in large-scale MANETs with a generalized i. i. d[C]//Mobility Model INFOCOM. Turin: Proceedings IEEE, 2013: 1321-1329. |