一种在无线自组织网络中的基于位置信息的组合服务执行路径选择方法

摘要

本发明属于自组织网络技术领域，具体是一种在无线自组织网络中的基于位置信息的组合服务执行路径选择方法。整个最短执行路径选择的过程包括相邻节间的跳数估计算法、线性类型组合服务最短执行路径选择、并发类型组合服务最短执行路径选择三个部分。本方法在保证服务执行成功率的基础上，大大降低了平均执行路径长度，减少了数据传输的时间和缩短了服务应答的时间，从而更好地适应无线自组织网络环境。

主权项

1.一种在无线自组织网络中基于位置信息的组合服务执行路径的选择方法，其特征在于包括相邻节点间的跳数估计算法、线性类型组合服务最短执行路径选择、并发类型组合服务最短执行路径选择：⑴跳数估计算法根据节点的位置信息估计节点间的跳数，定义：N：表示一个节点的集合；|N|：表示集合中节点的个数；L*L：表示L长L宽面积的节点分布范围；L²/|N|：表示节点平均覆盖范围；R：表示每个节点传输数据的半径；D：两节点间的距离；d_k：表示某节点k跳范围的传播半径；公共域S：两个圆相交的部分面积；圆心角α和β：两个圆相交的圆心角，即，记两个圆的圆心为o₁和o₂，记两圆的两个交点为P和Q，则α和β分别定义为∠Po₁o₂和∠Po₂o₁；如果A、B两节点的距离D＜R，两节点直接通信，跳数记为1跳，即d₁为R；如果A、B两节点的距离2R＞D＞R，A、B两个节点的传播覆盖面积分别为一个半径为R的圆，若两个圆相交，公共域S为2R²α-RDsinα，当S＞L²/|N|时，A和B经过一个中间节点完成两者间的通信，从而算出A点在2跳范围下的传播半径d₂；用d_k代表相距k跳的两节点的最大距离，且d_k已知；以A为圆心的圆覆盖的是A在k跳下的传播数据范围；两个圆的公共域S为当S>L²/|N|时A、B间相距k+1跳；变量代换后得算出d_k+1的数值；以此类推得到d_k的所有值，其中k=1，2……|n|；最后在得到A、B两节点的距离D后，符合d_k＜D＜d_k+1这样的d_k和d_k+1时，A、B间的跳数为k+1跳；且d_k和d_k+1满足和Rsinβ＝d_ksinα；⑵构建全局加权有向图定义一个有向加权图，当且仅当一个节点是另一节点的前一服务时，两者之间存在一条边，边的权重为两个节点之间的跳数，如果连续的两个服务都在同一节点上部署，两个服务间的跳数记为0，即权重为0；如果两个节点之间无法通信，权重定为无限大，如此构成一个加权有向图；⑶计算最短执行路径根据加权有向图，由服务请求节点为组合服务选择最短执行路径；组合服务分为线性类型和并发类型两类；在并发类型的组合服务中，采用改良的算法对原始加权有向图进行处理，将并发类型转化成线性类型；并发类组合服务的最短执行路径选择步骤如下：步骤1：给拓扑图加权；步骤2：找到服务分离点和服务汇合点；步骤3：对每组分支实例计算其最长路径；步骤4：使用Dijkstra算法得出最短执行路径；步骤5：还原删掉的分支路径。