一种适用于工业无线传感器网络的资源均衡多径路由方法

摘要

本发明是一种适用于工业无线传感器网络中基于资源均衡策略的多径路由方法，涉及工业无线传感器网络；该路由方法采用跨层设计的思想，对物理层的数据收发能量消耗以及网络层的转发队列内存消耗进行综合评估，提出基于资源均衡因子的路径优先级判定策略。同时结合广度优先搜索算法，计算出从数据源节点到目的节点间的多条冗余路径，既满足了工业无线传感器网络均衡节点资源的要求，也提高了源节点与目的节点之间通信的可靠性。发明以ISA100.11a网络为例，当ISA100.11a网络中系统管理器进行路由路径计算时，会基于当前网络的拓扑以及各个传感器节点的资源消耗情况，计算出一条优选路径以及多条备选路径，并把路由信息分发存储到路径上的各个节点中，完成路由的配置。经验证，算法可行及达到预期效果。

主权项

一种适用于工业无线传感器网络的资源均衡多径路由方法，其特征在于：主要包括以下步骤： 步骤一：当前网络拓扑为G(V,E)，V表示网络中的传感器节点的集合，E表示传感器节点之间相连的边的集合，从数据传输的目的节点出发，遍历网络中的每一个传感器节点，计算广度优先搜索生成树T_BFS； 步骤二：根据步骤一中计算得到的生成树T_BFS，其叶子节点组成叶子节点集合V_leaf。创建集合M和一个先进先出的队列Q； 步骤三：任意取出步骤二V_leaf中的一个叶子节点V_j(j＝1,2,...,k)，k为叶子节点总数，把V_j加入集合M。若V_leaf为空，则转至步骤七； 步骤四：从集合M中取出一个元素V_d，设元素V_d在步骤一所述的生成树T_BFS中的深度为d，取所有深度为d‑1且在G(V,E)中与V_d有相连边的传感器节点，加入集合M； 步骤五：取出当前集合M中的所有节点V_i(i＝1,2,...,n)，n为集合M中传感器节点的数量，计算其资源均衡因子k_i。根据k_i从小到大的顺序，步骤四中的节点V_d依次选取V_i作为其下一跳节点，并在V_d与V_i间生成多跳冗余路径，其中选择传感器节点V_t(k_t＝min{k₁,k₂,...,k_n})为下一跳优选节点，并生成优选路径e_dt，e_dt表示一条从节点V_d指向节点V_t的边，加入ROUTE_j中，ROUTE_j用来存储当前已生成的从叶子节点V_j到目的节点的路由路径，j用来标识步骤三中当前正在处理的叶子节点V_j。选择其余节点V_q(q＝1,2,...,n,q≠t)为下一跳备选节点，并生成多条备选路径e_dq加入ROUTE_j中，备选路径e_dq根据对应传感器节点V_q的k_q(q＝1,2,...,n,q≠t)值按从小到大的顺序排列为第一备选路径、第二备选路径等，路径优先级逐渐递减。最后，若V_i在前面的步骤中没有被加入过队列Q，则把V_i按照其k_i从小到大的顺序依次放入队列Q中； 步骤六：取出步骤五Q队列中的第一个传感器节点，若该节点不是数据传输的目的节点，则把该节点加入集合M，执行步骤四，否则表明从步骤三中叶子节点V_j到目的节点的路径已求出，且已保存于ROUTE_j(j＝1,2,...,k)中，k为叶子节点总数。此时清空集合M和队列Q，执行步骤三； 步骤七：对于计算得到的ROUTE_j(j＝1,2,...,k)进行如下优化。若对于某一个ROUTE_i中包含的所有路径，存在一个ROUTE_j同样包含这些路径，称ROUTE_i包含于ROUTE_j中，则删除ROUTE_i，只保留ROUTE_j。 步骤八：为优化过后的每一个ROUTE_j(j＝1,2,...,k)分配唯一的路由ID标识ID₁,ID₂,...,ID_k，对于ROUTE_j中的每一条路径e_ab，表明传感器节点V_a存在下一跳节点V_b，把ID_j以及V_b分发到V_a的路由表中。下一跳节点包括下一跳优选节点和下一跳备选节点，每个传感器节点的路由表记录分发得到的路由ID以及路由ID对应的下一跳优选节点、备选节点。